CodeGenDAGPatterns.h revision 6d3d7656539188b496089a3313ed4d13759adba3
1//===- CodeGenDAGPatterns.h - Read DAG patterns from .td file ---*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file declares the CodeGenDAGPatterns class, which is used to read and 11// represent the patterns present in a .td file for instructions. 12// 13//===----------------------------------------------------------------------===// 14 15#ifndef CODEGEN_DAGPATTERNS_H 16#define CODEGEN_DAGPATTERNS_H 17 18#include "CodeGenTarget.h" 19#include "CodeGenIntrinsics.h" 20#include "llvm/ADT/SmallVector.h" 21#include "llvm/ADT/StringMap.h" 22#include "llvm/Support/ErrorHandling.h" 23#include <set> 24#include <algorithm> 25#include <vector> 26#include <map> 27 28namespace llvm { 29 class Record; 30 class Init; 31 class ListInit; 32 class DagInit; 33 class SDNodeInfo; 34 class TreePattern; 35 class TreePatternNode; 36 class CodeGenDAGPatterns; 37 class ComplexPattern; 38 39/// EEVT::DAGISelGenValueType - These are some extended forms of 40/// MVT::SimpleValueType that we use as lattice values during type inference. 41/// The existing MVT iAny, fAny and vAny types suffice to represent 42/// arbitrary integer, floating-point, and vector types, so only an unknown 43/// value is needed. 44namespace EEVT { 45 /// TypeSet - This is either empty if it's completely unknown, or holds a set 46 /// of types. It is used during type inference because register classes can 47 /// have multiple possible types and we don't know which one they get until 48 /// type inference is complete. 49 /// 50 /// TypeSet can have three states: 51 /// Vector is empty: The type is completely unknown, it can be any valid 52 /// target type. 53 /// Vector has multiple constrained types: (e.g. v4i32 + v4f32) it is one 54 /// of those types only. 55 /// Vector has one concrete type: The type is completely known. 56 /// 57 class TypeSet { 58 SmallVector<MVT::SimpleValueType, 4> TypeVec; 59 public: 60 TypeSet() {} 61 TypeSet(MVT::SimpleValueType VT, TreePattern &TP); 62 TypeSet(const std::vector<MVT::SimpleValueType> &VTList); 63 64 bool isCompletelyUnknown() const { return TypeVec.empty(); } 65 66 bool isConcrete() const { 67 if (TypeVec.size() != 1) return false; 68 unsigned char T = TypeVec[0]; (void)T; 69 assert(T < MVT::LAST_VALUETYPE || T == MVT::iPTR || T == MVT::iPTRAny); 70 return true; 71 } 72 73 MVT::SimpleValueType getConcrete() const { 74 assert(isConcrete() && "Type isn't concrete yet"); 75 return (MVT::SimpleValueType)TypeVec[0]; 76 } 77 78 bool isDynamicallyResolved() const { 79 return getConcrete() == MVT::iPTR || getConcrete() == MVT::iPTRAny; 80 } 81 82 const SmallVectorImpl<MVT::SimpleValueType> &getTypeList() const { 83 assert(!TypeVec.empty() && "Not a type list!"); 84 return TypeVec; 85 } 86 87 bool isVoid() const { 88 return TypeVec.size() == 1 && TypeVec[0] == MVT::isVoid; 89 } 90 91 /// hasIntegerTypes - Return true if this TypeSet contains any integer value 92 /// types. 93 bool hasIntegerTypes() const; 94 95 /// hasFloatingPointTypes - Return true if this TypeSet contains an fAny or 96 /// a floating point value type. 97 bool hasFloatingPointTypes() const; 98 99 /// hasVectorTypes - Return true if this TypeSet contains a vector value 100 /// type. 101 bool hasVectorTypes() const; 102 103 /// getName() - Return this TypeSet as a string. 104 std::string getName() const; 105 106 /// MergeInTypeInfo - This merges in type information from the specified 107 /// argument. If 'this' changes, it returns true. If the two types are 108 /// contradictory (e.g. merge f32 into i32) then this throws an exception. 109 bool MergeInTypeInfo(const EEVT::TypeSet &InVT, TreePattern &TP); 110 111 bool MergeInTypeInfo(MVT::SimpleValueType InVT, TreePattern &TP) { 112 return MergeInTypeInfo(EEVT::TypeSet(InVT, TP), TP); 113 } 114 115 /// Force this type list to only contain integer types. 116 bool EnforceInteger(TreePattern &TP); 117 118 /// Force this type list to only contain floating point types. 119 bool EnforceFloatingPoint(TreePattern &TP); 120 121 /// EnforceScalar - Remove all vector types from this type list. 122 bool EnforceScalar(TreePattern &TP); 123 124 /// EnforceVector - Remove all non-vector types from this type list. 125 bool EnforceVector(TreePattern &TP); 126 127 /// EnforceSmallerThan - 'this' must be a smaller VT than Other. Update 128 /// this an other based on this information. 129 bool EnforceSmallerThan(EEVT::TypeSet &Other, TreePattern &TP); 130 131 /// EnforceVectorEltTypeIs - 'this' is now constrainted to be a vector type 132 /// whose element is VT. 133 bool EnforceVectorEltTypeIs(EEVT::TypeSet &VT, TreePattern &TP); 134 135 /// EnforceVectorSubVectorTypeIs - 'this' is now constrainted to 136 /// be a vector type VT. 137 bool EnforceVectorSubVectorTypeIs(EEVT::TypeSet &VT, TreePattern &TP); 138 139 bool operator!=(const TypeSet &RHS) const { return TypeVec != RHS.TypeVec; } 140 bool operator==(const TypeSet &RHS) const { return TypeVec == RHS.TypeVec; } 141 142 private: 143 /// FillWithPossibleTypes - Set to all legal types and return true, only 144 /// valid on completely unknown type sets. If Pred is non-null, only MVTs 145 /// that pass the predicate are added. 146 bool FillWithPossibleTypes(TreePattern &TP, 147 bool (*Pred)(MVT::SimpleValueType) = 0, 148 const char *PredicateName = 0); 149 }; 150} 151 152/// Set type used to track multiply used variables in patterns 153typedef std::set<std::string> MultipleUseVarSet; 154 155/// SDTypeConstraint - This is a discriminated union of constraints, 156/// corresponding to the SDTypeConstraint tablegen class in Target.td. 157struct SDTypeConstraint { 158 SDTypeConstraint(Record *R); 159 160 unsigned OperandNo; // The operand # this constraint applies to. 161 enum { 162 SDTCisVT, SDTCisPtrTy, SDTCisInt, SDTCisFP, SDTCisVec, SDTCisSameAs, 163 SDTCisVTSmallerThanOp, SDTCisOpSmallerThanOp, SDTCisEltOfVec, 164 SDTCisSubVecOfVec 165 } ConstraintType; 166 167 union { // The discriminated union. 168 struct { 169 MVT::SimpleValueType VT; 170 } SDTCisVT_Info; 171 struct { 172 unsigned OtherOperandNum; 173 } SDTCisSameAs_Info; 174 struct { 175 unsigned OtherOperandNum; 176 } SDTCisVTSmallerThanOp_Info; 177 struct { 178 unsigned BigOperandNum; 179 } SDTCisOpSmallerThanOp_Info; 180 struct { 181 unsigned OtherOperandNum; 182 } SDTCisEltOfVec_Info; 183 struct { 184 unsigned OtherOperandNum; 185 } SDTCisSubVecOfVec_Info; 186 } x; 187 188 /// ApplyTypeConstraint - Given a node in a pattern, apply this type 189 /// constraint to the nodes operands. This returns true if it makes a 190 /// change, false otherwise. If a type contradiction is found, throw an 191 /// exception. 192 bool ApplyTypeConstraint(TreePatternNode *N, const SDNodeInfo &NodeInfo, 193 TreePattern &TP) const; 194}; 195 196/// SDNodeInfo - One of these records is created for each SDNode instance in 197/// the target .td file. This represents the various dag nodes we will be 198/// processing. 199class SDNodeInfo { 200 Record *Def; 201 std::string EnumName; 202 std::string SDClassName; 203 unsigned Properties; 204 unsigned NumResults; 205 int NumOperands; 206 std::vector<SDTypeConstraint> TypeConstraints; 207public: 208 SDNodeInfo(Record *R); // Parse the specified record. 209 210 unsigned getNumResults() const { return NumResults; } 211 212 /// getNumOperands - This is the number of operands required or -1 if 213 /// variadic. 214 int getNumOperands() const { return NumOperands; } 215 Record *getRecord() const { return Def; } 216 const std::string &getEnumName() const { return EnumName; } 217 const std::string &getSDClassName() const { return SDClassName; } 218 219 const std::vector<SDTypeConstraint> &getTypeConstraints() const { 220 return TypeConstraints; 221 } 222 223 /// getKnownType - If the type constraints on this node imply a fixed type 224 /// (e.g. all stores return void, etc), then return it as an 225 /// MVT::SimpleValueType. Otherwise, return MVT::Other. 226 MVT::SimpleValueType getKnownType(unsigned ResNo) const; 227 228 /// hasProperty - Return true if this node has the specified property. 229 /// 230 bool hasProperty(enum SDNP Prop) const { return Properties & (1 << Prop); } 231 232 /// ApplyTypeConstraints - Given a node in a pattern, apply the type 233 /// constraints for this node to the operands of the node. This returns 234 /// true if it makes a change, false otherwise. If a type contradiction is 235 /// found, throw an exception. 236 bool ApplyTypeConstraints(TreePatternNode *N, TreePattern &TP) const { 237 bool MadeChange = false; 238 for (unsigned i = 0, e = TypeConstraints.size(); i != e; ++i) 239 MadeChange |= TypeConstraints[i].ApplyTypeConstraint(N, *this, TP); 240 return MadeChange; 241 } 242}; 243 244/// TreePredicateFn - This is an abstraction that represents the predicates on 245/// a PatFrag node. This is a simple one-word wrapper around a pointer to 246/// provide nice accessors. 247class TreePredicateFn { 248 /// PatFragRec - This is the TreePattern for the PatFrag that we 249 /// originally came from. 250 TreePattern *PatFragRec; 251public: 252 /// TreePredicateFn constructor. Here 'N' is a subclass of PatFrag. 253 TreePredicateFn(TreePattern *N); 254 255 256 TreePattern *getOrigPatFragRecord() const { return PatFragRec; } 257 258 /// isAlwaysTrue - Return true if this is a noop predicate. 259 bool isAlwaysTrue() const; 260 261 bool isImmediatePattern() const { return !getImmCode().empty(); } 262 263 /// getImmediatePredicateCode - Return the code that evaluates this pattern if 264 /// this is an immediate predicate. It is an error to call this on a 265 /// non-immediate pattern. 266 std::string getImmediatePredicateCode() const { 267 std::string Result = getImmCode(); 268 assert(!Result.empty() && "Isn't an immediate pattern!"); 269 return Result; 270 } 271 272 273 bool operator==(const TreePredicateFn &RHS) const { 274 return PatFragRec == RHS.PatFragRec; 275 } 276 277 bool operator!=(const TreePredicateFn &RHS) const { return !(*this == RHS); } 278 279 /// Return the name to use in the generated code to reference this, this is 280 /// "Predicate_foo" if from a pattern fragment "foo". 281 std::string getFnName() const; 282 283 /// getCodeToRunOnSDNode - Return the code for the function body that 284 /// evaluates this predicate. The argument is expected to be in "Node", 285 /// not N. This handles casting and conversion to a concrete node type as 286 /// appropriate. 287 std::string getCodeToRunOnSDNode() const; 288 289private: 290 std::string getPredCode() const; 291 std::string getImmCode() const; 292}; 293 294 295/// FIXME: TreePatternNode's can be shared in some cases (due to dag-shaped 296/// patterns), and as such should be ref counted. We currently just leak all 297/// TreePatternNode objects! 298class TreePatternNode { 299 /// The type of each node result. Before and during type inference, each 300 /// result may be a set of possible types. After (successful) type inference, 301 /// each is a single concrete type. 302 SmallVector<EEVT::TypeSet, 1> Types; 303 304 /// Operator - The Record for the operator if this is an interior node (not 305 /// a leaf). 306 Record *Operator; 307 308 /// Val - The init value (e.g. the "GPRC" record, or "7") for a leaf. 309 /// 310 Init *Val; 311 312 /// Name - The name given to this node with the :$foo notation. 313 /// 314 std::string Name; 315 316 /// PredicateFns - The predicate functions to execute on this node to check 317 /// for a match. If this list is empty, no predicate is involved. 318 std::vector<TreePredicateFn> PredicateFns; 319 320 /// TransformFn - The transformation function to execute on this node before 321 /// it can be substituted into the resulting instruction on a pattern match. 322 Record *TransformFn; 323 324 std::vector<TreePatternNode*> Children; 325public: 326 TreePatternNode(Record *Op, const std::vector<TreePatternNode*> &Ch, 327 unsigned NumResults) 328 : Operator(Op), Val(0), TransformFn(0), Children(Ch) { 329 Types.resize(NumResults); 330 } 331 TreePatternNode(Init *val, unsigned NumResults) // leaf ctor 332 : Operator(0), Val(val), TransformFn(0) { 333 Types.resize(NumResults); 334 } 335 ~TreePatternNode(); 336 337 const std::string &getName() const { return Name; } 338 void setName(StringRef N) { Name.assign(N.begin(), N.end()); } 339 340 bool isLeaf() const { return Val != 0; } 341 342 // Type accessors. 343 unsigned getNumTypes() const { return Types.size(); } 344 MVT::SimpleValueType getType(unsigned ResNo) const { 345 return Types[ResNo].getConcrete(); 346 } 347 const SmallVectorImpl<EEVT::TypeSet> &getExtTypes() const { return Types; } 348 const EEVT::TypeSet &getExtType(unsigned ResNo) const { return Types[ResNo]; } 349 EEVT::TypeSet &getExtType(unsigned ResNo) { return Types[ResNo]; } 350 void setType(unsigned ResNo, const EEVT::TypeSet &T) { Types[ResNo] = T; } 351 352 bool hasTypeSet(unsigned ResNo) const { 353 return Types[ResNo].isConcrete(); 354 } 355 bool isTypeCompletelyUnknown(unsigned ResNo) const { 356 return Types[ResNo].isCompletelyUnknown(); 357 } 358 bool isTypeDynamicallyResolved(unsigned ResNo) const { 359 return Types[ResNo].isDynamicallyResolved(); 360 } 361 362 Init *getLeafValue() const { assert(isLeaf()); return Val; } 363 Record *getOperator() const { assert(!isLeaf()); return Operator; } 364 365 unsigned getNumChildren() const { return Children.size(); } 366 TreePatternNode *getChild(unsigned N) const { return Children[N]; } 367 void setChild(unsigned i, TreePatternNode *N) { 368 Children[i] = N; 369 } 370 371 /// hasChild - Return true if N is any of our children. 372 bool hasChild(const TreePatternNode *N) const { 373 for (unsigned i = 0, e = Children.size(); i != e; ++i) 374 if (Children[i] == N) return true; 375 return false; 376 } 377 378 bool hasAnyPredicate() const { return !PredicateFns.empty(); } 379 380 const std::vector<TreePredicateFn> &getPredicateFns() const { 381 return PredicateFns; 382 } 383 void clearPredicateFns() { PredicateFns.clear(); } 384 void setPredicateFns(const std::vector<TreePredicateFn> &Fns) { 385 assert(PredicateFns.empty() && "Overwriting non-empty predicate list!"); 386 PredicateFns = Fns; 387 } 388 void addPredicateFn(const TreePredicateFn &Fn) { 389 assert(!Fn.isAlwaysTrue() && "Empty predicate string!"); 390 if (std::find(PredicateFns.begin(), PredicateFns.end(), Fn) == 391 PredicateFns.end()) 392 PredicateFns.push_back(Fn); 393 } 394 395 Record *getTransformFn() const { return TransformFn; } 396 void setTransformFn(Record *Fn) { TransformFn = Fn; } 397 398 /// getIntrinsicInfo - If this node corresponds to an intrinsic, return the 399 /// CodeGenIntrinsic information for it, otherwise return a null pointer. 400 const CodeGenIntrinsic *getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const; 401 402 /// getComplexPatternInfo - If this node corresponds to a ComplexPattern, 403 /// return the ComplexPattern information, otherwise return null. 404 const ComplexPattern * 405 getComplexPatternInfo(const CodeGenDAGPatterns &CGP) const; 406 407 /// NodeHasProperty - Return true if this node has the specified property. 408 bool NodeHasProperty(SDNP Property, const CodeGenDAGPatterns &CGP) const; 409 410 /// TreeHasProperty - Return true if any node in this tree has the specified 411 /// property. 412 bool TreeHasProperty(SDNP Property, const CodeGenDAGPatterns &CGP) const; 413 414 /// isCommutativeIntrinsic - Return true if the node is an intrinsic which is 415 /// marked isCommutative. 416 bool isCommutativeIntrinsic(const CodeGenDAGPatterns &CDP) const; 417 418 void print(raw_ostream &OS) const; 419 void dump() const; 420 421public: // Higher level manipulation routines. 422 423 /// clone - Return a new copy of this tree. 424 /// 425 TreePatternNode *clone() const; 426 427 /// RemoveAllTypes - Recursively strip all the types of this tree. 428 void RemoveAllTypes(); 429 430 /// isIsomorphicTo - Return true if this node is recursively isomorphic to 431 /// the specified node. For this comparison, all of the state of the node 432 /// is considered, except for the assigned name. Nodes with differing names 433 /// that are otherwise identical are considered isomorphic. 434 bool isIsomorphicTo(const TreePatternNode *N, 435 const MultipleUseVarSet &DepVars) const; 436 437 /// SubstituteFormalArguments - Replace the formal arguments in this tree 438 /// with actual values specified by ArgMap. 439 void SubstituteFormalArguments(std::map<std::string, 440 TreePatternNode*> &ArgMap); 441 442 /// InlinePatternFragments - If this pattern refers to any pattern 443 /// fragments, inline them into place, giving us a pattern without any 444 /// PatFrag references. 445 TreePatternNode *InlinePatternFragments(TreePattern &TP); 446 447 /// ApplyTypeConstraints - Apply all of the type constraints relevant to 448 /// this node and its children in the tree. This returns true if it makes a 449 /// change, false otherwise. If a type contradiction is found, throw an 450 /// exception. 451 bool ApplyTypeConstraints(TreePattern &TP, bool NotRegisters); 452 453 /// UpdateNodeType - Set the node type of N to VT if VT contains 454 /// information. If N already contains a conflicting type, then throw an 455 /// exception. This returns true if any information was updated. 456 /// 457 bool UpdateNodeType(unsigned ResNo, const EEVT::TypeSet &InTy, 458 TreePattern &TP) { 459 return Types[ResNo].MergeInTypeInfo(InTy, TP); 460 } 461 462 bool UpdateNodeType(unsigned ResNo, MVT::SimpleValueType InTy, 463 TreePattern &TP) { 464 return Types[ResNo].MergeInTypeInfo(EEVT::TypeSet(InTy, TP), TP); 465 } 466 467 /// ContainsUnresolvedType - Return true if this tree contains any 468 /// unresolved types. 469 bool ContainsUnresolvedType() const { 470 for (unsigned i = 0, e = Types.size(); i != e; ++i) 471 if (!Types[i].isConcrete()) return true; 472 473 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 474 if (getChild(i)->ContainsUnresolvedType()) return true; 475 return false; 476 } 477 478 /// canPatternMatch - If it is impossible for this pattern to match on this 479 /// target, fill in Reason and return false. Otherwise, return true. 480 bool canPatternMatch(std::string &Reason, const CodeGenDAGPatterns &CDP); 481}; 482 483inline raw_ostream &operator<<(raw_ostream &OS, const TreePatternNode &TPN) { 484 TPN.print(OS); 485 return OS; 486} 487 488 489/// TreePattern - Represent a pattern, used for instructions, pattern 490/// fragments, etc. 491/// 492class TreePattern { 493 /// Trees - The list of pattern trees which corresponds to this pattern. 494 /// Note that PatFrag's only have a single tree. 495 /// 496 std::vector<TreePatternNode*> Trees; 497 498 /// NamedNodes - This is all of the nodes that have names in the trees in this 499 /// pattern. 500 StringMap<SmallVector<TreePatternNode*,1> > NamedNodes; 501 502 /// TheRecord - The actual TableGen record corresponding to this pattern. 503 /// 504 Record *TheRecord; 505 506 /// Args - This is a list of all of the arguments to this pattern (for 507 /// PatFrag patterns), which are the 'node' markers in this pattern. 508 std::vector<std::string> Args; 509 510 /// CDP - the top-level object coordinating this madness. 511 /// 512 CodeGenDAGPatterns &CDP; 513 514 /// isInputPattern - True if this is an input pattern, something to match. 515 /// False if this is an output pattern, something to emit. 516 bool isInputPattern; 517public: 518 519 /// TreePattern constructor - Parse the specified DagInits into the 520 /// current record. 521 TreePattern(Record *TheRec, ListInit *RawPat, bool isInput, 522 CodeGenDAGPatterns &ise); 523 TreePattern(Record *TheRec, DagInit *Pat, bool isInput, 524 CodeGenDAGPatterns &ise); 525 TreePattern(Record *TheRec, TreePatternNode *Pat, bool isInput, 526 CodeGenDAGPatterns &ise); 527 528 /// getTrees - Return the tree patterns which corresponds to this pattern. 529 /// 530 const std::vector<TreePatternNode*> &getTrees() const { return Trees; } 531 unsigned getNumTrees() const { return Trees.size(); } 532 TreePatternNode *getTree(unsigned i) const { return Trees[i]; } 533 TreePatternNode *getOnlyTree() const { 534 assert(Trees.size() == 1 && "Doesn't have exactly one pattern!"); 535 return Trees[0]; 536 } 537 538 const StringMap<SmallVector<TreePatternNode*,1> > &getNamedNodesMap() { 539 if (NamedNodes.empty()) 540 ComputeNamedNodes(); 541 return NamedNodes; 542 } 543 544 /// getRecord - Return the actual TableGen record corresponding to this 545 /// pattern. 546 /// 547 Record *getRecord() const { return TheRecord; } 548 549 unsigned getNumArgs() const { return Args.size(); } 550 const std::string &getArgName(unsigned i) const { 551 assert(i < Args.size() && "Argument reference out of range!"); 552 return Args[i]; 553 } 554 std::vector<std::string> &getArgList() { return Args; } 555 556 CodeGenDAGPatterns &getDAGPatterns() const { return CDP; } 557 558 /// InlinePatternFragments - If this pattern refers to any pattern 559 /// fragments, inline them into place, giving us a pattern without any 560 /// PatFrag references. 561 void InlinePatternFragments() { 562 for (unsigned i = 0, e = Trees.size(); i != e; ++i) 563 Trees[i] = Trees[i]->InlinePatternFragments(*this); 564 } 565 566 /// InferAllTypes - Infer/propagate as many types throughout the expression 567 /// patterns as possible. Return true if all types are inferred, false 568 /// otherwise. Throw an exception if a type contradiction is found. 569 bool InferAllTypes(const StringMap<SmallVector<TreePatternNode*,1> > 570 *NamedTypes=0); 571 572 /// error - Throw an exception, prefixing it with information about this 573 /// pattern. 574 void error(const std::string &Msg) const; 575 576 void print(raw_ostream &OS) const; 577 void dump() const; 578 579private: 580 TreePatternNode *ParseTreePattern(Init *DI, StringRef OpName); 581 void ComputeNamedNodes(); 582 void ComputeNamedNodes(TreePatternNode *N); 583}; 584 585/// DAGDefaultOperand - One of these is created for each OperandWithDefaultOps 586/// that has a set ExecuteAlways / DefaultOps field. 587struct DAGDefaultOperand { 588 std::vector<TreePatternNode*> DefaultOps; 589}; 590 591class DAGInstruction { 592 TreePattern *Pattern; 593 std::vector<Record*> Results; 594 std::vector<Record*> Operands; 595 std::vector<Record*> ImpResults; 596 TreePatternNode *ResultPattern; 597public: 598 DAGInstruction(TreePattern *TP, 599 const std::vector<Record*> &results, 600 const std::vector<Record*> &operands, 601 const std::vector<Record*> &impresults) 602 : Pattern(TP), Results(results), Operands(operands), 603 ImpResults(impresults), ResultPattern(0) {} 604 605 const TreePattern *getPattern() const { return Pattern; } 606 unsigned getNumResults() const { return Results.size(); } 607 unsigned getNumOperands() const { return Operands.size(); } 608 unsigned getNumImpResults() const { return ImpResults.size(); } 609 const std::vector<Record*>& getImpResults() const { return ImpResults; } 610 611 void setResultPattern(TreePatternNode *R) { ResultPattern = R; } 612 613 Record *getResult(unsigned RN) const { 614 assert(RN < Results.size()); 615 return Results[RN]; 616 } 617 618 Record *getOperand(unsigned ON) const { 619 assert(ON < Operands.size()); 620 return Operands[ON]; 621 } 622 623 Record *getImpResult(unsigned RN) const { 624 assert(RN < ImpResults.size()); 625 return ImpResults[RN]; 626 } 627 628 TreePatternNode *getResultPattern() const { return ResultPattern; } 629}; 630 631/// PatternToMatch - Used by CodeGenDAGPatterns to keep tab of patterns 632/// processed to produce isel. 633class PatternToMatch { 634public: 635 PatternToMatch(Record *srcrecord, ListInit *preds, 636 TreePatternNode *src, TreePatternNode *dst, 637 const std::vector<Record*> &dstregs, 638 unsigned complexity, unsigned uid) 639 : SrcRecord(srcrecord), Predicates(preds), SrcPattern(src), DstPattern(dst), 640 Dstregs(dstregs), AddedComplexity(complexity), ID(uid) {} 641 642 Record *SrcRecord; // Originating Record for the pattern. 643 ListInit *Predicates; // Top level predicate conditions to match. 644 TreePatternNode *SrcPattern; // Source pattern to match. 645 TreePatternNode *DstPattern; // Resulting pattern. 646 std::vector<Record*> Dstregs; // Physical register defs being matched. 647 unsigned AddedComplexity; // Add to matching pattern complexity. 648 unsigned ID; // Unique ID for the record. 649 650 Record *getSrcRecord() const { return SrcRecord; } 651 ListInit *getPredicates() const { return Predicates; } 652 TreePatternNode *getSrcPattern() const { return SrcPattern; } 653 TreePatternNode *getDstPattern() const { return DstPattern; } 654 const std::vector<Record*> &getDstRegs() const { return Dstregs; } 655 unsigned getAddedComplexity() const { return AddedComplexity; } 656 657 std::string getPredicateCheck() const; 658 659 /// Compute the complexity metric for the input pattern. This roughly 660 /// corresponds to the number of nodes that are covered. 661 unsigned getPatternComplexity(const CodeGenDAGPatterns &CGP) const; 662}; 663 664// Deterministic comparison of Record*. 665struct RecordPtrCmp { 666 bool operator()(const Record *LHS, const Record *RHS) const; 667}; 668 669class CodeGenDAGPatterns { 670 RecordKeeper &Records; 671 CodeGenTarget Target; 672 std::vector<CodeGenIntrinsic> Intrinsics; 673 std::vector<CodeGenIntrinsic> TgtIntrinsics; 674 675 std::map<Record*, SDNodeInfo, RecordPtrCmp> SDNodes; 676 std::map<Record*, std::pair<Record*, std::string>, RecordPtrCmp> SDNodeXForms; 677 std::map<Record*, ComplexPattern, RecordPtrCmp> ComplexPatterns; 678 std::map<Record*, TreePattern*, RecordPtrCmp> PatternFragments; 679 std::map<Record*, DAGDefaultOperand, RecordPtrCmp> DefaultOperands; 680 std::map<Record*, DAGInstruction, RecordPtrCmp> Instructions; 681 682 // Specific SDNode definitions: 683 Record *intrinsic_void_sdnode; 684 Record *intrinsic_w_chain_sdnode, *intrinsic_wo_chain_sdnode; 685 686 /// PatternsToMatch - All of the things we are matching on the DAG. The first 687 /// value is the pattern to match, the second pattern is the result to 688 /// emit. 689 std::vector<PatternToMatch> PatternsToMatch; 690public: 691 CodeGenDAGPatterns(RecordKeeper &R); 692 ~CodeGenDAGPatterns(); 693 694 CodeGenTarget &getTargetInfo() { return Target; } 695 const CodeGenTarget &getTargetInfo() const { return Target; } 696 697 Record *getSDNodeNamed(const std::string &Name) const; 698 699 const SDNodeInfo &getSDNodeInfo(Record *R) const { 700 assert(SDNodes.count(R) && "Unknown node!"); 701 return SDNodes.find(R)->second; 702 } 703 704 // Node transformation lookups. 705 typedef std::pair<Record*, std::string> NodeXForm; 706 const NodeXForm &getSDNodeTransform(Record *R) const { 707 assert(SDNodeXForms.count(R) && "Invalid transform!"); 708 return SDNodeXForms.find(R)->second; 709 } 710 711 typedef std::map<Record*, NodeXForm, RecordPtrCmp>::const_iterator 712 nx_iterator; 713 nx_iterator nx_begin() const { return SDNodeXForms.begin(); } 714 nx_iterator nx_end() const { return SDNodeXForms.end(); } 715 716 717 const ComplexPattern &getComplexPattern(Record *R) const { 718 assert(ComplexPatterns.count(R) && "Unknown addressing mode!"); 719 return ComplexPatterns.find(R)->second; 720 } 721 722 const CodeGenIntrinsic &getIntrinsic(Record *R) const { 723 for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i) 724 if (Intrinsics[i].TheDef == R) return Intrinsics[i]; 725 for (unsigned i = 0, e = TgtIntrinsics.size(); i != e; ++i) 726 if (TgtIntrinsics[i].TheDef == R) return TgtIntrinsics[i]; 727 llvm_unreachable("Unknown intrinsic!"); 728 } 729 730 const CodeGenIntrinsic &getIntrinsicInfo(unsigned IID) const { 731 if (IID-1 < Intrinsics.size()) 732 return Intrinsics[IID-1]; 733 if (IID-Intrinsics.size()-1 < TgtIntrinsics.size()) 734 return TgtIntrinsics[IID-Intrinsics.size()-1]; 735 llvm_unreachable("Bad intrinsic ID!"); 736 } 737 738 unsigned getIntrinsicID(Record *R) const { 739 for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i) 740 if (Intrinsics[i].TheDef == R) return i; 741 for (unsigned i = 0, e = TgtIntrinsics.size(); i != e; ++i) 742 if (TgtIntrinsics[i].TheDef == R) return i + Intrinsics.size(); 743 llvm_unreachable("Unknown intrinsic!"); 744 } 745 746 const DAGDefaultOperand &getDefaultOperand(Record *R) const { 747 assert(DefaultOperands.count(R) &&"Isn't an analyzed default operand!"); 748 return DefaultOperands.find(R)->second; 749 } 750 751 // Pattern Fragment information. 752 TreePattern *getPatternFragment(Record *R) const { 753 assert(PatternFragments.count(R) && "Invalid pattern fragment request!"); 754 return PatternFragments.find(R)->second; 755 } 756 TreePattern *getPatternFragmentIfRead(Record *R) const { 757 if (!PatternFragments.count(R)) return 0; 758 return PatternFragments.find(R)->second; 759 } 760 761 typedef std::map<Record*, TreePattern*, RecordPtrCmp>::const_iterator 762 pf_iterator; 763 pf_iterator pf_begin() const { return PatternFragments.begin(); } 764 pf_iterator pf_end() const { return PatternFragments.end(); } 765 766 // Patterns to match information. 767 typedef std::vector<PatternToMatch>::const_iterator ptm_iterator; 768 ptm_iterator ptm_begin() const { return PatternsToMatch.begin(); } 769 ptm_iterator ptm_end() const { return PatternsToMatch.end(); } 770 771 772 773 const DAGInstruction &getInstruction(Record *R) const { 774 assert(Instructions.count(R) && "Unknown instruction!"); 775 return Instructions.find(R)->second; 776 } 777 778 Record *get_intrinsic_void_sdnode() const { 779 return intrinsic_void_sdnode; 780 } 781 Record *get_intrinsic_w_chain_sdnode() const { 782 return intrinsic_w_chain_sdnode; 783 } 784 Record *get_intrinsic_wo_chain_sdnode() const { 785 return intrinsic_wo_chain_sdnode; 786 } 787 788 bool hasTargetIntrinsics() { return !TgtIntrinsics.empty(); } 789 790private: 791 void ParseNodeInfo(); 792 void ParseNodeTransforms(); 793 void ParseComplexPatterns(); 794 void ParsePatternFragments(); 795 void ParseDefaultOperands(); 796 void ParseInstructions(); 797 void ParsePatterns(); 798 void InferInstructionFlags(); 799 void GenerateVariants(); 800 void VerifyInstructionFlags(); 801 802 void AddPatternToMatch(const TreePattern *Pattern, const PatternToMatch &PTM); 803 void FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, 804 std::map<std::string, 805 TreePatternNode*> &InstInputs, 806 std::map<std::string, 807 TreePatternNode*> &InstResults, 808 std::vector<Record*> &InstImpResults); 809}; 810} // end namespace llvm 811 812#endif 813