1 //===- GlobalISelEmitter.cpp - Generate an instruction selector -----------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
10 /// This tablegen backend emits code for use by the GlobalISel instruction
11 /// selector. See include/llvm/CodeGen/TargetGlobalISel.td.
13 /// This file analyzes the patterns recognized by the SelectionDAGISel tablegen
14 /// backend, filters out the ones that are unsupported, maps
15 /// SelectionDAG-specific constructs to their GlobalISel counterpart
16 /// (when applicable: MVT to LLT; SDNode to generic Instruction).
18 /// Not all patterns are supported: pass the tablegen invocation
19 /// "-warn-on-skipped-patterns" to emit a warning when a pattern is skipped,
22 /// The generated file defines a single method:
23 /// bool <Target>InstructionSelector::selectImpl(MachineInstr &I) const;
24 /// intended to be used in InstructionSelector::select as the first-step
25 /// selector for the patterns that don't require complex C++.
27 /// FIXME: We'll probably want to eventually define a base
28 /// "TargetGenInstructionSelector" class.
30 //===----------------------------------------------------------------------===//
32 #include "CodeGenDAGPatterns.h"
33 #include "SubtargetFeatureInfo.h"
34 #include "llvm/ADT/Optional.h"
35 #include "llvm/ADT/SmallSet.h"
36 #include "llvm/ADT/Statistic.h"
37 #include "llvm/Support/CodeGenCoverage.h"
38 #include "llvm/Support/CommandLine.h"
39 #include "llvm/Support/Error.h"
40 #include "llvm/Support/LowLevelTypeImpl.h"
41 #include "llvm/Support/MachineValueType.h"
42 #include "llvm/Support/ScopedPrinter.h"
43 #include "llvm/TableGen/Error.h"
44 #include "llvm/TableGen/Record.h"
45 #include "llvm/TableGen/TableGenBackend.h"
50 #define DEBUG_TYPE "gisel-emitter"
52 STATISTIC(NumPatternTotal, "Total number of patterns");
53 STATISTIC(NumPatternImported, "Number of patterns imported from SelectionDAG");
54 STATISTIC(NumPatternImportsSkipped, "Number of SelectionDAG imports skipped");
55 STATISTIC(NumPatternsTested, "Number of patterns executed according to coverage information");
56 STATISTIC(NumPatternEmitted, "Number of patterns emitted");
58 cl::OptionCategory GlobalISelEmitterCat("Options for -gen-global-isel");
60 static cl::opt<bool> WarnOnSkippedPatterns(
61 "warn-on-skipped-patterns",
62 cl::desc("Explain why a pattern was skipped for inclusion "
63 "in the GlobalISel selector"),
64 cl::init(false), cl::cat(GlobalISelEmitterCat));
66 static cl::opt<bool> GenerateCoverage(
67 "instrument-gisel-coverage",
68 cl::desc("Generate coverage instrumentation for GlobalISel"),
69 cl::init(false), cl::cat(GlobalISelEmitterCat));
71 static cl::opt<std::string> UseCoverageFile(
72 "gisel-coverage-file", cl::init(""),
73 cl::desc("Specify file to retrieve coverage information from"),
74 cl::cat(GlobalISelEmitterCat));
76 static cl::opt<bool> OptimizeMatchTable(
77 "optimize-match-table",
78 cl::desc("Generate an optimized version of the match table"),
79 cl::init(true), cl::cat(GlobalISelEmitterCat));
82 //===- Helper functions ---------------------------------------------------===//
84 /// Get the name of the enum value used to number the predicate function.
85 std::string getEnumNameForPredicate(const TreePredicateFn &Predicate) {
86 if (Predicate.hasGISelPredicateCode())
87 return "GIPFP_MI_" + Predicate.getFnName();
88 return "GIPFP_" + Predicate.getImmTypeIdentifier().str() + "_" +
89 Predicate.getFnName();
92 /// Get the opcode used to check this predicate.
93 std::string getMatchOpcodeForPredicate(const TreePredicateFn &Predicate) {
94 return "GIM_Check" + Predicate.getImmTypeIdentifier().str() + "ImmPredicate";
97 /// This class stands in for LLT wherever we want to tablegen-erate an
98 /// equivalent at compiler run-time.
104 LLTCodeGen() = default;
105 LLTCodeGen(const LLT &Ty) : Ty(Ty) {}
107 std::string getCxxEnumValue() const {
109 raw_string_ostream OS(Str);
111 emitCxxEnumValue(OS);
115 void emitCxxEnumValue(raw_ostream &OS) const {
117 OS << "GILLT_s" << Ty.getSizeInBits();
121 OS << "GILLT_v" << Ty.getNumElements() << "s" << Ty.getScalarSizeInBits();
124 if (Ty.isPointer()) {
125 OS << "GILLT_p" << Ty.getAddressSpace();
126 if (Ty.getSizeInBits() > 0)
127 OS << "s" << Ty.getSizeInBits();
130 llvm_unreachable("Unhandled LLT");
133 void emitCxxConstructorCall(raw_ostream &OS) const {
135 OS << "LLT::scalar(" << Ty.getSizeInBits() << ")";
139 OS << "LLT::vector(" << Ty.getNumElements() << ", "
140 << Ty.getScalarSizeInBits() << ")";
143 if (Ty.isPointer() && Ty.getSizeInBits() > 0) {
144 OS << "LLT::pointer(" << Ty.getAddressSpace() << ", "
145 << Ty.getSizeInBits() << ")";
148 llvm_unreachable("Unhandled LLT");
151 const LLT &get() const { return Ty; }
153 /// This ordering is used for std::unique() and llvm::sort(). There's no
154 /// particular logic behind the order but either A < B or B < A must be
156 bool operator<(const LLTCodeGen &Other) const {
157 if (Ty.isValid() != Other.Ty.isValid())
158 return Ty.isValid() < Other.Ty.isValid();
162 if (Ty.isVector() != Other.Ty.isVector())
163 return Ty.isVector() < Other.Ty.isVector();
164 if (Ty.isScalar() != Other.Ty.isScalar())
165 return Ty.isScalar() < Other.Ty.isScalar();
166 if (Ty.isPointer() != Other.Ty.isPointer())
167 return Ty.isPointer() < Other.Ty.isPointer();
169 if (Ty.isPointer() && Ty.getAddressSpace() != Other.Ty.getAddressSpace())
170 return Ty.getAddressSpace() < Other.Ty.getAddressSpace();
172 if (Ty.isVector() && Ty.getNumElements() != Other.Ty.getNumElements())
173 return Ty.getNumElements() < Other.Ty.getNumElements();
175 return Ty.getSizeInBits() < Other.Ty.getSizeInBits();
178 bool operator==(const LLTCodeGen &B) const { return Ty == B.Ty; }
181 // Track all types that are used so we can emit the corresponding enum.
182 std::set<LLTCodeGen> KnownTypes;
184 class InstructionMatcher;
185 /// Convert an MVT to an equivalent LLT if possible, or the invalid LLT() for
186 /// MVTs that don't map cleanly to an LLT (e.g., iPTR, *any, ...).
187 static Optional<LLTCodeGen> MVTToLLT(MVT::SimpleValueType SVT) {
190 if (VT.isVector() && VT.getVectorNumElements() != 1)
192 LLT::vector(VT.getVectorNumElements(), VT.getScalarSizeInBits()));
194 if (VT.isInteger() || VT.isFloatingPoint())
195 return LLTCodeGen(LLT::scalar(VT.getSizeInBits()));
199 static std::string explainPredicates(const TreePatternNode *N) {
200 std::string Explanation = "";
201 StringRef Separator = "";
202 for (const TreePredicateCall &Call : N->getPredicateCalls()) {
203 const TreePredicateFn &P = Call.Fn;
205 (Separator + P.getOrigPatFragRecord()->getRecord()->getName()).str();
208 if (P.isAlwaysTrue())
209 Explanation += " always-true";
210 if (P.isImmediatePattern())
211 Explanation += " immediate";
214 Explanation += " unindexed";
216 if (P.isNonExtLoad())
217 Explanation += " non-extload";
218 if (P.isAnyExtLoad())
219 Explanation += " extload";
220 if (P.isSignExtLoad())
221 Explanation += " sextload";
222 if (P.isZeroExtLoad())
223 Explanation += " zextload";
225 if (P.isNonTruncStore())
226 Explanation += " non-truncstore";
227 if (P.isTruncStore())
228 Explanation += " truncstore";
230 if (Record *VT = P.getMemoryVT())
231 Explanation += (" MemVT=" + VT->getName()).str();
232 if (Record *VT = P.getScalarMemoryVT())
233 Explanation += (" ScalarVT(MemVT)=" + VT->getName()).str();
235 if (ListInit *AddrSpaces = P.getAddressSpaces()) {
236 raw_string_ostream OS(Explanation);
237 OS << " AddressSpaces=[";
239 StringRef AddrSpaceSeparator;
240 for (Init *Val : AddrSpaces->getValues()) {
241 IntInit *IntVal = dyn_cast<IntInit>(Val);
245 OS << AddrSpaceSeparator << IntVal->getValue();
246 AddrSpaceSeparator = ", ";
252 int64_t MinAlign = P.getMinAlignment();
254 Explanation += " MinAlign=" + utostr(MinAlign);
256 if (P.isAtomicOrderingMonotonic())
257 Explanation += " monotonic";
258 if (P.isAtomicOrderingAcquire())
259 Explanation += " acquire";
260 if (P.isAtomicOrderingRelease())
261 Explanation += " release";
262 if (P.isAtomicOrderingAcquireRelease())
263 Explanation += " acq_rel";
264 if (P.isAtomicOrderingSequentiallyConsistent())
265 Explanation += " seq_cst";
266 if (P.isAtomicOrderingAcquireOrStronger())
267 Explanation += " >=acquire";
268 if (P.isAtomicOrderingWeakerThanAcquire())
269 Explanation += " <acquire";
270 if (P.isAtomicOrderingReleaseOrStronger())
271 Explanation += " >=release";
272 if (P.isAtomicOrderingWeakerThanRelease())
273 Explanation += " <release";
278 std::string explainOperator(Record *Operator) {
279 if (Operator->isSubClassOf("SDNode"))
280 return (" (" + Operator->getValueAsString("Opcode") + ")").str();
282 if (Operator->isSubClassOf("Intrinsic"))
283 return (" (Operator is an Intrinsic, " + Operator->getName() + ")").str();
285 if (Operator->isSubClassOf("ComplexPattern"))
286 return (" (Operator is an unmapped ComplexPattern, " + Operator->getName() +
290 if (Operator->isSubClassOf("SDNodeXForm"))
291 return (" (Operator is an unmapped SDNodeXForm, " + Operator->getName() +
295 return (" (Operator " + Operator->getName() + " not understood)").str();
298 /// Helper function to let the emitter report skip reason error messages.
299 static Error failedImport(const Twine &Reason) {
300 return make_error<StringError>(Reason, inconvertibleErrorCode());
303 static Error isTrivialOperatorNode(const TreePatternNode *N) {
304 std::string Explanation = "";
305 std::string Separator = "";
307 bool HasUnsupportedPredicate = false;
308 for (const TreePredicateCall &Call : N->getPredicateCalls()) {
309 const TreePredicateFn &Predicate = Call.Fn;
311 if (Predicate.isAlwaysTrue())
314 if (Predicate.isImmediatePattern())
317 if (Predicate.isNonExtLoad() || Predicate.isAnyExtLoad() ||
318 Predicate.isSignExtLoad() || Predicate.isZeroExtLoad())
321 if (Predicate.isNonTruncStore() || Predicate.isTruncStore())
324 if (Predicate.isLoad() && Predicate.getMemoryVT())
327 if (Predicate.isLoad() || Predicate.isStore()) {
328 if (Predicate.isUnindexed())
332 if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
333 const ListInit *AddrSpaces = Predicate.getAddressSpaces();
334 if (AddrSpaces && !AddrSpaces->empty())
337 if (Predicate.getMinAlignment() > 0)
341 if (Predicate.isAtomic() && Predicate.getMemoryVT())
344 if (Predicate.isAtomic() &&
345 (Predicate.isAtomicOrderingMonotonic() ||
346 Predicate.isAtomicOrderingAcquire() ||
347 Predicate.isAtomicOrderingRelease() ||
348 Predicate.isAtomicOrderingAcquireRelease() ||
349 Predicate.isAtomicOrderingSequentiallyConsistent() ||
350 Predicate.isAtomicOrderingAcquireOrStronger() ||
351 Predicate.isAtomicOrderingWeakerThanAcquire() ||
352 Predicate.isAtomicOrderingReleaseOrStronger() ||
353 Predicate.isAtomicOrderingWeakerThanRelease()))
356 if (Predicate.hasGISelPredicateCode())
359 HasUnsupportedPredicate = true;
360 Explanation = Separator + "Has a predicate (" + explainPredicates(N) + ")";
362 Explanation += (Separator + "first-failing:" +
363 Predicate.getOrigPatFragRecord()->getRecord()->getName())
368 if (!HasUnsupportedPredicate)
369 return Error::success();
371 return failedImport(Explanation);
374 static Record *getInitValueAsRegClass(Init *V) {
375 if (DefInit *VDefInit = dyn_cast<DefInit>(V)) {
376 if (VDefInit->getDef()->isSubClassOf("RegisterOperand"))
377 return VDefInit->getDef()->getValueAsDef("RegClass");
378 if (VDefInit->getDef()->isSubClassOf("RegisterClass"))
379 return VDefInit->getDef();
385 getNameForFeatureBitset(const std::vector<Record *> &FeatureBitset) {
386 std::string Name = "GIFBS";
387 for (const auto &Feature : FeatureBitset)
388 Name += ("_" + Feature->getName()).str();
392 //===- MatchTable Helpers -------------------------------------------------===//
396 /// A record to be stored in a MatchTable.
398 /// This class represents any and all output that may be required to emit the
399 /// MatchTable. Instances are most often configured to represent an opcode or
400 /// value that will be emitted to the table with some formatting but it can also
401 /// represent commas, comments, and other formatting instructions.
402 struct MatchTableRecord {
403 enum RecordFlagsBits {
405 /// Causes EmitStr to be formatted as comment when emitted.
407 /// Causes the record value to be followed by a comma when emitted.
408 MTRF_CommaFollows = 0x2,
409 /// Causes the record value to be followed by a line break when emitted.
410 MTRF_LineBreakFollows = 0x4,
411 /// Indicates that the record defines a label and causes an additional
412 /// comment to be emitted containing the index of the label.
414 /// Causes the record to be emitted as the index of the label specified by
415 /// LabelID along with a comment indicating where that label is.
416 MTRF_JumpTarget = 0x10,
417 /// Causes the formatter to add a level of indentation before emitting the
420 /// Causes the formatter to remove a level of indentation after emitting the
425 /// When MTRF_Label or MTRF_JumpTarget is used, indicates a label id to
426 /// reference or define.
428 /// The string to emit. Depending on the MTRF_* flags it may be a comment, a
429 /// value, a label name.
433 /// The number of MatchTable elements described by this record. Comments are 0
434 /// while values are typically 1. Values >1 may occur when we need to emit
435 /// values that exceed the size of a MatchTable element.
436 unsigned NumElements;
439 /// A bitfield of RecordFlagsBits flags.
442 /// The actual run-time value, if known
445 MatchTableRecord(Optional<unsigned> LabelID_, StringRef EmitStr,
446 unsigned NumElements, unsigned Flags,
447 int64_t RawValue = std::numeric_limits<int64_t>::min())
448 : LabelID(LabelID_.hasValue() ? LabelID_.getValue() : ~0u),
449 EmitStr(EmitStr), NumElements(NumElements), Flags(Flags),
452 assert((!LabelID_.hasValue() || LabelID != ~0u) &&
453 "This value is reserved for non-labels");
455 MatchTableRecord(const MatchTableRecord &Other) = default;
456 MatchTableRecord(MatchTableRecord &&Other) = default;
458 /// Useful if a Match Table Record gets optimized out
459 void turnIntoComment() {
460 Flags |= MTRF_Comment;
461 Flags &= ~MTRF_CommaFollows;
465 /// For Jump Table generation purposes
466 bool operator<(const MatchTableRecord &Other) const {
467 return RawValue < Other.RawValue;
469 int64_t getRawValue() const { return RawValue; }
471 void emit(raw_ostream &OS, bool LineBreakNextAfterThis,
472 const MatchTable &Table) const;
473 unsigned size() const { return NumElements; }
478 /// Holds the contents of a generated MatchTable to enable formatting and the
479 /// necessary index tracking needed to support GIM_Try.
481 /// An unique identifier for the table. The generated table will be named
484 /// The records that make up the table. Also includes comments describing the
485 /// values being emitted and line breaks to format it.
486 std::vector<MatchTableRecord> Contents;
487 /// The currently defined labels.
488 DenseMap<unsigned, unsigned> LabelMap;
489 /// Tracks the sum of MatchTableRecord::NumElements as the table is built.
490 unsigned CurrentSize = 0;
491 /// A unique identifier for a MatchTable label.
492 unsigned CurrentLabelID = 0;
493 /// Determines if the table should be instrumented for rule coverage tracking.
497 static MatchTableRecord LineBreak;
498 static MatchTableRecord Comment(StringRef Comment) {
499 return MatchTableRecord(None, Comment, 0, MatchTableRecord::MTRF_Comment);
501 static MatchTableRecord Opcode(StringRef Opcode, int IndentAdjust = 0) {
502 unsigned ExtraFlags = 0;
503 if (IndentAdjust > 0)
504 ExtraFlags |= MatchTableRecord::MTRF_Indent;
505 if (IndentAdjust < 0)
506 ExtraFlags |= MatchTableRecord::MTRF_Outdent;
508 return MatchTableRecord(None, Opcode, 1,
509 MatchTableRecord::MTRF_CommaFollows | ExtraFlags);
511 static MatchTableRecord NamedValue(StringRef NamedValue) {
512 return MatchTableRecord(None, NamedValue, 1,
513 MatchTableRecord::MTRF_CommaFollows);
515 static MatchTableRecord NamedValue(StringRef NamedValue, int64_t RawValue) {
516 return MatchTableRecord(None, NamedValue, 1,
517 MatchTableRecord::MTRF_CommaFollows, RawValue);
519 static MatchTableRecord NamedValue(StringRef Namespace,
520 StringRef NamedValue) {
521 return MatchTableRecord(None, (Namespace + "::" + NamedValue).str(), 1,
522 MatchTableRecord::MTRF_CommaFollows);
524 static MatchTableRecord NamedValue(StringRef Namespace, StringRef NamedValue,
526 return MatchTableRecord(None, (Namespace + "::" + NamedValue).str(), 1,
527 MatchTableRecord::MTRF_CommaFollows, RawValue);
529 static MatchTableRecord IntValue(int64_t IntValue) {
530 return MatchTableRecord(None, llvm::to_string(IntValue), 1,
531 MatchTableRecord::MTRF_CommaFollows);
533 static MatchTableRecord Label(unsigned LabelID) {
534 return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 0,
535 MatchTableRecord::MTRF_Label |
536 MatchTableRecord::MTRF_Comment |
537 MatchTableRecord::MTRF_LineBreakFollows);
539 static MatchTableRecord JumpTarget(unsigned LabelID) {
540 return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 1,
541 MatchTableRecord::MTRF_JumpTarget |
542 MatchTableRecord::MTRF_Comment |
543 MatchTableRecord::MTRF_CommaFollows);
546 static MatchTable buildTable(ArrayRef<Matcher *> Rules, bool WithCoverage);
548 MatchTable(bool WithCoverage, unsigned ID = 0)
549 : ID(ID), IsWithCoverage(WithCoverage) {}
551 bool isWithCoverage() const { return IsWithCoverage; }
553 void push_back(const MatchTableRecord &Value) {
554 if (Value.Flags & MatchTableRecord::MTRF_Label)
555 defineLabel(Value.LabelID);
556 Contents.push_back(Value);
557 CurrentSize += Value.size();
560 unsigned allocateLabelID() { return CurrentLabelID++; }
562 void defineLabel(unsigned LabelID) {
563 LabelMap.insert(std::make_pair(LabelID, CurrentSize));
566 unsigned getLabelIndex(unsigned LabelID) const {
567 const auto I = LabelMap.find(LabelID);
568 assert(I != LabelMap.end() && "Use of undeclared label");
572 void emitUse(raw_ostream &OS) const { OS << "MatchTable" << ID; }
574 void emitDeclaration(raw_ostream &OS) const {
575 unsigned Indentation = 4;
576 OS << " constexpr static int64_t MatchTable" << ID << "[] = {";
577 LineBreak.emit(OS, true, *this);
578 OS << std::string(Indentation, ' ');
580 for (auto I = Contents.begin(), E = Contents.end(); I != E;
582 bool LineBreakIsNext = false;
583 const auto &NextI = std::next(I);
586 if (NextI->EmitStr == "" &&
587 NextI->Flags == MatchTableRecord::MTRF_LineBreakFollows)
588 LineBreakIsNext = true;
591 if (I->Flags & MatchTableRecord::MTRF_Indent)
594 I->emit(OS, LineBreakIsNext, *this);
595 if (I->Flags & MatchTableRecord::MTRF_LineBreakFollows)
596 OS << std::string(Indentation, ' ');
598 if (I->Flags & MatchTableRecord::MTRF_Outdent)
605 MatchTableRecord MatchTable::LineBreak = {
606 None, "" /* Emit String */, 0 /* Elements */,
607 MatchTableRecord::MTRF_LineBreakFollows};
609 void MatchTableRecord::emit(raw_ostream &OS, bool LineBreakIsNextAfterThis,
610 const MatchTable &Table) const {
611 bool UseLineComment =
612 LineBreakIsNextAfterThis || (Flags & MTRF_LineBreakFollows);
613 if (Flags & (MTRF_JumpTarget | MTRF_CommaFollows))
614 UseLineComment = false;
616 if (Flags & MTRF_Comment)
617 OS << (UseLineComment ? "// " : "/*");
620 if (Flags & MTRF_Label)
621 OS << ": @" << Table.getLabelIndex(LabelID);
623 if ((Flags & MTRF_Comment) && !UseLineComment)
626 if (Flags & MTRF_JumpTarget) {
627 if (Flags & MTRF_Comment)
629 OS << Table.getLabelIndex(LabelID);
632 if (Flags & MTRF_CommaFollows) {
634 if (!LineBreakIsNextAfterThis && !(Flags & MTRF_LineBreakFollows))
638 if (Flags & MTRF_LineBreakFollows)
642 MatchTable &operator<<(MatchTable &Table, const MatchTableRecord &Value) {
643 Table.push_back(Value);
647 //===- Matchers -----------------------------------------------------------===//
649 class OperandMatcher;
651 class PredicateMatcher;
656 virtual ~Matcher() = default;
657 virtual void optimize() {}
658 virtual void emit(MatchTable &Table) = 0;
660 virtual bool hasFirstCondition() const = 0;
661 virtual const PredicateMatcher &getFirstCondition() const = 0;
662 virtual std::unique_ptr<PredicateMatcher> popFirstCondition() = 0;
665 MatchTable MatchTable::buildTable(ArrayRef<Matcher *> Rules,
667 MatchTable Table(WithCoverage);
668 for (Matcher *Rule : Rules)
671 return Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
674 class GroupMatcher final : public Matcher {
675 /// Conditions that form a common prefix of all the matchers contained.
676 SmallVector<std::unique_ptr<PredicateMatcher>, 1> Conditions;
678 /// All the nested matchers, sharing a common prefix.
679 std::vector<Matcher *> Matchers;
681 /// An owning collection for any auxiliary matchers created while optimizing
682 /// nested matchers contained.
683 std::vector<std::unique_ptr<Matcher>> MatcherStorage;
686 /// Add a matcher to the collection of nested matchers if it meets the
687 /// requirements, and return true. If it doesn't, do nothing and return false.
689 /// Expected to preserve its argument, so it could be moved out later on.
690 bool addMatcher(Matcher &Candidate);
692 /// Mark the matcher as fully-built and ensure any invariants expected by both
693 /// optimize() and emit(...) methods. Generally, both sequences of calls
694 /// are expected to lead to a sensible result:
696 /// addMatcher(...)*; finalize(); optimize(); emit(...); and
697 /// addMatcher(...)*; finalize(); emit(...);
701 /// addMatcher(...)*; finalize(); { optimize()*; emit(...); }*
703 /// Multiple calls to optimize() are expected to be handled gracefully, though
704 /// optimize() is not expected to be idempotent. Multiple calls to finalize()
705 /// aren't generally supported. emit(...) is expected to be non-mutating and
706 /// producing the exact same results upon repeated calls.
708 /// addMatcher() calls after the finalize() call are not supported.
710 /// finalize() and optimize() are both allowed to mutate the contained
711 /// matchers, so moving them out after finalize() is not supported.
713 void optimize() override;
714 void emit(MatchTable &Table) override;
716 /// Could be used to move out the matchers added previously, unless finalize()
717 /// has been already called. If any of the matchers are moved out, the group
718 /// becomes safe to destroy, but not safe to re-use for anything else.
719 iterator_range<std::vector<Matcher *>::iterator> matchers() {
720 return make_range(Matchers.begin(), Matchers.end());
722 size_t size() const { return Matchers.size(); }
723 bool empty() const { return Matchers.empty(); }
725 std::unique_ptr<PredicateMatcher> popFirstCondition() override {
726 assert(!Conditions.empty() &&
727 "Trying to pop a condition from a condition-less group");
728 std::unique_ptr<PredicateMatcher> P = std::move(Conditions.front());
729 Conditions.erase(Conditions.begin());
732 const PredicateMatcher &getFirstCondition() const override {
733 assert(!Conditions.empty() &&
734 "Trying to get a condition from a condition-less group");
735 return *Conditions.front();
737 bool hasFirstCondition() const override { return !Conditions.empty(); }
740 /// See if a candidate matcher could be added to this group solely by
741 /// analyzing its first condition.
742 bool candidateConditionMatches(const PredicateMatcher &Predicate) const;
745 class SwitchMatcher : public Matcher {
746 /// All the nested matchers, representing distinct switch-cases. The first
747 /// conditions (as Matcher::getFirstCondition() reports) of all the nested
748 /// matchers must share the same type and path to a value they check, in other
749 /// words, be isIdenticalDownToValue, but have different values they check
751 std::vector<Matcher *> Matchers;
753 /// The representative condition, with a type and a path (InsnVarID and OpIdx
754 /// in most cases) shared by all the matchers contained.
755 std::unique_ptr<PredicateMatcher> Condition = nullptr;
757 /// Temporary set used to check that the case values don't repeat within the
759 std::set<MatchTableRecord> Values;
761 /// An owning collection for any auxiliary matchers created while optimizing
762 /// nested matchers contained.
763 std::vector<std::unique_ptr<Matcher>> MatcherStorage;
766 bool addMatcher(Matcher &Candidate);
769 void emit(MatchTable &Table) override;
771 iterator_range<std::vector<Matcher *>::iterator> matchers() {
772 return make_range(Matchers.begin(), Matchers.end());
774 size_t size() const { return Matchers.size(); }
775 bool empty() const { return Matchers.empty(); }
777 std::unique_ptr<PredicateMatcher> popFirstCondition() override {
778 // SwitchMatcher doesn't have a common first condition for its cases, as all
779 // the cases only share a kind of a value (a type and a path to it) they
780 // match, but deliberately differ in the actual value they match.
781 llvm_unreachable("Trying to pop a condition from a condition-less group");
783 const PredicateMatcher &getFirstCondition() const override {
784 llvm_unreachable("Trying to pop a condition from a condition-less group");
786 bool hasFirstCondition() const override { return false; }
789 /// See if the predicate type has a Switch-implementation for it.
790 static bool isSupportedPredicateType(const PredicateMatcher &Predicate);
792 bool candidateConditionMatches(const PredicateMatcher &Predicate) const;
795 static void emitPredicateSpecificOpcodes(const PredicateMatcher &P,
799 /// Generates code to check that a match rule matches.
800 class RuleMatcher : public Matcher {
802 using ActionList = std::list<std::unique_ptr<MatchAction>>;
803 using action_iterator = ActionList::iterator;
806 /// A list of matchers that all need to succeed for the current rule to match.
807 /// FIXME: This currently supports a single match position but could be
808 /// extended to support multiple positions to support div/rem fusion or
809 /// load-multiple instructions.
810 using MatchersTy = std::vector<std::unique_ptr<InstructionMatcher>> ;
813 /// A list of actions that need to be taken when all predicates in this rule
817 using DefinedInsnVariablesMap = std::map<InstructionMatcher *, unsigned>;
819 /// A map of instruction matchers to the local variables
820 DefinedInsnVariablesMap InsnVariableIDs;
822 using MutatableInsnSet = SmallPtrSet<InstructionMatcher *, 4>;
824 // The set of instruction matchers that have not yet been claimed for mutation
826 MutatableInsnSet MutatableInsns;
828 /// A map of named operands defined by the matchers that may be referenced by
830 StringMap<OperandMatcher *> DefinedOperands;
832 /// A map of anonymous physical register operands defined by the matchers that
833 /// may be referenced by the renderers.
834 DenseMap<Record *, OperandMatcher *> PhysRegOperands;
836 /// ID for the next instruction variable defined with implicitlyDefineInsnVar()
837 unsigned NextInsnVarID;
839 /// ID for the next output instruction allocated with allocateOutputInsnID()
840 unsigned NextOutputInsnID;
842 /// ID for the next temporary register ID allocated with allocateTempRegID()
843 unsigned NextTempRegID;
845 std::vector<Record *> RequiredFeatures;
846 std::vector<std::unique_ptr<PredicateMatcher>> EpilogueMatchers;
848 ArrayRef<SMLoc> SrcLoc;
850 typedef std::tuple<Record *, unsigned, unsigned>
851 DefinedComplexPatternSubOperand;
852 typedef StringMap<DefinedComplexPatternSubOperand>
853 DefinedComplexPatternSubOperandMap;
854 /// A map of Symbolic Names to ComplexPattern sub-operands.
855 DefinedComplexPatternSubOperandMap ComplexSubOperands;
858 static uint64_t NextRuleID;
861 RuleMatcher(ArrayRef<SMLoc> SrcLoc)
862 : Matchers(), Actions(), InsnVariableIDs(), MutatableInsns(),
863 DefinedOperands(), NextInsnVarID(0), NextOutputInsnID(0),
864 NextTempRegID(0), SrcLoc(SrcLoc), ComplexSubOperands(),
865 RuleID(NextRuleID++) {}
866 RuleMatcher(RuleMatcher &&Other) = default;
867 RuleMatcher &operator=(RuleMatcher &&Other) = default;
869 uint64_t getRuleID() const { return RuleID; }
871 InstructionMatcher &addInstructionMatcher(StringRef SymbolicName);
872 void addRequiredFeature(Record *Feature);
873 const std::vector<Record *> &getRequiredFeatures() const;
875 template <class Kind, class... Args> Kind &addAction(Args &&... args);
876 template <class Kind, class... Args>
877 action_iterator insertAction(action_iterator InsertPt, Args &&... args);
879 /// Define an instruction without emitting any code to do so.
880 unsigned implicitlyDefineInsnVar(InstructionMatcher &Matcher);
882 unsigned getInsnVarID(InstructionMatcher &InsnMatcher) const;
883 DefinedInsnVariablesMap::const_iterator defined_insn_vars_begin() const {
884 return InsnVariableIDs.begin();
886 DefinedInsnVariablesMap::const_iterator defined_insn_vars_end() const {
887 return InsnVariableIDs.end();
889 iterator_range<typename DefinedInsnVariablesMap::const_iterator>
890 defined_insn_vars() const {
891 return make_range(defined_insn_vars_begin(), defined_insn_vars_end());
894 MutatableInsnSet::const_iterator mutatable_insns_begin() const {
895 return MutatableInsns.begin();
897 MutatableInsnSet::const_iterator mutatable_insns_end() const {
898 return MutatableInsns.end();
900 iterator_range<typename MutatableInsnSet::const_iterator>
901 mutatable_insns() const {
902 return make_range(mutatable_insns_begin(), mutatable_insns_end());
904 void reserveInsnMatcherForMutation(InstructionMatcher *InsnMatcher) {
905 bool R = MutatableInsns.erase(InsnMatcher);
906 assert(R && "Reserving a mutatable insn that isn't available");
910 action_iterator actions_begin() { return Actions.begin(); }
911 action_iterator actions_end() { return Actions.end(); }
912 iterator_range<action_iterator> actions() {
913 return make_range(actions_begin(), actions_end());
916 void defineOperand(StringRef SymbolicName, OperandMatcher &OM);
918 void definePhysRegOperand(Record *Reg, OperandMatcher &OM);
920 Error defineComplexSubOperand(StringRef SymbolicName, Record *ComplexPattern,
921 unsigned RendererID, unsigned SubOperandID) {
922 if (ComplexSubOperands.count(SymbolicName))
924 "Complex suboperand referenced more than once (Operand: " +
927 ComplexSubOperands[SymbolicName] =
928 std::make_tuple(ComplexPattern, RendererID, SubOperandID);
930 return Error::success();
933 Optional<DefinedComplexPatternSubOperand>
934 getComplexSubOperand(StringRef SymbolicName) const {
935 const auto &I = ComplexSubOperands.find(SymbolicName);
936 if (I == ComplexSubOperands.end())
941 InstructionMatcher &getInstructionMatcher(StringRef SymbolicName) const;
942 const OperandMatcher &getOperandMatcher(StringRef Name) const;
943 const OperandMatcher &getPhysRegOperandMatcher(Record *) const;
945 void optimize() override;
946 void emit(MatchTable &Table) override;
948 /// Compare the priority of this object and B.
950 /// Returns true if this object is more important than B.
951 bool isHigherPriorityThan(const RuleMatcher &B) const;
953 /// Report the maximum number of temporary operands needed by the rule
955 unsigned countRendererFns() const;
957 std::unique_ptr<PredicateMatcher> popFirstCondition() override;
958 const PredicateMatcher &getFirstCondition() const override;
959 LLTCodeGen getFirstConditionAsRootType();
960 bool hasFirstCondition() const override;
961 unsigned getNumOperands() const;
962 StringRef getOpcode() const;
964 // FIXME: Remove this as soon as possible
965 InstructionMatcher &insnmatchers_front() const { return *Matchers.front(); }
967 unsigned allocateOutputInsnID() { return NextOutputInsnID++; }
968 unsigned allocateTempRegID() { return NextTempRegID++; }
970 iterator_range<MatchersTy::iterator> insnmatchers() {
971 return make_range(Matchers.begin(), Matchers.end());
973 bool insnmatchers_empty() const { return Matchers.empty(); }
974 void insnmatchers_pop_front() { Matchers.erase(Matchers.begin()); }
977 uint64_t RuleMatcher::NextRuleID = 0;
979 using action_iterator = RuleMatcher::action_iterator;
981 template <class PredicateTy> class PredicateListMatcher {
983 /// Template instantiations should specialize this to return a string to use
984 /// for the comment emitted when there are no predicates.
985 std::string getNoPredicateComment() const;
988 using PredicatesTy = std::deque<std::unique_ptr<PredicateTy>>;
989 PredicatesTy Predicates;
991 /// Track if the list of predicates was manipulated by one of the optimization
993 bool Optimized = false;
996 /// Construct a new predicate and add it to the matcher.
997 template <class Kind, class... Args>
998 Optional<Kind *> addPredicate(Args &&... args);
1000 typename PredicatesTy::iterator predicates_begin() {
1001 return Predicates.begin();
1003 typename PredicatesTy::iterator predicates_end() {
1004 return Predicates.end();
1006 iterator_range<typename PredicatesTy::iterator> predicates() {
1007 return make_range(predicates_begin(), predicates_end());
1009 typename PredicatesTy::size_type predicates_size() const {
1010 return Predicates.size();
1012 bool predicates_empty() const { return Predicates.empty(); }
1014 std::unique_ptr<PredicateTy> predicates_pop_front() {
1015 std::unique_ptr<PredicateTy> Front = std::move(Predicates.front());
1016 Predicates.pop_front();
1021 void prependPredicate(std::unique_ptr<PredicateTy> &&Predicate) {
1022 Predicates.push_front(std::move(Predicate));
1025 void eraseNullPredicates() {
1027 std::stable_partition(Predicates.begin(), Predicates.end(),
1028 std::logical_not<std::unique_ptr<PredicateTy>>());
1029 if (NewEnd != Predicates.begin()) {
1030 Predicates.erase(Predicates.begin(), NewEnd);
1035 /// Emit MatchTable opcodes that tests whether all the predicates are met.
1036 template <class... Args>
1037 void emitPredicateListOpcodes(MatchTable &Table, Args &&... args) {
1038 if (Predicates.empty() && !Optimized) {
1039 Table << MatchTable::Comment(getNoPredicateComment())
1040 << MatchTable::LineBreak;
1044 for (const auto &Predicate : predicates())
1045 Predicate->emitPredicateOpcodes(Table, std::forward<Args>(args)...);
1049 class PredicateMatcher {
1051 /// This enum is used for RTTI and also defines the priority that is given to
1052 /// the predicate when generating the matcher code. Kinds with higher priority
1053 /// must be tested first.
1055 /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter
1056 /// but OPM_Int must have priority over OPM_RegBank since constant integers
1057 /// are represented by a virtual register defined by a G_CONSTANT instruction.
1059 /// Note: The relative priority between IPM_ and OPM_ does not matter, they
1060 /// are currently not compared between each other.
1061 enum PredicateKind {
1066 IPM_AtomicOrderingMMO,
1068 IPM_MemoryVsLLTSize,
1069 IPM_MemoryAddressSpace,
1070 IPM_MemoryAlignment,
1071 IPM_GenericPredicate,
1091 PredicateMatcher(PredicateKind Kind, unsigned InsnVarID, unsigned OpIdx = ~0)
1092 : Kind(Kind), InsnVarID(InsnVarID), OpIdx(OpIdx) {}
1094 unsigned getInsnVarID() const { return InsnVarID; }
1095 unsigned getOpIdx() const { return OpIdx; }
1097 virtual ~PredicateMatcher() = default;
1098 /// Emit MatchTable opcodes that check the predicate for the given operand.
1099 virtual void emitPredicateOpcodes(MatchTable &Table,
1100 RuleMatcher &Rule) const = 0;
1102 PredicateKind getKind() const { return Kind; }
1104 virtual bool isIdentical(const PredicateMatcher &B) const {
1105 return B.getKind() == getKind() && InsnVarID == B.InsnVarID &&
1109 virtual bool isIdenticalDownToValue(const PredicateMatcher &B) const {
1110 return hasValue() && PredicateMatcher::isIdentical(B);
1113 virtual MatchTableRecord getValue() const {
1114 assert(hasValue() && "Can not get a value of a value-less predicate!");
1115 llvm_unreachable("Not implemented yet");
1117 virtual bool hasValue() const { return false; }
1119 /// Report the maximum number of temporary operands needed by the predicate
1121 virtual unsigned countRendererFns() const { return 0; }
1124 /// Generates code to check a predicate of an operand.
1126 /// Typical predicates include:
1127 /// * Operand is a particular register.
1128 /// * Operand is assigned a particular register bank.
1129 /// * Operand is an MBB.
1130 class OperandPredicateMatcher : public PredicateMatcher {
1132 OperandPredicateMatcher(PredicateKind Kind, unsigned InsnVarID,
1134 : PredicateMatcher(Kind, InsnVarID, OpIdx) {}
1135 virtual ~OperandPredicateMatcher() {}
1137 /// Compare the priority of this object and B.
1139 /// Returns true if this object is more important than B.
1140 virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const;
1145 PredicateListMatcher<OperandPredicateMatcher>::getNoPredicateComment() const {
1146 return "No operand predicates";
1149 /// Generates code to check that a register operand is defined by the same exact
1151 class SameOperandMatcher : public OperandPredicateMatcher {
1152 std::string MatchingName;
1155 SameOperandMatcher(unsigned InsnVarID, unsigned OpIdx, StringRef MatchingName)
1156 : OperandPredicateMatcher(OPM_SameOperand, InsnVarID, OpIdx),
1157 MatchingName(MatchingName) {}
1159 static bool classof(const PredicateMatcher *P) {
1160 return P->getKind() == OPM_SameOperand;
1163 void emitPredicateOpcodes(MatchTable &Table,
1164 RuleMatcher &Rule) const override;
1166 bool isIdentical(const PredicateMatcher &B) const override {
1167 return OperandPredicateMatcher::isIdentical(B) &&
1168 MatchingName == cast<SameOperandMatcher>(&B)->MatchingName;
1172 /// Generates code to check that an operand is a particular LLT.
1173 class LLTOperandMatcher : public OperandPredicateMatcher {
1178 static std::map<LLTCodeGen, unsigned> TypeIDValues;
1180 static void initTypeIDValuesMap() {
1181 TypeIDValues.clear();
1184 for (const LLTCodeGen &LLTy : KnownTypes)
1185 TypeIDValues[LLTy] = ID++;
1188 LLTOperandMatcher(unsigned InsnVarID, unsigned OpIdx, const LLTCodeGen &Ty)
1189 : OperandPredicateMatcher(OPM_LLT, InsnVarID, OpIdx), Ty(Ty) {
1190 KnownTypes.insert(Ty);
1193 static bool classof(const PredicateMatcher *P) {
1194 return P->getKind() == OPM_LLT;
1196 bool isIdentical(const PredicateMatcher &B) const override {
1197 return OperandPredicateMatcher::isIdentical(B) &&
1198 Ty == cast<LLTOperandMatcher>(&B)->Ty;
1200 MatchTableRecord getValue() const override {
1201 const auto VI = TypeIDValues.find(Ty);
1202 if (VI == TypeIDValues.end())
1203 return MatchTable::NamedValue(getTy().getCxxEnumValue());
1204 return MatchTable::NamedValue(getTy().getCxxEnumValue(), VI->second);
1206 bool hasValue() const override {
1207 if (TypeIDValues.size() != KnownTypes.size())
1208 initTypeIDValuesMap();
1209 return TypeIDValues.count(Ty);
1212 LLTCodeGen getTy() const { return Ty; }
1214 void emitPredicateOpcodes(MatchTable &Table,
1215 RuleMatcher &Rule) const override {
1216 Table << MatchTable::Opcode("GIM_CheckType") << MatchTable::Comment("MI")
1217 << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
1218 << MatchTable::IntValue(OpIdx) << MatchTable::Comment("Type")
1219 << getValue() << MatchTable::LineBreak;
1223 std::map<LLTCodeGen, unsigned> LLTOperandMatcher::TypeIDValues;
1225 /// Generates code to check that an operand is a pointer to any address space.
1227 /// In SelectionDAG, the types did not describe pointers or address spaces. As a
1228 /// result, iN is used to describe a pointer of N bits to any address space and
1229 /// PatFrag predicates are typically used to constrain the address space. There's
1230 /// no reliable means to derive the missing type information from the pattern so
1231 /// imported rules must test the components of a pointer separately.
1233 /// If SizeInBits is zero, then the pointer size will be obtained from the
1235 class PointerToAnyOperandMatcher : public OperandPredicateMatcher {
1237 unsigned SizeInBits;
1240 PointerToAnyOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1241 unsigned SizeInBits)
1242 : OperandPredicateMatcher(OPM_PointerToAny, InsnVarID, OpIdx),
1243 SizeInBits(SizeInBits) {}
1245 static bool classof(const OperandPredicateMatcher *P) {
1246 return P->getKind() == OPM_PointerToAny;
1249 void emitPredicateOpcodes(MatchTable &Table,
1250 RuleMatcher &Rule) const override {
1251 Table << MatchTable::Opcode("GIM_CheckPointerToAny")
1252 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1253 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1254 << MatchTable::Comment("SizeInBits")
1255 << MatchTable::IntValue(SizeInBits) << MatchTable::LineBreak;
1259 /// Generates code to check that an operand is a particular target constant.
1260 class ComplexPatternOperandMatcher : public OperandPredicateMatcher {
1262 const OperandMatcher &Operand;
1263 const Record &TheDef;
1265 unsigned getAllocatedTemporariesBaseID() const;
1268 bool isIdentical(const PredicateMatcher &B) const override { return false; }
1270 ComplexPatternOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1271 const OperandMatcher &Operand,
1272 const Record &TheDef)
1273 : OperandPredicateMatcher(OPM_ComplexPattern, InsnVarID, OpIdx),
1274 Operand(Operand), TheDef(TheDef) {}
1276 static bool classof(const PredicateMatcher *P) {
1277 return P->getKind() == OPM_ComplexPattern;
1280 void emitPredicateOpcodes(MatchTable &Table,
1281 RuleMatcher &Rule) const override {
1282 unsigned ID = getAllocatedTemporariesBaseID();
1283 Table << MatchTable::Opcode("GIM_CheckComplexPattern")
1284 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1285 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1286 << MatchTable::Comment("Renderer") << MatchTable::IntValue(ID)
1287 << MatchTable::NamedValue(("GICP_" + TheDef.getName()).str())
1288 << MatchTable::LineBreak;
1291 unsigned countRendererFns() const override {
1296 /// Generates code to check that an operand is in a particular register bank.
1297 class RegisterBankOperandMatcher : public OperandPredicateMatcher {
1299 const CodeGenRegisterClass &RC;
1302 RegisterBankOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1303 const CodeGenRegisterClass &RC)
1304 : OperandPredicateMatcher(OPM_RegBank, InsnVarID, OpIdx), RC(RC) {}
1306 bool isIdentical(const PredicateMatcher &B) const override {
1307 return OperandPredicateMatcher::isIdentical(B) &&
1308 RC.getDef() == cast<RegisterBankOperandMatcher>(&B)->RC.getDef();
1311 static bool classof(const PredicateMatcher *P) {
1312 return P->getKind() == OPM_RegBank;
1315 void emitPredicateOpcodes(MatchTable &Table,
1316 RuleMatcher &Rule) const override {
1317 Table << MatchTable::Opcode("GIM_CheckRegBankForClass")
1318 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1319 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1320 << MatchTable::Comment("RC")
1321 << MatchTable::NamedValue(RC.getQualifiedName() + "RegClassID")
1322 << MatchTable::LineBreak;
1326 /// Generates code to check that an operand is a basic block.
1327 class MBBOperandMatcher : public OperandPredicateMatcher {
1329 MBBOperandMatcher(unsigned InsnVarID, unsigned OpIdx)
1330 : OperandPredicateMatcher(OPM_MBB, InsnVarID, OpIdx) {}
1332 static bool classof(const PredicateMatcher *P) {
1333 return P->getKind() == OPM_MBB;
1336 void emitPredicateOpcodes(MatchTable &Table,
1337 RuleMatcher &Rule) const override {
1338 Table << MatchTable::Opcode("GIM_CheckIsMBB") << MatchTable::Comment("MI")
1339 << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
1340 << MatchTable::IntValue(OpIdx) << MatchTable::LineBreak;
1344 class ImmOperandMatcher : public OperandPredicateMatcher {
1346 ImmOperandMatcher(unsigned InsnVarID, unsigned OpIdx)
1347 : OperandPredicateMatcher(IPM_Imm, InsnVarID, OpIdx) {}
1349 static bool classof(const PredicateMatcher *P) {
1350 return P->getKind() == IPM_Imm;
1353 void emitPredicateOpcodes(MatchTable &Table,
1354 RuleMatcher &Rule) const override {
1355 Table << MatchTable::Opcode("GIM_CheckIsImm") << MatchTable::Comment("MI")
1356 << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
1357 << MatchTable::IntValue(OpIdx) << MatchTable::LineBreak;
1361 /// Generates code to check that an operand is a G_CONSTANT with a particular
1363 class ConstantIntOperandMatcher : public OperandPredicateMatcher {
1368 ConstantIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value)
1369 : OperandPredicateMatcher(OPM_Int, InsnVarID, OpIdx), Value(Value) {}
1371 bool isIdentical(const PredicateMatcher &B) const override {
1372 return OperandPredicateMatcher::isIdentical(B) &&
1373 Value == cast<ConstantIntOperandMatcher>(&B)->Value;
1376 static bool classof(const PredicateMatcher *P) {
1377 return P->getKind() == OPM_Int;
1380 void emitPredicateOpcodes(MatchTable &Table,
1381 RuleMatcher &Rule) const override {
1382 Table << MatchTable::Opcode("GIM_CheckConstantInt")
1383 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1384 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1385 << MatchTable::IntValue(Value) << MatchTable::LineBreak;
1389 /// Generates code to check that an operand is a raw int (where MO.isImm() or
1390 /// MO.isCImm() is true).
1391 class LiteralIntOperandMatcher : public OperandPredicateMatcher {
1396 LiteralIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value)
1397 : OperandPredicateMatcher(OPM_LiteralInt, InsnVarID, OpIdx),
1400 bool isIdentical(const PredicateMatcher &B) const override {
1401 return OperandPredicateMatcher::isIdentical(B) &&
1402 Value == cast<LiteralIntOperandMatcher>(&B)->Value;
1405 static bool classof(const PredicateMatcher *P) {
1406 return P->getKind() == OPM_LiteralInt;
1409 void emitPredicateOpcodes(MatchTable &Table,
1410 RuleMatcher &Rule) const override {
1411 Table << MatchTable::Opcode("GIM_CheckLiteralInt")
1412 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1413 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1414 << MatchTable::IntValue(Value) << MatchTable::LineBreak;
1418 /// Generates code to check that an operand is an CmpInst predicate
1419 class CmpPredicateOperandMatcher : public OperandPredicateMatcher {
1421 std::string PredName;
1424 CmpPredicateOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1426 : OperandPredicateMatcher(OPM_CmpPredicate, InsnVarID, OpIdx), PredName(P) {}
1428 bool isIdentical(const PredicateMatcher &B) const override {
1429 return OperandPredicateMatcher::isIdentical(B) &&
1430 PredName == cast<CmpPredicateOperandMatcher>(&B)->PredName;
1433 static bool classof(const PredicateMatcher *P) {
1434 return P->getKind() == OPM_CmpPredicate;
1437 void emitPredicateOpcodes(MatchTable &Table,
1438 RuleMatcher &Rule) const override {
1439 Table << MatchTable::Opcode("GIM_CheckCmpPredicate")
1440 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1441 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1442 << MatchTable::Comment("Predicate")
1443 << MatchTable::NamedValue("CmpInst", PredName)
1444 << MatchTable::LineBreak;
1448 /// Generates code to check that an operand is an intrinsic ID.
1449 class IntrinsicIDOperandMatcher : public OperandPredicateMatcher {
1451 const CodeGenIntrinsic *II;
1454 IntrinsicIDOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1455 const CodeGenIntrinsic *II)
1456 : OperandPredicateMatcher(OPM_IntrinsicID, InsnVarID, OpIdx), II(II) {}
1458 bool isIdentical(const PredicateMatcher &B) const override {
1459 return OperandPredicateMatcher::isIdentical(B) &&
1460 II == cast<IntrinsicIDOperandMatcher>(&B)->II;
1463 static bool classof(const PredicateMatcher *P) {
1464 return P->getKind() == OPM_IntrinsicID;
1467 void emitPredicateOpcodes(MatchTable &Table,
1468 RuleMatcher &Rule) const override {
1469 Table << MatchTable::Opcode("GIM_CheckIntrinsicID")
1470 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1471 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1472 << MatchTable::NamedValue("Intrinsic::" + II->EnumName)
1473 << MatchTable::LineBreak;
1477 /// Generates code to check that a set of predicates match for a particular
1479 class OperandMatcher : public PredicateListMatcher<OperandPredicateMatcher> {
1481 InstructionMatcher &Insn;
1483 std::string SymbolicName;
1485 /// The index of the first temporary variable allocated to this operand. The
1486 /// number of allocated temporaries can be found with
1487 /// countRendererFns().
1488 unsigned AllocatedTemporariesBaseID;
1491 OperandMatcher(InstructionMatcher &Insn, unsigned OpIdx,
1492 const std::string &SymbolicName,
1493 unsigned AllocatedTemporariesBaseID)
1494 : Insn(Insn), OpIdx(OpIdx), SymbolicName(SymbolicName),
1495 AllocatedTemporariesBaseID(AllocatedTemporariesBaseID) {}
1497 bool hasSymbolicName() const { return !SymbolicName.empty(); }
1498 const StringRef getSymbolicName() const { return SymbolicName; }
1499 void setSymbolicName(StringRef Name) {
1500 assert(SymbolicName.empty() && "Operand already has a symbolic name");
1501 SymbolicName = Name;
1504 /// Construct a new operand predicate and add it to the matcher.
1505 template <class Kind, class... Args>
1506 Optional<Kind *> addPredicate(Args &&... args) {
1507 if (isSameAsAnotherOperand())
1509 Predicates.emplace_back(std::make_unique<Kind>(
1510 getInsnVarID(), getOpIdx(), std::forward<Args>(args)...));
1511 return static_cast<Kind *>(Predicates.back().get());
1514 unsigned getOpIdx() const { return OpIdx; }
1515 unsigned getInsnVarID() const;
1517 std::string getOperandExpr(unsigned InsnVarID) const {
1518 return "State.MIs[" + llvm::to_string(InsnVarID) + "]->getOperand(" +
1519 llvm::to_string(OpIdx) + ")";
1522 InstructionMatcher &getInstructionMatcher() const { return Insn; }
1524 Error addTypeCheckPredicate(const TypeSetByHwMode &VTy,
1525 bool OperandIsAPointer);
1527 /// Emit MatchTable opcodes that test whether the instruction named in
1528 /// InsnVarID matches all the predicates and all the operands.
1529 void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) {
1531 std::string Comment;
1532 raw_string_ostream CommentOS(Comment);
1533 CommentOS << "MIs[" << getInsnVarID() << "] ";
1534 if (SymbolicName.empty())
1535 CommentOS << "Operand " << OpIdx;
1537 CommentOS << SymbolicName;
1538 Table << MatchTable::Comment(CommentOS.str()) << MatchTable::LineBreak;
1541 emitPredicateListOpcodes(Table, Rule);
1544 /// Compare the priority of this object and B.
1546 /// Returns true if this object is more important than B.
1547 bool isHigherPriorityThan(OperandMatcher &B) {
1548 // Operand matchers involving more predicates have higher priority.
1549 if (predicates_size() > B.predicates_size())
1551 if (predicates_size() < B.predicates_size())
1554 // This assumes that predicates are added in a consistent order.
1555 for (auto &&Predicate : zip(predicates(), B.predicates())) {
1556 if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate)))
1558 if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate)))
1565 /// Report the maximum number of temporary operands needed by the operand
1567 unsigned countRendererFns() {
1568 return std::accumulate(
1569 predicates().begin(), predicates().end(), 0,
1571 const std::unique_ptr<OperandPredicateMatcher> &Predicate) {
1572 return A + Predicate->countRendererFns();
1576 unsigned getAllocatedTemporariesBaseID() const {
1577 return AllocatedTemporariesBaseID;
1580 bool isSameAsAnotherOperand() {
1581 for (const auto &Predicate : predicates())
1582 if (isa<SameOperandMatcher>(Predicate))
1588 Error OperandMatcher::addTypeCheckPredicate(const TypeSetByHwMode &VTy,
1589 bool OperandIsAPointer) {
1590 if (!VTy.isMachineValueType())
1591 return failedImport("unsupported typeset");
1593 if (VTy.getMachineValueType() == MVT::iPTR && OperandIsAPointer) {
1594 addPredicate<PointerToAnyOperandMatcher>(0);
1595 return Error::success();
1598 auto OpTyOrNone = MVTToLLT(VTy.getMachineValueType().SimpleTy);
1600 return failedImport("unsupported type");
1602 if (OperandIsAPointer)
1603 addPredicate<PointerToAnyOperandMatcher>(OpTyOrNone->get().getSizeInBits());
1604 else if (VTy.isPointer())
1605 addPredicate<LLTOperandMatcher>(LLT::pointer(VTy.getPtrAddrSpace(),
1606 OpTyOrNone->get().getSizeInBits()));
1608 addPredicate<LLTOperandMatcher>(*OpTyOrNone);
1609 return Error::success();
1612 unsigned ComplexPatternOperandMatcher::getAllocatedTemporariesBaseID() const {
1613 return Operand.getAllocatedTemporariesBaseID();
1616 /// Generates code to check a predicate on an instruction.
1618 /// Typical predicates include:
1619 /// * The opcode of the instruction is a particular value.
1620 /// * The nsw/nuw flag is/isn't set.
1621 class InstructionPredicateMatcher : public PredicateMatcher {
1623 InstructionPredicateMatcher(PredicateKind Kind, unsigned InsnVarID)
1624 : PredicateMatcher(Kind, InsnVarID) {}
1625 virtual ~InstructionPredicateMatcher() {}
1627 /// Compare the priority of this object and B.
1629 /// Returns true if this object is more important than B.
1631 isHigherPriorityThan(const InstructionPredicateMatcher &B) const {
1632 return Kind < B.Kind;
1638 PredicateListMatcher<PredicateMatcher>::getNoPredicateComment() const {
1639 return "No instruction predicates";
1642 /// Generates code to check the opcode of an instruction.
1643 class InstructionOpcodeMatcher : public InstructionPredicateMatcher {
1645 const CodeGenInstruction *I;
1647 static DenseMap<const CodeGenInstruction *, unsigned> OpcodeValues;
1650 static void initOpcodeValuesMap(const CodeGenTarget &Target) {
1651 OpcodeValues.clear();
1653 unsigned OpcodeValue = 0;
1654 for (const CodeGenInstruction *I : Target.getInstructionsByEnumValue())
1655 OpcodeValues[I] = OpcodeValue++;
1658 InstructionOpcodeMatcher(unsigned InsnVarID, const CodeGenInstruction *I)
1659 : InstructionPredicateMatcher(IPM_Opcode, InsnVarID), I(I) {}
1661 static bool classof(const PredicateMatcher *P) {
1662 return P->getKind() == IPM_Opcode;
1665 bool isIdentical(const PredicateMatcher &B) const override {
1666 return InstructionPredicateMatcher::isIdentical(B) &&
1667 I == cast<InstructionOpcodeMatcher>(&B)->I;
1669 MatchTableRecord getValue() const override {
1670 const auto VI = OpcodeValues.find(I);
1671 if (VI != OpcodeValues.end())
1672 return MatchTable::NamedValue(I->Namespace, I->TheDef->getName(),
1674 return MatchTable::NamedValue(I->Namespace, I->TheDef->getName());
1676 bool hasValue() const override { return OpcodeValues.count(I); }
1678 void emitPredicateOpcodes(MatchTable &Table,
1679 RuleMatcher &Rule) const override {
1680 Table << MatchTable::Opcode("GIM_CheckOpcode") << MatchTable::Comment("MI")
1681 << MatchTable::IntValue(InsnVarID) << getValue()
1682 << MatchTable::LineBreak;
1685 /// Compare the priority of this object and B.
1687 /// Returns true if this object is more important than B.
1689 isHigherPriorityThan(const InstructionPredicateMatcher &B) const override {
1690 if (InstructionPredicateMatcher::isHigherPriorityThan(B))
1692 if (B.InstructionPredicateMatcher::isHigherPriorityThan(*this))
1695 // Prioritize opcodes for cosmetic reasons in the generated source. Although
1696 // this is cosmetic at the moment, we may want to drive a similar ordering
1697 // using instruction frequency information to improve compile time.
1698 if (const InstructionOpcodeMatcher *BO =
1699 dyn_cast<InstructionOpcodeMatcher>(&B))
1700 return I->TheDef->getName() < BO->I->TheDef->getName();
1705 bool isConstantInstruction() const {
1706 return I->TheDef->getName() == "G_CONSTANT";
1709 StringRef getOpcode() const { return I->TheDef->getName(); }
1710 bool isVariadicNumOperands() const { return I->Operands.isVariadic; }
1712 StringRef getOperandType(unsigned OpIdx) const {
1713 return I->Operands[OpIdx].OperandType;
1717 DenseMap<const CodeGenInstruction *, unsigned>
1718 InstructionOpcodeMatcher::OpcodeValues;
1720 class InstructionNumOperandsMatcher final : public InstructionPredicateMatcher {
1721 unsigned NumOperands = 0;
1724 InstructionNumOperandsMatcher(unsigned InsnVarID, unsigned NumOperands)
1725 : InstructionPredicateMatcher(IPM_NumOperands, InsnVarID),
1726 NumOperands(NumOperands) {}
1728 static bool classof(const PredicateMatcher *P) {
1729 return P->getKind() == IPM_NumOperands;
1732 bool isIdentical(const PredicateMatcher &B) const override {
1733 return InstructionPredicateMatcher::isIdentical(B) &&
1734 NumOperands == cast<InstructionNumOperandsMatcher>(&B)->NumOperands;
1737 void emitPredicateOpcodes(MatchTable &Table,
1738 RuleMatcher &Rule) const override {
1739 Table << MatchTable::Opcode("GIM_CheckNumOperands")
1740 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1741 << MatchTable::Comment("Expected")
1742 << MatchTable::IntValue(NumOperands) << MatchTable::LineBreak;
1746 /// Generates code to check that this instruction is a constant whose value
1747 /// meets an immediate predicate.
1749 /// Immediates are slightly odd since they are typically used like an operand
1750 /// but are represented as an operator internally. We typically write simm8:$src
1751 /// in a tablegen pattern, but this is just syntactic sugar for
1752 /// (imm:i32)<<P:Predicate_simm8>>:$imm which more directly describes the nodes
1753 /// that will be matched and the predicate (which is attached to the imm
1754 /// operator) that will be tested. In SelectionDAG this describes a
1755 /// ConstantSDNode whose internal value will be tested using the simm8 predicate.
1757 /// The corresponding GlobalISel representation is %1 = G_CONSTANT iN Value. In
1758 /// this representation, the immediate could be tested with an
1759 /// InstructionMatcher, InstructionOpcodeMatcher, OperandMatcher, and a
1760 /// OperandPredicateMatcher-subclass to check the Value meets the predicate but
1761 /// there are two implementation issues with producing that matcher
1762 /// configuration from the SelectionDAG pattern:
1763 /// * ImmLeaf is a PatFrag whose root is an InstructionMatcher. This means that
1764 /// were we to sink the immediate predicate to the operand we would have to
1765 /// have two partial implementations of PatFrag support, one for immediates
1766 /// and one for non-immediates.
1767 /// * At the point we handle the predicate, the OperandMatcher hasn't been
1768 /// created yet. If we were to sink the predicate to the OperandMatcher we
1769 /// would also have to complicate (or duplicate) the code that descends and
1770 /// creates matchers for the subtree.
1771 /// Overall, it's simpler to handle it in the place it was found.
1772 class InstructionImmPredicateMatcher : public InstructionPredicateMatcher {
1774 TreePredicateFn Predicate;
1777 InstructionImmPredicateMatcher(unsigned InsnVarID,
1778 const TreePredicateFn &Predicate)
1779 : InstructionPredicateMatcher(IPM_ImmPredicate, InsnVarID),
1780 Predicate(Predicate) {}
1782 bool isIdentical(const PredicateMatcher &B) const override {
1783 return InstructionPredicateMatcher::isIdentical(B) &&
1784 Predicate.getOrigPatFragRecord() ==
1785 cast<InstructionImmPredicateMatcher>(&B)
1786 ->Predicate.getOrigPatFragRecord();
1789 static bool classof(const PredicateMatcher *P) {
1790 return P->getKind() == IPM_ImmPredicate;
1793 void emitPredicateOpcodes(MatchTable &Table,
1794 RuleMatcher &Rule) const override {
1795 Table << MatchTable::Opcode(getMatchOpcodeForPredicate(Predicate))
1796 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1797 << MatchTable::Comment("Predicate")
1798 << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
1799 << MatchTable::LineBreak;
1803 /// Generates code to check that a memory instruction has a atomic ordering
1804 /// MachineMemoryOperand.
1805 class AtomicOrderingMMOPredicateMatcher : public InstructionPredicateMatcher {
1815 AOComparator Comparator;
1818 AtomicOrderingMMOPredicateMatcher(unsigned InsnVarID, StringRef Order,
1819 AOComparator Comparator = AO_Exactly)
1820 : InstructionPredicateMatcher(IPM_AtomicOrderingMMO, InsnVarID),
1821 Order(Order), Comparator(Comparator) {}
1823 static bool classof(const PredicateMatcher *P) {
1824 return P->getKind() == IPM_AtomicOrderingMMO;
1827 bool isIdentical(const PredicateMatcher &B) const override {
1828 if (!InstructionPredicateMatcher::isIdentical(B))
1830 const auto &R = *cast<AtomicOrderingMMOPredicateMatcher>(&B);
1831 return Order == R.Order && Comparator == R.Comparator;
1834 void emitPredicateOpcodes(MatchTable &Table,
1835 RuleMatcher &Rule) const override {
1836 StringRef Opcode = "GIM_CheckAtomicOrdering";
1838 if (Comparator == AO_OrStronger)
1839 Opcode = "GIM_CheckAtomicOrderingOrStrongerThan";
1840 if (Comparator == AO_WeakerThan)
1841 Opcode = "GIM_CheckAtomicOrderingWeakerThan";
1843 Table << MatchTable::Opcode(Opcode) << MatchTable::Comment("MI")
1844 << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Order")
1845 << MatchTable::NamedValue(("(int64_t)AtomicOrdering::" + Order).str())
1846 << MatchTable::LineBreak;
1850 /// Generates code to check that the size of an MMO is exactly N bytes.
1851 class MemorySizePredicateMatcher : public InstructionPredicateMatcher {
1857 MemorySizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, unsigned Size)
1858 : InstructionPredicateMatcher(IPM_MemoryLLTSize, InsnVarID),
1859 MMOIdx(MMOIdx), Size(Size) {}
1861 static bool classof(const PredicateMatcher *P) {
1862 return P->getKind() == IPM_MemoryLLTSize;
1864 bool isIdentical(const PredicateMatcher &B) const override {
1865 return InstructionPredicateMatcher::isIdentical(B) &&
1866 MMOIdx == cast<MemorySizePredicateMatcher>(&B)->MMOIdx &&
1867 Size == cast<MemorySizePredicateMatcher>(&B)->Size;
1870 void emitPredicateOpcodes(MatchTable &Table,
1871 RuleMatcher &Rule) const override {
1872 Table << MatchTable::Opcode("GIM_CheckMemorySizeEqualTo")
1873 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1874 << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
1875 << MatchTable::Comment("Size") << MatchTable::IntValue(Size)
1876 << MatchTable::LineBreak;
1880 class MemoryAddressSpacePredicateMatcher : public InstructionPredicateMatcher {
1883 SmallVector<unsigned, 4> AddrSpaces;
1886 MemoryAddressSpacePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
1887 ArrayRef<unsigned> AddrSpaces)
1888 : InstructionPredicateMatcher(IPM_MemoryAddressSpace, InsnVarID),
1889 MMOIdx(MMOIdx), AddrSpaces(AddrSpaces.begin(), AddrSpaces.end()) {}
1891 static bool classof(const PredicateMatcher *P) {
1892 return P->getKind() == IPM_MemoryAddressSpace;
1894 bool isIdentical(const PredicateMatcher &B) const override {
1895 if (!InstructionPredicateMatcher::isIdentical(B))
1897 auto *Other = cast<MemoryAddressSpacePredicateMatcher>(&B);
1898 return MMOIdx == Other->MMOIdx && AddrSpaces == Other->AddrSpaces;
1901 void emitPredicateOpcodes(MatchTable &Table,
1902 RuleMatcher &Rule) const override {
1903 Table << MatchTable::Opcode("GIM_CheckMemoryAddressSpace")
1904 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1905 << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
1906 // Encode number of address spaces to expect.
1907 << MatchTable::Comment("NumAddrSpace")
1908 << MatchTable::IntValue(AddrSpaces.size());
1909 for (unsigned AS : AddrSpaces)
1910 Table << MatchTable::Comment("AddrSpace") << MatchTable::IntValue(AS);
1912 Table << MatchTable::LineBreak;
1916 class MemoryAlignmentPredicateMatcher : public InstructionPredicateMatcher {
1922 MemoryAlignmentPredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
1924 : InstructionPredicateMatcher(IPM_MemoryAlignment, InsnVarID),
1925 MMOIdx(MMOIdx), MinAlign(MinAlign) {
1926 assert(MinAlign > 0);
1929 static bool classof(const PredicateMatcher *P) {
1930 return P->getKind() == IPM_MemoryAlignment;
1933 bool isIdentical(const PredicateMatcher &B) const override {
1934 if (!InstructionPredicateMatcher::isIdentical(B))
1936 auto *Other = cast<MemoryAlignmentPredicateMatcher>(&B);
1937 return MMOIdx == Other->MMOIdx && MinAlign == Other->MinAlign;
1940 void emitPredicateOpcodes(MatchTable &Table,
1941 RuleMatcher &Rule) const override {
1942 Table << MatchTable::Opcode("GIM_CheckMemoryAlignment")
1943 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1944 << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
1945 << MatchTable::Comment("MinAlign") << MatchTable::IntValue(MinAlign)
1946 << MatchTable::LineBreak;
1950 /// Generates code to check that the size of an MMO is less-than, equal-to, or
1951 /// greater than a given LLT.
1952 class MemoryVsLLTSizePredicateMatcher : public InstructionPredicateMatcher {
1962 RelationKind Relation;
1966 MemoryVsLLTSizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
1967 enum RelationKind Relation,
1969 : InstructionPredicateMatcher(IPM_MemoryVsLLTSize, InsnVarID),
1970 MMOIdx(MMOIdx), Relation(Relation), OpIdx(OpIdx) {}
1972 static bool classof(const PredicateMatcher *P) {
1973 return P->getKind() == IPM_MemoryVsLLTSize;
1975 bool isIdentical(const PredicateMatcher &B) const override {
1976 return InstructionPredicateMatcher::isIdentical(B) &&
1977 MMOIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->MMOIdx &&
1978 Relation == cast<MemoryVsLLTSizePredicateMatcher>(&B)->Relation &&
1979 OpIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->OpIdx;
1982 void emitPredicateOpcodes(MatchTable &Table,
1983 RuleMatcher &Rule) const override {
1984 Table << MatchTable::Opcode(Relation == EqualTo
1985 ? "GIM_CheckMemorySizeEqualToLLT"
1986 : Relation == GreaterThan
1987 ? "GIM_CheckMemorySizeGreaterThanLLT"
1988 : "GIM_CheckMemorySizeLessThanLLT")
1989 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1990 << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
1991 << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx)
1992 << MatchTable::LineBreak;
1996 /// Generates code to check an arbitrary C++ instruction predicate.
1997 class GenericInstructionPredicateMatcher : public InstructionPredicateMatcher {
1999 TreePredicateFn Predicate;
2002 GenericInstructionPredicateMatcher(unsigned InsnVarID,
2003 TreePredicateFn Predicate)
2004 : InstructionPredicateMatcher(IPM_GenericPredicate, InsnVarID),
2005 Predicate(Predicate) {}
2007 static bool classof(const InstructionPredicateMatcher *P) {
2008 return P->getKind() == IPM_GenericPredicate;
2010 bool isIdentical(const PredicateMatcher &B) const override {
2011 return InstructionPredicateMatcher::isIdentical(B) &&
2013 static_cast<const GenericInstructionPredicateMatcher &>(B)
2016 void emitPredicateOpcodes(MatchTable &Table,
2017 RuleMatcher &Rule) const override {
2018 Table << MatchTable::Opcode("GIM_CheckCxxInsnPredicate")
2019 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
2020 << MatchTable::Comment("FnId")
2021 << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
2022 << MatchTable::LineBreak;
2026 /// Generates code to check that a set of predicates and operands match for a
2027 /// particular instruction.
2029 /// Typical predicates include:
2030 /// * Has a specific opcode.
2031 /// * Has an nsw/nuw flag or doesn't.
2032 class InstructionMatcher final : public PredicateListMatcher<PredicateMatcher> {
2034 typedef std::vector<std::unique_ptr<OperandMatcher>> OperandVec;
2038 /// The operands to match. All rendered operands must be present even if the
2039 /// condition is always true.
2040 OperandVec Operands;
2041 bool NumOperandsCheck = true;
2043 std::string SymbolicName;
2046 /// PhysRegInputs - List list has an entry for each explicitly specified
2047 /// physreg input to the pattern. The first elt is the Register node, the
2048 /// second is the recorded slot number the input pattern match saved it in.
2049 SmallVector<std::pair<Record *, unsigned>, 2> PhysRegInputs;
2052 InstructionMatcher(RuleMatcher &Rule, StringRef SymbolicName)
2053 : Rule(Rule), SymbolicName(SymbolicName) {
2054 // We create a new instruction matcher.
2055 // Get a new ID for that instruction.
2056 InsnVarID = Rule.implicitlyDefineInsnVar(*this);
2059 /// Construct a new instruction predicate and add it to the matcher.
2060 template <class Kind, class... Args>
2061 Optional<Kind *> addPredicate(Args &&... args) {
2062 Predicates.emplace_back(
2063 std::make_unique<Kind>(getInsnVarID(), std::forward<Args>(args)...));
2064 return static_cast<Kind *>(Predicates.back().get());
2067 RuleMatcher &getRuleMatcher() const { return Rule; }
2069 unsigned getInsnVarID() const { return InsnVarID; }
2071 /// Add an operand to the matcher.
2072 OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName,
2073 unsigned AllocatedTemporariesBaseID) {
2074 Operands.emplace_back(new OperandMatcher(*this, OpIdx, SymbolicName,
2075 AllocatedTemporariesBaseID));
2076 if (!SymbolicName.empty())
2077 Rule.defineOperand(SymbolicName, *Operands.back());
2079 return *Operands.back();
2082 OperandMatcher &getOperand(unsigned OpIdx) {
2083 auto I = std::find_if(Operands.begin(), Operands.end(),
2084 [&OpIdx](const std::unique_ptr<OperandMatcher> &X) {
2085 return X->getOpIdx() == OpIdx;
2087 if (I != Operands.end())
2089 llvm_unreachable("Failed to lookup operand");
2092 OperandMatcher &addPhysRegInput(Record *Reg, unsigned OpIdx,
2093 unsigned TempOpIdx) {
2094 assert(SymbolicName.empty());
2095 OperandMatcher *OM = new OperandMatcher(*this, OpIdx, "", TempOpIdx);
2096 Operands.emplace_back(OM);
2097 Rule.definePhysRegOperand(Reg, *OM);
2098 PhysRegInputs.emplace_back(Reg, OpIdx);
2102 ArrayRef<std::pair<Record *, unsigned>> getPhysRegInputs() const {
2103 return PhysRegInputs;
2106 StringRef getSymbolicName() const { return SymbolicName; }
2107 unsigned getNumOperands() const { return Operands.size(); }
2108 OperandVec::iterator operands_begin() { return Operands.begin(); }
2109 OperandVec::iterator operands_end() { return Operands.end(); }
2110 iterator_range<OperandVec::iterator> operands() {
2111 return make_range(operands_begin(), operands_end());
2113 OperandVec::const_iterator operands_begin() const { return Operands.begin(); }
2114 OperandVec::const_iterator operands_end() const { return Operands.end(); }
2115 iterator_range<OperandVec::const_iterator> operands() const {
2116 return make_range(operands_begin(), operands_end());
2118 bool operands_empty() const { return Operands.empty(); }
2120 void pop_front() { Operands.erase(Operands.begin()); }
2124 /// Emit MatchTable opcodes that test whether the instruction named in
2125 /// InsnVarName matches all the predicates and all the operands.
2126 void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) {
2127 if (NumOperandsCheck)
2128 InstructionNumOperandsMatcher(InsnVarID, getNumOperands())
2129 .emitPredicateOpcodes(Table, Rule);
2131 emitPredicateListOpcodes(Table, Rule);
2133 for (const auto &Operand : Operands)
2134 Operand->emitPredicateOpcodes(Table, Rule);
2137 /// Compare the priority of this object and B.
2139 /// Returns true if this object is more important than B.
2140 bool isHigherPriorityThan(InstructionMatcher &B) {
2141 // Instruction matchers involving more operands have higher priority.
2142 if (Operands.size() > B.Operands.size())
2144 if (Operands.size() < B.Operands.size())
2147 for (auto &&P : zip(predicates(), B.predicates())) {
2148 auto L = static_cast<InstructionPredicateMatcher *>(std::get<0>(P).get());
2149 auto R = static_cast<InstructionPredicateMatcher *>(std::get<1>(P).get());
2150 if (L->isHigherPriorityThan(*R))
2152 if (R->isHigherPriorityThan(*L))
2156 for (auto Operand : zip(Operands, B.Operands)) {
2157 if (std::get<0>(Operand)->isHigherPriorityThan(*std::get<1>(Operand)))
2159 if (std::get<1>(Operand)->isHigherPriorityThan(*std::get<0>(Operand)))
2166 /// Report the maximum number of temporary operands needed by the instruction
2168 unsigned countRendererFns() {
2169 return std::accumulate(
2170 predicates().begin(), predicates().end(), 0,
2172 const std::unique_ptr<PredicateMatcher> &Predicate) {
2173 return A + Predicate->countRendererFns();
2176 Operands.begin(), Operands.end(), 0,
2177 [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) {
2178 return A + Operand->countRendererFns();
2182 InstructionOpcodeMatcher &getOpcodeMatcher() {
2183 for (auto &P : predicates())
2184 if (auto *OpMatcher = dyn_cast<InstructionOpcodeMatcher>(P.get()))
2186 llvm_unreachable("Didn't find an opcode matcher");
2189 bool isConstantInstruction() {
2190 return getOpcodeMatcher().isConstantInstruction();
2193 StringRef getOpcode() { return getOpcodeMatcher().getOpcode(); }
2196 StringRef RuleMatcher::getOpcode() const {
2197 return Matchers.front()->getOpcode();
2200 unsigned RuleMatcher::getNumOperands() const {
2201 return Matchers.front()->getNumOperands();
2204 LLTCodeGen RuleMatcher::getFirstConditionAsRootType() {
2205 InstructionMatcher &InsnMatcher = *Matchers.front();
2206 if (!InsnMatcher.predicates_empty())
2207 if (const auto *TM =
2208 dyn_cast<LLTOperandMatcher>(&**InsnMatcher.predicates_begin()))
2209 if (TM->getInsnVarID() == 0 && TM->getOpIdx() == 0)
2214 /// Generates code to check that the operand is a register defined by an
2215 /// instruction that matches the given instruction matcher.
2217 /// For example, the pattern:
2218 /// (set $dst, (G_MUL (G_ADD $src1, $src2), $src3))
2219 /// would use an InstructionOperandMatcher for operand 1 of the G_MUL to match
2221 /// (G_ADD $src1, $src2)
2223 class InstructionOperandMatcher : public OperandPredicateMatcher {
2225 std::unique_ptr<InstructionMatcher> InsnMatcher;
2228 InstructionOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
2229 RuleMatcher &Rule, StringRef SymbolicName)
2230 : OperandPredicateMatcher(OPM_Instruction, InsnVarID, OpIdx),
2231 InsnMatcher(new InstructionMatcher(Rule, SymbolicName)) {}
2233 static bool classof(const PredicateMatcher *P) {
2234 return P->getKind() == OPM_Instruction;
2237 InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; }
2239 void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const {
2240 const unsigned NewInsnVarID = InsnMatcher->getInsnVarID();
2241 Table << MatchTable::Opcode("GIM_RecordInsn")
2242 << MatchTable::Comment("DefineMI")
2243 << MatchTable::IntValue(NewInsnVarID) << MatchTable::Comment("MI")
2244 << MatchTable::IntValue(getInsnVarID())
2245 << MatchTable::Comment("OpIdx") << MatchTable::IntValue(getOpIdx())
2246 << MatchTable::Comment("MIs[" + llvm::to_string(NewInsnVarID) + "]")
2247 << MatchTable::LineBreak;
2250 void emitPredicateOpcodes(MatchTable &Table,
2251 RuleMatcher &Rule) const override {
2252 emitCaptureOpcodes(Table, Rule);
2253 InsnMatcher->emitPredicateOpcodes(Table, Rule);
2256 bool isHigherPriorityThan(const OperandPredicateMatcher &B) const override {
2257 if (OperandPredicateMatcher::isHigherPriorityThan(B))
2259 if (B.OperandPredicateMatcher::isHigherPriorityThan(*this))
2262 if (const InstructionOperandMatcher *BP =
2263 dyn_cast<InstructionOperandMatcher>(&B))
2264 if (InsnMatcher->isHigherPriorityThan(*BP->InsnMatcher))
2270 void InstructionMatcher::optimize() {
2271 SmallVector<std::unique_ptr<PredicateMatcher>, 8> Stash;
2272 const auto &OpcMatcher = getOpcodeMatcher();
2274 Stash.push_back(predicates_pop_front());
2275 if (Stash.back().get() == &OpcMatcher) {
2276 if (NumOperandsCheck && OpcMatcher.isVariadicNumOperands())
2278 new InstructionNumOperandsMatcher(InsnVarID, getNumOperands()));
2279 NumOperandsCheck = false;
2281 for (auto &OM : Operands)
2282 for (auto &OP : OM->predicates())
2283 if (isa<IntrinsicIDOperandMatcher>(OP)) {
2284 Stash.push_back(std::move(OP));
2285 OM->eraseNullPredicates();
2290 if (InsnVarID > 0) {
2291 assert(!Operands.empty() && "Nested instruction is expected to def a vreg");
2292 for (auto &OP : Operands[0]->predicates())
2294 Operands[0]->eraseNullPredicates();
2296 for (auto &OM : Operands) {
2297 for (auto &OP : OM->predicates())
2298 if (isa<LLTOperandMatcher>(OP))
2299 Stash.push_back(std::move(OP));
2300 OM->eraseNullPredicates();
2302 while (!Stash.empty())
2303 prependPredicate(Stash.pop_back_val());
2306 //===- Actions ------------------------------------------------------------===//
2307 class OperandRenderer {
2311 OR_CopyOrAddZeroReg,
2314 OR_CopyConstantAsImm,
2315 OR_CopyFConstantAsFPImm,
2329 OperandRenderer(RendererKind Kind) : Kind(Kind) {}
2330 virtual ~OperandRenderer() {}
2332 RendererKind getKind() const { return Kind; }
2334 virtual void emitRenderOpcodes(MatchTable &Table,
2335 RuleMatcher &Rule) const = 0;
2338 /// A CopyRenderer emits code to copy a single operand from an existing
2339 /// instruction to the one being built.
2340 class CopyRenderer : public OperandRenderer {
2343 /// The name of the operand.
2344 const StringRef SymbolicName;
2347 CopyRenderer(unsigned NewInsnID, StringRef SymbolicName)
2348 : OperandRenderer(OR_Copy), NewInsnID(NewInsnID),
2349 SymbolicName(SymbolicName) {
2350 assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
2353 static bool classof(const OperandRenderer *R) {
2354 return R->getKind() == OR_Copy;
2357 const StringRef getSymbolicName() const { return SymbolicName; }
2359 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2360 const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2361 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2362 Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
2363 << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID")
2364 << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2365 << MatchTable::IntValue(Operand.getOpIdx())
2366 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2370 /// A CopyRenderer emits code to copy a virtual register to a specific physical
2372 class CopyPhysRegRenderer : public OperandRenderer {
2378 CopyPhysRegRenderer(unsigned NewInsnID, Record *Reg)
2379 : OperandRenderer(OR_CopyPhysReg), NewInsnID(NewInsnID),
2384 static bool classof(const OperandRenderer *R) {
2385 return R->getKind() == OR_CopyPhysReg;
2388 Record *getPhysReg() const { return PhysReg; }
2390 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2391 const OperandMatcher &Operand = Rule.getPhysRegOperandMatcher(PhysReg);
2392 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2393 Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
2394 << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID")
2395 << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2396 << MatchTable::IntValue(Operand.getOpIdx())
2397 << MatchTable::Comment(PhysReg->getName())
2398 << MatchTable::LineBreak;
2402 /// A CopyOrAddZeroRegRenderer emits code to copy a single operand from an
2403 /// existing instruction to the one being built. If the operand turns out to be
2404 /// a 'G_CONSTANT 0' then it replaces the operand with a zero register.
2405 class CopyOrAddZeroRegRenderer : public OperandRenderer {
2408 /// The name of the operand.
2409 const StringRef SymbolicName;
2410 const Record *ZeroRegisterDef;
2413 CopyOrAddZeroRegRenderer(unsigned NewInsnID,
2414 StringRef SymbolicName, Record *ZeroRegisterDef)
2415 : OperandRenderer(OR_CopyOrAddZeroReg), NewInsnID(NewInsnID),
2416 SymbolicName(SymbolicName), ZeroRegisterDef(ZeroRegisterDef) {
2417 assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
2420 static bool classof(const OperandRenderer *R) {
2421 return R->getKind() == OR_CopyOrAddZeroReg;
2424 const StringRef getSymbolicName() const { return SymbolicName; }
2426 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2427 const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2428 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2429 Table << MatchTable::Opcode("GIR_CopyOrAddZeroReg")
2430 << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2431 << MatchTable::Comment("OldInsnID")
2432 << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2433 << MatchTable::IntValue(Operand.getOpIdx())
2434 << MatchTable::NamedValue(
2435 (ZeroRegisterDef->getValue("Namespace")
2436 ? ZeroRegisterDef->getValueAsString("Namespace")
2438 ZeroRegisterDef->getName())
2439 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2443 /// A CopyConstantAsImmRenderer emits code to render a G_CONSTANT instruction to
2444 /// an extended immediate operand.
2445 class CopyConstantAsImmRenderer : public OperandRenderer {
2448 /// The name of the operand.
2449 const std::string SymbolicName;
2453 CopyConstantAsImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
2454 : OperandRenderer(OR_CopyConstantAsImm), NewInsnID(NewInsnID),
2455 SymbolicName(SymbolicName), Signed(true) {}
2457 static bool classof(const OperandRenderer *R) {
2458 return R->getKind() == OR_CopyConstantAsImm;
2461 const StringRef getSymbolicName() const { return SymbolicName; }
2463 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2464 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2465 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2466 Table << MatchTable::Opcode(Signed ? "GIR_CopyConstantAsSImm"
2467 : "GIR_CopyConstantAsUImm")
2468 << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2469 << MatchTable::Comment("OldInsnID")
2470 << MatchTable::IntValue(OldInsnVarID)
2471 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2475 /// A CopyFConstantAsFPImmRenderer emits code to render a G_FCONSTANT
2476 /// instruction to an extended immediate operand.
2477 class CopyFConstantAsFPImmRenderer : public OperandRenderer {
2480 /// The name of the operand.
2481 const std::string SymbolicName;
2484 CopyFConstantAsFPImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
2485 : OperandRenderer(OR_CopyFConstantAsFPImm), NewInsnID(NewInsnID),
2486 SymbolicName(SymbolicName) {}
2488 static bool classof(const OperandRenderer *R) {
2489 return R->getKind() == OR_CopyFConstantAsFPImm;
2492 const StringRef getSymbolicName() const { return SymbolicName; }
2494 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2495 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2496 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2497 Table << MatchTable::Opcode("GIR_CopyFConstantAsFPImm")
2498 << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2499 << MatchTable::Comment("OldInsnID")
2500 << MatchTable::IntValue(OldInsnVarID)
2501 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2505 /// A CopySubRegRenderer emits code to copy a single register operand from an
2506 /// existing instruction to the one being built and indicate that only a
2507 /// subregister should be copied.
2508 class CopySubRegRenderer : public OperandRenderer {
2511 /// The name of the operand.
2512 const StringRef SymbolicName;
2513 /// The subregister to extract.
2514 const CodeGenSubRegIndex *SubReg;
2517 CopySubRegRenderer(unsigned NewInsnID, StringRef SymbolicName,
2518 const CodeGenSubRegIndex *SubReg)
2519 : OperandRenderer(OR_CopySubReg), NewInsnID(NewInsnID),
2520 SymbolicName(SymbolicName), SubReg(SubReg) {}
2522 static bool classof(const OperandRenderer *R) {
2523 return R->getKind() == OR_CopySubReg;
2526 const StringRef getSymbolicName() const { return SymbolicName; }
2528 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2529 const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2530 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2531 Table << MatchTable::Opcode("GIR_CopySubReg")
2532 << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2533 << MatchTable::Comment("OldInsnID")
2534 << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2535 << MatchTable::IntValue(Operand.getOpIdx())
2536 << MatchTable::Comment("SubRegIdx")
2537 << MatchTable::IntValue(SubReg->EnumValue)
2538 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2542 /// Adds a specific physical register to the instruction being built.
2543 /// This is typically useful for WZR/XZR on AArch64.
2544 class AddRegisterRenderer : public OperandRenderer {
2547 const Record *RegisterDef;
2551 AddRegisterRenderer(unsigned InsnID, const Record *RegisterDef,
2553 : OperandRenderer(OR_Register), InsnID(InsnID), RegisterDef(RegisterDef),
2556 static bool classof(const OperandRenderer *R) {
2557 return R->getKind() == OR_Register;
2560 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2561 Table << MatchTable::Opcode("GIR_AddRegister")
2562 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2563 << MatchTable::NamedValue(
2564 (RegisterDef->getValue("Namespace")
2565 ? RegisterDef->getValueAsString("Namespace")
2567 RegisterDef->getName())
2568 << MatchTable::Comment("AddRegisterRegFlags");
2570 // TODO: This is encoded as a 64-bit element, but only 16 or 32-bits are
2571 // really needed for a physical register reference. We can pack the
2572 // register and flags in a single field.
2574 Table << MatchTable::NamedValue("RegState::Define");
2576 Table << MatchTable::IntValue(0);
2577 Table << MatchTable::LineBreak;
2581 /// Adds a specific temporary virtual register to the instruction being built.
2582 /// This is used to chain instructions together when emitting multiple
2584 class TempRegRenderer : public OperandRenderer {
2591 TempRegRenderer(unsigned InsnID, unsigned TempRegID, bool IsDef = false)
2592 : OperandRenderer(OR_Register), InsnID(InsnID), TempRegID(TempRegID),
2595 static bool classof(const OperandRenderer *R) {
2596 return R->getKind() == OR_TempRegister;
2599 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2600 Table << MatchTable::Opcode("GIR_AddTempRegister")
2601 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2602 << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID)
2603 << MatchTable::Comment("TempRegFlags");
2605 Table << MatchTable::NamedValue("RegState::Define");
2607 Table << MatchTable::IntValue(0);
2608 Table << MatchTable::LineBreak;
2612 /// Adds a specific immediate to the instruction being built.
2613 class ImmRenderer : public OperandRenderer {
2619 ImmRenderer(unsigned InsnID, int64_t Imm)
2620 : OperandRenderer(OR_Imm), InsnID(InsnID), Imm(Imm) {}
2622 static bool classof(const OperandRenderer *R) {
2623 return R->getKind() == OR_Imm;
2626 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2627 Table << MatchTable::Opcode("GIR_AddImm") << MatchTable::Comment("InsnID")
2628 << MatchTable::IntValue(InsnID) << MatchTable::Comment("Imm")
2629 << MatchTable::IntValue(Imm) << MatchTable::LineBreak;
2633 /// Adds an enum value for a subreg index to the instruction being built.
2634 class SubRegIndexRenderer : public OperandRenderer {
2637 const CodeGenSubRegIndex *SubRegIdx;
2640 SubRegIndexRenderer(unsigned InsnID, const CodeGenSubRegIndex *SRI)
2641 : OperandRenderer(OR_SubRegIndex), InsnID(InsnID), SubRegIdx(SRI) {}
2643 static bool classof(const OperandRenderer *R) {
2644 return R->getKind() == OR_SubRegIndex;
2647 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2648 Table << MatchTable::Opcode("GIR_AddImm") << MatchTable::Comment("InsnID")
2649 << MatchTable::IntValue(InsnID) << MatchTable::Comment("SubRegIndex")
2650 << MatchTable::IntValue(SubRegIdx->EnumValue)
2651 << MatchTable::LineBreak;
2655 /// Adds operands by calling a renderer function supplied by the ComplexPattern
2656 /// matcher function.
2657 class RenderComplexPatternOperand : public OperandRenderer {
2660 const Record &TheDef;
2661 /// The name of the operand.
2662 const StringRef SymbolicName;
2663 /// The renderer number. This must be unique within a rule since it's used to
2664 /// identify a temporary variable to hold the renderer function.
2665 unsigned RendererID;
2666 /// When provided, this is the suboperand of the ComplexPattern operand to
2667 /// render. Otherwise all the suboperands will be rendered.
2668 Optional<unsigned> SubOperand;
2670 unsigned getNumOperands() const {
2671 return TheDef.getValueAsDag("Operands")->getNumArgs();
2675 RenderComplexPatternOperand(unsigned InsnID, const Record &TheDef,
2676 StringRef SymbolicName, unsigned RendererID,
2677 Optional<unsigned> SubOperand = None)
2678 : OperandRenderer(OR_ComplexPattern), InsnID(InsnID), TheDef(TheDef),
2679 SymbolicName(SymbolicName), RendererID(RendererID),
2680 SubOperand(SubOperand) {}
2682 static bool classof(const OperandRenderer *R) {
2683 return R->getKind() == OR_ComplexPattern;
2686 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2687 Table << MatchTable::Opcode(SubOperand.hasValue() ? "GIR_ComplexSubOperandRenderer"
2688 : "GIR_ComplexRenderer")
2689 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2690 << MatchTable::Comment("RendererID")
2691 << MatchTable::IntValue(RendererID);
2692 if (SubOperand.hasValue())
2693 Table << MatchTable::Comment("SubOperand")
2694 << MatchTable::IntValue(SubOperand.getValue());
2695 Table << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2699 class CustomRenderer : public OperandRenderer {
2702 const Record &Renderer;
2703 /// The name of the operand.
2704 const std::string SymbolicName;
2707 CustomRenderer(unsigned InsnID, const Record &Renderer,
2708 StringRef SymbolicName)
2709 : OperandRenderer(OR_Custom), InsnID(InsnID), Renderer(Renderer),
2710 SymbolicName(SymbolicName) {}
2712 static bool classof(const OperandRenderer *R) {
2713 return R->getKind() == OR_Custom;
2716 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2717 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2718 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2719 Table << MatchTable::Opcode("GIR_CustomRenderer")
2720 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2721 << MatchTable::Comment("OldInsnID")
2722 << MatchTable::IntValue(OldInsnVarID)
2723 << MatchTable::Comment("Renderer")
2724 << MatchTable::NamedValue(
2725 "GICR_" + Renderer.getValueAsString("RendererFn").str())
2726 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2730 class CustomOperandRenderer : public OperandRenderer {
2733 const Record &Renderer;
2734 /// The name of the operand.
2735 const std::string SymbolicName;
2738 CustomOperandRenderer(unsigned InsnID, const Record &Renderer,
2739 StringRef SymbolicName)
2740 : OperandRenderer(OR_CustomOperand), InsnID(InsnID), Renderer(Renderer),
2741 SymbolicName(SymbolicName) {}
2743 static bool classof(const OperandRenderer *R) {
2744 return R->getKind() == OR_CustomOperand;
2747 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2748 const OperandMatcher &OpdMatcher = Rule.getOperandMatcher(SymbolicName);
2749 Table << MatchTable::Opcode("GIR_CustomOperandRenderer")
2750 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2751 << MatchTable::Comment("OldInsnID")
2752 << MatchTable::IntValue(OpdMatcher.getInsnVarID())
2753 << MatchTable::Comment("OpIdx")
2754 << MatchTable::IntValue(OpdMatcher.getOpIdx())
2755 << MatchTable::Comment("OperandRenderer")
2756 << MatchTable::NamedValue(
2757 "GICR_" + Renderer.getValueAsString("RendererFn").str())
2758 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2762 /// An action taken when all Matcher predicates succeeded for a parent rule.
2764 /// Typical actions include:
2765 /// * Changing the opcode of an instruction.
2766 /// * Adding an operand to an instruction.
2769 virtual ~MatchAction() {}
2771 /// Emit the MatchTable opcodes to implement the action.
2772 virtual void emitActionOpcodes(MatchTable &Table,
2773 RuleMatcher &Rule) const = 0;
2776 /// Generates a comment describing the matched rule being acted upon.
2777 class DebugCommentAction : public MatchAction {
2782 DebugCommentAction(StringRef S) : S(S) {}
2784 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2785 Table << MatchTable::Comment(S) << MatchTable::LineBreak;
2789 /// Generates code to build an instruction or mutate an existing instruction
2790 /// into the desired instruction when this is possible.
2791 class BuildMIAction : public MatchAction {
2794 const CodeGenInstruction *I;
2795 InstructionMatcher *Matched;
2796 std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers;
2798 /// True if the instruction can be built solely by mutating the opcode.
2799 bool canMutate(RuleMatcher &Rule, const InstructionMatcher *Insn) const {
2803 if (OperandRenderers.size() != Insn->getNumOperands())
2806 for (const auto &Renderer : enumerate(OperandRenderers)) {
2807 if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) {
2808 const OperandMatcher &OM = Rule.getOperandMatcher(Copy->getSymbolicName());
2809 if (Insn != &OM.getInstructionMatcher() ||
2810 OM.getOpIdx() != Renderer.index())
2820 BuildMIAction(unsigned InsnID, const CodeGenInstruction *I)
2821 : InsnID(InsnID), I(I), Matched(nullptr) {}
2823 unsigned getInsnID() const { return InsnID; }
2824 const CodeGenInstruction *getCGI() const { return I; }
2826 void chooseInsnToMutate(RuleMatcher &Rule) {
2827 for (auto *MutateCandidate : Rule.mutatable_insns()) {
2828 if (canMutate(Rule, MutateCandidate)) {
2829 // Take the first one we're offered that we're able to mutate.
2830 Rule.reserveInsnMatcherForMutation(MutateCandidate);
2831 Matched = MutateCandidate;
2837 template <class Kind, class... Args>
2838 Kind &addRenderer(Args&&... args) {
2839 OperandRenderers.emplace_back(
2840 std::make_unique<Kind>(InsnID, std::forward<Args>(args)...));
2841 return *static_cast<Kind *>(OperandRenderers.back().get());
2844 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2846 assert(canMutate(Rule, Matched) &&
2847 "Arranged to mutate an insn that isn't mutatable");
2849 unsigned RecycleInsnID = Rule.getInsnVarID(*Matched);
2850 Table << MatchTable::Opcode("GIR_MutateOpcode")
2851 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2852 << MatchTable::Comment("RecycleInsnID")
2853 << MatchTable::IntValue(RecycleInsnID)
2854 << MatchTable::Comment("Opcode")
2855 << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
2856 << MatchTable::LineBreak;
2858 if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) {
2859 for (auto Def : I->ImplicitDefs) {
2860 auto Namespace = Def->getValue("Namespace")
2861 ? Def->getValueAsString("Namespace")
2863 Table << MatchTable::Opcode("GIR_AddImplicitDef")
2864 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2865 << MatchTable::NamedValue(Namespace, Def->getName())
2866 << MatchTable::LineBreak;
2868 for (auto Use : I->ImplicitUses) {
2869 auto Namespace = Use->getValue("Namespace")
2870 ? Use->getValueAsString("Namespace")
2872 Table << MatchTable::Opcode("GIR_AddImplicitUse")
2873 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2874 << MatchTable::NamedValue(Namespace, Use->getName())
2875 << MatchTable::LineBreak;
2881 // TODO: Simple permutation looks like it could be almost as common as
2882 // mutation due to commutative operations.
2884 Table << MatchTable::Opcode("GIR_BuildMI") << MatchTable::Comment("InsnID")
2885 << MatchTable::IntValue(InsnID) << MatchTable::Comment("Opcode")
2886 << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
2887 << MatchTable::LineBreak;
2888 for (const auto &Renderer : OperandRenderers)
2889 Renderer->emitRenderOpcodes(Table, Rule);
2891 if (I->mayLoad || I->mayStore) {
2892 Table << MatchTable::Opcode("GIR_MergeMemOperands")
2893 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2894 << MatchTable::Comment("MergeInsnID's");
2895 // Emit the ID's for all the instructions that are matched by this rule.
2896 // TODO: Limit this to matched instructions that mayLoad/mayStore or have
2897 // some other means of having a memoperand. Also limit this to
2898 // emitted instructions that expect to have a memoperand too. For
2899 // example, (G_SEXT (G_LOAD x)) that results in separate load and
2900 // sign-extend instructions shouldn't put the memoperand on the
2901 // sign-extend since it has no effect there.
2902 std::vector<unsigned> MergeInsnIDs;
2903 for (const auto &IDMatcherPair : Rule.defined_insn_vars())
2904 MergeInsnIDs.push_back(IDMatcherPair.second);
2905 llvm::sort(MergeInsnIDs);
2906 for (const auto &MergeInsnID : MergeInsnIDs)
2907 Table << MatchTable::IntValue(MergeInsnID);
2908 Table << MatchTable::NamedValue("GIU_MergeMemOperands_EndOfList")
2909 << MatchTable::LineBreak;
2912 // FIXME: This is a hack but it's sufficient for ISel. We'll need to do
2913 // better for combines. Particularly when there are multiple match
2916 Table << MatchTable::Opcode("GIR_EraseFromParent")
2917 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2918 << MatchTable::LineBreak;
2922 /// Generates code to constrain the operands of an output instruction to the
2923 /// register classes specified by the definition of that instruction.
2924 class ConstrainOperandsToDefinitionAction : public MatchAction {
2928 ConstrainOperandsToDefinitionAction(unsigned InsnID) : InsnID(InsnID) {}
2930 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2931 Table << MatchTable::Opcode("GIR_ConstrainSelectedInstOperands")
2932 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2933 << MatchTable::LineBreak;
2937 /// Generates code to constrain the specified operand of an output instruction
2938 /// to the specified register class.
2939 class ConstrainOperandToRegClassAction : public MatchAction {
2942 const CodeGenRegisterClass &RC;
2945 ConstrainOperandToRegClassAction(unsigned InsnID, unsigned OpIdx,
2946 const CodeGenRegisterClass &RC)
2947 : InsnID(InsnID), OpIdx(OpIdx), RC(RC) {}
2949 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2950 Table << MatchTable::Opcode("GIR_ConstrainOperandRC")
2951 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2952 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
2953 << MatchTable::Comment("RC " + RC.getName())
2954 << MatchTable::IntValue(RC.EnumValue) << MatchTable::LineBreak;
2958 /// Generates code to create a temporary register which can be used to chain
2959 /// instructions together.
2960 class MakeTempRegisterAction : public MatchAction {
2966 MakeTempRegisterAction(const LLTCodeGen &Ty, unsigned TempRegID)
2967 : Ty(Ty), TempRegID(TempRegID) {
2968 KnownTypes.insert(Ty);
2971 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2972 Table << MatchTable::Opcode("GIR_MakeTempReg")
2973 << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID)
2974 << MatchTable::Comment("TypeID")
2975 << MatchTable::NamedValue(Ty.getCxxEnumValue())
2976 << MatchTable::LineBreak;
2980 InstructionMatcher &RuleMatcher::addInstructionMatcher(StringRef SymbolicName) {
2981 Matchers.emplace_back(new InstructionMatcher(*this, SymbolicName));
2982 MutatableInsns.insert(Matchers.back().get());
2983 return *Matchers.back();
2986 void RuleMatcher::addRequiredFeature(Record *Feature) {
2987 RequiredFeatures.push_back(Feature);
2990 const std::vector<Record *> &RuleMatcher::getRequiredFeatures() const {
2991 return RequiredFeatures;
2994 // Emplaces an action of the specified Kind at the end of the action list.
2996 // Returns a reference to the newly created action.
2998 // Like std::vector::emplace_back(), may invalidate all iterators if the new
2999 // size exceeds the capacity. Otherwise, only invalidates the past-the-end
3001 template <class Kind, class... Args>
3002 Kind &RuleMatcher::addAction(Args &&... args) {
3003 Actions.emplace_back(std::make_unique<Kind>(std::forward<Args>(args)...));
3004 return *static_cast<Kind *>(Actions.back().get());
3007 // Emplaces an action of the specified Kind before the given insertion point.
3009 // Returns an iterator pointing at the newly created instruction.
3011 // Like std::vector::insert(), may invalidate all iterators if the new size
3012 // exceeds the capacity. Otherwise, only invalidates the iterators from the
3013 // insertion point onwards.
3014 template <class Kind, class... Args>
3015 action_iterator RuleMatcher::insertAction(action_iterator InsertPt,
3017 return Actions.emplace(InsertPt,
3018 std::make_unique<Kind>(std::forward<Args>(args)...));
3021 unsigned RuleMatcher::implicitlyDefineInsnVar(InstructionMatcher &Matcher) {
3022 unsigned NewInsnVarID = NextInsnVarID++;
3023 InsnVariableIDs[&Matcher] = NewInsnVarID;
3024 return NewInsnVarID;
3027 unsigned RuleMatcher::getInsnVarID(InstructionMatcher &InsnMatcher) const {
3028 const auto &I = InsnVariableIDs.find(&InsnMatcher);
3029 if (I != InsnVariableIDs.end())
3031 llvm_unreachable("Matched Insn was not captured in a local variable");
3034 void RuleMatcher::defineOperand(StringRef SymbolicName, OperandMatcher &OM) {
3035 if (DefinedOperands.find(SymbolicName) == DefinedOperands.end()) {
3036 DefinedOperands[SymbolicName] = &OM;
3040 // If the operand is already defined, then we must ensure both references in
3041 // the matcher have the exact same node.
3042 OM.addPredicate<SameOperandMatcher>(OM.getSymbolicName());
3045 void RuleMatcher::definePhysRegOperand(Record *Reg, OperandMatcher &OM) {
3046 if (PhysRegOperands.find(Reg) == PhysRegOperands.end()) {
3047 PhysRegOperands[Reg] = &OM;
3052 InstructionMatcher &
3053 RuleMatcher::getInstructionMatcher(StringRef SymbolicName) const {
3054 for (const auto &I : InsnVariableIDs)
3055 if (I.first->getSymbolicName() == SymbolicName)
3058 ("Failed to lookup instruction " + SymbolicName).str().c_str());
3061 const OperandMatcher &
3062 RuleMatcher::getPhysRegOperandMatcher(Record *Reg) const {
3063 const auto &I = PhysRegOperands.find(Reg);
3065 if (I == PhysRegOperands.end()) {
3066 PrintFatalError(SrcLoc, "Register " + Reg->getName() +
3067 " was not declared in matcher");
3073 const OperandMatcher &
3074 RuleMatcher::getOperandMatcher(StringRef Name) const {
3075 const auto &I = DefinedOperands.find(Name);
3077 if (I == DefinedOperands.end())
3078 PrintFatalError(SrcLoc, "Operand " + Name + " was not declared in matcher");
3083 void RuleMatcher::emit(MatchTable &Table) {
3084 if (Matchers.empty())
3085 llvm_unreachable("Unexpected empty matcher!");
3087 // The representation supports rules that require multiple roots such as:
3089 // %elt0(s32) = G_LOAD %ptr
3090 // %1(p0) = G_ADD %ptr, 4
3091 // %elt1(s32) = G_LOAD p0 %1
3092 // which could be usefully folded into:
3094 // %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr
3095 // on some targets but we don't need to make use of that yet.
3096 assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
3098 unsigned LabelID = Table.allocateLabelID();
3099 Table << MatchTable::Opcode("GIM_Try", +1)
3100 << MatchTable::Comment("On fail goto")
3101 << MatchTable::JumpTarget(LabelID)
3102 << MatchTable::Comment(("Rule ID " + Twine(RuleID) + " //").str())
3103 << MatchTable::LineBreak;
3105 if (!RequiredFeatures.empty()) {
3106 Table << MatchTable::Opcode("GIM_CheckFeatures")
3107 << MatchTable::NamedValue(getNameForFeatureBitset(RequiredFeatures))
3108 << MatchTable::LineBreak;
3111 Matchers.front()->emitPredicateOpcodes(Table, *this);
3113 // We must also check if it's safe to fold the matched instructions.
3114 if (InsnVariableIDs.size() >= 2) {
3115 // Invert the map to create stable ordering (by var names)
3116 SmallVector<unsigned, 2> InsnIDs;
3117 for (const auto &Pair : InsnVariableIDs) {
3118 // Skip the root node since it isn't moving anywhere. Everything else is
3119 // sinking to meet it.
3120 if (Pair.first == Matchers.front().get())
3123 InsnIDs.push_back(Pair.second);
3125 llvm::sort(InsnIDs);
3127 for (const auto &InsnID : InsnIDs) {
3128 // Reject the difficult cases until we have a more accurate check.
3129 Table << MatchTable::Opcode("GIM_CheckIsSafeToFold")
3130 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
3131 << MatchTable::LineBreak;
3133 // FIXME: Emit checks to determine it's _actually_ safe to fold and/or
3134 // account for unsafe cases.
3139 // MI0--> %2 = ... %0
3140 // It's not safe to erase MI1. We currently handle this by not
3141 // erasing %0 (even when it's dead).
3144 // MI1--> %0 = load volatile @a
3145 // %1 = load volatile @a
3146 // MI0--> %2 = ... %0
3147 // It's not safe to sink %0's def past %1. We currently handle
3148 // this by rejecting all loads.
3151 // MI1--> %0 = load @a
3153 // MI0--> %2 = ... %0
3154 // It's not safe to sink %0's def past %1. We currently handle
3155 // this by rejecting all loads.
3158 // G_CONDBR %cond, @BB1
3160 // MI1--> %0 = load @a
3163 // MI0--> %2 = ... %0
3164 // It's not always safe to sink %0 across control flow. In this
3165 // case it may introduce a memory fault. We currentl handle this
3166 // by rejecting all loads.
3170 for (const auto &PM : EpilogueMatchers)
3171 PM->emitPredicateOpcodes(Table, *this);
3173 for (const auto &MA : Actions)
3174 MA->emitActionOpcodes(Table, *this);
3176 if (Table.isWithCoverage())
3177 Table << MatchTable::Opcode("GIR_Coverage") << MatchTable::IntValue(RuleID)
3178 << MatchTable::LineBreak;
3180 Table << MatchTable::Comment(("GIR_Coverage, " + Twine(RuleID) + ",").str())
3181 << MatchTable::LineBreak;
3183 Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak
3184 << MatchTable::Label(LabelID);
3185 ++NumPatternEmitted;
3188 bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
3189 // Rules involving more match roots have higher priority.
3190 if (Matchers.size() > B.Matchers.size())
3192 if (Matchers.size() < B.Matchers.size())
3195 for (auto Matcher : zip(Matchers, B.Matchers)) {
3196 if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher)))
3198 if (std::get<1>(Matcher)->isHigherPriorityThan(*std::get<0>(Matcher)))
3205 unsigned RuleMatcher::countRendererFns() const {
3206 return std::accumulate(
3207 Matchers.begin(), Matchers.end(), 0,
3208 [](unsigned A, const std::unique_ptr<InstructionMatcher> &Matcher) {
3209 return A + Matcher->countRendererFns();
3213 bool OperandPredicateMatcher::isHigherPriorityThan(
3214 const OperandPredicateMatcher &B) const {
3215 // Generally speaking, an instruction is more important than an Int or a
3216 // LiteralInt because it can cover more nodes but theres an exception to
3217 // this. G_CONSTANT's are less important than either of those two because they
3218 // are more permissive.
3220 const InstructionOperandMatcher *AOM =
3221 dyn_cast<InstructionOperandMatcher>(this);
3222 const InstructionOperandMatcher *BOM =
3223 dyn_cast<InstructionOperandMatcher>(&B);
3224 bool AIsConstantInsn = AOM && AOM->getInsnMatcher().isConstantInstruction();
3225 bool BIsConstantInsn = BOM && BOM->getInsnMatcher().isConstantInstruction();
3228 // The relative priorities between a G_CONSTANT and any other instruction
3229 // don't actually matter but this code is needed to ensure a strict weak
3230 // ordering. This is particularly important on Windows where the rules will
3231 // be incorrectly sorted without it.
3232 if (AIsConstantInsn != BIsConstantInsn)
3233 return AIsConstantInsn < BIsConstantInsn;
3237 if (AOM && AIsConstantInsn && (B.Kind == OPM_Int || B.Kind == OPM_LiteralInt))
3239 if (BOM && BIsConstantInsn && (Kind == OPM_Int || Kind == OPM_LiteralInt))
3242 return Kind < B.Kind;
3245 void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
3246 RuleMatcher &Rule) const {
3247 const OperandMatcher &OtherOM = Rule.getOperandMatcher(MatchingName);
3248 unsigned OtherInsnVarID = Rule.getInsnVarID(OtherOM.getInstructionMatcher());
3249 assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getInsnVarID());
3251 Table << MatchTable::Opcode("GIM_CheckIsSameOperand")
3252 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
3253 << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx)
3254 << MatchTable::Comment("OtherMI")
3255 << MatchTable::IntValue(OtherInsnVarID)
3256 << MatchTable::Comment("OtherOpIdx")
3257 << MatchTable::IntValue(OtherOM.getOpIdx())
3258 << MatchTable::LineBreak;
3261 //===- GlobalISelEmitter class --------------------------------------------===//
3263 class GlobalISelEmitter {
3265 explicit GlobalISelEmitter(RecordKeeper &RK);
3266 void run(raw_ostream &OS);
3269 const RecordKeeper &RK;
3270 const CodeGenDAGPatterns CGP;
3271 const CodeGenTarget &Target;
3272 CodeGenRegBank CGRegs;
3274 /// Keep track of the equivalence between SDNodes and Instruction by mapping
3275 /// SDNodes to the GINodeEquiv mapping. We need to map to the GINodeEquiv to
3276 /// check for attributes on the relation such as CheckMMOIsNonAtomic.
3277 /// This is defined using 'GINodeEquiv' in the target description.
3278 DenseMap<Record *, Record *> NodeEquivs;
3280 /// Keep track of the equivalence between ComplexPattern's and
3281 /// GIComplexOperandMatcher. Map entries are specified by subclassing
3282 /// GIComplexPatternEquiv.
3283 DenseMap<const Record *, const Record *> ComplexPatternEquivs;
3285 /// Keep track of the equivalence between SDNodeXForm's and
3286 /// GICustomOperandRenderer. Map entries are specified by subclassing
3287 /// GISDNodeXFormEquiv.
3288 DenseMap<const Record *, const Record *> SDNodeXFormEquivs;
3290 /// Keep track of Scores of PatternsToMatch similar to how the DAG does.
3291 /// This adds compatibility for RuleMatchers to use this for ordering rules.
3292 DenseMap<uint64_t, int> RuleMatcherScores;
3294 // Map of predicates to their subtarget features.
3295 SubtargetFeatureInfoMap SubtargetFeatures;
3297 // Rule coverage information.
3298 Optional<CodeGenCoverage> RuleCoverage;
3300 void gatherOpcodeValues();
3301 void gatherTypeIDValues();
3302 void gatherNodeEquivs();
3304 Record *findNodeEquiv(Record *N) const;
3305 const CodeGenInstruction *getEquivNode(Record &Equiv,
3306 const TreePatternNode *N) const;
3308 Error importRulePredicates(RuleMatcher &M, ArrayRef<Predicate> Predicates);
3309 Expected<InstructionMatcher &>
3310 createAndImportSelDAGMatcher(RuleMatcher &Rule,
3311 InstructionMatcher &InsnMatcher,
3312 const TreePatternNode *Src, unsigned &TempOpIdx);
3313 Error importComplexPatternOperandMatcher(OperandMatcher &OM, Record *R,
3314 unsigned &TempOpIdx) const;
3315 Error importChildMatcher(RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
3316 const TreePatternNode *SrcChild,
3317 bool OperandIsAPointer, bool OperandIsImmArg,
3318 unsigned OpIdx, unsigned &TempOpIdx);
3320 Expected<BuildMIAction &> createAndImportInstructionRenderer(
3321 RuleMatcher &M, InstructionMatcher &InsnMatcher,
3322 const TreePatternNode *Src, const TreePatternNode *Dst);
3323 Expected<action_iterator> createAndImportSubInstructionRenderer(
3324 action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst,
3326 Expected<action_iterator>
3327 createInstructionRenderer(action_iterator InsertPt, RuleMatcher &M,
3328 const TreePatternNode *Dst);
3329 void importExplicitDefRenderers(BuildMIAction &DstMIBuilder);
3331 Expected<action_iterator>
3332 importExplicitUseRenderers(action_iterator InsertPt, RuleMatcher &M,
3333 BuildMIAction &DstMIBuilder,
3334 const llvm::TreePatternNode *Dst);
3335 Expected<action_iterator>
3336 importExplicitUseRenderer(action_iterator InsertPt, RuleMatcher &Rule,
3337 BuildMIAction &DstMIBuilder,
3338 TreePatternNode *DstChild);
3339 Error importDefaultOperandRenderers(action_iterator InsertPt, RuleMatcher &M,
3340 BuildMIAction &DstMIBuilder,
3341 DagInit *DefaultOps) const;
3343 importImplicitDefRenderers(BuildMIAction &DstMIBuilder,
3344 const std::vector<Record *> &ImplicitDefs) const;
3346 void emitCxxPredicateFns(raw_ostream &OS, StringRef CodeFieldName,
3347 StringRef TypeIdentifier, StringRef ArgType,
3348 StringRef ArgName, StringRef AdditionalDeclarations,
3349 std::function<bool(const Record *R)> Filter);
3350 void emitImmPredicateFns(raw_ostream &OS, StringRef TypeIdentifier,
3352 std::function<bool(const Record *R)> Filter);
3353 void emitMIPredicateFns(raw_ostream &OS);
3355 /// Analyze pattern \p P, returning a matcher for it if possible.
3356 /// Otherwise, return an Error explaining why we don't support it.
3357 Expected<RuleMatcher> runOnPattern(const PatternToMatch &P);
3359 void declareSubtargetFeature(Record *Predicate);
3361 MatchTable buildMatchTable(MutableArrayRef<RuleMatcher> Rules, bool Optimize,
3364 /// Infer a CodeGenRegisterClass for the type of \p SuperRegNode. The returned
3365 /// CodeGenRegisterClass will support the CodeGenRegisterClass of
3366 /// \p SubRegNode, and the subregister index defined by \p SubRegIdxNode.
3367 /// If no register class is found, return None.
3368 Optional<const CodeGenRegisterClass *>
3369 inferSuperRegisterClassForNode(const TypeSetByHwMode &Ty,
3370 TreePatternNode *SuperRegNode,
3371 TreePatternNode *SubRegIdxNode);
3372 Optional<CodeGenSubRegIndex *>
3373 inferSubRegIndexForNode(TreePatternNode *SubRegIdxNode);
3375 /// Infer a CodeGenRegisterClass which suppoorts \p Ty and \p SubRegIdxNode.
3376 /// Return None if no such class exists.
3377 Optional<const CodeGenRegisterClass *>
3378 inferSuperRegisterClass(const TypeSetByHwMode &Ty,
3379 TreePatternNode *SubRegIdxNode);
3381 /// Return the CodeGenRegisterClass associated with \p Leaf if it has one.
3382 Optional<const CodeGenRegisterClass *>
3383 getRegClassFromLeaf(TreePatternNode *Leaf);
3385 /// Return a CodeGenRegisterClass for \p N if one can be found. Return None
3387 Optional<const CodeGenRegisterClass *>
3388 inferRegClassFromPattern(TreePatternNode *N);
3391 /// Takes a sequence of \p Rules and group them based on the predicates
3392 /// they share. \p MatcherStorage is used as a memory container
3393 /// for the group that are created as part of this process.
3395 /// What this optimization does looks like if GroupT = GroupMatcher:
3396 /// Output without optimization:
3403 /// # predicate A // <-- effectively this is going to be checked twice.
3404 /// // Once in R1 and once in R2.
3407 /// Output with optimization:
3410 /// # predicate A // <-- Check is now shared.
3416 template <class GroupT>
3417 static std::vector<Matcher *> optimizeRules(
3418 ArrayRef<Matcher *> Rules,
3419 std::vector<std::unique_ptr<Matcher>> &MatcherStorage);
3422 void GlobalISelEmitter::gatherOpcodeValues() {
3423 InstructionOpcodeMatcher::initOpcodeValuesMap(Target);
3426 void GlobalISelEmitter::gatherTypeIDValues() {
3427 LLTOperandMatcher::initTypeIDValuesMap();
3430 void GlobalISelEmitter::gatherNodeEquivs() {
3431 assert(NodeEquivs.empty());
3432 for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
3433 NodeEquivs[Equiv->getValueAsDef("Node")] = Equiv;
3435 assert(ComplexPatternEquivs.empty());
3436 for (Record *Equiv : RK.getAllDerivedDefinitions("GIComplexPatternEquiv")) {
3437 Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
3440 ComplexPatternEquivs[SelDAGEquiv] = Equiv;
3443 assert(SDNodeXFormEquivs.empty());
3444 for (Record *Equiv : RK.getAllDerivedDefinitions("GISDNodeXFormEquiv")) {
3445 Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
3448 SDNodeXFormEquivs[SelDAGEquiv] = Equiv;
3452 Record *GlobalISelEmitter::findNodeEquiv(Record *N) const {
3453 return NodeEquivs.lookup(N);
3456 const CodeGenInstruction *
3457 GlobalISelEmitter::getEquivNode(Record &Equiv, const TreePatternNode *N) const {
3458 if (N->getNumChildren() >= 1) {
3459 // setcc operation maps to two different G_* instructions based on the type.
3460 if (!Equiv.isValueUnset("IfFloatingPoint") &&
3461 MVT(N->getChild(0)->getSimpleType(0)).isFloatingPoint())
3462 return &Target.getInstruction(Equiv.getValueAsDef("IfFloatingPoint"));
3465 for (const TreePredicateCall &Call : N->getPredicateCalls()) {
3466 const TreePredicateFn &Predicate = Call.Fn;
3467 if (!Equiv.isValueUnset("IfSignExtend") && Predicate.isLoad() &&
3468 Predicate.isSignExtLoad())
3469 return &Target.getInstruction(Equiv.getValueAsDef("IfSignExtend"));
3470 if (!Equiv.isValueUnset("IfZeroExtend") && Predicate.isLoad() &&
3471 Predicate.isZeroExtLoad())
3472 return &Target.getInstruction(Equiv.getValueAsDef("IfZeroExtend"));
3475 return &Target.getInstruction(Equiv.getValueAsDef("I"));
3478 GlobalISelEmitter::GlobalISelEmitter(RecordKeeper &RK)
3479 : RK(RK), CGP(RK), Target(CGP.getTargetInfo()),
3480 CGRegs(RK, Target.getHwModes()) {}
3482 //===- Emitter ------------------------------------------------------------===//
3485 GlobalISelEmitter::importRulePredicates(RuleMatcher &M,
3486 ArrayRef<Predicate> Predicates) {
3487 for (const Predicate &P : Predicates) {
3488 if (!P.Def || P.getCondString().empty())
3490 declareSubtargetFeature(P.Def);
3491 M.addRequiredFeature(P.Def);
3494 return Error::success();
3497 Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher(
3498 RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
3499 const TreePatternNode *Src, unsigned &TempOpIdx) {
3500 Record *SrcGIEquivOrNull = nullptr;
3501 const CodeGenInstruction *SrcGIOrNull = nullptr;
3503 // Start with the defined operands (i.e., the results of the root operator).
3504 if (Src->getExtTypes().size() > 1)
3505 return failedImport("Src pattern has multiple results");
3507 if (Src->isLeaf()) {
3508 Init *SrcInit = Src->getLeafValue();
3509 if (isa<IntInit>(SrcInit)) {
3510 InsnMatcher.addPredicate<InstructionOpcodeMatcher>(
3511 &Target.getInstruction(RK.getDef("G_CONSTANT")));
3513 return failedImport(
3514 "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
3516 SrcGIEquivOrNull = findNodeEquiv(Src->getOperator());
3517 if (!SrcGIEquivOrNull)
3518 return failedImport("Pattern operator lacks an equivalent Instruction" +
3519 explainOperator(Src->getOperator()));
3520 SrcGIOrNull = getEquivNode(*SrcGIEquivOrNull, Src);
3522 // The operators look good: match the opcode
3523 InsnMatcher.addPredicate<InstructionOpcodeMatcher>(SrcGIOrNull);
3527 for (const TypeSetByHwMode &VTy : Src->getExtTypes()) {
3528 // Results don't have a name unless they are the root node. The caller will
3529 // set the name if appropriate.
3530 OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
3531 if (auto Error = OM.addTypeCheckPredicate(VTy, false /* OperandIsAPointer */))
3532 return failedImport(toString(std::move(Error)) +
3533 " for result of Src pattern operator");
3536 for (const TreePredicateCall &Call : Src->getPredicateCalls()) {
3537 const TreePredicateFn &Predicate = Call.Fn;
3538 if (Predicate.isAlwaysTrue())
3541 if (Predicate.isImmediatePattern()) {
3542 InsnMatcher.addPredicate<InstructionImmPredicateMatcher>(Predicate);
3546 // An address space check is needed in all contexts if there is one.
3547 if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
3548 if (const ListInit *AddrSpaces = Predicate.getAddressSpaces()) {
3549 SmallVector<unsigned, 4> ParsedAddrSpaces;
3551 for (Init *Val : AddrSpaces->getValues()) {
3552 IntInit *IntVal = dyn_cast<IntInit>(Val);
3554 return failedImport("Address space is not an integer");
3555 ParsedAddrSpaces.push_back(IntVal->getValue());
3558 if (!ParsedAddrSpaces.empty()) {
3559 InsnMatcher.addPredicate<MemoryAddressSpacePredicateMatcher>(
3560 0, ParsedAddrSpaces);
3564 int64_t MinAlign = Predicate.getMinAlignment();
3566 InsnMatcher.addPredicate<MemoryAlignmentPredicateMatcher>(0, MinAlign);
3569 // G_LOAD is used for both non-extending and any-extending loads.
3570 if (Predicate.isLoad() && Predicate.isNonExtLoad()) {
3571 InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3572 0, MemoryVsLLTSizePredicateMatcher::EqualTo, 0);
3575 if (Predicate.isLoad() && Predicate.isAnyExtLoad()) {
3576 InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3577 0, MemoryVsLLTSizePredicateMatcher::LessThan, 0);
3581 if (Predicate.isStore()) {
3582 if (Predicate.isTruncStore()) {
3583 // FIXME: If MemoryVT is set, we end up with 2 checks for the MMO size.
3584 InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3585 0, MemoryVsLLTSizePredicateMatcher::LessThan, 0);
3588 if (Predicate.isNonTruncStore()) {
3589 // We need to check the sizes match here otherwise we could incorrectly
3590 // match truncating stores with non-truncating ones.
3591 InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3592 0, MemoryVsLLTSizePredicateMatcher::EqualTo, 0);
3596 // No check required. We already did it by swapping the opcode.
3597 if (!SrcGIEquivOrNull->isValueUnset("IfSignExtend") &&
3598 Predicate.isSignExtLoad())
3601 // No check required. We already did it by swapping the opcode.
3602 if (!SrcGIEquivOrNull->isValueUnset("IfZeroExtend") &&
3603 Predicate.isZeroExtLoad())
3606 // No check required. G_STORE by itself is a non-extending store.
3607 if (Predicate.isNonTruncStore())
3610 if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
3611 if (Predicate.getMemoryVT() != nullptr) {
3612 Optional<LLTCodeGen> MemTyOrNone =
3613 MVTToLLT(getValueType(Predicate.getMemoryVT()));
3616 return failedImport("MemVT could not be converted to LLT");
3618 // MMO's work in bytes so we must take care of unusual types like i1
3619 // don't round down.
3620 unsigned MemSizeInBits =
3621 llvm::alignTo(MemTyOrNone->get().getSizeInBits(), 8);
3623 InsnMatcher.addPredicate<MemorySizePredicateMatcher>(
3624 0, MemSizeInBits / 8);
3629 if (Predicate.isLoad() || Predicate.isStore()) {
3630 // No check required. A G_LOAD/G_STORE is an unindexed load.
3631 if (Predicate.isUnindexed())
3635 if (Predicate.isAtomic()) {
3636 if (Predicate.isAtomicOrderingMonotonic()) {
3637 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3641 if (Predicate.isAtomicOrderingAcquire()) {
3642 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Acquire");
3645 if (Predicate.isAtomicOrderingRelease()) {
3646 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Release");
3649 if (Predicate.isAtomicOrderingAcquireRelease()) {
3650 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3654 if (Predicate.isAtomicOrderingSequentiallyConsistent()) {
3655 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3656 "SequentiallyConsistent");
3660 if (Predicate.isAtomicOrderingAcquireOrStronger()) {
3661 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3662 "Acquire", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
3665 if (Predicate.isAtomicOrderingWeakerThanAcquire()) {
3666 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3667 "Acquire", AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
3671 if (Predicate.isAtomicOrderingReleaseOrStronger()) {
3672 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3673 "Release", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
3676 if (Predicate.isAtomicOrderingWeakerThanRelease()) {
3677 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3678 "Release", AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
3683 if (Predicate.hasGISelPredicateCode()) {
3684 InsnMatcher.addPredicate<GenericInstructionPredicateMatcher>(Predicate);
3688 return failedImport("Src pattern child has predicate (" +
3689 explainPredicates(Src) + ")");
3691 if (SrcGIEquivOrNull && SrcGIEquivOrNull->getValueAsBit("CheckMMOIsNonAtomic"))
3692 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("NotAtomic");
3693 else if (SrcGIEquivOrNull && SrcGIEquivOrNull->getValueAsBit("CheckMMOIsAtomic")) {
3694 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3695 "Unordered", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
3698 if (Src->isLeaf()) {
3699 Init *SrcInit = Src->getLeafValue();
3700 if (IntInit *SrcIntInit = dyn_cast<IntInit>(SrcInit)) {
3701 OperandMatcher &OM =
3702 InsnMatcher.addOperand(OpIdx++, Src->getName(), TempOpIdx);
3703 OM.addPredicate<LiteralIntOperandMatcher>(SrcIntInit->getValue());
3705 return failedImport(
3706 "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
3708 assert(SrcGIOrNull &&
3709 "Expected to have already found an equivalent Instruction");
3710 if (SrcGIOrNull->TheDef->getName() == "G_CONSTANT" ||
3711 SrcGIOrNull->TheDef->getName() == "G_FCONSTANT") {
3712 // imm/fpimm still have operands but we don't need to do anything with it
3713 // here since we don't support ImmLeaf predicates yet. However, we still
3714 // need to note the hidden operand to get GIM_CheckNumOperands correct.
3715 InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
3719 // Special case because the operand order is changed from setcc. The
3720 // predicate operand needs to be swapped from the last operand to the first
3723 unsigned NumChildren = Src->getNumChildren();
3724 bool IsFCmp = SrcGIOrNull->TheDef->getName() == "G_FCMP";
3726 if (IsFCmp || SrcGIOrNull->TheDef->getName() == "G_ICMP") {
3727 TreePatternNode *SrcChild = Src->getChild(NumChildren - 1);
3728 if (SrcChild->isLeaf()) {
3729 DefInit *DI = dyn_cast<DefInit>(SrcChild->getLeafValue());
3730 Record *CCDef = DI ? DI->getDef() : nullptr;
3731 if (!CCDef || !CCDef->isSubClassOf("CondCode"))
3732 return failedImport("Unable to handle CondCode");
3734 OperandMatcher &OM =
3735 InsnMatcher.addOperand(OpIdx++, SrcChild->getName(), TempOpIdx);
3736 StringRef PredType = IsFCmp ? CCDef->getValueAsString("FCmpPredicate") :
3737 CCDef->getValueAsString("ICmpPredicate");
3739 if (!PredType.empty()) {
3740 OM.addPredicate<CmpPredicateOperandMatcher>(PredType);
3741 // Process the other 2 operands normally.
3747 // Match the used operands (i.e. the children of the operator).
3749 SrcGIOrNull->TheDef->getName() == "G_INTRINSIC" ||
3750 SrcGIOrNull->TheDef->getName() == "G_INTRINSIC_W_SIDE_EFFECTS";
3751 const CodeGenIntrinsic *II = Src->getIntrinsicInfo(CGP);
3752 if (IsIntrinsic && !II)
3753 return failedImport("Expected IntInit containing intrinsic ID)");
3755 for (unsigned i = 0; i != NumChildren; ++i) {
3756 TreePatternNode *SrcChild = Src->getChild(i);
3758 // We need to determine the meaning of a literal integer based on the
3759 // context. If this is a field required to be an immediate (such as an
3760 // immarg intrinsic argument), the required predicates are different than
3761 // a constant which may be materialized in a register. If we have an
3762 // argument that is required to be an immediate, we should not emit an LLT
3763 // type check, and should not be looking for a G_CONSTANT defined
3765 bool OperandIsImmArg = SrcGIOrNull->isOperandImmArg(i);
3767 // SelectionDAG allows pointers to be represented with iN since it doesn't
3768 // distinguish between pointers and integers but they are different types in GlobalISel.
3769 // Coerce integers to pointers to address space 0 if the context indicates a pointer.
3771 bool OperandIsAPointer = SrcGIOrNull->isOperandAPointer(i);
3774 // For G_INTRINSIC/G_INTRINSIC_W_SIDE_EFFECTS, the operand immediately
3775 // following the defs is an intrinsic ID.
3777 OperandMatcher &OM =
3778 InsnMatcher.addOperand(OpIdx++, SrcChild->getName(), TempOpIdx);
3779 OM.addPredicate<IntrinsicIDOperandMatcher>(II);
3783 // We have to check intrinsics for llvm_anyptr_ty and immarg parameters.
3785 // Note that we have to look at the i-1th parameter, because we don't
3786 // have the intrinsic ID in the intrinsic's parameter list.
3787 OperandIsAPointer |= II->isParamAPointer(i - 1);
3788 OperandIsImmArg |= II->isParamImmArg(i - 1);
3792 importChildMatcher(Rule, InsnMatcher, SrcChild, OperandIsAPointer,
3793 OperandIsImmArg, OpIdx++, TempOpIdx))
3794 return std::move(Error);
3801 Error GlobalISelEmitter::importComplexPatternOperandMatcher(
3802 OperandMatcher &OM, Record *R, unsigned &TempOpIdx) const {
3803 const auto &ComplexPattern = ComplexPatternEquivs.find(R);
3804 if (ComplexPattern == ComplexPatternEquivs.end())
3805 return failedImport("SelectionDAG ComplexPattern (" + R->getName() +
3806 ") not mapped to GlobalISel");
3808 OM.addPredicate<ComplexPatternOperandMatcher>(OM, *ComplexPattern->second);
3810 return Error::success();
3813 // Get the name to use for a pattern operand. For an anonymous physical register
3814 // input, this should use the register name.
3815 static StringRef getSrcChildName(const TreePatternNode *SrcChild,
3817 StringRef SrcChildName = SrcChild->getName();
3818 if (SrcChildName.empty() && SrcChild->isLeaf()) {
3819 if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
3820 auto *ChildRec = ChildDefInit->getDef();
3821 if (ChildRec->isSubClassOf("Register")) {
3822 SrcChildName = ChildRec->getName();
3828 return SrcChildName;
3831 Error GlobalISelEmitter::importChildMatcher(
3832 RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
3833 const TreePatternNode *SrcChild, bool OperandIsAPointer,
3834 bool OperandIsImmArg, unsigned OpIdx, unsigned &TempOpIdx) {
3836 Record *PhysReg = nullptr;
3837 StringRef SrcChildName = getSrcChildName(SrcChild, PhysReg);
3839 OperandMatcher &OM = PhysReg ?
3840 InsnMatcher.addPhysRegInput(PhysReg, OpIdx, TempOpIdx) :
3841 InsnMatcher.addOperand(OpIdx, SrcChildName, TempOpIdx);
3842 if (OM.isSameAsAnotherOperand())
3843 return Error::success();
3845 ArrayRef<TypeSetByHwMode> ChildTypes = SrcChild->getExtTypes();
3846 if (ChildTypes.size() != 1)
3847 return failedImport("Src pattern child has multiple results");
3849 // Check MBB's before the type check since they are not a known type.
3850 if (!SrcChild->isLeaf()) {
3851 if (SrcChild->getOperator()->isSubClassOf("SDNode")) {
3852 auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator());
3853 if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
3854 OM.addPredicate<MBBOperandMatcher>();
3855 return Error::success();
3857 if (SrcChild->getOperator()->getName() == "timm") {
3858 OM.addPredicate<ImmOperandMatcher>();
3859 return Error::success();
3864 // Immediate arguments have no meaningful type to check as they don't have
3866 if (!OperandIsImmArg) {
3868 OM.addTypeCheckPredicate(ChildTypes.front(), OperandIsAPointer))
3869 return failedImport(toString(std::move(Error)) + " for Src operand (" +
3870 to_string(*SrcChild) + ")");
3873 // Check for nested instructions.
3874 if (!SrcChild->isLeaf()) {
3875 if (SrcChild->getOperator()->isSubClassOf("ComplexPattern")) {
3876 // When a ComplexPattern is used as an operator, it should do the same
3877 // thing as when used as a leaf. However, the children of the operator
3878 // name the sub-operands that make up the complex operand and we must
3879 // prepare to reference them in the renderer too.
3880 unsigned RendererID = TempOpIdx;
3881 if (auto Error = importComplexPatternOperandMatcher(
3882 OM, SrcChild->getOperator(), TempOpIdx))
3885 for (unsigned i = 0, e = SrcChild->getNumChildren(); i != e; ++i) {
3886 auto *SubOperand = SrcChild->getChild(i);
3887 if (!SubOperand->getName().empty()) {
3888 if (auto Error = Rule.defineComplexSubOperand(SubOperand->getName(),
3889 SrcChild->getOperator(),
3895 return Error::success();
3898 auto MaybeInsnOperand = OM.addPredicate<InstructionOperandMatcher>(
3899 InsnMatcher.getRuleMatcher(), SrcChild->getName());
3900 if (!MaybeInsnOperand.hasValue()) {
3901 // This isn't strictly true. If the user were to provide exactly the same
3902 // matchers as the original operand then we could allow it. However, it's
3903 // simpler to not permit the redundant specification.
3904 return failedImport("Nested instruction cannot be the same as another operand");
3907 // Map the node to a gMIR instruction.
3908 InstructionOperandMatcher &InsnOperand = **MaybeInsnOperand;
3909 auto InsnMatcherOrError = createAndImportSelDAGMatcher(
3910 Rule, InsnOperand.getInsnMatcher(), SrcChild, TempOpIdx);
3911 if (auto Error = InsnMatcherOrError.takeError())
3914 return Error::success();
3917 if (SrcChild->hasAnyPredicate())
3918 return failedImport("Src pattern child has unsupported predicate");
3920 // Check for constant immediates.
3921 if (auto *ChildInt = dyn_cast<IntInit>(SrcChild->getLeafValue())) {
3922 if (OperandIsImmArg) {
3923 // Checks for argument directly in operand list
3924 OM.addPredicate<LiteralIntOperandMatcher>(ChildInt->getValue());
3926 // Checks for materialized constant
3927 OM.addPredicate<ConstantIntOperandMatcher>(ChildInt->getValue());
3929 return Error::success();
3932 // Check for def's like register classes or ComplexPattern's.
3933 if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
3934 auto *ChildRec = ChildDefInit->getDef();
3936 // Check for register classes.
3937 if (ChildRec->isSubClassOf("RegisterClass") ||
3938 ChildRec->isSubClassOf("RegisterOperand")) {
3939 OM.addPredicate<RegisterBankOperandMatcher>(
3940 Target.getRegisterClass(getInitValueAsRegClass(ChildDefInit)));
3941 return Error::success();
3944 if (ChildRec->isSubClassOf("Register")) {
3945 // This just be emitted as a copy to the specific register.
3946 ValueTypeByHwMode VT = ChildTypes.front().getValueTypeByHwMode();
3947 const CodeGenRegisterClass *RC
3948 = CGRegs.getMinimalPhysRegClass(ChildRec, &VT);
3950 return failedImport(
3951 "Could not determine physical register class of pattern source");
3954 OM.addPredicate<RegisterBankOperandMatcher>(*RC);
3955 return Error::success();
3958 // Check for ValueType.
3959 if (ChildRec->isSubClassOf("ValueType")) {
3960 // We already added a type check as standard practice so this doesn't need
3962 return Error::success();
3965 // Check for ComplexPattern's.
3966 if (ChildRec->isSubClassOf("ComplexPattern"))
3967 return importComplexPatternOperandMatcher(OM, ChildRec, TempOpIdx);
3969 if (ChildRec->isSubClassOf("ImmLeaf")) {
3970 return failedImport(
3971 "Src pattern child def is an unsupported tablegen class (ImmLeaf)");
3974 return failedImport(
3975 "Src pattern child def is an unsupported tablegen class");
3978 return failedImport("Src pattern child is an unsupported kind");
3981 Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderer(
3982 action_iterator InsertPt, RuleMatcher &Rule, BuildMIAction &DstMIBuilder,
3983 TreePatternNode *DstChild) {
3985 const auto &SubOperand = Rule.getComplexSubOperand(DstChild->getName());
3986 if (SubOperand.hasValue()) {
3987 DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
3988 *std::get<0>(*SubOperand), DstChild->getName(),
3989 std::get<1>(*SubOperand), std::get<2>(*SubOperand));
3993 if (!DstChild->isLeaf()) {
3994 if (DstChild->getOperator()->isSubClassOf("SDNodeXForm")) {
3995 auto Child = DstChild->getChild(0);
3996 auto I = SDNodeXFormEquivs.find(DstChild->getOperator());
3997 if (I != SDNodeXFormEquivs.end()) {
3998 Record *XFormOpc = DstChild->getOperator()->getValueAsDef("Opcode");
3999 if (XFormOpc->getName() == "timm") {
4000 // If this is a TargetConstant, there won't be a corresponding
4001 // instruction to transform. Instead, this will refer directly to an
4002 // operand in an instruction's operand list.
4003 DstMIBuilder.addRenderer<CustomOperandRenderer>(*I->second,
4006 DstMIBuilder.addRenderer<CustomRenderer>(*I->second,
4012 return failedImport("SDNodeXForm " + Child->getName() +
4013 " has no custom renderer");
4016 // We accept 'bb' here. It's an operator because BasicBlockSDNode isn't
4017 // inline, but in MI it's just another operand.
4018 if (DstChild->getOperator()->isSubClassOf("SDNode")) {
4019 auto &ChildSDNI = CGP.getSDNodeInfo(DstChild->getOperator());
4020 if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
4021 DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
4026 // Similarly, imm is an operator in TreePatternNode's view but must be
4027 // rendered as operands.
4028 // FIXME: The target should be able to choose sign-extended when appropriate
4030 if (DstChild->getOperator()->getName() == "timm") {
4031 DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
4033 } else if (DstChild->getOperator()->getName() == "imm") {
4034 DstMIBuilder.addRenderer<CopyConstantAsImmRenderer>(DstChild->getName());
4036 } else if (DstChild->getOperator()->getName() == "fpimm") {
4037 DstMIBuilder.addRenderer<CopyFConstantAsFPImmRenderer>(
4038 DstChild->getName());
4042 if (DstChild->getOperator()->isSubClassOf("Instruction")) {
4043 ArrayRef<TypeSetByHwMode> ChildTypes = DstChild->getExtTypes();
4044 if (ChildTypes.size() != 1)
4045 return failedImport("Dst pattern child has multiple results");
4047 Optional<LLTCodeGen> OpTyOrNone = None;
4048 if (ChildTypes.front().isMachineValueType())
4050 MVTToLLT(ChildTypes.front().getMachineValueType().SimpleTy);
4052 return failedImport("Dst operand has an unsupported type");
4054 unsigned TempRegID = Rule.allocateTempRegID();
4055 InsertPt = Rule.insertAction<MakeTempRegisterAction>(
4056 InsertPt, OpTyOrNone.getValue(), TempRegID);
4057 DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
4059 auto InsertPtOrError = createAndImportSubInstructionRenderer(
4060 ++InsertPt, Rule, DstChild, TempRegID);
4061 if (auto Error = InsertPtOrError.takeError())
4062 return std::move(Error);
4063 return InsertPtOrError.get();
4066 return failedImport("Dst pattern child isn't a leaf node or an MBB" + llvm::to_string(*DstChild));
4069 // It could be a specific immediate in which case we should just check for
4071 if (const IntInit *ChildIntInit =
4072 dyn_cast<IntInit>(DstChild->getLeafValue())) {
4073 DstMIBuilder.addRenderer<ImmRenderer>(ChildIntInit->getValue());
4077 // Otherwise, we're looking for a bog-standard RegisterClass operand.
4078 if (auto *ChildDefInit = dyn_cast<DefInit>(DstChild->getLeafValue())) {
4079 auto *ChildRec = ChildDefInit->getDef();
4081 ArrayRef<TypeSetByHwMode> ChildTypes = DstChild->getExtTypes();
4082 if (ChildTypes.size() != 1)
4083 return failedImport("Dst pattern child has multiple results");
4085 Optional<LLTCodeGen> OpTyOrNone = None;
4086 if (ChildTypes.front().isMachineValueType())
4087 OpTyOrNone = MVTToLLT(ChildTypes.front().getMachineValueType().SimpleTy);
4089 return failedImport("Dst operand has an unsupported type");
4091 if (ChildRec->isSubClassOf("Register")) {
4092 DstMIBuilder.addRenderer<AddRegisterRenderer>(ChildRec);
4096 if (ChildRec->isSubClassOf("RegisterClass") ||
4097 ChildRec->isSubClassOf("RegisterOperand") ||
4098 ChildRec->isSubClassOf("ValueType")) {
4099 if (ChildRec->isSubClassOf("RegisterOperand") &&
4100 !ChildRec->isValueUnset("GIZeroRegister")) {
4101 DstMIBuilder.addRenderer<CopyOrAddZeroRegRenderer>(
4102 DstChild->getName(), ChildRec->getValueAsDef("GIZeroRegister"));
4106 DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
4110 if (ChildRec->isSubClassOf("SubRegIndex")) {
4111 CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(ChildRec);
4112 DstMIBuilder.addRenderer<ImmRenderer>(SubIdx->EnumValue);
4116 if (ChildRec->isSubClassOf("ComplexPattern")) {
4117 const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
4118 if (ComplexPattern == ComplexPatternEquivs.end())
4119 return failedImport(
4120 "SelectionDAG ComplexPattern not mapped to GlobalISel");
4122 const OperandMatcher &OM = Rule.getOperandMatcher(DstChild->getName());
4123 DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
4124 *ComplexPattern->second, DstChild->getName(),
4125 OM.getAllocatedTemporariesBaseID());
4129 return failedImport(
4130 "Dst pattern child def is an unsupported tablegen class");
4133 return failedImport("Dst pattern child is an unsupported kind");
4136 Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
4137 RuleMatcher &M, InstructionMatcher &InsnMatcher, const TreePatternNode *Src,
4138 const TreePatternNode *Dst) {
4139 auto InsertPtOrError = createInstructionRenderer(M.actions_end(), M, Dst);
4140 if (auto Error = InsertPtOrError.takeError())
4141 return std::move(Error);
4143 action_iterator InsertPt = InsertPtOrError.get();
4144 BuildMIAction &DstMIBuilder = *static_cast<BuildMIAction *>(InsertPt->get());
4146 for (auto PhysInput : InsnMatcher.getPhysRegInputs()) {
4147 InsertPt = M.insertAction<BuildMIAction>(
4148 InsertPt, M.allocateOutputInsnID(),
4149 &Target.getInstruction(RK.getDef("COPY")));
4150 BuildMIAction &CopyToPhysRegMIBuilder =
4151 *static_cast<BuildMIAction *>(InsertPt->get());
4152 CopyToPhysRegMIBuilder.addRenderer<AddRegisterRenderer>(PhysInput.first,
4154 CopyToPhysRegMIBuilder.addRenderer<CopyPhysRegRenderer>(PhysInput.first);
4157 importExplicitDefRenderers(DstMIBuilder);
4159 if (auto Error = importExplicitUseRenderers(InsertPt, M, DstMIBuilder, Dst)
4161 return std::move(Error);
4163 return DstMIBuilder;
4166 Expected<action_iterator>
4167 GlobalISelEmitter::createAndImportSubInstructionRenderer(
4168 const action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst,
4169 unsigned TempRegID) {
4170 auto InsertPtOrError = createInstructionRenderer(InsertPt, M, Dst);
4172 // TODO: Assert there's exactly one result.
4174 if (auto Error = InsertPtOrError.takeError())
4175 return std::move(Error);
4177 BuildMIAction &DstMIBuilder =
4178 *static_cast<BuildMIAction *>(InsertPtOrError.get()->get());
4180 // Assign the result to TempReg.
4181 DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID, true);
4184 importExplicitUseRenderers(InsertPtOrError.get(), M, DstMIBuilder, Dst);
4185 if (auto Error = InsertPtOrError.takeError())
4186 return std::move(Error);
4188 // We need to make sure that when we import an INSERT_SUBREG as a
4189 // subinstruction that it ends up being constrained to the correct super
4190 // register and subregister classes.
4191 auto OpName = Target.getInstruction(Dst->getOperator()).TheDef->getName();
4192 if (OpName == "INSERT_SUBREG") {
4193 auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
4195 return failedImport(
4196 "Cannot infer register class from INSERT_SUBREG operand #1");
4197 Optional<const CodeGenRegisterClass *> SuperClass =
4198 inferSuperRegisterClassForNode(Dst->getExtType(0), Dst->getChild(0),
4201 return failedImport(
4202 "Cannot infer register class for INSERT_SUBREG operand #0");
4203 // The destination and the super register source of an INSERT_SUBREG must
4204 // be the same register class.
4205 M.insertAction<ConstrainOperandToRegClassAction>(
4206 InsertPt, DstMIBuilder.getInsnID(), 0, **SuperClass);
4207 M.insertAction<ConstrainOperandToRegClassAction>(
4208 InsertPt, DstMIBuilder.getInsnID(), 1, **SuperClass);
4209 M.insertAction<ConstrainOperandToRegClassAction>(
4210 InsertPt, DstMIBuilder.getInsnID(), 2, **SubClass);
4211 return InsertPtOrError.get();
4214 if (OpName == "EXTRACT_SUBREG") {
4215 // EXTRACT_SUBREG selects into a subregister COPY but unlike most
4216 // instructions, the result register class is controlled by the
4217 // subregisters of the operand. As a result, we must constrain the result
4218 // class rather than check that it's already the right one.
4219 auto SuperClass = inferRegClassFromPattern(Dst->getChild(0));
4221 return failedImport(
4222 "Cannot infer register class from EXTRACT_SUBREG operand #0");
4224 auto SubIdx = inferSubRegIndexForNode(Dst->getChild(1));
4226 return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
4228 const auto &SrcRCDstRCPair =
4229 (*SuperClass)->getMatchingSubClassWithSubRegs(CGRegs, *SubIdx);
4230 assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
4231 M.insertAction<ConstrainOperandToRegClassAction>(
4232 InsertPt, DstMIBuilder.getInsnID(), 0, *SrcRCDstRCPair->second);
4233 M.insertAction<ConstrainOperandToRegClassAction>(
4234 InsertPt, DstMIBuilder.getInsnID(), 1, *SrcRCDstRCPair->first);
4236 // We're done with this pattern! It's eligible for GISel emission; return
4238 return InsertPtOrError.get();
4241 // Similar to INSERT_SUBREG, we also have to handle SUBREG_TO_REG as a
4243 if (OpName == "SUBREG_TO_REG") {
4244 auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
4246 return failedImport(
4247 "Cannot infer register class from SUBREG_TO_REG child #1");
4248 auto SuperClass = inferSuperRegisterClass(Dst->getExtType(0),
4251 return failedImport(
4252 "Cannot infer register class for SUBREG_TO_REG operand #0");
4253 M.insertAction<ConstrainOperandToRegClassAction>(
4254 InsertPt, DstMIBuilder.getInsnID(), 0, **SuperClass);
4255 M.insertAction<ConstrainOperandToRegClassAction>(
4256 InsertPt, DstMIBuilder.getInsnID(), 2, **SubClass);
4257 return InsertPtOrError.get();
4260 M.insertAction<ConstrainOperandsToDefinitionAction>(InsertPt,
4261 DstMIBuilder.getInsnID());
4262 return InsertPtOrError.get();
4265 Expected<action_iterator> GlobalISelEmitter::createInstructionRenderer(
4266 action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst) {
4267 Record *DstOp = Dst->getOperator();
4268 if (!DstOp->isSubClassOf("Instruction")) {
4269 if (DstOp->isSubClassOf("ValueType"))
4270 return failedImport(
4271 "Pattern operator isn't an instruction (it's a ValueType)");
4272 return failedImport("Pattern operator isn't an instruction");
4274 CodeGenInstruction *DstI = &Target.getInstruction(DstOp);
4276 // COPY_TO_REGCLASS is just a copy with a ConstrainOperandToRegClassAction
4277 // attached. Similarly for EXTRACT_SUBREG except that's a subregister copy.
4278 StringRef Name = DstI->TheDef->getName();
4279 if (Name == "COPY_TO_REGCLASS" || Name == "EXTRACT_SUBREG")
4280 DstI = &Target.getInstruction(RK.getDef("COPY"));
4282 return M.insertAction<BuildMIAction>(InsertPt, M.allocateOutputInsnID(),
4286 void GlobalISelEmitter::importExplicitDefRenderers(
4287 BuildMIAction &DstMIBuilder) {
4288 const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
4289 for (unsigned I = 0; I < DstI->Operands.NumDefs; ++I) {
4290 const CGIOperandList::OperandInfo &DstIOperand = DstI->Operands[I];
4291 DstMIBuilder.addRenderer<CopyRenderer>(DstIOperand.Name);
4295 Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderers(
4296 action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
4297 const llvm::TreePatternNode *Dst) {
4298 const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
4299 CodeGenInstruction *OrigDstI = &Target.getInstruction(Dst->getOperator());
4301 StringRef Name = OrigDstI->TheDef->getName();
4302 unsigned ExpectedDstINumUses = Dst->getNumChildren();
4304 // EXTRACT_SUBREG needs to use a subregister COPY.
4305 if (Name == "EXTRACT_SUBREG") {
4306 if (!Dst->getChild(0)->isLeaf())
4307 return failedImport("EXTRACT_SUBREG child #1 is not a leaf");
4309 if (DefInit *SubRegInit =
4310 dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue())) {
4311 Record *RCDef = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
4313 return failedImport("EXTRACT_SUBREG child #0 could not "
4314 "be coerced to a register class");
4316 CodeGenRegisterClass *RC = CGRegs.getRegClass(RCDef);
4317 CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
4319 const auto &SrcRCDstRCPair =
4320 RC->getMatchingSubClassWithSubRegs(CGRegs, SubIdx);
4321 if (SrcRCDstRCPair.hasValue()) {
4322 assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
4323 if (SrcRCDstRCPair->first != RC)
4324 return failedImport("EXTRACT_SUBREG requires an additional COPY");
4327 DstMIBuilder.addRenderer<CopySubRegRenderer>(Dst->getChild(0)->getName(),
4332 return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
4335 if (Name == "REG_SEQUENCE") {
4336 if (!Dst->getChild(0)->isLeaf())
4337 return failedImport("REG_SEQUENCE child #0 is not a leaf");
4339 Record *RCDef = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
4341 return failedImport("REG_SEQUENCE child #0 could not "
4342 "be coerced to a register class");
4344 if ((ExpectedDstINumUses - 1) % 2 != 0)
4345 return failedImport("Malformed REG_SEQUENCE");
4347 for (unsigned I = 1; I != ExpectedDstINumUses; I += 2) {
4348 TreePatternNode *ValChild = Dst->getChild(I);
4349 TreePatternNode *SubRegChild = Dst->getChild(I + 1);
4351 if (DefInit *SubRegInit =
4352 dyn_cast<DefInit>(SubRegChild->getLeafValue())) {
4353 CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
4355 auto InsertPtOrError =
4356 importExplicitUseRenderer(InsertPt, M, DstMIBuilder, ValChild);
4357 if (auto Error = InsertPtOrError.takeError())
4358 return std::move(Error);
4359 InsertPt = InsertPtOrError.get();
4360 DstMIBuilder.addRenderer<SubRegIndexRenderer>(SubIdx);
4367 // Render the explicit uses.
4368 unsigned DstINumUses = OrigDstI->Operands.size() - OrigDstI->Operands.NumDefs;
4369 if (Name == "COPY_TO_REGCLASS") {
4370 DstINumUses--; // Ignore the class constraint.
4371 ExpectedDstINumUses--;
4374 // NumResults - This is the number of results produced by the instruction in
4376 unsigned NumResults = OrigDstI->Operands.NumDefs;
4378 // Number of operands we know the output instruction must have. If it is
4379 // variadic, we could have more operands.
4380 unsigned NumFixedOperands = DstI->Operands.size();
4382 // Loop over all of the fixed operands of the instruction pattern, emitting
4383 // code to fill them all in. The node 'N' usually has number children equal to
4384 // the number of input operands of the instruction. However, in cases where
4385 // there are predicate operands for an instruction, we need to fill in the
4386 // 'execute always' values. Match up the node operands to the instruction
4387 // operands to do this.
4390 // Similarly to the code in TreePatternNode::ApplyTypeConstraints, count the
4391 // number of operands at the end of the list which have default values.
4392 // Those can come from the pattern if it provides enough arguments, or be
4393 // filled in with the default if the pattern hasn't provided them. But any
4394 // operand with a default value _before_ the last mandatory one will be
4395 // filled in with their defaults unconditionally.
4396 unsigned NonOverridableOperands = NumFixedOperands;
4397 while (NonOverridableOperands > NumResults &&
4398 CGP.operandHasDefault(DstI->Operands[NonOverridableOperands - 1].Rec))
4399 --NonOverridableOperands;
4401 unsigned NumDefaultOps = 0;
4402 for (unsigned I = 0; I != DstINumUses; ++I) {
4403 unsigned InstOpNo = DstI->Operands.NumDefs + I;
4405 // Determine what to emit for this operand.
4406 Record *OperandNode = DstI->Operands[InstOpNo].Rec;
4408 // If the operand has default values, introduce them now.
4409 if (CGP.operandHasDefault(OperandNode) &&
4410 (InstOpNo < NonOverridableOperands || Child >= Dst->getNumChildren())) {
4411 // This is a predicate or optional def operand which the pattern has not
4412 // overridden, or which we aren't letting it override; emit the 'default
4415 const CGIOperandList::OperandInfo &DstIOperand = DstI->Operands[InstOpNo];
4416 DagInit *DefaultOps = DstIOperand.Rec->getValueAsDag("DefaultOps");
4417 if (auto Error = importDefaultOperandRenderers(
4418 InsertPt, M, DstMIBuilder, DefaultOps))
4419 return std::move(Error);
4424 auto InsertPtOrError = importExplicitUseRenderer(InsertPt, M, DstMIBuilder,
4425 Dst->getChild(Child));
4426 if (auto Error = InsertPtOrError.takeError())
4427 return std::move(Error);
4428 InsertPt = InsertPtOrError.get();
4432 if (NumDefaultOps + ExpectedDstINumUses != DstINumUses)
4433 return failedImport("Expected " + llvm::to_string(DstINumUses) +
4434 " used operands but found " +
4435 llvm::to_string(ExpectedDstINumUses) +
4436 " explicit ones and " + llvm::to_string(NumDefaultOps) +
4442 Error GlobalISelEmitter::importDefaultOperandRenderers(
4443 action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
4444 DagInit *DefaultOps) const {
4445 for (const auto *DefaultOp : DefaultOps->getArgs()) {
4446 Optional<LLTCodeGen> OpTyOrNone = None;
4448 // Look through ValueType operators.
4449 if (const DagInit *DefaultDagOp = dyn_cast<DagInit>(DefaultOp)) {
4450 if (const DefInit *DefaultDagOperator =
4451 dyn_cast<DefInit>(DefaultDagOp->getOperator())) {
4452 if (DefaultDagOperator->getDef()->isSubClassOf("ValueType")) {
4453 OpTyOrNone = MVTToLLT(getValueType(
4454 DefaultDagOperator->getDef()));
4455 DefaultOp = DefaultDagOp->getArg(0);
4460 if (const DefInit *DefaultDefOp = dyn_cast<DefInit>(DefaultOp)) {
4461 auto Def = DefaultDefOp->getDef();
4462 if (Def->getName() == "undef_tied_input") {
4463 unsigned TempRegID = M.allocateTempRegID();
4464 M.insertAction<MakeTempRegisterAction>(
4465 InsertPt, OpTyOrNone.getValue(), TempRegID);
4466 InsertPt = M.insertAction<BuildMIAction>(
4467 InsertPt, M.allocateOutputInsnID(),
4468 &Target.getInstruction(RK.getDef("IMPLICIT_DEF")));
4469 BuildMIAction &IDMIBuilder = *static_cast<BuildMIAction *>(
4471 IDMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
4472 DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
4474 DstMIBuilder.addRenderer<AddRegisterRenderer>(Def);
4479 if (const IntInit *DefaultIntOp = dyn_cast<IntInit>(DefaultOp)) {
4480 DstMIBuilder.addRenderer<ImmRenderer>(DefaultIntOp->getValue());
4484 return failedImport("Could not add default op");
4487 return Error::success();
4490 Error GlobalISelEmitter::importImplicitDefRenderers(
4491 BuildMIAction &DstMIBuilder,
4492 const std::vector<Record *> &ImplicitDefs) const {
4493 if (!ImplicitDefs.empty())
4494 return failedImport("Pattern defines a physical register");
4495 return Error::success();
4498 Optional<const CodeGenRegisterClass *>
4499 GlobalISelEmitter::getRegClassFromLeaf(TreePatternNode *Leaf) {
4500 assert(Leaf && "Expected node?");
4501 assert(Leaf->isLeaf() && "Expected leaf?");
4502 Record *RCRec = getInitValueAsRegClass(Leaf->getLeafValue());
4505 CodeGenRegisterClass *RC = CGRegs.getRegClass(RCRec);
4511 Optional<const CodeGenRegisterClass *>
4512 GlobalISelEmitter::inferRegClassFromPattern(TreePatternNode *N) {
4517 return getRegClassFromLeaf(N);
4519 // We don't have a leaf node, so we have to try and infer something. Check
4520 // that we have an instruction that we an infer something from.
4522 // Only handle things that produce a single type.
4523 if (N->getNumTypes() != 1)
4525 Record *OpRec = N->getOperator();
4527 // We only want instructions.
4528 if (!OpRec->isSubClassOf("Instruction"))
4531 // Don't want to try and infer things when there could potentially be more
4532 // than one candidate register class.
4533 auto &Inst = Target.getInstruction(OpRec);
4534 if (Inst.Operands.NumDefs > 1)
4537 // Handle any special-case instructions which we can safely infer register
4539 StringRef InstName = Inst.TheDef->getName();
4540 bool IsRegSequence = InstName == "REG_SEQUENCE";
4541 if (IsRegSequence || InstName == "COPY_TO_REGCLASS") {
4542 // If we have a COPY_TO_REGCLASS, then we need to handle it specially. It
4543 // has the desired register class as the first child.
4544 TreePatternNode *RCChild = N->getChild(IsRegSequence ? 0 : 1);
4545 if (!RCChild->isLeaf())
4547 return getRegClassFromLeaf(RCChild);
4550 // Handle destination record types that we can safely infer a register class
4552 const auto &DstIOperand = Inst.Operands[0];
4553 Record *DstIOpRec = DstIOperand.Rec;
4554 if (DstIOpRec->isSubClassOf("RegisterOperand")) {
4555 DstIOpRec = DstIOpRec->getValueAsDef("RegClass");
4556 const CodeGenRegisterClass &RC = Target.getRegisterClass(DstIOpRec);
4560 if (DstIOpRec->isSubClassOf("RegisterClass")) {
4561 const CodeGenRegisterClass &RC = Target.getRegisterClass(DstIOpRec);
4568 Optional<const CodeGenRegisterClass *>
4569 GlobalISelEmitter::inferSuperRegisterClass(const TypeSetByHwMode &Ty,
4570 TreePatternNode *SubRegIdxNode) {
4571 assert(SubRegIdxNode && "Expected subregister index node!");
4572 // We need a ValueTypeByHwMode for getSuperRegForSubReg.
4573 if (!Ty.isValueTypeByHwMode(false))
4575 if (!SubRegIdxNode->isLeaf())
4577 DefInit *SubRegInit = dyn_cast<DefInit>(SubRegIdxNode->getLeafValue());
4580 CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
4582 // Use the information we found above to find a minimal register class which
4583 // supports the subregister and type we want.
4585 Target.getSuperRegForSubReg(Ty.getValueTypeByHwMode(), CGRegs, SubIdx);
4591 Optional<const CodeGenRegisterClass *>
4592 GlobalISelEmitter::inferSuperRegisterClassForNode(
4593 const TypeSetByHwMode &Ty, TreePatternNode *SuperRegNode,
4594 TreePatternNode *SubRegIdxNode) {
4595 assert(SuperRegNode && "Expected super register node!");
4596 // Check if we already have a defined register class for the super register
4597 // node. If we do, then we should preserve that rather than inferring anything
4598 // from the subregister index node. We can assume that whoever wrote the
4599 // pattern in the first place made sure that the super register and
4600 // subregister are compatible.
4601 if (Optional<const CodeGenRegisterClass *> SuperRegisterClass =
4602 inferRegClassFromPattern(SuperRegNode))
4603 return *SuperRegisterClass;
4604 return inferSuperRegisterClass(Ty, SubRegIdxNode);
4607 Optional<CodeGenSubRegIndex *>
4608 GlobalISelEmitter::inferSubRegIndexForNode(TreePatternNode *SubRegIdxNode) {
4609 if (!SubRegIdxNode->isLeaf())
4612 DefInit *SubRegInit = dyn_cast<DefInit>(SubRegIdxNode->getLeafValue());
4615 return CGRegs.getSubRegIdx(SubRegInit->getDef());
4618 Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
4619 // Keep track of the matchers and actions to emit.
4620 int Score = P.getPatternComplexity(CGP);
4621 RuleMatcher M(P.getSrcRecord()->getLoc());
4622 RuleMatcherScores[M.getRuleID()] = Score;
4623 M.addAction<DebugCommentAction>(llvm::to_string(*P.getSrcPattern()) +
4625 llvm::to_string(*P.getDstPattern()));
4627 if (auto Error = importRulePredicates(M, P.getPredicates()))
4628 return std::move(Error);
4630 // Next, analyze the pattern operators.
4631 TreePatternNode *Src = P.getSrcPattern();
4632 TreePatternNode *Dst = P.getDstPattern();
4634 // If the root of either pattern isn't a simple operator, ignore it.
4635 if (auto Err = isTrivialOperatorNode(Dst))
4636 return failedImport("Dst pattern root isn't a trivial operator (" +
4637 toString(std::move(Err)) + ")");
4638 if (auto Err = isTrivialOperatorNode(Src))
4639 return failedImport("Src pattern root isn't a trivial operator (" +
4640 toString(std::move(Err)) + ")");
4642 // The different predicates and matchers created during
4643 // addInstructionMatcher use the RuleMatcher M to set up their
4644 // instruction ID (InsnVarID) that are going to be used when
4645 // M is going to be emitted.
4646 // However, the code doing the emission still relies on the IDs
4647 // returned during that process by the RuleMatcher when issuing
4648 // the recordInsn opcodes.
4650 // 1. The order in which we created the predicates
4651 // and such must be the same as the order in which we emit them,
4653 // 2. We need to reset the generation of the IDs in M somewhere between
4654 // addInstructionMatcher and emit
4656 // FIXME: Long term, we don't want to have to rely on this implicit
4657 // naming being the same. One possible solution would be to have
4658 // explicit operator for operation capture and reference those.
4659 // The plus side is that it would expose opportunities to share
4660 // the capture accross rules. The downside is that it would
4661 // introduce a dependency between predicates (captures must happen
4662 // before their first use.)
4663 InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher(Src->getName());
4664 unsigned TempOpIdx = 0;
4665 auto InsnMatcherOrError =
4666 createAndImportSelDAGMatcher(M, InsnMatcherTemp, Src, TempOpIdx);
4667 if (auto Error = InsnMatcherOrError.takeError())
4668 return std::move(Error);
4669 InstructionMatcher &InsnMatcher = InsnMatcherOrError.get();
4671 if (Dst->isLeaf()) {
4672 Record *RCDef = getInitValueAsRegClass(Dst->getLeafValue());
4674 const CodeGenRegisterClass &RC = Target.getRegisterClass(RCDef);
4676 // We need to replace the def and all its uses with the specified
4677 // operand. However, we must also insert COPY's wherever needed.
4678 // For now, emit a copy and let the register allocator clean up.
4679 auto &DstI = Target.getInstruction(RK.getDef("COPY"));
4680 const auto &DstIOperand = DstI.Operands[0];
4682 OperandMatcher &OM0 = InsnMatcher.getOperand(0);
4683 OM0.setSymbolicName(DstIOperand.Name);
4684 M.defineOperand(OM0.getSymbolicName(), OM0);
4685 OM0.addPredicate<RegisterBankOperandMatcher>(RC);
4687 auto &DstMIBuilder =
4688 M.addAction<BuildMIAction>(M.allocateOutputInsnID(), &DstI);
4689 DstMIBuilder.addRenderer<CopyRenderer>(DstIOperand.Name);
4690 DstMIBuilder.addRenderer<CopyRenderer>(Dst->getName());
4691 M.addAction<ConstrainOperandToRegClassAction>(0, 0, RC);
4693 // We're done with this pattern! It's eligible for GISel emission; return
4695 ++NumPatternImported;
4696 return std::move(M);
4699 return failedImport("Dst pattern root isn't a known leaf");
4702 // Start with the defined operands (i.e., the results of the root operator).
4703 Record *DstOp = Dst->getOperator();
4704 if (!DstOp->isSubClassOf("Instruction"))
4705 return failedImport("Pattern operator isn't an instruction");
4707 auto &DstI = Target.getInstruction(DstOp);
4708 StringRef DstIName = DstI.TheDef->getName();
4710 if (DstI.Operands.NumDefs != Src->getExtTypes().size())
4711 return failedImport("Src pattern results and dst MI defs are different (" +
4712 to_string(Src->getExtTypes().size()) + " def(s) vs " +
4713 to_string(DstI.Operands.NumDefs) + " def(s))");
4715 // The root of the match also has constraints on the register bank so that it
4716 // matches the result instruction.
4718 for (const TypeSetByHwMode &VTy : Src->getExtTypes()) {
4721 const auto &DstIOperand = DstI.Operands[OpIdx];
4722 Record *DstIOpRec = DstIOperand.Rec;
4723 if (DstIName == "COPY_TO_REGCLASS") {
4724 DstIOpRec = getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());
4726 if (DstIOpRec == nullptr)
4727 return failedImport(
4728 "COPY_TO_REGCLASS operand #1 isn't a register class");
4729 } else if (DstIName == "REG_SEQUENCE") {
4730 DstIOpRec = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
4731 if (DstIOpRec == nullptr)
4732 return failedImport("REG_SEQUENCE operand #0 isn't a register class");
4733 } else if (DstIName == "EXTRACT_SUBREG") {
4734 if (!Dst->getChild(0)->isLeaf())
4735 return failedImport("EXTRACT_SUBREG operand #0 isn't a leaf");
4737 // We can assume that a subregister is in the same bank as it's super
4739 DstIOpRec = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
4741 if (DstIOpRec == nullptr)
4742 return failedImport("EXTRACT_SUBREG operand #0 isn't a register class");
4743 } else if (DstIName == "INSERT_SUBREG") {
4744 auto MaybeSuperClass = inferSuperRegisterClassForNode(
4745 VTy, Dst->getChild(0), Dst->getChild(2));
4746 if (!MaybeSuperClass)
4747 return failedImport(
4748 "Cannot infer register class for INSERT_SUBREG operand #0");
4749 // Move to the next pattern here, because the register class we found
4750 // doesn't necessarily have a record associated with it. So, we can't
4751 // set DstIOpRec using this.
4752 OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
4753 OM.setSymbolicName(DstIOperand.Name);
4754 M.defineOperand(OM.getSymbolicName(), OM);
4755 OM.addPredicate<RegisterBankOperandMatcher>(**MaybeSuperClass);
4758 } else if (DstIName == "SUBREG_TO_REG") {
4759 auto MaybeRegClass = inferSuperRegisterClass(VTy, Dst->getChild(2));
4761 return failedImport(
4762 "Cannot infer register class for SUBREG_TO_REG operand #0");
4763 OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
4764 OM.setSymbolicName(DstIOperand.Name);
4765 M.defineOperand(OM.getSymbolicName(), OM);
4766 OM.addPredicate<RegisterBankOperandMatcher>(**MaybeRegClass);
4769 } else if (DstIOpRec->isSubClassOf("RegisterOperand"))
4770 DstIOpRec = DstIOpRec->getValueAsDef("RegClass");
4771 else if (!DstIOpRec->isSubClassOf("RegisterClass"))
4772 return failedImport("Dst MI def isn't a register class" +
4775 OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
4776 OM.setSymbolicName(DstIOperand.Name);
4777 M.defineOperand(OM.getSymbolicName(), OM);
4778 OM.addPredicate<RegisterBankOperandMatcher>(
4779 Target.getRegisterClass(DstIOpRec));
4783 auto DstMIBuilderOrError =
4784 createAndImportInstructionRenderer(M, InsnMatcher, Src, Dst);
4785 if (auto Error = DstMIBuilderOrError.takeError())
4786 return std::move(Error);
4787 BuildMIAction &DstMIBuilder = DstMIBuilderOrError.get();
4789 // Render the implicit defs.
4790 // These are only added to the root of the result.
4791 if (auto Error = importImplicitDefRenderers(DstMIBuilder, P.getDstRegs()))
4792 return std::move(Error);
4794 DstMIBuilder.chooseInsnToMutate(M);
4796 // Constrain the registers to classes. This is normally derived from the
4797 // emitted instruction but a few instructions require special handling.
4798 if (DstIName == "COPY_TO_REGCLASS") {
4799 // COPY_TO_REGCLASS does not provide operand constraints itself but the
4800 // result is constrained to the class given by the second child.
4802 getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());
4804 if (DstIOpRec == nullptr)
4805 return failedImport("COPY_TO_REGCLASS operand #1 isn't a register class");
4807 M.addAction<ConstrainOperandToRegClassAction>(
4808 0, 0, Target.getRegisterClass(DstIOpRec));
4810 // We're done with this pattern! It's eligible for GISel emission; return
4812 ++NumPatternImported;
4813 return std::move(M);
4816 if (DstIName == "EXTRACT_SUBREG") {
4817 auto SuperClass = inferRegClassFromPattern(Dst->getChild(0));
4819 return failedImport(
4820 "Cannot infer register class from EXTRACT_SUBREG operand #0");
4822 auto SubIdx = inferSubRegIndexForNode(Dst->getChild(1));
4824 return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
4826 // It would be nice to leave this constraint implicit but we're required
4827 // to pick a register class so constrain the result to a register class
4828 // that can hold the correct MVT.
4830 // FIXME: This may introduce an extra copy if the chosen class doesn't
4831 // actually contain the subregisters.
4832 assert(Src->getExtTypes().size() == 1 &&
4833 "Expected Src of EXTRACT_SUBREG to have one result type");
4835 const auto &SrcRCDstRCPair =
4836 (*SuperClass)->getMatchingSubClassWithSubRegs(CGRegs, *SubIdx);
4837 assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
4838 M.addAction<ConstrainOperandToRegClassAction>(0, 0, *SrcRCDstRCPair->second);
4839 M.addAction<ConstrainOperandToRegClassAction>(0, 1, *SrcRCDstRCPair->first);
4841 // We're done with this pattern! It's eligible for GISel emission; return
4843 ++NumPatternImported;
4844 return std::move(M);
4847 if (DstIName == "INSERT_SUBREG") {
4848 assert(Src->getExtTypes().size() == 1 &&
4849 "Expected Src of INSERT_SUBREG to have one result type");
4850 // We need to constrain the destination, a super regsister source, and a
4851 // subregister source.
4852 auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
4854 return failedImport(
4855 "Cannot infer register class from INSERT_SUBREG operand #1");
4856 auto SuperClass = inferSuperRegisterClassForNode(
4857 Src->getExtType(0), Dst->getChild(0), Dst->getChild(2));
4859 return failedImport(
4860 "Cannot infer register class for INSERT_SUBREG operand #0");
4861 M.addAction<ConstrainOperandToRegClassAction>(0, 0, **SuperClass);
4862 M.addAction<ConstrainOperandToRegClassAction>(0, 1, **SuperClass);
4863 M.addAction<ConstrainOperandToRegClassAction>(0, 2, **SubClass);
4864 ++NumPatternImported;
4865 return std::move(M);
4868 if (DstIName == "SUBREG_TO_REG") {
4869 // We need to constrain the destination and subregister source.
4870 assert(Src->getExtTypes().size() == 1 &&
4871 "Expected Src of SUBREG_TO_REG to have one result type");
4873 // Attempt to infer the subregister source from the first child. If it has
4874 // an explicitly given register class, we'll use that. Otherwise, we will
4876 auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
4878 return failedImport(
4879 "Cannot infer register class from SUBREG_TO_REG child #1");
4880 // We don't have a child to look at that might have a super register node.
4882 inferSuperRegisterClass(Src->getExtType(0), Dst->getChild(2));
4884 return failedImport(
4885 "Cannot infer register class for SUBREG_TO_REG operand #0");
4886 M.addAction<ConstrainOperandToRegClassAction>(0, 0, **SuperClass);
4887 M.addAction<ConstrainOperandToRegClassAction>(0, 2, **SubClass);
4888 ++NumPatternImported;
4889 return std::move(M);
4892 M.addAction<ConstrainOperandsToDefinitionAction>(0);
4894 // We're done with this pattern! It's eligible for GISel emission; return it.
4895 ++NumPatternImported;
4896 return std::move(M);
4899 // Emit imm predicate table and an enum to reference them with.
4900 // The 'Predicate_' part of the name is redundant but eliminating it is more
4901 // trouble than it's worth.
4902 void GlobalISelEmitter::emitCxxPredicateFns(
4903 raw_ostream &OS, StringRef CodeFieldName, StringRef TypeIdentifier,
4904 StringRef ArgType, StringRef ArgName, StringRef AdditionalDeclarations,
4905 std::function<bool(const Record *R)> Filter) {
4906 std::vector<const Record *> MatchedRecords;
4907 const auto &Defs = RK.getAllDerivedDefinitions("PatFrag");
4908 std::copy_if(Defs.begin(), Defs.end(), std::back_inserter(MatchedRecords),
4909 [&](Record *Record) {
4910 return !Record->getValueAsString(CodeFieldName).empty() &&
4914 if (!MatchedRecords.empty()) {
4915 OS << "// PatFrag predicates.\n"
4917 std::string EnumeratorSeparator =
4918 (" = GIPFP_" + TypeIdentifier + "_Invalid + 1,\n").str();
4919 for (const auto *Record : MatchedRecords) {
4920 OS << " GIPFP_" << TypeIdentifier << "_Predicate_" << Record->getName()
4921 << EnumeratorSeparator;
4922 EnumeratorSeparator = ",\n";
4927 OS << "bool " << Target.getName() << "InstructionSelector::test" << ArgName
4928 << "Predicate_" << TypeIdentifier << "(unsigned PredicateID, " << ArgType << " "
4929 << ArgName << ") const {\n"
4930 << AdditionalDeclarations;
4931 if (!AdditionalDeclarations.empty())
4933 if (!MatchedRecords.empty())
4934 OS << " switch (PredicateID) {\n";
4935 for (const auto *Record : MatchedRecords) {
4936 OS << " case GIPFP_" << TypeIdentifier << "_Predicate_"
4937 << Record->getName() << ": {\n"
4938 << " " << Record->getValueAsString(CodeFieldName) << "\n"
4939 << " llvm_unreachable(\"" << CodeFieldName
4940 << " should have returned\");\n"
4941 << " return false;\n"
4944 if (!MatchedRecords.empty())
4946 OS << " llvm_unreachable(\"Unknown predicate\");\n"
4947 << " return false;\n"
4951 void GlobalISelEmitter::emitImmPredicateFns(
4952 raw_ostream &OS, StringRef TypeIdentifier, StringRef ArgType,
4953 std::function<bool(const Record *R)> Filter) {
4954 return emitCxxPredicateFns(OS, "ImmediateCode", TypeIdentifier, ArgType,
4958 void GlobalISelEmitter::emitMIPredicateFns(raw_ostream &OS) {
4959 return emitCxxPredicateFns(
4960 OS, "GISelPredicateCode", "MI", "const MachineInstr &", "MI",
4961 " const MachineFunction &MF = *MI.getParent()->getParent();\n"
4962 " const MachineRegisterInfo &MRI = MF.getRegInfo();\n"
4964 [](const Record *R) { return true; });
4967 template <class GroupT>
4968 std::vector<Matcher *> GlobalISelEmitter::optimizeRules(
4969 ArrayRef<Matcher *> Rules,
4970 std::vector<std::unique_ptr<Matcher>> &MatcherStorage) {
4972 std::vector<Matcher *> OptRules;
4973 std::unique_ptr<GroupT> CurrentGroup = std::make_unique<GroupT>();
4974 assert(CurrentGroup->empty() && "Newly created group isn't empty!");
4975 unsigned NumGroups = 0;
4977 auto ProcessCurrentGroup = [&]() {
4978 if (CurrentGroup->empty())
4979 // An empty group is good to be reused:
4982 // If the group isn't large enough to provide any benefit, move all the
4983 // added rules out of it and make sure to re-create the group to properly
4984 // re-initialize it:
4985 if (CurrentGroup->size() < 2)
4986 for (Matcher *M : CurrentGroup->matchers())
4987 OptRules.push_back(M);
4989 CurrentGroup->finalize();
4990 OptRules.push_back(CurrentGroup.get());
4991 MatcherStorage.emplace_back(std::move(CurrentGroup));
4994 CurrentGroup = std::make_unique<GroupT>();
4996 for (Matcher *Rule : Rules) {
4997 // Greedily add as many matchers as possible to the current group:
4998 if (CurrentGroup->addMatcher(*Rule))
5001 ProcessCurrentGroup();
5002 assert(CurrentGroup->empty() && "A group wasn't properly re-initialized");
5004 // Try to add the pending matcher to a newly created empty group:
5005 if (!CurrentGroup->addMatcher(*Rule))
5006 // If we couldn't add the matcher to an empty group, that group type
5007 // doesn't support that kind of matchers at all, so just skip it:
5008 OptRules.push_back(Rule);
5010 ProcessCurrentGroup();
5012 LLVM_DEBUG(dbgs() << "NumGroups: " << NumGroups << "\n");
5013 assert(CurrentGroup->empty() && "The last group wasn't properly processed");
5018 GlobalISelEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules,
5019 bool Optimize, bool WithCoverage) {
5020 std::vector<Matcher *> InputRules;
5021 for (Matcher &Rule : Rules)
5022 InputRules.push_back(&Rule);
5025 return MatchTable::buildTable(InputRules, WithCoverage);
5027 unsigned CurrentOrdering = 0;
5028 StringMap<unsigned> OpcodeOrder;
5029 for (RuleMatcher &Rule : Rules) {
5030 const StringRef Opcode = Rule.getOpcode();
5031 assert(!Opcode.empty() && "Didn't expect an undefined opcode");
5032 if (OpcodeOrder.count(Opcode) == 0)
5033 OpcodeOrder[Opcode] = CurrentOrdering++;
5036 std::stable_sort(InputRules.begin(), InputRules.end(),
5037 [&OpcodeOrder](const Matcher *A, const Matcher *B) {
5038 auto *L = static_cast<const RuleMatcher *>(A);
5039 auto *R = static_cast<const RuleMatcher *>(B);
5040 return std::make_tuple(OpcodeOrder[L->getOpcode()],
5041 L->getNumOperands()) <
5042 std::make_tuple(OpcodeOrder[R->getOpcode()],
5043 R->getNumOperands());
5046 for (Matcher *Rule : InputRules)
5049 std::vector<std::unique_ptr<Matcher>> MatcherStorage;
5050 std::vector<Matcher *> OptRules =
5051 optimizeRules<GroupMatcher>(InputRules, MatcherStorage);
5053 for (Matcher *Rule : OptRules)
5056 OptRules = optimizeRules<SwitchMatcher>(OptRules, MatcherStorage);
5058 return MatchTable::buildTable(OptRules, WithCoverage);
5061 void GroupMatcher::optimize() {
5062 // Make sure we only sort by a specific predicate within a range of rules that
5063 // all have that predicate checked against a specific value (not a wildcard):
5064 auto F = Matchers.begin();
5066 auto E = Matchers.end();
5069 auto *R = static_cast<RuleMatcher *>(*T);
5070 if (!R->getFirstConditionAsRootType().get().isValid())
5074 std::stable_sort(F, T, [](Matcher *A, Matcher *B) {
5075 auto *L = static_cast<RuleMatcher *>(A);
5076 auto *R = static_cast<RuleMatcher *>(B);
5077 return L->getFirstConditionAsRootType() <
5078 R->getFirstConditionAsRootType();
5083 GlobalISelEmitter::optimizeRules<GroupMatcher>(Matchers, MatcherStorage)
5085 GlobalISelEmitter::optimizeRules<SwitchMatcher>(Matchers, MatcherStorage)
5089 void GlobalISelEmitter::run(raw_ostream &OS) {
5090 if (!UseCoverageFile.empty()) {
5091 RuleCoverage = CodeGenCoverage();
5092 auto RuleCoverageBufOrErr = MemoryBuffer::getFile(UseCoverageFile);
5093 if (!RuleCoverageBufOrErr) {
5094 PrintWarning(SMLoc(), "Missing rule coverage data");
5095 RuleCoverage = None;
5097 if (!RuleCoverage->parse(*RuleCoverageBufOrErr.get(), Target.getName())) {
5098 PrintWarning(SMLoc(), "Ignoring invalid or missing rule coverage data");
5099 RuleCoverage = None;
5104 // Track the run-time opcode values
5105 gatherOpcodeValues();
5106 // Track the run-time LLT ID values
5107 gatherTypeIDValues();
5109 // Track the GINodeEquiv definitions.
5112 emitSourceFileHeader(("Global Instruction Selector for the " +
5113 Target.getName() + " target").str(), OS);
5114 std::vector<RuleMatcher> Rules;
5115 // Look through the SelectionDAG patterns we found, possibly emitting some.
5116 for (const PatternToMatch &Pat : CGP.ptms()) {
5119 auto MatcherOrErr = runOnPattern(Pat);
5121 // The pattern analysis can fail, indicating an unsupported pattern.
5122 // Report that if we've been asked to do so.
5123 if (auto Err = MatcherOrErr.takeError()) {
5124 if (WarnOnSkippedPatterns) {
5125 PrintWarning(Pat.getSrcRecord()->getLoc(),
5126 "Skipped pattern: " + toString(std::move(Err)));
5128 consumeError(std::move(Err));
5130 ++NumPatternImportsSkipped;
5135 if (RuleCoverage->isCovered(MatcherOrErr->getRuleID()))
5136 ++NumPatternsTested;
5138 PrintWarning(Pat.getSrcRecord()->getLoc(),
5139 "Pattern is not covered by a test");
5141 Rules.push_back(std::move(MatcherOrErr.get()));
5144 // Comparison function to order records by name.
5145 auto orderByName = [](const Record *A, const Record *B) {
5146 return A->getName() < B->getName();
5149 std::vector<Record *> ComplexPredicates =
5150 RK.getAllDerivedDefinitions("GIComplexOperandMatcher");
5151 llvm::sort(ComplexPredicates, orderByName);
5153 std::vector<Record *> CustomRendererFns =
5154 RK.getAllDerivedDefinitions("GICustomOperandRenderer");
5155 llvm::sort(CustomRendererFns, orderByName);
5157 unsigned MaxTemporaries = 0;
5158 for (const auto &Rule : Rules)
5159 MaxTemporaries = std::max(MaxTemporaries, Rule.countRendererFns());
5161 OS << "#ifdef GET_GLOBALISEL_PREDICATE_BITSET\n"
5162 << "const unsigned MAX_SUBTARGET_PREDICATES = " << SubtargetFeatures.size()
5164 << "using PredicateBitset = "
5165 "llvm::PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;\n"
5166 << "#endif // ifdef GET_GLOBALISEL_PREDICATE_BITSET\n\n";
5168 OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n"
5169 << " mutable MatcherState State;\n"
5171 "ComplexRendererFns("
5173 << "InstructionSelector::*ComplexMatcherMemFn)(MachineOperand &) const;\n"
5175 << " typedef void(" << Target.getName()
5176 << "InstructionSelector::*CustomRendererFn)(MachineInstrBuilder &, const "
5177 "MachineInstr&, int) "
5179 << " const ISelInfoTy<PredicateBitset, ComplexMatcherMemFn, "
5180 "CustomRendererFn> "
5182 OS << " static " << Target.getName()
5183 << "InstructionSelector::ComplexMatcherMemFn ComplexPredicateFns[];\n"
5184 << " static " << Target.getName()
5185 << "InstructionSelector::CustomRendererFn CustomRenderers[];\n"
5186 << " bool testImmPredicate_I64(unsigned PredicateID, int64_t Imm) const "
5188 << " bool testImmPredicate_APInt(unsigned PredicateID, const APInt &Imm) "
5190 << " bool testImmPredicate_APFloat(unsigned PredicateID, const APFloat "
5191 "&Imm) const override;\n"
5192 << " const int64_t *getMatchTable() const override;\n"
5193 << " bool testMIPredicate_MI(unsigned PredicateID, const MachineInstr &MI) "
5195 << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n";
5197 OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n"
5198 << ", State(" << MaxTemporaries << "),\n"
5199 << "ISelInfo(TypeObjects, NumTypeObjects, FeatureBitsets"
5200 << ", ComplexPredicateFns, CustomRenderers)\n"
5201 << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";
5203 OS << "#ifdef GET_GLOBALISEL_IMPL\n";
5204 SubtargetFeatureInfo::emitSubtargetFeatureBitEnumeration(SubtargetFeatures,
5207 // Separate subtarget features by how often they must be recomputed.
5208 SubtargetFeatureInfoMap ModuleFeatures;
5209 std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
5210 std::inserter(ModuleFeatures, ModuleFeatures.end()),
5211 [](const SubtargetFeatureInfoMap::value_type &X) {
5212 return !X.second.mustRecomputePerFunction();
5214 SubtargetFeatureInfoMap FunctionFeatures;
5215 std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
5216 std::inserter(FunctionFeatures, FunctionFeatures.end()),
5217 [](const SubtargetFeatureInfoMap::value_type &X) {
5218 return X.second.mustRecomputePerFunction();
5221 SubtargetFeatureInfo::emitComputeAvailableFeatures(
5222 Target.getName(), "InstructionSelector", "computeAvailableModuleFeatures",
5223 ModuleFeatures, OS);
5226 OS << "void " << Target.getName() << "InstructionSelector"
5227 "::setupGeneratedPerFunctionState(MachineFunction &MF) {\n"
5228 " AvailableFunctionFeatures = computeAvailableFunctionFeatures("
5229 "(const " << Target.getName() << "Subtarget*)&MF.getSubtarget(), &MF);\n"
5232 if (Target.getName() == "X86" || Target.getName() == "AArch64") {
5233 // TODO: Implement PGSO.
5234 OS << "static bool shouldOptForSize(const MachineFunction *MF) {\n";
5235 OS << " return MF->getFunction().hasOptSize();\n";
5239 SubtargetFeatureInfo::emitComputeAvailableFeatures(
5240 Target.getName(), "InstructionSelector",
5241 "computeAvailableFunctionFeatures", FunctionFeatures, OS,
5242 "const MachineFunction *MF");
5244 // Emit a table containing the LLT objects needed by the matcher and an enum
5245 // for the matcher to reference them with.
5246 std::vector<LLTCodeGen> TypeObjects;
5247 for (const auto &Ty : KnownTypes)
5248 TypeObjects.push_back(Ty);
5249 llvm::sort(TypeObjects);
5250 OS << "// LLT Objects.\n"
5252 for (const auto &TypeObject : TypeObjects) {
5254 TypeObject.emitCxxEnumValue(OS);
5258 OS << "const static size_t NumTypeObjects = " << TypeObjects.size() << ";\n"
5259 << "const static LLT TypeObjects[] = {\n";
5260 for (const auto &TypeObject : TypeObjects) {
5262 TypeObject.emitCxxConstructorCall(OS);
5267 // Emit a table containing the PredicateBitsets objects needed by the matcher
5268 // and an enum for the matcher to reference them with.
5269 std::vector<std::vector<Record *>> FeatureBitsets;
5270 for (auto &Rule : Rules)
5271 FeatureBitsets.push_back(Rule.getRequiredFeatures());
5272 llvm::sort(FeatureBitsets, [&](const std::vector<Record *> &A,
5273 const std::vector<Record *> &B) {
5274 if (A.size() < B.size())
5276 if (A.size() > B.size())
5278 for (auto Pair : zip(A, B)) {
5279 if (std::get<0>(Pair)->getName() < std::get<1>(Pair)->getName())
5281 if (std::get<0>(Pair)->getName() > std::get<1>(Pair)->getName())
5286 FeatureBitsets.erase(
5287 std::unique(FeatureBitsets.begin(), FeatureBitsets.end()),
5288 FeatureBitsets.end());
5289 OS << "// Feature bitsets.\n"
5291 << " GIFBS_Invalid,\n";
5292 for (const auto &FeatureBitset : FeatureBitsets) {
5293 if (FeatureBitset.empty())
5295 OS << " " << getNameForFeatureBitset(FeatureBitset) << ",\n";
5298 << "const static PredicateBitset FeatureBitsets[] {\n"
5299 << " {}, // GIFBS_Invalid\n";
5300 for (const auto &FeatureBitset : FeatureBitsets) {
5301 if (FeatureBitset.empty())
5304 for (const auto &Feature : FeatureBitset) {
5305 const auto &I = SubtargetFeatures.find(Feature);
5306 assert(I != SubtargetFeatures.end() && "Didn't import predicate?");
5307 OS << I->second.getEnumBitName() << ", ";
5313 // Emit complex predicate table and an enum to reference them with.
5314 OS << "// ComplexPattern predicates.\n"
5316 << " GICP_Invalid,\n";
5317 for (const auto &Record : ComplexPredicates)
5318 OS << " GICP_" << Record->getName() << ",\n";
5320 << "// See constructor for table contents\n\n";
5322 emitImmPredicateFns(OS, "I64", "int64_t", [](const Record *R) {
5324 return !R->getValueAsBitOrUnset("IsAPFloat", Unset) &&
5325 !R->getValueAsBit("IsAPInt");
5327 emitImmPredicateFns(OS, "APFloat", "const APFloat &", [](const Record *R) {
5329 return R->getValueAsBitOrUnset("IsAPFloat", Unset);
5331 emitImmPredicateFns(OS, "APInt", "const APInt &", [](const Record *R) {
5332 return R->getValueAsBit("IsAPInt");
5334 emitMIPredicateFns(OS);
5337 OS << Target.getName() << "InstructionSelector::ComplexMatcherMemFn\n"
5338 << Target.getName() << "InstructionSelector::ComplexPredicateFns[] = {\n"
5339 << " nullptr, // GICP_Invalid\n";
5340 for (const auto &Record : ComplexPredicates)
5341 OS << " &" << Target.getName()
5342 << "InstructionSelector::" << Record->getValueAsString("MatcherFn")
5343 << ", // " << Record->getName() << "\n";
5346 OS << "// Custom renderers.\n"
5348 << " GICR_Invalid,\n";
5349 for (const auto &Record : CustomRendererFns)
5350 OS << " GICR_" << Record->getValueAsString("RendererFn") << ", \n";
5353 OS << Target.getName() << "InstructionSelector::CustomRendererFn\n"
5354 << Target.getName() << "InstructionSelector::CustomRenderers[] = {\n"
5355 << " nullptr, // GICR_Invalid\n";
5356 for (const auto &Record : CustomRendererFns)
5357 OS << " &" << Target.getName()
5358 << "InstructionSelector::" << Record->getValueAsString("RendererFn")
5359 << ", // " << Record->getName() << "\n";
5362 llvm::stable_sort(Rules, [&](const RuleMatcher &A, const RuleMatcher &B) {
5363 int ScoreA = RuleMatcherScores[A.getRuleID()];
5364 int ScoreB = RuleMatcherScores[B.getRuleID()];
5365 if (ScoreA > ScoreB)
5367 if (ScoreB > ScoreA)
5369 if (A.isHigherPriorityThan(B)) {
5370 assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
5371 "and less important at "
5378 OS << "bool " << Target.getName()
5379 << "InstructionSelector::selectImpl(MachineInstr &I, CodeGenCoverage "
5380 "&CoverageInfo) const {\n"
5381 << " MachineFunction &MF = *I.getParent()->getParent();\n"
5382 << " MachineRegisterInfo &MRI = MF.getRegInfo();\n"
5383 << " const PredicateBitset AvailableFeatures = getAvailableFeatures();\n"
5384 << " NewMIVector OutMIs;\n"
5385 << " State.MIs.clear();\n"
5386 << " State.MIs.push_back(&I);\n\n"
5387 << " if (executeMatchTable(*this, OutMIs, State, ISelInfo"
5388 << ", getMatchTable(), TII, MRI, TRI, RBI, AvailableFeatures"
5389 << ", CoverageInfo)) {\n"
5390 << " return true;\n"
5392 << " return false;\n"
5395 const MatchTable Table =
5396 buildMatchTable(Rules, OptimizeMatchTable, GenerateCoverage);
5397 OS << "const int64_t *" << Target.getName()
5398 << "InstructionSelector::getMatchTable() const {\n";
5399 Table.emitDeclaration(OS);
5403 OS << "#endif // ifdef GET_GLOBALISEL_IMPL\n";
5405 OS << "#ifdef GET_GLOBALISEL_PREDICATES_DECL\n"
5406 << "PredicateBitset AvailableModuleFeatures;\n"
5407 << "mutable PredicateBitset AvailableFunctionFeatures;\n"
5408 << "PredicateBitset getAvailableFeatures() const {\n"
5409 << " return AvailableModuleFeatures | AvailableFunctionFeatures;\n"
5411 << "PredicateBitset\n"
5412 << "computeAvailableModuleFeatures(const " << Target.getName()
5413 << "Subtarget *Subtarget) const;\n"
5414 << "PredicateBitset\n"
5415 << "computeAvailableFunctionFeatures(const " << Target.getName()
5416 << "Subtarget *Subtarget,\n"
5417 << " const MachineFunction *MF) const;\n"
5418 << "void setupGeneratedPerFunctionState(MachineFunction &MF) override;\n"
5419 << "#endif // ifdef GET_GLOBALISEL_PREDICATES_DECL\n";
5421 OS << "#ifdef GET_GLOBALISEL_PREDICATES_INIT\n"
5422 << "AvailableModuleFeatures(computeAvailableModuleFeatures(&STI)),\n"
5423 << "AvailableFunctionFeatures()\n"
5424 << "#endif // ifdef GET_GLOBALISEL_PREDICATES_INIT\n";
5427 void GlobalISelEmitter::declareSubtargetFeature(Record *Predicate) {
5428 if (SubtargetFeatures.count(Predicate) == 0)
5429 SubtargetFeatures.emplace(
5430 Predicate, SubtargetFeatureInfo(Predicate, SubtargetFeatures.size()));
5433 void RuleMatcher::optimize() {
5434 for (auto &Item : InsnVariableIDs) {
5435 InstructionMatcher &InsnMatcher = *Item.first;
5436 for (auto &OM : InsnMatcher.operands()) {
5437 // Complex Patterns are usually expensive and they relatively rarely fail
5438 // on their own: more often we end up throwing away all the work done by a
5439 // matching part of a complex pattern because some other part of the
5440 // enclosing pattern didn't match. All of this makes it beneficial to
5441 // delay complex patterns until the very end of the rule matching,
5442 // especially for targets having lots of complex patterns.
5443 for (auto &OP : OM->predicates())
5444 if (isa<ComplexPatternOperandMatcher>(OP))
5445 EpilogueMatchers.emplace_back(std::move(OP));
5446 OM->eraseNullPredicates();
5448 InsnMatcher.optimize();
5450 llvm::sort(EpilogueMatchers, [](const std::unique_ptr<PredicateMatcher> &L,
5451 const std::unique_ptr<PredicateMatcher> &R) {
5452 return std::make_tuple(L->getKind(), L->getInsnVarID(), L->getOpIdx()) <
5453 std::make_tuple(R->getKind(), R->getInsnVarID(), R->getOpIdx());
5457 bool RuleMatcher::hasFirstCondition() const {
5458 if (insnmatchers_empty())
5460 InstructionMatcher &Matcher = insnmatchers_front();
5461 if (!Matcher.predicates_empty())
5463 for (auto &OM : Matcher.operands())
5464 for (auto &OP : OM->predicates())
5465 if (!isa<InstructionOperandMatcher>(OP))
5470 const PredicateMatcher &RuleMatcher::getFirstCondition() const {
5471 assert(!insnmatchers_empty() &&
5472 "Trying to get a condition from an empty RuleMatcher");
5474 InstructionMatcher &Matcher = insnmatchers_front();
5475 if (!Matcher.predicates_empty())
5476 return **Matcher.predicates_begin();
5477 // If there is no more predicate on the instruction itself, look at its
5479 for (auto &OM : Matcher.operands())
5480 for (auto &OP : OM->predicates())
5481 if (!isa<InstructionOperandMatcher>(OP))
5484 llvm_unreachable("Trying to get a condition from an InstructionMatcher with "
5488 std::unique_ptr<PredicateMatcher> RuleMatcher::popFirstCondition() {
5489 assert(!insnmatchers_empty() &&
5490 "Trying to pop a condition from an empty RuleMatcher");
5492 InstructionMatcher &Matcher = insnmatchers_front();
5493 if (!Matcher.predicates_empty())
5494 return Matcher.predicates_pop_front();
5495 // If there is no more predicate on the instruction itself, look at its
5497 for (auto &OM : Matcher.operands())
5498 for (auto &OP : OM->predicates())
5499 if (!isa<InstructionOperandMatcher>(OP)) {
5500 std::unique_ptr<PredicateMatcher> Result = std::move(OP);
5501 OM->eraseNullPredicates();
5505 llvm_unreachable("Trying to pop a condition from an InstructionMatcher with "
5509 bool GroupMatcher::candidateConditionMatches(
5510 const PredicateMatcher &Predicate) const {
5513 // Sharing predicates for nested instructions is not supported yet as we
5514 // currently don't hoist the GIM_RecordInsn's properly, therefore we can
5515 // only work on the original root instruction (InsnVarID == 0):
5516 if (Predicate.getInsnVarID() != 0)
5518 // ... otherwise an empty group can handle any predicate with no specific
5523 const Matcher &Representative = **Matchers.begin();
5524 const auto &RepresentativeCondition = Representative.getFirstCondition();
5525 // ... if not empty, the group can only accomodate matchers with the exact
5526 // same first condition:
5527 return Predicate.isIdentical(RepresentativeCondition);
5530 bool GroupMatcher::addMatcher(Matcher &Candidate) {
5531 if (!Candidate.hasFirstCondition())
5534 const PredicateMatcher &Predicate = Candidate.getFirstCondition();
5535 if (!candidateConditionMatches(Predicate))
5538 Matchers.push_back(&Candidate);
5542 void GroupMatcher::finalize() {
5543 assert(Conditions.empty() && "Already finalized?");
5547 Matcher &FirstRule = **Matchers.begin();
5549 // All the checks are expected to succeed during the first iteration:
5550 for (const auto &Rule : Matchers)
5551 if (!Rule->hasFirstCondition())
5553 const auto &FirstCondition = FirstRule.getFirstCondition();
5554 for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
5555 if (!Matchers[I]->getFirstCondition().isIdentical(FirstCondition))
5558 Conditions.push_back(FirstRule.popFirstCondition());
5559 for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
5560 Matchers[I]->popFirstCondition();
5564 void GroupMatcher::emit(MatchTable &Table) {
5565 unsigned LabelID = ~0U;
5566 if (!Conditions.empty()) {
5567 LabelID = Table.allocateLabelID();
5568 Table << MatchTable::Opcode("GIM_Try", +1)
5569 << MatchTable::Comment("On fail goto")
5570 << MatchTable::JumpTarget(LabelID) << MatchTable::LineBreak;
5572 for (auto &Condition : Conditions)
5573 Condition->emitPredicateOpcodes(
5574 Table, *static_cast<RuleMatcher *>(*Matchers.begin()));
5576 for (const auto &M : Matchers)
5580 if (!Conditions.empty())
5581 Table << MatchTable::Opcode("GIM_Reject", -1) << MatchTable::LineBreak
5582 << MatchTable::Label(LabelID);
5585 bool SwitchMatcher::isSupportedPredicateType(const PredicateMatcher &P) {
5586 return isa<InstructionOpcodeMatcher>(P) || isa<LLTOperandMatcher>(P);
5589 bool SwitchMatcher::candidateConditionMatches(
5590 const PredicateMatcher &Predicate) const {
5593 // Sharing predicates for nested instructions is not supported yet as we
5594 // currently don't hoist the GIM_RecordInsn's properly, therefore we can
5595 // only work on the original root instruction (InsnVarID == 0):
5596 if (Predicate.getInsnVarID() != 0)
5598 // ... while an attempt to add even a root matcher to an empty SwitchMatcher
5599 // could fail as not all the types of conditions are supported:
5600 if (!isSupportedPredicateType(Predicate))
5602 // ... or the condition might not have a proper implementation of
5603 // getValue() / isIdenticalDownToValue() yet:
5604 if (!Predicate.hasValue())
5606 // ... otherwise an empty Switch can accomodate the condition with no
5607 // further requirements:
5611 const Matcher &CaseRepresentative = **Matchers.begin();
5612 const auto &RepresentativeCondition = CaseRepresentative.getFirstCondition();
5613 // Switch-cases must share the same kind of condition and path to the value it
5615 if (!Predicate.isIdenticalDownToValue(RepresentativeCondition))
5618 const auto Value = Predicate.getValue();
5619 // ... but be unique with respect to the actual value they check:
5620 return Values.count(Value) == 0;
5623 bool SwitchMatcher::addMatcher(Matcher &Candidate) {
5624 if (!Candidate.hasFirstCondition())
5627 const PredicateMatcher &Predicate = Candidate.getFirstCondition();
5628 if (!candidateConditionMatches(Predicate))
5630 const auto Value = Predicate.getValue();
5631 Values.insert(Value);
5633 Matchers.push_back(&Candidate);
5637 void SwitchMatcher::finalize() {
5638 assert(Condition == nullptr && "Already finalized");
5639 assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");
5643 std::stable_sort(Matchers.begin(), Matchers.end(),
5644 [](const Matcher *L, const Matcher *R) {
5645 return L->getFirstCondition().getValue() <
5646 R->getFirstCondition().getValue();
5648 Condition = Matchers[0]->popFirstCondition();
5649 for (unsigned I = 1, E = Values.size(); I < E; ++I)
5650 Matchers[I]->popFirstCondition();
5653 void SwitchMatcher::emitPredicateSpecificOpcodes(const PredicateMatcher &P,
5654 MatchTable &Table) {
5655 assert(isSupportedPredicateType(P) && "Predicate type is not supported");
5657 if (const auto *Condition = dyn_cast<InstructionOpcodeMatcher>(&P)) {
5658 Table << MatchTable::Opcode("GIM_SwitchOpcode") << MatchTable::Comment("MI")
5659 << MatchTable::IntValue(Condition->getInsnVarID());
5662 if (const auto *Condition = dyn_cast<LLTOperandMatcher>(&P)) {
5663 Table << MatchTable::Opcode("GIM_SwitchType") << MatchTable::Comment("MI")
5664 << MatchTable::IntValue(Condition->getInsnVarID())
5665 << MatchTable::Comment("Op")
5666 << MatchTable::IntValue(Condition->getOpIdx());
5670 llvm_unreachable("emitPredicateSpecificOpcodes is broken: can not handle a "
5671 "predicate type that is claimed to be supported");
5674 void SwitchMatcher::emit(MatchTable &Table) {
5675 assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");
5678 assert(Condition != nullptr &&
5679 "Broken SwitchMatcher, hasn't been finalized?");
5681 std::vector<unsigned> LabelIDs(Values.size());
5682 std::generate(LabelIDs.begin(), LabelIDs.end(),
5683 [&Table]() { return Table.allocateLabelID(); });
5684 const unsigned Default = Table.allocateLabelID();
5686 const int64_t LowerBound = Values.begin()->getRawValue();
5687 const int64_t UpperBound = Values.rbegin()->getRawValue() + 1;
5689 emitPredicateSpecificOpcodes(*Condition, Table);
5691 Table << MatchTable::Comment("[") << MatchTable::IntValue(LowerBound)
5692 << MatchTable::IntValue(UpperBound) << MatchTable::Comment(")")
5693 << MatchTable::Comment("default:") << MatchTable::JumpTarget(Default);
5695 int64_t J = LowerBound;
5696 auto VI = Values.begin();
5697 for (unsigned I = 0, E = Values.size(); I < E; ++I) {
5699 while (J++ < V.getRawValue())
5700 Table << MatchTable::IntValue(0);
5701 V.turnIntoComment();
5702 Table << MatchTable::LineBreak << V << MatchTable::JumpTarget(LabelIDs[I]);
5704 Table << MatchTable::LineBreak;
5706 for (unsigned I = 0, E = Values.size(); I < E; ++I) {
5707 Table << MatchTable::Label(LabelIDs[I]);
5708 Matchers[I]->emit(Table);
5709 Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
5711 Table << MatchTable::Label(Default);
5714 unsigned OperandMatcher::getInsnVarID() const { return Insn.getInsnVarID(); }
5716 } // end anonymous namespace
5718 //===----------------------------------------------------------------------===//
5721 void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS) {
5722 GlobalISelEmitter(RK).run(OS);
5724 } // End llvm namespace