X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=utils%2FTableGen%2FDAGISelEmitter.cpp;h=39480c966404a92f0e5006fa5ba3baf97e756c03;hb=9ec4849ff6cd771f53a1340aa6383702b7a6bb98;hp=b4317ff4fa58022aa023ca78a76f9c03009fcca3;hpb=61a0209a8ac7b55a40f291f30679f16b3eb1d83c;p=oota-llvm.git diff --git a/utils/TableGen/DAGISelEmitter.cpp b/utils/TableGen/DAGISelEmitter.cpp index b4317ff4fa5..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; @@ -121,6 +122,13 @@ TreePatternNode *SDTypeConstraint::getOperandNum(unsigned OpNo, assert(NumResults <= 1 && "We only work with nodes with zero or one result so far!"); + if (OpNo >= (NumResults + N->getNumChildren())) { + std::cerr << "Invalid operand number " << OpNo << " "; + N->dump(); + std::cerr << '\n'; + exit(1); + } + if (OpNo < NumResults) return N; // FIXME: need value # else @@ -138,7 +146,7 @@ bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, assert(NumResults <= 1 && "We only work with nodes with zero or one result so far!"); - // Check that the number of operands is sane. + // Check that the number of operands is sane. Negative operands -> varargs. if (NodeInfo.getNumOperands() >= 0) { if (N->getNumChildren() != (unsigned)NodeInfo.getNumOperands()) TP.error(N->getOperator()->getName() + " node requires exactly " + @@ -156,7 +164,7 @@ bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, return NodeToApply->UpdateNodeType(x.SDTCisVT_Info.VT, TP); case SDTCisPtrTy: { // Operand must be same as target pointer type. - return NodeToApply->UpdateNodeType(CGT.getPointerType(), TP); + return NodeToApply->UpdateNodeType(MVT::iPTR, TP); } case SDTCisInt: { // If there is only one integer type supported, this must be it. @@ -346,6 +354,18 @@ bool TreePatternNode::UpdateNodeType(const std::vector &ExtVTs, setTypes(ExtVTs); return true; } + + if (getExtTypeNum(0) == MVT::iPTR) { + if (ExtVTs[0] == MVT::iPTR || ExtVTs[0] == MVT::isInt) + return false; + if (isExtIntegerInVTs(ExtVTs)) { + std::vector FVTs = FilterEVTs(ExtVTs, MVT::isInteger); + if (FVTs.size()) { + setTypes(ExtVTs); + return true; + } + } + } if (ExtVTs[0] == MVT::isInt && isExtIntegerInVTs(getExtTypes())) { assert(hasTypeSet() && "should be handled above!"); @@ -355,6 +375,16 @@ bool TreePatternNode::UpdateNodeType(const std::vector &ExtVTs, setTypes(FVTs); return true; } + if (ExtVTs[0] == MVT::iPTR && isExtIntegerInVTs(getExtTypes())) { + //assert(hasTypeSet() && "should be handled above!"); + std::vector FVTs = FilterEVTs(getExtTypes(), MVT::isInteger); + if (getExtTypes() == FVTs) + return false; + if (FVTs.size()) { + setTypes(FVTs); + return true; + } + } if (ExtVTs[0] == MVT::isFP && isExtFloatingPointInVTs(getExtTypes())) { assert(hasTypeSet() && "should be handled above!"); std::vector FVTs = @@ -374,7 +404,11 @@ bool TreePatternNode::UpdateNodeType(const std::vector &ExtVTs, (getExtTypeNum(0) == MVT::isFP && isExtFloatingPointInVTs(ExtVTs))) { setTypes(ExtVTs); return true; - } + } + if (getExtTypeNum(0) == MVT::isInt && ExtVTs[0] == MVT::iPTR) { + setTypes(ExtVTs); + return true; + } if (isLeaf()) { dump(); @@ -402,7 +436,15 @@ void TreePatternNode::print(std::ostream &OS) const { case MVT::isInt: OS << ":isInt"; break; case MVT::isFP : OS << ":isFP"; break; case MVT::isUnknown: ; /*OS << ":?";*/ break; - default: OS << ":" << getTypeNum(0); break; + case MVT::iPTR: OS << ":iPTR"; break; + default: { + std::string VTName = llvm::getName(getTypeNum(0)); + // Strip off MVT:: prefix if present. + if (VTName.substr(0,5) == "MVT::") + VTName = VTName.substr(5); + OS << ":" << VTName; + break; + } } if (!isLeaf()) { @@ -565,12 +607,8 @@ static std::vector getImplicitType(Record *R, bool NotRegisters, } else if (R->isSubClassOf("Register")) { if (NotRegisters) return Unknown; - // If the register appears in exactly one regclass, and the regclass has one - // value type, use it as the known type. const CodeGenTarget &T = TP.getDAGISelEmitter().getTargetInfo(); - if (const CodeGenRegisterClass *RC = T.getRegisterClassForRegister(R)) - return ConvertVTs(RC->getValueTypes()); - return Unknown; + return T.getRegisterVTs(R); } else if (R->isSubClassOf("ValueType") || R->isSubClassOf("CondCode")) { // Using a VTSDNode or CondCodeSDNode. return Other; @@ -607,16 +645,22 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { // At some point, it may make sense for this tree pattern to have // multiple types. Assert here that it does not, so we revisit this // code when appropriate. - assert(getExtTypes().size() == 1 && "TreePattern has too many types!"); + assert(getExtTypes().size() >= 1 && "TreePattern doesn't have a type!"); + MVT::ValueType VT = getTypeNum(0); + for (unsigned i = 1, e = getExtTypes().size(); i != e; ++i) + assert(getTypeNum(i) == VT && "TreePattern has too many types!"); - unsigned Size = MVT::getSizeInBits(getTypeNum(0)); - // Make sure that the value is representable for this type. - if (Size < 32) { - int Val = (II->getValue() << (32-Size)) >> (32-Size); - if (Val != II->getValue()) - TP.error("Sign-extended integer value '" + itostr(II->getValue()) + - "' is out of range for type 'MVT::" + - getEnumName(getTypeNum(0)) + "'!"); + VT = getTypeNum(0); + if (VT != MVT::iPTR) { + unsigned Size = MVT::getSizeInBits(VT); + // Make sure that the value is representable for this type. + if (Size < 32) { + int Val = (II->getValue() << (32-Size)) >> (32-Size); + if (Val != II->getValue()) + TP.error("Sign-extended integer value '" + itostr(II->getValue())+ + "' is out of range for type '" + + getEnumName(getTypeNum(0)) + "'!"); + } } } @@ -653,8 +697,7 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { utostr(getNumChildren()-1) + " operands!"); // Apply type info to the intrinsic ID. - MVT::ValueType PtrTy = ISE.getTargetInfo().getPointerType(); - MadeChange |= getChild(0)->UpdateNodeType(PtrTy, TP); + MadeChange |= getChild(0)->UpdateNodeType(MVT::iPTR, TP); for (unsigned i = 1, e = getNumChildren(); i != e; ++i) { MVT::ValueType OpVT = Int.ArgVTs[i]; @@ -700,8 +743,11 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { assert(NumResults <= 1 && "Only supports zero or one result instrs!"); + + CodeGenInstruction &InstInfo = + ISE.getTargetInfo().getInstruction(getOperator()->getName()); // Apply the result type to the node - if (NumResults == 0) { + if (NumResults == 0 || InstInfo.noResults) { // FIXME: temporary hack... MadeChange = UpdateNodeType(MVT::isVoid, TP); } else { Record *ResultNode = Inst.getResult(0); @@ -723,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")) { @@ -756,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 @@ -778,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; @@ -1111,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()); } @@ -1519,22 +1580,6 @@ void DAGISelEmitter::ParsePatterns() { // Inline pattern fragments into it. Pattern->InlinePatternFragments(); - // 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. - if (!Pattern->InferAllTypes()) - Pattern->error("Could not infer all types in pattern!"); - - // Validate that the input pattern is correct. - { - std::map InstInputs; - std::map InstResults; - std::vector InstImpInputs; - std::vector InstImpResults; - FindPatternInputsAndOutputs(Pattern, Pattern->getOnlyTree(), - InstInputs, InstResults, - InstImpInputs, InstImpResults); - } - ListInit *LI = Patterns[i]->getValueAsListInit("ResultInstrs"); if (LI->getSize() == 0) continue; // no pattern. @@ -1543,15 +1588,49 @@ void DAGISelEmitter::ParsePatterns() { // Inline pattern fragments into it. Result->InlinePatternFragments(); - - // 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. - if (!Result->InferAllTypes()) - Result->error("Could not infer all types in pattern result!"); - + if (Result->getNumTrees() != 1) Result->error("Cannot handle instructions producing instructions " "with temporaries yet!"); + + bool IterateInference; + bool InferredAllPatternTypes, InferredAllResultTypes; + do { + // 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. + 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. + InferredAllResultTypes = Result->InferAllTypes(); + + // Apply the type of the result to the source pattern. This helps us + // resolve cases where the input type is known to be a pointer type (which + // is considered resolved), but the result knows it needs to be 32- or + // 64-bits. Infer the other way for good measure. + IterateInference = Pattern->getOnlyTree()-> + UpdateNodeType(Result->getOnlyTree()->getExtTypes(), *Result); + IterateInference |= Result->getOnlyTree()-> + UpdateNodeType(Pattern->getOnlyTree()->getExtTypes(), *Result); + } while (IterateInference); + + // Verify that we inferred enough types that we can do something with the + // pattern and result. If these fire the user has to add type casts. + if (!InferredAllPatternTypes) + Pattern->error("Could not infer all types in pattern!"); + if (!InferredAllResultTypes) + Result->error("Could not infer all types in pattern result!"); + + // Validate that the input pattern is correct. + { + std::map InstInputs; + std::map InstResults; + std::vector InstImpInputs; + std::vector InstImpResults; + FindPatternInputsAndOutputs(Pattern, Pattern->getOnlyTree(), + InstInputs, InstResults, + InstImpInputs, InstImpResults); + } // Promote the xform function to be an explicit node if set. std::vector ResultNodeOperands; @@ -1703,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); @@ -1764,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); } } @@ -1833,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) @@ -1863,16 +1954,17 @@ static const ComplexPattern *NodeGetComplexPattern(TreePatternNode *N, /// patterns before small ones. This is used to determine the size of a /// pattern. static unsigned getPatternSize(TreePatternNode *P, DAGISelEmitter &ISE) { - assert(isExtIntegerInVTs(P->getExtTypes()) || - isExtFloatingPointInVTs(P->getExtTypes()) || - P->getExtTypeNum(0) == MVT::isVoid || - P->getExtTypeNum(0) == MVT::Flag && + assert((isExtIntegerInVTs(P->getExtTypes()) || + isExtFloatingPointInVTs(P->getExtTypes()) || + P->getExtTypeNum(0) == MVT::isVoid || + 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. @@ -1881,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. @@ -1895,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()) @@ -1925,6 +2017,21 @@ static unsigned getResultPatternCost(TreePatternNode *P, DAGISelEmitter &ISE) { return Cost; } +/// getResultPatternCodeSize - Compute the code size of instructions for this +/// pattern. +static unsigned getResultPatternSize(TreePatternNode *P, DAGISelEmitter &ISE) { + if (P->isLeaf()) return 0; + + unsigned Cost = 0; + Record *Op = P->getOperator(); + if (Op->isSubClassOf("Instruction")) { + Cost += Op->getValueAsInt("CodeSize"); + } + for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) + Cost += getResultPatternSize(P->getChild(i), ISE); + return Cost; +} + // PatternSortingPredicate - return true if we prefer to match LHS before RHS. // In particular, we want to match maximal patterns first and lowest cost within // a particular complexity first. @@ -1942,8 +2049,13 @@ struct PatternSortingPredicate { if (LHSSize < RHSSize) return false; // If the patterns have equal complexity, compare generated instruction cost - return getResultPatternCost(LHS->getDstPattern(), ISE) < - getResultPatternCost(RHS->getDstPattern(), ISE); + unsigned LHSCost = getResultPatternCost(LHS->getDstPattern(), ISE); + unsigned RHSCost = getResultPatternCost(RHS->getDstPattern(), ISE); + if (LHSCost < RHSCost) return true; + if (LHSCost > RHSCost) return false; + + return getResultPatternSize(LHS->getDstPattern(), ISE) < + getResultPatternSize(RHS->getDstPattern(), ISE); } }; @@ -1976,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; @@ -1987,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)) @@ -2021,52 +2138,70 @@ 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; - /// These nodes are being marked "in-flight" so they cannot be folded. - std::vector InflightNodes; - /// 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 NewTF; - 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, bool isSDNode=false) { + void emitDecl(const std::string &S) { assert(!S.empty() && "Invalid declaration"); - GeneratedDecl.insert(std::make_pair(isSDNode, S)); + GeneratedDecl.insert(S); + } + void emitOpcode(const std::string &Opc) { + TargetOpcodes.push_back(Opc); + OpcNo++; + } + void emitVT(const std::string &VT) { + TargetVTs.push_back(VT); + VTNo++; } public: PatternCodeEmitter(DAGISelEmitter &ise, ListInit *preds, TreePatternNode *pattern, TreePatternNode *instr, - std::vector > &gc, - std::set > &gd, - bool dorep) + std::vector > &gc, + std::set &gd, + std::vector &to, + std::vector &tv) : ISE(ise), Predicates(preds), Pattern(pattern), Instruction(instr), GeneratedCode(gc), GeneratedDecl(gd), - NewTF(false), DoReplace(dorep), TmpNo(0) {} + 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) { @@ -2075,11 +2210,13 @@ public: if (DefInit *Pred = dynamic_cast(Predicates->getElement(i))) { Record *Def = Pred->getDef(); if (!Def->isSubClassOf("Predicate")) { +#ifndef NDEBUG Def->dump(); +#endif assert(0 && "Unknown predicate type!"); } if (!PredicateCheck.empty()) - PredicateCheck += " || "; + PredicateCheck += " && "; PredicateCheck += "(" + Def->getValueAsString("CondString") + ")"; } } @@ -2120,48 +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()); - // Not in flight? - emitCheck("(FoldNodeInFlight || InFlightSet.count(" - + RootName + ".Val) == 0)"); // 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 @@ -2175,36 +2281,40 @@ 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)) - if (PInfo.getNumOperands() > 1) { - emitCheck("!isNonImmUse(" + ParentName + ".Val, " + RootName + - ".Val)"); - } else { - emitCheck("(" + ParentName + ".getNumOperands() == 1 || !" + - "isNonImmUse(" + ParentName + ".Val, " + RootName + - ".Val))"); - } + 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, N.Val)"); + } } } if (NodeHasChain) { - ChainName = "Chain" + ChainSuffix; - emitDecl(ChainName); if (FoundChain) { - // FIXME: temporary workaround for a common case where chain - // is a TokenFactor and the previous "inner" chain is an operand. - NewTF = true; - emitDecl("OldTF", true); - emitCheck("(" + ChainName + " = UpdateFoldedChain(CurDAG, " + - RootName + ".Val, Chain.Val, OldTF)).Val"); - } else { + emitCheck("(" + ChainName + ".Val == " + RootName + ".Val || " + "IsChainCompatible(" + ChainName + ".Val, " + + RootName + ".Val))"); + OrigChains.push_back(std::make_pair(ChainName, RootName)); + } else FoundChain = true; - emitCode(ChainName + " = " + RootName + ".getOperand(0);"); - } + ChainName = "Chain" + ChainSuffix; + emitInit("SDOperand " + ChainName + " = " + RootName + + ".getOperand(0);"); } } @@ -2214,105 +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 { - Child->dump(); - std::cerr << " "; - 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()]; @@ -2320,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; @@ -2337,108 +2546,100 @@ public: case MVT::i32: CastType = "unsigned"; break; case MVT::i64: CastType = "uint64_t"; break; } - emitCode(CastType + " Tmp" + utostr(ResNo) + "C = (" + CastType + - ")cast(" + Val + ")->getValue();"); - emitDecl("Tmp" + utostr(ResNo)); - emitCode("Tmp" + utostr(ResNo) + - " = CurDAG->getTargetConstant(Tmp" + utostr(ResNo) + - "C, MVT::" + getEnumName(N->getTypeNum(0)) + ");"); + 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(), MVT::" + + 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(), MVT::" + getEnumName(N->getTypeNum(0)) + + ")->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("Tmp" + utostr(i+ResNo)); - - std::string Code = Fn + "(" + Val; - for (unsigned i = 0; i < NumRes; i++) - Code += ", Tmp" + utostr(i + ResNo); - emitCheck(Code + ")"); - - for (unsigned i = 0; i < NumRes; ++i) { - emitCode("InFlightSet.insert(Tmp" + utostr(i+ResNo) + ".Val);"); - InflightNodes.push_back("Tmp" + utostr(i+ResNo)); + for (unsigned i = 0; i < CP->getNumOperands(); ++i) { + emitCode("AddToISelQueue(CPTmp" + utostr(i) + ");"); + NodeOps.push_back("CPTmp" + utostr(i)); } - for (unsigned i = 0; i < NumRes; ++i) - emitCode("Select(Tmp" + utostr(i+ResNo) + ", Tmp" + - utostr(i+ResNo) + ");"); - - 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(" + - ISE.getQualifiedName(DI->getDef()) + ", MVT::" + + 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()) + - ", MVT::" + getEnumName(N->getTypeNum(0)) + ");"); - return std::make_pair(1, ResNo); + ", " + getEnumName(N->getTypeNum(0)) + ");"); + 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(); @@ -2446,23 +2647,33 @@ public: const CodeGenTarget &CGT = ISE.getTargetInfo(); CodeGenInstruction &II = CGT.getInstruction(Op->getName()); const DAGInstruction &Inst = ISE.getInstruction(Op); - bool HasImpInputs = Inst.getNumImpOperands() > 0; - bool HasImpResults = Inst.getNumImpResults() > 0; - bool HasOptInFlag = isRoot && - PatternHasProperty(Pattern, SDNodeInfo::SDNPOptInFlag, ISE); - bool HasInFlag = isRoot && - PatternHasProperty(Pattern, SDNodeInfo::SDNPInFlag, ISE); - bool NodeHasOutFlag = HasImpResults || - (isRoot && PatternHasProperty(Pattern, SDNodeInfo::SDNPOutFlag, ISE)); - bool NodeHasChain = - NodeHasProperty(Pattern, SDNodeInfo::SDNPHasChain, ISE); - bool HasChain = II.hasCtrlDep || - (isRoot && PatternHasProperty(Pattern, SDNodeInfo::SDNPHasChain, ISE)); - - if (HasInFlag || NodeHasOutFlag || HasOptInFlag || HasImpInputs) - emitDecl("InFlag"); - if (HasOptInFlag) - emitCode("bool HasOptInFlag = false;"); + TreePattern *InstPat = Inst.getPattern(); + TreePatternNode *InstPatNode = + isRoot ? (InstPat ? InstPat->getOnlyTree() : Pattern) + : (InstPat ? InstPat->getOnlyTree() : NULL); + if (InstPatNode && InstPatNode->getOperator()->getName() == "set") { + InstPatNode = InstPatNode->getChild(1); + } + bool HasVarOps = isRoot && II.hasVariableNumberOfOperands; + bool HasImpInputs = isRoot && Inst.getNumImpOperands() > 0; + bool HasImpResults = isRoot && Inst.getNumImpResults() > 0; + bool NodeHasOptInFlag = isRoot && + PatternHasProperty(Pattern, SDNPOptInFlag, ISE); + bool NodeHasInFlag = isRoot && + PatternHasProperty(Pattern, SDNPInFlag, ISE); + bool NodeHasOutFlag = HasImpResults || (isRoot && + PatternHasProperty(Pattern, SDNPOutFlag, ISE)); + bool NodeHasChain = InstPatNode && + PatternHasProperty(InstPatNode, SDNPHasChain, ISE); + bool InputHasChain = isRoot && + NodeHasProperty(Pattern, SDNPHasChain, ISE); + + if (NodeHasOptInFlag) { + emitCode("bool HasInFlag = " + "(N.getOperand(N.getNumOperands()-1).getValueType() == MVT::Flag);"); + } + if (HasVarOps) + emitCode("SmallVector Ops" + utostr(OpcNo) + ";"); // How many results is this pattern expected to produce? unsigned PatResults = 0; @@ -2472,270 +2683,279 @@ 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());"); } - // Make sure these operands which would be selected won't be folded while - // the isel traverses the DAG upward. - std::vector > NumTemps(EmitOrder.size()); - for (unsigned i = 0, e = EmitOrder.size(); i != e; ++i) { - TreePatternNode *Child = EmitOrder[i].second; - if (!Child->getName().empty()) { - std::string &Val = VariableMap[Child->getName()]; - assert(!Val.empty() && - "Variable referenced but not defined and not caught earlier!"); - if (Child->isLeaf() && !NodeGetComplexPattern(Child, ISE)) { - emitCode("InFlightSet.insert(" + Val + ".Val);"); - InflightNodes.push_back(Val); - } - } - } - - // Emit all of the operands. - 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; + 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()); } - // 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); + // Emit all the chain and CopyToReg stuff. + bool ChainEmitted = NodeHasChain; + if (NodeHasChain) + emitCode("AddToISelQueue(" + ChainName + ");"); + if (NodeHasInFlag || HasImpInputs) + 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("}"); + } } - // Emit all the chain and CopyToReg stuff. - bool ChainEmitted = HasChain; - if (HasChain) - emitCode("Select(" + ChainName + ", " + ChainName + ");"); - if (HasInFlag || HasOptInFlag || HasImpInputs) - EmitInFlagSelectCode(Pattern, "N", ChainEmitted, true); - - // The operands have been selected. Remove them from InFlightSet. - for (std::vector::iterator AI = InflightNodes.begin(), - AE = InflightNodes.end(); AI != AE; ++AI) - emitCode("InFlightSet.erase(" + *AI + ".Val);"); unsigned NumResults = Inst.getNumResults(); unsigned ResNo = TmpNo++; - if (!isRoot) { - emitDecl("Tmp" + utostr(ResNo)); - std::string Code = - "Tmp" + utostr(ResNo) + " = SDOperand(CurDAG->getTargetNode(" + - II.Namespace + "::" + II.TheDef->getName(); - if (N->getTypeNum(0) != MVT::isVoid) - Code += ", MVT::" + getEnumName(N->getTypeNum(0)); + if (!isRoot || InputHasChain || NodeHasChain || NodeHasOutFlag || + NodeHasOptInFlag) { + std::string Code; + std::string Code2; + std::string NodeName; + if (!isRoot) { + NodeName = "Tmp" + utostr(ResNo); + Code2 = "SDOperand " + NodeName + " = SDOperand("; + } else { + NodeName = "ResNode"; + 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 + // Result types. + if (NumResults > 0 && N->getTypeNum(0) != MVT::isVoid) { + Code += ", VT" + utostr(VTNo); + emitVT(getEnumName(N->getTypeNum(0))); + } + if (NodeHasChain) + Code += ", MVT::Other"; if (NodeHasOutFlag) Code += ", MVT::Flag"; - unsigned LastOp = 0; - for (unsigned i = 0, e = Ops.size(); i != e; ++i) { - LastOp = Ops[i]; - Code += ", Tmp" + utostr(LastOp); - } - emitCode(Code + "), 0);"); - if (HasChain) { - // Must have at least one result - emitCode(ChainName + " = Tmp" + utostr(LastOp) + ".getValue(" + - utostr(NumResults) + ");"); + // Inputs. + if (HasVarOps) { + for (unsigned i = 0, e = AllOps.size(); i != e; ++i) + emitCode("Ops" + utostr(OpsNo) + ".push_back(" + AllOps[i] + ");"); + AllOps.clear(); } - } else if (HasChain || NodeHasOutFlag) { - if (HasOptInFlag) { - unsigned FlagNo = (unsigned) NodeHasChain + Pattern->getNumChildren(); - emitDecl("ResNode", true); - emitCode("if (HasOptInFlag)"); - std::string Code = " ResNode = CurDAG->getTargetNode(" + - II.Namespace + "::" + II.TheDef->getName(); - - // Output order: results, chain, flags - // Result types. - if (NumResults > 0) { - if (N->getTypeNum(0) != MVT::isVoid) - Code += ", MVT::" + getEnumName(N->getTypeNum(0)); - } - if (HasChain) - Code += ", MVT::Other"; - if (NodeHasOutFlag) - Code += ", MVT::Flag"; - - // Inputs. - for (unsigned i = 0, e = Ops.size(); i != e; ++i) - Code += ", Tmp" + utostr(Ops[i]); - if (HasChain) Code += ", " + ChainName; - emitCode(Code + ", InFlag);"); - - emitCode("else"); - Code = " ResNode = CurDAG->getTargetNode(" + II.Namespace + "::" + - II.TheDef->getName(); - - // Output order: results, chain, flags - // Result types. - if (NumResults > 0 && N->getTypeNum(0) != MVT::isVoid) - Code += ", MVT::" + getEnumName(N->getTypeNum(0)); - if (HasChain) - Code += ", MVT::Other"; - if (NodeHasOutFlag) - Code += ", MVT::Flag"; - // Inputs. - for (unsigned i = 0, e = Ops.size(); i != e; ++i) - Code += ", Tmp" + utostr(Ops[i]); - if (HasChain) Code += ", " + ChainName + ");"; - emitCode(Code); - } else { - emitDecl("ResNode", true); - std::string Code = "ResNode = CurDAG->getTargetNode(" + - II.Namespace + "::" + II.TheDef->getName(); - - // Output order: results, chain, flags - // Result types. - if (NumResults > 0 && N->getTypeNum(0) != MVT::isVoid) - Code += ", MVT::" + getEnumName(N->getTypeNum(0)); - if (HasChain) - Code += ", MVT::Other"; - if (NodeHasOutFlag) - Code += ", MVT::Flag"; - - // Inputs. - for (unsigned i = 0, e = Ops.size(); i != e; ++i) - Code += ", Tmp" + utostr(Ops[i]); - if (HasChain) Code += ", " + ChainName; - if (HasInFlag || HasImpInputs) Code += ", InFlag"; - emitCode(Code + ");"); + if (HasVarOps) { + if (NodeHasInFlag || HasImpInputs) + emitCode("for (unsigned i = 2, e = N.getNumOperands()-1; " + "i != e; ++i) {"); + else if (NodeHasOptInFlag) + emitCode("for (unsigned i = 2, e = N.getNumOperands()-" + "(HasInFlag?1:0); i != e; ++i) {"); + else + emitCode("for (unsigned i = 2, e = N.getNumOperands(); " + "i != e; ++i) {"); + emitCode(" AddToISelQueue(N.getOperand(i));"); + emitCode(" Ops" + utostr(OpsNo) + ".push_back(N.getOperand(i));"); + emitCode("}"); } - if (NewTF) - emitCode("if (OldTF) " - "SelectionDAG::InsertISelMapEntry(CodeGenMap, OldTF, 0, " + - ChainName + ".Val, 0);"); - - for (unsigned i = 0; i < NumResults; i++) - emitCode("SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, " + - utostr(i) + ", ResNode, " + utostr(i) + ");"); + if (NodeHasChain) { + if (HasVarOps) + emitCode("Ops" + utostr(OpsNo) + ".push_back(" + ChainName + ");"); + else + AllOps.push_back(ChainName); + } - if (NodeHasOutFlag) - emitCode("InFlag = SDOperand(ResNode, " + - utostr(NumResults + (unsigned)HasChain) + ");"); + 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 + ");"); + + if (NodeHasChain) + // Remember which op produces the chain. + if (!isRoot) + emitCode(ChainName + " = SDOperand(" + NodeName + + ".Val, " + utostr(PatResults) + ");"); + else + emitCode(ChainName + " = SDOperand(" + NodeName + + ", " + utostr(PatResults) + ");"); + + 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 (NodeHasChain) { - emitCode("SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, " + - utostr(PatResults) + ", ResNode, " + - utostr(NumResults) + ");"); - if (DoReplace) - emitCode("if (N.ResNo == 0) AddHandleReplacement(N.Val, " + - utostr(PatResults) + ", " + "ResNode, " + - utostr(NumResults) + ");"); + 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)NodeHasChain) + - ", 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 = HasChain && !NodeHasChain; - 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);"); - } - } else { - emitCode("Result = SDOperand(ResNode, N.ResNo);"); + if ((!InputHasChain && NodeHasChain) && NodeHasOutFlag) { + ; + } else if (InputHasChain && !NodeHasChain) { + // One of the inner node produces a chain. + 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, " + - II.Namespace + "::" + II.TheDef->getName(); + std::string Code = "return CurDAG->SelectNodeTo(N.Val, Opc" + + utostr(OpcNo); if (N->getTypeNum(0) != MVT::isVoid) - Code += ", MVT::" + getEnumName(N->getTypeNum(0)); + 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 (HasInFlag || 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", true); - Code = " ResNode = CurDAG->getTargetNode(" + - II.Namespace + "::" + II.TheDef->getName(); + emitOpcode(II.Namespace + "::" + II.TheDef->getName()); if (N->getTypeNum(0) != MVT::isVoid) - Code += ", MVT::" + 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 (HasInFlag || HasImpInputs) - Code += ", InFlag"; - emitCode(Code + ");"); - emitCode(" SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, N.ResNo, " - "ResNode, 0);"); - emitCode(" Result = SDOperand(ResNode, 0);"); - emitCode("}"); + emitVT(getEnumName(N->getTypeNum(0))); } - 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"; @@ -2748,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->hasTypeSet()) { + if (Pat->getExtTypes() != Other->getExtTypes()) { // Move a type over from 'other' to 'pat'. Pat->setTypes(Other->getExtTypes()); - emitCheck(Prefix + ".Val->getValueType(0) == MVT::" + - 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))) @@ -2771,16 +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); - bool HasOptInFlag = NodeHasProperty(N, SDNodeInfo::SDNPOptInFlag, 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()) { @@ -2794,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) + - ", MVT::" + 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);"); } @@ -2816,32 +3047,28 @@ private: } } - if (HasInFlag || HasOptInFlag) { - std::string Code; - if (HasOptInFlag) { - emitCode("if (" + RootName + ".getNumOperands() == " + utostr(OpNo+1) + - ") {"); - Code = " "; - } - emitCode(Code + "Select(InFlag, " + RootName + - ".getOperand(" + utostr(OpNo) + "));"); - if (HasOptInFlag) { - emitCode(" HasOptInFlag = true;"); - emitCode("}"); - } + 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")) { 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); @@ -2849,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 + ", " + - ISE.getQualifiedName(RR) + ", MVT::" + getEnumName(RVT) + + 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; @@ -2872,16 +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, - bool DoReplace) { + std::vector > &GeneratedCode, + std::set &GeneratedDecl, + std::vector &TargetOpcodes, + std::vector &TargetVTs) { PatternCodeEmitter Emitter(*this, Pattern.getPredicates(), Pattern.getSrcPattern(), Pattern.getDstPattern(), - GeneratedCode, GeneratedDecl, DoReplace); + GeneratedCode, GeneratedDecl, + 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; @@ -2917,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; } @@ -2927,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) { @@ -2944,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; @@ -2979,14 +3210,16 @@ void DAGISelEmitter::EmitPatterns(std::vector, CompareByRecordName> PatternsByOpcode; + // All unique target node emission functions. + std::map EmitFunctions; 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(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]] @@ -3098,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. @@ -3106,144 +3347,226 @@ void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) { CompareByRecordName>::iterator PBOI = PatternsByOpcode.begin(), E = PatternsByOpcode.end(); PBOI != E; ++PBOI) { const std::string &OpName = PBOI->first->getName(); - OS << "void Select_" << OpName << "(SDOperand &Result, SDOperand N) {\n"; - const SDNodeInfo &OpcodeInfo = getSDNodeInfo(PBOI->first); - bool OptSlctOrder = - (OpcodeInfo.hasProperty(SDNodeInfo::SDNPHasChain) && - OpcodeInfo.getNumResults() > 0); - - 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"; - } - - 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::set DeclSet; - - std::vector > CodeForPatterns; - std::set > GeneratedDecl; - for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { - CodeList GeneratedCode; - GenerateCodeForPattern(*Patterns[i], GeneratedCode, GeneratedDecl, - OptSlctOrder); - CodeForPatterns.push_back(std::make_pair(Patterns[i], GeneratedCode)); + // 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); + } } - } - // Print all declarations. - for (std::set >::iterator - I = GeneratedDecl.begin(), E = GeneratedDecl.end(); I != E; ++I) - if (I->first) - OS << " SDNode *" << I->second << ";\n"; - else - OS << " SDOperand " << I->second << "(0, 0);\n"; + // 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); + } - // 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()); - } + 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; + } + 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 { + EmitFuncNum = EmitFunctions.size(); + EmitFunctions.insert(std::make_pair(CalleeCode, EmitFuncNum)); + OS << "SDNode *Emit_" << utostr(EmitFuncNum) << CalleeCode; + } + + // 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)); + } + + // 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" @@ -3256,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 @@ -3362,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" @@ -3381,6 +3661,7 @@ void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) { << " }\n" << " std::cerr << '\\n';\n" << " abort();\n" + << " return NULL;\n" << "}\n"; } @@ -3392,147 +3673,123 @@ void DAGISelEmitter::run(std::ostream &OS) { << "// *** instruction selector class. These functions are really " << "methods.\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 << "// Keep track of nodes that are currently being selecte and therefore\n" - << "// should not be folded.\n"; - OS << "std::set InFlightSet;\n"; - - OS << "\n"; - OS << "static void findNonImmUse(SDNode* Use, SDNode* Def, bool &found, " - << "std::set &Visited) {\n"; - OS << " if (found || !Visited.insert(Use).second) return;\n"; - OS << " for (unsigned i = 0, e = Use->getNumOperands(); i != e; ++i) {\n"; - OS << " SDNode *N = Use->getOperand(i).Val;\n"; - OS << " if (N->getNodeDepth() >= Def->getNodeDepth()) {\n"; - OS << " if (N != Def) {\n"; - OS << " findNonImmUse(N, Def, found, Visited);\n"; - OS << " } else {\n"; - OS << " found = true;\n"; - OS << " break;\n"; - OS << " }\n"; - OS << " }\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 << "static bool isNonImmUse(SDNode* Use, SDNode* Def) {\n"; - OS << " std::set Visited;\n"; - OS << " bool found = false;\n"; - OS << " for (unsigned i = 0, e = Use->getNumOperands(); i != e; ++i) {\n"; - OS << " SDNode *N = Use->getOperand(i).Val;\n"; - OS << " if (N != Def) {\n"; - OS << " findNonImmUse(N, Def, found, Visited);\n"; - OS << " if (found) break;\n"; - OS << " }\n"; - OS << " }\n"; - OS << " return found;\n"; - OS << "}\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 << "\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 << " }\n"; + OS << "inline void setQueued(int Id) {\n"; + OS << " ISelQueued[Id / 8] |= 1 << (Id % 8);\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 << " }\n"; + OS << "inline bool isQueued(int Id) {\n"; + OS << " return ISelQueued[Id / 8] & (1 << (Id % 8));\n"; OS << "}\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 << " }\n"; - OS << " SDOperand U = SDOperand(Use, 0);\n"; - OS << " CurDAG->UpdateNodeOperands(U, Ops);\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 << "// UpdateFoldedChain - return a SDOperand of the new chain created\n"; - OS << "// if the folding were to happen. This is called when, for example,\n"; - OS << "// a load is folded into a store. If the store's chain is the load,\n"; - OS << "// then the resulting node's input chain would be the load's input\n"; - OS << "// chain. If the store's chain is a TokenFactor and the load's\n"; - OS << "// output chain feeds into in, then the new chain is a TokenFactor\n"; - OS << "// with the other operands along with the input chain of the load.\n"; - OS << "SDOperand UpdateFoldedChain(SelectionDAG *DAG, SDNode *N, " - << "SDNode *Chain, SDNode* &OldTF) {\n"; - OS << " OldTF = NULL;\n"; - OS << " if (N == Chain) {\n"; - OS << " return N->getOperand(0);\n"; - OS << " } else if (Chain->getOpcode() == ISD::TokenFactor &&\n"; - OS << " N->isOperand(Chain)) {\n"; - OS << " SDOperand Ch = SDOperand(Chain, 0);\n"; - OS << " std::map::iterator CGMI = " - << "CodeGenMap.find(Ch);\n"; - OS << " if (CGMI != CodeGenMap.end())\n"; - OS << " return SDOperand(0, 0);\n"; - OS << " OldTF = Chain;\n"; - OS << " std::vector Ops;\n"; - OS << " for (unsigned i = 0; i < Chain->getNumOperands(); ++i) {\n"; - OS << " SDOperand Op = Chain->getOperand(i);\n"; - OS << " if (Op.Val == N)\n"; - OS << " Ops.push_back(N->getOperand(0));\n"; - OS << " else\n"; - OS << " Ops.push_back(Op);\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 << " }\n"; - OS << " return DAG->getNode(ISD::TokenFactor, MVT::Other, Ops);\n"; OS << " }\n"; - OS << " return SDOperand(0, 0);\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);