X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=utils%2FTableGen%2FDAGISelEmitter.h;h=35606f7787c2319387600a7c75d20fb19ca87983;hb=2ca956f8dede03c23f6b497395cd3b99ebd1eb8a;hp=20ead35a79d432b1f811f063b2e4fc6ca3030d8a;hpb=ca559d0654d55355852b72eea812b6bb39df15a5;p=oota-llvm.git diff --git a/utils/TableGen/DAGISelEmitter.h b/utils/TableGen/DAGISelEmitter.h index 20ead35a79d..35606f7787c 100644 --- a/utils/TableGen/DAGISelEmitter.h +++ b/utils/TableGen/DAGISelEmitter.h @@ -16,13 +16,70 @@ #include "TableGenBackend.h" #include "CodeGenTarget.h" +#include namespace llvm { class Record; - class Init; + struct Init; + class ListInit; class DagInit; + class SDNodeInfo; class TreePattern; + class TreePatternNode; class DAGISelEmitter; + class ComplexPattern; + + /// MVT::DAGISelGenValueType - These are some extended forms of MVT::ValueType + /// that we use as lattice values during type inferrence. + namespace MVT { + enum DAGISelGenValueType { + isFP = MVT::LAST_VALUETYPE, + isInt, + isUnknown + }; + } + + /// SDTypeConstraint - This is a discriminated union of constraints, + /// corresponding to the SDTypeConstraint tablegen class in Target.td. + struct SDTypeConstraint { + SDTypeConstraint(Record *R); + + unsigned OperandNo; // The operand # this constraint applies to. + enum { + SDTCisVT, SDTCisPtrTy, SDTCisInt, SDTCisFP, SDTCisSameAs, + SDTCisVTSmallerThanOp, SDTCisOpSmallerThanOp, SDTCisIntVectorOfSameSize + } ConstraintType; + + union { // The discriminated union. + struct { + MVT::ValueType VT; + } SDTCisVT_Info; + struct { + unsigned OtherOperandNum; + } SDTCisSameAs_Info; + struct { + unsigned OtherOperandNum; + } SDTCisVTSmallerThanOp_Info; + struct { + unsigned BigOperandNum; + } SDTCisOpSmallerThanOp_Info; + struct { + unsigned OtherOperandNum; + } SDTCisIntVectorOfSameSize_Info; + } x; + + /// ApplyTypeConstraint - Given a node in a pattern, apply this type + /// constraint to the nodes operands. This returns true if it makes a + /// change, false otherwise. If a type contradiction is found, throw an + /// exception. + bool ApplyTypeConstraint(TreePatternNode *N, const SDNodeInfo &NodeInfo, + TreePattern &TP) const; + + /// getOperandNum - Return the node corresponding to operand #OpNo in tree + /// N, which has NumResults results. + TreePatternNode *getOperandNum(unsigned OpNo, TreePatternNode *N, + unsigned NumResults) const; + }; /// SDNodeInfo - One of these records is created for each SDNode instance in /// the target .td file. This represents the various dag nodes we will be @@ -31,22 +88,51 @@ namespace llvm { Record *Def; std::string EnumName; std::string SDClassName; + unsigned Properties; + unsigned NumResults; + int NumOperands; + std::vector TypeConstraints; public: SDNodeInfo(Record *R); // Parse the specified record. + unsigned getNumResults() const { return NumResults; } + int getNumOperands() const { return NumOperands; } Record *getRecord() const { return Def; } const std::string &getEnumName() const { return EnumName; } const std::string &getSDClassName() const { return SDClassName; } + + const std::vector &getTypeConstraints() const { + return TypeConstraints; + } + + // SelectionDAG node properties. + enum SDNP { SDNPCommutative, SDNPAssociative, SDNPHasChain, + SDNPOutFlag, SDNPInFlag, SDNPOptInFlag }; + + /// hasProperty - Return true if this node has the specified property. + /// + bool hasProperty(enum SDNP Prop) const { return Properties & (1 << Prop); } + + /// ApplyTypeConstraints - Given a node in a pattern, apply the type + /// constraints for this node to the operands of the node. This returns + /// true if it makes a change, false otherwise. If a type contradiction is + /// found, throw an exception. + bool ApplyTypeConstraints(TreePatternNode *N, TreePattern &TP) const { + bool MadeChange = false; + for (unsigned i = 0, e = TypeConstraints.size(); i != e; ++i) + MadeChange |= TypeConstraints[i].ApplyTypeConstraint(N, *this, TP); + return MadeChange; + } }; /// FIXME: TreePatternNode's can be shared in some cases (due to dag-shaped /// patterns), and as such should be ref counted. We currently just leak all /// TreePatternNode objects! class TreePatternNode { - /// The inferred type for this node, or MVT::LAST_VALUETYPE if it hasn't + /// The inferred type for this node, or MVT::isUnknown if it hasn't /// been determined yet. - MVT::ValueType Ty; - + std::vector Types; + /// Operator - The Record for the operator if this is an interior node (not /// a leaf). Record *Operator; @@ -63,20 +149,41 @@ namespace llvm { /// for a match. If this string is empty, no predicate is involved. std::string PredicateFn; + /// TransformFn - The transformation function to execute on this node before + /// it can be substituted into the resulting instruction on a pattern match. + Record *TransformFn; + std::vector Children; public: TreePatternNode(Record *Op, const std::vector &Ch) - : Ty(MVT::LAST_VALUETYPE), Operator(Op), Val(0), Children(Ch) {} + : Types(), Operator(Op), Val(0), TransformFn(0), + Children(Ch) { Types.push_back(MVT::isUnknown); } TreePatternNode(Init *val) // leaf ctor - : Ty(MVT::LAST_VALUETYPE), Operator(0), Val(val) {} + : Types(), Operator(0), Val(val), TransformFn(0) { + Types.push_back(MVT::isUnknown); + } ~TreePatternNode(); const std::string &getName() const { return Name; } void setName(const std::string &N) { Name = N; } bool isLeaf() const { return Val != 0; } - MVT::ValueType getType() const { return Ty; } - void setType(MVT::ValueType VT) { Ty = VT; } + bool hasTypeSet() const { return Types[0] < MVT::LAST_VALUETYPE; } + bool isTypeCompletelyUnknown() const { + return Types[0] == MVT::isUnknown; + } + MVT::ValueType getTypeNum(unsigned Num) const { + assert(hasTypeSet() && "Doesn't have a type yet!"); + assert(Types.size() > Num && "Type num out of range!"); + return (MVT::ValueType)Types[Num]; + } + unsigned char getExtTypeNum(unsigned Num) const { + assert(Types.size() > Num && "Extended type num out of range!"); + return Types[Num]; + } + const std::vector &getExtTypes() const { return Types; } + void setTypes(const std::vector &T) { Types = T; } + void removeTypes() { Types = std::vector(1,MVT::isUnknown); } Init *getLeafValue() const { assert(isLeaf()); return Val; } Record *getOperator() const { assert(!isLeaf()); return Operator; } @@ -87,8 +194,12 @@ namespace llvm { Children[i] = N; } + const std::string &getPredicateFn() const { return PredicateFn; } void setPredicateFn(const std::string &Fn) { PredicateFn = Fn; } + + Record *getTransformFn() const { return TransformFn; } + void setTransformFn(Record *Fn) { TransformFn = Fn; } void print(std::ostream &OS) const; void dump() const; @@ -99,6 +210,14 @@ namespace llvm { /// TreePatternNode *clone() const; + /// isIsomorphicTo - Return true if this node is recursively isomorphic to + /// the specified node. For this comparison, all of the state of the node + /// is considered, except for the assigned name. Nodes with differing names + /// that are otherwise identical are considered isomorphic. + bool isIsomorphicTo(const TreePatternNode *N) const; + + /// SubstituteFormalArguments - Replace the formal arguments in this tree + /// with actual values specified by ArgMap. void SubstituteFormalArguments(std::map &ArgMap); @@ -106,23 +225,43 @@ namespace llvm { /// fragments, inline them into place, giving us a pattern without any /// PatFrag references. TreePatternNode *InlinePatternFragments(TreePattern &TP); - + + /// ApplyTypeConstraints - Apply all of the type constraints relevent to + /// this node and its children in the tree. This returns true if it makes a + /// change, false otherwise. If a type contradiction is found, throw an + /// exception. + bool ApplyTypeConstraints(TreePattern &TP, bool NotRegisters); + + /// 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(const std::vector &ExtVTs, + TreePattern &TP); + bool UpdateNodeType(unsigned char ExtVT, TreePattern &TP) { + std::vector ExtVTs(1, ExtVT); + return UpdateNodeType(ExtVTs, TP); + } + + /// ContainsUnresolvedType - Return true if this tree contains any + /// unresolved types. + bool ContainsUnresolvedType() const { + if (!hasTypeSet()) return true; + for (unsigned i = 0, e = getNumChildren(); i != e; ++i) + if (getChild(i)->ContainsUnresolvedType()) return true; + return false; + } + + /// canPatternMatch - If it is impossible for this pattern to match on this + /// target, fill in Reason and return false. Otherwise, return true. + bool canPatternMatch(std::string &Reason, DAGISelEmitter &ISE); }; - /// TreePattern - Represent a pattern of one form or another. Currently, two - /// types of patterns are possible: Instructions and PatFrags. + /// TreePattern - Represent a pattern, used for instructions, pattern + /// fragments, etc. /// class TreePattern { - public: - enum PatternType { - PatFrag, Instruction - }; - private: - /// PTy - The type of pattern this is. - /// - PatternType PTy; - /// Trees - The list of pattern trees which corresponds to this pattern. /// Note that PatFrag's only have a single tree. /// @@ -139,20 +278,30 @@ namespace llvm { /// ISE - the DAG isel emitter coordinating this madness. /// DAGISelEmitter &ISE; + + /// isInputPattern - True if this is an input pattern, something to match. + /// False if this is an output pattern, something to emit. + bool isInputPattern; public: /// TreePattern constructor - Parse the specified DagInits into the /// current record. - TreePattern(PatternType pty, Record *TheRec, - const std::vector &RawPat, DAGISelEmitter &ise); + TreePattern(Record *TheRec, ListInit *RawPat, bool isInput, + DAGISelEmitter &ise); + TreePattern(Record *TheRec, DagInit *Pat, bool isInput, + DAGISelEmitter &ise); + TreePattern(Record *TheRec, TreePatternNode *Pat, bool isInput, + DAGISelEmitter &ise); - /// getPatternType - Return what flavor of Record this pattern originated from - /// - PatternType getPatternType() const { return PTy; } - /// getTrees - Return the tree patterns which corresponds to this pattern. /// const std::vector &getTrees() const { return Trees; } + unsigned getNumTrees() const { return Trees.size(); } + TreePatternNode *getTree(unsigned i) const { return Trees[i]; } + TreePatternNode *getOnlyTree() const { + assert(Trees.size() == 1 && "Doesn't have exactly one pattern!"); + return Trees[0]; + } /// getRecord - Return the actual TableGen record corresponding to this /// pattern. @@ -164,6 +313,7 @@ namespace llvm { assert(i < Args.size() && "Argument reference out of range!"); return Args[i]; } + std::vector &getArgList() { return Args; } DAGISelEmitter &getDAGISelEmitter() const { return ISE; } @@ -175,6 +325,11 @@ namespace llvm { Trees[i] = Trees[i]->InlinePatternFragments(*this); } + /// InferAllTypes - Infer/propagate as many types throughout the expression + /// patterns as possible. Return true if all types are infered, false + /// otherwise. Throw an exception if a type contradiction is found. + bool InferAllTypes(); + /// error - Throw an exception, prefixing it with information about this /// pattern. void error(const std::string &Msg) const; @@ -183,42 +338,148 @@ namespace llvm { void dump() const; private: - MVT::ValueType getIntrinsicType(Record *R) const; TreePatternNode *ParseTreePattern(DagInit *DI); }; + + + class DAGInstruction { + TreePattern *Pattern; + std::vector Results; + std::vector Operands; + std::vector ImpResults; + std::vector ImpOperands; + TreePatternNode *ResultPattern; + public: + DAGInstruction(TreePattern *TP, + const std::vector &results, + const std::vector &operands, + const std::vector &impresults, + const std::vector &impoperands) + : Pattern(TP), Results(results), Operands(operands), + ImpResults(impresults), ImpOperands(impoperands), + ResultPattern(0) {} + + TreePattern *getPattern() const { return Pattern; } + unsigned getNumResults() const { return Results.size(); } + unsigned getNumOperands() const { return Operands.size(); } + unsigned getNumImpResults() const { return ImpResults.size(); } + unsigned getNumImpOperands() const { return ImpOperands.size(); } + + void setResultPattern(TreePatternNode *R) { ResultPattern = R; } + + Record *getResult(unsigned RN) const { + assert(RN < Results.size()); + return Results[RN]; + } + + Record *getOperand(unsigned ON) const { + assert(ON < Operands.size()); + return Operands[ON]; + } + + Record *getImpResult(unsigned RN) const { + assert(RN < ImpResults.size()); + return ImpResults[RN]; + } + + Record *getImpOperand(unsigned ON) const { + assert(ON < ImpOperands.size()); + return ImpOperands[ON]; + } + + TreePatternNode *getResultPattern() const { return ResultPattern; } + }; - - -/// InstrSelectorEmitter - The top-level class which coordinates construction +/// PatternToMatch - Used by DAGISelEmitter to keep tab of patterns processed +/// to produce isel. +struct PatternToMatch { + PatternToMatch(ListInit *preds, TreePatternNode *src, TreePatternNode *dst): + Predicates(preds), SrcPattern(src), DstPattern(dst) {}; + + ListInit *Predicates; // Top level predicate conditions to match. + TreePatternNode *SrcPattern; // Source pattern to match. + TreePatternNode *DstPattern; // Resulting pattern. + + ListInit *getPredicates() const { return Predicates; } + TreePatternNode *getSrcPattern() const { return SrcPattern; } + TreePatternNode *getDstPattern() const { return DstPattern; } +}; + +/// DAGISelEmitter - The top-level class which coordinates construction /// and emission of the instruction selector. /// class DAGISelEmitter : public TableGenBackend { +private: RecordKeeper &Records; CodeGenTarget Target; - + std::map SDNodes; + std::map > SDNodeXForms; + std::map ComplexPatterns; std::map PatternFragments; - std::vector Instructions; + std::map Instructions; + + /// PatternsToMatch - All of the things we are matching on the DAG. The first + /// value is the pattern to match, the second pattern is the result to + /// emit. + std::vector PatternsToMatch; public: DAGISelEmitter(RecordKeeper &R) : Records(R) {} // run - Output the isel, returning true on failure. void run(std::ostream &OS); + const CodeGenTarget &getTargetInfo() const { return Target; } + + Record *getSDNodeNamed(const std::string &Name) const; + const SDNodeInfo &getSDNodeInfo(Record *R) const { assert(SDNodes.count(R) && "Unknown node!"); return SDNodes.find(R)->second; } + const std::pair &getSDNodeTransform(Record *R) const { + assert(SDNodeXForms.count(R) && "Invalid transform!"); + return SDNodeXForms.find(R)->second; + } + + const ComplexPattern &getComplexPattern(Record *R) const { + assert(ComplexPatterns.count(R) && "Unknown addressing mode!"); + return ComplexPatterns.find(R)->second; + } + TreePattern *getPatternFragment(Record *R) const { assert(PatternFragments.count(R) && "Invalid pattern fragment request!"); return PatternFragments.find(R)->second; } + const DAGInstruction &getInstruction(Record *R) const { + assert(Instructions.count(R) && "Unknown instruction!"); + return Instructions.find(R)->second; + } + private: void ParseNodeInfo(); - void ParseAndResolvePatternFragments(std::ostream &OS); - void ParseAndResolveInstructions(); + void ParseNodeTransforms(std::ostream &OS); + void ParseComplexPatterns(); + void ParsePatternFragments(std::ostream &OS); + void ParseInstructions(); + void ParsePatterns(); + void GenerateVariants(); + void FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, + std::map &InstInputs, + std::map &InstResults, + std::vector &InstImpInputs, + std::vector &InstImpResults); + void GenerateCodeForPattern(PatternToMatch &Pattern, + std::vector > &GeneratedCode, + std::set > &GeneratedDecl, + bool UseGoto); + void EmitPatterns(std::vector > > > &Patterns, + unsigned Indent, std::ostream &OS); void EmitInstructionSelector(std::ostream &OS); };