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