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