contrib/llvm/utils/TableGen/GlobalISelEmitter.cpp

   1 //===- GlobalISelEmitter.cpp - Generate an instruction selector -----------===//
   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 /// \file
  11 /// This tablegen backend emits code for use by the GlobalISel instruction
  12 /// selector. See include/llvm/CodeGen/TargetGlobalISel.td.
  13 ///
  14 /// This file analyzes the patterns recognized by the SelectionDAGISel tablegen
  15 /// backend, filters out the ones that are unsupported, maps
  16 /// SelectionDAG-specific constructs to their GlobalISel counterpart
  17 /// (when applicable: MVT to LLT;  SDNode to generic Instruction).
  18 ///
  19 /// Not all patterns are supported: pass the tablegen invocation
  20 /// "-warn-on-skipped-patterns" to emit a warning when a pattern is skipped,
  21 /// as well as why.
  22 ///
  23 /// The generated file defines a single method:
  24 ///     bool <Target>InstructionSelector::selectImpl(MachineInstr &I) const;
  25 /// intended to be used in InstructionSelector::select as the first-step
  26 /// selector for the patterns that don't require complex C++.
  27 ///
  28 /// FIXME: We'll probably want to eventually define a base
  29 /// "TargetGenInstructionSelector" class.
  30 ///
  31 //===----------------------------------------------------------------------===//
  32
  33 #include "CodeGenDAGPatterns.h"
  34 #include "SubtargetFeatureInfo.h"
  35 #include "llvm/ADT/Optional.h"
  36 #include "llvm/ADT/SmallSet.h"
  37 #include "llvm/ADT/Statistic.h"
  38 #include "llvm/CodeGen/MachineValueType.h"
  39 #include "llvm/Support/CommandLine.h"
  40 #include "llvm/Support/Error.h"
  41 #include "llvm/Support/LowLevelTypeImpl.h"
  42 #include "llvm/Support/ScopedPrinter.h"
  43 #include "llvm/TableGen/Error.h"
  44 #include "llvm/TableGen/Record.h"
  45 #include "llvm/TableGen/TableGenBackend.h"
  46 #include <string>
  47 #include <numeric>
  48 using namespace llvm;
  49
  50 #define DEBUG_TYPE "gisel-emitter"
  51
  52 STATISTIC(NumPatternTotal, "Total number of patterns");
  53 STATISTIC(NumPatternImported, "Number of patterns imported from SelectionDAG");
  54 STATISTIC(NumPatternImportsSkipped, "Number of SelectionDAG imports skipped");
  55 STATISTIC(NumPatternEmitted, "Number of patterns emitted");
  56 /// A unique identifier for a MatchTable.
  57 static unsigned CurrentMatchTableID = 0;
  58
  59 cl::OptionCategory GlobalISelEmitterCat("Options for -gen-global-isel");
  60
  61 static cl::opt<bool> WarnOnSkippedPatterns(
  62     "warn-on-skipped-patterns",
  63     cl::desc("Explain why a pattern was skipped for inclusion "
  64              "in the GlobalISel selector"),
  65     cl::init(false), cl::cat(GlobalISelEmitterCat));
  66
  67 namespace {
  68 //===- Helper functions ---------------------------------------------------===//
  69
  70 /// This class stands in for LLT wherever we want to tablegen-erate an
  71 /// equivalent at compiler run-time.
  72 class LLTCodeGen {
  73 private:
  74   LLT Ty;
  75
  76 public:
  77   LLTCodeGen(const LLT &Ty) : Ty(Ty) {}
  78
  79   void emitCxxEnumValue(raw_ostream &OS) const {
  80     if (Ty.isScalar()) {
  81       OS << "GILLT_s" << Ty.getSizeInBits();
  82       return;
  83     }
  84     if (Ty.isVector()) {
  85       OS << "GILLT_v" << Ty.getNumElements() << "s" << Ty.getScalarSizeInBits();
  86       return;
  87     }
  88     llvm_unreachable("Unhandled LLT");
  89   }
  90
  91   void emitCxxConstructorCall(raw_ostream &OS) const {
  92     if (Ty.isScalar()) {
  93       OS << "LLT::scalar(" << Ty.getSizeInBits() << ")";
  94       return;
  95     }
  96     if (Ty.isVector()) {
  97       OS << "LLT::vector(" << Ty.getNumElements() << ", "
  98          << Ty.getScalarSizeInBits() << ")";
  99       return;
 100     }
 101     llvm_unreachable("Unhandled LLT");
 102   }
 103
 104   const LLT &get() const { return Ty; }
 105
 106   /// This ordering is used for std::unique() and std::sort(). There's no
 107   /// particular logic behind the order.
 108   bool operator<(const LLTCodeGen &Other) const {
 109     if (!Ty.isValid())
 110       return Other.Ty.isValid();
 111     if (Ty.isScalar()) {
 112       if (!Other.Ty.isValid())
 113         return false;
 114       if (Other.Ty.isScalar())
 115         return Ty.getSizeInBits() < Other.Ty.getSizeInBits();
 116       return false;
 117     }
 118     if (Ty.isVector()) {
 119       if (!Other.Ty.isValid() || Other.Ty.isScalar())
 120         return false;
 121       if (Other.Ty.isVector()) {
 122         if (Ty.getNumElements() < Other.Ty.getNumElements())
 123           return true;
 124         if (Ty.getNumElements() > Other.Ty.getNumElements())
 125           return false;
 126         return Ty.getSizeInBits() < Other.Ty.getSizeInBits();
 127       }
 128       return false;
 129     }
 130     llvm_unreachable("Unhandled LLT");
 131   }
 132 };
 133
 134 class InstructionMatcher;
 135 /// Convert an MVT to an equivalent LLT if possible, or the invalid LLT() for
 136 /// MVTs that don't map cleanly to an LLT (e.g., iPTR, *any, ...).
 137 static Optional<LLTCodeGen> MVTToLLT(MVT::SimpleValueType SVT) {
 138   MVT VT(SVT);
 139   if (VT.isVector() && VT.getVectorNumElements() != 1)
 140     return LLTCodeGen(
 141         LLT::vector(VT.getVectorNumElements(), VT.getScalarSizeInBits()));
 142   if (VT.isInteger() || VT.isFloatingPoint())
 143     return LLTCodeGen(LLT::scalar(VT.getSizeInBits()));
 144   return None;
 145 }
 146
 147 static std::string explainPredicates(const TreePatternNode *N) {
 148   std::string Explanation = "";
 149   StringRef Separator = "";
 150   for (const auto &P : N->getPredicateFns()) {
 151     Explanation +=
 152         (Separator + P.getOrigPatFragRecord()->getRecord()->getName()).str();
 153     if (P.isAlwaysTrue())
 154       Explanation += " always-true";
 155     if (P.isImmediatePattern())
 156       Explanation += " immediate";
 157   }
 158   return Explanation;
 159 }
 160
 161 std::string explainOperator(Record *Operator) {
 162   if (Operator->isSubClassOf("SDNode"))
 163     return (" (" + Operator->getValueAsString("Opcode") + ")").str();
 164
 165   if (Operator->isSubClassOf("Intrinsic"))
 166     return (" (Operator is an Intrinsic, " + Operator->getName() + ")").str();
 167
 168   return " (Operator not understood)";
 169 }
 170
 171 /// Helper function to let the emitter report skip reason error messages.
 172 static Error failedImport(const Twine &Reason) {
 173   return make_error<StringError>(Reason, inconvertibleErrorCode());
 174 }
 175
 176 static Error isTrivialOperatorNode(const TreePatternNode *N) {
 177   std::string Explanation = "";
 178   std::string Separator = "";
 179   if (N->isLeaf()) {
 180     if (isa<IntInit>(N->getLeafValue()))
 181       return Error::success();
 182
 183     Explanation = "Is a leaf";
 184     Separator = ", ";
 185   }
 186
 187   if (N->hasAnyPredicate()) {
 188     Explanation = Separator + "Has a predicate (" + explainPredicates(N) + ")";
 189     Separator = ", ";
 190   }
 191
 192   if (N->getTransformFn()) {
 193     Explanation += Separator + "Has a transform function";
 194     Separator = ", ";
 195   }
 196
 197   if (!N->isLeaf() && !N->hasAnyPredicate() && !N->getTransformFn())
 198     return Error::success();
 199
 200   return failedImport(Explanation);
 201 }
 202
 203 static Record *getInitValueAsRegClass(Init *V) {
 204   if (DefInit *VDefInit = dyn_cast<DefInit>(V)) {
 205     if (VDefInit->getDef()->isSubClassOf("RegisterOperand"))
 206       return VDefInit->getDef()->getValueAsDef("RegClass");
 207     if (VDefInit->getDef()->isSubClassOf("RegisterClass"))
 208       return VDefInit->getDef();
 209   }
 210   return nullptr;
 211 }
 212
 213 std::string
 214 getNameForFeatureBitset(const std::vector<Record *> &FeatureBitset) {
 215   std::string Name = "GIFBS";
 216   for (const auto &Feature : FeatureBitset)
 217     Name += ("_" + Feature->getName()).str();
 218   return Name;
 219 }
 220 //===- Matchers -----------------------------------------------------------===//
 221
 222 class OperandMatcher;
 223 class MatchAction;
 224
 225 /// Generates code to check that a match rule matches.
 226 class RuleMatcher {
 227   /// A list of matchers that all need to succeed for the current rule to match.
 228   /// FIXME: This currently supports a single match position but could be
 229   /// extended to support multiple positions to support div/rem fusion or
 230   /// load-multiple instructions.
 231   std::vector<std::unique_ptr<InstructionMatcher>> Matchers;
 232
 233   /// A list of actions that need to be taken when all predicates in this rule
 234   /// have succeeded.
 235   std::vector<std::unique_ptr<MatchAction>> Actions;
 236
 237   /// A map of instruction matchers to the local variables created by
 238   /// emitCaptureOpcodes().
 239   std::map<const InstructionMatcher *, unsigned> InsnVariableIDs;
 240
 241   /// ID for the next instruction variable defined with defineInsnVar()
 242   unsigned NextInsnVarID;
 243
 244   std::vector<Record *> RequiredFeatures;
 245
 246 public:
 247   RuleMatcher()
 248       : Matchers(), Actions(), InsnVariableIDs(), NextInsnVarID(0) {}
 249   RuleMatcher(RuleMatcher &&Other) = default;
 250   RuleMatcher &operator=(RuleMatcher &&Other) = default;
 251
 252   InstructionMatcher &addInstructionMatcher();
 253   void addRequiredFeature(Record *Feature);
 254   const std::vector<Record *> &getRequiredFeatures() const;
 255
 256   template <class Kind, class... Args> Kind &addAction(Args &&... args);
 257
 258   /// Define an instruction without emitting any code to do so.
 259   /// This is used for the root of the match.
 260   unsigned implicitlyDefineInsnVar(const InstructionMatcher &Matcher);
 261   /// Define an instruction and emit corresponding state-machine opcodes.
 262   unsigned defineInsnVar(raw_ostream &OS, const InstructionMatcher &Matcher,
 263                          unsigned InsnVarID, unsigned OpIdx);
 264   unsigned getInsnVarID(const InstructionMatcher &InsnMatcher) const;
 265
 266   void emitCaptureOpcodes(raw_ostream &OS);
 267
 268   void emit(raw_ostream &OS);
 269
 270   /// Compare the priority of this object and B.
 271   ///
 272   /// Returns true if this object is more important than B.
 273   bool isHigherPriorityThan(const RuleMatcher &B) const;
 274
 275   /// Report the maximum number of temporary operands needed by the rule
 276   /// matcher.
 277   unsigned countRendererFns() const;
 278
 279   // FIXME: Remove this as soon as possible
 280   InstructionMatcher &insnmatcher_front() const { return *Matchers.front(); }
 281 };
 282
 283 template <class PredicateTy> class PredicateListMatcher {
 284 private:
 285   typedef std::vector<std::unique_ptr<PredicateTy>> PredicateVec;
 286   PredicateVec Predicates;
 287
 288 public:
 289   /// Construct a new operand predicate and add it to the matcher.
 290   template <class Kind, class... Args>
 291   Kind &addPredicate(Args&&... args) {
 292     Predicates.emplace_back(
 293         llvm::make_unique<Kind>(std::forward<Args>(args)...));
 294     return *static_cast<Kind *>(Predicates.back().get());
 295   }
 296
 297   typename PredicateVec::const_iterator predicates_begin() const {
 298     return Predicates.begin();
 299   }
 300   typename PredicateVec::const_iterator predicates_end() const {
 301     return Predicates.end();
 302   }
 303   iterator_range<typename PredicateVec::const_iterator> predicates() const {
 304     return make_range(predicates_begin(), predicates_end());
 305   }
 306   typename PredicateVec::size_type predicates_size() const {
 307     return Predicates.size();
 308   }
 309
 310   /// Emit MatchTable opcodes that tests whether all the predicates are met.
 311   template <class... Args>
 312   void emitPredicateListOpcodes(raw_ostream &OS, Args &&... args) const {
 313     if (Predicates.empty()) {
 314       OS << "// No predicates\n";
 315       return;
 316     }
 317
 318     for (const auto &Predicate : predicates())
 319       Predicate->emitPredicateOpcodes(OS, std::forward<Args>(args)...);
 320   }
 321 };
 322
 323 /// Generates code to check a predicate of an operand.
 324 ///
 325 /// Typical predicates include:
 326 /// * Operand is a particular register.
 327 /// * Operand is assigned a particular register bank.
 328 /// * Operand is an MBB.
 329 class OperandPredicateMatcher {
 330 public:
 331   /// This enum is used for RTTI and also defines the priority that is given to
 332   /// the predicate when generating the matcher code. Kinds with higher priority
 333   /// must be tested first.
 334   ///
 335   /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter
 336   /// but OPM_Int must have priority over OPM_RegBank since constant integers
 337   /// are represented by a virtual register defined by a G_CONSTANT instruction.
 338   enum PredicateKind {
 339     OPM_ComplexPattern,
 340     OPM_Instruction,
 341     OPM_IntrinsicID,
 342     OPM_Int,
 343     OPM_LiteralInt,
 344     OPM_LLT,
 345     OPM_RegBank,
 346     OPM_MBB,
 347   };
 348
 349 protected:
 350   PredicateKind Kind;
 351
 352 public:
 353   OperandPredicateMatcher(PredicateKind Kind) : Kind(Kind) {}
 354   virtual ~OperandPredicateMatcher() {}
 355
 356   PredicateKind getKind() const { return Kind; }
 357
 358   /// Return the OperandMatcher for the specified operand or nullptr if there
 359   /// isn't one by that name in this operand predicate matcher.
 360   ///
 361   /// InstructionOperandMatcher is the only subclass that can return non-null
 362   /// for this.
 363   virtual Optional<const OperandMatcher *>
 364   getOptionalOperand(StringRef SymbolicName) const {
 365     assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
 366     return None;
 367   }
 368
 369   /// Emit MatchTable opcodes to capture instructions into the MIs table.
 370   ///
 371   /// Only InstructionOperandMatcher needs to do anything for this method the
 372   /// rest just walk the tree.
 373   virtual void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule,
 374                                   unsigned InsnVarID, unsigned OpIdx) const {}
 375
 376   /// Emit MatchTable opcodes that check the predicate for the given operand.
 377   virtual void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
 378                                     unsigned InsnVarID,
 379                                     unsigned OpIdx) const = 0;
 380
 381   /// Compare the priority of this object and B.
 382   ///
 383   /// Returns true if this object is more important than B.
 384   virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const {
 385     return Kind < B.Kind;
 386   };
 387
 388   /// Report the maximum number of temporary operands needed by the predicate
 389   /// matcher.
 390   virtual unsigned countRendererFns() const { return 0; }
 391 };
 392
 393 /// Generates code to check that an operand is a particular LLT.
 394 class LLTOperandMatcher : public OperandPredicateMatcher {
 395 protected:
 396   LLTCodeGen Ty;
 397
 398 public:
 399   LLTOperandMatcher(const LLTCodeGen &Ty)
 400       : OperandPredicateMatcher(OPM_LLT), Ty(Ty) {}
 401
 402   static bool classof(const OperandPredicateMatcher *P) {
 403     return P->getKind() == OPM_LLT;
 404   }
 405
 406   void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
 407                             unsigned InsnVarID, unsigned OpIdx) const override {
 408     OS << "    GIM_CheckType, /*MI*/" << InsnVarID << ", /*Op*/" << OpIdx
 409        << ", /*Type*/";
 410     Ty.emitCxxEnumValue(OS);
 411     OS << ", \n";
 412   }
 413 };
 414
 415 /// Generates code to check that an operand is a particular target constant.
 416 class ComplexPatternOperandMatcher : public OperandPredicateMatcher {
 417 protected:
 418   const OperandMatcher &Operand;
 419   const Record &TheDef;
 420
 421   unsigned getAllocatedTemporariesBaseID() const;
 422
 423 public:
 424   ComplexPatternOperandMatcher(const OperandMatcher &Operand,
 425                                const Record &TheDef)
 426       : OperandPredicateMatcher(OPM_ComplexPattern), Operand(Operand),
 427         TheDef(TheDef) {}
 428
 429   static bool classof(const OperandPredicateMatcher *P) {
 430     return P->getKind() == OPM_ComplexPattern;
 431   }
 432
 433   void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
 434                             unsigned InsnVarID, unsigned OpIdx) const override {
 435     unsigned ID = getAllocatedTemporariesBaseID();
 436     OS << "    GIM_CheckComplexPattern, /*MI*/" << InsnVarID << ", /*Op*/"
 437        << OpIdx << ", /*Renderer*/" << ID << ", GICP_"
 438        << TheDef.getName() << ",\n";
 439   }
 440
 441   unsigned countRendererFns() const override {
 442     return 1;
 443   }
 444 };
 445
 446 /// Generates code to check that an operand is in a particular register bank.
 447 class RegisterBankOperandMatcher : public OperandPredicateMatcher {
 448 protected:
 449   const CodeGenRegisterClass &RC;
 450
 451 public:
 452   RegisterBankOperandMatcher(const CodeGenRegisterClass &RC)
 453       : OperandPredicateMatcher(OPM_RegBank), RC(RC) {}
 454
 455   static bool classof(const OperandPredicateMatcher *P) {
 456     return P->getKind() == OPM_RegBank;
 457   }
 458
 459   void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
 460                             unsigned InsnVarID, unsigned OpIdx) const override {
 461     OS << "    GIM_CheckRegBankForClass, /*MI*/" << InsnVarID << ", /*Op*/"
 462        << OpIdx << ", /*RC*/" << RC.getQualifiedName() << "RegClassID,\n";
 463   }
 464 };
 465
 466 /// Generates code to check that an operand is a basic block.
 467 class MBBOperandMatcher : public OperandPredicateMatcher {
 468 public:
 469   MBBOperandMatcher() : OperandPredicateMatcher(OPM_MBB) {}
 470
 471   static bool classof(const OperandPredicateMatcher *P) {
 472     return P->getKind() == OPM_MBB;
 473   }
 474
 475   void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
 476                             unsigned InsnVarID, unsigned OpIdx) const override {
 477     OS << "    GIM_CheckIsMBB, /*MI*/" << InsnVarID << ", /*Op*/" << OpIdx << ",\n";
 478   }
 479 };
 480
 481 /// Generates code to check that an operand is a G_CONSTANT with a particular
 482 /// int.
 483 class ConstantIntOperandMatcher : public OperandPredicateMatcher {
 484 protected:
 485   int64_t Value;
 486
 487 public:
 488   ConstantIntOperandMatcher(int64_t Value)
 489       : OperandPredicateMatcher(OPM_Int), Value(Value) {}
 490
 491   static bool classof(const OperandPredicateMatcher *P) {
 492     return P->getKind() == OPM_Int;
 493   }
 494
 495   void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
 496                             unsigned InsnVarID, unsigned OpIdx) const override {
 497     OS << "    GIM_CheckConstantInt, /*MI*/" << InsnVarID << ", /*Op*/"
 498        << OpIdx << ", " << Value << ",\n";
 499   }
 500 };
 501
 502 /// Generates code to check that an operand is a raw int (where MO.isImm() or
 503 /// MO.isCImm() is true).
 504 class LiteralIntOperandMatcher : public OperandPredicateMatcher {
 505 protected:
 506   int64_t Value;
 507
 508 public:
 509   LiteralIntOperandMatcher(int64_t Value)
 510       : OperandPredicateMatcher(OPM_LiteralInt), Value(Value) {}
 511
 512   static bool classof(const OperandPredicateMatcher *P) {
 513     return P->getKind() == OPM_LiteralInt;
 514   }
 515
 516   void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
 517                             unsigned InsnVarID, unsigned OpIdx) const override {
 518     OS << "    GIM_CheckLiteralInt, /*MI*/" << InsnVarID << ", /*Op*/"
 519        << OpIdx << ", " << Value << ",\n";
 520   }
 521 };
 522
 523 /// Generates code to check that an operand is an intrinsic ID.
 524 class IntrinsicIDOperandMatcher : public OperandPredicateMatcher {
 525 protected:
 526   const CodeGenIntrinsic *II;
 527
 528 public:
 529   IntrinsicIDOperandMatcher(const CodeGenIntrinsic *II)
 530       : OperandPredicateMatcher(OPM_IntrinsicID), II(II) {}
 531
 532   static bool classof(const OperandPredicateMatcher *P) {
 533     return P->getKind() == OPM_IntrinsicID;
 534   }
 535
 536   void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
 537                             unsigned InsnVarID, unsigned OpIdx) const override {
 538     OS << "    GIM_CheckIntrinsicID, /*MI*/" << InsnVarID << ", /*Op*/"
 539        << OpIdx << ", Intrinsic::" << II->EnumName << ",\n";
 540   }
 541 };
 542
 543 /// Generates code to check that a set of predicates match for a particular
 544 /// operand.
 545 class OperandMatcher : public PredicateListMatcher<OperandPredicateMatcher> {
 546 protected:
 547   InstructionMatcher &Insn;
 548   unsigned OpIdx;
 549   std::string SymbolicName;
 550
 551   /// The index of the first temporary variable allocated to this operand. The
 552   /// number of allocated temporaries can be found with
 553   /// countRendererFns().
 554   unsigned AllocatedTemporariesBaseID;
 555
 556 public:
 557   OperandMatcher(InstructionMatcher &Insn, unsigned OpIdx,
 558                  const std::string &SymbolicName,
 559                  unsigned AllocatedTemporariesBaseID)
 560       : Insn(Insn), OpIdx(OpIdx), SymbolicName(SymbolicName),
 561         AllocatedTemporariesBaseID(AllocatedTemporariesBaseID) {}
 562
 563   bool hasSymbolicName() const { return !SymbolicName.empty(); }
 564   const StringRef getSymbolicName() const { return SymbolicName; }
 565   void setSymbolicName(StringRef Name) {
 566     assert(SymbolicName.empty() && "Operand already has a symbolic name");
 567     SymbolicName = Name;
 568   }
 569   unsigned getOperandIndex() const { return OpIdx; }
 570
 571   std::string getOperandExpr(unsigned InsnVarID) const {
 572     return "State.MIs[" + llvm::to_string(InsnVarID) + "]->getOperand(" +
 573            llvm::to_string(OpIdx) + ")";
 574   }
 575
 576   Optional<const OperandMatcher *>
 577   getOptionalOperand(StringRef DesiredSymbolicName) const {
 578     assert(!DesiredSymbolicName.empty() && "Cannot lookup unnamed operand");
 579     if (DesiredSymbolicName == SymbolicName)
 580       return this;
 581     for (const auto &OP : predicates()) {
 582       const auto &MaybeOperand = OP->getOptionalOperand(DesiredSymbolicName);
 583       if (MaybeOperand.hasValue())
 584         return MaybeOperand.getValue();
 585     }
 586     return None;
 587   }
 588
 589   InstructionMatcher &getInstructionMatcher() const { return Insn; }
 590
 591   /// Emit MatchTable opcodes to capture instructions into the MIs table.
 592   void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule,
 593                           unsigned InsnVarID) const {
 594     for (const auto &Predicate : predicates())
 595       Predicate->emitCaptureOpcodes(OS, Rule, InsnVarID, OpIdx);
 596   }
 597
 598   /// Emit MatchTable opcodes that test whether the instruction named in
 599   /// InsnVarID matches all the predicates and all the operands.
 600   void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
 601                             unsigned InsnVarID) const {
 602     OS << "    // MIs[" << InsnVarID << "] ";
 603     if (SymbolicName.empty())
 604       OS << "Operand " << OpIdx;
 605     else
 606       OS << SymbolicName;
 607     OS << "\n";
 608     emitPredicateListOpcodes(OS, Rule, InsnVarID, OpIdx);
 609   }
 610
 611   /// Compare the priority of this object and B.
 612   ///
 613   /// Returns true if this object is more important than B.
 614   bool isHigherPriorityThan(const OperandMatcher &B) const {
 615     // Operand matchers involving more predicates have higher priority.
 616     if (predicates_size() > B.predicates_size())
 617       return true;
 618     if (predicates_size() < B.predicates_size())
 619       return false;
 620
 621     // This assumes that predicates are added in a consistent order.
 622     for (const auto &Predicate : zip(predicates(), B.predicates())) {
 623       if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate)))
 624         return true;
 625       if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate)))
 626         return false;
 627     }
 628
 629     return false;
 630   };
 631
 632   /// Report the maximum number of temporary operands needed by the operand
 633   /// matcher.
 634   unsigned countRendererFns() const {
 635     return std::accumulate(
 636         predicates().begin(), predicates().end(), 0,
 637         [](unsigned A,
 638            const std::unique_ptr<OperandPredicateMatcher> &Predicate) {
 639           return A + Predicate->countRendererFns();
 640         });
 641   }
 642
 643   unsigned getAllocatedTemporariesBaseID() const {
 644     return AllocatedTemporariesBaseID;
 645   }
 646 };
 647
 648 unsigned ComplexPatternOperandMatcher::getAllocatedTemporariesBaseID() const {
 649   return Operand.getAllocatedTemporariesBaseID();
 650 }
 651
 652 /// Generates code to check a predicate on an instruction.
 653 ///
 654 /// Typical predicates include:
 655 /// * The opcode of the instruction is a particular value.
 656 /// * The nsw/nuw flag is/isn't set.
 657 class InstructionPredicateMatcher {
 658 protected:
 659   /// This enum is used for RTTI and also defines the priority that is given to
 660   /// the predicate when generating the matcher code. Kinds with higher priority
 661   /// must be tested first.
 662   enum PredicateKind {
 663     IPM_Opcode,
 664   };
 665
 666   PredicateKind Kind;
 667
 668 public:
 669   InstructionPredicateMatcher(PredicateKind Kind) : Kind(Kind) {}
 670   virtual ~InstructionPredicateMatcher() {}
 671
 672   PredicateKind getKind() const { return Kind; }
 673
 674   /// Emit MatchTable opcodes that test whether the instruction named in
 675   /// InsnVarID matches the predicate.
 676   virtual void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
 677                                     unsigned InsnVarID) const = 0;
 678
 679   /// Compare the priority of this object and B.
 680   ///
 681   /// Returns true if this object is more important than B.
 682   virtual bool
 683   isHigherPriorityThan(const InstructionPredicateMatcher &B) const {
 684     return Kind < B.Kind;
 685   };
 686
 687   /// Report the maximum number of temporary operands needed by the predicate
 688   /// matcher.
 689   virtual unsigned countRendererFns() const { return 0; }
 690 };
 691
 692 /// Generates code to check the opcode of an instruction.
 693 class InstructionOpcodeMatcher : public InstructionPredicateMatcher {
 694 protected:
 695   const CodeGenInstruction *I;
 696
 697 public:
 698   InstructionOpcodeMatcher(const CodeGenInstruction *I)
 699       : InstructionPredicateMatcher(IPM_Opcode), I(I) {}
 700
 701   static bool classof(const InstructionPredicateMatcher *P) {
 702     return P->getKind() == IPM_Opcode;
 703   }
 704
 705   void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
 706                             unsigned InsnVarID) const override {
 707     OS << "    GIM_CheckOpcode, /*MI*/" << InsnVarID << ", " << I->Namespace
 708        << "::" << I->TheDef->getName() << ",\n";
 709   }
 710
 711   /// Compare the priority of this object and B.
 712   ///
 713   /// Returns true if this object is more important than B.
 714   bool
 715   isHigherPriorityThan(const InstructionPredicateMatcher &B) const override {
 716     if (InstructionPredicateMatcher::isHigherPriorityThan(B))
 717       return true;
 718     if (B.InstructionPredicateMatcher::isHigherPriorityThan(*this))
 719       return false;
 720
 721     // Prioritize opcodes for cosmetic reasons in the generated source. Although
 722     // this is cosmetic at the moment, we may want to drive a similar ordering
 723     // using instruction frequency information to improve compile time.
 724     if (const InstructionOpcodeMatcher *BO =
 725             dyn_cast<InstructionOpcodeMatcher>(&B))
 726       return I->TheDef->getName() < BO->I->TheDef->getName();
 727
 728     return false;
 729   };
 730 };
 731
 732 /// Generates code to check that a set of predicates and operands match for a
 733 /// particular instruction.
 734 ///
 735 /// Typical predicates include:
 736 /// * Has a specific opcode.
 737 /// * Has an nsw/nuw flag or doesn't.
 738 class InstructionMatcher
 739     : public PredicateListMatcher<InstructionPredicateMatcher> {
 740 protected:
 741   typedef std::vector<std::unique_ptr<OperandMatcher>> OperandVec;
 742
 743   /// The operands to match. All rendered operands must be present even if the
 744   /// condition is always true.
 745   OperandVec Operands;
 746
 747 public:
 748   /// Add an operand to the matcher.
 749   OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName,
 750                              unsigned AllocatedTemporariesBaseID) {
 751     Operands.emplace_back(new OperandMatcher(*this, OpIdx, SymbolicName,
 752                                              AllocatedTemporariesBaseID));
 753     return *Operands.back();
 754   }
 755
 756   OperandMatcher &getOperand(unsigned OpIdx) {
 757     auto I = std::find_if(Operands.begin(), Operands.end(),
 758                           [&OpIdx](const std::unique_ptr<OperandMatcher> &X) {
 759                             return X->getOperandIndex() == OpIdx;
 760                           });
 761     if (I != Operands.end())
 762       return **I;
 763     llvm_unreachable("Failed to lookup operand");
 764   }
 765
 766   Optional<const OperandMatcher *>
 767   getOptionalOperand(StringRef SymbolicName) const {
 768     assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
 769     for (const auto &Operand : Operands) {
 770       const auto &OM = Operand->getOptionalOperand(SymbolicName);
 771       if (OM.hasValue())
 772         return OM.getValue();
 773     }
 774     return None;
 775   }
 776
 777   const OperandMatcher &getOperand(StringRef SymbolicName) const {
 778     Optional<const OperandMatcher *>OM = getOptionalOperand(SymbolicName);
 779     if (OM.hasValue())
 780       return *OM.getValue();
 781     llvm_unreachable("Failed to lookup operand");
 782   }
 783
 784   unsigned getNumOperands() const { return Operands.size(); }
 785   OperandVec::iterator operands_begin() { return Operands.begin(); }
 786   OperandVec::iterator operands_end() { return Operands.end(); }
 787   iterator_range<OperandVec::iterator> operands() {
 788     return make_range(operands_begin(), operands_end());
 789   }
 790   OperandVec::const_iterator operands_begin() const { return Operands.begin(); }
 791   OperandVec::const_iterator operands_end() const { return Operands.end(); }
 792   iterator_range<OperandVec::const_iterator> operands() const {
 793     return make_range(operands_begin(), operands_end());
 794   }
 795
 796   /// Emit MatchTable opcodes to check the shape of the match and capture
 797   /// instructions into the MIs table.
 798   void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule,
 799                           unsigned InsnID) {
 800     OS << "    GIM_CheckNumOperands, /*MI*/" << InsnID << ", /*Expected*/"
 801        << getNumOperands() << ",\n";
 802     for (const auto &Operand : Operands)
 803       Operand->emitCaptureOpcodes(OS, Rule, InsnID);
 804   }
 805
 806   /// Emit MatchTable opcodes that test whether the instruction named in
 807   /// InsnVarName matches all the predicates and all the operands.
 808   void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
 809                             unsigned InsnVarID) const {
 810     emitPredicateListOpcodes(OS, Rule, InsnVarID);
 811     for (const auto &Operand : Operands)
 812       Operand->emitPredicateOpcodes(OS, Rule, InsnVarID);
 813   }
 814
 815   /// Compare the priority of this object and B.
 816   ///
 817   /// Returns true if this object is more important than B.
 818   bool isHigherPriorityThan(const InstructionMatcher &B) const {
 819     // Instruction matchers involving more operands have higher priority.
 820     if (Operands.size() > B.Operands.size())
 821       return true;
 822     if (Operands.size() < B.Operands.size())
 823       return false;
 824
 825     for (const auto &Predicate : zip(predicates(), B.predicates())) {
 826       if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate)))
 827         return true;
 828       if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate)))
 829         return false;
 830     }
 831
 832     for (const auto &Operand : zip(Operands, B.Operands)) {
 833       if (std::get<0>(Operand)->isHigherPriorityThan(*std::get<1>(Operand)))
 834         return true;
 835       if (std::get<1>(Operand)->isHigherPriorityThan(*std::get<0>(Operand)))
 836         return false;
 837     }
 838
 839     return false;
 840   };
 841
 842   /// Report the maximum number of temporary operands needed by the instruction
 843   /// matcher.
 844   unsigned countRendererFns() const {
 845     return std::accumulate(predicates().begin(), predicates().end(), 0,
 846                            [](unsigned A,
 847                               const std::unique_ptr<InstructionPredicateMatcher>
 848                                   &Predicate) {
 849                              return A + Predicate->countRendererFns();
 850                            }) +
 851            std::accumulate(
 852                Operands.begin(), Operands.end(), 0,
 853                [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) {
 854                  return A + Operand->countRendererFns();
 855                });
 856   }
 857 };
 858
 859 /// Generates code to check that the operand is a register defined by an
 860 /// instruction that matches the given instruction matcher.
 861 ///
 862 /// For example, the pattern:
 863 ///   (set $dst, (G_MUL (G_ADD $src1, $src2), $src3))
 864 /// would use an InstructionOperandMatcher for operand 1 of the G_MUL to match
 865 /// the:
 866 ///   (G_ADD $src1, $src2)
 867 /// subpattern.
 868 class InstructionOperandMatcher : public OperandPredicateMatcher {
 869 protected:
 870   std::unique_ptr<InstructionMatcher> InsnMatcher;
 871
 872 public:
 873   InstructionOperandMatcher()
 874       : OperandPredicateMatcher(OPM_Instruction),
 875         InsnMatcher(new InstructionMatcher()) {}
 876
 877   static bool classof(const OperandPredicateMatcher *P) {
 878     return P->getKind() == OPM_Instruction;
 879   }
 880
 881   InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; }
 882
 883   Optional<const OperandMatcher *>
 884   getOptionalOperand(StringRef SymbolicName) const override {
 885     assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
 886     return InsnMatcher->getOptionalOperand(SymbolicName);
 887   }
 888
 889   void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule,
 890                           unsigned InsnID, unsigned OpIdx) const override {
 891     unsigned InsnVarID = Rule.defineInsnVar(OS, *InsnMatcher, InsnID, OpIdx);
 892     InsnMatcher->emitCaptureOpcodes(OS, Rule, InsnVarID);
 893   }
 894
 895   void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
 896                             unsigned InsnVarID_,
 897                             unsigned OpIdx_) const override {
 898     unsigned InsnVarID = Rule.getInsnVarID(*InsnMatcher);
 899     InsnMatcher->emitPredicateOpcodes(OS, Rule, InsnVarID);
 900   }
 901 };
 902
 903 //===- Actions ------------------------------------------------------------===//
 904 class OperandRenderer {
 905 public:
 906   enum RendererKind {
 907     OR_Copy,
 908     OR_CopySubReg,
 909     OR_Imm,
 910     OR_Register,
 911     OR_ComplexPattern
 912   };
 913
 914 protected:
 915   RendererKind Kind;
 916
 917 public:
 918   OperandRenderer(RendererKind Kind) : Kind(Kind) {}
 919   virtual ~OperandRenderer() {}
 920
 921   RendererKind getKind() const { return Kind; }
 922
 923   virtual void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const = 0;
 924 };
 925
 926 /// A CopyRenderer emits code to copy a single operand from an existing
 927 /// instruction to the one being built.
 928 class CopyRenderer : public OperandRenderer {
 929 protected:
 930   unsigned NewInsnID;
 931   /// The matcher for the instruction that this operand is copied from.
 932   /// This provides the facility for looking up an a operand by it's name so
 933   /// that it can be used as a source for the instruction being built.
 934   const InstructionMatcher &Matched;
 935   /// The name of the operand.
 936   const StringRef SymbolicName;
 937
 938 public:
 939   CopyRenderer(unsigned NewInsnID, const InstructionMatcher &Matched,
 940                StringRef SymbolicName)
 941       : OperandRenderer(OR_Copy), NewInsnID(NewInsnID), Matched(Matched),
 942         SymbolicName(SymbolicName) {}
 943
 944   static bool classof(const OperandRenderer *R) {
 945     return R->getKind() == OR_Copy;
 946   }
 947
 948   const StringRef getSymbolicName() const { return SymbolicName; }
 949
 950   void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
 951     const OperandMatcher &Operand = Matched.getOperand(SymbolicName);
 952     unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
 953     OS << "    GIR_Copy, /*NewInsnID*/" << NewInsnID << ", /*OldInsnID*/"
 954        << OldInsnVarID << ", /*OpIdx*/" << Operand.getOperandIndex() << ", // "
 955        << SymbolicName << "\n";
 956   }
 957 };
 958
 959 /// A CopySubRegRenderer emits code to copy a single register operand from an
 960 /// existing instruction to the one being built and indicate that only a
 961 /// subregister should be copied.
 962 class CopySubRegRenderer : public OperandRenderer {
 963 protected:
 964   unsigned NewInsnID;
 965   /// The matcher for the instruction that this operand is copied from.
 966   /// This provides the facility for looking up an a operand by it's name so
 967   /// that it can be used as a source for the instruction being built.
 968   const InstructionMatcher &Matched;
 969   /// The name of the operand.
 970   const StringRef SymbolicName;
 971   /// The subregister to extract.
 972   const CodeGenSubRegIndex *SubReg;
 973
 974 public:
 975   CopySubRegRenderer(unsigned NewInsnID, const InstructionMatcher &Matched,
 976                      StringRef SymbolicName, const CodeGenSubRegIndex *SubReg)
 977       : OperandRenderer(OR_CopySubReg), NewInsnID(NewInsnID), Matched(Matched),
 978         SymbolicName(SymbolicName), SubReg(SubReg) {}
 979
 980   static bool classof(const OperandRenderer *R) {
 981     return R->getKind() == OR_CopySubReg;
 982   }
 983
 984   const StringRef getSymbolicName() const { return SymbolicName; }
 985
 986   void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
 987     const OperandMatcher &Operand = Matched.getOperand(SymbolicName);
 988     unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
 989     OS << "    GIR_CopySubReg, /*NewInsnID*/" << NewInsnID
 990        << ", /*OldInsnID*/" << OldInsnVarID << ", /*OpIdx*/"
 991        << Operand.getOperandIndex() << ", /*SubRegIdx*/" << SubReg->EnumValue
 992        << ", // " << SymbolicName << "\n";
 993   }
 994 };
 995
 996 /// Adds a specific physical register to the instruction being built.
 997 /// This is typically useful for WZR/XZR on AArch64.
 998 class AddRegisterRenderer : public OperandRenderer {
 999 protected:
1000   unsigned InsnID;
1001   const Record *RegisterDef;
1002
1003 public:
1004   AddRegisterRenderer(unsigned InsnID, const Record *RegisterDef)
1005       : OperandRenderer(OR_Register), InsnID(InsnID), RegisterDef(RegisterDef) {
1006   }
1007
1008   static bool classof(const OperandRenderer *R) {
1009     return R->getKind() == OR_Register;
1010   }
1011
1012   void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
1013     OS << "      GIR_AddRegister, /*InsnID*/" << InsnID << ", "
1014        << (RegisterDef->getValue("Namespace")
1015                ? RegisterDef->getValueAsString("Namespace")
1016                : "")
1017        << "::" << RegisterDef->getName() << ",\n";
1018   }
1019 };
1020
1021 /// Adds a specific immediate to the instruction being built.
1022 class ImmRenderer : public OperandRenderer {
1023 protected:
1024   unsigned InsnID;
1025   int64_t Imm;
1026
1027 public:
1028   ImmRenderer(unsigned InsnID, int64_t Imm)
1029       : OperandRenderer(OR_Imm), InsnID(InsnID), Imm(Imm) {}
1030
1031   static bool classof(const OperandRenderer *R) {
1032     return R->getKind() == OR_Imm;
1033   }
1034
1035   void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
1036     OS << "      GIR_AddImm, /*InsnID*/" << InsnID << ", /*Imm*/" << Imm
1037        << ",\n";
1038   }
1039 };
1040
1041 /// Adds operands by calling a renderer function supplied by the ComplexPattern
1042 /// matcher function.
1043 class RenderComplexPatternOperand : public OperandRenderer {
1044 private:
1045   unsigned InsnID;
1046   const Record &TheDef;
1047   /// The name of the operand.
1048   const StringRef SymbolicName;
1049   /// The renderer number. This must be unique within a rule since it's used to
1050   /// identify a temporary variable to hold the renderer function.
1051   unsigned RendererID;
1052
1053   unsigned getNumOperands() const {
1054     return TheDef.getValueAsDag("Operands")->getNumArgs();
1055   }
1056
1057 public:
1058   RenderComplexPatternOperand(unsigned InsnID, const Record &TheDef,
1059                               StringRef SymbolicName, unsigned RendererID)
1060       : OperandRenderer(OR_ComplexPattern), InsnID(InsnID), TheDef(TheDef),
1061         SymbolicName(SymbolicName), RendererID(RendererID) {}
1062
1063   static bool classof(const OperandRenderer *R) {
1064     return R->getKind() == OR_ComplexPattern;
1065   }
1066
1067   void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
1068     OS << "    GIR_ComplexRenderer, /*InsnID*/" << InsnID << ", /*RendererID*/"
1069        << RendererID << ",\n";
1070   }
1071 };
1072
1073 /// An action taken when all Matcher predicates succeeded for a parent rule.
1074 ///
1075 /// Typical actions include:
1076 /// * Changing the opcode of an instruction.
1077 /// * Adding an operand to an instruction.
1078 class MatchAction {
1079 public:
1080   virtual ~MatchAction() {}
1081
1082   /// Emit the C++ statements to implement the action.
1083   ///
1084   /// \param RecycleInsnID If given, it's an instruction to recycle. The
1085   ///                      requirements on the instruction vary from action to
1086   ///                      action.
1087   virtual void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
1088                                   unsigned RecycleInsnID) const = 0;
1089 };
1090
1091 /// Generates a comment describing the matched rule being acted upon.
1092 class DebugCommentAction : public MatchAction {
1093 private:
1094   const PatternToMatch &P;
1095
1096 public:
1097   DebugCommentAction(const PatternToMatch &P) : P(P) {}
1098
1099   void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
1100                           unsigned RecycleInsnID) const override {
1101     OS << "    // " << *P.getSrcPattern() << "  =>  " << *P.getDstPattern()
1102        << "\n";
1103   }
1104 };
1105
1106 /// Generates code to build an instruction or mutate an existing instruction
1107 /// into the desired instruction when this is possible.
1108 class BuildMIAction : public MatchAction {
1109 private:
1110   unsigned InsnID;
1111   const CodeGenInstruction *I;
1112   const InstructionMatcher &Matched;
1113   std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers;
1114
1115   /// True if the instruction can be built solely by mutating the opcode.
1116   bool canMutate() const {
1117     if (OperandRenderers.size() != Matched.getNumOperands())
1118       return false;
1119
1120     for (const auto &Renderer : enumerate(OperandRenderers)) {
1121       if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) {
1122         const OperandMatcher &OM = Matched.getOperand(Copy->getSymbolicName());
1123         if (&Matched != &OM.getInstructionMatcher() ||
1124             OM.getOperandIndex() != Renderer.index())
1125           return false;
1126       } else
1127         return false;
1128     }
1129
1130     return true;
1131   }
1132
1133 public:
1134   BuildMIAction(unsigned InsnID, const CodeGenInstruction *I,
1135                 const InstructionMatcher &Matched)
1136       : InsnID(InsnID), I(I), Matched(Matched) {}
1137
1138   template <class Kind, class... Args>
1139   Kind &addRenderer(Args&&... args) {
1140     OperandRenderers.emplace_back(
1141         llvm::make_unique<Kind>(std::forward<Args>(args)...));
1142     return *static_cast<Kind *>(OperandRenderers.back().get());
1143   }
1144
1145   void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
1146                           unsigned RecycleInsnID) const override {
1147     if (canMutate()) {
1148       OS << "    GIR_MutateOpcode, /*InsnID*/" << InsnID
1149          << ", /*RecycleInsnID*/ " << RecycleInsnID << ", /*Opcode*/"
1150          << I->Namespace << "::" << I->TheDef->getName() << ",\n";
1151
1152       if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) {
1153         for (auto Def : I->ImplicitDefs) {
1154           auto Namespace = Def->getValue("Namespace")
1155                                ? Def->getValueAsString("Namespace")
1156                                : "";
1157           OS << "    GIR_AddImplicitDef, " << InsnID << ", " << Namespace
1158              << "::" << Def->getName() << ",\n";
1159         }
1160         for (auto Use : I->ImplicitUses) {
1161           auto Namespace = Use->getValue("Namespace")
1162                                ? Use->getValueAsString("Namespace")
1163                                : "";
1164           OS << "    GIR_AddImplicitUse, " << InsnID << ", " << Namespace
1165              << "::" << Use->getName() << ",\n";
1166         }
1167       }
1168       return;
1169     }
1170
1171     // TODO: Simple permutation looks like it could be almost as common as
1172     //       mutation due to commutative operations.
1173
1174     OS << "    GIR_BuildMI, /*InsnID*/" << InsnID << ", /*Opcode*/"
1175        << I->Namespace << "::" << I->TheDef->getName() << ",\n";
1176     for (const auto &Renderer : OperandRenderers)
1177       Renderer->emitRenderOpcodes(OS, Rule);
1178
1179     OS << "    GIR_MergeMemOperands, /*InsnID*/" << InsnID << ",\n"
1180        << "    GIR_EraseFromParent, /*InsnID*/" << RecycleInsnID << ",\n";
1181   }
1182 };
1183
1184 /// Generates code to constrain the operands of an output instruction to the
1185 /// register classes specified by the definition of that instruction.
1186 class ConstrainOperandsToDefinitionAction : public MatchAction {
1187   unsigned InsnID;
1188
1189 public:
1190   ConstrainOperandsToDefinitionAction(unsigned InsnID) : InsnID(InsnID) {}
1191
1192   void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
1193                           unsigned RecycleInsnID) const override {
1194     OS << "    GIR_ConstrainSelectedInstOperands, /*InsnID*/" << InsnID << ",\n";
1195   }
1196 };
1197
1198 /// Generates code to constrain the specified operand of an output instruction
1199 /// to the specified register class.
1200 class ConstrainOperandToRegClassAction : public MatchAction {
1201   unsigned InsnID;
1202   unsigned OpIdx;
1203   const CodeGenRegisterClass &RC;
1204
1205 public:
1206   ConstrainOperandToRegClassAction(unsigned InsnID, unsigned OpIdx,
1207                                    const CodeGenRegisterClass &RC)
1208       : InsnID(InsnID), OpIdx(OpIdx), RC(RC) {}
1209
1210   void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
1211                           unsigned RecycleInsnID) const override {
1212     OS << "    GIR_ConstrainOperandRC, /*InsnID*/" << InsnID << ", /*Op*/"
1213        << OpIdx << ", /*RC " << RC.getName() << "*/ " << RC.EnumValue << ",\n";
1214   }
1215 };
1216
1217 InstructionMatcher &RuleMatcher::addInstructionMatcher() {
1218   Matchers.emplace_back(new InstructionMatcher());
1219   return *Matchers.back();
1220 }
1221
1222 void RuleMatcher::addRequiredFeature(Record *Feature) {
1223   RequiredFeatures.push_back(Feature);
1224 }
1225
1226 const std::vector<Record *> &RuleMatcher::getRequiredFeatures() const {
1227   return RequiredFeatures;
1228 }
1229
1230 template <class Kind, class... Args>
1231 Kind &RuleMatcher::addAction(Args &&... args) {
1232   Actions.emplace_back(llvm::make_unique<Kind>(std::forward<Args>(args)...));
1233   return *static_cast<Kind *>(Actions.back().get());
1234 }
1235
1236 unsigned
1237 RuleMatcher::implicitlyDefineInsnVar(const InstructionMatcher &Matcher) {
1238   unsigned NewInsnVarID = NextInsnVarID++;
1239   InsnVariableIDs[&Matcher] = NewInsnVarID;
1240   return NewInsnVarID;
1241 }
1242
1243 unsigned RuleMatcher::defineInsnVar(raw_ostream &OS,
1244                                     const InstructionMatcher &Matcher,
1245                                     unsigned InsnID, unsigned OpIdx) {
1246   unsigned NewInsnVarID = implicitlyDefineInsnVar(Matcher);
1247   OS << "    GIM_RecordInsn, /*DefineMI*/" << NewInsnVarID << ", /*MI*/"
1248      << InsnID << ", /*OpIdx*/" << OpIdx << ", // MIs[" << NewInsnVarID
1249      << "]\n";
1250   return NewInsnVarID;
1251 }
1252
1253 unsigned RuleMatcher::getInsnVarID(const InstructionMatcher &InsnMatcher) const {
1254   const auto &I = InsnVariableIDs.find(&InsnMatcher);
1255   if (I != InsnVariableIDs.end())
1256     return I->second;
1257   llvm_unreachable("Matched Insn was not captured in a local variable");
1258 }
1259
1260 /// Emit MatchTable opcodes to check the shape of the match and capture
1261 /// instructions into local variables.
1262 void RuleMatcher::emitCaptureOpcodes(raw_ostream &OS) {
1263   assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
1264   unsigned InsnVarID = implicitlyDefineInsnVar(*Matchers.front());
1265   Matchers.front()->emitCaptureOpcodes(OS, *this, InsnVarID);
1266 }
1267
1268 void RuleMatcher::emit(raw_ostream &OS) {
1269   if (Matchers.empty())
1270     llvm_unreachable("Unexpected empty matcher!");
1271
1272   // The representation supports rules that require multiple roots such as:
1273   //    %ptr(p0) = ...
1274   //    %elt0(s32) = G_LOAD %ptr
1275   //    %1(p0) = G_ADD %ptr, 4
1276   //    %elt1(s32) = G_LOAD p0 %1
1277   // which could be usefully folded into:
1278   //    %ptr(p0) = ...
1279   //    %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr
1280   // on some targets but we don't need to make use of that yet.
1281   assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
1282
1283   OS << "  const static int64_t MatchTable" << CurrentMatchTableID << "[] = {\n";
1284   if (!RequiredFeatures.empty()) {
1285     OS << "    GIM_CheckFeatures, " << getNameForFeatureBitset(RequiredFeatures)
1286        << ",\n";
1287   }
1288
1289   emitCaptureOpcodes(OS);
1290
1291   Matchers.front()->emitPredicateOpcodes(OS, *this,
1292                                          getInsnVarID(*Matchers.front()));
1293
1294   // We must also check if it's safe to fold the matched instructions.
1295   if (InsnVariableIDs.size() >= 2) {
1296     // Invert the map to create stable ordering (by var names)
1297     SmallVector<unsigned, 2> InsnIDs;
1298     for (const auto &Pair : InsnVariableIDs) {
1299       // Skip the root node since it isn't moving anywhere. Everything else is
1300       // sinking to meet it.
1301       if (Pair.first == Matchers.front().get())
1302         continue;
1303
1304       InsnIDs.push_back(Pair.second);
1305     }
1306     std::sort(InsnIDs.begin(), InsnIDs.end());
1307
1308     for (const auto &InsnID : InsnIDs) {
1309       // Reject the difficult cases until we have a more accurate check.
1310       OS << "    GIM_CheckIsSafeToFold, /*InsnID*/" << InsnID << ",\n";
1311
1312       // FIXME: Emit checks to determine it's _actually_ safe to fold and/or
1313       //        account for unsafe cases.
1314       //
1315       //        Example:
1316       //          MI1--> %0 = ...
1317       //                 %1 = ... %0
1318       //          MI0--> %2 = ... %0
1319       //          It's not safe to erase MI1. We currently handle this by not
1320       //          erasing %0 (even when it's dead).
1321       //
1322       //        Example:
1323       //          MI1--> %0 = load volatile @a
1324       //                 %1 = load volatile @a
1325       //          MI0--> %2 = ... %0
1326       //          It's not safe to sink %0's def past %1. We currently handle
1327       //          this by rejecting all loads.
1328       //
1329       //        Example:
1330       //          MI1--> %0 = load @a
1331       //                 %1 = store @a
1332       //          MI0--> %2 = ... %0
1333       //          It's not safe to sink %0's def past %1. We currently handle
1334       //          this by rejecting all loads.
1335       //
1336       //        Example:
1337       //                   G_CONDBR %cond, @BB1
1338       //                 BB0:
1339       //          MI1-->   %0 = load @a
1340       //                   G_BR @BB1
1341       //                 BB1:
1342       //          MI0-->   %2 = ... %0
1343       //          It's not always safe to sink %0 across control flow. In this
1344       //          case it may introduce a memory fault. We currentl handle this
1345       //          by rejecting all loads.
1346     }
1347   }
1348
1349   for (const auto &MA : Actions)
1350     MA->emitCxxActionStmts(OS, *this, 0);
1351   OS << "    GIR_Done,\n"
1352      << "  };\n"
1353      << "  State.MIs.resize(1);\n"
1354      << "  DEBUG(dbgs() << \"Processing MatchTable" << CurrentMatchTableID
1355      << "\\n\");\n"
1356      << "  if (executeMatchTable(*this, OutMIs, State, MatcherInfo, MatchTable"
1357      << CurrentMatchTableID << ", TII, MRI, TRI, RBI, AvailableFeatures)) {\n"
1358      << "    return true;\n"
1359      << "  }\n\n";
1360 }
1361
1362 bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
1363   // Rules involving more match roots have higher priority.
1364   if (Matchers.size() > B.Matchers.size())
1365     return true;
1366   if (Matchers.size() < B.Matchers.size())
1367     return false;
1368
1369   for (const auto &Matcher : zip(Matchers, B.Matchers)) {
1370     if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher)))
1371       return true;
1372     if (std::get<1>(Matcher)->isHigherPriorityThan(*std::get<0>(Matcher)))
1373       return false;
1374   }
1375
1376   return false;
1377 }
1378
1379 unsigned RuleMatcher::countRendererFns() const {
1380   return std::accumulate(
1381       Matchers.begin(), Matchers.end(), 0,
1382       [](unsigned A, const std::unique_ptr<InstructionMatcher> &Matcher) {
1383         return A + Matcher->countRendererFns();
1384       });
1385 }
1386
1387 //===- GlobalISelEmitter class --------------------------------------------===//
1388
1389 class GlobalISelEmitter {
1390 public:
1391   explicit GlobalISelEmitter(RecordKeeper &RK);
1392   void run(raw_ostream &OS);
1393
1394 private:
1395   const RecordKeeper &RK;
1396   const CodeGenDAGPatterns CGP;
1397   const CodeGenTarget &Target;
1398   CodeGenRegBank CGRegs;
1399
1400   /// Keep track of the equivalence between SDNodes and Instruction.
1401   /// This is defined using 'GINodeEquiv' in the target description.
1402   DenseMap<Record *, const CodeGenInstruction *> NodeEquivs;
1403
1404   /// Keep track of the equivalence between ComplexPattern's and
1405   /// GIComplexOperandMatcher. Map entries are specified by subclassing
1406   /// GIComplexPatternEquiv.
1407   DenseMap<const Record *, const Record *> ComplexPatternEquivs;
1408
1409   // Map of predicates to their subtarget features.
1410   SubtargetFeatureInfoMap SubtargetFeatures;
1411
1412   void gatherNodeEquivs();
1413   const CodeGenInstruction *findNodeEquiv(Record *N) const;
1414
1415   Error importRulePredicates(RuleMatcher &M, ArrayRef<Init *> Predicates);
1416   Expected<InstructionMatcher &>
1417   createAndImportSelDAGMatcher(InstructionMatcher &InsnMatcher,
1418                                const TreePatternNode *Src,
1419                                unsigned &TempOpIdx) const;
1420   Error importChildMatcher(InstructionMatcher &InsnMatcher,
1421                            const TreePatternNode *SrcChild, unsigned OpIdx,
1422                            unsigned &TempOpIdx) const;
1423   Expected<BuildMIAction &>
1424   createAndImportInstructionRenderer(RuleMatcher &M, const TreePatternNode *Dst,
1425                                      const InstructionMatcher &InsnMatcher);
1426   Error importExplicitUseRenderer(BuildMIAction &DstMIBuilder,
1427                                   TreePatternNode *DstChild,
1428                                   const InstructionMatcher &InsnMatcher) const;
1429   Error importDefaultOperandRenderers(BuildMIAction &DstMIBuilder,
1430                                       DagInit *DefaultOps) const;
1431   Error
1432   importImplicitDefRenderers(BuildMIAction &DstMIBuilder,
1433                              const std::vector<Record *> &ImplicitDefs) const;
1434
1435   /// Analyze pattern \p P, returning a matcher for it if possible.
1436   /// Otherwise, return an Error explaining why we don't support it.
1437   Expected<RuleMatcher> runOnPattern(const PatternToMatch &P);
1438
1439   void declareSubtargetFeature(Record *Predicate);
1440 };
1441
1442 void GlobalISelEmitter::gatherNodeEquivs() {
1443   assert(NodeEquivs.empty());
1444   for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
1445     NodeEquivs[Equiv->getValueAsDef("Node")] =
1446         &Target.getInstruction(Equiv->getValueAsDef("I"));
1447
1448   assert(ComplexPatternEquivs.empty());
1449   for (Record *Equiv : RK.getAllDerivedDefinitions("GIComplexPatternEquiv")) {
1450     Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
1451     if (!SelDAGEquiv)
1452       continue;
1453     ComplexPatternEquivs[SelDAGEquiv] = Equiv;
1454  }
1455 }
1456
1457 const CodeGenInstruction *GlobalISelEmitter::findNodeEquiv(Record *N) const {
1458   return NodeEquivs.lookup(N);
1459 }
1460
1461 GlobalISelEmitter::GlobalISelEmitter(RecordKeeper &RK)
1462     : RK(RK), CGP(RK), Target(CGP.getTargetInfo()), CGRegs(RK) {}
1463
1464 //===- Emitter ------------------------------------------------------------===//
1465
1466 Error
1467 GlobalISelEmitter::importRulePredicates(RuleMatcher &M,
1468                                         ArrayRef<Init *> Predicates) {
1469   for (const Init *Predicate : Predicates) {
1470     const DefInit *PredicateDef = static_cast<const DefInit *>(Predicate);
1471     declareSubtargetFeature(PredicateDef->getDef());
1472     M.addRequiredFeature(PredicateDef->getDef());
1473   }
1474
1475   return Error::success();
1476 }
1477
1478 Expected<InstructionMatcher &>
1479 GlobalISelEmitter::createAndImportSelDAGMatcher(InstructionMatcher &InsnMatcher,
1480                                                 const TreePatternNode *Src,
1481                                                 unsigned &TempOpIdx) const {
1482   const CodeGenInstruction *SrcGIOrNull = nullptr;
1483
1484   // Start with the defined operands (i.e., the results of the root operator).
1485   if (Src->getExtTypes().size() > 1)
1486     return failedImport("Src pattern has multiple results");
1487
1488   if (Src->isLeaf()) {
1489     Init *SrcInit = Src->getLeafValue();
1490     if (isa<IntInit>(SrcInit)) {
1491       InsnMatcher.addPredicate<InstructionOpcodeMatcher>(
1492           &Target.getInstruction(RK.getDef("G_CONSTANT")));
1493     } else
1494       return failedImport(
1495           "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
1496   } else {
1497     SrcGIOrNull = findNodeEquiv(Src->getOperator());
1498     if (!SrcGIOrNull)
1499       return failedImport("Pattern operator lacks an equivalent Instruction" +
1500                           explainOperator(Src->getOperator()));
1501     auto &SrcGI = *SrcGIOrNull;
1502
1503     // The operators look good: match the opcode
1504     InsnMatcher.addPredicate<InstructionOpcodeMatcher>(&SrcGI);
1505   }
1506
1507   unsigned OpIdx = 0;
1508   for (const EEVT::TypeSet &Ty : Src->getExtTypes()) {
1509     auto OpTyOrNone = MVTToLLT(Ty.getConcrete());
1510
1511     if (!OpTyOrNone)
1512       return failedImport(
1513           "Result of Src pattern operator has an unsupported type");
1514
1515     // Results don't have a name unless they are the root node. The caller will
1516     // set the name if appropriate.
1517     OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
1518     OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
1519   }
1520
1521   if (Src->isLeaf()) {
1522     Init *SrcInit = Src->getLeafValue();
1523     if (IntInit *SrcIntInit = dyn_cast<IntInit>(SrcInit)) {
1524       OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
1525       OM.addPredicate<LiteralIntOperandMatcher>(SrcIntInit->getValue());
1526     } else
1527       return failedImport(
1528           "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
1529   } else {
1530     assert(SrcGIOrNull &&
1531            "Expected to have already found an equivalent Instruction");
1532     // Match the used operands (i.e. the children of the operator).
1533     for (unsigned i = 0, e = Src->getNumChildren(); i != e; ++i) {
1534       TreePatternNode *SrcChild = Src->getChild(i);
1535
1536       // For G_INTRINSIC, the operand immediately following the defs is an
1537       // intrinsic ID.
1538       if (SrcGIOrNull->TheDef->getName() == "G_INTRINSIC" && i == 0) {
1539         if (const CodeGenIntrinsic *II = Src->getIntrinsicInfo(CGP)) {
1540           OperandMatcher &OM =
1541               InsnMatcher.addOperand(OpIdx++, SrcChild->getName(), TempOpIdx);
1542           OM.addPredicate<IntrinsicIDOperandMatcher>(II);
1543           continue;
1544         }
1545
1546         return failedImport("Expected IntInit containing instrinsic ID)");
1547       }
1548
1549       if (auto Error =
1550               importChildMatcher(InsnMatcher, SrcChild, OpIdx++, TempOpIdx))
1551         return std::move(Error);
1552     }
1553   }
1554
1555   return InsnMatcher;
1556 }
1557
1558 Error GlobalISelEmitter::importChildMatcher(InstructionMatcher &InsnMatcher,
1559                                             const TreePatternNode *SrcChild,
1560                                             unsigned OpIdx,
1561                                             unsigned &TempOpIdx) const {
1562   OperandMatcher &OM =
1563       InsnMatcher.addOperand(OpIdx, SrcChild->getName(), TempOpIdx);
1564
1565   if (SrcChild->hasAnyPredicate())
1566     return failedImport("Src pattern child has predicate (" +
1567                         explainPredicates(SrcChild) + ")");
1568
1569   ArrayRef<EEVT::TypeSet> ChildTypes = SrcChild->getExtTypes();
1570   if (ChildTypes.size() != 1)
1571     return failedImport("Src pattern child has multiple results");
1572
1573   // Check MBB's before the type check since they are not a known type.
1574   if (!SrcChild->isLeaf()) {
1575     if (SrcChild->getOperator()->isSubClassOf("SDNode")) {
1576       auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator());
1577       if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
1578         OM.addPredicate<MBBOperandMatcher>();
1579         return Error::success();
1580       }
1581     }
1582   }
1583
1584   auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete());
1585   if (!OpTyOrNone)
1586     return failedImport("Src operand has an unsupported type (" + to_string(*SrcChild) + ")");
1587   OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
1588
1589   // Check for nested instructions.
1590   if (!SrcChild->isLeaf()) {
1591     // Map the node to a gMIR instruction.
1592     InstructionOperandMatcher &InsnOperand =
1593         OM.addPredicate<InstructionOperandMatcher>();
1594     auto InsnMatcherOrError = createAndImportSelDAGMatcher(
1595         InsnOperand.getInsnMatcher(), SrcChild, TempOpIdx);
1596     if (auto Error = InsnMatcherOrError.takeError())
1597       return Error;
1598
1599     return Error::success();
1600   }
1601
1602   // Check for constant immediates.
1603   if (auto *ChildInt = dyn_cast<IntInit>(SrcChild->getLeafValue())) {
1604     OM.addPredicate<ConstantIntOperandMatcher>(ChildInt->getValue());
1605     return Error::success();
1606   }
1607
1608   // Check for def's like register classes or ComplexPattern's.
1609   if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
1610     auto *ChildRec = ChildDefInit->getDef();
1611
1612     // Check for register classes.
1613     if (ChildRec->isSubClassOf("RegisterClass") ||
1614         ChildRec->isSubClassOf("RegisterOperand")) {
1615       OM.addPredicate<RegisterBankOperandMatcher>(
1616           Target.getRegisterClass(getInitValueAsRegClass(ChildDefInit)));
1617       return Error::success();
1618     }
1619
1620     // Check for ComplexPattern's.
1621     if (ChildRec->isSubClassOf("ComplexPattern")) {
1622       const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
1623       if (ComplexPattern == ComplexPatternEquivs.end())
1624         return failedImport("SelectionDAG ComplexPattern (" +
1625                             ChildRec->getName() + ") not mapped to GlobalISel");
1626
1627       OM.addPredicate<ComplexPatternOperandMatcher>(OM,
1628                                                     *ComplexPattern->second);
1629       TempOpIdx++;
1630       return Error::success();
1631     }
1632
1633     if (ChildRec->isSubClassOf("ImmLeaf")) {
1634       return failedImport(
1635           "Src pattern child def is an unsupported tablegen class (ImmLeaf)");
1636     }
1637
1638     return failedImport(
1639         "Src pattern child def is an unsupported tablegen class");
1640   }
1641
1642   return failedImport("Src pattern child is an unsupported kind");
1643 }
1644
1645 Error GlobalISelEmitter::importExplicitUseRenderer(
1646     BuildMIAction &DstMIBuilder, TreePatternNode *DstChild,
1647     const InstructionMatcher &InsnMatcher) const {
1648   // The only non-leaf child we accept is 'bb': it's an operator because
1649   // BasicBlockSDNode isn't inline, but in MI it's just another operand.
1650   if (!DstChild->isLeaf()) {
1651     if (DstChild->getOperator()->isSubClassOf("SDNode")) {
1652       auto &ChildSDNI = CGP.getSDNodeInfo(DstChild->getOperator());
1653       if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
1654         DstMIBuilder.addRenderer<CopyRenderer>(0, InsnMatcher,
1655                                                DstChild->getName());
1656         return Error::success();
1657       }
1658     }
1659     return failedImport("Dst pattern child isn't a leaf node or an MBB");
1660   }
1661
1662   // Otherwise, we're looking for a bog-standard RegisterClass operand.
1663   if (DstChild->hasAnyPredicate())
1664     return failedImport("Dst pattern child has predicate (" +
1665                         explainPredicates(DstChild) + ")");
1666
1667   if (auto *ChildDefInit = dyn_cast<DefInit>(DstChild->getLeafValue())) {
1668     auto *ChildRec = ChildDefInit->getDef();
1669
1670     ArrayRef<EEVT::TypeSet> ChildTypes = DstChild->getExtTypes();
1671     if (ChildTypes.size() != 1)
1672       return failedImport("Dst pattern child has multiple results");
1673
1674     auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete());
1675     if (!OpTyOrNone)
1676       return failedImport("Dst operand has an unsupported type");
1677
1678     if (ChildRec->isSubClassOf("Register")) {
1679       DstMIBuilder.addRenderer<AddRegisterRenderer>(0, ChildRec);
1680       return Error::success();
1681     }
1682
1683     if (ChildRec->isSubClassOf("RegisterClass") ||
1684         ChildRec->isSubClassOf("RegisterOperand")) {
1685       DstMIBuilder.addRenderer<CopyRenderer>(0, InsnMatcher,
1686                                              DstChild->getName());
1687       return Error::success();
1688     }
1689
1690     if (ChildRec->isSubClassOf("ComplexPattern")) {
1691       const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
1692       if (ComplexPattern == ComplexPatternEquivs.end())
1693         return failedImport(
1694             "SelectionDAG ComplexPattern not mapped to GlobalISel");
1695
1696       const OperandMatcher &OM = InsnMatcher.getOperand(DstChild->getName());
1697       DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
1698           0, *ComplexPattern->second, DstChild->getName(),
1699           OM.getAllocatedTemporariesBaseID());
1700       return Error::success();
1701     }
1702
1703     if (ChildRec->isSubClassOf("SDNodeXForm"))
1704       return failedImport("Dst pattern child def is an unsupported tablegen "
1705                           "class (SDNodeXForm)");
1706
1707     return failedImport(
1708         "Dst pattern child def is an unsupported tablegen class");
1709   }
1710
1711   return failedImport("Dst pattern child is an unsupported kind");
1712 }
1713
1714 Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
1715     RuleMatcher &M, const TreePatternNode *Dst,
1716     const InstructionMatcher &InsnMatcher) {
1717   Record *DstOp = Dst->getOperator();
1718   if (!DstOp->isSubClassOf("Instruction")) {
1719     if (DstOp->isSubClassOf("ValueType"))
1720       return failedImport(
1721           "Pattern operator isn't an instruction (it's a ValueType)");
1722     return failedImport("Pattern operator isn't an instruction");
1723   }
1724   CodeGenInstruction *DstI = &Target.getInstruction(DstOp);
1725
1726   unsigned DstINumUses = DstI->Operands.size() - DstI->Operands.NumDefs;
1727   unsigned ExpectedDstINumUses = Dst->getNumChildren();
1728   bool IsExtractSubReg = false;
1729
1730   // COPY_TO_REGCLASS is just a copy with a ConstrainOperandToRegClassAction
1731   // attached. Similarly for EXTRACT_SUBREG except that's a subregister copy.
1732   if (DstI->TheDef->getName() == "COPY_TO_REGCLASS") {
1733     DstI = &Target.getInstruction(RK.getDef("COPY"));
1734     DstINumUses--; // Ignore the class constraint.
1735     ExpectedDstINumUses--;
1736   } else if (DstI->TheDef->getName() == "EXTRACT_SUBREG") {
1737     DstI = &Target.getInstruction(RK.getDef("COPY"));
1738     IsExtractSubReg = true;
1739   }
1740
1741   auto &DstMIBuilder = M.addAction<BuildMIAction>(0, DstI, InsnMatcher);
1742
1743   // Render the explicit defs.
1744   for (unsigned I = 0; I < DstI->Operands.NumDefs; ++I) {
1745     const CGIOperandList::OperandInfo &DstIOperand = DstI->Operands[I];
1746     DstMIBuilder.addRenderer<CopyRenderer>(0, InsnMatcher, DstIOperand.Name);
1747   }
1748
1749   // EXTRACT_SUBREG needs to use a subregister COPY.
1750   if (IsExtractSubReg) {
1751     if (!Dst->getChild(0)->isLeaf())
1752       return failedImport("EXTRACT_SUBREG child #1 is not a leaf");
1753
1754     if (DefInit *SubRegInit =
1755             dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue())) {
1756       CodeGenRegisterClass *RC = CGRegs.getRegClass(
1757           getInitValueAsRegClass(Dst->getChild(0)->getLeafValue()));
1758       CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
1759
1760       const auto &SrcRCDstRCPair =
1761           RC->getMatchingSubClassWithSubRegs(CGRegs, SubIdx);
1762       if (SrcRCDstRCPair.hasValue()) {
1763         assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
1764         if (SrcRCDstRCPair->first != RC)
1765           return failedImport("EXTRACT_SUBREG requires an additional COPY");
1766       }
1767
1768       DstMIBuilder.addRenderer<CopySubRegRenderer>(
1769           0, InsnMatcher, Dst->getChild(0)->getName(), SubIdx);
1770       return DstMIBuilder;
1771     }
1772
1773     return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
1774   }
1775
1776   // Render the explicit uses.
1777   unsigned Child = 0;
1778   unsigned NumDefaultOps = 0;
1779   for (unsigned I = 0; I != DstINumUses; ++I) {
1780     const CGIOperandList::OperandInfo &DstIOperand =
1781         DstI->Operands[DstI->Operands.NumDefs + I];
1782
1783     // If the operand has default values, introduce them now.
1784     // FIXME: Until we have a decent test case that dictates we should do
1785     // otherwise, we're going to assume that operands with default values cannot
1786     // be specified in the patterns. Therefore, adding them will not cause us to
1787     // end up with too many rendered operands.
1788     if (DstIOperand.Rec->isSubClassOf("OperandWithDefaultOps")) {
1789       DagInit *DefaultOps = DstIOperand.Rec->getValueAsDag("DefaultOps");
1790       if (auto Error = importDefaultOperandRenderers(DstMIBuilder, DefaultOps))
1791         return std::move(Error);
1792       ++NumDefaultOps;
1793       continue;
1794     }
1795
1796     if (auto Error = importExplicitUseRenderer(
1797             DstMIBuilder, Dst->getChild(Child), InsnMatcher))
1798       return std::move(Error);
1799     ++Child;
1800   }
1801
1802   if (NumDefaultOps + ExpectedDstINumUses != DstINumUses)
1803     return failedImport("Expected " + llvm::to_string(DstINumUses) +
1804                         " used operands but found " +
1805                         llvm::to_string(ExpectedDstINumUses) +
1806                         " explicit ones and " + llvm::to_string(NumDefaultOps) +
1807                         " default ones");
1808
1809   return DstMIBuilder;
1810 }
1811
1812 Error GlobalISelEmitter::importDefaultOperandRenderers(
1813     BuildMIAction &DstMIBuilder, DagInit *DefaultOps) const {
1814   for (const auto *DefaultOp : DefaultOps->getArgs()) {
1815     // Look through ValueType operators.
1816     if (const DagInit *DefaultDagOp = dyn_cast<DagInit>(DefaultOp)) {
1817       if (const DefInit *DefaultDagOperator =
1818               dyn_cast<DefInit>(DefaultDagOp->getOperator())) {
1819         if (DefaultDagOperator->getDef()->isSubClassOf("ValueType"))
1820           DefaultOp = DefaultDagOp->getArg(0);
1821       }
1822     }
1823
1824     if (const DefInit *DefaultDefOp = dyn_cast<DefInit>(DefaultOp)) {
1825       DstMIBuilder.addRenderer<AddRegisterRenderer>(0, DefaultDefOp->getDef());
1826       continue;
1827     }
1828
1829     if (const IntInit *DefaultIntOp = dyn_cast<IntInit>(DefaultOp)) {
1830       DstMIBuilder.addRenderer<ImmRenderer>(0, DefaultIntOp->getValue());
1831       continue;
1832     }
1833
1834     return failedImport("Could not add default op");
1835   }
1836
1837   return Error::success();
1838 }
1839
1840 Error GlobalISelEmitter::importImplicitDefRenderers(
1841     BuildMIAction &DstMIBuilder,
1842     const std::vector<Record *> &ImplicitDefs) const {
1843   if (!ImplicitDefs.empty())
1844     return failedImport("Pattern defines a physical register");
1845   return Error::success();
1846 }
1847
1848 Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
1849   // Keep track of the matchers and actions to emit.
1850   RuleMatcher M;
1851   M.addAction<DebugCommentAction>(P);
1852
1853   if (auto Error = importRulePredicates(M, P.getPredicates()->getValues()))
1854     return std::move(Error);
1855
1856   // Next, analyze the pattern operators.
1857   TreePatternNode *Src = P.getSrcPattern();
1858   TreePatternNode *Dst = P.getDstPattern();
1859
1860   // If the root of either pattern isn't a simple operator, ignore it.
1861   if (auto Err = isTrivialOperatorNode(Dst))
1862     return failedImport("Dst pattern root isn't a trivial operator (" +
1863                         toString(std::move(Err)) + ")");
1864   if (auto Err = isTrivialOperatorNode(Src))
1865     return failedImport("Src pattern root isn't a trivial operator (" +
1866                         toString(std::move(Err)) + ")");
1867
1868   if (Dst->isLeaf())
1869     return failedImport("Dst pattern root isn't a known leaf");
1870
1871   // Start with the defined operands (i.e., the results of the root operator).
1872   Record *DstOp = Dst->getOperator();
1873   if (!DstOp->isSubClassOf("Instruction"))
1874     return failedImport("Pattern operator isn't an instruction");
1875
1876   auto &DstI = Target.getInstruction(DstOp);
1877   if (DstI.Operands.NumDefs != Src->getExtTypes().size())
1878     return failedImport("Src pattern results and dst MI defs are different (" +
1879                         to_string(Src->getExtTypes().size()) + " def(s) vs " +
1880                         to_string(DstI.Operands.NumDefs) + " def(s))");
1881
1882   InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher();
1883   unsigned TempOpIdx = 0;
1884   auto InsnMatcherOrError =
1885       createAndImportSelDAGMatcher(InsnMatcherTemp, Src, TempOpIdx);
1886   if (auto Error = InsnMatcherOrError.takeError())
1887     return std::move(Error);
1888   InstructionMatcher &InsnMatcher = InsnMatcherOrError.get();
1889
1890   // The root of the match also has constraints on the register bank so that it
1891   // matches the result instruction.
1892   unsigned OpIdx = 0;
1893   for (const EEVT::TypeSet &Ty : Src->getExtTypes()) {
1894     (void)Ty;
1895
1896     const auto &DstIOperand = DstI.Operands[OpIdx];
1897     Record *DstIOpRec = DstIOperand.Rec;
1898     if (DstI.TheDef->getName() == "COPY_TO_REGCLASS") {
1899       DstIOpRec = getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());
1900
1901       if (DstIOpRec == nullptr)
1902         return failedImport(
1903             "COPY_TO_REGCLASS operand #1 isn't a register class");
1904     } else if (DstI.TheDef->getName() == "EXTRACT_SUBREG") {
1905       if (!Dst->getChild(0)->isLeaf())
1906         return failedImport("EXTRACT_SUBREG operand #0 isn't a leaf");
1907
1908       // We can assume that a subregister is in the same bank as it's super
1909       // register.
1910       DstIOpRec = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
1911
1912       if (DstIOpRec == nullptr)
1913         return failedImport(
1914             "EXTRACT_SUBREG operand #0 isn't a register class");
1915     } else if (DstIOpRec->isSubClassOf("RegisterOperand"))
1916       DstIOpRec = DstIOpRec->getValueAsDef("RegClass");
1917     else if (!DstIOpRec->isSubClassOf("RegisterClass"))
1918       return failedImport("Dst MI def isn't a register class" +
1919                           to_string(*Dst));
1920
1921     OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
1922     OM.setSymbolicName(DstIOperand.Name);
1923     OM.addPredicate<RegisterBankOperandMatcher>(
1924         Target.getRegisterClass(DstIOpRec));
1925     ++OpIdx;
1926   }
1927
1928   auto DstMIBuilderOrError =
1929       createAndImportInstructionRenderer(M, Dst, InsnMatcher);
1930   if (auto Error = DstMIBuilderOrError.takeError())
1931     return std::move(Error);
1932   BuildMIAction &DstMIBuilder = DstMIBuilderOrError.get();
1933
1934   // Render the implicit defs.
1935   // These are only added to the root of the result.
1936   if (auto Error = importImplicitDefRenderers(DstMIBuilder, P.getDstRegs()))
1937     return std::move(Error);
1938
1939   // Constrain the registers to classes. This is normally derived from the
1940   // emitted instruction but a few instructions require special handling.
1941   if (DstI.TheDef->getName() == "COPY_TO_REGCLASS") {
1942     // COPY_TO_REGCLASS does not provide operand constraints itself but the
1943     // result is constrained to the class given by the second child.
1944     Record *DstIOpRec =
1945         getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());
1946
1947     if (DstIOpRec == nullptr)
1948       return failedImport("COPY_TO_REGCLASS operand #1 isn't a register class");
1949
1950     M.addAction<ConstrainOperandToRegClassAction>(
1951         0, 0, Target.getRegisterClass(DstIOpRec));
1952
1953     // We're done with this pattern!  It's eligible for GISel emission; return
1954     // it.
1955     ++NumPatternImported;
1956     return std::move(M);
1957   }
1958
1959   if (DstI.TheDef->getName() == "EXTRACT_SUBREG") {
1960     // EXTRACT_SUBREG selects into a subregister COPY but unlike most
1961     // instructions, the result register class is controlled by the
1962     // subregisters of the operand. As a result, we must constrain the result
1963     // class rather than check that it's already the right one.
1964     if (!Dst->getChild(0)->isLeaf())
1965       return failedImport("EXTRACT_SUBREG child #1 is not a leaf");
1966
1967     DefInit *SubRegInit = dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue());
1968     if (!SubRegInit)
1969       return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
1970
1971     // Constrain the result to the same register bank as the operand.
1972     Record *DstIOpRec =
1973         getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
1974
1975     if (DstIOpRec == nullptr)
1976       return failedImport("EXTRACT_SUBREG operand #1 isn't a register class");
1977
1978     CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
1979     CodeGenRegisterClass *SrcRC = CGRegs.getRegClass(DstIOpRec);
1980
1981     // It would be nice to leave this constraint implicit but we're required
1982     // to pick a register class so constrain the result to a register class
1983     // that can hold the correct MVT.
1984     //
1985     // FIXME: This may introduce an extra copy if the chosen class doesn't
1986     //        actually contain the subregisters.
1987     assert(Src->getExtTypes().size() == 1 &&
1988              "Expected Src of EXTRACT_SUBREG to have one result type");
1989
1990     const auto &SrcRCDstRCPair =
1991         SrcRC->getMatchingSubClassWithSubRegs(CGRegs, SubIdx);
1992     assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
1993     M.addAction<ConstrainOperandToRegClassAction>(0, 0, *SrcRCDstRCPair->second);
1994     M.addAction<ConstrainOperandToRegClassAction>(0, 1, *SrcRCDstRCPair->first);
1995
1996     // We're done with this pattern!  It's eligible for GISel emission; return
1997     // it.
1998     ++NumPatternImported;
1999     return std::move(M);
2000   }
2001
2002   M.addAction<ConstrainOperandsToDefinitionAction>(0);
2003
2004   // We're done with this pattern!  It's eligible for GISel emission; return it.
2005   ++NumPatternImported;
2006   return std::move(M);
2007 }
2008
2009 void GlobalISelEmitter::run(raw_ostream &OS) {
2010   // Track the GINodeEquiv definitions.
2011   gatherNodeEquivs();
2012
2013   emitSourceFileHeader(("Global Instruction Selector for the " +
2014                        Target.getName() + " target").str(), OS);
2015   std::vector<RuleMatcher> Rules;
2016   // Look through the SelectionDAG patterns we found, possibly emitting some.
2017   for (const PatternToMatch &Pat : CGP.ptms()) {
2018     ++NumPatternTotal;
2019     auto MatcherOrErr = runOnPattern(Pat);
2020
2021     // The pattern analysis can fail, indicating an unsupported pattern.
2022     // Report that if we've been asked to do so.
2023     if (auto Err = MatcherOrErr.takeError()) {
2024       if (WarnOnSkippedPatterns) {
2025         PrintWarning(Pat.getSrcRecord()->getLoc(),
2026                      "Skipped pattern: " + toString(std::move(Err)));
2027       } else {
2028         consumeError(std::move(Err));
2029       }
2030       ++NumPatternImportsSkipped;
2031       continue;
2032     }
2033
2034     Rules.push_back(std::move(MatcherOrErr.get()));
2035   }
2036
2037   std::stable_sort(Rules.begin(), Rules.end(),
2038             [&](const RuleMatcher &A, const RuleMatcher &B) {
2039               if (A.isHigherPriorityThan(B)) {
2040                 assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
2041                                                      "and less important at "
2042                                                      "the same time");
2043                 return true;
2044               }
2045               return false;
2046             });
2047
2048   std::vector<Record *> ComplexPredicates =
2049       RK.getAllDerivedDefinitions("GIComplexOperandMatcher");
2050   std::sort(ComplexPredicates.begin(), ComplexPredicates.end(),
2051             [](const Record *A, const Record *B) {
2052               if (A->getName() < B->getName())
2053                 return true;
2054               return false;
2055             });
2056   unsigned MaxTemporaries = 0;
2057   for (const auto &Rule : Rules)
2058     MaxTemporaries = std::max(MaxTemporaries, Rule.countRendererFns());
2059
2060   OS << "#ifdef GET_GLOBALISEL_PREDICATE_BITSET\n"
2061      << "const unsigned MAX_SUBTARGET_PREDICATES = " << SubtargetFeatures.size()
2062      << ";\n"
2063      << "using PredicateBitset = "
2064         "llvm::PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;\n"
2065      << "#endif // ifdef GET_GLOBALISEL_PREDICATE_BITSET\n\n";
2066
2067   OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n"
2068      << "  mutable MatcherState State;\n"
2069      << "  typedef "
2070         "ComplexRendererFn("
2071      << Target.getName()
2072      << "InstructionSelector::*ComplexMatcherMemFn)(MachineOperand &) const;\n"
2073      << "const MatcherInfoTy<PredicateBitset, ComplexMatcherMemFn> "
2074         "MatcherInfo;\n"
2075      << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n";
2076
2077   OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n"
2078      << ", State(" << MaxTemporaries << "),\n"
2079      << "MatcherInfo({TypeObjects, FeatureBitsets, {\n"
2080      << "  nullptr, // GICP_Invalid\n";
2081   for (const auto &Record : ComplexPredicates)
2082     OS << "  &" << Target.getName()
2083        << "InstructionSelector::" << Record->getValueAsString("MatcherFn")
2084        << ", // " << Record->getName() << "\n";
2085   OS << "}})\n"
2086      << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";
2087
2088   OS << "#ifdef GET_GLOBALISEL_IMPL\n";
2089   SubtargetFeatureInfo::emitSubtargetFeatureBitEnumeration(SubtargetFeatures,
2090                                                            OS);
2091
2092   // Separate subtarget features by how often they must be recomputed.
2093   SubtargetFeatureInfoMap ModuleFeatures;
2094   std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
2095                std::inserter(ModuleFeatures, ModuleFeatures.end()),
2096                [](const SubtargetFeatureInfoMap::value_type &X) {
2097                  return !X.second.mustRecomputePerFunction();
2098                });
2099   SubtargetFeatureInfoMap FunctionFeatures;
2100   std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
2101                std::inserter(FunctionFeatures, FunctionFeatures.end()),
2102                [](const SubtargetFeatureInfoMap::value_type &X) {
2103                  return X.second.mustRecomputePerFunction();
2104                });
2105
2106   SubtargetFeatureInfo::emitComputeAvailableFeatures(
2107       Target.getName(), "InstructionSelector", "computeAvailableModuleFeatures",
2108       ModuleFeatures, OS);
2109   SubtargetFeatureInfo::emitComputeAvailableFeatures(
2110       Target.getName(), "InstructionSelector",
2111       "computeAvailableFunctionFeatures", FunctionFeatures, OS,
2112       "const MachineFunction *MF");
2113
2114   // Emit a table containing the LLT objects needed by the matcher and an enum
2115   // for the matcher to reference them with.
2116   std::vector<LLTCodeGen> TypeObjects = {
2117       LLT::scalar(8),      LLT::scalar(16),     LLT::scalar(32),
2118       LLT::scalar(64),     LLT::scalar(80),     LLT::vector(8, 1),
2119       LLT::vector(16, 1),  LLT::vector(32, 1),  LLT::vector(64, 1),
2120       LLT::vector(8, 8),   LLT::vector(16, 8),  LLT::vector(32, 8),
2121       LLT::vector(64, 8),  LLT::vector(4, 16),  LLT::vector(8, 16),
2122       LLT::vector(16, 16), LLT::vector(32, 16), LLT::vector(2, 32),
2123       LLT::vector(4, 32),  LLT::vector(8, 32),  LLT::vector(16, 32),
2124       LLT::vector(2, 64),  LLT::vector(4, 64),  LLT::vector(8, 64),
2125   };
2126   std::sort(TypeObjects.begin(), TypeObjects.end());
2127   OS << "enum {\n";
2128   for (const auto &TypeObject : TypeObjects) {
2129     OS << "  ";
2130     TypeObject.emitCxxEnumValue(OS);
2131     OS << ",\n";
2132   }
2133   OS << "};\n"
2134      << "const static LLT TypeObjects[] = {\n";
2135   for (const auto &TypeObject : TypeObjects) {
2136     OS << "  ";
2137     TypeObject.emitCxxConstructorCall(OS);
2138     OS << ",\n";
2139   }
2140   OS << "};\n\n";
2141
2142   // Emit a table containing the PredicateBitsets objects needed by the matcher
2143   // and an enum for the matcher to reference them with.
2144   std::vector<std::vector<Record *>> FeatureBitsets;
2145   for (auto &Rule : Rules)
2146     FeatureBitsets.push_back(Rule.getRequiredFeatures());
2147   std::sort(
2148       FeatureBitsets.begin(), FeatureBitsets.end(),
2149       [&](const std::vector<Record *> &A, const std::vector<Record *> &B) {
2150         if (A.size() < B.size())
2151           return true;
2152         if (A.size() > B.size())
2153           return false;
2154         for (const auto &Pair : zip(A, B)) {
2155           if (std::get<0>(Pair)->getName() < std::get<1>(Pair)->getName())
2156             return true;
2157           if (std::get<0>(Pair)->getName() > std::get<1>(Pair)->getName())
2158             return false;
2159         }
2160         return false;
2161       });
2162   FeatureBitsets.erase(
2163       std::unique(FeatureBitsets.begin(), FeatureBitsets.end()),
2164       FeatureBitsets.end());
2165   OS << "enum {\n"
2166      << "  GIFBS_Invalid,\n";
2167   for (const auto &FeatureBitset : FeatureBitsets) {
2168     if (FeatureBitset.empty())
2169       continue;
2170     OS << "  " << getNameForFeatureBitset(FeatureBitset) << ",\n";
2171   }
2172   OS << "};\n"
2173      << "const static PredicateBitset FeatureBitsets[] {\n"
2174      << "  {}, // GIFBS_Invalid\n";
2175   for (const auto &FeatureBitset : FeatureBitsets) {
2176     if (FeatureBitset.empty())
2177       continue;
2178     OS << "  {";
2179     for (const auto &Feature : FeatureBitset) {
2180       const auto &I = SubtargetFeatures.find(Feature);
2181       assert(I != SubtargetFeatures.end() && "Didn't import predicate?");
2182       OS << I->second.getEnumBitName() << ", ";
2183     }
2184     OS << "},\n";
2185   }
2186   OS << "};\n\n";
2187
2188   // Emit complex predicate table and an enum to reference them with.
2189   OS << "enum {\n"
2190      << "  GICP_Invalid,\n";
2191   for (const auto &Record : ComplexPredicates)
2192     OS << "  GICP_" << Record->getName() << ",\n";
2193   OS << "};\n"
2194      << "// See constructor for table contents\n\n";
2195
2196   OS << "bool " << Target.getName()
2197      << "InstructionSelector::selectImpl(MachineInstr &I) const {\n"
2198      << "  MachineFunction &MF = *I.getParent()->getParent();\n"
2199      << "  MachineRegisterInfo &MRI = MF.getRegInfo();\n"
2200      << "  // FIXME: This should be computed on a per-function basis rather "
2201         "than per-insn.\n"
2202      << "  AvailableFunctionFeatures = computeAvailableFunctionFeatures(&STI, "
2203         "&MF);\n"
2204      << "  const PredicateBitset AvailableFeatures = getAvailableFeatures();\n"
2205      << "  NewMIVector OutMIs;\n"
2206      << "  State.MIs.clear();\n"
2207      << "  State.MIs.push_back(&I);\n\n";
2208
2209   for (auto &Rule : Rules) {
2210     Rule.emit(OS);
2211     ++CurrentMatchTableID;
2212     ++NumPatternEmitted;
2213     assert(CurrentMatchTableID == NumPatternEmitted &&
2214            "Statistic deviates from number of emitted tables");
2215   }
2216
2217   OS << "  return false;\n"
2218      << "}\n"
2219      << "#endif // ifdef GET_GLOBALISEL_IMPL\n";
2220
2221   OS << "#ifdef GET_GLOBALISEL_PREDICATES_DECL\n"
2222      << "PredicateBitset AvailableModuleFeatures;\n"
2223      << "mutable PredicateBitset AvailableFunctionFeatures;\n"
2224      << "PredicateBitset getAvailableFeatures() const {\n"
2225      << "  return AvailableModuleFeatures | AvailableFunctionFeatures;\n"
2226      << "}\n"
2227      << "PredicateBitset\n"
2228      << "computeAvailableModuleFeatures(const " << Target.getName()
2229      << "Subtarget *Subtarget) const;\n"
2230      << "PredicateBitset\n"
2231      << "computeAvailableFunctionFeatures(const " << Target.getName()
2232      << "Subtarget *Subtarget,\n"
2233      << "                                 const MachineFunction *MF) const;\n"
2234      << "#endif // ifdef GET_GLOBALISEL_PREDICATES_DECL\n";
2235
2236   OS << "#ifdef GET_GLOBALISEL_PREDICATES_INIT\n"
2237      << "AvailableModuleFeatures(computeAvailableModuleFeatures(&STI)),\n"
2238      << "AvailableFunctionFeatures()\n"
2239      << "#endif // ifdef GET_GLOBALISEL_PREDICATES_INIT\n";
2240 }
2241
2242 void GlobalISelEmitter::declareSubtargetFeature(Record *Predicate) {
2243   if (SubtargetFeatures.count(Predicate) == 0)
2244     SubtargetFeatures.emplace(
2245         Predicate, SubtargetFeatureInfo(Predicate, SubtargetFeatures.size()));
2246 }
2247
2248 } // end anonymous namespace
2249
2250 //===----------------------------------------------------------------------===//
2251
2252 namespace llvm {
2253 void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS) {
2254   GlobalISelEmitter(RK).run(OS);
2255 }
2256 } // End llvm namespace