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