contrib/llvm/utils/TableGen/GlobalISelEmitter.cpp

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