X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=utils%2FTableGen%2FDAGISelEmitter.h;h=8ed66be800a214826ccfb320c3ab92b54c5c6ae5;hb=8c06318821e4febb3a7f1afbab72dae362f1bf5f;hp=d16052286791ab939f5593cba7b1e87502104c2f;hpb=24eeeb8c3e80e22cb2fd311580ae22b5e3ae7b51;p=oota-llvm.git diff --git a/utils/TableGen/DAGISelEmitter.h b/utils/TableGen/DAGISelEmitter.h index d1605228679..8ed66be800a 100644 --- a/utils/TableGen/DAGISelEmitter.h +++ b/utils/TableGen/DAGISelEmitter.h @@ -16,15 +16,29 @@ #include "TableGenBackend.h" #include "CodeGenTarget.h" +#include "CodeGenIntrinsics.h" +#include namespace llvm { class Record; 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. @@ -33,7 +47,8 @@ namespace llvm { unsigned OperandNo; // The operand # this constraint applies to. enum { - SDTCisVT, SDTCisInt, SDTCisFP, SDTCisSameAs, SDTCisVTSmallerThanOp + SDTCisVT, SDTCisPtrTy, SDTCisInt, SDTCisFP, SDTCisSameAs, + SDTCisVTSmallerThanOp, SDTCisOpSmallerThanOp, SDTCisIntVectorOfSameSize } ConstraintType; union { // The discriminated union. @@ -46,6 +61,12 @@ namespace llvm { 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 @@ -68,6 +89,7 @@ namespace llvm { Record *Def; std::string EnumName; std::string SDClassName; + unsigned Properties; unsigned NumResults; int NumOperands; std::vector TypeConstraints; @@ -83,6 +105,14 @@ namespace llvm { 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 @@ -100,10 +130,10 @@ namespace llvm { /// 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; @@ -122,23 +152,39 @@ namespace llvm { /// TransformFn - The transformation function to execute on this node before /// it can be substituted into the resulting instruction on a pattern match. - std::string TransformFn; + 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; } - bool hasTypeSet() const { return Ty != MVT::LAST_VALUETYPE; } - 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; } @@ -149,11 +195,12 @@ namespace llvm { Children[i] = N; } + const std::string &getPredicateFn() const { return PredicateFn; } void setPredicateFn(const std::string &Fn) { PredicateFn = Fn; } - const std::string &getTransformFn() const { return TransformFn; } - void setTransformFn(const std::string &Fn) { TransformFn = Fn; } + Record *getTransformFn() const { return TransformFn; } + void setTransformFn(Record *Fn) { TransformFn = Fn; } void print(std::ostream &OS) const; void dump() const; @@ -164,6 +211,12 @@ 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 &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 (Ty == MVT::LAST_VALUETYPE) return true; + 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); }; @@ -217,12 +279,20 @@ 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(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); /// getTrees - Return the tree patterns which corresponds to this pattern. /// @@ -269,44 +339,183 @@ 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::vector Intrinsics; + std::map SDNodes; std::map > SDNodeXForms; + std::map ComplexPatterns; std::map PatternFragments; - std::vector Instructions; + std::map Instructions; + + // Specific SDNode definitions: + Record *intrinsic_void_sdnode; + Record *intrinsic_w_chain_sdnode, *intrinsic_wo_chain_sdnode; + + /// 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; + } + + const CodeGenIntrinsic &getIntrinsic(Record *R) const { + for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i) + if (Intrinsics[i].TheDef == R) return Intrinsics[i]; + assert(0 && "Unknown intrinsic!"); + abort(); + } + + const CodeGenIntrinsic &getIntrinsicInfo(unsigned IID) const { + assert(IID-1 < Intrinsics.size() && "Bad intrinsic ID!"); + return Intrinsics[IID-1]; + } + + unsigned getIntrinsicID(Record *R) const { + for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i) + if (Intrinsics[i].TheDef == R) return i; + assert(0 && "Unknown intrinsic!"); + abort(); + } + 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; + } + + Record *get_intrinsic_void_sdnode() const { + return intrinsic_void_sdnode; + } + Record *get_intrinsic_w_chain_sdnode() const { + return intrinsic_w_chain_sdnode; + } + Record *get_intrinsic_wo_chain_sdnode() const { + return intrinsic_wo_chain_sdnode; + } + + private: void ParseNodeInfo(); void ParseNodeTransforms(std::ostream &OS); - void ParseAndResolvePatternFragments(std::ostream &OS); - void ParseAndResolveInstructions(); + 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); };