1 //===- GlobalISelEmitter.cpp - Generate an instruction selector -----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// This tablegen backend emits code for use by the GlobalISel instruction
12 /// selector. See include/llvm/CodeGen/TargetGlobalISel.td.
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).
19 /// Not all patterns are supported: pass the tablegen invocation
20 /// "-warn-on-skipped-patterns" to emit a warning when a pattern is skipped,
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++.
28 /// FIXME: We'll probably want to eventually define a base
29 /// "TargetGenInstructionSelector" class.
31 //===----------------------------------------------------------------------===//
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"
50 #define DEBUG_TYPE "gisel-emitter"
52 STATISTIC(NumPatternTotal, "Total number of patterns");
53 STATISTIC(NumPatternImported, "Number of patterns imported from SelectionDAG");
54 STATISTIC(NumPatternImportsSkipped, "Number of SelectionDAG imports skipped");
55 STATISTIC(NumPatternEmitted, "Number of patterns emitted");
56 /// A unique identifier for a MatchTable.
57 static unsigned CurrentMatchTableID = 0;
59 cl::OptionCategory GlobalISelEmitterCat("Options for -gen-global-isel");
61 static cl::opt<bool> WarnOnSkippedPatterns(
62 "warn-on-skipped-patterns",
63 cl::desc("Explain why a pattern was skipped for inclusion "
64 "in the GlobalISel selector"),
65 cl::init(false), cl::cat(GlobalISelEmitterCat));
68 //===- Helper functions ---------------------------------------------------===//
70 /// This class stands in for LLT wherever we want to tablegen-erate an
71 /// equivalent at compiler run-time.
77 LLTCodeGen(const LLT &Ty) : Ty(Ty) {}
79 void emitCxxEnumValue(raw_ostream &OS) const {
81 OS << "GILLT_s" << Ty.getSizeInBits();
85 OS << "GILLT_v" << Ty.getNumElements() << "s" << Ty.getScalarSizeInBits();
88 llvm_unreachable("Unhandled LLT");
91 void emitCxxConstructorCall(raw_ostream &OS) const {
93 OS << "LLT::scalar(" << Ty.getSizeInBits() << ")";
97 OS << "LLT::vector(" << Ty.getNumElements() << ", "
98 << Ty.getScalarSizeInBits() << ")";
101 llvm_unreachable("Unhandled LLT");
104 const LLT &get() const { return Ty; }
106 /// This ordering is used for std::unique() and std::sort(). There's no
107 /// particular logic behind the order.
108 bool operator<(const LLTCodeGen &Other) const {
110 return Other.Ty.isValid();
112 if (!Other.Ty.isValid())
114 if (Other.Ty.isScalar())
115 return Ty.getSizeInBits() < Other.Ty.getSizeInBits();
119 if (!Other.Ty.isValid() || Other.Ty.isScalar())
121 if (Other.Ty.isVector()) {
122 if (Ty.getNumElements() < Other.Ty.getNumElements())
124 if (Ty.getNumElements() > Other.Ty.getNumElements())
126 return Ty.getSizeInBits() < Other.Ty.getSizeInBits();
130 llvm_unreachable("Unhandled LLT");
134 class InstructionMatcher;
135 /// Convert an MVT to an equivalent LLT if possible, or the invalid LLT() for
136 /// MVTs that don't map cleanly to an LLT (e.g., iPTR, *any, ...).
137 static Optional<LLTCodeGen> MVTToLLT(MVT::SimpleValueType SVT) {
139 if (VT.isVector() && VT.getVectorNumElements() != 1)
141 LLT::vector(VT.getVectorNumElements(), VT.getScalarSizeInBits()));
142 if (VT.isInteger() || VT.isFloatingPoint())
143 return LLTCodeGen(LLT::scalar(VT.getSizeInBits()));
147 static std::string explainPredicates(const TreePatternNode *N) {
148 std::string Explanation = "";
149 StringRef Separator = "";
150 for (const auto &P : N->getPredicateFns()) {
152 (Separator + P.getOrigPatFragRecord()->getRecord()->getName()).str();
153 if (P.isAlwaysTrue())
154 Explanation += " always-true";
155 if (P.isImmediatePattern())
156 Explanation += " immediate";
161 std::string explainOperator(Record *Operator) {
162 if (Operator->isSubClassOf("SDNode"))
163 return (" (" + Operator->getValueAsString("Opcode") + ")").str();
165 if (Operator->isSubClassOf("Intrinsic"))
166 return (" (Operator is an Intrinsic, " + Operator->getName() + ")").str();
168 return " (Operator not understood)";
171 /// Helper function to let the emitter report skip reason error messages.
172 static Error failedImport(const Twine &Reason) {
173 return make_error<StringError>(Reason, inconvertibleErrorCode());
176 static Error isTrivialOperatorNode(const TreePatternNode *N) {
177 std::string Explanation = "";
178 std::string Separator = "";
180 if (isa<IntInit>(N->getLeafValue()))
181 return Error::success();
183 Explanation = "Is a leaf";
187 if (N->hasAnyPredicate()) {
188 Explanation = Separator + "Has a predicate (" + explainPredicates(N) + ")";
192 if (N->getTransformFn()) {
193 Explanation += Separator + "Has a transform function";
197 if (!N->isLeaf() && !N->hasAnyPredicate() && !N->getTransformFn())
198 return Error::success();
200 return failedImport(Explanation);
203 static Record *getInitValueAsRegClass(Init *V) {
204 if (DefInit *VDefInit = dyn_cast<DefInit>(V)) {
205 if (VDefInit->getDef()->isSubClassOf("RegisterOperand"))
206 return VDefInit->getDef()->getValueAsDef("RegClass");
207 if (VDefInit->getDef()->isSubClassOf("RegisterClass"))
208 return VDefInit->getDef();
214 getNameForFeatureBitset(const std::vector<Record *> &FeatureBitset) {
215 std::string Name = "GIFBS";
216 for (const auto &Feature : FeatureBitset)
217 Name += ("_" + Feature->getName()).str();
220 //===- Matchers -----------------------------------------------------------===//
222 class OperandMatcher;
225 /// Generates code to check that a match rule matches.
227 /// A list of matchers that all need to succeed for the current rule to match.
228 /// FIXME: This currently supports a single match position but could be
229 /// extended to support multiple positions to support div/rem fusion or
230 /// load-multiple instructions.
231 std::vector<std::unique_ptr<InstructionMatcher>> Matchers;
233 /// A list of actions that need to be taken when all predicates in this rule
235 std::vector<std::unique_ptr<MatchAction>> Actions;
237 /// A map of instruction matchers to the local variables created by
238 /// emitCaptureOpcodes().
239 std::map<const InstructionMatcher *, unsigned> InsnVariableIDs;
241 /// ID for the next instruction variable defined with defineInsnVar()
242 unsigned NextInsnVarID;
244 std::vector<Record *> RequiredFeatures;
248 : Matchers(), Actions(), InsnVariableIDs(), NextInsnVarID(0) {}
249 RuleMatcher(RuleMatcher &&Other) = default;
250 RuleMatcher &operator=(RuleMatcher &&Other) = default;
252 InstructionMatcher &addInstructionMatcher();
253 void addRequiredFeature(Record *Feature);
254 const std::vector<Record *> &getRequiredFeatures() const;
256 template <class Kind, class... Args> Kind &addAction(Args &&... args);
258 /// Define an instruction without emitting any code to do so.
259 /// This is used for the root of the match.
260 unsigned implicitlyDefineInsnVar(const InstructionMatcher &Matcher);
261 /// Define an instruction and emit corresponding state-machine opcodes.
262 unsigned defineInsnVar(raw_ostream &OS, const InstructionMatcher &Matcher,
263 unsigned InsnVarID, unsigned OpIdx);
264 unsigned getInsnVarID(const InstructionMatcher &InsnMatcher) const;
266 void emitCaptureOpcodes(raw_ostream &OS);
268 void emit(raw_ostream &OS);
270 /// Compare the priority of this object and B.
272 /// Returns true if this object is more important than B.
273 bool isHigherPriorityThan(const RuleMatcher &B) const;
275 /// Report the maximum number of temporary operands needed by the rule
277 unsigned countRendererFns() const;
279 // FIXME: Remove this as soon as possible
280 InstructionMatcher &insnmatcher_front() const { return *Matchers.front(); }
283 template <class PredicateTy> class PredicateListMatcher {
285 typedef std::vector<std::unique_ptr<PredicateTy>> PredicateVec;
286 PredicateVec Predicates;
289 /// Construct a new operand predicate and add it to the matcher.
290 template <class Kind, class... Args>
291 Kind &addPredicate(Args&&... args) {
292 Predicates.emplace_back(
293 llvm::make_unique<Kind>(std::forward<Args>(args)...));
294 return *static_cast<Kind *>(Predicates.back().get());
297 typename PredicateVec::const_iterator predicates_begin() const {
298 return Predicates.begin();
300 typename PredicateVec::const_iterator predicates_end() const {
301 return Predicates.end();
303 iterator_range<typename PredicateVec::const_iterator> predicates() const {
304 return make_range(predicates_begin(), predicates_end());
306 typename PredicateVec::size_type predicates_size() const {
307 return Predicates.size();
310 /// Emit MatchTable opcodes that tests whether all the predicates are met.
311 template <class... Args>
312 void emitPredicateListOpcodes(raw_ostream &OS, Args &&... args) const {
313 if (Predicates.empty()) {
314 OS << "// No predicates\n";
318 for (const auto &Predicate : predicates())
319 Predicate->emitPredicateOpcodes(OS, std::forward<Args>(args)...);
323 /// Generates code to check a predicate of an operand.
325 /// Typical predicates include:
326 /// * Operand is a particular register.
327 /// * Operand is assigned a particular register bank.
328 /// * Operand is an MBB.
329 class OperandPredicateMatcher {
331 /// This enum is used for RTTI and also defines the priority that is given to
332 /// the predicate when generating the matcher code. Kinds with higher priority
333 /// must be tested first.
335 /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter
336 /// but OPM_Int must have priority over OPM_RegBank since constant integers
337 /// are represented by a virtual register defined by a G_CONSTANT instruction.
353 OperandPredicateMatcher(PredicateKind Kind) : Kind(Kind) {}
354 virtual ~OperandPredicateMatcher() {}
356 PredicateKind getKind() const { return Kind; }
358 /// Return the OperandMatcher for the specified operand or nullptr if there
359 /// isn't one by that name in this operand predicate matcher.
361 /// InstructionOperandMatcher is the only subclass that can return non-null
363 virtual Optional<const OperandMatcher *>
364 getOptionalOperand(StringRef SymbolicName) const {
365 assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
369 /// Emit MatchTable opcodes to capture instructions into the MIs table.
371 /// Only InstructionOperandMatcher needs to do anything for this method the
372 /// rest just walk the tree.
373 virtual void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule,
374 unsigned InsnVarID, unsigned OpIdx) const {}
376 /// Emit MatchTable opcodes that check the predicate for the given operand.
377 virtual void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
379 unsigned OpIdx) const = 0;
381 /// Compare the priority of this object and B.
383 /// Returns true if this object is more important than B.
384 virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const {
385 return Kind < B.Kind;
388 /// Report the maximum number of temporary operands needed by the predicate
390 virtual unsigned countRendererFns() const { return 0; }
393 /// Generates code to check that an operand is a particular LLT.
394 class LLTOperandMatcher : public OperandPredicateMatcher {
399 LLTOperandMatcher(const LLTCodeGen &Ty)
400 : OperandPredicateMatcher(OPM_LLT), Ty(Ty) {}
402 static bool classof(const OperandPredicateMatcher *P) {
403 return P->getKind() == OPM_LLT;
406 void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
407 unsigned InsnVarID, unsigned OpIdx) const override {
408 OS << " GIM_CheckType, /*MI*/" << InsnVarID << ", /*Op*/" << OpIdx
410 Ty.emitCxxEnumValue(OS);
415 /// Generates code to check that an operand is a particular target constant.
416 class ComplexPatternOperandMatcher : public OperandPredicateMatcher {
418 const OperandMatcher &Operand;
419 const Record &TheDef;
421 unsigned getAllocatedTemporariesBaseID() const;
424 ComplexPatternOperandMatcher(const OperandMatcher &Operand,
425 const Record &TheDef)
426 : OperandPredicateMatcher(OPM_ComplexPattern), Operand(Operand),
429 static bool classof(const OperandPredicateMatcher *P) {
430 return P->getKind() == OPM_ComplexPattern;
433 void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
434 unsigned InsnVarID, unsigned OpIdx) const override {
435 unsigned ID = getAllocatedTemporariesBaseID();
436 OS << " GIM_CheckComplexPattern, /*MI*/" << InsnVarID << ", /*Op*/"
437 << OpIdx << ", /*Renderer*/" << ID << ", GICP_"
438 << TheDef.getName() << ",\n";
441 unsigned countRendererFns() const override {
446 /// Generates code to check that an operand is in a particular register bank.
447 class RegisterBankOperandMatcher : public OperandPredicateMatcher {
449 const CodeGenRegisterClass &RC;
452 RegisterBankOperandMatcher(const CodeGenRegisterClass &RC)
453 : OperandPredicateMatcher(OPM_RegBank), RC(RC) {}
455 static bool classof(const OperandPredicateMatcher *P) {
456 return P->getKind() == OPM_RegBank;
459 void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
460 unsigned InsnVarID, unsigned OpIdx) const override {
461 OS << " GIM_CheckRegBankForClass, /*MI*/" << InsnVarID << ", /*Op*/"
462 << OpIdx << ", /*RC*/" << RC.getQualifiedName() << "RegClassID,\n";
466 /// Generates code to check that an operand is a basic block.
467 class MBBOperandMatcher : public OperandPredicateMatcher {
469 MBBOperandMatcher() : OperandPredicateMatcher(OPM_MBB) {}
471 static bool classof(const OperandPredicateMatcher *P) {
472 return P->getKind() == OPM_MBB;
475 void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
476 unsigned InsnVarID, unsigned OpIdx) const override {
477 OS << " GIM_CheckIsMBB, /*MI*/" << InsnVarID << ", /*Op*/" << OpIdx << ",\n";
481 /// Generates code to check that an operand is a G_CONSTANT with a particular
483 class ConstantIntOperandMatcher : public OperandPredicateMatcher {
488 ConstantIntOperandMatcher(int64_t Value)
489 : OperandPredicateMatcher(OPM_Int), Value(Value) {}
491 static bool classof(const OperandPredicateMatcher *P) {
492 return P->getKind() == OPM_Int;
495 void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
496 unsigned InsnVarID, unsigned OpIdx) const override {
497 OS << " GIM_CheckConstantInt, /*MI*/" << InsnVarID << ", /*Op*/"
498 << OpIdx << ", " << Value << ",\n";
502 /// Generates code to check that an operand is a raw int (where MO.isImm() or
503 /// MO.isCImm() is true).
504 class LiteralIntOperandMatcher : public OperandPredicateMatcher {
509 LiteralIntOperandMatcher(int64_t Value)
510 : OperandPredicateMatcher(OPM_LiteralInt), Value(Value) {}
512 static bool classof(const OperandPredicateMatcher *P) {
513 return P->getKind() == OPM_LiteralInt;
516 void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
517 unsigned InsnVarID, unsigned OpIdx) const override {
518 OS << " GIM_CheckLiteralInt, /*MI*/" << InsnVarID << ", /*Op*/"
519 << OpIdx << ", " << Value << ",\n";
523 /// Generates code to check that an operand is an intrinsic ID.
524 class IntrinsicIDOperandMatcher : public OperandPredicateMatcher {
526 const CodeGenIntrinsic *II;
529 IntrinsicIDOperandMatcher(const CodeGenIntrinsic *II)
530 : OperandPredicateMatcher(OPM_IntrinsicID), II(II) {}
532 static bool classof(const OperandPredicateMatcher *P) {
533 return P->getKind() == OPM_IntrinsicID;
536 void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
537 unsigned InsnVarID, unsigned OpIdx) const override {
538 OS << " GIM_CheckIntrinsicID, /*MI*/" << InsnVarID << ", /*Op*/"
539 << OpIdx << ", Intrinsic::" << II->EnumName << ",\n";
543 /// Generates code to check that a set of predicates match for a particular
545 class OperandMatcher : public PredicateListMatcher<OperandPredicateMatcher> {
547 InstructionMatcher &Insn;
549 std::string SymbolicName;
551 /// The index of the first temporary variable allocated to this operand. The
552 /// number of allocated temporaries can be found with
553 /// countRendererFns().
554 unsigned AllocatedTemporariesBaseID;
557 OperandMatcher(InstructionMatcher &Insn, unsigned OpIdx,
558 const std::string &SymbolicName,
559 unsigned AllocatedTemporariesBaseID)
560 : Insn(Insn), OpIdx(OpIdx), SymbolicName(SymbolicName),
561 AllocatedTemporariesBaseID(AllocatedTemporariesBaseID) {}
563 bool hasSymbolicName() const { return !SymbolicName.empty(); }
564 const StringRef getSymbolicName() const { return SymbolicName; }
565 void setSymbolicName(StringRef Name) {
566 assert(SymbolicName.empty() && "Operand already has a symbolic name");
569 unsigned getOperandIndex() const { return OpIdx; }
571 std::string getOperandExpr(unsigned InsnVarID) const {
572 return "State.MIs[" + llvm::to_string(InsnVarID) + "]->getOperand(" +
573 llvm::to_string(OpIdx) + ")";
576 Optional<const OperandMatcher *>
577 getOptionalOperand(StringRef DesiredSymbolicName) const {
578 assert(!DesiredSymbolicName.empty() && "Cannot lookup unnamed operand");
579 if (DesiredSymbolicName == SymbolicName)
581 for (const auto &OP : predicates()) {
582 const auto &MaybeOperand = OP->getOptionalOperand(DesiredSymbolicName);
583 if (MaybeOperand.hasValue())
584 return MaybeOperand.getValue();
589 InstructionMatcher &getInstructionMatcher() const { return Insn; }
591 /// Emit MatchTable opcodes to capture instructions into the MIs table.
592 void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule,
593 unsigned InsnVarID) const {
594 for (const auto &Predicate : predicates())
595 Predicate->emitCaptureOpcodes(OS, Rule, InsnVarID, OpIdx);
598 /// Emit MatchTable opcodes that test whether the instruction named in
599 /// InsnVarID matches all the predicates and all the operands.
600 void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
601 unsigned InsnVarID) const {
602 OS << " // MIs[" << InsnVarID << "] ";
603 if (SymbolicName.empty())
604 OS << "Operand " << OpIdx;
608 emitPredicateListOpcodes(OS, Rule, InsnVarID, OpIdx);
611 /// Compare the priority of this object and B.
613 /// Returns true if this object is more important than B.
614 bool isHigherPriorityThan(const OperandMatcher &B) const {
615 // Operand matchers involving more predicates have higher priority.
616 if (predicates_size() > B.predicates_size())
618 if (predicates_size() < B.predicates_size())
621 // This assumes that predicates are added in a consistent order.
622 for (const auto &Predicate : zip(predicates(), B.predicates())) {
623 if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate)))
625 if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate)))
632 /// Report the maximum number of temporary operands needed by the operand
634 unsigned countRendererFns() const {
635 return std::accumulate(
636 predicates().begin(), predicates().end(), 0,
638 const std::unique_ptr<OperandPredicateMatcher> &Predicate) {
639 return A + Predicate->countRendererFns();
643 unsigned getAllocatedTemporariesBaseID() const {
644 return AllocatedTemporariesBaseID;
648 unsigned ComplexPatternOperandMatcher::getAllocatedTemporariesBaseID() const {
649 return Operand.getAllocatedTemporariesBaseID();
652 /// Generates code to check a predicate on an instruction.
654 /// Typical predicates include:
655 /// * The opcode of the instruction is a particular value.
656 /// * The nsw/nuw flag is/isn't set.
657 class InstructionPredicateMatcher {
659 /// This enum is used for RTTI and also defines the priority that is given to
660 /// the predicate when generating the matcher code. Kinds with higher priority
661 /// must be tested first.
669 InstructionPredicateMatcher(PredicateKind Kind) : Kind(Kind) {}
670 virtual ~InstructionPredicateMatcher() {}
672 PredicateKind getKind() const { return Kind; }
674 /// Emit MatchTable opcodes that test whether the instruction named in
675 /// InsnVarID matches the predicate.
676 virtual void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
677 unsigned InsnVarID) const = 0;
679 /// Compare the priority of this object and B.
681 /// Returns true if this object is more important than B.
683 isHigherPriorityThan(const InstructionPredicateMatcher &B) const {
684 return Kind < B.Kind;
687 /// Report the maximum number of temporary operands needed by the predicate
689 virtual unsigned countRendererFns() const { return 0; }
692 /// Generates code to check the opcode of an instruction.
693 class InstructionOpcodeMatcher : public InstructionPredicateMatcher {
695 const CodeGenInstruction *I;
698 InstructionOpcodeMatcher(const CodeGenInstruction *I)
699 : InstructionPredicateMatcher(IPM_Opcode), I(I) {}
701 static bool classof(const InstructionPredicateMatcher *P) {
702 return P->getKind() == IPM_Opcode;
705 void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
706 unsigned InsnVarID) const override {
707 OS << " GIM_CheckOpcode, /*MI*/" << InsnVarID << ", " << I->Namespace
708 << "::" << I->TheDef->getName() << ",\n";
711 /// Compare the priority of this object and B.
713 /// Returns true if this object is more important than B.
715 isHigherPriorityThan(const InstructionPredicateMatcher &B) const override {
716 if (InstructionPredicateMatcher::isHigherPriorityThan(B))
718 if (B.InstructionPredicateMatcher::isHigherPriorityThan(*this))
721 // Prioritize opcodes for cosmetic reasons in the generated source. Although
722 // this is cosmetic at the moment, we may want to drive a similar ordering
723 // using instruction frequency information to improve compile time.
724 if (const InstructionOpcodeMatcher *BO =
725 dyn_cast<InstructionOpcodeMatcher>(&B))
726 return I->TheDef->getName() < BO->I->TheDef->getName();
732 /// Generates code to check that a set of predicates and operands match for a
733 /// particular instruction.
735 /// Typical predicates include:
736 /// * Has a specific opcode.
737 /// * Has an nsw/nuw flag or doesn't.
738 class InstructionMatcher
739 : public PredicateListMatcher<InstructionPredicateMatcher> {
741 typedef std::vector<std::unique_ptr<OperandMatcher>> OperandVec;
743 /// The operands to match. All rendered operands must be present even if the
744 /// condition is always true.
748 /// Add an operand to the matcher.
749 OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName,
750 unsigned AllocatedTemporariesBaseID) {
751 Operands.emplace_back(new OperandMatcher(*this, OpIdx, SymbolicName,
752 AllocatedTemporariesBaseID));
753 return *Operands.back();
756 OperandMatcher &getOperand(unsigned OpIdx) {
757 auto I = std::find_if(Operands.begin(), Operands.end(),
758 [&OpIdx](const std::unique_ptr<OperandMatcher> &X) {
759 return X->getOperandIndex() == OpIdx;
761 if (I != Operands.end())
763 llvm_unreachable("Failed to lookup operand");
766 Optional<const OperandMatcher *>
767 getOptionalOperand(StringRef SymbolicName) const {
768 assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
769 for (const auto &Operand : Operands) {
770 const auto &OM = Operand->getOptionalOperand(SymbolicName);
772 return OM.getValue();
777 const OperandMatcher &getOperand(StringRef SymbolicName) const {
778 Optional<const OperandMatcher *>OM = getOptionalOperand(SymbolicName);
780 return *OM.getValue();
781 llvm_unreachable("Failed to lookup operand");
784 unsigned getNumOperands() const { return Operands.size(); }
785 OperandVec::iterator operands_begin() { return Operands.begin(); }
786 OperandVec::iterator operands_end() { return Operands.end(); }
787 iterator_range<OperandVec::iterator> operands() {
788 return make_range(operands_begin(), operands_end());
790 OperandVec::const_iterator operands_begin() const { return Operands.begin(); }
791 OperandVec::const_iterator operands_end() const { return Operands.end(); }
792 iterator_range<OperandVec::const_iterator> operands() const {
793 return make_range(operands_begin(), operands_end());
796 /// Emit MatchTable opcodes to check the shape of the match and capture
797 /// instructions into the MIs table.
798 void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule,
800 OS << " GIM_CheckNumOperands, /*MI*/" << InsnID << ", /*Expected*/"
801 << getNumOperands() << ",\n";
802 for (const auto &Operand : Operands)
803 Operand->emitCaptureOpcodes(OS, Rule, InsnID);
806 /// Emit MatchTable opcodes that test whether the instruction named in
807 /// InsnVarName matches all the predicates and all the operands.
808 void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
809 unsigned InsnVarID) const {
810 emitPredicateListOpcodes(OS, Rule, InsnVarID);
811 for (const auto &Operand : Operands)
812 Operand->emitPredicateOpcodes(OS, Rule, InsnVarID);
815 /// Compare the priority of this object and B.
817 /// Returns true if this object is more important than B.
818 bool isHigherPriorityThan(const InstructionMatcher &B) const {
819 // Instruction matchers involving more operands have higher priority.
820 if (Operands.size() > B.Operands.size())
822 if (Operands.size() < B.Operands.size())
825 for (const auto &Predicate : zip(predicates(), B.predicates())) {
826 if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate)))
828 if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate)))
832 for (const auto &Operand : zip(Operands, B.Operands)) {
833 if (std::get<0>(Operand)->isHigherPriorityThan(*std::get<1>(Operand)))
835 if (std::get<1>(Operand)->isHigherPriorityThan(*std::get<0>(Operand)))
842 /// Report the maximum number of temporary operands needed by the instruction
844 unsigned countRendererFns() const {
845 return std::accumulate(predicates().begin(), predicates().end(), 0,
847 const std::unique_ptr<InstructionPredicateMatcher>
849 return A + Predicate->countRendererFns();
852 Operands.begin(), Operands.end(), 0,
853 [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) {
854 return A + Operand->countRendererFns();
859 /// Generates code to check that the operand is a register defined by an
860 /// instruction that matches the given instruction matcher.
862 /// For example, the pattern:
863 /// (set $dst, (G_MUL (G_ADD $src1, $src2), $src3))
864 /// would use an InstructionOperandMatcher for operand 1 of the G_MUL to match
866 /// (G_ADD $src1, $src2)
868 class InstructionOperandMatcher : public OperandPredicateMatcher {
870 std::unique_ptr<InstructionMatcher> InsnMatcher;
873 InstructionOperandMatcher()
874 : OperandPredicateMatcher(OPM_Instruction),
875 InsnMatcher(new InstructionMatcher()) {}
877 static bool classof(const OperandPredicateMatcher *P) {
878 return P->getKind() == OPM_Instruction;
881 InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; }
883 Optional<const OperandMatcher *>
884 getOptionalOperand(StringRef SymbolicName) const override {
885 assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
886 return InsnMatcher->getOptionalOperand(SymbolicName);
889 void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule,
890 unsigned InsnID, unsigned OpIdx) const override {
891 unsigned InsnVarID = Rule.defineInsnVar(OS, *InsnMatcher, InsnID, OpIdx);
892 InsnMatcher->emitCaptureOpcodes(OS, Rule, InsnVarID);
895 void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
897 unsigned OpIdx_) const override {
898 unsigned InsnVarID = Rule.getInsnVarID(*InsnMatcher);
899 InsnMatcher->emitPredicateOpcodes(OS, Rule, InsnVarID);
903 //===- Actions ------------------------------------------------------------===//
904 class OperandRenderer {
918 OperandRenderer(RendererKind Kind) : Kind(Kind) {}
919 virtual ~OperandRenderer() {}
921 RendererKind getKind() const { return Kind; }
923 virtual void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const = 0;
926 /// A CopyRenderer emits code to copy a single operand from an existing
927 /// instruction to the one being built.
928 class CopyRenderer : public OperandRenderer {
931 /// The matcher for the instruction that this operand is copied from.
932 /// This provides the facility for looking up an a operand by it's name so
933 /// that it can be used as a source for the instruction being built.
934 const InstructionMatcher &Matched;
935 /// The name of the operand.
936 const StringRef SymbolicName;
939 CopyRenderer(unsigned NewInsnID, const InstructionMatcher &Matched,
940 StringRef SymbolicName)
941 : OperandRenderer(OR_Copy), NewInsnID(NewInsnID), Matched(Matched),
942 SymbolicName(SymbolicName) {}
944 static bool classof(const OperandRenderer *R) {
945 return R->getKind() == OR_Copy;
948 const StringRef getSymbolicName() const { return SymbolicName; }
950 void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
951 const OperandMatcher &Operand = Matched.getOperand(SymbolicName);
952 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
953 OS << " GIR_Copy, /*NewInsnID*/" << NewInsnID << ", /*OldInsnID*/"
954 << OldInsnVarID << ", /*OpIdx*/" << Operand.getOperandIndex() << ", // "
955 << SymbolicName << "\n";
959 /// A CopySubRegRenderer emits code to copy a single register operand from an
960 /// existing instruction to the one being built and indicate that only a
961 /// subregister should be copied.
962 class CopySubRegRenderer : public OperandRenderer {
965 /// The matcher for the instruction that this operand is copied from.
966 /// This provides the facility for looking up an a operand by it's name so
967 /// that it can be used as a source for the instruction being built.
968 const InstructionMatcher &Matched;
969 /// The name of the operand.
970 const StringRef SymbolicName;
971 /// The subregister to extract.
972 const CodeGenSubRegIndex *SubReg;
975 CopySubRegRenderer(unsigned NewInsnID, const InstructionMatcher &Matched,
976 StringRef SymbolicName, const CodeGenSubRegIndex *SubReg)
977 : OperandRenderer(OR_CopySubReg), NewInsnID(NewInsnID), Matched(Matched),
978 SymbolicName(SymbolicName), SubReg(SubReg) {}
980 static bool classof(const OperandRenderer *R) {
981 return R->getKind() == OR_CopySubReg;
984 const StringRef getSymbolicName() const { return SymbolicName; }
986 void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
987 const OperandMatcher &Operand = Matched.getOperand(SymbolicName);
988 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
989 OS << " GIR_CopySubReg, /*NewInsnID*/" << NewInsnID
990 << ", /*OldInsnID*/" << OldInsnVarID << ", /*OpIdx*/"
991 << Operand.getOperandIndex() << ", /*SubRegIdx*/" << SubReg->EnumValue
992 << ", // " << SymbolicName << "\n";
996 /// Adds a specific physical register to the instruction being built.
997 /// This is typically useful for WZR/XZR on AArch64.
998 class AddRegisterRenderer : public OperandRenderer {
1001 const Record *RegisterDef;
1004 AddRegisterRenderer(unsigned InsnID, const Record *RegisterDef)
1005 : OperandRenderer(OR_Register), InsnID(InsnID), RegisterDef(RegisterDef) {
1008 static bool classof(const OperandRenderer *R) {
1009 return R->getKind() == OR_Register;
1012 void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
1013 OS << " GIR_AddRegister, /*InsnID*/" << InsnID << ", "
1014 << (RegisterDef->getValue("Namespace")
1015 ? RegisterDef->getValueAsString("Namespace")
1017 << "::" << RegisterDef->getName() << ",\n";
1021 /// Adds a specific immediate to the instruction being built.
1022 class ImmRenderer : public OperandRenderer {
1028 ImmRenderer(unsigned InsnID, int64_t Imm)
1029 : OperandRenderer(OR_Imm), InsnID(InsnID), Imm(Imm) {}
1031 static bool classof(const OperandRenderer *R) {
1032 return R->getKind() == OR_Imm;
1035 void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
1036 OS << " GIR_AddImm, /*InsnID*/" << InsnID << ", /*Imm*/" << Imm
1041 /// Adds operands by calling a renderer function supplied by the ComplexPattern
1042 /// matcher function.
1043 class RenderComplexPatternOperand : public OperandRenderer {
1046 const Record &TheDef;
1047 /// The name of the operand.
1048 const StringRef SymbolicName;
1049 /// The renderer number. This must be unique within a rule since it's used to
1050 /// identify a temporary variable to hold the renderer function.
1051 unsigned RendererID;
1053 unsigned getNumOperands() const {
1054 return TheDef.getValueAsDag("Operands")->getNumArgs();
1058 RenderComplexPatternOperand(unsigned InsnID, const Record &TheDef,
1059 StringRef SymbolicName, unsigned RendererID)
1060 : OperandRenderer(OR_ComplexPattern), InsnID(InsnID), TheDef(TheDef),
1061 SymbolicName(SymbolicName), RendererID(RendererID) {}
1063 static bool classof(const OperandRenderer *R) {
1064 return R->getKind() == OR_ComplexPattern;
1067 void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
1068 OS << " GIR_ComplexRenderer, /*InsnID*/" << InsnID << ", /*RendererID*/"
1069 << RendererID << ",\n";
1073 /// An action taken when all Matcher predicates succeeded for a parent rule.
1075 /// Typical actions include:
1076 /// * Changing the opcode of an instruction.
1077 /// * Adding an operand to an instruction.
1080 virtual ~MatchAction() {}
1082 /// Emit the C++ statements to implement the action.
1084 /// \param RecycleInsnID If given, it's an instruction to recycle. The
1085 /// requirements on the instruction vary from action to
1087 virtual void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
1088 unsigned RecycleInsnID) const = 0;
1091 /// Generates a comment describing the matched rule being acted upon.
1092 class DebugCommentAction : public MatchAction {
1094 const PatternToMatch &P;
1097 DebugCommentAction(const PatternToMatch &P) : P(P) {}
1099 void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
1100 unsigned RecycleInsnID) const override {
1101 OS << " // " << *P.getSrcPattern() << " => " << *P.getDstPattern()
1106 /// Generates code to build an instruction or mutate an existing instruction
1107 /// into the desired instruction when this is possible.
1108 class BuildMIAction : public MatchAction {
1111 const CodeGenInstruction *I;
1112 const InstructionMatcher &Matched;
1113 std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers;
1115 /// True if the instruction can be built solely by mutating the opcode.
1116 bool canMutate() const {
1117 if (OperandRenderers.size() != Matched.getNumOperands())
1120 for (const auto &Renderer : enumerate(OperandRenderers)) {
1121 if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) {
1122 const OperandMatcher &OM = Matched.getOperand(Copy->getSymbolicName());
1123 if (&Matched != &OM.getInstructionMatcher() ||
1124 OM.getOperandIndex() != Renderer.index())
1134 BuildMIAction(unsigned InsnID, const CodeGenInstruction *I,
1135 const InstructionMatcher &Matched)
1136 : InsnID(InsnID), I(I), Matched(Matched) {}
1138 template <class Kind, class... Args>
1139 Kind &addRenderer(Args&&... args) {
1140 OperandRenderers.emplace_back(
1141 llvm::make_unique<Kind>(std::forward<Args>(args)...));
1142 return *static_cast<Kind *>(OperandRenderers.back().get());
1145 void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
1146 unsigned RecycleInsnID) const override {
1148 OS << " GIR_MutateOpcode, /*InsnID*/" << InsnID
1149 << ", /*RecycleInsnID*/ " << RecycleInsnID << ", /*Opcode*/"
1150 << I->Namespace << "::" << I->TheDef->getName() << ",\n";
1152 if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) {
1153 for (auto Def : I->ImplicitDefs) {
1154 auto Namespace = Def->getValue("Namespace")
1155 ? Def->getValueAsString("Namespace")
1157 OS << " GIR_AddImplicitDef, " << InsnID << ", " << Namespace
1158 << "::" << Def->getName() << ",\n";
1160 for (auto Use : I->ImplicitUses) {
1161 auto Namespace = Use->getValue("Namespace")
1162 ? Use->getValueAsString("Namespace")
1164 OS << " GIR_AddImplicitUse, " << InsnID << ", " << Namespace
1165 << "::" << Use->getName() << ",\n";
1171 // TODO: Simple permutation looks like it could be almost as common as
1172 // mutation due to commutative operations.
1174 OS << " GIR_BuildMI, /*InsnID*/" << InsnID << ", /*Opcode*/"
1175 << I->Namespace << "::" << I->TheDef->getName() << ",\n";
1176 for (const auto &Renderer : OperandRenderers)
1177 Renderer->emitRenderOpcodes(OS, Rule);
1179 OS << " GIR_MergeMemOperands, /*InsnID*/" << InsnID << ",\n"
1180 << " GIR_EraseFromParent, /*InsnID*/" << RecycleInsnID << ",\n";
1184 /// Generates code to constrain the operands of an output instruction to the
1185 /// register classes specified by the definition of that instruction.
1186 class ConstrainOperandsToDefinitionAction : public MatchAction {
1190 ConstrainOperandsToDefinitionAction(unsigned InsnID) : InsnID(InsnID) {}
1192 void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
1193 unsigned RecycleInsnID) const override {
1194 OS << " GIR_ConstrainSelectedInstOperands, /*InsnID*/" << InsnID << ",\n";
1198 /// Generates code to constrain the specified operand of an output instruction
1199 /// to the specified register class.
1200 class ConstrainOperandToRegClassAction : public MatchAction {
1203 const CodeGenRegisterClass &RC;
1206 ConstrainOperandToRegClassAction(unsigned InsnID, unsigned OpIdx,
1207 const CodeGenRegisterClass &RC)
1208 : InsnID(InsnID), OpIdx(OpIdx), RC(RC) {}
1210 void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
1211 unsigned RecycleInsnID) const override {
1212 OS << " GIR_ConstrainOperandRC, /*InsnID*/" << InsnID << ", /*Op*/"
1213 << OpIdx << ", /*RC " << RC.getName() << "*/ " << RC.EnumValue << ",\n";
1217 InstructionMatcher &RuleMatcher::addInstructionMatcher() {
1218 Matchers.emplace_back(new InstructionMatcher());
1219 return *Matchers.back();
1222 void RuleMatcher::addRequiredFeature(Record *Feature) {
1223 RequiredFeatures.push_back(Feature);
1226 const std::vector<Record *> &RuleMatcher::getRequiredFeatures() const {
1227 return RequiredFeatures;
1230 template <class Kind, class... Args>
1231 Kind &RuleMatcher::addAction(Args &&... args) {
1232 Actions.emplace_back(llvm::make_unique<Kind>(std::forward<Args>(args)...));
1233 return *static_cast<Kind *>(Actions.back().get());
1237 RuleMatcher::implicitlyDefineInsnVar(const InstructionMatcher &Matcher) {
1238 unsigned NewInsnVarID = NextInsnVarID++;
1239 InsnVariableIDs[&Matcher] = NewInsnVarID;
1240 return NewInsnVarID;
1243 unsigned RuleMatcher::defineInsnVar(raw_ostream &OS,
1244 const InstructionMatcher &Matcher,
1245 unsigned InsnID, unsigned OpIdx) {
1246 unsigned NewInsnVarID = implicitlyDefineInsnVar(Matcher);
1247 OS << " GIM_RecordInsn, /*DefineMI*/" << NewInsnVarID << ", /*MI*/"
1248 << InsnID << ", /*OpIdx*/" << OpIdx << ", // MIs[" << NewInsnVarID
1250 return NewInsnVarID;
1253 unsigned RuleMatcher::getInsnVarID(const InstructionMatcher &InsnMatcher) const {
1254 const auto &I = InsnVariableIDs.find(&InsnMatcher);
1255 if (I != InsnVariableIDs.end())
1257 llvm_unreachable("Matched Insn was not captured in a local variable");
1260 /// Emit MatchTable opcodes to check the shape of the match and capture
1261 /// instructions into local variables.
1262 void RuleMatcher::emitCaptureOpcodes(raw_ostream &OS) {
1263 assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
1264 unsigned InsnVarID = implicitlyDefineInsnVar(*Matchers.front());
1265 Matchers.front()->emitCaptureOpcodes(OS, *this, InsnVarID);
1268 void RuleMatcher::emit(raw_ostream &OS) {
1269 if (Matchers.empty())
1270 llvm_unreachable("Unexpected empty matcher!");
1272 // The representation supports rules that require multiple roots such as:
1274 // %elt0(s32) = G_LOAD %ptr
1275 // %1(p0) = G_ADD %ptr, 4
1276 // %elt1(s32) = G_LOAD p0 %1
1277 // which could be usefully folded into:
1279 // %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr
1280 // on some targets but we don't need to make use of that yet.
1281 assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
1283 OS << " const static int64_t MatchTable" << CurrentMatchTableID << "[] = {\n";
1284 if (!RequiredFeatures.empty()) {
1285 OS << " GIM_CheckFeatures, " << getNameForFeatureBitset(RequiredFeatures)
1289 emitCaptureOpcodes(OS);
1291 Matchers.front()->emitPredicateOpcodes(OS, *this,
1292 getInsnVarID(*Matchers.front()));
1294 // We must also check if it's safe to fold the matched instructions.
1295 if (InsnVariableIDs.size() >= 2) {
1296 // Invert the map to create stable ordering (by var names)
1297 SmallVector<unsigned, 2> InsnIDs;
1298 for (const auto &Pair : InsnVariableIDs) {
1299 // Skip the root node since it isn't moving anywhere. Everything else is
1300 // sinking to meet it.
1301 if (Pair.first == Matchers.front().get())
1304 InsnIDs.push_back(Pair.second);
1306 std::sort(InsnIDs.begin(), InsnIDs.end());
1308 for (const auto &InsnID : InsnIDs) {
1309 // Reject the difficult cases until we have a more accurate check.
1310 OS << " GIM_CheckIsSafeToFold, /*InsnID*/" << InsnID << ",\n";
1312 // FIXME: Emit checks to determine it's _actually_ safe to fold and/or
1313 // account for unsafe cases.
1318 // MI0--> %2 = ... %0
1319 // It's not safe to erase MI1. We currently handle this by not
1320 // erasing %0 (even when it's dead).
1323 // MI1--> %0 = load volatile @a
1324 // %1 = load volatile @a
1325 // MI0--> %2 = ... %0
1326 // It's not safe to sink %0's def past %1. We currently handle
1327 // this by rejecting all loads.
1330 // MI1--> %0 = load @a
1332 // MI0--> %2 = ... %0
1333 // It's not safe to sink %0's def past %1. We currently handle
1334 // this by rejecting all loads.
1337 // G_CONDBR %cond, @BB1
1339 // MI1--> %0 = load @a
1342 // MI0--> %2 = ... %0
1343 // It's not always safe to sink %0 across control flow. In this
1344 // case it may introduce a memory fault. We currentl handle this
1345 // by rejecting all loads.
1349 for (const auto &MA : Actions)
1350 MA->emitCxxActionStmts(OS, *this, 0);
1351 OS << " GIR_Done,\n"
1353 << " State.MIs.resize(1);\n"
1354 << " DEBUG(dbgs() << \"Processing MatchTable" << CurrentMatchTableID
1356 << " if (executeMatchTable(*this, OutMIs, State, MatcherInfo, MatchTable"
1357 << CurrentMatchTableID << ", TII, MRI, TRI, RBI, AvailableFeatures)) {\n"
1358 << " return true;\n"
1362 bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
1363 // Rules involving more match roots have higher priority.
1364 if (Matchers.size() > B.Matchers.size())
1366 if (Matchers.size() < B.Matchers.size())
1369 for (const auto &Matcher : zip(Matchers, B.Matchers)) {
1370 if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher)))
1372 if (std::get<1>(Matcher)->isHigherPriorityThan(*std::get<0>(Matcher)))
1379 unsigned RuleMatcher::countRendererFns() const {
1380 return std::accumulate(
1381 Matchers.begin(), Matchers.end(), 0,
1382 [](unsigned A, const std::unique_ptr<InstructionMatcher> &Matcher) {
1383 return A + Matcher->countRendererFns();
1387 //===- GlobalISelEmitter class --------------------------------------------===//
1389 class GlobalISelEmitter {
1391 explicit GlobalISelEmitter(RecordKeeper &RK);
1392 void run(raw_ostream &OS);
1395 const RecordKeeper &RK;
1396 const CodeGenDAGPatterns CGP;
1397 const CodeGenTarget &Target;
1398 CodeGenRegBank CGRegs;
1400 /// Keep track of the equivalence between SDNodes and Instruction.
1401 /// This is defined using 'GINodeEquiv' in the target description.
1402 DenseMap<Record *, const CodeGenInstruction *> NodeEquivs;
1404 /// Keep track of the equivalence between ComplexPattern's and
1405 /// GIComplexOperandMatcher. Map entries are specified by subclassing
1406 /// GIComplexPatternEquiv.
1407 DenseMap<const Record *, const Record *> ComplexPatternEquivs;
1409 // Map of predicates to their subtarget features.
1410 SubtargetFeatureInfoMap SubtargetFeatures;
1412 void gatherNodeEquivs();
1413 const CodeGenInstruction *findNodeEquiv(Record *N) const;
1415 Error importRulePredicates(RuleMatcher &M, ArrayRef<Init *> Predicates);
1416 Expected<InstructionMatcher &>
1417 createAndImportSelDAGMatcher(InstructionMatcher &InsnMatcher,
1418 const TreePatternNode *Src,
1419 unsigned &TempOpIdx) const;
1420 Error importChildMatcher(InstructionMatcher &InsnMatcher,
1421 const TreePatternNode *SrcChild, unsigned OpIdx,
1422 unsigned &TempOpIdx) const;
1423 Expected<BuildMIAction &>
1424 createAndImportInstructionRenderer(RuleMatcher &M, const TreePatternNode *Dst,
1425 const InstructionMatcher &InsnMatcher);
1426 Error importExplicitUseRenderer(BuildMIAction &DstMIBuilder,
1427 TreePatternNode *DstChild,
1428 const InstructionMatcher &InsnMatcher) const;
1429 Error importDefaultOperandRenderers(BuildMIAction &DstMIBuilder,
1430 DagInit *DefaultOps) const;
1432 importImplicitDefRenderers(BuildMIAction &DstMIBuilder,
1433 const std::vector<Record *> &ImplicitDefs) const;
1435 /// Analyze pattern \p P, returning a matcher for it if possible.
1436 /// Otherwise, return an Error explaining why we don't support it.
1437 Expected<RuleMatcher> runOnPattern(const PatternToMatch &P);
1439 void declareSubtargetFeature(Record *Predicate);
1442 void GlobalISelEmitter::gatherNodeEquivs() {
1443 assert(NodeEquivs.empty());
1444 for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
1445 NodeEquivs[Equiv->getValueAsDef("Node")] =
1446 &Target.getInstruction(Equiv->getValueAsDef("I"));
1448 assert(ComplexPatternEquivs.empty());
1449 for (Record *Equiv : RK.getAllDerivedDefinitions("GIComplexPatternEquiv")) {
1450 Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
1453 ComplexPatternEquivs[SelDAGEquiv] = Equiv;
1457 const CodeGenInstruction *GlobalISelEmitter::findNodeEquiv(Record *N) const {
1458 return NodeEquivs.lookup(N);
1461 GlobalISelEmitter::GlobalISelEmitter(RecordKeeper &RK)
1462 : RK(RK), CGP(RK), Target(CGP.getTargetInfo()), CGRegs(RK) {}
1464 //===- Emitter ------------------------------------------------------------===//
1467 GlobalISelEmitter::importRulePredicates(RuleMatcher &M,
1468 ArrayRef<Init *> Predicates) {
1469 for (const Init *Predicate : Predicates) {
1470 const DefInit *PredicateDef = static_cast<const DefInit *>(Predicate);
1471 declareSubtargetFeature(PredicateDef->getDef());
1472 M.addRequiredFeature(PredicateDef->getDef());
1475 return Error::success();
1478 Expected<InstructionMatcher &>
1479 GlobalISelEmitter::createAndImportSelDAGMatcher(InstructionMatcher &InsnMatcher,
1480 const TreePatternNode *Src,
1481 unsigned &TempOpIdx) const {
1482 const CodeGenInstruction *SrcGIOrNull = nullptr;
1484 // Start with the defined operands (i.e., the results of the root operator).
1485 if (Src->getExtTypes().size() > 1)
1486 return failedImport("Src pattern has multiple results");
1488 if (Src->isLeaf()) {
1489 Init *SrcInit = Src->getLeafValue();
1490 if (isa<IntInit>(SrcInit)) {
1491 InsnMatcher.addPredicate<InstructionOpcodeMatcher>(
1492 &Target.getInstruction(RK.getDef("G_CONSTANT")));
1494 return failedImport(
1495 "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
1497 SrcGIOrNull = findNodeEquiv(Src->getOperator());
1499 return failedImport("Pattern operator lacks an equivalent Instruction" +
1500 explainOperator(Src->getOperator()));
1501 auto &SrcGI = *SrcGIOrNull;
1503 // The operators look good: match the opcode
1504 InsnMatcher.addPredicate<InstructionOpcodeMatcher>(&SrcGI);
1508 for (const EEVT::TypeSet &Ty : Src->getExtTypes()) {
1509 auto OpTyOrNone = MVTToLLT(Ty.getConcrete());
1512 return failedImport(
1513 "Result of Src pattern operator has an unsupported type");
1515 // Results don't have a name unless they are the root node. The caller will
1516 // set the name if appropriate.
1517 OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
1518 OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
1521 if (Src->isLeaf()) {
1522 Init *SrcInit = Src->getLeafValue();
1523 if (IntInit *SrcIntInit = dyn_cast<IntInit>(SrcInit)) {
1524 OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
1525 OM.addPredicate<LiteralIntOperandMatcher>(SrcIntInit->getValue());
1527 return failedImport(
1528 "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
1530 assert(SrcGIOrNull &&
1531 "Expected to have already found an equivalent Instruction");
1532 // Match the used operands (i.e. the children of the operator).
1533 for (unsigned i = 0, e = Src->getNumChildren(); i != e; ++i) {
1534 TreePatternNode *SrcChild = Src->getChild(i);
1536 // For G_INTRINSIC, the operand immediately following the defs is an
1538 if (SrcGIOrNull->TheDef->getName() == "G_INTRINSIC" && i == 0) {
1539 if (const CodeGenIntrinsic *II = Src->getIntrinsicInfo(CGP)) {
1540 OperandMatcher &OM =
1541 InsnMatcher.addOperand(OpIdx++, SrcChild->getName(), TempOpIdx);
1542 OM.addPredicate<IntrinsicIDOperandMatcher>(II);
1546 return failedImport("Expected IntInit containing instrinsic ID)");
1550 importChildMatcher(InsnMatcher, SrcChild, OpIdx++, TempOpIdx))
1551 return std::move(Error);
1558 Error GlobalISelEmitter::importChildMatcher(InstructionMatcher &InsnMatcher,
1559 const TreePatternNode *SrcChild,
1561 unsigned &TempOpIdx) const {
1562 OperandMatcher &OM =
1563 InsnMatcher.addOperand(OpIdx, SrcChild->getName(), TempOpIdx);
1565 if (SrcChild->hasAnyPredicate())
1566 return failedImport("Src pattern child has predicate (" +
1567 explainPredicates(SrcChild) + ")");
1569 ArrayRef<EEVT::TypeSet> ChildTypes = SrcChild->getExtTypes();
1570 if (ChildTypes.size() != 1)
1571 return failedImport("Src pattern child has multiple results");
1573 // Check MBB's before the type check since they are not a known type.
1574 if (!SrcChild->isLeaf()) {
1575 if (SrcChild->getOperator()->isSubClassOf("SDNode")) {
1576 auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator());
1577 if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
1578 OM.addPredicate<MBBOperandMatcher>();
1579 return Error::success();
1584 auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete());
1586 return failedImport("Src operand has an unsupported type (" + to_string(*SrcChild) + ")");
1587 OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
1589 // Check for nested instructions.
1590 if (!SrcChild->isLeaf()) {
1591 // Map the node to a gMIR instruction.
1592 InstructionOperandMatcher &InsnOperand =
1593 OM.addPredicate<InstructionOperandMatcher>();
1594 auto InsnMatcherOrError = createAndImportSelDAGMatcher(
1595 InsnOperand.getInsnMatcher(), SrcChild, TempOpIdx);
1596 if (auto Error = InsnMatcherOrError.takeError())
1599 return Error::success();
1602 // Check for constant immediates.
1603 if (auto *ChildInt = dyn_cast<IntInit>(SrcChild->getLeafValue())) {
1604 OM.addPredicate<ConstantIntOperandMatcher>(ChildInt->getValue());
1605 return Error::success();
1608 // Check for def's like register classes or ComplexPattern's.
1609 if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
1610 auto *ChildRec = ChildDefInit->getDef();
1612 // Check for register classes.
1613 if (ChildRec->isSubClassOf("RegisterClass") ||
1614 ChildRec->isSubClassOf("RegisterOperand")) {
1615 OM.addPredicate<RegisterBankOperandMatcher>(
1616 Target.getRegisterClass(getInitValueAsRegClass(ChildDefInit)));
1617 return Error::success();
1620 // Check for ComplexPattern's.
1621 if (ChildRec->isSubClassOf("ComplexPattern")) {
1622 const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
1623 if (ComplexPattern == ComplexPatternEquivs.end())
1624 return failedImport("SelectionDAG ComplexPattern (" +
1625 ChildRec->getName() + ") not mapped to GlobalISel");
1627 OM.addPredicate<ComplexPatternOperandMatcher>(OM,
1628 *ComplexPattern->second);
1630 return Error::success();
1633 if (ChildRec->isSubClassOf("ImmLeaf")) {
1634 return failedImport(
1635 "Src pattern child def is an unsupported tablegen class (ImmLeaf)");
1638 return failedImport(
1639 "Src pattern child def is an unsupported tablegen class");
1642 return failedImport("Src pattern child is an unsupported kind");
1645 Error GlobalISelEmitter::importExplicitUseRenderer(
1646 BuildMIAction &DstMIBuilder, TreePatternNode *DstChild,
1647 const InstructionMatcher &InsnMatcher) const {
1648 // The only non-leaf child we accept is 'bb': it's an operator because
1649 // BasicBlockSDNode isn't inline, but in MI it's just another operand.
1650 if (!DstChild->isLeaf()) {
1651 if (DstChild->getOperator()->isSubClassOf("SDNode")) {
1652 auto &ChildSDNI = CGP.getSDNodeInfo(DstChild->getOperator());
1653 if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
1654 DstMIBuilder.addRenderer<CopyRenderer>(0, InsnMatcher,
1655 DstChild->getName());
1656 return Error::success();
1659 return failedImport("Dst pattern child isn't a leaf node or an MBB");
1662 // Otherwise, we're looking for a bog-standard RegisterClass operand.
1663 if (DstChild->hasAnyPredicate())
1664 return failedImport("Dst pattern child has predicate (" +
1665 explainPredicates(DstChild) + ")");
1667 if (auto *ChildDefInit = dyn_cast<DefInit>(DstChild->getLeafValue())) {
1668 auto *ChildRec = ChildDefInit->getDef();
1670 ArrayRef<EEVT::TypeSet> ChildTypes = DstChild->getExtTypes();
1671 if (ChildTypes.size() != 1)
1672 return failedImport("Dst pattern child has multiple results");
1674 auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete());
1676 return failedImport("Dst operand has an unsupported type");
1678 if (ChildRec->isSubClassOf("Register")) {
1679 DstMIBuilder.addRenderer<AddRegisterRenderer>(0, ChildRec);
1680 return Error::success();
1683 if (ChildRec->isSubClassOf("RegisterClass") ||
1684 ChildRec->isSubClassOf("RegisterOperand")) {
1685 DstMIBuilder.addRenderer<CopyRenderer>(0, InsnMatcher,
1686 DstChild->getName());
1687 return Error::success();
1690 if (ChildRec->isSubClassOf("ComplexPattern")) {
1691 const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
1692 if (ComplexPattern == ComplexPatternEquivs.end())
1693 return failedImport(
1694 "SelectionDAG ComplexPattern not mapped to GlobalISel");
1696 const OperandMatcher &OM = InsnMatcher.getOperand(DstChild->getName());
1697 DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
1698 0, *ComplexPattern->second, DstChild->getName(),
1699 OM.getAllocatedTemporariesBaseID());
1700 return Error::success();
1703 if (ChildRec->isSubClassOf("SDNodeXForm"))
1704 return failedImport("Dst pattern child def is an unsupported tablegen "
1705 "class (SDNodeXForm)");
1707 return failedImport(
1708 "Dst pattern child def is an unsupported tablegen class");
1711 return failedImport("Dst pattern child is an unsupported kind");
1714 Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
1715 RuleMatcher &M, const TreePatternNode *Dst,
1716 const InstructionMatcher &InsnMatcher) {
1717 Record *DstOp = Dst->getOperator();
1718 if (!DstOp->isSubClassOf("Instruction")) {
1719 if (DstOp->isSubClassOf("ValueType"))
1720 return failedImport(
1721 "Pattern operator isn't an instruction (it's a ValueType)");
1722 return failedImport("Pattern operator isn't an instruction");
1724 CodeGenInstruction *DstI = &Target.getInstruction(DstOp);
1726 unsigned DstINumUses = DstI->Operands.size() - DstI->Operands.NumDefs;
1727 unsigned ExpectedDstINumUses = Dst->getNumChildren();
1728 bool IsExtractSubReg = false;
1730 // COPY_TO_REGCLASS is just a copy with a ConstrainOperandToRegClassAction
1731 // attached. Similarly for EXTRACT_SUBREG except that's a subregister copy.
1732 if (DstI->TheDef->getName() == "COPY_TO_REGCLASS") {
1733 DstI = &Target.getInstruction(RK.getDef("COPY"));
1734 DstINumUses--; // Ignore the class constraint.
1735 ExpectedDstINumUses--;
1736 } else if (DstI->TheDef->getName() == "EXTRACT_SUBREG") {
1737 DstI = &Target.getInstruction(RK.getDef("COPY"));
1738 IsExtractSubReg = true;
1741 auto &DstMIBuilder = M.addAction<BuildMIAction>(0, DstI, InsnMatcher);
1743 // Render the explicit defs.
1744 for (unsigned I = 0; I < DstI->Operands.NumDefs; ++I) {
1745 const CGIOperandList::OperandInfo &DstIOperand = DstI->Operands[I];
1746 DstMIBuilder.addRenderer<CopyRenderer>(0, InsnMatcher, DstIOperand.Name);
1749 // EXTRACT_SUBREG needs to use a subregister COPY.
1750 if (IsExtractSubReg) {
1751 if (!Dst->getChild(0)->isLeaf())
1752 return failedImport("EXTRACT_SUBREG child #1 is not a leaf");
1754 if (DefInit *SubRegInit =
1755 dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue())) {
1756 CodeGenRegisterClass *RC = CGRegs.getRegClass(
1757 getInitValueAsRegClass(Dst->getChild(0)->getLeafValue()));
1758 CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
1760 const auto &SrcRCDstRCPair =
1761 RC->getMatchingSubClassWithSubRegs(CGRegs, SubIdx);
1762 if (SrcRCDstRCPair.hasValue()) {
1763 assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
1764 if (SrcRCDstRCPair->first != RC)
1765 return failedImport("EXTRACT_SUBREG requires an additional COPY");
1768 DstMIBuilder.addRenderer<CopySubRegRenderer>(
1769 0, InsnMatcher, Dst->getChild(0)->getName(), SubIdx);
1770 return DstMIBuilder;
1773 return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
1776 // Render the explicit uses.
1778 unsigned NumDefaultOps = 0;
1779 for (unsigned I = 0; I != DstINumUses; ++I) {
1780 const CGIOperandList::OperandInfo &DstIOperand =
1781 DstI->Operands[DstI->Operands.NumDefs + I];
1783 // If the operand has default values, introduce them now.
1784 // FIXME: Until we have a decent test case that dictates we should do
1785 // otherwise, we're going to assume that operands with default values cannot
1786 // be specified in the patterns. Therefore, adding them will not cause us to
1787 // end up with too many rendered operands.
1788 if (DstIOperand.Rec->isSubClassOf("OperandWithDefaultOps")) {
1789 DagInit *DefaultOps = DstIOperand.Rec->getValueAsDag("DefaultOps");
1790 if (auto Error = importDefaultOperandRenderers(DstMIBuilder, DefaultOps))
1791 return std::move(Error);
1796 if (auto Error = importExplicitUseRenderer(
1797 DstMIBuilder, Dst->getChild(Child), InsnMatcher))
1798 return std::move(Error);
1802 if (NumDefaultOps + ExpectedDstINumUses != DstINumUses)
1803 return failedImport("Expected " + llvm::to_string(DstINumUses) +
1804 " used operands but found " +
1805 llvm::to_string(ExpectedDstINumUses) +
1806 " explicit ones and " + llvm::to_string(NumDefaultOps) +
1809 return DstMIBuilder;
1812 Error GlobalISelEmitter::importDefaultOperandRenderers(
1813 BuildMIAction &DstMIBuilder, DagInit *DefaultOps) const {
1814 for (const auto *DefaultOp : DefaultOps->getArgs()) {
1815 // Look through ValueType operators.
1816 if (const DagInit *DefaultDagOp = dyn_cast<DagInit>(DefaultOp)) {
1817 if (const DefInit *DefaultDagOperator =
1818 dyn_cast<DefInit>(DefaultDagOp->getOperator())) {
1819 if (DefaultDagOperator->getDef()->isSubClassOf("ValueType"))
1820 DefaultOp = DefaultDagOp->getArg(0);
1824 if (const DefInit *DefaultDefOp = dyn_cast<DefInit>(DefaultOp)) {
1825 DstMIBuilder.addRenderer<AddRegisterRenderer>(0, DefaultDefOp->getDef());
1829 if (const IntInit *DefaultIntOp = dyn_cast<IntInit>(DefaultOp)) {
1830 DstMIBuilder.addRenderer<ImmRenderer>(0, DefaultIntOp->getValue());
1834 return failedImport("Could not add default op");
1837 return Error::success();
1840 Error GlobalISelEmitter::importImplicitDefRenderers(
1841 BuildMIAction &DstMIBuilder,
1842 const std::vector<Record *> &ImplicitDefs) const {
1843 if (!ImplicitDefs.empty())
1844 return failedImport("Pattern defines a physical register");
1845 return Error::success();
1848 Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
1849 // Keep track of the matchers and actions to emit.
1851 M.addAction<DebugCommentAction>(P);
1853 if (auto Error = importRulePredicates(M, P.getPredicates()->getValues()))
1854 return std::move(Error);
1856 // Next, analyze the pattern operators.
1857 TreePatternNode *Src = P.getSrcPattern();
1858 TreePatternNode *Dst = P.getDstPattern();
1860 // If the root of either pattern isn't a simple operator, ignore it.
1861 if (auto Err = isTrivialOperatorNode(Dst))
1862 return failedImport("Dst pattern root isn't a trivial operator (" +
1863 toString(std::move(Err)) + ")");
1864 if (auto Err = isTrivialOperatorNode(Src))
1865 return failedImport("Src pattern root isn't a trivial operator (" +
1866 toString(std::move(Err)) + ")");
1869 return failedImport("Dst pattern root isn't a known leaf");
1871 // Start with the defined operands (i.e., the results of the root operator).
1872 Record *DstOp = Dst->getOperator();
1873 if (!DstOp->isSubClassOf("Instruction"))
1874 return failedImport("Pattern operator isn't an instruction");
1876 auto &DstI = Target.getInstruction(DstOp);
1877 if (DstI.Operands.NumDefs != Src->getExtTypes().size())
1878 return failedImport("Src pattern results and dst MI defs are different (" +
1879 to_string(Src->getExtTypes().size()) + " def(s) vs " +
1880 to_string(DstI.Operands.NumDefs) + " def(s))");
1882 InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher();
1883 unsigned TempOpIdx = 0;
1884 auto InsnMatcherOrError =
1885 createAndImportSelDAGMatcher(InsnMatcherTemp, Src, TempOpIdx);
1886 if (auto Error = InsnMatcherOrError.takeError())
1887 return std::move(Error);
1888 InstructionMatcher &InsnMatcher = InsnMatcherOrError.get();
1890 // The root of the match also has constraints on the register bank so that it
1891 // matches the result instruction.
1893 for (const EEVT::TypeSet &Ty : Src->getExtTypes()) {
1896 const auto &DstIOperand = DstI.Operands[OpIdx];
1897 Record *DstIOpRec = DstIOperand.Rec;
1898 if (DstI.TheDef->getName() == "COPY_TO_REGCLASS") {
1899 DstIOpRec = getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());
1901 if (DstIOpRec == nullptr)
1902 return failedImport(
1903 "COPY_TO_REGCLASS operand #1 isn't a register class");
1904 } else if (DstI.TheDef->getName() == "EXTRACT_SUBREG") {
1905 if (!Dst->getChild(0)->isLeaf())
1906 return failedImport("EXTRACT_SUBREG operand #0 isn't a leaf");
1908 // We can assume that a subregister is in the same bank as it's super
1910 DstIOpRec = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
1912 if (DstIOpRec == nullptr)
1913 return failedImport(
1914 "EXTRACT_SUBREG operand #0 isn't a register class");
1915 } else if (DstIOpRec->isSubClassOf("RegisterOperand"))
1916 DstIOpRec = DstIOpRec->getValueAsDef("RegClass");
1917 else if (!DstIOpRec->isSubClassOf("RegisterClass"))
1918 return failedImport("Dst MI def isn't a register class" +
1921 OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
1922 OM.setSymbolicName(DstIOperand.Name);
1923 OM.addPredicate<RegisterBankOperandMatcher>(
1924 Target.getRegisterClass(DstIOpRec));
1928 auto DstMIBuilderOrError =
1929 createAndImportInstructionRenderer(M, Dst, InsnMatcher);
1930 if (auto Error = DstMIBuilderOrError.takeError())
1931 return std::move(Error);
1932 BuildMIAction &DstMIBuilder = DstMIBuilderOrError.get();
1934 // Render the implicit defs.
1935 // These are only added to the root of the result.
1936 if (auto Error = importImplicitDefRenderers(DstMIBuilder, P.getDstRegs()))
1937 return std::move(Error);
1939 // Constrain the registers to classes. This is normally derived from the
1940 // emitted instruction but a few instructions require special handling.
1941 if (DstI.TheDef->getName() == "COPY_TO_REGCLASS") {
1942 // COPY_TO_REGCLASS does not provide operand constraints itself but the
1943 // result is constrained to the class given by the second child.
1945 getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());
1947 if (DstIOpRec == nullptr)
1948 return failedImport("COPY_TO_REGCLASS operand #1 isn't a register class");
1950 M.addAction<ConstrainOperandToRegClassAction>(
1951 0, 0, Target.getRegisterClass(DstIOpRec));
1953 // We're done with this pattern! It's eligible for GISel emission; return
1955 ++NumPatternImported;
1956 return std::move(M);
1959 if (DstI.TheDef->getName() == "EXTRACT_SUBREG") {
1960 // EXTRACT_SUBREG selects into a subregister COPY but unlike most
1961 // instructions, the result register class is controlled by the
1962 // subregisters of the operand. As a result, we must constrain the result
1963 // class rather than check that it's already the right one.
1964 if (!Dst->getChild(0)->isLeaf())
1965 return failedImport("EXTRACT_SUBREG child #1 is not a leaf");
1967 DefInit *SubRegInit = dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue());
1969 return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
1971 // Constrain the result to the same register bank as the operand.
1973 getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
1975 if (DstIOpRec == nullptr)
1976 return failedImport("EXTRACT_SUBREG operand #1 isn't a register class");
1978 CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
1979 CodeGenRegisterClass *SrcRC = CGRegs.getRegClass(DstIOpRec);
1981 // It would be nice to leave this constraint implicit but we're required
1982 // to pick a register class so constrain the result to a register class
1983 // that can hold the correct MVT.
1985 // FIXME: This may introduce an extra copy if the chosen class doesn't
1986 // actually contain the subregisters.
1987 assert(Src->getExtTypes().size() == 1 &&
1988 "Expected Src of EXTRACT_SUBREG to have one result type");
1990 const auto &SrcRCDstRCPair =
1991 SrcRC->getMatchingSubClassWithSubRegs(CGRegs, SubIdx);
1992 assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
1993 M.addAction<ConstrainOperandToRegClassAction>(0, 0, *SrcRCDstRCPair->second);
1994 M.addAction<ConstrainOperandToRegClassAction>(0, 1, *SrcRCDstRCPair->first);
1996 // We're done with this pattern! It's eligible for GISel emission; return
1998 ++NumPatternImported;
1999 return std::move(M);
2002 M.addAction<ConstrainOperandsToDefinitionAction>(0);
2004 // We're done with this pattern! It's eligible for GISel emission; return it.
2005 ++NumPatternImported;
2006 return std::move(M);
2009 void GlobalISelEmitter::run(raw_ostream &OS) {
2010 // Track the GINodeEquiv definitions.
2013 emitSourceFileHeader(("Global Instruction Selector for the " +
2014 Target.getName() + " target").str(), OS);
2015 std::vector<RuleMatcher> Rules;
2016 // Look through the SelectionDAG patterns we found, possibly emitting some.
2017 for (const PatternToMatch &Pat : CGP.ptms()) {
2019 auto MatcherOrErr = runOnPattern(Pat);
2021 // The pattern analysis can fail, indicating an unsupported pattern.
2022 // Report that if we've been asked to do so.
2023 if (auto Err = MatcherOrErr.takeError()) {
2024 if (WarnOnSkippedPatterns) {
2025 PrintWarning(Pat.getSrcRecord()->getLoc(),
2026 "Skipped pattern: " + toString(std::move(Err)));
2028 consumeError(std::move(Err));
2030 ++NumPatternImportsSkipped;
2034 Rules.push_back(std::move(MatcherOrErr.get()));
2037 std::stable_sort(Rules.begin(), Rules.end(),
2038 [&](const RuleMatcher &A, const RuleMatcher &B) {
2039 if (A.isHigherPriorityThan(B)) {
2040 assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
2041 "and less important at "
2048 std::vector<Record *> ComplexPredicates =
2049 RK.getAllDerivedDefinitions("GIComplexOperandMatcher");
2050 std::sort(ComplexPredicates.begin(), ComplexPredicates.end(),
2051 [](const Record *A, const Record *B) {
2052 if (A->getName() < B->getName())
2056 unsigned MaxTemporaries = 0;
2057 for (const auto &Rule : Rules)
2058 MaxTemporaries = std::max(MaxTemporaries, Rule.countRendererFns());
2060 OS << "#ifdef GET_GLOBALISEL_PREDICATE_BITSET\n"
2061 << "const unsigned MAX_SUBTARGET_PREDICATES = " << SubtargetFeatures.size()
2063 << "using PredicateBitset = "
2064 "llvm::PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;\n"
2065 << "#endif // ifdef GET_GLOBALISEL_PREDICATE_BITSET\n\n";
2067 OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n"
2068 << " mutable MatcherState State;\n"
2070 "ComplexRendererFn("
2072 << "InstructionSelector::*ComplexMatcherMemFn)(MachineOperand &) const;\n"
2073 << "const MatcherInfoTy<PredicateBitset, ComplexMatcherMemFn> "
2075 << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n";
2077 OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n"
2078 << ", State(" << MaxTemporaries << "),\n"
2079 << "MatcherInfo({TypeObjects, FeatureBitsets, {\n"
2080 << " nullptr, // GICP_Invalid\n";
2081 for (const auto &Record : ComplexPredicates)
2082 OS << " &" << Target.getName()
2083 << "InstructionSelector::" << Record->getValueAsString("MatcherFn")
2084 << ", // " << Record->getName() << "\n";
2086 << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";
2088 OS << "#ifdef GET_GLOBALISEL_IMPL\n";
2089 SubtargetFeatureInfo::emitSubtargetFeatureBitEnumeration(SubtargetFeatures,
2092 // Separate subtarget features by how often they must be recomputed.
2093 SubtargetFeatureInfoMap ModuleFeatures;
2094 std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
2095 std::inserter(ModuleFeatures, ModuleFeatures.end()),
2096 [](const SubtargetFeatureInfoMap::value_type &X) {
2097 return !X.second.mustRecomputePerFunction();
2099 SubtargetFeatureInfoMap FunctionFeatures;
2100 std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
2101 std::inserter(FunctionFeatures, FunctionFeatures.end()),
2102 [](const SubtargetFeatureInfoMap::value_type &X) {
2103 return X.second.mustRecomputePerFunction();
2106 SubtargetFeatureInfo::emitComputeAvailableFeatures(
2107 Target.getName(), "InstructionSelector", "computeAvailableModuleFeatures",
2108 ModuleFeatures, OS);
2109 SubtargetFeatureInfo::emitComputeAvailableFeatures(
2110 Target.getName(), "InstructionSelector",
2111 "computeAvailableFunctionFeatures", FunctionFeatures, OS,
2112 "const MachineFunction *MF");
2114 // Emit a table containing the LLT objects needed by the matcher and an enum
2115 // for the matcher to reference them with.
2116 std::vector<LLTCodeGen> TypeObjects = {
2117 LLT::scalar(8), LLT::scalar(16), LLT::scalar(32),
2118 LLT::scalar(64), LLT::scalar(80), LLT::vector(8, 1),
2119 LLT::vector(16, 1), LLT::vector(32, 1), LLT::vector(64, 1),
2120 LLT::vector(8, 8), LLT::vector(16, 8), LLT::vector(32, 8),
2121 LLT::vector(64, 8), LLT::vector(4, 16), LLT::vector(8, 16),
2122 LLT::vector(16, 16), LLT::vector(32, 16), LLT::vector(2, 32),
2123 LLT::vector(4, 32), LLT::vector(8, 32), LLT::vector(16, 32),
2124 LLT::vector(2, 64), LLT::vector(4, 64), LLT::vector(8, 64),
2126 std::sort(TypeObjects.begin(), TypeObjects.end());
2128 for (const auto &TypeObject : TypeObjects) {
2130 TypeObject.emitCxxEnumValue(OS);
2134 << "const static LLT TypeObjects[] = {\n";
2135 for (const auto &TypeObject : TypeObjects) {
2137 TypeObject.emitCxxConstructorCall(OS);
2142 // Emit a table containing the PredicateBitsets objects needed by the matcher
2143 // and an enum for the matcher to reference them with.
2144 std::vector<std::vector<Record *>> FeatureBitsets;
2145 for (auto &Rule : Rules)
2146 FeatureBitsets.push_back(Rule.getRequiredFeatures());
2148 FeatureBitsets.begin(), FeatureBitsets.end(),
2149 [&](const std::vector<Record *> &A, const std::vector<Record *> &B) {
2150 if (A.size() < B.size())
2152 if (A.size() > B.size())
2154 for (const auto &Pair : zip(A, B)) {
2155 if (std::get<0>(Pair)->getName() < std::get<1>(Pair)->getName())
2157 if (std::get<0>(Pair)->getName() > std::get<1>(Pair)->getName())
2162 FeatureBitsets.erase(
2163 std::unique(FeatureBitsets.begin(), FeatureBitsets.end()),
2164 FeatureBitsets.end());
2166 << " GIFBS_Invalid,\n";
2167 for (const auto &FeatureBitset : FeatureBitsets) {
2168 if (FeatureBitset.empty())
2170 OS << " " << getNameForFeatureBitset(FeatureBitset) << ",\n";
2173 << "const static PredicateBitset FeatureBitsets[] {\n"
2174 << " {}, // GIFBS_Invalid\n";
2175 for (const auto &FeatureBitset : FeatureBitsets) {
2176 if (FeatureBitset.empty())
2179 for (const auto &Feature : FeatureBitset) {
2180 const auto &I = SubtargetFeatures.find(Feature);
2181 assert(I != SubtargetFeatures.end() && "Didn't import predicate?");
2182 OS << I->second.getEnumBitName() << ", ";
2188 // Emit complex predicate table and an enum to reference them with.
2190 << " GICP_Invalid,\n";
2191 for (const auto &Record : ComplexPredicates)
2192 OS << " GICP_" << Record->getName() << ",\n";
2194 << "// See constructor for table contents\n\n";
2196 OS << "bool " << Target.getName()
2197 << "InstructionSelector::selectImpl(MachineInstr &I) const {\n"
2198 << " MachineFunction &MF = *I.getParent()->getParent();\n"
2199 << " MachineRegisterInfo &MRI = MF.getRegInfo();\n"
2200 << " // FIXME: This should be computed on a per-function basis rather "
2202 << " AvailableFunctionFeatures = computeAvailableFunctionFeatures(&STI, "
2204 << " const PredicateBitset AvailableFeatures = getAvailableFeatures();\n"
2205 << " NewMIVector OutMIs;\n"
2206 << " State.MIs.clear();\n"
2207 << " State.MIs.push_back(&I);\n\n";
2209 for (auto &Rule : Rules) {
2211 ++CurrentMatchTableID;
2212 ++NumPatternEmitted;
2213 assert(CurrentMatchTableID == NumPatternEmitted &&
2214 "Statistic deviates from number of emitted tables");
2217 OS << " return false;\n"
2219 << "#endif // ifdef GET_GLOBALISEL_IMPL\n";
2221 OS << "#ifdef GET_GLOBALISEL_PREDICATES_DECL\n"
2222 << "PredicateBitset AvailableModuleFeatures;\n"
2223 << "mutable PredicateBitset AvailableFunctionFeatures;\n"
2224 << "PredicateBitset getAvailableFeatures() const {\n"
2225 << " return AvailableModuleFeatures | AvailableFunctionFeatures;\n"
2227 << "PredicateBitset\n"
2228 << "computeAvailableModuleFeatures(const " << Target.getName()
2229 << "Subtarget *Subtarget) const;\n"
2230 << "PredicateBitset\n"
2231 << "computeAvailableFunctionFeatures(const " << Target.getName()
2232 << "Subtarget *Subtarget,\n"
2233 << " const MachineFunction *MF) const;\n"
2234 << "#endif // ifdef GET_GLOBALISEL_PREDICATES_DECL\n";
2236 OS << "#ifdef GET_GLOBALISEL_PREDICATES_INIT\n"
2237 << "AvailableModuleFeatures(computeAvailableModuleFeatures(&STI)),\n"
2238 << "AvailableFunctionFeatures()\n"
2239 << "#endif // ifdef GET_GLOBALISEL_PREDICATES_INIT\n";
2242 void GlobalISelEmitter::declareSubtargetFeature(Record *Predicate) {
2243 if (SubtargetFeatures.count(Predicate) == 0)
2244 SubtargetFeatures.emplace(
2245 Predicate, SubtargetFeatureInfo(Predicate, SubtargetFeatures.size()));
2248 } // end anonymous namespace
2250 //===----------------------------------------------------------------------===//
2253 void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS) {
2254 GlobalISelEmitter(RK).run(OS);
2256 } // End llvm namespace