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