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   /// FirstResult - This is the first slot in the RecordedNodes list that the
 613   /// result of the match populates.
 614   unsigned FirstResult;
 615 public:
 616   CheckComplexPatMatcher(const ComplexPattern &pattern, unsigned firstresult)
 617     : Matcher(CheckComplexPat), Pattern(pattern), FirstResult(firstresult) {}
 618
 619   const ComplexPattern &getPattern() const { return Pattern; }
 620   unsigned getFirstResult() const { return FirstResult; }
 621
 622   static inline bool classof(const Matcher *N) {
 623     return N->getKind() == CheckComplexPat;
 624   }
 625
 626   // Not safe to move a pattern predicate past a complex pattern.
 627   virtual bool isSafeToReorderWithPatternPredicate() const { return false; }
 628
 629 private:
 630   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 631   virtual bool isEqualImpl(const Matcher *M) const {
 632     return &cast<CheckComplexPatMatcher>(M)->Pattern == &Pattern;
 633   }
 634   virtual unsigned getHashImpl() const {
 635     return (unsigned)(intptr_t)&Pattern;
 636   }
 637 };
 638
 639 /// CheckAndImmMatcher - This checks to see if the current node is an 'and'
 640 /// with something equivalent to the specified immediate.
 641 class CheckAndImmMatcher : public Matcher {
 642   int64_t Value;
 643 public:
 644   CheckAndImmMatcher(int64_t value)
 645     : Matcher(CheckAndImm), Value(value) {}
 646
 647   int64_t getValue() const { return Value; }
 648
 649   static inline bool classof(const Matcher *N) {
 650     return N->getKind() == CheckAndImm;
 651   }
 652
 653   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 654
 655 private:
 656   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 657   virtual bool isEqualImpl(const Matcher *M) const {
 658     return cast<CheckAndImmMatcher>(M)->Value == Value;
 659   }
 660   virtual unsigned getHashImpl() const { return Value; }
 661 };
 662
 663 /// CheckOrImmMatcher - This checks to see if the current node is an 'and'
 664 /// with something equivalent to the specified immediate.
 665 class CheckOrImmMatcher : public Matcher {
 666   int64_t Value;
 667 public:
 668   CheckOrImmMatcher(int64_t value)
 669     : Matcher(CheckOrImm), Value(value) {}
 670
 671   int64_t getValue() const { return Value; }
 672
 673   static inline bool classof(const Matcher *N) {
 674     return N->getKind() == CheckOrImm;
 675   }
 676
 677   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 678
 679 private:
 680   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 681   virtual bool isEqualImpl(const Matcher *M) const {
 682     return cast<CheckOrImmMatcher>(M)->Value == Value;
 683   }
 684   virtual unsigned getHashImpl() const { return Value; }
 685 };
 686
 687 /// CheckFoldableChainNodeMatcher - This checks to see if the current node
 688 /// (which defines a chain operand) is safe to fold into a larger pattern.
 689 class CheckFoldableChainNodeMatcher : public Matcher {
 690 public:
 691   CheckFoldableChainNodeMatcher()
 692     : Matcher(CheckFoldableChainNode) {}
 693
 694   static inline bool classof(const Matcher *N) {
 695     return N->getKind() == CheckFoldableChainNode;
 696   }
 697
 698   virtual bool isSafeToReorderWithPatternPredicate() const { return true; }
 699
 700 private:
 701   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 702   virtual bool isEqualImpl(const Matcher *M) const { return true; }
 703   virtual unsigned getHashImpl() const { return 0; }
 704 };
 705
 706 /// EmitIntegerMatcher - This creates a new TargetConstant.
 707 class EmitIntegerMatcher : public Matcher {
 708   int64_t Val;
 709   MVT::SimpleValueType VT;
 710 public:
 711   EmitIntegerMatcher(int64_t val, MVT::SimpleValueType vt)
 712     : Matcher(EmitInteger), Val(val), VT(vt) {}
 713
 714   int64_t getValue() const { return Val; }
 715   MVT::SimpleValueType getVT() const { return VT; }
 716
 717   static inline bool classof(const Matcher *N) {
 718     return N->getKind() == EmitInteger;
 719   }
 720
 721 private:
 722   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 723   virtual bool isEqualImpl(const Matcher *M) const {
 724     return cast<EmitIntegerMatcher>(M)->Val == Val &&
 725            cast<EmitIntegerMatcher>(M)->VT == VT;
 726   }
 727   virtual unsigned getHashImpl() const { return (Val << 4) | VT; }
 728 };
 729
 730 /// EmitStringIntegerMatcher - A target constant whose value is represented
 731 /// by a string.
 732 class EmitStringIntegerMatcher : public Matcher {
 733   std::string Val;
 734   MVT::SimpleValueType VT;
 735 public:
 736   EmitStringIntegerMatcher(const std::string &val, MVT::SimpleValueType vt)
 737     : Matcher(EmitStringInteger), Val(val), VT(vt) {}
 738
 739   const std::string &getValue() const { return Val; }
 740   MVT::SimpleValueType getVT() const { return VT; }
 741
 742   static inline bool classof(const Matcher *N) {
 743     return N->getKind() == EmitStringInteger;
 744   }
 745
 746 private:
 747   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 748   virtual bool isEqualImpl(const Matcher *M) const {
 749     return cast<EmitStringIntegerMatcher>(M)->Val == Val &&
 750            cast<EmitStringIntegerMatcher>(M)->VT == VT;
 751   }
 752   virtual unsigned getHashImpl() const;
 753 };
 754
 755 /// EmitRegisterMatcher - This creates a new TargetConstant.
 756 class EmitRegisterMatcher : public Matcher {
 757   /// Reg - The def for the register that we're emitting.  If this is null, then
 758   /// this is a reference to zero_reg.
 759   Record *Reg;
 760   MVT::SimpleValueType VT;
 761 public:
 762   EmitRegisterMatcher(Record *reg, MVT::SimpleValueType vt)
 763     : Matcher(EmitRegister), Reg(reg), VT(vt) {}
 764
 765   Record *getReg() const { return Reg; }
 766   MVT::SimpleValueType getVT() const { return VT; }
 767
 768   static inline bool classof(const Matcher *N) {
 769     return N->getKind() == EmitRegister;
 770   }
 771
 772 private:
 773   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 774   virtual bool isEqualImpl(const Matcher *M) const {
 775     return cast<EmitRegisterMatcher>(M)->Reg == Reg &&
 776            cast<EmitRegisterMatcher>(M)->VT == VT;
 777   }
 778   virtual unsigned getHashImpl() const {
 779     return ((unsigned)(intptr_t)Reg) << 4 | VT;
 780   }
 781 };
 782
 783 /// EmitConvertToTargetMatcher - Emit an operation that reads a specified
 784 /// recorded node and converts it from being a ISD::Constant to
 785 /// ISD::TargetConstant, likewise for ConstantFP.
 786 class EmitConvertToTargetMatcher : public Matcher {
 787   unsigned Slot;
 788 public:
 789   EmitConvertToTargetMatcher(unsigned slot)
 790     : Matcher(EmitConvertToTarget), Slot(slot) {}
 791
 792   unsigned getSlot() const { return Slot; }
 793
 794   static inline bool classof(const Matcher *N) {
 795     return N->getKind() == EmitConvertToTarget;
 796   }
 797
 798 private:
 799   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 800   virtual bool isEqualImpl(const Matcher *M) const {
 801     return cast<EmitConvertToTargetMatcher>(M)->Slot == Slot;
 802   }
 803   virtual unsigned getHashImpl() const { return Slot; }
 804 };
 805
 806 /// EmitMergeInputChainsMatcher - Emit a node that merges a list of input
 807 /// chains together with a token factor.  The list of nodes are the nodes in the
 808 /// matched pattern that have chain input/outputs.  This node adds all input
 809 /// chains of these nodes if they are not themselves a node in the pattern.
 810 class EmitMergeInputChainsMatcher : public Matcher {
 811   SmallVector<unsigned, 3> ChainNodes;
 812 public:
 813   EmitMergeInputChainsMatcher(const unsigned *nodes, unsigned NumNodes)
 814     : Matcher(EmitMergeInputChains), ChainNodes(nodes, nodes+NumNodes) {}
 815
 816   unsigned getNumNodes() const { return ChainNodes.size(); }
 817
 818   unsigned getNode(unsigned i) const {
 819     assert(i < ChainNodes.size());
 820     return ChainNodes[i];
 821   }
 822
 823   static inline bool classof(const Matcher *N) {
 824     return N->getKind() == EmitMergeInputChains;
 825   }
 826
 827 private:
 828   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 829   virtual bool isEqualImpl(const Matcher *M) const {
 830     return cast<EmitMergeInputChainsMatcher>(M)->ChainNodes == ChainNodes;
 831   }
 832   virtual unsigned getHashImpl() const;
 833 };
 834
 835 /// EmitCopyToRegMatcher - Emit a CopyToReg node from a value to a physreg,
 836 /// pushing the chain and flag results.
 837 ///
 838 class EmitCopyToRegMatcher : public Matcher {
 839   unsigned SrcSlot; // Value to copy into the physreg.
 840   Record *DestPhysReg;
 841 public:
 842   EmitCopyToRegMatcher(unsigned srcSlot, Record *destPhysReg)
 843     : Matcher(EmitCopyToReg), SrcSlot(srcSlot), DestPhysReg(destPhysReg) {}
 844
 845   unsigned getSrcSlot() const { return SrcSlot; }
 846   Record *getDestPhysReg() const { return DestPhysReg; }
 847
 848   static inline bool classof(const Matcher *N) {
 849     return N->getKind() == EmitCopyToReg;
 850   }
 851
 852 private:
 853   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 854   virtual bool isEqualImpl(const Matcher *M) const {
 855     return cast<EmitCopyToRegMatcher>(M)->SrcSlot == SrcSlot &&
 856            cast<EmitCopyToRegMatcher>(M)->DestPhysReg == DestPhysReg;
 857   }
 858   virtual unsigned getHashImpl() const {
 859     return SrcSlot ^ ((unsigned)(intptr_t)DestPhysReg << 4);
 860   }
 861 };
 862
 863
 864
 865 /// EmitNodeXFormMatcher - Emit an operation that runs an SDNodeXForm on a
 866 /// recorded node and records the result.
 867 class EmitNodeXFormMatcher : public Matcher {
 868   unsigned Slot;
 869   Record *NodeXForm;
 870 public:
 871   EmitNodeXFormMatcher(unsigned slot, Record *nodeXForm)
 872     : Matcher(EmitNodeXForm), Slot(slot), NodeXForm(nodeXForm) {}
 873
 874   unsigned getSlot() const { return Slot; }
 875   Record *getNodeXForm() const { return NodeXForm; }
 876
 877   static inline bool classof(const Matcher *N) {
 878     return N->getKind() == EmitNodeXForm;
 879   }
 880
 881 private:
 882   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 883   virtual bool isEqualImpl(const Matcher *M) const {
 884     return cast<EmitNodeXFormMatcher>(M)->Slot == Slot &&
 885            cast<EmitNodeXFormMatcher>(M)->NodeXForm == NodeXForm;
 886   }
 887   virtual unsigned getHashImpl() const {
 888     return Slot ^ ((unsigned)(intptr_t)NodeXForm << 4);
 889   }
 890 };
 891
 892 /// EmitNodeMatcherCommon - Common class shared between EmitNode and
 893 /// MorphNodeTo.
 894 class EmitNodeMatcherCommon : public Matcher {
 895   std::string OpcodeName;
 896   const SmallVector<MVT::SimpleValueType, 3> VTs;
 897   const SmallVector<unsigned, 6> Operands;
 898   bool HasChain, HasInFlag, HasOutFlag, HasMemRefs;
 899
 900   /// NumFixedArityOperands - If this is a fixed arity node, this is set to -1.
 901   /// If this is a varidic node, this is set to the number of fixed arity
 902   /// operands in the root of the pattern.  The rest are appended to this node.
 903   int NumFixedArityOperands;
 904 public:
 905   EmitNodeMatcherCommon(const std::string &opcodeName,
 906                         const MVT::SimpleValueType *vts, unsigned numvts,
 907                         const unsigned *operands, unsigned numops,
 908                         bool hasChain, bool hasInFlag, bool hasOutFlag,
 909                         bool hasmemrefs,
 910                         int numfixedarityoperands, bool isMorphNodeTo)
 911     : Matcher(isMorphNodeTo ? MorphNodeTo : EmitNode), OpcodeName(opcodeName),
 912       VTs(vts, vts+numvts), Operands(operands, operands+numops),
 913       HasChain(hasChain), HasInFlag(hasInFlag), HasOutFlag(hasOutFlag),
 914       HasMemRefs(hasmemrefs), NumFixedArityOperands(numfixedarityoperands) {}
 915
 916   const std::string &getOpcodeName() const { return OpcodeName; }
 917
 918   unsigned getNumVTs() const { return VTs.size(); }
 919   MVT::SimpleValueType getVT(unsigned i) const {
 920     assert(i < VTs.size());
 921     return VTs[i];
 922   }
 923
 924   unsigned getNumOperands() const { return Operands.size(); }
 925   unsigned getOperand(unsigned i) const {
 926     assert(i < Operands.size());
 927     return Operands[i];
 928   }
 929
 930   const SmallVectorImpl<MVT::SimpleValueType> &getVTList() const { return VTs; }
 931   const SmallVectorImpl<unsigned> &getOperandList() const { return Operands; }
 932
 933
 934   bool hasChain() const { return HasChain; }
 935   bool hasInFlag() const { return HasInFlag; }
 936   bool hasOutFlag() const { return HasOutFlag; }
 937   bool hasMemRefs() const { return HasMemRefs; }
 938   int getNumFixedArityOperands() const { return NumFixedArityOperands; }
 939
 940   static inline bool classof(const Matcher *N) {
 941     return N->getKind() == EmitNode || N->getKind() == MorphNodeTo;
 942   }
 943
 944 private:
 945   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
 946   virtual bool isEqualImpl(const Matcher *M) const;
 947   virtual unsigned getHashImpl() const;
 948 };
 949
 950 /// EmitNodeMatcher - This signals a successful match and generates a node.
 951 class EmitNodeMatcher : public EmitNodeMatcherCommon {
 952   unsigned FirstResultSlot;
 953 public:
 954   EmitNodeMatcher(const std::string &opcodeName,
 955                   const MVT::SimpleValueType *vts, unsigned numvts,
 956                   const unsigned *operands, unsigned numops,
 957                   bool hasChain, bool hasInFlag, bool hasOutFlag,
 958                   bool hasmemrefs,
 959                   int numfixedarityoperands, unsigned firstresultslot)
 960   : EmitNodeMatcherCommon(opcodeName, vts, numvts, operands, numops, hasChain,
 961                           hasInFlag, hasOutFlag, hasmemrefs,
 962                           numfixedarityoperands, false),
 963     FirstResultSlot(firstresultslot) {}
 964
 965   unsigned getFirstResultSlot() const { return FirstResultSlot; }
 966
 967   static inline bool classof(const Matcher *N) {
 968     return N->getKind() == EmitNode;
 969   }
 970
 971 };
 972
 973 class MorphNodeToMatcher : public EmitNodeMatcherCommon {
 974   const PatternToMatch &Pattern;
 975 public:
 976   MorphNodeToMatcher(const std::string &opcodeName,
 977                      const MVT::SimpleValueType *vts, unsigned numvts,
 978                      const unsigned *operands, unsigned numops,
 979                      bool hasChain, bool hasInFlag, bool hasOutFlag,
 980                      bool hasmemrefs,
 981                      int numfixedarityoperands, const PatternToMatch &pattern)
 982     : EmitNodeMatcherCommon(opcodeName, vts, numvts, operands, numops, hasChain,
 983                             hasInFlag, hasOutFlag, hasmemrefs,
 984                             numfixedarityoperands, true),
 985       Pattern(pattern) {
 986   }
 987
 988   const PatternToMatch &getPattern() const { return Pattern; }
 989
 990   static inline bool classof(const Matcher *N) {
 991     return N->getKind() == MorphNodeTo;
 992   }
 993 };
 994
 995 /// MarkFlagResultsMatcher - This node indicates which non-root nodes in the
 996 /// pattern produce flags.  This allows CompleteMatchMatcher to update them
 997 /// with the output flag of the resultant code.
 998 class MarkFlagResultsMatcher : public Matcher {
 999   SmallVector<unsigned, 3> FlagResultNodes;
1000 public:
1001   MarkFlagResultsMatcher(const unsigned *nodes, unsigned NumNodes)
1002     : Matcher(MarkFlagResults), FlagResultNodes(nodes, nodes+NumNodes) {}
1003
1004   unsigned getNumNodes() const { return FlagResultNodes.size(); }
1005
1006   unsigned getNode(unsigned i) const {
1007     assert(i < FlagResultNodes.size());
1008     return FlagResultNodes[i];
1009   }
1010
1011   static inline bool classof(const Matcher *N) {
1012     return N->getKind() == MarkFlagResults;
1013   }
1014
1015 private:
1016   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
1017   virtual bool isEqualImpl(const Matcher *M) const {
1018     return cast<MarkFlagResultsMatcher>(M)->FlagResultNodes == FlagResultNodes;
1019   }
1020   virtual unsigned getHashImpl() const;
1021 };
1022
1023 /// CompleteMatchMatcher - Complete a match by replacing the results of the
1024 /// pattern with the newly generated nodes.  This also prints a comment
1025 /// indicating the source and dest patterns.
1026 class CompleteMatchMatcher : public Matcher {
1027   SmallVector<unsigned, 2> Results;
1028   const PatternToMatch &Pattern;
1029 public:
1030   CompleteMatchMatcher(const unsigned *results, unsigned numresults,
1031                        const PatternToMatch &pattern)
1032   : Matcher(CompleteMatch), Results(results, results+numresults),
1033     Pattern(pattern) {}
1034
1035   unsigned getNumResults() const { return Results.size(); }
1036   unsigned getResult(unsigned R) const { return Results[R]; }
1037   const PatternToMatch &getPattern() const { return Pattern; }
1038
1039   static inline bool classof(const Matcher *N) {
1040     return N->getKind() == CompleteMatch;
1041   }
1042
1043 private:
1044   virtual void printImpl(raw_ostream &OS, unsigned indent) const;
1045   virtual bool isEqualImpl(const Matcher *M) const {
1046     return cast<CompleteMatchMatcher>(M)->Results == Results &&
1047           &cast<CompleteMatchMatcher>(M)->Pattern == &Pattern;
1048   }
1049   virtual unsigned getHashImpl() const;
1050 };
1051
1052 } // end namespace llvm
1053
1054 #endif