X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=utils%2FTableGen%2FCodeGenDAGPatterns.h;h=f330e558f56a7b9ed2d74524c1ad92ee47a71e8e;hb=d33bb62823b37dab31f996cfbe7a5b8563d85e9b;hp=9ce14dcc7b360501b7d25e29d2dcf22b0b984f3a;hpb=b706d29f9c5ed3ed9acc82f7ab46205ba56b92dc;p=oota-llvm.git diff --git a/utils/TableGen/CodeGenDAGPatterns.h b/utils/TableGen/CodeGenDAGPatterns.h index 9ce14dcc7b3..f330e558f56 100644 --- a/utils/TableGen/CodeGenDAGPatterns.h +++ b/utils/TableGen/CodeGenDAGPatterns.h @@ -12,19 +12,22 @@ // //===----------------------------------------------------------------------===// -#ifndef CODEGEN_DAGPATTERNS_H -#define CODEGEN_DAGPATTERNS_H +#ifndef LLVM_UTILS_TABLEGEN_CODEGENDAGPATTERNS_H +#define LLVM_UTILS_TABLEGEN_CODEGENDAGPATTERNS_H -#include +#include "CodeGenIntrinsics.h" +#include "CodeGenTarget.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringMap.h" +#include "llvm/Support/ErrorHandling.h" #include +#include +#include #include -#include "CodeGenTarget.h" -#include "CodeGenIntrinsics.h" - namespace llvm { class Record; - struct Init; + class Init; class ListInit; class DagInit; class SDNodeInfo; @@ -33,22 +36,129 @@ 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(ArrayRef 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; + + /// hasScalarTypes - Return true if this TypeSet contains a scalar value + /// type. + bool hasScalarTypes() 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 flags an error. + 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); + + /// Force this type list to only contain floating point types. + bool EnforceFloatingPoint(TreePattern &TP); + + /// 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 constrained to be a vector type + /// whose element is VT. + bool EnforceVectorEltTypeIs(EEVT::TypeSet &VT, TreePattern &TP); + + /// EnforceVectorEltTypeIs - 'this' is now constrained to be a vector type + /// whose element is VT. + bool EnforceVectorEltTypeIs(MVT::SimpleValueType VT, TreePattern &TP); + + /// EnforceVectorSubVectorTypeIs - 'this' is now constrained to + /// be a vector type VT. + bool EnforceVectorSubVectorTypeIs(EEVT::TypeSet &VT, TreePattern &TP); + + /// EnforceVectorSameNumElts - 'this' is now constrained to + /// be a vector with same num elements as VT. + bool EnforceVectorSameNumElts(EEVT::TypeSet &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) = nullptr, + const char *PredicateName = nullptr); }; - - /// isExtIntegerVT - Return true if the specified extended value type vector - /// contains isInt or an integer value type. - bool isExtIntegerInVTs(const std::vector &EVTs); - - /// isExtFloatingPointVT - Return true if the specified extended value type - /// vector contains isFP or a FP value type. - bool isExtFloatingPointInVTs(const std::vector &EVTs); } /// Set type used to track multiply used variables in patterns @@ -58,16 +168,17 @@ typedef std::set MultipleUseVarSet; /// 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, SDTCisEltOfVec + enum { + SDTCisVT, SDTCisPtrTy, SDTCisInt, SDTCisFP, SDTCisVec, SDTCisSameAs, + SDTCisVTSmallerThanOp, SDTCisOpSmallerThanOp, SDTCisEltOfVec, + SDTCisSubVecOfVec, SDTCVecEltisVT, SDTCisSameNumEltsAs } ConstraintType; - + union { // The discriminated union. struct { - unsigned char VT; + MVT::SimpleValueType VT; } SDTCisVT_Info; struct { unsigned OtherOperandNum; @@ -81,19 +192,23 @@ struct SDTypeConstraint { struct { unsigned OtherOperandNum; } SDTCisEltOfVec_Info; + struct { + unsigned OtherOperandNum; + } SDTCisSubVecOfVec_Info; + struct { + MVT::SimpleValueType VT; + } SDTCVecEltisVT_Info; + struct { + unsigned OtherOperandNum; + } SDTCisSameNumEltsAs_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. + /// change, false otherwise. If a type contradiction is found, an error + /// is flagged. 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 @@ -109,17 +224,25 @@ class SDNodeInfo { std::vector TypeConstraints; public: SDNodeInfo(Record *R); // Parse the specified record. - + unsigned getNumResults() const { return NumResults; } + + /// getNumOperands - This is the number of operands required or -1 if + /// variadic. 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; } - + + /// 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(unsigned ResNo) const; + /// hasProperty - Return true if this node has the specified property. /// bool hasProperty(enum SDNP Prop) const { return Properties & (1 << Prop); } @@ -127,7 +250,7 @@ public: /// 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. + /// found, an error is flagged. bool ApplyTypeConstraints(TreePatternNode *N, TreePattern &TP) const { bool MadeChange = false; for (unsigned i = 0, e = TypeConstraints.size(); i != e; ++i) @@ -135,91 +258,154 @@ public: return MadeChange; } }; + +/// TreePredicateFn - This is an abstraction that represents the predicates on +/// a PatFrag node. This is a simple one-word wrapper around a pointer to +/// provide nice accessors. +class TreePredicateFn { + /// PatFragRec - This is the TreePattern for the PatFrag that we + /// originally came from. + TreePattern *PatFragRec; +public: + /// TreePredicateFn constructor. Here 'N' is a subclass of PatFrag. + TreePredicateFn(TreePattern *N); + + + TreePattern *getOrigPatFragRecord() const { return PatFragRec; } + + /// isAlwaysTrue - Return true if this is a noop predicate. + bool isAlwaysTrue() const; + + bool isImmediatePattern() const { return !getImmCode().empty(); } + + /// getImmediatePredicateCode - Return the code that evaluates this pattern if + /// this is an immediate predicate. It is an error to call this on a + /// non-immediate pattern. + std::string getImmediatePredicateCode() const { + std::string Result = getImmCode(); + assert(!Result.empty() && "Isn't an immediate pattern!"); + return Result; + } + + + bool operator==(const TreePredicateFn &RHS) const { + return PatFragRec == RHS.PatFragRec; + } + + bool operator!=(const TreePredicateFn &RHS) const { return !(*this == RHS); } + + /// Return the name to use in the generated code to reference this, this is + /// "Predicate_foo" if from a pattern fragment "foo". + std::string getFnName() const; + + /// getCodeToRunOnSDNode - Return the code for the function body that + /// evaluates this predicate. The argument is expected to be in "Node", + /// not N. This handles casting and conversion to a concrete node type as + /// appropriate. + std::string getCodeToRunOnSDNode() const; + +private: + std::string getPredCode() const; + std::string getImmCode() const; +}; + /// 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 EMVT::isUnknown if it hasn't - /// been determined yet. This is a std::vector because during inference - /// there may be multiple possible types. - 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). Record *Operator; - + /// Val - The init value (e.g. the "GPRC" record, or "7") for a leaf. /// Init *Val; - + /// Name - The name given to this node with the :$foo notation. /// std::string Name; - + /// 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; - + 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. Record *TransformFn; - + 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(nullptr), TransformFn(nullptr), Children(Ch) { + Types.resize(NumResults); + } + TreePatternNode(Init *val, unsigned NumResults) // leaf ctor + : Operator(nullptr), Val(val), TransformFn(nullptr) { + Types.resize(NumResults); } ~TreePatternNode(); - + + bool hasName() const { return !Name.empty(); } 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 (Types[0] < MVT::LAST_VALUETYPE) || (Types[0] == MVT::iPTR) || - (Types[0] == MVT::iPTRAny); - } - bool isTypeCompletelyUnknown() const { - return Types[0] == EMVT::isUnknown; + void setName(StringRef N) { Name.assign(N.begin(), N.end()); } + + bool isLeaf() const { return Val != nullptr; } + + // 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; } - + unsigned getNumChildren() const { return Children.size(); } TreePatternNode *getChild(unsigned N) const { return Children[N]; } void setChild(unsigned i, TreePatternNode *N) { Children[i] = N; } - const std::vector &getPredicateFns() const { return PredicateFns; } + /// 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; + } + + bool hasAnyPredicate() const { return !PredicateFns.empty(); } + + const std::vector &getPredicateFns() const { + return PredicateFns; + } void clearPredicateFns() { PredicateFns.clear(); } - void setPredicateFns(const std::vector &Fns) { + 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!"); + void addPredicateFn(const TreePredicateFn &Fn) { + assert(!Fn.isAlwaysTrue() && "Empty predicate string!"); if (std::find(PredicateFns.begin(), PredicateFns.end(), Fn) == PredicateFns.end()) PredicateFns.push_back(Fn); @@ -227,31 +413,52 @@ public: Record *getTransformFn() const { return TransformFn; } void setTransformFn(Record *Fn) { TransformFn = Fn; } - + /// getIntrinsicInfo - If this node corresponds to an intrinsic, return the /// 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; + + /// Returns the number of MachineInstr operands that would be produced by this + /// node if it mapped directly to an output Instruction's + /// operand. ComplexPattern specifies this explicitly; MIOperandInfo gives it + /// for Operands; otherwise 1. + unsigned getNumMIResults(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. /// 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 /// is considered, except for the assigned name. Nodes with differing names /// that are otherwise identical are considered isomorphic. bool isIsomorphicTo(const TreePatternNode *N, const MultipleUseVarSet &DepVars) 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); + 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); + } + + // Update node type with types inferred from an instruction operand or result + // def from the ins/outs lists. + // Return true if the type changed. + bool UpdateNodeTypeFromInst(unsigned ResNo, Record *Operand, TreePattern &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; } - + /// 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, 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. @@ -302,15 +523,19 @@ class TreePattern { /// Note that PatFrag's only have a single tree. /// 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; - + /// Args - This is a list of all of the arguments to this pattern (for /// PatFrag patterns), which are the 'node' markers in this pattern. std::vector Args; - + /// CDP - the top-level object coordinating this madness. /// CodeGenDAGPatterns &CDP; @@ -318,8 +543,19 @@ class TreePattern { /// isInputPattern - True if this is an input pattern, something to match. /// False if this is an output pattern, something to emit. bool isInputPattern; + + /// hasError - True if the currently processed nodes have unresolvable types + /// or other non-fatal errors + bool HasError; + + /// It's important that the usage of operands in ComplexPatterns is + /// consistent: each named operand can be defined by at most one + /// ComplexPattern. This records the ComplexPattern instance and the operand + /// number for each operand encountered in a ComplexPattern to aid in that + /// check. + StringMap> ComplexPatternOperands; public: - + /// TreePattern constructor - Parse the specified DagInits into the /// current record. TreePattern(Record *TheRec, ListInit *RawPat, bool isInput, @@ -328,7 +564,7 @@ public: CodeGenDAGPatterns &ise); TreePattern(Record *TheRec, TreePatternNode *Pat, bool isInput, CodeGenDAGPatterns &ise); - + /// getTrees - Return the tree patterns which corresponds to this pattern. /// const std::vector &getTrees() const { return Trees; } @@ -338,19 +574,25 @@ 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. /// Record *getRecord() const { return TheRecord; } - + unsigned getNumArgs() const { return Args.size(); } const std::string &getArgName(unsigned i) const { assert(i < Args.size() && "Argument reference out of range!"); return Args[i]; } std::vector &getArgList() { return Args; } - + CodeGenDAGPatterns &getDAGPatterns() const { return CDP; } /// InlinePatternFragments - If this pattern refers to any pattern @@ -360,25 +602,34 @@ public: for (unsigned i = 0, e = Trees.size(); i != e; ++i) Trees[i] = Trees[i]->InlinePatternFragments(*this); } - + /// InferAllTypes - Infer/propagate as many types throughout the expression /// patterns as possible. Return true if all types are inferred, 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; - - void print(std::ostream &OS) const; + /// otherwise. Bail out if a type contradiction is found. + bool InferAllTypes(const StringMap > + *NamedTypes=nullptr); + + /// error - If this is the first error in the current resolution step, + /// print it and set the error flag. Otherwise, continue silently. + void error(const Twine &Msg); + bool hasError() const { + return HasError; + } + void resetError() { + HasError = false; + } + + void print(raw_ostream &OS) const; void dump() const; - + private: - TreePatternNode *ParseTreePattern(DagInit *DI); + TreePatternNode *ParseTreePattern(Init *DI, StringRef OpName); + void ComputeNamedNodes(); + void ComputeNamedNodes(TreePatternNode *N); }; -/// DAGDefaultOperand - One of these is created for each PredicateOperand -/// or OptionalDefOperand that has a set ExecuteAlways / DefaultOps field. +/// DAGDefaultOperand - One of these is created for each OperandWithDefaultOps +/// that has a set ExecuteAlways / DefaultOps field. struct DAGDefaultOperand { std::vector DefaultOps; }; @@ -388,32 +639,28 @@ class DAGInstruction { 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) {} + const std::vector &impresults) + : Pattern(TP), Results(results), Operands(operands), + ImpResults(impresults), ResultPattern(nullptr) {} - const TreePattern *getPattern() const { return Pattern; } + 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(); } const std::vector& getImpResults() const { return ImpResults; } - + 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]; @@ -423,131 +670,138 @@ public: assert(RN < ImpResults.size()); return ImpResults[RN]; } - - Record *getImpOperand(unsigned ON) const { - assert(ON < ImpOperands.size()); - return ImpOperands[ON]; - } TreePatternNode *getResultPattern() const { return ResultPattern; } }; - + /// PatternToMatch - Used by CodeGenDAGPatterns to keep tab of patterns /// processed to produce isel. -struct PatternToMatch { - PatternToMatch(ListInit *preds, +class PatternToMatch { +public: + PatternToMatch(Record *srcrecord, ListInit *preds, TreePatternNode *src, TreePatternNode *dst, const std::vector &dstregs, - unsigned complexity): - Predicates(preds), SrcPattern(src), DstPattern(dst), Dstregs(dstregs), - AddedComplexity(complexity) {}; + int complexity, unsigned uid) + : SrcRecord(srcrecord), Predicates(preds), SrcPattern(src), DstPattern(dst), + Dstregs(dstregs), AddedComplexity(complexity), ID(uid) {} + Record *SrcRecord; // Originating Record for the pattern. 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. + int AddedComplexity; // Add to matching pattern complexity. + unsigned ID; // Unique ID for the record. + Record *getSrcRecord() const { return SrcRecord; } 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; } + int getAddedComplexity() const { return AddedComplexity; } std::string getPredicateCheck() const; + + /// Compute the complexity metric for the input pattern. This roughly + /// corresponds to the number of nodes that are covered. + int getPatternComplexity(const CodeGenDAGPatterns &CGP) 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, LessRecordByID> SDNodeXForms; + std::map ComplexPatterns; + std::map, LessRecordByID> + PatternFragments; + std::map DefaultOperands; + 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: - CodeGenDAGPatterns(RecordKeeper &R); - ~CodeGenDAGPatterns(); - + CodeGenDAGPatterns(RecordKeeper &R); + CodeGenTarget &getTargetInfo() { return Target; } 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; } - + // Node transformation lookups. typedef std::pair NodeXForm; const NodeXForm &getSDNodeTransform(Record *R) const { assert(SDNodeXForms.count(R) && "Invalid transform!"); 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(); } - + 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]; for (unsigned i = 0, e = TgtIntrinsics.size(); i != e; ++i) if (TgtIntrinsics[i].TheDef == R) return TgtIntrinsics[i]; - assert(0 && "Unknown intrinsic!"); - abort(); + llvm_unreachable("Unknown intrinsic!"); } - + const CodeGenIntrinsic &getIntrinsicInfo(unsigned IID) const { 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(); + llvm_unreachable("Bad intrinsic ID!"); } - + 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(); + llvm_unreachable("Unknown intrinsic!"); } - - 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; } - + // Pattern Fragment information. TreePattern *getPatternFragment(Record *R) const { assert(PatternFragments.count(R) && "Invalid pattern fragment request!"); - return PatternFragments.find(R)->second; + return PatternFragments.find(R)->second.get(); } - typedef std::map::const_iterator pf_iterator; + TreePattern *getPatternFragmentIfRead(Record *R) const { + if (!PatternFragments.count(R)) + return nullptr; + return PatternFragments.find(R)->second.get(); + } + + typedef std::map, + LessRecordByID>::const_iterator pf_iterator; pf_iterator pf_begin() const { return PatternFragments.begin(); } pf_iterator pf_end() const { return PatternFragments.end(); } @@ -555,14 +809,18 @@ public: typedef std::vector::const_iterator ptm_iterator; ptm_iterator ptm_begin() const { return PatternsToMatch.begin(); } ptm_iterator ptm_end() const { return PatternsToMatch.end(); } - - - + + /// Parse the Pattern for an instruction, and insert the result in DAGInsts. + typedef std::map DAGInstMap; + const DAGInstruction &parseInstructionPattern( + CodeGenInstruction &CGI, ListInit *Pattern, + DAGInstMap &DAGInsts); + 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; } @@ -572,24 +830,27 @@ public: Record *get_intrinsic_wo_chain_sdnode() const { return intrinsic_wo_chain_sdnode; } - + + bool hasTargetIntrinsics() { return !TgtIntrinsics.empty(); } + private: void ParseNodeInfo(); void ParseNodeTransforms(); void ParseComplexPatterns(); - void ParsePatternFragments(); + void ParsePatternFragments(bool OutFrags = false); void ParseDefaultOperands(); void ParseInstructions(); void ParsePatterns(); void InferInstructionFlags(); void GenerateVariants(); - + void VerifyInstructionFlags(); + + void AddPatternToMatch(TreePattern *Pattern, const PatternToMatch &PTM); void FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, std::map &InstInputs, std::map &InstResults, - std::vector &InstImpInputs, std::vector &InstImpResults); }; } // end namespace llvm