From ef0ce6a4948f4494d2115b7d3593ad0f30037e6b Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Thu, 7 Aug 2003 23:16:20 +0000 Subject: Finish implementation of nonterminal instantiation. Tree patterns are now, finally, ready to use! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7699 91177308-0d34-0410-b5e6-96231b3b80d8 --- utils/TableGen/InstrSelectorEmitter.cpp | 128 ++++++++++++++++++++++++++++---- utils/TableGen/InstrSelectorEmitter.h | 51 +++++++++++-- 2 files changed, 158 insertions(+), 21 deletions(-) (limited to 'utils/TableGen') diff --git a/utils/TableGen/InstrSelectorEmitter.cpp b/utils/TableGen/InstrSelectorEmitter.cpp index 250c8975c1..3e30a52b6c 100644 --- a/utils/TableGen/InstrSelectorEmitter.cpp +++ b/utils/TableGen/InstrSelectorEmitter.cpp @@ -38,6 +38,49 @@ bool TreePatternNode::updateNodeType(MVT::ValueType VT, throw "Type inferfence contradiction found for pattern " + RecName; } +/// InstantiateNonterminals - If this pattern refers to any nonterminals which +/// are not themselves completely resolved, clone the nonterminal and resolve it +/// with the using context we provide. +/// +void TreePatternNode::InstantiateNonterminals(InstrSelectorEmitter &ISE) { + if (!isLeaf()) { + for (unsigned i = 0, e = Children.size(); i != e; ++i) + Children[i]->InstantiateNonterminals(ISE); + return; + } + + // 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())); + } + } +} + + +/// clone - Make a copy of this tree and all of its children. +/// +TreePatternNode *TreePatternNode::clone() const { + TreePatternNode *New; + if (isLeaf()) { + New = new TreePatternNode(Value); + } else { + std::vector CChildren(Children.size()); + for (unsigned i = 0, e = Children.size(); i != e; ++i) + CChildren[i] = Children[i]->clone(); + New = new TreePatternNode(Operator, CChildren); + } + New->setType(Type); + return New; +} + + std::ostream &operator<<(std::ostream &OS, const TreePatternNode &N) { if (N.isLeaf()) return OS << N.getType() << ":" << *N.getValue(); @@ -67,16 +110,13 @@ Pattern::Pattern(PatternType pty, DagInit *RawPat, Record *TheRec, // First, parse the pattern... Tree = ParseTreePattern(RawPat); - - bool MadeChange, AnyUnset; - do { - MadeChange = false; - AnyUnset = InferTypes(Tree, MadeChange); - } while ((AnyUnset || MadeChange) && !(AnyUnset && !MadeChange)); + + // Run the type-inference engine... + InferAllTypes(); if (PTy == Instruction || PTy == Expander) { // Check to make sure there is not any unset types in the tree pattern... - if (AnyUnset) { + if (!isResolved()) { std::cerr << "In pattern: " << *Tree << "\n"; error("Could not infer all types!"); } @@ -92,13 +132,12 @@ Pattern::Pattern(PatternType pty, DagInit *RawPat, Record *TheRec, Result = RegInit->getDef(); Tree = Tree->getChild(1); - } } - - Resolved = !AnyUnset; } + + void Pattern::error(const std::string &Msg) const { std::string M = "In "; switch (PTy) { @@ -175,6 +214,15 @@ TreePatternNode *Pattern::ParseTreePattern(DagInit *DI) { return new TreePatternNode(Operator, Children); } +void Pattern::InferAllTypes() { + bool MadeChange, AnyUnset; + do { + MadeChange = false; + AnyUnset = InferTypes(Tree, MadeChange); + } while ((AnyUnset || MadeChange) && !(AnyUnset && !MadeChange)); + Resolved = !AnyUnset; +} + // InferTypes - Perform type inference on the tree, returning true if there // are any remaining untyped nodes and setting MadeChange if any changes were @@ -240,15 +288,16 @@ bool Pattern::InferTypes(TreePatternNode *N, bool &MadeChange) { return AnyUnset | N->getType() == MVT::Other; } -/// InstantiateNonterminalsReferenced - If this pattern refers to any -/// nonterminals which are not themselves completely resolved, clone the -/// nonterminal and resolve it with the using context we provide. +/// clone - This method is used to make an exact copy of the current pattern, +/// then change the "TheRecord" instance variable to the specified record. /// -void Pattern::InstantiateNonterminalsReferenced() { - +Pattern *Pattern::clone(Record *R) const { + assert(PTy == Nonterminal && "Can only clone nonterminals"); + return new Pattern(Tree->clone(), R, Resolved, ISE); } + std::ostream &operator<<(std::ostream &OS, const Pattern &P) { switch (P.getPatternType()) { case Pattern::Nonterminal: OS << "Nonterminal pattern "; break; @@ -362,10 +411,50 @@ void InstrSelectorEmitter::ReadExpanderPatterns() { // information from the context that they are used in. // void InstrSelectorEmitter::InstantiateNonterminals() { + DEBUG(std::cerr << "Instantiating nonterminals:\n"); for (std::map::iterator I = Patterns.begin(), E = Patterns.end(); I != E; ++I) if (I->second->isResolved()) - I->second->InstantiateNonterminalsReferenced(); + I->second->InstantiateNonterminals(); +} + +/// InstantiateNonterminal - This method takes the nonterminal specified by +/// NT, which should not be completely resolved, clones it, applies ResultTy +/// to its root, then runs the type inference stuff on it. This should +/// produce a newly resolved nonterminal, which we make a record for and +/// return. To be extra fancy and efficient, this only makes one clone for +/// each type it is instantiated with. +Record *InstrSelectorEmitter::InstantiateNonterminal(Pattern *NT, + MVT::ValueType ResultTy) { + assert(!NT->isResolved() && "Nonterminal is already resolved!"); + + // Check to see if we have already instantiated this pair... + 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)); + + // Copy the pattern... + Pattern *NewPat = NT->clone(New); + + // Apply the type to the root... + NewPat->getTree()->updateNodeType(ResultTy, New->getName()); + + // Infer types... + NewPat->InferAllTypes(); + + // Make sure everything is good to go now... + if (!NewPat->isResolved()) + NewPat->error("Instantiating nonterminal did not resolve all types!"); + + // Add the pattern to the patterns map, add the record to the RecordKeeper, + // return the new record. + Patterns[New] = NewPat; + Records.addDef(New); + return Slot = New; } @@ -381,4 +470,11 @@ void InstrSelectorEmitter::run(std::ostream &OS) { // Instantiate any unresolved nonterminals with information from the context // that they are used in. InstantiateNonterminals(); + + + 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"; } diff --git a/utils/TableGen/InstrSelectorEmitter.h b/utils/TableGen/InstrSelectorEmitter.h index e8c8fad33f..0a8ca982fe 100644 --- a/utils/TableGen/InstrSelectorEmitter.h +++ b/utils/TableGen/InstrSelectorEmitter.h @@ -87,8 +87,16 @@ public: return Value; } + /// clone - Make a copy of this tree and all of its children. + /// + TreePatternNode *clone() const; + void dump() const; + /// InstantiateNonterminals - If this pattern refers to any nonterminals which + /// are not themselves completely resolved, clone the nonterminal and resolve + /// 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 @@ -145,6 +153,11 @@ public: Pattern(PatternType pty, DagInit *RawPat, Record *TheRec, InstrSelectorEmitter &ise); + /// Pattern - Constructor used for cloning nonterminal patterns + Pattern(TreePatternNode *tree, Record *rec, bool res, + InstrSelectorEmitter &ise) : PTy(Nonterminal), Tree(tree), Result(0), + TheRecord(rec), Resolved(res), ISE(ise){} + /// getPatternType - Return what flavor of Record this pattern originated from /// PatternType getPatternType() const { return PTy; } @@ -162,15 +175,30 @@ public: bool isResolved() const { return Resolved; } - /// InstantiateNonterminalsReferenced - If this pattern refers to any - /// nonterminals which are not themselves completely resolved, clone the - /// nonterminal and resolve it with the using context we provide. - void InstantiateNonterminalsReferenced(); + /// InferAllTypes - Runs the type inference engine on the current pattern, + /// stopping when nothing can be inferred, then updating the Resolved field. + void InferAllTypes(); + + /// InstantiateNonterminals - If this pattern refers to any nonterminals which + /// are not themselves completely resolved, clone the nonterminal and resolve + /// it with the using context we provide. + void InstantiateNonterminals() { + Tree->InstantiateNonterminals(ISE); + } + + /// clone - This method is used to make an exact copy of the current pattern, + /// then change the "TheRecord" instance variable to the specified record. + /// + Pattern *clone(Record *R) const; + + /// error - Throw an exception, prefixing it with information about this + /// pattern. + void error(const std::string &Msg) const; + private: MVT::ValueType getIntrinsicType(Record *R) const; TreePatternNode *ParseTreePattern(DagInit *DI); bool InferTypes(TreePatternNode *N, bool &MadeChange); - void error(const std::string &Msg) const; }; std::ostream &operator<<(std::ostream &OS, const Pattern &P); @@ -189,6 +217,11 @@ class InstrSelectorEmitter : public TableGenBackend { /// Patterns - a list of all of the patterns defined by the target description /// std::map Patterns; + + /// InstantiatedNTs - A data structure to keep track of which nonterminals + /// have been instantiated already... + /// + std::map, Record*> InstantiatedNTs; public: InstrSelectorEmitter(RecordKeeper &R) : Records(R) {} @@ -209,6 +242,14 @@ public: /// nonterminal, but only if it hasn't been read in already. Pattern *ReadNonterminal(Record *R); + /// InstantiateNonterminal - This method takes the nonterminal specified by + /// NT, which should not be completely resolved, clones it, applies ResultTy + /// to its root, then runs the type inference stuff on it. This should + /// produce a newly resolved nonterminal, which we make a record for and + /// return. To be extra fancy and efficient, this only makes one clone for + /// each type it is instantiated with. + Record *InstantiateNonterminal(Pattern *NT, MVT::ValueType ResultTy); + private: // ReadNodeTypes - Read in all of the node types in the current RecordKeeper, // turning them into the more accessible NodeTypes data structure. -- cgit v1.2.3