1203954Srdivacky//===- DAGISelMatcherGen.cpp - Matcher generator --------------------------===// 2203954Srdivacky// 3203954Srdivacky// The LLVM Compiler Infrastructure 4203954Srdivacky// 5203954Srdivacky// This file is distributed under the University of Illinois Open Source 6203954Srdivacky// License. See LICENSE.TXT for details. 7203954Srdivacky// 8203954Srdivacky//===----------------------------------------------------------------------===// 9203954Srdivacky 10203954Srdivacky#include "DAGISelMatcher.h" 11203954Srdivacky#include "CodeGenDAGPatterns.h" 12221345Sdim#include "CodeGenRegisters.h" 13221345Sdim#include "llvm/ADT/DenseMap.h" 14204642Srdivacky#include "llvm/ADT/SmallVector.h" 15203954Srdivacky#include "llvm/ADT/StringMap.h" 16249423Sdim#include "llvm/TableGen/Error.h" 17249423Sdim#include "llvm/TableGen/Record.h" 18204642Srdivacky#include <utility> 19203954Srdivackyusing namespace llvm; 20203954Srdivacky 21204642Srdivacky 22204642Srdivacky/// getRegisterValueType - Look up and return the ValueType of the specified 23204642Srdivacky/// register. If the register is a member of multiple register classes which 24204642Srdivacky/// have different associated types, return MVT::Other. 25204642Srdivackystatic MVT::SimpleValueType getRegisterValueType(Record *R, 26204642Srdivacky const CodeGenTarget &T) { 27204642Srdivacky bool FoundRC = false; 28204642Srdivacky MVT::SimpleValueType VT = MVT::Other; 29224145Sdim const CodeGenRegister *Reg = T.getRegBank().getReg(R); 30226633Sdim ArrayRef<CodeGenRegisterClass*> RCs = T.getRegBank().getRegClasses(); 31218893Sdim 32204642Srdivacky for (unsigned rc = 0, e = RCs.size(); rc != e; ++rc) { 33226633Sdim const CodeGenRegisterClass &RC = *RCs[rc]; 34224145Sdim if (!RC.contains(Reg)) 35204642Srdivacky continue; 36218893Sdim 37204642Srdivacky if (!FoundRC) { 38204642Srdivacky FoundRC = true; 39204642Srdivacky VT = RC.getValueTypeNum(0); 40204642Srdivacky continue; 41204642Srdivacky } 42204642Srdivacky 43204642Srdivacky // If this occurs in multiple register classes, they all have to agree. 44204642Srdivacky assert(VT == RC.getValueTypeNum(0)); 45204642Srdivacky } 46204642Srdivacky return VT; 47204642Srdivacky} 48204642Srdivacky 49204642Srdivacky 50203954Srdivackynamespace { 51203954Srdivacky class MatcherGen { 52203954Srdivacky const PatternToMatch &Pattern; 53203954Srdivacky const CodeGenDAGPatterns &CGP; 54218893Sdim 55203954Srdivacky /// PatWithNoTypes - This is a clone of Pattern.getSrcPattern() that starts 56203954Srdivacky /// out with all of the types removed. This allows us to insert type checks 57203954Srdivacky /// as we scan the tree. 58203954Srdivacky TreePatternNode *PatWithNoTypes; 59218893Sdim 60203954Srdivacky /// VariableMap - A map from variable names ('$dst') to the recorded operand 61203954Srdivacky /// number that they were captured as. These are biased by 1 to make 62203954Srdivacky /// insertion easier. 63203954Srdivacky StringMap<unsigned> VariableMap; 64218893Sdim 65204642Srdivacky /// NextRecordedOperandNo - As we emit opcodes to record matched values in 66204642Srdivacky /// the RecordedNodes array, this keeps track of which slot will be next to 67204642Srdivacky /// record into. 68203954Srdivacky unsigned NextRecordedOperandNo; 69218893Sdim 70204642Srdivacky /// MatchedChainNodes - This maintains the position in the recorded nodes 71204642Srdivacky /// array of all of the recorded input nodes that have chains. 72204642Srdivacky SmallVector<unsigned, 2> MatchedChainNodes; 73204642Srdivacky 74218893Sdim /// MatchedGlueResultNodes - This maintains the position in the recorded 75218893Sdim /// nodes array of all of the recorded input nodes that have glue results. 76218893Sdim SmallVector<unsigned, 2> MatchedGlueResultNodes; 77218893Sdim 78204792Srdivacky /// MatchedComplexPatterns - This maintains a list of all of the 79204792Srdivacky /// ComplexPatterns that we need to check. The patterns are known to have 80204792Srdivacky /// names which were recorded. The second element of each pair is the first 81204792Srdivacky /// slot number that the OPC_CheckComplexPat opcode drops the matched 82204792Srdivacky /// results into. 83204792Srdivacky SmallVector<std::pair<const TreePatternNode*, 84204792Srdivacky unsigned>, 2> MatchedComplexPatterns; 85218893Sdim 86204642Srdivacky /// PhysRegInputs - List list has an entry for each explicitly specified 87204642Srdivacky /// physreg input to the pattern. The first elt is the Register node, the 88204642Srdivacky /// second is the recorded slot number the input pattern match saved it in. 89204642Srdivacky SmallVector<std::pair<Record*, unsigned>, 2> PhysRegInputs; 90218893Sdim 91204642Srdivacky /// Matcher - This is the top level of the generated matcher, the result. 92204642Srdivacky Matcher *TheMatcher; 93218893Sdim 94204642Srdivacky /// CurPredicate - As we emit matcher nodes, this points to the latest check 95204642Srdivacky /// which should have future checks stuck into its Next position. 96204642Srdivacky Matcher *CurPredicate; 97203954Srdivacky public: 98203954Srdivacky MatcherGen(const PatternToMatch &pattern, const CodeGenDAGPatterns &cgp); 99218893Sdim 100203954Srdivacky ~MatcherGen() { 101203954Srdivacky delete PatWithNoTypes; 102203954Srdivacky } 103218893Sdim 104204642Srdivacky bool EmitMatcherCode(unsigned Variant); 105204642Srdivacky void EmitResultCode(); 106218893Sdim 107204642Srdivacky Matcher *GetMatcher() const { return TheMatcher; } 108203954Srdivacky private: 109204642Srdivacky void AddMatcher(Matcher *NewNode); 110203954Srdivacky void InferPossibleTypes(); 111218893Sdim 112204642Srdivacky // Matcher Generation. 113203954Srdivacky void EmitMatchCode(const TreePatternNode *N, TreePatternNode *NodeNoTypes); 114203954Srdivacky void EmitLeafMatchCode(const TreePatternNode *N); 115203954Srdivacky void EmitOperatorMatchCode(const TreePatternNode *N, 116203954Srdivacky TreePatternNode *NodeNoTypes); 117218893Sdim 118204642Srdivacky // Result Code Generation. 119204642Srdivacky unsigned getNamedArgumentSlot(StringRef Name) { 120204642Srdivacky unsigned VarMapEntry = VariableMap[Name]; 121204642Srdivacky assert(VarMapEntry != 0 && 122204642Srdivacky "Variable referenced but not defined and not caught earlier!"); 123204642Srdivacky return VarMapEntry-1; 124204642Srdivacky } 125204642Srdivacky 126204642Srdivacky /// GetInstPatternNode - Get the pattern for an instruction. 127204642Srdivacky const TreePatternNode *GetInstPatternNode(const DAGInstruction &Ins, 128204642Srdivacky const TreePatternNode *N); 129218893Sdim 130204642Srdivacky void EmitResultOperand(const TreePatternNode *N, 131204642Srdivacky SmallVectorImpl<unsigned> &ResultOps); 132204642Srdivacky void EmitResultOfNamedOperand(const TreePatternNode *N, 133204642Srdivacky SmallVectorImpl<unsigned> &ResultOps); 134204642Srdivacky void EmitResultLeafAsOperand(const TreePatternNode *N, 135204642Srdivacky SmallVectorImpl<unsigned> &ResultOps); 136204642Srdivacky void EmitResultInstructionAsOperand(const TreePatternNode *N, 137204642Srdivacky SmallVectorImpl<unsigned> &ResultOps); 138204642Srdivacky void EmitResultSDNodeXFormAsOperand(const TreePatternNode *N, 139204642Srdivacky SmallVectorImpl<unsigned> &ResultOps); 140204642Srdivacky }; 141218893Sdim 142203954Srdivacky} // end anon namespace. 143203954Srdivacky 144203954SrdivackyMatcherGen::MatcherGen(const PatternToMatch &pattern, 145203954Srdivacky const CodeGenDAGPatterns &cgp) 146203954Srdivacky: Pattern(pattern), CGP(cgp), NextRecordedOperandNo(0), 147204642Srdivacky TheMatcher(0), CurPredicate(0) { 148203954Srdivacky // We need to produce the matcher tree for the patterns source pattern. To do 149203954Srdivacky // this we need to match the structure as well as the types. To do the type 150203954Srdivacky // matching, we want to figure out the fewest number of type checks we need to 151203954Srdivacky // emit. For example, if there is only one integer type supported by a 152203954Srdivacky // target, there should be no type comparisons at all for integer patterns! 153203954Srdivacky // 154203954Srdivacky // To figure out the fewest number of type checks needed, clone the pattern, 155203954Srdivacky // remove the types, then perform type inference on the pattern as a whole. 156203954Srdivacky // If there are unresolved types, emit an explicit check for those types, 157203954Srdivacky // apply the type to the tree, then rerun type inference. Iterate until all 158203954Srdivacky // types are resolved. 159203954Srdivacky // 160203954Srdivacky PatWithNoTypes = Pattern.getSrcPattern()->clone(); 161203954Srdivacky PatWithNoTypes->RemoveAllTypes(); 162218893Sdim 163203954Srdivacky // If there are types that are manifestly known, infer them. 164203954Srdivacky InferPossibleTypes(); 165203954Srdivacky} 166203954Srdivacky 167203954Srdivacky/// InferPossibleTypes - As we emit the pattern, we end up generating type 168203954Srdivacky/// checks and applying them to the 'PatWithNoTypes' tree. As we do this, we 169203954Srdivacky/// want to propagate implied types as far throughout the tree as possible so 170203954Srdivacky/// that we avoid doing redundant type checks. This does the type propagation. 171203954Srdivackyvoid MatcherGen::InferPossibleTypes() { 172203954Srdivacky // TP - Get *SOME* tree pattern, we don't care which. It is only used for 173203954Srdivacky // diagnostics, which we know are impossible at this point. 174203954Srdivacky TreePattern &TP = *CGP.pf_begin()->second; 175218893Sdim 176243830Sdim bool MadeChange = true; 177243830Sdim while (MadeChange) 178243830Sdim MadeChange = PatWithNoTypes->ApplyTypeConstraints(TP, 179243830Sdim true/*Ignore reg constraints*/); 180203954Srdivacky} 181203954Srdivacky 182203954Srdivacky 183218893Sdim/// AddMatcher - Add a matcher node to the current graph we're building. 184204642Srdivackyvoid MatcherGen::AddMatcher(Matcher *NewNode) { 185203954Srdivacky if (CurPredicate != 0) 186204642Srdivacky CurPredicate->setNext(NewNode); 187203954Srdivacky else 188204642Srdivacky TheMatcher = NewNode; 189203954Srdivacky CurPredicate = NewNode; 190203954Srdivacky} 191203954Srdivacky 192203954Srdivacky 193204642Srdivacky//===----------------------------------------------------------------------===// 194204642Srdivacky// Pattern Match Generation 195204642Srdivacky//===----------------------------------------------------------------------===// 196203954Srdivacky 197203954Srdivacky/// EmitLeafMatchCode - Generate matching code for leaf nodes. 198203954Srdivackyvoid MatcherGen::EmitLeafMatchCode(const TreePatternNode *N) { 199203954Srdivacky assert(N->isLeaf() && "Not a leaf?"); 200218893Sdim 201203954Srdivacky // Direct match against an integer constant. 202243830Sdim if (IntInit *II = dyn_cast<IntInit>(N->getLeafValue())) { 203204642Srdivacky // If this is the root of the dag we're matching, we emit a redundant opcode 204204642Srdivacky // check to ensure that this gets folded into the normal top-level 205204642Srdivacky // OpcodeSwitch. 206204642Srdivacky if (N == Pattern.getSrcPattern()) { 207204642Srdivacky const SDNodeInfo &NI = CGP.getSDNodeInfo(CGP.getSDNodeNamed("imm")); 208204642Srdivacky AddMatcher(new CheckOpcodeMatcher(NI)); 209204642Srdivacky } 210204642Srdivacky 211204642Srdivacky return AddMatcher(new CheckIntegerMatcher(II->getValue())); 212204642Srdivacky } 213218893Sdim 214249423Sdim // An UnsetInit represents a named node without any constraints. 215249423Sdim if (N->getLeafValue() == UnsetInit::get()) { 216249423Sdim assert(N->hasName() && "Unnamed ? leaf"); 217249423Sdim return; 218249423Sdim } 219249423Sdim 220243830Sdim DefInit *DI = dyn_cast<DefInit>(N->getLeafValue()); 221203954Srdivacky if (DI == 0) { 222234353Sdim errs() << "Unknown leaf kind: " << *N << "\n"; 223203954Srdivacky abort(); 224203954Srdivacky } 225218893Sdim 226203954Srdivacky Record *LeafRec = DI->getDef(); 227249423Sdim 228249423Sdim // A ValueType leaf node can represent a register when named, or itself when 229249423Sdim // unnamed. 230249423Sdim if (LeafRec->isSubClassOf("ValueType")) { 231249423Sdim // A named ValueType leaf always matches: (add i32:$a, i32:$b). 232249423Sdim if (N->hasName()) 233249423Sdim return; 234249423Sdim // An unnamed ValueType as in (sext_inreg GPR:$foo, i8). 235249423Sdim return AddMatcher(new CheckValueTypeMatcher(LeafRec->getName())); 236249423Sdim } 237249423Sdim 238203954Srdivacky if (// Handle register references. Nothing to do here, they always match. 239218893Sdim LeafRec->isSubClassOf("RegisterClass") || 240224145Sdim LeafRec->isSubClassOf("RegisterOperand") || 241203954Srdivacky LeafRec->isSubClassOf("PointerLikeRegClass") || 242208599Srdivacky LeafRec->isSubClassOf("SubRegIndex") || 243203954Srdivacky // Place holder for SRCVALUE nodes. Nothing to do here. 244203954Srdivacky LeafRec->getName() == "srcvalue") 245203954Srdivacky return; 246204642Srdivacky 247204642Srdivacky // If we have a physreg reference like (mul gpr:$src, EAX) then we need to 248218893Sdim // record the register 249204642Srdivacky if (LeafRec->isSubClassOf("Register")) { 250204642Srdivacky AddMatcher(new RecordMatcher("physreg input "+LeafRec->getName(), 251204642Srdivacky NextRecordedOperandNo)); 252204642Srdivacky PhysRegInputs.push_back(std::make_pair(LeafRec, NextRecordedOperandNo++)); 253204642Srdivacky return; 254204642Srdivacky } 255218893Sdim 256203954Srdivacky if (LeafRec->isSubClassOf("CondCode")) 257204642Srdivacky return AddMatcher(new CheckCondCodeMatcher(LeafRec->getName())); 258218893Sdim 259203954Srdivacky if (LeafRec->isSubClassOf("ComplexPattern")) { 260204642Srdivacky // We can't model ComplexPattern uses that don't have their name taken yet. 261204642Srdivacky // The OPC_CheckComplexPattern operation implicitly records the results. 262204642Srdivacky if (N->getName().empty()) { 263204642Srdivacky errs() << "We expect complex pattern uses to have names: " << *N << "\n"; 264204642Srdivacky exit(1); 265204642Srdivacky } 266204642Srdivacky 267204792Srdivacky // Remember this ComplexPattern so that we can emit it after all the other 268204792Srdivacky // structural matches are done. 269204792Srdivacky MatchedComplexPatterns.push_back(std::make_pair(N, 0)); 270204642Srdivacky return; 271203954Srdivacky } 272218893Sdim 273203954Srdivacky errs() << "Unknown leaf kind: " << *N << "\n"; 274203954Srdivacky abort(); 275203954Srdivacky} 276203954Srdivacky 277203954Srdivackyvoid MatcherGen::EmitOperatorMatchCode(const TreePatternNode *N, 278203954Srdivacky TreePatternNode *NodeNoTypes) { 279203954Srdivacky assert(!N->isLeaf() && "Not an operator?"); 280203954Srdivacky const SDNodeInfo &CInfo = CGP.getSDNodeInfo(N->getOperator()); 281218893Sdim 282203954Srdivacky // If this is an 'and R, 1234' where the operation is AND/OR and the RHS is 283203954Srdivacky // a constant without a predicate fn that has more that one bit set, handle 284203954Srdivacky // this as a special case. This is usually for targets that have special 285203954Srdivacky // handling of certain large constants (e.g. alpha with it's 8/16/32-bit 286203954Srdivacky // handling stuff). Using these instructions is often far more efficient 287203954Srdivacky // than materializing the constant. Unfortunately, both the instcombiner 288203954Srdivacky // and the dag combiner can often infer that bits are dead, and thus drop 289203954Srdivacky // them from the mask in the dag. For example, it might turn 'AND X, 255' 290203954Srdivacky // into 'AND X, 254' if it knows the low bit is set. Emit code that checks 291203954Srdivacky // to handle this. 292218893Sdim if ((N->getOperator()->getName() == "and" || 293203954Srdivacky N->getOperator()->getName() == "or") && 294204642Srdivacky N->getChild(1)->isLeaf() && N->getChild(1)->getPredicateFns().empty() && 295204642Srdivacky N->getPredicateFns().empty()) { 296243830Sdim if (IntInit *II = dyn_cast<IntInit>(N->getChild(1)->getLeafValue())) { 297203954Srdivacky if (!isPowerOf2_32(II->getValue())) { // Don't bother with single bits. 298204642Srdivacky // If this is at the root of the pattern, we emit a redundant 299204642Srdivacky // CheckOpcode so that the following checks get factored properly under 300204642Srdivacky // a single opcode check. 301204642Srdivacky if (N == Pattern.getSrcPattern()) 302204642Srdivacky AddMatcher(new CheckOpcodeMatcher(CInfo)); 303204642Srdivacky 304204642Srdivacky // Emit the CheckAndImm/CheckOrImm node. 305203954Srdivacky if (N->getOperator()->getName() == "and") 306204642Srdivacky AddMatcher(new CheckAndImmMatcher(II->getValue())); 307203954Srdivacky else 308204642Srdivacky AddMatcher(new CheckOrImmMatcher(II->getValue())); 309203954Srdivacky 310203954Srdivacky // Match the LHS of the AND as appropriate. 311204642Srdivacky AddMatcher(new MoveChildMatcher(0)); 312203954Srdivacky EmitMatchCode(N->getChild(0), NodeNoTypes->getChild(0)); 313204642Srdivacky AddMatcher(new MoveParentMatcher()); 314203954Srdivacky return; 315203954Srdivacky } 316203954Srdivacky } 317203954Srdivacky } 318218893Sdim 319203954Srdivacky // Check that the current opcode lines up. 320204642Srdivacky AddMatcher(new CheckOpcodeMatcher(CInfo)); 321218893Sdim 322204642Srdivacky // If this node has memory references (i.e. is a load or store), tell the 323204642Srdivacky // interpreter to capture them in the memref array. 324204642Srdivacky if (N->NodeHasProperty(SDNPMemOperand, CGP)) 325204642Srdivacky AddMatcher(new RecordMemRefMatcher()); 326218893Sdim 327203954Srdivacky // If this node has a chain, then the chain is operand #0 is the SDNode, and 328203954Srdivacky // the child numbers of the node are all offset by one. 329203954Srdivacky unsigned OpNo = 0; 330204642Srdivacky if (N->NodeHasProperty(SDNPHasChain, CGP)) { 331204642Srdivacky // Record the node and remember it in our chained nodes list. 332204642Srdivacky AddMatcher(new RecordMatcher("'" + N->getOperator()->getName() + 333204642Srdivacky "' chained node", 334204642Srdivacky NextRecordedOperandNo)); 335204642Srdivacky // Remember all of the input chains our pattern will match. 336204642Srdivacky MatchedChainNodes.push_back(NextRecordedOperandNo++); 337218893Sdim 338204642Srdivacky // Don't look at the input chain when matching the tree pattern to the 339204642Srdivacky // SDNode. 340203954Srdivacky OpNo = 1; 341203954Srdivacky 342204642Srdivacky // If this node is not the root and the subtree underneath it produces a 343204642Srdivacky // chain, then the result of matching the node is also produce a chain. 344204642Srdivacky // Beyond that, this means that we're also folding (at least) the root node 345204642Srdivacky // into the node that produce the chain (for example, matching 346204642Srdivacky // "(add reg, (load ptr))" as a add_with_memory on X86). This is 347204642Srdivacky // problematic, if the 'reg' node also uses the load (say, its chain). 348204642Srdivacky // Graphically: 349204642Srdivacky // 350204642Srdivacky // [LD] 351204642Srdivacky // ^ ^ 352204642Srdivacky // | \ DAG's like cheese. 353204642Srdivacky // / | 354204642Srdivacky // / [YY] 355204642Srdivacky // | ^ 356204642Srdivacky // [XX]--/ 357204642Srdivacky // 358204642Srdivacky // It would be invalid to fold XX and LD. In this case, folding the two 359204642Srdivacky // nodes together would induce a cycle in the DAG, making it a 'cyclic DAG' 360204642Srdivacky // To prevent this, we emit a dynamic check for legality before allowing 361204642Srdivacky // this to be folded. 362204642Srdivacky // 363204642Srdivacky const TreePatternNode *Root = Pattern.getSrcPattern(); 364204642Srdivacky if (N != Root) { // Not the root of the pattern. 365203954Srdivacky // If there is a node between the root and this node, then we definitely 366203954Srdivacky // need to emit the check. 367203954Srdivacky bool NeedCheck = !Root->hasChild(N); 368218893Sdim 369203954Srdivacky // If it *is* an immediate child of the root, we can still need a check if 370203954Srdivacky // the root SDNode has multiple inputs. For us, this means that it is an 371203954Srdivacky // intrinsic, has multiple operands, or has other inputs like chain or 372218893Sdim // glue). 373203954Srdivacky if (!NeedCheck) { 374203954Srdivacky const SDNodeInfo &PInfo = CGP.getSDNodeInfo(Root->getOperator()); 375203954Srdivacky NeedCheck = 376203954Srdivacky Root->getOperator() == CGP.get_intrinsic_void_sdnode() || 377203954Srdivacky Root->getOperator() == CGP.get_intrinsic_w_chain_sdnode() || 378203954Srdivacky Root->getOperator() == CGP.get_intrinsic_wo_chain_sdnode() || 379203954Srdivacky PInfo.getNumOperands() > 1 || 380203954Srdivacky PInfo.hasProperty(SDNPHasChain) || 381218893Sdim PInfo.hasProperty(SDNPInGlue) || 382218893Sdim PInfo.hasProperty(SDNPOptInGlue); 383203954Srdivacky } 384218893Sdim 385203954Srdivacky if (NeedCheck) 386204642Srdivacky AddMatcher(new CheckFoldableChainNodeMatcher()); 387203954Srdivacky } 388203954Srdivacky } 389204642Srdivacky 390218893Sdim // If this node has an output glue and isn't the root, remember it. 391218893Sdim if (N->NodeHasProperty(SDNPOutGlue, CGP) && 392204642Srdivacky N != Pattern.getSrcPattern()) { 393218893Sdim // TODO: This redundantly records nodes with both glues and chains. 394218893Sdim 395204642Srdivacky // Record the node and remember it in our chained nodes list. 396204642Srdivacky AddMatcher(new RecordMatcher("'" + N->getOperator()->getName() + 397218893Sdim "' glue output node", 398204642Srdivacky NextRecordedOperandNo)); 399218893Sdim // Remember all of the nodes with output glue our pattern will match. 400218893Sdim MatchedGlueResultNodes.push_back(NextRecordedOperandNo++); 401204642Srdivacky } 402218893Sdim 403218893Sdim // If this node is known to have an input glue or if it *might* have an input 404218893Sdim // glue, capture it as the glue input of the pattern. 405218893Sdim if (N->NodeHasProperty(SDNPOptInGlue, CGP) || 406218893Sdim N->NodeHasProperty(SDNPInGlue, CGP)) 407218893Sdim AddMatcher(new CaptureGlueInputMatcher()); 408218893Sdim 409203954Srdivacky for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) { 410203954Srdivacky // Get the code suitable for matching this child. Move to the child, check 411203954Srdivacky // it then move back to the parent. 412204642Srdivacky AddMatcher(new MoveChildMatcher(OpNo)); 413203954Srdivacky EmitMatchCode(N->getChild(i), NodeNoTypes->getChild(i)); 414204642Srdivacky AddMatcher(new MoveParentMatcher()); 415203954Srdivacky } 416203954Srdivacky} 417203954Srdivacky 418203954Srdivacky 419203954Srdivackyvoid MatcherGen::EmitMatchCode(const TreePatternNode *N, 420203954Srdivacky TreePatternNode *NodeNoTypes) { 421203954Srdivacky // If N and NodeNoTypes don't agree on a type, then this is a case where we 422203954Srdivacky // need to do a type check. Emit the check, apply the tyep to NodeNoTypes and 423203954Srdivacky // reinfer any correlated types. 424206083Srdivacky SmallVector<unsigned, 2> ResultsToTypeCheck; 425218893Sdim 426206083Srdivacky for (unsigned i = 0, e = NodeNoTypes->getNumTypes(); i != e; ++i) { 427206083Srdivacky if (NodeNoTypes->getExtType(i) == N->getExtType(i)) continue; 428206083Srdivacky NodeNoTypes->setType(i, N->getExtType(i)); 429203954Srdivacky InferPossibleTypes(); 430206083Srdivacky ResultsToTypeCheck.push_back(i); 431203954Srdivacky } 432218893Sdim 433203954Srdivacky // If this node has a name associated with it, capture it in VariableMap. If 434203954Srdivacky // we already saw this in the pattern, emit code to verify dagness. 435203954Srdivacky if (!N->getName().empty()) { 436203954Srdivacky unsigned &VarMapEntry = VariableMap[N->getName()]; 437203954Srdivacky if (VarMapEntry == 0) { 438204642Srdivacky // If it is a named node, we must emit a 'Record' opcode. 439204642Srdivacky AddMatcher(new RecordMatcher("$" + N->getName(), NextRecordedOperandNo)); 440203954Srdivacky VarMapEntry = ++NextRecordedOperandNo; 441203954Srdivacky } else { 442203954Srdivacky // If we get here, this is a second reference to a specific name. Since 443203954Srdivacky // we already have checked that the first reference is valid, we don't 444203954Srdivacky // have to recursively match it, just check that it's the same as the 445203954Srdivacky // previously named thing. 446204642Srdivacky AddMatcher(new CheckSameMatcher(VarMapEntry-1)); 447203954Srdivacky return; 448203954Srdivacky } 449203954Srdivacky } 450218893Sdim 451203954Srdivacky if (N->isLeaf()) 452203954Srdivacky EmitLeafMatchCode(N); 453203954Srdivacky else 454203954Srdivacky EmitOperatorMatchCode(N, NodeNoTypes); 455218893Sdim 456204961Srdivacky // If there are node predicates for this node, generate their checks. 457204961Srdivacky for (unsigned i = 0, e = N->getPredicateFns().size(); i != e; ++i) 458204961Srdivacky AddMatcher(new CheckPredicateMatcher(N->getPredicateFns()[i])); 459218893Sdim 460206083Srdivacky for (unsigned i = 0, e = ResultsToTypeCheck.size(); i != e; ++i) 461206083Srdivacky AddMatcher(new CheckTypeMatcher(N->getType(ResultsToTypeCheck[i]), 462206083Srdivacky ResultsToTypeCheck[i])); 463203954Srdivacky} 464203954Srdivacky 465204642Srdivacky/// EmitMatcherCode - Generate the code that matches the predicate of this 466204642Srdivacky/// pattern for the specified Variant. If the variant is invalid this returns 467204642Srdivacky/// true and does not generate code, if it is valid, it returns false. 468204642Srdivackybool MatcherGen::EmitMatcherCode(unsigned Variant) { 469204642Srdivacky // If the root of the pattern is a ComplexPattern and if it is specified to 470204642Srdivacky // match some number of root opcodes, these are considered to be our variants. 471204642Srdivacky // Depending on which variant we're generating code for, emit the root opcode 472204642Srdivacky // check. 473204642Srdivacky if (const ComplexPattern *CP = 474204642Srdivacky Pattern.getSrcPattern()->getComplexPatternInfo(CGP)) { 475204642Srdivacky const std::vector<Record*> &OpNodes = CP->getRootNodes(); 476204642Srdivacky assert(!OpNodes.empty() &&"Complex Pattern must specify what it can match"); 477204642Srdivacky if (Variant >= OpNodes.size()) return true; 478218893Sdim 479204642Srdivacky AddMatcher(new CheckOpcodeMatcher(CGP.getSDNodeInfo(OpNodes[Variant]))); 480204642Srdivacky } else { 481204642Srdivacky if (Variant != 0) return true; 482204642Srdivacky } 483218893Sdim 484204792Srdivacky // Emit the matcher for the pattern structure and types. 485204792Srdivacky EmitMatchCode(Pattern.getSrcPattern(), PatWithNoTypes); 486218893Sdim 487203954Srdivacky // If the pattern has a predicate on it (e.g. only enabled when a subtarget 488203954Srdivacky // feature is around, do the check). 489203954Srdivacky if (!Pattern.getPredicateCheck().empty()) 490204642Srdivacky AddMatcher(new CheckPatternPredicateMatcher(Pattern.getPredicateCheck())); 491218893Sdim 492204792Srdivacky // Now that we've completed the structural type match, emit any ComplexPattern 493204792Srdivacky // checks (e.g. addrmode matches). We emit this after the structural match 494204792Srdivacky // because they are generally more expensive to evaluate and more difficult to 495204792Srdivacky // factor. 496204792Srdivacky for (unsigned i = 0, e = MatchedComplexPatterns.size(); i != e; ++i) { 497204792Srdivacky const TreePatternNode *N = MatchedComplexPatterns[i].first; 498218893Sdim 499204792Srdivacky // Remember where the results of this match get stuck. 500204792Srdivacky MatchedComplexPatterns[i].second = NextRecordedOperandNo; 501204642Srdivacky 502204792Srdivacky // Get the slot we recorded the value in from the name on the node. 503204792Srdivacky unsigned RecNodeEntry = VariableMap[N->getName()]; 504204792Srdivacky assert(!N->getName().empty() && RecNodeEntry && 505204792Srdivacky "Complex pattern should have a name and slot"); 506204792Srdivacky --RecNodeEntry; // Entries in VariableMap are biased. 507218893Sdim 508204792Srdivacky const ComplexPattern &CP = 509204792Srdivacky CGP.getComplexPattern(((DefInit*)N->getLeafValue())->getDef()); 510218893Sdim 511204792Srdivacky // Emit a CheckComplexPat operation, which does the match (aborting if it 512204792Srdivacky // fails) and pushes the matched operands onto the recorded nodes list. 513204792Srdivacky AddMatcher(new CheckComplexPatMatcher(CP, RecNodeEntry, 514204792Srdivacky N->getName(), NextRecordedOperandNo)); 515218893Sdim 516204792Srdivacky // Record the right number of operands. 517204792Srdivacky NextRecordedOperandNo += CP.getNumOperands(); 518204792Srdivacky if (CP.hasProperty(SDNPHasChain)) { 519204792Srdivacky // If the complex pattern has a chain, then we need to keep track of the 520204792Srdivacky // fact that we just recorded a chain input. The chain input will be 521204792Srdivacky // matched as the last operand of the predicate if it was successful. 522204792Srdivacky ++NextRecordedOperandNo; // Chained node operand. 523218893Sdim 524204792Srdivacky // It is the last operand recorded. 525204792Srdivacky assert(NextRecordedOperandNo > 1 && 526204792Srdivacky "Should have recorded input/result chains at least!"); 527204792Srdivacky MatchedChainNodes.push_back(NextRecordedOperandNo-1); 528204792Srdivacky } 529218893Sdim 530218893Sdim // TODO: Complex patterns can't have output glues, if they did, we'd want 531204792Srdivacky // to record them. 532204792Srdivacky } 533218893Sdim 534204642Srdivacky return false; 535203954Srdivacky} 536203954Srdivacky 537203954Srdivacky 538204642Srdivacky//===----------------------------------------------------------------------===// 539204642Srdivacky// Node Result Generation 540204642Srdivacky//===----------------------------------------------------------------------===// 541204642Srdivacky 542204642Srdivackyvoid MatcherGen::EmitResultOfNamedOperand(const TreePatternNode *N, 543204642Srdivacky SmallVectorImpl<unsigned> &ResultOps){ 544204642Srdivacky assert(!N->getName().empty() && "Operand not named!"); 545218893Sdim 546204642Srdivacky // A reference to a complex pattern gets all of the results of the complex 547204642Srdivacky // pattern's match. 548204642Srdivacky if (const ComplexPattern *CP = N->getComplexPatternInfo(CGP)) { 549204792Srdivacky unsigned SlotNo = 0; 550204792Srdivacky for (unsigned i = 0, e = MatchedComplexPatterns.size(); i != e; ++i) 551204792Srdivacky if (MatchedComplexPatterns[i].first->getName() == N->getName()) { 552204792Srdivacky SlotNo = MatchedComplexPatterns[i].second; 553204792Srdivacky break; 554204792Srdivacky } 555204792Srdivacky assert(SlotNo != 0 && "Didn't get a slot number assigned?"); 556218893Sdim 557204642Srdivacky // The first slot entry is the node itself, the subsequent entries are the 558204642Srdivacky // matched values. 559204642Srdivacky for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i) 560204792Srdivacky ResultOps.push_back(SlotNo+i); 561204642Srdivacky return; 562204642Srdivacky } 563204642Srdivacky 564204792Srdivacky unsigned SlotNo = getNamedArgumentSlot(N->getName()); 565204792Srdivacky 566204642Srdivacky // If this is an 'imm' or 'fpimm' node, make sure to convert it to the target 567204642Srdivacky // version of the immediate so that it doesn't get selected due to some other 568204642Srdivacky // node use. 569204642Srdivacky if (!N->isLeaf()) { 570204642Srdivacky StringRef OperatorName = N->getOperator()->getName(); 571204642Srdivacky if (OperatorName == "imm" || OperatorName == "fpimm") { 572204642Srdivacky AddMatcher(new EmitConvertToTargetMatcher(SlotNo)); 573204642Srdivacky ResultOps.push_back(NextRecordedOperandNo++); 574204642Srdivacky return; 575204642Srdivacky } 576204642Srdivacky } 577218893Sdim 578204642Srdivacky ResultOps.push_back(SlotNo); 579204642Srdivacky} 580204642Srdivacky 581204642Srdivackyvoid MatcherGen::EmitResultLeafAsOperand(const TreePatternNode *N, 582204642Srdivacky SmallVectorImpl<unsigned> &ResultOps) { 583204642Srdivacky assert(N->isLeaf() && "Must be a leaf"); 584218893Sdim 585243830Sdim if (IntInit *II = dyn_cast<IntInit>(N->getLeafValue())) { 586205407Srdivacky AddMatcher(new EmitIntegerMatcher(II->getValue(), N->getType(0))); 587204642Srdivacky ResultOps.push_back(NextRecordedOperandNo++); 588204642Srdivacky return; 589204642Srdivacky } 590218893Sdim 591204642Srdivacky // If this is an explicit register reference, handle it. 592243830Sdim if (DefInit *DI = dyn_cast<DefInit>(N->getLeafValue())) { 593224145Sdim Record *Def = DI->getDef(); 594224145Sdim if (Def->isSubClassOf("Register")) { 595224145Sdim const CodeGenRegister *Reg = 596224145Sdim CGP.getTargetInfo().getRegBank().getReg(Def); 597224145Sdim AddMatcher(new EmitRegisterMatcher(Reg, N->getType(0))); 598204642Srdivacky ResultOps.push_back(NextRecordedOperandNo++); 599204642Srdivacky return; 600204642Srdivacky } 601218893Sdim 602224145Sdim if (Def->getName() == "zero_reg") { 603205407Srdivacky AddMatcher(new EmitRegisterMatcher(0, N->getType(0))); 604204642Srdivacky ResultOps.push_back(NextRecordedOperandNo++); 605204642Srdivacky return; 606204642Srdivacky } 607218893Sdim 608204642Srdivacky // Handle a reference to a register class. This is used 609204642Srdivacky // in COPY_TO_SUBREG instructions. 610224145Sdim if (Def->isSubClassOf("RegisterOperand")) 611224145Sdim Def = Def->getValueAsDef("RegClass"); 612224145Sdim if (Def->isSubClassOf("RegisterClass")) { 613224145Sdim std::string Value = getQualifiedName(Def) + "RegClassID"; 614204642Srdivacky AddMatcher(new EmitStringIntegerMatcher(Value, MVT::i32)); 615204642Srdivacky ResultOps.push_back(NextRecordedOperandNo++); 616204642Srdivacky return; 617204642Srdivacky } 618208599Srdivacky 619208599Srdivacky // Handle a subregister index. This is used for INSERT_SUBREG etc. 620224145Sdim if (Def->isSubClassOf("SubRegIndex")) { 621224145Sdim std::string Value = getQualifiedName(Def); 622208599Srdivacky AddMatcher(new EmitStringIntegerMatcher(Value, MVT::i32)); 623208599Srdivacky ResultOps.push_back(NextRecordedOperandNo++); 624208599Srdivacky return; 625208599Srdivacky } 626204642Srdivacky } 627218893Sdim 628204642Srdivacky errs() << "unhandled leaf node: \n"; 629204642Srdivacky N->dump(); 630204642Srdivacky} 631204642Srdivacky 632204642Srdivacky/// GetInstPatternNode - Get the pattern for an instruction. 633218893Sdim/// 634204642Srdivackyconst TreePatternNode *MatcherGen:: 635204642SrdivackyGetInstPatternNode(const DAGInstruction &Inst, const TreePatternNode *N) { 636204642Srdivacky const TreePattern *InstPat = Inst.getPattern(); 637218893Sdim 638204642Srdivacky // FIXME2?: Assume actual pattern comes before "implicit". 639204642Srdivacky TreePatternNode *InstPatNode; 640204642Srdivacky if (InstPat) 641204642Srdivacky InstPatNode = InstPat->getTree(0); 642204642Srdivacky else if (/*isRoot*/ N == Pattern.getDstPattern()) 643204642Srdivacky InstPatNode = Pattern.getSrcPattern(); 644204642Srdivacky else 645204642Srdivacky return 0; 646218893Sdim 647204642Srdivacky if (InstPatNode && !InstPatNode->isLeaf() && 648204642Srdivacky InstPatNode->getOperator()->getName() == "set") 649204642Srdivacky InstPatNode = InstPatNode->getChild(InstPatNode->getNumChildren()-1); 650218893Sdim 651204642Srdivacky return InstPatNode; 652204642Srdivacky} 653204642Srdivacky 654223017Sdimstatic bool 655223017SdimmayInstNodeLoadOrStore(const TreePatternNode *N, 656223017Sdim const CodeGenDAGPatterns &CGP) { 657223017Sdim Record *Op = N->getOperator(); 658223017Sdim const CodeGenTarget &CGT = CGP.getTargetInfo(); 659223017Sdim CodeGenInstruction &II = CGT.getInstruction(Op); 660223017Sdim return II.mayLoad || II.mayStore; 661223017Sdim} 662223017Sdim 663223017Sdimstatic unsigned 664223017SdimnumNodesThatMayLoadOrStore(const TreePatternNode *N, 665223017Sdim const CodeGenDAGPatterns &CGP) { 666223017Sdim if (N->isLeaf()) 667223017Sdim return 0; 668223017Sdim 669223017Sdim Record *OpRec = N->getOperator(); 670223017Sdim if (!OpRec->isSubClassOf("Instruction")) 671223017Sdim return 0; 672223017Sdim 673223017Sdim unsigned Count = 0; 674223017Sdim if (mayInstNodeLoadOrStore(N, CGP)) 675223017Sdim ++Count; 676223017Sdim 677223017Sdim for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 678223017Sdim Count += numNodesThatMayLoadOrStore(N->getChild(i), CGP); 679223017Sdim 680223017Sdim return Count; 681223017Sdim} 682223017Sdim 683204642Srdivackyvoid MatcherGen:: 684204642SrdivackyEmitResultInstructionAsOperand(const TreePatternNode *N, 685204642Srdivacky SmallVectorImpl<unsigned> &OutputOps) { 686204642Srdivacky Record *Op = N->getOperator(); 687204642Srdivacky const CodeGenTarget &CGT = CGP.getTargetInfo(); 688205407Srdivacky CodeGenInstruction &II = CGT.getInstruction(Op); 689204642Srdivacky const DAGInstruction &Inst = CGP.getInstruction(Op); 690218893Sdim 691204642Srdivacky // If we can, get the pattern for the instruction we're generating. We derive 692204642Srdivacky // a variety of information from this pattern, such as whether it has a chain. 693204642Srdivacky // 694204642Srdivacky // FIXME2: This is extremely dubious for several reasons, not the least of 695204642Srdivacky // which it gives special status to instructions with patterns that Pat<> 696204642Srdivacky // nodes can't duplicate. 697204642Srdivacky const TreePatternNode *InstPatNode = GetInstPatternNode(Inst, N); 698204642Srdivacky 699218893Sdim // NodeHasChain - Whether the instruction node we're creating takes chains. 700204642Srdivacky bool NodeHasChain = InstPatNode && 701204642Srdivacky InstPatNode->TreeHasProperty(SDNPHasChain, CGP); 702218893Sdim 703239462Sdim // Instructions which load and store from memory should have a chain, 704239462Sdim // regardless of whether they happen to have an internal pattern saying so. 705239462Sdim if (Pattern.getSrcPattern()->TreeHasProperty(SDNPHasChain, CGP) 706239462Sdim && (II.hasCtrlDep || II.mayLoad || II.mayStore || II.canFoldAsLoad || 707239462Sdim II.hasSideEffects)) 708239462Sdim NodeHasChain = true; 709239462Sdim 710204642Srdivacky bool isRoot = N == Pattern.getDstPattern(); 711204642Srdivacky 712218893Sdim // TreeHasOutGlue - True if this tree has glue. 713218893Sdim bool TreeHasInGlue = false, TreeHasOutGlue = false; 714204642Srdivacky if (isRoot) { 715204642Srdivacky const TreePatternNode *SrcPat = Pattern.getSrcPattern(); 716218893Sdim TreeHasInGlue = SrcPat->TreeHasProperty(SDNPOptInGlue, CGP) || 717218893Sdim SrcPat->TreeHasProperty(SDNPInGlue, CGP); 718218893Sdim 719204642Srdivacky // FIXME2: this is checking the entire pattern, not just the node in 720204642Srdivacky // question, doing this just for the root seems like a total hack. 721218893Sdim TreeHasOutGlue = SrcPat->TreeHasProperty(SDNPOutGlue, CGP); 722204642Srdivacky } 723204642Srdivacky 724204642Srdivacky // NumResults - This is the number of results produced by the instruction in 725204642Srdivacky // the "outs" list. 726218893Sdim unsigned NumResults = Inst.getNumResults(); 727204642Srdivacky 728204642Srdivacky // Loop over all of the operands of the instruction pattern, emitting code 729204642Srdivacky // to fill them all in. The node 'N' usually has number children equal to 730204642Srdivacky // the number of input operands of the instruction. However, in cases 731204642Srdivacky // where there are predicate operands for an instruction, we need to fill 732204642Srdivacky // in the 'execute always' values. Match up the node operands to the 733204642Srdivacky // instruction operands to do this. 734204642Srdivacky SmallVector<unsigned, 8> InstOps; 735218893Sdim for (unsigned ChildNo = 0, InstOpNo = NumResults, e = II.Operands.size(); 736204642Srdivacky InstOpNo != e; ++InstOpNo) { 737218893Sdim 738204642Srdivacky // Determine what to emit for this operand. 739218893Sdim Record *OperandNode = II.Operands[InstOpNo].Rec; 740243830Sdim if (OperandNode->isSubClassOf("OperandWithDefaultOps") && 741204642Srdivacky !CGP.getDefaultOperand(OperandNode).DefaultOps.empty()) { 742204642Srdivacky // This is a predicate or optional def operand; emit the 743204642Srdivacky // 'default ops' operands. 744212904Sdim const DAGDefaultOperand &DefaultOp 745218893Sdim = CGP.getDefaultOperand(OperandNode); 746204642Srdivacky for (unsigned i = 0, e = DefaultOp.DefaultOps.size(); i != e; ++i) 747204642Srdivacky EmitResultOperand(DefaultOp.DefaultOps[i], InstOps); 748204642Srdivacky continue; 749204642Srdivacky } 750218893Sdim 751204642Srdivacky // Otherwise this is a normal operand or a predicate operand without 752204642Srdivacky // 'execute always'; emit it. 753218893Sdim 754249423Sdim // For operands with multiple sub-operands we may need to emit 755249423Sdim // multiple child patterns to cover them all. However, ComplexPattern 756249423Sdim // children may themselves emit multiple MI operands. 757249423Sdim unsigned NumSubOps = 1; 758249423Sdim if (OperandNode->isSubClassOf("Operand")) { 759249423Sdim DagInit *MIOpInfo = OperandNode->getValueAsDag("MIOperandInfo"); 760249423Sdim if (unsigned NumArgs = MIOpInfo->getNumArgs()) 761249423Sdim NumSubOps = NumArgs; 762249423Sdim } 763218893Sdim 764249423Sdim unsigned FinalNumOps = InstOps.size() + NumSubOps; 765249423Sdim while (InstOps.size() < FinalNumOps) { 766249423Sdim const TreePatternNode *Child = N->getChild(ChildNo); 767249423Sdim unsigned BeforeAddingNumOps = InstOps.size(); 768249423Sdim EmitResultOperand(Child, InstOps); 769249423Sdim assert(InstOps.size() > BeforeAddingNumOps && "Didn't add any operands"); 770249423Sdim 771249423Sdim // If the operand is an instruction and it produced multiple results, just 772249423Sdim // take the first one. 773249423Sdim if (!Child->isLeaf() && Child->getOperator()->isSubClassOf("Instruction")) 774249423Sdim InstOps.resize(BeforeAddingNumOps+1); 775249423Sdim 776249423Sdim ++ChildNo; 777249423Sdim } 778204642Srdivacky } 779218893Sdim 780218893Sdim // If this node has input glue or explicitly specified input physregs, we 781218893Sdim // need to add chained and glued copyfromreg nodes and materialize the glue 782204642Srdivacky // input. 783204642Srdivacky if (isRoot && !PhysRegInputs.empty()) { 784204642Srdivacky // Emit all of the CopyToReg nodes for the input physical registers. These 785204642Srdivacky // occur in patterns like (mul:i8 AL:i8, GR8:i8:$src). 786204642Srdivacky for (unsigned i = 0, e = PhysRegInputs.size(); i != e; ++i) 787204642Srdivacky AddMatcher(new EmitCopyToRegMatcher(PhysRegInputs[i].second, 788205407Srdivacky PhysRegInputs[i].first)); 789218893Sdim // Even if the node has no other glue inputs, the resultant node must be 790218893Sdim // glued to the CopyFromReg nodes we just generated. 791218893Sdim TreeHasInGlue = true; 792204642Srdivacky } 793218893Sdim 794218893Sdim // Result order: node results, chain, glue 795218893Sdim 796204642Srdivacky // Determine the result types. 797204642Srdivacky SmallVector<MVT::SimpleValueType, 4> ResultVTs; 798206083Srdivacky for (unsigned i = 0, e = N->getNumTypes(); i != e; ++i) 799206083Srdivacky ResultVTs.push_back(N->getType(i)); 800218893Sdim 801204642Srdivacky // If this is the root instruction of a pattern that has physical registers in 802204642Srdivacky // its result pattern, add output VTs for them. For example, X86 has: 803204642Srdivacky // (set AL, (mul ...)) 804204642Srdivacky // This also handles implicit results like: 805204642Srdivacky // (implicit EFLAGS) 806206083Srdivacky if (isRoot && !Pattern.getDstRegs().empty()) { 807205407Srdivacky // If the root came from an implicit def in the instruction handling stuff, 808205407Srdivacky // don't re-add it. 809205407Srdivacky Record *HandledReg = 0; 810206083Srdivacky if (II.HasOneImplicitDefWithKnownVT(CGT) != MVT::Other) 811205407Srdivacky HandledReg = II.ImplicitDefs[0]; 812218893Sdim 813205407Srdivacky for (unsigned i = 0; i != Pattern.getDstRegs().size(); ++i) { 814205407Srdivacky Record *Reg = Pattern.getDstRegs()[i]; 815205407Srdivacky if (!Reg->isSubClassOf("Register") || Reg == HandledReg) continue; 816205407Srdivacky ResultVTs.push_back(getRegisterValueType(Reg, CGT)); 817205407Srdivacky } 818204642Srdivacky } 819204642Srdivacky 820205407Srdivacky // If this is the root of the pattern and the pattern we're matching includes 821205407Srdivacky // a node that is variadic, mark the generated node as variadic so that it 822205407Srdivacky // gets the excess operands from the input DAG. 823204642Srdivacky int NumFixedArityOperands = -1; 824205407Srdivacky if (isRoot && 825205407Srdivacky (Pattern.getSrcPattern()->NodeHasProperty(SDNPVariadic, CGP))) 826204642Srdivacky NumFixedArityOperands = Pattern.getSrcPattern()->getNumChildren(); 827218893Sdim 828223017Sdim // If this is the root node and multiple matched nodes in the input pattern 829223017Sdim // have MemRefs in them, have the interpreter collect them and plop them onto 830223017Sdim // this node. If there is just one node with MemRefs, leave them on that node 831223017Sdim // even if it is not the root. 832204642Srdivacky // 833223017Sdim // FIXME3: This is actively incorrect for result patterns with multiple 834223017Sdim // memory-referencing instructions. 835223017Sdim bool PatternHasMemOperands = 836223017Sdim Pattern.getSrcPattern()->TreeHasProperty(SDNPMemOperand, CGP); 837204642Srdivacky 838223017Sdim bool NodeHasMemRefs = false; 839223017Sdim if (PatternHasMemOperands) { 840223017Sdim unsigned NumNodesThatLoadOrStore = 841223017Sdim numNodesThatMayLoadOrStore(Pattern.getDstPattern(), CGP); 842223017Sdim bool NodeIsUniqueLoadOrStore = mayInstNodeLoadOrStore(N, CGP) && 843223017Sdim NumNodesThatLoadOrStore == 1; 844223017Sdim NodeHasMemRefs = 845223017Sdim NodeIsUniqueLoadOrStore || (isRoot && (mayInstNodeLoadOrStore(N, CGP) || 846223017Sdim NumNodesThatLoadOrStore != 1)); 847223017Sdim } 848223017Sdim 849218893Sdim assert((!ResultVTs.empty() || TreeHasOutGlue || NodeHasChain) && 850206083Srdivacky "Node has no result"); 851218893Sdim 852204642Srdivacky AddMatcher(new EmitNodeMatcher(II.Namespace+"::"+II.TheDef->getName(), 853204642Srdivacky ResultVTs.data(), ResultVTs.size(), 854204642Srdivacky InstOps.data(), InstOps.size(), 855218893Sdim NodeHasChain, TreeHasInGlue, TreeHasOutGlue, 856204642Srdivacky NodeHasMemRefs, NumFixedArityOperands, 857204642Srdivacky NextRecordedOperandNo)); 858218893Sdim 859218893Sdim // The non-chain and non-glue results of the newly emitted node get recorded. 860204642Srdivacky for (unsigned i = 0, e = ResultVTs.size(); i != e; ++i) { 861218893Sdim if (ResultVTs[i] == MVT::Other || ResultVTs[i] == MVT::Glue) break; 862204642Srdivacky OutputOps.push_back(NextRecordedOperandNo++); 863204642Srdivacky } 864204642Srdivacky} 865204642Srdivacky 866204642Srdivackyvoid MatcherGen:: 867204642SrdivackyEmitResultSDNodeXFormAsOperand(const TreePatternNode *N, 868204642Srdivacky SmallVectorImpl<unsigned> &ResultOps) { 869204642Srdivacky assert(N->getOperator()->isSubClassOf("SDNodeXForm") && "Not SDNodeXForm?"); 870204642Srdivacky 871204642Srdivacky // Emit the operand. 872204642Srdivacky SmallVector<unsigned, 8> InputOps; 873218893Sdim 874204642Srdivacky // FIXME2: Could easily generalize this to support multiple inputs and outputs 875204642Srdivacky // to the SDNodeXForm. For now we just support one input and one output like 876204642Srdivacky // the old instruction selector. 877204642Srdivacky assert(N->getNumChildren() == 1); 878204642Srdivacky EmitResultOperand(N->getChild(0), InputOps); 879204642Srdivacky 880204642Srdivacky // The input currently must have produced exactly one result. 881204642Srdivacky assert(InputOps.size() == 1 && "Unexpected input to SDNodeXForm"); 882204642Srdivacky 883204642Srdivacky AddMatcher(new EmitNodeXFormMatcher(InputOps[0], N->getOperator())); 884204642Srdivacky ResultOps.push_back(NextRecordedOperandNo++); 885204642Srdivacky} 886204642Srdivacky 887204642Srdivackyvoid MatcherGen::EmitResultOperand(const TreePatternNode *N, 888204642Srdivacky SmallVectorImpl<unsigned> &ResultOps) { 889204642Srdivacky // This is something selected from the pattern we matched. 890204642Srdivacky if (!N->getName().empty()) 891204642Srdivacky return EmitResultOfNamedOperand(N, ResultOps); 892204642Srdivacky 893204642Srdivacky if (N->isLeaf()) 894204642Srdivacky return EmitResultLeafAsOperand(N, ResultOps); 895204642Srdivacky 896204642Srdivacky Record *OpRec = N->getOperator(); 897204642Srdivacky if (OpRec->isSubClassOf("Instruction")) 898204642Srdivacky return EmitResultInstructionAsOperand(N, ResultOps); 899204642Srdivacky if (OpRec->isSubClassOf("SDNodeXForm")) 900204642Srdivacky return EmitResultSDNodeXFormAsOperand(N, ResultOps); 901204642Srdivacky errs() << "Unknown result node to emit code for: " << *N << '\n'; 902243830Sdim PrintFatalError("Unknown node in result pattern!"); 903204642Srdivacky} 904204642Srdivacky 905204642Srdivackyvoid MatcherGen::EmitResultCode() { 906204642Srdivacky // Patterns that match nodes with (potentially multiple) chain inputs have to 907204642Srdivacky // merge them together into a token factor. This informs the generated code 908204642Srdivacky // what all the chained nodes are. 909204642Srdivacky if (!MatchedChainNodes.empty()) 910204642Srdivacky AddMatcher(new EmitMergeInputChainsMatcher 911204642Srdivacky (MatchedChainNodes.data(), MatchedChainNodes.size())); 912218893Sdim 913204642Srdivacky // Codegen the root of the result pattern, capturing the resulting values. 914204642Srdivacky SmallVector<unsigned, 8> Ops; 915204642Srdivacky EmitResultOperand(Pattern.getDstPattern(), Ops); 916204642Srdivacky 917204642Srdivacky // At this point, we have however many values the result pattern produces. 918204642Srdivacky // However, the input pattern might not need all of these. If there are 919206083Srdivacky // excess values at the end (such as implicit defs of condition codes etc) 920218893Sdim // just lop them off. This doesn't need to worry about glue or chains, just 921206083Srdivacky // explicit results. 922204642Srdivacky // 923206083Srdivacky unsigned NumSrcResults = Pattern.getSrcPattern()->getNumTypes(); 924218893Sdim 925206083Srdivacky // If the pattern also has (implicit) results, count them as well. 926206083Srdivacky if (!Pattern.getDstRegs().empty()) { 927206083Srdivacky // If the root came from an implicit def in the instruction handling stuff, 928206083Srdivacky // don't re-add it. 929206083Srdivacky Record *HandledReg = 0; 930206083Srdivacky const TreePatternNode *DstPat = Pattern.getDstPattern(); 931206083Srdivacky if (!DstPat->isLeaf() &&DstPat->getOperator()->isSubClassOf("Instruction")){ 932206083Srdivacky const CodeGenTarget &CGT = CGP.getTargetInfo(); 933206083Srdivacky CodeGenInstruction &II = CGT.getInstruction(DstPat->getOperator()); 934206083Srdivacky 935206083Srdivacky if (II.HasOneImplicitDefWithKnownVT(CGT) != MVT::Other) 936206083Srdivacky HandledReg = II.ImplicitDefs[0]; 937206083Srdivacky } 938218893Sdim 939206083Srdivacky for (unsigned i = 0; i != Pattern.getDstRegs().size(); ++i) { 940206083Srdivacky Record *Reg = Pattern.getDstRegs()[i]; 941206083Srdivacky if (!Reg->isSubClassOf("Register") || Reg == HandledReg) continue; 942206083Srdivacky ++NumSrcResults; 943206083Srdivacky } 944218893Sdim } 945218893Sdim 946204642Srdivacky assert(Ops.size() >= NumSrcResults && "Didn't provide enough results"); 947204642Srdivacky Ops.resize(NumSrcResults); 948204642Srdivacky 949218893Sdim // If the matched pattern covers nodes which define a glue result, emit a node 950204642Srdivacky // that tells the matcher about them so that it can update their results. 951218893Sdim if (!MatchedGlueResultNodes.empty()) 952218893Sdim AddMatcher(new MarkGlueResultsMatcher(MatchedGlueResultNodes.data(), 953218893Sdim MatchedGlueResultNodes.size())); 954218893Sdim 955204642Srdivacky AddMatcher(new CompleteMatchMatcher(Ops.data(), Ops.size(), Pattern)); 956204642Srdivacky} 957204642Srdivacky 958204642Srdivacky 959204642Srdivacky/// ConvertPatternToMatcher - Create the matcher for the specified pattern with 960204642Srdivacky/// the specified variant. If the variant number is invalid, this returns null. 961204642SrdivackyMatcher *llvm::ConvertPatternToMatcher(const PatternToMatch &Pattern, 962204642Srdivacky unsigned Variant, 963204642Srdivacky const CodeGenDAGPatterns &CGP) { 964203954Srdivacky MatcherGen Gen(Pattern, CGP); 965203954Srdivacky 966203954Srdivacky // Generate the code for the matcher. 967204642Srdivacky if (Gen.EmitMatcherCode(Variant)) 968204642Srdivacky return 0; 969218893Sdim 970204642Srdivacky // FIXME2: Kill extra MoveParent commands at the end of the matcher sequence. 971204642Srdivacky // FIXME2: Split result code out to another table, and make the matcher end 972204642Srdivacky // with an "Emit <index>" command. This allows result generation stuff to be 973204642Srdivacky // shared and factored? 974218893Sdim 975203954Srdivacky // If the match succeeds, then we generate Pattern. 976204642Srdivacky Gen.EmitResultCode(); 977203954Srdivacky 978203954Srdivacky // Unconditional match. 979204642Srdivacky return Gen.GetMatcher(); 980203954Srdivacky} 981