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