From 955c1be529728a27ff952eb5f6d7ab9e5d6b5f86 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Fri, 8 Aug 2003 22:29:23 +0000 Subject: [PATCH] This implements a large amount of the matcher, in fact, all of it except for one bug git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7702 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../tools/TableGen/InstrSelectorEmitter.cpp | 397 ++++++++++++++++-- support/tools/TableGen/InstrSelectorEmitter.h | 31 +- utils/TableGen/InstrSelectorEmitter.cpp | 397 ++++++++++++++++-- utils/TableGen/InstrSelectorEmitter.h | 31 +- 4 files changed, 758 insertions(+), 98 deletions(-) diff --git a/support/tools/TableGen/InstrSelectorEmitter.cpp b/support/tools/TableGen/InstrSelectorEmitter.cpp index b9475360376..a2de8c122b4 100644 --- a/support/tools/TableGen/InstrSelectorEmitter.cpp +++ b/support/tools/TableGen/InstrSelectorEmitter.cpp @@ -9,6 +9,8 @@ #include "CodeGenWrappers.h" #include "Record.h" #include "Support/Debug.h" +#include "Support/StringExtras.h" +#include NodeType::ArgResultTypes NodeType::Translate(Record *R) { const std::string &Name = R->getName(); @@ -24,6 +26,15 @@ NodeType::ArgResultTypes NodeType::Translate(Record *R) { // TreePatternNode implementation // +/// getValueRecord - Returns the value of this tree node as a record. For now +/// we only allow DefInit's as our leaf values, so this is used. +Record *TreePatternNode::getValueRecord() const { + DefInit *DI = dynamic_cast(getValue()); + assert(DI && "Instruction Selector does not yet support non-def leaves!"); + return DI->getDef(); +} + + // updateNodeType - Set the node type of N to VT if VT contains information. If // N already contains a conflicting type, then throw an exception // @@ -50,17 +61,17 @@ void TreePatternNode::InstantiateNonterminals(InstrSelectorEmitter &ISE) { } // If this is a leaf, it might be a reference to a nonterminal! Check now. - if (DefInit *DI = dynamic_cast(getValue())) - if (DI->getDef()->isSubClassOf("Nonterminal")) { - Pattern *NT = ISE.getPattern(DI->getDef()); - if (!NT->isResolved()) { - // We found an unresolved nonterminal reference. Ask the ISE to clone - // it for us, then update our reference to the fresh, new, resolved, - // nonterminal. - - Value = new DefInit(ISE.InstantiateNonterminal(NT, getType())); - } + Record *R = getValueRecord(); + if (R->isSubClassOf("Nonterminal")) { + Pattern *NT = ISE.getPattern(R); + if (!NT->isResolved()) { + // We found an unresolved nonterminal reference. Ask the ISE to clone + // it for us, then update our reference to the fresh, new, resolved, + // nonterminal. + + Value = new DefInit(ISE.InstantiateNonterminal(NT, getType())); } + } } @@ -80,7 +91,6 @@ TreePatternNode *TreePatternNode::clone() const { return New; } - std::ostream &operator<<(std::ostream &OS, const TreePatternNode &N) { if (N.isLeaf()) return OS << N.getType() << ":" << *N.getValue(); @@ -126,11 +136,7 @@ Pattern::Pattern(PatternType pty, DagInit *RawPat, Record *TheRec, assert(Tree->getChildren().size() == 2 && "Set with != 2 arguments?"); if (!Tree->getChild(0)->isLeaf()) error("Arg #0 of set should be a register or register class!"); - DefInit *RegInit = dynamic_cast(Tree->getChild(0)->getValue()); - if (RegInit == 0) - error("LHS of 'set' expected to be a register or register class!"); - - Result = RegInit->getDef(); + Result = Tree->getChild(0)->getValueRecord(); Tree = Tree->getChild(1); } } @@ -232,8 +238,7 @@ bool Pattern::InferTypes(TreePatternNode *N, bool &MadeChange) { bool AnyUnset = false; Record *Operator = N->getOperator(); - assert(ISE.getNodeTypes().count(Operator) && "No node info for node!"); - const NodeType &NT = ISE.getNodeTypes()[Operator]; + const NodeType &NT = ISE.getNodeType(Operator); // Check to see if we can infer anything about the argument types from the // return types... @@ -317,6 +322,38 @@ std::ostream &operator<<(std::ostream &OS, const Pattern &P) { } +/// getSlotName - If this is a leaf node, return the slot name that the operand +/// will update. +std::string Pattern::getSlotName() const { + if (getPatternType() == Pattern::Nonterminal) { + // Just use the nonterminal name, which will already include the type if + // it has been cloned. + return getRecord()->getName(); + } else { + std::string SlotName; + if (getResult()) + SlotName = getResult()->getName()+"_"; + else + SlotName = "Void_"; + return SlotName + getName(getTree()->getType()); + } +} + +/// getSlotName - If this is a leaf node, return the slot name that the +/// operand will update. +std::string Pattern::getSlotName(Record *R) { + if (R->isSubClassOf("Nonterminal")) { + // Just use the nonterminal name, which will already include the type if + // it has been cloned. + return R->getName(); + } else if (R->isSubClassOf("RegisterClass")) { + MVT::ValueType Ty = getValueType(R->getValueAsDef("RegType")); + return R->getName() + "_" + getName(Ty); + } else { + assert(0 && "Don't know how to get a slot name for this!"); + } +} + //===----------------------------------------------------------------------===// // PatternOrganizer implementation // @@ -324,29 +361,12 @@ std::ostream &operator<<(std::ostream &OS, const Pattern &P) { /// addPattern - Add the specified pattern to the appropriate location in the /// collection. void PatternOrganizer::addPattern(Pattern *P) { - std::string ValueName; - if (P->getPatternType() == Pattern::Nonterminal) { - // Just use the nonterminal name, which will already include the type if - // it has been cloned. - ValueName = P->getRecord()->getName(); - } else { - if (P->getResult()) - ValueName += P->getResult()->getName()+"_"; - else - ValueName += "Void_"; - ValueName += getName(P->getTree()->getType()); - } - - NodesForSlot &Nodes = AllPatterns[ValueName]; + NodesForSlot &Nodes = AllPatterns[P->getSlotName()]; if (!P->getTree()->isLeaf()) Nodes[P->getTree()->getOperator()].push_back(P); else { // Right now we only support DefInit's with node types... - DefInit *Val = dynamic_cast(P->getTree()->getValue()); - if (!Val) - throw std::string("We only support def inits in PatternOrganizer" - "::addPattern so far!"); - Nodes[Val->getDef()].push_back(P); + Nodes[P->getTree()->getValueRecord()].push_back(P); } } @@ -469,6 +489,11 @@ Record *InstrSelectorEmitter::InstantiateNonterminal(Pattern *NT, Record *New = new Record(NT->getRecord()->getName()+"_"+getName(ResultTy)); + // Copy over the superclasses... + const std::vector &SCs = NT->getRecord()->getSuperClasses(); + for (unsigned i = 0, e = SCs.size(); i != e; ++i) + New->addSuperClass(SCs[i]); + DEBUG(std::cerr << " Nonterminal '" << NT->getRecord()->getName() << "' for type '" << getName(ResultTy) << "', producing '" << New->getName() << "'\n"); @@ -503,6 +528,242 @@ void InstrSelectorEmitter::CalculateComputableValues() { ComputableValues.addPattern(I->second); } +#if 0 +// MoveIdenticalPatterns - Given a tree pattern 'P', move all of the tree +// patterns which have the same top-level structure as P from the 'From' list to +// the 'To' list. +static void MoveIdenticalPatterns(TreePatternNode *P, + std::vector > &From, + std::vector > &To) { + assert(!P->isLeaf() && "All leaves are identical!"); + + const std::vector &PChildren = P->getChildren(); + for (unsigned i = 0; i != From.size(); ++i) { + TreePatternNode *N = From[i].second; + assert(P->getOperator() == N->getOperator() &&"Differing operators?"); + assert(PChildren.size() == N->getChildren().size() && + "Nodes with different arity??"); + bool isDifferent = false; + for (unsigned c = 0, e = PChildren.size(); c != e; ++c) { + TreePatternNode *PC = PChildren[c]; + TreePatternNode *NC = N->getChild(c); + if (PC->isLeaf() != NC->isLeaf()) { + isDifferent = true; + break; + } + + if (!PC->isLeaf()) { + if (PC->getOperator() != NC->getOperator()) { + isDifferent = true; + break; + } + } else { // It's a leaf! + if (PC->getValueRecord() != NC->getValueRecord()) { + isDifferent = true; + break; + } + } + } + // If it's the same as the reference one, move it over now... + if (!isDifferent) { + To.push_back(std::make_pair(From[i].first, N)); + From.erase(From.begin()+i); + --i; // Don't skip an entry... + } + } +} +#endif + +static void EmitPatternPredicates(TreePatternNode *Tree, + const std::string &VarName, std::ostream &OS){ + OS << " && " << VarName << "->getNodeType() == ISD::" + << Tree->getOperator()->getName(); + + for (unsigned c = 0, e = Tree->getNumChildren(); c != e; ++c) + if (!Tree->getChild(c)->isLeaf()) + EmitPatternPredicates(Tree->getChild(c), + VarName + "->getUse(" + utostr(c)+")", OS); +} + +static void EmitPatternCosts(TreePatternNode *Tree, const std::string &VarName, + std::ostream &OS) { + for (unsigned c = 0, e = Tree->getNumChildren(); c != e; ++c) + if (Tree->getChild(c)->isLeaf()) { + OS << " + Match_" + << Pattern::getSlotName(Tree->getChild(c)->getValueRecord()) << "(" + << VarName << "->getUse(" << c << "))"; + } else { + EmitPatternCosts(Tree->getChild(c), + VarName + "->getUse(" + utostr(c) + ")", OS); + } +} + + +// EmitMatchCosters - Given a list of patterns, which all have the same root +// pattern operator, emit an efficient decision tree to decide which one to +// pick. This is structured this way to avoid reevaluations of non-obvious +// subexpressions. +void InstrSelectorEmitter::EmitMatchCosters(std::ostream &OS, + const std::vector > &Patterns, + const std::string &VarPrefix, + unsigned IndentAmt) { + assert(!Patterns.empty() && "No patterns to emit matchers for!"); + std::string Indent(IndentAmt, ' '); + + // Load all of the operands of the root node into scalars for fast access + const NodeType &ONT = getNodeType(Patterns[0].second->getOperator()); + for (unsigned i = 0, e = ONT.ArgTypes.size(); i != e; ++i) + OS << Indent << "SelectionDAGNode *" << VarPrefix << "_Op" << i + << " = N->getUse(" << i << ");\n"; + + // Compute the costs of computing the various nonterminals/registers, which + // are directly used at this level. + OS << "\n" << Indent << "// Operand matching costs...\n"; + std::set ComputedValues; // Avoid duplicate computations... + for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { + const std::vector &Children = + Patterns[i].second->getChildren(); + for (unsigned c = 0, e = Children.size(); c != e; ++c) { + TreePatternNode *N = Children[c]; + if (N->isLeaf()) { + Record *VR = N->getValueRecord(); + const std::string &LeafName = VR->getName(); + std::string OpName = VarPrefix + "_Op" + utostr(c); + std::string ValName = OpName + "_" + LeafName + "_Cost"; + if (!ComputedValues.count(ValName)) { + OS << Indent << "unsigned " << ValName << " = Match_" + << Pattern::getSlotName(VR) << "(" << OpName << ");\n"; + ComputedValues.insert(ValName); + } + } + } + } + OS << "\n"; + + + std::string LocCostName = VarPrefix + "_Cost"; + OS << Indent << "unsigned " << LocCostName << "Min = ~0U >> 1;\n" + << Indent << "unsigned " << VarPrefix << "_PatternMin = NoMatch;\n"; + +#if 0 + // Separate out all of the patterns into groups based on what their top-level + // signature looks like... + std::vector > PatternsLeft(Patterns); + while (!PatternsLeft.empty()) { + // Process all of the patterns that have the same signature as the last + // element... + std::vector > Group; + MoveIdenticalPatterns(PatternsLeft.back().second, PatternsLeft, Group); + assert(!Group.empty() && "Didn't at least pick the source pattern?"); + +#if 0 + OS << "PROCESSING GROUP:\n"; + for (unsigned i = 0, e = Group.size(); i != e; ++i) + OS << " " << *Group[i].first << "\n"; + OS << "\n\n"; +#endif + + OS << Indent << "{ // "; + + if (Group.size() != 1) { + OS << Group.size() << " size group...\n"; + OS << Indent << " unsigned " << VarPrefix << "_Pattern = NoMatch;\n"; + } else { + OS << *Group[0].first << "\n"; + OS << Indent << " unsigned " << VarPrefix << "_Pattern = " + << Group[0].first->getRecord()->getName() << "_Pattern;\n"; + } + + OS << Indent << " unsigned " << LocCostName << " = "; + if (Group.size() == 1) + OS << "1;\n"; // Add inst cost if at individual rec + else + OS << "0;\n"; + + // Loop over all of the operands, adding in their costs... + TreePatternNode *N = Group[0].second; + const std::vector &Children = N->getChildren(); + + // If necessary, emit conditionals to check for the appropriate tree + // structure here... + for (unsigned i = 0, e = Children.size(); i != e; ++i) { + TreePatternNode *C = Children[i]; + if (C->isLeaf()) { + // We already calculated the cost for this leaf, add it in now... + OS << Indent << " " << LocCostName << " += " + << VarPrefix << "_Op" << utostr(i) << "_" + << C->getValueRecord()->getName() << "_Cost;\n"; + } else { + // If it's not a leaf, we have to check to make sure that the current + // node has the appropriate structure, then recurse into it... + OS << Indent << " if (" << VarPrefix << "_Op" << i + << "->getNodeType() == ISD::" << C->getOperator()->getName() + << ") {\n"; + std::vector > SubPatterns; + for (unsigned n = 0, e = Group.size(); n != e; ++n) + SubPatterns.push_back(std::make_pair(Group[n].first, + Group[n].second->getChild(i))); + EmitMatchCosters(OS, SubPatterns, VarPrefix+"_Op"+utostr(i), + IndentAmt + 4); + OS << Indent << " }\n"; + } + } + + // If the cost for this match is less than the minimum computed cost so far, + // update the minimum cost and selected pattern. + OS << Indent << " if (" << LocCostName << " < " << LocCostName << "Min) { " + << LocCostName << "Min = " << LocCostName << "; " << VarPrefix + << "_PatternMin = " << VarPrefix << "_Pattern; }\n"; + + OS << Indent << "}\n"; + } +#endif + + for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { + Pattern *P = Patterns[i].first; + TreePatternNode *PTree = P->getTree(); + unsigned PatternCost = 1; + + // Check to see if there are any non-leaf elements in the pattern. If so, + // we need to emit a predicate for this match. + bool AnyNonLeaf = false; + for (unsigned c = 0, e = PTree->getNumChildren(); c != e; ++c) + if (!PTree->getChild(c)->isLeaf()) { + AnyNonLeaf = true; + break; + } + + if (!AnyNonLeaf) { // No predicate necessary, just output a scope... + OS << " {// " << *P << "\n"; + } else { + // We need to emit a predicate to make sure the tree pattern matches, do + // so now... + OS << " if (1"; + for (unsigned c = 0, e = PTree->getNumChildren(); c != e; ++c) + if (!PTree->getChild(c)->isLeaf()) + EmitPatternPredicates(PTree->getChild(c), + VarPrefix + "_Op" + utostr(c), OS); + + OS << ") {\n // " << *P << "\n"; + } + + OS << " unsigned PatCost = " << PatternCost; + + for (unsigned c = 0, e = PTree->getNumChildren(); c != e; ++c) + if (PTree->getChild(c)->isLeaf()) { + OS << " + " << VarPrefix << "_Op" << c << "_" + << PTree->getChild(c)->getValueRecord()->getName() << "_Cost"; + } else { + EmitPatternCosts(PTree->getChild(c), VarPrefix + "_Op" + utostr(c), OS); + } + OS << ";\n"; + OS << " if (PatCost < MinCost) { MinCost = PatCost; Pattern = " + << P->getRecord()->getName() << "_Pattern; }\n" + << " }\n"; + } +} + + void InstrSelectorEmitter::run(std::ostream &OS) { // Type-check all of the node types to ensure we "understand" them. ReadNodeTypes(); @@ -570,30 +831,30 @@ void InstrSelectorEmitter::run(std::ostream &OS) { << " }\n\n" << " // DAG matching methods for classes... all of these methods" " return the cost\n" - <<" // of producing a value of the specified class and type, which" + << " // of producing a value of the specified class and type, which" " also gets\n" << " // added to the DAG node.\n"; // Output all of the matching prototypes for slots... for (PatternOrganizer::iterator I = ComputableValues.begin(), E = ComputableValues.end(); I != E; ++I) - OS << " unsigned Match_" << I->first << "(SelectionDAGNode *N);\n"; - OS << "\n // DAG matching methods for DAG nodes...\n"; + OS << " unsigned Match_" << I->first << "(SelectionDAGNode *N);\n"; + OS << "\n // DAG matching methods for DAG nodes...\n"; // Output all of the matching prototypes for slot/node pairs for (PatternOrganizer::iterator I = ComputableValues.begin(), E = ComputableValues.end(); I != E; ++I) for (PatternOrganizer::NodesForSlot::iterator J = I->second.begin(), E = I->second.end(); J != E; ++J) - OS << " unsigned Match_" << I->first << "_" << J->first->getName() + OS << " unsigned Match_" << I->first << "_" << J->first->getName() << "(SelectionDAGNode *N);\n"; // Output all of the dag reduction methods prototypes... - OS << "\n // DAG reduction methods...\n"; + OS << "\n // DAG reduction methods...\n"; for (PatternOrganizer::iterator I = ComputableValues.begin(), E = ComputableValues.end(); I != E; ++I) - OS << " ReducedValue_" << I->first << " *Reduce_" << I->first - << "(SelectionDAGNode *N,\n" << std::string(25+2*I->first.size(), ' ') + OS << " ReducedValue_" << I->first << " *Reduce_" << I->first + << "(SelectionDAGNode *N,\n" << std::string(27+2*I->first.size(), ' ') << "MachineBasicBlock *MBB);\n"; OS << " };\n}\n\n"; @@ -613,6 +874,52 @@ void InstrSelectorEmitter::run(std::ostream &OS) { << "}\n\n" << "//===" << std::string(70, '-') << "===//\n" << "// Matching methods...\n" - << "//\n"; + << "//\n\n"; + + for (PatternOrganizer::iterator I = ComputableValues.begin(), + E = ComputableValues.end(); I != E; ++I) { + const std::string &SlotName = I->first; + OS << "unsigned " << Target.getName() << "ISel::Match_" << SlotName + << "(SelectionDAGNode *N) {\n" + << " assert(N->getValueType() == ISD::" + << getName((*I->second.begin()).second[0]->getTree()->getType())<< ");\n" + << " // If we already have a cost available for " << SlotName + << " use it!\n" + << " if (N->getPatternFor(" << SlotName << "_Slot))\n" + << " return N->getCostFor(" << SlotName << "_Slot);\n\n" + << " unsigned Cost;\n" + << " switch (N->getNodeType()) {\n" + << " default: assert(0 && \"Unhandled node type for " << SlotName + << "!\");\n"; + + for (PatternOrganizer::NodesForSlot::iterator J = I->second.begin(), + E = I->second.end(); J != E; ++J) + OS << " case ISD::" << J->first->getName() << ":\tCost = Match_" + << SlotName << "_" << J->first->getName() << "(N); break;\n"; + + OS << " }\n return Cost;\n}\n\n"; + + for (PatternOrganizer::NodesForSlot::iterator J = I->second.begin(), + E = I->second.end(); J != E; ++J) { + Record *Operator = J->first; + OS << "unsigned " << Target.getName() << "ISel::Match_" << SlotName << "_" + << Operator->getName() << "(SelectionDAGNode *N) {\n" + << " unsigned Pattern = NoMatchPattern;\n" + << " unsigned MinCost = ~0U >> 1;\n"; + + std::vector > Patterns; + for (unsigned i = 0, e = J->second.size(); i != e; ++i) + Patterns.push_back(std::make_pair(J->second[i], + J->second[i]->getTree())); + EmitMatchCosters(OS, Patterns, "N", 2); + + OS << "\n N->setPatternCostFor(" << SlotName + << "_Slot, Pattern, MinCost, NumSlots);\n" + << " return MinCost;\n" + << "}\n"; + } + + break; // FIXME: REMOVE + } } diff --git a/support/tools/TableGen/InstrSelectorEmitter.h b/support/tools/TableGen/InstrSelectorEmitter.h index fce31487033..d1178a09c43 100644 --- a/support/tools/TableGen/InstrSelectorEmitter.h +++ b/support/tools/TableGen/InstrSelectorEmitter.h @@ -80,6 +80,7 @@ public: assert(Operator != 0 && "This is a leaf node!"); return Children; } + unsigned getNumChildren() const { return Children.size(); } TreePatternNode *getChild(unsigned c) const { assert(c < Children.size() && "Child access out of range!"); return getChildren()[c]; @@ -90,6 +91,10 @@ public: return Value; } + /// getValueRecord - Returns the value of this tree node as a record. For now + /// we only allow DefInit's as our leaf values, so this is used. + Record *getValueRecord() const; + /// clone - Make a copy of this tree and all of its children. /// TreePatternNode *clone() const; @@ -101,10 +106,10 @@ public: /// it with the using context we provide. void InstantiateNonterminals(InstrSelectorEmitter &ISE); - // UpdateNodeType - Set the node type of N to VT if VT contains information. - // If N already contains a conflicting type, then throw an exception. This - // returns true if any information was updated. - // + /// UpdateNodeType - Set the node type of N to VT if VT contains information. + /// If N already contains a conflicting type, then throw an exception. This + /// returns true if any information was updated. + /// bool updateNodeType(MVT::ValueType VT, const std::string &RecName); }; @@ -198,6 +203,11 @@ public: /// pattern. void error(const std::string &Msg) const; + /// getSlotName - If this is a leaf node, return the slot name that the + /// operand will update. + std::string getSlotName() const; + static std::string getSlotName(Record *R); + private: MVT::ValueType getIntrinsicType(Record *R) const; TreePatternNode *ParseTreePattern(DagInit *DI); @@ -270,6 +280,11 @@ public: const CodeGenTarget &getTarget() const { return Target; } std::map &getNodeTypes() { return NodeTypes; } + const NodeType &getNodeType(Record *R) const { + std::map::const_iterator I = NodeTypes.find(R); + assert(I != NodeTypes.end() && "Unknown node type!"); + return I->second; + } /// getPattern - return the pattern corresponding to the specified record, or /// null if there is none. @@ -313,6 +328,14 @@ private: // CalculateComputableValues - Fill in the ComputableValues map through // analysis of the patterns we are playing with. void CalculateComputableValues(); + + // EmitMatchCosters - Given a list of patterns, which all have the same root + // pattern operator, emit an efficient decision tree to decide which one to + // pick. This is structured this way to avoid reevaluations of non-obvious + // subexpressions. + void EmitMatchCosters(std::ostream &OS, + const std::vector > &Patterns, + const std::string &VarPrefix, unsigned Indent); }; #endif diff --git a/utils/TableGen/InstrSelectorEmitter.cpp b/utils/TableGen/InstrSelectorEmitter.cpp index b9475360376..a2de8c122b4 100644 --- a/utils/TableGen/InstrSelectorEmitter.cpp +++ b/utils/TableGen/InstrSelectorEmitter.cpp @@ -9,6 +9,8 @@ #include "CodeGenWrappers.h" #include "Record.h" #include "Support/Debug.h" +#include "Support/StringExtras.h" +#include NodeType::ArgResultTypes NodeType::Translate(Record *R) { const std::string &Name = R->getName(); @@ -24,6 +26,15 @@ NodeType::ArgResultTypes NodeType::Translate(Record *R) { // TreePatternNode implementation // +/// getValueRecord - Returns the value of this tree node as a record. For now +/// we only allow DefInit's as our leaf values, so this is used. +Record *TreePatternNode::getValueRecord() const { + DefInit *DI = dynamic_cast(getValue()); + assert(DI && "Instruction Selector does not yet support non-def leaves!"); + return DI->getDef(); +} + + // updateNodeType - Set the node type of N to VT if VT contains information. If // N already contains a conflicting type, then throw an exception // @@ -50,17 +61,17 @@ void TreePatternNode::InstantiateNonterminals(InstrSelectorEmitter &ISE) { } // If this is a leaf, it might be a reference to a nonterminal! Check now. - if (DefInit *DI = dynamic_cast(getValue())) - if (DI->getDef()->isSubClassOf("Nonterminal")) { - Pattern *NT = ISE.getPattern(DI->getDef()); - if (!NT->isResolved()) { - // We found an unresolved nonterminal reference. Ask the ISE to clone - // it for us, then update our reference to the fresh, new, resolved, - // nonterminal. - - Value = new DefInit(ISE.InstantiateNonterminal(NT, getType())); - } + Record *R = getValueRecord(); + if (R->isSubClassOf("Nonterminal")) { + Pattern *NT = ISE.getPattern(R); + if (!NT->isResolved()) { + // We found an unresolved nonterminal reference. Ask the ISE to clone + // it for us, then update our reference to the fresh, new, resolved, + // nonterminal. + + Value = new DefInit(ISE.InstantiateNonterminal(NT, getType())); } + } } @@ -80,7 +91,6 @@ TreePatternNode *TreePatternNode::clone() const { return New; } - std::ostream &operator<<(std::ostream &OS, const TreePatternNode &N) { if (N.isLeaf()) return OS << N.getType() << ":" << *N.getValue(); @@ -126,11 +136,7 @@ Pattern::Pattern(PatternType pty, DagInit *RawPat, Record *TheRec, assert(Tree->getChildren().size() == 2 && "Set with != 2 arguments?"); if (!Tree->getChild(0)->isLeaf()) error("Arg #0 of set should be a register or register class!"); - DefInit *RegInit = dynamic_cast(Tree->getChild(0)->getValue()); - if (RegInit == 0) - error("LHS of 'set' expected to be a register or register class!"); - - Result = RegInit->getDef(); + Result = Tree->getChild(0)->getValueRecord(); Tree = Tree->getChild(1); } } @@ -232,8 +238,7 @@ bool Pattern::InferTypes(TreePatternNode *N, bool &MadeChange) { bool AnyUnset = false; Record *Operator = N->getOperator(); - assert(ISE.getNodeTypes().count(Operator) && "No node info for node!"); - const NodeType &NT = ISE.getNodeTypes()[Operator]; + const NodeType &NT = ISE.getNodeType(Operator); // Check to see if we can infer anything about the argument types from the // return types... @@ -317,6 +322,38 @@ std::ostream &operator<<(std::ostream &OS, const Pattern &P) { } +/// getSlotName - If this is a leaf node, return the slot name that the operand +/// will update. +std::string Pattern::getSlotName() const { + if (getPatternType() == Pattern::Nonterminal) { + // Just use the nonterminal name, which will already include the type if + // it has been cloned. + return getRecord()->getName(); + } else { + std::string SlotName; + if (getResult()) + SlotName = getResult()->getName()+"_"; + else + SlotName = "Void_"; + return SlotName + getName(getTree()->getType()); + } +} + +/// getSlotName - If this is a leaf node, return the slot name that the +/// operand will update. +std::string Pattern::getSlotName(Record *R) { + if (R->isSubClassOf("Nonterminal")) { + // Just use the nonterminal name, which will already include the type if + // it has been cloned. + return R->getName(); + } else if (R->isSubClassOf("RegisterClass")) { + MVT::ValueType Ty = getValueType(R->getValueAsDef("RegType")); + return R->getName() + "_" + getName(Ty); + } else { + assert(0 && "Don't know how to get a slot name for this!"); + } +} + //===----------------------------------------------------------------------===// // PatternOrganizer implementation // @@ -324,29 +361,12 @@ std::ostream &operator<<(std::ostream &OS, const Pattern &P) { /// addPattern - Add the specified pattern to the appropriate location in the /// collection. void PatternOrganizer::addPattern(Pattern *P) { - std::string ValueName; - if (P->getPatternType() == Pattern::Nonterminal) { - // Just use the nonterminal name, which will already include the type if - // it has been cloned. - ValueName = P->getRecord()->getName(); - } else { - if (P->getResult()) - ValueName += P->getResult()->getName()+"_"; - else - ValueName += "Void_"; - ValueName += getName(P->getTree()->getType()); - } - - NodesForSlot &Nodes = AllPatterns[ValueName]; + NodesForSlot &Nodes = AllPatterns[P->getSlotName()]; if (!P->getTree()->isLeaf()) Nodes[P->getTree()->getOperator()].push_back(P); else { // Right now we only support DefInit's with node types... - DefInit *Val = dynamic_cast(P->getTree()->getValue()); - if (!Val) - throw std::string("We only support def inits in PatternOrganizer" - "::addPattern so far!"); - Nodes[Val->getDef()].push_back(P); + Nodes[P->getTree()->getValueRecord()].push_back(P); } } @@ -469,6 +489,11 @@ Record *InstrSelectorEmitter::InstantiateNonterminal(Pattern *NT, Record *New = new Record(NT->getRecord()->getName()+"_"+getName(ResultTy)); + // Copy over the superclasses... + const std::vector &SCs = NT->getRecord()->getSuperClasses(); + for (unsigned i = 0, e = SCs.size(); i != e; ++i) + New->addSuperClass(SCs[i]); + DEBUG(std::cerr << " Nonterminal '" << NT->getRecord()->getName() << "' for type '" << getName(ResultTy) << "', producing '" << New->getName() << "'\n"); @@ -503,6 +528,242 @@ void InstrSelectorEmitter::CalculateComputableValues() { ComputableValues.addPattern(I->second); } +#if 0 +// MoveIdenticalPatterns - Given a tree pattern 'P', move all of the tree +// patterns which have the same top-level structure as P from the 'From' list to +// the 'To' list. +static void MoveIdenticalPatterns(TreePatternNode *P, + std::vector > &From, + std::vector > &To) { + assert(!P->isLeaf() && "All leaves are identical!"); + + const std::vector &PChildren = P->getChildren(); + for (unsigned i = 0; i != From.size(); ++i) { + TreePatternNode *N = From[i].second; + assert(P->getOperator() == N->getOperator() &&"Differing operators?"); + assert(PChildren.size() == N->getChildren().size() && + "Nodes with different arity??"); + bool isDifferent = false; + for (unsigned c = 0, e = PChildren.size(); c != e; ++c) { + TreePatternNode *PC = PChildren[c]; + TreePatternNode *NC = N->getChild(c); + if (PC->isLeaf() != NC->isLeaf()) { + isDifferent = true; + break; + } + + if (!PC->isLeaf()) { + if (PC->getOperator() != NC->getOperator()) { + isDifferent = true; + break; + } + } else { // It's a leaf! + if (PC->getValueRecord() != NC->getValueRecord()) { + isDifferent = true; + break; + } + } + } + // If it's the same as the reference one, move it over now... + if (!isDifferent) { + To.push_back(std::make_pair(From[i].first, N)); + From.erase(From.begin()+i); + --i; // Don't skip an entry... + } + } +} +#endif + +static void EmitPatternPredicates(TreePatternNode *Tree, + const std::string &VarName, std::ostream &OS){ + OS << " && " << VarName << "->getNodeType() == ISD::" + << Tree->getOperator()->getName(); + + for (unsigned c = 0, e = Tree->getNumChildren(); c != e; ++c) + if (!Tree->getChild(c)->isLeaf()) + EmitPatternPredicates(Tree->getChild(c), + VarName + "->getUse(" + utostr(c)+")", OS); +} + +static void EmitPatternCosts(TreePatternNode *Tree, const std::string &VarName, + std::ostream &OS) { + for (unsigned c = 0, e = Tree->getNumChildren(); c != e; ++c) + if (Tree->getChild(c)->isLeaf()) { + OS << " + Match_" + << Pattern::getSlotName(Tree->getChild(c)->getValueRecord()) << "(" + << VarName << "->getUse(" << c << "))"; + } else { + EmitPatternCosts(Tree->getChild(c), + VarName + "->getUse(" + utostr(c) + ")", OS); + } +} + + +// EmitMatchCosters - Given a list of patterns, which all have the same root +// pattern operator, emit an efficient decision tree to decide which one to +// pick. This is structured this way to avoid reevaluations of non-obvious +// subexpressions. +void InstrSelectorEmitter::EmitMatchCosters(std::ostream &OS, + const std::vector > &Patterns, + const std::string &VarPrefix, + unsigned IndentAmt) { + assert(!Patterns.empty() && "No patterns to emit matchers for!"); + std::string Indent(IndentAmt, ' '); + + // Load all of the operands of the root node into scalars for fast access + const NodeType &ONT = getNodeType(Patterns[0].second->getOperator()); + for (unsigned i = 0, e = ONT.ArgTypes.size(); i != e; ++i) + OS << Indent << "SelectionDAGNode *" << VarPrefix << "_Op" << i + << " = N->getUse(" << i << ");\n"; + + // Compute the costs of computing the various nonterminals/registers, which + // are directly used at this level. + OS << "\n" << Indent << "// Operand matching costs...\n"; + std::set ComputedValues; // Avoid duplicate computations... + for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { + const std::vector &Children = + Patterns[i].second->getChildren(); + for (unsigned c = 0, e = Children.size(); c != e; ++c) { + TreePatternNode *N = Children[c]; + if (N->isLeaf()) { + Record *VR = N->getValueRecord(); + const std::string &LeafName = VR->getName(); + std::string OpName = VarPrefix + "_Op" + utostr(c); + std::string ValName = OpName + "_" + LeafName + "_Cost"; + if (!ComputedValues.count(ValName)) { + OS << Indent << "unsigned " << ValName << " = Match_" + << Pattern::getSlotName(VR) << "(" << OpName << ");\n"; + ComputedValues.insert(ValName); + } + } + } + } + OS << "\n"; + + + std::string LocCostName = VarPrefix + "_Cost"; + OS << Indent << "unsigned " << LocCostName << "Min = ~0U >> 1;\n" + << Indent << "unsigned " << VarPrefix << "_PatternMin = NoMatch;\n"; + +#if 0 + // Separate out all of the patterns into groups based on what their top-level + // signature looks like... + std::vector > PatternsLeft(Patterns); + while (!PatternsLeft.empty()) { + // Process all of the patterns that have the same signature as the last + // element... + std::vector > Group; + MoveIdenticalPatterns(PatternsLeft.back().second, PatternsLeft, Group); + assert(!Group.empty() && "Didn't at least pick the source pattern?"); + +#if 0 + OS << "PROCESSING GROUP:\n"; + for (unsigned i = 0, e = Group.size(); i != e; ++i) + OS << " " << *Group[i].first << "\n"; + OS << "\n\n"; +#endif + + OS << Indent << "{ // "; + + if (Group.size() != 1) { + OS << Group.size() << " size group...\n"; + OS << Indent << " unsigned " << VarPrefix << "_Pattern = NoMatch;\n"; + } else { + OS << *Group[0].first << "\n"; + OS << Indent << " unsigned " << VarPrefix << "_Pattern = " + << Group[0].first->getRecord()->getName() << "_Pattern;\n"; + } + + OS << Indent << " unsigned " << LocCostName << " = "; + if (Group.size() == 1) + OS << "1;\n"; // Add inst cost if at individual rec + else + OS << "0;\n"; + + // Loop over all of the operands, adding in their costs... + TreePatternNode *N = Group[0].second; + const std::vector &Children = N->getChildren(); + + // If necessary, emit conditionals to check for the appropriate tree + // structure here... + for (unsigned i = 0, e = Children.size(); i != e; ++i) { + TreePatternNode *C = Children[i]; + if (C->isLeaf()) { + // We already calculated the cost for this leaf, add it in now... + OS << Indent << " " << LocCostName << " += " + << VarPrefix << "_Op" << utostr(i) << "_" + << C->getValueRecord()->getName() << "_Cost;\n"; + } else { + // If it's not a leaf, we have to check to make sure that the current + // node has the appropriate structure, then recurse into it... + OS << Indent << " if (" << VarPrefix << "_Op" << i + << "->getNodeType() == ISD::" << C->getOperator()->getName() + << ") {\n"; + std::vector > SubPatterns; + for (unsigned n = 0, e = Group.size(); n != e; ++n) + SubPatterns.push_back(std::make_pair(Group[n].first, + Group[n].second->getChild(i))); + EmitMatchCosters(OS, SubPatterns, VarPrefix+"_Op"+utostr(i), + IndentAmt + 4); + OS << Indent << " }\n"; + } + } + + // If the cost for this match is less than the minimum computed cost so far, + // update the minimum cost and selected pattern. + OS << Indent << " if (" << LocCostName << " < " << LocCostName << "Min) { " + << LocCostName << "Min = " << LocCostName << "; " << VarPrefix + << "_PatternMin = " << VarPrefix << "_Pattern; }\n"; + + OS << Indent << "}\n"; + } +#endif + + for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { + Pattern *P = Patterns[i].first; + TreePatternNode *PTree = P->getTree(); + unsigned PatternCost = 1; + + // Check to see if there are any non-leaf elements in the pattern. If so, + // we need to emit a predicate for this match. + bool AnyNonLeaf = false; + for (unsigned c = 0, e = PTree->getNumChildren(); c != e; ++c) + if (!PTree->getChild(c)->isLeaf()) { + AnyNonLeaf = true; + break; + } + + if (!AnyNonLeaf) { // No predicate necessary, just output a scope... + OS << " {// " << *P << "\n"; + } else { + // We need to emit a predicate to make sure the tree pattern matches, do + // so now... + OS << " if (1"; + for (unsigned c = 0, e = PTree->getNumChildren(); c != e; ++c) + if (!PTree->getChild(c)->isLeaf()) + EmitPatternPredicates(PTree->getChild(c), + VarPrefix + "_Op" + utostr(c), OS); + + OS << ") {\n // " << *P << "\n"; + } + + OS << " unsigned PatCost = " << PatternCost; + + for (unsigned c = 0, e = PTree->getNumChildren(); c != e; ++c) + if (PTree->getChild(c)->isLeaf()) { + OS << " + " << VarPrefix << "_Op" << c << "_" + << PTree->getChild(c)->getValueRecord()->getName() << "_Cost"; + } else { + EmitPatternCosts(PTree->getChild(c), VarPrefix + "_Op" + utostr(c), OS); + } + OS << ";\n"; + OS << " if (PatCost < MinCost) { MinCost = PatCost; Pattern = " + << P->getRecord()->getName() << "_Pattern; }\n" + << " }\n"; + } +} + + void InstrSelectorEmitter::run(std::ostream &OS) { // Type-check all of the node types to ensure we "understand" them. ReadNodeTypes(); @@ -570,30 +831,30 @@ void InstrSelectorEmitter::run(std::ostream &OS) { << " }\n\n" << " // DAG matching methods for classes... all of these methods" " return the cost\n" - <<" // of producing a value of the specified class and type, which" + << " // of producing a value of the specified class and type, which" " also gets\n" << " // added to the DAG node.\n"; // Output all of the matching prototypes for slots... for (PatternOrganizer::iterator I = ComputableValues.begin(), E = ComputableValues.end(); I != E; ++I) - OS << " unsigned Match_" << I->first << "(SelectionDAGNode *N);\n"; - OS << "\n // DAG matching methods for DAG nodes...\n"; + OS << " unsigned Match_" << I->first << "(SelectionDAGNode *N);\n"; + OS << "\n // DAG matching methods for DAG nodes...\n"; // Output all of the matching prototypes for slot/node pairs for (PatternOrganizer::iterator I = ComputableValues.begin(), E = ComputableValues.end(); I != E; ++I) for (PatternOrganizer::NodesForSlot::iterator J = I->second.begin(), E = I->second.end(); J != E; ++J) - OS << " unsigned Match_" << I->first << "_" << J->first->getName() + OS << " unsigned Match_" << I->first << "_" << J->first->getName() << "(SelectionDAGNode *N);\n"; // Output all of the dag reduction methods prototypes... - OS << "\n // DAG reduction methods...\n"; + OS << "\n // DAG reduction methods...\n"; for (PatternOrganizer::iterator I = ComputableValues.begin(), E = ComputableValues.end(); I != E; ++I) - OS << " ReducedValue_" << I->first << " *Reduce_" << I->first - << "(SelectionDAGNode *N,\n" << std::string(25+2*I->first.size(), ' ') + OS << " ReducedValue_" << I->first << " *Reduce_" << I->first + << "(SelectionDAGNode *N,\n" << std::string(27+2*I->first.size(), ' ') << "MachineBasicBlock *MBB);\n"; OS << " };\n}\n\n"; @@ -613,6 +874,52 @@ void InstrSelectorEmitter::run(std::ostream &OS) { << "}\n\n" << "//===" << std::string(70, '-') << "===//\n" << "// Matching methods...\n" - << "//\n"; + << "//\n\n"; + + for (PatternOrganizer::iterator I = ComputableValues.begin(), + E = ComputableValues.end(); I != E; ++I) { + const std::string &SlotName = I->first; + OS << "unsigned " << Target.getName() << "ISel::Match_" << SlotName + << "(SelectionDAGNode *N) {\n" + << " assert(N->getValueType() == ISD::" + << getName((*I->second.begin()).second[0]->getTree()->getType())<< ");\n" + << " // If we already have a cost available for " << SlotName + << " use it!\n" + << " if (N->getPatternFor(" << SlotName << "_Slot))\n" + << " return N->getCostFor(" << SlotName << "_Slot);\n\n" + << " unsigned Cost;\n" + << " switch (N->getNodeType()) {\n" + << " default: assert(0 && \"Unhandled node type for " << SlotName + << "!\");\n"; + + for (PatternOrganizer::NodesForSlot::iterator J = I->second.begin(), + E = I->second.end(); J != E; ++J) + OS << " case ISD::" << J->first->getName() << ":\tCost = Match_" + << SlotName << "_" << J->first->getName() << "(N); break;\n"; + + OS << " }\n return Cost;\n}\n\n"; + + for (PatternOrganizer::NodesForSlot::iterator J = I->second.begin(), + E = I->second.end(); J != E; ++J) { + Record *Operator = J->first; + OS << "unsigned " << Target.getName() << "ISel::Match_" << SlotName << "_" + << Operator->getName() << "(SelectionDAGNode *N) {\n" + << " unsigned Pattern = NoMatchPattern;\n" + << " unsigned MinCost = ~0U >> 1;\n"; + + std::vector > Patterns; + for (unsigned i = 0, e = J->second.size(); i != e; ++i) + Patterns.push_back(std::make_pair(J->second[i], + J->second[i]->getTree())); + EmitMatchCosters(OS, Patterns, "N", 2); + + OS << "\n N->setPatternCostFor(" << SlotName + << "_Slot, Pattern, MinCost, NumSlots);\n" + << " return MinCost;\n" + << "}\n"; + } + + break; // FIXME: REMOVE + } } diff --git a/utils/TableGen/InstrSelectorEmitter.h b/utils/TableGen/InstrSelectorEmitter.h index fce31487033..d1178a09c43 100644 --- a/utils/TableGen/InstrSelectorEmitter.h +++ b/utils/TableGen/InstrSelectorEmitter.h @@ -80,6 +80,7 @@ public: assert(Operator != 0 && "This is a leaf node!"); return Children; } + unsigned getNumChildren() const { return Children.size(); } TreePatternNode *getChild(unsigned c) const { assert(c < Children.size() && "Child access out of range!"); return getChildren()[c]; @@ -90,6 +91,10 @@ public: return Value; } + /// getValueRecord - Returns the value of this tree node as a record. For now + /// we only allow DefInit's as our leaf values, so this is used. + Record *getValueRecord() const; + /// clone - Make a copy of this tree and all of its children. /// TreePatternNode *clone() const; @@ -101,10 +106,10 @@ public: /// it with the using context we provide. void InstantiateNonterminals(InstrSelectorEmitter &ISE); - // UpdateNodeType - Set the node type of N to VT if VT contains information. - // If N already contains a conflicting type, then throw an exception. This - // returns true if any information was updated. - // + /// UpdateNodeType - Set the node type of N to VT if VT contains information. + /// If N already contains a conflicting type, then throw an exception. This + /// returns true if any information was updated. + /// bool updateNodeType(MVT::ValueType VT, const std::string &RecName); }; @@ -198,6 +203,11 @@ public: /// pattern. void error(const std::string &Msg) const; + /// getSlotName - If this is a leaf node, return the slot name that the + /// operand will update. + std::string getSlotName() const; + static std::string getSlotName(Record *R); + private: MVT::ValueType getIntrinsicType(Record *R) const; TreePatternNode *ParseTreePattern(DagInit *DI); @@ -270,6 +280,11 @@ public: const CodeGenTarget &getTarget() const { return Target; } std::map &getNodeTypes() { return NodeTypes; } + const NodeType &getNodeType(Record *R) const { + std::map::const_iterator I = NodeTypes.find(R); + assert(I != NodeTypes.end() && "Unknown node type!"); + return I->second; + } /// getPattern - return the pattern corresponding to the specified record, or /// null if there is none. @@ -313,6 +328,14 @@ private: // CalculateComputableValues - Fill in the ComputableValues map through // analysis of the patterns we are playing with. void CalculateComputableValues(); + + // EmitMatchCosters - Given a list of patterns, which all have the same root + // pattern operator, emit an efficient decision tree to decide which one to + // pick. This is structured this way to avoid reevaluations of non-obvious + // subexpressions. + void EmitMatchCosters(std::ostream &OS, + const std::vector > &Patterns, + const std::string &VarPrefix, unsigned Indent); }; #endif -- 2.34.1