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 if (P.isAtomicOrderingMonotonic())
253 Explanation += " monotonic";
254 if (P.isAtomicOrderingAcquire())
255 Explanation += " acquire";
256 if (P.isAtomicOrderingRelease())
257 Explanation += " release";
258 if (P.isAtomicOrderingAcquireRelease())
259 Explanation += " acq_rel";
260 if (P.isAtomicOrderingSequentiallyConsistent())
261 Explanation += " seq_cst";
262 if (P.isAtomicOrderingAcquireOrStronger())
263 Explanation += " >=acquire";
264 if (P.isAtomicOrderingWeakerThanAcquire())
265 Explanation += " <acquire";
266 if (P.isAtomicOrderingReleaseOrStronger())
267 Explanation += " >=release";
268 if (P.isAtomicOrderingWeakerThanRelease())
269 Explanation += " <release";
274 std::string explainOperator(Record *Operator) {
275 if (Operator->isSubClassOf("SDNode"))
276 return (" (" + Operator->getValueAsString("Opcode") + ")").str();
278 if (Operator->isSubClassOf("Intrinsic"))
279 return (" (Operator is an Intrinsic, " + Operator->getName() + ")").str();
281 if (Operator->isSubClassOf("ComplexPattern"))
282 return (" (Operator is an unmapped ComplexPattern, " + Operator->getName() +
286 if (Operator->isSubClassOf("SDNodeXForm"))
287 return (" (Operator is an unmapped SDNodeXForm, " + Operator->getName() +
291 return (" (Operator " + Operator->getName() + " not understood)").str();
294 /// Helper function to let the emitter report skip reason error messages.
295 static Error failedImport(const Twine &Reason) {
296 return make_error<StringError>(Reason, inconvertibleErrorCode());
299 static Error isTrivialOperatorNode(const TreePatternNode *N) {
300 std::string Explanation = "";
301 std::string Separator = "";
303 bool HasUnsupportedPredicate = false;
304 for (const TreePredicateCall &Call : N->getPredicateCalls()) {
305 const TreePredicateFn &Predicate = Call.Fn;
307 if (Predicate.isAlwaysTrue())
310 if (Predicate.isImmediatePattern())
313 if (Predicate.isNonExtLoad() || Predicate.isAnyExtLoad() ||
314 Predicate.isSignExtLoad() || Predicate.isZeroExtLoad())
317 if (Predicate.isNonTruncStore() || Predicate.isTruncStore())
320 if (Predicate.isLoad() && Predicate.getMemoryVT())
323 if (Predicate.isLoad() || Predicate.isStore()) {
324 if (Predicate.isUnindexed())
328 if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
329 const ListInit *AddrSpaces = Predicate.getAddressSpaces();
330 if (AddrSpaces && !AddrSpaces->empty())
334 if (Predicate.isAtomic() && Predicate.getMemoryVT())
337 if (Predicate.isAtomic() &&
338 (Predicate.isAtomicOrderingMonotonic() ||
339 Predicate.isAtomicOrderingAcquire() ||
340 Predicate.isAtomicOrderingRelease() ||
341 Predicate.isAtomicOrderingAcquireRelease() ||
342 Predicate.isAtomicOrderingSequentiallyConsistent() ||
343 Predicate.isAtomicOrderingAcquireOrStronger() ||
344 Predicate.isAtomicOrderingWeakerThanAcquire() ||
345 Predicate.isAtomicOrderingReleaseOrStronger() ||
346 Predicate.isAtomicOrderingWeakerThanRelease()))
349 if (Predicate.hasGISelPredicateCode())
352 HasUnsupportedPredicate = true;
353 Explanation = Separator + "Has a predicate (" + explainPredicates(N) + ")";
355 Explanation += (Separator + "first-failing:" +
356 Predicate.getOrigPatFragRecord()->getRecord()->getName())
361 if (!HasUnsupportedPredicate)
362 return Error::success();
364 return failedImport(Explanation);
367 static Record *getInitValueAsRegClass(Init *V) {
368 if (DefInit *VDefInit = dyn_cast<DefInit>(V)) {
369 if (VDefInit->getDef()->isSubClassOf("RegisterOperand"))
370 return VDefInit->getDef()->getValueAsDef("RegClass");
371 if (VDefInit->getDef()->isSubClassOf("RegisterClass"))
372 return VDefInit->getDef();
378 getNameForFeatureBitset(const std::vector<Record *> &FeatureBitset) {
379 std::string Name = "GIFBS";
380 for (const auto &Feature : FeatureBitset)
381 Name += ("_" + Feature->getName()).str();
385 //===- MatchTable Helpers -------------------------------------------------===//
389 /// A record to be stored in a MatchTable.
391 /// This class represents any and all output that may be required to emit the
392 /// MatchTable. Instances are most often configured to represent an opcode or
393 /// value that will be emitted to the table with some formatting but it can also
394 /// represent commas, comments, and other formatting instructions.
395 struct MatchTableRecord {
396 enum RecordFlagsBits {
398 /// Causes EmitStr to be formatted as comment when emitted.
400 /// Causes the record value to be followed by a comma when emitted.
401 MTRF_CommaFollows = 0x2,
402 /// Causes the record value to be followed by a line break when emitted.
403 MTRF_LineBreakFollows = 0x4,
404 /// Indicates that the record defines a label and causes an additional
405 /// comment to be emitted containing the index of the label.
407 /// Causes the record to be emitted as the index of the label specified by
408 /// LabelID along with a comment indicating where that label is.
409 MTRF_JumpTarget = 0x10,
410 /// Causes the formatter to add a level of indentation before emitting the
413 /// Causes the formatter to remove a level of indentation after emitting the
418 /// When MTRF_Label or MTRF_JumpTarget is used, indicates a label id to
419 /// reference or define.
421 /// The string to emit. Depending on the MTRF_* flags it may be a comment, a
422 /// value, a label name.
426 /// The number of MatchTable elements described by this record. Comments are 0
427 /// while values are typically 1. Values >1 may occur when we need to emit
428 /// values that exceed the size of a MatchTable element.
429 unsigned NumElements;
432 /// A bitfield of RecordFlagsBits flags.
435 /// The actual run-time value, if known
438 MatchTableRecord(Optional<unsigned> LabelID_, StringRef EmitStr,
439 unsigned NumElements, unsigned Flags,
440 int64_t RawValue = std::numeric_limits<int64_t>::min())
441 : LabelID(LabelID_.hasValue() ? LabelID_.getValue() : ~0u),
442 EmitStr(EmitStr), NumElements(NumElements), Flags(Flags),
445 assert((!LabelID_.hasValue() || LabelID != ~0u) &&
446 "This value is reserved for non-labels");
448 MatchTableRecord(const MatchTableRecord &Other) = default;
449 MatchTableRecord(MatchTableRecord &&Other) = default;
451 /// Useful if a Match Table Record gets optimized out
452 void turnIntoComment() {
453 Flags |= MTRF_Comment;
454 Flags &= ~MTRF_CommaFollows;
458 /// For Jump Table generation purposes
459 bool operator<(const MatchTableRecord &Other) const {
460 return RawValue < Other.RawValue;
462 int64_t getRawValue() const { return RawValue; }
464 void emit(raw_ostream &OS, bool LineBreakNextAfterThis,
465 const MatchTable &Table) const;
466 unsigned size() const { return NumElements; }
471 /// Holds the contents of a generated MatchTable to enable formatting and the
472 /// necessary index tracking needed to support GIM_Try.
474 /// An unique identifier for the table. The generated table will be named
477 /// The records that make up the table. Also includes comments describing the
478 /// values being emitted and line breaks to format it.
479 std::vector<MatchTableRecord> Contents;
480 /// The currently defined labels.
481 DenseMap<unsigned, unsigned> LabelMap;
482 /// Tracks the sum of MatchTableRecord::NumElements as the table is built.
483 unsigned CurrentSize = 0;
484 /// A unique identifier for a MatchTable label.
485 unsigned CurrentLabelID = 0;
486 /// Determines if the table should be instrumented for rule coverage tracking.
490 static MatchTableRecord LineBreak;
491 static MatchTableRecord Comment(StringRef Comment) {
492 return MatchTableRecord(None, Comment, 0, MatchTableRecord::MTRF_Comment);
494 static MatchTableRecord Opcode(StringRef Opcode, int IndentAdjust = 0) {
495 unsigned ExtraFlags = 0;
496 if (IndentAdjust > 0)
497 ExtraFlags |= MatchTableRecord::MTRF_Indent;
498 if (IndentAdjust < 0)
499 ExtraFlags |= MatchTableRecord::MTRF_Outdent;
501 return MatchTableRecord(None, Opcode, 1,
502 MatchTableRecord::MTRF_CommaFollows | ExtraFlags);
504 static MatchTableRecord NamedValue(StringRef NamedValue) {
505 return MatchTableRecord(None, NamedValue, 1,
506 MatchTableRecord::MTRF_CommaFollows);
508 static MatchTableRecord NamedValue(StringRef NamedValue, int64_t RawValue) {
509 return MatchTableRecord(None, NamedValue, 1,
510 MatchTableRecord::MTRF_CommaFollows, RawValue);
512 static MatchTableRecord NamedValue(StringRef Namespace,
513 StringRef NamedValue) {
514 return MatchTableRecord(None, (Namespace + "::" + NamedValue).str(), 1,
515 MatchTableRecord::MTRF_CommaFollows);
517 static MatchTableRecord NamedValue(StringRef Namespace, StringRef NamedValue,
519 return MatchTableRecord(None, (Namespace + "::" + NamedValue).str(), 1,
520 MatchTableRecord::MTRF_CommaFollows, RawValue);
522 static MatchTableRecord IntValue(int64_t IntValue) {
523 return MatchTableRecord(None, llvm::to_string(IntValue), 1,
524 MatchTableRecord::MTRF_CommaFollows);
526 static MatchTableRecord Label(unsigned LabelID) {
527 return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 0,
528 MatchTableRecord::MTRF_Label |
529 MatchTableRecord::MTRF_Comment |
530 MatchTableRecord::MTRF_LineBreakFollows);
532 static MatchTableRecord JumpTarget(unsigned LabelID) {
533 return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 1,
534 MatchTableRecord::MTRF_JumpTarget |
535 MatchTableRecord::MTRF_Comment |
536 MatchTableRecord::MTRF_CommaFollows);
539 static MatchTable buildTable(ArrayRef<Matcher *> Rules, bool WithCoverage);
541 MatchTable(bool WithCoverage, unsigned ID = 0)
542 : ID(ID), IsWithCoverage(WithCoverage) {}
544 bool isWithCoverage() const { return IsWithCoverage; }
546 void push_back(const MatchTableRecord &Value) {
547 if (Value.Flags & MatchTableRecord::MTRF_Label)
548 defineLabel(Value.LabelID);
549 Contents.push_back(Value);
550 CurrentSize += Value.size();
553 unsigned allocateLabelID() { return CurrentLabelID++; }
555 void defineLabel(unsigned LabelID) {
556 LabelMap.insert(std::make_pair(LabelID, CurrentSize));
559 unsigned getLabelIndex(unsigned LabelID) const {
560 const auto I = LabelMap.find(LabelID);
561 assert(I != LabelMap.end() && "Use of undeclared label");
565 void emitUse(raw_ostream &OS) const { OS << "MatchTable" << ID; }
567 void emitDeclaration(raw_ostream &OS) const {
568 unsigned Indentation = 4;
569 OS << " constexpr static int64_t MatchTable" << ID << "[] = {";
570 LineBreak.emit(OS, true, *this);
571 OS << std::string(Indentation, ' ');
573 for (auto I = Contents.begin(), E = Contents.end(); I != E;
575 bool LineBreakIsNext = false;
576 const auto &NextI = std::next(I);
579 if (NextI->EmitStr == "" &&
580 NextI->Flags == MatchTableRecord::MTRF_LineBreakFollows)
581 LineBreakIsNext = true;
584 if (I->Flags & MatchTableRecord::MTRF_Indent)
587 I->emit(OS, LineBreakIsNext, *this);
588 if (I->Flags & MatchTableRecord::MTRF_LineBreakFollows)
589 OS << std::string(Indentation, ' ');
591 if (I->Flags & MatchTableRecord::MTRF_Outdent)
598 MatchTableRecord MatchTable::LineBreak = {
599 None, "" /* Emit String */, 0 /* Elements */,
600 MatchTableRecord::MTRF_LineBreakFollows};
602 void MatchTableRecord::emit(raw_ostream &OS, bool LineBreakIsNextAfterThis,
603 const MatchTable &Table) const {
604 bool UseLineComment =
605 LineBreakIsNextAfterThis | (Flags & MTRF_LineBreakFollows);
606 if (Flags & (MTRF_JumpTarget | MTRF_CommaFollows))
607 UseLineComment = false;
609 if (Flags & MTRF_Comment)
610 OS << (UseLineComment ? "// " : "/*");
613 if (Flags & MTRF_Label)
614 OS << ": @" << Table.getLabelIndex(LabelID);
616 if (Flags & MTRF_Comment && !UseLineComment)
619 if (Flags & MTRF_JumpTarget) {
620 if (Flags & MTRF_Comment)
622 OS << Table.getLabelIndex(LabelID);
625 if (Flags & MTRF_CommaFollows) {
627 if (!LineBreakIsNextAfterThis && !(Flags & MTRF_LineBreakFollows))
631 if (Flags & MTRF_LineBreakFollows)
635 MatchTable &operator<<(MatchTable &Table, const MatchTableRecord &Value) {
636 Table.push_back(Value);
640 //===- Matchers -----------------------------------------------------------===//
642 class OperandMatcher;
644 class PredicateMatcher;
649 virtual ~Matcher() = default;
650 virtual void optimize() {}
651 virtual void emit(MatchTable &Table) = 0;
653 virtual bool hasFirstCondition() const = 0;
654 virtual const PredicateMatcher &getFirstCondition() const = 0;
655 virtual std::unique_ptr<PredicateMatcher> popFirstCondition() = 0;
658 MatchTable MatchTable::buildTable(ArrayRef<Matcher *> Rules,
660 MatchTable Table(WithCoverage);
661 for (Matcher *Rule : Rules)
664 return Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
667 class GroupMatcher final : public Matcher {
668 /// Conditions that form a common prefix of all the matchers contained.
669 SmallVector<std::unique_ptr<PredicateMatcher>, 1> Conditions;
671 /// All the nested matchers, sharing a common prefix.
672 std::vector<Matcher *> Matchers;
674 /// An owning collection for any auxiliary matchers created while optimizing
675 /// nested matchers contained.
676 std::vector<std::unique_ptr<Matcher>> MatcherStorage;
679 /// Add a matcher to the collection of nested matchers if it meets the
680 /// requirements, and return true. If it doesn't, do nothing and return false.
682 /// Expected to preserve its argument, so it could be moved out later on.
683 bool addMatcher(Matcher &Candidate);
685 /// Mark the matcher as fully-built and ensure any invariants expected by both
686 /// optimize() and emit(...) methods. Generally, both sequences of calls
687 /// are expected to lead to a sensible result:
689 /// addMatcher(...)*; finalize(); optimize(); emit(...); and
690 /// addMatcher(...)*; finalize(); emit(...);
694 /// addMatcher(...)*; finalize(); { optimize()*; emit(...); }*
696 /// Multiple calls to optimize() are expected to be handled gracefully, though
697 /// optimize() is not expected to be idempotent. Multiple calls to finalize()
698 /// aren't generally supported. emit(...) is expected to be non-mutating and
699 /// producing the exact same results upon repeated calls.
701 /// addMatcher() calls after the finalize() call are not supported.
703 /// finalize() and optimize() are both allowed to mutate the contained
704 /// matchers, so moving them out after finalize() is not supported.
706 void optimize() override;
707 void emit(MatchTable &Table) override;
709 /// Could be used to move out the matchers added previously, unless finalize()
710 /// has been already called. If any of the matchers are moved out, the group
711 /// becomes safe to destroy, but not safe to re-use for anything else.
712 iterator_range<std::vector<Matcher *>::iterator> matchers() {
713 return make_range(Matchers.begin(), Matchers.end());
715 size_t size() const { return Matchers.size(); }
716 bool empty() const { return Matchers.empty(); }
718 std::unique_ptr<PredicateMatcher> popFirstCondition() override {
719 assert(!Conditions.empty() &&
720 "Trying to pop a condition from a condition-less group");
721 std::unique_ptr<PredicateMatcher> P = std::move(Conditions.front());
722 Conditions.erase(Conditions.begin());
725 const PredicateMatcher &getFirstCondition() const override {
726 assert(!Conditions.empty() &&
727 "Trying to get a condition from a condition-less group");
728 return *Conditions.front();
730 bool hasFirstCondition() const override { return !Conditions.empty(); }
733 /// See if a candidate matcher could be added to this group solely by
734 /// analyzing its first condition.
735 bool candidateConditionMatches(const PredicateMatcher &Predicate) const;
738 class SwitchMatcher : public Matcher {
739 /// All the nested matchers, representing distinct switch-cases. The first
740 /// conditions (as Matcher::getFirstCondition() reports) of all the nested
741 /// matchers must share the same type and path to a value they check, in other
742 /// words, be isIdenticalDownToValue, but have different values they check
744 std::vector<Matcher *> Matchers;
746 /// The representative condition, with a type and a path (InsnVarID and OpIdx
747 /// in most cases) shared by all the matchers contained.
748 std::unique_ptr<PredicateMatcher> Condition = nullptr;
750 /// Temporary set used to check that the case values don't repeat within the
752 std::set<MatchTableRecord> Values;
754 /// An owning collection for any auxiliary matchers created while optimizing
755 /// nested matchers contained.
756 std::vector<std::unique_ptr<Matcher>> MatcherStorage;
759 bool addMatcher(Matcher &Candidate);
762 void emit(MatchTable &Table) override;
764 iterator_range<std::vector<Matcher *>::iterator> matchers() {
765 return make_range(Matchers.begin(), Matchers.end());
767 size_t size() const { return Matchers.size(); }
768 bool empty() const { return Matchers.empty(); }
770 std::unique_ptr<PredicateMatcher> popFirstCondition() override {
771 // SwitchMatcher doesn't have a common first condition for its cases, as all
772 // the cases only share a kind of a value (a type and a path to it) they
773 // match, but deliberately differ in the actual value they match.
774 llvm_unreachable("Trying to pop a condition from a condition-less group");
776 const PredicateMatcher &getFirstCondition() const override {
777 llvm_unreachable("Trying to pop a condition from a condition-less group");
779 bool hasFirstCondition() const override { return false; }
782 /// See if the predicate type has a Switch-implementation for it.
783 static bool isSupportedPredicateType(const PredicateMatcher &Predicate);
785 bool candidateConditionMatches(const PredicateMatcher &Predicate) const;
788 static void emitPredicateSpecificOpcodes(const PredicateMatcher &P,
792 /// Generates code to check that a match rule matches.
793 class RuleMatcher : public Matcher {
795 using ActionList = std::list<std::unique_ptr<MatchAction>>;
796 using action_iterator = ActionList::iterator;
799 /// A list of matchers that all need to succeed for the current rule to match.
800 /// FIXME: This currently supports a single match position but could be
801 /// extended to support multiple positions to support div/rem fusion or
802 /// load-multiple instructions.
803 using MatchersTy = std::vector<std::unique_ptr<InstructionMatcher>> ;
806 /// A list of actions that need to be taken when all predicates in this rule
810 using DefinedInsnVariablesMap = std::map<InstructionMatcher *, unsigned>;
812 /// A map of instruction matchers to the local variables
813 DefinedInsnVariablesMap InsnVariableIDs;
815 using MutatableInsnSet = SmallPtrSet<InstructionMatcher *, 4>;
817 // The set of instruction matchers that have not yet been claimed for mutation
819 MutatableInsnSet MutatableInsns;
821 /// A map of named operands defined by the matchers that may be referenced by
823 StringMap<OperandMatcher *> DefinedOperands;
825 /// ID for the next instruction variable defined with implicitlyDefineInsnVar()
826 unsigned NextInsnVarID;
828 /// ID for the next output instruction allocated with allocateOutputInsnID()
829 unsigned NextOutputInsnID;
831 /// ID for the next temporary register ID allocated with allocateTempRegID()
832 unsigned NextTempRegID;
834 std::vector<Record *> RequiredFeatures;
835 std::vector<std::unique_ptr<PredicateMatcher>> EpilogueMatchers;
837 ArrayRef<SMLoc> SrcLoc;
839 typedef std::tuple<Record *, unsigned, unsigned>
840 DefinedComplexPatternSubOperand;
841 typedef StringMap<DefinedComplexPatternSubOperand>
842 DefinedComplexPatternSubOperandMap;
843 /// A map of Symbolic Names to ComplexPattern sub-operands.
844 DefinedComplexPatternSubOperandMap ComplexSubOperands;
847 static uint64_t NextRuleID;
850 RuleMatcher(ArrayRef<SMLoc> SrcLoc)
851 : Matchers(), Actions(), InsnVariableIDs(), MutatableInsns(),
852 DefinedOperands(), NextInsnVarID(0), NextOutputInsnID(0),
853 NextTempRegID(0), SrcLoc(SrcLoc), ComplexSubOperands(),
854 RuleID(NextRuleID++) {}
855 RuleMatcher(RuleMatcher &&Other) = default;
856 RuleMatcher &operator=(RuleMatcher &&Other) = default;
858 uint64_t getRuleID() const { return RuleID; }
860 InstructionMatcher &addInstructionMatcher(StringRef SymbolicName);
861 void addRequiredFeature(Record *Feature);
862 const std::vector<Record *> &getRequiredFeatures() const;
864 template <class Kind, class... Args> Kind &addAction(Args &&... args);
865 template <class Kind, class... Args>
866 action_iterator insertAction(action_iterator InsertPt, Args &&... args);
868 /// Define an instruction without emitting any code to do so.
869 unsigned implicitlyDefineInsnVar(InstructionMatcher &Matcher);
871 unsigned getInsnVarID(InstructionMatcher &InsnMatcher) const;
872 DefinedInsnVariablesMap::const_iterator defined_insn_vars_begin() const {
873 return InsnVariableIDs.begin();
875 DefinedInsnVariablesMap::const_iterator defined_insn_vars_end() const {
876 return InsnVariableIDs.end();
878 iterator_range<typename DefinedInsnVariablesMap::const_iterator>
879 defined_insn_vars() const {
880 return make_range(defined_insn_vars_begin(), defined_insn_vars_end());
883 MutatableInsnSet::const_iterator mutatable_insns_begin() const {
884 return MutatableInsns.begin();
886 MutatableInsnSet::const_iterator mutatable_insns_end() const {
887 return MutatableInsns.end();
889 iterator_range<typename MutatableInsnSet::const_iterator>
890 mutatable_insns() const {
891 return make_range(mutatable_insns_begin(), mutatable_insns_end());
893 void reserveInsnMatcherForMutation(InstructionMatcher *InsnMatcher) {
894 bool R = MutatableInsns.erase(InsnMatcher);
895 assert(R && "Reserving a mutatable insn that isn't available");
899 action_iterator actions_begin() { return Actions.begin(); }
900 action_iterator actions_end() { return Actions.end(); }
901 iterator_range<action_iterator> actions() {
902 return make_range(actions_begin(), actions_end());
905 void defineOperand(StringRef SymbolicName, OperandMatcher &OM);
907 Error defineComplexSubOperand(StringRef SymbolicName, Record *ComplexPattern,
908 unsigned RendererID, unsigned SubOperandID) {
909 if (ComplexSubOperands.count(SymbolicName))
911 "Complex suboperand referenced more than once (Operand: " +
914 ComplexSubOperands[SymbolicName] =
915 std::make_tuple(ComplexPattern, RendererID, SubOperandID);
917 return Error::success();
920 Optional<DefinedComplexPatternSubOperand>
921 getComplexSubOperand(StringRef SymbolicName) const {
922 const auto &I = ComplexSubOperands.find(SymbolicName);
923 if (I == ComplexSubOperands.end())
928 InstructionMatcher &getInstructionMatcher(StringRef SymbolicName) const;
929 const OperandMatcher &getOperandMatcher(StringRef Name) const;
931 void optimize() override;
932 void emit(MatchTable &Table) override;
934 /// Compare the priority of this object and B.
936 /// Returns true if this object is more important than B.
937 bool isHigherPriorityThan(const RuleMatcher &B) const;
939 /// Report the maximum number of temporary operands needed by the rule
941 unsigned countRendererFns() const;
943 std::unique_ptr<PredicateMatcher> popFirstCondition() override;
944 const PredicateMatcher &getFirstCondition() const override;
945 LLTCodeGen getFirstConditionAsRootType();
946 bool hasFirstCondition() const override;
947 unsigned getNumOperands() const;
948 StringRef getOpcode() const;
950 // FIXME: Remove this as soon as possible
951 InstructionMatcher &insnmatchers_front() const { return *Matchers.front(); }
953 unsigned allocateOutputInsnID() { return NextOutputInsnID++; }
954 unsigned allocateTempRegID() { return NextTempRegID++; }
956 iterator_range<MatchersTy::iterator> insnmatchers() {
957 return make_range(Matchers.begin(), Matchers.end());
959 bool insnmatchers_empty() const { return Matchers.empty(); }
960 void insnmatchers_pop_front() { Matchers.erase(Matchers.begin()); }
963 uint64_t RuleMatcher::NextRuleID = 0;
965 using action_iterator = RuleMatcher::action_iterator;
967 template <class PredicateTy> class PredicateListMatcher {
969 /// Template instantiations should specialize this to return a string to use
970 /// for the comment emitted when there are no predicates.
971 std::string getNoPredicateComment() const;
974 using PredicatesTy = std::deque<std::unique_ptr<PredicateTy>>;
975 PredicatesTy Predicates;
977 /// Track if the list of predicates was manipulated by one of the optimization
979 bool Optimized = false;
982 /// Construct a new predicate and add it to the matcher.
983 template <class Kind, class... Args>
984 Optional<Kind *> addPredicate(Args &&... args);
986 typename PredicatesTy::iterator predicates_begin() {
987 return Predicates.begin();
989 typename PredicatesTy::iterator predicates_end() {
990 return Predicates.end();
992 iterator_range<typename PredicatesTy::iterator> predicates() {
993 return make_range(predicates_begin(), predicates_end());
995 typename PredicatesTy::size_type predicates_size() const {
996 return Predicates.size();
998 bool predicates_empty() const { return Predicates.empty(); }
1000 std::unique_ptr<PredicateTy> predicates_pop_front() {
1001 std::unique_ptr<PredicateTy> Front = std::move(Predicates.front());
1002 Predicates.pop_front();
1007 void prependPredicate(std::unique_ptr<PredicateTy> &&Predicate) {
1008 Predicates.push_front(std::move(Predicate));
1011 void eraseNullPredicates() {
1013 std::stable_partition(Predicates.begin(), Predicates.end(),
1014 std::logical_not<std::unique_ptr<PredicateTy>>());
1015 if (NewEnd != Predicates.begin()) {
1016 Predicates.erase(Predicates.begin(), NewEnd);
1021 /// Emit MatchTable opcodes that tests whether all the predicates are met.
1022 template <class... Args>
1023 void emitPredicateListOpcodes(MatchTable &Table, Args &&... args) {
1024 if (Predicates.empty() && !Optimized) {
1025 Table << MatchTable::Comment(getNoPredicateComment())
1026 << MatchTable::LineBreak;
1030 for (const auto &Predicate : predicates())
1031 Predicate->emitPredicateOpcodes(Table, std::forward<Args>(args)...);
1035 class PredicateMatcher {
1037 /// This enum is used for RTTI and also defines the priority that is given to
1038 /// the predicate when generating the matcher code. Kinds with higher priority
1039 /// must be tested first.
1041 /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter
1042 /// but OPM_Int must have priority over OPM_RegBank since constant integers
1043 /// are represented by a virtual register defined by a G_CONSTANT instruction.
1045 /// Note: The relative priority between IPM_ and OPM_ does not matter, they
1046 /// are currently not compared between each other.
1047 enum PredicateKind {
1051 IPM_AtomicOrderingMMO,
1053 IPM_MemoryVsLLTSize,
1054 IPM_MemoryAddressSpace,
1055 IPM_GenericPredicate,
1074 PredicateMatcher(PredicateKind Kind, unsigned InsnVarID, unsigned OpIdx = ~0)
1075 : Kind(Kind), InsnVarID(InsnVarID), OpIdx(OpIdx) {}
1077 unsigned getInsnVarID() const { return InsnVarID; }
1078 unsigned getOpIdx() const { return OpIdx; }
1080 virtual ~PredicateMatcher() = default;
1081 /// Emit MatchTable opcodes that check the predicate for the given operand.
1082 virtual void emitPredicateOpcodes(MatchTable &Table,
1083 RuleMatcher &Rule) const = 0;
1085 PredicateKind getKind() const { return Kind; }
1087 virtual bool isIdentical(const PredicateMatcher &B) const {
1088 return B.getKind() == getKind() && InsnVarID == B.InsnVarID &&
1092 virtual bool isIdenticalDownToValue(const PredicateMatcher &B) const {
1093 return hasValue() && PredicateMatcher::isIdentical(B);
1096 virtual MatchTableRecord getValue() const {
1097 assert(hasValue() && "Can not get a value of a value-less predicate!");
1098 llvm_unreachable("Not implemented yet");
1100 virtual bool hasValue() const { return false; }
1102 /// Report the maximum number of temporary operands needed by the predicate
1104 virtual unsigned countRendererFns() const { return 0; }
1107 /// Generates code to check a predicate of an operand.
1109 /// Typical predicates include:
1110 /// * Operand is a particular register.
1111 /// * Operand is assigned a particular register bank.
1112 /// * Operand is an MBB.
1113 class OperandPredicateMatcher : public PredicateMatcher {
1115 OperandPredicateMatcher(PredicateKind Kind, unsigned InsnVarID,
1117 : PredicateMatcher(Kind, InsnVarID, OpIdx) {}
1118 virtual ~OperandPredicateMatcher() {}
1120 /// Compare the priority of this object and B.
1122 /// Returns true if this object is more important than B.
1123 virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const;
1128 PredicateListMatcher<OperandPredicateMatcher>::getNoPredicateComment() const {
1129 return "No operand predicates";
1132 /// Generates code to check that a register operand is defined by the same exact
1134 class SameOperandMatcher : public OperandPredicateMatcher {
1135 std::string MatchingName;
1138 SameOperandMatcher(unsigned InsnVarID, unsigned OpIdx, StringRef MatchingName)
1139 : OperandPredicateMatcher(OPM_SameOperand, InsnVarID, OpIdx),
1140 MatchingName(MatchingName) {}
1142 static bool classof(const PredicateMatcher *P) {
1143 return P->getKind() == OPM_SameOperand;
1146 void emitPredicateOpcodes(MatchTable &Table,
1147 RuleMatcher &Rule) const override;
1149 bool isIdentical(const PredicateMatcher &B) const override {
1150 return OperandPredicateMatcher::isIdentical(B) &&
1151 MatchingName == cast<SameOperandMatcher>(&B)->MatchingName;
1155 /// Generates code to check that an operand is a particular LLT.
1156 class LLTOperandMatcher : public OperandPredicateMatcher {
1161 static std::map<LLTCodeGen, unsigned> TypeIDValues;
1163 static void initTypeIDValuesMap() {
1164 TypeIDValues.clear();
1167 for (const LLTCodeGen LLTy : KnownTypes)
1168 TypeIDValues[LLTy] = ID++;
1171 LLTOperandMatcher(unsigned InsnVarID, unsigned OpIdx, const LLTCodeGen &Ty)
1172 : OperandPredicateMatcher(OPM_LLT, InsnVarID, OpIdx), Ty(Ty) {
1173 KnownTypes.insert(Ty);
1176 static bool classof(const PredicateMatcher *P) {
1177 return P->getKind() == OPM_LLT;
1179 bool isIdentical(const PredicateMatcher &B) const override {
1180 return OperandPredicateMatcher::isIdentical(B) &&
1181 Ty == cast<LLTOperandMatcher>(&B)->Ty;
1183 MatchTableRecord getValue() const override {
1184 const auto VI = TypeIDValues.find(Ty);
1185 if (VI == TypeIDValues.end())
1186 return MatchTable::NamedValue(getTy().getCxxEnumValue());
1187 return MatchTable::NamedValue(getTy().getCxxEnumValue(), VI->second);
1189 bool hasValue() const override {
1190 if (TypeIDValues.size() != KnownTypes.size())
1191 initTypeIDValuesMap();
1192 return TypeIDValues.count(Ty);
1195 LLTCodeGen getTy() const { return Ty; }
1197 void emitPredicateOpcodes(MatchTable &Table,
1198 RuleMatcher &Rule) const override {
1199 Table << MatchTable::Opcode("GIM_CheckType") << MatchTable::Comment("MI")
1200 << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
1201 << MatchTable::IntValue(OpIdx) << MatchTable::Comment("Type")
1202 << getValue() << MatchTable::LineBreak;
1206 std::map<LLTCodeGen, unsigned> LLTOperandMatcher::TypeIDValues;
1208 /// Generates code to check that an operand is a pointer to any address space.
1210 /// In SelectionDAG, the types did not describe pointers or address spaces. As a
1211 /// result, iN is used to describe a pointer of N bits to any address space and
1212 /// PatFrag predicates are typically used to constrain the address space. There's
1213 /// no reliable means to derive the missing type information from the pattern so
1214 /// imported rules must test the components of a pointer separately.
1216 /// If SizeInBits is zero, then the pointer size will be obtained from the
1218 class PointerToAnyOperandMatcher : public OperandPredicateMatcher {
1220 unsigned SizeInBits;
1223 PointerToAnyOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1224 unsigned SizeInBits)
1225 : OperandPredicateMatcher(OPM_PointerToAny, InsnVarID, OpIdx),
1226 SizeInBits(SizeInBits) {}
1228 static bool classof(const OperandPredicateMatcher *P) {
1229 return P->getKind() == OPM_PointerToAny;
1232 void emitPredicateOpcodes(MatchTable &Table,
1233 RuleMatcher &Rule) const override {
1234 Table << MatchTable::Opcode("GIM_CheckPointerToAny")
1235 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1236 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1237 << MatchTable::Comment("SizeInBits")
1238 << MatchTable::IntValue(SizeInBits) << MatchTable::LineBreak;
1242 /// Generates code to check that an operand is a particular target constant.
1243 class ComplexPatternOperandMatcher : public OperandPredicateMatcher {
1245 const OperandMatcher &Operand;
1246 const Record &TheDef;
1248 unsigned getAllocatedTemporariesBaseID() const;
1251 bool isIdentical(const PredicateMatcher &B) const override { return false; }
1253 ComplexPatternOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1254 const OperandMatcher &Operand,
1255 const Record &TheDef)
1256 : OperandPredicateMatcher(OPM_ComplexPattern, InsnVarID, OpIdx),
1257 Operand(Operand), TheDef(TheDef) {}
1259 static bool classof(const PredicateMatcher *P) {
1260 return P->getKind() == OPM_ComplexPattern;
1263 void emitPredicateOpcodes(MatchTable &Table,
1264 RuleMatcher &Rule) const override {
1265 unsigned ID = getAllocatedTemporariesBaseID();
1266 Table << MatchTable::Opcode("GIM_CheckComplexPattern")
1267 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1268 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1269 << MatchTable::Comment("Renderer") << MatchTable::IntValue(ID)
1270 << MatchTable::NamedValue(("GICP_" + TheDef.getName()).str())
1271 << MatchTable::LineBreak;
1274 unsigned countRendererFns() const override {
1279 /// Generates code to check that an operand is in a particular register bank.
1280 class RegisterBankOperandMatcher : public OperandPredicateMatcher {
1282 const CodeGenRegisterClass &RC;
1285 RegisterBankOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1286 const CodeGenRegisterClass &RC)
1287 : OperandPredicateMatcher(OPM_RegBank, InsnVarID, OpIdx), RC(RC) {}
1289 bool isIdentical(const PredicateMatcher &B) const override {
1290 return OperandPredicateMatcher::isIdentical(B) &&
1291 RC.getDef() == cast<RegisterBankOperandMatcher>(&B)->RC.getDef();
1294 static bool classof(const PredicateMatcher *P) {
1295 return P->getKind() == OPM_RegBank;
1298 void emitPredicateOpcodes(MatchTable &Table,
1299 RuleMatcher &Rule) const override {
1300 Table << MatchTable::Opcode("GIM_CheckRegBankForClass")
1301 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1302 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1303 << MatchTable::Comment("RC")
1304 << MatchTable::NamedValue(RC.getQualifiedName() + "RegClassID")
1305 << MatchTable::LineBreak;
1309 /// Generates code to check that an operand is a basic block.
1310 class MBBOperandMatcher : public OperandPredicateMatcher {
1312 MBBOperandMatcher(unsigned InsnVarID, unsigned OpIdx)
1313 : OperandPredicateMatcher(OPM_MBB, InsnVarID, OpIdx) {}
1315 static bool classof(const PredicateMatcher *P) {
1316 return P->getKind() == OPM_MBB;
1319 void emitPredicateOpcodes(MatchTable &Table,
1320 RuleMatcher &Rule) const override {
1321 Table << MatchTable::Opcode("GIM_CheckIsMBB") << MatchTable::Comment("MI")
1322 << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
1323 << MatchTable::IntValue(OpIdx) << MatchTable::LineBreak;
1327 /// Generates code to check that an operand is a G_CONSTANT with a particular
1329 class ConstantIntOperandMatcher : public OperandPredicateMatcher {
1334 ConstantIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value)
1335 : OperandPredicateMatcher(OPM_Int, InsnVarID, OpIdx), Value(Value) {}
1337 bool isIdentical(const PredicateMatcher &B) const override {
1338 return OperandPredicateMatcher::isIdentical(B) &&
1339 Value == cast<ConstantIntOperandMatcher>(&B)->Value;
1342 static bool classof(const PredicateMatcher *P) {
1343 return P->getKind() == OPM_Int;
1346 void emitPredicateOpcodes(MatchTable &Table,
1347 RuleMatcher &Rule) const override {
1348 Table << MatchTable::Opcode("GIM_CheckConstantInt")
1349 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1350 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1351 << MatchTable::IntValue(Value) << MatchTable::LineBreak;
1355 /// Generates code to check that an operand is a raw int (where MO.isImm() or
1356 /// MO.isCImm() is true).
1357 class LiteralIntOperandMatcher : public OperandPredicateMatcher {
1362 LiteralIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value)
1363 : OperandPredicateMatcher(OPM_LiteralInt, InsnVarID, OpIdx),
1366 bool isIdentical(const PredicateMatcher &B) const override {
1367 return OperandPredicateMatcher::isIdentical(B) &&
1368 Value == cast<LiteralIntOperandMatcher>(&B)->Value;
1371 static bool classof(const PredicateMatcher *P) {
1372 return P->getKind() == OPM_LiteralInt;
1375 void emitPredicateOpcodes(MatchTable &Table,
1376 RuleMatcher &Rule) const override {
1377 Table << MatchTable::Opcode("GIM_CheckLiteralInt")
1378 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1379 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1380 << MatchTable::IntValue(Value) << MatchTable::LineBreak;
1384 /// Generates code to check that an operand is an intrinsic ID.
1385 class IntrinsicIDOperandMatcher : public OperandPredicateMatcher {
1387 const CodeGenIntrinsic *II;
1390 IntrinsicIDOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1391 const CodeGenIntrinsic *II)
1392 : OperandPredicateMatcher(OPM_IntrinsicID, InsnVarID, OpIdx), II(II) {}
1394 bool isIdentical(const PredicateMatcher &B) const override {
1395 return OperandPredicateMatcher::isIdentical(B) &&
1396 II == cast<IntrinsicIDOperandMatcher>(&B)->II;
1399 static bool classof(const PredicateMatcher *P) {
1400 return P->getKind() == OPM_IntrinsicID;
1403 void emitPredicateOpcodes(MatchTable &Table,
1404 RuleMatcher &Rule) const override {
1405 Table << MatchTable::Opcode("GIM_CheckIntrinsicID")
1406 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1407 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1408 << MatchTable::NamedValue("Intrinsic::" + II->EnumName)
1409 << MatchTable::LineBreak;
1413 /// Generates code to check that a set of predicates match for a particular
1415 class OperandMatcher : public PredicateListMatcher<OperandPredicateMatcher> {
1417 InstructionMatcher &Insn;
1419 std::string SymbolicName;
1421 /// The index of the first temporary variable allocated to this operand. The
1422 /// number of allocated temporaries can be found with
1423 /// countRendererFns().
1424 unsigned AllocatedTemporariesBaseID;
1427 OperandMatcher(InstructionMatcher &Insn, unsigned OpIdx,
1428 const std::string &SymbolicName,
1429 unsigned AllocatedTemporariesBaseID)
1430 : Insn(Insn), OpIdx(OpIdx), SymbolicName(SymbolicName),
1431 AllocatedTemporariesBaseID(AllocatedTemporariesBaseID) {}
1433 bool hasSymbolicName() const { return !SymbolicName.empty(); }
1434 const StringRef getSymbolicName() const { return SymbolicName; }
1435 void setSymbolicName(StringRef Name) {
1436 assert(SymbolicName.empty() && "Operand already has a symbolic name");
1437 SymbolicName = Name;
1440 /// Construct a new operand predicate and add it to the matcher.
1441 template <class Kind, class... Args>
1442 Optional<Kind *> addPredicate(Args &&... args) {
1443 if (isSameAsAnotherOperand())
1445 Predicates.emplace_back(llvm::make_unique<Kind>(
1446 getInsnVarID(), getOpIdx(), std::forward<Args>(args)...));
1447 return static_cast<Kind *>(Predicates.back().get());
1450 unsigned getOpIdx() const { return OpIdx; }
1451 unsigned getInsnVarID() const;
1453 std::string getOperandExpr(unsigned InsnVarID) const {
1454 return "State.MIs[" + llvm::to_string(InsnVarID) + "]->getOperand(" +
1455 llvm::to_string(OpIdx) + ")";
1458 InstructionMatcher &getInstructionMatcher() const { return Insn; }
1460 Error addTypeCheckPredicate(const TypeSetByHwMode &VTy,
1461 bool OperandIsAPointer);
1463 /// Emit MatchTable opcodes that test whether the instruction named in
1464 /// InsnVarID matches all the predicates and all the operands.
1465 void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) {
1467 std::string Comment;
1468 raw_string_ostream CommentOS(Comment);
1469 CommentOS << "MIs[" << getInsnVarID() << "] ";
1470 if (SymbolicName.empty())
1471 CommentOS << "Operand " << OpIdx;
1473 CommentOS << SymbolicName;
1474 Table << MatchTable::Comment(CommentOS.str()) << MatchTable::LineBreak;
1477 emitPredicateListOpcodes(Table, Rule);
1480 /// Compare the priority of this object and B.
1482 /// Returns true if this object is more important than B.
1483 bool isHigherPriorityThan(OperandMatcher &B) {
1484 // Operand matchers involving more predicates have higher priority.
1485 if (predicates_size() > B.predicates_size())
1487 if (predicates_size() < B.predicates_size())
1490 // This assumes that predicates are added in a consistent order.
1491 for (auto &&Predicate : zip(predicates(), B.predicates())) {
1492 if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate)))
1494 if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate)))
1501 /// Report the maximum number of temporary operands needed by the operand
1503 unsigned countRendererFns() {
1504 return std::accumulate(
1505 predicates().begin(), predicates().end(), 0,
1507 const std::unique_ptr<OperandPredicateMatcher> &Predicate) {
1508 return A + Predicate->countRendererFns();
1512 unsigned getAllocatedTemporariesBaseID() const {
1513 return AllocatedTemporariesBaseID;
1516 bool isSameAsAnotherOperand() {
1517 for (const auto &Predicate : predicates())
1518 if (isa<SameOperandMatcher>(Predicate))
1524 Error OperandMatcher::addTypeCheckPredicate(const TypeSetByHwMode &VTy,
1525 bool OperandIsAPointer) {
1526 if (!VTy.isMachineValueType())
1527 return failedImport("unsupported typeset");
1529 if (VTy.getMachineValueType() == MVT::iPTR && OperandIsAPointer) {
1530 addPredicate<PointerToAnyOperandMatcher>(0);
1531 return Error::success();
1534 auto OpTyOrNone = MVTToLLT(VTy.getMachineValueType().SimpleTy);
1536 return failedImport("unsupported type");
1538 if (OperandIsAPointer)
1539 addPredicate<PointerToAnyOperandMatcher>(OpTyOrNone->get().getSizeInBits());
1540 else if (VTy.isPointer())
1541 addPredicate<LLTOperandMatcher>(LLT::pointer(VTy.getPtrAddrSpace(),
1542 OpTyOrNone->get().getSizeInBits()));
1544 addPredicate<LLTOperandMatcher>(*OpTyOrNone);
1545 return Error::success();
1548 unsigned ComplexPatternOperandMatcher::getAllocatedTemporariesBaseID() const {
1549 return Operand.getAllocatedTemporariesBaseID();
1552 /// Generates code to check a predicate on an instruction.
1554 /// Typical predicates include:
1555 /// * The opcode of the instruction is a particular value.
1556 /// * The nsw/nuw flag is/isn't set.
1557 class InstructionPredicateMatcher : public PredicateMatcher {
1559 InstructionPredicateMatcher(PredicateKind Kind, unsigned InsnVarID)
1560 : PredicateMatcher(Kind, InsnVarID) {}
1561 virtual ~InstructionPredicateMatcher() {}
1563 /// Compare the priority of this object and B.
1565 /// Returns true if this object is more important than B.
1567 isHigherPriorityThan(const InstructionPredicateMatcher &B) const {
1568 return Kind < B.Kind;
1574 PredicateListMatcher<PredicateMatcher>::getNoPredicateComment() const {
1575 return "No instruction predicates";
1578 /// Generates code to check the opcode of an instruction.
1579 class InstructionOpcodeMatcher : public InstructionPredicateMatcher {
1581 const CodeGenInstruction *I;
1583 static DenseMap<const CodeGenInstruction *, unsigned> OpcodeValues;
1586 static void initOpcodeValuesMap(const CodeGenTarget &Target) {
1587 OpcodeValues.clear();
1589 unsigned OpcodeValue = 0;
1590 for (const CodeGenInstruction *I : Target.getInstructionsByEnumValue())
1591 OpcodeValues[I] = OpcodeValue++;
1594 InstructionOpcodeMatcher(unsigned InsnVarID, const CodeGenInstruction *I)
1595 : InstructionPredicateMatcher(IPM_Opcode, InsnVarID), I(I) {}
1597 static bool classof(const PredicateMatcher *P) {
1598 return P->getKind() == IPM_Opcode;
1601 bool isIdentical(const PredicateMatcher &B) const override {
1602 return InstructionPredicateMatcher::isIdentical(B) &&
1603 I == cast<InstructionOpcodeMatcher>(&B)->I;
1605 MatchTableRecord getValue() const override {
1606 const auto VI = OpcodeValues.find(I);
1607 if (VI != OpcodeValues.end())
1608 return MatchTable::NamedValue(I->Namespace, I->TheDef->getName(),
1610 return MatchTable::NamedValue(I->Namespace, I->TheDef->getName());
1612 bool hasValue() const override { return OpcodeValues.count(I); }
1614 void emitPredicateOpcodes(MatchTable &Table,
1615 RuleMatcher &Rule) const override {
1616 Table << MatchTable::Opcode("GIM_CheckOpcode") << MatchTable::Comment("MI")
1617 << MatchTable::IntValue(InsnVarID) << getValue()
1618 << MatchTable::LineBreak;
1621 /// Compare the priority of this object and B.
1623 /// Returns true if this object is more important than B.
1625 isHigherPriorityThan(const InstructionPredicateMatcher &B) const override {
1626 if (InstructionPredicateMatcher::isHigherPriorityThan(B))
1628 if (B.InstructionPredicateMatcher::isHigherPriorityThan(*this))
1631 // Prioritize opcodes for cosmetic reasons in the generated source. Although
1632 // this is cosmetic at the moment, we may want to drive a similar ordering
1633 // using instruction frequency information to improve compile time.
1634 if (const InstructionOpcodeMatcher *BO =
1635 dyn_cast<InstructionOpcodeMatcher>(&B))
1636 return I->TheDef->getName() < BO->I->TheDef->getName();
1641 bool isConstantInstruction() const {
1642 return I->TheDef->getName() == "G_CONSTANT";
1645 StringRef getOpcode() const { return I->TheDef->getName(); }
1646 unsigned getNumOperands() const { return I->Operands.size(); }
1648 StringRef getOperandType(unsigned OpIdx) const {
1649 return I->Operands[OpIdx].OperandType;
1653 DenseMap<const CodeGenInstruction *, unsigned>
1654 InstructionOpcodeMatcher::OpcodeValues;
1656 class InstructionNumOperandsMatcher final : public InstructionPredicateMatcher {
1657 unsigned NumOperands = 0;
1660 InstructionNumOperandsMatcher(unsigned InsnVarID, unsigned NumOperands)
1661 : InstructionPredicateMatcher(IPM_NumOperands, InsnVarID),
1662 NumOperands(NumOperands) {}
1664 static bool classof(const PredicateMatcher *P) {
1665 return P->getKind() == IPM_NumOperands;
1668 bool isIdentical(const PredicateMatcher &B) const override {
1669 return InstructionPredicateMatcher::isIdentical(B) &&
1670 NumOperands == cast<InstructionNumOperandsMatcher>(&B)->NumOperands;
1673 void emitPredicateOpcodes(MatchTable &Table,
1674 RuleMatcher &Rule) const override {
1675 Table << MatchTable::Opcode("GIM_CheckNumOperands")
1676 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1677 << MatchTable::Comment("Expected")
1678 << MatchTable::IntValue(NumOperands) << MatchTable::LineBreak;
1682 /// Generates code to check that this instruction is a constant whose value
1683 /// meets an immediate predicate.
1685 /// Immediates are slightly odd since they are typically used like an operand
1686 /// but are represented as an operator internally. We typically write simm8:$src
1687 /// in a tablegen pattern, but this is just syntactic sugar for
1688 /// (imm:i32)<<P:Predicate_simm8>>:$imm which more directly describes the nodes
1689 /// that will be matched and the predicate (which is attached to the imm
1690 /// operator) that will be tested. In SelectionDAG this describes a
1691 /// ConstantSDNode whose internal value will be tested using the simm8 predicate.
1693 /// The corresponding GlobalISel representation is %1 = G_CONSTANT iN Value. In
1694 /// this representation, the immediate could be tested with an
1695 /// InstructionMatcher, InstructionOpcodeMatcher, OperandMatcher, and a
1696 /// OperandPredicateMatcher-subclass to check the Value meets the predicate but
1697 /// there are two implementation issues with producing that matcher
1698 /// configuration from the SelectionDAG pattern:
1699 /// * ImmLeaf is a PatFrag whose root is an InstructionMatcher. This means that
1700 /// were we to sink the immediate predicate to the operand we would have to
1701 /// have two partial implementations of PatFrag support, one for immediates
1702 /// and one for non-immediates.
1703 /// * At the point we handle the predicate, the OperandMatcher hasn't been
1704 /// created yet. If we were to sink the predicate to the OperandMatcher we
1705 /// would also have to complicate (or duplicate) the code that descends and
1706 /// creates matchers for the subtree.
1707 /// Overall, it's simpler to handle it in the place it was found.
1708 class InstructionImmPredicateMatcher : public InstructionPredicateMatcher {
1710 TreePredicateFn Predicate;
1713 InstructionImmPredicateMatcher(unsigned InsnVarID,
1714 const TreePredicateFn &Predicate)
1715 : InstructionPredicateMatcher(IPM_ImmPredicate, InsnVarID),
1716 Predicate(Predicate) {}
1718 bool isIdentical(const PredicateMatcher &B) const override {
1719 return InstructionPredicateMatcher::isIdentical(B) &&
1720 Predicate.getOrigPatFragRecord() ==
1721 cast<InstructionImmPredicateMatcher>(&B)
1722 ->Predicate.getOrigPatFragRecord();
1725 static bool classof(const PredicateMatcher *P) {
1726 return P->getKind() == IPM_ImmPredicate;
1729 void emitPredicateOpcodes(MatchTable &Table,
1730 RuleMatcher &Rule) const override {
1731 Table << MatchTable::Opcode(getMatchOpcodeForPredicate(Predicate))
1732 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1733 << MatchTable::Comment("Predicate")
1734 << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
1735 << MatchTable::LineBreak;
1739 /// Generates code to check that a memory instruction has a atomic ordering
1740 /// MachineMemoryOperand.
1741 class AtomicOrderingMMOPredicateMatcher : public InstructionPredicateMatcher {
1751 AOComparator Comparator;
1754 AtomicOrderingMMOPredicateMatcher(unsigned InsnVarID, StringRef Order,
1755 AOComparator Comparator = AO_Exactly)
1756 : InstructionPredicateMatcher(IPM_AtomicOrderingMMO, InsnVarID),
1757 Order(Order), Comparator(Comparator) {}
1759 static bool classof(const PredicateMatcher *P) {
1760 return P->getKind() == IPM_AtomicOrderingMMO;
1763 bool isIdentical(const PredicateMatcher &B) const override {
1764 if (!InstructionPredicateMatcher::isIdentical(B))
1766 const auto &R = *cast<AtomicOrderingMMOPredicateMatcher>(&B);
1767 return Order == R.Order && Comparator == R.Comparator;
1770 void emitPredicateOpcodes(MatchTable &Table,
1771 RuleMatcher &Rule) const override {
1772 StringRef Opcode = "GIM_CheckAtomicOrdering";
1774 if (Comparator == AO_OrStronger)
1775 Opcode = "GIM_CheckAtomicOrderingOrStrongerThan";
1776 if (Comparator == AO_WeakerThan)
1777 Opcode = "GIM_CheckAtomicOrderingWeakerThan";
1779 Table << MatchTable::Opcode(Opcode) << MatchTable::Comment("MI")
1780 << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Order")
1781 << MatchTable::NamedValue(("(int64_t)AtomicOrdering::" + Order).str())
1782 << MatchTable::LineBreak;
1786 /// Generates code to check that the size of an MMO is exactly N bytes.
1787 class MemorySizePredicateMatcher : public InstructionPredicateMatcher {
1793 MemorySizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, unsigned Size)
1794 : InstructionPredicateMatcher(IPM_MemoryLLTSize, InsnVarID),
1795 MMOIdx(MMOIdx), Size(Size) {}
1797 static bool classof(const PredicateMatcher *P) {
1798 return P->getKind() == IPM_MemoryLLTSize;
1800 bool isIdentical(const PredicateMatcher &B) const override {
1801 return InstructionPredicateMatcher::isIdentical(B) &&
1802 MMOIdx == cast<MemorySizePredicateMatcher>(&B)->MMOIdx &&
1803 Size == cast<MemorySizePredicateMatcher>(&B)->Size;
1806 void emitPredicateOpcodes(MatchTable &Table,
1807 RuleMatcher &Rule) const override {
1808 Table << MatchTable::Opcode("GIM_CheckMemorySizeEqualTo")
1809 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1810 << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
1811 << MatchTable::Comment("Size") << MatchTable::IntValue(Size)
1812 << MatchTable::LineBreak;
1816 class MemoryAddressSpacePredicateMatcher : public InstructionPredicateMatcher {
1819 SmallVector<unsigned, 4> AddrSpaces;
1822 MemoryAddressSpacePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
1823 ArrayRef<unsigned> AddrSpaces)
1824 : InstructionPredicateMatcher(IPM_MemoryAddressSpace, InsnVarID),
1825 MMOIdx(MMOIdx), AddrSpaces(AddrSpaces.begin(), AddrSpaces.end()) {}
1827 static bool classof(const PredicateMatcher *P) {
1828 return P->getKind() == IPM_MemoryAddressSpace;
1830 bool isIdentical(const PredicateMatcher &B) const override {
1831 if (!InstructionPredicateMatcher::isIdentical(B))
1833 auto *Other = cast<MemoryAddressSpacePredicateMatcher>(&B);
1834 return MMOIdx == Other->MMOIdx && AddrSpaces == Other->AddrSpaces;
1837 void emitPredicateOpcodes(MatchTable &Table,
1838 RuleMatcher &Rule) const override {
1839 Table << MatchTable::Opcode("GIM_CheckMemoryAddressSpace")
1840 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1841 << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
1842 // Encode number of address spaces to expect.
1843 << MatchTable::Comment("NumAddrSpace")
1844 << MatchTable::IntValue(AddrSpaces.size());
1845 for (unsigned AS : AddrSpaces)
1846 Table << MatchTable::Comment("AddrSpace") << MatchTable::IntValue(AS);
1848 Table << MatchTable::LineBreak;
1852 /// Generates code to check that the size of an MMO is less-than, equal-to, or
1853 /// greater than a given LLT.
1854 class MemoryVsLLTSizePredicateMatcher : public InstructionPredicateMatcher {
1864 RelationKind Relation;
1868 MemoryVsLLTSizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
1869 enum RelationKind Relation,
1871 : InstructionPredicateMatcher(IPM_MemoryVsLLTSize, InsnVarID),
1872 MMOIdx(MMOIdx), Relation(Relation), OpIdx(OpIdx) {}
1874 static bool classof(const PredicateMatcher *P) {
1875 return P->getKind() == IPM_MemoryVsLLTSize;
1877 bool isIdentical(const PredicateMatcher &B) const override {
1878 return InstructionPredicateMatcher::isIdentical(B) &&
1879 MMOIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->MMOIdx &&
1880 Relation == cast<MemoryVsLLTSizePredicateMatcher>(&B)->Relation &&
1881 OpIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->OpIdx;
1884 void emitPredicateOpcodes(MatchTable &Table,
1885 RuleMatcher &Rule) const override {
1886 Table << MatchTable::Opcode(Relation == EqualTo
1887 ? "GIM_CheckMemorySizeEqualToLLT"
1888 : Relation == GreaterThan
1889 ? "GIM_CheckMemorySizeGreaterThanLLT"
1890 : "GIM_CheckMemorySizeLessThanLLT")
1891 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1892 << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
1893 << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx)
1894 << MatchTable::LineBreak;
1898 /// Generates code to check an arbitrary C++ instruction predicate.
1899 class GenericInstructionPredicateMatcher : public InstructionPredicateMatcher {
1901 TreePredicateFn Predicate;
1904 GenericInstructionPredicateMatcher(unsigned InsnVarID,
1905 TreePredicateFn Predicate)
1906 : InstructionPredicateMatcher(IPM_GenericPredicate, InsnVarID),
1907 Predicate(Predicate) {}
1909 static bool classof(const InstructionPredicateMatcher *P) {
1910 return P->getKind() == IPM_GenericPredicate;
1912 bool isIdentical(const PredicateMatcher &B) const override {
1913 return InstructionPredicateMatcher::isIdentical(B) &&
1915 static_cast<const GenericInstructionPredicateMatcher &>(B)
1918 void emitPredicateOpcodes(MatchTable &Table,
1919 RuleMatcher &Rule) const override {
1920 Table << MatchTable::Opcode("GIM_CheckCxxInsnPredicate")
1921 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1922 << MatchTable::Comment("FnId")
1923 << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
1924 << MatchTable::LineBreak;
1928 /// Generates code to check that a set of predicates and operands match for a
1929 /// particular instruction.
1931 /// Typical predicates include:
1932 /// * Has a specific opcode.
1933 /// * Has an nsw/nuw flag or doesn't.
1934 class InstructionMatcher final : public PredicateListMatcher<PredicateMatcher> {
1936 typedef std::vector<std::unique_ptr<OperandMatcher>> OperandVec;
1940 /// The operands to match. All rendered operands must be present even if the
1941 /// condition is always true.
1942 OperandVec Operands;
1943 bool NumOperandsCheck = true;
1945 std::string SymbolicName;
1949 InstructionMatcher(RuleMatcher &Rule, StringRef SymbolicName)
1950 : Rule(Rule), SymbolicName(SymbolicName) {
1951 // We create a new instruction matcher.
1952 // Get a new ID for that instruction.
1953 InsnVarID = Rule.implicitlyDefineInsnVar(*this);
1956 /// Construct a new instruction predicate and add it to the matcher.
1957 template <class Kind, class... Args>
1958 Optional<Kind *> addPredicate(Args &&... args) {
1959 Predicates.emplace_back(
1960 llvm::make_unique<Kind>(getInsnVarID(), std::forward<Args>(args)...));
1961 return static_cast<Kind *>(Predicates.back().get());
1964 RuleMatcher &getRuleMatcher() const { return Rule; }
1966 unsigned getInsnVarID() const { return InsnVarID; }
1968 /// Add an operand to the matcher.
1969 OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName,
1970 unsigned AllocatedTemporariesBaseID) {
1971 Operands.emplace_back(new OperandMatcher(*this, OpIdx, SymbolicName,
1972 AllocatedTemporariesBaseID));
1973 if (!SymbolicName.empty())
1974 Rule.defineOperand(SymbolicName, *Operands.back());
1976 return *Operands.back();
1979 OperandMatcher &getOperand(unsigned OpIdx) {
1980 auto I = std::find_if(Operands.begin(), Operands.end(),
1981 [&OpIdx](const std::unique_ptr<OperandMatcher> &X) {
1982 return X->getOpIdx() == OpIdx;
1984 if (I != Operands.end())
1986 llvm_unreachable("Failed to lookup operand");
1989 StringRef getSymbolicName() const { return SymbolicName; }
1990 unsigned getNumOperands() const { return Operands.size(); }
1991 OperandVec::iterator operands_begin() { return Operands.begin(); }
1992 OperandVec::iterator operands_end() { return Operands.end(); }
1993 iterator_range<OperandVec::iterator> operands() {
1994 return make_range(operands_begin(), operands_end());
1996 OperandVec::const_iterator operands_begin() const { return Operands.begin(); }
1997 OperandVec::const_iterator operands_end() const { return Operands.end(); }
1998 iterator_range<OperandVec::const_iterator> operands() const {
1999 return make_range(operands_begin(), operands_end());
2001 bool operands_empty() const { return Operands.empty(); }
2003 void pop_front() { Operands.erase(Operands.begin()); }
2007 /// Emit MatchTable opcodes that test whether the instruction named in
2008 /// InsnVarName matches all the predicates and all the operands.
2009 void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) {
2010 if (NumOperandsCheck)
2011 InstructionNumOperandsMatcher(InsnVarID, getNumOperands())
2012 .emitPredicateOpcodes(Table, Rule);
2014 emitPredicateListOpcodes(Table, Rule);
2016 for (const auto &Operand : Operands)
2017 Operand->emitPredicateOpcodes(Table, Rule);
2020 /// Compare the priority of this object and B.
2022 /// Returns true if this object is more important than B.
2023 bool isHigherPriorityThan(InstructionMatcher &B) {
2024 // Instruction matchers involving more operands have higher priority.
2025 if (Operands.size() > B.Operands.size())
2027 if (Operands.size() < B.Operands.size())
2030 for (auto &&P : zip(predicates(), B.predicates())) {
2031 auto L = static_cast<InstructionPredicateMatcher *>(std::get<0>(P).get());
2032 auto R = static_cast<InstructionPredicateMatcher *>(std::get<1>(P).get());
2033 if (L->isHigherPriorityThan(*R))
2035 if (R->isHigherPriorityThan(*L))
2039 for (const auto &Operand : zip(Operands, B.Operands)) {
2040 if (std::get<0>(Operand)->isHigherPriorityThan(*std::get<1>(Operand)))
2042 if (std::get<1>(Operand)->isHigherPriorityThan(*std::get<0>(Operand)))
2049 /// Report the maximum number of temporary operands needed by the instruction
2051 unsigned countRendererFns() {
2052 return std::accumulate(
2053 predicates().begin(), predicates().end(), 0,
2055 const std::unique_ptr<PredicateMatcher> &Predicate) {
2056 return A + Predicate->countRendererFns();
2059 Operands.begin(), Operands.end(), 0,
2060 [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) {
2061 return A + Operand->countRendererFns();
2065 InstructionOpcodeMatcher &getOpcodeMatcher() {
2066 for (auto &P : predicates())
2067 if (auto *OpMatcher = dyn_cast<InstructionOpcodeMatcher>(P.get()))
2069 llvm_unreachable("Didn't find an opcode matcher");
2072 bool isConstantInstruction() {
2073 return getOpcodeMatcher().isConstantInstruction();
2076 StringRef getOpcode() { return getOpcodeMatcher().getOpcode(); }
2079 StringRef RuleMatcher::getOpcode() const {
2080 return Matchers.front()->getOpcode();
2083 unsigned RuleMatcher::getNumOperands() const {
2084 return Matchers.front()->getNumOperands();
2087 LLTCodeGen RuleMatcher::getFirstConditionAsRootType() {
2088 InstructionMatcher &InsnMatcher = *Matchers.front();
2089 if (!InsnMatcher.predicates_empty())
2090 if (const auto *TM =
2091 dyn_cast<LLTOperandMatcher>(&**InsnMatcher.predicates_begin()))
2092 if (TM->getInsnVarID() == 0 && TM->getOpIdx() == 0)
2097 /// Generates code to check that the operand is a register defined by an
2098 /// instruction that matches the given instruction matcher.
2100 /// For example, the pattern:
2101 /// (set $dst, (G_MUL (G_ADD $src1, $src2), $src3))
2102 /// would use an InstructionOperandMatcher for operand 1 of the G_MUL to match
2104 /// (G_ADD $src1, $src2)
2106 class InstructionOperandMatcher : public OperandPredicateMatcher {
2108 std::unique_ptr<InstructionMatcher> InsnMatcher;
2111 InstructionOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
2112 RuleMatcher &Rule, StringRef SymbolicName)
2113 : OperandPredicateMatcher(OPM_Instruction, InsnVarID, OpIdx),
2114 InsnMatcher(new InstructionMatcher(Rule, SymbolicName)) {}
2116 static bool classof(const PredicateMatcher *P) {
2117 return P->getKind() == OPM_Instruction;
2120 InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; }
2122 void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const {
2123 const unsigned NewInsnVarID = InsnMatcher->getInsnVarID();
2124 Table << MatchTable::Opcode("GIM_RecordInsn")
2125 << MatchTable::Comment("DefineMI")
2126 << MatchTable::IntValue(NewInsnVarID) << MatchTable::Comment("MI")
2127 << MatchTable::IntValue(getInsnVarID())
2128 << MatchTable::Comment("OpIdx") << MatchTable::IntValue(getOpIdx())
2129 << MatchTable::Comment("MIs[" + llvm::to_string(NewInsnVarID) + "]")
2130 << MatchTable::LineBreak;
2133 void emitPredicateOpcodes(MatchTable &Table,
2134 RuleMatcher &Rule) const override {
2135 emitCaptureOpcodes(Table, Rule);
2136 InsnMatcher->emitPredicateOpcodes(Table, Rule);
2139 bool isHigherPriorityThan(const OperandPredicateMatcher &B) const override {
2140 if (OperandPredicateMatcher::isHigherPriorityThan(B))
2142 if (B.OperandPredicateMatcher::isHigherPriorityThan(*this))
2145 if (const InstructionOperandMatcher *BP =
2146 dyn_cast<InstructionOperandMatcher>(&B))
2147 if (InsnMatcher->isHigherPriorityThan(*BP->InsnMatcher))
2153 void InstructionMatcher::optimize() {
2154 SmallVector<std::unique_ptr<PredicateMatcher>, 8> Stash;
2155 const auto &OpcMatcher = getOpcodeMatcher();
2157 Stash.push_back(predicates_pop_front());
2158 if (Stash.back().get() == &OpcMatcher) {
2159 if (NumOperandsCheck && OpcMatcher.getNumOperands() < getNumOperands())
2161 new InstructionNumOperandsMatcher(InsnVarID, getNumOperands()));
2162 NumOperandsCheck = false;
2164 for (auto &OM : Operands)
2165 for (auto &OP : OM->predicates())
2166 if (isa<IntrinsicIDOperandMatcher>(OP)) {
2167 Stash.push_back(std::move(OP));
2168 OM->eraseNullPredicates();
2173 if (InsnVarID > 0) {
2174 assert(!Operands.empty() && "Nested instruction is expected to def a vreg");
2175 for (auto &OP : Operands[0]->predicates())
2177 Operands[0]->eraseNullPredicates();
2179 for (auto &OM : Operands) {
2180 for (auto &OP : OM->predicates())
2181 if (isa<LLTOperandMatcher>(OP))
2182 Stash.push_back(std::move(OP));
2183 OM->eraseNullPredicates();
2185 while (!Stash.empty())
2186 prependPredicate(Stash.pop_back_val());
2189 //===- Actions ------------------------------------------------------------===//
2190 class OperandRenderer {
2194 OR_CopyOrAddZeroReg,
2196 OR_CopyConstantAsImm,
2197 OR_CopyFConstantAsFPImm,
2209 OperandRenderer(RendererKind Kind) : Kind(Kind) {}
2210 virtual ~OperandRenderer() {}
2212 RendererKind getKind() const { return Kind; }
2214 virtual void emitRenderOpcodes(MatchTable &Table,
2215 RuleMatcher &Rule) const = 0;
2218 /// A CopyRenderer emits code to copy a single operand from an existing
2219 /// instruction to the one being built.
2220 class CopyRenderer : public OperandRenderer {
2223 /// The name of the operand.
2224 const StringRef SymbolicName;
2227 CopyRenderer(unsigned NewInsnID, StringRef SymbolicName)
2228 : OperandRenderer(OR_Copy), NewInsnID(NewInsnID),
2229 SymbolicName(SymbolicName) {
2230 assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
2233 static bool classof(const OperandRenderer *R) {
2234 return R->getKind() == OR_Copy;
2237 const StringRef getSymbolicName() const { return SymbolicName; }
2239 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2240 const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2241 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2242 Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
2243 << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID")
2244 << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2245 << MatchTable::IntValue(Operand.getOpIdx())
2246 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2250 /// A CopyOrAddZeroRegRenderer emits code to copy a single operand from an
2251 /// existing instruction to the one being built. If the operand turns out to be
2252 /// a 'G_CONSTANT 0' then it replaces the operand with a zero register.
2253 class CopyOrAddZeroRegRenderer : public OperandRenderer {
2256 /// The name of the operand.
2257 const StringRef SymbolicName;
2258 const Record *ZeroRegisterDef;
2261 CopyOrAddZeroRegRenderer(unsigned NewInsnID,
2262 StringRef SymbolicName, Record *ZeroRegisterDef)
2263 : OperandRenderer(OR_CopyOrAddZeroReg), NewInsnID(NewInsnID),
2264 SymbolicName(SymbolicName), ZeroRegisterDef(ZeroRegisterDef) {
2265 assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
2268 static bool classof(const OperandRenderer *R) {
2269 return R->getKind() == OR_CopyOrAddZeroReg;
2272 const StringRef getSymbolicName() const { return SymbolicName; }
2274 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2275 const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2276 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2277 Table << MatchTable::Opcode("GIR_CopyOrAddZeroReg")
2278 << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2279 << MatchTable::Comment("OldInsnID")
2280 << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2281 << MatchTable::IntValue(Operand.getOpIdx())
2282 << MatchTable::NamedValue(
2283 (ZeroRegisterDef->getValue("Namespace")
2284 ? ZeroRegisterDef->getValueAsString("Namespace")
2286 ZeroRegisterDef->getName())
2287 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2291 /// A CopyConstantAsImmRenderer emits code to render a G_CONSTANT instruction to
2292 /// an extended immediate operand.
2293 class CopyConstantAsImmRenderer : public OperandRenderer {
2296 /// The name of the operand.
2297 const std::string SymbolicName;
2301 CopyConstantAsImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
2302 : OperandRenderer(OR_CopyConstantAsImm), NewInsnID(NewInsnID),
2303 SymbolicName(SymbolicName), Signed(true) {}
2305 static bool classof(const OperandRenderer *R) {
2306 return R->getKind() == OR_CopyConstantAsImm;
2309 const StringRef getSymbolicName() const { return SymbolicName; }
2311 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2312 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2313 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2314 Table << MatchTable::Opcode(Signed ? "GIR_CopyConstantAsSImm"
2315 : "GIR_CopyConstantAsUImm")
2316 << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2317 << MatchTable::Comment("OldInsnID")
2318 << MatchTable::IntValue(OldInsnVarID)
2319 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2323 /// A CopyFConstantAsFPImmRenderer emits code to render a G_FCONSTANT
2324 /// instruction to an extended immediate operand.
2325 class CopyFConstantAsFPImmRenderer : public OperandRenderer {
2328 /// The name of the operand.
2329 const std::string SymbolicName;
2332 CopyFConstantAsFPImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
2333 : OperandRenderer(OR_CopyFConstantAsFPImm), NewInsnID(NewInsnID),
2334 SymbolicName(SymbolicName) {}
2336 static bool classof(const OperandRenderer *R) {
2337 return R->getKind() == OR_CopyFConstantAsFPImm;
2340 const StringRef getSymbolicName() const { return SymbolicName; }
2342 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2343 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2344 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2345 Table << MatchTable::Opcode("GIR_CopyFConstantAsFPImm")
2346 << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2347 << MatchTable::Comment("OldInsnID")
2348 << MatchTable::IntValue(OldInsnVarID)
2349 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2353 /// A CopySubRegRenderer emits code to copy a single register operand from an
2354 /// existing instruction to the one being built and indicate that only a
2355 /// subregister should be copied.
2356 class CopySubRegRenderer : public OperandRenderer {
2359 /// The name of the operand.
2360 const StringRef SymbolicName;
2361 /// The subregister to extract.
2362 const CodeGenSubRegIndex *SubReg;
2365 CopySubRegRenderer(unsigned NewInsnID, StringRef SymbolicName,
2366 const CodeGenSubRegIndex *SubReg)
2367 : OperandRenderer(OR_CopySubReg), NewInsnID(NewInsnID),
2368 SymbolicName(SymbolicName), SubReg(SubReg) {}
2370 static bool classof(const OperandRenderer *R) {
2371 return R->getKind() == OR_CopySubReg;
2374 const StringRef getSymbolicName() const { return SymbolicName; }
2376 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2377 const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2378 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2379 Table << MatchTable::Opcode("GIR_CopySubReg")
2380 << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2381 << MatchTable::Comment("OldInsnID")
2382 << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2383 << MatchTable::IntValue(Operand.getOpIdx())
2384 << MatchTable::Comment("SubRegIdx")
2385 << MatchTable::IntValue(SubReg->EnumValue)
2386 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2390 /// Adds a specific physical register to the instruction being built.
2391 /// This is typically useful for WZR/XZR on AArch64.
2392 class AddRegisterRenderer : public OperandRenderer {
2395 const Record *RegisterDef;
2398 AddRegisterRenderer(unsigned InsnID, const Record *RegisterDef)
2399 : OperandRenderer(OR_Register), InsnID(InsnID), RegisterDef(RegisterDef) {
2402 static bool classof(const OperandRenderer *R) {
2403 return R->getKind() == OR_Register;
2406 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2407 Table << MatchTable::Opcode("GIR_AddRegister")
2408 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2409 << MatchTable::NamedValue(
2410 (RegisterDef->getValue("Namespace")
2411 ? RegisterDef->getValueAsString("Namespace")
2413 RegisterDef->getName())
2414 << MatchTable::LineBreak;
2418 /// Adds a specific temporary virtual register to the instruction being built.
2419 /// This is used to chain instructions together when emitting multiple
2421 class TempRegRenderer : public OperandRenderer {
2428 TempRegRenderer(unsigned InsnID, unsigned TempRegID, bool IsDef = false)
2429 : OperandRenderer(OR_Register), InsnID(InsnID), TempRegID(TempRegID),
2432 static bool classof(const OperandRenderer *R) {
2433 return R->getKind() == OR_TempRegister;
2436 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2437 Table << MatchTable::Opcode("GIR_AddTempRegister")
2438 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2439 << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID)
2440 << MatchTable::Comment("TempRegFlags");
2442 Table << MatchTable::NamedValue("RegState::Define");
2444 Table << MatchTable::IntValue(0);
2445 Table << MatchTable::LineBreak;
2449 /// Adds a specific immediate to the instruction being built.
2450 class ImmRenderer : public OperandRenderer {
2456 ImmRenderer(unsigned InsnID, int64_t Imm)
2457 : OperandRenderer(OR_Imm), InsnID(InsnID), Imm(Imm) {}
2459 static bool classof(const OperandRenderer *R) {
2460 return R->getKind() == OR_Imm;
2463 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2464 Table << MatchTable::Opcode("GIR_AddImm") << MatchTable::Comment("InsnID")
2465 << MatchTable::IntValue(InsnID) << MatchTable::Comment("Imm")
2466 << MatchTable::IntValue(Imm) << MatchTable::LineBreak;
2470 /// Adds operands by calling a renderer function supplied by the ComplexPattern
2471 /// matcher function.
2472 class RenderComplexPatternOperand : public OperandRenderer {
2475 const Record &TheDef;
2476 /// The name of the operand.
2477 const StringRef SymbolicName;
2478 /// The renderer number. This must be unique within a rule since it's used to
2479 /// identify a temporary variable to hold the renderer function.
2480 unsigned RendererID;
2481 /// When provided, this is the suboperand of the ComplexPattern operand to
2482 /// render. Otherwise all the suboperands will be rendered.
2483 Optional<unsigned> SubOperand;
2485 unsigned getNumOperands() const {
2486 return TheDef.getValueAsDag("Operands")->getNumArgs();
2490 RenderComplexPatternOperand(unsigned InsnID, const Record &TheDef,
2491 StringRef SymbolicName, unsigned RendererID,
2492 Optional<unsigned> SubOperand = None)
2493 : OperandRenderer(OR_ComplexPattern), InsnID(InsnID), TheDef(TheDef),
2494 SymbolicName(SymbolicName), RendererID(RendererID),
2495 SubOperand(SubOperand) {}
2497 static bool classof(const OperandRenderer *R) {
2498 return R->getKind() == OR_ComplexPattern;
2501 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2502 Table << MatchTable::Opcode(SubOperand.hasValue() ? "GIR_ComplexSubOperandRenderer"
2503 : "GIR_ComplexRenderer")
2504 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2505 << MatchTable::Comment("RendererID")
2506 << MatchTable::IntValue(RendererID);
2507 if (SubOperand.hasValue())
2508 Table << MatchTable::Comment("SubOperand")
2509 << MatchTable::IntValue(SubOperand.getValue());
2510 Table << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2514 class CustomRenderer : public OperandRenderer {
2517 const Record &Renderer;
2518 /// The name of the operand.
2519 const std::string SymbolicName;
2522 CustomRenderer(unsigned InsnID, const Record &Renderer,
2523 StringRef SymbolicName)
2524 : OperandRenderer(OR_Custom), InsnID(InsnID), Renderer(Renderer),
2525 SymbolicName(SymbolicName) {}
2527 static bool classof(const OperandRenderer *R) {
2528 return R->getKind() == OR_Custom;
2531 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2532 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2533 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2534 Table << MatchTable::Opcode("GIR_CustomRenderer")
2535 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2536 << MatchTable::Comment("OldInsnID")
2537 << MatchTable::IntValue(OldInsnVarID)
2538 << MatchTable::Comment("Renderer")
2539 << MatchTable::NamedValue(
2540 "GICR_" + Renderer.getValueAsString("RendererFn").str())
2541 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2545 /// An action taken when all Matcher predicates succeeded for a parent rule.
2547 /// Typical actions include:
2548 /// * Changing the opcode of an instruction.
2549 /// * Adding an operand to an instruction.
2552 virtual ~MatchAction() {}
2554 /// Emit the MatchTable opcodes to implement the action.
2555 virtual void emitActionOpcodes(MatchTable &Table,
2556 RuleMatcher &Rule) const = 0;
2559 /// Generates a comment describing the matched rule being acted upon.
2560 class DebugCommentAction : public MatchAction {
2565 DebugCommentAction(StringRef S) : S(S) {}
2567 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2568 Table << MatchTable::Comment(S) << MatchTable::LineBreak;
2572 /// Generates code to build an instruction or mutate an existing instruction
2573 /// into the desired instruction when this is possible.
2574 class BuildMIAction : public MatchAction {
2577 const CodeGenInstruction *I;
2578 InstructionMatcher *Matched;
2579 std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers;
2581 /// True if the instruction can be built solely by mutating the opcode.
2582 bool canMutate(RuleMatcher &Rule, const InstructionMatcher *Insn) const {
2586 if (OperandRenderers.size() != Insn->getNumOperands())
2589 for (const auto &Renderer : enumerate(OperandRenderers)) {
2590 if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) {
2591 const OperandMatcher &OM = Rule.getOperandMatcher(Copy->getSymbolicName());
2592 if (Insn != &OM.getInstructionMatcher() ||
2593 OM.getOpIdx() != Renderer.index())
2603 BuildMIAction(unsigned InsnID, const CodeGenInstruction *I)
2604 : InsnID(InsnID), I(I), Matched(nullptr) {}
2606 unsigned getInsnID() const { return InsnID; }
2607 const CodeGenInstruction *getCGI() const { return I; }
2609 void chooseInsnToMutate(RuleMatcher &Rule) {
2610 for (auto *MutateCandidate : Rule.mutatable_insns()) {
2611 if (canMutate(Rule, MutateCandidate)) {
2612 // Take the first one we're offered that we're able to mutate.
2613 Rule.reserveInsnMatcherForMutation(MutateCandidate);
2614 Matched = MutateCandidate;
2620 template <class Kind, class... Args>
2621 Kind &addRenderer(Args&&... args) {
2622 OperandRenderers.emplace_back(
2623 llvm::make_unique<Kind>(InsnID, std::forward<Args>(args)...));
2624 return *static_cast<Kind *>(OperandRenderers.back().get());
2627 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2629 assert(canMutate(Rule, Matched) &&
2630 "Arranged to mutate an insn that isn't mutatable");
2632 unsigned RecycleInsnID = Rule.getInsnVarID(*Matched);
2633 Table << MatchTable::Opcode("GIR_MutateOpcode")
2634 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2635 << MatchTable::Comment("RecycleInsnID")
2636 << MatchTable::IntValue(RecycleInsnID)
2637 << MatchTable::Comment("Opcode")
2638 << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
2639 << MatchTable::LineBreak;
2641 if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) {
2642 for (auto Def : I->ImplicitDefs) {
2643 auto Namespace = Def->getValue("Namespace")
2644 ? Def->getValueAsString("Namespace")
2646 Table << MatchTable::Opcode("GIR_AddImplicitDef")
2647 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2648 << MatchTable::NamedValue(Namespace, Def->getName())
2649 << MatchTable::LineBreak;
2651 for (auto Use : I->ImplicitUses) {
2652 auto Namespace = Use->getValue("Namespace")
2653 ? Use->getValueAsString("Namespace")
2655 Table << MatchTable::Opcode("GIR_AddImplicitUse")
2656 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2657 << MatchTable::NamedValue(Namespace, Use->getName())
2658 << MatchTable::LineBreak;
2664 // TODO: Simple permutation looks like it could be almost as common as
2665 // mutation due to commutative operations.
2667 Table << MatchTable::Opcode("GIR_BuildMI") << MatchTable::Comment("InsnID")
2668 << MatchTable::IntValue(InsnID) << MatchTable::Comment("Opcode")
2669 << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
2670 << MatchTable::LineBreak;
2671 for (const auto &Renderer : OperandRenderers)
2672 Renderer->emitRenderOpcodes(Table, Rule);
2674 if (I->mayLoad || I->mayStore) {
2675 Table << MatchTable::Opcode("GIR_MergeMemOperands")
2676 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2677 << MatchTable::Comment("MergeInsnID's");
2678 // Emit the ID's for all the instructions that are matched by this rule.
2679 // TODO: Limit this to matched instructions that mayLoad/mayStore or have
2680 // some other means of having a memoperand. Also limit this to
2681 // emitted instructions that expect to have a memoperand too. For
2682 // example, (G_SEXT (G_LOAD x)) that results in separate load and
2683 // sign-extend instructions shouldn't put the memoperand on the
2684 // sign-extend since it has no effect there.
2685 std::vector<unsigned> MergeInsnIDs;
2686 for (const auto &IDMatcherPair : Rule.defined_insn_vars())
2687 MergeInsnIDs.push_back(IDMatcherPair.second);
2688 llvm::sort(MergeInsnIDs);
2689 for (const auto &MergeInsnID : MergeInsnIDs)
2690 Table << MatchTable::IntValue(MergeInsnID);
2691 Table << MatchTable::NamedValue("GIU_MergeMemOperands_EndOfList")
2692 << MatchTable::LineBreak;
2695 // FIXME: This is a hack but it's sufficient for ISel. We'll need to do
2696 // better for combines. Particularly when there are multiple match
2699 Table << MatchTable::Opcode("GIR_EraseFromParent")
2700 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2701 << MatchTable::LineBreak;
2705 /// Generates code to constrain the operands of an output instruction to the
2706 /// register classes specified by the definition of that instruction.
2707 class ConstrainOperandsToDefinitionAction : public MatchAction {
2711 ConstrainOperandsToDefinitionAction(unsigned InsnID) : InsnID(InsnID) {}
2713 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2714 Table << MatchTable::Opcode("GIR_ConstrainSelectedInstOperands")
2715 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2716 << MatchTable::LineBreak;
2720 /// Generates code to constrain the specified operand of an output instruction
2721 /// to the specified register class.
2722 class ConstrainOperandToRegClassAction : public MatchAction {
2725 const CodeGenRegisterClass &RC;
2728 ConstrainOperandToRegClassAction(unsigned InsnID, unsigned OpIdx,
2729 const CodeGenRegisterClass &RC)
2730 : InsnID(InsnID), OpIdx(OpIdx), RC(RC) {}
2732 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2733 Table << MatchTable::Opcode("GIR_ConstrainOperandRC")
2734 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2735 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
2736 << MatchTable::Comment("RC " + RC.getName())
2737 << MatchTable::IntValue(RC.EnumValue) << MatchTable::LineBreak;
2741 /// Generates code to create a temporary register which can be used to chain
2742 /// instructions together.
2743 class MakeTempRegisterAction : public MatchAction {
2749 MakeTempRegisterAction(const LLTCodeGen &Ty, unsigned TempRegID)
2750 : Ty(Ty), TempRegID(TempRegID) {}
2752 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2753 Table << MatchTable::Opcode("GIR_MakeTempReg")
2754 << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID)
2755 << MatchTable::Comment("TypeID")
2756 << MatchTable::NamedValue(Ty.getCxxEnumValue())
2757 << MatchTable::LineBreak;
2761 InstructionMatcher &RuleMatcher::addInstructionMatcher(StringRef SymbolicName) {
2762 Matchers.emplace_back(new InstructionMatcher(*this, SymbolicName));
2763 MutatableInsns.insert(Matchers.back().get());
2764 return *Matchers.back();
2767 void RuleMatcher::addRequiredFeature(Record *Feature) {
2768 RequiredFeatures.push_back(Feature);
2771 const std::vector<Record *> &RuleMatcher::getRequiredFeatures() const {
2772 return RequiredFeatures;
2775 // Emplaces an action of the specified Kind at the end of the action list.
2777 // Returns a reference to the newly created action.
2779 // Like std::vector::emplace_back(), may invalidate all iterators if the new
2780 // size exceeds the capacity. Otherwise, only invalidates the past-the-end
2782 template <class Kind, class... Args>
2783 Kind &RuleMatcher::addAction(Args &&... args) {
2784 Actions.emplace_back(llvm::make_unique<Kind>(std::forward<Args>(args)...));
2785 return *static_cast<Kind *>(Actions.back().get());
2788 // Emplaces an action of the specified Kind before the given insertion point.
2790 // Returns an iterator pointing at the newly created instruction.
2792 // Like std::vector::insert(), may invalidate all iterators if the new size
2793 // exceeds the capacity. Otherwise, only invalidates the iterators from the
2794 // insertion point onwards.
2795 template <class Kind, class... Args>
2796 action_iterator RuleMatcher::insertAction(action_iterator InsertPt,
2798 return Actions.emplace(InsertPt,
2799 llvm::make_unique<Kind>(std::forward<Args>(args)...));
2802 unsigned RuleMatcher::implicitlyDefineInsnVar(InstructionMatcher &Matcher) {
2803 unsigned NewInsnVarID = NextInsnVarID++;
2804 InsnVariableIDs[&Matcher] = NewInsnVarID;
2805 return NewInsnVarID;
2808 unsigned RuleMatcher::getInsnVarID(InstructionMatcher &InsnMatcher) const {
2809 const auto &I = InsnVariableIDs.find(&InsnMatcher);
2810 if (I != InsnVariableIDs.end())
2812 llvm_unreachable("Matched Insn was not captured in a local variable");
2815 void RuleMatcher::defineOperand(StringRef SymbolicName, OperandMatcher &OM) {
2816 if (DefinedOperands.find(SymbolicName) == DefinedOperands.end()) {
2817 DefinedOperands[SymbolicName] = &OM;
2821 // If the operand is already defined, then we must ensure both references in
2822 // the matcher have the exact same node.
2823 OM.addPredicate<SameOperandMatcher>(OM.getSymbolicName());
2826 InstructionMatcher &
2827 RuleMatcher::getInstructionMatcher(StringRef SymbolicName) const {
2828 for (const auto &I : InsnVariableIDs)
2829 if (I.first->getSymbolicName() == SymbolicName)
2832 ("Failed to lookup instruction " + SymbolicName).str().c_str());
2835 const OperandMatcher &
2836 RuleMatcher::getOperandMatcher(StringRef Name) const {
2837 const auto &I = DefinedOperands.find(Name);
2839 if (I == DefinedOperands.end())
2840 PrintFatalError(SrcLoc, "Operand " + Name + " was not declared in matcher");
2845 void RuleMatcher::emit(MatchTable &Table) {
2846 if (Matchers.empty())
2847 llvm_unreachable("Unexpected empty matcher!");
2849 // The representation supports rules that require multiple roots such as:
2851 // %elt0(s32) = G_LOAD %ptr
2852 // %1(p0) = G_ADD %ptr, 4
2853 // %elt1(s32) = G_LOAD p0 %1
2854 // which could be usefully folded into:
2856 // %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr
2857 // on some targets but we don't need to make use of that yet.
2858 assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
2860 unsigned LabelID = Table.allocateLabelID();
2861 Table << MatchTable::Opcode("GIM_Try", +1)
2862 << MatchTable::Comment("On fail goto")
2863 << MatchTable::JumpTarget(LabelID)
2864 << MatchTable::Comment(("Rule ID " + Twine(RuleID) + " //").str())
2865 << MatchTable::LineBreak;
2867 if (!RequiredFeatures.empty()) {
2868 Table << MatchTable::Opcode("GIM_CheckFeatures")
2869 << MatchTable::NamedValue(getNameForFeatureBitset(RequiredFeatures))
2870 << MatchTable::LineBreak;
2873 Matchers.front()->emitPredicateOpcodes(Table, *this);
2875 // We must also check if it's safe to fold the matched instructions.
2876 if (InsnVariableIDs.size() >= 2) {
2877 // Invert the map to create stable ordering (by var names)
2878 SmallVector<unsigned, 2> InsnIDs;
2879 for (const auto &Pair : InsnVariableIDs) {
2880 // Skip the root node since it isn't moving anywhere. Everything else is
2881 // sinking to meet it.
2882 if (Pair.first == Matchers.front().get())
2885 InsnIDs.push_back(Pair.second);
2887 llvm::sort(InsnIDs);
2889 for (const auto &InsnID : InsnIDs) {
2890 // Reject the difficult cases until we have a more accurate check.
2891 Table << MatchTable::Opcode("GIM_CheckIsSafeToFold")
2892 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2893 << MatchTable::LineBreak;
2895 // FIXME: Emit checks to determine it's _actually_ safe to fold and/or
2896 // account for unsafe cases.
2901 // MI0--> %2 = ... %0
2902 // It's not safe to erase MI1. We currently handle this by not
2903 // erasing %0 (even when it's dead).
2906 // MI1--> %0 = load volatile @a
2907 // %1 = load volatile @a
2908 // MI0--> %2 = ... %0
2909 // It's not safe to sink %0's def past %1. We currently handle
2910 // this by rejecting all loads.
2913 // MI1--> %0 = load @a
2915 // MI0--> %2 = ... %0
2916 // It's not safe to sink %0's def past %1. We currently handle
2917 // this by rejecting all loads.
2920 // G_CONDBR %cond, @BB1
2922 // MI1--> %0 = load @a
2925 // MI0--> %2 = ... %0
2926 // It's not always safe to sink %0 across control flow. In this
2927 // case it may introduce a memory fault. We currentl handle this
2928 // by rejecting all loads.
2932 for (const auto &PM : EpilogueMatchers)
2933 PM->emitPredicateOpcodes(Table, *this);
2935 for (const auto &MA : Actions)
2936 MA->emitActionOpcodes(Table, *this);
2938 if (Table.isWithCoverage())
2939 Table << MatchTable::Opcode("GIR_Coverage") << MatchTable::IntValue(RuleID)
2940 << MatchTable::LineBreak;
2942 Table << MatchTable::Comment(("GIR_Coverage, " + Twine(RuleID) + ",").str())
2943 << MatchTable::LineBreak;
2945 Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak
2946 << MatchTable::Label(LabelID);
2947 ++NumPatternEmitted;
2950 bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
2951 // Rules involving more match roots have higher priority.
2952 if (Matchers.size() > B.Matchers.size())
2954 if (Matchers.size() < B.Matchers.size())
2957 for (const auto &Matcher : zip(Matchers, B.Matchers)) {
2958 if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher)))
2960 if (std::get<1>(Matcher)->isHigherPriorityThan(*std::get<0>(Matcher)))
2967 unsigned RuleMatcher::countRendererFns() const {
2968 return std::accumulate(
2969 Matchers.begin(), Matchers.end(), 0,
2970 [](unsigned A, const std::unique_ptr<InstructionMatcher> &Matcher) {
2971 return A + Matcher->countRendererFns();
2975 bool OperandPredicateMatcher::isHigherPriorityThan(
2976 const OperandPredicateMatcher &B) const {
2977 // Generally speaking, an instruction is more important than an Int or a
2978 // LiteralInt because it can cover more nodes but theres an exception to
2979 // this. G_CONSTANT's are less important than either of those two because they
2980 // are more permissive.
2982 const InstructionOperandMatcher *AOM =
2983 dyn_cast<InstructionOperandMatcher>(this);
2984 const InstructionOperandMatcher *BOM =
2985 dyn_cast<InstructionOperandMatcher>(&B);
2986 bool AIsConstantInsn = AOM && AOM->getInsnMatcher().isConstantInstruction();
2987 bool BIsConstantInsn = BOM && BOM->getInsnMatcher().isConstantInstruction();
2990 // The relative priorities between a G_CONSTANT and any other instruction
2991 // don't actually matter but this code is needed to ensure a strict weak
2992 // ordering. This is particularly important on Windows where the rules will
2993 // be incorrectly sorted without it.
2994 if (AIsConstantInsn != BIsConstantInsn)
2995 return AIsConstantInsn < BIsConstantInsn;
2999 if (AOM && AIsConstantInsn && (B.Kind == OPM_Int || B.Kind == OPM_LiteralInt))
3001 if (BOM && BIsConstantInsn && (Kind == OPM_Int || Kind == OPM_LiteralInt))
3004 return Kind < B.Kind;
3007 void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
3008 RuleMatcher &Rule) const {
3009 const OperandMatcher &OtherOM = Rule.getOperandMatcher(MatchingName);
3010 unsigned OtherInsnVarID = Rule.getInsnVarID(OtherOM.getInstructionMatcher());
3011 assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getInsnVarID());
3013 Table << MatchTable::Opcode("GIM_CheckIsSameOperand")
3014 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
3015 << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx)
3016 << MatchTable::Comment("OtherMI")
3017 << MatchTable::IntValue(OtherInsnVarID)
3018 << MatchTable::Comment("OtherOpIdx")
3019 << MatchTable::IntValue(OtherOM.getOpIdx())
3020 << MatchTable::LineBreak;
3023 //===- GlobalISelEmitter class --------------------------------------------===//
3025 class GlobalISelEmitter {
3027 explicit GlobalISelEmitter(RecordKeeper &RK);
3028 void run(raw_ostream &OS);
3031 const RecordKeeper &RK;
3032 const CodeGenDAGPatterns CGP;
3033 const CodeGenTarget &Target;
3034 CodeGenRegBank CGRegs;
3036 /// Keep track of the equivalence between SDNodes and Instruction by mapping
3037 /// SDNodes to the GINodeEquiv mapping. We need to map to the GINodeEquiv to
3038 /// check for attributes on the relation such as CheckMMOIsNonAtomic.
3039 /// This is defined using 'GINodeEquiv' in the target description.
3040 DenseMap<Record *, Record *> NodeEquivs;
3042 /// Keep track of the equivalence between ComplexPattern's and
3043 /// GIComplexOperandMatcher. Map entries are specified by subclassing
3044 /// GIComplexPatternEquiv.
3045 DenseMap<const Record *, const Record *> ComplexPatternEquivs;
3047 /// Keep track of the equivalence between SDNodeXForm's and
3048 /// GICustomOperandRenderer. Map entries are specified by subclassing
3049 /// GISDNodeXFormEquiv.
3050 DenseMap<const Record *, const Record *> SDNodeXFormEquivs;
3052 /// Keep track of Scores of PatternsToMatch similar to how the DAG does.
3053 /// This adds compatibility for RuleMatchers to use this for ordering rules.
3054 DenseMap<uint64_t, int> RuleMatcherScores;
3056 // Map of predicates to their subtarget features.
3057 SubtargetFeatureInfoMap SubtargetFeatures;
3059 // Rule coverage information.
3060 Optional<CodeGenCoverage> RuleCoverage;
3062 void gatherOpcodeValues();
3063 void gatherTypeIDValues();
3064 void gatherNodeEquivs();
3066 Record *findNodeEquiv(Record *N) const;
3067 const CodeGenInstruction *getEquivNode(Record &Equiv,
3068 const TreePatternNode *N) const;
3070 Error importRulePredicates(RuleMatcher &M, ArrayRef<Predicate> Predicates);
3071 Expected<InstructionMatcher &>
3072 createAndImportSelDAGMatcher(RuleMatcher &Rule,
3073 InstructionMatcher &InsnMatcher,
3074 const TreePatternNode *Src, unsigned &TempOpIdx);
3075 Error importComplexPatternOperandMatcher(OperandMatcher &OM, Record *R,
3076 unsigned &TempOpIdx) const;
3077 Error importChildMatcher(RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
3078 const TreePatternNode *SrcChild,
3079 bool OperandIsAPointer, unsigned OpIdx,
3080 unsigned &TempOpIdx);
3082 Expected<BuildMIAction &>
3083 createAndImportInstructionRenderer(RuleMatcher &M,
3084 const TreePatternNode *Dst);
3085 Expected<action_iterator> createAndImportSubInstructionRenderer(
3086 action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst,
3088 Expected<action_iterator>
3089 createInstructionRenderer(action_iterator InsertPt, RuleMatcher &M,
3090 const TreePatternNode *Dst);
3091 void importExplicitDefRenderers(BuildMIAction &DstMIBuilder);
3092 Expected<action_iterator>
3093 importExplicitUseRenderers(action_iterator InsertPt, RuleMatcher &M,
3094 BuildMIAction &DstMIBuilder,
3095 const llvm::TreePatternNode *Dst);
3096 Expected<action_iterator>
3097 importExplicitUseRenderer(action_iterator InsertPt, RuleMatcher &Rule,
3098 BuildMIAction &DstMIBuilder,
3099 TreePatternNode *DstChild);
3100 Error importDefaultOperandRenderers(action_iterator InsertPt, RuleMatcher &M,
3101 BuildMIAction &DstMIBuilder,
3102 DagInit *DefaultOps) const;
3104 importImplicitDefRenderers(BuildMIAction &DstMIBuilder,
3105 const std::vector<Record *> &ImplicitDefs) const;
3107 void emitCxxPredicateFns(raw_ostream &OS, StringRef CodeFieldName,
3108 StringRef TypeIdentifier, StringRef ArgType,
3109 StringRef ArgName, StringRef AdditionalDeclarations,
3110 std::function<bool(const Record *R)> Filter);
3111 void emitImmPredicateFns(raw_ostream &OS, StringRef TypeIdentifier,
3113 std::function<bool(const Record *R)> Filter);
3114 void emitMIPredicateFns(raw_ostream &OS);
3116 /// Analyze pattern \p P, returning a matcher for it if possible.
3117 /// Otherwise, return an Error explaining why we don't support it.
3118 Expected<RuleMatcher> runOnPattern(const PatternToMatch &P);
3120 void declareSubtargetFeature(Record *Predicate);
3122 MatchTable buildMatchTable(MutableArrayRef<RuleMatcher> Rules, bool Optimize,
3126 /// Takes a sequence of \p Rules and group them based on the predicates
3127 /// they share. \p MatcherStorage is used as a memory container
3128 /// for the group that are created as part of this process.
3130 /// What this optimization does looks like if GroupT = GroupMatcher:
3131 /// Output without optimization:
3138 /// # predicate A // <-- effectively this is going to be checked twice.
3139 /// // Once in R1 and once in R2.
3142 /// Output with optimization:
3145 /// # predicate A // <-- Check is now shared.
3151 template <class GroupT>
3152 static std::vector<Matcher *> optimizeRules(
3153 ArrayRef<Matcher *> Rules,
3154 std::vector<std::unique_ptr<Matcher>> &MatcherStorage);
3157 void GlobalISelEmitter::gatherOpcodeValues() {
3158 InstructionOpcodeMatcher::initOpcodeValuesMap(Target);
3161 void GlobalISelEmitter::gatherTypeIDValues() {
3162 LLTOperandMatcher::initTypeIDValuesMap();
3165 void GlobalISelEmitter::gatherNodeEquivs() {
3166 assert(NodeEquivs.empty());
3167 for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
3168 NodeEquivs[Equiv->getValueAsDef("Node")] = Equiv;
3170 assert(ComplexPatternEquivs.empty());
3171 for (Record *Equiv : RK.getAllDerivedDefinitions("GIComplexPatternEquiv")) {
3172 Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
3175 ComplexPatternEquivs[SelDAGEquiv] = Equiv;
3178 assert(SDNodeXFormEquivs.empty());
3179 for (Record *Equiv : RK.getAllDerivedDefinitions("GISDNodeXFormEquiv")) {
3180 Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
3183 SDNodeXFormEquivs[SelDAGEquiv] = Equiv;
3187 Record *GlobalISelEmitter::findNodeEquiv(Record *N) const {
3188 return NodeEquivs.lookup(N);
3191 const CodeGenInstruction *
3192 GlobalISelEmitter::getEquivNode(Record &Equiv, const TreePatternNode *N) const {
3193 for (const TreePredicateCall &Call : N->getPredicateCalls()) {
3194 const TreePredicateFn &Predicate = Call.Fn;
3195 if (!Equiv.isValueUnset("IfSignExtend") && Predicate.isLoad() &&
3196 Predicate.isSignExtLoad())
3197 return &Target.getInstruction(Equiv.getValueAsDef("IfSignExtend"));
3198 if (!Equiv.isValueUnset("IfZeroExtend") && Predicate.isLoad() &&
3199 Predicate.isZeroExtLoad())
3200 return &Target.getInstruction(Equiv.getValueAsDef("IfZeroExtend"));
3202 return &Target.getInstruction(Equiv.getValueAsDef("I"));
3205 GlobalISelEmitter::GlobalISelEmitter(RecordKeeper &RK)
3206 : RK(RK), CGP(RK), Target(CGP.getTargetInfo()),
3207 CGRegs(RK, Target.getHwModes()) {}
3209 //===- Emitter ------------------------------------------------------------===//
3212 GlobalISelEmitter::importRulePredicates(RuleMatcher &M,
3213 ArrayRef<Predicate> Predicates) {
3214 for (const Predicate &P : Predicates) {
3217 declareSubtargetFeature(P.Def);
3218 M.addRequiredFeature(P.Def);
3221 return Error::success();
3224 Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher(
3225 RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
3226 const TreePatternNode *Src, unsigned &TempOpIdx) {
3227 Record *SrcGIEquivOrNull = nullptr;
3228 const CodeGenInstruction *SrcGIOrNull = nullptr;
3230 // Start with the defined operands (i.e., the results of the root operator).
3231 if (Src->getExtTypes().size() > 1)
3232 return failedImport("Src pattern has multiple results");
3234 if (Src->isLeaf()) {
3235 Init *SrcInit = Src->getLeafValue();
3236 if (isa<IntInit>(SrcInit)) {
3237 InsnMatcher.addPredicate<InstructionOpcodeMatcher>(
3238 &Target.getInstruction(RK.getDef("G_CONSTANT")));
3240 return failedImport(
3241 "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
3243 SrcGIEquivOrNull = findNodeEquiv(Src->getOperator());
3244 if (!SrcGIEquivOrNull)
3245 return failedImport("Pattern operator lacks an equivalent Instruction" +
3246 explainOperator(Src->getOperator()));
3247 SrcGIOrNull = getEquivNode(*SrcGIEquivOrNull, Src);
3249 // The operators look good: match the opcode
3250 InsnMatcher.addPredicate<InstructionOpcodeMatcher>(SrcGIOrNull);
3254 for (const TypeSetByHwMode &VTy : Src->getExtTypes()) {
3255 // Results don't have a name unless they are the root node. The caller will
3256 // set the name if appropriate.
3257 OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
3258 if (auto Error = OM.addTypeCheckPredicate(VTy, false /* OperandIsAPointer */))
3259 return failedImport(toString(std::move(Error)) +
3260 " for result of Src pattern operator");
3263 for (const TreePredicateCall &Call : Src->getPredicateCalls()) {
3264 const TreePredicateFn &Predicate = Call.Fn;
3265 if (Predicate.isAlwaysTrue())
3268 if (Predicate.isImmediatePattern()) {
3269 InsnMatcher.addPredicate<InstructionImmPredicateMatcher>(Predicate);
3273 // An address space check is needed in all contexts if there is one.
3274 if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
3275 if (const ListInit *AddrSpaces = Predicate.getAddressSpaces()) {
3276 SmallVector<unsigned, 4> ParsedAddrSpaces;
3278 for (Init *Val : AddrSpaces->getValues()) {
3279 IntInit *IntVal = dyn_cast<IntInit>(Val);
3281 return failedImport("Address space is not an integer");
3282 ParsedAddrSpaces.push_back(IntVal->getValue());
3285 if (!ParsedAddrSpaces.empty()) {
3286 InsnMatcher.addPredicate<MemoryAddressSpacePredicateMatcher>(
3287 0, ParsedAddrSpaces);
3292 // G_LOAD is used for both non-extending and any-extending loads.
3293 if (Predicate.isLoad() && Predicate.isNonExtLoad()) {
3294 InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3295 0, MemoryVsLLTSizePredicateMatcher::EqualTo, 0);
3298 if (Predicate.isLoad() && Predicate.isAnyExtLoad()) {
3299 InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3300 0, MemoryVsLLTSizePredicateMatcher::LessThan, 0);
3304 if (Predicate.isStore() && Predicate.isTruncStore()) {
3305 // FIXME: If MemoryVT is set, we end up with 2 checks for the MMO size.
3306 InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3307 0, MemoryVsLLTSizePredicateMatcher::LessThan, 0);
3311 // No check required. We already did it by swapping the opcode.
3312 if (!SrcGIEquivOrNull->isValueUnset("IfSignExtend") &&
3313 Predicate.isSignExtLoad())
3316 // No check required. We already did it by swapping the opcode.
3317 if (!SrcGIEquivOrNull->isValueUnset("IfZeroExtend") &&
3318 Predicate.isZeroExtLoad())
3321 // No check required. G_STORE by itself is a non-extending store.
3322 if (Predicate.isNonTruncStore())
3325 if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
3326 if (Predicate.getMemoryVT() != nullptr) {
3327 Optional<LLTCodeGen> MemTyOrNone =
3328 MVTToLLT(getValueType(Predicate.getMemoryVT()));
3331 return failedImport("MemVT could not be converted to LLT");
3333 // MMO's work in bytes so we must take care of unusual types like i1
3334 // don't round down.
3335 unsigned MemSizeInBits =
3336 llvm::alignTo(MemTyOrNone->get().getSizeInBits(), 8);
3338 InsnMatcher.addPredicate<MemorySizePredicateMatcher>(
3339 0, MemSizeInBits / 8);
3344 if (Predicate.isLoad() || Predicate.isStore()) {
3345 // No check required. A G_LOAD/G_STORE is an unindexed load.
3346 if (Predicate.isUnindexed())
3350 if (Predicate.isAtomic()) {
3351 if (Predicate.isAtomicOrderingMonotonic()) {
3352 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3356 if (Predicate.isAtomicOrderingAcquire()) {
3357 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Acquire");
3360 if (Predicate.isAtomicOrderingRelease()) {
3361 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Release");
3364 if (Predicate.isAtomicOrderingAcquireRelease()) {
3365 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3369 if (Predicate.isAtomicOrderingSequentiallyConsistent()) {
3370 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3371 "SequentiallyConsistent");
3375 if (Predicate.isAtomicOrderingAcquireOrStronger()) {
3376 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3377 "Acquire", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
3380 if (Predicate.isAtomicOrderingWeakerThanAcquire()) {
3381 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3382 "Acquire", AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
3386 if (Predicate.isAtomicOrderingReleaseOrStronger()) {
3387 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3388 "Release", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
3391 if (Predicate.isAtomicOrderingWeakerThanRelease()) {
3392 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3393 "Release", AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
3398 if (Predicate.hasGISelPredicateCode()) {
3399 InsnMatcher.addPredicate<GenericInstructionPredicateMatcher>(Predicate);
3403 return failedImport("Src pattern child has predicate (" +
3404 explainPredicates(Src) + ")");
3406 if (SrcGIEquivOrNull && SrcGIEquivOrNull->getValueAsBit("CheckMMOIsNonAtomic"))
3407 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("NotAtomic");
3409 if (Src->isLeaf()) {
3410 Init *SrcInit = Src->getLeafValue();
3411 if (IntInit *SrcIntInit = dyn_cast<IntInit>(SrcInit)) {
3412 OperandMatcher &OM =
3413 InsnMatcher.addOperand(OpIdx++, Src->getName(), TempOpIdx);
3414 OM.addPredicate<LiteralIntOperandMatcher>(SrcIntInit->getValue());
3416 return failedImport(
3417 "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
3419 assert(SrcGIOrNull &&
3420 "Expected to have already found an equivalent Instruction");
3421 if (SrcGIOrNull->TheDef->getName() == "G_CONSTANT" ||
3422 SrcGIOrNull->TheDef->getName() == "G_FCONSTANT") {
3423 // imm/fpimm still have operands but we don't need to do anything with it
3424 // here since we don't support ImmLeaf predicates yet. However, we still
3425 // need to note the hidden operand to get GIM_CheckNumOperands correct.
3426 InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
3430 // Match the used operands (i.e. the children of the operator).
3431 for (unsigned i = 0, e = Src->getNumChildren(); i != e; ++i) {
3432 TreePatternNode *SrcChild = Src->getChild(i);
3434 // SelectionDAG allows pointers to be represented with iN since it doesn't
3435 // distinguish between pointers and integers but they are different types in GlobalISel.
3436 // Coerce integers to pointers to address space 0 if the context indicates a pointer.
3437 bool OperandIsAPointer = SrcGIOrNull->isOperandAPointer(i);
3439 // For G_INTRINSIC/G_INTRINSIC_W_SIDE_EFFECTS, the operand immediately
3440 // following the defs is an intrinsic ID.
3441 if ((SrcGIOrNull->TheDef->getName() == "G_INTRINSIC" ||
3442 SrcGIOrNull->TheDef->getName() == "G_INTRINSIC_W_SIDE_EFFECTS") &&
3444 if (const CodeGenIntrinsic *II = Src->getIntrinsicInfo(CGP)) {
3445 OperandMatcher &OM =
3446 InsnMatcher.addOperand(OpIdx++, SrcChild->getName(), TempOpIdx);
3447 OM.addPredicate<IntrinsicIDOperandMatcher>(II);
3451 return failedImport("Expected IntInit containing instrinsic ID)");
3455 importChildMatcher(Rule, InsnMatcher, SrcChild, OperandIsAPointer,
3456 OpIdx++, TempOpIdx))
3457 return std::move(Error);
3464 Error GlobalISelEmitter::importComplexPatternOperandMatcher(
3465 OperandMatcher &OM, Record *R, unsigned &TempOpIdx) const {
3466 const auto &ComplexPattern = ComplexPatternEquivs.find(R);
3467 if (ComplexPattern == ComplexPatternEquivs.end())
3468 return failedImport("SelectionDAG ComplexPattern (" + R->getName() +
3469 ") not mapped to GlobalISel");
3471 OM.addPredicate<ComplexPatternOperandMatcher>(OM, *ComplexPattern->second);
3473 return Error::success();
3476 Error GlobalISelEmitter::importChildMatcher(RuleMatcher &Rule,
3477 InstructionMatcher &InsnMatcher,
3478 const TreePatternNode *SrcChild,
3479 bool OperandIsAPointer,
3481 unsigned &TempOpIdx) {
3482 OperandMatcher &OM =
3483 InsnMatcher.addOperand(OpIdx, SrcChild->getName(), TempOpIdx);
3484 if (OM.isSameAsAnotherOperand())
3485 return Error::success();
3487 ArrayRef<TypeSetByHwMode> ChildTypes = SrcChild->getExtTypes();
3488 if (ChildTypes.size() != 1)
3489 return failedImport("Src pattern child has multiple results");
3491 // Check MBB's before the type check since they are not a known type.
3492 if (!SrcChild->isLeaf()) {
3493 if (SrcChild->getOperator()->isSubClassOf("SDNode")) {
3494 auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator());
3495 if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
3496 OM.addPredicate<MBBOperandMatcher>();
3497 return Error::success();
3503 OM.addTypeCheckPredicate(ChildTypes.front(), OperandIsAPointer))
3504 return failedImport(toString(std::move(Error)) + " for Src operand (" +
3505 to_string(*SrcChild) + ")");
3507 // Check for nested instructions.
3508 if (!SrcChild->isLeaf()) {
3509 if (SrcChild->getOperator()->isSubClassOf("ComplexPattern")) {
3510 // When a ComplexPattern is used as an operator, it should do the same
3511 // thing as when used as a leaf. However, the children of the operator
3512 // name the sub-operands that make up the complex operand and we must
3513 // prepare to reference them in the renderer too.
3514 unsigned RendererID = TempOpIdx;
3515 if (auto Error = importComplexPatternOperandMatcher(
3516 OM, SrcChild->getOperator(), TempOpIdx))
3519 for (unsigned i = 0, e = SrcChild->getNumChildren(); i != e; ++i) {
3520 auto *SubOperand = SrcChild->getChild(i);
3521 if (!SubOperand->getName().empty()) {
3522 if (auto Error = Rule.defineComplexSubOperand(SubOperand->getName(),
3523 SrcChild->getOperator(),
3529 return Error::success();
3532 auto MaybeInsnOperand = OM.addPredicate<InstructionOperandMatcher>(
3533 InsnMatcher.getRuleMatcher(), SrcChild->getName());
3534 if (!MaybeInsnOperand.hasValue()) {
3535 // This isn't strictly true. If the user were to provide exactly the same
3536 // matchers as the original operand then we could allow it. However, it's
3537 // simpler to not permit the redundant specification.
3538 return failedImport("Nested instruction cannot be the same as another operand");
3541 // Map the node to a gMIR instruction.
3542 InstructionOperandMatcher &InsnOperand = **MaybeInsnOperand;
3543 auto InsnMatcherOrError = createAndImportSelDAGMatcher(
3544 Rule, InsnOperand.getInsnMatcher(), SrcChild, TempOpIdx);
3545 if (auto Error = InsnMatcherOrError.takeError())
3548 return Error::success();
3551 if (SrcChild->hasAnyPredicate())
3552 return failedImport("Src pattern child has unsupported predicate");
3554 // Check for constant immediates.
3555 if (auto *ChildInt = dyn_cast<IntInit>(SrcChild->getLeafValue())) {
3556 OM.addPredicate<ConstantIntOperandMatcher>(ChildInt->getValue());
3557 return Error::success();
3560 // Check for def's like register classes or ComplexPattern's.
3561 if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
3562 auto *ChildRec = ChildDefInit->getDef();
3564 // Check for register classes.
3565 if (ChildRec->isSubClassOf("RegisterClass") ||
3566 ChildRec->isSubClassOf("RegisterOperand")) {
3567 OM.addPredicate<RegisterBankOperandMatcher>(
3568 Target.getRegisterClass(getInitValueAsRegClass(ChildDefInit)));
3569 return Error::success();
3572 // Check for ValueType.
3573 if (ChildRec->isSubClassOf("ValueType")) {
3574 // We already added a type check as standard practice so this doesn't need
3576 return Error::success();
3579 // Check for ComplexPattern's.
3580 if (ChildRec->isSubClassOf("ComplexPattern"))
3581 return importComplexPatternOperandMatcher(OM, ChildRec, TempOpIdx);
3583 if (ChildRec->isSubClassOf("ImmLeaf")) {
3584 return failedImport(
3585 "Src pattern child def is an unsupported tablegen class (ImmLeaf)");
3588 return failedImport(
3589 "Src pattern child def is an unsupported tablegen class");
3592 return failedImport("Src pattern child is an unsupported kind");
3595 Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderer(
3596 action_iterator InsertPt, RuleMatcher &Rule, BuildMIAction &DstMIBuilder,
3597 TreePatternNode *DstChild) {
3599 const auto &SubOperand = Rule.getComplexSubOperand(DstChild->getName());
3600 if (SubOperand.hasValue()) {
3601 DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
3602 *std::get<0>(*SubOperand), DstChild->getName(),
3603 std::get<1>(*SubOperand), std::get<2>(*SubOperand));
3607 if (!DstChild->isLeaf()) {
3609 if (DstChild->getOperator()->isSubClassOf("SDNodeXForm")) {
3610 auto Child = DstChild->getChild(0);
3611 auto I = SDNodeXFormEquivs.find(DstChild->getOperator());
3612 if (I != SDNodeXFormEquivs.end()) {
3613 DstMIBuilder.addRenderer<CustomRenderer>(*I->second, Child->getName());
3616 return failedImport("SDNodeXForm " + Child->getName() +
3617 " has no custom renderer");
3620 // We accept 'bb' here. It's an operator because BasicBlockSDNode isn't
3621 // inline, but in MI it's just another operand.
3622 if (DstChild->getOperator()->isSubClassOf("SDNode")) {
3623 auto &ChildSDNI = CGP.getSDNodeInfo(DstChild->getOperator());
3624 if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
3625 DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
3630 // Similarly, imm is an operator in TreePatternNode's view but must be
3631 // rendered as operands.
3632 // FIXME: The target should be able to choose sign-extended when appropriate
3634 if (DstChild->getOperator()->getName() == "imm") {
3635 DstMIBuilder.addRenderer<CopyConstantAsImmRenderer>(DstChild->getName());
3637 } else if (DstChild->getOperator()->getName() == "fpimm") {
3638 DstMIBuilder.addRenderer<CopyFConstantAsFPImmRenderer>(
3639 DstChild->getName());
3643 if (DstChild->getOperator()->isSubClassOf("Instruction")) {
3644 ArrayRef<TypeSetByHwMode> ChildTypes = DstChild->getExtTypes();
3645 if (ChildTypes.size() != 1)
3646 return failedImport("Dst pattern child has multiple results");
3648 Optional<LLTCodeGen> OpTyOrNone = None;
3649 if (ChildTypes.front().isMachineValueType())
3651 MVTToLLT(ChildTypes.front().getMachineValueType().SimpleTy);
3653 return failedImport("Dst operand has an unsupported type");
3655 unsigned TempRegID = Rule.allocateTempRegID();
3656 InsertPt = Rule.insertAction<MakeTempRegisterAction>(
3657 InsertPt, OpTyOrNone.getValue(), TempRegID);
3658 DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
3660 auto InsertPtOrError = createAndImportSubInstructionRenderer(
3661 ++InsertPt, Rule, DstChild, TempRegID);
3662 if (auto Error = InsertPtOrError.takeError())
3663 return std::move(Error);
3664 return InsertPtOrError.get();
3667 return failedImport("Dst pattern child isn't a leaf node or an MBB" + llvm::to_string(*DstChild));
3670 // It could be a specific immediate in which case we should just check for
3672 if (const IntInit *ChildIntInit =
3673 dyn_cast<IntInit>(DstChild->getLeafValue())) {
3674 DstMIBuilder.addRenderer<ImmRenderer>(ChildIntInit->getValue());
3678 // Otherwise, we're looking for a bog-standard RegisterClass operand.
3679 if (auto *ChildDefInit = dyn_cast<DefInit>(DstChild->getLeafValue())) {
3680 auto *ChildRec = ChildDefInit->getDef();
3682 ArrayRef<TypeSetByHwMode> ChildTypes = DstChild->getExtTypes();
3683 if (ChildTypes.size() != 1)
3684 return failedImport("Dst pattern child has multiple results");
3686 Optional<LLTCodeGen> OpTyOrNone = None;
3687 if (ChildTypes.front().isMachineValueType())
3688 OpTyOrNone = MVTToLLT(ChildTypes.front().getMachineValueType().SimpleTy);
3690 return failedImport("Dst operand has an unsupported type");
3692 if (ChildRec->isSubClassOf("Register")) {
3693 DstMIBuilder.addRenderer<AddRegisterRenderer>(ChildRec);
3697 if (ChildRec->isSubClassOf("RegisterClass") ||
3698 ChildRec->isSubClassOf("RegisterOperand") ||
3699 ChildRec->isSubClassOf("ValueType")) {
3700 if (ChildRec->isSubClassOf("RegisterOperand") &&
3701 !ChildRec->isValueUnset("GIZeroRegister")) {
3702 DstMIBuilder.addRenderer<CopyOrAddZeroRegRenderer>(
3703 DstChild->getName(), ChildRec->getValueAsDef("GIZeroRegister"));
3707 DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
3711 if (ChildRec->isSubClassOf("ComplexPattern")) {
3712 const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
3713 if (ComplexPattern == ComplexPatternEquivs.end())
3714 return failedImport(
3715 "SelectionDAG ComplexPattern not mapped to GlobalISel");
3717 const OperandMatcher &OM = Rule.getOperandMatcher(DstChild->getName());
3718 DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
3719 *ComplexPattern->second, DstChild->getName(),
3720 OM.getAllocatedTemporariesBaseID());
3724 return failedImport(
3725 "Dst pattern child def is an unsupported tablegen class");
3728 return failedImport("Dst pattern child is an unsupported kind");
3731 Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
3732 RuleMatcher &M, const TreePatternNode *Dst) {
3733 auto InsertPtOrError = createInstructionRenderer(M.actions_end(), M, Dst);
3734 if (auto Error = InsertPtOrError.takeError())
3735 return std::move(Error);
3737 action_iterator InsertPt = InsertPtOrError.get();
3738 BuildMIAction &DstMIBuilder = *static_cast<BuildMIAction *>(InsertPt->get());
3740 importExplicitDefRenderers(DstMIBuilder);
3742 if (auto Error = importExplicitUseRenderers(InsertPt, M, DstMIBuilder, Dst)
3744 return std::move(Error);
3746 return DstMIBuilder;
3749 Expected<action_iterator>
3750 GlobalISelEmitter::createAndImportSubInstructionRenderer(
3751 const action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst,
3752 unsigned TempRegID) {
3753 auto InsertPtOrError = createInstructionRenderer(InsertPt, M, Dst);
3755 // TODO: Assert there's exactly one result.
3757 if (auto Error = InsertPtOrError.takeError())
3758 return std::move(Error);
3760 BuildMIAction &DstMIBuilder =
3761 *static_cast<BuildMIAction *>(InsertPtOrError.get()->get());
3763 // Assign the result to TempReg.
3764 DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID, true);
3767 importExplicitUseRenderers(InsertPtOrError.get(), M, DstMIBuilder, Dst);
3768 if (auto Error = InsertPtOrError.takeError())
3769 return std::move(Error);
3771 M.insertAction<ConstrainOperandsToDefinitionAction>(InsertPt,
3772 DstMIBuilder.getInsnID());
3773 return InsertPtOrError.get();
3776 Expected<action_iterator> GlobalISelEmitter::createInstructionRenderer(
3777 action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst) {
3778 Record *DstOp = Dst->getOperator();
3779 if (!DstOp->isSubClassOf("Instruction")) {
3780 if (DstOp->isSubClassOf("ValueType"))
3781 return failedImport(
3782 "Pattern operator isn't an instruction (it's a ValueType)");
3783 return failedImport("Pattern operator isn't an instruction");
3785 CodeGenInstruction *DstI = &Target.getInstruction(DstOp);
3787 // COPY_TO_REGCLASS is just a copy with a ConstrainOperandToRegClassAction
3788 // attached. Similarly for EXTRACT_SUBREG except that's a subregister copy.
3789 if (DstI->TheDef->getName() == "COPY_TO_REGCLASS")
3790 DstI = &Target.getInstruction(RK.getDef("COPY"));
3791 else if (DstI->TheDef->getName() == "EXTRACT_SUBREG")
3792 DstI = &Target.getInstruction(RK.getDef("COPY"));
3793 else if (DstI->TheDef->getName() == "REG_SEQUENCE")
3794 return failedImport("Unable to emit REG_SEQUENCE");
3796 return M.insertAction<BuildMIAction>(InsertPt, M.allocateOutputInsnID(),
3800 void GlobalISelEmitter::importExplicitDefRenderers(
3801 BuildMIAction &DstMIBuilder) {
3802 const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
3803 for (unsigned I = 0; I < DstI->Operands.NumDefs; ++I) {
3804 const CGIOperandList::OperandInfo &DstIOperand = DstI->Operands[I];
3805 DstMIBuilder.addRenderer<CopyRenderer>(DstIOperand.Name);
3809 Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderers(
3810 action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
3811 const llvm::TreePatternNode *Dst) {
3812 const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
3813 CodeGenInstruction *OrigDstI = &Target.getInstruction(Dst->getOperator());
3815 // EXTRACT_SUBREG needs to use a subregister COPY.
3816 if (OrigDstI->TheDef->getName() == "EXTRACT_SUBREG") {
3817 if (!Dst->getChild(0)->isLeaf())
3818 return failedImport("EXTRACT_SUBREG child #1 is not a leaf");
3820 if (DefInit *SubRegInit =
3821 dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue())) {
3822 Record *RCDef = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
3824 return failedImport("EXTRACT_SUBREG child #0 could not "
3825 "be coerced to a register class");
3827 CodeGenRegisterClass *RC = CGRegs.getRegClass(RCDef);
3828 CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
3830 const auto &SrcRCDstRCPair =
3831 RC->getMatchingSubClassWithSubRegs(CGRegs, SubIdx);
3832 if (SrcRCDstRCPair.hasValue()) {
3833 assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
3834 if (SrcRCDstRCPair->first != RC)
3835 return failedImport("EXTRACT_SUBREG requires an additional COPY");
3838 DstMIBuilder.addRenderer<CopySubRegRenderer>(Dst->getChild(0)->getName(),
3843 return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
3846 // Render the explicit uses.
3847 unsigned DstINumUses = OrigDstI->Operands.size() - OrigDstI->Operands.NumDefs;
3848 unsigned ExpectedDstINumUses = Dst->getNumChildren();
3849 if (OrigDstI->TheDef->getName() == "COPY_TO_REGCLASS") {
3850 DstINumUses--; // Ignore the class constraint.
3851 ExpectedDstINumUses--;
3855 unsigned NumDefaultOps = 0;
3856 for (unsigned I = 0; I != DstINumUses; ++I) {
3857 const CGIOperandList::OperandInfo &DstIOperand =
3858 DstI->Operands[DstI->Operands.NumDefs + I];
3860 // If the operand has default values, introduce them now.
3861 // FIXME: Until we have a decent test case that dictates we should do
3862 // otherwise, we're going to assume that operands with default values cannot
3863 // be specified in the patterns. Therefore, adding them will not cause us to
3864 // end up with too many rendered operands.
3865 if (DstIOperand.Rec->isSubClassOf("OperandWithDefaultOps")) {
3866 DagInit *DefaultOps = DstIOperand.Rec->getValueAsDag("DefaultOps");
3867 if (auto Error = importDefaultOperandRenderers(
3868 InsertPt, M, DstMIBuilder, DefaultOps))
3869 return std::move(Error);
3874 auto InsertPtOrError = importExplicitUseRenderer(InsertPt, M, DstMIBuilder,
3875 Dst->getChild(Child));
3876 if (auto Error = InsertPtOrError.takeError())
3877 return std::move(Error);
3878 InsertPt = InsertPtOrError.get();
3882 if (NumDefaultOps + ExpectedDstINumUses != DstINumUses)
3883 return failedImport("Expected " + llvm::to_string(DstINumUses) +
3884 " used operands but found " +
3885 llvm::to_string(ExpectedDstINumUses) +
3886 " explicit ones and " + llvm::to_string(NumDefaultOps) +
3892 Error GlobalISelEmitter::importDefaultOperandRenderers(
3893 action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
3894 DagInit *DefaultOps) const {
3895 for (const auto *DefaultOp : DefaultOps->getArgs()) {
3896 Optional<LLTCodeGen> OpTyOrNone = None;
3898 // Look through ValueType operators.
3899 if (const DagInit *DefaultDagOp = dyn_cast<DagInit>(DefaultOp)) {
3900 if (const DefInit *DefaultDagOperator =
3901 dyn_cast<DefInit>(DefaultDagOp->getOperator())) {
3902 if (DefaultDagOperator->getDef()->isSubClassOf("ValueType")) {
3903 OpTyOrNone = MVTToLLT(getValueType(
3904 DefaultDagOperator->getDef()));
3905 DefaultOp = DefaultDagOp->getArg(0);
3910 if (const DefInit *DefaultDefOp = dyn_cast<DefInit>(DefaultOp)) {
3911 auto Def = DefaultDefOp->getDef();
3912 if (Def->getName() == "undef_tied_input") {
3913 unsigned TempRegID = M.allocateTempRegID();
3914 M.insertAction<MakeTempRegisterAction>(
3915 InsertPt, OpTyOrNone.getValue(), TempRegID);
3916 InsertPt = M.insertAction<BuildMIAction>(
3917 InsertPt, M.allocateOutputInsnID(),
3918 &Target.getInstruction(RK.getDef("IMPLICIT_DEF")));
3919 BuildMIAction &IDMIBuilder = *static_cast<BuildMIAction *>(
3921 IDMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
3922 DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
3924 DstMIBuilder.addRenderer<AddRegisterRenderer>(Def);
3929 if (const IntInit *DefaultIntOp = dyn_cast<IntInit>(DefaultOp)) {
3930 DstMIBuilder.addRenderer<ImmRenderer>(DefaultIntOp->getValue());
3934 return failedImport("Could not add default op");
3937 return Error::success();
3940 Error GlobalISelEmitter::importImplicitDefRenderers(
3941 BuildMIAction &DstMIBuilder,
3942 const std::vector<Record *> &ImplicitDefs) const {
3943 if (!ImplicitDefs.empty())
3944 return failedImport("Pattern defines a physical register");
3945 return Error::success();
3948 Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
3949 // Keep track of the matchers and actions to emit.
3950 int Score = P.getPatternComplexity(CGP);
3951 RuleMatcher M(P.getSrcRecord()->getLoc());
3952 RuleMatcherScores[M.getRuleID()] = Score;
3953 M.addAction<DebugCommentAction>(llvm::to_string(*P.getSrcPattern()) +
3955 llvm::to_string(*P.getDstPattern()));
3957 if (auto Error = importRulePredicates(M, P.getPredicates()))
3958 return std::move(Error);
3960 // Next, analyze the pattern operators.
3961 TreePatternNode *Src = P.getSrcPattern();
3962 TreePatternNode *Dst = P.getDstPattern();
3964 // If the root of either pattern isn't a simple operator, ignore it.
3965 if (auto Err = isTrivialOperatorNode(Dst))
3966 return failedImport("Dst pattern root isn't a trivial operator (" +
3967 toString(std::move(Err)) + ")");
3968 if (auto Err = isTrivialOperatorNode(Src))
3969 return failedImport("Src pattern root isn't a trivial operator (" +
3970 toString(std::move(Err)) + ")");
3972 // The different predicates and matchers created during
3973 // addInstructionMatcher use the RuleMatcher M to set up their
3974 // instruction ID (InsnVarID) that are going to be used when
3975 // M is going to be emitted.
3976 // However, the code doing the emission still relies on the IDs
3977 // returned during that process by the RuleMatcher when issuing
3978 // the recordInsn opcodes.
3980 // 1. The order in which we created the predicates
3981 // and such must be the same as the order in which we emit them,
3983 // 2. We need to reset the generation of the IDs in M somewhere between
3984 // addInstructionMatcher and emit
3986 // FIXME: Long term, we don't want to have to rely on this implicit
3987 // naming being the same. One possible solution would be to have
3988 // explicit operator for operation capture and reference those.
3989 // The plus side is that it would expose opportunities to share
3990 // the capture accross rules. The downside is that it would
3991 // introduce a dependency between predicates (captures must happen
3992 // before their first use.)
3993 InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher(Src->getName());
3994 unsigned TempOpIdx = 0;
3995 auto InsnMatcherOrError =
3996 createAndImportSelDAGMatcher(M, InsnMatcherTemp, Src, TempOpIdx);
3997 if (auto Error = InsnMatcherOrError.takeError())
3998 return std::move(Error);
3999 InstructionMatcher &InsnMatcher = InsnMatcherOrError.get();
4001 if (Dst->isLeaf()) {
4002 Record *RCDef = getInitValueAsRegClass(Dst->getLeafValue());
4004 const CodeGenRegisterClass &RC = Target.getRegisterClass(RCDef);
4006 // We need to replace the def and all its uses with the specified
4007 // operand. However, we must also insert COPY's wherever needed.
4008 // For now, emit a copy and let the register allocator clean up.
4009 auto &DstI = Target.getInstruction(RK.getDef("COPY"));
4010 const auto &DstIOperand = DstI.Operands[0];
4012 OperandMatcher &OM0 = InsnMatcher.getOperand(0);
4013 OM0.setSymbolicName(DstIOperand.Name);
4014 M.defineOperand(OM0.getSymbolicName(), OM0);
4015 OM0.addPredicate<RegisterBankOperandMatcher>(RC);
4017 auto &DstMIBuilder =
4018 M.addAction<BuildMIAction>(M.allocateOutputInsnID(), &DstI);
4019 DstMIBuilder.addRenderer<CopyRenderer>(DstIOperand.Name);
4020 DstMIBuilder.addRenderer<CopyRenderer>(Dst->getName());
4021 M.addAction<ConstrainOperandToRegClassAction>(0, 0, RC);
4023 // We're done with this pattern! It's eligible for GISel emission; return
4025 ++NumPatternImported;
4026 return std::move(M);
4029 return failedImport("Dst pattern root isn't a known leaf");
4032 // Start with the defined operands (i.e., the results of the root operator).
4033 Record *DstOp = Dst->getOperator();
4034 if (!DstOp->isSubClassOf("Instruction"))
4035 return failedImport("Pattern operator isn't an instruction");
4037 auto &DstI = Target.getInstruction(DstOp);
4038 if (DstI.Operands.NumDefs != Src->getExtTypes().size())
4039 return failedImport("Src pattern results and dst MI defs are different (" +
4040 to_string(Src->getExtTypes().size()) + " def(s) vs " +
4041 to_string(DstI.Operands.NumDefs) + " def(s))");
4043 // The root of the match also has constraints on the register bank so that it
4044 // matches the result instruction.
4046 for (const TypeSetByHwMode &VTy : Src->getExtTypes()) {
4049 const auto &DstIOperand = DstI.Operands[OpIdx];
4050 Record *DstIOpRec = DstIOperand.Rec;
4051 if (DstI.TheDef->getName() == "COPY_TO_REGCLASS") {
4052 DstIOpRec = getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());
4054 if (DstIOpRec == nullptr)
4055 return failedImport(
4056 "COPY_TO_REGCLASS operand #1 isn't a register class");
4057 } else if (DstI.TheDef->getName() == "EXTRACT_SUBREG") {
4058 if (!Dst->getChild(0)->isLeaf())
4059 return failedImport("EXTRACT_SUBREG operand #0 isn't a leaf");
4061 // We can assume that a subregister is in the same bank as it's super
4063 DstIOpRec = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
4065 if (DstIOpRec == nullptr)
4066 return failedImport(
4067 "EXTRACT_SUBREG operand #0 isn't a register class");
4068 } else if (DstIOpRec->isSubClassOf("RegisterOperand"))
4069 DstIOpRec = DstIOpRec->getValueAsDef("RegClass");
4070 else if (!DstIOpRec->isSubClassOf("RegisterClass"))
4071 return failedImport("Dst MI def isn't a register class" +
4074 OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
4075 OM.setSymbolicName(DstIOperand.Name);
4076 M.defineOperand(OM.getSymbolicName(), OM);
4077 OM.addPredicate<RegisterBankOperandMatcher>(
4078 Target.getRegisterClass(DstIOpRec));
4082 auto DstMIBuilderOrError = createAndImportInstructionRenderer(M, Dst);
4083 if (auto Error = DstMIBuilderOrError.takeError())
4084 return std::move(Error);
4085 BuildMIAction &DstMIBuilder = DstMIBuilderOrError.get();
4087 // Render the implicit defs.
4088 // These are only added to the root of the result.
4089 if (auto Error = importImplicitDefRenderers(DstMIBuilder, P.getDstRegs()))
4090 return std::move(Error);
4092 DstMIBuilder.chooseInsnToMutate(M);
4094 // Constrain the registers to classes. This is normally derived from the
4095 // emitted instruction but a few instructions require special handling.
4096 if (DstI.TheDef->getName() == "COPY_TO_REGCLASS") {
4097 // COPY_TO_REGCLASS does not provide operand constraints itself but the
4098 // result is constrained to the class given by the second child.
4100 getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());
4102 if (DstIOpRec == nullptr)
4103 return failedImport("COPY_TO_REGCLASS operand #1 isn't a register class");
4105 M.addAction<ConstrainOperandToRegClassAction>(
4106 0, 0, Target.getRegisterClass(DstIOpRec));
4108 // We're done with this pattern! It's eligible for GISel emission; return
4110 ++NumPatternImported;
4111 return std::move(M);
4114 if (DstI.TheDef->getName() == "EXTRACT_SUBREG") {
4115 // EXTRACT_SUBREG selects into a subregister COPY but unlike most
4116 // instructions, the result register class is controlled by the
4117 // subregisters of the operand. As a result, we must constrain the result
4118 // class rather than check that it's already the right one.
4119 if (!Dst->getChild(0)->isLeaf())
4120 return failedImport("EXTRACT_SUBREG child #1 is not a leaf");
4122 DefInit *SubRegInit = dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue());
4124 return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
4126 // Constrain the result to the same register bank as the operand.
4128 getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
4130 if (DstIOpRec == nullptr)
4131 return failedImport("EXTRACT_SUBREG operand #1 isn't a register class");
4133 CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
4134 CodeGenRegisterClass *SrcRC = CGRegs.getRegClass(DstIOpRec);
4136 // It would be nice to leave this constraint implicit but we're required
4137 // to pick a register class so constrain the result to a register class
4138 // that can hold the correct MVT.
4140 // FIXME: This may introduce an extra copy if the chosen class doesn't
4141 // actually contain the subregisters.
4142 assert(Src->getExtTypes().size() == 1 &&
4143 "Expected Src of EXTRACT_SUBREG to have one result type");
4145 const auto &SrcRCDstRCPair =
4146 SrcRC->getMatchingSubClassWithSubRegs(CGRegs, SubIdx);
4147 assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
4148 M.addAction<ConstrainOperandToRegClassAction>(0, 0, *SrcRCDstRCPair->second);
4149 M.addAction<ConstrainOperandToRegClassAction>(0, 1, *SrcRCDstRCPair->first);
4151 // We're done with this pattern! It's eligible for GISel emission; return
4153 ++NumPatternImported;
4154 return std::move(M);
4157 M.addAction<ConstrainOperandsToDefinitionAction>(0);
4159 // We're done with this pattern! It's eligible for GISel emission; return it.
4160 ++NumPatternImported;
4161 return std::move(M);
4164 // Emit imm predicate table and an enum to reference them with.
4165 // The 'Predicate_' part of the name is redundant but eliminating it is more
4166 // trouble than it's worth.
4167 void GlobalISelEmitter::emitCxxPredicateFns(
4168 raw_ostream &OS, StringRef CodeFieldName, StringRef TypeIdentifier,
4169 StringRef ArgType, StringRef ArgName, StringRef AdditionalDeclarations,
4170 std::function<bool(const Record *R)> Filter) {
4171 std::vector<const Record *> MatchedRecords;
4172 const auto &Defs = RK.getAllDerivedDefinitions("PatFrag");
4173 std::copy_if(Defs.begin(), Defs.end(), std::back_inserter(MatchedRecords),
4174 [&](Record *Record) {
4175 return !Record->getValueAsString(CodeFieldName).empty() &&
4179 if (!MatchedRecords.empty()) {
4180 OS << "// PatFrag predicates.\n"
4182 std::string EnumeratorSeparator =
4183 (" = GIPFP_" + TypeIdentifier + "_Invalid + 1,\n").str();
4184 for (const auto *Record : MatchedRecords) {
4185 OS << " GIPFP_" << TypeIdentifier << "_Predicate_" << Record->getName()
4186 << EnumeratorSeparator;
4187 EnumeratorSeparator = ",\n";
4192 OS << "bool " << Target.getName() << "InstructionSelector::test" << ArgName
4193 << "Predicate_" << TypeIdentifier << "(unsigned PredicateID, " << ArgType << " "
4194 << ArgName << ") const {\n"
4195 << AdditionalDeclarations;
4196 if (!AdditionalDeclarations.empty())
4198 if (!MatchedRecords.empty())
4199 OS << " switch (PredicateID) {\n";
4200 for (const auto *Record : MatchedRecords) {
4201 OS << " case GIPFP_" << TypeIdentifier << "_Predicate_"
4202 << Record->getName() << ": {\n"
4203 << " " << Record->getValueAsString(CodeFieldName) << "\n"
4204 << " llvm_unreachable(\"" << CodeFieldName
4205 << " should have returned\");\n"
4206 << " return false;\n"
4209 if (!MatchedRecords.empty())
4211 OS << " llvm_unreachable(\"Unknown predicate\");\n"
4212 << " return false;\n"
4216 void GlobalISelEmitter::emitImmPredicateFns(
4217 raw_ostream &OS, StringRef TypeIdentifier, StringRef ArgType,
4218 std::function<bool(const Record *R)> Filter) {
4219 return emitCxxPredicateFns(OS, "ImmediateCode", TypeIdentifier, ArgType,
4223 void GlobalISelEmitter::emitMIPredicateFns(raw_ostream &OS) {
4224 return emitCxxPredicateFns(
4225 OS, "GISelPredicateCode", "MI", "const MachineInstr &", "MI",
4226 " const MachineFunction &MF = *MI.getParent()->getParent();\n"
4227 " const MachineRegisterInfo &MRI = MF.getRegInfo();\n"
4229 [](const Record *R) { return true; });
4232 template <class GroupT>
4233 std::vector<Matcher *> GlobalISelEmitter::optimizeRules(
4234 ArrayRef<Matcher *> Rules,
4235 std::vector<std::unique_ptr<Matcher>> &MatcherStorage) {
4237 std::vector<Matcher *> OptRules;
4238 std::unique_ptr<GroupT> CurrentGroup = make_unique<GroupT>();
4239 assert(CurrentGroup->empty() && "Newly created group isn't empty!");
4240 unsigned NumGroups = 0;
4242 auto ProcessCurrentGroup = [&]() {
4243 if (CurrentGroup->empty())
4244 // An empty group is good to be reused:
4247 // If the group isn't large enough to provide any benefit, move all the
4248 // added rules out of it and make sure to re-create the group to properly
4249 // re-initialize it:
4250 if (CurrentGroup->size() < 2)
4251 for (Matcher *M : CurrentGroup->matchers())
4252 OptRules.push_back(M);
4254 CurrentGroup->finalize();
4255 OptRules.push_back(CurrentGroup.get());
4256 MatcherStorage.emplace_back(std::move(CurrentGroup));
4259 CurrentGroup = make_unique<GroupT>();
4261 for (Matcher *Rule : Rules) {
4262 // Greedily add as many matchers as possible to the current group:
4263 if (CurrentGroup->addMatcher(*Rule))
4266 ProcessCurrentGroup();
4267 assert(CurrentGroup->empty() && "A group wasn't properly re-initialized");
4269 // Try to add the pending matcher to a newly created empty group:
4270 if (!CurrentGroup->addMatcher(*Rule))
4271 // If we couldn't add the matcher to an empty group, that group type
4272 // doesn't support that kind of matchers at all, so just skip it:
4273 OptRules.push_back(Rule);
4275 ProcessCurrentGroup();
4277 LLVM_DEBUG(dbgs() << "NumGroups: " << NumGroups << "\n");
4278 assert(CurrentGroup->empty() && "The last group wasn't properly processed");
4283 GlobalISelEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules,
4284 bool Optimize, bool WithCoverage) {
4285 std::vector<Matcher *> InputRules;
4286 for (Matcher &Rule : Rules)
4287 InputRules.push_back(&Rule);
4290 return MatchTable::buildTable(InputRules, WithCoverage);
4292 unsigned CurrentOrdering = 0;
4293 StringMap<unsigned> OpcodeOrder;
4294 for (RuleMatcher &Rule : Rules) {
4295 const StringRef Opcode = Rule.getOpcode();
4296 assert(!Opcode.empty() && "Didn't expect an undefined opcode");
4297 if (OpcodeOrder.count(Opcode) == 0)
4298 OpcodeOrder[Opcode] = CurrentOrdering++;
4301 std::stable_sort(InputRules.begin(), InputRules.end(),
4302 [&OpcodeOrder](const Matcher *A, const Matcher *B) {
4303 auto *L = static_cast<const RuleMatcher *>(A);
4304 auto *R = static_cast<const RuleMatcher *>(B);
4305 return std::make_tuple(OpcodeOrder[L->getOpcode()],
4306 L->getNumOperands()) <
4307 std::make_tuple(OpcodeOrder[R->getOpcode()],
4308 R->getNumOperands());
4311 for (Matcher *Rule : InputRules)
4314 std::vector<std::unique_ptr<Matcher>> MatcherStorage;
4315 std::vector<Matcher *> OptRules =
4316 optimizeRules<GroupMatcher>(InputRules, MatcherStorage);
4318 for (Matcher *Rule : OptRules)
4321 OptRules = optimizeRules<SwitchMatcher>(OptRules, MatcherStorage);
4323 return MatchTable::buildTable(OptRules, WithCoverage);
4326 void GroupMatcher::optimize() {
4327 // Make sure we only sort by a specific predicate within a range of rules that
4328 // all have that predicate checked against a specific value (not a wildcard):
4329 auto F = Matchers.begin();
4331 auto E = Matchers.end();
4334 auto *R = static_cast<RuleMatcher *>(*T);
4335 if (!R->getFirstConditionAsRootType().get().isValid())
4339 std::stable_sort(F, T, [](Matcher *A, Matcher *B) {
4340 auto *L = static_cast<RuleMatcher *>(A);
4341 auto *R = static_cast<RuleMatcher *>(B);
4342 return L->getFirstConditionAsRootType() <
4343 R->getFirstConditionAsRootType();
4348 GlobalISelEmitter::optimizeRules<GroupMatcher>(Matchers, MatcherStorage)
4350 GlobalISelEmitter::optimizeRules<SwitchMatcher>(Matchers, MatcherStorage)
4354 void GlobalISelEmitter::run(raw_ostream &OS) {
4355 if (!UseCoverageFile.empty()) {
4356 RuleCoverage = CodeGenCoverage();
4357 auto RuleCoverageBufOrErr = MemoryBuffer::getFile(UseCoverageFile);
4358 if (!RuleCoverageBufOrErr) {
4359 PrintWarning(SMLoc(), "Missing rule coverage data");
4360 RuleCoverage = None;
4362 if (!RuleCoverage->parse(*RuleCoverageBufOrErr.get(), Target.getName())) {
4363 PrintWarning(SMLoc(), "Ignoring invalid or missing rule coverage data");
4364 RuleCoverage = None;
4369 // Track the run-time opcode values
4370 gatherOpcodeValues();
4371 // Track the run-time LLT ID values
4372 gatherTypeIDValues();
4374 // Track the GINodeEquiv definitions.
4377 emitSourceFileHeader(("Global Instruction Selector for the " +
4378 Target.getName() + " target").str(), OS);
4379 std::vector<RuleMatcher> Rules;
4380 // Look through the SelectionDAG patterns we found, possibly emitting some.
4381 for (const PatternToMatch &Pat : CGP.ptms()) {
4384 auto MatcherOrErr = runOnPattern(Pat);
4386 // The pattern analysis can fail, indicating an unsupported pattern.
4387 // Report that if we've been asked to do so.
4388 if (auto Err = MatcherOrErr.takeError()) {
4389 if (WarnOnSkippedPatterns) {
4390 PrintWarning(Pat.getSrcRecord()->getLoc(),
4391 "Skipped pattern: " + toString(std::move(Err)));
4393 consumeError(std::move(Err));
4395 ++NumPatternImportsSkipped;
4400 if (RuleCoverage->isCovered(MatcherOrErr->getRuleID()))
4401 ++NumPatternsTested;
4403 PrintWarning(Pat.getSrcRecord()->getLoc(),
4404 "Pattern is not covered by a test");
4406 Rules.push_back(std::move(MatcherOrErr.get()));
4409 // Comparison function to order records by name.
4410 auto orderByName = [](const Record *A, const Record *B) {
4411 return A->getName() < B->getName();
4414 std::vector<Record *> ComplexPredicates =
4415 RK.getAllDerivedDefinitions("GIComplexOperandMatcher");
4416 llvm::sort(ComplexPredicates, orderByName);
4418 std::vector<Record *> CustomRendererFns =
4419 RK.getAllDerivedDefinitions("GICustomOperandRenderer");
4420 llvm::sort(CustomRendererFns, orderByName);
4422 unsigned MaxTemporaries = 0;
4423 for (const auto &Rule : Rules)
4424 MaxTemporaries = std::max(MaxTemporaries, Rule.countRendererFns());
4426 OS << "#ifdef GET_GLOBALISEL_PREDICATE_BITSET\n"
4427 << "const unsigned MAX_SUBTARGET_PREDICATES = " << SubtargetFeatures.size()
4429 << "using PredicateBitset = "
4430 "llvm::PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;\n"
4431 << "#endif // ifdef GET_GLOBALISEL_PREDICATE_BITSET\n\n";
4433 OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n"
4434 << " mutable MatcherState State;\n"
4436 "ComplexRendererFns("
4438 << "InstructionSelector::*ComplexMatcherMemFn)(MachineOperand &) const;\n"
4440 << " typedef void(" << Target.getName()
4441 << "InstructionSelector::*CustomRendererFn)(MachineInstrBuilder &, const "
4444 << " const ISelInfoTy<PredicateBitset, ComplexMatcherMemFn, "
4445 "CustomRendererFn> "
4447 OS << " static " << Target.getName()
4448 << "InstructionSelector::ComplexMatcherMemFn ComplexPredicateFns[];\n"
4449 << " static " << Target.getName()
4450 << "InstructionSelector::CustomRendererFn CustomRenderers[];\n"
4451 << " bool testImmPredicate_I64(unsigned PredicateID, int64_t Imm) const "
4453 << " bool testImmPredicate_APInt(unsigned PredicateID, const APInt &Imm) "
4455 << " bool testImmPredicate_APFloat(unsigned PredicateID, const APFloat "
4456 "&Imm) const override;\n"
4457 << " const int64_t *getMatchTable() const override;\n"
4458 << " bool testMIPredicate_MI(unsigned PredicateID, const MachineInstr &MI) "
4460 << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n";
4462 OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n"
4463 << ", State(" << MaxTemporaries << "),\n"
4464 << "ISelInfo(TypeObjects, NumTypeObjects, FeatureBitsets"
4465 << ", ComplexPredicateFns, CustomRenderers)\n"
4466 << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";
4468 OS << "#ifdef GET_GLOBALISEL_IMPL\n";
4469 SubtargetFeatureInfo::emitSubtargetFeatureBitEnumeration(SubtargetFeatures,
4472 // Separate subtarget features by how often they must be recomputed.
4473 SubtargetFeatureInfoMap ModuleFeatures;
4474 std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
4475 std::inserter(ModuleFeatures, ModuleFeatures.end()),
4476 [](const SubtargetFeatureInfoMap::value_type &X) {
4477 return !X.second.mustRecomputePerFunction();
4479 SubtargetFeatureInfoMap FunctionFeatures;
4480 std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
4481 std::inserter(FunctionFeatures, FunctionFeatures.end()),
4482 [](const SubtargetFeatureInfoMap::value_type &X) {
4483 return X.second.mustRecomputePerFunction();
4486 SubtargetFeatureInfo::emitComputeAvailableFeatures(
4487 Target.getName(), "InstructionSelector", "computeAvailableModuleFeatures",
4488 ModuleFeatures, OS);
4489 SubtargetFeatureInfo::emitComputeAvailableFeatures(
4490 Target.getName(), "InstructionSelector",
4491 "computeAvailableFunctionFeatures", FunctionFeatures, OS,
4492 "const MachineFunction *MF");
4494 // Emit a table containing the LLT objects needed by the matcher and an enum
4495 // for the matcher to reference them with.
4496 std::vector<LLTCodeGen> TypeObjects;
4497 for (const auto &Ty : KnownTypes)
4498 TypeObjects.push_back(Ty);
4499 llvm::sort(TypeObjects);
4500 OS << "// LLT Objects.\n"
4502 for (const auto &TypeObject : TypeObjects) {
4504 TypeObject.emitCxxEnumValue(OS);
4508 OS << "const static size_t NumTypeObjects = " << TypeObjects.size() << ";\n"
4509 << "const static LLT TypeObjects[] = {\n";
4510 for (const auto &TypeObject : TypeObjects) {
4512 TypeObject.emitCxxConstructorCall(OS);
4517 // Emit a table containing the PredicateBitsets objects needed by the matcher
4518 // and an enum for the matcher to reference them with.
4519 std::vector<std::vector<Record *>> FeatureBitsets;
4520 for (auto &Rule : Rules)
4521 FeatureBitsets.push_back(Rule.getRequiredFeatures());
4522 llvm::sort(FeatureBitsets, [&](const std::vector<Record *> &A,
4523 const std::vector<Record *> &B) {
4524 if (A.size() < B.size())
4526 if (A.size() > B.size())
4528 for (const auto &Pair : zip(A, B)) {
4529 if (std::get<0>(Pair)->getName() < std::get<1>(Pair)->getName())
4531 if (std::get<0>(Pair)->getName() > std::get<1>(Pair)->getName())
4536 FeatureBitsets.erase(
4537 std::unique(FeatureBitsets.begin(), FeatureBitsets.end()),
4538 FeatureBitsets.end());
4539 OS << "// Feature bitsets.\n"
4541 << " GIFBS_Invalid,\n";
4542 for (const auto &FeatureBitset : FeatureBitsets) {
4543 if (FeatureBitset.empty())
4545 OS << " " << getNameForFeatureBitset(FeatureBitset) << ",\n";
4548 << "const static PredicateBitset FeatureBitsets[] {\n"
4549 << " {}, // GIFBS_Invalid\n";
4550 for (const auto &FeatureBitset : FeatureBitsets) {
4551 if (FeatureBitset.empty())
4554 for (const auto &Feature : FeatureBitset) {
4555 const auto &I = SubtargetFeatures.find(Feature);
4556 assert(I != SubtargetFeatures.end() && "Didn't import predicate?");
4557 OS << I->second.getEnumBitName() << ", ";
4563 // Emit complex predicate table and an enum to reference them with.
4564 OS << "// ComplexPattern predicates.\n"
4566 << " GICP_Invalid,\n";
4567 for (const auto &Record : ComplexPredicates)
4568 OS << " GICP_" << Record->getName() << ",\n";
4570 << "// See constructor for table contents\n\n";
4572 emitImmPredicateFns(OS, "I64", "int64_t", [](const Record *R) {
4574 return !R->getValueAsBitOrUnset("IsAPFloat", Unset) &&
4575 !R->getValueAsBit("IsAPInt");
4577 emitImmPredicateFns(OS, "APFloat", "const APFloat &", [](const Record *R) {
4579 return R->getValueAsBitOrUnset("IsAPFloat", Unset);
4581 emitImmPredicateFns(OS, "APInt", "const APInt &", [](const Record *R) {
4582 return R->getValueAsBit("IsAPInt");
4584 emitMIPredicateFns(OS);
4587 OS << Target.getName() << "InstructionSelector::ComplexMatcherMemFn\n"
4588 << Target.getName() << "InstructionSelector::ComplexPredicateFns[] = {\n"
4589 << " nullptr, // GICP_Invalid\n";
4590 for (const auto &Record : ComplexPredicates)
4591 OS << " &" << Target.getName()
4592 << "InstructionSelector::" << Record->getValueAsString("MatcherFn")
4593 << ", // " << Record->getName() << "\n";
4596 OS << "// Custom renderers.\n"
4598 << " GICR_Invalid,\n";
4599 for (const auto &Record : CustomRendererFns)
4600 OS << " GICR_" << Record->getValueAsString("RendererFn") << ", \n";
4603 OS << Target.getName() << "InstructionSelector::CustomRendererFn\n"
4604 << Target.getName() << "InstructionSelector::CustomRenderers[] = {\n"
4605 << " nullptr, // GICP_Invalid\n";
4606 for (const auto &Record : CustomRendererFns)
4607 OS << " &" << Target.getName()
4608 << "InstructionSelector::" << Record->getValueAsString("RendererFn")
4609 << ", // " << Record->getName() << "\n";
4612 llvm::stable_sort(Rules, [&](const RuleMatcher &A, const RuleMatcher &B) {
4613 int ScoreA = RuleMatcherScores[A.getRuleID()];
4614 int ScoreB = RuleMatcherScores[B.getRuleID()];
4615 if (ScoreA > ScoreB)
4617 if (ScoreB > ScoreA)
4619 if (A.isHigherPriorityThan(B)) {
4620 assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
4621 "and less important at "
4628 OS << "bool " << Target.getName()
4629 << "InstructionSelector::selectImpl(MachineInstr &I, CodeGenCoverage "
4630 "&CoverageInfo) const {\n"
4631 << " MachineFunction &MF = *I.getParent()->getParent();\n"
4632 << " MachineRegisterInfo &MRI = MF.getRegInfo();\n"
4633 << " // FIXME: This should be computed on a per-function basis rather "
4635 << " AvailableFunctionFeatures = computeAvailableFunctionFeatures(&STI, "
4637 << " const PredicateBitset AvailableFeatures = getAvailableFeatures();\n"
4638 << " NewMIVector OutMIs;\n"
4639 << " State.MIs.clear();\n"
4640 << " State.MIs.push_back(&I);\n\n"
4641 << " if (executeMatchTable(*this, OutMIs, State, ISelInfo"
4642 << ", getMatchTable(), TII, MRI, TRI, RBI, AvailableFeatures"
4643 << ", CoverageInfo)) {\n"
4644 << " return true;\n"
4646 << " return false;\n"
4649 const MatchTable Table =
4650 buildMatchTable(Rules, OptimizeMatchTable, GenerateCoverage);
4651 OS << "const int64_t *" << Target.getName()
4652 << "InstructionSelector::getMatchTable() const {\n";
4653 Table.emitDeclaration(OS);
4657 OS << "#endif // ifdef GET_GLOBALISEL_IMPL\n";
4659 OS << "#ifdef GET_GLOBALISEL_PREDICATES_DECL\n"
4660 << "PredicateBitset AvailableModuleFeatures;\n"
4661 << "mutable PredicateBitset AvailableFunctionFeatures;\n"
4662 << "PredicateBitset getAvailableFeatures() const {\n"
4663 << " return AvailableModuleFeatures | AvailableFunctionFeatures;\n"
4665 << "PredicateBitset\n"
4666 << "computeAvailableModuleFeatures(const " << Target.getName()
4667 << "Subtarget *Subtarget) const;\n"
4668 << "PredicateBitset\n"
4669 << "computeAvailableFunctionFeatures(const " << Target.getName()
4670 << "Subtarget *Subtarget,\n"
4671 << " const MachineFunction *MF) const;\n"
4672 << "#endif // ifdef GET_GLOBALISEL_PREDICATES_DECL\n";
4674 OS << "#ifdef GET_GLOBALISEL_PREDICATES_INIT\n"
4675 << "AvailableModuleFeatures(computeAvailableModuleFeatures(&STI)),\n"
4676 << "AvailableFunctionFeatures()\n"
4677 << "#endif // ifdef GET_GLOBALISEL_PREDICATES_INIT\n";
4680 void GlobalISelEmitter::declareSubtargetFeature(Record *Predicate) {
4681 if (SubtargetFeatures.count(Predicate) == 0)
4682 SubtargetFeatures.emplace(
4683 Predicate, SubtargetFeatureInfo(Predicate, SubtargetFeatures.size()));
4686 void RuleMatcher::optimize() {
4687 for (auto &Item : InsnVariableIDs) {
4688 InstructionMatcher &InsnMatcher = *Item.first;
4689 for (auto &OM : InsnMatcher.operands()) {
4690 // Complex Patterns are usually expensive and they relatively rarely fail
4691 // on their own: more often we end up throwing away all the work done by a
4692 // matching part of a complex pattern because some other part of the
4693 // enclosing pattern didn't match. All of this makes it beneficial to
4694 // delay complex patterns until the very end of the rule matching,
4695 // especially for targets having lots of complex patterns.
4696 for (auto &OP : OM->predicates())
4697 if (isa<ComplexPatternOperandMatcher>(OP))
4698 EpilogueMatchers.emplace_back(std::move(OP));
4699 OM->eraseNullPredicates();
4701 InsnMatcher.optimize();
4703 llvm::sort(EpilogueMatchers, [](const std::unique_ptr<PredicateMatcher> &L,
4704 const std::unique_ptr<PredicateMatcher> &R) {
4705 return std::make_tuple(L->getKind(), L->getInsnVarID(), L->getOpIdx()) <
4706 std::make_tuple(R->getKind(), R->getInsnVarID(), R->getOpIdx());
4710 bool RuleMatcher::hasFirstCondition() const {
4711 if (insnmatchers_empty())
4713 InstructionMatcher &Matcher = insnmatchers_front();
4714 if (!Matcher.predicates_empty())
4716 for (auto &OM : Matcher.operands())
4717 for (auto &OP : OM->predicates())
4718 if (!isa<InstructionOperandMatcher>(OP))
4723 const PredicateMatcher &RuleMatcher::getFirstCondition() const {
4724 assert(!insnmatchers_empty() &&
4725 "Trying to get a condition from an empty RuleMatcher");
4727 InstructionMatcher &Matcher = insnmatchers_front();
4728 if (!Matcher.predicates_empty())
4729 return **Matcher.predicates_begin();
4730 // If there is no more predicate on the instruction itself, look at its
4732 for (auto &OM : Matcher.operands())
4733 for (auto &OP : OM->predicates())
4734 if (!isa<InstructionOperandMatcher>(OP))
4737 llvm_unreachable("Trying to get a condition from an InstructionMatcher with "
4741 std::unique_ptr<PredicateMatcher> RuleMatcher::popFirstCondition() {
4742 assert(!insnmatchers_empty() &&
4743 "Trying to pop a condition from an empty RuleMatcher");
4745 InstructionMatcher &Matcher = insnmatchers_front();
4746 if (!Matcher.predicates_empty())
4747 return Matcher.predicates_pop_front();
4748 // If there is no more predicate on the instruction itself, look at its
4750 for (auto &OM : Matcher.operands())
4751 for (auto &OP : OM->predicates())
4752 if (!isa<InstructionOperandMatcher>(OP)) {
4753 std::unique_ptr<PredicateMatcher> Result = std::move(OP);
4754 OM->eraseNullPredicates();
4758 llvm_unreachable("Trying to pop a condition from an InstructionMatcher with "
4762 bool GroupMatcher::candidateConditionMatches(
4763 const PredicateMatcher &Predicate) const {
4766 // Sharing predicates for nested instructions is not supported yet as we
4767 // currently don't hoist the GIM_RecordInsn's properly, therefore we can
4768 // only work on the original root instruction (InsnVarID == 0):
4769 if (Predicate.getInsnVarID() != 0)
4771 // ... otherwise an empty group can handle any predicate with no specific
4776 const Matcher &Representative = **Matchers.begin();
4777 const auto &RepresentativeCondition = Representative.getFirstCondition();
4778 // ... if not empty, the group can only accomodate matchers with the exact
4779 // same first condition:
4780 return Predicate.isIdentical(RepresentativeCondition);
4783 bool GroupMatcher::addMatcher(Matcher &Candidate) {
4784 if (!Candidate.hasFirstCondition())
4787 const PredicateMatcher &Predicate = Candidate.getFirstCondition();
4788 if (!candidateConditionMatches(Predicate))
4791 Matchers.push_back(&Candidate);
4795 void GroupMatcher::finalize() {
4796 assert(Conditions.empty() && "Already finalized?");
4800 Matcher &FirstRule = **Matchers.begin();
4802 // All the checks are expected to succeed during the first iteration:
4803 for (const auto &Rule : Matchers)
4804 if (!Rule->hasFirstCondition())
4806 const auto &FirstCondition = FirstRule.getFirstCondition();
4807 for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
4808 if (!Matchers[I]->getFirstCondition().isIdentical(FirstCondition))
4811 Conditions.push_back(FirstRule.popFirstCondition());
4812 for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
4813 Matchers[I]->popFirstCondition();
4817 void GroupMatcher::emit(MatchTable &Table) {
4818 unsigned LabelID = ~0U;
4819 if (!Conditions.empty()) {
4820 LabelID = Table.allocateLabelID();
4821 Table << MatchTable::Opcode("GIM_Try", +1)
4822 << MatchTable::Comment("On fail goto")
4823 << MatchTable::JumpTarget(LabelID) << MatchTable::LineBreak;
4825 for (auto &Condition : Conditions)
4826 Condition->emitPredicateOpcodes(
4827 Table, *static_cast<RuleMatcher *>(*Matchers.begin()));
4829 for (const auto &M : Matchers)
4833 if (!Conditions.empty())
4834 Table << MatchTable::Opcode("GIM_Reject", -1) << MatchTable::LineBreak
4835 << MatchTable::Label(LabelID);
4838 bool SwitchMatcher::isSupportedPredicateType(const PredicateMatcher &P) {
4839 return isa<InstructionOpcodeMatcher>(P) || isa<LLTOperandMatcher>(P);
4842 bool SwitchMatcher::candidateConditionMatches(
4843 const PredicateMatcher &Predicate) const {
4846 // Sharing predicates for nested instructions is not supported yet as we
4847 // currently don't hoist the GIM_RecordInsn's properly, therefore we can
4848 // only work on the original root instruction (InsnVarID == 0):
4849 if (Predicate.getInsnVarID() != 0)
4851 // ... while an attempt to add even a root matcher to an empty SwitchMatcher
4852 // could fail as not all the types of conditions are supported:
4853 if (!isSupportedPredicateType(Predicate))
4855 // ... or the condition might not have a proper implementation of
4856 // getValue() / isIdenticalDownToValue() yet:
4857 if (!Predicate.hasValue())
4859 // ... otherwise an empty Switch can accomodate the condition with no
4860 // further requirements:
4864 const Matcher &CaseRepresentative = **Matchers.begin();
4865 const auto &RepresentativeCondition = CaseRepresentative.getFirstCondition();
4866 // Switch-cases must share the same kind of condition and path to the value it
4868 if (!Predicate.isIdenticalDownToValue(RepresentativeCondition))
4871 const auto Value = Predicate.getValue();
4872 // ... but be unique with respect to the actual value they check:
4873 return Values.count(Value) == 0;
4876 bool SwitchMatcher::addMatcher(Matcher &Candidate) {
4877 if (!Candidate.hasFirstCondition())
4880 const PredicateMatcher &Predicate = Candidate.getFirstCondition();
4881 if (!candidateConditionMatches(Predicate))
4883 const auto Value = Predicate.getValue();
4884 Values.insert(Value);
4886 Matchers.push_back(&Candidate);
4890 void SwitchMatcher::finalize() {
4891 assert(Condition == nullptr && "Already finalized");
4892 assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");
4896 std::stable_sort(Matchers.begin(), Matchers.end(),
4897 [](const Matcher *L, const Matcher *R) {
4898 return L->getFirstCondition().getValue() <
4899 R->getFirstCondition().getValue();
4901 Condition = Matchers[0]->popFirstCondition();
4902 for (unsigned I = 1, E = Values.size(); I < E; ++I)
4903 Matchers[I]->popFirstCondition();
4906 void SwitchMatcher::emitPredicateSpecificOpcodes(const PredicateMatcher &P,
4907 MatchTable &Table) {
4908 assert(isSupportedPredicateType(P) && "Predicate type is not supported");
4910 if (const auto *Condition = dyn_cast<InstructionOpcodeMatcher>(&P)) {
4911 Table << MatchTable::Opcode("GIM_SwitchOpcode") << MatchTable::Comment("MI")
4912 << MatchTable::IntValue(Condition->getInsnVarID());
4915 if (const auto *Condition = dyn_cast<LLTOperandMatcher>(&P)) {
4916 Table << MatchTable::Opcode("GIM_SwitchType") << MatchTable::Comment("MI")
4917 << MatchTable::IntValue(Condition->getInsnVarID())
4918 << MatchTable::Comment("Op")
4919 << MatchTable::IntValue(Condition->getOpIdx());
4923 llvm_unreachable("emitPredicateSpecificOpcodes is broken: can not handle a "
4924 "predicate type that is claimed to be supported");
4927 void SwitchMatcher::emit(MatchTable &Table) {
4928 assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");
4931 assert(Condition != nullptr &&
4932 "Broken SwitchMatcher, hasn't been finalized?");
4934 std::vector<unsigned> LabelIDs(Values.size());
4935 std::generate(LabelIDs.begin(), LabelIDs.end(),
4936 [&Table]() { return Table.allocateLabelID(); });
4937 const unsigned Default = Table.allocateLabelID();
4939 const int64_t LowerBound = Values.begin()->getRawValue();
4940 const int64_t UpperBound = Values.rbegin()->getRawValue() + 1;
4942 emitPredicateSpecificOpcodes(*Condition, Table);
4944 Table << MatchTable::Comment("[") << MatchTable::IntValue(LowerBound)
4945 << MatchTable::IntValue(UpperBound) << MatchTable::Comment(")")
4946 << MatchTable::Comment("default:") << MatchTable::JumpTarget(Default);
4948 int64_t J = LowerBound;
4949 auto VI = Values.begin();
4950 for (unsigned I = 0, E = Values.size(); I < E; ++I) {
4952 while (J++ < V.getRawValue())
4953 Table << MatchTable::IntValue(0);
4954 V.turnIntoComment();
4955 Table << MatchTable::LineBreak << V << MatchTable::JumpTarget(LabelIDs[I]);
4957 Table << MatchTable::LineBreak;
4959 for (unsigned I = 0, E = Values.size(); I < E; ++I) {
4960 Table << MatchTable::Label(LabelIDs[I]);
4961 Matchers[I]->emit(Table);
4962 Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
4964 Table << MatchTable::Label(Default);
4967 unsigned OperandMatcher::getInsnVarID() const { return Insn.getInsnVarID(); }
4969 } // end anonymous namespace
4971 //===----------------------------------------------------------------------===//
4974 void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS) {
4975 GlobalISelEmitter(RK).run(OS);
4977 } // End llvm namespace