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