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,unsigned Variant,
  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 /// CheckTypeMatcher - This checks to see if the current node has the
 453 /// specified type, if not it fails to match.
 454 class CheckTypeMatcher : public Matcher {
 455   MVT::SimpleValueType Type;
 456 public:
 457   CheckTypeMatcher(MVT::SimpleValueType type)
 458     : Matcher(CheckType), Type(type) {}
 459
 460   MVT::SimpleValueType getType() const { return Type; }
 461
 462   static inline bool classof(const Matcher *N) {
 463     return N->getKind() == CheckType;
 464   }
 465
 466   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 467
 468 private:
 469   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 470   virtual bool isEqualImpl(const Matcher *M) const {
 471     return cast<CheckTypeMatcher>(M)->Type == Type;
 472   }
 473   virtual unsigned getHashImpl() const { return Type; }
 474   virtual bool isContradictoryImpl(const Matcher *M) const;
 475 };
 476
 477 /// CheckChildTypeMatcher - This checks to see if a child node has the
 478 /// specified type, if not it fails to match.
 479 class CheckChildTypeMatcher : public Matcher {
 480   unsigned ChildNo;
 481   MVT::SimpleValueType Type;
 482 public:
 483   CheckChildTypeMatcher(unsigned childno, MVT::SimpleValueType type)
 484     : Matcher(CheckChildType), ChildNo(childno), Type(type) {}
 485
 486   unsigned getChildNo() const { return ChildNo; }
 487   MVT::SimpleValueType getType() const { return Type; }
 488
 489   static inline bool classof(const Matcher *N) {
 490     return N->getKind() == CheckChildType;
 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<CheckChildTypeMatcher>(M)->ChildNo == ChildNo &&
 499            cast<CheckChildTypeMatcher>(M)->Type == Type;
 500   }
 501   virtual unsigned getHashImpl() const { return (Type << 3) | ChildNo; }
 502   virtual bool isContradictoryImpl(const Matcher *M) const;
 503 };
 504
 505
 506 /// CheckIntegerMatcher - This checks to see if the current node is a
 507 /// ConstantSDNode with the specified integer value, if not it fails to match.
 508 class CheckIntegerMatcher : public Matcher {
 509   int64_t Value;
 510 public:
 511   CheckIntegerMatcher(int64_t value)
 512     : Matcher(CheckInteger), Value(value) {}
 513
 514   int64_t getValue() const { return Value; }
 515
 516   static inline bool classof(const Matcher *N) {
 517     return N->getKind() == CheckInteger;
 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<CheckIntegerMatcher>(M)->Value == Value;
 526   }
 527   virtual unsigned getHashImpl() const { return Value; }
 528   virtual bool isContradictoryImpl(const Matcher *M) const;
 529 };
 530
 531 /// CheckCondCodeMatcher - This checks to see if the current node is a
 532 /// CondCodeSDNode with the specified condition, if not it fails to match.
 533 class CheckCondCodeMatcher : public Matcher {
 534   StringRef CondCodeName;
 535 public:
 536   CheckCondCodeMatcher(StringRef condcodename)
 537     : Matcher(CheckCondCode), CondCodeName(condcodename) {}
 538
 539   StringRef getCondCodeName() const { return CondCodeName; }
 540
 541   static inline bool classof(const Matcher *N) {
 542     return N->getKind() == CheckCondCode;
 543   }
 544
 545   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 546
 547 private:
 548   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 549   virtual bool isEqualImpl(const Matcher *M) const {
 550     return cast<CheckCondCodeMatcher>(M)->CondCodeName == CondCodeName;
 551   }
 552   virtual unsigned getHashImpl() const;
 553 };
 554
 555 /// CheckValueTypeMatcher - This checks to see if the current node is a
 556 /// VTSDNode with the specified type, if not it fails to match.
 557 class CheckValueTypeMatcher : public Matcher {
 558   StringRef TypeName;
 559 public:
 560   CheckValueTypeMatcher(StringRef type_name)
 561     : Matcher(CheckValueType), TypeName(type_name) {}
 562
 563   StringRef getTypeName() const { return TypeName; }
 564
 565   static inline bool classof(const Matcher *N) {
 566     return N->getKind() == CheckValueType;
 567   }
 568
 569   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 570
 571 private:
 572   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 573   virtual bool isEqualImpl(const Matcher *M) const {
 574     return cast<CheckValueTypeMatcher>(M)->TypeName == TypeName;
 575   }
 576   virtual unsigned getHashImpl() const;
 577 };
 578
 579
 580
 581 /// CheckComplexPatMatcher - This node runs the specified ComplexPattern on
 582 /// the current node.
 583 class CheckComplexPatMatcher : public Matcher {
 584   const ComplexPattern &Pattern;
 585 public:
 586   CheckComplexPatMatcher(const ComplexPattern &pattern)
 587     : Matcher(CheckComplexPat), Pattern(pattern) {}
 588
 589   const ComplexPattern &getPattern() const { return Pattern; }
 590
 591   static inline bool classof(const Matcher *N) {
 592     return N->getKind() == CheckComplexPat;
 593   }
 594
 595   // Not safe to move a pattern predicate past a complex pattern.
 596   virtual bool isSafeToReorderWithPatternPredicate() const { return false; }
 597
 598 private:
 599   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 600   virtual bool isEqualImpl(const Matcher *M) const {
 601     return &cast<CheckComplexPatMatcher>(M)->Pattern == &Pattern;
 602   }
 603   virtual unsigned getHashImpl() const {
 604     return (unsigned)(intptr_t)&Pattern;
 605   }
 606 };
 607
 608 /// CheckAndImmMatcher - This checks to see if the current node is an 'and'
 609 /// with something equivalent to the specified immediate.
 610 class CheckAndImmMatcher : public Matcher {
 611   int64_t Value;
 612 public:
 613   CheckAndImmMatcher(int64_t value)
 614     : Matcher(CheckAndImm), Value(value) {}
 615
 616   int64_t getValue() const { return Value; }
 617
 618   static inline bool classof(const Matcher *N) {
 619     return N->getKind() == CheckAndImm;
 620   }
 621
 622   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 623
 624 private:
 625   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 626   virtual bool isEqualImpl(const Matcher *M) const {
 627     return cast<CheckAndImmMatcher>(M)->Value == Value;
 628   }
 629   virtual unsigned getHashImpl() const { return Value; }
 630 };
 631
 632 /// CheckOrImmMatcher - This checks to see if the current node is an 'and'
 633 /// with something equivalent to the specified immediate.
 634 class CheckOrImmMatcher : public Matcher {
 635   int64_t Value;
 636 public:
 637   CheckOrImmMatcher(int64_t value)
 638     : Matcher(CheckOrImm), Value(value) {}
 639
 640   int64_t getValue() const { return Value; }
 641
 642   static inline bool classof(const Matcher *N) {
 643     return N->getKind() == CheckOrImm;
 644   }
 645
 646   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 647
 648 private:
 649   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 650   virtual bool isEqualImpl(const Matcher *M) const {
 651     return cast<CheckOrImmMatcher>(M)->Value == Value;
 652   }
 653   virtual unsigned getHashImpl() const { return Value; }
 654 };
 655
 656 /// CheckFoldableChainNodeMatcher - This checks to see if the current node
 657 /// (which defines a chain operand) is safe to fold into a larger pattern.
 658 class CheckFoldableChainNodeMatcher : public Matcher {
 659 public:
 660   CheckFoldableChainNodeMatcher()
 661     : Matcher(CheckFoldableChainNode) {}
 662
 663   static inline bool classof(const Matcher *N) {
 664     return N->getKind() == CheckFoldableChainNode;
 665   }
 666
 667   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 668
 669 private:
 670   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 671   virtual bool isEqualImpl(const Matcher *M) const { return true; }
 672   virtual unsigned getHashImpl() const { return 0; }
 673 };
 674
 675 /// CheckChainCompatibleMatcher - Verify that the current node's chain
 676 /// operand is 'compatible' with the specified recorded node's.
 677 class CheckChainCompatibleMatcher : public Matcher {
 678   unsigned PreviousOp;
 679 public:
 680   CheckChainCompatibleMatcher(unsigned previousop)
 681     : Matcher(CheckChainCompatible), PreviousOp(previousop) {}
 682
 683   unsigned getPreviousOp() const { return PreviousOp; }
 684
 685   static inline bool classof(const Matcher *N) {
 686     return N->getKind() == CheckChainCompatible;
 687   }
 688
 689   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 690
 691 private:
 692   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 693   virtual bool isEqualImpl(const Matcher *M) const {
 694     return cast<CheckChainCompatibleMatcher>(M)->PreviousOp == PreviousOp;
 695   }
 696   virtual unsigned getHashImpl() const { return PreviousOp; }
 697 };
 698
 699 /// EmitIntegerMatcher - This creates a new TargetConstant.
 700 class EmitIntegerMatcher : public Matcher {
 701   int64_t Val;
 702   MVT::SimpleValueType VT;
 703 public:
 704   EmitIntegerMatcher(int64_t val, MVT::SimpleValueType vt)
 705     : Matcher(EmitInteger), Val(val), VT(vt) {}
 706
 707   int64_t getValue() const { return Val; }
 708   MVT::SimpleValueType getVT() const { return VT; }
 709
 710   static inline bool classof(const Matcher *N) {
 711     return N->getKind() == EmitInteger;
 712   }
 713
 714 private:
 715   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 716   virtual bool isEqualImpl(const Matcher *M) const {
 717     return cast<EmitIntegerMatcher>(M)->Val == Val &&
 718            cast<EmitIntegerMatcher>(M)->VT == VT;
 719   }
 720   virtual unsigned getHashImpl() const { return (Val << 4) | VT; }
 721 };
 722
 723 /// EmitStringIntegerMatcher - A target constant whose value is represented
 724 /// by a string.
 725 class EmitStringIntegerMatcher : public Matcher {
 726   std::string Val;
 727   MVT::SimpleValueType VT;
 728 public:
 729   EmitStringIntegerMatcher(const std::string &val, MVT::SimpleValueType vt)
 730     : Matcher(EmitStringInteger), Val(val), VT(vt) {}
 731
 732   const std::string &getValue() const { return Val; }
 733   MVT::SimpleValueType getVT() const { return VT; }
 734
 735   static inline bool classof(const Matcher *N) {
 736     return N->getKind() == EmitStringInteger;
 737   }
 738
 739 private:
 740   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 741   virtual bool isEqualImpl(const Matcher *M) const {
 742     return cast<EmitStringIntegerMatcher>(M)->Val == Val &&
 743            cast<EmitStringIntegerMatcher>(M)->VT == VT;
 744   }
 745   virtual unsigned getHashImpl() const;
 746 };
 747
 748 /// EmitRegisterMatcher - This creates a new TargetConstant.
 749 class EmitRegisterMatcher : public Matcher {
 750   /// Reg - The def for the register that we're emitting.  If this is null, then
 751   /// this is a reference to zero_reg.
 752   Record *Reg;
 753   MVT::SimpleValueType VT;
 754 public:
 755   EmitRegisterMatcher(Record *reg, MVT::SimpleValueType vt)
 756     : Matcher(EmitRegister), Reg(reg), VT(vt) {}
 757
 758   Record *getReg() const { return Reg; }
 759   MVT::SimpleValueType getVT() const { return VT; }
 760
 761   static inline bool classof(const Matcher *N) {
 762     return N->getKind() == EmitRegister;
 763   }
 764
 765 private:
 766   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 767   virtual bool isEqualImpl(const Matcher *M) const {
 768     return cast<EmitRegisterMatcher>(M)->Reg == Reg &&
 769            cast<EmitRegisterMatcher>(M)->VT == VT;
 770   }
 771   virtual unsigned getHashImpl() const {
 772     return ((unsigned)(intptr_t)Reg) << 4 | VT;
 773   }
 774 };
 775
 776 /// EmitConvertToTargetMatcher - Emit an operation that reads a specified
 777 /// recorded node and converts it from being a ISD::Constant to
 778 /// ISD::TargetConstant, likewise for ConstantFP.
 779 class EmitConvertToTargetMatcher : public Matcher {
 780   unsigned Slot;
 781 public:
 782   EmitConvertToTargetMatcher(unsigned slot)
 783     : Matcher(EmitConvertToTarget), Slot(slot) {}
 784
 785   unsigned getSlot() const { return Slot; }
 786
 787   static inline bool classof(const Matcher *N) {
 788     return N->getKind() == EmitConvertToTarget;
 789   }
 790
 791 private:
 792   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 793   virtual bool isEqualImpl(const Matcher *M) const {
 794     return cast<EmitConvertToTargetMatcher>(M)->Slot == Slot;
 795   }
 796   virtual unsigned getHashImpl() const { return Slot; }
 797 };
 798
 799 /// EmitMergeInputChainsMatcher - Emit a node that merges a list of input
 800 /// chains together with a token factor.  The list of nodes are the nodes in the
 801 /// matched pattern that have chain input/outputs.  This node adds all input
 802 /// chains of these nodes if they are not themselves a node in the pattern.
 803 class EmitMergeInputChainsMatcher : public Matcher {
 804   SmallVector<unsigned, 3> ChainNodes;
 805 public:
 806   EmitMergeInputChainsMatcher(const unsigned *nodes, unsigned NumNodes)
 807     : Matcher(EmitMergeInputChains), ChainNodes(nodes, nodes+NumNodes) {}
 808
 809   unsigned getNumNodes() const { return ChainNodes.size(); }
 810
 811   unsigned getNode(unsigned i) const {
 812     assert(i < ChainNodes.size());
 813     return ChainNodes[i];
 814   }
 815
 816   static inline bool classof(const Matcher *N) {
 817     return N->getKind() == EmitMergeInputChains;
 818   }
 819
 820 private:
 821   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 822   virtual bool isEqualImpl(const Matcher *M) const {
 823     return cast<EmitMergeInputChainsMatcher>(M)->ChainNodes == ChainNodes;
 824   }
 825   virtual unsigned getHashImpl() const;
 826 };
 827
 828 /// EmitCopyToRegMatcher - Emit a CopyToReg node from a value to a physreg,
 829 /// pushing the chain and flag results.
 830 ///
 831 class EmitCopyToRegMatcher : public Matcher {
 832   unsigned SrcSlot; // Value to copy into the physreg.
 833   Record *DestPhysReg;
 834 public:
 835   EmitCopyToRegMatcher(unsigned srcSlot, Record *destPhysReg)
 836     : Matcher(EmitCopyToReg), SrcSlot(srcSlot), DestPhysReg(destPhysReg) {}
 837
 838   unsigned getSrcSlot() const { return SrcSlot; }
 839   Record *getDestPhysReg() const { return DestPhysReg; }
 840
 841   static inline bool classof(const Matcher *N) {
 842     return N->getKind() == EmitCopyToReg;
 843   }
 844
 845 private:
 846   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 847   virtual bool isEqualImpl(const Matcher *M) const {
 848     return cast<EmitCopyToRegMatcher>(M)->SrcSlot == SrcSlot &&
 849            cast<EmitCopyToRegMatcher>(M)->DestPhysReg == DestPhysReg;
 850   }
 851   virtual unsigned getHashImpl() const {
 852     return SrcSlot ^ ((unsigned)(intptr_t)DestPhysReg << 4);
 853   }
 854 };
 855
 856
 857
 858 /// EmitNodeXFormMatcher - Emit an operation that runs an SDNodeXForm on a
 859 /// recorded node and records the result.
 860 class EmitNodeXFormMatcher : public Matcher {
 861   unsigned Slot;
 862   Record *NodeXForm;
 863 public:
 864   EmitNodeXFormMatcher(unsigned slot, Record *nodeXForm)
 865     : Matcher(EmitNodeXForm), Slot(slot), NodeXForm(nodeXForm) {}
 866
 867   unsigned getSlot() const { return Slot; }
 868   Record *getNodeXForm() const { return NodeXForm; }
 869
 870   static inline bool classof(const Matcher *N) {
 871     return N->getKind() == EmitNodeXForm;
 872   }
 873
 874 private:
 875   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 876   virtual bool isEqualImpl(const Matcher *M) const {
 877     return cast<EmitNodeXFormMatcher>(M)->Slot == Slot &&
 878            cast<EmitNodeXFormMatcher>(M)->NodeXForm == NodeXForm;
 879   }
 880   virtual unsigned getHashImpl() const {
 881     return Slot ^ ((unsigned)(intptr_t)NodeXForm << 4);
 882   }
 883 };
 884
 885 /// EmitNodeMatcherCommon - Common class shared between EmitNode and
 886 /// MorphNodeTo.
 887 class EmitNodeMatcherCommon : public Matcher {
 888   std::string OpcodeName;
 889   const SmallVector<MVT::SimpleValueType, 3> VTs;
 890   const SmallVector<unsigned, 6> Operands;
 891   bool HasChain, HasInFlag, HasOutFlag, HasMemRefs;
 892
 893   /// NumFixedArityOperands - If this is a fixed arity node, this is set to -1.
 894   /// If this is a varidic node, this is set to the number of fixed arity
 895   /// operands in the root of the pattern.  The rest are appended to this node.
 896   int NumFixedArityOperands;
 897 public:
 898   EmitNodeMatcherCommon(const std::string &opcodeName,
 899                         const MVT::SimpleValueType *vts, unsigned numvts,
 900                         const unsigned *operands, unsigned numops,
 901                         bool hasChain, bool hasInFlag, bool hasOutFlag,
 902                         bool hasmemrefs,
 903                         int numfixedarityoperands, bool isMorphNodeTo)
 904     : Matcher(isMorphNodeTo ? MorphNodeTo : EmitNode), OpcodeName(opcodeName),
 905       VTs(vts, vts+numvts), Operands(operands, operands+numops),
 906       HasChain(hasChain), HasInFlag(hasInFlag), HasOutFlag(hasOutFlag),
 907       HasMemRefs(hasmemrefs), NumFixedArityOperands(numfixedarityoperands) {}
 908
 909   const std::string &getOpcodeName() const { return OpcodeName; }
 910
 911   unsigned getNumVTs() const { return VTs.size(); }
 912   MVT::SimpleValueType getVT(unsigned i) const {
 913     assert(i < VTs.size());
 914     return VTs[i];
 915   }
 916
 917   unsigned getNumOperands() const { return Operands.size(); }
 918   unsigned getOperand(unsigned i) const {
 919     assert(i < Operands.size());
 920     return Operands[i];
 921   }
 922
 923   const SmallVectorImpl<MVT::SimpleValueType> &getVTList() const { return VTs; }
 924   const SmallVectorImpl<unsigned> &getOperandList() const { return Operands; }
 925
 926
 927   bool hasChain() const { return HasChain; }
 928   bool hasInFlag() const { return HasInFlag; }
 929   bool hasOutFlag() const { return HasOutFlag; }
 930   bool hasMemRefs() const { return HasMemRefs; }
 931   int getNumFixedArityOperands() const { return NumFixedArityOperands; }
 932
 933   static inline bool classof(const Matcher *N) {
 934     return N->getKind() == EmitNode || N->getKind() == MorphNodeTo;
 935   }
 936
 937 private:
 938   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 939   virtual bool isEqualImpl(const Matcher *M) const;
 940   virtual unsigned getHashImpl() const;
 941 };
 942
 943 /// EmitNodeMatcher - This signals a successful match and generates a node.
 944 class EmitNodeMatcher : public EmitNodeMatcherCommon {
 945   unsigned FirstResultSlot;
 946 public:
 947   EmitNodeMatcher(const std::string &opcodeName,
 948                   const MVT::SimpleValueType *vts, unsigned numvts,
 949                   const unsigned *operands, unsigned numops,
 950                   bool hasChain, bool hasInFlag, bool hasOutFlag,
 951                   bool hasmemrefs,
 952                   int numfixedarityoperands, unsigned firstresultslot)
 953   : EmitNodeMatcherCommon(opcodeName, vts, numvts, operands, numops, hasChain,
 954                           hasInFlag, hasOutFlag, hasmemrefs,
 955                           numfixedarityoperands, false),
 956     FirstResultSlot(firstresultslot) {}
 957
 958   unsigned getFirstResultSlot() const { return FirstResultSlot; }
 959
 960   static inline bool classof(const Matcher *N) {
 961     return N->getKind() == EmitNode;
 962   }
 963
 964 };
 965
 966 class MorphNodeToMatcher : public EmitNodeMatcherCommon {
 967   const PatternToMatch &Pattern;
 968 public:
 969   MorphNodeToMatcher(const std::string &opcodeName,
 970                      const MVT::SimpleValueType *vts, unsigned numvts,
 971                      const unsigned *operands, unsigned numops,
 972                      bool hasChain, bool hasInFlag, bool hasOutFlag,
 973                      bool hasmemrefs,
 974                      int numfixedarityoperands, const PatternToMatch &pattern)
 975     : EmitNodeMatcherCommon(opcodeName, vts, numvts, operands, numops, hasChain,
 976                             hasInFlag, hasOutFlag, hasmemrefs,
 977                             numfixedarityoperands, true),
 978       Pattern(pattern) {
 979   }
 980
 981   const PatternToMatch &getPattern() const { return Pattern; }
 982
 983   static inline bool classof(const Matcher *N) {
 984     return N->getKind() == MorphNodeTo;
 985   }
 986 };
 987
 988 /// MarkFlagResultsMatcher - This node indicates which non-root nodes in the
 989 /// pattern produce flags.  This allows CompleteMatchMatcher to update them
 990 /// with the output flag of the resultant code.
 991 class MarkFlagResultsMatcher : public Matcher {
 992   SmallVector<unsigned, 3> FlagResultNodes;
 993 public:
 994   MarkFlagResultsMatcher(const unsigned *nodes, unsigned NumNodes)
 995     : Matcher(MarkFlagResults), FlagResultNodes(nodes, nodes+NumNodes) {}
 996
 997   unsigned getNumNodes() const { return FlagResultNodes.size(); }
 998
 999   unsigned getNode(unsigned i) const {
1000     assert(i < FlagResultNodes.size());
1001     return FlagResultNodes[i];
1002   }
1003
1004   static inline bool classof(const Matcher *N) {
1005     return N->getKind() == MarkFlagResults;
1006   }
1007
1008 private:
1009   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
1010   virtual bool isEqualImpl(const Matcher *M) const {
1011     return cast<MarkFlagResultsMatcher>(M)->FlagResultNodes == FlagResultNodes;
1012   }
1013   virtual unsigned getHashImpl() const;
1014 };
1015
1016 /// CompleteMatchMatcher - Complete a match by replacing the results of the
1017 /// pattern with the newly generated nodes.  This also prints a comment
1018 /// indicating the source and dest patterns.
1019 class CompleteMatchMatcher : public Matcher {
1020   SmallVector<unsigned, 2> Results;
1021   const PatternToMatch &Pattern;
1022 public:
1023   CompleteMatchMatcher(const unsigned *results, unsigned numresults,
1024                        const PatternToMatch &pattern)
1025   : Matcher(CompleteMatch), Results(results, results+numresults),
1026     Pattern(pattern) {}
1027
1028   unsigned getNumResults() const { return Results.size(); }
1029   unsigned getResult(unsigned R) const { return Results[R]; }
1030   const PatternToMatch &getPattern() const { return Pattern; }
1031
1032   static inline bool classof(const Matcher *N) {
1033     return N->getKind() == CompleteMatch;
1034   }
1035
1036 private:
1037   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
1038   virtual bool isEqualImpl(const Matcher *M) const {
1039     return cast<CompleteMatchMatcher>(M)->Results == Results &&
1040           &cast<CompleteMatchMatcher>(M)->Pattern == &Pattern;
1041   }
1042   virtual unsigned getHashImpl() const;
1043 };
1044
1045 } // end namespace llvm
1046
1047 #endif