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/ADT/OwningPtr.h"
  14 #include "llvm/ADT/SmallVector.h"
  15 #include "llvm/ADT/StringRef.h"
  16 #include "llvm/CodeGen/ValueTypes.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     CheckChildSame,       // Fail if child not same as prev match.
  59     CheckPatternPredicate,
  60     CheckPredicate,       // Fail if node predicate fails.
  61     CheckOpcode,          // Fail if not opcode.
  62     SwitchOpcode,         // Dispatch based on opcode.
  63     CheckType,            // Fail if not correct type.
  64     SwitchType,           // Dispatch based on type.
  65     CheckChildType,       // Fail if child has wrong type.
  66     CheckInteger,         // Fail if wrong val.
  67     CheckCondCode,        // Fail if not condcode.
  68     CheckValueType,
  69     CheckComplexPat,
  70     CheckAndImm,
  71     CheckOrImm,
  72     CheckFoldableChainNode,
  73
  74     // Node creation/emisssion.
  75     EmitInteger,          // Create a TargetConstant
  76     EmitStringInteger,    // Create a TargetConstant from a string.
  77     EmitRegister,         // Create a register.
  78     EmitConvertToTarget,  // Convert a imm/fpimm to target imm/fpimm
  79     EmitMergeInputChains, // Merge together a chains for an input.
  80     EmitCopyToReg,        // Emit a copytoreg into a physreg.
  81     EmitNode,             // Create a DAG node
  82     EmitNodeXForm,        // Run a SDNodeXForm
  83     MarkGlueResults,      // Indicate which interior nodes have glue results.
  84     CompleteMatch,        // Finish a match and update the results.
  85     MorphNodeTo           // Build a node, finish a match and update results.
  86   };
  87   const KindTy Kind;
  88
  89 protected:
  90   Matcher(KindTy K) : Kind(K) {}
  91 public:
  92   virtual ~Matcher() {}
  93
  94   KindTy getKind() const { return Kind; }
  95
  96   Matcher *getNext() { return Next.get(); }
  97   const Matcher *getNext() const { return Next.get(); }
  98   void setNext(Matcher *C) { Next.reset(C); }
  99   Matcher *takeNext() { return Next.take(); }
 100
 101   OwningPtr<Matcher> &getNextPtr() { return Next; }
 102
 103   bool isEqual(const Matcher *M) const {
 104     if (getKind() != M->getKind()) return false;
 105     return isEqualImpl(M);
 106   }
 107
 108   unsigned getHash() const {
 109     // Clear the high bit so we don't conflict with tombstones etc.
 110     return ((getHashImpl() << 4) ^ getKind()) & (~0U>>1);
 111   }
 112
 113   /// isSafeToReorderWithPatternPredicate - Return true if it is safe to sink a
 114   /// PatternPredicate node past this one.
 115   virtual bool isSafeToReorderWithPatternPredicate() const {
 116     return false;
 117   }
 118
 119   /// isSimplePredicateNode - Return true if this is a simple predicate that
 120   /// operates on the node or its children without potential side effects or a
 121   /// change of the current node.
 122   bool isSimplePredicateNode() const {
 123     switch (getKind()) {
 124     default: return false;
 125     case CheckSame:
 126     case CheckChildSame:
 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   /// canMoveBeforeNode - 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 /// CheckChildSameMatcher - This checks to see if child node is exactly the same
 398 /// node as the specified match that was recorded with 'Record'.  This is used
 399 /// when patterns have the same name in them, like '(mul GPR:$in, GPR:$in)'.
 400 class CheckChildSameMatcher : public Matcher {
 401   unsigned ChildNo;
 402   unsigned MatchNumber;
 403 public:
 404   CheckChildSameMatcher(unsigned childno, unsigned matchnumber)
 405     : Matcher(CheckChildSame), ChildNo(childno), MatchNumber(matchnumber) {}
 406
 407   unsigned getChildNo() const { return ChildNo; }
 408   unsigned getMatchNumber() const { return MatchNumber; }
 409
 410   static inline bool classof(const Matcher *N) {
 411     return N->getKind() == CheckChildSame;
 412   }
 413
 414   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 415
 416 private:
 417   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 418   virtual bool isEqualImpl(const Matcher *M) const {
 419     return cast<CheckChildSameMatcher>(M)->ChildNo == ChildNo &&
 420            cast<CheckChildSameMatcher>(M)->MatchNumber == MatchNumber;
 421   }
 422   virtual unsigned getHashImpl() const { return (MatchNumber << 2) | ChildNo; }
 423 };
 424
 425 /// CheckPatternPredicateMatcher - This checks the target-specific predicate
 426 /// to see if the entire pattern is capable of matching.  This predicate does
 427 /// not take a node as input.  This is used for subtarget feature checks etc.
 428 class CheckPatternPredicateMatcher : public Matcher {
 429   std::string Predicate;
 430 public:
 431   CheckPatternPredicateMatcher(StringRef predicate)
 432     : Matcher(CheckPatternPredicate), Predicate(predicate) {}
 433
 434   StringRef getPredicate() const { return Predicate; }
 435
 436   static inline bool classof(const Matcher *N) {
 437     return N->getKind() == CheckPatternPredicate;
 438   }
 439
 440   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 441
 442 private:
 443   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 444   virtual bool isEqualImpl(const Matcher *M) const {
 445     return cast<CheckPatternPredicateMatcher>(M)->getPredicate() == Predicate;
 446   }
 447   virtual unsigned getHashImpl() const;
 448 };
 449
 450 /// CheckPredicateMatcher - This checks the target-specific predicate to
 451 /// see if the node is acceptable.
 452 class CheckPredicateMatcher : public Matcher {
 453   TreePattern *Pred;
 454 public:
 455   CheckPredicateMatcher(const TreePredicateFn &pred);
 456
 457   TreePredicateFn getPredicate() const;
 458
 459   static inline bool classof(const Matcher *N) {
 460     return N->getKind() == CheckPredicate;
 461   }
 462
 463   // TODO: Ok?
 464   //virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 465
 466 private:
 467   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 468   virtual bool isEqualImpl(const Matcher *M) const {
 469     return cast<CheckPredicateMatcher>(M)->Pred == Pred;
 470   }
 471   virtual unsigned getHashImpl() const;
 472 };
 473
 474
 475 /// CheckOpcodeMatcher - This checks to see if the current node has the
 476 /// specified opcode, if not it fails to match.
 477 class CheckOpcodeMatcher : public Matcher {
 478   const SDNodeInfo &Opcode;
 479 public:
 480   CheckOpcodeMatcher(const SDNodeInfo &opcode)
 481     : Matcher(CheckOpcode), Opcode(opcode) {}
 482
 483   const SDNodeInfo &getOpcode() const { return Opcode; }
 484
 485   static inline bool classof(const Matcher *N) {
 486     return N->getKind() == CheckOpcode;
 487   }
 488
 489   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 490
 491 private:
 492   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 493   virtual bool isEqualImpl(const Matcher *M) const;
 494   virtual unsigned getHashImpl() const;
 495   virtual bool isContradictoryImpl(const Matcher *M) const;
 496 };
 497
 498 /// SwitchOpcodeMatcher - Switch based on the current node's opcode, dispatching
 499 /// to one matcher per opcode.  If the opcode doesn't match any of the cases,
 500 /// then the match fails.  This is semantically equivalent to a Scope node where
 501 /// every child does a CheckOpcode, but is much faster.
 502 class SwitchOpcodeMatcher : public Matcher {
 503   SmallVector<std::pair<const SDNodeInfo*, Matcher*>, 8> Cases;
 504 public:
 505   SwitchOpcodeMatcher(const std::pair<const SDNodeInfo*, Matcher*> *cases,
 506                       unsigned numcases)
 507     : Matcher(SwitchOpcode), Cases(cases, cases+numcases) {}
 508
 509   static inline bool classof(const Matcher *N) {
 510     return N->getKind() == SwitchOpcode;
 511   }
 512
 513   unsigned getNumCases() const { return Cases.size(); }
 514
 515   const SDNodeInfo &getCaseOpcode(unsigned i) const { return *Cases[i].first; }
 516   Matcher *getCaseMatcher(unsigned i) { return Cases[i].second; }
 517   const Matcher *getCaseMatcher(unsigned i) const { return Cases[i].second; }
 518
 519 private:
 520   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 521   virtual bool isEqualImpl(const Matcher *M) const { return false; }
 522   virtual unsigned getHashImpl() const { return 4123; }
 523 };
 524
 525 /// CheckTypeMatcher - This checks to see if the current node has the
 526 /// specified type at the specified result, if not it fails to match.
 527 class CheckTypeMatcher : public Matcher {
 528   MVT::SimpleValueType Type;
 529   unsigned ResNo;
 530 public:
 531   CheckTypeMatcher(MVT::SimpleValueType type, unsigned resno)
 532     : Matcher(CheckType), Type(type), ResNo(resno) {}
 533
 534   MVT::SimpleValueType getType() const { return Type; }
 535   unsigned getResNo() const { return ResNo; }
 536
 537   static inline bool classof(const Matcher *N) {
 538     return N->getKind() == CheckType;
 539   }
 540
 541   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 542
 543 private:
 544   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 545   virtual bool isEqualImpl(const Matcher *M) const {
 546     return cast<CheckTypeMatcher>(M)->Type == Type;
 547   }
 548   virtual unsigned getHashImpl() const { return Type; }
 549   virtual bool isContradictoryImpl(const Matcher *M) const;
 550 };
 551
 552 /// SwitchTypeMatcher - Switch based on the current node's type, dispatching
 553 /// to one matcher per case.  If the type doesn't match any of the cases,
 554 /// then the match fails.  This is semantically equivalent to a Scope node where
 555 /// every child does a CheckType, but is much faster.
 556 class SwitchTypeMatcher : public Matcher {
 557   SmallVector<std::pair<MVT::SimpleValueType, Matcher*>, 8> Cases;
 558 public:
 559   SwitchTypeMatcher(const std::pair<MVT::SimpleValueType, Matcher*> *cases,
 560                     unsigned numcases)
 561   : Matcher(SwitchType), Cases(cases, cases+numcases) {}
 562
 563   static inline bool classof(const Matcher *N) {
 564     return N->getKind() == SwitchType;
 565   }
 566
 567   unsigned getNumCases() const { return Cases.size(); }
 568
 569   MVT::SimpleValueType getCaseType(unsigned i) const { return Cases[i].first; }
 570   Matcher *getCaseMatcher(unsigned i) { return Cases[i].second; }
 571   const Matcher *getCaseMatcher(unsigned i) const { return Cases[i].second; }
 572
 573 private:
 574   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 575   virtual bool isEqualImpl(const Matcher *M) const { return false; }
 576   virtual unsigned getHashImpl() const { return 4123; }
 577 };
 578
 579
 580 /// CheckChildTypeMatcher - This checks to see if a child node has the
 581 /// specified type, if not it fails to match.
 582 class CheckChildTypeMatcher : public Matcher {
 583   unsigned ChildNo;
 584   MVT::SimpleValueType Type;
 585 public:
 586   CheckChildTypeMatcher(unsigned childno, MVT::SimpleValueType type)
 587     : Matcher(CheckChildType), ChildNo(childno), Type(type) {}
 588
 589   unsigned getChildNo() const { return ChildNo; }
 590   MVT::SimpleValueType getType() const { return Type; }
 591
 592   static inline bool classof(const Matcher *N) {
 593     return N->getKind() == CheckChildType;
 594   }
 595
 596   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 597
 598 private:
 599   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 600   virtual bool isEqualImpl(const Matcher *M) const {
 601     return cast<CheckChildTypeMatcher>(M)->ChildNo == ChildNo &&
 602            cast<CheckChildTypeMatcher>(M)->Type == Type;
 603   }
 604   virtual unsigned getHashImpl() const { return (Type << 3) | ChildNo; }
 605   virtual bool isContradictoryImpl(const Matcher *M) const;
 606 };
 607
 608
 609 /// CheckIntegerMatcher - This checks to see if the current node is a
 610 /// ConstantSDNode with the specified integer value, if not it fails to match.
 611 class CheckIntegerMatcher : public Matcher {
 612   int64_t Value;
 613 public:
 614   CheckIntegerMatcher(int64_t value)
 615     : Matcher(CheckInteger), Value(value) {}
 616
 617   int64_t getValue() const { return Value; }
 618
 619   static inline bool classof(const Matcher *N) {
 620     return N->getKind() == CheckInteger;
 621   }
 622
 623   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 624
 625 private:
 626   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 627   virtual bool isEqualImpl(const Matcher *M) const {
 628     return cast<CheckIntegerMatcher>(M)->Value == Value;
 629   }
 630   virtual unsigned getHashImpl() const { return Value; }
 631   virtual bool isContradictoryImpl(const Matcher *M) const;
 632 };
 633
 634 /// CheckCondCodeMatcher - This checks to see if the current node is a
 635 /// CondCodeSDNode with the specified condition, if not it fails to match.
 636 class CheckCondCodeMatcher : public Matcher {
 637   StringRef CondCodeName;
 638 public:
 639   CheckCondCodeMatcher(StringRef condcodename)
 640     : Matcher(CheckCondCode), CondCodeName(condcodename) {}
 641
 642   StringRef getCondCodeName() const { return CondCodeName; }
 643
 644   static inline bool classof(const Matcher *N) {
 645     return N->getKind() == CheckCondCode;
 646   }
 647
 648   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 649
 650 private:
 651   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 652   virtual bool isEqualImpl(const Matcher *M) const {
 653     return cast<CheckCondCodeMatcher>(M)->CondCodeName == CondCodeName;
 654   }
 655   virtual unsigned getHashImpl() const;
 656 };
 657
 658 /// CheckValueTypeMatcher - This checks to see if the current node is a
 659 /// VTSDNode with the specified type, if not it fails to match.
 660 class CheckValueTypeMatcher : public Matcher {
 661   StringRef TypeName;
 662 public:
 663   CheckValueTypeMatcher(StringRef type_name)
 664     : Matcher(CheckValueType), TypeName(type_name) {}
 665
 666   StringRef getTypeName() const { return TypeName; }
 667
 668   static inline bool classof(const Matcher *N) {
 669     return N->getKind() == CheckValueType;
 670   }
 671
 672   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 673
 674 private:
 675   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 676   virtual bool isEqualImpl(const Matcher *M) const {
 677     return cast<CheckValueTypeMatcher>(M)->TypeName == TypeName;
 678   }
 679   virtual unsigned getHashImpl() const;
 680   bool isContradictoryImpl(const Matcher *M) const;
 681 };
 682
 683
 684
 685 /// CheckComplexPatMatcher - This node runs the specified ComplexPattern on
 686 /// the current node.
 687 class CheckComplexPatMatcher : public Matcher {
 688   const ComplexPattern &Pattern;
 689
 690   /// MatchNumber - This is the recorded nodes slot that contains the node we
 691   /// want to match against.
 692   unsigned MatchNumber;
 693
 694   /// Name - The name of the node we're matching, for comment emission.
 695   std::string Name;
 696
 697   /// FirstResult - This is the first slot in the RecordedNodes list that the
 698   /// result of the match populates.
 699   unsigned FirstResult;
 700 public:
 701   CheckComplexPatMatcher(const ComplexPattern &pattern, unsigned matchnumber,
 702                          const std::string &name, unsigned firstresult)
 703     : Matcher(CheckComplexPat), Pattern(pattern), MatchNumber(matchnumber),
 704       Name(name), FirstResult(firstresult) {}
 705
 706   const ComplexPattern &getPattern() const { return Pattern; }
 707   unsigned getMatchNumber() const { return MatchNumber; }
 708
 709   const std::string getName() const { return Name; }
 710   unsigned getFirstResult() const { return FirstResult; }
 711
 712   static inline bool classof(const Matcher *N) {
 713     return N->getKind() == CheckComplexPat;
 714   }
 715
 716   // Not safe to move a pattern predicate past a complex pattern.
 717   virtual bool isSafeToReorderWithPatternPredicate() const { return false; }
 718
 719 private:
 720   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 721   virtual bool isEqualImpl(const Matcher *M) const {
 722     return &cast<CheckComplexPatMatcher>(M)->Pattern == &Pattern &&
 723            cast<CheckComplexPatMatcher>(M)->MatchNumber == MatchNumber;
 724   }
 725   virtual unsigned getHashImpl() const {
 726     return (unsigned)(intptr_t)&Pattern ^ MatchNumber;
 727   }
 728 };
 729
 730 /// CheckAndImmMatcher - This checks to see if the current node is an 'and'
 731 /// with something equivalent to the specified immediate.
 732 class CheckAndImmMatcher : public Matcher {
 733   int64_t Value;
 734 public:
 735   CheckAndImmMatcher(int64_t value)
 736     : Matcher(CheckAndImm), Value(value) {}
 737
 738   int64_t getValue() const { return Value; }
 739
 740   static inline bool classof(const Matcher *N) {
 741     return N->getKind() == CheckAndImm;
 742   }
 743
 744   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 745
 746 private:
 747   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 748   virtual bool isEqualImpl(const Matcher *M) const {
 749     return cast<CheckAndImmMatcher>(M)->Value == Value;
 750   }
 751   virtual unsigned getHashImpl() const { return Value; }
 752 };
 753
 754 /// CheckOrImmMatcher - This checks to see if the current node is an 'and'
 755 /// with something equivalent to the specified immediate.
 756 class CheckOrImmMatcher : public Matcher {
 757   int64_t Value;
 758 public:
 759   CheckOrImmMatcher(int64_t value)
 760     : Matcher(CheckOrImm), Value(value) {}
 761
 762   int64_t getValue() const { return Value; }
 763
 764   static inline bool classof(const Matcher *N) {
 765     return N->getKind() == CheckOrImm;
 766   }
 767
 768   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 769
 770 private:
 771   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 772   virtual bool isEqualImpl(const Matcher *M) const {
 773     return cast<CheckOrImmMatcher>(M)->Value == Value;
 774   }
 775   virtual unsigned getHashImpl() const { return Value; }
 776 };
 777
 778 /// CheckFoldableChainNodeMatcher - This checks to see if the current node
 779 /// (which defines a chain operand) is safe to fold into a larger pattern.
 780 class CheckFoldableChainNodeMatcher : public Matcher {
 781 public:
 782   CheckFoldableChainNodeMatcher()
 783     : Matcher(CheckFoldableChainNode) {}
 784
 785   static inline bool classof(const Matcher *N) {
 786     return N->getKind() == CheckFoldableChainNode;
 787   }
 788
 789   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 790
 791 private:
 792   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 793   virtual bool isEqualImpl(const Matcher *M) const { return true; }
 794   virtual unsigned getHashImpl() const { return 0; }
 795 };
 796
 797 /// EmitIntegerMatcher - This creates a new TargetConstant.
 798 class EmitIntegerMatcher : public Matcher {
 799   int64_t Val;
 800   MVT::SimpleValueType VT;
 801 public:
 802   EmitIntegerMatcher(int64_t val, MVT::SimpleValueType vt)
 803     : Matcher(EmitInteger), Val(val), VT(vt) {}
 804
 805   int64_t getValue() const { return Val; }
 806   MVT::SimpleValueType getVT() const { return VT; }
 807
 808   static inline bool classof(const Matcher *N) {
 809     return N->getKind() == EmitInteger;
 810   }
 811
 812 private:
 813   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 814   virtual bool isEqualImpl(const Matcher *M) const {
 815     return cast<EmitIntegerMatcher>(M)->Val == Val &&
 816            cast<EmitIntegerMatcher>(M)->VT == VT;
 817   }
 818   virtual unsigned getHashImpl() const { return (Val << 4) | VT; }
 819 };
 820
 821 /// EmitStringIntegerMatcher - A target constant whose value is represented
 822 /// by a string.
 823 class EmitStringIntegerMatcher : public Matcher {
 824   std::string Val;
 825   MVT::SimpleValueType VT;
 826 public:
 827   EmitStringIntegerMatcher(const std::string &val, MVT::SimpleValueType vt)
 828     : Matcher(EmitStringInteger), Val(val), VT(vt) {}
 829
 830   const std::string &getValue() const { return Val; }
 831   MVT::SimpleValueType getVT() const { return VT; }
 832
 833   static inline bool classof(const Matcher *N) {
 834     return N->getKind() == EmitStringInteger;
 835   }
 836
 837 private:
 838   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 839   virtual bool isEqualImpl(const Matcher *M) const {
 840     return cast<EmitStringIntegerMatcher>(M)->Val == Val &&
 841            cast<EmitStringIntegerMatcher>(M)->VT == VT;
 842   }
 843   virtual unsigned getHashImpl() const;
 844 };
 845
 846 /// EmitRegisterMatcher - This creates a new TargetConstant.
 847 class EmitRegisterMatcher : public Matcher {
 848   /// Reg - The def for the register that we're emitting.  If this is null, then
 849   /// this is a reference to zero_reg.
 850   const CodeGenRegister *Reg;
 851   MVT::SimpleValueType VT;
 852 public:
 853   EmitRegisterMatcher(const CodeGenRegister *reg, MVT::SimpleValueType vt)
 854     : Matcher(EmitRegister), Reg(reg), VT(vt) {}
 855
 856   const CodeGenRegister *getReg() const { return Reg; }
 857   MVT::SimpleValueType getVT() const { return VT; }
 858
 859   static inline bool classof(const Matcher *N) {
 860     return N->getKind() == EmitRegister;
 861   }
 862
 863 private:
 864   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 865   virtual bool isEqualImpl(const Matcher *M) const {
 866     return cast<EmitRegisterMatcher>(M)->Reg == Reg &&
 867            cast<EmitRegisterMatcher>(M)->VT == VT;
 868   }
 869   virtual unsigned getHashImpl() const {
 870     return ((unsigned)(intptr_t)Reg) << 4 | VT;
 871   }
 872 };
 873
 874 /// EmitConvertToTargetMatcher - Emit an operation that reads a specified
 875 /// recorded node and converts it from being a ISD::Constant to
 876 /// ISD::TargetConstant, likewise for ConstantFP.
 877 class EmitConvertToTargetMatcher : public Matcher {
 878   unsigned Slot;
 879 public:
 880   EmitConvertToTargetMatcher(unsigned slot)
 881     : Matcher(EmitConvertToTarget), Slot(slot) {}
 882
 883   unsigned getSlot() const { return Slot; }
 884
 885   static inline bool classof(const Matcher *N) {
 886     return N->getKind() == EmitConvertToTarget;
 887   }
 888
 889 private:
 890   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 891   virtual bool isEqualImpl(const Matcher *M) const {
 892     return cast<EmitConvertToTargetMatcher>(M)->Slot == Slot;
 893   }
 894   virtual unsigned getHashImpl() const { return Slot; }
 895 };
 896
 897 /// EmitMergeInputChainsMatcher - Emit a node that merges a list of input
 898 /// chains together with a token factor.  The list of nodes are the nodes in the
 899 /// matched pattern that have chain input/outputs.  This node adds all input
 900 /// chains of these nodes if they are not themselves a node in the pattern.
 901 class EmitMergeInputChainsMatcher : public Matcher {
 902   SmallVector<unsigned, 3> ChainNodes;
 903 public:
 904   EmitMergeInputChainsMatcher(const unsigned *nodes, unsigned NumNodes)
 905     : Matcher(EmitMergeInputChains), ChainNodes(nodes, nodes+NumNodes) {}
 906
 907   unsigned getNumNodes() const { return ChainNodes.size(); }
 908
 909   unsigned getNode(unsigned i) const {
 910     assert(i < ChainNodes.size());
 911     return ChainNodes[i];
 912   }
 913
 914   static inline bool classof(const Matcher *N) {
 915     return N->getKind() == EmitMergeInputChains;
 916   }
 917
 918 private:
 919   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 920   virtual bool isEqualImpl(const Matcher *M) const {
 921     return cast<EmitMergeInputChainsMatcher>(M)->ChainNodes == ChainNodes;
 922   }
 923   virtual unsigned getHashImpl() const;
 924 };
 925
 926 /// EmitCopyToRegMatcher - Emit a CopyToReg node from a value to a physreg,
 927 /// pushing the chain and glue results.
 928 ///
 929 class EmitCopyToRegMatcher : public Matcher {
 930   unsigned SrcSlot; // Value to copy into the physreg.
 931   Record *DestPhysReg;
 932 public:
 933   EmitCopyToRegMatcher(unsigned srcSlot, Record *destPhysReg)
 934     : Matcher(EmitCopyToReg), SrcSlot(srcSlot), DestPhysReg(destPhysReg) {}
 935
 936   unsigned getSrcSlot() const { return SrcSlot; }
 937   Record *getDestPhysReg() const { return DestPhysReg; }
 938
 939   static inline bool classof(const Matcher *N) {
 940     return N->getKind() == EmitCopyToReg;
 941   }
 942
 943 private:
 944   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 945   virtual bool isEqualImpl(const Matcher *M) const {
 946     return cast<EmitCopyToRegMatcher>(M)->SrcSlot == SrcSlot &&
 947            cast<EmitCopyToRegMatcher>(M)->DestPhysReg == DestPhysReg;
 948   }
 949   virtual unsigned getHashImpl() const {
 950     return SrcSlot ^ ((unsigned)(intptr_t)DestPhysReg << 4);
 951   }
 952 };
 953
 954
 955
 956 /// EmitNodeXFormMatcher - Emit an operation that runs an SDNodeXForm on a
 957 /// recorded node and records the result.
 958 class EmitNodeXFormMatcher : public Matcher {
 959   unsigned Slot;
 960   Record *NodeXForm;
 961 public:
 962   EmitNodeXFormMatcher(unsigned slot, Record *nodeXForm)
 963     : Matcher(EmitNodeXForm), Slot(slot), NodeXForm(nodeXForm) {}
 964
 965   unsigned getSlot() const { return Slot; }
 966   Record *getNodeXForm() const { return NodeXForm; }
 967
 968   static inline bool classof(const Matcher *N) {
 969     return N->getKind() == EmitNodeXForm;
 970   }
 971
 972 private:
 973   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 974   virtual bool isEqualImpl(const Matcher *M) const {
 975     return cast<EmitNodeXFormMatcher>(M)->Slot == Slot &&
 976            cast<EmitNodeXFormMatcher>(M)->NodeXForm == NodeXForm;
 977   }
 978   virtual unsigned getHashImpl() const {
 979     return Slot ^ ((unsigned)(intptr_t)NodeXForm << 4);
 980   }
 981 };
 982
 983 /// EmitNodeMatcherCommon - Common class shared between EmitNode and
 984 /// MorphNodeTo.
 985 class EmitNodeMatcherCommon : public Matcher {
 986   std::string OpcodeName;
 987   const SmallVector<MVT::SimpleValueType, 3> VTs;
 988   const SmallVector<unsigned, 6> Operands;
 989   bool HasChain, HasInGlue, HasOutGlue, HasMemRefs;
 990
 991   /// NumFixedArityOperands - If this is a fixed arity node, this is set to -1.
 992   /// If this is a varidic node, this is set to the number of fixed arity
 993   /// operands in the root of the pattern.  The rest are appended to this node.
 994   int NumFixedArityOperands;
 995 public:
 996   EmitNodeMatcherCommon(const std::string &opcodeName,
 997                         const MVT::SimpleValueType *vts, unsigned numvts,
 998                         const unsigned *operands, unsigned numops,
 999                         bool hasChain, bool hasInGlue, bool hasOutGlue,
1000                         bool hasmemrefs,
1001                         int numfixedarityoperands, bool isMorphNodeTo)
1002     : Matcher(isMorphNodeTo ? MorphNodeTo : EmitNode), OpcodeName(opcodeName),
1003       VTs(vts, vts+numvts), Operands(operands, operands+numops),
1004       HasChain(hasChain), HasInGlue(hasInGlue), HasOutGlue(hasOutGlue),
1005       HasMemRefs(hasmemrefs), NumFixedArityOperands(numfixedarityoperands) {}
1006
1007   const std::string &getOpcodeName() const { return OpcodeName; }
1008
1009   unsigned getNumVTs() const { return VTs.size(); }
1010   MVT::SimpleValueType getVT(unsigned i) const {
1011     assert(i < VTs.size());
1012     return VTs[i];
1013   }
1014
1015   unsigned getNumOperands() const { return Operands.size(); }
1016   unsigned getOperand(unsigned i) const {
1017     assert(i < Operands.size());
1018     return Operands[i];
1019   }
1020
1021   const SmallVectorImpl<MVT::SimpleValueType> &getVTList() const { return VTs; }
1022   const SmallVectorImpl<unsigned> &getOperandList() const { return Operands; }
1023
1024
1025   bool hasChain() const { return HasChain; }
1026   bool hasInFlag() const { return HasInGlue; }
1027   bool hasOutFlag() const { return HasOutGlue; }
1028   bool hasMemRefs() const { return HasMemRefs; }
1029   int getNumFixedArityOperands() const { return NumFixedArityOperands; }
1030
1031   static inline bool classof(const Matcher *N) {
1032     return N->getKind() == EmitNode || N->getKind() == MorphNodeTo;
1033   }
1034
1035 private:
1036   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
1037   virtual bool isEqualImpl(const Matcher *M) const;
1038   virtual unsigned getHashImpl() const;
1039 };
1040
1041 /// EmitNodeMatcher - This signals a successful match and generates a node.
1042 class EmitNodeMatcher : public EmitNodeMatcherCommon {
1043   virtual void anchor();
1044   unsigned FirstResultSlot;
1045 public:
1046   EmitNodeMatcher(const std::string &opcodeName,
1047                   const MVT::SimpleValueType *vts, unsigned numvts,
1048                   const unsigned *operands, unsigned numops,
1049                   bool hasChain, bool hasInFlag, bool hasOutFlag,
1050                   bool hasmemrefs,
1051                   int numfixedarityoperands, unsigned firstresultslot)
1052   : EmitNodeMatcherCommon(opcodeName, vts, numvts, operands, numops, hasChain,
1053                           hasInFlag, hasOutFlag, hasmemrefs,
1054                           numfixedarityoperands, false),
1055     FirstResultSlot(firstresultslot) {}
1056
1057   unsigned getFirstResultSlot() const { return FirstResultSlot; }
1058
1059   static inline bool classof(const Matcher *N) {
1060     return N->getKind() == EmitNode;
1061   }
1062
1063 };
1064
1065 class MorphNodeToMatcher : public EmitNodeMatcherCommon {
1066   virtual void anchor();
1067   const PatternToMatch &Pattern;
1068 public:
1069   MorphNodeToMatcher(const std::string &opcodeName,
1070                      const MVT::SimpleValueType *vts, unsigned numvts,
1071                      const unsigned *operands, unsigned numops,
1072                      bool hasChain, bool hasInFlag, bool hasOutFlag,
1073                      bool hasmemrefs,
1074                      int numfixedarityoperands, const PatternToMatch &pattern)
1075     : EmitNodeMatcherCommon(opcodeName, vts, numvts, operands, numops, hasChain,
1076                             hasInFlag, hasOutFlag, hasmemrefs,
1077                             numfixedarityoperands, true),
1078       Pattern(pattern) {
1079   }
1080
1081   const PatternToMatch &getPattern() const { return Pattern; }
1082
1083   static inline bool classof(const Matcher *N) {
1084     return N->getKind() == MorphNodeTo;
1085   }
1086 };
1087
1088 /// MarkGlueResultsMatcher - This node indicates which non-root nodes in the
1089 /// pattern produce glue.  This allows CompleteMatchMatcher to update them
1090 /// with the output glue of the resultant code.
1091 class MarkGlueResultsMatcher : public Matcher {
1092   SmallVector<unsigned, 3> GlueResultNodes;
1093 public:
1094   MarkGlueResultsMatcher(const unsigned *nodes, unsigned NumNodes)
1095     : Matcher(MarkGlueResults), GlueResultNodes(nodes, nodes+NumNodes) {}
1096
1097   unsigned getNumNodes() const { return GlueResultNodes.size(); }
1098
1099   unsigned getNode(unsigned i) const {
1100     assert(i < GlueResultNodes.size());
1101     return GlueResultNodes[i];
1102   }
1103
1104   static inline bool classof(const Matcher *N) {
1105     return N->getKind() == MarkGlueResults;
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<MarkGlueResultsMatcher>(M)->GlueResultNodes == GlueResultNodes;
1112   }
1113   virtual unsigned getHashImpl() const;
1114 };
1115
1116 /// CompleteMatchMatcher - Complete a match by replacing the results of the
1117 /// pattern with the newly generated nodes.  This also prints a comment
1118 /// indicating the source and dest patterns.
1119 class CompleteMatchMatcher : public Matcher {
1120   SmallVector<unsigned, 2> Results;
1121   const PatternToMatch &Pattern;
1122 public:
1123   CompleteMatchMatcher(const unsigned *results, unsigned numresults,
1124                        const PatternToMatch &pattern)
1125   : Matcher(CompleteMatch), Results(results, results+numresults),
1126     Pattern(pattern) {}
1127
1128   unsigned getNumResults() const { return Results.size(); }
1129   unsigned getResult(unsigned R) const { return Results[R]; }
1130   const PatternToMatch &getPattern() const { return Pattern; }
1131
1132   static inline bool classof(const Matcher *N) {
1133     return N->getKind() == CompleteMatch;
1134   }
1135
1136 private:
1137   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
1138   virtual bool isEqualImpl(const Matcher *M) const {
1139     return cast<CompleteMatchMatcher>(M)->Results == Results &&
1140           &cast<CompleteMatchMatcher>(M)->Pattern == &Pattern;
1141   }
1142   virtual unsigned getHashImpl() const;
1143 };
1144
1145 } // end namespace llvm
1146
1147 #endif