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,
 203             std::map<Record *, SubtargetFeatureInfo, LessRecordByID>
 204                 SubtargetFeatures);
 205
 206   /// Compare the priority of this object and B.
 207   ///
 208   /// Returns true if this object is more important than B.
 209   bool isHigherPriorityThan(const RuleMatcher &B) const;
 210
 211   /// Report the maximum number of temporary operands needed by the rule
 212   /// matcher.
 213   unsigned countRendererFns() const;
 214
 215   // FIXME: Remove this as soon as possible
 216   InstructionMatcher &insnmatcher_front() const { return *Matchers.front(); }
 217 };
 218
 219 template <class PredicateTy> class PredicateListMatcher {
 220 private:
 221   typedef std::vector<std::unique_ptr<PredicateTy>> PredicateVec;
 222   PredicateVec Predicates;
 223
 224 public:
 225   /// Construct a new operand predicate and add it to the matcher.
 226   template <class Kind, class... Args>
 227   Kind &addPredicate(Args&&... args) {
 228     Predicates.emplace_back(
 229         llvm::make_unique<Kind>(std::forward<Args>(args)...));
 230     return *static_cast<Kind *>(Predicates.back().get());
 231   }
 232
 233   typename PredicateVec::const_iterator predicates_begin() const { return Predicates.begin(); }
 234   typename PredicateVec::const_iterator predicates_end() const { return Predicates.end(); }
 235   iterator_range<typename PredicateVec::const_iterator> predicates() const {
 236     return make_range(predicates_begin(), predicates_end());
 237   }
 238   typename PredicateVec::size_type predicates_size() const { return Predicates.size(); }
 239
 240   /// Emit a C++ expression that tests whether all the predicates are met.
 241   template <class... Args>
 242   void emitCxxPredicateListExpr(raw_ostream &OS, Args &&... args) const {
 243     if (Predicates.empty()) {
 244       OS << "true";
 245       return;
 246     }
 247
 248     StringRef Separator = "";
 249     for (const auto &Predicate : predicates()) {
 250       OS << Separator << "(";
 251       Predicate->emitCxxPredicateExpr(OS, std::forward<Args>(args)...);
 252       OS << ")";
 253       Separator = " &&\n";
 254     }
 255   }
 256 };
 257
 258 /// Generates code to check a predicate of an operand.
 259 ///
 260 /// Typical predicates include:
 261 /// * Operand is a particular register.
 262 /// * Operand is assigned a particular register bank.
 263 /// * Operand is an MBB.
 264 class OperandPredicateMatcher {
 265 public:
 266   /// This enum is used for RTTI and also defines the priority that is given to
 267   /// the predicate when generating the matcher code. Kinds with higher priority
 268   /// must be tested first.
 269   ///
 270   /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter
 271   /// but OPM_Int must have priority over OPM_RegBank since constant integers
 272   /// are represented by a virtual register defined by a G_CONSTANT instruction.
 273   enum PredicateKind {
 274     OPM_ComplexPattern,
 275     OPM_Instruction,
 276     OPM_Int,
 277     OPM_LLT,
 278     OPM_RegBank,
 279     OPM_MBB,
 280   };
 281
 282 protected:
 283   PredicateKind Kind;
 284
 285 public:
 286   OperandPredicateMatcher(PredicateKind Kind) : Kind(Kind) {}
 287   virtual ~OperandPredicateMatcher() {}
 288
 289   PredicateKind getKind() const { return Kind; }
 290
 291   /// Return the OperandMatcher for the specified operand or nullptr if there
 292   /// isn't one by that name in this operand predicate matcher.
 293   ///
 294   /// InstructionOperandMatcher is the only subclass that can return non-null
 295   /// for this.
 296   virtual Optional<const OperandMatcher *>
 297   getOptionalOperand(StringRef SymbolicName) const {
 298     assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
 299     return None;
 300   }
 301
 302   /// Emit C++ statements to capture instructions into local variables.
 303   ///
 304   /// Only InstructionOperandMatcher needs to do anything for this method.
 305   virtual void emitCxxCaptureStmts(raw_ostream &OS, RuleMatcher &Rule,
 306                                    StringRef Expr) const {}
 307
 308   /// Emit a C++ expression that checks the predicate for the given operand.
 309   virtual void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
 310                                     StringRef OperandExpr) const = 0;
 311
 312   /// Compare the priority of this object and B.
 313   ///
 314   /// Returns true if this object is more important than B.
 315   virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const {
 316     return Kind < B.Kind;
 317   };
 318
 319   /// Report the maximum number of temporary operands needed by the predicate
 320   /// matcher.
 321   virtual unsigned countRendererFns() const { return 0; }
 322 };
 323
 324 /// Generates code to check that an operand is a particular LLT.
 325 class LLTOperandMatcher : public OperandPredicateMatcher {
 326 protected:
 327   LLTCodeGen Ty;
 328
 329 public:
 330   LLTOperandMatcher(const LLTCodeGen &Ty)
 331       : OperandPredicateMatcher(OPM_LLT), Ty(Ty) {}
 332
 333   static bool classof(const OperandPredicateMatcher *P) {
 334     return P->getKind() == OPM_LLT;
 335   }
 336
 337   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
 338                             StringRef OperandExpr) const override {
 339     OS << "MRI.getType(" << OperandExpr << ".getReg()) == (";
 340     Ty.emitCxxConstructorCall(OS);
 341     OS << ")";
 342   }
 343 };
 344
 345 /// Generates code to check that an operand is a particular target constant.
 346 class ComplexPatternOperandMatcher : public OperandPredicateMatcher {
 347 protected:
 348   const OperandMatcher &Operand;
 349   const Record &TheDef;
 350
 351   unsigned getAllocatedTemporariesBaseID() const;
 352
 353 public:
 354   ComplexPatternOperandMatcher(const OperandMatcher &Operand,
 355                                const Record &TheDef)
 356       : OperandPredicateMatcher(OPM_ComplexPattern), Operand(Operand),
 357         TheDef(TheDef) {}
 358
 359   static bool classof(const OperandPredicateMatcher *P) {
 360     return P->getKind() == OPM_ComplexPattern;
 361   }
 362
 363   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
 364                             StringRef OperandExpr) const override {
 365     unsigned ID = getAllocatedTemporariesBaseID();
 366     OS << "(Renderer" << ID << " = " << TheDef.getValueAsString("MatcherFn")
 367        << "(" << OperandExpr << "))";
 368   }
 369
 370   unsigned countRendererFns() const override {
 371     return 1;
 372   }
 373 };
 374
 375 /// Generates code to check that an operand is in a particular register bank.
 376 class RegisterBankOperandMatcher : public OperandPredicateMatcher {
 377 protected:
 378   const CodeGenRegisterClass &RC;
 379
 380 public:
 381   RegisterBankOperandMatcher(const CodeGenRegisterClass &RC)
 382       : OperandPredicateMatcher(OPM_RegBank), RC(RC) {}
 383
 384   static bool classof(const OperandPredicateMatcher *P) {
 385     return P->getKind() == OPM_RegBank;
 386   }
 387
 388   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
 389                             StringRef OperandExpr) const override {
 390     OS << "(&RBI.getRegBankFromRegClass(" << RC.getQualifiedName()
 391        << "RegClass) == RBI.getRegBank(" << OperandExpr
 392        << ".getReg(), MRI, TRI))";
 393   }
 394 };
 395
 396 /// Generates code to check that an operand is a basic block.
 397 class MBBOperandMatcher : public OperandPredicateMatcher {
 398 public:
 399   MBBOperandMatcher() : OperandPredicateMatcher(OPM_MBB) {}
 400
 401   static bool classof(const OperandPredicateMatcher *P) {
 402     return P->getKind() == OPM_MBB;
 403   }
 404
 405   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
 406                             StringRef OperandExpr) const override {
 407     OS << OperandExpr << ".isMBB()";
 408   }
 409 };
 410
 411 /// Generates code to check that an operand is a particular int.
 412 class IntOperandMatcher : public OperandPredicateMatcher {
 413 protected:
 414   int64_t Value;
 415
 416 public:
 417   IntOperandMatcher(int64_t Value)
 418       : OperandPredicateMatcher(OPM_Int), Value(Value) {}
 419
 420   static bool classof(const OperandPredicateMatcher *P) {
 421     return P->getKind() == OPM_Int;
 422   }
 423
 424   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
 425                             StringRef OperandExpr) const override {
 426     OS << "isOperandImmEqual(" << OperandExpr << ", " << Value << ", MRI)";
 427   }
 428 };
 429
 430 /// Generates code to check that a set of predicates match for a particular
 431 /// operand.
 432 class OperandMatcher : public PredicateListMatcher<OperandPredicateMatcher> {
 433 protected:
 434   InstructionMatcher &Insn;
 435   unsigned OpIdx;
 436   std::string SymbolicName;
 437
 438   /// The index of the first temporary variable allocated to this operand. The
 439   /// number of allocated temporaries can be found with
 440   /// countRendererFns().
 441   unsigned AllocatedTemporariesBaseID;
 442
 443 public:
 444   OperandMatcher(InstructionMatcher &Insn, unsigned OpIdx,
 445                  const std::string &SymbolicName,
 446                  unsigned AllocatedTemporariesBaseID)
 447       : Insn(Insn), OpIdx(OpIdx), SymbolicName(SymbolicName),
 448         AllocatedTemporariesBaseID(AllocatedTemporariesBaseID) {}
 449
 450   bool hasSymbolicName() const { return !SymbolicName.empty(); }
 451   const StringRef getSymbolicName() const { return SymbolicName; }
 452   void setSymbolicName(StringRef Name) {
 453     assert(SymbolicName.empty() && "Operand already has a symbolic name");
 454     SymbolicName = Name;
 455   }
 456   unsigned getOperandIndex() const { return OpIdx; }
 457
 458   std::string getOperandExpr(StringRef InsnVarName) const {
 459     return (InsnVarName + ".getOperand(" + llvm::to_string(OpIdx) + ")").str();
 460   }
 461
 462   Optional<const OperandMatcher *>
 463   getOptionalOperand(StringRef DesiredSymbolicName) const {
 464     assert(!DesiredSymbolicName.empty() && "Cannot lookup unnamed operand");
 465     if (DesiredSymbolicName == SymbolicName)
 466       return this;
 467     for (const auto &OP : predicates()) {
 468       const auto &MaybeOperand = OP->getOptionalOperand(DesiredSymbolicName);
 469       if (MaybeOperand.hasValue())
 470         return MaybeOperand.getValue();
 471     }
 472     return None;
 473   }
 474
 475   InstructionMatcher &getInstructionMatcher() const { return Insn; }
 476
 477   /// Emit C++ statements to capture instructions into local variables.
 478   void emitCxxCaptureStmts(raw_ostream &OS, RuleMatcher &Rule,
 479                            StringRef OperandExpr) const {
 480     for (const auto &Predicate : predicates())
 481       Predicate->emitCxxCaptureStmts(OS, Rule, OperandExpr);
 482   }
 483
 484   /// Emit a C++ expression that tests whether the instruction named in
 485   /// InsnVarName matches all the predicate and all the operands.
 486   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
 487                             StringRef InsnVarName) const {
 488     OS << "(/* ";
 489     if (SymbolicName.empty())
 490       OS << "Operand " << OpIdx;
 491     else
 492       OS << SymbolicName;
 493     OS << " */ ";
 494     emitCxxPredicateListExpr(OS, Rule, getOperandExpr(InsnVarName));
 495     OS << ")";
 496   }
 497
 498   /// Compare the priority of this object and B.
 499   ///
 500   /// Returns true if this object is more important than B.
 501   bool isHigherPriorityThan(const OperandMatcher &B) const {
 502     // Operand matchers involving more predicates have higher priority.
 503     if (predicates_size() > B.predicates_size())
 504       return true;
 505     if (predicates_size() < B.predicates_size())
 506       return false;
 507
 508     // This assumes that predicates are added in a consistent order.
 509     for (const auto &Predicate : zip(predicates(), B.predicates())) {
 510       if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate)))
 511         return true;
 512       if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate)))
 513         return false;
 514     }
 515
 516     return false;
 517   };
 518
 519   /// Report the maximum number of temporary operands needed by the operand
 520   /// matcher.
 521   unsigned countRendererFns() const {
 522     return std::accumulate(
 523         predicates().begin(), predicates().end(), 0,
 524         [](unsigned A,
 525            const std::unique_ptr<OperandPredicateMatcher> &Predicate) {
 526           return A + Predicate->countRendererFns();
 527         });
 528   }
 529
 530   unsigned getAllocatedTemporariesBaseID() const {
 531     return AllocatedTemporariesBaseID;
 532   }
 533 };
 534
 535 unsigned ComplexPatternOperandMatcher::getAllocatedTemporariesBaseID() const {
 536   return Operand.getAllocatedTemporariesBaseID();
 537 }
 538
 539 /// Generates code to check a predicate on an instruction.
 540 ///
 541 /// Typical predicates include:
 542 /// * The opcode of the instruction is a particular value.
 543 /// * The nsw/nuw flag is/isn't set.
 544 class InstructionPredicateMatcher {
 545 protected:
 546   /// This enum is used for RTTI and also defines the priority that is given to
 547   /// the predicate when generating the matcher code. Kinds with higher priority
 548   /// must be tested first.
 549   enum PredicateKind {
 550     IPM_Opcode,
 551   };
 552
 553   PredicateKind Kind;
 554
 555 public:
 556   InstructionPredicateMatcher(PredicateKind Kind) : Kind(Kind) {}
 557   virtual ~InstructionPredicateMatcher() {}
 558
 559   PredicateKind getKind() const { return Kind; }
 560
 561   /// Emit a C++ expression that tests whether the instruction named in
 562   /// InsnVarName matches the predicate.
 563   virtual void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
 564                                     StringRef InsnVarName) const = 0;
 565
 566   /// Compare the priority of this object and B.
 567   ///
 568   /// Returns true if this object is more important than B.
 569   virtual bool isHigherPriorityThan(const InstructionPredicateMatcher &B) const {
 570     return Kind < B.Kind;
 571   };
 572
 573   /// Report the maximum number of temporary operands needed by the predicate
 574   /// matcher.
 575   virtual unsigned countRendererFns() const { return 0; }
 576 };
 577
 578 /// Generates code to check the opcode of an instruction.
 579 class InstructionOpcodeMatcher : public InstructionPredicateMatcher {
 580 protected:
 581   const CodeGenInstruction *I;
 582
 583 public:
 584   InstructionOpcodeMatcher(const CodeGenInstruction *I)
 585       : InstructionPredicateMatcher(IPM_Opcode), I(I) {}
 586
 587   static bool classof(const InstructionPredicateMatcher *P) {
 588     return P->getKind() == IPM_Opcode;
 589   }
 590
 591   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
 592                             StringRef InsnVarName) const override {
 593     OS << InsnVarName << ".getOpcode() == " << I->Namespace
 594        << "::" << I->TheDef->getName();
 595   }
 596
 597   /// Compare the priority of this object and B.
 598   ///
 599   /// Returns true if this object is more important than B.
 600   bool isHigherPriorityThan(const InstructionPredicateMatcher &B) const override {
 601     if (InstructionPredicateMatcher::isHigherPriorityThan(B))
 602       return true;
 603     if (B.InstructionPredicateMatcher::isHigherPriorityThan(*this))
 604       return false;
 605
 606     // Prioritize opcodes for cosmetic reasons in the generated source. Although
 607     // this is cosmetic at the moment, we may want to drive a similar ordering
 608     // using instruction frequency information to improve compile time.
 609     if (const InstructionOpcodeMatcher *BO =
 610             dyn_cast<InstructionOpcodeMatcher>(&B))
 611       return I->TheDef->getName() < BO->I->TheDef->getName();
 612
 613     return false;
 614   };
 615 };
 616
 617 /// Generates code to check that a set of predicates and operands match for a
 618 /// particular instruction.
 619 ///
 620 /// Typical predicates include:
 621 /// * Has a specific opcode.
 622 /// * Has an nsw/nuw flag or doesn't.
 623 class InstructionMatcher
 624     : public PredicateListMatcher<InstructionPredicateMatcher> {
 625 protected:
 626   typedef std::vector<std::unique_ptr<OperandMatcher>> OperandVec;
 627
 628   /// The operands to match. All rendered operands must be present even if the
 629   /// condition is always true.
 630   OperandVec Operands;
 631
 632 public:
 633   /// Add an operand to the matcher.
 634   OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName,
 635                              unsigned AllocatedTemporariesBaseID) {
 636     Operands.emplace_back(new OperandMatcher(*this, OpIdx, SymbolicName,
 637                                              AllocatedTemporariesBaseID));
 638     return *Operands.back();
 639   }
 640
 641   OperandMatcher &getOperand(unsigned OpIdx) {
 642     auto I = std::find_if(Operands.begin(), Operands.end(),
 643                           [&OpIdx](const std::unique_ptr<OperandMatcher> &X) {
 644                             return X->getOperandIndex() == OpIdx;
 645                           });
 646     if (I != Operands.end())
 647       return **I;
 648     llvm_unreachable("Failed to lookup operand");
 649   }
 650
 651   Optional<const OperandMatcher *>
 652   getOptionalOperand(StringRef SymbolicName) const {
 653     assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
 654     for (const auto &Operand : Operands) {
 655       const auto &OM = Operand->getOptionalOperand(SymbolicName);
 656       if (OM.hasValue())
 657         return OM.getValue();
 658     }
 659     return None;
 660   }
 661
 662   const OperandMatcher &getOperand(StringRef SymbolicName) const {
 663     Optional<const OperandMatcher *>OM = getOptionalOperand(SymbolicName);
 664     if (OM.hasValue())
 665       return *OM.getValue();
 666     llvm_unreachable("Failed to lookup operand");
 667   }
 668
 669   unsigned getNumOperands() const { return Operands.size(); }
 670   OperandVec::iterator operands_begin() { return Operands.begin(); }
 671   OperandVec::iterator operands_end() { return Operands.end(); }
 672   iterator_range<OperandVec::iterator> operands() {
 673     return make_range(operands_begin(), operands_end());
 674   }
 675   OperandVec::const_iterator operands_begin() const { return Operands.begin(); }
 676   OperandVec::const_iterator operands_end() const { return Operands.end(); }
 677   iterator_range<OperandVec::const_iterator> operands() const {
 678     return make_range(operands_begin(), operands_end());
 679   }
 680
 681   /// Emit C++ statements to check the shape of the match and capture
 682   /// instructions into local variables.
 683   void emitCxxCaptureStmts(raw_ostream &OS, RuleMatcher &Rule, StringRef Expr) {
 684     OS << "if (" << Expr << ".getNumOperands() < " << getNumOperands() << ")\n"
 685        << "  return false;\n";
 686     for (const auto &Operand : Operands) {
 687       Operand->emitCxxCaptureStmts(OS, Rule, Operand->getOperandExpr(Expr));
 688     }
 689   }
 690
 691   /// Emit a C++ expression that tests whether the instruction named in
 692   /// InsnVarName matches all the predicates and all the operands.
 693   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
 694                             StringRef InsnVarName) const {
 695     emitCxxPredicateListExpr(OS, Rule, InsnVarName);
 696     for (const auto &Operand : Operands) {
 697       OS << " &&\n(";
 698       Operand->emitCxxPredicateExpr(OS, Rule, InsnVarName);
 699       OS << ")";
 700     }
 701   }
 702
 703   /// Compare the priority of this object and B.
 704   ///
 705   /// Returns true if this object is more important than B.
 706   bool isHigherPriorityThan(const InstructionMatcher &B) const {
 707     // Instruction matchers involving more operands have higher priority.
 708     if (Operands.size() > B.Operands.size())
 709       return true;
 710     if (Operands.size() < B.Operands.size())
 711       return false;
 712
 713     for (const auto &Predicate : zip(predicates(), B.predicates())) {
 714       if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate)))
 715         return true;
 716       if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate)))
 717         return false;
 718     }
 719
 720     for (const auto &Operand : zip(Operands, B.Operands)) {
 721       if (std::get<0>(Operand)->isHigherPriorityThan(*std::get<1>(Operand)))
 722         return true;
 723       if (std::get<1>(Operand)->isHigherPriorityThan(*std::get<0>(Operand)))
 724         return false;
 725     }
 726
 727     return false;
 728   };
 729
 730   /// Report the maximum number of temporary operands needed by the instruction
 731   /// matcher.
 732   unsigned countRendererFns() const {
 733     return std::accumulate(predicates().begin(), predicates().end(), 0,
 734                            [](unsigned A,
 735                               const std::unique_ptr<InstructionPredicateMatcher>
 736                                   &Predicate) {
 737                              return A + Predicate->countRendererFns();
 738                            }) +
 739            std::accumulate(
 740                Operands.begin(), Operands.end(), 0,
 741                [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) {
 742                  return A + Operand->countRendererFns();
 743                });
 744   }
 745 };
 746
 747 /// Generates code to check that the operand is a register defined by an
 748 /// instruction that matches the given instruction matcher.
 749 ///
 750 /// For example, the pattern:
 751 ///   (set $dst, (G_MUL (G_ADD $src1, $src2), $src3))
 752 /// would use an InstructionOperandMatcher for operand 1 of the G_MUL to match
 753 /// the:
 754 ///   (G_ADD $src1, $src2)
 755 /// subpattern.
 756 class InstructionOperandMatcher : public OperandPredicateMatcher {
 757 protected:
 758   std::unique_ptr<InstructionMatcher> InsnMatcher;
 759
 760 public:
 761   InstructionOperandMatcher()
 762       : OperandPredicateMatcher(OPM_Instruction),
 763         InsnMatcher(new InstructionMatcher()) {}
 764
 765   static bool classof(const OperandPredicateMatcher *P) {
 766     return P->getKind() == OPM_Instruction;
 767   }
 768
 769   InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; }
 770
 771   Optional<const OperandMatcher *>
 772   getOptionalOperand(StringRef SymbolicName) const override {
 773     assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
 774     return InsnMatcher->getOptionalOperand(SymbolicName);
 775   }
 776
 777   void emitCxxCaptureStmts(raw_ostream &OS, RuleMatcher &Rule,
 778                            StringRef OperandExpr) const override {
 779     OS << "if (!" << OperandExpr + ".isReg())\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->getValueAsString("Namespace")
 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     for (const auto &Renderer : enumerate(OperandRenderers)) {
 955       if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) {
 956         const OperandMatcher &OM = Matched.getOperand(Copy->getSymbolicName());
 957         if (&Matched != &OM.getInstructionMatcher() ||
 958             OM.getOperandIndex() != Renderer.index())
 959           return false;
 960       } else
 961         return false;
 962     }
 963
 964     return true;
 965   }
 966
 967 public:
 968   BuildMIAction(const CodeGenInstruction *I, const InstructionMatcher &Matched)
 969       : I(I), Matched(Matched) {}
 970
 971   template <class Kind, class... Args>
 972   Kind &addRenderer(Args&&... args) {
 973     OperandRenderers.emplace_back(
 974         llvm::make_unique<Kind>(std::forward<Args>(args)...));
 975     return *static_cast<Kind *>(OperandRenderers.back().get());
 976   }
 977
 978   void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
 979                           StringRef RecycleVarName) const override {
 980     if (canMutate()) {
 981       OS << "    " << RecycleVarName << ".setDesc(TII.get(" << I->Namespace
 982          << "::" << I->TheDef->getName() << "));\n";
 983
 984       if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) {
 985         OS << "    auto MIB = MachineInstrBuilder(MF, &" << RecycleVarName
 986            << ");\n";
 987
 988         for (auto Def : I->ImplicitDefs) {
 989           auto Namespace = Def->getValueAsString("Namespace");
 990           OS << "    MIB.addDef(" << Namespace << "::" << Def->getName()
 991              << ", RegState::Implicit);\n";
 992         }
 993         for (auto Use : I->ImplicitUses) {
 994           auto Namespace = Use->getValueAsString("Namespace");
 995           OS << "    MIB.addUse(" << Namespace << "::" << Use->getName()
 996              << ", RegState::Implicit);\n";
 997         }
 998       }
 999
1000       OS << "    MachineInstr &NewI = " << RecycleVarName << ";\n";
1001       return;
1002     }
1003
1004     // TODO: Simple permutation looks like it could be almost as common as
1005     //       mutation due to commutative operations.
1006
1007     OS << "MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, "
1008           "I.getDebugLoc(), TII.get("
1009        << I->Namespace << "::" << I->TheDef->getName() << "));\n";
1010     for (const auto &Renderer : OperandRenderers)
1011       Renderer->emitCxxRenderStmts(OS, Rule);
1012     OS << "    for (const auto *FromMI : ";
1013     Rule.emitCxxCapturedInsnList(OS);
1014     OS << ")\n";
1015     OS << "      for (const auto &MMO : FromMI->memoperands())\n";
1016     OS << "        MIB.addMemOperand(MMO);\n";
1017     OS << "    " << RecycleVarName << ".eraseFromParent();\n";
1018     OS << "    MachineInstr &NewI = *MIB;\n";
1019   }
1020 };
1021
1022 InstructionMatcher &RuleMatcher::addInstructionMatcher() {
1023   Matchers.emplace_back(new InstructionMatcher());
1024   return *Matchers.back();
1025 }
1026
1027 void RuleMatcher::addRequiredFeature(Record *Feature) {
1028   RequiredFeatures.push_back(Feature);
1029 }
1030
1031 template <class Kind, class... Args>
1032 Kind &RuleMatcher::addAction(Args &&... args) {
1033   Actions.emplace_back(llvm::make_unique<Kind>(std::forward<Args>(args)...));
1034   return *static_cast<Kind *>(Actions.back().get());
1035 }
1036
1037 std::string RuleMatcher::defineInsnVar(raw_ostream &OS,
1038                                        const InstructionMatcher &Matcher,
1039                                        StringRef Value) {
1040   std::string InsnVarName = "MI" + llvm::to_string(NextInsnVarID++);
1041   OS << "MachineInstr &" << InsnVarName << " = " << Value << ";\n";
1042   InsnVariableNames[&Matcher] = InsnVarName;
1043   return InsnVarName;
1044 }
1045
1046 StringRef RuleMatcher::getInsnVarName(const InstructionMatcher &InsnMatcher) const {
1047   const auto &I = InsnVariableNames.find(&InsnMatcher);
1048   if (I != InsnVariableNames.end())
1049     return I->second;
1050   llvm_unreachable("Matched Insn was not captured in a local variable");
1051 }
1052
1053 /// Emit a C++ initializer_list containing references to every matched instruction.
1054 void RuleMatcher::emitCxxCapturedInsnList(raw_ostream &OS) {
1055   SmallVector<StringRef, 2> Names;
1056   for (const auto &Pair : InsnVariableNames)
1057     Names.push_back(Pair.second);
1058   std::sort(Names.begin(), Names.end());
1059
1060   OS << "{";
1061   for (const auto &Name : Names)
1062     OS << "&" << Name << ", ";
1063   OS << "}";
1064 }
1065
1066 /// Emit C++ statements to check the shape of the match and capture
1067 /// instructions into local variables.
1068 void RuleMatcher::emitCxxCaptureStmts(raw_ostream &OS, StringRef Expr) {
1069   assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
1070   std::string InsnVarName = defineInsnVar(OS, *Matchers.front(), Expr);
1071   Matchers.front()->emitCxxCaptureStmts(OS, *this, InsnVarName);
1072 }
1073
1074 void RuleMatcher::emit(raw_ostream &OS,
1075                        std::map<Record *, SubtargetFeatureInfo, LessRecordByID>
1076                            SubtargetFeatures) {
1077   if (Matchers.empty())
1078     llvm_unreachable("Unexpected empty matcher!");
1079
1080   // The representation supports rules that require multiple roots such as:
1081   //    %ptr(p0) = ...
1082   //    %elt0(s32) = G_LOAD %ptr
1083   //    %1(p0) = G_ADD %ptr, 4
1084   //    %elt1(s32) = G_LOAD p0 %1
1085   // which could be usefully folded into:
1086   //    %ptr(p0) = ...
1087   //    %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr
1088   // on some targets but we don't need to make use of that yet.
1089   assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
1090
1091   OS << "if (";
1092   OS << "[&]() {\n";
1093   if (!RequiredFeatures.empty()) {
1094     OS << "  PredicateBitset ExpectedFeatures = {";
1095     StringRef Separator = "";
1096     for (const auto &Predicate : RequiredFeatures) {
1097       const auto &I = SubtargetFeatures.find(Predicate);
1098       assert(I != SubtargetFeatures.end() && "Didn't import predicate?");
1099       OS << Separator << I->second.getEnumBitName();
1100       Separator = ", ";
1101     }
1102     OS << "};\n";
1103     OS << "if ((AvailableFeatures & ExpectedFeatures) != ExpectedFeatures)\n"
1104        << "  return false;\n";
1105   }
1106
1107   emitCxxCaptureStmts(OS, "I");
1108
1109   OS << "    if (";
1110   Matchers.front()->emitCxxPredicateExpr(OS, *this,
1111                                          getInsnVarName(*Matchers.front()));
1112   OS << ") {\n";
1113
1114   // We must also check if it's safe to fold the matched instructions.
1115   if (InsnVariableNames.size() >= 2) {
1116     for (const auto &Pair : InsnVariableNames) {
1117       // Skip the root node since it isn't moving anywhere. Everything else is
1118       // sinking to meet it.
1119       if (Pair.first == Matchers.front().get())
1120         continue;
1121
1122       // Reject the difficult cases until we have a more accurate check.
1123       OS << "      if (!isObviouslySafeToFold(" << Pair.second
1124          << ")) return false;\n";
1125
1126       // FIXME: Emit checks to determine it's _actually_ safe to fold and/or
1127       //        account for unsafe cases.
1128       //
1129       //        Example:
1130       //          MI1--> %0 = ...
1131       //                 %1 = ... %0
1132       //          MI0--> %2 = ... %0
1133       //          It's not safe to erase MI1. We currently handle this by not
1134       //          erasing %0 (even when it's dead).
1135       //
1136       //        Example:
1137       //          MI1--> %0 = load volatile @a
1138       //                 %1 = load volatile @a
1139       //          MI0--> %2 = ... %0
1140       //          It's not safe to sink %0's def past %1. We currently handle
1141       //          this by rejecting all loads.
1142       //
1143       //        Example:
1144       //          MI1--> %0 = load @a
1145       //                 %1 = store @a
1146       //          MI0--> %2 = ... %0
1147       //          It's not safe to sink %0's def past %1. We currently handle
1148       //          this by rejecting all loads.
1149       //
1150       //        Example:
1151       //                   G_CONDBR %cond, @BB1
1152       //                 BB0:
1153       //          MI1-->   %0 = load @a
1154       //                   G_BR @BB1
1155       //                 BB1:
1156       //          MI0-->   %2 = ... %0
1157       //          It's not always safe to sink %0 across control flow. In this
1158       //          case it may introduce a memory fault. We currentl handle this
1159       //          by rejecting all loads.
1160     }
1161   }
1162
1163   for (const auto &MA : Actions) {
1164     MA->emitCxxActionStmts(OS, *this, "I");
1165   }
1166
1167   OS << "      constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);\n";
1168   OS << "      return true;\n";
1169   OS << "    }\n";
1170   OS << "    return false;\n";
1171   OS << "  }()) { return true; }\n\n";
1172 }
1173
1174 bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
1175   // Rules involving more match roots have higher priority.
1176   if (Matchers.size() > B.Matchers.size())
1177     return true;
1178   if (Matchers.size() < B.Matchers.size())
1179     return false;
1180
1181   for (const auto &Matcher : zip(Matchers, B.Matchers)) {
1182     if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher)))
1183       return true;
1184     if (std::get<1>(Matcher)->isHigherPriorityThan(*std::get<0>(Matcher)))
1185       return false;
1186   }
1187
1188   return false;
1189 }
1190
1191 unsigned RuleMatcher::countRendererFns() const {
1192   return std::accumulate(
1193       Matchers.begin(), Matchers.end(), 0,
1194       [](unsigned A, const std::unique_ptr<InstructionMatcher> &Matcher) {
1195         return A + Matcher->countRendererFns();
1196       });
1197 }
1198
1199 //===- GlobalISelEmitter class --------------------------------------------===//
1200
1201 class GlobalISelEmitter {
1202 public:
1203   explicit GlobalISelEmitter(RecordKeeper &RK);
1204   void run(raw_ostream &OS);
1205
1206 private:
1207   const RecordKeeper &RK;
1208   const CodeGenDAGPatterns CGP;
1209   const CodeGenTarget &Target;
1210
1211   /// Keep track of the equivalence between SDNodes and Instruction.
1212   /// This is defined using 'GINodeEquiv' in the target description.
1213   DenseMap<Record *, const CodeGenInstruction *> NodeEquivs;
1214
1215   /// Keep track of the equivalence between ComplexPattern's and
1216   /// GIComplexOperandMatcher. Map entries are specified by subclassing
1217   /// GIComplexPatternEquiv.
1218   DenseMap<const Record *, const Record *> ComplexPatternEquivs;
1219
1220   // Map of predicates to their subtarget features.
1221   std::map<Record *, SubtargetFeatureInfo, LessRecordByID> SubtargetFeatures;
1222
1223   void gatherNodeEquivs();
1224   const CodeGenInstruction *findNodeEquiv(Record *N) const;
1225
1226   Error importRulePredicates(RuleMatcher &M, ArrayRef<Init *> Predicates);
1227   Expected<InstructionMatcher &>
1228   createAndImportSelDAGMatcher(InstructionMatcher &InsnMatcher,
1229                                const TreePatternNode *Src) const;
1230   Error importChildMatcher(InstructionMatcher &InsnMatcher,
1231                            TreePatternNode *SrcChild, unsigned OpIdx,
1232                            unsigned &TempOpIdx) const;
1233   Expected<BuildMIAction &> createAndImportInstructionRenderer(
1234       RuleMatcher &M, const TreePatternNode *Dst,
1235       const InstructionMatcher &InsnMatcher) const;
1236   Error importExplicitUseRenderer(BuildMIAction &DstMIBuilder,
1237                                   TreePatternNode *DstChild,
1238                                   const InstructionMatcher &InsnMatcher) const;
1239   Error
1240   importImplicitDefRenderers(BuildMIAction &DstMIBuilder,
1241                              const std::vector<Record *> &ImplicitDefs) const;
1242
1243   /// Analyze pattern \p P, returning a matcher for it if possible.
1244   /// Otherwise, return an Error explaining why we don't support it.
1245   Expected<RuleMatcher> runOnPattern(const PatternToMatch &P);
1246
1247   void declareSubtargetFeature(Record *Predicate);
1248 };
1249
1250 void GlobalISelEmitter::gatherNodeEquivs() {
1251   assert(NodeEquivs.empty());
1252   for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
1253     NodeEquivs[Equiv->getValueAsDef("Node")] =
1254         &Target.getInstruction(Equiv->getValueAsDef("I"));
1255
1256   assert(ComplexPatternEquivs.empty());
1257   for (Record *Equiv : RK.getAllDerivedDefinitions("GIComplexPatternEquiv")) {
1258     Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
1259     if (!SelDAGEquiv)
1260       continue;
1261     ComplexPatternEquivs[SelDAGEquiv] = Equiv;
1262  }
1263 }
1264
1265 const CodeGenInstruction *GlobalISelEmitter::findNodeEquiv(Record *N) const {
1266   return NodeEquivs.lookup(N);
1267 }
1268
1269 GlobalISelEmitter::GlobalISelEmitter(RecordKeeper &RK)
1270     : RK(RK), CGP(RK), Target(CGP.getTargetInfo()) {}
1271
1272 //===- Emitter ------------------------------------------------------------===//
1273
1274 Error
1275 GlobalISelEmitter::importRulePredicates(RuleMatcher &M,
1276                                         ArrayRef<Init *> Predicates) {
1277   for (const Init *Predicate : Predicates) {
1278     const DefInit *PredicateDef = static_cast<const DefInit *>(Predicate);
1279     declareSubtargetFeature(PredicateDef->getDef());
1280     M.addRequiredFeature(PredicateDef->getDef());
1281   }
1282
1283   return Error::success();
1284 }
1285
1286 Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher(
1287     InstructionMatcher &InsnMatcher, const TreePatternNode *Src) const {
1288   // Start with the defined operands (i.e., the results of the root operator).
1289   if (Src->getExtTypes().size() > 1)
1290     return failedImport("Src pattern has multiple results");
1291
1292   auto SrcGIOrNull = findNodeEquiv(Src->getOperator());
1293   if (!SrcGIOrNull)
1294     return failedImport("Pattern operator lacks an equivalent Instruction" +
1295                         explainOperator(Src->getOperator()));
1296   auto &SrcGI = *SrcGIOrNull;
1297
1298   // The operators look good: match the opcode and mutate it to the new one.
1299   InsnMatcher.addPredicate<InstructionOpcodeMatcher>(&SrcGI);
1300
1301   unsigned OpIdx = 0;
1302   unsigned TempOpIdx = 0;
1303   for (const EEVT::TypeSet &Ty : Src->getExtTypes()) {
1304     auto OpTyOrNone = MVTToLLT(Ty.getConcrete());
1305
1306     if (!OpTyOrNone)
1307       return failedImport(
1308           "Result of Src pattern operator has an unsupported type");
1309
1310     // Results don't have a name unless they are the root node. The caller will
1311     // set the name if appropriate.
1312     OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
1313     OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
1314   }
1315
1316   // Match the used operands (i.e. the children of the operator).
1317   for (unsigned i = 0, e = Src->getNumChildren(); i != e; ++i) {
1318     if (auto Error = importChildMatcher(InsnMatcher, Src->getChild(i), OpIdx++,
1319                                         TempOpIdx))
1320       return std::move(Error);
1321   }
1322
1323   return InsnMatcher;
1324 }
1325
1326 Error GlobalISelEmitter::importChildMatcher(InstructionMatcher &InsnMatcher,
1327                                             TreePatternNode *SrcChild,
1328                                             unsigned OpIdx,
1329                                             unsigned &TempOpIdx) const {
1330   OperandMatcher &OM =
1331       InsnMatcher.addOperand(OpIdx, SrcChild->getName(), TempOpIdx);
1332
1333   if (SrcChild->hasAnyPredicate())
1334     return failedImport("Src pattern child has predicate (" +
1335                         explainPredicates(SrcChild) + ")");
1336
1337   ArrayRef<EEVT::TypeSet> ChildTypes = SrcChild->getExtTypes();
1338   if (ChildTypes.size() != 1)
1339     return failedImport("Src pattern child has multiple results");
1340
1341   // Check MBB's before the type check since they are not a known type.
1342   if (!SrcChild->isLeaf()) {
1343     if (SrcChild->getOperator()->isSubClassOf("SDNode")) {
1344       auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator());
1345       if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
1346         OM.addPredicate<MBBOperandMatcher>();
1347         return Error::success();
1348       }
1349     }
1350   }
1351
1352   auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete());
1353   if (!OpTyOrNone)
1354     return failedImport("Src operand has an unsupported type");
1355   OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
1356
1357   // Check for nested instructions.
1358   if (!SrcChild->isLeaf()) {
1359     // Map the node to a gMIR instruction.
1360     InstructionOperandMatcher &InsnOperand =
1361         OM.addPredicate<InstructionOperandMatcher>();
1362     auto InsnMatcherOrError =
1363         createAndImportSelDAGMatcher(InsnOperand.getInsnMatcher(), SrcChild);
1364     if (auto Error = InsnMatcherOrError.takeError())
1365       return Error;
1366
1367     return Error::success();
1368   }
1369
1370   // Check for constant immediates.
1371   if (auto *ChildInt = dyn_cast<IntInit>(SrcChild->getLeafValue())) {
1372     OM.addPredicate<IntOperandMatcher>(ChildInt->getValue());
1373     return Error::success();
1374   }
1375
1376   // Check for def's like register classes or ComplexPattern's.
1377   if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
1378     auto *ChildRec = ChildDefInit->getDef();
1379
1380     // Check for register classes.
1381     if (ChildRec->isSubClassOf("RegisterClass")) {
1382       OM.addPredicate<RegisterBankOperandMatcher>(
1383           Target.getRegisterClass(ChildRec));
1384       return Error::success();
1385     }
1386
1387     if (ChildRec->isSubClassOf("RegisterOperand")) {
1388       OM.addPredicate<RegisterBankOperandMatcher>(
1389           Target.getRegisterClass(ChildRec->getValueAsDef("RegClass")));
1390       return Error::success();
1391     }
1392
1393     // Check for ComplexPattern's.
1394     if (ChildRec->isSubClassOf("ComplexPattern")) {
1395       const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
1396       if (ComplexPattern == ComplexPatternEquivs.end())
1397         return failedImport("SelectionDAG ComplexPattern (" +
1398                             ChildRec->getName() + ") not mapped to GlobalISel");
1399
1400       OM.addPredicate<ComplexPatternOperandMatcher>(OM,
1401                                                     *ComplexPattern->second);
1402       TempOpIdx++;
1403       return Error::success();
1404     }
1405
1406     if (ChildRec->isSubClassOf("ImmLeaf")) {
1407       return failedImport(
1408           "Src pattern child def is an unsupported tablegen class (ImmLeaf)");
1409     }
1410
1411     return failedImport(
1412         "Src pattern child def is an unsupported tablegen class");
1413   }
1414
1415   return failedImport("Src pattern child is an unsupported kind");
1416 }
1417
1418 Error GlobalISelEmitter::importExplicitUseRenderer(
1419     BuildMIAction &DstMIBuilder, TreePatternNode *DstChild,
1420     const InstructionMatcher &InsnMatcher) const {
1421   // The only non-leaf child we accept is 'bb': it's an operator because
1422   // BasicBlockSDNode isn't inline, but in MI it's just another operand.
1423   if (!DstChild->isLeaf()) {
1424     if (DstChild->getOperator()->isSubClassOf("SDNode")) {
1425       auto &ChildSDNI = CGP.getSDNodeInfo(DstChild->getOperator());
1426       if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
1427         DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher,
1428                                                DstChild->getName());
1429         return Error::success();
1430       }
1431     }
1432     return failedImport("Dst pattern child isn't a leaf node or an MBB");
1433   }
1434
1435   // Otherwise, we're looking for a bog-standard RegisterClass operand.
1436   if (DstChild->hasAnyPredicate())
1437     return failedImport("Dst pattern child has predicate (" +
1438                         explainPredicates(DstChild) + ")");
1439
1440   if (auto *ChildDefInit = dyn_cast<DefInit>(DstChild->getLeafValue())) {
1441     auto *ChildRec = ChildDefInit->getDef();
1442
1443     ArrayRef<EEVT::TypeSet> ChildTypes = DstChild->getExtTypes();
1444     if (ChildTypes.size() != 1)
1445       return failedImport("Dst pattern child has multiple results");
1446
1447     auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete());
1448     if (!OpTyOrNone)
1449       return failedImport("Dst operand has an unsupported type");
1450
1451     if (ChildRec->isSubClassOf("Register")) {
1452       DstMIBuilder.addRenderer<AddRegisterRenderer>(ChildRec);
1453       return Error::success();
1454     }
1455
1456     if (ChildRec->isSubClassOf("RegisterClass") ||
1457         ChildRec->isSubClassOf("RegisterOperand")) {
1458       DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher, DstChild->getName());
1459       return Error::success();
1460     }
1461
1462     if (ChildRec->isSubClassOf("ComplexPattern")) {
1463       const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
1464       if (ComplexPattern == ComplexPatternEquivs.end())
1465         return failedImport(
1466             "SelectionDAG ComplexPattern not mapped to GlobalISel");
1467
1468       const OperandMatcher &OM = InsnMatcher.getOperand(DstChild->getName());
1469       DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
1470           *ComplexPattern->second, DstChild->getName(),
1471           OM.getAllocatedTemporariesBaseID());
1472       return Error::success();
1473     }
1474
1475     if (ChildRec->isSubClassOf("SDNodeXForm"))
1476       return failedImport("Dst pattern child def is an unsupported tablegen "
1477                           "class (SDNodeXForm)");
1478
1479     return failedImport(
1480         "Dst pattern child def is an unsupported tablegen class");
1481   }
1482
1483   return failedImport("Dst pattern child is an unsupported kind");
1484 }
1485
1486 Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
1487     RuleMatcher &M, const TreePatternNode *Dst,
1488     const InstructionMatcher &InsnMatcher) const {
1489   Record *DstOp = Dst->getOperator();
1490   if (!DstOp->isSubClassOf("Instruction")) {
1491     if (DstOp->isSubClassOf("ValueType"))
1492       return failedImport(
1493           "Pattern operator isn't an instruction (it's a ValueType)");
1494     return failedImport("Pattern operator isn't an instruction");
1495   }
1496   auto &DstI = Target.getInstruction(DstOp);
1497
1498   auto &DstMIBuilder = M.addAction<BuildMIAction>(&DstI, InsnMatcher);
1499
1500   // Render the explicit defs.
1501   for (unsigned I = 0; I < DstI.Operands.NumDefs; ++I) {
1502     const auto &DstIOperand = DstI.Operands[I];
1503     DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher, DstIOperand.Name);
1504   }
1505
1506   // Figure out which operands need defaults inserted. Operands that subclass
1507   // OperandWithDefaultOps are considered from left to right until we have
1508   // enough operands to render the instruction.
1509   SmallSet<unsigned, 2> DefaultOperands;
1510   unsigned DstINumUses = DstI.Operands.size() - DstI.Operands.NumDefs;
1511   unsigned NumDefaultOperands = 0;
1512   for (unsigned I = 0; I < DstINumUses &&
1513                        DstINumUses > Dst->getNumChildren() + NumDefaultOperands;
1514        ++I) {
1515     const auto &DstIOperand = DstI.Operands[DstI.Operands.NumDefs + I];
1516     if (DstIOperand.Rec->isSubClassOf("OperandWithDefaultOps")) {
1517       DefaultOperands.insert(I);
1518       NumDefaultOperands +=
1519           DstIOperand.Rec->getValueAsDag("DefaultOps")->getNumArgs();
1520     }
1521   }
1522   if (DstINumUses > Dst->getNumChildren() + DefaultOperands.size())
1523     return failedImport("Insufficient operands supplied and default ops "
1524                         "couldn't make up the shortfall");
1525   if (DstINumUses < Dst->getNumChildren() + DefaultOperands.size())
1526     return failedImport("Too many operands supplied");
1527
1528   // Render the explicit uses.
1529   unsigned Child = 0;
1530   for (unsigned I = 0; I != DstINumUses; ++I) {
1531     // If we need to insert default ops here, then do so.
1532     if (DefaultOperands.count(I)) {
1533       const auto &DstIOperand = DstI.Operands[DstI.Operands.NumDefs + I];
1534
1535       DagInit *DefaultOps = DstIOperand.Rec->getValueAsDag("DefaultOps");
1536       for (const auto *DefaultOp : DefaultOps->args()) {
1537         // Look through ValueType operators.
1538         if (const DagInit *DefaultDagOp = dyn_cast<DagInit>(DefaultOp)) {
1539           if (const DefInit *DefaultDagOperator =
1540                   dyn_cast<DefInit>(DefaultDagOp->getOperator())) {
1541             if (DefaultDagOperator->getDef()->isSubClassOf("ValueType"))
1542               DefaultOp = DefaultDagOp->getArg(0);
1543           }
1544         }
1545
1546         if (const DefInit *DefaultDefOp = dyn_cast<DefInit>(DefaultOp)) {
1547           DstMIBuilder.addRenderer<AddRegisterRenderer>(DefaultDefOp->getDef());
1548           continue;
1549         }
1550
1551         if (const IntInit *DefaultIntOp = dyn_cast<IntInit>(DefaultOp)) {
1552           DstMIBuilder.addRenderer<ImmRenderer>(DefaultIntOp->getValue());
1553           continue;
1554         }
1555
1556         return failedImport("Could not add default op");
1557       }
1558
1559       continue;
1560     }
1561
1562     if (auto Error = importExplicitUseRenderer(
1563             DstMIBuilder, Dst->getChild(Child), InsnMatcher))
1564       return std::move(Error);
1565     ++Child;
1566   }
1567
1568   return DstMIBuilder;
1569 }
1570
1571 Error GlobalISelEmitter::importImplicitDefRenderers(
1572     BuildMIAction &DstMIBuilder,
1573     const std::vector<Record *> &ImplicitDefs) const {
1574   if (!ImplicitDefs.empty())
1575     return failedImport("Pattern defines a physical register");
1576   return Error::success();
1577 }
1578
1579 Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
1580   // Keep track of the matchers and actions to emit.
1581   RuleMatcher M;
1582   M.addAction<DebugCommentAction>(P);
1583
1584   if (auto Error = importRulePredicates(M, P.getPredicates()->getValues()))
1585     return std::move(Error);
1586
1587   // Next, analyze the pattern operators.
1588   TreePatternNode *Src = P.getSrcPattern();
1589   TreePatternNode *Dst = P.getDstPattern();
1590
1591   // If the root of either pattern isn't a simple operator, ignore it.
1592   if (auto Err = isTrivialOperatorNode(Dst))
1593     return failedImport("Dst pattern root isn't a trivial operator (" +
1594                         toString(std::move(Err)) + ")");
1595   if (auto Err = isTrivialOperatorNode(Src))
1596     return failedImport("Src pattern root isn't a trivial operator (" +
1597                         toString(std::move(Err)) + ")");
1598
1599   // Start with the defined operands (i.e., the results of the root operator).
1600   Record *DstOp = Dst->getOperator();
1601   if (!DstOp->isSubClassOf("Instruction"))
1602     return failedImport("Pattern operator isn't an instruction");
1603
1604   auto &DstI = Target.getInstruction(DstOp);
1605   if (DstI.Operands.NumDefs != Src->getExtTypes().size())
1606     return failedImport("Src pattern results and dst MI defs are different (" +
1607                         to_string(Src->getExtTypes().size()) + " def(s) vs " +
1608                         to_string(DstI.Operands.NumDefs) + " def(s))");
1609
1610   InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher();
1611   auto InsnMatcherOrError = createAndImportSelDAGMatcher(InsnMatcherTemp, Src);
1612   if (auto Error = InsnMatcherOrError.takeError())
1613     return std::move(Error);
1614   InstructionMatcher &InsnMatcher = InsnMatcherOrError.get();
1615
1616   // The root of the match also has constraints on the register bank so that it
1617   // matches the result instruction.
1618   unsigned OpIdx = 0;
1619   for (const EEVT::TypeSet &Ty : Src->getExtTypes()) {
1620     (void)Ty;
1621
1622     const auto &DstIOperand = DstI.Operands[OpIdx];
1623     Record *DstIOpRec = DstIOperand.Rec;
1624     if (DstIOpRec->isSubClassOf("RegisterOperand"))
1625       DstIOpRec = DstIOpRec->getValueAsDef("RegClass");
1626     if (!DstIOpRec->isSubClassOf("RegisterClass"))
1627       return failedImport("Dst MI def isn't a register class");
1628
1629     OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
1630     OM.setSymbolicName(DstIOperand.Name);
1631     OM.addPredicate<RegisterBankOperandMatcher>(
1632         Target.getRegisterClass(DstIOpRec));
1633     ++OpIdx;
1634   }
1635
1636   auto DstMIBuilderOrError =
1637       createAndImportInstructionRenderer(M, Dst, InsnMatcher);
1638   if (auto Error = DstMIBuilderOrError.takeError())
1639     return std::move(Error);
1640   BuildMIAction &DstMIBuilder = DstMIBuilderOrError.get();
1641
1642   // Render the implicit defs.
1643   // These are only added to the root of the result.
1644   if (auto Error = importImplicitDefRenderers(DstMIBuilder, P.getDstRegs()))
1645     return std::move(Error);
1646
1647   // We're done with this pattern!  It's eligible for GISel emission; return it.
1648   ++NumPatternImported;
1649   return std::move(M);
1650 }
1651
1652 void GlobalISelEmitter::run(raw_ostream &OS) {
1653   // Track the GINodeEquiv definitions.
1654   gatherNodeEquivs();
1655
1656   emitSourceFileHeader(("Global Instruction Selector for the " +
1657                        Target.getName() + " target").str(), OS);
1658   std::vector<RuleMatcher> Rules;
1659   // Look through the SelectionDAG patterns we found, possibly emitting some.
1660   for (const PatternToMatch &Pat : CGP.ptms()) {
1661     ++NumPatternTotal;
1662     auto MatcherOrErr = runOnPattern(Pat);
1663
1664     // The pattern analysis can fail, indicating an unsupported pattern.
1665     // Report that if we've been asked to do so.
1666     if (auto Err = MatcherOrErr.takeError()) {
1667       if (WarnOnSkippedPatterns) {
1668         PrintWarning(Pat.getSrcRecord()->getLoc(),
1669                      "Skipped pattern: " + toString(std::move(Err)));
1670       } else {
1671         consumeError(std::move(Err));
1672       }
1673       ++NumPatternImportsSkipped;
1674       continue;
1675     }
1676
1677     Rules.push_back(std::move(MatcherOrErr.get()));
1678   }
1679
1680   std::stable_sort(Rules.begin(), Rules.end(),
1681             [&](const RuleMatcher &A, const RuleMatcher &B) {
1682               if (A.isHigherPriorityThan(B)) {
1683                 assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
1684                                                      "and less important at "
1685                                                      "the same time");
1686                 return true;
1687               }
1688               return false;
1689             });
1690
1691   unsigned MaxTemporaries = 0;
1692   for (const auto &Rule : Rules)
1693     MaxTemporaries = std::max(MaxTemporaries, Rule.countRendererFns());
1694
1695   OS << "#ifdef GET_GLOBALISEL_PREDICATE_BITSET\n"
1696      << "const unsigned MAX_SUBTARGET_PREDICATES = " << SubtargetFeatures.size()
1697      << ";\n"
1698      << "using PredicateBitset = "
1699         "llvm::PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;\n"
1700      << "#endif // ifdef GET_GLOBALISEL_PREDICATE_BITSET\n\n";
1701
1702   OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n";
1703   for (unsigned I = 0; I < MaxTemporaries; ++I)
1704     OS << "  mutable ComplexRendererFn Renderer" << I << ";\n";
1705   OS << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n";
1706
1707   OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n";
1708   for (unsigned I = 0; I < MaxTemporaries; ++I)
1709     OS << ", Renderer" << I << "(nullptr)\n";
1710   OS << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";
1711
1712   OS << "#ifdef GET_GLOBALISEL_IMPL\n";
1713   SubtargetFeatureInfo::emitSubtargetFeatureBitEnumeration(SubtargetFeatures,
1714                                                            OS);
1715   SubtargetFeatureInfo::emitNameTable(SubtargetFeatures, OS);
1716   SubtargetFeatureInfo::emitComputeAvailableFeatures(
1717       Target.getName(), "InstructionSelector", "computeAvailableFeatures",
1718       SubtargetFeatures, OS);
1719
1720   OS << "bool " << Target.getName()
1721      << "InstructionSelector::selectImpl(MachineInstr &I) const {\n"
1722      << "  MachineFunction &MF = *I.getParent()->getParent();\n"
1723      << "  const MachineRegisterInfo &MRI = MF.getRegInfo();\n";
1724
1725   for (auto &Rule : Rules) {
1726     Rule.emit(OS, SubtargetFeatures);
1727     ++NumPatternEmitted;
1728   }
1729
1730   OS << "  return false;\n"
1731      << "}\n"
1732      << "#endif // ifdef GET_GLOBALISEL_IMPL\n";
1733 }
1734
1735 void GlobalISelEmitter::declareSubtargetFeature(Record *Predicate) {
1736   if (SubtargetFeatures.count(Predicate) == 0)
1737     SubtargetFeatures.emplace(
1738         Predicate, SubtargetFeatureInfo(Predicate, SubtargetFeatures.size()));
1739 }
1740
1741 } // end anonymous namespace
1742
1743 //===----------------------------------------------------------------------===//
1744
1745 namespace llvm {
1746 void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS) {
1747   GlobalISelEmitter(RK).run(OS);
1748 }
1749 } // End llvm namespace