1 //===- GlobalISelEmitter.cpp - Generate an instruction selector -----------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
10 /// This tablegen backend emits code for use by the GlobalISel instruction
11 /// selector. See include/llvm/CodeGen/TargetGlobalISel.td.
13 /// This file analyzes the patterns recognized by the SelectionDAGISel tablegen
14 /// backend, filters out the ones that are unsupported, maps
15 /// SelectionDAG-specific constructs to their GlobalISel counterpart
16 /// (when applicable: MVT to LLT; SDNode to generic Instruction).
18 /// Not all patterns are supported: pass the tablegen invocation
19 /// "-warn-on-skipped-patterns" to emit a warning when a pattern is skipped,
22 /// The generated file defines a single method:
23 /// bool <Target>InstructionSelector::selectImpl(MachineInstr &I) const;
24 /// intended to be used in InstructionSelector::select as the first-step
25 /// selector for the patterns that don't require complex C++.
27 /// FIXME: We'll probably want to eventually define a base
28 /// "TargetGenInstructionSelector" class.
30 //===----------------------------------------------------------------------===//
32 #include "CodeGenDAGPatterns.h"
33 #include "SubtargetFeatureInfo.h"
34 #include "llvm/ADT/Optional.h"
35 #include "llvm/ADT/SmallSet.h"
36 #include "llvm/ADT/Statistic.h"
37 #include "llvm/Support/CodeGenCoverage.h"
38 #include "llvm/Support/CommandLine.h"
39 #include "llvm/Support/Error.h"
40 #include "llvm/Support/LowLevelTypeImpl.h"
41 #include "llvm/Support/MachineValueType.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(NumPatternsTested, "Number of patterns executed according to coverage information");
56 STATISTIC(NumPatternEmitted, "Number of patterns emitted");
58 cl::OptionCategory GlobalISelEmitterCat("Options for -gen-global-isel");
60 static cl::opt<bool> WarnOnSkippedPatterns(
61 "warn-on-skipped-patterns",
62 cl::desc("Explain why a pattern was skipped for inclusion "
63 "in the GlobalISel selector"),
64 cl::init(false), cl::cat(GlobalISelEmitterCat));
66 static cl::opt<bool> GenerateCoverage(
67 "instrument-gisel-coverage",
68 cl::desc("Generate coverage instrumentation for GlobalISel"),
69 cl::init(false), cl::cat(GlobalISelEmitterCat));
71 static cl::opt<std::string> UseCoverageFile(
72 "gisel-coverage-file", cl::init(""),
73 cl::desc("Specify file to retrieve coverage information from"),
74 cl::cat(GlobalISelEmitterCat));
76 static cl::opt<bool> OptimizeMatchTable(
77 "optimize-match-table",
78 cl::desc("Generate an optimized version of the match table"),
79 cl::init(true), cl::cat(GlobalISelEmitterCat));
82 //===- Helper functions ---------------------------------------------------===//
84 /// Get the name of the enum value used to number the predicate function.
85 std::string getEnumNameForPredicate(const TreePredicateFn &Predicate) {
86 if (Predicate.hasGISelPredicateCode())
87 return "GIPFP_MI_" + Predicate.getFnName();
88 return "GIPFP_" + Predicate.getImmTypeIdentifier().str() + "_" +
89 Predicate.getFnName();
92 /// Get the opcode used to check this predicate.
93 std::string getMatchOpcodeForPredicate(const TreePredicateFn &Predicate) {
94 return "GIM_Check" + Predicate.getImmTypeIdentifier().str() + "ImmPredicate";
97 /// This class stands in for LLT wherever we want to tablegen-erate an
98 /// equivalent at compiler run-time.
104 LLTCodeGen() = default;
105 LLTCodeGen(const LLT &Ty) : Ty(Ty) {}
107 std::string getCxxEnumValue() const {
109 raw_string_ostream OS(Str);
111 emitCxxEnumValue(OS);
115 void emitCxxEnumValue(raw_ostream &OS) const {
117 OS << "GILLT_s" << Ty.getSizeInBits();
121 OS << "GILLT_v" << Ty.getNumElements() << "s" << Ty.getScalarSizeInBits();
124 if (Ty.isPointer()) {
125 OS << "GILLT_p" << Ty.getAddressSpace();
126 if (Ty.getSizeInBits() > 0)
127 OS << "s" << Ty.getSizeInBits();
130 llvm_unreachable("Unhandled LLT");
133 void emitCxxConstructorCall(raw_ostream &OS) const {
135 OS << "LLT::scalar(" << Ty.getSizeInBits() << ")";
139 OS << "LLT::vector(" << Ty.getNumElements() << ", "
140 << Ty.getScalarSizeInBits() << ")";
143 if (Ty.isPointer() && Ty.getSizeInBits() > 0) {
144 OS << "LLT::pointer(" << Ty.getAddressSpace() << ", "
145 << Ty.getSizeInBits() << ")";
148 llvm_unreachable("Unhandled LLT");
151 const LLT &get() const { return Ty; }
153 /// This ordering is used for std::unique() and llvm::sort(). There's no
154 /// particular logic behind the order but either A < B or B < A must be
156 bool operator<(const LLTCodeGen &Other) const {
157 if (Ty.isValid() != Other.Ty.isValid())
158 return Ty.isValid() < Other.Ty.isValid();
162 if (Ty.isVector() != Other.Ty.isVector())
163 return Ty.isVector() < Other.Ty.isVector();
164 if (Ty.isScalar() != Other.Ty.isScalar())
165 return Ty.isScalar() < Other.Ty.isScalar();
166 if (Ty.isPointer() != Other.Ty.isPointer())
167 return Ty.isPointer() < Other.Ty.isPointer();
169 if (Ty.isPointer() && Ty.getAddressSpace() != Other.Ty.getAddressSpace())
170 return Ty.getAddressSpace() < Other.Ty.getAddressSpace();
172 if (Ty.isVector() && Ty.getNumElements() != Other.Ty.getNumElements())
173 return Ty.getNumElements() < Other.Ty.getNumElements();
175 return Ty.getSizeInBits() < Other.Ty.getSizeInBits();
178 bool operator==(const LLTCodeGen &B) const { return Ty == B.Ty; }
181 // Track all types that are used so we can emit the corresponding enum.
182 std::set<LLTCodeGen> KnownTypes;
184 class InstructionMatcher;
185 /// Convert an MVT to an equivalent LLT if possible, or the invalid LLT() for
186 /// MVTs that don't map cleanly to an LLT (e.g., iPTR, *any, ...).
187 static Optional<LLTCodeGen> MVTToLLT(MVT::SimpleValueType SVT) {
190 if (VT.isVector() && VT.getVectorNumElements() != 1)
192 LLT::vector(VT.getVectorNumElements(), VT.getScalarSizeInBits()));
194 if (VT.isInteger() || VT.isFloatingPoint())
195 return LLTCodeGen(LLT::scalar(VT.getSizeInBits()));
199 static std::string explainPredicates(const TreePatternNode *N) {
200 std::string Explanation = "";
201 StringRef Separator = "";
202 for (const TreePredicateCall &Call : N->getPredicateCalls()) {
203 const TreePredicateFn &P = Call.Fn;
205 (Separator + P.getOrigPatFragRecord()->getRecord()->getName()).str();
208 if (P.isAlwaysTrue())
209 Explanation += " always-true";
210 if (P.isImmediatePattern())
211 Explanation += " immediate";
214 Explanation += " unindexed";
216 if (P.isNonExtLoad())
217 Explanation += " non-extload";
218 if (P.isAnyExtLoad())
219 Explanation += " extload";
220 if (P.isSignExtLoad())
221 Explanation += " sextload";
222 if (P.isZeroExtLoad())
223 Explanation += " zextload";
225 if (P.isNonTruncStore())
226 Explanation += " non-truncstore";
227 if (P.isTruncStore())
228 Explanation += " truncstore";
230 if (Record *VT = P.getMemoryVT())
231 Explanation += (" MemVT=" + VT->getName()).str();
232 if (Record *VT = P.getScalarMemoryVT())
233 Explanation += (" ScalarVT(MemVT)=" + VT->getName()).str();
235 if (ListInit *AddrSpaces = P.getAddressSpaces()) {
236 raw_string_ostream OS(Explanation);
237 OS << " AddressSpaces=[";
239 StringRef AddrSpaceSeparator;
240 for (Init *Val : AddrSpaces->getValues()) {
241 IntInit *IntVal = dyn_cast<IntInit>(Val);
245 OS << AddrSpaceSeparator << IntVal->getValue();
246 AddrSpaceSeparator = ", ";
252 int64_t MinAlign = P.getMinAlignment();
254 Explanation += " MinAlign=" + utostr(MinAlign);
256 if (P.isAtomicOrderingMonotonic())
257 Explanation += " monotonic";
258 if (P.isAtomicOrderingAcquire())
259 Explanation += " acquire";
260 if (P.isAtomicOrderingRelease())
261 Explanation += " release";
262 if (P.isAtomicOrderingAcquireRelease())
263 Explanation += " acq_rel";
264 if (P.isAtomicOrderingSequentiallyConsistent())
265 Explanation += " seq_cst";
266 if (P.isAtomicOrderingAcquireOrStronger())
267 Explanation += " >=acquire";
268 if (P.isAtomicOrderingWeakerThanAcquire())
269 Explanation += " <acquire";
270 if (P.isAtomicOrderingReleaseOrStronger())
271 Explanation += " >=release";
272 if (P.isAtomicOrderingWeakerThanRelease())
273 Explanation += " <release";
278 std::string explainOperator(Record *Operator) {
279 if (Operator->isSubClassOf("SDNode"))
280 return (" (" + Operator->getValueAsString("Opcode") + ")").str();
282 if (Operator->isSubClassOf("Intrinsic"))
283 return (" (Operator is an Intrinsic, " + Operator->getName() + ")").str();
285 if (Operator->isSubClassOf("ComplexPattern"))
286 return (" (Operator is an unmapped ComplexPattern, " + Operator->getName() +
290 if (Operator->isSubClassOf("SDNodeXForm"))
291 return (" (Operator is an unmapped SDNodeXForm, " + Operator->getName() +
295 return (" (Operator " + Operator->getName() + " not understood)").str();
298 /// Helper function to let the emitter report skip reason error messages.
299 static Error failedImport(const Twine &Reason) {
300 return make_error<StringError>(Reason, inconvertibleErrorCode());
303 static Error isTrivialOperatorNode(const TreePatternNode *N) {
304 std::string Explanation = "";
305 std::string Separator = "";
307 bool HasUnsupportedPredicate = false;
308 for (const TreePredicateCall &Call : N->getPredicateCalls()) {
309 const TreePredicateFn &Predicate = Call.Fn;
311 if (Predicate.isAlwaysTrue())
314 if (Predicate.isImmediatePattern())
317 if (Predicate.isNonExtLoad() || Predicate.isAnyExtLoad() ||
318 Predicate.isSignExtLoad() || Predicate.isZeroExtLoad())
321 if (Predicate.isNonTruncStore() || Predicate.isTruncStore())
324 if (Predicate.isLoad() && Predicate.getMemoryVT())
327 if (Predicate.isLoad() || Predicate.isStore()) {
328 if (Predicate.isUnindexed())
332 if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
333 const ListInit *AddrSpaces = Predicate.getAddressSpaces();
334 if (AddrSpaces && !AddrSpaces->empty())
337 if (Predicate.getMinAlignment() > 0)
341 if (Predicate.isAtomic() && Predicate.getMemoryVT())
344 if (Predicate.isAtomic() &&
345 (Predicate.isAtomicOrderingMonotonic() ||
346 Predicate.isAtomicOrderingAcquire() ||
347 Predicate.isAtomicOrderingRelease() ||
348 Predicate.isAtomicOrderingAcquireRelease() ||
349 Predicate.isAtomicOrderingSequentiallyConsistent() ||
350 Predicate.isAtomicOrderingAcquireOrStronger() ||
351 Predicate.isAtomicOrderingWeakerThanAcquire() ||
352 Predicate.isAtomicOrderingReleaseOrStronger() ||
353 Predicate.isAtomicOrderingWeakerThanRelease()))
356 if (Predicate.hasGISelPredicateCode())
359 HasUnsupportedPredicate = true;
360 Explanation = Separator + "Has a predicate (" + explainPredicates(N) + ")";
362 Explanation += (Separator + "first-failing:" +
363 Predicate.getOrigPatFragRecord()->getRecord()->getName())
368 if (!HasUnsupportedPredicate)
369 return Error::success();
371 return failedImport(Explanation);
374 static Record *getInitValueAsRegClass(Init *V) {
375 if (DefInit *VDefInit = dyn_cast<DefInit>(V)) {
376 if (VDefInit->getDef()->isSubClassOf("RegisterOperand"))
377 return VDefInit->getDef()->getValueAsDef("RegClass");
378 if (VDefInit->getDef()->isSubClassOf("RegisterClass"))
379 return VDefInit->getDef();
385 getNameForFeatureBitset(const std::vector<Record *> &FeatureBitset) {
386 std::string Name = "GIFBS";
387 for (const auto &Feature : FeatureBitset)
388 Name += ("_" + Feature->getName()).str();
392 //===- MatchTable Helpers -------------------------------------------------===//
396 /// A record to be stored in a MatchTable.
398 /// This class represents any and all output that may be required to emit the
399 /// MatchTable. Instances are most often configured to represent an opcode or
400 /// value that will be emitted to the table with some formatting but it can also
401 /// represent commas, comments, and other formatting instructions.
402 struct MatchTableRecord {
403 enum RecordFlagsBits {
405 /// Causes EmitStr to be formatted as comment when emitted.
407 /// Causes the record value to be followed by a comma when emitted.
408 MTRF_CommaFollows = 0x2,
409 /// Causes the record value to be followed by a line break when emitted.
410 MTRF_LineBreakFollows = 0x4,
411 /// Indicates that the record defines a label and causes an additional
412 /// comment to be emitted containing the index of the label.
414 /// Causes the record to be emitted as the index of the label specified by
415 /// LabelID along with a comment indicating where that label is.
416 MTRF_JumpTarget = 0x10,
417 /// Causes the formatter to add a level of indentation before emitting the
420 /// Causes the formatter to remove a level of indentation after emitting the
425 /// When MTRF_Label or MTRF_JumpTarget is used, indicates a label id to
426 /// reference or define.
428 /// The string to emit. Depending on the MTRF_* flags it may be a comment, a
429 /// value, a label name.
433 /// The number of MatchTable elements described by this record. Comments are 0
434 /// while values are typically 1. Values >1 may occur when we need to emit
435 /// values that exceed the size of a MatchTable element.
436 unsigned NumElements;
439 /// A bitfield of RecordFlagsBits flags.
442 /// The actual run-time value, if known
445 MatchTableRecord(Optional<unsigned> LabelID_, StringRef EmitStr,
446 unsigned NumElements, unsigned Flags,
447 int64_t RawValue = std::numeric_limits<int64_t>::min())
448 : LabelID(LabelID_.hasValue() ? LabelID_.getValue() : ~0u),
449 EmitStr(EmitStr), NumElements(NumElements), Flags(Flags),
452 assert((!LabelID_.hasValue() || LabelID != ~0u) &&
453 "This value is reserved for non-labels");
455 MatchTableRecord(const MatchTableRecord &Other) = default;
456 MatchTableRecord(MatchTableRecord &&Other) = default;
458 /// Useful if a Match Table Record gets optimized out
459 void turnIntoComment() {
460 Flags |= MTRF_Comment;
461 Flags &= ~MTRF_CommaFollows;
465 /// For Jump Table generation purposes
466 bool operator<(const MatchTableRecord &Other) const {
467 return RawValue < Other.RawValue;
469 int64_t getRawValue() const { return RawValue; }
471 void emit(raw_ostream &OS, bool LineBreakNextAfterThis,
472 const MatchTable &Table) const;
473 unsigned size() const { return NumElements; }
478 /// Holds the contents of a generated MatchTable to enable formatting and the
479 /// necessary index tracking needed to support GIM_Try.
481 /// An unique identifier for the table. The generated table will be named
484 /// The records that make up the table. Also includes comments describing the
485 /// values being emitted and line breaks to format it.
486 std::vector<MatchTableRecord> Contents;
487 /// The currently defined labels.
488 DenseMap<unsigned, unsigned> LabelMap;
489 /// Tracks the sum of MatchTableRecord::NumElements as the table is built.
490 unsigned CurrentSize = 0;
491 /// A unique identifier for a MatchTable label.
492 unsigned CurrentLabelID = 0;
493 /// Determines if the table should be instrumented for rule coverage tracking.
497 static MatchTableRecord LineBreak;
498 static MatchTableRecord Comment(StringRef Comment) {
499 return MatchTableRecord(None, Comment, 0, MatchTableRecord::MTRF_Comment);
501 static MatchTableRecord Opcode(StringRef Opcode, int IndentAdjust = 0) {
502 unsigned ExtraFlags = 0;
503 if (IndentAdjust > 0)
504 ExtraFlags |= MatchTableRecord::MTRF_Indent;
505 if (IndentAdjust < 0)
506 ExtraFlags |= MatchTableRecord::MTRF_Outdent;
508 return MatchTableRecord(None, Opcode, 1,
509 MatchTableRecord::MTRF_CommaFollows | ExtraFlags);
511 static MatchTableRecord NamedValue(StringRef NamedValue) {
512 return MatchTableRecord(None, NamedValue, 1,
513 MatchTableRecord::MTRF_CommaFollows);
515 static MatchTableRecord NamedValue(StringRef NamedValue, int64_t RawValue) {
516 return MatchTableRecord(None, NamedValue, 1,
517 MatchTableRecord::MTRF_CommaFollows, RawValue);
519 static MatchTableRecord NamedValue(StringRef Namespace,
520 StringRef NamedValue) {
521 return MatchTableRecord(None, (Namespace + "::" + NamedValue).str(), 1,
522 MatchTableRecord::MTRF_CommaFollows);
524 static MatchTableRecord NamedValue(StringRef Namespace, StringRef NamedValue,
526 return MatchTableRecord(None, (Namespace + "::" + NamedValue).str(), 1,
527 MatchTableRecord::MTRF_CommaFollows, RawValue);
529 static MatchTableRecord IntValue(int64_t IntValue) {
530 return MatchTableRecord(None, llvm::to_string(IntValue), 1,
531 MatchTableRecord::MTRF_CommaFollows);
533 static MatchTableRecord Label(unsigned LabelID) {
534 return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 0,
535 MatchTableRecord::MTRF_Label |
536 MatchTableRecord::MTRF_Comment |
537 MatchTableRecord::MTRF_LineBreakFollows);
539 static MatchTableRecord JumpTarget(unsigned LabelID) {
540 return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 1,
541 MatchTableRecord::MTRF_JumpTarget |
542 MatchTableRecord::MTRF_Comment |
543 MatchTableRecord::MTRF_CommaFollows);
546 static MatchTable buildTable(ArrayRef<Matcher *> Rules, bool WithCoverage);
548 MatchTable(bool WithCoverage, unsigned ID = 0)
549 : ID(ID), IsWithCoverage(WithCoverage) {}
551 bool isWithCoverage() const { return IsWithCoverage; }
553 void push_back(const MatchTableRecord &Value) {
554 if (Value.Flags & MatchTableRecord::MTRF_Label)
555 defineLabel(Value.LabelID);
556 Contents.push_back(Value);
557 CurrentSize += Value.size();
560 unsigned allocateLabelID() { return CurrentLabelID++; }
562 void defineLabel(unsigned LabelID) {
563 LabelMap.insert(std::make_pair(LabelID, CurrentSize));
566 unsigned getLabelIndex(unsigned LabelID) const {
567 const auto I = LabelMap.find(LabelID);
568 assert(I != LabelMap.end() && "Use of undeclared label");
572 void emitUse(raw_ostream &OS) const { OS << "MatchTable" << ID; }
574 void emitDeclaration(raw_ostream &OS) const {
575 unsigned Indentation = 4;
576 OS << " constexpr static int64_t MatchTable" << ID << "[] = {";
577 LineBreak.emit(OS, true, *this);
578 OS << std::string(Indentation, ' ');
580 for (auto I = Contents.begin(), E = Contents.end(); I != E;
582 bool LineBreakIsNext = false;
583 const auto &NextI = std::next(I);
586 if (NextI->EmitStr == "" &&
587 NextI->Flags == MatchTableRecord::MTRF_LineBreakFollows)
588 LineBreakIsNext = true;
591 if (I->Flags & MatchTableRecord::MTRF_Indent)
594 I->emit(OS, LineBreakIsNext, *this);
595 if (I->Flags & MatchTableRecord::MTRF_LineBreakFollows)
596 OS << std::string(Indentation, ' ');
598 if (I->Flags & MatchTableRecord::MTRF_Outdent)
605 MatchTableRecord MatchTable::LineBreak = {
606 None, "" /* Emit String */, 0 /* Elements */,
607 MatchTableRecord::MTRF_LineBreakFollows};
609 void MatchTableRecord::emit(raw_ostream &OS, bool LineBreakIsNextAfterThis,
610 const MatchTable &Table) const {
611 bool UseLineComment =
612 LineBreakIsNextAfterThis | (Flags & MTRF_LineBreakFollows);
613 if (Flags & (MTRF_JumpTarget | MTRF_CommaFollows))
614 UseLineComment = false;
616 if (Flags & MTRF_Comment)
617 OS << (UseLineComment ? "// " : "/*");
620 if (Flags & MTRF_Label)
621 OS << ": @" << Table.getLabelIndex(LabelID);
623 if (Flags & MTRF_Comment && !UseLineComment)
626 if (Flags & MTRF_JumpTarget) {
627 if (Flags & MTRF_Comment)
629 OS << Table.getLabelIndex(LabelID);
632 if (Flags & MTRF_CommaFollows) {
634 if (!LineBreakIsNextAfterThis && !(Flags & MTRF_LineBreakFollows))
638 if (Flags & MTRF_LineBreakFollows)
642 MatchTable &operator<<(MatchTable &Table, const MatchTableRecord &Value) {
643 Table.push_back(Value);
647 //===- Matchers -----------------------------------------------------------===//
649 class OperandMatcher;
651 class PredicateMatcher;
656 virtual ~Matcher() = default;
657 virtual void optimize() {}
658 virtual void emit(MatchTable &Table) = 0;
660 virtual bool hasFirstCondition() const = 0;
661 virtual const PredicateMatcher &getFirstCondition() const = 0;
662 virtual std::unique_ptr<PredicateMatcher> popFirstCondition() = 0;
665 MatchTable MatchTable::buildTable(ArrayRef<Matcher *> Rules,
667 MatchTable Table(WithCoverage);
668 for (Matcher *Rule : Rules)
671 return Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
674 class GroupMatcher final : public Matcher {
675 /// Conditions that form a common prefix of all the matchers contained.
676 SmallVector<std::unique_ptr<PredicateMatcher>, 1> Conditions;
678 /// All the nested matchers, sharing a common prefix.
679 std::vector<Matcher *> Matchers;
681 /// An owning collection for any auxiliary matchers created while optimizing
682 /// nested matchers contained.
683 std::vector<std::unique_ptr<Matcher>> MatcherStorage;
686 /// Add a matcher to the collection of nested matchers if it meets the
687 /// requirements, and return true. If it doesn't, do nothing and return false.
689 /// Expected to preserve its argument, so it could be moved out later on.
690 bool addMatcher(Matcher &Candidate);
692 /// Mark the matcher as fully-built and ensure any invariants expected by both
693 /// optimize() and emit(...) methods. Generally, both sequences of calls
694 /// are expected to lead to a sensible result:
696 /// addMatcher(...)*; finalize(); optimize(); emit(...); and
697 /// addMatcher(...)*; finalize(); emit(...);
701 /// addMatcher(...)*; finalize(); { optimize()*; emit(...); }*
703 /// Multiple calls to optimize() are expected to be handled gracefully, though
704 /// optimize() is not expected to be idempotent. Multiple calls to finalize()
705 /// aren't generally supported. emit(...) is expected to be non-mutating and
706 /// producing the exact same results upon repeated calls.
708 /// addMatcher() calls after the finalize() call are not supported.
710 /// finalize() and optimize() are both allowed to mutate the contained
711 /// matchers, so moving them out after finalize() is not supported.
713 void optimize() override;
714 void emit(MatchTable &Table) override;
716 /// Could be used to move out the matchers added previously, unless finalize()
717 /// has been already called. If any of the matchers are moved out, the group
718 /// becomes safe to destroy, but not safe to re-use for anything else.
719 iterator_range<std::vector<Matcher *>::iterator> matchers() {
720 return make_range(Matchers.begin(), Matchers.end());
722 size_t size() const { return Matchers.size(); }
723 bool empty() const { return Matchers.empty(); }
725 std::unique_ptr<PredicateMatcher> popFirstCondition() override {
726 assert(!Conditions.empty() &&
727 "Trying to pop a condition from a condition-less group");
728 std::unique_ptr<PredicateMatcher> P = std::move(Conditions.front());
729 Conditions.erase(Conditions.begin());
732 const PredicateMatcher &getFirstCondition() const override {
733 assert(!Conditions.empty() &&
734 "Trying to get a condition from a condition-less group");
735 return *Conditions.front();
737 bool hasFirstCondition() const override { return !Conditions.empty(); }
740 /// See if a candidate matcher could be added to this group solely by
741 /// analyzing its first condition.
742 bool candidateConditionMatches(const PredicateMatcher &Predicate) const;
745 class SwitchMatcher : public Matcher {
746 /// All the nested matchers, representing distinct switch-cases. The first
747 /// conditions (as Matcher::getFirstCondition() reports) of all the nested
748 /// matchers must share the same type and path to a value they check, in other
749 /// words, be isIdenticalDownToValue, but have different values they check
751 std::vector<Matcher *> Matchers;
753 /// The representative condition, with a type and a path (InsnVarID and OpIdx
754 /// in most cases) shared by all the matchers contained.
755 std::unique_ptr<PredicateMatcher> Condition = nullptr;
757 /// Temporary set used to check that the case values don't repeat within the
759 std::set<MatchTableRecord> Values;
761 /// An owning collection for any auxiliary matchers created while optimizing
762 /// nested matchers contained.
763 std::vector<std::unique_ptr<Matcher>> MatcherStorage;
766 bool addMatcher(Matcher &Candidate);
769 void emit(MatchTable &Table) override;
771 iterator_range<std::vector<Matcher *>::iterator> matchers() {
772 return make_range(Matchers.begin(), Matchers.end());
774 size_t size() const { return Matchers.size(); }
775 bool empty() const { return Matchers.empty(); }
777 std::unique_ptr<PredicateMatcher> popFirstCondition() override {
778 // SwitchMatcher doesn't have a common first condition for its cases, as all
779 // the cases only share a kind of a value (a type and a path to it) they
780 // match, but deliberately differ in the actual value they match.
781 llvm_unreachable("Trying to pop a condition from a condition-less group");
783 const PredicateMatcher &getFirstCondition() const override {
784 llvm_unreachable("Trying to pop a condition from a condition-less group");
786 bool hasFirstCondition() const override { return false; }
789 /// See if the predicate type has a Switch-implementation for it.
790 static bool isSupportedPredicateType(const PredicateMatcher &Predicate);
792 bool candidateConditionMatches(const PredicateMatcher &Predicate) const;
795 static void emitPredicateSpecificOpcodes(const PredicateMatcher &P,
799 /// Generates code to check that a match rule matches.
800 class RuleMatcher : public Matcher {
802 using ActionList = std::list<std::unique_ptr<MatchAction>>;
803 using action_iterator = ActionList::iterator;
806 /// A list of matchers that all need to succeed for the current rule to match.
807 /// FIXME: This currently supports a single match position but could be
808 /// extended to support multiple positions to support div/rem fusion or
809 /// load-multiple instructions.
810 using MatchersTy = std::vector<std::unique_ptr<InstructionMatcher>> ;
813 /// A list of actions that need to be taken when all predicates in this rule
817 using DefinedInsnVariablesMap = std::map<InstructionMatcher *, unsigned>;
819 /// A map of instruction matchers to the local variables
820 DefinedInsnVariablesMap InsnVariableIDs;
822 using MutatableInsnSet = SmallPtrSet<InstructionMatcher *, 4>;
824 // The set of instruction matchers that have not yet been claimed for mutation
826 MutatableInsnSet MutatableInsns;
828 /// A map of named operands defined by the matchers that may be referenced by
830 StringMap<OperandMatcher *> DefinedOperands;
832 /// A map of anonymous physical register operands defined by the matchers that
833 /// may be referenced by the renderers.
834 DenseMap<Record *, OperandMatcher *> PhysRegOperands;
836 /// ID for the next instruction variable defined with implicitlyDefineInsnVar()
837 unsigned NextInsnVarID;
839 /// ID for the next output instruction allocated with allocateOutputInsnID()
840 unsigned NextOutputInsnID;
842 /// ID for the next temporary register ID allocated with allocateTempRegID()
843 unsigned NextTempRegID;
845 std::vector<Record *> RequiredFeatures;
846 std::vector<std::unique_ptr<PredicateMatcher>> EpilogueMatchers;
848 ArrayRef<SMLoc> SrcLoc;
850 typedef std::tuple<Record *, unsigned, unsigned>
851 DefinedComplexPatternSubOperand;
852 typedef StringMap<DefinedComplexPatternSubOperand>
853 DefinedComplexPatternSubOperandMap;
854 /// A map of Symbolic Names to ComplexPattern sub-operands.
855 DefinedComplexPatternSubOperandMap ComplexSubOperands;
858 static uint64_t NextRuleID;
861 RuleMatcher(ArrayRef<SMLoc> SrcLoc)
862 : Matchers(), Actions(), InsnVariableIDs(), MutatableInsns(),
863 DefinedOperands(), NextInsnVarID(0), NextOutputInsnID(0),
864 NextTempRegID(0), SrcLoc(SrcLoc), ComplexSubOperands(),
865 RuleID(NextRuleID++) {}
866 RuleMatcher(RuleMatcher &&Other) = default;
867 RuleMatcher &operator=(RuleMatcher &&Other) = default;
869 uint64_t getRuleID() const { return RuleID; }
871 InstructionMatcher &addInstructionMatcher(StringRef SymbolicName);
872 void addRequiredFeature(Record *Feature);
873 const std::vector<Record *> &getRequiredFeatures() const;
875 template <class Kind, class... Args> Kind &addAction(Args &&... args);
876 template <class Kind, class... Args>
877 action_iterator insertAction(action_iterator InsertPt, Args &&... args);
879 /// Define an instruction without emitting any code to do so.
880 unsigned implicitlyDefineInsnVar(InstructionMatcher &Matcher);
882 unsigned getInsnVarID(InstructionMatcher &InsnMatcher) const;
883 DefinedInsnVariablesMap::const_iterator defined_insn_vars_begin() const {
884 return InsnVariableIDs.begin();
886 DefinedInsnVariablesMap::const_iterator defined_insn_vars_end() const {
887 return InsnVariableIDs.end();
889 iterator_range<typename DefinedInsnVariablesMap::const_iterator>
890 defined_insn_vars() const {
891 return make_range(defined_insn_vars_begin(), defined_insn_vars_end());
894 MutatableInsnSet::const_iterator mutatable_insns_begin() const {
895 return MutatableInsns.begin();
897 MutatableInsnSet::const_iterator mutatable_insns_end() const {
898 return MutatableInsns.end();
900 iterator_range<typename MutatableInsnSet::const_iterator>
901 mutatable_insns() const {
902 return make_range(mutatable_insns_begin(), mutatable_insns_end());
904 void reserveInsnMatcherForMutation(InstructionMatcher *InsnMatcher) {
905 bool R = MutatableInsns.erase(InsnMatcher);
906 assert(R && "Reserving a mutatable insn that isn't available");
910 action_iterator actions_begin() { return Actions.begin(); }
911 action_iterator actions_end() { return Actions.end(); }
912 iterator_range<action_iterator> actions() {
913 return make_range(actions_begin(), actions_end());
916 void defineOperand(StringRef SymbolicName, OperandMatcher &OM);
918 void definePhysRegOperand(Record *Reg, OperandMatcher &OM);
920 Error defineComplexSubOperand(StringRef SymbolicName, Record *ComplexPattern,
921 unsigned RendererID, unsigned SubOperandID) {
922 if (ComplexSubOperands.count(SymbolicName))
924 "Complex suboperand referenced more than once (Operand: " +
927 ComplexSubOperands[SymbolicName] =
928 std::make_tuple(ComplexPattern, RendererID, SubOperandID);
930 return Error::success();
933 Optional<DefinedComplexPatternSubOperand>
934 getComplexSubOperand(StringRef SymbolicName) const {
935 const auto &I = ComplexSubOperands.find(SymbolicName);
936 if (I == ComplexSubOperands.end())
941 InstructionMatcher &getInstructionMatcher(StringRef SymbolicName) const;
942 const OperandMatcher &getOperandMatcher(StringRef Name) const;
943 const OperandMatcher &getPhysRegOperandMatcher(Record *) const;
945 void optimize() override;
946 void emit(MatchTable &Table) override;
948 /// Compare the priority of this object and B.
950 /// Returns true if this object is more important than B.
951 bool isHigherPriorityThan(const RuleMatcher &B) const;
953 /// Report the maximum number of temporary operands needed by the rule
955 unsigned countRendererFns() const;
957 std::unique_ptr<PredicateMatcher> popFirstCondition() override;
958 const PredicateMatcher &getFirstCondition() const override;
959 LLTCodeGen getFirstConditionAsRootType();
960 bool hasFirstCondition() const override;
961 unsigned getNumOperands() const;
962 StringRef getOpcode() const;
964 // FIXME: Remove this as soon as possible
965 InstructionMatcher &insnmatchers_front() const { return *Matchers.front(); }
967 unsigned allocateOutputInsnID() { return NextOutputInsnID++; }
968 unsigned allocateTempRegID() { return NextTempRegID++; }
970 iterator_range<MatchersTy::iterator> insnmatchers() {
971 return make_range(Matchers.begin(), Matchers.end());
973 bool insnmatchers_empty() const { return Matchers.empty(); }
974 void insnmatchers_pop_front() { Matchers.erase(Matchers.begin()); }
977 uint64_t RuleMatcher::NextRuleID = 0;
979 using action_iterator = RuleMatcher::action_iterator;
981 template <class PredicateTy> class PredicateListMatcher {
983 /// Template instantiations should specialize this to return a string to use
984 /// for the comment emitted when there are no predicates.
985 std::string getNoPredicateComment() const;
988 using PredicatesTy = std::deque<std::unique_ptr<PredicateTy>>;
989 PredicatesTy Predicates;
991 /// Track if the list of predicates was manipulated by one of the optimization
993 bool Optimized = false;
996 /// Construct a new predicate and add it to the matcher.
997 template <class Kind, class... Args>
998 Optional<Kind *> addPredicate(Args &&... args);
1000 typename PredicatesTy::iterator predicates_begin() {
1001 return Predicates.begin();
1003 typename PredicatesTy::iterator predicates_end() {
1004 return Predicates.end();
1006 iterator_range<typename PredicatesTy::iterator> predicates() {
1007 return make_range(predicates_begin(), predicates_end());
1009 typename PredicatesTy::size_type predicates_size() const {
1010 return Predicates.size();
1012 bool predicates_empty() const { return Predicates.empty(); }
1014 std::unique_ptr<PredicateTy> predicates_pop_front() {
1015 std::unique_ptr<PredicateTy> Front = std::move(Predicates.front());
1016 Predicates.pop_front();
1021 void prependPredicate(std::unique_ptr<PredicateTy> &&Predicate) {
1022 Predicates.push_front(std::move(Predicate));
1025 void eraseNullPredicates() {
1027 std::stable_partition(Predicates.begin(), Predicates.end(),
1028 std::logical_not<std::unique_ptr<PredicateTy>>());
1029 if (NewEnd != Predicates.begin()) {
1030 Predicates.erase(Predicates.begin(), NewEnd);
1035 /// Emit MatchTable opcodes that tests whether all the predicates are met.
1036 template <class... Args>
1037 void emitPredicateListOpcodes(MatchTable &Table, Args &&... args) {
1038 if (Predicates.empty() && !Optimized) {
1039 Table << MatchTable::Comment(getNoPredicateComment())
1040 << MatchTable::LineBreak;
1044 for (const auto &Predicate : predicates())
1045 Predicate->emitPredicateOpcodes(Table, std::forward<Args>(args)...);
1049 class PredicateMatcher {
1051 /// This enum is used for RTTI and also defines the priority that is given to
1052 /// the predicate when generating the matcher code. Kinds with higher priority
1053 /// must be tested first.
1055 /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter
1056 /// but OPM_Int must have priority over OPM_RegBank since constant integers
1057 /// are represented by a virtual register defined by a G_CONSTANT instruction.
1059 /// Note: The relative priority between IPM_ and OPM_ does not matter, they
1060 /// are currently not compared between each other.
1061 enum PredicateKind {
1066 IPM_AtomicOrderingMMO,
1068 IPM_MemoryVsLLTSize,
1069 IPM_MemoryAddressSpace,
1070 IPM_MemoryAlignment,
1071 IPM_GenericPredicate,
1091 PredicateMatcher(PredicateKind Kind, unsigned InsnVarID, unsigned OpIdx = ~0)
1092 : Kind(Kind), InsnVarID(InsnVarID), OpIdx(OpIdx) {}
1094 unsigned getInsnVarID() const { return InsnVarID; }
1095 unsigned getOpIdx() const { return OpIdx; }
1097 virtual ~PredicateMatcher() = default;
1098 /// Emit MatchTable opcodes that check the predicate for the given operand.
1099 virtual void emitPredicateOpcodes(MatchTable &Table,
1100 RuleMatcher &Rule) const = 0;
1102 PredicateKind getKind() const { return Kind; }
1104 virtual bool isIdentical(const PredicateMatcher &B) const {
1105 return B.getKind() == getKind() && InsnVarID == B.InsnVarID &&
1109 virtual bool isIdenticalDownToValue(const PredicateMatcher &B) const {
1110 return hasValue() && PredicateMatcher::isIdentical(B);
1113 virtual MatchTableRecord getValue() const {
1114 assert(hasValue() && "Can not get a value of a value-less predicate!");
1115 llvm_unreachable("Not implemented yet");
1117 virtual bool hasValue() const { return false; }
1119 /// Report the maximum number of temporary operands needed by the predicate
1121 virtual unsigned countRendererFns() const { return 0; }
1124 /// Generates code to check a predicate of an operand.
1126 /// Typical predicates include:
1127 /// * Operand is a particular register.
1128 /// * Operand is assigned a particular register bank.
1129 /// * Operand is an MBB.
1130 class OperandPredicateMatcher : public PredicateMatcher {
1132 OperandPredicateMatcher(PredicateKind Kind, unsigned InsnVarID,
1134 : PredicateMatcher(Kind, InsnVarID, OpIdx) {}
1135 virtual ~OperandPredicateMatcher() {}
1137 /// Compare the priority of this object and B.
1139 /// Returns true if this object is more important than B.
1140 virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const;
1145 PredicateListMatcher<OperandPredicateMatcher>::getNoPredicateComment() const {
1146 return "No operand predicates";
1149 /// Generates code to check that a register operand is defined by the same exact
1151 class SameOperandMatcher : public OperandPredicateMatcher {
1152 std::string MatchingName;
1155 SameOperandMatcher(unsigned InsnVarID, unsigned OpIdx, StringRef MatchingName)
1156 : OperandPredicateMatcher(OPM_SameOperand, InsnVarID, OpIdx),
1157 MatchingName(MatchingName) {}
1159 static bool classof(const PredicateMatcher *P) {
1160 return P->getKind() == OPM_SameOperand;
1163 void emitPredicateOpcodes(MatchTable &Table,
1164 RuleMatcher &Rule) const override;
1166 bool isIdentical(const PredicateMatcher &B) const override {
1167 return OperandPredicateMatcher::isIdentical(B) &&
1168 MatchingName == cast<SameOperandMatcher>(&B)->MatchingName;
1172 /// Generates code to check that an operand is a particular LLT.
1173 class LLTOperandMatcher : public OperandPredicateMatcher {
1178 static std::map<LLTCodeGen, unsigned> TypeIDValues;
1180 static void initTypeIDValuesMap() {
1181 TypeIDValues.clear();
1184 for (const LLTCodeGen LLTy : KnownTypes)
1185 TypeIDValues[LLTy] = ID++;
1188 LLTOperandMatcher(unsigned InsnVarID, unsigned OpIdx, const LLTCodeGen &Ty)
1189 : OperandPredicateMatcher(OPM_LLT, InsnVarID, OpIdx), Ty(Ty) {
1190 KnownTypes.insert(Ty);
1193 static bool classof(const PredicateMatcher *P) {
1194 return P->getKind() == OPM_LLT;
1196 bool isIdentical(const PredicateMatcher &B) const override {
1197 return OperandPredicateMatcher::isIdentical(B) &&
1198 Ty == cast<LLTOperandMatcher>(&B)->Ty;
1200 MatchTableRecord getValue() const override {
1201 const auto VI = TypeIDValues.find(Ty);
1202 if (VI == TypeIDValues.end())
1203 return MatchTable::NamedValue(getTy().getCxxEnumValue());
1204 return MatchTable::NamedValue(getTy().getCxxEnumValue(), VI->second);
1206 bool hasValue() const override {
1207 if (TypeIDValues.size() != KnownTypes.size())
1208 initTypeIDValuesMap();
1209 return TypeIDValues.count(Ty);
1212 LLTCodeGen getTy() const { return Ty; }
1214 void emitPredicateOpcodes(MatchTable &Table,
1215 RuleMatcher &Rule) const override {
1216 Table << MatchTable::Opcode("GIM_CheckType") << MatchTable::Comment("MI")
1217 << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
1218 << MatchTable::IntValue(OpIdx) << MatchTable::Comment("Type")
1219 << getValue() << MatchTable::LineBreak;
1223 std::map<LLTCodeGen, unsigned> LLTOperandMatcher::TypeIDValues;
1225 /// Generates code to check that an operand is a pointer to any address space.
1227 /// In SelectionDAG, the types did not describe pointers or address spaces. As a
1228 /// result, iN is used to describe a pointer of N bits to any address space and
1229 /// PatFrag predicates are typically used to constrain the address space. There's
1230 /// no reliable means to derive the missing type information from the pattern so
1231 /// imported rules must test the components of a pointer separately.
1233 /// If SizeInBits is zero, then the pointer size will be obtained from the
1235 class PointerToAnyOperandMatcher : public OperandPredicateMatcher {
1237 unsigned SizeInBits;
1240 PointerToAnyOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1241 unsigned SizeInBits)
1242 : OperandPredicateMatcher(OPM_PointerToAny, InsnVarID, OpIdx),
1243 SizeInBits(SizeInBits) {}
1245 static bool classof(const OperandPredicateMatcher *P) {
1246 return P->getKind() == OPM_PointerToAny;
1249 void emitPredicateOpcodes(MatchTable &Table,
1250 RuleMatcher &Rule) const override {
1251 Table << MatchTable::Opcode("GIM_CheckPointerToAny")
1252 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1253 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1254 << MatchTable::Comment("SizeInBits")
1255 << MatchTable::IntValue(SizeInBits) << MatchTable::LineBreak;
1259 /// Generates code to check that an operand is a particular target constant.
1260 class ComplexPatternOperandMatcher : public OperandPredicateMatcher {
1262 const OperandMatcher &Operand;
1263 const Record &TheDef;
1265 unsigned getAllocatedTemporariesBaseID() const;
1268 bool isIdentical(const PredicateMatcher &B) const override { return false; }
1270 ComplexPatternOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1271 const OperandMatcher &Operand,
1272 const Record &TheDef)
1273 : OperandPredicateMatcher(OPM_ComplexPattern, InsnVarID, OpIdx),
1274 Operand(Operand), TheDef(TheDef) {}
1276 static bool classof(const PredicateMatcher *P) {
1277 return P->getKind() == OPM_ComplexPattern;
1280 void emitPredicateOpcodes(MatchTable &Table,
1281 RuleMatcher &Rule) const override {
1282 unsigned ID = getAllocatedTemporariesBaseID();
1283 Table << MatchTable::Opcode("GIM_CheckComplexPattern")
1284 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1285 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1286 << MatchTable::Comment("Renderer") << MatchTable::IntValue(ID)
1287 << MatchTable::NamedValue(("GICP_" + TheDef.getName()).str())
1288 << MatchTable::LineBreak;
1291 unsigned countRendererFns() const override {
1296 /// Generates code to check that an operand is in a particular register bank.
1297 class RegisterBankOperandMatcher : public OperandPredicateMatcher {
1299 const CodeGenRegisterClass &RC;
1302 RegisterBankOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1303 const CodeGenRegisterClass &RC)
1304 : OperandPredicateMatcher(OPM_RegBank, InsnVarID, OpIdx), RC(RC) {}
1306 bool isIdentical(const PredicateMatcher &B) const override {
1307 return OperandPredicateMatcher::isIdentical(B) &&
1308 RC.getDef() == cast<RegisterBankOperandMatcher>(&B)->RC.getDef();
1311 static bool classof(const PredicateMatcher *P) {
1312 return P->getKind() == OPM_RegBank;
1315 void emitPredicateOpcodes(MatchTable &Table,
1316 RuleMatcher &Rule) const override {
1317 Table << MatchTable::Opcode("GIM_CheckRegBankForClass")
1318 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1319 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1320 << MatchTable::Comment("RC")
1321 << MatchTable::NamedValue(RC.getQualifiedName() + "RegClassID")
1322 << MatchTable::LineBreak;
1326 /// Generates code to check that an operand is a basic block.
1327 class MBBOperandMatcher : public OperandPredicateMatcher {
1329 MBBOperandMatcher(unsigned InsnVarID, unsigned OpIdx)
1330 : OperandPredicateMatcher(OPM_MBB, InsnVarID, OpIdx) {}
1332 static bool classof(const PredicateMatcher *P) {
1333 return P->getKind() == OPM_MBB;
1336 void emitPredicateOpcodes(MatchTable &Table,
1337 RuleMatcher &Rule) const override {
1338 Table << MatchTable::Opcode("GIM_CheckIsMBB") << MatchTable::Comment("MI")
1339 << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
1340 << MatchTable::IntValue(OpIdx) << MatchTable::LineBreak;
1344 class ImmOperandMatcher : public OperandPredicateMatcher {
1346 ImmOperandMatcher(unsigned InsnVarID, unsigned OpIdx)
1347 : OperandPredicateMatcher(IPM_Imm, InsnVarID, OpIdx) {}
1349 static bool classof(const PredicateMatcher *P) {
1350 return P->getKind() == IPM_Imm;
1353 void emitPredicateOpcodes(MatchTable &Table,
1354 RuleMatcher &Rule) const override {
1355 Table << MatchTable::Opcode("GIM_CheckIsImm") << MatchTable::Comment("MI")
1356 << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
1357 << MatchTable::IntValue(OpIdx) << MatchTable::LineBreak;
1361 /// Generates code to check that an operand is a G_CONSTANT with a particular
1363 class ConstantIntOperandMatcher : public OperandPredicateMatcher {
1368 ConstantIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value)
1369 : OperandPredicateMatcher(OPM_Int, InsnVarID, OpIdx), Value(Value) {}
1371 bool isIdentical(const PredicateMatcher &B) const override {
1372 return OperandPredicateMatcher::isIdentical(B) &&
1373 Value == cast<ConstantIntOperandMatcher>(&B)->Value;
1376 static bool classof(const PredicateMatcher *P) {
1377 return P->getKind() == OPM_Int;
1380 void emitPredicateOpcodes(MatchTable &Table,
1381 RuleMatcher &Rule) const override {
1382 Table << MatchTable::Opcode("GIM_CheckConstantInt")
1383 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1384 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1385 << MatchTable::IntValue(Value) << MatchTable::LineBreak;
1389 /// Generates code to check that an operand is a raw int (where MO.isImm() or
1390 /// MO.isCImm() is true).
1391 class LiteralIntOperandMatcher : public OperandPredicateMatcher {
1396 LiteralIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value)
1397 : OperandPredicateMatcher(OPM_LiteralInt, InsnVarID, OpIdx),
1400 bool isIdentical(const PredicateMatcher &B) const override {
1401 return OperandPredicateMatcher::isIdentical(B) &&
1402 Value == cast<LiteralIntOperandMatcher>(&B)->Value;
1405 static bool classof(const PredicateMatcher *P) {
1406 return P->getKind() == OPM_LiteralInt;
1409 void emitPredicateOpcodes(MatchTable &Table,
1410 RuleMatcher &Rule) const override {
1411 Table << MatchTable::Opcode("GIM_CheckLiteralInt")
1412 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1413 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1414 << MatchTable::IntValue(Value) << MatchTable::LineBreak;
1418 /// Generates code to check that an operand is an CmpInst predicate
1419 class CmpPredicateOperandMatcher : public OperandPredicateMatcher {
1421 std::string PredName;
1424 CmpPredicateOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1426 : OperandPredicateMatcher(OPM_CmpPredicate, InsnVarID, OpIdx), PredName(P) {}
1428 bool isIdentical(const PredicateMatcher &B) const override {
1429 return OperandPredicateMatcher::isIdentical(B) &&
1430 PredName == cast<CmpPredicateOperandMatcher>(&B)->PredName;
1433 static bool classof(const PredicateMatcher *P) {
1434 return P->getKind() == OPM_CmpPredicate;
1437 void emitPredicateOpcodes(MatchTable &Table,
1438 RuleMatcher &Rule) const override {
1439 Table << MatchTable::Opcode("GIM_CheckCmpPredicate")
1440 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1441 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1442 << MatchTable::Comment("Predicate")
1443 << MatchTable::NamedValue("CmpInst", PredName)
1444 << MatchTable::LineBreak;
1448 /// Generates code to check that an operand is an intrinsic ID.
1449 class IntrinsicIDOperandMatcher : public OperandPredicateMatcher {
1451 const CodeGenIntrinsic *II;
1454 IntrinsicIDOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1455 const CodeGenIntrinsic *II)
1456 : OperandPredicateMatcher(OPM_IntrinsicID, InsnVarID, OpIdx), II(II) {}
1458 bool isIdentical(const PredicateMatcher &B) const override {
1459 return OperandPredicateMatcher::isIdentical(B) &&
1460 II == cast<IntrinsicIDOperandMatcher>(&B)->II;
1463 static bool classof(const PredicateMatcher *P) {
1464 return P->getKind() == OPM_IntrinsicID;
1467 void emitPredicateOpcodes(MatchTable &Table,
1468 RuleMatcher &Rule) const override {
1469 Table << MatchTable::Opcode("GIM_CheckIntrinsicID")
1470 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1471 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1472 << MatchTable::NamedValue("Intrinsic::" + II->EnumName)
1473 << MatchTable::LineBreak;
1477 /// Generates code to check that a set of predicates match for a particular
1479 class OperandMatcher : public PredicateListMatcher<OperandPredicateMatcher> {
1481 InstructionMatcher &Insn;
1483 std::string SymbolicName;
1485 /// The index of the first temporary variable allocated to this operand. The
1486 /// number of allocated temporaries can be found with
1487 /// countRendererFns().
1488 unsigned AllocatedTemporariesBaseID;
1491 OperandMatcher(InstructionMatcher &Insn, unsigned OpIdx,
1492 const std::string &SymbolicName,
1493 unsigned AllocatedTemporariesBaseID)
1494 : Insn(Insn), OpIdx(OpIdx), SymbolicName(SymbolicName),
1495 AllocatedTemporariesBaseID(AllocatedTemporariesBaseID) {}
1497 bool hasSymbolicName() const { return !SymbolicName.empty(); }
1498 const StringRef getSymbolicName() const { return SymbolicName; }
1499 void setSymbolicName(StringRef Name) {
1500 assert(SymbolicName.empty() && "Operand already has a symbolic name");
1501 SymbolicName = Name;
1504 /// Construct a new operand predicate and add it to the matcher.
1505 template <class Kind, class... Args>
1506 Optional<Kind *> addPredicate(Args &&... args) {
1507 if (isSameAsAnotherOperand())
1509 Predicates.emplace_back(std::make_unique<Kind>(
1510 getInsnVarID(), getOpIdx(), std::forward<Args>(args)...));
1511 return static_cast<Kind *>(Predicates.back().get());
1514 unsigned getOpIdx() const { return OpIdx; }
1515 unsigned getInsnVarID() const;
1517 std::string getOperandExpr(unsigned InsnVarID) const {
1518 return "State.MIs[" + llvm::to_string(InsnVarID) + "]->getOperand(" +
1519 llvm::to_string(OpIdx) + ")";
1522 InstructionMatcher &getInstructionMatcher() const { return Insn; }
1524 Error addTypeCheckPredicate(const TypeSetByHwMode &VTy,
1525 bool OperandIsAPointer);
1527 /// Emit MatchTable opcodes that test whether the instruction named in
1528 /// InsnVarID matches all the predicates and all the operands.
1529 void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) {
1531 std::string Comment;
1532 raw_string_ostream CommentOS(Comment);
1533 CommentOS << "MIs[" << getInsnVarID() << "] ";
1534 if (SymbolicName.empty())
1535 CommentOS << "Operand " << OpIdx;
1537 CommentOS << SymbolicName;
1538 Table << MatchTable::Comment(CommentOS.str()) << MatchTable::LineBreak;
1541 emitPredicateListOpcodes(Table, Rule);
1544 /// Compare the priority of this object and B.
1546 /// Returns true if this object is more important than B.
1547 bool isHigherPriorityThan(OperandMatcher &B) {
1548 // Operand matchers involving more predicates have higher priority.
1549 if (predicates_size() > B.predicates_size())
1551 if (predicates_size() < B.predicates_size())
1554 // This assumes that predicates are added in a consistent order.
1555 for (auto &&Predicate : zip(predicates(), B.predicates())) {
1556 if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate)))
1558 if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate)))
1565 /// Report the maximum number of temporary operands needed by the operand
1567 unsigned countRendererFns() {
1568 return std::accumulate(
1569 predicates().begin(), predicates().end(), 0,
1571 const std::unique_ptr<OperandPredicateMatcher> &Predicate) {
1572 return A + Predicate->countRendererFns();
1576 unsigned getAllocatedTemporariesBaseID() const {
1577 return AllocatedTemporariesBaseID;
1580 bool isSameAsAnotherOperand() {
1581 for (const auto &Predicate : predicates())
1582 if (isa<SameOperandMatcher>(Predicate))
1588 Error OperandMatcher::addTypeCheckPredicate(const TypeSetByHwMode &VTy,
1589 bool OperandIsAPointer) {
1590 if (!VTy.isMachineValueType())
1591 return failedImport("unsupported typeset");
1593 if (VTy.getMachineValueType() == MVT::iPTR && OperandIsAPointer) {
1594 addPredicate<PointerToAnyOperandMatcher>(0);
1595 return Error::success();
1598 auto OpTyOrNone = MVTToLLT(VTy.getMachineValueType().SimpleTy);
1600 return failedImport("unsupported type");
1602 if (OperandIsAPointer)
1603 addPredicate<PointerToAnyOperandMatcher>(OpTyOrNone->get().getSizeInBits());
1604 else if (VTy.isPointer())
1605 addPredicate<LLTOperandMatcher>(LLT::pointer(VTy.getPtrAddrSpace(),
1606 OpTyOrNone->get().getSizeInBits()));
1608 addPredicate<LLTOperandMatcher>(*OpTyOrNone);
1609 return Error::success();
1612 unsigned ComplexPatternOperandMatcher::getAllocatedTemporariesBaseID() const {
1613 return Operand.getAllocatedTemporariesBaseID();
1616 /// Generates code to check a predicate on an instruction.
1618 /// Typical predicates include:
1619 /// * The opcode of the instruction is a particular value.
1620 /// * The nsw/nuw flag is/isn't set.
1621 class InstructionPredicateMatcher : public PredicateMatcher {
1623 InstructionPredicateMatcher(PredicateKind Kind, unsigned InsnVarID)
1624 : PredicateMatcher(Kind, InsnVarID) {}
1625 virtual ~InstructionPredicateMatcher() {}
1627 /// Compare the priority of this object and B.
1629 /// Returns true if this object is more important than B.
1631 isHigherPriorityThan(const InstructionPredicateMatcher &B) const {
1632 return Kind < B.Kind;
1638 PredicateListMatcher<PredicateMatcher>::getNoPredicateComment() const {
1639 return "No instruction predicates";
1642 /// Generates code to check the opcode of an instruction.
1643 class InstructionOpcodeMatcher : public InstructionPredicateMatcher {
1645 const CodeGenInstruction *I;
1647 static DenseMap<const CodeGenInstruction *, unsigned> OpcodeValues;
1650 static void initOpcodeValuesMap(const CodeGenTarget &Target) {
1651 OpcodeValues.clear();
1653 unsigned OpcodeValue = 0;
1654 for (const CodeGenInstruction *I : Target.getInstructionsByEnumValue())
1655 OpcodeValues[I] = OpcodeValue++;
1658 InstructionOpcodeMatcher(unsigned InsnVarID, const CodeGenInstruction *I)
1659 : InstructionPredicateMatcher(IPM_Opcode, InsnVarID), I(I) {}
1661 static bool classof(const PredicateMatcher *P) {
1662 return P->getKind() == IPM_Opcode;
1665 bool isIdentical(const PredicateMatcher &B) const override {
1666 return InstructionPredicateMatcher::isIdentical(B) &&
1667 I == cast<InstructionOpcodeMatcher>(&B)->I;
1669 MatchTableRecord getValue() const override {
1670 const auto VI = OpcodeValues.find(I);
1671 if (VI != OpcodeValues.end())
1672 return MatchTable::NamedValue(I->Namespace, I->TheDef->getName(),
1674 return MatchTable::NamedValue(I->Namespace, I->TheDef->getName());
1676 bool hasValue() const override { return OpcodeValues.count(I); }
1678 void emitPredicateOpcodes(MatchTable &Table,
1679 RuleMatcher &Rule) const override {
1680 Table << MatchTable::Opcode("GIM_CheckOpcode") << MatchTable::Comment("MI")
1681 << MatchTable::IntValue(InsnVarID) << getValue()
1682 << MatchTable::LineBreak;
1685 /// Compare the priority of this object and B.
1687 /// Returns true if this object is more important than B.
1689 isHigherPriorityThan(const InstructionPredicateMatcher &B) const override {
1690 if (InstructionPredicateMatcher::isHigherPriorityThan(B))
1692 if (B.InstructionPredicateMatcher::isHigherPriorityThan(*this))
1695 // Prioritize opcodes for cosmetic reasons in the generated source. Although
1696 // this is cosmetic at the moment, we may want to drive a similar ordering
1697 // using instruction frequency information to improve compile time.
1698 if (const InstructionOpcodeMatcher *BO =
1699 dyn_cast<InstructionOpcodeMatcher>(&B))
1700 return I->TheDef->getName() < BO->I->TheDef->getName();
1705 bool isConstantInstruction() const {
1706 return I->TheDef->getName() == "G_CONSTANT";
1709 StringRef getOpcode() const { return I->TheDef->getName(); }
1710 unsigned getNumOperands() const { return I->Operands.size(); }
1712 StringRef getOperandType(unsigned OpIdx) const {
1713 return I->Operands[OpIdx].OperandType;
1717 DenseMap<const CodeGenInstruction *, unsigned>
1718 InstructionOpcodeMatcher::OpcodeValues;
1720 class InstructionNumOperandsMatcher final : public InstructionPredicateMatcher {
1721 unsigned NumOperands = 0;
1724 InstructionNumOperandsMatcher(unsigned InsnVarID, unsigned NumOperands)
1725 : InstructionPredicateMatcher(IPM_NumOperands, InsnVarID),
1726 NumOperands(NumOperands) {}
1728 static bool classof(const PredicateMatcher *P) {
1729 return P->getKind() == IPM_NumOperands;
1732 bool isIdentical(const PredicateMatcher &B) const override {
1733 return InstructionPredicateMatcher::isIdentical(B) &&
1734 NumOperands == cast<InstructionNumOperandsMatcher>(&B)->NumOperands;
1737 void emitPredicateOpcodes(MatchTable &Table,
1738 RuleMatcher &Rule) const override {
1739 Table << MatchTable::Opcode("GIM_CheckNumOperands")
1740 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1741 << MatchTable::Comment("Expected")
1742 << MatchTable::IntValue(NumOperands) << MatchTable::LineBreak;
1746 /// Generates code to check that this instruction is a constant whose value
1747 /// meets an immediate predicate.
1749 /// Immediates are slightly odd since they are typically used like an operand
1750 /// but are represented as an operator internally. We typically write simm8:$src
1751 /// in a tablegen pattern, but this is just syntactic sugar for
1752 /// (imm:i32)<<P:Predicate_simm8>>:$imm which more directly describes the nodes
1753 /// that will be matched and the predicate (which is attached to the imm
1754 /// operator) that will be tested. In SelectionDAG this describes a
1755 /// ConstantSDNode whose internal value will be tested using the simm8 predicate.
1757 /// The corresponding GlobalISel representation is %1 = G_CONSTANT iN Value. In
1758 /// this representation, the immediate could be tested with an
1759 /// InstructionMatcher, InstructionOpcodeMatcher, OperandMatcher, and a
1760 /// OperandPredicateMatcher-subclass to check the Value meets the predicate but
1761 /// there are two implementation issues with producing that matcher
1762 /// configuration from the SelectionDAG pattern:
1763 /// * ImmLeaf is a PatFrag whose root is an InstructionMatcher. This means that
1764 /// were we to sink the immediate predicate to the operand we would have to
1765 /// have two partial implementations of PatFrag support, one for immediates
1766 /// and one for non-immediates.
1767 /// * At the point we handle the predicate, the OperandMatcher hasn't been
1768 /// created yet. If we were to sink the predicate to the OperandMatcher we
1769 /// would also have to complicate (or duplicate) the code that descends and
1770 /// creates matchers for the subtree.
1771 /// Overall, it's simpler to handle it in the place it was found.
1772 class InstructionImmPredicateMatcher : public InstructionPredicateMatcher {
1774 TreePredicateFn Predicate;
1777 InstructionImmPredicateMatcher(unsigned InsnVarID,
1778 const TreePredicateFn &Predicate)
1779 : InstructionPredicateMatcher(IPM_ImmPredicate, InsnVarID),
1780 Predicate(Predicate) {}
1782 bool isIdentical(const PredicateMatcher &B) const override {
1783 return InstructionPredicateMatcher::isIdentical(B) &&
1784 Predicate.getOrigPatFragRecord() ==
1785 cast<InstructionImmPredicateMatcher>(&B)
1786 ->Predicate.getOrigPatFragRecord();
1789 static bool classof(const PredicateMatcher *P) {
1790 return P->getKind() == IPM_ImmPredicate;
1793 void emitPredicateOpcodes(MatchTable &Table,
1794 RuleMatcher &Rule) const override {
1795 Table << MatchTable::Opcode(getMatchOpcodeForPredicate(Predicate))
1796 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1797 << MatchTable::Comment("Predicate")
1798 << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
1799 << MatchTable::LineBreak;
1803 /// Generates code to check that a memory instruction has a atomic ordering
1804 /// MachineMemoryOperand.
1805 class AtomicOrderingMMOPredicateMatcher : public InstructionPredicateMatcher {
1815 AOComparator Comparator;
1818 AtomicOrderingMMOPredicateMatcher(unsigned InsnVarID, StringRef Order,
1819 AOComparator Comparator = AO_Exactly)
1820 : InstructionPredicateMatcher(IPM_AtomicOrderingMMO, InsnVarID),
1821 Order(Order), Comparator(Comparator) {}
1823 static bool classof(const PredicateMatcher *P) {
1824 return P->getKind() == IPM_AtomicOrderingMMO;
1827 bool isIdentical(const PredicateMatcher &B) const override {
1828 if (!InstructionPredicateMatcher::isIdentical(B))
1830 const auto &R = *cast<AtomicOrderingMMOPredicateMatcher>(&B);
1831 return Order == R.Order && Comparator == R.Comparator;
1834 void emitPredicateOpcodes(MatchTable &Table,
1835 RuleMatcher &Rule) const override {
1836 StringRef Opcode = "GIM_CheckAtomicOrdering";
1838 if (Comparator == AO_OrStronger)
1839 Opcode = "GIM_CheckAtomicOrderingOrStrongerThan";
1840 if (Comparator == AO_WeakerThan)
1841 Opcode = "GIM_CheckAtomicOrderingWeakerThan";
1843 Table << MatchTable::Opcode(Opcode) << MatchTable::Comment("MI")
1844 << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Order")
1845 << MatchTable::NamedValue(("(int64_t)AtomicOrdering::" + Order).str())
1846 << MatchTable::LineBreak;
1850 /// Generates code to check that the size of an MMO is exactly N bytes.
1851 class MemorySizePredicateMatcher : public InstructionPredicateMatcher {
1857 MemorySizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, unsigned Size)
1858 : InstructionPredicateMatcher(IPM_MemoryLLTSize, InsnVarID),
1859 MMOIdx(MMOIdx), Size(Size) {}
1861 static bool classof(const PredicateMatcher *P) {
1862 return P->getKind() == IPM_MemoryLLTSize;
1864 bool isIdentical(const PredicateMatcher &B) const override {
1865 return InstructionPredicateMatcher::isIdentical(B) &&
1866 MMOIdx == cast<MemorySizePredicateMatcher>(&B)->MMOIdx &&
1867 Size == cast<MemorySizePredicateMatcher>(&B)->Size;
1870 void emitPredicateOpcodes(MatchTable &Table,
1871 RuleMatcher &Rule) const override {
1872 Table << MatchTable::Opcode("GIM_CheckMemorySizeEqualTo")
1873 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1874 << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
1875 << MatchTable::Comment("Size") << MatchTable::IntValue(Size)
1876 << MatchTable::LineBreak;
1880 class MemoryAddressSpacePredicateMatcher : public InstructionPredicateMatcher {
1883 SmallVector<unsigned, 4> AddrSpaces;
1886 MemoryAddressSpacePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
1887 ArrayRef<unsigned> AddrSpaces)
1888 : InstructionPredicateMatcher(IPM_MemoryAddressSpace, InsnVarID),
1889 MMOIdx(MMOIdx), AddrSpaces(AddrSpaces.begin(), AddrSpaces.end()) {}
1891 static bool classof(const PredicateMatcher *P) {
1892 return P->getKind() == IPM_MemoryAddressSpace;
1894 bool isIdentical(const PredicateMatcher &B) const override {
1895 if (!InstructionPredicateMatcher::isIdentical(B))
1897 auto *Other = cast<MemoryAddressSpacePredicateMatcher>(&B);
1898 return MMOIdx == Other->MMOIdx && AddrSpaces == Other->AddrSpaces;
1901 void emitPredicateOpcodes(MatchTable &Table,
1902 RuleMatcher &Rule) const override {
1903 Table << MatchTable::Opcode("GIM_CheckMemoryAddressSpace")
1904 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1905 << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
1906 // Encode number of address spaces to expect.
1907 << MatchTable::Comment("NumAddrSpace")
1908 << MatchTable::IntValue(AddrSpaces.size());
1909 for (unsigned AS : AddrSpaces)
1910 Table << MatchTable::Comment("AddrSpace") << MatchTable::IntValue(AS);
1912 Table << MatchTable::LineBreak;
1916 class MemoryAlignmentPredicateMatcher : public InstructionPredicateMatcher {
1922 MemoryAlignmentPredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
1924 : InstructionPredicateMatcher(IPM_MemoryAlignment, InsnVarID),
1925 MMOIdx(MMOIdx), MinAlign(MinAlign) {
1926 assert(MinAlign > 0);
1929 static bool classof(const PredicateMatcher *P) {
1930 return P->getKind() == IPM_MemoryAlignment;
1933 bool isIdentical(const PredicateMatcher &B) const override {
1934 if (!InstructionPredicateMatcher::isIdentical(B))
1936 auto *Other = cast<MemoryAlignmentPredicateMatcher>(&B);
1937 return MMOIdx == Other->MMOIdx && MinAlign == Other->MinAlign;
1940 void emitPredicateOpcodes(MatchTable &Table,
1941 RuleMatcher &Rule) const override {
1942 Table << MatchTable::Opcode("GIM_CheckMemoryAlignment")
1943 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1944 << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
1945 << MatchTable::Comment("MinAlign") << MatchTable::IntValue(MinAlign)
1946 << MatchTable::LineBreak;
1950 /// Generates code to check that the size of an MMO is less-than, equal-to, or
1951 /// greater than a given LLT.
1952 class MemoryVsLLTSizePredicateMatcher : public InstructionPredicateMatcher {
1962 RelationKind Relation;
1966 MemoryVsLLTSizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
1967 enum RelationKind Relation,
1969 : InstructionPredicateMatcher(IPM_MemoryVsLLTSize, InsnVarID),
1970 MMOIdx(MMOIdx), Relation(Relation), OpIdx(OpIdx) {}
1972 static bool classof(const PredicateMatcher *P) {
1973 return P->getKind() == IPM_MemoryVsLLTSize;
1975 bool isIdentical(const PredicateMatcher &B) const override {
1976 return InstructionPredicateMatcher::isIdentical(B) &&
1977 MMOIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->MMOIdx &&
1978 Relation == cast<MemoryVsLLTSizePredicateMatcher>(&B)->Relation &&
1979 OpIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->OpIdx;
1982 void emitPredicateOpcodes(MatchTable &Table,
1983 RuleMatcher &Rule) const override {
1984 Table << MatchTable::Opcode(Relation == EqualTo
1985 ? "GIM_CheckMemorySizeEqualToLLT"
1986 : Relation == GreaterThan
1987 ? "GIM_CheckMemorySizeGreaterThanLLT"
1988 : "GIM_CheckMemorySizeLessThanLLT")
1989 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1990 << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
1991 << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx)
1992 << MatchTable::LineBreak;
1996 /// Generates code to check an arbitrary C++ instruction predicate.
1997 class GenericInstructionPredicateMatcher : public InstructionPredicateMatcher {
1999 TreePredicateFn Predicate;
2002 GenericInstructionPredicateMatcher(unsigned InsnVarID,
2003 TreePredicateFn Predicate)
2004 : InstructionPredicateMatcher(IPM_GenericPredicate, InsnVarID),
2005 Predicate(Predicate) {}
2007 static bool classof(const InstructionPredicateMatcher *P) {
2008 return P->getKind() == IPM_GenericPredicate;
2010 bool isIdentical(const PredicateMatcher &B) const override {
2011 return InstructionPredicateMatcher::isIdentical(B) &&
2013 static_cast<const GenericInstructionPredicateMatcher &>(B)
2016 void emitPredicateOpcodes(MatchTable &Table,
2017 RuleMatcher &Rule) const override {
2018 Table << MatchTable::Opcode("GIM_CheckCxxInsnPredicate")
2019 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
2020 << MatchTable::Comment("FnId")
2021 << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
2022 << MatchTable::LineBreak;
2026 /// Generates code to check that a set of predicates and operands match for a
2027 /// particular instruction.
2029 /// Typical predicates include:
2030 /// * Has a specific opcode.
2031 /// * Has an nsw/nuw flag or doesn't.
2032 class InstructionMatcher final : public PredicateListMatcher<PredicateMatcher> {
2034 typedef std::vector<std::unique_ptr<OperandMatcher>> OperandVec;
2038 /// The operands to match. All rendered operands must be present even if the
2039 /// condition is always true.
2040 OperandVec Operands;
2041 bool NumOperandsCheck = true;
2043 std::string SymbolicName;
2046 /// PhysRegInputs - List list has an entry for each explicitly specified
2047 /// physreg input to the pattern. The first elt is the Register node, the
2048 /// second is the recorded slot number the input pattern match saved it in.
2049 SmallVector<std::pair<Record *, unsigned>, 2> PhysRegInputs;
2052 InstructionMatcher(RuleMatcher &Rule, StringRef SymbolicName)
2053 : Rule(Rule), SymbolicName(SymbolicName) {
2054 // We create a new instruction matcher.
2055 // Get a new ID for that instruction.
2056 InsnVarID = Rule.implicitlyDefineInsnVar(*this);
2059 /// Construct a new instruction predicate and add it to the matcher.
2060 template <class Kind, class... Args>
2061 Optional<Kind *> addPredicate(Args &&... args) {
2062 Predicates.emplace_back(
2063 std::make_unique<Kind>(getInsnVarID(), std::forward<Args>(args)...));
2064 return static_cast<Kind *>(Predicates.back().get());
2067 RuleMatcher &getRuleMatcher() const { return Rule; }
2069 unsigned getInsnVarID() const { return InsnVarID; }
2071 /// Add an operand to the matcher.
2072 OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName,
2073 unsigned AllocatedTemporariesBaseID) {
2074 Operands.emplace_back(new OperandMatcher(*this, OpIdx, SymbolicName,
2075 AllocatedTemporariesBaseID));
2076 if (!SymbolicName.empty())
2077 Rule.defineOperand(SymbolicName, *Operands.back());
2079 return *Operands.back();
2082 OperandMatcher &getOperand(unsigned OpIdx) {
2083 auto I = std::find_if(Operands.begin(), Operands.end(),
2084 [&OpIdx](const std::unique_ptr<OperandMatcher> &X) {
2085 return X->getOpIdx() == OpIdx;
2087 if (I != Operands.end())
2089 llvm_unreachable("Failed to lookup operand");
2092 OperandMatcher &addPhysRegInput(Record *Reg, unsigned OpIdx,
2093 unsigned TempOpIdx) {
2094 assert(SymbolicName.empty());
2095 OperandMatcher *OM = new OperandMatcher(*this, OpIdx, "", TempOpIdx);
2096 Operands.emplace_back(OM);
2097 Rule.definePhysRegOperand(Reg, *OM);
2098 PhysRegInputs.emplace_back(Reg, OpIdx);
2102 ArrayRef<std::pair<Record *, unsigned>> getPhysRegInputs() const {
2103 return PhysRegInputs;
2106 StringRef getSymbolicName() const { return SymbolicName; }
2107 unsigned getNumOperands() const { return Operands.size(); }
2108 OperandVec::iterator operands_begin() { return Operands.begin(); }
2109 OperandVec::iterator operands_end() { return Operands.end(); }
2110 iterator_range<OperandVec::iterator> operands() {
2111 return make_range(operands_begin(), operands_end());
2113 OperandVec::const_iterator operands_begin() const { return Operands.begin(); }
2114 OperandVec::const_iterator operands_end() const { return Operands.end(); }
2115 iterator_range<OperandVec::const_iterator> operands() const {
2116 return make_range(operands_begin(), operands_end());
2118 bool operands_empty() const { return Operands.empty(); }
2120 void pop_front() { Operands.erase(Operands.begin()); }
2124 /// Emit MatchTable opcodes that test whether the instruction named in
2125 /// InsnVarName matches all the predicates and all the operands.
2126 void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) {
2127 if (NumOperandsCheck)
2128 InstructionNumOperandsMatcher(InsnVarID, getNumOperands())
2129 .emitPredicateOpcodes(Table, Rule);
2131 emitPredicateListOpcodes(Table, Rule);
2133 for (const auto &Operand : Operands)
2134 Operand->emitPredicateOpcodes(Table, Rule);
2137 /// Compare the priority of this object and B.
2139 /// Returns true if this object is more important than B.
2140 bool isHigherPriorityThan(InstructionMatcher &B) {
2141 // Instruction matchers involving more operands have higher priority.
2142 if (Operands.size() > B.Operands.size())
2144 if (Operands.size() < B.Operands.size())
2147 for (auto &&P : zip(predicates(), B.predicates())) {
2148 auto L = static_cast<InstructionPredicateMatcher *>(std::get<0>(P).get());
2149 auto R = static_cast<InstructionPredicateMatcher *>(std::get<1>(P).get());
2150 if (L->isHigherPriorityThan(*R))
2152 if (R->isHigherPriorityThan(*L))
2156 for (const auto &Operand : zip(Operands, B.Operands)) {
2157 if (std::get<0>(Operand)->isHigherPriorityThan(*std::get<1>(Operand)))
2159 if (std::get<1>(Operand)->isHigherPriorityThan(*std::get<0>(Operand)))
2166 /// Report the maximum number of temporary operands needed by the instruction
2168 unsigned countRendererFns() {
2169 return std::accumulate(
2170 predicates().begin(), predicates().end(), 0,
2172 const std::unique_ptr<PredicateMatcher> &Predicate) {
2173 return A + Predicate->countRendererFns();
2176 Operands.begin(), Operands.end(), 0,
2177 [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) {
2178 return A + Operand->countRendererFns();
2182 InstructionOpcodeMatcher &getOpcodeMatcher() {
2183 for (auto &P : predicates())
2184 if (auto *OpMatcher = dyn_cast<InstructionOpcodeMatcher>(P.get()))
2186 llvm_unreachable("Didn't find an opcode matcher");
2189 bool isConstantInstruction() {
2190 return getOpcodeMatcher().isConstantInstruction();
2193 StringRef getOpcode() { return getOpcodeMatcher().getOpcode(); }
2196 StringRef RuleMatcher::getOpcode() const {
2197 return Matchers.front()->getOpcode();
2200 unsigned RuleMatcher::getNumOperands() const {
2201 return Matchers.front()->getNumOperands();
2204 LLTCodeGen RuleMatcher::getFirstConditionAsRootType() {
2205 InstructionMatcher &InsnMatcher = *Matchers.front();
2206 if (!InsnMatcher.predicates_empty())
2207 if (const auto *TM =
2208 dyn_cast<LLTOperandMatcher>(&**InsnMatcher.predicates_begin()))
2209 if (TM->getInsnVarID() == 0 && TM->getOpIdx() == 0)
2214 /// Generates code to check that the operand is a register defined by an
2215 /// instruction that matches the given instruction matcher.
2217 /// For example, the pattern:
2218 /// (set $dst, (G_MUL (G_ADD $src1, $src2), $src3))
2219 /// would use an InstructionOperandMatcher for operand 1 of the G_MUL to match
2221 /// (G_ADD $src1, $src2)
2223 class InstructionOperandMatcher : public OperandPredicateMatcher {
2225 std::unique_ptr<InstructionMatcher> InsnMatcher;
2228 InstructionOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
2229 RuleMatcher &Rule, StringRef SymbolicName)
2230 : OperandPredicateMatcher(OPM_Instruction, InsnVarID, OpIdx),
2231 InsnMatcher(new InstructionMatcher(Rule, SymbolicName)) {}
2233 static bool classof(const PredicateMatcher *P) {
2234 return P->getKind() == OPM_Instruction;
2237 InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; }
2239 void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const {
2240 const unsigned NewInsnVarID = InsnMatcher->getInsnVarID();
2241 Table << MatchTable::Opcode("GIM_RecordInsn")
2242 << MatchTable::Comment("DefineMI")
2243 << MatchTable::IntValue(NewInsnVarID) << MatchTable::Comment("MI")
2244 << MatchTable::IntValue(getInsnVarID())
2245 << MatchTable::Comment("OpIdx") << MatchTable::IntValue(getOpIdx())
2246 << MatchTable::Comment("MIs[" + llvm::to_string(NewInsnVarID) + "]")
2247 << MatchTable::LineBreak;
2250 void emitPredicateOpcodes(MatchTable &Table,
2251 RuleMatcher &Rule) const override {
2252 emitCaptureOpcodes(Table, Rule);
2253 InsnMatcher->emitPredicateOpcodes(Table, Rule);
2256 bool isHigherPriorityThan(const OperandPredicateMatcher &B) const override {
2257 if (OperandPredicateMatcher::isHigherPriorityThan(B))
2259 if (B.OperandPredicateMatcher::isHigherPriorityThan(*this))
2262 if (const InstructionOperandMatcher *BP =
2263 dyn_cast<InstructionOperandMatcher>(&B))
2264 if (InsnMatcher->isHigherPriorityThan(*BP->InsnMatcher))
2270 void InstructionMatcher::optimize() {
2271 SmallVector<std::unique_ptr<PredicateMatcher>, 8> Stash;
2272 const auto &OpcMatcher = getOpcodeMatcher();
2274 Stash.push_back(predicates_pop_front());
2275 if (Stash.back().get() == &OpcMatcher) {
2276 if (NumOperandsCheck && OpcMatcher.getNumOperands() < getNumOperands())
2278 new InstructionNumOperandsMatcher(InsnVarID, getNumOperands()));
2279 NumOperandsCheck = false;
2281 for (auto &OM : Operands)
2282 for (auto &OP : OM->predicates())
2283 if (isa<IntrinsicIDOperandMatcher>(OP)) {
2284 Stash.push_back(std::move(OP));
2285 OM->eraseNullPredicates();
2290 if (InsnVarID > 0) {
2291 assert(!Operands.empty() && "Nested instruction is expected to def a vreg");
2292 for (auto &OP : Operands[0]->predicates())
2294 Operands[0]->eraseNullPredicates();
2296 for (auto &OM : Operands) {
2297 for (auto &OP : OM->predicates())
2298 if (isa<LLTOperandMatcher>(OP))
2299 Stash.push_back(std::move(OP));
2300 OM->eraseNullPredicates();
2302 while (!Stash.empty())
2303 prependPredicate(Stash.pop_back_val());
2306 //===- Actions ------------------------------------------------------------===//
2307 class OperandRenderer {
2311 OR_CopyOrAddZeroReg,
2314 OR_CopyConstantAsImm,
2315 OR_CopyFConstantAsFPImm,
2328 OperandRenderer(RendererKind Kind) : Kind(Kind) {}
2329 virtual ~OperandRenderer() {}
2331 RendererKind getKind() const { return Kind; }
2333 virtual void emitRenderOpcodes(MatchTable &Table,
2334 RuleMatcher &Rule) const = 0;
2337 /// A CopyRenderer emits code to copy a single operand from an existing
2338 /// instruction to the one being built.
2339 class CopyRenderer : public OperandRenderer {
2342 /// The name of the operand.
2343 const StringRef SymbolicName;
2346 CopyRenderer(unsigned NewInsnID, StringRef SymbolicName)
2347 : OperandRenderer(OR_Copy), NewInsnID(NewInsnID),
2348 SymbolicName(SymbolicName) {
2349 assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
2352 static bool classof(const OperandRenderer *R) {
2353 return R->getKind() == OR_Copy;
2356 const StringRef getSymbolicName() const { return SymbolicName; }
2358 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2359 const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2360 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2361 Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
2362 << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID")
2363 << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2364 << MatchTable::IntValue(Operand.getOpIdx())
2365 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2369 /// A CopyRenderer emits code to copy a virtual register to a specific physical
2371 class CopyPhysRegRenderer : public OperandRenderer {
2377 CopyPhysRegRenderer(unsigned NewInsnID, Record *Reg)
2378 : OperandRenderer(OR_CopyPhysReg), NewInsnID(NewInsnID),
2383 static bool classof(const OperandRenderer *R) {
2384 return R->getKind() == OR_CopyPhysReg;
2387 Record *getPhysReg() const { return PhysReg; }
2389 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2390 const OperandMatcher &Operand = Rule.getPhysRegOperandMatcher(PhysReg);
2391 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2392 Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
2393 << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID")
2394 << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2395 << MatchTable::IntValue(Operand.getOpIdx())
2396 << MatchTable::Comment(PhysReg->getName())
2397 << MatchTable::LineBreak;
2401 /// A CopyOrAddZeroRegRenderer emits code to copy a single operand from an
2402 /// existing instruction to the one being built. If the operand turns out to be
2403 /// a 'G_CONSTANT 0' then it replaces the operand with a zero register.
2404 class CopyOrAddZeroRegRenderer : public OperandRenderer {
2407 /// The name of the operand.
2408 const StringRef SymbolicName;
2409 const Record *ZeroRegisterDef;
2412 CopyOrAddZeroRegRenderer(unsigned NewInsnID,
2413 StringRef SymbolicName, Record *ZeroRegisterDef)
2414 : OperandRenderer(OR_CopyOrAddZeroReg), NewInsnID(NewInsnID),
2415 SymbolicName(SymbolicName), ZeroRegisterDef(ZeroRegisterDef) {
2416 assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
2419 static bool classof(const OperandRenderer *R) {
2420 return R->getKind() == OR_CopyOrAddZeroReg;
2423 const StringRef getSymbolicName() const { return SymbolicName; }
2425 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2426 const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2427 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2428 Table << MatchTable::Opcode("GIR_CopyOrAddZeroReg")
2429 << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2430 << MatchTable::Comment("OldInsnID")
2431 << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2432 << MatchTable::IntValue(Operand.getOpIdx())
2433 << MatchTable::NamedValue(
2434 (ZeroRegisterDef->getValue("Namespace")
2435 ? ZeroRegisterDef->getValueAsString("Namespace")
2437 ZeroRegisterDef->getName())
2438 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2442 /// A CopyConstantAsImmRenderer emits code to render a G_CONSTANT instruction to
2443 /// an extended immediate operand.
2444 class CopyConstantAsImmRenderer : public OperandRenderer {
2447 /// The name of the operand.
2448 const std::string SymbolicName;
2452 CopyConstantAsImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
2453 : OperandRenderer(OR_CopyConstantAsImm), NewInsnID(NewInsnID),
2454 SymbolicName(SymbolicName), Signed(true) {}
2456 static bool classof(const OperandRenderer *R) {
2457 return R->getKind() == OR_CopyConstantAsImm;
2460 const StringRef getSymbolicName() const { return SymbolicName; }
2462 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2463 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2464 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2465 Table << MatchTable::Opcode(Signed ? "GIR_CopyConstantAsSImm"
2466 : "GIR_CopyConstantAsUImm")
2467 << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2468 << MatchTable::Comment("OldInsnID")
2469 << MatchTable::IntValue(OldInsnVarID)
2470 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2474 /// A CopyFConstantAsFPImmRenderer emits code to render a G_FCONSTANT
2475 /// instruction to an extended immediate operand.
2476 class CopyFConstantAsFPImmRenderer : public OperandRenderer {
2479 /// The name of the operand.
2480 const std::string SymbolicName;
2483 CopyFConstantAsFPImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
2484 : OperandRenderer(OR_CopyFConstantAsFPImm), NewInsnID(NewInsnID),
2485 SymbolicName(SymbolicName) {}
2487 static bool classof(const OperandRenderer *R) {
2488 return R->getKind() == OR_CopyFConstantAsFPImm;
2491 const StringRef getSymbolicName() const { return SymbolicName; }
2493 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2494 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2495 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2496 Table << MatchTable::Opcode("GIR_CopyFConstantAsFPImm")
2497 << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2498 << MatchTable::Comment("OldInsnID")
2499 << MatchTable::IntValue(OldInsnVarID)
2500 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2504 /// A CopySubRegRenderer emits code to copy a single register operand from an
2505 /// existing instruction to the one being built and indicate that only a
2506 /// subregister should be copied.
2507 class CopySubRegRenderer : public OperandRenderer {
2510 /// The name of the operand.
2511 const StringRef SymbolicName;
2512 /// The subregister to extract.
2513 const CodeGenSubRegIndex *SubReg;
2516 CopySubRegRenderer(unsigned NewInsnID, StringRef SymbolicName,
2517 const CodeGenSubRegIndex *SubReg)
2518 : OperandRenderer(OR_CopySubReg), NewInsnID(NewInsnID),
2519 SymbolicName(SymbolicName), SubReg(SubReg) {}
2521 static bool classof(const OperandRenderer *R) {
2522 return R->getKind() == OR_CopySubReg;
2525 const StringRef getSymbolicName() const { return SymbolicName; }
2527 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2528 const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2529 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2530 Table << MatchTable::Opcode("GIR_CopySubReg")
2531 << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2532 << MatchTable::Comment("OldInsnID")
2533 << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2534 << MatchTable::IntValue(Operand.getOpIdx())
2535 << MatchTable::Comment("SubRegIdx")
2536 << MatchTable::IntValue(SubReg->EnumValue)
2537 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2541 /// Adds a specific physical register to the instruction being built.
2542 /// This is typically useful for WZR/XZR on AArch64.
2543 class AddRegisterRenderer : public OperandRenderer {
2546 const Record *RegisterDef;
2550 AddRegisterRenderer(unsigned InsnID, const Record *RegisterDef,
2552 : OperandRenderer(OR_Register), InsnID(InsnID), RegisterDef(RegisterDef),
2555 static bool classof(const OperandRenderer *R) {
2556 return R->getKind() == OR_Register;
2559 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2560 Table << MatchTable::Opcode("GIR_AddRegister")
2561 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2562 << MatchTable::NamedValue(
2563 (RegisterDef->getValue("Namespace")
2564 ? RegisterDef->getValueAsString("Namespace")
2566 RegisterDef->getName())
2567 << MatchTable::Comment("AddRegisterRegFlags");
2569 // TODO: This is encoded as a 64-bit element, but only 16 or 32-bits are
2570 // really needed for a physical register reference. We can pack the
2571 // register and flags in a single field.
2573 Table << MatchTable::NamedValue("RegState::Define");
2575 Table << MatchTable::IntValue(0);
2576 Table << MatchTable::LineBreak;
2580 /// Adds a specific temporary virtual register to the instruction being built.
2581 /// This is used to chain instructions together when emitting multiple
2583 class TempRegRenderer : public OperandRenderer {
2590 TempRegRenderer(unsigned InsnID, unsigned TempRegID, bool IsDef = false)
2591 : OperandRenderer(OR_Register), InsnID(InsnID), TempRegID(TempRegID),
2594 static bool classof(const OperandRenderer *R) {
2595 return R->getKind() == OR_TempRegister;
2598 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2599 Table << MatchTable::Opcode("GIR_AddTempRegister")
2600 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2601 << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID)
2602 << MatchTable::Comment("TempRegFlags");
2604 Table << MatchTable::NamedValue("RegState::Define");
2606 Table << MatchTable::IntValue(0);
2607 Table << MatchTable::LineBreak;
2611 /// Adds a specific immediate to the instruction being built.
2612 class ImmRenderer : public OperandRenderer {
2618 ImmRenderer(unsigned InsnID, int64_t Imm)
2619 : OperandRenderer(OR_Imm), InsnID(InsnID), Imm(Imm) {}
2621 static bool classof(const OperandRenderer *R) {
2622 return R->getKind() == OR_Imm;
2625 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2626 Table << MatchTable::Opcode("GIR_AddImm") << MatchTable::Comment("InsnID")
2627 << MatchTable::IntValue(InsnID) << MatchTable::Comment("Imm")
2628 << MatchTable::IntValue(Imm) << MatchTable::LineBreak;
2632 /// Adds an enum value for a subreg index to the instruction being built.
2633 class SubRegIndexRenderer : public OperandRenderer {
2636 const CodeGenSubRegIndex *SubRegIdx;
2639 SubRegIndexRenderer(unsigned InsnID, const CodeGenSubRegIndex *SRI)
2640 : OperandRenderer(OR_SubRegIndex), InsnID(InsnID), SubRegIdx(SRI) {}
2642 static bool classof(const OperandRenderer *R) {
2643 return R->getKind() == OR_SubRegIndex;
2646 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2647 Table << MatchTable::Opcode("GIR_AddImm") << MatchTable::Comment("InsnID")
2648 << MatchTable::IntValue(InsnID) << MatchTable::Comment("SubRegIndex")
2649 << MatchTable::IntValue(SubRegIdx->EnumValue)
2650 << MatchTable::LineBreak;
2654 /// Adds operands by calling a renderer function supplied by the ComplexPattern
2655 /// matcher function.
2656 class RenderComplexPatternOperand : public OperandRenderer {
2659 const Record &TheDef;
2660 /// The name of the operand.
2661 const StringRef SymbolicName;
2662 /// The renderer number. This must be unique within a rule since it's used to
2663 /// identify a temporary variable to hold the renderer function.
2664 unsigned RendererID;
2665 /// When provided, this is the suboperand of the ComplexPattern operand to
2666 /// render. Otherwise all the suboperands will be rendered.
2667 Optional<unsigned> SubOperand;
2669 unsigned getNumOperands() const {
2670 return TheDef.getValueAsDag("Operands")->getNumArgs();
2674 RenderComplexPatternOperand(unsigned InsnID, const Record &TheDef,
2675 StringRef SymbolicName, unsigned RendererID,
2676 Optional<unsigned> SubOperand = None)
2677 : OperandRenderer(OR_ComplexPattern), InsnID(InsnID), TheDef(TheDef),
2678 SymbolicName(SymbolicName), RendererID(RendererID),
2679 SubOperand(SubOperand) {}
2681 static bool classof(const OperandRenderer *R) {
2682 return R->getKind() == OR_ComplexPattern;
2685 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2686 Table << MatchTable::Opcode(SubOperand.hasValue() ? "GIR_ComplexSubOperandRenderer"
2687 : "GIR_ComplexRenderer")
2688 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2689 << MatchTable::Comment("RendererID")
2690 << MatchTable::IntValue(RendererID);
2691 if (SubOperand.hasValue())
2692 Table << MatchTable::Comment("SubOperand")
2693 << MatchTable::IntValue(SubOperand.getValue());
2694 Table << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2698 class CustomRenderer : public OperandRenderer {
2701 const Record &Renderer;
2702 /// The name of the operand.
2703 const std::string SymbolicName;
2706 CustomRenderer(unsigned InsnID, const Record &Renderer,
2707 StringRef SymbolicName)
2708 : OperandRenderer(OR_Custom), InsnID(InsnID), Renderer(Renderer),
2709 SymbolicName(SymbolicName) {}
2711 static bool classof(const OperandRenderer *R) {
2712 return R->getKind() == OR_Custom;
2715 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2716 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2717 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2718 Table << MatchTable::Opcode("GIR_CustomRenderer")
2719 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2720 << MatchTable::Comment("OldInsnID")
2721 << MatchTable::IntValue(OldInsnVarID)
2722 << MatchTable::Comment("Renderer")
2723 << MatchTable::NamedValue(
2724 "GICR_" + Renderer.getValueAsString("RendererFn").str())
2725 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2729 /// An action taken when all Matcher predicates succeeded for a parent rule.
2731 /// Typical actions include:
2732 /// * Changing the opcode of an instruction.
2733 /// * Adding an operand to an instruction.
2736 virtual ~MatchAction() {}
2738 /// Emit the MatchTable opcodes to implement the action.
2739 virtual void emitActionOpcodes(MatchTable &Table,
2740 RuleMatcher &Rule) const = 0;
2743 /// Generates a comment describing the matched rule being acted upon.
2744 class DebugCommentAction : public MatchAction {
2749 DebugCommentAction(StringRef S) : S(S) {}
2751 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2752 Table << MatchTable::Comment(S) << MatchTable::LineBreak;
2756 /// Generates code to build an instruction or mutate an existing instruction
2757 /// into the desired instruction when this is possible.
2758 class BuildMIAction : public MatchAction {
2761 const CodeGenInstruction *I;
2762 InstructionMatcher *Matched;
2763 std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers;
2765 /// True if the instruction can be built solely by mutating the opcode.
2766 bool canMutate(RuleMatcher &Rule, const InstructionMatcher *Insn) const {
2770 if (OperandRenderers.size() != Insn->getNumOperands())
2773 for (const auto &Renderer : enumerate(OperandRenderers)) {
2774 if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) {
2775 const OperandMatcher &OM = Rule.getOperandMatcher(Copy->getSymbolicName());
2776 if (Insn != &OM.getInstructionMatcher() ||
2777 OM.getOpIdx() != Renderer.index())
2787 BuildMIAction(unsigned InsnID, const CodeGenInstruction *I)
2788 : InsnID(InsnID), I(I), Matched(nullptr) {}
2790 unsigned getInsnID() const { return InsnID; }
2791 const CodeGenInstruction *getCGI() const { return I; }
2793 void chooseInsnToMutate(RuleMatcher &Rule) {
2794 for (auto *MutateCandidate : Rule.mutatable_insns()) {
2795 if (canMutate(Rule, MutateCandidate)) {
2796 // Take the first one we're offered that we're able to mutate.
2797 Rule.reserveInsnMatcherForMutation(MutateCandidate);
2798 Matched = MutateCandidate;
2804 template <class Kind, class... Args>
2805 Kind &addRenderer(Args&&... args) {
2806 OperandRenderers.emplace_back(
2807 std::make_unique<Kind>(InsnID, std::forward<Args>(args)...));
2808 return *static_cast<Kind *>(OperandRenderers.back().get());
2811 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2813 assert(canMutate(Rule, Matched) &&
2814 "Arranged to mutate an insn that isn't mutatable");
2816 unsigned RecycleInsnID = Rule.getInsnVarID(*Matched);
2817 Table << MatchTable::Opcode("GIR_MutateOpcode")
2818 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2819 << MatchTable::Comment("RecycleInsnID")
2820 << MatchTable::IntValue(RecycleInsnID)
2821 << MatchTable::Comment("Opcode")
2822 << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
2823 << MatchTable::LineBreak;
2825 if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) {
2826 for (auto Def : I->ImplicitDefs) {
2827 auto Namespace = Def->getValue("Namespace")
2828 ? Def->getValueAsString("Namespace")
2830 Table << MatchTable::Opcode("GIR_AddImplicitDef")
2831 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2832 << MatchTable::NamedValue(Namespace, Def->getName())
2833 << MatchTable::LineBreak;
2835 for (auto Use : I->ImplicitUses) {
2836 auto Namespace = Use->getValue("Namespace")
2837 ? Use->getValueAsString("Namespace")
2839 Table << MatchTable::Opcode("GIR_AddImplicitUse")
2840 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2841 << MatchTable::NamedValue(Namespace, Use->getName())
2842 << MatchTable::LineBreak;
2848 // TODO: Simple permutation looks like it could be almost as common as
2849 // mutation due to commutative operations.
2851 Table << MatchTable::Opcode("GIR_BuildMI") << MatchTable::Comment("InsnID")
2852 << MatchTable::IntValue(InsnID) << MatchTable::Comment("Opcode")
2853 << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
2854 << MatchTable::LineBreak;
2855 for (const auto &Renderer : OperandRenderers)
2856 Renderer->emitRenderOpcodes(Table, Rule);
2858 if (I->mayLoad || I->mayStore) {
2859 Table << MatchTable::Opcode("GIR_MergeMemOperands")
2860 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2861 << MatchTable::Comment("MergeInsnID's");
2862 // Emit the ID's for all the instructions that are matched by this rule.
2863 // TODO: Limit this to matched instructions that mayLoad/mayStore or have
2864 // some other means of having a memoperand. Also limit this to
2865 // emitted instructions that expect to have a memoperand too. For
2866 // example, (G_SEXT (G_LOAD x)) that results in separate load and
2867 // sign-extend instructions shouldn't put the memoperand on the
2868 // sign-extend since it has no effect there.
2869 std::vector<unsigned> MergeInsnIDs;
2870 for (const auto &IDMatcherPair : Rule.defined_insn_vars())
2871 MergeInsnIDs.push_back(IDMatcherPair.second);
2872 llvm::sort(MergeInsnIDs);
2873 for (const auto &MergeInsnID : MergeInsnIDs)
2874 Table << MatchTable::IntValue(MergeInsnID);
2875 Table << MatchTable::NamedValue("GIU_MergeMemOperands_EndOfList")
2876 << MatchTable::LineBreak;
2879 // FIXME: This is a hack but it's sufficient for ISel. We'll need to do
2880 // better for combines. Particularly when there are multiple match
2883 Table << MatchTable::Opcode("GIR_EraseFromParent")
2884 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2885 << MatchTable::LineBreak;
2889 /// Generates code to constrain the operands of an output instruction to the
2890 /// register classes specified by the definition of that instruction.
2891 class ConstrainOperandsToDefinitionAction : public MatchAction {
2895 ConstrainOperandsToDefinitionAction(unsigned InsnID) : InsnID(InsnID) {}
2897 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2898 Table << MatchTable::Opcode("GIR_ConstrainSelectedInstOperands")
2899 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2900 << MatchTable::LineBreak;
2904 /// Generates code to constrain the specified operand of an output instruction
2905 /// to the specified register class.
2906 class ConstrainOperandToRegClassAction : public MatchAction {
2909 const CodeGenRegisterClass &RC;
2912 ConstrainOperandToRegClassAction(unsigned InsnID, unsigned OpIdx,
2913 const CodeGenRegisterClass &RC)
2914 : InsnID(InsnID), OpIdx(OpIdx), RC(RC) {}
2916 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2917 Table << MatchTable::Opcode("GIR_ConstrainOperandRC")
2918 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2919 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
2920 << MatchTable::Comment("RC " + RC.getName())
2921 << MatchTable::IntValue(RC.EnumValue) << MatchTable::LineBreak;
2925 /// Generates code to create a temporary register which can be used to chain
2926 /// instructions together.
2927 class MakeTempRegisterAction : public MatchAction {
2933 MakeTempRegisterAction(const LLTCodeGen &Ty, unsigned TempRegID)
2934 : Ty(Ty), TempRegID(TempRegID) {
2935 KnownTypes.insert(Ty);
2938 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2939 Table << MatchTable::Opcode("GIR_MakeTempReg")
2940 << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID)
2941 << MatchTable::Comment("TypeID")
2942 << MatchTable::NamedValue(Ty.getCxxEnumValue())
2943 << MatchTable::LineBreak;
2947 InstructionMatcher &RuleMatcher::addInstructionMatcher(StringRef SymbolicName) {
2948 Matchers.emplace_back(new InstructionMatcher(*this, SymbolicName));
2949 MutatableInsns.insert(Matchers.back().get());
2950 return *Matchers.back();
2953 void RuleMatcher::addRequiredFeature(Record *Feature) {
2954 RequiredFeatures.push_back(Feature);
2957 const std::vector<Record *> &RuleMatcher::getRequiredFeatures() const {
2958 return RequiredFeatures;
2961 // Emplaces an action of the specified Kind at the end of the action list.
2963 // Returns a reference to the newly created action.
2965 // Like std::vector::emplace_back(), may invalidate all iterators if the new
2966 // size exceeds the capacity. Otherwise, only invalidates the past-the-end
2968 template <class Kind, class... Args>
2969 Kind &RuleMatcher::addAction(Args &&... args) {
2970 Actions.emplace_back(std::make_unique<Kind>(std::forward<Args>(args)...));
2971 return *static_cast<Kind *>(Actions.back().get());
2974 // Emplaces an action of the specified Kind before the given insertion point.
2976 // Returns an iterator pointing at the newly created instruction.
2978 // Like std::vector::insert(), may invalidate all iterators if the new size
2979 // exceeds the capacity. Otherwise, only invalidates the iterators from the
2980 // insertion point onwards.
2981 template <class Kind, class... Args>
2982 action_iterator RuleMatcher::insertAction(action_iterator InsertPt,
2984 return Actions.emplace(InsertPt,
2985 std::make_unique<Kind>(std::forward<Args>(args)...));
2988 unsigned RuleMatcher::implicitlyDefineInsnVar(InstructionMatcher &Matcher) {
2989 unsigned NewInsnVarID = NextInsnVarID++;
2990 InsnVariableIDs[&Matcher] = NewInsnVarID;
2991 return NewInsnVarID;
2994 unsigned RuleMatcher::getInsnVarID(InstructionMatcher &InsnMatcher) const {
2995 const auto &I = InsnVariableIDs.find(&InsnMatcher);
2996 if (I != InsnVariableIDs.end())
2998 llvm_unreachable("Matched Insn was not captured in a local variable");
3001 void RuleMatcher::defineOperand(StringRef SymbolicName, OperandMatcher &OM) {
3002 if (DefinedOperands.find(SymbolicName) == DefinedOperands.end()) {
3003 DefinedOperands[SymbolicName] = &OM;
3007 // If the operand is already defined, then we must ensure both references in
3008 // the matcher have the exact same node.
3009 OM.addPredicate<SameOperandMatcher>(OM.getSymbolicName());
3012 void RuleMatcher::definePhysRegOperand(Record *Reg, OperandMatcher &OM) {
3013 if (PhysRegOperands.find(Reg) == PhysRegOperands.end()) {
3014 PhysRegOperands[Reg] = &OM;
3019 InstructionMatcher &
3020 RuleMatcher::getInstructionMatcher(StringRef SymbolicName) const {
3021 for (const auto &I : InsnVariableIDs)
3022 if (I.first->getSymbolicName() == SymbolicName)
3025 ("Failed to lookup instruction " + SymbolicName).str().c_str());
3028 const OperandMatcher &
3029 RuleMatcher::getPhysRegOperandMatcher(Record *Reg) const {
3030 const auto &I = PhysRegOperands.find(Reg);
3032 if (I == PhysRegOperands.end()) {
3033 PrintFatalError(SrcLoc, "Register " + Reg->getName() +
3034 " was not declared in matcher");
3040 const OperandMatcher &
3041 RuleMatcher::getOperandMatcher(StringRef Name) const {
3042 const auto &I = DefinedOperands.find(Name);
3044 if (I == DefinedOperands.end())
3045 PrintFatalError(SrcLoc, "Operand " + Name + " was not declared in matcher");
3050 void RuleMatcher::emit(MatchTable &Table) {
3051 if (Matchers.empty())
3052 llvm_unreachable("Unexpected empty matcher!");
3054 // The representation supports rules that require multiple roots such as:
3056 // %elt0(s32) = G_LOAD %ptr
3057 // %1(p0) = G_ADD %ptr, 4
3058 // %elt1(s32) = G_LOAD p0 %1
3059 // which could be usefully folded into:
3061 // %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr
3062 // on some targets but we don't need to make use of that yet.
3063 assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
3065 unsigned LabelID = Table.allocateLabelID();
3066 Table << MatchTable::Opcode("GIM_Try", +1)
3067 << MatchTable::Comment("On fail goto")
3068 << MatchTable::JumpTarget(LabelID)
3069 << MatchTable::Comment(("Rule ID " + Twine(RuleID) + " //").str())
3070 << MatchTable::LineBreak;
3072 if (!RequiredFeatures.empty()) {
3073 Table << MatchTable::Opcode("GIM_CheckFeatures")
3074 << MatchTable::NamedValue(getNameForFeatureBitset(RequiredFeatures))
3075 << MatchTable::LineBreak;
3078 Matchers.front()->emitPredicateOpcodes(Table, *this);
3080 // We must also check if it's safe to fold the matched instructions.
3081 if (InsnVariableIDs.size() >= 2) {
3082 // Invert the map to create stable ordering (by var names)
3083 SmallVector<unsigned, 2> InsnIDs;
3084 for (const auto &Pair : InsnVariableIDs) {
3085 // Skip the root node since it isn't moving anywhere. Everything else is
3086 // sinking to meet it.
3087 if (Pair.first == Matchers.front().get())
3090 InsnIDs.push_back(Pair.second);
3092 llvm::sort(InsnIDs);
3094 for (const auto &InsnID : InsnIDs) {
3095 // Reject the difficult cases until we have a more accurate check.
3096 Table << MatchTable::Opcode("GIM_CheckIsSafeToFold")
3097 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
3098 << MatchTable::LineBreak;
3100 // FIXME: Emit checks to determine it's _actually_ safe to fold and/or
3101 // account for unsafe cases.
3106 // MI0--> %2 = ... %0
3107 // It's not safe to erase MI1. We currently handle this by not
3108 // erasing %0 (even when it's dead).
3111 // MI1--> %0 = load volatile @a
3112 // %1 = load volatile @a
3113 // MI0--> %2 = ... %0
3114 // It's not safe to sink %0's def past %1. We currently handle
3115 // this by rejecting all loads.
3118 // MI1--> %0 = load @a
3120 // MI0--> %2 = ... %0
3121 // It's not safe to sink %0's def past %1. We currently handle
3122 // this by rejecting all loads.
3125 // G_CONDBR %cond, @BB1
3127 // MI1--> %0 = load @a
3130 // MI0--> %2 = ... %0
3131 // It's not always safe to sink %0 across control flow. In this
3132 // case it may introduce a memory fault. We currentl handle this
3133 // by rejecting all loads.
3137 for (const auto &PM : EpilogueMatchers)
3138 PM->emitPredicateOpcodes(Table, *this);
3140 for (const auto &MA : Actions)
3141 MA->emitActionOpcodes(Table, *this);
3143 if (Table.isWithCoverage())
3144 Table << MatchTable::Opcode("GIR_Coverage") << MatchTable::IntValue(RuleID)
3145 << MatchTable::LineBreak;
3147 Table << MatchTable::Comment(("GIR_Coverage, " + Twine(RuleID) + ",").str())
3148 << MatchTable::LineBreak;
3150 Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak
3151 << MatchTable::Label(LabelID);
3152 ++NumPatternEmitted;
3155 bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
3156 // Rules involving more match roots have higher priority.
3157 if (Matchers.size() > B.Matchers.size())
3159 if (Matchers.size() < B.Matchers.size())
3162 for (const auto &Matcher : zip(Matchers, B.Matchers)) {
3163 if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher)))
3165 if (std::get<1>(Matcher)->isHigherPriorityThan(*std::get<0>(Matcher)))
3172 unsigned RuleMatcher::countRendererFns() const {
3173 return std::accumulate(
3174 Matchers.begin(), Matchers.end(), 0,
3175 [](unsigned A, const std::unique_ptr<InstructionMatcher> &Matcher) {
3176 return A + Matcher->countRendererFns();
3180 bool OperandPredicateMatcher::isHigherPriorityThan(
3181 const OperandPredicateMatcher &B) const {
3182 // Generally speaking, an instruction is more important than an Int or a
3183 // LiteralInt because it can cover more nodes but theres an exception to
3184 // this. G_CONSTANT's are less important than either of those two because they
3185 // are more permissive.
3187 const InstructionOperandMatcher *AOM =
3188 dyn_cast<InstructionOperandMatcher>(this);
3189 const InstructionOperandMatcher *BOM =
3190 dyn_cast<InstructionOperandMatcher>(&B);
3191 bool AIsConstantInsn = AOM && AOM->getInsnMatcher().isConstantInstruction();
3192 bool BIsConstantInsn = BOM && BOM->getInsnMatcher().isConstantInstruction();
3195 // The relative priorities between a G_CONSTANT and any other instruction
3196 // don't actually matter but this code is needed to ensure a strict weak
3197 // ordering. This is particularly important on Windows where the rules will
3198 // be incorrectly sorted without it.
3199 if (AIsConstantInsn != BIsConstantInsn)
3200 return AIsConstantInsn < BIsConstantInsn;
3204 if (AOM && AIsConstantInsn && (B.Kind == OPM_Int || B.Kind == OPM_LiteralInt))
3206 if (BOM && BIsConstantInsn && (Kind == OPM_Int || Kind == OPM_LiteralInt))
3209 return Kind < B.Kind;
3212 void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
3213 RuleMatcher &Rule) const {
3214 const OperandMatcher &OtherOM = Rule.getOperandMatcher(MatchingName);
3215 unsigned OtherInsnVarID = Rule.getInsnVarID(OtherOM.getInstructionMatcher());
3216 assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getInsnVarID());
3218 Table << MatchTable::Opcode("GIM_CheckIsSameOperand")
3219 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
3220 << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx)
3221 << MatchTable::Comment("OtherMI")
3222 << MatchTable::IntValue(OtherInsnVarID)
3223 << MatchTable::Comment("OtherOpIdx")
3224 << MatchTable::IntValue(OtherOM.getOpIdx())
3225 << MatchTable::LineBreak;
3228 //===- GlobalISelEmitter class --------------------------------------------===//
3230 class GlobalISelEmitter {
3232 explicit GlobalISelEmitter(RecordKeeper &RK);
3233 void run(raw_ostream &OS);
3236 const RecordKeeper &RK;
3237 const CodeGenDAGPatterns CGP;
3238 const CodeGenTarget &Target;
3239 CodeGenRegBank CGRegs;
3241 /// Keep track of the equivalence between SDNodes and Instruction by mapping
3242 /// SDNodes to the GINodeEquiv mapping. We need to map to the GINodeEquiv to
3243 /// check for attributes on the relation such as CheckMMOIsNonAtomic.
3244 /// This is defined using 'GINodeEquiv' in the target description.
3245 DenseMap<Record *, Record *> NodeEquivs;
3247 /// Keep track of the equivalence between ComplexPattern's and
3248 /// GIComplexOperandMatcher. Map entries are specified by subclassing
3249 /// GIComplexPatternEquiv.
3250 DenseMap<const Record *, const Record *> ComplexPatternEquivs;
3252 /// Keep track of the equivalence between SDNodeXForm's and
3253 /// GICustomOperandRenderer. Map entries are specified by subclassing
3254 /// GISDNodeXFormEquiv.
3255 DenseMap<const Record *, const Record *> SDNodeXFormEquivs;
3257 /// Keep track of Scores of PatternsToMatch similar to how the DAG does.
3258 /// This adds compatibility for RuleMatchers to use this for ordering rules.
3259 DenseMap<uint64_t, int> RuleMatcherScores;
3261 // Map of predicates to their subtarget features.
3262 SubtargetFeatureInfoMap SubtargetFeatures;
3264 // Rule coverage information.
3265 Optional<CodeGenCoverage> RuleCoverage;
3267 void gatherOpcodeValues();
3268 void gatherTypeIDValues();
3269 void gatherNodeEquivs();
3271 Record *findNodeEquiv(Record *N) const;
3272 const CodeGenInstruction *getEquivNode(Record &Equiv,
3273 const TreePatternNode *N) const;
3275 Error importRulePredicates(RuleMatcher &M, ArrayRef<Predicate> Predicates);
3276 Expected<InstructionMatcher &>
3277 createAndImportSelDAGMatcher(RuleMatcher &Rule,
3278 InstructionMatcher &InsnMatcher,
3279 const TreePatternNode *Src, unsigned &TempOpIdx);
3280 Error importComplexPatternOperandMatcher(OperandMatcher &OM, Record *R,
3281 unsigned &TempOpIdx) const;
3282 Error importChildMatcher(RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
3283 const TreePatternNode *SrcChild,
3284 bool OperandIsAPointer, unsigned OpIdx,
3285 unsigned &TempOpIdx);
3287 Expected<BuildMIAction &> createAndImportInstructionRenderer(
3288 RuleMatcher &M, InstructionMatcher &InsnMatcher,
3289 const TreePatternNode *Src, const TreePatternNode *Dst);
3290 Expected<action_iterator> createAndImportSubInstructionRenderer(
3291 action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst,
3293 Expected<action_iterator>
3294 createInstructionRenderer(action_iterator InsertPt, RuleMatcher &M,
3295 const TreePatternNode *Dst);
3296 void importExplicitDefRenderers(BuildMIAction &DstMIBuilder);
3298 Expected<action_iterator>
3299 importExplicitUseRenderers(action_iterator InsertPt, RuleMatcher &M,
3300 BuildMIAction &DstMIBuilder,
3301 const llvm::TreePatternNode *Dst);
3302 Expected<action_iterator>
3303 importExplicitUseRenderer(action_iterator InsertPt, RuleMatcher &Rule,
3304 BuildMIAction &DstMIBuilder,
3305 TreePatternNode *DstChild);
3306 Error importDefaultOperandRenderers(action_iterator InsertPt, RuleMatcher &M,
3307 BuildMIAction &DstMIBuilder,
3308 DagInit *DefaultOps) const;
3310 importImplicitDefRenderers(BuildMIAction &DstMIBuilder,
3311 const std::vector<Record *> &ImplicitDefs) const;
3313 void emitCxxPredicateFns(raw_ostream &OS, StringRef CodeFieldName,
3314 StringRef TypeIdentifier, StringRef ArgType,
3315 StringRef ArgName, StringRef AdditionalDeclarations,
3316 std::function<bool(const Record *R)> Filter);
3317 void emitImmPredicateFns(raw_ostream &OS, StringRef TypeIdentifier,
3319 std::function<bool(const Record *R)> Filter);
3320 void emitMIPredicateFns(raw_ostream &OS);
3322 /// Analyze pattern \p P, returning a matcher for it if possible.
3323 /// Otherwise, return an Error explaining why we don't support it.
3324 Expected<RuleMatcher> runOnPattern(const PatternToMatch &P);
3326 void declareSubtargetFeature(Record *Predicate);
3328 MatchTable buildMatchTable(MutableArrayRef<RuleMatcher> Rules, bool Optimize,
3331 /// Infer a CodeGenRegisterClass for the type of \p SuperRegNode. The returned
3332 /// CodeGenRegisterClass will support the CodeGenRegisterClass of
3333 /// \p SubRegNode, and the subregister index defined by \p SubRegIdxNode.
3334 /// If no register class is found, return None.
3335 Optional<const CodeGenRegisterClass *>
3336 inferSuperRegisterClassForNode(const TypeSetByHwMode &Ty,
3337 TreePatternNode *SuperRegNode,
3338 TreePatternNode *SubRegIdxNode);
3339 Optional<CodeGenSubRegIndex *>
3340 inferSubRegIndexForNode(TreePatternNode *SubRegIdxNode);
3342 /// Infer a CodeGenRegisterClass which suppoorts \p Ty and \p SubRegIdxNode.
3343 /// Return None if no such class exists.
3344 Optional<const CodeGenRegisterClass *>
3345 inferSuperRegisterClass(const TypeSetByHwMode &Ty,
3346 TreePatternNode *SubRegIdxNode);
3348 /// Return the CodeGenRegisterClass associated with \p Leaf if it has one.
3349 Optional<const CodeGenRegisterClass *>
3350 getRegClassFromLeaf(TreePatternNode *Leaf);
3352 /// Return a CodeGenRegisterClass for \p N if one can be found. Return None
3354 Optional<const CodeGenRegisterClass *>
3355 inferRegClassFromPattern(TreePatternNode *N);
3358 /// Takes a sequence of \p Rules and group them based on the predicates
3359 /// they share. \p MatcherStorage is used as a memory container
3360 /// for the group that are created as part of this process.
3362 /// What this optimization does looks like if GroupT = GroupMatcher:
3363 /// Output without optimization:
3370 /// # predicate A // <-- effectively this is going to be checked twice.
3371 /// // Once in R1 and once in R2.
3374 /// Output with optimization:
3377 /// # predicate A // <-- Check is now shared.
3383 template <class GroupT>
3384 static std::vector<Matcher *> optimizeRules(
3385 ArrayRef<Matcher *> Rules,
3386 std::vector<std::unique_ptr<Matcher>> &MatcherStorage);
3389 void GlobalISelEmitter::gatherOpcodeValues() {
3390 InstructionOpcodeMatcher::initOpcodeValuesMap(Target);
3393 void GlobalISelEmitter::gatherTypeIDValues() {
3394 LLTOperandMatcher::initTypeIDValuesMap();
3397 void GlobalISelEmitter::gatherNodeEquivs() {
3398 assert(NodeEquivs.empty());
3399 for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
3400 NodeEquivs[Equiv->getValueAsDef("Node")] = Equiv;
3402 assert(ComplexPatternEquivs.empty());
3403 for (Record *Equiv : RK.getAllDerivedDefinitions("GIComplexPatternEquiv")) {
3404 Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
3407 ComplexPatternEquivs[SelDAGEquiv] = Equiv;
3410 assert(SDNodeXFormEquivs.empty());
3411 for (Record *Equiv : RK.getAllDerivedDefinitions("GISDNodeXFormEquiv")) {
3412 Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
3415 SDNodeXFormEquivs[SelDAGEquiv] = Equiv;
3419 Record *GlobalISelEmitter::findNodeEquiv(Record *N) const {
3420 return NodeEquivs.lookup(N);
3423 const CodeGenInstruction *
3424 GlobalISelEmitter::getEquivNode(Record &Equiv, const TreePatternNode *N) const {
3425 if (N->getNumChildren() >= 1) {
3426 // setcc operation maps to two different G_* instructions based on the type.
3427 if (!Equiv.isValueUnset("IfFloatingPoint") &&
3428 MVT(N->getChild(0)->getSimpleType(0)).isFloatingPoint())
3429 return &Target.getInstruction(Equiv.getValueAsDef("IfFloatingPoint"));
3432 for (const TreePredicateCall &Call : N->getPredicateCalls()) {
3433 const TreePredicateFn &Predicate = Call.Fn;
3434 if (!Equiv.isValueUnset("IfSignExtend") && Predicate.isLoad() &&
3435 Predicate.isSignExtLoad())
3436 return &Target.getInstruction(Equiv.getValueAsDef("IfSignExtend"));
3437 if (!Equiv.isValueUnset("IfZeroExtend") && Predicate.isLoad() &&
3438 Predicate.isZeroExtLoad())
3439 return &Target.getInstruction(Equiv.getValueAsDef("IfZeroExtend"));
3442 return &Target.getInstruction(Equiv.getValueAsDef("I"));
3445 GlobalISelEmitter::GlobalISelEmitter(RecordKeeper &RK)
3446 : RK(RK), CGP(RK), Target(CGP.getTargetInfo()),
3447 CGRegs(RK, Target.getHwModes()) {}
3449 //===- Emitter ------------------------------------------------------------===//
3452 GlobalISelEmitter::importRulePredicates(RuleMatcher &M,
3453 ArrayRef<Predicate> Predicates) {
3454 for (const Predicate &P : Predicates) {
3455 if (!P.Def || P.getCondString().empty())
3457 declareSubtargetFeature(P.Def);
3458 M.addRequiredFeature(P.Def);
3461 return Error::success();
3464 Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher(
3465 RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
3466 const TreePatternNode *Src, unsigned &TempOpIdx) {
3467 Record *SrcGIEquivOrNull = nullptr;
3468 const CodeGenInstruction *SrcGIOrNull = nullptr;
3470 // Start with the defined operands (i.e., the results of the root operator).
3471 if (Src->getExtTypes().size() > 1)
3472 return failedImport("Src pattern has multiple results");
3474 if (Src->isLeaf()) {
3475 Init *SrcInit = Src->getLeafValue();
3476 if (isa<IntInit>(SrcInit)) {
3477 InsnMatcher.addPredicate<InstructionOpcodeMatcher>(
3478 &Target.getInstruction(RK.getDef("G_CONSTANT")));
3480 return failedImport(
3481 "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
3483 SrcGIEquivOrNull = findNodeEquiv(Src->getOperator());
3484 if (!SrcGIEquivOrNull)
3485 return failedImport("Pattern operator lacks an equivalent Instruction" +
3486 explainOperator(Src->getOperator()));
3487 SrcGIOrNull = getEquivNode(*SrcGIEquivOrNull, Src);
3489 // The operators look good: match the opcode
3490 InsnMatcher.addPredicate<InstructionOpcodeMatcher>(SrcGIOrNull);
3494 for (const TypeSetByHwMode &VTy : Src->getExtTypes()) {
3495 // Results don't have a name unless they are the root node. The caller will
3496 // set the name if appropriate.
3497 OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
3498 if (auto Error = OM.addTypeCheckPredicate(VTy, false /* OperandIsAPointer */))
3499 return failedImport(toString(std::move(Error)) +
3500 " for result of Src pattern operator");
3503 for (const TreePredicateCall &Call : Src->getPredicateCalls()) {
3504 const TreePredicateFn &Predicate = Call.Fn;
3505 if (Predicate.isAlwaysTrue())
3508 if (Predicate.isImmediatePattern()) {
3509 InsnMatcher.addPredicate<InstructionImmPredicateMatcher>(Predicate);
3513 // An address space check is needed in all contexts if there is one.
3514 if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
3515 if (const ListInit *AddrSpaces = Predicate.getAddressSpaces()) {
3516 SmallVector<unsigned, 4> ParsedAddrSpaces;
3518 for (Init *Val : AddrSpaces->getValues()) {
3519 IntInit *IntVal = dyn_cast<IntInit>(Val);
3521 return failedImport("Address space is not an integer");
3522 ParsedAddrSpaces.push_back(IntVal->getValue());
3525 if (!ParsedAddrSpaces.empty()) {
3526 InsnMatcher.addPredicate<MemoryAddressSpacePredicateMatcher>(
3527 0, ParsedAddrSpaces);
3531 int64_t MinAlign = Predicate.getMinAlignment();
3533 InsnMatcher.addPredicate<MemoryAlignmentPredicateMatcher>(0, MinAlign);
3536 // G_LOAD is used for both non-extending and any-extending loads.
3537 if (Predicate.isLoad() && Predicate.isNonExtLoad()) {
3538 InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3539 0, MemoryVsLLTSizePredicateMatcher::EqualTo, 0);
3542 if (Predicate.isLoad() && Predicate.isAnyExtLoad()) {
3543 InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3544 0, MemoryVsLLTSizePredicateMatcher::LessThan, 0);
3548 if (Predicate.isStore()) {
3549 if (Predicate.isTruncStore()) {
3550 // FIXME: If MemoryVT is set, we end up with 2 checks for the MMO size.
3551 InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3552 0, MemoryVsLLTSizePredicateMatcher::LessThan, 0);
3555 if (Predicate.isNonTruncStore()) {
3556 // We need to check the sizes match here otherwise we could incorrectly
3557 // match truncating stores with non-truncating ones.
3558 InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3559 0, MemoryVsLLTSizePredicateMatcher::EqualTo, 0);
3563 // No check required. We already did it by swapping the opcode.
3564 if (!SrcGIEquivOrNull->isValueUnset("IfSignExtend") &&
3565 Predicate.isSignExtLoad())
3568 // No check required. We already did it by swapping the opcode.
3569 if (!SrcGIEquivOrNull->isValueUnset("IfZeroExtend") &&
3570 Predicate.isZeroExtLoad())
3573 // No check required. G_STORE by itself is a non-extending store.
3574 if (Predicate.isNonTruncStore())
3577 if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
3578 if (Predicate.getMemoryVT() != nullptr) {
3579 Optional<LLTCodeGen> MemTyOrNone =
3580 MVTToLLT(getValueType(Predicate.getMemoryVT()));
3583 return failedImport("MemVT could not be converted to LLT");
3585 // MMO's work in bytes so we must take care of unusual types like i1
3586 // don't round down.
3587 unsigned MemSizeInBits =
3588 llvm::alignTo(MemTyOrNone->get().getSizeInBits(), 8);
3590 InsnMatcher.addPredicate<MemorySizePredicateMatcher>(
3591 0, MemSizeInBits / 8);
3596 if (Predicate.isLoad() || Predicate.isStore()) {
3597 // No check required. A G_LOAD/G_STORE is an unindexed load.
3598 if (Predicate.isUnindexed())
3602 if (Predicate.isAtomic()) {
3603 if (Predicate.isAtomicOrderingMonotonic()) {
3604 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3608 if (Predicate.isAtomicOrderingAcquire()) {
3609 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Acquire");
3612 if (Predicate.isAtomicOrderingRelease()) {
3613 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Release");
3616 if (Predicate.isAtomicOrderingAcquireRelease()) {
3617 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3621 if (Predicate.isAtomicOrderingSequentiallyConsistent()) {
3622 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3623 "SequentiallyConsistent");
3627 if (Predicate.isAtomicOrderingAcquireOrStronger()) {
3628 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3629 "Acquire", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
3632 if (Predicate.isAtomicOrderingWeakerThanAcquire()) {
3633 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3634 "Acquire", AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
3638 if (Predicate.isAtomicOrderingReleaseOrStronger()) {
3639 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3640 "Release", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
3643 if (Predicate.isAtomicOrderingWeakerThanRelease()) {
3644 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3645 "Release", AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
3650 if (Predicate.hasGISelPredicateCode()) {
3651 InsnMatcher.addPredicate<GenericInstructionPredicateMatcher>(Predicate);
3655 return failedImport("Src pattern child has predicate (" +
3656 explainPredicates(Src) + ")");
3658 if (SrcGIEquivOrNull && SrcGIEquivOrNull->getValueAsBit("CheckMMOIsNonAtomic"))
3659 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("NotAtomic");
3660 else if (SrcGIEquivOrNull && SrcGIEquivOrNull->getValueAsBit("CheckMMOIsAtomic")) {
3661 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3662 "Unordered", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
3665 if (Src->isLeaf()) {
3666 Init *SrcInit = Src->getLeafValue();
3667 if (IntInit *SrcIntInit = dyn_cast<IntInit>(SrcInit)) {
3668 OperandMatcher &OM =
3669 InsnMatcher.addOperand(OpIdx++, Src->getName(), TempOpIdx);
3670 OM.addPredicate<LiteralIntOperandMatcher>(SrcIntInit->getValue());
3672 return failedImport(
3673 "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
3675 assert(SrcGIOrNull &&
3676 "Expected to have already found an equivalent Instruction");
3677 if (SrcGIOrNull->TheDef->getName() == "G_CONSTANT" ||
3678 SrcGIOrNull->TheDef->getName() == "G_FCONSTANT") {
3679 // imm/fpimm still have operands but we don't need to do anything with it
3680 // here since we don't support ImmLeaf predicates yet. However, we still
3681 // need to note the hidden operand to get GIM_CheckNumOperands correct.
3682 InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
3686 // Special case because the operand order is changed from setcc. The
3687 // predicate operand needs to be swapped from the last operand to the first
3690 unsigned NumChildren = Src->getNumChildren();
3691 bool IsFCmp = SrcGIOrNull->TheDef->getName() == "G_FCMP";
3693 if (IsFCmp || SrcGIOrNull->TheDef->getName() == "G_ICMP") {
3694 TreePatternNode *SrcChild = Src->getChild(NumChildren - 1);
3695 if (SrcChild->isLeaf()) {
3696 DefInit *DI = dyn_cast<DefInit>(SrcChild->getLeafValue());
3697 Record *CCDef = DI ? DI->getDef() : nullptr;
3698 if (!CCDef || !CCDef->isSubClassOf("CondCode"))
3699 return failedImport("Unable to handle CondCode");
3701 OperandMatcher &OM =
3702 InsnMatcher.addOperand(OpIdx++, SrcChild->getName(), TempOpIdx);
3703 StringRef PredType = IsFCmp ? CCDef->getValueAsString("FCmpPredicate") :
3704 CCDef->getValueAsString("ICmpPredicate");
3706 if (!PredType.empty()) {
3707 OM.addPredicate<CmpPredicateOperandMatcher>(PredType);
3708 // Process the other 2 operands normally.
3714 // Match the used operands (i.e. the children of the operator).
3716 SrcGIOrNull->TheDef->getName() == "G_INTRINSIC" ||
3717 SrcGIOrNull->TheDef->getName() == "G_INTRINSIC_W_SIDE_EFFECTS";
3718 const CodeGenIntrinsic *II = Src->getIntrinsicInfo(CGP);
3719 if (IsIntrinsic && !II)
3720 return failedImport("Expected IntInit containing intrinsic ID)");
3722 for (unsigned i = 0; i != NumChildren; ++i) {
3723 TreePatternNode *SrcChild = Src->getChild(i);
3725 // SelectionDAG allows pointers to be represented with iN since it doesn't
3726 // distinguish between pointers and integers but they are different types in GlobalISel.
3727 // Coerce integers to pointers to address space 0 if the context indicates a pointer.
3728 bool OperandIsAPointer = SrcGIOrNull->isOperandAPointer(i);
3731 // For G_INTRINSIC/G_INTRINSIC_W_SIDE_EFFECTS, the operand immediately
3732 // following the defs is an intrinsic ID.
3734 OperandMatcher &OM =
3735 InsnMatcher.addOperand(OpIdx++, SrcChild->getName(), TempOpIdx);
3736 OM.addPredicate<IntrinsicIDOperandMatcher>(II);
3740 // We have to check intrinsics for llvm_anyptr_ty parameters.
3742 // Note that we have to look at the i-1th parameter, because we don't
3743 // have the intrinsic ID in the intrinsic's parameter list.
3744 OperandIsAPointer |= II->isParamAPointer(i - 1);
3748 importChildMatcher(Rule, InsnMatcher, SrcChild, OperandIsAPointer,
3749 OpIdx++, TempOpIdx))
3750 return std::move(Error);
3757 Error GlobalISelEmitter::importComplexPatternOperandMatcher(
3758 OperandMatcher &OM, Record *R, unsigned &TempOpIdx) const {
3759 const auto &ComplexPattern = ComplexPatternEquivs.find(R);
3760 if (ComplexPattern == ComplexPatternEquivs.end())
3761 return failedImport("SelectionDAG ComplexPattern (" + R->getName() +
3762 ") not mapped to GlobalISel");
3764 OM.addPredicate<ComplexPatternOperandMatcher>(OM, *ComplexPattern->second);
3766 return Error::success();
3769 // Get the name to use for a pattern operand. For an anonymous physical register
3770 // input, this should use the register name.
3771 static StringRef getSrcChildName(const TreePatternNode *SrcChild,
3773 StringRef SrcChildName = SrcChild->getName();
3774 if (SrcChildName.empty() && SrcChild->isLeaf()) {
3775 if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
3776 auto *ChildRec = ChildDefInit->getDef();
3777 if (ChildRec->isSubClassOf("Register")) {
3778 SrcChildName = ChildRec->getName();
3784 return SrcChildName;
3787 Error GlobalISelEmitter::importChildMatcher(RuleMatcher &Rule,
3788 InstructionMatcher &InsnMatcher,
3789 const TreePatternNode *SrcChild,
3790 bool OperandIsAPointer,
3792 unsigned &TempOpIdx) {
3794 Record *PhysReg = nullptr;
3795 StringRef SrcChildName = getSrcChildName(SrcChild, PhysReg);
3797 OperandMatcher &OM = PhysReg ?
3798 InsnMatcher.addPhysRegInput(PhysReg, OpIdx, TempOpIdx) :
3799 InsnMatcher.addOperand(OpIdx, SrcChildName, TempOpIdx);
3800 if (OM.isSameAsAnotherOperand())
3801 return Error::success();
3803 ArrayRef<TypeSetByHwMode> ChildTypes = SrcChild->getExtTypes();
3804 if (ChildTypes.size() != 1)
3805 return failedImport("Src pattern child has multiple results");
3807 // Check MBB's before the type check since they are not a known type.
3808 if (!SrcChild->isLeaf()) {
3809 if (SrcChild->getOperator()->isSubClassOf("SDNode")) {
3810 auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator());
3811 if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
3812 OM.addPredicate<MBBOperandMatcher>();
3813 return Error::success();
3815 if (SrcChild->getOperator()->getName() == "timm") {
3816 OM.addPredicate<ImmOperandMatcher>();
3817 return Error::success();
3823 OM.addTypeCheckPredicate(ChildTypes.front(), OperandIsAPointer))
3824 return failedImport(toString(std::move(Error)) + " for Src operand (" +
3825 to_string(*SrcChild) + ")");
3827 // Check for nested instructions.
3828 if (!SrcChild->isLeaf()) {
3829 if (SrcChild->getOperator()->isSubClassOf("ComplexPattern")) {
3830 // When a ComplexPattern is used as an operator, it should do the same
3831 // thing as when used as a leaf. However, the children of the operator
3832 // name the sub-operands that make up the complex operand and we must
3833 // prepare to reference them in the renderer too.
3834 unsigned RendererID = TempOpIdx;
3835 if (auto Error = importComplexPatternOperandMatcher(
3836 OM, SrcChild->getOperator(), TempOpIdx))
3839 for (unsigned i = 0, e = SrcChild->getNumChildren(); i != e; ++i) {
3840 auto *SubOperand = SrcChild->getChild(i);
3841 if (!SubOperand->getName().empty()) {
3842 if (auto Error = Rule.defineComplexSubOperand(SubOperand->getName(),
3843 SrcChild->getOperator(),
3849 return Error::success();
3852 auto MaybeInsnOperand = OM.addPredicate<InstructionOperandMatcher>(
3853 InsnMatcher.getRuleMatcher(), SrcChild->getName());
3854 if (!MaybeInsnOperand.hasValue()) {
3855 // This isn't strictly true. If the user were to provide exactly the same
3856 // matchers as the original operand then we could allow it. However, it's
3857 // simpler to not permit the redundant specification.
3858 return failedImport("Nested instruction cannot be the same as another operand");
3861 // Map the node to a gMIR instruction.
3862 InstructionOperandMatcher &InsnOperand = **MaybeInsnOperand;
3863 auto InsnMatcherOrError = createAndImportSelDAGMatcher(
3864 Rule, InsnOperand.getInsnMatcher(), SrcChild, TempOpIdx);
3865 if (auto Error = InsnMatcherOrError.takeError())
3868 return Error::success();
3871 if (SrcChild->hasAnyPredicate())
3872 return failedImport("Src pattern child has unsupported predicate");
3874 // Check for constant immediates.
3875 if (auto *ChildInt = dyn_cast<IntInit>(SrcChild->getLeafValue())) {
3876 OM.addPredicate<ConstantIntOperandMatcher>(ChildInt->getValue());
3877 return Error::success();
3880 // Check for def's like register classes or ComplexPattern's.
3881 if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
3882 auto *ChildRec = ChildDefInit->getDef();
3884 // Check for register classes.
3885 if (ChildRec->isSubClassOf("RegisterClass") ||
3886 ChildRec->isSubClassOf("RegisterOperand")) {
3887 OM.addPredicate<RegisterBankOperandMatcher>(
3888 Target.getRegisterClass(getInitValueAsRegClass(ChildDefInit)));
3889 return Error::success();
3892 if (ChildRec->isSubClassOf("Register")) {
3893 // This just be emitted as a copy to the specific register.
3894 ValueTypeByHwMode VT = ChildTypes.front().getValueTypeByHwMode();
3895 const CodeGenRegisterClass *RC
3896 = CGRegs.getMinimalPhysRegClass(ChildRec, &VT);
3898 return failedImport(
3899 "Could not determine physical register class of pattern source");
3902 OM.addPredicate<RegisterBankOperandMatcher>(*RC);
3903 return Error::success();
3906 // Check for ValueType.
3907 if (ChildRec->isSubClassOf("ValueType")) {
3908 // We already added a type check as standard practice so this doesn't need
3910 return Error::success();
3913 // Check for ComplexPattern's.
3914 if (ChildRec->isSubClassOf("ComplexPattern"))
3915 return importComplexPatternOperandMatcher(OM, ChildRec, TempOpIdx);
3917 if (ChildRec->isSubClassOf("ImmLeaf")) {
3918 return failedImport(
3919 "Src pattern child def is an unsupported tablegen class (ImmLeaf)");
3922 return failedImport(
3923 "Src pattern child def is an unsupported tablegen class");
3926 return failedImport("Src pattern child is an unsupported kind");
3929 Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderer(
3930 action_iterator InsertPt, RuleMatcher &Rule, BuildMIAction &DstMIBuilder,
3931 TreePatternNode *DstChild) {
3933 const auto &SubOperand = Rule.getComplexSubOperand(DstChild->getName());
3934 if (SubOperand.hasValue()) {
3935 DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
3936 *std::get<0>(*SubOperand), DstChild->getName(),
3937 std::get<1>(*SubOperand), std::get<2>(*SubOperand));
3941 if (!DstChild->isLeaf()) {
3943 if (DstChild->getOperator()->isSubClassOf("SDNodeXForm")) {
3944 auto Child = DstChild->getChild(0);
3945 auto I = SDNodeXFormEquivs.find(DstChild->getOperator());
3946 if (I != SDNodeXFormEquivs.end()) {
3947 DstMIBuilder.addRenderer<CustomRenderer>(*I->second, Child->getName());
3950 return failedImport("SDNodeXForm " + Child->getName() +
3951 " has no custom renderer");
3954 // We accept 'bb' here. It's an operator because BasicBlockSDNode isn't
3955 // inline, but in MI it's just another operand.
3956 if (DstChild->getOperator()->isSubClassOf("SDNode")) {
3957 auto &ChildSDNI = CGP.getSDNodeInfo(DstChild->getOperator());
3958 if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
3959 DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
3964 // Similarly, imm is an operator in TreePatternNode's view but must be
3965 // rendered as operands.
3966 // FIXME: The target should be able to choose sign-extended when appropriate
3968 if (DstChild->getOperator()->getName() == "timm") {
3969 DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
3971 } else if (DstChild->getOperator()->getName() == "imm") {
3972 DstMIBuilder.addRenderer<CopyConstantAsImmRenderer>(DstChild->getName());
3974 } else if (DstChild->getOperator()->getName() == "fpimm") {
3975 DstMIBuilder.addRenderer<CopyFConstantAsFPImmRenderer>(
3976 DstChild->getName());
3980 if (DstChild->getOperator()->isSubClassOf("Instruction")) {
3981 ArrayRef<TypeSetByHwMode> ChildTypes = DstChild->getExtTypes();
3982 if (ChildTypes.size() != 1)
3983 return failedImport("Dst pattern child has multiple results");
3985 Optional<LLTCodeGen> OpTyOrNone = None;
3986 if (ChildTypes.front().isMachineValueType())
3988 MVTToLLT(ChildTypes.front().getMachineValueType().SimpleTy);
3990 return failedImport("Dst operand has an unsupported type");
3992 unsigned TempRegID = Rule.allocateTempRegID();
3993 InsertPt = Rule.insertAction<MakeTempRegisterAction>(
3994 InsertPt, OpTyOrNone.getValue(), TempRegID);
3995 DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
3997 auto InsertPtOrError = createAndImportSubInstructionRenderer(
3998 ++InsertPt, Rule, DstChild, TempRegID);
3999 if (auto Error = InsertPtOrError.takeError())
4000 return std::move(Error);
4001 return InsertPtOrError.get();
4004 return failedImport("Dst pattern child isn't a leaf node or an MBB" + llvm::to_string(*DstChild));
4007 // It could be a specific immediate in which case we should just check for
4009 if (const IntInit *ChildIntInit =
4010 dyn_cast<IntInit>(DstChild->getLeafValue())) {
4011 DstMIBuilder.addRenderer<ImmRenderer>(ChildIntInit->getValue());
4015 // Otherwise, we're looking for a bog-standard RegisterClass operand.
4016 if (auto *ChildDefInit = dyn_cast<DefInit>(DstChild->getLeafValue())) {
4017 auto *ChildRec = ChildDefInit->getDef();
4019 ArrayRef<TypeSetByHwMode> ChildTypes = DstChild->getExtTypes();
4020 if (ChildTypes.size() != 1)
4021 return failedImport("Dst pattern child has multiple results");
4023 Optional<LLTCodeGen> OpTyOrNone = None;
4024 if (ChildTypes.front().isMachineValueType())
4025 OpTyOrNone = MVTToLLT(ChildTypes.front().getMachineValueType().SimpleTy);
4027 return failedImport("Dst operand has an unsupported type");
4029 if (ChildRec->isSubClassOf("Register")) {
4030 DstMIBuilder.addRenderer<AddRegisterRenderer>(ChildRec);
4034 if (ChildRec->isSubClassOf("RegisterClass") ||
4035 ChildRec->isSubClassOf("RegisterOperand") ||
4036 ChildRec->isSubClassOf("ValueType")) {
4037 if (ChildRec->isSubClassOf("RegisterOperand") &&
4038 !ChildRec->isValueUnset("GIZeroRegister")) {
4039 DstMIBuilder.addRenderer<CopyOrAddZeroRegRenderer>(
4040 DstChild->getName(), ChildRec->getValueAsDef("GIZeroRegister"));
4044 DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
4048 if (ChildRec->isSubClassOf("SubRegIndex")) {
4049 CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(ChildRec);
4050 DstMIBuilder.addRenderer<ImmRenderer>(SubIdx->EnumValue);
4054 if (ChildRec->isSubClassOf("ComplexPattern")) {
4055 const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
4056 if (ComplexPattern == ComplexPatternEquivs.end())
4057 return failedImport(
4058 "SelectionDAG ComplexPattern not mapped to GlobalISel");
4060 const OperandMatcher &OM = Rule.getOperandMatcher(DstChild->getName());
4061 DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
4062 *ComplexPattern->second, DstChild->getName(),
4063 OM.getAllocatedTemporariesBaseID());
4067 return failedImport(
4068 "Dst pattern child def is an unsupported tablegen class");
4071 return failedImport("Dst pattern child is an unsupported kind");
4074 Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
4075 RuleMatcher &M, InstructionMatcher &InsnMatcher, const TreePatternNode *Src,
4076 const TreePatternNode *Dst) {
4077 auto InsertPtOrError = createInstructionRenderer(M.actions_end(), M, Dst);
4078 if (auto Error = InsertPtOrError.takeError())
4079 return std::move(Error);
4081 action_iterator InsertPt = InsertPtOrError.get();
4082 BuildMIAction &DstMIBuilder = *static_cast<BuildMIAction *>(InsertPt->get());
4084 for (auto PhysInput : InsnMatcher.getPhysRegInputs()) {
4085 InsertPt = M.insertAction<BuildMIAction>(
4086 InsertPt, M.allocateOutputInsnID(),
4087 &Target.getInstruction(RK.getDef("COPY")));
4088 BuildMIAction &CopyToPhysRegMIBuilder =
4089 *static_cast<BuildMIAction *>(InsertPt->get());
4090 CopyToPhysRegMIBuilder.addRenderer<AddRegisterRenderer>(PhysInput.first,
4092 CopyToPhysRegMIBuilder.addRenderer<CopyPhysRegRenderer>(PhysInput.first);
4095 importExplicitDefRenderers(DstMIBuilder);
4097 if (auto Error = importExplicitUseRenderers(InsertPt, M, DstMIBuilder, Dst)
4099 return std::move(Error);
4101 return DstMIBuilder;
4104 Expected<action_iterator>
4105 GlobalISelEmitter::createAndImportSubInstructionRenderer(
4106 const action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst,
4107 unsigned TempRegID) {
4108 auto InsertPtOrError = createInstructionRenderer(InsertPt, M, Dst);
4110 // TODO: Assert there's exactly one result.
4112 if (auto Error = InsertPtOrError.takeError())
4113 return std::move(Error);
4115 BuildMIAction &DstMIBuilder =
4116 *static_cast<BuildMIAction *>(InsertPtOrError.get()->get());
4118 // Assign the result to TempReg.
4119 DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID, true);
4122 importExplicitUseRenderers(InsertPtOrError.get(), M, DstMIBuilder, Dst);
4123 if (auto Error = InsertPtOrError.takeError())
4124 return std::move(Error);
4126 // We need to make sure that when we import an INSERT_SUBREG as a
4127 // subinstruction that it ends up being constrained to the correct super
4128 // register and subregister classes.
4129 auto OpName = Target.getInstruction(Dst->getOperator()).TheDef->getName();
4130 if (OpName == "INSERT_SUBREG") {
4131 auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
4133 return failedImport(
4134 "Cannot infer register class from INSERT_SUBREG operand #1");
4135 Optional<const CodeGenRegisterClass *> SuperClass =
4136 inferSuperRegisterClassForNode(Dst->getExtType(0), Dst->getChild(0),
4139 return failedImport(
4140 "Cannot infer register class for INSERT_SUBREG operand #0");
4141 // The destination and the super register source of an INSERT_SUBREG must
4142 // be the same register class.
4143 M.insertAction<ConstrainOperandToRegClassAction>(
4144 InsertPt, DstMIBuilder.getInsnID(), 0, **SuperClass);
4145 M.insertAction<ConstrainOperandToRegClassAction>(
4146 InsertPt, DstMIBuilder.getInsnID(), 1, **SuperClass);
4147 M.insertAction<ConstrainOperandToRegClassAction>(
4148 InsertPt, DstMIBuilder.getInsnID(), 2, **SubClass);
4149 return InsertPtOrError.get();
4152 if (OpName == "EXTRACT_SUBREG") {
4153 // EXTRACT_SUBREG selects into a subregister COPY but unlike most
4154 // instructions, the result register class is controlled by the
4155 // subregisters of the operand. As a result, we must constrain the result
4156 // class rather than check that it's already the right one.
4157 auto SuperClass = inferRegClassFromPattern(Dst->getChild(0));
4159 return failedImport(
4160 "Cannot infer register class from EXTRACT_SUBREG operand #0");
4162 auto SubIdx = inferSubRegIndexForNode(Dst->getChild(1));
4164 return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
4166 const auto &SrcRCDstRCPair =
4167 (*SuperClass)->getMatchingSubClassWithSubRegs(CGRegs, *SubIdx);
4168 assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
4169 M.insertAction<ConstrainOperandToRegClassAction>(
4170 InsertPt, DstMIBuilder.getInsnID(), 0, *SrcRCDstRCPair->second);
4171 M.insertAction<ConstrainOperandToRegClassAction>(
4172 InsertPt, DstMIBuilder.getInsnID(), 1, *SrcRCDstRCPair->first);
4174 // We're done with this pattern! It's eligible for GISel emission; return
4176 return InsertPtOrError.get();
4179 // Similar to INSERT_SUBREG, we also have to handle SUBREG_TO_REG as a
4181 if (OpName == "SUBREG_TO_REG") {
4182 auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
4184 return failedImport(
4185 "Cannot infer register class from SUBREG_TO_REG child #1");
4186 auto SuperClass = inferSuperRegisterClass(Dst->getExtType(0),
4189 return failedImport(
4190 "Cannot infer register class for SUBREG_TO_REG operand #0");
4191 M.insertAction<ConstrainOperandToRegClassAction>(
4192 InsertPt, DstMIBuilder.getInsnID(), 0, **SuperClass);
4193 M.insertAction<ConstrainOperandToRegClassAction>(
4194 InsertPt, DstMIBuilder.getInsnID(), 2, **SubClass);
4195 return InsertPtOrError.get();
4198 M.insertAction<ConstrainOperandsToDefinitionAction>(InsertPt,
4199 DstMIBuilder.getInsnID());
4200 return InsertPtOrError.get();
4203 Expected<action_iterator> GlobalISelEmitter::createInstructionRenderer(
4204 action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst) {
4205 Record *DstOp = Dst->getOperator();
4206 if (!DstOp->isSubClassOf("Instruction")) {
4207 if (DstOp->isSubClassOf("ValueType"))
4208 return failedImport(
4209 "Pattern operator isn't an instruction (it's a ValueType)");
4210 return failedImport("Pattern operator isn't an instruction");
4212 CodeGenInstruction *DstI = &Target.getInstruction(DstOp);
4214 // COPY_TO_REGCLASS is just a copy with a ConstrainOperandToRegClassAction
4215 // attached. Similarly for EXTRACT_SUBREG except that's a subregister copy.
4216 StringRef Name = DstI->TheDef->getName();
4217 if (Name == "COPY_TO_REGCLASS" || Name == "EXTRACT_SUBREG")
4218 DstI = &Target.getInstruction(RK.getDef("COPY"));
4220 return M.insertAction<BuildMIAction>(InsertPt, M.allocateOutputInsnID(),
4224 void GlobalISelEmitter::importExplicitDefRenderers(
4225 BuildMIAction &DstMIBuilder) {
4226 const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
4227 for (unsigned I = 0; I < DstI->Operands.NumDefs; ++I) {
4228 const CGIOperandList::OperandInfo &DstIOperand = DstI->Operands[I];
4229 DstMIBuilder.addRenderer<CopyRenderer>(DstIOperand.Name);
4233 Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderers(
4234 action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
4235 const llvm::TreePatternNode *Dst) {
4236 const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
4237 CodeGenInstruction *OrigDstI = &Target.getInstruction(Dst->getOperator());
4239 StringRef Name = OrigDstI->TheDef->getName();
4240 unsigned ExpectedDstINumUses = Dst->getNumChildren();
4242 // EXTRACT_SUBREG needs to use a subregister COPY.
4243 if (Name == "EXTRACT_SUBREG") {
4244 if (!Dst->getChild(0)->isLeaf())
4245 return failedImport("EXTRACT_SUBREG child #1 is not a leaf");
4247 if (DefInit *SubRegInit =
4248 dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue())) {
4249 Record *RCDef = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
4251 return failedImport("EXTRACT_SUBREG child #0 could not "
4252 "be coerced to a register class");
4254 CodeGenRegisterClass *RC = CGRegs.getRegClass(RCDef);
4255 CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
4257 const auto &SrcRCDstRCPair =
4258 RC->getMatchingSubClassWithSubRegs(CGRegs, SubIdx);
4259 if (SrcRCDstRCPair.hasValue()) {
4260 assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
4261 if (SrcRCDstRCPair->first != RC)
4262 return failedImport("EXTRACT_SUBREG requires an additional COPY");
4265 DstMIBuilder.addRenderer<CopySubRegRenderer>(Dst->getChild(0)->getName(),
4270 return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
4273 if (Name == "REG_SEQUENCE") {
4274 if (!Dst->getChild(0)->isLeaf())
4275 return failedImport("REG_SEQUENCE child #0 is not a leaf");
4277 Record *RCDef = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
4279 return failedImport("REG_SEQUENCE child #0 could not "
4280 "be coerced to a register class");
4282 if ((ExpectedDstINumUses - 1) % 2 != 0)
4283 return failedImport("Malformed REG_SEQUENCE");
4285 for (unsigned I = 1; I != ExpectedDstINumUses; I += 2) {
4286 TreePatternNode *ValChild = Dst->getChild(I);
4287 TreePatternNode *SubRegChild = Dst->getChild(I + 1);
4289 if (DefInit *SubRegInit =
4290 dyn_cast<DefInit>(SubRegChild->getLeafValue())) {
4291 CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
4293 auto InsertPtOrError =
4294 importExplicitUseRenderer(InsertPt, M, DstMIBuilder, ValChild);
4295 if (auto Error = InsertPtOrError.takeError())
4296 return std::move(Error);
4297 InsertPt = InsertPtOrError.get();
4298 DstMIBuilder.addRenderer<SubRegIndexRenderer>(SubIdx);
4305 // Render the explicit uses.
4306 unsigned DstINumUses = OrigDstI->Operands.size() - OrigDstI->Operands.NumDefs;
4307 if (Name == "COPY_TO_REGCLASS") {
4308 DstINumUses--; // Ignore the class constraint.
4309 ExpectedDstINumUses--;
4313 unsigned NumDefaultOps = 0;
4314 for (unsigned I = 0; I != DstINumUses; ++I) {
4315 const CGIOperandList::OperandInfo &DstIOperand =
4316 DstI->Operands[DstI->Operands.NumDefs + I];
4318 // If the operand has default values, introduce them now.
4319 // FIXME: Until we have a decent test case that dictates we should do
4320 // otherwise, we're going to assume that operands with default values cannot
4321 // be specified in the patterns. Therefore, adding them will not cause us to
4322 // end up with too many rendered operands.
4323 if (DstIOperand.Rec->isSubClassOf("OperandWithDefaultOps")) {
4324 DagInit *DefaultOps = DstIOperand.Rec->getValueAsDag("DefaultOps");
4325 if (auto Error = importDefaultOperandRenderers(
4326 InsertPt, M, DstMIBuilder, DefaultOps))
4327 return std::move(Error);
4332 auto InsertPtOrError = importExplicitUseRenderer(InsertPt, M, DstMIBuilder,
4333 Dst->getChild(Child));
4334 if (auto Error = InsertPtOrError.takeError())
4335 return std::move(Error);
4336 InsertPt = InsertPtOrError.get();
4340 if (NumDefaultOps + ExpectedDstINumUses != DstINumUses)
4341 return failedImport("Expected " + llvm::to_string(DstINumUses) +
4342 " used operands but found " +
4343 llvm::to_string(ExpectedDstINumUses) +
4344 " explicit ones and " + llvm::to_string(NumDefaultOps) +
4350 Error GlobalISelEmitter::importDefaultOperandRenderers(
4351 action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
4352 DagInit *DefaultOps) const {
4353 for (const auto *DefaultOp : DefaultOps->getArgs()) {
4354 Optional<LLTCodeGen> OpTyOrNone = None;
4356 // Look through ValueType operators.
4357 if (const DagInit *DefaultDagOp = dyn_cast<DagInit>(DefaultOp)) {
4358 if (const DefInit *DefaultDagOperator =
4359 dyn_cast<DefInit>(DefaultDagOp->getOperator())) {
4360 if (DefaultDagOperator->getDef()->isSubClassOf("ValueType")) {
4361 OpTyOrNone = MVTToLLT(getValueType(
4362 DefaultDagOperator->getDef()));
4363 DefaultOp = DefaultDagOp->getArg(0);
4368 if (const DefInit *DefaultDefOp = dyn_cast<DefInit>(DefaultOp)) {
4369 auto Def = DefaultDefOp->getDef();
4370 if (Def->getName() == "undef_tied_input") {
4371 unsigned TempRegID = M.allocateTempRegID();
4372 M.insertAction<MakeTempRegisterAction>(
4373 InsertPt, OpTyOrNone.getValue(), TempRegID);
4374 InsertPt = M.insertAction<BuildMIAction>(
4375 InsertPt, M.allocateOutputInsnID(),
4376 &Target.getInstruction(RK.getDef("IMPLICIT_DEF")));
4377 BuildMIAction &IDMIBuilder = *static_cast<BuildMIAction *>(
4379 IDMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
4380 DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
4382 DstMIBuilder.addRenderer<AddRegisterRenderer>(Def);
4387 if (const IntInit *DefaultIntOp = dyn_cast<IntInit>(DefaultOp)) {
4388 DstMIBuilder.addRenderer<ImmRenderer>(DefaultIntOp->getValue());
4392 return failedImport("Could not add default op");
4395 return Error::success();
4398 Error GlobalISelEmitter::importImplicitDefRenderers(
4399 BuildMIAction &DstMIBuilder,
4400 const std::vector<Record *> &ImplicitDefs) const {
4401 if (!ImplicitDefs.empty())
4402 return failedImport("Pattern defines a physical register");
4403 return Error::success();
4406 Optional<const CodeGenRegisterClass *>
4407 GlobalISelEmitter::getRegClassFromLeaf(TreePatternNode *Leaf) {
4408 assert(Leaf && "Expected node?");
4409 assert(Leaf->isLeaf() && "Expected leaf?");
4410 Record *RCRec = getInitValueAsRegClass(Leaf->getLeafValue());
4413 CodeGenRegisterClass *RC = CGRegs.getRegClass(RCRec);
4419 Optional<const CodeGenRegisterClass *>
4420 GlobalISelEmitter::inferRegClassFromPattern(TreePatternNode *N) {
4425 return getRegClassFromLeaf(N);
4427 // We don't have a leaf node, so we have to try and infer something. Check
4428 // that we have an instruction that we an infer something from.
4430 // Only handle things that produce a single type.
4431 if (N->getNumTypes() != 1)
4433 Record *OpRec = N->getOperator();
4435 // We only want instructions.
4436 if (!OpRec->isSubClassOf("Instruction"))
4439 // Don't want to try and infer things when there could potentially be more
4440 // than one candidate register class.
4441 auto &Inst = Target.getInstruction(OpRec);
4442 if (Inst.Operands.NumDefs > 1)
4445 // Handle any special-case instructions which we can safely infer register
4447 StringRef InstName = Inst.TheDef->getName();
4448 bool IsRegSequence = InstName == "REG_SEQUENCE";
4449 if (IsRegSequence || InstName == "COPY_TO_REGCLASS") {
4450 // If we have a COPY_TO_REGCLASS, then we need to handle it specially. It
4451 // has the desired register class as the first child.
4452 TreePatternNode *RCChild = N->getChild(IsRegSequence ? 0 : 1);
4453 if (!RCChild->isLeaf())
4455 return getRegClassFromLeaf(RCChild);
4458 // Handle destination record types that we can safely infer a register class
4460 const auto &DstIOperand = Inst.Operands[0];
4461 Record *DstIOpRec = DstIOperand.Rec;
4462 if (DstIOpRec->isSubClassOf("RegisterOperand")) {
4463 DstIOpRec = DstIOpRec->getValueAsDef("RegClass");
4464 const CodeGenRegisterClass &RC = Target.getRegisterClass(DstIOpRec);
4468 if (DstIOpRec->isSubClassOf("RegisterClass")) {
4469 const CodeGenRegisterClass &RC = Target.getRegisterClass(DstIOpRec);
4476 Optional<const CodeGenRegisterClass *>
4477 GlobalISelEmitter::inferSuperRegisterClass(const TypeSetByHwMode &Ty,
4478 TreePatternNode *SubRegIdxNode) {
4479 assert(SubRegIdxNode && "Expected subregister index node!");
4480 // We need a ValueTypeByHwMode for getSuperRegForSubReg.
4481 if (!Ty.isValueTypeByHwMode(false))
4483 if (!SubRegIdxNode->isLeaf())
4485 DefInit *SubRegInit = dyn_cast<DefInit>(SubRegIdxNode->getLeafValue());
4488 CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
4490 // Use the information we found above to find a minimal register class which
4491 // supports the subregister and type we want.
4493 Target.getSuperRegForSubReg(Ty.getValueTypeByHwMode(), CGRegs, SubIdx);
4499 Optional<const CodeGenRegisterClass *>
4500 GlobalISelEmitter::inferSuperRegisterClassForNode(
4501 const TypeSetByHwMode &Ty, TreePatternNode *SuperRegNode,
4502 TreePatternNode *SubRegIdxNode) {
4503 assert(SuperRegNode && "Expected super register node!");
4504 // Check if we already have a defined register class for the super register
4505 // node. If we do, then we should preserve that rather than inferring anything
4506 // from the subregister index node. We can assume that whoever wrote the
4507 // pattern in the first place made sure that the super register and
4508 // subregister are compatible.
4509 if (Optional<const CodeGenRegisterClass *> SuperRegisterClass =
4510 inferRegClassFromPattern(SuperRegNode))
4511 return *SuperRegisterClass;
4512 return inferSuperRegisterClass(Ty, SubRegIdxNode);
4515 Optional<CodeGenSubRegIndex *>
4516 GlobalISelEmitter::inferSubRegIndexForNode(TreePatternNode *SubRegIdxNode) {
4517 if (!SubRegIdxNode->isLeaf())
4520 DefInit *SubRegInit = dyn_cast<DefInit>(SubRegIdxNode->getLeafValue());
4523 return CGRegs.getSubRegIdx(SubRegInit->getDef());
4526 Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
4527 // Keep track of the matchers and actions to emit.
4528 int Score = P.getPatternComplexity(CGP);
4529 RuleMatcher M(P.getSrcRecord()->getLoc());
4530 RuleMatcherScores[M.getRuleID()] = Score;
4531 M.addAction<DebugCommentAction>(llvm::to_string(*P.getSrcPattern()) +
4533 llvm::to_string(*P.getDstPattern()));
4535 if (auto Error = importRulePredicates(M, P.getPredicates()))
4536 return std::move(Error);
4538 // Next, analyze the pattern operators.
4539 TreePatternNode *Src = P.getSrcPattern();
4540 TreePatternNode *Dst = P.getDstPattern();
4542 // If the root of either pattern isn't a simple operator, ignore it.
4543 if (auto Err = isTrivialOperatorNode(Dst))
4544 return failedImport("Dst pattern root isn't a trivial operator (" +
4545 toString(std::move(Err)) + ")");
4546 if (auto Err = isTrivialOperatorNode(Src))
4547 return failedImport("Src pattern root isn't a trivial operator (" +
4548 toString(std::move(Err)) + ")");
4550 // The different predicates and matchers created during
4551 // addInstructionMatcher use the RuleMatcher M to set up their
4552 // instruction ID (InsnVarID) that are going to be used when
4553 // M is going to be emitted.
4554 // However, the code doing the emission still relies on the IDs
4555 // returned during that process by the RuleMatcher when issuing
4556 // the recordInsn opcodes.
4558 // 1. The order in which we created the predicates
4559 // and such must be the same as the order in which we emit them,
4561 // 2. We need to reset the generation of the IDs in M somewhere between
4562 // addInstructionMatcher and emit
4564 // FIXME: Long term, we don't want to have to rely on this implicit
4565 // naming being the same. One possible solution would be to have
4566 // explicit operator for operation capture and reference those.
4567 // The plus side is that it would expose opportunities to share
4568 // the capture accross rules. The downside is that it would
4569 // introduce a dependency between predicates (captures must happen
4570 // before their first use.)
4571 InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher(Src->getName());
4572 unsigned TempOpIdx = 0;
4573 auto InsnMatcherOrError =
4574 createAndImportSelDAGMatcher(M, InsnMatcherTemp, Src, TempOpIdx);
4575 if (auto Error = InsnMatcherOrError.takeError())
4576 return std::move(Error);
4577 InstructionMatcher &InsnMatcher = InsnMatcherOrError.get();
4579 if (Dst->isLeaf()) {
4580 Record *RCDef = getInitValueAsRegClass(Dst->getLeafValue());
4582 const CodeGenRegisterClass &RC = Target.getRegisterClass(RCDef);
4584 // We need to replace the def and all its uses with the specified
4585 // operand. However, we must also insert COPY's wherever needed.
4586 // For now, emit a copy and let the register allocator clean up.
4587 auto &DstI = Target.getInstruction(RK.getDef("COPY"));
4588 const auto &DstIOperand = DstI.Operands[0];
4590 OperandMatcher &OM0 = InsnMatcher.getOperand(0);
4591 OM0.setSymbolicName(DstIOperand.Name);
4592 M.defineOperand(OM0.getSymbolicName(), OM0);
4593 OM0.addPredicate<RegisterBankOperandMatcher>(RC);
4595 auto &DstMIBuilder =
4596 M.addAction<BuildMIAction>(M.allocateOutputInsnID(), &DstI);
4597 DstMIBuilder.addRenderer<CopyRenderer>(DstIOperand.Name);
4598 DstMIBuilder.addRenderer<CopyRenderer>(Dst->getName());
4599 M.addAction<ConstrainOperandToRegClassAction>(0, 0, RC);
4601 // We're done with this pattern! It's eligible for GISel emission; return
4603 ++NumPatternImported;
4604 return std::move(M);
4607 return failedImport("Dst pattern root isn't a known leaf");
4610 // Start with the defined operands (i.e., the results of the root operator).
4611 Record *DstOp = Dst->getOperator();
4612 if (!DstOp->isSubClassOf("Instruction"))
4613 return failedImport("Pattern operator isn't an instruction");
4615 auto &DstI = Target.getInstruction(DstOp);
4616 StringRef DstIName = DstI.TheDef->getName();
4618 if (DstI.Operands.NumDefs != Src->getExtTypes().size())
4619 return failedImport("Src pattern results and dst MI defs are different (" +
4620 to_string(Src->getExtTypes().size()) + " def(s) vs " +
4621 to_string(DstI.Operands.NumDefs) + " def(s))");
4623 // The root of the match also has constraints on the register bank so that it
4624 // matches the result instruction.
4626 for (const TypeSetByHwMode &VTy : Src->getExtTypes()) {
4629 const auto &DstIOperand = DstI.Operands[OpIdx];
4630 Record *DstIOpRec = DstIOperand.Rec;
4631 if (DstIName == "COPY_TO_REGCLASS") {
4632 DstIOpRec = getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());
4634 if (DstIOpRec == nullptr)
4635 return failedImport(
4636 "COPY_TO_REGCLASS operand #1 isn't a register class");
4637 } else if (DstIName == "REG_SEQUENCE") {
4638 DstIOpRec = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
4639 if (DstIOpRec == nullptr)
4640 return failedImport("REG_SEQUENCE operand #0 isn't a register class");
4641 } else if (DstIName == "EXTRACT_SUBREG") {
4642 if (!Dst->getChild(0)->isLeaf())
4643 return failedImport("EXTRACT_SUBREG operand #0 isn't a leaf");
4645 // We can assume that a subregister is in the same bank as it's super
4647 DstIOpRec = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
4649 if (DstIOpRec == nullptr)
4650 return failedImport("EXTRACT_SUBREG operand #0 isn't a register class");
4651 } else if (DstIName == "INSERT_SUBREG") {
4652 auto MaybeSuperClass = inferSuperRegisterClassForNode(
4653 VTy, Dst->getChild(0), Dst->getChild(2));
4654 if (!MaybeSuperClass)
4655 return failedImport(
4656 "Cannot infer register class for INSERT_SUBREG operand #0");
4657 // Move to the next pattern here, because the register class we found
4658 // doesn't necessarily have a record associated with it. So, we can't
4659 // set DstIOpRec using this.
4660 OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
4661 OM.setSymbolicName(DstIOperand.Name);
4662 M.defineOperand(OM.getSymbolicName(), OM);
4663 OM.addPredicate<RegisterBankOperandMatcher>(**MaybeSuperClass);
4666 } else if (DstIName == "SUBREG_TO_REG") {
4667 auto MaybeRegClass = inferSuperRegisterClass(VTy, Dst->getChild(2));
4669 return failedImport(
4670 "Cannot infer register class for SUBREG_TO_REG operand #0");
4671 OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
4672 OM.setSymbolicName(DstIOperand.Name);
4673 M.defineOperand(OM.getSymbolicName(), OM);
4674 OM.addPredicate<RegisterBankOperandMatcher>(**MaybeRegClass);
4677 } else if (DstIOpRec->isSubClassOf("RegisterOperand"))
4678 DstIOpRec = DstIOpRec->getValueAsDef("RegClass");
4679 else if (!DstIOpRec->isSubClassOf("RegisterClass"))
4680 return failedImport("Dst MI def isn't a register class" +
4683 OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
4684 OM.setSymbolicName(DstIOperand.Name);
4685 M.defineOperand(OM.getSymbolicName(), OM);
4686 OM.addPredicate<RegisterBankOperandMatcher>(
4687 Target.getRegisterClass(DstIOpRec));
4691 auto DstMIBuilderOrError =
4692 createAndImportInstructionRenderer(M, InsnMatcher, Src, Dst);
4693 if (auto Error = DstMIBuilderOrError.takeError())
4694 return std::move(Error);
4695 BuildMIAction &DstMIBuilder = DstMIBuilderOrError.get();
4697 // Render the implicit defs.
4698 // These are only added to the root of the result.
4699 if (auto Error = importImplicitDefRenderers(DstMIBuilder, P.getDstRegs()))
4700 return std::move(Error);
4702 DstMIBuilder.chooseInsnToMutate(M);
4704 // Constrain the registers to classes. This is normally derived from the
4705 // emitted instruction but a few instructions require special handling.
4706 if (DstIName == "COPY_TO_REGCLASS") {
4707 // COPY_TO_REGCLASS does not provide operand constraints itself but the
4708 // result is constrained to the class given by the second child.
4710 getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());
4712 if (DstIOpRec == nullptr)
4713 return failedImport("COPY_TO_REGCLASS operand #1 isn't a register class");
4715 M.addAction<ConstrainOperandToRegClassAction>(
4716 0, 0, Target.getRegisterClass(DstIOpRec));
4718 // We're done with this pattern! It's eligible for GISel emission; return
4720 ++NumPatternImported;
4721 return std::move(M);
4724 if (DstIName == "EXTRACT_SUBREG") {
4725 auto SuperClass = inferRegClassFromPattern(Dst->getChild(0));
4727 return failedImport(
4728 "Cannot infer register class from EXTRACT_SUBREG operand #0");
4730 auto SubIdx = inferSubRegIndexForNode(Dst->getChild(1));
4732 return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
4734 // It would be nice to leave this constraint implicit but we're required
4735 // to pick a register class so constrain the result to a register class
4736 // that can hold the correct MVT.
4738 // FIXME: This may introduce an extra copy if the chosen class doesn't
4739 // actually contain the subregisters.
4740 assert(Src->getExtTypes().size() == 1 &&
4741 "Expected Src of EXTRACT_SUBREG to have one result type");
4743 const auto &SrcRCDstRCPair =
4744 (*SuperClass)->getMatchingSubClassWithSubRegs(CGRegs, *SubIdx);
4745 assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
4746 M.addAction<ConstrainOperandToRegClassAction>(0, 0, *SrcRCDstRCPair->second);
4747 M.addAction<ConstrainOperandToRegClassAction>(0, 1, *SrcRCDstRCPair->first);
4749 // We're done with this pattern! It's eligible for GISel emission; return
4751 ++NumPatternImported;
4752 return std::move(M);
4755 if (DstIName == "INSERT_SUBREG") {
4756 assert(Src->getExtTypes().size() == 1 &&
4757 "Expected Src of INSERT_SUBREG to have one result type");
4758 // We need to constrain the destination, a super regsister source, and a
4759 // subregister source.
4760 auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
4762 return failedImport(
4763 "Cannot infer register class from INSERT_SUBREG operand #1");
4764 auto SuperClass = inferSuperRegisterClassForNode(
4765 Src->getExtType(0), Dst->getChild(0), Dst->getChild(2));
4767 return failedImport(
4768 "Cannot infer register class for INSERT_SUBREG operand #0");
4769 M.addAction<ConstrainOperandToRegClassAction>(0, 0, **SuperClass);
4770 M.addAction<ConstrainOperandToRegClassAction>(0, 1, **SuperClass);
4771 M.addAction<ConstrainOperandToRegClassAction>(0, 2, **SubClass);
4772 ++NumPatternImported;
4773 return std::move(M);
4776 if (DstIName == "SUBREG_TO_REG") {
4777 // We need to constrain the destination and subregister source.
4778 assert(Src->getExtTypes().size() == 1 &&
4779 "Expected Src of SUBREG_TO_REG to have one result type");
4781 // Attempt to infer the subregister source from the first child. If it has
4782 // an explicitly given register class, we'll use that. Otherwise, we will
4784 auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
4786 return failedImport(
4787 "Cannot infer register class from SUBREG_TO_REG child #1");
4788 // We don't have a child to look at that might have a super register node.
4790 inferSuperRegisterClass(Src->getExtType(0), Dst->getChild(2));
4792 return failedImport(
4793 "Cannot infer register class for SUBREG_TO_REG operand #0");
4794 M.addAction<ConstrainOperandToRegClassAction>(0, 0, **SuperClass);
4795 M.addAction<ConstrainOperandToRegClassAction>(0, 2, **SubClass);
4796 ++NumPatternImported;
4797 return std::move(M);
4800 M.addAction<ConstrainOperandsToDefinitionAction>(0);
4802 // We're done with this pattern! It's eligible for GISel emission; return it.
4803 ++NumPatternImported;
4804 return std::move(M);
4807 // Emit imm predicate table and an enum to reference them with.
4808 // The 'Predicate_' part of the name is redundant but eliminating it is more
4809 // trouble than it's worth.
4810 void GlobalISelEmitter::emitCxxPredicateFns(
4811 raw_ostream &OS, StringRef CodeFieldName, StringRef TypeIdentifier,
4812 StringRef ArgType, StringRef ArgName, StringRef AdditionalDeclarations,
4813 std::function<bool(const Record *R)> Filter) {
4814 std::vector<const Record *> MatchedRecords;
4815 const auto &Defs = RK.getAllDerivedDefinitions("PatFrag");
4816 std::copy_if(Defs.begin(), Defs.end(), std::back_inserter(MatchedRecords),
4817 [&](Record *Record) {
4818 return !Record->getValueAsString(CodeFieldName).empty() &&
4822 if (!MatchedRecords.empty()) {
4823 OS << "// PatFrag predicates.\n"
4825 std::string EnumeratorSeparator =
4826 (" = GIPFP_" + TypeIdentifier + "_Invalid + 1,\n").str();
4827 for (const auto *Record : MatchedRecords) {
4828 OS << " GIPFP_" << TypeIdentifier << "_Predicate_" << Record->getName()
4829 << EnumeratorSeparator;
4830 EnumeratorSeparator = ",\n";
4835 OS << "bool " << Target.getName() << "InstructionSelector::test" << ArgName
4836 << "Predicate_" << TypeIdentifier << "(unsigned PredicateID, " << ArgType << " "
4837 << ArgName << ") const {\n"
4838 << AdditionalDeclarations;
4839 if (!AdditionalDeclarations.empty())
4841 if (!MatchedRecords.empty())
4842 OS << " switch (PredicateID) {\n";
4843 for (const auto *Record : MatchedRecords) {
4844 OS << " case GIPFP_" << TypeIdentifier << "_Predicate_"
4845 << Record->getName() << ": {\n"
4846 << " " << Record->getValueAsString(CodeFieldName) << "\n"
4847 << " llvm_unreachable(\"" << CodeFieldName
4848 << " should have returned\");\n"
4849 << " return false;\n"
4852 if (!MatchedRecords.empty())
4854 OS << " llvm_unreachable(\"Unknown predicate\");\n"
4855 << " return false;\n"
4859 void GlobalISelEmitter::emitImmPredicateFns(
4860 raw_ostream &OS, StringRef TypeIdentifier, StringRef ArgType,
4861 std::function<bool(const Record *R)> Filter) {
4862 return emitCxxPredicateFns(OS, "ImmediateCode", TypeIdentifier, ArgType,
4866 void GlobalISelEmitter::emitMIPredicateFns(raw_ostream &OS) {
4867 return emitCxxPredicateFns(
4868 OS, "GISelPredicateCode", "MI", "const MachineInstr &", "MI",
4869 " const MachineFunction &MF = *MI.getParent()->getParent();\n"
4870 " const MachineRegisterInfo &MRI = MF.getRegInfo();\n"
4872 [](const Record *R) { return true; });
4875 template <class GroupT>
4876 std::vector<Matcher *> GlobalISelEmitter::optimizeRules(
4877 ArrayRef<Matcher *> Rules,
4878 std::vector<std::unique_ptr<Matcher>> &MatcherStorage) {
4880 std::vector<Matcher *> OptRules;
4881 std::unique_ptr<GroupT> CurrentGroup = std::make_unique<GroupT>();
4882 assert(CurrentGroup->empty() && "Newly created group isn't empty!");
4883 unsigned NumGroups = 0;
4885 auto ProcessCurrentGroup = [&]() {
4886 if (CurrentGroup->empty())
4887 // An empty group is good to be reused:
4890 // If the group isn't large enough to provide any benefit, move all the
4891 // added rules out of it and make sure to re-create the group to properly
4892 // re-initialize it:
4893 if (CurrentGroup->size() < 2)
4894 for (Matcher *M : CurrentGroup->matchers())
4895 OptRules.push_back(M);
4897 CurrentGroup->finalize();
4898 OptRules.push_back(CurrentGroup.get());
4899 MatcherStorage.emplace_back(std::move(CurrentGroup));
4902 CurrentGroup = std::make_unique<GroupT>();
4904 for (Matcher *Rule : Rules) {
4905 // Greedily add as many matchers as possible to the current group:
4906 if (CurrentGroup->addMatcher(*Rule))
4909 ProcessCurrentGroup();
4910 assert(CurrentGroup->empty() && "A group wasn't properly re-initialized");
4912 // Try to add the pending matcher to a newly created empty group:
4913 if (!CurrentGroup->addMatcher(*Rule))
4914 // If we couldn't add the matcher to an empty group, that group type
4915 // doesn't support that kind of matchers at all, so just skip it:
4916 OptRules.push_back(Rule);
4918 ProcessCurrentGroup();
4920 LLVM_DEBUG(dbgs() << "NumGroups: " << NumGroups << "\n");
4921 assert(CurrentGroup->empty() && "The last group wasn't properly processed");
4926 GlobalISelEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules,
4927 bool Optimize, bool WithCoverage) {
4928 std::vector<Matcher *> InputRules;
4929 for (Matcher &Rule : Rules)
4930 InputRules.push_back(&Rule);
4933 return MatchTable::buildTable(InputRules, WithCoverage);
4935 unsigned CurrentOrdering = 0;
4936 StringMap<unsigned> OpcodeOrder;
4937 for (RuleMatcher &Rule : Rules) {
4938 const StringRef Opcode = Rule.getOpcode();
4939 assert(!Opcode.empty() && "Didn't expect an undefined opcode");
4940 if (OpcodeOrder.count(Opcode) == 0)
4941 OpcodeOrder[Opcode] = CurrentOrdering++;
4944 std::stable_sort(InputRules.begin(), InputRules.end(),
4945 [&OpcodeOrder](const Matcher *A, const Matcher *B) {
4946 auto *L = static_cast<const RuleMatcher *>(A);
4947 auto *R = static_cast<const RuleMatcher *>(B);
4948 return std::make_tuple(OpcodeOrder[L->getOpcode()],
4949 L->getNumOperands()) <
4950 std::make_tuple(OpcodeOrder[R->getOpcode()],
4951 R->getNumOperands());
4954 for (Matcher *Rule : InputRules)
4957 std::vector<std::unique_ptr<Matcher>> MatcherStorage;
4958 std::vector<Matcher *> OptRules =
4959 optimizeRules<GroupMatcher>(InputRules, MatcherStorage);
4961 for (Matcher *Rule : OptRules)
4964 OptRules = optimizeRules<SwitchMatcher>(OptRules, MatcherStorage);
4966 return MatchTable::buildTable(OptRules, WithCoverage);
4969 void GroupMatcher::optimize() {
4970 // Make sure we only sort by a specific predicate within a range of rules that
4971 // all have that predicate checked against a specific value (not a wildcard):
4972 auto F = Matchers.begin();
4974 auto E = Matchers.end();
4977 auto *R = static_cast<RuleMatcher *>(*T);
4978 if (!R->getFirstConditionAsRootType().get().isValid())
4982 std::stable_sort(F, T, [](Matcher *A, Matcher *B) {
4983 auto *L = static_cast<RuleMatcher *>(A);
4984 auto *R = static_cast<RuleMatcher *>(B);
4985 return L->getFirstConditionAsRootType() <
4986 R->getFirstConditionAsRootType();
4991 GlobalISelEmitter::optimizeRules<GroupMatcher>(Matchers, MatcherStorage)
4993 GlobalISelEmitter::optimizeRules<SwitchMatcher>(Matchers, MatcherStorage)
4997 void GlobalISelEmitter::run(raw_ostream &OS) {
4998 if (!UseCoverageFile.empty()) {
4999 RuleCoverage = CodeGenCoverage();
5000 auto RuleCoverageBufOrErr = MemoryBuffer::getFile(UseCoverageFile);
5001 if (!RuleCoverageBufOrErr) {
5002 PrintWarning(SMLoc(), "Missing rule coverage data");
5003 RuleCoverage = None;
5005 if (!RuleCoverage->parse(*RuleCoverageBufOrErr.get(), Target.getName())) {
5006 PrintWarning(SMLoc(), "Ignoring invalid or missing rule coverage data");
5007 RuleCoverage = None;
5012 // Track the run-time opcode values
5013 gatherOpcodeValues();
5014 // Track the run-time LLT ID values
5015 gatherTypeIDValues();
5017 // Track the GINodeEquiv definitions.
5020 emitSourceFileHeader(("Global Instruction Selector for the " +
5021 Target.getName() + " target").str(), OS);
5022 std::vector<RuleMatcher> Rules;
5023 // Look through the SelectionDAG patterns we found, possibly emitting some.
5024 for (const PatternToMatch &Pat : CGP.ptms()) {
5027 auto MatcherOrErr = runOnPattern(Pat);
5029 // The pattern analysis can fail, indicating an unsupported pattern.
5030 // Report that if we've been asked to do so.
5031 if (auto Err = MatcherOrErr.takeError()) {
5032 if (WarnOnSkippedPatterns) {
5033 PrintWarning(Pat.getSrcRecord()->getLoc(),
5034 "Skipped pattern: " + toString(std::move(Err)));
5036 consumeError(std::move(Err));
5038 ++NumPatternImportsSkipped;
5043 if (RuleCoverage->isCovered(MatcherOrErr->getRuleID()))
5044 ++NumPatternsTested;
5046 PrintWarning(Pat.getSrcRecord()->getLoc(),
5047 "Pattern is not covered by a test");
5049 Rules.push_back(std::move(MatcherOrErr.get()));
5052 // Comparison function to order records by name.
5053 auto orderByName = [](const Record *A, const Record *B) {
5054 return A->getName() < B->getName();
5057 std::vector<Record *> ComplexPredicates =
5058 RK.getAllDerivedDefinitions("GIComplexOperandMatcher");
5059 llvm::sort(ComplexPredicates, orderByName);
5061 std::vector<Record *> CustomRendererFns =
5062 RK.getAllDerivedDefinitions("GICustomOperandRenderer");
5063 llvm::sort(CustomRendererFns, orderByName);
5065 unsigned MaxTemporaries = 0;
5066 for (const auto &Rule : Rules)
5067 MaxTemporaries = std::max(MaxTemporaries, Rule.countRendererFns());
5069 OS << "#ifdef GET_GLOBALISEL_PREDICATE_BITSET\n"
5070 << "const unsigned MAX_SUBTARGET_PREDICATES = " << SubtargetFeatures.size()
5072 << "using PredicateBitset = "
5073 "llvm::PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;\n"
5074 << "#endif // ifdef GET_GLOBALISEL_PREDICATE_BITSET\n\n";
5076 OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n"
5077 << " mutable MatcherState State;\n"
5079 "ComplexRendererFns("
5081 << "InstructionSelector::*ComplexMatcherMemFn)(MachineOperand &) const;\n"
5083 << " typedef void(" << Target.getName()
5084 << "InstructionSelector::*CustomRendererFn)(MachineInstrBuilder &, const "
5087 << " const ISelInfoTy<PredicateBitset, ComplexMatcherMemFn, "
5088 "CustomRendererFn> "
5090 OS << " static " << Target.getName()
5091 << "InstructionSelector::ComplexMatcherMemFn ComplexPredicateFns[];\n"
5092 << " static " << Target.getName()
5093 << "InstructionSelector::CustomRendererFn CustomRenderers[];\n"
5094 << " bool testImmPredicate_I64(unsigned PredicateID, int64_t Imm) const "
5096 << " bool testImmPredicate_APInt(unsigned PredicateID, const APInt &Imm) "
5098 << " bool testImmPredicate_APFloat(unsigned PredicateID, const APFloat "
5099 "&Imm) const override;\n"
5100 << " const int64_t *getMatchTable() const override;\n"
5101 << " bool testMIPredicate_MI(unsigned PredicateID, const MachineInstr &MI) "
5103 << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n";
5105 OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n"
5106 << ", State(" << MaxTemporaries << "),\n"
5107 << "ISelInfo(TypeObjects, NumTypeObjects, FeatureBitsets"
5108 << ", ComplexPredicateFns, CustomRenderers)\n"
5109 << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";
5111 OS << "#ifdef GET_GLOBALISEL_IMPL\n";
5112 SubtargetFeatureInfo::emitSubtargetFeatureBitEnumeration(SubtargetFeatures,
5115 // Separate subtarget features by how often they must be recomputed.
5116 SubtargetFeatureInfoMap ModuleFeatures;
5117 std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
5118 std::inserter(ModuleFeatures, ModuleFeatures.end()),
5119 [](const SubtargetFeatureInfoMap::value_type &X) {
5120 return !X.second.mustRecomputePerFunction();
5122 SubtargetFeatureInfoMap FunctionFeatures;
5123 std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
5124 std::inserter(FunctionFeatures, FunctionFeatures.end()),
5125 [](const SubtargetFeatureInfoMap::value_type &X) {
5126 return X.second.mustRecomputePerFunction();
5129 SubtargetFeatureInfo::emitComputeAvailableFeatures(
5130 Target.getName(), "InstructionSelector", "computeAvailableModuleFeatures",
5131 ModuleFeatures, OS);
5132 SubtargetFeatureInfo::emitComputeAvailableFeatures(
5133 Target.getName(), "InstructionSelector",
5134 "computeAvailableFunctionFeatures", FunctionFeatures, OS,
5135 "const MachineFunction *MF");
5137 // Emit a table containing the LLT objects needed by the matcher and an enum
5138 // for the matcher to reference them with.
5139 std::vector<LLTCodeGen> TypeObjects;
5140 for (const auto &Ty : KnownTypes)
5141 TypeObjects.push_back(Ty);
5142 llvm::sort(TypeObjects);
5143 OS << "// LLT Objects.\n"
5145 for (const auto &TypeObject : TypeObjects) {
5147 TypeObject.emitCxxEnumValue(OS);
5151 OS << "const static size_t NumTypeObjects = " << TypeObjects.size() << ";\n"
5152 << "const static LLT TypeObjects[] = {\n";
5153 for (const auto &TypeObject : TypeObjects) {
5155 TypeObject.emitCxxConstructorCall(OS);
5160 // Emit a table containing the PredicateBitsets objects needed by the matcher
5161 // and an enum for the matcher to reference them with.
5162 std::vector<std::vector<Record *>> FeatureBitsets;
5163 for (auto &Rule : Rules)
5164 FeatureBitsets.push_back(Rule.getRequiredFeatures());
5165 llvm::sort(FeatureBitsets, [&](const std::vector<Record *> &A,
5166 const std::vector<Record *> &B) {
5167 if (A.size() < B.size())
5169 if (A.size() > B.size())
5171 for (const auto &Pair : zip(A, B)) {
5172 if (std::get<0>(Pair)->getName() < std::get<1>(Pair)->getName())
5174 if (std::get<0>(Pair)->getName() > std::get<1>(Pair)->getName())
5179 FeatureBitsets.erase(
5180 std::unique(FeatureBitsets.begin(), FeatureBitsets.end()),
5181 FeatureBitsets.end());
5182 OS << "// Feature bitsets.\n"
5184 << " GIFBS_Invalid,\n";
5185 for (const auto &FeatureBitset : FeatureBitsets) {
5186 if (FeatureBitset.empty())
5188 OS << " " << getNameForFeatureBitset(FeatureBitset) << ",\n";
5191 << "const static PredicateBitset FeatureBitsets[] {\n"
5192 << " {}, // GIFBS_Invalid\n";
5193 for (const auto &FeatureBitset : FeatureBitsets) {
5194 if (FeatureBitset.empty())
5197 for (const auto &Feature : FeatureBitset) {
5198 const auto &I = SubtargetFeatures.find(Feature);
5199 assert(I != SubtargetFeatures.end() && "Didn't import predicate?");
5200 OS << I->second.getEnumBitName() << ", ";
5206 // Emit complex predicate table and an enum to reference them with.
5207 OS << "// ComplexPattern predicates.\n"
5209 << " GICP_Invalid,\n";
5210 for (const auto &Record : ComplexPredicates)
5211 OS << " GICP_" << Record->getName() << ",\n";
5213 << "// See constructor for table contents\n\n";
5215 emitImmPredicateFns(OS, "I64", "int64_t", [](const Record *R) {
5217 return !R->getValueAsBitOrUnset("IsAPFloat", Unset) &&
5218 !R->getValueAsBit("IsAPInt");
5220 emitImmPredicateFns(OS, "APFloat", "const APFloat &", [](const Record *R) {
5222 return R->getValueAsBitOrUnset("IsAPFloat", Unset);
5224 emitImmPredicateFns(OS, "APInt", "const APInt &", [](const Record *R) {
5225 return R->getValueAsBit("IsAPInt");
5227 emitMIPredicateFns(OS);
5230 OS << Target.getName() << "InstructionSelector::ComplexMatcherMemFn\n"
5231 << Target.getName() << "InstructionSelector::ComplexPredicateFns[] = {\n"
5232 << " nullptr, // GICP_Invalid\n";
5233 for (const auto &Record : ComplexPredicates)
5234 OS << " &" << Target.getName()
5235 << "InstructionSelector::" << Record->getValueAsString("MatcherFn")
5236 << ", // " << Record->getName() << "\n";
5239 OS << "// Custom renderers.\n"
5241 << " GICR_Invalid,\n";
5242 for (const auto &Record : CustomRendererFns)
5243 OS << " GICR_" << Record->getValueAsString("RendererFn") << ", \n";
5246 OS << Target.getName() << "InstructionSelector::CustomRendererFn\n"
5247 << Target.getName() << "InstructionSelector::CustomRenderers[] = {\n"
5248 << " nullptr, // GICP_Invalid\n";
5249 for (const auto &Record : CustomRendererFns)
5250 OS << " &" << Target.getName()
5251 << "InstructionSelector::" << Record->getValueAsString("RendererFn")
5252 << ", // " << Record->getName() << "\n";
5255 llvm::stable_sort(Rules, [&](const RuleMatcher &A, const RuleMatcher &B) {
5256 int ScoreA = RuleMatcherScores[A.getRuleID()];
5257 int ScoreB = RuleMatcherScores[B.getRuleID()];
5258 if (ScoreA > ScoreB)
5260 if (ScoreB > ScoreA)
5262 if (A.isHigherPriorityThan(B)) {
5263 assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
5264 "and less important at "
5271 OS << "bool " << Target.getName()
5272 << "InstructionSelector::selectImpl(MachineInstr &I, CodeGenCoverage "
5273 "&CoverageInfo) const {\n"
5274 << " MachineFunction &MF = *I.getParent()->getParent();\n"
5275 << " MachineRegisterInfo &MRI = MF.getRegInfo();\n"
5276 << " // FIXME: This should be computed on a per-function basis rather "
5278 << " AvailableFunctionFeatures = computeAvailableFunctionFeatures(&STI, "
5280 << " const PredicateBitset AvailableFeatures = getAvailableFeatures();\n"
5281 << " NewMIVector OutMIs;\n"
5282 << " State.MIs.clear();\n"
5283 << " State.MIs.push_back(&I);\n\n"
5284 << " if (executeMatchTable(*this, OutMIs, State, ISelInfo"
5285 << ", getMatchTable(), TII, MRI, TRI, RBI, AvailableFeatures"
5286 << ", CoverageInfo)) {\n"
5287 << " return true;\n"
5289 << " return false;\n"
5292 const MatchTable Table =
5293 buildMatchTable(Rules, OptimizeMatchTable, GenerateCoverage);
5294 OS << "const int64_t *" << Target.getName()
5295 << "InstructionSelector::getMatchTable() const {\n";
5296 Table.emitDeclaration(OS);
5300 OS << "#endif // ifdef GET_GLOBALISEL_IMPL\n";
5302 OS << "#ifdef GET_GLOBALISEL_PREDICATES_DECL\n"
5303 << "PredicateBitset AvailableModuleFeatures;\n"
5304 << "mutable PredicateBitset AvailableFunctionFeatures;\n"
5305 << "PredicateBitset getAvailableFeatures() const {\n"
5306 << " return AvailableModuleFeatures | AvailableFunctionFeatures;\n"
5308 << "PredicateBitset\n"
5309 << "computeAvailableModuleFeatures(const " << Target.getName()
5310 << "Subtarget *Subtarget) const;\n"
5311 << "PredicateBitset\n"
5312 << "computeAvailableFunctionFeatures(const " << Target.getName()
5313 << "Subtarget *Subtarget,\n"
5314 << " const MachineFunction *MF) const;\n"
5315 << "#endif // ifdef GET_GLOBALISEL_PREDICATES_DECL\n";
5317 OS << "#ifdef GET_GLOBALISEL_PREDICATES_INIT\n"
5318 << "AvailableModuleFeatures(computeAvailableModuleFeatures(&STI)),\n"
5319 << "AvailableFunctionFeatures()\n"
5320 << "#endif // ifdef GET_GLOBALISEL_PREDICATES_INIT\n";
5323 void GlobalISelEmitter::declareSubtargetFeature(Record *Predicate) {
5324 if (SubtargetFeatures.count(Predicate) == 0)
5325 SubtargetFeatures.emplace(
5326 Predicate, SubtargetFeatureInfo(Predicate, SubtargetFeatures.size()));
5329 void RuleMatcher::optimize() {
5330 for (auto &Item : InsnVariableIDs) {
5331 InstructionMatcher &InsnMatcher = *Item.first;
5332 for (auto &OM : InsnMatcher.operands()) {
5333 // Complex Patterns are usually expensive and they relatively rarely fail
5334 // on their own: more often we end up throwing away all the work done by a
5335 // matching part of a complex pattern because some other part of the
5336 // enclosing pattern didn't match. All of this makes it beneficial to
5337 // delay complex patterns until the very end of the rule matching,
5338 // especially for targets having lots of complex patterns.
5339 for (auto &OP : OM->predicates())
5340 if (isa<ComplexPatternOperandMatcher>(OP))
5341 EpilogueMatchers.emplace_back(std::move(OP));
5342 OM->eraseNullPredicates();
5344 InsnMatcher.optimize();
5346 llvm::sort(EpilogueMatchers, [](const std::unique_ptr<PredicateMatcher> &L,
5347 const std::unique_ptr<PredicateMatcher> &R) {
5348 return std::make_tuple(L->getKind(), L->getInsnVarID(), L->getOpIdx()) <
5349 std::make_tuple(R->getKind(), R->getInsnVarID(), R->getOpIdx());
5353 bool RuleMatcher::hasFirstCondition() const {
5354 if (insnmatchers_empty())
5356 InstructionMatcher &Matcher = insnmatchers_front();
5357 if (!Matcher.predicates_empty())
5359 for (auto &OM : Matcher.operands())
5360 for (auto &OP : OM->predicates())
5361 if (!isa<InstructionOperandMatcher>(OP))
5366 const PredicateMatcher &RuleMatcher::getFirstCondition() const {
5367 assert(!insnmatchers_empty() &&
5368 "Trying to get a condition from an empty RuleMatcher");
5370 InstructionMatcher &Matcher = insnmatchers_front();
5371 if (!Matcher.predicates_empty())
5372 return **Matcher.predicates_begin();
5373 // If there is no more predicate on the instruction itself, look at its
5375 for (auto &OM : Matcher.operands())
5376 for (auto &OP : OM->predicates())
5377 if (!isa<InstructionOperandMatcher>(OP))
5380 llvm_unreachable("Trying to get a condition from an InstructionMatcher with "
5384 std::unique_ptr<PredicateMatcher> RuleMatcher::popFirstCondition() {
5385 assert(!insnmatchers_empty() &&
5386 "Trying to pop a condition from an empty RuleMatcher");
5388 InstructionMatcher &Matcher = insnmatchers_front();
5389 if (!Matcher.predicates_empty())
5390 return Matcher.predicates_pop_front();
5391 // If there is no more predicate on the instruction itself, look at its
5393 for (auto &OM : Matcher.operands())
5394 for (auto &OP : OM->predicates())
5395 if (!isa<InstructionOperandMatcher>(OP)) {
5396 std::unique_ptr<PredicateMatcher> Result = std::move(OP);
5397 OM->eraseNullPredicates();
5401 llvm_unreachable("Trying to pop a condition from an InstructionMatcher with "
5405 bool GroupMatcher::candidateConditionMatches(
5406 const PredicateMatcher &Predicate) const {
5409 // Sharing predicates for nested instructions is not supported yet as we
5410 // currently don't hoist the GIM_RecordInsn's properly, therefore we can
5411 // only work on the original root instruction (InsnVarID == 0):
5412 if (Predicate.getInsnVarID() != 0)
5414 // ... otherwise an empty group can handle any predicate with no specific
5419 const Matcher &Representative = **Matchers.begin();
5420 const auto &RepresentativeCondition = Representative.getFirstCondition();
5421 // ... if not empty, the group can only accomodate matchers with the exact
5422 // same first condition:
5423 return Predicate.isIdentical(RepresentativeCondition);
5426 bool GroupMatcher::addMatcher(Matcher &Candidate) {
5427 if (!Candidate.hasFirstCondition())
5430 const PredicateMatcher &Predicate = Candidate.getFirstCondition();
5431 if (!candidateConditionMatches(Predicate))
5434 Matchers.push_back(&Candidate);
5438 void GroupMatcher::finalize() {
5439 assert(Conditions.empty() && "Already finalized?");
5443 Matcher &FirstRule = **Matchers.begin();
5445 // All the checks are expected to succeed during the first iteration:
5446 for (const auto &Rule : Matchers)
5447 if (!Rule->hasFirstCondition())
5449 const auto &FirstCondition = FirstRule.getFirstCondition();
5450 for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
5451 if (!Matchers[I]->getFirstCondition().isIdentical(FirstCondition))
5454 Conditions.push_back(FirstRule.popFirstCondition());
5455 for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
5456 Matchers[I]->popFirstCondition();
5460 void GroupMatcher::emit(MatchTable &Table) {
5461 unsigned LabelID = ~0U;
5462 if (!Conditions.empty()) {
5463 LabelID = Table.allocateLabelID();
5464 Table << MatchTable::Opcode("GIM_Try", +1)
5465 << MatchTable::Comment("On fail goto")
5466 << MatchTable::JumpTarget(LabelID) << MatchTable::LineBreak;
5468 for (auto &Condition : Conditions)
5469 Condition->emitPredicateOpcodes(
5470 Table, *static_cast<RuleMatcher *>(*Matchers.begin()));
5472 for (const auto &M : Matchers)
5476 if (!Conditions.empty())
5477 Table << MatchTable::Opcode("GIM_Reject", -1) << MatchTable::LineBreak
5478 << MatchTable::Label(LabelID);
5481 bool SwitchMatcher::isSupportedPredicateType(const PredicateMatcher &P) {
5482 return isa<InstructionOpcodeMatcher>(P) || isa<LLTOperandMatcher>(P);
5485 bool SwitchMatcher::candidateConditionMatches(
5486 const PredicateMatcher &Predicate) const {
5489 // Sharing predicates for nested instructions is not supported yet as we
5490 // currently don't hoist the GIM_RecordInsn's properly, therefore we can
5491 // only work on the original root instruction (InsnVarID == 0):
5492 if (Predicate.getInsnVarID() != 0)
5494 // ... while an attempt to add even a root matcher to an empty SwitchMatcher
5495 // could fail as not all the types of conditions are supported:
5496 if (!isSupportedPredicateType(Predicate))
5498 // ... or the condition might not have a proper implementation of
5499 // getValue() / isIdenticalDownToValue() yet:
5500 if (!Predicate.hasValue())
5502 // ... otherwise an empty Switch can accomodate the condition with no
5503 // further requirements:
5507 const Matcher &CaseRepresentative = **Matchers.begin();
5508 const auto &RepresentativeCondition = CaseRepresentative.getFirstCondition();
5509 // Switch-cases must share the same kind of condition and path to the value it
5511 if (!Predicate.isIdenticalDownToValue(RepresentativeCondition))
5514 const auto Value = Predicate.getValue();
5515 // ... but be unique with respect to the actual value they check:
5516 return Values.count(Value) == 0;
5519 bool SwitchMatcher::addMatcher(Matcher &Candidate) {
5520 if (!Candidate.hasFirstCondition())
5523 const PredicateMatcher &Predicate = Candidate.getFirstCondition();
5524 if (!candidateConditionMatches(Predicate))
5526 const auto Value = Predicate.getValue();
5527 Values.insert(Value);
5529 Matchers.push_back(&Candidate);
5533 void SwitchMatcher::finalize() {
5534 assert(Condition == nullptr && "Already finalized");
5535 assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");
5539 std::stable_sort(Matchers.begin(), Matchers.end(),
5540 [](const Matcher *L, const Matcher *R) {
5541 return L->getFirstCondition().getValue() <
5542 R->getFirstCondition().getValue();
5544 Condition = Matchers[0]->popFirstCondition();
5545 for (unsigned I = 1, E = Values.size(); I < E; ++I)
5546 Matchers[I]->popFirstCondition();
5549 void SwitchMatcher::emitPredicateSpecificOpcodes(const PredicateMatcher &P,
5550 MatchTable &Table) {
5551 assert(isSupportedPredicateType(P) && "Predicate type is not supported");
5553 if (const auto *Condition = dyn_cast<InstructionOpcodeMatcher>(&P)) {
5554 Table << MatchTable::Opcode("GIM_SwitchOpcode") << MatchTable::Comment("MI")
5555 << MatchTable::IntValue(Condition->getInsnVarID());
5558 if (const auto *Condition = dyn_cast<LLTOperandMatcher>(&P)) {
5559 Table << MatchTable::Opcode("GIM_SwitchType") << MatchTable::Comment("MI")
5560 << MatchTable::IntValue(Condition->getInsnVarID())
5561 << MatchTable::Comment("Op")
5562 << MatchTable::IntValue(Condition->getOpIdx());
5566 llvm_unreachable("emitPredicateSpecificOpcodes is broken: can not handle a "
5567 "predicate type that is claimed to be supported");
5570 void SwitchMatcher::emit(MatchTable &Table) {
5571 assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");
5574 assert(Condition != nullptr &&
5575 "Broken SwitchMatcher, hasn't been finalized?");
5577 std::vector<unsigned> LabelIDs(Values.size());
5578 std::generate(LabelIDs.begin(), LabelIDs.end(),
5579 [&Table]() { return Table.allocateLabelID(); });
5580 const unsigned Default = Table.allocateLabelID();
5582 const int64_t LowerBound = Values.begin()->getRawValue();
5583 const int64_t UpperBound = Values.rbegin()->getRawValue() + 1;
5585 emitPredicateSpecificOpcodes(*Condition, Table);
5587 Table << MatchTable::Comment("[") << MatchTable::IntValue(LowerBound)
5588 << MatchTable::IntValue(UpperBound) << MatchTable::Comment(")")
5589 << MatchTable::Comment("default:") << MatchTable::JumpTarget(Default);
5591 int64_t J = LowerBound;
5592 auto VI = Values.begin();
5593 for (unsigned I = 0, E = Values.size(); I < E; ++I) {
5595 while (J++ < V.getRawValue())
5596 Table << MatchTable::IntValue(0);
5597 V.turnIntoComment();
5598 Table << MatchTable::LineBreak << V << MatchTable::JumpTarget(LabelIDs[I]);
5600 Table << MatchTable::LineBreak;
5602 for (unsigned I = 0, E = Values.size(); I < E; ++I) {
5603 Table << MatchTable::Label(LabelIDs[I]);
5604 Matchers[I]->emit(Table);
5605 Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
5607 Table << MatchTable::Label(Default);
5610 unsigned OperandMatcher::getInsnVarID() const { return Insn.getInsnVarID(); }
5612 } // end anonymous namespace
5614 //===----------------------------------------------------------------------===//
5617 void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS) {
5618 GlobalISelEmitter(RK).run(OS);
5620 } // End llvm namespace