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