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