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),
451 assert((!LabelID_.hasValue() || LabelID != ~0u) &&
452 "This value is reserved for non-labels");
454 MatchTableRecord(const MatchTableRecord &Other) = default;
455 MatchTableRecord(MatchTableRecord &&Other) = default;
457 /// Useful if a Match Table Record gets optimized out
458 void turnIntoComment() {
459 Flags |= MTRF_Comment;
460 Flags &= ~MTRF_CommaFollows;
464 /// For Jump Table generation purposes
465 bool operator<(const MatchTableRecord &Other) const {
466 return RawValue < Other.RawValue;
468 int64_t getRawValue() const { return RawValue; }
470 void emit(raw_ostream &OS, bool LineBreakNextAfterThis,
471 const MatchTable &Table) const;
472 unsigned size() const { return NumElements; }
477 /// Holds the contents of a generated MatchTable to enable formatting and the
478 /// necessary index tracking needed to support GIM_Try.
480 /// An unique identifier for the table. The generated table will be named
483 /// The records that make up the table. Also includes comments describing the
484 /// values being emitted and line breaks to format it.
485 std::vector<MatchTableRecord> Contents;
486 /// The currently defined labels.
487 DenseMap<unsigned, unsigned> LabelMap;
488 /// Tracks the sum of MatchTableRecord::NumElements as the table is built.
489 unsigned CurrentSize = 0;
490 /// A unique identifier for a MatchTable label.
491 unsigned CurrentLabelID = 0;
492 /// Determines if the table should be instrumented for rule coverage tracking.
496 static MatchTableRecord LineBreak;
497 static MatchTableRecord Comment(StringRef Comment) {
498 return MatchTableRecord(None, Comment, 0, MatchTableRecord::MTRF_Comment);
500 static MatchTableRecord Opcode(StringRef Opcode, int IndentAdjust = 0) {
501 unsigned ExtraFlags = 0;
502 if (IndentAdjust > 0)
503 ExtraFlags |= MatchTableRecord::MTRF_Indent;
504 if (IndentAdjust < 0)
505 ExtraFlags |= MatchTableRecord::MTRF_Outdent;
507 return MatchTableRecord(None, Opcode, 1,
508 MatchTableRecord::MTRF_CommaFollows | ExtraFlags);
510 static MatchTableRecord NamedValue(StringRef NamedValue) {
511 return MatchTableRecord(None, NamedValue, 1,
512 MatchTableRecord::MTRF_CommaFollows);
514 static MatchTableRecord NamedValue(StringRef NamedValue, int64_t RawValue) {
515 return MatchTableRecord(None, NamedValue, 1,
516 MatchTableRecord::MTRF_CommaFollows, RawValue);
518 static MatchTableRecord NamedValue(StringRef Namespace,
519 StringRef NamedValue) {
520 return MatchTableRecord(None, (Namespace + "::" + NamedValue).str(), 1,
521 MatchTableRecord::MTRF_CommaFollows);
523 static MatchTableRecord NamedValue(StringRef Namespace, StringRef NamedValue,
525 return MatchTableRecord(None, (Namespace + "::" + NamedValue).str(), 1,
526 MatchTableRecord::MTRF_CommaFollows, RawValue);
528 static MatchTableRecord IntValue(int64_t IntValue) {
529 return MatchTableRecord(None, llvm::to_string(IntValue), 1,
530 MatchTableRecord::MTRF_CommaFollows);
532 static MatchTableRecord Label(unsigned LabelID) {
533 return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 0,
534 MatchTableRecord::MTRF_Label |
535 MatchTableRecord::MTRF_Comment |
536 MatchTableRecord::MTRF_LineBreakFollows);
538 static MatchTableRecord JumpTarget(unsigned LabelID) {
539 return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 1,
540 MatchTableRecord::MTRF_JumpTarget |
541 MatchTableRecord::MTRF_Comment |
542 MatchTableRecord::MTRF_CommaFollows);
545 static MatchTable buildTable(ArrayRef<Matcher *> Rules, bool WithCoverage);
547 MatchTable(bool WithCoverage, unsigned ID = 0)
548 : ID(ID), IsWithCoverage(WithCoverage) {}
550 bool isWithCoverage() const { return IsWithCoverage; }
552 void push_back(const MatchTableRecord &Value) {
553 if (Value.Flags & MatchTableRecord::MTRF_Label)
554 defineLabel(Value.LabelID);
555 Contents.push_back(Value);
556 CurrentSize += Value.size();
559 unsigned allocateLabelID() { return CurrentLabelID++; }
561 void defineLabel(unsigned LabelID) {
562 LabelMap.insert(std::make_pair(LabelID, CurrentSize));
565 unsigned getLabelIndex(unsigned LabelID) const {
566 const auto I = LabelMap.find(LabelID);
567 assert(I != LabelMap.end() && "Use of undeclared label");
571 void emitUse(raw_ostream &OS) const { OS << "MatchTable" << ID; }
573 void emitDeclaration(raw_ostream &OS) const {
574 unsigned Indentation = 4;
575 OS << " constexpr static int64_t MatchTable" << ID << "[] = {";
576 LineBreak.emit(OS, true, *this);
577 OS << std::string(Indentation, ' ');
579 for (auto I = Contents.begin(), E = Contents.end(); I != E;
581 bool LineBreakIsNext = false;
582 const auto &NextI = std::next(I);
585 if (NextI->EmitStr == "" &&
586 NextI->Flags == MatchTableRecord::MTRF_LineBreakFollows)
587 LineBreakIsNext = true;
590 if (I->Flags & MatchTableRecord::MTRF_Indent)
593 I->emit(OS, LineBreakIsNext, *this);
594 if (I->Flags & MatchTableRecord::MTRF_LineBreakFollows)
595 OS << std::string(Indentation, ' ');
597 if (I->Flags & MatchTableRecord::MTRF_Outdent)
604 MatchTableRecord MatchTable::LineBreak = {
605 None, "" /* Emit String */, 0 /* Elements */,
606 MatchTableRecord::MTRF_LineBreakFollows};
608 void MatchTableRecord::emit(raw_ostream &OS, bool LineBreakIsNextAfterThis,
609 const MatchTable &Table) const {
610 bool UseLineComment =
611 LineBreakIsNextAfterThis || (Flags & MTRF_LineBreakFollows);
612 if (Flags & (MTRF_JumpTarget | MTRF_CommaFollows))
613 UseLineComment = false;
615 if (Flags & MTRF_Comment)
616 OS << (UseLineComment ? "// " : "/*");
619 if (Flags & MTRF_Label)
620 OS << ": @" << Table.getLabelIndex(LabelID);
622 if ((Flags & MTRF_Comment) && !UseLineComment)
625 if (Flags & MTRF_JumpTarget) {
626 if (Flags & MTRF_Comment)
628 OS << Table.getLabelIndex(LabelID);
631 if (Flags & MTRF_CommaFollows) {
633 if (!LineBreakIsNextAfterThis && !(Flags & MTRF_LineBreakFollows))
637 if (Flags & MTRF_LineBreakFollows)
641 MatchTable &operator<<(MatchTable &Table, const MatchTableRecord &Value) {
642 Table.push_back(Value);
646 //===- Matchers -----------------------------------------------------------===//
648 class OperandMatcher;
650 class PredicateMatcher;
655 virtual ~Matcher() = default;
656 virtual void optimize() {}
657 virtual void emit(MatchTable &Table) = 0;
659 virtual bool hasFirstCondition() const = 0;
660 virtual const PredicateMatcher &getFirstCondition() const = 0;
661 virtual std::unique_ptr<PredicateMatcher> popFirstCondition() = 0;
664 MatchTable MatchTable::buildTable(ArrayRef<Matcher *> Rules,
666 MatchTable Table(WithCoverage);
667 for (Matcher *Rule : Rules)
670 return Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
673 class GroupMatcher final : public Matcher {
674 /// Conditions that form a common prefix of all the matchers contained.
675 SmallVector<std::unique_ptr<PredicateMatcher>, 1> Conditions;
677 /// All the nested matchers, sharing a common prefix.
678 std::vector<Matcher *> Matchers;
680 /// An owning collection for any auxiliary matchers created while optimizing
681 /// nested matchers contained.
682 std::vector<std::unique_ptr<Matcher>> MatcherStorage;
685 /// Add a matcher to the collection of nested matchers if it meets the
686 /// requirements, and return true. If it doesn't, do nothing and return false.
688 /// Expected to preserve its argument, so it could be moved out later on.
689 bool addMatcher(Matcher &Candidate);
691 /// Mark the matcher as fully-built and ensure any invariants expected by both
692 /// optimize() and emit(...) methods. Generally, both sequences of calls
693 /// are expected to lead to a sensible result:
695 /// addMatcher(...)*; finalize(); optimize(); emit(...); and
696 /// addMatcher(...)*; finalize(); emit(...);
700 /// addMatcher(...)*; finalize(); { optimize()*; emit(...); }*
702 /// Multiple calls to optimize() are expected to be handled gracefully, though
703 /// optimize() is not expected to be idempotent. Multiple calls to finalize()
704 /// aren't generally supported. emit(...) is expected to be non-mutating and
705 /// producing the exact same results upon repeated calls.
707 /// addMatcher() calls after the finalize() call are not supported.
709 /// finalize() and optimize() are both allowed to mutate the contained
710 /// matchers, so moving them out after finalize() is not supported.
712 void optimize() override;
713 void emit(MatchTable &Table) override;
715 /// Could be used to move out the matchers added previously, unless finalize()
716 /// has been already called. If any of the matchers are moved out, the group
717 /// becomes safe to destroy, but not safe to re-use for anything else.
718 iterator_range<std::vector<Matcher *>::iterator> matchers() {
719 return make_range(Matchers.begin(), Matchers.end());
721 size_t size() const { return Matchers.size(); }
722 bool empty() const { return Matchers.empty(); }
724 std::unique_ptr<PredicateMatcher> popFirstCondition() override {
725 assert(!Conditions.empty() &&
726 "Trying to pop a condition from a condition-less group");
727 std::unique_ptr<PredicateMatcher> P = std::move(Conditions.front());
728 Conditions.erase(Conditions.begin());
731 const PredicateMatcher &getFirstCondition() const override {
732 assert(!Conditions.empty() &&
733 "Trying to get a condition from a condition-less group");
734 return *Conditions.front();
736 bool hasFirstCondition() const override { return !Conditions.empty(); }
739 /// See if a candidate matcher could be added to this group solely by
740 /// analyzing its first condition.
741 bool candidateConditionMatches(const PredicateMatcher &Predicate) const;
744 class SwitchMatcher : public Matcher {
745 /// All the nested matchers, representing distinct switch-cases. The first
746 /// conditions (as Matcher::getFirstCondition() reports) of all the nested
747 /// matchers must share the same type and path to a value they check, in other
748 /// words, be isIdenticalDownToValue, but have different values they check
750 std::vector<Matcher *> Matchers;
752 /// The representative condition, with a type and a path (InsnVarID and OpIdx
753 /// in most cases) shared by all the matchers contained.
754 std::unique_ptr<PredicateMatcher> Condition = nullptr;
756 /// Temporary set used to check that the case values don't repeat within the
758 std::set<MatchTableRecord> Values;
760 /// An owning collection for any auxiliary matchers created while optimizing
761 /// nested matchers contained.
762 std::vector<std::unique_ptr<Matcher>> MatcherStorage;
765 bool addMatcher(Matcher &Candidate);
768 void emit(MatchTable &Table) override;
770 iterator_range<std::vector<Matcher *>::iterator> matchers() {
771 return make_range(Matchers.begin(), Matchers.end());
773 size_t size() const { return Matchers.size(); }
774 bool empty() const { return Matchers.empty(); }
776 std::unique_ptr<PredicateMatcher> popFirstCondition() override {
777 // SwitchMatcher doesn't have a common first condition for its cases, as all
778 // the cases only share a kind of a value (a type and a path to it) they
779 // match, but deliberately differ in the actual value they match.
780 llvm_unreachable("Trying to pop a condition from a condition-less group");
782 const PredicateMatcher &getFirstCondition() const override {
783 llvm_unreachable("Trying to pop a condition from a condition-less group");
785 bool hasFirstCondition() const override { return false; }
788 /// See if the predicate type has a Switch-implementation for it.
789 static bool isSupportedPredicateType(const PredicateMatcher &Predicate);
791 bool candidateConditionMatches(const PredicateMatcher &Predicate) const;
794 static void emitPredicateSpecificOpcodes(const PredicateMatcher &P,
798 /// Generates code to check that a match rule matches.
799 class RuleMatcher : public Matcher {
801 using ActionList = std::list<std::unique_ptr<MatchAction>>;
802 using action_iterator = ActionList::iterator;
805 /// A list of matchers that all need to succeed for the current rule to match.
806 /// FIXME: This currently supports a single match position but could be
807 /// extended to support multiple positions to support div/rem fusion or
808 /// load-multiple instructions.
809 using MatchersTy = std::vector<std::unique_ptr<InstructionMatcher>> ;
812 /// A list of actions that need to be taken when all predicates in this rule
816 using DefinedInsnVariablesMap = std::map<InstructionMatcher *, unsigned>;
818 /// A map of instruction matchers to the local variables
819 DefinedInsnVariablesMap InsnVariableIDs;
821 using MutatableInsnSet = SmallPtrSet<InstructionMatcher *, 4>;
823 // The set of instruction matchers that have not yet been claimed for mutation
825 MutatableInsnSet MutatableInsns;
827 /// A map of named operands defined by the matchers that may be referenced by
829 StringMap<OperandMatcher *> DefinedOperands;
831 /// A map of anonymous physical register operands defined by the matchers that
832 /// may be referenced by the renderers.
833 DenseMap<Record *, OperandMatcher *> PhysRegOperands;
835 /// ID for the next instruction variable defined with implicitlyDefineInsnVar()
836 unsigned NextInsnVarID;
838 /// ID for the next output instruction allocated with allocateOutputInsnID()
839 unsigned NextOutputInsnID;
841 /// ID for the next temporary register ID allocated with allocateTempRegID()
842 unsigned NextTempRegID;
844 std::vector<Record *> RequiredFeatures;
845 std::vector<std::unique_ptr<PredicateMatcher>> EpilogueMatchers;
847 ArrayRef<SMLoc> SrcLoc;
849 typedef std::tuple<Record *, unsigned, unsigned>
850 DefinedComplexPatternSubOperand;
851 typedef StringMap<DefinedComplexPatternSubOperand>
852 DefinedComplexPatternSubOperandMap;
853 /// A map of Symbolic Names to ComplexPattern sub-operands.
854 DefinedComplexPatternSubOperandMap ComplexSubOperands;
857 static uint64_t NextRuleID;
860 RuleMatcher(ArrayRef<SMLoc> SrcLoc)
861 : Matchers(), Actions(), InsnVariableIDs(), MutatableInsns(),
862 DefinedOperands(), NextInsnVarID(0), NextOutputInsnID(0),
863 NextTempRegID(0), SrcLoc(SrcLoc), ComplexSubOperands(),
864 RuleID(NextRuleID++) {}
865 RuleMatcher(RuleMatcher &&Other) = default;
866 RuleMatcher &operator=(RuleMatcher &&Other) = default;
868 uint64_t getRuleID() const { return RuleID; }
870 InstructionMatcher &addInstructionMatcher(StringRef SymbolicName);
871 void addRequiredFeature(Record *Feature);
872 const std::vector<Record *> &getRequiredFeatures() const;
874 template <class Kind, class... Args> Kind &addAction(Args &&... args);
875 template <class Kind, class... Args>
876 action_iterator insertAction(action_iterator InsertPt, Args &&... args);
878 /// Define an instruction without emitting any code to do so.
879 unsigned implicitlyDefineInsnVar(InstructionMatcher &Matcher);
881 unsigned getInsnVarID(InstructionMatcher &InsnMatcher) const;
882 DefinedInsnVariablesMap::const_iterator defined_insn_vars_begin() const {
883 return InsnVariableIDs.begin();
885 DefinedInsnVariablesMap::const_iterator defined_insn_vars_end() const {
886 return InsnVariableIDs.end();
888 iterator_range<typename DefinedInsnVariablesMap::const_iterator>
889 defined_insn_vars() const {
890 return make_range(defined_insn_vars_begin(), defined_insn_vars_end());
893 MutatableInsnSet::const_iterator mutatable_insns_begin() const {
894 return MutatableInsns.begin();
896 MutatableInsnSet::const_iterator mutatable_insns_end() const {
897 return MutatableInsns.end();
899 iterator_range<typename MutatableInsnSet::const_iterator>
900 mutatable_insns() const {
901 return make_range(mutatable_insns_begin(), mutatable_insns_end());
903 void reserveInsnMatcherForMutation(InstructionMatcher *InsnMatcher) {
904 bool R = MutatableInsns.erase(InsnMatcher);
905 assert(R && "Reserving a mutatable insn that isn't available");
909 action_iterator actions_begin() { return Actions.begin(); }
910 action_iterator actions_end() { return Actions.end(); }
911 iterator_range<action_iterator> actions() {
912 return make_range(actions_begin(), actions_end());
915 void defineOperand(StringRef SymbolicName, OperandMatcher &OM);
917 void definePhysRegOperand(Record *Reg, OperandMatcher &OM);
919 Error defineComplexSubOperand(StringRef SymbolicName, Record *ComplexPattern,
920 unsigned RendererID, unsigned SubOperandID) {
921 if (ComplexSubOperands.count(SymbolicName))
923 "Complex suboperand referenced more than once (Operand: " +
926 ComplexSubOperands[SymbolicName] =
927 std::make_tuple(ComplexPattern, RendererID, SubOperandID);
929 return Error::success();
932 Optional<DefinedComplexPatternSubOperand>
933 getComplexSubOperand(StringRef SymbolicName) const {
934 const auto &I = ComplexSubOperands.find(SymbolicName);
935 if (I == ComplexSubOperands.end())
940 InstructionMatcher &getInstructionMatcher(StringRef SymbolicName) const;
941 const OperandMatcher &getOperandMatcher(StringRef Name) const;
942 const OperandMatcher &getPhysRegOperandMatcher(Record *) const;
944 void optimize() override;
945 void emit(MatchTable &Table) override;
947 /// Compare the priority of this object and B.
949 /// Returns true if this object is more important than B.
950 bool isHigherPriorityThan(const RuleMatcher &B) const;
952 /// Report the maximum number of temporary operands needed by the rule
954 unsigned countRendererFns() const;
956 std::unique_ptr<PredicateMatcher> popFirstCondition() override;
957 const PredicateMatcher &getFirstCondition() const override;
958 LLTCodeGen getFirstConditionAsRootType();
959 bool hasFirstCondition() const override;
960 unsigned getNumOperands() const;
961 StringRef getOpcode() const;
963 // FIXME: Remove this as soon as possible
964 InstructionMatcher &insnmatchers_front() const { return *Matchers.front(); }
966 unsigned allocateOutputInsnID() { return NextOutputInsnID++; }
967 unsigned allocateTempRegID() { return NextTempRegID++; }
969 iterator_range<MatchersTy::iterator> insnmatchers() {
970 return make_range(Matchers.begin(), Matchers.end());
972 bool insnmatchers_empty() const { return Matchers.empty(); }
973 void insnmatchers_pop_front() { Matchers.erase(Matchers.begin()); }
976 uint64_t RuleMatcher::NextRuleID = 0;
978 using action_iterator = RuleMatcher::action_iterator;
980 template <class PredicateTy> class PredicateListMatcher {
982 /// Template instantiations should specialize this to return a string to use
983 /// for the comment emitted when there are no predicates.
984 std::string getNoPredicateComment() const;
987 using PredicatesTy = std::deque<std::unique_ptr<PredicateTy>>;
988 PredicatesTy Predicates;
990 /// Track if the list of predicates was manipulated by one of the optimization
992 bool Optimized = false;
995 /// Construct a new predicate and add it to the matcher.
996 template <class Kind, class... Args>
997 Optional<Kind *> addPredicate(Args &&... args);
999 typename PredicatesTy::iterator predicates_begin() {
1000 return Predicates.begin();
1002 typename PredicatesTy::iterator predicates_end() {
1003 return Predicates.end();
1005 iterator_range<typename PredicatesTy::iterator> predicates() {
1006 return make_range(predicates_begin(), predicates_end());
1008 typename PredicatesTy::size_type predicates_size() const {
1009 return Predicates.size();
1011 bool predicates_empty() const { return Predicates.empty(); }
1013 std::unique_ptr<PredicateTy> predicates_pop_front() {
1014 std::unique_ptr<PredicateTy> Front = std::move(Predicates.front());
1015 Predicates.pop_front();
1020 void prependPredicate(std::unique_ptr<PredicateTy> &&Predicate) {
1021 Predicates.push_front(std::move(Predicate));
1024 void eraseNullPredicates() {
1026 std::stable_partition(Predicates.begin(), Predicates.end(),
1027 std::logical_not<std::unique_ptr<PredicateTy>>());
1028 if (NewEnd != Predicates.begin()) {
1029 Predicates.erase(Predicates.begin(), NewEnd);
1034 /// Emit MatchTable opcodes that tests whether all the predicates are met.
1035 template <class... Args>
1036 void emitPredicateListOpcodes(MatchTable &Table, Args &&... args) {
1037 if (Predicates.empty() && !Optimized) {
1038 Table << MatchTable::Comment(getNoPredicateComment())
1039 << MatchTable::LineBreak;
1043 for (const auto &Predicate : predicates())
1044 Predicate->emitPredicateOpcodes(Table, std::forward<Args>(args)...);
1047 /// Provide a function to avoid emitting certain predicates. This is used to
1048 /// defer some predicate checks until after others
1049 using PredicateFilterFunc = std::function<bool(const PredicateTy&)>;
1051 /// Emit MatchTable opcodes for predicates which satisfy \p
1052 /// ShouldEmitPredicate. This should be called multiple times to ensure all
1053 /// predicates are eventually added to the match table.
1054 template <class... Args>
1055 void emitFilteredPredicateListOpcodes(PredicateFilterFunc ShouldEmitPredicate,
1056 MatchTable &Table, Args &&... args) {
1057 if (Predicates.empty() && !Optimized) {
1058 Table << MatchTable::Comment(getNoPredicateComment())
1059 << MatchTable::LineBreak;
1063 for (const auto &Predicate : predicates()) {
1064 if (ShouldEmitPredicate(*Predicate))
1065 Predicate->emitPredicateOpcodes(Table, std::forward<Args>(args)...);
1070 class PredicateMatcher {
1072 /// This enum is used for RTTI and also defines the priority that is given to
1073 /// the predicate when generating the matcher code. Kinds with higher priority
1074 /// must be tested first.
1076 /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter
1077 /// but OPM_Int must have priority over OPM_RegBank since constant integers
1078 /// are represented by a virtual register defined by a G_CONSTANT instruction.
1080 /// Note: The relative priority between IPM_ and OPM_ does not matter, they
1081 /// are currently not compared between each other.
1082 enum PredicateKind {
1087 IPM_AtomicOrderingMMO,
1089 IPM_MemoryVsLLTSize,
1090 IPM_MemoryAddressSpace,
1091 IPM_MemoryAlignment,
1092 IPM_GenericPredicate,
1112 PredicateMatcher(PredicateKind Kind, unsigned InsnVarID, unsigned OpIdx = ~0)
1113 : Kind(Kind), InsnVarID(InsnVarID), OpIdx(OpIdx) {}
1115 unsigned getInsnVarID() const { return InsnVarID; }
1116 unsigned getOpIdx() const { return OpIdx; }
1118 virtual ~PredicateMatcher() = default;
1119 /// Emit MatchTable opcodes that check the predicate for the given operand.
1120 virtual void emitPredicateOpcodes(MatchTable &Table,
1121 RuleMatcher &Rule) const = 0;
1123 PredicateKind getKind() const { return Kind; }
1125 bool dependsOnOperands() const {
1126 // Custom predicates really depend on the context pattern of the
1127 // instruction, not just the individual instruction. This therefore
1128 // implicitly depends on all other pattern constraints.
1129 return Kind == IPM_GenericPredicate;
1132 virtual bool isIdentical(const PredicateMatcher &B) const {
1133 return B.getKind() == getKind() && InsnVarID == B.InsnVarID &&
1137 virtual bool isIdenticalDownToValue(const PredicateMatcher &B) const {
1138 return hasValue() && PredicateMatcher::isIdentical(B);
1141 virtual MatchTableRecord getValue() const {
1142 assert(hasValue() && "Can not get a value of a value-less predicate!");
1143 llvm_unreachable("Not implemented yet");
1145 virtual bool hasValue() const { return false; }
1147 /// Report the maximum number of temporary operands needed by the predicate
1149 virtual unsigned countRendererFns() const { return 0; }
1152 /// Generates code to check a predicate of an operand.
1154 /// Typical predicates include:
1155 /// * Operand is a particular register.
1156 /// * Operand is assigned a particular register bank.
1157 /// * Operand is an MBB.
1158 class OperandPredicateMatcher : public PredicateMatcher {
1160 OperandPredicateMatcher(PredicateKind Kind, unsigned InsnVarID,
1162 : PredicateMatcher(Kind, InsnVarID, OpIdx) {}
1163 virtual ~OperandPredicateMatcher() {}
1165 /// Compare the priority of this object and B.
1167 /// Returns true if this object is more important than B.
1168 virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const;
1173 PredicateListMatcher<OperandPredicateMatcher>::getNoPredicateComment() const {
1174 return "No operand predicates";
1177 /// Generates code to check that a register operand is defined by the same exact
1179 class SameOperandMatcher : public OperandPredicateMatcher {
1180 std::string MatchingName;
1183 SameOperandMatcher(unsigned InsnVarID, unsigned OpIdx, StringRef MatchingName)
1184 : OperandPredicateMatcher(OPM_SameOperand, InsnVarID, OpIdx),
1185 MatchingName(MatchingName) {}
1187 static bool classof(const PredicateMatcher *P) {
1188 return P->getKind() == OPM_SameOperand;
1191 void emitPredicateOpcodes(MatchTable &Table,
1192 RuleMatcher &Rule) const override;
1194 bool isIdentical(const PredicateMatcher &B) const override {
1195 return OperandPredicateMatcher::isIdentical(B) &&
1196 MatchingName == cast<SameOperandMatcher>(&B)->MatchingName;
1200 /// Generates code to check that an operand is a particular LLT.
1201 class LLTOperandMatcher : public OperandPredicateMatcher {
1206 static std::map<LLTCodeGen, unsigned> TypeIDValues;
1208 static void initTypeIDValuesMap() {
1209 TypeIDValues.clear();
1212 for (const LLTCodeGen &LLTy : KnownTypes)
1213 TypeIDValues[LLTy] = ID++;
1216 LLTOperandMatcher(unsigned InsnVarID, unsigned OpIdx, const LLTCodeGen &Ty)
1217 : OperandPredicateMatcher(OPM_LLT, InsnVarID, OpIdx), Ty(Ty) {
1218 KnownTypes.insert(Ty);
1221 static bool classof(const PredicateMatcher *P) {
1222 return P->getKind() == OPM_LLT;
1224 bool isIdentical(const PredicateMatcher &B) const override {
1225 return OperandPredicateMatcher::isIdentical(B) &&
1226 Ty == cast<LLTOperandMatcher>(&B)->Ty;
1228 MatchTableRecord getValue() const override {
1229 const auto VI = TypeIDValues.find(Ty);
1230 if (VI == TypeIDValues.end())
1231 return MatchTable::NamedValue(getTy().getCxxEnumValue());
1232 return MatchTable::NamedValue(getTy().getCxxEnumValue(), VI->second);
1234 bool hasValue() const override {
1235 if (TypeIDValues.size() != KnownTypes.size())
1236 initTypeIDValuesMap();
1237 return TypeIDValues.count(Ty);
1240 LLTCodeGen getTy() const { return Ty; }
1242 void emitPredicateOpcodes(MatchTable &Table,
1243 RuleMatcher &Rule) const override {
1244 Table << MatchTable::Opcode("GIM_CheckType") << MatchTable::Comment("MI")
1245 << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
1246 << MatchTable::IntValue(OpIdx) << MatchTable::Comment("Type")
1247 << getValue() << MatchTable::LineBreak;
1251 std::map<LLTCodeGen, unsigned> LLTOperandMatcher::TypeIDValues;
1253 /// Generates code to check that an operand is a pointer to any address space.
1255 /// In SelectionDAG, the types did not describe pointers or address spaces. As a
1256 /// result, iN is used to describe a pointer of N bits to any address space and
1257 /// PatFrag predicates are typically used to constrain the address space. There's
1258 /// no reliable means to derive the missing type information from the pattern so
1259 /// imported rules must test the components of a pointer separately.
1261 /// If SizeInBits is zero, then the pointer size will be obtained from the
1263 class PointerToAnyOperandMatcher : public OperandPredicateMatcher {
1265 unsigned SizeInBits;
1268 PointerToAnyOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1269 unsigned SizeInBits)
1270 : OperandPredicateMatcher(OPM_PointerToAny, InsnVarID, OpIdx),
1271 SizeInBits(SizeInBits) {}
1273 static bool classof(const OperandPredicateMatcher *P) {
1274 return P->getKind() == OPM_PointerToAny;
1277 void emitPredicateOpcodes(MatchTable &Table,
1278 RuleMatcher &Rule) const override {
1279 Table << MatchTable::Opcode("GIM_CheckPointerToAny")
1280 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1281 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1282 << MatchTable::Comment("SizeInBits")
1283 << MatchTable::IntValue(SizeInBits) << MatchTable::LineBreak;
1287 /// Generates code to check that an operand is a particular target constant.
1288 class ComplexPatternOperandMatcher : public OperandPredicateMatcher {
1290 const OperandMatcher &Operand;
1291 const Record &TheDef;
1293 unsigned getAllocatedTemporariesBaseID() const;
1296 bool isIdentical(const PredicateMatcher &B) const override { return false; }
1298 ComplexPatternOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1299 const OperandMatcher &Operand,
1300 const Record &TheDef)
1301 : OperandPredicateMatcher(OPM_ComplexPattern, InsnVarID, OpIdx),
1302 Operand(Operand), TheDef(TheDef) {}
1304 static bool classof(const PredicateMatcher *P) {
1305 return P->getKind() == OPM_ComplexPattern;
1308 void emitPredicateOpcodes(MatchTable &Table,
1309 RuleMatcher &Rule) const override {
1310 unsigned ID = getAllocatedTemporariesBaseID();
1311 Table << MatchTable::Opcode("GIM_CheckComplexPattern")
1312 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1313 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1314 << MatchTable::Comment("Renderer") << MatchTable::IntValue(ID)
1315 << MatchTable::NamedValue(("GICP_" + TheDef.getName()).str())
1316 << MatchTable::LineBreak;
1319 unsigned countRendererFns() const override {
1324 /// Generates code to check that an operand is in a particular register bank.
1325 class RegisterBankOperandMatcher : public OperandPredicateMatcher {
1327 const CodeGenRegisterClass &RC;
1330 RegisterBankOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1331 const CodeGenRegisterClass &RC)
1332 : OperandPredicateMatcher(OPM_RegBank, InsnVarID, OpIdx), RC(RC) {}
1334 bool isIdentical(const PredicateMatcher &B) const override {
1335 return OperandPredicateMatcher::isIdentical(B) &&
1336 RC.getDef() == cast<RegisterBankOperandMatcher>(&B)->RC.getDef();
1339 static bool classof(const PredicateMatcher *P) {
1340 return P->getKind() == OPM_RegBank;
1343 void emitPredicateOpcodes(MatchTable &Table,
1344 RuleMatcher &Rule) const override {
1345 Table << MatchTable::Opcode("GIM_CheckRegBankForClass")
1346 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1347 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1348 << MatchTable::Comment("RC")
1349 << MatchTable::NamedValue(RC.getQualifiedName() + "RegClassID")
1350 << MatchTable::LineBreak;
1354 /// Generates code to check that an operand is a basic block.
1355 class MBBOperandMatcher : public OperandPredicateMatcher {
1357 MBBOperandMatcher(unsigned InsnVarID, unsigned OpIdx)
1358 : OperandPredicateMatcher(OPM_MBB, InsnVarID, OpIdx) {}
1360 static bool classof(const PredicateMatcher *P) {
1361 return P->getKind() == OPM_MBB;
1364 void emitPredicateOpcodes(MatchTable &Table,
1365 RuleMatcher &Rule) const override {
1366 Table << MatchTable::Opcode("GIM_CheckIsMBB") << MatchTable::Comment("MI")
1367 << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
1368 << MatchTable::IntValue(OpIdx) << MatchTable::LineBreak;
1372 class ImmOperandMatcher : public OperandPredicateMatcher {
1374 ImmOperandMatcher(unsigned InsnVarID, unsigned OpIdx)
1375 : OperandPredicateMatcher(IPM_Imm, InsnVarID, OpIdx) {}
1377 static bool classof(const PredicateMatcher *P) {
1378 return P->getKind() == IPM_Imm;
1381 void emitPredicateOpcodes(MatchTable &Table,
1382 RuleMatcher &Rule) const override {
1383 Table << MatchTable::Opcode("GIM_CheckIsImm") << MatchTable::Comment("MI")
1384 << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
1385 << MatchTable::IntValue(OpIdx) << MatchTable::LineBreak;
1389 /// Generates code to check that an operand is a G_CONSTANT with a particular
1391 class ConstantIntOperandMatcher : public OperandPredicateMatcher {
1396 ConstantIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value)
1397 : OperandPredicateMatcher(OPM_Int, InsnVarID, OpIdx), Value(Value) {}
1399 bool isIdentical(const PredicateMatcher &B) const override {
1400 return OperandPredicateMatcher::isIdentical(B) &&
1401 Value == cast<ConstantIntOperandMatcher>(&B)->Value;
1404 static bool classof(const PredicateMatcher *P) {
1405 return P->getKind() == OPM_Int;
1408 void emitPredicateOpcodes(MatchTable &Table,
1409 RuleMatcher &Rule) const override {
1410 Table << MatchTable::Opcode("GIM_CheckConstantInt")
1411 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1412 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1413 << MatchTable::IntValue(Value) << MatchTable::LineBreak;
1417 /// Generates code to check that an operand is a raw int (where MO.isImm() or
1418 /// MO.isCImm() is true).
1419 class LiteralIntOperandMatcher : public OperandPredicateMatcher {
1424 LiteralIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value)
1425 : OperandPredicateMatcher(OPM_LiteralInt, InsnVarID, OpIdx),
1428 bool isIdentical(const PredicateMatcher &B) const override {
1429 return OperandPredicateMatcher::isIdentical(B) &&
1430 Value == cast<LiteralIntOperandMatcher>(&B)->Value;
1433 static bool classof(const PredicateMatcher *P) {
1434 return P->getKind() == OPM_LiteralInt;
1437 void emitPredicateOpcodes(MatchTable &Table,
1438 RuleMatcher &Rule) const override {
1439 Table << MatchTable::Opcode("GIM_CheckLiteralInt")
1440 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1441 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1442 << MatchTable::IntValue(Value) << MatchTable::LineBreak;
1446 /// Generates code to check that an operand is an CmpInst predicate
1447 class CmpPredicateOperandMatcher : public OperandPredicateMatcher {
1449 std::string PredName;
1452 CmpPredicateOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1454 : OperandPredicateMatcher(OPM_CmpPredicate, InsnVarID, OpIdx), PredName(P) {}
1456 bool isIdentical(const PredicateMatcher &B) const override {
1457 return OperandPredicateMatcher::isIdentical(B) &&
1458 PredName == cast<CmpPredicateOperandMatcher>(&B)->PredName;
1461 static bool classof(const PredicateMatcher *P) {
1462 return P->getKind() == OPM_CmpPredicate;
1465 void emitPredicateOpcodes(MatchTable &Table,
1466 RuleMatcher &Rule) const override {
1467 Table << MatchTable::Opcode("GIM_CheckCmpPredicate")
1468 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1469 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1470 << MatchTable::Comment("Predicate")
1471 << MatchTable::NamedValue("CmpInst", PredName)
1472 << MatchTable::LineBreak;
1476 /// Generates code to check that an operand is an intrinsic ID.
1477 class IntrinsicIDOperandMatcher : public OperandPredicateMatcher {
1479 const CodeGenIntrinsic *II;
1482 IntrinsicIDOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1483 const CodeGenIntrinsic *II)
1484 : OperandPredicateMatcher(OPM_IntrinsicID, InsnVarID, OpIdx), II(II) {}
1486 bool isIdentical(const PredicateMatcher &B) const override {
1487 return OperandPredicateMatcher::isIdentical(B) &&
1488 II == cast<IntrinsicIDOperandMatcher>(&B)->II;
1491 static bool classof(const PredicateMatcher *P) {
1492 return P->getKind() == OPM_IntrinsicID;
1495 void emitPredicateOpcodes(MatchTable &Table,
1496 RuleMatcher &Rule) const override {
1497 Table << MatchTable::Opcode("GIM_CheckIntrinsicID")
1498 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1499 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1500 << MatchTable::NamedValue("Intrinsic::" + II->EnumName)
1501 << MatchTable::LineBreak;
1505 /// Generates code to check that a set of predicates match for a particular
1507 class OperandMatcher : public PredicateListMatcher<OperandPredicateMatcher> {
1509 InstructionMatcher &Insn;
1511 std::string SymbolicName;
1513 /// The index of the first temporary variable allocated to this operand. The
1514 /// number of allocated temporaries can be found with
1515 /// countRendererFns().
1516 unsigned AllocatedTemporariesBaseID;
1519 OperandMatcher(InstructionMatcher &Insn, unsigned OpIdx,
1520 const std::string &SymbolicName,
1521 unsigned AllocatedTemporariesBaseID)
1522 : Insn(Insn), OpIdx(OpIdx), SymbolicName(SymbolicName),
1523 AllocatedTemporariesBaseID(AllocatedTemporariesBaseID) {}
1525 bool hasSymbolicName() const { return !SymbolicName.empty(); }
1526 const StringRef getSymbolicName() const { return SymbolicName; }
1527 void setSymbolicName(StringRef Name) {
1528 assert(SymbolicName.empty() && "Operand already has a symbolic name");
1529 SymbolicName = std::string(Name);
1532 /// Construct a new operand predicate and add it to the matcher.
1533 template <class Kind, class... Args>
1534 Optional<Kind *> addPredicate(Args &&... args) {
1535 if (isSameAsAnotherOperand())
1537 Predicates.emplace_back(std::make_unique<Kind>(
1538 getInsnVarID(), getOpIdx(), std::forward<Args>(args)...));
1539 return static_cast<Kind *>(Predicates.back().get());
1542 unsigned getOpIdx() const { return OpIdx; }
1543 unsigned getInsnVarID() const;
1545 std::string getOperandExpr(unsigned InsnVarID) const {
1546 return "State.MIs[" + llvm::to_string(InsnVarID) + "]->getOperand(" +
1547 llvm::to_string(OpIdx) + ")";
1550 InstructionMatcher &getInstructionMatcher() const { return Insn; }
1552 Error addTypeCheckPredicate(const TypeSetByHwMode &VTy,
1553 bool OperandIsAPointer);
1555 /// Emit MatchTable opcodes that test whether the instruction named in
1556 /// InsnVarID matches all the predicates and all the operands.
1557 void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) {
1559 std::string Comment;
1560 raw_string_ostream CommentOS(Comment);
1561 CommentOS << "MIs[" << getInsnVarID() << "] ";
1562 if (SymbolicName.empty())
1563 CommentOS << "Operand " << OpIdx;
1565 CommentOS << SymbolicName;
1566 Table << MatchTable::Comment(CommentOS.str()) << MatchTable::LineBreak;
1569 emitPredicateListOpcodes(Table, Rule);
1572 /// Compare the priority of this object and B.
1574 /// Returns true if this object is more important than B.
1575 bool isHigherPriorityThan(OperandMatcher &B) {
1576 // Operand matchers involving more predicates have higher priority.
1577 if (predicates_size() > B.predicates_size())
1579 if (predicates_size() < B.predicates_size())
1582 // This assumes that predicates are added in a consistent order.
1583 for (auto &&Predicate : zip(predicates(), B.predicates())) {
1584 if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate)))
1586 if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate)))
1593 /// Report the maximum number of temporary operands needed by the operand
1595 unsigned countRendererFns() {
1596 return std::accumulate(
1597 predicates().begin(), predicates().end(), 0,
1599 const std::unique_ptr<OperandPredicateMatcher> &Predicate) {
1600 return A + Predicate->countRendererFns();
1604 unsigned getAllocatedTemporariesBaseID() const {
1605 return AllocatedTemporariesBaseID;
1608 bool isSameAsAnotherOperand() {
1609 for (const auto &Predicate : predicates())
1610 if (isa<SameOperandMatcher>(Predicate))
1616 Error OperandMatcher::addTypeCheckPredicate(const TypeSetByHwMode &VTy,
1617 bool OperandIsAPointer) {
1618 if (!VTy.isMachineValueType())
1619 return failedImport("unsupported typeset");
1621 if (VTy.getMachineValueType() == MVT::iPTR && OperandIsAPointer) {
1622 addPredicate<PointerToAnyOperandMatcher>(0);
1623 return Error::success();
1626 auto OpTyOrNone = MVTToLLT(VTy.getMachineValueType().SimpleTy);
1628 return failedImport("unsupported type");
1630 if (OperandIsAPointer)
1631 addPredicate<PointerToAnyOperandMatcher>(OpTyOrNone->get().getSizeInBits());
1632 else if (VTy.isPointer())
1633 addPredicate<LLTOperandMatcher>(LLT::pointer(VTy.getPtrAddrSpace(),
1634 OpTyOrNone->get().getSizeInBits()));
1636 addPredicate<LLTOperandMatcher>(*OpTyOrNone);
1637 return Error::success();
1640 unsigned ComplexPatternOperandMatcher::getAllocatedTemporariesBaseID() const {
1641 return Operand.getAllocatedTemporariesBaseID();
1644 /// Generates code to check a predicate on an instruction.
1646 /// Typical predicates include:
1647 /// * The opcode of the instruction is a particular value.
1648 /// * The nsw/nuw flag is/isn't set.
1649 class InstructionPredicateMatcher : public PredicateMatcher {
1651 InstructionPredicateMatcher(PredicateKind Kind, unsigned InsnVarID)
1652 : PredicateMatcher(Kind, InsnVarID) {}
1653 virtual ~InstructionPredicateMatcher() {}
1655 /// Compare the priority of this object and B.
1657 /// Returns true if this object is more important than B.
1659 isHigherPriorityThan(const InstructionPredicateMatcher &B) const {
1660 return Kind < B.Kind;
1666 PredicateListMatcher<PredicateMatcher>::getNoPredicateComment() const {
1667 return "No instruction predicates";
1670 /// Generates code to check the opcode of an instruction.
1671 class InstructionOpcodeMatcher : public InstructionPredicateMatcher {
1673 const CodeGenInstruction *I;
1675 static DenseMap<const CodeGenInstruction *, unsigned> OpcodeValues;
1678 static void initOpcodeValuesMap(const CodeGenTarget &Target) {
1679 OpcodeValues.clear();
1681 unsigned OpcodeValue = 0;
1682 for (const CodeGenInstruction *I : Target.getInstructionsByEnumValue())
1683 OpcodeValues[I] = OpcodeValue++;
1686 InstructionOpcodeMatcher(unsigned InsnVarID, const CodeGenInstruction *I)
1687 : InstructionPredicateMatcher(IPM_Opcode, InsnVarID), I(I) {}
1689 static bool classof(const PredicateMatcher *P) {
1690 return P->getKind() == IPM_Opcode;
1693 bool isIdentical(const PredicateMatcher &B) const override {
1694 return InstructionPredicateMatcher::isIdentical(B) &&
1695 I == cast<InstructionOpcodeMatcher>(&B)->I;
1697 MatchTableRecord getValue() const override {
1698 const auto VI = OpcodeValues.find(I);
1699 if (VI != OpcodeValues.end())
1700 return MatchTable::NamedValue(I->Namespace, I->TheDef->getName(),
1702 return MatchTable::NamedValue(I->Namespace, I->TheDef->getName());
1704 bool hasValue() const override { return OpcodeValues.count(I); }
1706 void emitPredicateOpcodes(MatchTable &Table,
1707 RuleMatcher &Rule) const override {
1708 Table << MatchTable::Opcode("GIM_CheckOpcode") << MatchTable::Comment("MI")
1709 << MatchTable::IntValue(InsnVarID) << getValue()
1710 << MatchTable::LineBreak;
1713 /// Compare the priority of this object and B.
1715 /// Returns true if this object is more important than B.
1717 isHigherPriorityThan(const InstructionPredicateMatcher &B) const override {
1718 if (InstructionPredicateMatcher::isHigherPriorityThan(B))
1720 if (B.InstructionPredicateMatcher::isHigherPriorityThan(*this))
1723 // Prioritize opcodes for cosmetic reasons in the generated source. Although
1724 // this is cosmetic at the moment, we may want to drive a similar ordering
1725 // using instruction frequency information to improve compile time.
1726 if (const InstructionOpcodeMatcher *BO =
1727 dyn_cast<InstructionOpcodeMatcher>(&B))
1728 return I->TheDef->getName() < BO->I->TheDef->getName();
1733 bool isConstantInstruction() const {
1734 return I->TheDef->getName() == "G_CONSTANT";
1737 StringRef getOpcode() const { return I->TheDef->getName(); }
1738 bool isVariadicNumOperands() const { return I->Operands.isVariadic; }
1740 StringRef getOperandType(unsigned OpIdx) const {
1741 return I->Operands[OpIdx].OperandType;
1745 DenseMap<const CodeGenInstruction *, unsigned>
1746 InstructionOpcodeMatcher::OpcodeValues;
1748 class InstructionNumOperandsMatcher final : public InstructionPredicateMatcher {
1749 unsigned NumOperands = 0;
1752 InstructionNumOperandsMatcher(unsigned InsnVarID, unsigned NumOperands)
1753 : InstructionPredicateMatcher(IPM_NumOperands, InsnVarID),
1754 NumOperands(NumOperands) {}
1756 static bool classof(const PredicateMatcher *P) {
1757 return P->getKind() == IPM_NumOperands;
1760 bool isIdentical(const PredicateMatcher &B) const override {
1761 return InstructionPredicateMatcher::isIdentical(B) &&
1762 NumOperands == cast<InstructionNumOperandsMatcher>(&B)->NumOperands;
1765 void emitPredicateOpcodes(MatchTable &Table,
1766 RuleMatcher &Rule) const override {
1767 Table << MatchTable::Opcode("GIM_CheckNumOperands")
1768 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1769 << MatchTable::Comment("Expected")
1770 << MatchTable::IntValue(NumOperands) << MatchTable::LineBreak;
1774 /// Generates code to check that this instruction is a constant whose value
1775 /// meets an immediate predicate.
1777 /// Immediates are slightly odd since they are typically used like an operand
1778 /// but are represented as an operator internally. We typically write simm8:$src
1779 /// in a tablegen pattern, but this is just syntactic sugar for
1780 /// (imm:i32)<<P:Predicate_simm8>>:$imm which more directly describes the nodes
1781 /// that will be matched and the predicate (which is attached to the imm
1782 /// operator) that will be tested. In SelectionDAG this describes a
1783 /// ConstantSDNode whose internal value will be tested using the simm8 predicate.
1785 /// The corresponding GlobalISel representation is %1 = G_CONSTANT iN Value. In
1786 /// this representation, the immediate could be tested with an
1787 /// InstructionMatcher, InstructionOpcodeMatcher, OperandMatcher, and a
1788 /// OperandPredicateMatcher-subclass to check the Value meets the predicate but
1789 /// there are two implementation issues with producing that matcher
1790 /// configuration from the SelectionDAG pattern:
1791 /// * ImmLeaf is a PatFrag whose root is an InstructionMatcher. This means that
1792 /// were we to sink the immediate predicate to the operand we would have to
1793 /// have two partial implementations of PatFrag support, one for immediates
1794 /// and one for non-immediates.
1795 /// * At the point we handle the predicate, the OperandMatcher hasn't been
1796 /// created yet. If we were to sink the predicate to the OperandMatcher we
1797 /// would also have to complicate (or duplicate) the code that descends and
1798 /// creates matchers for the subtree.
1799 /// Overall, it's simpler to handle it in the place it was found.
1800 class InstructionImmPredicateMatcher : public InstructionPredicateMatcher {
1802 TreePredicateFn Predicate;
1805 InstructionImmPredicateMatcher(unsigned InsnVarID,
1806 const TreePredicateFn &Predicate)
1807 : InstructionPredicateMatcher(IPM_ImmPredicate, InsnVarID),
1808 Predicate(Predicate) {}
1810 bool isIdentical(const PredicateMatcher &B) const override {
1811 return InstructionPredicateMatcher::isIdentical(B) &&
1812 Predicate.getOrigPatFragRecord() ==
1813 cast<InstructionImmPredicateMatcher>(&B)
1814 ->Predicate.getOrigPatFragRecord();
1817 static bool classof(const PredicateMatcher *P) {
1818 return P->getKind() == IPM_ImmPredicate;
1821 void emitPredicateOpcodes(MatchTable &Table,
1822 RuleMatcher &Rule) const override {
1823 Table << MatchTable::Opcode(getMatchOpcodeForPredicate(Predicate))
1824 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1825 << MatchTable::Comment("Predicate")
1826 << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
1827 << MatchTable::LineBreak;
1831 /// Generates code to check that a memory instruction has a atomic ordering
1832 /// MachineMemoryOperand.
1833 class AtomicOrderingMMOPredicateMatcher : public InstructionPredicateMatcher {
1843 AOComparator Comparator;
1846 AtomicOrderingMMOPredicateMatcher(unsigned InsnVarID, StringRef Order,
1847 AOComparator Comparator = AO_Exactly)
1848 : InstructionPredicateMatcher(IPM_AtomicOrderingMMO, InsnVarID),
1849 Order(Order), Comparator(Comparator) {}
1851 static bool classof(const PredicateMatcher *P) {
1852 return P->getKind() == IPM_AtomicOrderingMMO;
1855 bool isIdentical(const PredicateMatcher &B) const override {
1856 if (!InstructionPredicateMatcher::isIdentical(B))
1858 const auto &R = *cast<AtomicOrderingMMOPredicateMatcher>(&B);
1859 return Order == R.Order && Comparator == R.Comparator;
1862 void emitPredicateOpcodes(MatchTable &Table,
1863 RuleMatcher &Rule) const override {
1864 StringRef Opcode = "GIM_CheckAtomicOrdering";
1866 if (Comparator == AO_OrStronger)
1867 Opcode = "GIM_CheckAtomicOrderingOrStrongerThan";
1868 if (Comparator == AO_WeakerThan)
1869 Opcode = "GIM_CheckAtomicOrderingWeakerThan";
1871 Table << MatchTable::Opcode(Opcode) << MatchTable::Comment("MI")
1872 << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Order")
1873 << MatchTable::NamedValue(("(int64_t)AtomicOrdering::" + Order).str())
1874 << MatchTable::LineBreak;
1878 /// Generates code to check that the size of an MMO is exactly N bytes.
1879 class MemorySizePredicateMatcher : public InstructionPredicateMatcher {
1885 MemorySizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, unsigned Size)
1886 : InstructionPredicateMatcher(IPM_MemoryLLTSize, InsnVarID),
1887 MMOIdx(MMOIdx), Size(Size) {}
1889 static bool classof(const PredicateMatcher *P) {
1890 return P->getKind() == IPM_MemoryLLTSize;
1892 bool isIdentical(const PredicateMatcher &B) const override {
1893 return InstructionPredicateMatcher::isIdentical(B) &&
1894 MMOIdx == cast<MemorySizePredicateMatcher>(&B)->MMOIdx &&
1895 Size == cast<MemorySizePredicateMatcher>(&B)->Size;
1898 void emitPredicateOpcodes(MatchTable &Table,
1899 RuleMatcher &Rule) const override {
1900 Table << MatchTable::Opcode("GIM_CheckMemorySizeEqualTo")
1901 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1902 << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
1903 << MatchTable::Comment("Size") << MatchTable::IntValue(Size)
1904 << MatchTable::LineBreak;
1908 class MemoryAddressSpacePredicateMatcher : public InstructionPredicateMatcher {
1911 SmallVector<unsigned, 4> AddrSpaces;
1914 MemoryAddressSpacePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
1915 ArrayRef<unsigned> AddrSpaces)
1916 : InstructionPredicateMatcher(IPM_MemoryAddressSpace, InsnVarID),
1917 MMOIdx(MMOIdx), AddrSpaces(AddrSpaces.begin(), AddrSpaces.end()) {}
1919 static bool classof(const PredicateMatcher *P) {
1920 return P->getKind() == IPM_MemoryAddressSpace;
1922 bool isIdentical(const PredicateMatcher &B) const override {
1923 if (!InstructionPredicateMatcher::isIdentical(B))
1925 auto *Other = cast<MemoryAddressSpacePredicateMatcher>(&B);
1926 return MMOIdx == Other->MMOIdx && AddrSpaces == Other->AddrSpaces;
1929 void emitPredicateOpcodes(MatchTable &Table,
1930 RuleMatcher &Rule) const override {
1931 Table << MatchTable::Opcode("GIM_CheckMemoryAddressSpace")
1932 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1933 << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
1934 // Encode number of address spaces to expect.
1935 << MatchTable::Comment("NumAddrSpace")
1936 << MatchTable::IntValue(AddrSpaces.size());
1937 for (unsigned AS : AddrSpaces)
1938 Table << MatchTable::Comment("AddrSpace") << MatchTable::IntValue(AS);
1940 Table << MatchTable::LineBreak;
1944 class MemoryAlignmentPredicateMatcher : public InstructionPredicateMatcher {
1950 MemoryAlignmentPredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
1952 : InstructionPredicateMatcher(IPM_MemoryAlignment, InsnVarID),
1953 MMOIdx(MMOIdx), MinAlign(MinAlign) {
1954 assert(MinAlign > 0);
1957 static bool classof(const PredicateMatcher *P) {
1958 return P->getKind() == IPM_MemoryAlignment;
1961 bool isIdentical(const PredicateMatcher &B) const override {
1962 if (!InstructionPredicateMatcher::isIdentical(B))
1964 auto *Other = cast<MemoryAlignmentPredicateMatcher>(&B);
1965 return MMOIdx == Other->MMOIdx && MinAlign == Other->MinAlign;
1968 void emitPredicateOpcodes(MatchTable &Table,
1969 RuleMatcher &Rule) const override {
1970 Table << MatchTable::Opcode("GIM_CheckMemoryAlignment")
1971 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1972 << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
1973 << MatchTable::Comment("MinAlign") << MatchTable::IntValue(MinAlign)
1974 << MatchTable::LineBreak;
1978 /// Generates code to check that the size of an MMO is less-than, equal-to, or
1979 /// greater than a given LLT.
1980 class MemoryVsLLTSizePredicateMatcher : public InstructionPredicateMatcher {
1990 RelationKind Relation;
1994 MemoryVsLLTSizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
1995 enum RelationKind Relation,
1997 : InstructionPredicateMatcher(IPM_MemoryVsLLTSize, InsnVarID),
1998 MMOIdx(MMOIdx), Relation(Relation), OpIdx(OpIdx) {}
2000 static bool classof(const PredicateMatcher *P) {
2001 return P->getKind() == IPM_MemoryVsLLTSize;
2003 bool isIdentical(const PredicateMatcher &B) const override {
2004 return InstructionPredicateMatcher::isIdentical(B) &&
2005 MMOIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->MMOIdx &&
2006 Relation == cast<MemoryVsLLTSizePredicateMatcher>(&B)->Relation &&
2007 OpIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->OpIdx;
2010 void emitPredicateOpcodes(MatchTable &Table,
2011 RuleMatcher &Rule) const override {
2012 Table << MatchTable::Opcode(Relation == EqualTo
2013 ? "GIM_CheckMemorySizeEqualToLLT"
2014 : Relation == GreaterThan
2015 ? "GIM_CheckMemorySizeGreaterThanLLT"
2016 : "GIM_CheckMemorySizeLessThanLLT")
2017 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
2018 << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
2019 << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx)
2020 << MatchTable::LineBreak;
2024 /// Generates code to check an arbitrary C++ instruction predicate.
2025 class GenericInstructionPredicateMatcher : public InstructionPredicateMatcher {
2027 TreePredicateFn Predicate;
2030 GenericInstructionPredicateMatcher(unsigned InsnVarID,
2031 TreePredicateFn Predicate)
2032 : InstructionPredicateMatcher(IPM_GenericPredicate, InsnVarID),
2033 Predicate(Predicate) {}
2035 static bool classof(const InstructionPredicateMatcher *P) {
2036 return P->getKind() == IPM_GenericPredicate;
2038 bool isIdentical(const PredicateMatcher &B) const override {
2039 return InstructionPredicateMatcher::isIdentical(B) &&
2041 static_cast<const GenericInstructionPredicateMatcher &>(B)
2044 void emitPredicateOpcodes(MatchTable &Table,
2045 RuleMatcher &Rule) const override {
2046 Table << MatchTable::Opcode("GIM_CheckCxxInsnPredicate")
2047 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
2048 << MatchTable::Comment("FnId")
2049 << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
2050 << MatchTable::LineBreak;
2054 /// Generates code to check that a set of predicates and operands match for a
2055 /// particular instruction.
2057 /// Typical predicates include:
2058 /// * Has a specific opcode.
2059 /// * Has an nsw/nuw flag or doesn't.
2060 class InstructionMatcher final : public PredicateListMatcher<PredicateMatcher> {
2062 typedef std::vector<std::unique_ptr<OperandMatcher>> OperandVec;
2066 /// The operands to match. All rendered operands must be present even if the
2067 /// condition is always true.
2068 OperandVec Operands;
2069 bool NumOperandsCheck = true;
2071 std::string SymbolicName;
2074 /// PhysRegInputs - List list has an entry for each explicitly specified
2075 /// physreg input to the pattern. The first elt is the Register node, the
2076 /// second is the recorded slot number the input pattern match saved it in.
2077 SmallVector<std::pair<Record *, unsigned>, 2> PhysRegInputs;
2080 InstructionMatcher(RuleMatcher &Rule, StringRef SymbolicName)
2081 : Rule(Rule), SymbolicName(SymbolicName) {
2082 // We create a new instruction matcher.
2083 // Get a new ID for that instruction.
2084 InsnVarID = Rule.implicitlyDefineInsnVar(*this);
2087 /// Construct a new instruction predicate and add it to the matcher.
2088 template <class Kind, class... Args>
2089 Optional<Kind *> addPredicate(Args &&... args) {
2090 Predicates.emplace_back(
2091 std::make_unique<Kind>(getInsnVarID(), std::forward<Args>(args)...));
2092 return static_cast<Kind *>(Predicates.back().get());
2095 RuleMatcher &getRuleMatcher() const { return Rule; }
2097 unsigned getInsnVarID() const { return InsnVarID; }
2099 /// Add an operand to the matcher.
2100 OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName,
2101 unsigned AllocatedTemporariesBaseID) {
2102 Operands.emplace_back(new OperandMatcher(*this, OpIdx, SymbolicName,
2103 AllocatedTemporariesBaseID));
2104 if (!SymbolicName.empty())
2105 Rule.defineOperand(SymbolicName, *Operands.back());
2107 return *Operands.back();
2110 OperandMatcher &getOperand(unsigned OpIdx) {
2111 auto I = std::find_if(Operands.begin(), Operands.end(),
2112 [&OpIdx](const std::unique_ptr<OperandMatcher> &X) {
2113 return X->getOpIdx() == OpIdx;
2115 if (I != Operands.end())
2117 llvm_unreachable("Failed to lookup operand");
2120 OperandMatcher &addPhysRegInput(Record *Reg, unsigned OpIdx,
2121 unsigned TempOpIdx) {
2122 assert(SymbolicName.empty());
2123 OperandMatcher *OM = new OperandMatcher(*this, OpIdx, "", TempOpIdx);
2124 Operands.emplace_back(OM);
2125 Rule.definePhysRegOperand(Reg, *OM);
2126 PhysRegInputs.emplace_back(Reg, OpIdx);
2130 ArrayRef<std::pair<Record *, unsigned>> getPhysRegInputs() const {
2131 return PhysRegInputs;
2134 StringRef getSymbolicName() const { return SymbolicName; }
2135 unsigned getNumOperands() const { return Operands.size(); }
2136 OperandVec::iterator operands_begin() { return Operands.begin(); }
2137 OperandVec::iterator operands_end() { return Operands.end(); }
2138 iterator_range<OperandVec::iterator> operands() {
2139 return make_range(operands_begin(), operands_end());
2141 OperandVec::const_iterator operands_begin() const { return Operands.begin(); }
2142 OperandVec::const_iterator operands_end() const { return Operands.end(); }
2143 iterator_range<OperandVec::const_iterator> operands() const {
2144 return make_range(operands_begin(), operands_end());
2146 bool operands_empty() const { return Operands.empty(); }
2148 void pop_front() { Operands.erase(Operands.begin()); }
2152 /// Emit MatchTable opcodes that test whether the instruction named in
2153 /// InsnVarName matches all the predicates and all the operands.
2154 void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) {
2155 if (NumOperandsCheck)
2156 InstructionNumOperandsMatcher(InsnVarID, getNumOperands())
2157 .emitPredicateOpcodes(Table, Rule);
2159 // First emit all instruction level predicates need to be verified before we
2160 // can verify operands.
2161 emitFilteredPredicateListOpcodes(
2162 [](const PredicateMatcher &P) {
2163 return !P.dependsOnOperands();
2166 // Emit all operand constraints.
2167 for (const auto &Operand : Operands)
2168 Operand->emitPredicateOpcodes(Table, Rule);
2170 // All of the tablegen defined predicates should now be matched. Now emit
2171 // any custom predicates that rely on all generated checks.
2172 emitFilteredPredicateListOpcodes(
2173 [](const PredicateMatcher &P) {
2174 return P.dependsOnOperands();
2178 /// Compare the priority of this object and B.
2180 /// Returns true if this object is more important than B.
2181 bool isHigherPriorityThan(InstructionMatcher &B) {
2182 // Instruction matchers involving more operands have higher priority.
2183 if (Operands.size() > B.Operands.size())
2185 if (Operands.size() < B.Operands.size())
2188 for (auto &&P : zip(predicates(), B.predicates())) {
2189 auto L = static_cast<InstructionPredicateMatcher *>(std::get<0>(P).get());
2190 auto R = static_cast<InstructionPredicateMatcher *>(std::get<1>(P).get());
2191 if (L->isHigherPriorityThan(*R))
2193 if (R->isHigherPriorityThan(*L))
2197 for (auto Operand : zip(Operands, B.Operands)) {
2198 if (std::get<0>(Operand)->isHigherPriorityThan(*std::get<1>(Operand)))
2200 if (std::get<1>(Operand)->isHigherPriorityThan(*std::get<0>(Operand)))
2207 /// Report the maximum number of temporary operands needed by the instruction
2209 unsigned countRendererFns() {
2210 return std::accumulate(
2211 predicates().begin(), predicates().end(), 0,
2213 const std::unique_ptr<PredicateMatcher> &Predicate) {
2214 return A + Predicate->countRendererFns();
2217 Operands.begin(), Operands.end(), 0,
2218 [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) {
2219 return A + Operand->countRendererFns();
2223 InstructionOpcodeMatcher &getOpcodeMatcher() {
2224 for (auto &P : predicates())
2225 if (auto *OpMatcher = dyn_cast<InstructionOpcodeMatcher>(P.get()))
2227 llvm_unreachable("Didn't find an opcode matcher");
2230 bool isConstantInstruction() {
2231 return getOpcodeMatcher().isConstantInstruction();
2234 StringRef getOpcode() { return getOpcodeMatcher().getOpcode(); }
2237 StringRef RuleMatcher::getOpcode() const {
2238 return Matchers.front()->getOpcode();
2241 unsigned RuleMatcher::getNumOperands() const {
2242 return Matchers.front()->getNumOperands();
2245 LLTCodeGen RuleMatcher::getFirstConditionAsRootType() {
2246 InstructionMatcher &InsnMatcher = *Matchers.front();
2247 if (!InsnMatcher.predicates_empty())
2248 if (const auto *TM =
2249 dyn_cast<LLTOperandMatcher>(&**InsnMatcher.predicates_begin()))
2250 if (TM->getInsnVarID() == 0 && TM->getOpIdx() == 0)
2255 /// Generates code to check that the operand is a register defined by an
2256 /// instruction that matches the given instruction matcher.
2258 /// For example, the pattern:
2259 /// (set $dst, (G_MUL (G_ADD $src1, $src2), $src3))
2260 /// would use an InstructionOperandMatcher for operand 1 of the G_MUL to match
2262 /// (G_ADD $src1, $src2)
2264 class InstructionOperandMatcher : public OperandPredicateMatcher {
2266 std::unique_ptr<InstructionMatcher> InsnMatcher;
2269 InstructionOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
2270 RuleMatcher &Rule, StringRef SymbolicName)
2271 : OperandPredicateMatcher(OPM_Instruction, InsnVarID, OpIdx),
2272 InsnMatcher(new InstructionMatcher(Rule, SymbolicName)) {}
2274 static bool classof(const PredicateMatcher *P) {
2275 return P->getKind() == OPM_Instruction;
2278 InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; }
2280 void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const {
2281 const unsigned NewInsnVarID = InsnMatcher->getInsnVarID();
2282 Table << MatchTable::Opcode("GIM_RecordInsn")
2283 << MatchTable::Comment("DefineMI")
2284 << MatchTable::IntValue(NewInsnVarID) << MatchTable::Comment("MI")
2285 << MatchTable::IntValue(getInsnVarID())
2286 << MatchTable::Comment("OpIdx") << MatchTable::IntValue(getOpIdx())
2287 << MatchTable::Comment("MIs[" + llvm::to_string(NewInsnVarID) + "]")
2288 << MatchTable::LineBreak;
2291 void emitPredicateOpcodes(MatchTable &Table,
2292 RuleMatcher &Rule) const override {
2293 emitCaptureOpcodes(Table, Rule);
2294 InsnMatcher->emitPredicateOpcodes(Table, Rule);
2297 bool isHigherPriorityThan(const OperandPredicateMatcher &B) const override {
2298 if (OperandPredicateMatcher::isHigherPriorityThan(B))
2300 if (B.OperandPredicateMatcher::isHigherPriorityThan(*this))
2303 if (const InstructionOperandMatcher *BP =
2304 dyn_cast<InstructionOperandMatcher>(&B))
2305 if (InsnMatcher->isHigherPriorityThan(*BP->InsnMatcher))
2311 void InstructionMatcher::optimize() {
2312 SmallVector<std::unique_ptr<PredicateMatcher>, 8> Stash;
2313 const auto &OpcMatcher = getOpcodeMatcher();
2315 Stash.push_back(predicates_pop_front());
2316 if (Stash.back().get() == &OpcMatcher) {
2317 if (NumOperandsCheck && OpcMatcher.isVariadicNumOperands())
2319 new InstructionNumOperandsMatcher(InsnVarID, getNumOperands()));
2320 NumOperandsCheck = false;
2322 for (auto &OM : Operands)
2323 for (auto &OP : OM->predicates())
2324 if (isa<IntrinsicIDOperandMatcher>(OP)) {
2325 Stash.push_back(std::move(OP));
2326 OM->eraseNullPredicates();
2331 if (InsnVarID > 0) {
2332 assert(!Operands.empty() && "Nested instruction is expected to def a vreg");
2333 for (auto &OP : Operands[0]->predicates())
2335 Operands[0]->eraseNullPredicates();
2337 for (auto &OM : Operands) {
2338 for (auto &OP : OM->predicates())
2339 if (isa<LLTOperandMatcher>(OP))
2340 Stash.push_back(std::move(OP));
2341 OM->eraseNullPredicates();
2343 while (!Stash.empty())
2344 prependPredicate(Stash.pop_back_val());
2347 //===- Actions ------------------------------------------------------------===//
2348 class OperandRenderer {
2352 OR_CopyOrAddZeroReg,
2355 OR_CopyConstantAsImm,
2356 OR_CopyFConstantAsFPImm,
2370 OperandRenderer(RendererKind Kind) : Kind(Kind) {}
2371 virtual ~OperandRenderer() {}
2373 RendererKind getKind() const { return Kind; }
2375 virtual void emitRenderOpcodes(MatchTable &Table,
2376 RuleMatcher &Rule) const = 0;
2379 /// A CopyRenderer emits code to copy a single operand from an existing
2380 /// instruction to the one being built.
2381 class CopyRenderer : public OperandRenderer {
2384 /// The name of the operand.
2385 const StringRef SymbolicName;
2388 CopyRenderer(unsigned NewInsnID, StringRef SymbolicName)
2389 : OperandRenderer(OR_Copy), NewInsnID(NewInsnID),
2390 SymbolicName(SymbolicName) {
2391 assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
2394 static bool classof(const OperandRenderer *R) {
2395 return R->getKind() == OR_Copy;
2398 const StringRef getSymbolicName() const { return SymbolicName; }
2400 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2401 const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2402 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2403 Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
2404 << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID")
2405 << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2406 << MatchTable::IntValue(Operand.getOpIdx())
2407 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2411 /// A CopyRenderer emits code to copy a virtual register to a specific physical
2413 class CopyPhysRegRenderer : public OperandRenderer {
2419 CopyPhysRegRenderer(unsigned NewInsnID, Record *Reg)
2420 : OperandRenderer(OR_CopyPhysReg), NewInsnID(NewInsnID),
2425 static bool classof(const OperandRenderer *R) {
2426 return R->getKind() == OR_CopyPhysReg;
2429 Record *getPhysReg() const { return PhysReg; }
2431 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2432 const OperandMatcher &Operand = Rule.getPhysRegOperandMatcher(PhysReg);
2433 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2434 Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
2435 << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID")
2436 << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2437 << MatchTable::IntValue(Operand.getOpIdx())
2438 << MatchTable::Comment(PhysReg->getName())
2439 << MatchTable::LineBreak;
2443 /// A CopyOrAddZeroRegRenderer emits code to copy a single operand from an
2444 /// existing instruction to the one being built. If the operand turns out to be
2445 /// a 'G_CONSTANT 0' then it replaces the operand with a zero register.
2446 class CopyOrAddZeroRegRenderer : public OperandRenderer {
2449 /// The name of the operand.
2450 const StringRef SymbolicName;
2451 const Record *ZeroRegisterDef;
2454 CopyOrAddZeroRegRenderer(unsigned NewInsnID,
2455 StringRef SymbolicName, Record *ZeroRegisterDef)
2456 : OperandRenderer(OR_CopyOrAddZeroReg), NewInsnID(NewInsnID),
2457 SymbolicName(SymbolicName), ZeroRegisterDef(ZeroRegisterDef) {
2458 assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
2461 static bool classof(const OperandRenderer *R) {
2462 return R->getKind() == OR_CopyOrAddZeroReg;
2465 const StringRef getSymbolicName() const { return SymbolicName; }
2467 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2468 const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2469 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2470 Table << MatchTable::Opcode("GIR_CopyOrAddZeroReg")
2471 << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2472 << MatchTable::Comment("OldInsnID")
2473 << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2474 << MatchTable::IntValue(Operand.getOpIdx())
2475 << MatchTable::NamedValue(
2476 (ZeroRegisterDef->getValue("Namespace")
2477 ? ZeroRegisterDef->getValueAsString("Namespace")
2479 ZeroRegisterDef->getName())
2480 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2484 /// A CopyConstantAsImmRenderer emits code to render a G_CONSTANT instruction to
2485 /// an extended immediate operand.
2486 class CopyConstantAsImmRenderer : public OperandRenderer {
2489 /// The name of the operand.
2490 const std::string SymbolicName;
2494 CopyConstantAsImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
2495 : OperandRenderer(OR_CopyConstantAsImm), NewInsnID(NewInsnID),
2496 SymbolicName(SymbolicName), Signed(true) {}
2498 static bool classof(const OperandRenderer *R) {
2499 return R->getKind() == OR_CopyConstantAsImm;
2502 const StringRef getSymbolicName() const { return SymbolicName; }
2504 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2505 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2506 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2507 Table << MatchTable::Opcode(Signed ? "GIR_CopyConstantAsSImm"
2508 : "GIR_CopyConstantAsUImm")
2509 << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2510 << MatchTable::Comment("OldInsnID")
2511 << MatchTable::IntValue(OldInsnVarID)
2512 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2516 /// A CopyFConstantAsFPImmRenderer emits code to render a G_FCONSTANT
2517 /// instruction to an extended immediate operand.
2518 class CopyFConstantAsFPImmRenderer : public OperandRenderer {
2521 /// The name of the operand.
2522 const std::string SymbolicName;
2525 CopyFConstantAsFPImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
2526 : OperandRenderer(OR_CopyFConstantAsFPImm), NewInsnID(NewInsnID),
2527 SymbolicName(SymbolicName) {}
2529 static bool classof(const OperandRenderer *R) {
2530 return R->getKind() == OR_CopyFConstantAsFPImm;
2533 const StringRef getSymbolicName() const { return SymbolicName; }
2535 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2536 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2537 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2538 Table << MatchTable::Opcode("GIR_CopyFConstantAsFPImm")
2539 << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2540 << MatchTable::Comment("OldInsnID")
2541 << MatchTable::IntValue(OldInsnVarID)
2542 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2546 /// A CopySubRegRenderer emits code to copy a single register operand from an
2547 /// existing instruction to the one being built and indicate that only a
2548 /// subregister should be copied.
2549 class CopySubRegRenderer : public OperandRenderer {
2552 /// The name of the operand.
2553 const StringRef SymbolicName;
2554 /// The subregister to extract.
2555 const CodeGenSubRegIndex *SubReg;
2558 CopySubRegRenderer(unsigned NewInsnID, StringRef SymbolicName,
2559 const CodeGenSubRegIndex *SubReg)
2560 : OperandRenderer(OR_CopySubReg), NewInsnID(NewInsnID),
2561 SymbolicName(SymbolicName), SubReg(SubReg) {}
2563 static bool classof(const OperandRenderer *R) {
2564 return R->getKind() == OR_CopySubReg;
2567 const StringRef getSymbolicName() const { return SymbolicName; }
2569 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2570 const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2571 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2572 Table << MatchTable::Opcode("GIR_CopySubReg")
2573 << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2574 << MatchTable::Comment("OldInsnID")
2575 << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2576 << MatchTable::IntValue(Operand.getOpIdx())
2577 << MatchTable::Comment("SubRegIdx")
2578 << MatchTable::IntValue(SubReg->EnumValue)
2579 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2583 /// Adds a specific physical register to the instruction being built.
2584 /// This is typically useful for WZR/XZR on AArch64.
2585 class AddRegisterRenderer : public OperandRenderer {
2588 const Record *RegisterDef;
2592 AddRegisterRenderer(unsigned InsnID, const Record *RegisterDef,
2594 : OperandRenderer(OR_Register), InsnID(InsnID), RegisterDef(RegisterDef),
2597 static bool classof(const OperandRenderer *R) {
2598 return R->getKind() == OR_Register;
2601 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2602 Table << MatchTable::Opcode("GIR_AddRegister")
2603 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2604 << MatchTable::NamedValue(
2605 (RegisterDef->getValue("Namespace")
2606 ? RegisterDef->getValueAsString("Namespace")
2608 RegisterDef->getName())
2609 << MatchTable::Comment("AddRegisterRegFlags");
2611 // TODO: This is encoded as a 64-bit element, but only 16 or 32-bits are
2612 // really needed for a physical register reference. We can pack the
2613 // register and flags in a single field.
2615 Table << MatchTable::NamedValue("RegState::Define");
2617 Table << MatchTable::IntValue(0);
2618 Table << MatchTable::LineBreak;
2622 /// Adds a specific temporary virtual register to the instruction being built.
2623 /// This is used to chain instructions together when emitting multiple
2625 class TempRegRenderer : public OperandRenderer {
2629 const CodeGenSubRegIndex *SubRegIdx;
2633 TempRegRenderer(unsigned InsnID, unsigned TempRegID, bool IsDef = false,
2634 const CodeGenSubRegIndex *SubReg = nullptr)
2635 : OperandRenderer(OR_Register), InsnID(InsnID), TempRegID(TempRegID),
2636 SubRegIdx(SubReg), IsDef(IsDef) {}
2638 static bool classof(const OperandRenderer *R) {
2639 return R->getKind() == OR_TempRegister;
2642 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2645 Table << MatchTable::Opcode("GIR_AddTempSubRegister");
2647 Table << MatchTable::Opcode("GIR_AddTempRegister");
2649 Table << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2650 << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID)
2651 << MatchTable::Comment("TempRegFlags");
2654 Table << MatchTable::NamedValue("RegState::Define");
2656 Table << MatchTable::IntValue(0);
2659 Table << MatchTable::NamedValue(SubRegIdx->getQualifiedName());
2660 Table << MatchTable::LineBreak;
2664 /// Adds a specific immediate to the instruction being built.
2665 class ImmRenderer : public OperandRenderer {
2671 ImmRenderer(unsigned InsnID, int64_t Imm)
2672 : OperandRenderer(OR_Imm), InsnID(InsnID), Imm(Imm) {}
2674 static bool classof(const OperandRenderer *R) {
2675 return R->getKind() == OR_Imm;
2678 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2679 Table << MatchTable::Opcode("GIR_AddImm") << MatchTable::Comment("InsnID")
2680 << MatchTable::IntValue(InsnID) << MatchTable::Comment("Imm")
2681 << MatchTable::IntValue(Imm) << MatchTable::LineBreak;
2685 /// Adds an enum value for a subreg index to the instruction being built.
2686 class SubRegIndexRenderer : public OperandRenderer {
2689 const CodeGenSubRegIndex *SubRegIdx;
2692 SubRegIndexRenderer(unsigned InsnID, const CodeGenSubRegIndex *SRI)
2693 : OperandRenderer(OR_SubRegIndex), InsnID(InsnID), SubRegIdx(SRI) {}
2695 static bool classof(const OperandRenderer *R) {
2696 return R->getKind() == OR_SubRegIndex;
2699 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2700 Table << MatchTable::Opcode("GIR_AddImm") << MatchTable::Comment("InsnID")
2701 << MatchTable::IntValue(InsnID) << MatchTable::Comment("SubRegIndex")
2702 << MatchTable::IntValue(SubRegIdx->EnumValue)
2703 << MatchTable::LineBreak;
2707 /// Adds operands by calling a renderer function supplied by the ComplexPattern
2708 /// matcher function.
2709 class RenderComplexPatternOperand : public OperandRenderer {
2712 const Record &TheDef;
2713 /// The name of the operand.
2714 const StringRef SymbolicName;
2715 /// The renderer number. This must be unique within a rule since it's used to
2716 /// identify a temporary variable to hold the renderer function.
2717 unsigned RendererID;
2718 /// When provided, this is the suboperand of the ComplexPattern operand to
2719 /// render. Otherwise all the suboperands will be rendered.
2720 Optional<unsigned> SubOperand;
2722 unsigned getNumOperands() const {
2723 return TheDef.getValueAsDag("Operands")->getNumArgs();
2727 RenderComplexPatternOperand(unsigned InsnID, const Record &TheDef,
2728 StringRef SymbolicName, unsigned RendererID,
2729 Optional<unsigned> SubOperand = None)
2730 : OperandRenderer(OR_ComplexPattern), InsnID(InsnID), TheDef(TheDef),
2731 SymbolicName(SymbolicName), RendererID(RendererID),
2732 SubOperand(SubOperand) {}
2734 static bool classof(const OperandRenderer *R) {
2735 return R->getKind() == OR_ComplexPattern;
2738 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2739 Table << MatchTable::Opcode(SubOperand.hasValue() ? "GIR_ComplexSubOperandRenderer"
2740 : "GIR_ComplexRenderer")
2741 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2742 << MatchTable::Comment("RendererID")
2743 << MatchTable::IntValue(RendererID);
2744 if (SubOperand.hasValue())
2745 Table << MatchTable::Comment("SubOperand")
2746 << MatchTable::IntValue(SubOperand.getValue());
2747 Table << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2751 class CustomRenderer : public OperandRenderer {
2754 const Record &Renderer;
2755 /// The name of the operand.
2756 const std::string SymbolicName;
2759 CustomRenderer(unsigned InsnID, const Record &Renderer,
2760 StringRef SymbolicName)
2761 : OperandRenderer(OR_Custom), InsnID(InsnID), Renderer(Renderer),
2762 SymbolicName(SymbolicName) {}
2764 static bool classof(const OperandRenderer *R) {
2765 return R->getKind() == OR_Custom;
2768 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2769 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2770 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2771 Table << MatchTable::Opcode("GIR_CustomRenderer")
2772 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2773 << MatchTable::Comment("OldInsnID")
2774 << MatchTable::IntValue(OldInsnVarID)
2775 << MatchTable::Comment("Renderer")
2776 << MatchTable::NamedValue(
2777 "GICR_" + Renderer.getValueAsString("RendererFn").str())
2778 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2782 class CustomOperandRenderer : public OperandRenderer {
2785 const Record &Renderer;
2786 /// The name of the operand.
2787 const std::string SymbolicName;
2790 CustomOperandRenderer(unsigned InsnID, const Record &Renderer,
2791 StringRef SymbolicName)
2792 : OperandRenderer(OR_CustomOperand), InsnID(InsnID), Renderer(Renderer),
2793 SymbolicName(SymbolicName) {}
2795 static bool classof(const OperandRenderer *R) {
2796 return R->getKind() == OR_CustomOperand;
2799 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2800 const OperandMatcher &OpdMatcher = Rule.getOperandMatcher(SymbolicName);
2801 Table << MatchTable::Opcode("GIR_CustomOperandRenderer")
2802 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2803 << MatchTable::Comment("OldInsnID")
2804 << MatchTable::IntValue(OpdMatcher.getInsnVarID())
2805 << MatchTable::Comment("OpIdx")
2806 << MatchTable::IntValue(OpdMatcher.getOpIdx())
2807 << MatchTable::Comment("OperandRenderer")
2808 << MatchTable::NamedValue(
2809 "GICR_" + Renderer.getValueAsString("RendererFn").str())
2810 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2814 /// An action taken when all Matcher predicates succeeded for a parent rule.
2816 /// Typical actions include:
2817 /// * Changing the opcode of an instruction.
2818 /// * Adding an operand to an instruction.
2821 virtual ~MatchAction() {}
2823 /// Emit the MatchTable opcodes to implement the action.
2824 virtual void emitActionOpcodes(MatchTable &Table,
2825 RuleMatcher &Rule) const = 0;
2828 /// Generates a comment describing the matched rule being acted upon.
2829 class DebugCommentAction : public MatchAction {
2834 DebugCommentAction(StringRef S) : S(std::string(S)) {}
2836 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2837 Table << MatchTable::Comment(S) << MatchTable::LineBreak;
2841 /// Generates code to build an instruction or mutate an existing instruction
2842 /// into the desired instruction when this is possible.
2843 class BuildMIAction : public MatchAction {
2846 const CodeGenInstruction *I;
2847 InstructionMatcher *Matched;
2848 std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers;
2850 /// True if the instruction can be built solely by mutating the opcode.
2851 bool canMutate(RuleMatcher &Rule, const InstructionMatcher *Insn) const {
2855 if (OperandRenderers.size() != Insn->getNumOperands())
2858 for (const auto &Renderer : enumerate(OperandRenderers)) {
2859 if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) {
2860 const OperandMatcher &OM = Rule.getOperandMatcher(Copy->getSymbolicName());
2861 if (Insn != &OM.getInstructionMatcher() ||
2862 OM.getOpIdx() != Renderer.index())
2872 BuildMIAction(unsigned InsnID, const CodeGenInstruction *I)
2873 : InsnID(InsnID), I(I), Matched(nullptr) {}
2875 unsigned getInsnID() const { return InsnID; }
2876 const CodeGenInstruction *getCGI() const { return I; }
2878 void chooseInsnToMutate(RuleMatcher &Rule) {
2879 for (auto *MutateCandidate : Rule.mutatable_insns()) {
2880 if (canMutate(Rule, MutateCandidate)) {
2881 // Take the first one we're offered that we're able to mutate.
2882 Rule.reserveInsnMatcherForMutation(MutateCandidate);
2883 Matched = MutateCandidate;
2889 template <class Kind, class... Args>
2890 Kind &addRenderer(Args&&... args) {
2891 OperandRenderers.emplace_back(
2892 std::make_unique<Kind>(InsnID, std::forward<Args>(args)...));
2893 return *static_cast<Kind *>(OperandRenderers.back().get());
2896 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2898 assert(canMutate(Rule, Matched) &&
2899 "Arranged to mutate an insn that isn't mutatable");
2901 unsigned RecycleInsnID = Rule.getInsnVarID(*Matched);
2902 Table << MatchTable::Opcode("GIR_MutateOpcode")
2903 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2904 << MatchTable::Comment("RecycleInsnID")
2905 << MatchTable::IntValue(RecycleInsnID)
2906 << MatchTable::Comment("Opcode")
2907 << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
2908 << MatchTable::LineBreak;
2910 if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) {
2911 for (auto Def : I->ImplicitDefs) {
2912 auto Namespace = Def->getValue("Namespace")
2913 ? Def->getValueAsString("Namespace")
2915 Table << MatchTable::Opcode("GIR_AddImplicitDef")
2916 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2917 << MatchTable::NamedValue(Namespace, Def->getName())
2918 << MatchTable::LineBreak;
2920 for (auto Use : I->ImplicitUses) {
2921 auto Namespace = Use->getValue("Namespace")
2922 ? Use->getValueAsString("Namespace")
2924 Table << MatchTable::Opcode("GIR_AddImplicitUse")
2925 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2926 << MatchTable::NamedValue(Namespace, Use->getName())
2927 << MatchTable::LineBreak;
2933 // TODO: Simple permutation looks like it could be almost as common as
2934 // mutation due to commutative operations.
2936 Table << MatchTable::Opcode("GIR_BuildMI") << MatchTable::Comment("InsnID")
2937 << MatchTable::IntValue(InsnID) << MatchTable::Comment("Opcode")
2938 << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
2939 << MatchTable::LineBreak;
2940 for (const auto &Renderer : OperandRenderers)
2941 Renderer->emitRenderOpcodes(Table, Rule);
2943 if (I->mayLoad || I->mayStore) {
2944 Table << MatchTable::Opcode("GIR_MergeMemOperands")
2945 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2946 << MatchTable::Comment("MergeInsnID's");
2947 // Emit the ID's for all the instructions that are matched by this rule.
2948 // TODO: Limit this to matched instructions that mayLoad/mayStore or have
2949 // some other means of having a memoperand. Also limit this to
2950 // emitted instructions that expect to have a memoperand too. For
2951 // example, (G_SEXT (G_LOAD x)) that results in separate load and
2952 // sign-extend instructions shouldn't put the memoperand on the
2953 // sign-extend since it has no effect there.
2954 std::vector<unsigned> MergeInsnIDs;
2955 for (const auto &IDMatcherPair : Rule.defined_insn_vars())
2956 MergeInsnIDs.push_back(IDMatcherPair.second);
2957 llvm::sort(MergeInsnIDs);
2958 for (const auto &MergeInsnID : MergeInsnIDs)
2959 Table << MatchTable::IntValue(MergeInsnID);
2960 Table << MatchTable::NamedValue("GIU_MergeMemOperands_EndOfList")
2961 << MatchTable::LineBreak;
2964 // FIXME: This is a hack but it's sufficient for ISel. We'll need to do
2965 // better for combines. Particularly when there are multiple match
2968 Table << MatchTable::Opcode("GIR_EraseFromParent")
2969 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2970 << MatchTable::LineBreak;
2974 /// Generates code to constrain the operands of an output instruction to the
2975 /// register classes specified by the definition of that instruction.
2976 class ConstrainOperandsToDefinitionAction : public MatchAction {
2980 ConstrainOperandsToDefinitionAction(unsigned InsnID) : InsnID(InsnID) {}
2982 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2983 Table << MatchTable::Opcode("GIR_ConstrainSelectedInstOperands")
2984 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2985 << MatchTable::LineBreak;
2989 /// Generates code to constrain the specified operand of an output instruction
2990 /// to the specified register class.
2991 class ConstrainOperandToRegClassAction : public MatchAction {
2994 const CodeGenRegisterClass &RC;
2997 ConstrainOperandToRegClassAction(unsigned InsnID, unsigned OpIdx,
2998 const CodeGenRegisterClass &RC)
2999 : InsnID(InsnID), OpIdx(OpIdx), RC(RC) {}
3001 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
3002 Table << MatchTable::Opcode("GIR_ConstrainOperandRC")
3003 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
3004 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
3005 << MatchTable::NamedValue(RC.getQualifiedName() + "RegClassID")
3006 << MatchTable::LineBreak;
3010 /// Generates code to create a temporary register which can be used to chain
3011 /// instructions together.
3012 class MakeTempRegisterAction : public MatchAction {
3018 MakeTempRegisterAction(const LLTCodeGen &Ty, unsigned TempRegID)
3019 : Ty(Ty), TempRegID(TempRegID) {
3020 KnownTypes.insert(Ty);
3023 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
3024 Table << MatchTable::Opcode("GIR_MakeTempReg")
3025 << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID)
3026 << MatchTable::Comment("TypeID")
3027 << MatchTable::NamedValue(Ty.getCxxEnumValue())
3028 << MatchTable::LineBreak;
3032 InstructionMatcher &RuleMatcher::addInstructionMatcher(StringRef SymbolicName) {
3033 Matchers.emplace_back(new InstructionMatcher(*this, SymbolicName));
3034 MutatableInsns.insert(Matchers.back().get());
3035 return *Matchers.back();
3038 void RuleMatcher::addRequiredFeature(Record *Feature) {
3039 RequiredFeatures.push_back(Feature);
3042 const std::vector<Record *> &RuleMatcher::getRequiredFeatures() const {
3043 return RequiredFeatures;
3046 // Emplaces an action of the specified Kind at the end of the action list.
3048 // Returns a reference to the newly created action.
3050 // Like std::vector::emplace_back(), may invalidate all iterators if the new
3051 // size exceeds the capacity. Otherwise, only invalidates the past-the-end
3053 template <class Kind, class... Args>
3054 Kind &RuleMatcher::addAction(Args &&... args) {
3055 Actions.emplace_back(std::make_unique<Kind>(std::forward<Args>(args)...));
3056 return *static_cast<Kind *>(Actions.back().get());
3059 // Emplaces an action of the specified Kind before the given insertion point.
3061 // Returns an iterator pointing at the newly created instruction.
3063 // Like std::vector::insert(), may invalidate all iterators if the new size
3064 // exceeds the capacity. Otherwise, only invalidates the iterators from the
3065 // insertion point onwards.
3066 template <class Kind, class... Args>
3067 action_iterator RuleMatcher::insertAction(action_iterator InsertPt,
3069 return Actions.emplace(InsertPt,
3070 std::make_unique<Kind>(std::forward<Args>(args)...));
3073 unsigned RuleMatcher::implicitlyDefineInsnVar(InstructionMatcher &Matcher) {
3074 unsigned NewInsnVarID = NextInsnVarID++;
3075 InsnVariableIDs[&Matcher] = NewInsnVarID;
3076 return NewInsnVarID;
3079 unsigned RuleMatcher::getInsnVarID(InstructionMatcher &InsnMatcher) const {
3080 const auto &I = InsnVariableIDs.find(&InsnMatcher);
3081 if (I != InsnVariableIDs.end())
3083 llvm_unreachable("Matched Insn was not captured in a local variable");
3086 void RuleMatcher::defineOperand(StringRef SymbolicName, OperandMatcher &OM) {
3087 if (DefinedOperands.find(SymbolicName) == DefinedOperands.end()) {
3088 DefinedOperands[SymbolicName] = &OM;
3092 // If the operand is already defined, then we must ensure both references in
3093 // the matcher have the exact same node.
3094 OM.addPredicate<SameOperandMatcher>(OM.getSymbolicName());
3097 void RuleMatcher::definePhysRegOperand(Record *Reg, OperandMatcher &OM) {
3098 if (PhysRegOperands.find(Reg) == PhysRegOperands.end()) {
3099 PhysRegOperands[Reg] = &OM;
3104 InstructionMatcher &
3105 RuleMatcher::getInstructionMatcher(StringRef SymbolicName) const {
3106 for (const auto &I : InsnVariableIDs)
3107 if (I.first->getSymbolicName() == SymbolicName)
3110 ("Failed to lookup instruction " + SymbolicName).str().c_str());
3113 const OperandMatcher &
3114 RuleMatcher::getPhysRegOperandMatcher(Record *Reg) const {
3115 const auto &I = PhysRegOperands.find(Reg);
3117 if (I == PhysRegOperands.end()) {
3118 PrintFatalError(SrcLoc, "Register " + Reg->getName() +
3119 " was not declared in matcher");
3125 const OperandMatcher &
3126 RuleMatcher::getOperandMatcher(StringRef Name) const {
3127 const auto &I = DefinedOperands.find(Name);
3129 if (I == DefinedOperands.end())
3130 PrintFatalError(SrcLoc, "Operand " + Name + " was not declared in matcher");
3135 void RuleMatcher::emit(MatchTable &Table) {
3136 if (Matchers.empty())
3137 llvm_unreachable("Unexpected empty matcher!");
3139 // The representation supports rules that require multiple roots such as:
3141 // %elt0(s32) = G_LOAD %ptr
3142 // %1(p0) = G_ADD %ptr, 4
3143 // %elt1(s32) = G_LOAD p0 %1
3144 // which could be usefully folded into:
3146 // %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr
3147 // on some targets but we don't need to make use of that yet.
3148 assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
3150 unsigned LabelID = Table.allocateLabelID();
3151 Table << MatchTable::Opcode("GIM_Try", +1)
3152 << MatchTable::Comment("On fail goto")
3153 << MatchTable::JumpTarget(LabelID)
3154 << MatchTable::Comment(("Rule ID " + Twine(RuleID) + " //").str())
3155 << MatchTable::LineBreak;
3157 if (!RequiredFeatures.empty()) {
3158 Table << MatchTable::Opcode("GIM_CheckFeatures")
3159 << MatchTable::NamedValue(getNameForFeatureBitset(RequiredFeatures))
3160 << MatchTable::LineBreak;
3163 Matchers.front()->emitPredicateOpcodes(Table, *this);
3165 // We must also check if it's safe to fold the matched instructions.
3166 if (InsnVariableIDs.size() >= 2) {
3167 // Invert the map to create stable ordering (by var names)
3168 SmallVector<unsigned, 2> InsnIDs;
3169 for (const auto &Pair : InsnVariableIDs) {
3170 // Skip the root node since it isn't moving anywhere. Everything else is
3171 // sinking to meet it.
3172 if (Pair.first == Matchers.front().get())
3175 InsnIDs.push_back(Pair.second);
3177 llvm::sort(InsnIDs);
3179 for (const auto &InsnID : InsnIDs) {
3180 // Reject the difficult cases until we have a more accurate check.
3181 Table << MatchTable::Opcode("GIM_CheckIsSafeToFold")
3182 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
3183 << MatchTable::LineBreak;
3185 // FIXME: Emit checks to determine it's _actually_ safe to fold and/or
3186 // account for unsafe cases.
3191 // MI0--> %2 = ... %0
3192 // It's not safe to erase MI1. We currently handle this by not
3193 // erasing %0 (even when it's dead).
3196 // MI1--> %0 = load volatile @a
3197 // %1 = load volatile @a
3198 // MI0--> %2 = ... %0
3199 // It's not safe to sink %0's def past %1. We currently handle
3200 // this by rejecting all loads.
3203 // MI1--> %0 = load @a
3205 // MI0--> %2 = ... %0
3206 // It's not safe to sink %0's def past %1. We currently handle
3207 // this by rejecting all loads.
3210 // G_CONDBR %cond, @BB1
3212 // MI1--> %0 = load @a
3215 // MI0--> %2 = ... %0
3216 // It's not always safe to sink %0 across control flow. In this
3217 // case it may introduce a memory fault. We currentl handle this
3218 // by rejecting all loads.
3222 for (const auto &PM : EpilogueMatchers)
3223 PM->emitPredicateOpcodes(Table, *this);
3225 for (const auto &MA : Actions)
3226 MA->emitActionOpcodes(Table, *this);
3228 if (Table.isWithCoverage())
3229 Table << MatchTable::Opcode("GIR_Coverage") << MatchTable::IntValue(RuleID)
3230 << MatchTable::LineBreak;
3232 Table << MatchTable::Comment(("GIR_Coverage, " + Twine(RuleID) + ",").str())
3233 << MatchTable::LineBreak;
3235 Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak
3236 << MatchTable::Label(LabelID);
3237 ++NumPatternEmitted;
3240 bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
3241 // Rules involving more match roots have higher priority.
3242 if (Matchers.size() > B.Matchers.size())
3244 if (Matchers.size() < B.Matchers.size())
3247 for (auto Matcher : zip(Matchers, B.Matchers)) {
3248 if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher)))
3250 if (std::get<1>(Matcher)->isHigherPriorityThan(*std::get<0>(Matcher)))
3257 unsigned RuleMatcher::countRendererFns() const {
3258 return std::accumulate(
3259 Matchers.begin(), Matchers.end(), 0,
3260 [](unsigned A, const std::unique_ptr<InstructionMatcher> &Matcher) {
3261 return A + Matcher->countRendererFns();
3265 bool OperandPredicateMatcher::isHigherPriorityThan(
3266 const OperandPredicateMatcher &B) const {
3267 // Generally speaking, an instruction is more important than an Int or a
3268 // LiteralInt because it can cover more nodes but theres an exception to
3269 // this. G_CONSTANT's are less important than either of those two because they
3270 // are more permissive.
3272 const InstructionOperandMatcher *AOM =
3273 dyn_cast<InstructionOperandMatcher>(this);
3274 const InstructionOperandMatcher *BOM =
3275 dyn_cast<InstructionOperandMatcher>(&B);
3276 bool AIsConstantInsn = AOM && AOM->getInsnMatcher().isConstantInstruction();
3277 bool BIsConstantInsn = BOM && BOM->getInsnMatcher().isConstantInstruction();
3280 // The relative priorities between a G_CONSTANT and any other instruction
3281 // don't actually matter but this code is needed to ensure a strict weak
3282 // ordering. This is particularly important on Windows where the rules will
3283 // be incorrectly sorted without it.
3284 if (AIsConstantInsn != BIsConstantInsn)
3285 return AIsConstantInsn < BIsConstantInsn;
3289 if (AOM && AIsConstantInsn && (B.Kind == OPM_Int || B.Kind == OPM_LiteralInt))
3291 if (BOM && BIsConstantInsn && (Kind == OPM_Int || Kind == OPM_LiteralInt))
3294 return Kind < B.Kind;
3297 void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
3298 RuleMatcher &Rule) const {
3299 const OperandMatcher &OtherOM = Rule.getOperandMatcher(MatchingName);
3300 unsigned OtherInsnVarID = Rule.getInsnVarID(OtherOM.getInstructionMatcher());
3301 assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getInsnVarID());
3303 Table << MatchTable::Opcode("GIM_CheckIsSameOperand")
3304 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
3305 << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx)
3306 << MatchTable::Comment("OtherMI")
3307 << MatchTable::IntValue(OtherInsnVarID)
3308 << MatchTable::Comment("OtherOpIdx")
3309 << MatchTable::IntValue(OtherOM.getOpIdx())
3310 << MatchTable::LineBreak;
3313 //===- GlobalISelEmitter class --------------------------------------------===//
3315 static Expected<LLTCodeGen> getInstResultType(const TreePatternNode *Dst) {
3316 ArrayRef<TypeSetByHwMode> ChildTypes = Dst->getExtTypes();
3317 if (ChildTypes.size() != 1)
3318 return failedImport("Dst pattern child has multiple results");
3320 Optional<LLTCodeGen> MaybeOpTy;
3321 if (ChildTypes.front().isMachineValueType()) {
3323 MVTToLLT(ChildTypes.front().getMachineValueType().SimpleTy);
3327 return failedImport("Dst operand has an unsupported type");
3331 class GlobalISelEmitter {
3333 explicit GlobalISelEmitter(RecordKeeper &RK);
3334 void run(raw_ostream &OS);
3337 const RecordKeeper &RK;
3338 const CodeGenDAGPatterns CGP;
3339 const CodeGenTarget &Target;
3340 CodeGenRegBank &CGRegs;
3342 /// Keep track of the equivalence between SDNodes and Instruction by mapping
3343 /// SDNodes to the GINodeEquiv mapping. We need to map to the GINodeEquiv to
3344 /// check for attributes on the relation such as CheckMMOIsNonAtomic.
3345 /// This is defined using 'GINodeEquiv' in the target description.
3346 DenseMap<Record *, Record *> NodeEquivs;
3348 /// Keep track of the equivalence between ComplexPattern's and
3349 /// GIComplexOperandMatcher. Map entries are specified by subclassing
3350 /// GIComplexPatternEquiv.
3351 DenseMap<const Record *, const Record *> ComplexPatternEquivs;
3353 /// Keep track of the equivalence between SDNodeXForm's and
3354 /// GICustomOperandRenderer. Map entries are specified by subclassing
3355 /// GISDNodeXFormEquiv.
3356 DenseMap<const Record *, const Record *> SDNodeXFormEquivs;
3358 /// Keep track of Scores of PatternsToMatch similar to how the DAG does.
3359 /// This adds compatibility for RuleMatchers to use this for ordering rules.
3360 DenseMap<uint64_t, int> RuleMatcherScores;
3362 // Map of predicates to their subtarget features.
3363 SubtargetFeatureInfoMap SubtargetFeatures;
3365 // Rule coverage information.
3366 Optional<CodeGenCoverage> RuleCoverage;
3368 void gatherOpcodeValues();
3369 void gatherTypeIDValues();
3370 void gatherNodeEquivs();
3372 Record *findNodeEquiv(Record *N) const;
3373 const CodeGenInstruction *getEquivNode(Record &Equiv,
3374 const TreePatternNode *N) const;
3376 Error importRulePredicates(RuleMatcher &M, ArrayRef<Predicate> Predicates);
3377 Expected<InstructionMatcher &>
3378 createAndImportSelDAGMatcher(RuleMatcher &Rule,
3379 InstructionMatcher &InsnMatcher,
3380 const TreePatternNode *Src, unsigned &TempOpIdx);
3381 Error importComplexPatternOperandMatcher(OperandMatcher &OM, Record *R,
3382 unsigned &TempOpIdx) const;
3383 Error importChildMatcher(RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
3384 const TreePatternNode *SrcChild,
3385 bool OperandIsAPointer, bool OperandIsImmArg,
3386 unsigned OpIdx, unsigned &TempOpIdx);
3388 Expected<BuildMIAction &> createAndImportInstructionRenderer(
3389 RuleMatcher &M, InstructionMatcher &InsnMatcher,
3390 const TreePatternNode *Src, const TreePatternNode *Dst);
3391 Expected<action_iterator> createAndImportSubInstructionRenderer(
3392 action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst,
3394 Expected<action_iterator>
3395 createInstructionRenderer(action_iterator InsertPt, RuleMatcher &M,
3396 const TreePatternNode *Dst);
3397 void importExplicitDefRenderers(BuildMIAction &DstMIBuilder);
3399 Expected<action_iterator>
3400 importExplicitUseRenderers(action_iterator InsertPt, RuleMatcher &M,
3401 BuildMIAction &DstMIBuilder,
3402 const llvm::TreePatternNode *Dst);
3403 Expected<action_iterator>
3404 importExplicitUseRenderer(action_iterator InsertPt, RuleMatcher &Rule,
3405 BuildMIAction &DstMIBuilder,
3406 TreePatternNode *DstChild);
3407 Error importDefaultOperandRenderers(action_iterator InsertPt, RuleMatcher &M,
3408 BuildMIAction &DstMIBuilder,
3409 DagInit *DefaultOps) const;
3411 importImplicitDefRenderers(BuildMIAction &DstMIBuilder,
3412 const std::vector<Record *> &ImplicitDefs) const;
3414 void emitCxxPredicateFns(raw_ostream &OS, StringRef CodeFieldName,
3415 StringRef TypeIdentifier, StringRef ArgType,
3416 StringRef ArgName, StringRef AdditionalDeclarations,
3417 std::function<bool(const Record *R)> Filter);
3418 void emitImmPredicateFns(raw_ostream &OS, StringRef TypeIdentifier,
3420 std::function<bool(const Record *R)> Filter);
3421 void emitMIPredicateFns(raw_ostream &OS);
3423 /// Analyze pattern \p P, returning a matcher for it if possible.
3424 /// Otherwise, return an Error explaining why we don't support it.
3425 Expected<RuleMatcher> runOnPattern(const PatternToMatch &P);
3427 void declareSubtargetFeature(Record *Predicate);
3429 MatchTable buildMatchTable(MutableArrayRef<RuleMatcher> Rules, bool Optimize,
3432 /// Infer a CodeGenRegisterClass for the type of \p SuperRegNode. The returned
3433 /// CodeGenRegisterClass will support the CodeGenRegisterClass of
3434 /// \p SubRegNode, and the subregister index defined by \p SubRegIdxNode.
3435 /// If no register class is found, return None.
3436 Optional<const CodeGenRegisterClass *>
3437 inferSuperRegisterClassForNode(const TypeSetByHwMode &Ty,
3438 TreePatternNode *SuperRegNode,
3439 TreePatternNode *SubRegIdxNode);
3440 Optional<CodeGenSubRegIndex *>
3441 inferSubRegIndexForNode(TreePatternNode *SubRegIdxNode);
3443 /// Infer a CodeGenRegisterClass which suppoorts \p Ty and \p SubRegIdxNode.
3444 /// Return None if no such class exists.
3445 Optional<const CodeGenRegisterClass *>
3446 inferSuperRegisterClass(const TypeSetByHwMode &Ty,
3447 TreePatternNode *SubRegIdxNode);
3449 /// Return the CodeGenRegisterClass associated with \p Leaf if it has one.
3450 Optional<const CodeGenRegisterClass *>
3451 getRegClassFromLeaf(TreePatternNode *Leaf);
3453 /// Return a CodeGenRegisterClass for \p N if one can be found. Return None
3455 Optional<const CodeGenRegisterClass *>
3456 inferRegClassFromPattern(TreePatternNode *N);
3459 /// Takes a sequence of \p Rules and group them based on the predicates
3460 /// they share. \p MatcherStorage is used as a memory container
3461 /// for the group that are created as part of this process.
3463 /// What this optimization does looks like if GroupT = GroupMatcher:
3464 /// Output without optimization:
3471 /// # predicate A // <-- effectively this is going to be checked twice.
3472 /// // Once in R1 and once in R2.
3475 /// Output with optimization:
3478 /// # predicate A // <-- Check is now shared.
3484 template <class GroupT>
3485 static std::vector<Matcher *> optimizeRules(
3486 ArrayRef<Matcher *> Rules,
3487 std::vector<std::unique_ptr<Matcher>> &MatcherStorage);
3490 void GlobalISelEmitter::gatherOpcodeValues() {
3491 InstructionOpcodeMatcher::initOpcodeValuesMap(Target);
3494 void GlobalISelEmitter::gatherTypeIDValues() {
3495 LLTOperandMatcher::initTypeIDValuesMap();
3498 void GlobalISelEmitter::gatherNodeEquivs() {
3499 assert(NodeEquivs.empty());
3500 for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
3501 NodeEquivs[Equiv->getValueAsDef("Node")] = Equiv;
3503 assert(ComplexPatternEquivs.empty());
3504 for (Record *Equiv : RK.getAllDerivedDefinitions("GIComplexPatternEquiv")) {
3505 Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
3508 ComplexPatternEquivs[SelDAGEquiv] = Equiv;
3511 assert(SDNodeXFormEquivs.empty());
3512 for (Record *Equiv : RK.getAllDerivedDefinitions("GISDNodeXFormEquiv")) {
3513 Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
3516 SDNodeXFormEquivs[SelDAGEquiv] = Equiv;
3520 Record *GlobalISelEmitter::findNodeEquiv(Record *N) const {
3521 return NodeEquivs.lookup(N);
3524 const CodeGenInstruction *
3525 GlobalISelEmitter::getEquivNode(Record &Equiv, const TreePatternNode *N) const {
3526 if (N->getNumChildren() >= 1) {
3527 // setcc operation maps to two different G_* instructions based on the type.
3528 if (!Equiv.isValueUnset("IfFloatingPoint") &&
3529 MVT(N->getChild(0)->getSimpleType(0)).isFloatingPoint())
3530 return &Target.getInstruction(Equiv.getValueAsDef("IfFloatingPoint"));
3533 for (const TreePredicateCall &Call : N->getPredicateCalls()) {
3534 const TreePredicateFn &Predicate = Call.Fn;
3535 if (!Equiv.isValueUnset("IfSignExtend") && Predicate.isLoad() &&
3536 Predicate.isSignExtLoad())
3537 return &Target.getInstruction(Equiv.getValueAsDef("IfSignExtend"));
3538 if (!Equiv.isValueUnset("IfZeroExtend") && Predicate.isLoad() &&
3539 Predicate.isZeroExtLoad())
3540 return &Target.getInstruction(Equiv.getValueAsDef("IfZeroExtend"));
3543 return &Target.getInstruction(Equiv.getValueAsDef("I"));
3546 GlobalISelEmitter::GlobalISelEmitter(RecordKeeper &RK)
3547 : RK(RK), CGP(RK), Target(CGP.getTargetInfo()),
3548 CGRegs(Target.getRegBank()) {}
3550 //===- Emitter ------------------------------------------------------------===//
3553 GlobalISelEmitter::importRulePredicates(RuleMatcher &M,
3554 ArrayRef<Predicate> Predicates) {
3555 for (const Predicate &P : Predicates) {
3556 if (!P.Def || P.getCondString().empty())
3558 declareSubtargetFeature(P.Def);
3559 M.addRequiredFeature(P.Def);
3562 return Error::success();
3565 Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher(
3566 RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
3567 const TreePatternNode *Src, unsigned &TempOpIdx) {
3568 Record *SrcGIEquivOrNull = nullptr;
3569 const CodeGenInstruction *SrcGIOrNull = nullptr;
3571 // Start with the defined operands (i.e., the results of the root operator).
3572 if (Src->getExtTypes().size() > 1)
3573 return failedImport("Src pattern has multiple results");
3575 if (Src->isLeaf()) {
3576 Init *SrcInit = Src->getLeafValue();
3577 if (isa<IntInit>(SrcInit)) {
3578 InsnMatcher.addPredicate<InstructionOpcodeMatcher>(
3579 &Target.getInstruction(RK.getDef("G_CONSTANT")));
3581 return failedImport(
3582 "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
3584 SrcGIEquivOrNull = findNodeEquiv(Src->getOperator());
3585 if (!SrcGIEquivOrNull)
3586 return failedImport("Pattern operator lacks an equivalent Instruction" +
3587 explainOperator(Src->getOperator()));
3588 SrcGIOrNull = getEquivNode(*SrcGIEquivOrNull, Src);
3590 // The operators look good: match the opcode
3591 InsnMatcher.addPredicate<InstructionOpcodeMatcher>(SrcGIOrNull);
3595 for (const TypeSetByHwMode &VTy : Src->getExtTypes()) {
3596 // Results don't have a name unless they are the root node. The caller will
3597 // set the name if appropriate.
3598 OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
3599 if (auto Error = OM.addTypeCheckPredicate(VTy, false /* OperandIsAPointer */))
3600 return failedImport(toString(std::move(Error)) +
3601 " for result of Src pattern operator");
3604 for (const TreePredicateCall &Call : Src->getPredicateCalls()) {
3605 const TreePredicateFn &Predicate = Call.Fn;
3606 if (Predicate.isAlwaysTrue())
3609 if (Predicate.isImmediatePattern()) {
3610 InsnMatcher.addPredicate<InstructionImmPredicateMatcher>(Predicate);
3614 // An address space check is needed in all contexts if there is one.
3615 if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
3616 if (const ListInit *AddrSpaces = Predicate.getAddressSpaces()) {
3617 SmallVector<unsigned, 4> ParsedAddrSpaces;
3619 for (Init *Val : AddrSpaces->getValues()) {
3620 IntInit *IntVal = dyn_cast<IntInit>(Val);
3622 return failedImport("Address space is not an integer");
3623 ParsedAddrSpaces.push_back(IntVal->getValue());
3626 if (!ParsedAddrSpaces.empty()) {
3627 InsnMatcher.addPredicate<MemoryAddressSpacePredicateMatcher>(
3628 0, ParsedAddrSpaces);
3632 int64_t MinAlign = Predicate.getMinAlignment();
3634 InsnMatcher.addPredicate<MemoryAlignmentPredicateMatcher>(0, MinAlign);
3637 // G_LOAD is used for both non-extending and any-extending loads.
3638 if (Predicate.isLoad() && Predicate.isNonExtLoad()) {
3639 InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3640 0, MemoryVsLLTSizePredicateMatcher::EqualTo, 0);
3643 if (Predicate.isLoad() && Predicate.isAnyExtLoad()) {
3644 InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3645 0, MemoryVsLLTSizePredicateMatcher::LessThan, 0);
3649 if (Predicate.isStore()) {
3650 if (Predicate.isTruncStore()) {
3651 // FIXME: If MemoryVT is set, we end up with 2 checks for the MMO size.
3652 InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3653 0, MemoryVsLLTSizePredicateMatcher::LessThan, 0);
3656 if (Predicate.isNonTruncStore()) {
3657 // We need to check the sizes match here otherwise we could incorrectly
3658 // match truncating stores with non-truncating ones.
3659 InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3660 0, MemoryVsLLTSizePredicateMatcher::EqualTo, 0);
3664 // No check required. We already did it by swapping the opcode.
3665 if (!SrcGIEquivOrNull->isValueUnset("IfSignExtend") &&
3666 Predicate.isSignExtLoad())
3669 // No check required. We already did it by swapping the opcode.
3670 if (!SrcGIEquivOrNull->isValueUnset("IfZeroExtend") &&
3671 Predicate.isZeroExtLoad())
3674 // No check required. G_STORE by itself is a non-extending store.
3675 if (Predicate.isNonTruncStore())
3678 if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
3679 if (Predicate.getMemoryVT() != nullptr) {
3680 Optional<LLTCodeGen> MemTyOrNone =
3681 MVTToLLT(getValueType(Predicate.getMemoryVT()));
3684 return failedImport("MemVT could not be converted to LLT");
3686 // MMO's work in bytes so we must take care of unusual types like i1
3687 // don't round down.
3688 unsigned MemSizeInBits =
3689 llvm::alignTo(MemTyOrNone->get().getSizeInBits(), 8);
3691 InsnMatcher.addPredicate<MemorySizePredicateMatcher>(
3692 0, MemSizeInBits / 8);
3697 if (Predicate.isLoad() || Predicate.isStore()) {
3698 // No check required. A G_LOAD/G_STORE is an unindexed load.
3699 if (Predicate.isUnindexed())
3703 if (Predicate.isAtomic()) {
3704 if (Predicate.isAtomicOrderingMonotonic()) {
3705 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3709 if (Predicate.isAtomicOrderingAcquire()) {
3710 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Acquire");
3713 if (Predicate.isAtomicOrderingRelease()) {
3714 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Release");
3717 if (Predicate.isAtomicOrderingAcquireRelease()) {
3718 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3722 if (Predicate.isAtomicOrderingSequentiallyConsistent()) {
3723 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3724 "SequentiallyConsistent");
3728 if (Predicate.isAtomicOrderingAcquireOrStronger()) {
3729 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3730 "Acquire", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
3733 if (Predicate.isAtomicOrderingWeakerThanAcquire()) {
3734 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3735 "Acquire", AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
3739 if (Predicate.isAtomicOrderingReleaseOrStronger()) {
3740 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3741 "Release", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
3744 if (Predicate.isAtomicOrderingWeakerThanRelease()) {
3745 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3746 "Release", AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
3751 if (Predicate.hasGISelPredicateCode()) {
3752 InsnMatcher.addPredicate<GenericInstructionPredicateMatcher>(Predicate);
3756 return failedImport("Src pattern child has predicate (" +
3757 explainPredicates(Src) + ")");
3759 if (SrcGIEquivOrNull && SrcGIEquivOrNull->getValueAsBit("CheckMMOIsNonAtomic"))
3760 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("NotAtomic");
3761 else if (SrcGIEquivOrNull && SrcGIEquivOrNull->getValueAsBit("CheckMMOIsAtomic")) {
3762 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3763 "Unordered", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
3766 if (Src->isLeaf()) {
3767 Init *SrcInit = Src->getLeafValue();
3768 if (IntInit *SrcIntInit = dyn_cast<IntInit>(SrcInit)) {
3769 OperandMatcher &OM =
3770 InsnMatcher.addOperand(OpIdx++, Src->getName(), TempOpIdx);
3771 OM.addPredicate<LiteralIntOperandMatcher>(SrcIntInit->getValue());
3773 return failedImport(
3774 "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
3776 assert(SrcGIOrNull &&
3777 "Expected to have already found an equivalent Instruction");
3778 if (SrcGIOrNull->TheDef->getName() == "G_CONSTANT" ||
3779 SrcGIOrNull->TheDef->getName() == "G_FCONSTANT") {
3780 // imm/fpimm still have operands but we don't need to do anything with it
3781 // here since we don't support ImmLeaf predicates yet. However, we still
3782 // need to note the hidden operand to get GIM_CheckNumOperands correct.
3783 InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
3787 // Special case because the operand order is changed from setcc. The
3788 // predicate operand needs to be swapped from the last operand to the first
3791 unsigned NumChildren = Src->getNumChildren();
3792 bool IsFCmp = SrcGIOrNull->TheDef->getName() == "G_FCMP";
3794 if (IsFCmp || SrcGIOrNull->TheDef->getName() == "G_ICMP") {
3795 TreePatternNode *SrcChild = Src->getChild(NumChildren - 1);
3796 if (SrcChild->isLeaf()) {
3797 DefInit *DI = dyn_cast<DefInit>(SrcChild->getLeafValue());
3798 Record *CCDef = DI ? DI->getDef() : nullptr;
3799 if (!CCDef || !CCDef->isSubClassOf("CondCode"))
3800 return failedImport("Unable to handle CondCode");
3802 OperandMatcher &OM =
3803 InsnMatcher.addOperand(OpIdx++, SrcChild->getName(), TempOpIdx);
3804 StringRef PredType = IsFCmp ? CCDef->getValueAsString("FCmpPredicate") :
3805 CCDef->getValueAsString("ICmpPredicate");
3807 if (!PredType.empty()) {
3808 OM.addPredicate<CmpPredicateOperandMatcher>(std::string(PredType));
3809 // Process the other 2 operands normally.
3815 // Match the used operands (i.e. the children of the operator).
3817 SrcGIOrNull->TheDef->getName() == "G_INTRINSIC" ||
3818 SrcGIOrNull->TheDef->getName() == "G_INTRINSIC_W_SIDE_EFFECTS";
3819 const CodeGenIntrinsic *II = Src->getIntrinsicInfo(CGP);
3820 if (IsIntrinsic && !II)
3821 return failedImport("Expected IntInit containing intrinsic ID)");
3823 for (unsigned i = 0; i != NumChildren; ++i) {
3824 TreePatternNode *SrcChild = Src->getChild(i);
3826 // We need to determine the meaning of a literal integer based on the
3827 // context. If this is a field required to be an immediate (such as an
3828 // immarg intrinsic argument), the required predicates are different than
3829 // a constant which may be materialized in a register. If we have an
3830 // argument that is required to be an immediate, we should not emit an LLT
3831 // type check, and should not be looking for a G_CONSTANT defined
3833 bool OperandIsImmArg = SrcGIOrNull->isOperandImmArg(i);
3835 // SelectionDAG allows pointers to be represented with iN since it doesn't
3836 // distinguish between pointers and integers but they are different types in GlobalISel.
3837 // Coerce integers to pointers to address space 0 if the context indicates a pointer.
3839 bool OperandIsAPointer = SrcGIOrNull->isOperandAPointer(i);
3842 // For G_INTRINSIC/G_INTRINSIC_W_SIDE_EFFECTS, the operand immediately
3843 // following the defs is an intrinsic ID.
3845 OperandMatcher &OM =
3846 InsnMatcher.addOperand(OpIdx++, SrcChild->getName(), TempOpIdx);
3847 OM.addPredicate<IntrinsicIDOperandMatcher>(II);
3851 // We have to check intrinsics for llvm_anyptr_ty and immarg parameters.
3853 // Note that we have to look at the i-1th parameter, because we don't
3854 // have the intrinsic ID in the intrinsic's parameter list.
3855 OperandIsAPointer |= II->isParamAPointer(i - 1);
3856 OperandIsImmArg |= II->isParamImmArg(i - 1);
3860 importChildMatcher(Rule, InsnMatcher, SrcChild, OperandIsAPointer,
3861 OperandIsImmArg, OpIdx++, TempOpIdx))
3862 return std::move(Error);
3869 Error GlobalISelEmitter::importComplexPatternOperandMatcher(
3870 OperandMatcher &OM, Record *R, unsigned &TempOpIdx) const {
3871 const auto &ComplexPattern = ComplexPatternEquivs.find(R);
3872 if (ComplexPattern == ComplexPatternEquivs.end())
3873 return failedImport("SelectionDAG ComplexPattern (" + R->getName() +
3874 ") not mapped to GlobalISel");
3876 OM.addPredicate<ComplexPatternOperandMatcher>(OM, *ComplexPattern->second);
3878 return Error::success();
3881 // Get the name to use for a pattern operand. For an anonymous physical register
3882 // input, this should use the register name.
3883 static StringRef getSrcChildName(const TreePatternNode *SrcChild,
3885 StringRef SrcChildName = SrcChild->getName();
3886 if (SrcChildName.empty() && SrcChild->isLeaf()) {
3887 if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
3888 auto *ChildRec = ChildDefInit->getDef();
3889 if (ChildRec->isSubClassOf("Register")) {
3890 SrcChildName = ChildRec->getName();
3896 return SrcChildName;
3899 Error GlobalISelEmitter::importChildMatcher(
3900 RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
3901 const TreePatternNode *SrcChild, bool OperandIsAPointer,
3902 bool OperandIsImmArg, unsigned OpIdx, unsigned &TempOpIdx) {
3904 Record *PhysReg = nullptr;
3905 StringRef SrcChildName = getSrcChildName(SrcChild, PhysReg);
3907 OperandMatcher &OM =
3909 ? InsnMatcher.addPhysRegInput(PhysReg, OpIdx, TempOpIdx)
3910 : InsnMatcher.addOperand(OpIdx, std::string(SrcChildName), TempOpIdx);
3911 if (OM.isSameAsAnotherOperand())
3912 return Error::success();
3914 ArrayRef<TypeSetByHwMode> ChildTypes = SrcChild->getExtTypes();
3915 if (ChildTypes.size() != 1)
3916 return failedImport("Src pattern child has multiple results");
3918 // Check MBB's before the type check since they are not a known type.
3919 if (!SrcChild->isLeaf()) {
3920 if (SrcChild->getOperator()->isSubClassOf("SDNode")) {
3921 auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator());
3922 if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
3923 OM.addPredicate<MBBOperandMatcher>();
3924 return Error::success();
3926 if (SrcChild->getOperator()->getName() == "timm") {
3927 OM.addPredicate<ImmOperandMatcher>();
3928 return Error::success();
3933 // Immediate arguments have no meaningful type to check as they don't have
3935 if (!OperandIsImmArg) {
3937 OM.addTypeCheckPredicate(ChildTypes.front(), OperandIsAPointer))
3938 return failedImport(toString(std::move(Error)) + " for Src operand (" +
3939 to_string(*SrcChild) + ")");
3942 // Check for nested instructions.
3943 if (!SrcChild->isLeaf()) {
3944 if (SrcChild->getOperator()->isSubClassOf("ComplexPattern")) {
3945 // When a ComplexPattern is used as an operator, it should do the same
3946 // thing as when used as a leaf. However, the children of the operator
3947 // name the sub-operands that make up the complex operand and we must
3948 // prepare to reference them in the renderer too.
3949 unsigned RendererID = TempOpIdx;
3950 if (auto Error = importComplexPatternOperandMatcher(
3951 OM, SrcChild->getOperator(), TempOpIdx))
3954 for (unsigned i = 0, e = SrcChild->getNumChildren(); i != e; ++i) {
3955 auto *SubOperand = SrcChild->getChild(i);
3956 if (!SubOperand->getName().empty()) {
3957 if (auto Error = Rule.defineComplexSubOperand(SubOperand->getName(),
3958 SrcChild->getOperator(),
3964 return Error::success();
3967 auto MaybeInsnOperand = OM.addPredicate<InstructionOperandMatcher>(
3968 InsnMatcher.getRuleMatcher(), SrcChild->getName());
3969 if (!MaybeInsnOperand.hasValue()) {
3970 // This isn't strictly true. If the user were to provide exactly the same
3971 // matchers as the original operand then we could allow it. However, it's
3972 // simpler to not permit the redundant specification.
3973 return failedImport("Nested instruction cannot be the same as another operand");
3976 // Map the node to a gMIR instruction.
3977 InstructionOperandMatcher &InsnOperand = **MaybeInsnOperand;
3978 auto InsnMatcherOrError = createAndImportSelDAGMatcher(
3979 Rule, InsnOperand.getInsnMatcher(), SrcChild, TempOpIdx);
3980 if (auto Error = InsnMatcherOrError.takeError())
3983 return Error::success();
3986 if (SrcChild->hasAnyPredicate())
3987 return failedImport("Src pattern child has unsupported predicate");
3989 // Check for constant immediates.
3990 if (auto *ChildInt = dyn_cast<IntInit>(SrcChild->getLeafValue())) {
3991 if (OperandIsImmArg) {
3992 // Checks for argument directly in operand list
3993 OM.addPredicate<LiteralIntOperandMatcher>(ChildInt->getValue());
3995 // Checks for materialized constant
3996 OM.addPredicate<ConstantIntOperandMatcher>(ChildInt->getValue());
3998 return Error::success();
4001 // Check for def's like register classes or ComplexPattern's.
4002 if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
4003 auto *ChildRec = ChildDefInit->getDef();
4005 // Check for register classes.
4006 if (ChildRec->isSubClassOf("RegisterClass") ||
4007 ChildRec->isSubClassOf("RegisterOperand")) {
4008 OM.addPredicate<RegisterBankOperandMatcher>(
4009 Target.getRegisterClass(getInitValueAsRegClass(ChildDefInit)));
4010 return Error::success();
4013 if (ChildRec->isSubClassOf("Register")) {
4014 // This just be emitted as a copy to the specific register.
4015 ValueTypeByHwMode VT = ChildTypes.front().getValueTypeByHwMode();
4016 const CodeGenRegisterClass *RC
4017 = CGRegs.getMinimalPhysRegClass(ChildRec, &VT);
4019 return failedImport(
4020 "Could not determine physical register class of pattern source");
4023 OM.addPredicate<RegisterBankOperandMatcher>(*RC);
4024 return Error::success();
4027 // Check for ValueType.
4028 if (ChildRec->isSubClassOf("ValueType")) {
4029 // We already added a type check as standard practice so this doesn't need
4031 return Error::success();
4034 // Check for ComplexPattern's.
4035 if (ChildRec->isSubClassOf("ComplexPattern"))
4036 return importComplexPatternOperandMatcher(OM, ChildRec, TempOpIdx);
4038 if (ChildRec->isSubClassOf("ImmLeaf")) {
4039 return failedImport(
4040 "Src pattern child def is an unsupported tablegen class (ImmLeaf)");
4043 // Place holder for SRCVALUE nodes. Nothing to do here.
4044 if (ChildRec->getName() == "srcvalue")
4045 return Error::success();
4047 return failedImport(
4048 "Src pattern child def is an unsupported tablegen class");
4051 return failedImport("Src pattern child is an unsupported kind");
4054 Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderer(
4055 action_iterator InsertPt, RuleMatcher &Rule, BuildMIAction &DstMIBuilder,
4056 TreePatternNode *DstChild) {
4058 const auto &SubOperand = Rule.getComplexSubOperand(DstChild->getName());
4059 if (SubOperand.hasValue()) {
4060 DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
4061 *std::get<0>(*SubOperand), DstChild->getName(),
4062 std::get<1>(*SubOperand), std::get<2>(*SubOperand));
4066 if (!DstChild->isLeaf()) {
4067 if (DstChild->getOperator()->isSubClassOf("SDNodeXForm")) {
4068 auto Child = DstChild->getChild(0);
4069 auto I = SDNodeXFormEquivs.find(DstChild->getOperator());
4070 if (I != SDNodeXFormEquivs.end()) {
4071 Record *XFormOpc = DstChild->getOperator()->getValueAsDef("Opcode");
4072 if (XFormOpc->getName() == "timm") {
4073 // If this is a TargetConstant, there won't be a corresponding
4074 // instruction to transform. Instead, this will refer directly to an
4075 // operand in an instruction's operand list.
4076 DstMIBuilder.addRenderer<CustomOperandRenderer>(*I->second,
4079 DstMIBuilder.addRenderer<CustomRenderer>(*I->second,
4085 return failedImport("SDNodeXForm " + Child->getName() +
4086 " has no custom renderer");
4089 // We accept 'bb' here. It's an operator because BasicBlockSDNode isn't
4090 // inline, but in MI it's just another operand.
4091 if (DstChild->getOperator()->isSubClassOf("SDNode")) {
4092 auto &ChildSDNI = CGP.getSDNodeInfo(DstChild->getOperator());
4093 if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
4094 DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
4099 // Similarly, imm is an operator in TreePatternNode's view but must be
4100 // rendered as operands.
4101 // FIXME: The target should be able to choose sign-extended when appropriate
4103 if (DstChild->getOperator()->getName() == "timm") {
4104 DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
4106 } else if (DstChild->getOperator()->getName() == "imm") {
4107 DstMIBuilder.addRenderer<CopyConstantAsImmRenderer>(DstChild->getName());
4109 } else if (DstChild->getOperator()->getName() == "fpimm") {
4110 DstMIBuilder.addRenderer<CopyFConstantAsFPImmRenderer>(
4111 DstChild->getName());
4115 if (DstChild->getOperator()->isSubClassOf("Instruction")) {
4116 auto OpTy = getInstResultType(DstChild);
4118 return OpTy.takeError();
4120 unsigned TempRegID = Rule.allocateTempRegID();
4121 InsertPt = Rule.insertAction<MakeTempRegisterAction>(
4122 InsertPt, *OpTy, TempRegID);
4123 DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
4125 auto InsertPtOrError = createAndImportSubInstructionRenderer(
4126 ++InsertPt, Rule, DstChild, TempRegID);
4127 if (auto Error = InsertPtOrError.takeError())
4128 return std::move(Error);
4129 return InsertPtOrError.get();
4132 return failedImport("Dst pattern child isn't a leaf node or an MBB" + llvm::to_string(*DstChild));
4135 // It could be a specific immediate in which case we should just check for
4137 if (const IntInit *ChildIntInit =
4138 dyn_cast<IntInit>(DstChild->getLeafValue())) {
4139 DstMIBuilder.addRenderer<ImmRenderer>(ChildIntInit->getValue());
4143 // Otherwise, we're looking for a bog-standard RegisterClass operand.
4144 if (auto *ChildDefInit = dyn_cast<DefInit>(DstChild->getLeafValue())) {
4145 auto *ChildRec = ChildDefInit->getDef();
4147 ArrayRef<TypeSetByHwMode> ChildTypes = DstChild->getExtTypes();
4148 if (ChildTypes.size() != 1)
4149 return failedImport("Dst pattern child has multiple results");
4151 Optional<LLTCodeGen> OpTyOrNone = None;
4152 if (ChildTypes.front().isMachineValueType())
4153 OpTyOrNone = MVTToLLT(ChildTypes.front().getMachineValueType().SimpleTy);
4155 return failedImport("Dst operand has an unsupported type");
4157 if (ChildRec->isSubClassOf("Register")) {
4158 DstMIBuilder.addRenderer<AddRegisterRenderer>(ChildRec);
4162 if (ChildRec->isSubClassOf("RegisterClass") ||
4163 ChildRec->isSubClassOf("RegisterOperand") ||
4164 ChildRec->isSubClassOf("ValueType")) {
4165 if (ChildRec->isSubClassOf("RegisterOperand") &&
4166 !ChildRec->isValueUnset("GIZeroRegister")) {
4167 DstMIBuilder.addRenderer<CopyOrAddZeroRegRenderer>(
4168 DstChild->getName(), ChildRec->getValueAsDef("GIZeroRegister"));
4172 DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
4176 if (ChildRec->isSubClassOf("SubRegIndex")) {
4177 CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(ChildRec);
4178 DstMIBuilder.addRenderer<ImmRenderer>(SubIdx->EnumValue);
4182 if (ChildRec->isSubClassOf("ComplexPattern")) {
4183 const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
4184 if (ComplexPattern == ComplexPatternEquivs.end())
4185 return failedImport(
4186 "SelectionDAG ComplexPattern not mapped to GlobalISel");
4188 const OperandMatcher &OM = Rule.getOperandMatcher(DstChild->getName());
4189 DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
4190 *ComplexPattern->second, DstChild->getName(),
4191 OM.getAllocatedTemporariesBaseID());
4195 return failedImport(
4196 "Dst pattern child def is an unsupported tablegen class");
4199 return failedImport("Dst pattern child is an unsupported kind");
4202 Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
4203 RuleMatcher &M, InstructionMatcher &InsnMatcher, const TreePatternNode *Src,
4204 const TreePatternNode *Dst) {
4205 auto InsertPtOrError = createInstructionRenderer(M.actions_end(), M, Dst);
4206 if (auto Error = InsertPtOrError.takeError())
4207 return std::move(Error);
4209 action_iterator InsertPt = InsertPtOrError.get();
4210 BuildMIAction &DstMIBuilder = *static_cast<BuildMIAction *>(InsertPt->get());
4212 for (auto PhysInput : InsnMatcher.getPhysRegInputs()) {
4213 InsertPt = M.insertAction<BuildMIAction>(
4214 InsertPt, M.allocateOutputInsnID(),
4215 &Target.getInstruction(RK.getDef("COPY")));
4216 BuildMIAction &CopyToPhysRegMIBuilder =
4217 *static_cast<BuildMIAction *>(InsertPt->get());
4218 CopyToPhysRegMIBuilder.addRenderer<AddRegisterRenderer>(PhysInput.first,
4220 CopyToPhysRegMIBuilder.addRenderer<CopyPhysRegRenderer>(PhysInput.first);
4223 importExplicitDefRenderers(DstMIBuilder);
4225 if (auto Error = importExplicitUseRenderers(InsertPt, M, DstMIBuilder, Dst)
4227 return std::move(Error);
4229 return DstMIBuilder;
4232 Expected<action_iterator>
4233 GlobalISelEmitter::createAndImportSubInstructionRenderer(
4234 const action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst,
4235 unsigned TempRegID) {
4236 auto InsertPtOrError = createInstructionRenderer(InsertPt, M, Dst);
4238 // TODO: Assert there's exactly one result.
4240 if (auto Error = InsertPtOrError.takeError())
4241 return std::move(Error);
4243 BuildMIAction &DstMIBuilder =
4244 *static_cast<BuildMIAction *>(InsertPtOrError.get()->get());
4246 // Assign the result to TempReg.
4247 DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID, true);
4250 importExplicitUseRenderers(InsertPtOrError.get(), M, DstMIBuilder, Dst);
4251 if (auto Error = InsertPtOrError.takeError())
4252 return std::move(Error);
4254 // We need to make sure that when we import an INSERT_SUBREG as a
4255 // subinstruction that it ends up being constrained to the correct super
4256 // register and subregister classes.
4257 auto OpName = Target.getInstruction(Dst->getOperator()).TheDef->getName();
4258 if (OpName == "INSERT_SUBREG") {
4259 auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
4261 return failedImport(
4262 "Cannot infer register class from INSERT_SUBREG operand #1");
4263 Optional<const CodeGenRegisterClass *> SuperClass =
4264 inferSuperRegisterClassForNode(Dst->getExtType(0), Dst->getChild(0),
4267 return failedImport(
4268 "Cannot infer register class for INSERT_SUBREG operand #0");
4269 // The destination and the super register source of an INSERT_SUBREG must
4270 // be the same register class.
4271 M.insertAction<ConstrainOperandToRegClassAction>(
4272 InsertPt, DstMIBuilder.getInsnID(), 0, **SuperClass);
4273 M.insertAction<ConstrainOperandToRegClassAction>(
4274 InsertPt, DstMIBuilder.getInsnID(), 1, **SuperClass);
4275 M.insertAction<ConstrainOperandToRegClassAction>(
4276 InsertPt, DstMIBuilder.getInsnID(), 2, **SubClass);
4277 return InsertPtOrError.get();
4280 if (OpName == "EXTRACT_SUBREG") {
4281 // EXTRACT_SUBREG selects into a subregister COPY but unlike most
4282 // instructions, the result register class is controlled by the
4283 // subregisters of the operand. As a result, we must constrain the result
4284 // class rather than check that it's already the right one.
4285 auto SuperClass = inferRegClassFromPattern(Dst->getChild(0));
4287 return failedImport(
4288 "Cannot infer register class from EXTRACT_SUBREG operand #0");
4290 auto SubIdx = inferSubRegIndexForNode(Dst->getChild(1));
4292 return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
4294 const auto SrcRCDstRCPair =
4295 (*SuperClass)->getMatchingSubClassWithSubRegs(CGRegs, *SubIdx);
4296 assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
4297 M.insertAction<ConstrainOperandToRegClassAction>(
4298 InsertPt, DstMIBuilder.getInsnID(), 0, *SrcRCDstRCPair->second);
4299 M.insertAction<ConstrainOperandToRegClassAction>(
4300 InsertPt, DstMIBuilder.getInsnID(), 1, *SrcRCDstRCPair->first);
4302 // We're done with this pattern! It's eligible for GISel emission; return
4304 return InsertPtOrError.get();
4307 // Similar to INSERT_SUBREG, we also have to handle SUBREG_TO_REG as a
4309 if (OpName == "SUBREG_TO_REG") {
4310 auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
4312 return failedImport(
4313 "Cannot infer register class from SUBREG_TO_REG child #1");
4314 auto SuperClass = inferSuperRegisterClass(Dst->getExtType(0),
4317 return failedImport(
4318 "Cannot infer register class for SUBREG_TO_REG operand #0");
4319 M.insertAction<ConstrainOperandToRegClassAction>(
4320 InsertPt, DstMIBuilder.getInsnID(), 0, **SuperClass);
4321 M.insertAction<ConstrainOperandToRegClassAction>(
4322 InsertPt, DstMIBuilder.getInsnID(), 2, **SubClass);
4323 return InsertPtOrError.get();
4326 if (OpName == "REG_SEQUENCE") {
4327 auto SuperClass = inferRegClassFromPattern(Dst->getChild(0));
4328 M.insertAction<ConstrainOperandToRegClassAction>(
4329 InsertPt, DstMIBuilder.getInsnID(), 0, **SuperClass);
4331 unsigned Num = Dst->getNumChildren();
4332 for (unsigned I = 1; I != Num; I += 2) {
4333 TreePatternNode *SubRegChild = Dst->getChild(I + 1);
4335 auto SubIdx = inferSubRegIndexForNode(SubRegChild);
4337 return failedImport("REG_SEQUENCE child is not a subreg index");
4339 const auto SrcRCDstRCPair =
4340 (*SuperClass)->getMatchingSubClassWithSubRegs(CGRegs, *SubIdx);
4341 assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
4342 M.insertAction<ConstrainOperandToRegClassAction>(
4343 InsertPt, DstMIBuilder.getInsnID(), I, *SrcRCDstRCPair->second);
4346 return InsertPtOrError.get();
4349 M.insertAction<ConstrainOperandsToDefinitionAction>(InsertPt,
4350 DstMIBuilder.getInsnID());
4351 return InsertPtOrError.get();
4354 Expected<action_iterator> GlobalISelEmitter::createInstructionRenderer(
4355 action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst) {
4356 Record *DstOp = Dst->getOperator();
4357 if (!DstOp->isSubClassOf("Instruction")) {
4358 if (DstOp->isSubClassOf("ValueType"))
4359 return failedImport(
4360 "Pattern operator isn't an instruction (it's a ValueType)");
4361 return failedImport("Pattern operator isn't an instruction");
4363 CodeGenInstruction *DstI = &Target.getInstruction(DstOp);
4365 // COPY_TO_REGCLASS is just a copy with a ConstrainOperandToRegClassAction
4366 // attached. Similarly for EXTRACT_SUBREG except that's a subregister copy.
4367 StringRef Name = DstI->TheDef->getName();
4368 if (Name == "COPY_TO_REGCLASS" || Name == "EXTRACT_SUBREG")
4369 DstI = &Target.getInstruction(RK.getDef("COPY"));
4371 return M.insertAction<BuildMIAction>(InsertPt, M.allocateOutputInsnID(),
4375 void GlobalISelEmitter::importExplicitDefRenderers(
4376 BuildMIAction &DstMIBuilder) {
4377 const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
4378 for (unsigned I = 0; I < DstI->Operands.NumDefs; ++I) {
4379 const CGIOperandList::OperandInfo &DstIOperand = DstI->Operands[I];
4380 DstMIBuilder.addRenderer<CopyRenderer>(DstIOperand.Name);
4384 Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderers(
4385 action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
4386 const llvm::TreePatternNode *Dst) {
4387 const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
4388 CodeGenInstruction *OrigDstI = &Target.getInstruction(Dst->getOperator());
4390 StringRef Name = OrigDstI->TheDef->getName();
4391 unsigned ExpectedDstINumUses = Dst->getNumChildren();
4393 // EXTRACT_SUBREG needs to use a subregister COPY.
4394 if (Name == "EXTRACT_SUBREG") {
4395 DefInit *SubRegInit = dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue());
4397 return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
4399 CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
4400 TreePatternNode *ValChild = Dst->getChild(0);
4401 if (!ValChild->isLeaf()) {
4402 // We really have to handle the source instruction, and then insert a
4403 // copy from the subregister.
4404 auto ExtractSrcTy = getInstResultType(ValChild);
4406 return ExtractSrcTy.takeError();
4408 unsigned TempRegID = M.allocateTempRegID();
4409 InsertPt = M.insertAction<MakeTempRegisterAction>(
4410 InsertPt, *ExtractSrcTy, TempRegID);
4412 auto InsertPtOrError = createAndImportSubInstructionRenderer(
4413 ++InsertPt, M, ValChild, TempRegID);
4414 if (auto Error = InsertPtOrError.takeError())
4415 return std::move(Error);
4417 DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID, false, SubIdx);
4421 // If this is a source operand, this is just a subregister copy.
4422 Record *RCDef = getInitValueAsRegClass(ValChild->getLeafValue());
4424 return failedImport("EXTRACT_SUBREG child #0 could not "
4425 "be coerced to a register class");
4427 CodeGenRegisterClass *RC = CGRegs.getRegClass(RCDef);
4429 const auto SrcRCDstRCPair =
4430 RC->getMatchingSubClassWithSubRegs(CGRegs, SubIdx);
4431 if (SrcRCDstRCPair.hasValue()) {
4432 assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
4433 if (SrcRCDstRCPair->first != RC)
4434 return failedImport("EXTRACT_SUBREG requires an additional COPY");
4437 DstMIBuilder.addRenderer<CopySubRegRenderer>(Dst->getChild(0)->getName(),
4442 if (Name == "REG_SEQUENCE") {
4443 if (!Dst->getChild(0)->isLeaf())
4444 return failedImport("REG_SEQUENCE child #0 is not a leaf");
4446 Record *RCDef = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
4448 return failedImport("REG_SEQUENCE child #0 could not "
4449 "be coerced to a register class");
4451 if ((ExpectedDstINumUses - 1) % 2 != 0)
4452 return failedImport("Malformed REG_SEQUENCE");
4454 for (unsigned I = 1; I != ExpectedDstINumUses; I += 2) {
4455 TreePatternNode *ValChild = Dst->getChild(I);
4456 TreePatternNode *SubRegChild = Dst->getChild(I + 1);
4458 if (DefInit *SubRegInit =
4459 dyn_cast<DefInit>(SubRegChild->getLeafValue())) {
4460 CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
4462 auto InsertPtOrError =
4463 importExplicitUseRenderer(InsertPt, M, DstMIBuilder, ValChild);
4464 if (auto Error = InsertPtOrError.takeError())
4465 return std::move(Error);
4466 InsertPt = InsertPtOrError.get();
4467 DstMIBuilder.addRenderer<SubRegIndexRenderer>(SubIdx);
4474 // Render the explicit uses.
4475 unsigned DstINumUses = OrigDstI->Operands.size() - OrigDstI->Operands.NumDefs;
4476 if (Name == "COPY_TO_REGCLASS") {
4477 DstINumUses--; // Ignore the class constraint.
4478 ExpectedDstINumUses--;
4481 // NumResults - This is the number of results produced by the instruction in
4483 unsigned NumResults = OrigDstI->Operands.NumDefs;
4485 // Number of operands we know the output instruction must have. If it is
4486 // variadic, we could have more operands.
4487 unsigned NumFixedOperands = DstI->Operands.size();
4489 // Loop over all of the fixed operands of the instruction pattern, emitting
4490 // code to fill them all in. The node 'N' usually has number children equal to
4491 // the number of input operands of the instruction. However, in cases where
4492 // there are predicate operands for an instruction, we need to fill in the
4493 // 'execute always' values. Match up the node operands to the instruction
4494 // operands to do this.
4497 // Similarly to the code in TreePatternNode::ApplyTypeConstraints, count the
4498 // number of operands at the end of the list which have default values.
4499 // Those can come from the pattern if it provides enough arguments, or be
4500 // filled in with the default if the pattern hasn't provided them. But any
4501 // operand with a default value _before_ the last mandatory one will be
4502 // filled in with their defaults unconditionally.
4503 unsigned NonOverridableOperands = NumFixedOperands;
4504 while (NonOverridableOperands > NumResults &&
4505 CGP.operandHasDefault(DstI->Operands[NonOverridableOperands - 1].Rec))
4506 --NonOverridableOperands;
4508 unsigned NumDefaultOps = 0;
4509 for (unsigned I = 0; I != DstINumUses; ++I) {
4510 unsigned InstOpNo = DstI->Operands.NumDefs + I;
4512 // Determine what to emit for this operand.
4513 Record *OperandNode = DstI->Operands[InstOpNo].Rec;
4515 // If the operand has default values, introduce them now.
4516 if (CGP.operandHasDefault(OperandNode) &&
4517 (InstOpNo < NonOverridableOperands || Child >= Dst->getNumChildren())) {
4518 // This is a predicate or optional def operand which the pattern has not
4519 // overridden, or which we aren't letting it override; emit the 'default
4522 const CGIOperandList::OperandInfo &DstIOperand = DstI->Operands[InstOpNo];
4523 DagInit *DefaultOps = DstIOperand.Rec->getValueAsDag("DefaultOps");
4524 if (auto Error = importDefaultOperandRenderers(
4525 InsertPt, M, DstMIBuilder, DefaultOps))
4526 return std::move(Error);
4531 auto InsertPtOrError = importExplicitUseRenderer(InsertPt, M, DstMIBuilder,
4532 Dst->getChild(Child));
4533 if (auto Error = InsertPtOrError.takeError())
4534 return std::move(Error);
4535 InsertPt = InsertPtOrError.get();
4539 if (NumDefaultOps + ExpectedDstINumUses != DstINumUses)
4540 return failedImport("Expected " + llvm::to_string(DstINumUses) +
4541 " used operands but found " +
4542 llvm::to_string(ExpectedDstINumUses) +
4543 " explicit ones and " + llvm::to_string(NumDefaultOps) +
4549 Error GlobalISelEmitter::importDefaultOperandRenderers(
4550 action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
4551 DagInit *DefaultOps) const {
4552 for (const auto *DefaultOp : DefaultOps->getArgs()) {
4553 Optional<LLTCodeGen> OpTyOrNone = None;
4555 // Look through ValueType operators.
4556 if (const DagInit *DefaultDagOp = dyn_cast<DagInit>(DefaultOp)) {
4557 if (const DefInit *DefaultDagOperator =
4558 dyn_cast<DefInit>(DefaultDagOp->getOperator())) {
4559 if (DefaultDagOperator->getDef()->isSubClassOf("ValueType")) {
4560 OpTyOrNone = MVTToLLT(getValueType(
4561 DefaultDagOperator->getDef()));
4562 DefaultOp = DefaultDagOp->getArg(0);
4567 if (const DefInit *DefaultDefOp = dyn_cast<DefInit>(DefaultOp)) {
4568 auto Def = DefaultDefOp->getDef();
4569 if (Def->getName() == "undef_tied_input") {
4570 unsigned TempRegID = M.allocateTempRegID();
4571 M.insertAction<MakeTempRegisterAction>(
4572 InsertPt, OpTyOrNone.getValue(), TempRegID);
4573 InsertPt = M.insertAction<BuildMIAction>(
4574 InsertPt, M.allocateOutputInsnID(),
4575 &Target.getInstruction(RK.getDef("IMPLICIT_DEF")));
4576 BuildMIAction &IDMIBuilder = *static_cast<BuildMIAction *>(
4578 IDMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
4579 DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
4581 DstMIBuilder.addRenderer<AddRegisterRenderer>(Def);
4586 if (const IntInit *DefaultIntOp = dyn_cast<IntInit>(DefaultOp)) {
4587 DstMIBuilder.addRenderer<ImmRenderer>(DefaultIntOp->getValue());
4591 return failedImport("Could not add default op");
4594 return Error::success();
4597 Error GlobalISelEmitter::importImplicitDefRenderers(
4598 BuildMIAction &DstMIBuilder,
4599 const std::vector<Record *> &ImplicitDefs) const {
4600 if (!ImplicitDefs.empty())
4601 return failedImport("Pattern defines a physical register");
4602 return Error::success();
4605 Optional<const CodeGenRegisterClass *>
4606 GlobalISelEmitter::getRegClassFromLeaf(TreePatternNode *Leaf) {
4607 assert(Leaf && "Expected node?");
4608 assert(Leaf->isLeaf() && "Expected leaf?");
4609 Record *RCRec = getInitValueAsRegClass(Leaf->getLeafValue());
4612 CodeGenRegisterClass *RC = CGRegs.getRegClass(RCRec);
4618 Optional<const CodeGenRegisterClass *>
4619 GlobalISelEmitter::inferRegClassFromPattern(TreePatternNode *N) {
4624 return getRegClassFromLeaf(N);
4626 // We don't have a leaf node, so we have to try and infer something. Check
4627 // that we have an instruction that we an infer something from.
4629 // Only handle things that produce a single type.
4630 if (N->getNumTypes() != 1)
4632 Record *OpRec = N->getOperator();
4634 // We only want instructions.
4635 if (!OpRec->isSubClassOf("Instruction"))
4638 // Don't want to try and infer things when there could potentially be more
4639 // than one candidate register class.
4640 auto &Inst = Target.getInstruction(OpRec);
4641 if (Inst.Operands.NumDefs > 1)
4644 // Handle any special-case instructions which we can safely infer register
4646 StringRef InstName = Inst.TheDef->getName();
4647 bool IsRegSequence = InstName == "REG_SEQUENCE";
4648 if (IsRegSequence || InstName == "COPY_TO_REGCLASS") {
4649 // If we have a COPY_TO_REGCLASS, then we need to handle it specially. It
4650 // has the desired register class as the first child.
4651 TreePatternNode *RCChild = N->getChild(IsRegSequence ? 0 : 1);
4652 if (!RCChild->isLeaf())
4654 return getRegClassFromLeaf(RCChild);
4657 // Handle destination record types that we can safely infer a register class
4659 const auto &DstIOperand = Inst.Operands[0];
4660 Record *DstIOpRec = DstIOperand.Rec;
4661 if (DstIOpRec->isSubClassOf("RegisterOperand")) {
4662 DstIOpRec = DstIOpRec->getValueAsDef("RegClass");
4663 const CodeGenRegisterClass &RC = Target.getRegisterClass(DstIOpRec);
4667 if (DstIOpRec->isSubClassOf("RegisterClass")) {
4668 const CodeGenRegisterClass &RC = Target.getRegisterClass(DstIOpRec);
4675 Optional<const CodeGenRegisterClass *>
4676 GlobalISelEmitter::inferSuperRegisterClass(const TypeSetByHwMode &Ty,
4677 TreePatternNode *SubRegIdxNode) {
4678 assert(SubRegIdxNode && "Expected subregister index node!");
4679 // We need a ValueTypeByHwMode for getSuperRegForSubReg.
4680 if (!Ty.isValueTypeByHwMode(false))
4682 if (!SubRegIdxNode->isLeaf())
4684 DefInit *SubRegInit = dyn_cast<DefInit>(SubRegIdxNode->getLeafValue());
4687 CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
4689 // Use the information we found above to find a minimal register class which
4690 // supports the subregister and type we want.
4692 Target.getSuperRegForSubReg(Ty.getValueTypeByHwMode(), CGRegs, SubIdx);
4698 Optional<const CodeGenRegisterClass *>
4699 GlobalISelEmitter::inferSuperRegisterClassForNode(
4700 const TypeSetByHwMode &Ty, TreePatternNode *SuperRegNode,
4701 TreePatternNode *SubRegIdxNode) {
4702 assert(SuperRegNode && "Expected super register node!");
4703 // Check if we already have a defined register class for the super register
4704 // node. If we do, then we should preserve that rather than inferring anything
4705 // from the subregister index node. We can assume that whoever wrote the
4706 // pattern in the first place made sure that the super register and
4707 // subregister are compatible.
4708 if (Optional<const CodeGenRegisterClass *> SuperRegisterClass =
4709 inferRegClassFromPattern(SuperRegNode))
4710 return *SuperRegisterClass;
4711 return inferSuperRegisterClass(Ty, SubRegIdxNode);
4714 Optional<CodeGenSubRegIndex *>
4715 GlobalISelEmitter::inferSubRegIndexForNode(TreePatternNode *SubRegIdxNode) {
4716 if (!SubRegIdxNode->isLeaf())
4719 DefInit *SubRegInit = dyn_cast<DefInit>(SubRegIdxNode->getLeafValue());
4722 return CGRegs.getSubRegIdx(SubRegInit->getDef());
4725 Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
4726 // Keep track of the matchers and actions to emit.
4727 int Score = P.getPatternComplexity(CGP);
4728 RuleMatcher M(P.getSrcRecord()->getLoc());
4729 RuleMatcherScores[M.getRuleID()] = Score;
4730 M.addAction<DebugCommentAction>(llvm::to_string(*P.getSrcPattern()) +
4732 llvm::to_string(*P.getDstPattern()));
4734 if (auto Error = importRulePredicates(M, P.getPredicates()))
4735 return std::move(Error);
4737 // Next, analyze the pattern operators.
4738 TreePatternNode *Src = P.getSrcPattern();
4739 TreePatternNode *Dst = P.getDstPattern();
4741 // If the root of either pattern isn't a simple operator, ignore it.
4742 if (auto Err = isTrivialOperatorNode(Dst))
4743 return failedImport("Dst pattern root isn't a trivial operator (" +
4744 toString(std::move(Err)) + ")");
4745 if (auto Err = isTrivialOperatorNode(Src))
4746 return failedImport("Src pattern root isn't a trivial operator (" +
4747 toString(std::move(Err)) + ")");
4749 // The different predicates and matchers created during
4750 // addInstructionMatcher use the RuleMatcher M to set up their
4751 // instruction ID (InsnVarID) that are going to be used when
4752 // M is going to be emitted.
4753 // However, the code doing the emission still relies on the IDs
4754 // returned during that process by the RuleMatcher when issuing
4755 // the recordInsn opcodes.
4757 // 1. The order in which we created the predicates
4758 // and such must be the same as the order in which we emit them,
4760 // 2. We need to reset the generation of the IDs in M somewhere between
4761 // addInstructionMatcher and emit
4763 // FIXME: Long term, we don't want to have to rely on this implicit
4764 // naming being the same. One possible solution would be to have
4765 // explicit operator for operation capture and reference those.
4766 // The plus side is that it would expose opportunities to share
4767 // the capture accross rules. The downside is that it would
4768 // introduce a dependency between predicates (captures must happen
4769 // before their first use.)
4770 InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher(Src->getName());
4771 unsigned TempOpIdx = 0;
4772 auto InsnMatcherOrError =
4773 createAndImportSelDAGMatcher(M, InsnMatcherTemp, Src, TempOpIdx);
4774 if (auto Error = InsnMatcherOrError.takeError())
4775 return std::move(Error);
4776 InstructionMatcher &InsnMatcher = InsnMatcherOrError.get();
4778 if (Dst->isLeaf()) {
4779 Record *RCDef = getInitValueAsRegClass(Dst->getLeafValue());
4781 const CodeGenRegisterClass &RC = Target.getRegisterClass(RCDef);
4783 // We need to replace the def and all its uses with the specified
4784 // operand. However, we must also insert COPY's wherever needed.
4785 // For now, emit a copy and let the register allocator clean up.
4786 auto &DstI = Target.getInstruction(RK.getDef("COPY"));
4787 const auto &DstIOperand = DstI.Operands[0];
4789 OperandMatcher &OM0 = InsnMatcher.getOperand(0);
4790 OM0.setSymbolicName(DstIOperand.Name);
4791 M.defineOperand(OM0.getSymbolicName(), OM0);
4792 OM0.addPredicate<RegisterBankOperandMatcher>(RC);
4794 auto &DstMIBuilder =
4795 M.addAction<BuildMIAction>(M.allocateOutputInsnID(), &DstI);
4796 DstMIBuilder.addRenderer<CopyRenderer>(DstIOperand.Name);
4797 DstMIBuilder.addRenderer<CopyRenderer>(Dst->getName());
4798 M.addAction<ConstrainOperandToRegClassAction>(0, 0, RC);
4800 // We're done with this pattern! It's eligible for GISel emission; return
4802 ++NumPatternImported;
4803 return std::move(M);
4806 return failedImport("Dst pattern root isn't a known leaf");
4809 // Start with the defined operands (i.e., the results of the root operator).
4810 Record *DstOp = Dst->getOperator();
4811 if (!DstOp->isSubClassOf("Instruction"))
4812 return failedImport("Pattern operator isn't an instruction");
4814 auto &DstI = Target.getInstruction(DstOp);
4815 StringRef DstIName = DstI.TheDef->getName();
4817 if (DstI.Operands.NumDefs != Src->getExtTypes().size())
4818 return failedImport("Src pattern results and dst MI defs are different (" +
4819 to_string(Src->getExtTypes().size()) + " def(s) vs " +
4820 to_string(DstI.Operands.NumDefs) + " def(s))");
4822 // The root of the match also has constraints on the register bank so that it
4823 // matches the result instruction.
4825 for (const TypeSetByHwMode &VTy : Src->getExtTypes()) {
4828 const auto &DstIOperand = DstI.Operands[OpIdx];
4829 Record *DstIOpRec = DstIOperand.Rec;
4830 if (DstIName == "COPY_TO_REGCLASS") {
4831 DstIOpRec = getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());
4833 if (DstIOpRec == nullptr)
4834 return failedImport(
4835 "COPY_TO_REGCLASS operand #1 isn't a register class");
4836 } else if (DstIName == "REG_SEQUENCE") {
4837 DstIOpRec = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
4838 if (DstIOpRec == nullptr)
4839 return failedImport("REG_SEQUENCE operand #0 isn't a register class");
4840 } else if (DstIName == "EXTRACT_SUBREG") {
4841 auto InferredClass = inferRegClassFromPattern(Dst->getChild(0));
4843 return failedImport("Could not infer class for EXTRACT_SUBREG operand #0");
4845 // We can assume that a subregister is in the same bank as it's super
4847 DstIOpRec = (*InferredClass)->getDef();
4848 } else if (DstIName == "INSERT_SUBREG") {
4849 auto MaybeSuperClass = inferSuperRegisterClassForNode(
4850 VTy, Dst->getChild(0), Dst->getChild(2));
4851 if (!MaybeSuperClass)
4852 return failedImport(
4853 "Cannot infer register class for INSERT_SUBREG operand #0");
4854 // Move to the next pattern here, because the register class we found
4855 // doesn't necessarily have a record associated with it. So, we can't
4856 // set DstIOpRec using this.
4857 OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
4858 OM.setSymbolicName(DstIOperand.Name);
4859 M.defineOperand(OM.getSymbolicName(), OM);
4860 OM.addPredicate<RegisterBankOperandMatcher>(**MaybeSuperClass);
4863 } else if (DstIName == "SUBREG_TO_REG") {
4864 auto MaybeRegClass = inferSuperRegisterClass(VTy, Dst->getChild(2));
4866 return failedImport(
4867 "Cannot infer register class for SUBREG_TO_REG operand #0");
4868 OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
4869 OM.setSymbolicName(DstIOperand.Name);
4870 M.defineOperand(OM.getSymbolicName(), OM);
4871 OM.addPredicate<RegisterBankOperandMatcher>(**MaybeRegClass);
4874 } else if (DstIOpRec->isSubClassOf("RegisterOperand"))
4875 DstIOpRec = DstIOpRec->getValueAsDef("RegClass");
4876 else if (!DstIOpRec->isSubClassOf("RegisterClass"))
4877 return failedImport("Dst MI def isn't a register class" +
4880 OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
4881 OM.setSymbolicName(DstIOperand.Name);
4882 M.defineOperand(OM.getSymbolicName(), OM);
4883 OM.addPredicate<RegisterBankOperandMatcher>(
4884 Target.getRegisterClass(DstIOpRec));
4888 auto DstMIBuilderOrError =
4889 createAndImportInstructionRenderer(M, InsnMatcher, Src, Dst);
4890 if (auto Error = DstMIBuilderOrError.takeError())
4891 return std::move(Error);
4892 BuildMIAction &DstMIBuilder = DstMIBuilderOrError.get();
4894 // Render the implicit defs.
4895 // These are only added to the root of the result.
4896 if (auto Error = importImplicitDefRenderers(DstMIBuilder, P.getDstRegs()))
4897 return std::move(Error);
4899 DstMIBuilder.chooseInsnToMutate(M);
4901 // Constrain the registers to classes. This is normally derived from the
4902 // emitted instruction but a few instructions require special handling.
4903 if (DstIName == "COPY_TO_REGCLASS") {
4904 // COPY_TO_REGCLASS does not provide operand constraints itself but the
4905 // result is constrained to the class given by the second child.
4907 getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());
4909 if (DstIOpRec == nullptr)
4910 return failedImport("COPY_TO_REGCLASS operand #1 isn't a register class");
4912 M.addAction<ConstrainOperandToRegClassAction>(
4913 0, 0, Target.getRegisterClass(DstIOpRec));
4915 // We're done with this pattern! It's eligible for GISel emission; return
4917 ++NumPatternImported;
4918 return std::move(M);
4921 if (DstIName == "EXTRACT_SUBREG") {
4922 auto SuperClass = inferRegClassFromPattern(Dst->getChild(0));
4924 return failedImport(
4925 "Cannot infer register class from EXTRACT_SUBREG operand #0");
4927 auto SubIdx = inferSubRegIndexForNode(Dst->getChild(1));
4929 return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
4931 // It would be nice to leave this constraint implicit but we're required
4932 // to pick a register class so constrain the result to a register class
4933 // that can hold the correct MVT.
4935 // FIXME: This may introduce an extra copy if the chosen class doesn't
4936 // actually contain the subregisters.
4937 assert(Src->getExtTypes().size() == 1 &&
4938 "Expected Src of EXTRACT_SUBREG to have one result type");
4940 const auto SrcRCDstRCPair =
4941 (*SuperClass)->getMatchingSubClassWithSubRegs(CGRegs, *SubIdx);
4942 if (!SrcRCDstRCPair) {
4943 return failedImport("subreg index is incompatible "
4944 "with inferred reg class");
4947 assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
4948 M.addAction<ConstrainOperandToRegClassAction>(0, 0, *SrcRCDstRCPair->second);
4949 M.addAction<ConstrainOperandToRegClassAction>(0, 1, *SrcRCDstRCPair->first);
4951 // We're done with this pattern! It's eligible for GISel emission; return
4953 ++NumPatternImported;
4954 return std::move(M);
4957 if (DstIName == "INSERT_SUBREG") {
4958 assert(Src->getExtTypes().size() == 1 &&
4959 "Expected Src of INSERT_SUBREG to have one result type");
4960 // We need to constrain the destination, a super regsister source, and a
4961 // subregister source.
4962 auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
4964 return failedImport(
4965 "Cannot infer register class from INSERT_SUBREG operand #1");
4966 auto SuperClass = inferSuperRegisterClassForNode(
4967 Src->getExtType(0), Dst->getChild(0), Dst->getChild(2));
4969 return failedImport(
4970 "Cannot infer register class for INSERT_SUBREG operand #0");
4971 M.addAction<ConstrainOperandToRegClassAction>(0, 0, **SuperClass);
4972 M.addAction<ConstrainOperandToRegClassAction>(0, 1, **SuperClass);
4973 M.addAction<ConstrainOperandToRegClassAction>(0, 2, **SubClass);
4974 ++NumPatternImported;
4975 return std::move(M);
4978 if (DstIName == "SUBREG_TO_REG") {
4979 // We need to constrain the destination and subregister source.
4980 assert(Src->getExtTypes().size() == 1 &&
4981 "Expected Src of SUBREG_TO_REG to have one result type");
4983 // Attempt to infer the subregister source from the first child. If it has
4984 // an explicitly given register class, we'll use that. Otherwise, we will
4986 auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
4988 return failedImport(
4989 "Cannot infer register class from SUBREG_TO_REG child #1");
4990 // We don't have a child to look at that might have a super register node.
4992 inferSuperRegisterClass(Src->getExtType(0), Dst->getChild(2));
4994 return failedImport(
4995 "Cannot infer register class for SUBREG_TO_REG operand #0");
4996 M.addAction<ConstrainOperandToRegClassAction>(0, 0, **SuperClass);
4997 M.addAction<ConstrainOperandToRegClassAction>(0, 2, **SubClass);
4998 ++NumPatternImported;
4999 return std::move(M);
5002 if (DstIName == "REG_SEQUENCE") {
5003 auto SuperClass = inferRegClassFromPattern(Dst->getChild(0));
5005 M.addAction<ConstrainOperandToRegClassAction>(0, 0, **SuperClass);
5007 unsigned Num = Dst->getNumChildren();
5008 for (unsigned I = 1; I != Num; I += 2) {
5009 TreePatternNode *SubRegChild = Dst->getChild(I + 1);
5011 auto SubIdx = inferSubRegIndexForNode(SubRegChild);
5013 return failedImport("REG_SEQUENCE child is not a subreg index");
5015 const auto SrcRCDstRCPair =
5016 (*SuperClass)->getMatchingSubClassWithSubRegs(CGRegs, *SubIdx);
5018 M.addAction<ConstrainOperandToRegClassAction>(0, I,
5019 *SrcRCDstRCPair->second);
5022 ++NumPatternImported;
5023 return std::move(M);
5026 M.addAction<ConstrainOperandsToDefinitionAction>(0);
5028 // We're done with this pattern! It's eligible for GISel emission; return it.
5029 ++NumPatternImported;
5030 return std::move(M);
5033 // Emit imm predicate table and an enum to reference them with.
5034 // The 'Predicate_' part of the name is redundant but eliminating it is more
5035 // trouble than it's worth.
5036 void GlobalISelEmitter::emitCxxPredicateFns(
5037 raw_ostream &OS, StringRef CodeFieldName, StringRef TypeIdentifier,
5038 StringRef ArgType, StringRef ArgName, StringRef AdditionalDeclarations,
5039 std::function<bool(const Record *R)> Filter) {
5040 std::vector<const Record *> MatchedRecords;
5041 const auto &Defs = RK.getAllDerivedDefinitions("PatFrag");
5042 std::copy_if(Defs.begin(), Defs.end(), std::back_inserter(MatchedRecords),
5043 [&](Record *Record) {
5044 return !Record->getValueAsString(CodeFieldName).empty() &&
5048 if (!MatchedRecords.empty()) {
5049 OS << "// PatFrag predicates.\n"
5051 std::string EnumeratorSeparator =
5052 (" = GIPFP_" + TypeIdentifier + "_Invalid + 1,\n").str();
5053 for (const auto *Record : MatchedRecords) {
5054 OS << " GIPFP_" << TypeIdentifier << "_Predicate_" << Record->getName()
5055 << EnumeratorSeparator;
5056 EnumeratorSeparator = ",\n";
5061 OS << "bool " << Target.getName() << "InstructionSelector::test" << ArgName
5062 << "Predicate_" << TypeIdentifier << "(unsigned PredicateID, " << ArgType << " "
5063 << ArgName << ") const {\n"
5064 << AdditionalDeclarations;
5065 if (!AdditionalDeclarations.empty())
5067 if (!MatchedRecords.empty())
5068 OS << " switch (PredicateID) {\n";
5069 for (const auto *Record : MatchedRecords) {
5070 OS << " case GIPFP_" << TypeIdentifier << "_Predicate_"
5071 << Record->getName() << ": {\n"
5072 << " " << Record->getValueAsString(CodeFieldName) << "\n"
5073 << " llvm_unreachable(\"" << CodeFieldName
5074 << " should have returned\");\n"
5075 << " return false;\n"
5078 if (!MatchedRecords.empty())
5080 OS << " llvm_unreachable(\"Unknown predicate\");\n"
5081 << " return false;\n"
5085 void GlobalISelEmitter::emitImmPredicateFns(
5086 raw_ostream &OS, StringRef TypeIdentifier, StringRef ArgType,
5087 std::function<bool(const Record *R)> Filter) {
5088 return emitCxxPredicateFns(OS, "ImmediateCode", TypeIdentifier, ArgType,
5092 void GlobalISelEmitter::emitMIPredicateFns(raw_ostream &OS) {
5093 return emitCxxPredicateFns(
5094 OS, "GISelPredicateCode", "MI", "const MachineInstr &", "MI",
5095 " const MachineFunction &MF = *MI.getParent()->getParent();\n"
5096 " const MachineRegisterInfo &MRI = MF.getRegInfo();\n"
5098 [](const Record *R) { return true; });
5101 template <class GroupT>
5102 std::vector<Matcher *> GlobalISelEmitter::optimizeRules(
5103 ArrayRef<Matcher *> Rules,
5104 std::vector<std::unique_ptr<Matcher>> &MatcherStorage) {
5106 std::vector<Matcher *> OptRules;
5107 std::unique_ptr<GroupT> CurrentGroup = std::make_unique<GroupT>();
5108 assert(CurrentGroup->empty() && "Newly created group isn't empty!");
5109 unsigned NumGroups = 0;
5111 auto ProcessCurrentGroup = [&]() {
5112 if (CurrentGroup->empty())
5113 // An empty group is good to be reused:
5116 // If the group isn't large enough to provide any benefit, move all the
5117 // added rules out of it and make sure to re-create the group to properly
5118 // re-initialize it:
5119 if (CurrentGroup->size() < 2)
5120 for (Matcher *M : CurrentGroup->matchers())
5121 OptRules.push_back(M);
5123 CurrentGroup->finalize();
5124 OptRules.push_back(CurrentGroup.get());
5125 MatcherStorage.emplace_back(std::move(CurrentGroup));
5128 CurrentGroup = std::make_unique<GroupT>();
5130 for (Matcher *Rule : Rules) {
5131 // Greedily add as many matchers as possible to the current group:
5132 if (CurrentGroup->addMatcher(*Rule))
5135 ProcessCurrentGroup();
5136 assert(CurrentGroup->empty() && "A group wasn't properly re-initialized");
5138 // Try to add the pending matcher to a newly created empty group:
5139 if (!CurrentGroup->addMatcher(*Rule))
5140 // If we couldn't add the matcher to an empty group, that group type
5141 // doesn't support that kind of matchers at all, so just skip it:
5142 OptRules.push_back(Rule);
5144 ProcessCurrentGroup();
5146 LLVM_DEBUG(dbgs() << "NumGroups: " << NumGroups << "\n");
5147 assert(CurrentGroup->empty() && "The last group wasn't properly processed");
5152 GlobalISelEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules,
5153 bool Optimize, bool WithCoverage) {
5154 std::vector<Matcher *> InputRules;
5155 for (Matcher &Rule : Rules)
5156 InputRules.push_back(&Rule);
5159 return MatchTable::buildTable(InputRules, WithCoverage);
5161 unsigned CurrentOrdering = 0;
5162 StringMap<unsigned> OpcodeOrder;
5163 for (RuleMatcher &Rule : Rules) {
5164 const StringRef Opcode = Rule.getOpcode();
5165 assert(!Opcode.empty() && "Didn't expect an undefined opcode");
5166 if (OpcodeOrder.count(Opcode) == 0)
5167 OpcodeOrder[Opcode] = CurrentOrdering++;
5170 std::stable_sort(InputRules.begin(), InputRules.end(),
5171 [&OpcodeOrder](const Matcher *A, const Matcher *B) {
5172 auto *L = static_cast<const RuleMatcher *>(A);
5173 auto *R = static_cast<const RuleMatcher *>(B);
5174 return std::make_tuple(OpcodeOrder[L->getOpcode()],
5175 L->getNumOperands()) <
5176 std::make_tuple(OpcodeOrder[R->getOpcode()],
5177 R->getNumOperands());
5180 for (Matcher *Rule : InputRules)
5183 std::vector<std::unique_ptr<Matcher>> MatcherStorage;
5184 std::vector<Matcher *> OptRules =
5185 optimizeRules<GroupMatcher>(InputRules, MatcherStorage);
5187 for (Matcher *Rule : OptRules)
5190 OptRules = optimizeRules<SwitchMatcher>(OptRules, MatcherStorage);
5192 return MatchTable::buildTable(OptRules, WithCoverage);
5195 void GroupMatcher::optimize() {
5196 // Make sure we only sort by a specific predicate within a range of rules that
5197 // all have that predicate checked against a specific value (not a wildcard):
5198 auto F = Matchers.begin();
5200 auto E = Matchers.end();
5203 auto *R = static_cast<RuleMatcher *>(*T);
5204 if (!R->getFirstConditionAsRootType().get().isValid())
5208 std::stable_sort(F, T, [](Matcher *A, Matcher *B) {
5209 auto *L = static_cast<RuleMatcher *>(A);
5210 auto *R = static_cast<RuleMatcher *>(B);
5211 return L->getFirstConditionAsRootType() <
5212 R->getFirstConditionAsRootType();
5217 GlobalISelEmitter::optimizeRules<GroupMatcher>(Matchers, MatcherStorage)
5219 GlobalISelEmitter::optimizeRules<SwitchMatcher>(Matchers, MatcherStorage)
5223 void GlobalISelEmitter::run(raw_ostream &OS) {
5224 if (!UseCoverageFile.empty()) {
5225 RuleCoverage = CodeGenCoverage();
5226 auto RuleCoverageBufOrErr = MemoryBuffer::getFile(UseCoverageFile);
5227 if (!RuleCoverageBufOrErr) {
5228 PrintWarning(SMLoc(), "Missing rule coverage data");
5229 RuleCoverage = None;
5231 if (!RuleCoverage->parse(*RuleCoverageBufOrErr.get(), Target.getName())) {
5232 PrintWarning(SMLoc(), "Ignoring invalid or missing rule coverage data");
5233 RuleCoverage = None;
5238 // Track the run-time opcode values
5239 gatherOpcodeValues();
5240 // Track the run-time LLT ID values
5241 gatherTypeIDValues();
5243 // Track the GINodeEquiv definitions.
5246 emitSourceFileHeader(("Global Instruction Selector for the " +
5247 Target.getName() + " target").str(), OS);
5248 std::vector<RuleMatcher> Rules;
5249 // Look through the SelectionDAG patterns we found, possibly emitting some.
5250 for (const PatternToMatch &Pat : CGP.ptms()) {
5253 auto MatcherOrErr = runOnPattern(Pat);
5255 // The pattern analysis can fail, indicating an unsupported pattern.
5256 // Report that if we've been asked to do so.
5257 if (auto Err = MatcherOrErr.takeError()) {
5258 if (WarnOnSkippedPatterns) {
5259 PrintWarning(Pat.getSrcRecord()->getLoc(),
5260 "Skipped pattern: " + toString(std::move(Err)));
5262 consumeError(std::move(Err));
5264 ++NumPatternImportsSkipped;
5269 if (RuleCoverage->isCovered(MatcherOrErr->getRuleID()))
5270 ++NumPatternsTested;
5272 PrintWarning(Pat.getSrcRecord()->getLoc(),
5273 "Pattern is not covered by a test");
5275 Rules.push_back(std::move(MatcherOrErr.get()));
5278 // Comparison function to order records by name.
5279 auto orderByName = [](const Record *A, const Record *B) {
5280 return A->getName() < B->getName();
5283 std::vector<Record *> ComplexPredicates =
5284 RK.getAllDerivedDefinitions("GIComplexOperandMatcher");
5285 llvm::sort(ComplexPredicates, orderByName);
5287 std::vector<Record *> CustomRendererFns =
5288 RK.getAllDerivedDefinitions("GICustomOperandRenderer");
5289 llvm::sort(CustomRendererFns, orderByName);
5291 unsigned MaxTemporaries = 0;
5292 for (const auto &Rule : Rules)
5293 MaxTemporaries = std::max(MaxTemporaries, Rule.countRendererFns());
5295 OS << "#ifdef GET_GLOBALISEL_PREDICATE_BITSET\n"
5296 << "const unsigned MAX_SUBTARGET_PREDICATES = " << SubtargetFeatures.size()
5298 << "using PredicateBitset = "
5299 "llvm::PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;\n"
5300 << "#endif // ifdef GET_GLOBALISEL_PREDICATE_BITSET\n\n";
5302 OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n"
5303 << " mutable MatcherState State;\n"
5305 "ComplexRendererFns("
5307 << "InstructionSelector::*ComplexMatcherMemFn)(MachineOperand &) const;\n"
5309 << " typedef void(" << Target.getName()
5310 << "InstructionSelector::*CustomRendererFn)(MachineInstrBuilder &, const "
5311 "MachineInstr&, int) "
5313 << " const ISelInfoTy<PredicateBitset, ComplexMatcherMemFn, "
5314 "CustomRendererFn> "
5316 OS << " static " << Target.getName()
5317 << "InstructionSelector::ComplexMatcherMemFn ComplexPredicateFns[];\n"
5318 << " static " << Target.getName()
5319 << "InstructionSelector::CustomRendererFn CustomRenderers[];\n"
5320 << " bool testImmPredicate_I64(unsigned PredicateID, int64_t Imm) const "
5322 << " bool testImmPredicate_APInt(unsigned PredicateID, const APInt &Imm) "
5324 << " bool testImmPredicate_APFloat(unsigned PredicateID, const APFloat "
5325 "&Imm) const override;\n"
5326 << " const int64_t *getMatchTable() const override;\n"
5327 << " bool testMIPredicate_MI(unsigned PredicateID, const MachineInstr &MI) "
5329 << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n";
5331 OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n"
5332 << ", State(" << MaxTemporaries << "),\n"
5333 << "ISelInfo(TypeObjects, NumTypeObjects, FeatureBitsets"
5334 << ", ComplexPredicateFns, CustomRenderers)\n"
5335 << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";
5337 OS << "#ifdef GET_GLOBALISEL_IMPL\n";
5338 SubtargetFeatureInfo::emitSubtargetFeatureBitEnumeration(SubtargetFeatures,
5341 // Separate subtarget features by how often they must be recomputed.
5342 SubtargetFeatureInfoMap ModuleFeatures;
5343 std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
5344 std::inserter(ModuleFeatures, ModuleFeatures.end()),
5345 [](const SubtargetFeatureInfoMap::value_type &X) {
5346 return !X.second.mustRecomputePerFunction();
5348 SubtargetFeatureInfoMap FunctionFeatures;
5349 std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
5350 std::inserter(FunctionFeatures, FunctionFeatures.end()),
5351 [](const SubtargetFeatureInfoMap::value_type &X) {
5352 return X.second.mustRecomputePerFunction();
5355 SubtargetFeatureInfo::emitComputeAvailableFeatures(
5356 Target.getName(), "InstructionSelector", "computeAvailableModuleFeatures",
5357 ModuleFeatures, OS);
5360 OS << "void " << Target.getName() << "InstructionSelector"
5361 "::setupGeneratedPerFunctionState(MachineFunction &MF) {\n"
5362 " AvailableFunctionFeatures = computeAvailableFunctionFeatures("
5363 "(const " << Target.getName() << "Subtarget*)&MF.getSubtarget(), &MF);\n"
5366 if (Target.getName() == "X86" || Target.getName() == "AArch64") {
5367 // TODO: Implement PGSO.
5368 OS << "static bool shouldOptForSize(const MachineFunction *MF) {\n";
5369 OS << " return MF->getFunction().hasOptSize();\n";
5373 SubtargetFeatureInfo::emitComputeAvailableFeatures(
5374 Target.getName(), "InstructionSelector",
5375 "computeAvailableFunctionFeatures", FunctionFeatures, OS,
5376 "const MachineFunction *MF");
5378 // Emit a table containing the LLT objects needed by the matcher and an enum
5379 // for the matcher to reference them with.
5380 std::vector<LLTCodeGen> TypeObjects;
5381 for (const auto &Ty : KnownTypes)
5382 TypeObjects.push_back(Ty);
5383 llvm::sort(TypeObjects);
5384 OS << "// LLT Objects.\n"
5386 for (const auto &TypeObject : TypeObjects) {
5388 TypeObject.emitCxxEnumValue(OS);
5392 OS << "const static size_t NumTypeObjects = " << TypeObjects.size() << ";\n"
5393 << "const static LLT TypeObjects[] = {\n";
5394 for (const auto &TypeObject : TypeObjects) {
5396 TypeObject.emitCxxConstructorCall(OS);
5401 // Emit a table containing the PredicateBitsets objects needed by the matcher
5402 // and an enum for the matcher to reference them with.
5403 std::vector<std::vector<Record *>> FeatureBitsets;
5404 for (auto &Rule : Rules)
5405 FeatureBitsets.push_back(Rule.getRequiredFeatures());
5406 llvm::sort(FeatureBitsets, [&](const std::vector<Record *> &A,
5407 const std::vector<Record *> &B) {
5408 if (A.size() < B.size())
5410 if (A.size() > B.size())
5412 for (auto Pair : zip(A, B)) {
5413 if (std::get<0>(Pair)->getName() < std::get<1>(Pair)->getName())
5415 if (std::get<0>(Pair)->getName() > std::get<1>(Pair)->getName())
5420 FeatureBitsets.erase(
5421 std::unique(FeatureBitsets.begin(), FeatureBitsets.end()),
5422 FeatureBitsets.end());
5423 OS << "// Feature bitsets.\n"
5425 << " GIFBS_Invalid,\n";
5426 for (const auto &FeatureBitset : FeatureBitsets) {
5427 if (FeatureBitset.empty())
5429 OS << " " << getNameForFeatureBitset(FeatureBitset) << ",\n";
5432 << "const static PredicateBitset FeatureBitsets[] {\n"
5433 << " {}, // GIFBS_Invalid\n";
5434 for (const auto &FeatureBitset : FeatureBitsets) {
5435 if (FeatureBitset.empty())
5438 for (const auto &Feature : FeatureBitset) {
5439 const auto &I = SubtargetFeatures.find(Feature);
5440 assert(I != SubtargetFeatures.end() && "Didn't import predicate?");
5441 OS << I->second.getEnumBitName() << ", ";
5447 // Emit complex predicate table and an enum to reference them with.
5448 OS << "// ComplexPattern predicates.\n"
5450 << " GICP_Invalid,\n";
5451 for (const auto &Record : ComplexPredicates)
5452 OS << " GICP_" << Record->getName() << ",\n";
5454 << "// See constructor for table contents\n\n";
5456 emitImmPredicateFns(OS, "I64", "int64_t", [](const Record *R) {
5458 return !R->getValueAsBitOrUnset("IsAPFloat", Unset) &&
5459 !R->getValueAsBit("IsAPInt");
5461 emitImmPredicateFns(OS, "APFloat", "const APFloat &", [](const Record *R) {
5463 return R->getValueAsBitOrUnset("IsAPFloat", Unset);
5465 emitImmPredicateFns(OS, "APInt", "const APInt &", [](const Record *R) {
5466 return R->getValueAsBit("IsAPInt");
5468 emitMIPredicateFns(OS);
5471 OS << Target.getName() << "InstructionSelector::ComplexMatcherMemFn\n"
5472 << Target.getName() << "InstructionSelector::ComplexPredicateFns[] = {\n"
5473 << " nullptr, // GICP_Invalid\n";
5474 for (const auto &Record : ComplexPredicates)
5475 OS << " &" << Target.getName()
5476 << "InstructionSelector::" << Record->getValueAsString("MatcherFn")
5477 << ", // " << Record->getName() << "\n";
5480 OS << "// Custom renderers.\n"
5482 << " GICR_Invalid,\n";
5483 for (const auto &Record : CustomRendererFns)
5484 OS << " GICR_" << Record->getValueAsString("RendererFn") << ", \n";
5487 OS << Target.getName() << "InstructionSelector::CustomRendererFn\n"
5488 << Target.getName() << "InstructionSelector::CustomRenderers[] = {\n"
5489 << " nullptr, // GICR_Invalid\n";
5490 for (const auto &Record : CustomRendererFns)
5491 OS << " &" << Target.getName()
5492 << "InstructionSelector::" << Record->getValueAsString("RendererFn")
5493 << ", // " << Record->getName() << "\n";
5496 llvm::stable_sort(Rules, [&](const RuleMatcher &A, const RuleMatcher &B) {
5497 int ScoreA = RuleMatcherScores[A.getRuleID()];
5498 int ScoreB = RuleMatcherScores[B.getRuleID()];
5499 if (ScoreA > ScoreB)
5501 if (ScoreB > ScoreA)
5503 if (A.isHigherPriorityThan(B)) {
5504 assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
5505 "and less important at "
5512 OS << "bool " << Target.getName()
5513 << "InstructionSelector::selectImpl(MachineInstr &I, CodeGenCoverage "
5514 "&CoverageInfo) const {\n"
5515 << " MachineFunction &MF = *I.getParent()->getParent();\n"
5516 << " MachineRegisterInfo &MRI = MF.getRegInfo();\n"
5517 << " const PredicateBitset AvailableFeatures = getAvailableFeatures();\n"
5518 << " NewMIVector OutMIs;\n"
5519 << " State.MIs.clear();\n"
5520 << " State.MIs.push_back(&I);\n\n"
5521 << " if (executeMatchTable(*this, OutMIs, State, ISelInfo"
5522 << ", getMatchTable(), TII, MRI, TRI, RBI, AvailableFeatures"
5523 << ", CoverageInfo)) {\n"
5524 << " return true;\n"
5526 << " return false;\n"
5529 const MatchTable Table =
5530 buildMatchTable(Rules, OptimizeMatchTable, GenerateCoverage);
5531 OS << "const int64_t *" << Target.getName()
5532 << "InstructionSelector::getMatchTable() const {\n";
5533 Table.emitDeclaration(OS);
5537 OS << "#endif // ifdef GET_GLOBALISEL_IMPL\n";
5539 OS << "#ifdef GET_GLOBALISEL_PREDICATES_DECL\n"
5540 << "PredicateBitset AvailableModuleFeatures;\n"
5541 << "mutable PredicateBitset AvailableFunctionFeatures;\n"
5542 << "PredicateBitset getAvailableFeatures() const {\n"
5543 << " return AvailableModuleFeatures | AvailableFunctionFeatures;\n"
5545 << "PredicateBitset\n"
5546 << "computeAvailableModuleFeatures(const " << Target.getName()
5547 << "Subtarget *Subtarget) const;\n"
5548 << "PredicateBitset\n"
5549 << "computeAvailableFunctionFeatures(const " << Target.getName()
5550 << "Subtarget *Subtarget,\n"
5551 << " const MachineFunction *MF) const;\n"
5552 << "void setupGeneratedPerFunctionState(MachineFunction &MF) override;\n"
5553 << "#endif // ifdef GET_GLOBALISEL_PREDICATES_DECL\n";
5555 OS << "#ifdef GET_GLOBALISEL_PREDICATES_INIT\n"
5556 << "AvailableModuleFeatures(computeAvailableModuleFeatures(&STI)),\n"
5557 << "AvailableFunctionFeatures()\n"
5558 << "#endif // ifdef GET_GLOBALISEL_PREDICATES_INIT\n";
5561 void GlobalISelEmitter::declareSubtargetFeature(Record *Predicate) {
5562 if (SubtargetFeatures.count(Predicate) == 0)
5563 SubtargetFeatures.emplace(
5564 Predicate, SubtargetFeatureInfo(Predicate, SubtargetFeatures.size()));
5567 void RuleMatcher::optimize() {
5568 for (auto &Item : InsnVariableIDs) {
5569 InstructionMatcher &InsnMatcher = *Item.first;
5570 for (auto &OM : InsnMatcher.operands()) {
5571 // Complex Patterns are usually expensive and they relatively rarely fail
5572 // on their own: more often we end up throwing away all the work done by a
5573 // matching part of a complex pattern because some other part of the
5574 // enclosing pattern didn't match. All of this makes it beneficial to
5575 // delay complex patterns until the very end of the rule matching,
5576 // especially for targets having lots of complex patterns.
5577 for (auto &OP : OM->predicates())
5578 if (isa<ComplexPatternOperandMatcher>(OP))
5579 EpilogueMatchers.emplace_back(std::move(OP));
5580 OM->eraseNullPredicates();
5582 InsnMatcher.optimize();
5584 llvm::sort(EpilogueMatchers, [](const std::unique_ptr<PredicateMatcher> &L,
5585 const std::unique_ptr<PredicateMatcher> &R) {
5586 return std::make_tuple(L->getKind(), L->getInsnVarID(), L->getOpIdx()) <
5587 std::make_tuple(R->getKind(), R->getInsnVarID(), R->getOpIdx());
5591 bool RuleMatcher::hasFirstCondition() const {
5592 if (insnmatchers_empty())
5594 InstructionMatcher &Matcher = insnmatchers_front();
5595 if (!Matcher.predicates_empty())
5597 for (auto &OM : Matcher.operands())
5598 for (auto &OP : OM->predicates())
5599 if (!isa<InstructionOperandMatcher>(OP))
5604 const PredicateMatcher &RuleMatcher::getFirstCondition() const {
5605 assert(!insnmatchers_empty() &&
5606 "Trying to get a condition from an empty RuleMatcher");
5608 InstructionMatcher &Matcher = insnmatchers_front();
5609 if (!Matcher.predicates_empty())
5610 return **Matcher.predicates_begin();
5611 // If there is no more predicate on the instruction itself, look at its
5613 for (auto &OM : Matcher.operands())
5614 for (auto &OP : OM->predicates())
5615 if (!isa<InstructionOperandMatcher>(OP))
5618 llvm_unreachable("Trying to get a condition from an InstructionMatcher with "
5622 std::unique_ptr<PredicateMatcher> RuleMatcher::popFirstCondition() {
5623 assert(!insnmatchers_empty() &&
5624 "Trying to pop a condition from an empty RuleMatcher");
5626 InstructionMatcher &Matcher = insnmatchers_front();
5627 if (!Matcher.predicates_empty())
5628 return Matcher.predicates_pop_front();
5629 // If there is no more predicate on the instruction itself, look at its
5631 for (auto &OM : Matcher.operands())
5632 for (auto &OP : OM->predicates())
5633 if (!isa<InstructionOperandMatcher>(OP)) {
5634 std::unique_ptr<PredicateMatcher> Result = std::move(OP);
5635 OM->eraseNullPredicates();
5639 llvm_unreachable("Trying to pop a condition from an InstructionMatcher with "
5643 bool GroupMatcher::candidateConditionMatches(
5644 const PredicateMatcher &Predicate) const {
5647 // Sharing predicates for nested instructions is not supported yet as we
5648 // currently don't hoist the GIM_RecordInsn's properly, therefore we can
5649 // only work on the original root instruction (InsnVarID == 0):
5650 if (Predicate.getInsnVarID() != 0)
5652 // ... otherwise an empty group can handle any predicate with no specific
5657 const Matcher &Representative = **Matchers.begin();
5658 const auto &RepresentativeCondition = Representative.getFirstCondition();
5659 // ... if not empty, the group can only accomodate matchers with the exact
5660 // same first condition:
5661 return Predicate.isIdentical(RepresentativeCondition);
5664 bool GroupMatcher::addMatcher(Matcher &Candidate) {
5665 if (!Candidate.hasFirstCondition())
5668 const PredicateMatcher &Predicate = Candidate.getFirstCondition();
5669 if (!candidateConditionMatches(Predicate))
5672 Matchers.push_back(&Candidate);
5676 void GroupMatcher::finalize() {
5677 assert(Conditions.empty() && "Already finalized?");
5681 Matcher &FirstRule = **Matchers.begin();
5683 // All the checks are expected to succeed during the first iteration:
5684 for (const auto &Rule : Matchers)
5685 if (!Rule->hasFirstCondition())
5687 const auto &FirstCondition = FirstRule.getFirstCondition();
5688 for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
5689 if (!Matchers[I]->getFirstCondition().isIdentical(FirstCondition))
5692 Conditions.push_back(FirstRule.popFirstCondition());
5693 for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
5694 Matchers[I]->popFirstCondition();
5698 void GroupMatcher::emit(MatchTable &Table) {
5699 unsigned LabelID = ~0U;
5700 if (!Conditions.empty()) {
5701 LabelID = Table.allocateLabelID();
5702 Table << MatchTable::Opcode("GIM_Try", +1)
5703 << MatchTable::Comment("On fail goto")
5704 << MatchTable::JumpTarget(LabelID) << MatchTable::LineBreak;
5706 for (auto &Condition : Conditions)
5707 Condition->emitPredicateOpcodes(
5708 Table, *static_cast<RuleMatcher *>(*Matchers.begin()));
5710 for (const auto &M : Matchers)
5714 if (!Conditions.empty())
5715 Table << MatchTable::Opcode("GIM_Reject", -1) << MatchTable::LineBreak
5716 << MatchTable::Label(LabelID);
5719 bool SwitchMatcher::isSupportedPredicateType(const PredicateMatcher &P) {
5720 return isa<InstructionOpcodeMatcher>(P) || isa<LLTOperandMatcher>(P);
5723 bool SwitchMatcher::candidateConditionMatches(
5724 const PredicateMatcher &Predicate) const {
5727 // Sharing predicates for nested instructions is not supported yet as we
5728 // currently don't hoist the GIM_RecordInsn's properly, therefore we can
5729 // only work on the original root instruction (InsnVarID == 0):
5730 if (Predicate.getInsnVarID() != 0)
5732 // ... while an attempt to add even a root matcher to an empty SwitchMatcher
5733 // could fail as not all the types of conditions are supported:
5734 if (!isSupportedPredicateType(Predicate))
5736 // ... or the condition might not have a proper implementation of
5737 // getValue() / isIdenticalDownToValue() yet:
5738 if (!Predicate.hasValue())
5740 // ... otherwise an empty Switch can accomodate the condition with no
5741 // further requirements:
5745 const Matcher &CaseRepresentative = **Matchers.begin();
5746 const auto &RepresentativeCondition = CaseRepresentative.getFirstCondition();
5747 // Switch-cases must share the same kind of condition and path to the value it
5749 if (!Predicate.isIdenticalDownToValue(RepresentativeCondition))
5752 const auto Value = Predicate.getValue();
5753 // ... but be unique with respect to the actual value they check:
5754 return Values.count(Value) == 0;
5757 bool SwitchMatcher::addMatcher(Matcher &Candidate) {
5758 if (!Candidate.hasFirstCondition())
5761 const PredicateMatcher &Predicate = Candidate.getFirstCondition();
5762 if (!candidateConditionMatches(Predicate))
5764 const auto Value = Predicate.getValue();
5765 Values.insert(Value);
5767 Matchers.push_back(&Candidate);
5771 void SwitchMatcher::finalize() {
5772 assert(Condition == nullptr && "Already finalized");
5773 assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");
5777 std::stable_sort(Matchers.begin(), Matchers.end(),
5778 [](const Matcher *L, const Matcher *R) {
5779 return L->getFirstCondition().getValue() <
5780 R->getFirstCondition().getValue();
5782 Condition = Matchers[0]->popFirstCondition();
5783 for (unsigned I = 1, E = Values.size(); I < E; ++I)
5784 Matchers[I]->popFirstCondition();
5787 void SwitchMatcher::emitPredicateSpecificOpcodes(const PredicateMatcher &P,
5788 MatchTable &Table) {
5789 assert(isSupportedPredicateType(P) && "Predicate type is not supported");
5791 if (const auto *Condition = dyn_cast<InstructionOpcodeMatcher>(&P)) {
5792 Table << MatchTable::Opcode("GIM_SwitchOpcode") << MatchTable::Comment("MI")
5793 << MatchTable::IntValue(Condition->getInsnVarID());
5796 if (const auto *Condition = dyn_cast<LLTOperandMatcher>(&P)) {
5797 Table << MatchTable::Opcode("GIM_SwitchType") << MatchTable::Comment("MI")
5798 << MatchTable::IntValue(Condition->getInsnVarID())
5799 << MatchTable::Comment("Op")
5800 << MatchTable::IntValue(Condition->getOpIdx());
5804 llvm_unreachable("emitPredicateSpecificOpcodes is broken: can not handle a "
5805 "predicate type that is claimed to be supported");
5808 void SwitchMatcher::emit(MatchTable &Table) {
5809 assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");
5812 assert(Condition != nullptr &&
5813 "Broken SwitchMatcher, hasn't been finalized?");
5815 std::vector<unsigned> LabelIDs(Values.size());
5816 std::generate(LabelIDs.begin(), LabelIDs.end(),
5817 [&Table]() { return Table.allocateLabelID(); });
5818 const unsigned Default = Table.allocateLabelID();
5820 const int64_t LowerBound = Values.begin()->getRawValue();
5821 const int64_t UpperBound = Values.rbegin()->getRawValue() + 1;
5823 emitPredicateSpecificOpcodes(*Condition, Table);
5825 Table << MatchTable::Comment("[") << MatchTable::IntValue(LowerBound)
5826 << MatchTable::IntValue(UpperBound) << MatchTable::Comment(")")
5827 << MatchTable::Comment("default:") << MatchTable::JumpTarget(Default);
5829 int64_t J = LowerBound;
5830 auto VI = Values.begin();
5831 for (unsigned I = 0, E = Values.size(); I < E; ++I) {
5833 while (J++ < V.getRawValue())
5834 Table << MatchTable::IntValue(0);
5835 V.turnIntoComment();
5836 Table << MatchTable::LineBreak << V << MatchTable::JumpTarget(LabelIDs[I]);
5838 Table << MatchTable::LineBreak;
5840 for (unsigned I = 0, E = Values.size(); I < E; ++I) {
5841 Table << MatchTable::Label(LabelIDs[I]);
5842 Matchers[I]->emit(Table);
5843 Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
5845 Table << MatchTable::Label(Default);
5848 unsigned OperandMatcher::getInsnVarID() const { return Insn.getInsnVarID(); }
5850 } // end anonymous namespace
5852 //===----------------------------------------------------------------------===//
5855 void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS) {
5856 GlobalISelEmitter(RK).run(OS);
5858 } // End llvm namespace