utils/TableGen/DAGISelMatcher.h

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