From 6dafd3921d991d736d7240aa9f553a8c1ebb6938 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Fri, 8 Aug 2003 16:30:10 +0000 Subject: Emit the first half of the instruction selector. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7701 91177308-0d34-0410-b5e6-96231b3b80d8 --- support/tools/TableGen/InstrSelectorEmitter.cpp | 144 +++++++++++++++++++++++- support/tools/TableGen/InstrSelectorEmitter.h | 46 +++++++- 2 files changed, 186 insertions(+), 4 deletions(-) (limited to 'support/tools') diff --git a/support/tools/TableGen/InstrSelectorEmitter.cpp b/support/tools/TableGen/InstrSelectorEmitter.cpp index 3e30a52b6c..b947536037 100644 --- a/support/tools/TableGen/InstrSelectorEmitter.cpp +++ b/support/tools/TableGen/InstrSelectorEmitter.cpp @@ -317,6 +317,41 @@ std::ostream &operator<<(std::ostream &OS, const Pattern &P) { } +//===----------------------------------------------------------------------===// +// PatternOrganizer implementation +// + +/// 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]; + 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); + } +} + + + //===----------------------------------------------------------------------===// // InstrSelectorEmitter implementation // @@ -432,11 +467,12 @@ Record *InstrSelectorEmitter::InstantiateNonterminal(Pattern *NT, Record* &Slot = InstantiatedNTs[std::make_pair(NT, ResultTy)]; if (Slot) return Slot; - DEBUG(std::cerr << " Nonterminal '" << NT->getRecord()->getName() - << "' for type '" << getName(ResultTy) << "'\n"); - Record *New = new Record(NT->getRecord()->getName()+"_"+getName(ResultTy)); + DEBUG(std::cerr << " Nonterminal '" << NT->getRecord()->getName() + << "' for type '" << getName(ResultTy) << "', producing '" + << New->getName() << "'\n"); + // Copy the pattern... Pattern *NewPat = NT->clone(New); @@ -457,6 +493,15 @@ Record *InstrSelectorEmitter::InstantiateNonterminal(Pattern *NT, return Slot = New; } +// CalculateComputableValues - Fill in the ComputableValues map through +// analysis of the patterns we are playing with. +void InstrSelectorEmitter::CalculateComputableValues() { + // Loop over all of the patterns, adding them to the ComputableValues map + for (std::map::iterator I = Patterns.begin(), + E = Patterns.end(); I != E; ++I) + if (I->second->isResolved()) + ComputableValues.addPattern(I->second); +} void InstrSelectorEmitter::run(std::ostream &OS) { // Type-check all of the node types to ensure we "understand" them. @@ -471,10 +516,103 @@ void InstrSelectorEmitter::run(std::ostream &OS) { // that they are used in. InstantiateNonterminals(); + // Clear InstantiatedNTs, we don't need it anymore... + InstantiatedNTs.clear(); std::cerr << "Patterns aquired:\n"; for (std::map::iterator I = Patterns.begin(), E = Patterns.end(); I != E; ++I) if (I->second->isResolved()) std::cerr << " " << *I->second << "\n"; + + CalculateComputableValues(); + + // Output the slot number enums... + OS << "\n\nenum { // Slot numbers...\n" + << " LastBuiltinSlot = ISD::NumBuiltinSlots-1, // Start numbering here\n"; + for (PatternOrganizer::iterator I = ComputableValues.begin(), + E = ComputableValues.end(); I != E; ++I) + OS << " " << I->first << "_Slot,\n"; + OS << " NumSlots\n};\n\n// Reduction value typedefs...\n"; + + // Output the reduction value typedefs... + for (PatternOrganizer::iterator I = ComputableValues.begin(), + E = ComputableValues.end(); I != E; ++I) + OS << "typedef ReduceValuefirst + << "_Slot> ReducedValue_" << I->first << ";\n"; + + // Output the pattern enums... + OS << "\n\n" + << "enum { // Patterns...\n" + << " NotComputed = 0,\n" + << " NoMatchPattern, \n"; + for (PatternOrganizer::iterator I = ComputableValues.begin(), + E = ComputableValues.end(); I != E; ++I) { + OS << " // " << I->first << " patterns...\n"; + for (PatternOrganizer::NodesForSlot::iterator J = I->second.begin(), + E = I->second.end(); J != E; ++J) + for (unsigned i = 0, e = J->second.size(); i != e; ++i) + OS << " " << J->second[i]->getRecord()->getName() << "_Pattern,\n"; + } + OS << "};\n\n"; + + // Start emitting the class... + OS << "namespace {\n" + << " class " << Target.getName() << "ISel {\n" + << " SelectionDAG &DAG;\n" + << " public:\n" + << " X86ISel(SelectionDag &D) : DAG(D) {}\n" + << " void generateCode();\n" + << " private:\n" + << " unsigned makeAnotherReg(const TargetRegisterClass *RC) {\n" + << " return DAG.getMachineFunction().getSSARegMap()->createVirt" + "ualRegister(RC);\n" + << " }\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" + " 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"; + + // 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() + << "(SelectionDAGNode *N);\n"; + + // Output all of the dag reduction methods prototypes... + 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(), ' ') + << "MachineBasicBlock *MBB);\n"; + OS << " };\n}\n\n"; + + OS << "void X86ISel::generateCode() {\n" + << " SelectionDAGNode *Root = DAG.getRoot();\n" + << " assert(Root->getValueType() == ISD::Void && " + "\"Root of DAG produces value??\");\n\n" + << " std::cerr << \"\\n\";\n" + << " unsigned Cost = Match_Void_Void(Root);\n" + << " if (Cost >= ~0U >> 1) {\n" + << " std::cerr << \"Match failed!\\n\";\n" + << " Root->dump();\n" + << " abort();\n" + << " }\n\n" + << " std::cerr << \"Total DAG Cost: \" << Cost << \"\\n\\n\";\n\n" + << " Reduce_Void_Void(Root, 0);\n" + << "}\n\n" + << "//===" << std::string(70, '-') << "===//\n" + << "// Matching methods...\n" + << "//\n"; } + diff --git a/support/tools/TableGen/InstrSelectorEmitter.h b/support/tools/TableGen/InstrSelectorEmitter.h index 0a8ca982fe..fce3148703 100644 --- a/support/tools/TableGen/InstrSelectorEmitter.h +++ b/support/tools/TableGen/InstrSelectorEmitter.h @@ -67,7 +67,10 @@ public: : Operator(o), Type(MVT::Other), Children(c), Value(0) {} TreePatternNode(Init *V) : Operator(0), Type(MVT::Other), Value(V) {} - Record *getOperator() const { return Operator; } + Record *getOperator() const { + assert(Operator && "This is a leaf node!"); + return Operator; + } MVT::ValueType getType() const { return Type; } void setType(MVT::ValueType T) { Type = T; } @@ -204,6 +207,36 @@ private: std::ostream &operator<<(std::ostream &OS, const Pattern &P); +/// PatternOrganizer - This class represents all of the patterns which are +/// useful for the instruction selector, neatly catagorized in a hierarchical +/// structure. +struct PatternOrganizer { + /// PatternsForNode - The list of patterns which can produce a value of a + /// particular slot type, given a particular root node in the tree. All of + /// the patterns in this vector produce the same value type and have the same + /// root DAG node. + typedef std::vector PatternsForNode; + + /// NodesForSlot - This map keeps track of all of the root DAG nodes which can + /// lead to the production of a value for this slot. All of the patterns in + /// this data structure produces values of the same slot. + typedef std::map NodesForSlot; + + /// AllPatterns - This data structure contains all patterns in the instruction + /// selector. + std::map AllPatterns; + + // Forwarding functions... + typedef std::map::iterator iterator; + iterator begin() { return AllPatterns.begin(); } + iterator end() { return AllPatterns.end(); } + + + /// addPattern - Add the specified pattern to the appropriate location in the + /// collection. + void addPattern(Pattern *P); +}; + /// InstrSelectorEmitter - The top-level class which coordinates construction /// and emission of the instruction selector. @@ -222,6 +255,13 @@ class InstrSelectorEmitter : public TableGenBackend { /// have been instantiated already... /// std::map, Record*> InstantiatedNTs; + + /// ComputableValues - This map indicates which patterns can be used to + /// generate a value that is used by the selector. The keys of this map + /// implicitly define the values that are used by the selector. + /// + PatternOrganizer ComputableValues; + public: InstrSelectorEmitter(RecordKeeper &R) : Records(R) {} @@ -269,6 +309,10 @@ private: // InstantiateNonterminals - Instantiate any unresolved nonterminals with // information from the context that they are used in. void InstantiateNonterminals(); + + // CalculateComputableValues - Fill in the ComputableValues map through + // analysis of the patterns we are playing with. + void CalculateComputableValues(); }; #endif -- cgit v1.2.3