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