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