DAGISelMatcherGen.cpp revision 223017
1//===- DAGISelMatcherGen.cpp - Matcher generator --------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9 10#include "DAGISelMatcher.h" 11#include "CodeGenDAGPatterns.h" 12#include "CodeGenRegisters.h" 13#include "Record.h" 14#include "llvm/ADT/DenseMap.h" 15#include "llvm/ADT/SmallVector.h" 16#include "llvm/ADT/StringMap.h" 17#include <utility> 18using namespace llvm; 19 20 21/// getRegisterValueType - Look up and return the ValueType of the specified 22/// register. If the register is a member of multiple register classes which 23/// have different associated types, return MVT::Other. 24static MVT::SimpleValueType getRegisterValueType(Record *R, 25 const CodeGenTarget &T) { 26 bool FoundRC = false; 27 MVT::SimpleValueType VT = MVT::Other; 28 const std::vector<CodeGenRegisterClass> &RCs = T.getRegisterClasses(); 29 std::vector<Record*>::const_iterator Element; 30 31 for (unsigned rc = 0, e = RCs.size(); rc != e; ++rc) { 32 const CodeGenRegisterClass &RC = RCs[rc]; 33 if (!std::count(RC.Elements.begin(), RC.Elements.end(), R)) 34 continue; 35 36 if (!FoundRC) { 37 FoundRC = true; 38 VT = RC.getValueTypeNum(0); 39 continue; 40 } 41 42 // If this occurs in multiple register classes, they all have to agree. 43 assert(VT == RC.getValueTypeNum(0)); 44 } 45 return VT; 46} 47 48 49namespace { 50 class MatcherGen { 51 const PatternToMatch &Pattern; 52 const CodeGenDAGPatterns &CGP; 53 54 /// PatWithNoTypes - This is a clone of Pattern.getSrcPattern() that starts 55 /// out with all of the types removed. This allows us to insert type checks 56 /// as we scan the tree. 57 TreePatternNode *PatWithNoTypes; 58 59 /// VariableMap - A map from variable names ('$dst') to the recorded operand 60 /// number that they were captured as. These are biased by 1 to make 61 /// insertion easier. 62 StringMap<unsigned> VariableMap; 63 64 /// NextRecordedOperandNo - As we emit opcodes to record matched values in 65 /// the RecordedNodes array, this keeps track of which slot will be next to 66 /// record into. 67 unsigned NextRecordedOperandNo; 68 69 /// MatchedChainNodes - This maintains the position in the recorded nodes 70 /// array of all of the recorded input nodes that have chains. 71 SmallVector<unsigned, 2> MatchedChainNodes; 72 73 /// MatchedGlueResultNodes - This maintains the position in the recorded 74 /// nodes array of all of the recorded input nodes that have glue results. 75 SmallVector<unsigned, 2> MatchedGlueResultNodes; 76 77 /// MatchedComplexPatterns - This maintains a list of all of the 78 /// ComplexPatterns that we need to check. The patterns are known to have 79 /// names which were recorded. The second element of each pair is the first 80 /// slot number that the OPC_CheckComplexPat opcode drops the matched 81 /// results into. 82 SmallVector<std::pair<const TreePatternNode*, 83 unsigned>, 2> MatchedComplexPatterns; 84 85 /// PhysRegInputs - List list has an entry for each explicitly specified 86 /// physreg input to the pattern. The first elt is the Register node, the 87 /// second is the recorded slot number the input pattern match saved it in. 88 SmallVector<std::pair<Record*, unsigned>, 2> PhysRegInputs; 89 90 /// Matcher - This is the top level of the generated matcher, the result. 91 Matcher *TheMatcher; 92 93 /// CurPredicate - As we emit matcher nodes, this points to the latest check 94 /// which should have future checks stuck into its Next position. 95 Matcher *CurPredicate; 96 97 /// RegisterDefMap - A map of register record definitions to the 98 /// corresponding target CodeGenRegister entry. 99 DenseMap<const Record *, const CodeGenRegister *> RegisterDefMap; 100 public: 101 MatcherGen(const PatternToMatch &pattern, const CodeGenDAGPatterns &cgp); 102 103 ~MatcherGen() { 104 delete PatWithNoTypes; 105 } 106 107 bool EmitMatcherCode(unsigned Variant); 108 void EmitResultCode(); 109 110 Matcher *GetMatcher() const { return TheMatcher; } 111 private: 112 void AddMatcher(Matcher *NewNode); 113 void InferPossibleTypes(); 114 115 // Matcher Generation. 116 void EmitMatchCode(const TreePatternNode *N, TreePatternNode *NodeNoTypes); 117 void EmitLeafMatchCode(const TreePatternNode *N); 118 void EmitOperatorMatchCode(const TreePatternNode *N, 119 TreePatternNode *NodeNoTypes); 120 121 // Result Code Generation. 122 unsigned getNamedArgumentSlot(StringRef Name) { 123 unsigned VarMapEntry = VariableMap[Name]; 124 assert(VarMapEntry != 0 && 125 "Variable referenced but not defined and not caught earlier!"); 126 return VarMapEntry-1; 127 } 128 129 /// GetInstPatternNode - Get the pattern for an instruction. 130 const TreePatternNode *GetInstPatternNode(const DAGInstruction &Ins, 131 const TreePatternNode *N); 132 133 void EmitResultOperand(const TreePatternNode *N, 134 SmallVectorImpl<unsigned> &ResultOps); 135 void EmitResultOfNamedOperand(const TreePatternNode *N, 136 SmallVectorImpl<unsigned> &ResultOps); 137 void EmitResultLeafAsOperand(const TreePatternNode *N, 138 SmallVectorImpl<unsigned> &ResultOps); 139 void EmitResultInstructionAsOperand(const TreePatternNode *N, 140 SmallVectorImpl<unsigned> &ResultOps); 141 void EmitResultSDNodeXFormAsOperand(const TreePatternNode *N, 142 SmallVectorImpl<unsigned> &ResultOps); 143 }; 144 145} // end anon namespace. 146 147MatcherGen::MatcherGen(const PatternToMatch &pattern, 148 const CodeGenDAGPatterns &cgp) 149: Pattern(pattern), CGP(cgp), NextRecordedOperandNo(0), 150 TheMatcher(0), CurPredicate(0) { 151 // We need to produce the matcher tree for the patterns source pattern. To do 152 // this we need to match the structure as well as the types. To do the type 153 // matching, we want to figure out the fewest number of type checks we need to 154 // emit. For example, if there is only one integer type supported by a 155 // target, there should be no type comparisons at all for integer patterns! 156 // 157 // To figure out the fewest number of type checks needed, clone the pattern, 158 // remove the types, then perform type inference on the pattern as a whole. 159 // If there are unresolved types, emit an explicit check for those types, 160 // apply the type to the tree, then rerun type inference. Iterate until all 161 // types are resolved. 162 // 163 PatWithNoTypes = Pattern.getSrcPattern()->clone(); 164 PatWithNoTypes->RemoveAllTypes(); 165 166 // If there are types that are manifestly known, infer them. 167 InferPossibleTypes(); 168 169 // Populate the map from records to CodeGenRegister entries. 170 const CodeGenTarget &CGT = CGP.getTargetInfo(); 171 const std::vector<CodeGenRegister> &Registers = CGT.getRegisters(); 172 for (unsigned i = 0, e = Registers.size(); i != e; ++i) 173 RegisterDefMap[Registers[i].TheDef] = &Registers[i]; 174} 175 176/// InferPossibleTypes - As we emit the pattern, we end up generating type 177/// checks and applying them to the 'PatWithNoTypes' tree. As we do this, we 178/// want to propagate implied types as far throughout the tree as possible so 179/// that we avoid doing redundant type checks. This does the type propagation. 180void MatcherGen::InferPossibleTypes() { 181 // TP - Get *SOME* tree pattern, we don't care which. It is only used for 182 // diagnostics, which we know are impossible at this point. 183 TreePattern &TP = *CGP.pf_begin()->second; 184 185 try { 186 bool MadeChange = true; 187 while (MadeChange) 188 MadeChange = PatWithNoTypes->ApplyTypeConstraints(TP, 189 true/*Ignore reg constraints*/); 190 } catch (...) { 191 errs() << "Type constraint application shouldn't fail!"; 192 abort(); 193 } 194} 195 196 197/// AddMatcher - Add a matcher node to the current graph we're building. 198void MatcherGen::AddMatcher(Matcher *NewNode) { 199 if (CurPredicate != 0) 200 CurPredicate->setNext(NewNode); 201 else 202 TheMatcher = NewNode; 203 CurPredicate = NewNode; 204} 205 206 207//===----------------------------------------------------------------------===// 208// Pattern Match Generation 209//===----------------------------------------------------------------------===// 210 211/// EmitLeafMatchCode - Generate matching code for leaf nodes. 212void MatcherGen::EmitLeafMatchCode(const TreePatternNode *N) { 213 assert(N->isLeaf() && "Not a leaf?"); 214 215 // Direct match against an integer constant. 216 if (IntInit *II = dynamic_cast<IntInit*>(N->getLeafValue())) { 217 // If this is the root of the dag we're matching, we emit a redundant opcode 218 // check to ensure that this gets folded into the normal top-level 219 // OpcodeSwitch. 220 if (N == Pattern.getSrcPattern()) { 221 const SDNodeInfo &NI = CGP.getSDNodeInfo(CGP.getSDNodeNamed("imm")); 222 AddMatcher(new CheckOpcodeMatcher(NI)); 223 } 224 225 return AddMatcher(new CheckIntegerMatcher(II->getValue())); 226 } 227 228 DefInit *DI = dynamic_cast<DefInit*>(N->getLeafValue()); 229 if (DI == 0) { 230 errs() << "Unknown leaf kind: " << *DI << "\n"; 231 abort(); 232 } 233 234 Record *LeafRec = DI->getDef(); 235 if (// Handle register references. Nothing to do here, they always match. 236 LeafRec->isSubClassOf("RegisterClass") || 237 LeafRec->isSubClassOf("PointerLikeRegClass") || 238 LeafRec->isSubClassOf("SubRegIndex") || 239 // Place holder for SRCVALUE nodes. Nothing to do here. 240 LeafRec->getName() == "srcvalue") 241 return; 242 243 // If we have a physreg reference like (mul gpr:$src, EAX) then we need to 244 // record the register 245 if (LeafRec->isSubClassOf("Register")) { 246 AddMatcher(new RecordMatcher("physreg input "+LeafRec->getName(), 247 NextRecordedOperandNo)); 248 PhysRegInputs.push_back(std::make_pair(LeafRec, NextRecordedOperandNo++)); 249 return; 250 } 251 252 if (LeafRec->isSubClassOf("ValueType")) 253 return AddMatcher(new CheckValueTypeMatcher(LeafRec->getName())); 254 255 if (LeafRec->isSubClassOf("CondCode")) 256 return AddMatcher(new CheckCondCodeMatcher(LeafRec->getName())); 257 258 if (LeafRec->isSubClassOf("ComplexPattern")) { 259 // We can't model ComplexPattern uses that don't have their name taken yet. 260 // The OPC_CheckComplexPattern operation implicitly records the results. 261 if (N->getName().empty()) { 262 errs() << "We expect complex pattern uses to have names: " << *N << "\n"; 263 exit(1); 264 } 265 266 // Remember this ComplexPattern so that we can emit it after all the other 267 // structural matches are done. 268 MatchedComplexPatterns.push_back(std::make_pair(N, 0)); 269 return; 270 } 271 272 errs() << "Unknown leaf kind: " << *N << "\n"; 273 abort(); 274} 275 276void MatcherGen::EmitOperatorMatchCode(const TreePatternNode *N, 277 TreePatternNode *NodeNoTypes) { 278 assert(!N->isLeaf() && "Not an operator?"); 279 const SDNodeInfo &CInfo = CGP.getSDNodeInfo(N->getOperator()); 280 281 // If this is an 'and R, 1234' where the operation is AND/OR and the RHS is 282 // a constant without a predicate fn that has more that one bit set, handle 283 // this as a special case. This is usually for targets that have special 284 // handling of certain large constants (e.g. alpha with it's 8/16/32-bit 285 // handling stuff). Using these instructions is often far more efficient 286 // than materializing the constant. Unfortunately, both the instcombiner 287 // and the dag combiner can often infer that bits are dead, and thus drop 288 // them from the mask in the dag. For example, it might turn 'AND X, 255' 289 // into 'AND X, 254' if it knows the low bit is set. Emit code that checks 290 // to handle this. 291 if ((N->getOperator()->getName() == "and" || 292 N->getOperator()->getName() == "or") && 293 N->getChild(1)->isLeaf() && N->getChild(1)->getPredicateFns().empty() && 294 N->getPredicateFns().empty()) { 295 if (IntInit *II = dynamic_cast<IntInit*>(N->getChild(1)->getLeafValue())) { 296 if (!isPowerOf2_32(II->getValue())) { // Don't bother with single bits. 297 // If this is at the root of the pattern, we emit a redundant 298 // CheckOpcode so that the following checks get factored properly under 299 // a single opcode check. 300 if (N == Pattern.getSrcPattern()) 301 AddMatcher(new CheckOpcodeMatcher(CInfo)); 302 303 // Emit the CheckAndImm/CheckOrImm node. 304 if (N->getOperator()->getName() == "and") 305 AddMatcher(new CheckAndImmMatcher(II->getValue())); 306 else 307 AddMatcher(new CheckOrImmMatcher(II->getValue())); 308 309 // Match the LHS of the AND as appropriate. 310 AddMatcher(new MoveChildMatcher(0)); 311 EmitMatchCode(N->getChild(0), NodeNoTypes->getChild(0)); 312 AddMatcher(new MoveParentMatcher()); 313 return; 314 } 315 } 316 } 317 318 // Check that the current opcode lines up. 319 AddMatcher(new CheckOpcodeMatcher(CInfo)); 320 321 // If this node has memory references (i.e. is a load or store), tell the 322 // interpreter to capture them in the memref array. 323 if (N->NodeHasProperty(SDNPMemOperand, CGP)) 324 AddMatcher(new RecordMemRefMatcher()); 325 326 // If this node has a chain, then the chain is operand #0 is the SDNode, and 327 // the child numbers of the node are all offset by one. 328 unsigned OpNo = 0; 329 if (N->NodeHasProperty(SDNPHasChain, CGP)) { 330 // Record the node and remember it in our chained nodes list. 331 AddMatcher(new RecordMatcher("'" + N->getOperator()->getName() + 332 "' chained node", 333 NextRecordedOperandNo)); 334 // Remember all of the input chains our pattern will match. 335 MatchedChainNodes.push_back(NextRecordedOperandNo++); 336 337 // Don't look at the input chain when matching the tree pattern to the 338 // SDNode. 339 OpNo = 1; 340 341 // If this node is not the root and the subtree underneath it produces a 342 // chain, then the result of matching the node is also produce a chain. 343 // Beyond that, this means that we're also folding (at least) the root node 344 // into the node that produce the chain (for example, matching 345 // "(add reg, (load ptr))" as a add_with_memory on X86). This is 346 // problematic, if the 'reg' node also uses the load (say, its chain). 347 // Graphically: 348 // 349 // [LD] 350 // ^ ^ 351 // | \ DAG's like cheese. 352 // / | 353 // / [YY] 354 // | ^ 355 // [XX]--/ 356 // 357 // It would be invalid to fold XX and LD. In this case, folding the two 358 // nodes together would induce a cycle in the DAG, making it a 'cyclic DAG' 359 // To prevent this, we emit a dynamic check for legality before allowing 360 // this to be folded. 361 // 362 const TreePatternNode *Root = Pattern.getSrcPattern(); 363 if (N != Root) { // Not the root of the pattern. 364 // If there is a node between the root and this node, then we definitely 365 // need to emit the check. 366 bool NeedCheck = !Root->hasChild(N); 367 368 // If it *is* an immediate child of the root, we can still need a check if 369 // the root SDNode has multiple inputs. For us, this means that it is an 370 // intrinsic, has multiple operands, or has other inputs like chain or 371 // glue). 372 if (!NeedCheck) { 373 const SDNodeInfo &PInfo = CGP.getSDNodeInfo(Root->getOperator()); 374 NeedCheck = 375 Root->getOperator() == CGP.get_intrinsic_void_sdnode() || 376 Root->getOperator() == CGP.get_intrinsic_w_chain_sdnode() || 377 Root->getOperator() == CGP.get_intrinsic_wo_chain_sdnode() || 378 PInfo.getNumOperands() > 1 || 379 PInfo.hasProperty(SDNPHasChain) || 380 PInfo.hasProperty(SDNPInGlue) || 381 PInfo.hasProperty(SDNPOptInGlue); 382 } 383 384 if (NeedCheck) 385 AddMatcher(new CheckFoldableChainNodeMatcher()); 386 } 387 } 388 389 // If this node has an output glue and isn't the root, remember it. 390 if (N->NodeHasProperty(SDNPOutGlue, CGP) && 391 N != Pattern.getSrcPattern()) { 392 // TODO: This redundantly records nodes with both glues and chains. 393 394 // Record the node and remember it in our chained nodes list. 395 AddMatcher(new RecordMatcher("'" + N->getOperator()->getName() + 396 "' glue output node", 397 NextRecordedOperandNo)); 398 // Remember all of the nodes with output glue our pattern will match. 399 MatchedGlueResultNodes.push_back(NextRecordedOperandNo++); 400 } 401 402 // If this node is known to have an input glue or if it *might* have an input 403 // glue, capture it as the glue input of the pattern. 404 if (N->NodeHasProperty(SDNPOptInGlue, CGP) || 405 N->NodeHasProperty(SDNPInGlue, CGP)) 406 AddMatcher(new CaptureGlueInputMatcher()); 407 408 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) { 409 // Get the code suitable for matching this child. Move to the child, check 410 // it then move back to the parent. 411 AddMatcher(new MoveChildMatcher(OpNo)); 412 EmitMatchCode(N->getChild(i), NodeNoTypes->getChild(i)); 413 AddMatcher(new MoveParentMatcher()); 414 } 415} 416 417 418void MatcherGen::EmitMatchCode(const TreePatternNode *N, 419 TreePatternNode *NodeNoTypes) { 420 // If N and NodeNoTypes don't agree on a type, then this is a case where we 421 // need to do a type check. Emit the check, apply the tyep to NodeNoTypes and 422 // reinfer any correlated types. 423 SmallVector<unsigned, 2> ResultsToTypeCheck; 424 425 for (unsigned i = 0, e = NodeNoTypes->getNumTypes(); i != e; ++i) { 426 if (NodeNoTypes->getExtType(i) == N->getExtType(i)) continue; 427 NodeNoTypes->setType(i, N->getExtType(i)); 428 InferPossibleTypes(); 429 ResultsToTypeCheck.push_back(i); 430 } 431 432 // If this node has a name associated with it, capture it in VariableMap. If 433 // we already saw this in the pattern, emit code to verify dagness. 434 if (!N->getName().empty()) { 435 unsigned &VarMapEntry = VariableMap[N->getName()]; 436 if (VarMapEntry == 0) { 437 // If it is a named node, we must emit a 'Record' opcode. 438 AddMatcher(new RecordMatcher("$" + N->getName(), NextRecordedOperandNo)); 439 VarMapEntry = ++NextRecordedOperandNo; 440 } else { 441 // If we get here, this is a second reference to a specific name. Since 442 // we already have checked that the first reference is valid, we don't 443 // have to recursively match it, just check that it's the same as the 444 // previously named thing. 445 AddMatcher(new CheckSameMatcher(VarMapEntry-1)); 446 return; 447 } 448 } 449 450 if (N->isLeaf()) 451 EmitLeafMatchCode(N); 452 else 453 EmitOperatorMatchCode(N, NodeNoTypes); 454 455 // If there are node predicates for this node, generate their checks. 456 for (unsigned i = 0, e = N->getPredicateFns().size(); i != e; ++i) 457 AddMatcher(new CheckPredicateMatcher(N->getPredicateFns()[i])); 458 459 for (unsigned i = 0, e = ResultsToTypeCheck.size(); i != e; ++i) 460 AddMatcher(new CheckTypeMatcher(N->getType(ResultsToTypeCheck[i]), 461 ResultsToTypeCheck[i])); 462} 463 464/// EmitMatcherCode - Generate the code that matches the predicate of this 465/// pattern for the specified Variant. If the variant is invalid this returns 466/// true and does not generate code, if it is valid, it returns false. 467bool MatcherGen::EmitMatcherCode(unsigned Variant) { 468 // If the root of the pattern is a ComplexPattern and if it is specified to 469 // match some number of root opcodes, these are considered to be our variants. 470 // Depending on which variant we're generating code for, emit the root opcode 471 // check. 472 if (const ComplexPattern *CP = 473 Pattern.getSrcPattern()->getComplexPatternInfo(CGP)) { 474 const std::vector<Record*> &OpNodes = CP->getRootNodes(); 475 assert(!OpNodes.empty() &&"Complex Pattern must specify what it can match"); 476 if (Variant >= OpNodes.size()) return true; 477 478 AddMatcher(new CheckOpcodeMatcher(CGP.getSDNodeInfo(OpNodes[Variant]))); 479 } else { 480 if (Variant != 0) return true; 481 } 482 483 // Emit the matcher for the pattern structure and types. 484 EmitMatchCode(Pattern.getSrcPattern(), PatWithNoTypes); 485 486 // If the pattern has a predicate on it (e.g. only enabled when a subtarget 487 // feature is around, do the check). 488 if (!Pattern.getPredicateCheck().empty()) 489 AddMatcher(new CheckPatternPredicateMatcher(Pattern.getPredicateCheck())); 490 491 // Now that we've completed the structural type match, emit any ComplexPattern 492 // checks (e.g. addrmode matches). We emit this after the structural match 493 // because they are generally more expensive to evaluate and more difficult to 494 // factor. 495 for (unsigned i = 0, e = MatchedComplexPatterns.size(); i != e; ++i) { 496 const TreePatternNode *N = MatchedComplexPatterns[i].first; 497 498 // Remember where the results of this match get stuck. 499 MatchedComplexPatterns[i].second = NextRecordedOperandNo; 500 501 // Get the slot we recorded the value in from the name on the node. 502 unsigned RecNodeEntry = VariableMap[N->getName()]; 503 assert(!N->getName().empty() && RecNodeEntry && 504 "Complex pattern should have a name and slot"); 505 --RecNodeEntry; // Entries in VariableMap are biased. 506 507 const ComplexPattern &CP = 508 CGP.getComplexPattern(((DefInit*)N->getLeafValue())->getDef()); 509 510 // Emit a CheckComplexPat operation, which does the match (aborting if it 511 // fails) and pushes the matched operands onto the recorded nodes list. 512 AddMatcher(new CheckComplexPatMatcher(CP, RecNodeEntry, 513 N->getName(), NextRecordedOperandNo)); 514 515 // Record the right number of operands. 516 NextRecordedOperandNo += CP.getNumOperands(); 517 if (CP.hasProperty(SDNPHasChain)) { 518 // If the complex pattern has a chain, then we need to keep track of the 519 // fact that we just recorded a chain input. The chain input will be 520 // matched as the last operand of the predicate if it was successful. 521 ++NextRecordedOperandNo; // Chained node operand. 522 523 // It is the last operand recorded. 524 assert(NextRecordedOperandNo > 1 && 525 "Should have recorded input/result chains at least!"); 526 MatchedChainNodes.push_back(NextRecordedOperandNo-1); 527 } 528 529 // TODO: Complex patterns can't have output glues, if they did, we'd want 530 // to record them. 531 } 532 533 return false; 534} 535 536 537//===----------------------------------------------------------------------===// 538// Node Result Generation 539//===----------------------------------------------------------------------===// 540 541void MatcherGen::EmitResultOfNamedOperand(const TreePatternNode *N, 542 SmallVectorImpl<unsigned> &ResultOps){ 543 assert(!N->getName().empty() && "Operand not named!"); 544 545 // A reference to a complex pattern gets all of the results of the complex 546 // pattern's match. 547 if (const ComplexPattern *CP = N->getComplexPatternInfo(CGP)) { 548 unsigned SlotNo = 0; 549 for (unsigned i = 0, e = MatchedComplexPatterns.size(); i != e; ++i) 550 if (MatchedComplexPatterns[i].first->getName() == N->getName()) { 551 SlotNo = MatchedComplexPatterns[i].second; 552 break; 553 } 554 assert(SlotNo != 0 && "Didn't get a slot number assigned?"); 555 556 // The first slot entry is the node itself, the subsequent entries are the 557 // matched values. 558 for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i) 559 ResultOps.push_back(SlotNo+i); 560 return; 561 } 562 563 unsigned SlotNo = getNamedArgumentSlot(N->getName()); 564 565 // If this is an 'imm' or 'fpimm' node, make sure to convert it to the target 566 // version of the immediate so that it doesn't get selected due to some other 567 // node use. 568 if (!N->isLeaf()) { 569 StringRef OperatorName = N->getOperator()->getName(); 570 if (OperatorName == "imm" || OperatorName == "fpimm") { 571 AddMatcher(new EmitConvertToTargetMatcher(SlotNo)); 572 ResultOps.push_back(NextRecordedOperandNo++); 573 return; 574 } 575 } 576 577 ResultOps.push_back(SlotNo); 578} 579 580void MatcherGen::EmitResultLeafAsOperand(const TreePatternNode *N, 581 SmallVectorImpl<unsigned> &ResultOps) { 582 assert(N->isLeaf() && "Must be a leaf"); 583 584 if (IntInit *II = dynamic_cast<IntInit*>(N->getLeafValue())) { 585 AddMatcher(new EmitIntegerMatcher(II->getValue(), N->getType(0))); 586 ResultOps.push_back(NextRecordedOperandNo++); 587 return; 588 } 589 590 // If this is an explicit register reference, handle it. 591 if (DefInit *DI = dynamic_cast<DefInit*>(N->getLeafValue())) { 592 if (DI->getDef()->isSubClassOf("Register")) { 593 AddMatcher(new EmitRegisterMatcher(RegisterDefMap[DI->getDef()], 594 N->getType(0))); 595 ResultOps.push_back(NextRecordedOperandNo++); 596 return; 597 } 598 599 if (DI->getDef()->getName() == "zero_reg") { 600 AddMatcher(new EmitRegisterMatcher(0, N->getType(0))); 601 ResultOps.push_back(NextRecordedOperandNo++); 602 return; 603 } 604 605 // Handle a reference to a register class. This is used 606 // in COPY_TO_SUBREG instructions. 607 if (DI->getDef()->isSubClassOf("RegisterClass")) { 608 std::string Value = getQualifiedName(DI->getDef()) + "RegClassID"; 609 AddMatcher(new EmitStringIntegerMatcher(Value, MVT::i32)); 610 ResultOps.push_back(NextRecordedOperandNo++); 611 return; 612 } 613 614 // Handle a subregister index. This is used for INSERT_SUBREG etc. 615 if (DI->getDef()->isSubClassOf("SubRegIndex")) { 616 std::string Value = getQualifiedName(DI->getDef()); 617 AddMatcher(new EmitStringIntegerMatcher(Value, MVT::i32)); 618 ResultOps.push_back(NextRecordedOperandNo++); 619 return; 620 } 621 } 622 623 errs() << "unhandled leaf node: \n"; 624 N->dump(); 625} 626 627/// GetInstPatternNode - Get the pattern for an instruction. 628/// 629const TreePatternNode *MatcherGen:: 630GetInstPatternNode(const DAGInstruction &Inst, const TreePatternNode *N) { 631 const TreePattern *InstPat = Inst.getPattern(); 632 633 // FIXME2?: Assume actual pattern comes before "implicit". 634 TreePatternNode *InstPatNode; 635 if (InstPat) 636 InstPatNode = InstPat->getTree(0); 637 else if (/*isRoot*/ N == Pattern.getDstPattern()) 638 InstPatNode = Pattern.getSrcPattern(); 639 else 640 return 0; 641 642 if (InstPatNode && !InstPatNode->isLeaf() && 643 InstPatNode->getOperator()->getName() == "set") 644 InstPatNode = InstPatNode->getChild(InstPatNode->getNumChildren()-1); 645 646 return InstPatNode; 647} 648 649static bool 650mayInstNodeLoadOrStore(const TreePatternNode *N, 651 const CodeGenDAGPatterns &CGP) { 652 Record *Op = N->getOperator(); 653 const CodeGenTarget &CGT = CGP.getTargetInfo(); 654 CodeGenInstruction &II = CGT.getInstruction(Op); 655 return II.mayLoad || II.mayStore; 656} 657 658static unsigned 659numNodesThatMayLoadOrStore(const TreePatternNode *N, 660 const CodeGenDAGPatterns &CGP) { 661 if (N->isLeaf()) 662 return 0; 663 664 Record *OpRec = N->getOperator(); 665 if (!OpRec->isSubClassOf("Instruction")) 666 return 0; 667 668 unsigned Count = 0; 669 if (mayInstNodeLoadOrStore(N, CGP)) 670 ++Count; 671 672 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 673 Count += numNodesThatMayLoadOrStore(N->getChild(i), CGP); 674 675 return Count; 676} 677 678void MatcherGen:: 679EmitResultInstructionAsOperand(const TreePatternNode *N, 680 SmallVectorImpl<unsigned> &OutputOps) { 681 Record *Op = N->getOperator(); 682 const CodeGenTarget &CGT = CGP.getTargetInfo(); 683 CodeGenInstruction &II = CGT.getInstruction(Op); 684 const DAGInstruction &Inst = CGP.getInstruction(Op); 685 686 // If we can, get the pattern for the instruction we're generating. We derive 687 // a variety of information from this pattern, such as whether it has a chain. 688 // 689 // FIXME2: This is extremely dubious for several reasons, not the least of 690 // which it gives special status to instructions with patterns that Pat<> 691 // nodes can't duplicate. 692 const TreePatternNode *InstPatNode = GetInstPatternNode(Inst, N); 693 694 // NodeHasChain - Whether the instruction node we're creating takes chains. 695 bool NodeHasChain = InstPatNode && 696 InstPatNode->TreeHasProperty(SDNPHasChain, CGP); 697 698 bool isRoot = N == Pattern.getDstPattern(); 699 700 // TreeHasOutGlue - True if this tree has glue. 701 bool TreeHasInGlue = false, TreeHasOutGlue = false; 702 if (isRoot) { 703 const TreePatternNode *SrcPat = Pattern.getSrcPattern(); 704 TreeHasInGlue = SrcPat->TreeHasProperty(SDNPOptInGlue, CGP) || 705 SrcPat->TreeHasProperty(SDNPInGlue, CGP); 706 707 // FIXME2: this is checking the entire pattern, not just the node in 708 // question, doing this just for the root seems like a total hack. 709 TreeHasOutGlue = SrcPat->TreeHasProperty(SDNPOutGlue, CGP); 710 } 711 712 // NumResults - This is the number of results produced by the instruction in 713 // the "outs" list. 714 unsigned NumResults = Inst.getNumResults(); 715 716 // Loop over all of the operands of the instruction pattern, emitting code 717 // to fill them all in. The node 'N' usually has number children equal to 718 // the number of input operands of the instruction. However, in cases 719 // where there are predicate operands for an instruction, we need to fill 720 // in the 'execute always' values. Match up the node operands to the 721 // instruction operands to do this. 722 SmallVector<unsigned, 8> InstOps; 723 for (unsigned ChildNo = 0, InstOpNo = NumResults, e = II.Operands.size(); 724 InstOpNo != e; ++InstOpNo) { 725 726 // Determine what to emit for this operand. 727 Record *OperandNode = II.Operands[InstOpNo].Rec; 728 if ((OperandNode->isSubClassOf("PredicateOperand") || 729 OperandNode->isSubClassOf("OptionalDefOperand")) && 730 !CGP.getDefaultOperand(OperandNode).DefaultOps.empty()) { 731 // This is a predicate or optional def operand; emit the 732 // 'default ops' operands. 733 const DAGDefaultOperand &DefaultOp 734 = CGP.getDefaultOperand(OperandNode); 735 for (unsigned i = 0, e = DefaultOp.DefaultOps.size(); i != e; ++i) 736 EmitResultOperand(DefaultOp.DefaultOps[i], InstOps); 737 continue; 738 } 739 740 const TreePatternNode *Child = N->getChild(ChildNo); 741 742 // Otherwise this is a normal operand or a predicate operand without 743 // 'execute always'; emit it. 744 unsigned BeforeAddingNumOps = InstOps.size(); 745 EmitResultOperand(Child, InstOps); 746 assert(InstOps.size() > BeforeAddingNumOps && "Didn't add any operands"); 747 748 // If the operand is an instruction and it produced multiple results, just 749 // take the first one. 750 if (!Child->isLeaf() && Child->getOperator()->isSubClassOf("Instruction")) 751 InstOps.resize(BeforeAddingNumOps+1); 752 753 ++ChildNo; 754 } 755 756 // If this node has input glue or explicitly specified input physregs, we 757 // need to add chained and glued copyfromreg nodes and materialize the glue 758 // input. 759 if (isRoot && !PhysRegInputs.empty()) { 760 // Emit all of the CopyToReg nodes for the input physical registers. These 761 // occur in patterns like (mul:i8 AL:i8, GR8:i8:$src). 762 for (unsigned i = 0, e = PhysRegInputs.size(); i != e; ++i) 763 AddMatcher(new EmitCopyToRegMatcher(PhysRegInputs[i].second, 764 PhysRegInputs[i].first)); 765 // Even if the node has no other glue inputs, the resultant node must be 766 // glued to the CopyFromReg nodes we just generated. 767 TreeHasInGlue = true; 768 } 769 770 // Result order: node results, chain, glue 771 772 // Determine the result types. 773 SmallVector<MVT::SimpleValueType, 4> ResultVTs; 774 for (unsigned i = 0, e = N->getNumTypes(); i != e; ++i) 775 ResultVTs.push_back(N->getType(i)); 776 777 // If this is the root instruction of a pattern that has physical registers in 778 // its result pattern, add output VTs for them. For example, X86 has: 779 // (set AL, (mul ...)) 780 // This also handles implicit results like: 781 // (implicit EFLAGS) 782 if (isRoot && !Pattern.getDstRegs().empty()) { 783 // If the root came from an implicit def in the instruction handling stuff, 784 // don't re-add it. 785 Record *HandledReg = 0; 786 if (II.HasOneImplicitDefWithKnownVT(CGT) != MVT::Other) 787 HandledReg = II.ImplicitDefs[0]; 788 789 for (unsigned i = 0; i != Pattern.getDstRegs().size(); ++i) { 790 Record *Reg = Pattern.getDstRegs()[i]; 791 if (!Reg->isSubClassOf("Register") || Reg == HandledReg) continue; 792 ResultVTs.push_back(getRegisterValueType(Reg, CGT)); 793 } 794 } 795 796 // If this is the root of the pattern and the pattern we're matching includes 797 // a node that is variadic, mark the generated node as variadic so that it 798 // gets the excess operands from the input DAG. 799 int NumFixedArityOperands = -1; 800 if (isRoot && 801 (Pattern.getSrcPattern()->NodeHasProperty(SDNPVariadic, CGP))) 802 NumFixedArityOperands = Pattern.getSrcPattern()->getNumChildren(); 803 804 // If this is the root node and multiple matched nodes in the input pattern 805 // have MemRefs in them, have the interpreter collect them and plop them onto 806 // this node. If there is just one node with MemRefs, leave them on that node 807 // even if it is not the root. 808 // 809 // FIXME3: This is actively incorrect for result patterns with multiple 810 // memory-referencing instructions. 811 bool PatternHasMemOperands = 812 Pattern.getSrcPattern()->TreeHasProperty(SDNPMemOperand, CGP); 813 814 bool NodeHasMemRefs = false; 815 if (PatternHasMemOperands) { 816 unsigned NumNodesThatLoadOrStore = 817 numNodesThatMayLoadOrStore(Pattern.getDstPattern(), CGP); 818 bool NodeIsUniqueLoadOrStore = mayInstNodeLoadOrStore(N, CGP) && 819 NumNodesThatLoadOrStore == 1; 820 NodeHasMemRefs = 821 NodeIsUniqueLoadOrStore || (isRoot && (mayInstNodeLoadOrStore(N, CGP) || 822 NumNodesThatLoadOrStore != 1)); 823 } 824 825 assert((!ResultVTs.empty() || TreeHasOutGlue || NodeHasChain) && 826 "Node has no result"); 827 828 AddMatcher(new EmitNodeMatcher(II.Namespace+"::"+II.TheDef->getName(), 829 ResultVTs.data(), ResultVTs.size(), 830 InstOps.data(), InstOps.size(), 831 NodeHasChain, TreeHasInGlue, TreeHasOutGlue, 832 NodeHasMemRefs, NumFixedArityOperands, 833 NextRecordedOperandNo)); 834 835 // The non-chain and non-glue results of the newly emitted node get recorded. 836 for (unsigned i = 0, e = ResultVTs.size(); i != e; ++i) { 837 if (ResultVTs[i] == MVT::Other || ResultVTs[i] == MVT::Glue) break; 838 OutputOps.push_back(NextRecordedOperandNo++); 839 } 840} 841 842void MatcherGen:: 843EmitResultSDNodeXFormAsOperand(const TreePatternNode *N, 844 SmallVectorImpl<unsigned> &ResultOps) { 845 assert(N->getOperator()->isSubClassOf("SDNodeXForm") && "Not SDNodeXForm?"); 846 847 // Emit the operand. 848 SmallVector<unsigned, 8> InputOps; 849 850 // FIXME2: Could easily generalize this to support multiple inputs and outputs 851 // to the SDNodeXForm. For now we just support one input and one output like 852 // the old instruction selector. 853 assert(N->getNumChildren() == 1); 854 EmitResultOperand(N->getChild(0), InputOps); 855 856 // The input currently must have produced exactly one result. 857 assert(InputOps.size() == 1 && "Unexpected input to SDNodeXForm"); 858 859 AddMatcher(new EmitNodeXFormMatcher(InputOps[0], N->getOperator())); 860 ResultOps.push_back(NextRecordedOperandNo++); 861} 862 863void MatcherGen::EmitResultOperand(const TreePatternNode *N, 864 SmallVectorImpl<unsigned> &ResultOps) { 865 // This is something selected from the pattern we matched. 866 if (!N->getName().empty()) 867 return EmitResultOfNamedOperand(N, ResultOps); 868 869 if (N->isLeaf()) 870 return EmitResultLeafAsOperand(N, ResultOps); 871 872 Record *OpRec = N->getOperator(); 873 if (OpRec->isSubClassOf("Instruction")) 874 return EmitResultInstructionAsOperand(N, ResultOps); 875 if (OpRec->isSubClassOf("SDNodeXForm")) 876 return EmitResultSDNodeXFormAsOperand(N, ResultOps); 877 errs() << "Unknown result node to emit code for: " << *N << '\n'; 878 throw std::string("Unknown node in result pattern!"); 879} 880 881void MatcherGen::EmitResultCode() { 882 // Patterns that match nodes with (potentially multiple) chain inputs have to 883 // merge them together into a token factor. This informs the generated code 884 // what all the chained nodes are. 885 if (!MatchedChainNodes.empty()) 886 AddMatcher(new EmitMergeInputChainsMatcher 887 (MatchedChainNodes.data(), MatchedChainNodes.size())); 888 889 // Codegen the root of the result pattern, capturing the resulting values. 890 SmallVector<unsigned, 8> Ops; 891 EmitResultOperand(Pattern.getDstPattern(), Ops); 892 893 // At this point, we have however many values the result pattern produces. 894 // However, the input pattern might not need all of these. If there are 895 // excess values at the end (such as implicit defs of condition codes etc) 896 // just lop them off. This doesn't need to worry about glue or chains, just 897 // explicit results. 898 // 899 unsigned NumSrcResults = Pattern.getSrcPattern()->getNumTypes(); 900 901 // If the pattern also has (implicit) results, count them as well. 902 if (!Pattern.getDstRegs().empty()) { 903 // If the root came from an implicit def in the instruction handling stuff, 904 // don't re-add it. 905 Record *HandledReg = 0; 906 const TreePatternNode *DstPat = Pattern.getDstPattern(); 907 if (!DstPat->isLeaf() &&DstPat->getOperator()->isSubClassOf("Instruction")){ 908 const CodeGenTarget &CGT = CGP.getTargetInfo(); 909 CodeGenInstruction &II = CGT.getInstruction(DstPat->getOperator()); 910 911 if (II.HasOneImplicitDefWithKnownVT(CGT) != MVT::Other) 912 HandledReg = II.ImplicitDefs[0]; 913 } 914 915 for (unsigned i = 0; i != Pattern.getDstRegs().size(); ++i) { 916 Record *Reg = Pattern.getDstRegs()[i]; 917 if (!Reg->isSubClassOf("Register") || Reg == HandledReg) continue; 918 ++NumSrcResults; 919 } 920 } 921 922 assert(Ops.size() >= NumSrcResults && "Didn't provide enough results"); 923 Ops.resize(NumSrcResults); 924 925 // If the matched pattern covers nodes which define a glue result, emit a node 926 // that tells the matcher about them so that it can update their results. 927 if (!MatchedGlueResultNodes.empty()) 928 AddMatcher(new MarkGlueResultsMatcher(MatchedGlueResultNodes.data(), 929 MatchedGlueResultNodes.size())); 930 931 AddMatcher(new CompleteMatchMatcher(Ops.data(), Ops.size(), Pattern)); 932} 933 934 935/// ConvertPatternToMatcher - Create the matcher for the specified pattern with 936/// the specified variant. If the variant number is invalid, this returns null. 937Matcher *llvm::ConvertPatternToMatcher(const PatternToMatch &Pattern, 938 unsigned Variant, 939 const CodeGenDAGPatterns &CGP) { 940 MatcherGen Gen(Pattern, CGP); 941 942 // Generate the code for the matcher. 943 if (Gen.EmitMatcherCode(Variant)) 944 return 0; 945 946 // FIXME2: Kill extra MoveParent commands at the end of the matcher sequence. 947 // FIXME2: Split result code out to another table, and make the matcher end 948 // with an "Emit <index>" command. This allows result generation stuff to be 949 // shared and factored? 950 951 // If the match succeeds, then we generate Pattern. 952 Gen.EmitResultCode(); 953 954 // Unconditional match. 955 return Gen.GetMatcher(); 956} 957