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