DAGISelMatcherGen.cpp revision 239462
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" 13226633Sdim#include "llvm/TableGen/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; 28224145Sdim const CodeGenRegister *Reg = T.getRegBank().getReg(R); 29226633Sdim ArrayRef<CodeGenRegisterClass*> RCs = T.getRegBank().getRegClasses(); 30218893Sdim 31204642Srdivacky for (unsigned rc = 0, e = RCs.size(); rc != e; ++rc) { 32226633Sdim const CodeGenRegisterClass &RC = *RCs[rc]; 33224145Sdim if (!RC.contains(Reg)) 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; 96203954Srdivacky public: 97203954Srdivacky MatcherGen(const PatternToMatch &pattern, const CodeGenDAGPatterns &cgp); 98218893Sdim 99203954Srdivacky ~MatcherGen() { 100203954Srdivacky delete PatWithNoTypes; 101203954Srdivacky } 102218893Sdim 103204642Srdivacky bool EmitMatcherCode(unsigned Variant); 104204642Srdivacky void EmitResultCode(); 105218893Sdim 106204642Srdivacky Matcher *GetMatcher() const { return TheMatcher; } 107203954Srdivacky private: 108204642Srdivacky void AddMatcher(Matcher *NewNode); 109203954Srdivacky void InferPossibleTypes(); 110218893Sdim 111204642Srdivacky // Matcher Generation. 112203954Srdivacky void EmitMatchCode(const TreePatternNode *N, TreePatternNode *NodeNoTypes); 113203954Srdivacky void EmitLeafMatchCode(const TreePatternNode *N); 114203954Srdivacky void EmitOperatorMatchCode(const TreePatternNode *N, 115203954Srdivacky TreePatternNode *NodeNoTypes); 116218893Sdim 117204642Srdivacky // Result Code Generation. 118204642Srdivacky unsigned getNamedArgumentSlot(StringRef Name) { 119204642Srdivacky unsigned VarMapEntry = VariableMap[Name]; 120204642Srdivacky assert(VarMapEntry != 0 && 121204642Srdivacky "Variable referenced but not defined and not caught earlier!"); 122204642Srdivacky return VarMapEntry-1; 123204642Srdivacky } 124204642Srdivacky 125204642Srdivacky /// GetInstPatternNode - Get the pattern for an instruction. 126204642Srdivacky const TreePatternNode *GetInstPatternNode(const DAGInstruction &Ins, 127204642Srdivacky const TreePatternNode *N); 128218893Sdim 129204642Srdivacky void EmitResultOperand(const TreePatternNode *N, 130204642Srdivacky SmallVectorImpl<unsigned> &ResultOps); 131204642Srdivacky void EmitResultOfNamedOperand(const TreePatternNode *N, 132204642Srdivacky SmallVectorImpl<unsigned> &ResultOps); 133204642Srdivacky void EmitResultLeafAsOperand(const TreePatternNode *N, 134204642Srdivacky SmallVectorImpl<unsigned> &ResultOps); 135204642Srdivacky void EmitResultInstructionAsOperand(const TreePatternNode *N, 136204642Srdivacky SmallVectorImpl<unsigned> &ResultOps); 137204642Srdivacky void EmitResultSDNodeXFormAsOperand(const TreePatternNode *N, 138204642Srdivacky SmallVectorImpl<unsigned> &ResultOps); 139204642Srdivacky }; 140218893Sdim 141203954Srdivacky} // end anon namespace. 142203954Srdivacky 143203954SrdivackyMatcherGen::MatcherGen(const PatternToMatch &pattern, 144203954Srdivacky const CodeGenDAGPatterns &cgp) 145203954Srdivacky: Pattern(pattern), CGP(cgp), NextRecordedOperandNo(0), 146204642Srdivacky TheMatcher(0), CurPredicate(0) { 147203954Srdivacky // We need to produce the matcher tree for the patterns source pattern. To do 148203954Srdivacky // this we need to match the structure as well as the types. To do the type 149203954Srdivacky // matching, we want to figure out the fewest number of type checks we need to 150203954Srdivacky // emit. For example, if there is only one integer type supported by a 151203954Srdivacky // target, there should be no type comparisons at all for integer patterns! 152203954Srdivacky // 153203954Srdivacky // To figure out the fewest number of type checks needed, clone the pattern, 154203954Srdivacky // remove the types, then perform type inference on the pattern as a whole. 155203954Srdivacky // If there are unresolved types, emit an explicit check for those types, 156203954Srdivacky // apply the type to the tree, then rerun type inference. Iterate until all 157203954Srdivacky // types are resolved. 158203954Srdivacky // 159203954Srdivacky PatWithNoTypes = Pattern.getSrcPattern()->clone(); 160203954Srdivacky PatWithNoTypes->RemoveAllTypes(); 161218893Sdim 162203954Srdivacky // If there are types that are manifestly known, infer them. 163203954Srdivacky InferPossibleTypes(); 164203954Srdivacky} 165203954Srdivacky 166203954Srdivacky/// InferPossibleTypes - As we emit the pattern, we end up generating type 167203954Srdivacky/// checks and applying them to the 'PatWithNoTypes' tree. As we do this, we 168203954Srdivacky/// want to propagate implied types as far throughout the tree as possible so 169203954Srdivacky/// that we avoid doing redundant type checks. This does the type propagation. 170203954Srdivackyvoid MatcherGen::InferPossibleTypes() { 171203954Srdivacky // TP - Get *SOME* tree pattern, we don't care which. It is only used for 172203954Srdivacky // diagnostics, which we know are impossible at this point. 173203954Srdivacky TreePattern &TP = *CGP.pf_begin()->second; 174218893Sdim 175203954Srdivacky try { 176203954Srdivacky bool MadeChange = true; 177203954Srdivacky while (MadeChange) 178203954Srdivacky MadeChange = PatWithNoTypes->ApplyTypeConstraints(TP, 179203954Srdivacky true/*Ignore reg constraints*/); 180203954Srdivacky } catch (...) { 181203954Srdivacky errs() << "Type constraint application shouldn't fail!"; 182203954Srdivacky abort(); 183203954Srdivacky } 184203954Srdivacky} 185203954Srdivacky 186203954Srdivacky 187218893Sdim/// AddMatcher - Add a matcher node to the current graph we're building. 188204642Srdivackyvoid MatcherGen::AddMatcher(Matcher *NewNode) { 189203954Srdivacky if (CurPredicate != 0) 190204642Srdivacky CurPredicate->setNext(NewNode); 191203954Srdivacky else 192204642Srdivacky TheMatcher = NewNode; 193203954Srdivacky CurPredicate = NewNode; 194203954Srdivacky} 195203954Srdivacky 196203954Srdivacky 197204642Srdivacky//===----------------------------------------------------------------------===// 198204642Srdivacky// Pattern Match Generation 199204642Srdivacky//===----------------------------------------------------------------------===// 200203954Srdivacky 201203954Srdivacky/// EmitLeafMatchCode - Generate matching code for leaf nodes. 202203954Srdivackyvoid MatcherGen::EmitLeafMatchCode(const TreePatternNode *N) { 203203954Srdivacky assert(N->isLeaf() && "Not a leaf?"); 204218893Sdim 205203954Srdivacky // Direct match against an integer constant. 206204642Srdivacky if (IntInit *II = dynamic_cast<IntInit*>(N->getLeafValue())) { 207204642Srdivacky // If this is the root of the dag we're matching, we emit a redundant opcode 208204642Srdivacky // check to ensure that this gets folded into the normal top-level 209204642Srdivacky // OpcodeSwitch. 210204642Srdivacky if (N == Pattern.getSrcPattern()) { 211204642Srdivacky const SDNodeInfo &NI = CGP.getSDNodeInfo(CGP.getSDNodeNamed("imm")); 212204642Srdivacky AddMatcher(new CheckOpcodeMatcher(NI)); 213204642Srdivacky } 214204642Srdivacky 215204642Srdivacky return AddMatcher(new CheckIntegerMatcher(II->getValue())); 216204642Srdivacky } 217218893Sdim 218203954Srdivacky DefInit *DI = dynamic_cast<DefInit*>(N->getLeafValue()); 219203954Srdivacky if (DI == 0) { 220234353Sdim errs() << "Unknown leaf kind: " << *N << "\n"; 221203954Srdivacky abort(); 222203954Srdivacky } 223218893Sdim 224203954Srdivacky Record *LeafRec = DI->getDef(); 225203954Srdivacky if (// Handle register references. Nothing to do here, they always match. 226218893Sdim LeafRec->isSubClassOf("RegisterClass") || 227224145Sdim LeafRec->isSubClassOf("RegisterOperand") || 228203954Srdivacky LeafRec->isSubClassOf("PointerLikeRegClass") || 229208599Srdivacky LeafRec->isSubClassOf("SubRegIndex") || 230203954Srdivacky // Place holder for SRCVALUE nodes. Nothing to do here. 231203954Srdivacky LeafRec->getName() == "srcvalue") 232203954Srdivacky return; 233204642Srdivacky 234204642Srdivacky // If we have a physreg reference like (mul gpr:$src, EAX) then we need to 235218893Sdim // record the register 236204642Srdivacky if (LeafRec->isSubClassOf("Register")) { 237204642Srdivacky AddMatcher(new RecordMatcher("physreg input "+LeafRec->getName(), 238204642Srdivacky NextRecordedOperandNo)); 239204642Srdivacky PhysRegInputs.push_back(std::make_pair(LeafRec, NextRecordedOperandNo++)); 240204642Srdivacky return; 241204642Srdivacky } 242218893Sdim 243203954Srdivacky if (LeafRec->isSubClassOf("ValueType")) 244204642Srdivacky return AddMatcher(new CheckValueTypeMatcher(LeafRec->getName())); 245218893Sdim 246203954Srdivacky if (LeafRec->isSubClassOf("CondCode")) 247204642Srdivacky return AddMatcher(new CheckCondCodeMatcher(LeafRec->getName())); 248218893Sdim 249203954Srdivacky if (LeafRec->isSubClassOf("ComplexPattern")) { 250204642Srdivacky // We can't model ComplexPattern uses that don't have their name taken yet. 251204642Srdivacky // The OPC_CheckComplexPattern operation implicitly records the results. 252204642Srdivacky if (N->getName().empty()) { 253204642Srdivacky errs() << "We expect complex pattern uses to have names: " << *N << "\n"; 254204642Srdivacky exit(1); 255204642Srdivacky } 256204642Srdivacky 257204792Srdivacky // Remember this ComplexPattern so that we can emit it after all the other 258204792Srdivacky // structural matches are done. 259204792Srdivacky MatchedComplexPatterns.push_back(std::make_pair(N, 0)); 260204642Srdivacky return; 261203954Srdivacky } 262218893Sdim 263203954Srdivacky errs() << "Unknown leaf kind: " << *N << "\n"; 264203954Srdivacky abort(); 265203954Srdivacky} 266203954Srdivacky 267203954Srdivackyvoid MatcherGen::EmitOperatorMatchCode(const TreePatternNode *N, 268203954Srdivacky TreePatternNode *NodeNoTypes) { 269203954Srdivacky assert(!N->isLeaf() && "Not an operator?"); 270203954Srdivacky const SDNodeInfo &CInfo = CGP.getSDNodeInfo(N->getOperator()); 271218893Sdim 272203954Srdivacky // If this is an 'and R, 1234' where the operation is AND/OR and the RHS is 273203954Srdivacky // a constant without a predicate fn that has more that one bit set, handle 274203954Srdivacky // this as a special case. This is usually for targets that have special 275203954Srdivacky // handling of certain large constants (e.g. alpha with it's 8/16/32-bit 276203954Srdivacky // handling stuff). Using these instructions is often far more efficient 277203954Srdivacky // than materializing the constant. Unfortunately, both the instcombiner 278203954Srdivacky // and the dag combiner can often infer that bits are dead, and thus drop 279203954Srdivacky // them from the mask in the dag. For example, it might turn 'AND X, 255' 280203954Srdivacky // into 'AND X, 254' if it knows the low bit is set. Emit code that checks 281203954Srdivacky // to handle this. 282218893Sdim if ((N->getOperator()->getName() == "and" || 283203954Srdivacky N->getOperator()->getName() == "or") && 284204642Srdivacky N->getChild(1)->isLeaf() && N->getChild(1)->getPredicateFns().empty() && 285204642Srdivacky N->getPredicateFns().empty()) { 286203954Srdivacky if (IntInit *II = dynamic_cast<IntInit*>(N->getChild(1)->getLeafValue())) { 287203954Srdivacky if (!isPowerOf2_32(II->getValue())) { // Don't bother with single bits. 288204642Srdivacky // If this is at the root of the pattern, we emit a redundant 289204642Srdivacky // CheckOpcode so that the following checks get factored properly under 290204642Srdivacky // a single opcode check. 291204642Srdivacky if (N == Pattern.getSrcPattern()) 292204642Srdivacky AddMatcher(new CheckOpcodeMatcher(CInfo)); 293204642Srdivacky 294204642Srdivacky // Emit the CheckAndImm/CheckOrImm node. 295203954Srdivacky if (N->getOperator()->getName() == "and") 296204642Srdivacky AddMatcher(new CheckAndImmMatcher(II->getValue())); 297203954Srdivacky else 298204642Srdivacky AddMatcher(new CheckOrImmMatcher(II->getValue())); 299203954Srdivacky 300203954Srdivacky // Match the LHS of the AND as appropriate. 301204642Srdivacky AddMatcher(new MoveChildMatcher(0)); 302203954Srdivacky EmitMatchCode(N->getChild(0), NodeNoTypes->getChild(0)); 303204642Srdivacky AddMatcher(new MoveParentMatcher()); 304203954Srdivacky return; 305203954Srdivacky } 306203954Srdivacky } 307203954Srdivacky } 308218893Sdim 309203954Srdivacky // Check that the current opcode lines up. 310204642Srdivacky AddMatcher(new CheckOpcodeMatcher(CInfo)); 311218893Sdim 312204642Srdivacky // If this node has memory references (i.e. is a load or store), tell the 313204642Srdivacky // interpreter to capture them in the memref array. 314204642Srdivacky if (N->NodeHasProperty(SDNPMemOperand, CGP)) 315204642Srdivacky AddMatcher(new RecordMemRefMatcher()); 316218893Sdim 317203954Srdivacky // If this node has a chain, then the chain is operand #0 is the SDNode, and 318203954Srdivacky // the child numbers of the node are all offset by one. 319203954Srdivacky unsigned OpNo = 0; 320204642Srdivacky if (N->NodeHasProperty(SDNPHasChain, CGP)) { 321204642Srdivacky // Record the node and remember it in our chained nodes list. 322204642Srdivacky AddMatcher(new RecordMatcher("'" + N->getOperator()->getName() + 323204642Srdivacky "' chained node", 324204642Srdivacky NextRecordedOperandNo)); 325204642Srdivacky // Remember all of the input chains our pattern will match. 326204642Srdivacky MatchedChainNodes.push_back(NextRecordedOperandNo++); 327218893Sdim 328204642Srdivacky // Don't look at the input chain when matching the tree pattern to the 329204642Srdivacky // SDNode. 330203954Srdivacky OpNo = 1; 331203954Srdivacky 332204642Srdivacky // If this node is not the root and the subtree underneath it produces a 333204642Srdivacky // chain, then the result of matching the node is also produce a chain. 334204642Srdivacky // Beyond that, this means that we're also folding (at least) the root node 335204642Srdivacky // into the node that produce the chain (for example, matching 336204642Srdivacky // "(add reg, (load ptr))" as a add_with_memory on X86). This is 337204642Srdivacky // problematic, if the 'reg' node also uses the load (say, its chain). 338204642Srdivacky // Graphically: 339204642Srdivacky // 340204642Srdivacky // [LD] 341204642Srdivacky // ^ ^ 342204642Srdivacky // | \ DAG's like cheese. 343204642Srdivacky // / | 344204642Srdivacky // / [YY] 345204642Srdivacky // | ^ 346204642Srdivacky // [XX]--/ 347204642Srdivacky // 348204642Srdivacky // It would be invalid to fold XX and LD. In this case, folding the two 349204642Srdivacky // nodes together would induce a cycle in the DAG, making it a 'cyclic DAG' 350204642Srdivacky // To prevent this, we emit a dynamic check for legality before allowing 351204642Srdivacky // this to be folded. 352204642Srdivacky // 353204642Srdivacky const TreePatternNode *Root = Pattern.getSrcPattern(); 354204642Srdivacky if (N != Root) { // Not the root of the pattern. 355203954Srdivacky // If there is a node between the root and this node, then we definitely 356203954Srdivacky // need to emit the check. 357203954Srdivacky bool NeedCheck = !Root->hasChild(N); 358218893Sdim 359203954Srdivacky // If it *is* an immediate child of the root, we can still need a check if 360203954Srdivacky // the root SDNode has multiple inputs. For us, this means that it is an 361203954Srdivacky // intrinsic, has multiple operands, or has other inputs like chain or 362218893Sdim // glue). 363203954Srdivacky if (!NeedCheck) { 364203954Srdivacky const SDNodeInfo &PInfo = CGP.getSDNodeInfo(Root->getOperator()); 365203954Srdivacky NeedCheck = 366203954Srdivacky Root->getOperator() == CGP.get_intrinsic_void_sdnode() || 367203954Srdivacky Root->getOperator() == CGP.get_intrinsic_w_chain_sdnode() || 368203954Srdivacky Root->getOperator() == CGP.get_intrinsic_wo_chain_sdnode() || 369203954Srdivacky PInfo.getNumOperands() > 1 || 370203954Srdivacky PInfo.hasProperty(SDNPHasChain) || 371218893Sdim PInfo.hasProperty(SDNPInGlue) || 372218893Sdim PInfo.hasProperty(SDNPOptInGlue); 373203954Srdivacky } 374218893Sdim 375203954Srdivacky if (NeedCheck) 376204642Srdivacky AddMatcher(new CheckFoldableChainNodeMatcher()); 377203954Srdivacky } 378203954Srdivacky } 379204642Srdivacky 380218893Sdim // If this node has an output glue and isn't the root, remember it. 381218893Sdim if (N->NodeHasProperty(SDNPOutGlue, CGP) && 382204642Srdivacky N != Pattern.getSrcPattern()) { 383218893Sdim // TODO: This redundantly records nodes with both glues and chains. 384218893Sdim 385204642Srdivacky // Record the node and remember it in our chained nodes list. 386204642Srdivacky AddMatcher(new RecordMatcher("'" + N->getOperator()->getName() + 387218893Sdim "' glue output node", 388204642Srdivacky NextRecordedOperandNo)); 389218893Sdim // Remember all of the nodes with output glue our pattern will match. 390218893Sdim MatchedGlueResultNodes.push_back(NextRecordedOperandNo++); 391204642Srdivacky } 392218893Sdim 393218893Sdim // If this node is known to have an input glue or if it *might* have an input 394218893Sdim // glue, capture it as the glue input of the pattern. 395218893Sdim if (N->NodeHasProperty(SDNPOptInGlue, CGP) || 396218893Sdim N->NodeHasProperty(SDNPInGlue, CGP)) 397218893Sdim AddMatcher(new CaptureGlueInputMatcher()); 398218893Sdim 399203954Srdivacky for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) { 400203954Srdivacky // Get the code suitable for matching this child. Move to the child, check 401203954Srdivacky // it then move back to the parent. 402204642Srdivacky AddMatcher(new MoveChildMatcher(OpNo)); 403203954Srdivacky EmitMatchCode(N->getChild(i), NodeNoTypes->getChild(i)); 404204642Srdivacky AddMatcher(new MoveParentMatcher()); 405203954Srdivacky } 406203954Srdivacky} 407203954Srdivacky 408203954Srdivacky 409203954Srdivackyvoid MatcherGen::EmitMatchCode(const TreePatternNode *N, 410203954Srdivacky TreePatternNode *NodeNoTypes) { 411203954Srdivacky // If N and NodeNoTypes don't agree on a type, then this is a case where we 412203954Srdivacky // need to do a type check. Emit the check, apply the tyep to NodeNoTypes and 413203954Srdivacky // reinfer any correlated types. 414206083Srdivacky SmallVector<unsigned, 2> ResultsToTypeCheck; 415218893Sdim 416206083Srdivacky for (unsigned i = 0, e = NodeNoTypes->getNumTypes(); i != e; ++i) { 417206083Srdivacky if (NodeNoTypes->getExtType(i) == N->getExtType(i)) continue; 418206083Srdivacky NodeNoTypes->setType(i, N->getExtType(i)); 419203954Srdivacky InferPossibleTypes(); 420206083Srdivacky ResultsToTypeCheck.push_back(i); 421203954Srdivacky } 422218893Sdim 423203954Srdivacky // If this node has a name associated with it, capture it in VariableMap. If 424203954Srdivacky // we already saw this in the pattern, emit code to verify dagness. 425203954Srdivacky if (!N->getName().empty()) { 426203954Srdivacky unsigned &VarMapEntry = VariableMap[N->getName()]; 427203954Srdivacky if (VarMapEntry == 0) { 428204642Srdivacky // If it is a named node, we must emit a 'Record' opcode. 429204642Srdivacky AddMatcher(new RecordMatcher("$" + N->getName(), NextRecordedOperandNo)); 430203954Srdivacky VarMapEntry = ++NextRecordedOperandNo; 431203954Srdivacky } else { 432203954Srdivacky // If we get here, this is a second reference to a specific name. Since 433203954Srdivacky // we already have checked that the first reference is valid, we don't 434203954Srdivacky // have to recursively match it, just check that it's the same as the 435203954Srdivacky // previously named thing. 436204642Srdivacky AddMatcher(new CheckSameMatcher(VarMapEntry-1)); 437203954Srdivacky return; 438203954Srdivacky } 439203954Srdivacky } 440218893Sdim 441203954Srdivacky if (N->isLeaf()) 442203954Srdivacky EmitLeafMatchCode(N); 443203954Srdivacky else 444203954Srdivacky EmitOperatorMatchCode(N, NodeNoTypes); 445218893Sdim 446204961Srdivacky // If there are node predicates for this node, generate their checks. 447204961Srdivacky for (unsigned i = 0, e = N->getPredicateFns().size(); i != e; ++i) 448204961Srdivacky AddMatcher(new CheckPredicateMatcher(N->getPredicateFns()[i])); 449218893Sdim 450206083Srdivacky for (unsigned i = 0, e = ResultsToTypeCheck.size(); i != e; ++i) 451206083Srdivacky AddMatcher(new CheckTypeMatcher(N->getType(ResultsToTypeCheck[i]), 452206083Srdivacky ResultsToTypeCheck[i])); 453203954Srdivacky} 454203954Srdivacky 455204642Srdivacky/// EmitMatcherCode - Generate the code that matches the predicate of this 456204642Srdivacky/// pattern for the specified Variant. If the variant is invalid this returns 457204642Srdivacky/// true and does not generate code, if it is valid, it returns false. 458204642Srdivackybool MatcherGen::EmitMatcherCode(unsigned Variant) { 459204642Srdivacky // If the root of the pattern is a ComplexPattern and if it is specified to 460204642Srdivacky // match some number of root opcodes, these are considered to be our variants. 461204642Srdivacky // Depending on which variant we're generating code for, emit the root opcode 462204642Srdivacky // check. 463204642Srdivacky if (const ComplexPattern *CP = 464204642Srdivacky Pattern.getSrcPattern()->getComplexPatternInfo(CGP)) { 465204642Srdivacky const std::vector<Record*> &OpNodes = CP->getRootNodes(); 466204642Srdivacky assert(!OpNodes.empty() &&"Complex Pattern must specify what it can match"); 467204642Srdivacky if (Variant >= OpNodes.size()) return true; 468218893Sdim 469204642Srdivacky AddMatcher(new CheckOpcodeMatcher(CGP.getSDNodeInfo(OpNodes[Variant]))); 470204642Srdivacky } else { 471204642Srdivacky if (Variant != 0) return true; 472204642Srdivacky } 473218893Sdim 474204792Srdivacky // Emit the matcher for the pattern structure and types. 475204792Srdivacky EmitMatchCode(Pattern.getSrcPattern(), PatWithNoTypes); 476218893Sdim 477203954Srdivacky // If the pattern has a predicate on it (e.g. only enabled when a subtarget 478203954Srdivacky // feature is around, do the check). 479203954Srdivacky if (!Pattern.getPredicateCheck().empty()) 480204642Srdivacky AddMatcher(new CheckPatternPredicateMatcher(Pattern.getPredicateCheck())); 481218893Sdim 482204792Srdivacky // Now that we've completed the structural type match, emit any ComplexPattern 483204792Srdivacky // checks (e.g. addrmode matches). We emit this after the structural match 484204792Srdivacky // because they are generally more expensive to evaluate and more difficult to 485204792Srdivacky // factor. 486204792Srdivacky for (unsigned i = 0, e = MatchedComplexPatterns.size(); i != e; ++i) { 487204792Srdivacky const TreePatternNode *N = MatchedComplexPatterns[i].first; 488218893Sdim 489204792Srdivacky // Remember where the results of this match get stuck. 490204792Srdivacky MatchedComplexPatterns[i].second = NextRecordedOperandNo; 491204642Srdivacky 492204792Srdivacky // Get the slot we recorded the value in from the name on the node. 493204792Srdivacky unsigned RecNodeEntry = VariableMap[N->getName()]; 494204792Srdivacky assert(!N->getName().empty() && RecNodeEntry && 495204792Srdivacky "Complex pattern should have a name and slot"); 496204792Srdivacky --RecNodeEntry; // Entries in VariableMap are biased. 497218893Sdim 498204792Srdivacky const ComplexPattern &CP = 499204792Srdivacky CGP.getComplexPattern(((DefInit*)N->getLeafValue())->getDef()); 500218893Sdim 501204792Srdivacky // Emit a CheckComplexPat operation, which does the match (aborting if it 502204792Srdivacky // fails) and pushes the matched operands onto the recorded nodes list. 503204792Srdivacky AddMatcher(new CheckComplexPatMatcher(CP, RecNodeEntry, 504204792Srdivacky N->getName(), NextRecordedOperandNo)); 505218893Sdim 506204792Srdivacky // Record the right number of operands. 507204792Srdivacky NextRecordedOperandNo += CP.getNumOperands(); 508204792Srdivacky if (CP.hasProperty(SDNPHasChain)) { 509204792Srdivacky // If the complex pattern has a chain, then we need to keep track of the 510204792Srdivacky // fact that we just recorded a chain input. The chain input will be 511204792Srdivacky // matched as the last operand of the predicate if it was successful. 512204792Srdivacky ++NextRecordedOperandNo; // Chained node operand. 513218893Sdim 514204792Srdivacky // It is the last operand recorded. 515204792Srdivacky assert(NextRecordedOperandNo > 1 && 516204792Srdivacky "Should have recorded input/result chains at least!"); 517204792Srdivacky MatchedChainNodes.push_back(NextRecordedOperandNo-1); 518204792Srdivacky } 519218893Sdim 520218893Sdim // TODO: Complex patterns can't have output glues, if they did, we'd want 521204792Srdivacky // to record them. 522204792Srdivacky } 523218893Sdim 524204642Srdivacky return false; 525203954Srdivacky} 526203954Srdivacky 527203954Srdivacky 528204642Srdivacky//===----------------------------------------------------------------------===// 529204642Srdivacky// Node Result Generation 530204642Srdivacky//===----------------------------------------------------------------------===// 531204642Srdivacky 532204642Srdivackyvoid MatcherGen::EmitResultOfNamedOperand(const TreePatternNode *N, 533204642Srdivacky SmallVectorImpl<unsigned> &ResultOps){ 534204642Srdivacky assert(!N->getName().empty() && "Operand not named!"); 535218893Sdim 536204642Srdivacky // A reference to a complex pattern gets all of the results of the complex 537204642Srdivacky // pattern's match. 538204642Srdivacky if (const ComplexPattern *CP = N->getComplexPatternInfo(CGP)) { 539204792Srdivacky unsigned SlotNo = 0; 540204792Srdivacky for (unsigned i = 0, e = MatchedComplexPatterns.size(); i != e; ++i) 541204792Srdivacky if (MatchedComplexPatterns[i].first->getName() == N->getName()) { 542204792Srdivacky SlotNo = MatchedComplexPatterns[i].second; 543204792Srdivacky break; 544204792Srdivacky } 545204792Srdivacky assert(SlotNo != 0 && "Didn't get a slot number assigned?"); 546218893Sdim 547204642Srdivacky // The first slot entry is the node itself, the subsequent entries are the 548204642Srdivacky // matched values. 549204642Srdivacky for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i) 550204792Srdivacky ResultOps.push_back(SlotNo+i); 551204642Srdivacky return; 552204642Srdivacky } 553204642Srdivacky 554204792Srdivacky unsigned SlotNo = getNamedArgumentSlot(N->getName()); 555204792Srdivacky 556204642Srdivacky // If this is an 'imm' or 'fpimm' node, make sure to convert it to the target 557204642Srdivacky // version of the immediate so that it doesn't get selected due to some other 558204642Srdivacky // node use. 559204642Srdivacky if (!N->isLeaf()) { 560204642Srdivacky StringRef OperatorName = N->getOperator()->getName(); 561204642Srdivacky if (OperatorName == "imm" || OperatorName == "fpimm") { 562204642Srdivacky AddMatcher(new EmitConvertToTargetMatcher(SlotNo)); 563204642Srdivacky ResultOps.push_back(NextRecordedOperandNo++); 564204642Srdivacky return; 565204642Srdivacky } 566204642Srdivacky } 567218893Sdim 568204642Srdivacky ResultOps.push_back(SlotNo); 569204642Srdivacky} 570204642Srdivacky 571204642Srdivackyvoid MatcherGen::EmitResultLeafAsOperand(const TreePatternNode *N, 572204642Srdivacky SmallVectorImpl<unsigned> &ResultOps) { 573204642Srdivacky assert(N->isLeaf() && "Must be a leaf"); 574218893Sdim 575204642Srdivacky if (IntInit *II = dynamic_cast<IntInit*>(N->getLeafValue())) { 576205407Srdivacky AddMatcher(new EmitIntegerMatcher(II->getValue(), N->getType(0))); 577204642Srdivacky ResultOps.push_back(NextRecordedOperandNo++); 578204642Srdivacky return; 579204642Srdivacky } 580218893Sdim 581204642Srdivacky // If this is an explicit register reference, handle it. 582204642Srdivacky if (DefInit *DI = dynamic_cast<DefInit*>(N->getLeafValue())) { 583224145Sdim Record *Def = DI->getDef(); 584224145Sdim if (Def->isSubClassOf("Register")) { 585224145Sdim const CodeGenRegister *Reg = 586224145Sdim CGP.getTargetInfo().getRegBank().getReg(Def); 587224145Sdim AddMatcher(new EmitRegisterMatcher(Reg, N->getType(0))); 588204642Srdivacky ResultOps.push_back(NextRecordedOperandNo++); 589204642Srdivacky return; 590204642Srdivacky } 591218893Sdim 592224145Sdim if (Def->getName() == "zero_reg") { 593205407Srdivacky AddMatcher(new EmitRegisterMatcher(0, N->getType(0))); 594204642Srdivacky ResultOps.push_back(NextRecordedOperandNo++); 595204642Srdivacky return; 596204642Srdivacky } 597218893Sdim 598204642Srdivacky // Handle a reference to a register class. This is used 599204642Srdivacky // in COPY_TO_SUBREG instructions. 600224145Sdim if (Def->isSubClassOf("RegisterOperand")) 601224145Sdim Def = Def->getValueAsDef("RegClass"); 602224145Sdim if (Def->isSubClassOf("RegisterClass")) { 603224145Sdim std::string Value = getQualifiedName(Def) + "RegClassID"; 604204642Srdivacky AddMatcher(new EmitStringIntegerMatcher(Value, MVT::i32)); 605204642Srdivacky ResultOps.push_back(NextRecordedOperandNo++); 606204642Srdivacky return; 607204642Srdivacky } 608208599Srdivacky 609208599Srdivacky // Handle a subregister index. This is used for INSERT_SUBREG etc. 610224145Sdim if (Def->isSubClassOf("SubRegIndex")) { 611224145Sdim std::string Value = getQualifiedName(Def); 612208599Srdivacky AddMatcher(new EmitStringIntegerMatcher(Value, MVT::i32)); 613208599Srdivacky ResultOps.push_back(NextRecordedOperandNo++); 614208599Srdivacky return; 615208599Srdivacky } 616204642Srdivacky } 617218893Sdim 618204642Srdivacky errs() << "unhandled leaf node: \n"; 619204642Srdivacky N->dump(); 620204642Srdivacky} 621204642Srdivacky 622204642Srdivacky/// GetInstPatternNode - Get the pattern for an instruction. 623218893Sdim/// 624204642Srdivackyconst TreePatternNode *MatcherGen:: 625204642SrdivackyGetInstPatternNode(const DAGInstruction &Inst, const TreePatternNode *N) { 626204642Srdivacky const TreePattern *InstPat = Inst.getPattern(); 627218893Sdim 628204642Srdivacky // FIXME2?: Assume actual pattern comes before "implicit". 629204642Srdivacky TreePatternNode *InstPatNode; 630204642Srdivacky if (InstPat) 631204642Srdivacky InstPatNode = InstPat->getTree(0); 632204642Srdivacky else if (/*isRoot*/ N == Pattern.getDstPattern()) 633204642Srdivacky InstPatNode = Pattern.getSrcPattern(); 634204642Srdivacky else 635204642Srdivacky return 0; 636218893Sdim 637204642Srdivacky if (InstPatNode && !InstPatNode->isLeaf() && 638204642Srdivacky InstPatNode->getOperator()->getName() == "set") 639204642Srdivacky InstPatNode = InstPatNode->getChild(InstPatNode->getNumChildren()-1); 640218893Sdim 641204642Srdivacky return InstPatNode; 642204642Srdivacky} 643204642Srdivacky 644223017Sdimstatic bool 645223017SdimmayInstNodeLoadOrStore(const TreePatternNode *N, 646223017Sdim const CodeGenDAGPatterns &CGP) { 647223017Sdim Record *Op = N->getOperator(); 648223017Sdim const CodeGenTarget &CGT = CGP.getTargetInfo(); 649223017Sdim CodeGenInstruction &II = CGT.getInstruction(Op); 650223017Sdim return II.mayLoad || II.mayStore; 651223017Sdim} 652223017Sdim 653223017Sdimstatic unsigned 654223017SdimnumNodesThatMayLoadOrStore(const TreePatternNode *N, 655223017Sdim const CodeGenDAGPatterns &CGP) { 656223017Sdim if (N->isLeaf()) 657223017Sdim return 0; 658223017Sdim 659223017Sdim Record *OpRec = N->getOperator(); 660223017Sdim if (!OpRec->isSubClassOf("Instruction")) 661223017Sdim return 0; 662223017Sdim 663223017Sdim unsigned Count = 0; 664223017Sdim if (mayInstNodeLoadOrStore(N, CGP)) 665223017Sdim ++Count; 666223017Sdim 667223017Sdim for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 668223017Sdim Count += numNodesThatMayLoadOrStore(N->getChild(i), CGP); 669223017Sdim 670223017Sdim return Count; 671223017Sdim} 672223017Sdim 673204642Srdivackyvoid MatcherGen:: 674204642SrdivackyEmitResultInstructionAsOperand(const TreePatternNode *N, 675204642Srdivacky SmallVectorImpl<unsigned> &OutputOps) { 676204642Srdivacky Record *Op = N->getOperator(); 677204642Srdivacky const CodeGenTarget &CGT = CGP.getTargetInfo(); 678205407Srdivacky CodeGenInstruction &II = CGT.getInstruction(Op); 679204642Srdivacky const DAGInstruction &Inst = CGP.getInstruction(Op); 680218893Sdim 681204642Srdivacky // If we can, get the pattern for the instruction we're generating. We derive 682204642Srdivacky // a variety of information from this pattern, such as whether it has a chain. 683204642Srdivacky // 684204642Srdivacky // FIXME2: This is extremely dubious for several reasons, not the least of 685204642Srdivacky // which it gives special status to instructions with patterns that Pat<> 686204642Srdivacky // nodes can't duplicate. 687204642Srdivacky const TreePatternNode *InstPatNode = GetInstPatternNode(Inst, N); 688204642Srdivacky 689218893Sdim // NodeHasChain - Whether the instruction node we're creating takes chains. 690204642Srdivacky bool NodeHasChain = InstPatNode && 691204642Srdivacky InstPatNode->TreeHasProperty(SDNPHasChain, CGP); 692218893Sdim 693239462Sdim // Instructions which load and store from memory should have a chain, 694239462Sdim // regardless of whether they happen to have an internal pattern saying so. 695239462Sdim if (Pattern.getSrcPattern()->TreeHasProperty(SDNPHasChain, CGP) 696239462Sdim && (II.hasCtrlDep || II.mayLoad || II.mayStore || II.canFoldAsLoad || 697239462Sdim II.hasSideEffects)) 698239462Sdim NodeHasChain = true; 699239462Sdim 700204642Srdivacky bool isRoot = N == Pattern.getDstPattern(); 701204642Srdivacky 702218893Sdim // TreeHasOutGlue - True if this tree has glue. 703218893Sdim bool TreeHasInGlue = false, TreeHasOutGlue = false; 704204642Srdivacky if (isRoot) { 705204642Srdivacky const TreePatternNode *SrcPat = Pattern.getSrcPattern(); 706218893Sdim TreeHasInGlue = SrcPat->TreeHasProperty(SDNPOptInGlue, CGP) || 707218893Sdim SrcPat->TreeHasProperty(SDNPInGlue, CGP); 708218893Sdim 709204642Srdivacky // FIXME2: this is checking the entire pattern, not just the node in 710204642Srdivacky // question, doing this just for the root seems like a total hack. 711218893Sdim TreeHasOutGlue = SrcPat->TreeHasProperty(SDNPOutGlue, CGP); 712204642Srdivacky } 713204642Srdivacky 714204642Srdivacky // NumResults - This is the number of results produced by the instruction in 715204642Srdivacky // the "outs" list. 716218893Sdim unsigned NumResults = Inst.getNumResults(); 717204642Srdivacky 718204642Srdivacky // Loop over all of the operands of the instruction pattern, emitting code 719204642Srdivacky // to fill them all in. The node 'N' usually has number children equal to 720204642Srdivacky // the number of input operands of the instruction. However, in cases 721204642Srdivacky // where there are predicate operands for an instruction, we need to fill 722204642Srdivacky // in the 'execute always' values. Match up the node operands to the 723204642Srdivacky // instruction operands to do this. 724204642Srdivacky SmallVector<unsigned, 8> InstOps; 725218893Sdim for (unsigned ChildNo = 0, InstOpNo = NumResults, e = II.Operands.size(); 726204642Srdivacky InstOpNo != e; ++InstOpNo) { 727218893Sdim 728204642Srdivacky // Determine what to emit for this operand. 729218893Sdim Record *OperandNode = II.Operands[InstOpNo].Rec; 730204642Srdivacky if ((OperandNode->isSubClassOf("PredicateOperand") || 731204642Srdivacky OperandNode->isSubClassOf("OptionalDefOperand")) && 732204642Srdivacky !CGP.getDefaultOperand(OperandNode).DefaultOps.empty()) { 733204642Srdivacky // This is a predicate or optional def operand; emit the 734204642Srdivacky // 'default ops' operands. 735212904Sdim const DAGDefaultOperand &DefaultOp 736218893Sdim = CGP.getDefaultOperand(OperandNode); 737204642Srdivacky for (unsigned i = 0, e = DefaultOp.DefaultOps.size(); i != e; ++i) 738204642Srdivacky EmitResultOperand(DefaultOp.DefaultOps[i], InstOps); 739204642Srdivacky continue; 740204642Srdivacky } 741218893Sdim 742206083Srdivacky const TreePatternNode *Child = N->getChild(ChildNo); 743218893Sdim 744204642Srdivacky // Otherwise this is a normal operand or a predicate operand without 745204642Srdivacky // 'execute always'; emit it. 746206083Srdivacky unsigned BeforeAddingNumOps = InstOps.size(); 747206083Srdivacky EmitResultOperand(Child, InstOps); 748206083Srdivacky assert(InstOps.size() > BeforeAddingNumOps && "Didn't add any operands"); 749218893Sdim 750206083Srdivacky // If the operand is an instruction and it produced multiple results, just 751206083Srdivacky // take the first one. 752206083Srdivacky if (!Child->isLeaf() && Child->getOperator()->isSubClassOf("Instruction")) 753206083Srdivacky InstOps.resize(BeforeAddingNumOps+1); 754218893Sdim 755204642Srdivacky ++ChildNo; 756204642Srdivacky } 757218893Sdim 758218893Sdim // If this node has input glue or explicitly specified input physregs, we 759218893Sdim // need to add chained and glued copyfromreg nodes and materialize the glue 760204642Srdivacky // input. 761204642Srdivacky if (isRoot && !PhysRegInputs.empty()) { 762204642Srdivacky // Emit all of the CopyToReg nodes for the input physical registers. These 763204642Srdivacky // occur in patterns like (mul:i8 AL:i8, GR8:i8:$src). 764204642Srdivacky for (unsigned i = 0, e = PhysRegInputs.size(); i != e; ++i) 765204642Srdivacky AddMatcher(new EmitCopyToRegMatcher(PhysRegInputs[i].second, 766205407Srdivacky PhysRegInputs[i].first)); 767218893Sdim // Even if the node has no other glue inputs, the resultant node must be 768218893Sdim // glued to the CopyFromReg nodes we just generated. 769218893Sdim TreeHasInGlue = true; 770204642Srdivacky } 771218893Sdim 772218893Sdim // Result order: node results, chain, glue 773218893Sdim 774204642Srdivacky // Determine the result types. 775204642Srdivacky SmallVector<MVT::SimpleValueType, 4> ResultVTs; 776206083Srdivacky for (unsigned i = 0, e = N->getNumTypes(); i != e; ++i) 777206083Srdivacky ResultVTs.push_back(N->getType(i)); 778218893Sdim 779204642Srdivacky // If this is the root instruction of a pattern that has physical registers in 780204642Srdivacky // its result pattern, add output VTs for them. For example, X86 has: 781204642Srdivacky // (set AL, (mul ...)) 782204642Srdivacky // This also handles implicit results like: 783204642Srdivacky // (implicit EFLAGS) 784206083Srdivacky if (isRoot && !Pattern.getDstRegs().empty()) { 785205407Srdivacky // If the root came from an implicit def in the instruction handling stuff, 786205407Srdivacky // don't re-add it. 787205407Srdivacky Record *HandledReg = 0; 788206083Srdivacky if (II.HasOneImplicitDefWithKnownVT(CGT) != MVT::Other) 789205407Srdivacky HandledReg = II.ImplicitDefs[0]; 790218893Sdim 791205407Srdivacky for (unsigned i = 0; i != Pattern.getDstRegs().size(); ++i) { 792205407Srdivacky Record *Reg = Pattern.getDstRegs()[i]; 793205407Srdivacky if (!Reg->isSubClassOf("Register") || Reg == HandledReg) continue; 794205407Srdivacky ResultVTs.push_back(getRegisterValueType(Reg, CGT)); 795205407Srdivacky } 796204642Srdivacky } 797204642Srdivacky 798205407Srdivacky // If this is the root of the pattern and the pattern we're matching includes 799205407Srdivacky // a node that is variadic, mark the generated node as variadic so that it 800205407Srdivacky // gets the excess operands from the input DAG. 801204642Srdivacky int NumFixedArityOperands = -1; 802205407Srdivacky if (isRoot && 803205407Srdivacky (Pattern.getSrcPattern()->NodeHasProperty(SDNPVariadic, CGP))) 804204642Srdivacky NumFixedArityOperands = Pattern.getSrcPattern()->getNumChildren(); 805218893Sdim 806223017Sdim // If this is the root node and multiple matched nodes in the input pattern 807223017Sdim // have MemRefs in them, have the interpreter collect them and plop them onto 808223017Sdim // this node. If there is just one node with MemRefs, leave them on that node 809223017Sdim // even if it is not the root. 810204642Srdivacky // 811223017Sdim // FIXME3: This is actively incorrect for result patterns with multiple 812223017Sdim // memory-referencing instructions. 813223017Sdim bool PatternHasMemOperands = 814223017Sdim Pattern.getSrcPattern()->TreeHasProperty(SDNPMemOperand, CGP); 815204642Srdivacky 816223017Sdim bool NodeHasMemRefs = false; 817223017Sdim if (PatternHasMemOperands) { 818223017Sdim unsigned NumNodesThatLoadOrStore = 819223017Sdim numNodesThatMayLoadOrStore(Pattern.getDstPattern(), CGP); 820223017Sdim bool NodeIsUniqueLoadOrStore = mayInstNodeLoadOrStore(N, CGP) && 821223017Sdim NumNodesThatLoadOrStore == 1; 822223017Sdim NodeHasMemRefs = 823223017Sdim NodeIsUniqueLoadOrStore || (isRoot && (mayInstNodeLoadOrStore(N, CGP) || 824223017Sdim NumNodesThatLoadOrStore != 1)); 825223017Sdim } 826223017Sdim 827218893Sdim assert((!ResultVTs.empty() || TreeHasOutGlue || NodeHasChain) && 828206083Srdivacky "Node has no result"); 829218893Sdim 830204642Srdivacky AddMatcher(new EmitNodeMatcher(II.Namespace+"::"+II.TheDef->getName(), 831204642Srdivacky ResultVTs.data(), ResultVTs.size(), 832204642Srdivacky InstOps.data(), InstOps.size(), 833218893Sdim NodeHasChain, TreeHasInGlue, TreeHasOutGlue, 834204642Srdivacky NodeHasMemRefs, NumFixedArityOperands, 835204642Srdivacky NextRecordedOperandNo)); 836218893Sdim 837218893Sdim // The non-chain and non-glue results of the newly emitted node get recorded. 838204642Srdivacky for (unsigned i = 0, e = ResultVTs.size(); i != e; ++i) { 839218893Sdim if (ResultVTs[i] == MVT::Other || ResultVTs[i] == MVT::Glue) break; 840204642Srdivacky OutputOps.push_back(NextRecordedOperandNo++); 841204642Srdivacky } 842204642Srdivacky} 843204642Srdivacky 844204642Srdivackyvoid MatcherGen:: 845204642SrdivackyEmitResultSDNodeXFormAsOperand(const TreePatternNode *N, 846204642Srdivacky SmallVectorImpl<unsigned> &ResultOps) { 847204642Srdivacky assert(N->getOperator()->isSubClassOf("SDNodeXForm") && "Not SDNodeXForm?"); 848204642Srdivacky 849204642Srdivacky // Emit the operand. 850204642Srdivacky SmallVector<unsigned, 8> InputOps; 851218893Sdim 852204642Srdivacky // FIXME2: Could easily generalize this to support multiple inputs and outputs 853204642Srdivacky // to the SDNodeXForm. For now we just support one input and one output like 854204642Srdivacky // the old instruction selector. 855204642Srdivacky assert(N->getNumChildren() == 1); 856204642Srdivacky EmitResultOperand(N->getChild(0), InputOps); 857204642Srdivacky 858204642Srdivacky // The input currently must have produced exactly one result. 859204642Srdivacky assert(InputOps.size() == 1 && "Unexpected input to SDNodeXForm"); 860204642Srdivacky 861204642Srdivacky AddMatcher(new EmitNodeXFormMatcher(InputOps[0], N->getOperator())); 862204642Srdivacky ResultOps.push_back(NextRecordedOperandNo++); 863204642Srdivacky} 864204642Srdivacky 865204642Srdivackyvoid MatcherGen::EmitResultOperand(const TreePatternNode *N, 866204642Srdivacky SmallVectorImpl<unsigned> &ResultOps) { 867204642Srdivacky // This is something selected from the pattern we matched. 868204642Srdivacky if (!N->getName().empty()) 869204642Srdivacky return EmitResultOfNamedOperand(N, ResultOps); 870204642Srdivacky 871204642Srdivacky if (N->isLeaf()) 872204642Srdivacky return EmitResultLeafAsOperand(N, ResultOps); 873204642Srdivacky 874204642Srdivacky Record *OpRec = N->getOperator(); 875204642Srdivacky if (OpRec->isSubClassOf("Instruction")) 876204642Srdivacky return EmitResultInstructionAsOperand(N, ResultOps); 877204642Srdivacky if (OpRec->isSubClassOf("SDNodeXForm")) 878204642Srdivacky return EmitResultSDNodeXFormAsOperand(N, ResultOps); 879204642Srdivacky errs() << "Unknown result node to emit code for: " << *N << '\n'; 880204642Srdivacky throw std::string("Unknown node in result pattern!"); 881204642Srdivacky} 882204642Srdivacky 883204642Srdivackyvoid MatcherGen::EmitResultCode() { 884204642Srdivacky // Patterns that match nodes with (potentially multiple) chain inputs have to 885204642Srdivacky // merge them together into a token factor. This informs the generated code 886204642Srdivacky // what all the chained nodes are. 887204642Srdivacky if (!MatchedChainNodes.empty()) 888204642Srdivacky AddMatcher(new EmitMergeInputChainsMatcher 889204642Srdivacky (MatchedChainNodes.data(), MatchedChainNodes.size())); 890218893Sdim 891204642Srdivacky // Codegen the root of the result pattern, capturing the resulting values. 892204642Srdivacky SmallVector<unsigned, 8> Ops; 893204642Srdivacky EmitResultOperand(Pattern.getDstPattern(), Ops); 894204642Srdivacky 895204642Srdivacky // At this point, we have however many values the result pattern produces. 896204642Srdivacky // However, the input pattern might not need all of these. If there are 897206083Srdivacky // excess values at the end (such as implicit defs of condition codes etc) 898218893Sdim // just lop them off. This doesn't need to worry about glue or chains, just 899206083Srdivacky // explicit results. 900204642Srdivacky // 901206083Srdivacky unsigned NumSrcResults = Pattern.getSrcPattern()->getNumTypes(); 902218893Sdim 903206083Srdivacky // If the pattern also has (implicit) results, count them as well. 904206083Srdivacky if (!Pattern.getDstRegs().empty()) { 905206083Srdivacky // If the root came from an implicit def in the instruction handling stuff, 906206083Srdivacky // don't re-add it. 907206083Srdivacky Record *HandledReg = 0; 908206083Srdivacky const TreePatternNode *DstPat = Pattern.getDstPattern(); 909206083Srdivacky if (!DstPat->isLeaf() &&DstPat->getOperator()->isSubClassOf("Instruction")){ 910206083Srdivacky const CodeGenTarget &CGT = CGP.getTargetInfo(); 911206083Srdivacky CodeGenInstruction &II = CGT.getInstruction(DstPat->getOperator()); 912206083Srdivacky 913206083Srdivacky if (II.HasOneImplicitDefWithKnownVT(CGT) != MVT::Other) 914206083Srdivacky HandledReg = II.ImplicitDefs[0]; 915206083Srdivacky } 916218893Sdim 917206083Srdivacky for (unsigned i = 0; i != Pattern.getDstRegs().size(); ++i) { 918206083Srdivacky Record *Reg = Pattern.getDstRegs()[i]; 919206083Srdivacky if (!Reg->isSubClassOf("Register") || Reg == HandledReg) continue; 920206083Srdivacky ++NumSrcResults; 921206083Srdivacky } 922218893Sdim } 923218893Sdim 924204642Srdivacky assert(Ops.size() >= NumSrcResults && "Didn't provide enough results"); 925204642Srdivacky Ops.resize(NumSrcResults); 926204642Srdivacky 927218893Sdim // If the matched pattern covers nodes which define a glue result, emit a node 928204642Srdivacky // that tells the matcher about them so that it can update their results. 929218893Sdim if (!MatchedGlueResultNodes.empty()) 930218893Sdim AddMatcher(new MarkGlueResultsMatcher(MatchedGlueResultNodes.data(), 931218893Sdim MatchedGlueResultNodes.size())); 932218893Sdim 933204642Srdivacky AddMatcher(new CompleteMatchMatcher(Ops.data(), Ops.size(), Pattern)); 934204642Srdivacky} 935204642Srdivacky 936204642Srdivacky 937204642Srdivacky/// ConvertPatternToMatcher - Create the matcher for the specified pattern with 938204642Srdivacky/// the specified variant. If the variant number is invalid, this returns null. 939204642SrdivackyMatcher *llvm::ConvertPatternToMatcher(const PatternToMatch &Pattern, 940204642Srdivacky unsigned Variant, 941204642Srdivacky const CodeGenDAGPatterns &CGP) { 942203954Srdivacky MatcherGen Gen(Pattern, CGP); 943203954Srdivacky 944203954Srdivacky // Generate the code for the matcher. 945204642Srdivacky if (Gen.EmitMatcherCode(Variant)) 946204642Srdivacky return 0; 947218893Sdim 948204642Srdivacky // FIXME2: Kill extra MoveParent commands at the end of the matcher sequence. 949204642Srdivacky // FIXME2: Split result code out to another table, and make the matcher end 950204642Srdivacky // with an "Emit <index>" command. This allows result generation stuff to be 951204642Srdivacky // shared and factored? 952218893Sdim 953203954Srdivacky // If the match succeeds, then we generate Pattern. 954204642Srdivacky Gen.EmitResultCode(); 955203954Srdivacky 956203954Srdivacky // Unconditional match. 957204642Srdivacky return Gen.GetMatcher(); 958203954Srdivacky} 959