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