DAGISelEmitter.cpp revision ce1381afd9e77c323b973989d8bb257dc33e7dda
1//===- DAGISelEmitter.cpp - Generate an instruction selector --------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by Chris Lattner and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This tablegen backend emits a DAG instruction selector. 11// 12//===----------------------------------------------------------------------===// 13 14#include "DAGISelEmitter.h" 15#include "Record.h" 16#include "llvm/ADT/StringExtras.h" 17#include "llvm/Support/Debug.h" 18#include "llvm/Support/MathExtras.h" 19#include <algorithm> 20#include <set> 21using namespace llvm; 22 23//===----------------------------------------------------------------------===// 24// Helpers for working with extended types. 25 26/// FilterVTs - Filter a list of VT's according to a predicate. 27/// 28template<typename T> 29static std::vector<MVT::ValueType> 30FilterVTs(const std::vector<MVT::ValueType> &InVTs, T Filter) { 31 std::vector<MVT::ValueType> Result; 32 for (unsigned i = 0, e = InVTs.size(); i != e; ++i) 33 if (Filter(InVTs[i])) 34 Result.push_back(InVTs[i]); 35 return Result; 36} 37 38template<typename T> 39static std::vector<unsigned char> 40FilterEVTs(const std::vector<unsigned char> &InVTs, T Filter) { 41 std::vector<unsigned char> Result; 42 for (unsigned i = 0, e = InVTs.size(); i != e; ++i) 43 if (Filter((MVT::ValueType)InVTs[i])) 44 Result.push_back(InVTs[i]); 45 return Result; 46} 47 48static std::vector<unsigned char> 49ConvertVTs(const std::vector<MVT::ValueType> &InVTs) { 50 std::vector<unsigned char> Result; 51 for (unsigned i = 0, e = InVTs.size(); i != e; ++i) 52 Result.push_back(InVTs[i]); 53 return Result; 54} 55 56static bool LHSIsSubsetOfRHS(const std::vector<unsigned char> &LHS, 57 const std::vector<unsigned char> &RHS) { 58 if (LHS.size() > RHS.size()) return false; 59 for (unsigned i = 0, e = LHS.size(); i != e; ++i) 60 if (std::find(RHS.begin(), RHS.end(), LHS[i]) == RHS.end()) 61 return false; 62 return true; 63} 64 65/// isExtIntegerVT - Return true if the specified extended value type vector 66/// contains isInt or an integer value type. 67static bool isExtIntegerInVTs(const std::vector<unsigned char> &EVTs) { 68 assert(!EVTs.empty() && "Cannot check for integer in empty ExtVT list!"); 69 return EVTs[0] == MVT::isInt || !(FilterEVTs(EVTs, MVT::isInteger).empty()); 70} 71 72/// isExtFloatingPointVT - Return true if the specified extended value type 73/// vector contains isFP or a FP value type. 74static bool isExtFloatingPointInVTs(const std::vector<unsigned char> &EVTs) { 75 assert(!EVTs.empty() && "Cannot check for integer in empty ExtVT list!"); 76 return EVTs[0] == MVT::isFP || 77 !(FilterEVTs(EVTs, MVT::isFloatingPoint).empty()); 78} 79 80//===----------------------------------------------------------------------===// 81// SDTypeConstraint implementation 82// 83 84SDTypeConstraint::SDTypeConstraint(Record *R) { 85 OperandNo = R->getValueAsInt("OperandNum"); 86 87 if (R->isSubClassOf("SDTCisVT")) { 88 ConstraintType = SDTCisVT; 89 x.SDTCisVT_Info.VT = getValueType(R->getValueAsDef("VT")); 90 } else if (R->isSubClassOf("SDTCisPtrTy")) { 91 ConstraintType = SDTCisPtrTy; 92 } else if (R->isSubClassOf("SDTCisInt")) { 93 ConstraintType = SDTCisInt; 94 } else if (R->isSubClassOf("SDTCisFP")) { 95 ConstraintType = SDTCisFP; 96 } else if (R->isSubClassOf("SDTCisSameAs")) { 97 ConstraintType = SDTCisSameAs; 98 x.SDTCisSameAs_Info.OtherOperandNum = R->getValueAsInt("OtherOperandNum"); 99 } else if (R->isSubClassOf("SDTCisVTSmallerThanOp")) { 100 ConstraintType = SDTCisVTSmallerThanOp; 101 x.SDTCisVTSmallerThanOp_Info.OtherOperandNum = 102 R->getValueAsInt("OtherOperandNum"); 103 } else if (R->isSubClassOf("SDTCisOpSmallerThanOp")) { 104 ConstraintType = SDTCisOpSmallerThanOp; 105 x.SDTCisOpSmallerThanOp_Info.BigOperandNum = 106 R->getValueAsInt("BigOperandNum"); 107 } else if (R->isSubClassOf("SDTCisIntVectorOfSameSize")) { 108 ConstraintType = SDTCisIntVectorOfSameSize; 109 x.SDTCisIntVectorOfSameSize_Info.OtherOperandNum = 110 R->getValueAsInt("OtherOpNum"); 111 } else { 112 std::cerr << "Unrecognized SDTypeConstraint '" << R->getName() << "'!\n"; 113 exit(1); 114 } 115} 116 117/// getOperandNum - Return the node corresponding to operand #OpNo in tree 118/// N, which has NumResults results. 119TreePatternNode *SDTypeConstraint::getOperandNum(unsigned OpNo, 120 TreePatternNode *N, 121 unsigned NumResults) const { 122 assert(NumResults <= 1 && 123 "We only work with nodes with zero or one result so far!"); 124 125 if (OpNo >= (NumResults + N->getNumChildren())) { 126 std::cerr << "Invalid operand number " << OpNo << " "; 127 N->dump(); 128 std::cerr << '\n'; 129 exit(1); 130 } 131 132 if (OpNo < NumResults) 133 return N; // FIXME: need value # 134 else 135 return N->getChild(OpNo-NumResults); 136} 137 138/// ApplyTypeConstraint - Given a node in a pattern, apply this type 139/// constraint to the nodes operands. This returns true if it makes a 140/// change, false otherwise. If a type contradiction is found, throw an 141/// exception. 142bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, 143 const SDNodeInfo &NodeInfo, 144 TreePattern &TP) const { 145 unsigned NumResults = NodeInfo.getNumResults(); 146 assert(NumResults <= 1 && 147 "We only work with nodes with zero or one result so far!"); 148 149 // Check that the number of operands is sane. Negative operands -> varargs. 150 if (NodeInfo.getNumOperands() >= 0) { 151 if (N->getNumChildren() != (unsigned)NodeInfo.getNumOperands()) 152 TP.error(N->getOperator()->getName() + " node requires exactly " + 153 itostr(NodeInfo.getNumOperands()) + " operands!"); 154 } 155 156 const CodeGenTarget &CGT = TP.getDAGISelEmitter().getTargetInfo(); 157 158 TreePatternNode *NodeToApply = getOperandNum(OperandNo, N, NumResults); 159 160 switch (ConstraintType) { 161 default: assert(0 && "Unknown constraint type!"); 162 case SDTCisVT: 163 // Operand must be a particular type. 164 return NodeToApply->UpdateNodeType(x.SDTCisVT_Info.VT, TP); 165 case SDTCisPtrTy: { 166 // Operand must be same as target pointer type. 167 return NodeToApply->UpdateNodeType(MVT::iPTR, TP); 168 } 169 case SDTCisInt: { 170 // If there is only one integer type supported, this must be it. 171 std::vector<MVT::ValueType> IntVTs = 172 FilterVTs(CGT.getLegalValueTypes(), MVT::isInteger); 173 174 // If we found exactly one supported integer type, apply it. 175 if (IntVTs.size() == 1) 176 return NodeToApply->UpdateNodeType(IntVTs[0], TP); 177 return NodeToApply->UpdateNodeType(MVT::isInt, TP); 178 } 179 case SDTCisFP: { 180 // If there is only one FP type supported, this must be it. 181 std::vector<MVT::ValueType> FPVTs = 182 FilterVTs(CGT.getLegalValueTypes(), MVT::isFloatingPoint); 183 184 // If we found exactly one supported FP type, apply it. 185 if (FPVTs.size() == 1) 186 return NodeToApply->UpdateNodeType(FPVTs[0], TP); 187 return NodeToApply->UpdateNodeType(MVT::isFP, TP); 188 } 189 case SDTCisSameAs: { 190 TreePatternNode *OtherNode = 191 getOperandNum(x.SDTCisSameAs_Info.OtherOperandNum, N, NumResults); 192 return NodeToApply->UpdateNodeType(OtherNode->getExtTypes(), TP) | 193 OtherNode->UpdateNodeType(NodeToApply->getExtTypes(), TP); 194 } 195 case SDTCisVTSmallerThanOp: { 196 // The NodeToApply must be a leaf node that is a VT. OtherOperandNum must 197 // have an integer type that is smaller than the VT. 198 if (!NodeToApply->isLeaf() || 199 !dynamic_cast<DefInit*>(NodeToApply->getLeafValue()) || 200 !static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef() 201 ->isSubClassOf("ValueType")) 202 TP.error(N->getOperator()->getName() + " expects a VT operand!"); 203 MVT::ValueType VT = 204 getValueType(static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef()); 205 if (!MVT::isInteger(VT)) 206 TP.error(N->getOperator()->getName() + " VT operand must be integer!"); 207 208 TreePatternNode *OtherNode = 209 getOperandNum(x.SDTCisVTSmallerThanOp_Info.OtherOperandNum, N,NumResults); 210 211 // It must be integer. 212 bool MadeChange = false; 213 MadeChange |= OtherNode->UpdateNodeType(MVT::isInt, TP); 214 215 // This code only handles nodes that have one type set. Assert here so 216 // that we can change this if we ever need to deal with multiple value 217 // types at this point. 218 assert(OtherNode->getExtTypes().size() == 1 && "Node has too many types!"); 219 if (OtherNode->hasTypeSet() && OtherNode->getTypeNum(0) <= VT) 220 OtherNode->UpdateNodeType(MVT::Other, TP); // Throw an error. 221 return false; 222 } 223 case SDTCisOpSmallerThanOp: { 224 TreePatternNode *BigOperand = 225 getOperandNum(x.SDTCisOpSmallerThanOp_Info.BigOperandNum, N, NumResults); 226 227 // Both operands must be integer or FP, but we don't care which. 228 bool MadeChange = false; 229 230 // This code does not currently handle nodes which have multiple types, 231 // where some types are integer, and some are fp. Assert that this is not 232 // the case. 233 assert(!(isExtIntegerInVTs(NodeToApply->getExtTypes()) && 234 isExtFloatingPointInVTs(NodeToApply->getExtTypes())) && 235 !(isExtIntegerInVTs(BigOperand->getExtTypes()) && 236 isExtFloatingPointInVTs(BigOperand->getExtTypes())) && 237 "SDTCisOpSmallerThanOp does not handle mixed int/fp types!"); 238 if (isExtIntegerInVTs(NodeToApply->getExtTypes())) 239 MadeChange |= BigOperand->UpdateNodeType(MVT::isInt, TP); 240 else if (isExtFloatingPointInVTs(NodeToApply->getExtTypes())) 241 MadeChange |= BigOperand->UpdateNodeType(MVT::isFP, TP); 242 if (isExtIntegerInVTs(BigOperand->getExtTypes())) 243 MadeChange |= NodeToApply->UpdateNodeType(MVT::isInt, TP); 244 else if (isExtFloatingPointInVTs(BigOperand->getExtTypes())) 245 MadeChange |= NodeToApply->UpdateNodeType(MVT::isFP, TP); 246 247 std::vector<MVT::ValueType> VTs = CGT.getLegalValueTypes(); 248 249 if (isExtIntegerInVTs(NodeToApply->getExtTypes())) { 250 VTs = FilterVTs(VTs, MVT::isInteger); 251 } else if (isExtFloatingPointInVTs(NodeToApply->getExtTypes())) { 252 VTs = FilterVTs(VTs, MVT::isFloatingPoint); 253 } else { 254 VTs.clear(); 255 } 256 257 switch (VTs.size()) { 258 default: // Too many VT's to pick from. 259 case 0: break; // No info yet. 260 case 1: 261 // Only one VT of this flavor. Cannot ever satisify the constraints. 262 return NodeToApply->UpdateNodeType(MVT::Other, TP); // throw 263 case 2: 264 // If we have exactly two possible types, the little operand must be the 265 // small one, the big operand should be the big one. Common with 266 // float/double for example. 267 assert(VTs[0] < VTs[1] && "Should be sorted!"); 268 MadeChange |= NodeToApply->UpdateNodeType(VTs[0], TP); 269 MadeChange |= BigOperand->UpdateNodeType(VTs[1], TP); 270 break; 271 } 272 return MadeChange; 273 } 274 case SDTCisIntVectorOfSameSize: { 275 TreePatternNode *OtherOperand = 276 getOperandNum(x.SDTCisIntVectorOfSameSize_Info.OtherOperandNum, 277 N, NumResults); 278 if (OtherOperand->hasTypeSet()) { 279 if (!MVT::isVector(OtherOperand->getTypeNum(0))) 280 TP.error(N->getOperator()->getName() + " VT operand must be a vector!"); 281 MVT::ValueType IVT = OtherOperand->getTypeNum(0); 282 IVT = MVT::getIntVectorWithNumElements(MVT::getVectorNumElements(IVT)); 283 return NodeToApply->UpdateNodeType(IVT, TP); 284 } 285 return false; 286 } 287 } 288 return false; 289} 290 291 292//===----------------------------------------------------------------------===// 293// SDNodeInfo implementation 294// 295SDNodeInfo::SDNodeInfo(Record *R) : Def(R) { 296 EnumName = R->getValueAsString("Opcode"); 297 SDClassName = R->getValueAsString("SDClass"); 298 Record *TypeProfile = R->getValueAsDef("TypeProfile"); 299 NumResults = TypeProfile->getValueAsInt("NumResults"); 300 NumOperands = TypeProfile->getValueAsInt("NumOperands"); 301 302 // Parse the properties. 303 Properties = 0; 304 std::vector<Record*> PropList = R->getValueAsListOfDefs("Properties"); 305 for (unsigned i = 0, e = PropList.size(); i != e; ++i) { 306 if (PropList[i]->getName() == "SDNPCommutative") { 307 Properties |= 1 << SDNPCommutative; 308 } else if (PropList[i]->getName() == "SDNPAssociative") { 309 Properties |= 1 << SDNPAssociative; 310 } else if (PropList[i]->getName() == "SDNPHasChain") { 311 Properties |= 1 << SDNPHasChain; 312 } else if (PropList[i]->getName() == "SDNPOutFlag") { 313 Properties |= 1 << SDNPOutFlag; 314 } else if (PropList[i]->getName() == "SDNPInFlag") { 315 Properties |= 1 << SDNPInFlag; 316 } else if (PropList[i]->getName() == "SDNPOptInFlag") { 317 Properties |= 1 << SDNPOptInFlag; 318 } else { 319 std::cerr << "Unknown SD Node property '" << PropList[i]->getName() 320 << "' on node '" << R->getName() << "'!\n"; 321 exit(1); 322 } 323 } 324 325 326 // Parse the type constraints. 327 std::vector<Record*> ConstraintList = 328 TypeProfile->getValueAsListOfDefs("Constraints"); 329 TypeConstraints.assign(ConstraintList.begin(), ConstraintList.end()); 330} 331 332//===----------------------------------------------------------------------===// 333// TreePatternNode implementation 334// 335 336TreePatternNode::~TreePatternNode() { 337#if 0 // FIXME: implement refcounted tree nodes! 338 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 339 delete getChild(i); 340#endif 341} 342 343/// UpdateNodeType - Set the node type of N to VT if VT contains 344/// information. If N already contains a conflicting type, then throw an 345/// exception. This returns true if any information was updated. 346/// 347bool TreePatternNode::UpdateNodeType(const std::vector<unsigned char> &ExtVTs, 348 TreePattern &TP) { 349 assert(!ExtVTs.empty() && "Cannot update node type with empty type vector!"); 350 351 if (ExtVTs[0] == MVT::isUnknown || LHSIsSubsetOfRHS(getExtTypes(), ExtVTs)) 352 return false; 353 if (isTypeCompletelyUnknown() || LHSIsSubsetOfRHS(ExtVTs, getExtTypes())) { 354 setTypes(ExtVTs); 355 return true; 356 } 357 358 if (getExtTypeNum(0) == MVT::iPTR) { 359 if (ExtVTs[0] == MVT::iPTR || ExtVTs[0] == MVT::isInt) 360 return false; 361 if (isExtIntegerInVTs(ExtVTs)) { 362 std::vector<unsigned char> FVTs = FilterEVTs(ExtVTs, MVT::isInteger); 363 if (FVTs.size()) { 364 setTypes(ExtVTs); 365 return true; 366 } 367 } 368 } 369 370 if (ExtVTs[0] == MVT::isInt && isExtIntegerInVTs(getExtTypes())) { 371 assert(hasTypeSet() && "should be handled above!"); 372 std::vector<unsigned char> FVTs = FilterEVTs(getExtTypes(), MVT::isInteger); 373 if (getExtTypes() == FVTs) 374 return false; 375 setTypes(FVTs); 376 return true; 377 } 378 if (ExtVTs[0] == MVT::iPTR && isExtIntegerInVTs(getExtTypes())) { 379 //assert(hasTypeSet() && "should be handled above!"); 380 std::vector<unsigned char> FVTs = FilterEVTs(getExtTypes(), MVT::isInteger); 381 if (getExtTypes() == FVTs) 382 return false; 383 if (FVTs.size()) { 384 setTypes(FVTs); 385 return true; 386 } 387 } 388 if (ExtVTs[0] == MVT::isFP && isExtFloatingPointInVTs(getExtTypes())) { 389 assert(hasTypeSet() && "should be handled above!"); 390 std::vector<unsigned char> FVTs = 391 FilterEVTs(getExtTypes(), MVT::isFloatingPoint); 392 if (getExtTypes() == FVTs) 393 return false; 394 setTypes(FVTs); 395 return true; 396 } 397 398 // If we know this is an int or fp type, and we are told it is a specific one, 399 // take the advice. 400 // 401 // Similarly, we should probably set the type here to the intersection of 402 // {isInt|isFP} and ExtVTs 403 if ((getExtTypeNum(0) == MVT::isInt && isExtIntegerInVTs(ExtVTs)) || 404 (getExtTypeNum(0) == MVT::isFP && isExtFloatingPointInVTs(ExtVTs))) { 405 setTypes(ExtVTs); 406 return true; 407 } 408 if (getExtTypeNum(0) == MVT::isInt && ExtVTs[0] == MVT::iPTR) { 409 setTypes(ExtVTs); 410 return true; 411 } 412 413 if (isLeaf()) { 414 dump(); 415 std::cerr << " "; 416 TP.error("Type inference contradiction found in node!"); 417 } else { 418 TP.error("Type inference contradiction found in node " + 419 getOperator()->getName() + "!"); 420 } 421 return true; // unreachable 422} 423 424 425void TreePatternNode::print(std::ostream &OS) const { 426 if (isLeaf()) { 427 OS << *getLeafValue(); 428 } else { 429 OS << "(" << getOperator()->getName(); 430 } 431 432 // FIXME: At some point we should handle printing all the value types for 433 // nodes that are multiply typed. 434 switch (getExtTypeNum(0)) { 435 case MVT::Other: OS << ":Other"; break; 436 case MVT::isInt: OS << ":isInt"; break; 437 case MVT::isFP : OS << ":isFP"; break; 438 case MVT::isUnknown: ; /*OS << ":?";*/ break; 439 case MVT::iPTR: OS << ":iPTR"; break; 440 default: { 441 std::string VTName = llvm::getName(getTypeNum(0)); 442 // Strip off MVT:: prefix if present. 443 if (VTName.substr(0,5) == "MVT::") 444 VTName = VTName.substr(5); 445 OS << ":" << VTName; 446 break; 447 } 448 } 449 450 if (!isLeaf()) { 451 if (getNumChildren() != 0) { 452 OS << " "; 453 getChild(0)->print(OS); 454 for (unsigned i = 1, e = getNumChildren(); i != e; ++i) { 455 OS << ", "; 456 getChild(i)->print(OS); 457 } 458 } 459 OS << ")"; 460 } 461 462 if (!PredicateFn.empty()) 463 OS << "<<P:" << PredicateFn << ">>"; 464 if (TransformFn) 465 OS << "<<X:" << TransformFn->getName() << ">>"; 466 if (!getName().empty()) 467 OS << ":$" << getName(); 468 469} 470void TreePatternNode::dump() const { 471 print(std::cerr); 472} 473 474/// isIsomorphicTo - Return true if this node is recursively isomorphic to 475/// the specified node. For this comparison, all of the state of the node 476/// is considered, except for the assigned name. Nodes with differing names 477/// that are otherwise identical are considered isomorphic. 478bool TreePatternNode::isIsomorphicTo(const TreePatternNode *N) const { 479 if (N == this) return true; 480 if (N->isLeaf() != isLeaf() || getExtTypes() != N->getExtTypes() || 481 getPredicateFn() != N->getPredicateFn() || 482 getTransformFn() != N->getTransformFn()) 483 return false; 484 485 if (isLeaf()) { 486 if (DefInit *DI = dynamic_cast<DefInit*>(getLeafValue())) 487 if (DefInit *NDI = dynamic_cast<DefInit*>(N->getLeafValue())) 488 return DI->getDef() == NDI->getDef(); 489 return getLeafValue() == N->getLeafValue(); 490 } 491 492 if (N->getOperator() != getOperator() || 493 N->getNumChildren() != getNumChildren()) return false; 494 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 495 if (!getChild(i)->isIsomorphicTo(N->getChild(i))) 496 return false; 497 return true; 498} 499 500/// clone - Make a copy of this tree and all of its children. 501/// 502TreePatternNode *TreePatternNode::clone() const { 503 TreePatternNode *New; 504 if (isLeaf()) { 505 New = new TreePatternNode(getLeafValue()); 506 } else { 507 std::vector<TreePatternNode*> CChildren; 508 CChildren.reserve(Children.size()); 509 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 510 CChildren.push_back(getChild(i)->clone()); 511 New = new TreePatternNode(getOperator(), CChildren); 512 } 513 New->setName(getName()); 514 New->setTypes(getExtTypes()); 515 New->setPredicateFn(getPredicateFn()); 516 New->setTransformFn(getTransformFn()); 517 return New; 518} 519 520/// SubstituteFormalArguments - Replace the formal arguments in this tree 521/// with actual values specified by ArgMap. 522void TreePatternNode:: 523SubstituteFormalArguments(std::map<std::string, TreePatternNode*> &ArgMap) { 524 if (isLeaf()) return; 525 526 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { 527 TreePatternNode *Child = getChild(i); 528 if (Child->isLeaf()) { 529 Init *Val = Child->getLeafValue(); 530 if (dynamic_cast<DefInit*>(Val) && 531 static_cast<DefInit*>(Val)->getDef()->getName() == "node") { 532 // We found a use of a formal argument, replace it with its value. 533 Child = ArgMap[Child->getName()]; 534 assert(Child && "Couldn't find formal argument!"); 535 setChild(i, Child); 536 } 537 } else { 538 getChild(i)->SubstituteFormalArguments(ArgMap); 539 } 540 } 541} 542 543 544/// InlinePatternFragments - If this pattern refers to any pattern 545/// fragments, inline them into place, giving us a pattern without any 546/// PatFrag references. 547TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) { 548 if (isLeaf()) return this; // nothing to do. 549 Record *Op = getOperator(); 550 551 if (!Op->isSubClassOf("PatFrag")) { 552 // Just recursively inline children nodes. 553 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 554 setChild(i, getChild(i)->InlinePatternFragments(TP)); 555 return this; 556 } 557 558 // Otherwise, we found a reference to a fragment. First, look up its 559 // TreePattern record. 560 TreePattern *Frag = TP.getDAGISelEmitter().getPatternFragment(Op); 561 562 // Verify that we are passing the right number of operands. 563 if (Frag->getNumArgs() != Children.size()) 564 TP.error("'" + Op->getName() + "' fragment requires " + 565 utostr(Frag->getNumArgs()) + " operands!"); 566 567 TreePatternNode *FragTree = Frag->getOnlyTree()->clone(); 568 569 // Resolve formal arguments to their actual value. 570 if (Frag->getNumArgs()) { 571 // Compute the map of formal to actual arguments. 572 std::map<std::string, TreePatternNode*> ArgMap; 573 for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i) 574 ArgMap[Frag->getArgName(i)] = getChild(i)->InlinePatternFragments(TP); 575 576 FragTree->SubstituteFormalArguments(ArgMap); 577 } 578 579 FragTree->setName(getName()); 580 FragTree->UpdateNodeType(getExtTypes(), TP); 581 582 // Get a new copy of this fragment to stitch into here. 583 //delete this; // FIXME: implement refcounting! 584 return FragTree; 585} 586 587/// getImplicitType - Check to see if the specified record has an implicit 588/// type which should be applied to it. This infer the type of register 589/// references from the register file information, for example. 590/// 591static std::vector<unsigned char> getImplicitType(Record *R, bool NotRegisters, 592 TreePattern &TP) { 593 // Some common return values 594 std::vector<unsigned char> Unknown(1, MVT::isUnknown); 595 std::vector<unsigned char> Other(1, MVT::Other); 596 597 // Check to see if this is a register or a register class... 598 if (R->isSubClassOf("RegisterClass")) { 599 if (NotRegisters) 600 return Unknown; 601 const CodeGenRegisterClass &RC = 602 TP.getDAGISelEmitter().getTargetInfo().getRegisterClass(R); 603 return ConvertVTs(RC.getValueTypes()); 604 } else if (R->isSubClassOf("PatFrag")) { 605 // Pattern fragment types will be resolved when they are inlined. 606 return Unknown; 607 } else if (R->isSubClassOf("Register")) { 608 if (NotRegisters) 609 return Unknown; 610 const CodeGenTarget &T = TP.getDAGISelEmitter().getTargetInfo(); 611 return T.getRegisterVTs(R); 612 } else if (R->isSubClassOf("ValueType") || R->isSubClassOf("CondCode")) { 613 // Using a VTSDNode or CondCodeSDNode. 614 return Other; 615 } else if (R->isSubClassOf("ComplexPattern")) { 616 if (NotRegisters) 617 return Unknown; 618 std::vector<unsigned char> 619 ComplexPat(1, TP.getDAGISelEmitter().getComplexPattern(R).getValueType()); 620 return ComplexPat; 621 } else if (R->getName() == "node" || R->getName() == "srcvalue") { 622 // Placeholder. 623 return Unknown; 624 } 625 626 TP.error("Unknown node flavor used in pattern: " + R->getName()); 627 return Other; 628} 629 630/// ApplyTypeConstraints - Apply all of the type constraints relevent to 631/// this node and its children in the tree. This returns true if it makes a 632/// change, false otherwise. If a type contradiction is found, throw an 633/// exception. 634bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { 635 DAGISelEmitter &ISE = TP.getDAGISelEmitter(); 636 if (isLeaf()) { 637 if (DefInit *DI = dynamic_cast<DefInit*>(getLeafValue())) { 638 // If it's a regclass or something else known, include the type. 639 return UpdateNodeType(getImplicitType(DI->getDef(), NotRegisters, TP),TP); 640 } else if (IntInit *II = dynamic_cast<IntInit*>(getLeafValue())) { 641 // Int inits are always integers. :) 642 bool MadeChange = UpdateNodeType(MVT::isInt, TP); 643 644 if (hasTypeSet()) { 645 // At some point, it may make sense for this tree pattern to have 646 // multiple types. Assert here that it does not, so we revisit this 647 // code when appropriate. 648 assert(getExtTypes().size() >= 1 && "TreePattern doesn't have a type!"); 649 MVT::ValueType VT = getTypeNum(0); 650 for (unsigned i = 1, e = getExtTypes().size(); i != e; ++i) 651 assert(getTypeNum(i) == VT && "TreePattern has too many types!"); 652 653 VT = getTypeNum(0); 654 if (VT != MVT::iPTR) { 655 unsigned Size = MVT::getSizeInBits(VT); 656 // Make sure that the value is representable for this type. 657 if (Size < 32) { 658 int Val = (II->getValue() << (32-Size)) >> (32-Size); 659 if (Val != II->getValue()) 660 TP.error("Sign-extended integer value '" + itostr(II->getValue())+ 661 "' is out of range for type '" + 662 getEnumName(getTypeNum(0)) + "'!"); 663 } 664 } 665 } 666 667 return MadeChange; 668 } 669 return false; 670 } 671 672 // special handling for set, which isn't really an SDNode. 673 if (getOperator()->getName() == "set") { 674 assert (getNumChildren() == 2 && "Only handle 2 operand set's for now!"); 675 bool MadeChange = getChild(0)->ApplyTypeConstraints(TP, NotRegisters); 676 MadeChange |= getChild(1)->ApplyTypeConstraints(TP, NotRegisters); 677 678 // Types of operands must match. 679 MadeChange |= getChild(0)->UpdateNodeType(getChild(1)->getExtTypes(), TP); 680 MadeChange |= getChild(1)->UpdateNodeType(getChild(0)->getExtTypes(), TP); 681 MadeChange |= UpdateNodeType(MVT::isVoid, TP); 682 return MadeChange; 683 } else if (getOperator() == ISE.get_intrinsic_void_sdnode() || 684 getOperator() == ISE.get_intrinsic_w_chain_sdnode() || 685 getOperator() == ISE.get_intrinsic_wo_chain_sdnode()) { 686 unsigned IID = 687 dynamic_cast<IntInit*>(getChild(0)->getLeafValue())->getValue(); 688 const CodeGenIntrinsic &Int = ISE.getIntrinsicInfo(IID); 689 bool MadeChange = false; 690 691 // Apply the result type to the node. 692 MadeChange = UpdateNodeType(Int.ArgVTs[0], TP); 693 694 if (getNumChildren() != Int.ArgVTs.size()) 695 TP.error("Intrinsic '" + Int.Name + "' expects " + 696 utostr(Int.ArgVTs.size()-1) + " operands, not " + 697 utostr(getNumChildren()-1) + " operands!"); 698 699 // Apply type info to the intrinsic ID. 700 MadeChange |= getChild(0)->UpdateNodeType(MVT::iPTR, TP); 701 702 for (unsigned i = 1, e = getNumChildren(); i != e; ++i) { 703 MVT::ValueType OpVT = Int.ArgVTs[i]; 704 MadeChange |= getChild(i)->UpdateNodeType(OpVT, TP); 705 MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 706 } 707 return MadeChange; 708 } else if (getOperator()->isSubClassOf("SDNode")) { 709 const SDNodeInfo &NI = ISE.getSDNodeInfo(getOperator()); 710 711 bool MadeChange = NI.ApplyTypeConstraints(this, TP); 712 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 713 MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 714 // Branch, etc. do not produce results and top-level forms in instr pattern 715 // must have void types. 716 if (NI.getNumResults() == 0) 717 MadeChange |= UpdateNodeType(MVT::isVoid, TP); 718 719 // If this is a vector_shuffle operation, apply types to the build_vector 720 // operation. The types of the integers don't matter, but this ensures they 721 // won't get checked. 722 if (getOperator()->getName() == "vector_shuffle" && 723 getChild(2)->getOperator()->getName() == "build_vector") { 724 TreePatternNode *BV = getChild(2); 725 const std::vector<MVT::ValueType> &LegalVTs 726 = ISE.getTargetInfo().getLegalValueTypes(); 727 MVT::ValueType LegalIntVT = MVT::Other; 728 for (unsigned i = 0, e = LegalVTs.size(); i != e; ++i) 729 if (MVT::isInteger(LegalVTs[i]) && !MVT::isVector(LegalVTs[i])) { 730 LegalIntVT = LegalVTs[i]; 731 break; 732 } 733 assert(LegalIntVT != MVT::Other && "No legal integer VT?"); 734 735 for (unsigned i = 0, e = BV->getNumChildren(); i != e; ++i) 736 MadeChange |= BV->getChild(i)->UpdateNodeType(LegalIntVT, TP); 737 } 738 return MadeChange; 739 } else if (getOperator()->isSubClassOf("Instruction")) { 740 const DAGInstruction &Inst = ISE.getInstruction(getOperator()); 741 bool MadeChange = false; 742 unsigned NumResults = Inst.getNumResults(); 743 744 assert(NumResults <= 1 && 745 "Only supports zero or one result instrs!"); 746 747 CodeGenInstruction &InstInfo = 748 ISE.getTargetInfo().getInstruction(getOperator()->getName()); 749 // Apply the result type to the node 750 if (NumResults == 0 || InstInfo.noResults) { // FIXME: temporary hack... 751 MadeChange = UpdateNodeType(MVT::isVoid, TP); 752 } else { 753 Record *ResultNode = Inst.getResult(0); 754 assert(ResultNode->isSubClassOf("RegisterClass") && 755 "Operands should be register classes!"); 756 757 const CodeGenRegisterClass &RC = 758 ISE.getTargetInfo().getRegisterClass(ResultNode); 759 MadeChange = UpdateNodeType(ConvertVTs(RC.getValueTypes()), TP); 760 } 761 762 if (getNumChildren() != Inst.getNumOperands()) 763 TP.error("Instruction '" + getOperator()->getName() + " expects " + 764 utostr(Inst.getNumOperands()) + " operands, not " + 765 utostr(getNumChildren()) + " operands!"); 766 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { 767 Record *OperandNode = Inst.getOperand(i); 768 MVT::ValueType VT; 769 if (OperandNode->isSubClassOf("RegisterClass")) { 770 const CodeGenRegisterClass &RC = 771 ISE.getTargetInfo().getRegisterClass(OperandNode); 772 MadeChange |=getChild(i)->UpdateNodeType(ConvertVTs(RC.getValueTypes()), 773 TP); 774 } else if (OperandNode->isSubClassOf("Operand")) { 775 VT = getValueType(OperandNode->getValueAsDef("Type")); 776 MadeChange |= getChild(i)->UpdateNodeType(VT, TP); 777 } else { 778 assert(0 && "Unknown operand type!"); 779 abort(); 780 } 781 MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 782 } 783 return MadeChange; 784 } else { 785 assert(getOperator()->isSubClassOf("SDNodeXForm") && "Unknown node type!"); 786 787 // Node transforms always take one operand. 788 if (getNumChildren() != 1) 789 TP.error("Node transform '" + getOperator()->getName() + 790 "' requires one operand!"); 791 792 // If either the output or input of the xform does not have exact 793 // type info. We assume they must be the same. Otherwise, it is perfectly 794 // legal to transform from one type to a completely different type. 795 if (!hasTypeSet() || !getChild(0)->hasTypeSet()) { 796 bool MadeChange = UpdateNodeType(getChild(0)->getExtTypes(), TP); 797 MadeChange |= getChild(0)->UpdateNodeType(getExtTypes(), TP); 798 return MadeChange; 799 } 800 return false; 801 } 802} 803 804/// OnlyOnRHSOfCommutative - Return true if this value is only allowed on the 805/// RHS of a commutative operation, not the on LHS. 806static bool OnlyOnRHSOfCommutative(TreePatternNode *N) { 807 if (!N->isLeaf() && N->getOperator()->getName() == "imm") 808 return true; 809 if (N->isLeaf() && dynamic_cast<IntInit*>(N->getLeafValue())) 810 return true; 811 return false; 812} 813 814 815/// canPatternMatch - If it is impossible for this pattern to match on this 816/// target, fill in Reason and return false. Otherwise, return true. This is 817/// used as a santity check for .td files (to prevent people from writing stuff 818/// that can never possibly work), and to prevent the pattern permuter from 819/// generating stuff that is useless. 820bool TreePatternNode::canPatternMatch(std::string &Reason, DAGISelEmitter &ISE){ 821 if (isLeaf()) return true; 822 823 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 824 if (!getChild(i)->canPatternMatch(Reason, ISE)) 825 return false; 826 827 // If this is an intrinsic, handle cases that would make it not match. For 828 // example, if an operand is required to be an immediate. 829 if (getOperator()->isSubClassOf("Intrinsic")) { 830 // TODO: 831 return true; 832 } 833 834 // If this node is a commutative operator, check that the LHS isn't an 835 // immediate. 836 const SDNodeInfo &NodeInfo = ISE.getSDNodeInfo(getOperator()); 837 if (NodeInfo.hasProperty(SDNPCommutative)) { 838 // Scan all of the operands of the node and make sure that only the last one 839 // is a constant node, unless the RHS also is. 840 if (!OnlyOnRHSOfCommutative(getChild(getNumChildren()-1))) { 841 for (unsigned i = 0, e = getNumChildren()-1; i != e; ++i) 842 if (OnlyOnRHSOfCommutative(getChild(i))) { 843 Reason="Immediate value must be on the RHS of commutative operators!"; 844 return false; 845 } 846 } 847 } 848 849 return true; 850} 851 852//===----------------------------------------------------------------------===// 853// TreePattern implementation 854// 855 856TreePattern::TreePattern(Record *TheRec, ListInit *RawPat, bool isInput, 857 DAGISelEmitter &ise) : TheRecord(TheRec), ISE(ise) { 858 isInputPattern = isInput; 859 for (unsigned i = 0, e = RawPat->getSize(); i != e; ++i) 860 Trees.push_back(ParseTreePattern((DagInit*)RawPat->getElement(i))); 861} 862 863TreePattern::TreePattern(Record *TheRec, DagInit *Pat, bool isInput, 864 DAGISelEmitter &ise) : TheRecord(TheRec), ISE(ise) { 865 isInputPattern = isInput; 866 Trees.push_back(ParseTreePattern(Pat)); 867} 868 869TreePattern::TreePattern(Record *TheRec, TreePatternNode *Pat, bool isInput, 870 DAGISelEmitter &ise) : TheRecord(TheRec), ISE(ise) { 871 isInputPattern = isInput; 872 Trees.push_back(Pat); 873} 874 875 876 877void TreePattern::error(const std::string &Msg) const { 878 dump(); 879 throw "In " + TheRecord->getName() + ": " + Msg; 880} 881 882TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) { 883 DefInit *OpDef = dynamic_cast<DefInit*>(Dag->getOperator()); 884 if (!OpDef) error("Pattern has unexpected operator type!"); 885 Record *Operator = OpDef->getDef(); 886 887 if (Operator->isSubClassOf("ValueType")) { 888 // If the operator is a ValueType, then this must be "type cast" of a leaf 889 // node. 890 if (Dag->getNumArgs() != 1) 891 error("Type cast only takes one operand!"); 892 893 Init *Arg = Dag->getArg(0); 894 TreePatternNode *New; 895 if (DefInit *DI = dynamic_cast<DefInit*>(Arg)) { 896 Record *R = DI->getDef(); 897 if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag")) { 898 Dag->setArg(0, new DagInit(DI, 899 std::vector<std::pair<Init*, std::string> >())); 900 return ParseTreePattern(Dag); 901 } 902 New = new TreePatternNode(DI); 903 } else if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) { 904 New = ParseTreePattern(DI); 905 } else if (IntInit *II = dynamic_cast<IntInit*>(Arg)) { 906 New = new TreePatternNode(II); 907 if (!Dag->getArgName(0).empty()) 908 error("Constant int argument should not have a name!"); 909 } else if (BitsInit *BI = dynamic_cast<BitsInit*>(Arg)) { 910 // Turn this into an IntInit. 911 Init *II = BI->convertInitializerTo(new IntRecTy()); 912 if (II == 0 || !dynamic_cast<IntInit*>(II)) 913 error("Bits value must be constants!"); 914 915 New = new TreePatternNode(dynamic_cast<IntInit*>(II)); 916 if (!Dag->getArgName(0).empty()) 917 error("Constant int argument should not have a name!"); 918 } else { 919 Arg->dump(); 920 error("Unknown leaf value for tree pattern!"); 921 return 0; 922 } 923 924 // Apply the type cast. 925 New->UpdateNodeType(getValueType(Operator), *this); 926 New->setName(Dag->getArgName(0)); 927 return New; 928 } 929 930 // Verify that this is something that makes sense for an operator. 931 if (!Operator->isSubClassOf("PatFrag") && !Operator->isSubClassOf("SDNode") && 932 !Operator->isSubClassOf("Instruction") && 933 !Operator->isSubClassOf("SDNodeXForm") && 934 !Operator->isSubClassOf("Intrinsic") && 935 Operator->getName() != "set") 936 error("Unrecognized node '" + Operator->getName() + "'!"); 937 938 // Check to see if this is something that is illegal in an input pattern. 939 if (isInputPattern && (Operator->isSubClassOf("Instruction") || 940 Operator->isSubClassOf("SDNodeXForm"))) 941 error("Cannot use '" + Operator->getName() + "' in an input pattern!"); 942 943 std::vector<TreePatternNode*> Children; 944 945 for (unsigned i = 0, e = Dag->getNumArgs(); i != e; ++i) { 946 Init *Arg = Dag->getArg(i); 947 if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) { 948 Children.push_back(ParseTreePattern(DI)); 949 if (Children.back()->getName().empty()) 950 Children.back()->setName(Dag->getArgName(i)); 951 } else if (DefInit *DefI = dynamic_cast<DefInit*>(Arg)) { 952 Record *R = DefI->getDef(); 953 // Direct reference to a leaf DagNode or PatFrag? Turn it into a 954 // TreePatternNode if its own. 955 if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag")) { 956 Dag->setArg(i, new DagInit(DefI, 957 std::vector<std::pair<Init*, std::string> >())); 958 --i; // Revisit this node... 959 } else { 960 TreePatternNode *Node = new TreePatternNode(DefI); 961 Node->setName(Dag->getArgName(i)); 962 Children.push_back(Node); 963 964 // Input argument? 965 if (R->getName() == "node") { 966 if (Dag->getArgName(i).empty()) 967 error("'node' argument requires a name to match with operand list"); 968 Args.push_back(Dag->getArgName(i)); 969 } 970 } 971 } else if (IntInit *II = dynamic_cast<IntInit*>(Arg)) { 972 TreePatternNode *Node = new TreePatternNode(II); 973 if (!Dag->getArgName(i).empty()) 974 error("Constant int argument should not have a name!"); 975 Children.push_back(Node); 976 } else if (BitsInit *BI = dynamic_cast<BitsInit*>(Arg)) { 977 // Turn this into an IntInit. 978 Init *II = BI->convertInitializerTo(new IntRecTy()); 979 if (II == 0 || !dynamic_cast<IntInit*>(II)) 980 error("Bits value must be constants!"); 981 982 TreePatternNode *Node = new TreePatternNode(dynamic_cast<IntInit*>(II)); 983 if (!Dag->getArgName(i).empty()) 984 error("Constant int argument should not have a name!"); 985 Children.push_back(Node); 986 } else { 987 std::cerr << '"'; 988 Arg->dump(); 989 std::cerr << "\": "; 990 error("Unknown leaf value for tree pattern!"); 991 } 992 } 993 994 // If the operator is an intrinsic, then this is just syntactic sugar for for 995 // (intrinsic_* <number>, ..children..). Pick the right intrinsic node, and 996 // convert the intrinsic name to a number. 997 if (Operator->isSubClassOf("Intrinsic")) { 998 const CodeGenIntrinsic &Int = getDAGISelEmitter().getIntrinsic(Operator); 999 unsigned IID = getDAGISelEmitter().getIntrinsicID(Operator)+1; 1000 1001 // If this intrinsic returns void, it must have side-effects and thus a 1002 // chain. 1003 if (Int.ArgVTs[0] == MVT::isVoid) { 1004 Operator = getDAGISelEmitter().get_intrinsic_void_sdnode(); 1005 } else if (Int.ModRef != CodeGenIntrinsic::NoMem) { 1006 // Has side-effects, requires chain. 1007 Operator = getDAGISelEmitter().get_intrinsic_w_chain_sdnode(); 1008 } else { 1009 // Otherwise, no chain. 1010 Operator = getDAGISelEmitter().get_intrinsic_wo_chain_sdnode(); 1011 } 1012 1013 TreePatternNode *IIDNode = new TreePatternNode(new IntInit(IID)); 1014 Children.insert(Children.begin(), IIDNode); 1015 } 1016 1017 return new TreePatternNode(Operator, Children); 1018} 1019 1020/// InferAllTypes - Infer/propagate as many types throughout the expression 1021/// patterns as possible. Return true if all types are infered, false 1022/// otherwise. Throw an exception if a type contradiction is found. 1023bool TreePattern::InferAllTypes() { 1024 bool MadeChange = true; 1025 while (MadeChange) { 1026 MadeChange = false; 1027 for (unsigned i = 0, e = Trees.size(); i != e; ++i) 1028 MadeChange |= Trees[i]->ApplyTypeConstraints(*this, false); 1029 } 1030 1031 bool HasUnresolvedTypes = false; 1032 for (unsigned i = 0, e = Trees.size(); i != e; ++i) 1033 HasUnresolvedTypes |= Trees[i]->ContainsUnresolvedType(); 1034 return !HasUnresolvedTypes; 1035} 1036 1037void TreePattern::print(std::ostream &OS) const { 1038 OS << getRecord()->getName(); 1039 if (!Args.empty()) { 1040 OS << "(" << Args[0]; 1041 for (unsigned i = 1, e = Args.size(); i != e; ++i) 1042 OS << ", " << Args[i]; 1043 OS << ")"; 1044 } 1045 OS << ": "; 1046 1047 if (Trees.size() > 1) 1048 OS << "[\n"; 1049 for (unsigned i = 0, e = Trees.size(); i != e; ++i) { 1050 OS << "\t"; 1051 Trees[i]->print(OS); 1052 OS << "\n"; 1053 } 1054 1055 if (Trees.size() > 1) 1056 OS << "]\n"; 1057} 1058 1059void TreePattern::dump() const { print(std::cerr); } 1060 1061 1062 1063//===----------------------------------------------------------------------===// 1064// DAGISelEmitter implementation 1065// 1066 1067// Parse all of the SDNode definitions for the target, populating SDNodes. 1068void DAGISelEmitter::ParseNodeInfo() { 1069 std::vector<Record*> Nodes = Records.getAllDerivedDefinitions("SDNode"); 1070 while (!Nodes.empty()) { 1071 SDNodes.insert(std::make_pair(Nodes.back(), Nodes.back())); 1072 Nodes.pop_back(); 1073 } 1074 1075 // Get the buildin intrinsic nodes. 1076 intrinsic_void_sdnode = getSDNodeNamed("intrinsic_void"); 1077 intrinsic_w_chain_sdnode = getSDNodeNamed("intrinsic_w_chain"); 1078 intrinsic_wo_chain_sdnode = getSDNodeNamed("intrinsic_wo_chain"); 1079} 1080 1081/// ParseNodeTransforms - Parse all SDNodeXForm instances into the SDNodeXForms 1082/// map, and emit them to the file as functions. 1083void DAGISelEmitter::ParseNodeTransforms(std::ostream &OS) { 1084 OS << "\n// Node transformations.\n"; 1085 std::vector<Record*> Xforms = Records.getAllDerivedDefinitions("SDNodeXForm"); 1086 while (!Xforms.empty()) { 1087 Record *XFormNode = Xforms.back(); 1088 Record *SDNode = XFormNode->getValueAsDef("Opcode"); 1089 std::string Code = XFormNode->getValueAsCode("XFormFunction"); 1090 SDNodeXForms.insert(std::make_pair(XFormNode, 1091 std::make_pair(SDNode, Code))); 1092 1093 if (!Code.empty()) { 1094 std::string ClassName = getSDNodeInfo(SDNode).getSDClassName(); 1095 const char *C2 = ClassName == "SDNode" ? "N" : "inN"; 1096 1097 OS << "inline SDOperand Transform_" << XFormNode->getName() 1098 << "(SDNode *" << C2 << ") {\n"; 1099 if (ClassName != "SDNode") 1100 OS << " " << ClassName << " *N = cast<" << ClassName << ">(inN);\n"; 1101 OS << Code << "\n}\n"; 1102 } 1103 1104 Xforms.pop_back(); 1105 } 1106} 1107 1108void DAGISelEmitter::ParseComplexPatterns() { 1109 std::vector<Record*> AMs = Records.getAllDerivedDefinitions("ComplexPattern"); 1110 while (!AMs.empty()) { 1111 ComplexPatterns.insert(std::make_pair(AMs.back(), AMs.back())); 1112 AMs.pop_back(); 1113 } 1114} 1115 1116 1117/// ParsePatternFragments - Parse all of the PatFrag definitions in the .td 1118/// file, building up the PatternFragments map. After we've collected them all, 1119/// inline fragments together as necessary, so that there are no references left 1120/// inside a pattern fragment to a pattern fragment. 1121/// 1122/// This also emits all of the predicate functions to the output file. 1123/// 1124void DAGISelEmitter::ParsePatternFragments(std::ostream &OS) { 1125 std::vector<Record*> Fragments = Records.getAllDerivedDefinitions("PatFrag"); 1126 1127 // First step, parse all of the fragments and emit predicate functions. 1128 OS << "\n// Predicate functions.\n"; 1129 for (unsigned i = 0, e = Fragments.size(); i != e; ++i) { 1130 DagInit *Tree = Fragments[i]->getValueAsDag("Fragment"); 1131 TreePattern *P = new TreePattern(Fragments[i], Tree, true, *this); 1132 PatternFragments[Fragments[i]] = P; 1133 1134 // Validate the argument list, converting it to map, to discard duplicates. 1135 std::vector<std::string> &Args = P->getArgList(); 1136 std::set<std::string> OperandsMap(Args.begin(), Args.end()); 1137 1138 if (OperandsMap.count("")) 1139 P->error("Cannot have unnamed 'node' values in pattern fragment!"); 1140 1141 // Parse the operands list. 1142 DagInit *OpsList = Fragments[i]->getValueAsDag("Operands"); 1143 DefInit *OpsOp = dynamic_cast<DefInit*>(OpsList->getOperator()); 1144 if (!OpsOp || OpsOp->getDef()->getName() != "ops") 1145 P->error("Operands list should start with '(ops ... '!"); 1146 1147 // Copy over the arguments. 1148 Args.clear(); 1149 for (unsigned j = 0, e = OpsList->getNumArgs(); j != e; ++j) { 1150 if (!dynamic_cast<DefInit*>(OpsList->getArg(j)) || 1151 static_cast<DefInit*>(OpsList->getArg(j))-> 1152 getDef()->getName() != "node") 1153 P->error("Operands list should all be 'node' values."); 1154 if (OpsList->getArgName(j).empty()) 1155 P->error("Operands list should have names for each operand!"); 1156 if (!OperandsMap.count(OpsList->getArgName(j))) 1157 P->error("'" + OpsList->getArgName(j) + 1158 "' does not occur in pattern or was multiply specified!"); 1159 OperandsMap.erase(OpsList->getArgName(j)); 1160 Args.push_back(OpsList->getArgName(j)); 1161 } 1162 1163 if (!OperandsMap.empty()) 1164 P->error("Operands list does not contain an entry for operand '" + 1165 *OperandsMap.begin() + "'!"); 1166 1167 // If there is a code init for this fragment, emit the predicate code and 1168 // keep track of the fact that this fragment uses it. 1169 std::string Code = Fragments[i]->getValueAsCode("Predicate"); 1170 if (!Code.empty()) { 1171 if (P->getOnlyTree()->isLeaf()) 1172 OS << "inline bool Predicate_" << Fragments[i]->getName() 1173 << "(SDNode *N) {\n"; 1174 else { 1175 std::string ClassName = 1176 getSDNodeInfo(P->getOnlyTree()->getOperator()).getSDClassName(); 1177 const char *C2 = ClassName == "SDNode" ? "N" : "inN"; 1178 1179 OS << "inline bool Predicate_" << Fragments[i]->getName() 1180 << "(SDNode *" << C2 << ") {\n"; 1181 if (ClassName != "SDNode") 1182 OS << " " << ClassName << " *N = cast<" << ClassName << ">(inN);\n"; 1183 } 1184 OS << Code << "\n}\n"; 1185 P->getOnlyTree()->setPredicateFn("Predicate_"+Fragments[i]->getName()); 1186 } 1187 1188 // If there is a node transformation corresponding to this, keep track of 1189 // it. 1190 Record *Transform = Fragments[i]->getValueAsDef("OperandTransform"); 1191 if (!getSDNodeTransform(Transform).second.empty()) // not noop xform? 1192 P->getOnlyTree()->setTransformFn(Transform); 1193 } 1194 1195 OS << "\n\n"; 1196 1197 // Now that we've parsed all of the tree fragments, do a closure on them so 1198 // that there are not references to PatFrags left inside of them. 1199 for (std::map<Record*, TreePattern*>::iterator I = PatternFragments.begin(), 1200 E = PatternFragments.end(); I != E; ++I) { 1201 TreePattern *ThePat = I->second; 1202 ThePat->InlinePatternFragments(); 1203 1204 // Infer as many types as possible. Don't worry about it if we don't infer 1205 // all of them, some may depend on the inputs of the pattern. 1206 try { 1207 ThePat->InferAllTypes(); 1208 } catch (...) { 1209 // If this pattern fragment is not supported by this target (no types can 1210 // satisfy its constraints), just ignore it. If the bogus pattern is 1211 // actually used by instructions, the type consistency error will be 1212 // reported there. 1213 } 1214 1215 // If debugging, print out the pattern fragment result. 1216 DEBUG(ThePat->dump()); 1217 } 1218} 1219 1220/// HandleUse - Given "Pat" a leaf in the pattern, check to see if it is an 1221/// instruction input. Return true if this is a real use. 1222static bool HandleUse(TreePattern *I, TreePatternNode *Pat, 1223 std::map<std::string, TreePatternNode*> &InstInputs, 1224 std::vector<Record*> &InstImpInputs) { 1225 // No name -> not interesting. 1226 if (Pat->getName().empty()) { 1227 if (Pat->isLeaf()) { 1228 DefInit *DI = dynamic_cast<DefInit*>(Pat->getLeafValue()); 1229 if (DI && DI->getDef()->isSubClassOf("RegisterClass")) 1230 I->error("Input " + DI->getDef()->getName() + " must be named!"); 1231 else if (DI && DI->getDef()->isSubClassOf("Register")) 1232 InstImpInputs.push_back(DI->getDef()); 1233 } 1234 return false; 1235 } 1236 1237 Record *Rec; 1238 if (Pat->isLeaf()) { 1239 DefInit *DI = dynamic_cast<DefInit*>(Pat->getLeafValue()); 1240 if (!DI) I->error("Input $" + Pat->getName() + " must be an identifier!"); 1241 Rec = DI->getDef(); 1242 } else { 1243 assert(Pat->getNumChildren() == 0 && "can't be a use with children!"); 1244 Rec = Pat->getOperator(); 1245 } 1246 1247 // SRCVALUE nodes are ignored. 1248 if (Rec->getName() == "srcvalue") 1249 return false; 1250 1251 TreePatternNode *&Slot = InstInputs[Pat->getName()]; 1252 if (!Slot) { 1253 Slot = Pat; 1254 } else { 1255 Record *SlotRec; 1256 if (Slot->isLeaf()) { 1257 SlotRec = dynamic_cast<DefInit*>(Slot->getLeafValue())->getDef(); 1258 } else { 1259 assert(Slot->getNumChildren() == 0 && "can't be a use with children!"); 1260 SlotRec = Slot->getOperator(); 1261 } 1262 1263 // Ensure that the inputs agree if we've already seen this input. 1264 if (Rec != SlotRec) 1265 I->error("All $" + Pat->getName() + " inputs must agree with each other"); 1266 if (Slot->getExtTypes() != Pat->getExtTypes()) 1267 I->error("All $" + Pat->getName() + " inputs must agree with each other"); 1268 } 1269 return true; 1270} 1271 1272/// FindPatternInputsAndOutputs - Scan the specified TreePatternNode (which is 1273/// part of "I", the instruction), computing the set of inputs and outputs of 1274/// the pattern. Report errors if we see anything naughty. 1275void DAGISelEmitter:: 1276FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, 1277 std::map<std::string, TreePatternNode*> &InstInputs, 1278 std::map<std::string, TreePatternNode*>&InstResults, 1279 std::vector<Record*> &InstImpInputs, 1280 std::vector<Record*> &InstImpResults) { 1281 if (Pat->isLeaf()) { 1282 bool isUse = HandleUse(I, Pat, InstInputs, InstImpInputs); 1283 if (!isUse && Pat->getTransformFn()) 1284 I->error("Cannot specify a transform function for a non-input value!"); 1285 return; 1286 } else if (Pat->getOperator()->getName() != "set") { 1287 // If this is not a set, verify that the children nodes are not void typed, 1288 // and recurse. 1289 for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) { 1290 if (Pat->getChild(i)->getExtTypeNum(0) == MVT::isVoid) 1291 I->error("Cannot have void nodes inside of patterns!"); 1292 FindPatternInputsAndOutputs(I, Pat->getChild(i), InstInputs, InstResults, 1293 InstImpInputs, InstImpResults); 1294 } 1295 1296 // If this is a non-leaf node with no children, treat it basically as if 1297 // it were a leaf. This handles nodes like (imm). 1298 bool isUse = false; 1299 if (Pat->getNumChildren() == 0) 1300 isUse = HandleUse(I, Pat, InstInputs, InstImpInputs); 1301 1302 if (!isUse && Pat->getTransformFn()) 1303 I->error("Cannot specify a transform function for a non-input value!"); 1304 return; 1305 } 1306 1307 // Otherwise, this is a set, validate and collect instruction results. 1308 if (Pat->getNumChildren() == 0) 1309 I->error("set requires operands!"); 1310 else if (Pat->getNumChildren() & 1) 1311 I->error("set requires an even number of operands"); 1312 1313 if (Pat->getTransformFn()) 1314 I->error("Cannot specify a transform function on a set node!"); 1315 1316 // Check the set destinations. 1317 unsigned NumValues = Pat->getNumChildren()/2; 1318 for (unsigned i = 0; i != NumValues; ++i) { 1319 TreePatternNode *Dest = Pat->getChild(i); 1320 if (!Dest->isLeaf()) 1321 I->error("set destination should be a register!"); 1322 1323 DefInit *Val = dynamic_cast<DefInit*>(Dest->getLeafValue()); 1324 if (!Val) 1325 I->error("set destination should be a register!"); 1326 1327 if (Val->getDef()->isSubClassOf("RegisterClass")) { 1328 if (Dest->getName().empty()) 1329 I->error("set destination must have a name!"); 1330 if (InstResults.count(Dest->getName())) 1331 I->error("cannot set '" + Dest->getName() +"' multiple times"); 1332 InstResults[Dest->getName()] = Dest; 1333 } else if (Val->getDef()->isSubClassOf("Register")) { 1334 InstImpResults.push_back(Val->getDef()); 1335 } else { 1336 I->error("set destination should be a register!"); 1337 } 1338 1339 // Verify and collect info from the computation. 1340 FindPatternInputsAndOutputs(I, Pat->getChild(i+NumValues), 1341 InstInputs, InstResults, 1342 InstImpInputs, InstImpResults); 1343 } 1344} 1345 1346/// ParseInstructions - Parse all of the instructions, inlining and resolving 1347/// any fragments involved. This populates the Instructions list with fully 1348/// resolved instructions. 1349void DAGISelEmitter::ParseInstructions() { 1350 std::vector<Record*> Instrs = Records.getAllDerivedDefinitions("Instruction"); 1351 1352 for (unsigned i = 0, e = Instrs.size(); i != e; ++i) { 1353 ListInit *LI = 0; 1354 1355 if (dynamic_cast<ListInit*>(Instrs[i]->getValueInit("Pattern"))) 1356 LI = Instrs[i]->getValueAsListInit("Pattern"); 1357 1358 // If there is no pattern, only collect minimal information about the 1359 // instruction for its operand list. We have to assume that there is one 1360 // result, as we have no detailed info. 1361 if (!LI || LI->getSize() == 0) { 1362 std::vector<Record*> Results; 1363 std::vector<Record*> Operands; 1364 1365 CodeGenInstruction &InstInfo =Target.getInstruction(Instrs[i]->getName()); 1366 1367 if (InstInfo.OperandList.size() != 0) { 1368 // FIXME: temporary hack... 1369 if (InstInfo.noResults) { 1370 // These produce no results 1371 for (unsigned j = 0, e = InstInfo.OperandList.size(); j < e; ++j) 1372 Operands.push_back(InstInfo.OperandList[j].Rec); 1373 } else { 1374 // Assume the first operand is the result. 1375 Results.push_back(InstInfo.OperandList[0].Rec); 1376 1377 // The rest are inputs. 1378 for (unsigned j = 1, e = InstInfo.OperandList.size(); j < e; ++j) 1379 Operands.push_back(InstInfo.OperandList[j].Rec); 1380 } 1381 } 1382 1383 // Create and insert the instruction. 1384 std::vector<Record*> ImpResults; 1385 std::vector<Record*> ImpOperands; 1386 Instructions.insert(std::make_pair(Instrs[i], 1387 DAGInstruction(0, Results, Operands, ImpResults, 1388 ImpOperands))); 1389 continue; // no pattern. 1390 } 1391 1392 // Parse the instruction. 1393 TreePattern *I = new TreePattern(Instrs[i], LI, true, *this); 1394 // Inline pattern fragments into it. 1395 I->InlinePatternFragments(); 1396 1397 // Infer as many types as possible. If we cannot infer all of them, we can 1398 // never do anything with this instruction pattern: report it to the user. 1399 if (!I->InferAllTypes()) 1400 I->error("Could not infer all types in pattern!"); 1401 1402 // InstInputs - Keep track of all of the inputs of the instruction, along 1403 // with the record they are declared as. 1404 std::map<std::string, TreePatternNode*> InstInputs; 1405 1406 // InstResults - Keep track of all the virtual registers that are 'set' 1407 // in the instruction, including what reg class they are. 1408 std::map<std::string, TreePatternNode*> InstResults; 1409 1410 std::vector<Record*> InstImpInputs; 1411 std::vector<Record*> InstImpResults; 1412 1413 // Verify that the top-level forms in the instruction are of void type, and 1414 // fill in the InstResults map. 1415 for (unsigned j = 0, e = I->getNumTrees(); j != e; ++j) { 1416 TreePatternNode *Pat = I->getTree(j); 1417 if (Pat->getExtTypeNum(0) != MVT::isVoid) 1418 I->error("Top-level forms in instruction pattern should have" 1419 " void types"); 1420 1421 // Find inputs and outputs, and verify the structure of the uses/defs. 1422 FindPatternInputsAndOutputs(I, Pat, InstInputs, InstResults, 1423 InstImpInputs, InstImpResults); 1424 } 1425 1426 // Now that we have inputs and outputs of the pattern, inspect the operands 1427 // list for the instruction. This determines the order that operands are 1428 // added to the machine instruction the node corresponds to. 1429 unsigned NumResults = InstResults.size(); 1430 1431 // Parse the operands list from the (ops) list, validating it. 1432 std::vector<std::string> &Args = I->getArgList(); 1433 assert(Args.empty() && "Args list should still be empty here!"); 1434 CodeGenInstruction &CGI = Target.getInstruction(Instrs[i]->getName()); 1435 1436 // Check that all of the results occur first in the list. 1437 std::vector<Record*> Results; 1438 TreePatternNode *Res0Node = NULL; 1439 for (unsigned i = 0; i != NumResults; ++i) { 1440 if (i == CGI.OperandList.size()) 1441 I->error("'" + InstResults.begin()->first + 1442 "' set but does not appear in operand list!"); 1443 const std::string &OpName = CGI.OperandList[i].Name; 1444 1445 // Check that it exists in InstResults. 1446 TreePatternNode *RNode = InstResults[OpName]; 1447 if (RNode == 0) 1448 I->error("Operand $" + OpName + " does not exist in operand list!"); 1449 1450 if (i == 0) 1451 Res0Node = RNode; 1452 Record *R = dynamic_cast<DefInit*>(RNode->getLeafValue())->getDef(); 1453 if (R == 0) 1454 I->error("Operand $" + OpName + " should be a set destination: all " 1455 "outputs must occur before inputs in operand list!"); 1456 1457 if (CGI.OperandList[i].Rec != R) 1458 I->error("Operand $" + OpName + " class mismatch!"); 1459 1460 // Remember the return type. 1461 Results.push_back(CGI.OperandList[i].Rec); 1462 1463 // Okay, this one checks out. 1464 InstResults.erase(OpName); 1465 } 1466 1467 // Loop over the inputs next. Make a copy of InstInputs so we can destroy 1468 // the copy while we're checking the inputs. 1469 std::map<std::string, TreePatternNode*> InstInputsCheck(InstInputs); 1470 1471 std::vector<TreePatternNode*> ResultNodeOperands; 1472 std::vector<Record*> Operands; 1473 for (unsigned i = NumResults, e = CGI.OperandList.size(); i != e; ++i) { 1474 const std::string &OpName = CGI.OperandList[i].Name; 1475 if (OpName.empty()) 1476 I->error("Operand #" + utostr(i) + " in operands list has no name!"); 1477 1478 if (!InstInputsCheck.count(OpName)) 1479 I->error("Operand $" + OpName + 1480 " does not appear in the instruction pattern"); 1481 TreePatternNode *InVal = InstInputsCheck[OpName]; 1482 InstInputsCheck.erase(OpName); // It occurred, remove from map. 1483 1484 if (InVal->isLeaf() && 1485 dynamic_cast<DefInit*>(InVal->getLeafValue())) { 1486 Record *InRec = static_cast<DefInit*>(InVal->getLeafValue())->getDef(); 1487 if (CGI.OperandList[i].Rec != InRec && 1488 !InRec->isSubClassOf("ComplexPattern")) 1489 I->error("Operand $" + OpName + "'s register class disagrees" 1490 " between the operand and pattern"); 1491 } 1492 Operands.push_back(CGI.OperandList[i].Rec); 1493 1494 // Construct the result for the dest-pattern operand list. 1495 TreePatternNode *OpNode = InVal->clone(); 1496 1497 // No predicate is useful on the result. 1498 OpNode->setPredicateFn(""); 1499 1500 // Promote the xform function to be an explicit node if set. 1501 if (Record *Xform = OpNode->getTransformFn()) { 1502 OpNode->setTransformFn(0); 1503 std::vector<TreePatternNode*> Children; 1504 Children.push_back(OpNode); 1505 OpNode = new TreePatternNode(Xform, Children); 1506 } 1507 1508 ResultNodeOperands.push_back(OpNode); 1509 } 1510 1511 if (!InstInputsCheck.empty()) 1512 I->error("Input operand $" + InstInputsCheck.begin()->first + 1513 " occurs in pattern but not in operands list!"); 1514 1515 TreePatternNode *ResultPattern = 1516 new TreePatternNode(I->getRecord(), ResultNodeOperands); 1517 // Copy fully inferred output node type to instruction result pattern. 1518 if (NumResults > 0) 1519 ResultPattern->setTypes(Res0Node->getExtTypes()); 1520 1521 // Create and insert the instruction. 1522 DAGInstruction TheInst(I, Results, Operands, InstImpResults, InstImpInputs); 1523 Instructions.insert(std::make_pair(I->getRecord(), TheInst)); 1524 1525 // Use a temporary tree pattern to infer all types and make sure that the 1526 // constructed result is correct. This depends on the instruction already 1527 // being inserted into the Instructions map. 1528 TreePattern Temp(I->getRecord(), ResultPattern, false, *this); 1529 Temp.InferAllTypes(); 1530 1531 DAGInstruction &TheInsertedInst = Instructions.find(I->getRecord())->second; 1532 TheInsertedInst.setResultPattern(Temp.getOnlyTree()); 1533 1534 DEBUG(I->dump()); 1535 } 1536 1537 // If we can, convert the instructions to be patterns that are matched! 1538 for (std::map<Record*, DAGInstruction>::iterator II = Instructions.begin(), 1539 E = Instructions.end(); II != E; ++II) { 1540 DAGInstruction &TheInst = II->second; 1541 TreePattern *I = TheInst.getPattern(); 1542 if (I == 0) continue; // No pattern. 1543 1544 if (I->getNumTrees() != 1) { 1545 std::cerr << "CANNOT HANDLE: " << I->getRecord()->getName() << " yet!"; 1546 continue; 1547 } 1548 TreePatternNode *Pattern = I->getTree(0); 1549 TreePatternNode *SrcPattern; 1550 if (Pattern->getOperator()->getName() == "set") { 1551 if (Pattern->getNumChildren() != 2) 1552 continue; // Not a set of a single value (not handled so far) 1553 1554 SrcPattern = Pattern->getChild(1)->clone(); 1555 } else{ 1556 // Not a set (store or something?) 1557 SrcPattern = Pattern; 1558 } 1559 1560 std::string Reason; 1561 if (!SrcPattern->canPatternMatch(Reason, *this)) 1562 I->error("Instruction can never match: " + Reason); 1563 1564 Record *Instr = II->first; 1565 TreePatternNode *DstPattern = TheInst.getResultPattern(); 1566 PatternsToMatch. 1567 push_back(PatternToMatch(Instr->getValueAsListInit("Predicates"), 1568 SrcPattern, DstPattern, 1569 Instr->getValueAsInt("AddedComplexity"))); 1570 } 1571} 1572 1573void DAGISelEmitter::ParsePatterns() { 1574 std::vector<Record*> Patterns = Records.getAllDerivedDefinitions("Pattern"); 1575 1576 for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { 1577 DagInit *Tree = Patterns[i]->getValueAsDag("PatternToMatch"); 1578 TreePattern *Pattern = new TreePattern(Patterns[i], Tree, true, *this); 1579 1580 // Inline pattern fragments into it. 1581 Pattern->InlinePatternFragments(); 1582 1583 ListInit *LI = Patterns[i]->getValueAsListInit("ResultInstrs"); 1584 if (LI->getSize() == 0) continue; // no pattern. 1585 1586 // Parse the instruction. 1587 TreePattern *Result = new TreePattern(Patterns[i], LI, false, *this); 1588 1589 // Inline pattern fragments into it. 1590 Result->InlinePatternFragments(); 1591 1592 if (Result->getNumTrees() != 1) 1593 Result->error("Cannot handle instructions producing instructions " 1594 "with temporaries yet!"); 1595 1596 bool IterateInference; 1597 bool InferredAllPatternTypes, InferredAllResultTypes; 1598 do { 1599 // Infer as many types as possible. If we cannot infer all of them, we 1600 // can never do anything with this pattern: report it to the user. 1601 InferredAllPatternTypes = Pattern->InferAllTypes(); 1602 1603 // Infer as many types as possible. If we cannot infer all of them, we 1604 // can never do anything with this pattern: report it to the user. 1605 InferredAllResultTypes = Result->InferAllTypes(); 1606 1607 // Apply the type of the result to the source pattern. This helps us 1608 // resolve cases where the input type is known to be a pointer type (which 1609 // is considered resolved), but the result knows it needs to be 32- or 1610 // 64-bits. Infer the other way for good measure. 1611 IterateInference = Pattern->getOnlyTree()-> 1612 UpdateNodeType(Result->getOnlyTree()->getExtTypes(), *Result); 1613 IterateInference |= Result->getOnlyTree()-> 1614 UpdateNodeType(Pattern->getOnlyTree()->getExtTypes(), *Result); 1615 } while (IterateInference); 1616 1617 // Verify that we inferred enough types that we can do something with the 1618 // pattern and result. If these fire the user has to add type casts. 1619 if (!InferredAllPatternTypes) 1620 Pattern->error("Could not infer all types in pattern!"); 1621 if (!InferredAllResultTypes) 1622 Result->error("Could not infer all types in pattern result!"); 1623 1624 // Validate that the input pattern is correct. 1625 { 1626 std::map<std::string, TreePatternNode*> InstInputs; 1627 std::map<std::string, TreePatternNode*> InstResults; 1628 std::vector<Record*> InstImpInputs; 1629 std::vector<Record*> InstImpResults; 1630 FindPatternInputsAndOutputs(Pattern, Pattern->getOnlyTree(), 1631 InstInputs, InstResults, 1632 InstImpInputs, InstImpResults); 1633 } 1634 1635 // Promote the xform function to be an explicit node if set. 1636 std::vector<TreePatternNode*> ResultNodeOperands; 1637 TreePatternNode *DstPattern = Result->getOnlyTree(); 1638 for (unsigned ii = 0, ee = DstPattern->getNumChildren(); ii != ee; ++ii) { 1639 TreePatternNode *OpNode = DstPattern->getChild(ii); 1640 if (Record *Xform = OpNode->getTransformFn()) { 1641 OpNode->setTransformFn(0); 1642 std::vector<TreePatternNode*> Children; 1643 Children.push_back(OpNode); 1644 OpNode = new TreePatternNode(Xform, Children); 1645 } 1646 ResultNodeOperands.push_back(OpNode); 1647 } 1648 DstPattern = Result->getOnlyTree(); 1649 if (!DstPattern->isLeaf()) 1650 DstPattern = new TreePatternNode(DstPattern->getOperator(), 1651 ResultNodeOperands); 1652 DstPattern->setTypes(Result->getOnlyTree()->getExtTypes()); 1653 TreePattern Temp(Result->getRecord(), DstPattern, false, *this); 1654 Temp.InferAllTypes(); 1655 1656 std::string Reason; 1657 if (!Pattern->getOnlyTree()->canPatternMatch(Reason, *this)) 1658 Pattern->error("Pattern can never match: " + Reason); 1659 1660 PatternsToMatch. 1661 push_back(PatternToMatch(Patterns[i]->getValueAsListInit("Predicates"), 1662 Pattern->getOnlyTree(), 1663 Temp.getOnlyTree(), 1664 Patterns[i]->getValueAsInt("AddedComplexity"))); 1665 } 1666} 1667 1668/// CombineChildVariants - Given a bunch of permutations of each child of the 1669/// 'operator' node, put them together in all possible ways. 1670static void CombineChildVariants(TreePatternNode *Orig, 1671 const std::vector<std::vector<TreePatternNode*> > &ChildVariants, 1672 std::vector<TreePatternNode*> &OutVariants, 1673 DAGISelEmitter &ISE) { 1674 // Make sure that each operand has at least one variant to choose from. 1675 for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i) 1676 if (ChildVariants[i].empty()) 1677 return; 1678 1679 // The end result is an all-pairs construction of the resultant pattern. 1680 std::vector<unsigned> Idxs; 1681 Idxs.resize(ChildVariants.size()); 1682 bool NotDone = true; 1683 while (NotDone) { 1684 // Create the variant and add it to the output list. 1685 std::vector<TreePatternNode*> NewChildren; 1686 for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i) 1687 NewChildren.push_back(ChildVariants[i][Idxs[i]]); 1688 TreePatternNode *R = new TreePatternNode(Orig->getOperator(), NewChildren); 1689 1690 // Copy over properties. 1691 R->setName(Orig->getName()); 1692 R->setPredicateFn(Orig->getPredicateFn()); 1693 R->setTransformFn(Orig->getTransformFn()); 1694 R->setTypes(Orig->getExtTypes()); 1695 1696 // If this pattern cannot every match, do not include it as a variant. 1697 std::string ErrString; 1698 if (!R->canPatternMatch(ErrString, ISE)) { 1699 delete R; 1700 } else { 1701 bool AlreadyExists = false; 1702 1703 // Scan to see if this pattern has already been emitted. We can get 1704 // duplication due to things like commuting: 1705 // (and GPRC:$a, GPRC:$b) -> (and GPRC:$b, GPRC:$a) 1706 // which are the same pattern. Ignore the dups. 1707 for (unsigned i = 0, e = OutVariants.size(); i != e; ++i) 1708 if (R->isIsomorphicTo(OutVariants[i])) { 1709 AlreadyExists = true; 1710 break; 1711 } 1712 1713 if (AlreadyExists) 1714 delete R; 1715 else 1716 OutVariants.push_back(R); 1717 } 1718 1719 // Increment indices to the next permutation. 1720 NotDone = false; 1721 // Look for something we can increment without causing a wrap-around. 1722 for (unsigned IdxsIdx = 0; IdxsIdx != Idxs.size(); ++IdxsIdx) { 1723 if (++Idxs[IdxsIdx] < ChildVariants[IdxsIdx].size()) { 1724 NotDone = true; // Found something to increment. 1725 break; 1726 } 1727 Idxs[IdxsIdx] = 0; 1728 } 1729 } 1730} 1731 1732/// CombineChildVariants - A helper function for binary operators. 1733/// 1734static void CombineChildVariants(TreePatternNode *Orig, 1735 const std::vector<TreePatternNode*> &LHS, 1736 const std::vector<TreePatternNode*> &RHS, 1737 std::vector<TreePatternNode*> &OutVariants, 1738 DAGISelEmitter &ISE) { 1739 std::vector<std::vector<TreePatternNode*> > ChildVariants; 1740 ChildVariants.push_back(LHS); 1741 ChildVariants.push_back(RHS); 1742 CombineChildVariants(Orig, ChildVariants, OutVariants, ISE); 1743} 1744 1745 1746static void GatherChildrenOfAssociativeOpcode(TreePatternNode *N, 1747 std::vector<TreePatternNode *> &Children) { 1748 assert(N->getNumChildren()==2 &&"Associative but doesn't have 2 children!"); 1749 Record *Operator = N->getOperator(); 1750 1751 // Only permit raw nodes. 1752 if (!N->getName().empty() || !N->getPredicateFn().empty() || 1753 N->getTransformFn()) { 1754 Children.push_back(N); 1755 return; 1756 } 1757 1758 if (N->getChild(0)->isLeaf() || N->getChild(0)->getOperator() != Operator) 1759 Children.push_back(N->getChild(0)); 1760 else 1761 GatherChildrenOfAssociativeOpcode(N->getChild(0), Children); 1762 1763 if (N->getChild(1)->isLeaf() || N->getChild(1)->getOperator() != Operator) 1764 Children.push_back(N->getChild(1)); 1765 else 1766 GatherChildrenOfAssociativeOpcode(N->getChild(1), Children); 1767} 1768 1769/// GenerateVariantsOf - Given a pattern N, generate all permutations we can of 1770/// the (potentially recursive) pattern by using algebraic laws. 1771/// 1772static void GenerateVariantsOf(TreePatternNode *N, 1773 std::vector<TreePatternNode*> &OutVariants, 1774 DAGISelEmitter &ISE) { 1775 // We cannot permute leaves. 1776 if (N->isLeaf()) { 1777 OutVariants.push_back(N); 1778 return; 1779 } 1780 1781 // Look up interesting info about the node. 1782 const SDNodeInfo &NodeInfo = ISE.getSDNodeInfo(N->getOperator()); 1783 1784 // If this node is associative, reassociate. 1785 if (NodeInfo.hasProperty(SDNPAssociative)) { 1786 // Reassociate by pulling together all of the linked operators 1787 std::vector<TreePatternNode*> MaximalChildren; 1788 GatherChildrenOfAssociativeOpcode(N, MaximalChildren); 1789 1790 // Only handle child sizes of 3. Otherwise we'll end up trying too many 1791 // permutations. 1792 if (MaximalChildren.size() == 3) { 1793 // Find the variants of all of our maximal children. 1794 std::vector<TreePatternNode*> AVariants, BVariants, CVariants; 1795 GenerateVariantsOf(MaximalChildren[0], AVariants, ISE); 1796 GenerateVariantsOf(MaximalChildren[1], BVariants, ISE); 1797 GenerateVariantsOf(MaximalChildren[2], CVariants, ISE); 1798 1799 // There are only two ways we can permute the tree: 1800 // (A op B) op C and A op (B op C) 1801 // Within these forms, we can also permute A/B/C. 1802 1803 // Generate legal pair permutations of A/B/C. 1804 std::vector<TreePatternNode*> ABVariants; 1805 std::vector<TreePatternNode*> BAVariants; 1806 std::vector<TreePatternNode*> ACVariants; 1807 std::vector<TreePatternNode*> CAVariants; 1808 std::vector<TreePatternNode*> BCVariants; 1809 std::vector<TreePatternNode*> CBVariants; 1810 CombineChildVariants(N, AVariants, BVariants, ABVariants, ISE); 1811 CombineChildVariants(N, BVariants, AVariants, BAVariants, ISE); 1812 CombineChildVariants(N, AVariants, CVariants, ACVariants, ISE); 1813 CombineChildVariants(N, CVariants, AVariants, CAVariants, ISE); 1814 CombineChildVariants(N, BVariants, CVariants, BCVariants, ISE); 1815 CombineChildVariants(N, CVariants, BVariants, CBVariants, ISE); 1816 1817 // Combine those into the result: (x op x) op x 1818 CombineChildVariants(N, ABVariants, CVariants, OutVariants, ISE); 1819 CombineChildVariants(N, BAVariants, CVariants, OutVariants, ISE); 1820 CombineChildVariants(N, ACVariants, BVariants, OutVariants, ISE); 1821 CombineChildVariants(N, CAVariants, BVariants, OutVariants, ISE); 1822 CombineChildVariants(N, BCVariants, AVariants, OutVariants, ISE); 1823 CombineChildVariants(N, CBVariants, AVariants, OutVariants, ISE); 1824 1825 // Combine those into the result: x op (x op x) 1826 CombineChildVariants(N, CVariants, ABVariants, OutVariants, ISE); 1827 CombineChildVariants(N, CVariants, BAVariants, OutVariants, ISE); 1828 CombineChildVariants(N, BVariants, ACVariants, OutVariants, ISE); 1829 CombineChildVariants(N, BVariants, CAVariants, OutVariants, ISE); 1830 CombineChildVariants(N, AVariants, BCVariants, OutVariants, ISE); 1831 CombineChildVariants(N, AVariants, CBVariants, OutVariants, ISE); 1832 return; 1833 } 1834 } 1835 1836 // Compute permutations of all children. 1837 std::vector<std::vector<TreePatternNode*> > ChildVariants; 1838 ChildVariants.resize(N->getNumChildren()); 1839 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 1840 GenerateVariantsOf(N->getChild(i), ChildVariants[i], ISE); 1841 1842 // Build all permutations based on how the children were formed. 1843 CombineChildVariants(N, ChildVariants, OutVariants, ISE); 1844 1845 // If this node is commutative, consider the commuted order. 1846 if (NodeInfo.hasProperty(SDNPCommutative)) { 1847 assert(N->getNumChildren()==2 &&"Commutative but doesn't have 2 children!"); 1848 // Don't count children which are actually register references. 1849 unsigned NC = 0; 1850 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { 1851 TreePatternNode *Child = N->getChild(i); 1852 if (Child->isLeaf()) 1853 if (DefInit *DI = dynamic_cast<DefInit*>(Child->getLeafValue())) { 1854 Record *RR = DI->getDef(); 1855 if (RR->isSubClassOf("Register")) 1856 continue; 1857 } 1858 NC++; 1859 } 1860 // Consider the commuted order. 1861 if (NC == 2) 1862 CombineChildVariants(N, ChildVariants[1], ChildVariants[0], 1863 OutVariants, ISE); 1864 } 1865} 1866 1867 1868// GenerateVariants - Generate variants. For example, commutative patterns can 1869// match multiple ways. Add them to PatternsToMatch as well. 1870void DAGISelEmitter::GenerateVariants() { 1871 1872 DEBUG(std::cerr << "Generating instruction variants.\n"); 1873 1874 // Loop over all of the patterns we've collected, checking to see if we can 1875 // generate variants of the instruction, through the exploitation of 1876 // identities. This permits the target to provide agressive matching without 1877 // the .td file having to contain tons of variants of instructions. 1878 // 1879 // Note that this loop adds new patterns to the PatternsToMatch list, but we 1880 // intentionally do not reconsider these. Any variants of added patterns have 1881 // already been added. 1882 // 1883 for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) { 1884 std::vector<TreePatternNode*> Variants; 1885 GenerateVariantsOf(PatternsToMatch[i].getSrcPattern(), Variants, *this); 1886 1887 assert(!Variants.empty() && "Must create at least original variant!"); 1888 Variants.erase(Variants.begin()); // Remove the original pattern. 1889 1890 if (Variants.empty()) // No variants for this pattern. 1891 continue; 1892 1893 DEBUG(std::cerr << "FOUND VARIANTS OF: "; 1894 PatternsToMatch[i].getSrcPattern()->dump(); 1895 std::cerr << "\n"); 1896 1897 for (unsigned v = 0, e = Variants.size(); v != e; ++v) { 1898 TreePatternNode *Variant = Variants[v]; 1899 1900 DEBUG(std::cerr << " VAR#" << v << ": "; 1901 Variant->dump(); 1902 std::cerr << "\n"); 1903 1904 // Scan to see if an instruction or explicit pattern already matches this. 1905 bool AlreadyExists = false; 1906 for (unsigned p = 0, e = PatternsToMatch.size(); p != e; ++p) { 1907 // Check to see if this variant already exists. 1908 if (Variant->isIsomorphicTo(PatternsToMatch[p].getSrcPattern())) { 1909 DEBUG(std::cerr << " *** ALREADY EXISTS, ignoring variant.\n"); 1910 AlreadyExists = true; 1911 break; 1912 } 1913 } 1914 // If we already have it, ignore the variant. 1915 if (AlreadyExists) continue; 1916 1917 // Otherwise, add it to the list of patterns we have. 1918 PatternsToMatch. 1919 push_back(PatternToMatch(PatternsToMatch[i].getPredicates(), 1920 Variant, PatternsToMatch[i].getDstPattern(), 1921 PatternsToMatch[i].getAddedComplexity())); 1922 } 1923 1924 DEBUG(std::cerr << "\n"); 1925 } 1926} 1927 1928// NodeIsComplexPattern - return true if N is a leaf node and a subclass of 1929// ComplexPattern. 1930static bool NodeIsComplexPattern(TreePatternNode *N) 1931{ 1932 return (N->isLeaf() && 1933 dynamic_cast<DefInit*>(N->getLeafValue()) && 1934 static_cast<DefInit*>(N->getLeafValue())->getDef()-> 1935 isSubClassOf("ComplexPattern")); 1936} 1937 1938// NodeGetComplexPattern - return the pointer to the ComplexPattern if N 1939// is a leaf node and a subclass of ComplexPattern, else it returns NULL. 1940static const ComplexPattern *NodeGetComplexPattern(TreePatternNode *N, 1941 DAGISelEmitter &ISE) 1942{ 1943 if (N->isLeaf() && 1944 dynamic_cast<DefInit*>(N->getLeafValue()) && 1945 static_cast<DefInit*>(N->getLeafValue())->getDef()-> 1946 isSubClassOf("ComplexPattern")) { 1947 return &ISE.getComplexPattern(static_cast<DefInit*>(N->getLeafValue()) 1948 ->getDef()); 1949 } 1950 return NULL; 1951} 1952 1953/// getPatternSize - Return the 'size' of this pattern. We want to match large 1954/// patterns before small ones. This is used to determine the size of a 1955/// pattern. 1956static unsigned getPatternSize(TreePatternNode *P, DAGISelEmitter &ISE) { 1957 assert((isExtIntegerInVTs(P->getExtTypes()) || 1958 isExtFloatingPointInVTs(P->getExtTypes()) || 1959 P->getExtTypeNum(0) == MVT::isVoid || 1960 P->getExtTypeNum(0) == MVT::Flag || 1961 P->getExtTypeNum(0) == MVT::iPTR) && 1962 "Not a valid pattern node to size!"); 1963 unsigned Size = 3; // The node itself. 1964 // If the root node is a ConstantSDNode, increases its size. 1965 // e.g. (set R32:$dst, 0). 1966 if (P->isLeaf() && dynamic_cast<IntInit*>(P->getLeafValue())) 1967 Size += 2; 1968 1969 // FIXME: This is a hack to statically increase the priority of patterns 1970 // which maps a sub-dag to a complex pattern. e.g. favors LEA over ADD. 1971 // Later we can allow complexity / cost for each pattern to be (optionally) 1972 // specified. To get best possible pattern match we'll need to dynamically 1973 // calculate the complexity of all patterns a dag can potentially map to. 1974 const ComplexPattern *AM = NodeGetComplexPattern(P, ISE); 1975 if (AM) 1976 Size += AM->getNumOperands() * 3; 1977 1978 // If this node has some predicate function that must match, it adds to the 1979 // complexity of this node. 1980 if (!P->getPredicateFn().empty()) 1981 ++Size; 1982 1983 // Count children in the count if they are also nodes. 1984 for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) { 1985 TreePatternNode *Child = P->getChild(i); 1986 if (!Child->isLeaf() && Child->getExtTypeNum(0) != MVT::Other) 1987 Size += getPatternSize(Child, ISE); 1988 else if (Child->isLeaf()) { 1989 if (dynamic_cast<IntInit*>(Child->getLeafValue())) 1990 Size += 5; // Matches a ConstantSDNode (+3) and a specific value (+2). 1991 else if (NodeIsComplexPattern(Child)) 1992 Size += getPatternSize(Child, ISE); 1993 else if (!Child->getPredicateFn().empty()) 1994 ++Size; 1995 } 1996 } 1997 1998 return Size; 1999} 2000 2001/// getResultPatternCost - Compute the number of instructions for this pattern. 2002/// This is a temporary hack. We should really include the instruction 2003/// latencies in this calculation. 2004static unsigned getResultPatternCost(TreePatternNode *P, DAGISelEmitter &ISE) { 2005 if (P->isLeaf()) return 0; 2006 2007 unsigned Cost = 0; 2008 Record *Op = P->getOperator(); 2009 if (Op->isSubClassOf("Instruction")) { 2010 Cost++; 2011 CodeGenInstruction &II = ISE.getTargetInfo().getInstruction(Op->getName()); 2012 if (II.usesCustomDAGSchedInserter) 2013 Cost += 10; 2014 } 2015 for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) 2016 Cost += getResultPatternCost(P->getChild(i), ISE); 2017 return Cost; 2018} 2019 2020/// getResultPatternCodeSize - Compute the code size of instructions for this 2021/// pattern. 2022static unsigned getResultPatternSize(TreePatternNode *P, DAGISelEmitter &ISE) { 2023 if (P->isLeaf()) return 0; 2024 2025 unsigned Cost = 0; 2026 Record *Op = P->getOperator(); 2027 if (Op->isSubClassOf("Instruction")) { 2028 Cost += Op->getValueAsInt("CodeSize"); 2029 } 2030 for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) 2031 Cost += getResultPatternSize(P->getChild(i), ISE); 2032 return Cost; 2033} 2034 2035// PatternSortingPredicate - return true if we prefer to match LHS before RHS. 2036// In particular, we want to match maximal patterns first and lowest cost within 2037// a particular complexity first. 2038struct PatternSortingPredicate { 2039 PatternSortingPredicate(DAGISelEmitter &ise) : ISE(ise) {}; 2040 DAGISelEmitter &ISE; 2041 2042 bool operator()(PatternToMatch *LHS, 2043 PatternToMatch *RHS) { 2044 unsigned LHSSize = getPatternSize(LHS->getSrcPattern(), ISE); 2045 unsigned RHSSize = getPatternSize(RHS->getSrcPattern(), ISE); 2046 LHSSize += LHS->getAddedComplexity(); 2047 RHSSize += RHS->getAddedComplexity(); 2048 if (LHSSize > RHSSize) return true; // LHS -> bigger -> less cost 2049 if (LHSSize < RHSSize) return false; 2050 2051 // If the patterns have equal complexity, compare generated instruction cost 2052 unsigned LHSCost = getResultPatternCost(LHS->getDstPattern(), ISE); 2053 unsigned RHSCost = getResultPatternCost(RHS->getDstPattern(), ISE); 2054 if (LHSCost < RHSCost) return true; 2055 if (LHSCost > RHSCost) return false; 2056 2057 return getResultPatternSize(LHS->getDstPattern(), ISE) < 2058 getResultPatternSize(RHS->getDstPattern(), ISE); 2059 } 2060}; 2061 2062/// getRegisterValueType - Look up and return the first ValueType of specified 2063/// RegisterClass record 2064static MVT::ValueType getRegisterValueType(Record *R, const CodeGenTarget &T) { 2065 if (const CodeGenRegisterClass *RC = T.getRegisterClassForRegister(R)) 2066 return RC->getValueTypeNum(0); 2067 return MVT::Other; 2068} 2069 2070 2071/// RemoveAllTypes - A quick recursive walk over a pattern which removes all 2072/// type information from it. 2073static void RemoveAllTypes(TreePatternNode *N) { 2074 N->removeTypes(); 2075 if (!N->isLeaf()) 2076 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 2077 RemoveAllTypes(N->getChild(i)); 2078} 2079 2080Record *DAGISelEmitter::getSDNodeNamed(const std::string &Name) const { 2081 Record *N = Records.getDef(Name); 2082 if (!N || !N->isSubClassOf("SDNode")) { 2083 std::cerr << "Error getting SDNode '" << Name << "'!\n"; 2084 exit(1); 2085 } 2086 return N; 2087} 2088 2089/// NodeHasProperty - return true if TreePatternNode has the specified 2090/// property. 2091static bool NodeHasProperty(TreePatternNode *N, SDNP Property, 2092 DAGISelEmitter &ISE) 2093{ 2094 if (N->isLeaf()) { 2095 const ComplexPattern *CP = NodeGetComplexPattern(N, ISE); 2096 if (CP) 2097 return CP->hasProperty(Property); 2098 return false; 2099 } 2100 Record *Operator = N->getOperator(); 2101 if (!Operator->isSubClassOf("SDNode")) return false; 2102 2103 const SDNodeInfo &NodeInfo = ISE.getSDNodeInfo(Operator); 2104 return NodeInfo.hasProperty(Property); 2105} 2106 2107static bool PatternHasProperty(TreePatternNode *N, SDNP Property, 2108 DAGISelEmitter &ISE) 2109{ 2110 if (NodeHasProperty(N, Property, ISE)) 2111 return true; 2112 2113 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { 2114 TreePatternNode *Child = N->getChild(i); 2115 if (PatternHasProperty(Child, Property, ISE)) 2116 return true; 2117 } 2118 2119 return false; 2120} 2121 2122class PatternCodeEmitter { 2123private: 2124 DAGISelEmitter &ISE; 2125 2126 // Predicates. 2127 ListInit *Predicates; 2128 // Pattern cost. 2129 unsigned Cost; 2130 // Instruction selector pattern. 2131 TreePatternNode *Pattern; 2132 // Matched instruction. 2133 TreePatternNode *Instruction; 2134 2135 // Node to name mapping 2136 std::map<std::string, std::string> VariableMap; 2137 // Node to operator mapping 2138 std::map<std::string, Record*> OperatorMap; 2139 // Names of all the folded nodes which produce chains. 2140 std::vector<std::pair<std::string, unsigned> > FoldedChains; 2141 // Original input chain(s). 2142 std::vector<std::pair<std::string, std::string> > OrigChains; 2143 std::set<std::string> Duplicates; 2144 2145 /// GeneratedCode - This is the buffer that we emit code to. The first int 2146 /// indicates whether this is an exit predicate (something that should be 2147 /// tested, and if true, the match fails) [when 1], or normal code to emit 2148 /// [when 0], or initialization code to emit [when 2]. 2149 std::vector<std::pair<unsigned, std::string> > &GeneratedCode; 2150 /// GeneratedDecl - This is the set of all SDOperand declarations needed for 2151 /// the set of patterns for each top-level opcode. 2152 std::set<std::string> &GeneratedDecl; 2153 /// TargetOpcodes - The target specific opcodes used by the resulting 2154 /// instructions. 2155 std::vector<std::string> &TargetOpcodes; 2156 std::vector<std::string> &TargetVTs; 2157 2158 std::string ChainName; 2159 unsigned TmpNo; 2160 unsigned OpcNo; 2161 unsigned VTNo; 2162 2163 void emitCheck(const std::string &S) { 2164 if (!S.empty()) 2165 GeneratedCode.push_back(std::make_pair(1, S)); 2166 } 2167 void emitCode(const std::string &S) { 2168 if (!S.empty()) 2169 GeneratedCode.push_back(std::make_pair(0, S)); 2170 } 2171 void emitInit(const std::string &S) { 2172 if (!S.empty()) 2173 GeneratedCode.push_back(std::make_pair(2, S)); 2174 } 2175 void emitDecl(const std::string &S) { 2176 assert(!S.empty() && "Invalid declaration"); 2177 GeneratedDecl.insert(S); 2178 } 2179 void emitOpcode(const std::string &Opc) { 2180 TargetOpcodes.push_back(Opc); 2181 OpcNo++; 2182 } 2183 void emitVT(const std::string &VT) { 2184 TargetVTs.push_back(VT); 2185 VTNo++; 2186 } 2187public: 2188 PatternCodeEmitter(DAGISelEmitter &ise, ListInit *preds, 2189 TreePatternNode *pattern, TreePatternNode *instr, 2190 std::vector<std::pair<unsigned, std::string> > &gc, 2191 std::set<std::string> &gd, 2192 std::vector<std::string> &to, 2193 std::vector<std::string> &tv) 2194 : ISE(ise), Predicates(preds), Pattern(pattern), Instruction(instr), 2195 GeneratedCode(gc), GeneratedDecl(gd), 2196 TargetOpcodes(to), TargetVTs(tv), 2197 TmpNo(0), OpcNo(0), VTNo(0) {} 2198 2199 /// EmitMatchCode - Emit a matcher for N, going to the label for PatternNo 2200 /// if the match fails. At this point, we already know that the opcode for N 2201 /// matches, and the SDNode for the result has the RootName specified name. 2202 void EmitMatchCode(TreePatternNode *Root, TreePatternNode *N, 2203 TreePatternNode *P, const std::string &RootName, 2204 const std::string &ChainSuffix, bool &FoundChain) { 2205 bool isRoot = (P == NULL); 2206 // Emit instruction predicates. Each predicate is just a string for now. 2207 if (isRoot) { 2208 std::string PredicateCheck; 2209 for (unsigned i = 0, e = Predicates->getSize(); i != e; ++i) { 2210 if (DefInit *Pred = dynamic_cast<DefInit*>(Predicates->getElement(i))) { 2211 Record *Def = Pred->getDef(); 2212 if (!Def->isSubClassOf("Predicate")) { 2213#ifndef NDEBUG 2214 Def->dump(); 2215#endif 2216 assert(0 && "Unknown predicate type!"); 2217 } 2218 if (!PredicateCheck.empty()) 2219 PredicateCheck += " && "; 2220 PredicateCheck += "(" + Def->getValueAsString("CondString") + ")"; 2221 } 2222 } 2223 2224 emitCheck(PredicateCheck); 2225 } 2226 2227 if (N->isLeaf()) { 2228 if (IntInit *II = dynamic_cast<IntInit*>(N->getLeafValue())) { 2229 emitCheck("cast<ConstantSDNode>(" + RootName + 2230 ")->getSignExtended() == " + itostr(II->getValue())); 2231 return; 2232 } else if (!NodeIsComplexPattern(N)) { 2233 assert(0 && "Cannot match this as a leaf value!"); 2234 abort(); 2235 } 2236 } 2237 2238 // If this node has a name associated with it, capture it in VariableMap. If 2239 // we already saw this in the pattern, emit code to verify dagness. 2240 if (!N->getName().empty()) { 2241 std::string &VarMapEntry = VariableMap[N->getName()]; 2242 if (VarMapEntry.empty()) { 2243 VarMapEntry = RootName; 2244 } else { 2245 // If we get here, this is a second reference to a specific name. Since 2246 // we already have checked that the first reference is valid, we don't 2247 // have to recursively match it, just check that it's the same as the 2248 // previously named thing. 2249 emitCheck(VarMapEntry + " == " + RootName); 2250 return; 2251 } 2252 2253 if (!N->isLeaf()) 2254 OperatorMap[N->getName()] = N->getOperator(); 2255 } 2256 2257 2258 // Emit code to load the child nodes and match their contents recursively. 2259 unsigned OpNo = 0; 2260 bool NodeHasChain = NodeHasProperty (N, SDNPHasChain, ISE); 2261 bool HasChain = PatternHasProperty(N, SDNPHasChain, ISE); 2262 bool HasOutFlag = PatternHasProperty(N, SDNPOutFlag, ISE); 2263 bool EmittedUseCheck = false; 2264 if (HasChain) { 2265 if (NodeHasChain) 2266 OpNo = 1; 2267 if (!isRoot) { 2268 const SDNodeInfo &CInfo = ISE.getSDNodeInfo(N->getOperator()); 2269 // Multiple uses of actual result? 2270 emitCheck(RootName + ".hasOneUse()"); 2271 EmittedUseCheck = true; 2272 if (NodeHasChain) { 2273 // If the immediate use can somehow reach this node through another 2274 // path, then can't fold it either or it will create a cycle. 2275 // e.g. In the following diagram, XX can reach ld through YY. If 2276 // ld is folded into XX, then YY is both a predecessor and a successor 2277 // of XX. 2278 // 2279 // [ld] 2280 // ^ ^ 2281 // | | 2282 // / \--- 2283 // / [YY] 2284 // | ^ 2285 // [XX]-------| 2286 const SDNodeInfo &PInfo = ISE.getSDNodeInfo(P->getOperator()); 2287 if (P != Root || 2288 PInfo.getNumOperands() > 1 || 2289 PInfo.hasProperty(SDNPHasChain) || 2290 PInfo.hasProperty(SDNPInFlag) || 2291 PInfo.hasProperty(SDNPOptInFlag)) { 2292 std::string ParentName(RootName.begin(), RootName.end()-1); 2293 emitCheck("CanBeFoldedBy(" + RootName + ".Val, " + ParentName + 2294 ".Val, N.Val)"); 2295 } 2296 } 2297 } 2298 2299 if (NodeHasChain) { 2300 if (FoundChain) { 2301 emitCheck("(" + ChainName + ".Val == " + RootName + ".Val || " 2302 "IsChainCompatible(" + ChainName + ".Val, " + 2303 RootName + ".Val))"); 2304 OrigChains.push_back(std::make_pair(ChainName, RootName)); 2305 } else 2306 FoundChain = true; 2307 ChainName = "Chain" + ChainSuffix; 2308 emitInit("SDOperand " + ChainName + " = " + RootName + 2309 ".getOperand(0);"); 2310 } 2311 } 2312 2313 // Don't fold any node which reads or writes a flag and has multiple uses. 2314 // FIXME: We really need to separate the concepts of flag and "glue". Those 2315 // real flag results, e.g. X86CMP output, can have multiple uses. 2316 // FIXME: If the optional incoming flag does not exist. Then it is ok to 2317 // fold it. 2318 if (!isRoot && 2319 (PatternHasProperty(N, SDNPInFlag, ISE) || 2320 PatternHasProperty(N, SDNPOptInFlag, ISE) || 2321 PatternHasProperty(N, SDNPOutFlag, ISE))) { 2322 const SDNodeInfo &CInfo = ISE.getSDNodeInfo(N->getOperator()); 2323 if (!EmittedUseCheck) { 2324 // Multiple uses of actual result? 2325 emitCheck(RootName + ".hasOneUse()"); 2326 } 2327 } 2328 2329 // If there is a node predicate for this, emit the call. 2330 if (!N->getPredicateFn().empty()) 2331 emitCheck(N->getPredicateFn() + "(" + RootName + ".Val)"); 2332 2333 2334 // If this is an 'and R, 1234' where the operation is AND/OR and the RHS is 2335 // a constant without a predicate fn that has more that one bit set, handle 2336 // this as a special case. This is usually for targets that have special 2337 // handling of certain large constants (e.g. alpha with it's 8/16/32-bit 2338 // handling stuff). Using these instructions is often far more efficient 2339 // than materializing the constant. Unfortunately, both the instcombiner 2340 // and the dag combiner can often infer that bits are dead, and thus drop 2341 // them from the mask in the dag. For example, it might turn 'AND X, 255' 2342 // into 'AND X, 254' if it knows the low bit is set. Emit code that checks 2343 // to handle this. 2344 if (!N->isLeaf() && 2345 (N->getOperator()->getName() == "and" || 2346 N->getOperator()->getName() == "or") && 2347 N->getChild(1)->isLeaf() && 2348 N->getChild(1)->getPredicateFn().empty()) { 2349 if (IntInit *II = dynamic_cast<IntInit*>(N->getChild(1)->getLeafValue())) { 2350 if (!isPowerOf2_32(II->getValue())) { // Don't bother with single bits. 2351 emitInit("SDOperand " + RootName + "0" + " = " + 2352 RootName + ".getOperand(" + utostr(0) + ");"); 2353 emitInit("SDOperand " + RootName + "1" + " = " + 2354 RootName + ".getOperand(" + utostr(1) + ");"); 2355 2356 emitCheck("isa<ConstantSDNode>(" + RootName + "1)"); 2357 const char *MaskPredicate = N->getOperator()->getName() == "or" 2358 ? "CheckOrMask(" : "CheckAndMask("; 2359 emitCheck(MaskPredicate + RootName + "0, cast<ConstantSDNode>(" + 2360 RootName + "1), " + itostr(II->getValue()) + ")"); 2361 2362 EmitChildMatchCode(Root, N->getChild(0), N, RootName + utostr(0), 2363 ChainSuffix + utostr(0), FoundChain); 2364 return; 2365 } 2366 } 2367 } 2368 2369 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) { 2370 emitInit("SDOperand " + RootName + utostr(OpNo) + " = " + 2371 RootName + ".getOperand(" +utostr(OpNo) + ");"); 2372 2373 EmitChildMatchCode(Root, N->getChild(i), N, RootName + utostr(OpNo), 2374 ChainSuffix + utostr(OpNo), FoundChain); 2375 } 2376 2377 // Handle cases when root is a complex pattern. 2378 const ComplexPattern *CP; 2379 if (isRoot && N->isLeaf() && (CP = NodeGetComplexPattern(N, ISE))) { 2380 std::string Fn = CP->getSelectFunc(); 2381 unsigned NumOps = CP->getNumOperands(); 2382 for (unsigned i = 0; i < NumOps; ++i) { 2383 emitDecl("CPTmp" + utostr(i)); 2384 emitCode("SDOperand CPTmp" + utostr(i) + ";"); 2385 } 2386 if (CP->hasProperty(SDNPHasChain)) { 2387 emitDecl("CPInChain"); 2388 emitDecl("Chain" + ChainSuffix); 2389 emitCode("SDOperand CPInChain;"); 2390 emitCode("SDOperand Chain" + ChainSuffix + ";"); 2391 } 2392 2393 std::string Code = Fn + "(" + RootName; 2394 for (unsigned i = 0; i < NumOps; i++) 2395 Code += ", CPTmp" + utostr(i); 2396 if (CP->hasProperty(SDNPHasChain)) { 2397 ChainName = "Chain" + ChainSuffix; 2398 Code += ", CPInChain, Chain" + ChainSuffix; 2399 } 2400 emitCheck(Code + ")"); 2401 } 2402 } 2403 2404 void EmitChildMatchCode(TreePatternNode *Root, TreePatternNode *Child, 2405 TreePatternNode *Parent, const std::string &RootName, 2406 const std::string &ChainSuffix, bool &FoundChain) { 2407 if (!Child->isLeaf()) { 2408 // If it's not a leaf, recursively match. 2409 const SDNodeInfo &CInfo = ISE.getSDNodeInfo(Child->getOperator()); 2410 emitCheck(RootName + ".getOpcode() == " + 2411 CInfo.getEnumName()); 2412 EmitMatchCode(Root, Child, Parent, RootName, ChainSuffix, FoundChain); 2413 if (NodeHasProperty(Child, SDNPHasChain, ISE)) 2414 FoldedChains.push_back(std::make_pair(RootName, CInfo.getNumResults())); 2415 } else { 2416 // If this child has a name associated with it, capture it in VarMap. If 2417 // we already saw this in the pattern, emit code to verify dagness. 2418 if (!Child->getName().empty()) { 2419 std::string &VarMapEntry = VariableMap[Child->getName()]; 2420 if (VarMapEntry.empty()) { 2421 VarMapEntry = RootName; 2422 } else { 2423 // If we get here, this is a second reference to a specific name. 2424 // Since we already have checked that the first reference is valid, 2425 // we don't have to recursively match it, just check that it's the 2426 // same as the previously named thing. 2427 emitCheck(VarMapEntry + " == " + RootName); 2428 Duplicates.insert(RootName); 2429 return; 2430 } 2431 } 2432 2433 // Handle leaves of various types. 2434 if (DefInit *DI = dynamic_cast<DefInit*>(Child->getLeafValue())) { 2435 Record *LeafRec = DI->getDef(); 2436 if (LeafRec->isSubClassOf("RegisterClass")) { 2437 // Handle register references. Nothing to do here. 2438 } else if (LeafRec->isSubClassOf("Register")) { 2439 // Handle register references. 2440 } else if (LeafRec->isSubClassOf("ComplexPattern")) { 2441 // Handle complex pattern. 2442 const ComplexPattern *CP = NodeGetComplexPattern(Child, ISE); 2443 std::string Fn = CP->getSelectFunc(); 2444 unsigned NumOps = CP->getNumOperands(); 2445 for (unsigned i = 0; i < NumOps; ++i) { 2446 emitDecl("CPTmp" + utostr(i)); 2447 emitCode("SDOperand CPTmp" + utostr(i) + ";"); 2448 } 2449 if (CP->hasProperty(SDNPHasChain)) { 2450 const SDNodeInfo &PInfo = ISE.getSDNodeInfo(Parent->getOperator()); 2451 FoldedChains.push_back(std::make_pair("CPInChain", 2452 PInfo.getNumResults())); 2453 ChainName = "Chain" + ChainSuffix; 2454 emitDecl("CPInChain"); 2455 emitDecl(ChainName); 2456 emitCode("SDOperand CPInChain;"); 2457 emitCode("SDOperand " + ChainName + ";"); 2458 } 2459 2460 std::string Code = Fn + "(" + RootName; 2461 for (unsigned i = 0; i < NumOps; i++) 2462 Code += ", CPTmp" + utostr(i); 2463 if (CP->hasProperty(SDNPHasChain)) 2464 Code += ", CPInChain, Chain" + ChainSuffix; 2465 emitCheck(Code + ")"); 2466 } else if (LeafRec->getName() == "srcvalue") { 2467 // Place holder for SRCVALUE nodes. Nothing to do here. 2468 } else if (LeafRec->isSubClassOf("ValueType")) { 2469 // Make sure this is the specified value type. 2470 emitCheck("cast<VTSDNode>(" + RootName + 2471 ")->getVT() == MVT::" + LeafRec->getName()); 2472 } else if (LeafRec->isSubClassOf("CondCode")) { 2473 // Make sure this is the specified cond code. 2474 emitCheck("cast<CondCodeSDNode>(" + RootName + 2475 ")->get() == ISD::" + LeafRec->getName()); 2476 } else { 2477#ifndef NDEBUG 2478 Child->dump(); 2479 std::cerr << " "; 2480#endif 2481 assert(0 && "Unknown leaf type!"); 2482 } 2483 2484 // If there is a node predicate for this, emit the call. 2485 if (!Child->getPredicateFn().empty()) 2486 emitCheck(Child->getPredicateFn() + "(" + RootName + 2487 ".Val)"); 2488 } else if (IntInit *II = 2489 dynamic_cast<IntInit*>(Child->getLeafValue())) { 2490 emitCheck("isa<ConstantSDNode>(" + RootName + ")"); 2491 unsigned CTmp = TmpNo++; 2492 emitCode("int64_t CN"+utostr(CTmp)+" = cast<ConstantSDNode>("+ 2493 RootName + ")->getSignExtended();"); 2494 2495 emitCheck("CN" + utostr(CTmp) + " == " +itostr(II->getValue())); 2496 } else { 2497#ifndef NDEBUG 2498 Child->dump(); 2499#endif 2500 assert(0 && "Unknown leaf type!"); 2501 } 2502 } 2503 } 2504 2505 /// EmitResultCode - Emit the action for a pattern. Now that it has matched 2506 /// we actually have to build a DAG! 2507 std::vector<std::string> 2508 EmitResultCode(TreePatternNode *N, bool RetSelected, 2509 bool InFlagDecled, bool ResNodeDecled, 2510 bool LikeLeaf = false, bool isRoot = false) { 2511 // List of arguments of getTargetNode() or SelectNodeTo(). 2512 std::vector<std::string> NodeOps; 2513 // This is something selected from the pattern we matched. 2514 if (!N->getName().empty()) { 2515 std::string &Val = VariableMap[N->getName()]; 2516 assert(!Val.empty() && 2517 "Variable referenced but not defined and not caught earlier!"); 2518 if (Val[0] == 'T' && Val[1] == 'm' && Val[2] == 'p') { 2519 // Already selected this operand, just return the tmpval. 2520 NodeOps.push_back(Val); 2521 return NodeOps; 2522 } 2523 2524 const ComplexPattern *CP; 2525 unsigned ResNo = TmpNo++; 2526 if (!N->isLeaf() && N->getOperator()->getName() == "imm") { 2527 assert(N->getExtTypes().size() == 1 && "Multiple types not handled!"); 2528 std::string CastType; 2529 switch (N->getTypeNum(0)) { 2530 default: assert(0 && "Unknown type for constant node!"); 2531 case MVT::i1: CastType = "bool"; break; 2532 case MVT::i8: CastType = "unsigned char"; break; 2533 case MVT::i16: CastType = "unsigned short"; break; 2534 case MVT::i32: CastType = "unsigned"; break; 2535 case MVT::i64: CastType = "uint64_t"; break; 2536 } 2537 emitCode("SDOperand Tmp" + utostr(ResNo) + 2538 " = CurDAG->getTargetConstant(((" + CastType + 2539 ") cast<ConstantSDNode>(" + Val + ")->getValue()), " + 2540 getEnumName(N->getTypeNum(0)) + ");"); 2541 NodeOps.push_back("Tmp" + utostr(ResNo)); 2542 // Add Tmp<ResNo> to VariableMap, so that we don't multiply select this 2543 // value if used multiple times by this pattern result. 2544 Val = "Tmp"+utostr(ResNo); 2545 } else if (!N->isLeaf() && N->getOperator()->getName() == "texternalsym"){ 2546 Record *Op = OperatorMap[N->getName()]; 2547 // Transform ExternalSymbol to TargetExternalSymbol 2548 if (Op && Op->getName() == "externalsym") { 2549 emitCode("SDOperand Tmp" + utostr(ResNo) + " = CurDAG->getTarget" 2550 "ExternalSymbol(cast<ExternalSymbolSDNode>(" + 2551 Val + ")->getSymbol(), " + 2552 getEnumName(N->getTypeNum(0)) + ");"); 2553 NodeOps.push_back("Tmp" + utostr(ResNo)); 2554 // Add Tmp<ResNo> to VariableMap, so that we don't multiply select 2555 // this value if used multiple times by this pattern result. 2556 Val = "Tmp"+utostr(ResNo); 2557 } else { 2558 NodeOps.push_back(Val); 2559 } 2560 } else if (!N->isLeaf() && N->getOperator()->getName() == "tglobaladdr") { 2561 Record *Op = OperatorMap[N->getName()]; 2562 // Transform GlobalAddress to TargetGlobalAddress 2563 if (Op && Op->getName() == "globaladdr") { 2564 emitCode("SDOperand Tmp" + utostr(ResNo) + " = CurDAG->getTarget" 2565 "GlobalAddress(cast<GlobalAddressSDNode>(" + Val + 2566 ")->getGlobal(), " + getEnumName(N->getTypeNum(0)) + 2567 ");"); 2568 NodeOps.push_back("Tmp" + utostr(ResNo)); 2569 // Add Tmp<ResNo> to VariableMap, so that we don't multiply select 2570 // this value if used multiple times by this pattern result. 2571 Val = "Tmp"+utostr(ResNo); 2572 } else { 2573 NodeOps.push_back(Val); 2574 } 2575 } else if (!N->isLeaf() && N->getOperator()->getName() == "texternalsym"){ 2576 NodeOps.push_back(Val); 2577 // Add Tmp<ResNo> to VariableMap, so that we don't multiply select this 2578 // value if used multiple times by this pattern result. 2579 Val = "Tmp"+utostr(ResNo); 2580 } else if (!N->isLeaf() && N->getOperator()->getName() == "tconstpool") { 2581 NodeOps.push_back(Val); 2582 // Add Tmp<ResNo> to VariableMap, so that we don't multiply select this 2583 // value if used multiple times by this pattern result. 2584 Val = "Tmp"+utostr(ResNo); 2585 } else if (N->isLeaf() && (CP = NodeGetComplexPattern(N, ISE))) { 2586 std::string Fn = CP->getSelectFunc(); 2587 for (unsigned i = 0; i < CP->getNumOperands(); ++i) { 2588 emitCode("AddToISelQueue(CPTmp" + utostr(i) + ");"); 2589 NodeOps.push_back("CPTmp" + utostr(i)); 2590 } 2591 } else { 2592 // This node, probably wrapped in a SDNodeXForm, behaves like a leaf 2593 // node even if it isn't one. Don't select it. 2594 if (!LikeLeaf) { 2595 emitCode("AddToISelQueue(" + Val + ");"); 2596 if (isRoot && N->isLeaf()) { 2597 emitCode("ReplaceUses(N, " + Val + ");"); 2598 emitCode("return NULL;"); 2599 } 2600 } 2601 NodeOps.push_back(Val); 2602 } 2603 return NodeOps; 2604 } 2605 if (N->isLeaf()) { 2606 // If this is an explicit register reference, handle it. 2607 if (DefInit *DI = dynamic_cast<DefInit*>(N->getLeafValue())) { 2608 unsigned ResNo = TmpNo++; 2609 if (DI->getDef()->isSubClassOf("Register")) { 2610 emitCode("SDOperand Tmp" + utostr(ResNo) + " = CurDAG->getRegister(" + 2611 ISE.getQualifiedName(DI->getDef()) + ", " + 2612 getEnumName(N->getTypeNum(0)) + ");"); 2613 NodeOps.push_back("Tmp" + utostr(ResNo)); 2614 return NodeOps; 2615 } 2616 } else if (IntInit *II = dynamic_cast<IntInit*>(N->getLeafValue())) { 2617 unsigned ResNo = TmpNo++; 2618 assert(N->getExtTypes().size() == 1 && "Multiple types not handled!"); 2619 emitCode("SDOperand Tmp" + utostr(ResNo) + 2620 " = CurDAG->getTargetConstant(" + itostr(II->getValue()) + 2621 ", " + getEnumName(N->getTypeNum(0)) + ");"); 2622 NodeOps.push_back("Tmp" + utostr(ResNo)); 2623 return NodeOps; 2624 } 2625 2626#ifndef NDEBUG 2627 N->dump(); 2628#endif 2629 assert(0 && "Unknown leaf type!"); 2630 return NodeOps; 2631 } 2632 2633 Record *Op = N->getOperator(); 2634 if (Op->isSubClassOf("Instruction")) { 2635 const CodeGenTarget &CGT = ISE.getTargetInfo(); 2636 CodeGenInstruction &II = CGT.getInstruction(Op->getName()); 2637 const DAGInstruction &Inst = ISE.getInstruction(Op); 2638 TreePattern *InstPat = Inst.getPattern(); 2639 TreePatternNode *InstPatNode = 2640 isRoot ? (InstPat ? InstPat->getOnlyTree() : Pattern) 2641 : (InstPat ? InstPat->getOnlyTree() : NULL); 2642 if (InstPatNode && InstPatNode->getOperator()->getName() == "set") { 2643 InstPatNode = InstPatNode->getChild(1); 2644 } 2645 bool HasVarOps = isRoot && II.hasVariableNumberOfOperands; 2646 bool HasImpInputs = isRoot && Inst.getNumImpOperands() > 0; 2647 bool HasImpResults = isRoot && Inst.getNumImpResults() > 0; 2648 bool NodeHasOptInFlag = isRoot && 2649 PatternHasProperty(Pattern, SDNPOptInFlag, ISE); 2650 bool NodeHasInFlag = isRoot && 2651 PatternHasProperty(Pattern, SDNPInFlag, ISE); 2652 bool NodeHasOutFlag = HasImpResults || (isRoot && 2653 PatternHasProperty(Pattern, SDNPOutFlag, ISE)); 2654 bool NodeHasChain = InstPatNode && 2655 PatternHasProperty(InstPatNode, SDNPHasChain, ISE); 2656 bool InputHasChain = isRoot && 2657 NodeHasProperty(Pattern, SDNPHasChain, ISE); 2658 2659 if (NodeHasOptInFlag) { 2660 emitCode("bool HasInFlag = " 2661 "(N.getOperand(N.getNumOperands()-1).getValueType() == MVT::Flag);"); 2662 } 2663 if (HasVarOps) 2664 emitCode("SmallVector<SDOperand, 8> Ops" + utostr(OpcNo) + ";"); 2665 2666 // How many results is this pattern expected to produce? 2667 unsigned PatResults = 0; 2668 for (unsigned i = 0, e = Pattern->getExtTypes().size(); i != e; i++) { 2669 MVT::ValueType VT = Pattern->getTypeNum(i); 2670 if (VT != MVT::isVoid && VT != MVT::Flag) 2671 PatResults++; 2672 } 2673 2674 if (OrigChains.size() > 0) { 2675 // The original input chain is being ignored. If it is not just 2676 // pointing to the op that's being folded, we should create a 2677 // TokenFactor with it and the chain of the folded op as the new chain. 2678 // We could potentially be doing multiple levels of folding, in that 2679 // case, the TokenFactor can have more operands. 2680 emitCode("SmallVector<SDOperand, 8> InChains;"); 2681 for (unsigned i = 0, e = OrigChains.size(); i < e; ++i) { 2682 emitCode("if (" + OrigChains[i].first + ".Val != " + 2683 OrigChains[i].second + ".Val) {"); 2684 emitCode(" AddToISelQueue(" + OrigChains[i].first + ");"); 2685 emitCode(" InChains.push_back(" + OrigChains[i].first + ");"); 2686 emitCode("}"); 2687 } 2688 emitCode("AddToISelQueue(" + ChainName + ");"); 2689 emitCode("InChains.push_back(" + ChainName + ");"); 2690 emitCode(ChainName + " = CurDAG->getNode(ISD::TokenFactor, MVT::Other, " 2691 "&InChains[0], InChains.size());"); 2692 } 2693 2694 std::vector<std::string> AllOps; 2695 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { 2696 std::vector<std::string> Ops = EmitResultCode(N->getChild(i), 2697 RetSelected, InFlagDecled, ResNodeDecled); 2698 AllOps.insert(AllOps.end(), Ops.begin(), Ops.end()); 2699 } 2700 2701 // Emit all the chain and CopyToReg stuff. 2702 bool ChainEmitted = NodeHasChain; 2703 if (NodeHasChain) 2704 emitCode("AddToISelQueue(" + ChainName + ");"); 2705 if (NodeHasInFlag || HasImpInputs) 2706 EmitInFlagSelectCode(Pattern, "N", ChainEmitted, 2707 InFlagDecled, ResNodeDecled, true); 2708 if (NodeHasOptInFlag || NodeHasInFlag || HasImpInputs) { 2709 if (!InFlagDecled) { 2710 emitCode("SDOperand InFlag(0, 0);"); 2711 InFlagDecled = true; 2712 } 2713 if (NodeHasOptInFlag) { 2714 emitCode("if (HasInFlag) {"); 2715 emitCode(" InFlag = N.getOperand(N.getNumOperands()-1);"); 2716 emitCode(" AddToISelQueue(InFlag);"); 2717 emitCode("}"); 2718 } 2719 } 2720 2721 unsigned NumResults = Inst.getNumResults(); 2722 unsigned ResNo = TmpNo++; 2723 if (!isRoot || InputHasChain || NodeHasChain || NodeHasOutFlag || 2724 NodeHasOptInFlag) { 2725 std::string Code; 2726 std::string Code2; 2727 std::string NodeName; 2728 if (!isRoot) { 2729 NodeName = "Tmp" + utostr(ResNo); 2730 Code2 = "SDOperand " + NodeName + " = SDOperand("; 2731 } else { 2732 NodeName = "ResNode"; 2733 if (!ResNodeDecled) 2734 Code2 = "SDNode *" + NodeName + " = "; 2735 else 2736 Code2 = NodeName + " = "; 2737 } 2738 2739 Code = "CurDAG->getTargetNode(Opc" + utostr(OpcNo); 2740 unsigned OpsNo = OpcNo; 2741 emitOpcode(II.Namespace + "::" + II.TheDef->getName()); 2742 2743 // Output order: results, chain, flags 2744 // Result types. 2745 if (NumResults > 0 && N->getTypeNum(0) != MVT::isVoid) { 2746 Code += ", VT" + utostr(VTNo); 2747 emitVT(getEnumName(N->getTypeNum(0))); 2748 } 2749 if (NodeHasChain) 2750 Code += ", MVT::Other"; 2751 if (NodeHasOutFlag) 2752 Code += ", MVT::Flag"; 2753 2754 // Inputs. 2755 if (HasVarOps) { 2756 for (unsigned i = 0, e = AllOps.size(); i != e; ++i) 2757 emitCode("Ops" + utostr(OpsNo) + ".push_back(" + AllOps[i] + ");"); 2758 AllOps.clear(); 2759 } 2760 2761 if (HasVarOps) { 2762 if (NodeHasInFlag || HasImpInputs) 2763 emitCode("for (unsigned i = 2, e = N.getNumOperands()-1; " 2764 "i != e; ++i) {"); 2765 else if (NodeHasOptInFlag) 2766 emitCode("for (unsigned i = 2, e = N.getNumOperands()-" 2767 "(HasInFlag?1:0); i != e; ++i) {"); 2768 else 2769 emitCode("for (unsigned i = 2, e = N.getNumOperands(); " 2770 "i != e; ++i) {"); 2771 emitCode(" AddToISelQueue(N.getOperand(i));"); 2772 emitCode(" Ops" + utostr(OpsNo) + ".push_back(N.getOperand(i));"); 2773 emitCode("}"); 2774 } 2775 2776 if (NodeHasChain) { 2777 if (HasVarOps) 2778 emitCode("Ops" + utostr(OpsNo) + ".push_back(" + ChainName + ");"); 2779 else 2780 AllOps.push_back(ChainName); 2781 } 2782 2783 if (HasVarOps) { 2784 if (NodeHasInFlag || HasImpInputs) 2785 emitCode("Ops" + utostr(OpsNo) + ".push_back(InFlag);"); 2786 else if (NodeHasOptInFlag) { 2787 emitCode("if (HasInFlag)"); 2788 emitCode(" Ops" + utostr(OpsNo) + ".push_back(InFlag);"); 2789 } 2790 Code += ", &Ops" + utostr(OpsNo) + "[0], Ops" + utostr(OpsNo) + 2791 ".size()"; 2792 } else if (NodeHasInFlag || NodeHasOptInFlag || HasImpInputs) 2793 AllOps.push_back("InFlag"); 2794 2795 unsigned NumOps = AllOps.size(); 2796 if (NumOps) { 2797 if (!NodeHasOptInFlag && NumOps < 4) { 2798 for (unsigned i = 0; i != NumOps; ++i) 2799 Code += ", " + AllOps[i]; 2800 } else { 2801 std::string OpsCode = "SDOperand Ops" + utostr(OpsNo) + "[] = { "; 2802 for (unsigned i = 0; i != NumOps; ++i) { 2803 OpsCode += AllOps[i]; 2804 if (i != NumOps-1) 2805 OpsCode += ", "; 2806 } 2807 emitCode(OpsCode + " };"); 2808 Code += ", Ops" + utostr(OpsNo) + ", "; 2809 if (NodeHasOptInFlag) { 2810 Code += "HasInFlag ? "; 2811 Code += utostr(NumOps) + " : " + utostr(NumOps-1); 2812 } else 2813 Code += utostr(NumOps); 2814 } 2815 } 2816 2817 if (!isRoot) 2818 Code += "), 0"; 2819 emitCode(Code2 + Code + ");"); 2820 2821 if (NodeHasChain) 2822 // Remember which op produces the chain. 2823 if (!isRoot) 2824 emitCode(ChainName + " = SDOperand(" + NodeName + 2825 ".Val, " + utostr(PatResults) + ");"); 2826 else 2827 emitCode(ChainName + " = SDOperand(" + NodeName + 2828 ", " + utostr(PatResults) + ");"); 2829 2830 if (!isRoot) { 2831 NodeOps.push_back("Tmp" + utostr(ResNo)); 2832 return NodeOps; 2833 } 2834 2835 bool NeedReplace = false; 2836 if (NodeHasOutFlag) { 2837 if (!InFlagDecled) { 2838 emitCode("SDOperand InFlag = SDOperand(ResNode, " + 2839 utostr(NumResults + (unsigned)NodeHasChain) + ");"); 2840 InFlagDecled = true; 2841 } else 2842 emitCode("InFlag = SDOperand(ResNode, " + 2843 utostr(NumResults + (unsigned)NodeHasChain) + ");"); 2844 } 2845 2846 if (HasImpResults && EmitCopyFromRegs(N, ResNodeDecled, ChainEmitted)) { 2847 emitCode("ReplaceUses(SDOperand(N.Val, 0), SDOperand(ResNode, 0));"); 2848 NumResults = 1; 2849 } 2850 2851 if (FoldedChains.size() > 0) { 2852 std::string Code; 2853 for (unsigned j = 0, e = FoldedChains.size(); j < e; j++) 2854 emitCode("ReplaceUses(SDOperand(" + 2855 FoldedChains[j].first + ".Val, " + 2856 utostr(FoldedChains[j].second) + "), SDOperand(ResNode, " + 2857 utostr(NumResults) + "));"); 2858 NeedReplace = true; 2859 } 2860 2861 if (NodeHasOutFlag) { 2862 emitCode("ReplaceUses(SDOperand(N.Val, " + 2863 utostr(PatResults + (unsigned)InputHasChain) +"), InFlag);"); 2864 NeedReplace = true; 2865 } 2866 2867 if (NeedReplace) { 2868 for (unsigned i = 0; i < NumResults; i++) 2869 emitCode("ReplaceUses(SDOperand(N.Val, " + 2870 utostr(i) + "), SDOperand(ResNode, " + utostr(i) + "));"); 2871 if (InputHasChain) 2872 emitCode("ReplaceUses(SDOperand(N.Val, " + 2873 utostr(PatResults) + "), SDOperand(" + ChainName + ".Val, " 2874 + ChainName + ".ResNo" + "));"); 2875 } else 2876 RetSelected = true; 2877 2878 // User does not expect the instruction would produce a chain! 2879 if ((!InputHasChain && NodeHasChain) && NodeHasOutFlag) { 2880 ; 2881 } else if (InputHasChain && !NodeHasChain) { 2882 // One of the inner node produces a chain. 2883 if (NodeHasOutFlag) 2884 emitCode("ReplaceUses(SDOperand(N.Val, " + utostr(PatResults+1) + 2885 "), SDOperand(ResNode, N.ResNo-1));"); 2886 for (unsigned i = 0; i < PatResults; ++i) 2887 emitCode("ReplaceUses(SDOperand(N.Val, " + utostr(i) + 2888 "), SDOperand(ResNode, " + utostr(i) + "));"); 2889 emitCode("ReplaceUses(SDOperand(N.Val, " + utostr(PatResults) + 2890 "), " + ChainName + ");"); 2891 RetSelected = false; 2892 } 2893 2894 if (RetSelected) 2895 emitCode("return ResNode;"); 2896 else 2897 emitCode("return NULL;"); 2898 } else { 2899 std::string Code = "return CurDAG->SelectNodeTo(N.Val, Opc" + 2900 utostr(OpcNo); 2901 if (N->getTypeNum(0) != MVT::isVoid) 2902 Code += ", VT" + utostr(VTNo); 2903 if (NodeHasOutFlag) 2904 Code += ", MVT::Flag"; 2905 2906 if (NodeHasInFlag || NodeHasOptInFlag || HasImpInputs) 2907 AllOps.push_back("InFlag"); 2908 2909 unsigned NumOps = AllOps.size(); 2910 if (NumOps) { 2911 if (!NodeHasOptInFlag && NumOps < 4) { 2912 for (unsigned i = 0; i != NumOps; ++i) 2913 Code += ", " + AllOps[i]; 2914 } else { 2915 std::string OpsCode = "SDOperand Ops" + utostr(OpcNo) + "[] = { "; 2916 for (unsigned i = 0; i != NumOps; ++i) { 2917 OpsCode += AllOps[i]; 2918 if (i != NumOps-1) 2919 OpsCode += ", "; 2920 } 2921 emitCode(OpsCode + " };"); 2922 Code += ", Ops" + utostr(OpcNo) + ", "; 2923 Code += utostr(NumOps); 2924 } 2925 } 2926 emitCode(Code + ");"); 2927 emitOpcode(II.Namespace + "::" + II.TheDef->getName()); 2928 if (N->getTypeNum(0) != MVT::isVoid) 2929 emitVT(getEnumName(N->getTypeNum(0))); 2930 } 2931 2932 return NodeOps; 2933 } else if (Op->isSubClassOf("SDNodeXForm")) { 2934 assert(N->getNumChildren() == 1 && "node xform should have one child!"); 2935 // PatLeaf node - the operand may or may not be a leaf node. But it should 2936 // behave like one. 2937 std::vector<std::string> Ops = 2938 EmitResultCode(N->getChild(0), RetSelected, InFlagDecled, 2939 ResNodeDecled, true); 2940 unsigned ResNo = TmpNo++; 2941 emitCode("SDOperand Tmp" + utostr(ResNo) + " = Transform_" + Op->getName() 2942 + "(" + Ops.back() + ".Val);"); 2943 NodeOps.push_back("Tmp" + utostr(ResNo)); 2944 if (isRoot) 2945 emitCode("return Tmp" + utostr(ResNo) + ".Val;"); 2946 return NodeOps; 2947 } else { 2948 N->dump(); 2949 std::cerr << "\n"; 2950 throw std::string("Unknown node in result pattern!"); 2951 } 2952 } 2953 2954 /// InsertOneTypeCheck - Insert a type-check for an unresolved type in 'Pat' 2955 /// and add it to the tree. 'Pat' and 'Other' are isomorphic trees except that 2956 /// 'Pat' may be missing types. If we find an unresolved type to add a check 2957 /// for, this returns true otherwise false if Pat has all types. 2958 bool InsertOneTypeCheck(TreePatternNode *Pat, TreePatternNode *Other, 2959 const std::string &Prefix, bool isRoot = false) { 2960 // Did we find one? 2961 if (Pat->getExtTypes() != Other->getExtTypes()) { 2962 // Move a type over from 'other' to 'pat'. 2963 Pat->setTypes(Other->getExtTypes()); 2964 // The top level node type is checked outside of the select function. 2965 if (!isRoot) 2966 emitCheck(Prefix + ".Val->getValueType(0) == " + 2967 getName(Pat->getTypeNum(0))); 2968 return true; 2969 } 2970 2971 unsigned OpNo = 2972 (unsigned) NodeHasProperty(Pat, SDNPHasChain, ISE); 2973 for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i, ++OpNo) 2974 if (InsertOneTypeCheck(Pat->getChild(i), Other->getChild(i), 2975 Prefix + utostr(OpNo))) 2976 return true; 2977 return false; 2978 } 2979 2980private: 2981 /// EmitInFlagSelectCode - Emit the flag operands for the DAG that is 2982 /// being built. 2983 void EmitInFlagSelectCode(TreePatternNode *N, const std::string &RootName, 2984 bool &ChainEmitted, bool &InFlagDecled, 2985 bool &ResNodeDecled, bool isRoot = false) { 2986 const CodeGenTarget &T = ISE.getTargetInfo(); 2987 unsigned OpNo = 2988 (unsigned) NodeHasProperty(N, SDNPHasChain, ISE); 2989 bool HasInFlag = NodeHasProperty(N, SDNPInFlag, ISE); 2990 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) { 2991 TreePatternNode *Child = N->getChild(i); 2992 if (!Child->isLeaf()) { 2993 EmitInFlagSelectCode(Child, RootName + utostr(OpNo), ChainEmitted, 2994 InFlagDecled, ResNodeDecled); 2995 } else { 2996 if (DefInit *DI = dynamic_cast<DefInit*>(Child->getLeafValue())) { 2997 if (!Child->getName().empty()) { 2998 std::string Name = RootName + utostr(OpNo); 2999 if (Duplicates.find(Name) != Duplicates.end()) 3000 // A duplicate! Do not emit a copy for this node. 3001 continue; 3002 } 3003 3004 Record *RR = DI->getDef(); 3005 if (RR->isSubClassOf("Register")) { 3006 MVT::ValueType RVT = getRegisterValueType(RR, T); 3007 if (RVT == MVT::Flag) { 3008 if (!InFlagDecled) { 3009 emitCode("SDOperand InFlag = " + RootName + utostr(OpNo) + ";"); 3010 InFlagDecled = true; 3011 } else 3012 emitCode("InFlag = " + RootName + utostr(OpNo) + ";"); 3013 emitCode("AddToISelQueue(InFlag);"); 3014 } else { 3015 if (!ChainEmitted) { 3016 emitCode("SDOperand Chain = CurDAG->getEntryNode();"); 3017 ChainName = "Chain"; 3018 ChainEmitted = true; 3019 } 3020 emitCode("AddToISelQueue(" + RootName + utostr(OpNo) + ");"); 3021 if (!InFlagDecled) { 3022 emitCode("SDOperand InFlag(0, 0);"); 3023 InFlagDecled = true; 3024 } 3025 std::string Decl = (!ResNodeDecled) ? "SDNode *" : ""; 3026 emitCode(Decl + "ResNode = CurDAG->getCopyToReg(" + ChainName + 3027 ", " + ISE.getQualifiedName(RR) + 3028 ", " + RootName + utostr(OpNo) + ", InFlag).Val;"); 3029 ResNodeDecled = true; 3030 emitCode(ChainName + " = SDOperand(ResNode, 0);"); 3031 emitCode("InFlag = SDOperand(ResNode, 1);"); 3032 } 3033 } 3034 } 3035 } 3036 } 3037 3038 if (HasInFlag) { 3039 if (!InFlagDecled) { 3040 emitCode("SDOperand InFlag = " + RootName + 3041 ".getOperand(" + utostr(OpNo) + ");"); 3042 InFlagDecled = true; 3043 } else 3044 emitCode("InFlag = " + RootName + 3045 ".getOperand(" + utostr(OpNo) + ");"); 3046 emitCode("AddToISelQueue(InFlag);"); 3047 } 3048 } 3049 3050 /// EmitCopyFromRegs - Emit code to copy result to physical registers 3051 /// as specified by the instruction. It returns true if any copy is 3052 /// emitted. 3053 bool EmitCopyFromRegs(TreePatternNode *N, bool &ResNodeDecled, 3054 bool &ChainEmitted) { 3055 bool RetVal = false; 3056 Record *Op = N->getOperator(); 3057 if (Op->isSubClassOf("Instruction")) { 3058 const DAGInstruction &Inst = ISE.getInstruction(Op); 3059 const CodeGenTarget &CGT = ISE.getTargetInfo(); 3060 unsigned NumImpResults = Inst.getNumImpResults(); 3061 for (unsigned i = 0; i < NumImpResults; i++) { 3062 Record *RR = Inst.getImpResult(i); 3063 if (RR->isSubClassOf("Register")) { 3064 MVT::ValueType RVT = getRegisterValueType(RR, CGT); 3065 if (RVT != MVT::Flag) { 3066 if (!ChainEmitted) { 3067 emitCode("SDOperand Chain = CurDAG->getEntryNode();"); 3068 ChainEmitted = true; 3069 ChainName = "Chain"; 3070 } 3071 std::string Decl = (!ResNodeDecled) ? "SDNode *" : ""; 3072 emitCode(Decl + "ResNode = CurDAG->getCopyFromReg(" + ChainName + 3073 ", " + ISE.getQualifiedName(RR) + ", " + getEnumName(RVT) + 3074 ", InFlag).Val;"); 3075 ResNodeDecled = true; 3076 emitCode(ChainName + " = SDOperand(ResNode, 1);"); 3077 emitCode("InFlag = SDOperand(ResNode, 2);"); 3078 RetVal = true; 3079 } 3080 } 3081 } 3082 } 3083 return RetVal; 3084 } 3085}; 3086 3087/// EmitCodeForPattern - Given a pattern to match, emit code to the specified 3088/// stream to match the pattern, and generate the code for the match if it 3089/// succeeds. Returns true if the pattern is not guaranteed to match. 3090void DAGISelEmitter::GenerateCodeForPattern(PatternToMatch &Pattern, 3091 std::vector<std::pair<unsigned, std::string> > &GeneratedCode, 3092 std::set<std::string> &GeneratedDecl, 3093 std::vector<std::string> &TargetOpcodes, 3094 std::vector<std::string> &TargetVTs) { 3095 PatternCodeEmitter Emitter(*this, Pattern.getPredicates(), 3096 Pattern.getSrcPattern(), Pattern.getDstPattern(), 3097 GeneratedCode, GeneratedDecl, 3098 TargetOpcodes, TargetVTs); 3099 3100 // Emit the matcher, capturing named arguments in VariableMap. 3101 bool FoundChain = false; 3102 Emitter.EmitMatchCode(Pattern.getSrcPattern(), Pattern.getSrcPattern(), NULL, 3103 "N", "", FoundChain); 3104 3105 // TP - Get *SOME* tree pattern, we don't care which. 3106 TreePattern &TP = *PatternFragments.begin()->second; 3107 3108 // At this point, we know that we structurally match the pattern, but the 3109 // types of the nodes may not match. Figure out the fewest number of type 3110 // comparisons we need to emit. For example, if there is only one integer 3111 // type supported by a target, there should be no type comparisons at all for 3112 // integer patterns! 3113 // 3114 // To figure out the fewest number of type checks needed, clone the pattern, 3115 // remove the types, then perform type inference on the pattern as a whole. 3116 // If there are unresolved types, emit an explicit check for those types, 3117 // apply the type to the tree, then rerun type inference. Iterate until all 3118 // types are resolved. 3119 // 3120 TreePatternNode *Pat = Pattern.getSrcPattern()->clone(); 3121 RemoveAllTypes(Pat); 3122 3123 do { 3124 // Resolve/propagate as many types as possible. 3125 try { 3126 bool MadeChange = true; 3127 while (MadeChange) 3128 MadeChange = Pat->ApplyTypeConstraints(TP, 3129 true/*Ignore reg constraints*/); 3130 } catch (...) { 3131 assert(0 && "Error: could not find consistent types for something we" 3132 " already decided was ok!"); 3133 abort(); 3134 } 3135 3136 // Insert a check for an unresolved type and add it to the tree. If we find 3137 // an unresolved type to add a check for, this returns true and we iterate, 3138 // otherwise we are done. 3139 } while (Emitter.InsertOneTypeCheck(Pat, Pattern.getSrcPattern(), "N", true)); 3140 3141 Emitter.EmitResultCode(Pattern.getDstPattern(), 3142 false, false, false, false, true); 3143 delete Pat; 3144} 3145 3146/// EraseCodeLine - Erase one code line from all of the patterns. If removing 3147/// a line causes any of them to be empty, remove them and return true when 3148/// done. 3149static bool EraseCodeLine(std::vector<std::pair<PatternToMatch*, 3150 std::vector<std::pair<unsigned, std::string> > > > 3151 &Patterns) { 3152 bool ErasedPatterns = false; 3153 for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { 3154 Patterns[i].second.pop_back(); 3155 if (Patterns[i].second.empty()) { 3156 Patterns.erase(Patterns.begin()+i); 3157 --i; --e; 3158 ErasedPatterns = true; 3159 } 3160 } 3161 return ErasedPatterns; 3162} 3163 3164/// EmitPatterns - Emit code for at least one pattern, but try to group common 3165/// code together between the patterns. 3166void DAGISelEmitter::EmitPatterns(std::vector<std::pair<PatternToMatch*, 3167 std::vector<std::pair<unsigned, std::string> > > > 3168 &Patterns, unsigned Indent, 3169 std::ostream &OS) { 3170 typedef std::pair<unsigned, std::string> CodeLine; 3171 typedef std::vector<CodeLine> CodeList; 3172 typedef std::vector<std::pair<PatternToMatch*, CodeList> > PatternList; 3173 3174 if (Patterns.empty()) return; 3175 3176 // Figure out how many patterns share the next code line. Explicitly copy 3177 // FirstCodeLine so that we don't invalidate a reference when changing 3178 // Patterns. 3179 const CodeLine FirstCodeLine = Patterns.back().second.back(); 3180 unsigned LastMatch = Patterns.size()-1; 3181 while (LastMatch != 0 && Patterns[LastMatch-1].second.back() == FirstCodeLine) 3182 --LastMatch; 3183 3184 // If not all patterns share this line, split the list into two pieces. The 3185 // first chunk will use this line, the second chunk won't. 3186 if (LastMatch != 0) { 3187 PatternList Shared(Patterns.begin()+LastMatch, Patterns.end()); 3188 PatternList Other(Patterns.begin(), Patterns.begin()+LastMatch); 3189 3190 // FIXME: Emit braces? 3191 if (Shared.size() == 1) { 3192 PatternToMatch &Pattern = *Shared.back().first; 3193 OS << "\n" << std::string(Indent, ' ') << "// Pattern: "; 3194 Pattern.getSrcPattern()->print(OS); 3195 OS << "\n" << std::string(Indent, ' ') << "// Emits: "; 3196 Pattern.getDstPattern()->print(OS); 3197 OS << "\n"; 3198 unsigned AddedComplexity = Pattern.getAddedComplexity(); 3199 OS << std::string(Indent, ' ') << "// Pattern complexity = " 3200 << getPatternSize(Pattern.getSrcPattern(), *this) + AddedComplexity 3201 << " cost = " 3202 << getResultPatternCost(Pattern.getDstPattern(), *this) 3203 << " size = " 3204 << getResultPatternSize(Pattern.getDstPattern(), *this) << "\n"; 3205 } 3206 if (FirstCodeLine.first != 1) { 3207 OS << std::string(Indent, ' ') << "{\n"; 3208 Indent += 2; 3209 } 3210 EmitPatterns(Shared, Indent, OS); 3211 if (FirstCodeLine.first != 1) { 3212 Indent -= 2; 3213 OS << std::string(Indent, ' ') << "}\n"; 3214 } 3215 3216 if (Other.size() == 1) { 3217 PatternToMatch &Pattern = *Other.back().first; 3218 OS << "\n" << std::string(Indent, ' ') << "// Pattern: "; 3219 Pattern.getSrcPattern()->print(OS); 3220 OS << "\n" << std::string(Indent, ' ') << "// Emits: "; 3221 Pattern.getDstPattern()->print(OS); 3222 OS << "\n"; 3223 unsigned AddedComplexity = Pattern.getAddedComplexity(); 3224 OS << std::string(Indent, ' ') << "// Pattern complexity = " 3225 << getPatternSize(Pattern.getSrcPattern(), *this) + AddedComplexity 3226 << " cost = " 3227 << getResultPatternCost(Pattern.getDstPattern(), *this) 3228 << " size = " 3229 << getResultPatternSize(Pattern.getDstPattern(), *this) << "\n"; 3230 } 3231 EmitPatterns(Other, Indent, OS); 3232 return; 3233 } 3234 3235 // Remove this code from all of the patterns that share it. 3236 bool ErasedPatterns = EraseCodeLine(Patterns); 3237 3238 bool isPredicate = FirstCodeLine.first == 1; 3239 3240 // Otherwise, every pattern in the list has this line. Emit it. 3241 if (!isPredicate) { 3242 // Normal code. 3243 OS << std::string(Indent, ' ') << FirstCodeLine.second << "\n"; 3244 } else { 3245 OS << std::string(Indent, ' ') << "if (" << FirstCodeLine.second; 3246 3247 // If the next code line is another predicate, and if all of the pattern 3248 // in this group share the same next line, emit it inline now. Do this 3249 // until we run out of common predicates. 3250 while (!ErasedPatterns && Patterns.back().second.back().first == 1) { 3251 // Check that all of fhe patterns in Patterns end with the same predicate. 3252 bool AllEndWithSamePredicate = true; 3253 for (unsigned i = 0, e = Patterns.size(); i != e; ++i) 3254 if (Patterns[i].second.back() != Patterns.back().second.back()) { 3255 AllEndWithSamePredicate = false; 3256 break; 3257 } 3258 // If all of the predicates aren't the same, we can't share them. 3259 if (!AllEndWithSamePredicate) break; 3260 3261 // Otherwise we can. Emit it shared now. 3262 OS << " &&\n" << std::string(Indent+4, ' ') 3263 << Patterns.back().second.back().second; 3264 ErasedPatterns = EraseCodeLine(Patterns); 3265 } 3266 3267 OS << ") {\n"; 3268 Indent += 2; 3269 } 3270 3271 EmitPatterns(Patterns, Indent, OS); 3272 3273 if (isPredicate) 3274 OS << std::string(Indent-2, ' ') << "}\n"; 3275} 3276 3277 3278 3279namespace { 3280 /// CompareByRecordName - An ordering predicate that implements less-than by 3281 /// comparing the names records. 3282 struct CompareByRecordName { 3283 bool operator()(const Record *LHS, const Record *RHS) const { 3284 // Sort by name first. 3285 if (LHS->getName() < RHS->getName()) return true; 3286 // If both names are equal, sort by pointer. 3287 return LHS->getName() == RHS->getName() && LHS < RHS; 3288 } 3289 }; 3290} 3291 3292void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) { 3293 std::string InstNS = Target.inst_begin()->second.Namespace; 3294 if (!InstNS.empty()) InstNS += "::"; 3295 3296 // Group the patterns by their top-level opcodes. 3297 std::map<Record*, std::vector<PatternToMatch*>, 3298 CompareByRecordName> PatternsByOpcode; 3299 // All unique target node emission functions. 3300 std::map<std::string, unsigned> EmitFunctions; 3301 for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) { 3302 TreePatternNode *Node = PatternsToMatch[i].getSrcPattern(); 3303 if (!Node->isLeaf()) { 3304 PatternsByOpcode[Node->getOperator()].push_back(&PatternsToMatch[i]); 3305 } else { 3306 const ComplexPattern *CP; 3307 if (IntInit *II = 3308 dynamic_cast<IntInit*>(Node->getLeafValue())) { 3309 PatternsByOpcode[getSDNodeNamed("imm")].push_back(&PatternsToMatch[i]); 3310 } else if ((CP = NodeGetComplexPattern(Node, *this))) { 3311 std::vector<Record*> OpNodes = CP->getRootNodes(); 3312 for (unsigned j = 0, e = OpNodes.size(); j != e; j++) { 3313 PatternsByOpcode[OpNodes[j]] 3314 .insert(PatternsByOpcode[OpNodes[j]].begin(), &PatternsToMatch[i]); 3315 } 3316 } else { 3317 std::cerr << "Unrecognized opcode '"; 3318 Node->dump(); 3319 std::cerr << "' on tree pattern '"; 3320 std::cerr << 3321 PatternsToMatch[i].getDstPattern()->getOperator()->getName(); 3322 std::cerr << "'!\n"; 3323 exit(1); 3324 } 3325 } 3326 } 3327 3328 // For each opcode, there might be multiple select functions, one per 3329 // ValueType of the node (or its first operand if it doesn't produce a 3330 // non-chain result. 3331 std::map<std::string, std::vector<std::string> > OpcodeVTMap; 3332 3333 // Emit one Select_* method for each top-level opcode. We do this instead of 3334 // emitting one giant switch statement to support compilers where this will 3335 // result in the recursive functions taking less stack space. 3336 for (std::map<Record*, std::vector<PatternToMatch*>, 3337 CompareByRecordName>::iterator PBOI = PatternsByOpcode.begin(), 3338 E = PatternsByOpcode.end(); PBOI != E; ++PBOI) { 3339 const std::string &OpName = PBOI->first->getName(); 3340 const SDNodeInfo &OpcodeInfo = getSDNodeInfo(PBOI->first); 3341 std::vector<PatternToMatch*> &PatternsOfOp = PBOI->second; 3342 assert(!PatternsOfOp.empty() && "No patterns but map has entry?"); 3343 3344 // We want to emit all of the matching code now. However, we want to emit 3345 // the matches in order of minimal cost. Sort the patterns so the least 3346 // cost one is at the start. 3347 std::stable_sort(PatternsOfOp.begin(), PatternsOfOp.end(), 3348 PatternSortingPredicate(*this)); 3349 3350 // Split them into groups by type. 3351 std::map<MVT::ValueType, std::vector<PatternToMatch*> > PatternsByType; 3352 for (unsigned i = 0, e = PatternsOfOp.size(); i != e; ++i) { 3353 PatternToMatch *Pat = PatternsOfOp[i]; 3354 TreePatternNode *SrcPat = Pat->getSrcPattern(); 3355 if (OpcodeInfo.getNumResults() == 0 && SrcPat->getNumChildren() > 0) 3356 SrcPat = SrcPat->getChild(0); 3357 MVT::ValueType VT = SrcPat->getTypeNum(0); 3358 std::map<MVT::ValueType, std::vector<PatternToMatch*> >::iterator TI = 3359 PatternsByType.find(VT); 3360 if (TI != PatternsByType.end()) 3361 TI->second.push_back(Pat); 3362 else { 3363 std::vector<PatternToMatch*> PVec; 3364 PVec.push_back(Pat); 3365 PatternsByType.insert(std::make_pair(VT, PVec)); 3366 } 3367 } 3368 3369 for (std::map<MVT::ValueType, std::vector<PatternToMatch*> >::iterator 3370 II = PatternsByType.begin(), EE = PatternsByType.end(); II != EE; 3371 ++II) { 3372 MVT::ValueType OpVT = II->first; 3373 std::vector<PatternToMatch*> &Patterns = II->second; 3374 typedef std::vector<std::pair<unsigned,std::string> > CodeList; 3375 typedef std::vector<std::pair<unsigned,std::string> >::iterator CodeListI; 3376 3377 std::vector<std::pair<PatternToMatch*, CodeList> > CodeForPatterns; 3378 std::vector<std::vector<std::string> > PatternOpcodes; 3379 std::vector<std::vector<std::string> > PatternVTs; 3380 std::vector<std::set<std::string> > PatternDecls; 3381 for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { 3382 CodeList GeneratedCode; 3383 std::set<std::string> GeneratedDecl; 3384 std::vector<std::string> TargetOpcodes; 3385 std::vector<std::string> TargetVTs; 3386 GenerateCodeForPattern(*Patterns[i], GeneratedCode, GeneratedDecl, 3387 TargetOpcodes, TargetVTs); 3388 CodeForPatterns.push_back(std::make_pair(Patterns[i], GeneratedCode)); 3389 PatternDecls.push_back(GeneratedDecl); 3390 PatternOpcodes.push_back(TargetOpcodes); 3391 PatternVTs.push_back(TargetVTs); 3392 } 3393 3394 // Scan the code to see if all of the patterns are reachable and if it is 3395 // possible that the last one might not match. 3396 bool mightNotMatch = true; 3397 for (unsigned i = 0, e = CodeForPatterns.size(); i != e; ++i) { 3398 CodeList &GeneratedCode = CodeForPatterns[i].second; 3399 mightNotMatch = false; 3400 3401 for (unsigned j = 0, e = GeneratedCode.size(); j != e; ++j) { 3402 if (GeneratedCode[j].first == 1) { // predicate. 3403 mightNotMatch = true; 3404 break; 3405 } 3406 } 3407 3408 // If this pattern definitely matches, and if it isn't the last one, the 3409 // patterns after it CANNOT ever match. Error out. 3410 if (mightNotMatch == false && i != CodeForPatterns.size()-1) { 3411 std::cerr << "Pattern '"; 3412 CodeForPatterns[i].first->getSrcPattern()->print(std::cerr); 3413 std::cerr << "' is impossible to select!\n"; 3414 exit(1); 3415 } 3416 } 3417 3418 // Factor target node emission code (emitted by EmitResultCode) into 3419 // separate functions. Uniquing and share them among all instruction 3420 // selection routines. 3421 for (unsigned i = 0, e = CodeForPatterns.size(); i != e; ++i) { 3422 CodeList &GeneratedCode = CodeForPatterns[i].second; 3423 std::vector<std::string> &TargetOpcodes = PatternOpcodes[i]; 3424 std::vector<std::string> &TargetVTs = PatternVTs[i]; 3425 std::set<std::string> Decls = PatternDecls[i]; 3426 std::vector<std::string> AddedInits; 3427 int CodeSize = (int)GeneratedCode.size(); 3428 int LastPred = -1; 3429 for (int j = CodeSize-1; j >= 0; --j) { 3430 if (LastPred == -1 && GeneratedCode[j].first == 1) 3431 LastPred = j; 3432 else if (LastPred != -1 && GeneratedCode[j].first == 2) 3433 AddedInits.push_back(GeneratedCode[j].second); 3434 } 3435 3436 std::string CalleeCode = "(const SDOperand &N"; 3437 std::string CallerCode = "(N"; 3438 for (unsigned j = 0, e = TargetOpcodes.size(); j != e; ++j) { 3439 CalleeCode += ", unsigned Opc" + utostr(j); 3440 CallerCode += ", " + TargetOpcodes[j]; 3441 } 3442 for (unsigned j = 0, e = TargetVTs.size(); j != e; ++j) { 3443 CalleeCode += ", MVT::ValueType VT" + utostr(j); 3444 CallerCode += ", " + TargetVTs[j]; 3445 } 3446 for (std::set<std::string>::iterator 3447 I = Decls.begin(), E = Decls.end(); I != E; ++I) { 3448 std::string Name = *I; 3449 CalleeCode += ", SDOperand &" + Name; 3450 CallerCode += ", " + Name; 3451 } 3452 CallerCode += ");"; 3453 CalleeCode += ") "; 3454 // Prevent emission routines from being inlined to reduce selection 3455 // routines stack frame sizes. 3456 CalleeCode += "DISABLE_INLINE "; 3457 CalleeCode += "{\n"; 3458 3459 for (std::vector<std::string>::const_reverse_iterator 3460 I = AddedInits.rbegin(), E = AddedInits.rend(); I != E; ++I) 3461 CalleeCode += " " + *I + "\n"; 3462 3463 for (int j = LastPred+1; j < CodeSize; ++j) 3464 CalleeCode += " " + GeneratedCode[j].second + "\n"; 3465 for (int j = LastPred+1; j < CodeSize; ++j) 3466 GeneratedCode.pop_back(); 3467 CalleeCode += "}\n"; 3468 3469 // Uniquing the emission routines. 3470 unsigned EmitFuncNum; 3471 std::map<std::string, unsigned>::iterator EFI = 3472 EmitFunctions.find(CalleeCode); 3473 if (EFI != EmitFunctions.end()) { 3474 EmitFuncNum = EFI->second; 3475 } else { 3476 EmitFuncNum = EmitFunctions.size(); 3477 EmitFunctions.insert(std::make_pair(CalleeCode, EmitFuncNum)); 3478 OS << "SDNode *Emit_" << utostr(EmitFuncNum) << CalleeCode; 3479 } 3480 3481 // Replace the emission code within selection routines with calls to the 3482 // emission functions. 3483 CallerCode = "return Emit_" + utostr(EmitFuncNum) + CallerCode; 3484 GeneratedCode.push_back(std::make_pair(false, CallerCode)); 3485 } 3486 3487 // Print function. 3488 std::string OpVTStr = (OpVT != MVT::isVoid && OpVT != MVT::iPTR) 3489 ? getEnumName(OpVT).substr(5) : "" ; 3490 std::map<std::string, std::vector<std::string> >::iterator OpVTI = 3491 OpcodeVTMap.find(OpName); 3492 if (OpVTI == OpcodeVTMap.end()) { 3493 std::vector<std::string> VTSet; 3494 VTSet.push_back(OpVTStr); 3495 OpcodeVTMap.insert(std::make_pair(OpName, VTSet)); 3496 } else 3497 OpVTI->second.push_back(OpVTStr); 3498 3499 OS << "SDNode *Select_" << OpName << (OpVTStr != "" ? "_" : "") 3500 << OpVTStr << "(const SDOperand &N) {\n"; 3501 3502 // Loop through and reverse all of the CodeList vectors, as we will be 3503 // accessing them from their logical front, but accessing the end of a 3504 // vector is more efficient. 3505 for (unsigned i = 0, e = CodeForPatterns.size(); i != e; ++i) { 3506 CodeList &GeneratedCode = CodeForPatterns[i].second; 3507 std::reverse(GeneratedCode.begin(), GeneratedCode.end()); 3508 } 3509 3510 // Next, reverse the list of patterns itself for the same reason. 3511 std::reverse(CodeForPatterns.begin(), CodeForPatterns.end()); 3512 3513 // Emit all of the patterns now, grouped together to share code. 3514 EmitPatterns(CodeForPatterns, 2, OS); 3515 3516 // If the last pattern has predicates (which could fail) emit code to 3517 // catch the case where nothing handles a pattern. 3518 if (mightNotMatch) { 3519 OS << " std::cerr << \"Cannot yet select: \";\n"; 3520 if (OpcodeInfo.getEnumName() != "ISD::INTRINSIC_W_CHAIN" && 3521 OpcodeInfo.getEnumName() != "ISD::INTRINSIC_WO_CHAIN" && 3522 OpcodeInfo.getEnumName() != "ISD::INTRINSIC_VOID") { 3523 OS << " N.Val->dump(CurDAG);\n"; 3524 } else { 3525 OS << " unsigned iid = cast<ConstantSDNode>(N.getOperand(" 3526 "N.getOperand(0).getValueType() == MVT::Other))->getValue();\n" 3527 << " std::cerr << \"intrinsic %\"<< " 3528 "Intrinsic::getName((Intrinsic::ID)iid);\n"; 3529 } 3530 OS << " std::cerr << '\\n';\n" 3531 << " abort();\n" 3532 << " return NULL;\n"; 3533 } 3534 OS << "}\n\n"; 3535 } 3536 } 3537 3538 // Emit boilerplate. 3539 OS << "SDNode *Select_INLINEASM(SDOperand N) {\n" 3540 << " std::vector<SDOperand> Ops(N.Val->op_begin(), N.Val->op_end());\n" 3541 << " AddToISelQueue(N.getOperand(0)); // Select the chain.\n\n" 3542 << " // Select the flag operand.\n" 3543 << " if (Ops.back().getValueType() == MVT::Flag)\n" 3544 << " AddToISelQueue(Ops.back());\n" 3545 << " SelectInlineAsmMemoryOperands(Ops, *CurDAG);\n" 3546 << " std::vector<MVT::ValueType> VTs;\n" 3547 << " VTs.push_back(MVT::Other);\n" 3548 << " VTs.push_back(MVT::Flag);\n" 3549 << " SDOperand New = CurDAG->getNode(ISD::INLINEASM, VTs, &Ops[0], " 3550 "Ops.size());\n" 3551 << " return New.Val;\n" 3552 << "}\n\n"; 3553 3554 OS << "// The main instruction selector code.\n" 3555 << "SDNode *SelectCode(SDOperand N) {\n" 3556 << " if (N.getOpcode() >= ISD::BUILTIN_OP_END &&\n" 3557 << " N.getOpcode() < (ISD::BUILTIN_OP_END+" << InstNS 3558 << "INSTRUCTION_LIST_END)) {\n" 3559 << " return NULL; // Already selected.\n" 3560 << " }\n\n" 3561 << " switch (N.getOpcode()) {\n" 3562 << " default: break;\n" 3563 << " case ISD::EntryToken: // These leaves remain the same.\n" 3564 << " case ISD::BasicBlock:\n" 3565 << " case ISD::Register:\n" 3566 << " case ISD::HANDLENODE:\n" 3567 << " case ISD::TargetConstant:\n" 3568 << " case ISD::TargetConstantPool:\n" 3569 << " case ISD::TargetFrameIndex:\n" 3570 << " case ISD::TargetJumpTable:\n" 3571 << " case ISD::TargetGlobalAddress: {\n" 3572 << " return NULL;\n" 3573 << " }\n" 3574 << " case ISD::AssertSext:\n" 3575 << " case ISD::AssertZext: {\n" 3576 << " AddToISelQueue(N.getOperand(0));\n" 3577 << " ReplaceUses(N, N.getOperand(0));\n" 3578 << " return NULL;\n" 3579 << " }\n" 3580 << " case ISD::TokenFactor:\n" 3581 << " case ISD::CopyFromReg:\n" 3582 << " case ISD::CopyToReg: {\n" 3583 << " for (unsigned i = 0, e = N.getNumOperands(); i != e; ++i)\n" 3584 << " AddToISelQueue(N.getOperand(i));\n" 3585 << " return NULL;\n" 3586 << " }\n" 3587 << " case ISD::INLINEASM: return Select_INLINEASM(N);\n"; 3588 3589 3590 // Loop over all of the case statements, emiting a call to each method we 3591 // emitted above. 3592 for (std::map<Record*, std::vector<PatternToMatch*>, 3593 CompareByRecordName>::iterator PBOI = PatternsByOpcode.begin(), 3594 E = PatternsByOpcode.end(); PBOI != E; ++PBOI) { 3595 const SDNodeInfo &OpcodeInfo = getSDNodeInfo(PBOI->first); 3596 const std::string &OpName = PBOI->first->getName(); 3597 // Potentially multiple versions of select for this opcode. One for each 3598 // ValueType of the node (or its first true operand if it doesn't produce a 3599 // result. 3600 std::map<std::string, std::vector<std::string> >::iterator OpVTI = 3601 OpcodeVTMap.find(OpName); 3602 std::vector<std::string> &OpVTs = OpVTI->second; 3603 OS << " case " << OpcodeInfo.getEnumName() << ": {\n"; 3604 if (OpVTs.size() == 1) { 3605 std::string &VTStr = OpVTs[0]; 3606 OS << " return Select_" << OpName 3607 << (VTStr != "" ? "_" : "") << VTStr << "(N);\n"; 3608 } else { 3609 if (OpcodeInfo.getNumResults()) 3610 OS << " MVT::ValueType NVT = N.Val->getValueType(0);\n"; 3611 else if (OpcodeInfo.hasProperty(SDNPHasChain)) 3612 OS << " MVT::ValueType NVT = (N.getNumOperands() > 1) ?" 3613 << " N.getOperand(1).Val->getValueType(0) : MVT::isVoid;\n"; 3614 else 3615 OS << " MVT::ValueType NVT = (N.getNumOperands() > 0) ?" 3616 << " N.getOperand(0).Val->getValueType(0) : MVT::isVoid;\n"; 3617 int Default = -1; 3618 OS << " switch (NVT) {\n"; 3619 for (unsigned i = 0, e = OpVTs.size(); i < e; ++i) { 3620 std::string &VTStr = OpVTs[i]; 3621 if (VTStr == "") { 3622 Default = i; 3623 continue; 3624 } 3625 OS << " case MVT::" << VTStr << ":\n" 3626 << " return Select_" << OpName 3627 << "_" << VTStr << "(N);\n"; 3628 } 3629 OS << " default:\n"; 3630 if (Default != -1) 3631 OS << " return Select_" << OpName << "(N);\n"; 3632 else 3633 OS << " break;\n"; 3634 OS << " }\n"; 3635 OS << " break;\n"; 3636 } 3637 OS << " }\n"; 3638 } 3639 3640 OS << " } // end of big switch.\n\n" 3641 << " std::cerr << \"Cannot yet select: \";\n" 3642 << " if (N.getOpcode() != ISD::INTRINSIC_W_CHAIN &&\n" 3643 << " N.getOpcode() != ISD::INTRINSIC_WO_CHAIN &&\n" 3644 << " N.getOpcode() != ISD::INTRINSIC_VOID) {\n" 3645 << " N.Val->dump(CurDAG);\n" 3646 << " } else {\n" 3647 << " unsigned iid = cast<ConstantSDNode>(N.getOperand(" 3648 "N.getOperand(0).getValueType() == MVT::Other))->getValue();\n" 3649 << " std::cerr << \"intrinsic %\"<< " 3650 "Intrinsic::getName((Intrinsic::ID)iid);\n" 3651 << " }\n" 3652 << " std::cerr << '\\n';\n" 3653 << " abort();\n" 3654 << " return NULL;\n" 3655 << "}\n"; 3656} 3657 3658void DAGISelEmitter::run(std::ostream &OS) { 3659 EmitSourceFileHeader("DAG Instruction Selector for the " + Target.getName() + 3660 " target", OS); 3661 3662 OS << "// *** NOTE: This file is #included into the middle of the target\n" 3663 << "// *** instruction selector class. These functions are really " 3664 << "methods.\n\n"; 3665 3666 OS << "#include \"llvm/Support/Compiler.h\"\n"; 3667 3668 OS << "// Instruction selector priority queue:\n" 3669 << "std::vector<SDNode*> ISelQueue;\n"; 3670 OS << "/// Keep track of nodes which have already been added to queue.\n" 3671 << "unsigned char *ISelQueued;\n"; 3672 OS << "/// Keep track of nodes which have already been selected.\n" 3673 << "unsigned char *ISelSelected;\n"; 3674 OS << "/// Dummy parameter to ReplaceAllUsesOfValueWith().\n" 3675 << "std::vector<SDNode*> ISelKilled;\n\n"; 3676 3677 OS << "/// IsChainCompatible - Returns true if Chain is Op or Chain does\n"; 3678 OS << "/// not reach Op.\n"; 3679 OS << "static bool IsChainCompatible(SDNode *Chain, SDNode *Op) {\n"; 3680 OS << " if (Chain->getOpcode() == ISD::EntryToken)\n"; 3681 OS << " return true;\n"; 3682 OS << " else if (Chain->getOpcode() == ISD::TokenFactor)\n"; 3683 OS << " return false;\n"; 3684 OS << " else if (Chain->getNumOperands() > 0) {\n"; 3685 OS << " SDOperand C0 = Chain->getOperand(0);\n"; 3686 OS << " if (C0.getValueType() == MVT::Other)\n"; 3687 OS << " return C0.Val != Op && IsChainCompatible(C0.Val, Op);\n"; 3688 OS << " }\n"; 3689 OS << " return true;\n"; 3690 OS << "}\n"; 3691 3692 OS << "/// Sorting functions for the selection queue.\n" 3693 << "struct isel_sort : public std::binary_function" 3694 << "<SDNode*, SDNode*, bool> {\n" 3695 << " bool operator()(const SDNode* left, const SDNode* right) " 3696 << "const {\n" 3697 << " return (left->getNodeId() > right->getNodeId());\n" 3698 << " }\n" 3699 << "};\n\n"; 3700 3701 OS << "inline void setQueued(int Id) {\n"; 3702 OS << " ISelQueued[Id / 8] |= 1 << (Id % 8);\n"; 3703 OS << "}\n"; 3704 OS << "inline bool isQueued(int Id) {\n"; 3705 OS << " return ISelQueued[Id / 8] & (1 << (Id % 8));\n"; 3706 OS << "}\n"; 3707 OS << "inline void setSelected(int Id) {\n"; 3708 OS << " ISelSelected[Id / 8] |= 1 << (Id % 8);\n"; 3709 OS << "}\n"; 3710 OS << "inline bool isSelected(int Id) {\n"; 3711 OS << " return ISelSelected[Id / 8] & (1 << (Id % 8));\n"; 3712 OS << "}\n\n"; 3713 3714 OS << "void AddToISelQueue(SDOperand N) DISABLE_INLINE {\n"; 3715 OS << " int Id = N.Val->getNodeId();\n"; 3716 OS << " if (Id != -1 && !isQueued(Id)) {\n"; 3717 OS << " ISelQueue.push_back(N.Val);\n"; 3718 OS << " std::push_heap(ISelQueue.begin(), ISelQueue.end(), isel_sort());\n"; 3719 OS << " setQueued(Id);\n"; 3720 OS << " }\n"; 3721 OS << "}\n\n"; 3722 3723 OS << "inline void RemoveKilled() {\n"; 3724OS << " unsigned NumKilled = ISelKilled.size();\n"; 3725 OS << " if (NumKilled) {\n"; 3726 OS << " for (unsigned i = 0; i != NumKilled; ++i) {\n"; 3727 OS << " SDNode *Temp = ISelKilled[i];\n"; 3728 OS << " ISelQueue.erase(std::remove(ISelQueue.begin(), ISelQueue.end(), " 3729 << "Temp), ISelQueue.end());\n"; 3730 OS << " };\n"; 3731 OS << " std::make_heap(ISelQueue.begin(), ISelQueue.end(), isel_sort());\n"; 3732 OS << " ISelKilled.clear();\n"; 3733 OS << " }\n"; 3734 OS << "}\n\n"; 3735 3736 OS << "void ReplaceUses(SDOperand F, SDOperand T) DISABLE_INLINE {\n"; 3737 OS << " CurDAG->ReplaceAllUsesOfValueWith(F, T, ISelKilled);\n"; 3738 OS << " setSelected(F.Val->getNodeId());\n"; 3739 OS << " RemoveKilled();\n"; 3740 OS << "}\n"; 3741 OS << "inline void ReplaceUses(SDNode *F, SDNode *T) {\n"; 3742 OS << " CurDAG->ReplaceAllUsesWith(F, T, &ISelKilled);\n"; 3743 OS << " setSelected(F->getNodeId());\n"; 3744 OS << " RemoveKilled();\n"; 3745 OS << "}\n\n"; 3746 3747 OS << "// SelectRoot - Top level entry to DAG isel.\n"; 3748 OS << "SDOperand SelectRoot(SDOperand Root) {\n"; 3749 OS << " SelectRootInit();\n"; 3750 OS << " unsigned NumBytes = (DAGSize + 7) / 8;\n"; 3751 OS << " ISelQueued = new unsigned char[NumBytes];\n"; 3752 OS << " ISelSelected = new unsigned char[NumBytes];\n"; 3753 OS << " memset(ISelQueued, 0, NumBytes);\n"; 3754 OS << " memset(ISelSelected, 0, NumBytes);\n"; 3755 OS << "\n"; 3756 OS << " // Create a dummy node (which is not added to allnodes), that adds\n" 3757 << " // a reference to the root node, preventing it from being deleted,\n" 3758 << " // and tracking any changes of the root.\n" 3759 << " HandleSDNode Dummy(CurDAG->getRoot());\n" 3760 << " ISelQueue.push_back(CurDAG->getRoot().Val);\n"; 3761 OS << " while (!ISelQueue.empty()) {\n"; 3762 OS << " SDNode *Node = ISelQueue.front();\n"; 3763 OS << " std::pop_heap(ISelQueue.begin(), ISelQueue.end(), isel_sort());\n"; 3764 OS << " ISelQueue.pop_back();\n"; 3765 OS << " if (!isSelected(Node->getNodeId())) {\n"; 3766 OS << " SDNode *ResNode = Select(SDOperand(Node, 0));\n"; 3767 OS << " if (ResNode != Node) {\n"; 3768 OS << " if (ResNode)\n"; 3769 OS << " ReplaceUses(Node, ResNode);\n"; 3770 OS << " if (Node->use_empty()) { // Don't delete EntryToken, etc.\n"; 3771 OS << " CurDAG->RemoveDeadNode(Node, ISelKilled);\n"; 3772 OS << " RemoveKilled();\n"; 3773 OS << " }\n"; 3774 OS << " }\n"; 3775 OS << " }\n"; 3776 OS << " }\n"; 3777 OS << "\n"; 3778 OS << " delete[] ISelQueued;\n"; 3779 OS << " ISelQueued = NULL;\n"; 3780 OS << " delete[] ISelSelected;\n"; 3781 OS << " ISelSelected = NULL;\n"; 3782 OS << " return Dummy.getValue();\n"; 3783 OS << "}\n"; 3784 3785 Intrinsics = LoadIntrinsics(Records); 3786 ParseNodeInfo(); 3787 ParseNodeTransforms(OS); 3788 ParseComplexPatterns(); 3789 ParsePatternFragments(OS); 3790 ParseInstructions(); 3791 ParsePatterns(); 3792 3793 // Generate variants. For example, commutative patterns can match 3794 // multiple ways. Add them to PatternsToMatch as well. 3795 GenerateVariants(); 3796 3797 3798 DEBUG(std::cerr << "\n\nALL PATTERNS TO MATCH:\n\n"; 3799 for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) { 3800 std::cerr << "PATTERN: "; PatternsToMatch[i].getSrcPattern()->dump(); 3801 std::cerr << "\nRESULT: ";PatternsToMatch[i].getDstPattern()->dump(); 3802 std::cerr << "\n"; 3803 }); 3804 3805 // At this point, we have full information about the 'Patterns' we need to 3806 // parse, both implicitly from instructions as well as from explicit pattern 3807 // definitions. Emit the resultant instruction selector. 3808 EmitInstructionSelector(OS); 3809 3810 for (std::map<Record*, TreePattern*>::iterator I = PatternFragments.begin(), 3811 E = PatternFragments.end(); I != E; ++I) 3812 delete I->second; 3813 PatternFragments.clear(); 3814 3815 Instructions.clear(); 3816} 3817