diff options
Diffstat (limited to 'utils')
25 files changed, 3358 insertions, 2587 deletions
diff --git a/utils/GenLibDeps.pl b/utils/GenLibDeps.pl index b320a91..f1f7e72 100755 --- a/utils/GenLibDeps.pl +++ b/utils/GenLibDeps.pl @@ -70,6 +70,8 @@ opendir DIR,$Directory; my @files = readdir DIR; closedir DIR; my @libs = grep(/libLLVM.*\.(dylib|so|a)$/,sort(@files)); +# Omit the all-of-llvm shared library. +@libs = grep(!/libLLVM-\d\.\d(svn)?\.(dylib|so)/, @libs); my @objs = grep(/LLVM.*\.o$/,sort(@files)); # Declare the hashes we will use to keep track of the library and object file diff --git a/utils/TableGen/CMakeLists.txt b/utils/TableGen/CMakeLists.txt index a2678a2..881b50a 100644 --- a/utils/TableGen/CMakeLists.txt +++ b/utils/TableGen/CMakeLists.txt @@ -11,6 +11,7 @@ add_executable(tblgen DAGISelEmitter.cpp DAGISelMatcherEmitter.cpp DAGISelMatcherGen.cpp + DAGISelMatcherOpt.cpp DAGISelMatcher.cpp DisassemblerEmitter.cpp EDEmitter.cpp diff --git a/utils/TableGen/CodeGenDAGPatterns.cpp b/utils/TableGen/CodeGenDAGPatterns.cpp index 94d3534..ce737bf 100644 --- a/utils/TableGen/CodeGenDAGPatterns.cpp +++ b/utils/TableGen/CodeGenDAGPatterns.cpp @@ -447,6 +447,30 @@ SDNodeInfo::SDNodeInfo(Record *R) : Def(R) { TypeConstraints.assign(ConstraintList.begin(), ConstraintList.end()); } +/// getKnownType - If the type constraints on this node imply a fixed type +/// (e.g. all stores return void, etc), then return it as an +/// MVT::SimpleValueType. Otherwise, return EEVT::isUnknown. +unsigned SDNodeInfo::getKnownType() const { + unsigned NumResults = getNumResults(); + assert(NumResults <= 1 && + "We only work with nodes with zero or one result so far!"); + + for (unsigned i = 0, e = TypeConstraints.size(); i != e; ++i) { + // Make sure that this applies to the correct node result. + if (TypeConstraints[i].OperandNo >= NumResults) // FIXME: need value # + continue; + + switch (TypeConstraints[i].ConstraintType) { + default: break; + case SDTypeConstraint::SDTCisVT: + return TypeConstraints[i].x.SDTCisVT_Info.VT; + case SDTypeConstraint::SDTCisPtrTy: + return MVT::iPTR; + } + } + return EEVT::isUnknown; +} + //===----------------------------------------------------------------------===// // TreePatternNode implementation // @@ -568,33 +592,36 @@ bool TreePatternNode::UpdateNodeType(const std::vector<unsigned char> &ExtVTs, return true; // unreachable } +static std::string GetTypeName(unsigned char TypeID) { + switch (TypeID) { + case MVT::Other: return "Other"; + case MVT::iAny: return "iAny"; + case MVT::fAny: return "fAny"; + case MVT::vAny: return "vAny"; + case EEVT::isUnknown: return "isUnknown"; + case MVT::iPTR: return "iPTR"; + case MVT::iPTRAny: return "iPTRAny"; + default: + std::string VTName = llvm::getName((MVT::SimpleValueType)TypeID); + // Strip off EVT:: prefix if present. + if (VTName.substr(0,5) == "MVT::") + VTName = VTName.substr(5); + return VTName; + } +} + void TreePatternNode::print(raw_ostream &OS) const { if (isLeaf()) { OS << *getLeafValue(); } else { - OS << "(" << getOperator()->getName(); + OS << '(' << getOperator()->getName(); } // FIXME: At some point we should handle printing all the value types for // nodes that are multiply typed. - switch (getExtTypeNum(0)) { - case MVT::Other: OS << ":Other"; break; - case MVT::iAny: OS << ":iAny"; break; - case MVT::fAny : OS << ":fAny"; break; - case MVT::vAny: OS << ":vAny"; break; - case EEVT::isUnknown: ; /*OS << ":?";*/ break; - case MVT::iPTR: OS << ":iPTR"; break; - case MVT::iPTRAny: OS << ":iPTRAny"; break; - default: { - std::string VTName = llvm::getName(getTypeNum(0)); - // Strip off EVT:: prefix if present. - if (VTName.substr(0,5) == "MVT::") - VTName = VTName.substr(5); - OS << ":" << VTName; - break; - } - } + if (getExtTypeNum(0) != EEVT::isUnknown) + OS << ':' << GetTypeName(getExtTypeNum(0)); if (!isLeaf()) { if (getNumChildren() != 0) { @@ -956,19 +983,25 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { MadeChange |= UpdateNodeType(MVT::isVoid, TP); } return MadeChange; - } else if (getOperator()->getName() == "implicit" || - getOperator()->getName() == "parallel") { + } + + if (getOperator()->getName() == "implicit" || + getOperator()->getName() == "parallel") { bool MadeChange = false; for (unsigned i = 0; i < getNumChildren(); ++i) MadeChange = getChild(i)->ApplyTypeConstraints(TP, NotRegisters); MadeChange |= UpdateNodeType(MVT::isVoid, TP); return MadeChange; - } else if (getOperator()->getName() == "COPY_TO_REGCLASS") { + } + + if (getOperator()->getName() == "COPY_TO_REGCLASS") { bool MadeChange = false; MadeChange |= getChild(0)->ApplyTypeConstraints(TP, NotRegisters); MadeChange |= getChild(1)->ApplyTypeConstraints(TP, NotRegisters); return MadeChange; - } else if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) { + } + + if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) { bool MadeChange = false; // Apply the result type to the node. @@ -992,7 +1025,9 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); } return MadeChange; - } else if (getOperator()->isSubClassOf("SDNode")) { + } + + if (getOperator()->isSubClassOf("SDNode")) { const SDNodeInfo &NI = CDP.getSDNodeInfo(getOperator()); bool MadeChange = NI.ApplyTypeConstraints(this, TP); @@ -1004,7 +1039,9 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { MadeChange |= UpdateNodeType(MVT::isVoid, TP); return MadeChange; - } else if (getOperator()->isSubClassOf("Instruction")) { + } + + if (getOperator()->isSubClassOf("Instruction")) { const DAGInstruction &Inst = CDP.getInstruction(getOperator()); bool MadeChange = false; unsigned NumResults = Inst.getNumResults(); @@ -1080,24 +1117,24 @@ bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { "' was provided too many operands!"); return MadeChange; - } else { - assert(getOperator()->isSubClassOf("SDNodeXForm") && "Unknown node type!"); - - // Node transforms always take one operand. - if (getNumChildren() != 1) - TP.error("Node transform '" + getOperator()->getName() + - "' requires one operand!"); - - // If either the output or input of the xform does not have exact - // type info. We assume they must be the same. Otherwise, it is perfectly - // legal to transform from one type to a completely different type. - if (!hasTypeSet() || !getChild(0)->hasTypeSet()) { - bool MadeChange = UpdateNodeType(getChild(0)->getExtTypes(), TP); - MadeChange |= getChild(0)->UpdateNodeType(getExtTypes(), TP); - return MadeChange; - } - return false; } + + assert(getOperator()->isSubClassOf("SDNodeXForm") && "Unknown node type!"); + + // Node transforms always take one operand. + if (getNumChildren() != 1) + TP.error("Node transform '" + getOperator()->getName() + + "' requires one operand!"); + + // If either the output or input of the xform does not have exact + // type info. We assume they must be the same. Otherwise, it is perfectly + // legal to transform from one type to a completely different type. + if (!hasTypeSet() || !getChild(0)->hasTypeSet()) { + bool MadeChange = UpdateNodeType(getChild(0)->getExtTypes(), TP); + MadeChange |= getChild(0)->UpdateNodeType(getExtTypes(), TP); + return MadeChange; + } + return false; } /// OnlyOnRHSOfCommutative - Return true if this value is only allowed on the @@ -1370,7 +1407,6 @@ void TreePattern::dump() const { print(errs()); } // CodeGenDAGPatterns implementation // -// FIXME: REMOVE OSTREAM ARGUMENT CodeGenDAGPatterns::CodeGenDAGPatterns(RecordKeeper &R) : Records(R) { Intrinsics = LoadIntrinsics(Records, false); TgtIntrinsics = LoadIntrinsics(Records, true); @@ -1569,10 +1605,10 @@ void CodeGenDAGPatterns::ParseDefaultOperands() { if (TPN->ContainsUnresolvedType()) { if (iter == 0) throw "Value #" + utostr(i) + " of PredicateOperand '" + - DefaultOps[iter][i]->getName() + "' doesn't have a concrete type!"; + DefaultOps[iter][i]->getName() +"' doesn't have a concrete type!"; else throw "Value #" + utostr(i) + " of OptionalDefOperand '" + - DefaultOps[iter][i]->getName() + "' doesn't have a concrete type!"; + DefaultOps[iter][i]->getName() +"' doesn't have a concrete type!"; } DefaultOpInfo.DefaultOps.push_back(TPN); } @@ -1616,21 +1652,21 @@ static bool HandleUse(TreePattern *I, TreePatternNode *Pat, TreePatternNode *&Slot = InstInputs[Pat->getName()]; if (!Slot) { Slot = Pat; + return true; + } + Record *SlotRec; + if (Slot->isLeaf()) { + SlotRec = dynamic_cast<DefInit*>(Slot->getLeafValue())->getDef(); } else { - Record *SlotRec; - if (Slot->isLeaf()) { - SlotRec = dynamic_cast<DefInit*>(Slot->getLeafValue())->getDef(); - } else { - assert(Slot->getNumChildren() == 0 && "can't be a use with children!"); - SlotRec = Slot->getOperator(); - } - - // Ensure that the inputs agree if we've already seen this input. - if (Rec != SlotRec) - I->error("All $" + Pat->getName() + " inputs must agree with each other"); - if (Slot->getExtTypes() != Pat->getExtTypes()) - I->error("All $" + Pat->getName() + " inputs must agree with each other"); + assert(Slot->getNumChildren() == 0 && "can't be a use with children!"); + SlotRec = Slot->getOperator(); } + + // Ensure that the inputs agree if we've already seen this input. + if (Rec != SlotRec) + I->error("All $" + Pat->getName() + " inputs must agree with each other"); + if (Slot->getExtTypes() != Pat->getExtTypes()) + I->error("All $" + Pat->getName() + " inputs must agree with each other"); return true; } @@ -1648,7 +1684,9 @@ FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, if (!isUse && Pat->getTransformFn()) I->error("Cannot specify a transform function for a non-input value!"); return; - } else if (Pat->getOperator()->getName() == "implicit") { + } + + if (Pat->getOperator()->getName() == "implicit") { for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) { TreePatternNode *Dest = Pat->getChild(i); if (!Dest->isLeaf()) @@ -1660,7 +1698,9 @@ FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, InstImpResults.push_back(Val->getDef()); } return; - } else if (Pat->getOperator()->getName() != "set") { + } + + if (Pat->getOperator()->getName() != "set") { // If this is not a set, verify that the children nodes are not void typed, // and recurse. for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) { @@ -1677,7 +1717,7 @@ FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, if (!isUse && Pat->getTransformFn()) I->error("Cannot specify a transform function for a non-input value!"); return; - } + } // Otherwise, this is a set, validate and collect instruction results. if (Pat->getNumChildren() == 0) @@ -2063,20 +2103,100 @@ void CodeGenDAGPatterns::ParseInstructions() { SrcPattern = Pattern; } - std::string Reason; - if (!SrcPattern->canPatternMatch(Reason, *this)) - I->error("Instruction can never match: " + Reason); - Record *Instr = II->first; - TreePatternNode *DstPattern = TheInst.getResultPattern(); - PatternsToMatch. - push_back(PatternToMatch(Instr->getValueAsListInit("Predicates"), - SrcPattern, DstPattern, TheInst.getImpResults(), - Instr->getValueAsInt("AddedComplexity"))); + AddPatternToMatch(I, + PatternToMatch(Instr->getValueAsListInit("Predicates"), + SrcPattern, + TheInst.getResultPattern(), + TheInst.getImpResults(), + Instr->getValueAsInt("AddedComplexity"), + Instr->getID())); } } +typedef std::pair<const TreePatternNode*, unsigned> NameRecord; + +static void FindNames(const TreePatternNode *P, + std::map<std::string, NameRecord> &Names, + const TreePattern *PatternTop) { + if (!P->getName().empty()) { + NameRecord &Rec = Names[P->getName()]; + // If this is the first instance of the name, remember the node. + if (Rec.second++ == 0) + Rec.first = P; + else if (Rec.first->getExtTypes() != P->getExtTypes()) + PatternTop->error("repetition of value: $" + P->getName() + + " where different uses have different types!"); + } + + if (!P->isLeaf()) { + for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) + FindNames(P->getChild(i), Names, PatternTop); + } +} + +void CodeGenDAGPatterns::AddPatternToMatch(const TreePattern *Pattern, + const PatternToMatch &PTM) { + // Do some sanity checking on the pattern we're about to match. + std::string Reason; + if (!PTM.getSrcPattern()->canPatternMatch(Reason, *this)) + Pattern->error("Pattern can never match: " + Reason); + + // If the source pattern's root is a complex pattern, that complex pattern + // must specify the nodes it can potentially match. + if (const ComplexPattern *CP = + PTM.getSrcPattern()->getComplexPatternInfo(*this)) + if (CP->getRootNodes().empty()) + Pattern->error("ComplexPattern at root must specify list of opcodes it" + " could match"); + + + // Find all of the named values in the input and output, ensure they have the + // same type. + std::map<std::string, NameRecord> SrcNames, DstNames; + FindNames(PTM.getSrcPattern(), SrcNames, Pattern); + FindNames(PTM.getDstPattern(), DstNames, Pattern); + + // Scan all of the named values in the destination pattern, rejecting them if + // they don't exist in the input pattern. + for (std::map<std::string, NameRecord>::iterator + I = DstNames.begin(), E = DstNames.end(); I != E; ++I) { + if (SrcNames[I->first].first == 0) + Pattern->error("Pattern has input without matching name in output: $" + + I->first); + +#if 0 + const std::vector<unsigned char> &SrcTypeVec = + SrcNames[I->first].first->getExtTypes(); + const std::vector<unsigned char> &DstTypeVec = + I->second.first->getExtTypes(); + if (SrcTypeVec == DstTypeVec) continue; + + std::string SrcType, DstType; + for (unsigned i = 0, e = SrcTypeVec.size(); i != e; ++i) + SrcType += ":" + GetTypeName(SrcTypeVec[i]); + for (unsigned i = 0, e = DstTypeVec.size(); i != e; ++i) + DstType += ":" + GetTypeName(DstTypeVec[i]); + + Pattern->error("Variable $" + I->first + + " has different types in source (" + SrcType + + ") and dest (" + DstType + ") pattern!"); +#endif + } + + // Scan all of the named values in the source pattern, rejecting them if the + // name isn't used in the dest, and isn't used to tie two values together. + for (std::map<std::string, NameRecord>::iterator + I = SrcNames.begin(), E = SrcNames.end(); I != E; ++I) + if (DstNames[I->first].first == 0 && SrcNames[I->first].second == 1) + Pattern->error("Pattern has dead named input: $" + I->first); + + PatternsToMatch.push_back(PTM); +} + + + void CodeGenDAGPatterns::InferInstructionFlags() { std::map<std::string, CodeGenInstruction> &InstrDescs = Target.getInstructions(); @@ -2204,15 +2324,13 @@ void CodeGenDAGPatterns::ParsePatterns() { TreePattern Temp(Result->getRecord(), DstPattern, false, *this); Temp.InferAllTypes(); - std::string Reason; - if (!Pattern->getTree(0)->canPatternMatch(Reason, *this)) - Pattern->error("Pattern can never match: " + Reason); - PatternsToMatch. - push_back(PatternToMatch(Patterns[i]->getValueAsListInit("Predicates"), - Pattern->getTree(0), - Temp.getOnlyTree(), InstImpResults, - Patterns[i]->getValueAsInt("AddedComplexity"))); + AddPatternToMatch(Pattern, + PatternToMatch(Patterns[i]->getValueAsListInit("Predicates"), + Pattern->getTree(0), + Temp.getOnlyTree(), InstImpResults, + Patterns[i]->getValueAsInt("AddedComplexity"), + Patterns[i]->getID())); } } @@ -2234,13 +2352,13 @@ static void CombineChildVariants(TreePatternNode *Orig, bool NotDone; do { #ifndef NDEBUG - if (DebugFlag && !Idxs.empty()) { - errs() << Orig->getOperator()->getName() << ": Idxs = [ "; - for (unsigned i = 0; i < Idxs.size(); ++i) { - errs() << Idxs[i] << " "; - } - errs() << "]\n"; - } + DEBUG(if (!Idxs.empty()) { + errs() << Orig->getOperator()->getName() << ": Idxs = [ "; + for (unsigned i = 0; i < Idxs.size(); ++i) { + errs() << Idxs[i] << " "; + } + errs() << "]\n"; + }); #endif // Create the variant and add it to the output list. std::vector<TreePatternNode*> NewChildren; @@ -2506,7 +2624,8 @@ void CodeGenDAGPatterns::GenerateVariants() { push_back(PatternToMatch(PatternsToMatch[i].getPredicates(), Variant, PatternsToMatch[i].getDstPattern(), PatternsToMatch[i].getDstRegs(), - PatternsToMatch[i].getAddedComplexity())); + PatternsToMatch[i].getAddedComplexity(), + Record::getNewUID())); } DEBUG(errs() << "\n"); diff --git a/utils/TableGen/CodeGenDAGPatterns.h b/utils/TableGen/CodeGenDAGPatterns.h index f1f7bca..37d633e 100644 --- a/utils/TableGen/CodeGenDAGPatterns.h +++ b/utils/TableGen/CodeGenDAGPatterns.h @@ -125,6 +125,11 @@ public: return TypeConstraints; } + /// getKnownType - If the type constraints on this node imply a fixed type + /// (e.g. all stores return void, etc), then return it as an + /// MVT::SimpleValueType. Otherwise, return EEVT::isUnknown. + unsigned getKnownType() const; + /// hasProperty - Return true if this node has the specified property. /// bool hasProperty(enum SDNP Prop) const { return Properties & (1 << Prop); } @@ -466,19 +471,21 @@ public: /// PatternToMatch - Used by CodeGenDAGPatterns to keep tab of patterns /// processed to produce isel. -struct PatternToMatch { +class PatternToMatch { +public: PatternToMatch(ListInit *preds, TreePatternNode *src, TreePatternNode *dst, const std::vector<Record*> &dstregs, - unsigned complexity): - Predicates(preds), SrcPattern(src), DstPattern(dst), Dstregs(dstregs), - AddedComplexity(complexity) {} + unsigned complexity, unsigned uid) + : Predicates(preds), SrcPattern(src), DstPattern(dst), + Dstregs(dstregs), AddedComplexity(complexity), ID(uid) {} ListInit *Predicates; // Top level predicate conditions to match. TreePatternNode *SrcPattern; // Source pattern to match. TreePatternNode *DstPattern; // Resulting pattern. std::vector<Record*> Dstregs; // Physical register defs being matched. unsigned AddedComplexity; // Add to matching pattern complexity. + unsigned ID; // Unique ID for the record. ListInit *getPredicates() const { return Predicates; } TreePatternNode *getSrcPattern() const { return SrcPattern; } @@ -574,7 +581,7 @@ public: abort(); } - const DAGDefaultOperand &getDefaultOperand(Record *R) { + const DAGDefaultOperand &getDefaultOperand(Record *R) const { assert(DefaultOperands.count(R) &&"Isn't an analyzed default operand!"); return DefaultOperands.find(R)->second; } @@ -624,6 +631,7 @@ private: void InferInstructionFlags(); void GenerateVariants(); + void AddPatternToMatch(const TreePattern *Pattern, const PatternToMatch &PTM); void FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, std::map<std::string, TreePatternNode*> &InstInputs, diff --git a/utils/TableGen/CodeGenInstruction.cpp b/utils/TableGen/CodeGenInstruction.cpp index d31502b..f5b52ec 100644 --- a/utils/TableGen/CodeGenInstruction.cpp +++ b/utils/TableGen/CodeGenInstruction.cpp @@ -117,7 +117,6 @@ CodeGenInstruction::CodeGenInstruction(Record *R, const std::string &AsmStr) hasCtrlDep = R->getValueAsBit("hasCtrlDep"); isNotDuplicable = R->getValueAsBit("isNotDuplicable"); hasSideEffects = R->getValueAsBit("hasSideEffects"); - mayHaveSideEffects = R->getValueAsBit("mayHaveSideEffects"); neverHasSideEffects = R->getValueAsBit("neverHasSideEffects"); isAsCheapAsAMove = R->getValueAsBit("isAsCheapAsAMove"); hasExtraSrcRegAllocReq = R->getValueAsBit("hasExtraSrcRegAllocReq"); @@ -125,7 +124,7 @@ CodeGenInstruction::CodeGenInstruction(Record *R, const std::string &AsmStr) hasOptionalDef = false; isVariadic = false; - if (mayHaveSideEffects + neverHasSideEffects + hasSideEffects > 1) + if (neverHasSideEffects + hasSideEffects > 1) throw R->getName() + ": multiple conflicting side-effect flags set!"; DagInit *DI; diff --git a/utils/TableGen/CodeGenInstruction.h b/utils/TableGen/CodeGenInstruction.h index 285da14..aae2cac 100644 --- a/utils/TableGen/CodeGenInstruction.h +++ b/utils/TableGen/CodeGenInstruction.h @@ -133,7 +133,6 @@ namespace llvm { bool isNotDuplicable; bool hasOptionalDef; bool hasSideEffects; - bool mayHaveSideEffects; bool neverHasSideEffects; bool isAsCheapAsAMove; bool hasExtraSrcRegAllocReq; diff --git a/utils/TableGen/DAGISelEmitter.cpp b/utils/TableGen/DAGISelEmitter.cpp index f0cebed..e0fa7c8 100644 --- a/utils/TableGen/DAGISelEmitter.cpp +++ b/utils/TableGen/DAGISelEmitter.cpp @@ -14,49 +14,13 @@ #include "DAGISelEmitter.h" #include "DAGISelMatcher.h" #include "Record.h" -#include "llvm/ADT/StringExtras.h" -#include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" -#include "llvm/Support/MathExtras.h" -#include "llvm/Support/Debug.h" -#include <algorithm> -#include <deque> -#include <iostream> using namespace llvm; -static cl::opt<bool> -GenDebug("gen-debug", cl::desc("Generate debug code"), cl::init(false)); - //===----------------------------------------------------------------------===// // DAGISelEmitter Helper methods // -/// getNodeName - The top level Select_* functions have an "SDNode* N" -/// argument. When expanding the pattern-matching code, the intermediate -/// variables have type SDValue. This function provides a uniform way to -/// reference the underlying "SDNode *" for both cases. -static std::string getNodeName(const std::string &S) { - if (S == "N") return S; - return S + ".getNode()"; -} - -/// getNodeValue - Similar to getNodeName, except it provides a uniform -/// way to access the SDValue for both cases. -static std::string getValueName(const std::string &S) { - if (S == "N") return "SDValue(N, 0)"; - return S; -} - -/// NodeIsComplexPattern - return true if N is a leaf node and a subclass of -/// ComplexPattern. -static bool NodeIsComplexPattern(TreePatternNode *N) { - return (N->isLeaf() && - dynamic_cast<DefInit*>(N->getLeafValue()) && - static_cast<DefInit*>(N->getLeafValue())->getDef()-> - isSubClassOf("ComplexPattern")); -} - - /// getPatternSize - Return the 'size' of this pattern. We want to match large /// patterns before small ones. This is used to determine the size of a /// pattern. @@ -96,7 +60,7 @@ static unsigned getPatternSize(TreePatternNode *P, CodeGenDAGPatterns &CGP) { else if (Child->isLeaf()) { if (dynamic_cast<IntInit*>(Child->getLeafValue())) Size += 5; // Matches a ConstantSDNode (+3) and a specific value (+2). - else if (NodeIsComplexPattern(Child)) + else if (Child->getComplexPatternInfo(CGP)) Size += getPatternSize(Child, CGP); else if (!Child->getPredicateFns().empty()) ++Size; @@ -142,106 +106,6 @@ static unsigned getResultPatternSize(TreePatternNode *P, 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. -struct PatternSortingPredicate { - PatternSortingPredicate(CodeGenDAGPatterns &cgp) : CGP(cgp) {} - CodeGenDAGPatterns &CGP; - - typedef std::pair<unsigned, std::string> CodeLine; - typedef std::vector<CodeLine> CodeList; - typedef std::vector<std::pair<const PatternToMatch*, CodeList> > PatternList; - - bool operator()(const std::pair<const PatternToMatch*, CodeList> &LHSPair, - const std::pair<const PatternToMatch*, CodeList> &RHSPair) { - const PatternToMatch *LHS = LHSPair.first; - const PatternToMatch *RHS = RHSPair.first; - - unsigned LHSSize = getPatternSize(LHS->getSrcPattern(), CGP); - unsigned RHSSize = getPatternSize(RHS->getSrcPattern(), CGP); - LHSSize += LHS->getAddedComplexity(); - RHSSize += RHS->getAddedComplexity(); - if (LHSSize > RHSSize) return true; // LHS -> bigger -> less cost - if (LHSSize < RHSSize) return false; - - // If the patterns have equal complexity, compare generated instruction cost - unsigned LHSCost = getResultPatternCost(LHS->getDstPattern(), CGP); - unsigned RHSCost = getResultPatternCost(RHS->getDstPattern(), CGP); - if (LHSCost < RHSCost) return true; - if (LHSCost > RHSCost) return false; - - return getResultPatternSize(LHS->getDstPattern(), CGP) < - getResultPatternSize(RHS->getDstPattern(), CGP); - } -}; - -/// getRegisterValueType - Look up and return the ValueType of the specified -/// register. If the register is a member of multiple register classes which -/// have different associated types, return MVT::Other. -static MVT::SimpleValueType getRegisterValueType(Record *R, const CodeGenTarget &T) { - bool FoundRC = false; - MVT::SimpleValueType VT = MVT::Other; - const std::vector<CodeGenRegisterClass> &RCs = T.getRegisterClasses(); - std::vector<CodeGenRegisterClass>::const_iterator RC; - std::vector<Record*>::const_iterator Element; - - for (RC = RCs.begin() ; RC != RCs.end() ; RC++) { - Element = find((*RC).Elements.begin(), (*RC).Elements.end(), R); - if (Element != (*RC).Elements.end()) { - if (!FoundRC) { - FoundRC = true; - VT = (*RC).getValueTypeNum(0); - } else { - // In multiple RC's - if (VT != (*RC).getValueTypeNum(0)) { - // Types of the RC's do not agree. Return MVT::Other. The - // target is responsible for handling this. - return MVT::Other; - } - } - } - } - return VT; -} - -static std::string getOpcodeName(Record *Op, CodeGenDAGPatterns &CGP) { - return CGP.getSDNodeInfo(Op).getEnumName(); -} - -//===----------------------------------------------------------------------===// -// Node Transformation emitter implementation. -// -void DAGISelEmitter::EmitNodeTransforms(raw_ostream &OS) { - // Walk the pattern fragments, adding them to a map, which sorts them by - // name. - typedef std::map<std::string, CodeGenDAGPatterns::NodeXForm> NXsByNameTy; - NXsByNameTy NXsByName; - - for (CodeGenDAGPatterns::nx_iterator I = CGP.nx_begin(), E = CGP.nx_end(); - I != E; ++I) - NXsByName.insert(std::make_pair(I->first->getName(), I->second)); - - OS << "\n// Node transformations.\n"; - - for (NXsByNameTy::iterator I = NXsByName.begin(), E = NXsByName.end(); - I != E; ++I) { - Record *SDNode = I->second.first; - std::string Code = I->second.second; - - if (Code.empty()) continue; // Empty code? Skip it. - - std::string ClassName = CGP.getSDNodeInfo(SDNode).getSDClassName(); - const char *C2 = ClassName == "SDNode" ? "N" : "inN"; - - OS << "inline SDValue Transform_" << I->first << "(SDNode *" << C2 - << ") {\n"; - if (ClassName != "SDNode") - OS << " " << ClassName << " *N = cast<" << ClassName << ">(inN);\n"; - OS << Code << "\n}\n"; - } -} - //===----------------------------------------------------------------------===// // Predicate emitter implementation. // @@ -287,1688 +151,41 @@ void DAGISelEmitter::EmitPredicateFunctions(raw_ostream &OS) { OS << "\n\n"; } - -//===----------------------------------------------------------------------===// -// PatternCodeEmitter implementation. -// -class PatternCodeEmitter { -private: +namespace { +// 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. +struct PatternSortingPredicate { + PatternSortingPredicate(CodeGenDAGPatterns &cgp) : CGP(cgp) {} CodeGenDAGPatterns &CGP; - - // Predicates. - std::string PredicateCheck; - // Pattern cost. - unsigned Cost; - // Instruction selector pattern. - TreePatternNode *Pattern; - // Matched instruction. - TreePatternNode *Instruction; - - // Node to name mapping - std::map<std::string, std::string> VariableMap; - // Node to operator mapping - std::map<std::string, Record*> OperatorMap; - // Name of the folded node which produces a flag. - std::pair<std::string, unsigned> FoldedFlag; - // Names of all the folded nodes which produce chains. - std::vector<std::pair<std::string, unsigned> > FoldedChains; - // Original input chain(s). - std::vector<std::pair<std::string, std::string> > OrigChains; - std::set<std::string> Duplicates; - - /// LSI - Load/Store information. - /// Save loads/stores matched by a pattern, and generate a MemOperandSDNode - /// for each memory access. This facilitates the use of AliasAnalysis in - /// the backend. - std::vector<std::string> LSI; - - /// 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 1], or normal code to emit - /// [when 0], or initialization code to emit [when 2]. - std::vector<std::pair<unsigned, std::string> > &GeneratedCode; - /// GeneratedDecl - This is the set of all SDValue declarations needed for - /// the set of patterns for each top-level opcode. - std::set<std::string> &GeneratedDecl; - /// TargetOpcodes - The target specific opcodes used by the resulting - /// instructions. - std::vector<std::string> &TargetOpcodes; - std::vector<std::string> &TargetVTs; - /// OutputIsVariadic - Records whether the instruction output pattern uses - /// variable_ops. This requires that the Emit function be passed an - /// additional argument to indicate where the input varargs operands - /// begin. - bool &OutputIsVariadic; - /// NumInputRootOps - Records the number of operands the root node of the - /// input pattern has. This information is used in the generated code to - /// pass to Emit functions when variable_ops processing is needed. - unsigned &NumInputRootOps; - - std::string ChainName; - unsigned TmpNo; - unsigned OpcNo; - unsigned VTNo; - void emitCheck(const std::string &S) { - if (!S.empty()) - GeneratedCode.push_back(std::make_pair(1, S)); - } - void emitCode(const std::string &S) { - if (!S.empty()) - 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) { - assert(!S.empty() && "Invalid declaration"); - 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(CodeGenDAGPatterns &cgp, std::string predcheck, - TreePatternNode *pattern, TreePatternNode *instr, - std::vector<std::pair<unsigned, std::string> > &gc, - std::set<std::string> &gd, - std::vector<std::string> &to, - std::vector<std::string> &tv, - bool &oiv, - unsigned &niro) - : CGP(cgp), PredicateCheck(predcheck), Pattern(pattern), Instruction(instr), - GeneratedCode(gc), GeneratedDecl(gd), - TargetOpcodes(to), TargetVTs(tv), - OutputIsVariadic(oiv), NumInputRootOps(niro), - 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 &ChainSuffix, - bool &FoundChain); - - void EmitChildMatchCode(TreePatternNode *Child, TreePatternNode *Parent, - const std::string &RootName, - const std::string &ChainSuffix, bool &FoundChain); - - /// EmitResultCode - Emit the action for a pattern. Now that it has matched - /// we actually have to build a DAG! - std::vector<std::string> - EmitResultCode(TreePatternNode *N, std::vector<Record*> DstRegs, - bool InFlagDecled, bool ResNodeDecled, - bool LikeLeaf = false, bool isRoot = false); - - /// InsertOneTypeCheck - Insert a type-check for an unresolved type in 'Pat' - /// and add it to the tree. 'Pat' and 'Other' are isomorphic trees except that - /// 'Pat' may be missing types. If we find an unresolved type to add a check - /// for, this returns true otherwise false if Pat has all types. - bool InsertOneTypeCheck(TreePatternNode *Pat, TreePatternNode *Other, - const std::string &Prefix, bool isRoot = false) { - // Did we find one? - if (Pat->getExtTypes() != Other->getExtTypes()) { - // Move a type over from 'other' to 'pat'. - Pat->setTypes(Other->getExtTypes()); - // The top level node type is checked outside of the select function. - if (!isRoot) - emitCheck(Prefix + ".getValueType() == " + - getName(Pat->getTypeNum(0))); - return true; - } - - unsigned OpNo = (unsigned)Pat->NodeHasProperty(SDNPHasChain, CGP); - for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i, ++OpNo) - if (InsertOneTypeCheck(Pat->getChild(i), Other->getChild(i), - Prefix + utostr(OpNo))) - return true; - return false; - } - -private: - /// EmitInFlagSelectCode - Emit the flag operands for the DAG that is - /// being built. - void EmitInFlagSelectCode(TreePatternNode *N, const std::string &RootName, - bool &ChainEmitted, bool &InFlagDecled, - bool &ResNodeDecled, bool isRoot = false) { - const CodeGenTarget &T = CGP.getTargetInfo(); - unsigned OpNo = (unsigned)N->NodeHasProperty(SDNPHasChain, CGP); - bool HasInFlag = N->NodeHasProperty(SDNPInFlag, CGP); - 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, - InFlagDecled, ResNodeDecled); - } else { - if (DefInit *DI = dynamic_cast<DefInit*>(Child->getLeafValue())) { - if (!Child->getName().empty()) { - std::string Name = RootName + utostr(OpNo); - if (Duplicates.find(Name) != Duplicates.end()) - // A duplicate! Do not emit a copy for this node. - continue; - } - - Record *RR = DI->getDef(); - if (RR->isSubClassOf("Register")) { - MVT::SimpleValueType RVT = getRegisterValueType(RR, T); - if (RVT == MVT::Flag) { - if (!InFlagDecled) { - emitCode("SDValue InFlag = " + - getValueName(RootName + utostr(OpNo)) + ";"); - InFlagDecled = true; - } else - emitCode("InFlag = " + - getValueName(RootName + utostr(OpNo)) + ";"); - } else { - if (!ChainEmitted) { - emitCode("SDValue Chain = CurDAG->getEntryNode();"); - ChainName = "Chain"; - ChainEmitted = true; - } - if (!InFlagDecled) { - emitCode("SDValue InFlag(0, 0);"); - InFlagDecled = true; - } - std::string Decl = (!ResNodeDecled) ? "SDNode *" : ""; - emitCode(Decl + "ResNode = CurDAG->getCopyToReg(" + ChainName + - ", " + getNodeName(RootName) + "->getDebugLoc()" + - ", " + getQualifiedName(RR) + - ", " + getValueName(RootName + utostr(OpNo)) + - ", InFlag).getNode();"); - ResNodeDecled = true; - emitCode(ChainName + " = SDValue(ResNode, 0);"); - emitCode("InFlag = SDValue(ResNode, 1);"); - } - } - } - } - } - - if (HasInFlag) { - if (!InFlagDecled) { - emitCode("SDValue InFlag = " + getNodeName(RootName) + - "->getOperand(" + utostr(OpNo) + ");"); - InFlagDecled = true; - } else - emitCode("InFlag = " + getNodeName(RootName) + - "->getOperand(" + utostr(OpNo) + ");"); - } - } -}; - - -/// 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 PatternCodeEmitter::EmitMatchCode(TreePatternNode *N, TreePatternNode *P, - const std::string &RootName, - const std::string &ChainSuffix, - bool &FoundChain) { - - // Save loads/stores matched by a pattern. - if (!N->isLeaf() && N->getName().empty()) { - if (N->NodeHasProperty(SDNPMemOperand, CGP)) - LSI.push_back(getNodeName(RootName)); - } - - bool isRoot = (P == NULL); - // Emit instruction predicates. Each predicate is just a string for now. - if (isRoot) { - // Record input varargs info. - NumInputRootOps = N->getNumChildren(); - emitCheck(PredicateCheck); - } - - if (N->isLeaf()) { - if (IntInit *II = dynamic_cast<IntInit*>(N->getLeafValue())) { - emitCheck("cast<ConstantSDNode>(" + getNodeName(RootName) + - ")->getSExtValue() == INT64_C(" + - itostr(II->getValue()) + ")"); - return; - } else if (!NodeIsComplexPattern(N)) { - assert(0 && "Cannot match this as a leaf value!"); - abort(); - } - } - - // If this node has a name associated with it, capture it in VariableMap. If - // we already saw this in the pattern, emit code to verify dagness. - if (!N->getName().empty()) { - std::string &VarMapEntry = VariableMap[N->getName()]; - if (VarMapEntry.empty()) { - VarMapEntry = RootName; - } else { - // 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); - return; - } - - if (!N->isLeaf()) - OperatorMap[N->getName()] = N->getOperator(); - } - - - // Emit code to load the child nodes and match their contents recursively. - unsigned OpNo = 0; - bool NodeHasChain = N->NodeHasProperty(SDNPHasChain, CGP); - bool HasChain = N->TreeHasProperty(SDNPHasChain, CGP); - if (HasChain) { - if (NodeHasChain) - OpNo = 1; - if (!isRoot) { - // Check if it's profitable to fold the node. e.g. Check for multiple uses - // of actual result? - std::string ParentName(RootName.begin(), RootName.end()-1); - emitCheck("IsProfitableToFold(" + getValueName(RootName) + - ", " + getNodeName(ParentName) + ", N)"); - if (NodeHasChain) { - // 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 - // ld is folded into XX, then YY is both a predecessor and a successor - // of XX. - // - // [ld] - // ^ ^ - // | | - // / \--- - // / [YY] - // | ^ - // [XX]-------| - - // We know we need the check if N's parent is not the root. - bool NeedCheck = P != Pattern; - if (!NeedCheck) { - const SDNodeInfo &PInfo = CGP.getSDNodeInfo(P->getOperator()); - NeedCheck = - P->getOperator() == CGP.get_intrinsic_void_sdnode() || - P->getOperator() == CGP.get_intrinsic_w_chain_sdnode() || - P->getOperator() == CGP.get_intrinsic_wo_chain_sdnode() || - PInfo.getNumOperands() > 1 || - PInfo.hasProperty(SDNPHasChain) || - PInfo.hasProperty(SDNPInFlag) || - PInfo.hasProperty(SDNPOptInFlag); - } - - if (NeedCheck) { - emitCheck("IsLegalToFold(" + getValueName(RootName) + - ", " + getNodeName(ParentName) + ", N)"); - } - } - } - - if (NodeHasChain) { - if (FoundChain) { - emitCheck("(" + ChainName + ".getNode() == " + - getNodeName(RootName) + " || " - "IsChainCompatible(" + ChainName + ".getNode(), " + - getNodeName(RootName) + "))"); - OrigChains.push_back(std::make_pair(ChainName, - getValueName(RootName))); - } else - FoundChain = true; - ChainName = "Chain" + ChainSuffix; - emitInit("SDValue " + ChainName + " = " + getNodeName(RootName) + - "->getOperand(0);"); - } - } - - // If there are node predicates for this, emit the calls. - for (unsigned i = 0, e = N->getPredicateFns().size(); i != e; ++i) - emitCheck(N->getPredicateFns()[i] + "(" + getNodeName(RootName) + ")"); - - // 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)->getPredicateFns().empty()) { - if (IntInit *II = dynamic_cast<IntInit*>(N->getChild(1)->getLeafValue())) { - if (!isPowerOf2_32(II->getValue())) { // Don't bother with single bits. - emitInit("SDValue " + RootName + "0" + " = " + - getNodeName(RootName) + "->getOperand(" + utostr(0) + ");"); - emitInit("SDValue " + RootName + "1" + " = " + - getNodeName(RootName) + "->getOperand(" + utostr(1) + ");"); - - unsigned NTmp = TmpNo++; - emitCode("ConstantSDNode *Tmp" + utostr(NTmp) + - " = dyn_cast<ConstantSDNode>(" + - getNodeName(RootName + "1") + ");"); - emitCheck("Tmp" + utostr(NTmp)); - const char *MaskPredicate = N->getOperator()->getName() == "or" - ? "CheckOrMask(" : "CheckAndMask("; - emitCheck(MaskPredicate + getValueName(RootName + "0") + - ", Tmp" + utostr(NTmp) + - ", INT64_C(" + 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) { - emitInit("SDValue " + getValueName(RootName + utostr(OpNo)) + " = " + - getNodeName(RootName) + "->getOperand(" + utostr(OpNo) + ");"); - - 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 = N->getComplexPatternInfo(CGP))) { - std::string Fn = CP->getSelectFunc(); - unsigned NumOps = CP->getNumOperands(); - for (unsigned i = 0; i < NumOps; ++i) { - emitDecl("CPTmp" + RootName + "_" + utostr(i)); - emitCode("SDValue CPTmp" + RootName + "_" + utostr(i) + ";"); - } - if (CP->hasProperty(SDNPHasChain)) { - emitDecl("CPInChain"); - emitDecl("Chain" + ChainSuffix); - emitCode("SDValue CPInChain;"); - emitCode("SDValue Chain" + ChainSuffix + ";"); - } - - std::string Code = Fn + "(" + - getNodeName(RootName) + ", " + - getValueName(RootName); - for (unsigned i = 0; i < NumOps; i++) - Code += ", CPTmp" + RootName + "_" + utostr(i); - if (CP->hasProperty(SDNPHasChain)) { - ChainName = "Chain" + ChainSuffix; - Code += ", CPInChain, Chain" + ChainSuffix; - } - emitCheck(Code + ")"); - } -} - -void PatternCodeEmitter::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 = CGP.getSDNodeInfo(Child->getOperator()); - emitCheck(getNodeName(RootName) + "->getOpcode() == " + - CInfo.getEnumName()); - EmitMatchCode(Child, Parent, RootName, ChainSuffix, FoundChain); - bool HasChain = false; - if (Child->NodeHasProperty(SDNPHasChain, CGP)) { - HasChain = true; - FoldedChains.push_back(std::make_pair(getValueName(RootName), - CInfo.getNumResults())); - } - if (Child->NodeHasProperty(SDNPOutFlag, CGP)) { - assert(FoldedFlag.first == "" && FoldedFlag.second == 0 && - "Pattern folded multiple nodes which produce flags?"); - FoldedFlag = std::make_pair(getValueName(RootName), - CInfo.getNumResults() + (unsigned)HasChain); - } - } 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 = getValueName(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 + " == " + getValueName(RootName)); - Duplicates.insert(getValueName(RootName)); - return; - } - } - - // Handle leaves of various types. - if (DefInit *DI = dynamic_cast<DefInit*>(Child->getLeafValue())) { - Record *LeafRec = DI->getDef(); - if (LeafRec->isSubClassOf("RegisterClass") || - LeafRec->isSubClassOf("PointerLikeRegClass")) { - // 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 = Child->getComplexPatternInfo(CGP); - std::string Fn = CP->getSelectFunc(); - unsigned NumOps = CP->getNumOperands(); - for (unsigned i = 0; i < NumOps; ++i) { - emitDecl("CPTmp" + RootName + "_" + utostr(i)); - emitCode("SDValue CPTmp" + RootName + "_" + utostr(i) + ";"); - } - if (CP->hasProperty(SDNPHasChain)) { - const SDNodeInfo &PInfo = CGP.getSDNodeInfo(Parent->getOperator()); - FoldedChains.push_back(std::make_pair("CPInChain", - PInfo.getNumResults())); - ChainName = "Chain" + ChainSuffix; - emitDecl("CPInChain"); - emitDecl(ChainName); - emitCode("SDValue CPInChain;"); - emitCode("SDValue " + ChainName + ";"); - } - - std::string Code = Fn + "(N, "; - if (CP->hasProperty(SDNPHasChain)) { - std::string ParentName(RootName.begin(), RootName.end()-1); - Code += getValueName(ParentName) + ", "; - } - Code += getValueName(RootName); - for (unsigned i = 0; i < NumOps; i++) - Code += ", CPTmp" + RootName + "_" + 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<VTSDNode>(" + getNodeName(RootName) + - ")->getVT() == MVT::" + LeafRec->getName()); - } else if (LeafRec->isSubClassOf("CondCode")) { - // Make sure this is the specified cond code. - emitCheck("cast<CondCodeSDNode>(" + getNodeName(RootName) + - ")->get() == ISD::" + LeafRec->getName()); - } else { -#ifndef NDEBUG - Child->dump(); - errs() << " "; -#endif - assert(0 && "Unknown leaf type!"); - } - - // If there are node predicates for this, emit the calls. - for (unsigned i = 0, e = Child->getPredicateFns().size(); i != e; ++i) - emitCheck(Child->getPredicateFns()[i] + "(" + getNodeName(RootName) + - ")"); - } else if (IntInit *II = - dynamic_cast<IntInit*>(Child->getLeafValue())) { - unsigned NTmp = TmpNo++; - emitCode("ConstantSDNode *Tmp"+ utostr(NTmp) + - " = dyn_cast<ConstantSDNode>("+ - getNodeName(RootName) + ");"); - emitCheck("Tmp" + utostr(NTmp)); - unsigned CTmp = TmpNo++; - emitCode("int64_t CN"+ utostr(CTmp) + - " = Tmp" + utostr(NTmp) + "->getSExtValue();"); - emitCheck("CN" + utostr(CTmp) + " == " - "INT64_C(" +itostr(II->getValue()) + ")"); - } else { -#ifndef NDEBUG - Child->dump(); -#endif - assert(0 && "Unknown leaf type!"); - } - } -} - -/// EmitResultCode - Emit the action for a pattern. Now that it has matched -/// we actually have to build a DAG! -std::vector<std::string> -PatternCodeEmitter::EmitResultCode(TreePatternNode *N, - std::vector<Record*> DstRegs, - bool InFlagDecled, bool ResNodeDecled, - bool LikeLeaf, bool isRoot) { - // List of arguments of getMachineNode() or SelectNodeTo(). - std::vector<std::string> NodeOps; - // This is something selected from the pattern we matched. - if (!N->getName().empty()) { - const std::string &VarName = N->getName(); - std::string Val = VariableMap[VarName]; - bool ModifiedVal = false; - if (Val.empty()) { - errs() << "Variable '" << VarName << " referenced but not defined " - << "and not caught earlier!\n"; - abort(); - } - if (Val[0] == 'T' && Val[1] == 'm' && Val[2] == 'p') { - // Already selected this operand, just return the tmpval. - NodeOps.push_back(getValueName(Val)); - return NodeOps; - } - - const ComplexPattern *CP; - unsigned ResNo = TmpNo++; - if (!N->isLeaf() && N->getOperator()->getName() == "imm") { - assert(N->getExtTypes().size() == 1 && "Multiple types not handled!"); - std::string CastType; - std::string TmpVar = "Tmp" + utostr(ResNo); - switch (N->getTypeNum(0)) { - default: - errs() << "Cannot handle " << getEnumName(N->getTypeNum(0)) - << " type as an immediate constant. Aborting\n"; - abort(); - case MVT::i1: CastType = "bool"; break; - case MVT::i8: CastType = "unsigned char"; break; - case MVT::i16: CastType = "unsigned short"; break; - case MVT::i32: CastType = "unsigned"; break; - case MVT::i64: CastType = "uint64_t"; break; - } - emitCode("SDValue " + TmpVar + - " = CurDAG->getTargetConstant(((" + CastType + - ") cast<ConstantSDNode>(" + Val + ")->getZExtValue()), " + - getEnumName(N->getTypeNum(0)) + ");"); - // Add Tmp<ResNo> to VariableMap, so that we don't multiply select this - // value if used multiple times by this pattern result. - Val = TmpVar; - ModifiedVal = true; - NodeOps.push_back(getValueName(Val)); - } else if (!N->isLeaf() && N->getOperator()->getName() == "fpimm") { - assert(N->getExtTypes().size() == 1 && "Multiple types not handled!"); - std::string TmpVar = "Tmp" + utostr(ResNo); - emitCode("SDValue " + TmpVar + - " = CurDAG->getTargetConstantFP(*cast<ConstantFPSDNode>(" + - Val + ")->getConstantFPValue(), cast<ConstantFPSDNode>(" + - Val + ")->getValueType(0));"); - // Add Tmp<ResNo> to VariableMap, so that we don't multiply select this - // value if used multiple times by this pattern result. - Val = TmpVar; - ModifiedVal = true; - NodeOps.push_back(getValueName(Val)); - } else if (!N->isLeaf() && N->getOperator()->getName() == "texternalsym"){ - Record *Op = OperatorMap[N->getName()]; - // Transform ExternalSymbol to TargetExternalSymbol - if (Op && Op->getName() == "externalsym") { - std::string TmpVar = "Tmp"+utostr(ResNo); - emitCode("SDValue " + TmpVar + " = CurDAG->getTarget" - "ExternalSymbol(cast<ExternalSymbolSDNode>(" + - Val + ")->getSymbol(), " + - getEnumName(N->getTypeNum(0)) + ");"); - // Add Tmp<ResNo> to VariableMap, so that we don't multiply select - // this value if used multiple times by this pattern result. - Val = TmpVar; - ModifiedVal = true; - } - NodeOps.push_back(getValueName(Val)); - } else if (!N->isLeaf() && (N->getOperator()->getName() == "tglobaladdr" - || N->getOperator()->getName() == "tglobaltlsaddr")) { - Record *Op = OperatorMap[N->getName()]; - // Transform GlobalAddress to TargetGlobalAddress - if (Op && (Op->getName() == "globaladdr" || - Op->getName() == "globaltlsaddr")) { - std::string TmpVar = "Tmp" + utostr(ResNo); - emitCode("SDValue " + TmpVar + " = CurDAG->getTarget" - "GlobalAddress(cast<GlobalAddressSDNode>(" + Val + - ")->getGlobal(), " + getEnumName(N->getTypeNum(0)) + - ");"); - // Add Tmp<ResNo> to VariableMap, so that we don't multiply select - // this value if used multiple times by this pattern result. - Val = TmpVar; - ModifiedVal = true; - } - NodeOps.push_back(getValueName(Val)); - } else if (!N->isLeaf() - && (N->getOperator()->getName() == "texternalsym" || - N->getOperator()->getName() == "tconstpool")) { - // Do not rewrite the variable name, since we don't generate a new - // temporary. - NodeOps.push_back(getValueName(Val)); - } else if (N->isLeaf() && (CP = N->getComplexPatternInfo(CGP))) { - for (unsigned i = 0; i < CP->getNumOperands(); ++i) { - NodeOps.push_back(getValueName("CPTmp" + Val + "_" + utostr(i))); - } - } else { - // This node, probably wrapped in a SDNodeXForm, behaves like a leaf - // node even if it isn't one. Don't select it. - if (!LikeLeaf) { - if (isRoot && N->isLeaf()) { - emitCode("ReplaceUses(SDValue(N, 0), " + Val + ");"); - emitCode("return NULL;"); - } - } - NodeOps.push_back(getValueName(Val)); - } - - if (ModifiedVal) - VariableMap[VarName] = Val; - return NodeOps; - } - if (N->isLeaf()) { - // If this is an explicit register reference, handle it. - if (DefInit *DI = dynamic_cast<DefInit*>(N->getLeafValue())) { - unsigned ResNo = TmpNo++; - if (DI->getDef()->isSubClassOf("Register")) { - emitCode("SDValue Tmp" + utostr(ResNo) + " = CurDAG->getRegister(" + - getQualifiedName(DI->getDef()) + ", " + - getEnumName(N->getTypeNum(0)) + ");"); - NodeOps.push_back(getValueName("Tmp" + utostr(ResNo))); - return NodeOps; - } else if (DI->getDef()->getName() == "zero_reg") { - emitCode("SDValue Tmp" + utostr(ResNo) + - " = CurDAG->getRegister(0, " + - getEnumName(N->getTypeNum(0)) + ");"); - NodeOps.push_back(getValueName("Tmp" + utostr(ResNo))); - return NodeOps; - } else if (DI->getDef()->isSubClassOf("RegisterClass")) { - // Handle a reference to a register class. This is used - // in COPY_TO_SUBREG instructions. - emitCode("SDValue Tmp" + utostr(ResNo) + - " = CurDAG->getTargetConstant(" + - getQualifiedName(DI->getDef()) + "RegClassID, " + - "MVT::i32);"); - NodeOps.push_back(getValueName("Tmp" + utostr(ResNo))); - return NodeOps; - } - } else if (IntInit *II = dynamic_cast<IntInit*>(N->getLeafValue())) { - unsigned ResNo = TmpNo++; - assert(N->getExtTypes().size() == 1 && "Multiple types not handled!"); - emitCode("SDValue Tmp" + utostr(ResNo) + - " = CurDAG->getTargetConstant(0x" + - utohexstr((uint64_t) II->getValue()) + - "ULL, " + getEnumName(N->getTypeNum(0)) + ");"); - NodeOps.push_back(getValueName("Tmp" + utostr(ResNo))); - return NodeOps; - } - -#ifndef NDEBUG - N->dump(); -#endif - assert(0 && "Unknown leaf type!"); - return NodeOps; - } - - Record *Op = N->getOperator(); - if (Op->isSubClassOf("Instruction")) { - const CodeGenTarget &CGT = CGP.getTargetInfo(); - CodeGenInstruction &II = CGT.getInstruction(Op->getName()); - const DAGInstruction &Inst = CGP.getInstruction(Op); - const TreePattern *InstPat = Inst.getPattern(); - // FIXME: Assume actual pattern comes before "implicit". - TreePatternNode *InstPatNode = - isRoot ? (InstPat ? InstPat->getTree(0) : Pattern) - : (InstPat ? InstPat->getTree(0) : NULL); - if (InstPatNode && !InstPatNode->isLeaf() && - InstPatNode->getOperator()->getName() == "set") { - InstPatNode = InstPatNode->getChild(InstPatNode->getNumChildren()-1); - } - bool IsVariadic = isRoot && II.isVariadic; - // FIXME: fix how we deal with physical register operands. - bool HasImpInputs = isRoot && Inst.getNumImpOperands() > 0; - bool HasImpResults = isRoot && DstRegs.size() > 0; - bool NodeHasOptInFlag = isRoot && - Pattern->TreeHasProperty(SDNPOptInFlag, CGP); - bool NodeHasInFlag = isRoot && - Pattern->TreeHasProperty(SDNPInFlag, CGP); - bool NodeHasOutFlag = isRoot && - Pattern->TreeHasProperty(SDNPOutFlag, CGP); - bool NodeHasChain = InstPatNode && - InstPatNode->TreeHasProperty(SDNPHasChain, CGP); - bool InputHasChain = isRoot && Pattern->NodeHasProperty(SDNPHasChain, CGP); - unsigned NumResults = Inst.getNumResults(); - unsigned NumDstRegs = HasImpResults ? DstRegs.size() : 0; - - // Record output varargs info. - OutputIsVariadic = IsVariadic; - - if (NodeHasOptInFlag) { - emitCode("bool HasInFlag = " - "(N->getOperand(N->getNumOperands()-1).getValueType() == " - "MVT::Flag);"); - } - if (IsVariadic) - emitCode("SmallVector<SDValue, 8> Ops" + utostr(OpcNo) + ";"); - - // How many results is this pattern expected to produce? - unsigned NumPatResults = 0; - for (unsigned i = 0, e = Pattern->getExtTypes().size(); i != e; i++) { - MVT::SimpleValueType VT = Pattern->getTypeNum(i); - if (VT != MVT::isVoid && VT != MVT::Flag) - NumPatResults++; - } - - 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<SDValue, 8> InChains;"); - for (unsigned i = 0, e = OrigChains.size(); i < e; ++i) { - emitCode("if (" + OrigChains[i].first + ".getNode() != " + - OrigChains[i].second + ".getNode()) {"); - emitCode(" InChains.push_back(" + OrigChains[i].first + ");"); - emitCode("}"); - } - emitCode("InChains.push_back(" + ChainName + ");"); - emitCode(ChainName + " = CurDAG->getNode(ISD::TokenFactor, " - "N->getDebugLoc(), MVT::Other, " - "&InChains[0], InChains.size());"); - if (GenDebug) { - emitCode("CurDAG->setSubgraphColor(" + ChainName +".getNode(), \"yellow\");"); - emitCode("CurDAG->setSubgraphColor(" + ChainName +".getNode(), \"black\");"); - } - } - - // Loop over all of the operands of the instruction pattern, emitting code - // to fill them all in. The node 'N' usually has number children equal to - // the number of input operands of the instruction. However, in cases - // where there are predicate operands for an instruction, we need to fill - // in the 'execute always' values. Match up the node operands to the - // instruction operands to do this. - std::vector<std::string> AllOps; - for (unsigned ChildNo = 0, InstOpNo = NumResults; - InstOpNo != II.OperandList.size(); ++InstOpNo) { - std::vector<std::string> Ops; - - // Determine what to emit for this operand. - Record *OperandNode = II.OperandList[InstOpNo].Rec; - if ((OperandNode->isSubClassOf("PredicateOperand") || - OperandNode->isSubClassOf("OptionalDefOperand")) && - !CGP.getDefaultOperand(OperandNode).DefaultOps.empty()) { - // This is a predicate or optional def operand; emit the - // 'default ops' operands. - const DAGDefaultOperand &DefaultOp = - CGP.getDefaultOperand(II.OperandList[InstOpNo].Rec); - for (unsigned i = 0, e = DefaultOp.DefaultOps.size(); i != e; ++i) { - Ops = EmitResultCode(DefaultOp.DefaultOps[i], DstRegs, - InFlagDecled, ResNodeDecled); - AllOps.insert(AllOps.end(), Ops.begin(), Ops.end()); - } - } else { - // Otherwise this is a normal operand or a predicate operand without - // 'execute always'; emit it. - Ops = EmitResultCode(N->getChild(ChildNo), DstRegs, - InFlagDecled, ResNodeDecled); - AllOps.insert(AllOps.end(), Ops.begin(), Ops.end()); - ++ChildNo; - } - } - - // Emit all the chain and CopyToReg stuff. - bool ChainEmitted = NodeHasChain; - if (NodeHasInFlag || HasImpInputs) - EmitInFlagSelectCode(Pattern, "N", ChainEmitted, - InFlagDecled, ResNodeDecled, true); - if (NodeHasOptInFlag || NodeHasInFlag || HasImpInputs) { - if (!InFlagDecled) { - emitCode("SDValue InFlag(0, 0);"); - InFlagDecled = true; - } - if (NodeHasOptInFlag) { - emitCode("if (HasInFlag) {"); - emitCode(" InFlag = N->getOperand(N->getNumOperands()-1);"); - emitCode("}"); - } - } - - unsigned ResNo = TmpNo++; - - unsigned OpsNo = OpcNo; - std::string CodePrefix; - bool ChainAssignmentNeeded = NodeHasChain && !isRoot; - std::deque<std::string> After; - std::string NodeName; - if (!isRoot) { - NodeName = "Tmp" + utostr(ResNo); - CodePrefix = "SDValue " + NodeName + "("; - } else { - NodeName = "ResNode"; - if (!ResNodeDecled) { - CodePrefix = "SDNode *" + NodeName + " = "; - ResNodeDecled = true; - } else - CodePrefix = NodeName + " = "; - } - - std::string Code = "Opc" + utostr(OpcNo); - - if (!isRoot || (InputHasChain && !NodeHasChain)) - // For call to "getMachineNode()". - Code += ", N->getDebugLoc()"; - - 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))); - } - // Add types for implicit results in physical registers, scheduler will - // care of adding copyfromreg nodes. - for (unsigned i = 0; i < NumDstRegs; i++) { - Record *RR = DstRegs[i]; - if (RR->isSubClassOf("Register")) { - MVT::SimpleValueType RVT = getRegisterValueType(RR, CGT); - Code += ", " + getEnumName(RVT); - } - } - if (NodeHasChain) - Code += ", MVT::Other"; - if (NodeHasOutFlag) - Code += ", MVT::Flag"; - - // Inputs. - if (IsVariadic) { - for (unsigned i = 0, e = AllOps.size(); i != e; ++i) - emitCode("Ops" + utostr(OpsNo) + ".push_back(" + AllOps[i] + ");"); - AllOps.clear(); - - // Figure out whether any operands at the end of the op list are not - // part of the variable section. - std::string EndAdjust; - if (NodeHasInFlag || HasImpInputs) - EndAdjust = "-1"; // Always has one flag. - else if (NodeHasOptInFlag) - EndAdjust = "-(HasInFlag?1:0)"; // May have a flag. - - emitCode("for (unsigned i = NumInputRootOps + " + utostr(NodeHasChain) + - ", e = N->getNumOperands()" + EndAdjust + "; i != e; ++i) {"); - - emitCode(" Ops" + utostr(OpsNo) + ".push_back(N->getOperand(i));"); - emitCode("}"); - } - - // Populate MemRefs with entries for each memory accesses covered by - // this pattern. - if (isRoot && !LSI.empty()) { - std::string MemRefs = "MemRefs" + utostr(OpsNo); - emitCode("MachineSDNode::mmo_iterator " + MemRefs + " = " - "MF->allocateMemRefsArray(" + utostr(LSI.size()) + ");"); - for (unsigned i = 0, e = LSI.size(); i != e; ++i) - emitCode(MemRefs + "[" + utostr(i) + "] = " - "cast<MemSDNode>(" + LSI[i] + ")->getMemOperand();"); - After.push_back("cast<MachineSDNode>(ResNode)->setMemRefs(" + - MemRefs + ", " + MemRefs + " + " + utostr(LSI.size()) + - ");"); - } - - if (NodeHasChain) { - if (IsVariadic) - emitCode("Ops" + utostr(OpsNo) + ".push_back(" + ChainName + ");"); - else - AllOps.push_back(ChainName); - } - - if (IsVariadic) { - 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 = "SDValue 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"; - - std::vector<std::string> ReplaceFroms; - std::vector<std::string> ReplaceTos; - if (!isRoot) { - NodeOps.push_back("Tmp" + utostr(ResNo)); - } else { - - if (NodeHasOutFlag) { - if (!InFlagDecled) { - After.push_back("SDValue InFlag(ResNode, " + - utostr(NumResults+NumDstRegs+(unsigned)NodeHasChain) + - ");"); - InFlagDecled = true; - } else - After.push_back("InFlag = SDValue(ResNode, " + - utostr(NumResults+NumDstRegs+(unsigned)NodeHasChain) + - ");"); - } - - for (unsigned j = 0, e = FoldedChains.size(); j < e; j++) { - ReplaceFroms.push_back("SDValue(" + - FoldedChains[j].first + ".getNode(), " + - utostr(FoldedChains[j].second) + - ")"); - ReplaceTos.push_back("SDValue(ResNode, " + - utostr(NumResults+NumDstRegs) + ")"); - } - - if (NodeHasOutFlag) { - if (FoldedFlag.first != "") { - ReplaceFroms.push_back("SDValue(" + FoldedFlag.first + ".getNode(), " + - utostr(FoldedFlag.second) + ")"); - ReplaceTos.push_back("InFlag"); - } else { - assert(Pattern->NodeHasProperty(SDNPOutFlag, CGP)); - ReplaceFroms.push_back("SDValue(N, " + - utostr(NumPatResults + (unsigned)InputHasChain) - + ")"); - ReplaceTos.push_back("InFlag"); - } - } - - if (!ReplaceFroms.empty() && InputHasChain) { - ReplaceFroms.push_back("SDValue(N, " + - utostr(NumPatResults) + ")"); - ReplaceTos.push_back("SDValue(" + ChainName + ".getNode(), " + - ChainName + ".getResNo()" + ")"); - ChainAssignmentNeeded |= NodeHasChain; - } - - // User does not expect the instruction would produce a chain! - if ((!InputHasChain && NodeHasChain) && NodeHasOutFlag) { - ; - } else if (InputHasChain && !NodeHasChain) { - // One of the inner node produces a chain. - assert(!NodeHasOutFlag && "Node has flag but not chain!"); - ReplaceFroms.push_back("SDValue(N, " + - utostr(NumPatResults) + ")"); - ReplaceTos.push_back(ChainName); - } - } - - if (ChainAssignmentNeeded) { - // Remember which op produces the chain. - std::string ChainAssign; - if (!isRoot) - ChainAssign = ChainName + " = SDValue(" + NodeName + - ".getNode(), " + utostr(NumResults+NumDstRegs) + ");"; - else - ChainAssign = ChainName + " = SDValue(" + NodeName + - ", " + utostr(NumResults+NumDstRegs) + ");"; - - After.push_front(ChainAssign); - } - - if (ReplaceFroms.size() == 1) { - After.push_back("ReplaceUses(" + ReplaceFroms[0] + ", " + - ReplaceTos[0] + ");"); - } else if (!ReplaceFroms.empty()) { - After.push_back("const SDValue Froms[] = {"); - for (unsigned i = 0, e = ReplaceFroms.size(); i != e; ++i) - After.push_back(" " + ReplaceFroms[i] + (i + 1 != e ? "," : "")); - After.push_back("};"); - After.push_back("const SDValue Tos[] = {"); - for (unsigned i = 0, e = ReplaceFroms.size(); i != e; ++i) - After.push_back(" " + ReplaceTos[i] + (i + 1 != e ? "," : "")); - After.push_back("};"); - After.push_back("ReplaceUses(Froms, Tos, " + - itostr(ReplaceFroms.size()) + ");"); - } - - // We prefer to use SelectNodeTo since it avoids allocation when - // possible and it avoids CSE map recalculation for the node's - // users, however it's tricky to use in a non-root context. - // - // We also don't use SelectNodeTo if the pattern replacement is being - // used to jettison a chain result, since morphing the node in place - // would leave users of the chain dangling. - // - if (!isRoot || (InputHasChain && !NodeHasChain)) { - Code = "CurDAG->getMachineNode(" + Code; - } else { - Code = "CurDAG->SelectNodeTo(N, " + Code; - } - if (isRoot) { - if (After.empty()) - CodePrefix = "return "; - else - After.push_back("return ResNode;"); - } - - emitCode(CodePrefix + Code + ");"); - - if (GenDebug) { - if (!isRoot) { - emitCode("CurDAG->setSubgraphColor(" + - NodeName +".getNode(), \"yellow\");"); - emitCode("CurDAG->setSubgraphColor(" + - NodeName +".getNode(), \"black\");"); - } else { - emitCode("CurDAG->setSubgraphColor(" + NodeName +", \"yellow\");"); - emitCode("CurDAG->setSubgraphColor(" + NodeName +", \"black\");"); - } - } - - for (unsigned i = 0, e = After.size(); i != e; ++i) - emitCode(After[i]); - - return NodeOps; - } - 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. - std::vector<std::string> Ops = - EmitResultCode(N->getChild(0), DstRegs, InFlagDecled, - ResNodeDecled, true); - unsigned ResNo = TmpNo++; - emitCode("SDValue Tmp" + utostr(ResNo) + " = Transform_" + Op->getName() - + "(" + Ops.back() + ".getNode());"); - NodeOps.push_back("Tmp" + utostr(ResNo)); - if (isRoot) - emitCode("return Tmp" + utostr(ResNo) + ".getNode();"); - return NodeOps; - } - - N->dump(); - errs() << "\n"; - throw std::string("Unknown node in result pattern!"); -} - - -/// EmitCodeForPattern - Given a pattern to match, emit code to the specified -/// stream to match the pattern, and generate the code for the match if it -/// succeeds. Returns true if the pattern is not guaranteed to match. -void DAGISelEmitter::GenerateCodeForPattern(const PatternToMatch &Pattern, - std::vector<std::pair<unsigned, std::string> > &GeneratedCode, - std::set<std::string> &GeneratedDecl, - std::vector<std::string> &TargetOpcodes, - std::vector<std::string> &TargetVTs, - bool &OutputIsVariadic, - unsigned &NumInputRootOps) { - OutputIsVariadic = false; - NumInputRootOps = 0; - - PatternCodeEmitter Emitter(CGP, Pattern.getPredicateCheck(), - Pattern.getSrcPattern(), Pattern.getDstPattern(), - GeneratedCode, GeneratedDecl, - TargetOpcodes, TargetVTs, - OutputIsVariadic, NumInputRootOps); - - // Emit the matcher, capturing named arguments in VariableMap. - bool FoundChain = false; - Emitter.EmitMatchCode(Pattern.getSrcPattern(), NULL, "N", "", FoundChain); - - // TP - Get *SOME* tree pattern, we don't care which. It is only used for - // diagnostics, which we know are impossible at this point. - TreePattern &TP = *CGP.pf_begin()->second; - - // At this point, we know that we structurally match the pattern, but the - // types of the nodes may not match. Figure out the fewest number of type - // comparisons we need to emit. For example, if there is only one integer - // type supported by a target, there should be no type comparisons at all for - // integer patterns! - // - // To figure out the fewest number of type checks needed, clone the pattern, - // remove the types, then perform type inference on the pattern as a whole. - // If there are unresolved types, emit an explicit check for those types, - // apply the type to the tree, then rerun type inference. Iterate until all - // types are resolved. - // - TreePatternNode *Pat = Pattern.getSrcPattern()->clone(); - Pat->RemoveAllTypes(); - - do { - // Resolve/propagate as many types as possible. - try { - bool MadeChange = true; - while (MadeChange) - MadeChange = Pat->ApplyTypeConstraints(TP, - true/*Ignore reg constraints*/); - } catch (...) { - assert(0 && "Error: could not find consistent types for something we" - " already decided was ok!"); - abort(); - } - - // 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", true)); - - Emitter.EmitResultCode(Pattern.getDstPattern(), Pattern.getDstRegs(), - false, false, false, true); - delete Pat; -} - -/// EraseCodeLine - Erase one code line from all of the patterns. If removing -/// a line causes any of them to be empty, remove them and return true when -/// done. -static bool EraseCodeLine(std::vector<std::pair<const PatternToMatch*, - std::vector<std::pair<unsigned, std::string> > > > - &Patterns) { - bool ErasedPatterns = false; - for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { - Patterns[i].second.pop_back(); - if (Patterns[i].second.empty()) { - Patterns.erase(Patterns.begin()+i); - --i; --e; - ErasedPatterns = true; - } - } - return ErasedPatterns; -} - -/// EmitPatterns - Emit code for at least one pattern, but try to group common -/// code together between the patterns. -void DAGISelEmitter::EmitPatterns(std::vector<std::pair<const PatternToMatch*, - std::vector<std::pair<unsigned, std::string> > > > - &Patterns, unsigned Indent, - raw_ostream &OS) { - typedef std::pair<unsigned, std::string> CodeLine; - typedef std::vector<CodeLine> CodeList; - typedef std::vector<std::pair<const PatternToMatch*, CodeList> > PatternList; - - if (Patterns.empty()) return; - - // Figure out how many patterns share the next code line. Explicitly copy - // FirstCodeLine so that we don't invalidate a reference when changing - // Patterns. - const CodeLine FirstCodeLine = Patterns.back().second.back(); - unsigned LastMatch = Patterns.size()-1; - while (LastMatch != 0 && Patterns[LastMatch-1].second.back() == FirstCodeLine) - --LastMatch; - - // If not all patterns share this line, split the list into two pieces. The - // first chunk will use this line, the second chunk won't. - if (LastMatch != 0) { - PatternList Shared(Patterns.begin()+LastMatch, Patterns.end()); - PatternList Other(Patterns.begin(), Patterns.begin()+LastMatch); - - // FIXME: Emit braces? - if (Shared.size() == 1) { - const PatternToMatch &Pattern = *Shared.back().first; - OS << "\n" << std::string(Indent, ' ') << "// Pattern: "; - Pattern.getSrcPattern()->print(OS); - OS << "\n" << std::string(Indent, ' ') << "// Emits: "; - Pattern.getDstPattern()->print(OS); - OS << "\n"; - unsigned AddedComplexity = Pattern.getAddedComplexity(); - OS << std::string(Indent, ' ') << "// Pattern complexity = " - << getPatternSize(Pattern.getSrcPattern(), CGP) + AddedComplexity - << " cost = " - << getResultPatternCost(Pattern.getDstPattern(), CGP) - << " size = " - << getResultPatternSize(Pattern.getDstPattern(), CGP) << "\n"; - } - if (FirstCodeLine.first != 1) { - OS << std::string(Indent, ' ') << "{\n"; - Indent += 2; - } - EmitPatterns(Shared, Indent, OS); - if (FirstCodeLine.first != 1) { - Indent -= 2; - OS << std::string(Indent, ' ') << "}\n"; - } + bool operator()(const PatternToMatch *LHS, + const PatternToMatch *RHS) { + unsigned LHSSize = getPatternSize(LHS->getSrcPattern(), CGP); + unsigned RHSSize = getPatternSize(RHS->getSrcPattern(), CGP); + LHSSize += LHS->getAddedComplexity(); + RHSSize += RHS->getAddedComplexity(); + if (LHSSize > RHSSize) return true; // LHS -> bigger -> less cost + if (LHSSize < RHSSize) return false; - if (Other.size() == 1) { - const PatternToMatch &Pattern = *Other.back().first; - OS << "\n" << std::string(Indent, ' ') << "// Pattern: "; - Pattern.getSrcPattern()->print(OS); - OS << "\n" << std::string(Indent, ' ') << "// Emits: "; - Pattern.getDstPattern()->print(OS); - OS << "\n"; - unsigned AddedComplexity = Pattern.getAddedComplexity(); - OS << std::string(Indent, ' ') << "// Pattern complexity = " - << getPatternSize(Pattern.getSrcPattern(), CGP) + AddedComplexity - << " cost = " - << getResultPatternCost(Pattern.getDstPattern(), CGP) - << " size = " - << getResultPatternSize(Pattern.getDstPattern(), CGP) << "\n"; - } - EmitPatterns(Other, Indent, OS); - return; - } - - // Remove this code from all of the patterns that share it. - bool ErasedPatterns = EraseCodeLine(Patterns); - - bool isPredicate = FirstCodeLine.first == 1; - - // Otherwise, every pattern in the list has this line. Emit it. - if (!isPredicate) { - // Normal code. - OS << std::string(Indent, ' ') << FirstCodeLine.second << "\n"; - } else { - OS << std::string(Indent, ' ') << "if (" << FirstCodeLine.second; + // If the patterns have equal complexity, compare generated instruction cost + unsigned LHSCost = getResultPatternCost(LHS->getDstPattern(), CGP); + unsigned RHSCost = getResultPatternCost(RHS->getDstPattern(), CGP); + if (LHSCost < RHSCost) return true; + if (LHSCost > RHSCost) return false; - // If the next code line is another predicate, and if all of the pattern - // in this group share the same next line, emit it inline now. Do this - // until we run out of common predicates. - while (!ErasedPatterns && Patterns.back().second.back().first == 1) { - // Check that all of the patterns in Patterns end with the same predicate. - bool AllEndWithSamePredicate = true; - for (unsigned i = 0, e = Patterns.size(); i != e; ++i) - if (Patterns[i].second.back() != Patterns.back().second.back()) { - AllEndWithSamePredicate = false; - break; - } - // If all of the predicates aren't the same, we can't share them. - if (!AllEndWithSamePredicate) break; - - // Otherwise we can. Emit it shared now. - OS << " &&\n" << std::string(Indent+4, ' ') - << Patterns.back().second.back().second; - ErasedPatterns = EraseCodeLine(Patterns); - } + unsigned LHSPatSize = getResultPatternSize(LHS->getDstPattern(), CGP); + unsigned RHSPatSize = getResultPatternSize(RHS->getDstPattern(), CGP); + if (LHSPatSize < RHSPatSize) return true; + if (LHSPatSize > RHSPatSize) return false; - OS << ") {\n"; - Indent += 2; + // Sort based on the UID of the pattern, giving us a deterministic ordering. + assert(LHS == RHS || LHS->ID != RHS->ID); + return LHS->ID < RHS->ID; } - - EmitPatterns(Patterns, Indent, OS); - - if (isPredicate) - OS << std::string(Indent-2, ' ') << "}\n"; -} - -static std::string getLegalCName(std::string OpName) { - std::string::size_type pos = OpName.find("::"); - if (pos != std::string::npos) - OpName.replace(pos, 2, "_"); - return OpName; +}; } -void DAGISelEmitter::EmitInstructionSelector(raw_ostream &OS) { - const CodeGenTarget &Target = CGP.getTargetInfo(); - - // Get the namespace to insert instructions into. - std::string InstNS = Target.getInstNamespace(); - if (!InstNS.empty()) InstNS += "::"; - - // Group the patterns by their top-level opcodes. - std::map<std::string, std::vector<const PatternToMatch*> > PatternsByOpcode; - // All unique target node emission functions. - std::map<std::string, unsigned> EmitFunctions; - for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), - E = CGP.ptm_end(); I != E; ++I) { - const PatternToMatch &Pattern = *I; - TreePatternNode *Node = Pattern.getSrcPattern(); - if (!Node->isLeaf()) { - PatternsByOpcode[getOpcodeName(Node->getOperator(), CGP)]. - push_back(&Pattern); - } else { - const ComplexPattern *CP; - if (dynamic_cast<IntInit*>(Node->getLeafValue())) { - PatternsByOpcode[getOpcodeName(CGP.getSDNodeNamed("imm"), CGP)]. - push_back(&Pattern); - } else if ((CP = Node->getComplexPatternInfo(CGP))) { - std::vector<Record*> OpNodes = CP->getRootNodes(); - for (unsigned j = 0, e = OpNodes.size(); j != e; j++) { - PatternsByOpcode[getOpcodeName(OpNodes[j], CGP)] - .insert(PatternsByOpcode[getOpcodeName(OpNodes[j], CGP)].begin(), - &Pattern); - } - } else { - errs() << "Unrecognized opcode '"; - Node->dump(); - errs() << "' on tree pattern '"; - errs() << Pattern.getDstPattern()->getOperator()->getName() << "'!\n"; - exit(1); - } - } - } - - // 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<std::string, std::vector<std::string> > 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. - for (std::map<std::string, std::vector<const PatternToMatch*> >::iterator - PBOI = PatternsByOpcode.begin(), E = PatternsByOpcode.end(); - PBOI != E; ++PBOI) { - const std::string &OpName = PBOI->first; - std::vector<const PatternToMatch*> &PatternsOfOp = PBOI->second; - assert(!PatternsOfOp.empty() && "No patterns but map has entry?"); - - // Split them into groups by type. - std::map<MVT::SimpleValueType, - std::vector<const PatternToMatch*> > PatternsByType; - for (unsigned i = 0, e = PatternsOfOp.size(); i != e; ++i) { - const PatternToMatch *Pat = PatternsOfOp[i]; - TreePatternNode *SrcPat = Pat->getSrcPattern(); - PatternsByType[SrcPat->getTypeNum(0)].push_back(Pat); - } - - for (std::map<MVT::SimpleValueType, - std::vector<const PatternToMatch*> >::iterator - II = PatternsByType.begin(), EE = PatternsByType.end(); II != EE; - ++II) { - MVT::SimpleValueType OpVT = II->first; - std::vector<const PatternToMatch*> &Patterns = II->second; - typedef std::pair<unsigned, std::string> CodeLine; - typedef std::vector<CodeLine> CodeList; - typedef CodeList::iterator CodeListI; - - std::vector<std::pair<const PatternToMatch*, CodeList> > CodeForPatterns; - std::vector<std::vector<std::string> > PatternOpcodes; - std::vector<std::vector<std::string> > PatternVTs; - std::vector<std::set<std::string> > PatternDecls; - std::vector<bool> OutputIsVariadicFlags; - std::vector<unsigned> NumInputRootOpsCounts; - for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { - CodeList GeneratedCode; - std::set<std::string> GeneratedDecl; - std::vector<std::string> TargetOpcodes; - std::vector<std::string> TargetVTs; - bool OutputIsVariadic; - unsigned NumInputRootOps; - GenerateCodeForPattern(*Patterns[i], GeneratedCode, GeneratedDecl, - TargetOpcodes, TargetVTs, - OutputIsVariadic, NumInputRootOps); - CodeForPatterns.push_back(std::make_pair(Patterns[i], GeneratedCode)); - PatternDecls.push_back(GeneratedDecl); - PatternOpcodes.push_back(TargetOpcodes); - PatternVTs.push_back(TargetVTs); - OutputIsVariadicFlags.push_back(OutputIsVariadic); - NumInputRootOpsCounts.push_back(NumInputRootOps); - } - - // 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<std::string> &TargetOpcodes = PatternOpcodes[i]; - std::vector<std::string> &TargetVTs = PatternVTs[i]; - std::set<std::string> Decls = PatternDecls[i]; - bool OutputIsVariadic = OutputIsVariadicFlags[i]; - unsigned NumInputRootOps = NumInputRootOpsCounts[i]; - std::vector<std::string> AddedInits; - int CodeSize = (int)GeneratedCode.size(); - int LastPred = -1; - for (int j = CodeSize-1; j >= 0; --j) { - if (LastPred == -1 && GeneratedCode[j].first == 1) - LastPred = j; - else if (LastPred != -1 && GeneratedCode[j].first == 2) - AddedInits.push_back(GeneratedCode[j].second); - } - - std::string CalleeCode = "(SDNode *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::SimpleValueType VT" + utostr(j); - CallerCode += ", " + TargetVTs[j]; - } - for (std::set<std::string>::iterator - I = Decls.begin(), E = Decls.end(); I != E; ++I) { - std::string Name = *I; - CalleeCode += ", SDValue &" + Name; - CallerCode += ", " + Name; - } - - if (OutputIsVariadic) { - CalleeCode += ", unsigned NumInputRootOps"; - CallerCode += ", " + utostr(NumInputRootOps); - } - - CallerCode += ");"; - CalleeCode += ") {\n"; - - for (std::vector<std::string>::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<std::string, unsigned>::iterator EFI = - EmitFunctions.find(CalleeCode); - if (EFI != EmitFunctions.end()) { - EmitFuncNum = EFI->second; - } else { - EmitFuncNum = EmitFunctions.size(); - EmitFunctions.insert(std::make_pair(CalleeCode, EmitFuncNum)); - // Prevent emission routines from being inlined to reduce selection - // routines stack frame sizes. - OS << "DISABLE_INLINE "; - OS << "SDNode *Emit_" << utostr(EmitFuncNum) << CalleeCode; - } - - // Replace the emission code within selection routines with calls to the - // emission functions. - if (GenDebug) - GeneratedCode.push_back(std::make_pair(0, "CurDAG->setSubgraphColor(N, \"red\");")); - CallerCode = "SDNode *Result = Emit_" + utostr(EmitFuncNum) + CallerCode; - GeneratedCode.push_back(std::make_pair(3, CallerCode)); - if (GenDebug) { - GeneratedCode.push_back(std::make_pair(0, "if(Result) {")); - GeneratedCode.push_back(std::make_pair(0, " CurDAG->setSubgraphColor(Result, \"yellow\");")); - GeneratedCode.push_back(std::make_pair(0, " CurDAG->setSubgraphColor(Result, \"black\");")); - GeneratedCode.push_back(std::make_pair(0, "}")); - //GeneratedCode.push_back(std::make_pair(0, "CurDAG->setSubgraphColor(N, \"black\");")); - } - GeneratedCode.push_back(std::make_pair(0, "return Result;")); - } - - // Print function. - std::string OpVTStr; - if (OpVT == MVT::iPTR) { - OpVTStr = "_iPTR"; - } else if (OpVT == MVT::iPTRAny) { - OpVTStr = "_iPTRAny"; - } else if (OpVT == MVT::isVoid) { - // Nodes with a void result actually have a first result type of either - // Other (a chain) or Flag. Since there is no one-to-one mapping from - // void to this case, we handle it specially here. - } else { - OpVTStr = "_" + getEnumName(OpVT).substr(5); // Skip 'MVT::' - } - std::map<std::string, std::vector<std::string> >::iterator OpVTI = - OpcodeVTMap.find(OpName); - if (OpVTI == OpcodeVTMap.end()) { - std::vector<std::string> VTSet; - VTSet.push_back(OpVTStr); - OpcodeVTMap.insert(std::make_pair(OpName, VTSet)); - } else - OpVTI->second.push_back(OpVTStr); - - // 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(CodeForPatterns.begin(), CodeForPatterns.end(), - PatternSortingPredicate(CGP)); - - // 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) { - errs() << "Pattern '"; - CodeForPatterns[i].first->getSrcPattern()->print(errs()); - errs() << "' is impossible to select!\n"; - exit(1); - } - } - - // 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()); - - OS << "SDNode *Select_" << getLegalCName(OpName) - << OpVTStr << "(SDNode *N) {\n"; - - // 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 << "\n"; - if (OpName != "ISD::INTRINSIC_W_CHAIN" && - OpName != "ISD::INTRINSIC_WO_CHAIN" && - OpName != "ISD::INTRINSIC_VOID") - OS << " CannotYetSelect(N);\n"; - else - OS << " CannotYetSelectIntrinsic(N);\n"; - - OS << " return NULL;\n"; - } - OS << "}\n\n"; - } - } - - OS << "// The main instruction selector code.\n" - << "SDNode *SelectCode(SDNode *N) {\n" - << " MVT::SimpleValueType NVT = N->getValueType(0).getSimpleVT().SimpleTy;\n" - << " switch (N->getOpcode()) {\n" - << " default:\n" - << " assert(!N->isMachineOpcode() && \"Node already selected!\");\n" - << " break;\n" - << " case ISD::EntryToken: // These nodes remain the same.\n" - << " case ISD::BasicBlock:\n" - << " case ISD::Register:\n" - << " case ISD::HANDLENODE:\n" - << " case ISD::TargetConstant:\n" - << " case ISD::TargetConstantFP:\n" - << " case ISD::TargetConstantPool:\n" - << " case ISD::TargetFrameIndex:\n" - << " case ISD::TargetExternalSymbol:\n" - << " case ISD::TargetBlockAddress:\n" - << " case ISD::TargetJumpTable:\n" - << " case ISD::TargetGlobalTLSAddress:\n" - << " case ISD::TargetGlobalAddress:\n" - << " case ISD::TokenFactor:\n" - << " case ISD::CopyFromReg:\n" - << " case ISD::CopyToReg: {\n" - << " return NULL;\n" - << " }\n" - << " case ISD::AssertSext:\n" - << " case ISD::AssertZext: {\n" - << " ReplaceUses(SDValue(N, 0), N->getOperand(0));\n" - << " return NULL;\n" - << " }\n" - << " case ISD::INLINEASM: return Select_INLINEASM(N);\n" - << " case ISD::EH_LABEL: return Select_EH_LABEL(N);\n" - << " case ISD::UNDEF: return Select_UNDEF(N);\n"; - - // Loop over all of the case statements, emiting a call to each method we - // emitted above. - for (std::map<std::string, std::vector<const PatternToMatch*> >::iterator - PBOI = PatternsByOpcode.begin(), E = PatternsByOpcode.end(); - PBOI != E; ++PBOI) { - const std::string &OpName = PBOI->first; - // 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<std::string, std::vector<std::string> >::iterator OpVTI = - OpcodeVTMap.find(OpName); - std::vector<std::string> &OpVTs = OpVTI->second; - OS << " case " << OpName << ": {\n"; - // If we have only one variant and it's the default, elide the - // switch. Marginally faster, and makes MSVC happier. - if (OpVTs.size()==1 && OpVTs[0].empty()) { - OS << " return Select_" << getLegalCName(OpName) << "(N);\n"; - OS << " break;\n"; - OS << " }\n"; - continue; - } - // Keep track of whether we see a pattern that has an iPtr result. - bool HasPtrPattern = false; - bool HasDefaultPattern = false; - - OS << " switch (NVT) {\n"; - for (unsigned i = 0, e = OpVTs.size(); i < e; ++i) { - std::string &VTStr = OpVTs[i]; - if (VTStr.empty()) { - HasDefaultPattern = true; - continue; - } - - // If this is a match on iPTR: don't emit it directly, we need special - // code. - if (VTStr == "_iPTR") { - HasPtrPattern = true; - continue; - } - OS << " case MVT::" << VTStr.substr(1) << ":\n" - << " return Select_" << getLegalCName(OpName) - << VTStr << "(N);\n"; - } - OS << " default:\n"; - - // If there is an iPTR result version of this pattern, emit it here. - if (HasPtrPattern) { - OS << " if (TLI.getPointerTy() == NVT)\n"; - OS << " return Select_" << getLegalCName(OpName) <<"_iPTR(N);\n"; - } - if (HasDefaultPattern) { - OS << " return Select_" << getLegalCName(OpName) << "(N);\n"; - } - OS << " break;\n"; - OS << " }\n"; - OS << " break;\n"; - OS << " }\n"; - } - - OS << " } // end of big switch.\n\n" - << " if (N->getOpcode() != ISD::INTRINSIC_W_CHAIN &&\n" - << " N->getOpcode() != ISD::INTRINSIC_WO_CHAIN &&\n" - << " N->getOpcode() != ISD::INTRINSIC_VOID) {\n" - << " CannotYetSelect(N);\n" - << " } else {\n" - << " CannotYetSelectIntrinsic(N);\n" - << " }\n" - << " return NULL;\n" - << "}\n\n"; -} void DAGISelEmitter::run(raw_ostream &OS) { EmitSourceFileHeader("DAG Instruction Selector for the " + @@ -1978,46 +195,45 @@ void DAGISelEmitter::run(raw_ostream &OS) { << "// *** instruction selector class. These functions are really " << "methods.\n\n"; - OS << "// Include standard, target-independent definitions and methods used\n" - << "// by the instruction selector.\n"; - OS << "#include \"llvm/CodeGen/DAGISelHeader.h\"\n\n"; - - EmitNodeTransforms(OS); + DEBUG(errs() << "\n\nALL PATTERNS TO MATCH:\n\n"; + for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), + E = CGP.ptm_end(); I != E; ++I) { + errs() << "PATTERN: "; I->getSrcPattern()->dump(); + errs() << "\nRESULT: "; I->getDstPattern()->dump(); + errs() << "\n"; + }); + + // FIXME: These are being used by hand written code, gross. EmitPredicateFunctions(OS); - - DEBUG(errs() << "\n\nALL PATTERNS TO MATCH:\n\n"); + + // Add all the patterns to a temporary list so we can sort them. + std::vector<const PatternToMatch*> Patterns; for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), E = CGP.ptm_end(); - I != E; ++I) { - DEBUG(errs() << "PATTERN: "; I->getSrcPattern()->dump()); - DEBUG(errs() << "\nRESULT: "; I->getDstPattern()->dump()); - DEBUG(errs() << "\n"); - } + I != E; ++I) + Patterns.push_back(&*I); + + // We want to process the matches in order of minimal cost. Sort the patterns + // so the least cost one is at the start. + std::stable_sort(Patterns.begin(), Patterns.end(), + PatternSortingPredicate(CGP)); - // At this point, we have full information about the 'Patterns' we need to - // parse, both implicitly from instructions as well as from explicit pattern - // definitions. Emit the resultant instruction selector. - EmitInstructionSelector(OS); -#if 0 - MatcherNode *Matcher = 0; - // Walk the patterns backwards, building a matcher for each and adding it to - // the matcher for the whole target. - for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), - E = CGP.ptm_end(); I != E;) { - const PatternToMatch &Pattern = *--E; - MatcherNode *N = ConvertPatternToMatcher(Pattern, CGP); - - if (Matcher == 0) - Matcher = N; - else - Matcher = new PushMatcherNode(N, Matcher); + // Convert each variant of each pattern into a Matcher. + std::vector<Matcher*> PatternMatchers; + for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { + for (unsigned Variant = 0; ; ++Variant) { + if (Matcher *M = ConvertPatternToMatcher(*Patterns[i], Variant, CGP)) + PatternMatchers.push_back(M); + else + break; + } } - - - EmitMatcherTable(Matcher, OS); - - + + Matcher *TheMatcher = new ScopeMatcher(&PatternMatchers[0], + PatternMatchers.size()); + + TheMatcher = OptimizeMatcher(TheMatcher, CGP); //Matcher->dump(); - delete Matcher; -#endif + EmitMatcherTable(TheMatcher, CGP, OS); + delete TheMatcher; } diff --git a/utils/TableGen/DAGISelEmitter.h b/utils/TableGen/DAGISelEmitter.h index d5b889b..5ffdde8 100644 --- a/utils/TableGen/DAGISelEmitter.h +++ b/utils/TableGen/DAGISelEmitter.h @@ -31,24 +31,8 @@ public: // run - Output the isel, returning true on failure. void run(raw_ostream &OS); - - private: - void EmitNodeTransforms(raw_ostream &OS); void EmitPredicateFunctions(raw_ostream &OS); - - void GenerateCodeForPattern(const PatternToMatch &Pattern, - std::vector<std::pair<unsigned, std::string> > &GeneratedCode, - std::set<std::string> &GeneratedDecl, - std::vector<std::string> &TargetOpcodes, - std::vector<std::string> &TargetVTs, - bool &OutputIsVariadic, - unsigned &NumInputRootOps); - void EmitPatterns(std::vector<std::pair<const PatternToMatch*, - std::vector<std::pair<unsigned, std::string> > > > &Patterns, - unsigned Indent, raw_ostream &OS); - - void EmitInstructionSelector(raw_ostream &OS); }; } // End llvm namespace diff --git a/utils/TableGen/DAGISelMatcher.cpp b/utils/TableGen/DAGISelMatcher.cpp index 3f75558..c4f1cbf 100644 --- a/utils/TableGen/DAGISelMatcher.cpp +++ b/utils/TableGen/DAGISelMatcher.cpp @@ -10,109 +10,338 @@ #include "DAGISelMatcher.h" #include "CodeGenDAGPatterns.h" #include "CodeGenTarget.h" +#include "Record.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/ADT/StringExtras.h" using namespace llvm; -void MatcherNode::dump() const { - print(errs()); +void Matcher::dump() const { + print(errs(), 0); } -void EmitNodeMatcherNode::print(raw_ostream &OS, unsigned indent) const { - OS.indent(indent) << "EmitNode: Src = " << *Pattern.getSrcPattern() << "\n"; - OS.indent(indent) << "EmitNode: Dst = " << *Pattern.getDstPattern() << "\n"; +void Matcher::print(raw_ostream &OS, unsigned indent) const { + printImpl(OS, indent); + if (Next) + return Next->print(OS, indent); } -void MatcherNodeWithChild::printChild(raw_ostream &OS, unsigned indent) const { - if (Child) - return Child->print(OS, indent); - OS.indent(indent) << "<null child>\n"; +void Matcher::printOne(raw_ostream &OS) const { + printImpl(OS, 0); } +ScopeMatcher::~ScopeMatcher() { + for (unsigned i = 0, e = Children.size(); i != e; ++i) + delete Children[i]; +} + + +// printImpl methods. -void PushMatcherNode::print(raw_ostream &OS, unsigned indent) const { - OS.indent(indent) << "Push\n"; - printChild(OS, indent+2); - Failure->print(OS, indent); +void ScopeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { + OS.indent(indent) << "Scope\n"; + for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { + if (getChild(i) == 0) + OS.indent(indent+1) << "NULL POINTER\n"; + else + getChild(i)->print(OS, indent+2); + } } -void RecordMatcherNode::print(raw_ostream &OS, unsigned indent) const { +void RecordMatcher::printImpl(raw_ostream &OS, unsigned indent) const { OS.indent(indent) << "Record\n"; - printChild(OS, indent); } -void MoveChildMatcherNode::print(raw_ostream &OS, unsigned indent) const { +void RecordChildMatcher::printImpl(raw_ostream &OS, unsigned indent) const { + OS.indent(indent) << "RecordChild: " << ChildNo << '\n'; +} + +void RecordMemRefMatcher::printImpl(raw_ostream &OS, unsigned indent) const { + OS.indent(indent) << "RecordMemRef\n"; +} + +void CaptureFlagInputMatcher::printImpl(raw_ostream &OS, unsigned indent) const{ + OS.indent(indent) << "CaptureFlagInput\n"; +} + +void MoveChildMatcher::printImpl(raw_ostream &OS, unsigned indent) const { OS.indent(indent) << "MoveChild " << ChildNo << '\n'; - printChild(OS, indent); } -void MoveParentMatcherNode::print(raw_ostream &OS, unsigned indent) const { +void MoveParentMatcher::printImpl(raw_ostream &OS, unsigned indent) const { OS.indent(indent) << "MoveParent\n"; - printChild(OS, indent); } -void CheckSameMatcherNode::print(raw_ostream &OS, unsigned indent) const { +void CheckSameMatcher::printImpl(raw_ostream &OS, unsigned indent) const { OS.indent(indent) << "CheckSame " << MatchNumber << '\n'; - printChild(OS, indent); } -void CheckPatternPredicateMatcherNode:: -print(raw_ostream &OS, unsigned indent) const { +void CheckPatternPredicateMatcher:: +printImpl(raw_ostream &OS, unsigned indent) const { OS.indent(indent) << "CheckPatternPredicate " << Predicate << '\n'; - printChild(OS, indent); } -void CheckPredicateMatcherNode::print(raw_ostream &OS, unsigned indent) const { +void CheckPredicateMatcher::printImpl(raw_ostream &OS, unsigned indent) const { OS.indent(indent) << "CheckPredicate " << PredName << '\n'; - printChild(OS, indent); } -void CheckOpcodeMatcherNode::print(raw_ostream &OS, unsigned indent) const { - OS.indent(indent) << "CheckOpcode " << OpcodeName << '\n'; - printChild(OS, indent); +void CheckOpcodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { + OS.indent(indent) << "CheckOpcode " << Opcode.getEnumName() << '\n'; } -void CheckTypeMatcherNode::print(raw_ostream &OS, unsigned indent) const { +void SwitchOpcodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { + OS.indent(indent) << "SwitchOpcode: {\n"; + for (unsigned i = 0, e = Cases.size(); i != e; ++i) { + OS.indent(indent) << "case " << Cases[i].first->getEnumName() << ":\n"; + Cases[i].second->print(OS, indent+2); + } + OS.indent(indent) << "}\n"; +} + + +void CheckTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { OS.indent(indent) << "CheckType " << getEnumName(Type) << '\n'; - printChild(OS, indent); } -void CheckIntegerMatcherNode::print(raw_ostream &OS, unsigned indent) const { +void SwitchTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { + OS.indent(indent) << "SwitchType: {\n"; + for (unsigned i = 0, e = Cases.size(); i != e; ++i) { + OS.indent(indent) << "case " << getEnumName(Cases[i].first) << ":\n"; + Cases[i].second->print(OS, indent+2); + } + OS.indent(indent) << "}\n"; +} + +void CheckChildTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { + OS.indent(indent) << "CheckChildType " << ChildNo << " " + << getEnumName(Type) << '\n'; +} + + +void CheckIntegerMatcher::printImpl(raw_ostream &OS, unsigned indent) const { OS.indent(indent) << "CheckInteger " << Value << '\n'; - printChild(OS, indent); } -void CheckCondCodeMatcherNode::print(raw_ostream &OS, unsigned indent) const { +void CheckCondCodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { OS.indent(indent) << "CheckCondCode ISD::" << CondCodeName << '\n'; - printChild(OS, indent); } -void CheckValueTypeMatcherNode::print(raw_ostream &OS, unsigned indent) const { +void CheckValueTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { OS.indent(indent) << "CheckValueType MVT::" << TypeName << '\n'; - printChild(OS, indent); } -void CheckComplexPatMatcherNode::print(raw_ostream &OS, unsigned indent) const { +void CheckComplexPatMatcher::printImpl(raw_ostream &OS, unsigned indent) const { OS.indent(indent) << "CheckComplexPat " << Pattern.getSelectFunc() << '\n'; - printChild(OS, indent); } -void CheckAndImmMatcherNode::print(raw_ostream &OS, unsigned indent) const { +void CheckAndImmMatcher::printImpl(raw_ostream &OS, unsigned indent) const { OS.indent(indent) << "CheckAndImm " << Value << '\n'; - printChild(OS, indent); } -void CheckOrImmMatcherNode::print(raw_ostream &OS, unsigned indent) const { +void CheckOrImmMatcher::printImpl(raw_ostream &OS, unsigned indent) const { OS.indent(indent) << "CheckOrImm " << Value << '\n'; - printChild(OS, indent); } -void CheckProfitableToFoldMatcherNode::print(raw_ostream &OS, - unsigned indent) const { - OS.indent(indent) << "CheckProfitableToFold\n"; - printChild(OS, indent); +void CheckFoldableChainNodeMatcher::printImpl(raw_ostream &OS, + unsigned indent) const { + OS.indent(indent) << "CheckFoldableChainNode\n"; +} + +void EmitIntegerMatcher::printImpl(raw_ostream &OS, unsigned indent) const { + OS.indent(indent) << "EmitInteger " << Val << " VT=" << VT << '\n'; +} + +void EmitStringIntegerMatcher:: +printImpl(raw_ostream &OS, unsigned indent) const { + OS.indent(indent) << "EmitStringInteger " << Val << " VT=" << VT << '\n'; +} + +void EmitRegisterMatcher::printImpl(raw_ostream &OS, unsigned indent) const { + OS.indent(indent) << "EmitRegister "; + if (Reg) + OS << Reg->getName(); + else + OS << "zero_reg"; + OS << " VT=" << VT << '\n'; +} + +void EmitConvertToTargetMatcher:: +printImpl(raw_ostream &OS, unsigned indent) const { + OS.indent(indent) << "EmitConvertToTarget " << Slot << '\n'; +} + +void EmitMergeInputChainsMatcher:: +printImpl(raw_ostream &OS, unsigned indent) const { + OS.indent(indent) << "EmitMergeInputChains <todo: args>\n"; +} + +void EmitCopyToRegMatcher::printImpl(raw_ostream &OS, unsigned indent) const { + OS.indent(indent) << "EmitCopyToReg <todo: args>\n"; +} + +void EmitNodeXFormMatcher::printImpl(raw_ostream &OS, unsigned indent) const { + OS.indent(indent) << "EmitNodeXForm " << NodeXForm->getName() + << " Slot=" << Slot << '\n'; +} + + +void EmitNodeMatcherCommon::printImpl(raw_ostream &OS, unsigned indent) const { + OS.indent(indent); + OS << (isa<MorphNodeToMatcher>(this) ? "MorphNodeTo: " : "EmitNode: ") + << OpcodeName << ": <todo flags> "; + + for (unsigned i = 0, e = VTs.size(); i != e; ++i) + OS << ' ' << getEnumName(VTs[i]); + OS << '('; + for (unsigned i = 0, e = Operands.size(); i != e; ++i) + OS << Operands[i] << ' '; + OS << ")\n"; +} + +void MarkFlagResultsMatcher::printImpl(raw_ostream &OS, unsigned indent) const { + OS.indent(indent) << "MarkFlagResults <todo: args>\n"; +} + +void CompleteMatchMatcher::printImpl(raw_ostream &OS, unsigned indent) const { + OS.indent(indent) << "CompleteMatch <todo args>\n"; + OS.indent(indent) << "Src = " << *Pattern.getSrcPattern() << "\n"; + OS.indent(indent) << "Dst = " << *Pattern.getDstPattern() << "\n"; +} + +// getHashImpl Implementation. + +unsigned CheckPatternPredicateMatcher::getHashImpl() const { + return HashString(Predicate); +} + +unsigned CheckPredicateMatcher::getHashImpl() const { + return HashString(PredName); +} + +unsigned CheckOpcodeMatcher::getHashImpl() const { + return HashString(Opcode.getEnumName()); +} + +unsigned CheckCondCodeMatcher::getHashImpl() const { + return HashString(CondCodeName); +} + +unsigned CheckValueTypeMatcher::getHashImpl() const { + return HashString(TypeName); +} + +unsigned EmitStringIntegerMatcher::getHashImpl() const { + return HashString(Val) ^ VT; +} + +template<typename It> +static unsigned HashUnsigneds(It I, It E) { + unsigned Result = 0; + for (; I != E; ++I) + Result = (Result<<3) ^ *I; + return Result; +} + +unsigned EmitMergeInputChainsMatcher::getHashImpl() const { + return HashUnsigneds(ChainNodes.begin(), ChainNodes.end()); +} + +bool CheckOpcodeMatcher::isEqualImpl(const Matcher *M) const { + // Note: pointer equality isn't enough here, we have to check the enum names + // to ensure that the nodes are for the same opcode. + return cast<CheckOpcodeMatcher>(M)->Opcode.getEnumName() == + Opcode.getEnumName(); +} + + +bool EmitNodeMatcherCommon::isEqualImpl(const Matcher *m) const { + const EmitNodeMatcherCommon *M = cast<EmitNodeMatcherCommon>(m); + return M->OpcodeName == OpcodeName && M->VTs == VTs && + M->Operands == Operands && M->HasChain == HasChain && + M->HasInFlag == HasInFlag && M->HasOutFlag == HasOutFlag && + M->HasMemRefs == HasMemRefs && + M->NumFixedArityOperands == NumFixedArityOperands; +} + +unsigned EmitNodeMatcherCommon::getHashImpl() const { + return (HashString(OpcodeName) << 4) | Operands.size(); } -void CheckLegalToFoldMatcherNode::print(raw_ostream &OS, unsigned indent) const{ - OS.indent(indent) << "CheckLegalToFold\n"; - printChild(OS, indent); + +unsigned MarkFlagResultsMatcher::getHashImpl() const { + return HashUnsigneds(FlagResultNodes.begin(), FlagResultNodes.end()); +} + +unsigned CompleteMatchMatcher::getHashImpl() const { + return HashUnsigneds(Results.begin(), Results.end()) ^ + ((unsigned)(intptr_t)&Pattern << 8); +} + +// isContradictoryImpl Implementations. + +static bool TypesAreContradictory(MVT::SimpleValueType T1, + MVT::SimpleValueType T2) { + // If the two types are the same, then they are the same, so they don't + // contradict. + if (T1 == T2) return false; + + // If either type is about iPtr, then they don't conflict unless the other + // one is not a scalar integer type. + if (T1 == MVT::iPTR) + return !MVT(T2).isInteger() || MVT(T2).isVector(); + + if (T2 == MVT::iPTR) + return !MVT(T1).isInteger() || MVT(T1).isVector(); + + // Otherwise, they are two different non-iPTR types, they conflict. + return true; +} + +bool CheckOpcodeMatcher::isContradictoryImpl(const Matcher *M) const { + if (const CheckOpcodeMatcher *COM = dyn_cast<CheckOpcodeMatcher>(M)) { + // One node can't have two different opcodes! + // Note: pointer equality isn't enough here, we have to check the enum names + // to ensure that the nodes are for the same opcode. + return COM->getOpcode().getEnumName() != getOpcode().getEnumName(); + } + + // If the node has a known type, and if the type we're checking for is + // different, then we know they contradict. For example, a check for + // ISD::STORE will never be true at the same time a check for Type i32 is. + if (const CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(M)) { + // FIXME: What result is this referring to? + unsigned NodeType; + if (getOpcode().getNumResults() == 0) + NodeType = MVT::isVoid; + else + NodeType = getOpcode().getKnownType(); + if (NodeType != EEVT::isUnknown) + return TypesAreContradictory((MVT::SimpleValueType)NodeType, + CT->getType()); + } + + return false; +} + +bool CheckTypeMatcher::isContradictoryImpl(const Matcher *M) const { + if (const CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(M)) + return TypesAreContradictory(getType(), CT->getType()); + return false; +} + +bool CheckChildTypeMatcher::isContradictoryImpl(const Matcher *M) const { + if (const CheckChildTypeMatcher *CC = dyn_cast<CheckChildTypeMatcher>(M)) { + // If the two checks are about different nodes, we don't know if they + // conflict! + if (CC->getChildNo() != getChildNo()) + return false; + + return TypesAreContradictory(getType(), CC->getType()); + } + return false; +} + +bool CheckIntegerMatcher::isContradictoryImpl(const Matcher *M) const { + if (const CheckIntegerMatcher *CIM = dyn_cast<CheckIntegerMatcher>(M)) + return CIM->getValue() != getValue(); + return false; } diff --git a/utils/TableGen/DAGISelMatcher.h b/utils/TableGen/DAGISelMatcher.h index b40fbf9..c2e8171 100644 --- a/utils/TableGen/DAGISelMatcher.h +++ b/utils/TableGen/DAGISelMatcher.h @@ -13,379 +13,1038 @@ #include "llvm/CodeGen/ValueTypes.h" #include "llvm/ADT/OwningPtr.h" #include "llvm/ADT/StringRef.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/Support/Casting.h" namespace llvm { class CodeGenDAGPatterns; - class MatcherNode; + class Matcher; class PatternToMatch; class raw_ostream; class ComplexPattern; + class Record; + class SDNodeInfo; -MatcherNode *ConvertPatternToMatcher(const PatternToMatch &Pattern, - const CodeGenDAGPatterns &CGP); - -void EmitMatcherTable(const MatcherNode *Matcher, raw_ostream &OS); +Matcher *ConvertPatternToMatcher(const PatternToMatch &Pattern,unsigned Variant, + const CodeGenDAGPatterns &CGP); +Matcher *OptimizeMatcher(Matcher *Matcher, const CodeGenDAGPatterns &CGP); +void EmitMatcherTable(const Matcher *Matcher, const CodeGenDAGPatterns &CGP, + raw_ostream &OS); -/// MatcherNode - Base class for all the the DAG ISel Matcher representation +/// Matcher - Base class for all the the DAG ISel Matcher representation /// nodes. -class MatcherNode { +class Matcher { + // The next matcher node that is executed after this one. Null if this is the + // last stage of a match. + OwningPtr<Matcher> Next; public: enum KindTy { - EmitNode, - Push, // [Push, Dest0, Dest1, Dest2, Dest3] - Record, // [Record] - MoveChild, // [MoveChild, Child#] - MoveParent, // [MoveParent] + // Matcher state manipulation. + Scope, // Push a checking scope. + RecordNode, // Record the current node. + RecordChild, // Record a child of the current node. + RecordMemRef, // Record the memref in the current node. + CaptureFlagInput, // If the current node has an input flag, save it. + MoveChild, // Move current node to specified child. + MoveParent, // Move current node to parent. - CheckSame, // [CheckSame, N] Fail if not same as prev match. + // Predicate checking. + CheckSame, // Fail if not same as prev match. CheckPatternPredicate, - CheckPredicate, // [CheckPredicate, P] Fail if predicate fails. - CheckOpcode, // [CheckOpcode, Opcode] Fail if not opcode. - CheckType, // [CheckType, MVT] Fail if not correct type. - CheckInteger, // [CheckInteger, int0,int1,int2,...int7] Fail if wrong val. - CheckCondCode, // [CheckCondCode, CondCode] Fail if not condcode. + CheckPredicate, // Fail if node predicate fails. + CheckOpcode, // Fail if not opcode. + SwitchOpcode, // Dispatch based on opcode. + CheckType, // Fail if not correct type. + SwitchType, // Dispatch based on type. + CheckChildType, // Fail if child has wrong type. + CheckInteger, // Fail if wrong val. + CheckCondCode, // Fail if not condcode. CheckValueType, CheckComplexPat, CheckAndImm, CheckOrImm, - CheckProfitableToFold, - CheckLegalToFold + CheckFoldableChainNode, + + // Node creation/emisssion. + EmitInteger, // Create a TargetConstant + EmitStringInteger, // Create a TargetConstant from a string. + EmitRegister, // Create a register. + EmitConvertToTarget, // Convert a imm/fpimm to target imm/fpimm + EmitMergeInputChains, // Merge together a chains for an input. + EmitCopyToReg, // Emit a copytoreg into a physreg. + EmitNode, // Create a DAG node + EmitNodeXForm, // Run a SDNodeXForm + MarkFlagResults, // Indicate which interior nodes have flag results. + CompleteMatch, // Finish a match and update the results. + MorphNodeTo // Build a node, finish a match and update results. }; const KindTy Kind; - + protected: - MatcherNode(KindTy K) : Kind(K) {} + Matcher(KindTy K) : Kind(K) {} public: - virtual ~MatcherNode() {} + virtual ~Matcher() {} KindTy getKind() const { return Kind; } + + Matcher *getNext() { return Next.get(); } + const Matcher *getNext() const { return Next.get(); } + void setNext(Matcher *C) { Next.reset(C); } + Matcher *takeNext() { return Next.take(); } + + OwningPtr<Matcher> &getNextPtr() { return Next; } + static inline bool classof(const Matcher *) { return true; } - static inline bool classof(const MatcherNode *) { return true; } + bool isEqual(const Matcher *M) const { + if (getKind() != M->getKind()) return false; + return isEqualImpl(M); + } + + unsigned getHash() const { + // Clear the high bit so we don't conflict with tombstones etc. + return ((getHashImpl() << 4) ^ getKind()) & (~0U>>1); + } + + /// isSafeToReorderWithPatternPredicate - Return true if it is safe to sink a + /// PatternPredicate node past this one. + virtual bool isSafeToReorderWithPatternPredicate() const { + return false; + } + + /// isContradictory - Return true of these two matchers could never match on + /// the same node. + bool isContradictory(const Matcher *Other) const { + // Since this predicate is reflexive, we canonicalize the ordering so that + // we always match a node against nodes with kinds that are greater or equal + // to them. For example, we'll pass in a CheckType node as an argument to + // the CheckOpcode method, not the other way around. + if (getKind() < Other->getKind()) + return isContradictoryImpl(Other); + return Other->isContradictoryImpl(this); + } - virtual void print(raw_ostream &OS, unsigned indent = 0) const = 0; + void print(raw_ostream &OS, unsigned indent = 0) const; + void printOne(raw_ostream &OS) const; void dump() const; +protected: + virtual void printImpl(raw_ostream &OS, unsigned indent) const = 0; + virtual bool isEqualImpl(const Matcher *M) const = 0; + virtual unsigned getHashImpl() const = 0; + virtual bool isContradictoryImpl(const Matcher *M) const { return false; } }; -/// EmitNodeMatcherNode - This signals a successful match and generates a node. -class EmitNodeMatcherNode : public MatcherNode { - const PatternToMatch &Pattern; +/// ScopeMatcher - This attempts to match each of its children to find the first +/// one that successfully matches. If one child fails, it tries the next child. +/// If none of the children match then this check fails. It never has a 'next'. +class ScopeMatcher : public Matcher { + SmallVector<Matcher*, 4> Children; public: - EmitNodeMatcherNode(const PatternToMatch &pattern) - : MatcherNode(EmitNode), Pattern(pattern) {} - - const PatternToMatch &getPattern() const { return Pattern; } + ScopeMatcher(Matcher *const *children, unsigned numchildren) + : Matcher(Scope), Children(children, children+numchildren) { + } + virtual ~ScopeMatcher(); + + unsigned getNumChildren() const { return Children.size(); } + + Matcher *getChild(unsigned i) { return Children[i]; } + const Matcher *getChild(unsigned i) const { return Children[i]; } + + void resetChild(unsigned i, Matcher *N) { + delete Children[i]; + Children[i] = N; + } - static inline bool classof(const MatcherNode *N) { - return N->getKind() == EmitNode; + Matcher *takeChild(unsigned i) { + Matcher *Res = Children[i]; + Children[i] = 0; + return Res; + } + + void setNumChildren(unsigned NC) { + if (NC < Children.size()) { + // delete any children we're about to lose pointers to. + for (unsigned i = NC, e = Children.size(); i != e; ++i) + delete Children[i]; + } + Children.resize(NC); } - virtual void print(raw_ostream &OS, unsigned indent = 0) const; + static inline bool classof(const Matcher *N) { + return N->getKind() == Scope; + } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { return false; } + virtual unsigned getHashImpl() const { return 12312; } }; -/// MatcherNodeWithChild - Every node accept the final accept state has a child -/// that is executed after the node runs. This class captures this commonality. -class MatcherNodeWithChild : public MatcherNode { - OwningPtr<MatcherNode> Child; +/// RecordMatcher - Save the current node in the operand list. +class RecordMatcher : public Matcher { + /// WhatFor - This is a string indicating why we're recording this. This + /// should only be used for comment generation not anything semantic. + std::string WhatFor; + + /// ResultNo - The slot number in the RecordedNodes vector that this will be, + /// just printed as a comment. + unsigned ResultNo; public: - MatcherNodeWithChild(KindTy K) : MatcherNode(K) {} + RecordMatcher(const std::string &whatfor, unsigned resultNo) + : Matcher(RecordNode), WhatFor(whatfor), ResultNo(resultNo) {} - MatcherNode *getChild() { return Child.get(); } - const MatcherNode *getChild() const { return Child.get(); } - void setChild(MatcherNode *C) { Child.reset(C); } + const std::string &getWhatFor() const { return WhatFor; } + unsigned getResultNo() const { return ResultNo; } - static inline bool classof(const MatcherNode *N) { - return N->getKind() != EmitNode; + static inline bool classof(const Matcher *N) { + return N->getKind() == RecordNode; } -protected: - void printChild(raw_ostream &OS, unsigned indent) const; + virtual bool isSafeToReorderWithPatternPredicate() const { return true; } +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { return true; } + virtual unsigned getHashImpl() const { return 0; } }; - -/// PushMatcherNode - This pushes a failure scope on the stack and evaluates -/// 'child'. If 'child' fails to match, it pops its scope and attempts to -/// match 'Failure'. -class PushMatcherNode : public MatcherNodeWithChild { - OwningPtr<MatcherNode> Failure; + +/// RecordChildMatcher - Save a numbered child of the current node, or fail +/// the match if it doesn't exist. This is logically equivalent to: +/// MoveChild N + RecordNode + MoveParent. +class RecordChildMatcher : public Matcher { + unsigned ChildNo; + + /// WhatFor - This is a string indicating why we're recording this. This + /// should only be used for comment generation not anything semantic. + std::string WhatFor; + + /// ResultNo - The slot number in the RecordedNodes vector that this will be, + /// just printed as a comment. + unsigned ResultNo; public: - PushMatcherNode(MatcherNode *child = 0, MatcherNode *failure = 0) - : MatcherNodeWithChild(Push), Failure(failure) { - setChild(child); + RecordChildMatcher(unsigned childno, const std::string &whatfor, + unsigned resultNo) + : Matcher(RecordChild), ChildNo(childno), WhatFor(whatfor), + ResultNo(resultNo) {} + + unsigned getChildNo() const { return ChildNo; } + const std::string &getWhatFor() const { return WhatFor; } + unsigned getResultNo() const { return ResultNo; } + + static inline bool classof(const Matcher *N) { + return N->getKind() == RecordChild; } - MatcherNode *getFailure() { return Failure.get(); } - const MatcherNode *getFailure() const { return Failure.get(); } - void setFailure(MatcherNode *N) { Failure.reset(N); } + virtual bool isSafeToReorderWithPatternPredicate() const { return true; } - static inline bool classof(const MatcherNode *N) { - return N->getKind() == Push; +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { + return cast<RecordChildMatcher>(M)->getChildNo() == getChildNo(); + } + virtual unsigned getHashImpl() const { return getChildNo(); } +}; + +/// RecordMemRefMatcher - Save the current node's memref. +class RecordMemRefMatcher : public Matcher { +public: + RecordMemRefMatcher() : Matcher(RecordMemRef) {} + + static inline bool classof(const Matcher *N) { + return N->getKind() == RecordMemRef; } - virtual void print(raw_ostream &OS, unsigned indent = 0) const; + virtual bool isSafeToReorderWithPatternPredicate() const { return true; } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { return true; } + virtual unsigned getHashImpl() const { return 0; } }; -/// RecordMatcherNode - Save the current node in the operand list. -class RecordMatcherNode : public MatcherNodeWithChild { + +/// CaptureFlagInputMatcher - If the current record has a flag input, record +/// it so that it is used as an input to the generated code. +class CaptureFlagInputMatcher : public Matcher { public: - RecordMatcherNode() : MatcherNodeWithChild(Record) {} + CaptureFlagInputMatcher() : Matcher(CaptureFlagInput) {} - static inline bool classof(const MatcherNode *N) { - return N->getKind() == Record; + static inline bool classof(const Matcher *N) { + return N->getKind() == CaptureFlagInput; } - virtual void print(raw_ostream &OS, unsigned indent = 0) const; + virtual bool isSafeToReorderWithPatternPredicate() const { return true; } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { return true; } + virtual unsigned getHashImpl() const { return 0; } }; -/// MoveChildMatcherNode - This tells the interpreter to move into the +/// MoveChildMatcher - This tells the interpreter to move into the /// specified child node. -class MoveChildMatcherNode : public MatcherNodeWithChild { +class MoveChildMatcher : public Matcher { unsigned ChildNo; public: - MoveChildMatcherNode(unsigned childNo) - : MatcherNodeWithChild(MoveChild), ChildNo(childNo) {} + MoveChildMatcher(unsigned childNo) : Matcher(MoveChild), ChildNo(childNo) {} unsigned getChildNo() const { return ChildNo; } - static inline bool classof(const MatcherNode *N) { + static inline bool classof(const Matcher *N) { return N->getKind() == MoveChild; } - virtual void print(raw_ostream &OS, unsigned indent = 0) const; + virtual bool isSafeToReorderWithPatternPredicate() const { return true; } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { + return cast<MoveChildMatcher>(M)->getChildNo() == getChildNo(); + } + virtual unsigned getHashImpl() const { return getChildNo(); } }; -/// MoveParentMatcherNode - This tells the interpreter to move to the parent +/// MoveParentMatcher - This tells the interpreter to move to the parent /// of the current node. -class MoveParentMatcherNode : public MatcherNodeWithChild { +class MoveParentMatcher : public Matcher { public: - MoveParentMatcherNode() - : MatcherNodeWithChild(MoveParent) {} + MoveParentMatcher() : Matcher(MoveParent) {} - static inline bool classof(const MatcherNode *N) { + static inline bool classof(const Matcher *N) { return N->getKind() == MoveParent; } - virtual void print(raw_ostream &OS, unsigned indent = 0) const; + virtual bool isSafeToReorderWithPatternPredicate() const { return true; } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { return true; } + virtual unsigned getHashImpl() const { return 0; } }; -/// CheckSameMatcherNode - This checks to see if this node is exactly the same +/// CheckSameMatcher - This checks to see if this node is exactly the same /// node as the specified match that was recorded with 'Record'. This is used /// when patterns have the same name in them, like '(mul GPR:$in, GPR:$in)'. -class CheckSameMatcherNode : public MatcherNodeWithChild { +class CheckSameMatcher : public Matcher { unsigned MatchNumber; public: - CheckSameMatcherNode(unsigned matchnumber) - : MatcherNodeWithChild(CheckSame), MatchNumber(matchnumber) {} + CheckSameMatcher(unsigned matchnumber) + : Matcher(CheckSame), MatchNumber(matchnumber) {} unsigned getMatchNumber() const { return MatchNumber; } - static inline bool classof(const MatcherNode *N) { + static inline bool classof(const Matcher *N) { return N->getKind() == CheckSame; } - virtual void print(raw_ostream &OS, unsigned indent = 0) const; + virtual bool isSafeToReorderWithPatternPredicate() const { return true; } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { + return cast<CheckSameMatcher>(M)->getMatchNumber() == getMatchNumber(); + } + virtual unsigned getHashImpl() const { return getMatchNumber(); } }; -/// CheckPatternPredicateMatcherNode - This checks the target-specific predicate +/// CheckPatternPredicateMatcher - This checks the target-specific predicate /// to see if the entire pattern is capable of matching. This predicate does /// not take a node as input. This is used for subtarget feature checks etc. -class CheckPatternPredicateMatcherNode : public MatcherNodeWithChild { +class CheckPatternPredicateMatcher : public Matcher { std::string Predicate; public: - CheckPatternPredicateMatcherNode(StringRef predicate) - : MatcherNodeWithChild(CheckPatternPredicate), Predicate(predicate) {} + CheckPatternPredicateMatcher(StringRef predicate) + : Matcher(CheckPatternPredicate), Predicate(predicate) {} StringRef getPredicate() const { return Predicate; } - static inline bool classof(const MatcherNode *N) { + static inline bool classof(const Matcher *N) { return N->getKind() == CheckPatternPredicate; } - virtual void print(raw_ostream &OS, unsigned indent = 0) const; + virtual bool isSafeToReorderWithPatternPredicate() const { return true; } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { + return cast<CheckPatternPredicateMatcher>(M)->getPredicate() == Predicate; + } + virtual unsigned getHashImpl() const; }; -/// CheckPredicateMatcherNode - This checks the target-specific predicate to +/// CheckPredicateMatcher - This checks the target-specific predicate to /// see if the node is acceptable. -class CheckPredicateMatcherNode : public MatcherNodeWithChild { +class CheckPredicateMatcher : public Matcher { StringRef PredName; public: - CheckPredicateMatcherNode(StringRef predname) - : MatcherNodeWithChild(CheckPredicate), PredName(predname) {} + CheckPredicateMatcher(StringRef predname) + : Matcher(CheckPredicate), PredName(predname) {} StringRef getPredicateName() const { return PredName; } - static inline bool classof(const MatcherNode *N) { + static inline bool classof(const Matcher *N) { return N->getKind() == CheckPredicate; } - virtual void print(raw_ostream &OS, unsigned indent = 0) const; + // TODO: Ok? + //virtual bool isSafeToReorderWithPatternPredicate() const { return true; } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { + return cast<CheckPredicateMatcher>(M)->PredName == PredName; + } + virtual unsigned getHashImpl() const; }; -/// CheckOpcodeMatcherNode - This checks to see if the current node has the +/// CheckOpcodeMatcher - This checks to see if the current node has the /// specified opcode, if not it fails to match. -class CheckOpcodeMatcherNode : public MatcherNodeWithChild { - StringRef OpcodeName; +class CheckOpcodeMatcher : public Matcher { + const SDNodeInfo &Opcode; public: - CheckOpcodeMatcherNode(StringRef opcodename) - : MatcherNodeWithChild(CheckOpcode), OpcodeName(opcodename) {} + CheckOpcodeMatcher(const SDNodeInfo &opcode) + : Matcher(CheckOpcode), Opcode(opcode) {} - StringRef getOpcodeName() const { return OpcodeName; } + const SDNodeInfo &getOpcode() const { return Opcode; } - static inline bool classof(const MatcherNode *N) { + static inline bool classof(const Matcher *N) { return N->getKind() == CheckOpcode; } - virtual void print(raw_ostream &OS, unsigned indent = 0) const; + virtual bool isSafeToReorderWithPatternPredicate() const { return true; } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const; + virtual unsigned getHashImpl() const; + virtual bool isContradictoryImpl(const Matcher *M) const; }; + +/// SwitchOpcodeMatcher - Switch based on the current node's opcode, dispatching +/// to one matcher per opcode. If the opcode doesn't match any of the cases, +/// then the match fails. This is semantically equivalent to a Scope node where +/// every child does a CheckOpcode, but is much faster. +class SwitchOpcodeMatcher : public Matcher { + SmallVector<std::pair<const SDNodeInfo*, Matcher*>, 8> Cases; +public: + SwitchOpcodeMatcher(const std::pair<const SDNodeInfo*, Matcher*> *cases, + unsigned numcases) + : Matcher(SwitchOpcode), Cases(cases, cases+numcases) {} + + static inline bool classof(const Matcher *N) { + return N->getKind() == SwitchOpcode; + } + + unsigned getNumCases() const { return Cases.size(); } -/// CheckTypeMatcherNode - This checks to see if the current node has the + const SDNodeInfo &getCaseOpcode(unsigned i) const { return *Cases[i].first; } + Matcher *getCaseMatcher(unsigned i) { return Cases[i].second; } + const Matcher *getCaseMatcher(unsigned i) const { return Cases[i].second; } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { return false; } + virtual unsigned getHashImpl() const { return 4123; } +}; + +/// CheckTypeMatcher - This checks to see if the current node has the /// specified type, if not it fails to match. -class CheckTypeMatcherNode : public MatcherNodeWithChild { +class CheckTypeMatcher : public Matcher { MVT::SimpleValueType Type; public: - CheckTypeMatcherNode(MVT::SimpleValueType type) - : MatcherNodeWithChild(CheckType), Type(type) {} + CheckTypeMatcher(MVT::SimpleValueType type) + : Matcher(CheckType), Type(type) {} MVT::SimpleValueType getType() const { return Type; } - static inline bool classof(const MatcherNode *N) { + static inline bool classof(const Matcher *N) { return N->getKind() == CheckType; } - virtual void print(raw_ostream &OS, unsigned indent = 0) const; + virtual bool isSafeToReorderWithPatternPredicate() const { return true; } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { + return cast<CheckTypeMatcher>(M)->Type == Type; + } + virtual unsigned getHashImpl() const { return Type; } + virtual bool isContradictoryImpl(const Matcher *M) const; +}; + +/// SwitchTypeMatcher - Switch based on the current node's type, dispatching +/// to one matcher per case. If the type doesn't match any of the cases, +/// then the match fails. This is semantically equivalent to a Scope node where +/// every child does a CheckType, but is much faster. +class SwitchTypeMatcher : public Matcher { + SmallVector<std::pair<MVT::SimpleValueType, Matcher*>, 8> Cases; +public: + SwitchTypeMatcher(const std::pair<MVT::SimpleValueType, Matcher*> *cases, + unsigned numcases) + : Matcher(SwitchType), Cases(cases, cases+numcases) {} + + static inline bool classof(const Matcher *N) { + return N->getKind() == SwitchType; + } + + unsigned getNumCases() const { return Cases.size(); } + + MVT::SimpleValueType getCaseType(unsigned i) const { return Cases[i].first; } + Matcher *getCaseMatcher(unsigned i) { return Cases[i].second; } + const Matcher *getCaseMatcher(unsigned i) const { return Cases[i].second; } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { return false; } + virtual unsigned getHashImpl() const { return 4123; } }; + + +/// CheckChildTypeMatcher - This checks to see if a child node has the +/// specified type, if not it fails to match. +class CheckChildTypeMatcher : public Matcher { + unsigned ChildNo; + MVT::SimpleValueType Type; +public: + CheckChildTypeMatcher(unsigned childno, MVT::SimpleValueType type) + : Matcher(CheckChildType), ChildNo(childno), Type(type) {} + + unsigned getChildNo() const { return ChildNo; } + MVT::SimpleValueType getType() const { return Type; } + + static inline bool classof(const Matcher *N) { + return N->getKind() == CheckChildType; + } + + virtual bool isSafeToReorderWithPatternPredicate() const { return true; } -/// CheckIntegerMatcherNode - This checks to see if the current node is a +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { + return cast<CheckChildTypeMatcher>(M)->ChildNo == ChildNo && + cast<CheckChildTypeMatcher>(M)->Type == Type; + } + virtual unsigned getHashImpl() const { return (Type << 3) | ChildNo; } + virtual bool isContradictoryImpl(const Matcher *M) const; +}; + + +/// CheckIntegerMatcher - This checks to see if the current node is a /// ConstantSDNode with the specified integer value, if not it fails to match. -class CheckIntegerMatcherNode : public MatcherNodeWithChild { +class CheckIntegerMatcher : public Matcher { int64_t Value; public: - CheckIntegerMatcherNode(int64_t value) - : MatcherNodeWithChild(CheckInteger), Value(value) {} + CheckIntegerMatcher(int64_t value) + : Matcher(CheckInteger), Value(value) {} int64_t getValue() const { return Value; } - static inline bool classof(const MatcherNode *N) { + static inline bool classof(const Matcher *N) { return N->getKind() == CheckInteger; } - virtual void print(raw_ostream &OS, unsigned indent = 0) const; + virtual bool isSafeToReorderWithPatternPredicate() const { return true; } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { + return cast<CheckIntegerMatcher>(M)->Value == Value; + } + virtual unsigned getHashImpl() const { return Value; } + virtual bool isContradictoryImpl(const Matcher *M) const; }; -/// CheckCondCodeMatcherNode - This checks to see if the current node is a +/// CheckCondCodeMatcher - This checks to see if the current node is a /// CondCodeSDNode with the specified condition, if not it fails to match. -class CheckCondCodeMatcherNode : public MatcherNodeWithChild { +class CheckCondCodeMatcher : public Matcher { StringRef CondCodeName; public: - CheckCondCodeMatcherNode(StringRef condcodename) - : MatcherNodeWithChild(CheckCondCode), CondCodeName(condcodename) {} + CheckCondCodeMatcher(StringRef condcodename) + : Matcher(CheckCondCode), CondCodeName(condcodename) {} StringRef getCondCodeName() const { return CondCodeName; } - static inline bool classof(const MatcherNode *N) { + static inline bool classof(const Matcher *N) { return N->getKind() == CheckCondCode; } - virtual void print(raw_ostream &OS, unsigned indent = 0) const; + virtual bool isSafeToReorderWithPatternPredicate() const { return true; } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { + return cast<CheckCondCodeMatcher>(M)->CondCodeName == CondCodeName; + } + virtual unsigned getHashImpl() const; }; -/// CheckValueTypeMatcherNode - This checks to see if the current node is a +/// CheckValueTypeMatcher - This checks to see if the current node is a /// VTSDNode with the specified type, if not it fails to match. -class CheckValueTypeMatcherNode : public MatcherNodeWithChild { +class CheckValueTypeMatcher : public Matcher { StringRef TypeName; public: - CheckValueTypeMatcherNode(StringRef type_name) - : MatcherNodeWithChild(CheckValueType), TypeName(type_name) {} + CheckValueTypeMatcher(StringRef type_name) + : Matcher(CheckValueType), TypeName(type_name) {} StringRef getTypeName() const { return TypeName; } - static inline bool classof(const MatcherNode *N) { + static inline bool classof(const Matcher *N) { return N->getKind() == CheckValueType; } - virtual void print(raw_ostream &OS, unsigned indent = 0) const; + virtual bool isSafeToReorderWithPatternPredicate() const { return true; } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { + return cast<CheckValueTypeMatcher>(M)->TypeName == TypeName; + } + virtual unsigned getHashImpl() const; }; -/// CheckComplexPatMatcherNode - This node runs the specified ComplexPattern on +/// CheckComplexPatMatcher - This node runs the specified ComplexPattern on /// the current node. -class CheckComplexPatMatcherNode : public MatcherNodeWithChild { +class CheckComplexPatMatcher : public Matcher { const ComplexPattern &Pattern; public: - CheckComplexPatMatcherNode(const ComplexPattern &pattern) - : MatcherNodeWithChild(CheckComplexPat), Pattern(pattern) {} + CheckComplexPatMatcher(const ComplexPattern &pattern) + : Matcher(CheckComplexPat), Pattern(pattern) {} - static inline bool classof(const MatcherNode *N) { + const ComplexPattern &getPattern() const { return Pattern; } + + static inline bool classof(const Matcher *N) { return N->getKind() == CheckComplexPat; } - virtual void print(raw_ostream &OS, unsigned indent = 0) const; + // Not safe to move a pattern predicate past a complex pattern. + virtual bool isSafeToReorderWithPatternPredicate() const { return false; } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { + return &cast<CheckComplexPatMatcher>(M)->Pattern == &Pattern; + } + virtual unsigned getHashImpl() const { + return (unsigned)(intptr_t)&Pattern; + } }; -/// CheckAndImmMatcherNode - This checks to see if the current node is an 'and' +/// CheckAndImmMatcher - This checks to see if the current node is an 'and' /// with something equivalent to the specified immediate. -class CheckAndImmMatcherNode : public MatcherNodeWithChild { +class CheckAndImmMatcher : public Matcher { int64_t Value; public: - CheckAndImmMatcherNode(int64_t value) - : MatcherNodeWithChild(CheckAndImm), Value(value) {} + CheckAndImmMatcher(int64_t value) + : Matcher(CheckAndImm), Value(value) {} int64_t getValue() const { return Value; } - static inline bool classof(const MatcherNode *N) { + static inline bool classof(const Matcher *N) { return N->getKind() == CheckAndImm; } - virtual void print(raw_ostream &OS, unsigned indent = 0) const; + virtual bool isSafeToReorderWithPatternPredicate() const { return true; } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { + return cast<CheckAndImmMatcher>(M)->Value == Value; + } + virtual unsigned getHashImpl() const { return Value; } }; -/// CheckOrImmMatcherNode - This checks to see if the current node is an 'and' +/// CheckOrImmMatcher - This checks to see if the current node is an 'and' /// with something equivalent to the specified immediate. -class CheckOrImmMatcherNode : public MatcherNodeWithChild { +class CheckOrImmMatcher : public Matcher { int64_t Value; public: - CheckOrImmMatcherNode(int64_t value) - : MatcherNodeWithChild(CheckOrImm), Value(value) {} + CheckOrImmMatcher(int64_t value) + : Matcher(CheckOrImm), Value(value) {} int64_t getValue() const { return Value; } - static inline bool classof(const MatcherNode *N) { + static inline bool classof(const Matcher *N) { return N->getKind() == CheckOrImm; } - virtual void print(raw_ostream &OS, unsigned indent = 0) const; + virtual bool isSafeToReorderWithPatternPredicate() const { return true; } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { + return cast<CheckOrImmMatcher>(M)->Value == Value; + } + virtual unsigned getHashImpl() const { return Value; } }; -/// CheckProfitableToFoldMatcherNode - This checks to see if the current node is -/// worthwhile to try to fold into a large pattern. -class CheckProfitableToFoldMatcherNode : public MatcherNodeWithChild { +/// CheckFoldableChainNodeMatcher - This checks to see if the current node +/// (which defines a chain operand) is safe to fold into a larger pattern. +class CheckFoldableChainNodeMatcher : public Matcher { public: - CheckProfitableToFoldMatcherNode() - : MatcherNodeWithChild(CheckProfitableToFold) {} + CheckFoldableChainNodeMatcher() + : Matcher(CheckFoldableChainNode) {} - static inline bool classof(const MatcherNode *N) { - return N->getKind() == CheckProfitableToFold; + static inline bool classof(const Matcher *N) { + return N->getKind() == CheckFoldableChainNode; } - virtual void print(raw_ostream &OS, unsigned indent = 0) const; + virtual bool isSafeToReorderWithPatternPredicate() const { return true; } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { return true; } + virtual unsigned getHashImpl() const { return 0; } }; -/// CheckLegalToFoldMatcherNode - This checks to see if the current node is -/// legal to try to fold into a large pattern. -class CheckLegalToFoldMatcherNode : public MatcherNodeWithChild { +/// EmitIntegerMatcher - This creates a new TargetConstant. +class EmitIntegerMatcher : public Matcher { + int64_t Val; + MVT::SimpleValueType VT; public: - CheckLegalToFoldMatcherNode() - : MatcherNodeWithChild(CheckLegalToFold) {} + EmitIntegerMatcher(int64_t val, MVT::SimpleValueType vt) + : Matcher(EmitInteger), Val(val), VT(vt) {} - static inline bool classof(const MatcherNode *N) { - return N->getKind() == CheckLegalToFold; + int64_t getValue() const { return Val; } + MVT::SimpleValueType getVT() const { return VT; } + + static inline bool classof(const Matcher *N) { + return N->getKind() == EmitInteger; + } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { + return cast<EmitIntegerMatcher>(M)->Val == Val && + cast<EmitIntegerMatcher>(M)->VT == VT; + } + virtual unsigned getHashImpl() const { return (Val << 4) | VT; } +}; + +/// EmitStringIntegerMatcher - A target constant whose value is represented +/// by a string. +class EmitStringIntegerMatcher : public Matcher { + std::string Val; + MVT::SimpleValueType VT; +public: + EmitStringIntegerMatcher(const std::string &val, MVT::SimpleValueType vt) + : Matcher(EmitStringInteger), Val(val), VT(vt) {} + + const std::string &getValue() const { return Val; } + MVT::SimpleValueType getVT() const { return VT; } + + static inline bool classof(const Matcher *N) { + return N->getKind() == EmitStringInteger; + } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { + return cast<EmitStringIntegerMatcher>(M)->Val == Val && + cast<EmitStringIntegerMatcher>(M)->VT == VT; + } + virtual unsigned getHashImpl() const; +}; + +/// EmitRegisterMatcher - This creates a new TargetConstant. +class EmitRegisterMatcher : public Matcher { + /// Reg - The def for the register that we're emitting. If this is null, then + /// this is a reference to zero_reg. + Record *Reg; + MVT::SimpleValueType VT; +public: + EmitRegisterMatcher(Record *reg, MVT::SimpleValueType vt) + : Matcher(EmitRegister), Reg(reg), VT(vt) {} + + Record *getReg() const { return Reg; } + MVT::SimpleValueType getVT() const { return VT; } + + static inline bool classof(const Matcher *N) { + return N->getKind() == EmitRegister; + } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { + return cast<EmitRegisterMatcher>(M)->Reg == Reg && + cast<EmitRegisterMatcher>(M)->VT == VT; + } + virtual unsigned getHashImpl() const { + return ((unsigned)(intptr_t)Reg) << 4 | VT; + } +}; + +/// EmitConvertToTargetMatcher - Emit an operation that reads a specified +/// recorded node and converts it from being a ISD::Constant to +/// ISD::TargetConstant, likewise for ConstantFP. +class EmitConvertToTargetMatcher : public Matcher { + unsigned Slot; +public: + EmitConvertToTargetMatcher(unsigned slot) + : Matcher(EmitConvertToTarget), Slot(slot) {} + + unsigned getSlot() const { return Slot; } + + static inline bool classof(const Matcher *N) { + return N->getKind() == EmitConvertToTarget; + } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { + return cast<EmitConvertToTargetMatcher>(M)->Slot == Slot; + } + virtual unsigned getHashImpl() const { return Slot; } +}; + +/// EmitMergeInputChainsMatcher - Emit a node that merges a list of input +/// chains together with a token factor. The list of nodes are the nodes in the +/// matched pattern that have chain input/outputs. This node adds all input +/// chains of these nodes if they are not themselves a node in the pattern. +class EmitMergeInputChainsMatcher : public Matcher { + SmallVector<unsigned, 3> ChainNodes; +public: + EmitMergeInputChainsMatcher(const unsigned *nodes, unsigned NumNodes) + : Matcher(EmitMergeInputChains), ChainNodes(nodes, nodes+NumNodes) {} + + unsigned getNumNodes() const { return ChainNodes.size(); } + + unsigned getNode(unsigned i) const { + assert(i < ChainNodes.size()); + return ChainNodes[i]; + } + + static inline bool classof(const Matcher *N) { + return N->getKind() == EmitMergeInputChains; + } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { + return cast<EmitMergeInputChainsMatcher>(M)->ChainNodes == ChainNodes; + } + virtual unsigned getHashImpl() const; +}; + +/// EmitCopyToRegMatcher - Emit a CopyToReg node from a value to a physreg, +/// pushing the chain and flag results. +/// +class EmitCopyToRegMatcher : public Matcher { + unsigned SrcSlot; // Value to copy into the physreg. + Record *DestPhysReg; +public: + EmitCopyToRegMatcher(unsigned srcSlot, Record *destPhysReg) + : Matcher(EmitCopyToReg), SrcSlot(srcSlot), DestPhysReg(destPhysReg) {} + + unsigned getSrcSlot() const { return SrcSlot; } + Record *getDestPhysReg() const { return DestPhysReg; } + + static inline bool classof(const Matcher *N) { + return N->getKind() == EmitCopyToReg; + } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { + return cast<EmitCopyToRegMatcher>(M)->SrcSlot == SrcSlot && + cast<EmitCopyToRegMatcher>(M)->DestPhysReg == DestPhysReg; + } + virtual unsigned getHashImpl() const { + return SrcSlot ^ ((unsigned)(intptr_t)DestPhysReg << 4); + } +}; + + + +/// EmitNodeXFormMatcher - Emit an operation that runs an SDNodeXForm on a +/// recorded node and records the result. +class EmitNodeXFormMatcher : public Matcher { + unsigned Slot; + Record *NodeXForm; +public: + EmitNodeXFormMatcher(unsigned slot, Record *nodeXForm) + : Matcher(EmitNodeXForm), Slot(slot), NodeXForm(nodeXForm) {} + + unsigned getSlot() const { return Slot; } + Record *getNodeXForm() const { return NodeXForm; } + + static inline bool classof(const Matcher *N) { + return N->getKind() == EmitNodeXForm; + } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { + return cast<EmitNodeXFormMatcher>(M)->Slot == Slot && + cast<EmitNodeXFormMatcher>(M)->NodeXForm == NodeXForm; + } + virtual unsigned getHashImpl() const { + return Slot ^ ((unsigned)(intptr_t)NodeXForm << 4); + } +}; + +/// EmitNodeMatcherCommon - Common class shared between EmitNode and +/// MorphNodeTo. +class EmitNodeMatcherCommon : public Matcher { + std::string OpcodeName; + const SmallVector<MVT::SimpleValueType, 3> VTs; + const SmallVector<unsigned, 6> Operands; + bool HasChain, HasInFlag, HasOutFlag, HasMemRefs; + + /// NumFixedArityOperands - If this is a fixed arity node, this is set to -1. + /// If this is a varidic node, this is set to the number of fixed arity + /// operands in the root of the pattern. The rest are appended to this node. + int NumFixedArityOperands; +public: + EmitNodeMatcherCommon(const std::string &opcodeName, + const MVT::SimpleValueType *vts, unsigned numvts, + const unsigned *operands, unsigned numops, + bool hasChain, bool hasInFlag, bool hasOutFlag, + bool hasmemrefs, + int numfixedarityoperands, bool isMorphNodeTo) + : Matcher(isMorphNodeTo ? MorphNodeTo : EmitNode), OpcodeName(opcodeName), + VTs(vts, vts+numvts), Operands(operands, operands+numops), + HasChain(hasChain), HasInFlag(hasInFlag), HasOutFlag(hasOutFlag), + HasMemRefs(hasmemrefs), NumFixedArityOperands(numfixedarityoperands) {} + + const std::string &getOpcodeName() const { return OpcodeName; } + + unsigned getNumVTs() const { return VTs.size(); } + MVT::SimpleValueType getVT(unsigned i) const { + assert(i < VTs.size()); + return VTs[i]; + } + + unsigned getNumOperands() const { return Operands.size(); } + unsigned getOperand(unsigned i) const { + assert(i < Operands.size()); + return Operands[i]; + } + + const SmallVectorImpl<MVT::SimpleValueType> &getVTList() const { return VTs; } + const SmallVectorImpl<unsigned> &getOperandList() const { return Operands; } + + + bool hasChain() const { return HasChain; } + bool hasInFlag() const { return HasInFlag; } + bool hasOutFlag() const { return HasOutFlag; } + bool hasMemRefs() const { return HasMemRefs; } + int getNumFixedArityOperands() const { return NumFixedArityOperands; } + + static inline bool classof(const Matcher *N) { + return N->getKind() == EmitNode || N->getKind() == MorphNodeTo; } - virtual void print(raw_ostream &OS, unsigned indent = 0) const; +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const; + virtual unsigned getHashImpl() const; +}; + +/// EmitNodeMatcher - This signals a successful match and generates a node. +class EmitNodeMatcher : public EmitNodeMatcherCommon { + unsigned FirstResultSlot; +public: + EmitNodeMatcher(const std::string &opcodeName, + const MVT::SimpleValueType *vts, unsigned numvts, + const unsigned *operands, unsigned numops, + bool hasChain, bool hasInFlag, bool hasOutFlag, + bool hasmemrefs, + int numfixedarityoperands, unsigned firstresultslot) + : EmitNodeMatcherCommon(opcodeName, vts, numvts, operands, numops, hasChain, + hasInFlag, hasOutFlag, hasmemrefs, + numfixedarityoperands, false), + FirstResultSlot(firstresultslot) {} + + unsigned getFirstResultSlot() const { return FirstResultSlot; } + + static inline bool classof(const Matcher *N) { + return N->getKind() == EmitNode; + } + +}; + +class MorphNodeToMatcher : public EmitNodeMatcherCommon { + const PatternToMatch &Pattern; +public: + MorphNodeToMatcher(const std::string &opcodeName, + const MVT::SimpleValueType *vts, unsigned numvts, + const unsigned *operands, unsigned numops, + bool hasChain, bool hasInFlag, bool hasOutFlag, + bool hasmemrefs, + int numfixedarityoperands, const PatternToMatch &pattern) + : EmitNodeMatcherCommon(opcodeName, vts, numvts, operands, numops, hasChain, + hasInFlag, hasOutFlag, hasmemrefs, + numfixedarityoperands, true), + Pattern(pattern) { + } + + const PatternToMatch &getPattern() const { return Pattern; } + + static inline bool classof(const Matcher *N) { + return N->getKind() == MorphNodeTo; + } +}; + +/// MarkFlagResultsMatcher - This node indicates which non-root nodes in the +/// pattern produce flags. This allows CompleteMatchMatcher to update them +/// with the output flag of the resultant code. +class MarkFlagResultsMatcher : public Matcher { + SmallVector<unsigned, 3> FlagResultNodes; +public: + MarkFlagResultsMatcher(const unsigned *nodes, unsigned NumNodes) + : Matcher(MarkFlagResults), FlagResultNodes(nodes, nodes+NumNodes) {} + + unsigned getNumNodes() const { return FlagResultNodes.size(); } + + unsigned getNode(unsigned i) const { + assert(i < FlagResultNodes.size()); + return FlagResultNodes[i]; + } + + static inline bool classof(const Matcher *N) { + return N->getKind() == MarkFlagResults; + } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { + return cast<MarkFlagResultsMatcher>(M)->FlagResultNodes == FlagResultNodes; + } + virtual unsigned getHashImpl() const; +}; + +/// CompleteMatchMatcher - Complete a match by replacing the results of the +/// pattern with the newly generated nodes. This also prints a comment +/// indicating the source and dest patterns. +class CompleteMatchMatcher : public Matcher { + SmallVector<unsigned, 2> Results; + const PatternToMatch &Pattern; +public: + CompleteMatchMatcher(const unsigned *results, unsigned numresults, + const PatternToMatch &pattern) + : Matcher(CompleteMatch), Results(results, results+numresults), + Pattern(pattern) {} + + unsigned getNumResults() const { return Results.size(); } + unsigned getResult(unsigned R) const { return Results[R]; } + const PatternToMatch &getPattern() const { return Pattern; } + + static inline bool classof(const Matcher *N) { + return N->getKind() == CompleteMatch; + } + +private: + virtual void printImpl(raw_ostream &OS, unsigned indent) const; + virtual bool isEqualImpl(const Matcher *M) const { + return cast<CompleteMatchMatcher>(M)->Results == Results && + &cast<CompleteMatchMatcher>(M)->Pattern == &Pattern; + } + virtual unsigned getHashImpl() const; }; + } // end namespace llvm #endif diff --git a/utils/TableGen/DAGISelMatcherEmitter.cpp b/utils/TableGen/DAGISelMatcherEmitter.cpp index c0ad169..1f04050 100644 --- a/utils/TableGen/DAGISelMatcherEmitter.cpp +++ b/utils/TableGen/DAGISelMatcherEmitter.cpp @@ -13,71 +13,50 @@ #include "DAGISelMatcher.h" #include "CodeGenDAGPatterns.h" +#include "Record.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallString.h" #include "llvm/ADT/StringMap.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/FormattedStream.h" using namespace llvm; -namespace { enum { - CommentIndent = 25 + CommentIndent = 30 }; -} -/// ClassifyInt - Classify an integer by size, return '1','2','4','8' if this -/// fits in 1, 2, 4, or 8 sign extended bytes. -static char ClassifyInt(int64_t Val) { - if (Val == int8_t(Val)) return '1'; - if (Val == int16_t(Val)) return '2'; - if (Val == int32_t(Val)) return '4'; - return '8'; -} - -/// EmitInt - Emit the specified integer, returning the number of bytes emitted. -static unsigned EmitInt(int64_t Val, formatted_raw_ostream &OS) { - unsigned BytesEmitted = 1; - OS << (int)(unsigned char)Val << ", "; - if (Val == int8_t(Val)) { - OS << "\n"; - return BytesEmitted; - } - - OS << (int)(unsigned char)(Val >> 8) << ", "; - ++BytesEmitted; - - if (Val != int16_t(Val)) { - OS << (int)(unsigned char)(Val >> 16) << ',' - << (int)(unsigned char)(Val >> 24) << ','; - BytesEmitted += 2; - - if (Val != int32_t(Val)) { - OS << (int)(unsigned char)(Val >> 32) << ',' - << (int)(unsigned char)(Val >> 40) << ',' - << (int)(unsigned char)(Val >> 48) << ',' - << (int)(unsigned char)(Val >> 56) << ','; - BytesEmitted += 4; - } - } - - OS.PadToColumn(CommentIndent) << "// " << Val << '\n'; - return BytesEmitted; -} +// To reduce generated source code size. +static cl::opt<bool> +OmitComments("omit-comments", cl::desc("Do not generate comments"), + cl::init(false)); namespace { class MatcherTableEmitter { - formatted_raw_ostream &OS; - StringMap<unsigned> NodePredicateMap, PatternPredicateMap; std::vector<std::string> NodePredicates, PatternPredicates; - + + DenseMap<const ComplexPattern*, unsigned> ComplexPatternMap; + std::vector<const ComplexPattern*> ComplexPatterns; + + + DenseMap<Record*, unsigned> NodeXFormMap; + std::vector<Record*> NodeXForms; + + // Per opcode frequence count. + std::vector<unsigned> Histogram; public: - MatcherTableEmitter(formatted_raw_ostream &os) : OS(os) {} + MatcherTableEmitter() {} - unsigned EmitMatcherAndChildren(const MatcherNode *N, unsigned Indent); + unsigned EmitMatcherList(const Matcher *N, unsigned Indent, + unsigned StartIdx, formatted_raw_ostream &OS); - void EmitPredicateFunctions(); + void EmitPredicateFunctions(const CodeGenDAGPatterns &CGP, + formatted_raw_ostream &OS); + + void EmitHistogram(formatted_raw_ostream &OS); private: - unsigned EmitMatcher(const MatcherNode *N, unsigned Indent); + unsigned EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx, + formatted_raw_ostream &OS); unsigned getNodePredicate(StringRef PredName) { unsigned &Entry = NodePredicateMap[PredName]; @@ -95,184 +74,679 @@ private: } return Entry-1; } + + unsigned getComplexPat(const ComplexPattern &P) { + unsigned &Entry = ComplexPatternMap[&P]; + if (Entry == 0) { + ComplexPatterns.push_back(&P); + Entry = ComplexPatterns.size(); + } + return Entry-1; + } + + unsigned getNodeXFormID(Record *Rec) { + unsigned &Entry = NodeXFormMap[Rec]; + if (Entry == 0) { + NodeXForms.push_back(Rec); + Entry = NodeXForms.size(); + } + return Entry-1; + } + }; } // end anonymous namespace. +static unsigned GetVBRSize(unsigned Val) { + if (Val <= 127) return 1; + + unsigned NumBytes = 0; + while (Val >= 128) { + Val >>= 7; + ++NumBytes; + } + return NumBytes+1; +} + +/// EmitVBRValue - Emit the specified value as a VBR, returning the number of +/// bytes emitted. +static uint64_t EmitVBRValue(uint64_t Val, raw_ostream &OS) { + if (Val <= 127) { + OS << Val << ", "; + return 1; + } + + uint64_t InVal = Val; + unsigned NumBytes = 0; + while (Val >= 128) { + OS << (Val&127) << "|128,"; + Val >>= 7; + ++NumBytes; + } + OS << Val; + if (!OmitComments) + OS << "/*" << InVal << "*/"; + OS << ", "; + return NumBytes+1; +} + /// EmitMatcherOpcodes - Emit bytes for the specified matcher and return /// the number of bytes emitted. unsigned MatcherTableEmitter:: -EmitMatcher(const MatcherNode *N, unsigned Indent) { +EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx, + formatted_raw_ostream &OS) { OS.PadToColumn(Indent*2); switch (N->getKind()) { - case MatcherNode::Push: assert(0 && "Should be handled by caller"); - case MatcherNode::EmitNode: - OS << "OPC_Emit, /*XXX*/"; - OS.PadToColumn(CommentIndent) << "// Src: " - << *cast<EmitNodeMatcherNode>(N)->getPattern().getSrcPattern() << '\n'; - OS.PadToColumn(CommentIndent) << "// Dst: " - << *cast<EmitNodeMatcherNode>(N)->getPattern().getDstPattern() << '\n'; + case Matcher::Scope: { + const ScopeMatcher *SM = cast<ScopeMatcher>(N); + assert(SM->getNext() == 0 && "Shouldn't have next after scope"); + + unsigned StartIdx = CurrentIdx; + + // Emit all of the children. + for (unsigned i = 0, e = SM->getNumChildren(); i != e; ++i) { + if (i == 0) { + OS << "OPC_Scope, "; + ++CurrentIdx; + } else { + if (!OmitComments) { + OS << "/*" << CurrentIdx << "*/"; + OS.PadToColumn(Indent*2) << "/*Scope*/ "; + } else + OS.PadToColumn(Indent*2); + } + + // We need to encode the child and the offset of the failure code before + // emitting either of them. Handle this by buffering the output into a + // string while we get the size. Unfortunately, the offset of the + // children depends on the VBR size of the child, so for large children we + // have to iterate a bit. + SmallString<128> TmpBuf; + unsigned ChildSize = 0; + unsigned VBRSize = 0; + do { + VBRSize = GetVBRSize(ChildSize); + + TmpBuf.clear(); + raw_svector_ostream OS(TmpBuf); + formatted_raw_ostream FOS(OS); + ChildSize = EmitMatcherList(SM->getChild(i), Indent+1, + CurrentIdx+VBRSize, FOS); + } while (GetVBRSize(ChildSize) != VBRSize); + + assert(ChildSize != 0 && "Should not have a zero-sized child!"); + + CurrentIdx += EmitVBRValue(ChildSize, OS); + if (!OmitComments) { + OS << "/*->" << CurrentIdx+ChildSize << "*/"; + + if (i == 0) + OS.PadToColumn(CommentIndent) << "// " << SM->getNumChildren() + << " children in Scope"; + } + + OS << '\n' << TmpBuf.str(); + CurrentIdx += ChildSize; + } + + // Emit a zero as a sentinel indicating end of 'Scope'. + if (!OmitComments) + OS << "/*" << CurrentIdx << "*/"; + OS.PadToColumn(Indent*2) << "0, "; + if (!OmitComments) + OS << "/*End of Scope*/"; + OS << '\n'; + return CurrentIdx - StartIdx + 1; + } + + case Matcher::RecordNode: + OS << "OPC_RecordNode,"; + if (!OmitComments) + OS.PadToColumn(CommentIndent) << "// #" + << cast<RecordMatcher>(N)->getResultNo() << " = " + << cast<RecordMatcher>(N)->getWhatFor(); + OS << '\n'; return 1; - case MatcherNode::Record: - OS << "OPC_Record,\n"; + + case Matcher::RecordChild: + OS << "OPC_RecordChild" << cast<RecordChildMatcher>(N)->getChildNo() + << ','; + if (!OmitComments) + OS.PadToColumn(CommentIndent) << "// #" + << cast<RecordChildMatcher>(N)->getResultNo() << " = " + << cast<RecordChildMatcher>(N)->getWhatFor(); + OS << '\n'; + return 1; + + case Matcher::RecordMemRef: + OS << "OPC_RecordMemRef,\n"; + return 1; + + case Matcher::CaptureFlagInput: + OS << "OPC_CaptureFlagInput,\n"; return 1; - case MatcherNode::MoveChild: - OS << "OPC_MoveChild, " - << cast<MoveChildMatcherNode>(N)->getChildNo() << ",\n"; + + case Matcher::MoveChild: + OS << "OPC_MoveChild, " << cast<MoveChildMatcher>(N)->getChildNo() << ",\n"; return 2; - case MatcherNode::MoveParent: + case Matcher::MoveParent: OS << "OPC_MoveParent,\n"; return 1; - case MatcherNode::CheckSame: + case Matcher::CheckSame: OS << "OPC_CheckSame, " - << cast<CheckSameMatcherNode>(N)->getMatchNumber() << ",\n"; + << cast<CheckSameMatcher>(N)->getMatchNumber() << ",\n"; return 2; - case MatcherNode::CheckPatternPredicate: { - StringRef Pred = cast<CheckPatternPredicateMatcherNode>(N)->getPredicate(); + case Matcher::CheckPatternPredicate: { + StringRef Pred = cast<CheckPatternPredicateMatcher>(N)->getPredicate(); OS << "OPC_CheckPatternPredicate, " << getPatternPredicate(Pred) << ','; - OS.PadToColumn(CommentIndent) << "// " << Pred << '\n'; + if (!OmitComments) + OS.PadToColumn(CommentIndent) << "// " << Pred; + OS << '\n'; return 2; } - case MatcherNode::CheckPredicate: { - StringRef Pred = cast<CheckPredicateMatcherNode>(N)->getPredicateName(); + case Matcher::CheckPredicate: { + StringRef Pred = cast<CheckPredicateMatcher>(N)->getPredicateName(); OS << "OPC_CheckPredicate, " << getNodePredicate(Pred) << ','; - OS.PadToColumn(CommentIndent) << "// " << Pred << '\n'; + if (!OmitComments) + OS.PadToColumn(CommentIndent) << "// " << Pred; + OS << '\n'; return 2; } - case MatcherNode::CheckOpcode: + case Matcher::CheckOpcode: OS << "OPC_CheckOpcode, " - << cast<CheckOpcodeMatcherNode>(N)->getOpcodeName() << ",\n"; + << cast<CheckOpcodeMatcher>(N)->getOpcode().getEnumName() << ",\n"; return 2; - case MatcherNode::CheckType: + case Matcher::SwitchOpcode: + case Matcher::SwitchType: { + unsigned StartIdx = CurrentIdx; + + unsigned NumCases; + if (const SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(N)) { + OS << "OPC_SwitchOpcode "; + NumCases = SOM->getNumCases(); + } else { + OS << "OPC_SwitchType "; + NumCases = cast<SwitchTypeMatcher>(N)->getNumCases(); + } + + if (!OmitComments) + OS << "/*" << NumCases << " cases */"; + OS << ", "; + ++CurrentIdx; + + // For each case we emit the size, then the opcode, then the matcher. + for (unsigned i = 0, e = NumCases; i != e; ++i) { + const Matcher *Child; + if (const SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(N)) + Child = SOM->getCaseMatcher(i); + else + Child = cast<SwitchTypeMatcher>(N)->getCaseMatcher(i); + + // We need to encode the opcode and the offset of the case code before + // emitting the case code. Handle this by buffering the output into a + // string while we get the size. Unfortunately, the offset of the + // children depends on the VBR size of the child, so for large children we + // have to iterate a bit. + SmallString<128> TmpBuf; + unsigned ChildSize = 0; + unsigned VBRSize = 0; + do { + VBRSize = GetVBRSize(ChildSize); + + TmpBuf.clear(); + raw_svector_ostream OS(TmpBuf); + formatted_raw_ostream FOS(OS); + ChildSize = EmitMatcherList(Child, Indent+1, CurrentIdx+VBRSize+1, FOS); + } while (GetVBRSize(ChildSize) != VBRSize); + + assert(ChildSize != 0 && "Should not have a zero-sized child!"); + + if (i != 0) { + OS.PadToColumn(Indent*2); + if (!OmitComments) + OS << (isa<SwitchOpcodeMatcher>(N) ? + "/*SwitchOpcode*/ " : "/*SwitchType*/ "); + } + + // Emit the VBR. + CurrentIdx += EmitVBRValue(ChildSize, OS); + + OS << ' '; + if (const SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(N)) + OS << SOM->getCaseOpcode(i).getEnumName(); + else + OS << getEnumName(cast<SwitchTypeMatcher>(N)->getCaseType(i)); + OS << ','; + + if (!OmitComments) + OS << "// ->" << CurrentIdx+ChildSize+1; + OS << '\n'; + ++CurrentIdx; + OS << TmpBuf.str(); + CurrentIdx += ChildSize; + } + + // Emit the final zero to terminate the switch. + OS.PadToColumn(Indent*2) << "0, "; + if (!OmitComments) + OS << (isa<SwitchOpcodeMatcher>(N) ? + "// EndSwitchOpcode" : "// EndSwitchType"); + + OS << '\n'; + ++CurrentIdx; + return CurrentIdx-StartIdx; + } + + case Matcher::CheckType: OS << "OPC_CheckType, " - << getEnumName(cast<CheckTypeMatcherNode>(N)->getType()) << ",\n"; + << getEnumName(cast<CheckTypeMatcher>(N)->getType()) << ",\n"; return 2; - - case MatcherNode::CheckInteger: { - int64_t Val = cast<CheckIntegerMatcherNode>(N)->getValue(); - OS << "OPC_CheckInteger" << ClassifyInt(Val) << ", "; - return EmitInt(Val, OS)+1; - } - case MatcherNode::CheckCondCode: + + case Matcher::CheckChildType: + OS << "OPC_CheckChild" + << cast<CheckChildTypeMatcher>(N)->getChildNo() << "Type, " + << getEnumName(cast<CheckChildTypeMatcher>(N)->getType()) << ",\n"; + return 2; + + case Matcher::CheckInteger: { + OS << "OPC_CheckInteger, "; + unsigned Bytes=1+EmitVBRValue(cast<CheckIntegerMatcher>(N)->getValue(), OS); + OS << '\n'; + return Bytes; + } + case Matcher::CheckCondCode: OS << "OPC_CheckCondCode, ISD::" - << cast<CheckCondCodeMatcherNode>(N)->getCondCodeName() << ",\n"; + << cast<CheckCondCodeMatcher>(N)->getCondCodeName() << ",\n"; return 2; - case MatcherNode::CheckValueType: + case Matcher::CheckValueType: OS << "OPC_CheckValueType, MVT::" - << cast<CheckValueTypeMatcherNode>(N)->getTypeName() << ",\n"; + << cast<CheckValueTypeMatcher>(N)->getTypeName() << ",\n"; return 2; - case MatcherNode::CheckComplexPat: - OS << "OPC_CheckComplexPat, 0/*XXX*/,\n"; + case Matcher::CheckComplexPat: { + const ComplexPattern &Pattern = + cast<CheckComplexPatMatcher>(N)->getPattern(); + OS << "OPC_CheckComplexPat, " << getComplexPat(Pattern) << ','; + if (!OmitComments) { + OS.PadToColumn(CommentIndent) << "// " << Pattern.getSelectFunc(); + OS << ": " << Pattern.getNumOperands() << " operands"; + if (Pattern.hasProperty(SDNPHasChain)) + OS << " + chain result and input"; + } + OS << '\n'; return 2; + } - case MatcherNode::CheckAndImm: { - int64_t Val = cast<CheckAndImmMatcherNode>(N)->getValue(); - OS << "OPC_CheckAndImm" << ClassifyInt(Val) << ", "; - return EmitInt(Val, OS)+1; + case Matcher::CheckAndImm: { + OS << "OPC_CheckAndImm, "; + unsigned Bytes=1+EmitVBRValue(cast<CheckAndImmMatcher>(N)->getValue(), OS); + OS << '\n'; + return Bytes; } - case MatcherNode::CheckOrImm: { - int64_t Val = cast<CheckOrImmMatcherNode>(N)->getValue(); - OS << "OPC_CheckOrImm" << ClassifyInt(Val) << ", "; - return EmitInt(Val, OS)+1; + case Matcher::CheckOrImm: { + OS << "OPC_CheckOrImm, "; + unsigned Bytes = 1+EmitVBRValue(cast<CheckOrImmMatcher>(N)->getValue(), OS); + OS << '\n'; + return Bytes; } - case MatcherNode::CheckProfitableToFold: - OS << "OPC_IsProfitableToFold,\n"; - return 1; - case MatcherNode::CheckLegalToFold: - OS << "OPC_IsLegalToFold,\n"; + + case Matcher::CheckFoldableChainNode: + OS << "OPC_CheckFoldableChainNode,\n"; return 1; + + case Matcher::EmitInteger: { + int64_t Val = cast<EmitIntegerMatcher>(N)->getValue(); + OS << "OPC_EmitInteger, " + << getEnumName(cast<EmitIntegerMatcher>(N)->getVT()) << ", "; + unsigned Bytes = 2+EmitVBRValue(Val, OS); + OS << '\n'; + return Bytes; + } + case Matcher::EmitStringInteger: { + const std::string &Val = cast<EmitStringIntegerMatcher>(N)->getValue(); + // These should always fit into one byte. + OS << "OPC_EmitInteger, " + << getEnumName(cast<EmitStringIntegerMatcher>(N)->getVT()) << ", " + << Val << ",\n"; + return 3; + } + + case Matcher::EmitRegister: + OS << "OPC_EmitRegister, " + << getEnumName(cast<EmitRegisterMatcher>(N)->getVT()) << ", "; + if (Record *R = cast<EmitRegisterMatcher>(N)->getReg()) + OS << getQualifiedName(R) << ",\n"; + else { + OS << "0 "; + if (!OmitComments) + OS << "/*zero_reg*/"; + OS << ",\n"; + } + return 3; + + case Matcher::EmitConvertToTarget: + OS << "OPC_EmitConvertToTarget, " + << cast<EmitConvertToTargetMatcher>(N)->getSlot() << ",\n"; + return 2; + + case Matcher::EmitMergeInputChains: { + const EmitMergeInputChainsMatcher *MN = + cast<EmitMergeInputChainsMatcher>(N); + OS << "OPC_EmitMergeInputChains, " << MN->getNumNodes() << ", "; + for (unsigned i = 0, e = MN->getNumNodes(); i != e; ++i) + OS << MN->getNode(i) << ", "; + OS << '\n'; + return 2+MN->getNumNodes(); + } + case Matcher::EmitCopyToReg: + OS << "OPC_EmitCopyToReg, " + << cast<EmitCopyToRegMatcher>(N)->getSrcSlot() << ", " + << getQualifiedName(cast<EmitCopyToRegMatcher>(N)->getDestPhysReg()) + << ",\n"; + return 3; + case Matcher::EmitNodeXForm: { + const EmitNodeXFormMatcher *XF = cast<EmitNodeXFormMatcher>(N); + OS << "OPC_EmitNodeXForm, " << getNodeXFormID(XF->getNodeXForm()) << ", " + << XF->getSlot() << ','; + if (!OmitComments) + OS.PadToColumn(CommentIndent) << "// "<<XF->getNodeXForm()->getName(); + OS <<'\n'; + return 3; + } + + case Matcher::EmitNode: + case Matcher::MorphNodeTo: { + const EmitNodeMatcherCommon *EN = cast<EmitNodeMatcherCommon>(N); + OS << (isa<EmitNodeMatcher>(EN) ? "OPC_EmitNode" : "OPC_MorphNodeTo"); + OS << ", TARGET_OPCODE(" << EN->getOpcodeName() << "), 0"; + + if (EN->hasChain()) OS << "|OPFL_Chain"; + if (EN->hasInFlag()) OS << "|OPFL_FlagInput"; + if (EN->hasOutFlag()) OS << "|OPFL_FlagOutput"; + if (EN->hasMemRefs()) OS << "|OPFL_MemRefs"; + if (EN->getNumFixedArityOperands() != -1) + OS << "|OPFL_Variadic" << EN->getNumFixedArityOperands(); + OS << ",\n"; + + OS.PadToColumn(Indent*2+4) << EN->getNumVTs(); + if (!OmitComments) + OS << "/*#VTs*/"; + OS << ", "; + for (unsigned i = 0, e = EN->getNumVTs(); i != e; ++i) + OS << getEnumName(EN->getVT(i)) << ", "; + + OS << EN->getNumOperands(); + if (!OmitComments) + OS << "/*#Ops*/"; + OS << ", "; + unsigned NumOperandBytes = 0; + for (unsigned i = 0, e = EN->getNumOperands(); i != e; ++i) + NumOperandBytes += EmitVBRValue(EN->getOperand(i), OS); + + if (!OmitComments) { + // Print the result #'s for EmitNode. + if (const EmitNodeMatcher *E = dyn_cast<EmitNodeMatcher>(EN)) { + if (unsigned NumResults = EN->getNumVTs()) { + OS.PadToColumn(CommentIndent) << "// Results = "; + unsigned First = E->getFirstResultSlot(); + for (unsigned i = 0; i != NumResults; ++i) + OS << "#" << First+i << " "; + } + } + OS << '\n'; + + if (const MorphNodeToMatcher *SNT = dyn_cast<MorphNodeToMatcher>(N)) { + OS.PadToColumn(Indent*2) << "// Src: " + << *SNT->getPattern().getSrcPattern() << '\n'; + OS.PadToColumn(Indent*2) << "// Dst: " + << *SNT->getPattern().getDstPattern() << '\n'; + } + } else + OS << '\n'; + + return 6+EN->getNumVTs()+NumOperandBytes; + } + case Matcher::MarkFlagResults: { + const MarkFlagResultsMatcher *CFR = cast<MarkFlagResultsMatcher>(N); + OS << "OPC_MarkFlagResults, " << CFR->getNumNodes() << ", "; + unsigned NumOperandBytes = 0; + for (unsigned i = 0, e = CFR->getNumNodes(); i != e; ++i) + NumOperandBytes += EmitVBRValue(CFR->getNode(i), OS); + OS << '\n'; + return 2+NumOperandBytes; + } + case Matcher::CompleteMatch: { + const CompleteMatchMatcher *CM = cast<CompleteMatchMatcher>(N); + OS << "OPC_CompleteMatch, " << CM->getNumResults() << ", "; + unsigned NumResultBytes = 0; + for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i) + NumResultBytes += EmitVBRValue(CM->getResult(i), OS); + OS << '\n'; + if (!OmitComments) { + OS.PadToColumn(Indent*2) << "// Src: " + << *CM->getPattern().getSrcPattern() << '\n'; + OS.PadToColumn(Indent*2) << "// Dst: " + << *CM->getPattern().getDstPattern(); + } + OS << '\n'; + return 2 + NumResultBytes; + } } assert(0 && "Unreachable"); return 0; } -/// EmitMatcherAndChildren - Emit the bytes for the specified matcher subtree. +/// EmitMatcherList - Emit the bytes for the specified matcher subtree. unsigned MatcherTableEmitter:: -EmitMatcherAndChildren(const MatcherNode *N, unsigned Indent) { +EmitMatcherList(const Matcher *N, unsigned Indent, unsigned CurrentIdx, + formatted_raw_ostream &OS) { unsigned Size = 0; - while (1) { - // Push is a special case since it is binary. - if (const PushMatcherNode *PMN = dyn_cast<PushMatcherNode>(N)) { - // We need to encode the child and the offset of the failure code before - // emitting either of them. Handle this by buffering the output into a - // string while we get the size. - SmallString<128> TmpBuf; - unsigned ChildSize; - { - raw_svector_ostream OS(TmpBuf); - formatted_raw_ostream FOS(OS); - ChildSize = - EmitMatcherAndChildren(cast<PushMatcherNode>(N)->getChild(),Indent+1); - } - - if (ChildSize > 255) { - errs() << - "Tblgen internal error: can't handle predicate this complex yet\n"; - exit(1); - } - - OS.PadToColumn(Indent*2); - OS << "OPC_Push, " << ChildSize << ",\n"; - OS << TmpBuf.str(); + while (N) { + if (unsigned(N->getKind()) >= Histogram.size()) + Histogram.resize(N->getKind()+1); + Histogram[N->getKind()]++; + if (!OmitComments) + OS << "/*" << CurrentIdx << "*/"; + unsigned MatcherSize = EmitMatcher(N, Indent, CurrentIdx, OS); + Size += MatcherSize; + CurrentIdx += MatcherSize; + + // If there are other nodes in this list, iterate to them, otherwise we're + // done. + N = N->getNext(); + } + return Size; +} + +void MatcherTableEmitter::EmitPredicateFunctions(const CodeGenDAGPatterns &CGP, + formatted_raw_ostream &OS) { + // Emit pattern predicates. + if (!PatternPredicates.empty()) { + OS << "bool CheckPatternPredicate(unsigned PredNo) const {\n"; + OS << " switch (PredNo) {\n"; + OS << " default: assert(0 && \"Invalid predicate in table?\");\n"; + for (unsigned i = 0, e = PatternPredicates.size(); i != e; ++i) + OS << " case " << i << ": return " << PatternPredicates[i] << ";\n"; + OS << " }\n"; + OS << "}\n\n"; + } + + // Emit Node predicates. + // FIXME: Annoyingly, these are stored by name, which we never even emit. Yay? + StringMap<TreePattern*> PFsByName; + + for (CodeGenDAGPatterns::pf_iterator I = CGP.pf_begin(), E = CGP.pf_end(); + I != E; ++I) + PFsByName[I->first->getName()] = I->second; + + if (!NodePredicates.empty()) { + OS << "bool CheckNodePredicate(SDNode *Node, unsigned PredNo) const {\n"; + OS << " switch (PredNo) {\n"; + OS << " default: assert(0 && \"Invalid predicate in table?\");\n"; + for (unsigned i = 0, e = NodePredicates.size(); i != e; ++i) { + // FIXME: Storing this by name is horrible. + TreePattern *P =PFsByName[NodePredicates[i].substr(strlen("Predicate_"))]; + assert(P && "Unknown name?"); - Size += 2 + ChildSize; + // Emit the predicate code corresponding to this pattern. + std::string Code = P->getRecord()->getValueAsCode("Predicate"); + assert(!Code.empty() && "No code in this predicate"); + OS << " case " << i << ": { // " << NodePredicates[i] << '\n'; + std::string ClassName; + if (P->getOnlyTree()->isLeaf()) + ClassName = "SDNode"; + else + ClassName = + CGP.getSDNodeInfo(P->getOnlyTree()->getOperator()).getSDClassName(); + if (ClassName == "SDNode") + OS << " SDNode *N = Node;\n"; + else + OS << " " << ClassName << "*N = cast<" << ClassName << ">(Node);\n"; + OS << Code << "\n }\n"; + } + OS << " }\n"; + OS << "}\n\n"; + } + + // Emit CompletePattern matchers. + // FIXME: This should be const. + if (!ComplexPatterns.empty()) { + OS << "bool CheckComplexPattern(SDNode *Root, SDValue N,\n"; + OS << " unsigned PatternNo, SmallVectorImpl<SDValue> &Result) {\n"; + OS << " switch (PatternNo) {\n"; + OS << " default: assert(0 && \"Invalid pattern # in table?\");\n"; + for (unsigned i = 0, e = ComplexPatterns.size(); i != e; ++i) { + const ComplexPattern &P = *ComplexPatterns[i]; + unsigned NumOps = P.getNumOperands(); + + if (P.hasProperty(SDNPHasChain)) + ++NumOps; // Get the chained node too. - N = PMN->getFailure(); - continue; + OS << " case " << i << ":\n"; + OS << " Result.resize(Result.size()+" << NumOps << ");\n"; + OS << " return " << P.getSelectFunc(); + + OS << "(Root, N"; + for (unsigned i = 0; i != NumOps; ++i) + OS << ", Result[Result.size()-" << (NumOps-i) << ']'; + OS << ");\n"; } + OS << " }\n"; + OS << "}\n\n"; + } - Size += EmitMatcher(N, Indent); + + // Emit SDNodeXForm handlers. + // FIXME: This should be const. + if (!NodeXForms.empty()) { + OS << "SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo) {\n"; + OS << " switch (XFormNo) {\n"; + OS << " default: assert(0 && \"Invalid xform # in table?\");\n"; - // If there are children of this node, iterate to them, otherwise we're - // done. - if (const MatcherNodeWithChild *MNWC = dyn_cast<MatcherNodeWithChild>(N)) - N = MNWC->getChild(); - else - return Size; + // FIXME: The node xform could take SDValue's instead of SDNode*'s. + for (unsigned i = 0, e = NodeXForms.size(); i != e; ++i) { + const CodeGenDAGPatterns::NodeXForm &Entry = + CGP.getSDNodeTransform(NodeXForms[i]); + + Record *SDNode = Entry.first; + const std::string &Code = Entry.second; + + OS << " case " << i << ": { "; + if (!OmitComments) + OS << "// " << NodeXForms[i]->getName(); + OS << '\n'; + + std::string ClassName = CGP.getSDNodeInfo(SDNode).getSDClassName(); + if (ClassName == "SDNode") + OS << " SDNode *N = V.getNode();\n"; + else + OS << " " << ClassName << " *N = cast<" << ClassName + << ">(V.getNode());\n"; + OS << Code << "\n }\n"; + } + OS << " }\n"; + OS << "}\n\n"; } } -void MatcherTableEmitter::EmitPredicateFunctions() { - OS << "bool CheckPatternPredicate(unsigned PredNo) const {\n"; - OS << " switch (PredNo) {\n"; - OS << " default: assert(0 && \"Invalid predicate in table?\");\n"; - for (unsigned i = 0, e = PatternPredicates.size(); i != e; ++i) - OS << " case " << i << ": return " << PatternPredicates[i] << ";\n"; - OS << " }\n"; - OS << "}\n\n"; - - OS << "bool CheckNodePredicate(SDNode *N, unsigned PredNo) const {\n"; - OS << " switch (PredNo) {\n"; - OS << " default: assert(0 && \"Invalid predicate in table?\");\n"; - for (unsigned i = 0, e = NodePredicates.size(); i != e; ++i) - OS << " case " << i << ": return " << NodePredicates[i] << "(N);\n"; - OS << " }\n"; - OS << "}\n\n"; +void MatcherTableEmitter::EmitHistogram(formatted_raw_ostream &OS) { + if (OmitComments) + return; + OS << " // Opcode Histogram:\n"; + for (unsigned i = 0, e = Histogram.size(); i != e; ++i) { + OS << " // #"; + switch ((Matcher::KindTy)i) { + case Matcher::Scope: OS << "OPC_Scope"; break; + case Matcher::RecordNode: OS << "OPC_RecordNode"; break; + case Matcher::RecordChild: OS << "OPC_RecordChild"; break; + case Matcher::RecordMemRef: OS << "OPC_RecordMemRef"; break; + case Matcher::CaptureFlagInput: OS << "OPC_CaptureFlagInput"; break; + case Matcher::MoveChild: OS << "OPC_MoveChild"; break; + case Matcher::MoveParent: OS << "OPC_MoveParent"; break; + case Matcher::CheckSame: OS << "OPC_CheckSame"; break; + case Matcher::CheckPatternPredicate: + OS << "OPC_CheckPatternPredicate"; break; + case Matcher::CheckPredicate: OS << "OPC_CheckPredicate"; break; + case Matcher::CheckOpcode: OS << "OPC_CheckOpcode"; break; + case Matcher::SwitchOpcode: OS << "OPC_SwitchOpcode"; break; + case Matcher::CheckType: OS << "OPC_CheckType"; break; + case Matcher::SwitchType: OS << "OPC_SwitchType"; break; + case Matcher::CheckChildType: OS << "OPC_CheckChildType"; break; + case Matcher::CheckInteger: OS << "OPC_CheckInteger"; break; + case Matcher::CheckCondCode: OS << "OPC_CheckCondCode"; break; + case Matcher::CheckValueType: OS << "OPC_CheckValueType"; break; + case Matcher::CheckComplexPat: OS << "OPC_CheckComplexPat"; break; + case Matcher::CheckAndImm: OS << "OPC_CheckAndImm"; break; + case Matcher::CheckOrImm: OS << "OPC_CheckOrImm"; break; + case Matcher::CheckFoldableChainNode: + OS << "OPC_CheckFoldableChainNode"; break; + case Matcher::EmitInteger: OS << "OPC_EmitInteger"; break; + case Matcher::EmitStringInteger: OS << "OPC_EmitStringInteger"; break; + case Matcher::EmitRegister: OS << "OPC_EmitRegister"; break; + case Matcher::EmitConvertToTarget: OS << "OPC_EmitConvertToTarget"; break; + case Matcher::EmitMergeInputChains: OS << "OPC_EmitMergeInputChains"; break; + case Matcher::EmitCopyToReg: OS << "OPC_EmitCopyToReg"; break; + case Matcher::EmitNode: OS << "OPC_EmitNode"; break; + case Matcher::MorphNodeTo: OS << "OPC_MorphNodeTo"; break; + case Matcher::EmitNodeXForm: OS << "OPC_EmitNodeXForm"; break; + case Matcher::MarkFlagResults: OS << "OPC_MarkFlagResults"; break; + case Matcher::CompleteMatch: OS << "OPC_CompleteMatch"; break; + } + + OS.PadToColumn(40) << " = " << Histogram[i] << '\n'; + } + OS << '\n'; } -void llvm::EmitMatcherTable(const MatcherNode *Matcher, raw_ostream &O) { +void llvm::EmitMatcherTable(const Matcher *TheMatcher, + const CodeGenDAGPatterns &CGP, raw_ostream &O) { formatted_raw_ostream OS(O); OS << "// The main instruction selector code.\n"; - OS << "SDNode *SelectCode2(SDNode *N) {\n"; + OS << "SDNode *SelectCode(SDNode *N) {\n"; - MatcherTableEmitter MatcherEmitter(OS); + MatcherTableEmitter MatcherEmitter; + OS << " // Opcodes are emitted as 2 bytes, TARGET_OPCODE handles this.\n"; + OS << " #define TARGET_OPCODE(X) X & 255, unsigned(X) >> 8\n"; OS << " static const unsigned char MatcherTable[] = {\n"; - unsigned TotalSize = MatcherEmitter.EmitMatcherAndChildren(Matcher, 2); + unsigned TotalSize = MatcherEmitter.EmitMatcherList(TheMatcher, 5, 0, OS); OS << " 0\n }; // Total Array size is " << (TotalSize+1) << " bytes\n\n"; + + MatcherEmitter.EmitHistogram(OS); + + OS << " #undef TARGET_OPCODE\n"; OS << " return SelectCodeCommon(N, MatcherTable,sizeof(MatcherTable));\n}\n"; - OS << "\n"; + OS << '\n'; // Next up, emit the function for node and pattern predicates: - MatcherEmitter.EmitPredicateFunctions(); + MatcherEmitter.EmitPredicateFunctions(CGP, OS); } diff --git a/utils/TableGen/DAGISelMatcherGen.cpp b/utils/TableGen/DAGISelMatcherGen.cpp index 07ab472..4482803 100644 --- a/utils/TableGen/DAGISelMatcherGen.cpp +++ b/utils/TableGen/DAGISelMatcherGen.cpp @@ -10,9 +10,40 @@ #include "DAGISelMatcher.h" #include "CodeGenDAGPatterns.h" #include "Record.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringMap.h" +#include <utility> using namespace llvm; + +/// getRegisterValueType - Look up and return the ValueType of the specified +/// register. If the register is a member of multiple register classes which +/// have different associated types, return MVT::Other. +static MVT::SimpleValueType getRegisterValueType(Record *R, + const CodeGenTarget &T) { + bool FoundRC = false; + MVT::SimpleValueType VT = MVT::Other; + const std::vector<CodeGenRegisterClass> &RCs = T.getRegisterClasses(); + std::vector<Record*>::const_iterator Element; + + for (unsigned rc = 0, e = RCs.size(); rc != e; ++rc) { + const CodeGenRegisterClass &RC = RCs[rc]; + if (!std::count(RC.Elements.begin(), RC.Elements.end(), R)) + continue; + + if (!FoundRC) { + FoundRC = true; + VT = RC.getValueTypeNum(0); + continue; + } + + // If this occurs in multiple register classes, they all have to agree. + assert(VT == RC.getValueTypeNum(0)); + } + return VT; +} + + namespace { class MatcherGen { const PatternToMatch &Pattern; @@ -27,10 +58,31 @@ namespace { /// number that they were captured as. These are biased by 1 to make /// insertion easier. StringMap<unsigned> VariableMap; + + /// NextRecordedOperandNo - As we emit opcodes to record matched values in + /// the RecordedNodes array, this keeps track of which slot will be next to + /// record into. unsigned NextRecordedOperandNo; - MatcherNodeWithChild *Matcher; - MatcherNodeWithChild *CurPredicate; + /// MatchedChainNodes - This maintains the position in the recorded nodes + /// array of all of the recorded input nodes that have chains. + SmallVector<unsigned, 2> MatchedChainNodes; + + /// MatchedFlagResultNodes - This maintains the position in the recorded + /// nodes array of all of the recorded input nodes that have flag results. + SmallVector<unsigned, 2> MatchedFlagResultNodes; + + /// PhysRegInputs - List list has an entry for each explicitly specified + /// physreg input to the pattern. The first elt is the Register node, the + /// second is the recorded slot number the input pattern match saved it in. + SmallVector<std::pair<Record*, unsigned>, 2> PhysRegInputs; + + /// Matcher - This is the top level of the generated matcher, the result. + Matcher *TheMatcher; + + /// CurPredicate - As we emit matcher nodes, this points to the latest check + /// which should have future checks stuck into its Next position. + Matcher *CurPredicate; public: MatcherGen(const PatternToMatch &pattern, const CodeGenDAGPatterns &cgp); @@ -38,25 +90,51 @@ namespace { delete PatWithNoTypes; } - void EmitMatcherCode(); + bool EmitMatcherCode(unsigned Variant); + void EmitResultCode(); - MatcherNodeWithChild *GetMatcher() const { return Matcher; } - MatcherNodeWithChild *GetCurPredicate() const { return CurPredicate; } + Matcher *GetMatcher() const { return TheMatcher; } + Matcher *GetCurPredicate() const { return CurPredicate; } private: - void AddMatcherNode(MatcherNodeWithChild *NewNode); + void AddMatcher(Matcher *NewNode); void InferPossibleTypes(); + + // Matcher Generation. void EmitMatchCode(const TreePatternNode *N, TreePatternNode *NodeNoTypes); void EmitLeafMatchCode(const TreePatternNode *N); void EmitOperatorMatchCode(const TreePatternNode *N, TreePatternNode *NodeNoTypes); - }; + + // Result Code Generation. + unsigned getNamedArgumentSlot(StringRef Name) { + unsigned VarMapEntry = VariableMap[Name]; + assert(VarMapEntry != 0 && + "Variable referenced but not defined and not caught earlier!"); + return VarMapEntry-1; + } + + /// GetInstPatternNode - Get the pattern for an instruction. + const TreePatternNode *GetInstPatternNode(const DAGInstruction &Ins, + const TreePatternNode *N); + + void EmitResultOperand(const TreePatternNode *N, + SmallVectorImpl<unsigned> &ResultOps); + void EmitResultOfNamedOperand(const TreePatternNode *N, + SmallVectorImpl<unsigned> &ResultOps); + void EmitResultLeafAsOperand(const TreePatternNode *N, + SmallVectorImpl<unsigned> &ResultOps); + void EmitResultInstructionAsOperand(const TreePatternNode *N, + SmallVectorImpl<unsigned> &ResultOps); + void EmitResultSDNodeXFormAsOperand(const TreePatternNode *N, + SmallVectorImpl<unsigned> &ResultOps); + }; } // end anon namespace. MatcherGen::MatcherGen(const PatternToMatch &pattern, const CodeGenDAGPatterns &cgp) : Pattern(pattern), CGP(cgp), NextRecordedOperandNo(0), - Matcher(0), CurPredicate(0) { + TheMatcher(0), CurPredicate(0) { // We need to produce the matcher tree for the patterns source pattern. To do // this we need to match the structure as well as the types. To do the type // matching, we want to figure out the fewest number of type checks we need to @@ -97,23 +175,40 @@ void MatcherGen::InferPossibleTypes() { } -/// AddMatcherNode - Add a matcher node to the current graph we're building. -void MatcherGen::AddMatcherNode(MatcherNodeWithChild *NewNode) { +/// AddMatcher - Add a matcher node to the current graph we're building. +void MatcherGen::AddMatcher(Matcher *NewNode) { if (CurPredicate != 0) - CurPredicate->setChild(NewNode); + CurPredicate->setNext(NewNode); else - Matcher = NewNode; + TheMatcher = NewNode; CurPredicate = NewNode; } +//===----------------------------------------------------------------------===// +// Pattern Match Generation +//===----------------------------------------------------------------------===// /// EmitLeafMatchCode - Generate matching code for leaf nodes. void MatcherGen::EmitLeafMatchCode(const TreePatternNode *N) { assert(N->isLeaf() && "Not a leaf?"); + + // If there are node predicates for this node, generate their checks. + for (unsigned i = 0, e = N->getPredicateFns().size(); i != e; ++i) + AddMatcher(new CheckPredicateMatcher(N->getPredicateFns()[i])); + // Direct match against an integer constant. - if (IntInit *II = dynamic_cast<IntInit*>(N->getLeafValue())) - return AddMatcherNode(new CheckIntegerMatcherNode(II->getValue())); + if (IntInit *II = dynamic_cast<IntInit*>(N->getLeafValue())) { + // If this is the root of the dag we're matching, we emit a redundant opcode + // check to ensure that this gets folded into the normal top-level + // OpcodeSwitch. + if (N == Pattern.getSrcPattern()) { + const SDNodeInfo &NI = CGP.getSDNodeInfo(CGP.getSDNodeNamed("imm")); + AddMatcher(new CheckOpcodeMatcher(NI)); + } + + return AddMatcher(new CheckIntegerMatcher(II->getValue())); + } DefInit *DI = dynamic_cast<DefInit*>(N->getLeafValue()); if (DI == 0) { @@ -125,21 +220,58 @@ void MatcherGen::EmitLeafMatchCode(const TreePatternNode *N) { if (// Handle register references. Nothing to do here, they always match. LeafRec->isSubClassOf("RegisterClass") || LeafRec->isSubClassOf("PointerLikeRegClass") || - LeafRec->isSubClassOf("Register") || // Place holder for SRCVALUE nodes. Nothing to do here. LeafRec->getName() == "srcvalue") return; + + // If we have a physreg reference like (mul gpr:$src, EAX) then we need to + // record the register + if (LeafRec->isSubClassOf("Register")) { + AddMatcher(new RecordMatcher("physreg input "+LeafRec->getName(), + NextRecordedOperandNo)); + PhysRegInputs.push_back(std::make_pair(LeafRec, NextRecordedOperandNo++)); + return; + } if (LeafRec->isSubClassOf("ValueType")) - return AddMatcherNode(new CheckValueTypeMatcherNode(LeafRec->getName())); + return AddMatcher(new CheckValueTypeMatcher(LeafRec->getName())); if (LeafRec->isSubClassOf("CondCode")) - return AddMatcherNode(new CheckCondCodeMatcherNode(LeafRec->getName())); + return AddMatcher(new CheckCondCodeMatcher(LeafRec->getName())); if (LeafRec->isSubClassOf("ComplexPattern")) { + // We can't model ComplexPattern uses that don't have their name taken yet. + // The OPC_CheckComplexPattern operation implicitly records the results. + if (N->getName().empty()) { + errs() << "We expect complex pattern uses to have names: " << *N << "\n"; + exit(1); + } + // Handle complex pattern. const ComplexPattern &CP = CGP.getComplexPattern(LeafRec); - return AddMatcherNode(new CheckComplexPatMatcherNode(CP)); + + // Emit a CheckComplexPat operation, which does the match (aborting if it + // fails) and pushes the matched operands onto the recorded nodes list. + AddMatcher(new CheckComplexPatMatcher(CP)); + + // Record the right number of operands. + NextRecordedOperandNo += CP.getNumOperands(); + if (CP.hasProperty(SDNPHasChain)) + ++NextRecordedOperandNo; // Chained node operand. + + // If the complex pattern has a chain, then we need to keep track of the + // fact that we just recorded a chain input. The chain input will be + // matched as the last operand of the predicate if it was successful. + if (CP.hasProperty(SDNPHasChain)) { + // It is the last operand recorded. + assert(NextRecordedOperandNo > 1 && + "Should have recorded input/result chains at least!"); + MatchedChainNodes.push_back(NextRecordedOperandNo-1); + } + + // TODO: Complex patterns can't have output flags, if they did, we'd want + // to record them. + return; } errs() << "Unknown leaf kind: " << *N << "\n"; @@ -163,61 +295,82 @@ void MatcherGen::EmitOperatorMatchCode(const TreePatternNode *N, // to handle this. if ((N->getOperator()->getName() == "and" || N->getOperator()->getName() == "or") && - N->getChild(1)->isLeaf() && N->getChild(1)->getPredicateFns().empty()) { + N->getChild(1)->isLeaf() && N->getChild(1)->getPredicateFns().empty() && + N->getPredicateFns().empty()) { if (IntInit *II = dynamic_cast<IntInit*>(N->getChild(1)->getLeafValue())) { if (!isPowerOf2_32(II->getValue())) { // Don't bother with single bits. + // If this is at the root of the pattern, we emit a redundant + // CheckOpcode so that the following checks get factored properly under + // a single opcode check. + if (N == Pattern.getSrcPattern()) + AddMatcher(new CheckOpcodeMatcher(CInfo)); + + // Emit the CheckAndImm/CheckOrImm node. if (N->getOperator()->getName() == "and") - AddMatcherNode(new CheckAndImmMatcherNode(II->getValue())); + AddMatcher(new CheckAndImmMatcher(II->getValue())); else - AddMatcherNode(new CheckOrImmMatcherNode(II->getValue())); + AddMatcher(new CheckOrImmMatcher(II->getValue())); // Match the LHS of the AND as appropriate. - AddMatcherNode(new MoveChildMatcherNode(0)); + AddMatcher(new MoveChildMatcher(0)); EmitMatchCode(N->getChild(0), NodeNoTypes->getChild(0)); - AddMatcherNode(new MoveParentMatcherNode()); + AddMatcher(new MoveParentMatcher()); return; } } } // Check that the current opcode lines up. - AddMatcherNode(new CheckOpcodeMatcherNode(CInfo.getEnumName())); + AddMatcher(new CheckOpcodeMatcher(CInfo)); + + // If there are node predicates for this node, generate their checks. + for (unsigned i = 0, e = N->getPredicateFns().size(); i != e; ++i) + AddMatcher(new CheckPredicateMatcher(N->getPredicateFns()[i])); + + + // If this node has memory references (i.e. is a load or store), tell the + // interpreter to capture them in the memref array. + if (N->NodeHasProperty(SDNPMemOperand, CGP)) + AddMatcher(new RecordMemRefMatcher()); // If this node has a chain, then the chain is operand #0 is the SDNode, and // the child numbers of the node are all offset by one. unsigned OpNo = 0; - if (N->NodeHasProperty(SDNPHasChain, CGP)) + if (N->NodeHasProperty(SDNPHasChain, CGP)) { + // Record the node and remember it in our chained nodes list. + AddMatcher(new RecordMatcher("'" + N->getOperator()->getName() + + "' chained node", + NextRecordedOperandNo)); + // Remember all of the input chains our pattern will match. + MatchedChainNodes.push_back(NextRecordedOperandNo++); + + // Don't look at the input chain when matching the tree pattern to the + // SDNode. OpNo = 1; - // If this node is not the root and the subtree underneath it produces a - // chain, then the result of matching the node is also produce a chain. - // Beyond that, this means that we're also folding (at least) the root node - // into the node that produce the chain (for example, matching - // "(add reg, (load ptr))" as a add_with_memory on X86). This is problematic, - // if the 'reg' node also uses the load (say, its chain). Graphically: - // - // [LD] - // ^ ^ - // | \ DAG's like cheese. - // / | - // / [YY] - // | ^ - // [XX]--/ - // - // It would be invalid to fold XX and LD. In this case, folding the two - // nodes together would induce a cycle in the DAG, making it a cyclic DAG (!). - // To prevent this, we emit a dynamic check for legality before allowing this - // to be folded. - // - const TreePatternNode *Root = Pattern.getSrcPattern(); - if (N != Root && // Not the root of the pattern. - N->TreeHasProperty(SDNPHasChain, CGP)) { // Has a chain somewhere in tree. - - AddMatcherNode(new CheckProfitableToFoldMatcherNode()); - - // If this non-root node produces a chain, we may need to emit a validity - // check. - if (OpNo != 0) { + // If this node is not the root and the subtree underneath it produces a + // chain, then the result of matching the node is also produce a chain. + // Beyond that, this means that we're also folding (at least) the root node + // into the node that produce the chain (for example, matching + // "(add reg, (load ptr))" as a add_with_memory on X86). This is + // problematic, if the 'reg' node also uses the load (say, its chain). + // Graphically: + // + // [LD] + // ^ ^ + // | \ DAG's like cheese. + // / | + // / [YY] + // | ^ + // [XX]--/ + // + // It would be invalid to fold XX and LD. In this case, folding the two + // nodes together would induce a cycle in the DAG, making it a 'cyclic DAG' + // To prevent this, we emit a dynamic check for legality before allowing + // this to be folded. + // + const TreePatternNode *Root = Pattern.getSrcPattern(); + if (N != Root) { // Not the root of the pattern. // If there is a node between the root and this node, then we definitely // need to emit the check. bool NeedCheck = !Root->hasChild(N); @@ -239,16 +392,35 @@ void MatcherGen::EmitOperatorMatchCode(const TreePatternNode *N, } if (NeedCheck) - AddMatcherNode(new CheckLegalToFoldMatcherNode()); + AddMatcher(new CheckFoldableChainNodeMatcher()); } } + + // If this node has an output flag and isn't the root, remember it. + if (N->NodeHasProperty(SDNPOutFlag, CGP) && + N != Pattern.getSrcPattern()) { + // TODO: This redundantly records nodes with both flags and chains. + + // Record the node and remember it in our chained nodes list. + AddMatcher(new RecordMatcher("'" + N->getOperator()->getName() + + "' flag output node", + NextRecordedOperandNo)); + // Remember all of the nodes with output flags our pattern will match. + MatchedFlagResultNodes.push_back(NextRecordedOperandNo++); + } + + // If this node is known to have an input flag or if it *might* have an input + // flag, capture it as the flag input of the pattern. + if (N->NodeHasProperty(SDNPOptInFlag, CGP) || + N->NodeHasProperty(SDNPInFlag, CGP)) + AddMatcher(new CaptureFlagInputMatcher()); for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) { // Get the code suitable for matching this child. Move to the child, check // it then move back to the parent. - AddMatcherNode(new MoveChildMatcherNode(i)); + AddMatcher(new MoveChildMatcher(OpNo)); EmitMatchCode(N->getChild(i), NodeNoTypes->getChild(i)); - AddMatcherNode(new MoveParentMatcherNode()); + AddMatcher(new MoveParentMatcher()); } } @@ -258,70 +430,424 @@ void MatcherGen::EmitMatchCode(const TreePatternNode *N, // If N and NodeNoTypes don't agree on a type, then this is a case where we // need to do a type check. Emit the check, apply the tyep to NodeNoTypes and // reinfer any correlated types. + unsigned NodeType = EEVT::isUnknown; if (NodeNoTypes->getExtTypes() != N->getExtTypes()) { - AddMatcherNode(new CheckTypeMatcherNode(N->getTypeNum(0))); + NodeType = N->getTypeNum(0); NodeNoTypes->setTypes(N->getExtTypes()); InferPossibleTypes(); } - // If this node has a name associated with it, capture it in VariableMap. If // we already saw this in the pattern, emit code to verify dagness. if (!N->getName().empty()) { unsigned &VarMapEntry = VariableMap[N->getName()]; if (VarMapEntry == 0) { + // If it is a named node, we must emit a 'Record' opcode. + AddMatcher(new RecordMatcher("$" + N->getName(), NextRecordedOperandNo)); VarMapEntry = ++NextRecordedOperandNo; - AddMatcherNode(new RecordMatcherNode()); } 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. - AddMatcherNode(new CheckSameMatcherNode(VarMapEntry-1)); + AddMatcher(new CheckSameMatcher(VarMapEntry-1)); return; } } - // If there are node predicates for this node, generate their checks. - for (unsigned i = 0, e = N->getPredicateFns().size(); i != e; ++i) - AddMatcherNode(new CheckPredicateMatcherNode(N->getPredicateFns()[i])); - if (N->isLeaf()) EmitLeafMatchCode(N); else EmitOperatorMatchCode(N, NodeNoTypes); + + if (NodeType != EEVT::isUnknown) + AddMatcher(new CheckTypeMatcher((MVT::SimpleValueType)NodeType)); + } -void MatcherGen::EmitMatcherCode() { +/// EmitMatcherCode - Generate the code that matches the predicate of this +/// pattern for the specified Variant. If the variant is invalid this returns +/// true and does not generate code, if it is valid, it returns false. +bool MatcherGen::EmitMatcherCode(unsigned Variant) { + // If the root of the pattern is a ComplexPattern and if it is specified to + // match some number of root opcodes, these are considered to be our variants. + // Depending on which variant we're generating code for, emit the root opcode + // check. + if (const ComplexPattern *CP = + Pattern.getSrcPattern()->getComplexPatternInfo(CGP)) { + const std::vector<Record*> &OpNodes = CP->getRootNodes(); + assert(!OpNodes.empty() &&"Complex Pattern must specify what it can match"); + if (Variant >= OpNodes.size()) return true; + + AddMatcher(new CheckOpcodeMatcher(CGP.getSDNodeInfo(OpNodes[Variant]))); + } else { + if (Variant != 0) return true; + } + // If the pattern has a predicate on it (e.g. only enabled when a subtarget // feature is around, do the check). + // FIXME: This should get emitted after the match code below to encourage + // sharing. This can't happen until we get an X86ISD::AddrMode node made by + // dag combine, eliminating the horrible side-effect-full stuff from + // X86's MatchAddress. if (!Pattern.getPredicateCheck().empty()) - AddMatcherNode(new - CheckPatternPredicateMatcherNode(Pattern.getPredicateCheck())); - + AddMatcher(new CheckPatternPredicateMatcher(Pattern.getPredicateCheck())); + // Emit the matcher for the pattern structure and types. EmitMatchCode(Pattern.getSrcPattern(), PatWithNoTypes); + return false; +} + + +//===----------------------------------------------------------------------===// +// Node Result Generation +//===----------------------------------------------------------------------===// + +void MatcherGen::EmitResultOfNamedOperand(const TreePatternNode *N, + SmallVectorImpl<unsigned> &ResultOps){ + assert(!N->getName().empty() && "Operand not named!"); + + unsigned SlotNo = getNamedArgumentSlot(N->getName()); + + // A reference to a complex pattern gets all of the results of the complex + // pattern's match. + if (const ComplexPattern *CP = N->getComplexPatternInfo(CGP)) { + // The first slot entry is the node itself, the subsequent entries are the + // matched values. + for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i) + ResultOps.push_back(SlotNo+i+1); + return; + } + + // If this is an 'imm' or 'fpimm' node, make sure to convert it to the target + // version of the immediate so that it doesn't get selected due to some other + // node use. + if (!N->isLeaf()) { + StringRef OperatorName = N->getOperator()->getName(); + if (OperatorName == "imm" || OperatorName == "fpimm") { + AddMatcher(new EmitConvertToTargetMatcher(SlotNo)); + ResultOps.push_back(NextRecordedOperandNo++); + return; + } + } + + ResultOps.push_back(SlotNo); +} + +void MatcherGen::EmitResultLeafAsOperand(const TreePatternNode *N, + SmallVectorImpl<unsigned> &ResultOps) { + assert(N->isLeaf() && "Must be a leaf"); + + if (IntInit *II = dynamic_cast<IntInit*>(N->getLeafValue())) { + AddMatcher(new EmitIntegerMatcher(II->getValue(),N->getTypeNum(0))); + ResultOps.push_back(NextRecordedOperandNo++); + return; + } + + // If this is an explicit register reference, handle it. + if (DefInit *DI = dynamic_cast<DefInit*>(N->getLeafValue())) { + if (DI->getDef()->isSubClassOf("Register")) { + AddMatcher(new EmitRegisterMatcher(DI->getDef(), + N->getTypeNum(0))); + ResultOps.push_back(NextRecordedOperandNo++); + return; + } + + if (DI->getDef()->getName() == "zero_reg") { + AddMatcher(new EmitRegisterMatcher(0, N->getTypeNum(0))); + ResultOps.push_back(NextRecordedOperandNo++); + return; + } + + // Handle a reference to a register class. This is used + // in COPY_TO_SUBREG instructions. + if (DI->getDef()->isSubClassOf("RegisterClass")) { + std::string Value = getQualifiedName(DI->getDef()) + "RegClassID"; + AddMatcher(new EmitStringIntegerMatcher(Value, MVT::i32)); + ResultOps.push_back(NextRecordedOperandNo++); + return; + } + } + + errs() << "unhandled leaf node: \n"; + N->dump(); +} + +/// GetInstPatternNode - Get the pattern for an instruction. +/// +const TreePatternNode *MatcherGen:: +GetInstPatternNode(const DAGInstruction &Inst, const TreePatternNode *N) { + const TreePattern *InstPat = Inst.getPattern(); + + // FIXME2?: Assume actual pattern comes before "implicit". + TreePatternNode *InstPatNode; + if (InstPat) + InstPatNode = InstPat->getTree(0); + else if (/*isRoot*/ N == Pattern.getDstPattern()) + InstPatNode = Pattern.getSrcPattern(); + else + return 0; + + if (InstPatNode && !InstPatNode->isLeaf() && + InstPatNode->getOperator()->getName() == "set") + InstPatNode = InstPatNode->getChild(InstPatNode->getNumChildren()-1); + + return InstPatNode; } +void MatcherGen:: +EmitResultInstructionAsOperand(const TreePatternNode *N, + SmallVectorImpl<unsigned> &OutputOps) { + Record *Op = N->getOperator(); + const CodeGenTarget &CGT = CGP.getTargetInfo(); + CodeGenInstruction &II = CGT.getInstruction(Op->getName()); + const DAGInstruction &Inst = CGP.getInstruction(Op); + + // If we can, get the pattern for the instruction we're generating. We derive + // a variety of information from this pattern, such as whether it has a chain. + // + // FIXME2: This is extremely dubious for several reasons, not the least of + // which it gives special status to instructions with patterns that Pat<> + // nodes can't duplicate. + const TreePatternNode *InstPatNode = GetInstPatternNode(Inst, N); + + // NodeHasChain - Whether the instruction node we're creating takes chains. + bool NodeHasChain = InstPatNode && + InstPatNode->TreeHasProperty(SDNPHasChain, CGP); + + bool isRoot = N == Pattern.getDstPattern(); + + // TreeHasOutFlag - True if this tree has a flag. + bool TreeHasInFlag = false, TreeHasOutFlag = false; + if (isRoot) { + const TreePatternNode *SrcPat = Pattern.getSrcPattern(); + TreeHasInFlag = SrcPat->TreeHasProperty(SDNPOptInFlag, CGP) || + SrcPat->TreeHasProperty(SDNPInFlag, CGP); + + // FIXME2: this is checking the entire pattern, not just the node in + // question, doing this just for the root seems like a total hack. + TreeHasOutFlag = SrcPat->TreeHasProperty(SDNPOutFlag, CGP); + } + + // NumResults - This is the number of results produced by the instruction in + // the "outs" list. + unsigned NumResults = Inst.getNumResults(); -MatcherNode *llvm::ConvertPatternToMatcher(const PatternToMatch &Pattern, - const CodeGenDAGPatterns &CGP) { + // Loop over all of the operands of the instruction pattern, emitting code + // to fill them all in. The node 'N' usually has number children equal to + // the number of input operands of the instruction. However, in cases + // where there are predicate operands for an instruction, we need to fill + // in the 'execute always' values. Match up the node operands to the + // instruction operands to do this. + SmallVector<unsigned, 8> InstOps; + for (unsigned ChildNo = 0, InstOpNo = NumResults, e = II.OperandList.size(); + InstOpNo != e; ++InstOpNo) { + + // Determine what to emit for this operand. + Record *OperandNode = II.OperandList[InstOpNo].Rec; + if ((OperandNode->isSubClassOf("PredicateOperand") || + OperandNode->isSubClassOf("OptionalDefOperand")) && + !CGP.getDefaultOperand(OperandNode).DefaultOps.empty()) { + // This is a predicate or optional def operand; emit the + // 'default ops' operands. + const DAGDefaultOperand &DefaultOp = + CGP.getDefaultOperand(II.OperandList[InstOpNo].Rec); + for (unsigned i = 0, e = DefaultOp.DefaultOps.size(); i != e; ++i) + EmitResultOperand(DefaultOp.DefaultOps[i], InstOps); + continue; + } + + // Otherwise this is a normal operand or a predicate operand without + // 'execute always'; emit it. + EmitResultOperand(N->getChild(ChildNo), InstOps); + ++ChildNo; + } + + // If this node has an input flag or explicitly specified input physregs, we + // need to add chained and flagged copyfromreg nodes and materialize the flag + // input. + if (isRoot && !PhysRegInputs.empty()) { + // Emit all of the CopyToReg nodes for the input physical registers. These + // occur in patterns like (mul:i8 AL:i8, GR8:i8:$src). + for (unsigned i = 0, e = PhysRegInputs.size(); i != e; ++i) + AddMatcher(new EmitCopyToRegMatcher(PhysRegInputs[i].second, + PhysRegInputs[i].first)); + // Even if the node has no other flag inputs, the resultant node must be + // flagged to the CopyFromReg nodes we just generated. + TreeHasInFlag = true; + } + + // Result order: node results, chain, flags + + // Determine the result types. + SmallVector<MVT::SimpleValueType, 4> ResultVTs; + if (NumResults != 0 && N->getTypeNum(0) != MVT::isVoid) { + // FIXME2: If the node has multiple results, we should add them. For now, + // preserve existing behavior?! + ResultVTs.push_back(N->getTypeNum(0)); + } + + + // If this is the root instruction of a pattern that has physical registers in + // its result pattern, add output VTs for them. For example, X86 has: + // (set AL, (mul ...)) + // This also handles implicit results like: + // (implicit EFLAGS) + if (isRoot && Pattern.getDstRegs().size() != 0) { + for (unsigned i = 0; i != Pattern.getDstRegs().size(); ++i) + if (Pattern.getDstRegs()[i]->isSubClassOf("Register")) + ResultVTs.push_back(getRegisterValueType(Pattern.getDstRegs()[i], CGT)); + } + + // FIXME2: Instead of using the isVariadic flag on the instruction, we should + // have an SDNP that indicates variadicism. The TargetInstrInfo isVariadic + // property should be inferred from this when an instruction has a pattern. + int NumFixedArityOperands = -1; + if (isRoot && II.isVariadic) + NumFixedArityOperands = Pattern.getSrcPattern()->getNumChildren(); + + // If this is the root node and any of the nodes matched nodes in the input + // pattern have MemRefs in them, have the interpreter collect them and plop + // them onto this node. + // + // FIXME3: This is actively incorrect for result patterns where the root of + // the pattern is not the memory reference and is also incorrect when the + // result pattern has multiple memory-referencing instructions. For example, + // in the X86 backend, this pattern causes the memrefs to get attached to the + // CVTSS2SDrr instead of the MOVSSrm: + // + // def : Pat<(extloadf32 addr:$src), + // (CVTSS2SDrr (MOVSSrm addr:$src))>; + // + bool NodeHasMemRefs = + isRoot && Pattern.getSrcPattern()->TreeHasProperty(SDNPMemOperand, CGP); + + AddMatcher(new EmitNodeMatcher(II.Namespace+"::"+II.TheDef->getName(), + ResultVTs.data(), ResultVTs.size(), + InstOps.data(), InstOps.size(), + NodeHasChain, TreeHasInFlag, TreeHasOutFlag, + NodeHasMemRefs, NumFixedArityOperands, + NextRecordedOperandNo)); + + // The non-chain and non-flag results of the newly emitted node get recorded. + for (unsigned i = 0, e = ResultVTs.size(); i != e; ++i) { + if (ResultVTs[i] == MVT::Other || ResultVTs[i] == MVT::Flag) break; + OutputOps.push_back(NextRecordedOperandNo++); + } +} + +void MatcherGen:: +EmitResultSDNodeXFormAsOperand(const TreePatternNode *N, + SmallVectorImpl<unsigned> &ResultOps) { + assert(N->getOperator()->isSubClassOf("SDNodeXForm") && "Not SDNodeXForm?"); + + // Emit the operand. + SmallVector<unsigned, 8> InputOps; + + // FIXME2: Could easily generalize this to support multiple inputs and outputs + // to the SDNodeXForm. For now we just support one input and one output like + // the old instruction selector. + assert(N->getNumChildren() == 1); + EmitResultOperand(N->getChild(0), InputOps); + + // The input currently must have produced exactly one result. + assert(InputOps.size() == 1 && "Unexpected input to SDNodeXForm"); + + AddMatcher(new EmitNodeXFormMatcher(InputOps[0], N->getOperator())); + ResultOps.push_back(NextRecordedOperandNo++); +} + +void MatcherGen::EmitResultOperand(const TreePatternNode *N, + SmallVectorImpl<unsigned> &ResultOps) { + // This is something selected from the pattern we matched. + if (!N->getName().empty()) + return EmitResultOfNamedOperand(N, ResultOps); + + if (N->isLeaf()) + return EmitResultLeafAsOperand(N, ResultOps); + + Record *OpRec = N->getOperator(); + if (OpRec->isSubClassOf("Instruction")) + return EmitResultInstructionAsOperand(N, ResultOps); + if (OpRec->isSubClassOf("SDNodeXForm")) + return EmitResultSDNodeXFormAsOperand(N, ResultOps); + errs() << "Unknown result node to emit code for: " << *N << '\n'; + throw std::string("Unknown node in result pattern!"); +} + +void MatcherGen::EmitResultCode() { + // Patterns that match nodes with (potentially multiple) chain inputs have to + // merge them together into a token factor. This informs the generated code + // what all the chained nodes are. + if (!MatchedChainNodes.empty()) + AddMatcher(new EmitMergeInputChainsMatcher + (MatchedChainNodes.data(), MatchedChainNodes.size())); + + // Codegen the root of the result pattern, capturing the resulting values. + SmallVector<unsigned, 8> Ops; + EmitResultOperand(Pattern.getDstPattern(), Ops); + + // At this point, we have however many values the result pattern produces. + // However, the input pattern might not need all of these. If there are + // excess values at the end (such as condition codes etc) just lop them off. + // This doesn't need to worry about flags or chains, just explicit results. + // + // FIXME2: This doesn't work because there is currently no way to get an + // accurate count of the # results the source pattern sets. This is because + // of the "parallel" construct in X86 land, which looks like this: + // + //def : Pat<(parallel (X86and_flag GR8:$src1, GR8:$src2), + // (implicit EFLAGS)), + // (AND8rr GR8:$src1, GR8:$src2)>; + // + // This idiom means to match the two-result node X86and_flag (which is + // declared as returning a single result, because we can't match multi-result + // nodes yet). In this case, we would have to know that the input has two + // results. However, mul8r is modelled exactly the same way, but without + // implicit defs included. The fix is to support multiple results directly + // and eliminate 'parallel'. + // + // FIXME2: When this is fixed, we should revert the terrible hack in the + // OPC_EmitNode code in the interpreter. +#if 0 + const TreePatternNode *Src = Pattern.getSrcPattern(); + unsigned NumSrcResults = Src->getTypeNum(0) != MVT::isVoid ? 1 : 0; + NumSrcResults += Pattern.getDstRegs().size(); + assert(Ops.size() >= NumSrcResults && "Didn't provide enough results"); + Ops.resize(NumSrcResults); +#endif + + // If the matched pattern covers nodes which define a flag result, emit a node + // that tells the matcher about them so that it can update their results. + if (!MatchedFlagResultNodes.empty()) + AddMatcher(new MarkFlagResultsMatcher(MatchedFlagResultNodes.data(), + MatchedFlagResultNodes.size())); + + AddMatcher(new CompleteMatchMatcher(Ops.data(), Ops.size(), Pattern)); +} + + +/// ConvertPatternToMatcher - Create the matcher for the specified pattern with +/// the specified variant. If the variant number is invalid, this returns null. +Matcher *llvm::ConvertPatternToMatcher(const PatternToMatch &Pattern, + unsigned Variant, + const CodeGenDAGPatterns &CGP) { MatcherGen Gen(Pattern, CGP); // Generate the code for the matcher. - Gen.EmitMatcherCode(); + if (Gen.EmitMatcherCode(Variant)) + return 0; - // If the match succeeds, then we generate Pattern. - EmitNodeMatcherNode *Result = new EmitNodeMatcherNode(Pattern); + // FIXME2: Kill extra MoveParent commands at the end of the matcher sequence. + // FIXME2: Split result code out to another table, and make the matcher end + // with an "Emit <index>" command. This allows result generation stuff to be + // shared and factored? - // Link it into the pattern. - if (MatcherNodeWithChild *Pred = Gen.GetCurPredicate()) { - Pred->setChild(Result); - return Gen.GetMatcher(); - } + // If the match succeeds, then we generate Pattern. + Gen.EmitResultCode(); // Unconditional match. - return Result; + return Gen.GetMatcher(); } diff --git a/utils/TableGen/DAGISelMatcherOpt.cpp b/utils/TableGen/DAGISelMatcherOpt.cpp new file mode 100644 index 0000000..dc077a9 --- /dev/null +++ b/utils/TableGen/DAGISelMatcherOpt.cpp @@ -0,0 +1,435 @@ +//===- DAGISelMatcherOpt.cpp - Optimize a DAG Matcher ---------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the DAG Matcher optimizer. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "isel-opt" +#include "DAGISelMatcher.h" +#include "CodeGenDAGPatterns.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/StringSet.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include <vector> +using namespace llvm; + +/// ContractNodes - Turn multiple matcher node patterns like 'MoveChild+Record' +/// into single compound nodes like RecordChild. +static void ContractNodes(OwningPtr<Matcher> &MatcherPtr, + const CodeGenDAGPatterns &CGP) { + // If we reached the end of the chain, we're done. + Matcher *N = MatcherPtr.get(); + if (N == 0) return; + + // If we have a scope node, walk down all of the children. + if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) { + for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { + OwningPtr<Matcher> Child(Scope->takeChild(i)); + ContractNodes(Child, CGP); + Scope->resetChild(i, Child.take()); + } + return; + } + + // If we found a movechild node with a node that comes in a 'foochild' form, + // transform it. + if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) { + Matcher *New = 0; + if (RecordMatcher *RM = dyn_cast<RecordMatcher>(MC->getNext())) + New = new RecordChildMatcher(MC->getChildNo(), RM->getWhatFor(), + RM->getResultNo()); + + if (CheckTypeMatcher *CT= dyn_cast<CheckTypeMatcher>(MC->getNext())) + New = new CheckChildTypeMatcher(MC->getChildNo(), CT->getType()); + + if (New) { + // Insert the new node. + New->setNext(MatcherPtr.take()); + MatcherPtr.reset(New); + // Remove the old one. + MC->setNext(MC->getNext()->takeNext()); + return ContractNodes(MatcherPtr, CGP); + } + } + + // Zap movechild -> moveparent. + if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) + if (MoveParentMatcher *MP = + dyn_cast<MoveParentMatcher>(MC->getNext())) { + MatcherPtr.reset(MP->takeNext()); + return ContractNodes(MatcherPtr, CGP); + } + + // Turn EmitNode->MarkFlagResults->CompleteMatch into + // MarkFlagResults->EmitNode->CompleteMatch when we can to encourage + // MorphNodeTo formation. This is safe because MarkFlagResults never refers + // to the root of the pattern. + if (isa<EmitNodeMatcher>(N) && isa<MarkFlagResultsMatcher>(N->getNext()) && + isa<CompleteMatchMatcher>(N->getNext()->getNext())) { + // Unlink the two nodes from the list. + Matcher *EmitNode = MatcherPtr.take(); + Matcher *MFR = EmitNode->takeNext(); + Matcher *Tail = MFR->takeNext(); + + // Relink them. + MatcherPtr.reset(MFR); + MFR->setNext(EmitNode); + EmitNode->setNext(Tail); + return ContractNodes(MatcherPtr, CGP); + } + + // Turn EmitNode->CompleteMatch into MorphNodeTo if we can. + if (EmitNodeMatcher *EN = dyn_cast<EmitNodeMatcher>(N)) + if (CompleteMatchMatcher *CM = + dyn_cast<CompleteMatchMatcher>(EN->getNext())) { + // We can only use MorphNodeTo if the result values match up. + unsigned RootResultFirst = EN->getFirstResultSlot(); + bool ResultsMatch = true; + for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i) + if (CM->getResult(i) != RootResultFirst+i) + ResultsMatch = false; + + // If the selected node defines a subset of the flag/chain results, we + // can't use MorphNodeTo. For example, we can't use MorphNodeTo if the + // matched pattern has a chain but the root node doesn't. + const PatternToMatch &Pattern = CM->getPattern(); + + if (!EN->hasChain() && + Pattern.getSrcPattern()->NodeHasProperty(SDNPHasChain, CGP)) + ResultsMatch = false; + + // If the matched node has a flag and the output root doesn't, we can't + // use MorphNodeTo. + // + // NOTE: Strictly speaking, we don't have to check for the flag here + // because the code in the pattern generator doesn't handle it right. We + // do it anyway for thoroughness. + if (!EN->hasOutFlag() && + Pattern.getSrcPattern()->NodeHasProperty(SDNPOutFlag, CGP)) + ResultsMatch = false; + + + // If the root result node defines more results than the source root node + // *and* has a chain or flag input, then we can't match it because it + // would end up replacing the extra result with the chain/flag. +#if 0 + if ((EN->hasFlag() || EN->hasChain()) && + EN->getNumNonChainFlagVTs() > ... need to get no results reliably ...) + ResultMatch = false; +#endif + + if (ResultsMatch) { + const SmallVectorImpl<MVT::SimpleValueType> &VTs = EN->getVTList(); + const SmallVectorImpl<unsigned> &Operands = EN->getOperandList(); + MatcherPtr.reset(new MorphNodeToMatcher(EN->getOpcodeName(), + VTs.data(), VTs.size(), + Operands.data(),Operands.size(), + EN->hasChain(), EN->hasInFlag(), + EN->hasOutFlag(), + EN->hasMemRefs(), + EN->getNumFixedArityOperands(), + Pattern)); + return; + } + + // FIXME2: Kill off all the SelectionDAG::SelectNodeTo and getMachineNode + // variants. + } + + ContractNodes(N->getNextPtr(), CGP); + + + // If we have a CheckType/CheckChildType/Record node followed by a + // CheckOpcode, invert the two nodes. We prefer to do structural checks + // before type checks, as this opens opportunities for factoring on targets + // like X86 where many operations are valid on multiple types. + if ((isa<CheckTypeMatcher>(N) || isa<CheckChildTypeMatcher>(N) || + isa<RecordMatcher>(N)) && + isa<CheckOpcodeMatcher>(N->getNext())) { + // Unlink the two nodes from the list. + Matcher *CheckType = MatcherPtr.take(); + Matcher *CheckOpcode = CheckType->takeNext(); + Matcher *Tail = CheckOpcode->takeNext(); + + // Relink them. + MatcherPtr.reset(CheckOpcode); + CheckOpcode->setNext(CheckType); + CheckType->setNext(Tail); + return ContractNodes(MatcherPtr, CGP); + } +} + +/// SinkPatternPredicates - Pattern predicates can be checked at any level of +/// the matching tree. The generator dumps them at the top level of the pattern +/// though, which prevents factoring from being able to see past them. This +/// optimization sinks them as far down into the pattern as possible. +/// +/// Conceptually, we'd like to sink these predicates all the way to the last +/// matcher predicate in the series. However, it turns out that some +/// ComplexPatterns have side effects on the graph, so we really don't want to +/// run a the complex pattern if the pattern predicate will fail. For this +/// reason, we refuse to sink the pattern predicate past a ComplexPattern. +/// +static void SinkPatternPredicates(OwningPtr<Matcher> &MatcherPtr) { + // Recursively scan for a PatternPredicate. + // If we reached the end of the chain, we're done. + Matcher *N = MatcherPtr.get(); + if (N == 0) return; + + // Walk down all members of a scope node. + if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) { + for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { + OwningPtr<Matcher> Child(Scope->takeChild(i)); + SinkPatternPredicates(Child); + Scope->resetChild(i, Child.take()); + } + return; + } + + // If this node isn't a CheckPatternPredicateMatcher we keep scanning until + // we find one. + CheckPatternPredicateMatcher *CPPM =dyn_cast<CheckPatternPredicateMatcher>(N); + if (CPPM == 0) + return SinkPatternPredicates(N->getNextPtr()); + + // Ok, we found one, lets try to sink it. Check if we can sink it past the + // next node in the chain. If not, we won't be able to change anything and + // might as well bail. + if (!CPPM->getNext()->isSafeToReorderWithPatternPredicate()) + return; + + // Okay, we know we can sink it past at least one node. Unlink it from the + // chain and scan for the new insertion point. + MatcherPtr.take(); // Don't delete CPPM. + MatcherPtr.reset(CPPM->takeNext()); + + N = MatcherPtr.get(); + while (N->getNext()->isSafeToReorderWithPatternPredicate()) + N = N->getNext(); + + // At this point, we want to insert CPPM after N. + CPPM->setNext(N->takeNext()); + N->setNext(CPPM); +} + +/// FactorNodes - Turn matches like this: +/// Scope +/// OPC_CheckType i32 +/// ABC +/// OPC_CheckType i32 +/// XYZ +/// into: +/// OPC_CheckType i32 +/// Scope +/// ABC +/// XYZ +/// +static void FactorNodes(OwningPtr<Matcher> &MatcherPtr) { + // If we reached the end of the chain, we're done. + Matcher *N = MatcherPtr.get(); + if (N == 0) return; + + // If this is not a push node, just scan for one. + ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N); + if (Scope == 0) + return FactorNodes(N->getNextPtr()); + + // Okay, pull together the children of the scope node into a vector so we can + // inspect it more easily. While we're at it, bucket them up by the hash + // code of their first predicate. + SmallVector<Matcher*, 32> OptionsToMatch; + + for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { + // Factor the subexpression. + OwningPtr<Matcher> Child(Scope->takeChild(i)); + FactorNodes(Child); + + if (Matcher *N = Child.take()) + OptionsToMatch.push_back(N); + } + + SmallVector<Matcher*, 32> NewOptionsToMatch; + + // Loop over options to match, merging neighboring patterns with identical + // starting nodes into a shared matcher. + for (unsigned OptionIdx = 0, e = OptionsToMatch.size(); OptionIdx != e;) { + // Find the set of matchers that start with this node. + Matcher *Optn = OptionsToMatch[OptionIdx++]; + + if (OptionIdx == e) { + NewOptionsToMatch.push_back(Optn); + continue; + } + + // See if the next option starts with the same matcher. If the two + // neighbors *do* start with the same matcher, we can factor the matcher out + // of at least these two patterns. See what the maximal set we can merge + // together is. + SmallVector<Matcher*, 8> EqualMatchers; + EqualMatchers.push_back(Optn); + + // Factor all of the known-equal matchers after this one into the same + // group. + while (OptionIdx != e && OptionsToMatch[OptionIdx]->isEqual(Optn)) + EqualMatchers.push_back(OptionsToMatch[OptionIdx++]); + + // If we found a non-equal matcher, see if it is contradictory with the + // current node. If so, we know that the ordering relation between the + // current sets of nodes and this node don't matter. Look past it to see if + // we can merge anything else into this matching group. + unsigned Scan = OptionIdx; + while (1) { + while (Scan != e && Optn->isContradictory(OptionsToMatch[Scan])) + ++Scan; + + // Ok, we found something that isn't known to be contradictory. If it is + // equal, we can merge it into the set of nodes to factor, if not, we have + // to cease factoring. + if (Scan == e || !Optn->isEqual(OptionsToMatch[Scan])) break; + + // If is equal after all, add the option to EqualMatchers and remove it + // from OptionsToMatch. + EqualMatchers.push_back(OptionsToMatch[Scan]); + OptionsToMatch.erase(OptionsToMatch.begin()+Scan); + --e; + } + + if (Scan != e && + // Don't print it's obvious nothing extra could be merged anyway. + Scan+1 != e) { + DEBUG(errs() << "Couldn't merge this:\n"; + Optn->print(errs(), 4); + errs() << "into this:\n"; + OptionsToMatch[Scan]->print(errs(), 4); + if (Scan+1 != e) + OptionsToMatch[Scan+1]->printOne(errs()); + if (Scan+2 < e) + OptionsToMatch[Scan+2]->printOne(errs()); + errs() << "\n"); + } + + // If we only found one option starting with this matcher, no factoring is + // possible. + if (EqualMatchers.size() == 1) { + NewOptionsToMatch.push_back(EqualMatchers[0]); + continue; + } + + // Factor these checks by pulling the first node off each entry and + // discarding it. Take the first one off the first entry to reuse. + Matcher *Shared = Optn; + Optn = Optn->takeNext(); + EqualMatchers[0] = Optn; + + // Remove and delete the first node from the other matchers we're factoring. + for (unsigned i = 1, e = EqualMatchers.size(); i != e; ++i) { + Matcher *Tmp = EqualMatchers[i]->takeNext(); + delete EqualMatchers[i]; + EqualMatchers[i] = Tmp; + } + + Shared->setNext(new ScopeMatcher(&EqualMatchers[0], EqualMatchers.size())); + + // Recursively factor the newly created node. + FactorNodes(Shared->getNextPtr()); + + NewOptionsToMatch.push_back(Shared); + } + + // If we're down to a single pattern to match, then we don't need this scope + // anymore. + if (NewOptionsToMatch.size() == 1) { + MatcherPtr.reset(NewOptionsToMatch[0]); + return; + } + + if (NewOptionsToMatch.empty()) { + MatcherPtr.reset(0); + return; + } + + // If our factoring failed (didn't achieve anything) see if we can simplify in + // other ways. + + // Check to see if all of the leading entries are now opcode checks. If so, + // we can convert this Scope to be a OpcodeSwitch instead. + bool AllOpcodeChecks = true, AllTypeChecks = true; + for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { + if (!isa<CheckOpcodeMatcher>(NewOptionsToMatch[i])) { +#if 0 + if (i > 3 && AllOpcodeChecks) { + errs() << "FAILING OPC #" << i << "\n"; + NewOptionsToMatch[i]->dump(); + } +#endif + AllOpcodeChecks = false; + } + + if (!isa<CheckTypeMatcher>(NewOptionsToMatch[i]) || + // iPTR checks could alias any other case without us knowing, don't + // bother with them. + cast<CheckTypeMatcher>(NewOptionsToMatch[i])->getType() == MVT::iPTR) { +#if 0 + if (i > 3 && AllTypeChecks) { + errs() << "FAILING TYPE #" << i << "\n"; + NewOptionsToMatch[i]->dump(); + } +#endif + AllTypeChecks = false; + } + } + // TODO: Can also do CheckChildNType. + + // If all the options are CheckOpcode's, we can form the SwitchOpcode, woot. + if (AllOpcodeChecks) { + StringSet<> Opcodes; + SmallVector<std::pair<const SDNodeInfo*, Matcher*>, 8> Cases; + for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { + CheckOpcodeMatcher *COM = cast<CheckOpcodeMatcher>(NewOptionsToMatch[i]); + assert(Opcodes.insert(COM->getOpcode().getEnumName()) && + "Duplicate opcodes not factored?"); + Cases.push_back(std::make_pair(&COM->getOpcode(), COM->getNext())); + } + + MatcherPtr.reset(new SwitchOpcodeMatcher(&Cases[0], Cases.size())); + return; + } + + // If all the options are CheckType's, we can form the SwitchType, woot. + if (AllTypeChecks) { + DenseSet<unsigned> Types; + SmallVector<std::pair<MVT::SimpleValueType, Matcher*>, 8> Cases; + for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { + CheckTypeMatcher *CTM = cast<CheckTypeMatcher>(NewOptionsToMatch[i]); + assert(Types.insert(CTM->getType()).second && + "Duplicate types not factored?"); + Cases.push_back(std::make_pair(CTM->getType(), CTM->getNext())); + } + + MatcherPtr.reset(new SwitchTypeMatcher(&Cases[0], Cases.size())); + return; + } + + + // Reassemble the Scope node with the adjusted children. + Scope->setNumChildren(NewOptionsToMatch.size()); + for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) + Scope->resetChild(i, NewOptionsToMatch[i]); +} + +Matcher *llvm::OptimizeMatcher(Matcher *TheMatcher, + const CodeGenDAGPatterns &CGP) { + OwningPtr<Matcher> MatcherPtr(TheMatcher); + ContractNodes(MatcherPtr, CGP); + SinkPatternPredicates(MatcherPtr); + FactorNodes(MatcherPtr); + return MatcherPtr.take(); +} diff --git a/utils/TableGen/InstrEnumEmitter.cpp b/utils/TableGen/InstrEnumEmitter.cpp index f382d34..d1e7f3d 100644 --- a/utils/TableGen/InstrEnumEmitter.cpp +++ b/utils/TableGen/InstrEnumEmitter.cpp @@ -29,7 +29,7 @@ void InstrEnumEmitter::run(raw_ostream &OS) { std::string Namespace; for (CodeGenTarget::inst_iterator II = Target.inst_begin(), E = Target.inst_end(); II != E; ++II) { - if (II->second.Namespace != "TargetInstrInfo") { + if (II->second.Namespace != "TargetOpcode") { Namespace = II->second.Namespace; break; } diff --git a/utils/TableGen/LLVMCConfigurationEmitter.cpp b/utils/TableGen/LLVMCConfigurationEmitter.cpp index 2abc94b..db59053 100644 --- a/utils/TableGen/LLVMCConfigurationEmitter.cpp +++ b/utils/TableGen/LLVMCConfigurationEmitter.cpp @@ -43,6 +43,7 @@ const unsigned TabWidth = 4; const unsigned Indent1 = TabWidth*1; const unsigned Indent2 = TabWidth*2; const unsigned Indent3 = TabWidth*3; +const unsigned Indent4 = TabWidth*4; // Default help string. const char * const DefaultHelpString = "NO HELP MESSAGE PROVIDED"; @@ -229,7 +230,7 @@ namespace OptionDescriptionFlags { enum OptionDescriptionFlags { Required = 0x1, Hidden = 0x2, ReallyHidden = 0x4, Extern = 0x8, OneOrMore = 0x10, Optional = 0x20, - CommaSeparated = 0x40 }; + CommaSeparated = 0x40, ForwardNotSplit = 0x80 }; } /// OptionDescription - Represents data contained in a single @@ -271,6 +272,9 @@ struct OptionDescription { bool isExtern() const; void setExtern(); + bool isForwardNotSplit() const; + void setForwardNotSplit(); + bool isRequired() const; void setRequired(); @@ -327,6 +331,13 @@ void OptionDescription::setCommaSeparated() { Flags |= OptionDescriptionFlags::CommaSeparated; } +bool OptionDescription::isForwardNotSplit() const { + return Flags & OptionDescriptionFlags::ForwardNotSplit; +} +void OptionDescription::setForwardNotSplit() { + Flags |= OptionDescriptionFlags::ForwardNotSplit; +} + bool OptionDescription::isExtern() const { return Flags & OptionDescriptionFlags::Extern; } @@ -586,6 +597,8 @@ public: AddHandler("required", &CollectOptionProperties::onRequired); AddHandler("optional", &CollectOptionProperties::onOptional); AddHandler("comma_separated", &CollectOptionProperties::onCommaSeparated); + AddHandler("forward_not_split", + &CollectOptionProperties::onForwardNotSplit); staticMembersInitialized_ = true; } @@ -629,6 +642,13 @@ private: optDesc_.setCommaSeparated(); } + void onForwardNotSplit (const DagInit& d) { + CheckNumberOfArguments(d, 0); + if (!optDesc_.isParameter()) + throw "'forward_not_split' is valid only for parameter options!"; + optDesc_.setForwardNotSplit(); + } + void onRequired (const DagInit& d) { CheckNumberOfArguments(d, 0); if (optDesc_.isOneOrMore() || optDesc_.isOptional()) @@ -761,9 +781,12 @@ struct ToolDescription : public RefCountedBase<ToolDescription> { Init* CmdLine; Init* Actions; StrVector InLanguage; + std::string InFileOption; + std::string OutFileOption; std::string OutLanguage; std::string OutputSuffix; unsigned Flags; + const Init* OnEmpty; // Various boolean properties void setSink() { Flags |= ToolFlags::Sink; } @@ -773,9 +796,13 @@ struct ToolDescription : public RefCountedBase<ToolDescription> { // Default ctor here is needed because StringMap can only store // DefaultConstructible objects - ToolDescription() : CmdLine(0), Actions(0), Flags(0) {} + ToolDescription () + : CmdLine(0), Actions(0), OutFileOption("-o"), + Flags(0), OnEmpty(0) + {} ToolDescription (const std::string& n) - : Name(n), CmdLine(0), Actions(0), Flags(0) + : Name(n), CmdLine(0), Actions(0), OutFileOption("-o"), + Flags(0), OnEmpty(0) {} }; @@ -806,12 +833,17 @@ public: if (!staticMembersInitialized_) { AddHandler("actions", &CollectToolProperties::onActions); - AddHandler("cmd_line", &CollectToolProperties::onCmdLine); + AddHandler("command", &CollectToolProperties::onCommand); AddHandler("in_language", &CollectToolProperties::onInLanguage); AddHandler("join", &CollectToolProperties::onJoin); AddHandler("out_language", &CollectToolProperties::onOutLanguage); + + AddHandler("out_file_option", &CollectToolProperties::onOutFileOption); + AddHandler("in_file_option", &CollectToolProperties::onInFileOption); + AddHandler("output_suffix", &CollectToolProperties::onOutputSuffix); AddHandler("sink", &CollectToolProperties::onSink); + AddHandler("works_on_empty", &CollectToolProperties::onWorksOnEmpty); staticMembersInitialized_ = true; } @@ -836,7 +868,7 @@ private: toolDesc_.Actions = Case; } - void onCmdLine (const DagInit& d) { + void onCommand (const DagInit& d) { CheckNumberOfArguments(d, 1); toolDesc_.CmdLine = d.getArg(0); } @@ -878,6 +910,16 @@ private: toolDesc_.OutLanguage = InitPtrToString(d.getArg(0)); } + void onOutFileOption (const DagInit& d) { + CheckNumberOfArguments(d, 1); + toolDesc_.OutFileOption = InitPtrToString(d.getArg(0)); + } + + void onInFileOption (const DagInit& d) { + CheckNumberOfArguments(d, 1); + toolDesc_.InFileOption = InitPtrToString(d.getArg(0)); + } + void onOutputSuffix (const DagInit& d) { CheckNumberOfArguments(d, 1); toolDesc_.OutputSuffix = InitPtrToString(d.getArg(0)); @@ -888,6 +930,10 @@ private: toolDesc_.setSink(); } + void onWorksOnEmpty (const DagInit& d) { + toolDesc_.OnEmpty = d.getArg(0); + } + }; /// CollectToolDescriptions - Gather information about tool properties @@ -1490,7 +1536,7 @@ public: /// EmitCaseConstructHandler - Emit code that handles the 'case' /// construct. Takes a function object that should emit code for every case /// clause. Implemented on top of WalkCase. -/// Callback's type is void F(Init* Statement, unsigned IndentLevel, +/// Callback's type is void F(const Init* Statement, unsigned IndentLevel, /// raw_ostream& O). /// EmitElseIf parameter controls the type of condition that is emitted ('if /// (..) {..} else if (..) {} .. else {..}' vs. 'if (..) {..} if(..) {..} @@ -1699,82 +1745,41 @@ void EmitCmdLineVecFill(const Init* CmdLine, const std::string& ToolName, if (StrVec.empty()) throw "Tool '" + ToolName + "' has empty command line!"; - StrVector::const_iterator I = StrVec.begin(), E = StrVec.end(); + StrVector::const_iterator B = StrVec.begin(), E = StrVec.end(); - // If there is a hook invocation on the place of the first command, skip it. + // Emit the command itself. assert(!StrVec[0].empty()); + O.indent(IndentLevel) << "cmd = "; if (StrVec[0][0] == '$') { - while (I != E && (*I)[0] != ')' ) - ++I; - - // Skip the ')' symbol. - ++I; + B = SubstituteSpecialCommands(B, E, IsJoin, O); + ++B; } else { - ++I; + O << '"' << StrVec[0] << '"'; + ++B; } + O << ";\n"; - bool hasINFILE = false; + // Go through the command arguments. + assert(B <= E); + for (; B != E; ++B) { + const std::string& cmd = *B; - for (; I != E; ++I) { - const std::string& cmd = *I; assert(!cmd.empty()); O.indent(IndentLevel); + if (cmd.at(0) == '$') { - if (cmd == "$INFILE") { - hasINFILE = true; - if (IsJoin) { - O << "for (PathVector::const_iterator B = inFiles.begin()" - << ", E = inFiles.end();\n"; - O.indent(IndentLevel) << "B != E; ++B)\n"; - O.indent(IndentLevel + Indent1) << "vec.push_back(B->str());\n"; - } - else { - O << "vec.push_back(inFile.str());\n"; - } - } - else if (cmd == "$OUTFILE") { - O << "vec.push_back(\"\");\n"; - O.indent(IndentLevel) << "out_file_index = vec.size()-1;\n"; - } - else { - O << "vec.push_back("; - I = SubstituteSpecialCommands(I, E, IsJoin, O); - O << ");\n"; - } + O << "vec.push_back(std::make_pair(0, "; + B = SubstituteSpecialCommands(B, E, IsJoin, O); + O << "));\n"; } else { - O << "vec.push_back(\"" << cmd << "\");\n"; + O << "vec.push_back(std::make_pair(0, \"" << cmd << "\"));\n"; } } - if (!hasINFILE) - throw "Tool '" + ToolName + "' doesn't take any input!"; - O.indent(IndentLevel) << "cmd = "; - if (StrVec[0][0] == '$') - SubstituteSpecialCommands(StrVec.begin(), StrVec.end(), IsJoin, O); - else - O << '"' << StrVec[0] << '"'; - O << ";\n"; } -/// EmitCmdLineVecFillCallback - A function object wrapper around -/// EmitCmdLineVecFill(). Used by EmitGenerateActionMethod() as an -/// argument to EmitCaseConstructHandler(). -class EmitCmdLineVecFillCallback { - bool IsJoin; - const std::string& ToolName; - public: - EmitCmdLineVecFillCallback(bool J, const std::string& TN) - : IsJoin(J), ToolName(TN) {} - - void operator()(const Init* Statement, unsigned IndentLevel, - raw_ostream& O) const - { - EmitCmdLineVecFill(Statement, ToolName, IsJoin, IndentLevel, O); - } -}; - /// EmitForwardOptionPropertyHandlingCode - Helper function used to /// implement EmitActionHandler. Emits code for /// handling the (forward) and (forward_as) option properties. @@ -1789,15 +1794,30 @@ void EmitForwardOptionPropertyHandlingCode (const OptionDescription& D, switch (D.Type) { case OptionType::Switch: - O.indent(IndentLevel) << "vec.push_back(\"" << Name << "\");\n"; + O.indent(IndentLevel) + << "vec.push_back(std::make_pair(" << D.GenVariableName() + << ".getPosition(), \"" << Name << "\"));\n"; break; case OptionType::Parameter: - O.indent(IndentLevel) << "vec.push_back(\"" << Name << "\");\n"; - O.indent(IndentLevel) << "vec.push_back(" << D.GenVariableName() << ");\n"; + O.indent(IndentLevel) << "vec.push_back(std::make_pair(" + << D.GenVariableName() + <<".getPosition(), \"" << Name; + + if (!D.isForwardNotSplit()) { + O << "\"));\n"; + O.indent(IndentLevel) << "vec.push_back(std::make_pair(" + << D.GenVariableName() << ".getPosition(), " + << D.GenVariableName() << "));\n"; + } + else { + O << "=\" + " << D.GenVariableName() << "));\n"; + } break; case OptionType::Prefix: - O.indent(IndentLevel) << "vec.push_back(\"" << Name << "\" + " - << D.GenVariableName() << ");\n"; + O.indent(IndentLevel) << "vec.push_back(std::make_pair(" + << D.GenVariableName() << ".getPosition(), \"" + << Name << "\" + " + << D.GenVariableName() << "));\n"; break; case OptionType::PrefixList: O.indent(IndentLevel) @@ -1805,11 +1825,15 @@ void EmitForwardOptionPropertyHandlingCode (const OptionDescription& D, << "::iterator B = " << D.GenVariableName() << ".begin(),\n"; O.indent(IndentLevel) << "E = " << D.GenVariableName() << ".end(); B != E;) {\n"; - O.indent(IndentLevel1) << "vec.push_back(\"" << Name << "\" + " << "*B);\n"; + O.indent(IndentLevel1) << "unsigned pos = " << D.GenVariableName() + << ".getPosition(B - " << D.GenVariableName() + << ".begin());\n"; + O.indent(IndentLevel1) << "vec.push_back(std::make_pair(pos, \"" + << Name << "\" + " << "*B));\n"; O.indent(IndentLevel1) << "++B;\n"; for (int i = 1, j = D.MultiVal; i < j; ++i) { - O.indent(IndentLevel1) << "vec.push_back(*B);\n"; + O.indent(IndentLevel1) << "vec.push_back(std::make_pair(pos, *B));\n"; O.indent(IndentLevel1) << "++B;\n"; } @@ -1821,10 +1845,14 @@ void EmitForwardOptionPropertyHandlingCode (const OptionDescription& D, << D.GenVariableName() << ".begin(),\n"; O.indent(IndentLevel) << "E = " << D.GenVariableName() << ".end() ; B != E;) {\n"; - O.indent(IndentLevel1) << "vec.push_back(\"" << Name << "\");\n"; + O.indent(IndentLevel1) << "unsigned pos = " << D.GenVariableName() + << ".getPosition(B - " << D.GenVariableName() + << ".begin());\n"; + O.indent(IndentLevel1) << "vec.push_back(std::make_pair(pos, \"" + << Name << "\"));\n"; for (int i = 0, j = D.MultiVal; i < j; ++i) { - O.indent(IndentLevel1) << "vec.push_back(*B);\n"; + O.indent(IndentLevel1) << "vec.push_back(std::make_pair(pos, *B));\n"; O.indent(IndentLevel1) << "++B;\n"; } @@ -1906,7 +1934,8 @@ class EmitActionHandlersCallback : { CheckNumberOfArguments(Dag, 1); this->EmitHookInvocation(InitPtrToString(Dag.getArg(0)), - "vec.push_back(", ");\n", IndentLevel, O); + "vec.push_back(std::make_pair(65536, ", "));\n", + IndentLevel, O); } void onForward (const DagInit& Dag, @@ -1936,13 +1965,23 @@ class EmitActionHandlersCallback : const OptionDescription& D = OptDescs.FindListOrParameter(Name); if (D.isParameter()) { - O.indent(IndentLevel) << "vec.push_back(" - << D.GenVariableName() << ");\n"; + O.indent(IndentLevel) << "vec.push_back(std::make_pair(" + << D.GenVariableName() << ".getPosition(), " + << D.GenVariableName() << "));\n"; } else { - O.indent(IndentLevel) << "std::copy(" << D.GenVariableName() - << ".begin(), " << D.GenVariableName() - << ".end(), std::back_inserter(vec));\n"; + O.indent(IndentLevel) << "for (cl::list<std::string>::iterator B = " + << D.GenVariableName() << ".begin(), \n"; + O.indent(IndentLevel + Indent1) << " E = " << D.GenVariableName() + << ".end(); B != E; ++B)\n"; + O.indent(IndentLevel) << "{\n"; + O.indent(IndentLevel + Indent1) + << "unsigned pos = " << D.GenVariableName() + << ".getPosition(B - " << D.GenVariableName() + << ".begin());\n"; + O.indent(IndentLevel + Indent1) + << "vec.push_back(std::make_pair(pos, *B));\n"; + O.indent(IndentLevel) << "}\n"; } } @@ -1954,9 +1993,18 @@ class EmitActionHandlersCallback : const std::string& Hook = InitPtrToString(Dag.getArg(1)); const OptionDescription& D = OptDescs.FindListOrParameter(Name); - O.indent(IndentLevel) << "vec.push_back(" << "hooks::" - << Hook << "(" << D.GenVariableName() - << (D.isParameter() ? ".c_str()" : "") << "));\n"; + O.indent(IndentLevel) << "vec.push_back(std::make_pair(" + << D.GenVariableName() << ".getPosition(" + << (D.isList() ? "0" : "") << "), " + << "hooks::" << Hook << "(" << D.GenVariableName() + << (D.isParameter() ? ".c_str()" : "") << ")));\n"; + } + + void onNoOutFile (const DagInit& Dag, + unsigned IndentLevel, raw_ostream& O) const + { + CheckNumberOfArguments(Dag, 0); + O.indent(IndentLevel) << "no_out_file = true;\n"; } void onOutputSuffix (const DagInit& Dag, @@ -1995,12 +2043,15 @@ class EmitActionHandlersCallback : AddHandler("forward_value", &EmitActionHandlersCallback::onForwardValue); AddHandler("forward_transformed_value", &EmitActionHandlersCallback::onForwardTransformedValue); + AddHandler("no_out_file", + &EmitActionHandlersCallback::onNoOutFile); AddHandler("output_suffix", &EmitActionHandlersCallback::onOutputSuffix); AddHandler("stop_compilation", &EmitActionHandlersCallback::onStopCompilation); AddHandler("unpack_values", &EmitActionHandlersCallback::onUnpackValues); + staticMembersInitialized_ = true; } } @@ -2012,58 +2063,6 @@ class EmitActionHandlersCallback : } }; -bool IsOutFileIndexCheckRequiredStr (const Init* CmdLine) { - StrVector StrVec; - TokenizeCmdLine(InitPtrToString(CmdLine), StrVec); - - for (StrVector::const_iterator I = StrVec.begin(), E = StrVec.end(); - I != E; ++I) { - if (*I == "$OUTFILE") - return false; - } - - return true; -} - -class IsOutFileIndexCheckRequiredStrCallback { - bool* ret_; - -public: - IsOutFileIndexCheckRequiredStrCallback(bool* ret) : ret_(ret) - {} - - void operator()(const Init* CmdLine) { - // Ignore nested 'case' DAG. - if (typeid(*CmdLine) == typeid(DagInit)) - return; - - if (IsOutFileIndexCheckRequiredStr(CmdLine)) - *ret_ = true; - } - - void operator()(const DagInit* Test, unsigned, bool) { - this->operator()(Test); - } - void operator()(const Init* Statement, unsigned) { - this->operator()(Statement); - } -}; - -bool IsOutFileIndexCheckRequiredCase (Init* CmdLine) { - bool ret = false; - WalkCase(CmdLine, Id(), IsOutFileIndexCheckRequiredStrCallback(&ret)); - return ret; -} - -/// IsOutFileIndexCheckRequired - Should we emit an "out_file_index != -1" check -/// in EmitGenerateActionMethod() ? -bool IsOutFileIndexCheckRequired (Init* CmdLine) { - if (typeid(*CmdLine) == typeid(StringInit)) - return IsOutFileIndexCheckRequiredStr(CmdLine); - else - return IsOutFileIndexCheckRequiredCase(CmdLine); -} - void EmitGenerateActionMethodHeader(const ToolDescription& D, bool IsJoin, raw_ostream& O) { @@ -2078,8 +2077,10 @@ void EmitGenerateActionMethodHeader(const ToolDescription& D, O.indent(Indent2) << "const LanguageMap& LangMap) const\n"; O.indent(Indent1) << "{\n"; O.indent(Indent2) << "std::string cmd;\n"; - O.indent(Indent2) << "std::vector<std::string> vec;\n"; + O.indent(Indent2) << "std::string out_file;\n"; + O.indent(Indent2) << "std::vector<std::pair<unsigned, std::string> > vec;\n"; O.indent(Indent2) << "bool stop_compilation = !HasChildren;\n"; + O.indent(Indent2) << "bool no_out_file = false;\n"; O.indent(Indent2) << "const char* output_suffix = \"" << D.OutputSuffix << "\";\n"; } @@ -2095,46 +2096,67 @@ void EmitGenerateActionMethod (const ToolDescription& D, if (!D.CmdLine) throw "Tool " + D.Name + " has no cmd_line property!"; - bool IndexCheckRequired = IsOutFileIndexCheckRequired(D.CmdLine); - O.indent(Indent2) << "int out_file_index" - << (IndexCheckRequired ? " = -1" : "") - << ";\n\n"; - - // Process the cmd_line property. - if (typeid(*D.CmdLine) == typeid(StringInit)) - EmitCmdLineVecFill(D.CmdLine, D.Name, IsJoin, Indent2, O); - else - EmitCaseConstructHandler(D.CmdLine, Indent2, - EmitCmdLineVecFillCallback(IsJoin, D.Name), - true, OptDescs, O); + // Process the 'command' property. + O << '\n'; + EmitCmdLineVecFill(D.CmdLine, D.Name, IsJoin, Indent2, O); + O << '\n'; - // For every understood option, emit handling code. + // Process the 'actions' list of this tool. if (D.Actions) EmitCaseConstructHandler(D.Actions, Indent2, EmitActionHandlersCallback(OptDescs), false, OptDescs, O); - O << '\n'; - O.indent(Indent2) - << "std::string out_file = OutFilename(" - << (IsJoin ? "sys::Path(),\n" : "inFile,\n"); - O.indent(Indent3) << "TempDir, stop_compilation, output_suffix).str();\n\n"; - if (IndexCheckRequired) - O.indent(Indent2) << "if (out_file_index != -1)\n"; - O.indent(IndexCheckRequired ? Indent3 : Indent2) - << "vec[out_file_index] = out_file;\n"; + // Input file (s) + if (!D.InFileOption.empty()) { + O.indent(Indent2) + << "vec.push_back(std::make_pair(InputFilenames.getPosition(0), \"" + << D.InFileOption << "\");\n"; + } + + if (IsJoin) { + O.indent(Indent2) + << "for (PathVector::const_iterator B = inFiles.begin(),\n"; + O.indent(Indent3) << "E = inFiles.end(); B != E; ++B)\n"; + O.indent(Indent2) << "{\n"; + O.indent(Indent3) << "vec.push_back(std::make_pair(" + << "InputFilenames.getPosition(B - inFiles.begin()), " + << "B->str()));\n"; + O.indent(Indent2) << "}\n"; + } + else { + O.indent(Indent2) << "vec.push_back(std::make_pair(" + << "InputFilenames.getPosition(0), inFile.str()));\n"; + } + + // Output file + O.indent(Indent2) << "if (!no_out_file) {\n"; + if (!D.OutFileOption.empty()) + O.indent(Indent3) << "vec.push_back(std::make_pair(65536, \"" + << D.OutFileOption << "\"));\n"; + + O.indent(Indent3) << "out_file = this->OutFilename(" + << (IsJoin ? "sys::Path(),\n" : "inFile,\n"); + O.indent(Indent4) << "TempDir, stop_compilation, output_suffix).str();\n\n"; + O.indent(Indent3) << "vec.push_back(std::make_pair(65536, out_file));\n"; + + O.indent(Indent2) << "}\n\n"; // Handle the Sink property. if (D.isSink()) { O.indent(Indent2) << "if (!" << SinkOptionName << ".empty()) {\n"; - O.indent(Indent3) << "vec.insert(vec.end(), " - << SinkOptionName << ".begin(), " << SinkOptionName - << ".end());\n"; + O.indent(Indent3) << "for (cl::list<std::string>::iterator B = " + << SinkOptionName << ".begin(), E = " << SinkOptionName + << ".end(); B != E; ++B)\n"; + O.indent(Indent4) << "vec.push_back(std::make_pair(" << SinkOptionName + << ".getPosition(B - " << SinkOptionName + << ".begin()), *B));\n"; O.indent(Indent2) << "}\n"; } - O.indent(Indent2) << "return Action(cmd, vec, stop_compilation, out_file);\n"; + O.indent(Indent2) << "return Action(cmd, this->SortArgs(vec), " + << "stop_compilation, out_file);\n"; O.indent(Indent1) << "}\n\n"; } @@ -2194,6 +2216,29 @@ void EmitIsJoinMethod (const ToolDescription& D, raw_ostream& O) { O.indent(Indent1) << "}\n\n"; } +/// EmitWorksOnEmptyCallback - Callback used by EmitWorksOnEmptyMethod in +/// conjunction with EmitCaseConstructHandler. +void EmitWorksOnEmptyCallback (const Init* Value, + unsigned IndentLevel, raw_ostream& O) { + CheckBooleanConstant(Value); + O.indent(IndentLevel) << "return " << Value->getAsString() << ";\n"; +} + +/// EmitWorksOnEmptyMethod - Emit the WorksOnEmpty() method for a given Tool +/// class. +void EmitWorksOnEmptyMethod (const ToolDescription& D, + const OptionDescriptions& OptDescs, + raw_ostream& O) +{ + O.indent(Indent1) << "bool WorksOnEmpty() const {\n"; + if (D.OnEmpty == 0) + O.indent(Indent2) << "return false;\n"; + else + EmitCaseConstructHandler(D.OnEmpty, Indent2, EmitWorksOnEmptyCallback, + /*EmitElseIf = */ true, OptDescs, O); + O.indent(Indent1) << "}\n\n"; +} + /// EmitStaticMemberDefinitions - Emit static member definitions for a /// given Tool class. void EmitStaticMemberDefinitions(const ToolDescription& D, raw_ostream& O) { @@ -2228,6 +2273,7 @@ void EmitToolClassDefinition (const ToolDescription& D, EmitNameMethod(D, O); EmitInOutLanguageMethods(D, O); EmitIsJoinMethod(D, O); + EmitWorksOnEmptyMethod(D, OptDescs, O); EmitGenerateActionMethods(D, OptDescs, O); // Close class definition @@ -2981,7 +3027,7 @@ void LLVMCConfigurationEmitter::run (raw_ostream &O) { CollectPluginData(Records, Data); CheckPluginData(Data); - EmitSourceFileHeader("LLVMC Configuration Library", O); + this->EmitSourceFileHeader("LLVMC Configuration Library", O); EmitPluginCode(Data, O); } catch (std::exception& Error) { diff --git a/utils/TableGen/Record.h b/utils/TableGen/Record.h index 45f3072..90096e9 100644 --- a/utils/TableGen/Record.h +++ b/utils/TableGen/Record.h @@ -1225,6 +1225,10 @@ public: ID(LastID++), Name(N), Loc(loc) {} ~Record() {} + + static unsigned getNewUID() { return LastID++; } + + unsigned getID() const { return ID; } const std::string &getName() const { return Name; } diff --git a/utils/TableGen/X86RecognizableInstr.cpp b/utils/TableGen/X86RecognizableInstr.cpp index 3843e56..ea78d41 100644 --- a/utils/TableGen/X86RecognizableInstr.cpp +++ b/utils/TableGen/X86RecognizableInstr.cpp @@ -282,6 +282,10 @@ RecognizableInstr::filter_ret RecognizableInstr::filter() const { IsCodeGenOnly) return FILTER_STRONG; + if (Form == X86Local::MRMInitReg) + return FILTER_STRONG; + + // Filter out instructions with a LOCK prefix; // prefer forms that do not have the prefix if (HasLockPrefix) @@ -353,9 +357,6 @@ RecognizableInstr::filter_ret RecognizableInstr::filter() const { if (AsmString.find("subreg") != AsmString.npos) return FILTER_STRONG; - assert(Form != X86Local::MRMInitReg && - "FORMAT_MRMINITREG instruction not skipped"); - if (HasFROperands && Name.find("MOV") != Name.npos && ((Name.find("2") != Name.npos && Name.find("32") == Name.npos) || (Name.find("to") != Name.npos))) diff --git a/utils/buildit/GNUmakefile b/utils/buildit/GNUmakefile index 57aac43..8d8504c 100644 --- a/utils/buildit/GNUmakefile +++ b/utils/buildit/GNUmakefile @@ -34,9 +34,9 @@ DSTROOT = $(OBJROOT)/../dst PREFIX = /usr/local -# Unless assertions are forced on in the GMAKE command line, enable them. +# Unless assertions are forced on in the GMAKE command line, disable them. ifndef ENABLE_ASSERTIONS -ENABLE_ASSERTIONS := yes +ENABLE_ASSERTIONS := no endif # Default is optimized build. diff --git a/utils/git/find-rev b/utils/git/find-rev new file mode 100755 index 0000000..a6161db --- /dev/null +++ b/utils/git/find-rev @@ -0,0 +1,50 @@ +#!/usr/bin/python + +import os, sys, subprocess + +def main(): + from optparse import OptionParser, OptionGroup + parser = OptionParser("usage: %prog [options] <repo> <revision>") + parser.add_option("", "--dump-section-data", dest="dumpSectionData", + help="Dump the contents of sections", + action="store_true", default=False) + (opts, args) = parser.parse_args() + + if len(args) != 2: + parser.error("invalid number of arguments") + + repo,rev = args + + try: + rev = int(rev) + except: + parser.error("invalid revision argument (not an integer)") + + os.chdir(repo) + p = subprocess.Popen(['git', 'rev-list', 'git-svn', '--pretty'], + stdout=subprocess.PIPE) + + bestRev = bestCommit = None + lastCommit = None + for ln in p.stdout: + if ln.startswith('commit '): + lastCommit = ln.split(' ',2)[1] + elif ln.startswith(' git-svn-id: '): + _,repo,_ = ln.strip().split(' ') + _,lrev = repo.rsplit('@',1) + lrev = int(lrev) + if lrev<=rev: + if bestRev is None or lrev>bestRev: + assert lastCommit + bestCommit = lastCommit + bestRev = lrev + if lrev == rev: + break + + if bestCommit is not None: + print bestCommit + sys.exit(0) + sys.exit(1) + +if __name__=='__main__': + main() diff --git a/utils/lit/lit/ExampleTests/LLVM.InTree/test/site.exp b/utils/lit/lit/ExampleTests/LLVM.InTree/test/site.exp index 1d9c743..efa839e 100644 --- a/utils/lit/lit/ExampleTests/LLVM.InTree/test/site.exp +++ b/utils/lit/lit/ExampleTests/LLVM.InTree/test/site.exp @@ -4,7 +4,6 @@ set target_triplet "x86_64-apple-darwin10" set TARGETS_TO_BUILD "X86 Sparc PowerPC Alpha ARM Mips CellSPU PIC16 XCore MSP430 SystemZ Blackfin CBackend MSIL CppBackend" set llvmgcc_langs "c,c++,objc,obj-c++" -set llvmgcc_version "4.2.1" set prcontext "/usr/bin/tclsh8.4 /Volumes/Data/ddunbar/llvm/test/Scripts/prcontext.tcl" set llvmtoolsdir "/Users/ddunbar/llvm.obj.64/Debug/bin" set llvmlibsdir "/Users/ddunbar/llvm.obj.64/Debug/lib" @@ -19,7 +18,6 @@ set compile_cxx " /usr/bin/g++ -arch x86_64 -I/Users/ddunbar/llvm.obj.64/include set link " /usr/bin/g++ -arch x86_64 -I/Users/ddunbar/llvm.obj.64/include -I/Users/ddunbar/llvm.obj.64/test -I/Volumes/Data/ddunbar/llvm.obj.64/include -I/Volumes/Data/ddunbar/llvm/include -I/Volumes/Data/ddunbar/llvm/test -D_DEBUG -D_GNU_SOURCE -D__STDC_LIMIT_MACROS -D__STDC_CONSTANT_MACROS -g -fno-exceptions -fno-common -Woverloaded-virtual -m64 -pedantic -Wno-long-long -Wall -W -Wno-unused-parameter -Wwrite-strings -g -L/Users/ddunbar/llvm.obj.64/Debug/lib -L/Volumes/Data/ddunbar/llvm.obj.64/Debug/lib " set llvmgcc "/Users/ddunbar/llvm-gcc/install/bin/llvm-gcc -m64 " set llvmgxx "/Users/ddunbar/llvm-gcc/install/bin/llvm-gcc -m64 " -set llvmgccmajvers "4" set bugpoint_topts "-gcc-tool-args -m64" set shlibext ".dylib" set ocamlopt "/sw/bin/ocamlopt -cc \"g++ -Wall -D_FILE_OFFSET_BITS=64 -D_REENTRANT\" -I /Users/ddunbar/llvm.obj.64/Debug/lib/ocaml" diff --git a/utils/lit/lit/ExampleTests/LLVM.OutOfTree/obj/test/site.exp b/utils/lit/lit/ExampleTests/LLVM.OutOfTree/obj/test/site.exp index 1d9c743..efa839e 100644 --- a/utils/lit/lit/ExampleTests/LLVM.OutOfTree/obj/test/site.exp +++ b/utils/lit/lit/ExampleTests/LLVM.OutOfTree/obj/test/site.exp @@ -4,7 +4,6 @@ set target_triplet "x86_64-apple-darwin10" set TARGETS_TO_BUILD "X86 Sparc PowerPC Alpha ARM Mips CellSPU PIC16 XCore MSP430 SystemZ Blackfin CBackend MSIL CppBackend" set llvmgcc_langs "c,c++,objc,obj-c++" -set llvmgcc_version "4.2.1" set prcontext "/usr/bin/tclsh8.4 /Volumes/Data/ddunbar/llvm/test/Scripts/prcontext.tcl" set llvmtoolsdir "/Users/ddunbar/llvm.obj.64/Debug/bin" set llvmlibsdir "/Users/ddunbar/llvm.obj.64/Debug/lib" @@ -19,7 +18,6 @@ set compile_cxx " /usr/bin/g++ -arch x86_64 -I/Users/ddunbar/llvm.obj.64/include set link " /usr/bin/g++ -arch x86_64 -I/Users/ddunbar/llvm.obj.64/include -I/Users/ddunbar/llvm.obj.64/test -I/Volumes/Data/ddunbar/llvm.obj.64/include -I/Volumes/Data/ddunbar/llvm/include -I/Volumes/Data/ddunbar/llvm/test -D_DEBUG -D_GNU_SOURCE -D__STDC_LIMIT_MACROS -D__STDC_CONSTANT_MACROS -g -fno-exceptions -fno-common -Woverloaded-virtual -m64 -pedantic -Wno-long-long -Wall -W -Wno-unused-parameter -Wwrite-strings -g -L/Users/ddunbar/llvm.obj.64/Debug/lib -L/Volumes/Data/ddunbar/llvm.obj.64/Debug/lib " set llvmgcc "/Users/ddunbar/llvm-gcc/install/bin/llvm-gcc -m64 " set llvmgxx "/Users/ddunbar/llvm-gcc/install/bin/llvm-gcc -m64 " -set llvmgccmajvers "4" set bugpoint_topts "-gcc-tool-args -m64" set shlibext ".dylib" set ocamlopt "/sw/bin/ocamlopt -cc \"g++ -Wall -D_FILE_OFFSET_BITS=64 -D_REENTRANT\" -I /Users/ddunbar/llvm.obj.64/Debug/lib/ocaml" diff --git a/utils/llvm.grm b/utils/llvm.grm index 86a707a..d391e2a 100644 --- a/utils/llvm.grm +++ b/utils/llvm.grm @@ -162,6 +162,7 @@ FuncAttr ::= noreturn | readnone | readonly | inlinehint + | alignstack | noinline | alwaysinline | optsize diff --git a/utils/vim/llvm.vim b/utils/vim/llvm.vim index 6e4a207..518aa04 100644 --- a/utils/vim/llvm.vim +++ b/utils/vim/llvm.vim @@ -1,7 +1,7 @@ " Vim syntax file " Language: llvm " Maintainer: The LLVM team, http://llvm.org/ -" Updated: 2003-06-02 +" Version: $Revision: 97271 $ if version < 600 syntax clear @@ -52,11 +52,12 @@ syn keyword llvmKeyword x86_stdcallcc x86_fastcallcc syn keyword llvmKeyword signext zeroext inreg sret nounwind noreturn syn keyword llvmKeyword nocapture byval nest readnone readonly noalias syn keyword llvmKeyword inlinehint noinline alwaysinline optsize ssp sspreq -syn keyword llvmKeyword noredzone noimplicitfloat naked +syn keyword llvmKeyword noredzone noimplicitfloat naked alignstack syn keyword llvmKeyword module asm align tail to syn keyword llvmKeyword addrspace section alias sideeffect c gc syn keyword llvmKeyword target datalayout triple syn keyword llvmKeyword blockaddress +syn keyword llvmKeyword union " Obsolete keywords. syn keyword llvmError uninitialized implementation diff --git a/utils/vim/tablegen.vim b/utils/vim/tablegen.vim index ad35872..11a4d80 100644 --- a/utils/vim/tablegen.vim +++ b/utils/vim/tablegen.vim @@ -1,7 +1,7 @@ " Vim syntax file " Language: TableGen " Maintainer: The LLVM team, http://llvm.org/ -" Updated: 2003-08-11 +" Version: $Revision: 97271 $ if version < 600 syntax clear diff --git a/utils/vim/vimrc b/utils/vim/vimrc index 4909f60..63108f2 100644 --- a/utils/vim/vimrc +++ b/utils/vim/vimrc @@ -1,4 +1,5 @@ " LLVM coding guidelines conformance for VIM +" $Revision: 97273 $ " " Maintainer: The LLVM Team, http://llvm.org " WARNING: Read before you source in all these commands and macros! Some @@ -10,17 +11,30 @@ " It's VIM, not VI set nocompatible -" Wrap text at 80 cols -set textwidth=80 - " A tab produces a 2-space indentation set softtabstop=2 set shiftwidth=2 set expandtab -" Highlight trailing whitespace +" Highlight trailing whitespace and lines longer than 80 columns. +highlight LongLine ctermbg=DarkYellow guibg=DarkYellow highlight WhitespaceEOL ctermbg=DarkYellow guibg=DarkYellow -match WhitespaceEOL /\s\+$/ +if v:version >= 702 + " Lines longer than 80 columns. + au BufWinEnter * let w:m0=matchadd('LongLine', '\%>80v.\+', -1) + + " Whitespace at the end of a line. This little dance suppresses + " whitespace that has just been typed. + au BufWinEnter * let w:m1=matchadd('WhitespaceEOL', '\s\+$', -1) + au InsertEnter * call matchdelete(w:m1) + au InsertEnter * let w:m2=matchadd('WhitespaceEOL', '\s\+\%#\@<!$', -1) + au InsertLeave * call matchdelete(w:m2) + au InsertLeave * let w:m1=matchadd('WhitespaceEOL', '\s\+$', -1) +else + au BufRead,BufNewFile * syntax match LongLine /\%>80v.\+/ + au InsertEnter * syntax match WhitespaceEOL /\s\+\%#\@<!$/ + au InsertLeave * syntax match WhitespaceEOL /\s\+$/ +endif " Enable filetype detection filetype on @@ -70,3 +84,10 @@ augroup END augroup filetype au! BufRead,BufNewFile *.td set filetype=tablegen augroup END + +" Additional vim features to optionally uncomment. +"set showcmd +"set showmatch +"set showmode +"set incsearch +"set ruler |
