CodeGenDAGPatterns.cpp revision 205407
1260684Skaiw//===- CodeGenDAGPatterns.cpp - Read DAG patterns from .td file -----------===// 2260684Skaiw// 3260684Skaiw// The LLVM Compiler Infrastructure 4260684Skaiw// 5260684Skaiw// This file is distributed under the University of Illinois Open Source 6260684Skaiw// License. See LICENSE.TXT for details. 7260684Skaiw// 8260684Skaiw//===----------------------------------------------------------------------===// 9260684Skaiw// 10260684Skaiw// This file implements the CodeGenDAGPatterns class, which is used to read and 11260684Skaiw// represent the patterns present in a .td file for instructions. 12260684Skaiw// 13260684Skaiw//===----------------------------------------------------------------------===// 14260684Skaiw 15260684Skaiw#include "CodeGenDAGPatterns.h" 16260684Skaiw#include "Record.h" 17260684Skaiw#include "llvm/ADT/StringExtras.h" 18260684Skaiw#include "llvm/ADT/STLExtras.h" 19260684Skaiw#include "llvm/Support/Debug.h" 20260684Skaiw#include <set> 21260684Skaiw#include <algorithm> 22260684Skaiwusing namespace llvm; 23260684Skaiw 24260684Skaiw//===----------------------------------------------------------------------===// 25260684Skaiw// EEVT::TypeSet Implementation 26260684Skaiw//===----------------------------------------------------------------------===// 27260684Skaiw 28260684Skaiwstatic inline bool isInteger(MVT::SimpleValueType VT) { 29298361Semaste return EVT(VT).isInteger(); 30260684Skaiw} 31260684Skaiwstatic inline bool isFloatingPoint(MVT::SimpleValueType VT) { 32260684Skaiw return EVT(VT).isFloatingPoint(); 33260684Skaiw} 34260684Skaiwstatic inline bool isVector(MVT::SimpleValueType VT) { 35260684Skaiw return EVT(VT).isVector(); 36260684Skaiw} 37260684Skaiwstatic inline bool isScalar(MVT::SimpleValueType VT) { 38260684Skaiw return !EVT(VT).isVector(); 39300311Semaste} 40260684Skaiw 41260684SkaiwEEVT::TypeSet::TypeSet(MVT::SimpleValueType VT, TreePattern &TP) { 42260684Skaiw if (VT == MVT::iAny) 43260684Skaiw EnforceInteger(TP); 44260684Skaiw else if (VT == MVT::fAny) 45260684Skaiw EnforceFloatingPoint(TP); 46260684Skaiw else if (VT == MVT::vAny) 47260684Skaiw EnforceVector(TP); 48260684Skaiw else { 49260684Skaiw assert((VT < MVT::LAST_VALUETYPE || VT == MVT::iPTR || 50260684Skaiw VT == MVT::iPTRAny) && "Not a concrete type!"); 51260684Skaiw TypeVec.push_back(VT); 52260684Skaiw } 53260684Skaiw} 54260684Skaiw 55260684Skaiw 56260684SkaiwEEVT::TypeSet::TypeSet(const std::vector<MVT::SimpleValueType> &VTList) { 57260684Skaiw assert(!VTList.empty() && "empty list?"); 58260684Skaiw TypeVec.append(VTList.begin(), VTList.end()); 59260684Skaiw 60260684Skaiw if (!VTList.empty()) 61260684Skaiw assert(VTList[0] != MVT::iAny && VTList[0] != MVT::vAny && 62260684Skaiw VTList[0] != MVT::fAny); 63260684Skaiw 64260684Skaiw // Remove duplicates. 65260684Skaiw array_pod_sort(TypeVec.begin(), TypeVec.end()); 66260684Skaiw TypeVec.erase(std::unique(TypeVec.begin(), TypeVec.end()), TypeVec.end()); 67260684Skaiw} 68260684Skaiw 69260684Skaiw/// FillWithPossibleTypes - Set to all legal types and return true, only valid 70260684Skaiw/// on completely unknown type sets. 71260684Skaiwbool EEVT::TypeSet::FillWithPossibleTypes(TreePattern &TP, 72260684Skaiw bool (*Pred)(MVT::SimpleValueType), 73260684Skaiw const char *PredicateName) { 74260684Skaiw assert(isCompletelyUnknown()); 75260684Skaiw const std::vector<MVT::SimpleValueType> &LegalTypes = 76260684Skaiw TP.getDAGPatterns().getTargetInfo().getLegalValueTypes(); 77260684Skaiw 78260684Skaiw for (unsigned i = 0, e = LegalTypes.size(); i != e; ++i) 79260684Skaiw if (Pred == 0 || Pred(LegalTypes[i])) 80260684Skaiw TypeVec.push_back(LegalTypes[i]); 81260684Skaiw 82260684Skaiw // If we have nothing that matches the predicate, bail out. 83260684Skaiw if (TypeVec.empty()) 84260684Skaiw TP.error("Type inference contradiction found, no " + 85260684Skaiw std::string(PredicateName) + " types found"); 86260684Skaiw // No need to sort with one element. 87260684Skaiw if (TypeVec.size() == 1) return true; 88260684Skaiw 89260684Skaiw // Remove duplicates. 90260684Skaiw array_pod_sort(TypeVec.begin(), TypeVec.end()); 91260684Skaiw TypeVec.erase(std::unique(TypeVec.begin(), TypeVec.end()), TypeVec.end()); 92260684Skaiw 93260684Skaiw return true; 94260684Skaiw} 95260684Skaiw 96260684Skaiw/// hasIntegerTypes - Return true if this TypeSet contains iAny or an 97260684Skaiw/// integer value type. 98260684Skaiwbool EEVT::TypeSet::hasIntegerTypes() const { 99260684Skaiw for (unsigned i = 0, e = TypeVec.size(); i != e; ++i) 100260684Skaiw if (isInteger(TypeVec[i])) 101260684Skaiw return true; 102260684Skaiw return false; 103260684Skaiw} 104260684Skaiw 105260684Skaiw/// hasFloatingPointTypes - Return true if this TypeSet contains an fAny or 106260684Skaiw/// a floating point value type. 107260684Skaiwbool EEVT::TypeSet::hasFloatingPointTypes() const { 108260684Skaiw for (unsigned i = 0, e = TypeVec.size(); i != e; ++i) 109260684Skaiw if (isFloatingPoint(TypeVec[i])) 110260684Skaiw return true; 111260684Skaiw return false; 112260684Skaiw} 113260684Skaiw 114260684Skaiw/// hasVectorTypes - Return true if this TypeSet contains a vAny or a vector 115260684Skaiw/// value type. 116260684Skaiwbool EEVT::TypeSet::hasVectorTypes() const { 117260684Skaiw for (unsigned i = 0, e = TypeVec.size(); i != e; ++i) 118260684Skaiw if (isVector(TypeVec[i])) 119260684Skaiw return true; 120260684Skaiw return false; 121260684Skaiw} 122260684Skaiw 123260684Skaiw 124260684Skaiwstd::string EEVT::TypeSet::getName() const { 125260684Skaiw if (TypeVec.empty()) return "<empty>"; 126260684Skaiw 127260684Skaiw std::string Result; 128260684Skaiw 129260684Skaiw for (unsigned i = 0, e = TypeVec.size(); i != e; ++i) { 130260684Skaiw std::string VTName = llvm::getEnumName(TypeVec[i]); 131260684Skaiw // Strip off MVT:: prefix if present. 132260684Skaiw if (VTName.substr(0,5) == "MVT::") 133260684Skaiw VTName = VTName.substr(5); 134260684Skaiw if (i) Result += ':'; 135260684Skaiw Result += VTName; 136260684Skaiw } 137260684Skaiw 138260684Skaiw if (TypeVec.size() == 1) 139260684Skaiw return Result; 140260684Skaiw return "{" + Result + "}"; 141260684Skaiw} 142260684Skaiw 143260684Skaiw/// MergeInTypeInfo - This merges in type information from the specified 144292116Semaste/// argument. If 'this' changes, it returns true. If the two types are 145260684Skaiw/// contradictory (e.g. merge f32 into i32) then this throws an exception. 146260684Skaiwbool EEVT::TypeSet::MergeInTypeInfo(const EEVT::TypeSet &InVT, TreePattern &TP){ 147260684Skaiw if (InVT.isCompletelyUnknown() || *this == InVT) 148260684Skaiw return false; 149260684Skaiw 150260684Skaiw if (isCompletelyUnknown()) { 151260684Skaiw *this = InVT; 152260684Skaiw return true; 153260684Skaiw } 154260684Skaiw 155260684Skaiw assert(TypeVec.size() >= 1 && InVT.TypeVec.size() >= 1 && "No unknowns"); 156260684Skaiw 157260684Skaiw // Handle the abstract cases, seeing if we can resolve them better. 158260684Skaiw switch (TypeVec[0]) { 159260684Skaiw default: break; 160260684Skaiw case MVT::iPTR: 161260684Skaiw case MVT::iPTRAny: 162260684Skaiw if (InVT.hasIntegerTypes()) { 163260684Skaiw EEVT::TypeSet InCopy(InVT); 164260684Skaiw InCopy.EnforceInteger(TP); 165260684Skaiw InCopy.EnforceScalar(TP); 166260684Skaiw 167260684Skaiw if (InCopy.isConcrete()) { 168260684Skaiw // If the RHS has one integer type, upgrade iPTR to i32. 169260684Skaiw TypeVec[0] = InVT.TypeVec[0]; 170260684Skaiw return true; 171260684Skaiw } 172260684Skaiw 173260684Skaiw // If the input has multiple scalar integers, this doesn't add any info. 174260684Skaiw if (!InCopy.isCompletelyUnknown()) 175260684Skaiw return false; 176260684Skaiw } 177260684Skaiw break; 178260684Skaiw } 179260684Skaiw 180260684Skaiw // If the input constraint is iAny/iPTR and this is an integer type list, 181260684Skaiw // remove non-integer types from the list. 182260684Skaiw if ((InVT.TypeVec[0] == MVT::iPTR || InVT.TypeVec[0] == MVT::iPTRAny) && 183260684Skaiw hasIntegerTypes()) { 184260684Skaiw bool MadeChange = EnforceInteger(TP); 185260684Skaiw 186260684Skaiw // If we're merging in iPTR/iPTRAny and the node currently has a list of 187260684Skaiw // multiple different integer types, replace them with a single iPTR. 188260684Skaiw if ((InVT.TypeVec[0] == MVT::iPTR || InVT.TypeVec[0] == MVT::iPTRAny) && 189260684Skaiw TypeVec.size() != 1) { 190260684Skaiw TypeVec.resize(1); 191260684Skaiw TypeVec[0] = InVT.TypeVec[0]; 192260684Skaiw MadeChange = true; 193260684Skaiw } 194260684Skaiw 195260684Skaiw return MadeChange; 196260684Skaiw } 197260684Skaiw 198260684Skaiw // If this is a type list and the RHS is a typelist as well, eliminate entries 199260684Skaiw // from this list that aren't in the other one. 200260684Skaiw bool MadeChange = false; 201260684Skaiw TypeSet InputSet(*this); 202260684Skaiw 203260684Skaiw for (unsigned i = 0; i != TypeVec.size(); ++i) { 204260684Skaiw bool InInVT = false; 205260684Skaiw for (unsigned j = 0, e = InVT.TypeVec.size(); j != e; ++j) 206260684Skaiw if (TypeVec[i] == InVT.TypeVec[j]) { 207260684Skaiw InInVT = true; 208260684Skaiw break; 209260684Skaiw } 210260684Skaiw 211260684Skaiw if (InInVT) continue; 212260684Skaiw TypeVec.erase(TypeVec.begin()+i--); 213260684Skaiw MadeChange = true; 214260684Skaiw } 215292116Semaste 216292116Semaste // If we removed all of our types, we have a type contradiction. 217298361Semaste if (!TypeVec.empty()) 218298361Semaste return MadeChange; 219298361Semaste 220260684Skaiw // FIXME: Really want an SMLoc here! 221292116Semaste TP.error("Type inference contradiction found, merging '" + 222260684Skaiw InVT.getName() + "' into '" + InputSet.getName() + "'"); 223260684Skaiw return true; // unreachable 224260684Skaiw} 225260684Skaiw 226260684Skaiw/// EnforceInteger - Remove all non-integer types from this set. 227260684Skaiwbool EEVT::TypeSet::EnforceInteger(TreePattern &TP) { 228260684Skaiw // If we know nothing, then get the full set. 229260684Skaiw if (TypeVec.empty()) 230260684Skaiw return FillWithPossibleTypes(TP, isInteger, "integer"); 231260684Skaiw if (!hasFloatingPointTypes()) 232260684Skaiw return false; 233260684Skaiw 234260684Skaiw TypeSet InputSet(*this); 235260684Skaiw 236260684Skaiw // Filter out all the fp types. 237260684Skaiw for (unsigned i = 0; i != TypeVec.size(); ++i) 238260684Skaiw if (!isInteger(TypeVec[i])) 239260684Skaiw TypeVec.erase(TypeVec.begin()+i--); 240260684Skaiw 241260684Skaiw if (TypeVec.empty()) 242260684Skaiw TP.error("Type inference contradiction found, '" + 243292116Semaste InputSet.getName() + "' needs to be integer"); 244260684Skaiw return true; 245260684Skaiw} 246260684Skaiw 247260684Skaiw/// EnforceFloatingPoint - Remove all integer types from this set. 248260684Skaiwbool EEVT::TypeSet::EnforceFloatingPoint(TreePattern &TP) { 249260684Skaiw // If we know nothing, then get the full set. 250260684Skaiw if (TypeVec.empty()) 251260684Skaiw return FillWithPossibleTypes(TP, isFloatingPoint, "floating point"); 252260684Skaiw 253260684Skaiw if (!hasIntegerTypes()) 254260684Skaiw return false; 255260684Skaiw 256260684Skaiw TypeSet InputSet(*this); 257260684Skaiw 258260684Skaiw // Filter out all the fp types. 259260684Skaiw for (unsigned i = 0; i != TypeVec.size(); ++i) 260260684Skaiw if (!isFloatingPoint(TypeVec[i])) 261260684Skaiw TypeVec.erase(TypeVec.begin()+i--); 262260684Skaiw 263260684Skaiw if (TypeVec.empty()) 264260684Skaiw TP.error("Type inference contradiction found, '" + 265260684Skaiw InputSet.getName() + "' needs to be floating point"); 266260684Skaiw return true; 267260684Skaiw} 268260684Skaiw 269260684Skaiw/// EnforceScalar - Remove all vector types from this. 270260684Skaiwbool EEVT::TypeSet::EnforceScalar(TreePattern &TP) { 271260684Skaiw // If we know nothing, then get the full set. 272260684Skaiw if (TypeVec.empty()) 273260684Skaiw return FillWithPossibleTypes(TP, isScalar, "scalar"); 274260684Skaiw 275260684Skaiw if (!hasVectorTypes()) 276260684Skaiw return false; 277260684Skaiw 278260684Skaiw TypeSet InputSet(*this); 279260684Skaiw 280260684Skaiw // Filter out all the vector types. 281260684Skaiw for (unsigned i = 0; i != TypeVec.size(); ++i) 282260684Skaiw if (!isScalar(TypeVec[i])) 283260684Skaiw TypeVec.erase(TypeVec.begin()+i--); 284260684Skaiw 285260684Skaiw if (TypeVec.empty()) 286260684Skaiw TP.error("Type inference contradiction found, '" + 287260684Skaiw InputSet.getName() + "' needs to be scalar"); 288260684Skaiw return true; 289260684Skaiw} 290260684Skaiw 291260684Skaiw/// EnforceVector - Remove all vector types from this. 292260684Skaiwbool EEVT::TypeSet::EnforceVector(TreePattern &TP) { 293260684Skaiw // If we know nothing, then get the full set. 294 if (TypeVec.empty()) 295 return FillWithPossibleTypes(TP, isVector, "vector"); 296 297 TypeSet InputSet(*this); 298 bool MadeChange = false; 299 300 // Filter out all the scalar types. 301 for (unsigned i = 0; i != TypeVec.size(); ++i) 302 if (!isVector(TypeVec[i])) { 303 TypeVec.erase(TypeVec.begin()+i--); 304 MadeChange = true; 305 } 306 307 if (TypeVec.empty()) 308 TP.error("Type inference contradiction found, '" + 309 InputSet.getName() + "' needs to be a vector"); 310 return MadeChange; 311} 312 313 314 315/// EnforceSmallerThan - 'this' must be a smaller VT than Other. Update 316/// this an other based on this information. 317bool EEVT::TypeSet::EnforceSmallerThan(EEVT::TypeSet &Other, TreePattern &TP) { 318 // Both operands must be integer or FP, but we don't care which. 319 bool MadeChange = false; 320 321 if (isCompletelyUnknown()) 322 MadeChange = FillWithPossibleTypes(TP); 323 324 if (Other.isCompletelyUnknown()) 325 MadeChange = Other.FillWithPossibleTypes(TP); 326 327 // If one side is known to be integer or known to be FP but the other side has 328 // no information, get at least the type integrality info in there. 329 if (!hasFloatingPointTypes()) 330 MadeChange |= Other.EnforceInteger(TP); 331 else if (!hasIntegerTypes()) 332 MadeChange |= Other.EnforceFloatingPoint(TP); 333 if (!Other.hasFloatingPointTypes()) 334 MadeChange |= EnforceInteger(TP); 335 else if (!Other.hasIntegerTypes()) 336 MadeChange |= EnforceFloatingPoint(TP); 337 338 assert(!isCompletelyUnknown() && !Other.isCompletelyUnknown() && 339 "Should have a type list now"); 340 341 // If one contains vectors but the other doesn't pull vectors out. 342 if (!hasVectorTypes()) 343 MadeChange |= Other.EnforceScalar(TP); 344 if (!hasVectorTypes()) 345 MadeChange |= EnforceScalar(TP); 346 347 // This code does not currently handle nodes which have multiple types, 348 // where some types are integer, and some are fp. Assert that this is not 349 // the case. 350 assert(!(hasIntegerTypes() && hasFloatingPointTypes()) && 351 !(Other.hasIntegerTypes() && Other.hasFloatingPointTypes()) && 352 "SDTCisOpSmallerThanOp does not handle mixed int/fp types!"); 353 354 // Okay, find the smallest type from the current set and remove it from the 355 // largest set. 356 MVT::SimpleValueType Smallest = TypeVec[0]; 357 for (unsigned i = 1, e = TypeVec.size(); i != e; ++i) 358 if (TypeVec[i] < Smallest) 359 Smallest = TypeVec[i]; 360 361 // If this is the only type in the large set, the constraint can never be 362 // satisfied. 363 if (Other.TypeVec.size() == 1 && Other.TypeVec[0] == Smallest) 364 TP.error("Type inference contradiction found, '" + 365 Other.getName() + "' has nothing larger than '" + getName() +"'!"); 366 367 SmallVector<MVT::SimpleValueType, 2>::iterator TVI = 368 std::find(Other.TypeVec.begin(), Other.TypeVec.end(), Smallest); 369 if (TVI != Other.TypeVec.end()) { 370 Other.TypeVec.erase(TVI); 371 MadeChange = true; 372 } 373 374 // Okay, find the largest type in the Other set and remove it from the 375 // current set. 376 MVT::SimpleValueType Largest = Other.TypeVec[0]; 377 for (unsigned i = 1, e = Other.TypeVec.size(); i != e; ++i) 378 if (Other.TypeVec[i] > Largest) 379 Largest = Other.TypeVec[i]; 380 381 // If this is the only type in the small set, the constraint can never be 382 // satisfied. 383 if (TypeVec.size() == 1 && TypeVec[0] == Largest) 384 TP.error("Type inference contradiction found, '" + 385 getName() + "' has nothing smaller than '" + Other.getName()+"'!"); 386 387 TVI = std::find(TypeVec.begin(), TypeVec.end(), Largest); 388 if (TVI != TypeVec.end()) { 389 TypeVec.erase(TVI); 390 MadeChange = true; 391 } 392 393 return MadeChange; 394} 395 396/// EnforceVectorEltTypeIs - 'this' is now constrainted to be a vector type 397/// whose element is VT. 398bool EEVT::TypeSet::EnforceVectorEltTypeIs(MVT::SimpleValueType VT, 399 TreePattern &TP) { 400 TypeSet InputSet(*this); 401 bool MadeChange = false; 402 403 // If we know nothing, then get the full set. 404 if (TypeVec.empty()) 405 MadeChange = FillWithPossibleTypes(TP, isVector, "vector"); 406 407 // Filter out all the non-vector types and types which don't have the right 408 // element type. 409 for (unsigned i = 0; i != TypeVec.size(); ++i) 410 if (!isVector(TypeVec[i]) || 411 EVT(TypeVec[i]).getVectorElementType().getSimpleVT().SimpleTy != VT) { 412 TypeVec.erase(TypeVec.begin()+i--); 413 MadeChange = true; 414 } 415 416 if (TypeVec.empty()) // FIXME: Really want an SMLoc here! 417 TP.error("Type inference contradiction found, forcing '" + 418 InputSet.getName() + "' to have a vector element"); 419 return MadeChange; 420} 421 422//===----------------------------------------------------------------------===// 423// Helpers for working with extended types. 424 425bool RecordPtrCmp::operator()(const Record *LHS, const Record *RHS) const { 426 return LHS->getID() < RHS->getID(); 427} 428 429/// Dependent variable map for CodeGenDAGPattern variant generation 430typedef std::map<std::string, int> DepVarMap; 431 432/// Const iterator shorthand for DepVarMap 433typedef DepVarMap::const_iterator DepVarMap_citer; 434 435namespace { 436void FindDepVarsOf(TreePatternNode *N, DepVarMap &DepMap) { 437 if (N->isLeaf()) { 438 if (dynamic_cast<DefInit*>(N->getLeafValue()) != NULL) { 439 DepMap[N->getName()]++; 440 } 441 } else { 442 for (size_t i = 0, e = N->getNumChildren(); i != e; ++i) 443 FindDepVarsOf(N->getChild(i), DepMap); 444 } 445} 446 447//! Find dependent variables within child patterns 448/*! 449 */ 450void FindDepVars(TreePatternNode *N, MultipleUseVarSet &DepVars) { 451 DepVarMap depcounts; 452 FindDepVarsOf(N, depcounts); 453 for (DepVarMap_citer i = depcounts.begin(); i != depcounts.end(); ++i) { 454 if (i->second > 1) { // std::pair<std::string, int> 455 DepVars.insert(i->first); 456 } 457 } 458} 459 460//! Dump the dependent variable set: 461void DumpDepVars(MultipleUseVarSet &DepVars) { 462 if (DepVars.empty()) { 463 DEBUG(errs() << "<empty set>"); 464 } else { 465 DEBUG(errs() << "[ "); 466 for (MultipleUseVarSet::const_iterator i = DepVars.begin(), e = DepVars.end(); 467 i != e; ++i) { 468 DEBUG(errs() << (*i) << " "); 469 } 470 DEBUG(errs() << "]"); 471 } 472} 473} 474 475//===----------------------------------------------------------------------===// 476// PatternToMatch implementation 477// 478 479/// getPredicateCheck - Return a single string containing all of this 480/// pattern's predicates concatenated with "&&" operators. 481/// 482std::string PatternToMatch::getPredicateCheck() const { 483 std::string PredicateCheck; 484 for (unsigned i = 0, e = Predicates->getSize(); i != e; ++i) { 485 if (DefInit *Pred = dynamic_cast<DefInit*>(Predicates->getElement(i))) { 486 Record *Def = Pred->getDef(); 487 if (!Def->isSubClassOf("Predicate")) { 488#ifndef NDEBUG 489 Def->dump(); 490#endif 491 assert(0 && "Unknown predicate type!"); 492 } 493 if (!PredicateCheck.empty()) 494 PredicateCheck += " && "; 495 PredicateCheck += "(" + Def->getValueAsString("CondString") + ")"; 496 } 497 } 498 499 return PredicateCheck; 500} 501 502//===----------------------------------------------------------------------===// 503// SDTypeConstraint implementation 504// 505 506SDTypeConstraint::SDTypeConstraint(Record *R) { 507 OperandNo = R->getValueAsInt("OperandNum"); 508 509 if (R->isSubClassOf("SDTCisVT")) { 510 ConstraintType = SDTCisVT; 511 x.SDTCisVT_Info.VT = getValueType(R->getValueAsDef("VT")); 512 } else if (R->isSubClassOf("SDTCisPtrTy")) { 513 ConstraintType = SDTCisPtrTy; 514 } else if (R->isSubClassOf("SDTCisInt")) { 515 ConstraintType = SDTCisInt; 516 } else if (R->isSubClassOf("SDTCisFP")) { 517 ConstraintType = SDTCisFP; 518 } else if (R->isSubClassOf("SDTCisVec")) { 519 ConstraintType = SDTCisVec; 520 } else if (R->isSubClassOf("SDTCisSameAs")) { 521 ConstraintType = SDTCisSameAs; 522 x.SDTCisSameAs_Info.OtherOperandNum = R->getValueAsInt("OtherOperandNum"); 523 } else if (R->isSubClassOf("SDTCisVTSmallerThanOp")) { 524 ConstraintType = SDTCisVTSmallerThanOp; 525 x.SDTCisVTSmallerThanOp_Info.OtherOperandNum = 526 R->getValueAsInt("OtherOperandNum"); 527 } else if (R->isSubClassOf("SDTCisOpSmallerThanOp")) { 528 ConstraintType = SDTCisOpSmallerThanOp; 529 x.SDTCisOpSmallerThanOp_Info.BigOperandNum = 530 R->getValueAsInt("BigOperandNum"); 531 } else if (R->isSubClassOf("SDTCisEltOfVec")) { 532 ConstraintType = SDTCisEltOfVec; 533 x.SDTCisEltOfVec_Info.OtherOperandNum = R->getValueAsInt("OtherOpNum"); 534 } else { 535 errs() << "Unrecognized SDTypeConstraint '" << R->getName() << "'!\n"; 536 exit(1); 537 } 538} 539 540/// getOperandNum - Return the node corresponding to operand #OpNo in tree 541/// N, and the result number in ResNo. 542static TreePatternNode *getOperandNum(unsigned OpNo, TreePatternNode *N, 543 const SDNodeInfo &NodeInfo, 544 unsigned &ResNo) { 545 unsigned NumResults = NodeInfo.getNumResults(); 546 if (OpNo < NumResults) { 547 ResNo = OpNo; 548 return N; 549 } 550 551 OpNo -= NumResults; 552 553 if (OpNo >= N->getNumChildren()) { 554 errs() << "Invalid operand number in type constraint " 555 << (OpNo+NumResults) << " "; 556 N->dump(); 557 errs() << '\n'; 558 exit(1); 559 } 560 561 return N->getChild(OpNo); 562} 563 564/// ApplyTypeConstraint - Given a node in a pattern, apply this type 565/// constraint to the nodes operands. This returns true if it makes a 566/// change, false otherwise. If a type contradiction is found, throw an 567/// exception. 568bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, 569 const SDNodeInfo &NodeInfo, 570 TreePattern &TP) const { 571 // Check that the number of operands is sane. Negative operands -> varargs. 572 if (NodeInfo.getNumOperands() >= 0) { 573 if (N->getNumChildren() != (unsigned)NodeInfo.getNumOperands()) 574 TP.error(N->getOperator()->getName() + " node requires exactly " + 575 itostr(NodeInfo.getNumOperands()) + " operands!"); 576 } 577 578 unsigned ResNo = 0; // The result number being referenced. 579 TreePatternNode *NodeToApply = getOperandNum(OperandNo, N, NodeInfo, ResNo); 580 581 switch (ConstraintType) { 582 default: assert(0 && "Unknown constraint type!"); 583 case SDTCisVT: 584 // Operand must be a particular type. 585 return NodeToApply->UpdateNodeType(ResNo, x.SDTCisVT_Info.VT, TP); 586 case SDTCisPtrTy: 587 // Operand must be same as target pointer type. 588 return NodeToApply->UpdateNodeType(ResNo, MVT::iPTR, TP); 589 case SDTCisInt: 590 // Require it to be one of the legal integer VTs. 591 return NodeToApply->getExtType(ResNo).EnforceInteger(TP); 592 case SDTCisFP: 593 // Require it to be one of the legal fp VTs. 594 return NodeToApply->getExtType(ResNo).EnforceFloatingPoint(TP); 595 case SDTCisVec: 596 // Require it to be one of the legal vector VTs. 597 return NodeToApply->getExtType(ResNo).EnforceVector(TP); 598 case SDTCisSameAs: { 599 unsigned OResNo = 0; 600 TreePatternNode *OtherNode = 601 getOperandNum(x.SDTCisSameAs_Info.OtherOperandNum, N, NodeInfo, OResNo); 602 return NodeToApply->UpdateNodeType(OResNo, OtherNode->getExtType(ResNo),TP)| 603 OtherNode->UpdateNodeType(ResNo,NodeToApply->getExtType(OResNo),TP); 604 } 605 case SDTCisVTSmallerThanOp: { 606 // The NodeToApply must be a leaf node that is a VT. OtherOperandNum must 607 // have an integer type that is smaller than the VT. 608 if (!NodeToApply->isLeaf() || 609 !dynamic_cast<DefInit*>(NodeToApply->getLeafValue()) || 610 !static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef() 611 ->isSubClassOf("ValueType")) 612 TP.error(N->getOperator()->getName() + " expects a VT operand!"); 613 MVT::SimpleValueType VT = 614 getValueType(static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef()); 615 if (!isInteger(VT)) 616 TP.error(N->getOperator()->getName() + " VT operand must be integer!"); 617 618 unsigned OResNo = 0; 619 TreePatternNode *OtherNode = 620 getOperandNum(x.SDTCisVTSmallerThanOp_Info.OtherOperandNum, N, NodeInfo, 621 OResNo); 622 623 // It must be integer. 624 bool MadeChange = OtherNode->getExtType(OResNo).EnforceInteger(TP); 625 626 // This doesn't try to enforce any information on the OtherNode, it just 627 // validates it when information is determined. 628 if (OtherNode->hasTypeSet(OResNo) && OtherNode->getType(OResNo) <= VT) 629 OtherNode->UpdateNodeType(OResNo, MVT::Other, TP); // Throw an error. 630 return MadeChange; 631 } 632 case SDTCisOpSmallerThanOp: { 633 unsigned BResNo = 0; 634 TreePatternNode *BigOperand = 635 getOperandNum(x.SDTCisOpSmallerThanOp_Info.BigOperandNum, N, NodeInfo, 636 BResNo); 637 return NodeToApply->getExtType(ResNo). 638 EnforceSmallerThan(BigOperand->getExtType(BResNo), TP); 639 } 640 case SDTCisEltOfVec: { 641 unsigned VResNo = 0; 642 TreePatternNode *VecOperand = 643 getOperandNum(x.SDTCisEltOfVec_Info.OtherOperandNum, N, NodeInfo, 644 VResNo); 645 if (VecOperand->hasTypeSet(VResNo)) { 646 if (!isVector(VecOperand->getType(VResNo))) 647 TP.error(N->getOperator()->getName() + " VT operand must be a vector!"); 648 EVT IVT = VecOperand->getType(VResNo); 649 IVT = IVT.getVectorElementType(); 650 return NodeToApply->UpdateNodeType(ResNo, IVT.getSimpleVT().SimpleTy, TP); 651 } 652 653 if (NodeToApply->hasTypeSet(ResNo) && 654 VecOperand->getExtType(VResNo).hasVectorTypes()){ 655 // Filter vector types out of VecOperand that don't have the right element 656 // type. 657 return VecOperand->getExtType(VResNo). 658 EnforceVectorEltTypeIs(NodeToApply->getType(ResNo), TP); 659 } 660 return false; 661 } 662 } 663 return false; 664} 665 666//===----------------------------------------------------------------------===// 667// SDNodeInfo implementation 668// 669SDNodeInfo::SDNodeInfo(Record *R) : Def(R) { 670 EnumName = R->getValueAsString("Opcode"); 671 SDClassName = R->getValueAsString("SDClass"); 672 Record *TypeProfile = R->getValueAsDef("TypeProfile"); 673 NumResults = TypeProfile->getValueAsInt("NumResults"); 674 NumOperands = TypeProfile->getValueAsInt("NumOperands"); 675 676 // Parse the properties. 677 Properties = 0; 678 std::vector<Record*> PropList = R->getValueAsListOfDefs("Properties"); 679 for (unsigned i = 0, e = PropList.size(); i != e; ++i) { 680 if (PropList[i]->getName() == "SDNPCommutative") { 681 Properties |= 1 << SDNPCommutative; 682 } else if (PropList[i]->getName() == "SDNPAssociative") { 683 Properties |= 1 << SDNPAssociative; 684 } else if (PropList[i]->getName() == "SDNPHasChain") { 685 Properties |= 1 << SDNPHasChain; 686 } else if (PropList[i]->getName() == "SDNPOutFlag") { 687 Properties |= 1 << SDNPOutFlag; 688 } else if (PropList[i]->getName() == "SDNPInFlag") { 689 Properties |= 1 << SDNPInFlag; 690 } else if (PropList[i]->getName() == "SDNPOptInFlag") { 691 Properties |= 1 << SDNPOptInFlag; 692 } else if (PropList[i]->getName() == "SDNPMayStore") { 693 Properties |= 1 << SDNPMayStore; 694 } else if (PropList[i]->getName() == "SDNPMayLoad") { 695 Properties |= 1 << SDNPMayLoad; 696 } else if (PropList[i]->getName() == "SDNPSideEffect") { 697 Properties |= 1 << SDNPSideEffect; 698 } else if (PropList[i]->getName() == "SDNPMemOperand") { 699 Properties |= 1 << SDNPMemOperand; 700 } else if (PropList[i]->getName() == "SDNPVariadic") { 701 Properties |= 1 << SDNPVariadic; 702 } else { 703 errs() << "Unknown SD Node property '" << PropList[i]->getName() 704 << "' on node '" << R->getName() << "'!\n"; 705 exit(1); 706 } 707 } 708 709 710 // Parse the type constraints. 711 std::vector<Record*> ConstraintList = 712 TypeProfile->getValueAsListOfDefs("Constraints"); 713 TypeConstraints.assign(ConstraintList.begin(), ConstraintList.end()); 714} 715 716/// getKnownType - If the type constraints on this node imply a fixed type 717/// (e.g. all stores return void, etc), then return it as an 718/// MVT::SimpleValueType. Otherwise, return EEVT::Other. 719MVT::SimpleValueType SDNodeInfo::getKnownType() const { 720 unsigned NumResults = getNumResults(); 721 assert(NumResults <= 1 && 722 "We only work with nodes with zero or one result so far!"); 723 724 for (unsigned i = 0, e = TypeConstraints.size(); i != e; ++i) { 725 // Make sure that this applies to the correct node result. 726 if (TypeConstraints[i].OperandNo >= NumResults) // FIXME: need value # 727 continue; 728 729 switch (TypeConstraints[i].ConstraintType) { 730 default: break; 731 case SDTypeConstraint::SDTCisVT: 732 return TypeConstraints[i].x.SDTCisVT_Info.VT; 733 case SDTypeConstraint::SDTCisPtrTy: 734 return MVT::iPTR; 735 } 736 } 737 return MVT::Other; 738} 739 740//===----------------------------------------------------------------------===// 741// TreePatternNode implementation 742// 743 744TreePatternNode::~TreePatternNode() { 745#if 0 // FIXME: implement refcounted tree nodes! 746 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 747 delete getChild(i); 748#endif 749} 750 751static unsigned GetNumNodeResults(Record *Operator, CodeGenDAGPatterns &CDP) { 752 if (Operator->getName() == "set" || 753 Operator->getName() == "implicit" || 754 Operator->getName() == "parallel") 755 return 0; // All return nothing. 756 757 if (Operator->isSubClassOf("Intrinsic")) { 758 unsigned NumRes = CDP.getIntrinsic(Operator).IS.RetVTs.size(); 759 if (NumRes == 1 && CDP.getIntrinsic(Operator).IS.RetVTs[0] == MVT::isVoid) 760 return 0; 761 return NumRes; 762 } 763 764 if (Operator->isSubClassOf("SDNode")) 765 return CDP.getSDNodeInfo(Operator).getNumResults(); 766 767 if (Operator->isSubClassOf("PatFrag")) { 768 // If we've already parsed this pattern fragment, get it. Otherwise, handle 769 // the forward reference case where one pattern fragment references another 770 // before it is processed. 771 if (TreePattern *PFRec = CDP.getPatternFragmentIfRead(Operator)) 772 return PFRec->getOnlyTree()->getNumTypes(); 773 774 // Get the result tree. 775 DagInit *Tree = Operator->getValueAsDag("Fragment"); 776 Record *Op = 0; 777 if (Tree && dynamic_cast<DefInit*>(Tree->getOperator())) 778 Op = dynamic_cast<DefInit*>(Tree->getOperator())->getDef(); 779 assert(Op && "Invalid Fragment"); 780 return GetNumNodeResults(Op, CDP); 781 } 782 783 if (Operator->isSubClassOf("Instruction")) { 784 CodeGenInstruction &InstInfo = CDP.getTargetInfo().getInstruction(Operator); 785 786 // FIXME: Handle implicit defs right. 787 if (InstInfo.NumDefs != 0) 788 return 1; // FIXME: Handle inst results right! 789 790 if (!InstInfo.ImplicitDefs.empty()) { 791 // Add on one implicit def if it has a resolvable type. 792 Record *FirstImplicitDef = InstInfo.ImplicitDefs[0]; 793 assert(FirstImplicitDef->isSubClassOf("Register")); 794 const std::vector<MVT::SimpleValueType> &RegVTs = 795 CDP.getTargetInfo().getRegisterVTs(FirstImplicitDef); 796 if (RegVTs.size() == 1) 797 return 1; 798 } 799 return 0; 800 } 801 802 if (Operator->isSubClassOf("SDNodeXForm")) 803 return 1; // FIXME: Generalize SDNodeXForm 804 805 Operator->dump(); 806 errs() << "Unhandled node in GetNumNodeResults\n"; 807 exit(1); 808} 809 810void TreePatternNode::print(raw_ostream &OS) const { 811 if (isLeaf()) 812 OS << *getLeafValue(); 813 else 814 OS << '(' << getOperator()->getName(); 815 816 for (unsigned i = 0, e = Types.size(); i != e; ++i) 817 OS << ':' << getExtType(i).getName(); 818 819 if (!isLeaf()) { 820 if (getNumChildren() != 0) { 821 OS << " "; 822 getChild(0)->print(OS); 823 for (unsigned i = 1, e = getNumChildren(); i != e; ++i) { 824 OS << ", "; 825 getChild(i)->print(OS); 826 } 827 } 828 OS << ")"; 829 } 830 831 for (unsigned i = 0, e = PredicateFns.size(); i != e; ++i) 832 OS << "<<P:" << PredicateFns[i] << ">>"; 833 if (TransformFn) 834 OS << "<<X:" << TransformFn->getName() << ">>"; 835 if (!getName().empty()) 836 OS << ":$" << getName(); 837 838} 839void TreePatternNode::dump() const { 840 print(errs()); 841} 842 843/// isIsomorphicTo - Return true if this node is recursively 844/// isomorphic to the specified node. For this comparison, the node's 845/// entire state is considered. The assigned name is ignored, since 846/// nodes with differing names are considered isomorphic. However, if 847/// the assigned name is present in the dependent variable set, then 848/// the assigned name is considered significant and the node is 849/// isomorphic if the names match. 850bool TreePatternNode::isIsomorphicTo(const TreePatternNode *N, 851 const MultipleUseVarSet &DepVars) const { 852 if (N == this) return true; 853 if (N->isLeaf() != isLeaf() || getExtTypes() != N->getExtTypes() || 854 getPredicateFns() != N->getPredicateFns() || 855 getTransformFn() != N->getTransformFn()) 856 return false; 857 858 if (isLeaf()) { 859 if (DefInit *DI = dynamic_cast<DefInit*>(getLeafValue())) { 860 if (DefInit *NDI = dynamic_cast<DefInit*>(N->getLeafValue())) { 861 return ((DI->getDef() == NDI->getDef()) 862 && (DepVars.find(getName()) == DepVars.end() 863 || getName() == N->getName())); 864 } 865 } 866 return getLeafValue() == N->getLeafValue(); 867 } 868 869 if (N->getOperator() != getOperator() || 870 N->getNumChildren() != getNumChildren()) return false; 871 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 872 if (!getChild(i)->isIsomorphicTo(N->getChild(i), DepVars)) 873 return false; 874 return true; 875} 876 877/// clone - Make a copy of this tree and all of its children. 878/// 879TreePatternNode *TreePatternNode::clone() const { 880 TreePatternNode *New; 881 if (isLeaf()) { 882 New = new TreePatternNode(getLeafValue(), getNumTypes()); 883 } else { 884 std::vector<TreePatternNode*> CChildren; 885 CChildren.reserve(Children.size()); 886 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 887 CChildren.push_back(getChild(i)->clone()); 888 New = new TreePatternNode(getOperator(), CChildren, getNumTypes()); 889 } 890 New->setName(getName()); 891 New->Types = Types; 892 New->setPredicateFns(getPredicateFns()); 893 New->setTransformFn(getTransformFn()); 894 return New; 895} 896 897/// RemoveAllTypes - Recursively strip all the types of this tree. 898void TreePatternNode::RemoveAllTypes() { 899 for (unsigned i = 0, e = Types.size(); i != e; ++i) 900 Types[i] = EEVT::TypeSet(); // Reset to unknown type. 901 if (isLeaf()) return; 902 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 903 getChild(i)->RemoveAllTypes(); 904} 905 906 907/// SubstituteFormalArguments - Replace the formal arguments in this tree 908/// with actual values specified by ArgMap. 909void TreePatternNode:: 910SubstituteFormalArguments(std::map<std::string, TreePatternNode*> &ArgMap) { 911 if (isLeaf()) return; 912 913 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { 914 TreePatternNode *Child = getChild(i); 915 if (Child->isLeaf()) { 916 Init *Val = Child->getLeafValue(); 917 if (dynamic_cast<DefInit*>(Val) && 918 static_cast<DefInit*>(Val)->getDef()->getName() == "node") { 919 // We found a use of a formal argument, replace it with its value. 920 TreePatternNode *NewChild = ArgMap[Child->getName()]; 921 assert(NewChild && "Couldn't find formal argument!"); 922 assert((Child->getPredicateFns().empty() || 923 NewChild->getPredicateFns() == Child->getPredicateFns()) && 924 "Non-empty child predicate clobbered!"); 925 setChild(i, NewChild); 926 } 927 } else { 928 getChild(i)->SubstituteFormalArguments(ArgMap); 929 } 930 } 931} 932 933 934/// InlinePatternFragments - If this pattern refers to any pattern 935/// fragments, inline them into place, giving us a pattern without any 936/// PatFrag references. 937TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) { 938 if (isLeaf()) return this; // nothing to do. 939 Record *Op = getOperator(); 940 941 if (!Op->isSubClassOf("PatFrag")) { 942 // Just recursively inline children nodes. 943 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { 944 TreePatternNode *Child = getChild(i); 945 TreePatternNode *NewChild = Child->InlinePatternFragments(TP); 946 947 assert((Child->getPredicateFns().empty() || 948 NewChild->getPredicateFns() == Child->getPredicateFns()) && 949 "Non-empty child predicate clobbered!"); 950 951 setChild(i, NewChild); 952 } 953 return this; 954 } 955 956 // Otherwise, we found a reference to a fragment. First, look up its 957 // TreePattern record. 958 TreePattern *Frag = TP.getDAGPatterns().getPatternFragment(Op); 959 960 // Verify that we are passing the right number of operands. 961 if (Frag->getNumArgs() != Children.size()) 962 TP.error("'" + Op->getName() + "' fragment requires " + 963 utostr(Frag->getNumArgs()) + " operands!"); 964 965 TreePatternNode *FragTree = Frag->getOnlyTree()->clone(); 966 967 std::string Code = Op->getValueAsCode("Predicate"); 968 if (!Code.empty()) 969 FragTree->addPredicateFn("Predicate_"+Op->getName()); 970 971 // Resolve formal arguments to their actual value. 972 if (Frag->getNumArgs()) { 973 // Compute the map of formal to actual arguments. 974 std::map<std::string, TreePatternNode*> ArgMap; 975 for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i) 976 ArgMap[Frag->getArgName(i)] = getChild(i)->InlinePatternFragments(TP); 977 978 FragTree->SubstituteFormalArguments(ArgMap); 979 } 980 981 FragTree->setName(getName()); 982 for (unsigned i = 0, e = Types.size(); i != e; ++i) 983 FragTree->UpdateNodeType(i, getExtType(i), TP); 984 985 // Transfer in the old predicates. 986 for (unsigned i = 0, e = getPredicateFns().size(); i != e; ++i) 987 FragTree->addPredicateFn(getPredicateFns()[i]); 988 989 // Get a new copy of this fragment to stitch into here. 990 //delete this; // FIXME: implement refcounting! 991 992 // The fragment we inlined could have recursive inlining that is needed. See 993 // if there are any pattern fragments in it and inline them as needed. 994 return FragTree->InlinePatternFragments(TP); 995} 996 997/// getImplicitType - Check to see if the specified record has an implicit 998/// type which should be applied to it. This will infer the type of register 999/// references from the register file information, for example. 1000/// 1001static EEVT::TypeSet getImplicitType(Record *R, unsigned ResNo, 1002 bool NotRegisters, TreePattern &TP) { 1003 assert(ResNo == 0 && "FIXME: Unhandled result number"); 1004 1005 // Check to see if this is a register or a register class. 1006 if (R->isSubClassOf("RegisterClass")) { 1007 if (NotRegisters) 1008 return EEVT::TypeSet(); // Unknown. 1009 const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo(); 1010 return EEVT::TypeSet(T.getRegisterClass(R).getValueTypes()); 1011 } else if (R->isSubClassOf("PatFrag")) { 1012 // Pattern fragment types will be resolved when they are inlined. 1013 return EEVT::TypeSet(); // Unknown. 1014 } else if (R->isSubClassOf("Register")) { 1015 if (NotRegisters) 1016 return EEVT::TypeSet(); // Unknown. 1017 const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo(); 1018 return EEVT::TypeSet(T.getRegisterVTs(R)); 1019 } else if (R->isSubClassOf("ValueType") || R->isSubClassOf("CondCode")) { 1020 // Using a VTSDNode or CondCodeSDNode. 1021 return EEVT::TypeSet(MVT::Other, TP); 1022 } else if (R->isSubClassOf("ComplexPattern")) { 1023 if (NotRegisters) 1024 return EEVT::TypeSet(); // Unknown. 1025 return EEVT::TypeSet(TP.getDAGPatterns().getComplexPattern(R).getValueType(), 1026 TP); 1027 } else if (R->isSubClassOf("PointerLikeRegClass")) { 1028 return EEVT::TypeSet(MVT::iPTR, TP); 1029 } else if (R->getName() == "node" || R->getName() == "srcvalue" || 1030 R->getName() == "zero_reg") { 1031 // Placeholder. 1032 return EEVT::TypeSet(); // Unknown. 1033 } 1034 1035 TP.error("Unknown node flavor used in pattern: " + R->getName()); 1036 return EEVT::TypeSet(MVT::Other, TP); 1037} 1038 1039 1040/// getIntrinsicInfo - If this node corresponds to an intrinsic, return the 1041/// CodeGenIntrinsic information for it, otherwise return a null pointer. 1042const CodeGenIntrinsic *TreePatternNode:: 1043getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const { 1044 if (getOperator() != CDP.get_intrinsic_void_sdnode() && 1045 getOperator() != CDP.get_intrinsic_w_chain_sdnode() && 1046 getOperator() != CDP.get_intrinsic_wo_chain_sdnode()) 1047 return 0; 1048 1049 unsigned IID = 1050 dynamic_cast<IntInit*>(getChild(0)->getLeafValue())->getValue(); 1051 return &CDP.getIntrinsicInfo(IID); 1052} 1053 1054/// getComplexPatternInfo - If this node corresponds to a ComplexPattern, 1055/// return the ComplexPattern information, otherwise return null. 1056const ComplexPattern * 1057TreePatternNode::getComplexPatternInfo(const CodeGenDAGPatterns &CGP) const { 1058 if (!isLeaf()) return 0; 1059 1060 DefInit *DI = dynamic_cast<DefInit*>(getLeafValue()); 1061 if (DI && DI->getDef()->isSubClassOf("ComplexPattern")) 1062 return &CGP.getComplexPattern(DI->getDef()); 1063 return 0; 1064} 1065 1066/// NodeHasProperty - Return true if this node has the specified property. 1067bool TreePatternNode::NodeHasProperty(SDNP Property, 1068 const CodeGenDAGPatterns &CGP) const { 1069 if (isLeaf()) { 1070 if (const ComplexPattern *CP = getComplexPatternInfo(CGP)) 1071 return CP->hasProperty(Property); 1072 return false; 1073 } 1074 1075 Record *Operator = getOperator(); 1076 if (!Operator->isSubClassOf("SDNode")) return false; 1077 1078 return CGP.getSDNodeInfo(Operator).hasProperty(Property); 1079} 1080 1081 1082 1083 1084/// TreeHasProperty - Return true if any node in this tree has the specified 1085/// property. 1086bool TreePatternNode::TreeHasProperty(SDNP Property, 1087 const CodeGenDAGPatterns &CGP) const { 1088 if (NodeHasProperty(Property, CGP)) 1089 return true; 1090 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1091 if (getChild(i)->TreeHasProperty(Property, CGP)) 1092 return true; 1093 return false; 1094} 1095 1096/// isCommutativeIntrinsic - Return true if the node corresponds to a 1097/// commutative intrinsic. 1098bool 1099TreePatternNode::isCommutativeIntrinsic(const CodeGenDAGPatterns &CDP) const { 1100 if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) 1101 return Int->isCommutative; 1102 return false; 1103} 1104 1105 1106/// ApplyTypeConstraints - Apply all of the type constraints relevant to 1107/// this node and its children in the tree. This returns true if it makes a 1108/// change, false otherwise. If a type contradiction is found, throw an 1109/// exception. 1110bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { 1111 CodeGenDAGPatterns &CDP = TP.getDAGPatterns(); 1112 if (isLeaf()) { 1113 if (DefInit *DI = dynamic_cast<DefInit*>(getLeafValue())) { 1114 // If it's a regclass or something else known, include the type. 1115 bool MadeChange = false; 1116 for (unsigned i = 0, e = Types.size(); i != e; ++i) 1117 MadeChange |= UpdateNodeType(i, getImplicitType(DI->getDef(), i, 1118 NotRegisters, TP), TP); 1119 return MadeChange; 1120 } 1121 1122 if (IntInit *II = dynamic_cast<IntInit*>(getLeafValue())) { 1123 assert(Types.size() == 1 && "Invalid IntInit"); 1124 1125 // Int inits are always integers. :) 1126 bool MadeChange = Types[0].EnforceInteger(TP); 1127 1128 if (!Types[0].isConcrete()) 1129 return MadeChange; 1130 1131 MVT::SimpleValueType VT = getType(0); 1132 if (VT == MVT::iPTR || VT == MVT::iPTRAny) 1133 return MadeChange; 1134 1135 unsigned Size = EVT(VT).getSizeInBits(); 1136 // Make sure that the value is representable for this type. 1137 if (Size >= 32) return MadeChange; 1138 1139 int Val = (II->getValue() << (32-Size)) >> (32-Size); 1140 if (Val == II->getValue()) return MadeChange; 1141 1142 // If sign-extended doesn't fit, does it fit as unsigned? 1143 unsigned ValueMask; 1144 unsigned UnsignedVal; 1145 ValueMask = unsigned(~uint32_t(0UL) >> (32-Size)); 1146 UnsignedVal = unsigned(II->getValue()); 1147 1148 if ((ValueMask & UnsignedVal) == UnsignedVal) 1149 return MadeChange; 1150 1151 TP.error("Integer value '" + itostr(II->getValue())+ 1152 "' is out of range for type '" + getEnumName(getType(0)) + "'!"); 1153 return MadeChange; 1154 } 1155 return false; 1156 } 1157 1158 // special handling for set, which isn't really an SDNode. 1159 if (getOperator()->getName() == "set") { 1160 assert(getNumTypes() == 0 && "Set doesn't produce a value"); 1161 assert(getNumChildren() >= 2 && "Missing RHS of a set?"); 1162 unsigned NC = getNumChildren(); 1163 1164 TreePatternNode *SetVal = getChild(NC-1); 1165 bool MadeChange = SetVal->ApplyTypeConstraints(TP, NotRegisters); 1166 1167 for (unsigned i = 0; i < NC-1; ++i) { 1168 TreePatternNode *Child = getChild(i); 1169 MadeChange |= Child->ApplyTypeConstraints(TP, NotRegisters); 1170 1171 // Types of operands must match. 1172 MadeChange |= Child->UpdateNodeType(0, SetVal->getExtType(i), TP); 1173 MadeChange |= SetVal->UpdateNodeType(i, Child->getExtType(0), TP); 1174 } 1175 return MadeChange; 1176 } 1177 1178 if (getOperator()->getName() == "implicit" || 1179 getOperator()->getName() == "parallel") { 1180 assert(getNumTypes() == 0 && "Node doesn't produce a value"); 1181 1182 bool MadeChange = false; 1183 for (unsigned i = 0; i < getNumChildren(); ++i) 1184 MadeChange = getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 1185 return MadeChange; 1186 } 1187 1188 if (getOperator()->getName() == "COPY_TO_REGCLASS") { 1189 bool MadeChange = false; 1190 MadeChange |= getChild(0)->ApplyTypeConstraints(TP, NotRegisters); 1191 MadeChange |= getChild(1)->ApplyTypeConstraints(TP, NotRegisters); 1192 1193 assert(getChild(0)->getNumTypes() == 1 && 1194 getChild(1)->getNumTypes() == 1 && "Unhandled case"); 1195 1196 // child #1 of COPY_TO_REGCLASS should be a register class. We don't care 1197 // what type it gets, so if it didn't get a concrete type just give it the 1198 // first viable type from the reg class. 1199 if (!getChild(1)->hasTypeSet(0) && 1200 !getChild(1)->getExtType(0).isCompletelyUnknown()) { 1201 MVT::SimpleValueType RCVT = getChild(1)->getExtType(0).getTypeList()[0]; 1202 MadeChange |= getChild(1)->UpdateNodeType(0, RCVT, TP); 1203 } 1204 return MadeChange; 1205 } 1206 1207 if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) { 1208 bool MadeChange = false; 1209 1210 // Apply the result type to the node. 1211 unsigned NumRetVTs = Int->IS.RetVTs.size(); 1212 unsigned NumParamVTs = Int->IS.ParamVTs.size(); 1213 if (NumRetVTs == 1 && Int->IS.RetVTs[0] == MVT::isVoid) 1214 NumRetVTs = 0; 1215 1216 for (unsigned i = 0, e = NumRetVTs; i != e; ++i) 1217 MadeChange |= UpdateNodeType(i, Int->IS.RetVTs[i], TP); 1218 1219 if (getNumChildren() != NumParamVTs + 1) 1220 TP.error("Intrinsic '" + Int->Name + "' expects " + 1221 utostr(NumParamVTs) + " operands, not " + 1222 utostr(getNumChildren() - 1) + " operands!"); 1223 1224 // Apply type info to the intrinsic ID. 1225 MadeChange |= getChild(0)->UpdateNodeType(0, MVT::iPTR, TP); 1226 1227 for (unsigned i = 0, e = getNumChildren()-1; i != e; ++i) { 1228 MadeChange |= getChild(i+1)->ApplyTypeConstraints(TP, NotRegisters); 1229 1230 MVT::SimpleValueType OpVT = Int->IS.ParamVTs[i]; 1231 assert(getChild(i+1)->getNumTypes() == 1 && "Unhandled case"); 1232 MadeChange |= getChild(i+1)->UpdateNodeType(0, OpVT, TP); 1233 } 1234 return MadeChange; 1235 } 1236 1237 if (getOperator()->isSubClassOf("SDNode")) { 1238 const SDNodeInfo &NI = CDP.getSDNodeInfo(getOperator()); 1239 1240 bool MadeChange = NI.ApplyTypeConstraints(this, TP); 1241 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1242 MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 1243 return MadeChange; 1244 } 1245 1246 if (getOperator()->isSubClassOf("Instruction")) { 1247 const DAGInstruction &Inst = CDP.getInstruction(getOperator()); 1248 unsigned ResNo = 0; 1249 assert(Inst.getNumResults() <= 1 && 1250 "FIXME: Only supports zero or one result instrs!"); 1251 1252 CodeGenInstruction &InstInfo = 1253 CDP.getTargetInfo().getInstruction(getOperator()); 1254 1255 EEVT::TypeSet ResultType; 1256 1257 // Apply the result type to the node 1258 if (InstInfo.NumDefs != 0) { // # of elements in (outs) list 1259 Record *ResultNode = Inst.getResult(0); 1260 1261 if (ResultNode->isSubClassOf("PointerLikeRegClass")) { 1262 ResultType = EEVT::TypeSet(MVT::iPTR, TP); 1263 } else if (ResultNode->getName() == "unknown") { 1264 // Nothing to do. 1265 } else { 1266 assert(ResultNode->isSubClassOf("RegisterClass") && 1267 "Operands should be register classes!"); 1268 const CodeGenRegisterClass &RC = 1269 CDP.getTargetInfo().getRegisterClass(ResultNode); 1270 ResultType = RC.getValueTypes(); 1271 } 1272 } else if (!InstInfo.ImplicitDefs.empty()) { 1273 // If the instruction has implicit defs, the first one defines the result 1274 // type. 1275 Record *FirstImplicitDef = InstInfo.ImplicitDefs[0]; 1276 assert(FirstImplicitDef->isSubClassOf("Register")); 1277 const std::vector<MVT::SimpleValueType> &RegVTs = 1278 CDP.getTargetInfo().getRegisterVTs(FirstImplicitDef); 1279 if (RegVTs.size() == 1) // FIXME: Generalize. 1280 ResultType = EEVT::TypeSet(RegVTs); 1281 } else { 1282 // Otherwise, the instruction produces no value result. 1283 } 1284 1285 bool MadeChange = false; 1286 1287 if (!ResultType.isCompletelyUnknown()) 1288 MadeChange |= UpdateNodeType(ResNo, ResultType, TP); 1289 1290 // If this is an INSERT_SUBREG, constrain the source and destination VTs to 1291 // be the same. 1292 if (getOperator()->getName() == "INSERT_SUBREG") { 1293 assert(getChild(0)->getNumTypes() == 1 && "FIXME: Unhandled"); 1294 MadeChange |= UpdateNodeType(0, getChild(0)->getExtType(0), TP); 1295 MadeChange |= getChild(0)->UpdateNodeType(0, getExtType(0), TP); 1296 } 1297 1298 unsigned ChildNo = 0; 1299 for (unsigned i = 0, e = Inst.getNumOperands(); i != e; ++i) { 1300 Record *OperandNode = Inst.getOperand(i); 1301 1302 // If the instruction expects a predicate or optional def operand, we 1303 // codegen this by setting the operand to it's default value if it has a 1304 // non-empty DefaultOps field. 1305 if ((OperandNode->isSubClassOf("PredicateOperand") || 1306 OperandNode->isSubClassOf("OptionalDefOperand")) && 1307 !CDP.getDefaultOperand(OperandNode).DefaultOps.empty()) 1308 continue; 1309 1310 // Verify that we didn't run out of provided operands. 1311 if (ChildNo >= getNumChildren()) 1312 TP.error("Instruction '" + getOperator()->getName() + 1313 "' expects more operands than were provided."); 1314 1315 MVT::SimpleValueType VT; 1316 TreePatternNode *Child = getChild(ChildNo++); 1317 assert(Child->getNumTypes() == 1 && "Unknown case?"); 1318 1319 if (OperandNode->isSubClassOf("RegisterClass")) { 1320 const CodeGenRegisterClass &RC = 1321 CDP.getTargetInfo().getRegisterClass(OperandNode); 1322 MadeChange |= Child->UpdateNodeType(0, RC.getValueTypes(), TP); 1323 } else if (OperandNode->isSubClassOf("Operand")) { 1324 VT = getValueType(OperandNode->getValueAsDef("Type")); 1325 MadeChange |= Child->UpdateNodeType(0, VT, TP); 1326 } else if (OperandNode->isSubClassOf("PointerLikeRegClass")) { 1327 MadeChange |= Child->UpdateNodeType(0, MVT::iPTR, TP); 1328 } else if (OperandNode->getName() == "unknown") { 1329 // Nothing to do. 1330 } else { 1331 assert(0 && "Unknown operand type!"); 1332 abort(); 1333 } 1334 MadeChange |= Child->ApplyTypeConstraints(TP, NotRegisters); 1335 } 1336 1337 if (ChildNo != getNumChildren()) 1338 TP.error("Instruction '" + getOperator()->getName() + 1339 "' was provided too many operands!"); 1340 1341 return MadeChange; 1342 } 1343 1344 assert(getOperator()->isSubClassOf("SDNodeXForm") && "Unknown node type!"); 1345 1346 // Node transforms always take one operand. 1347 if (getNumChildren() != 1) 1348 TP.error("Node transform '" + getOperator()->getName() + 1349 "' requires one operand!"); 1350 1351 bool MadeChange = getChild(0)->ApplyTypeConstraints(TP, NotRegisters); 1352 1353 1354 // If either the output or input of the xform does not have exact 1355 // type info. We assume they must be the same. Otherwise, it is perfectly 1356 // legal to transform from one type to a completely different type. 1357#if 0 1358 if (!hasTypeSet() || !getChild(0)->hasTypeSet()) { 1359 bool MadeChange = UpdateNodeType(getChild(0)->getExtType(), TP); 1360 MadeChange |= getChild(0)->UpdateNodeType(getExtType(), TP); 1361 return MadeChange; 1362 } 1363#endif 1364 return MadeChange; 1365} 1366 1367/// OnlyOnRHSOfCommutative - Return true if this value is only allowed on the 1368/// RHS of a commutative operation, not the on LHS. 1369static bool OnlyOnRHSOfCommutative(TreePatternNode *N) { 1370 if (!N->isLeaf() && N->getOperator()->getName() == "imm") 1371 return true; 1372 if (N->isLeaf() && dynamic_cast<IntInit*>(N->getLeafValue())) 1373 return true; 1374 return false; 1375} 1376 1377 1378/// canPatternMatch - If it is impossible for this pattern to match on this 1379/// target, fill in Reason and return false. Otherwise, return true. This is 1380/// used as a sanity check for .td files (to prevent people from writing stuff 1381/// that can never possibly work), and to prevent the pattern permuter from 1382/// generating stuff that is useless. 1383bool TreePatternNode::canPatternMatch(std::string &Reason, 1384 const CodeGenDAGPatterns &CDP) { 1385 if (isLeaf()) return true; 1386 1387 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1388 if (!getChild(i)->canPatternMatch(Reason, CDP)) 1389 return false; 1390 1391 // If this is an intrinsic, handle cases that would make it not match. For 1392 // example, if an operand is required to be an immediate. 1393 if (getOperator()->isSubClassOf("Intrinsic")) { 1394 // TODO: 1395 return true; 1396 } 1397 1398 // If this node is a commutative operator, check that the LHS isn't an 1399 // immediate. 1400 const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(getOperator()); 1401 bool isCommIntrinsic = isCommutativeIntrinsic(CDP); 1402 if (NodeInfo.hasProperty(SDNPCommutative) || isCommIntrinsic) { 1403 // Scan all of the operands of the node and make sure that only the last one 1404 // is a constant node, unless the RHS also is. 1405 if (!OnlyOnRHSOfCommutative(getChild(getNumChildren()-1))) { 1406 bool Skip = isCommIntrinsic ? 1 : 0; // First operand is intrinsic id. 1407 for (unsigned i = Skip, e = getNumChildren()-1; i != e; ++i) 1408 if (OnlyOnRHSOfCommutative(getChild(i))) { 1409 Reason="Immediate value must be on the RHS of commutative operators!"; 1410 return false; 1411 } 1412 } 1413 } 1414 1415 return true; 1416} 1417 1418//===----------------------------------------------------------------------===// 1419// TreePattern implementation 1420// 1421 1422TreePattern::TreePattern(Record *TheRec, ListInit *RawPat, bool isInput, 1423 CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp){ 1424 isInputPattern = isInput; 1425 for (unsigned i = 0, e = RawPat->getSize(); i != e; ++i) 1426 Trees.push_back(ParseTreePattern((DagInit*)RawPat->getElement(i))); 1427} 1428 1429TreePattern::TreePattern(Record *TheRec, DagInit *Pat, bool isInput, 1430 CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp){ 1431 isInputPattern = isInput; 1432 Trees.push_back(ParseTreePattern(Pat)); 1433} 1434 1435TreePattern::TreePattern(Record *TheRec, TreePatternNode *Pat, bool isInput, 1436 CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp){ 1437 isInputPattern = isInput; 1438 Trees.push_back(Pat); 1439} 1440 1441void TreePattern::error(const std::string &Msg) const { 1442 dump(); 1443 throw TGError(TheRecord->getLoc(), "In " + TheRecord->getName() + ": " + Msg); 1444} 1445 1446void TreePattern::ComputeNamedNodes() { 1447 for (unsigned i = 0, e = Trees.size(); i != e; ++i) 1448 ComputeNamedNodes(Trees[i]); 1449} 1450 1451void TreePattern::ComputeNamedNodes(TreePatternNode *N) { 1452 if (!N->getName().empty()) 1453 NamedNodes[N->getName()].push_back(N); 1454 1455 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 1456 ComputeNamedNodes(N->getChild(i)); 1457} 1458 1459 1460TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) { 1461 DefInit *OpDef = dynamic_cast<DefInit*>(Dag->getOperator()); 1462 if (!OpDef) error("Pattern has unexpected operator type!"); 1463 Record *Operator = OpDef->getDef(); 1464 1465 if (Operator->isSubClassOf("ValueType")) { 1466 // If the operator is a ValueType, then this must be "type cast" of a leaf 1467 // node. 1468 if (Dag->getNumArgs() != 1) 1469 error("Type cast only takes one operand!"); 1470 1471 Init *Arg = Dag->getArg(0); 1472 TreePatternNode *New; 1473 if (DefInit *DI = dynamic_cast<DefInit*>(Arg)) { 1474 Record *R = DI->getDef(); 1475 if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag")) { 1476 Dag->setArg(0, new DagInit(DI, "", 1477 std::vector<std::pair<Init*, std::string> >())); 1478 return ParseTreePattern(Dag); 1479 } 1480 1481 // Input argument? 1482 if (R->getName() == "node") { 1483 if (Dag->getArgName(0).empty()) 1484 error("'node' argument requires a name to match with operand list"); 1485 Args.push_back(Dag->getArgName(0)); 1486 } 1487 1488 New = new TreePatternNode(DI, 1); 1489 } else if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) { 1490 New = ParseTreePattern(DI); 1491 } else if (IntInit *II = dynamic_cast<IntInit*>(Arg)) { 1492 New = new TreePatternNode(II, 1); 1493 if (!Dag->getArgName(0).empty()) 1494 error("Constant int argument should not have a name!"); 1495 } else if (BitsInit *BI = dynamic_cast<BitsInit*>(Arg)) { 1496 // Turn this into an IntInit. 1497 Init *II = BI->convertInitializerTo(new IntRecTy()); 1498 if (II == 0 || !dynamic_cast<IntInit*>(II)) 1499 error("Bits value must be constants!"); 1500 1501 New = new TreePatternNode(dynamic_cast<IntInit*>(II), 1); 1502 if (!Dag->getArgName(0).empty()) 1503 error("Constant int argument should not have a name!"); 1504 } else { 1505 Arg->dump(); 1506 error("Unknown leaf value for tree pattern!"); 1507 return 0; 1508 } 1509 1510 // Apply the type cast. 1511 assert(New->getNumTypes() == 1 && "FIXME: Unhandled"); 1512 New->UpdateNodeType(0, getValueType(Operator), *this); 1513 if (New->getNumChildren() == 0) 1514 New->setName(Dag->getArgName(0)); 1515 return New; 1516 } 1517 1518 // Verify that this is something that makes sense for an operator. 1519 if (!Operator->isSubClassOf("PatFrag") && 1520 !Operator->isSubClassOf("SDNode") && 1521 !Operator->isSubClassOf("Instruction") && 1522 !Operator->isSubClassOf("SDNodeXForm") && 1523 !Operator->isSubClassOf("Intrinsic") && 1524 Operator->getName() != "set" && 1525 Operator->getName() != "implicit" && 1526 Operator->getName() != "parallel") 1527 error("Unrecognized node '" + Operator->getName() + "'!"); 1528 1529 // Check to see if this is something that is illegal in an input pattern. 1530 if (isInputPattern && (Operator->isSubClassOf("Instruction") || 1531 Operator->isSubClassOf("SDNodeXForm"))) 1532 error("Cannot use '" + Operator->getName() + "' in an input pattern!"); 1533 1534 std::vector<TreePatternNode*> Children; 1535 1536 for (unsigned i = 0, e = Dag->getNumArgs(); i != e; ++i) { 1537 Init *Arg = Dag->getArg(i); 1538 if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) { 1539 Children.push_back(ParseTreePattern(DI)); 1540 if (Children.back()->getName().empty()) 1541 Children.back()->setName(Dag->getArgName(i)); 1542 } else if (DefInit *DefI = dynamic_cast<DefInit*>(Arg)) { 1543 Record *R = DefI->getDef(); 1544 // Direct reference to a leaf DagNode or PatFrag? Turn it into a 1545 // TreePatternNode if its own. 1546 if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag")) { 1547 Dag->setArg(i, new DagInit(DefI, "", 1548 std::vector<std::pair<Init*, std::string> >())); 1549 --i; // Revisit this node... 1550 } else { 1551 TreePatternNode *Node = new TreePatternNode(DefI, 1); 1552 Node->setName(Dag->getArgName(i)); 1553 Children.push_back(Node); 1554 1555 // Input argument? 1556 if (R->getName() == "node") { 1557 if (Dag->getArgName(i).empty()) 1558 error("'node' argument requires a name to match with operand list"); 1559 Args.push_back(Dag->getArgName(i)); 1560 } 1561 } 1562 } else if (IntInit *II = dynamic_cast<IntInit*>(Arg)) { 1563 TreePatternNode *Node = new TreePatternNode(II, 1); 1564 if (!Dag->getArgName(i).empty()) 1565 error("Constant int argument should not have a name!"); 1566 Children.push_back(Node); 1567 } else if (BitsInit *BI = dynamic_cast<BitsInit*>(Arg)) { 1568 // Turn this into an IntInit. 1569 Init *II = BI->convertInitializerTo(new IntRecTy()); 1570 if (II == 0 || !dynamic_cast<IntInit*>(II)) 1571 error("Bits value must be constants!"); 1572 1573 TreePatternNode *Node = new TreePatternNode(dynamic_cast<IntInit*>(II),1); 1574 if (!Dag->getArgName(i).empty()) 1575 error("Constant int argument should not have a name!"); 1576 Children.push_back(Node); 1577 } else { 1578 errs() << '"'; 1579 Arg->dump(); 1580 errs() << "\": "; 1581 error("Unknown leaf value for tree pattern!"); 1582 } 1583 } 1584 1585 // If the operator is an intrinsic, then this is just syntactic sugar for for 1586 // (intrinsic_* <number>, ..children..). Pick the right intrinsic node, and 1587 // convert the intrinsic name to a number. 1588 if (Operator->isSubClassOf("Intrinsic")) { 1589 const CodeGenIntrinsic &Int = getDAGPatterns().getIntrinsic(Operator); 1590 unsigned IID = getDAGPatterns().getIntrinsicID(Operator)+1; 1591 1592 // If this intrinsic returns void, it must have side-effects and thus a 1593 // chain. 1594 if (Int.IS.RetVTs[0] == MVT::isVoid) { 1595 Operator = getDAGPatterns().get_intrinsic_void_sdnode(); 1596 } else if (Int.ModRef != CodeGenIntrinsic::NoMem) { 1597 // Has side-effects, requires chain. 1598 Operator = getDAGPatterns().get_intrinsic_w_chain_sdnode(); 1599 } else { 1600 // Otherwise, no chain. 1601 Operator = getDAGPatterns().get_intrinsic_wo_chain_sdnode(); 1602 } 1603 1604 TreePatternNode *IIDNode = new TreePatternNode(new IntInit(IID), 1); 1605 Children.insert(Children.begin(), IIDNode); 1606 } 1607 1608 unsigned NumResults = GetNumNodeResults(Operator, CDP); 1609 TreePatternNode *Result = new TreePatternNode(Operator, Children, NumResults); 1610 Result->setName(Dag->getName()); 1611 return Result; 1612} 1613 1614/// InferAllTypes - Infer/propagate as many types throughout the expression 1615/// patterns as possible. Return true if all types are inferred, false 1616/// otherwise. Throw an exception if a type contradiction is found. 1617bool TreePattern:: 1618InferAllTypes(const StringMap<SmallVector<TreePatternNode*,1> > *InNamedTypes) { 1619 if (NamedNodes.empty()) 1620 ComputeNamedNodes(); 1621 1622 bool MadeChange = true; 1623 while (MadeChange) { 1624 MadeChange = false; 1625 for (unsigned i = 0, e = Trees.size(); i != e; ++i) 1626 MadeChange |= Trees[i]->ApplyTypeConstraints(*this, false); 1627 1628 // If there are constraints on our named nodes, apply them. 1629 for (StringMap<SmallVector<TreePatternNode*,1> >::iterator 1630 I = NamedNodes.begin(), E = NamedNodes.end(); I != E; ++I) { 1631 SmallVectorImpl<TreePatternNode*> &Nodes = I->second; 1632 1633 // If we have input named node types, propagate their types to the named 1634 // values here. 1635 if (InNamedTypes) { 1636 // FIXME: Should be error? 1637 assert(InNamedTypes->count(I->getKey()) && 1638 "Named node in output pattern but not input pattern?"); 1639 1640 const SmallVectorImpl<TreePatternNode*> &InNodes = 1641 InNamedTypes->find(I->getKey())->second; 1642 1643 // The input types should be fully resolved by now. 1644 for (unsigned i = 0, e = Nodes.size(); i != e; ++i) { 1645 // If this node is a register class, and it is the root of the pattern 1646 // then we're mapping something onto an input register. We allow 1647 // changing the type of the input register in this case. This allows 1648 // us to match things like: 1649 // def : Pat<(v1i64 (bitconvert(v2i32 DPR:$src))), (v1i64 DPR:$src)>; 1650 if (Nodes[i] == Trees[0] && Nodes[i]->isLeaf()) { 1651 DefInit *DI = dynamic_cast<DefInit*>(Nodes[i]->getLeafValue()); 1652 if (DI && DI->getDef()->isSubClassOf("RegisterClass")) 1653 continue; 1654 } 1655 1656 assert(Nodes[i]->getNumTypes() == 1 && 1657 InNodes[0]->getNumTypes() == 1 && 1658 "FIXME: cannot name multiple result nodes yet"); 1659 MadeChange |= Nodes[i]->UpdateNodeType(0, InNodes[0]->getExtType(0), 1660 *this); 1661 } 1662 } 1663 1664 // If there are multiple nodes with the same name, they must all have the 1665 // same type. 1666 if (I->second.size() > 1) { 1667 for (unsigned i = 0, e = Nodes.size()-1; i != e; ++i) { 1668 TreePatternNode *N1 = Nodes[i], *N2 = Nodes[i+1]; 1669 assert(N1->getNumTypes() == 1 && N2->getNumTypes() == 1 && 1670 "FIXME: cannot name multiple result nodes yet"); 1671 1672 MadeChange |= N1->UpdateNodeType(0, N2->getExtType(0), *this); 1673 MadeChange |= N2->UpdateNodeType(0, N1->getExtType(0), *this); 1674 } 1675 } 1676 } 1677 } 1678 1679 bool HasUnresolvedTypes = false; 1680 for (unsigned i = 0, e = Trees.size(); i != e; ++i) 1681 HasUnresolvedTypes |= Trees[i]->ContainsUnresolvedType(); 1682 return !HasUnresolvedTypes; 1683} 1684 1685void TreePattern::print(raw_ostream &OS) const { 1686 OS << getRecord()->getName(); 1687 if (!Args.empty()) { 1688 OS << "(" << Args[0]; 1689 for (unsigned i = 1, e = Args.size(); i != e; ++i) 1690 OS << ", " << Args[i]; 1691 OS << ")"; 1692 } 1693 OS << ": "; 1694 1695 if (Trees.size() > 1) 1696 OS << "[\n"; 1697 for (unsigned i = 0, e = Trees.size(); i != e; ++i) { 1698 OS << "\t"; 1699 Trees[i]->print(OS); 1700 OS << "\n"; 1701 } 1702 1703 if (Trees.size() > 1) 1704 OS << "]\n"; 1705} 1706 1707void TreePattern::dump() const { print(errs()); } 1708 1709//===----------------------------------------------------------------------===// 1710// CodeGenDAGPatterns implementation 1711// 1712 1713CodeGenDAGPatterns::CodeGenDAGPatterns(RecordKeeper &R) : Records(R) { 1714 Intrinsics = LoadIntrinsics(Records, false); 1715 TgtIntrinsics = LoadIntrinsics(Records, true); 1716 ParseNodeInfo(); 1717 ParseNodeTransforms(); 1718 ParseComplexPatterns(); 1719 ParsePatternFragments(); 1720 ParseDefaultOperands(); 1721 ParseInstructions(); 1722 ParsePatterns(); 1723 1724 // Generate variants. For example, commutative patterns can match 1725 // multiple ways. Add them to PatternsToMatch as well. 1726 GenerateVariants(); 1727 1728 // Infer instruction flags. For example, we can detect loads, 1729 // stores, and side effects in many cases by examining an 1730 // instruction's pattern. 1731 InferInstructionFlags(); 1732} 1733 1734CodeGenDAGPatterns::~CodeGenDAGPatterns() { 1735 for (pf_iterator I = PatternFragments.begin(), 1736 E = PatternFragments.end(); I != E; ++I) 1737 delete I->second; 1738} 1739 1740 1741Record *CodeGenDAGPatterns::getSDNodeNamed(const std::string &Name) const { 1742 Record *N = Records.getDef(Name); 1743 if (!N || !N->isSubClassOf("SDNode")) { 1744 errs() << "Error getting SDNode '" << Name << "'!\n"; 1745 exit(1); 1746 } 1747 return N; 1748} 1749 1750// Parse all of the SDNode definitions for the target, populating SDNodes. 1751void CodeGenDAGPatterns::ParseNodeInfo() { 1752 std::vector<Record*> Nodes = Records.getAllDerivedDefinitions("SDNode"); 1753 while (!Nodes.empty()) { 1754 SDNodes.insert(std::make_pair(Nodes.back(), Nodes.back())); 1755 Nodes.pop_back(); 1756 } 1757 1758 // Get the builtin intrinsic nodes. 1759 intrinsic_void_sdnode = getSDNodeNamed("intrinsic_void"); 1760 intrinsic_w_chain_sdnode = getSDNodeNamed("intrinsic_w_chain"); 1761 intrinsic_wo_chain_sdnode = getSDNodeNamed("intrinsic_wo_chain"); 1762} 1763 1764/// ParseNodeTransforms - Parse all SDNodeXForm instances into the SDNodeXForms 1765/// map, and emit them to the file as functions. 1766void CodeGenDAGPatterns::ParseNodeTransforms() { 1767 std::vector<Record*> Xforms = Records.getAllDerivedDefinitions("SDNodeXForm"); 1768 while (!Xforms.empty()) { 1769 Record *XFormNode = Xforms.back(); 1770 Record *SDNode = XFormNode->getValueAsDef("Opcode"); 1771 std::string Code = XFormNode->getValueAsCode("XFormFunction"); 1772 SDNodeXForms.insert(std::make_pair(XFormNode, NodeXForm(SDNode, Code))); 1773 1774 Xforms.pop_back(); 1775 } 1776} 1777 1778void CodeGenDAGPatterns::ParseComplexPatterns() { 1779 std::vector<Record*> AMs = Records.getAllDerivedDefinitions("ComplexPattern"); 1780 while (!AMs.empty()) { 1781 ComplexPatterns.insert(std::make_pair(AMs.back(), AMs.back())); 1782 AMs.pop_back(); 1783 } 1784} 1785 1786 1787/// ParsePatternFragments - Parse all of the PatFrag definitions in the .td 1788/// file, building up the PatternFragments map. After we've collected them all, 1789/// inline fragments together as necessary, so that there are no references left 1790/// inside a pattern fragment to a pattern fragment. 1791/// 1792void CodeGenDAGPatterns::ParsePatternFragments() { 1793 std::vector<Record*> Fragments = Records.getAllDerivedDefinitions("PatFrag"); 1794 1795 // First step, parse all of the fragments. 1796 for (unsigned i = 0, e = Fragments.size(); i != e; ++i) { 1797 DagInit *Tree = Fragments[i]->getValueAsDag("Fragment"); 1798 TreePattern *P = new TreePattern(Fragments[i], Tree, true, *this); 1799 PatternFragments[Fragments[i]] = P; 1800 1801 // Validate the argument list, converting it to set, to discard duplicates. 1802 std::vector<std::string> &Args = P->getArgList(); 1803 std::set<std::string> OperandsSet(Args.begin(), Args.end()); 1804 1805 if (OperandsSet.count("")) 1806 P->error("Cannot have unnamed 'node' values in pattern fragment!"); 1807 1808 // Parse the operands list. 1809 DagInit *OpsList = Fragments[i]->getValueAsDag("Operands"); 1810 DefInit *OpsOp = dynamic_cast<DefInit*>(OpsList->getOperator()); 1811 // Special cases: ops == outs == ins. Different names are used to 1812 // improve readability. 1813 if (!OpsOp || 1814 (OpsOp->getDef()->getName() != "ops" && 1815 OpsOp->getDef()->getName() != "outs" && 1816 OpsOp->getDef()->getName() != "ins")) 1817 P->error("Operands list should start with '(ops ... '!"); 1818 1819 // Copy over the arguments. 1820 Args.clear(); 1821 for (unsigned j = 0, e = OpsList->getNumArgs(); j != e; ++j) { 1822 if (!dynamic_cast<DefInit*>(OpsList->getArg(j)) || 1823 static_cast<DefInit*>(OpsList->getArg(j))-> 1824 getDef()->getName() != "node") 1825 P->error("Operands list should all be 'node' values."); 1826 if (OpsList->getArgName(j).empty()) 1827 P->error("Operands list should have names for each operand!"); 1828 if (!OperandsSet.count(OpsList->getArgName(j))) 1829 P->error("'" + OpsList->getArgName(j) + 1830 "' does not occur in pattern or was multiply specified!"); 1831 OperandsSet.erase(OpsList->getArgName(j)); 1832 Args.push_back(OpsList->getArgName(j)); 1833 } 1834 1835 if (!OperandsSet.empty()) 1836 P->error("Operands list does not contain an entry for operand '" + 1837 *OperandsSet.begin() + "'!"); 1838 1839 // If there is a code init for this fragment, keep track of the fact that 1840 // this fragment uses it. 1841 std::string Code = Fragments[i]->getValueAsCode("Predicate"); 1842 if (!Code.empty()) 1843 P->getOnlyTree()->addPredicateFn("Predicate_"+Fragments[i]->getName()); 1844 1845 // If there is a node transformation corresponding to this, keep track of 1846 // it. 1847 Record *Transform = Fragments[i]->getValueAsDef("OperandTransform"); 1848 if (!getSDNodeTransform(Transform).second.empty()) // not noop xform? 1849 P->getOnlyTree()->setTransformFn(Transform); 1850 } 1851 1852 // Now that we've parsed all of the tree fragments, do a closure on them so 1853 // that there are not references to PatFrags left inside of them. 1854 for (unsigned i = 0, e = Fragments.size(); i != e; ++i) { 1855 TreePattern *ThePat = PatternFragments[Fragments[i]]; 1856 ThePat->InlinePatternFragments(); 1857 1858 // Infer as many types as possible. Don't worry about it if we don't infer 1859 // all of them, some may depend on the inputs of the pattern. 1860 try { 1861 ThePat->InferAllTypes(); 1862 } catch (...) { 1863 // If this pattern fragment is not supported by this target (no types can 1864 // satisfy its constraints), just ignore it. If the bogus pattern is 1865 // actually used by instructions, the type consistency error will be 1866 // reported there. 1867 } 1868 1869 // If debugging, print out the pattern fragment result. 1870 DEBUG(ThePat->dump()); 1871 } 1872} 1873 1874void CodeGenDAGPatterns::ParseDefaultOperands() { 1875 std::vector<Record*> DefaultOps[2]; 1876 DefaultOps[0] = Records.getAllDerivedDefinitions("PredicateOperand"); 1877 DefaultOps[1] = Records.getAllDerivedDefinitions("OptionalDefOperand"); 1878 1879 // Find some SDNode. 1880 assert(!SDNodes.empty() && "No SDNodes parsed?"); 1881 Init *SomeSDNode = new DefInit(SDNodes.begin()->first); 1882 1883 for (unsigned iter = 0; iter != 2; ++iter) { 1884 for (unsigned i = 0, e = DefaultOps[iter].size(); i != e; ++i) { 1885 DagInit *DefaultInfo = DefaultOps[iter][i]->getValueAsDag("DefaultOps"); 1886 1887 // Clone the DefaultInfo dag node, changing the operator from 'ops' to 1888 // SomeSDnode so that we can parse this. 1889 std::vector<std::pair<Init*, std::string> > Ops; 1890 for (unsigned op = 0, e = DefaultInfo->getNumArgs(); op != e; ++op) 1891 Ops.push_back(std::make_pair(DefaultInfo->getArg(op), 1892 DefaultInfo->getArgName(op))); 1893 DagInit *DI = new DagInit(SomeSDNode, "", Ops); 1894 1895 // Create a TreePattern to parse this. 1896 TreePattern P(DefaultOps[iter][i], DI, false, *this); 1897 assert(P.getNumTrees() == 1 && "This ctor can only produce one tree!"); 1898 1899 // Copy the operands over into a DAGDefaultOperand. 1900 DAGDefaultOperand DefaultOpInfo; 1901 1902 TreePatternNode *T = P.getTree(0); 1903 for (unsigned op = 0, e = T->getNumChildren(); op != e; ++op) { 1904 TreePatternNode *TPN = T->getChild(op); 1905 while (TPN->ApplyTypeConstraints(P, false)) 1906 /* Resolve all types */; 1907 1908 if (TPN->ContainsUnresolvedType()) { 1909 if (iter == 0) 1910 throw "Value #" + utostr(i) + " of PredicateOperand '" + 1911 DefaultOps[iter][i]->getName() +"' doesn't have a concrete type!"; 1912 else 1913 throw "Value #" + utostr(i) + " of OptionalDefOperand '" + 1914 DefaultOps[iter][i]->getName() +"' doesn't have a concrete type!"; 1915 } 1916 DefaultOpInfo.DefaultOps.push_back(TPN); 1917 } 1918 1919 // Insert it into the DefaultOperands map so we can find it later. 1920 DefaultOperands[DefaultOps[iter][i]] = DefaultOpInfo; 1921 } 1922 } 1923} 1924 1925/// HandleUse - Given "Pat" a leaf in the pattern, check to see if it is an 1926/// instruction input. Return true if this is a real use. 1927static bool HandleUse(TreePattern *I, TreePatternNode *Pat, 1928 std::map<std::string, TreePatternNode*> &InstInputs, 1929 std::vector<Record*> &InstImpInputs) { 1930 // No name -> not interesting. 1931 if (Pat->getName().empty()) { 1932 if (Pat->isLeaf()) { 1933 DefInit *DI = dynamic_cast<DefInit*>(Pat->getLeafValue()); 1934 if (DI && DI->getDef()->isSubClassOf("RegisterClass")) 1935 I->error("Input " + DI->getDef()->getName() + " must be named!"); 1936 else if (DI && DI->getDef()->isSubClassOf("Register")) 1937 InstImpInputs.push_back(DI->getDef()); 1938 } 1939 return false; 1940 } 1941 1942 Record *Rec; 1943 if (Pat->isLeaf()) { 1944 DefInit *DI = dynamic_cast<DefInit*>(Pat->getLeafValue()); 1945 if (!DI) I->error("Input $" + Pat->getName() + " must be an identifier!"); 1946 Rec = DI->getDef(); 1947 } else { 1948 Rec = Pat->getOperator(); 1949 } 1950 1951 // SRCVALUE nodes are ignored. 1952 if (Rec->getName() == "srcvalue") 1953 return false; 1954 1955 TreePatternNode *&Slot = InstInputs[Pat->getName()]; 1956 if (!Slot) { 1957 Slot = Pat; 1958 return true; 1959 } 1960 Record *SlotRec; 1961 if (Slot->isLeaf()) { 1962 SlotRec = dynamic_cast<DefInit*>(Slot->getLeafValue())->getDef(); 1963 } else { 1964 assert(Slot->getNumChildren() == 0 && "can't be a use with children!"); 1965 SlotRec = Slot->getOperator(); 1966 } 1967 1968 // Ensure that the inputs agree if we've already seen this input. 1969 if (Rec != SlotRec) 1970 I->error("All $" + Pat->getName() + " inputs must agree with each other"); 1971 if (Slot->getExtTypes() != Pat->getExtTypes()) 1972 I->error("All $" + Pat->getName() + " inputs must agree with each other"); 1973 return true; 1974} 1975 1976/// FindPatternInputsAndOutputs - Scan the specified TreePatternNode (which is 1977/// part of "I", the instruction), computing the set of inputs and outputs of 1978/// the pattern. Report errors if we see anything naughty. 1979void CodeGenDAGPatterns:: 1980FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, 1981 std::map<std::string, TreePatternNode*> &InstInputs, 1982 std::map<std::string, TreePatternNode*>&InstResults, 1983 std::vector<Record*> &InstImpInputs, 1984 std::vector<Record*> &InstImpResults) { 1985 if (Pat->isLeaf()) { 1986 bool isUse = HandleUse(I, Pat, InstInputs, InstImpInputs); 1987 if (!isUse && Pat->getTransformFn()) 1988 I->error("Cannot specify a transform function for a non-input value!"); 1989 return; 1990 } 1991 1992 if (Pat->getOperator()->getName() == "implicit") { 1993 for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) { 1994 TreePatternNode *Dest = Pat->getChild(i); 1995 if (!Dest->isLeaf()) 1996 I->error("implicitly defined value should be a register!"); 1997 1998 DefInit *Val = dynamic_cast<DefInit*>(Dest->getLeafValue()); 1999 if (!Val || !Val->getDef()->isSubClassOf("Register")) 2000 I->error("implicitly defined value should be a register!"); 2001 InstImpResults.push_back(Val->getDef()); 2002 } 2003 return; 2004 } 2005 2006 if (Pat->getOperator()->getName() != "set") { 2007 // If this is not a set, verify that the children nodes are not void typed, 2008 // and recurse. 2009 for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) { 2010 if (Pat->getChild(i)->getNumTypes() == 0) 2011 I->error("Cannot have void nodes inside of patterns!"); 2012 FindPatternInputsAndOutputs(I, Pat->getChild(i), InstInputs, InstResults, 2013 InstImpInputs, InstImpResults); 2014 } 2015 2016 // If this is a non-leaf node with no children, treat it basically as if 2017 // it were a leaf. This handles nodes like (imm). 2018 bool isUse = HandleUse(I, Pat, InstInputs, InstImpInputs); 2019 2020 if (!isUse && Pat->getTransformFn()) 2021 I->error("Cannot specify a transform function for a non-input value!"); 2022 return; 2023 } 2024 2025 // Otherwise, this is a set, validate and collect instruction results. 2026 if (Pat->getNumChildren() == 0) 2027 I->error("set requires operands!"); 2028 2029 if (Pat->getTransformFn()) 2030 I->error("Cannot specify a transform function on a set node!"); 2031 2032 // Check the set destinations. 2033 unsigned NumDests = Pat->getNumChildren()-1; 2034 for (unsigned i = 0; i != NumDests; ++i) { 2035 TreePatternNode *Dest = Pat->getChild(i); 2036 if (!Dest->isLeaf()) 2037 I->error("set destination should be a register!"); 2038 2039 DefInit *Val = dynamic_cast<DefInit*>(Dest->getLeafValue()); 2040 if (!Val) 2041 I->error("set destination should be a register!"); 2042 2043 if (Val->getDef()->isSubClassOf("RegisterClass") || 2044 Val->getDef()->isSubClassOf("PointerLikeRegClass")) { 2045 if (Dest->getName().empty()) 2046 I->error("set destination must have a name!"); 2047 if (InstResults.count(Dest->getName())) 2048 I->error("cannot set '" + Dest->getName() +"' multiple times"); 2049 InstResults[Dest->getName()] = Dest; 2050 } else if (Val->getDef()->isSubClassOf("Register")) { 2051 InstImpResults.push_back(Val->getDef()); 2052 } else { 2053 I->error("set destination should be a register!"); 2054 } 2055 } 2056 2057 // Verify and collect info from the computation. 2058 FindPatternInputsAndOutputs(I, Pat->getChild(NumDests), 2059 InstInputs, InstResults, 2060 InstImpInputs, InstImpResults); 2061} 2062 2063//===----------------------------------------------------------------------===// 2064// Instruction Analysis 2065//===----------------------------------------------------------------------===// 2066 2067class InstAnalyzer { 2068 const CodeGenDAGPatterns &CDP; 2069 bool &mayStore; 2070 bool &mayLoad; 2071 bool &HasSideEffects; 2072 bool &IsVariadic; 2073public: 2074 InstAnalyzer(const CodeGenDAGPatterns &cdp, 2075 bool &maystore, bool &mayload, bool &hse, bool &isv) 2076 : CDP(cdp), mayStore(maystore), mayLoad(mayload), HasSideEffects(hse), 2077 IsVariadic(isv) { 2078 } 2079 2080 /// Analyze - Analyze the specified instruction, returning true if the 2081 /// instruction had a pattern. 2082 bool Analyze(Record *InstRecord) { 2083 const TreePattern *Pattern = CDP.getInstruction(InstRecord).getPattern(); 2084 if (Pattern == 0) { 2085 HasSideEffects = 1; 2086 return false; // No pattern. 2087 } 2088 2089 // FIXME: Assume only the first tree is the pattern. The others are clobber 2090 // nodes. 2091 AnalyzeNode(Pattern->getTree(0)); 2092 return true; 2093 } 2094 2095private: 2096 void AnalyzeNode(const TreePatternNode *N) { 2097 if (N->isLeaf()) { 2098 if (DefInit *DI = dynamic_cast<DefInit*>(N->getLeafValue())) { 2099 Record *LeafRec = DI->getDef(); 2100 // Handle ComplexPattern leaves. 2101 if (LeafRec->isSubClassOf("ComplexPattern")) { 2102 const ComplexPattern &CP = CDP.getComplexPattern(LeafRec); 2103 if (CP.hasProperty(SDNPMayStore)) mayStore = true; 2104 if (CP.hasProperty(SDNPMayLoad)) mayLoad = true; 2105 if (CP.hasProperty(SDNPSideEffect)) HasSideEffects = true; 2106 } 2107 } 2108 return; 2109 } 2110 2111 // Analyze children. 2112 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 2113 AnalyzeNode(N->getChild(i)); 2114 2115 // Ignore set nodes, which are not SDNodes. 2116 if (N->getOperator()->getName() == "set") 2117 return; 2118 2119 // Get information about the SDNode for the operator. 2120 const SDNodeInfo &OpInfo = CDP.getSDNodeInfo(N->getOperator()); 2121 2122 // Notice properties of the node. 2123 if (OpInfo.hasProperty(SDNPMayStore)) mayStore = true; 2124 if (OpInfo.hasProperty(SDNPMayLoad)) mayLoad = true; 2125 if (OpInfo.hasProperty(SDNPSideEffect)) HasSideEffects = true; 2126 if (OpInfo.hasProperty(SDNPVariadic)) IsVariadic = true; 2127 2128 if (const CodeGenIntrinsic *IntInfo = N->getIntrinsicInfo(CDP)) { 2129 // If this is an intrinsic, analyze it. 2130 if (IntInfo->ModRef >= CodeGenIntrinsic::ReadArgMem) 2131 mayLoad = true;// These may load memory. 2132 2133 if (IntInfo->ModRef >= CodeGenIntrinsic::WriteArgMem) 2134 mayStore = true;// Intrinsics that can write to memory are 'mayStore'. 2135 2136 if (IntInfo->ModRef >= CodeGenIntrinsic::WriteMem) 2137 // WriteMem intrinsics can have other strange effects. 2138 HasSideEffects = true; 2139 } 2140 } 2141 2142}; 2143 2144static void InferFromPattern(const CodeGenInstruction &Inst, 2145 bool &MayStore, bool &MayLoad, 2146 bool &HasSideEffects, bool &IsVariadic, 2147 const CodeGenDAGPatterns &CDP) { 2148 MayStore = MayLoad = HasSideEffects = IsVariadic = false; 2149 2150 bool HadPattern = 2151 InstAnalyzer(CDP, MayStore, MayLoad, HasSideEffects, IsVariadic) 2152 .Analyze(Inst.TheDef); 2153 2154 // InstAnalyzer only correctly analyzes mayStore/mayLoad so far. 2155 if (Inst.mayStore) { // If the .td file explicitly sets mayStore, use it. 2156 // If we decided that this is a store from the pattern, then the .td file 2157 // entry is redundant. 2158 if (MayStore) 2159 fprintf(stderr, 2160 "Warning: mayStore flag explicitly set on instruction '%s'" 2161 " but flag already inferred from pattern.\n", 2162 Inst.TheDef->getName().c_str()); 2163 MayStore = true; 2164 } 2165 2166 if (Inst.mayLoad) { // If the .td file explicitly sets mayLoad, use it. 2167 // If we decided that this is a load from the pattern, then the .td file 2168 // entry is redundant. 2169 if (MayLoad) 2170 fprintf(stderr, 2171 "Warning: mayLoad flag explicitly set on instruction '%s'" 2172 " but flag already inferred from pattern.\n", 2173 Inst.TheDef->getName().c_str()); 2174 MayLoad = true; 2175 } 2176 2177 if (Inst.neverHasSideEffects) { 2178 if (HadPattern) 2179 fprintf(stderr, "Warning: neverHasSideEffects set on instruction '%s' " 2180 "which already has a pattern\n", Inst.TheDef->getName().c_str()); 2181 HasSideEffects = false; 2182 } 2183 2184 if (Inst.hasSideEffects) { 2185 if (HasSideEffects) 2186 fprintf(stderr, "Warning: hasSideEffects set on instruction '%s' " 2187 "which already inferred this.\n", Inst.TheDef->getName().c_str()); 2188 HasSideEffects = true; 2189 } 2190 2191 if (Inst.isVariadic) 2192 IsVariadic = true; // Can warn if we want. 2193} 2194 2195/// ParseInstructions - Parse all of the instructions, inlining and resolving 2196/// any fragments involved. This populates the Instructions list with fully 2197/// resolved instructions. 2198void CodeGenDAGPatterns::ParseInstructions() { 2199 std::vector<Record*> Instrs = Records.getAllDerivedDefinitions("Instruction"); 2200 2201 for (unsigned i = 0, e = Instrs.size(); i != e; ++i) { 2202 ListInit *LI = 0; 2203 2204 if (dynamic_cast<ListInit*>(Instrs[i]->getValueInit("Pattern"))) 2205 LI = Instrs[i]->getValueAsListInit("Pattern"); 2206 2207 // If there is no pattern, only collect minimal information about the 2208 // instruction for its operand list. We have to assume that there is one 2209 // result, as we have no detailed info. 2210 if (!LI || LI->getSize() == 0) { 2211 std::vector<Record*> Results; 2212 std::vector<Record*> Operands; 2213 2214 CodeGenInstruction &InstInfo = Target.getInstruction(Instrs[i]); 2215 2216 if (InstInfo.OperandList.size() != 0) { 2217 if (InstInfo.NumDefs == 0) { 2218 // These produce no results 2219 for (unsigned j = 0, e = InstInfo.OperandList.size(); j < e; ++j) 2220 Operands.push_back(InstInfo.OperandList[j].Rec); 2221 } else { 2222 // Assume the first operand is the result. 2223 Results.push_back(InstInfo.OperandList[0].Rec); 2224 2225 // The rest are inputs. 2226 for (unsigned j = 1, e = InstInfo.OperandList.size(); j < e; ++j) 2227 Operands.push_back(InstInfo.OperandList[j].Rec); 2228 } 2229 } 2230 2231 // Create and insert the instruction. 2232 std::vector<Record*> ImpResults; 2233 std::vector<Record*> ImpOperands; 2234 Instructions.insert(std::make_pair(Instrs[i], 2235 DAGInstruction(0, Results, Operands, ImpResults, 2236 ImpOperands))); 2237 continue; // no pattern. 2238 } 2239 2240 // Parse the instruction. 2241 TreePattern *I = new TreePattern(Instrs[i], LI, true, *this); 2242 // Inline pattern fragments into it. 2243 I->InlinePatternFragments(); 2244 2245 // Infer as many types as possible. If we cannot infer all of them, we can 2246 // never do anything with this instruction pattern: report it to the user. 2247 if (!I->InferAllTypes()) 2248 I->error("Could not infer all types in pattern!"); 2249 2250 // InstInputs - Keep track of all of the inputs of the instruction, along 2251 // with the record they are declared as. 2252 std::map<std::string, TreePatternNode*> InstInputs; 2253 2254 // InstResults - Keep track of all the virtual registers that are 'set' 2255 // in the instruction, including what reg class they are. 2256 std::map<std::string, TreePatternNode*> InstResults; 2257 2258 std::vector<Record*> InstImpInputs; 2259 std::vector<Record*> InstImpResults; 2260 2261 // Verify that the top-level forms in the instruction are of void type, and 2262 // fill in the InstResults map. 2263 for (unsigned j = 0, e = I->getNumTrees(); j != e; ++j) { 2264 TreePatternNode *Pat = I->getTree(j); 2265 if (Pat->getNumTypes() != 0) 2266 I->error("Top-level forms in instruction pattern should have" 2267 " void types"); 2268 2269 // Find inputs and outputs, and verify the structure of the uses/defs. 2270 FindPatternInputsAndOutputs(I, Pat, InstInputs, InstResults, 2271 InstImpInputs, InstImpResults); 2272 } 2273 2274 // Now that we have inputs and outputs of the pattern, inspect the operands 2275 // list for the instruction. This determines the order that operands are 2276 // added to the machine instruction the node corresponds to. 2277 unsigned NumResults = InstResults.size(); 2278 2279 // Parse the operands list from the (ops) list, validating it. 2280 assert(I->getArgList().empty() && "Args list should still be empty here!"); 2281 CodeGenInstruction &CGI = Target.getInstruction(Instrs[i]); 2282 2283 // Check that all of the results occur first in the list. 2284 std::vector<Record*> Results; 2285 TreePatternNode *Res0Node = 0; 2286 for (unsigned i = 0; i != NumResults; ++i) { 2287 if (i == CGI.OperandList.size()) 2288 I->error("'" + InstResults.begin()->first + 2289 "' set but does not appear in operand list!"); 2290 const std::string &OpName = CGI.OperandList[i].Name; 2291 2292 // Check that it exists in InstResults. 2293 TreePatternNode *RNode = InstResults[OpName]; 2294 if (RNode == 0) 2295 I->error("Operand $" + OpName + " does not exist in operand list!"); 2296 2297 if (i == 0) 2298 Res0Node = RNode; 2299 Record *R = dynamic_cast<DefInit*>(RNode->getLeafValue())->getDef(); 2300 if (R == 0) 2301 I->error("Operand $" + OpName + " should be a set destination: all " 2302 "outputs must occur before inputs in operand list!"); 2303 2304 if (CGI.OperandList[i].Rec != R) 2305 I->error("Operand $" + OpName + " class mismatch!"); 2306 2307 // Remember the return type. 2308 Results.push_back(CGI.OperandList[i].Rec); 2309 2310 // Okay, this one checks out. 2311 InstResults.erase(OpName); 2312 } 2313 2314 // Loop over the inputs next. Make a copy of InstInputs so we can destroy 2315 // the copy while we're checking the inputs. 2316 std::map<std::string, TreePatternNode*> InstInputsCheck(InstInputs); 2317 2318 std::vector<TreePatternNode*> ResultNodeOperands; 2319 std::vector<Record*> Operands; 2320 for (unsigned i = NumResults, e = CGI.OperandList.size(); i != e; ++i) { 2321 CodeGenInstruction::OperandInfo &Op = CGI.OperandList[i]; 2322 const std::string &OpName = Op.Name; 2323 if (OpName.empty()) 2324 I->error("Operand #" + utostr(i) + " in operands list has no name!"); 2325 2326 if (!InstInputsCheck.count(OpName)) { 2327 // If this is an predicate operand or optional def operand with an 2328 // DefaultOps set filled in, we can ignore this. When we codegen it, 2329 // we will do so as always executed. 2330 if (Op.Rec->isSubClassOf("PredicateOperand") || 2331 Op.Rec->isSubClassOf("OptionalDefOperand")) { 2332 // Does it have a non-empty DefaultOps field? If so, ignore this 2333 // operand. 2334 if (!getDefaultOperand(Op.Rec).DefaultOps.empty()) 2335 continue; 2336 } 2337 I->error("Operand $" + OpName + 2338 " does not appear in the instruction pattern"); 2339 } 2340 TreePatternNode *InVal = InstInputsCheck[OpName]; 2341 InstInputsCheck.erase(OpName); // It occurred, remove from map. 2342 2343 if (InVal->isLeaf() && 2344 dynamic_cast<DefInit*>(InVal->getLeafValue())) { 2345 Record *InRec = static_cast<DefInit*>(InVal->getLeafValue())->getDef(); 2346 if (Op.Rec != InRec && !InRec->isSubClassOf("ComplexPattern")) 2347 I->error("Operand $" + OpName + "'s register class disagrees" 2348 " between the operand and pattern"); 2349 } 2350 Operands.push_back(Op.Rec); 2351 2352 // Construct the result for the dest-pattern operand list. 2353 TreePatternNode *OpNode = InVal->clone(); 2354 2355 // No predicate is useful on the result. 2356 OpNode->clearPredicateFns(); 2357 2358 // Promote the xform function to be an explicit node if set. 2359 if (Record *Xform = OpNode->getTransformFn()) { 2360 OpNode->setTransformFn(0); 2361 std::vector<TreePatternNode*> Children; 2362 Children.push_back(OpNode); 2363 OpNode = new TreePatternNode(Xform, Children, OpNode->getNumTypes()); 2364 } 2365 2366 ResultNodeOperands.push_back(OpNode); 2367 } 2368 2369 if (!InstInputsCheck.empty()) 2370 I->error("Input operand $" + InstInputsCheck.begin()->first + 2371 " occurs in pattern but not in operands list!"); 2372 2373 TreePatternNode *ResultPattern = 2374 new TreePatternNode(I->getRecord(), ResultNodeOperands, 2375 GetNumNodeResults(I->getRecord(), *this)); 2376 // Copy fully inferred output node type to instruction result pattern. 2377 for (unsigned i = 0; i != NumResults; ++i) 2378 ResultPattern->setType(i, Res0Node->getExtType(i)); 2379 2380 // Create and insert the instruction. 2381 // FIXME: InstImpResults and InstImpInputs should not be part of 2382 // DAGInstruction. 2383 DAGInstruction TheInst(I, Results, Operands, InstImpResults, InstImpInputs); 2384 Instructions.insert(std::make_pair(I->getRecord(), TheInst)); 2385 2386 // Use a temporary tree pattern to infer all types and make sure that the 2387 // constructed result is correct. This depends on the instruction already 2388 // being inserted into the Instructions map. 2389 TreePattern Temp(I->getRecord(), ResultPattern, false, *this); 2390 Temp.InferAllTypes(&I->getNamedNodesMap()); 2391 2392 DAGInstruction &TheInsertedInst = Instructions.find(I->getRecord())->second; 2393 TheInsertedInst.setResultPattern(Temp.getOnlyTree()); 2394 2395 DEBUG(I->dump()); 2396 } 2397 2398 // If we can, convert the instructions to be patterns that are matched! 2399 for (std::map<Record*, DAGInstruction, RecordPtrCmp>::iterator II = 2400 Instructions.begin(), 2401 E = Instructions.end(); II != E; ++II) { 2402 DAGInstruction &TheInst = II->second; 2403 const TreePattern *I = TheInst.getPattern(); 2404 if (I == 0) continue; // No pattern. 2405 2406 // FIXME: Assume only the first tree is the pattern. The others are clobber 2407 // nodes. 2408 TreePatternNode *Pattern = I->getTree(0); 2409 TreePatternNode *SrcPattern; 2410 if (Pattern->getOperator()->getName() == "set") { 2411 SrcPattern = Pattern->getChild(Pattern->getNumChildren()-1)->clone(); 2412 } else{ 2413 // Not a set (store or something?) 2414 SrcPattern = Pattern; 2415 } 2416 2417 Record *Instr = II->first; 2418 AddPatternToMatch(I, 2419 PatternToMatch(Instr->getValueAsListInit("Predicates"), 2420 SrcPattern, 2421 TheInst.getResultPattern(), 2422 TheInst.getImpResults(), 2423 Instr->getValueAsInt("AddedComplexity"), 2424 Instr->getID())); 2425 } 2426} 2427 2428 2429typedef std::pair<const TreePatternNode*, unsigned> NameRecord; 2430 2431static void FindNames(const TreePatternNode *P, 2432 std::map<std::string, NameRecord> &Names, 2433 const TreePattern *PatternTop) { 2434 if (!P->getName().empty()) { 2435 NameRecord &Rec = Names[P->getName()]; 2436 // If this is the first instance of the name, remember the node. 2437 if (Rec.second++ == 0) 2438 Rec.first = P; 2439 else if (Rec.first->getExtTypes() != P->getExtTypes()) 2440 PatternTop->error("repetition of value: $" + P->getName() + 2441 " where different uses have different types!"); 2442 } 2443 2444 if (!P->isLeaf()) { 2445 for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) 2446 FindNames(P->getChild(i), Names, PatternTop); 2447 } 2448} 2449 2450void CodeGenDAGPatterns::AddPatternToMatch(const TreePattern *Pattern, 2451 const PatternToMatch &PTM) { 2452 // Do some sanity checking on the pattern we're about to match. 2453 std::string Reason; 2454 if (!PTM.getSrcPattern()->canPatternMatch(Reason, *this)) 2455 Pattern->error("Pattern can never match: " + Reason); 2456 2457 // If the source pattern's root is a complex pattern, that complex pattern 2458 // must specify the nodes it can potentially match. 2459 if (const ComplexPattern *CP = 2460 PTM.getSrcPattern()->getComplexPatternInfo(*this)) 2461 if (CP->getRootNodes().empty()) 2462 Pattern->error("ComplexPattern at root must specify list of opcodes it" 2463 " could match"); 2464 2465 2466 // Find all of the named values in the input and output, ensure they have the 2467 // same type. 2468 std::map<std::string, NameRecord> SrcNames, DstNames; 2469 FindNames(PTM.getSrcPattern(), SrcNames, Pattern); 2470 FindNames(PTM.getDstPattern(), DstNames, Pattern); 2471 2472 // Scan all of the named values in the destination pattern, rejecting them if 2473 // they don't exist in the input pattern. 2474 for (std::map<std::string, NameRecord>::iterator 2475 I = DstNames.begin(), E = DstNames.end(); I != E; ++I) { 2476 if (SrcNames[I->first].first == 0) 2477 Pattern->error("Pattern has input without matching name in output: $" + 2478 I->first); 2479 } 2480 2481 // Scan all of the named values in the source pattern, rejecting them if the 2482 // name isn't used in the dest, and isn't used to tie two values together. 2483 for (std::map<std::string, NameRecord>::iterator 2484 I = SrcNames.begin(), E = SrcNames.end(); I != E; ++I) 2485 if (DstNames[I->first].first == 0 && SrcNames[I->first].second == 1) 2486 Pattern->error("Pattern has dead named input: $" + I->first); 2487 2488 PatternsToMatch.push_back(PTM); 2489} 2490 2491 2492 2493void CodeGenDAGPatterns::InferInstructionFlags() { 2494 const std::vector<const CodeGenInstruction*> &Instructions = 2495 Target.getInstructionsByEnumValue(); 2496 for (unsigned i = 0, e = Instructions.size(); i != e; ++i) { 2497 CodeGenInstruction &InstInfo = 2498 const_cast<CodeGenInstruction &>(*Instructions[i]); 2499 // Determine properties of the instruction from its pattern. 2500 bool MayStore, MayLoad, HasSideEffects, IsVariadic; 2501 InferFromPattern(InstInfo, MayStore, MayLoad, HasSideEffects, IsVariadic, 2502 *this); 2503 InstInfo.mayStore = MayStore; 2504 InstInfo.mayLoad = MayLoad; 2505 InstInfo.hasSideEffects = HasSideEffects; 2506 InstInfo.isVariadic = IsVariadic; 2507 } 2508} 2509 2510/// Given a pattern result with an unresolved type, see if we can find one 2511/// instruction with an unresolved result type. Force this result type to an 2512/// arbitrary element if it's possible types to converge results. 2513static bool ForceArbitraryInstResultType(TreePatternNode *N, TreePattern &TP) { 2514 if (N->isLeaf()) 2515 return false; 2516 2517 // Analyze children. 2518 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 2519 if (ForceArbitraryInstResultType(N->getChild(i), TP)) 2520 return true; 2521 2522 if (!N->getOperator()->isSubClassOf("Instruction")) 2523 return false; 2524 2525 // If this type is already concrete or completely unknown we can't do 2526 // anything. 2527 for (unsigned i = 0, e = N->getNumTypes(); i != e; ++i) { 2528 if (N->getExtType(i).isCompletelyUnknown() || N->getExtType(i).isConcrete()) 2529 continue; 2530 2531 // Otherwise, force its type to the first possibility (an arbitrary choice). 2532 if (N->getExtType(i).MergeInTypeInfo(N->getExtType(i).getTypeList()[0], TP)) 2533 return true; 2534 } 2535 2536 return false; 2537} 2538 2539void CodeGenDAGPatterns::ParsePatterns() { 2540 std::vector<Record*> Patterns = Records.getAllDerivedDefinitions("Pattern"); 2541 2542 for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { 2543 Record *CurPattern = Patterns[i]; 2544 DagInit *Tree = CurPattern->getValueAsDag("PatternToMatch"); 2545 DefInit *OpDef = dynamic_cast<DefInit*>(Tree->getOperator()); 2546 Record *Operator = OpDef->getDef(); 2547 TreePattern *Pattern; 2548 if (Operator->getName() != "parallel") 2549 Pattern = new TreePattern(CurPattern, Tree, true, *this); 2550 else { 2551 std::vector<Init*> Values; 2552 RecTy *ListTy = 0; 2553 for (unsigned j = 0, ee = Tree->getNumArgs(); j != ee; ++j) { 2554 Values.push_back(Tree->getArg(j)); 2555 TypedInit *TArg = dynamic_cast<TypedInit*>(Tree->getArg(j)); 2556 if (TArg == 0) { 2557 errs() << "In dag: " << Tree->getAsString(); 2558 errs() << " -- Untyped argument in pattern\n"; 2559 assert(0 && "Untyped argument in pattern"); 2560 } 2561 if (ListTy != 0) { 2562 ListTy = resolveTypes(ListTy, TArg->getType()); 2563 if (ListTy == 0) { 2564 errs() << "In dag: " << Tree->getAsString(); 2565 errs() << " -- Incompatible types in pattern arguments\n"; 2566 assert(0 && "Incompatible types in pattern arguments"); 2567 } 2568 } 2569 else { 2570 ListTy = TArg->getType(); 2571 } 2572 } 2573 ListInit *LI = new ListInit(Values, new ListRecTy(ListTy)); 2574 Pattern = new TreePattern(CurPattern, LI, true, *this); 2575 } 2576 2577 // Inline pattern fragments into it. 2578 Pattern->InlinePatternFragments(); 2579 2580 ListInit *LI = CurPattern->getValueAsListInit("ResultInstrs"); 2581 if (LI->getSize() == 0) continue; // no pattern. 2582 2583 // Parse the instruction. 2584 TreePattern *Result = new TreePattern(CurPattern, LI, false, *this); 2585 2586 // Inline pattern fragments into it. 2587 Result->InlinePatternFragments(); 2588 2589 if (Result->getNumTrees() != 1) 2590 Result->error("Cannot handle instructions producing instructions " 2591 "with temporaries yet!"); 2592 2593 bool IterateInference; 2594 bool InferredAllPatternTypes, InferredAllResultTypes; 2595 do { 2596 // Infer as many types as possible. If we cannot infer all of them, we 2597 // can never do anything with this pattern: report it to the user. 2598 InferredAllPatternTypes = 2599 Pattern->InferAllTypes(&Pattern->getNamedNodesMap()); 2600 2601 // Infer as many types as possible. If we cannot infer all of them, we 2602 // can never do anything with this pattern: report it to the user. 2603 InferredAllResultTypes = 2604 Result->InferAllTypes(&Pattern->getNamedNodesMap()); 2605 2606 IterateInference = false; 2607 2608 // Apply the type of the result to the source pattern. This helps us 2609 // resolve cases where the input type is known to be a pointer type (which 2610 // is considered resolved), but the result knows it needs to be 32- or 2611 // 64-bits. Infer the other way for good measure. 2612 for (unsigned i = 0, e = std::min(Result->getTree(0)->getNumTypes(), 2613 Pattern->getTree(0)->getNumTypes()); 2614 i != e; ++i) { 2615 IterateInference = Pattern->getTree(0)-> 2616 UpdateNodeType(i, Result->getTree(0)->getExtType(i), *Result); 2617 IterateInference |= Result->getTree(0)-> 2618 UpdateNodeType(i, Pattern->getTree(0)->getExtType(i), *Result); 2619 } 2620 2621 // If our iteration has converged and the input pattern's types are fully 2622 // resolved but the result pattern is not fully resolved, we may have a 2623 // situation where we have two instructions in the result pattern and 2624 // the instructions require a common register class, but don't care about 2625 // what actual MVT is used. This is actually a bug in our modelling: 2626 // output patterns should have register classes, not MVTs. 2627 // 2628 // In any case, to handle this, we just go through and disambiguate some 2629 // arbitrary types to the result pattern's nodes. 2630 if (!IterateInference && InferredAllPatternTypes && 2631 !InferredAllResultTypes) 2632 IterateInference = ForceArbitraryInstResultType(Result->getTree(0), 2633 *Result); 2634 } while (IterateInference); 2635 2636 // Verify that we inferred enough types that we can do something with the 2637 // pattern and result. If these fire the user has to add type casts. 2638 if (!InferredAllPatternTypes) 2639 Pattern->error("Could not infer all types in pattern!"); 2640 if (!InferredAllResultTypes) { 2641 Pattern->dump(); 2642 Result->error("Could not infer all types in pattern result!"); 2643 } 2644 2645 // Validate that the input pattern is correct. 2646 std::map<std::string, TreePatternNode*> InstInputs; 2647 std::map<std::string, TreePatternNode*> InstResults; 2648 std::vector<Record*> InstImpInputs; 2649 std::vector<Record*> InstImpResults; 2650 for (unsigned j = 0, ee = Pattern->getNumTrees(); j != ee; ++j) 2651 FindPatternInputsAndOutputs(Pattern, Pattern->getTree(j), 2652 InstInputs, InstResults, 2653 InstImpInputs, InstImpResults); 2654 2655 // Promote the xform function to be an explicit node if set. 2656 TreePatternNode *DstPattern = Result->getOnlyTree(); 2657 std::vector<TreePatternNode*> ResultNodeOperands; 2658 for (unsigned ii = 0, ee = DstPattern->getNumChildren(); ii != ee; ++ii) { 2659 TreePatternNode *OpNode = DstPattern->getChild(ii); 2660 if (Record *Xform = OpNode->getTransformFn()) { 2661 OpNode->setTransformFn(0); 2662 std::vector<TreePatternNode*> Children; 2663 Children.push_back(OpNode); 2664 OpNode = new TreePatternNode(Xform, Children, OpNode->getNumTypes()); 2665 } 2666 ResultNodeOperands.push_back(OpNode); 2667 } 2668 DstPattern = Result->getOnlyTree(); 2669 if (!DstPattern->isLeaf()) 2670 DstPattern = new TreePatternNode(DstPattern->getOperator(), 2671 ResultNodeOperands, 2672 DstPattern->getNumTypes()); 2673 2674 for (unsigned i = 0, e = Result->getOnlyTree()->getNumTypes(); i != e; ++i) 2675 DstPattern->setType(i, Result->getOnlyTree()->getExtType(i)); 2676 2677 TreePattern Temp(Result->getRecord(), DstPattern, false, *this); 2678 Temp.InferAllTypes(); 2679 2680 2681 AddPatternToMatch(Pattern, 2682 PatternToMatch(CurPattern->getValueAsListInit("Predicates"), 2683 Pattern->getTree(0), 2684 Temp.getOnlyTree(), InstImpResults, 2685 CurPattern->getValueAsInt("AddedComplexity"), 2686 CurPattern->getID())); 2687 } 2688} 2689 2690/// CombineChildVariants - Given a bunch of permutations of each child of the 2691/// 'operator' node, put them together in all possible ways. 2692static void CombineChildVariants(TreePatternNode *Orig, 2693 const std::vector<std::vector<TreePatternNode*> > &ChildVariants, 2694 std::vector<TreePatternNode*> &OutVariants, 2695 CodeGenDAGPatterns &CDP, 2696 const MultipleUseVarSet &DepVars) { 2697 // Make sure that each operand has at least one variant to choose from. 2698 for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i) 2699 if (ChildVariants[i].empty()) 2700 return; 2701 2702 // The end result is an all-pairs construction of the resultant pattern. 2703 std::vector<unsigned> Idxs; 2704 Idxs.resize(ChildVariants.size()); 2705 bool NotDone; 2706 do { 2707#ifndef NDEBUG 2708 DEBUG(if (!Idxs.empty()) { 2709 errs() << Orig->getOperator()->getName() << ": Idxs = [ "; 2710 for (unsigned i = 0; i < Idxs.size(); ++i) { 2711 errs() << Idxs[i] << " "; 2712 } 2713 errs() << "]\n"; 2714 }); 2715#endif 2716 // Create the variant and add it to the output list. 2717 std::vector<TreePatternNode*> NewChildren; 2718 for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i) 2719 NewChildren.push_back(ChildVariants[i][Idxs[i]]); 2720 TreePatternNode *R = new TreePatternNode(Orig->getOperator(), NewChildren, 2721 Orig->getNumTypes()); 2722 2723 // Copy over properties. 2724 R->setName(Orig->getName()); 2725 R->setPredicateFns(Orig->getPredicateFns()); 2726 R->setTransformFn(Orig->getTransformFn()); 2727 for (unsigned i = 0, e = Orig->getNumTypes(); i != e; ++i) 2728 R->setType(i, Orig->getExtType(i)); 2729 2730 // If this pattern cannot match, do not include it as a variant. 2731 std::string ErrString; 2732 if (!R->canPatternMatch(ErrString, CDP)) { 2733 delete R; 2734 } else { 2735 bool AlreadyExists = false; 2736 2737 // Scan to see if this pattern has already been emitted. We can get 2738 // duplication due to things like commuting: 2739 // (and GPRC:$a, GPRC:$b) -> (and GPRC:$b, GPRC:$a) 2740 // which are the same pattern. Ignore the dups. 2741 for (unsigned i = 0, e = OutVariants.size(); i != e; ++i) 2742 if (R->isIsomorphicTo(OutVariants[i], DepVars)) { 2743 AlreadyExists = true; 2744 break; 2745 } 2746 2747 if (AlreadyExists) 2748 delete R; 2749 else 2750 OutVariants.push_back(R); 2751 } 2752 2753 // Increment indices to the next permutation by incrementing the 2754 // indicies from last index backward, e.g., generate the sequence 2755 // [0, 0], [0, 1], [1, 0], [1, 1]. 2756 int IdxsIdx; 2757 for (IdxsIdx = Idxs.size() - 1; IdxsIdx >= 0; --IdxsIdx) { 2758 if (++Idxs[IdxsIdx] == ChildVariants[IdxsIdx].size()) 2759 Idxs[IdxsIdx] = 0; 2760 else 2761 break; 2762 } 2763 NotDone = (IdxsIdx >= 0); 2764 } while (NotDone); 2765} 2766 2767/// CombineChildVariants - A helper function for binary operators. 2768/// 2769static void CombineChildVariants(TreePatternNode *Orig, 2770 const std::vector<TreePatternNode*> &LHS, 2771 const std::vector<TreePatternNode*> &RHS, 2772 std::vector<TreePatternNode*> &OutVariants, 2773 CodeGenDAGPatterns &CDP, 2774 const MultipleUseVarSet &DepVars) { 2775 std::vector<std::vector<TreePatternNode*> > ChildVariants; 2776 ChildVariants.push_back(LHS); 2777 ChildVariants.push_back(RHS); 2778 CombineChildVariants(Orig, ChildVariants, OutVariants, CDP, DepVars); 2779} 2780 2781 2782static void GatherChildrenOfAssociativeOpcode(TreePatternNode *N, 2783 std::vector<TreePatternNode *> &Children) { 2784 assert(N->getNumChildren()==2 &&"Associative but doesn't have 2 children!"); 2785 Record *Operator = N->getOperator(); 2786 2787 // Only permit raw nodes. 2788 if (!N->getName().empty() || !N->getPredicateFns().empty() || 2789 N->getTransformFn()) { 2790 Children.push_back(N); 2791 return; 2792 } 2793 2794 if (N->getChild(0)->isLeaf() || N->getChild(0)->getOperator() != Operator) 2795 Children.push_back(N->getChild(0)); 2796 else 2797 GatherChildrenOfAssociativeOpcode(N->getChild(0), Children); 2798 2799 if (N->getChild(1)->isLeaf() || N->getChild(1)->getOperator() != Operator) 2800 Children.push_back(N->getChild(1)); 2801 else 2802 GatherChildrenOfAssociativeOpcode(N->getChild(1), Children); 2803} 2804 2805/// GenerateVariantsOf - Given a pattern N, generate all permutations we can of 2806/// the (potentially recursive) pattern by using algebraic laws. 2807/// 2808static void GenerateVariantsOf(TreePatternNode *N, 2809 std::vector<TreePatternNode*> &OutVariants, 2810 CodeGenDAGPatterns &CDP, 2811 const MultipleUseVarSet &DepVars) { 2812 // We cannot permute leaves. 2813 if (N->isLeaf()) { 2814 OutVariants.push_back(N); 2815 return; 2816 } 2817 2818 // Look up interesting info about the node. 2819 const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(N->getOperator()); 2820 2821 // If this node is associative, re-associate. 2822 if (NodeInfo.hasProperty(SDNPAssociative)) { 2823 // Re-associate by pulling together all of the linked operators 2824 std::vector<TreePatternNode*> MaximalChildren; 2825 GatherChildrenOfAssociativeOpcode(N, MaximalChildren); 2826 2827 // Only handle child sizes of 3. Otherwise we'll end up trying too many 2828 // permutations. 2829 if (MaximalChildren.size() == 3) { 2830 // Find the variants of all of our maximal children. 2831 std::vector<TreePatternNode*> AVariants, BVariants, CVariants; 2832 GenerateVariantsOf(MaximalChildren[0], AVariants, CDP, DepVars); 2833 GenerateVariantsOf(MaximalChildren[1], BVariants, CDP, DepVars); 2834 GenerateVariantsOf(MaximalChildren[2], CVariants, CDP, DepVars); 2835 2836 // There are only two ways we can permute the tree: 2837 // (A op B) op C and A op (B op C) 2838 // Within these forms, we can also permute A/B/C. 2839 2840 // Generate legal pair permutations of A/B/C. 2841 std::vector<TreePatternNode*> ABVariants; 2842 std::vector<TreePatternNode*> BAVariants; 2843 std::vector<TreePatternNode*> ACVariants; 2844 std::vector<TreePatternNode*> CAVariants; 2845 std::vector<TreePatternNode*> BCVariants; 2846 std::vector<TreePatternNode*> CBVariants; 2847 CombineChildVariants(N, AVariants, BVariants, ABVariants, CDP, DepVars); 2848 CombineChildVariants(N, BVariants, AVariants, BAVariants, CDP, DepVars); 2849 CombineChildVariants(N, AVariants, CVariants, ACVariants, CDP, DepVars); 2850 CombineChildVariants(N, CVariants, AVariants, CAVariants, CDP, DepVars); 2851 CombineChildVariants(N, BVariants, CVariants, BCVariants, CDP, DepVars); 2852 CombineChildVariants(N, CVariants, BVariants, CBVariants, CDP, DepVars); 2853 2854 // Combine those into the result: (x op x) op x 2855 CombineChildVariants(N, ABVariants, CVariants, OutVariants, CDP, DepVars); 2856 CombineChildVariants(N, BAVariants, CVariants, OutVariants, CDP, DepVars); 2857 CombineChildVariants(N, ACVariants, BVariants, OutVariants, CDP, DepVars); 2858 CombineChildVariants(N, CAVariants, BVariants, OutVariants, CDP, DepVars); 2859 CombineChildVariants(N, BCVariants, AVariants, OutVariants, CDP, DepVars); 2860 CombineChildVariants(N, CBVariants, AVariants, OutVariants, CDP, DepVars); 2861 2862 // Combine those into the result: x op (x op x) 2863 CombineChildVariants(N, CVariants, ABVariants, OutVariants, CDP, DepVars); 2864 CombineChildVariants(N, CVariants, BAVariants, OutVariants, CDP, DepVars); 2865 CombineChildVariants(N, BVariants, ACVariants, OutVariants, CDP, DepVars); 2866 CombineChildVariants(N, BVariants, CAVariants, OutVariants, CDP, DepVars); 2867 CombineChildVariants(N, AVariants, BCVariants, OutVariants, CDP, DepVars); 2868 CombineChildVariants(N, AVariants, CBVariants, OutVariants, CDP, DepVars); 2869 return; 2870 } 2871 } 2872 2873 // Compute permutations of all children. 2874 std::vector<std::vector<TreePatternNode*> > ChildVariants; 2875 ChildVariants.resize(N->getNumChildren()); 2876 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 2877 GenerateVariantsOf(N->getChild(i), ChildVariants[i], CDP, DepVars); 2878 2879 // Build all permutations based on how the children were formed. 2880 CombineChildVariants(N, ChildVariants, OutVariants, CDP, DepVars); 2881 2882 // If this node is commutative, consider the commuted order. 2883 bool isCommIntrinsic = N->isCommutativeIntrinsic(CDP); 2884 if (NodeInfo.hasProperty(SDNPCommutative) || isCommIntrinsic) { 2885 assert((N->getNumChildren()==2 || isCommIntrinsic) && 2886 "Commutative but doesn't have 2 children!"); 2887 // Don't count children which are actually register references. 2888 unsigned NC = 0; 2889 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { 2890 TreePatternNode *Child = N->getChild(i); 2891 if (Child->isLeaf()) 2892 if (DefInit *DI = dynamic_cast<DefInit*>(Child->getLeafValue())) { 2893 Record *RR = DI->getDef(); 2894 if (RR->isSubClassOf("Register")) 2895 continue; 2896 } 2897 NC++; 2898 } 2899 // Consider the commuted order. 2900 if (isCommIntrinsic) { 2901 // Commutative intrinsic. First operand is the intrinsic id, 2nd and 3rd 2902 // operands are the commutative operands, and there might be more operands 2903 // after those. 2904 assert(NC >= 3 && 2905 "Commutative intrinsic should have at least 3 childrean!"); 2906 std::vector<std::vector<TreePatternNode*> > Variants; 2907 Variants.push_back(ChildVariants[0]); // Intrinsic id. 2908 Variants.push_back(ChildVariants[2]); 2909 Variants.push_back(ChildVariants[1]); 2910 for (unsigned i = 3; i != NC; ++i) 2911 Variants.push_back(ChildVariants[i]); 2912 CombineChildVariants(N, Variants, OutVariants, CDP, DepVars); 2913 } else if (NC == 2) 2914 CombineChildVariants(N, ChildVariants[1], ChildVariants[0], 2915 OutVariants, CDP, DepVars); 2916 } 2917} 2918 2919 2920// GenerateVariants - Generate variants. For example, commutative patterns can 2921// match multiple ways. Add them to PatternsToMatch as well. 2922void CodeGenDAGPatterns::GenerateVariants() { 2923 DEBUG(errs() << "Generating instruction variants.\n"); 2924 2925 // Loop over all of the patterns we've collected, checking to see if we can 2926 // generate variants of the instruction, through the exploitation of 2927 // identities. This permits the target to provide aggressive matching without 2928 // the .td file having to contain tons of variants of instructions. 2929 // 2930 // Note that this loop adds new patterns to the PatternsToMatch list, but we 2931 // intentionally do not reconsider these. Any variants of added patterns have 2932 // already been added. 2933 // 2934 for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) { 2935 MultipleUseVarSet DepVars; 2936 std::vector<TreePatternNode*> Variants; 2937 FindDepVars(PatternsToMatch[i].getSrcPattern(), DepVars); 2938 DEBUG(errs() << "Dependent/multiply used variables: "); 2939 DEBUG(DumpDepVars(DepVars)); 2940 DEBUG(errs() << "\n"); 2941 GenerateVariantsOf(PatternsToMatch[i].getSrcPattern(), Variants, *this, DepVars); 2942 2943 assert(!Variants.empty() && "Must create at least original variant!"); 2944 Variants.erase(Variants.begin()); // Remove the original pattern. 2945 2946 if (Variants.empty()) // No variants for this pattern. 2947 continue; 2948 2949 DEBUG(errs() << "FOUND VARIANTS OF: "; 2950 PatternsToMatch[i].getSrcPattern()->dump(); 2951 errs() << "\n"); 2952 2953 for (unsigned v = 0, e = Variants.size(); v != e; ++v) { 2954 TreePatternNode *Variant = Variants[v]; 2955 2956 DEBUG(errs() << " VAR#" << v << ": "; 2957 Variant->dump(); 2958 errs() << "\n"); 2959 2960 // Scan to see if an instruction or explicit pattern already matches this. 2961 bool AlreadyExists = false; 2962 for (unsigned p = 0, e = PatternsToMatch.size(); p != e; ++p) { 2963 // Skip if the top level predicates do not match. 2964 if (PatternsToMatch[i].getPredicates() != 2965 PatternsToMatch[p].getPredicates()) 2966 continue; 2967 // Check to see if this variant already exists. 2968 if (Variant->isIsomorphicTo(PatternsToMatch[p].getSrcPattern(), DepVars)) { 2969 DEBUG(errs() << " *** ALREADY EXISTS, ignoring variant.\n"); 2970 AlreadyExists = true; 2971 break; 2972 } 2973 } 2974 // If we already have it, ignore the variant. 2975 if (AlreadyExists) continue; 2976 2977 // Otherwise, add it to the list of patterns we have. 2978 PatternsToMatch. 2979 push_back(PatternToMatch(PatternsToMatch[i].getPredicates(), 2980 Variant, PatternsToMatch[i].getDstPattern(), 2981 PatternsToMatch[i].getDstRegs(), 2982 PatternsToMatch[i].getAddedComplexity(), 2983 Record::getNewUID())); 2984 } 2985 2986 DEBUG(errs() << "\n"); 2987 } 2988} 2989 2990