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