1 //===- CodeGenDAGPatterns.cpp - Read DAG patterns from .td file -----------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements the CodeGenDAGPatterns class, which is used to read and 11 // represent the patterns present in a .td file for instructions. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "CodeGenDAGPatterns.h" 16 #include "llvm/TableGen/Error.h" 17 #include "llvm/TableGen/Record.h" 18 #include "llvm/ADT/StringExtras.h" 19 #include "llvm/ADT/STLExtras.h" 20 #include "llvm/ADT/Twine.h" 21 #include "llvm/Support/Debug.h" 22 #include "llvm/Support/ErrorHandling.h" 23 #include <algorithm> 24 #include <cstdio> 25 #include <set> 26 using namespace llvm; 27 28 //===----------------------------------------------------------------------===// 29 // EEVT::TypeSet Implementation 30 //===----------------------------------------------------------------------===// 31 32 static inline bool isInteger(MVT::SimpleValueType VT) { 33 return EVT(VT).isInteger(); 34 } 35 static inline bool isFloatingPoint(MVT::SimpleValueType VT) { 36 return EVT(VT).isFloatingPoint(); 37 } 38 static inline bool isVector(MVT::SimpleValueType VT) { 39 return EVT(VT).isVector(); 40 } 41 static inline bool isScalar(MVT::SimpleValueType VT) { 42 return !EVT(VT).isVector(); 43 } 44 45 EEVT::TypeSet::TypeSet(MVT::SimpleValueType VT, TreePattern &TP) { 46 if (VT == MVT::iAny) 47 EnforceInteger(TP); 48 else if (VT == MVT::fAny) 49 EnforceFloatingPoint(TP); 50 else if (VT == MVT::vAny) 51 EnforceVector(TP); 52 else { 53 assert((VT < MVT::LAST_VALUETYPE || VT == MVT::iPTR || 54 VT == MVT::iPTRAny) && "Not a concrete type!"); 55 TypeVec.push_back(VT); 56 } 57 } 58 59 60 EEVT::TypeSet::TypeSet(const std::vector<MVT::SimpleValueType> &VTList) { 61 assert(!VTList.empty() && "empty list?"); 62 TypeVec.append(VTList.begin(), VTList.end()); 63 64 if (!VTList.empty()) 65 assert(VTList[0] != MVT::iAny && VTList[0] != MVT::vAny && 66 VTList[0] != MVT::fAny); 67 68 // Verify no duplicates. 69 array_pod_sort(TypeVec.begin(), TypeVec.end()); 70 assert(std::unique(TypeVec.begin(), TypeVec.end()) == TypeVec.end()); 71 } 72 73 /// FillWithPossibleTypes - Set to all legal types and return true, only valid 74 /// on completely unknown type sets. 75 bool EEVT::TypeSet::FillWithPossibleTypes(TreePattern &TP, 76 bool (*Pred)(MVT::SimpleValueType), 77 const char *PredicateName) { 78 assert(isCompletelyUnknown()); 79 const std::vector<MVT::SimpleValueType> &LegalTypes = 80 TP.getDAGPatterns().getTargetInfo().getLegalValueTypes(); 81 82 for (unsigned i = 0, e = LegalTypes.size(); i != e; ++i) 83 if (Pred == 0 || Pred(LegalTypes[i])) 84 TypeVec.push_back(LegalTypes[i]); 85 86 // If we have nothing that matches the predicate, bail out. 87 if (TypeVec.empty()) 88 TP.error("Type inference contradiction found, no " + 89 std::string(PredicateName) + " types found"); 90 // No need to sort with one element. 91 if (TypeVec.size() == 1) return true; 92 93 // Remove duplicates. 94 array_pod_sort(TypeVec.begin(), TypeVec.end()); 95 TypeVec.erase(std::unique(TypeVec.begin(), TypeVec.end()), TypeVec.end()); 96 97 return true; 98 } 99 100 /// hasIntegerTypes - Return true if this TypeSet contains iAny or an 101 /// integer value type. 102 bool EEVT::TypeSet::hasIntegerTypes() const { 103 for (unsigned i = 0, e = TypeVec.size(); i != e; ++i) 104 if (isInteger(TypeVec[i])) 105 return true; 106 return false; 107 } 108 109 /// hasFloatingPointTypes - Return true if this TypeSet contains an fAny or 110 /// a floating point value type. 111 bool EEVT::TypeSet::hasFloatingPointTypes() const { 112 for (unsigned i = 0, e = TypeVec.size(); i != e; ++i) 113 if (isFloatingPoint(TypeVec[i])) 114 return true; 115 return false; 116 } 117 118 /// hasVectorTypes - Return true if this TypeSet contains a vAny or a vector 119 /// value type. 120 bool EEVT::TypeSet::hasVectorTypes() const { 121 for (unsigned i = 0, e = TypeVec.size(); i != e; ++i) 122 if (isVector(TypeVec[i])) 123 return true; 124 return false; 125 } 126 127 128 std::string EEVT::TypeSet::getName() const { 129 if (TypeVec.empty()) return "<empty>"; 130 131 std::string Result; 132 133 for (unsigned i = 0, e = TypeVec.size(); i != e; ++i) { 134 std::string VTName = llvm::getEnumName(TypeVec[i]); 135 // Strip off MVT:: prefix if present. 136 if (VTName.substr(0,5) == "MVT::") 137 VTName = VTName.substr(5); 138 if (i) Result += ':'; 139 Result += VTName; 140 } 141 142 if (TypeVec.size() == 1) 143 return Result; 144 return "{" + Result + "}"; 145 } 146 147 /// MergeInTypeInfo - This merges in type information from the specified 148 /// argument. If 'this' changes, it returns true. If the two types are 149 /// contradictory (e.g. merge f32 into i32) then this throws an exception. 150 bool EEVT::TypeSet::MergeInTypeInfo(const EEVT::TypeSet &InVT, TreePattern &TP){ 151 if (InVT.isCompletelyUnknown() || *this == InVT) 152 return false; 153 154 if (isCompletelyUnknown()) { 155 *this = InVT; 156 return true; 157 } 158 159 assert(TypeVec.size() >= 1 && InVT.TypeVec.size() >= 1 && "No unknowns"); 160 161 // Handle the abstract cases, seeing if we can resolve them better. 162 switch (TypeVec[0]) { 163 default: break; 164 case MVT::iPTR: 165 case MVT::iPTRAny: 166 if (InVT.hasIntegerTypes()) { 167 EEVT::TypeSet InCopy(InVT); 168 InCopy.EnforceInteger(TP); 169 InCopy.EnforceScalar(TP); 170 171 if (InCopy.isConcrete()) { 172 // If the RHS has one integer type, upgrade iPTR to i32. 173 TypeVec[0] = InVT.TypeVec[0]; 174 return true; 175 } 176 177 // If the input has multiple scalar integers, this doesn't add any info. 178 if (!InCopy.isCompletelyUnknown()) 179 return false; 180 } 181 break; 182 } 183 184 // If the input constraint is iAny/iPTR and this is an integer type list, 185 // remove non-integer types from the list. 186 if ((InVT.TypeVec[0] == MVT::iPTR || InVT.TypeVec[0] == MVT::iPTRAny) && 187 hasIntegerTypes()) { 188 bool MadeChange = EnforceInteger(TP); 189 190 // If we're merging in iPTR/iPTRAny and the node currently has a list of 191 // multiple different integer types, replace them with a single iPTR. 192 if ((InVT.TypeVec[0] == MVT::iPTR || InVT.TypeVec[0] == MVT::iPTRAny) && 193 TypeVec.size() != 1) { 194 TypeVec.resize(1); 195 TypeVec[0] = InVT.TypeVec[0]; 196 MadeChange = true; 197 } 198 199 return MadeChange; 200 } 201 202 // If this is a type list and the RHS is a typelist as well, eliminate entries 203 // from this list that aren't in the other one. 204 bool MadeChange = false; 205 TypeSet InputSet(*this); 206 207 for (unsigned i = 0; i != TypeVec.size(); ++i) { 208 bool InInVT = false; 209 for (unsigned j = 0, e = InVT.TypeVec.size(); j != e; ++j) 210 if (TypeVec[i] == InVT.TypeVec[j]) { 211 InInVT = true; 212 break; 213 } 214 215 if (InInVT) continue; 216 TypeVec.erase(TypeVec.begin()+i--); 217 MadeChange = true; 218 } 219 220 // If we removed all of our types, we have a type contradiction. 221 if (!TypeVec.empty()) 222 return MadeChange; 223 224 // FIXME: Really want an SMLoc here! 225 TP.error("Type inference contradiction found, merging '" + 226 InVT.getName() + "' into '" + InputSet.getName() + "'"); 227 return true; // unreachable 228 } 229 230 /// EnforceInteger - Remove all non-integer types from this set. 231 bool EEVT::TypeSet::EnforceInteger(TreePattern &TP) { 232 // If we know nothing, then get the full set. 233 if (TypeVec.empty()) 234 return FillWithPossibleTypes(TP, isInteger, "integer"); 235 if (!hasFloatingPointTypes()) 236 return false; 237 238 TypeSet InputSet(*this); 239 240 // Filter out all the fp types. 241 for (unsigned i = 0; i != TypeVec.size(); ++i) 242 if (!isInteger(TypeVec[i])) 243 TypeVec.erase(TypeVec.begin()+i--); 244 245 if (TypeVec.empty()) 246 TP.error("Type inference contradiction found, '" + 247 InputSet.getName() + "' needs to be integer"); 248 return true; 249 } 250 251 /// EnforceFloatingPoint - Remove all integer types from this set. 252 bool EEVT::TypeSet::EnforceFloatingPoint(TreePattern &TP) { 253 // If we know nothing, then get the full set. 254 if (TypeVec.empty()) 255 return FillWithPossibleTypes(TP, isFloatingPoint, "floating point"); 256 257 if (!hasIntegerTypes()) 258 return false; 259 260 TypeSet InputSet(*this); 261 262 // Filter out all the fp types. 263 for (unsigned i = 0; i != TypeVec.size(); ++i) 264 if (!isFloatingPoint(TypeVec[i])) 265 TypeVec.erase(TypeVec.begin()+i--); 266 267 if (TypeVec.empty()) 268 TP.error("Type inference contradiction found, '" + 269 InputSet.getName() + "' needs to be floating point"); 270 return true; 271 } 272 273 /// EnforceScalar - Remove all vector types from this. 274 bool EEVT::TypeSet::EnforceScalar(TreePattern &TP) { 275 // If we know nothing, then get the full set. 276 if (TypeVec.empty()) 277 return FillWithPossibleTypes(TP, isScalar, "scalar"); 278 279 if (!hasVectorTypes()) 280 return false; 281 282 TypeSet InputSet(*this); 283 284 // Filter out all the vector types. 285 for (unsigned i = 0; i != TypeVec.size(); ++i) 286 if (!isScalar(TypeVec[i])) 287 TypeVec.erase(TypeVec.begin()+i--); 288 289 if (TypeVec.empty()) 290 TP.error("Type inference contradiction found, '" + 291 InputSet.getName() + "' needs to be scalar"); 292 return true; 293 } 294 295 /// EnforceVector - Remove all vector types from this. 296 bool EEVT::TypeSet::EnforceVector(TreePattern &TP) { 297 // If we know nothing, then get the full set. 298 if (TypeVec.empty()) 299 return FillWithPossibleTypes(TP, isVector, "vector"); 300 301 TypeSet InputSet(*this); 302 bool MadeChange = false; 303 304 // Filter out all the scalar types. 305 for (unsigned i = 0; i != TypeVec.size(); ++i) 306 if (!isVector(TypeVec[i])) { 307 TypeVec.erase(TypeVec.begin()+i--); 308 MadeChange = true; 309 } 310 311 if (TypeVec.empty()) 312 TP.error("Type inference contradiction found, '" + 313 InputSet.getName() + "' needs to be a vector"); 314 return MadeChange; 315 } 316 317 318 319 /// EnforceSmallerThan - 'this' must be a smaller VT than Other. Update 320 /// this an other based on this information. 321 bool EEVT::TypeSet::EnforceSmallerThan(EEVT::TypeSet &Other, TreePattern &TP) { 322 // Both operands must be integer or FP, but we don't care which. 323 bool MadeChange = false; 324 325 if (isCompletelyUnknown()) 326 MadeChange = FillWithPossibleTypes(TP); 327 328 if (Other.isCompletelyUnknown()) 329 MadeChange = Other.FillWithPossibleTypes(TP); 330 331 // If one side is known to be integer or known to be FP but the other side has 332 // no information, get at least the type integrality info in there. 333 if (!hasFloatingPointTypes()) 334 MadeChange |= Other.EnforceInteger(TP); 335 else if (!hasIntegerTypes()) 336 MadeChange |= Other.EnforceFloatingPoint(TP); 337 if (!Other.hasFloatingPointTypes()) 338 MadeChange |= EnforceInteger(TP); 339 else if (!Other.hasIntegerTypes()) 340 MadeChange |= EnforceFloatingPoint(TP); 341 342 assert(!isCompletelyUnknown() && !Other.isCompletelyUnknown() && 343 "Should have a type list now"); 344 345 // If one contains vectors but the other doesn't pull vectors out. 346 if (!hasVectorTypes()) 347 MadeChange |= Other.EnforceScalar(TP); 348 if (!hasVectorTypes()) 349 MadeChange |= EnforceScalar(TP); 350 351 if (TypeVec.size() == 1 && Other.TypeVec.size() == 1) { 352 // If we are down to concrete types, this code does not currently 353 // handle nodes which have multiple types, where some types are 354 // integer, and some are fp. Assert that this is not the case. 355 assert(!(hasIntegerTypes() && hasFloatingPointTypes()) && 356 !(Other.hasIntegerTypes() && Other.hasFloatingPointTypes()) && 357 "SDTCisOpSmallerThanOp does not handle mixed int/fp types!"); 358 359 // Otherwise, if these are both vector types, either this vector 360 // must have a larger bitsize than the other, or this element type 361 // must be larger than the other. 362 EVT Type(TypeVec[0]); 363 EVT OtherType(Other.TypeVec[0]); 364 365 if (hasVectorTypes() && Other.hasVectorTypes()) { 366 if (Type.getSizeInBits() >= OtherType.getSizeInBits()) 367 if (Type.getVectorElementType().getSizeInBits() 368 >= OtherType.getVectorElementType().getSizeInBits()) 369 TP.error("Type inference contradiction found, '" + 370 getName() + "' element type not smaller than '" + 371 Other.getName() +"'!"); 372 } 373 else 374 // For scalar types, the bitsize of this type must be larger 375 // than that of the other. 376 if (Type.getSizeInBits() >= OtherType.getSizeInBits()) 377 TP.error("Type inference contradiction found, '" + 378 getName() + "' is not smaller than '" + 379 Other.getName() +"'!"); 380 381 } 382 383 384 // Handle int and fp as disjoint sets. This won't work for patterns 385 // that have mixed fp/int types but those are likely rare and would 386 // not have been accepted by this code previously. 387 388 // Okay, find the smallest type from the current set and remove it from the 389 // largest set. 390 MVT::SimpleValueType SmallestInt = MVT::LAST_VALUETYPE; 391 for (unsigned i = 0, e = TypeVec.size(); i != e; ++i) 392 if (isInteger(TypeVec[i])) { 393 SmallestInt = TypeVec[i]; 394 break; 395 } 396 for (unsigned i = 1, e = TypeVec.size(); i != e; ++i) 397 if (isInteger(TypeVec[i]) && TypeVec[i] < SmallestInt) 398 SmallestInt = TypeVec[i]; 399 400 MVT::SimpleValueType SmallestFP = MVT::LAST_VALUETYPE; 401 for (unsigned i = 0, e = TypeVec.size(); i != e; ++i) 402 if (isFloatingPoint(TypeVec[i])) { 403 SmallestFP = TypeVec[i]; 404 break; 405 } 406 for (unsigned i = 1, e = TypeVec.size(); i != e; ++i) 407 if (isFloatingPoint(TypeVec[i]) && TypeVec[i] < SmallestFP) 408 SmallestFP = TypeVec[i]; 409 410 int OtherIntSize = 0; 411 int OtherFPSize = 0; 412 for (SmallVector<MVT::SimpleValueType, 2>::iterator TVI = 413 Other.TypeVec.begin(); 414 TVI != Other.TypeVec.end(); 415 /* NULL */) { 416 if (isInteger(*TVI)) { 417 ++OtherIntSize; 418 if (*TVI == SmallestInt) { 419 TVI = Other.TypeVec.erase(TVI); 420 --OtherIntSize; 421 MadeChange = true; 422 continue; 423 } 424 } 425 else if (isFloatingPoint(*TVI)) { 426 ++OtherFPSize; 427 if (*TVI == SmallestFP) { 428 TVI = Other.TypeVec.erase(TVI); 429 --OtherFPSize; 430 MadeChange = true; 431 continue; 432 } 433 } 434 ++TVI; 435 } 436 437 // If this is the only type in the large set, the constraint can never be 438 // satisfied. 439 if ((Other.hasIntegerTypes() && OtherIntSize == 0) 440 || (Other.hasFloatingPointTypes() && OtherFPSize == 0)) 441 TP.error("Type inference contradiction found, '" + 442 Other.getName() + "' has nothing larger than '" + getName() +"'!"); 443 444 // Okay, find the largest type in the Other set and remove it from the 445 // current set. 446 MVT::SimpleValueType LargestInt = MVT::Other; 447 for (unsigned i = 0, e = Other.TypeVec.size(); i != e; ++i) 448 if (isInteger(Other.TypeVec[i])) { 449 LargestInt = Other.TypeVec[i]; 450 break; 451 } 452 for (unsigned i = 1, e = Other.TypeVec.size(); i != e; ++i) 453 if (isInteger(Other.TypeVec[i]) && Other.TypeVec[i] > LargestInt) 454 LargestInt = Other.TypeVec[i]; 455 456 MVT::SimpleValueType LargestFP = MVT::Other; 457 for (unsigned i = 0, e = Other.TypeVec.size(); i != e; ++i) 458 if (isFloatingPoint(Other.TypeVec[i])) { 459 LargestFP = Other.TypeVec[i]; 460 break; 461 } 462 for (unsigned i = 1, e = Other.TypeVec.size(); i != e; ++i) 463 if (isFloatingPoint(Other.TypeVec[i]) && Other.TypeVec[i] > LargestFP) 464 LargestFP = Other.TypeVec[i]; 465 466 int IntSize = 0; 467 int FPSize = 0; 468 for (SmallVector<MVT::SimpleValueType, 2>::iterator TVI = 469 TypeVec.begin(); 470 TVI != TypeVec.end(); 471 /* NULL */) { 472 if (isInteger(*TVI)) { 473 ++IntSize; 474 if (*TVI == LargestInt) { 475 TVI = TypeVec.erase(TVI); 476 --IntSize; 477 MadeChange = true; 478 continue; 479 } 480 } 481 else if (isFloatingPoint(*TVI)) { 482 ++FPSize; 483 if (*TVI == LargestFP) { 484 TVI = TypeVec.erase(TVI); 485 --FPSize; 486 MadeChange = true; 487 continue; 488 } 489 } 490 ++TVI; 491 } 492 493 // If this is the only type in the small set, the constraint can never be 494 // satisfied. 495 if ((hasIntegerTypes() && IntSize == 0) 496 || (hasFloatingPointTypes() && FPSize == 0)) 497 TP.error("Type inference contradiction found, '" + 498 getName() + "' has nothing smaller than '" + Other.getName()+"'!"); 499 500 return MadeChange; 501 } 502 503 /// EnforceVectorEltTypeIs - 'this' is now constrainted to be a vector type 504 /// whose element is specified by VTOperand. 505 bool EEVT::TypeSet::EnforceVectorEltTypeIs(EEVT::TypeSet &VTOperand, 506 TreePattern &TP) { 507 // "This" must be a vector and "VTOperand" must be a scalar. 508 bool MadeChange = false; 509 MadeChange |= EnforceVector(TP); 510 MadeChange |= VTOperand.EnforceScalar(TP); 511 512 // If we know the vector type, it forces the scalar to agree. 513 if (isConcrete()) { 514 EVT IVT = getConcrete(); 515 IVT = IVT.getVectorElementType(); 516 return MadeChange | 517 VTOperand.MergeInTypeInfo(IVT.getSimpleVT().SimpleTy, TP); 518 } 519 520 // If the scalar type is known, filter out vector types whose element types 521 // disagree. 522 if (!VTOperand.isConcrete()) 523 return MadeChange; 524 525 MVT::SimpleValueType VT = VTOperand.getConcrete(); 526 527 TypeSet InputSet(*this); 528 529 // Filter out all the types which don't have the right element type. 530 for (unsigned i = 0; i != TypeVec.size(); ++i) { 531 assert(isVector(TypeVec[i]) && "EnforceVector didn't work"); 532 if (EVT(TypeVec[i]).getVectorElementType().getSimpleVT().SimpleTy != VT) { 533 TypeVec.erase(TypeVec.begin()+i--); 534 MadeChange = true; 535 } 536 } 537 538 if (TypeVec.empty()) // FIXME: Really want an SMLoc here! 539 TP.error("Type inference contradiction found, forcing '" + 540 InputSet.getName() + "' to have a vector element"); 541 return MadeChange; 542 } 543 544 /// EnforceVectorSubVectorTypeIs - 'this' is now constrainted to be a 545 /// vector type specified by VTOperand. 546 bool EEVT::TypeSet::EnforceVectorSubVectorTypeIs(EEVT::TypeSet &VTOperand, 547 TreePattern &TP) { 548 // "This" must be a vector and "VTOperand" must be a vector. 549 bool MadeChange = false; 550 MadeChange |= EnforceVector(TP); 551 MadeChange |= VTOperand.EnforceVector(TP); 552 553 // "This" must be larger than "VTOperand." 554 MadeChange |= VTOperand.EnforceSmallerThan(*this, TP); 555 556 // If we know the vector type, it forces the scalar types to agree. 557 if (isConcrete()) { 558 EVT IVT = getConcrete(); 559 IVT = IVT.getVectorElementType(); 560 561 EEVT::TypeSet EltTypeSet(IVT.getSimpleVT().SimpleTy, TP); 562 MadeChange |= VTOperand.EnforceVectorEltTypeIs(EltTypeSet, TP); 563 } else if (VTOperand.isConcrete()) { 564 EVT IVT = VTOperand.getConcrete(); 565 IVT = IVT.getVectorElementType(); 566 567 EEVT::TypeSet EltTypeSet(IVT.getSimpleVT().SimpleTy, TP); 568 MadeChange |= EnforceVectorEltTypeIs(EltTypeSet, TP); 569 } 570 571 return MadeChange; 572 } 573 574 //===----------------------------------------------------------------------===// 575 // Helpers for working with extended types. 576 577 bool RecordPtrCmp::operator()(const Record *LHS, const Record *RHS) const { 578 return LHS->getID() < RHS->getID(); 579 } 580 581 /// Dependent variable map for CodeGenDAGPattern variant generation 582 typedef std::map<std::string, int> DepVarMap; 583 584 /// Const iterator shorthand for DepVarMap 585 typedef DepVarMap::const_iterator DepVarMap_citer; 586 587 static void FindDepVarsOf(TreePatternNode *N, DepVarMap &DepMap) { 588 if (N->isLeaf()) { 589 if (dynamic_cast<DefInit*>(N->getLeafValue()) != NULL) 590 DepMap[N->getName()]++; 591 } else { 592 for (size_t i = 0, e = N->getNumChildren(); i != e; ++i) 593 FindDepVarsOf(N->getChild(i), DepMap); 594 } 595 } 596 597 /// Find dependent variables within child patterns 598 static void FindDepVars(TreePatternNode *N, MultipleUseVarSet &DepVars) { 599 DepVarMap depcounts; 600 FindDepVarsOf(N, depcounts); 601 for (DepVarMap_citer i = depcounts.begin(); i != depcounts.end(); ++i) { 602 if (i->second > 1) // std::pair<std::string, int> 603 DepVars.insert(i->first); 604 } 605 } 606 607 #ifndef NDEBUG 608 /// Dump the dependent variable set: 609 static void DumpDepVars(MultipleUseVarSet &DepVars) { 610 if (DepVars.empty()) { 611 DEBUG(errs() << "<empty set>"); 612 } else { 613 DEBUG(errs() << "[ "); 614 for (MultipleUseVarSet::const_iterator i = DepVars.begin(), 615 e = DepVars.end(); i != e; ++i) { 616 DEBUG(errs() << (*i) << " "); 617 } 618 DEBUG(errs() << "]"); 619 } 620 } 621 #endif 622 623 624 //===----------------------------------------------------------------------===// 625 // TreePredicateFn Implementation 626 //===----------------------------------------------------------------------===// 627 628 /// TreePredicateFn constructor. Here 'N' is a subclass of PatFrag. 629 TreePredicateFn::TreePredicateFn(TreePattern *N) : PatFragRec(N) { 630 assert((getPredCode().empty() || getImmCode().empty()) && 631 ".td file corrupt: can't have a node predicate *and* an imm predicate"); 632 } 633 634 std::string TreePredicateFn::getPredCode() const { 635 return PatFragRec->getRecord()->getValueAsString("PredicateCode"); 636 } 637 638 std::string TreePredicateFn::getImmCode() const { 639 return PatFragRec->getRecord()->getValueAsString("ImmediateCode"); 640 } 641 642 643 /// isAlwaysTrue - Return true if this is a noop predicate. 644 bool TreePredicateFn::isAlwaysTrue() const { 645 return getPredCode().empty() && getImmCode().empty(); 646 } 647 648 /// Return the name to use in the generated code to reference this, this is 649 /// "Predicate_foo" if from a pattern fragment "foo". 650 std::string TreePredicateFn::getFnName() const { 651 return "Predicate_" + PatFragRec->getRecord()->getName(); 652 } 653 654 /// getCodeToRunOnSDNode - Return the code for the function body that 655 /// evaluates this predicate. The argument is expected to be in "Node", 656 /// not N. This handles casting and conversion to a concrete node type as 657 /// appropriate. 658 std::string TreePredicateFn::getCodeToRunOnSDNode() const { 659 // Handle immediate predicates first. 660 std::string ImmCode = getImmCode(); 661 if (!ImmCode.empty()) { 662 std::string Result = 663 " int64_t Imm = cast<ConstantSDNode>(Node)->getSExtValue();\n"; 664 return Result + ImmCode; 665 } 666 667 // Handle arbitrary node predicates. 668 assert(!getPredCode().empty() && "Don't have any predicate code!"); 669 std::string ClassName; 670 if (PatFragRec->getOnlyTree()->isLeaf()) 671 ClassName = "SDNode"; 672 else { 673 Record *Op = PatFragRec->getOnlyTree()->getOperator(); 674 ClassName = PatFragRec->getDAGPatterns().getSDNodeInfo(Op).getSDClassName(); 675 } 676 std::string Result; 677 if (ClassName == "SDNode") 678 Result = " SDNode *N = Node;\n"; 679 else 680 Result = " " + ClassName + "*N = cast<" + ClassName + ">(Node);\n"; 681 682 return Result + getPredCode(); 683 } 684 685 //===----------------------------------------------------------------------===// 686 // PatternToMatch implementation 687 // 688 689 690 /// getPatternSize - Return the 'size' of this pattern. We want to match large 691 /// patterns before small ones. This is used to determine the size of a 692 /// pattern. 693 static unsigned getPatternSize(const TreePatternNode *P, 694 const CodeGenDAGPatterns &CGP) { 695 unsigned Size = 3; // The node itself. 696 // If the root node is a ConstantSDNode, increases its size. 697 // e.g. (set R32:$dst, 0). 698 if (P->isLeaf() && dynamic_cast<IntInit*>(P->getLeafValue())) 699 Size += 2; 700 701 // FIXME: This is a hack to statically increase the priority of patterns 702 // which maps a sub-dag to a complex pattern. e.g. favors LEA over ADD. 703 // Later we can allow complexity / cost for each pattern to be (optionally) 704 // specified. To get best possible pattern match we'll need to dynamically 705 // calculate the complexity of all patterns a dag can potentially map to. 706 const ComplexPattern *AM = P->getComplexPatternInfo(CGP); 707 if (AM) 708 Size += AM->getNumOperands() * 3; 709 710 // If this node has some predicate function that must match, it adds to the 711 // complexity of this node. 712 if (!P->getPredicateFns().empty()) 713 ++Size; 714 715 // Count children in the count if they are also nodes. 716 for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) { 717 TreePatternNode *Child = P->getChild(i); 718 if (!Child->isLeaf() && Child->getNumTypes() && 719 Child->getType(0) != MVT::Other) 720 Size += getPatternSize(Child, CGP); 721 else if (Child->isLeaf()) { 722 if (dynamic_cast<IntInit*>(Child->getLeafValue())) 723 Size += 5; // Matches a ConstantSDNode (+3) and a specific value (+2). 724 else if (Child->getComplexPatternInfo(CGP)) 725 Size += getPatternSize(Child, CGP); 726 else if (!Child->getPredicateFns().empty()) 727 ++Size; 728 } 729 } 730 731 return Size; 732 } 733 734 /// Compute the complexity metric for the input pattern. This roughly 735 /// corresponds to the number of nodes that are covered. 736 unsigned PatternToMatch:: 737 getPatternComplexity(const CodeGenDAGPatterns &CGP) const { 738 return getPatternSize(getSrcPattern(), CGP) + getAddedComplexity(); 739 } 740 741 742 /// getPredicateCheck - Return a single string containing all of this 743 /// pattern's predicates concatenated with "&&" operators. 744 /// 745 std::string PatternToMatch::getPredicateCheck() const { 746 std::string PredicateCheck; 747 for (unsigned i = 0, e = Predicates->getSize(); i != e; ++i) { 748 if (DefInit *Pred = dynamic_cast<DefInit*>(Predicates->getElement(i))) { 749 Record *Def = Pred->getDef(); 750 if (!Def->isSubClassOf("Predicate")) { 751 #ifndef NDEBUG 752 Def->dump(); 753 #endif 754 llvm_unreachable("Unknown predicate type!"); 755 } 756 if (!PredicateCheck.empty()) 757 PredicateCheck += " && "; 758 PredicateCheck += "(" + Def->getValueAsString("CondString") + ")"; 759 } 760 } 761 762 return PredicateCheck; 763 } 764 765 //===----------------------------------------------------------------------===// 766 // SDTypeConstraint implementation 767 // 768 769 SDTypeConstraint::SDTypeConstraint(Record *R) { 770 OperandNo = R->getValueAsInt("OperandNum"); 771 772 if (R->isSubClassOf("SDTCisVT")) { 773 ConstraintType = SDTCisVT; 774 x.SDTCisVT_Info.VT = getValueType(R->getValueAsDef("VT")); 775 if (x.SDTCisVT_Info.VT == MVT::isVoid) 776 throw TGError(R->getLoc(), "Cannot use 'Void' as type to SDTCisVT"); 777 778 } else if (R->isSubClassOf("SDTCisPtrTy")) { 779 ConstraintType = SDTCisPtrTy; 780 } else if (R->isSubClassOf("SDTCisInt")) { 781 ConstraintType = SDTCisInt; 782 } else if (R->isSubClassOf("SDTCisFP")) { 783 ConstraintType = SDTCisFP; 784 } else if (R->isSubClassOf("SDTCisVec")) { 785 ConstraintType = SDTCisVec; 786 } else if (R->isSubClassOf("SDTCisSameAs")) { 787 ConstraintType = SDTCisSameAs; 788 x.SDTCisSameAs_Info.OtherOperandNum = R->getValueAsInt("OtherOperandNum"); 789 } else if (R->isSubClassOf("SDTCisVTSmallerThanOp")) { 790 ConstraintType = SDTCisVTSmallerThanOp; 791 x.SDTCisVTSmallerThanOp_Info.OtherOperandNum = 792 R->getValueAsInt("OtherOperandNum"); 793 } else if (R->isSubClassOf("SDTCisOpSmallerThanOp")) { 794 ConstraintType = SDTCisOpSmallerThanOp; 795 x.SDTCisOpSmallerThanOp_Info.BigOperandNum = 796 R->getValueAsInt("BigOperandNum"); 797 } else if (R->isSubClassOf("SDTCisEltOfVec")) { 798 ConstraintType = SDTCisEltOfVec; 799 x.SDTCisEltOfVec_Info.OtherOperandNum = R->getValueAsInt("OtherOpNum"); 800 } else if (R->isSubClassOf("SDTCisSubVecOfVec")) { 801 ConstraintType = SDTCisSubVecOfVec; 802 x.SDTCisSubVecOfVec_Info.OtherOperandNum = 803 R->getValueAsInt("OtherOpNum"); 804 } else { 805 errs() << "Unrecognized SDTypeConstraint '" << R->getName() << "'!\n"; 806 exit(1); 807 } 808 } 809 810 /// getOperandNum - Return the node corresponding to operand #OpNo in tree 811 /// N, and the result number in ResNo. 812 static TreePatternNode *getOperandNum(unsigned OpNo, TreePatternNode *N, 813 const SDNodeInfo &NodeInfo, 814 unsigned &ResNo) { 815 unsigned NumResults = NodeInfo.getNumResults(); 816 if (OpNo < NumResults) { 817 ResNo = OpNo; 818 return N; 819 } 820 821 OpNo -= NumResults; 822 823 if (OpNo >= N->getNumChildren()) { 824 errs() << "Invalid operand number in type constraint " 825 << (OpNo+NumResults) << " "; 826 N->dump(); 827 errs() << '\n'; 828 exit(1); 829 } 830 831 return N->getChild(OpNo); 832 } 833 834 /// ApplyTypeConstraint - Given a node in a pattern, apply this type 835 /// constraint to the nodes operands. This returns true if it makes a 836 /// change, false otherwise. If a type contradiction is found, throw an 837 /// exception. 838 bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, 839 const SDNodeInfo &NodeInfo, 840 TreePattern &TP) const { 841 unsigned ResNo = 0; // The result number being referenced. 842 TreePatternNode *NodeToApply = getOperandNum(OperandNo, N, NodeInfo, ResNo); 843 844 switch (ConstraintType) { 845 case SDTCisVT: 846 // Operand must be a particular type. 847 return NodeToApply->UpdateNodeType(ResNo, x.SDTCisVT_Info.VT, TP); 848 case SDTCisPtrTy: 849 // Operand must be same as target pointer type. 850 return NodeToApply->UpdateNodeType(ResNo, MVT::iPTR, TP); 851 case SDTCisInt: 852 // Require it to be one of the legal integer VTs. 853 return NodeToApply->getExtType(ResNo).EnforceInteger(TP); 854 case SDTCisFP: 855 // Require it to be one of the legal fp VTs. 856 return NodeToApply->getExtType(ResNo).EnforceFloatingPoint(TP); 857 case SDTCisVec: 858 // Require it to be one of the legal vector VTs. 859 return NodeToApply->getExtType(ResNo).EnforceVector(TP); 860 case SDTCisSameAs: { 861 unsigned OResNo = 0; 862 TreePatternNode *OtherNode = 863 getOperandNum(x.SDTCisSameAs_Info.OtherOperandNum, N, NodeInfo, OResNo); 864 return NodeToApply->UpdateNodeType(OResNo, OtherNode->getExtType(ResNo),TP)| 865 OtherNode->UpdateNodeType(ResNo,NodeToApply->getExtType(OResNo),TP); 866 } 867 case SDTCisVTSmallerThanOp: { 868 // The NodeToApply must be a leaf node that is a VT. OtherOperandNum must 869 // have an integer type that is smaller than the VT. 870 if (!NodeToApply->isLeaf() || 871 !dynamic_cast<DefInit*>(NodeToApply->getLeafValue()) || 872 !static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef() 873 ->isSubClassOf("ValueType")) 874 TP.error(N->getOperator()->getName() + " expects a VT operand!"); 875 MVT::SimpleValueType VT = 876 getValueType(static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef()); 877 878 EEVT::TypeSet TypeListTmp(VT, TP); 879 880 unsigned OResNo = 0; 881 TreePatternNode *OtherNode = 882 getOperandNum(x.SDTCisVTSmallerThanOp_Info.OtherOperandNum, N, NodeInfo, 883 OResNo); 884 885 return TypeListTmp.EnforceSmallerThan(OtherNode->getExtType(OResNo), TP); 886 } 887 case SDTCisOpSmallerThanOp: { 888 unsigned BResNo = 0; 889 TreePatternNode *BigOperand = 890 getOperandNum(x.SDTCisOpSmallerThanOp_Info.BigOperandNum, N, NodeInfo, 891 BResNo); 892 return NodeToApply->getExtType(ResNo). 893 EnforceSmallerThan(BigOperand->getExtType(BResNo), TP); 894 } 895 case SDTCisEltOfVec: { 896 unsigned VResNo = 0; 897 TreePatternNode *VecOperand = 898 getOperandNum(x.SDTCisEltOfVec_Info.OtherOperandNum, N, NodeInfo, 899 VResNo); 900 901 // Filter vector types out of VecOperand that don't have the right element 902 // type. 903 return VecOperand->getExtType(VResNo). 904 EnforceVectorEltTypeIs(NodeToApply->getExtType(ResNo), TP); 905 } 906 case SDTCisSubVecOfVec: { 907 unsigned VResNo = 0; 908 TreePatternNode *BigVecOperand = 909 getOperandNum(x.SDTCisSubVecOfVec_Info.OtherOperandNum, N, NodeInfo, 910 VResNo); 911 912 // Filter vector types out of BigVecOperand that don't have the 913 // right subvector type. 914 return BigVecOperand->getExtType(VResNo). 915 EnforceVectorSubVectorTypeIs(NodeToApply->getExtType(ResNo), TP); 916 } 917 } 918 llvm_unreachable("Invalid ConstraintType!"); 919 } 920 921 //===----------------------------------------------------------------------===// 922 // SDNodeInfo implementation 923 // 924 SDNodeInfo::SDNodeInfo(Record *R) : Def(R) { 925 EnumName = R->getValueAsString("Opcode"); 926 SDClassName = R->getValueAsString("SDClass"); 927 Record *TypeProfile = R->getValueAsDef("TypeProfile"); 928 NumResults = TypeProfile->getValueAsInt("NumResults"); 929 NumOperands = TypeProfile->getValueAsInt("NumOperands"); 930 931 // Parse the properties. 932 Properties = 0; 933 std::vector<Record*> PropList = R->getValueAsListOfDefs("Properties"); 934 for (unsigned i = 0, e = PropList.size(); i != e; ++i) { 935 if (PropList[i]->getName() == "SDNPCommutative") { 936 Properties |= 1 << SDNPCommutative; 937 } else if (PropList[i]->getName() == "SDNPAssociative") { 938 Properties |= 1 << SDNPAssociative; 939 } else if (PropList[i]->getName() == "SDNPHasChain") { 940 Properties |= 1 << SDNPHasChain; 941 } else if (PropList[i]->getName() == "SDNPOutGlue") { 942 Properties |= 1 << SDNPOutGlue; 943 } else if (PropList[i]->getName() == "SDNPInGlue") { 944 Properties |= 1 << SDNPInGlue; 945 } else if (PropList[i]->getName() == "SDNPOptInGlue") { 946 Properties |= 1 << SDNPOptInGlue; 947 } else if (PropList[i]->getName() == "SDNPMayStore") { 948 Properties |= 1 << SDNPMayStore; 949 } else if (PropList[i]->getName() == "SDNPMayLoad") { 950 Properties |= 1 << SDNPMayLoad; 951 } else if (PropList[i]->getName() == "SDNPSideEffect") { 952 Properties |= 1 << SDNPSideEffect; 953 } else if (PropList[i]->getName() == "SDNPMemOperand") { 954 Properties |= 1 << SDNPMemOperand; 955 } else if (PropList[i]->getName() == "SDNPVariadic") { 956 Properties |= 1 << SDNPVariadic; 957 } else { 958 errs() << "Unknown SD Node property '" << PropList[i]->getName() 959 << "' on node '" << R->getName() << "'!\n"; 960 exit(1); 961 } 962 } 963 964 965 // Parse the type constraints. 966 std::vector<Record*> ConstraintList = 967 TypeProfile->getValueAsListOfDefs("Constraints"); 968 TypeConstraints.assign(ConstraintList.begin(), ConstraintList.end()); 969 } 970 971 /// getKnownType - If the type constraints on this node imply a fixed type 972 /// (e.g. all stores return void, etc), then return it as an 973 /// MVT::SimpleValueType. Otherwise, return EEVT::Other. 974 MVT::SimpleValueType SDNodeInfo::getKnownType(unsigned ResNo) const { 975 unsigned NumResults = getNumResults(); 976 assert(NumResults <= 1 && 977 "We only work with nodes with zero or one result so far!"); 978 assert(ResNo == 0 && "Only handles single result nodes so far"); 979 980 for (unsigned i = 0, e = TypeConstraints.size(); i != e; ++i) { 981 // Make sure that this applies to the correct node result. 982 if (TypeConstraints[i].OperandNo >= NumResults) // FIXME: need value # 983 continue; 984 985 switch (TypeConstraints[i].ConstraintType) { 986 default: break; 987 case SDTypeConstraint::SDTCisVT: 988 return TypeConstraints[i].x.SDTCisVT_Info.VT; 989 case SDTypeConstraint::SDTCisPtrTy: 990 return MVT::iPTR; 991 } 992 } 993 return MVT::Other; 994 } 995 996 //===----------------------------------------------------------------------===// 997 // TreePatternNode implementation 998 // 999 1000 TreePatternNode::~TreePatternNode() { 1001 #if 0 // FIXME: implement refcounted tree nodes! 1002 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1003 delete getChild(i); 1004 #endif 1005 } 1006 1007 static unsigned GetNumNodeResults(Record *Operator, CodeGenDAGPatterns &CDP) { 1008 if (Operator->getName() == "set" || 1009 Operator->getName() == "implicit") 1010 return 0; // All return nothing. 1011 1012 if (Operator->isSubClassOf("Intrinsic")) 1013 return CDP.getIntrinsic(Operator).IS.RetVTs.size(); 1014 1015 if (Operator->isSubClassOf("SDNode")) 1016 return CDP.getSDNodeInfo(Operator).getNumResults(); 1017 1018 if (Operator->isSubClassOf("PatFrag")) { 1019 // If we've already parsed this pattern fragment, get it. Otherwise, handle 1020 // the forward reference case where one pattern fragment references another 1021 // before it is processed. 1022 if (TreePattern *PFRec = CDP.getPatternFragmentIfRead(Operator)) 1023 return PFRec->getOnlyTree()->getNumTypes(); 1024 1025 // Get the result tree. 1026 DagInit *Tree = Operator->getValueAsDag("Fragment"); 1027 Record *Op = 0; 1028 if (Tree && dynamic_cast<DefInit*>(Tree->getOperator())) 1029 Op = dynamic_cast<DefInit*>(Tree->getOperator())->getDef(); 1030 assert(Op && "Invalid Fragment"); 1031 return GetNumNodeResults(Op, CDP); 1032 } 1033 1034 if (Operator->isSubClassOf("Instruction")) { 1035 CodeGenInstruction &InstInfo = CDP.getTargetInfo().getInstruction(Operator); 1036 1037 // FIXME: Should allow access to all the results here. 1038 unsigned NumDefsToAdd = InstInfo.Operands.NumDefs ? 1 : 0; 1039 1040 // Add on one implicit def if it has a resolvable type. 1041 if (InstInfo.HasOneImplicitDefWithKnownVT(CDP.getTargetInfo()) !=MVT::Other) 1042 ++NumDefsToAdd; 1043 return NumDefsToAdd; 1044 } 1045 1046 if (Operator->isSubClassOf("SDNodeXForm")) 1047 return 1; // FIXME: Generalize SDNodeXForm 1048 1049 Operator->dump(); 1050 errs() << "Unhandled node in GetNumNodeResults\n"; 1051 exit(1); 1052 } 1053 1054 void TreePatternNode::print(raw_ostream &OS) const { 1055 if (isLeaf()) 1056 OS << *getLeafValue(); 1057 else 1058 OS << '(' << getOperator()->getName(); 1059 1060 for (unsigned i = 0, e = Types.size(); i != e; ++i) 1061 OS << ':' << getExtType(i).getName(); 1062 1063 if (!isLeaf()) { 1064 if (getNumChildren() != 0) { 1065 OS << " "; 1066 getChild(0)->print(OS); 1067 for (unsigned i = 1, e = getNumChildren(); i != e; ++i) { 1068 OS << ", "; 1069 getChild(i)->print(OS); 1070 } 1071 } 1072 OS << ")"; 1073 } 1074 1075 for (unsigned i = 0, e = PredicateFns.size(); i != e; ++i) 1076 OS << "<<P:" << PredicateFns[i].getFnName() << ">>"; 1077 if (TransformFn) 1078 OS << "<<X:" << TransformFn->getName() << ">>"; 1079 if (!getName().empty()) 1080 OS << ":$" << getName(); 1081 1082 } 1083 void TreePatternNode::dump() const { 1084 print(errs()); 1085 } 1086 1087 /// isIsomorphicTo - Return true if this node is recursively 1088 /// isomorphic to the specified node. For this comparison, the node's 1089 /// entire state is considered. The assigned name is ignored, since 1090 /// nodes with differing names are considered isomorphic. However, if 1091 /// the assigned name is present in the dependent variable set, then 1092 /// the assigned name is considered significant and the node is 1093 /// isomorphic if the names match. 1094 bool TreePatternNode::isIsomorphicTo(const TreePatternNode *N, 1095 const MultipleUseVarSet &DepVars) const { 1096 if (N == this) return true; 1097 if (N->isLeaf() != isLeaf() || getExtTypes() != N->getExtTypes() || 1098 getPredicateFns() != N->getPredicateFns() || 1099 getTransformFn() != N->getTransformFn()) 1100 return false; 1101 1102 if (isLeaf()) { 1103 if (DefInit *DI = dynamic_cast<DefInit*>(getLeafValue())) { 1104 if (DefInit *NDI = dynamic_cast<DefInit*>(N->getLeafValue())) { 1105 return ((DI->getDef() == NDI->getDef()) 1106 && (DepVars.find(getName()) == DepVars.end() 1107 || getName() == N->getName())); 1108 } 1109 } 1110 return getLeafValue() == N->getLeafValue(); 1111 } 1112 1113 if (N->getOperator() != getOperator() || 1114 N->getNumChildren() != getNumChildren()) return false; 1115 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1116 if (!getChild(i)->isIsomorphicTo(N->getChild(i), DepVars)) 1117 return false; 1118 return true; 1119 } 1120 1121 /// clone - Make a copy of this tree and all of its children. 1122 /// 1123 TreePatternNode *TreePatternNode::clone() const { 1124 TreePatternNode *New; 1125 if (isLeaf()) { 1126 New = new TreePatternNode(getLeafValue(), getNumTypes()); 1127 } else { 1128 std::vector<TreePatternNode*> CChildren; 1129 CChildren.reserve(Children.size()); 1130 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1131 CChildren.push_back(getChild(i)->clone()); 1132 New = new TreePatternNode(getOperator(), CChildren, getNumTypes()); 1133 } 1134 New->setName(getName()); 1135 New->Types = Types; 1136 New->setPredicateFns(getPredicateFns()); 1137 New->setTransformFn(getTransformFn()); 1138 return New; 1139 } 1140 1141 /// RemoveAllTypes - Recursively strip all the types of this tree. 1142 void TreePatternNode::RemoveAllTypes() { 1143 for (unsigned i = 0, e = Types.size(); i != e; ++i) 1144 Types[i] = EEVT::TypeSet(); // Reset to unknown type. 1145 if (isLeaf()) return; 1146 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1147 getChild(i)->RemoveAllTypes(); 1148 } 1149 1150 1151 /// SubstituteFormalArguments - Replace the formal arguments in this tree 1152 /// with actual values specified by ArgMap. 1153 void TreePatternNode:: 1154 SubstituteFormalArguments(std::map<std::string, TreePatternNode*> &ArgMap) { 1155 if (isLeaf()) return; 1156 1157 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { 1158 TreePatternNode *Child = getChild(i); 1159 if (Child->isLeaf()) { 1160 Init *Val = Child->getLeafValue(); 1161 if (dynamic_cast<DefInit*>(Val) && 1162 static_cast<DefInit*>(Val)->getDef()->getName() == "node") { 1163 // We found a use of a formal argument, replace it with its value. 1164 TreePatternNode *NewChild = ArgMap[Child->getName()]; 1165 assert(NewChild && "Couldn't find formal argument!"); 1166 assert((Child->getPredicateFns().empty() || 1167 NewChild->getPredicateFns() == Child->getPredicateFns()) && 1168 "Non-empty child predicate clobbered!"); 1169 setChild(i, NewChild); 1170 } 1171 } else { 1172 getChild(i)->SubstituteFormalArguments(ArgMap); 1173 } 1174 } 1175 } 1176 1177 1178 /// InlinePatternFragments - If this pattern refers to any pattern 1179 /// fragments, inline them into place, giving us a pattern without any 1180 /// PatFrag references. 1181 TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) { 1182 if (isLeaf()) return this; // nothing to do. 1183 Record *Op = getOperator(); 1184 1185 if (!Op->isSubClassOf("PatFrag")) { 1186 // Just recursively inline children nodes. 1187 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { 1188 TreePatternNode *Child = getChild(i); 1189 TreePatternNode *NewChild = Child->InlinePatternFragments(TP); 1190 1191 assert((Child->getPredicateFns().empty() || 1192 NewChild->getPredicateFns() == Child->getPredicateFns()) && 1193 "Non-empty child predicate clobbered!"); 1194 1195 setChild(i, NewChild); 1196 } 1197 return this; 1198 } 1199 1200 // Otherwise, we found a reference to a fragment. First, look up its 1201 // TreePattern record. 1202 TreePattern *Frag = TP.getDAGPatterns().getPatternFragment(Op); 1203 1204 // Verify that we are passing the right number of operands. 1205 if (Frag->getNumArgs() != Children.size()) 1206 TP.error("'" + Op->getName() + "' fragment requires " + 1207 utostr(Frag->getNumArgs()) + " operands!"); 1208 1209 TreePatternNode *FragTree = Frag->getOnlyTree()->clone(); 1210 1211 TreePredicateFn PredFn(Frag); 1212 if (!PredFn.isAlwaysTrue()) 1213 FragTree->addPredicateFn(PredFn); 1214 1215 // Resolve formal arguments to their actual value. 1216 if (Frag->getNumArgs()) { 1217 // Compute the map of formal to actual arguments. 1218 std::map<std::string, TreePatternNode*> ArgMap; 1219 for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i) 1220 ArgMap[Frag->getArgName(i)] = getChild(i)->InlinePatternFragments(TP); 1221 1222 FragTree->SubstituteFormalArguments(ArgMap); 1223 } 1224 1225 FragTree->setName(getName()); 1226 for (unsigned i = 0, e = Types.size(); i != e; ++i) 1227 FragTree->UpdateNodeType(i, getExtType(i), TP); 1228 1229 // Transfer in the old predicates. 1230 for (unsigned i = 0, e = getPredicateFns().size(); i != e; ++i) 1231 FragTree->addPredicateFn(getPredicateFns()[i]); 1232 1233 // Get a new copy of this fragment to stitch into here. 1234 //delete this; // FIXME: implement refcounting! 1235 1236 // The fragment we inlined could have recursive inlining that is needed. See 1237 // if there are any pattern fragments in it and inline them as needed. 1238 return FragTree->InlinePatternFragments(TP); 1239 } 1240 1241 /// getImplicitType - Check to see if the specified record has an implicit 1242 /// type which should be applied to it. This will infer the type of register 1243 /// references from the register file information, for example. 1244 /// 1245 static EEVT::TypeSet getImplicitType(Record *R, unsigned ResNo, 1246 bool NotRegisters, TreePattern &TP) { 1247 // Check to see if this is a register operand. 1248 if (R->isSubClassOf("RegisterOperand")) { 1249 assert(ResNo == 0 && "Regoperand ref only has one result!"); 1250 if (NotRegisters) 1251 return EEVT::TypeSet(); // Unknown. 1252 Record *RegClass = R->getValueAsDef("RegClass"); 1253 const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo(); 1254 return EEVT::TypeSet(T.getRegisterClass(RegClass).getValueTypes()); 1255 } 1256 1257 // Check to see if this is a register or a register class. 1258 if (R->isSubClassOf("RegisterClass")) { 1259 assert(ResNo == 0 && "Regclass ref only has one result!"); 1260 if (NotRegisters) 1261 return EEVT::TypeSet(); // Unknown. 1262 const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo(); 1263 return EEVT::TypeSet(T.getRegisterClass(R).getValueTypes()); 1264 } 1265 1266 if (R->isSubClassOf("PatFrag")) { 1267 assert(ResNo == 0 && "FIXME: PatFrag with multiple results?"); 1268 // Pattern fragment types will be resolved when they are inlined. 1269 return EEVT::TypeSet(); // Unknown. 1270 } 1271 1272 if (R->isSubClassOf("Register")) { 1273 assert(ResNo == 0 && "Registers only produce one result!"); 1274 if (NotRegisters) 1275 return EEVT::TypeSet(); // Unknown. 1276 const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo(); 1277 return EEVT::TypeSet(T.getRegisterVTs(R)); 1278 } 1279 1280 if (R->isSubClassOf("SubRegIndex")) { 1281 assert(ResNo == 0 && "SubRegisterIndices only produce one result!"); 1282 return EEVT::TypeSet(); 1283 } 1284 1285 if (R->isSubClassOf("ValueType") || R->isSubClassOf("CondCode")) { 1286 assert(ResNo == 0 && "This node only has one result!"); 1287 // Using a VTSDNode or CondCodeSDNode. 1288 return EEVT::TypeSet(MVT::Other, TP); 1289 } 1290 1291 if (R->isSubClassOf("ComplexPattern")) { 1292 assert(ResNo == 0 && "FIXME: ComplexPattern with multiple results?"); 1293 if (NotRegisters) 1294 return EEVT::TypeSet(); // Unknown. 1295 return EEVT::TypeSet(TP.getDAGPatterns().getComplexPattern(R).getValueType(), 1296 TP); 1297 } 1298 if (R->isSubClassOf("PointerLikeRegClass")) { 1299 assert(ResNo == 0 && "Regclass can only have one result!"); 1300 return EEVT::TypeSet(MVT::iPTR, TP); 1301 } 1302 1303 if (R->getName() == "node" || R->getName() == "srcvalue" || 1304 R->getName() == "zero_reg") { 1305 // Placeholder. 1306 return EEVT::TypeSet(); // Unknown. 1307 } 1308 1309 TP.error("Unknown node flavor used in pattern: " + R->getName()); 1310 return EEVT::TypeSet(MVT::Other, TP); 1311 } 1312 1313 1314 /// getIntrinsicInfo - If this node corresponds to an intrinsic, return the 1315 /// CodeGenIntrinsic information for it, otherwise return a null pointer. 1316 const CodeGenIntrinsic *TreePatternNode:: 1317 getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const { 1318 if (getOperator() != CDP.get_intrinsic_void_sdnode() && 1319 getOperator() != CDP.get_intrinsic_w_chain_sdnode() && 1320 getOperator() != CDP.get_intrinsic_wo_chain_sdnode()) 1321 return 0; 1322 1323 unsigned IID = 1324 dynamic_cast<IntInit*>(getChild(0)->getLeafValue())->getValue(); 1325 return &CDP.getIntrinsicInfo(IID); 1326 } 1327 1328 /// getComplexPatternInfo - If this node corresponds to a ComplexPattern, 1329 /// return the ComplexPattern information, otherwise return null. 1330 const ComplexPattern * 1331 TreePatternNode::getComplexPatternInfo(const CodeGenDAGPatterns &CGP) const { 1332 if (!isLeaf()) return 0; 1333 1334 DefInit *DI = dynamic_cast<DefInit*>(getLeafValue()); 1335 if (DI && DI->getDef()->isSubClassOf("ComplexPattern")) 1336 return &CGP.getComplexPattern(DI->getDef()); 1337 return 0; 1338 } 1339 1340 /// NodeHasProperty - Return true if this node has the specified property. 1341 bool TreePatternNode::NodeHasProperty(SDNP Property, 1342 const CodeGenDAGPatterns &CGP) const { 1343 if (isLeaf()) { 1344 if (const ComplexPattern *CP = getComplexPatternInfo(CGP)) 1345 return CP->hasProperty(Property); 1346 return false; 1347 } 1348 1349 Record *Operator = getOperator(); 1350 if (!Operator->isSubClassOf("SDNode")) return false; 1351 1352 return CGP.getSDNodeInfo(Operator).hasProperty(Property); 1353 } 1354 1355 1356 1357 1358 /// TreeHasProperty - Return true if any node in this tree has the specified 1359 /// property. 1360 bool TreePatternNode::TreeHasProperty(SDNP Property, 1361 const CodeGenDAGPatterns &CGP) const { 1362 if (NodeHasProperty(Property, CGP)) 1363 return true; 1364 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1365 if (getChild(i)->TreeHasProperty(Property, CGP)) 1366 return true; 1367 return false; 1368 } 1369 1370 /// isCommutativeIntrinsic - Return true if the node corresponds to a 1371 /// commutative intrinsic. 1372 bool 1373 TreePatternNode::isCommutativeIntrinsic(const CodeGenDAGPatterns &CDP) const { 1374 if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) 1375 return Int->isCommutative; 1376 return false; 1377 } 1378 1379 1380 /// ApplyTypeConstraints - Apply all of the type constraints relevant to 1381 /// this node and its children in the tree. This returns true if it makes a 1382 /// change, false otherwise. If a type contradiction is found, throw an 1383 /// exception. 1384 bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { 1385 CodeGenDAGPatterns &CDP = TP.getDAGPatterns(); 1386 if (isLeaf()) { 1387 if (DefInit *DI = dynamic_cast<DefInit*>(getLeafValue())) { 1388 // If it's a regclass or something else known, include the type. 1389 bool MadeChange = false; 1390 for (unsigned i = 0, e = Types.size(); i != e; ++i) 1391 MadeChange |= UpdateNodeType(i, getImplicitType(DI->getDef(), i, 1392 NotRegisters, TP), TP); 1393 return MadeChange; 1394 } 1395 1396 if (IntInit *II = dynamic_cast<IntInit*>(getLeafValue())) { 1397 assert(Types.size() == 1 && "Invalid IntInit"); 1398 1399 // Int inits are always integers. :) 1400 bool MadeChange = Types[0].EnforceInteger(TP); 1401 1402 if (!Types[0].isConcrete()) 1403 return MadeChange; 1404 1405 MVT::SimpleValueType VT = getType(0); 1406 if (VT == MVT::iPTR || VT == MVT::iPTRAny) 1407 return MadeChange; 1408 1409 unsigned Size = EVT(VT).getSizeInBits(); 1410 // Make sure that the value is representable for this type. 1411 if (Size >= 32) return MadeChange; 1412 1413 int Val = (II->getValue() << (32-Size)) >> (32-Size); 1414 if (Val == II->getValue()) return MadeChange; 1415 1416 // If sign-extended doesn't fit, does it fit as unsigned? 1417 unsigned ValueMask; 1418 unsigned UnsignedVal; 1419 ValueMask = unsigned(~uint32_t(0UL) >> (32-Size)); 1420 UnsignedVal = unsigned(II->getValue()); 1421 1422 if ((ValueMask & UnsignedVal) == UnsignedVal) 1423 return MadeChange; 1424 1425 TP.error("Integer value '" + itostr(II->getValue())+ 1426 "' is out of range for type '" + getEnumName(getType(0)) + "'!"); 1427 return MadeChange; 1428 } 1429 return false; 1430 } 1431 1432 // special handling for set, which isn't really an SDNode. 1433 if (getOperator()->getName() == "set") { 1434 assert(getNumTypes() == 0 && "Set doesn't produce a value"); 1435 assert(getNumChildren() >= 2 && "Missing RHS of a set?"); 1436 unsigned NC = getNumChildren(); 1437 1438 TreePatternNode *SetVal = getChild(NC-1); 1439 bool MadeChange = SetVal->ApplyTypeConstraints(TP, NotRegisters); 1440 1441 for (unsigned i = 0; i < NC-1; ++i) { 1442 TreePatternNode *Child = getChild(i); 1443 MadeChange |= Child->ApplyTypeConstraints(TP, NotRegisters); 1444 1445 // Types of operands must match. 1446 MadeChange |= Child->UpdateNodeType(0, SetVal->getExtType(i), TP); 1447 MadeChange |= SetVal->UpdateNodeType(i, Child->getExtType(0), TP); 1448 } 1449 return MadeChange; 1450 } 1451 1452 if (getOperator()->getName() == "implicit") { 1453 assert(getNumTypes() == 0 && "Node doesn't produce a value"); 1454 1455 bool MadeChange = false; 1456 for (unsigned i = 0; i < getNumChildren(); ++i) 1457 MadeChange = getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 1458 return MadeChange; 1459 } 1460 1461 if (getOperator()->getName() == "COPY_TO_REGCLASS") { 1462 bool MadeChange = false; 1463 MadeChange |= getChild(0)->ApplyTypeConstraints(TP, NotRegisters); 1464 MadeChange |= getChild(1)->ApplyTypeConstraints(TP, NotRegisters); 1465 1466 assert(getChild(0)->getNumTypes() == 1 && 1467 getChild(1)->getNumTypes() == 1 && "Unhandled case"); 1468 1469 // child #1 of COPY_TO_REGCLASS should be a register class. We don't care 1470 // what type it gets, so if it didn't get a concrete type just give it the 1471 // first viable type from the reg class. 1472 if (!getChild(1)->hasTypeSet(0) && 1473 !getChild(1)->getExtType(0).isCompletelyUnknown()) { 1474 MVT::SimpleValueType RCVT = getChild(1)->getExtType(0).getTypeList()[0]; 1475 MadeChange |= getChild(1)->UpdateNodeType(0, RCVT, TP); 1476 } 1477 return MadeChange; 1478 } 1479 1480 if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) { 1481 bool MadeChange = false; 1482 1483 // Apply the result type to the node. 1484 unsigned NumRetVTs = Int->IS.RetVTs.size(); 1485 unsigned NumParamVTs = Int->IS.ParamVTs.size(); 1486 1487 for (unsigned i = 0, e = NumRetVTs; i != e; ++i) 1488 MadeChange |= UpdateNodeType(i, Int->IS.RetVTs[i], TP); 1489 1490 if (getNumChildren() != NumParamVTs + 1) 1491 TP.error("Intrinsic '" + Int->Name + "' expects " + 1492 utostr(NumParamVTs) + " operands, not " + 1493 utostr(getNumChildren() - 1) + " operands!"); 1494 1495 // Apply type info to the intrinsic ID. 1496 MadeChange |= getChild(0)->UpdateNodeType(0, MVT::iPTR, TP); 1497 1498 for (unsigned i = 0, e = getNumChildren()-1; i != e; ++i) { 1499 MadeChange |= getChild(i+1)->ApplyTypeConstraints(TP, NotRegisters); 1500 1501 MVT::SimpleValueType OpVT = Int->IS.ParamVTs[i]; 1502 assert(getChild(i+1)->getNumTypes() == 1 && "Unhandled case"); 1503 MadeChange |= getChild(i+1)->UpdateNodeType(0, OpVT, TP); 1504 } 1505 return MadeChange; 1506 } 1507 1508 if (getOperator()->isSubClassOf("SDNode")) { 1509 const SDNodeInfo &NI = CDP.getSDNodeInfo(getOperator()); 1510 1511 // Check that the number of operands is sane. Negative operands -> varargs. 1512 if (NI.getNumOperands() >= 0 && 1513 getNumChildren() != (unsigned)NI.getNumOperands()) 1514 TP.error(getOperator()->getName() + " node requires exactly " + 1515 itostr(NI.getNumOperands()) + " operands!"); 1516 1517 bool MadeChange = NI.ApplyTypeConstraints(this, TP); 1518 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1519 MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 1520 return MadeChange; 1521 } 1522 1523 if (getOperator()->isSubClassOf("Instruction")) { 1524 const DAGInstruction &Inst = CDP.getInstruction(getOperator()); 1525 CodeGenInstruction &InstInfo = 1526 CDP.getTargetInfo().getInstruction(getOperator()); 1527 1528 bool MadeChange = false; 1529 1530 // Apply the result types to the node, these come from the things in the 1531 // (outs) list of the instruction. 1532 // FIXME: Cap at one result so far. 1533 unsigned NumResultsToAdd = InstInfo.Operands.NumDefs ? 1 : 0; 1534 for (unsigned ResNo = 0; ResNo != NumResultsToAdd; ++ResNo) { 1535 Record *ResultNode = Inst.getResult(ResNo); 1536 1537 if (ResultNode->isSubClassOf("PointerLikeRegClass")) { 1538 MadeChange |= UpdateNodeType(ResNo, MVT::iPTR, TP); 1539 } else if (ResultNode->isSubClassOf("RegisterOperand")) { 1540 Record *RegClass = ResultNode->getValueAsDef("RegClass"); 1541 const CodeGenRegisterClass &RC = 1542 CDP.getTargetInfo().getRegisterClass(RegClass); 1543 MadeChange |= UpdateNodeType(ResNo, RC.getValueTypes(), TP); 1544 } else if (ResultNode->getName() == "unknown") { 1545 // Nothing to do. 1546 } else { 1547 assert(ResultNode->isSubClassOf("RegisterClass") && 1548 "Operands should be register classes!"); 1549 const CodeGenRegisterClass &RC = 1550 CDP.getTargetInfo().getRegisterClass(ResultNode); 1551 MadeChange |= UpdateNodeType(ResNo, RC.getValueTypes(), TP); 1552 } 1553 } 1554 1555 // If the instruction has implicit defs, we apply the first one as a result. 1556 // FIXME: This sucks, it should apply all implicit defs. 1557 if (!InstInfo.ImplicitDefs.empty()) { 1558 unsigned ResNo = NumResultsToAdd; 1559 1560 // FIXME: Generalize to multiple possible types and multiple possible 1561 // ImplicitDefs. 1562 MVT::SimpleValueType VT = 1563 InstInfo.HasOneImplicitDefWithKnownVT(CDP.getTargetInfo()); 1564 1565 if (VT != MVT::Other) 1566 MadeChange |= UpdateNodeType(ResNo, VT, TP); 1567 } 1568 1569 // If this is an INSERT_SUBREG, constrain the source and destination VTs to 1570 // be the same. 1571 if (getOperator()->getName() == "INSERT_SUBREG") { 1572 assert(getChild(0)->getNumTypes() == 1 && "FIXME: Unhandled"); 1573 MadeChange |= UpdateNodeType(0, getChild(0)->getExtType(0), TP); 1574 MadeChange |= getChild(0)->UpdateNodeType(0, getExtType(0), TP); 1575 } 1576 1577 unsigned ChildNo = 0; 1578 for (unsigned i = 0, e = Inst.getNumOperands(); i != e; ++i) { 1579 Record *OperandNode = Inst.getOperand(i); 1580 1581 // If the instruction expects a predicate or optional def operand, we 1582 // codegen this by setting the operand to it's default value if it has a 1583 // non-empty DefaultOps field. 1584 if ((OperandNode->isSubClassOf("PredicateOperand") || 1585 OperandNode->isSubClassOf("OptionalDefOperand")) && 1586 !CDP.getDefaultOperand(OperandNode).DefaultOps.empty()) 1587 continue; 1588 1589 // Verify that we didn't run out of provided operands. 1590 if (ChildNo >= getNumChildren()) 1591 TP.error("Instruction '" + getOperator()->getName() + 1592 "' expects more operands than were provided."); 1593 1594 MVT::SimpleValueType VT; 1595 TreePatternNode *Child = getChild(ChildNo++); 1596 unsigned ChildResNo = 0; // Instructions always use res #0 of their op. 1597 1598 if (OperandNode->isSubClassOf("RegisterClass")) { 1599 const CodeGenRegisterClass &RC = 1600 CDP.getTargetInfo().getRegisterClass(OperandNode); 1601 MadeChange |= Child->UpdateNodeType(ChildResNo, RC.getValueTypes(), TP); 1602 } else if (OperandNode->isSubClassOf("RegisterOperand")) { 1603 Record *RegClass = OperandNode->getValueAsDef("RegClass"); 1604 const CodeGenRegisterClass &RC = 1605 CDP.getTargetInfo().getRegisterClass(RegClass); 1606 MadeChange |= Child->UpdateNodeType(ChildResNo, RC.getValueTypes(), TP); 1607 } else if (OperandNode->isSubClassOf("Operand")) { 1608 VT = getValueType(OperandNode->getValueAsDef("Type")); 1609 MadeChange |= Child->UpdateNodeType(ChildResNo, VT, TP); 1610 } else if (OperandNode->isSubClassOf("PointerLikeRegClass")) { 1611 MadeChange |= Child->UpdateNodeType(ChildResNo, MVT::iPTR, TP); 1612 } else if (OperandNode->getName() == "unknown") { 1613 // Nothing to do. 1614 } else 1615 llvm_unreachable("Unknown operand type!"); 1616 1617 MadeChange |= Child->ApplyTypeConstraints(TP, NotRegisters); 1618 } 1619 1620 if (ChildNo != getNumChildren()) 1621 TP.error("Instruction '" + getOperator()->getName() + 1622 "' was provided too many operands!"); 1623 1624 return MadeChange; 1625 } 1626 1627 assert(getOperator()->isSubClassOf("SDNodeXForm") && "Unknown node type!"); 1628 1629 // Node transforms always take one operand. 1630 if (getNumChildren() != 1) 1631 TP.error("Node transform '" + getOperator()->getName() + 1632 "' requires one operand!"); 1633 1634 bool MadeChange = getChild(0)->ApplyTypeConstraints(TP, NotRegisters); 1635 1636 1637 // If either the output or input of the xform does not have exact 1638 // type info. We assume they must be the same. Otherwise, it is perfectly 1639 // legal to transform from one type to a completely different type. 1640 #if 0 1641 if (!hasTypeSet() || !getChild(0)->hasTypeSet()) { 1642 bool MadeChange = UpdateNodeType(getChild(0)->getExtType(), TP); 1643 MadeChange |= getChild(0)->UpdateNodeType(getExtType(), TP); 1644 return MadeChange; 1645 } 1646 #endif 1647 return MadeChange; 1648 } 1649 1650 /// OnlyOnRHSOfCommutative - Return true if this value is only allowed on the 1651 /// RHS of a commutative operation, not the on LHS. 1652 static bool OnlyOnRHSOfCommutative(TreePatternNode *N) { 1653 if (!N->isLeaf() && N->getOperator()->getName() == "imm") 1654 return true; 1655 if (N->isLeaf() && dynamic_cast<IntInit*>(N->getLeafValue())) 1656 return true; 1657 return false; 1658 } 1659 1660 1661 /// canPatternMatch - If it is impossible for this pattern to match on this 1662 /// target, fill in Reason and return false. Otherwise, return true. This is 1663 /// used as a sanity check for .td files (to prevent people from writing stuff 1664 /// that can never possibly work), and to prevent the pattern permuter from 1665 /// generating stuff that is useless. 1666 bool TreePatternNode::canPatternMatch(std::string &Reason, 1667 const CodeGenDAGPatterns &CDP) { 1668 if (isLeaf()) return true; 1669 1670 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1671 if (!getChild(i)->canPatternMatch(Reason, CDP)) 1672 return false; 1673 1674 // If this is an intrinsic, handle cases that would make it not match. For 1675 // example, if an operand is required to be an immediate. 1676 if (getOperator()->isSubClassOf("Intrinsic")) { 1677 // TODO: 1678 return true; 1679 } 1680 1681 // If this node is a commutative operator, check that the LHS isn't an 1682 // immediate. 1683 const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(getOperator()); 1684 bool isCommIntrinsic = isCommutativeIntrinsic(CDP); 1685 if (NodeInfo.hasProperty(SDNPCommutative) || isCommIntrinsic) { 1686 // Scan all of the operands of the node and make sure that only the last one 1687 // is a constant node, unless the RHS also is. 1688 if (!OnlyOnRHSOfCommutative(getChild(getNumChildren()-1))) { 1689 bool Skip = isCommIntrinsic ? 1 : 0; // First operand is intrinsic id. 1690 for (unsigned i = Skip, e = getNumChildren()-1; i != e; ++i) 1691 if (OnlyOnRHSOfCommutative(getChild(i))) { 1692 Reason="Immediate value must be on the RHS of commutative operators!"; 1693 return false; 1694 } 1695 } 1696 } 1697 1698 return true; 1699 } 1700 1701 //===----------------------------------------------------------------------===// 1702 // TreePattern implementation 1703 // 1704 1705 TreePattern::TreePattern(Record *TheRec, ListInit *RawPat, bool isInput, 1706 CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp){ 1707 isInputPattern = isInput; 1708 for (unsigned i = 0, e = RawPat->getSize(); i != e; ++i) 1709 Trees.push_back(ParseTreePattern(RawPat->getElement(i), "")); 1710 } 1711 1712 TreePattern::TreePattern(Record *TheRec, DagInit *Pat, bool isInput, 1713 CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp){ 1714 isInputPattern = isInput; 1715 Trees.push_back(ParseTreePattern(Pat, "")); 1716 } 1717 1718 TreePattern::TreePattern(Record *TheRec, TreePatternNode *Pat, bool isInput, 1719 CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp){ 1720 isInputPattern = isInput; 1721 Trees.push_back(Pat); 1722 } 1723 1724 void TreePattern::error(const std::string &Msg) const { 1725 dump(); 1726 throw TGError(TheRecord->getLoc(), "In " + TheRecord->getName() + ": " + Msg); 1727 } 1728 1729 void TreePattern::ComputeNamedNodes() { 1730 for (unsigned i = 0, e = Trees.size(); i != e; ++i) 1731 ComputeNamedNodes(Trees[i]); 1732 } 1733 1734 void TreePattern::ComputeNamedNodes(TreePatternNode *N) { 1735 if (!N->getName().empty()) 1736 NamedNodes[N->getName()].push_back(N); 1737 1738 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 1739 ComputeNamedNodes(N->getChild(i)); 1740 } 1741 1742 1743 TreePatternNode *TreePattern::ParseTreePattern(Init *TheInit, StringRef OpName){ 1744 if (DefInit *DI = dynamic_cast<DefInit*>(TheInit)) { 1745 Record *R = DI->getDef(); 1746 1747 // Direct reference to a leaf DagNode or PatFrag? Turn it into a 1748 // TreePatternNode of its own. For example: 1749 /// (foo GPR, imm) -> (foo GPR, (imm)) 1750 if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag")) 1751 return ParseTreePattern( 1752 DagInit::get(DI, "", 1753 std::vector<std::pair<Init*, std::string> >()), 1754 OpName); 1755 1756 // Input argument? 1757 TreePatternNode *Res = new TreePatternNode(DI, 1); 1758 if (R->getName() == "node" && !OpName.empty()) { 1759 if (OpName.empty()) 1760 error("'node' argument requires a name to match with operand list"); 1761 Args.push_back(OpName); 1762 } 1763 1764 Res->setName(OpName); 1765 return Res; 1766 } 1767 1768 if (IntInit *II = dynamic_cast<IntInit*>(TheInit)) { 1769 if (!OpName.empty()) 1770 error("Constant int argument should not have a name!"); 1771 return new TreePatternNode(II, 1); 1772 } 1773 1774 if (BitsInit *BI = dynamic_cast<BitsInit*>(TheInit)) { 1775 // Turn this into an IntInit. 1776 Init *II = BI->convertInitializerTo(IntRecTy::get()); 1777 if (II == 0 || !dynamic_cast<IntInit*>(II)) 1778 error("Bits value must be constants!"); 1779 return ParseTreePattern(II, OpName); 1780 } 1781 1782 DagInit *Dag = dynamic_cast<DagInit*>(TheInit); 1783 if (!Dag) { 1784 TheInit->dump(); 1785 error("Pattern has unexpected init kind!"); 1786 } 1787 DefInit *OpDef = dynamic_cast<DefInit*>(Dag->getOperator()); 1788 if (!OpDef) error("Pattern has unexpected operator type!"); 1789 Record *Operator = OpDef->getDef(); 1790 1791 if (Operator->isSubClassOf("ValueType")) { 1792 // If the operator is a ValueType, then this must be "type cast" of a leaf 1793 // node. 1794 if (Dag->getNumArgs() != 1) 1795 error("Type cast only takes one operand!"); 1796 1797 TreePatternNode *New = ParseTreePattern(Dag->getArg(0), Dag->getArgName(0)); 1798 1799 // Apply the type cast. 1800 assert(New->getNumTypes() == 1 && "FIXME: Unhandled"); 1801 New->UpdateNodeType(0, getValueType(Operator), *this); 1802 1803 if (!OpName.empty()) 1804 error("ValueType cast should not have a name!"); 1805 return New; 1806 } 1807 1808 // Verify that this is something that makes sense for an operator. 1809 if (!Operator->isSubClassOf("PatFrag") && 1810 !Operator->isSubClassOf("SDNode") && 1811 !Operator->isSubClassOf("Instruction") && 1812 !Operator->isSubClassOf("SDNodeXForm") && 1813 !Operator->isSubClassOf("Intrinsic") && 1814 Operator->getName() != "set" && 1815 Operator->getName() != "implicit") 1816 error("Unrecognized node '" + Operator->getName() + "'!"); 1817 1818 // Check to see if this is something that is illegal in an input pattern. 1819 if (isInputPattern) { 1820 if (Operator->isSubClassOf("Instruction") || 1821 Operator->isSubClassOf("SDNodeXForm")) 1822 error("Cannot use '" + Operator->getName() + "' in an input pattern!"); 1823 } else { 1824 if (Operator->isSubClassOf("Intrinsic")) 1825 error("Cannot use '" + Operator->getName() + "' in an output pattern!"); 1826 1827 if (Operator->isSubClassOf("SDNode") && 1828 Operator->getName() != "imm" && 1829 Operator->getName() != "fpimm" && 1830 Operator->getName() != "tglobaltlsaddr" && 1831 Operator->getName() != "tconstpool" && 1832 Operator->getName() != "tjumptable" && 1833 Operator->getName() != "tframeindex" && 1834 Operator->getName() != "texternalsym" && 1835 Operator->getName() != "tblockaddress" && 1836 Operator->getName() != "tglobaladdr" && 1837 Operator->getName() != "bb" && 1838 Operator->getName() != "vt") 1839 error("Cannot use '" + Operator->getName() + "' in an output pattern!"); 1840 } 1841 1842 std::vector<TreePatternNode*> Children; 1843 1844 // Parse all the operands. 1845 for (unsigned i = 0, e = Dag->getNumArgs(); i != e; ++i) 1846 Children.push_back(ParseTreePattern(Dag->getArg(i), Dag->getArgName(i))); 1847 1848 // If the operator is an intrinsic, then this is just syntactic sugar for for 1849 // (intrinsic_* <number>, ..children..). Pick the right intrinsic node, and 1850 // convert the intrinsic name to a number. 1851 if (Operator->isSubClassOf("Intrinsic")) { 1852 const CodeGenIntrinsic &Int = getDAGPatterns().getIntrinsic(Operator); 1853 unsigned IID = getDAGPatterns().getIntrinsicID(Operator)+1; 1854 1855 // If this intrinsic returns void, it must have side-effects and thus a 1856 // chain. 1857 if (Int.IS.RetVTs.empty()) 1858 Operator = getDAGPatterns().get_intrinsic_void_sdnode(); 1859 else if (Int.ModRef != CodeGenIntrinsic::NoMem) 1860 // Has side-effects, requires chain. 1861 Operator = getDAGPatterns().get_intrinsic_w_chain_sdnode(); 1862 else // Otherwise, no chain. 1863 Operator = getDAGPatterns().get_intrinsic_wo_chain_sdnode(); 1864 1865 TreePatternNode *IIDNode = new TreePatternNode(IntInit::get(IID), 1); 1866 Children.insert(Children.begin(), IIDNode); 1867 } 1868 1869 unsigned NumResults = GetNumNodeResults(Operator, CDP); 1870 TreePatternNode *Result = new TreePatternNode(Operator, Children, NumResults); 1871 Result->setName(OpName); 1872 1873 if (!Dag->getName().empty()) { 1874 assert(Result->getName().empty()); 1875 Result->setName(Dag->getName()); 1876 } 1877 return Result; 1878 } 1879 1880 /// SimplifyTree - See if we can simplify this tree to eliminate something that 1881 /// will never match in favor of something obvious that will. This is here 1882 /// strictly as a convenience to target authors because it allows them to write 1883 /// more type generic things and have useless type casts fold away. 1884 /// 1885 /// This returns true if any change is made. 1886 static bool SimplifyTree(TreePatternNode *&N) { 1887 if (N->isLeaf()) 1888 return false; 1889 1890 // If we have a bitconvert with a resolved type and if the source and 1891 // destination types are the same, then the bitconvert is useless, remove it. 1892 if (N->getOperator()->getName() == "bitconvert" && 1893 N->getExtType(0).isConcrete() && 1894 N->getExtType(0) == N->getChild(0)->getExtType(0) && 1895 N->getName().empty()) { 1896 N = N->getChild(0); 1897 SimplifyTree(N); 1898 return true; 1899 } 1900 1901 // Walk all children. 1902 bool MadeChange = false; 1903 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { 1904 TreePatternNode *Child = N->getChild(i); 1905 MadeChange |= SimplifyTree(Child); 1906 N->setChild(i, Child); 1907 } 1908 return MadeChange; 1909 } 1910 1911 1912 1913 /// InferAllTypes - Infer/propagate as many types throughout the expression 1914 /// patterns as possible. Return true if all types are inferred, false 1915 /// otherwise. Throw an exception if a type contradiction is found. 1916 bool TreePattern:: 1917 InferAllTypes(const StringMap<SmallVector<TreePatternNode*,1> > *InNamedTypes) { 1918 if (NamedNodes.empty()) 1919 ComputeNamedNodes(); 1920 1921 bool MadeChange = true; 1922 while (MadeChange) { 1923 MadeChange = false; 1924 for (unsigned i = 0, e = Trees.size(); i != e; ++i) { 1925 MadeChange |= Trees[i]->ApplyTypeConstraints(*this, false); 1926 MadeChange |= SimplifyTree(Trees[i]); 1927 } 1928 1929 // If there are constraints on our named nodes, apply them. 1930 for (StringMap<SmallVector<TreePatternNode*,1> >::iterator 1931 I = NamedNodes.begin(), E = NamedNodes.end(); I != E; ++I) { 1932 SmallVectorImpl<TreePatternNode*> &Nodes = I->second; 1933 1934 // If we have input named node types, propagate their types to the named 1935 // values here. 1936 if (InNamedTypes) { 1937 // FIXME: Should be error? 1938 assert(InNamedTypes->count(I->getKey()) && 1939 "Named node in output pattern but not input pattern?"); 1940 1941 const SmallVectorImpl<TreePatternNode*> &InNodes = 1942 InNamedTypes->find(I->getKey())->second; 1943 1944 // The input types should be fully resolved by now. 1945 for (unsigned i = 0, e = Nodes.size(); i != e; ++i) { 1946 // If this node is a register class, and it is the root of the pattern 1947 // then we're mapping something onto an input register. We allow 1948 // changing the type of the input register in this case. This allows 1949 // us to match things like: 1950 // def : Pat<(v1i64 (bitconvert(v2i32 DPR:$src))), (v1i64 DPR:$src)>; 1951 if (Nodes[i] == Trees[0] && Nodes[i]->isLeaf()) { 1952 DefInit *DI = dynamic_cast<DefInit*>(Nodes[i]->getLeafValue()); 1953 if (DI && (DI->getDef()->isSubClassOf("RegisterClass") || 1954 DI->getDef()->isSubClassOf("RegisterOperand"))) 1955 continue; 1956 } 1957 1958 assert(Nodes[i]->getNumTypes() == 1 && 1959 InNodes[0]->getNumTypes() == 1 && 1960 "FIXME: cannot name multiple result nodes yet"); 1961 MadeChange |= Nodes[i]->UpdateNodeType(0, InNodes[0]->getExtType(0), 1962 *this); 1963 } 1964 } 1965 1966 // If there are multiple nodes with the same name, they must all have the 1967 // same type. 1968 if (I->second.size() > 1) { 1969 for (unsigned i = 0, e = Nodes.size()-1; i != e; ++i) { 1970 TreePatternNode *N1 = Nodes[i], *N2 = Nodes[i+1]; 1971 assert(N1->getNumTypes() == 1 && N2->getNumTypes() == 1 && 1972 "FIXME: cannot name multiple result nodes yet"); 1973 1974 MadeChange |= N1->UpdateNodeType(0, N2->getExtType(0), *this); 1975 MadeChange |= N2->UpdateNodeType(0, N1->getExtType(0), *this); 1976 } 1977 } 1978 } 1979 } 1980 1981 bool HasUnresolvedTypes = false; 1982 for (unsigned i = 0, e = Trees.size(); i != e; ++i) 1983 HasUnresolvedTypes |= Trees[i]->ContainsUnresolvedType(); 1984 return !HasUnresolvedTypes; 1985 } 1986 1987 void TreePattern::print(raw_ostream &OS) const { 1988 OS << getRecord()->getName(); 1989 if (!Args.empty()) { 1990 OS << "(" << Args[0]; 1991 for (unsigned i = 1, e = Args.size(); i != e; ++i) 1992 OS << ", " << Args[i]; 1993 OS << ")"; 1994 } 1995 OS << ": "; 1996 1997 if (Trees.size() > 1) 1998 OS << "[\n"; 1999 for (unsigned i = 0, e = Trees.size(); i != e; ++i) { 2000 OS << "\t"; 2001 Trees[i]->print(OS); 2002 OS << "\n"; 2003 } 2004 2005 if (Trees.size() > 1) 2006 OS << "]\n"; 2007 } 2008 2009 void TreePattern::dump() const { print(errs()); } 2010 2011 //===----------------------------------------------------------------------===// 2012 // CodeGenDAGPatterns implementation 2013 // 2014 2015 CodeGenDAGPatterns::CodeGenDAGPatterns(RecordKeeper &R) : 2016 Records(R), Target(R) { 2017 2018 Intrinsics = LoadIntrinsics(Records, false); 2019 TgtIntrinsics = LoadIntrinsics(Records, true); 2020 ParseNodeInfo(); 2021 ParseNodeTransforms(); 2022 ParseComplexPatterns(); 2023 ParsePatternFragments(); 2024 ParseDefaultOperands(); 2025 ParseInstructions(); 2026 ParsePatterns(); 2027 2028 // Generate variants. For example, commutative patterns can match 2029 // multiple ways. Add them to PatternsToMatch as well. 2030 GenerateVariants(); 2031 2032 // Infer instruction flags. For example, we can detect loads, 2033 // stores, and side effects in many cases by examining an 2034 // instruction's pattern. 2035 InferInstructionFlags(); 2036 } 2037 2038 CodeGenDAGPatterns::~CodeGenDAGPatterns() { 2039 for (pf_iterator I = PatternFragments.begin(), 2040 E = PatternFragments.end(); I != E; ++I) 2041 delete I->second; 2042 } 2043 2044 2045 Record *CodeGenDAGPatterns::getSDNodeNamed(const std::string &Name) const { 2046 Record *N = Records.getDef(Name); 2047 if (!N || !N->isSubClassOf("SDNode")) { 2048 errs() << "Error getting SDNode '" << Name << "'!\n"; 2049 exit(1); 2050 } 2051 return N; 2052 } 2053 2054 // Parse all of the SDNode definitions for the target, populating SDNodes. 2055 void CodeGenDAGPatterns::ParseNodeInfo() { 2056 std::vector<Record*> Nodes = Records.getAllDerivedDefinitions("SDNode"); 2057 while (!Nodes.empty()) { 2058 SDNodes.insert(std::make_pair(Nodes.back(), Nodes.back())); 2059 Nodes.pop_back(); 2060 } 2061 2062 // Get the builtin intrinsic nodes. 2063 intrinsic_void_sdnode = getSDNodeNamed("intrinsic_void"); 2064 intrinsic_w_chain_sdnode = getSDNodeNamed("intrinsic_w_chain"); 2065 intrinsic_wo_chain_sdnode = getSDNodeNamed("intrinsic_wo_chain"); 2066 } 2067 2068 /// ParseNodeTransforms - Parse all SDNodeXForm instances into the SDNodeXForms 2069 /// map, and emit them to the file as functions. 2070 void CodeGenDAGPatterns::ParseNodeTransforms() { 2071 std::vector<Record*> Xforms = Records.getAllDerivedDefinitions("SDNodeXForm"); 2072 while (!Xforms.empty()) { 2073 Record *XFormNode = Xforms.back(); 2074 Record *SDNode = XFormNode->getValueAsDef("Opcode"); 2075 std::string Code = XFormNode->getValueAsString("XFormFunction"); 2076 SDNodeXForms.insert(std::make_pair(XFormNode, NodeXForm(SDNode, Code))); 2077 2078 Xforms.pop_back(); 2079 } 2080 } 2081 2082 void CodeGenDAGPatterns::ParseComplexPatterns() { 2083 std::vector<Record*> AMs = Records.getAllDerivedDefinitions("ComplexPattern"); 2084 while (!AMs.empty()) { 2085 ComplexPatterns.insert(std::make_pair(AMs.back(), AMs.back())); 2086 AMs.pop_back(); 2087 } 2088 } 2089 2090 2091 /// ParsePatternFragments - Parse all of the PatFrag definitions in the .td 2092 /// file, building up the PatternFragments map. After we've collected them all, 2093 /// inline fragments together as necessary, so that there are no references left 2094 /// inside a pattern fragment to a pattern fragment. 2095 /// 2096 void CodeGenDAGPatterns::ParsePatternFragments() { 2097 std::vector<Record*> Fragments = Records.getAllDerivedDefinitions("PatFrag"); 2098 2099 // First step, parse all of the fragments. 2100 for (unsigned i = 0, e = Fragments.size(); i != e; ++i) { 2101 DagInit *Tree = Fragments[i]->getValueAsDag("Fragment"); 2102 TreePattern *P = new TreePattern(Fragments[i], Tree, true, *this); 2103 PatternFragments[Fragments[i]] = P; 2104 2105 // Validate the argument list, converting it to set, to discard duplicates. 2106 std::vector<std::string> &Args = P->getArgList(); 2107 std::set<std::string> OperandsSet(Args.begin(), Args.end()); 2108 2109 if (OperandsSet.count("")) 2110 P->error("Cannot have unnamed 'node' values in pattern fragment!"); 2111 2112 // Parse the operands list. 2113 DagInit *OpsList = Fragments[i]->getValueAsDag("Operands"); 2114 DefInit *OpsOp = dynamic_cast<DefInit*>(OpsList->getOperator()); 2115 // Special cases: ops == outs == ins. Different names are used to 2116 // improve readability. 2117 if (!OpsOp || 2118 (OpsOp->getDef()->getName() != "ops" && 2119 OpsOp->getDef()->getName() != "outs" && 2120 OpsOp->getDef()->getName() != "ins")) 2121 P->error("Operands list should start with '(ops ... '!"); 2122 2123 // Copy over the arguments. 2124 Args.clear(); 2125 for (unsigned j = 0, e = OpsList->getNumArgs(); j != e; ++j) { 2126 if (!dynamic_cast<DefInit*>(OpsList->getArg(j)) || 2127 static_cast<DefInit*>(OpsList->getArg(j))-> 2128 getDef()->getName() != "node") 2129 P->error("Operands list should all be 'node' values."); 2130 if (OpsList->getArgName(j).empty()) 2131 P->error("Operands list should have names for each operand!"); 2132 if (!OperandsSet.count(OpsList->getArgName(j))) 2133 P->error("'" + OpsList->getArgName(j) + 2134 "' does not occur in pattern or was multiply specified!"); 2135 OperandsSet.erase(OpsList->getArgName(j)); 2136 Args.push_back(OpsList->getArgName(j)); 2137 } 2138 2139 if (!OperandsSet.empty()) 2140 P->error("Operands list does not contain an entry for operand '" + 2141 *OperandsSet.begin() + "'!"); 2142 2143 // If there is a code init for this fragment, keep track of the fact that 2144 // this fragment uses it. 2145 TreePredicateFn PredFn(P); 2146 if (!PredFn.isAlwaysTrue()) 2147 P->getOnlyTree()->addPredicateFn(PredFn); 2148 2149 // If there is a node transformation corresponding to this, keep track of 2150 // it. 2151 Record *Transform = Fragments[i]->getValueAsDef("OperandTransform"); 2152 if (!getSDNodeTransform(Transform).second.empty()) // not noop xform? 2153 P->getOnlyTree()->setTransformFn(Transform); 2154 } 2155 2156 // Now that we've parsed all of the tree fragments, do a closure on them so 2157 // that there are not references to PatFrags left inside of them. 2158 for (unsigned i = 0, e = Fragments.size(); i != e; ++i) { 2159 TreePattern *ThePat = PatternFragments[Fragments[i]]; 2160 ThePat->InlinePatternFragments(); 2161 2162 // Infer as many types as possible. Don't worry about it if we don't infer 2163 // all of them, some may depend on the inputs of the pattern. 2164 try { 2165 ThePat->InferAllTypes(); 2166 } catch (...) { 2167 // If this pattern fragment is not supported by this target (no types can 2168 // satisfy its constraints), just ignore it. If the bogus pattern is 2169 // actually used by instructions, the type consistency error will be 2170 // reported there. 2171 } 2172 2173 // If debugging, print out the pattern fragment result. 2174 DEBUG(ThePat->dump()); 2175 } 2176 } 2177 2178 void CodeGenDAGPatterns::ParseDefaultOperands() { 2179 std::vector<Record*> DefaultOps[2]; 2180 DefaultOps[0] = Records.getAllDerivedDefinitions("PredicateOperand"); 2181 DefaultOps[1] = Records.getAllDerivedDefinitions("OptionalDefOperand"); 2182 2183 // Find some SDNode. 2184 assert(!SDNodes.empty() && "No SDNodes parsed?"); 2185 Init *SomeSDNode = DefInit::get(SDNodes.begin()->first); 2186 2187 for (unsigned iter = 0; iter != 2; ++iter) { 2188 for (unsigned i = 0, e = DefaultOps[iter].size(); i != e; ++i) { 2189 DagInit *DefaultInfo = DefaultOps[iter][i]->getValueAsDag("DefaultOps"); 2190 2191 // Clone the DefaultInfo dag node, changing the operator from 'ops' to 2192 // SomeSDnode so that we can parse this. 2193 std::vector<std::pair<Init*, std::string> > Ops; 2194 for (unsigned op = 0, e = DefaultInfo->getNumArgs(); op != e; ++op) 2195 Ops.push_back(std::make_pair(DefaultInfo->getArg(op), 2196 DefaultInfo->getArgName(op))); 2197 DagInit *DI = DagInit::get(SomeSDNode, "", Ops); 2198 2199 // Create a TreePattern to parse this. 2200 TreePattern P(DefaultOps[iter][i], DI, false, *this); 2201 assert(P.getNumTrees() == 1 && "This ctor can only produce one tree!"); 2202 2203 // Copy the operands over into a DAGDefaultOperand. 2204 DAGDefaultOperand DefaultOpInfo; 2205 2206 TreePatternNode *T = P.getTree(0); 2207 for (unsigned op = 0, e = T->getNumChildren(); op != e; ++op) { 2208 TreePatternNode *TPN = T->getChild(op); 2209 while (TPN->ApplyTypeConstraints(P, false)) 2210 /* Resolve all types */; 2211 2212 if (TPN->ContainsUnresolvedType()) { 2213 if (iter == 0) 2214 throw "Value #" + utostr(i) + " of PredicateOperand '" + 2215 DefaultOps[iter][i]->getName() +"' doesn't have a concrete type!"; 2216 else 2217 throw "Value #" + utostr(i) + " of OptionalDefOperand '" + 2218 DefaultOps[iter][i]->getName() +"' doesn't have a concrete type!"; 2219 } 2220 DefaultOpInfo.DefaultOps.push_back(TPN); 2221 } 2222 2223 // Insert it into the DefaultOperands map so we can find it later. 2224 DefaultOperands[DefaultOps[iter][i]] = DefaultOpInfo; 2225 } 2226 } 2227 } 2228 2229 /// HandleUse - Given "Pat" a leaf in the pattern, check to see if it is an 2230 /// instruction input. Return true if this is a real use. 2231 static bool HandleUse(TreePattern *I, TreePatternNode *Pat, 2232 std::map<std::string, TreePatternNode*> &InstInputs) { 2233 // No name -> not interesting. 2234 if (Pat->getName().empty()) { 2235 if (Pat->isLeaf()) { 2236 DefInit *DI = dynamic_cast<DefInit*>(Pat->getLeafValue()); 2237 if (DI && (DI->getDef()->isSubClassOf("RegisterClass") || 2238 DI->getDef()->isSubClassOf("RegisterOperand"))) 2239 I->error("Input " + DI->getDef()->getName() + " must be named!"); 2240 } 2241 return false; 2242 } 2243 2244 Record *Rec; 2245 if (Pat->isLeaf()) { 2246 DefInit *DI = dynamic_cast<DefInit*>(Pat->getLeafValue()); 2247 if (!DI) I->error("Input $" + Pat->getName() + " must be an identifier!"); 2248 Rec = DI->getDef(); 2249 } else { 2250 Rec = Pat->getOperator(); 2251 } 2252 2253 // SRCVALUE nodes are ignored. 2254 if (Rec->getName() == "srcvalue") 2255 return false; 2256 2257 TreePatternNode *&Slot = InstInputs[Pat->getName()]; 2258 if (!Slot) { 2259 Slot = Pat; 2260 return true; 2261 } 2262 Record *SlotRec; 2263 if (Slot->isLeaf()) { 2264 SlotRec = dynamic_cast<DefInit*>(Slot->getLeafValue())->getDef(); 2265 } else { 2266 assert(Slot->getNumChildren() == 0 && "can't be a use with children!"); 2267 SlotRec = Slot->getOperator(); 2268 } 2269 2270 // Ensure that the inputs agree if we've already seen this input. 2271 if (Rec != SlotRec) 2272 I->error("All $" + Pat->getName() + " inputs must agree with each other"); 2273 if (Slot->getExtTypes() != Pat->getExtTypes()) 2274 I->error("All $" + Pat->getName() + " inputs must agree with each other"); 2275 return true; 2276 } 2277 2278 /// FindPatternInputsAndOutputs - Scan the specified TreePatternNode (which is 2279 /// part of "I", the instruction), computing the set of inputs and outputs of 2280 /// the pattern. Report errors if we see anything naughty. 2281 void CodeGenDAGPatterns:: 2282 FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, 2283 std::map<std::string, TreePatternNode*> &InstInputs, 2284 std::map<std::string, TreePatternNode*>&InstResults, 2285 std::vector<Record*> &InstImpResults) { 2286 if (Pat->isLeaf()) { 2287 bool isUse = HandleUse(I, Pat, InstInputs); 2288 if (!isUse && Pat->getTransformFn()) 2289 I->error("Cannot specify a transform function for a non-input value!"); 2290 return; 2291 } 2292 2293 if (Pat->getOperator()->getName() == "implicit") { 2294 for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) { 2295 TreePatternNode *Dest = Pat->getChild(i); 2296 if (!Dest->isLeaf()) 2297 I->error("implicitly defined value should be a register!"); 2298 2299 DefInit *Val = dynamic_cast<DefInit*>(Dest->getLeafValue()); 2300 if (!Val || !Val->getDef()->isSubClassOf("Register")) 2301 I->error("implicitly defined value should be a register!"); 2302 InstImpResults.push_back(Val->getDef()); 2303 } 2304 return; 2305 } 2306 2307 if (Pat->getOperator()->getName() != "set") { 2308 // If this is not a set, verify that the children nodes are not void typed, 2309 // and recurse. 2310 for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) { 2311 if (Pat->getChild(i)->getNumTypes() == 0) 2312 I->error("Cannot have void nodes inside of patterns!"); 2313 FindPatternInputsAndOutputs(I, Pat->getChild(i), InstInputs, InstResults, 2314 InstImpResults); 2315 } 2316 2317 // If this is a non-leaf node with no children, treat it basically as if 2318 // it were a leaf. This handles nodes like (imm). 2319 bool isUse = HandleUse(I, Pat, InstInputs); 2320 2321 if (!isUse && Pat->getTransformFn()) 2322 I->error("Cannot specify a transform function for a non-input value!"); 2323 return; 2324 } 2325 2326 // Otherwise, this is a set, validate and collect instruction results. 2327 if (Pat->getNumChildren() == 0) 2328 I->error("set requires operands!"); 2329 2330 if (Pat->getTransformFn()) 2331 I->error("Cannot specify a transform function on a set node!"); 2332 2333 // Check the set destinations. 2334 unsigned NumDests = Pat->getNumChildren()-1; 2335 for (unsigned i = 0; i != NumDests; ++i) { 2336 TreePatternNode *Dest = Pat->getChild(i); 2337 if (!Dest->isLeaf()) 2338 I->error("set destination should be a register!"); 2339 2340 DefInit *Val = dynamic_cast<DefInit*>(Dest->getLeafValue()); 2341 if (!Val) 2342 I->error("set destination should be a register!"); 2343 2344 if (Val->getDef()->isSubClassOf("RegisterClass") || 2345 Val->getDef()->isSubClassOf("RegisterOperand") || 2346 Val->getDef()->isSubClassOf("PointerLikeRegClass")) { 2347 if (Dest->getName().empty()) 2348 I->error("set destination must have a name!"); 2349 if (InstResults.count(Dest->getName())) 2350 I->error("cannot set '" + Dest->getName() +"' multiple times"); 2351 InstResults[Dest->getName()] = Dest; 2352 } else if (Val->getDef()->isSubClassOf("Register")) { 2353 InstImpResults.push_back(Val->getDef()); 2354 } else { 2355 I->error("set destination should be a register!"); 2356 } 2357 } 2358 2359 // Verify and collect info from the computation. 2360 FindPatternInputsAndOutputs(I, Pat->getChild(NumDests), 2361 InstInputs, InstResults, InstImpResults); 2362 } 2363 2364 //===----------------------------------------------------------------------===// 2365 // Instruction Analysis 2366 //===----------------------------------------------------------------------===// 2367 2368 class InstAnalyzer { 2369 const CodeGenDAGPatterns &CDP; 2370 bool &mayStore; 2371 bool &mayLoad; 2372 bool &IsBitcast; 2373 bool &HasSideEffects; 2374 bool &IsVariadic; 2375 public: 2376 InstAnalyzer(const CodeGenDAGPatterns &cdp, 2377 bool &maystore, bool &mayload, bool &isbc, bool &hse, bool &isv) 2378 : CDP(cdp), mayStore(maystore), mayLoad(mayload), IsBitcast(isbc), 2379 HasSideEffects(hse), IsVariadic(isv) { 2380 } 2381 2382 /// Analyze - Analyze the specified instruction, returning true if the 2383 /// instruction had a pattern. 2384 bool Analyze(Record *InstRecord) { 2385 const TreePattern *Pattern = CDP.getInstruction(InstRecord).getPattern(); 2386 if (Pattern == 0) { 2387 HasSideEffects = 1; 2388 return false; // No pattern. 2389 } 2390 2391 // FIXME: Assume only the first tree is the pattern. The others are clobber 2392 // nodes. 2393 AnalyzeNode(Pattern->getTree(0)); 2394 return true; 2395 } 2396 2397 private: 2398 bool IsNodeBitcast(const TreePatternNode *N) const { 2399 if (HasSideEffects || mayLoad || mayStore || IsVariadic) 2400 return false; 2401 2402 if (N->getNumChildren() != 2) 2403 return false; 2404 2405 const TreePatternNode *N0 = N->getChild(0); 2406 if (!N0->isLeaf() || !dynamic_cast<DefInit*>(N0->getLeafValue())) 2407 return false; 2408 2409 const TreePatternNode *N1 = N->getChild(1); 2410 if (N1->isLeaf()) 2411 return false; 2412 if (N1->getNumChildren() != 1 || !N1->getChild(0)->isLeaf()) 2413 return false; 2414 2415 const SDNodeInfo &OpInfo = CDP.getSDNodeInfo(N1->getOperator()); 2416 if (OpInfo.getNumResults() != 1 || OpInfo.getNumOperands() != 1) 2417 return false; 2418 return OpInfo.getEnumName() == "ISD::BITCAST"; 2419 } 2420 2421 void AnalyzeNode(const TreePatternNode *N) { 2422 if (N->isLeaf()) { 2423 if (DefInit *DI = dynamic_cast<DefInit*>(N->getLeafValue())) { 2424 Record *LeafRec = DI->getDef(); 2425 // Handle ComplexPattern leaves. 2426 if (LeafRec->isSubClassOf("ComplexPattern")) { 2427 const ComplexPattern &CP = CDP.getComplexPattern(LeafRec); 2428 if (CP.hasProperty(SDNPMayStore)) mayStore = true; 2429 if (CP.hasProperty(SDNPMayLoad)) mayLoad = true; 2430 if (CP.hasProperty(SDNPSideEffect)) HasSideEffects = true; 2431 } 2432 } 2433 return; 2434 } 2435 2436 // Analyze children. 2437 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 2438 AnalyzeNode(N->getChild(i)); 2439 2440 // Ignore set nodes, which are not SDNodes. 2441 if (N->getOperator()->getName() == "set") { 2442 IsBitcast = IsNodeBitcast(N); 2443 return; 2444 } 2445 2446 // Get information about the SDNode for the operator. 2447 const SDNodeInfo &OpInfo = CDP.getSDNodeInfo(N->getOperator()); 2448 2449 // Notice properties of the node. 2450 if (OpInfo.hasProperty(SDNPMayStore)) mayStore = true; 2451 if (OpInfo.hasProperty(SDNPMayLoad)) mayLoad = true; 2452 if (OpInfo.hasProperty(SDNPSideEffect)) HasSideEffects = true; 2453 if (OpInfo.hasProperty(SDNPVariadic)) IsVariadic = true; 2454 2455 if (const CodeGenIntrinsic *IntInfo = N->getIntrinsicInfo(CDP)) { 2456 // If this is an intrinsic, analyze it. 2457 if (IntInfo->ModRef >= CodeGenIntrinsic::ReadArgMem) 2458 mayLoad = true;// These may load memory. 2459 2460 if (IntInfo->ModRef >= CodeGenIntrinsic::ReadWriteArgMem) 2461 mayStore = true;// Intrinsics that can write to memory are 'mayStore'. 2462 2463 if (IntInfo->ModRef >= CodeGenIntrinsic::ReadWriteMem) 2464 // WriteMem intrinsics can have other strange effects. 2465 HasSideEffects = true; 2466 } 2467 } 2468 2469 }; 2470 2471 static void InferFromPattern(const CodeGenInstruction &Inst, 2472 bool &MayStore, bool &MayLoad, 2473 bool &IsBitcast, 2474 bool &HasSideEffects, bool &IsVariadic, 2475 const CodeGenDAGPatterns &CDP) { 2476 MayStore = MayLoad = IsBitcast = HasSideEffects = IsVariadic = false; 2477 2478 bool HadPattern = 2479 InstAnalyzer(CDP, MayStore, MayLoad, IsBitcast, HasSideEffects, IsVariadic) 2480 .Analyze(Inst.TheDef); 2481 2482 // InstAnalyzer only correctly analyzes mayStore/mayLoad so far. 2483 if (Inst.mayStore) { // If the .td file explicitly sets mayStore, use it. 2484 // If we decided that this is a store from the pattern, then the .td file 2485 // entry is redundant. 2486 if (MayStore) 2487 PrintWarning(Inst.TheDef->getLoc(), 2488 "mayStore flag explicitly set on " 2489 "instruction, but flag already inferred from pattern."); 2490 MayStore = true; 2491 } 2492 2493 if (Inst.mayLoad) { // If the .td file explicitly sets mayLoad, use it. 2494 // If we decided that this is a load from the pattern, then the .td file 2495 // entry is redundant. 2496 if (MayLoad) 2497 PrintWarning(Inst.TheDef->getLoc(), 2498 "mayLoad flag explicitly set on " 2499 "instruction, but flag already inferred from pattern."); 2500 MayLoad = true; 2501 } 2502 2503 if (Inst.neverHasSideEffects) { 2504 if (HadPattern) 2505 PrintWarning(Inst.TheDef->getLoc(), 2506 "neverHasSideEffects flag explicitly set on " 2507 "instruction, but flag already inferred from pattern."); 2508 HasSideEffects = false; 2509 } 2510 2511 if (Inst.hasSideEffects) { 2512 if (HasSideEffects) 2513 PrintWarning(Inst.TheDef->getLoc(), 2514 "hasSideEffects flag explicitly set on " 2515 "instruction, but flag already inferred from pattern."); 2516 HasSideEffects = true; 2517 } 2518 2519 if (Inst.Operands.isVariadic) 2520 IsVariadic = true; // Can warn if we want. 2521 } 2522 2523 /// ParseInstructions - Parse all of the instructions, inlining and resolving 2524 /// any fragments involved. This populates the Instructions list with fully 2525 /// resolved instructions. 2526 void CodeGenDAGPatterns::ParseInstructions() { 2527 std::vector<Record*> Instrs = Records.getAllDerivedDefinitions("Instruction"); 2528 2529 for (unsigned i = 0, e = Instrs.size(); i != e; ++i) { 2530 ListInit *LI = 0; 2531 2532 if (dynamic_cast<ListInit*>(Instrs[i]->getValueInit("Pattern"))) 2533 LI = Instrs[i]->getValueAsListInit("Pattern"); 2534 2535 // If there is no pattern, only collect minimal information about the 2536 // instruction for its operand list. We have to assume that there is one 2537 // result, as we have no detailed info. 2538 if (!LI || LI->getSize() == 0) { 2539 std::vector<Record*> Results; 2540 std::vector<Record*> Operands; 2541 2542 CodeGenInstruction &InstInfo = Target.getInstruction(Instrs[i]); 2543 2544 if (InstInfo.Operands.size() != 0) { 2545 if (InstInfo.Operands.NumDefs == 0) { 2546 // These produce no results 2547 for (unsigned j = 0, e = InstInfo.Operands.size(); j < e; ++j) 2548 Operands.push_back(InstInfo.Operands[j].Rec); 2549 } else { 2550 // Assume the first operand is the result. 2551 Results.push_back(InstInfo.Operands[0].Rec); 2552 2553 // The rest are inputs. 2554 for (unsigned j = 1, e = InstInfo.Operands.size(); j < e; ++j) 2555 Operands.push_back(InstInfo.Operands[j].Rec); 2556 } 2557 } 2558 2559 // Create and insert the instruction. 2560 std::vector<Record*> ImpResults; 2561 Instructions.insert(std::make_pair(Instrs[i], 2562 DAGInstruction(0, Results, Operands, ImpResults))); 2563 continue; // no pattern. 2564 } 2565 2566 // Parse the instruction. 2567 TreePattern *I = new TreePattern(Instrs[i], LI, true, *this); 2568 // Inline pattern fragments into it. 2569 I->InlinePatternFragments(); 2570 2571 // Infer as many types as possible. If we cannot infer all of them, we can 2572 // never do anything with this instruction pattern: report it to the user. 2573 if (!I->InferAllTypes()) 2574 I->error("Could not infer all types in pattern!"); 2575 2576 // InstInputs - Keep track of all of the inputs of the instruction, along 2577 // with the record they are declared as. 2578 std::map<std::string, TreePatternNode*> InstInputs; 2579 2580 // InstResults - Keep track of all the virtual registers that are 'set' 2581 // in the instruction, including what reg class they are. 2582 std::map<std::string, TreePatternNode*> InstResults; 2583 2584 std::vector<Record*> InstImpResults; 2585 2586 // Verify that the top-level forms in the instruction are of void type, and 2587 // fill in the InstResults map. 2588 for (unsigned j = 0, e = I->getNumTrees(); j != e; ++j) { 2589 TreePatternNode *Pat = I->getTree(j); 2590 if (Pat->getNumTypes() != 0) 2591 I->error("Top-level forms in instruction pattern should have" 2592 " void types"); 2593 2594 // Find inputs and outputs, and verify the structure of the uses/defs. 2595 FindPatternInputsAndOutputs(I, Pat, InstInputs, InstResults, 2596 InstImpResults); 2597 } 2598 2599 // Now that we have inputs and outputs of the pattern, inspect the operands 2600 // list for the instruction. This determines the order that operands are 2601 // added to the machine instruction the node corresponds to. 2602 unsigned NumResults = InstResults.size(); 2603 2604 // Parse the operands list from the (ops) list, validating it. 2605 assert(I->getArgList().empty() && "Args list should still be empty here!"); 2606 CodeGenInstruction &CGI = Target.getInstruction(Instrs[i]); 2607 2608 // Check that all of the results occur first in the list. 2609 std::vector<Record*> Results; 2610 TreePatternNode *Res0Node = 0; 2611 for (unsigned i = 0; i != NumResults; ++i) { 2612 if (i == CGI.Operands.size()) 2613 I->error("'" + InstResults.begin()->first + 2614 "' set but does not appear in operand list!"); 2615 const std::string &OpName = CGI.Operands[i].Name; 2616 2617 // Check that it exists in InstResults. 2618 TreePatternNode *RNode = InstResults[OpName]; 2619 if (RNode == 0) 2620 I->error("Operand $" + OpName + " does not exist in operand list!"); 2621 2622 if (i == 0) 2623 Res0Node = RNode; 2624 Record *R = dynamic_cast<DefInit*>(RNode->getLeafValue())->getDef(); 2625 if (R == 0) 2626 I->error("Operand $" + OpName + " should be a set destination: all " 2627 "outputs must occur before inputs in operand list!"); 2628 2629 if (CGI.Operands[i].Rec != R) 2630 I->error("Operand $" + OpName + " class mismatch!"); 2631 2632 // Remember the return type. 2633 Results.push_back(CGI.Operands[i].Rec); 2634 2635 // Okay, this one checks out. 2636 InstResults.erase(OpName); 2637 } 2638 2639 // Loop over the inputs next. Make a copy of InstInputs so we can destroy 2640 // the copy while we're checking the inputs. 2641 std::map<std::string, TreePatternNode*> InstInputsCheck(InstInputs); 2642 2643 std::vector<TreePatternNode*> ResultNodeOperands; 2644 std::vector<Record*> Operands; 2645 for (unsigned i = NumResults, e = CGI.Operands.size(); i != e; ++i) { 2646 CGIOperandList::OperandInfo &Op = CGI.Operands[i]; 2647 const std::string &OpName = Op.Name; 2648 if (OpName.empty()) 2649 I->error("Operand #" + utostr(i) + " in operands list has no name!"); 2650 2651 if (!InstInputsCheck.count(OpName)) { 2652 // If this is an predicate operand or optional def operand with an 2653 // DefaultOps set filled in, we can ignore this. When we codegen it, 2654 // we will do so as always executed. 2655 if (Op.Rec->isSubClassOf("PredicateOperand") || 2656 Op.Rec->isSubClassOf("OptionalDefOperand")) { 2657 // Does it have a non-empty DefaultOps field? If so, ignore this 2658 // operand. 2659 if (!getDefaultOperand(Op.Rec).DefaultOps.empty()) 2660 continue; 2661 } 2662 I->error("Operand $" + OpName + 2663 " does not appear in the instruction pattern"); 2664 } 2665 TreePatternNode *InVal = InstInputsCheck[OpName]; 2666 InstInputsCheck.erase(OpName); // It occurred, remove from map. 2667 2668 if (InVal->isLeaf() && 2669 dynamic_cast<DefInit*>(InVal->getLeafValue())) { 2670 Record *InRec = static_cast<DefInit*>(InVal->getLeafValue())->getDef(); 2671 if (Op.Rec != InRec && !InRec->isSubClassOf("ComplexPattern")) 2672 I->error("Operand $" + OpName + "'s register class disagrees" 2673 " between the operand and pattern"); 2674 } 2675 Operands.push_back(Op.Rec); 2676 2677 // Construct the result for the dest-pattern operand list. 2678 TreePatternNode *OpNode = InVal->clone(); 2679 2680 // No predicate is useful on the result. 2681 OpNode->clearPredicateFns(); 2682 2683 // Promote the xform function to be an explicit node if set. 2684 if (Record *Xform = OpNode->getTransformFn()) { 2685 OpNode->setTransformFn(0); 2686 std::vector<TreePatternNode*> Children; 2687 Children.push_back(OpNode); 2688 OpNode = new TreePatternNode(Xform, Children, OpNode->getNumTypes()); 2689 } 2690 2691 ResultNodeOperands.push_back(OpNode); 2692 } 2693 2694 if (!InstInputsCheck.empty()) 2695 I->error("Input operand $" + InstInputsCheck.begin()->first + 2696 " occurs in pattern but not in operands list!"); 2697 2698 TreePatternNode *ResultPattern = 2699 new TreePatternNode(I->getRecord(), ResultNodeOperands, 2700 GetNumNodeResults(I->getRecord(), *this)); 2701 // Copy fully inferred output node type to instruction result pattern. 2702 for (unsigned i = 0; i != NumResults; ++i) 2703 ResultPattern->setType(i, Res0Node->getExtType(i)); 2704 2705 // Create and insert the instruction. 2706 // FIXME: InstImpResults should not be part of DAGInstruction. 2707 DAGInstruction TheInst(I, Results, Operands, InstImpResults); 2708 Instructions.insert(std::make_pair(I->getRecord(), TheInst)); 2709 2710 // Use a temporary tree pattern to infer all types and make sure that the 2711 // constructed result is correct. This depends on the instruction already 2712 // being inserted into the Instructions map. 2713 TreePattern Temp(I->getRecord(), ResultPattern, false, *this); 2714 Temp.InferAllTypes(&I->getNamedNodesMap()); 2715 2716 DAGInstruction &TheInsertedInst = Instructions.find(I->getRecord())->second; 2717 TheInsertedInst.setResultPattern(Temp.getOnlyTree()); 2718 2719 DEBUG(I->dump()); 2720 } 2721 2722 // If we can, convert the instructions to be patterns that are matched! 2723 for (std::map<Record*, DAGInstruction, RecordPtrCmp>::iterator II = 2724 Instructions.begin(), 2725 E = Instructions.end(); II != E; ++II) { 2726 DAGInstruction &TheInst = II->second; 2727 const TreePattern *I = TheInst.getPattern(); 2728 if (I == 0) continue; // No pattern. 2729 2730 // FIXME: Assume only the first tree is the pattern. The others are clobber 2731 // nodes. 2732 TreePatternNode *Pattern = I->getTree(0); 2733 TreePatternNode *SrcPattern; 2734 if (Pattern->getOperator()->getName() == "set") { 2735 SrcPattern = Pattern->getChild(Pattern->getNumChildren()-1)->clone(); 2736 } else{ 2737 // Not a set (store or something?) 2738 SrcPattern = Pattern; 2739 } 2740 2741 Record *Instr = II->first; 2742 AddPatternToMatch(I, 2743 PatternToMatch(Instr, 2744 Instr->getValueAsListInit("Predicates"), 2745 SrcPattern, 2746 TheInst.getResultPattern(), 2747 TheInst.getImpResults(), 2748 Instr->getValueAsInt("AddedComplexity"), 2749 Instr->getID())); 2750 } 2751 } 2752 2753 2754 typedef std::pair<const TreePatternNode*, unsigned> NameRecord; 2755 2756 static void FindNames(const TreePatternNode *P, 2757 std::map<std::string, NameRecord> &Names, 2758 const TreePattern *PatternTop) { 2759 if (!P->getName().empty()) { 2760 NameRecord &Rec = Names[P->getName()]; 2761 // If this is the first instance of the name, remember the node. 2762 if (Rec.second++ == 0) 2763 Rec.first = P; 2764 else if (Rec.first->getExtTypes() != P->getExtTypes()) 2765 PatternTop->error("repetition of value: $" + P->getName() + 2766 " where different uses have different types!"); 2767 } 2768 2769 if (!P->isLeaf()) { 2770 for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) 2771 FindNames(P->getChild(i), Names, PatternTop); 2772 } 2773 } 2774 2775 void CodeGenDAGPatterns::AddPatternToMatch(const TreePattern *Pattern, 2776 const PatternToMatch &PTM) { 2777 // Do some sanity checking on the pattern we're about to match. 2778 std::string Reason; 2779 if (!PTM.getSrcPattern()->canPatternMatch(Reason, *this)) 2780 Pattern->error("Pattern can never match: " + Reason); 2781 2782 // If the source pattern's root is a complex pattern, that complex pattern 2783 // must specify the nodes it can potentially match. 2784 if (const ComplexPattern *CP = 2785 PTM.getSrcPattern()->getComplexPatternInfo(*this)) 2786 if (CP->getRootNodes().empty()) 2787 Pattern->error("ComplexPattern at root must specify list of opcodes it" 2788 " could match"); 2789 2790 2791 // Find all of the named values in the input and output, ensure they have the 2792 // same type. 2793 std::map<std::string, NameRecord> SrcNames, DstNames; 2794 FindNames(PTM.getSrcPattern(), SrcNames, Pattern); 2795 FindNames(PTM.getDstPattern(), DstNames, Pattern); 2796 2797 // Scan all of the named values in the destination pattern, rejecting them if 2798 // they don't exist in the input pattern. 2799 for (std::map<std::string, NameRecord>::iterator 2800 I = DstNames.begin(), E = DstNames.end(); I != E; ++I) { 2801 if (SrcNames[I->first].first == 0) 2802 Pattern->error("Pattern has input without matching name in output: $" + 2803 I->first); 2804 } 2805 2806 // Scan all of the named values in the source pattern, rejecting them if the 2807 // name isn't used in the dest, and isn't used to tie two values together. 2808 for (std::map<std::string, NameRecord>::iterator 2809 I = SrcNames.begin(), E = SrcNames.end(); I != E; ++I) 2810 if (DstNames[I->first].first == 0 && SrcNames[I->first].second == 1) 2811 Pattern->error("Pattern has dead named input: $" + I->first); 2812 2813 PatternsToMatch.push_back(PTM); 2814 } 2815 2816 2817 2818 void CodeGenDAGPatterns::InferInstructionFlags() { 2819 const std::vector<const CodeGenInstruction*> &Instructions = 2820 Target.getInstructionsByEnumValue(); 2821 for (unsigned i = 0, e = Instructions.size(); i != e; ++i) { 2822 CodeGenInstruction &InstInfo = 2823 const_cast<CodeGenInstruction &>(*Instructions[i]); 2824 // Determine properties of the instruction from its pattern. 2825 bool MayStore, MayLoad, IsBitcast, HasSideEffects, IsVariadic; 2826 InferFromPattern(InstInfo, MayStore, MayLoad, IsBitcast, 2827 HasSideEffects, IsVariadic, *this); 2828 InstInfo.mayStore = MayStore; 2829 InstInfo.mayLoad = MayLoad; 2830 InstInfo.isBitcast = IsBitcast; 2831 InstInfo.hasSideEffects = HasSideEffects; 2832 InstInfo.Operands.isVariadic = IsVariadic; 2833 2834 // Sanity checks. 2835 if (InstInfo.isReMaterializable && InstInfo.hasSideEffects) 2836 throw TGError(InstInfo.TheDef->getLoc(), "The instruction " + 2837 InstInfo.TheDef->getName() + 2838 " is rematerializable AND has unmodeled side effects?"); 2839 } 2840 } 2841 2842 /// Given a pattern result with an unresolved type, see if we can find one 2843 /// instruction with an unresolved result type. Force this result type to an 2844 /// arbitrary element if it's possible types to converge results. 2845 static bool ForceArbitraryInstResultType(TreePatternNode *N, TreePattern &TP) { 2846 if (N->isLeaf()) 2847 return false; 2848 2849 // Analyze children. 2850 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 2851 if (ForceArbitraryInstResultType(N->getChild(i), TP)) 2852 return true; 2853 2854 if (!N->getOperator()->isSubClassOf("Instruction")) 2855 return false; 2856 2857 // If this type is already concrete or completely unknown we can't do 2858 // anything. 2859 for (unsigned i = 0, e = N->getNumTypes(); i != e; ++i) { 2860 if (N->getExtType(i).isCompletelyUnknown() || N->getExtType(i).isConcrete()) 2861 continue; 2862 2863 // Otherwise, force its type to the first possibility (an arbitrary choice). 2864 if (N->getExtType(i).MergeInTypeInfo(N->getExtType(i).getTypeList()[0], TP)) 2865 return true; 2866 } 2867 2868 return false; 2869 } 2870 2871 void CodeGenDAGPatterns::ParsePatterns() { 2872 std::vector<Record*> Patterns = Records.getAllDerivedDefinitions("Pattern"); 2873 2874 for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { 2875 Record *CurPattern = Patterns[i]; 2876 DagInit *Tree = CurPattern->getValueAsDag("PatternToMatch"); 2877 TreePattern *Pattern = new TreePattern(CurPattern, Tree, true, *this); 2878 2879 // Inline pattern fragments into it. 2880 Pattern->InlinePatternFragments(); 2881 2882 ListInit *LI = CurPattern->getValueAsListInit("ResultInstrs"); 2883 if (LI->getSize() == 0) continue; // no pattern. 2884 2885 // Parse the instruction. 2886 TreePattern *Result = new TreePattern(CurPattern, LI, false, *this); 2887 2888 // Inline pattern fragments into it. 2889 Result->InlinePatternFragments(); 2890 2891 if (Result->getNumTrees() != 1) 2892 Result->error("Cannot handle instructions producing instructions " 2893 "with temporaries yet!"); 2894 2895 bool IterateInference; 2896 bool InferredAllPatternTypes, InferredAllResultTypes; 2897 do { 2898 // Infer as many types as possible. If we cannot infer all of them, we 2899 // can never do anything with this pattern: report it to the user. 2900 InferredAllPatternTypes = 2901 Pattern->InferAllTypes(&Pattern->getNamedNodesMap()); 2902 2903 // Infer as many types as possible. If we cannot infer all of them, we 2904 // can never do anything with this pattern: report it to the user. 2905 InferredAllResultTypes = 2906 Result->InferAllTypes(&Pattern->getNamedNodesMap()); 2907 2908 IterateInference = false; 2909 2910 // Apply the type of the result to the source pattern. This helps us 2911 // resolve cases where the input type is known to be a pointer type (which 2912 // is considered resolved), but the result knows it needs to be 32- or 2913 // 64-bits. Infer the other way for good measure. 2914 for (unsigned i = 0, e = std::min(Result->getTree(0)->getNumTypes(), 2915 Pattern->getTree(0)->getNumTypes()); 2916 i != e; ++i) { 2917 IterateInference = Pattern->getTree(0)-> 2918 UpdateNodeType(i, Result->getTree(0)->getExtType(i), *Result); 2919 IterateInference |= Result->getTree(0)-> 2920 UpdateNodeType(i, Pattern->getTree(0)->getExtType(i), *Result); 2921 } 2922 2923 // If our iteration has converged and the input pattern's types are fully 2924 // resolved but the result pattern is not fully resolved, we may have a 2925 // situation where we have two instructions in the result pattern and 2926 // the instructions require a common register class, but don't care about 2927 // what actual MVT is used. This is actually a bug in our modelling: 2928 // output patterns should have register classes, not MVTs. 2929 // 2930 // In any case, to handle this, we just go through and disambiguate some 2931 // arbitrary types to the result pattern's nodes. 2932 if (!IterateInference && InferredAllPatternTypes && 2933 !InferredAllResultTypes) 2934 IterateInference = ForceArbitraryInstResultType(Result->getTree(0), 2935 *Result); 2936 } while (IterateInference); 2937 2938 // Verify that we inferred enough types that we can do something with the 2939 // pattern and result. If these fire the user has to add type casts. 2940 if (!InferredAllPatternTypes) 2941 Pattern->error("Could not infer all types in pattern!"); 2942 if (!InferredAllResultTypes) { 2943 Pattern->dump(); 2944 Result->error("Could not infer all types in pattern result!"); 2945 } 2946 2947 // Validate that the input pattern is correct. 2948 std::map<std::string, TreePatternNode*> InstInputs; 2949 std::map<std::string, TreePatternNode*> InstResults; 2950 std::vector<Record*> InstImpResults; 2951 for (unsigned j = 0, ee = Pattern->getNumTrees(); j != ee; ++j) 2952 FindPatternInputsAndOutputs(Pattern, Pattern->getTree(j), 2953 InstInputs, InstResults, 2954 InstImpResults); 2955 2956 // Promote the xform function to be an explicit node if set. 2957 TreePatternNode *DstPattern = Result->getOnlyTree(); 2958 std::vector<TreePatternNode*> ResultNodeOperands; 2959 for (unsigned ii = 0, ee = DstPattern->getNumChildren(); ii != ee; ++ii) { 2960 TreePatternNode *OpNode = DstPattern->getChild(ii); 2961 if (Record *Xform = OpNode->getTransformFn()) { 2962 OpNode->setTransformFn(0); 2963 std::vector<TreePatternNode*> Children; 2964 Children.push_back(OpNode); 2965 OpNode = new TreePatternNode(Xform, Children, OpNode->getNumTypes()); 2966 } 2967 ResultNodeOperands.push_back(OpNode); 2968 } 2969 DstPattern = Result->getOnlyTree(); 2970 if (!DstPattern->isLeaf()) 2971 DstPattern = new TreePatternNode(DstPattern->getOperator(), 2972 ResultNodeOperands, 2973 DstPattern->getNumTypes()); 2974 2975 for (unsigned i = 0, e = Result->getOnlyTree()->getNumTypes(); i != e; ++i) 2976 DstPattern->setType(i, Result->getOnlyTree()->getExtType(i)); 2977 2978 TreePattern Temp(Result->getRecord(), DstPattern, false, *this); 2979 Temp.InferAllTypes(); 2980 2981 2982 AddPatternToMatch(Pattern, 2983 PatternToMatch(CurPattern, 2984 CurPattern->getValueAsListInit("Predicates"), 2985 Pattern->getTree(0), 2986 Temp.getOnlyTree(), InstImpResults, 2987 CurPattern->getValueAsInt("AddedComplexity"), 2988 CurPattern->getID())); 2989 } 2990 } 2991 2992 /// CombineChildVariants - Given a bunch of permutations of each child of the 2993 /// 'operator' node, put them together in all possible ways. 2994 static void CombineChildVariants(TreePatternNode *Orig, 2995 const std::vector<std::vector<TreePatternNode*> > &ChildVariants, 2996 std::vector<TreePatternNode*> &OutVariants, 2997 CodeGenDAGPatterns &CDP, 2998 const MultipleUseVarSet &DepVars) { 2999 // Make sure that each operand has at least one variant to choose from. 3000 for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i) 3001 if (ChildVariants[i].empty()) 3002 return; 3003 3004 // The end result is an all-pairs construction of the resultant pattern. 3005 std::vector<unsigned> Idxs; 3006 Idxs.resize(ChildVariants.size()); 3007 bool NotDone; 3008 do { 3009 #ifndef NDEBUG 3010 DEBUG(if (!Idxs.empty()) { 3011 errs() << Orig->getOperator()->getName() << ": Idxs = [ "; 3012 for (unsigned i = 0; i < Idxs.size(); ++i) { 3013 errs() << Idxs[i] << " "; 3014 } 3015 errs() << "]\n"; 3016 }); 3017 #endif 3018 // Create the variant and add it to the output list. 3019 std::vector<TreePatternNode*> NewChildren; 3020 for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i) 3021 NewChildren.push_back(ChildVariants[i][Idxs[i]]); 3022 TreePatternNode *R = new TreePatternNode(Orig->getOperator(), NewChildren, 3023 Orig->getNumTypes()); 3024 3025 // Copy over properties. 3026 R->setName(Orig->getName()); 3027 R->setPredicateFns(Orig->getPredicateFns()); 3028 R->setTransformFn(Orig->getTransformFn()); 3029 for (unsigned i = 0, e = Orig->getNumTypes(); i != e; ++i) 3030 R->setType(i, Orig->getExtType(i)); 3031 3032 // If this pattern cannot match, do not include it as a variant. 3033 std::string ErrString; 3034 if (!R->canPatternMatch(ErrString, CDP)) { 3035 delete R; 3036 } else { 3037 bool AlreadyExists = false; 3038 3039 // Scan to see if this pattern has already been emitted. We can get 3040 // duplication due to things like commuting: 3041 // (and GPRC:$a, GPRC:$b) -> (and GPRC:$b, GPRC:$a) 3042 // which are the same pattern. Ignore the dups. 3043 for (unsigned i = 0, e = OutVariants.size(); i != e; ++i) 3044 if (R->isIsomorphicTo(OutVariants[i], DepVars)) { 3045 AlreadyExists = true; 3046 break; 3047 } 3048 3049 if (AlreadyExists) 3050 delete R; 3051 else 3052 OutVariants.push_back(R); 3053 } 3054 3055 // Increment indices to the next permutation by incrementing the 3056 // indicies from last index backward, e.g., generate the sequence 3057 // [0, 0], [0, 1], [1, 0], [1, 1]. 3058 int IdxsIdx; 3059 for (IdxsIdx = Idxs.size() - 1; IdxsIdx >= 0; --IdxsIdx) { 3060 if (++Idxs[IdxsIdx] == ChildVariants[IdxsIdx].size()) 3061 Idxs[IdxsIdx] = 0; 3062 else 3063 break; 3064 } 3065 NotDone = (IdxsIdx >= 0); 3066 } while (NotDone); 3067 } 3068 3069 /// CombineChildVariants - A helper function for binary operators. 3070 /// 3071 static void CombineChildVariants(TreePatternNode *Orig, 3072 const std::vector<TreePatternNode*> &LHS, 3073 const std::vector<TreePatternNode*> &RHS, 3074 std::vector<TreePatternNode*> &OutVariants, 3075 CodeGenDAGPatterns &CDP, 3076 const MultipleUseVarSet &DepVars) { 3077 std::vector<std::vector<TreePatternNode*> > ChildVariants; 3078 ChildVariants.push_back(LHS); 3079 ChildVariants.push_back(RHS); 3080 CombineChildVariants(Orig, ChildVariants, OutVariants, CDP, DepVars); 3081 } 3082 3083 3084 static void GatherChildrenOfAssociativeOpcode(TreePatternNode *N, 3085 std::vector<TreePatternNode *> &Children) { 3086 assert(N->getNumChildren()==2 &&"Associative but doesn't have 2 children!"); 3087 Record *Operator = N->getOperator(); 3088 3089 // Only permit raw nodes. 3090 if (!N->getName().empty() || !N->getPredicateFns().empty() || 3091 N->getTransformFn()) { 3092 Children.push_back(N); 3093 return; 3094 } 3095 3096 if (N->getChild(0)->isLeaf() || N->getChild(0)->getOperator() != Operator) 3097 Children.push_back(N->getChild(0)); 3098 else 3099 GatherChildrenOfAssociativeOpcode(N->getChild(0), Children); 3100 3101 if (N->getChild(1)->isLeaf() || N->getChild(1)->getOperator() != Operator) 3102 Children.push_back(N->getChild(1)); 3103 else 3104 GatherChildrenOfAssociativeOpcode(N->getChild(1), Children); 3105 } 3106 3107 /// GenerateVariantsOf - Given a pattern N, generate all permutations we can of 3108 /// the (potentially recursive) pattern by using algebraic laws. 3109 /// 3110 static void GenerateVariantsOf(TreePatternNode *N, 3111 std::vector<TreePatternNode*> &OutVariants, 3112 CodeGenDAGPatterns &CDP, 3113 const MultipleUseVarSet &DepVars) { 3114 // We cannot permute leaves. 3115 if (N->isLeaf()) { 3116 OutVariants.push_back(N); 3117 return; 3118 } 3119 3120 // Look up interesting info about the node. 3121 const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(N->getOperator()); 3122 3123 // If this node is associative, re-associate. 3124 if (NodeInfo.hasProperty(SDNPAssociative)) { 3125 // Re-associate by pulling together all of the linked operators 3126 std::vector<TreePatternNode*> MaximalChildren; 3127 GatherChildrenOfAssociativeOpcode(N, MaximalChildren); 3128 3129 // Only handle child sizes of 3. Otherwise we'll end up trying too many 3130 // permutations. 3131 if (MaximalChildren.size() == 3) { 3132 // Find the variants of all of our maximal children. 3133 std::vector<TreePatternNode*> AVariants, BVariants, CVariants; 3134 GenerateVariantsOf(MaximalChildren[0], AVariants, CDP, DepVars); 3135 GenerateVariantsOf(MaximalChildren[1], BVariants, CDP, DepVars); 3136 GenerateVariantsOf(MaximalChildren[2], CVariants, CDP, DepVars); 3137 3138 // There are only two ways we can permute the tree: 3139 // (A op B) op C and A op (B op C) 3140 // Within these forms, we can also permute A/B/C. 3141 3142 // Generate legal pair permutations of A/B/C. 3143 std::vector<TreePatternNode*> ABVariants; 3144 std::vector<TreePatternNode*> BAVariants; 3145 std::vector<TreePatternNode*> ACVariants; 3146 std::vector<TreePatternNode*> CAVariants; 3147 std::vector<TreePatternNode*> BCVariants; 3148 std::vector<TreePatternNode*> CBVariants; 3149 CombineChildVariants(N, AVariants, BVariants, ABVariants, CDP, DepVars); 3150 CombineChildVariants(N, BVariants, AVariants, BAVariants, CDP, DepVars); 3151 CombineChildVariants(N, AVariants, CVariants, ACVariants, CDP, DepVars); 3152 CombineChildVariants(N, CVariants, AVariants, CAVariants, CDP, DepVars); 3153 CombineChildVariants(N, BVariants, CVariants, BCVariants, CDP, DepVars); 3154 CombineChildVariants(N, CVariants, BVariants, CBVariants, CDP, DepVars); 3155 3156 // Combine those into the result: (x op x) op x 3157 CombineChildVariants(N, ABVariants, CVariants, OutVariants, CDP, DepVars); 3158 CombineChildVariants(N, BAVariants, CVariants, OutVariants, CDP, DepVars); 3159 CombineChildVariants(N, ACVariants, BVariants, OutVariants, CDP, DepVars); 3160 CombineChildVariants(N, CAVariants, BVariants, OutVariants, CDP, DepVars); 3161 CombineChildVariants(N, BCVariants, AVariants, OutVariants, CDP, DepVars); 3162 CombineChildVariants(N, CBVariants, AVariants, OutVariants, CDP, DepVars); 3163 3164 // Combine those into the result: x op (x op x) 3165 CombineChildVariants(N, CVariants, ABVariants, OutVariants, CDP, DepVars); 3166 CombineChildVariants(N, CVariants, BAVariants, OutVariants, CDP, DepVars); 3167 CombineChildVariants(N, BVariants, ACVariants, OutVariants, CDP, DepVars); 3168 CombineChildVariants(N, BVariants, CAVariants, OutVariants, CDP, DepVars); 3169 CombineChildVariants(N, AVariants, BCVariants, OutVariants, CDP, DepVars); 3170 CombineChildVariants(N, AVariants, CBVariants, OutVariants, CDP, DepVars); 3171 return; 3172 } 3173 } 3174 3175 // Compute permutations of all children. 3176 std::vector<std::vector<TreePatternNode*> > ChildVariants; 3177 ChildVariants.resize(N->getNumChildren()); 3178 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 3179 GenerateVariantsOf(N->getChild(i), ChildVariants[i], CDP, DepVars); 3180 3181 // Build all permutations based on how the children were formed. 3182 CombineChildVariants(N, ChildVariants, OutVariants, CDP, DepVars); 3183 3184 // If this node is commutative, consider the commuted order. 3185 bool isCommIntrinsic = N->isCommutativeIntrinsic(CDP); 3186 if (NodeInfo.hasProperty(SDNPCommutative) || isCommIntrinsic) { 3187 assert((N->getNumChildren()==2 || isCommIntrinsic) && 3188 "Commutative but doesn't have 2 children!"); 3189 // Don't count children which are actually register references. 3190 unsigned NC = 0; 3191 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { 3192 TreePatternNode *Child = N->getChild(i); 3193 if (Child->isLeaf()) 3194 if (DefInit *DI = dynamic_cast<DefInit*>(Child->getLeafValue())) { 3195 Record *RR = DI->getDef(); 3196 if (RR->isSubClassOf("Register")) 3197 continue; 3198 } 3199 NC++; 3200 } 3201 // Consider the commuted order. 3202 if (isCommIntrinsic) { 3203 // Commutative intrinsic. First operand is the intrinsic id, 2nd and 3rd 3204 // operands are the commutative operands, and there might be more operands 3205 // after those. 3206 assert(NC >= 3 && 3207 "Commutative intrinsic should have at least 3 childrean!"); 3208 std::vector<std::vector<TreePatternNode*> > Variants; 3209 Variants.push_back(ChildVariants[0]); // Intrinsic id. 3210 Variants.push_back(ChildVariants[2]); 3211 Variants.push_back(ChildVariants[1]); 3212 for (unsigned i = 3; i != NC; ++i) 3213 Variants.push_back(ChildVariants[i]); 3214 CombineChildVariants(N, Variants, OutVariants, CDP, DepVars); 3215 } else if (NC == 2) 3216 CombineChildVariants(N, ChildVariants[1], ChildVariants[0], 3217 OutVariants, CDP, DepVars); 3218 } 3219 } 3220 3221 3222 // GenerateVariants - Generate variants. For example, commutative patterns can 3223 // match multiple ways. Add them to PatternsToMatch as well. 3224 void CodeGenDAGPatterns::GenerateVariants() { 3225 DEBUG(errs() << "Generating instruction variants.\n"); 3226 3227 // Loop over all of the patterns we've collected, checking to see if we can 3228 // generate variants of the instruction, through the exploitation of 3229 // identities. This permits the target to provide aggressive matching without 3230 // the .td file having to contain tons of variants of instructions. 3231 // 3232 // Note that this loop adds new patterns to the PatternsToMatch list, but we 3233 // intentionally do not reconsider these. Any variants of added patterns have 3234 // already been added. 3235 // 3236 for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) { 3237 MultipleUseVarSet DepVars; 3238 std::vector<TreePatternNode*> Variants; 3239 FindDepVars(PatternsToMatch[i].getSrcPattern(), DepVars); 3240 DEBUG(errs() << "Dependent/multiply used variables: "); 3241 DEBUG(DumpDepVars(DepVars)); 3242 DEBUG(errs() << "\n"); 3243 GenerateVariantsOf(PatternsToMatch[i].getSrcPattern(), Variants, *this, 3244 DepVars); 3245 3246 assert(!Variants.empty() && "Must create at least original variant!"); 3247 Variants.erase(Variants.begin()); // Remove the original pattern. 3248 3249 if (Variants.empty()) // No variants for this pattern. 3250 continue; 3251 3252 DEBUG(errs() << "FOUND VARIANTS OF: "; 3253 PatternsToMatch[i].getSrcPattern()->dump(); 3254 errs() << "\n"); 3255 3256 for (unsigned v = 0, e = Variants.size(); v != e; ++v) { 3257 TreePatternNode *Variant = Variants[v]; 3258 3259 DEBUG(errs() << " VAR#" << v << ": "; 3260 Variant->dump(); 3261 errs() << "\n"); 3262 3263 // Scan to see if an instruction or explicit pattern already matches this. 3264 bool AlreadyExists = false; 3265 for (unsigned p = 0, e = PatternsToMatch.size(); p != e; ++p) { 3266 // Skip if the top level predicates do not match. 3267 if (PatternsToMatch[i].getPredicates() != 3268 PatternsToMatch[p].getPredicates()) 3269 continue; 3270 // Check to see if this variant already exists. 3271 if (Variant->isIsomorphicTo(PatternsToMatch[p].getSrcPattern(), 3272 DepVars)) { 3273 DEBUG(errs() << " *** ALREADY EXISTS, ignoring variant.\n"); 3274 AlreadyExists = true; 3275 break; 3276 } 3277 } 3278 // If we already have it, ignore the variant. 3279 if (AlreadyExists) continue; 3280 3281 // Otherwise, add it to the list of patterns we have. 3282 PatternsToMatch. 3283 push_back(PatternToMatch(PatternsToMatch[i].getSrcRecord(), 3284 PatternsToMatch[i].getPredicates(), 3285 Variant, PatternsToMatch[i].getDstPattern(), 3286 PatternsToMatch[i].getDstRegs(), 3287 PatternsToMatch[i].getAddedComplexity(), 3288 Record::getNewUID())); 3289 } 3290 3291 DEBUG(errs() << "\n"); 3292 } 3293 } 3294 3295