X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=utils%2FTableGen%2FCodeGenDAGPatterns.h;h=34fdb595c3944970c764292f4fca58bcbcffa813;hb=d7349194650386d97a1d779369cb46f20ba9f252;hp=4434cf0c1c152c920b611661a92a192fd26153f0;hpb=e3b3a7241c01f26613694e53b26b01abf764ddfc;p=oota-llvm.git diff --git a/utils/TableGen/CodeGenDAGPatterns.h b/utils/TableGen/CodeGenDAGPatterns.h index 4434cf0c1c1..34fdb595c39 100644 --- a/utils/TableGen/CodeGenDAGPatterns.h +++ b/utils/TableGen/CodeGenDAGPatterns.h @@ -15,10 +15,14 @@ #ifndef CODEGEN_DAGPATTERNS_H #define CODEGEN_DAGPATTERNS_H -#include - #include "CodeGenTarget.h" #include "CodeGenIntrinsics.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringMap.h" +#include +#include +#include +#include namespace llvm { class Record; @@ -31,22 +35,113 @@ namespace llvm { class CodeGenDAGPatterns; class ComplexPattern; -/// EMVT::DAGISelGenValueType - These are some extended forms of +/// EEVT::DAGISelGenValueType - These are some extended forms of /// MVT::SimpleValueType that we use as lattice values during type inference. -namespace EMVT { - enum DAGISelGenValueType { - isFP = MVT::LAST_VALUETYPE, - isInt, - isUnknown - }; +/// The existing MVT iAny, fAny and vAny types suffice to represent +/// arbitrary integer, floating-point, and vector types, so only an unknown +/// value is needed. +namespace EEVT { + /// TypeSet - This is either empty if it's completely unknown, or holds a set + /// of types. It is used during type inference because register classes can + /// have multiple possible types and we don't know which one they get until + /// type inference is complete. + /// + /// TypeSet can have three states: + /// Vector is empty: The type is completely unknown, it can be any valid + /// target type. + /// Vector has multiple constrained types: (e.g. v4i32 + v4f32) it is one + /// of those types only. + /// Vector has one concrete type: The type is completely known. + /// + class TypeSet { + SmallVector TypeVec; + public: + TypeSet() {} + TypeSet(MVT::SimpleValueType VT, TreePattern &TP); + TypeSet(const std::vector &VTList); + + bool isCompletelyUnknown() const { return TypeVec.empty(); } + + bool isConcrete() const { + if (TypeVec.size() != 1) return false; + unsigned char T = TypeVec[0]; (void)T; + assert(T < MVT::LAST_VALUETYPE || T == MVT::iPTR || T == MVT::iPTRAny); + return true; + } + + MVT::SimpleValueType getConcrete() const { + assert(isConcrete() && "Type isn't concrete yet"); + return (MVT::SimpleValueType)TypeVec[0]; + } + + bool isDynamicallyResolved() const { + return getConcrete() == MVT::iPTR || getConcrete() == MVT::iPTRAny; + } + + const SmallVectorImpl &getTypeList() const { + assert(!TypeVec.empty() && "Not a type list!"); + return TypeVec; + } + + bool isVoid() const { + return TypeVec.size() == 1 && TypeVec[0] == MVT::isVoid; + } + + /// hasIntegerTypes - Return true if this TypeSet contains any integer value + /// types. + bool hasIntegerTypes() const; + + /// hasFloatingPointTypes - Return true if this TypeSet contains an fAny or + /// a floating point value type. + bool hasFloatingPointTypes() const; + + /// hasVectorTypes - Return true if this TypeSet contains a vector value + /// type. + bool hasVectorTypes() const; + + /// getName() - Return this TypeSet as a string. + std::string getName() const; + + /// MergeInTypeInfo - This merges in type information from the specified + /// argument. If 'this' changes, it returns true. If the two types are + /// contradictory (e.g. merge f32 into i32) then this throws an exception. + bool MergeInTypeInfo(const EEVT::TypeSet &InVT, TreePattern &TP); + + bool MergeInTypeInfo(MVT::SimpleValueType InVT, TreePattern &TP) { + return MergeInTypeInfo(EEVT::TypeSet(InVT, TP), TP); + } + + /// Force this type list to only contain integer types. + bool EnforceInteger(TreePattern &TP); - /// isExtIntegerVT - Return true if the specified extended value type vector - /// contains isInt or an integer value type. - bool isExtIntegerInVTs(const std::vector &EVTs); + /// Force this type list to only contain floating point types. + bool EnforceFloatingPoint(TreePattern &TP); - /// isExtFloatingPointVT - Return true if the specified extended value type - /// vector contains isFP or a FP value type. - bool isExtFloatingPointInVTs(const std::vector &EVTs); + /// EnforceScalar - Remove all vector types from this type list. + bool EnforceScalar(TreePattern &TP); + + /// EnforceVector - Remove all non-vector types from this type list. + bool EnforceVector(TreePattern &TP); + + /// EnforceSmallerThan - 'this' must be a smaller VT than Other. Update + /// this an other based on this information. + bool EnforceSmallerThan(EEVT::TypeSet &Other, TreePattern &TP); + + /// EnforceVectorEltTypeIs - 'this' is now constrainted to be a vector type + /// whose element is VT. + bool EnforceVectorEltTypeIs(MVT::SimpleValueType VT, TreePattern &TP); + + bool operator!=(const TypeSet &RHS) const { return TypeVec != RHS.TypeVec; } + bool operator==(const TypeSet &RHS) const { return TypeVec == RHS.TypeVec; } + + private: + /// FillWithPossibleTypes - Set to all legal types and return true, only + /// valid on completely unknown type sets. If Pred is non-null, only MVTs + /// that pass the predicate are added. + bool FillWithPossibleTypes(TreePattern &TP, + bool (*Pred)(MVT::SimpleValueType) = 0, + const char *PredicateName = 0); + }; } /// Set type used to track multiply used variables in patterns @@ -59,14 +154,13 @@ struct SDTypeConstraint { unsigned OperandNo; // The operand # this constraint applies to. enum { - SDTCisVT, SDTCisPtrTy, SDTCisInt, SDTCisFP, SDTCisSameAs, - SDTCisVTSmallerThanOp, SDTCisOpSmallerThanOp, SDTCisIntVectorOfSameSize, - SDTCisEltOfVec + SDTCisVT, SDTCisPtrTy, SDTCisInt, SDTCisFP, SDTCisVec, SDTCisSameAs, + SDTCisVTSmallerThanOp, SDTCisOpSmallerThanOp, SDTCisEltOfVec } ConstraintType; union { // The discriminated union. struct { - unsigned char VT; + MVT::SimpleValueType VT; } SDTCisVT_Info; struct { unsigned OtherOperandNum; @@ -77,9 +171,6 @@ struct SDTypeConstraint { struct { unsigned BigOperandNum; } SDTCisOpSmallerThanOp_Info; - struct { - unsigned OtherOperandNum; - } SDTCisIntVectorOfSameSize_Info; struct { unsigned OtherOperandNum; } SDTCisEltOfVec_Info; @@ -122,6 +213,11 @@ public: return TypeConstraints; } + /// getKnownType - If the type constraints on this node imply a fixed type + /// (e.g. all stores return void, etc), then return it as an + /// MVT::SimpleValueType. Otherwise, return MVT::Other. + MVT::SimpleValueType getKnownType() const; + /// hasProperty - Return true if this node has the specified property. /// bool hasProperty(enum SDNP Prop) const { return Properties & (1 << Prop); } @@ -142,9 +238,10 @@ public: /// patterns), and as such should be ref counted. We currently just leak all /// TreePatternNode objects! class TreePatternNode { - /// The inferred type for this node, or EMVT::isUnknown if it hasn't - /// been determined yet. - std::vector Types; + /// The type of each node result. Before and during type inference, each + /// result may be a set of possible types. After (successful) type inference, + /// each is a single concrete type. + SmallVector Types; /// Operator - The Record for the operator if this is an interior node (not /// a leaf). @@ -158,9 +255,9 @@ class TreePatternNode { /// std::string Name; - /// PredicateFn - The predicate function to execute on this node to check - /// for a match. If this string is empty, no predicate is involved. - std::string PredicateFn; + /// PredicateFns - The predicate functions to execute on this node to check + /// for a match. If this list is empty, no predicate is involved. + std::vector PredicateFns; /// TransformFn - The transformation function to execute on this node before /// it can be substituted into the resulting instruction on a pattern match. @@ -168,12 +265,14 @@ class TreePatternNode { std::vector Children; public: - TreePatternNode(Record *Op, const std::vector &Ch) - : Types(), Operator(Op), Val(0), TransformFn(0), - Children(Ch) { Types.push_back(EMVT::isUnknown); } - TreePatternNode(Init *val) // leaf ctor - : Types(), Operator(0), Val(val), TransformFn(0) { - Types.push_back(EMVT::isUnknown); + TreePatternNode(Record *Op, const std::vector &Ch, + unsigned NumResults) + : Operator(Op), Val(0), TransformFn(0), Children(Ch) { + Types.resize(NumResults); + } + TreePatternNode(Init *val, unsigned NumResults) // leaf ctor + : Operator(0), Val(val), TransformFn(0) { + Types.resize(NumResults); } ~TreePatternNode(); @@ -181,28 +280,26 @@ public: void setName(const std::string &N) { Name = N; } bool isLeaf() const { return Val != 0; } - bool hasTypeSet() const { - return (Types[0] < MVT::LAST_VALUETYPE) || (Types[0] == MVT::iPTR) || - (Types[0] == MVT::iPTRAny); - } - bool isTypeCompletelyUnknown() const { - return Types[0] == EMVT::isUnknown; + + // Type accessors. + unsigned getNumTypes() const { return Types.size(); } + MVT::SimpleValueType getType(unsigned ResNo) const { + return Types[ResNo].getConcrete(); } - bool isTypeDynamicallyResolved() const { - return (Types[0] == MVT::iPTR) || (Types[0] == MVT::iPTRAny); + const SmallVectorImpl &getExtTypes() const { return Types; } + const EEVT::TypeSet &getExtType(unsigned ResNo) const { return Types[ResNo]; } + EEVT::TypeSet &getExtType(unsigned ResNo) { return Types[ResNo]; } + void setType(unsigned ResNo, const EEVT::TypeSet &T) { Types[ResNo] = T; } + + bool hasTypeSet(unsigned ResNo) const { + return Types[ResNo].isConcrete(); } - MVT::SimpleValueType getTypeNum(unsigned Num) const { - assert(hasTypeSet() && "Doesn't have a type yet!"); - assert(Types.size() > Num && "Type num out of range!"); - return (MVT::SimpleValueType)Types[Num]; + bool isTypeCompletelyUnknown(unsigned ResNo) const { + return Types[ResNo].isCompletelyUnknown(); } - unsigned char getExtTypeNum(unsigned Num) const { - assert(Types.size() > Num && "Extended type num out of range!"); - return Types[Num]; + bool isTypeDynamicallyResolved(unsigned ResNo) const { + return Types[ResNo].isDynamicallyResolved(); } - const std::vector &getExtTypes() const { return Types; } - void setTypes(const std::vector &T) { Types = T; } - void removeTypes() { Types = std::vector(1, EMVT::isUnknown); } Init *getLeafValue() const { assert(isLeaf()); return Val; } Record *getOperator() const { assert(!isLeaf()); return Operator; } @@ -212,9 +309,26 @@ public: void setChild(unsigned i, TreePatternNode *N) { Children[i] = N; } + + /// hasChild - Return true if N is any of our children. + bool hasChild(const TreePatternNode *N) const { + for (unsigned i = 0, e = Children.size(); i != e; ++i) + if (Children[i] == N) return true; + return false; + } - const std::string &getPredicateFn() const { return PredicateFn; } - void setPredicateFn(const std::string &Fn) { PredicateFn = Fn; } + const std::vector &getPredicateFns() const {return PredicateFns;} + void clearPredicateFns() { PredicateFns.clear(); } + void setPredicateFns(const std::vector &Fns) { + assert(PredicateFns.empty() && "Overwriting non-empty predicate list!"); + PredicateFns = Fns; + } + void addPredicateFn(const std::string &Fn) { + assert(!Fn.empty() && "Empty predicate string!"); + if (std::find(PredicateFns.begin(), PredicateFns.end(), Fn) == + PredicateFns.end()) + PredicateFns.push_back(Fn); + } Record *getTransformFn() const { return TransformFn; } void setTransformFn(Record *Fn) { TransformFn = Fn; } @@ -223,11 +337,23 @@ public: /// CodeGenIntrinsic information for it, otherwise return a null pointer. const CodeGenIntrinsic *getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const; + /// getComplexPatternInfo - If this node corresponds to a ComplexPattern, + /// return the ComplexPattern information, otherwise return null. + const ComplexPattern * + getComplexPatternInfo(const CodeGenDAGPatterns &CGP) const; + + /// NodeHasProperty - Return true if this node has the specified property. + bool NodeHasProperty(SDNP Property, const CodeGenDAGPatterns &CGP) const; + + /// TreeHasProperty - Return true if any node in this tree has the specified + /// property. + bool TreeHasProperty(SDNP Property, const CodeGenDAGPatterns &CGP) const; + /// isCommutativeIntrinsic - Return true if the node is an intrinsic which is /// marked isCommutative. bool isCommutativeIntrinsic(const CodeGenDAGPatterns &CDP) const; - void print(std::ostream &OS) const; + void print(raw_ostream &OS) const; void dump() const; public: // Higher level manipulation routines. @@ -235,6 +361,9 @@ public: // Higher level manipulation routines. /// clone - Return a new copy of this tree. /// TreePatternNode *clone() const; + + /// RemoveAllTypes - Recursively strip all the types of this tree. + void RemoveAllTypes(); /// isIsomorphicTo - Return true if this node is recursively isomorphic to /// the specified node. For this comparison, all of the state of the node @@ -253,7 +382,7 @@ public: // Higher level manipulation routines. /// PatFrag references. TreePatternNode *InlinePatternFragments(TreePattern &TP); - /// ApplyTypeConstraints - Apply all of the type constraints relevent to + /// ApplyTypeConstraints - Apply all of the type constraints relevant 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. @@ -263,17 +392,22 @@ public: // Higher level manipulation routines. /// 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); + bool UpdateNodeType(unsigned ResNo, const EEVT::TypeSet &InTy, + TreePattern &TP) { + return Types[ResNo].MergeInTypeInfo(InTy, TP); + } + + bool UpdateNodeType(unsigned ResNo, MVT::SimpleValueType InTy, + TreePattern &TP) { + return Types[ResNo].MergeInTypeInfo(EEVT::TypeSet(InTy, TP), TP); } /// ContainsUnresolvedType - Return true if this tree contains any /// unresolved types. bool ContainsUnresolvedType() const { - if (!hasTypeSet() && !isTypeDynamicallyResolved()) return true; + for (unsigned i = 0, e = Types.size(); i != e; ++i) + if (!Types[i].isConcrete()) return true; + for (unsigned i = 0, e = getNumChildren(); i != e; ++i) if (getChild(i)->ContainsUnresolvedType()) return true; return false; @@ -284,6 +418,11 @@ public: // Higher level manipulation routines. bool canPatternMatch(std::string &Reason, const CodeGenDAGPatterns &CDP); }; +inline raw_ostream &operator<<(raw_ostream &OS, const TreePatternNode &TPN) { + TPN.print(OS); + return OS; +} + /// TreePattern - Represent a pattern, used for instructions, pattern /// fragments, etc. @@ -294,6 +433,10 @@ class TreePattern { /// std::vector Trees; + /// NamedNodes - This is all of the nodes that have names in the trees in this + /// pattern. + StringMap > NamedNodes; + /// TheRecord - The actual TableGen record corresponding to this pattern. /// Record *TheRecord; @@ -329,6 +472,12 @@ public: assert(Trees.size() == 1 && "Doesn't have exactly one pattern!"); return Trees[0]; } + + const StringMap > &getNamedNodesMap() { + if (NamedNodes.empty()) + ComputeNamedNodes(); + return NamedNodes; + } /// getRecord - Return the actual TableGen record corresponding to this /// pattern. @@ -353,19 +502,22 @@ public: } /// InferAllTypes - Infer/propagate as many types throughout the expression - /// patterns as possible. Return true if all types are infered, false + /// patterns as possible. Return true if all types are inferred, false /// otherwise. Throw an exception if a type contradiction is found. - bool InferAllTypes(); + bool InferAllTypes(const StringMap > + *NamedTypes=0); /// error - Throw an exception, prefixing it with information about this /// pattern. void error(const std::string &Msg) const; - void print(std::ostream &OS) const; + void print(raw_ostream &OS) const; void dump() const; private: TreePatternNode *ParseTreePattern(DagInit *DI); + void ComputeNamedNodes(); + void ComputeNamedNodes(TreePatternNode *N); }; /// DAGDefaultOperand - One of these is created for each PredicateOperand @@ -425,39 +577,48 @@ public: /// PatternToMatch - Used by CodeGenDAGPatterns to keep tab of patterns /// processed to produce isel. -struct PatternToMatch { +class PatternToMatch { +public: PatternToMatch(ListInit *preds, TreePatternNode *src, TreePatternNode *dst, const std::vector &dstregs, - unsigned complexity): - Predicates(preds), SrcPattern(src), DstPattern(dst), Dstregs(dstregs), - AddedComplexity(complexity) {}; + unsigned complexity, unsigned uid) + : Predicates(preds), SrcPattern(src), DstPattern(dst), + Dstregs(dstregs), AddedComplexity(complexity), ID(uid) {} ListInit *Predicates; // Top level predicate conditions to match. TreePatternNode *SrcPattern; // Source pattern to match. TreePatternNode *DstPattern; // Resulting pattern. std::vector Dstregs; // Physical register defs being matched. unsigned AddedComplexity; // Add to matching pattern complexity. + unsigned ID; // Unique ID for the record. ListInit *getPredicates() const { return Predicates; } TreePatternNode *getSrcPattern() const { return SrcPattern; } TreePatternNode *getDstPattern() const { return DstPattern; } const std::vector &getDstRegs() const { return Dstregs; } unsigned getAddedComplexity() const { return AddedComplexity; } + + std::string getPredicateCheck() const; }; +// Deterministic comparison of Record*. +struct RecordPtrCmp { + bool operator()(const Record *LHS, const Record *RHS) const; +}; class CodeGenDAGPatterns { RecordKeeper &Records; CodeGenTarget Target; std::vector Intrinsics; + std::vector TgtIntrinsics; - std::map SDNodes; - std::map > SDNodeXForms; - std::map ComplexPatterns; - std::map PatternFragments; - std::map DefaultOperands; - std::map Instructions; + std::map SDNodes; + std::map, RecordPtrCmp> SDNodeXForms; + std::map ComplexPatterns; + std::map PatternFragments; + std::map DefaultOperands; + std::map Instructions; // Specific SDNode definitions: Record *intrinsic_void_sdnode; @@ -488,7 +649,8 @@ public: return SDNodeXForms.find(R)->second; } - typedef std::map::const_iterator nx_iterator; + typedef std::map::const_iterator + nx_iterator; nx_iterator nx_begin() const { return SDNodeXForms.begin(); } nx_iterator nx_end() const { return SDNodeXForms.end(); } @@ -501,23 +663,31 @@ public: const CodeGenIntrinsic &getIntrinsic(Record *R) const { for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i) if (Intrinsics[i].TheDef == R) return Intrinsics[i]; + for (unsigned i = 0, e = TgtIntrinsics.size(); i != e; ++i) + if (TgtIntrinsics[i].TheDef == R) return TgtIntrinsics[i]; assert(0 && "Unknown intrinsic!"); abort(); } const CodeGenIntrinsic &getIntrinsicInfo(unsigned IID) const { - assert(IID-1 < Intrinsics.size() && "Bad intrinsic ID!"); - return Intrinsics[IID-1]; + if (IID-1 < Intrinsics.size()) + return Intrinsics[IID-1]; + if (IID-Intrinsics.size()-1 < TgtIntrinsics.size()) + return TgtIntrinsics[IID-Intrinsics.size()-1]; + assert(0 && "Bad intrinsic ID!"); + abort(); } unsigned getIntrinsicID(Record *R) const { for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i) if (Intrinsics[i].TheDef == R) return i; + for (unsigned i = 0, e = TgtIntrinsics.size(); i != e; ++i) + if (TgtIntrinsics[i].TheDef == R) return i + Intrinsics.size(); assert(0 && "Unknown intrinsic!"); abort(); } - const DAGDefaultOperand &getDefaultOperand(Record *R) { + const DAGDefaultOperand &getDefaultOperand(Record *R) const { assert(DefaultOperands.count(R) &&"Isn't an analyzed default operand!"); return DefaultOperands.find(R)->second; } @@ -527,7 +697,13 @@ public: assert(PatternFragments.count(R) && "Invalid pattern fragment request!"); return PatternFragments.find(R)->second; } - typedef std::map::const_iterator pf_iterator; + TreePattern *getPatternFragmentIfRead(Record *R) const { + if (!PatternFragments.count(R)) return 0; + return PatternFragments.find(R)->second; + } + + typedef std::map::const_iterator + pf_iterator; pf_iterator pf_begin() const { return PatternFragments.begin(); } pf_iterator pf_end() const { return PatternFragments.end(); } @@ -553,6 +729,8 @@ public: return intrinsic_wo_chain_sdnode; } + bool hasTargetIntrinsics() { return !TgtIntrinsics.empty(); } + private: void ParseNodeInfo(); void ParseNodeTransforms(); @@ -564,6 +742,7 @@ private: void InferInstructionFlags(); void GenerateVariants(); + void AddPatternToMatch(const TreePattern *Pattern, const PatternToMatch &PTM); void FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, std::map &InstInputs,