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