1193323Sed//===- CodeGenDAGPatterns.h - Read DAG patterns from .td file ---*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file declares the CodeGenDAGPatterns class, which is used to read and 11193323Sed// represent the patterns present in a .td file for instructions. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15193323Sed#ifndef CODEGEN_DAGPATTERNS_H 16193323Sed#define CODEGEN_DAGPATTERNS_H 17193323Sed 18252723Sdim#include "CodeGenIntrinsics.h" 19193323Sed#include "CodeGenTarget.h" 20205218Srdivacky#include "llvm/ADT/SmallVector.h" 21205218Srdivacky#include "llvm/ADT/StringMap.h" 22235633Sdim#include "llvm/Support/ErrorHandling.h" 23252723Sdim#include <algorithm> 24252723Sdim#include <map> 25205407Srdivacky#include <set> 26205407Srdivacky#include <vector> 27193323Sed 28193323Sednamespace llvm { 29193323Sed class Record; 30224145Sdim class Init; 31193323Sed class ListInit; 32193323Sed class DagInit; 33193323Sed class SDNodeInfo; 34193323Sed class TreePattern; 35193323Sed class TreePatternNode; 36193323Sed class CodeGenDAGPatterns; 37193323Sed class ComplexPattern; 38193323Sed 39198090Srdivacky/// EEVT::DAGISelGenValueType - These are some extended forms of 40193323Sed/// MVT::SimpleValueType that we use as lattice values during type inference. 41198090Srdivacky/// The existing MVT iAny, fAny and vAny types suffice to represent 42198090Srdivacky/// arbitrary integer, floating-point, and vector types, so only an unknown 43198090Srdivacky/// value is needed. 44198090Srdivackynamespace EEVT { 45205218Srdivacky /// TypeSet - This is either empty if it's completely unknown, or holds a set 46205218Srdivacky /// of types. It is used during type inference because register classes can 47205218Srdivacky /// have multiple possible types and we don't know which one they get until 48205218Srdivacky /// type inference is complete. 49205218Srdivacky /// 50205218Srdivacky /// TypeSet can have three states: 51205218Srdivacky /// Vector is empty: The type is completely unknown, it can be any valid 52205218Srdivacky /// target type. 53205218Srdivacky /// Vector has multiple constrained types: (e.g. v4i32 + v4f32) it is one 54205218Srdivacky /// of those types only. 55205218Srdivacky /// Vector has one concrete type: The type is completely known. 56205218Srdivacky /// 57205218Srdivacky class TypeSet { 58205407Srdivacky SmallVector<MVT::SimpleValueType, 4> TypeVec; 59205218Srdivacky public: 60205218Srdivacky TypeSet() {} 61205218Srdivacky TypeSet(MVT::SimpleValueType VT, TreePattern &TP); 62252723Sdim TypeSet(ArrayRef<MVT::SimpleValueType> VTList); 63218893Sdim 64205218Srdivacky bool isCompletelyUnknown() const { return TypeVec.empty(); } 65218893Sdim 66205218Srdivacky bool isConcrete() const { 67205218Srdivacky if (TypeVec.size() != 1) return false; 68205218Srdivacky unsigned char T = TypeVec[0]; (void)T; 69205218Srdivacky assert(T < MVT::LAST_VALUETYPE || T == MVT::iPTR || T == MVT::iPTRAny); 70205218Srdivacky return true; 71205218Srdivacky } 72218893Sdim 73205218Srdivacky MVT::SimpleValueType getConcrete() const { 74205218Srdivacky assert(isConcrete() && "Type isn't concrete yet"); 75205218Srdivacky return (MVT::SimpleValueType)TypeVec[0]; 76205218Srdivacky } 77218893Sdim 78205218Srdivacky bool isDynamicallyResolved() const { 79205218Srdivacky return getConcrete() == MVT::iPTR || getConcrete() == MVT::iPTRAny; 80205218Srdivacky } 81218893Sdim 82205218Srdivacky const SmallVectorImpl<MVT::SimpleValueType> &getTypeList() const { 83205218Srdivacky assert(!TypeVec.empty() && "Not a type list!"); 84205218Srdivacky return TypeVec; 85205218Srdivacky } 86218893Sdim 87205407Srdivacky bool isVoid() const { 88205407Srdivacky return TypeVec.size() == 1 && TypeVec[0] == MVT::isVoid; 89205407Srdivacky } 90218893Sdim 91205218Srdivacky /// hasIntegerTypes - Return true if this TypeSet contains any integer value 92205218Srdivacky /// types. 93205218Srdivacky bool hasIntegerTypes() const; 94218893Sdim 95205218Srdivacky /// hasFloatingPointTypes - Return true if this TypeSet contains an fAny or 96205218Srdivacky /// a floating point value type. 97205218Srdivacky bool hasFloatingPointTypes() const; 98218893Sdim 99205218Srdivacky /// hasVectorTypes - Return true if this TypeSet contains a vector value 100205218Srdivacky /// type. 101205218Srdivacky bool hasVectorTypes() const; 102218893Sdim 103205218Srdivacky /// getName() - Return this TypeSet as a string. 104205218Srdivacky std::string getName() const; 105218893Sdim 106205218Srdivacky /// MergeInTypeInfo - This merges in type information from the specified 107205218Srdivacky /// argument. If 'this' changes, it returns true. If the two types are 108245431Sdim /// contradictory (e.g. merge f32 into i32) then this flags an error. 109205218Srdivacky bool MergeInTypeInfo(const EEVT::TypeSet &InVT, TreePattern &TP); 110193323Sed 111205218Srdivacky bool MergeInTypeInfo(MVT::SimpleValueType InVT, TreePattern &TP) { 112205218Srdivacky return MergeInTypeInfo(EEVT::TypeSet(InVT, TP), TP); 113205218Srdivacky } 114193323Sed 115205218Srdivacky /// Force this type list to only contain integer types. 116205218Srdivacky bool EnforceInteger(TreePattern &TP); 117198090Srdivacky 118205218Srdivacky /// Force this type list to only contain floating point types. 119205218Srdivacky bool EnforceFloatingPoint(TreePattern &TP); 120205218Srdivacky 121205218Srdivacky /// EnforceScalar - Remove all vector types from this type list. 122205218Srdivacky bool EnforceScalar(TreePattern &TP); 123205218Srdivacky 124205218Srdivacky /// EnforceVector - Remove all non-vector types from this type list. 125205218Srdivacky bool EnforceVector(TreePattern &TP); 126205218Srdivacky 127205218Srdivacky /// EnforceSmallerThan - 'this' must be a smaller VT than Other. Update 128205218Srdivacky /// this an other based on this information. 129205218Srdivacky bool EnforceSmallerThan(EEVT::TypeSet &Other, TreePattern &TP); 130218893Sdim 131205218Srdivacky /// EnforceVectorEltTypeIs - 'this' is now constrainted to be a vector type 132205218Srdivacky /// whose element is VT. 133206083Srdivacky bool EnforceVectorEltTypeIs(EEVT::TypeSet &VT, TreePattern &TP); 134218893Sdim 135218893Sdim /// EnforceVectorSubVectorTypeIs - 'this' is now constrainted to 136218893Sdim /// be a vector type VT. 137218893Sdim bool EnforceVectorSubVectorTypeIs(EEVT::TypeSet &VT, TreePattern &TP); 138218893Sdim 139205218Srdivacky bool operator!=(const TypeSet &RHS) const { return TypeVec != RHS.TypeVec; } 140205218Srdivacky bool operator==(const TypeSet &RHS) const { return TypeVec == RHS.TypeVec; } 141218893Sdim 142205407Srdivacky private: 143205407Srdivacky /// FillWithPossibleTypes - Set to all legal types and return true, only 144205407Srdivacky /// valid on completely unknown type sets. If Pred is non-null, only MVTs 145205407Srdivacky /// that pass the predicate are added. 146205407Srdivacky bool FillWithPossibleTypes(TreePattern &TP, 147205407Srdivacky bool (*Pred)(MVT::SimpleValueType) = 0, 148205407Srdivacky const char *PredicateName = 0); 149205218Srdivacky }; 150193323Sed} 151193323Sed 152193323Sed/// Set type used to track multiply used variables in patterns 153193323Sedtypedef std::set<std::string> MultipleUseVarSet; 154193323Sed 155193323Sed/// SDTypeConstraint - This is a discriminated union of constraints, 156193323Sed/// corresponding to the SDTypeConstraint tablegen class in Target.td. 157193323Sedstruct SDTypeConstraint { 158193323Sed SDTypeConstraint(Record *R); 159218893Sdim 160193323Sed unsigned OperandNo; // The operand # this constraint applies to. 161218893Sdim enum { 162218893Sdim SDTCisVT, SDTCisPtrTy, SDTCisInt, SDTCisFP, SDTCisVec, SDTCisSameAs, 163218893Sdim SDTCisVTSmallerThanOp, SDTCisOpSmallerThanOp, SDTCisEltOfVec, 164218893Sdim SDTCisSubVecOfVec 165193323Sed } ConstraintType; 166218893Sdim 167193323Sed union { // The discriminated union. 168193323Sed struct { 169205218Srdivacky MVT::SimpleValueType VT; 170193323Sed } SDTCisVT_Info; 171193323Sed struct { 172193323Sed unsigned OtherOperandNum; 173193323Sed } SDTCisSameAs_Info; 174193323Sed struct { 175193323Sed unsigned OtherOperandNum; 176193323Sed } SDTCisVTSmallerThanOp_Info; 177193323Sed struct { 178193323Sed unsigned BigOperandNum; 179193323Sed } SDTCisOpSmallerThanOp_Info; 180193323Sed struct { 181193323Sed unsigned OtherOperandNum; 182193323Sed } SDTCisEltOfVec_Info; 183218893Sdim struct { 184218893Sdim unsigned OtherOperandNum; 185218893Sdim } SDTCisSubVecOfVec_Info; 186193323Sed } x; 187193323Sed 188193323Sed /// ApplyTypeConstraint - Given a node in a pattern, apply this type 189193323Sed /// constraint to the nodes operands. This returns true if it makes a 190245431Sdim /// change, false otherwise. If a type contradiction is found, an error 191245431Sdim /// is flagged. 192193323Sed bool ApplyTypeConstraint(TreePatternNode *N, const SDNodeInfo &NodeInfo, 193193323Sed TreePattern &TP) const; 194193323Sed}; 195193323Sed 196193323Sed/// SDNodeInfo - One of these records is created for each SDNode instance in 197193323Sed/// the target .td file. This represents the various dag nodes we will be 198193323Sed/// processing. 199193323Sedclass SDNodeInfo { 200193323Sed Record *Def; 201193323Sed std::string EnumName; 202193323Sed std::string SDClassName; 203193323Sed unsigned Properties; 204193323Sed unsigned NumResults; 205193323Sed int NumOperands; 206193323Sed std::vector<SDTypeConstraint> TypeConstraints; 207193323Sedpublic: 208193323Sed SDNodeInfo(Record *R); // Parse the specified record. 209218893Sdim 210193323Sed unsigned getNumResults() const { return NumResults; } 211218893Sdim 212206083Srdivacky /// getNumOperands - This is the number of operands required or -1 if 213206083Srdivacky /// variadic. 214193323Sed int getNumOperands() const { return NumOperands; } 215193323Sed Record *getRecord() const { return Def; } 216193323Sed const std::string &getEnumName() const { return EnumName; } 217193323Sed const std::string &getSDClassName() const { return SDClassName; } 218218893Sdim 219193323Sed const std::vector<SDTypeConstraint> &getTypeConstraints() const { 220193323Sed return TypeConstraints; 221193323Sed } 222218893Sdim 223204642Srdivacky /// getKnownType - If the type constraints on this node imply a fixed type 224204642Srdivacky /// (e.g. all stores return void, etc), then return it as an 225205407Srdivacky /// MVT::SimpleValueType. Otherwise, return MVT::Other. 226206083Srdivacky MVT::SimpleValueType getKnownType(unsigned ResNo) const; 227218893Sdim 228193323Sed /// hasProperty - Return true if this node has the specified property. 229193323Sed /// 230193323Sed bool hasProperty(enum SDNP Prop) const { return Properties & (1 << Prop); } 231193323Sed 232193323Sed /// ApplyTypeConstraints - Given a node in a pattern, apply the type 233193323Sed /// constraints for this node to the operands of the node. This returns 234193323Sed /// true if it makes a change, false otherwise. If a type contradiction is 235245431Sdim /// found, an error is flagged. 236193323Sed bool ApplyTypeConstraints(TreePatternNode *N, TreePattern &TP) const { 237193323Sed bool MadeChange = false; 238193323Sed for (unsigned i = 0, e = TypeConstraints.size(); i != e; ++i) 239193323Sed MadeChange |= TypeConstraints[i].ApplyTypeConstraint(N, *this, TP); 240193323Sed return MadeChange; 241193323Sed } 242193323Sed}; 243221345Sdim 244221345Sdim/// TreePredicateFn - This is an abstraction that represents the predicates on 245221345Sdim/// a PatFrag node. This is a simple one-word wrapper around a pointer to 246221345Sdim/// provide nice accessors. 247221345Sdimclass TreePredicateFn { 248221345Sdim /// PatFragRec - This is the TreePattern for the PatFrag that we 249221345Sdim /// originally came from. 250221345Sdim TreePattern *PatFragRec; 251221345Sdimpublic: 252221345Sdim /// TreePredicateFn constructor. Here 'N' is a subclass of PatFrag. 253221345Sdim TreePredicateFn(TreePattern *N); 254193323Sed 255221345Sdim 256221345Sdim TreePattern *getOrigPatFragRecord() const { return PatFragRec; } 257221345Sdim 258221345Sdim /// isAlwaysTrue - Return true if this is a noop predicate. 259221345Sdim bool isAlwaysTrue() const; 260221345Sdim 261221345Sdim bool isImmediatePattern() const { return !getImmCode().empty(); } 262221345Sdim 263221345Sdim /// getImmediatePredicateCode - Return the code that evaluates this pattern if 264221345Sdim /// this is an immediate predicate. It is an error to call this on a 265221345Sdim /// non-immediate pattern. 266221345Sdim std::string getImmediatePredicateCode() const { 267221345Sdim std::string Result = getImmCode(); 268221345Sdim assert(!Result.empty() && "Isn't an immediate pattern!"); 269221345Sdim return Result; 270221345Sdim } 271221345Sdim 272221345Sdim 273221345Sdim bool operator==(const TreePredicateFn &RHS) const { 274221345Sdim return PatFragRec == RHS.PatFragRec; 275221345Sdim } 276221345Sdim 277221345Sdim bool operator!=(const TreePredicateFn &RHS) const { return !(*this == RHS); } 278221345Sdim 279221345Sdim /// Return the name to use in the generated code to reference this, this is 280221345Sdim /// "Predicate_foo" if from a pattern fragment "foo". 281221345Sdim std::string getFnName() const; 282221345Sdim 283221345Sdim /// getCodeToRunOnSDNode - Return the code for the function body that 284221345Sdim /// evaluates this predicate. The argument is expected to be in "Node", 285221345Sdim /// not N. This handles casting and conversion to a concrete node type as 286221345Sdim /// appropriate. 287221345Sdim std::string getCodeToRunOnSDNode() const; 288221345Sdim 289221345Sdimprivate: 290221345Sdim std::string getPredCode() const; 291221345Sdim std::string getImmCode() const; 292221345Sdim}; 293221345Sdim 294221345Sdim 295193323Sed/// FIXME: TreePatternNode's can be shared in some cases (due to dag-shaped 296193323Sed/// patterns), and as such should be ref counted. We currently just leak all 297193323Sed/// TreePatternNode objects! 298193323Sedclass TreePatternNode { 299205407Srdivacky /// The type of each node result. Before and during type inference, each 300205407Srdivacky /// result may be a set of possible types. After (successful) type inference, 301205407Srdivacky /// each is a single concrete type. 302205407Srdivacky SmallVector<EEVT::TypeSet, 1> Types; 303218893Sdim 304193323Sed /// Operator - The Record for the operator if this is an interior node (not 305193323Sed /// a leaf). 306193323Sed Record *Operator; 307218893Sdim 308193323Sed /// Val - The init value (e.g. the "GPRC" record, or "7") for a leaf. 309193323Sed /// 310193323Sed Init *Val; 311218893Sdim 312193323Sed /// Name - The name given to this node with the :$foo notation. 313193323Sed /// 314193323Sed std::string Name; 315218893Sdim 316193323Sed /// PredicateFns - The predicate functions to execute on this node to check 317193323Sed /// for a match. If this list is empty, no predicate is involved. 318221345Sdim std::vector<TreePredicateFn> PredicateFns; 319218893Sdim 320193323Sed /// TransformFn - The transformation function to execute on this node before 321193323Sed /// it can be substituted into the resulting instruction on a pattern match. 322193323Sed Record *TransformFn; 323218893Sdim 324193323Sed std::vector<TreePatternNode*> Children; 325193323Sedpublic: 326205407Srdivacky TreePatternNode(Record *Op, const std::vector<TreePatternNode*> &Ch, 327218893Sdim unsigned NumResults) 328205407Srdivacky : Operator(Op), Val(0), TransformFn(0), Children(Ch) { 329205407Srdivacky Types.resize(NumResults); 330205407Srdivacky } 331205407Srdivacky TreePatternNode(Init *val, unsigned NumResults) // leaf ctor 332205218Srdivacky : Operator(0), Val(val), TransformFn(0) { 333205407Srdivacky Types.resize(NumResults); 334193323Sed } 335193323Sed ~TreePatternNode(); 336218893Sdim 337252723Sdim bool hasName() const { return !Name.empty(); } 338193323Sed const std::string &getName() const { return Name; } 339206083Srdivacky void setName(StringRef N) { Name.assign(N.begin(), N.end()); } 340218893Sdim 341193323Sed bool isLeaf() const { return Val != 0; } 342218893Sdim 343205218Srdivacky // Type accessors. 344205407Srdivacky unsigned getNumTypes() const { return Types.size(); } 345205407Srdivacky MVT::SimpleValueType getType(unsigned ResNo) const { 346205407Srdivacky return Types[ResNo].getConcrete(); 347205407Srdivacky } 348205407Srdivacky const SmallVectorImpl<EEVT::TypeSet> &getExtTypes() const { return Types; } 349205407Srdivacky const EEVT::TypeSet &getExtType(unsigned ResNo) const { return Types[ResNo]; } 350205407Srdivacky EEVT::TypeSet &getExtType(unsigned ResNo) { return Types[ResNo]; } 351205407Srdivacky void setType(unsigned ResNo, const EEVT::TypeSet &T) { Types[ResNo] = T; } 352218893Sdim 353205407Srdivacky bool hasTypeSet(unsigned ResNo) const { 354205407Srdivacky return Types[ResNo].isConcrete(); 355205407Srdivacky } 356205407Srdivacky bool isTypeCompletelyUnknown(unsigned ResNo) const { 357205407Srdivacky return Types[ResNo].isCompletelyUnknown(); 358205407Srdivacky } 359205407Srdivacky bool isTypeDynamicallyResolved(unsigned ResNo) const { 360205407Srdivacky return Types[ResNo].isDynamicallyResolved(); 361205407Srdivacky } 362218893Sdim 363193323Sed Init *getLeafValue() const { assert(isLeaf()); return Val; } 364193323Sed Record *getOperator() const { assert(!isLeaf()); return Operator; } 365218893Sdim 366193323Sed unsigned getNumChildren() const { return Children.size(); } 367193323Sed TreePatternNode *getChild(unsigned N) const { return Children[N]; } 368193323Sed void setChild(unsigned i, TreePatternNode *N) { 369193323Sed Children[i] = N; 370193323Sed } 371218893Sdim 372203954Srdivacky /// hasChild - Return true if N is any of our children. 373203954Srdivacky bool hasChild(const TreePatternNode *N) const { 374203954Srdivacky for (unsigned i = 0, e = Children.size(); i != e; ++i) 375203954Srdivacky if (Children[i] == N) return true; 376203954Srdivacky return false; 377203954Srdivacky } 378193323Sed 379221345Sdim bool hasAnyPredicate() const { return !PredicateFns.empty(); } 380221345Sdim 381221345Sdim const std::vector<TreePredicateFn> &getPredicateFns() const { 382221345Sdim return PredicateFns; 383221345Sdim } 384193323Sed void clearPredicateFns() { PredicateFns.clear(); } 385221345Sdim void setPredicateFns(const std::vector<TreePredicateFn> &Fns) { 386193323Sed assert(PredicateFns.empty() && "Overwriting non-empty predicate list!"); 387193323Sed PredicateFns = Fns; 388193323Sed } 389221345Sdim void addPredicateFn(const TreePredicateFn &Fn) { 390221345Sdim assert(!Fn.isAlwaysTrue() && "Empty predicate string!"); 391193323Sed if (std::find(PredicateFns.begin(), PredicateFns.end(), Fn) == 392193323Sed PredicateFns.end()) 393193323Sed PredicateFns.push_back(Fn); 394193323Sed } 395193323Sed 396193323Sed Record *getTransformFn() const { return TransformFn; } 397193323Sed void setTransformFn(Record *Fn) { TransformFn = Fn; } 398218893Sdim 399193323Sed /// getIntrinsicInfo - If this node corresponds to an intrinsic, return the 400193323Sed /// CodeGenIntrinsic information for it, otherwise return a null pointer. 401193323Sed const CodeGenIntrinsic *getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const; 402193323Sed 403203954Srdivacky /// getComplexPatternInfo - If this node corresponds to a ComplexPattern, 404203954Srdivacky /// return the ComplexPattern information, otherwise return null. 405203954Srdivacky const ComplexPattern * 406203954Srdivacky getComplexPatternInfo(const CodeGenDAGPatterns &CGP) const; 407203954Srdivacky 408203954Srdivacky /// NodeHasProperty - Return true if this node has the specified property. 409203954Srdivacky bool NodeHasProperty(SDNP Property, const CodeGenDAGPatterns &CGP) const; 410218893Sdim 411203954Srdivacky /// TreeHasProperty - Return true if any node in this tree has the specified 412203954Srdivacky /// property. 413203954Srdivacky bool TreeHasProperty(SDNP Property, const CodeGenDAGPatterns &CGP) const; 414218893Sdim 415193323Sed /// isCommutativeIntrinsic - Return true if the node is an intrinsic which is 416193323Sed /// marked isCommutative. 417193323Sed bool isCommutativeIntrinsic(const CodeGenDAGPatterns &CDP) const; 418218893Sdim 419195340Sed void print(raw_ostream &OS) const; 420193323Sed void dump() const; 421218893Sdim 422193323Sedpublic: // Higher level manipulation routines. 423193323Sed 424193323Sed /// clone - Return a new copy of this tree. 425193323Sed /// 426193323Sed TreePatternNode *clone() const; 427203954Srdivacky 428203954Srdivacky /// RemoveAllTypes - Recursively strip all the types of this tree. 429203954Srdivacky void RemoveAllTypes(); 430218893Sdim 431193323Sed /// isIsomorphicTo - Return true if this node is recursively isomorphic to 432193323Sed /// the specified node. For this comparison, all of the state of the node 433193323Sed /// is considered, except for the assigned name. Nodes with differing names 434193323Sed /// that are otherwise identical are considered isomorphic. 435193323Sed bool isIsomorphicTo(const TreePatternNode *N, 436193323Sed const MultipleUseVarSet &DepVars) const; 437218893Sdim 438193323Sed /// SubstituteFormalArguments - Replace the formal arguments in this tree 439193323Sed /// with actual values specified by ArgMap. 440193323Sed void SubstituteFormalArguments(std::map<std::string, 441193323Sed TreePatternNode*> &ArgMap); 442193323Sed 443193323Sed /// InlinePatternFragments - If this pattern refers to any pattern 444193323Sed /// fragments, inline them into place, giving us a pattern without any 445193323Sed /// PatFrag references. 446193323Sed TreePatternNode *InlinePatternFragments(TreePattern &TP); 447218893Sdim 448193323Sed /// ApplyTypeConstraints - Apply all of the type constraints relevant to 449193323Sed /// this node and its children in the tree. This returns true if it makes a 450245431Sdim /// change, false otherwise. If a type contradiction is found, flag an error. 451193323Sed bool ApplyTypeConstraints(TreePattern &TP, bool NotRegisters); 452218893Sdim 453193323Sed /// UpdateNodeType - Set the node type of N to VT if VT contains 454245431Sdim /// information. If N already contains a conflicting type, then flag an 455245431Sdim /// error. This returns true if any information was updated. 456193323Sed /// 457205407Srdivacky bool UpdateNodeType(unsigned ResNo, const EEVT::TypeSet &InTy, 458205407Srdivacky TreePattern &TP) { 459205407Srdivacky return Types[ResNo].MergeInTypeInfo(InTy, TP); 460193323Sed } 461205218Srdivacky 462205407Srdivacky bool UpdateNodeType(unsigned ResNo, MVT::SimpleValueType InTy, 463205407Srdivacky TreePattern &TP) { 464205407Srdivacky return Types[ResNo].MergeInTypeInfo(EEVT::TypeSet(InTy, TP), TP); 465205218Srdivacky } 466218893Sdim 467252723Sdim // Update node type with types inferred from an instruction operand or result 468252723Sdim // def from the ins/outs lists. 469252723Sdim // Return true if the type changed. 470252723Sdim bool UpdateNodeTypeFromInst(unsigned ResNo, Record *Operand, TreePattern &TP); 471252723Sdim 472193323Sed /// ContainsUnresolvedType - Return true if this tree contains any 473193323Sed /// unresolved types. 474193323Sed bool ContainsUnresolvedType() const { 475205407Srdivacky for (unsigned i = 0, e = Types.size(); i != e; ++i) 476205407Srdivacky if (!Types[i].isConcrete()) return true; 477218893Sdim 478193323Sed for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 479193323Sed if (getChild(i)->ContainsUnresolvedType()) return true; 480193323Sed return false; 481193323Sed } 482218893Sdim 483193323Sed /// canPatternMatch - If it is impossible for this pattern to match on this 484193323Sed /// target, fill in Reason and return false. Otherwise, return true. 485193323Sed bool canPatternMatch(std::string &Reason, const CodeGenDAGPatterns &CDP); 486193323Sed}; 487193323Sed 488203954Srdivackyinline raw_ostream &operator<<(raw_ostream &OS, const TreePatternNode &TPN) { 489203954Srdivacky TPN.print(OS); 490203954Srdivacky return OS; 491203954Srdivacky} 492193323Sed 493218893Sdim 494193323Sed/// TreePattern - Represent a pattern, used for instructions, pattern 495193323Sed/// fragments, etc. 496193323Sed/// 497193323Sedclass TreePattern { 498193323Sed /// Trees - The list of pattern trees which corresponds to this pattern. 499193323Sed /// Note that PatFrag's only have a single tree. 500193323Sed /// 501193323Sed std::vector<TreePatternNode*> Trees; 502218893Sdim 503205218Srdivacky /// NamedNodes - This is all of the nodes that have names in the trees in this 504205218Srdivacky /// pattern. 505205218Srdivacky StringMap<SmallVector<TreePatternNode*,1> > NamedNodes; 506218893Sdim 507193323Sed /// TheRecord - The actual TableGen record corresponding to this pattern. 508193323Sed /// 509193323Sed Record *TheRecord; 510218893Sdim 511193323Sed /// Args - This is a list of all of the arguments to this pattern (for 512193323Sed /// PatFrag patterns), which are the 'node' markers in this pattern. 513193323Sed std::vector<std::string> Args; 514218893Sdim 515193323Sed /// CDP - the top-level object coordinating this madness. 516193323Sed /// 517193323Sed CodeGenDAGPatterns &CDP; 518193323Sed 519193323Sed /// isInputPattern - True if this is an input pattern, something to match. 520193323Sed /// False if this is an output pattern, something to emit. 521193323Sed bool isInputPattern; 522245431Sdim 523245431Sdim /// hasError - True if the currently processed nodes have unresolvable types 524245431Sdim /// or other non-fatal errors 525245431Sdim bool HasError; 526193323Sedpublic: 527218893Sdim 528193323Sed /// TreePattern constructor - Parse the specified DagInits into the 529193323Sed /// current record. 530193323Sed TreePattern(Record *TheRec, ListInit *RawPat, bool isInput, 531193323Sed CodeGenDAGPatterns &ise); 532193323Sed TreePattern(Record *TheRec, DagInit *Pat, bool isInput, 533193323Sed CodeGenDAGPatterns &ise); 534193323Sed TreePattern(Record *TheRec, TreePatternNode *Pat, bool isInput, 535193323Sed CodeGenDAGPatterns &ise); 536218893Sdim 537193323Sed /// getTrees - Return the tree patterns which corresponds to this pattern. 538193323Sed /// 539193323Sed const std::vector<TreePatternNode*> &getTrees() const { return Trees; } 540193323Sed unsigned getNumTrees() const { return Trees.size(); } 541193323Sed TreePatternNode *getTree(unsigned i) const { return Trees[i]; } 542193323Sed TreePatternNode *getOnlyTree() const { 543193323Sed assert(Trees.size() == 1 && "Doesn't have exactly one pattern!"); 544193323Sed return Trees[0]; 545193323Sed } 546218893Sdim 547205218Srdivacky const StringMap<SmallVector<TreePatternNode*,1> > &getNamedNodesMap() { 548205218Srdivacky if (NamedNodes.empty()) 549205218Srdivacky ComputeNamedNodes(); 550205218Srdivacky return NamedNodes; 551205218Srdivacky } 552218893Sdim 553193323Sed /// getRecord - Return the actual TableGen record corresponding to this 554193323Sed /// pattern. 555193323Sed /// 556193323Sed Record *getRecord() const { return TheRecord; } 557218893Sdim 558193323Sed unsigned getNumArgs() const { return Args.size(); } 559193323Sed const std::string &getArgName(unsigned i) const { 560193323Sed assert(i < Args.size() && "Argument reference out of range!"); 561193323Sed return Args[i]; 562193323Sed } 563193323Sed std::vector<std::string> &getArgList() { return Args; } 564218893Sdim 565193323Sed CodeGenDAGPatterns &getDAGPatterns() const { return CDP; } 566193323Sed 567193323Sed /// InlinePatternFragments - If this pattern refers to any pattern 568193323Sed /// fragments, inline them into place, giving us a pattern without any 569193323Sed /// PatFrag references. 570193323Sed void InlinePatternFragments() { 571193323Sed for (unsigned i = 0, e = Trees.size(); i != e; ++i) 572193323Sed Trees[i] = Trees[i]->InlinePatternFragments(*this); 573193323Sed } 574218893Sdim 575193323Sed /// InferAllTypes - Infer/propagate as many types throughout the expression 576193323Sed /// patterns as possible. Return true if all types are inferred, false 577245431Sdim /// otherwise. Bail out if a type contradiction is found. 578205218Srdivacky bool InferAllTypes(const StringMap<SmallVector<TreePatternNode*,1> > 579205218Srdivacky *NamedTypes=0); 580218893Sdim 581245431Sdim /// error - If this is the first error in the current resolution step, 582245431Sdim /// print it and set the error flag. Otherwise, continue silently. 583245431Sdim void error(const std::string &Msg); 584245431Sdim bool hasError() const { 585245431Sdim return HasError; 586245431Sdim } 587245431Sdim void resetError() { 588245431Sdim HasError = false; 589245431Sdim } 590218893Sdim 591195340Sed void print(raw_ostream &OS) const; 592193323Sed void dump() const; 593218893Sdim 594193323Sedprivate: 595206083Srdivacky TreePatternNode *ParseTreePattern(Init *DI, StringRef OpName); 596205218Srdivacky void ComputeNamedNodes(); 597205218Srdivacky void ComputeNamedNodes(TreePatternNode *N); 598193323Sed}; 599193323Sed 600245431Sdim/// DAGDefaultOperand - One of these is created for each OperandWithDefaultOps 601245431Sdim/// that has a set ExecuteAlways / DefaultOps field. 602193323Sedstruct DAGDefaultOperand { 603193323Sed std::vector<TreePatternNode*> DefaultOps; 604193323Sed}; 605193323Sed 606193323Sedclass DAGInstruction { 607193323Sed TreePattern *Pattern; 608193323Sed std::vector<Record*> Results; 609193323Sed std::vector<Record*> Operands; 610193323Sed std::vector<Record*> ImpResults; 611193323Sed TreePatternNode *ResultPattern; 612193323Sedpublic: 613193323Sed DAGInstruction(TreePattern *TP, 614193323Sed const std::vector<Record*> &results, 615193323Sed const std::vector<Record*> &operands, 616207618Srdivacky const std::vector<Record*> &impresults) 617218893Sdim : Pattern(TP), Results(results), Operands(operands), 618207618Srdivacky ImpResults(impresults), ResultPattern(0) {} 619193323Sed 620245431Sdim TreePattern *getPattern() const { return Pattern; } 621193323Sed unsigned getNumResults() const { return Results.size(); } 622193323Sed unsigned getNumOperands() const { return Operands.size(); } 623193323Sed unsigned getNumImpResults() const { return ImpResults.size(); } 624193323Sed const std::vector<Record*>& getImpResults() const { return ImpResults; } 625218893Sdim 626193323Sed void setResultPattern(TreePatternNode *R) { ResultPattern = R; } 627218893Sdim 628193323Sed Record *getResult(unsigned RN) const { 629193323Sed assert(RN < Results.size()); 630193323Sed return Results[RN]; 631193323Sed } 632218893Sdim 633193323Sed Record *getOperand(unsigned ON) const { 634193323Sed assert(ON < Operands.size()); 635193323Sed return Operands[ON]; 636193323Sed } 637193323Sed 638193323Sed Record *getImpResult(unsigned RN) const { 639193323Sed assert(RN < ImpResults.size()); 640193323Sed return ImpResults[RN]; 641193323Sed } 642218893Sdim 643193323Sed TreePatternNode *getResultPattern() const { return ResultPattern; } 644193323Sed}; 645218893Sdim 646193323Sed/// PatternToMatch - Used by CodeGenDAGPatterns to keep tab of patterns 647193323Sed/// processed to produce isel. 648204642Srdivackyclass PatternToMatch { 649204642Srdivackypublic: 650218893Sdim PatternToMatch(Record *srcrecord, ListInit *preds, 651193323Sed TreePatternNode *src, TreePatternNode *dst, 652193323Sed const std::vector<Record*> &dstregs, 653204642Srdivacky unsigned complexity, unsigned uid) 654218893Sdim : SrcRecord(srcrecord), Predicates(preds), SrcPattern(src), DstPattern(dst), 655204642Srdivacky Dstregs(dstregs), AddedComplexity(complexity), ID(uid) {} 656193323Sed 657218893Sdim Record *SrcRecord; // Originating Record for the pattern. 658193323Sed ListInit *Predicates; // Top level predicate conditions to match. 659193323Sed TreePatternNode *SrcPattern; // Source pattern to match. 660193323Sed TreePatternNode *DstPattern; // Resulting pattern. 661193323Sed std::vector<Record*> Dstregs; // Physical register defs being matched. 662193323Sed unsigned AddedComplexity; // Add to matching pattern complexity. 663204642Srdivacky unsigned ID; // Unique ID for the record. 664193323Sed 665218893Sdim Record *getSrcRecord() const { return SrcRecord; } 666193323Sed ListInit *getPredicates() const { return Predicates; } 667193323Sed TreePatternNode *getSrcPattern() const { return SrcPattern; } 668193323Sed TreePatternNode *getDstPattern() const { return DstPattern; } 669193323Sed const std::vector<Record*> &getDstRegs() const { return Dstregs; } 670193323Sed unsigned getAddedComplexity() const { return AddedComplexity; } 671193323Sed 672193323Sed std::string getPredicateCheck() const; 673218893Sdim 674206083Srdivacky /// Compute the complexity metric for the input pattern. This roughly 675206083Srdivacky /// corresponds to the number of nodes that are covered. 676206083Srdivacky unsigned getPatternComplexity(const CodeGenDAGPatterns &CGP) const; 677193323Sed}; 678193323Sed 679193323Sedclass CodeGenDAGPatterns { 680193323Sed RecordKeeper &Records; 681193323Sed CodeGenTarget Target; 682193323Sed std::vector<CodeGenIntrinsic> Intrinsics; 683193323Sed std::vector<CodeGenIntrinsic> TgtIntrinsics; 684218893Sdim 685245431Sdim std::map<Record*, SDNodeInfo, LessRecordByID> SDNodes; 686245431Sdim std::map<Record*, std::pair<Record*, std::string>, LessRecordByID> SDNodeXForms; 687245431Sdim std::map<Record*, ComplexPattern, LessRecordByID> ComplexPatterns; 688245431Sdim std::map<Record*, TreePattern*, LessRecordByID> PatternFragments; 689245431Sdim std::map<Record*, DAGDefaultOperand, LessRecordByID> DefaultOperands; 690245431Sdim std::map<Record*, DAGInstruction, LessRecordByID> Instructions; 691218893Sdim 692193323Sed // Specific SDNode definitions: 693193323Sed Record *intrinsic_void_sdnode; 694193323Sed Record *intrinsic_w_chain_sdnode, *intrinsic_wo_chain_sdnode; 695218893Sdim 696193323Sed /// PatternsToMatch - All of the things we are matching on the DAG. The first 697193323Sed /// value is the pattern to match, the second pattern is the result to 698193323Sed /// emit. 699193323Sed std::vector<PatternToMatch> PatternsToMatch; 700193323Sedpublic: 701218893Sdim CodeGenDAGPatterns(RecordKeeper &R); 702193323Sed ~CodeGenDAGPatterns(); 703218893Sdim 704193323Sed CodeGenTarget &getTargetInfo() { return Target; } 705193323Sed const CodeGenTarget &getTargetInfo() const { return Target; } 706218893Sdim 707193323Sed Record *getSDNodeNamed(const std::string &Name) const; 708218893Sdim 709193323Sed const SDNodeInfo &getSDNodeInfo(Record *R) const { 710193323Sed assert(SDNodes.count(R) && "Unknown node!"); 711193323Sed return SDNodes.find(R)->second; 712193323Sed } 713218893Sdim 714193323Sed // Node transformation lookups. 715193323Sed typedef std::pair<Record*, std::string> NodeXForm; 716193323Sed const NodeXForm &getSDNodeTransform(Record *R) const { 717193323Sed assert(SDNodeXForms.count(R) && "Invalid transform!"); 718193323Sed return SDNodeXForms.find(R)->second; 719193323Sed } 720218893Sdim 721245431Sdim typedef std::map<Record*, NodeXForm, LessRecordByID>::const_iterator 722198090Srdivacky nx_iterator; 723193323Sed nx_iterator nx_begin() const { return SDNodeXForms.begin(); } 724193323Sed nx_iterator nx_end() const { return SDNodeXForms.end(); } 725193323Sed 726218893Sdim 727193323Sed const ComplexPattern &getComplexPattern(Record *R) const { 728193323Sed assert(ComplexPatterns.count(R) && "Unknown addressing mode!"); 729193323Sed return ComplexPatterns.find(R)->second; 730193323Sed } 731218893Sdim 732193323Sed const CodeGenIntrinsic &getIntrinsic(Record *R) const { 733193323Sed for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i) 734193323Sed if (Intrinsics[i].TheDef == R) return Intrinsics[i]; 735193323Sed for (unsigned i = 0, e = TgtIntrinsics.size(); i != e; ++i) 736193323Sed if (TgtIntrinsics[i].TheDef == R) return TgtIntrinsics[i]; 737235633Sdim llvm_unreachable("Unknown intrinsic!"); 738193323Sed } 739218893Sdim 740193323Sed const CodeGenIntrinsic &getIntrinsicInfo(unsigned IID) const { 741193323Sed if (IID-1 < Intrinsics.size()) 742193323Sed return Intrinsics[IID-1]; 743193323Sed if (IID-Intrinsics.size()-1 < TgtIntrinsics.size()) 744193323Sed return TgtIntrinsics[IID-Intrinsics.size()-1]; 745235633Sdim llvm_unreachable("Bad intrinsic ID!"); 746193323Sed } 747218893Sdim 748193323Sed unsigned getIntrinsicID(Record *R) const { 749193323Sed for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i) 750193323Sed if (Intrinsics[i].TheDef == R) return i; 751193323Sed for (unsigned i = 0, e = TgtIntrinsics.size(); i != e; ++i) 752193323Sed if (TgtIntrinsics[i].TheDef == R) return i + Intrinsics.size(); 753235633Sdim llvm_unreachable("Unknown intrinsic!"); 754193323Sed } 755218893Sdim 756204642Srdivacky const DAGDefaultOperand &getDefaultOperand(Record *R) const { 757193323Sed assert(DefaultOperands.count(R) &&"Isn't an analyzed default operand!"); 758193323Sed return DefaultOperands.find(R)->second; 759193323Sed } 760218893Sdim 761193323Sed // Pattern Fragment information. 762193323Sed TreePattern *getPatternFragment(Record *R) const { 763193323Sed assert(PatternFragments.count(R) && "Invalid pattern fragment request!"); 764193323Sed return PatternFragments.find(R)->second; 765193323Sed } 766205407Srdivacky TreePattern *getPatternFragmentIfRead(Record *R) const { 767205407Srdivacky if (!PatternFragments.count(R)) return 0; 768205407Srdivacky return PatternFragments.find(R)->second; 769205407Srdivacky } 770218893Sdim 771245431Sdim typedef std::map<Record*, TreePattern*, LessRecordByID>::const_iterator 772198090Srdivacky pf_iterator; 773193323Sed pf_iterator pf_begin() const { return PatternFragments.begin(); } 774193323Sed pf_iterator pf_end() const { return PatternFragments.end(); } 775193323Sed 776193323Sed // Patterns to match information. 777193323Sed typedef std::vector<PatternToMatch>::const_iterator ptm_iterator; 778193323Sed ptm_iterator ptm_begin() const { return PatternsToMatch.begin(); } 779193323Sed ptm_iterator ptm_end() const { return PatternsToMatch.end(); } 780218893Sdim 781263509Sdim /// Parse the Pattern for an instruction, and insert the result in DAGInsts. 782263509Sdim typedef std::map<Record*, DAGInstruction, LessRecordByID> DAGInstMap; 783263509Sdim const DAGInstruction &parseInstructionPattern( 784263509Sdim CodeGenInstruction &CGI, ListInit *Pattern, 785263509Sdim DAGInstMap &DAGInsts); 786218893Sdim 787193323Sed const DAGInstruction &getInstruction(Record *R) const { 788193323Sed assert(Instructions.count(R) && "Unknown instruction!"); 789193323Sed return Instructions.find(R)->second; 790193323Sed } 791218893Sdim 792193323Sed Record *get_intrinsic_void_sdnode() const { 793193323Sed return intrinsic_void_sdnode; 794193323Sed } 795193323Sed Record *get_intrinsic_w_chain_sdnode() const { 796193323Sed return intrinsic_w_chain_sdnode; 797193323Sed } 798193323Sed Record *get_intrinsic_wo_chain_sdnode() const { 799193323Sed return intrinsic_wo_chain_sdnode; 800193323Sed } 801218893Sdim 802198396Srdivacky bool hasTargetIntrinsics() { return !TgtIntrinsics.empty(); } 803198396Srdivacky 804193323Sedprivate: 805193323Sed void ParseNodeInfo(); 806193323Sed void ParseNodeTransforms(); 807193323Sed void ParseComplexPatterns(); 808193323Sed void ParsePatternFragments(); 809193323Sed void ParseDefaultOperands(); 810193323Sed void ParseInstructions(); 811193323Sed void ParsePatterns(); 812193323Sed void InferInstructionFlags(); 813193323Sed void GenerateVariants(); 814245431Sdim void VerifyInstructionFlags(); 815218893Sdim 816245431Sdim void AddPatternToMatch(TreePattern *Pattern, const PatternToMatch &PTM); 817193323Sed void FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, 818193323Sed std::map<std::string, 819193323Sed TreePatternNode*> &InstInputs, 820193323Sed std::map<std::string, 821193323Sed TreePatternNode*> &InstResults, 822193323Sed std::vector<Record*> &InstImpResults); 823193323Sed}; 824193323Sed} // end namespace llvm 825193323Sed 826193323Sed#endif 827