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