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