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