utils/TableGen/DAGISelMatcher.h

   1 //===- DAGISelMatcher.h - Representation of DAG pattern matcher -----------===//
   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 #ifndef TBLGEN_DAGISELMATCHER_H
  11 #define TBLGEN_DAGISELMATCHER_H
  12
  13 #include "llvm/CodeGen/ValueTypes.h"
  14 #include "llvm/ADT/OwningPtr.h"
  15 #include "llvm/ADT/StringRef.h"
  16 #include "llvm/ADT/SmallVector.h"
  17 #include "llvm/Support/Casting.h"
  18
  19 namespace llvm {
  20   struct CodeGenRegister;
  21   class CodeGenDAGPatterns;
  22   class Matcher;
  23   class PatternToMatch;
  24   class raw_ostream;
  25   class ComplexPattern;
  26   class Record;
  27   class SDNodeInfo;
  28   class TreePredicateFn;
  29   class TreePattern;
  30
  31 Matcher *ConvertPatternToMatcher(const PatternToMatch &Pattern,unsigned Variant,
  32                                  const CodeGenDAGPatterns &CGP);
  33 Matcher *OptimizeMatcher(Matcher *Matcher, const CodeGenDAGPatterns &CGP);
  34 void EmitMatcherTable(const Matcher *Matcher, const CodeGenDAGPatterns &CGP,
  35                       raw_ostream &OS);
  36
  37
  38 /// Matcher - Base class for all the DAG ISel Matcher representation
  39 /// nodes.
  40 class Matcher {
  41   // The next matcher node that is executed after this one.  Null if this is the
  42   // last stage of a match.
  43   OwningPtr<Matcher> Next;
  44   virtual void anchor();
  45 public:
  46   enum KindTy {
  47     // Matcher state manipulation.
  48     Scope,                // Push a checking scope.
  49     RecordNode,           // Record the current node.
  50     RecordChild,          // Record a child of the current node.
  51     RecordMemRef,         // Record the memref in the current node.
  52     CaptureGlueInput,     // If the current node has an input glue, save it.
  53     MoveChild,            // Move current node to specified child.
  54     MoveParent,           // Move current node to parent.
  55
  56     // Predicate checking.
  57     CheckSame,            // Fail if not same as prev match.
  58     CheckPatternPredicate,
  59     CheckPredicate,       // Fail if node predicate fails.
  60     CheckOpcode,          // Fail if not opcode.
  61     SwitchOpcode,         // Dispatch based on opcode.
  62     CheckType,            // Fail if not correct type.
  63     SwitchType,           // Dispatch based on type.
  64     CheckChildType,       // Fail if child has wrong type.
  65     CheckInteger,         // Fail if wrong val.
  66     CheckCondCode,        // Fail if not condcode.
  67     CheckValueType,
  68     CheckComplexPat,
  69     CheckAndImm,
  70     CheckOrImm,
  71     CheckFoldableChainNode,
  72
  73     // Node creation/emisssion.
  74     EmitInteger,          // Create a TargetConstant
  75     EmitStringInteger,    // Create a TargetConstant from a string.
  76     EmitRegister,         // Create a register.
  77     EmitConvertToTarget,  // Convert a imm/fpimm to target imm/fpimm
  78     EmitMergeInputChains, // Merge together a chains for an input.
  79     EmitCopyToReg,        // Emit a copytoreg into a physreg.
  80     EmitNode,             // Create a DAG node
  81     EmitNodeXForm,        // Run a SDNodeXForm
  82     MarkGlueResults,      // Indicate which interior nodes have glue results.
  83     CompleteMatch,        // Finish a match and update the results.
  84     MorphNodeTo           // Build a node, finish a match and update results.
  85   };
  86   const KindTy Kind;
  87
  88 protected:
  89   Matcher(KindTy K) : Kind(K) {}
  90 public:
  91   virtual ~Matcher() {}
  92
  93   KindTy getKind() const { return Kind; }
  94
  95   Matcher *getNext() { return Next.get(); }
  96   const Matcher *getNext() const { return Next.get(); }
  97   void setNext(Matcher *C) { Next.reset(C); }
  98   Matcher *takeNext() { return Next.take(); }
  99
 100   OwningPtr<Matcher> &getNextPtr() { return Next; }
 101
 102   static inline bool classof(const Matcher *) { return true; }
 103
 104   bool isEqual(const Matcher *M) const {
 105     if (getKind() != M->getKind()) return false;
 106     return isEqualImpl(M);
 107   }
 108
 109   unsigned getHash() const {
 110     // Clear the high bit so we don't conflict with tombstones etc.
 111     return ((getHashImpl() << 4) ^ getKind()) & (~0U>>1);
 112   }
 113
 114   /// isSafeToReorderWithPatternPredicate - Return true if it is safe to sink a
 115   /// PatternPredicate node past this one.
 116   virtual bool isSafeToReorderWithPatternPredicate() const {
 117     return false;
 118   }
 119
 120   /// isSimplePredicateNode - Return true if this is a simple predicate that
 121   /// operates on the node or its children without potential side effects or a
 122   /// change of the current node.
 123   bool isSimplePredicateNode() const {
 124     switch (getKind()) {
 125     default: return false;
 126     case CheckSame:
 127     case CheckPatternPredicate:
 128     case CheckPredicate:
 129     case CheckOpcode:
 130     case CheckType:
 131     case CheckChildType:
 132     case CheckInteger:
 133     case CheckCondCode:
 134     case CheckValueType:
 135     case CheckAndImm:
 136     case CheckOrImm:
 137     case CheckFoldableChainNode:
 138       return true;
 139     }
 140   }
 141
 142   /// isSimplePredicateOrRecordNode - Return true if this is a record node or
 143   /// a simple predicate.
 144   bool isSimplePredicateOrRecordNode() const {
 145     return isSimplePredicateNode() ||
 146            getKind() == RecordNode || getKind() == RecordChild;
 147   }
 148
 149   /// unlinkNode - Unlink the specified node from this chain.  If Other == this,
 150   /// we unlink the next pointer and return it.  Otherwise we unlink Other from
 151   /// the list and return this.
 152   Matcher *unlinkNode(Matcher *Other);
 153
 154   /// canMoveBefore - Return true if this matcher is the same as Other, or if
 155   /// we can move this matcher past all of the nodes in-between Other and this
 156   /// node.  Other must be equal to or before this.
 157   bool canMoveBefore(const Matcher *Other) const;
 158
 159   /// canMoveBefore - Return true if it is safe to move the current matcher
 160   /// across the specified one.
 161   bool canMoveBeforeNode(const Matcher *Other) const;
 162
 163   /// isContradictory - Return true of these two matchers could never match on
 164   /// the same node.
 165   bool isContradictory(const Matcher *Other) const {
 166     // Since this predicate is reflexive, we canonicalize the ordering so that
 167     // we always match a node against nodes with kinds that are greater or equal
 168     // to them.  For example, we'll pass in a CheckType node as an argument to
 169     // the CheckOpcode method, not the other way around.
 170     if (getKind() < Other->getKind())
 171       return isContradictoryImpl(Other);
 172     return Other->isContradictoryImpl(this);
 173   }
 174
 175   void print(raw_ostream &OS, unsigned indent = 0) const;
 176   void printOne(raw_ostream &OS) const;
 177   void dump() const;
 178 protected:
 179   virtual void printImpl(raw_ostream &OS, unsigned indent) const = 0;
 180   virtual bool isEqualImpl(const Matcher *M) const = 0;
 181   virtual unsigned getHashImpl() const = 0;
 182   virtual bool isContradictoryImpl(const Matcher *M) const { return false; }
 183 };
 184
 185 /// ScopeMatcher - This attempts to match each of its children to find the first
 186 /// one that successfully matches.  If one child fails, it tries the next child.
 187 /// If none of the children match then this check fails.  It never has a 'next'.
 188 class ScopeMatcher : public Matcher {
 189   SmallVector<Matcher*, 4> Children;
 190 public:
 191   ScopeMatcher(Matcher *const *children, unsigned numchildren)
 192     : Matcher(Scope), Children(children, children+numchildren) {
 193   }
 194   virtual ~ScopeMatcher();
 195
 196   unsigned getNumChildren() const { return Children.size(); }
 197
 198   Matcher *getChild(unsigned i) { return Children[i]; }
 199   const Matcher *getChild(unsigned i) const { return Children[i]; }
 200
 201   void resetChild(unsigned i, Matcher *N) {
 202     delete Children[i];
 203     Children[i] = N;
 204   }
 205
 206   Matcher *takeChild(unsigned i) {
 207     Matcher *Res = Children[i];
 208     Children[i] = 0;
 209     return Res;
 210   }
 211
 212   void setNumChildren(unsigned NC) {
 213     if (NC < Children.size()) {
 214       // delete any children we're about to lose pointers to.
 215       for (unsigned i = NC, e = Children.size(); i != e; ++i)
 216         delete Children[i];
 217     }
 218     Children.resize(NC);
 219   }
 220
 221   static inline bool classof(const Matcher *N) {
 222     return N->getKind() == Scope;
 223   }
 224
 225 private:
 226   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 227   virtual bool isEqualImpl(const Matcher *M) const { return false; }
 228   virtual unsigned getHashImpl() const { return 12312; }
 229 };
 230
 231 /// RecordMatcher - Save the current node in the operand list.
 232 class RecordMatcher : public Matcher {
 233   /// WhatFor - This is a string indicating why we're recording this.  This
 234   /// should only be used for comment generation not anything semantic.
 235   std::string WhatFor;
 236
 237   /// ResultNo - The slot number in the RecordedNodes vector that this will be,
 238   /// just printed as a comment.
 239   unsigned ResultNo;
 240 public:
 241   RecordMatcher(const std::string &whatfor, unsigned resultNo)
 242     : Matcher(RecordNode), WhatFor(whatfor), ResultNo(resultNo) {}
 243
 244   const std::string &getWhatFor() const { return WhatFor; }
 245   unsigned getResultNo() const { return ResultNo; }
 246
 247   static inline bool classof(const Matcher *N) {
 248     return N->getKind() == RecordNode;
 249   }
 250
 251   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 252 private:
 253   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 254   virtual bool isEqualImpl(const Matcher *M) const { return true; }
 255   virtual unsigned getHashImpl() const { return 0; }
 256 };
 257
 258 /// RecordChildMatcher - Save a numbered child of the current node, or fail
 259 /// the match if it doesn't exist.  This is logically equivalent to:
 260 ///    MoveChild N + RecordNode + MoveParent.
 261 class RecordChildMatcher : public Matcher {
 262   unsigned ChildNo;
 263
 264   /// WhatFor - This is a string indicating why we're recording this.  This
 265   /// should only be used for comment generation not anything semantic.
 266   std::string WhatFor;
 267
 268   /// ResultNo - The slot number in the RecordedNodes vector that this will be,
 269   /// just printed as a comment.
 270   unsigned ResultNo;
 271 public:
 272   RecordChildMatcher(unsigned childno, const std::string &whatfor,
 273                      unsigned resultNo)
 274   : Matcher(RecordChild), ChildNo(childno), WhatFor(whatfor),
 275     ResultNo(resultNo) {}
 276
 277   unsigned getChildNo() const { return ChildNo; }
 278   const std::string &getWhatFor() const { return WhatFor; }
 279   unsigned getResultNo() const { return ResultNo; }
 280
 281   static inline bool classof(const Matcher *N) {
 282     return N->getKind() == RecordChild;
 283   }
 284
 285   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 286
 287 private:
 288   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 289   virtual bool isEqualImpl(const Matcher *M) const {
 290     return cast<RecordChildMatcher>(M)->getChildNo() == getChildNo();
 291   }
 292   virtual unsigned getHashImpl() const { return getChildNo(); }
 293 };
 294
 295 /// RecordMemRefMatcher - Save the current node's memref.
 296 class RecordMemRefMatcher : public Matcher {
 297 public:
 298   RecordMemRefMatcher() : Matcher(RecordMemRef) {}
 299
 300   static inline bool classof(const Matcher *N) {
 301     return N->getKind() == RecordMemRef;
 302   }
 303
 304   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 305
 306 private:
 307   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 308   virtual bool isEqualImpl(const Matcher *M) const { return true; }
 309   virtual unsigned getHashImpl() const { return 0; }
 310 };
 311
 312
 313 /// CaptureGlueInputMatcher - If the current record has a glue input, record
 314 /// it so that it is used as an input to the generated code.
 315 class CaptureGlueInputMatcher : public Matcher {
 316 public:
 317   CaptureGlueInputMatcher() : Matcher(CaptureGlueInput) {}
 318
 319   static inline bool classof(const Matcher *N) {
 320     return N->getKind() == CaptureGlueInput;
 321   }
 322
 323   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 324
 325 private:
 326   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 327   virtual bool isEqualImpl(const Matcher *M) const { return true; }
 328   virtual unsigned getHashImpl() const { return 0; }
 329 };
 330
 331 /// MoveChildMatcher - This tells the interpreter to move into the
 332 /// specified child node.
 333 class MoveChildMatcher : public Matcher {
 334   unsigned ChildNo;
 335 public:
 336   MoveChildMatcher(unsigned childNo) : Matcher(MoveChild), ChildNo(childNo) {}
 337
 338   unsigned getChildNo() const { return ChildNo; }
 339
 340   static inline bool classof(const Matcher *N) {
 341     return N->getKind() == MoveChild;
 342   }
 343
 344   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 345
 346 private:
 347   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 348   virtual bool isEqualImpl(const Matcher *M) const {
 349     return cast<MoveChildMatcher>(M)->getChildNo() == getChildNo();
 350   }
 351   virtual unsigned getHashImpl() const { return getChildNo(); }
 352 };
 353
 354 /// MoveParentMatcher - This tells the interpreter to move to the parent
 355 /// of the current node.
 356 class MoveParentMatcher : public Matcher {
 357 public:
 358   MoveParentMatcher() : Matcher(MoveParent) {}
 359
 360   static inline bool classof(const Matcher *N) {
 361     return N->getKind() == MoveParent;
 362   }
 363
 364   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 365
 366 private:
 367   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 368   virtual bool isEqualImpl(const Matcher *M) const { return true; }
 369   virtual unsigned getHashImpl() const { return 0; }
 370 };
 371
 372 /// CheckSameMatcher - This checks to see if this node is exactly the same
 373 /// node as the specified match that was recorded with 'Record'.  This is used
 374 /// when patterns have the same name in them, like '(mul GPR:$in, GPR:$in)'.
 375 class CheckSameMatcher : public Matcher {
 376   unsigned MatchNumber;
 377 public:
 378   CheckSameMatcher(unsigned matchnumber)
 379     : Matcher(CheckSame), MatchNumber(matchnumber) {}
 380
 381   unsigned getMatchNumber() const { return MatchNumber; }
 382
 383   static inline bool classof(const Matcher *N) {
 384     return N->getKind() == CheckSame;
 385   }
 386
 387   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 388
 389 private:
 390   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 391   virtual bool isEqualImpl(const Matcher *M) const {
 392     return cast<CheckSameMatcher>(M)->getMatchNumber() == getMatchNumber();
 393   }
 394   virtual unsigned getHashImpl() const { return getMatchNumber(); }
 395 };
 396
 397 /// CheckPatternPredicateMatcher - This checks the target-specific predicate
 398 /// to see if the entire pattern is capable of matching.  This predicate does
 399 /// not take a node as input.  This is used for subtarget feature checks etc.
 400 class CheckPatternPredicateMatcher : public Matcher {
 401   std::string Predicate;
 402 public:
 403   CheckPatternPredicateMatcher(StringRef predicate)
 404     : Matcher(CheckPatternPredicate), Predicate(predicate) {}
 405
 406   StringRef getPredicate() const { return Predicate; }
 407
 408   static inline bool classof(const Matcher *N) {
 409     return N->getKind() == CheckPatternPredicate;
 410   }
 411
 412   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 413
 414 private:
 415   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 416   virtual bool isEqualImpl(const Matcher *M) const {
 417     return cast<CheckPatternPredicateMatcher>(M)->getPredicate() == Predicate;
 418   }
 419   virtual unsigned getHashImpl() const;
 420 };
 421
 422 /// CheckPredicateMatcher - This checks the target-specific predicate to
 423 /// see if the node is acceptable.
 424 class CheckPredicateMatcher : public Matcher {
 425   TreePattern *Pred;
 426 public:
 427   CheckPredicateMatcher(const TreePredicateFn &pred);
 428
 429   TreePredicateFn getPredicate() const;
 430
 431   static inline bool classof(const Matcher *N) {
 432     return N->getKind() == CheckPredicate;
 433   }
 434
 435   // TODO: Ok?
 436   //virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 437
 438 private:
 439   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 440   virtual bool isEqualImpl(const Matcher *M) const {
 441     return cast<CheckPredicateMatcher>(M)->Pred == Pred;
 442   }
 443   virtual unsigned getHashImpl() const;
 444 };
 445
 446
 447 /// CheckOpcodeMatcher - This checks to see if the current node has the
 448 /// specified opcode, if not it fails to match.
 449 class CheckOpcodeMatcher : public Matcher {
 450   const SDNodeInfo &Opcode;
 451 public:
 452   CheckOpcodeMatcher(const SDNodeInfo &opcode)
 453     : Matcher(CheckOpcode), Opcode(opcode) {}
 454
 455   const SDNodeInfo &getOpcode() const { return Opcode; }
 456
 457   static inline bool classof(const Matcher *N) {
 458     return N->getKind() == CheckOpcode;
 459   }
 460
 461   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 462
 463 private:
 464   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 465   virtual bool isEqualImpl(const Matcher *M) const;
 466   virtual unsigned getHashImpl() const;
 467   virtual bool isContradictoryImpl(const Matcher *M) const;
 468 };
 469
 470 /// SwitchOpcodeMatcher - Switch based on the current node's opcode, dispatching
 471 /// to one matcher per opcode.  If the opcode doesn't match any of the cases,
 472 /// then the match fails.  This is semantically equivalent to a Scope node where
 473 /// every child does a CheckOpcode, but is much faster.
 474 class SwitchOpcodeMatcher : public Matcher {
 475   SmallVector<std::pair<const SDNodeInfo*, Matcher*>, 8> Cases;
 476 public:
 477   SwitchOpcodeMatcher(const std::pair<const SDNodeInfo*, Matcher*> *cases,
 478                       unsigned numcases)
 479     : Matcher(SwitchOpcode), Cases(cases, cases+numcases) {}
 480
 481   static inline bool classof(const Matcher *N) {
 482     return N->getKind() == SwitchOpcode;
 483   }
 484
 485   unsigned getNumCases() const { return Cases.size(); }
 486
 487   const SDNodeInfo &getCaseOpcode(unsigned i) const { return *Cases[i].first; }
 488   Matcher *getCaseMatcher(unsigned i) { return Cases[i].second; }
 489   const Matcher *getCaseMatcher(unsigned i) const { return Cases[i].second; }
 490
 491 private:
 492   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 493   virtual bool isEqualImpl(const Matcher *M) const { return false; }
 494   virtual unsigned getHashImpl() const { return 4123; }
 495 };
 496
 497 /// CheckTypeMatcher - This checks to see if the current node has the
 498 /// specified type at the specified result, if not it fails to match.
 499 class CheckTypeMatcher : public Matcher {
 500   MVT::SimpleValueType Type;
 501   unsigned ResNo;
 502 public:
 503   CheckTypeMatcher(MVT::SimpleValueType type, unsigned resno)
 504     : Matcher(CheckType), Type(type), ResNo(resno) {}
 505
 506   MVT::SimpleValueType getType() const { return Type; }
 507   unsigned getResNo() const { return ResNo; }
 508
 509   static inline bool classof(const Matcher *N) {
 510     return N->getKind() == CheckType;
 511   }
 512
 513   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 514
 515 private:
 516   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 517   virtual bool isEqualImpl(const Matcher *M) const {
 518     return cast<CheckTypeMatcher>(M)->Type == Type;
 519   }
 520   virtual unsigned getHashImpl() const { return Type; }
 521   virtual bool isContradictoryImpl(const Matcher *M) const;
 522 };
 523
 524 /// SwitchTypeMatcher - Switch based on the current node's type, dispatching
 525 /// to one matcher per case.  If the type doesn't match any of the cases,
 526 /// then the match fails.  This is semantically equivalent to a Scope node where
 527 /// every child does a CheckType, but is much faster.
 528 class SwitchTypeMatcher : public Matcher {
 529   SmallVector<std::pair<MVT::SimpleValueType, Matcher*>, 8> Cases;
 530 public:
 531   SwitchTypeMatcher(const std::pair<MVT::SimpleValueType, Matcher*> *cases,
 532                     unsigned numcases)
 533   : Matcher(SwitchType), Cases(cases, cases+numcases) {}
 534
 535   static inline bool classof(const Matcher *N) {
 536     return N->getKind() == SwitchType;
 537   }
 538
 539   unsigned getNumCases() const { return Cases.size(); }
 540
 541   MVT::SimpleValueType getCaseType(unsigned i) const { return Cases[i].first; }
 542   Matcher *getCaseMatcher(unsigned i) { return Cases[i].second; }
 543   const Matcher *getCaseMatcher(unsigned i) const { return Cases[i].second; }
 544
 545 private:
 546   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 547   virtual bool isEqualImpl(const Matcher *M) const { return false; }
 548   virtual unsigned getHashImpl() const { return 4123; }
 549 };
 550
 551
 552 /// CheckChildTypeMatcher - This checks to see if a child node has the
 553 /// specified type, if not it fails to match.
 554 class CheckChildTypeMatcher : public Matcher {
 555   unsigned ChildNo;
 556   MVT::SimpleValueType Type;
 557 public:
 558   CheckChildTypeMatcher(unsigned childno, MVT::SimpleValueType type)
 559     : Matcher(CheckChildType), ChildNo(childno), Type(type) {}
 560
 561   unsigned getChildNo() const { return ChildNo; }
 562   MVT::SimpleValueType getType() const { return Type; }
 563
 564   static inline bool classof(const Matcher *N) {
 565     return N->getKind() == CheckChildType;
 566   }
 567
 568   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 569
 570 private:
 571   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 572   virtual bool isEqualImpl(const Matcher *M) const {
 573     return cast<CheckChildTypeMatcher>(M)->ChildNo == ChildNo &&
 574            cast<CheckChildTypeMatcher>(M)->Type == Type;
 575   }
 576   virtual unsigned getHashImpl() const { return (Type << 3) | ChildNo; }
 577   virtual bool isContradictoryImpl(const Matcher *M) const;
 578 };
 579
 580
 581 /// CheckIntegerMatcher - This checks to see if the current node is a
 582 /// ConstantSDNode with the specified integer value, if not it fails to match.
 583 class CheckIntegerMatcher : public Matcher {
 584   int64_t Value;
 585 public:
 586   CheckIntegerMatcher(int64_t value)
 587     : Matcher(CheckInteger), Value(value) {}
 588
 589   int64_t getValue() const { return Value; }
 590
 591   static inline bool classof(const Matcher *N) {
 592     return N->getKind() == CheckInteger;
 593   }
 594
 595   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 596
 597 private:
 598   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 599   virtual bool isEqualImpl(const Matcher *M) const {
 600     return cast<CheckIntegerMatcher>(M)->Value == Value;
 601   }
 602   virtual unsigned getHashImpl() const { return Value; }
 603   virtual bool isContradictoryImpl(const Matcher *M) const;
 604 };
 605
 606 /// CheckCondCodeMatcher - This checks to see if the current node is a
 607 /// CondCodeSDNode with the specified condition, if not it fails to match.
 608 class CheckCondCodeMatcher : public Matcher {
 609   StringRef CondCodeName;
 610 public:
 611   CheckCondCodeMatcher(StringRef condcodename)
 612     : Matcher(CheckCondCode), CondCodeName(condcodename) {}
 613
 614   StringRef getCondCodeName() const { return CondCodeName; }
 615
 616   static inline bool classof(const Matcher *N) {
 617     return N->getKind() == CheckCondCode;
 618   }
 619
 620   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 621
 622 private:
 623   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 624   virtual bool isEqualImpl(const Matcher *M) const {
 625     return cast<CheckCondCodeMatcher>(M)->CondCodeName == CondCodeName;
 626   }
 627   virtual unsigned getHashImpl() const;
 628 };
 629
 630 /// CheckValueTypeMatcher - This checks to see if the current node is a
 631 /// VTSDNode with the specified type, if not it fails to match.
 632 class CheckValueTypeMatcher : public Matcher {
 633   StringRef TypeName;
 634 public:
 635   CheckValueTypeMatcher(StringRef type_name)
 636     : Matcher(CheckValueType), TypeName(type_name) {}
 637
 638   StringRef getTypeName() const { return TypeName; }
 639
 640   static inline bool classof(const Matcher *N) {
 641     return N->getKind() == CheckValueType;
 642   }
 643
 644   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 645
 646 private:
 647   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 648   virtual bool isEqualImpl(const Matcher *M) const {
 649     return cast<CheckValueTypeMatcher>(M)->TypeName == TypeName;
 650   }
 651   virtual unsigned getHashImpl() const;
 652   bool isContradictoryImpl(const Matcher *M) const;
 653 };
 654
 655
 656
 657 /// CheckComplexPatMatcher - This node runs the specified ComplexPattern on
 658 /// the current node.
 659 class CheckComplexPatMatcher : public Matcher {
 660   const ComplexPattern &Pattern;
 661
 662   /// MatchNumber - This is the recorded nodes slot that contains the node we
 663   /// want to match against.
 664   unsigned MatchNumber;
 665
 666   /// Name - The name of the node we're matching, for comment emission.
 667   std::string Name;
 668
 669   /// FirstResult - This is the first slot in the RecordedNodes list that the
 670   /// result of the match populates.
 671   unsigned FirstResult;
 672 public:
 673   CheckComplexPatMatcher(const ComplexPattern &pattern, unsigned matchnumber,
 674                          const std::string &name, unsigned firstresult)
 675     : Matcher(CheckComplexPat), Pattern(pattern), MatchNumber(matchnumber),
 676       Name(name), FirstResult(firstresult) {}
 677
 678   const ComplexPattern &getPattern() const { return Pattern; }
 679   unsigned getMatchNumber() const { return MatchNumber; }
 680
 681   const std::string getName() const { return Name; }
 682   unsigned getFirstResult() const { return FirstResult; }
 683
 684   static inline bool classof(const Matcher *N) {
 685     return N->getKind() == CheckComplexPat;
 686   }
 687
 688   // Not safe to move a pattern predicate past a complex pattern.
 689   virtual bool isSafeToReorderWithPatternPredicate() const { return false; }
 690
 691 private:
 692   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 693   virtual bool isEqualImpl(const Matcher *M) const {
 694     return &cast<CheckComplexPatMatcher>(M)->Pattern == &Pattern &&
 695            cast<CheckComplexPatMatcher>(M)->MatchNumber == MatchNumber;
 696   }
 697   virtual unsigned getHashImpl() const {
 698     return (unsigned)(intptr_t)&Pattern ^ MatchNumber;
 699   }
 700 };
 701
 702 /// CheckAndImmMatcher - This checks to see if the current node is an 'and'
 703 /// with something equivalent to the specified immediate.
 704 class CheckAndImmMatcher : public Matcher {
 705   int64_t Value;
 706 public:
 707   CheckAndImmMatcher(int64_t value)
 708     : Matcher(CheckAndImm), Value(value) {}
 709
 710   int64_t getValue() const { return Value; }
 711
 712   static inline bool classof(const Matcher *N) {
 713     return N->getKind() == CheckAndImm;
 714   }
 715
 716   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 717
 718 private:
 719   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 720   virtual bool isEqualImpl(const Matcher *M) const {
 721     return cast<CheckAndImmMatcher>(M)->Value == Value;
 722   }
 723   virtual unsigned getHashImpl() const { return Value; }
 724 };
 725
 726 /// CheckOrImmMatcher - This checks to see if the current node is an 'and'
 727 /// with something equivalent to the specified immediate.
 728 class CheckOrImmMatcher : public Matcher {
 729   int64_t Value;
 730 public:
 731   CheckOrImmMatcher(int64_t value)
 732     : Matcher(CheckOrImm), Value(value) {}
 733
 734   int64_t getValue() const { return Value; }
 735
 736   static inline bool classof(const Matcher *N) {
 737     return N->getKind() == CheckOrImm;
 738   }
 739
 740   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 741
 742 private:
 743   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 744   virtual bool isEqualImpl(const Matcher *M) const {
 745     return cast<CheckOrImmMatcher>(M)->Value == Value;
 746   }
 747   virtual unsigned getHashImpl() const { return Value; }
 748 };
 749
 750 /// CheckFoldableChainNodeMatcher - This checks to see if the current node
 751 /// (which defines a chain operand) is safe to fold into a larger pattern.
 752 class CheckFoldableChainNodeMatcher : public Matcher {
 753 public:
 754   CheckFoldableChainNodeMatcher()
 755     : Matcher(CheckFoldableChainNode) {}
 756
 757   static inline bool classof(const Matcher *N) {
 758     return N->getKind() == CheckFoldableChainNode;
 759   }
 760
 761   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 762
 763 private:
 764   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 765   virtual bool isEqualImpl(const Matcher *M) const { return true; }
 766   virtual unsigned getHashImpl() const { return 0; }
 767 };
 768
 769 /// EmitIntegerMatcher - This creates a new TargetConstant.
 770 class EmitIntegerMatcher : public Matcher {
 771   int64_t Val;
 772   MVT::SimpleValueType VT;
 773 public:
 774   EmitIntegerMatcher(int64_t val, MVT::SimpleValueType vt)
 775     : Matcher(EmitInteger), Val(val), VT(vt) {}
 776
 777   int64_t getValue() const { return Val; }
 778   MVT::SimpleValueType getVT() const { return VT; }
 779
 780   static inline bool classof(const Matcher *N) {
 781     return N->getKind() == EmitInteger;
 782   }
 783
 784 private:
 785   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 786   virtual bool isEqualImpl(const Matcher *M) const {
 787     return cast<EmitIntegerMatcher>(M)->Val == Val &&
 788            cast<EmitIntegerMatcher>(M)->VT == VT;
 789   }
 790   virtual unsigned getHashImpl() const { return (Val << 4) | VT; }
 791 };
 792
 793 /// EmitStringIntegerMatcher - A target constant whose value is represented
 794 /// by a string.
 795 class EmitStringIntegerMatcher : public Matcher {
 796   std::string Val;
 797   MVT::SimpleValueType VT;
 798 public:
 799   EmitStringIntegerMatcher(const std::string &val, MVT::SimpleValueType vt)
 800     : Matcher(EmitStringInteger), Val(val), VT(vt) {}
 801
 802   const std::string &getValue() const { return Val; }
 803   MVT::SimpleValueType getVT() const { return VT; }
 804
 805   static inline bool classof(const Matcher *N) {
 806     return N->getKind() == EmitStringInteger;
 807   }
 808
 809 private:
 810   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 811   virtual bool isEqualImpl(const Matcher *M) const {
 812     return cast<EmitStringIntegerMatcher>(M)->Val == Val &&
 813            cast<EmitStringIntegerMatcher>(M)->VT == VT;
 814   }
 815   virtual unsigned getHashImpl() const;
 816 };
 817
 818 /// EmitRegisterMatcher - This creates a new TargetConstant.
 819 class EmitRegisterMatcher : public Matcher {
 820   /// Reg - The def for the register that we're emitting.  If this is null, then
 821   /// this is a reference to zero_reg.
 822   const CodeGenRegister *Reg;
 823   MVT::SimpleValueType VT;
 824 public:
 825   EmitRegisterMatcher(const CodeGenRegister *reg, MVT::SimpleValueType vt)
 826     : Matcher(EmitRegister), Reg(reg), VT(vt) {}
 827
 828   const CodeGenRegister *getReg() const { return Reg; }
 829   MVT::SimpleValueType getVT() const { return VT; }
 830
 831   static inline bool classof(const Matcher *N) {
 832     return N->getKind() == EmitRegister;
 833   }
 834
 835 private:
 836   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 837   virtual bool isEqualImpl(const Matcher *M) const {
 838     return cast<EmitRegisterMatcher>(M)->Reg == Reg &&
 839            cast<EmitRegisterMatcher>(M)->VT == VT;
 840   }
 841   virtual unsigned getHashImpl() const {
 842     return ((unsigned)(intptr_t)Reg) << 4 | VT;
 843   }
 844 };
 845
 846 /// EmitConvertToTargetMatcher - Emit an operation that reads a specified
 847 /// recorded node and converts it from being a ISD::Constant to
 848 /// ISD::TargetConstant, likewise for ConstantFP.
 849 class EmitConvertToTargetMatcher : public Matcher {
 850   unsigned Slot;
 851 public:
 852   EmitConvertToTargetMatcher(unsigned slot)
 853     : Matcher(EmitConvertToTarget), Slot(slot) {}
 854
 855   unsigned getSlot() const { return Slot; }
 856
 857   static inline bool classof(const Matcher *N) {
 858     return N->getKind() == EmitConvertToTarget;
 859   }
 860
 861 private:
 862   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 863   virtual bool isEqualImpl(const Matcher *M) const {
 864     return cast<EmitConvertToTargetMatcher>(M)->Slot == Slot;
 865   }
 866   virtual unsigned getHashImpl() const { return Slot; }
 867 };
 868
 869 /// EmitMergeInputChainsMatcher - Emit a node that merges a list of input
 870 /// chains together with a token factor.  The list of nodes are the nodes in the
 871 /// matched pattern that have chain input/outputs.  This node adds all input
 872 /// chains of these nodes if they are not themselves a node in the pattern.
 873 class EmitMergeInputChainsMatcher : public Matcher {
 874   SmallVector<unsigned, 3> ChainNodes;
 875 public:
 876   EmitMergeInputChainsMatcher(const unsigned *nodes, unsigned NumNodes)
 877     : Matcher(EmitMergeInputChains), ChainNodes(nodes, nodes+NumNodes) {}
 878
 879   unsigned getNumNodes() const { return ChainNodes.size(); }
 880
 881   unsigned getNode(unsigned i) const {
 882     assert(i < ChainNodes.size());
 883     return ChainNodes[i];
 884   }
 885
 886   static inline bool classof(const Matcher *N) {
 887     return N->getKind() == EmitMergeInputChains;
 888   }
 889
 890 private:
 891   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 892   virtual bool isEqualImpl(const Matcher *M) const {
 893     return cast<EmitMergeInputChainsMatcher>(M)->ChainNodes == ChainNodes;
 894   }
 895   virtual unsigned getHashImpl() const;
 896 };
 897
 898 /// EmitCopyToRegMatcher - Emit a CopyToReg node from a value to a physreg,
 899 /// pushing the chain and glue results.
 900 ///
 901 class EmitCopyToRegMatcher : public Matcher {
 902   unsigned SrcSlot; // Value to copy into the physreg.
 903   Record *DestPhysReg;
 904 public:
 905   EmitCopyToRegMatcher(unsigned srcSlot, Record *destPhysReg)
 906     : Matcher(EmitCopyToReg), SrcSlot(srcSlot), DestPhysReg(destPhysReg) {}
 907
 908   unsigned getSrcSlot() const { return SrcSlot; }
 909   Record *getDestPhysReg() const { return DestPhysReg; }
 910
 911   static inline bool classof(const Matcher *N) {
 912     return N->getKind() == EmitCopyToReg;
 913   }
 914
 915 private:
 916   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 917   virtual bool isEqualImpl(const Matcher *M) const {
 918     return cast<EmitCopyToRegMatcher>(M)->SrcSlot == SrcSlot &&
 919            cast<EmitCopyToRegMatcher>(M)->DestPhysReg == DestPhysReg;
 920   }
 921   virtual unsigned getHashImpl() const {
 922     return SrcSlot ^ ((unsigned)(intptr_t)DestPhysReg << 4);
 923   }
 924 };
 925
 926
 927
 928 /// EmitNodeXFormMatcher - Emit an operation that runs an SDNodeXForm on a
 929 /// recorded node and records the result.
 930 class EmitNodeXFormMatcher : public Matcher {
 931   unsigned Slot;
 932   Record *NodeXForm;
 933 public:
 934   EmitNodeXFormMatcher(unsigned slot, Record *nodeXForm)
 935     : Matcher(EmitNodeXForm), Slot(slot), NodeXForm(nodeXForm) {}
 936
 937   unsigned getSlot() const { return Slot; }
 938   Record *getNodeXForm() const { return NodeXForm; }
 939
 940   static inline bool classof(const Matcher *N) {
 941     return N->getKind() == EmitNodeXForm;
 942   }
 943
 944 private:
 945   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 946   virtual bool isEqualImpl(const Matcher *M) const {
 947     return cast<EmitNodeXFormMatcher>(M)->Slot == Slot &&
 948            cast<EmitNodeXFormMatcher>(M)->NodeXForm == NodeXForm;
 949   }
 950   virtual unsigned getHashImpl() const {
 951     return Slot ^ ((unsigned)(intptr_t)NodeXForm << 4);
 952   }
 953 };
 954
 955 /// EmitNodeMatcherCommon - Common class shared between EmitNode and
 956 /// MorphNodeTo.
 957 class EmitNodeMatcherCommon : public Matcher {
 958   std::string OpcodeName;
 959   const SmallVector<MVT::SimpleValueType, 3> VTs;
 960   const SmallVector<unsigned, 6> Operands;
 961   bool HasChain, HasInGlue, HasOutGlue, HasMemRefs;
 962
 963   /// NumFixedArityOperands - If this is a fixed arity node, this is set to -1.
 964   /// If this is a varidic node, this is set to the number of fixed arity
 965   /// operands in the root of the pattern.  The rest are appended to this node.
 966   int NumFixedArityOperands;
 967 public:
 968   EmitNodeMatcherCommon(const std::string &opcodeName,
 969                         const MVT::SimpleValueType *vts, unsigned numvts,
 970                         const unsigned *operands, unsigned numops,
 971                         bool hasChain, bool hasInGlue, bool hasOutGlue,
 972                         bool hasmemrefs,
 973                         int numfixedarityoperands, bool isMorphNodeTo)
 974     : Matcher(isMorphNodeTo ? MorphNodeTo : EmitNode), OpcodeName(opcodeName),
 975       VTs(vts, vts+numvts), Operands(operands, operands+numops),
 976       HasChain(hasChain), HasInGlue(hasInGlue), HasOutGlue(hasOutGlue),
 977       HasMemRefs(hasmemrefs), NumFixedArityOperands(numfixedarityoperands) {}
 978
 979   const std::string &getOpcodeName() const { return OpcodeName; }
 980
 981   unsigned getNumVTs() const { return VTs.size(); }
 982   MVT::SimpleValueType getVT(unsigned i) const {
 983     assert(i < VTs.size());
 984     return VTs[i];
 985   }
 986
 987   unsigned getNumOperands() const { return Operands.size(); }
 988   unsigned getOperand(unsigned i) const {
 989     assert(i < Operands.size());
 990     return Operands[i];
 991   }
 992
 993   const SmallVectorImpl<MVT::SimpleValueType> &getVTList() const { return VTs; }
 994   const SmallVectorImpl<unsigned> &getOperandList() const { return Operands; }
 995
 996
 997   bool hasChain() const { return HasChain; }
 998   bool hasInFlag() const { return HasInGlue; }
 999   bool hasOutFlag() const { return HasOutGlue; }
1000   bool hasMemRefs() const { return HasMemRefs; }
1001   int getNumFixedArityOperands() const { return NumFixedArityOperands; }
1002
1003   static inline bool classof(const Matcher *N) {
1004     return N->getKind() == EmitNode || N->getKind() == MorphNodeTo;
1005   }
1006
1007 private:
1008   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
1009   virtual bool isEqualImpl(const Matcher *M) const;
1010   virtual unsigned getHashImpl() const;
1011 };
1012
1013 /// EmitNodeMatcher - This signals a successful match and generates a node.
1014 class EmitNodeMatcher : public EmitNodeMatcherCommon {
1015   virtual void anchor();
1016   unsigned FirstResultSlot;
1017 public:
1018   EmitNodeMatcher(const std::string &opcodeName,
1019                   const MVT::SimpleValueType *vts, unsigned numvts,
1020                   const unsigned *operands, unsigned numops,
1021                   bool hasChain, bool hasInFlag, bool hasOutFlag,
1022                   bool hasmemrefs,
1023                   int numfixedarityoperands, unsigned firstresultslot)
1024   : EmitNodeMatcherCommon(opcodeName, vts, numvts, operands, numops, hasChain,
1025                           hasInFlag, hasOutFlag, hasmemrefs,
1026                           numfixedarityoperands, false),
1027     FirstResultSlot(firstresultslot) {}
1028
1029   unsigned getFirstResultSlot() const { return FirstResultSlot; }
1030
1031   static inline bool classof(const Matcher *N) {
1032     return N->getKind() == EmitNode;
1033   }
1034
1035 };
1036
1037 class MorphNodeToMatcher : public EmitNodeMatcherCommon {
1038   virtual void anchor();
1039   const PatternToMatch &Pattern;
1040 public:
1041   MorphNodeToMatcher(const std::string &opcodeName,
1042                      const MVT::SimpleValueType *vts, unsigned numvts,
1043                      const unsigned *operands, unsigned numops,
1044                      bool hasChain, bool hasInFlag, bool hasOutFlag,
1045                      bool hasmemrefs,
1046                      int numfixedarityoperands, const PatternToMatch &pattern)
1047     : EmitNodeMatcherCommon(opcodeName, vts, numvts, operands, numops, hasChain,
1048                             hasInFlag, hasOutFlag, hasmemrefs,
1049                             numfixedarityoperands, true),
1050       Pattern(pattern) {
1051   }
1052
1053   const PatternToMatch &getPattern() const { return Pattern; }
1054
1055   static inline bool classof(const Matcher *N) {
1056     return N->getKind() == MorphNodeTo;
1057   }
1058 };
1059
1060 /// MarkGlueResultsMatcher - This node indicates which non-root nodes in the
1061 /// pattern produce glue.  This allows CompleteMatchMatcher to update them
1062 /// with the output glue of the resultant code.
1063 class MarkGlueResultsMatcher : public Matcher {
1064   SmallVector<unsigned, 3> GlueResultNodes;
1065 public:
1066   MarkGlueResultsMatcher(const unsigned *nodes, unsigned NumNodes)
1067     : Matcher(MarkGlueResults), GlueResultNodes(nodes, nodes+NumNodes) {}
1068
1069   unsigned getNumNodes() const { return GlueResultNodes.size(); }
1070
1071   unsigned getNode(unsigned i) const {
1072     assert(i < GlueResultNodes.size());
1073     return GlueResultNodes[i];
1074   }
1075
1076   static inline bool classof(const Matcher *N) {
1077     return N->getKind() == MarkGlueResults;
1078   }
1079
1080 private:
1081   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
1082   virtual bool isEqualImpl(const Matcher *M) const {
1083     return cast<MarkGlueResultsMatcher>(M)->GlueResultNodes == GlueResultNodes;
1084   }
1085   virtual unsigned getHashImpl() const;
1086 };
1087
1088 /// CompleteMatchMatcher - Complete a match by replacing the results of the
1089 /// pattern with the newly generated nodes.  This also prints a comment
1090 /// indicating the source and dest patterns.
1091 class CompleteMatchMatcher : public Matcher {
1092   SmallVector<unsigned, 2> Results;
1093   const PatternToMatch &Pattern;
1094 public:
1095   CompleteMatchMatcher(const unsigned *results, unsigned numresults,
1096                        const PatternToMatch &pattern)
1097   : Matcher(CompleteMatch), Results(results, results+numresults),
1098     Pattern(pattern) {}
1099
1100   unsigned getNumResults() const { return Results.size(); }
1101   unsigned getResult(unsigned R) const { return Results[R]; }
1102   const PatternToMatch &getPattern() const { return Pattern; }
1103
1104   static inline bool classof(const Matcher *N) {
1105     return N->getKind() == CompleteMatch;
1106   }
1107
1108 private:
1109   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
1110   virtual bool isEqualImpl(const Matcher *M) const {
1111     return cast<CompleteMatchMatcher>(M)->Results == Results &&
1112           &cast<CompleteMatchMatcher>(M)->Pattern == &Pattern;
1113   }
1114   virtual unsigned getHashImpl() const;
1115 };
1116
1117 } // end namespace llvm
1118
1119 #endif