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
  57 cl::OptionCategory GlobalISelEmitterCat("Options for -gen-global-isel");
  58
  59 static cl::opt<bool> WarnOnSkippedPatterns(
  60     "warn-on-skipped-patterns",
  61     cl::desc("Explain why a pattern was skipped for inclusion "
  62              "in the GlobalISel selector"),
  63     cl::init(false), cl::cat(GlobalISelEmitterCat));
  64
  65 namespace {
  66 //===- Helper functions ---------------------------------------------------===//
  67
  68 /// This class stands in for LLT wherever we want to tablegen-erate an
  69 /// equivalent at compiler run-time.
  70 class LLTCodeGen {
  71 private:
  72   LLT Ty;
  73
  74 public:
  75   LLTCodeGen(const LLT &Ty) : Ty(Ty) {}
  76
  77   void emitCxxConstructorCall(raw_ostream &OS) const {
  78     if (Ty.isScalar()) {
  79       OS << "LLT::scalar(" << Ty.getSizeInBits() << ")";
  80       return;
  81     }
  82     if (Ty.isVector()) {
  83       OS << "LLT::vector(" << Ty.getNumElements() << ", " << Ty.getScalarSizeInBits()
  84          << ")";
  85       return;
  86     }
  87     llvm_unreachable("Unhandled LLT");
  88   }
  89
  90   const LLT &get() const { return Ty; }
  91 };
  92
  93 class InstructionMatcher;
  94 /// Convert an MVT to an equivalent LLT if possible, or the invalid LLT() for
  95 /// MVTs that don't map cleanly to an LLT (e.g., iPTR, *any, ...).
  96 static Optional<LLTCodeGen> MVTToLLT(MVT::SimpleValueType SVT) {
  97   MVT VT(SVT);
  98   if (VT.isVector() && VT.getVectorNumElements() != 1)
  99     return LLTCodeGen(LLT::vector(VT.getVectorNumElements(), VT.getScalarSizeInBits()));
 100   if (VT.isInteger() || VT.isFloatingPoint())
 101     return LLTCodeGen(LLT::scalar(VT.getSizeInBits()));
 102   return None;
 103 }
 104
 105 static std::string explainPredicates(const TreePatternNode *N) {
 106   std::string Explanation = "";
 107   StringRef Separator = "";
 108   for (const auto &P : N->getPredicateFns()) {
 109     Explanation +=
 110         (Separator + P.getOrigPatFragRecord()->getRecord()->getName()).str();
 111     if (P.isAlwaysTrue())
 112       Explanation += " always-true";
 113     if (P.isImmediatePattern())
 114       Explanation += " immediate";
 115   }
 116   return Explanation;
 117 }
 118
 119 std::string explainOperator(Record *Operator) {
 120   if (Operator->isSubClassOf("SDNode"))
 121     return " (" + Operator->getValueAsString("Opcode") + ")";
 122
 123   if (Operator->isSubClassOf("Intrinsic"))
 124     return (" (Operator is an Intrinsic, " + Operator->getName() + ")").str();
 125
 126   return " (Operator not understood)";
 127 }
 128
 129 /// Helper function to let the emitter report skip reason error messages.
 130 static Error failedImport(const Twine &Reason) {
 131   return make_error<StringError>(Reason, inconvertibleErrorCode());
 132 }
 133
 134 static Error isTrivialOperatorNode(const TreePatternNode *N) {
 135   std::string Explanation = "";
 136   std::string Separator = "";
 137   if (N->isLeaf()) {
 138     Explanation = "Is a leaf";
 139     Separator = ", ";
 140   }
 141
 142   if (N->hasAnyPredicate()) {
 143     Explanation = Separator + "Has a predicate (" + explainPredicates(N) + ")";
 144     Separator = ", ";
 145   }
 146
 147   if (N->getTransformFn()) {
 148     Explanation += Separator + "Has a transform function";
 149     Separator = ", ";
 150   }
 151
 152   if (!N->isLeaf() && !N->hasAnyPredicate() && !N->getTransformFn())
 153     return Error::success();
 154
 155   return failedImport(Explanation);
 156 }
 157
 158 //===- Matchers -----------------------------------------------------------===//
 159
 160 class OperandMatcher;
 161 class MatchAction;
 162
 163 /// Generates code to check that a match rule matches.
 164 class RuleMatcher {
 165   /// A list of matchers that all need to succeed for the current rule to match.
 166   /// FIXME: This currently supports a single match position but could be
 167   /// extended to support multiple positions to support div/rem fusion or
 168   /// load-multiple instructions.
 169   std::vector<std::unique_ptr<InstructionMatcher>> Matchers;
 170
 171   /// A list of actions that need to be taken when all predicates in this rule
 172   /// have succeeded.
 173   std::vector<std::unique_ptr<MatchAction>> Actions;
 174
 175   /// A map of instruction matchers to the local variables created by
 176   /// emitCxxCaptureStmts().
 177   std::map<const InstructionMatcher *, std::string> InsnVariableNames;
 178
 179   /// ID for the next instruction variable defined with defineInsnVar()
 180   unsigned NextInsnVarID;
 181
 182   std::vector<Record *> RequiredFeatures;
 183
 184 public:
 185   RuleMatcher()
 186       : Matchers(), Actions(), InsnVariableNames(), NextInsnVarID(0) {}
 187   RuleMatcher(RuleMatcher &&Other) = default;
 188   RuleMatcher &operator=(RuleMatcher &&Other) = default;
 189
 190   InstructionMatcher &addInstructionMatcher();
 191   void addRequiredFeature(Record *Feature);
 192
 193   template <class Kind, class... Args> Kind &addAction(Args &&... args);
 194
 195   std::string defineInsnVar(raw_ostream &OS, const InstructionMatcher &Matcher,
 196                             StringRef Value);
 197   StringRef getInsnVarName(const InstructionMatcher &InsnMatcher) const;
 198
 199   void emitCxxCapturedInsnList(raw_ostream &OS);
 200   void emitCxxCaptureStmts(raw_ostream &OS, StringRef Expr);
 201
 202 void emit(raw_ostream &OS, SubtargetFeatureInfoMap SubtargetFeatures);
 203
 204 /// Compare the priority of this object and B.
 205 ///
 206 /// Returns true if this object is more important than B.
 207 bool isHigherPriorityThan(const RuleMatcher &B) const;
 208
 209 /// Report the maximum number of temporary operands needed by the rule
 210 /// matcher.
 211 unsigned countRendererFns() const;
 212
 213 // FIXME: Remove this as soon as possible
 214 InstructionMatcher &insnmatcher_front() const { return *Matchers.front(); }
 215 };
 216
 217 template <class PredicateTy> class PredicateListMatcher {
 218 private:
 219   typedef std::vector<std::unique_ptr<PredicateTy>> PredicateVec;
 220   PredicateVec Predicates;
 221
 222 public:
 223   /// Construct a new operand predicate and add it to the matcher.
 224   template <class Kind, class... Args>
 225   Kind &addPredicate(Args&&... args) {
 226     Predicates.emplace_back(
 227         llvm::make_unique<Kind>(std::forward<Args>(args)...));
 228     return *static_cast<Kind *>(Predicates.back().get());
 229   }
 230
 231   typename PredicateVec::const_iterator predicates_begin() const { return Predicates.begin(); }
 232   typename PredicateVec::const_iterator predicates_end() const { return Predicates.end(); }
 233   iterator_range<typename PredicateVec::const_iterator> predicates() const {
 234     return make_range(predicates_begin(), predicates_end());
 235   }
 236   typename PredicateVec::size_type predicates_size() const { return Predicates.size(); }
 237
 238   /// Emit a C++ expression that tests whether all the predicates are met.
 239   template <class... Args>
 240   void emitCxxPredicateListExpr(raw_ostream &OS, Args &&... args) const {
 241     if (Predicates.empty()) {
 242       OS << "true";
 243       return;
 244     }
 245
 246     StringRef Separator = "";
 247     for (const auto &Predicate : predicates()) {
 248       OS << Separator << "(";
 249       Predicate->emitCxxPredicateExpr(OS, std::forward<Args>(args)...);
 250       OS << ")";
 251       Separator = " &&\n";
 252     }
 253   }
 254 };
 255
 256 /// Generates code to check a predicate of an operand.
 257 ///
 258 /// Typical predicates include:
 259 /// * Operand is a particular register.
 260 /// * Operand is assigned a particular register bank.
 261 /// * Operand is an MBB.
 262 class OperandPredicateMatcher {
 263 public:
 264   /// This enum is used for RTTI and also defines the priority that is given to
 265   /// the predicate when generating the matcher code. Kinds with higher priority
 266   /// must be tested first.
 267   ///
 268   /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter
 269   /// but OPM_Int must have priority over OPM_RegBank since constant integers
 270   /// are represented by a virtual register defined by a G_CONSTANT instruction.
 271   enum PredicateKind {
 272     OPM_ComplexPattern,
 273     OPM_Instruction,
 274     OPM_Int,
 275     OPM_LLT,
 276     OPM_RegBank,
 277     OPM_MBB,
 278   };
 279
 280 protected:
 281   PredicateKind Kind;
 282
 283 public:
 284   OperandPredicateMatcher(PredicateKind Kind) : Kind(Kind) {}
 285   virtual ~OperandPredicateMatcher() {}
 286
 287   PredicateKind getKind() const { return Kind; }
 288
 289   /// Return the OperandMatcher for the specified operand or nullptr if there
 290   /// isn't one by that name in this operand predicate matcher.
 291   ///
 292   /// InstructionOperandMatcher is the only subclass that can return non-null
 293   /// for this.
 294   virtual Optional<const OperandMatcher *>
 295   getOptionalOperand(StringRef SymbolicName) const {
 296     assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
 297     return None;
 298   }
 299
 300   /// Emit C++ statements to capture instructions into local variables.
 301   ///
 302   /// Only InstructionOperandMatcher needs to do anything for this method.
 303   virtual void emitCxxCaptureStmts(raw_ostream &OS, RuleMatcher &Rule,
 304                                    StringRef Expr) const {}
 305
 306   /// Emit a C++ expression that checks the predicate for the given operand.
 307   virtual void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
 308                                     StringRef OperandExpr) const = 0;
 309
 310   /// Compare the priority of this object and B.
 311   ///
 312   /// Returns true if this object is more important than B.
 313   virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const {
 314     return Kind < B.Kind;
 315   };
 316
 317   /// Report the maximum number of temporary operands needed by the predicate
 318   /// matcher.
 319   virtual unsigned countRendererFns() const { return 0; }
 320 };
 321
 322 /// Generates code to check that an operand is a particular LLT.
 323 class LLTOperandMatcher : public OperandPredicateMatcher {
 324 protected:
 325   LLTCodeGen Ty;
 326
 327 public:
 328   LLTOperandMatcher(const LLTCodeGen &Ty)
 329       : OperandPredicateMatcher(OPM_LLT), Ty(Ty) {}
 330
 331   static bool classof(const OperandPredicateMatcher *P) {
 332     return P->getKind() == OPM_LLT;
 333   }
 334
 335   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
 336                             StringRef OperandExpr) const override {
 337     OS << "MRI.getType(" << OperandExpr << ".getReg()) == (";
 338     Ty.emitCxxConstructorCall(OS);
 339     OS << ")";
 340   }
 341 };
 342
 343 /// Generates code to check that an operand is a particular target constant.
 344 class ComplexPatternOperandMatcher : public OperandPredicateMatcher {
 345 protected:
 346   const OperandMatcher &Operand;
 347   const Record &TheDef;
 348
 349   unsigned getAllocatedTemporariesBaseID() const;
 350
 351 public:
 352   ComplexPatternOperandMatcher(const OperandMatcher &Operand,
 353                                const Record &TheDef)
 354       : OperandPredicateMatcher(OPM_ComplexPattern), Operand(Operand),
 355         TheDef(TheDef) {}
 356
 357   static bool classof(const OperandPredicateMatcher *P) {
 358     return P->getKind() == OPM_ComplexPattern;
 359   }
 360
 361   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
 362                             StringRef OperandExpr) const override {
 363     unsigned ID = getAllocatedTemporariesBaseID();
 364     OS << "(Renderer" << ID << " = " << TheDef.getValueAsString("MatcherFn")
 365        << "(" << OperandExpr << "))";
 366   }
 367
 368   unsigned countRendererFns() const override {
 369     return 1;
 370   }
 371 };
 372
 373 /// Generates code to check that an operand is in a particular register bank.
 374 class RegisterBankOperandMatcher : public OperandPredicateMatcher {
 375 protected:
 376   const CodeGenRegisterClass &RC;
 377
 378 public:
 379   RegisterBankOperandMatcher(const CodeGenRegisterClass &RC)
 380       : OperandPredicateMatcher(OPM_RegBank), RC(RC) {}
 381
 382   static bool classof(const OperandPredicateMatcher *P) {
 383     return P->getKind() == OPM_RegBank;
 384   }
 385
 386   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
 387                             StringRef OperandExpr) const override {
 388     OS << "(&RBI.getRegBankFromRegClass(" << RC.getQualifiedName()
 389        << "RegClass) == RBI.getRegBank(" << OperandExpr
 390        << ".getReg(), MRI, TRI))";
 391   }
 392 };
 393
 394 /// Generates code to check that an operand is a basic block.
 395 class MBBOperandMatcher : public OperandPredicateMatcher {
 396 public:
 397   MBBOperandMatcher() : OperandPredicateMatcher(OPM_MBB) {}
 398
 399   static bool classof(const OperandPredicateMatcher *P) {
 400     return P->getKind() == OPM_MBB;
 401   }
 402
 403   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
 404                             StringRef OperandExpr) const override {
 405     OS << OperandExpr << ".isMBB()";
 406   }
 407 };
 408
 409 /// Generates code to check that an operand is a particular int.
 410 class IntOperandMatcher : public OperandPredicateMatcher {
 411 protected:
 412   int64_t Value;
 413
 414 public:
 415   IntOperandMatcher(int64_t Value)
 416       : OperandPredicateMatcher(OPM_Int), Value(Value) {}
 417
 418   static bool classof(const OperandPredicateMatcher *P) {
 419     return P->getKind() == OPM_Int;
 420   }
 421
 422   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
 423                             StringRef OperandExpr) const override {
 424     OS << "isOperandImmEqual(" << OperandExpr << ", " << Value << ", MRI)";
 425   }
 426 };
 427
 428 /// Generates code to check that a set of predicates match for a particular
 429 /// operand.
 430 class OperandMatcher : public PredicateListMatcher<OperandPredicateMatcher> {
 431 protected:
 432   InstructionMatcher &Insn;
 433   unsigned OpIdx;
 434   std::string SymbolicName;
 435
 436   /// The index of the first temporary variable allocated to this operand. The
 437   /// number of allocated temporaries can be found with
 438   /// countRendererFns().
 439   unsigned AllocatedTemporariesBaseID;
 440
 441 public:
 442   OperandMatcher(InstructionMatcher &Insn, unsigned OpIdx,
 443                  const std::string &SymbolicName,
 444                  unsigned AllocatedTemporariesBaseID)
 445       : Insn(Insn), OpIdx(OpIdx), SymbolicName(SymbolicName),
 446         AllocatedTemporariesBaseID(AllocatedTemporariesBaseID) {}
 447
 448   bool hasSymbolicName() const { return !SymbolicName.empty(); }
 449   const StringRef getSymbolicName() const { return SymbolicName; }
 450   void setSymbolicName(StringRef Name) {
 451     assert(SymbolicName.empty() && "Operand already has a symbolic name");
 452     SymbolicName = Name;
 453   }
 454   unsigned getOperandIndex() const { return OpIdx; }
 455
 456   std::string getOperandExpr(StringRef InsnVarName) const {
 457     return (InsnVarName + ".getOperand(" + llvm::to_string(OpIdx) + ")").str();
 458   }
 459
 460   Optional<const OperandMatcher *>
 461   getOptionalOperand(StringRef DesiredSymbolicName) const {
 462     assert(!DesiredSymbolicName.empty() && "Cannot lookup unnamed operand");
 463     if (DesiredSymbolicName == SymbolicName)
 464       return this;
 465     for (const auto &OP : predicates()) {
 466       const auto &MaybeOperand = OP->getOptionalOperand(DesiredSymbolicName);
 467       if (MaybeOperand.hasValue())
 468         return MaybeOperand.getValue();
 469     }
 470     return None;
 471   }
 472
 473   InstructionMatcher &getInstructionMatcher() const { return Insn; }
 474
 475   /// Emit C++ statements to capture instructions into local variables.
 476   void emitCxxCaptureStmts(raw_ostream &OS, RuleMatcher &Rule,
 477                            StringRef OperandExpr) const {
 478     for (const auto &Predicate : predicates())
 479       Predicate->emitCxxCaptureStmts(OS, Rule, OperandExpr);
 480   }
 481
 482   /// Emit a C++ expression that tests whether the instruction named in
 483   /// InsnVarName matches all the predicate and all the operands.
 484   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
 485                             StringRef InsnVarName) const {
 486     OS << "(/* ";
 487     if (SymbolicName.empty())
 488       OS << "Operand " << OpIdx;
 489     else
 490       OS << SymbolicName;
 491     OS << " */ ";
 492     emitCxxPredicateListExpr(OS, Rule, getOperandExpr(InsnVarName));
 493     OS << ")";
 494   }
 495
 496   /// Compare the priority of this object and B.
 497   ///
 498   /// Returns true if this object is more important than B.
 499   bool isHigherPriorityThan(const OperandMatcher &B) const {
 500     // Operand matchers involving more predicates have higher priority.
 501     if (predicates_size() > B.predicates_size())
 502       return true;
 503     if (predicates_size() < B.predicates_size())
 504       return false;
 505
 506     // This assumes that predicates are added in a consistent order.
 507     for (const auto &Predicate : zip(predicates(), B.predicates())) {
 508       if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate)))
 509         return true;
 510       if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate)))
 511         return false;
 512     }
 513
 514     return false;
 515   };
 516
 517   /// Report the maximum number of temporary operands needed by the operand
 518   /// matcher.
 519   unsigned countRendererFns() const {
 520     return std::accumulate(
 521         predicates().begin(), predicates().end(), 0,
 522         [](unsigned A,
 523            const std::unique_ptr<OperandPredicateMatcher> &Predicate) {
 524           return A + Predicate->countRendererFns();
 525         });
 526   }
 527
 528   unsigned getAllocatedTemporariesBaseID() const {
 529     return AllocatedTemporariesBaseID;
 530   }
 531 };
 532
 533 unsigned ComplexPatternOperandMatcher::getAllocatedTemporariesBaseID() const {
 534   return Operand.getAllocatedTemporariesBaseID();
 535 }
 536
 537 /// Generates code to check a predicate on an instruction.
 538 ///
 539 /// Typical predicates include:
 540 /// * The opcode of the instruction is a particular value.
 541 /// * The nsw/nuw flag is/isn't set.
 542 class InstructionPredicateMatcher {
 543 protected:
 544   /// This enum is used for RTTI and also defines the priority that is given to
 545   /// the predicate when generating the matcher code. Kinds with higher priority
 546   /// must be tested first.
 547   enum PredicateKind {
 548     IPM_Opcode,
 549   };
 550
 551   PredicateKind Kind;
 552
 553 public:
 554   InstructionPredicateMatcher(PredicateKind Kind) : Kind(Kind) {}
 555   virtual ~InstructionPredicateMatcher() {}
 556
 557   PredicateKind getKind() const { return Kind; }
 558
 559   /// Emit a C++ expression that tests whether the instruction named in
 560   /// InsnVarName matches the predicate.
 561   virtual void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
 562                                     StringRef InsnVarName) const = 0;
 563
 564   /// Compare the priority of this object and B.
 565   ///
 566   /// Returns true if this object is more important than B.
 567   virtual bool isHigherPriorityThan(const InstructionPredicateMatcher &B) const {
 568     return Kind < B.Kind;
 569   };
 570
 571   /// Report the maximum number of temporary operands needed by the predicate
 572   /// matcher.
 573   virtual unsigned countRendererFns() const { return 0; }
 574 };
 575
 576 /// Generates code to check the opcode of an instruction.
 577 class InstructionOpcodeMatcher : public InstructionPredicateMatcher {
 578 protected:
 579   const CodeGenInstruction *I;
 580
 581 public:
 582   InstructionOpcodeMatcher(const CodeGenInstruction *I)
 583       : InstructionPredicateMatcher(IPM_Opcode), I(I) {}
 584
 585   static bool classof(const InstructionPredicateMatcher *P) {
 586     return P->getKind() == IPM_Opcode;
 587   }
 588
 589   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
 590                             StringRef InsnVarName) const override {
 591     OS << InsnVarName << ".getOpcode() == " << I->Namespace
 592        << "::" << I->TheDef->getName();
 593   }
 594
 595   /// Compare the priority of this object and B.
 596   ///
 597   /// Returns true if this object is more important than B.
 598   bool isHigherPriorityThan(const InstructionPredicateMatcher &B) const override {
 599     if (InstructionPredicateMatcher::isHigherPriorityThan(B))
 600       return true;
 601     if (B.InstructionPredicateMatcher::isHigherPriorityThan(*this))
 602       return false;
 603
 604     // Prioritize opcodes for cosmetic reasons in the generated source. Although
 605     // this is cosmetic at the moment, we may want to drive a similar ordering
 606     // using instruction frequency information to improve compile time.
 607     if (const InstructionOpcodeMatcher *BO =
 608             dyn_cast<InstructionOpcodeMatcher>(&B))
 609       return I->TheDef->getName() < BO->I->TheDef->getName();
 610
 611     return false;
 612   };
 613 };
 614
 615 /// Generates code to check that a set of predicates and operands match for a
 616 /// particular instruction.
 617 ///
 618 /// Typical predicates include:
 619 /// * Has a specific opcode.
 620 /// * Has an nsw/nuw flag or doesn't.
 621 class InstructionMatcher
 622     : public PredicateListMatcher<InstructionPredicateMatcher> {
 623 protected:
 624   typedef std::vector<std::unique_ptr<OperandMatcher>> OperandVec;
 625
 626   /// The operands to match. All rendered operands must be present even if the
 627   /// condition is always true.
 628   OperandVec Operands;
 629
 630 public:
 631   /// Add an operand to the matcher.
 632   OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName,
 633                              unsigned AllocatedTemporariesBaseID) {
 634     Operands.emplace_back(new OperandMatcher(*this, OpIdx, SymbolicName,
 635                                              AllocatedTemporariesBaseID));
 636     return *Operands.back();
 637   }
 638
 639   OperandMatcher &getOperand(unsigned OpIdx) {
 640     auto I = std::find_if(Operands.begin(), Operands.end(),
 641                           [&OpIdx](const std::unique_ptr<OperandMatcher> &X) {
 642                             return X->getOperandIndex() == OpIdx;
 643                           });
 644     if (I != Operands.end())
 645       return **I;
 646     llvm_unreachable("Failed to lookup operand");
 647   }
 648
 649   Optional<const OperandMatcher *>
 650   getOptionalOperand(StringRef SymbolicName) const {
 651     assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
 652     for (const auto &Operand : Operands) {
 653       const auto &OM = Operand->getOptionalOperand(SymbolicName);
 654       if (OM.hasValue())
 655         return OM.getValue();
 656     }
 657     return None;
 658   }
 659
 660   const OperandMatcher &getOperand(StringRef SymbolicName) const {
 661     Optional<const OperandMatcher *>OM = getOptionalOperand(SymbolicName);
 662     if (OM.hasValue())
 663       return *OM.getValue();
 664     llvm_unreachable("Failed to lookup operand");
 665   }
 666
 667   unsigned getNumOperands() const { return Operands.size(); }
 668   OperandVec::iterator operands_begin() { return Operands.begin(); }
 669   OperandVec::iterator operands_end() { return Operands.end(); }
 670   iterator_range<OperandVec::iterator> operands() {
 671     return make_range(operands_begin(), operands_end());
 672   }
 673   OperandVec::const_iterator operands_begin() const { return Operands.begin(); }
 674   OperandVec::const_iterator operands_end() const { return Operands.end(); }
 675   iterator_range<OperandVec::const_iterator> operands() const {
 676     return make_range(operands_begin(), operands_end());
 677   }
 678
 679   /// Emit C++ statements to check the shape of the match and capture
 680   /// instructions into local variables.
 681   void emitCxxCaptureStmts(raw_ostream &OS, RuleMatcher &Rule, StringRef Expr) {
 682     OS << "if (" << Expr << ".getNumOperands() < " << getNumOperands() << ")\n"
 683        << "  return false;\n";
 684     for (const auto &Operand : Operands) {
 685       Operand->emitCxxCaptureStmts(OS, Rule, Operand->getOperandExpr(Expr));
 686     }
 687   }
 688
 689   /// Emit a C++ expression that tests whether the instruction named in
 690   /// InsnVarName matches all the predicates and all the operands.
 691   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
 692                             StringRef InsnVarName) const {
 693     emitCxxPredicateListExpr(OS, Rule, InsnVarName);
 694     for (const auto &Operand : Operands) {
 695       OS << " &&\n(";
 696       Operand->emitCxxPredicateExpr(OS, Rule, InsnVarName);
 697       OS << ")";
 698     }
 699   }
 700
 701   /// Compare the priority of this object and B.
 702   ///
 703   /// Returns true if this object is more important than B.
 704   bool isHigherPriorityThan(const InstructionMatcher &B) const {
 705     // Instruction matchers involving more operands have higher priority.
 706     if (Operands.size() > B.Operands.size())
 707       return true;
 708     if (Operands.size() < B.Operands.size())
 709       return false;
 710
 711     for (const auto &Predicate : zip(predicates(), B.predicates())) {
 712       if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate)))
 713         return true;
 714       if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate)))
 715         return false;
 716     }
 717
 718     for (const auto &Operand : zip(Operands, B.Operands)) {
 719       if (std::get<0>(Operand)->isHigherPriorityThan(*std::get<1>(Operand)))
 720         return true;
 721       if (std::get<1>(Operand)->isHigherPriorityThan(*std::get<0>(Operand)))
 722         return false;
 723     }
 724
 725     return false;
 726   };
 727
 728   /// Report the maximum number of temporary operands needed by the instruction
 729   /// matcher.
 730   unsigned countRendererFns() const {
 731     return std::accumulate(predicates().begin(), predicates().end(), 0,
 732                            [](unsigned A,
 733                               const std::unique_ptr<InstructionPredicateMatcher>
 734                                   &Predicate) {
 735                              return A + Predicate->countRendererFns();
 736                            }) +
 737            std::accumulate(
 738                Operands.begin(), Operands.end(), 0,
 739                [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) {
 740                  return A + Operand->countRendererFns();
 741                });
 742   }
 743 };
 744
 745 /// Generates code to check that the operand is a register defined by an
 746 /// instruction that matches the given instruction matcher.
 747 ///
 748 /// For example, the pattern:
 749 ///   (set $dst, (G_MUL (G_ADD $src1, $src2), $src3))
 750 /// would use an InstructionOperandMatcher for operand 1 of the G_MUL to match
 751 /// the:
 752 ///   (G_ADD $src1, $src2)
 753 /// subpattern.
 754 class InstructionOperandMatcher : public OperandPredicateMatcher {
 755 protected:
 756   std::unique_ptr<InstructionMatcher> InsnMatcher;
 757
 758 public:
 759   InstructionOperandMatcher()
 760       : OperandPredicateMatcher(OPM_Instruction),
 761         InsnMatcher(new InstructionMatcher()) {}
 762
 763   static bool classof(const OperandPredicateMatcher *P) {
 764     return P->getKind() == OPM_Instruction;
 765   }
 766
 767   InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; }
 768
 769   Optional<const OperandMatcher *>
 770   getOptionalOperand(StringRef SymbolicName) const override {
 771     assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
 772     return InsnMatcher->getOptionalOperand(SymbolicName);
 773   }
 774
 775   void emitCxxCaptureStmts(raw_ostream &OS, RuleMatcher &Rule,
 776                            StringRef OperandExpr) const override {
 777     OS << "if (!" << OperandExpr + ".isReg())\n"
 778        << "  return false;\n"
 779        << "if (TRI.isPhysicalRegister(" << OperandExpr + ".getReg()))\n"
 780        << "  return false;\n";
 781     std::string InsnVarName = Rule.defineInsnVar(
 782         OS, *InsnMatcher,
 783         ("*MRI.getVRegDef(" + OperandExpr + ".getReg())").str());
 784     InsnMatcher->emitCxxCaptureStmts(OS, Rule, InsnVarName);
 785   }
 786
 787   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
 788                             StringRef OperandExpr) const override {
 789     OperandExpr = Rule.getInsnVarName(*InsnMatcher);
 790     OS << "(";
 791     InsnMatcher->emitCxxPredicateExpr(OS, Rule, OperandExpr);
 792     OS << ")\n";
 793   }
 794 };
 795
 796 //===- Actions ------------------------------------------------------------===//
 797 class OperandRenderer {
 798 public:
 799   enum RendererKind { OR_Copy, OR_Imm, OR_Register, OR_ComplexPattern };
 800
 801 protected:
 802   RendererKind Kind;
 803
 804 public:
 805   OperandRenderer(RendererKind Kind) : Kind(Kind) {}
 806   virtual ~OperandRenderer() {}
 807
 808   RendererKind getKind() const { return Kind; }
 809
 810   virtual void emitCxxRenderStmts(raw_ostream &OS, RuleMatcher &Rule) const = 0;
 811 };
 812
 813 /// A CopyRenderer emits code to copy a single operand from an existing
 814 /// instruction to the one being built.
 815 class CopyRenderer : public OperandRenderer {
 816 protected:
 817   /// The matcher for the instruction that this operand is copied from.
 818   /// This provides the facility for looking up an a operand by it's name so
 819   /// that it can be used as a source for the instruction being built.
 820   const InstructionMatcher &Matched;
 821   /// The name of the operand.
 822   const StringRef SymbolicName;
 823
 824 public:
 825   CopyRenderer(const InstructionMatcher &Matched, StringRef SymbolicName)
 826       : OperandRenderer(OR_Copy), Matched(Matched), SymbolicName(SymbolicName) {
 827   }
 828
 829   static bool classof(const OperandRenderer *R) {
 830     return R->getKind() == OR_Copy;
 831   }
 832
 833   const StringRef getSymbolicName() const { return SymbolicName; }
 834
 835   void emitCxxRenderStmts(raw_ostream &OS, RuleMatcher &Rule) const override {
 836     const OperandMatcher &Operand = Matched.getOperand(SymbolicName);
 837     StringRef InsnVarName =
 838         Rule.getInsnVarName(Operand.getInstructionMatcher());
 839     std::string OperandExpr = Operand.getOperandExpr(InsnVarName);
 840     OS << "    MIB.add(" << OperandExpr << "/*" << SymbolicName << "*/);\n";
 841   }
 842 };
 843
 844 /// Adds a specific physical register to the instruction being built.
 845 /// This is typically useful for WZR/XZR on AArch64.
 846 class AddRegisterRenderer : public OperandRenderer {
 847 protected:
 848   const Record *RegisterDef;
 849
 850 public:
 851   AddRegisterRenderer(const Record *RegisterDef)
 852       : OperandRenderer(OR_Register), RegisterDef(RegisterDef) {}
 853
 854   static bool classof(const OperandRenderer *R) {
 855     return R->getKind() == OR_Register;
 856   }
 857
 858   void emitCxxRenderStmts(raw_ostream &OS, RuleMatcher &Rule) const override {
 859     OS << "    MIB.addReg(" << (RegisterDef->getValue("Namespace")
 860                                     ? RegisterDef->getValueAsString("Namespace")
 861                                     : "")
 862        << "::" << RegisterDef->getName() << ");\n";
 863   }
 864 };
 865
 866 /// Adds a specific immediate to the instruction being built.
 867 class ImmRenderer : public OperandRenderer {
 868 protected:
 869   int64_t Imm;
 870
 871 public:
 872   ImmRenderer(int64_t Imm)
 873       : OperandRenderer(OR_Imm), Imm(Imm) {}
 874
 875   static bool classof(const OperandRenderer *R) {
 876     return R->getKind() == OR_Imm;
 877   }
 878
 879   void emitCxxRenderStmts(raw_ostream &OS, RuleMatcher &Rule) const override {
 880     OS << "    MIB.addImm(" << Imm << ");\n";
 881   }
 882 };
 883
 884 /// Adds operands by calling a renderer function supplied by the ComplexPattern
 885 /// matcher function.
 886 class RenderComplexPatternOperand : public OperandRenderer {
 887 private:
 888   const Record &TheDef;
 889   /// The name of the operand.
 890   const StringRef SymbolicName;
 891   /// The renderer number. This must be unique within a rule since it's used to
 892   /// identify a temporary variable to hold the renderer function.
 893   unsigned RendererID;
 894
 895   unsigned getNumOperands() const {
 896     return TheDef.getValueAsDag("Operands")->getNumArgs();
 897   }
 898
 899 public:
 900   RenderComplexPatternOperand(const Record &TheDef, StringRef SymbolicName,
 901                               unsigned RendererID)
 902       : OperandRenderer(OR_ComplexPattern), TheDef(TheDef),
 903         SymbolicName(SymbolicName), RendererID(RendererID) {}
 904
 905   static bool classof(const OperandRenderer *R) {
 906     return R->getKind() == OR_ComplexPattern;
 907   }
 908
 909   void emitCxxRenderStmts(raw_ostream &OS, RuleMatcher &Rule) const override {
 910     OS << "Renderer" << RendererID << "(MIB);\n";
 911   }
 912 };
 913
 914 /// An action taken when all Matcher predicates succeeded for a parent rule.
 915 ///
 916 /// Typical actions include:
 917 /// * Changing the opcode of an instruction.
 918 /// * Adding an operand to an instruction.
 919 class MatchAction {
 920 public:
 921   virtual ~MatchAction() {}
 922
 923   /// Emit the C++ statements to implement the action.
 924   ///
 925   /// \param RecycleVarName If given, it's an instruction to recycle. The
 926   ///                       requirements on the instruction vary from action to
 927   ///                       action.
 928   virtual void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
 929                                   StringRef RecycleVarName) const = 0;
 930 };
 931
 932 /// Generates a comment describing the matched rule being acted upon.
 933 class DebugCommentAction : public MatchAction {
 934 private:
 935   const PatternToMatch &P;
 936
 937 public:
 938   DebugCommentAction(const PatternToMatch &P) : P(P) {}
 939
 940   void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
 941                           StringRef RecycleVarName) const override {
 942     OS << "// " << *P.getSrcPattern() << "  =>  " << *P.getDstPattern() << "\n";
 943   }
 944 };
 945
 946 /// Generates code to build an instruction or mutate an existing instruction
 947 /// into the desired instruction when this is possible.
 948 class BuildMIAction : public MatchAction {
 949 private:
 950   const CodeGenInstruction *I;
 951   const InstructionMatcher &Matched;
 952   std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers;
 953
 954   /// True if the instruction can be built solely by mutating the opcode.
 955   bool canMutate() const {
 956     if (OperandRenderers.size() != Matched.getNumOperands())
 957       return false;
 958
 959     for (const auto &Renderer : enumerate(OperandRenderers)) {
 960       if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) {
 961         const OperandMatcher &OM = Matched.getOperand(Copy->getSymbolicName());
 962         if (&Matched != &OM.getInstructionMatcher() ||
 963             OM.getOperandIndex() != Renderer.index())
 964           return false;
 965       } else
 966         return false;
 967     }
 968
 969     return true;
 970   }
 971
 972 public:
 973   BuildMIAction(const CodeGenInstruction *I, const InstructionMatcher &Matched)
 974       : I(I), Matched(Matched) {}
 975
 976   template <class Kind, class... Args>
 977   Kind &addRenderer(Args&&... args) {
 978     OperandRenderers.emplace_back(
 979         llvm::make_unique<Kind>(std::forward<Args>(args)...));
 980     return *static_cast<Kind *>(OperandRenderers.back().get());
 981   }
 982
 983   void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
 984                           StringRef RecycleVarName) const override {
 985     if (canMutate()) {
 986       OS << "    " << RecycleVarName << ".setDesc(TII.get(" << I->Namespace
 987          << "::" << I->TheDef->getName() << "));\n";
 988
 989       if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) {
 990         OS << "    auto MIB = MachineInstrBuilder(MF, &" << RecycleVarName
 991            << ");\n";
 992
 993         for (auto Def : I->ImplicitDefs) {
 994           auto Namespace = Def->getValue("Namespace")
 995                                ? Def->getValueAsString("Namespace")
 996                                : "";
 997           OS << "    MIB.addDef(" << Namespace << "::" << Def->getName()
 998              << ", RegState::Implicit);\n";
 999         }
1000         for (auto Use : I->ImplicitUses) {
1001           auto Namespace = Use->getValue("Namespace")
1002                                ? Use->getValueAsString("Namespace")
1003                                : "";
1004           OS << "    MIB.addUse(" << Namespace << "::" << Use->getName()
1005              << ", RegState::Implicit);\n";
1006         }
1007       }
1008
1009       OS << "    MachineInstr &NewI = " << RecycleVarName << ";\n";
1010       return;
1011     }
1012
1013     // TODO: Simple permutation looks like it could be almost as common as
1014     //       mutation due to commutative operations.
1015
1016     OS << "MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, "
1017           "I.getDebugLoc(), TII.get("
1018        << I->Namespace << "::" << I->TheDef->getName() << "));\n";
1019     for (const auto &Renderer : OperandRenderers)
1020       Renderer->emitCxxRenderStmts(OS, Rule);
1021     OS << "    for (const auto *FromMI : ";
1022     Rule.emitCxxCapturedInsnList(OS);
1023     OS << ")\n";
1024     OS << "      for (const auto &MMO : FromMI->memoperands())\n";
1025     OS << "        MIB.addMemOperand(MMO);\n";
1026     OS << "    " << RecycleVarName << ".eraseFromParent();\n";
1027     OS << "    MachineInstr &NewI = *MIB;\n";
1028   }
1029 };
1030
1031 InstructionMatcher &RuleMatcher::addInstructionMatcher() {
1032   Matchers.emplace_back(new InstructionMatcher());
1033   return *Matchers.back();
1034 }
1035
1036 void RuleMatcher::addRequiredFeature(Record *Feature) {
1037   RequiredFeatures.push_back(Feature);
1038 }
1039
1040 template <class Kind, class... Args>
1041 Kind &RuleMatcher::addAction(Args &&... args) {
1042   Actions.emplace_back(llvm::make_unique<Kind>(std::forward<Args>(args)...));
1043   return *static_cast<Kind *>(Actions.back().get());
1044 }
1045
1046 std::string RuleMatcher::defineInsnVar(raw_ostream &OS,
1047                                        const InstructionMatcher &Matcher,
1048                                        StringRef Value) {
1049   std::string InsnVarName = "MI" + llvm::to_string(NextInsnVarID++);
1050   OS << "MachineInstr &" << InsnVarName << " = " << Value << ";\n";
1051   InsnVariableNames[&Matcher] = InsnVarName;
1052   return InsnVarName;
1053 }
1054
1055 StringRef RuleMatcher::getInsnVarName(const InstructionMatcher &InsnMatcher) const {
1056   const auto &I = InsnVariableNames.find(&InsnMatcher);
1057   if (I != InsnVariableNames.end())
1058     return I->second;
1059   llvm_unreachable("Matched Insn was not captured in a local variable");
1060 }
1061
1062 /// Emit a C++ initializer_list containing references to every matched instruction.
1063 void RuleMatcher::emitCxxCapturedInsnList(raw_ostream &OS) {
1064   SmallVector<StringRef, 2> Names;
1065   for (const auto &Pair : InsnVariableNames)
1066     Names.push_back(Pair.second);
1067   std::sort(Names.begin(), Names.end());
1068
1069   OS << "{";
1070   for (const auto &Name : Names)
1071     OS << "&" << Name << ", ";
1072   OS << "}";
1073 }
1074
1075 /// Emit C++ statements to check the shape of the match and capture
1076 /// instructions into local variables.
1077 void RuleMatcher::emitCxxCaptureStmts(raw_ostream &OS, StringRef Expr) {
1078   assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
1079   std::string InsnVarName = defineInsnVar(OS, *Matchers.front(), Expr);
1080   Matchers.front()->emitCxxCaptureStmts(OS, *this, InsnVarName);
1081 }
1082
1083 void RuleMatcher::emit(raw_ostream &OS,
1084                        SubtargetFeatureInfoMap SubtargetFeatures) {
1085   if (Matchers.empty())
1086     llvm_unreachable("Unexpected empty matcher!");
1087
1088   // The representation supports rules that require multiple roots such as:
1089   //    %ptr(p0) = ...
1090   //    %elt0(s32) = G_LOAD %ptr
1091   //    %1(p0) = G_ADD %ptr, 4
1092   //    %elt1(s32) = G_LOAD p0 %1
1093   // which could be usefully folded into:
1094   //    %ptr(p0) = ...
1095   //    %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr
1096   // on some targets but we don't need to make use of that yet.
1097   assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
1098
1099   OS << "if (";
1100   OS << "[&]() {\n";
1101   if (!RequiredFeatures.empty()) {
1102     OS << "  PredicateBitset ExpectedFeatures = {";
1103     StringRef Separator = "";
1104     for (const auto &Predicate : RequiredFeatures) {
1105       const auto &I = SubtargetFeatures.find(Predicate);
1106       assert(I != SubtargetFeatures.end() && "Didn't import predicate?");
1107       OS << Separator << I->second.getEnumBitName();
1108       Separator = ", ";
1109     }
1110     OS << "};\n";
1111     OS << "if ((AvailableFeatures & ExpectedFeatures) != ExpectedFeatures)\n"
1112        << "  return false;\n";
1113   }
1114
1115   emitCxxCaptureStmts(OS, "I");
1116
1117   OS << "    if (";
1118   Matchers.front()->emitCxxPredicateExpr(OS, *this,
1119                                          getInsnVarName(*Matchers.front()));
1120   OS << ") {\n";
1121
1122   // We must also check if it's safe to fold the matched instructions.
1123   if (InsnVariableNames.size() >= 2) {
1124     for (const auto &Pair : InsnVariableNames) {
1125       // Skip the root node since it isn't moving anywhere. Everything else is
1126       // sinking to meet it.
1127       if (Pair.first == Matchers.front().get())
1128         continue;
1129
1130       // Reject the difficult cases until we have a more accurate check.
1131       OS << "      if (!isObviouslySafeToFold(" << Pair.second
1132          << ")) return false;\n";
1133
1134       // FIXME: Emit checks to determine it's _actually_ safe to fold and/or
1135       //        account for unsafe cases.
1136       //
1137       //        Example:
1138       //          MI1--> %0 = ...
1139       //                 %1 = ... %0
1140       //          MI0--> %2 = ... %0
1141       //          It's not safe to erase MI1. We currently handle this by not
1142       //          erasing %0 (even when it's dead).
1143       //
1144       //        Example:
1145       //          MI1--> %0 = load volatile @a
1146       //                 %1 = load volatile @a
1147       //          MI0--> %2 = ... %0
1148       //          It's not safe to sink %0's def past %1. We currently handle
1149       //          this by rejecting all loads.
1150       //
1151       //        Example:
1152       //          MI1--> %0 = load @a
1153       //                 %1 = store @a
1154       //          MI0--> %2 = ... %0
1155       //          It's not safe to sink %0's def past %1. We currently handle
1156       //          this by rejecting all loads.
1157       //
1158       //        Example:
1159       //                   G_CONDBR %cond, @BB1
1160       //                 BB0:
1161       //          MI1-->   %0 = load @a
1162       //                   G_BR @BB1
1163       //                 BB1:
1164       //          MI0-->   %2 = ... %0
1165       //          It's not always safe to sink %0 across control flow. In this
1166       //          case it may introduce a memory fault. We currentl handle this
1167       //          by rejecting all loads.
1168     }
1169   }
1170
1171   for (const auto &MA : Actions) {
1172     MA->emitCxxActionStmts(OS, *this, "I");
1173   }
1174
1175   OS << "      constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);\n";
1176   OS << "      return true;\n";
1177   OS << "    }\n";
1178   OS << "    return false;\n";
1179   OS << "  }()) { return true; }\n\n";
1180 }
1181
1182 bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
1183   // Rules involving more match roots have higher priority.
1184   if (Matchers.size() > B.Matchers.size())
1185     return true;
1186   if (Matchers.size() < B.Matchers.size())
1187     return false;
1188
1189   for (const auto &Matcher : zip(Matchers, B.Matchers)) {
1190     if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher)))
1191       return true;
1192     if (std::get<1>(Matcher)->isHigherPriorityThan(*std::get<0>(Matcher)))
1193       return false;
1194   }
1195
1196   return false;
1197 }
1198
1199 unsigned RuleMatcher::countRendererFns() const {
1200   return std::accumulate(
1201       Matchers.begin(), Matchers.end(), 0,
1202       [](unsigned A, const std::unique_ptr<InstructionMatcher> &Matcher) {
1203         return A + Matcher->countRendererFns();
1204       });
1205 }
1206
1207 //===- GlobalISelEmitter class --------------------------------------------===//
1208
1209 class GlobalISelEmitter {
1210 public:
1211   explicit GlobalISelEmitter(RecordKeeper &RK);
1212   void run(raw_ostream &OS);
1213
1214 private:
1215   const RecordKeeper &RK;
1216   const CodeGenDAGPatterns CGP;
1217   const CodeGenTarget &Target;
1218
1219   /// Keep track of the equivalence between SDNodes and Instruction.
1220   /// This is defined using 'GINodeEquiv' in the target description.
1221   DenseMap<Record *, const CodeGenInstruction *> NodeEquivs;
1222
1223   /// Keep track of the equivalence between ComplexPattern's and
1224   /// GIComplexOperandMatcher. Map entries are specified by subclassing
1225   /// GIComplexPatternEquiv.
1226   DenseMap<const Record *, const Record *> ComplexPatternEquivs;
1227
1228   // Map of predicates to their subtarget features.
1229   SubtargetFeatureInfoMap SubtargetFeatures;
1230
1231   void gatherNodeEquivs();
1232   const CodeGenInstruction *findNodeEquiv(Record *N) const;
1233
1234   Error importRulePredicates(RuleMatcher &M, ArrayRef<Init *> Predicates);
1235   Expected<InstructionMatcher &>
1236   createAndImportSelDAGMatcher(InstructionMatcher &InsnMatcher,
1237                                const TreePatternNode *Src) const;
1238   Error importChildMatcher(InstructionMatcher &InsnMatcher,
1239                            TreePatternNode *SrcChild, unsigned OpIdx,
1240                            unsigned &TempOpIdx) const;
1241   Expected<BuildMIAction &> createAndImportInstructionRenderer(
1242       RuleMatcher &M, const TreePatternNode *Dst,
1243       const InstructionMatcher &InsnMatcher) const;
1244   Error importExplicitUseRenderer(BuildMIAction &DstMIBuilder,
1245                                   TreePatternNode *DstChild,
1246                                   const InstructionMatcher &InsnMatcher) const;
1247   Error importDefaultOperandRenderers(BuildMIAction &DstMIBuilder,
1248                                       DagInit *DefaultOps) const;
1249   Error
1250   importImplicitDefRenderers(BuildMIAction &DstMIBuilder,
1251                              const std::vector<Record *> &ImplicitDefs) const;
1252
1253   /// Analyze pattern \p P, returning a matcher for it if possible.
1254   /// Otherwise, return an Error explaining why we don't support it.
1255   Expected<RuleMatcher> runOnPattern(const PatternToMatch &P);
1256
1257   void declareSubtargetFeature(Record *Predicate);
1258 };
1259
1260 void GlobalISelEmitter::gatherNodeEquivs() {
1261   assert(NodeEquivs.empty());
1262   for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
1263     NodeEquivs[Equiv->getValueAsDef("Node")] =
1264         &Target.getInstruction(Equiv->getValueAsDef("I"));
1265
1266   assert(ComplexPatternEquivs.empty());
1267   for (Record *Equiv : RK.getAllDerivedDefinitions("GIComplexPatternEquiv")) {
1268     Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
1269     if (!SelDAGEquiv)
1270       continue;
1271     ComplexPatternEquivs[SelDAGEquiv] = Equiv;
1272  }
1273 }
1274
1275 const CodeGenInstruction *GlobalISelEmitter::findNodeEquiv(Record *N) const {
1276   return NodeEquivs.lookup(N);
1277 }
1278
1279 GlobalISelEmitter::GlobalISelEmitter(RecordKeeper &RK)
1280     : RK(RK), CGP(RK), Target(CGP.getTargetInfo()) {}
1281
1282 //===- Emitter ------------------------------------------------------------===//
1283
1284 Error
1285 GlobalISelEmitter::importRulePredicates(RuleMatcher &M,
1286                                         ArrayRef<Init *> Predicates) {
1287   for (const Init *Predicate : Predicates) {
1288     const DefInit *PredicateDef = static_cast<const DefInit *>(Predicate);
1289     declareSubtargetFeature(PredicateDef->getDef());
1290     M.addRequiredFeature(PredicateDef->getDef());
1291   }
1292
1293   return Error::success();
1294 }
1295
1296 Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher(
1297     InstructionMatcher &InsnMatcher, const TreePatternNode *Src) const {
1298   // Start with the defined operands (i.e., the results of the root operator).
1299   if (Src->getExtTypes().size() > 1)
1300     return failedImport("Src pattern has multiple results");
1301
1302   auto SrcGIOrNull = findNodeEquiv(Src->getOperator());
1303   if (!SrcGIOrNull)
1304     return failedImport("Pattern operator lacks an equivalent Instruction" +
1305                         explainOperator(Src->getOperator()));
1306   auto &SrcGI = *SrcGIOrNull;
1307
1308   // The operators look good: match the opcode and mutate it to the new one.
1309   InsnMatcher.addPredicate<InstructionOpcodeMatcher>(&SrcGI);
1310
1311   unsigned OpIdx = 0;
1312   unsigned TempOpIdx = 0;
1313   for (const EEVT::TypeSet &Ty : Src->getExtTypes()) {
1314     auto OpTyOrNone = MVTToLLT(Ty.getConcrete());
1315
1316     if (!OpTyOrNone)
1317       return failedImport(
1318           "Result of Src pattern operator has an unsupported type");
1319
1320     // Results don't have a name unless they are the root node. The caller will
1321     // set the name if appropriate.
1322     OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
1323     OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
1324   }
1325
1326   // Match the used operands (i.e. the children of the operator).
1327   for (unsigned i = 0, e = Src->getNumChildren(); i != e; ++i) {
1328     if (auto Error = importChildMatcher(InsnMatcher, Src->getChild(i), OpIdx++,
1329                                         TempOpIdx))
1330       return std::move(Error);
1331   }
1332
1333   return InsnMatcher;
1334 }
1335
1336 Error GlobalISelEmitter::importChildMatcher(InstructionMatcher &InsnMatcher,
1337                                             TreePatternNode *SrcChild,
1338                                             unsigned OpIdx,
1339                                             unsigned &TempOpIdx) const {
1340   OperandMatcher &OM =
1341       InsnMatcher.addOperand(OpIdx, SrcChild->getName(), TempOpIdx);
1342
1343   if (SrcChild->hasAnyPredicate())
1344     return failedImport("Src pattern child has predicate (" +
1345                         explainPredicates(SrcChild) + ")");
1346
1347   ArrayRef<EEVT::TypeSet> ChildTypes = SrcChild->getExtTypes();
1348   if (ChildTypes.size() != 1)
1349     return failedImport("Src pattern child has multiple results");
1350
1351   // Check MBB's before the type check since they are not a known type.
1352   if (!SrcChild->isLeaf()) {
1353     if (SrcChild->getOperator()->isSubClassOf("SDNode")) {
1354       auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator());
1355       if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
1356         OM.addPredicate<MBBOperandMatcher>();
1357         return Error::success();
1358       }
1359     }
1360   }
1361
1362   auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete());
1363   if (!OpTyOrNone)
1364     return failedImport("Src operand has an unsupported type");
1365   OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
1366
1367   // Check for nested instructions.
1368   if (!SrcChild->isLeaf()) {
1369     // Map the node to a gMIR instruction.
1370     InstructionOperandMatcher &InsnOperand =
1371         OM.addPredicate<InstructionOperandMatcher>();
1372     auto InsnMatcherOrError =
1373         createAndImportSelDAGMatcher(InsnOperand.getInsnMatcher(), SrcChild);
1374     if (auto Error = InsnMatcherOrError.takeError())
1375       return Error;
1376
1377     return Error::success();
1378   }
1379
1380   // Check for constant immediates.
1381   if (auto *ChildInt = dyn_cast<IntInit>(SrcChild->getLeafValue())) {
1382     OM.addPredicate<IntOperandMatcher>(ChildInt->getValue());
1383     return Error::success();
1384   }
1385
1386   // Check for def's like register classes or ComplexPattern's.
1387   if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
1388     auto *ChildRec = ChildDefInit->getDef();
1389
1390     // Check for register classes.
1391     if (ChildRec->isSubClassOf("RegisterClass")) {
1392       OM.addPredicate<RegisterBankOperandMatcher>(
1393           Target.getRegisterClass(ChildRec));
1394       return Error::success();
1395     }
1396
1397     if (ChildRec->isSubClassOf("RegisterOperand")) {
1398       OM.addPredicate<RegisterBankOperandMatcher>(
1399           Target.getRegisterClass(ChildRec->getValueAsDef("RegClass")));
1400       return Error::success();
1401     }
1402
1403     // Check for ComplexPattern's.
1404     if (ChildRec->isSubClassOf("ComplexPattern")) {
1405       const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
1406       if (ComplexPattern == ComplexPatternEquivs.end())
1407         return failedImport("SelectionDAG ComplexPattern (" +
1408                             ChildRec->getName() + ") not mapped to GlobalISel");
1409
1410       OM.addPredicate<ComplexPatternOperandMatcher>(OM,
1411                                                     *ComplexPattern->second);
1412       TempOpIdx++;
1413       return Error::success();
1414     }
1415
1416     if (ChildRec->isSubClassOf("ImmLeaf")) {
1417       return failedImport(
1418           "Src pattern child def is an unsupported tablegen class (ImmLeaf)");
1419     }
1420
1421     return failedImport(
1422         "Src pattern child def is an unsupported tablegen class");
1423   }
1424
1425   return failedImport("Src pattern child is an unsupported kind");
1426 }
1427
1428 Error GlobalISelEmitter::importExplicitUseRenderer(
1429     BuildMIAction &DstMIBuilder, TreePatternNode *DstChild,
1430     const InstructionMatcher &InsnMatcher) const {
1431   // The only non-leaf child we accept is 'bb': it's an operator because
1432   // BasicBlockSDNode isn't inline, but in MI it's just another operand.
1433   if (!DstChild->isLeaf()) {
1434     if (DstChild->getOperator()->isSubClassOf("SDNode")) {
1435       auto &ChildSDNI = CGP.getSDNodeInfo(DstChild->getOperator());
1436       if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
1437         DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher,
1438                                                DstChild->getName());
1439         return Error::success();
1440       }
1441     }
1442     return failedImport("Dst pattern child isn't a leaf node or an MBB");
1443   }
1444
1445   // Otherwise, we're looking for a bog-standard RegisterClass operand.
1446   if (DstChild->hasAnyPredicate())
1447     return failedImport("Dst pattern child has predicate (" +
1448                         explainPredicates(DstChild) + ")");
1449
1450   if (auto *ChildDefInit = dyn_cast<DefInit>(DstChild->getLeafValue())) {
1451     auto *ChildRec = ChildDefInit->getDef();
1452
1453     ArrayRef<EEVT::TypeSet> ChildTypes = DstChild->getExtTypes();
1454     if (ChildTypes.size() != 1)
1455       return failedImport("Dst pattern child has multiple results");
1456
1457     auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete());
1458     if (!OpTyOrNone)
1459       return failedImport("Dst operand has an unsupported type");
1460
1461     if (ChildRec->isSubClassOf("Register")) {
1462       DstMIBuilder.addRenderer<AddRegisterRenderer>(ChildRec);
1463       return Error::success();
1464     }
1465
1466     if (ChildRec->isSubClassOf("RegisterClass") ||
1467         ChildRec->isSubClassOf("RegisterOperand")) {
1468       DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher, DstChild->getName());
1469       return Error::success();
1470     }
1471
1472     if (ChildRec->isSubClassOf("ComplexPattern")) {
1473       const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
1474       if (ComplexPattern == ComplexPatternEquivs.end())
1475         return failedImport(
1476             "SelectionDAG ComplexPattern not mapped to GlobalISel");
1477
1478       const OperandMatcher &OM = InsnMatcher.getOperand(DstChild->getName());
1479       DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
1480           *ComplexPattern->second, DstChild->getName(),
1481           OM.getAllocatedTemporariesBaseID());
1482       return Error::success();
1483     }
1484
1485     if (ChildRec->isSubClassOf("SDNodeXForm"))
1486       return failedImport("Dst pattern child def is an unsupported tablegen "
1487                           "class (SDNodeXForm)");
1488
1489     return failedImport(
1490         "Dst pattern child def is an unsupported tablegen class");
1491   }
1492
1493   return failedImport("Dst pattern child is an unsupported kind");
1494 }
1495
1496 Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
1497     RuleMatcher &M, const TreePatternNode *Dst,
1498     const InstructionMatcher &InsnMatcher) const {
1499   Record *DstOp = Dst->getOperator();
1500   if (!DstOp->isSubClassOf("Instruction")) {
1501     if (DstOp->isSubClassOf("ValueType"))
1502       return failedImport(
1503           "Pattern operator isn't an instruction (it's a ValueType)");
1504     return failedImport("Pattern operator isn't an instruction");
1505   }
1506   auto &DstI = Target.getInstruction(DstOp);
1507
1508   auto &DstMIBuilder = M.addAction<BuildMIAction>(&DstI, InsnMatcher);
1509
1510   // Render the explicit defs.
1511   for (unsigned I = 0; I < DstI.Operands.NumDefs; ++I) {
1512     const auto &DstIOperand = DstI.Operands[I];
1513     DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher, DstIOperand.Name);
1514   }
1515
1516   // Render the explicit uses.
1517   unsigned Child = 0;
1518   unsigned DstINumUses = DstI.Operands.size() - DstI.Operands.NumDefs;
1519   unsigned NumDefaultOps = 0;
1520   for (unsigned I = 0; I != DstINumUses; ++I) {
1521     const auto &DstIOperand = DstI.Operands[DstI.Operands.NumDefs + I];
1522
1523     // If the operand has default values, introduce them now.
1524     // FIXME: Until we have a decent test case that dictates we should do
1525     // otherwise, we're going to assume that operands with default values cannot
1526     // be specified in the patterns. Therefore, adding them will not cause us to
1527     // end up with too many rendered operands.
1528     if (DstIOperand.Rec->isSubClassOf("OperandWithDefaultOps")) {
1529       DagInit *DefaultOps = DstIOperand.Rec->getValueAsDag("DefaultOps");
1530       if (auto Error = importDefaultOperandRenderers(DstMIBuilder, DefaultOps))
1531         return std::move(Error);
1532       ++NumDefaultOps;
1533       continue;
1534     }
1535
1536     if (auto Error = importExplicitUseRenderer(
1537             DstMIBuilder, Dst->getChild(Child), InsnMatcher))
1538       return std::move(Error);
1539     ++Child;
1540   }
1541
1542   if (NumDefaultOps + Dst->getNumChildren() != DstINumUses)
1543     return failedImport("Expected " + llvm::to_string(DstINumUses) +
1544                         " used operands but found " +
1545                         llvm::to_string(Dst->getNumChildren()) +
1546                         " explicit ones and " + llvm::to_string(NumDefaultOps) +
1547                         " default ones");
1548
1549   return DstMIBuilder;
1550 }
1551
1552 Error GlobalISelEmitter::importDefaultOperandRenderers(
1553     BuildMIAction &DstMIBuilder, DagInit *DefaultOps) const {
1554   for (const auto *DefaultOp : DefaultOps->args()) {
1555     // Look through ValueType operators.
1556     if (const DagInit *DefaultDagOp = dyn_cast<DagInit>(DefaultOp)) {
1557       if (const DefInit *DefaultDagOperator =
1558               dyn_cast<DefInit>(DefaultDagOp->getOperator())) {
1559         if (DefaultDagOperator->getDef()->isSubClassOf("ValueType"))
1560           DefaultOp = DefaultDagOp->getArg(0);
1561       }
1562     }
1563
1564     if (const DefInit *DefaultDefOp = dyn_cast<DefInit>(DefaultOp)) {
1565       DstMIBuilder.addRenderer<AddRegisterRenderer>(DefaultDefOp->getDef());
1566       continue;
1567     }
1568
1569     if (const IntInit *DefaultIntOp = dyn_cast<IntInit>(DefaultOp)) {
1570       DstMIBuilder.addRenderer<ImmRenderer>(DefaultIntOp->getValue());
1571       continue;
1572     }
1573
1574     return failedImport("Could not add default op");
1575   }
1576
1577   return Error::success();
1578 }
1579
1580 Error GlobalISelEmitter::importImplicitDefRenderers(
1581     BuildMIAction &DstMIBuilder,
1582     const std::vector<Record *> &ImplicitDefs) const {
1583   if (!ImplicitDefs.empty())
1584     return failedImport("Pattern defines a physical register");
1585   return Error::success();
1586 }
1587
1588 Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
1589   // Keep track of the matchers and actions to emit.
1590   RuleMatcher M;
1591   M.addAction<DebugCommentAction>(P);
1592
1593   if (auto Error = importRulePredicates(M, P.getPredicates()->getValues()))
1594     return std::move(Error);
1595
1596   // Next, analyze the pattern operators.
1597   TreePatternNode *Src = P.getSrcPattern();
1598   TreePatternNode *Dst = P.getDstPattern();
1599
1600   // If the root of either pattern isn't a simple operator, ignore it.
1601   if (auto Err = isTrivialOperatorNode(Dst))
1602     return failedImport("Dst pattern root isn't a trivial operator (" +
1603                         toString(std::move(Err)) + ")");
1604   if (auto Err = isTrivialOperatorNode(Src))
1605     return failedImport("Src pattern root isn't a trivial operator (" +
1606                         toString(std::move(Err)) + ")");
1607
1608   // Start with the defined operands (i.e., the results of the root operator).
1609   Record *DstOp = Dst->getOperator();
1610   if (!DstOp->isSubClassOf("Instruction"))
1611     return failedImport("Pattern operator isn't an instruction");
1612
1613   auto &DstI = Target.getInstruction(DstOp);
1614   if (DstI.Operands.NumDefs != Src->getExtTypes().size())
1615     return failedImport("Src pattern results and dst MI defs are different (" +
1616                         to_string(Src->getExtTypes().size()) + " def(s) vs " +
1617                         to_string(DstI.Operands.NumDefs) + " def(s))");
1618
1619   InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher();
1620   auto InsnMatcherOrError = createAndImportSelDAGMatcher(InsnMatcherTemp, Src);
1621   if (auto Error = InsnMatcherOrError.takeError())
1622     return std::move(Error);
1623   InstructionMatcher &InsnMatcher = InsnMatcherOrError.get();
1624
1625   // The root of the match also has constraints on the register bank so that it
1626   // matches the result instruction.
1627   unsigned OpIdx = 0;
1628   for (const EEVT::TypeSet &Ty : Src->getExtTypes()) {
1629     (void)Ty;
1630
1631     const auto &DstIOperand = DstI.Operands[OpIdx];
1632     Record *DstIOpRec = DstIOperand.Rec;
1633     if (DstIOpRec->isSubClassOf("RegisterOperand"))
1634       DstIOpRec = DstIOpRec->getValueAsDef("RegClass");
1635     if (!DstIOpRec->isSubClassOf("RegisterClass"))
1636       return failedImport("Dst MI def isn't a register class");
1637
1638     OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
1639     OM.setSymbolicName(DstIOperand.Name);
1640     OM.addPredicate<RegisterBankOperandMatcher>(
1641         Target.getRegisterClass(DstIOpRec));
1642     ++OpIdx;
1643   }
1644
1645   auto DstMIBuilderOrError =
1646       createAndImportInstructionRenderer(M, Dst, InsnMatcher);
1647   if (auto Error = DstMIBuilderOrError.takeError())
1648     return std::move(Error);
1649   BuildMIAction &DstMIBuilder = DstMIBuilderOrError.get();
1650
1651   // Render the implicit defs.
1652   // These are only added to the root of the result.
1653   if (auto Error = importImplicitDefRenderers(DstMIBuilder, P.getDstRegs()))
1654     return std::move(Error);
1655
1656   // We're done with this pattern!  It's eligible for GISel emission; return it.
1657   ++NumPatternImported;
1658   return std::move(M);
1659 }
1660
1661 void GlobalISelEmitter::run(raw_ostream &OS) {
1662   // Track the GINodeEquiv definitions.
1663   gatherNodeEquivs();
1664
1665   emitSourceFileHeader(("Global Instruction Selector for the " +
1666                        Target.getName() + " target").str(), OS);
1667   std::vector<RuleMatcher> Rules;
1668   // Look through the SelectionDAG patterns we found, possibly emitting some.
1669   for (const PatternToMatch &Pat : CGP.ptms()) {
1670     ++NumPatternTotal;
1671     auto MatcherOrErr = runOnPattern(Pat);
1672
1673     // The pattern analysis can fail, indicating an unsupported pattern.
1674     // Report that if we've been asked to do so.
1675     if (auto Err = MatcherOrErr.takeError()) {
1676       if (WarnOnSkippedPatterns) {
1677         PrintWarning(Pat.getSrcRecord()->getLoc(),
1678                      "Skipped pattern: " + toString(std::move(Err)));
1679       } else {
1680         consumeError(std::move(Err));
1681       }
1682       ++NumPatternImportsSkipped;
1683       continue;
1684     }
1685
1686     Rules.push_back(std::move(MatcherOrErr.get()));
1687   }
1688
1689   std::stable_sort(Rules.begin(), Rules.end(),
1690             [&](const RuleMatcher &A, const RuleMatcher &B) {
1691               if (A.isHigherPriorityThan(B)) {
1692                 assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
1693                                                      "and less important at "
1694                                                      "the same time");
1695                 return true;
1696               }
1697               return false;
1698             });
1699
1700   unsigned MaxTemporaries = 0;
1701   for (const auto &Rule : Rules)
1702     MaxTemporaries = std::max(MaxTemporaries, Rule.countRendererFns());
1703
1704   OS << "#ifdef GET_GLOBALISEL_PREDICATE_BITSET\n"
1705      << "const unsigned MAX_SUBTARGET_PREDICATES = " << SubtargetFeatures.size()
1706      << ";\n"
1707      << "using PredicateBitset = "
1708         "llvm::PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;\n"
1709      << "#endif // ifdef GET_GLOBALISEL_PREDICATE_BITSET\n\n";
1710
1711   OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n";
1712   for (unsigned I = 0; I < MaxTemporaries; ++I)
1713     OS << "  mutable ComplexRendererFn Renderer" << I << ";\n";
1714   OS << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n";
1715
1716   OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n";
1717   for (unsigned I = 0; I < MaxTemporaries; ++I)
1718     OS << ", Renderer" << I << "(nullptr)\n";
1719   OS << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";
1720
1721   OS << "#ifdef GET_GLOBALISEL_IMPL\n";
1722   SubtargetFeatureInfo::emitSubtargetFeatureBitEnumeration(SubtargetFeatures,
1723                                                            OS);
1724
1725   // Separate subtarget features by how often they must be recomputed.
1726   SubtargetFeatureInfoMap ModuleFeatures;
1727   std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
1728                std::inserter(ModuleFeatures, ModuleFeatures.end()),
1729                [](const SubtargetFeatureInfoMap::value_type &X) {
1730                  return !X.second.mustRecomputePerFunction();
1731                });
1732   SubtargetFeatureInfoMap FunctionFeatures;
1733   std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
1734                std::inserter(FunctionFeatures, FunctionFeatures.end()),
1735                [](const SubtargetFeatureInfoMap::value_type &X) {
1736                  return X.second.mustRecomputePerFunction();
1737                });
1738
1739   SubtargetFeatureInfo::emitComputeAvailableFeatures(
1740       Target.getName(), "InstructionSelector", "computeAvailableModuleFeatures",
1741       ModuleFeatures, OS);
1742   SubtargetFeatureInfo::emitComputeAvailableFeatures(
1743       Target.getName(), "InstructionSelector",
1744       "computeAvailableFunctionFeatures", FunctionFeatures, OS,
1745       "const MachineFunction *MF");
1746
1747   OS << "bool " << Target.getName()
1748      << "InstructionSelector::selectImpl(MachineInstr &I) const {\n"
1749      << "  MachineFunction &MF = *I.getParent()->getParent();\n"
1750      << "  const MachineRegisterInfo &MRI = MF.getRegInfo();\n"
1751      << "  // FIXME: This should be computed on a per-function basis rather than per-insn.\n"
1752      << "  AvailableFunctionFeatures = computeAvailableFunctionFeatures(&STI, &MF);\n"
1753      << "  const PredicateBitset AvailableFeatures = getAvailableFeatures();\n";
1754
1755   for (auto &Rule : Rules) {
1756     Rule.emit(OS, SubtargetFeatures);
1757     ++NumPatternEmitted;
1758   }
1759
1760   OS << "  return false;\n"
1761      << "}\n"
1762      << "#endif // ifdef GET_GLOBALISEL_IMPL\n";
1763
1764   OS << "#ifdef GET_GLOBALISEL_PREDICATES_DECL\n"
1765      << "PredicateBitset AvailableModuleFeatures;\n"
1766      << "mutable PredicateBitset AvailableFunctionFeatures;\n"
1767      << "PredicateBitset getAvailableFeatures() const {\n"
1768      << "  return AvailableModuleFeatures | AvailableFunctionFeatures;\n"
1769      << "}\n"
1770      << "PredicateBitset\n"
1771      << "computeAvailableModuleFeatures(const " << Target.getName()
1772      << "Subtarget *Subtarget) const;\n"
1773      << "PredicateBitset\n"
1774      << "computeAvailableFunctionFeatures(const " << Target.getName()
1775      << "Subtarget *Subtarget,\n"
1776      << "                                 const MachineFunction *MF) const;\n"
1777      << "#endif // ifdef GET_GLOBALISEL_PREDICATES_DECL\n";
1778
1779   OS << "#ifdef GET_GLOBALISEL_PREDICATES_INIT\n"
1780      << "AvailableModuleFeatures(computeAvailableModuleFeatures(&STI)),\n"
1781      << "AvailableFunctionFeatures()\n"
1782      << "#endif // ifdef GET_GLOBALISEL_PREDICATES_INIT\n";
1783 }
1784
1785 void GlobalISelEmitter::declareSubtargetFeature(Record *Predicate) {
1786   if (SubtargetFeatures.count(Predicate) == 0)
1787     SubtargetFeatures.emplace(
1788         Predicate, SubtargetFeatureInfo(Predicate, SubtargetFeatures.size()));
1789 }
1790
1791 } // end anonymous namespace
1792
1793 //===----------------------------------------------------------------------===//
1794
1795 namespace llvm {
1796 void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS) {
1797   GlobalISelEmitter(RK).run(OS);
1798 }
1799 } // End llvm namespace