DAGISelMatcherGen.cpp revision 223017
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" 13203954Srdivacky#include "Record.h" 14221345Sdim#include "llvm/ADT/DenseMap.h" 15204642Srdivacky#include "llvm/ADT/SmallVector.h" 16203954Srdivacky#include "llvm/ADT/StringMap.h" 17204642Srdivacky#include <utility> 18203954Srdivackyusing namespace llvm; 19203954Srdivacky 20204642Srdivacky 21204642Srdivacky/// getRegisterValueType - Look up and return the ValueType of the specified 22204642Srdivacky/// register. If the register is a member of multiple register classes which 23204642Srdivacky/// have different associated types, return MVT::Other. 24204642Srdivackystatic MVT::SimpleValueType getRegisterValueType(Record *R, 25204642Srdivacky const CodeGenTarget &T) { 26204642Srdivacky bool FoundRC = false; 27204642Srdivacky MVT::SimpleValueType VT = MVT::Other; 28204642Srdivacky const std::vector<CodeGenRegisterClass> &RCs = T.getRegisterClasses(); 29204642Srdivacky std::vector<Record*>::const_iterator Element; 30218893Sdim 31204642Srdivacky for (unsigned rc = 0, e = RCs.size(); rc != e; ++rc) { 32204642Srdivacky const CodeGenRegisterClass &RC = RCs[rc]; 33204642Srdivacky if (!std::count(RC.Elements.begin(), RC.Elements.end(), R)) 34204642Srdivacky continue; 35218893Sdim 36204642Srdivacky if (!FoundRC) { 37204642Srdivacky FoundRC = true; 38204642Srdivacky VT = RC.getValueTypeNum(0); 39204642Srdivacky continue; 40204642Srdivacky } 41204642Srdivacky 42204642Srdivacky // If this occurs in multiple register classes, they all have to agree. 43204642Srdivacky assert(VT == RC.getValueTypeNum(0)); 44204642Srdivacky } 45204642Srdivacky return VT; 46204642Srdivacky} 47204642Srdivacky 48204642Srdivacky 49203954Srdivackynamespace { 50203954Srdivacky class MatcherGen { 51203954Srdivacky const PatternToMatch &Pattern; 52203954Srdivacky const CodeGenDAGPatterns &CGP; 53218893Sdim 54203954Srdivacky /// PatWithNoTypes - This is a clone of Pattern.getSrcPattern() that starts 55203954Srdivacky /// out with all of the types removed. This allows us to insert type checks 56203954Srdivacky /// as we scan the tree. 57203954Srdivacky TreePatternNode *PatWithNoTypes; 58218893Sdim 59203954Srdivacky /// VariableMap - A map from variable names ('$dst') to the recorded operand 60203954Srdivacky /// number that they were captured as. These are biased by 1 to make 61203954Srdivacky /// insertion easier. 62203954Srdivacky StringMap<unsigned> VariableMap; 63218893Sdim 64204642Srdivacky /// NextRecordedOperandNo - As we emit opcodes to record matched values in 65204642Srdivacky /// the RecordedNodes array, this keeps track of which slot will be next to 66204642Srdivacky /// record into. 67203954Srdivacky unsigned NextRecordedOperandNo; 68218893Sdim 69204642Srdivacky /// MatchedChainNodes - This maintains the position in the recorded nodes 70204642Srdivacky /// array of all of the recorded input nodes that have chains. 71204642Srdivacky SmallVector<unsigned, 2> MatchedChainNodes; 72204642Srdivacky 73218893Sdim /// MatchedGlueResultNodes - This maintains the position in the recorded 74218893Sdim /// nodes array of all of the recorded input nodes that have glue results. 75218893Sdim SmallVector<unsigned, 2> MatchedGlueResultNodes; 76218893Sdim 77204792Srdivacky /// MatchedComplexPatterns - This maintains a list of all of the 78204792Srdivacky /// ComplexPatterns that we need to check. The patterns are known to have 79204792Srdivacky /// names which were recorded. The second element of each pair is the first 80204792Srdivacky /// slot number that the OPC_CheckComplexPat opcode drops the matched 81204792Srdivacky /// results into. 82204792Srdivacky SmallVector<std::pair<const TreePatternNode*, 83204792Srdivacky unsigned>, 2> MatchedComplexPatterns; 84218893Sdim 85204642Srdivacky /// PhysRegInputs - List list has an entry for each explicitly specified 86204642Srdivacky /// physreg input to the pattern. The first elt is the Register node, the 87204642Srdivacky /// second is the recorded slot number the input pattern match saved it in. 88204642Srdivacky SmallVector<std::pair<Record*, unsigned>, 2> PhysRegInputs; 89218893Sdim 90204642Srdivacky /// Matcher - This is the top level of the generated matcher, the result. 91204642Srdivacky Matcher *TheMatcher; 92218893Sdim 93204642Srdivacky /// CurPredicate - As we emit matcher nodes, this points to the latest check 94204642Srdivacky /// which should have future checks stuck into its Next position. 95204642Srdivacky Matcher *CurPredicate; 96221345Sdim 97221345Sdim /// RegisterDefMap - A map of register record definitions to the 98221345Sdim /// corresponding target CodeGenRegister entry. 99221345Sdim DenseMap<const Record *, const CodeGenRegister *> RegisterDefMap; 100203954Srdivacky public: 101203954Srdivacky MatcherGen(const PatternToMatch &pattern, const CodeGenDAGPatterns &cgp); 102218893Sdim 103203954Srdivacky ~MatcherGen() { 104203954Srdivacky delete PatWithNoTypes; 105203954Srdivacky } 106218893Sdim 107204642Srdivacky bool EmitMatcherCode(unsigned Variant); 108204642Srdivacky void EmitResultCode(); 109218893Sdim 110204642Srdivacky Matcher *GetMatcher() const { return TheMatcher; } 111203954Srdivacky private: 112204642Srdivacky void AddMatcher(Matcher *NewNode); 113203954Srdivacky void InferPossibleTypes(); 114218893Sdim 115204642Srdivacky // Matcher Generation. 116203954Srdivacky void EmitMatchCode(const TreePatternNode *N, TreePatternNode *NodeNoTypes); 117203954Srdivacky void EmitLeafMatchCode(const TreePatternNode *N); 118203954Srdivacky void EmitOperatorMatchCode(const TreePatternNode *N, 119203954Srdivacky TreePatternNode *NodeNoTypes); 120218893Sdim 121204642Srdivacky // Result Code Generation. 122204642Srdivacky unsigned getNamedArgumentSlot(StringRef Name) { 123204642Srdivacky unsigned VarMapEntry = VariableMap[Name]; 124204642Srdivacky assert(VarMapEntry != 0 && 125204642Srdivacky "Variable referenced but not defined and not caught earlier!"); 126204642Srdivacky return VarMapEntry-1; 127204642Srdivacky } 128204642Srdivacky 129204642Srdivacky /// GetInstPatternNode - Get the pattern for an instruction. 130204642Srdivacky const TreePatternNode *GetInstPatternNode(const DAGInstruction &Ins, 131204642Srdivacky const TreePatternNode *N); 132218893Sdim 133204642Srdivacky void EmitResultOperand(const TreePatternNode *N, 134204642Srdivacky SmallVectorImpl<unsigned> &ResultOps); 135204642Srdivacky void EmitResultOfNamedOperand(const TreePatternNode *N, 136204642Srdivacky SmallVectorImpl<unsigned> &ResultOps); 137204642Srdivacky void EmitResultLeafAsOperand(const TreePatternNode *N, 138204642Srdivacky SmallVectorImpl<unsigned> &ResultOps); 139204642Srdivacky void EmitResultInstructionAsOperand(const TreePatternNode *N, 140204642Srdivacky SmallVectorImpl<unsigned> &ResultOps); 141204642Srdivacky void EmitResultSDNodeXFormAsOperand(const TreePatternNode *N, 142204642Srdivacky SmallVectorImpl<unsigned> &ResultOps); 143204642Srdivacky }; 144218893Sdim 145203954Srdivacky} // end anon namespace. 146203954Srdivacky 147203954SrdivackyMatcherGen::MatcherGen(const PatternToMatch &pattern, 148203954Srdivacky const CodeGenDAGPatterns &cgp) 149203954Srdivacky: Pattern(pattern), CGP(cgp), NextRecordedOperandNo(0), 150204642Srdivacky TheMatcher(0), CurPredicate(0) { 151203954Srdivacky // We need to produce the matcher tree for the patterns source pattern. To do 152203954Srdivacky // this we need to match the structure as well as the types. To do the type 153203954Srdivacky // matching, we want to figure out the fewest number of type checks we need to 154203954Srdivacky // emit. For example, if there is only one integer type supported by a 155203954Srdivacky // target, there should be no type comparisons at all for integer patterns! 156203954Srdivacky // 157203954Srdivacky // To figure out the fewest number of type checks needed, clone the pattern, 158203954Srdivacky // remove the types, then perform type inference on the pattern as a whole. 159203954Srdivacky // If there are unresolved types, emit an explicit check for those types, 160203954Srdivacky // apply the type to the tree, then rerun type inference. Iterate until all 161203954Srdivacky // types are resolved. 162203954Srdivacky // 163203954Srdivacky PatWithNoTypes = Pattern.getSrcPattern()->clone(); 164203954Srdivacky PatWithNoTypes->RemoveAllTypes(); 165218893Sdim 166203954Srdivacky // If there are types that are manifestly known, infer them. 167203954Srdivacky InferPossibleTypes(); 168221345Sdim 169221345Sdim // Populate the map from records to CodeGenRegister entries. 170221345Sdim const CodeGenTarget &CGT = CGP.getTargetInfo(); 171221345Sdim const std::vector<CodeGenRegister> &Registers = CGT.getRegisters(); 172221345Sdim for (unsigned i = 0, e = Registers.size(); i != e; ++i) 173221345Sdim RegisterDefMap[Registers[i].TheDef] = &Registers[i]; 174203954Srdivacky} 175203954Srdivacky 176203954Srdivacky/// InferPossibleTypes - As we emit the pattern, we end up generating type 177203954Srdivacky/// checks and applying them to the 'PatWithNoTypes' tree. As we do this, we 178203954Srdivacky/// want to propagate implied types as far throughout the tree as possible so 179203954Srdivacky/// that we avoid doing redundant type checks. This does the type propagation. 180203954Srdivackyvoid MatcherGen::InferPossibleTypes() { 181203954Srdivacky // TP - Get *SOME* tree pattern, we don't care which. It is only used for 182203954Srdivacky // diagnostics, which we know are impossible at this point. 183203954Srdivacky TreePattern &TP = *CGP.pf_begin()->second; 184218893Sdim 185203954Srdivacky try { 186203954Srdivacky bool MadeChange = true; 187203954Srdivacky while (MadeChange) 188203954Srdivacky MadeChange = PatWithNoTypes->ApplyTypeConstraints(TP, 189203954Srdivacky true/*Ignore reg constraints*/); 190203954Srdivacky } catch (...) { 191203954Srdivacky errs() << "Type constraint application shouldn't fail!"; 192203954Srdivacky abort(); 193203954Srdivacky } 194203954Srdivacky} 195203954Srdivacky 196203954Srdivacky 197218893Sdim/// AddMatcher - Add a matcher node to the current graph we're building. 198204642Srdivackyvoid MatcherGen::AddMatcher(Matcher *NewNode) { 199203954Srdivacky if (CurPredicate != 0) 200204642Srdivacky CurPredicate->setNext(NewNode); 201203954Srdivacky else 202204642Srdivacky TheMatcher = NewNode; 203203954Srdivacky CurPredicate = NewNode; 204203954Srdivacky} 205203954Srdivacky 206203954Srdivacky 207204642Srdivacky//===----------------------------------------------------------------------===// 208204642Srdivacky// Pattern Match Generation 209204642Srdivacky//===----------------------------------------------------------------------===// 210203954Srdivacky 211203954Srdivacky/// EmitLeafMatchCode - Generate matching code for leaf nodes. 212203954Srdivackyvoid MatcherGen::EmitLeafMatchCode(const TreePatternNode *N) { 213203954Srdivacky assert(N->isLeaf() && "Not a leaf?"); 214218893Sdim 215203954Srdivacky // Direct match against an integer constant. 216204642Srdivacky if (IntInit *II = dynamic_cast<IntInit*>(N->getLeafValue())) { 217204642Srdivacky // If this is the root of the dag we're matching, we emit a redundant opcode 218204642Srdivacky // check to ensure that this gets folded into the normal top-level 219204642Srdivacky // OpcodeSwitch. 220204642Srdivacky if (N == Pattern.getSrcPattern()) { 221204642Srdivacky const SDNodeInfo &NI = CGP.getSDNodeInfo(CGP.getSDNodeNamed("imm")); 222204642Srdivacky AddMatcher(new CheckOpcodeMatcher(NI)); 223204642Srdivacky } 224204642Srdivacky 225204642Srdivacky return AddMatcher(new CheckIntegerMatcher(II->getValue())); 226204642Srdivacky } 227218893Sdim 228203954Srdivacky DefInit *DI = dynamic_cast<DefInit*>(N->getLeafValue()); 229203954Srdivacky if (DI == 0) { 230203954Srdivacky errs() << "Unknown leaf kind: " << *DI << "\n"; 231203954Srdivacky abort(); 232203954Srdivacky } 233218893Sdim 234203954Srdivacky Record *LeafRec = DI->getDef(); 235203954Srdivacky if (// Handle register references. Nothing to do here, they always match. 236218893Sdim LeafRec->isSubClassOf("RegisterClass") || 237203954Srdivacky LeafRec->isSubClassOf("PointerLikeRegClass") || 238208599Srdivacky LeafRec->isSubClassOf("SubRegIndex") || 239203954Srdivacky // Place holder for SRCVALUE nodes. Nothing to do here. 240203954Srdivacky LeafRec->getName() == "srcvalue") 241203954Srdivacky return; 242204642Srdivacky 243204642Srdivacky // If we have a physreg reference like (mul gpr:$src, EAX) then we need to 244218893Sdim // record the register 245204642Srdivacky if (LeafRec->isSubClassOf("Register")) { 246204642Srdivacky AddMatcher(new RecordMatcher("physreg input "+LeafRec->getName(), 247204642Srdivacky NextRecordedOperandNo)); 248204642Srdivacky PhysRegInputs.push_back(std::make_pair(LeafRec, NextRecordedOperandNo++)); 249204642Srdivacky return; 250204642Srdivacky } 251218893Sdim 252203954Srdivacky if (LeafRec->isSubClassOf("ValueType")) 253204642Srdivacky return AddMatcher(new CheckValueTypeMatcher(LeafRec->getName())); 254218893Sdim 255203954Srdivacky if (LeafRec->isSubClassOf("CondCode")) 256204642Srdivacky return AddMatcher(new CheckCondCodeMatcher(LeafRec->getName())); 257218893Sdim 258203954Srdivacky if (LeafRec->isSubClassOf("ComplexPattern")) { 259204642Srdivacky // We can't model ComplexPattern uses that don't have their name taken yet. 260204642Srdivacky // The OPC_CheckComplexPattern operation implicitly records the results. 261204642Srdivacky if (N->getName().empty()) { 262204642Srdivacky errs() << "We expect complex pattern uses to have names: " << *N << "\n"; 263204642Srdivacky exit(1); 264204642Srdivacky } 265204642Srdivacky 266204792Srdivacky // Remember this ComplexPattern so that we can emit it after all the other 267204792Srdivacky // structural matches are done. 268204792Srdivacky MatchedComplexPatterns.push_back(std::make_pair(N, 0)); 269204642Srdivacky return; 270203954Srdivacky } 271218893Sdim 272203954Srdivacky errs() << "Unknown leaf kind: " << *N << "\n"; 273203954Srdivacky abort(); 274203954Srdivacky} 275203954Srdivacky 276203954Srdivackyvoid MatcherGen::EmitOperatorMatchCode(const TreePatternNode *N, 277203954Srdivacky TreePatternNode *NodeNoTypes) { 278203954Srdivacky assert(!N->isLeaf() && "Not an operator?"); 279203954Srdivacky const SDNodeInfo &CInfo = CGP.getSDNodeInfo(N->getOperator()); 280218893Sdim 281203954Srdivacky // If this is an 'and R, 1234' where the operation is AND/OR and the RHS is 282203954Srdivacky // a constant without a predicate fn that has more that one bit set, handle 283203954Srdivacky // this as a special case. This is usually for targets that have special 284203954Srdivacky // handling of certain large constants (e.g. alpha with it's 8/16/32-bit 285203954Srdivacky // handling stuff). Using these instructions is often far more efficient 286203954Srdivacky // than materializing the constant. Unfortunately, both the instcombiner 287203954Srdivacky // and the dag combiner can often infer that bits are dead, and thus drop 288203954Srdivacky // them from the mask in the dag. For example, it might turn 'AND X, 255' 289203954Srdivacky // into 'AND X, 254' if it knows the low bit is set. Emit code that checks 290203954Srdivacky // to handle this. 291218893Sdim if ((N->getOperator()->getName() == "and" || 292203954Srdivacky N->getOperator()->getName() == "or") && 293204642Srdivacky N->getChild(1)->isLeaf() && N->getChild(1)->getPredicateFns().empty() && 294204642Srdivacky N->getPredicateFns().empty()) { 295203954Srdivacky if (IntInit *II = dynamic_cast<IntInit*>(N->getChild(1)->getLeafValue())) { 296203954Srdivacky if (!isPowerOf2_32(II->getValue())) { // Don't bother with single bits. 297204642Srdivacky // If this is at the root of the pattern, we emit a redundant 298204642Srdivacky // CheckOpcode so that the following checks get factored properly under 299204642Srdivacky // a single opcode check. 300204642Srdivacky if (N == Pattern.getSrcPattern()) 301204642Srdivacky AddMatcher(new CheckOpcodeMatcher(CInfo)); 302204642Srdivacky 303204642Srdivacky // Emit the CheckAndImm/CheckOrImm node. 304203954Srdivacky if (N->getOperator()->getName() == "and") 305204642Srdivacky AddMatcher(new CheckAndImmMatcher(II->getValue())); 306203954Srdivacky else 307204642Srdivacky AddMatcher(new CheckOrImmMatcher(II->getValue())); 308203954Srdivacky 309203954Srdivacky // Match the LHS of the AND as appropriate. 310204642Srdivacky AddMatcher(new MoveChildMatcher(0)); 311203954Srdivacky EmitMatchCode(N->getChild(0), NodeNoTypes->getChild(0)); 312204642Srdivacky AddMatcher(new MoveParentMatcher()); 313203954Srdivacky return; 314203954Srdivacky } 315203954Srdivacky } 316203954Srdivacky } 317218893Sdim 318203954Srdivacky // Check that the current opcode lines up. 319204642Srdivacky AddMatcher(new CheckOpcodeMatcher(CInfo)); 320218893Sdim 321204642Srdivacky // If this node has memory references (i.e. is a load or store), tell the 322204642Srdivacky // interpreter to capture them in the memref array. 323204642Srdivacky if (N->NodeHasProperty(SDNPMemOperand, CGP)) 324204642Srdivacky AddMatcher(new RecordMemRefMatcher()); 325218893Sdim 326203954Srdivacky // If this node has a chain, then the chain is operand #0 is the SDNode, and 327203954Srdivacky // the child numbers of the node are all offset by one. 328203954Srdivacky unsigned OpNo = 0; 329204642Srdivacky if (N->NodeHasProperty(SDNPHasChain, CGP)) { 330204642Srdivacky // Record the node and remember it in our chained nodes list. 331204642Srdivacky AddMatcher(new RecordMatcher("'" + N->getOperator()->getName() + 332204642Srdivacky "' chained node", 333204642Srdivacky NextRecordedOperandNo)); 334204642Srdivacky // Remember all of the input chains our pattern will match. 335204642Srdivacky MatchedChainNodes.push_back(NextRecordedOperandNo++); 336218893Sdim 337204642Srdivacky // Don't look at the input chain when matching the tree pattern to the 338204642Srdivacky // SDNode. 339203954Srdivacky OpNo = 1; 340203954Srdivacky 341204642Srdivacky // If this node is not the root and the subtree underneath it produces a 342204642Srdivacky // chain, then the result of matching the node is also produce a chain. 343204642Srdivacky // Beyond that, this means that we're also folding (at least) the root node 344204642Srdivacky // into the node that produce the chain (for example, matching 345204642Srdivacky // "(add reg, (load ptr))" as a add_with_memory on X86). This is 346204642Srdivacky // problematic, if the 'reg' node also uses the load (say, its chain). 347204642Srdivacky // Graphically: 348204642Srdivacky // 349204642Srdivacky // [LD] 350204642Srdivacky // ^ ^ 351204642Srdivacky // | \ DAG's like cheese. 352204642Srdivacky // / | 353204642Srdivacky // / [YY] 354204642Srdivacky // | ^ 355204642Srdivacky // [XX]--/ 356204642Srdivacky // 357204642Srdivacky // It would be invalid to fold XX and LD. In this case, folding the two 358204642Srdivacky // nodes together would induce a cycle in the DAG, making it a 'cyclic DAG' 359204642Srdivacky // To prevent this, we emit a dynamic check for legality before allowing 360204642Srdivacky // this to be folded. 361204642Srdivacky // 362204642Srdivacky const TreePatternNode *Root = Pattern.getSrcPattern(); 363204642Srdivacky if (N != Root) { // Not the root of the pattern. 364203954Srdivacky // If there is a node between the root and this node, then we definitely 365203954Srdivacky // need to emit the check. 366203954Srdivacky bool NeedCheck = !Root->hasChild(N); 367218893Sdim 368203954Srdivacky // If it *is* an immediate child of the root, we can still need a check if 369203954Srdivacky // the root SDNode has multiple inputs. For us, this means that it is an 370203954Srdivacky // intrinsic, has multiple operands, or has other inputs like chain or 371218893Sdim // glue). 372203954Srdivacky if (!NeedCheck) { 373203954Srdivacky const SDNodeInfo &PInfo = CGP.getSDNodeInfo(Root->getOperator()); 374203954Srdivacky NeedCheck = 375203954Srdivacky Root->getOperator() == CGP.get_intrinsic_void_sdnode() || 376203954Srdivacky Root->getOperator() == CGP.get_intrinsic_w_chain_sdnode() || 377203954Srdivacky Root->getOperator() == CGP.get_intrinsic_wo_chain_sdnode() || 378203954Srdivacky PInfo.getNumOperands() > 1 || 379203954Srdivacky PInfo.hasProperty(SDNPHasChain) || 380218893Sdim PInfo.hasProperty(SDNPInGlue) || 381218893Sdim PInfo.hasProperty(SDNPOptInGlue); 382203954Srdivacky } 383218893Sdim 384203954Srdivacky if (NeedCheck) 385204642Srdivacky AddMatcher(new CheckFoldableChainNodeMatcher()); 386203954Srdivacky } 387203954Srdivacky } 388204642Srdivacky 389218893Sdim // If this node has an output glue and isn't the root, remember it. 390218893Sdim if (N->NodeHasProperty(SDNPOutGlue, CGP) && 391204642Srdivacky N != Pattern.getSrcPattern()) { 392218893Sdim // TODO: This redundantly records nodes with both glues and chains. 393218893Sdim 394204642Srdivacky // Record the node and remember it in our chained nodes list. 395204642Srdivacky AddMatcher(new RecordMatcher("'" + N->getOperator()->getName() + 396218893Sdim "' glue output node", 397204642Srdivacky NextRecordedOperandNo)); 398218893Sdim // Remember all of the nodes with output glue our pattern will match. 399218893Sdim MatchedGlueResultNodes.push_back(NextRecordedOperandNo++); 400204642Srdivacky } 401218893Sdim 402218893Sdim // If this node is known to have an input glue or if it *might* have an input 403218893Sdim // glue, capture it as the glue input of the pattern. 404218893Sdim if (N->NodeHasProperty(SDNPOptInGlue, CGP) || 405218893Sdim N->NodeHasProperty(SDNPInGlue, CGP)) 406218893Sdim AddMatcher(new CaptureGlueInputMatcher()); 407218893Sdim 408203954Srdivacky for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) { 409203954Srdivacky // Get the code suitable for matching this child. Move to the child, check 410203954Srdivacky // it then move back to the parent. 411204642Srdivacky AddMatcher(new MoveChildMatcher(OpNo)); 412203954Srdivacky EmitMatchCode(N->getChild(i), NodeNoTypes->getChild(i)); 413204642Srdivacky AddMatcher(new MoveParentMatcher()); 414203954Srdivacky } 415203954Srdivacky} 416203954Srdivacky 417203954Srdivacky 418203954Srdivackyvoid MatcherGen::EmitMatchCode(const TreePatternNode *N, 419203954Srdivacky TreePatternNode *NodeNoTypes) { 420203954Srdivacky // If N and NodeNoTypes don't agree on a type, then this is a case where we 421203954Srdivacky // need to do a type check. Emit the check, apply the tyep to NodeNoTypes and 422203954Srdivacky // reinfer any correlated types. 423206083Srdivacky SmallVector<unsigned, 2> ResultsToTypeCheck; 424218893Sdim 425206083Srdivacky for (unsigned i = 0, e = NodeNoTypes->getNumTypes(); i != e; ++i) { 426206083Srdivacky if (NodeNoTypes->getExtType(i) == N->getExtType(i)) continue; 427206083Srdivacky NodeNoTypes->setType(i, N->getExtType(i)); 428203954Srdivacky InferPossibleTypes(); 429206083Srdivacky ResultsToTypeCheck.push_back(i); 430203954Srdivacky } 431218893Sdim 432203954Srdivacky // If this node has a name associated with it, capture it in VariableMap. If 433203954Srdivacky // we already saw this in the pattern, emit code to verify dagness. 434203954Srdivacky if (!N->getName().empty()) { 435203954Srdivacky unsigned &VarMapEntry = VariableMap[N->getName()]; 436203954Srdivacky if (VarMapEntry == 0) { 437204642Srdivacky // If it is a named node, we must emit a 'Record' opcode. 438204642Srdivacky AddMatcher(new RecordMatcher("$" + N->getName(), NextRecordedOperandNo)); 439203954Srdivacky VarMapEntry = ++NextRecordedOperandNo; 440203954Srdivacky } else { 441203954Srdivacky // If we get here, this is a second reference to a specific name. Since 442203954Srdivacky // we already have checked that the first reference is valid, we don't 443203954Srdivacky // have to recursively match it, just check that it's the same as the 444203954Srdivacky // previously named thing. 445204642Srdivacky AddMatcher(new CheckSameMatcher(VarMapEntry-1)); 446203954Srdivacky return; 447203954Srdivacky } 448203954Srdivacky } 449218893Sdim 450203954Srdivacky if (N->isLeaf()) 451203954Srdivacky EmitLeafMatchCode(N); 452203954Srdivacky else 453203954Srdivacky EmitOperatorMatchCode(N, NodeNoTypes); 454218893Sdim 455204961Srdivacky // If there are node predicates for this node, generate their checks. 456204961Srdivacky for (unsigned i = 0, e = N->getPredicateFns().size(); i != e; ++i) 457204961Srdivacky AddMatcher(new CheckPredicateMatcher(N->getPredicateFns()[i])); 458218893Sdim 459206083Srdivacky for (unsigned i = 0, e = ResultsToTypeCheck.size(); i != e; ++i) 460206083Srdivacky AddMatcher(new CheckTypeMatcher(N->getType(ResultsToTypeCheck[i]), 461206083Srdivacky ResultsToTypeCheck[i])); 462203954Srdivacky} 463203954Srdivacky 464204642Srdivacky/// EmitMatcherCode - Generate the code that matches the predicate of this 465204642Srdivacky/// pattern for the specified Variant. If the variant is invalid this returns 466204642Srdivacky/// true and does not generate code, if it is valid, it returns false. 467204642Srdivackybool MatcherGen::EmitMatcherCode(unsigned Variant) { 468204642Srdivacky // If the root of the pattern is a ComplexPattern and if it is specified to 469204642Srdivacky // match some number of root opcodes, these are considered to be our variants. 470204642Srdivacky // Depending on which variant we're generating code for, emit the root opcode 471204642Srdivacky // check. 472204642Srdivacky if (const ComplexPattern *CP = 473204642Srdivacky Pattern.getSrcPattern()->getComplexPatternInfo(CGP)) { 474204642Srdivacky const std::vector<Record*> &OpNodes = CP->getRootNodes(); 475204642Srdivacky assert(!OpNodes.empty() &&"Complex Pattern must specify what it can match"); 476204642Srdivacky if (Variant >= OpNodes.size()) return true; 477218893Sdim 478204642Srdivacky AddMatcher(new CheckOpcodeMatcher(CGP.getSDNodeInfo(OpNodes[Variant]))); 479204642Srdivacky } else { 480204642Srdivacky if (Variant != 0) return true; 481204642Srdivacky } 482218893Sdim 483204792Srdivacky // Emit the matcher for the pattern structure and types. 484204792Srdivacky EmitMatchCode(Pattern.getSrcPattern(), PatWithNoTypes); 485218893Sdim 486203954Srdivacky // If the pattern has a predicate on it (e.g. only enabled when a subtarget 487203954Srdivacky // feature is around, do the check). 488203954Srdivacky if (!Pattern.getPredicateCheck().empty()) 489204642Srdivacky AddMatcher(new CheckPatternPredicateMatcher(Pattern.getPredicateCheck())); 490218893Sdim 491204792Srdivacky // Now that we've completed the structural type match, emit any ComplexPattern 492204792Srdivacky // checks (e.g. addrmode matches). We emit this after the structural match 493204792Srdivacky // because they are generally more expensive to evaluate and more difficult to 494204792Srdivacky // factor. 495204792Srdivacky for (unsigned i = 0, e = MatchedComplexPatterns.size(); i != e; ++i) { 496204792Srdivacky const TreePatternNode *N = MatchedComplexPatterns[i].first; 497218893Sdim 498204792Srdivacky // Remember where the results of this match get stuck. 499204792Srdivacky MatchedComplexPatterns[i].second = NextRecordedOperandNo; 500204642Srdivacky 501204792Srdivacky // Get the slot we recorded the value in from the name on the node. 502204792Srdivacky unsigned RecNodeEntry = VariableMap[N->getName()]; 503204792Srdivacky assert(!N->getName().empty() && RecNodeEntry && 504204792Srdivacky "Complex pattern should have a name and slot"); 505204792Srdivacky --RecNodeEntry; // Entries in VariableMap are biased. 506218893Sdim 507204792Srdivacky const ComplexPattern &CP = 508204792Srdivacky CGP.getComplexPattern(((DefInit*)N->getLeafValue())->getDef()); 509218893Sdim 510204792Srdivacky // Emit a CheckComplexPat operation, which does the match (aborting if it 511204792Srdivacky // fails) and pushes the matched operands onto the recorded nodes list. 512204792Srdivacky AddMatcher(new CheckComplexPatMatcher(CP, RecNodeEntry, 513204792Srdivacky N->getName(), NextRecordedOperandNo)); 514218893Sdim 515204792Srdivacky // Record the right number of operands. 516204792Srdivacky NextRecordedOperandNo += CP.getNumOperands(); 517204792Srdivacky if (CP.hasProperty(SDNPHasChain)) { 518204792Srdivacky // If the complex pattern has a chain, then we need to keep track of the 519204792Srdivacky // fact that we just recorded a chain input. The chain input will be 520204792Srdivacky // matched as the last operand of the predicate if it was successful. 521204792Srdivacky ++NextRecordedOperandNo; // Chained node operand. 522218893Sdim 523204792Srdivacky // It is the last operand recorded. 524204792Srdivacky assert(NextRecordedOperandNo > 1 && 525204792Srdivacky "Should have recorded input/result chains at least!"); 526204792Srdivacky MatchedChainNodes.push_back(NextRecordedOperandNo-1); 527204792Srdivacky } 528218893Sdim 529218893Sdim // TODO: Complex patterns can't have output glues, if they did, we'd want 530204792Srdivacky // to record them. 531204792Srdivacky } 532218893Sdim 533204642Srdivacky return false; 534203954Srdivacky} 535203954Srdivacky 536203954Srdivacky 537204642Srdivacky//===----------------------------------------------------------------------===// 538204642Srdivacky// Node Result Generation 539204642Srdivacky//===----------------------------------------------------------------------===// 540204642Srdivacky 541204642Srdivackyvoid MatcherGen::EmitResultOfNamedOperand(const TreePatternNode *N, 542204642Srdivacky SmallVectorImpl<unsigned> &ResultOps){ 543204642Srdivacky assert(!N->getName().empty() && "Operand not named!"); 544218893Sdim 545204642Srdivacky // A reference to a complex pattern gets all of the results of the complex 546204642Srdivacky // pattern's match. 547204642Srdivacky if (const ComplexPattern *CP = N->getComplexPatternInfo(CGP)) { 548204792Srdivacky unsigned SlotNo = 0; 549204792Srdivacky for (unsigned i = 0, e = MatchedComplexPatterns.size(); i != e; ++i) 550204792Srdivacky if (MatchedComplexPatterns[i].first->getName() == N->getName()) { 551204792Srdivacky SlotNo = MatchedComplexPatterns[i].second; 552204792Srdivacky break; 553204792Srdivacky } 554204792Srdivacky assert(SlotNo != 0 && "Didn't get a slot number assigned?"); 555218893Sdim 556204642Srdivacky // The first slot entry is the node itself, the subsequent entries are the 557204642Srdivacky // matched values. 558204642Srdivacky for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i) 559204792Srdivacky ResultOps.push_back(SlotNo+i); 560204642Srdivacky return; 561204642Srdivacky } 562204642Srdivacky 563204792Srdivacky unsigned SlotNo = getNamedArgumentSlot(N->getName()); 564204792Srdivacky 565204642Srdivacky // If this is an 'imm' or 'fpimm' node, make sure to convert it to the target 566204642Srdivacky // version of the immediate so that it doesn't get selected due to some other 567204642Srdivacky // node use. 568204642Srdivacky if (!N->isLeaf()) { 569204642Srdivacky StringRef OperatorName = N->getOperator()->getName(); 570204642Srdivacky if (OperatorName == "imm" || OperatorName == "fpimm") { 571204642Srdivacky AddMatcher(new EmitConvertToTargetMatcher(SlotNo)); 572204642Srdivacky ResultOps.push_back(NextRecordedOperandNo++); 573204642Srdivacky return; 574204642Srdivacky } 575204642Srdivacky } 576218893Sdim 577204642Srdivacky ResultOps.push_back(SlotNo); 578204642Srdivacky} 579204642Srdivacky 580204642Srdivackyvoid MatcherGen::EmitResultLeafAsOperand(const TreePatternNode *N, 581204642Srdivacky SmallVectorImpl<unsigned> &ResultOps) { 582204642Srdivacky assert(N->isLeaf() && "Must be a leaf"); 583218893Sdim 584204642Srdivacky if (IntInit *II = dynamic_cast<IntInit*>(N->getLeafValue())) { 585205407Srdivacky AddMatcher(new EmitIntegerMatcher(II->getValue(), N->getType(0))); 586204642Srdivacky ResultOps.push_back(NextRecordedOperandNo++); 587204642Srdivacky return; 588204642Srdivacky } 589218893Sdim 590204642Srdivacky // If this is an explicit register reference, handle it. 591204642Srdivacky if (DefInit *DI = dynamic_cast<DefInit*>(N->getLeafValue())) { 592204642Srdivacky if (DI->getDef()->isSubClassOf("Register")) { 593221345Sdim AddMatcher(new EmitRegisterMatcher(RegisterDefMap[DI->getDef()], 594221345Sdim N->getType(0))); 595204642Srdivacky ResultOps.push_back(NextRecordedOperandNo++); 596204642Srdivacky return; 597204642Srdivacky } 598218893Sdim 599204642Srdivacky if (DI->getDef()->getName() == "zero_reg") { 600205407Srdivacky AddMatcher(new EmitRegisterMatcher(0, N->getType(0))); 601204642Srdivacky ResultOps.push_back(NextRecordedOperandNo++); 602204642Srdivacky return; 603204642Srdivacky } 604218893Sdim 605204642Srdivacky // Handle a reference to a register class. This is used 606204642Srdivacky // in COPY_TO_SUBREG instructions. 607204642Srdivacky if (DI->getDef()->isSubClassOf("RegisterClass")) { 608204642Srdivacky std::string Value = getQualifiedName(DI->getDef()) + "RegClassID"; 609204642Srdivacky AddMatcher(new EmitStringIntegerMatcher(Value, MVT::i32)); 610204642Srdivacky ResultOps.push_back(NextRecordedOperandNo++); 611204642Srdivacky return; 612204642Srdivacky } 613208599Srdivacky 614208599Srdivacky // Handle a subregister index. This is used for INSERT_SUBREG etc. 615208599Srdivacky if (DI->getDef()->isSubClassOf("SubRegIndex")) { 616208599Srdivacky std::string Value = getQualifiedName(DI->getDef()); 617208599Srdivacky AddMatcher(new EmitStringIntegerMatcher(Value, MVT::i32)); 618208599Srdivacky ResultOps.push_back(NextRecordedOperandNo++); 619208599Srdivacky return; 620208599Srdivacky } 621204642Srdivacky } 622218893Sdim 623204642Srdivacky errs() << "unhandled leaf node: \n"; 624204642Srdivacky N->dump(); 625204642Srdivacky} 626204642Srdivacky 627204642Srdivacky/// GetInstPatternNode - Get the pattern for an instruction. 628218893Sdim/// 629204642Srdivackyconst TreePatternNode *MatcherGen:: 630204642SrdivackyGetInstPatternNode(const DAGInstruction &Inst, const TreePatternNode *N) { 631204642Srdivacky const TreePattern *InstPat = Inst.getPattern(); 632218893Sdim 633204642Srdivacky // FIXME2?: Assume actual pattern comes before "implicit". 634204642Srdivacky TreePatternNode *InstPatNode; 635204642Srdivacky if (InstPat) 636204642Srdivacky InstPatNode = InstPat->getTree(0); 637204642Srdivacky else if (/*isRoot*/ N == Pattern.getDstPattern()) 638204642Srdivacky InstPatNode = Pattern.getSrcPattern(); 639204642Srdivacky else 640204642Srdivacky return 0; 641218893Sdim 642204642Srdivacky if (InstPatNode && !InstPatNode->isLeaf() && 643204642Srdivacky InstPatNode->getOperator()->getName() == "set") 644204642Srdivacky InstPatNode = InstPatNode->getChild(InstPatNode->getNumChildren()-1); 645218893Sdim 646204642Srdivacky return InstPatNode; 647204642Srdivacky} 648204642Srdivacky 649223017Sdimstatic bool 650223017SdimmayInstNodeLoadOrStore(const TreePatternNode *N, 651223017Sdim const CodeGenDAGPatterns &CGP) { 652223017Sdim Record *Op = N->getOperator(); 653223017Sdim const CodeGenTarget &CGT = CGP.getTargetInfo(); 654223017Sdim CodeGenInstruction &II = CGT.getInstruction(Op); 655223017Sdim return II.mayLoad || II.mayStore; 656223017Sdim} 657223017Sdim 658223017Sdimstatic unsigned 659223017SdimnumNodesThatMayLoadOrStore(const TreePatternNode *N, 660223017Sdim const CodeGenDAGPatterns &CGP) { 661223017Sdim if (N->isLeaf()) 662223017Sdim return 0; 663223017Sdim 664223017Sdim Record *OpRec = N->getOperator(); 665223017Sdim if (!OpRec->isSubClassOf("Instruction")) 666223017Sdim return 0; 667223017Sdim 668223017Sdim unsigned Count = 0; 669223017Sdim if (mayInstNodeLoadOrStore(N, CGP)) 670223017Sdim ++Count; 671223017Sdim 672223017Sdim for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 673223017Sdim Count += numNodesThatMayLoadOrStore(N->getChild(i), CGP); 674223017Sdim 675223017Sdim return Count; 676223017Sdim} 677223017Sdim 678204642Srdivackyvoid MatcherGen:: 679204642SrdivackyEmitResultInstructionAsOperand(const TreePatternNode *N, 680204642Srdivacky SmallVectorImpl<unsigned> &OutputOps) { 681204642Srdivacky Record *Op = N->getOperator(); 682204642Srdivacky const CodeGenTarget &CGT = CGP.getTargetInfo(); 683205407Srdivacky CodeGenInstruction &II = CGT.getInstruction(Op); 684204642Srdivacky const DAGInstruction &Inst = CGP.getInstruction(Op); 685218893Sdim 686204642Srdivacky // If we can, get the pattern for the instruction we're generating. We derive 687204642Srdivacky // a variety of information from this pattern, such as whether it has a chain. 688204642Srdivacky // 689204642Srdivacky // FIXME2: This is extremely dubious for several reasons, not the least of 690204642Srdivacky // which it gives special status to instructions with patterns that Pat<> 691204642Srdivacky // nodes can't duplicate. 692204642Srdivacky const TreePatternNode *InstPatNode = GetInstPatternNode(Inst, N); 693204642Srdivacky 694218893Sdim // NodeHasChain - Whether the instruction node we're creating takes chains. 695204642Srdivacky bool NodeHasChain = InstPatNode && 696204642Srdivacky InstPatNode->TreeHasProperty(SDNPHasChain, CGP); 697218893Sdim 698204642Srdivacky bool isRoot = N == Pattern.getDstPattern(); 699204642Srdivacky 700218893Sdim // TreeHasOutGlue - True if this tree has glue. 701218893Sdim bool TreeHasInGlue = false, TreeHasOutGlue = false; 702204642Srdivacky if (isRoot) { 703204642Srdivacky const TreePatternNode *SrcPat = Pattern.getSrcPattern(); 704218893Sdim TreeHasInGlue = SrcPat->TreeHasProperty(SDNPOptInGlue, CGP) || 705218893Sdim SrcPat->TreeHasProperty(SDNPInGlue, CGP); 706218893Sdim 707204642Srdivacky // FIXME2: this is checking the entire pattern, not just the node in 708204642Srdivacky // question, doing this just for the root seems like a total hack. 709218893Sdim TreeHasOutGlue = SrcPat->TreeHasProperty(SDNPOutGlue, CGP); 710204642Srdivacky } 711204642Srdivacky 712204642Srdivacky // NumResults - This is the number of results produced by the instruction in 713204642Srdivacky // the "outs" list. 714218893Sdim unsigned NumResults = Inst.getNumResults(); 715204642Srdivacky 716204642Srdivacky // Loop over all of the operands of the instruction pattern, emitting code 717204642Srdivacky // to fill them all in. The node 'N' usually has number children equal to 718204642Srdivacky // the number of input operands of the instruction. However, in cases 719204642Srdivacky // where there are predicate operands for an instruction, we need to fill 720204642Srdivacky // in the 'execute always' values. Match up the node operands to the 721204642Srdivacky // instruction operands to do this. 722204642Srdivacky SmallVector<unsigned, 8> InstOps; 723218893Sdim for (unsigned ChildNo = 0, InstOpNo = NumResults, e = II.Operands.size(); 724204642Srdivacky InstOpNo != e; ++InstOpNo) { 725218893Sdim 726204642Srdivacky // Determine what to emit for this operand. 727218893Sdim Record *OperandNode = II.Operands[InstOpNo].Rec; 728204642Srdivacky if ((OperandNode->isSubClassOf("PredicateOperand") || 729204642Srdivacky OperandNode->isSubClassOf("OptionalDefOperand")) && 730204642Srdivacky !CGP.getDefaultOperand(OperandNode).DefaultOps.empty()) { 731204642Srdivacky // This is a predicate or optional def operand; emit the 732204642Srdivacky // 'default ops' operands. 733212904Sdim const DAGDefaultOperand &DefaultOp 734218893Sdim = CGP.getDefaultOperand(OperandNode); 735204642Srdivacky for (unsigned i = 0, e = DefaultOp.DefaultOps.size(); i != e; ++i) 736204642Srdivacky EmitResultOperand(DefaultOp.DefaultOps[i], InstOps); 737204642Srdivacky continue; 738204642Srdivacky } 739218893Sdim 740206083Srdivacky const TreePatternNode *Child = N->getChild(ChildNo); 741218893Sdim 742204642Srdivacky // Otherwise this is a normal operand or a predicate operand without 743204642Srdivacky // 'execute always'; emit it. 744206083Srdivacky unsigned BeforeAddingNumOps = InstOps.size(); 745206083Srdivacky EmitResultOperand(Child, InstOps); 746206083Srdivacky assert(InstOps.size() > BeforeAddingNumOps && "Didn't add any operands"); 747218893Sdim 748206083Srdivacky // If the operand is an instruction and it produced multiple results, just 749206083Srdivacky // take the first one. 750206083Srdivacky if (!Child->isLeaf() && Child->getOperator()->isSubClassOf("Instruction")) 751206083Srdivacky InstOps.resize(BeforeAddingNumOps+1); 752218893Sdim 753204642Srdivacky ++ChildNo; 754204642Srdivacky } 755218893Sdim 756218893Sdim // If this node has input glue or explicitly specified input physregs, we 757218893Sdim // need to add chained and glued copyfromreg nodes and materialize the glue 758204642Srdivacky // input. 759204642Srdivacky if (isRoot && !PhysRegInputs.empty()) { 760204642Srdivacky // Emit all of the CopyToReg nodes for the input physical registers. These 761204642Srdivacky // occur in patterns like (mul:i8 AL:i8, GR8:i8:$src). 762204642Srdivacky for (unsigned i = 0, e = PhysRegInputs.size(); i != e; ++i) 763204642Srdivacky AddMatcher(new EmitCopyToRegMatcher(PhysRegInputs[i].second, 764205407Srdivacky PhysRegInputs[i].first)); 765218893Sdim // Even if the node has no other glue inputs, the resultant node must be 766218893Sdim // glued to the CopyFromReg nodes we just generated. 767218893Sdim TreeHasInGlue = true; 768204642Srdivacky } 769218893Sdim 770218893Sdim // Result order: node results, chain, glue 771218893Sdim 772204642Srdivacky // Determine the result types. 773204642Srdivacky SmallVector<MVT::SimpleValueType, 4> ResultVTs; 774206083Srdivacky for (unsigned i = 0, e = N->getNumTypes(); i != e; ++i) 775206083Srdivacky ResultVTs.push_back(N->getType(i)); 776218893Sdim 777204642Srdivacky // If this is the root instruction of a pattern that has physical registers in 778204642Srdivacky // its result pattern, add output VTs for them. For example, X86 has: 779204642Srdivacky // (set AL, (mul ...)) 780204642Srdivacky // This also handles implicit results like: 781204642Srdivacky // (implicit EFLAGS) 782206083Srdivacky if (isRoot && !Pattern.getDstRegs().empty()) { 783205407Srdivacky // If the root came from an implicit def in the instruction handling stuff, 784205407Srdivacky // don't re-add it. 785205407Srdivacky Record *HandledReg = 0; 786206083Srdivacky if (II.HasOneImplicitDefWithKnownVT(CGT) != MVT::Other) 787205407Srdivacky HandledReg = II.ImplicitDefs[0]; 788218893Sdim 789205407Srdivacky for (unsigned i = 0; i != Pattern.getDstRegs().size(); ++i) { 790205407Srdivacky Record *Reg = Pattern.getDstRegs()[i]; 791205407Srdivacky if (!Reg->isSubClassOf("Register") || Reg == HandledReg) continue; 792205407Srdivacky ResultVTs.push_back(getRegisterValueType(Reg, CGT)); 793205407Srdivacky } 794204642Srdivacky } 795204642Srdivacky 796205407Srdivacky // If this is the root of the pattern and the pattern we're matching includes 797205407Srdivacky // a node that is variadic, mark the generated node as variadic so that it 798205407Srdivacky // gets the excess operands from the input DAG. 799204642Srdivacky int NumFixedArityOperands = -1; 800205407Srdivacky if (isRoot && 801205407Srdivacky (Pattern.getSrcPattern()->NodeHasProperty(SDNPVariadic, CGP))) 802204642Srdivacky NumFixedArityOperands = Pattern.getSrcPattern()->getNumChildren(); 803218893Sdim 804223017Sdim // If this is the root node and multiple matched nodes in the input pattern 805223017Sdim // have MemRefs in them, have the interpreter collect them and plop them onto 806223017Sdim // this node. If there is just one node with MemRefs, leave them on that node 807223017Sdim // even if it is not the root. 808204642Srdivacky // 809223017Sdim // FIXME3: This is actively incorrect for result patterns with multiple 810223017Sdim // memory-referencing instructions. 811223017Sdim bool PatternHasMemOperands = 812223017Sdim Pattern.getSrcPattern()->TreeHasProperty(SDNPMemOperand, CGP); 813204642Srdivacky 814223017Sdim bool NodeHasMemRefs = false; 815223017Sdim if (PatternHasMemOperands) { 816223017Sdim unsigned NumNodesThatLoadOrStore = 817223017Sdim numNodesThatMayLoadOrStore(Pattern.getDstPattern(), CGP); 818223017Sdim bool NodeIsUniqueLoadOrStore = mayInstNodeLoadOrStore(N, CGP) && 819223017Sdim NumNodesThatLoadOrStore == 1; 820223017Sdim NodeHasMemRefs = 821223017Sdim NodeIsUniqueLoadOrStore || (isRoot && (mayInstNodeLoadOrStore(N, CGP) || 822223017Sdim NumNodesThatLoadOrStore != 1)); 823223017Sdim } 824223017Sdim 825218893Sdim assert((!ResultVTs.empty() || TreeHasOutGlue || NodeHasChain) && 826206083Srdivacky "Node has no result"); 827218893Sdim 828204642Srdivacky AddMatcher(new EmitNodeMatcher(II.Namespace+"::"+II.TheDef->getName(), 829204642Srdivacky ResultVTs.data(), ResultVTs.size(), 830204642Srdivacky InstOps.data(), InstOps.size(), 831218893Sdim NodeHasChain, TreeHasInGlue, TreeHasOutGlue, 832204642Srdivacky NodeHasMemRefs, NumFixedArityOperands, 833204642Srdivacky NextRecordedOperandNo)); 834218893Sdim 835218893Sdim // The non-chain and non-glue results of the newly emitted node get recorded. 836204642Srdivacky for (unsigned i = 0, e = ResultVTs.size(); i != e; ++i) { 837218893Sdim if (ResultVTs[i] == MVT::Other || ResultVTs[i] == MVT::Glue) break; 838204642Srdivacky OutputOps.push_back(NextRecordedOperandNo++); 839204642Srdivacky } 840204642Srdivacky} 841204642Srdivacky 842204642Srdivackyvoid MatcherGen:: 843204642SrdivackyEmitResultSDNodeXFormAsOperand(const TreePatternNode *N, 844204642Srdivacky SmallVectorImpl<unsigned> &ResultOps) { 845204642Srdivacky assert(N->getOperator()->isSubClassOf("SDNodeXForm") && "Not SDNodeXForm?"); 846204642Srdivacky 847204642Srdivacky // Emit the operand. 848204642Srdivacky SmallVector<unsigned, 8> InputOps; 849218893Sdim 850204642Srdivacky // FIXME2: Could easily generalize this to support multiple inputs and outputs 851204642Srdivacky // to the SDNodeXForm. For now we just support one input and one output like 852204642Srdivacky // the old instruction selector. 853204642Srdivacky assert(N->getNumChildren() == 1); 854204642Srdivacky EmitResultOperand(N->getChild(0), InputOps); 855204642Srdivacky 856204642Srdivacky // The input currently must have produced exactly one result. 857204642Srdivacky assert(InputOps.size() == 1 && "Unexpected input to SDNodeXForm"); 858204642Srdivacky 859204642Srdivacky AddMatcher(new EmitNodeXFormMatcher(InputOps[0], N->getOperator())); 860204642Srdivacky ResultOps.push_back(NextRecordedOperandNo++); 861204642Srdivacky} 862204642Srdivacky 863204642Srdivackyvoid MatcherGen::EmitResultOperand(const TreePatternNode *N, 864204642Srdivacky SmallVectorImpl<unsigned> &ResultOps) { 865204642Srdivacky // This is something selected from the pattern we matched. 866204642Srdivacky if (!N->getName().empty()) 867204642Srdivacky return EmitResultOfNamedOperand(N, ResultOps); 868204642Srdivacky 869204642Srdivacky if (N->isLeaf()) 870204642Srdivacky return EmitResultLeafAsOperand(N, ResultOps); 871204642Srdivacky 872204642Srdivacky Record *OpRec = N->getOperator(); 873204642Srdivacky if (OpRec->isSubClassOf("Instruction")) 874204642Srdivacky return EmitResultInstructionAsOperand(N, ResultOps); 875204642Srdivacky if (OpRec->isSubClassOf("SDNodeXForm")) 876204642Srdivacky return EmitResultSDNodeXFormAsOperand(N, ResultOps); 877204642Srdivacky errs() << "Unknown result node to emit code for: " << *N << '\n'; 878204642Srdivacky throw std::string("Unknown node in result pattern!"); 879204642Srdivacky} 880204642Srdivacky 881204642Srdivackyvoid MatcherGen::EmitResultCode() { 882204642Srdivacky // Patterns that match nodes with (potentially multiple) chain inputs have to 883204642Srdivacky // merge them together into a token factor. This informs the generated code 884204642Srdivacky // what all the chained nodes are. 885204642Srdivacky if (!MatchedChainNodes.empty()) 886204642Srdivacky AddMatcher(new EmitMergeInputChainsMatcher 887204642Srdivacky (MatchedChainNodes.data(), MatchedChainNodes.size())); 888218893Sdim 889204642Srdivacky // Codegen the root of the result pattern, capturing the resulting values. 890204642Srdivacky SmallVector<unsigned, 8> Ops; 891204642Srdivacky EmitResultOperand(Pattern.getDstPattern(), Ops); 892204642Srdivacky 893204642Srdivacky // At this point, we have however many values the result pattern produces. 894204642Srdivacky // However, the input pattern might not need all of these. If there are 895206083Srdivacky // excess values at the end (such as implicit defs of condition codes etc) 896218893Sdim // just lop them off. This doesn't need to worry about glue or chains, just 897206083Srdivacky // explicit results. 898204642Srdivacky // 899206083Srdivacky unsigned NumSrcResults = Pattern.getSrcPattern()->getNumTypes(); 900218893Sdim 901206083Srdivacky // If the pattern also has (implicit) results, count them as well. 902206083Srdivacky if (!Pattern.getDstRegs().empty()) { 903206083Srdivacky // If the root came from an implicit def in the instruction handling stuff, 904206083Srdivacky // don't re-add it. 905206083Srdivacky Record *HandledReg = 0; 906206083Srdivacky const TreePatternNode *DstPat = Pattern.getDstPattern(); 907206083Srdivacky if (!DstPat->isLeaf() &&DstPat->getOperator()->isSubClassOf("Instruction")){ 908206083Srdivacky const CodeGenTarget &CGT = CGP.getTargetInfo(); 909206083Srdivacky CodeGenInstruction &II = CGT.getInstruction(DstPat->getOperator()); 910206083Srdivacky 911206083Srdivacky if (II.HasOneImplicitDefWithKnownVT(CGT) != MVT::Other) 912206083Srdivacky HandledReg = II.ImplicitDefs[0]; 913206083Srdivacky } 914218893Sdim 915206083Srdivacky for (unsigned i = 0; i != Pattern.getDstRegs().size(); ++i) { 916206083Srdivacky Record *Reg = Pattern.getDstRegs()[i]; 917206083Srdivacky if (!Reg->isSubClassOf("Register") || Reg == HandledReg) continue; 918206083Srdivacky ++NumSrcResults; 919206083Srdivacky } 920218893Sdim } 921218893Sdim 922204642Srdivacky assert(Ops.size() >= NumSrcResults && "Didn't provide enough results"); 923204642Srdivacky Ops.resize(NumSrcResults); 924204642Srdivacky 925218893Sdim // If the matched pattern covers nodes which define a glue result, emit a node 926204642Srdivacky // that tells the matcher about them so that it can update their results. 927218893Sdim if (!MatchedGlueResultNodes.empty()) 928218893Sdim AddMatcher(new MarkGlueResultsMatcher(MatchedGlueResultNodes.data(), 929218893Sdim MatchedGlueResultNodes.size())); 930218893Sdim 931204642Srdivacky AddMatcher(new CompleteMatchMatcher(Ops.data(), Ops.size(), Pattern)); 932204642Srdivacky} 933204642Srdivacky 934204642Srdivacky 935204642Srdivacky/// ConvertPatternToMatcher - Create the matcher for the specified pattern with 936204642Srdivacky/// the specified variant. If the variant number is invalid, this returns null. 937204642SrdivackyMatcher *llvm::ConvertPatternToMatcher(const PatternToMatch &Pattern, 938204642Srdivacky unsigned Variant, 939204642Srdivacky const CodeGenDAGPatterns &CGP) { 940203954Srdivacky MatcherGen Gen(Pattern, CGP); 941203954Srdivacky 942203954Srdivacky // Generate the code for the matcher. 943204642Srdivacky if (Gen.EmitMatcherCode(Variant)) 944204642Srdivacky return 0; 945218893Sdim 946204642Srdivacky // FIXME2: Kill extra MoveParent commands at the end of the matcher sequence. 947204642Srdivacky // FIXME2: Split result code out to another table, and make the matcher end 948204642Srdivacky // with an "Emit <index>" command. This allows result generation stuff to be 949204642Srdivacky // shared and factored? 950218893Sdim 951203954Srdivacky // If the match succeeds, then we generate Pattern. 952204642Srdivacky Gen.EmitResultCode(); 953203954Srdivacky 954203954Srdivacky // Unconditional match. 955204642Srdivacky return Gen.GetMatcher(); 956203954Srdivacky} 957