From f8e9683a330afcdc31fd177283f8e0aea6c52b9c Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Thu, 7 Aug 2003 19:12:24 +0000 Subject: Continued evolution of the selector emitter: Represent instruction patterns as first class objects git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7677 91177308-0d34-0410-b5e6-96231b3b80d8 --- support/tools/TableGen/InstrSelectorEmitter.cpp | 141 ++++++++++++++++-------- support/tools/TableGen/InstrSelectorEmitter.h | 112 ++++++++++++++++--- 2 files changed, 189 insertions(+), 64 deletions(-) (limited to 'support/tools') diff --git a/support/tools/TableGen/InstrSelectorEmitter.cpp b/support/tools/TableGen/InstrSelectorEmitter.cpp index dbc1b66ffc..cf3fa68cb7 100644 --- a/support/tools/TableGen/InstrSelectorEmitter.cpp +++ b/support/tools/TableGen/InstrSelectorEmitter.cpp @@ -93,12 +93,60 @@ static MVT::ValueType getIntrinsicType(Record *R) { // Parse the specified DagInit into a TreePattern which we can use. // -TreePatternNode *InstrSelectorEmitter::ParseTreePattern(DagInit *DI, - const std::string &RecName) { +Pattern::Pattern(PatternType pty, DagInit *RawPat, Record *TheRec, + InstrSelectorEmitter &ise) + : PTy(pty), TheRecord(TheRec), ISE(ise) { + + // First, parse the pattern... + Tree = ParseTreePattern(RawPat); + + bool MadeChange, AnyUnset; + do { + MadeChange = false; + AnyUnset = InferTypes(Tree, MadeChange); + } while ((AnyUnset || MadeChange) && !(AnyUnset && !MadeChange)); + + if (PTy == Instruction) { + // Check to make sure there is not any unset types in the tree pattern... + if (AnyUnset) { + std::cerr << "In instruction pattern: " << *Tree << "\n"; + error("Could not infer all types!"); + } + + // Check to see if we have a top-level (set) of a register. + if (Tree->getOperator()->getName() == "set") { + 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(); + Tree = Tree->getChild(1); + + } + } + + Resolved = !AnyUnset; +} + +void Pattern::error(const std::string &Msg) { + std::string M = "In "; + switch (PTy) { + case Nonterminal: M += "nonterminal "; break; + case Instruction: M += "instruction "; break; + case Expander : M += "expander "; break; + } + throw M + TheRecord->getName() + ": " + Msg; +} + + +TreePatternNode *Pattern::ParseTreePattern(DagInit *DI) { Record *Operator = DI->getNodeType(); - if (!NodeTypes.count(Operator)) - throw "Illegal node for instruction pattern: '" + Operator->getName() +"'!"; + if (!ISE.getNodeTypes().count(Operator)) + error("Unrecognized node '" + Operator->getName() + "'!"); const std::vector &Args = DI->getArgs(); std::vector Children; @@ -106,14 +154,14 @@ TreePatternNode *InstrSelectorEmitter::ParseTreePattern(DagInit *DI, for (unsigned i = 0, e = Args.size(); i != e; ++i) { Init *Arg = Args[i]; if (DagInit *DI = dynamic_cast(Arg)) { - Children.push_back(ParseTreePattern(DI, RecName)); + Children.push_back(ParseTreePattern(DI)); } else if (DefInit *DI = dynamic_cast(Arg)) { Children.push_back(new TreePatternNode(DI)); // If it's a regclass or something else known, set the type. Children.back()->setType(getIntrinsicType(DI->getDef())); } else { Arg->dump(); - throw "Unknown value for tree pattern in '" + RecName + "'!"; + error("Unknown leaf value for tree pattern!"); } } @@ -138,37 +186,36 @@ static bool UpdateNodeType(TreePatternNode *N, MVT::ValueType VT, // InferTypes - Perform type inference on the tree, returning true if there // are any remaining untyped nodes and setting MadeChange if any changes were // made. -bool InstrSelectorEmitter::InferTypes(TreePatternNode *N, - const std::string &RecName, - bool &MadeChange) { +bool Pattern::InferTypes(TreePatternNode *N, bool &MadeChange) { if (N->isLeaf()) return N->getType() == MVT::Other; bool AnyUnset = false; Record *Operator = N->getOperator(); - assert(NodeTypes.count(Operator) && "No node info for node!"); - const NodeType &NT = NodeTypes[Operator]; + assert(ISE.getNodeTypes().count(Operator) && "No node info for node!"); + const NodeType &NT = ISE.getNodeTypes()[Operator]; // Check to see if we can infer anything about the argument types from the // return types... const std::vector &Children = N->getChildren(); if (Children.size() != NT.ArgTypes.size()) - throw "In record " + RecName + " incorrect number of children for " + - Operator->getName() + " node!"; + error("Incorrect number of children for " + Operator->getName() + " node!"); for (unsigned i = 0, e = Children.size(); i != e; ++i) { - AnyUnset |= InferTypes(Children[i], RecName, MadeChange); - + AnyUnset |= InferTypes(Children[i], MadeChange); switch (NT.ArgTypes[i]) { case NodeType::Arg0: - MadeChange |= UpdateNodeType(Children[i], Children[0]->getType(),RecName); + MadeChange |= UpdateNodeType(Children[i], Children[0]->getType(), + TheRecord->getName()); break; case NodeType::Val: if (Children[i]->getType() == MVT::isVoid) - throw "In pattern for " + RecName + " should not get a void node!"; + error("Inferred a void node in an illegal place!"); break; case NodeType::Ptr: - MadeChange |= UpdateNodeType(Children[i],Target.getPointerType(),RecName); + MadeChange |= UpdateNodeType(Children[i], + ISE.getTarget().getPointerType(), + TheRecord->getName()); break; default: assert(0 && "Invalid argument ArgType!"); } @@ -177,18 +224,20 @@ bool InstrSelectorEmitter::InferTypes(TreePatternNode *N, // See if we can infer anything about the return type now... switch (NT.ResultType) { case NodeType::Void: - MadeChange |= UpdateNodeType(N, MVT::isVoid, RecName); + MadeChange |= UpdateNodeType(N, MVT::isVoid, TheRecord->getName()); break; case NodeType::Arg0: - MadeChange |= UpdateNodeType(N, Children[0]->getType(), RecName); + MadeChange |= UpdateNodeType(N, Children[0]->getType(), + TheRecord->getName()); break; case NodeType::Ptr: - MadeChange |= UpdateNodeType(N, Target.getPointerType(), RecName); + MadeChange |= UpdateNodeType(N, ISE.getTarget().getPointerType(), + TheRecord->getName()); break; case NodeType::Val: if (N->getType() == MVT::isVoid) - throw "In pattern for " + RecName + " should not get a void node!"; + error("Inferred a void node in an illegal place!"); break; default: assert(0 && "Unhandled type constraint!"); @@ -198,39 +247,36 @@ bool InstrSelectorEmitter::InferTypes(TreePatternNode *N, return AnyUnset | N->getType() == MVT::Other; } +std::ostream &operator<<(std::ostream &OS, const Pattern &P) { + switch (P.getPatternType()) { + case Pattern::Nonterminal: OS << "Nonterminal pattern "; break; + case Pattern::Instruction: OS << "Instruction pattern "; break; + case Pattern::Expander: OS << "Expander pattern "; break; + } -// ReadAndCheckPattern - Parse the specified DagInit into a pattern and then -// perform full type inference. -// -TreePatternNode *InstrSelectorEmitter::ReadAndCheckPattern(DagInit *DI, - const std::string &RecName) { - // First, parse the pattern... - TreePatternNode *Pattern = ParseTreePattern(DI, RecName); - - bool MadeChange, AnyUnset; - do { - MadeChange = false; - AnyUnset = InferTypes(Pattern, RecName, MadeChange); - if (AnyUnset && !MadeChange) { - std::cerr << "In pattern: " << *Pattern << "\n"; - throw "Cannot infer types for " + RecName; - } - } while (AnyUnset || MadeChange); + OS << P.getRecord()->getName() << ":\t"; - return Pattern; + if (Record *Result = P.getResult()) + OS << Result->getName() << " = "; + OS << *P.getTree(); + + if (!P.isResolved()) + OS << " [not completely resolved]"; + return OS; } + // ProcessNonTerminals - Read in all nonterminals and incorporate them into // our pattern database. -void InstrSelectorEmitter::ProcessNonTerminals() { +void InstrSelectorEmitter::ProcessNonterminals() { std::vector NTs = Records.getAllDerivedDefinitions("Nonterminal"); for (unsigned i = 0, e = NTs.size(); i != e; ++i) { DagInit *DI = NTs[i]->getValueAsDag("Pattern"); - TreePatternNode *Pattern = ReadAndCheckPattern(DI, NTs[i]->getName()); + Pattern *P = new Pattern(Pattern::Nonterminal, DI, NTs[i], *this); + - DEBUG(std::cerr << "Parsed nonterm pattern " << NTs[i]->getName() << "\t= " - << *Pattern << "\n"); + DEBUG(std::cerr << "Parsed " << *P << "\n"); } } @@ -243,10 +289,9 @@ void InstrSelectorEmitter::ProcessInstructionPatterns() { for (unsigned i = 0, e = Insts.size(); i != e; ++i) { Record *Inst = Insts[i]; if (DagInit *DI = dynamic_cast(Inst->getValueInit("Pattern"))) { - TreePatternNode *Pattern = ReadAndCheckPattern(DI, Inst->getName()); + Pattern *P = new Pattern(Pattern::Instruction, DI, Inst, *this); - DEBUG(std::cerr << "Parsed inst pattern " << Inst->getName() << "\t= " - << *Pattern << "\n"); + DEBUG(std::cerr << "Parsed " << *P << "\n"); } } } @@ -257,7 +302,7 @@ void InstrSelectorEmitter::run(std::ostream &OS) { ProcessNodeTypes(); // Read in all of the nonterminals... - //ProcessNonTerminals(); + ProcessNonterminals(); // Read all of the instruction patterns in... ProcessInstructionPatterns(); diff --git a/support/tools/TableGen/InstrSelectorEmitter.h b/support/tools/TableGen/InstrSelectorEmitter.h index 108aeee20c..b168e50686 100644 --- a/support/tools/TableGen/InstrSelectorEmitter.h +++ b/support/tools/TableGen/InstrSelectorEmitter.h @@ -14,7 +14,10 @@ #include class DagInit; class Init; +class InstrSelectorEmitter; +/// NodeType - Represents Information parsed from the DagNode entries. +/// struct NodeType { enum ArgResultTypes { // Both argument and return types... @@ -39,12 +42,17 @@ struct NodeType { static ArgResultTypes Translate(Record *R); }; + + +/// TreePatternNode - Represent a node of the tree patterns. +/// class TreePatternNode { /// Operator - The operation that this node represents... this is null if this /// is a leaf. Record *Operator; /// Type - The inferred value type... + /// MVT::ValueType Type; /// Children - If this is not a leaf (Operator != 0), this is the subtrees @@ -52,6 +60,7 @@ class TreePatternNode { std::vector Children; /// Value - If this node is a leaf, this indicates what the thing is. + /// Init *Value; public: TreePatternNode(Record *o, const std::vector &c) @@ -68,6 +77,11 @@ public: assert(Operator != 0 && "This is a leaf node!"); return Children; } + TreePatternNode *getChild(unsigned c) const { + assert(c < Children.size() && "Child access out of range!"); + return getChildren()[c]; + } + Init *getValue() const { assert(Operator == 0 && "This is not a leaf node!"); return Value; @@ -80,17 +94,98 @@ std::ostream &operator<<(std::ostream &OS, const TreePatternNode &N); +/// Pattern - Represent a pattern of one form or another. Currently, three +/// types of patterns are possible: Instruction's, Nonterminals, and Expanders. +/// +struct Pattern { + enum PatternType { + Nonterminal, Instruction, Expander + }; +private: + /// PTy - The type of pattern this is. + /// + PatternType PTy; + + /// Tree - The tree pattern which corresponds to this pattern. Note that if + /// there was a (set) node on the outside level that it has been stripped off. + /// + TreePatternNode *Tree; + + /// Result - If this is an instruction or expander pattern, this is the + /// register result, specified with a (set) in the pattern. + /// + Record *Result; + + /// TheRecord - The actual TableGen record corresponding to this pattern. + /// + Record *TheRecord; + + /// Resolved - This is true of the pattern is useful in practice. In + /// particular, some non-terminals will have non-resolvable types. When a + /// user of the non-terminal is later found, they will have inferred a type + /// for the result of the non-terminal, which cause a clone of an unresolved + /// nonterminal to be made which is "resolved". + /// + bool Resolved; + + /// ISE - the instruction selector emitter coordinating this madness. + /// + InstrSelectorEmitter &ISE; +public: + + /// Pattern constructor - Parse the specified DagInitializer into the current + /// record. + Pattern(PatternType pty, DagInit *RawPat, Record *TheRec, + InstrSelectorEmitter &ise); + + /// getPatternType - Return what flavor of Record this pattern originated from + /// + PatternType getPatternType() const { return PTy; } + + /// getTree - Return the tree pattern which corresponds to this pattern. + /// + TreePatternNode *getTree() const { return Tree; } + + Record *getResult() const { return Result; } + + /// getRecord - Return the actual TableGen record corresponding to this + /// pattern. + /// + Record *getRecord() const { return TheRecord; } + + bool isResolved() const { return Resolved; } + +private: + TreePatternNode *ParseTreePattern(DagInit *DI); + bool InferTypes(TreePatternNode *N, bool &MadeChange); + void error(const std::string &Msg); +}; + +std::ostream &operator<<(std::ostream &OS, const Pattern &P); + + + +/// InstrSelectorEmitter - The top-level class which coordinates construction +/// and emission of the instruction selector. +/// class InstrSelectorEmitter : public TableGenBackend { RecordKeeper &Records; CodeGenTarget Target; std::map NodeTypes; + + /// Patterns - a list of all of the patterns defined by the target description + /// + std::map Patterns; public: InstrSelectorEmitter(RecordKeeper &R) : Records(R) {} // run - Output the instruction set description, returning true on failure. void run(std::ostream &OS); + const CodeGenTarget &getTarget() const { return Target; } + std::map &getNodeTypes() { return NodeTypes; } + private: // ProcessNodeTypes - Process all of the node types in the current // RecordKeeper, turning them into the more accessible NodeTypes data @@ -99,26 +194,11 @@ private: // ProcessNonTerminals - Read in all nonterminals and incorporate them into // our pattern database. - void ProcessNonTerminals(); + void ProcessNonterminals(); // ProcessInstructionPatterns - Read in all subclasses of Instruction, and // process those with a useful Pattern field. void ProcessInstructionPatterns(); - - // ParseTreePattern - Parse the specified DagInit into a TreePattern which we - // can use. - // - TreePatternNode *ParseTreePattern(DagInit *DI, const std::string &RecName); - - // InferTypes - Perform type inference on the tree, returning true if there - // are any remaining untyped nodes and setting MadeChange if any changes were - // made. - bool InferTypes(TreePatternNode *N, const std::string &RecName, - bool &MadeChange); - - // ReadAndCheckPattern - Parse the specified DagInit into a pattern and then - // perform full type inference. - TreePatternNode *ReadAndCheckPattern(DagInit *DI, const std::string &RecName); }; #endif -- cgit v1.2.3