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     std::string InsnVarName = Rule.defineInsnVar(
 780         OS, *InsnMatcher,
 781         ("*MRI.getVRegDef(" + OperandExpr + ".getReg())").str());
 782     InsnMatcher->emitCxxCaptureStmts(OS, Rule, InsnVarName);
 783   }
 784
 785   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
 786                             StringRef OperandExpr) const override {
 787     OperandExpr = Rule.getInsnVarName(*InsnMatcher);
 788     OS << "(";
 789     InsnMatcher->emitCxxPredicateExpr(OS, Rule, OperandExpr);
 790     OS << ")\n";
 791   }
 792 };
 793
 794 //===- Actions ------------------------------------------------------------===//
 795 class OperandRenderer {
 796 public:
 797   enum RendererKind { OR_Copy, OR_Imm, OR_Register, OR_ComplexPattern };
 798
 799 protected:
 800   RendererKind Kind;
 801
 802 public:
 803   OperandRenderer(RendererKind Kind) : Kind(Kind) {}
 804   virtual ~OperandRenderer() {}
 805
 806   RendererKind getKind() const { return Kind; }
 807
 808   virtual void emitCxxRenderStmts(raw_ostream &OS, RuleMatcher &Rule) const = 0;
 809 };
 810
 811 /// A CopyRenderer emits code to copy a single operand from an existing
 812 /// instruction to the one being built.
 813 class CopyRenderer : public OperandRenderer {
 814 protected:
 815   /// The matcher for the instruction that this operand is copied from.
 816   /// This provides the facility for looking up an a operand by it's name so
 817   /// that it can be used as a source for the instruction being built.
 818   const InstructionMatcher &Matched;
 819   /// The name of the operand.
 820   const StringRef SymbolicName;
 821
 822 public:
 823   CopyRenderer(const InstructionMatcher &Matched, StringRef SymbolicName)
 824       : OperandRenderer(OR_Copy), Matched(Matched), SymbolicName(SymbolicName) {
 825   }
 826
 827   static bool classof(const OperandRenderer *R) {
 828     return R->getKind() == OR_Copy;
 829   }
 830
 831   const StringRef getSymbolicName() const { return SymbolicName; }
 832
 833   void emitCxxRenderStmts(raw_ostream &OS, RuleMatcher &Rule) const override {
 834     const OperandMatcher &Operand = Matched.getOperand(SymbolicName);
 835     StringRef InsnVarName =
 836         Rule.getInsnVarName(Operand.getInstructionMatcher());
 837     std::string OperandExpr = Operand.getOperandExpr(InsnVarName);
 838     OS << "    MIB.add(" << OperandExpr << "/*" << SymbolicName << "*/);\n";
 839   }
 840 };
 841
 842 /// Adds a specific physical register to the instruction being built.
 843 /// This is typically useful for WZR/XZR on AArch64.
 844 class AddRegisterRenderer : public OperandRenderer {
 845 protected:
 846   const Record *RegisterDef;
 847
 848 public:
 849   AddRegisterRenderer(const Record *RegisterDef)
 850       : OperandRenderer(OR_Register), RegisterDef(RegisterDef) {}
 851
 852   static bool classof(const OperandRenderer *R) {
 853     return R->getKind() == OR_Register;
 854   }
 855
 856   void emitCxxRenderStmts(raw_ostream &OS, RuleMatcher &Rule) const override {
 857     OS << "    MIB.addReg(" << (RegisterDef->getValue("Namespace")
 858                                     ? RegisterDef->getValueAsString("Namespace")
 859                                     : "")
 860        << "::" << RegisterDef->getName() << ");\n";
 861   }
 862 };
 863
 864 /// Adds a specific immediate to the instruction being built.
 865 class ImmRenderer : public OperandRenderer {
 866 protected:
 867   int64_t Imm;
 868
 869 public:
 870   ImmRenderer(int64_t Imm)
 871       : OperandRenderer(OR_Imm), Imm(Imm) {}
 872
 873   static bool classof(const OperandRenderer *R) {
 874     return R->getKind() == OR_Imm;
 875   }
 876
 877   void emitCxxRenderStmts(raw_ostream &OS, RuleMatcher &Rule) const override {
 878     OS << "    MIB.addImm(" << Imm << ");\n";
 879   }
 880 };
 881
 882 /// Adds operands by calling a renderer function supplied by the ComplexPattern
 883 /// matcher function.
 884 class RenderComplexPatternOperand : public OperandRenderer {
 885 private:
 886   const Record &TheDef;
 887   /// The name of the operand.
 888   const StringRef SymbolicName;
 889   /// The renderer number. This must be unique within a rule since it's used to
 890   /// identify a temporary variable to hold the renderer function.
 891   unsigned RendererID;
 892
 893   unsigned getNumOperands() const {
 894     return TheDef.getValueAsDag("Operands")->getNumArgs();
 895   }
 896
 897 public:
 898   RenderComplexPatternOperand(const Record &TheDef, StringRef SymbolicName,
 899                               unsigned RendererID)
 900       : OperandRenderer(OR_ComplexPattern), TheDef(TheDef),
 901         SymbolicName(SymbolicName), RendererID(RendererID) {}
 902
 903   static bool classof(const OperandRenderer *R) {
 904     return R->getKind() == OR_ComplexPattern;
 905   }
 906
 907   void emitCxxRenderStmts(raw_ostream &OS, RuleMatcher &Rule) const override {
 908     OS << "Renderer" << RendererID << "(MIB);\n";
 909   }
 910 };
 911
 912 /// An action taken when all Matcher predicates succeeded for a parent rule.
 913 ///
 914 /// Typical actions include:
 915 /// * Changing the opcode of an instruction.
 916 /// * Adding an operand to an instruction.
 917 class MatchAction {
 918 public:
 919   virtual ~MatchAction() {}
 920
 921   /// Emit the C++ statements to implement the action.
 922   ///
 923   /// \param RecycleVarName If given, it's an instruction to recycle. The
 924   ///                       requirements on the instruction vary from action to
 925   ///                       action.
 926   virtual void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
 927                                   StringRef RecycleVarName) const = 0;
 928 };
 929
 930 /// Generates a comment describing the matched rule being acted upon.
 931 class DebugCommentAction : public MatchAction {
 932 private:
 933   const PatternToMatch &P;
 934
 935 public:
 936   DebugCommentAction(const PatternToMatch &P) : P(P) {}
 937
 938   void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
 939                           StringRef RecycleVarName) const override {
 940     OS << "// " << *P.getSrcPattern() << "  =>  " << *P.getDstPattern() << "\n";
 941   }
 942 };
 943
 944 /// Generates code to build an instruction or mutate an existing instruction
 945 /// into the desired instruction when this is possible.
 946 class BuildMIAction : public MatchAction {
 947 private:
 948   const CodeGenInstruction *I;
 949   const InstructionMatcher &Matched;
 950   std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers;
 951
 952   /// True if the instruction can be built solely by mutating the opcode.
 953   bool canMutate() const {
 954     if (OperandRenderers.size() != Matched.getNumOperands())
 955       return false;
 956
 957     for (const auto &Renderer : enumerate(OperandRenderers)) {
 958       if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) {
 959         const OperandMatcher &OM = Matched.getOperand(Copy->getSymbolicName());
 960         if (&Matched != &OM.getInstructionMatcher() ||
 961             OM.getOperandIndex() != Renderer.index())
 962           return false;
 963       } else
 964         return false;
 965     }
 966
 967     return true;
 968   }
 969
 970 public:
 971   BuildMIAction(const CodeGenInstruction *I, const InstructionMatcher &Matched)
 972       : I(I), Matched(Matched) {}
 973
 974   template <class Kind, class... Args>
 975   Kind &addRenderer(Args&&... args) {
 976     OperandRenderers.emplace_back(
 977         llvm::make_unique<Kind>(std::forward<Args>(args)...));
 978     return *static_cast<Kind *>(OperandRenderers.back().get());
 979   }
 980
 981   void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
 982                           StringRef RecycleVarName) const override {
 983     if (canMutate()) {
 984       OS << "    " << RecycleVarName << ".setDesc(TII.get(" << I->Namespace
 985          << "::" << I->TheDef->getName() << "));\n";
 986
 987       if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) {
 988         OS << "    auto MIB = MachineInstrBuilder(MF, &" << RecycleVarName
 989            << ");\n";
 990
 991         for (auto Def : I->ImplicitDefs) {
 992           auto Namespace = Def->getValue("Namespace")
 993                                ? Def->getValueAsString("Namespace")
 994                                : "";
 995           OS << "    MIB.addDef(" << Namespace << "::" << Def->getName()
 996              << ", RegState::Implicit);\n";
 997         }
 998         for (auto Use : I->ImplicitUses) {
 999           auto Namespace = Use->getValue("Namespace")
1000                                ? Use->getValueAsString("Namespace")
1001                                : "";
1002           OS << "    MIB.addUse(" << Namespace << "::" << Use->getName()
1003              << ", RegState::Implicit);\n";
1004         }
1005       }
1006
1007       OS << "    MachineInstr &NewI = " << RecycleVarName << ";\n";
1008       return;
1009     }
1010
1011     // TODO: Simple permutation looks like it could be almost as common as
1012     //       mutation due to commutative operations.
1013
1014     OS << "MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, "
1015           "I.getDebugLoc(), TII.get("
1016        << I->Namespace << "::" << I->TheDef->getName() << "));\n";
1017     for (const auto &Renderer : OperandRenderers)
1018       Renderer->emitCxxRenderStmts(OS, Rule);
1019     OS << "    for (const auto *FromMI : ";
1020     Rule.emitCxxCapturedInsnList(OS);
1021     OS << ")\n";
1022     OS << "      for (const auto &MMO : FromMI->memoperands())\n";
1023     OS << "        MIB.addMemOperand(MMO);\n";
1024     OS << "    " << RecycleVarName << ".eraseFromParent();\n";
1025     OS << "    MachineInstr &NewI = *MIB;\n";
1026   }
1027 };
1028
1029 InstructionMatcher &RuleMatcher::addInstructionMatcher() {
1030   Matchers.emplace_back(new InstructionMatcher());
1031   return *Matchers.back();
1032 }
1033
1034 void RuleMatcher::addRequiredFeature(Record *Feature) {
1035   RequiredFeatures.push_back(Feature);
1036 }
1037
1038 template <class Kind, class... Args>
1039 Kind &RuleMatcher::addAction(Args &&... args) {
1040   Actions.emplace_back(llvm::make_unique<Kind>(std::forward<Args>(args)...));
1041   return *static_cast<Kind *>(Actions.back().get());
1042 }
1043
1044 std::string RuleMatcher::defineInsnVar(raw_ostream &OS,
1045                                        const InstructionMatcher &Matcher,
1046                                        StringRef Value) {
1047   std::string InsnVarName = "MI" + llvm::to_string(NextInsnVarID++);
1048   OS << "MachineInstr &" << InsnVarName << " = " << Value << ";\n";
1049   InsnVariableNames[&Matcher] = InsnVarName;
1050   return InsnVarName;
1051 }
1052
1053 StringRef RuleMatcher::getInsnVarName(const InstructionMatcher &InsnMatcher) const {
1054   const auto &I = InsnVariableNames.find(&InsnMatcher);
1055   if (I != InsnVariableNames.end())
1056     return I->second;
1057   llvm_unreachable("Matched Insn was not captured in a local variable");
1058 }
1059
1060 /// Emit a C++ initializer_list containing references to every matched instruction.
1061 void RuleMatcher::emitCxxCapturedInsnList(raw_ostream &OS) {
1062   SmallVector<StringRef, 2> Names;
1063   for (const auto &Pair : InsnVariableNames)
1064     Names.push_back(Pair.second);
1065   std::sort(Names.begin(), Names.end());
1066
1067   OS << "{";
1068   for (const auto &Name : Names)
1069     OS << "&" << Name << ", ";
1070   OS << "}";
1071 }
1072
1073 /// Emit C++ statements to check the shape of the match and capture
1074 /// instructions into local variables.
1075 void RuleMatcher::emitCxxCaptureStmts(raw_ostream &OS, StringRef Expr) {
1076   assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
1077   std::string InsnVarName = defineInsnVar(OS, *Matchers.front(), Expr);
1078   Matchers.front()->emitCxxCaptureStmts(OS, *this, InsnVarName);
1079 }
1080
1081 void RuleMatcher::emit(raw_ostream &OS,
1082                        SubtargetFeatureInfoMap SubtargetFeatures) {
1083   if (Matchers.empty())
1084     llvm_unreachable("Unexpected empty matcher!");
1085
1086   // The representation supports rules that require multiple roots such as:
1087   //    %ptr(p0) = ...
1088   //    %elt0(s32) = G_LOAD %ptr
1089   //    %1(p0) = G_ADD %ptr, 4
1090   //    %elt1(s32) = G_LOAD p0 %1
1091   // which could be usefully folded into:
1092   //    %ptr(p0) = ...
1093   //    %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr
1094   // on some targets but we don't need to make use of that yet.
1095   assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
1096
1097   OS << "if (";
1098   OS << "[&]() {\n";
1099   if (!RequiredFeatures.empty()) {
1100     OS << "  PredicateBitset ExpectedFeatures = {";
1101     StringRef Separator = "";
1102     for (const auto &Predicate : RequiredFeatures) {
1103       const auto &I = SubtargetFeatures.find(Predicate);
1104       assert(I != SubtargetFeatures.end() && "Didn't import predicate?");
1105       OS << Separator << I->second.getEnumBitName();
1106       Separator = ", ";
1107     }
1108     OS << "};\n";
1109     OS << "if ((AvailableFeatures & ExpectedFeatures) != ExpectedFeatures)\n"
1110        << "  return false;\n";
1111   }
1112
1113   emitCxxCaptureStmts(OS, "I");
1114
1115   OS << "    if (";
1116   Matchers.front()->emitCxxPredicateExpr(OS, *this,
1117                                          getInsnVarName(*Matchers.front()));
1118   OS << ") {\n";
1119
1120   // We must also check if it's safe to fold the matched instructions.
1121   if (InsnVariableNames.size() >= 2) {
1122     for (const auto &Pair : InsnVariableNames) {
1123       // Skip the root node since it isn't moving anywhere. Everything else is
1124       // sinking to meet it.
1125       if (Pair.first == Matchers.front().get())
1126         continue;
1127
1128       // Reject the difficult cases until we have a more accurate check.
1129       OS << "      if (!isObviouslySafeToFold(" << Pair.second
1130          << ")) return false;\n";
1131
1132       // FIXME: Emit checks to determine it's _actually_ safe to fold and/or
1133       //        account for unsafe cases.
1134       //
1135       //        Example:
1136       //          MI1--> %0 = ...
1137       //                 %1 = ... %0
1138       //          MI0--> %2 = ... %0
1139       //          It's not safe to erase MI1. We currently handle this by not
1140       //          erasing %0 (even when it's dead).
1141       //
1142       //        Example:
1143       //          MI1--> %0 = load volatile @a
1144       //                 %1 = load volatile @a
1145       //          MI0--> %2 = ... %0
1146       //          It's not safe to sink %0's def past %1. We currently handle
1147       //          this by rejecting all loads.
1148       //
1149       //        Example:
1150       //          MI1--> %0 = load @a
1151       //                 %1 = store @a
1152       //          MI0--> %2 = ... %0
1153       //          It's not safe to sink %0's def past %1. We currently handle
1154       //          this by rejecting all loads.
1155       //
1156       //        Example:
1157       //                   G_CONDBR %cond, @BB1
1158       //                 BB0:
1159       //          MI1-->   %0 = load @a
1160       //                   G_BR @BB1
1161       //                 BB1:
1162       //          MI0-->   %2 = ... %0
1163       //          It's not always safe to sink %0 across control flow. In this
1164       //          case it may introduce a memory fault. We currentl handle this
1165       //          by rejecting all loads.
1166     }
1167   }
1168
1169   for (const auto &MA : Actions) {
1170     MA->emitCxxActionStmts(OS, *this, "I");
1171   }
1172
1173   OS << "      constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);\n";
1174   OS << "      return true;\n";
1175   OS << "    }\n";
1176   OS << "    return false;\n";
1177   OS << "  }()) { return true; }\n\n";
1178 }
1179
1180 bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
1181   // Rules involving more match roots have higher priority.
1182   if (Matchers.size() > B.Matchers.size())
1183     return true;
1184   if (Matchers.size() < B.Matchers.size())
1185     return false;
1186
1187   for (const auto &Matcher : zip(Matchers, B.Matchers)) {
1188     if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher)))
1189       return true;
1190     if (std::get<1>(Matcher)->isHigherPriorityThan(*std::get<0>(Matcher)))
1191       return false;
1192   }
1193
1194   return false;
1195 }
1196
1197 unsigned RuleMatcher::countRendererFns() const {
1198   return std::accumulate(
1199       Matchers.begin(), Matchers.end(), 0,
1200       [](unsigned A, const std::unique_ptr<InstructionMatcher> &Matcher) {
1201         return A + Matcher->countRendererFns();
1202       });
1203 }
1204
1205 //===- GlobalISelEmitter class --------------------------------------------===//
1206
1207 class GlobalISelEmitter {
1208 public:
1209   explicit GlobalISelEmitter(RecordKeeper &RK);
1210   void run(raw_ostream &OS);
1211
1212 private:
1213   const RecordKeeper &RK;
1214   const CodeGenDAGPatterns CGP;
1215   const CodeGenTarget &Target;
1216
1217   /// Keep track of the equivalence between SDNodes and Instruction.
1218   /// This is defined using 'GINodeEquiv' in the target description.
1219   DenseMap<Record *, const CodeGenInstruction *> NodeEquivs;
1220
1221   /// Keep track of the equivalence between ComplexPattern's and
1222   /// GIComplexOperandMatcher. Map entries are specified by subclassing
1223   /// GIComplexPatternEquiv.
1224   DenseMap<const Record *, const Record *> ComplexPatternEquivs;
1225
1226   // Map of predicates to their subtarget features.
1227   SubtargetFeatureInfoMap SubtargetFeatures;
1228
1229   void gatherNodeEquivs();
1230   const CodeGenInstruction *findNodeEquiv(Record *N) const;
1231
1232   Error importRulePredicates(RuleMatcher &M, ArrayRef<Init *> Predicates);
1233   Expected<InstructionMatcher &>
1234   createAndImportSelDAGMatcher(InstructionMatcher &InsnMatcher,
1235                                const TreePatternNode *Src) const;
1236   Error importChildMatcher(InstructionMatcher &InsnMatcher,
1237                            TreePatternNode *SrcChild, unsigned OpIdx,
1238                            unsigned &TempOpIdx) const;
1239   Expected<BuildMIAction &> createAndImportInstructionRenderer(
1240       RuleMatcher &M, const TreePatternNode *Dst,
1241       const InstructionMatcher &InsnMatcher) const;
1242   Error importExplicitUseRenderer(BuildMIAction &DstMIBuilder,
1243                                   TreePatternNode *DstChild,
1244                                   const InstructionMatcher &InsnMatcher) const;
1245   Error
1246   importImplicitDefRenderers(BuildMIAction &DstMIBuilder,
1247                              const std::vector<Record *> &ImplicitDefs) const;
1248
1249   /// Analyze pattern \p P, returning a matcher for it if possible.
1250   /// Otherwise, return an Error explaining why we don't support it.
1251   Expected<RuleMatcher> runOnPattern(const PatternToMatch &P);
1252
1253   void declareSubtargetFeature(Record *Predicate);
1254 };
1255
1256 void GlobalISelEmitter::gatherNodeEquivs() {
1257   assert(NodeEquivs.empty());
1258   for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
1259     NodeEquivs[Equiv->getValueAsDef("Node")] =
1260         &Target.getInstruction(Equiv->getValueAsDef("I"));
1261
1262   assert(ComplexPatternEquivs.empty());
1263   for (Record *Equiv : RK.getAllDerivedDefinitions("GIComplexPatternEquiv")) {
1264     Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
1265     if (!SelDAGEquiv)
1266       continue;
1267     ComplexPatternEquivs[SelDAGEquiv] = Equiv;
1268  }
1269 }
1270
1271 const CodeGenInstruction *GlobalISelEmitter::findNodeEquiv(Record *N) const {
1272   return NodeEquivs.lookup(N);
1273 }
1274
1275 GlobalISelEmitter::GlobalISelEmitter(RecordKeeper &RK)
1276     : RK(RK), CGP(RK), Target(CGP.getTargetInfo()) {}
1277
1278 //===- Emitter ------------------------------------------------------------===//
1279
1280 Error
1281 GlobalISelEmitter::importRulePredicates(RuleMatcher &M,
1282                                         ArrayRef<Init *> Predicates) {
1283   for (const Init *Predicate : Predicates) {
1284     const DefInit *PredicateDef = static_cast<const DefInit *>(Predicate);
1285     declareSubtargetFeature(PredicateDef->getDef());
1286     M.addRequiredFeature(PredicateDef->getDef());
1287   }
1288
1289   return Error::success();
1290 }
1291
1292 Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher(
1293     InstructionMatcher &InsnMatcher, const TreePatternNode *Src) const {
1294   // Start with the defined operands (i.e., the results of the root operator).
1295   if (Src->getExtTypes().size() > 1)
1296     return failedImport("Src pattern has multiple results");
1297
1298   auto SrcGIOrNull = findNodeEquiv(Src->getOperator());
1299   if (!SrcGIOrNull)
1300     return failedImport("Pattern operator lacks an equivalent Instruction" +
1301                         explainOperator(Src->getOperator()));
1302   auto &SrcGI = *SrcGIOrNull;
1303
1304   // The operators look good: match the opcode and mutate it to the new one.
1305   InsnMatcher.addPredicate<InstructionOpcodeMatcher>(&SrcGI);
1306
1307   unsigned OpIdx = 0;
1308   unsigned TempOpIdx = 0;
1309   for (const EEVT::TypeSet &Ty : Src->getExtTypes()) {
1310     auto OpTyOrNone = MVTToLLT(Ty.getConcrete());
1311
1312     if (!OpTyOrNone)
1313       return failedImport(
1314           "Result of Src pattern operator has an unsupported type");
1315
1316     // Results don't have a name unless they are the root node. The caller will
1317     // set the name if appropriate.
1318     OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
1319     OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
1320   }
1321
1322   // Match the used operands (i.e. the children of the operator).
1323   for (unsigned i = 0, e = Src->getNumChildren(); i != e; ++i) {
1324     if (auto Error = importChildMatcher(InsnMatcher, Src->getChild(i), OpIdx++,
1325                                         TempOpIdx))
1326       return std::move(Error);
1327   }
1328
1329   return InsnMatcher;
1330 }
1331
1332 Error GlobalISelEmitter::importChildMatcher(InstructionMatcher &InsnMatcher,
1333                                             TreePatternNode *SrcChild,
1334                                             unsigned OpIdx,
1335                                             unsigned &TempOpIdx) const {
1336   OperandMatcher &OM =
1337       InsnMatcher.addOperand(OpIdx, SrcChild->getName(), TempOpIdx);
1338
1339   if (SrcChild->hasAnyPredicate())
1340     return failedImport("Src pattern child has predicate (" +
1341                         explainPredicates(SrcChild) + ")");
1342
1343   ArrayRef<EEVT::TypeSet> ChildTypes = SrcChild->getExtTypes();
1344   if (ChildTypes.size() != 1)
1345     return failedImport("Src pattern child has multiple results");
1346
1347   // Check MBB's before the type check since they are not a known type.
1348   if (!SrcChild->isLeaf()) {
1349     if (SrcChild->getOperator()->isSubClassOf("SDNode")) {
1350       auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator());
1351       if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
1352         OM.addPredicate<MBBOperandMatcher>();
1353         return Error::success();
1354       }
1355     }
1356   }
1357
1358   auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete());
1359   if (!OpTyOrNone)
1360     return failedImport("Src operand has an unsupported type");
1361   OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
1362
1363   // Check for nested instructions.
1364   if (!SrcChild->isLeaf()) {
1365     // Map the node to a gMIR instruction.
1366     InstructionOperandMatcher &InsnOperand =
1367         OM.addPredicate<InstructionOperandMatcher>();
1368     auto InsnMatcherOrError =
1369         createAndImportSelDAGMatcher(InsnOperand.getInsnMatcher(), SrcChild);
1370     if (auto Error = InsnMatcherOrError.takeError())
1371       return Error;
1372
1373     return Error::success();
1374   }
1375
1376   // Check for constant immediates.
1377   if (auto *ChildInt = dyn_cast<IntInit>(SrcChild->getLeafValue())) {
1378     OM.addPredicate<IntOperandMatcher>(ChildInt->getValue());
1379     return Error::success();
1380   }
1381
1382   // Check for def's like register classes or ComplexPattern's.
1383   if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
1384     auto *ChildRec = ChildDefInit->getDef();
1385
1386     // Check for register classes.
1387     if (ChildRec->isSubClassOf("RegisterClass")) {
1388       OM.addPredicate<RegisterBankOperandMatcher>(
1389           Target.getRegisterClass(ChildRec));
1390       return Error::success();
1391     }
1392
1393     if (ChildRec->isSubClassOf("RegisterOperand")) {
1394       OM.addPredicate<RegisterBankOperandMatcher>(
1395           Target.getRegisterClass(ChildRec->getValueAsDef("RegClass")));
1396       return Error::success();
1397     }
1398
1399     // Check for ComplexPattern's.
1400     if (ChildRec->isSubClassOf("ComplexPattern")) {
1401       const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
1402       if (ComplexPattern == ComplexPatternEquivs.end())
1403         return failedImport("SelectionDAG ComplexPattern (" +
1404                             ChildRec->getName() + ") not mapped to GlobalISel");
1405
1406       OM.addPredicate<ComplexPatternOperandMatcher>(OM,
1407                                                     *ComplexPattern->second);
1408       TempOpIdx++;
1409       return Error::success();
1410     }
1411
1412     if (ChildRec->isSubClassOf("ImmLeaf")) {
1413       return failedImport(
1414           "Src pattern child def is an unsupported tablegen class (ImmLeaf)");
1415     }
1416
1417     return failedImport(
1418         "Src pattern child def is an unsupported tablegen class");
1419   }
1420
1421   return failedImport("Src pattern child is an unsupported kind");
1422 }
1423
1424 Error GlobalISelEmitter::importExplicitUseRenderer(
1425     BuildMIAction &DstMIBuilder, TreePatternNode *DstChild,
1426     const InstructionMatcher &InsnMatcher) const {
1427   // The only non-leaf child we accept is 'bb': it's an operator because
1428   // BasicBlockSDNode isn't inline, but in MI it's just another operand.
1429   if (!DstChild->isLeaf()) {
1430     if (DstChild->getOperator()->isSubClassOf("SDNode")) {
1431       auto &ChildSDNI = CGP.getSDNodeInfo(DstChild->getOperator());
1432       if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
1433         DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher,
1434                                                DstChild->getName());
1435         return Error::success();
1436       }
1437     }
1438     return failedImport("Dst pattern child isn't a leaf node or an MBB");
1439   }
1440
1441   // Otherwise, we're looking for a bog-standard RegisterClass operand.
1442   if (DstChild->hasAnyPredicate())
1443     return failedImport("Dst pattern child has predicate (" +
1444                         explainPredicates(DstChild) + ")");
1445
1446   if (auto *ChildDefInit = dyn_cast<DefInit>(DstChild->getLeafValue())) {
1447     auto *ChildRec = ChildDefInit->getDef();
1448
1449     ArrayRef<EEVT::TypeSet> ChildTypes = DstChild->getExtTypes();
1450     if (ChildTypes.size() != 1)
1451       return failedImport("Dst pattern child has multiple results");
1452
1453     auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete());
1454     if (!OpTyOrNone)
1455       return failedImport("Dst operand has an unsupported type");
1456
1457     if (ChildRec->isSubClassOf("Register")) {
1458       DstMIBuilder.addRenderer<AddRegisterRenderer>(ChildRec);
1459       return Error::success();
1460     }
1461
1462     if (ChildRec->isSubClassOf("RegisterClass") ||
1463         ChildRec->isSubClassOf("RegisterOperand")) {
1464       DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher, DstChild->getName());
1465       return Error::success();
1466     }
1467
1468     if (ChildRec->isSubClassOf("ComplexPattern")) {
1469       const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
1470       if (ComplexPattern == ComplexPatternEquivs.end())
1471         return failedImport(
1472             "SelectionDAG ComplexPattern not mapped to GlobalISel");
1473
1474       const OperandMatcher &OM = InsnMatcher.getOperand(DstChild->getName());
1475       DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
1476           *ComplexPattern->second, DstChild->getName(),
1477           OM.getAllocatedTemporariesBaseID());
1478       return Error::success();
1479     }
1480
1481     if (ChildRec->isSubClassOf("SDNodeXForm"))
1482       return failedImport("Dst pattern child def is an unsupported tablegen "
1483                           "class (SDNodeXForm)");
1484
1485     return failedImport(
1486         "Dst pattern child def is an unsupported tablegen class");
1487   }
1488
1489   return failedImport("Dst pattern child is an unsupported kind");
1490 }
1491
1492 Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
1493     RuleMatcher &M, const TreePatternNode *Dst,
1494     const InstructionMatcher &InsnMatcher) const {
1495   Record *DstOp = Dst->getOperator();
1496   if (!DstOp->isSubClassOf("Instruction")) {
1497     if (DstOp->isSubClassOf("ValueType"))
1498       return failedImport(
1499           "Pattern operator isn't an instruction (it's a ValueType)");
1500     return failedImport("Pattern operator isn't an instruction");
1501   }
1502   auto &DstI = Target.getInstruction(DstOp);
1503
1504   auto &DstMIBuilder = M.addAction<BuildMIAction>(&DstI, InsnMatcher);
1505
1506   // Render the explicit defs.
1507   for (unsigned I = 0; I < DstI.Operands.NumDefs; ++I) {
1508     const auto &DstIOperand = DstI.Operands[I];
1509     DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher, DstIOperand.Name);
1510   }
1511
1512   // Figure out which operands need defaults inserted. Operands that subclass
1513   // OperandWithDefaultOps are considered from left to right until we have
1514   // enough operands to render the instruction.
1515   SmallSet<unsigned, 2> DefaultOperands;
1516   unsigned DstINumUses = DstI.Operands.size() - DstI.Operands.NumDefs;
1517   unsigned NumDefaultOperands = 0;
1518   for (unsigned I = 0; I < DstINumUses &&
1519                        DstINumUses > Dst->getNumChildren() + NumDefaultOperands;
1520        ++I) {
1521     const auto &DstIOperand = DstI.Operands[DstI.Operands.NumDefs + I];
1522     if (DstIOperand.Rec->isSubClassOf("OperandWithDefaultOps")) {
1523       DefaultOperands.insert(I);
1524       NumDefaultOperands +=
1525           DstIOperand.Rec->getValueAsDag("DefaultOps")->getNumArgs();
1526     }
1527   }
1528   if (DstINumUses > Dst->getNumChildren() + DefaultOperands.size())
1529     return failedImport("Insufficient operands supplied and default ops "
1530                         "couldn't make up the shortfall");
1531   if (DstINumUses < Dst->getNumChildren() + DefaultOperands.size())
1532     return failedImport("Too many operands supplied");
1533
1534   // Render the explicit uses.
1535   unsigned Child = 0;
1536   for (unsigned I = 0; I != DstINumUses; ++I) {
1537     // If we need to insert default ops here, then do so.
1538     if (DefaultOperands.count(I)) {
1539       const auto &DstIOperand = DstI.Operands[DstI.Operands.NumDefs + I];
1540
1541       DagInit *DefaultOps = DstIOperand.Rec->getValueAsDag("DefaultOps");
1542       for (const auto *DefaultOp : DefaultOps->args()) {
1543         // Look through ValueType operators.
1544         if (const DagInit *DefaultDagOp = dyn_cast<DagInit>(DefaultOp)) {
1545           if (const DefInit *DefaultDagOperator =
1546                   dyn_cast<DefInit>(DefaultDagOp->getOperator())) {
1547             if (DefaultDagOperator->getDef()->isSubClassOf("ValueType"))
1548               DefaultOp = DefaultDagOp->getArg(0);
1549           }
1550         }
1551
1552         if (const DefInit *DefaultDefOp = dyn_cast<DefInit>(DefaultOp)) {
1553           DstMIBuilder.addRenderer<AddRegisterRenderer>(DefaultDefOp->getDef());
1554           continue;
1555         }
1556
1557         if (const IntInit *DefaultIntOp = dyn_cast<IntInit>(DefaultOp)) {
1558           DstMIBuilder.addRenderer<ImmRenderer>(DefaultIntOp->getValue());
1559           continue;
1560         }
1561
1562         return failedImport("Could not add default op");
1563       }
1564
1565       continue;
1566     }
1567
1568     if (auto Error = importExplicitUseRenderer(
1569             DstMIBuilder, Dst->getChild(Child), InsnMatcher))
1570       return std::move(Error);
1571     ++Child;
1572   }
1573
1574   return DstMIBuilder;
1575 }
1576
1577 Error GlobalISelEmitter::importImplicitDefRenderers(
1578     BuildMIAction &DstMIBuilder,
1579     const std::vector<Record *> &ImplicitDefs) const {
1580   if (!ImplicitDefs.empty())
1581     return failedImport("Pattern defines a physical register");
1582   return Error::success();
1583 }
1584
1585 Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
1586   // Keep track of the matchers and actions to emit.
1587   RuleMatcher M;
1588   M.addAction<DebugCommentAction>(P);
1589
1590   if (auto Error = importRulePredicates(M, P.getPredicates()->getValues()))
1591     return std::move(Error);
1592
1593   // Next, analyze the pattern operators.
1594   TreePatternNode *Src = P.getSrcPattern();
1595   TreePatternNode *Dst = P.getDstPattern();
1596
1597   // If the root of either pattern isn't a simple operator, ignore it.
1598   if (auto Err = isTrivialOperatorNode(Dst))
1599     return failedImport("Dst pattern root isn't a trivial operator (" +
1600                         toString(std::move(Err)) + ")");
1601   if (auto Err = isTrivialOperatorNode(Src))
1602     return failedImport("Src pattern root isn't a trivial operator (" +
1603                         toString(std::move(Err)) + ")");
1604
1605   // Start with the defined operands (i.e., the results of the root operator).
1606   Record *DstOp = Dst->getOperator();
1607   if (!DstOp->isSubClassOf("Instruction"))
1608     return failedImport("Pattern operator isn't an instruction");
1609
1610   auto &DstI = Target.getInstruction(DstOp);
1611   if (DstI.Operands.NumDefs != Src->getExtTypes().size())
1612     return failedImport("Src pattern results and dst MI defs are different (" +
1613                         to_string(Src->getExtTypes().size()) + " def(s) vs " +
1614                         to_string(DstI.Operands.NumDefs) + " def(s))");
1615
1616   InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher();
1617   auto InsnMatcherOrError = createAndImportSelDAGMatcher(InsnMatcherTemp, Src);
1618   if (auto Error = InsnMatcherOrError.takeError())
1619     return std::move(Error);
1620   InstructionMatcher &InsnMatcher = InsnMatcherOrError.get();
1621
1622   // The root of the match also has constraints on the register bank so that it
1623   // matches the result instruction.
1624   unsigned OpIdx = 0;
1625   for (const EEVT::TypeSet &Ty : Src->getExtTypes()) {
1626     (void)Ty;
1627
1628     const auto &DstIOperand = DstI.Operands[OpIdx];
1629     Record *DstIOpRec = DstIOperand.Rec;
1630     if (DstIOpRec->isSubClassOf("RegisterOperand"))
1631       DstIOpRec = DstIOpRec->getValueAsDef("RegClass");
1632     if (!DstIOpRec->isSubClassOf("RegisterClass"))
1633       return failedImport("Dst MI def isn't a register class");
1634
1635     OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
1636     OM.setSymbolicName(DstIOperand.Name);
1637     OM.addPredicate<RegisterBankOperandMatcher>(
1638         Target.getRegisterClass(DstIOpRec));
1639     ++OpIdx;
1640   }
1641
1642   auto DstMIBuilderOrError =
1643       createAndImportInstructionRenderer(M, Dst, InsnMatcher);
1644   if (auto Error = DstMIBuilderOrError.takeError())
1645     return std::move(Error);
1646   BuildMIAction &DstMIBuilder = DstMIBuilderOrError.get();
1647
1648   // Render the implicit defs.
1649   // These are only added to the root of the result.
1650   if (auto Error = importImplicitDefRenderers(DstMIBuilder, P.getDstRegs()))
1651     return std::move(Error);
1652
1653   // We're done with this pattern!  It's eligible for GISel emission; return it.
1654   ++NumPatternImported;
1655   return std::move(M);
1656 }
1657
1658 void GlobalISelEmitter::run(raw_ostream &OS) {
1659   // Track the GINodeEquiv definitions.
1660   gatherNodeEquivs();
1661
1662   emitSourceFileHeader(("Global Instruction Selector for the " +
1663                        Target.getName() + " target").str(), OS);
1664   std::vector<RuleMatcher> Rules;
1665   // Look through the SelectionDAG patterns we found, possibly emitting some.
1666   for (const PatternToMatch &Pat : CGP.ptms()) {
1667     ++NumPatternTotal;
1668     auto MatcherOrErr = runOnPattern(Pat);
1669
1670     // The pattern analysis can fail, indicating an unsupported pattern.
1671     // Report that if we've been asked to do so.
1672     if (auto Err = MatcherOrErr.takeError()) {
1673       if (WarnOnSkippedPatterns) {
1674         PrintWarning(Pat.getSrcRecord()->getLoc(),
1675                      "Skipped pattern: " + toString(std::move(Err)));
1676       } else {
1677         consumeError(std::move(Err));
1678       }
1679       ++NumPatternImportsSkipped;
1680       continue;
1681     }
1682
1683     Rules.push_back(std::move(MatcherOrErr.get()));
1684   }
1685
1686   std::stable_sort(Rules.begin(), Rules.end(),
1687             [&](const RuleMatcher &A, const RuleMatcher &B) {
1688               if (A.isHigherPriorityThan(B)) {
1689                 assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
1690                                                      "and less important at "
1691                                                      "the same time");
1692                 return true;
1693               }
1694               return false;
1695             });
1696
1697   unsigned MaxTemporaries = 0;
1698   for (const auto &Rule : Rules)
1699     MaxTemporaries = std::max(MaxTemporaries, Rule.countRendererFns());
1700
1701   OS << "#ifdef GET_GLOBALISEL_PREDICATE_BITSET\n"
1702      << "const unsigned MAX_SUBTARGET_PREDICATES = " << SubtargetFeatures.size()
1703      << ";\n"
1704      << "using PredicateBitset = "
1705         "llvm::PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;\n"
1706      << "#endif // ifdef GET_GLOBALISEL_PREDICATE_BITSET\n\n";
1707
1708   OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n";
1709   for (unsigned I = 0; I < MaxTemporaries; ++I)
1710     OS << "  mutable ComplexRendererFn Renderer" << I << ";\n";
1711   OS << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n";
1712
1713   OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n";
1714   for (unsigned I = 0; I < MaxTemporaries; ++I)
1715     OS << ", Renderer" << I << "(nullptr)\n";
1716   OS << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";
1717
1718   OS << "#ifdef GET_GLOBALISEL_IMPL\n";
1719   SubtargetFeatureInfo::emitSubtargetFeatureBitEnumeration(SubtargetFeatures,
1720                                                            OS);
1721
1722   // Separate subtarget features by how often they must be recomputed.
1723   SubtargetFeatureInfoMap ModuleFeatures;
1724   std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
1725                std::inserter(ModuleFeatures, ModuleFeatures.end()),
1726                [](const SubtargetFeatureInfoMap::value_type &X) {
1727                  return !X.second.mustRecomputePerFunction();
1728                });
1729   SubtargetFeatureInfoMap FunctionFeatures;
1730   std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
1731                std::inserter(FunctionFeatures, FunctionFeatures.end()),
1732                [](const SubtargetFeatureInfoMap::value_type &X) {
1733                  return X.second.mustRecomputePerFunction();
1734                });
1735
1736   SubtargetFeatureInfo::emitComputeAvailableFeatures(
1737       Target.getName(), "InstructionSelector", "computeAvailableModuleFeatures",
1738       ModuleFeatures, OS);
1739   SubtargetFeatureInfo::emitComputeAvailableFeatures(
1740       Target.getName(), "InstructionSelector",
1741       "computeAvailableFunctionFeatures", FunctionFeatures, OS,
1742       "const MachineFunction *MF");
1743
1744   OS << "bool " << Target.getName()
1745      << "InstructionSelector::selectImpl(MachineInstr &I) const {\n"
1746      << "  MachineFunction &MF = *I.getParent()->getParent();\n"
1747      << "  const MachineRegisterInfo &MRI = MF.getRegInfo();\n"
1748      << "  // FIXME: This should be computed on a per-function basis rather than per-insn.\n"
1749      << "  AvailableFunctionFeatures = computeAvailableFunctionFeatures(&STI, &MF);\n"
1750      << "  const PredicateBitset AvailableFeatures = getAvailableFeatures();\n";
1751
1752   for (auto &Rule : Rules) {
1753     Rule.emit(OS, SubtargetFeatures);
1754     ++NumPatternEmitted;
1755   }
1756
1757   OS << "  return false;\n"
1758      << "}\n"
1759      << "#endif // ifdef GET_GLOBALISEL_IMPL\n";
1760
1761   OS << "#ifdef GET_GLOBALISEL_PREDICATES_DECL\n"
1762      << "PredicateBitset AvailableModuleFeatures;\n"
1763      << "mutable PredicateBitset AvailableFunctionFeatures;\n"
1764      << "PredicateBitset getAvailableFeatures() const {\n"
1765      << "  return AvailableModuleFeatures | AvailableFunctionFeatures;\n"
1766      << "}\n"
1767      << "PredicateBitset\n"
1768      << "computeAvailableModuleFeatures(const " << Target.getName()
1769      << "Subtarget *Subtarget) const;\n"
1770      << "PredicateBitset\n"
1771      << "computeAvailableFunctionFeatures(const " << Target.getName()
1772      << "Subtarget *Subtarget,\n"
1773      << "                                 const MachineFunction *MF) const;\n"
1774      << "#endif // ifdef GET_GLOBALISEL_PREDICATES_DECL\n";
1775
1776   OS << "#ifdef GET_GLOBALISEL_PREDICATES_INIT\n"
1777      << "AvailableModuleFeatures(computeAvailableModuleFeatures(&STI)),\n"
1778      << "AvailableFunctionFeatures()\n"
1779      << "#endif // ifdef GET_GLOBALISEL_PREDICATES_INIT\n";
1780 }
1781
1782 void GlobalISelEmitter::declareSubtargetFeature(Record *Predicate) {
1783   if (SubtargetFeatures.count(Predicate) == 0)
1784     SubtargetFeatures.emplace(
1785         Predicate, SubtargetFeatureInfo(Predicate, SubtargetFeatures.size()));
1786 }
1787
1788 } // end anonymous namespace
1789
1790 //===----------------------------------------------------------------------===//
1791
1792 namespace llvm {
1793 void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS) {
1794   GlobalISelEmitter(RK).run(OS);
1795 }
1796 } // End llvm namespace