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