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