CodeGenDAGPatterns.cpp revision 193323
1//===- CodeGenDAGPatterns.cpp - Read DAG patterns from .td file -----------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the CodeGenDAGPatterns class, which is used to read and 11// represent the patterns present in a .td file for instructions. 12// 13//===----------------------------------------------------------------------===// 14 15#include "CodeGenDAGPatterns.h" 16#include "Record.h" 17#include "llvm/ADT/StringExtras.h" 18#include "llvm/Support/Debug.h" 19#include "llvm/Support/Streams.h" 20#include <set> 21#include <algorithm> 22using namespace llvm; 23 24//===----------------------------------------------------------------------===// 25// Helpers for working with extended types. 26 27/// FilterVTs - Filter a list of VT's according to a predicate. 28/// 29template<typename T> 30static std::vector<MVT::SimpleValueType> 31FilterVTs(const std::vector<MVT::SimpleValueType> &InVTs, T Filter) { 32 std::vector<MVT::SimpleValueType> Result; 33 for (unsigned i = 0, e = InVTs.size(); i != e; ++i) 34 if (Filter(InVTs[i])) 35 Result.push_back(InVTs[i]); 36 return Result; 37} 38 39template<typename T> 40static std::vector<unsigned char> 41FilterEVTs(const std::vector<unsigned char> &InVTs, T Filter) { 42 std::vector<unsigned char> Result; 43 for (unsigned i = 0, e = InVTs.size(); i != e; ++i) 44 if (Filter((MVT::SimpleValueType)InVTs[i])) 45 Result.push_back(InVTs[i]); 46 return Result; 47} 48 49static std::vector<unsigned char> 50ConvertVTs(const std::vector<MVT::SimpleValueType> &InVTs) { 51 std::vector<unsigned char> Result; 52 for (unsigned i = 0, e = InVTs.size(); i != e; ++i) 53 Result.push_back(InVTs[i]); 54 return Result; 55} 56 57static inline bool isInteger(MVT::SimpleValueType VT) { 58 return MVT(VT).isInteger(); 59} 60 61static inline bool isFloatingPoint(MVT::SimpleValueType VT) { 62 return MVT(VT).isFloatingPoint(); 63} 64 65static inline bool isVector(MVT::SimpleValueType VT) { 66 return MVT(VT).isVector(); 67} 68 69static bool LHSIsSubsetOfRHS(const std::vector<unsigned char> &LHS, 70 const std::vector<unsigned char> &RHS) { 71 if (LHS.size() > RHS.size()) return false; 72 for (unsigned i = 0, e = LHS.size(); i != e; ++i) 73 if (std::find(RHS.begin(), RHS.end(), LHS[i]) == RHS.end()) 74 return false; 75 return true; 76} 77 78namespace llvm { 79namespace EMVT { 80/// isExtIntegerInVTs - Return true if the specified extended value type vector 81/// contains isInt or an integer value type. 82bool isExtIntegerInVTs(const std::vector<unsigned char> &EVTs) { 83 assert(!EVTs.empty() && "Cannot check for integer in empty ExtVT list!"); 84 return EVTs[0] == isInt || !(FilterEVTs(EVTs, isInteger).empty()); 85} 86 87/// isExtFloatingPointInVTs - Return true if the specified extended value type 88/// vector contains isFP or a FP value type. 89bool isExtFloatingPointInVTs(const std::vector<unsigned char> &EVTs) { 90 assert(!EVTs.empty() && "Cannot check for integer in empty ExtVT list!"); 91 return EVTs[0] == isFP || !(FilterEVTs(EVTs, isFloatingPoint).empty()); 92} 93} // end namespace EMVT. 94} // end namespace llvm. 95 96 97/// Dependent variable map for CodeGenDAGPattern variant generation 98typedef std::map<std::string, int> DepVarMap; 99 100/// Const iterator shorthand for DepVarMap 101typedef DepVarMap::const_iterator DepVarMap_citer; 102 103namespace { 104void FindDepVarsOf(TreePatternNode *N, DepVarMap &DepMap) { 105 if (N->isLeaf()) { 106 if (dynamic_cast<DefInit*>(N->getLeafValue()) != NULL) { 107 DepMap[N->getName()]++; 108 } 109 } else { 110 for (size_t i = 0, e = N->getNumChildren(); i != e; ++i) 111 FindDepVarsOf(N->getChild(i), DepMap); 112 } 113} 114 115//! Find dependent variables within child patterns 116/*! 117 */ 118void FindDepVars(TreePatternNode *N, MultipleUseVarSet &DepVars) { 119 DepVarMap depcounts; 120 FindDepVarsOf(N, depcounts); 121 for (DepVarMap_citer i = depcounts.begin(); i != depcounts.end(); ++i) { 122 if (i->second > 1) { // std::pair<std::string, int> 123 DepVars.insert(i->first); 124 } 125 } 126} 127 128//! Dump the dependent variable set: 129void DumpDepVars(MultipleUseVarSet &DepVars) { 130 if (DepVars.empty()) { 131 DOUT << "<empty set>"; 132 } else { 133 DOUT << "[ "; 134 for (MultipleUseVarSet::const_iterator i = DepVars.begin(), e = DepVars.end(); 135 i != e; ++i) { 136 DOUT << (*i) << " "; 137 } 138 DOUT << "]"; 139 } 140} 141} 142 143//===----------------------------------------------------------------------===// 144// PatternToMatch implementation 145// 146 147/// getPredicateCheck - Return a single string containing all of this 148/// pattern's predicates concatenated with "&&" operators. 149/// 150std::string PatternToMatch::getPredicateCheck() const { 151 std::string PredicateCheck; 152 for (unsigned i = 0, e = Predicates->getSize(); i != e; ++i) { 153 if (DefInit *Pred = dynamic_cast<DefInit*>(Predicates->getElement(i))) { 154 Record *Def = Pred->getDef(); 155 if (!Def->isSubClassOf("Predicate")) { 156#ifndef NDEBUG 157 Def->dump(); 158#endif 159 assert(0 && "Unknown predicate type!"); 160 } 161 if (!PredicateCheck.empty()) 162 PredicateCheck += " && "; 163 PredicateCheck += "(" + Def->getValueAsString("CondString") + ")"; 164 } 165 } 166 167 return PredicateCheck; 168} 169 170//===----------------------------------------------------------------------===// 171// SDTypeConstraint implementation 172// 173 174SDTypeConstraint::SDTypeConstraint(Record *R) { 175 OperandNo = R->getValueAsInt("OperandNum"); 176 177 if (R->isSubClassOf("SDTCisVT")) { 178 ConstraintType = SDTCisVT; 179 x.SDTCisVT_Info.VT = getValueType(R->getValueAsDef("VT")); 180 } else if (R->isSubClassOf("SDTCisPtrTy")) { 181 ConstraintType = SDTCisPtrTy; 182 } else if (R->isSubClassOf("SDTCisInt")) { 183 ConstraintType = SDTCisInt; 184 } else if (R->isSubClassOf("SDTCisFP")) { 185 ConstraintType = SDTCisFP; 186 } else if (R->isSubClassOf("SDTCisSameAs")) { 187 ConstraintType = SDTCisSameAs; 188 x.SDTCisSameAs_Info.OtherOperandNum = R->getValueAsInt("OtherOperandNum"); 189 } else if (R->isSubClassOf("SDTCisVTSmallerThanOp")) { 190 ConstraintType = SDTCisVTSmallerThanOp; 191 x.SDTCisVTSmallerThanOp_Info.OtherOperandNum = 192 R->getValueAsInt("OtherOperandNum"); 193 } else if (R->isSubClassOf("SDTCisOpSmallerThanOp")) { 194 ConstraintType = SDTCisOpSmallerThanOp; 195 x.SDTCisOpSmallerThanOp_Info.BigOperandNum = 196 R->getValueAsInt("BigOperandNum"); 197 } else if (R->isSubClassOf("SDTCisEltOfVec")) { 198 ConstraintType = SDTCisEltOfVec; 199 x.SDTCisEltOfVec_Info.OtherOperandNum = 200 R->getValueAsInt("OtherOpNum"); 201 } else { 202 cerr << "Unrecognized SDTypeConstraint '" << R->getName() << "'!\n"; 203 exit(1); 204 } 205} 206 207/// getOperandNum - Return the node corresponding to operand #OpNo in tree 208/// N, which has NumResults results. 209TreePatternNode *SDTypeConstraint::getOperandNum(unsigned OpNo, 210 TreePatternNode *N, 211 unsigned NumResults) const { 212 assert(NumResults <= 1 && 213 "We only work with nodes with zero or one result so far!"); 214 215 if (OpNo >= (NumResults + N->getNumChildren())) { 216 cerr << "Invalid operand number " << OpNo << " "; 217 N->dump(); 218 cerr << '\n'; 219 exit(1); 220 } 221 222 if (OpNo < NumResults) 223 return N; // FIXME: need value # 224 else 225 return N->getChild(OpNo-NumResults); 226} 227 228/// ApplyTypeConstraint - Given a node in a pattern, apply this type 229/// constraint to the nodes operands. This returns true if it makes a 230/// change, false otherwise. If a type contradiction is found, throw an 231/// exception. 232bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, 233 const SDNodeInfo &NodeInfo, 234 TreePattern &TP) const { 235 unsigned NumResults = NodeInfo.getNumResults(); 236 assert(NumResults <= 1 && 237 "We only work with nodes with zero or one result so far!"); 238 239 // Check that the number of operands is sane. Negative operands -> varargs. 240 if (NodeInfo.getNumOperands() >= 0) { 241 if (N->getNumChildren() != (unsigned)NodeInfo.getNumOperands()) 242 TP.error(N->getOperator()->getName() + " node requires exactly " + 243 itostr(NodeInfo.getNumOperands()) + " operands!"); 244 } 245 246 const CodeGenTarget &CGT = TP.getDAGPatterns().getTargetInfo(); 247 248 TreePatternNode *NodeToApply = getOperandNum(OperandNo, N, NumResults); 249 250 switch (ConstraintType) { 251 default: assert(0 && "Unknown constraint type!"); 252 case SDTCisVT: 253 // Operand must be a particular type. 254 return NodeToApply->UpdateNodeType(x.SDTCisVT_Info.VT, TP); 255 case SDTCisPtrTy: { 256 // Operand must be same as target pointer type. 257 return NodeToApply->UpdateNodeType(MVT::iPTR, TP); 258 } 259 case SDTCisInt: { 260 // If there is only one integer type supported, this must be it. 261 std::vector<MVT::SimpleValueType> IntVTs = 262 FilterVTs(CGT.getLegalValueTypes(), isInteger); 263 264 // If we found exactly one supported integer type, apply it. 265 if (IntVTs.size() == 1) 266 return NodeToApply->UpdateNodeType(IntVTs[0], TP); 267 return NodeToApply->UpdateNodeType(EMVT::isInt, TP); 268 } 269 case SDTCisFP: { 270 // If there is only one FP type supported, this must be it. 271 std::vector<MVT::SimpleValueType> FPVTs = 272 FilterVTs(CGT.getLegalValueTypes(), isFloatingPoint); 273 274 // If we found exactly one supported FP type, apply it. 275 if (FPVTs.size() == 1) 276 return NodeToApply->UpdateNodeType(FPVTs[0], TP); 277 return NodeToApply->UpdateNodeType(EMVT::isFP, TP); 278 } 279 case SDTCisSameAs: { 280 TreePatternNode *OtherNode = 281 getOperandNum(x.SDTCisSameAs_Info.OtherOperandNum, N, NumResults); 282 return NodeToApply->UpdateNodeType(OtherNode->getExtTypes(), TP) | 283 OtherNode->UpdateNodeType(NodeToApply->getExtTypes(), TP); 284 } 285 case SDTCisVTSmallerThanOp: { 286 // The NodeToApply must be a leaf node that is a VT. OtherOperandNum must 287 // have an integer type that is smaller than the VT. 288 if (!NodeToApply->isLeaf() || 289 !dynamic_cast<DefInit*>(NodeToApply->getLeafValue()) || 290 !static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef() 291 ->isSubClassOf("ValueType")) 292 TP.error(N->getOperator()->getName() + " expects a VT operand!"); 293 MVT::SimpleValueType VT = 294 getValueType(static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef()); 295 if (!isInteger(VT)) 296 TP.error(N->getOperator()->getName() + " VT operand must be integer!"); 297 298 TreePatternNode *OtherNode = 299 getOperandNum(x.SDTCisVTSmallerThanOp_Info.OtherOperandNum, N,NumResults); 300 301 // It must be integer. 302 bool MadeChange = false; 303 MadeChange |= OtherNode->UpdateNodeType(EMVT::isInt, TP); 304 305 // This code only handles nodes that have one type set. Assert here so 306 // that we can change this if we ever need to deal with multiple value 307 // types at this point. 308 assert(OtherNode->getExtTypes().size() == 1 && "Node has too many types!"); 309 if (OtherNode->hasTypeSet() && OtherNode->getTypeNum(0) <= VT) 310 OtherNode->UpdateNodeType(MVT::Other, TP); // Throw an error. 311 return false; 312 } 313 case SDTCisOpSmallerThanOp: { 314 TreePatternNode *BigOperand = 315 getOperandNum(x.SDTCisOpSmallerThanOp_Info.BigOperandNum, N, NumResults); 316 317 // Both operands must be integer or FP, but we don't care which. 318 bool MadeChange = false; 319 320 // This code does not currently handle nodes which have multiple types, 321 // where some types are integer, and some are fp. Assert that this is not 322 // the case. 323 assert(!(EMVT::isExtIntegerInVTs(NodeToApply->getExtTypes()) && 324 EMVT::isExtFloatingPointInVTs(NodeToApply->getExtTypes())) && 325 !(EMVT::isExtIntegerInVTs(BigOperand->getExtTypes()) && 326 EMVT::isExtFloatingPointInVTs(BigOperand->getExtTypes())) && 327 "SDTCisOpSmallerThanOp does not handle mixed int/fp types!"); 328 if (EMVT::isExtIntegerInVTs(NodeToApply->getExtTypes())) 329 MadeChange |= BigOperand->UpdateNodeType(EMVT::isInt, TP); 330 else if (EMVT::isExtFloatingPointInVTs(NodeToApply->getExtTypes())) 331 MadeChange |= BigOperand->UpdateNodeType(EMVT::isFP, TP); 332 if (EMVT::isExtIntegerInVTs(BigOperand->getExtTypes())) 333 MadeChange |= NodeToApply->UpdateNodeType(EMVT::isInt, TP); 334 else if (EMVT::isExtFloatingPointInVTs(BigOperand->getExtTypes())) 335 MadeChange |= NodeToApply->UpdateNodeType(EMVT::isFP, TP); 336 337 std::vector<MVT::SimpleValueType> VTs = CGT.getLegalValueTypes(); 338 339 if (EMVT::isExtIntegerInVTs(NodeToApply->getExtTypes())) { 340 VTs = FilterVTs(VTs, isInteger); 341 } else if (EMVT::isExtFloatingPointInVTs(NodeToApply->getExtTypes())) { 342 VTs = FilterVTs(VTs, isFloatingPoint); 343 } else { 344 VTs.clear(); 345 } 346 347 switch (VTs.size()) { 348 default: // Too many VT's to pick from. 349 case 0: break; // No info yet. 350 case 1: 351 // Only one VT of this flavor. Cannot ever satisfy the constraints. 352 return NodeToApply->UpdateNodeType(MVT::Other, TP); // throw 353 case 2: 354 // If we have exactly two possible types, the little operand must be the 355 // small one, the big operand should be the big one. Common with 356 // float/double for example. 357 assert(VTs[0] < VTs[1] && "Should be sorted!"); 358 MadeChange |= NodeToApply->UpdateNodeType(VTs[0], TP); 359 MadeChange |= BigOperand->UpdateNodeType(VTs[1], TP); 360 break; 361 } 362 return MadeChange; 363 } 364 case SDTCisEltOfVec: { 365 TreePatternNode *OtherOperand = 366 getOperandNum(x.SDTCisEltOfVec_Info.OtherOperandNum, 367 N, NumResults); 368 if (OtherOperand->hasTypeSet()) { 369 if (!isVector(OtherOperand->getTypeNum(0))) 370 TP.error(N->getOperator()->getName() + " VT operand must be a vector!"); 371 MVT IVT = OtherOperand->getTypeNum(0); 372 IVT = IVT.getVectorElementType(); 373 return NodeToApply->UpdateNodeType(IVT.getSimpleVT(), TP); 374 } 375 return false; 376 } 377 } 378 return false; 379} 380 381//===----------------------------------------------------------------------===// 382// SDNodeInfo implementation 383// 384SDNodeInfo::SDNodeInfo(Record *R) : Def(R) { 385 EnumName = R->getValueAsString("Opcode"); 386 SDClassName = R->getValueAsString("SDClass"); 387 Record *TypeProfile = R->getValueAsDef("TypeProfile"); 388 NumResults = TypeProfile->getValueAsInt("NumResults"); 389 NumOperands = TypeProfile->getValueAsInt("NumOperands"); 390 391 // Parse the properties. 392 Properties = 0; 393 std::vector<Record*> PropList = R->getValueAsListOfDefs("Properties"); 394 for (unsigned i = 0, e = PropList.size(); i != e; ++i) { 395 if (PropList[i]->getName() == "SDNPCommutative") { 396 Properties |= 1 << SDNPCommutative; 397 } else if (PropList[i]->getName() == "SDNPAssociative") { 398 Properties |= 1 << SDNPAssociative; 399 } else if (PropList[i]->getName() == "SDNPHasChain") { 400 Properties |= 1 << SDNPHasChain; 401 } else if (PropList[i]->getName() == "SDNPOutFlag") { 402 Properties |= 1 << SDNPOutFlag; 403 } else if (PropList[i]->getName() == "SDNPInFlag") { 404 Properties |= 1 << SDNPInFlag; 405 } else if (PropList[i]->getName() == "SDNPOptInFlag") { 406 Properties |= 1 << SDNPOptInFlag; 407 } else if (PropList[i]->getName() == "SDNPMayStore") { 408 Properties |= 1 << SDNPMayStore; 409 } else if (PropList[i]->getName() == "SDNPMayLoad") { 410 Properties |= 1 << SDNPMayLoad; 411 } else if (PropList[i]->getName() == "SDNPSideEffect") { 412 Properties |= 1 << SDNPSideEffect; 413 } else if (PropList[i]->getName() == "SDNPMemOperand") { 414 Properties |= 1 << SDNPMemOperand; 415 } else { 416 cerr << "Unknown SD Node property '" << PropList[i]->getName() 417 << "' on node '" << R->getName() << "'!\n"; 418 exit(1); 419 } 420 } 421 422 423 // Parse the type constraints. 424 std::vector<Record*> ConstraintList = 425 TypeProfile->getValueAsListOfDefs("Constraints"); 426 TypeConstraints.assign(ConstraintList.begin(), ConstraintList.end()); 427} 428 429//===----------------------------------------------------------------------===// 430// TreePatternNode implementation 431// 432 433TreePatternNode::~TreePatternNode() { 434#if 0 // FIXME: implement refcounted tree nodes! 435 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 436 delete getChild(i); 437#endif 438} 439 440/// UpdateNodeType - Set the node type of N to VT if VT contains 441/// information. If N already contains a conflicting type, then throw an 442/// exception. This returns true if any information was updated. 443/// 444bool TreePatternNode::UpdateNodeType(const std::vector<unsigned char> &ExtVTs, 445 TreePattern &TP) { 446 assert(!ExtVTs.empty() && "Cannot update node type with empty type vector!"); 447 448 if (ExtVTs[0] == EMVT::isUnknown || LHSIsSubsetOfRHS(getExtTypes(), ExtVTs)) 449 return false; 450 if (isTypeCompletelyUnknown() || LHSIsSubsetOfRHS(ExtVTs, getExtTypes())) { 451 setTypes(ExtVTs); 452 return true; 453 } 454 455 if (getExtTypeNum(0) == MVT::iPTR || getExtTypeNum(0) == MVT::iPTRAny) { 456 if (ExtVTs[0] == MVT::iPTR || ExtVTs[0] == MVT::iPTRAny || 457 ExtVTs[0] == EMVT::isInt) 458 return false; 459 if (EMVT::isExtIntegerInVTs(ExtVTs)) { 460 std::vector<unsigned char> FVTs = FilterEVTs(ExtVTs, isInteger); 461 if (FVTs.size()) { 462 setTypes(ExtVTs); 463 return true; 464 } 465 } 466 } 467 468 if ((ExtVTs[0] == EMVT::isInt || ExtVTs[0] == MVT::iAny) && 469 EMVT::isExtIntegerInVTs(getExtTypes())) { 470 assert(hasTypeSet() && "should be handled above!"); 471 std::vector<unsigned char> FVTs = FilterEVTs(getExtTypes(), isInteger); 472 if (getExtTypes() == FVTs) 473 return false; 474 setTypes(FVTs); 475 return true; 476 } 477 if ((ExtVTs[0] == MVT::iPTR || ExtVTs[0] == MVT::iPTRAny) && 478 EMVT::isExtIntegerInVTs(getExtTypes())) { 479 //assert(hasTypeSet() && "should be handled above!"); 480 std::vector<unsigned char> FVTs = FilterEVTs(getExtTypes(), isInteger); 481 if (getExtTypes() == FVTs) 482 return false; 483 if (FVTs.size()) { 484 setTypes(FVTs); 485 return true; 486 } 487 } 488 if ((ExtVTs[0] == EMVT::isFP || ExtVTs[0] == MVT::fAny) && 489 EMVT::isExtFloatingPointInVTs(getExtTypes())) { 490 assert(hasTypeSet() && "should be handled above!"); 491 std::vector<unsigned char> FVTs = 492 FilterEVTs(getExtTypes(), isFloatingPoint); 493 if (getExtTypes() == FVTs) 494 return false; 495 setTypes(FVTs); 496 return true; 497 } 498 499 // If we know this is an int or fp type, and we are told it is a specific one, 500 // take the advice. 501 // 502 // Similarly, we should probably set the type here to the intersection of 503 // {isInt|isFP} and ExtVTs 504 if (((getExtTypeNum(0) == EMVT::isInt || getExtTypeNum(0) == MVT::iAny) && 505 EMVT::isExtIntegerInVTs(ExtVTs)) || 506 ((getExtTypeNum(0) == EMVT::isFP || getExtTypeNum(0) == MVT::fAny) && 507 EMVT::isExtFloatingPointInVTs(ExtVTs))) { 508 setTypes(ExtVTs); 509 return true; 510 } 511 if (getExtTypeNum(0) == EMVT::isInt && 512 (ExtVTs[0] == MVT::iPTR || ExtVTs[0] == MVT::iPTRAny)) { 513 setTypes(ExtVTs); 514 return true; 515 } 516 517 if (isLeaf()) { 518 dump(); 519 cerr << " "; 520 TP.error("Type inference contradiction found in node!"); 521 } else { 522 TP.error("Type inference contradiction found in node " + 523 getOperator()->getName() + "!"); 524 } 525 return true; // unreachable 526} 527 528 529void TreePatternNode::print(std::ostream &OS) const { 530 if (isLeaf()) { 531 OS << *getLeafValue(); 532 } else { 533 OS << "(" << getOperator()->getName(); 534 } 535 536 // FIXME: At some point we should handle printing all the value types for 537 // nodes that are multiply typed. 538 switch (getExtTypeNum(0)) { 539 case MVT::Other: OS << ":Other"; break; 540 case EMVT::isInt: OS << ":isInt"; break; 541 case EMVT::isFP : OS << ":isFP"; break; 542 case EMVT::isUnknown: ; /*OS << ":?";*/ break; 543 case MVT::iPTR: OS << ":iPTR"; break; 544 case MVT::iPTRAny: OS << ":iPTRAny"; break; 545 default: { 546 std::string VTName = llvm::getName(getTypeNum(0)); 547 // Strip off MVT:: prefix if present. 548 if (VTName.substr(0,5) == "MVT::") 549 VTName = VTName.substr(5); 550 OS << ":" << VTName; 551 break; 552 } 553 } 554 555 if (!isLeaf()) { 556 if (getNumChildren() != 0) { 557 OS << " "; 558 getChild(0)->print(OS); 559 for (unsigned i = 1, e = getNumChildren(); i != e; ++i) { 560 OS << ", "; 561 getChild(i)->print(OS); 562 } 563 } 564 OS << ")"; 565 } 566 567 for (unsigned i = 0, e = PredicateFns.size(); i != e; ++i) 568 OS << "<<P:" << PredicateFns[i] << ">>"; 569 if (TransformFn) 570 OS << "<<X:" << TransformFn->getName() << ">>"; 571 if (!getName().empty()) 572 OS << ":$" << getName(); 573 574} 575void TreePatternNode::dump() const { 576 print(*cerr.stream()); 577} 578 579/// isIsomorphicTo - Return true if this node is recursively 580/// isomorphic to the specified node. For this comparison, the node's 581/// entire state is considered. The assigned name is ignored, since 582/// nodes with differing names are considered isomorphic. However, if 583/// the assigned name is present in the dependent variable set, then 584/// the assigned name is considered significant and the node is 585/// isomorphic if the names match. 586bool TreePatternNode::isIsomorphicTo(const TreePatternNode *N, 587 const MultipleUseVarSet &DepVars) const { 588 if (N == this) return true; 589 if (N->isLeaf() != isLeaf() || getExtTypes() != N->getExtTypes() || 590 getPredicateFns() != N->getPredicateFns() || 591 getTransformFn() != N->getTransformFn()) 592 return false; 593 594 if (isLeaf()) { 595 if (DefInit *DI = dynamic_cast<DefInit*>(getLeafValue())) { 596 if (DefInit *NDI = dynamic_cast<DefInit*>(N->getLeafValue())) { 597 return ((DI->getDef() == NDI->getDef()) 598 && (DepVars.find(getName()) == DepVars.end() 599 || getName() == N->getName())); 600 } 601 } 602 return getLeafValue() == N->getLeafValue(); 603 } 604 605 if (N->getOperator() != getOperator() || 606 N->getNumChildren() != getNumChildren()) return false; 607 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 608 if (!getChild(i)->isIsomorphicTo(N->getChild(i), DepVars)) 609 return false; 610 return true; 611} 612 613/// clone - Make a copy of this tree and all of its children. 614/// 615TreePatternNode *TreePatternNode::clone() const { 616 TreePatternNode *New; 617 if (isLeaf()) { 618 New = new TreePatternNode(getLeafValue()); 619 } else { 620 std::vector<TreePatternNode*> CChildren; 621 CChildren.reserve(Children.size()); 622 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 623 CChildren.push_back(getChild(i)->clone()); 624 New = new TreePatternNode(getOperator(), CChildren); 625 } 626 New->setName(getName()); 627 New->setTypes(getExtTypes()); 628 New->setPredicateFns(getPredicateFns()); 629 New->setTransformFn(getTransformFn()); 630 return New; 631} 632 633/// SubstituteFormalArguments - Replace the formal arguments in this tree 634/// with actual values specified by ArgMap. 635void TreePatternNode:: 636SubstituteFormalArguments(std::map<std::string, TreePatternNode*> &ArgMap) { 637 if (isLeaf()) return; 638 639 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { 640 TreePatternNode *Child = getChild(i); 641 if (Child->isLeaf()) { 642 Init *Val = Child->getLeafValue(); 643 if (dynamic_cast<DefInit*>(Val) && 644 static_cast<DefInit*>(Val)->getDef()->getName() == "node") { 645 // We found a use of a formal argument, replace it with its value. 646 TreePatternNode *NewChild = ArgMap[Child->getName()]; 647 assert(NewChild && "Couldn't find formal argument!"); 648 assert((Child->getPredicateFns().empty() || 649 NewChild->getPredicateFns() == Child->getPredicateFns()) && 650 "Non-empty child predicate clobbered!"); 651 setChild(i, NewChild); 652 } 653 } else { 654 getChild(i)->SubstituteFormalArguments(ArgMap); 655 } 656 } 657} 658 659 660/// InlinePatternFragments - If this pattern refers to any pattern 661/// fragments, inline them into place, giving us a pattern without any 662/// PatFrag references. 663TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) { 664 if (isLeaf()) return this; // nothing to do. 665 Record *Op = getOperator(); 666 667 if (!Op->isSubClassOf("PatFrag")) { 668 // Just recursively inline children nodes. 669 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { 670 TreePatternNode *Child = getChild(i); 671 TreePatternNode *NewChild = Child->InlinePatternFragments(TP); 672 673 assert((Child->getPredicateFns().empty() || 674 NewChild->getPredicateFns() == Child->getPredicateFns()) && 675 "Non-empty child predicate clobbered!"); 676 677 setChild(i, NewChild); 678 } 679 return this; 680 } 681 682 // Otherwise, we found a reference to a fragment. First, look up its 683 // TreePattern record. 684 TreePattern *Frag = TP.getDAGPatterns().getPatternFragment(Op); 685 686 // Verify that we are passing the right number of operands. 687 if (Frag->getNumArgs() != Children.size()) 688 TP.error("'" + Op->getName() + "' fragment requires " + 689 utostr(Frag->getNumArgs()) + " operands!"); 690 691 TreePatternNode *FragTree = Frag->getOnlyTree()->clone(); 692 693 std::string Code = Op->getValueAsCode("Predicate"); 694 if (!Code.empty()) 695 FragTree->addPredicateFn("Predicate_"+Op->getName()); 696 697 // Resolve formal arguments to their actual value. 698 if (Frag->getNumArgs()) { 699 // Compute the map of formal to actual arguments. 700 std::map<std::string, TreePatternNode*> ArgMap; 701 for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i) 702 ArgMap[Frag->getArgName(i)] = getChild(i)->InlinePatternFragments(TP); 703 704 FragTree->SubstituteFormalArguments(ArgMap); 705 } 706 707 FragTree->setName(getName()); 708 FragTree->UpdateNodeType(getExtTypes(), TP); 709 710 // Transfer in the old predicates. 711 for (unsigned i = 0, e = getPredicateFns().size(); i != e; ++i) 712 FragTree->addPredicateFn(getPredicateFns()[i]); 713 714 // Get a new copy of this fragment to stitch into here. 715 //delete this; // FIXME: implement refcounting! 716 717 // The fragment we inlined could have recursive inlining that is needed. See 718 // if there are any pattern fragments in it and inline them as needed. 719 return FragTree->InlinePatternFragments(TP); 720} 721 722/// getImplicitType - Check to see if the specified record has an implicit 723/// type which should be applied to it. This infer the type of register 724/// references from the register file information, for example. 725/// 726static std::vector<unsigned char> getImplicitType(Record *R, bool NotRegisters, 727 TreePattern &TP) { 728 // Some common return values 729 std::vector<unsigned char> Unknown(1, EMVT::isUnknown); 730 std::vector<unsigned char> Other(1, MVT::Other); 731 732 // Check to see if this is a register or a register class... 733 if (R->isSubClassOf("RegisterClass")) { 734 if (NotRegisters) 735 return Unknown; 736 const CodeGenRegisterClass &RC = 737 TP.getDAGPatterns().getTargetInfo().getRegisterClass(R); 738 return ConvertVTs(RC.getValueTypes()); 739 } else if (R->isSubClassOf("PatFrag")) { 740 // Pattern fragment types will be resolved when they are inlined. 741 return Unknown; 742 } else if (R->isSubClassOf("Register")) { 743 if (NotRegisters) 744 return Unknown; 745 const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo(); 746 return T.getRegisterVTs(R); 747 } else if (R->isSubClassOf("ValueType") || R->isSubClassOf("CondCode")) { 748 // Using a VTSDNode or CondCodeSDNode. 749 return Other; 750 } else if (R->isSubClassOf("ComplexPattern")) { 751 if (NotRegisters) 752 return Unknown; 753 std::vector<unsigned char> 754 ComplexPat(1, TP.getDAGPatterns().getComplexPattern(R).getValueType()); 755 return ComplexPat; 756 } else if (R->getName() == "ptr_rc") { 757 Other[0] = MVT::iPTR; 758 return Other; 759 } else if (R->getName() == "node" || R->getName() == "srcvalue" || 760 R->getName() == "zero_reg") { 761 // Placeholder. 762 return Unknown; 763 } 764 765 TP.error("Unknown node flavor used in pattern: " + R->getName()); 766 return Other; 767} 768 769 770/// getIntrinsicInfo - If this node corresponds to an intrinsic, return the 771/// CodeGenIntrinsic information for it, otherwise return a null pointer. 772const CodeGenIntrinsic *TreePatternNode:: 773getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const { 774 if (getOperator() != CDP.get_intrinsic_void_sdnode() && 775 getOperator() != CDP.get_intrinsic_w_chain_sdnode() && 776 getOperator() != CDP.get_intrinsic_wo_chain_sdnode()) 777 return 0; 778 779 unsigned IID = 780 dynamic_cast<IntInit*>(getChild(0)->getLeafValue())->getValue(); 781 return &CDP.getIntrinsicInfo(IID); 782} 783 784/// isCommutativeIntrinsic - Return true if the node corresponds to a 785/// commutative intrinsic. 786bool 787TreePatternNode::isCommutativeIntrinsic(const CodeGenDAGPatterns &CDP) const { 788 if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) 789 return Int->isCommutative; 790 return false; 791} 792 793 794/// ApplyTypeConstraints - Apply all of the type constraints relevant to 795/// this node and its children in the tree. This returns true if it makes a 796/// change, false otherwise. If a type contradiction is found, throw an 797/// exception. 798bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { 799 CodeGenDAGPatterns &CDP = TP.getDAGPatterns(); 800 if (isLeaf()) { 801 if (DefInit *DI = dynamic_cast<DefInit*>(getLeafValue())) { 802 // If it's a regclass or something else known, include the type. 803 return UpdateNodeType(getImplicitType(DI->getDef(), NotRegisters, TP),TP); 804 } else if (IntInit *II = dynamic_cast<IntInit*>(getLeafValue())) { 805 // Int inits are always integers. :) 806 bool MadeChange = UpdateNodeType(EMVT::isInt, TP); 807 808 if (hasTypeSet()) { 809 // At some point, it may make sense for this tree pattern to have 810 // multiple types. Assert here that it does not, so we revisit this 811 // code when appropriate. 812 assert(getExtTypes().size() >= 1 && "TreePattern doesn't have a type!"); 813 MVT::SimpleValueType VT = getTypeNum(0); 814 for (unsigned i = 1, e = getExtTypes().size(); i != e; ++i) 815 assert(getTypeNum(i) == VT && "TreePattern has too many types!"); 816 817 VT = getTypeNum(0); 818 if (VT != MVT::iPTR && VT != MVT::iPTRAny) { 819 unsigned Size = MVT(VT).getSizeInBits(); 820 // Make sure that the value is representable for this type. 821 if (Size < 32) { 822 int Val = (II->getValue() << (32-Size)) >> (32-Size); 823 if (Val != II->getValue()) { 824 // If sign-extended doesn't fit, does it fit as unsigned? 825 unsigned ValueMask; 826 unsigned UnsignedVal; 827 ValueMask = unsigned(~uint32_t(0UL) >> (32-Size)); 828 UnsignedVal = unsigned(II->getValue()); 829 830 if ((ValueMask & UnsignedVal) != UnsignedVal) { 831 TP.error("Integer value '" + itostr(II->getValue())+ 832 "' is out of range for type '" + 833 getEnumName(getTypeNum(0)) + "'!"); 834 } 835 } 836 } 837 } 838 } 839 840 return MadeChange; 841 } 842 return false; 843 } 844 845 // special handling for set, which isn't really an SDNode. 846 if (getOperator()->getName() == "set") { 847 assert (getNumChildren() >= 2 && "Missing RHS of a set?"); 848 unsigned NC = getNumChildren(); 849 bool MadeChange = false; 850 for (unsigned i = 0; i < NC-1; ++i) { 851 MadeChange = getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 852 MadeChange |= getChild(NC-1)->ApplyTypeConstraints(TP, NotRegisters); 853 854 // Types of operands must match. 855 MadeChange |= getChild(i)->UpdateNodeType(getChild(NC-1)->getExtTypes(), 856 TP); 857 MadeChange |= getChild(NC-1)->UpdateNodeType(getChild(i)->getExtTypes(), 858 TP); 859 MadeChange |= UpdateNodeType(MVT::isVoid, TP); 860 } 861 return MadeChange; 862 } else if (getOperator()->getName() == "implicit" || 863 getOperator()->getName() == "parallel") { 864 bool MadeChange = false; 865 for (unsigned i = 0; i < getNumChildren(); ++i) 866 MadeChange = getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 867 MadeChange |= UpdateNodeType(MVT::isVoid, TP); 868 return MadeChange; 869 } else if (getOperator()->getName() == "COPY_TO_REGCLASS") { 870 bool MadeChange = false; 871 MadeChange |= getChild(0)->ApplyTypeConstraints(TP, NotRegisters); 872 MadeChange |= getChild(1)->ApplyTypeConstraints(TP, NotRegisters); 873 MadeChange |= UpdateNodeType(getChild(1)->getTypeNum(0), TP); 874 return MadeChange; 875 } else if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) { 876 bool MadeChange = false; 877 878 // Apply the result type to the node. 879 unsigned NumRetVTs = Int->IS.RetVTs.size(); 880 unsigned NumParamVTs = Int->IS.ParamVTs.size(); 881 882 for (unsigned i = 0, e = NumRetVTs; i != e; ++i) 883 MadeChange |= UpdateNodeType(Int->IS.RetVTs[i], TP); 884 885 if (getNumChildren() != NumParamVTs + NumRetVTs) 886 TP.error("Intrinsic '" + Int->Name + "' expects " + 887 utostr(NumParamVTs + NumRetVTs - 1) + " operands, not " + 888 utostr(getNumChildren() - 1) + " operands!"); 889 890 // Apply type info to the intrinsic ID. 891 MadeChange |= getChild(0)->UpdateNodeType(MVT::iPTR, TP); 892 893 for (unsigned i = NumRetVTs, e = getNumChildren(); i != e; ++i) { 894 MVT::SimpleValueType OpVT = Int->IS.ParamVTs[i - NumRetVTs]; 895 MadeChange |= getChild(i)->UpdateNodeType(OpVT, TP); 896 MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 897 } 898 return MadeChange; 899 } else if (getOperator()->isSubClassOf("SDNode")) { 900 const SDNodeInfo &NI = CDP.getSDNodeInfo(getOperator()); 901 902 bool MadeChange = NI.ApplyTypeConstraints(this, TP); 903 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 904 MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 905 // Branch, etc. do not produce results and top-level forms in instr pattern 906 // must have void types. 907 if (NI.getNumResults() == 0) 908 MadeChange |= UpdateNodeType(MVT::isVoid, TP); 909 910 return MadeChange; 911 } else if (getOperator()->isSubClassOf("Instruction")) { 912 const DAGInstruction &Inst = CDP.getInstruction(getOperator()); 913 bool MadeChange = false; 914 unsigned NumResults = Inst.getNumResults(); 915 916 assert(NumResults <= 1 && 917 "Only supports zero or one result instrs!"); 918 919 CodeGenInstruction &InstInfo = 920 CDP.getTargetInfo().getInstruction(getOperator()->getName()); 921 // Apply the result type to the node 922 if (NumResults == 0 || InstInfo.NumDefs == 0) { 923 MadeChange = UpdateNodeType(MVT::isVoid, TP); 924 } else { 925 Record *ResultNode = Inst.getResult(0); 926 927 if (ResultNode->getName() == "ptr_rc") { 928 std::vector<unsigned char> VT; 929 VT.push_back(MVT::iPTR); 930 MadeChange = UpdateNodeType(VT, TP); 931 } else if (ResultNode->getName() == "unknown") { 932 std::vector<unsigned char> VT; 933 VT.push_back(EMVT::isUnknown); 934 MadeChange = UpdateNodeType(VT, TP); 935 } else { 936 assert(ResultNode->isSubClassOf("RegisterClass") && 937 "Operands should be register classes!"); 938 939 const CodeGenRegisterClass &RC = 940 CDP.getTargetInfo().getRegisterClass(ResultNode); 941 MadeChange = UpdateNodeType(ConvertVTs(RC.getValueTypes()), TP); 942 } 943 } 944 945 unsigned ChildNo = 0; 946 for (unsigned i = 0, e = Inst.getNumOperands(); i != e; ++i) { 947 Record *OperandNode = Inst.getOperand(i); 948 949 // If the instruction expects a predicate or optional def operand, we 950 // codegen this by setting the operand to it's default value if it has a 951 // non-empty DefaultOps field. 952 if ((OperandNode->isSubClassOf("PredicateOperand") || 953 OperandNode->isSubClassOf("OptionalDefOperand")) && 954 !CDP.getDefaultOperand(OperandNode).DefaultOps.empty()) 955 continue; 956 957 // Verify that we didn't run out of provided operands. 958 if (ChildNo >= getNumChildren()) 959 TP.error("Instruction '" + getOperator()->getName() + 960 "' expects more operands than were provided."); 961 962 MVT::SimpleValueType VT; 963 TreePatternNode *Child = getChild(ChildNo++); 964 if (OperandNode->isSubClassOf("RegisterClass")) { 965 const CodeGenRegisterClass &RC = 966 CDP.getTargetInfo().getRegisterClass(OperandNode); 967 MadeChange |= Child->UpdateNodeType(ConvertVTs(RC.getValueTypes()), TP); 968 } else if (OperandNode->isSubClassOf("Operand")) { 969 VT = getValueType(OperandNode->getValueAsDef("Type")); 970 MadeChange |= Child->UpdateNodeType(VT, TP); 971 } else if (OperandNode->getName() == "ptr_rc") { 972 MadeChange |= Child->UpdateNodeType(MVT::iPTR, TP); 973 } else if (OperandNode->getName() == "unknown") { 974 MadeChange |= Child->UpdateNodeType(EMVT::isUnknown, TP); 975 } else { 976 assert(0 && "Unknown operand type!"); 977 abort(); 978 } 979 MadeChange |= Child->ApplyTypeConstraints(TP, NotRegisters); 980 } 981 982 if (ChildNo != getNumChildren()) 983 TP.error("Instruction '" + getOperator()->getName() + 984 "' was provided too many operands!"); 985 986 return MadeChange; 987 } else { 988 assert(getOperator()->isSubClassOf("SDNodeXForm") && "Unknown node type!"); 989 990 // Node transforms always take one operand. 991 if (getNumChildren() != 1) 992 TP.error("Node transform '" + getOperator()->getName() + 993 "' requires one operand!"); 994 995 // If either the output or input of the xform does not have exact 996 // type info. We assume they must be the same. Otherwise, it is perfectly 997 // legal to transform from one type to a completely different type. 998 if (!hasTypeSet() || !getChild(0)->hasTypeSet()) { 999 bool MadeChange = UpdateNodeType(getChild(0)->getExtTypes(), TP); 1000 MadeChange |= getChild(0)->UpdateNodeType(getExtTypes(), TP); 1001 return MadeChange; 1002 } 1003 return false; 1004 } 1005} 1006 1007/// OnlyOnRHSOfCommutative - Return true if this value is only allowed on the 1008/// RHS of a commutative operation, not the on LHS. 1009static bool OnlyOnRHSOfCommutative(TreePatternNode *N) { 1010 if (!N->isLeaf() && N->getOperator()->getName() == "imm") 1011 return true; 1012 if (N->isLeaf() && dynamic_cast<IntInit*>(N->getLeafValue())) 1013 return true; 1014 return false; 1015} 1016 1017 1018/// canPatternMatch - If it is impossible for this pattern to match on this 1019/// target, fill in Reason and return false. Otherwise, return true. This is 1020/// used as a sanity check for .td files (to prevent people from writing stuff 1021/// that can never possibly work), and to prevent the pattern permuter from 1022/// generating stuff that is useless. 1023bool TreePatternNode::canPatternMatch(std::string &Reason, 1024 const CodeGenDAGPatterns &CDP) { 1025 if (isLeaf()) return true; 1026 1027 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 1028 if (!getChild(i)->canPatternMatch(Reason, CDP)) 1029 return false; 1030 1031 // If this is an intrinsic, handle cases that would make it not match. For 1032 // example, if an operand is required to be an immediate. 1033 if (getOperator()->isSubClassOf("Intrinsic")) { 1034 // TODO: 1035 return true; 1036 } 1037 1038 // If this node is a commutative operator, check that the LHS isn't an 1039 // immediate. 1040 const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(getOperator()); 1041 bool isCommIntrinsic = isCommutativeIntrinsic(CDP); 1042 if (NodeInfo.hasProperty(SDNPCommutative) || isCommIntrinsic) { 1043 // Scan all of the operands of the node and make sure that only the last one 1044 // is a constant node, unless the RHS also is. 1045 if (!OnlyOnRHSOfCommutative(getChild(getNumChildren()-1))) { 1046 bool Skip = isCommIntrinsic ? 1 : 0; // First operand is intrinsic id. 1047 for (unsigned i = Skip, e = getNumChildren()-1; i != e; ++i) 1048 if (OnlyOnRHSOfCommutative(getChild(i))) { 1049 Reason="Immediate value must be on the RHS of commutative operators!"; 1050 return false; 1051 } 1052 } 1053 } 1054 1055 return true; 1056} 1057 1058//===----------------------------------------------------------------------===// 1059// TreePattern implementation 1060// 1061 1062TreePattern::TreePattern(Record *TheRec, ListInit *RawPat, bool isInput, 1063 CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp){ 1064 isInputPattern = isInput; 1065 for (unsigned i = 0, e = RawPat->getSize(); i != e; ++i) 1066 Trees.push_back(ParseTreePattern((DagInit*)RawPat->getElement(i))); 1067} 1068 1069TreePattern::TreePattern(Record *TheRec, DagInit *Pat, bool isInput, 1070 CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp){ 1071 isInputPattern = isInput; 1072 Trees.push_back(ParseTreePattern(Pat)); 1073} 1074 1075TreePattern::TreePattern(Record *TheRec, TreePatternNode *Pat, bool isInput, 1076 CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp){ 1077 isInputPattern = isInput; 1078 Trees.push_back(Pat); 1079} 1080 1081 1082 1083void TreePattern::error(const std::string &Msg) const { 1084 dump(); 1085 throw TGError(TheRecord->getLoc(), "In " + TheRecord->getName() + ": " + Msg); 1086} 1087 1088TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) { 1089 DefInit *OpDef = dynamic_cast<DefInit*>(Dag->getOperator()); 1090 if (!OpDef) error("Pattern has unexpected operator type!"); 1091 Record *Operator = OpDef->getDef(); 1092 1093 if (Operator->isSubClassOf("ValueType")) { 1094 // If the operator is a ValueType, then this must be "type cast" of a leaf 1095 // node. 1096 if (Dag->getNumArgs() != 1) 1097 error("Type cast only takes one operand!"); 1098 1099 Init *Arg = Dag->getArg(0); 1100 TreePatternNode *New; 1101 if (DefInit *DI = dynamic_cast<DefInit*>(Arg)) { 1102 Record *R = DI->getDef(); 1103 if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag")) { 1104 Dag->setArg(0, new DagInit(DI, "", 1105 std::vector<std::pair<Init*, std::string> >())); 1106 return ParseTreePattern(Dag); 1107 } 1108 New = new TreePatternNode(DI); 1109 } else if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) { 1110 New = ParseTreePattern(DI); 1111 } else if (IntInit *II = dynamic_cast<IntInit*>(Arg)) { 1112 New = new TreePatternNode(II); 1113 if (!Dag->getArgName(0).empty()) 1114 error("Constant int argument should not have a name!"); 1115 } else if (BitsInit *BI = dynamic_cast<BitsInit*>(Arg)) { 1116 // Turn this into an IntInit. 1117 Init *II = BI->convertInitializerTo(new IntRecTy()); 1118 if (II == 0 || !dynamic_cast<IntInit*>(II)) 1119 error("Bits value must be constants!"); 1120 1121 New = new TreePatternNode(dynamic_cast<IntInit*>(II)); 1122 if (!Dag->getArgName(0).empty()) 1123 error("Constant int argument should not have a name!"); 1124 } else { 1125 Arg->dump(); 1126 error("Unknown leaf value for tree pattern!"); 1127 return 0; 1128 } 1129 1130 // Apply the type cast. 1131 New->UpdateNodeType(getValueType(Operator), *this); 1132 if (New->getNumChildren() == 0) 1133 New->setName(Dag->getArgName(0)); 1134 return New; 1135 } 1136 1137 // Verify that this is something that makes sense for an operator. 1138 if (!Operator->isSubClassOf("PatFrag") && 1139 !Operator->isSubClassOf("SDNode") && 1140 !Operator->isSubClassOf("Instruction") && 1141 !Operator->isSubClassOf("SDNodeXForm") && 1142 !Operator->isSubClassOf("Intrinsic") && 1143 Operator->getName() != "set" && 1144 Operator->getName() != "implicit" && 1145 Operator->getName() != "parallel") 1146 error("Unrecognized node '" + Operator->getName() + "'!"); 1147 1148 // Check to see if this is something that is illegal in an input pattern. 1149 if (isInputPattern && (Operator->isSubClassOf("Instruction") || 1150 Operator->isSubClassOf("SDNodeXForm"))) 1151 error("Cannot use '" + Operator->getName() + "' in an input pattern!"); 1152 1153 std::vector<TreePatternNode*> Children; 1154 1155 for (unsigned i = 0, e = Dag->getNumArgs(); i != e; ++i) { 1156 Init *Arg = Dag->getArg(i); 1157 if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) { 1158 Children.push_back(ParseTreePattern(DI)); 1159 if (Children.back()->getName().empty()) 1160 Children.back()->setName(Dag->getArgName(i)); 1161 } else if (DefInit *DefI = dynamic_cast<DefInit*>(Arg)) { 1162 Record *R = DefI->getDef(); 1163 // Direct reference to a leaf DagNode or PatFrag? Turn it into a 1164 // TreePatternNode if its own. 1165 if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag")) { 1166 Dag->setArg(i, new DagInit(DefI, "", 1167 std::vector<std::pair<Init*, std::string> >())); 1168 --i; // Revisit this node... 1169 } else { 1170 TreePatternNode *Node = new TreePatternNode(DefI); 1171 Node->setName(Dag->getArgName(i)); 1172 Children.push_back(Node); 1173 1174 // Input argument? 1175 if (R->getName() == "node") { 1176 if (Dag->getArgName(i).empty()) 1177 error("'node' argument requires a name to match with operand list"); 1178 Args.push_back(Dag->getArgName(i)); 1179 } 1180 } 1181 } else if (IntInit *II = dynamic_cast<IntInit*>(Arg)) { 1182 TreePatternNode *Node = new TreePatternNode(II); 1183 if (!Dag->getArgName(i).empty()) 1184 error("Constant int argument should not have a name!"); 1185 Children.push_back(Node); 1186 } else if (BitsInit *BI = dynamic_cast<BitsInit*>(Arg)) { 1187 // Turn this into an IntInit. 1188 Init *II = BI->convertInitializerTo(new IntRecTy()); 1189 if (II == 0 || !dynamic_cast<IntInit*>(II)) 1190 error("Bits value must be constants!"); 1191 1192 TreePatternNode *Node = new TreePatternNode(dynamic_cast<IntInit*>(II)); 1193 if (!Dag->getArgName(i).empty()) 1194 error("Constant int argument should not have a name!"); 1195 Children.push_back(Node); 1196 } else { 1197 cerr << '"'; 1198 Arg->dump(); 1199 cerr << "\": "; 1200 error("Unknown leaf value for tree pattern!"); 1201 } 1202 } 1203 1204 // If the operator is an intrinsic, then this is just syntactic sugar for for 1205 // (intrinsic_* <number>, ..children..). Pick the right intrinsic node, and 1206 // convert the intrinsic name to a number. 1207 if (Operator->isSubClassOf("Intrinsic")) { 1208 const CodeGenIntrinsic &Int = getDAGPatterns().getIntrinsic(Operator); 1209 unsigned IID = getDAGPatterns().getIntrinsicID(Operator)+1; 1210 1211 // If this intrinsic returns void, it must have side-effects and thus a 1212 // chain. 1213 if (Int.IS.RetVTs[0] == MVT::isVoid) { 1214 Operator = getDAGPatterns().get_intrinsic_void_sdnode(); 1215 } else if (Int.ModRef != CodeGenIntrinsic::NoMem) { 1216 // Has side-effects, requires chain. 1217 Operator = getDAGPatterns().get_intrinsic_w_chain_sdnode(); 1218 } else { 1219 // Otherwise, no chain. 1220 Operator = getDAGPatterns().get_intrinsic_wo_chain_sdnode(); 1221 } 1222 1223 TreePatternNode *IIDNode = new TreePatternNode(new IntInit(IID)); 1224 Children.insert(Children.begin(), IIDNode); 1225 } 1226 1227 TreePatternNode *Result = new TreePatternNode(Operator, Children); 1228 Result->setName(Dag->getName()); 1229 return Result; 1230} 1231 1232/// InferAllTypes - Infer/propagate as many types throughout the expression 1233/// patterns as possible. Return true if all types are inferred, false 1234/// otherwise. Throw an exception if a type contradiction is found. 1235bool TreePattern::InferAllTypes() { 1236 bool MadeChange = true; 1237 while (MadeChange) { 1238 MadeChange = false; 1239 for (unsigned i = 0, e = Trees.size(); i != e; ++i) 1240 MadeChange |= Trees[i]->ApplyTypeConstraints(*this, false); 1241 } 1242 1243 bool HasUnresolvedTypes = false; 1244 for (unsigned i = 0, e = Trees.size(); i != e; ++i) 1245 HasUnresolvedTypes |= Trees[i]->ContainsUnresolvedType(); 1246 return !HasUnresolvedTypes; 1247} 1248 1249void TreePattern::print(std::ostream &OS) const { 1250 OS << getRecord()->getName(); 1251 if (!Args.empty()) { 1252 OS << "(" << Args[0]; 1253 for (unsigned i = 1, e = Args.size(); i != e; ++i) 1254 OS << ", " << Args[i]; 1255 OS << ")"; 1256 } 1257 OS << ": "; 1258 1259 if (Trees.size() > 1) 1260 OS << "[\n"; 1261 for (unsigned i = 0, e = Trees.size(); i != e; ++i) { 1262 OS << "\t"; 1263 Trees[i]->print(OS); 1264 OS << "\n"; 1265 } 1266 1267 if (Trees.size() > 1) 1268 OS << "]\n"; 1269} 1270 1271void TreePattern::dump() const { print(*cerr.stream()); } 1272 1273//===----------------------------------------------------------------------===// 1274// CodeGenDAGPatterns implementation 1275// 1276 1277// FIXME: REMOVE OSTREAM ARGUMENT 1278CodeGenDAGPatterns::CodeGenDAGPatterns(RecordKeeper &R) : Records(R) { 1279 Intrinsics = LoadIntrinsics(Records, false); 1280 TgtIntrinsics = LoadIntrinsics(Records, true); 1281 ParseNodeInfo(); 1282 ParseNodeTransforms(); 1283 ParseComplexPatterns(); 1284 ParsePatternFragments(); 1285 ParseDefaultOperands(); 1286 ParseInstructions(); 1287 ParsePatterns(); 1288 1289 // Generate variants. For example, commutative patterns can match 1290 // multiple ways. Add them to PatternsToMatch as well. 1291 GenerateVariants(); 1292 1293 // Infer instruction flags. For example, we can detect loads, 1294 // stores, and side effects in many cases by examining an 1295 // instruction's pattern. 1296 InferInstructionFlags(); 1297} 1298 1299CodeGenDAGPatterns::~CodeGenDAGPatterns() { 1300 for (std::map<Record*, TreePattern*>::iterator I = PatternFragments.begin(), 1301 E = PatternFragments.end(); I != E; ++I) 1302 delete I->second; 1303} 1304 1305 1306Record *CodeGenDAGPatterns::getSDNodeNamed(const std::string &Name) const { 1307 Record *N = Records.getDef(Name); 1308 if (!N || !N->isSubClassOf("SDNode")) { 1309 cerr << "Error getting SDNode '" << Name << "'!\n"; 1310 exit(1); 1311 } 1312 return N; 1313} 1314 1315// Parse all of the SDNode definitions for the target, populating SDNodes. 1316void CodeGenDAGPatterns::ParseNodeInfo() { 1317 std::vector<Record*> Nodes = Records.getAllDerivedDefinitions("SDNode"); 1318 while (!Nodes.empty()) { 1319 SDNodes.insert(std::make_pair(Nodes.back(), Nodes.back())); 1320 Nodes.pop_back(); 1321 } 1322 1323 // Get the builtin intrinsic nodes. 1324 intrinsic_void_sdnode = getSDNodeNamed("intrinsic_void"); 1325 intrinsic_w_chain_sdnode = getSDNodeNamed("intrinsic_w_chain"); 1326 intrinsic_wo_chain_sdnode = getSDNodeNamed("intrinsic_wo_chain"); 1327} 1328 1329/// ParseNodeTransforms - Parse all SDNodeXForm instances into the SDNodeXForms 1330/// map, and emit them to the file as functions. 1331void CodeGenDAGPatterns::ParseNodeTransforms() { 1332 std::vector<Record*> Xforms = Records.getAllDerivedDefinitions("SDNodeXForm"); 1333 while (!Xforms.empty()) { 1334 Record *XFormNode = Xforms.back(); 1335 Record *SDNode = XFormNode->getValueAsDef("Opcode"); 1336 std::string Code = XFormNode->getValueAsCode("XFormFunction"); 1337 SDNodeXForms.insert(std::make_pair(XFormNode, NodeXForm(SDNode, Code))); 1338 1339 Xforms.pop_back(); 1340 } 1341} 1342 1343void CodeGenDAGPatterns::ParseComplexPatterns() { 1344 std::vector<Record*> AMs = Records.getAllDerivedDefinitions("ComplexPattern"); 1345 while (!AMs.empty()) { 1346 ComplexPatterns.insert(std::make_pair(AMs.back(), AMs.back())); 1347 AMs.pop_back(); 1348 } 1349} 1350 1351 1352/// ParsePatternFragments - Parse all of the PatFrag definitions in the .td 1353/// file, building up the PatternFragments map. After we've collected them all, 1354/// inline fragments together as necessary, so that there are no references left 1355/// inside a pattern fragment to a pattern fragment. 1356/// 1357void CodeGenDAGPatterns::ParsePatternFragments() { 1358 std::vector<Record*> Fragments = Records.getAllDerivedDefinitions("PatFrag"); 1359 1360 // First step, parse all of the fragments. 1361 for (unsigned i = 0, e = Fragments.size(); i != e; ++i) { 1362 DagInit *Tree = Fragments[i]->getValueAsDag("Fragment"); 1363 TreePattern *P = new TreePattern(Fragments[i], Tree, true, *this); 1364 PatternFragments[Fragments[i]] = P; 1365 1366 // Validate the argument list, converting it to set, to discard duplicates. 1367 std::vector<std::string> &Args = P->getArgList(); 1368 std::set<std::string> OperandsSet(Args.begin(), Args.end()); 1369 1370 if (OperandsSet.count("")) 1371 P->error("Cannot have unnamed 'node' values in pattern fragment!"); 1372 1373 // Parse the operands list. 1374 DagInit *OpsList = Fragments[i]->getValueAsDag("Operands"); 1375 DefInit *OpsOp = dynamic_cast<DefInit*>(OpsList->getOperator()); 1376 // Special cases: ops == outs == ins. Different names are used to 1377 // improve readability. 1378 if (!OpsOp || 1379 (OpsOp->getDef()->getName() != "ops" && 1380 OpsOp->getDef()->getName() != "outs" && 1381 OpsOp->getDef()->getName() != "ins")) 1382 P->error("Operands list should start with '(ops ... '!"); 1383 1384 // Copy over the arguments. 1385 Args.clear(); 1386 for (unsigned j = 0, e = OpsList->getNumArgs(); j != e; ++j) { 1387 if (!dynamic_cast<DefInit*>(OpsList->getArg(j)) || 1388 static_cast<DefInit*>(OpsList->getArg(j))-> 1389 getDef()->getName() != "node") 1390 P->error("Operands list should all be 'node' values."); 1391 if (OpsList->getArgName(j).empty()) 1392 P->error("Operands list should have names for each operand!"); 1393 if (!OperandsSet.count(OpsList->getArgName(j))) 1394 P->error("'" + OpsList->getArgName(j) + 1395 "' does not occur in pattern or was multiply specified!"); 1396 OperandsSet.erase(OpsList->getArgName(j)); 1397 Args.push_back(OpsList->getArgName(j)); 1398 } 1399 1400 if (!OperandsSet.empty()) 1401 P->error("Operands list does not contain an entry for operand '" + 1402 *OperandsSet.begin() + "'!"); 1403 1404 // If there is a code init for this fragment, keep track of the fact that 1405 // this fragment uses it. 1406 std::string Code = Fragments[i]->getValueAsCode("Predicate"); 1407 if (!Code.empty()) 1408 P->getOnlyTree()->addPredicateFn("Predicate_"+Fragments[i]->getName()); 1409 1410 // If there is a node transformation corresponding to this, keep track of 1411 // it. 1412 Record *Transform = Fragments[i]->getValueAsDef("OperandTransform"); 1413 if (!getSDNodeTransform(Transform).second.empty()) // not noop xform? 1414 P->getOnlyTree()->setTransformFn(Transform); 1415 } 1416 1417 // Now that we've parsed all of the tree fragments, do a closure on them so 1418 // that there are not references to PatFrags left inside of them. 1419 for (unsigned i = 0, e = Fragments.size(); i != e; ++i) { 1420 TreePattern *ThePat = PatternFragments[Fragments[i]]; 1421 ThePat->InlinePatternFragments(); 1422 1423 // Infer as many types as possible. Don't worry about it if we don't infer 1424 // all of them, some may depend on the inputs of the pattern. 1425 try { 1426 ThePat->InferAllTypes(); 1427 } catch (...) { 1428 // If this pattern fragment is not supported by this target (no types can 1429 // satisfy its constraints), just ignore it. If the bogus pattern is 1430 // actually used by instructions, the type consistency error will be 1431 // reported there. 1432 } 1433 1434 // If debugging, print out the pattern fragment result. 1435 DEBUG(ThePat->dump()); 1436 } 1437} 1438 1439void CodeGenDAGPatterns::ParseDefaultOperands() { 1440 std::vector<Record*> DefaultOps[2]; 1441 DefaultOps[0] = Records.getAllDerivedDefinitions("PredicateOperand"); 1442 DefaultOps[1] = Records.getAllDerivedDefinitions("OptionalDefOperand"); 1443 1444 // Find some SDNode. 1445 assert(!SDNodes.empty() && "No SDNodes parsed?"); 1446 Init *SomeSDNode = new DefInit(SDNodes.begin()->first); 1447 1448 for (unsigned iter = 0; iter != 2; ++iter) { 1449 for (unsigned i = 0, e = DefaultOps[iter].size(); i != e; ++i) { 1450 DagInit *DefaultInfo = DefaultOps[iter][i]->getValueAsDag("DefaultOps"); 1451 1452 // Clone the DefaultInfo dag node, changing the operator from 'ops' to 1453 // SomeSDnode so that we can parse this. 1454 std::vector<std::pair<Init*, std::string> > Ops; 1455 for (unsigned op = 0, e = DefaultInfo->getNumArgs(); op != e; ++op) 1456 Ops.push_back(std::make_pair(DefaultInfo->getArg(op), 1457 DefaultInfo->getArgName(op))); 1458 DagInit *DI = new DagInit(SomeSDNode, "", Ops); 1459 1460 // Create a TreePattern to parse this. 1461 TreePattern P(DefaultOps[iter][i], DI, false, *this); 1462 assert(P.getNumTrees() == 1 && "This ctor can only produce one tree!"); 1463 1464 // Copy the operands over into a DAGDefaultOperand. 1465 DAGDefaultOperand DefaultOpInfo; 1466 1467 TreePatternNode *T = P.getTree(0); 1468 for (unsigned op = 0, e = T->getNumChildren(); op != e; ++op) { 1469 TreePatternNode *TPN = T->getChild(op); 1470 while (TPN->ApplyTypeConstraints(P, false)) 1471 /* Resolve all types */; 1472 1473 if (TPN->ContainsUnresolvedType()) { 1474 if (iter == 0) 1475 throw "Value #" + utostr(i) + " of PredicateOperand '" + 1476 DefaultOps[iter][i]->getName() + "' doesn't have a concrete type!"; 1477 else 1478 throw "Value #" + utostr(i) + " of OptionalDefOperand '" + 1479 DefaultOps[iter][i]->getName() + "' doesn't have a concrete type!"; 1480 } 1481 DefaultOpInfo.DefaultOps.push_back(TPN); 1482 } 1483 1484 // Insert it into the DefaultOperands map so we can find it later. 1485 DefaultOperands[DefaultOps[iter][i]] = DefaultOpInfo; 1486 } 1487 } 1488} 1489 1490/// HandleUse - Given "Pat" a leaf in the pattern, check to see if it is an 1491/// instruction input. Return true if this is a real use. 1492static bool HandleUse(TreePattern *I, TreePatternNode *Pat, 1493 std::map<std::string, TreePatternNode*> &InstInputs, 1494 std::vector<Record*> &InstImpInputs) { 1495 // No name -> not interesting. 1496 if (Pat->getName().empty()) { 1497 if (Pat->isLeaf()) { 1498 DefInit *DI = dynamic_cast<DefInit*>(Pat->getLeafValue()); 1499 if (DI && DI->getDef()->isSubClassOf("RegisterClass")) 1500 I->error("Input " + DI->getDef()->getName() + " must be named!"); 1501 else if (DI && DI->getDef()->isSubClassOf("Register")) 1502 InstImpInputs.push_back(DI->getDef()); 1503 } 1504 return false; 1505 } 1506 1507 Record *Rec; 1508 if (Pat->isLeaf()) { 1509 DefInit *DI = dynamic_cast<DefInit*>(Pat->getLeafValue()); 1510 if (!DI) I->error("Input $" + Pat->getName() + " must be an identifier!"); 1511 Rec = DI->getDef(); 1512 } else { 1513 Rec = Pat->getOperator(); 1514 } 1515 1516 // SRCVALUE nodes are ignored. 1517 if (Rec->getName() == "srcvalue") 1518 return false; 1519 1520 TreePatternNode *&Slot = InstInputs[Pat->getName()]; 1521 if (!Slot) { 1522 Slot = Pat; 1523 } else { 1524 Record *SlotRec; 1525 if (Slot->isLeaf()) { 1526 SlotRec = dynamic_cast<DefInit*>(Slot->getLeafValue())->getDef(); 1527 } else { 1528 assert(Slot->getNumChildren() == 0 && "can't be a use with children!"); 1529 SlotRec = Slot->getOperator(); 1530 } 1531 1532 // Ensure that the inputs agree if we've already seen this input. 1533 if (Rec != SlotRec) 1534 I->error("All $" + Pat->getName() + " inputs must agree with each other"); 1535 if (Slot->getExtTypes() != Pat->getExtTypes()) 1536 I->error("All $" + Pat->getName() + " inputs must agree with each other"); 1537 } 1538 return true; 1539} 1540 1541/// FindPatternInputsAndOutputs - Scan the specified TreePatternNode (which is 1542/// part of "I", the instruction), computing the set of inputs and outputs of 1543/// the pattern. Report errors if we see anything naughty. 1544void CodeGenDAGPatterns:: 1545FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, 1546 std::map<std::string, TreePatternNode*> &InstInputs, 1547 std::map<std::string, TreePatternNode*>&InstResults, 1548 std::vector<Record*> &InstImpInputs, 1549 std::vector<Record*> &InstImpResults) { 1550 if (Pat->isLeaf()) { 1551 bool isUse = HandleUse(I, Pat, InstInputs, InstImpInputs); 1552 if (!isUse && Pat->getTransformFn()) 1553 I->error("Cannot specify a transform function for a non-input value!"); 1554 return; 1555 } else if (Pat->getOperator()->getName() == "implicit") { 1556 for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) { 1557 TreePatternNode *Dest = Pat->getChild(i); 1558 if (!Dest->isLeaf()) 1559 I->error("implicitly defined value should be a register!"); 1560 1561 DefInit *Val = dynamic_cast<DefInit*>(Dest->getLeafValue()); 1562 if (!Val || !Val->getDef()->isSubClassOf("Register")) 1563 I->error("implicitly defined value should be a register!"); 1564 InstImpResults.push_back(Val->getDef()); 1565 } 1566 return; 1567 } else if (Pat->getOperator()->getName() != "set") { 1568 // If this is not a set, verify that the children nodes are not void typed, 1569 // and recurse. 1570 for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) { 1571 if (Pat->getChild(i)->getExtTypeNum(0) == MVT::isVoid) 1572 I->error("Cannot have void nodes inside of patterns!"); 1573 FindPatternInputsAndOutputs(I, Pat->getChild(i), InstInputs, InstResults, 1574 InstImpInputs, InstImpResults); 1575 } 1576 1577 // If this is a non-leaf node with no children, treat it basically as if 1578 // it were a leaf. This handles nodes like (imm). 1579 bool isUse = HandleUse(I, Pat, InstInputs, InstImpInputs); 1580 1581 if (!isUse && Pat->getTransformFn()) 1582 I->error("Cannot specify a transform function for a non-input value!"); 1583 return; 1584 } 1585 1586 // Otherwise, this is a set, validate and collect instruction results. 1587 if (Pat->getNumChildren() == 0) 1588 I->error("set requires operands!"); 1589 1590 if (Pat->getTransformFn()) 1591 I->error("Cannot specify a transform function on a set node!"); 1592 1593 // Check the set destinations. 1594 unsigned NumDests = Pat->getNumChildren()-1; 1595 for (unsigned i = 0; i != NumDests; ++i) { 1596 TreePatternNode *Dest = Pat->getChild(i); 1597 if (!Dest->isLeaf()) 1598 I->error("set destination should be a register!"); 1599 1600 DefInit *Val = dynamic_cast<DefInit*>(Dest->getLeafValue()); 1601 if (!Val) 1602 I->error("set destination should be a register!"); 1603 1604 if (Val->getDef()->isSubClassOf("RegisterClass") || 1605 Val->getDef()->getName() == "ptr_rc") { 1606 if (Dest->getName().empty()) 1607 I->error("set destination must have a name!"); 1608 if (InstResults.count(Dest->getName())) 1609 I->error("cannot set '" + Dest->getName() +"' multiple times"); 1610 InstResults[Dest->getName()] = Dest; 1611 } else if (Val->getDef()->isSubClassOf("Register")) { 1612 InstImpResults.push_back(Val->getDef()); 1613 } else { 1614 I->error("set destination should be a register!"); 1615 } 1616 } 1617 1618 // Verify and collect info from the computation. 1619 FindPatternInputsAndOutputs(I, Pat->getChild(NumDests), 1620 InstInputs, InstResults, 1621 InstImpInputs, InstImpResults); 1622} 1623 1624//===----------------------------------------------------------------------===// 1625// Instruction Analysis 1626//===----------------------------------------------------------------------===// 1627 1628class InstAnalyzer { 1629 const CodeGenDAGPatterns &CDP; 1630 bool &mayStore; 1631 bool &mayLoad; 1632 bool &HasSideEffects; 1633public: 1634 InstAnalyzer(const CodeGenDAGPatterns &cdp, 1635 bool &maystore, bool &mayload, bool &hse) 1636 : CDP(cdp), mayStore(maystore), mayLoad(mayload), HasSideEffects(hse){ 1637 } 1638 1639 /// Analyze - Analyze the specified instruction, returning true if the 1640 /// instruction had a pattern. 1641 bool Analyze(Record *InstRecord) { 1642 const TreePattern *Pattern = CDP.getInstruction(InstRecord).getPattern(); 1643 if (Pattern == 0) { 1644 HasSideEffects = 1; 1645 return false; // No pattern. 1646 } 1647 1648 // FIXME: Assume only the first tree is the pattern. The others are clobber 1649 // nodes. 1650 AnalyzeNode(Pattern->getTree(0)); 1651 return true; 1652 } 1653 1654private: 1655 void AnalyzeNode(const TreePatternNode *N) { 1656 if (N->isLeaf()) { 1657 if (DefInit *DI = dynamic_cast<DefInit*>(N->getLeafValue())) { 1658 Record *LeafRec = DI->getDef(); 1659 // Handle ComplexPattern leaves. 1660 if (LeafRec->isSubClassOf("ComplexPattern")) { 1661 const ComplexPattern &CP = CDP.getComplexPattern(LeafRec); 1662 if (CP.hasProperty(SDNPMayStore)) mayStore = true; 1663 if (CP.hasProperty(SDNPMayLoad)) mayLoad = true; 1664 if (CP.hasProperty(SDNPSideEffect)) HasSideEffects = true; 1665 } 1666 } 1667 return; 1668 } 1669 1670 // Analyze children. 1671 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 1672 AnalyzeNode(N->getChild(i)); 1673 1674 // Ignore set nodes, which are not SDNodes. 1675 if (N->getOperator()->getName() == "set") 1676 return; 1677 1678 // Get information about the SDNode for the operator. 1679 const SDNodeInfo &OpInfo = CDP.getSDNodeInfo(N->getOperator()); 1680 1681 // Notice properties of the node. 1682 if (OpInfo.hasProperty(SDNPMayStore)) mayStore = true; 1683 if (OpInfo.hasProperty(SDNPMayLoad)) mayLoad = true; 1684 if (OpInfo.hasProperty(SDNPSideEffect)) HasSideEffects = true; 1685 1686 if (const CodeGenIntrinsic *IntInfo = N->getIntrinsicInfo(CDP)) { 1687 // If this is an intrinsic, analyze it. 1688 if (IntInfo->ModRef >= CodeGenIntrinsic::ReadArgMem) 1689 mayLoad = true;// These may load memory. 1690 1691 if (IntInfo->ModRef >= CodeGenIntrinsic::WriteArgMem) 1692 mayStore = true;// Intrinsics that can write to memory are 'mayStore'. 1693 1694 if (IntInfo->ModRef >= CodeGenIntrinsic::WriteMem) 1695 // WriteMem intrinsics can have other strange effects. 1696 HasSideEffects = true; 1697 } 1698 } 1699 1700}; 1701 1702static void InferFromPattern(const CodeGenInstruction &Inst, 1703 bool &MayStore, bool &MayLoad, 1704 bool &HasSideEffects, 1705 const CodeGenDAGPatterns &CDP) { 1706 MayStore = MayLoad = HasSideEffects = false; 1707 1708 bool HadPattern = 1709 InstAnalyzer(CDP, MayStore, MayLoad, HasSideEffects).Analyze(Inst.TheDef); 1710 1711 // InstAnalyzer only correctly analyzes mayStore/mayLoad so far. 1712 if (Inst.mayStore) { // If the .td file explicitly sets mayStore, use it. 1713 // If we decided that this is a store from the pattern, then the .td file 1714 // entry is redundant. 1715 if (MayStore) 1716 fprintf(stderr, 1717 "Warning: mayStore flag explicitly set on instruction '%s'" 1718 " but flag already inferred from pattern.\n", 1719 Inst.TheDef->getName().c_str()); 1720 MayStore = true; 1721 } 1722 1723 if (Inst.mayLoad) { // If the .td file explicitly sets mayLoad, use it. 1724 // If we decided that this is a load from the pattern, then the .td file 1725 // entry is redundant. 1726 if (MayLoad) 1727 fprintf(stderr, 1728 "Warning: mayLoad flag explicitly set on instruction '%s'" 1729 " but flag already inferred from pattern.\n", 1730 Inst.TheDef->getName().c_str()); 1731 MayLoad = true; 1732 } 1733 1734 if (Inst.neverHasSideEffects) { 1735 if (HadPattern) 1736 fprintf(stderr, "Warning: neverHasSideEffects set on instruction '%s' " 1737 "which already has a pattern\n", Inst.TheDef->getName().c_str()); 1738 HasSideEffects = false; 1739 } 1740 1741 if (Inst.hasSideEffects) { 1742 if (HasSideEffects) 1743 fprintf(stderr, "Warning: hasSideEffects set on instruction '%s' " 1744 "which already inferred this.\n", Inst.TheDef->getName().c_str()); 1745 HasSideEffects = true; 1746 } 1747} 1748 1749/// ParseInstructions - Parse all of the instructions, inlining and resolving 1750/// any fragments involved. This populates the Instructions list with fully 1751/// resolved instructions. 1752void CodeGenDAGPatterns::ParseInstructions() { 1753 std::vector<Record*> Instrs = Records.getAllDerivedDefinitions("Instruction"); 1754 1755 for (unsigned i = 0, e = Instrs.size(); i != e; ++i) { 1756 ListInit *LI = 0; 1757 1758 if (dynamic_cast<ListInit*>(Instrs[i]->getValueInit("Pattern"))) 1759 LI = Instrs[i]->getValueAsListInit("Pattern"); 1760 1761 // If there is no pattern, only collect minimal information about the 1762 // instruction for its operand list. We have to assume that there is one 1763 // result, as we have no detailed info. 1764 if (!LI || LI->getSize() == 0) { 1765 std::vector<Record*> Results; 1766 std::vector<Record*> Operands; 1767 1768 CodeGenInstruction &InstInfo =Target.getInstruction(Instrs[i]->getName()); 1769 1770 if (InstInfo.OperandList.size() != 0) { 1771 if (InstInfo.NumDefs == 0) { 1772 // These produce no results 1773 for (unsigned j = 0, e = InstInfo.OperandList.size(); j < e; ++j) 1774 Operands.push_back(InstInfo.OperandList[j].Rec); 1775 } else { 1776 // Assume the first operand is the result. 1777 Results.push_back(InstInfo.OperandList[0].Rec); 1778 1779 // The rest are inputs. 1780 for (unsigned j = 1, e = InstInfo.OperandList.size(); j < e; ++j) 1781 Operands.push_back(InstInfo.OperandList[j].Rec); 1782 } 1783 } 1784 1785 // Create and insert the instruction. 1786 std::vector<Record*> ImpResults; 1787 std::vector<Record*> ImpOperands; 1788 Instructions.insert(std::make_pair(Instrs[i], 1789 DAGInstruction(0, Results, Operands, ImpResults, 1790 ImpOperands))); 1791 continue; // no pattern. 1792 } 1793 1794 // Parse the instruction. 1795 TreePattern *I = new TreePattern(Instrs[i], LI, true, *this); 1796 // Inline pattern fragments into it. 1797 I->InlinePatternFragments(); 1798 1799 // Infer as many types as possible. If we cannot infer all of them, we can 1800 // never do anything with this instruction pattern: report it to the user. 1801 if (!I->InferAllTypes()) 1802 I->error("Could not infer all types in pattern!"); 1803 1804 // InstInputs - Keep track of all of the inputs of the instruction, along 1805 // with the record they are declared as. 1806 std::map<std::string, TreePatternNode*> InstInputs; 1807 1808 // InstResults - Keep track of all the virtual registers that are 'set' 1809 // in the instruction, including what reg class they are. 1810 std::map<std::string, TreePatternNode*> InstResults; 1811 1812 std::vector<Record*> InstImpInputs; 1813 std::vector<Record*> InstImpResults; 1814 1815 // Verify that the top-level forms in the instruction are of void type, and 1816 // fill in the InstResults map. 1817 for (unsigned j = 0, e = I->getNumTrees(); j != e; ++j) { 1818 TreePatternNode *Pat = I->getTree(j); 1819 if (Pat->getExtTypeNum(0) != MVT::isVoid) 1820 I->error("Top-level forms in instruction pattern should have" 1821 " void types"); 1822 1823 // Find inputs and outputs, and verify the structure of the uses/defs. 1824 FindPatternInputsAndOutputs(I, Pat, InstInputs, InstResults, 1825 InstImpInputs, InstImpResults); 1826 } 1827 1828 // Now that we have inputs and outputs of the pattern, inspect the operands 1829 // list for the instruction. This determines the order that operands are 1830 // added to the machine instruction the node corresponds to. 1831 unsigned NumResults = InstResults.size(); 1832 1833 // Parse the operands list from the (ops) list, validating it. 1834 assert(I->getArgList().empty() && "Args list should still be empty here!"); 1835 CodeGenInstruction &CGI = Target.getInstruction(Instrs[i]->getName()); 1836 1837 // Check that all of the results occur first in the list. 1838 std::vector<Record*> Results; 1839 TreePatternNode *Res0Node = NULL; 1840 for (unsigned i = 0; i != NumResults; ++i) { 1841 if (i == CGI.OperandList.size()) 1842 I->error("'" + InstResults.begin()->first + 1843 "' set but does not appear in operand list!"); 1844 const std::string &OpName = CGI.OperandList[i].Name; 1845 1846 // Check that it exists in InstResults. 1847 TreePatternNode *RNode = InstResults[OpName]; 1848 if (RNode == 0) 1849 I->error("Operand $" + OpName + " does not exist in operand list!"); 1850 1851 if (i == 0) 1852 Res0Node = RNode; 1853 Record *R = dynamic_cast<DefInit*>(RNode->getLeafValue())->getDef(); 1854 if (R == 0) 1855 I->error("Operand $" + OpName + " should be a set destination: all " 1856 "outputs must occur before inputs in operand list!"); 1857 1858 if (CGI.OperandList[i].Rec != R) 1859 I->error("Operand $" + OpName + " class mismatch!"); 1860 1861 // Remember the return type. 1862 Results.push_back(CGI.OperandList[i].Rec); 1863 1864 // Okay, this one checks out. 1865 InstResults.erase(OpName); 1866 } 1867 1868 // Loop over the inputs next. Make a copy of InstInputs so we can destroy 1869 // the copy while we're checking the inputs. 1870 std::map<std::string, TreePatternNode*> InstInputsCheck(InstInputs); 1871 1872 std::vector<TreePatternNode*> ResultNodeOperands; 1873 std::vector<Record*> Operands; 1874 for (unsigned i = NumResults, e = CGI.OperandList.size(); i != e; ++i) { 1875 CodeGenInstruction::OperandInfo &Op = CGI.OperandList[i]; 1876 const std::string &OpName = Op.Name; 1877 if (OpName.empty()) 1878 I->error("Operand #" + utostr(i) + " in operands list has no name!"); 1879 1880 if (!InstInputsCheck.count(OpName)) { 1881 // If this is an predicate operand or optional def operand with an 1882 // DefaultOps set filled in, we can ignore this. When we codegen it, 1883 // we will do so as always executed. 1884 if (Op.Rec->isSubClassOf("PredicateOperand") || 1885 Op.Rec->isSubClassOf("OptionalDefOperand")) { 1886 // Does it have a non-empty DefaultOps field? If so, ignore this 1887 // operand. 1888 if (!getDefaultOperand(Op.Rec).DefaultOps.empty()) 1889 continue; 1890 } 1891 I->error("Operand $" + OpName + 1892 " does not appear in the instruction pattern"); 1893 } 1894 TreePatternNode *InVal = InstInputsCheck[OpName]; 1895 InstInputsCheck.erase(OpName); // It occurred, remove from map. 1896 1897 if (InVal->isLeaf() && 1898 dynamic_cast<DefInit*>(InVal->getLeafValue())) { 1899 Record *InRec = static_cast<DefInit*>(InVal->getLeafValue())->getDef(); 1900 if (Op.Rec != InRec && !InRec->isSubClassOf("ComplexPattern")) 1901 I->error("Operand $" + OpName + "'s register class disagrees" 1902 " between the operand and pattern"); 1903 } 1904 Operands.push_back(Op.Rec); 1905 1906 // Construct the result for the dest-pattern operand list. 1907 TreePatternNode *OpNode = InVal->clone(); 1908 1909 // No predicate is useful on the result. 1910 OpNode->clearPredicateFns(); 1911 1912 // Promote the xform function to be an explicit node if set. 1913 if (Record *Xform = OpNode->getTransformFn()) { 1914 OpNode->setTransformFn(0); 1915 std::vector<TreePatternNode*> Children; 1916 Children.push_back(OpNode); 1917 OpNode = new TreePatternNode(Xform, Children); 1918 } 1919 1920 ResultNodeOperands.push_back(OpNode); 1921 } 1922 1923 if (!InstInputsCheck.empty()) 1924 I->error("Input operand $" + InstInputsCheck.begin()->first + 1925 " occurs in pattern but not in operands list!"); 1926 1927 TreePatternNode *ResultPattern = 1928 new TreePatternNode(I->getRecord(), ResultNodeOperands); 1929 // Copy fully inferred output node type to instruction result pattern. 1930 if (NumResults > 0) 1931 ResultPattern->setTypes(Res0Node->getExtTypes()); 1932 1933 // Create and insert the instruction. 1934 // FIXME: InstImpResults and InstImpInputs should not be part of 1935 // DAGInstruction. 1936 DAGInstruction TheInst(I, Results, Operands, InstImpResults, InstImpInputs); 1937 Instructions.insert(std::make_pair(I->getRecord(), TheInst)); 1938 1939 // Use a temporary tree pattern to infer all types and make sure that the 1940 // constructed result is correct. This depends on the instruction already 1941 // being inserted into the Instructions map. 1942 TreePattern Temp(I->getRecord(), ResultPattern, false, *this); 1943 Temp.InferAllTypes(); 1944 1945 DAGInstruction &TheInsertedInst = Instructions.find(I->getRecord())->second; 1946 TheInsertedInst.setResultPattern(Temp.getOnlyTree()); 1947 1948 DEBUG(I->dump()); 1949 } 1950 1951 // If we can, convert the instructions to be patterns that are matched! 1952 for (std::map<Record*, DAGInstruction>::iterator II = Instructions.begin(), 1953 E = Instructions.end(); II != E; ++II) { 1954 DAGInstruction &TheInst = II->second; 1955 const TreePattern *I = TheInst.getPattern(); 1956 if (I == 0) continue; // No pattern. 1957 1958 // FIXME: Assume only the first tree is the pattern. The others are clobber 1959 // nodes. 1960 TreePatternNode *Pattern = I->getTree(0); 1961 TreePatternNode *SrcPattern; 1962 if (Pattern->getOperator()->getName() == "set") { 1963 SrcPattern = Pattern->getChild(Pattern->getNumChildren()-1)->clone(); 1964 } else{ 1965 // Not a set (store or something?) 1966 SrcPattern = Pattern; 1967 } 1968 1969 std::string Reason; 1970 if (!SrcPattern->canPatternMatch(Reason, *this)) 1971 I->error("Instruction can never match: " + Reason); 1972 1973 Record *Instr = II->first; 1974 TreePatternNode *DstPattern = TheInst.getResultPattern(); 1975 PatternsToMatch. 1976 push_back(PatternToMatch(Instr->getValueAsListInit("Predicates"), 1977 SrcPattern, DstPattern, TheInst.getImpResults(), 1978 Instr->getValueAsInt("AddedComplexity"))); 1979 } 1980} 1981 1982 1983void CodeGenDAGPatterns::InferInstructionFlags() { 1984 std::map<std::string, CodeGenInstruction> &InstrDescs = 1985 Target.getInstructions(); 1986 for (std::map<std::string, CodeGenInstruction>::iterator 1987 II = InstrDescs.begin(), E = InstrDescs.end(); II != E; ++II) { 1988 CodeGenInstruction &InstInfo = II->second; 1989 // Determine properties of the instruction from its pattern. 1990 bool MayStore, MayLoad, HasSideEffects; 1991 InferFromPattern(InstInfo, MayStore, MayLoad, HasSideEffects, *this); 1992 InstInfo.mayStore = MayStore; 1993 InstInfo.mayLoad = MayLoad; 1994 InstInfo.hasSideEffects = HasSideEffects; 1995 } 1996} 1997 1998void CodeGenDAGPatterns::ParsePatterns() { 1999 std::vector<Record*> Patterns = Records.getAllDerivedDefinitions("Pattern"); 2000 2001 for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { 2002 DagInit *Tree = Patterns[i]->getValueAsDag("PatternToMatch"); 2003 DefInit *OpDef = dynamic_cast<DefInit*>(Tree->getOperator()); 2004 Record *Operator = OpDef->getDef(); 2005 TreePattern *Pattern; 2006 if (Operator->getName() != "parallel") 2007 Pattern = new TreePattern(Patterns[i], Tree, true, *this); 2008 else { 2009 std::vector<Init*> Values; 2010 for (unsigned j = 0, ee = Tree->getNumArgs(); j != ee; ++j) 2011 Values.push_back(Tree->getArg(j)); 2012 ListInit *LI = new ListInit(Values); 2013 Pattern = new TreePattern(Patterns[i], LI, true, *this); 2014 } 2015 2016 // Inline pattern fragments into it. 2017 Pattern->InlinePatternFragments(); 2018 2019 ListInit *LI = Patterns[i]->getValueAsListInit("ResultInstrs"); 2020 if (LI->getSize() == 0) continue; // no pattern. 2021 2022 // Parse the instruction. 2023 TreePattern *Result = new TreePattern(Patterns[i], LI, false, *this); 2024 2025 // Inline pattern fragments into it. 2026 Result->InlinePatternFragments(); 2027 2028 if (Result->getNumTrees() != 1) 2029 Result->error("Cannot handle instructions producing instructions " 2030 "with temporaries yet!"); 2031 2032 bool IterateInference; 2033 bool InferredAllPatternTypes, InferredAllResultTypes; 2034 do { 2035 // Infer as many types as possible. If we cannot infer all of them, we 2036 // can never do anything with this pattern: report it to the user. 2037 InferredAllPatternTypes = Pattern->InferAllTypes(); 2038 2039 // Infer as many types as possible. If we cannot infer all of them, we 2040 // can never do anything with this pattern: report it to the user. 2041 InferredAllResultTypes = Result->InferAllTypes(); 2042 2043 // Apply the type of the result to the source pattern. This helps us 2044 // resolve cases where the input type is known to be a pointer type (which 2045 // is considered resolved), but the result knows it needs to be 32- or 2046 // 64-bits. Infer the other way for good measure. 2047 IterateInference = Pattern->getTree(0)-> 2048 UpdateNodeType(Result->getTree(0)->getExtTypes(), *Result); 2049 IterateInference |= Result->getTree(0)-> 2050 UpdateNodeType(Pattern->getTree(0)->getExtTypes(), *Result); 2051 } while (IterateInference); 2052 2053 // Verify that we inferred enough types that we can do something with the 2054 // pattern and result. If these fire the user has to add type casts. 2055 if (!InferredAllPatternTypes) 2056 Pattern->error("Could not infer all types in pattern!"); 2057 if (!InferredAllResultTypes) 2058 Result->error("Could not infer all types in pattern result!"); 2059 2060 // Validate that the input pattern is correct. 2061 std::map<std::string, TreePatternNode*> InstInputs; 2062 std::map<std::string, TreePatternNode*> InstResults; 2063 std::vector<Record*> InstImpInputs; 2064 std::vector<Record*> InstImpResults; 2065 for (unsigned j = 0, ee = Pattern->getNumTrees(); j != ee; ++j) 2066 FindPatternInputsAndOutputs(Pattern, Pattern->getTree(j), 2067 InstInputs, InstResults, 2068 InstImpInputs, InstImpResults); 2069 2070 // Promote the xform function to be an explicit node if set. 2071 TreePatternNode *DstPattern = Result->getOnlyTree(); 2072 std::vector<TreePatternNode*> ResultNodeOperands; 2073 for (unsigned ii = 0, ee = DstPattern->getNumChildren(); ii != ee; ++ii) { 2074 TreePatternNode *OpNode = DstPattern->getChild(ii); 2075 if (Record *Xform = OpNode->getTransformFn()) { 2076 OpNode->setTransformFn(0); 2077 std::vector<TreePatternNode*> Children; 2078 Children.push_back(OpNode); 2079 OpNode = new TreePatternNode(Xform, Children); 2080 } 2081 ResultNodeOperands.push_back(OpNode); 2082 } 2083 DstPattern = Result->getOnlyTree(); 2084 if (!DstPattern->isLeaf()) 2085 DstPattern = new TreePatternNode(DstPattern->getOperator(), 2086 ResultNodeOperands); 2087 DstPattern->setTypes(Result->getOnlyTree()->getExtTypes()); 2088 TreePattern Temp(Result->getRecord(), DstPattern, false, *this); 2089 Temp.InferAllTypes(); 2090 2091 std::string Reason; 2092 if (!Pattern->getTree(0)->canPatternMatch(Reason, *this)) 2093 Pattern->error("Pattern can never match: " + Reason); 2094 2095 PatternsToMatch. 2096 push_back(PatternToMatch(Patterns[i]->getValueAsListInit("Predicates"), 2097 Pattern->getTree(0), 2098 Temp.getOnlyTree(), InstImpResults, 2099 Patterns[i]->getValueAsInt("AddedComplexity"))); 2100 } 2101} 2102 2103/// CombineChildVariants - Given a bunch of permutations of each child of the 2104/// 'operator' node, put them together in all possible ways. 2105static void CombineChildVariants(TreePatternNode *Orig, 2106 const std::vector<std::vector<TreePatternNode*> > &ChildVariants, 2107 std::vector<TreePatternNode*> &OutVariants, 2108 CodeGenDAGPatterns &CDP, 2109 const MultipleUseVarSet &DepVars) { 2110 // Make sure that each operand has at least one variant to choose from. 2111 for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i) 2112 if (ChildVariants[i].empty()) 2113 return; 2114 2115 // The end result is an all-pairs construction of the resultant pattern. 2116 std::vector<unsigned> Idxs; 2117 Idxs.resize(ChildVariants.size()); 2118 bool NotDone; 2119 do { 2120#ifndef NDEBUG 2121 if (DebugFlag && !Idxs.empty()) { 2122 cerr << Orig->getOperator()->getName() << ": Idxs = [ "; 2123 for (unsigned i = 0; i < Idxs.size(); ++i) { 2124 cerr << Idxs[i] << " "; 2125 } 2126 cerr << "]\n"; 2127 } 2128#endif 2129 // Create the variant and add it to the output list. 2130 std::vector<TreePatternNode*> NewChildren; 2131 for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i) 2132 NewChildren.push_back(ChildVariants[i][Idxs[i]]); 2133 TreePatternNode *R = new TreePatternNode(Orig->getOperator(), NewChildren); 2134 2135 // Copy over properties. 2136 R->setName(Orig->getName()); 2137 R->setPredicateFns(Orig->getPredicateFns()); 2138 R->setTransformFn(Orig->getTransformFn()); 2139 R->setTypes(Orig->getExtTypes()); 2140 2141 // If this pattern cannot match, do not include it as a variant. 2142 std::string ErrString; 2143 if (!R->canPatternMatch(ErrString, CDP)) { 2144 delete R; 2145 } else { 2146 bool AlreadyExists = false; 2147 2148 // Scan to see if this pattern has already been emitted. We can get 2149 // duplication due to things like commuting: 2150 // (and GPRC:$a, GPRC:$b) -> (and GPRC:$b, GPRC:$a) 2151 // which are the same pattern. Ignore the dups. 2152 for (unsigned i = 0, e = OutVariants.size(); i != e; ++i) 2153 if (R->isIsomorphicTo(OutVariants[i], DepVars)) { 2154 AlreadyExists = true; 2155 break; 2156 } 2157 2158 if (AlreadyExists) 2159 delete R; 2160 else 2161 OutVariants.push_back(R); 2162 } 2163 2164 // Increment indices to the next permutation by incrementing the 2165 // indicies from last index backward, e.g., generate the sequence 2166 // [0, 0], [0, 1], [1, 0], [1, 1]. 2167 int IdxsIdx; 2168 for (IdxsIdx = Idxs.size() - 1; IdxsIdx >= 0; --IdxsIdx) { 2169 if (++Idxs[IdxsIdx] == ChildVariants[IdxsIdx].size()) 2170 Idxs[IdxsIdx] = 0; 2171 else 2172 break; 2173 } 2174 NotDone = (IdxsIdx >= 0); 2175 } while (NotDone); 2176} 2177 2178/// CombineChildVariants - A helper function for binary operators. 2179/// 2180static void CombineChildVariants(TreePatternNode *Orig, 2181 const std::vector<TreePatternNode*> &LHS, 2182 const std::vector<TreePatternNode*> &RHS, 2183 std::vector<TreePatternNode*> &OutVariants, 2184 CodeGenDAGPatterns &CDP, 2185 const MultipleUseVarSet &DepVars) { 2186 std::vector<std::vector<TreePatternNode*> > ChildVariants; 2187 ChildVariants.push_back(LHS); 2188 ChildVariants.push_back(RHS); 2189 CombineChildVariants(Orig, ChildVariants, OutVariants, CDP, DepVars); 2190} 2191 2192 2193static void GatherChildrenOfAssociativeOpcode(TreePatternNode *N, 2194 std::vector<TreePatternNode *> &Children) { 2195 assert(N->getNumChildren()==2 &&"Associative but doesn't have 2 children!"); 2196 Record *Operator = N->getOperator(); 2197 2198 // Only permit raw nodes. 2199 if (!N->getName().empty() || !N->getPredicateFns().empty() || 2200 N->getTransformFn()) { 2201 Children.push_back(N); 2202 return; 2203 } 2204 2205 if (N->getChild(0)->isLeaf() || N->getChild(0)->getOperator() != Operator) 2206 Children.push_back(N->getChild(0)); 2207 else 2208 GatherChildrenOfAssociativeOpcode(N->getChild(0), Children); 2209 2210 if (N->getChild(1)->isLeaf() || N->getChild(1)->getOperator() != Operator) 2211 Children.push_back(N->getChild(1)); 2212 else 2213 GatherChildrenOfAssociativeOpcode(N->getChild(1), Children); 2214} 2215 2216/// GenerateVariantsOf - Given a pattern N, generate all permutations we can of 2217/// the (potentially recursive) pattern by using algebraic laws. 2218/// 2219static void GenerateVariantsOf(TreePatternNode *N, 2220 std::vector<TreePatternNode*> &OutVariants, 2221 CodeGenDAGPatterns &CDP, 2222 const MultipleUseVarSet &DepVars) { 2223 // We cannot permute leaves. 2224 if (N->isLeaf()) { 2225 OutVariants.push_back(N); 2226 return; 2227 } 2228 2229 // Look up interesting info about the node. 2230 const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(N->getOperator()); 2231 2232 // If this node is associative, re-associate. 2233 if (NodeInfo.hasProperty(SDNPAssociative)) { 2234 // Re-associate by pulling together all of the linked operators 2235 std::vector<TreePatternNode*> MaximalChildren; 2236 GatherChildrenOfAssociativeOpcode(N, MaximalChildren); 2237 2238 // Only handle child sizes of 3. Otherwise we'll end up trying too many 2239 // permutations. 2240 if (MaximalChildren.size() == 3) { 2241 // Find the variants of all of our maximal children. 2242 std::vector<TreePatternNode*> AVariants, BVariants, CVariants; 2243 GenerateVariantsOf(MaximalChildren[0], AVariants, CDP, DepVars); 2244 GenerateVariantsOf(MaximalChildren[1], BVariants, CDP, DepVars); 2245 GenerateVariantsOf(MaximalChildren[2], CVariants, CDP, DepVars); 2246 2247 // There are only two ways we can permute the tree: 2248 // (A op B) op C and A op (B op C) 2249 // Within these forms, we can also permute A/B/C. 2250 2251 // Generate legal pair permutations of A/B/C. 2252 std::vector<TreePatternNode*> ABVariants; 2253 std::vector<TreePatternNode*> BAVariants; 2254 std::vector<TreePatternNode*> ACVariants; 2255 std::vector<TreePatternNode*> CAVariants; 2256 std::vector<TreePatternNode*> BCVariants; 2257 std::vector<TreePatternNode*> CBVariants; 2258 CombineChildVariants(N, AVariants, BVariants, ABVariants, CDP, DepVars); 2259 CombineChildVariants(N, BVariants, AVariants, BAVariants, CDP, DepVars); 2260 CombineChildVariants(N, AVariants, CVariants, ACVariants, CDP, DepVars); 2261 CombineChildVariants(N, CVariants, AVariants, CAVariants, CDP, DepVars); 2262 CombineChildVariants(N, BVariants, CVariants, BCVariants, CDP, DepVars); 2263 CombineChildVariants(N, CVariants, BVariants, CBVariants, CDP, DepVars); 2264 2265 // Combine those into the result: (x op x) op x 2266 CombineChildVariants(N, ABVariants, CVariants, OutVariants, CDP, DepVars); 2267 CombineChildVariants(N, BAVariants, CVariants, OutVariants, CDP, DepVars); 2268 CombineChildVariants(N, ACVariants, BVariants, OutVariants, CDP, DepVars); 2269 CombineChildVariants(N, CAVariants, BVariants, OutVariants, CDP, DepVars); 2270 CombineChildVariants(N, BCVariants, AVariants, OutVariants, CDP, DepVars); 2271 CombineChildVariants(N, CBVariants, AVariants, OutVariants, CDP, DepVars); 2272 2273 // Combine those into the result: x op (x op x) 2274 CombineChildVariants(N, CVariants, ABVariants, OutVariants, CDP, DepVars); 2275 CombineChildVariants(N, CVariants, BAVariants, OutVariants, CDP, DepVars); 2276 CombineChildVariants(N, BVariants, ACVariants, OutVariants, CDP, DepVars); 2277 CombineChildVariants(N, BVariants, CAVariants, OutVariants, CDP, DepVars); 2278 CombineChildVariants(N, AVariants, BCVariants, OutVariants, CDP, DepVars); 2279 CombineChildVariants(N, AVariants, CBVariants, OutVariants, CDP, DepVars); 2280 return; 2281 } 2282 } 2283 2284 // Compute permutations of all children. 2285 std::vector<std::vector<TreePatternNode*> > ChildVariants; 2286 ChildVariants.resize(N->getNumChildren()); 2287 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 2288 GenerateVariantsOf(N->getChild(i), ChildVariants[i], CDP, DepVars); 2289 2290 // Build all permutations based on how the children were formed. 2291 CombineChildVariants(N, ChildVariants, OutVariants, CDP, DepVars); 2292 2293 // If this node is commutative, consider the commuted order. 2294 bool isCommIntrinsic = N->isCommutativeIntrinsic(CDP); 2295 if (NodeInfo.hasProperty(SDNPCommutative) || isCommIntrinsic) { 2296 assert((N->getNumChildren()==2 || isCommIntrinsic) && 2297 "Commutative but doesn't have 2 children!"); 2298 // Don't count children which are actually register references. 2299 unsigned NC = 0; 2300 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { 2301 TreePatternNode *Child = N->getChild(i); 2302 if (Child->isLeaf()) 2303 if (DefInit *DI = dynamic_cast<DefInit*>(Child->getLeafValue())) { 2304 Record *RR = DI->getDef(); 2305 if (RR->isSubClassOf("Register")) 2306 continue; 2307 } 2308 NC++; 2309 } 2310 // Consider the commuted order. 2311 if (isCommIntrinsic) { 2312 // Commutative intrinsic. First operand is the intrinsic id, 2nd and 3rd 2313 // operands are the commutative operands, and there might be more operands 2314 // after those. 2315 assert(NC >= 3 && 2316 "Commutative intrinsic should have at least 3 childrean!"); 2317 std::vector<std::vector<TreePatternNode*> > Variants; 2318 Variants.push_back(ChildVariants[0]); // Intrinsic id. 2319 Variants.push_back(ChildVariants[2]); 2320 Variants.push_back(ChildVariants[1]); 2321 for (unsigned i = 3; i != NC; ++i) 2322 Variants.push_back(ChildVariants[i]); 2323 CombineChildVariants(N, Variants, OutVariants, CDP, DepVars); 2324 } else if (NC == 2) 2325 CombineChildVariants(N, ChildVariants[1], ChildVariants[0], 2326 OutVariants, CDP, DepVars); 2327 } 2328} 2329 2330 2331// GenerateVariants - Generate variants. For example, commutative patterns can 2332// match multiple ways. Add them to PatternsToMatch as well. 2333void CodeGenDAGPatterns::GenerateVariants() { 2334 DOUT << "Generating instruction variants.\n"; 2335 2336 // Loop over all of the patterns we've collected, checking to see if we can 2337 // generate variants of the instruction, through the exploitation of 2338 // identities. This permits the target to provide aggressive matching without 2339 // the .td file having to contain tons of variants of instructions. 2340 // 2341 // Note that this loop adds new patterns to the PatternsToMatch list, but we 2342 // intentionally do not reconsider these. Any variants of added patterns have 2343 // already been added. 2344 // 2345 for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) { 2346 MultipleUseVarSet DepVars; 2347 std::vector<TreePatternNode*> Variants; 2348 FindDepVars(PatternsToMatch[i].getSrcPattern(), DepVars); 2349 DOUT << "Dependent/multiply used variables: "; 2350 DEBUG(DumpDepVars(DepVars)); 2351 DOUT << "\n"; 2352 GenerateVariantsOf(PatternsToMatch[i].getSrcPattern(), Variants, *this, DepVars); 2353 2354 assert(!Variants.empty() && "Must create at least original variant!"); 2355 Variants.erase(Variants.begin()); // Remove the original pattern. 2356 2357 if (Variants.empty()) // No variants for this pattern. 2358 continue; 2359 2360 DOUT << "FOUND VARIANTS OF: "; 2361 DEBUG(PatternsToMatch[i].getSrcPattern()->dump()); 2362 DOUT << "\n"; 2363 2364 for (unsigned v = 0, e = Variants.size(); v != e; ++v) { 2365 TreePatternNode *Variant = Variants[v]; 2366 2367 DOUT << " VAR#" << v << ": "; 2368 DEBUG(Variant->dump()); 2369 DOUT << "\n"; 2370 2371 // Scan to see if an instruction or explicit pattern already matches this. 2372 bool AlreadyExists = false; 2373 for (unsigned p = 0, e = PatternsToMatch.size(); p != e; ++p) { 2374 // Check to see if this variant already exists. 2375 if (Variant->isIsomorphicTo(PatternsToMatch[p].getSrcPattern(), DepVars)) { 2376 DOUT << " *** ALREADY EXISTS, ignoring variant.\n"; 2377 AlreadyExists = true; 2378 break; 2379 } 2380 } 2381 // If we already have it, ignore the variant. 2382 if (AlreadyExists) continue; 2383 2384 // Otherwise, add it to the list of patterns we have. 2385 PatternsToMatch. 2386 push_back(PatternToMatch(PatternsToMatch[i].getPredicates(), 2387 Variant, PatternsToMatch[i].getDstPattern(), 2388 PatternsToMatch[i].getDstRegs(), 2389 PatternsToMatch[i].getAddedComplexity())); 2390 } 2391 2392 DOUT << "\n"; 2393 } 2394} 2395 2396