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