X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=utils%2FTableGen%2FDAGISelEmitter.cpp;h=39480c966404a92f0e5006fa5ba3baf97e756c03;hb=9ec4849ff6cd771f53a1340aa6383702b7a6bb98;hp=7983ad31375c4d439c32a233daaca629bb18f68d;hpb=dc7a66a0819e65fa5164c9bdc35e02f47b878b47;p=oota-llvm.git diff --git a/utils/TableGen/DAGISelEmitter.cpp b/utils/TableGen/DAGISelEmitter.cpp index 7983ad31375..39480c96640 100644 --- a/utils/TableGen/DAGISelEmitter.cpp +++ b/utils/TableGen/DAGISelEmitter.cpp @@ -15,6 +15,7 @@ #include "Record.h" #include "llvm/ADT/StringExtras.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/MathExtras.h" #include #include using namespace llvm; @@ -768,7 +769,6 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { if (OperandNode->isSubClassOf("RegisterClass")) { const CodeGenRegisterClass &RC = ISE.getTargetInfo().getRegisterClass(OperandNode); - //VT = RC.getValueTypeNum(0); MadeChange |=getChild(i)->UpdateNodeType(ConvertVTs(RC.getValueTypes()), TP); } else if (OperandNode->isSubClassOf("Operand")) { @@ -801,6 +801,17 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { } } +/// OnlyOnRHSOfCommutative - Return true if this value is only allowed on the +/// RHS of a commutative operation, not the on LHS. +static bool OnlyOnRHSOfCommutative(TreePatternNode *N) { + if (!N->isLeaf() && N->getOperator()->getName() == "imm") + return true; + if (N->isLeaf() && dynamic_cast(N->getLeafValue())) + return true; + return false; +} + + /// canPatternMatch - If it is impossible for this pattern to match on this /// target, fill in Reason and return false. Otherwise, return true. This is /// used as a santity check for .td files (to prevent people from writing stuff @@ -823,15 +834,16 @@ bool TreePatternNode::canPatternMatch(std::string &Reason, DAGISelEmitter &ISE){ // If this node is a commutative operator, check that the LHS isn't an // immediate. const SDNodeInfo &NodeInfo = ISE.getSDNodeInfo(getOperator()); - if (NodeInfo.hasProperty(SDNodeInfo::SDNPCommutative)) { + if (NodeInfo.hasProperty(SDNPCommutative)) { // Scan all of the operands of the node and make sure that only the last one - // is a constant node. - for (unsigned i = 0, e = getNumChildren()-1; i != e; ++i) - if (!getChild(i)->isLeaf() && - getChild(i)->getOperator()->getName() == "imm") { - Reason = "Immediate value must be on the RHS of commutative operators!"; - return false; - } + // is a constant node, unless the RHS also is. + if (!OnlyOnRHSOfCommutative(getChild(getNumChildren()-1))) { + for (unsigned i = 0, e = getNumChildren()-1; i != e; ++i) + if (OnlyOnRHSOfCommutative(getChild(i))) { + Reason="Immediate value must be on the RHS of commutative operators!"; + return false; + } + } } return true; @@ -1156,15 +1168,19 @@ void DAGISelEmitter::ParsePatternFragments(std::ostream &OS) { // keep track of the fact that this fragment uses it. std::string Code = Fragments[i]->getValueAsCode("Predicate"); if (!Code.empty()) { - assert(!P->getOnlyTree()->isLeaf() && "Can't be a leaf!"); - std::string ClassName = - getSDNodeInfo(P->getOnlyTree()->getOperator()).getSDClassName(); - const char *C2 = ClassName == "SDNode" ? "N" : "inN"; + if (P->getOnlyTree()->isLeaf()) + OS << "inline bool Predicate_" << Fragments[i]->getName() + << "(SDNode *N) {\n"; + else { + std::string ClassName = + getSDNodeInfo(P->getOnlyTree()->getOperator()).getSDClassName(); + const char *C2 = ClassName == "SDNode" ? "N" : "inN"; - OS << "inline bool Predicate_" << Fragments[i]->getName() - << "(SDNode *" << C2 << ") {\n"; - if (ClassName != "SDNode") - OS << " " << ClassName << " *N = cast<" << ClassName << ">(inN);\n"; + OS << "inline bool Predicate_" << Fragments[i]->getName() + << "(SDNode *" << C2 << ") {\n"; + if (ClassName != "SDNode") + OS << " " << ClassName << " *N = cast<" << ClassName << ">(inN);\n"; + } OS << Code << "\n}\n"; P->getOnlyTree()->setPredicateFn("Predicate_"+Fragments[i]->getName()); } @@ -1584,8 +1600,8 @@ void DAGISelEmitter::ParsePatterns() { // can never do anything with this pattern: report it to the user. InferredAllPatternTypes = Pattern->InferAllTypes(); - // Infer as many types as possible. If we cannot infer all of them, we can - // never do anything with this pattern: report it to the user. + // Infer as many types as possible. If we cannot infer all of them, we + // can never do anything with this pattern: report it to the user. InferredAllResultTypes = Result->InferAllTypes(); // Apply the type of the result to the source pattern. This helps us @@ -1766,7 +1782,7 @@ static void GenerateVariantsOf(TreePatternNode *N, const SDNodeInfo &NodeInfo = ISE.getSDNodeInfo(N->getOperator()); // If this node is associative, reassociate. - if (NodeInfo.hasProperty(SDNodeInfo::SDNPAssociative)) { + if (NodeInfo.hasProperty(SDNPAssociative)) { // Reassociate by pulling together all of the linked operators std::vector MaximalChildren; GatherChildrenOfAssociativeOpcode(N, MaximalChildren); @@ -1827,11 +1843,24 @@ static void GenerateVariantsOf(TreePatternNode *N, CombineChildVariants(N, ChildVariants, OutVariants, ISE); // If this node is commutative, consider the commuted order. - if (NodeInfo.hasProperty(SDNodeInfo::SDNPCommutative)) { + if (NodeInfo.hasProperty(SDNPCommutative)) { assert(N->getNumChildren()==2 &&"Commutative but doesn't have 2 children!"); + // Don't count children which are actually register references. + unsigned NC = 0; + for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { + TreePatternNode *Child = N->getChild(i); + if (Child->isLeaf()) + if (DefInit *DI = dynamic_cast(Child->getLeafValue())) { + Record *RR = DI->getDef(); + if (RR->isSubClassOf("Register")) + continue; + } + NC++; + } // Consider the commuted order. - CombineChildVariants(N, ChildVariants[1], ChildVariants[0], - OutVariants, ISE); + if (NC == 2) + CombineChildVariants(N, ChildVariants[1], ChildVariants[0], + OutVariants, ISE); } } @@ -1896,7 +1925,6 @@ void DAGISelEmitter::GenerateVariants() { } } - // NodeIsComplexPattern - return true if N is a leaf node and a subclass of // ComplexPattern. static bool NodeIsComplexPattern(TreePatternNode *N) @@ -1932,11 +1960,11 @@ static unsigned getPatternSize(TreePatternNode *P, DAGISelEmitter &ISE) { P->getExtTypeNum(0) == MVT::Flag || P->getExtTypeNum(0) == MVT::iPTR) && "Not a valid pattern node to size!"); - unsigned Size = 2; // The node itself. + unsigned Size = 3; // The node itself. // If the root node is a ConstantSDNode, increases its size. // e.g. (set R32:$dst, 0). if (P->isLeaf() && dynamic_cast(P->getLeafValue())) - Size++; + Size += 2; // 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. @@ -1945,7 +1973,7 @@ static unsigned getPatternSize(TreePatternNode *P, DAGISelEmitter &ISE) { // calculate the complexity of all patterns a dag can potentially map to. const ComplexPattern *AM = NodeGetComplexPattern(P, ISE); if (AM) - Size += AM->getNumOperands() * 2; + Size += AM->getNumOperands() * 3; // If this node has some predicate function that must match, it adds to the // complexity of this node. @@ -1959,7 +1987,7 @@ static unsigned getPatternSize(TreePatternNode *P, DAGISelEmitter &ISE) { Size += getPatternSize(Child, ISE); else if (Child->isLeaf()) { if (dynamic_cast(Child->getLeafValue())) - Size += 3; // Matches a ConstantSDNode (+2) and a specific value (+1). + Size += 5; // Matches a ConstantSDNode (+3) and a specific value (+2). else if (NodeIsComplexPattern(Child)) Size += getPatternSize(Child, ISE); else if (!Child->getPredicateFn().empty()) @@ -2060,10 +2088,15 @@ Record *DAGISelEmitter::getSDNodeNamed(const std::string &Name) const { /// NodeHasProperty - return true if TreePatternNode has the specified /// property. -static bool NodeHasProperty(TreePatternNode *N, SDNodeInfo::SDNP Property, +static bool NodeHasProperty(TreePatternNode *N, SDNP Property, DAGISelEmitter &ISE) { - if (N->isLeaf()) return false; + if (N->isLeaf()) { + const ComplexPattern *CP = NodeGetComplexPattern(N, ISE); + if (CP) + return CP->hasProperty(Property); + return false; + } Record *Operator = N->getOperator(); if (!Operator->isSubClassOf("SDNode")) return false; @@ -2071,7 +2104,7 @@ static bool NodeHasProperty(TreePatternNode *N, SDNodeInfo::SDNP Property, return NodeInfo.hasProperty(Property); } -static bool PatternHasProperty(TreePatternNode *N, SDNodeInfo::SDNP Property, +static bool PatternHasProperty(TreePatternNode *N, SDNP Property, DAGISelEmitter &ISE) { if (NodeHasProperty(N, Property, ISE)) @@ -2105,38 +2138,43 @@ private: std::map OperatorMap; // Names of all the folded nodes which produce chains. std::vector > FoldedChains; + // Original input chain(s). + std::vector > OrigChains; std::set Duplicates; - /// GeneratedCode - This is the buffer that we emit code to. The first bool + /// GeneratedCode - This is the buffer that we emit code to. The first int /// indicates whether this is an exit predicate (something that should be - /// tested, and if true, the match fails) [when true] or normal code to emit - /// [when false]. - std::vector > &GeneratedCode; + /// tested, and if true, the match fails) [when 1], or normal code to emit + /// [when 0], or initialization code to emit [when 2]. + std::vector > &GeneratedCode; /// GeneratedDecl - This is the set of all SDOperand declarations needed for /// the set of patterns for each top-level opcode. - std::set > &GeneratedDecl; + std::set &GeneratedDecl; /// TargetOpcodes - The target specific opcodes used by the resulting /// instructions. std::vector &TargetOpcodes; std::vector &TargetVTs; std::string ChainName; - bool DoReplace; unsigned TmpNo; unsigned OpcNo; unsigned VTNo; void emitCheck(const std::string &S) { if (!S.empty()) - GeneratedCode.push_back(std::make_pair(true, S)); + GeneratedCode.push_back(std::make_pair(1, S)); } void emitCode(const std::string &S) { if (!S.empty()) - GeneratedCode.push_back(std::make_pair(false, S)); + GeneratedCode.push_back(std::make_pair(0, S)); + } + void emitInit(const std::string &S) { + if (!S.empty()) + GeneratedCode.push_back(std::make_pair(2, S)); } - void emitDecl(const std::string &S, unsigned T=0) { + void emitDecl(const std::string &S) { assert(!S.empty() && "Invalid declaration"); - GeneratedDecl.insert(std::make_pair(T, S)); + GeneratedDecl.insert(S); } void emitOpcode(const std::string &Opc) { TargetOpcodes.push_back(Opc); @@ -2149,21 +2187,21 @@ private: public: PatternCodeEmitter(DAGISelEmitter &ise, ListInit *preds, TreePatternNode *pattern, TreePatternNode *instr, - std::vector > &gc, - std::set > &gd, + std::vector > &gc, + std::set &gd, std::vector &to, - std::vector &tv, - bool dorep) + std::vector &tv) : ISE(ise), Predicates(preds), Pattern(pattern), Instruction(instr), - GeneratedCode(gc), GeneratedDecl(gd), TargetOpcodes(to), TargetVTs(tv), - DoReplace(dorep), TmpNo(0), OpcNo(0), VTNo(0) {} + GeneratedCode(gc), GeneratedDecl(gd), + TargetOpcodes(to), TargetVTs(tv), + TmpNo(0), OpcNo(0), VTNo(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, TreePatternNode *P, - const std::string &RootName, const std::string &ParentName, - const std::string &ChainSuffix, bool &FoundChain) { + const std::string &RootName, const std::string &ChainSuffix, + bool &FoundChain) { bool isRoot = (P == NULL); // Emit instruction predicates. Each predicate is just a string for now. if (isRoot) { @@ -2178,7 +2216,7 @@ public: assert(0 && "Unknown predicate type!"); } if (!PredicateCheck.empty()) - PredicateCheck += " || "; + PredicateCheck += " && "; PredicateCheck += "(" + Def->getValueAsString("CondString") + ")"; } } @@ -2219,45 +2257,17 @@ public: // Emit code to load the child nodes and match their contents recursively. unsigned OpNo = 0; - bool NodeHasChain = NodeHasProperty (N, SDNodeInfo::SDNPHasChain, ISE); - bool HasChain = PatternHasProperty(N, SDNodeInfo::SDNPHasChain, ISE); - bool HasOutFlag = PatternHasProperty(N, SDNodeInfo::SDNPOutFlag, ISE); + bool NodeHasChain = NodeHasProperty (N, SDNPHasChain, ISE); + bool HasChain = PatternHasProperty(N, SDNPHasChain, ISE); bool EmittedUseCheck = false; - bool EmittedSlctedCheck = false; if (HasChain) { if (NodeHasChain) OpNo = 1; if (!isRoot) { - const SDNodeInfo &CInfo = ISE.getSDNodeInfo(N->getOperator()); // Multiple uses of actual result? emitCheck(RootName + ".hasOneUse()"); EmittedUseCheck = true; - // hasOneUse() check is not strong enough. If the original node has - // already been selected, it may have been replaced with another. - for (unsigned j = 0; j != CInfo.getNumResults(); j++) - emitCheck("!CodeGenMap.count(" + RootName + ".getValue(" + utostr(j) + - "))"); - - EmittedSlctedCheck = true; if (NodeHasChain) { - // FIXME: Don't fold if 1) the parent node writes a flag, 2) the node - // has a chain use. - // This a workaround for this problem: - // - // [ch, r : ld] - // ^ ^ - // | | - // [XX]--/ \- [flag : cmp] - // ^ ^ - // | | - // \---[br flag]- - // - // cmp + br should be considered as a single node as they are flagged - // together. So, if the ld is folded into the cmp, the XX node in the - // graph is now both an operand and a use of the ld/cmp/br node. - if (NodeHasProperty(P, SDNodeInfo::SDNPOutFlag, ISE)) - emitCheck(ParentName + ".Val->isOnlyUse(" + RootName + ".Val)"); - // If the immediate use can somehow reach this node through another // path, then can't fold it either or it will create a cycle. // e.g. In the following diagram, XX can reach ld through YY. If @@ -2271,24 +2281,39 @@ public: // / [YY] // | ^ // [XX]-------| - const SDNodeInfo &PInfo = ISE.getSDNodeInfo(P->getOperator()); - if (PInfo.getNumOperands() > 1 || - PInfo.hasProperty(SDNodeInfo::SDNPHasChain) || - PInfo.hasProperty(SDNodeInfo::SDNPInFlag) || - PInfo.hasProperty(SDNodeInfo::SDNPOptInFlag)) + bool NeedCheck = false; + if (P != Pattern) + NeedCheck = true; + else { + const SDNodeInfo &PInfo = ISE.getSDNodeInfo(P->getOperator()); + NeedCheck = + P->getOperator() == ISE.get_intrinsic_void_sdnode() || + P->getOperator() == ISE.get_intrinsic_w_chain_sdnode() || + P->getOperator() == ISE.get_intrinsic_wo_chain_sdnode() || + PInfo.getNumOperands() > 1 || + PInfo.hasProperty(SDNPHasChain) || + PInfo.hasProperty(SDNPInFlag) || + PInfo.hasProperty(SDNPOptInFlag); + } + + if (NeedCheck) { + std::string ParentName(RootName.begin(), RootName.end()-1); emitCheck("CanBeFoldedBy(" + RootName + ".Val, " + ParentName + - ".Val)"); + ".Val, N.Val)"); + } } } if (NodeHasChain) { - if (FoundChain) - emitCheck("Chain.Val == " + RootName + ".Val"); - else + if (FoundChain) { + emitCheck("(" + ChainName + ".Val == " + RootName + ".Val || " + "IsChainCompatible(" + ChainName + ".Val, " + + RootName + ".Val))"); + OrigChains.push_back(std::make_pair(ChainName, RootName)); + } else FoundChain = true; ChainName = "Chain" + ChainSuffix; - emitDecl(ChainName); - emitCode(ChainName + " = " + RootName + + emitInit("SDOperand " + ChainName + " = " + RootName + ".getOperand(0);"); } } @@ -2299,109 +2324,204 @@ public: // FIXME: If the optional incoming flag does not exist. Then it is ok to // fold it. if (!isRoot && - (PatternHasProperty(N, SDNodeInfo::SDNPInFlag, ISE) || - PatternHasProperty(N, SDNodeInfo::SDNPOptInFlag, ISE) || - PatternHasProperty(N, SDNodeInfo::SDNPOutFlag, ISE))) { - const SDNodeInfo &CInfo = ISE.getSDNodeInfo(N->getOperator()); + (PatternHasProperty(N, SDNPInFlag, ISE) || + PatternHasProperty(N, SDNPOptInFlag, ISE) || + PatternHasProperty(N, SDNPOutFlag, ISE))) { if (!EmittedUseCheck) { // Multiple uses of actual result? emitCheck(RootName + ".hasOneUse()"); } - if (!EmittedSlctedCheck) - // hasOneUse() check is not strong enough. If the original node has - // already been selected, it may have been replaced with another. - for (unsigned j = 0; j < CInfo.getNumResults(); j++) - emitCheck("!CodeGenMap.count(" + RootName + ".getValue(" + utostr(j) + - "))"); } + // If there is a node predicate for this, emit the call. + if (!N->getPredicateFn().empty()) + emitCheck(N->getPredicateFn() + "(" + RootName + ".Val)"); + + + // If this is an 'and R, 1234' where the operation is AND/OR and the RHS is + // a constant without a predicate fn that has more that one bit set, handle + // this as a special case. This is usually for targets that have special + // handling of certain large constants (e.g. alpha with it's 8/16/32-bit + // handling stuff). Using these instructions is often far more efficient + // than materializing the constant. Unfortunately, both the instcombiner + // and the dag combiner can often infer that bits are dead, and thus drop + // them from the mask in the dag. For example, it might turn 'AND X, 255' + // into 'AND X, 254' if it knows the low bit is set. Emit code that checks + // to handle this. + if (!N->isLeaf() && + (N->getOperator()->getName() == "and" || + N->getOperator()->getName() == "or") && + N->getChild(1)->isLeaf() && + N->getChild(1)->getPredicateFn().empty()) { + if (IntInit *II = dynamic_cast(N->getChild(1)->getLeafValue())) { + if (!isPowerOf2_32(II->getValue())) { // Don't bother with single bits. + emitInit("SDOperand " + RootName + "0" + " = " + + RootName + ".getOperand(" + utostr(0) + ");"); + emitInit("SDOperand " + RootName + "1" + " = " + + RootName + ".getOperand(" + utostr(1) + ");"); + + emitCheck("isa(" + RootName + "1)"); + const char *MaskPredicate = N->getOperator()->getName() == "or" + ? "CheckOrMask(" : "CheckAndMask("; + emitCheck(MaskPredicate + RootName + "0, cast(" + + RootName + "1), " + itostr(II->getValue()) + ")"); + + EmitChildMatchCode(N->getChild(0), N, RootName + utostr(0), + ChainSuffix + utostr(0), FoundChain); + return; + } + } + } + for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) { - emitDecl(RootName + utostr(OpNo)); - emitCode(RootName + utostr(OpNo) + " = " + + emitInit("SDOperand " + RootName + utostr(OpNo) + " = " + RootName + ".getOperand(" +utostr(OpNo) + ");"); - TreePatternNode *Child = N->getChild(i); - - if (!Child->isLeaf()) { - // If it's not a leaf, recursively match. - const SDNodeInfo &CInfo = ISE.getSDNodeInfo(Child->getOperator()); - emitCheck(RootName + utostr(OpNo) + ".getOpcode() == " + - CInfo.getEnumName()); - EmitMatchCode(Child, N, RootName + utostr(OpNo), RootName, - ChainSuffix + utostr(OpNo), FoundChain); - if (NodeHasProperty(Child, SDNodeInfo::SDNPHasChain, 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. - emitCheck(VarMapEntry + " == " + RootName + utostr(OpNo)); - Duplicates.insert(RootName + utostr(OpNo)); - continue; - } + + EmitChildMatchCode(N->getChild(i), N, RootName + utostr(OpNo), + ChainSuffix + utostr(OpNo), FoundChain); + } + + // Handle cases when root is a complex pattern. + const ComplexPattern *CP; + if (isRoot && N->isLeaf() && (CP = NodeGetComplexPattern(N, ISE))) { + std::string Fn = CP->getSelectFunc(); + unsigned NumOps = CP->getNumOperands(); + for (unsigned i = 0; i < NumOps; ++i) { + emitDecl("CPTmp" + utostr(i)); + emitCode("SDOperand CPTmp" + utostr(i) + ";"); + } + if (CP->hasProperty(SDNPHasChain)) { + emitDecl("CPInChain"); + emitDecl("Chain" + ChainSuffix); + emitCode("SDOperand CPInChain;"); + emitCode("SDOperand Chain" + ChainSuffix + ";"); + } + + std::string Code = Fn + "(" + RootName; + for (unsigned i = 0; i < NumOps; i++) + Code += ", CPTmp" + utostr(i); + if (CP->hasProperty(SDNPHasChain)) { + ChainName = "Chain" + ChainSuffix; + Code += ", CPInChain, Chain" + ChainSuffix; + } + emitCheck(Code + ")"); + } + } + + void EmitChildMatchCode(TreePatternNode *Child, TreePatternNode *Parent, + const std::string &RootName, + const std::string &ChainSuffix, bool &FoundChain) { + if (!Child->isLeaf()) { + // If it's not a leaf, recursively match. + const SDNodeInfo &CInfo = ISE.getSDNodeInfo(Child->getOperator()); + emitCheck(RootName + ".getOpcode() == " + + CInfo.getEnumName()); + EmitMatchCode(Child, Parent, RootName, ChainSuffix, FoundChain); + if (NodeHasProperty(Child, SDNPHasChain, ISE)) + FoldedChains.push_back(std::make_pair(RootName, 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; + } 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. + emitCheck(VarMapEntry + " == " + RootName); + Duplicates.insert(RootName); + return; } + } - // 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")) { - // Handle register references. - } 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. - emitCheck("cast(" + RootName + utostr(OpNo) + - ")->getVT() == MVT::" + LeafRec->getName()); - } else if (LeafRec->isSubClassOf("CondCode")) { - // Make sure this is the specified cond code. - emitCheck("cast(" + RootName + utostr(OpNo) + - ")->get() == ISD::" + LeafRec->getName()); - } else { -#ifndef NDEBUG - Child->dump(); - std::cerr << " "; -#endif - assert(0 && "Unknown leaf type!"); + // 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")) { + // Handle register references. + } else if (LeafRec->isSubClassOf("ComplexPattern")) { + // Handle complex pattern. + const ComplexPattern *CP = NodeGetComplexPattern(Child, ISE); + std::string Fn = CP->getSelectFunc(); + unsigned NumOps = CP->getNumOperands(); + for (unsigned i = 0; i < NumOps; ++i) { + emitDecl("CPTmp" + utostr(i)); + emitCode("SDOperand CPTmp" + utostr(i) + ";"); + } + if (CP->hasProperty(SDNPHasChain)) { + const SDNodeInfo &PInfo = ISE.getSDNodeInfo(Parent->getOperator()); + FoldedChains.push_back(std::make_pair("CPInChain", + PInfo.getNumResults())); + ChainName = "Chain" + ChainSuffix; + emitDecl("CPInChain"); + emitDecl(ChainName); + emitCode("SDOperand CPInChain;"); + emitCode("SDOperand " + ChainName + ";"); } - } else if (IntInit *II = - dynamic_cast(Child->getLeafValue())) { - emitCheck("isa(" + RootName + utostr(OpNo) + ")"); - unsigned CTmp = TmpNo++; - emitCode("int64_t CN"+utostr(CTmp)+" = cast("+ - RootName + utostr(OpNo) + ")->getSignExtended();"); - - emitCheck("CN" + utostr(CTmp) + " == " +itostr(II->getValue())); + + std::string Code = Fn + "("; + if (CP->hasProperty(SDNPHasChain)) { + std::string ParentName(RootName.begin(), RootName.end()-1); + Code += "N, " + ParentName + ", "; + } + Code += RootName; + for (unsigned i = 0; i < NumOps; i++) + Code += ", CPTmp" + utostr(i); + if (CP->hasProperty(SDNPHasChain)) + Code += ", CPInChain, Chain" + ChainSuffix; + emitCheck(Code + ")"); + } 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. + emitCheck("cast(" + RootName + + ")->getVT() == MVT::" + LeafRec->getName()); + } else if (LeafRec->isSubClassOf("CondCode")) { + // Make sure this is the specified cond code. + emitCheck("cast(" + RootName + + ")->get() == ISD::" + LeafRec->getName()); } else { #ifndef NDEBUG Child->dump(); + std::cerr << " "; #endif assert(0 && "Unknown leaf type!"); } + + // If there is a node predicate for this, emit the call. + if (!Child->getPredicateFn().empty()) + emitCheck(Child->getPredicateFn() + "(" + RootName + + ".Val)"); + } else if (IntInit *II = + dynamic_cast(Child->getLeafValue())) { + emitCheck("isa(" + RootName + ")"); + unsigned CTmp = TmpNo++; + emitCode("int64_t CN"+utostr(CTmp)+" = cast("+ + RootName + ")->getSignExtended();"); + + emitCheck("CN" + utostr(CTmp) + " == " +itostr(II->getValue())); + } else { +#ifndef NDEBUG + Child->dump(); +#endif + assert(0 && "Unknown leaf type!"); } } - - // If there is a node predicate for this, emit the call. - if (!N->getPredicateFn().empty()) - emitCheck(N->getPredicateFn() + "(" + RootName + ".Val)"); } /// 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 LikeLeaf = false, - bool isRoot = false) { + std::vector + EmitResultCode(TreePatternNode *N, bool RetSelected, + bool InFlagDecled, bool ResNodeDecled, + bool LikeLeaf = false, bool isRoot = false) { + // List of arguments of getTargetNode() or SelectNodeTo(). + std::vector NodeOps; // This is something selected from the pattern we matched. if (!N->getName().empty()) { std::string &Val = VariableMap[N->getName()]; @@ -2409,12 +2529,12 @@ public: "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)); + NodeOps.push_back(Val); + return NodeOps; } const ComplexPattern *CP; unsigned ResNo = TmpNo++; - unsigned NumRes = 1; if (!N->isLeaf() && N->getOperator()->getName() == "imm") { assert(N->getExtTypes().size() == 1 && "Multiple types not handled!"); std::string CastType; @@ -2426,107 +2546,100 @@ public: case MVT::i32: CastType = "unsigned"; break; case MVT::i64: CastType = "uint64_t"; break; } - emitDecl("Tmp" + utostr(ResNo)); - emitCode("Tmp" + utostr(ResNo) + + emitCode("SDOperand Tmp" + utostr(ResNo) + " = CurDAG->getTargetConstant(((" + CastType + ") cast(" + Val + ")->getValue()), " + getEnumName(N->getTypeNum(0)) + ");"); + NodeOps.push_back("Tmp" + utostr(ResNo)); + // 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); } else if (!N->isLeaf() && N->getOperator()->getName() == "texternalsym"){ Record *Op = OperatorMap[N->getName()]; // Transform ExternalSymbol to TargetExternalSymbol if (Op && Op->getName() == "externalsym") { - emitDecl("Tmp" + utostr(ResNo)); - emitCode("Tmp" + utostr(ResNo) + " = CurDAG->getTarget" + emitCode("SDOperand Tmp" + utostr(ResNo) + " = CurDAG->getTarget" "ExternalSymbol(cast(" + Val + ")->getSymbol(), " + getEnumName(N->getTypeNum(0)) + ");"); + NodeOps.push_back("Tmp" + utostr(ResNo)); + // 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); } else { - emitDecl("Tmp" + utostr(ResNo)); - emitCode("Tmp" + utostr(ResNo) + " = " + Val + ";"); + NodeOps.push_back(Val); } } else if (!N->isLeaf() && N->getOperator()->getName() == "tglobaladdr") { Record *Op = OperatorMap[N->getName()]; // Transform GlobalAddress to TargetGlobalAddress if (Op && Op->getName() == "globaladdr") { - emitDecl("Tmp" + utostr(ResNo)); - emitCode("Tmp" + utostr(ResNo) + " = CurDAG->getTarget" + emitCode("SDOperand Tmp" + utostr(ResNo) + " = CurDAG->getTarget" "GlobalAddress(cast(" + Val + ")->getGlobal(), " + getEnumName(N->getTypeNum(0)) + ");"); + NodeOps.push_back("Tmp" + utostr(ResNo)); + // 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); } else { - emitDecl("Tmp" + utostr(ResNo)); - emitCode("Tmp" + utostr(ResNo) + " = " + Val + ";"); + NodeOps.push_back(Val); } } else if (!N->isLeaf() && N->getOperator()->getName() == "texternalsym"){ - emitDecl("Tmp" + utostr(ResNo)); - emitCode("Tmp" + utostr(ResNo) + " = " + Val + ";"); + NodeOps.push_back(Val); + // 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); } else if (!N->isLeaf() && N->getOperator()->getName() == "tconstpool") { - emitDecl("Tmp" + utostr(ResNo)); - emitCode("Tmp" + utostr(ResNo) + " = " + Val + ";"); + NodeOps.push_back(Val); + // 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); } else if (N->isLeaf() && (CP = NodeGetComplexPattern(N, ISE))) { std::string Fn = CP->getSelectFunc(); - NumRes = CP->getNumOperands(); - for (unsigned i = 0; i < NumRes; ++i) - emitDecl("CPTmp" + utostr(i+ResNo)); - - std::string Code = Fn + "(" + Val; - for (unsigned i = 0; i < NumRes; i++) - Code += ", CPTmp" + utostr(i + ResNo); - emitCheck(Code + ")"); - - for (unsigned i = 0; i < NumRes; ++i) { - emitDecl("Tmp" + utostr(i+ResNo)); - emitCode("Select(Tmp" + utostr(i+ResNo) + ", CPTmp" + - utostr(i+ResNo) + ");"); + for (unsigned i = 0; i < CP->getNumOperands(); ++i) { + emitCode("AddToISelQueue(CPTmp" + utostr(i) + ");"); + NodeOps.push_back("CPTmp" + utostr(i)); } - - TmpNo = ResNo + NumRes; } else { - emitDecl("Tmp" + utostr(ResNo)); - // This node, probably wrapped in a SDNodeXForms, behaves like a leaf + // This node, probably wrapped in a SDNodeXForm, behaves like a leaf // node even if it isn't one. Don't select it. - if (LikeLeaf) - emitCode("Tmp" + utostr(ResNo) + " = " + Val + ";"); - else { - emitCode("Select(Tmp" + utostr(ResNo) + ", " + Val + ");"); - } - - if (isRoot && N->isLeaf()) { - emitCode("Result = Tmp" + utostr(ResNo) + ";"); - emitCode("return;"); + if (!LikeLeaf) { + emitCode("AddToISelQueue(" + Val + ");"); + if (isRoot && N->isLeaf()) { + emitCode("ReplaceUses(N, " + Val + ");"); + emitCode("return NULL;"); + } } + NodeOps.push_back(Val); } - // 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); + return NodeOps; } 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")) { - emitDecl("Tmp" + utostr(ResNo)); - emitCode("Tmp" + utostr(ResNo) + " = CurDAG->getRegister(" + + emitCode("SDOperand Tmp" + utostr(ResNo) + " = CurDAG->getRegister(" + ISE.getQualifiedName(DI->getDef()) + ", " + getEnumName(N->getTypeNum(0)) + ");"); - return std::make_pair(1, ResNo); + NodeOps.push_back("Tmp" + utostr(ResNo)); + return NodeOps; } } else if (IntInit *II = dynamic_cast(N->getLeafValue())) { unsigned ResNo = TmpNo++; assert(N->getExtTypes().size() == 1 && "Multiple types not handled!"); - emitDecl("Tmp" + utostr(ResNo)); - emitCode("Tmp" + utostr(ResNo) + + emitCode("SDOperand Tmp" + utostr(ResNo) + " = CurDAG->getTargetConstant(" + itostr(II->getValue()) + ", " + getEnumName(N->getTypeNum(0)) + ");"); - return std::make_pair(1, ResNo); + NodeOps.push_back("Tmp" + utostr(ResNo)); + return NodeOps; } #ifndef NDEBUG N->dump(); #endif assert(0 && "Unknown leaf type!"); - return std::make_pair(1, ~0U); + return NodeOps; } Record *Op = N->getOperator(); @@ -2545,25 +2658,22 @@ public: bool HasImpInputs = isRoot && Inst.getNumImpOperands() > 0; bool HasImpResults = isRoot && Inst.getNumImpResults() > 0; bool NodeHasOptInFlag = isRoot && - PatternHasProperty(Pattern, SDNodeInfo::SDNPOptInFlag, ISE); + PatternHasProperty(Pattern, SDNPOptInFlag, ISE); bool NodeHasInFlag = isRoot && - PatternHasProperty(Pattern, SDNodeInfo::SDNPInFlag, ISE); + PatternHasProperty(Pattern, SDNPInFlag, ISE); bool NodeHasOutFlag = HasImpResults || (isRoot && - PatternHasProperty(Pattern, SDNodeInfo::SDNPOutFlag, ISE)); + PatternHasProperty(Pattern, SDNPOutFlag, ISE)); bool NodeHasChain = InstPatNode && - PatternHasProperty(InstPatNode, SDNodeInfo::SDNPHasChain, ISE); + PatternHasProperty(InstPatNode, SDNPHasChain, ISE); bool InputHasChain = isRoot && - NodeHasProperty(Pattern, SDNodeInfo::SDNPHasChain, ISE); + NodeHasProperty(Pattern, SDNPHasChain, ISE); - if (NodeHasInFlag || NodeHasOutFlag || NodeHasOptInFlag || HasImpInputs) - emitDecl("InFlag"); if (NodeHasOptInFlag) { - emitDecl("HasInFlag", 2); - emitCode("HasInFlag = " + emitCode("bool HasInFlag = " "(N.getOperand(N.getNumOperands()-1).getValueType() == MVT::Flag);"); } if (HasVarOps) - emitCode("std::vector Ops;"); + emitCode("SmallVector Ops" + utostr(OpcNo) + ";"); // How many results is this pattern expected to produce? unsigned PatResults = 0; @@ -2573,46 +2683,51 @@ public: PatResults++; } - // 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)); + if (OrigChains.size() > 0) { + // The original input chain is being ignored. If it is not just + // pointing to the op that's being folded, we should create a + // TokenFactor with it and the chain of the folded op as the new chain. + // We could potentially be doing multiple levels of folding, in that + // case, the TokenFactor can have more operands. + emitCode("SmallVector InChains;"); + for (unsigned i = 0, e = OrigChains.size(); i < e; ++i) { + emitCode("if (" + OrigChains[i].first + ".Val != " + + OrigChains[i].second + ".Val) {"); + emitCode(" AddToISelQueue(" + OrigChains[i].first + ");"); + emitCode(" InChains.push_back(" + OrigChains[i].first + ");"); + emitCode("}"); } + emitCode("AddToISelQueue(" + ChainName + ");"); + emitCode("InChains.push_back(" + ChainName + ");"); + emitCode(ChainName + " = CurDAG->getNode(ISD::TokenFactor, MVT::Other, " + "&InChains[0], InChains.size());"); } - // 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; - } - - // 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); + std::vector AllOps; + for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { + std::vector Ops = EmitResultCode(N->getChild(i), + RetSelected, InFlagDecled, ResNodeDecled); + AllOps.insert(AllOps.end(), Ops.begin(), Ops.end()); } // Emit all the chain and CopyToReg stuff. bool ChainEmitted = NodeHasChain; if (NodeHasChain) - emitCode("Select(" + ChainName + ", " + ChainName + ");"); + emitCode("AddToISelQueue(" + ChainName + ");"); if (NodeHasInFlag || HasImpInputs) - EmitInFlagSelectCode(Pattern, "N", ChainEmitted, true); - if (NodeHasOptInFlag) { - emitCode("if (HasInFlag)"); - emitCode(" Select(InFlag, N.getOperand(N.getNumOperands()-1));"); + EmitInFlagSelectCode(Pattern, "N", ChainEmitted, + InFlagDecled, ResNodeDecled, true); + if (NodeHasOptInFlag || NodeHasInFlag || HasImpInputs) { + if (!InFlagDecled) { + emitCode("SDOperand InFlag(0, 0);"); + InFlagDecled = true; + } + if (NodeHasOptInFlag) { + emitCode("if (HasInFlag) {"); + emitCode(" InFlag = N.getOperand(N.getNumOperands()-1);"); + emitCode(" AddToISelQueue(InFlag);"); + emitCode("}"); + } } unsigned NumResults = Inst.getNumResults(); @@ -2624,14 +2739,17 @@ public: std::string NodeName; if (!isRoot) { NodeName = "Tmp" + utostr(ResNo); - emitDecl(NodeName); - Code2 = NodeName + " = SDOperand("; + Code2 = "SDOperand " + NodeName + " = SDOperand("; } else { NodeName = "ResNode"; - emitDecl(NodeName, true); - Code2 = NodeName + " = "; + if (!ResNodeDecled) + Code2 = "SDNode *" + NodeName + " = "; + else + Code2 = NodeName + " = "; } + Code = "CurDAG->getTargetNode(Opc" + utostr(OpcNo); + unsigned OpsNo = OpcNo; emitOpcode(II.Namespace + "::" + II.TheDef->getName()); // Output order: results, chain, flags @@ -2646,11 +2764,10 @@ public: Code += ", MVT::Flag"; // Inputs. - for (unsigned i = 0, e = Ops.size(); i != e; ++i) { - if (HasVarOps) - emitCode("Ops.push_back(Tmp" + utostr(Ops[i]) + ");"); - else - Code += ", Tmp" + utostr(Ops[i]); + if (HasVarOps) { + for (unsigned i = 0, e = AllOps.size(); i != e; ++i) + emitCode("Ops" + utostr(OpsNo) + ".push_back(" + AllOps[i] + ");"); + AllOps.clear(); } if (HasVarOps) { @@ -2663,33 +2780,52 @@ public: else emitCode("for (unsigned i = 2, e = N.getNumOperands(); " "i != e; ++i) {"); - emitCode(" SDOperand VarOp(0, 0);"); - emitCode(" Select(VarOp, N.getOperand(i));"); - emitCode(" Ops.push_back(VarOp);"); + emitCode(" AddToISelQueue(N.getOperand(i));"); + emitCode(" Ops" + utostr(OpsNo) + ".push_back(N.getOperand(i));"); emitCode("}"); } if (NodeHasChain) { if (HasVarOps) - emitCode("Ops.push_back(" + ChainName + ");"); + emitCode("Ops" + utostr(OpsNo) + ".push_back(" + ChainName + ");"); else - Code += ", " + ChainName; + AllOps.push_back(ChainName); } - if (NodeHasInFlag || HasImpInputs) { - if (HasVarOps) - emitCode("Ops.push_back(InFlag);"); - else - Code += ", InFlag"; - } else if (NodeHasOptInFlag && HasVarOps) { - emitCode("if (HasInFlag)"); - emitCode(" Ops.push_back(InFlag);"); - } - - if (HasVarOps) - Code += ", Ops"; - else if (NodeHasOptInFlag) - Code = "HasInFlag ? " + Code + ", InFlag) : " + Code; + if (HasVarOps) { + if (NodeHasInFlag || HasImpInputs) + emitCode("Ops" + utostr(OpsNo) + ".push_back(InFlag);"); + else if (NodeHasOptInFlag) { + emitCode("if (HasInFlag)"); + emitCode(" Ops" + utostr(OpsNo) + ".push_back(InFlag);"); + } + Code += ", &Ops" + utostr(OpsNo) + "[0], Ops" + utostr(OpsNo) + + ".size()"; + } else if (NodeHasInFlag || NodeHasOptInFlag || HasImpInputs) + AllOps.push_back("InFlag"); + + unsigned NumOps = AllOps.size(); + if (NumOps) { + if (!NodeHasOptInFlag && NumOps < 4) { + for (unsigned i = 0; i != NumOps; ++i) + Code += ", " + AllOps[i]; + } else { + std::string OpsCode = "SDOperand Ops" + utostr(OpsNo) + "[] = { "; + for (unsigned i = 0; i != NumOps; ++i) { + OpsCode += AllOps[i]; + if (i != NumOps-1) + OpsCode += ", "; + } + emitCode(OpsCode + " };"); + Code += ", Ops" + utostr(OpsNo) + ", "; + if (NodeHasOptInFlag) { + Code += "HasInFlag ? "; + Code += utostr(NumOps) + " : " + utostr(NumOps-1); + } else + Code += utostr(NumOps); + } + } + if (!isRoot) Code += "), 0"; emitCode(Code2 + Code + ");"); @@ -2703,136 +2839,123 @@ public: emitCode(ChainName + " = SDOperand(" + NodeName + ", " + utostr(PatResults) + ");"); - if (!isRoot) - return std::make_pair(1, ResNo); - - for (unsigned i = 0; i < NumResults; i++) - emitCode("SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, " + - utostr(i) + ", ResNode, " + utostr(i) + ");"); - - if (NodeHasOutFlag) - emitCode("InFlag = SDOperand(ResNode, " + - utostr(NumResults + (unsigned)NodeHasChain) + ");"); + if (!isRoot) { + NodeOps.push_back("Tmp" + utostr(ResNo)); + return NodeOps; + } - if (HasImpResults && EmitCopyFromRegs(N, ChainEmitted)) { - emitCode("SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, " - "0, ResNode, 0);"); - NumResults = 1; + bool NeedReplace = false; + if (NodeHasOutFlag) { + if (!InFlagDecled) { + emitCode("SDOperand InFlag = SDOperand(ResNode, " + + utostr(NumResults + (unsigned)NodeHasChain) + ");"); + InFlagDecled = true; + } else + emitCode("InFlag = SDOperand(ResNode, " + + utostr(NumResults + (unsigned)NodeHasChain) + ");"); } - if (InputHasChain) { - emitCode("SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, " + - utostr(PatResults) + ", " + ChainName + ".Val, " + - ChainName + ".ResNo" + ");"); - if (DoReplace) - emitCode("if (N.ResNo == 0) AddHandleReplacement(N.Val, " + - utostr(PatResults) + ", " + ChainName + ".Val, " + - ChainName + ".ResNo" + ");"); + if (HasImpResults && EmitCopyFromRegs(N, ResNodeDecled, ChainEmitted)) { + emitCode("ReplaceUses(SDOperand(N.Val, 0), SDOperand(ResNode, 0));"); + NumResults = 1; } if (FoldedChains.size() > 0) { std::string Code; for (unsigned j = 0, e = FoldedChains.size(); j < e; j++) - emitCode("SelectionDAG::InsertISelMapEntry(CodeGenMap, " + + emitCode("ReplaceUses(SDOperand(" + FoldedChains[j].first + ".Val, " + - utostr(FoldedChains[j].second) + ", ResNode, " + - utostr(NumResults) + ");"); - - for (unsigned j = 0, e = FoldedChains.size(); j < e; j++) { - std::string Code = - FoldedChains[j].first + ".Val, " + - utostr(FoldedChains[j].second) + ", "; - emitCode("AddHandleReplacement(" + Code + "ResNode, " + - utostr(NumResults) + ");"); - } + utostr(FoldedChains[j].second) + "), SDOperand(ResNode, " + + utostr(NumResults) + "));"); + NeedReplace = true; } - if (NodeHasOutFlag) - emitCode("SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, " + - utostr(PatResults + (unsigned)InputHasChain) + - ", InFlag.Val, InFlag.ResNo);"); + if (NodeHasOutFlag) { + emitCode("ReplaceUses(SDOperand(N.Val, " + + utostr(PatResults + (unsigned)InputHasChain) +"), InFlag);"); + NeedReplace = true; + } + + if (NeedReplace) { + for (unsigned i = 0; i < NumResults; i++) + emitCode("ReplaceUses(SDOperand(N.Val, " + + utostr(i) + "), SDOperand(ResNode, " + utostr(i) + "));"); + if (InputHasChain) + emitCode("ReplaceUses(SDOperand(N.Val, " + + utostr(PatResults) + "), SDOperand(" + ChainName + ".Val, " + + ChainName + ".ResNo" + "));"); + } else + RetSelected = true; // User does not expect the instruction would produce a chain! - bool AddedChain = NodeHasChain && !InputHasChain; - if (AddedChain && NodeHasOutFlag) { - if (PatResults == 0) { - emitCode("Result = SDOperand(ResNode, N.ResNo+1);"); - } else { - emitCode("if (N.ResNo < " + utostr(PatResults) + ")"); - emitCode(" Result = SDOperand(ResNode, N.ResNo);"); - emitCode("else"); - emitCode(" Result = SDOperand(ResNode, N.ResNo+1);"); - } + if ((!InputHasChain && NodeHasChain) && NodeHasOutFlag) { + ; } else if (InputHasChain && !NodeHasChain) { // One of the inner node produces a chain. - emitCode("if (N.ResNo < " + utostr(PatResults) + ")"); - emitCode(" Result = SDOperand(ResNode, N.ResNo);"); - if (NodeHasOutFlag) { - emitCode("else if (N.ResNo > " + utostr(PatResults) + ")"); - emitCode(" Result = SDOperand(ResNode, N.ResNo-1);"); - } - emitCode("else"); - emitCode(" Result = SDOperand(" + ChainName + ".Val, " + - ChainName + ".ResNo);"); - } else { - emitCode("Result = SDOperand(ResNode, N.ResNo);"); + if (NodeHasOutFlag) + emitCode("ReplaceUses(SDOperand(N.Val, " + utostr(PatResults+1) + + "), SDOperand(ResNode, N.ResNo-1));"); + for (unsigned i = 0; i < PatResults; ++i) + emitCode("ReplaceUses(SDOperand(N.Val, " + utostr(i) + + "), SDOperand(ResNode, " + utostr(i) + "));"); + emitCode("ReplaceUses(SDOperand(N.Val, " + utostr(PatResults) + + "), " + ChainName + ");"); + RetSelected = false; } + + if (RetSelected) + emitCode("return ResNode;"); + else + emitCode("return NULL;"); } 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. - emitCode("if (N.Val->hasOneUse()) {"); - std::string Code = " Result = CurDAG->SelectNodeTo(N.Val, Opc" + + std::string Code = "return CurDAG->SelectNodeTo(N.Val, Opc" + utostr(OpcNo); if (N->getTypeNum(0) != MVT::isVoid) Code += ", VT" + utostr(VTNo); if (NodeHasOutFlag) Code += ", MVT::Flag"; - for (unsigned i = 0, e = Ops.size(); i != e; ++i) - Code += ", Tmp" + utostr(Ops[i]); - if (NodeHasInFlag || HasImpInputs) - Code += ", InFlag"; + + if (NodeHasInFlag || NodeHasOptInFlag || HasImpInputs) + AllOps.push_back("InFlag"); + + unsigned NumOps = AllOps.size(); + if (NumOps) { + if (!NodeHasOptInFlag && NumOps < 4) { + for (unsigned i = 0; i != NumOps; ++i) + Code += ", " + AllOps[i]; + } else { + std::string OpsCode = "SDOperand Ops" + utostr(OpcNo) + "[] = { "; + for (unsigned i = 0; i != NumOps; ++i) { + OpsCode += AllOps[i]; + if (i != NumOps-1) + OpsCode += ", "; + } + emitCode(OpsCode + " };"); + Code += ", Ops" + utostr(OpcNo) + ", "; + Code += utostr(NumOps); + } + } emitCode(Code + ");"); - emitCode("} else {"); - emitDecl("ResNode", 1); - Code = " ResNode = CurDAG->getTargetNode(Opc" + utostr(OpcNo); emitOpcode(II.Namespace + "::" + II.TheDef->getName()); - if (N->getTypeNum(0) != MVT::isVoid) { - Code += ", VT" + utostr(VTNo); + if (N->getTypeNum(0) != MVT::isVoid) emitVT(getEnumName(N->getTypeNum(0))); - } - if (NodeHasOutFlag) - Code += ", MVT::Flag"; - for (unsigned i = 0, e = Ops.size(); i != e; ++i) - Code += ", Tmp" + utostr(Ops[i]); - if (NodeHasInFlag || HasImpInputs) - Code += ", InFlag"; - emitCode(Code + ");"); - emitCode(" SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, N.ResNo" - ", ResNode, 0);"); - emitCode(" Result = SDOperand(ResNode, 0);"); - emitCode("}"); } - if (isRoot) - emitCode("return;"); - return std::make_pair(1, ResNo); + return NodeOps; } else if (Op->isSubClassOf("SDNodeXForm")) { assert(N->getNumChildren() == 1 && "node xform should have one child!"); // PatLeaf node - the operand may or may not be a leaf node. But it should // behave like one. - unsigned OpVal = EmitResultCode(N->getChild(0), true).second; + std::vector Ops = + EmitResultCode(N->getChild(0), RetSelected, InFlagDecled, + ResNodeDecled, true); unsigned ResNo = TmpNo++; - emitDecl("Tmp" + utostr(ResNo)); - emitCode("Tmp" + utostr(ResNo) + " = Transform_" + Op->getName() - + "(Tmp" + utostr(OpVal) + ".Val);"); - if (isRoot) { - emitCode("SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val," - "N.ResNo, Tmp" + utostr(ResNo) + ".Val, Tmp" + - utostr(ResNo) + ".ResNo);"); - emitCode("Result = Tmp" + utostr(ResNo) + ";"); - emitCode("return;"); - } - return std::make_pair(1, ResNo); + emitCode("SDOperand Tmp" + utostr(ResNo) + " = Transform_" + Op->getName() + + "(" + Ops.back() + ".Val);"); + NodeOps.push_back("Tmp" + utostr(ResNo)); + if (isRoot) + emitCode("return Tmp" + utostr(ResNo) + ".Val;"); + return NodeOps; } else { N->dump(); std::cerr << "\n"; @@ -2845,18 +2968,20 @@ public: /// '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) { + const std::string &Prefix, bool isRoot = false) { // Did we find one? if (Pat->getExtTypes() != Other->getExtTypes()) { // Move a type over from 'other' to 'pat'. Pat->setTypes(Other->getExtTypes()); - emitCheck(Prefix + ".Val->getValueType(0) == " + - getName(Pat->getTypeNum(0))); + // The top level node type is checked outside of the select function. + if (!isRoot) + emitCheck(Prefix + ".Val->getValueType(0) == " + + getName(Pat->getTypeNum(0))); return true; } unsigned OpNo = - (unsigned) NodeHasProperty(Pat, SDNodeInfo::SDNPHasChain, ISE); + (unsigned) NodeHasProperty(Pat, SDNPHasChain, ISE); for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i, ++OpNo) if (InsertOneTypeCheck(Pat->getChild(i), Other->getChild(i), Prefix + utostr(OpNo))) @@ -2868,15 +2993,17 @@ private: /// EmitInFlagSelectCode - Emit the flag operands for the DAG that is /// being built. void EmitInFlagSelectCode(TreePatternNode *N, const std::string &RootName, - bool &ChainEmitted, bool isRoot = false) { + bool &ChainEmitted, bool &InFlagDecled, + bool &ResNodeDecled, bool isRoot = false) { const CodeGenTarget &T = ISE.getTargetInfo(); unsigned OpNo = - (unsigned) NodeHasProperty(N, SDNodeInfo::SDNPHasChain, ISE); - bool HasInFlag = NodeHasProperty(N, SDNodeInfo::SDNPInFlag, ISE); + (unsigned) NodeHasProperty(N, SDNPHasChain, ISE); + bool HasInFlag = NodeHasProperty(N, SDNPInFlag, ISE); for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) { TreePatternNode *Child = N->getChild(i); if (!Child->isLeaf()) { - EmitInFlagSelectCode(Child, RootName + utostr(OpNo), ChainEmitted); + EmitInFlagSelectCode(Child, RootName + utostr(OpNo), ChainEmitted, + InFlagDecled, ResNodeDecled); } else { if (DefInit *DI = dynamic_cast(Child->getLeafValue())) { if (!Child->getName().empty()) { @@ -2890,20 +3017,28 @@ private: if (RR->isSubClassOf("Register")) { MVT::ValueType RVT = getRegisterValueType(RR, T); if (RVT == MVT::Flag) { - emitCode("Select(InFlag, " + RootName + utostr(OpNo) + ");"); + if (!InFlagDecled) { + emitCode("SDOperand InFlag = " + RootName + utostr(OpNo) + ";"); + InFlagDecled = true; + } else + emitCode("InFlag = " + RootName + utostr(OpNo) + ";"); + emitCode("AddToISelQueue(InFlag);"); } else { if (!ChainEmitted) { - emitDecl("Chain"); - emitCode("Chain = CurDAG->getEntryNode();"); + emitCode("SDOperand Chain = CurDAG->getEntryNode();"); ChainName = "Chain"; ChainEmitted = true; } - emitCode("Select(" + RootName + utostr(OpNo) + ", " + - RootName + utostr(OpNo) + ");"); - emitCode("ResNode = CurDAG->getCopyToReg(" + ChainName + - ", CurDAG->getRegister(" + ISE.getQualifiedName(RR) + - ", " + getEnumName(RVT) + "), " + - RootName + utostr(OpNo) + ", InFlag).Val;"); + emitCode("AddToISelQueue(" + RootName + utostr(OpNo) + ");"); + if (!InFlagDecled) { + emitCode("SDOperand InFlag(0, 0);"); + InFlagDecled = true; + } + std::string Decl = (!ResNodeDecled) ? "SDNode *" : ""; + emitCode(Decl + "ResNode = CurDAG->getCopyToReg(" + ChainName + + ", " + ISE.getQualifiedName(RR) + + ", " + RootName + utostr(OpNo) + ", InFlag).Val;"); + ResNodeDecled = true; emitCode(ChainName + " = SDOperand(ResNode, 0);"); emitCode("InFlag = SDOperand(ResNode, 1);"); } @@ -2912,15 +3047,23 @@ private: } } - if (HasInFlag) - emitCode("Select(InFlag, " + RootName + - ".getOperand(" + utostr(OpNo) + "));"); + if (HasInFlag) { + if (!InFlagDecled) { + emitCode("SDOperand InFlag = " + RootName + + ".getOperand(" + utostr(OpNo) + ");"); + InFlagDecled = true; + } else + emitCode("InFlag = " + RootName + + ".getOperand(" + utostr(OpNo) + ");"); + emitCode("AddToISelQueue(InFlag);"); + } } /// EmitCopyFromRegs - Emit code to copy result to physical registers /// as specified by the instruction. It returns true if any copy is /// emitted. - bool EmitCopyFromRegs(TreePatternNode *N, bool &ChainEmitted) { + bool EmitCopyFromRegs(TreePatternNode *N, bool &ResNodeDecled, + bool &ChainEmitted) { bool RetVal = false; Record *Op = N->getOperator(); if (Op->isSubClassOf("Instruction")) { @@ -2933,14 +3076,15 @@ private: MVT::ValueType RVT = getRegisterValueType(RR, CGT); if (RVT != MVT::Flag) { if (!ChainEmitted) { - emitDecl("Chain"); - emitCode("Chain = CurDAG->getEntryNode();"); + emitCode("SDOperand Chain = CurDAG->getEntryNode();"); ChainEmitted = true; ChainName = "Chain"; } - emitCode("ResNode = CurDAG->getCopyFromReg(" + ChainName + + std::string Decl = (!ResNodeDecled) ? "SDNode *" : ""; + emitCode(Decl + "ResNode = CurDAG->getCopyFromReg(" + ChainName + ", " + ISE.getQualifiedName(RR) + ", " + getEnumName(RVT) + ", InFlag).Val;"); + ResNodeDecled = true; emitCode(ChainName + " = SDOperand(ResNode, 1);"); emitCode("InFlag = SDOperand(ResNode, 2);"); RetVal = true; @@ -2956,20 +3100,18 @@ private: /// stream to match the pattern, and generate the code for the match if it /// succeeds. Returns true if the pattern is not guaranteed to match. void DAGISelEmitter::GenerateCodeForPattern(PatternToMatch &Pattern, - std::vector > &GeneratedCode, - std::set > &GeneratedDecl, + std::vector > &GeneratedCode, + std::set &GeneratedDecl, std::vector &TargetOpcodes, - std::vector &TargetVTs, - bool DoReplace) { + std::vector &TargetVTs) { PatternCodeEmitter Emitter(*this, Pattern.getPredicates(), Pattern.getSrcPattern(), Pattern.getDstPattern(), GeneratedCode, GeneratedDecl, - TargetOpcodes, TargetVTs, - DoReplace); + TargetOpcodes, TargetVTs); // Emit the matcher, capturing named arguments in VariableMap. bool FoundChain = false; - Emitter.EmitMatchCode(Pattern.getSrcPattern(), NULL, "N", "", "", FoundChain); + Emitter.EmitMatchCode(Pattern.getSrcPattern(), NULL, "N", "", FoundChain); // TP - Get *SOME* tree pattern, we don't care which. TreePattern &TP = *PatternFragments.begin()->second; @@ -3005,9 +3147,10 @@ void DAGISelEmitter::GenerateCodeForPattern(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 (Emitter.InsertOneTypeCheck(Pat, Pattern.getSrcPattern(), "N")); + } while (Emitter.InsertOneTypeCheck(Pat, Pattern.getSrcPattern(), "N", true)); - Emitter.EmitResultCode(Pattern.getDstPattern(), false, true /*the root*/); + Emitter.EmitResultCode(Pattern.getDstPattern(), + false, false, false, false, true); delete Pat; } @@ -3015,7 +3158,7 @@ void DAGISelEmitter::GenerateCodeForPattern(PatternToMatch &Pattern, /// a line causes any of them to be empty, remove them and return true when /// done. static bool EraseCodeLine(std::vector > > > + std::vector > > > &Patterns) { bool ErasedPatterns = false; for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { @@ -3032,10 +3175,10 @@ static bool EraseCodeLine(std::vector > > > + std::vector > > > &Patterns, unsigned Indent, std::ostream &OS) { - typedef std::pair CodeLine; + typedef std::pair CodeLine; typedef std::vector CodeList; typedef std::vector > PatternList; @@ -3071,12 +3214,12 @@ void DAGISelEmitter::EmitPatterns(std::vectorgetOperator()].push_back(&PatternsToMatch[i]); } else { const ComplexPattern *CP; - if (IntInit *II = - dynamic_cast(Node->getLeafValue())) { + if (dynamic_cast(Node->getLeafValue())) { PatternsByOpcode[getSDNodeNamed("imm")].push_back(&PatternsToMatch[i]); - } else if ((CP = NodeGetComplexPattern(Node, *this))) { + } else if (NodeGetComplexPattern(Node, *this)) { std::vector OpNodes = CP->getRootNodes(); for (unsigned j = 0, e = OpNodes.size(); j != e; j++) { PatternsByOpcode[OpNodes[j]] @@ -3190,7 +3334,12 @@ void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) { } } } - + + // For each opcode, there might be multiple select functions, one per + // ValueType of the node (or its first operand if it doesn't produce a + // non-chain result. + std::map > OpcodeVTMap; + // Emit one Select_* method for each top-level opcode. We do this instead of // emitting one giant switch statement to support compilers where this will // result in the recursive functions taking less stack space. @@ -3199,239 +3348,225 @@ void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) { E = PatternsByOpcode.end(); PBOI != E; ++PBOI) { const std::string &OpName = PBOI->first->getName(); const SDNodeInfo &OpcodeInfo = getSDNodeInfo(PBOI->first); - bool OptSlctOrder = - (OpcodeInfo.hasProperty(SDNodeInfo::SDNPHasChain) && - OpcodeInfo.getNumResults() > 0); - std::vector &Patterns = PBOI->second; - assert(!Patterns.empty() && "No patterns but map has entry?"); - + std::vector &PatternsOfOp = PBOI->second; + assert(!PatternsOfOp.empty() && "No patterns but map has entry?"); + // We want to emit all of the matching code now. However, we want to emit // 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(), + std::stable_sort(PatternsOfOp.begin(), PatternsOfOp.end(), PatternSortingPredicate(*this)); - typedef std::vector > CodeList; - typedef std::vector >::iterator CodeListI; - - std::vector > CodeForPatterns; - std::vector > PatternOpcodes; - std::vector > PatternVTs; - std::vector > > PatternDecls; - std::set > AllGenDecls; - for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { - CodeList GeneratedCode; - std::set > GeneratedDecl; - std::vector TargetOpcodes; - std::vector TargetVTs; - GenerateCodeForPattern(*Patterns[i], GeneratedCode, GeneratedDecl, - TargetOpcodes, TargetVTs, OptSlctOrder); - for (std::set >::iterator - si = GeneratedDecl.begin(), se = GeneratedDecl.end(); si!=se; ++si) - AllGenDecls.insert(*si); - CodeForPatterns.push_back(std::make_pair(Patterns[i], GeneratedCode)); - PatternDecls.push_back(GeneratedDecl); - PatternOpcodes.push_back(TargetOpcodes); - PatternVTs.push_back(TargetVTs); + // Split them into groups by type. + std::map > PatternsByType; + for (unsigned i = 0, e = PatternsOfOp.size(); i != e; ++i) { + PatternToMatch *Pat = PatternsOfOp[i]; + TreePatternNode *SrcPat = Pat->getSrcPattern(); + if (OpcodeInfo.getNumResults() == 0 && SrcPat->getNumChildren() > 0) + SrcPat = SrcPat->getChild(0); + MVT::ValueType VT = SrcPat->getTypeNum(0); + std::map >::iterator TI = + PatternsByType.find(VT); + if (TI != PatternsByType.end()) + TI->second.push_back(Pat); + else { + std::vector PVec; + PVec.push_back(Pat); + PatternsByType.insert(std::make_pair(VT, PVec)); + } } + + for (std::map >::iterator + II = PatternsByType.begin(), EE = PatternsByType.end(); II != EE; + ++II) { + MVT::ValueType OpVT = II->first; + std::vector &Patterns = II->second; + typedef std::vector > CodeList; + typedef std::vector >::iterator CodeListI; - // Scan the code to see if all of the patterns are reachable and if it is - // possible that the last one might not match. - bool mightNotMatch = true; - for (unsigned i = 0, e = CodeForPatterns.size(); i != e; ++i) { - CodeList &GeneratedCode = CodeForPatterns[i].second; - mightNotMatch = false; - - for (unsigned j = 0, e = GeneratedCode.size(); j != e; ++j) { - if (GeneratedCode[j].first) { // predicate. - mightNotMatch = true; - break; - } + std::vector > CodeForPatterns; + std::vector > PatternOpcodes; + std::vector > PatternVTs; + std::vector > PatternDecls; + for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { + CodeList GeneratedCode; + std::set GeneratedDecl; + std::vector TargetOpcodes; + std::vector TargetVTs; + GenerateCodeForPattern(*Patterns[i], GeneratedCode, GeneratedDecl, + TargetOpcodes, TargetVTs); + CodeForPatterns.push_back(std::make_pair(Patterns[i], GeneratedCode)); + PatternDecls.push_back(GeneratedDecl); + PatternOpcodes.push_back(TargetOpcodes); + PatternVTs.push_back(TargetVTs); } + + // Scan the code to see if all of the patterns are reachable and if it is + // possible that the last one might not match. + bool mightNotMatch = true; + for (unsigned i = 0, e = CodeForPatterns.size(); i != e; ++i) { + CodeList &GeneratedCode = CodeForPatterns[i].second; + mightNotMatch = false; + + for (unsigned j = 0, e = GeneratedCode.size(); j != e; ++j) { + if (GeneratedCode[j].first == 1) { // predicate. + mightNotMatch = true; + break; + } + } - // If this pattern definitely matches, and if it isn't the last one, the - // patterns after it CANNOT ever match. Error out. - if (mightNotMatch == false && i != CodeForPatterns.size()-1) { - std::cerr << "Pattern '"; - CodeForPatterns[i+1].first->getSrcPattern()->print(OS); - std::cerr << "' is impossible to select!\n"; - exit(1); + // If this pattern definitely matches, and if it isn't the last one, the + // patterns after it CANNOT ever match. Error out. + if (mightNotMatch == false && i != CodeForPatterns.size()-1) { + std::cerr << "Pattern '"; + CodeForPatterns[i].first->getSrcPattern()->print(std::cerr); + std::cerr << "' is impossible to select!\n"; + exit(1); + } } - } - // Factor target node emission code (emitted by EmitResultCode) into - // separate functions. Uniquing and share them among all instruction - // selection routines. - for (unsigned i = 0, e = CodeForPatterns.size(); i != e; ++i) { - CodeList &GeneratedCode = CodeForPatterns[i].second; - std::vector &TargetOpcodes = PatternOpcodes[i]; - std::vector &TargetVTs = PatternVTs[i]; - std::set > Decls = PatternDecls[i]; - int CodeSize = (int)GeneratedCode.size(); - int LastPred = -1; - for (int j = CodeSize-1; j >= 0; --j) { - if (GeneratedCode[j].first) { - LastPred = j; - break; + // Factor target node emission code (emitted by EmitResultCode) into + // separate functions. Uniquing and share them among all instruction + // selection routines. + for (unsigned i = 0, e = CodeForPatterns.size(); i != e; ++i) { + CodeList &GeneratedCode = CodeForPatterns[i].second; + std::vector &TargetOpcodes = PatternOpcodes[i]; + std::vector &TargetVTs = PatternVTs[i]; + std::set Decls = PatternDecls[i]; + std::vector AddedInits; + int CodeSize = (int)GeneratedCode.size(); + int LastPred = -1; + for (int j = CodeSize-1; j >= 0; --j) { + if (LastPred == -1 && GeneratedCode[j].first == 1) + LastPred = j; + else if (LastPred != -1 && GeneratedCode[j].first == 2) + AddedInits.push_back(GeneratedCode[j].second); } - } - std::string CalleeDecls; - std::string CalleeCode = "(SDOperand &Result, SDOperand &N"; - std::string CallerCode = "(Result, N"; - for (unsigned j = 0, e = TargetOpcodes.size(); j != e; ++j) { - CalleeCode += ", unsigned Opc" + utostr(j); - CallerCode += ", " + TargetOpcodes[j]; - } - for (unsigned j = 0, e = TargetVTs.size(); j != e; ++j) { - CalleeCode += ", MVT::ValueType VT" + utostr(j); - CallerCode += ", " + TargetVTs[j]; - } - for (std::set >::iterator - I = Decls.begin(), E = Decls.end(); I != E; ++I) { - std::string Name = I->second; - if (I->first == 0) { - if (Name == "InFlag" || - (Name.size() > 3 && - Name[0] == 'T' && Name[1] == 'm' && Name[2] == 'p')) { - CalleeDecls += " SDOperand " + Name + "(0, 0);\n"; - continue; - } + std::string CalleeCode = "(const SDOperand &N"; + std::string CallerCode = "(N"; + for (unsigned j = 0, e = TargetOpcodes.size(); j != e; ++j) { + CalleeCode += ", unsigned Opc" + utostr(j); + CallerCode += ", " + TargetOpcodes[j]; + } + for (unsigned j = 0, e = TargetVTs.size(); j != e; ++j) { + CalleeCode += ", MVT::ValueType VT" + utostr(j); + CallerCode += ", " + TargetVTs[j]; + } + for (std::set::iterator + I = Decls.begin(), E = Decls.end(); I != E; ++I) { + std::string Name = *I; CalleeCode += ", SDOperand &" + Name; CallerCode += ", " + Name; - } else if (I->first == 1) { - if (Name == "ResNode") { - CalleeDecls += " SDNode *" + Name + " = NULL;\n"; - continue; - } - CalleeCode += ", SDNode *" + Name; - CallerCode += ", " + Name; + } + CallerCode += ");"; + CalleeCode += ") "; + // Prevent emission routines from being inlined to reduce selection + // routines stack frame sizes. + CalleeCode += "DISABLE_INLINE "; + CalleeCode += "{\n"; + + for (std::vector::const_reverse_iterator + I = AddedInits.rbegin(), E = AddedInits.rend(); I != E; ++I) + CalleeCode += " " + *I + "\n"; + + for (int j = LastPred+1; j < CodeSize; ++j) + CalleeCode += " " + GeneratedCode[j].second + "\n"; + for (int j = LastPred+1; j < CodeSize; ++j) + GeneratedCode.pop_back(); + CalleeCode += "}\n"; + + // Uniquing the emission routines. + unsigned EmitFuncNum; + std::map::iterator EFI = + EmitFunctions.find(CalleeCode); + if (EFI != EmitFunctions.end()) { + EmitFuncNum = EFI->second; } else { - CalleeCode += ", bool " + Name; - CallerCode += ", " + Name; + EmitFuncNum = EmitFunctions.size(); + EmitFunctions.insert(std::make_pair(CalleeCode, EmitFuncNum)); + OS << "SDNode *Emit_" << utostr(EmitFuncNum) << CalleeCode; } - } - CallerCode += ");"; - CalleeCode += ") "; - // Prevent emission routines from being inlined to reduce selection - // routines stack frame sizes. - CalleeCode += "NOINLINE "; - CalleeCode += "{\n" + CalleeDecls; - for (int j = LastPred+1; j < CodeSize; ++j) - CalleeCode += " " + GeneratedCode[j].second + '\n'; - for (int j = LastPred+1; j < CodeSize; ++j) - GeneratedCode.pop_back(); - CalleeCode += "}\n"; - - // Uniquing the emission routines. - unsigned EmitFuncNum; - std::map::iterator EFI = - EmitFunctions.find(CalleeCode); - if (EFI != EmitFunctions.end()) { - EmitFuncNum = EFI->second; - } else { - EmitFuncNum = EmitFunctions.size(); - EmitFunctions.insert(std::make_pair(CalleeCode, EmitFuncNum)); - OS << "void " << "Emit_" << utostr(EmitFuncNum) << CalleeCode; - } - // Replace the emission code within selection routines with calls to the - // emission functions. - CallerCode = "Emit_" + utostr(EmitFuncNum) + CallerCode; - GeneratedCode.push_back(std::make_pair(false, CallerCode)); - GeneratedCode.push_back(std::make_pair(false, "return;")); - } - - // Print function. - OS << "void Select_" << OpName << "(SDOperand &Result, SDOperand N) {\n"; - if (OptSlctOrder) { - OS << " if (N.ResNo == " << OpcodeInfo.getNumResults() - << " && N.getValue(0).hasOneUse()) {\n" - << " SDOperand Dummy = " - << "CurDAG->getNode(ISD::HANDLENODE, MVT::Other, N);\n" - << " SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, " - << OpcodeInfo.getNumResults() << ", Dummy.Val, 0);\n" - << " SelectionDAG::InsertISelMapEntry(HandleMap, N.Val, " - << OpcodeInfo.getNumResults() << ", Dummy.Val, 0);\n" - << " Result = Dummy;\n" - << " return;\n" - << " }\n"; - } - - // Print all declarations. - for (std::set >::iterator - I = AllGenDecls.begin(), E = AllGenDecls.end(); I != E; ++I) - if (I->first == 0) - OS << " SDOperand " << I->second << "(0, 0);\n"; - else if (I->first == 1) - OS << " SDNode *" << I->second << " = NULL;\n"; - else - OS << " bool " << I->second << " = false;\n"; + // Replace the emission code within selection routines with calls to the + // emission functions. + CallerCode = "return Emit_" + utostr(EmitFuncNum) + CallerCode; + GeneratedCode.push_back(std::make_pair(false, CallerCode)); + } - // Loop through and reverse all of the CodeList vectors, as we will be - // accessing them from their logical front, but accessing the end of a - // vector is more efficient. - for (unsigned i = 0, e = CodeForPatterns.size(); i != e; ++i) { - CodeList &GeneratedCode = CodeForPatterns[i].second; - std::reverse(GeneratedCode.begin(), GeneratedCode.end()); - } + // Print function. + std::string OpVTStr = (OpVT != MVT::isVoid && OpVT != MVT::iPTR) + ? getEnumName(OpVT).substr(5) : "" ; + std::map >::iterator OpVTI = + OpcodeVTMap.find(OpName); + if (OpVTI == OpcodeVTMap.end()) { + std::vector VTSet; + VTSet.push_back(OpVTStr); + OpcodeVTMap.insert(std::make_pair(OpName, VTSet)); + } else + OpVTI->second.push_back(OpVTStr); + + OS << "SDNode *Select_" << OpName << (OpVTStr != "" ? "_" : "") + << OpVTStr << "(const SDOperand &N) {\n"; + + // Loop through and reverse all of the CodeList vectors, as we will be + // accessing them from their logical front, but accessing the end of a + // vector is more efficient. + for (unsigned i = 0, e = CodeForPatterns.size(); i != e; ++i) { + CodeList &GeneratedCode = CodeForPatterns[i].second; + std::reverse(GeneratedCode.begin(), GeneratedCode.end()); + } - // Next, reverse the list of patterns itself for the same reason. - std::reverse(CodeForPatterns.begin(), CodeForPatterns.end()); + // Next, reverse the list of patterns itself for the same reason. + std::reverse(CodeForPatterns.begin(), CodeForPatterns.end()); - // Emit all of the patterns now, grouped together to share code. - EmitPatterns(CodeForPatterns, 2, OS); + // Emit all of the patterns now, grouped together to share code. + EmitPatterns(CodeForPatterns, 2, OS); - // If the last pattern has predicates (which could fail) emit code to catch - // the case where nothing handles a pattern. - if (mightNotMatch) { - OS << " std::cerr << \"Cannot yet select: \";\n"; - if (OpcodeInfo.getEnumName() != "ISD::INTRINSIC_W_CHAIN" && - OpcodeInfo.getEnumName() != "ISD::INTRINSIC_WO_CHAIN" && - OpcodeInfo.getEnumName() != "ISD::INTRINSIC_VOID") { - OS << " N.Val->dump(CurDAG);\n"; - } else { - OS << " unsigned iid = cast(N.getOperand(" - "N.getOperand(0).getValueType() == MVT::Other))->getValue();\n" - << " std::cerr << \"intrinsic %\"<< " - "Intrinsic::getName((Intrinsic::ID)iid);\n"; + // If the last pattern has predicates (which could fail) emit code to + // catch the case where nothing handles a pattern. + if (mightNotMatch) { + OS << " std::cerr << \"Cannot yet select: \";\n"; + if (OpcodeInfo.getEnumName() != "ISD::INTRINSIC_W_CHAIN" && + OpcodeInfo.getEnumName() != "ISD::INTRINSIC_WO_CHAIN" && + OpcodeInfo.getEnumName() != "ISD::INTRINSIC_VOID") { + OS << " N.Val->dump(CurDAG);\n"; + } else { + OS << " unsigned iid = cast(N.getOperand(" + "N.getOperand(0).getValueType() == MVT::Other))->getValue();\n" + << " std::cerr << \"intrinsic %\"<< " + "Intrinsic::getName((Intrinsic::ID)iid);\n"; + } + OS << " std::cerr << '\\n';\n" + << " abort();\n" + << " return NULL;\n"; } - OS << " std::cerr << '\\n';\n" - << " abort();\n"; + OS << "}\n\n"; } - OS << "}\n\n"; } // Emit boilerplate. - OS << "void Select_INLINEASM(SDOperand& Result, SDOperand N) {\n" + OS << "SDNode *Select_INLINEASM(SDOperand N) {\n" << " std::vector Ops(N.Val->op_begin(), N.Val->op_end());\n" - << " Select(Ops[0], N.getOperand(0)); // Select the chain.\n\n" + << " AddToISelQueue(N.getOperand(0)); // Select the chain.\n\n" << " // Select the flag operand.\n" << " if (Ops.back().getValueType() == MVT::Flag)\n" - << " Select(Ops.back(), Ops.back());\n" + << " AddToISelQueue(Ops.back());\n" << " SelectInlineAsmMemoryOperands(Ops, *CurDAG);\n" << " std::vector VTs;\n" << " VTs.push_back(MVT::Other);\n" << " VTs.push_back(MVT::Flag);\n" - << " SDOperand New = CurDAG->getNode(ISD::INLINEASM, VTs, Ops);\n" - << " SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, 0, New.Val, 0);\n" - << " SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, 1, New.Val, 1);\n" - << " Result = New.getValue(N.ResNo);\n" - << " return;\n" + << " SDOperand New = CurDAG->getNode(ISD::INLINEASM, VTs, &Ops[0], " + "Ops.size());\n" + << " return New.Val;\n" << "}\n\n"; OS << "// The main instruction selector code.\n" - << "void SelectCode(SDOperand &Result, SDOperand N) {\n" + << "SDNode *SelectCode(SDOperand N) {\n" << " if (N.getOpcode() >= ISD::BUILTIN_OP_END &&\n" << " N.getOpcode() < (ISD::BUILTIN_OP_END+" << InstNS << "INSTRUCTION_LIST_END)) {\n" - << " Result = N;\n" - << " return; // Already selected.\n" - << " }\n\n" - << " std::map::iterator CGMI = CodeGenMap.find(N);\n" - << " if (CGMI != CodeGenMap.end()) {\n" - << " Result = CGMI->second;\n" - << " return;\n" + << " return NULL; // Already selected.\n" << " }\n\n" << " switch (N.getOpcode()) {\n" << " default: break;\n" @@ -3444,104 +3579,22 @@ void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) { << " case ISD::TargetFrameIndex:\n" << " case ISD::TargetJumpTable:\n" << " case ISD::TargetGlobalAddress: {\n" - << " Result = N;\n" - << " return;\n" + << " return NULL;\n" << " }\n" << " case ISD::AssertSext:\n" << " case ISD::AssertZext: {\n" - << " SDOperand Tmp0;\n" - << " Select(Tmp0, N.getOperand(0));\n" - << " if (!N.Val->hasOneUse())\n" - << " SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, N.ResNo, " - << "Tmp0.Val, Tmp0.ResNo);\n" - << " Result = Tmp0;\n" - << " return;\n" + << " AddToISelQueue(N.getOperand(0));\n" + << " ReplaceUses(N, N.getOperand(0));\n" + << " return NULL;\n" << " }\n" << " case ISD::TokenFactor:\n" - << " if (N.getNumOperands() == 2) {\n" - << " SDOperand Op0, Op1;\n" - << " Select(Op0, N.getOperand(0));\n" - << " Select(Op1, N.getOperand(1));\n" - << " Result = \n" - << " CurDAG->getNode(ISD::TokenFactor, MVT::Other, Op0, Op1);\n" - << " SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, N.ResNo, " - << "Result.Val, Result.ResNo);\n" - << " } else {\n" - << " std::vector Ops;\n" - << " for (unsigned i = 0, e = N.getNumOperands(); i != e; ++i) {\n" - << " SDOperand Val;\n" - << " Select(Val, N.getOperand(i));\n" - << " Ops.push_back(Val);\n" - << " }\n" - << " Result = \n" - << " CurDAG->getNode(ISD::TokenFactor, MVT::Other, Ops);\n" - << " SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, N.ResNo, " - << "Result.Val, Result.ResNo);\n" - << " }\n" - << " return;\n" - << " case ISD::CopyFromReg: {\n" - << " SDOperand Chain;\n" - << " Select(Chain, N.getOperand(0));\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)) {\n" - << " Result = N; // No change\n" - << " return;\n" - << " }\n" - << " SDOperand New = CurDAG->getCopyFromReg(Chain, Reg, VT);\n" - << " SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, 0, " - << "New.Val, 0);\n" - << " SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, 1, " - << "New.Val, 1);\n" - << " Result = New.getValue(N.ResNo);\n" - << " return;\n" - << " } else {\n" - << " SDOperand Flag;\n" - << " if (N.getNumOperands() == 3) Select(Flag, N.getOperand(2));\n" - << " if (Chain == N.getOperand(0) &&\n" - << " (N.getNumOperands() == 2 || Flag == N.getOperand(2))) {\n" - << " Result = N; // No change\n" - << " return;\n" - << " }\n" - << " SDOperand New = CurDAG->getCopyFromReg(Chain, Reg, VT, Flag);\n" - << " SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, 0, " - << "New.Val, 0);\n" - << " SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, 1, " - << "New.Val, 1);\n" - << " SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, 2, " - << "New.Val, 2);\n" - << " Result = New.getValue(N.ResNo);\n" - << " return;\n" - << " }\n" - << " }\n" + << " case ISD::CopyFromReg:\n" << " case ISD::CopyToReg: {\n" - << " SDOperand Chain;\n" - << " Select(Chain, N.getOperand(0));\n" - << " unsigned Reg = cast(N.getOperand(1))->getReg();\n" - << " SDOperand Val;\n" - << " Select(Val, N.getOperand(2));\n" - << " 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" - << " SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, 0, " - << "Result.Val, 0);\n" - << " } else {\n" - << " SDOperand Flag(0, 0);\n" - << " if (N.getNumOperands() == 4) Select(Flag, 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" - << " SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, 0, " - << "Result.Val, 0);\n" - << " SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, 1, " - << "Result.Val, 1);\n" - << " Result = Result.getValue(N.ResNo);\n" - << " }\n" - << " return;\n" + << " for (unsigned i = 0, e = N.getNumOperands(); i != e; ++i)\n" + << " AddToISelQueue(N.getOperand(i));\n" + << " return NULL;\n" << " }\n" - << " case ISD::INLINEASM: Select_INLINEASM(Result, N); return;\n"; + << " case ISD::INLINEASM: return Select_INLINEASM(N);\n"; // Loop over all of the case statements, emiting a call to each method we @@ -3550,9 +3603,48 @@ void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) { CompareByRecordName>::iterator PBOI = PatternsByOpcode.begin(), E = PatternsByOpcode.end(); PBOI != E; ++PBOI) { const SDNodeInfo &OpcodeInfo = getSDNodeInfo(PBOI->first); - OS << " case " << OpcodeInfo.getEnumName() << ": " - << std::string(std::max(0, int(24-OpcodeInfo.getEnumName().size())), ' ') - << "Select_" << PBOI->first->getName() << "(Result, N); return;\n"; + const std::string &OpName = PBOI->first->getName(); + // Potentially multiple versions of select for this opcode. One for each + // ValueType of the node (or its first true operand if it doesn't produce a + // result. + std::map >::iterator OpVTI = + OpcodeVTMap.find(OpName); + std::vector &OpVTs = OpVTI->second; + OS << " case " << OpcodeInfo.getEnumName() << ": {\n"; + if (OpVTs.size() == 1) { + std::string &VTStr = OpVTs[0]; + OS << " return Select_" << OpName + << (VTStr != "" ? "_" : "") << VTStr << "(N);\n"; + } else { + if (OpcodeInfo.getNumResults()) + OS << " MVT::ValueType NVT = N.Val->getValueType(0);\n"; + else if (OpcodeInfo.hasProperty(SDNPHasChain)) + OS << " MVT::ValueType NVT = (N.getNumOperands() > 1) ?" + << " N.getOperand(1).Val->getValueType(0) : MVT::isVoid;\n"; + else + OS << " MVT::ValueType NVT = (N.getNumOperands() > 0) ?" + << " N.getOperand(0).Val->getValueType(0) : MVT::isVoid;\n"; + int Default = -1; + OS << " switch (NVT) {\n"; + for (unsigned i = 0, e = OpVTs.size(); i < e; ++i) { + std::string &VTStr = OpVTs[i]; + if (VTStr == "") { + Default = i; + continue; + } + OS << " case MVT::" << VTStr << ":\n" + << " return Select_" << OpName + << "_" << VTStr << "(N);\n"; + } + OS << " default:\n"; + if (Default != -1) + OS << " return Select_" << OpName << "(N);\n"; + else + OS << " break;\n"; + OS << " }\n"; + OS << " break;\n"; + } + OS << " }\n"; } OS << " } // end of big switch.\n\n" @@ -3569,6 +3661,7 @@ void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) { << " }\n" << " std::cerr << '\\n';\n" << " abort();\n" + << " return NULL;\n" << "}\n"; } @@ -3580,84 +3673,123 @@ void DAGISelEmitter::run(std::ostream &OS) { << "// *** instruction selector class. These functions are really " << "methods.\n\n"; - OS << "#if defined(__GNUC__) && \\\n"; - OS << " ((__GNUC__ > 3) || ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 4)))\n"; - OS << "#define NOINLINE __attribute__((noinline))\n"; - OS << "#endif\n\n"; - - OS << "// Instance var to keep track of multiply used nodes that have \n" - << "// already been selected.\n" - << "std::map CodeGenMap;\n"; - - OS << "// Instance var to keep track of mapping of chain generating nodes\n" - << "// and their place handle nodes.\n"; - OS << "std::map HandleMap;\n"; - OS << "// Instance var to keep track of mapping of place handle nodes\n" - << "// and their replacement nodes.\n"; - OS << "std::map ReplaceMap;\n"; - - OS << "\n"; - OS << "// AddHandleReplacement - Note the pending replacement node for a\n" - << "// handle node in ReplaceMap.\n"; - OS << "void AddHandleReplacement(SDNode *H, unsigned HNum, SDNode *R, " - << "unsigned RNum) {\n"; - OS << " SDOperand N(H, HNum);\n"; - OS << " std::map::iterator HMI = HandleMap.find(N);\n"; - OS << " if (HMI != HandleMap.end()) {\n"; - OS << " ReplaceMap[HMI->second] = SDOperand(R, RNum);\n"; - OS << " HandleMap.erase(N);\n"; + OS << "#include \"llvm/Support/Compiler.h\"\n"; + + OS << "// Instruction selector priority queue:\n" + << "std::vector ISelQueue;\n"; + OS << "/// Keep track of nodes which have already been added to queue.\n" + << "unsigned char *ISelQueued;\n"; + OS << "/// Keep track of nodes which have already been selected.\n" + << "unsigned char *ISelSelected;\n"; + OS << "/// Dummy parameter to ReplaceAllUsesOfValueWith().\n" + << "std::vector ISelKilled;\n\n"; + + OS << "/// IsChainCompatible - Returns true if Chain is Op or Chain does\n"; + OS << "/// not reach Op.\n"; + OS << "static bool IsChainCompatible(SDNode *Chain, SDNode *Op) {\n"; + OS << " if (Chain->getOpcode() == ISD::EntryToken)\n"; + OS << " return true;\n"; + OS << " else if (Chain->getOpcode() == ISD::TokenFactor)\n"; + OS << " return false;\n"; + OS << " else if (Chain->getNumOperands() > 0) {\n"; + OS << " SDOperand C0 = Chain->getOperand(0);\n"; + OS << " if (C0.getValueType() == MVT::Other)\n"; + OS << " return C0.Val != Op && IsChainCompatible(C0.Val, Op);\n"; OS << " }\n"; + OS << " return true;\n"; OS << "}\n"; - OS << "\n"; - OS << "// SelectDanglingHandles - Select replacements for all `dangling`\n"; - OS << "// handles.Some handles do not yet have replacements because the\n"; - OS << "// nodes they replacements have only dead readers.\n"; - OS << "void SelectDanglingHandles() {\n"; - OS << " for (std::map::iterator I = " - << "HandleMap.begin(),\n" - << " E = HandleMap.end(); I != E; ++I) {\n"; - OS << " SDOperand N = I->first;\n"; - OS << " SDOperand R;\n"; - OS << " Select(R, N.getValue(0));\n"; - OS << " AddHandleReplacement(N.Val, N.ResNo, R.Val, R.ResNo);\n"; + OS << "/// Sorting functions for the selection queue.\n" + << "struct isel_sort : public std::binary_function" + << " {\n" + << " bool operator()(const SDNode* left, const SDNode* right) " + << "const {\n" + << " return (left->getNodeId() > right->getNodeId());\n" + << " }\n" + << "};\n\n"; + + OS << "inline void setQueued(int Id) {\n"; + OS << " ISelQueued[Id / 8] |= 1 << (Id % 8);\n"; + OS << "}\n"; + OS << "inline bool isQueued(int Id) {\n"; + OS << " return ISelQueued[Id / 8] & (1 << (Id % 8));\n"; + OS << "}\n"; + OS << "inline void setSelected(int Id) {\n"; + OS << " ISelSelected[Id / 8] |= 1 << (Id % 8);\n"; + OS << "}\n"; + OS << "inline bool isSelected(int Id) {\n"; + OS << " return ISelSelected[Id / 8] & (1 << (Id % 8));\n"; + OS << "}\n\n"; + + OS << "void AddToISelQueue(SDOperand N) DISABLE_INLINE {\n"; + OS << " int Id = N.Val->getNodeId();\n"; + OS << " if (Id != -1 && !isQueued(Id)) {\n"; + OS << " ISelQueue.push_back(N.Val);\n"; + OS << " std::push_heap(ISelQueue.begin(), ISelQueue.end(), isel_sort());\n"; + OS << " setQueued(Id);\n"; + OS << " }\n"; + OS << "}\n\n"; + + OS << "inline void RemoveKilled() {\n"; +OS << " unsigned NumKilled = ISelKilled.size();\n"; + OS << " if (NumKilled) {\n"; + OS << " for (unsigned i = 0; i != NumKilled; ++i) {\n"; + OS << " SDNode *Temp = ISelKilled[i];\n"; + OS << " ISelQueue.erase(std::remove(ISelQueue.begin(), ISelQueue.end(), " + << "Temp), ISelQueue.end());\n"; + OS << " };\n"; + OS << " std::make_heap(ISelQueue.begin(), ISelQueue.end(), isel_sort());\n"; + OS << " ISelKilled.clear();\n"; OS << " }\n"; + OS << "}\n\n"; + + OS << "void ReplaceUses(SDOperand F, SDOperand T) DISABLE_INLINE {\n"; + OS << " CurDAG->ReplaceAllUsesOfValueWith(F, T, ISelKilled);\n"; + OS << " setSelected(F.Val->getNodeId());\n"; + OS << " RemoveKilled();\n"; OS << "}\n"; + OS << "inline void ReplaceUses(SDNode *F, SDNode *T) {\n"; + OS << " CurDAG->ReplaceAllUsesWith(F, T, &ISelKilled);\n"; + OS << " setSelected(F->getNodeId());\n"; + OS << " RemoveKilled();\n"; + OS << "}\n\n"; + + OS << "// SelectRoot - Top level entry to DAG isel.\n"; + OS << "SDOperand SelectRoot(SDOperand Root) {\n"; + OS << " SelectRootInit();\n"; + OS << " unsigned NumBytes = (DAGSize + 7) / 8;\n"; + OS << " ISelQueued = new unsigned char[NumBytes];\n"; + OS << " ISelSelected = new unsigned char[NumBytes];\n"; + OS << " memset(ISelQueued, 0, NumBytes);\n"; + OS << " memset(ISelSelected, 0, NumBytes);\n"; OS << "\n"; - OS << "// ReplaceHandles - Replace all the handles with the real target\n"; - OS << "// specific nodes.\n"; - OS << "void ReplaceHandles() {\n"; - OS << " for (std::map::iterator I = " - << "ReplaceMap.begin(),\n" - << " E = ReplaceMap.end(); I != E; ++I) {\n"; - OS << " SDOperand From = I->first;\n"; - OS << " SDOperand To = I->second;\n"; - OS << " for (SDNode::use_iterator UI = From.Val->use_begin(), " - << "E = From.Val->use_end(); UI != E; ++UI) {\n"; - OS << " SDNode *Use = *UI;\n"; - OS << " std::vector Ops;\n"; - OS << " for (unsigned i = 0, e = Use->getNumOperands(); i != e; ++i){\n"; - OS << " SDOperand O = Use->getOperand(i);\n"; - OS << " if (O.Val == From.Val)\n"; - OS << " Ops.push_back(To);\n"; - OS << " else\n"; - OS << " Ops.push_back(O);\n"; + OS << " // Create a dummy node (which is not added to allnodes), that adds\n" + << " // a reference to the root node, preventing it from being deleted,\n" + << " // and tracking any changes of the root.\n" + << " HandleSDNode Dummy(CurDAG->getRoot());\n" + << " ISelQueue.push_back(CurDAG->getRoot().Val);\n"; + OS << " while (!ISelQueue.empty()) {\n"; + OS << " SDNode *Node = ISelQueue.front();\n"; + OS << " std::pop_heap(ISelQueue.begin(), ISelQueue.end(), isel_sort());\n"; + OS << " ISelQueue.pop_back();\n"; + OS << " if (!isSelected(Node->getNodeId())) {\n"; + OS << " SDNode *ResNode = Select(SDOperand(Node, 0));\n"; + OS << " if (ResNode != Node) {\n"; + OS << " if (ResNode)\n"; + OS << " ReplaceUses(Node, ResNode);\n"; + OS << " if (Node->use_empty()) { // Don't delete EntryToken, etc.\n"; + OS << " CurDAG->RemoveDeadNode(Node, ISelKilled);\n"; + OS << " RemoveKilled();\n"; + OS << " }\n"; OS << " }\n"; - OS << " SDOperand U = SDOperand(Use, 0);\n"; - OS << " CurDAG->UpdateNodeOperands(U, Ops);\n"; OS << " }\n"; OS << " }\n"; - OS << "}\n"; - OS << "\n"; - OS << "// SelectRoot - Top level entry to DAG isel.\n"; - OS << "SDOperand SelectRoot(SDOperand N) {\n"; - OS << " SDOperand ResNode;\n"; - OS << " Select(ResNode, N);\n"; - OS << " SelectDanglingHandles();\n"; - OS << " ReplaceHandles();\n"; - OS << " ReplaceMap.clear();\n"; - OS << " return ResNode;\n"; + OS << " delete[] ISelQueued;\n"; + OS << " ISelQueued = NULL;\n"; + OS << " delete[] ISelSelected;\n"; + OS << " ISelSelected = NULL;\n"; + OS << " return Dummy.getValue();\n"; OS << "}\n"; Intrinsics = LoadIntrinsics(Records);