X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=utils%2FTableGen%2FDAGISelEmitter.cpp;h=3b0d4eac1223bab1e456c9b08f823b55b76aff49;hb=4fba28116cefb160cbe11e54777bb8cde89f5d73;hp=e3b2c8920e73934ded7b730e4fb1145ac4f689e0;hpb=22faeabb3abb83e283d898b35b0b3c96e0fb2835;p=oota-llvm.git diff --git a/utils/TableGen/DAGISelEmitter.cpp b/utils/TableGen/DAGISelEmitter.cpp index e3b2c8920e7..3b0d4eac122 100644 --- a/utils/TableGen/DAGISelEmitter.cpp +++ b/utils/TableGen/DAGISelEmitter.cpp @@ -58,6 +58,8 @@ SDTypeConstraint::SDTypeConstraint(Record *R) { if (R->isSubClassOf("SDTCisVT")) { ConstraintType = SDTCisVT; x.SDTCisVT_Info.VT = getValueType(R->getValueAsDef("VT")); + } else if (R->isSubClassOf("SDTCisPtrTy")) { + ConstraintType = SDTCisPtrTy; } else if (R->isSubClassOf("SDTCisInt")) { ConstraintType = SDTCisInt; } else if (R->isSubClassOf("SDTCisFP")) { @@ -120,6 +122,10 @@ bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, case SDTCisVT: // Operand must be a particular type. return NodeToApply->UpdateNodeType(x.SDTCisVT_Info.VT, TP); + case SDTCisPtrTy: { + // Operand must be same as target pointer type. + return NodeToApply->UpdateNodeType(CGT.getPointerType(), TP); + } case SDTCisInt: { // If there is only one integer type supported, this must be it. std::vector IntVTs = @@ -290,6 +296,7 @@ bool TreePatternNode::UpdateNodeType(unsigned char VT, TreePattern &TP) { if (isLeaf()) { dump(); + std::cerr << " "; TP.error("Type inference contradiction found in node!"); } else { TP.error("Type inference contradiction found in node " + @@ -477,7 +484,9 @@ static unsigned char getIntrinsicType(Record *R, bool NotRegisters, } else if (R->isSubClassOf("ValueType") || R->isSubClassOf("CondCode")) { // Using a VTSDNode or CondCodeSDNode. return MVT::Other; - } else if (R->getName() == "node") { + } else if (R->isSubClassOf("ComplexPattern")) { + return TP.getDAGISelEmitter().getComplexPattern(R).getValueType(); + } else if (R->getName() == "node" || R->getName() == "srcvalue") { // Placeholder. return MVT::isUnknown; } @@ -609,7 +618,7 @@ bool TreePatternNode::canPatternMatch(std::string &Reason, DAGISelEmitter &ISE){ for (unsigned i = 0, e = getNumChildren(); i != e; ++i) if (!getChild(i)->canPatternMatch(Reason, ISE)) return false; - + // If this node is a commutative operator, check that the LHS isn't an // immediate. const SDNodeInfo &NodeInfo = ISE.getSDNodeInfo(getOperator()); @@ -833,6 +842,13 @@ void DAGISelEmitter::ParseNodeTransforms(std::ostream &OS) { } } +void DAGISelEmitter::ParseComplexPatterns() { + std::vector AMs = Records.getAllDerivedDefinitions("ComplexPattern"); + while (!AMs.empty()) { + ComplexPatterns.insert(std::make_pair(AMs.back(), AMs.back())); + AMs.pop_back(); + } +} /// ParsePatternFragments - Parse all of the PatFrag definitions in the .td @@ -936,14 +952,17 @@ void DAGISelEmitter::ParsePatternFragments(std::ostream &OS) { /// HandleUse - Given "Pat" a leaf in the pattern, check to see if it is an /// instruction input. Return true if this is a real use. static bool HandleUse(TreePattern *I, TreePatternNode *Pat, - std::map &InstInputs) { + std::map &InstInputs, + std::vector &InstImpInputs) { // No name -> not interesting. if (Pat->getName().empty()) { if (Pat->isLeaf()) { DefInit *DI = dynamic_cast(Pat->getLeafValue()); if (DI && DI->getDef()->isSubClassOf("RegisterClass")) I->error("Input " + DI->getDef()->getName() + " must be named!"); - + else if (DI && DI->getDef()->isSubClassOf("Register")) { + InstImpInputs.push_back(DI->getDef()); + } } return false; } @@ -958,6 +977,10 @@ static bool HandleUse(TreePattern *I, TreePatternNode *Pat, Rec = Pat->getOperator(); } + // SRCVALUE nodes are ignored. + if (Rec->getName() == "srcvalue") + return false; + TreePatternNode *&Slot = InstInputs[Pat->getName()]; if (!Slot) { Slot = Pat; @@ -985,9 +1008,11 @@ static bool HandleUse(TreePattern *I, TreePatternNode *Pat, void DAGISelEmitter:: FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, std::map &InstInputs, - std::map &InstResults) { + std::map &InstResults, + std::vector &InstImpInputs, + std::vector &InstImpResults) { if (Pat->isLeaf()) { - bool isUse = HandleUse(I, Pat, InstInputs); + bool isUse = HandleUse(I, Pat, InstInputs, InstImpInputs); if (!isUse && Pat->getTransformFn()) I->error("Cannot specify a transform function for a non-input value!"); return; @@ -997,14 +1022,15 @@ FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) { if (Pat->getChild(i)->getExtType() == MVT::isVoid) I->error("Cannot have void nodes inside of patterns!"); - FindPatternInputsAndOutputs(I, Pat->getChild(i), InstInputs, InstResults); + FindPatternInputsAndOutputs(I, Pat->getChild(i), InstInputs, InstResults, + InstImpInputs, InstImpResults); } // If this is a non-leaf node with no children, treat it basically as if // it were a leaf. This handles nodes like (imm). bool isUse = false; if (Pat->getNumChildren() == 0) - isUse = HandleUse(I, Pat, InstInputs); + isUse = HandleUse(I, Pat, InstInputs, InstImpInputs); if (!isUse && Pat->getTransformFn()) I->error("Cannot specify a transform function for a non-input value!"); @@ -1025,24 +1051,56 @@ FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, for (unsigned i = 0; i != NumValues; ++i) { TreePatternNode *Dest = Pat->getChild(i); if (!Dest->isLeaf()) - I->error("set destination should be a virtual register!"); + I->error("set destination should be a register!"); DefInit *Val = dynamic_cast(Dest->getLeafValue()); if (!Val) - I->error("set destination should be a virtual register!"); + I->error("set destination should be a register!"); + + if (Val->getDef()->isSubClassOf("RegisterClass")) { + if (Dest->getName().empty()) + I->error("set destination must have a name!"); + if (InstResults.count(Dest->getName())) + I->error("cannot set '" + Dest->getName() +"' multiple times"); + InstResults[Dest->getName()] = Val->getDef(); + } else if (Val->getDef()->isSubClassOf("Register")) { + InstImpResults.push_back(Val->getDef()); + } else { + I->error("set destination should be a register!"); + } - if (!Val->getDef()->isSubClassOf("RegisterClass")) - I->error("set destination should be a virtual register!"); - if (Dest->getName().empty()) - I->error("set destination must have a name!"); - if (InstResults.count(Dest->getName())) - I->error("cannot set '" + Dest->getName() +"' multiple times"); - InstResults[Dest->getName()] = Val->getDef(); - // Verify and collect info from the computation. FindPatternInputsAndOutputs(I, Pat->getChild(i+NumValues), - InstInputs, InstResults); + InstInputs, InstResults, InstImpInputs, InstImpResults); + } +} + +/// NodeHasChain - return true if TreePatternNode has the property +/// 'hasChain', meaning it reads a ctrl-flow chain operand and writes +/// a chain result. +static bool NodeHasChain(TreePatternNode *N, DAGISelEmitter &ISE) +{ + if (N->isLeaf()) return false; + Record *Operator = N->getOperator(); + if (!Operator->isSubClassOf("SDNode")) return false; + + const SDNodeInfo &NodeInfo = ISE.getSDNodeInfo(Operator); + return NodeInfo.hasProperty(SDNodeInfo::SDNPHasChain); +} + +static bool PatternHasCtrlDep(TreePatternNode *N, DAGISelEmitter &ISE) +{ + if (NodeHasChain(N, ISE)) + return true; + else { + for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { + TreePatternNode *Child = N->getChild(i); + if (PatternHasCtrlDep(Child, ISE)) + return true; + } } + + return false; } @@ -1087,8 +1145,11 @@ void DAGISelEmitter::ParseInstructions() { } // Create and insert the instruction. + std::vector ImpResults; + std::vector ImpOperands; Instructions.insert(std::make_pair(Instrs[i], - DAGInstruction(0, Results, Operands))); + DAGInstruction(0, Results, Operands, + ImpResults, ImpOperands))); continue; // no pattern. } @@ -1109,6 +1170,9 @@ void DAGISelEmitter::ParseInstructions() { // InstResults - Keep track of all the virtual registers that are 'set' // in the instruction, including what reg class they are. std::map InstResults; + + std::vector InstImpInputs; + std::vector InstImpResults; // Verify that the top-level forms in the instruction are of void type, and // fill in the InstResults map. @@ -1119,7 +1183,8 @@ void DAGISelEmitter::ParseInstructions() { " void types"); // Find inputs and outputs, and verify the structure of the uses/defs. - FindPatternInputsAndOutputs(I, Pat, InstInputs, InstResults); + FindPatternInputsAndOutputs(I, Pat, InstInputs, InstResults, + InstImpInputs, InstImpResults); } // Now that we have inputs and outputs of the pattern, inspect the operands @@ -1176,9 +1241,10 @@ void DAGISelEmitter::ParseInstructions() { if (InVal->isLeaf() && dynamic_cast(InVal->getLeafValue())) { Record *InRec = static_cast(InVal->getLeafValue())->getDef(); - if (CGI.OperandList[i].Rec != InRec) + if (CGI.OperandList[i].Rec != InRec && + !InRec->isSubClassOf("ComplexPattern")) I->error("Operand $" + OpName + - "'s register class disagrees between the operand and pattern"); + "'s register class disagrees between the operand and pattern"); } Operands.push_back(CGI.OperandList[i].Rec); @@ -1207,7 +1273,7 @@ void DAGISelEmitter::ParseInstructions() { new TreePatternNode(I->getRecord(), ResultNodeOperands); // Create and insert the instruction. - DAGInstruction TheInst(I, Results, Operands); + DAGInstruction TheInst(I, Results, Operands, InstImpResults, InstImpInputs); Instructions.insert(std::make_pair(I->getRecord(), TheInst)); // Use a temporary tree pattern to infer all types and make sure that the @@ -1228,31 +1294,37 @@ void DAGISelEmitter::ParseInstructions() { DAGInstruction &TheInst = II->second; TreePattern *I = TheInst.getPattern(); if (I == 0) continue; // No pattern. - + if (I->getNumTrees() != 1) { std::cerr << "CANNOT HANDLE: " << I->getRecord()->getName() << " yet!"; continue; } TreePatternNode *Pattern = I->getTree(0); TreePatternNode *SrcPattern; - if (TheInst.getNumResults() == 0) { - SrcPattern = Pattern; - } else { - if (Pattern->getOperator()->getName() != "set") - continue; // Not a set (store or something?) - + if (Pattern->getOperator()->getName() == "set") { if (Pattern->getNumChildren() != 2) continue; // Not a set of a single value (not handled so far) SrcPattern = Pattern->getChild(1)->clone(); + } else{ + // Not a set (store or something?) + SrcPattern = Pattern; } std::string Reason; if (!SrcPattern->canPatternMatch(Reason, *this)) I->error("Instruction can never match: " + Reason); + Record *Instr = II->first; TreePatternNode *DstPattern = TheInst.getResultPattern(); - PatternsToMatch.push_back(std::make_pair(SrcPattern, DstPattern)); + PatternsToMatch. + push_back(PatternToMatch(Instr->getValueAsListInit("Predicates"), + SrcPattern, DstPattern)); + + if (PatternHasCtrlDep(Pattern, *this)) { + CodeGenInstruction &InstInfo = Target.getInstruction(Instr->getName()); + InstInfo.hasCtrlDep = true; + } } } @@ -1275,8 +1347,11 @@ void DAGISelEmitter::ParsePatterns() { { std::map InstInputs; std::map InstResults; + std::vector InstImpInputs; + std::vector InstImpResults; FindPatternInputsAndOutputs(Pattern, Pattern->getOnlyTree(), - InstInputs, InstResults); + InstInputs, InstResults, + InstImpInputs, InstImpResults); } ListInit *LI = Patterns[i]->getValueAsListInit("ResultInstrs"); @@ -1301,8 +1376,10 @@ void DAGISelEmitter::ParsePatterns() { if (!Pattern->getOnlyTree()->canPatternMatch(Reason, *this)) Pattern->error("Pattern can never match: " + Reason); - PatternsToMatch.push_back(std::make_pair(Pattern->getOnlyTree(), - Result->getOnlyTree())); + PatternsToMatch. + push_back(PatternToMatch(Patterns[i]->getValueAsListInit("Predicates"), + Pattern->getOnlyTree(), + Result->getOnlyTree())); } } @@ -1510,7 +1587,7 @@ void DAGISelEmitter::GenerateVariants() { // for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) { std::vector Variants; - GenerateVariantsOf(PatternsToMatch[i].first, Variants, *this); + GenerateVariantsOf(PatternsToMatch[i].getSrcPattern(), Variants, *this); assert(!Variants.empty() && "Must create at least original variant!"); Variants.erase(Variants.begin()); // Remove the original pattern. @@ -1519,7 +1596,7 @@ void DAGISelEmitter::GenerateVariants() { continue; DEBUG(std::cerr << "FOUND VARIANTS OF: "; - PatternsToMatch[i].first->dump(); + PatternsToMatch[i].getSrcPattern()->dump(); std::cerr << "\n"); for (unsigned v = 0, e = Variants.size(); v != e; ++v) { @@ -1533,7 +1610,7 @@ void DAGISelEmitter::GenerateVariants() { bool AlreadyExists = false; for (unsigned p = 0, e = PatternsToMatch.size(); p != e; ++p) { // Check to see if this variant already exists. - if (Variant->isIsomorphicTo(PatternsToMatch[p].first)) { + if (Variant->isIsomorphicTo(PatternsToMatch[p].getSrcPattern())) { DEBUG(std::cerr << " *** ALREADY EXISTS, ignoring variant.\n"); AlreadyExists = true; break; @@ -1543,8 +1620,9 @@ void DAGISelEmitter::GenerateVariants() { if (AlreadyExists) continue; // Otherwise, add it to the list of patterns we have. - PatternsToMatch.push_back(std::make_pair(Variant, - PatternsToMatch[i].second)); + PatternsToMatch. + push_back(PatternToMatch(PatternsToMatch[i].getPredicates(), + Variant, PatternsToMatch[i].getDstPattern())); } DEBUG(std::cerr << "\n"); @@ -1552,22 +1630,60 @@ void DAGISelEmitter::GenerateVariants() { } +// NodeIsComplexPattern - return true if N is a leaf node and a subclass of +// ComplexPattern. +static bool NodeIsComplexPattern(TreePatternNode *N) +{ + return (N->isLeaf() && + dynamic_cast(N->getLeafValue()) && + static_cast(N->getLeafValue())->getDef()-> + isSubClassOf("ComplexPattern")); +} + +// NodeGetComplexPattern - return the pointer to the ComplexPattern if N +// is a leaf node and a subclass of ComplexPattern, else it returns NULL. +static const ComplexPattern *NodeGetComplexPattern(TreePatternNode *N, + DAGISelEmitter &ISE) +{ + if (N->isLeaf() && + dynamic_cast(N->getLeafValue()) && + static_cast(N->getLeafValue())->getDef()-> + isSubClassOf("ComplexPattern")) { + return &ISE.getComplexPattern(static_cast(N->getLeafValue()) + ->getDef()); + } + return NULL; +} + /// getPatternSize - Return the 'size' of this pattern. We want to match large /// patterns before small ones. This is used to determine the size of a /// pattern. -static unsigned getPatternSize(TreePatternNode *P) { +static unsigned getPatternSize(TreePatternNode *P, DAGISelEmitter &ISE) { assert(isExtIntegerVT(P->getExtType()) || isExtFloatingPointVT(P->getExtType()) || - P->getExtType() == MVT::isVoid && "Not a valid pattern node to size!"); + P->getExtType() == MVT::isVoid || + P->getExtType() == MVT::Flag && "Not a valid pattern node to size!"); unsigned Size = 1; // The node itself. - + + // FIXME: This is a hack to statically increase the priority of patterns + // which maps a sub-dag to a complex pattern. e.g. favors LEA over ADD. + // Later we can allow complexity / cost for each pattern to be (optionally) + // specified. To get best possible pattern match we'll need to dynamically + // calculate the complexity of all patterns a dag can potentially map to. + const ComplexPattern *AM = NodeGetComplexPattern(P, ISE); + if (AM) + Size += AM->getNumOperands(); + // Count children in the count if they are also nodes. for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) { TreePatternNode *Child = P->getChild(i); if (!Child->isLeaf() && Child->getExtType() != MVT::Other) - Size += getPatternSize(Child); - else if (Child->isLeaf() && dynamic_cast(Child->getLeafValue())) { - ++Size; // Matches a ConstantSDNode. + Size += getPatternSize(Child, ISE); + else if (Child->isLeaf()) { + if (dynamic_cast(Child->getLeafValue())) + ++Size; // Matches a ConstantSDNode. + else if (NodeIsComplexPattern(Child)) + Size += getPatternSize(Child, ISE); } } @@ -1590,422 +1706,600 @@ static unsigned getResultPatternCost(TreePatternNode *P) { // In particular, we want to match maximal patterns first and lowest cost within // a particular complexity first. struct PatternSortingPredicate { - bool operator()(DAGISelEmitter::PatternToMatch *LHS, - DAGISelEmitter::PatternToMatch *RHS) { - unsigned LHSSize = getPatternSize(LHS->first); - unsigned RHSSize = getPatternSize(RHS->first); + PatternSortingPredicate(DAGISelEmitter &ise) : ISE(ise) {}; + DAGISelEmitter &ISE; + + bool operator()(PatternToMatch *LHS, + PatternToMatch *RHS) { + unsigned LHSSize = getPatternSize(LHS->getSrcPattern(), ISE); + unsigned RHSSize = getPatternSize(RHS->getSrcPattern(), ISE); if (LHSSize > RHSSize) return true; // LHS -> bigger -> less cost if (LHSSize < RHSSize) return false; // If the patterns have equal complexity, compare generated instruction cost - return getResultPatternCost(LHS->second) second); + return getResultPatternCost(LHS->getDstPattern()) < + getResultPatternCost(RHS->getDstPattern()); } }; -/// nodeHasChain - return true if TreePatternNode has the property -/// 'hasChain', meaning it reads a ctrl-flow chain operand and writes -/// a chain result. -static bool nodeHasChain(TreePatternNode *N, DAGISelEmitter &ISE) -{ - if (N->isLeaf()) return false; - - const SDNodeInfo &NodeInfo = ISE.getSDNodeInfo(N->getOperator()); - return NodeInfo.hasProperty(SDNodeInfo::SDNPHasChain); +/// getRegisterValueType - Look up and return the first ValueType of specified +/// RegisterClass record +static MVT::ValueType getRegisterValueType(Record *R, const CodeGenTarget &T) { + if (const CodeGenRegisterClass *RC = T.getRegisterClassForRegister(R)) + return RC->getValueTypeNum(0); + return MVT::Other; } -/// EmitMatchForPattern - Emit a matcher for N, going to the label for PatternNo -/// if the match fails. At this point, we already know that the opcode for N -/// matches, and the SDNode for the result has the RootName specified name. -void DAGISelEmitter::EmitMatchForPattern(TreePatternNode *N, - const std::string &RootName, - std::map &VarMap, - unsigned PatternNo,std::ostream &OS) { - if (N->isLeaf()) { - if (IntInit *II = dynamic_cast(N->getLeafValue())) { - OS << " if (cast(" << RootName - << ")->getSignExtended() != " << II->getValue() << ")\n" - << " goto P" << PatternNo << "Fail;\n"; - return; - } - assert(0 && "Cannot match this as a leaf value!"); - abort(); - } - - // If this node has a name associated with it, capture it in VarMap. If - // we already saw this in the pattern, emit code to verify dagness. - if (!N->getName().empty()) { - std::string &VarMapEntry = VarMap[N->getName()]; - if (VarMapEntry.empty()) { - VarMapEntry = RootName; - } else { - // If we get here, this is a second reference to a specific name. Since - // we already have checked that the first reference is valid, we don't - // have to recursively match it, just check that it's the same as the - // previously named thing. - OS << " if (" << VarMapEntry << " != " << RootName - << ") goto P" << PatternNo << "Fail;\n"; - return; - } - } +/// RemoveAllTypes - A quick recursive walk over a pattern which removes all +/// type information from it. +static void RemoveAllTypes(TreePatternNode *N) { + N->setType(MVT::isUnknown); + if (!N->isLeaf()) + for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) + RemoveAllTypes(N->getChild(i)); +} - // Emit code to load the child nodes and match their contents recursively. - unsigned OpNo = (unsigned) nodeHasChain(N, *this); - for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) { - OS << " SDOperand " << RootName << OpNo <<" = " << RootName - << ".getOperand(" << OpNo << ");\n"; - TreePatternNode *Child = N->getChild(i); - - if (!Child->isLeaf()) { - // If it's not a leaf, recursively match. - const SDNodeInfo &CInfo = getSDNodeInfo(Child->getOperator()); - OS << " if (" << RootName << OpNo << ".getOpcode() != " - << CInfo.getEnumName() << ") goto P" << PatternNo << "Fail;\n"; - EmitMatchForPattern(Child, RootName + utostr(OpNo), VarMap, PatternNo, - OS); - } else { - // If this child has a name associated with it, capture it in VarMap. If - // we already saw this in the pattern, emit code to verify dagness. - if (!Child->getName().empty()) { - std::string &VarMapEntry = VarMap[Child->getName()]; - if (VarMapEntry.empty()) { - VarMapEntry = RootName + utostr(OpNo); - } else { - // If we get here, this is a second reference to a specific name. Since - // we already have checked that the first reference is valid, we don't - // have to recursively match it, just check that it's the same as the - // previously named thing. - OS << " if (" << VarMapEntry << " != " << RootName << OpNo - << ") goto P" << PatternNo << "Fail;\n"; - continue; +Record *DAGISelEmitter::getSDNodeNamed(const std::string &Name) const { + Record *N = Records.getDef(Name); + assert(N && N->isSubClassOf("SDNode") && "Bad argument"); + return N; +} + +class PatternCodeEmitter { +private: + DAGISelEmitter &ISE; + + // Predicates. + ListInit *Predicates; + // Instruction selector pattern. + TreePatternNode *Pattern; + // Matched instruction. + TreePatternNode *Instruction; + unsigned PatternNo; + std::ostream &OS; + // Node to name mapping + std::map VariableMap; + // Names of all the folded nodes which produce chains. + std::vector > FoldedChains; + bool FoundChain; + unsigned TmpNo; + +public: + PatternCodeEmitter(DAGISelEmitter &ise, ListInit *preds, + TreePatternNode *pattern, TreePatternNode *instr, + unsigned PatNum, std::ostream &os) : + ISE(ise), Predicates(preds), Pattern(pattern), Instruction(instr), + PatternNo(PatNum), OS(os), FoundChain(false), TmpNo(0) {}; + + /// EmitMatchCode - Emit a matcher for N, going to the label for PatternNo + /// if the match fails. At this point, we already know that the opcode for N + /// matches, and the SDNode for the result has the RootName specified name. + void EmitMatchCode(TreePatternNode *N, const std::string &RootName, + bool isRoot = false) { + + // Emit instruction predicates. Each predicate is just a string for now. + if (isRoot) { + for (unsigned i = 0, e = Predicates->getSize(); i != e; ++i) { + if (DefInit *Pred = dynamic_cast(Predicates->getElement(i))) { + Record *Def = Pred->getDef(); + if (Def->isSubClassOf("Predicate")) { + if (i == 0) + OS << " if ("; + else + OS << " && "; + OS << "(" << Def->getValueAsString("CondString") << ")"; + if (i == e-1) + OS << ") goto P" << PatternNo << "Fail;\n"; + } else { + Def->dump(); + assert(0 && "Unknown predicate type!"); + } } } - - // Handle leaves of various types. - if (DefInit *DI = dynamic_cast(Child->getLeafValue())) { - Record *LeafRec = DI->getDef(); - if (LeafRec->isSubClassOf("RegisterClass") || - LeafRec->isSubClassOf("Register")) { - // Handle register references. Nothing to do here. - } else if (LeafRec->isSubClassOf("ValueType")) { - // Make sure this is the specified value type. - OS << " if (cast(" << RootName << OpNo << ")->getVT() != " - << "MVT::" << LeafRec->getName() << ") goto P" << PatternNo - << "Fail;\n"; - } else if (LeafRec->isSubClassOf("CondCode")) { - // Make sure this is the specified cond code. - OS << " if (cast(" << RootName << OpNo - << ")->get() != " << "ISD::" << LeafRec->getName() - << ") goto P" << PatternNo << "Fail;\n"; - } else { - Child->dump(); - assert(0 && "Unknown leaf type!"); - } - } else if (IntInit *II = dynamic_cast(Child->getLeafValue())) { - OS << " if (!isa(" << RootName << OpNo << ") ||\n" - << " cast(" << RootName << OpNo + } + + if (N->isLeaf()) { + if (IntInit *II = dynamic_cast(N->getLeafValue())) { + OS << " if (cast(" << RootName << ")->getSignExtended() != " << II->getValue() << ")\n" << " goto P" << PatternNo << "Fail;\n"; + return; + } else if (!NodeIsComplexPattern(N)) { + assert(0 && "Cannot match this as a leaf value!"); + abort(); + } + } + + // If this node has a name associated with it, capture it in VariableMap. If + // we already saw this in the pattern, emit code to verify dagness. + if (!N->getName().empty()) { + std::string &VarMapEntry = VariableMap[N->getName()]; + if (VarMapEntry.empty()) { + VarMapEntry = RootName; } else { - Child->dump(); - assert(0 && "Unknown leaf type!"); + // If we get here, this is a second reference to a specific name. Since + // we already have checked that the first reference is valid, we don't + // have to recursively match it, just check that it's the same as the + // previously named thing. + OS << " if (" << VarMapEntry << " != " << RootName + << ") goto P" << PatternNo << "Fail;\n"; + return; } } - } - - // If there is a node predicate for this, emit the call. - if (!N->getPredicateFn().empty()) - OS << " if (!" << N->getPredicateFn() << "(" << RootName - << ".Val)) goto P" << PatternNo << "Fail;\n"; -} - -/// getRegisterValueType - Look up and return the first ValueType of specified -/// RegisterClass record -static MVT::ValueType getRegisterValueType(Record *R, const CodeGenTarget &T) { - if (const CodeGenRegisterClass *RC = T.getRegisterClassForRegister(R)) - return RC->getValueTypeNum(0); - return MVT::Other; -} -/// EmitLeadChainForPattern - Emit the flag operands for the DAG that will be -/// built in CodeGenPatternResult. -void DAGISelEmitter::EmitLeadChainForPattern(TreePatternNode *N, - const std::string &RootName, - std::ostream &OS, - bool &HasChain) { - if (!N->isLeaf()) { - Record *Op = N->getOperator(); - if (Op->isSubClassOf("Instruction")) { - bool HasCtrlDep = Op->getValueAsBit("hasCtrlDep"); - unsigned OpNo = (unsigned) HasCtrlDep; - for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) - EmitLeadChainForPattern(N->getChild(i), RootName + utostr(OpNo), - OS, HasChain); - - if (!HasChain && HasCtrlDep) { - OS << " SDOperand Chain = Select(" - << RootName << ".getOperand(0));\n"; - HasChain = true; + // Emit code to load the child nodes and match their contents recursively. + unsigned OpNo = 0; + bool HasChain = NodeHasChain(N, ISE); + if (HasChain) { + OpNo = 1; + if (!isRoot) { + const SDNodeInfo &CInfo = ISE.getSDNodeInfo(N->getOperator()); + OS << " if (!" << RootName << ".hasOneUse()) goto P" + << PatternNo << "Fail; // Multiple uses of actual result?\n"; + OS << " if (CodeGenMap.count(" << RootName + << ".getValue(" << CInfo.getNumResults() << "))) goto P" + << PatternNo << "Fail; // Already selected for a chain use?\n"; } } - } -} -/// EmitCopyToRegsForPattern - Emit the flag operands for the DAG that will be -/// built in CodeGenPatternResult. -void DAGISelEmitter::EmitCopyToRegsForPattern(TreePatternNode *N, - const std::string &RootName, - std::ostream &OS, - bool &HasChain, bool &InFlag) { - const CodeGenTarget &T = getTargetInfo(); - unsigned OpNo = (unsigned) nodeHasChain(N, *this); - for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) { - TreePatternNode *Child = N->getChild(i); - if (!Child->isLeaf()) { - EmitCopyToRegsForPattern(Child, RootName + utostr(OpNo), OS, HasChain, - InFlag); - } else { - if (DefInit *DI = dynamic_cast(Child->getLeafValue())) { - Record *RR = DI->getDef(); - if (RR->isSubClassOf("Register")) { - MVT::ValueType RVT = getRegisterValueType(RR, T); - if (!InFlag) { - OS << " SDOperand InFlag = SDOperand(0,0);\n"; - InFlag = true; + for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) { + OS << " SDOperand " << RootName << OpNo <<" = " << RootName + << ".getOperand(" << OpNo << ");\n"; + TreePatternNode *Child = N->getChild(i); + + if (!Child->isLeaf()) { + // If it's not a leaf, recursively match. + const SDNodeInfo &CInfo = ISE.getSDNodeInfo(Child->getOperator()); + OS << " if (" << RootName << OpNo << ".getOpcode() != " + << CInfo.getEnumName() << ") goto P" << PatternNo << "Fail;\n"; + EmitMatchCode(Child, RootName + utostr(OpNo)); + if (NodeHasChain(Child, ISE)) { + FoldedChains.push_back(std::make_pair(RootName + utostr(OpNo), + CInfo.getNumResults())); + } + } else { + // If this child has a name associated with it, capture it in VarMap. If + // we already saw this in the pattern, emit code to verify dagness. + if (!Child->getName().empty()) { + std::string &VarMapEntry = VariableMap[Child->getName()]; + if (VarMapEntry.empty()) { + VarMapEntry = RootName + utostr(OpNo); + } else { + // If we get here, this is a second reference to a specific name. Since + // we already have checked that the first reference is valid, we don't + // have to recursively match it, just check that it's the same as the + // previously named thing. + OS << " if (" << VarMapEntry << " != " << RootName << OpNo + << ") goto P" << PatternNo << "Fail;\n"; + continue; } - if (HasChain) { - OS << " SDOperand " << RootName << "CR" << i << ";\n"; - OS << " " << RootName << "CR" << i - << " = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(" - << getQualifiedName(RR) << ", MVT::" << getEnumName(RVT) << ")" - << ", Select(" << RootName << OpNo << "), InFlag);\n"; - OS << " Chain = " << RootName << "CR" << i - << ".getValue(0);\n"; - OS << " InFlag = " << RootName << "CR" << i - << ".getValue(1);\n"; + } + + // Handle leaves of various types. + if (DefInit *DI = dynamic_cast(Child->getLeafValue())) { + Record *LeafRec = DI->getDef(); + if (LeafRec->isSubClassOf("RegisterClass")) { + // Handle register references. Nothing to do here. + } else if (LeafRec->isSubClassOf("Register")) { + } else if (LeafRec->isSubClassOf("ComplexPattern")) { + // Handle complex pattern. Nothing to do here. + } else if (LeafRec->getName() == "srcvalue") { + // Place holder for SRCVALUE nodes. Nothing to do here. + } else if (LeafRec->isSubClassOf("ValueType")) { + // Make sure this is the specified value type. + OS << " if (cast(" << RootName << OpNo << ")->getVT() != " + << "MVT::" << LeafRec->getName() << ") goto P" << PatternNo + << "Fail;\n"; + } else if (LeafRec->isSubClassOf("CondCode")) { + // Make sure this is the specified cond code. + OS << " if (cast(" << RootName << OpNo + << ")->get() != " << "ISD::" << LeafRec->getName() + << ") goto P" << PatternNo << "Fail;\n"; } else { - OS << " InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode()" - << ", CurDAG->getRegister(" << getQualifiedName(RR) - << ", MVT::" << getEnumName(RVT) << ")" - << ", Select(" << RootName << OpNo - << "), InFlag).getValue(1);\n"; + Child->dump(); + assert(0 && "Unknown leaf type!"); } + } else if (IntInit *II = dynamic_cast(Child->getLeafValue())) { + OS << " if (!isa(" << RootName << OpNo << ") ||\n" + << " cast(" << RootName << OpNo + << ")->getSignExtended() != " << II->getValue() << ")\n" + << " goto P" << PatternNo << "Fail;\n"; + } else { + Child->dump(); + assert(0 && "Unknown leaf type!"); } } } - } -} -/// CodeGenPatternResult - Emit the action for a pattern. Now that it has -/// matched, we actually have to build a DAG! -unsigned DAGISelEmitter:: -CodeGenPatternResult(TreePatternNode *N, unsigned &Ctr, - std::map &VariableMap, - std::ostream &OS, bool &HasChain, bool InFlag, - bool isRoot) { - // This is something selected from the pattern we matched. - if (!N->getName().empty()) { - assert(!isRoot && "Root of pattern cannot be a leaf!"); - std::string &Val = VariableMap[N->getName()]; - assert(!Val.empty() && - "Variable referenced but not defined and not caught earlier!"); - if (Val[0] == 'T' && Val[1] == 'm' && Val[2] == 'p') { - // Already selected this operand, just return the tmpval. - return atoi(Val.c_str()+3); - } - - unsigned ResNo = Ctr++; - if (!N->isLeaf() && N->getOperator()->getName() == "imm") { - switch (N->getType()) { - default: assert(0 && "Unknown type for constant node!"); - case MVT::i1: OS << " bool Tmp"; break; - case MVT::i8: OS << " unsigned char Tmp"; break; - case MVT::i16: OS << " unsigned short Tmp"; break; - case MVT::i32: OS << " unsigned Tmp"; break; - case MVT::i64: OS << " uint64_t Tmp"; break; + if (HasChain) { + if (!FoundChain) { + OS << " SDOperand Chain = " << RootName << ".getOperand(0);\n"; + FoundChain = true; } - OS << ResNo << "C = cast(" << Val << ")->getValue();\n"; - OS << " SDOperand Tmp" << ResNo << " = CurDAG->getTargetConstant(Tmp" - << ResNo << "C, MVT::" << getEnumName(N->getType()) << ");\n"; - } else if (!N->isLeaf() && N->getOperator()->getName() == "tglobaladdr") { - OS << " SDOperand Tmp" << ResNo << " = " << Val << ";\n"; - } else { - OS << " SDOperand Tmp" << ResNo << " = Select(" << Val << ");\n"; } - // Add Tmp to VariableMap, so that we don't multiply select this - // value if used multiple times by this pattern result. - Val = "Tmp"+utostr(ResNo); - return ResNo; + + // If there is a node predicate for this, emit the call. + if (!N->getPredicateFn().empty()) + OS << " if (!" << N->getPredicateFn() << "(" << RootName + << ".Val)) goto P" << PatternNo << "Fail;\n"; } + + /// EmitResultCode - Emit the action for a pattern. Now that it has matched + /// we actually have to build a DAG! + std::pair + EmitResultCode(TreePatternNode *N, bool isRoot = false) { + // This is something selected from the pattern we matched. + if (!N->getName().empty()) { + assert(!isRoot && "Root of pattern cannot be a leaf!"); + std::string &Val = VariableMap[N->getName()]; + assert(!Val.empty() && + "Variable referenced but not defined and not caught earlier!"); + if (Val[0] == 'T' && Val[1] == 'm' && Val[2] == 'p') { + // Already selected this operand, just return the tmpval. + return std::make_pair(1, atoi(Val.c_str()+3)); + } + + const ComplexPattern *CP; + unsigned ResNo = TmpNo++; + unsigned NumRes = 1; + if (!N->isLeaf() && N->getOperator()->getName() == "imm") { + switch (N->getType()) { + default: assert(0 && "Unknown type for constant node!"); + case MVT::i1: OS << " bool Tmp"; break; + case MVT::i8: OS << " unsigned char Tmp"; break; + case MVT::i16: OS << " unsigned short Tmp"; break; + case MVT::i32: OS << " unsigned Tmp"; break; + case MVT::i64: OS << " uint64_t Tmp"; break; + } + OS << ResNo << "C = cast(" << Val << ")->getValue();\n"; + OS << " SDOperand Tmp" << ResNo << " = CurDAG->getTargetConstant(Tmp" + << ResNo << "C, MVT::" << getEnumName(N->getType()) << ");\n"; + } else if (!N->isLeaf() && N->getOperator()->getName() == "tglobaladdr") { + OS << " SDOperand Tmp" << ResNo << " = " << Val << ";\n"; + } else if (!N->isLeaf() && N->getOperator()->getName() == "tconstpool") { + OS << " SDOperand Tmp" << ResNo << " = " << Val << ";\n"; + } else if (N->isLeaf() && (CP = NodeGetComplexPattern(N, ISE))) { + std::string Fn = CP->getSelectFunc(); + NumRes = CP->getNumOperands(); + OS << " SDOperand "; + for (unsigned i = 0; i < NumRes; i++) { + if (i != 0) OS << ", "; + OS << "Tmp" << i + ResNo; + } + OS << ";\n"; + OS << " if (!" << Fn << "(" << Val; + for (unsigned i = 0; i < NumRes; i++) + OS << ", Tmp" << i + ResNo; + OS << ")) goto P" << PatternNo << "Fail;\n"; + TmpNo = ResNo + NumRes; + } else { + OS << " SDOperand Tmp" << ResNo << " = Select(" << Val << ");\n"; + } + // Add Tmp to VariableMap, so that we don't multiply select this + // value if used multiple times by this pattern result. + Val = "Tmp"+utostr(ResNo); + return std::make_pair(NumRes, ResNo); + } - if (N->isLeaf()) { - // If this is an explicit register reference, handle it. - if (DefInit *DI = dynamic_cast(N->getLeafValue())) { - unsigned ResNo = Ctr++; - if (DI->getDef()->isSubClassOf("Register")) { - OS << " SDOperand Tmp" << ResNo << " = CurDAG->getRegister(" - << getQualifiedName(DI->getDef()) << ", MVT::" + if (N->isLeaf()) { + // If this is an explicit register reference, handle it. + if (DefInit *DI = dynamic_cast(N->getLeafValue())) { + unsigned ResNo = TmpNo++; + if (DI->getDef()->isSubClassOf("Register")) { + OS << " SDOperand Tmp" << ResNo << " = CurDAG->getRegister(" + << ISE.getQualifiedName(DI->getDef()) << ", MVT::" + << getEnumName(N->getType()) + << ");\n"; + return std::make_pair(1, ResNo); + } + } else if (IntInit *II = dynamic_cast(N->getLeafValue())) { + unsigned ResNo = TmpNo++; + OS << " SDOperand Tmp" << ResNo << " = CurDAG->getTargetConstant(" + << II->getValue() << ", MVT::" << getEnumName(N->getType()) << ");\n"; - return ResNo; + return std::make_pair(1, ResNo); } - } else if (IntInit *II = dynamic_cast(N->getLeafValue())) { - unsigned ResNo = Ctr++; - OS << " SDOperand Tmp" << ResNo << " = CurDAG->getTargetConstant(" - << II->getValue() << ", MVT::" - << getEnumName(N->getType()) - << ");\n"; - return ResNo; - } - N->dump(); - assert(0 && "Unknown leaf type!"); - return ~0U; - } - - Record *Op = N->getOperator(); - if (Op->isSubClassOf("Instruction")) { - bool HasCtrlDep = Op->getValueAsBit("hasCtrlDep"); - - // Emit all of the operands. - std::vector Ops; - for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) - Ops.push_back(CodeGenPatternResult(N->getChild(i), Ctr, - VariableMap, OS, HasChain, InFlag)); + N->dump(); + assert(0 && "Unknown leaf type!"); + return std::make_pair(1, ~0U); + } - CodeGenInstruction &II = Target.getInstruction(Op->getName()); - unsigned ResNo = Ctr++; + Record *Op = N->getOperator(); + if (Op->isSubClassOf("Instruction")) { + const DAGInstruction &Inst = ISE.getInstruction(Op); + unsigned NumImpResults = Inst.getNumImpResults(); + unsigned NumImpOperands = Inst.getNumImpOperands(); + bool InFlag = NumImpOperands > 0; + bool OutFlag = NumImpResults > 0; + bool IsCopyFromReg = false; + + if (InFlag || OutFlag) + OS << " SDOperand InFlag = SDOperand(0,0);\n"; + + // Determine operand emission order. Complex pattern first. + std::vector > EmitOrder; + std::vector >::iterator OI; + for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { + TreePatternNode *Child = N->getChild(i); + if (i == 0) { + EmitOrder.push_back(std::make_pair(i, Child)); + OI = EmitOrder.begin(); + } else if (NodeIsComplexPattern(Child)) { + OI = EmitOrder.insert(OI, std::make_pair(i, Child)); + } else { + EmitOrder.push_back(std::make_pair(i, Child)); + } + } - const DAGInstruction &Inst = getInstruction(Op); - unsigned NumResults = Inst.getNumResults(); - - if (!isRoot) { - OS << " SDOperand Tmp" << ResNo << " = CurDAG->getTargetNode(" - << II.Namespace << "::" << II.TheDef->getName() << ", MVT::" - << getEnumName(N->getType()); - unsigned LastOp = 0; - for (unsigned i = 0, e = Ops.size(); i != e; ++i) { - LastOp = Ops[i]; - OS << ", Tmp" << LastOp; + // Emit all of the operands. + std::vector > NumTemps(EmitOrder.size()); + for (unsigned i = 0, e = EmitOrder.size(); i != e; ++i) { + unsigned OpOrder = EmitOrder[i].first; + TreePatternNode *Child = EmitOrder[i].second; + std::pair NumTemp = EmitResultCode(Child); + NumTemps[OpOrder] = NumTemp; } - OS << ");\n"; - if (HasCtrlDep) { - // Must have at least one result - OS << " Chain = Tmp" << LastOp << ".getValue(" - << NumResults << ");\n"; + + // List all the operands in the right order. + std::vector Ops; + for (unsigned i = 0, e = NumTemps.size(); i != e; i++) { + for (unsigned j = 0; j < NumTemps[i].first; j++) + Ops.push_back(NumTemps[i].second + j); } - } else if (HasCtrlDep) { - if (NumResults > 0) - OS << " SDOperand Result = "; - else - OS << " Chain = CodeGenMap[N] = "; - OS << "CurDAG->getTargetNode(" - << II.Namespace << "::" << II.TheDef->getName(); - if (NumResults > 0) - OS << ", MVT::" << getEnumName(N->getType()); // TODO: multiple results? - OS << ", MVT::Other"; - for (unsigned i = 0, e = Ops.size(); i != e; ++i) - OS << ", Tmp" << Ops[i]; - OS << ", Chain"; + + const CodeGenTarget &CGT = ISE.getTargetInfo(); + CodeGenInstruction &II = CGT.getInstruction(Op->getName()); + + // Emit all the chain and CopyToReg stuff. + if (II.hasCtrlDep) + OS << " Chain = Select(Chain);\n"; if (InFlag) - OS << ", InFlag"; - OS << ");\n"; - if (NumResults > 0) { - OS << " CodeGenMap[N.getValue(0)] = Result;\n"; - OS << " CodeGenMap[N.getValue(" << NumResults - << ")] = Result.getValue(" << NumResults << ");\n"; - OS << " Chain = CodeGenMap[N].getValue(" << NumResults << ");\n"; + EmitCopyToRegs(Pattern, "N", II.hasCtrlDep); + + unsigned NumResults = Inst.getNumResults(); + unsigned ResNo = TmpNo++; + if (!isRoot) { + OS << " SDOperand Tmp" << ResNo << " = CurDAG->getTargetNode(" + << II.Namespace << "::" << II.TheDef->getName(); + if (N->getType() != MVT::isVoid) + OS << ", MVT::" << getEnumName(N->getType()); + if (OutFlag) + OS << ", MVT::Flag"; + + unsigned LastOp = 0; + for (unsigned i = 0, e = Ops.size(); i != e; ++i) { + LastOp = Ops[i]; + OS << ", Tmp" << LastOp; + } + OS << ");\n"; + if (II.hasCtrlDep) { + // Must have at least one result + OS << " Chain = Tmp" << LastOp << ".getValue(" + << NumResults << ");\n"; + } + } else if (II.hasCtrlDep || OutFlag) { + OS << " SDOperand Result = CurDAG->getTargetNode(" + << II.Namespace << "::" << II.TheDef->getName(); + + // Output order: results, chain, flags + // Result types. + if (NumResults > 0) { + // TODO: multiple results? + if (N->getType() != MVT::isVoid) + OS << ", MVT::" << getEnumName(N->getType()); + } + if (II.hasCtrlDep) + OS << ", MVT::Other"; + if (OutFlag) + OS << ", MVT::Flag"; + + // Inputs. + for (unsigned i = 0, e = Ops.size(); i != e; ++i) + OS << ", Tmp" << Ops[i]; + if (II.hasCtrlDep) OS << ", Chain"; + if (InFlag) OS << ", InFlag"; + OS << ");\n"; + + unsigned ValNo = 0; + for (unsigned i = 0; i < NumResults; i++) { + OS << " CodeGenMap[N.getValue(" << ValNo << ")] = Result" + << ".getValue(" << ValNo << ");\n"; + ValNo++; + } + + if (II.hasCtrlDep) { + OS << " Chain = Result.getValue(" << ValNo << ");\n"; + if (OutFlag) + OS << " InFlag = Result.getValue(" << ValNo+1 << ");\n"; + } else if (OutFlag) + OS << " InFlag = Result.getValue(" << ValNo << ");\n"; + + if (OutFlag) + IsCopyFromReg = EmitCopyFromRegs(N, II.hasCtrlDep); + if (IsCopyFromReg) + OS << " CodeGenMap[N.getValue(" << ValNo++ << ")] = Result;\n"; + + if (OutFlag) + OS << " CodeGenMap[N.getValue(" << ValNo++ << ")] = InFlag;\n"; + + if (IsCopyFromReg || II.hasCtrlDep) { + OS << " "; + if (IsCopyFromReg || NodeHasChain(Pattern, ISE)) + OS << "CodeGenMap[N.getValue(" << ValNo << ")] = "; + for (unsigned j = 0, e = FoldedChains.size(); j < e; j++) + OS << "CodeGenMap[" << FoldedChains[j].first << ".getValue(" + << FoldedChains[j].second << ")] = "; + OS << "Chain;\n"; + } + + // FIXME: this only works because (for now) an instruction can either + // produce a single result or a single flag. + if (II.hasCtrlDep && OutFlag) { + if (IsCopyFromReg) + OS << " return (N.ResNo == 0) ? Result : " + << "((N.ResNo == 2) ? Chain : InFlag);" + << " // Chain comes before flag.\n"; + else + OS << " return (N.ResNo) ? Chain : InFlag;" + << " // Chain comes before flag.\n"; + } else { + OS << " return Result.getValue(N.ResNo);\n"; + } + } else { + // If this instruction is the root, and if there is only one use of it, + // use SelectNodeTo instead of getTargetNode to avoid an allocation. + OS << " if (N.Val->hasOneUse()) {\n"; + OS << " return CurDAG->SelectNodeTo(N.Val, " + << II.Namespace << "::" << II.TheDef->getName(); + if (N->getType() != MVT::isVoid) + OS << ", MVT::" << getEnumName(N->getType()); + if (OutFlag) + OS << ", MVT::Flag"; + for (unsigned i = 0, e = Ops.size(); i != e; ++i) + OS << ", Tmp" << Ops[i]; + if (InFlag) + OS << ", InFlag"; + OS << ");\n"; + OS << " } else {\n"; + OS << " return CodeGenMap[N] = CurDAG->getTargetNode(" + << II.Namespace << "::" << II.TheDef->getName(); + if (N->getType() != MVT::isVoid) + OS << ", MVT::" << getEnumName(N->getType()); + if (OutFlag) + OS << ", MVT::Flag"; + for (unsigned i = 0, e = Ops.size(); i != e; ++i) + OS << ", Tmp" << Ops[i]; + if (InFlag) + OS << ", InFlag"; + OS << ");\n"; + OS << " }\n"; } - if (NumResults == 0) - OS << " return Chain;\n"; - else - OS << " return (N.ResNo) ? Chain : CodeGenMap[N];\n"; + + return std::make_pair(1, ResNo); + } else if (Op->isSubClassOf("SDNodeXForm")) { + assert(N->getNumChildren() == 1 && "node xform should have one child!"); + unsigned OpVal = EmitResultCode(N->getChild(0)).second; + unsigned ResNo = TmpNo++; + OS << " SDOperand Tmp" << ResNo << " = Transform_" << Op->getName() + << "(Tmp" << OpVal << ".Val);\n"; + if (isRoot) { + OS << " CodeGenMap[N] = Tmp" << ResNo << ";\n"; + OS << " return Tmp" << ResNo << ";\n"; + } + return std::make_pair(1, ResNo); } else { - // If this instruction is the root, and if there is only one use of it, - // use SelectNodeTo instead of getTargetNode to avoid an allocation. - OS << " if (N.Val->hasOneUse()) {\n"; - OS << " return CurDAG->SelectNodeTo(N.Val, " - << II.Namespace << "::" << II.TheDef->getName() << ", MVT::" - << getEnumName(N->getType()); - for (unsigned i = 0, e = Ops.size(); i != e; ++i) - OS << ", Tmp" << Ops[i]; - if (InFlag) - OS << ", InFlag"; - OS << ");\n"; - OS << " } else {\n"; - OS << " return CodeGenMap[N] = CurDAG->getTargetNode(" - << II.Namespace << "::" << II.TheDef->getName() << ", MVT::" - << getEnumName(N->getType()); - for (unsigned i = 0, e = Ops.size(); i != e; ++i) - OS << ", Tmp" << Ops[i]; - if (InFlag) - OS << ", InFlag"; - OS << ");\n"; - OS << " }\n"; - } - return ResNo; - } else if (Op->isSubClassOf("SDNodeXForm")) { - assert(N->getNumChildren() == 1 && "node xform should have one child!"); - unsigned OpVal = CodeGenPatternResult(N->getChild(0), Ctr, - VariableMap, OS, HasChain, InFlag); - - unsigned ResNo = Ctr++; - OS << " SDOperand Tmp" << ResNo << " = Transform_" << Op->getName() - << "(Tmp" << OpVal << ".Val);\n"; - if (isRoot) { - OS << " CodeGenMap[N] = Tmp" << ResNo << ";\n"; - OS << " return Tmp" << ResNo << ";\n"; + N->dump(); + assert(0 && "Unknown node in result pattern!"); + return std::make_pair(1, ~0U); } - return ResNo; - } else { - N->dump(); - assert(0 && "Unknown node in result pattern!"); - return ~0U; } -} -/// RemoveAllTypes - A quick recursive walk over a pattern which removes all -/// type information from it. -static void RemoveAllTypes(TreePatternNode *N) { - N->setType(MVT::isUnknown); - if (!N->isLeaf()) - for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) - RemoveAllTypes(N->getChild(i)); -} - -/// InsertOneTypeCheck - Insert a type-check for an unresolved type in 'Pat' and -/// add it to the tree. 'Pat' and 'Other' are isomorphic trees except that -/// 'Pat' may be missing types. If we find an unresolved type to add a check -/// for, this returns true otherwise false if Pat has all types. -static bool InsertOneTypeCheck(TreePatternNode *Pat, TreePatternNode *Other, - DAGISelEmitter &ISE, - const std::string &Prefix, unsigned PatternNo, - std::ostream &OS) { - // Did we find one? - if (!Pat->hasTypeSet()) { - // Move a type over from 'other' to 'pat'. - Pat->setType(Other->getType()); - OS << " if (" << Prefix << ".getValueType() != MVT::" - << getName(Pat->getType()) << ") goto P" << PatternNo << "Fail;\n"; - return true; - } else if (Pat->isLeaf()) { + /// InsertOneTypeCheck - Insert a type-check for an unresolved type in 'Pat' and + /// add it to the tree. 'Pat' and 'Other' are isomorphic trees except that + /// 'Pat' may be missing types. If we find an unresolved type to add a check + /// for, this returns true otherwise false if Pat has all types. + bool InsertOneTypeCheck(TreePatternNode *Pat, TreePatternNode *Other, + const std::string &Prefix) { + // Did we find one? + if (!Pat->hasTypeSet()) { + // Move a type over from 'other' to 'pat'. + Pat->setType(Other->getType()); + OS << " if (" << Prefix << ".Val->getValueType(0) != MVT::" + << getName(Pat->getType()) << ") goto P" << PatternNo << "Fail;\n"; + return true; + } + + unsigned OpNo = (unsigned) NodeHasChain(Pat, ISE); + for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i, ++OpNo) + if (InsertOneTypeCheck(Pat->getChild(i), Other->getChild(i), + Prefix + utostr(OpNo))) + return true; return false; } - - unsigned OpNo = (unsigned) nodeHasChain(Pat, ISE); - for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i, ++OpNo) - if (InsertOneTypeCheck(Pat->getChild(i), Other->getChild(i), - ISE, Prefix + utostr(OpNo), PatternNo, OS)) - return true; - return false; -} -Record *DAGISelEmitter::getSDNodeNamed(const std::string &Name) const { - Record *N = Records.getDef(Name); - assert(N && N->isSubClassOf("SDNode") && "Bad argument"); - return N; -} +private: + /// EmitCopyToRegs - Emit the flag operands for the DAG that is + /// being built. + void EmitCopyToRegs(TreePatternNode *N, const std::string &RootName, + bool HasCtrlDep) { + const CodeGenTarget &T = ISE.getTargetInfo(); + unsigned OpNo = (unsigned) NodeHasChain(N, ISE); + for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) { + TreePatternNode *Child = N->getChild(i); + if (!Child->isLeaf()) { + EmitCopyToRegs(Child, RootName + utostr(OpNo), HasCtrlDep); + } else { + if (DefInit *DI = dynamic_cast(Child->getLeafValue())) { + Record *RR = DI->getDef(); + if (RR->isSubClassOf("Register")) { + MVT::ValueType RVT = getRegisterValueType(RR, T); + if (RVT == MVT::Flag) { + OS << " InFlag = Select(" << RootName << OpNo << ");\n"; + } else if (HasCtrlDep) { + OS << " SDOperand " << RootName << "CR" << i << ";\n"; + OS << " " << RootName << "CR" << i + << " = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(" + << ISE.getQualifiedName(RR) << ", MVT::" + << getEnumName(RVT) << ")" + << ", Select(" << RootName << OpNo << "), InFlag);\n"; + OS << " Chain = " << RootName << "CR" << i + << ".getValue(0);\n"; + OS << " InFlag = " << RootName << "CR" << i + << ".getValue(1);\n"; + } else { + OS << " InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode()" + << ", CurDAG->getRegister(" << ISE.getQualifiedName(RR) + << ", MVT::" << getEnumName(RVT) << ")" + << ", Select(" << RootName << OpNo + << "), InFlag).getValue(1);\n"; + } + } + } + } + } + } + + /// EmitCopyFromRegs - Emit code to copy result to physical registers + /// as specified by the instruction. + bool EmitCopyFromRegs(TreePatternNode *N, bool HasCtrlDep) { + bool RetVal = false; + Record *Op = N->getOperator(); + if (Op->isSubClassOf("Instruction")) { + const DAGInstruction &Inst = ISE.getInstruction(Op); + const CodeGenTarget &CGT = ISE.getTargetInfo(); + CodeGenInstruction &II = CGT.getInstruction(Op->getName()); + unsigned NumImpResults = Inst.getNumImpResults(); + for (unsigned i = 0; i < NumImpResults; i++) { + Record *RR = Inst.getImpResult(i); + if (RR->isSubClassOf("Register")) { + MVT::ValueType RVT = getRegisterValueType(RR, CGT); + if (RVT != MVT::Flag) { + if (HasCtrlDep) { + OS << " Result = CurDAG->getCopyFromReg(Chain, " + << ISE.getQualifiedName(RR) + << ", MVT::" << getEnumName(RVT) << ", InFlag);\n"; + OS << " Chain = Result.getValue(1);\n"; + OS << " InFlag = Result.getValue(2);\n"; + } else { + OS << " SDOperand Chain;\n"; + OS << " Result = CurDAG->getCopyFromReg(" + << "CurDAG->getEntryNode(), ISE.getQualifiedName(RR)" + << ", MVT::" << getEnumName(RVT) << ", InFlag);\n"; + OS << " Chain = Result.getValue(1);\n"; + OS << " InFlag = Result.getValue(2);\n"; + } + RetVal = true; + } + } + } + } + return RetVal; + } +}; /// EmitCodeForPattern - Given a pattern to match, emit code to the specified /// stream to match the pattern, and generate the code for the match if it @@ -2015,17 +2309,22 @@ void DAGISelEmitter::EmitCodeForPattern(PatternToMatch &Pattern, static unsigned PatternCount = 0; unsigned PatternNo = PatternCount++; OS << " { // Pattern #" << PatternNo << ": "; - Pattern.first->print(OS); + Pattern.getSrcPattern()->print(OS); OS << "\n // Emits: "; - Pattern.second->print(OS); + Pattern.getDstPattern()->print(OS); OS << "\n"; - OS << " // Pattern complexity = " << getPatternSize(Pattern.first) - << " cost = " << getResultPatternCost(Pattern.second) << "\n"; + OS << " // Pattern complexity = " + << getPatternSize(Pattern.getSrcPattern(), *this) + << " cost = " + << getResultPatternCost(Pattern.getDstPattern()) << "\n"; + + PatternCodeEmitter Emitter(*this, Pattern.getPredicates(), + Pattern.getSrcPattern(), Pattern.getDstPattern(), + PatternNo, OS); // Emit the matcher, capturing named arguments in VariableMap. - std::map VariableMap; - EmitMatchForPattern(Pattern.first, "N", VariableMap, PatternNo, OS); - + Emitter.EmitMatchCode(Pattern.getSrcPattern(), "N", true /*the root*/); + // TP - Get *SOME* tree pattern, we don't care which. TreePattern &TP = *PatternFragments.begin()->second; @@ -2041,7 +2340,7 @@ void DAGISelEmitter::EmitCodeForPattern(PatternToMatch &Pattern, // apply the type to the tree, then rerun type inference. Iterate until all // types are resolved. // - TreePatternNode *Pat = Pattern.first->clone(); + TreePatternNode *Pat = Pattern.getSrcPattern()->clone(); RemoveAllTypes(Pat); do { @@ -2059,17 +2358,10 @@ void DAGISelEmitter::EmitCodeForPattern(PatternToMatch &Pattern, // Insert a check for an unresolved type and add it to the tree. If we find // an unresolved type to add a check for, this returns true and we iterate, // otherwise we are done. - } while (InsertOneTypeCheck(Pat, Pattern.first, *this, "N", PatternNo, OS)); + } while (Emitter.InsertOneTypeCheck(Pat, Pattern.getSrcPattern(), "N")); - bool HasChain = false; - EmitLeadChainForPattern(Pattern.second, "N", OS, HasChain); + Emitter.EmitResultCode(Pattern.getDstPattern(), true /*the root*/); - bool InFlag = false; - EmitCopyToRegsForPattern(Pattern.first, "N", OS, HasChain, InFlag); - - unsigned TmpNo = 0; - CodeGenPatternResult(Pattern.second, - TmpNo, VariableMap, OS, HasChain, InFlag, true /*the root*/); delete Pat; OS << " }\n P" << PatternNo << "Fail:\n"; @@ -2100,13 +2392,12 @@ void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) { << " N.getOpcode() < (ISD::BUILTIN_OP_END+" << InstNS << "INSTRUCTION_LIST_END))\n" << " return N; // Already selected.\n\n" - << " if (!N.Val->hasOneUse()) {\n" - << " std::map::iterator CGMI = CodeGenMap.find(N);\n" - << " if (CGMI != CodeGenMap.end()) return CGMI->second;\n" - << " }\n" + << " std::map::iterator CGMI = CodeGenMap.find(N);\n" + << " if (CGMI != CodeGenMap.end()) return CGMI->second;\n" << " switch (N.getOpcode()) {\n" << " default: break;\n" << " case ISD::EntryToken: // These leaves remain the same.\n" + << " case ISD::BasicBlock:\n" << " return N;\n" << " case ISD::AssertSext:\n" << " case ISD::AssertZext: {\n" @@ -2129,41 +2420,76 @@ void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) { << " }\n" << " case ISD::CopyFromReg: {\n" << " SDOperand Chain = Select(N.getOperand(0));\n" - << " if (Chain == N.getOperand(0)) return N; // No change\n" - << " SDOperand New = CurDAG->getCopyFromReg(Chain,\n" - << " cast(N.getOperand(1))->getReg(),\n" - << " N.Val->getValueType(0));\n" - << " return New.getValue(N.ResNo);\n" + << " unsigned Reg = cast(N.getOperand(1))->getReg();\n" + << " MVT::ValueType VT = N.Val->getValueType(0);\n" + << " if (N.Val->getNumValues() == 2) {\n" + << " if (Chain == N.getOperand(0)) return N; // No change\n" + << " SDOperand New = CurDAG->getCopyFromReg(Chain, Reg, VT);\n" + << " CodeGenMap[N.getValue(0)] = New;\n" + << " CodeGenMap[N.getValue(1)] = New.getValue(1);\n" + << " return New.getValue(N.ResNo);\n" + << " } else {\n" + << " SDOperand Flag;\n" + << " if (N.getNumOperands() == 3) Flag = Select(N.getOperand(2));\n" + << " if (Chain == N.getOperand(0) &&\n" + << " (N.getNumOperands() == 2 || Flag == N.getOperand(2)))\n" + << " return N; // No change\n" + << " SDOperand New = CurDAG->getCopyFromReg(Chain, Reg, VT, Flag);\n" + << " CodeGenMap[N.getValue(0)] = New;\n" + << " CodeGenMap[N.getValue(1)] = New.getValue(1);\n" + << " CodeGenMap[N.getValue(2)] = New.getValue(2);\n" + << " return New.getValue(N.ResNo);\n" + << " }\n" << " }\n" << " case ISD::CopyToReg: {\n" << " SDOperand Chain = Select(N.getOperand(0));\n" - << " SDOperand Reg = N.getOperand(1);\n" + << " unsigned Reg = cast(N.getOperand(1))->getReg();\n" << " SDOperand Val = Select(N.getOperand(2));\n" - << " return CodeGenMap[N] = \n" - << " CurDAG->getNode(ISD::CopyToReg, MVT::Other,\n" - << " Chain, Reg, Val);\n" + << " SDOperand Result = N;\n" + << " if (N.Val->getNumValues() == 1) {\n" + << " if (Chain != N.getOperand(0) || Val != N.getOperand(2))\n" + << " Result = CurDAG->getCopyToReg(Chain, Reg, Val);\n" + << " return CodeGenMap[N] = Result;\n" + << " } else {\n" + << " SDOperand Flag;\n" + << " if (N.getNumOperands() == 4) Flag = Select(N.getOperand(3));\n" + << " if (Chain != N.getOperand(0) || Val != N.getOperand(2) ||\n" + << " (N.getNumOperands() == 4 && Flag != N.getOperand(3)))\n" + << " Result = CurDAG->getCopyToReg(Chain, Reg, Val, Flag);\n" + << " CodeGenMap[N.getValue(0)] = Result;\n" + << " CodeGenMap[N.getValue(1)] = Result.getValue(1);\n" + << " return Result.getValue(N.ResNo);\n" + << " }\n" << " }\n"; // Group the patterns by their top-level opcodes. std::map, CompareByRecordName> PatternsByOpcode; - for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) - if (!PatternsToMatch[i].first->isLeaf()) { - PatternsByOpcode[PatternsToMatch[i].first->getOperator()] - .push_back(&PatternsToMatch[i]); + for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) { + TreePatternNode *Node = PatternsToMatch[i].getSrcPattern(); + if (!Node->isLeaf()) { + PatternsByOpcode[Node->getOperator()].push_back(&PatternsToMatch[i]); } else { + const ComplexPattern *CP; if (IntInit *II = - dynamic_cast(PatternsToMatch[i].first->getLeafValue())) { + dynamic_cast(Node->getLeafValue())) { PatternsByOpcode[getSDNodeNamed("imm")].push_back(&PatternsToMatch[i]); + } else if ((CP = NodeGetComplexPattern(Node, *this))) { + std::vector OpNodes = CP->getRootNodes(); + for (unsigned j = 0, e = OpNodes.size(); j != e; j++) { + PatternsByOpcode[OpNodes[j]].insert(PatternsByOpcode[OpNodes[j]].begin(), + &PatternsToMatch[i]); + } } else { std::cerr << "Unrecognized opcode '"; - PatternsToMatch[i].first->dump(); + Node->dump(); std::cerr << "' on tree pattern '"; - std::cerr << PatternsToMatch[i].second->getOperator()->getName(); + std::cerr << PatternsToMatch[i].getDstPattern()->getOperator()->getName(); std::cerr << "'!\n"; exit(1); } } + } // Loop over all of the case statements. for (std::map, @@ -2178,7 +2504,7 @@ void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) { // the matches in order of minimal cost. Sort the patterns so the least // cost one is at the start. std::stable_sort(Patterns.begin(), Patterns.end(), - PatternSortingPredicate()); + PatternSortingPredicate(*this)); for (unsigned i = 0, e = Patterns.size(); i != e; ++i) EmitCodeForPattern(*Patterns[i], OS); @@ -2208,6 +2534,7 @@ void DAGISelEmitter::run(std::ostream &OS) { ParseNodeInfo(); ParseNodeTransforms(OS); + ParseComplexPatterns(); ParsePatternFragments(OS); ParseInstructions(); ParsePatterns(); @@ -2219,8 +2546,8 @@ void DAGISelEmitter::run(std::ostream &OS) { DEBUG(std::cerr << "\n\nALL PATTERNS TO MATCH:\n\n"; for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) { - std::cerr << "PATTERN: "; PatternsToMatch[i].first->dump(); - std::cerr << "\nRESULT: ";PatternsToMatch[i].second->dump(); + std::cerr << "PATTERN: "; PatternsToMatch[i].getSrcPattern()->dump(); + std::cerr << "\nRESULT: ";PatternsToMatch[i].getDstPattern()->dump(); std::cerr << "\n"; });