llvm/utils/TableGen/DAGISelMatcher.h

   1 //===- DAGISelMatcher.h - Representation of DAG pattern matcher -*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef LLVM_UTILS_TABLEGEN_DAGISELMATCHER_H
  10 #define LLVM_UTILS_TABLEGEN_DAGISELMATCHER_H
  11
  12 #include "llvm/ADT/ArrayRef.h"
  13 #include "llvm/ADT/SmallVector.h"
  14 #include "llvm/ADT/StringRef.h"
  15 #include "llvm/CodeGen/MachineValueType.h"
  16 #include "llvm/Support/Casting.h"
  17 #include <cassert>
  18 #include <cstddef>
  19 #include <memory>
  20 #include <string>
  21 #include <utility>
  22
  23 namespace llvm {
  24   class CodeGenRegister;
  25   class CodeGenDAGPatterns;
  26   class CodeGenInstruction;
  27   class Matcher;
  28   class PatternToMatch;
  29   class raw_ostream;
  30   class ComplexPattern;
  31   class Record;
  32   class SDNodeInfo;
  33   class TreePredicateFn;
  34   class TreePattern;
  35
  36   Matcher *ConvertPatternToMatcher(const PatternToMatch &Pattern,
  37                                    unsigned Variant,
  38                                    const CodeGenDAGPatterns &CGP);
  39   void OptimizeMatcher(std::unique_ptr<Matcher> &Matcher,
  40                        const CodeGenDAGPatterns &CGP);
  41   void EmitMatcherTable(Matcher *Matcher, const CodeGenDAGPatterns &CGP,
  42                         raw_ostream &OS);
  43
  44   /// Matcher - Base class for all the DAG ISel Matcher representation
  45   /// nodes.
  46   class Matcher {
  47     // The next matcher node that is executed after this one.  Null if this is
  48     // the last stage of a match.
  49     std::unique_ptr<Matcher> Next;
  50     size_t Size = 0; // Size in bytes of matcher and all its children (if any).
  51     virtual void anchor();
  52
  53   public:
  54     enum KindTy {
  55       // Matcher state manipulation.
  56       Scope,            // Push a checking scope.
  57       RecordNode,       // Record the current node.
  58       RecordChild,      // Record a child of the current node.
  59       RecordMemRef,     // Record the memref in the current node.
  60       CaptureGlueInput, // If the current node has an input glue, save it.
  61       MoveChild,        // Move current node to specified child.
  62       MoveSibling,      // Move current node to specified sibling.
  63       MoveParent,       // Move current node to parent.
  64
  65       // Predicate checking.
  66       CheckSame,      // Fail if not same as prev match.
  67       CheckChildSame, // Fail if child not same as prev match.
  68       CheckPatternPredicate,
  69       CheckPredicate,      // Fail if node predicate fails.
  70       CheckOpcode,         // Fail if not opcode.
  71       SwitchOpcode,        // Dispatch based on opcode.
  72       CheckType,           // Fail if not correct type.
  73       SwitchType,          // Dispatch based on type.
  74       CheckChildType,      // Fail if child has wrong type.
  75       CheckInteger,        // Fail if wrong val.
  76       CheckChildInteger,   // Fail if child is wrong val.
  77       CheckCondCode,       // Fail if not condcode.
  78       CheckChild2CondCode, // Fail if child is wrong condcode.
  79       CheckValueType,
  80       CheckComplexPat,
  81       CheckAndImm,
  82       CheckOrImm,
  83       CheckImmAllOnesV,
  84       CheckImmAllZerosV,
  85       CheckFoldableChainNode,
  86
  87       // Node creation/emisssion.
  88       EmitInteger,          // Create a TargetConstant
  89       EmitStringInteger,    // Create a TargetConstant from a string.
  90       EmitRegister,         // Create a register.
  91       EmitConvertToTarget,  // Convert a imm/fpimm to target imm/fpimm
  92       EmitMergeInputChains, // Merge together a chains for an input.
  93       EmitCopyToReg,        // Emit a copytoreg into a physreg.
  94       EmitNode,             // Create a DAG node
  95       EmitNodeXForm,        // Run a SDNodeXForm
  96       CompleteMatch,        // Finish a match and update the results.
  97       MorphNodeTo,          // Build a node, finish a match and update results.
  98
  99       // Highest enum value; watch out when adding more.
 100       HighestKind = MorphNodeTo
 101     };
 102     const KindTy Kind;
 103
 104   protected:
 105     Matcher(KindTy K) : Kind(K) {}
 106
 107   public:
 108     virtual ~Matcher() {}
 109
 110     unsigned getSize() const { return Size; }
 111     void setSize(unsigned sz) { Size = sz; }
 112     KindTy getKind() const { return Kind; }
 113
 114     Matcher *getNext() { return Next.get(); }
 115     const Matcher *getNext() const { return Next.get(); }
 116     void setNext(Matcher *C) { Next.reset(C); }
 117     Matcher *takeNext() { return Next.release(); }
 118
 119     std::unique_ptr<Matcher> &getNextPtr() { return Next; }
 120
 121     bool isEqual(const Matcher *M) const {
 122       if (getKind() != M->getKind())
 123         return false;
 124       return isEqualImpl(M);
 125     }
 126
 127     /// isSimplePredicateNode - Return true if this is a simple predicate that
 128     /// operates on the node or its children without potential side effects or a
 129     /// change of the current node.
 130     bool isSimplePredicateNode() const {
 131       switch (getKind()) {
 132       default:
 133         return false;
 134       case CheckSame:
 135       case CheckChildSame:
 136       case CheckPatternPredicate:
 137       case CheckPredicate:
 138       case CheckOpcode:
 139       case CheckType:
 140       case CheckChildType:
 141       case CheckInteger:
 142       case CheckChildInteger:
 143       case CheckCondCode:
 144       case CheckChild2CondCode:
 145       case CheckValueType:
 146       case CheckAndImm:
 147       case CheckOrImm:
 148       case CheckImmAllOnesV:
 149       case CheckImmAllZerosV:
 150       case CheckFoldableChainNode:
 151         return true;
 152       }
 153     }
 154
 155     /// isSimplePredicateOrRecordNode - Return true if this is a record node or
 156     /// a simple predicate.
 157     bool isSimplePredicateOrRecordNode() const {
 158       return isSimplePredicateNode() || getKind() == RecordNode ||
 159              getKind() == RecordChild;
 160     }
 161
 162     /// unlinkNode - Unlink the specified node from this chain.  If Other ==
 163     /// this, we unlink the next pointer and return it.  Otherwise we unlink
 164     /// Other from the list and return this.
 165     Matcher *unlinkNode(Matcher *Other);
 166
 167     /// canMoveBefore - Return true if this matcher is the same as Other, or if
 168     /// we can move this matcher past all of the nodes in-between Other and this
 169     /// node.  Other must be equal to or before this.
 170     bool canMoveBefore(const Matcher *Other) const;
 171
 172     /// canMoveBeforeNode - Return true if it is safe to move the current
 173     /// matcher across the specified one.
 174     bool canMoveBeforeNode(const Matcher *Other) const;
 175
 176     /// isContradictory - Return true of these two matchers could never match on
 177     /// the same node.
 178     bool isContradictory(const Matcher *Other) const {
 179       // Since this predicate is reflexive, we canonicalize the ordering so that
 180       // we always match a node against nodes with kinds that are greater or
 181       // equal to them.  For example, we'll pass in a CheckType node as an
 182       // argument to the CheckOpcode method, not the other way around.
 183       if (getKind() < Other->getKind())
 184         return isContradictoryImpl(Other);
 185       return Other->isContradictoryImpl(this);
 186     }
 187
 188     void print(raw_ostream &OS, unsigned indent = 0) const;
 189     void printOne(raw_ostream &OS) const;
 190     void dump() const;
 191
 192   protected:
 193     virtual void printImpl(raw_ostream &OS, unsigned indent) const = 0;
 194     virtual bool isEqualImpl(const Matcher *M) const = 0;
 195     virtual bool isContradictoryImpl(const Matcher *M) const { return false; }
 196   };
 197
 198 /// ScopeMatcher - This attempts to match each of its children to find the first
 199 /// one that successfully matches.  If one child fails, it tries the next child.
 200 /// If none of the children match then this check fails.  It never has a 'next'.
 201 class ScopeMatcher : public Matcher {
 202   SmallVector<Matcher*, 4> Children;
 203 public:
 204   ScopeMatcher(SmallVectorImpl<Matcher *> &&children)
 205       : Matcher(Scope), Children(std::move(children)) {}
 206   ~ScopeMatcher() override;
 207
 208   unsigned getNumChildren() const { return Children.size(); }
 209
 210   Matcher *getChild(unsigned i) { return Children[i]; }
 211   const Matcher *getChild(unsigned i) const { return Children[i]; }
 212
 213   void resetChild(unsigned i, Matcher *N) {
 214     delete Children[i];
 215     Children[i] = N;
 216   }
 217
 218   Matcher *takeChild(unsigned i) {
 219     Matcher *Res = Children[i];
 220     Children[i] = nullptr;
 221     return Res;
 222   }
 223
 224   void setNumChildren(unsigned NC) {
 225     if (NC < Children.size()) {
 226       // delete any children we're about to lose pointers to.
 227       for (unsigned i = NC, e = Children.size(); i != e; ++i)
 228         delete Children[i];
 229     }
 230     Children.resize(NC);
 231   }
 232
 233   static bool classof(const Matcher *N) {
 234     return N->getKind() == Scope;
 235   }
 236
 237 private:
 238   void printImpl(raw_ostream &OS, unsigned indent) const override;
 239   bool isEqualImpl(const Matcher *M) const override { return false; }
 240 };
 241
 242 /// RecordMatcher - Save the current node in the operand list.
 243 class RecordMatcher : public Matcher {
 244   /// WhatFor - This is a string indicating why we're recording this.  This
 245   /// should only be used for comment generation not anything semantic.
 246   std::string WhatFor;
 247
 248   /// ResultNo - The slot number in the RecordedNodes vector that this will be,
 249   /// just printed as a comment.
 250   unsigned ResultNo;
 251 public:
 252   RecordMatcher(const std::string &whatfor, unsigned resultNo)
 253     : Matcher(RecordNode), WhatFor(whatfor), ResultNo(resultNo) {}
 254
 255   const std::string &getWhatFor() const { return WhatFor; }
 256   unsigned getResultNo() const { return ResultNo; }
 257
 258   static bool classof(const Matcher *N) {
 259     return N->getKind() == RecordNode;
 260   }
 261
 262 private:
 263   void printImpl(raw_ostream &OS, unsigned indent) const override;
 264   bool isEqualImpl(const Matcher *M) const override { return true; }
 265 };
 266
 267 /// RecordChildMatcher - Save a numbered child of the current node, or fail
 268 /// the match if it doesn't exist.  This is logically equivalent to:
 269 ///    MoveChild N + RecordNode + MoveParent.
 270 class RecordChildMatcher : public Matcher {
 271   unsigned ChildNo;
 272
 273   /// WhatFor - This is a string indicating why we're recording this.  This
 274   /// should only be used for comment generation not anything semantic.
 275   std::string WhatFor;
 276
 277   /// ResultNo - The slot number in the RecordedNodes vector that this will be,
 278   /// just printed as a comment.
 279   unsigned ResultNo;
 280 public:
 281   RecordChildMatcher(unsigned childno, const std::string &whatfor,
 282                      unsigned resultNo)
 283   : Matcher(RecordChild), ChildNo(childno), WhatFor(whatfor),
 284     ResultNo(resultNo) {}
 285
 286   unsigned getChildNo() const { return ChildNo; }
 287   const std::string &getWhatFor() const { return WhatFor; }
 288   unsigned getResultNo() const { return ResultNo; }
 289
 290   static bool classof(const Matcher *N) {
 291     return N->getKind() == RecordChild;
 292   }
 293
 294 private:
 295   void printImpl(raw_ostream &OS, unsigned indent) const override;
 296   bool isEqualImpl(const Matcher *M) const override {
 297     return cast<RecordChildMatcher>(M)->getChildNo() == getChildNo();
 298   }
 299 };
 300
 301 /// RecordMemRefMatcher - Save the current node's memref.
 302 class RecordMemRefMatcher : public Matcher {
 303 public:
 304   RecordMemRefMatcher() : Matcher(RecordMemRef) {}
 305
 306   static bool classof(const Matcher *N) {
 307     return N->getKind() == RecordMemRef;
 308   }
 309
 310 private:
 311   void printImpl(raw_ostream &OS, unsigned indent) const override;
 312   bool isEqualImpl(const Matcher *M) const override { return true; }
 313 };
 314
 315
 316 /// CaptureGlueInputMatcher - If the current record has a glue input, record
 317 /// it so that it is used as an input to the generated code.
 318 class CaptureGlueInputMatcher : public Matcher {
 319 public:
 320   CaptureGlueInputMatcher() : Matcher(CaptureGlueInput) {}
 321
 322   static bool classof(const Matcher *N) {
 323     return N->getKind() == CaptureGlueInput;
 324   }
 325
 326 private:
 327   void printImpl(raw_ostream &OS, unsigned indent) const override;
 328   bool isEqualImpl(const Matcher *M) const override { return true; }
 329 };
 330
 331 /// MoveChildMatcher - This tells the interpreter to move into the
 332 /// specified child node.
 333 class MoveChildMatcher : public Matcher {
 334   unsigned ChildNo;
 335 public:
 336   MoveChildMatcher(unsigned childNo) : Matcher(MoveChild), ChildNo(childNo) {}
 337
 338   unsigned getChildNo() const { return ChildNo; }
 339
 340   static bool classof(const Matcher *N) {
 341     return N->getKind() == MoveChild;
 342   }
 343
 344 private:
 345   void printImpl(raw_ostream &OS, unsigned indent) const override;
 346   bool isEqualImpl(const Matcher *M) const override {
 347     return cast<MoveChildMatcher>(M)->getChildNo() == getChildNo();
 348   }
 349 };
 350
 351 /// MoveSiblingMatcher - This tells the interpreter to move into the
 352 /// specified sibling node.
 353 class MoveSiblingMatcher : public Matcher {
 354   unsigned SiblingNo;
 355
 356 public:
 357   MoveSiblingMatcher(unsigned SiblingNo)
 358       : Matcher(MoveSibling), SiblingNo(SiblingNo) {}
 359
 360   unsigned getSiblingNo() const { return SiblingNo; }
 361
 362   static bool classof(const Matcher *N) { return N->getKind() == MoveSibling; }
 363
 364 private:
 365   void printImpl(raw_ostream &OS, unsigned Indent) const override;
 366   bool isEqualImpl(const Matcher *M) const override {
 367     return cast<MoveSiblingMatcher>(M)->getSiblingNo() == getSiblingNo();
 368   }
 369 };
 370
 371 /// MoveParentMatcher - This tells the interpreter to move to the parent
 372 /// of the current node.
 373 class MoveParentMatcher : public Matcher {
 374 public:
 375   MoveParentMatcher() : Matcher(MoveParent) {}
 376
 377   static bool classof(const Matcher *N) {
 378     return N->getKind() == MoveParent;
 379   }
 380
 381 private:
 382   void printImpl(raw_ostream &OS, unsigned indent) const override;
 383   bool isEqualImpl(const Matcher *M) const override { return true; }
 384 };
 385
 386 /// CheckSameMatcher - This checks to see if this node is exactly the same
 387 /// node as the specified match that was recorded with 'Record'.  This is used
 388 /// when patterns have the same name in them, like '(mul GPR:$in, GPR:$in)'.
 389 class CheckSameMatcher : public Matcher {
 390   unsigned MatchNumber;
 391 public:
 392   CheckSameMatcher(unsigned matchnumber)
 393     : Matcher(CheckSame), MatchNumber(matchnumber) {}
 394
 395   unsigned getMatchNumber() const { return MatchNumber; }
 396
 397   static bool classof(const Matcher *N) {
 398     return N->getKind() == CheckSame;
 399   }
 400
 401 private:
 402   void printImpl(raw_ostream &OS, unsigned indent) const override;
 403   bool isEqualImpl(const Matcher *M) const override {
 404     return cast<CheckSameMatcher>(M)->getMatchNumber() == getMatchNumber();
 405   }
 406 };
 407
 408 /// CheckChildSameMatcher - This checks to see if child node is exactly the same
 409 /// node as the specified match that was recorded with 'Record'.  This is used
 410 /// when patterns have the same name in them, like '(mul GPR:$in, GPR:$in)'.
 411 class CheckChildSameMatcher : public Matcher {
 412   unsigned ChildNo;
 413   unsigned MatchNumber;
 414 public:
 415   CheckChildSameMatcher(unsigned childno, unsigned matchnumber)
 416     : Matcher(CheckChildSame), ChildNo(childno), MatchNumber(matchnumber) {}
 417
 418   unsigned getChildNo() const { return ChildNo; }
 419   unsigned getMatchNumber() const { return MatchNumber; }
 420
 421   static bool classof(const Matcher *N) {
 422     return N->getKind() == CheckChildSame;
 423   }
 424
 425 private:
 426   void printImpl(raw_ostream &OS, unsigned indent) const override;
 427   bool isEqualImpl(const Matcher *M) const override {
 428     return cast<CheckChildSameMatcher>(M)->ChildNo == ChildNo &&
 429            cast<CheckChildSameMatcher>(M)->MatchNumber == MatchNumber;
 430   }
 431 };
 432
 433 /// CheckPatternPredicateMatcher - This checks the target-specific predicate
 434 /// to see if the entire pattern is capable of matching.  This predicate does
 435 /// not take a node as input.  This is used for subtarget feature checks etc.
 436 class CheckPatternPredicateMatcher : public Matcher {
 437   std::string Predicate;
 438 public:
 439   CheckPatternPredicateMatcher(StringRef predicate)
 440     : Matcher(CheckPatternPredicate), Predicate(predicate) {}
 441
 442   StringRef getPredicate() const { return Predicate; }
 443
 444   static bool classof(const Matcher *N) {
 445     return N->getKind() == CheckPatternPredicate;
 446   }
 447
 448 private:
 449   void printImpl(raw_ostream &OS, unsigned indent) const override;
 450   bool isEqualImpl(const Matcher *M) const override {
 451     return cast<CheckPatternPredicateMatcher>(M)->getPredicate() == Predicate;
 452   }
 453 };
 454
 455 /// CheckPredicateMatcher - This checks the target-specific predicate to
 456 /// see if the node is acceptable.
 457 class CheckPredicateMatcher : public Matcher {
 458   TreePattern *Pred;
 459   const SmallVector<unsigned, 4> Operands;
 460 public:
 461   CheckPredicateMatcher(const TreePredicateFn &pred,
 462                         const SmallVectorImpl<unsigned> &Operands);
 463
 464   TreePredicateFn getPredicate() const;
 465   unsigned getNumOperands() const;
 466   unsigned getOperandNo(unsigned i) const;
 467
 468   static bool classof(const Matcher *N) {
 469     return N->getKind() == CheckPredicate;
 470   }
 471
 472 private:
 473   void printImpl(raw_ostream &OS, unsigned indent) const override;
 474   bool isEqualImpl(const Matcher *M) const override {
 475     return cast<CheckPredicateMatcher>(M)->Pred == Pred;
 476   }
 477 };
 478
 479
 480 /// CheckOpcodeMatcher - This checks to see if the current node has the
 481 /// specified opcode, if not it fails to match.
 482 class CheckOpcodeMatcher : public Matcher {
 483   const SDNodeInfo &Opcode;
 484 public:
 485   CheckOpcodeMatcher(const SDNodeInfo &opcode)
 486     : Matcher(CheckOpcode), Opcode(opcode) {}
 487
 488   const SDNodeInfo &getOpcode() const { return Opcode; }
 489
 490   static bool classof(const Matcher *N) {
 491     return N->getKind() == CheckOpcode;
 492   }
 493
 494 private:
 495   void printImpl(raw_ostream &OS, unsigned indent) const override;
 496   bool isEqualImpl(const Matcher *M) const override;
 497   bool isContradictoryImpl(const Matcher *M) const override;
 498 };
 499
 500 /// SwitchOpcodeMatcher - Switch based on the current node's opcode, dispatching
 501 /// to one matcher per opcode.  If the opcode doesn't match any of the cases,
 502 /// then the match fails.  This is semantically equivalent to a Scope node where
 503 /// every child does a CheckOpcode, but is much faster.
 504 class SwitchOpcodeMatcher : public Matcher {
 505   SmallVector<std::pair<const SDNodeInfo*, Matcher*>, 8> Cases;
 506 public:
 507   SwitchOpcodeMatcher(
 508       SmallVectorImpl<std::pair<const SDNodeInfo *, Matcher *>> &&cases)
 509       : Matcher(SwitchOpcode), Cases(std::move(cases)) {}
 510   ~SwitchOpcodeMatcher() override;
 511
 512   static bool classof(const Matcher *N) {
 513     return N->getKind() == SwitchOpcode;
 514   }
 515
 516   unsigned getNumCases() const { return Cases.size(); }
 517
 518   const SDNodeInfo &getCaseOpcode(unsigned i) const { return *Cases[i].first; }
 519   Matcher *getCaseMatcher(unsigned i) { return Cases[i].second; }
 520   const Matcher *getCaseMatcher(unsigned i) const { return Cases[i].second; }
 521
 522 private:
 523   void printImpl(raw_ostream &OS, unsigned indent) const override;
 524   bool isEqualImpl(const Matcher *M) const override { return false; }
 525 };
 526
 527 /// CheckTypeMatcher - This checks to see if the current node has the
 528 /// specified type at the specified result, if not it fails to match.
 529 class CheckTypeMatcher : public Matcher {
 530   MVT::SimpleValueType Type;
 531   unsigned ResNo;
 532 public:
 533   CheckTypeMatcher(MVT::SimpleValueType type, unsigned resno)
 534     : Matcher(CheckType), Type(type), ResNo(resno) {}
 535
 536   MVT::SimpleValueType getType() const { return Type; }
 537   unsigned getResNo() const { return ResNo; }
 538
 539   static bool classof(const Matcher *N) {
 540     return N->getKind() == CheckType;
 541   }
 542
 543 private:
 544   void printImpl(raw_ostream &OS, unsigned indent) const override;
 545   bool isEqualImpl(const Matcher *M) const override {
 546     return cast<CheckTypeMatcher>(M)->Type == Type;
 547   }
 548   bool isContradictoryImpl(const Matcher *M) const override;
 549 };
 550
 551 /// SwitchTypeMatcher - Switch based on the current node's type, dispatching
 552 /// to one matcher per case.  If the type doesn't match any of the cases,
 553 /// then the match fails.  This is semantically equivalent to a Scope node where
 554 /// every child does a CheckType, but is much faster.
 555 class SwitchTypeMatcher : public Matcher {
 556   SmallVector<std::pair<MVT::SimpleValueType, Matcher*>, 8> Cases;
 557 public:
 558   SwitchTypeMatcher(
 559       SmallVectorImpl<std::pair<MVT::SimpleValueType, Matcher *>> &&cases)
 560       : Matcher(SwitchType), Cases(std::move(cases)) {}
 561   ~SwitchTypeMatcher() override;
 562
 563   static bool classof(const Matcher *N) {
 564     return N->getKind() == SwitchType;
 565   }
 566
 567   unsigned getNumCases() const { return Cases.size(); }
 568
 569   MVT::SimpleValueType getCaseType(unsigned i) const { return Cases[i].first; }
 570   Matcher *getCaseMatcher(unsigned i) { return Cases[i].second; }
 571   const Matcher *getCaseMatcher(unsigned i) const { return Cases[i].second; }
 572
 573 private:
 574   void printImpl(raw_ostream &OS, unsigned indent) const override;
 575   bool isEqualImpl(const Matcher *M) const override { return false; }
 576 };
 577
 578
 579 /// CheckChildTypeMatcher - This checks to see if a child node has the
 580 /// specified type, if not it fails to match.
 581 class CheckChildTypeMatcher : public Matcher {
 582   unsigned ChildNo;
 583   MVT::SimpleValueType Type;
 584 public:
 585   CheckChildTypeMatcher(unsigned childno, MVT::SimpleValueType type)
 586     : Matcher(CheckChildType), ChildNo(childno), Type(type) {}
 587
 588   unsigned getChildNo() const { return ChildNo; }
 589   MVT::SimpleValueType getType() const { return Type; }
 590
 591   static bool classof(const Matcher *N) {
 592     return N->getKind() == CheckChildType;
 593   }
 594
 595 private:
 596   void printImpl(raw_ostream &OS, unsigned indent) const override;
 597   bool isEqualImpl(const Matcher *M) const override {
 598     return cast<CheckChildTypeMatcher>(M)->ChildNo == ChildNo &&
 599            cast<CheckChildTypeMatcher>(M)->Type == Type;
 600   }
 601   bool isContradictoryImpl(const Matcher *M) const override;
 602 };
 603
 604
 605 /// CheckIntegerMatcher - This checks to see if the current node is a
 606 /// ConstantSDNode with the specified integer value, if not it fails to match.
 607 class CheckIntegerMatcher : public Matcher {
 608   int64_t Value;
 609 public:
 610   CheckIntegerMatcher(int64_t value)
 611     : Matcher(CheckInteger), Value(value) {}
 612
 613   int64_t getValue() const { return Value; }
 614
 615   static bool classof(const Matcher *N) {
 616     return N->getKind() == CheckInteger;
 617   }
 618
 619 private:
 620   void printImpl(raw_ostream &OS, unsigned indent) const override;
 621   bool isEqualImpl(const Matcher *M) const override {
 622     return cast<CheckIntegerMatcher>(M)->Value == Value;
 623   }
 624   bool isContradictoryImpl(const Matcher *M) const override;
 625 };
 626
 627 /// CheckChildIntegerMatcher - This checks to see if the child node is a
 628 /// ConstantSDNode with a specified integer value, if not it fails to match.
 629 class CheckChildIntegerMatcher : public Matcher {
 630   unsigned ChildNo;
 631   int64_t Value;
 632 public:
 633   CheckChildIntegerMatcher(unsigned childno, int64_t value)
 634     : Matcher(CheckChildInteger), ChildNo(childno), Value(value) {}
 635
 636   unsigned getChildNo() const { return ChildNo; }
 637   int64_t getValue() const { return Value; }
 638
 639   static bool classof(const Matcher *N) {
 640     return N->getKind() == CheckChildInteger;
 641   }
 642
 643 private:
 644   void printImpl(raw_ostream &OS, unsigned indent) const override;
 645   bool isEqualImpl(const Matcher *M) const override {
 646     return cast<CheckChildIntegerMatcher>(M)->ChildNo == ChildNo &&
 647            cast<CheckChildIntegerMatcher>(M)->Value == Value;
 648   }
 649   bool isContradictoryImpl(const Matcher *M) const override;
 650 };
 651
 652 /// CheckCondCodeMatcher - This checks to see if the current node is a
 653 /// CondCodeSDNode with the specified condition, if not it fails to match.
 654 class CheckCondCodeMatcher : public Matcher {
 655   StringRef CondCodeName;
 656 public:
 657   CheckCondCodeMatcher(StringRef condcodename)
 658     : Matcher(CheckCondCode), CondCodeName(condcodename) {}
 659
 660   StringRef getCondCodeName() const { return CondCodeName; }
 661
 662   static bool classof(const Matcher *N) {
 663     return N->getKind() == CheckCondCode;
 664   }
 665
 666 private:
 667   void printImpl(raw_ostream &OS, unsigned indent) const override;
 668   bool isEqualImpl(const Matcher *M) const override {
 669     return cast<CheckCondCodeMatcher>(M)->CondCodeName == CondCodeName;
 670   }
 671   bool isContradictoryImpl(const Matcher *M) const override;
 672 };
 673
 674 /// CheckChild2CondCodeMatcher - This checks to see if child 2 node is a
 675 /// CondCodeSDNode with the specified condition, if not it fails to match.
 676 class CheckChild2CondCodeMatcher : public Matcher {
 677   StringRef CondCodeName;
 678 public:
 679   CheckChild2CondCodeMatcher(StringRef condcodename)
 680     : Matcher(CheckChild2CondCode), CondCodeName(condcodename) {}
 681
 682   StringRef getCondCodeName() const { return CondCodeName; }
 683
 684   static bool classof(const Matcher *N) {
 685     return N->getKind() == CheckChild2CondCode;
 686   }
 687
 688 private:
 689   void printImpl(raw_ostream &OS, unsigned indent) const override;
 690   bool isEqualImpl(const Matcher *M) const override {
 691     return cast<CheckChild2CondCodeMatcher>(M)->CondCodeName == CondCodeName;
 692   }
 693   bool isContradictoryImpl(const Matcher *M) const override;
 694 };
 695
 696 /// CheckValueTypeMatcher - This checks to see if the current node is a
 697 /// VTSDNode with the specified type, if not it fails to match.
 698 class CheckValueTypeMatcher : public Matcher {
 699   StringRef TypeName;
 700 public:
 701   CheckValueTypeMatcher(StringRef type_name)
 702     : Matcher(CheckValueType), TypeName(type_name) {}
 703
 704   StringRef getTypeName() const { return TypeName; }
 705
 706   static bool classof(const Matcher *N) {
 707     return N->getKind() == CheckValueType;
 708   }
 709
 710 private:
 711   void printImpl(raw_ostream &OS, unsigned indent) const override;
 712   bool isEqualImpl(const Matcher *M) const override {
 713     return cast<CheckValueTypeMatcher>(M)->TypeName == TypeName;
 714   }
 715   bool isContradictoryImpl(const Matcher *M) const override;
 716 };
 717
 718
 719
 720 /// CheckComplexPatMatcher - This node runs the specified ComplexPattern on
 721 /// the current node.
 722 class CheckComplexPatMatcher : public Matcher {
 723   const ComplexPattern &Pattern;
 724
 725   /// MatchNumber - This is the recorded nodes slot that contains the node we
 726   /// want to match against.
 727   unsigned MatchNumber;
 728
 729   /// Name - The name of the node we're matching, for comment emission.
 730   std::string Name;
 731
 732   /// FirstResult - This is the first slot in the RecordedNodes list that the
 733   /// result of the match populates.
 734   unsigned FirstResult;
 735 public:
 736   CheckComplexPatMatcher(const ComplexPattern &pattern, unsigned matchnumber,
 737                          const std::string &name, unsigned firstresult)
 738     : Matcher(CheckComplexPat), Pattern(pattern), MatchNumber(matchnumber),
 739       Name(name), FirstResult(firstresult) {}
 740
 741   const ComplexPattern &getPattern() const { return Pattern; }
 742   unsigned getMatchNumber() const { return MatchNumber; }
 743
 744   std::string getName() const { return Name; }
 745   unsigned getFirstResult() const { return FirstResult; }
 746
 747   static bool classof(const Matcher *N) {
 748     return N->getKind() == CheckComplexPat;
 749   }
 750
 751 private:
 752   void printImpl(raw_ostream &OS, unsigned indent) const override;
 753   bool isEqualImpl(const Matcher *M) const override {
 754     return &cast<CheckComplexPatMatcher>(M)->Pattern == &Pattern &&
 755            cast<CheckComplexPatMatcher>(M)->MatchNumber == MatchNumber;
 756   }
 757 };
 758
 759 /// CheckAndImmMatcher - This checks to see if the current node is an 'and'
 760 /// with something equivalent to the specified immediate.
 761 class CheckAndImmMatcher : public Matcher {
 762   int64_t Value;
 763 public:
 764   CheckAndImmMatcher(int64_t value)
 765     : Matcher(CheckAndImm), Value(value) {}
 766
 767   int64_t getValue() const { return Value; }
 768
 769   static bool classof(const Matcher *N) {
 770     return N->getKind() == CheckAndImm;
 771   }
 772
 773 private:
 774   void printImpl(raw_ostream &OS, unsigned indent) const override;
 775   bool isEqualImpl(const Matcher *M) const override {
 776     return cast<CheckAndImmMatcher>(M)->Value == Value;
 777   }
 778 };
 779
 780 /// CheckOrImmMatcher - This checks to see if the current node is an 'and'
 781 /// with something equivalent to the specified immediate.
 782 class CheckOrImmMatcher : public Matcher {
 783   int64_t Value;
 784 public:
 785   CheckOrImmMatcher(int64_t value)
 786     : Matcher(CheckOrImm), Value(value) {}
 787
 788   int64_t getValue() const { return Value; }
 789
 790   static bool classof(const Matcher *N) {
 791     return N->getKind() == CheckOrImm;
 792   }
 793
 794 private:
 795   void printImpl(raw_ostream &OS, unsigned indent) const override;
 796   bool isEqualImpl(const Matcher *M) const override {
 797     return cast<CheckOrImmMatcher>(M)->Value == Value;
 798   }
 799 };
 800
 801 /// CheckImmAllOnesVMatcher - This checks if the current node is a build_vector
 802 /// or splat_vector of all ones.
 803 class CheckImmAllOnesVMatcher : public Matcher {
 804 public:
 805   CheckImmAllOnesVMatcher() : Matcher(CheckImmAllOnesV) {}
 806
 807   static bool classof(const Matcher *N) {
 808     return N->getKind() == CheckImmAllOnesV;
 809   }
 810
 811 private:
 812   void printImpl(raw_ostream &OS, unsigned indent) const override;
 813   bool isEqualImpl(const Matcher *M) const override { return true; }
 814   bool isContradictoryImpl(const Matcher *M) const override;
 815 };
 816
 817 /// CheckImmAllZerosVMatcher - This checks if the current node is a
 818 /// build_vector or splat_vector of all zeros.
 819 class CheckImmAllZerosVMatcher : public Matcher {
 820 public:
 821   CheckImmAllZerosVMatcher() : Matcher(CheckImmAllZerosV) {}
 822
 823   static bool classof(const Matcher *N) {
 824     return N->getKind() == CheckImmAllZerosV;
 825   }
 826
 827 private:
 828   void printImpl(raw_ostream &OS, unsigned indent) const override;
 829   bool isEqualImpl(const Matcher *M) const override { return true; }
 830   bool isContradictoryImpl(const Matcher *M) const override;
 831 };
 832
 833 /// CheckFoldableChainNodeMatcher - This checks to see if the current node
 834 /// (which defines a chain operand) is safe to fold into a larger pattern.
 835 class CheckFoldableChainNodeMatcher : public Matcher {
 836 public:
 837   CheckFoldableChainNodeMatcher()
 838     : Matcher(CheckFoldableChainNode) {}
 839
 840   static bool classof(const Matcher *N) {
 841     return N->getKind() == CheckFoldableChainNode;
 842   }
 843
 844 private:
 845   void printImpl(raw_ostream &OS, unsigned indent) const override;
 846   bool isEqualImpl(const Matcher *M) const override { return true; }
 847 };
 848
 849 /// EmitIntegerMatcher - This creates a new TargetConstant.
 850 class EmitIntegerMatcher : public Matcher {
 851   int64_t Val;
 852   MVT::SimpleValueType VT;
 853 public:
 854   EmitIntegerMatcher(int64_t val, MVT::SimpleValueType vt)
 855     : Matcher(EmitInteger), Val(val), VT(vt) {}
 856
 857   int64_t getValue() const { return Val; }
 858   MVT::SimpleValueType getVT() const { return VT; }
 859
 860   static bool classof(const Matcher *N) {
 861     return N->getKind() == EmitInteger;
 862   }
 863
 864 private:
 865   void printImpl(raw_ostream &OS, unsigned indent) const override;
 866   bool isEqualImpl(const Matcher *M) const override {
 867     return cast<EmitIntegerMatcher>(M)->Val == Val &&
 868            cast<EmitIntegerMatcher>(M)->VT == VT;
 869   }
 870 };
 871
 872 /// EmitStringIntegerMatcher - A target constant whose value is represented
 873 /// by a string.
 874 class EmitStringIntegerMatcher : public Matcher {
 875   std::string Val;
 876   MVT::SimpleValueType VT;
 877 public:
 878   EmitStringIntegerMatcher(const std::string &val, MVT::SimpleValueType vt)
 879     : Matcher(EmitStringInteger), Val(val), VT(vt) {}
 880
 881   const std::string &getValue() const { return Val; }
 882   MVT::SimpleValueType getVT() const { return VT; }
 883
 884   static bool classof(const Matcher *N) {
 885     return N->getKind() == EmitStringInteger;
 886   }
 887
 888 private:
 889   void printImpl(raw_ostream &OS, unsigned indent) const override;
 890   bool isEqualImpl(const Matcher *M) const override {
 891     return cast<EmitStringIntegerMatcher>(M)->Val == Val &&
 892            cast<EmitStringIntegerMatcher>(M)->VT == VT;
 893   }
 894 };
 895
 896 /// EmitRegisterMatcher - This creates a new TargetConstant.
 897 class EmitRegisterMatcher : public Matcher {
 898   /// Reg - The def for the register that we're emitting.  If this is null, then
 899   /// this is a reference to zero_reg.
 900   const CodeGenRegister *Reg;
 901   MVT::SimpleValueType VT;
 902 public:
 903   EmitRegisterMatcher(const CodeGenRegister *reg, MVT::SimpleValueType vt)
 904     : Matcher(EmitRegister), Reg(reg), VT(vt) {}
 905
 906   const CodeGenRegister *getReg() const { return Reg; }
 907   MVT::SimpleValueType getVT() const { return VT; }
 908
 909   static bool classof(const Matcher *N) {
 910     return N->getKind() == EmitRegister;
 911   }
 912
 913 private:
 914   void printImpl(raw_ostream &OS, unsigned indent) const override;
 915   bool isEqualImpl(const Matcher *M) const override {
 916     return cast<EmitRegisterMatcher>(M)->Reg == Reg &&
 917            cast<EmitRegisterMatcher>(M)->VT == VT;
 918   }
 919 };
 920
 921 /// EmitConvertToTargetMatcher - Emit an operation that reads a specified
 922 /// recorded node and converts it from being a ISD::Constant to
 923 /// ISD::TargetConstant, likewise for ConstantFP.
 924 class EmitConvertToTargetMatcher : public Matcher {
 925   unsigned Slot;
 926 public:
 927   EmitConvertToTargetMatcher(unsigned slot)
 928     : Matcher(EmitConvertToTarget), Slot(slot) {}
 929
 930   unsigned getSlot() const { return Slot; }
 931
 932   static bool classof(const Matcher *N) {
 933     return N->getKind() == EmitConvertToTarget;
 934   }
 935
 936 private:
 937   void printImpl(raw_ostream &OS, unsigned indent) const override;
 938   bool isEqualImpl(const Matcher *M) const override {
 939     return cast<EmitConvertToTargetMatcher>(M)->Slot == Slot;
 940   }
 941 };
 942
 943 /// EmitMergeInputChainsMatcher - Emit a node that merges a list of input
 944 /// chains together with a token factor.  The list of nodes are the nodes in the
 945 /// matched pattern that have chain input/outputs.  This node adds all input
 946 /// chains of these nodes if they are not themselves a node in the pattern.
 947 class EmitMergeInputChainsMatcher : public Matcher {
 948   SmallVector<unsigned, 3> ChainNodes;
 949 public:
 950   EmitMergeInputChainsMatcher(ArrayRef<unsigned> nodes)
 951     : Matcher(EmitMergeInputChains), ChainNodes(nodes.begin(), nodes.end()) {}
 952
 953   unsigned getNumNodes() const { return ChainNodes.size(); }
 954
 955   unsigned getNode(unsigned i) const {
 956     assert(i < ChainNodes.size());
 957     return ChainNodes[i];
 958   }
 959
 960   static bool classof(const Matcher *N) {
 961     return N->getKind() == EmitMergeInputChains;
 962   }
 963
 964 private:
 965   void printImpl(raw_ostream &OS, unsigned indent) const override;
 966   bool isEqualImpl(const Matcher *M) const override {
 967     return cast<EmitMergeInputChainsMatcher>(M)->ChainNodes == ChainNodes;
 968   }
 969 };
 970
 971 /// EmitCopyToRegMatcher - Emit a CopyToReg node from a value to a physreg,
 972 /// pushing the chain and glue results.
 973 ///
 974 class EmitCopyToRegMatcher : public Matcher {
 975   unsigned SrcSlot; // Value to copy into the physreg.
 976   const CodeGenRegister *DestPhysReg;
 977
 978 public:
 979   EmitCopyToRegMatcher(unsigned srcSlot,
 980                        const CodeGenRegister *destPhysReg)
 981     : Matcher(EmitCopyToReg), SrcSlot(srcSlot), DestPhysReg(destPhysReg) {}
 982
 983   unsigned getSrcSlot() const { return SrcSlot; }
 984   const CodeGenRegister *getDestPhysReg() const { return DestPhysReg; }
 985
 986   static bool classof(const Matcher *N) {
 987     return N->getKind() == EmitCopyToReg;
 988   }
 989
 990 private:
 991   void printImpl(raw_ostream &OS, unsigned indent) const override;
 992   bool isEqualImpl(const Matcher *M) const override {
 993     return cast<EmitCopyToRegMatcher>(M)->SrcSlot == SrcSlot &&
 994            cast<EmitCopyToRegMatcher>(M)->DestPhysReg == DestPhysReg;
 995   }
 996 };
 997
 998
 999
1000 /// EmitNodeXFormMatcher - Emit an operation that runs an SDNodeXForm on a
1001 /// recorded node and records the result.
1002 class EmitNodeXFormMatcher : public Matcher {
1003   unsigned Slot;
1004   Record *NodeXForm;
1005 public:
1006   EmitNodeXFormMatcher(unsigned slot, Record *nodeXForm)
1007     : Matcher(EmitNodeXForm), Slot(slot), NodeXForm(nodeXForm) {}
1008
1009   unsigned getSlot() const { return Slot; }
1010   Record *getNodeXForm() const { return NodeXForm; }
1011
1012   static bool classof(const Matcher *N) {
1013     return N->getKind() == EmitNodeXForm;
1014   }
1015
1016 private:
1017   void printImpl(raw_ostream &OS, unsigned indent) const override;
1018   bool isEqualImpl(const Matcher *M) const override {
1019     return cast<EmitNodeXFormMatcher>(M)->Slot == Slot &&
1020            cast<EmitNodeXFormMatcher>(M)->NodeXForm == NodeXForm;
1021   }
1022 };
1023
1024 /// EmitNodeMatcherCommon - Common class shared between EmitNode and
1025 /// MorphNodeTo.
1026 class EmitNodeMatcherCommon : public Matcher {
1027   const CodeGenInstruction &CGI;
1028   const SmallVector<MVT::SimpleValueType, 3> VTs;
1029   const SmallVector<unsigned, 6> Operands;
1030   bool HasChain, HasInGlue, HasOutGlue, HasMemRefs;
1031
1032   /// NumFixedArityOperands - If this is a fixed arity node, this is set to -1.
1033   /// If this is a varidic node, this is set to the number of fixed arity
1034   /// operands in the root of the pattern.  The rest are appended to this node.
1035   int NumFixedArityOperands;
1036 public:
1037   EmitNodeMatcherCommon(const CodeGenInstruction &cgi,
1038                         ArrayRef<MVT::SimpleValueType> vts,
1039                         ArrayRef<unsigned> operands, bool hasChain,
1040                         bool hasInGlue, bool hasOutGlue, bool hasmemrefs,
1041                         int numfixedarityoperands, bool isMorphNodeTo)
1042       : Matcher(isMorphNodeTo ? MorphNodeTo : EmitNode), CGI(cgi),
1043         VTs(vts.begin(), vts.end()), Operands(operands.begin(), operands.end()),
1044         HasChain(hasChain), HasInGlue(hasInGlue), HasOutGlue(hasOutGlue),
1045         HasMemRefs(hasmemrefs), NumFixedArityOperands(numfixedarityoperands) {}
1046
1047   const CodeGenInstruction &getInstruction() const { return CGI; }
1048
1049   unsigned getNumVTs() const { return VTs.size(); }
1050   MVT::SimpleValueType getVT(unsigned i) const {
1051     assert(i < VTs.size());
1052     return VTs[i];
1053   }
1054
1055   unsigned getNumOperands() const { return Operands.size(); }
1056   unsigned getOperand(unsigned i) const {
1057     assert(i < Operands.size());
1058     return Operands[i];
1059   }
1060
1061   const SmallVectorImpl<MVT::SimpleValueType> &getVTList() const { return VTs; }
1062   const SmallVectorImpl<unsigned> &getOperandList() const { return Operands; }
1063
1064
1065   bool hasChain() const { return HasChain; }
1066   bool hasInGlue() const { return HasInGlue; }
1067   bool hasOutGlue() const { return HasOutGlue; }
1068   bool hasMemRefs() const { return HasMemRefs; }
1069   int getNumFixedArityOperands() const { return NumFixedArityOperands; }
1070
1071   static bool classof(const Matcher *N) {
1072     return N->getKind() == EmitNode || N->getKind() == MorphNodeTo;
1073   }
1074
1075 private:
1076   void printImpl(raw_ostream &OS, unsigned indent) const override;
1077   bool isEqualImpl(const Matcher *M) const override;
1078 };
1079
1080 /// EmitNodeMatcher - This signals a successful match and generates a node.
1081 class EmitNodeMatcher : public EmitNodeMatcherCommon {
1082   void anchor() override;
1083   unsigned FirstResultSlot;
1084 public:
1085   EmitNodeMatcher(const CodeGenInstruction &cgi,
1086                   ArrayRef<MVT::SimpleValueType> vts,
1087                   ArrayRef<unsigned> operands, bool hasChain, bool hasInGlue,
1088                   bool hasOutGlue, bool hasmemrefs, int numfixedarityoperands,
1089                   unsigned firstresultslot)
1090       : EmitNodeMatcherCommon(cgi, vts, operands, hasChain, hasInGlue,
1091                               hasOutGlue, hasmemrefs, numfixedarityoperands,
1092                               false),
1093         FirstResultSlot(firstresultslot) {}
1094
1095   unsigned getFirstResultSlot() const { return FirstResultSlot; }
1096
1097   static bool classof(const Matcher *N) {
1098     return N->getKind() == EmitNode;
1099   }
1100
1101 };
1102
1103 class MorphNodeToMatcher : public EmitNodeMatcherCommon {
1104   void anchor() override;
1105   const PatternToMatch &Pattern;
1106 public:
1107   MorphNodeToMatcher(const CodeGenInstruction &cgi,
1108                      ArrayRef<MVT::SimpleValueType> vts,
1109                      ArrayRef<unsigned> operands, bool hasChain, bool hasInGlue,
1110                      bool hasOutGlue, bool hasmemrefs,
1111                      int numfixedarityoperands, const PatternToMatch &pattern)
1112       : EmitNodeMatcherCommon(cgi, vts, operands, hasChain, hasInGlue,
1113                               hasOutGlue, hasmemrefs, numfixedarityoperands,
1114                               true),
1115         Pattern(pattern) {}
1116
1117   const PatternToMatch &getPattern() const { return Pattern; }
1118
1119   static bool classof(const Matcher *N) {
1120     return N->getKind() == MorphNodeTo;
1121   }
1122 };
1123
1124 /// CompleteMatchMatcher - Complete a match by replacing the results of the
1125 /// pattern with the newly generated nodes.  This also prints a comment
1126 /// indicating the source and dest patterns.
1127 class CompleteMatchMatcher : public Matcher {
1128   SmallVector<unsigned, 2> Results;
1129   const PatternToMatch &Pattern;
1130 public:
1131   CompleteMatchMatcher(ArrayRef<unsigned> results,
1132                        const PatternToMatch &pattern)
1133   : Matcher(CompleteMatch), Results(results.begin(), results.end()),
1134     Pattern(pattern) {}
1135
1136   unsigned getNumResults() const { return Results.size(); }
1137   unsigned getResult(unsigned R) const { return Results[R]; }
1138   const PatternToMatch &getPattern() const { return Pattern; }
1139
1140   static bool classof(const Matcher *N) {
1141     return N->getKind() == CompleteMatch;
1142   }
1143
1144 private:
1145   void printImpl(raw_ostream &OS, unsigned indent) const override;
1146   bool isEqualImpl(const Matcher *M) const override {
1147     return cast<CompleteMatchMatcher>(M)->Results == Results &&
1148           &cast<CompleteMatchMatcher>(M)->Pattern == &Pattern;
1149   }
1150 };
1151
1152 } // end namespace llvm
1153
1154 #endif