1 //===- GlobalISelEmitter.cpp - Generate an instruction selector -----------===//
2 //
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
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 /// \file
10 /// This tablegen backend emits code for use by the GlobalISel instruction
11 /// selector. See include/llvm/CodeGen/TargetGlobalISel.td.
12 ///
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).
17 ///
18 /// Not all patterns are supported: pass the tablegen invocation
19 /// "-warn-on-skipped-patterns" to emit a warning when a pattern is skipped,
20 /// as well as why.
21 ///
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++.
26 ///
27 /// FIXME: We'll probably want to eventually define a base
28 /// "TargetGenInstructionSelector" class.
29 ///
30 //===----------------------------------------------------------------------===//
31
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"
46 #include <numeric>
47 #include <string>
48 using namespace llvm;
49
50 #define DEBUG_TYPE "gisel-emitter"
51
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");
57
58 cl::OptionCategory GlobalISelEmitterCat("Options for -gen-global-isel");
59
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));
65
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));
70
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));
75
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));
80
81 namespace {
82 //===- Helper functions ---------------------------------------------------===//
83
84 /// Get the name of the enum value used to number the predicate function.
getEnumNameForPredicate(const TreePredicateFn & Predicate)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();
90 }
91
92 /// Get the opcode used to check this predicate.
getMatchOpcodeForImmPredicate(const TreePredicateFn & Predicate)93 std::string getMatchOpcodeForImmPredicate(const TreePredicateFn &Predicate) {
94 return "GIM_Check" + Predicate.getImmTypeIdentifier().str() + "ImmPredicate";
95 }
96
97 /// This class stands in for LLT wherever we want to tablegen-erate an
98 /// equivalent at compiler run-time.
99 class LLTCodeGen {
100 private:
101 LLT Ty;
102
103 public:
104 LLTCodeGen() = default;
LLTCodeGen(const LLT & Ty)105 LLTCodeGen(const LLT &Ty) : Ty(Ty) {}
106
getCxxEnumValue() const107 std::string getCxxEnumValue() const {
108 std::string Str;
109 raw_string_ostream OS(Str);
110
111 emitCxxEnumValue(OS);
112 return OS.str();
113 }
114
emitCxxEnumValue(raw_ostream & OS) const115 void emitCxxEnumValue(raw_ostream &OS) const {
116 if (Ty.isScalar()) {
117 OS << "GILLT_s" << Ty.getSizeInBits();
118 return;
119 }
120 if (Ty.isVector()) {
121 OS << "GILLT_v" << Ty.getNumElements() << "s" << Ty.getScalarSizeInBits();
122 return;
123 }
124 if (Ty.isPointer()) {
125 OS << "GILLT_p" << Ty.getAddressSpace();
126 if (Ty.getSizeInBits() > 0)
127 OS << "s" << Ty.getSizeInBits();
128 return;
129 }
130 llvm_unreachable("Unhandled LLT");
131 }
132
emitCxxConstructorCall(raw_ostream & OS) const133 void emitCxxConstructorCall(raw_ostream &OS) const {
134 if (Ty.isScalar()) {
135 OS << "LLT::scalar(" << Ty.getSizeInBits() << ")";
136 return;
137 }
138 if (Ty.isVector()) {
139 OS << "LLT::vector(" << Ty.getNumElements() << ", "
140 << Ty.getScalarSizeInBits() << ")";
141 return;
142 }
143 if (Ty.isPointer() && Ty.getSizeInBits() > 0) {
144 OS << "LLT::pointer(" << Ty.getAddressSpace() << ", "
145 << Ty.getSizeInBits() << ")";
146 return;
147 }
148 llvm_unreachable("Unhandled LLT");
149 }
150
get() const151 const LLT &get() const { return Ty; }
152
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
155 /// true if A != B.
operator <(const LLTCodeGen & Other) const156 bool operator<(const LLTCodeGen &Other) const {
157 if (Ty.isValid() != Other.Ty.isValid())
158 return Ty.isValid() < Other.Ty.isValid();
159 if (!Ty.isValid())
160 return false;
161
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();
168
169 if (Ty.isPointer() && Ty.getAddressSpace() != Other.Ty.getAddressSpace())
170 return Ty.getAddressSpace() < Other.Ty.getAddressSpace();
171
172 if (Ty.isVector() && Ty.getNumElements() != Other.Ty.getNumElements())
173 return Ty.getNumElements() < Other.Ty.getNumElements();
174
175 return Ty.getSizeInBits() < Other.Ty.getSizeInBits();
176 }
177
operator ==(const LLTCodeGen & B) const178 bool operator==(const LLTCodeGen &B) const { return Ty == B.Ty; }
179 };
180
181 // Track all types that are used so we can emit the corresponding enum.
182 std::set<LLTCodeGen> KnownTypes;
183
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, ...).
MVTToLLT(MVT::SimpleValueType SVT)187 static Optional<LLTCodeGen> MVTToLLT(MVT::SimpleValueType SVT) {
188 MVT VT(SVT);
189
190 if (VT.isScalableVector())
191 return None;
192
193 if (VT.isFixedLengthVector() && VT.getVectorNumElements() != 1)
194 return LLTCodeGen(
195 LLT::vector(VT.getVectorNumElements(), VT.getScalarSizeInBits()));
196
197 if (VT.isInteger() || VT.isFloatingPoint())
198 return LLTCodeGen(LLT::scalar(VT.getSizeInBits()));
199
200 return None;
201 }
202
explainPredicates(const TreePatternNode * N)203 static std::string explainPredicates(const TreePatternNode *N) {
204 std::string Explanation;
205 StringRef Separator = "";
206 for (const TreePredicateCall &Call : N->getPredicateCalls()) {
207 const TreePredicateFn &P = Call.Fn;
208 Explanation +=
209 (Separator + P.getOrigPatFragRecord()->getRecord()->getName()).str();
210 Separator = ", ";
211
212 if (P.isAlwaysTrue())
213 Explanation += " always-true";
214 if (P.isImmediatePattern())
215 Explanation += " immediate";
216
217 if (P.isUnindexed())
218 Explanation += " unindexed";
219
220 if (P.isNonExtLoad())
221 Explanation += " non-extload";
222 if (P.isAnyExtLoad())
223 Explanation += " extload";
224 if (P.isSignExtLoad())
225 Explanation += " sextload";
226 if (P.isZeroExtLoad())
227 Explanation += " zextload";
228
229 if (P.isNonTruncStore())
230 Explanation += " non-truncstore";
231 if (P.isTruncStore())
232 Explanation += " truncstore";
233
234 if (Record *VT = P.getMemoryVT())
235 Explanation += (" MemVT=" + VT->getName()).str();
236 if (Record *VT = P.getScalarMemoryVT())
237 Explanation += (" ScalarVT(MemVT)=" + VT->getName()).str();
238
239 if (ListInit *AddrSpaces = P.getAddressSpaces()) {
240 raw_string_ostream OS(Explanation);
241 OS << " AddressSpaces=[";
242
243 StringRef AddrSpaceSeparator;
244 for (Init *Val : AddrSpaces->getValues()) {
245 IntInit *IntVal = dyn_cast<IntInit>(Val);
246 if (!IntVal)
247 continue;
248
249 OS << AddrSpaceSeparator << IntVal->getValue();
250 AddrSpaceSeparator = ", ";
251 }
252
253 OS << ']';
254 }
255
256 int64_t MinAlign = P.getMinAlignment();
257 if (MinAlign > 0)
258 Explanation += " MinAlign=" + utostr(MinAlign);
259
260 if (P.isAtomicOrderingMonotonic())
261 Explanation += " monotonic";
262 if (P.isAtomicOrderingAcquire())
263 Explanation += " acquire";
264 if (P.isAtomicOrderingRelease())
265 Explanation += " release";
266 if (P.isAtomicOrderingAcquireRelease())
267 Explanation += " acq_rel";
268 if (P.isAtomicOrderingSequentiallyConsistent())
269 Explanation += " seq_cst";
270 if (P.isAtomicOrderingAcquireOrStronger())
271 Explanation += " >=acquire";
272 if (P.isAtomicOrderingWeakerThanAcquire())
273 Explanation += " <acquire";
274 if (P.isAtomicOrderingReleaseOrStronger())
275 Explanation += " >=release";
276 if (P.isAtomicOrderingWeakerThanRelease())
277 Explanation += " <release";
278 }
279 return Explanation;
280 }
281
explainOperator(Record * Operator)282 std::string explainOperator(Record *Operator) {
283 if (Operator->isSubClassOf("SDNode"))
284 return (" (" + Operator->getValueAsString("Opcode") + ")").str();
285
286 if (Operator->isSubClassOf("Intrinsic"))
287 return (" (Operator is an Intrinsic, " + Operator->getName() + ")").str();
288
289 if (Operator->isSubClassOf("ComplexPattern"))
290 return (" (Operator is an unmapped ComplexPattern, " + Operator->getName() +
291 ")")
292 .str();
293
294 if (Operator->isSubClassOf("SDNodeXForm"))
295 return (" (Operator is an unmapped SDNodeXForm, " + Operator->getName() +
296 ")")
297 .str();
298
299 return (" (Operator " + Operator->getName() + " not understood)").str();
300 }
301
302 /// Helper function to let the emitter report skip reason error messages.
failedImport(const Twine & Reason)303 static Error failedImport(const Twine &Reason) {
304 return make_error<StringError>(Reason, inconvertibleErrorCode());
305 }
306
isTrivialOperatorNode(const TreePatternNode * N)307 static Error isTrivialOperatorNode(const TreePatternNode *N) {
308 std::string Explanation;
309 std::string Separator;
310
311 bool HasUnsupportedPredicate = false;
312 for (const TreePredicateCall &Call : N->getPredicateCalls()) {
313 const TreePredicateFn &Predicate = Call.Fn;
314
315 if (Predicate.isAlwaysTrue())
316 continue;
317
318 if (Predicate.isImmediatePattern())
319 continue;
320
321 if (Predicate.isNonExtLoad() || Predicate.isAnyExtLoad() ||
322 Predicate.isSignExtLoad() || Predicate.isZeroExtLoad())
323 continue;
324
325 if (Predicate.isNonTruncStore() || Predicate.isTruncStore())
326 continue;
327
328 if (Predicate.isLoad() && Predicate.getMemoryVT())
329 continue;
330
331 if (Predicate.isLoad() || Predicate.isStore()) {
332 if (Predicate.isUnindexed())
333 continue;
334 }
335
336 if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
337 const ListInit *AddrSpaces = Predicate.getAddressSpaces();
338 if (AddrSpaces && !AddrSpaces->empty())
339 continue;
340
341 if (Predicate.getMinAlignment() > 0)
342 continue;
343 }
344
345 if (Predicate.isAtomic() && Predicate.getMemoryVT())
346 continue;
347
348 if (Predicate.isAtomic() &&
349 (Predicate.isAtomicOrderingMonotonic() ||
350 Predicate.isAtomicOrderingAcquire() ||
351 Predicate.isAtomicOrderingRelease() ||
352 Predicate.isAtomicOrderingAcquireRelease() ||
353 Predicate.isAtomicOrderingSequentiallyConsistent() ||
354 Predicate.isAtomicOrderingAcquireOrStronger() ||
355 Predicate.isAtomicOrderingWeakerThanAcquire() ||
356 Predicate.isAtomicOrderingReleaseOrStronger() ||
357 Predicate.isAtomicOrderingWeakerThanRelease()))
358 continue;
359
360 if (Predicate.hasGISelPredicateCode())
361 continue;
362
363 HasUnsupportedPredicate = true;
364 Explanation = Separator + "Has a predicate (" + explainPredicates(N) + ")";
365 Separator = ", ";
366 Explanation += (Separator + "first-failing:" +
367 Predicate.getOrigPatFragRecord()->getRecord()->getName())
368 .str();
369 break;
370 }
371
372 if (!HasUnsupportedPredicate)
373 return Error::success();
374
375 return failedImport(Explanation);
376 }
377
getInitValueAsRegClass(Init * V)378 static Record *getInitValueAsRegClass(Init *V) {
379 if (DefInit *VDefInit = dyn_cast<DefInit>(V)) {
380 if (VDefInit->getDef()->isSubClassOf("RegisterOperand"))
381 return VDefInit->getDef()->getValueAsDef("RegClass");
382 if (VDefInit->getDef()->isSubClassOf("RegisterClass"))
383 return VDefInit->getDef();
384 }
385 return nullptr;
386 }
387
388 std::string
getNameForFeatureBitset(const std::vector<Record * > & FeatureBitset)389 getNameForFeatureBitset(const std::vector<Record *> &FeatureBitset) {
390 std::string Name = "GIFBS";
391 for (const auto &Feature : FeatureBitset)
392 Name += ("_" + Feature->getName()).str();
393 return Name;
394 }
395
getScopedName(unsigned Scope,const std::string & Name)396 static std::string getScopedName(unsigned Scope, const std::string &Name) {
397 return ("pred:" + Twine(Scope) + ":" + Name).str();
398 }
399
400 //===- MatchTable Helpers -------------------------------------------------===//
401
402 class MatchTable;
403
404 /// A record to be stored in a MatchTable.
405 ///
406 /// This class represents any and all output that may be required to emit the
407 /// MatchTable. Instances are most often configured to represent an opcode or
408 /// value that will be emitted to the table with some formatting but it can also
409 /// represent commas, comments, and other formatting instructions.
410 struct MatchTableRecord {
411 enum RecordFlagsBits {
412 MTRF_None = 0x0,
413 /// Causes EmitStr to be formatted as comment when emitted.
414 MTRF_Comment = 0x1,
415 /// Causes the record value to be followed by a comma when emitted.
416 MTRF_CommaFollows = 0x2,
417 /// Causes the record value to be followed by a line break when emitted.
418 MTRF_LineBreakFollows = 0x4,
419 /// Indicates that the record defines a label and causes an additional
420 /// comment to be emitted containing the index of the label.
421 MTRF_Label = 0x8,
422 /// Causes the record to be emitted as the index of the label specified by
423 /// LabelID along with a comment indicating where that label is.
424 MTRF_JumpTarget = 0x10,
425 /// Causes the formatter to add a level of indentation before emitting the
426 /// record.
427 MTRF_Indent = 0x20,
428 /// Causes the formatter to remove a level of indentation after emitting the
429 /// record.
430 MTRF_Outdent = 0x40,
431 };
432
433 /// When MTRF_Label or MTRF_JumpTarget is used, indicates a label id to
434 /// reference or define.
435 unsigned LabelID;
436 /// The string to emit. Depending on the MTRF_* flags it may be a comment, a
437 /// value, a label name.
438 std::string EmitStr;
439
440 private:
441 /// The number of MatchTable elements described by this record. Comments are 0
442 /// while values are typically 1. Values >1 may occur when we need to emit
443 /// values that exceed the size of a MatchTable element.
444 unsigned NumElements;
445
446 public:
447 /// A bitfield of RecordFlagsBits flags.
448 unsigned Flags;
449
450 /// The actual run-time value, if known
451 int64_t RawValue;
452
MatchTableRecord__anon1998b5b40111::MatchTableRecord453 MatchTableRecord(Optional<unsigned> LabelID_, StringRef EmitStr,
454 unsigned NumElements, unsigned Flags,
455 int64_t RawValue = std::numeric_limits<int64_t>::min())
456 : LabelID(LabelID_.getValueOr(~0u)), EmitStr(EmitStr),
457 NumElements(NumElements), Flags(Flags), RawValue(RawValue) {
458 assert((!LabelID_.hasValue() || LabelID != ~0u) &&
459 "This value is reserved for non-labels");
460 }
461 MatchTableRecord(const MatchTableRecord &Other) = default;
462 MatchTableRecord(MatchTableRecord &&Other) = default;
463
464 /// Useful if a Match Table Record gets optimized out
turnIntoComment__anon1998b5b40111::MatchTableRecord465 void turnIntoComment() {
466 Flags |= MTRF_Comment;
467 Flags &= ~MTRF_CommaFollows;
468 NumElements = 0;
469 }
470
471 /// For Jump Table generation purposes
operator <__anon1998b5b40111::MatchTableRecord472 bool operator<(const MatchTableRecord &Other) const {
473 return RawValue < Other.RawValue;
474 }
getRawValue__anon1998b5b40111::MatchTableRecord475 int64_t getRawValue() const { return RawValue; }
476
477 void emit(raw_ostream &OS, bool LineBreakNextAfterThis,
478 const MatchTable &Table) const;
size__anon1998b5b40111::MatchTableRecord479 unsigned size() const { return NumElements; }
480 };
481
482 class Matcher;
483
484 /// Holds the contents of a generated MatchTable to enable formatting and the
485 /// necessary index tracking needed to support GIM_Try.
486 class MatchTable {
487 /// An unique identifier for the table. The generated table will be named
488 /// MatchTable${ID}.
489 unsigned ID;
490 /// The records that make up the table. Also includes comments describing the
491 /// values being emitted and line breaks to format it.
492 std::vector<MatchTableRecord> Contents;
493 /// The currently defined labels.
494 DenseMap<unsigned, unsigned> LabelMap;
495 /// Tracks the sum of MatchTableRecord::NumElements as the table is built.
496 unsigned CurrentSize = 0;
497 /// A unique identifier for a MatchTable label.
498 unsigned CurrentLabelID = 0;
499 /// Determines if the table should be instrumented for rule coverage tracking.
500 bool IsWithCoverage;
501
502 public:
503 static MatchTableRecord LineBreak;
Comment(StringRef Comment)504 static MatchTableRecord Comment(StringRef Comment) {
505 return MatchTableRecord(None, Comment, 0, MatchTableRecord::MTRF_Comment);
506 }
Opcode(StringRef Opcode,int IndentAdjust=0)507 static MatchTableRecord Opcode(StringRef Opcode, int IndentAdjust = 0) {
508 unsigned ExtraFlags = 0;
509 if (IndentAdjust > 0)
510 ExtraFlags |= MatchTableRecord::MTRF_Indent;
511 if (IndentAdjust < 0)
512 ExtraFlags |= MatchTableRecord::MTRF_Outdent;
513
514 return MatchTableRecord(None, Opcode, 1,
515 MatchTableRecord::MTRF_CommaFollows | ExtraFlags);
516 }
NamedValue(StringRef NamedValue)517 static MatchTableRecord NamedValue(StringRef NamedValue) {
518 return MatchTableRecord(None, NamedValue, 1,
519 MatchTableRecord::MTRF_CommaFollows);
520 }
NamedValue(StringRef NamedValue,int64_t RawValue)521 static MatchTableRecord NamedValue(StringRef NamedValue, int64_t RawValue) {
522 return MatchTableRecord(None, NamedValue, 1,
523 MatchTableRecord::MTRF_CommaFollows, RawValue);
524 }
NamedValue(StringRef Namespace,StringRef NamedValue)525 static MatchTableRecord NamedValue(StringRef Namespace,
526 StringRef NamedValue) {
527 return MatchTableRecord(None, (Namespace + "::" + NamedValue).str(), 1,
528 MatchTableRecord::MTRF_CommaFollows);
529 }
NamedValue(StringRef Namespace,StringRef NamedValue,int64_t RawValue)530 static MatchTableRecord NamedValue(StringRef Namespace, StringRef NamedValue,
531 int64_t RawValue) {
532 return MatchTableRecord(None, (Namespace + "::" + NamedValue).str(), 1,
533 MatchTableRecord::MTRF_CommaFollows, RawValue);
534 }
IntValue(int64_t IntValue)535 static MatchTableRecord IntValue(int64_t IntValue) {
536 return MatchTableRecord(None, llvm::to_string(IntValue), 1,
537 MatchTableRecord::MTRF_CommaFollows);
538 }
Label(unsigned LabelID)539 static MatchTableRecord Label(unsigned LabelID) {
540 return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 0,
541 MatchTableRecord::MTRF_Label |
542 MatchTableRecord::MTRF_Comment |
543 MatchTableRecord::MTRF_LineBreakFollows);
544 }
JumpTarget(unsigned LabelID)545 static MatchTableRecord JumpTarget(unsigned LabelID) {
546 return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 1,
547 MatchTableRecord::MTRF_JumpTarget |
548 MatchTableRecord::MTRF_Comment |
549 MatchTableRecord::MTRF_CommaFollows);
550 }
551
552 static MatchTable buildTable(ArrayRef<Matcher *> Rules, bool WithCoverage);
553
MatchTable(bool WithCoverage,unsigned ID=0)554 MatchTable(bool WithCoverage, unsigned ID = 0)
555 : ID(ID), IsWithCoverage(WithCoverage) {}
556
isWithCoverage() const557 bool isWithCoverage() const { return IsWithCoverage; }
558
push_back(const MatchTableRecord & Value)559 void push_back(const MatchTableRecord &Value) {
560 if (Value.Flags & MatchTableRecord::MTRF_Label)
561 defineLabel(Value.LabelID);
562 Contents.push_back(Value);
563 CurrentSize += Value.size();
564 }
565
allocateLabelID()566 unsigned allocateLabelID() { return CurrentLabelID++; }
567
defineLabel(unsigned LabelID)568 void defineLabel(unsigned LabelID) {
569 LabelMap.insert(std::make_pair(LabelID, CurrentSize));
570 }
571
getLabelIndex(unsigned LabelID) const572 unsigned getLabelIndex(unsigned LabelID) const {
573 const auto I = LabelMap.find(LabelID);
574 assert(I != LabelMap.end() && "Use of undeclared label");
575 return I->second;
576 }
577
emitUse(raw_ostream & OS) const578 void emitUse(raw_ostream &OS) const { OS << "MatchTable" << ID; }
579
emitDeclaration(raw_ostream & OS) const580 void emitDeclaration(raw_ostream &OS) const {
581 unsigned Indentation = 4;
582 OS << " constexpr static int64_t MatchTable" << ID << "[] = {";
583 LineBreak.emit(OS, true, *this);
584 OS << std::string(Indentation, ' ');
585
586 for (auto I = Contents.begin(), E = Contents.end(); I != E;
587 ++I) {
588 bool LineBreakIsNext = false;
589 const auto &NextI = std::next(I);
590
591 if (NextI != E) {
592 if (NextI->EmitStr == "" &&
593 NextI->Flags == MatchTableRecord::MTRF_LineBreakFollows)
594 LineBreakIsNext = true;
595 }
596
597 if (I->Flags & MatchTableRecord::MTRF_Indent)
598 Indentation += 2;
599
600 I->emit(OS, LineBreakIsNext, *this);
601 if (I->Flags & MatchTableRecord::MTRF_LineBreakFollows)
602 OS << std::string(Indentation, ' ');
603
604 if (I->Flags & MatchTableRecord::MTRF_Outdent)
605 Indentation -= 2;
606 }
607 OS << "};\n";
608 }
609 };
610
611 MatchTableRecord MatchTable::LineBreak = {
612 None, "" /* Emit String */, 0 /* Elements */,
613 MatchTableRecord::MTRF_LineBreakFollows};
614
emit(raw_ostream & OS,bool LineBreakIsNextAfterThis,const MatchTable & Table) const615 void MatchTableRecord::emit(raw_ostream &OS, bool LineBreakIsNextAfterThis,
616 const MatchTable &Table) const {
617 bool UseLineComment =
618 LineBreakIsNextAfterThis || (Flags & MTRF_LineBreakFollows);
619 if (Flags & (MTRF_JumpTarget | MTRF_CommaFollows))
620 UseLineComment = false;
621
622 if (Flags & MTRF_Comment)
623 OS << (UseLineComment ? "// " : "/*");
624
625 OS << EmitStr;
626 if (Flags & MTRF_Label)
627 OS << ": @" << Table.getLabelIndex(LabelID);
628
629 if ((Flags & MTRF_Comment) && !UseLineComment)
630 OS << "*/";
631
632 if (Flags & MTRF_JumpTarget) {
633 if (Flags & MTRF_Comment)
634 OS << " ";
635 OS << Table.getLabelIndex(LabelID);
636 }
637
638 if (Flags & MTRF_CommaFollows) {
639 OS << ",";
640 if (!LineBreakIsNextAfterThis && !(Flags & MTRF_LineBreakFollows))
641 OS << " ";
642 }
643
644 if (Flags & MTRF_LineBreakFollows)
645 OS << "\n";
646 }
647
operator <<(MatchTable & Table,const MatchTableRecord & Value)648 MatchTable &operator<<(MatchTable &Table, const MatchTableRecord &Value) {
649 Table.push_back(Value);
650 return Table;
651 }
652
653 //===- Matchers -----------------------------------------------------------===//
654
655 class OperandMatcher;
656 class MatchAction;
657 class PredicateMatcher;
658 class RuleMatcher;
659
660 class Matcher {
661 public:
662 virtual ~Matcher() = default;
optimize()663 virtual void optimize() {}
664 virtual void emit(MatchTable &Table) = 0;
665
666 virtual bool hasFirstCondition() const = 0;
667 virtual const PredicateMatcher &getFirstCondition() const = 0;
668 virtual std::unique_ptr<PredicateMatcher> popFirstCondition() = 0;
669 };
670
buildTable(ArrayRef<Matcher * > Rules,bool WithCoverage)671 MatchTable MatchTable::buildTable(ArrayRef<Matcher *> Rules,
672 bool WithCoverage) {
673 MatchTable Table(WithCoverage);
674 for (Matcher *Rule : Rules)
675 Rule->emit(Table);
676
677 return Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
678 }
679
680 class GroupMatcher final : public Matcher {
681 /// Conditions that form a common prefix of all the matchers contained.
682 SmallVector<std::unique_ptr<PredicateMatcher>, 1> Conditions;
683
684 /// All the nested matchers, sharing a common prefix.
685 std::vector<Matcher *> Matchers;
686
687 /// An owning collection for any auxiliary matchers created while optimizing
688 /// nested matchers contained.
689 std::vector<std::unique_ptr<Matcher>> MatcherStorage;
690
691 public:
692 /// Add a matcher to the collection of nested matchers if it meets the
693 /// requirements, and return true. If it doesn't, do nothing and return false.
694 ///
695 /// Expected to preserve its argument, so it could be moved out later on.
696 bool addMatcher(Matcher &Candidate);
697
698 /// Mark the matcher as fully-built and ensure any invariants expected by both
699 /// optimize() and emit(...) methods. Generally, both sequences of calls
700 /// are expected to lead to a sensible result:
701 ///
702 /// addMatcher(...)*; finalize(); optimize(); emit(...); and
703 /// addMatcher(...)*; finalize(); emit(...);
704 ///
705 /// or generally
706 ///
707 /// addMatcher(...)*; finalize(); { optimize()*; emit(...); }*
708 ///
709 /// Multiple calls to optimize() are expected to be handled gracefully, though
710 /// optimize() is not expected to be idempotent. Multiple calls to finalize()
711 /// aren't generally supported. emit(...) is expected to be non-mutating and
712 /// producing the exact same results upon repeated calls.
713 ///
714 /// addMatcher() calls after the finalize() call are not supported.
715 ///
716 /// finalize() and optimize() are both allowed to mutate the contained
717 /// matchers, so moving them out after finalize() is not supported.
718 void finalize();
719 void optimize() override;
720 void emit(MatchTable &Table) override;
721
722 /// Could be used to move out the matchers added previously, unless finalize()
723 /// has been already called. If any of the matchers are moved out, the group
724 /// becomes safe to destroy, but not safe to re-use for anything else.
matchers()725 iterator_range<std::vector<Matcher *>::iterator> matchers() {
726 return make_range(Matchers.begin(), Matchers.end());
727 }
size() const728 size_t size() const { return Matchers.size(); }
empty() const729 bool empty() const { return Matchers.empty(); }
730
popFirstCondition()731 std::unique_ptr<PredicateMatcher> popFirstCondition() override {
732 assert(!Conditions.empty() &&
733 "Trying to pop a condition from a condition-less group");
734 std::unique_ptr<PredicateMatcher> P = std::move(Conditions.front());
735 Conditions.erase(Conditions.begin());
736 return P;
737 }
getFirstCondition() const738 const PredicateMatcher &getFirstCondition() const override {
739 assert(!Conditions.empty() &&
740 "Trying to get a condition from a condition-less group");
741 return *Conditions.front();
742 }
hasFirstCondition() const743 bool hasFirstCondition() const override { return !Conditions.empty(); }
744
745 private:
746 /// See if a candidate matcher could be added to this group solely by
747 /// analyzing its first condition.
748 bool candidateConditionMatches(const PredicateMatcher &Predicate) const;
749 };
750
751 class SwitchMatcher : public Matcher {
752 /// All the nested matchers, representing distinct switch-cases. The first
753 /// conditions (as Matcher::getFirstCondition() reports) of all the nested
754 /// matchers must share the same type and path to a value they check, in other
755 /// words, be isIdenticalDownToValue, but have different values they check
756 /// against.
757 std::vector<Matcher *> Matchers;
758
759 /// The representative condition, with a type and a path (InsnVarID and OpIdx
760 /// in most cases) shared by all the matchers contained.
761 std::unique_ptr<PredicateMatcher> Condition = nullptr;
762
763 /// Temporary set used to check that the case values don't repeat within the
764 /// same switch.
765 std::set<MatchTableRecord> Values;
766
767 /// An owning collection for any auxiliary matchers created while optimizing
768 /// nested matchers contained.
769 std::vector<std::unique_ptr<Matcher>> MatcherStorage;
770
771 public:
772 bool addMatcher(Matcher &Candidate);
773
774 void finalize();
775 void emit(MatchTable &Table) override;
776
matchers()777 iterator_range<std::vector<Matcher *>::iterator> matchers() {
778 return make_range(Matchers.begin(), Matchers.end());
779 }
size() const780 size_t size() const { return Matchers.size(); }
empty() const781 bool empty() const { return Matchers.empty(); }
782
popFirstCondition()783 std::unique_ptr<PredicateMatcher> popFirstCondition() override {
784 // SwitchMatcher doesn't have a common first condition for its cases, as all
785 // the cases only share a kind of a value (a type and a path to it) they
786 // match, but deliberately differ in the actual value they match.
787 llvm_unreachable("Trying to pop a condition from a condition-less group");
788 }
getFirstCondition() const789 const PredicateMatcher &getFirstCondition() const override {
790 llvm_unreachable("Trying to pop a condition from a condition-less group");
791 }
hasFirstCondition() const792 bool hasFirstCondition() const override { return false; }
793
794 private:
795 /// See if the predicate type has a Switch-implementation for it.
796 static bool isSupportedPredicateType(const PredicateMatcher &Predicate);
797
798 bool candidateConditionMatches(const PredicateMatcher &Predicate) const;
799
800 /// emit()-helper
801 static void emitPredicateSpecificOpcodes(const PredicateMatcher &P,
802 MatchTable &Table);
803 };
804
805 /// Generates code to check that a match rule matches.
806 class RuleMatcher : public Matcher {
807 public:
808 using ActionList = std::list<std::unique_ptr<MatchAction>>;
809 using action_iterator = ActionList::iterator;
810
811 protected:
812 /// A list of matchers that all need to succeed for the current rule to match.
813 /// FIXME: This currently supports a single match position but could be
814 /// extended to support multiple positions to support div/rem fusion or
815 /// load-multiple instructions.
816 using MatchersTy = std::vector<std::unique_ptr<InstructionMatcher>> ;
817 MatchersTy Matchers;
818
819 /// A list of actions that need to be taken when all predicates in this rule
820 /// have succeeded.
821 ActionList Actions;
822
823 using DefinedInsnVariablesMap = std::map<InstructionMatcher *, unsigned>;
824
825 /// A map of instruction matchers to the local variables
826 DefinedInsnVariablesMap InsnVariableIDs;
827
828 using MutatableInsnSet = SmallPtrSet<InstructionMatcher *, 4>;
829
830 // The set of instruction matchers that have not yet been claimed for mutation
831 // by a BuildMI.
832 MutatableInsnSet MutatableInsns;
833
834 /// A map of named operands defined by the matchers that may be referenced by
835 /// the renderers.
836 StringMap<OperandMatcher *> DefinedOperands;
837
838 /// A map of anonymous physical register operands defined by the matchers that
839 /// may be referenced by the renderers.
840 DenseMap<Record *, OperandMatcher *> PhysRegOperands;
841
842 /// ID for the next instruction variable defined with implicitlyDefineInsnVar()
843 unsigned NextInsnVarID;
844
845 /// ID for the next output instruction allocated with allocateOutputInsnID()
846 unsigned NextOutputInsnID;
847
848 /// ID for the next temporary register ID allocated with allocateTempRegID()
849 unsigned NextTempRegID;
850
851 std::vector<Record *> RequiredFeatures;
852 std::vector<std::unique_ptr<PredicateMatcher>> EpilogueMatchers;
853
854 ArrayRef<SMLoc> SrcLoc;
855
856 typedef std::tuple<Record *, unsigned, unsigned>
857 DefinedComplexPatternSubOperand;
858 typedef StringMap<DefinedComplexPatternSubOperand>
859 DefinedComplexPatternSubOperandMap;
860 /// A map of Symbolic Names to ComplexPattern sub-operands.
861 DefinedComplexPatternSubOperandMap ComplexSubOperands;
862 /// A map used to for multiple referenced error check of ComplexSubOperand.
863 /// ComplexSubOperand can't be referenced multiple from different operands,
864 /// however multiple references from same operand are allowed since that is
865 /// how 'same operand checks' are generated.
866 StringMap<std::string> ComplexSubOperandsParentName;
867
868 uint64_t RuleID;
869 static uint64_t NextRuleID;
870
871 public:
RuleMatcher(ArrayRef<SMLoc> SrcLoc)872 RuleMatcher(ArrayRef<SMLoc> SrcLoc)
873 : Matchers(), Actions(), InsnVariableIDs(), MutatableInsns(),
874 DefinedOperands(), NextInsnVarID(0), NextOutputInsnID(0),
875 NextTempRegID(0), SrcLoc(SrcLoc), ComplexSubOperands(),
876 RuleID(NextRuleID++) {}
877 RuleMatcher(RuleMatcher &&Other) = default;
878 RuleMatcher &operator=(RuleMatcher &&Other) = default;
879
getRuleID() const880 uint64_t getRuleID() const { return RuleID; }
881
882 InstructionMatcher &addInstructionMatcher(StringRef SymbolicName);
883 void addRequiredFeature(Record *Feature);
884 const std::vector<Record *> &getRequiredFeatures() const;
885
886 template <class Kind, class... Args> Kind &addAction(Args &&... args);
887 template <class Kind, class... Args>
888 action_iterator insertAction(action_iterator InsertPt, Args &&... args);
889
890 /// Define an instruction without emitting any code to do so.
891 unsigned implicitlyDefineInsnVar(InstructionMatcher &Matcher);
892
893 unsigned getInsnVarID(InstructionMatcher &InsnMatcher) const;
defined_insn_vars_begin() const894 DefinedInsnVariablesMap::const_iterator defined_insn_vars_begin() const {
895 return InsnVariableIDs.begin();
896 }
defined_insn_vars_end() const897 DefinedInsnVariablesMap::const_iterator defined_insn_vars_end() const {
898 return InsnVariableIDs.end();
899 }
900 iterator_range<typename DefinedInsnVariablesMap::const_iterator>
defined_insn_vars() const901 defined_insn_vars() const {
902 return make_range(defined_insn_vars_begin(), defined_insn_vars_end());
903 }
904
mutatable_insns_begin() const905 MutatableInsnSet::const_iterator mutatable_insns_begin() const {
906 return MutatableInsns.begin();
907 }
mutatable_insns_end() const908 MutatableInsnSet::const_iterator mutatable_insns_end() const {
909 return MutatableInsns.end();
910 }
911 iterator_range<typename MutatableInsnSet::const_iterator>
mutatable_insns() const912 mutatable_insns() const {
913 return make_range(mutatable_insns_begin(), mutatable_insns_end());
914 }
reserveInsnMatcherForMutation(InstructionMatcher * InsnMatcher)915 void reserveInsnMatcherForMutation(InstructionMatcher *InsnMatcher) {
916 bool R = MutatableInsns.erase(InsnMatcher);
917 assert(R && "Reserving a mutatable insn that isn't available");
918 (void)R;
919 }
920
actions_begin()921 action_iterator actions_begin() { return Actions.begin(); }
actions_end()922 action_iterator actions_end() { return Actions.end(); }
actions()923 iterator_range<action_iterator> actions() {
924 return make_range(actions_begin(), actions_end());
925 }
926
927 void defineOperand(StringRef SymbolicName, OperandMatcher &OM);
928
929 void definePhysRegOperand(Record *Reg, OperandMatcher &OM);
930
defineComplexSubOperand(StringRef SymbolicName,Record * ComplexPattern,unsigned RendererID,unsigned SubOperandID,StringRef ParentSymbolicName)931 Error defineComplexSubOperand(StringRef SymbolicName, Record *ComplexPattern,
932 unsigned RendererID, unsigned SubOperandID,
933 StringRef ParentSymbolicName) {
934 std::string ParentName(ParentSymbolicName);
935 if (ComplexSubOperands.count(SymbolicName)) {
936 const std::string &RecordedParentName =
937 ComplexSubOperandsParentName[SymbolicName];
938 if (RecordedParentName != ParentName)
939 return failedImport("Error: Complex suboperand " + SymbolicName +
940 " referenced by different operands: " +
941 RecordedParentName + " and " + ParentName + ".");
942 // Complex suboperand referenced more than once from same the operand is
943 // used to generate 'same operand check'. Emitting of
944 // GIR_ComplexSubOperandRenderer for them is already handled.
945 return Error::success();
946 }
947
948 ComplexSubOperands[SymbolicName] =
949 std::make_tuple(ComplexPattern, RendererID, SubOperandID);
950 ComplexSubOperandsParentName[SymbolicName] = ParentName;
951
952 return Error::success();
953 }
954
955 Optional<DefinedComplexPatternSubOperand>
getComplexSubOperand(StringRef SymbolicName) const956 getComplexSubOperand(StringRef SymbolicName) const {
957 const auto &I = ComplexSubOperands.find(SymbolicName);
958 if (I == ComplexSubOperands.end())
959 return None;
960 return I->second;
961 }
962
963 InstructionMatcher &getInstructionMatcher(StringRef SymbolicName) const;
964 const OperandMatcher &getOperandMatcher(StringRef Name) const;
965 const OperandMatcher &getPhysRegOperandMatcher(Record *) const;
966
967 void optimize() override;
968 void emit(MatchTable &Table) override;
969
970 /// Compare the priority of this object and B.
971 ///
972 /// Returns true if this object is more important than B.
973 bool isHigherPriorityThan(const RuleMatcher &B) const;
974
975 /// Report the maximum number of temporary operands needed by the rule
976 /// matcher.
977 unsigned countRendererFns() const;
978
979 std::unique_ptr<PredicateMatcher> popFirstCondition() override;
980 const PredicateMatcher &getFirstCondition() const override;
981 LLTCodeGen getFirstConditionAsRootType();
982 bool hasFirstCondition() const override;
983 unsigned getNumOperands() const;
984 StringRef getOpcode() const;
985
986 // FIXME: Remove this as soon as possible
insnmatchers_front() const987 InstructionMatcher &insnmatchers_front() const { return *Matchers.front(); }
988
allocateOutputInsnID()989 unsigned allocateOutputInsnID() { return NextOutputInsnID++; }
allocateTempRegID()990 unsigned allocateTempRegID() { return NextTempRegID++; }
991
insnmatchers()992 iterator_range<MatchersTy::iterator> insnmatchers() {
993 return make_range(Matchers.begin(), Matchers.end());
994 }
insnmatchers_empty() const995 bool insnmatchers_empty() const { return Matchers.empty(); }
insnmatchers_pop_front()996 void insnmatchers_pop_front() { Matchers.erase(Matchers.begin()); }
997 };
998
999 uint64_t RuleMatcher::NextRuleID = 0;
1000
1001 using action_iterator = RuleMatcher::action_iterator;
1002
1003 template <class PredicateTy> class PredicateListMatcher {
1004 private:
1005 /// Template instantiations should specialize this to return a string to use
1006 /// for the comment emitted when there are no predicates.
1007 std::string getNoPredicateComment() const;
1008
1009 protected:
1010 using PredicatesTy = std::deque<std::unique_ptr<PredicateTy>>;
1011 PredicatesTy Predicates;
1012
1013 /// Track if the list of predicates was manipulated by one of the optimization
1014 /// methods.
1015 bool Optimized = false;
1016
1017 public:
predicates_begin()1018 typename PredicatesTy::iterator predicates_begin() {
1019 return Predicates.begin();
1020 }
predicates_end()1021 typename PredicatesTy::iterator predicates_end() {
1022 return Predicates.end();
1023 }
predicates()1024 iterator_range<typename PredicatesTy::iterator> predicates() {
1025 return make_range(predicates_begin(), predicates_end());
1026 }
predicates_size() const1027 typename PredicatesTy::size_type predicates_size() const {
1028 return Predicates.size();
1029 }
predicates_empty() const1030 bool predicates_empty() const { return Predicates.empty(); }
1031
predicates_pop_front()1032 std::unique_ptr<PredicateTy> predicates_pop_front() {
1033 std::unique_ptr<PredicateTy> Front = std::move(Predicates.front());
1034 Predicates.pop_front();
1035 Optimized = true;
1036 return Front;
1037 }
1038
prependPredicate(std::unique_ptr<PredicateTy> && Predicate)1039 void prependPredicate(std::unique_ptr<PredicateTy> &&Predicate) {
1040 Predicates.push_front(std::move(Predicate));
1041 }
1042
eraseNullPredicates()1043 void eraseNullPredicates() {
1044 const auto NewEnd =
1045 std::stable_partition(Predicates.begin(), Predicates.end(),
1046 std::logical_not<std::unique_ptr<PredicateTy>>());
1047 if (NewEnd != Predicates.begin()) {
1048 Predicates.erase(Predicates.begin(), NewEnd);
1049 Optimized = true;
1050 }
1051 }
1052
1053 /// Emit MatchTable opcodes that tests whether all the predicates are met.
1054 template <class... Args>
emitPredicateListOpcodes(MatchTable & Table,Args &&...args)1055 void emitPredicateListOpcodes(MatchTable &Table, Args &&... args) {
1056 if (Predicates.empty() && !Optimized) {
1057 Table << MatchTable::Comment(getNoPredicateComment())
1058 << MatchTable::LineBreak;
1059 return;
1060 }
1061
1062 for (const auto &Predicate : predicates())
1063 Predicate->emitPredicateOpcodes(Table, std::forward<Args>(args)...);
1064 }
1065
1066 /// Provide a function to avoid emitting certain predicates. This is used to
1067 /// defer some predicate checks until after others
1068 using PredicateFilterFunc = std::function<bool(const PredicateTy&)>;
1069
1070 /// Emit MatchTable opcodes for predicates which satisfy \p
1071 /// ShouldEmitPredicate. This should be called multiple times to ensure all
1072 /// predicates are eventually added to the match table.
1073 template <class... Args>
emitFilteredPredicateListOpcodes(PredicateFilterFunc ShouldEmitPredicate,MatchTable & Table,Args &&...args)1074 void emitFilteredPredicateListOpcodes(PredicateFilterFunc ShouldEmitPredicate,
1075 MatchTable &Table, Args &&... args) {
1076 if (Predicates.empty() && !Optimized) {
1077 Table << MatchTable::Comment(getNoPredicateComment())
1078 << MatchTable::LineBreak;
1079 return;
1080 }
1081
1082 for (const auto &Predicate : predicates()) {
1083 if (ShouldEmitPredicate(*Predicate))
1084 Predicate->emitPredicateOpcodes(Table, std::forward<Args>(args)...);
1085 }
1086 }
1087 };
1088
1089 class PredicateMatcher {
1090 public:
1091 /// This enum is used for RTTI and also defines the priority that is given to
1092 /// the predicate when generating the matcher code. Kinds with higher priority
1093 /// must be tested first.
1094 ///
1095 /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter
1096 /// but OPM_Int must have priority over OPM_RegBank since constant integers
1097 /// are represented by a virtual register defined by a G_CONSTANT instruction.
1098 ///
1099 /// Note: The relative priority between IPM_ and OPM_ does not matter, they
1100 /// are currently not compared between each other.
1101 enum PredicateKind {
1102 IPM_Opcode,
1103 IPM_NumOperands,
1104 IPM_ImmPredicate,
1105 IPM_Imm,
1106 IPM_AtomicOrderingMMO,
1107 IPM_MemoryLLTSize,
1108 IPM_MemoryVsLLTSize,
1109 IPM_MemoryAddressSpace,
1110 IPM_MemoryAlignment,
1111 IPM_VectorSplatImm,
1112 IPM_GenericPredicate,
1113 OPM_SameOperand,
1114 OPM_ComplexPattern,
1115 OPM_IntrinsicID,
1116 OPM_CmpPredicate,
1117 OPM_Instruction,
1118 OPM_Int,
1119 OPM_LiteralInt,
1120 OPM_LLT,
1121 OPM_PointerToAny,
1122 OPM_RegBank,
1123 OPM_MBB,
1124 OPM_RecordNamedOperand,
1125 };
1126
1127 protected:
1128 PredicateKind Kind;
1129 unsigned InsnVarID;
1130 unsigned OpIdx;
1131
1132 public:
PredicateMatcher(PredicateKind Kind,unsigned InsnVarID,unsigned OpIdx=~0)1133 PredicateMatcher(PredicateKind Kind, unsigned InsnVarID, unsigned OpIdx = ~0)
1134 : Kind(Kind), InsnVarID(InsnVarID), OpIdx(OpIdx) {}
1135
getInsnVarID() const1136 unsigned getInsnVarID() const { return InsnVarID; }
getOpIdx() const1137 unsigned getOpIdx() const { return OpIdx; }
1138
1139 virtual ~PredicateMatcher() = default;
1140 /// Emit MatchTable opcodes that check the predicate for the given operand.
1141 virtual void emitPredicateOpcodes(MatchTable &Table,
1142 RuleMatcher &Rule) const = 0;
1143
getKind() const1144 PredicateKind getKind() const { return Kind; }
1145
dependsOnOperands() const1146 bool dependsOnOperands() const {
1147 // Custom predicates really depend on the context pattern of the
1148 // instruction, not just the individual instruction. This therefore
1149 // implicitly depends on all other pattern constraints.
1150 return Kind == IPM_GenericPredicate;
1151 }
1152
isIdentical(const PredicateMatcher & B) const1153 virtual bool isIdentical(const PredicateMatcher &B) const {
1154 return B.getKind() == getKind() && InsnVarID == B.InsnVarID &&
1155 OpIdx == B.OpIdx;
1156 }
1157
isIdenticalDownToValue(const PredicateMatcher & B) const1158 virtual bool isIdenticalDownToValue(const PredicateMatcher &B) const {
1159 return hasValue() && PredicateMatcher::isIdentical(B);
1160 }
1161
getValue() const1162 virtual MatchTableRecord getValue() const {
1163 assert(hasValue() && "Can not get a value of a value-less predicate!");
1164 llvm_unreachable("Not implemented yet");
1165 }
hasValue() const1166 virtual bool hasValue() const { return false; }
1167
1168 /// Report the maximum number of temporary operands needed by the predicate
1169 /// matcher.
countRendererFns() const1170 virtual unsigned countRendererFns() const { return 0; }
1171 };
1172
1173 /// Generates code to check a predicate of an operand.
1174 ///
1175 /// Typical predicates include:
1176 /// * Operand is a particular register.
1177 /// * Operand is assigned a particular register bank.
1178 /// * Operand is an MBB.
1179 class OperandPredicateMatcher : public PredicateMatcher {
1180 public:
OperandPredicateMatcher(PredicateKind Kind,unsigned InsnVarID,unsigned OpIdx)1181 OperandPredicateMatcher(PredicateKind Kind, unsigned InsnVarID,
1182 unsigned OpIdx)
1183 : PredicateMatcher(Kind, InsnVarID, OpIdx) {}
~OperandPredicateMatcher()1184 virtual ~OperandPredicateMatcher() {}
1185
1186 /// Compare the priority of this object and B.
1187 ///
1188 /// Returns true if this object is more important than B.
1189 virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const;
1190 };
1191
1192 template <>
1193 std::string
getNoPredicateComment() const1194 PredicateListMatcher<OperandPredicateMatcher>::getNoPredicateComment() const {
1195 return "No operand predicates";
1196 }
1197
1198 /// Generates code to check that a register operand is defined by the same exact
1199 /// one as another.
1200 class SameOperandMatcher : public OperandPredicateMatcher {
1201 std::string MatchingName;
1202
1203 public:
SameOperandMatcher(unsigned InsnVarID,unsigned OpIdx,StringRef MatchingName)1204 SameOperandMatcher(unsigned InsnVarID, unsigned OpIdx, StringRef MatchingName)
1205 : OperandPredicateMatcher(OPM_SameOperand, InsnVarID, OpIdx),
1206 MatchingName(MatchingName) {}
1207
classof(const PredicateMatcher * P)1208 static bool classof(const PredicateMatcher *P) {
1209 return P->getKind() == OPM_SameOperand;
1210 }
1211
1212 void emitPredicateOpcodes(MatchTable &Table,
1213 RuleMatcher &Rule) const override;
1214
isIdentical(const PredicateMatcher & B) const1215 bool isIdentical(const PredicateMatcher &B) const override {
1216 return OperandPredicateMatcher::isIdentical(B) &&
1217 MatchingName == cast<SameOperandMatcher>(&B)->MatchingName;
1218 }
1219 };
1220
1221 /// Generates code to check that an operand is a particular LLT.
1222 class LLTOperandMatcher : public OperandPredicateMatcher {
1223 protected:
1224 LLTCodeGen Ty;
1225
1226 public:
1227 static std::map<LLTCodeGen, unsigned> TypeIDValues;
1228
initTypeIDValuesMap()1229 static void initTypeIDValuesMap() {
1230 TypeIDValues.clear();
1231
1232 unsigned ID = 0;
1233 for (const LLTCodeGen &LLTy : KnownTypes)
1234 TypeIDValues[LLTy] = ID++;
1235 }
1236
LLTOperandMatcher(unsigned InsnVarID,unsigned OpIdx,const LLTCodeGen & Ty)1237 LLTOperandMatcher(unsigned InsnVarID, unsigned OpIdx, const LLTCodeGen &Ty)
1238 : OperandPredicateMatcher(OPM_LLT, InsnVarID, OpIdx), Ty(Ty) {
1239 KnownTypes.insert(Ty);
1240 }
1241
classof(const PredicateMatcher * P)1242 static bool classof(const PredicateMatcher *P) {
1243 return P->getKind() == OPM_LLT;
1244 }
isIdentical(const PredicateMatcher & B) const1245 bool isIdentical(const PredicateMatcher &B) const override {
1246 return OperandPredicateMatcher::isIdentical(B) &&
1247 Ty == cast<LLTOperandMatcher>(&B)->Ty;
1248 }
getValue() const1249 MatchTableRecord getValue() const override {
1250 const auto VI = TypeIDValues.find(Ty);
1251 if (VI == TypeIDValues.end())
1252 return MatchTable::NamedValue(getTy().getCxxEnumValue());
1253 return MatchTable::NamedValue(getTy().getCxxEnumValue(), VI->second);
1254 }
hasValue() const1255 bool hasValue() const override {
1256 if (TypeIDValues.size() != KnownTypes.size())
1257 initTypeIDValuesMap();
1258 return TypeIDValues.count(Ty);
1259 }
1260
getTy() const1261 LLTCodeGen getTy() const { return Ty; }
1262
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1263 void emitPredicateOpcodes(MatchTable &Table,
1264 RuleMatcher &Rule) const override {
1265 Table << MatchTable::Opcode("GIM_CheckType") << MatchTable::Comment("MI")
1266 << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
1267 << MatchTable::IntValue(OpIdx) << MatchTable::Comment("Type")
1268 << getValue() << MatchTable::LineBreak;
1269 }
1270 };
1271
1272 std::map<LLTCodeGen, unsigned> LLTOperandMatcher::TypeIDValues;
1273
1274 /// Generates code to check that an operand is a pointer to any address space.
1275 ///
1276 /// In SelectionDAG, the types did not describe pointers or address spaces. As a
1277 /// result, iN is used to describe a pointer of N bits to any address space and
1278 /// PatFrag predicates are typically used to constrain the address space. There's
1279 /// no reliable means to derive the missing type information from the pattern so
1280 /// imported rules must test the components of a pointer separately.
1281 ///
1282 /// If SizeInBits is zero, then the pointer size will be obtained from the
1283 /// subtarget.
1284 class PointerToAnyOperandMatcher : public OperandPredicateMatcher {
1285 protected:
1286 unsigned SizeInBits;
1287
1288 public:
PointerToAnyOperandMatcher(unsigned InsnVarID,unsigned OpIdx,unsigned SizeInBits)1289 PointerToAnyOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1290 unsigned SizeInBits)
1291 : OperandPredicateMatcher(OPM_PointerToAny, InsnVarID, OpIdx),
1292 SizeInBits(SizeInBits) {}
1293
classof(const PredicateMatcher * P)1294 static bool classof(const PredicateMatcher *P) {
1295 return P->getKind() == OPM_PointerToAny;
1296 }
1297
isIdentical(const PredicateMatcher & B) const1298 bool isIdentical(const PredicateMatcher &B) const override {
1299 return OperandPredicateMatcher::isIdentical(B) &&
1300 SizeInBits == cast<PointerToAnyOperandMatcher>(&B)->SizeInBits;
1301 }
1302
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1303 void emitPredicateOpcodes(MatchTable &Table,
1304 RuleMatcher &Rule) const override {
1305 Table << MatchTable::Opcode("GIM_CheckPointerToAny")
1306 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1307 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1308 << MatchTable::Comment("SizeInBits")
1309 << MatchTable::IntValue(SizeInBits) << MatchTable::LineBreak;
1310 }
1311 };
1312
1313 /// Generates code to record named operand in RecordedOperands list at StoreIdx.
1314 /// Predicates with 'let PredicateCodeUsesOperands = 1' get RecordedOperands as
1315 /// an argument to predicate's c++ code once all operands have been matched.
1316 class RecordNamedOperandMatcher : public OperandPredicateMatcher {
1317 protected:
1318 unsigned StoreIdx;
1319 std::string Name;
1320
1321 public:
RecordNamedOperandMatcher(unsigned InsnVarID,unsigned OpIdx,unsigned StoreIdx,StringRef Name)1322 RecordNamedOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1323 unsigned StoreIdx, StringRef Name)
1324 : OperandPredicateMatcher(OPM_RecordNamedOperand, InsnVarID, OpIdx),
1325 StoreIdx(StoreIdx), Name(Name) {}
1326
classof(const PredicateMatcher * P)1327 static bool classof(const PredicateMatcher *P) {
1328 return P->getKind() == OPM_RecordNamedOperand;
1329 }
1330
isIdentical(const PredicateMatcher & B) const1331 bool isIdentical(const PredicateMatcher &B) const override {
1332 return OperandPredicateMatcher::isIdentical(B) &&
1333 StoreIdx == cast<RecordNamedOperandMatcher>(&B)->StoreIdx &&
1334 Name == cast<RecordNamedOperandMatcher>(&B)->Name;
1335 }
1336
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1337 void emitPredicateOpcodes(MatchTable &Table,
1338 RuleMatcher &Rule) const override {
1339 Table << MatchTable::Opcode("GIM_RecordNamedOperand")
1340 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1341 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1342 << MatchTable::Comment("StoreIdx") << MatchTable::IntValue(StoreIdx)
1343 << MatchTable::Comment("Name : " + Name) << MatchTable::LineBreak;
1344 }
1345 };
1346
1347 /// Generates code to check that an operand is a particular target constant.
1348 class ComplexPatternOperandMatcher : public OperandPredicateMatcher {
1349 protected:
1350 const OperandMatcher &Operand;
1351 const Record &TheDef;
1352
1353 unsigned getAllocatedTemporariesBaseID() const;
1354
1355 public:
isIdentical(const PredicateMatcher & B) const1356 bool isIdentical(const PredicateMatcher &B) const override { return false; }
1357
ComplexPatternOperandMatcher(unsigned InsnVarID,unsigned OpIdx,const OperandMatcher & Operand,const Record & TheDef)1358 ComplexPatternOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1359 const OperandMatcher &Operand,
1360 const Record &TheDef)
1361 : OperandPredicateMatcher(OPM_ComplexPattern, InsnVarID, OpIdx),
1362 Operand(Operand), TheDef(TheDef) {}
1363
classof(const PredicateMatcher * P)1364 static bool classof(const PredicateMatcher *P) {
1365 return P->getKind() == OPM_ComplexPattern;
1366 }
1367
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1368 void emitPredicateOpcodes(MatchTable &Table,
1369 RuleMatcher &Rule) const override {
1370 unsigned ID = getAllocatedTemporariesBaseID();
1371 Table << MatchTable::Opcode("GIM_CheckComplexPattern")
1372 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1373 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1374 << MatchTable::Comment("Renderer") << MatchTable::IntValue(ID)
1375 << MatchTable::NamedValue(("GICP_" + TheDef.getName()).str())
1376 << MatchTable::LineBreak;
1377 }
1378
countRendererFns() const1379 unsigned countRendererFns() const override {
1380 return 1;
1381 }
1382 };
1383
1384 /// Generates code to check that an operand is in a particular register bank.
1385 class RegisterBankOperandMatcher : public OperandPredicateMatcher {
1386 protected:
1387 const CodeGenRegisterClass &RC;
1388
1389 public:
RegisterBankOperandMatcher(unsigned InsnVarID,unsigned OpIdx,const CodeGenRegisterClass & RC)1390 RegisterBankOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1391 const CodeGenRegisterClass &RC)
1392 : OperandPredicateMatcher(OPM_RegBank, InsnVarID, OpIdx), RC(RC) {}
1393
isIdentical(const PredicateMatcher & B) const1394 bool isIdentical(const PredicateMatcher &B) const override {
1395 return OperandPredicateMatcher::isIdentical(B) &&
1396 RC.getDef() == cast<RegisterBankOperandMatcher>(&B)->RC.getDef();
1397 }
1398
classof(const PredicateMatcher * P)1399 static bool classof(const PredicateMatcher *P) {
1400 return P->getKind() == OPM_RegBank;
1401 }
1402
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1403 void emitPredicateOpcodes(MatchTable &Table,
1404 RuleMatcher &Rule) const override {
1405 Table << MatchTable::Opcode("GIM_CheckRegBankForClass")
1406 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1407 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1408 << MatchTable::Comment("RC")
1409 << MatchTable::NamedValue(RC.getQualifiedName() + "RegClassID")
1410 << MatchTable::LineBreak;
1411 }
1412 };
1413
1414 /// Generates code to check that an operand is a basic block.
1415 class MBBOperandMatcher : public OperandPredicateMatcher {
1416 public:
MBBOperandMatcher(unsigned InsnVarID,unsigned OpIdx)1417 MBBOperandMatcher(unsigned InsnVarID, unsigned OpIdx)
1418 : OperandPredicateMatcher(OPM_MBB, InsnVarID, OpIdx) {}
1419
classof(const PredicateMatcher * P)1420 static bool classof(const PredicateMatcher *P) {
1421 return P->getKind() == OPM_MBB;
1422 }
1423
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1424 void emitPredicateOpcodes(MatchTable &Table,
1425 RuleMatcher &Rule) const override {
1426 Table << MatchTable::Opcode("GIM_CheckIsMBB") << MatchTable::Comment("MI")
1427 << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
1428 << MatchTable::IntValue(OpIdx) << MatchTable::LineBreak;
1429 }
1430 };
1431
1432 class ImmOperandMatcher : public OperandPredicateMatcher {
1433 public:
ImmOperandMatcher(unsigned InsnVarID,unsigned OpIdx)1434 ImmOperandMatcher(unsigned InsnVarID, unsigned OpIdx)
1435 : OperandPredicateMatcher(IPM_Imm, InsnVarID, OpIdx) {}
1436
classof(const PredicateMatcher * P)1437 static bool classof(const PredicateMatcher *P) {
1438 return P->getKind() == IPM_Imm;
1439 }
1440
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1441 void emitPredicateOpcodes(MatchTable &Table,
1442 RuleMatcher &Rule) const override {
1443 Table << MatchTable::Opcode("GIM_CheckIsImm") << MatchTable::Comment("MI")
1444 << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
1445 << MatchTable::IntValue(OpIdx) << MatchTable::LineBreak;
1446 }
1447 };
1448
1449 /// Generates code to check that an operand is a G_CONSTANT with a particular
1450 /// int.
1451 class ConstantIntOperandMatcher : public OperandPredicateMatcher {
1452 protected:
1453 int64_t Value;
1454
1455 public:
ConstantIntOperandMatcher(unsigned InsnVarID,unsigned OpIdx,int64_t Value)1456 ConstantIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value)
1457 : OperandPredicateMatcher(OPM_Int, InsnVarID, OpIdx), Value(Value) {}
1458
isIdentical(const PredicateMatcher & B) const1459 bool isIdentical(const PredicateMatcher &B) const override {
1460 return OperandPredicateMatcher::isIdentical(B) &&
1461 Value == cast<ConstantIntOperandMatcher>(&B)->Value;
1462 }
1463
classof(const PredicateMatcher * P)1464 static bool classof(const PredicateMatcher *P) {
1465 return P->getKind() == OPM_Int;
1466 }
1467
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1468 void emitPredicateOpcodes(MatchTable &Table,
1469 RuleMatcher &Rule) const override {
1470 Table << MatchTable::Opcode("GIM_CheckConstantInt")
1471 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1472 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1473 << MatchTable::IntValue(Value) << MatchTable::LineBreak;
1474 }
1475 };
1476
1477 /// Generates code to check that an operand is a raw int (where MO.isImm() or
1478 /// MO.isCImm() is true).
1479 class LiteralIntOperandMatcher : public OperandPredicateMatcher {
1480 protected:
1481 int64_t Value;
1482
1483 public:
LiteralIntOperandMatcher(unsigned InsnVarID,unsigned OpIdx,int64_t Value)1484 LiteralIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value)
1485 : OperandPredicateMatcher(OPM_LiteralInt, InsnVarID, OpIdx),
1486 Value(Value) {}
1487
isIdentical(const PredicateMatcher & B) const1488 bool isIdentical(const PredicateMatcher &B) const override {
1489 return OperandPredicateMatcher::isIdentical(B) &&
1490 Value == cast<LiteralIntOperandMatcher>(&B)->Value;
1491 }
1492
classof(const PredicateMatcher * P)1493 static bool classof(const PredicateMatcher *P) {
1494 return P->getKind() == OPM_LiteralInt;
1495 }
1496
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1497 void emitPredicateOpcodes(MatchTable &Table,
1498 RuleMatcher &Rule) const override {
1499 Table << MatchTable::Opcode("GIM_CheckLiteralInt")
1500 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1501 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1502 << MatchTable::IntValue(Value) << MatchTable::LineBreak;
1503 }
1504 };
1505
1506 /// Generates code to check that an operand is an CmpInst predicate
1507 class CmpPredicateOperandMatcher : public OperandPredicateMatcher {
1508 protected:
1509 std::string PredName;
1510
1511 public:
CmpPredicateOperandMatcher(unsigned InsnVarID,unsigned OpIdx,std::string P)1512 CmpPredicateOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1513 std::string P)
1514 : OperandPredicateMatcher(OPM_CmpPredicate, InsnVarID, OpIdx), PredName(P) {}
1515
isIdentical(const PredicateMatcher & B) const1516 bool isIdentical(const PredicateMatcher &B) const override {
1517 return OperandPredicateMatcher::isIdentical(B) &&
1518 PredName == cast<CmpPredicateOperandMatcher>(&B)->PredName;
1519 }
1520
classof(const PredicateMatcher * P)1521 static bool classof(const PredicateMatcher *P) {
1522 return P->getKind() == OPM_CmpPredicate;
1523 }
1524
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1525 void emitPredicateOpcodes(MatchTable &Table,
1526 RuleMatcher &Rule) const override {
1527 Table << MatchTable::Opcode("GIM_CheckCmpPredicate")
1528 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1529 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1530 << MatchTable::Comment("Predicate")
1531 << MatchTable::NamedValue("CmpInst", PredName)
1532 << MatchTable::LineBreak;
1533 }
1534 };
1535
1536 /// Generates code to check that an operand is an intrinsic ID.
1537 class IntrinsicIDOperandMatcher : public OperandPredicateMatcher {
1538 protected:
1539 const CodeGenIntrinsic *II;
1540
1541 public:
IntrinsicIDOperandMatcher(unsigned InsnVarID,unsigned OpIdx,const CodeGenIntrinsic * II)1542 IntrinsicIDOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1543 const CodeGenIntrinsic *II)
1544 : OperandPredicateMatcher(OPM_IntrinsicID, InsnVarID, OpIdx), II(II) {}
1545
isIdentical(const PredicateMatcher & B) const1546 bool isIdentical(const PredicateMatcher &B) const override {
1547 return OperandPredicateMatcher::isIdentical(B) &&
1548 II == cast<IntrinsicIDOperandMatcher>(&B)->II;
1549 }
1550
classof(const PredicateMatcher * P)1551 static bool classof(const PredicateMatcher *P) {
1552 return P->getKind() == OPM_IntrinsicID;
1553 }
1554
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1555 void emitPredicateOpcodes(MatchTable &Table,
1556 RuleMatcher &Rule) const override {
1557 Table << MatchTable::Opcode("GIM_CheckIntrinsicID")
1558 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1559 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1560 << MatchTable::NamedValue("Intrinsic::" + II->EnumName)
1561 << MatchTable::LineBreak;
1562 }
1563 };
1564
1565 /// Generates code to check that this operand is an immediate whose value meets
1566 /// an immediate predicate.
1567 class OperandImmPredicateMatcher : public OperandPredicateMatcher {
1568 protected:
1569 TreePredicateFn Predicate;
1570
1571 public:
OperandImmPredicateMatcher(unsigned InsnVarID,unsigned OpIdx,const TreePredicateFn & Predicate)1572 OperandImmPredicateMatcher(unsigned InsnVarID, unsigned OpIdx,
1573 const TreePredicateFn &Predicate)
1574 : OperandPredicateMatcher(IPM_ImmPredicate, InsnVarID, OpIdx),
1575 Predicate(Predicate) {}
1576
isIdentical(const PredicateMatcher & B) const1577 bool isIdentical(const PredicateMatcher &B) const override {
1578 return OperandPredicateMatcher::isIdentical(B) &&
1579 Predicate.getOrigPatFragRecord() ==
1580 cast<OperandImmPredicateMatcher>(&B)
1581 ->Predicate.getOrigPatFragRecord();
1582 }
1583
classof(const PredicateMatcher * P)1584 static bool classof(const PredicateMatcher *P) {
1585 return P->getKind() == IPM_ImmPredicate;
1586 }
1587
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1588 void emitPredicateOpcodes(MatchTable &Table,
1589 RuleMatcher &Rule) const override {
1590 Table << MatchTable::Opcode("GIM_CheckImmOperandPredicate")
1591 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1592 << MatchTable::Comment("MO") << MatchTable::IntValue(OpIdx)
1593 << MatchTable::Comment("Predicate")
1594 << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
1595 << MatchTable::LineBreak;
1596 }
1597 };
1598
1599 /// Generates code to check that a set of predicates match for a particular
1600 /// operand.
1601 class OperandMatcher : public PredicateListMatcher<OperandPredicateMatcher> {
1602 protected:
1603 InstructionMatcher &Insn;
1604 unsigned OpIdx;
1605 std::string SymbolicName;
1606
1607 /// The index of the first temporary variable allocated to this operand. The
1608 /// number of allocated temporaries can be found with
1609 /// countRendererFns().
1610 unsigned AllocatedTemporariesBaseID;
1611
1612 public:
OperandMatcher(InstructionMatcher & Insn,unsigned OpIdx,const std::string & SymbolicName,unsigned AllocatedTemporariesBaseID)1613 OperandMatcher(InstructionMatcher &Insn, unsigned OpIdx,
1614 const std::string &SymbolicName,
1615 unsigned AllocatedTemporariesBaseID)
1616 : Insn(Insn), OpIdx(OpIdx), SymbolicName(SymbolicName),
1617 AllocatedTemporariesBaseID(AllocatedTemporariesBaseID) {}
1618
hasSymbolicName() const1619 bool hasSymbolicName() const { return !SymbolicName.empty(); }
getSymbolicName() const1620 StringRef getSymbolicName() const { return SymbolicName; }
setSymbolicName(StringRef Name)1621 void setSymbolicName(StringRef Name) {
1622 assert(SymbolicName.empty() && "Operand already has a symbolic name");
1623 SymbolicName = std::string(Name);
1624 }
1625
1626 /// Construct a new operand predicate and add it to the matcher.
1627 template <class Kind, class... Args>
addPredicate(Args &&...args)1628 Optional<Kind *> addPredicate(Args &&... args) {
1629 if (isSameAsAnotherOperand())
1630 return None;
1631 Predicates.emplace_back(std::make_unique<Kind>(
1632 getInsnVarID(), getOpIdx(), std::forward<Args>(args)...));
1633 return static_cast<Kind *>(Predicates.back().get());
1634 }
1635
getOpIdx() const1636 unsigned getOpIdx() const { return OpIdx; }
1637 unsigned getInsnVarID() const;
1638
getOperandExpr(unsigned InsnVarID) const1639 std::string getOperandExpr(unsigned InsnVarID) const {
1640 return "State.MIs[" + llvm::to_string(InsnVarID) + "]->getOperand(" +
1641 llvm::to_string(OpIdx) + ")";
1642 }
1643
getInstructionMatcher() const1644 InstructionMatcher &getInstructionMatcher() const { return Insn; }
1645
1646 Error addTypeCheckPredicate(const TypeSetByHwMode &VTy,
1647 bool OperandIsAPointer);
1648
1649 /// Emit MatchTable opcodes that test whether the instruction named in
1650 /// InsnVarID matches all the predicates and all the operands.
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule)1651 void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) {
1652 if (!Optimized) {
1653 std::string Comment;
1654 raw_string_ostream CommentOS(Comment);
1655 CommentOS << "MIs[" << getInsnVarID() << "] ";
1656 if (SymbolicName.empty())
1657 CommentOS << "Operand " << OpIdx;
1658 else
1659 CommentOS << SymbolicName;
1660 Table << MatchTable::Comment(CommentOS.str()) << MatchTable::LineBreak;
1661 }
1662
1663 emitPredicateListOpcodes(Table, Rule);
1664 }
1665
1666 /// Compare the priority of this object and B.
1667 ///
1668 /// Returns true if this object is more important than B.
isHigherPriorityThan(OperandMatcher & B)1669 bool isHigherPriorityThan(OperandMatcher &B) {
1670 // Operand matchers involving more predicates have higher priority.
1671 if (predicates_size() > B.predicates_size())
1672 return true;
1673 if (predicates_size() < B.predicates_size())
1674 return false;
1675
1676 // This assumes that predicates are added in a consistent order.
1677 for (auto &&Predicate : zip(predicates(), B.predicates())) {
1678 if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate)))
1679 return true;
1680 if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate)))
1681 return false;
1682 }
1683
1684 return false;
1685 };
1686
1687 /// Report the maximum number of temporary operands needed by the operand
1688 /// matcher.
countRendererFns()1689 unsigned countRendererFns() {
1690 return std::accumulate(
1691 predicates().begin(), predicates().end(), 0,
1692 [](unsigned A,
1693 const std::unique_ptr<OperandPredicateMatcher> &Predicate) {
1694 return A + Predicate->countRendererFns();
1695 });
1696 }
1697
getAllocatedTemporariesBaseID() const1698 unsigned getAllocatedTemporariesBaseID() const {
1699 return AllocatedTemporariesBaseID;
1700 }
1701
isSameAsAnotherOperand()1702 bool isSameAsAnotherOperand() {
1703 for (const auto &Predicate : predicates())
1704 if (isa<SameOperandMatcher>(Predicate))
1705 return true;
1706 return false;
1707 }
1708 };
1709
addTypeCheckPredicate(const TypeSetByHwMode & VTy,bool OperandIsAPointer)1710 Error OperandMatcher::addTypeCheckPredicate(const TypeSetByHwMode &VTy,
1711 bool OperandIsAPointer) {
1712 if (!VTy.isMachineValueType())
1713 return failedImport("unsupported typeset");
1714
1715 if (VTy.getMachineValueType() == MVT::iPTR && OperandIsAPointer) {
1716 addPredicate<PointerToAnyOperandMatcher>(0);
1717 return Error::success();
1718 }
1719
1720 auto OpTyOrNone = MVTToLLT(VTy.getMachineValueType().SimpleTy);
1721 if (!OpTyOrNone)
1722 return failedImport("unsupported type");
1723
1724 if (OperandIsAPointer)
1725 addPredicate<PointerToAnyOperandMatcher>(OpTyOrNone->get().getSizeInBits());
1726 else if (VTy.isPointer())
1727 addPredicate<LLTOperandMatcher>(LLT::pointer(VTy.getPtrAddrSpace(),
1728 OpTyOrNone->get().getSizeInBits()));
1729 else
1730 addPredicate<LLTOperandMatcher>(*OpTyOrNone);
1731 return Error::success();
1732 }
1733
getAllocatedTemporariesBaseID() const1734 unsigned ComplexPatternOperandMatcher::getAllocatedTemporariesBaseID() const {
1735 return Operand.getAllocatedTemporariesBaseID();
1736 }
1737
1738 /// Generates code to check a predicate on an instruction.
1739 ///
1740 /// Typical predicates include:
1741 /// * The opcode of the instruction is a particular value.
1742 /// * The nsw/nuw flag is/isn't set.
1743 class InstructionPredicateMatcher : public PredicateMatcher {
1744 public:
InstructionPredicateMatcher(PredicateKind Kind,unsigned InsnVarID)1745 InstructionPredicateMatcher(PredicateKind Kind, unsigned InsnVarID)
1746 : PredicateMatcher(Kind, InsnVarID) {}
~InstructionPredicateMatcher()1747 virtual ~InstructionPredicateMatcher() {}
1748
1749 /// Compare the priority of this object and B.
1750 ///
1751 /// Returns true if this object is more important than B.
1752 virtual bool
isHigherPriorityThan(const InstructionPredicateMatcher & B) const1753 isHigherPriorityThan(const InstructionPredicateMatcher &B) const {
1754 return Kind < B.Kind;
1755 };
1756 };
1757
1758 template <>
1759 std::string
getNoPredicateComment() const1760 PredicateListMatcher<PredicateMatcher>::getNoPredicateComment() const {
1761 return "No instruction predicates";
1762 }
1763
1764 /// Generates code to check the opcode of an instruction.
1765 class InstructionOpcodeMatcher : public InstructionPredicateMatcher {
1766 protected:
1767 // Allow matching one to several, similar opcodes that share properties. This
1768 // is to handle patterns where one SelectionDAG operation maps to multiple
1769 // GlobalISel ones (e.g. G_BUILD_VECTOR and G_BUILD_VECTOR_TRUNC). The first
1770 // is treated as the canonical opcode.
1771 SmallVector<const CodeGenInstruction *, 2> Insts;
1772
1773 static DenseMap<const CodeGenInstruction *, unsigned> OpcodeValues;
1774
1775
getInstValue(const CodeGenInstruction * I) const1776 MatchTableRecord getInstValue(const CodeGenInstruction *I) const {
1777 const auto VI = OpcodeValues.find(I);
1778 if (VI != OpcodeValues.end())
1779 return MatchTable::NamedValue(I->Namespace, I->TheDef->getName(),
1780 VI->second);
1781 return MatchTable::NamedValue(I->Namespace, I->TheDef->getName());
1782 }
1783
1784 public:
initOpcodeValuesMap(const CodeGenTarget & Target)1785 static void initOpcodeValuesMap(const CodeGenTarget &Target) {
1786 OpcodeValues.clear();
1787
1788 unsigned OpcodeValue = 0;
1789 for (const CodeGenInstruction *I : Target.getInstructionsByEnumValue())
1790 OpcodeValues[I] = OpcodeValue++;
1791 }
1792
InstructionOpcodeMatcher(unsigned InsnVarID,ArrayRef<const CodeGenInstruction * > I)1793 InstructionOpcodeMatcher(unsigned InsnVarID,
1794 ArrayRef<const CodeGenInstruction *> I)
1795 : InstructionPredicateMatcher(IPM_Opcode, InsnVarID),
1796 Insts(I.begin(), I.end()) {
1797 assert((Insts.size() == 1 || Insts.size() == 2) &&
1798 "unexpected number of opcode alternatives");
1799 }
1800
classof(const PredicateMatcher * P)1801 static bool classof(const PredicateMatcher *P) {
1802 return P->getKind() == IPM_Opcode;
1803 }
1804
isIdentical(const PredicateMatcher & B) const1805 bool isIdentical(const PredicateMatcher &B) const override {
1806 return InstructionPredicateMatcher::isIdentical(B) &&
1807 Insts == cast<InstructionOpcodeMatcher>(&B)->Insts;
1808 }
1809
hasValue() const1810 bool hasValue() const override {
1811 return Insts.size() == 1 && OpcodeValues.count(Insts[0]);
1812 }
1813
1814 // TODO: This is used for the SwitchMatcher optimization. We should be able to
1815 // return a list of the opcodes to match.
getValue() const1816 MatchTableRecord getValue() const override {
1817 assert(Insts.size() == 1);
1818
1819 const CodeGenInstruction *I = Insts[0];
1820 const auto VI = OpcodeValues.find(I);
1821 if (VI != OpcodeValues.end())
1822 return MatchTable::NamedValue(I->Namespace, I->TheDef->getName(),
1823 VI->second);
1824 return MatchTable::NamedValue(I->Namespace, I->TheDef->getName());
1825 }
1826
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1827 void emitPredicateOpcodes(MatchTable &Table,
1828 RuleMatcher &Rule) const override {
1829 StringRef CheckType = Insts.size() == 1 ?
1830 "GIM_CheckOpcode" : "GIM_CheckOpcodeIsEither";
1831 Table << MatchTable::Opcode(CheckType) << MatchTable::Comment("MI")
1832 << MatchTable::IntValue(InsnVarID);
1833
1834 for (const CodeGenInstruction *I : Insts)
1835 Table << getInstValue(I);
1836 Table << MatchTable::LineBreak;
1837 }
1838
1839 /// Compare the priority of this object and B.
1840 ///
1841 /// Returns true if this object is more important than B.
1842 bool
isHigherPriorityThan(const InstructionPredicateMatcher & B) const1843 isHigherPriorityThan(const InstructionPredicateMatcher &B) const override {
1844 if (InstructionPredicateMatcher::isHigherPriorityThan(B))
1845 return true;
1846 if (B.InstructionPredicateMatcher::isHigherPriorityThan(*this))
1847 return false;
1848
1849 // Prioritize opcodes for cosmetic reasons in the generated source. Although
1850 // this is cosmetic at the moment, we may want to drive a similar ordering
1851 // using instruction frequency information to improve compile time.
1852 if (const InstructionOpcodeMatcher *BO =
1853 dyn_cast<InstructionOpcodeMatcher>(&B))
1854 return Insts[0]->TheDef->getName() < BO->Insts[0]->TheDef->getName();
1855
1856 return false;
1857 };
1858
isConstantInstruction() const1859 bool isConstantInstruction() const {
1860 return Insts.size() == 1 && Insts[0]->TheDef->getName() == "G_CONSTANT";
1861 }
1862
1863 // The first opcode is the canonical opcode, and later are alternatives.
getOpcode() const1864 StringRef getOpcode() const {
1865 return Insts[0]->TheDef->getName();
1866 }
1867
getAlternativeOpcodes()1868 ArrayRef<const CodeGenInstruction *> getAlternativeOpcodes() {
1869 return Insts;
1870 }
1871
isVariadicNumOperands() const1872 bool isVariadicNumOperands() const {
1873 // If one is variadic, they all should be.
1874 return Insts[0]->Operands.isVariadic;
1875 }
1876
getOperandType(unsigned OpIdx) const1877 StringRef getOperandType(unsigned OpIdx) const {
1878 // Types expected to be uniform for all alternatives.
1879 return Insts[0]->Operands[OpIdx].OperandType;
1880 }
1881 };
1882
1883 DenseMap<const CodeGenInstruction *, unsigned>
1884 InstructionOpcodeMatcher::OpcodeValues;
1885
1886 class InstructionNumOperandsMatcher final : public InstructionPredicateMatcher {
1887 unsigned NumOperands = 0;
1888
1889 public:
InstructionNumOperandsMatcher(unsigned InsnVarID,unsigned NumOperands)1890 InstructionNumOperandsMatcher(unsigned InsnVarID, unsigned NumOperands)
1891 : InstructionPredicateMatcher(IPM_NumOperands, InsnVarID),
1892 NumOperands(NumOperands) {}
1893
classof(const PredicateMatcher * P)1894 static bool classof(const PredicateMatcher *P) {
1895 return P->getKind() == IPM_NumOperands;
1896 }
1897
isIdentical(const PredicateMatcher & B) const1898 bool isIdentical(const PredicateMatcher &B) const override {
1899 return InstructionPredicateMatcher::isIdentical(B) &&
1900 NumOperands == cast<InstructionNumOperandsMatcher>(&B)->NumOperands;
1901 }
1902
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1903 void emitPredicateOpcodes(MatchTable &Table,
1904 RuleMatcher &Rule) const override {
1905 Table << MatchTable::Opcode("GIM_CheckNumOperands")
1906 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1907 << MatchTable::Comment("Expected")
1908 << MatchTable::IntValue(NumOperands) << MatchTable::LineBreak;
1909 }
1910 };
1911
1912 /// Generates code to check that this instruction is a constant whose value
1913 /// meets an immediate predicate.
1914 ///
1915 /// Immediates are slightly odd since they are typically used like an operand
1916 /// but are represented as an operator internally. We typically write simm8:$src
1917 /// in a tablegen pattern, but this is just syntactic sugar for
1918 /// (imm:i32)<<P:Predicate_simm8>>:$imm which more directly describes the nodes
1919 /// that will be matched and the predicate (which is attached to the imm
1920 /// operator) that will be tested. In SelectionDAG this describes a
1921 /// ConstantSDNode whose internal value will be tested using the simm8 predicate.
1922 ///
1923 /// The corresponding GlobalISel representation is %1 = G_CONSTANT iN Value. In
1924 /// this representation, the immediate could be tested with an
1925 /// InstructionMatcher, InstructionOpcodeMatcher, OperandMatcher, and a
1926 /// OperandPredicateMatcher-subclass to check the Value meets the predicate but
1927 /// there are two implementation issues with producing that matcher
1928 /// configuration from the SelectionDAG pattern:
1929 /// * ImmLeaf is a PatFrag whose root is an InstructionMatcher. This means that
1930 /// were we to sink the immediate predicate to the operand we would have to
1931 /// have two partial implementations of PatFrag support, one for immediates
1932 /// and one for non-immediates.
1933 /// * At the point we handle the predicate, the OperandMatcher hasn't been
1934 /// created yet. If we were to sink the predicate to the OperandMatcher we
1935 /// would also have to complicate (or duplicate) the code that descends and
1936 /// creates matchers for the subtree.
1937 /// Overall, it's simpler to handle it in the place it was found.
1938 class InstructionImmPredicateMatcher : public InstructionPredicateMatcher {
1939 protected:
1940 TreePredicateFn Predicate;
1941
1942 public:
InstructionImmPredicateMatcher(unsigned InsnVarID,const TreePredicateFn & Predicate)1943 InstructionImmPredicateMatcher(unsigned InsnVarID,
1944 const TreePredicateFn &Predicate)
1945 : InstructionPredicateMatcher(IPM_ImmPredicate, InsnVarID),
1946 Predicate(Predicate) {}
1947
isIdentical(const PredicateMatcher & B) const1948 bool isIdentical(const PredicateMatcher &B) const override {
1949 return InstructionPredicateMatcher::isIdentical(B) &&
1950 Predicate.getOrigPatFragRecord() ==
1951 cast<InstructionImmPredicateMatcher>(&B)
1952 ->Predicate.getOrigPatFragRecord();
1953 }
1954
classof(const PredicateMatcher * P)1955 static bool classof(const PredicateMatcher *P) {
1956 return P->getKind() == IPM_ImmPredicate;
1957 }
1958
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1959 void emitPredicateOpcodes(MatchTable &Table,
1960 RuleMatcher &Rule) const override {
1961 Table << MatchTable::Opcode(getMatchOpcodeForImmPredicate(Predicate))
1962 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1963 << MatchTable::Comment("Predicate")
1964 << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
1965 << MatchTable::LineBreak;
1966 }
1967 };
1968
1969 /// Generates code to check that a memory instruction has a atomic ordering
1970 /// MachineMemoryOperand.
1971 class AtomicOrderingMMOPredicateMatcher : public InstructionPredicateMatcher {
1972 public:
1973 enum AOComparator {
1974 AO_Exactly,
1975 AO_OrStronger,
1976 AO_WeakerThan,
1977 };
1978
1979 protected:
1980 StringRef Order;
1981 AOComparator Comparator;
1982
1983 public:
AtomicOrderingMMOPredicateMatcher(unsigned InsnVarID,StringRef Order,AOComparator Comparator=AO_Exactly)1984 AtomicOrderingMMOPredicateMatcher(unsigned InsnVarID, StringRef Order,
1985 AOComparator Comparator = AO_Exactly)
1986 : InstructionPredicateMatcher(IPM_AtomicOrderingMMO, InsnVarID),
1987 Order(Order), Comparator(Comparator) {}
1988
classof(const PredicateMatcher * P)1989 static bool classof(const PredicateMatcher *P) {
1990 return P->getKind() == IPM_AtomicOrderingMMO;
1991 }
1992
isIdentical(const PredicateMatcher & B) const1993 bool isIdentical(const PredicateMatcher &B) const override {
1994 if (!InstructionPredicateMatcher::isIdentical(B))
1995 return false;
1996 const auto &R = *cast<AtomicOrderingMMOPredicateMatcher>(&B);
1997 return Order == R.Order && Comparator == R.Comparator;
1998 }
1999
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const2000 void emitPredicateOpcodes(MatchTable &Table,
2001 RuleMatcher &Rule) const override {
2002 StringRef Opcode = "GIM_CheckAtomicOrdering";
2003
2004 if (Comparator == AO_OrStronger)
2005 Opcode = "GIM_CheckAtomicOrderingOrStrongerThan";
2006 if (Comparator == AO_WeakerThan)
2007 Opcode = "GIM_CheckAtomicOrderingWeakerThan";
2008
2009 Table << MatchTable::Opcode(Opcode) << MatchTable::Comment("MI")
2010 << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Order")
2011 << MatchTable::NamedValue(("(int64_t)AtomicOrdering::" + Order).str())
2012 << MatchTable::LineBreak;
2013 }
2014 };
2015
2016 /// Generates code to check that the size of an MMO is exactly N bytes.
2017 class MemorySizePredicateMatcher : public InstructionPredicateMatcher {
2018 protected:
2019 unsigned MMOIdx;
2020 uint64_t Size;
2021
2022 public:
MemorySizePredicateMatcher(unsigned InsnVarID,unsigned MMOIdx,unsigned Size)2023 MemorySizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, unsigned Size)
2024 : InstructionPredicateMatcher(IPM_MemoryLLTSize, InsnVarID),
2025 MMOIdx(MMOIdx), Size(Size) {}
2026
classof(const PredicateMatcher * P)2027 static bool classof(const PredicateMatcher *P) {
2028 return P->getKind() == IPM_MemoryLLTSize;
2029 }
isIdentical(const PredicateMatcher & B) const2030 bool isIdentical(const PredicateMatcher &B) const override {
2031 return InstructionPredicateMatcher::isIdentical(B) &&
2032 MMOIdx == cast<MemorySizePredicateMatcher>(&B)->MMOIdx &&
2033 Size == cast<MemorySizePredicateMatcher>(&B)->Size;
2034 }
2035
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const2036 void emitPredicateOpcodes(MatchTable &Table,
2037 RuleMatcher &Rule) const override {
2038 Table << MatchTable::Opcode("GIM_CheckMemorySizeEqualTo")
2039 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
2040 << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
2041 << MatchTable::Comment("Size") << MatchTable::IntValue(Size)
2042 << MatchTable::LineBreak;
2043 }
2044 };
2045
2046 class MemoryAddressSpacePredicateMatcher : public InstructionPredicateMatcher {
2047 protected:
2048 unsigned MMOIdx;
2049 SmallVector<unsigned, 4> AddrSpaces;
2050
2051 public:
MemoryAddressSpacePredicateMatcher(unsigned InsnVarID,unsigned MMOIdx,ArrayRef<unsigned> AddrSpaces)2052 MemoryAddressSpacePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
2053 ArrayRef<unsigned> AddrSpaces)
2054 : InstructionPredicateMatcher(IPM_MemoryAddressSpace, InsnVarID),
2055 MMOIdx(MMOIdx), AddrSpaces(AddrSpaces.begin(), AddrSpaces.end()) {}
2056
classof(const PredicateMatcher * P)2057 static bool classof(const PredicateMatcher *P) {
2058 return P->getKind() == IPM_MemoryAddressSpace;
2059 }
isIdentical(const PredicateMatcher & B) const2060 bool isIdentical(const PredicateMatcher &B) const override {
2061 if (!InstructionPredicateMatcher::isIdentical(B))
2062 return false;
2063 auto *Other = cast<MemoryAddressSpacePredicateMatcher>(&B);
2064 return MMOIdx == Other->MMOIdx && AddrSpaces == Other->AddrSpaces;
2065 }
2066
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const2067 void emitPredicateOpcodes(MatchTable &Table,
2068 RuleMatcher &Rule) const override {
2069 Table << MatchTable::Opcode("GIM_CheckMemoryAddressSpace")
2070 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
2071 << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
2072 // Encode number of address spaces to expect.
2073 << MatchTable::Comment("NumAddrSpace")
2074 << MatchTable::IntValue(AddrSpaces.size());
2075 for (unsigned AS : AddrSpaces)
2076 Table << MatchTable::Comment("AddrSpace") << MatchTable::IntValue(AS);
2077
2078 Table << MatchTable::LineBreak;
2079 }
2080 };
2081
2082 class MemoryAlignmentPredicateMatcher : public InstructionPredicateMatcher {
2083 protected:
2084 unsigned MMOIdx;
2085 int MinAlign;
2086
2087 public:
MemoryAlignmentPredicateMatcher(unsigned InsnVarID,unsigned MMOIdx,int MinAlign)2088 MemoryAlignmentPredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
2089 int MinAlign)
2090 : InstructionPredicateMatcher(IPM_MemoryAlignment, InsnVarID),
2091 MMOIdx(MMOIdx), MinAlign(MinAlign) {
2092 assert(MinAlign > 0);
2093 }
2094
classof(const PredicateMatcher * P)2095 static bool classof(const PredicateMatcher *P) {
2096 return P->getKind() == IPM_MemoryAlignment;
2097 }
2098
isIdentical(const PredicateMatcher & B) const2099 bool isIdentical(const PredicateMatcher &B) const override {
2100 if (!InstructionPredicateMatcher::isIdentical(B))
2101 return false;
2102 auto *Other = cast<MemoryAlignmentPredicateMatcher>(&B);
2103 return MMOIdx == Other->MMOIdx && MinAlign == Other->MinAlign;
2104 }
2105
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const2106 void emitPredicateOpcodes(MatchTable &Table,
2107 RuleMatcher &Rule) const override {
2108 Table << MatchTable::Opcode("GIM_CheckMemoryAlignment")
2109 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
2110 << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
2111 << MatchTable::Comment("MinAlign") << MatchTable::IntValue(MinAlign)
2112 << MatchTable::LineBreak;
2113 }
2114 };
2115
2116 /// Generates code to check that the size of an MMO is less-than, equal-to, or
2117 /// greater than a given LLT.
2118 class MemoryVsLLTSizePredicateMatcher : public InstructionPredicateMatcher {
2119 public:
2120 enum RelationKind {
2121 GreaterThan,
2122 EqualTo,
2123 LessThan,
2124 };
2125
2126 protected:
2127 unsigned MMOIdx;
2128 RelationKind Relation;
2129 unsigned OpIdx;
2130
2131 public:
MemoryVsLLTSizePredicateMatcher(unsigned InsnVarID,unsigned MMOIdx,enum RelationKind Relation,unsigned OpIdx)2132 MemoryVsLLTSizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
2133 enum RelationKind Relation,
2134 unsigned OpIdx)
2135 : InstructionPredicateMatcher(IPM_MemoryVsLLTSize, InsnVarID),
2136 MMOIdx(MMOIdx), Relation(Relation), OpIdx(OpIdx) {}
2137
classof(const PredicateMatcher * P)2138 static bool classof(const PredicateMatcher *P) {
2139 return P->getKind() == IPM_MemoryVsLLTSize;
2140 }
isIdentical(const PredicateMatcher & B) const2141 bool isIdentical(const PredicateMatcher &B) const override {
2142 return InstructionPredicateMatcher::isIdentical(B) &&
2143 MMOIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->MMOIdx &&
2144 Relation == cast<MemoryVsLLTSizePredicateMatcher>(&B)->Relation &&
2145 OpIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->OpIdx;
2146 }
2147
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const2148 void emitPredicateOpcodes(MatchTable &Table,
2149 RuleMatcher &Rule) const override {
2150 Table << MatchTable::Opcode(Relation == EqualTo
2151 ? "GIM_CheckMemorySizeEqualToLLT"
2152 : Relation == GreaterThan
2153 ? "GIM_CheckMemorySizeGreaterThanLLT"
2154 : "GIM_CheckMemorySizeLessThanLLT")
2155 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
2156 << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
2157 << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx)
2158 << MatchTable::LineBreak;
2159 }
2160 };
2161
2162 // Matcher for immAllOnesV/immAllZerosV
2163 class VectorSplatImmPredicateMatcher : public InstructionPredicateMatcher {
2164 public:
2165 enum SplatKind {
2166 AllZeros,
2167 AllOnes
2168 };
2169
2170 private:
2171 SplatKind Kind;
2172
2173 public:
VectorSplatImmPredicateMatcher(unsigned InsnVarID,SplatKind K)2174 VectorSplatImmPredicateMatcher(unsigned InsnVarID, SplatKind K)
2175 : InstructionPredicateMatcher(IPM_VectorSplatImm, InsnVarID), Kind(K) {}
2176
classof(const PredicateMatcher * P)2177 static bool classof(const PredicateMatcher *P) {
2178 return P->getKind() == IPM_VectorSplatImm;
2179 }
2180
isIdentical(const PredicateMatcher & B) const2181 bool isIdentical(const PredicateMatcher &B) const override {
2182 return InstructionPredicateMatcher::isIdentical(B) &&
2183 Kind == static_cast<const VectorSplatImmPredicateMatcher &>(B).Kind;
2184 }
2185
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const2186 void emitPredicateOpcodes(MatchTable &Table,
2187 RuleMatcher &Rule) const override {
2188 if (Kind == AllOnes)
2189 Table << MatchTable::Opcode("GIM_CheckIsBuildVectorAllOnes");
2190 else
2191 Table << MatchTable::Opcode("GIM_CheckIsBuildVectorAllZeros");
2192
2193 Table << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID);
2194 Table << MatchTable::LineBreak;
2195 }
2196 };
2197
2198 /// Generates code to check an arbitrary C++ instruction predicate.
2199 class GenericInstructionPredicateMatcher : public InstructionPredicateMatcher {
2200 protected:
2201 TreePredicateFn Predicate;
2202
2203 public:
GenericInstructionPredicateMatcher(unsigned InsnVarID,TreePredicateFn Predicate)2204 GenericInstructionPredicateMatcher(unsigned InsnVarID,
2205 TreePredicateFn Predicate)
2206 : InstructionPredicateMatcher(IPM_GenericPredicate, InsnVarID),
2207 Predicate(Predicate) {}
2208
classof(const InstructionPredicateMatcher * P)2209 static bool classof(const InstructionPredicateMatcher *P) {
2210 return P->getKind() == IPM_GenericPredicate;
2211 }
isIdentical(const PredicateMatcher & B) const2212 bool isIdentical(const PredicateMatcher &B) const override {
2213 return InstructionPredicateMatcher::isIdentical(B) &&
2214 Predicate ==
2215 static_cast<const GenericInstructionPredicateMatcher &>(B)
2216 .Predicate;
2217 }
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const2218 void emitPredicateOpcodes(MatchTable &Table,
2219 RuleMatcher &Rule) const override {
2220 Table << MatchTable::Opcode("GIM_CheckCxxInsnPredicate")
2221 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
2222 << MatchTable::Comment("FnId")
2223 << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
2224 << MatchTable::LineBreak;
2225 }
2226 };
2227
2228 /// Generates code to check that a set of predicates and operands match for a
2229 /// particular instruction.
2230 ///
2231 /// Typical predicates include:
2232 /// * Has a specific opcode.
2233 /// * Has an nsw/nuw flag or doesn't.
2234 class InstructionMatcher final : public PredicateListMatcher<PredicateMatcher> {
2235 protected:
2236 typedef std::vector<std::unique_ptr<OperandMatcher>> OperandVec;
2237
2238 RuleMatcher &Rule;
2239
2240 /// The operands to match. All rendered operands must be present even if the
2241 /// condition is always true.
2242 OperandVec Operands;
2243 bool NumOperandsCheck = true;
2244
2245 std::string SymbolicName;
2246 unsigned InsnVarID;
2247
2248 /// PhysRegInputs - List list has an entry for each explicitly specified
2249 /// physreg input to the pattern. The first elt is the Register node, the
2250 /// second is the recorded slot number the input pattern match saved it in.
2251 SmallVector<std::pair<Record *, unsigned>, 2> PhysRegInputs;
2252
2253 public:
InstructionMatcher(RuleMatcher & Rule,StringRef SymbolicName,bool NumOpsCheck=true)2254 InstructionMatcher(RuleMatcher &Rule, StringRef SymbolicName,
2255 bool NumOpsCheck = true)
2256 : Rule(Rule), NumOperandsCheck(NumOpsCheck), SymbolicName(SymbolicName) {
2257 // We create a new instruction matcher.
2258 // Get a new ID for that instruction.
2259 InsnVarID = Rule.implicitlyDefineInsnVar(*this);
2260 }
2261
2262 /// Construct a new instruction predicate and add it to the matcher.
2263 template <class Kind, class... Args>
addPredicate(Args &&...args)2264 Optional<Kind *> addPredicate(Args &&... args) {
2265 Predicates.emplace_back(
2266 std::make_unique<Kind>(getInsnVarID(), std::forward<Args>(args)...));
2267 return static_cast<Kind *>(Predicates.back().get());
2268 }
2269
getRuleMatcher() const2270 RuleMatcher &getRuleMatcher() const { return Rule; }
2271
getInsnVarID() const2272 unsigned getInsnVarID() const { return InsnVarID; }
2273
2274 /// Add an operand to the matcher.
addOperand(unsigned OpIdx,const std::string & SymbolicName,unsigned AllocatedTemporariesBaseID)2275 OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName,
2276 unsigned AllocatedTemporariesBaseID) {
2277 Operands.emplace_back(new OperandMatcher(*this, OpIdx, SymbolicName,
2278 AllocatedTemporariesBaseID));
2279 if (!SymbolicName.empty())
2280 Rule.defineOperand(SymbolicName, *Operands.back());
2281
2282 return *Operands.back();
2283 }
2284
getOperand(unsigned OpIdx)2285 OperandMatcher &getOperand(unsigned OpIdx) {
2286 auto I = llvm::find_if(Operands,
2287 [&OpIdx](const std::unique_ptr<OperandMatcher> &X) {
2288 return X->getOpIdx() == OpIdx;
2289 });
2290 if (I != Operands.end())
2291 return **I;
2292 llvm_unreachable("Failed to lookup operand");
2293 }
2294
addPhysRegInput(Record * Reg,unsigned OpIdx,unsigned TempOpIdx)2295 OperandMatcher &addPhysRegInput(Record *Reg, unsigned OpIdx,
2296 unsigned TempOpIdx) {
2297 assert(SymbolicName.empty());
2298 OperandMatcher *OM = new OperandMatcher(*this, OpIdx, "", TempOpIdx);
2299 Operands.emplace_back(OM);
2300 Rule.definePhysRegOperand(Reg, *OM);
2301 PhysRegInputs.emplace_back(Reg, OpIdx);
2302 return *OM;
2303 }
2304
getPhysRegInputs() const2305 ArrayRef<std::pair<Record *, unsigned>> getPhysRegInputs() const {
2306 return PhysRegInputs;
2307 }
2308
getSymbolicName() const2309 StringRef getSymbolicName() const { return SymbolicName; }
getNumOperands() const2310 unsigned getNumOperands() const { return Operands.size(); }
operands_begin()2311 OperandVec::iterator operands_begin() { return Operands.begin(); }
operands_end()2312 OperandVec::iterator operands_end() { return Operands.end(); }
operands()2313 iterator_range<OperandVec::iterator> operands() {
2314 return make_range(operands_begin(), operands_end());
2315 }
operands_begin() const2316 OperandVec::const_iterator operands_begin() const { return Operands.begin(); }
operands_end() const2317 OperandVec::const_iterator operands_end() const { return Operands.end(); }
operands() const2318 iterator_range<OperandVec::const_iterator> operands() const {
2319 return make_range(operands_begin(), operands_end());
2320 }
operands_empty() const2321 bool operands_empty() const { return Operands.empty(); }
2322
pop_front()2323 void pop_front() { Operands.erase(Operands.begin()); }
2324
2325 void optimize();
2326
2327 /// Emit MatchTable opcodes that test whether the instruction named in
2328 /// InsnVarName matches all the predicates and all the operands.
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule)2329 void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) {
2330 if (NumOperandsCheck)
2331 InstructionNumOperandsMatcher(InsnVarID, getNumOperands())
2332 .emitPredicateOpcodes(Table, Rule);
2333
2334 // First emit all instruction level predicates need to be verified before we
2335 // can verify operands.
2336 emitFilteredPredicateListOpcodes(
2337 [](const PredicateMatcher &P) {
2338 return !P.dependsOnOperands();
2339 }, Table, Rule);
2340
2341 // Emit all operand constraints.
2342 for (const auto &Operand : Operands)
2343 Operand->emitPredicateOpcodes(Table, Rule);
2344
2345 // All of the tablegen defined predicates should now be matched. Now emit
2346 // any custom predicates that rely on all generated checks.
2347 emitFilteredPredicateListOpcodes(
2348 [](const PredicateMatcher &P) {
2349 return P.dependsOnOperands();
2350 }, Table, Rule);
2351 }
2352
2353 /// Compare the priority of this object and B.
2354 ///
2355 /// Returns true if this object is more important than B.
isHigherPriorityThan(InstructionMatcher & B)2356 bool isHigherPriorityThan(InstructionMatcher &B) {
2357 // Instruction matchers involving more operands have higher priority.
2358 if (Operands.size() > B.Operands.size())
2359 return true;
2360 if (Operands.size() < B.Operands.size())
2361 return false;
2362
2363 for (auto &&P : zip(predicates(), B.predicates())) {
2364 auto L = static_cast<InstructionPredicateMatcher *>(std::get<0>(P).get());
2365 auto R = static_cast<InstructionPredicateMatcher *>(std::get<1>(P).get());
2366 if (L->isHigherPriorityThan(*R))
2367 return true;
2368 if (R->isHigherPriorityThan(*L))
2369 return false;
2370 }
2371
2372 for (auto Operand : zip(Operands, B.Operands)) {
2373 if (std::get<0>(Operand)->isHigherPriorityThan(*std::get<1>(Operand)))
2374 return true;
2375 if (std::get<1>(Operand)->isHigherPriorityThan(*std::get<0>(Operand)))
2376 return false;
2377 }
2378
2379 return false;
2380 };
2381
2382 /// Report the maximum number of temporary operands needed by the instruction
2383 /// matcher.
countRendererFns()2384 unsigned countRendererFns() {
2385 return std::accumulate(
2386 predicates().begin(), predicates().end(), 0,
2387 [](unsigned A,
2388 const std::unique_ptr<PredicateMatcher> &Predicate) {
2389 return A + Predicate->countRendererFns();
2390 }) +
2391 std::accumulate(
2392 Operands.begin(), Operands.end(), 0,
2393 [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) {
2394 return A + Operand->countRendererFns();
2395 });
2396 }
2397
getOpcodeMatcher()2398 InstructionOpcodeMatcher &getOpcodeMatcher() {
2399 for (auto &P : predicates())
2400 if (auto *OpMatcher = dyn_cast<InstructionOpcodeMatcher>(P.get()))
2401 return *OpMatcher;
2402 llvm_unreachable("Didn't find an opcode matcher");
2403 }
2404
isConstantInstruction()2405 bool isConstantInstruction() {
2406 return getOpcodeMatcher().isConstantInstruction();
2407 }
2408
getOpcode()2409 StringRef getOpcode() { return getOpcodeMatcher().getOpcode(); }
2410 };
2411
getOpcode() const2412 StringRef RuleMatcher::getOpcode() const {
2413 return Matchers.front()->getOpcode();
2414 }
2415
getNumOperands() const2416 unsigned RuleMatcher::getNumOperands() const {
2417 return Matchers.front()->getNumOperands();
2418 }
2419
getFirstConditionAsRootType()2420 LLTCodeGen RuleMatcher::getFirstConditionAsRootType() {
2421 InstructionMatcher &InsnMatcher = *Matchers.front();
2422 if (!InsnMatcher.predicates_empty())
2423 if (const auto *TM =
2424 dyn_cast<LLTOperandMatcher>(&**InsnMatcher.predicates_begin()))
2425 if (TM->getInsnVarID() == 0 && TM->getOpIdx() == 0)
2426 return TM->getTy();
2427 return {};
2428 }
2429
2430 /// Generates code to check that the operand is a register defined by an
2431 /// instruction that matches the given instruction matcher.
2432 ///
2433 /// For example, the pattern:
2434 /// (set $dst, (G_MUL (G_ADD $src1, $src2), $src3))
2435 /// would use an InstructionOperandMatcher for operand 1 of the G_MUL to match
2436 /// the:
2437 /// (G_ADD $src1, $src2)
2438 /// subpattern.
2439 class InstructionOperandMatcher : public OperandPredicateMatcher {
2440 protected:
2441 std::unique_ptr<InstructionMatcher> InsnMatcher;
2442
2443 public:
InstructionOperandMatcher(unsigned InsnVarID,unsigned OpIdx,RuleMatcher & Rule,StringRef SymbolicName,bool NumOpsCheck=true)2444 InstructionOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
2445 RuleMatcher &Rule, StringRef SymbolicName,
2446 bool NumOpsCheck = true)
2447 : OperandPredicateMatcher(OPM_Instruction, InsnVarID, OpIdx),
2448 InsnMatcher(new InstructionMatcher(Rule, SymbolicName, NumOpsCheck)) {}
2449
classof(const PredicateMatcher * P)2450 static bool classof(const PredicateMatcher *P) {
2451 return P->getKind() == OPM_Instruction;
2452 }
2453
getInsnMatcher() const2454 InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; }
2455
emitCaptureOpcodes(MatchTable & Table,RuleMatcher & Rule) const2456 void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const {
2457 const unsigned NewInsnVarID = InsnMatcher->getInsnVarID();
2458 Table << MatchTable::Opcode("GIM_RecordInsn")
2459 << MatchTable::Comment("DefineMI")
2460 << MatchTable::IntValue(NewInsnVarID) << MatchTable::Comment("MI")
2461 << MatchTable::IntValue(getInsnVarID())
2462 << MatchTable::Comment("OpIdx") << MatchTable::IntValue(getOpIdx())
2463 << MatchTable::Comment("MIs[" + llvm::to_string(NewInsnVarID) + "]")
2464 << MatchTable::LineBreak;
2465 }
2466
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const2467 void emitPredicateOpcodes(MatchTable &Table,
2468 RuleMatcher &Rule) const override {
2469 emitCaptureOpcodes(Table, Rule);
2470 InsnMatcher->emitPredicateOpcodes(Table, Rule);
2471 }
2472
isHigherPriorityThan(const OperandPredicateMatcher & B) const2473 bool isHigherPriorityThan(const OperandPredicateMatcher &B) const override {
2474 if (OperandPredicateMatcher::isHigherPriorityThan(B))
2475 return true;
2476 if (B.OperandPredicateMatcher::isHigherPriorityThan(*this))
2477 return false;
2478
2479 if (const InstructionOperandMatcher *BP =
2480 dyn_cast<InstructionOperandMatcher>(&B))
2481 if (InsnMatcher->isHigherPriorityThan(*BP->InsnMatcher))
2482 return true;
2483 return false;
2484 }
2485 };
2486
optimize()2487 void InstructionMatcher::optimize() {
2488 SmallVector<std::unique_ptr<PredicateMatcher>, 8> Stash;
2489 const auto &OpcMatcher = getOpcodeMatcher();
2490
2491 Stash.push_back(predicates_pop_front());
2492 if (Stash.back().get() == &OpcMatcher) {
2493 if (NumOperandsCheck && OpcMatcher.isVariadicNumOperands())
2494 Stash.emplace_back(
2495 new InstructionNumOperandsMatcher(InsnVarID, getNumOperands()));
2496 NumOperandsCheck = false;
2497
2498 for (auto &OM : Operands)
2499 for (auto &OP : OM->predicates())
2500 if (isa<IntrinsicIDOperandMatcher>(OP)) {
2501 Stash.push_back(std::move(OP));
2502 OM->eraseNullPredicates();
2503 break;
2504 }
2505 }
2506
2507 if (InsnVarID > 0) {
2508 assert(!Operands.empty() && "Nested instruction is expected to def a vreg");
2509 for (auto &OP : Operands[0]->predicates())
2510 OP.reset();
2511 Operands[0]->eraseNullPredicates();
2512 }
2513 for (auto &OM : Operands) {
2514 for (auto &OP : OM->predicates())
2515 if (isa<LLTOperandMatcher>(OP))
2516 Stash.push_back(std::move(OP));
2517 OM->eraseNullPredicates();
2518 }
2519 while (!Stash.empty())
2520 prependPredicate(Stash.pop_back_val());
2521 }
2522
2523 //===- Actions ------------------------------------------------------------===//
2524 class OperandRenderer {
2525 public:
2526 enum RendererKind {
2527 OR_Copy,
2528 OR_CopyOrAddZeroReg,
2529 OR_CopySubReg,
2530 OR_CopyPhysReg,
2531 OR_CopyConstantAsImm,
2532 OR_CopyFConstantAsFPImm,
2533 OR_Imm,
2534 OR_SubRegIndex,
2535 OR_Register,
2536 OR_TempRegister,
2537 OR_ComplexPattern,
2538 OR_Custom,
2539 OR_CustomOperand
2540 };
2541
2542 protected:
2543 RendererKind Kind;
2544
2545 public:
OperandRenderer(RendererKind Kind)2546 OperandRenderer(RendererKind Kind) : Kind(Kind) {}
~OperandRenderer()2547 virtual ~OperandRenderer() {}
2548
getKind() const2549 RendererKind getKind() const { return Kind; }
2550
2551 virtual void emitRenderOpcodes(MatchTable &Table,
2552 RuleMatcher &Rule) const = 0;
2553 };
2554
2555 /// A CopyRenderer emits code to copy a single operand from an existing
2556 /// instruction to the one being built.
2557 class CopyRenderer : public OperandRenderer {
2558 protected:
2559 unsigned NewInsnID;
2560 /// The name of the operand.
2561 const StringRef SymbolicName;
2562
2563 public:
CopyRenderer(unsigned NewInsnID,StringRef SymbolicName)2564 CopyRenderer(unsigned NewInsnID, StringRef SymbolicName)
2565 : OperandRenderer(OR_Copy), NewInsnID(NewInsnID),
2566 SymbolicName(SymbolicName) {
2567 assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
2568 }
2569
classof(const OperandRenderer * R)2570 static bool classof(const OperandRenderer *R) {
2571 return R->getKind() == OR_Copy;
2572 }
2573
getSymbolicName() const2574 StringRef getSymbolicName() const { return SymbolicName; }
2575
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2576 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2577 const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2578 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2579 Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
2580 << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID")
2581 << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2582 << MatchTable::IntValue(Operand.getOpIdx())
2583 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2584 }
2585 };
2586
2587 /// A CopyRenderer emits code to copy a virtual register to a specific physical
2588 /// register.
2589 class CopyPhysRegRenderer : public OperandRenderer {
2590 protected:
2591 unsigned NewInsnID;
2592 Record *PhysReg;
2593
2594 public:
CopyPhysRegRenderer(unsigned NewInsnID,Record * Reg)2595 CopyPhysRegRenderer(unsigned NewInsnID, Record *Reg)
2596 : OperandRenderer(OR_CopyPhysReg), NewInsnID(NewInsnID),
2597 PhysReg(Reg) {
2598 assert(PhysReg);
2599 }
2600
classof(const OperandRenderer * R)2601 static bool classof(const OperandRenderer *R) {
2602 return R->getKind() == OR_CopyPhysReg;
2603 }
2604
getPhysReg() const2605 Record *getPhysReg() const { return PhysReg; }
2606
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2607 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2608 const OperandMatcher &Operand = Rule.getPhysRegOperandMatcher(PhysReg);
2609 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2610 Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
2611 << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID")
2612 << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2613 << MatchTable::IntValue(Operand.getOpIdx())
2614 << MatchTable::Comment(PhysReg->getName())
2615 << MatchTable::LineBreak;
2616 }
2617 };
2618
2619 /// A CopyOrAddZeroRegRenderer emits code to copy a single operand from an
2620 /// existing instruction to the one being built. If the operand turns out to be
2621 /// a 'G_CONSTANT 0' then it replaces the operand with a zero register.
2622 class CopyOrAddZeroRegRenderer : public OperandRenderer {
2623 protected:
2624 unsigned NewInsnID;
2625 /// The name of the operand.
2626 const StringRef SymbolicName;
2627 const Record *ZeroRegisterDef;
2628
2629 public:
CopyOrAddZeroRegRenderer(unsigned NewInsnID,StringRef SymbolicName,Record * ZeroRegisterDef)2630 CopyOrAddZeroRegRenderer(unsigned NewInsnID,
2631 StringRef SymbolicName, Record *ZeroRegisterDef)
2632 : OperandRenderer(OR_CopyOrAddZeroReg), NewInsnID(NewInsnID),
2633 SymbolicName(SymbolicName), ZeroRegisterDef(ZeroRegisterDef) {
2634 assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
2635 }
2636
classof(const OperandRenderer * R)2637 static bool classof(const OperandRenderer *R) {
2638 return R->getKind() == OR_CopyOrAddZeroReg;
2639 }
2640
getSymbolicName() const2641 StringRef getSymbolicName() const { return SymbolicName; }
2642
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2643 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2644 const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2645 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2646 Table << MatchTable::Opcode("GIR_CopyOrAddZeroReg")
2647 << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2648 << MatchTable::Comment("OldInsnID")
2649 << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2650 << MatchTable::IntValue(Operand.getOpIdx())
2651 << MatchTable::NamedValue(
2652 (ZeroRegisterDef->getValue("Namespace")
2653 ? ZeroRegisterDef->getValueAsString("Namespace")
2654 : ""),
2655 ZeroRegisterDef->getName())
2656 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2657 }
2658 };
2659
2660 /// A CopyConstantAsImmRenderer emits code to render a G_CONSTANT instruction to
2661 /// an extended immediate operand.
2662 class CopyConstantAsImmRenderer : public OperandRenderer {
2663 protected:
2664 unsigned NewInsnID;
2665 /// The name of the operand.
2666 const std::string SymbolicName;
2667 bool Signed;
2668
2669 public:
CopyConstantAsImmRenderer(unsigned NewInsnID,StringRef SymbolicName)2670 CopyConstantAsImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
2671 : OperandRenderer(OR_CopyConstantAsImm), NewInsnID(NewInsnID),
2672 SymbolicName(SymbolicName), Signed(true) {}
2673
classof(const OperandRenderer * R)2674 static bool classof(const OperandRenderer *R) {
2675 return R->getKind() == OR_CopyConstantAsImm;
2676 }
2677
getSymbolicName() const2678 StringRef getSymbolicName() const { return SymbolicName; }
2679
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2680 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2681 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2682 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2683 Table << MatchTable::Opcode(Signed ? "GIR_CopyConstantAsSImm"
2684 : "GIR_CopyConstantAsUImm")
2685 << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2686 << MatchTable::Comment("OldInsnID")
2687 << MatchTable::IntValue(OldInsnVarID)
2688 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2689 }
2690 };
2691
2692 /// A CopyFConstantAsFPImmRenderer emits code to render a G_FCONSTANT
2693 /// instruction to an extended immediate operand.
2694 class CopyFConstantAsFPImmRenderer : public OperandRenderer {
2695 protected:
2696 unsigned NewInsnID;
2697 /// The name of the operand.
2698 const std::string SymbolicName;
2699
2700 public:
CopyFConstantAsFPImmRenderer(unsigned NewInsnID,StringRef SymbolicName)2701 CopyFConstantAsFPImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
2702 : OperandRenderer(OR_CopyFConstantAsFPImm), NewInsnID(NewInsnID),
2703 SymbolicName(SymbolicName) {}
2704
classof(const OperandRenderer * R)2705 static bool classof(const OperandRenderer *R) {
2706 return R->getKind() == OR_CopyFConstantAsFPImm;
2707 }
2708
getSymbolicName() const2709 StringRef getSymbolicName() const { return SymbolicName; }
2710
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2711 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2712 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2713 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2714 Table << MatchTable::Opcode("GIR_CopyFConstantAsFPImm")
2715 << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2716 << MatchTable::Comment("OldInsnID")
2717 << MatchTable::IntValue(OldInsnVarID)
2718 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2719 }
2720 };
2721
2722 /// A CopySubRegRenderer emits code to copy a single register operand from an
2723 /// existing instruction to the one being built and indicate that only a
2724 /// subregister should be copied.
2725 class CopySubRegRenderer : public OperandRenderer {
2726 protected:
2727 unsigned NewInsnID;
2728 /// The name of the operand.
2729 const StringRef SymbolicName;
2730 /// The subregister to extract.
2731 const CodeGenSubRegIndex *SubReg;
2732
2733 public:
CopySubRegRenderer(unsigned NewInsnID,StringRef SymbolicName,const CodeGenSubRegIndex * SubReg)2734 CopySubRegRenderer(unsigned NewInsnID, StringRef SymbolicName,
2735 const CodeGenSubRegIndex *SubReg)
2736 : OperandRenderer(OR_CopySubReg), NewInsnID(NewInsnID),
2737 SymbolicName(SymbolicName), SubReg(SubReg) {}
2738
classof(const OperandRenderer * R)2739 static bool classof(const OperandRenderer *R) {
2740 return R->getKind() == OR_CopySubReg;
2741 }
2742
getSymbolicName() const2743 StringRef getSymbolicName() const { return SymbolicName; }
2744
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2745 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2746 const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2747 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2748 Table << MatchTable::Opcode("GIR_CopySubReg")
2749 << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2750 << MatchTable::Comment("OldInsnID")
2751 << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2752 << MatchTable::IntValue(Operand.getOpIdx())
2753 << MatchTable::Comment("SubRegIdx")
2754 << MatchTable::IntValue(SubReg->EnumValue)
2755 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2756 }
2757 };
2758
2759 /// Adds a specific physical register to the instruction being built.
2760 /// This is typically useful for WZR/XZR on AArch64.
2761 class AddRegisterRenderer : public OperandRenderer {
2762 protected:
2763 unsigned InsnID;
2764 const Record *RegisterDef;
2765 bool IsDef;
2766 const CodeGenTarget &Target;
2767
2768 public:
AddRegisterRenderer(unsigned InsnID,const CodeGenTarget & Target,const Record * RegisterDef,bool IsDef=false)2769 AddRegisterRenderer(unsigned InsnID, const CodeGenTarget &Target,
2770 const Record *RegisterDef, bool IsDef = false)
2771 : OperandRenderer(OR_Register), InsnID(InsnID), RegisterDef(RegisterDef),
2772 IsDef(IsDef), Target(Target) {}
2773
classof(const OperandRenderer * R)2774 static bool classof(const OperandRenderer *R) {
2775 return R->getKind() == OR_Register;
2776 }
2777
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2778 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2779 Table << MatchTable::Opcode("GIR_AddRegister")
2780 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID);
2781 if (RegisterDef->getName() != "zero_reg") {
2782 Table << MatchTable::NamedValue(
2783 (RegisterDef->getValue("Namespace")
2784 ? RegisterDef->getValueAsString("Namespace")
2785 : ""),
2786 RegisterDef->getName());
2787 } else {
2788 Table << MatchTable::NamedValue(Target.getRegNamespace(), "NoRegister");
2789 }
2790 Table << MatchTable::Comment("AddRegisterRegFlags");
2791
2792 // TODO: This is encoded as a 64-bit element, but only 16 or 32-bits are
2793 // really needed for a physical register reference. We can pack the
2794 // register and flags in a single field.
2795 if (IsDef)
2796 Table << MatchTable::NamedValue("RegState::Define");
2797 else
2798 Table << MatchTable::IntValue(0);
2799 Table << MatchTable::LineBreak;
2800 }
2801 };
2802
2803 /// Adds a specific temporary virtual register to the instruction being built.
2804 /// This is used to chain instructions together when emitting multiple
2805 /// instructions.
2806 class TempRegRenderer : public OperandRenderer {
2807 protected:
2808 unsigned InsnID;
2809 unsigned TempRegID;
2810 const CodeGenSubRegIndex *SubRegIdx;
2811 bool IsDef;
2812 bool IsDead;
2813
2814 public:
TempRegRenderer(unsigned InsnID,unsigned TempRegID,bool IsDef=false,const CodeGenSubRegIndex * SubReg=nullptr,bool IsDead=false)2815 TempRegRenderer(unsigned InsnID, unsigned TempRegID, bool IsDef = false,
2816 const CodeGenSubRegIndex *SubReg = nullptr,
2817 bool IsDead = false)
2818 : OperandRenderer(OR_Register), InsnID(InsnID), TempRegID(TempRegID),
2819 SubRegIdx(SubReg), IsDef(IsDef), IsDead(IsDead) {}
2820
classof(const OperandRenderer * R)2821 static bool classof(const OperandRenderer *R) {
2822 return R->getKind() == OR_TempRegister;
2823 }
2824
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2825 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2826 if (SubRegIdx) {
2827 assert(!IsDef);
2828 Table << MatchTable::Opcode("GIR_AddTempSubRegister");
2829 } else
2830 Table << MatchTable::Opcode("GIR_AddTempRegister");
2831
2832 Table << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2833 << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID)
2834 << MatchTable::Comment("TempRegFlags");
2835
2836 if (IsDef) {
2837 SmallString<32> RegFlags;
2838 RegFlags += "RegState::Define";
2839 if (IsDead)
2840 RegFlags += "|RegState::Dead";
2841 Table << MatchTable::NamedValue(RegFlags);
2842 } else
2843 Table << MatchTable::IntValue(0);
2844
2845 if (SubRegIdx)
2846 Table << MatchTable::NamedValue(SubRegIdx->getQualifiedName());
2847 Table << MatchTable::LineBreak;
2848 }
2849 };
2850
2851 /// Adds a specific immediate to the instruction being built.
2852 class ImmRenderer : public OperandRenderer {
2853 protected:
2854 unsigned InsnID;
2855 int64_t Imm;
2856
2857 public:
ImmRenderer(unsigned InsnID,int64_t Imm)2858 ImmRenderer(unsigned InsnID, int64_t Imm)
2859 : OperandRenderer(OR_Imm), InsnID(InsnID), Imm(Imm) {}
2860
classof(const OperandRenderer * R)2861 static bool classof(const OperandRenderer *R) {
2862 return R->getKind() == OR_Imm;
2863 }
2864
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2865 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2866 Table << MatchTable::Opcode("GIR_AddImm") << MatchTable::Comment("InsnID")
2867 << MatchTable::IntValue(InsnID) << MatchTable::Comment("Imm")
2868 << MatchTable::IntValue(Imm) << MatchTable::LineBreak;
2869 }
2870 };
2871
2872 /// Adds an enum value for a subreg index to the instruction being built.
2873 class SubRegIndexRenderer : public OperandRenderer {
2874 protected:
2875 unsigned InsnID;
2876 const CodeGenSubRegIndex *SubRegIdx;
2877
2878 public:
SubRegIndexRenderer(unsigned InsnID,const CodeGenSubRegIndex * SRI)2879 SubRegIndexRenderer(unsigned InsnID, const CodeGenSubRegIndex *SRI)
2880 : OperandRenderer(OR_SubRegIndex), InsnID(InsnID), SubRegIdx(SRI) {}
2881
classof(const OperandRenderer * R)2882 static bool classof(const OperandRenderer *R) {
2883 return R->getKind() == OR_SubRegIndex;
2884 }
2885
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2886 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2887 Table << MatchTable::Opcode("GIR_AddImm") << MatchTable::Comment("InsnID")
2888 << MatchTable::IntValue(InsnID) << MatchTable::Comment("SubRegIndex")
2889 << MatchTable::IntValue(SubRegIdx->EnumValue)
2890 << MatchTable::LineBreak;
2891 }
2892 };
2893
2894 /// Adds operands by calling a renderer function supplied by the ComplexPattern
2895 /// matcher function.
2896 class RenderComplexPatternOperand : public OperandRenderer {
2897 private:
2898 unsigned InsnID;
2899 const Record &TheDef;
2900 /// The name of the operand.
2901 const StringRef SymbolicName;
2902 /// The renderer number. This must be unique within a rule since it's used to
2903 /// identify a temporary variable to hold the renderer function.
2904 unsigned RendererID;
2905 /// When provided, this is the suboperand of the ComplexPattern operand to
2906 /// render. Otherwise all the suboperands will be rendered.
2907 Optional<unsigned> SubOperand;
2908
getNumOperands() const2909 unsigned getNumOperands() const {
2910 return TheDef.getValueAsDag("Operands")->getNumArgs();
2911 }
2912
2913 public:
RenderComplexPatternOperand(unsigned InsnID,const Record & TheDef,StringRef SymbolicName,unsigned RendererID,Optional<unsigned> SubOperand=None)2914 RenderComplexPatternOperand(unsigned InsnID, const Record &TheDef,
2915 StringRef SymbolicName, unsigned RendererID,
2916 Optional<unsigned> SubOperand = None)
2917 : OperandRenderer(OR_ComplexPattern), InsnID(InsnID), TheDef(TheDef),
2918 SymbolicName(SymbolicName), RendererID(RendererID),
2919 SubOperand(SubOperand) {}
2920
classof(const OperandRenderer * R)2921 static bool classof(const OperandRenderer *R) {
2922 return R->getKind() == OR_ComplexPattern;
2923 }
2924
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2925 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2926 Table << MatchTable::Opcode(SubOperand.hasValue() ? "GIR_ComplexSubOperandRenderer"
2927 : "GIR_ComplexRenderer")
2928 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2929 << MatchTable::Comment("RendererID")
2930 << MatchTable::IntValue(RendererID);
2931 if (SubOperand.hasValue())
2932 Table << MatchTable::Comment("SubOperand")
2933 << MatchTable::IntValue(SubOperand.getValue());
2934 Table << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2935 }
2936 };
2937
2938 class CustomRenderer : public OperandRenderer {
2939 protected:
2940 unsigned InsnID;
2941 const Record &Renderer;
2942 /// The name of the operand.
2943 const std::string SymbolicName;
2944
2945 public:
CustomRenderer(unsigned InsnID,const Record & Renderer,StringRef SymbolicName)2946 CustomRenderer(unsigned InsnID, const Record &Renderer,
2947 StringRef SymbolicName)
2948 : OperandRenderer(OR_Custom), InsnID(InsnID), Renderer(Renderer),
2949 SymbolicName(SymbolicName) {}
2950
classof(const OperandRenderer * R)2951 static bool classof(const OperandRenderer *R) {
2952 return R->getKind() == OR_Custom;
2953 }
2954
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2955 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2956 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2957 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2958 Table << MatchTable::Opcode("GIR_CustomRenderer")
2959 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2960 << MatchTable::Comment("OldInsnID")
2961 << MatchTable::IntValue(OldInsnVarID)
2962 << MatchTable::Comment("Renderer")
2963 << MatchTable::NamedValue(
2964 "GICR_" + Renderer.getValueAsString("RendererFn").str())
2965 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2966 }
2967 };
2968
2969 class CustomOperandRenderer : public OperandRenderer {
2970 protected:
2971 unsigned InsnID;
2972 const Record &Renderer;
2973 /// The name of the operand.
2974 const std::string SymbolicName;
2975
2976 public:
CustomOperandRenderer(unsigned InsnID,const Record & Renderer,StringRef SymbolicName)2977 CustomOperandRenderer(unsigned InsnID, const Record &Renderer,
2978 StringRef SymbolicName)
2979 : OperandRenderer(OR_CustomOperand), InsnID(InsnID), Renderer(Renderer),
2980 SymbolicName(SymbolicName) {}
2981
classof(const OperandRenderer * R)2982 static bool classof(const OperandRenderer *R) {
2983 return R->getKind() == OR_CustomOperand;
2984 }
2985
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2986 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2987 const OperandMatcher &OpdMatcher = Rule.getOperandMatcher(SymbolicName);
2988 Table << MatchTable::Opcode("GIR_CustomOperandRenderer")
2989 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2990 << MatchTable::Comment("OldInsnID")
2991 << MatchTable::IntValue(OpdMatcher.getInsnVarID())
2992 << MatchTable::Comment("OpIdx")
2993 << MatchTable::IntValue(OpdMatcher.getOpIdx())
2994 << MatchTable::Comment("OperandRenderer")
2995 << MatchTable::NamedValue(
2996 "GICR_" + Renderer.getValueAsString("RendererFn").str())
2997 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2998 }
2999 };
3000
3001 /// An action taken when all Matcher predicates succeeded for a parent rule.
3002 ///
3003 /// Typical actions include:
3004 /// * Changing the opcode of an instruction.
3005 /// * Adding an operand to an instruction.
3006 class MatchAction {
3007 public:
~MatchAction()3008 virtual ~MatchAction() {}
3009
3010 /// Emit the MatchTable opcodes to implement the action.
3011 virtual void emitActionOpcodes(MatchTable &Table,
3012 RuleMatcher &Rule) const = 0;
3013 };
3014
3015 /// Generates a comment describing the matched rule being acted upon.
3016 class DebugCommentAction : public MatchAction {
3017 private:
3018 std::string S;
3019
3020 public:
DebugCommentAction(StringRef S)3021 DebugCommentAction(StringRef S) : S(std::string(S)) {}
3022
emitActionOpcodes(MatchTable & Table,RuleMatcher & Rule) const3023 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
3024 Table << MatchTable::Comment(S) << MatchTable::LineBreak;
3025 }
3026 };
3027
3028 /// Generates code to build an instruction or mutate an existing instruction
3029 /// into the desired instruction when this is possible.
3030 class BuildMIAction : public MatchAction {
3031 private:
3032 unsigned InsnID;
3033 const CodeGenInstruction *I;
3034 InstructionMatcher *Matched;
3035 std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers;
3036
3037 /// True if the instruction can be built solely by mutating the opcode.
canMutate(RuleMatcher & Rule,const InstructionMatcher * Insn) const3038 bool canMutate(RuleMatcher &Rule, const InstructionMatcher *Insn) const {
3039 if (!Insn)
3040 return false;
3041
3042 if (OperandRenderers.size() != Insn->getNumOperands())
3043 return false;
3044
3045 for (const auto &Renderer : enumerate(OperandRenderers)) {
3046 if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) {
3047 const OperandMatcher &OM = Rule.getOperandMatcher(Copy->getSymbolicName());
3048 if (Insn != &OM.getInstructionMatcher() ||
3049 OM.getOpIdx() != Renderer.index())
3050 return false;
3051 } else
3052 return false;
3053 }
3054
3055 return true;
3056 }
3057
3058 public:
BuildMIAction(unsigned InsnID,const CodeGenInstruction * I)3059 BuildMIAction(unsigned InsnID, const CodeGenInstruction *I)
3060 : InsnID(InsnID), I(I), Matched(nullptr) {}
3061
getInsnID() const3062 unsigned getInsnID() const { return InsnID; }
getCGI() const3063 const CodeGenInstruction *getCGI() const { return I; }
3064
chooseInsnToMutate(RuleMatcher & Rule)3065 void chooseInsnToMutate(RuleMatcher &Rule) {
3066 for (auto *MutateCandidate : Rule.mutatable_insns()) {
3067 if (canMutate(Rule, MutateCandidate)) {
3068 // Take the first one we're offered that we're able to mutate.
3069 Rule.reserveInsnMatcherForMutation(MutateCandidate);
3070 Matched = MutateCandidate;
3071 return;
3072 }
3073 }
3074 }
3075
3076 template <class Kind, class... Args>
3077 Kind &addRenderer(Args&&... args) {
3078 OperandRenderers.emplace_back(
3079 std::make_unique<Kind>(InsnID, std::forward<Args>(args)...));
3080 return *static_cast<Kind *>(OperandRenderers.back().get());
3081 }
3082
emitActionOpcodes(MatchTable & Table,RuleMatcher & Rule) const3083 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
3084 if (Matched) {
3085 assert(canMutate(Rule, Matched) &&
3086 "Arranged to mutate an insn that isn't mutatable");
3087
3088 unsigned RecycleInsnID = Rule.getInsnVarID(*Matched);
3089 Table << MatchTable::Opcode("GIR_MutateOpcode")
3090 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
3091 << MatchTable::Comment("RecycleInsnID")
3092 << MatchTable::IntValue(RecycleInsnID)
3093 << MatchTable::Comment("Opcode")
3094 << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
3095 << MatchTable::LineBreak;
3096
3097 if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) {
3098 for (auto Def : I->ImplicitDefs) {
3099 auto Namespace = Def->getValue("Namespace")
3100 ? Def->getValueAsString("Namespace")
3101 : "";
3102 Table << MatchTable::Opcode("GIR_AddImplicitDef")
3103 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
3104 << MatchTable::NamedValue(Namespace, Def->getName())
3105 << MatchTable::LineBreak;
3106 }
3107 for (auto Use : I->ImplicitUses) {
3108 auto Namespace = Use->getValue("Namespace")
3109 ? Use->getValueAsString("Namespace")
3110 : "";
3111 Table << MatchTable::Opcode("GIR_AddImplicitUse")
3112 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
3113 << MatchTable::NamedValue(Namespace, Use->getName())
3114 << MatchTable::LineBreak;
3115 }
3116 }
3117 return;
3118 }
3119
3120 // TODO: Simple permutation looks like it could be almost as common as
3121 // mutation due to commutative operations.
3122
3123 Table << MatchTable::Opcode("GIR_BuildMI") << MatchTable::Comment("InsnID")
3124 << MatchTable::IntValue(InsnID) << MatchTable::Comment("Opcode")
3125 << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
3126 << MatchTable::LineBreak;
3127 for (const auto &Renderer : OperandRenderers)
3128 Renderer->emitRenderOpcodes(Table, Rule);
3129
3130 if (I->mayLoad || I->mayStore) {
3131 Table << MatchTable::Opcode("GIR_MergeMemOperands")
3132 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
3133 << MatchTable::Comment("MergeInsnID's");
3134 // Emit the ID's for all the instructions that are matched by this rule.
3135 // TODO: Limit this to matched instructions that mayLoad/mayStore or have
3136 // some other means of having a memoperand. Also limit this to
3137 // emitted instructions that expect to have a memoperand too. For
3138 // example, (G_SEXT (G_LOAD x)) that results in separate load and
3139 // sign-extend instructions shouldn't put the memoperand on the
3140 // sign-extend since it has no effect there.
3141 std::vector<unsigned> MergeInsnIDs;
3142 for (const auto &IDMatcherPair : Rule.defined_insn_vars())
3143 MergeInsnIDs.push_back(IDMatcherPair.second);
3144 llvm::sort(MergeInsnIDs);
3145 for (const auto &MergeInsnID : MergeInsnIDs)
3146 Table << MatchTable::IntValue(MergeInsnID);
3147 Table << MatchTable::NamedValue("GIU_MergeMemOperands_EndOfList")
3148 << MatchTable::LineBreak;
3149 }
3150
3151 // FIXME: This is a hack but it's sufficient for ISel. We'll need to do
3152 // better for combines. Particularly when there are multiple match
3153 // roots.
3154 if (InsnID == 0)
3155 Table << MatchTable::Opcode("GIR_EraseFromParent")
3156 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
3157 << MatchTable::LineBreak;
3158 }
3159 };
3160
3161 /// Generates code to constrain the operands of an output instruction to the
3162 /// register classes specified by the definition of that instruction.
3163 class ConstrainOperandsToDefinitionAction : public MatchAction {
3164 unsigned InsnID;
3165
3166 public:
ConstrainOperandsToDefinitionAction(unsigned InsnID)3167 ConstrainOperandsToDefinitionAction(unsigned InsnID) : InsnID(InsnID) {}
3168
emitActionOpcodes(MatchTable & Table,RuleMatcher & Rule) const3169 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
3170 Table << MatchTable::Opcode("GIR_ConstrainSelectedInstOperands")
3171 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
3172 << MatchTable::LineBreak;
3173 }
3174 };
3175
3176 /// Generates code to constrain the specified operand of an output instruction
3177 /// to the specified register class.
3178 class ConstrainOperandToRegClassAction : public MatchAction {
3179 unsigned InsnID;
3180 unsigned OpIdx;
3181 const CodeGenRegisterClass &RC;
3182
3183 public:
ConstrainOperandToRegClassAction(unsigned InsnID,unsigned OpIdx,const CodeGenRegisterClass & RC)3184 ConstrainOperandToRegClassAction(unsigned InsnID, unsigned OpIdx,
3185 const CodeGenRegisterClass &RC)
3186 : InsnID(InsnID), OpIdx(OpIdx), RC(RC) {}
3187
emitActionOpcodes(MatchTable & Table,RuleMatcher & Rule) const3188 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
3189 Table << MatchTable::Opcode("GIR_ConstrainOperandRC")
3190 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
3191 << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
3192 << MatchTable::NamedValue(RC.getQualifiedName() + "RegClassID")
3193 << MatchTable::LineBreak;
3194 }
3195 };
3196
3197 /// Generates code to create a temporary register which can be used to chain
3198 /// instructions together.
3199 class MakeTempRegisterAction : public MatchAction {
3200 private:
3201 LLTCodeGen Ty;
3202 unsigned TempRegID;
3203
3204 public:
MakeTempRegisterAction(const LLTCodeGen & Ty,unsigned TempRegID)3205 MakeTempRegisterAction(const LLTCodeGen &Ty, unsigned TempRegID)
3206 : Ty(Ty), TempRegID(TempRegID) {
3207 KnownTypes.insert(Ty);
3208 }
3209
emitActionOpcodes(MatchTable & Table,RuleMatcher & Rule) const3210 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
3211 Table << MatchTable::Opcode("GIR_MakeTempReg")
3212 << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID)
3213 << MatchTable::Comment("TypeID")
3214 << MatchTable::NamedValue(Ty.getCxxEnumValue())
3215 << MatchTable::LineBreak;
3216 }
3217 };
3218
addInstructionMatcher(StringRef SymbolicName)3219 InstructionMatcher &RuleMatcher::addInstructionMatcher(StringRef SymbolicName) {
3220 Matchers.emplace_back(new InstructionMatcher(*this, SymbolicName));
3221 MutatableInsns.insert(Matchers.back().get());
3222 return *Matchers.back();
3223 }
3224
addRequiredFeature(Record * Feature)3225 void RuleMatcher::addRequiredFeature(Record *Feature) {
3226 RequiredFeatures.push_back(Feature);
3227 }
3228
getRequiredFeatures() const3229 const std::vector<Record *> &RuleMatcher::getRequiredFeatures() const {
3230 return RequiredFeatures;
3231 }
3232
3233 // Emplaces an action of the specified Kind at the end of the action list.
3234 //
3235 // Returns a reference to the newly created action.
3236 //
3237 // Like std::vector::emplace_back(), may invalidate all iterators if the new
3238 // size exceeds the capacity. Otherwise, only invalidates the past-the-end
3239 // iterator.
3240 template <class Kind, class... Args>
3241 Kind &RuleMatcher::addAction(Args &&... args) {
3242 Actions.emplace_back(std::make_unique<Kind>(std::forward<Args>(args)...));
3243 return *static_cast<Kind *>(Actions.back().get());
3244 }
3245
3246 // Emplaces an action of the specified Kind before the given insertion point.
3247 //
3248 // Returns an iterator pointing at the newly created instruction.
3249 //
3250 // Like std::vector::insert(), may invalidate all iterators if the new size
3251 // exceeds the capacity. Otherwise, only invalidates the iterators from the
3252 // insertion point onwards.
3253 template <class Kind, class... Args>
insertAction(action_iterator InsertPt,Args &&...args)3254 action_iterator RuleMatcher::insertAction(action_iterator InsertPt,
3255 Args &&... args) {
3256 return Actions.emplace(InsertPt,
3257 std::make_unique<Kind>(std::forward<Args>(args)...));
3258 }
3259
implicitlyDefineInsnVar(InstructionMatcher & Matcher)3260 unsigned RuleMatcher::implicitlyDefineInsnVar(InstructionMatcher &Matcher) {
3261 unsigned NewInsnVarID = NextInsnVarID++;
3262 InsnVariableIDs[&Matcher] = NewInsnVarID;
3263 return NewInsnVarID;
3264 }
3265
getInsnVarID(InstructionMatcher & InsnMatcher) const3266 unsigned RuleMatcher::getInsnVarID(InstructionMatcher &InsnMatcher) const {
3267 const auto &I = InsnVariableIDs.find(&InsnMatcher);
3268 if (I != InsnVariableIDs.end())
3269 return I->second;
3270 llvm_unreachable("Matched Insn was not captured in a local variable");
3271 }
3272
defineOperand(StringRef SymbolicName,OperandMatcher & OM)3273 void RuleMatcher::defineOperand(StringRef SymbolicName, OperandMatcher &OM) {
3274 if (DefinedOperands.find(SymbolicName) == DefinedOperands.end()) {
3275 DefinedOperands[SymbolicName] = &OM;
3276 return;
3277 }
3278
3279 // If the operand is already defined, then we must ensure both references in
3280 // the matcher have the exact same node.
3281 OM.addPredicate<SameOperandMatcher>(OM.getSymbolicName());
3282 }
3283
definePhysRegOperand(Record * Reg,OperandMatcher & OM)3284 void RuleMatcher::definePhysRegOperand(Record *Reg, OperandMatcher &OM) {
3285 if (PhysRegOperands.find(Reg) == PhysRegOperands.end()) {
3286 PhysRegOperands[Reg] = &OM;
3287 return;
3288 }
3289 }
3290
3291 InstructionMatcher &
getInstructionMatcher(StringRef SymbolicName) const3292 RuleMatcher::getInstructionMatcher(StringRef SymbolicName) const {
3293 for (const auto &I : InsnVariableIDs)
3294 if (I.first->getSymbolicName() == SymbolicName)
3295 return *I.first;
3296 llvm_unreachable(
3297 ("Failed to lookup instruction " + SymbolicName).str().c_str());
3298 }
3299
3300 const OperandMatcher &
getPhysRegOperandMatcher(Record * Reg) const3301 RuleMatcher::getPhysRegOperandMatcher(Record *Reg) const {
3302 const auto &I = PhysRegOperands.find(Reg);
3303
3304 if (I == PhysRegOperands.end()) {
3305 PrintFatalError(SrcLoc, "Register " + Reg->getName() +
3306 " was not declared in matcher");
3307 }
3308
3309 return *I->second;
3310 }
3311
3312 const OperandMatcher &
getOperandMatcher(StringRef Name) const3313 RuleMatcher::getOperandMatcher(StringRef Name) const {
3314 const auto &I = DefinedOperands.find(Name);
3315
3316 if (I == DefinedOperands.end())
3317 PrintFatalError(SrcLoc, "Operand " + Name + " was not declared in matcher");
3318
3319 return *I->second;
3320 }
3321
emit(MatchTable & Table)3322 void RuleMatcher::emit(MatchTable &Table) {
3323 if (Matchers.empty())
3324 llvm_unreachable("Unexpected empty matcher!");
3325
3326 // The representation supports rules that require multiple roots such as:
3327 // %ptr(p0) = ...
3328 // %elt0(s32) = G_LOAD %ptr
3329 // %1(p0) = G_ADD %ptr, 4
3330 // %elt1(s32) = G_LOAD p0 %1
3331 // which could be usefully folded into:
3332 // %ptr(p0) = ...
3333 // %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr
3334 // on some targets but we don't need to make use of that yet.
3335 assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
3336
3337 unsigned LabelID = Table.allocateLabelID();
3338 Table << MatchTable::Opcode("GIM_Try", +1)
3339 << MatchTable::Comment("On fail goto")
3340 << MatchTable::JumpTarget(LabelID)
3341 << MatchTable::Comment(("Rule ID " + Twine(RuleID) + " //").str())
3342 << MatchTable::LineBreak;
3343
3344 if (!RequiredFeatures.empty()) {
3345 Table << MatchTable::Opcode("GIM_CheckFeatures")
3346 << MatchTable::NamedValue(getNameForFeatureBitset(RequiredFeatures))
3347 << MatchTable::LineBreak;
3348 }
3349
3350 Matchers.front()->emitPredicateOpcodes(Table, *this);
3351
3352 // We must also check if it's safe to fold the matched instructions.
3353 if (InsnVariableIDs.size() >= 2) {
3354 // Invert the map to create stable ordering (by var names)
3355 SmallVector<unsigned, 2> InsnIDs;
3356 for (const auto &Pair : InsnVariableIDs) {
3357 // Skip the root node since it isn't moving anywhere. Everything else is
3358 // sinking to meet it.
3359 if (Pair.first == Matchers.front().get())
3360 continue;
3361
3362 InsnIDs.push_back(Pair.second);
3363 }
3364 llvm::sort(InsnIDs);
3365
3366 for (const auto &InsnID : InsnIDs) {
3367 // Reject the difficult cases until we have a more accurate check.
3368 Table << MatchTable::Opcode("GIM_CheckIsSafeToFold")
3369 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
3370 << MatchTable::LineBreak;
3371
3372 // FIXME: Emit checks to determine it's _actually_ safe to fold and/or
3373 // account for unsafe cases.
3374 //
3375 // Example:
3376 // MI1--> %0 = ...
3377 // %1 = ... %0
3378 // MI0--> %2 = ... %0
3379 // It's not safe to erase MI1. We currently handle this by not
3380 // erasing %0 (even when it's dead).
3381 //
3382 // Example:
3383 // MI1--> %0 = load volatile @a
3384 // %1 = load volatile @a
3385 // MI0--> %2 = ... %0
3386 // It's not safe to sink %0's def past %1. We currently handle
3387 // this by rejecting all loads.
3388 //
3389 // Example:
3390 // MI1--> %0 = load @a
3391 // %1 = store @a
3392 // MI0--> %2 = ... %0
3393 // It's not safe to sink %0's def past %1. We currently handle
3394 // this by rejecting all loads.
3395 //
3396 // Example:
3397 // G_CONDBR %cond, @BB1
3398 // BB0:
3399 // MI1--> %0 = load @a
3400 // G_BR @BB1
3401 // BB1:
3402 // MI0--> %2 = ... %0
3403 // It's not always safe to sink %0 across control flow. In this
3404 // case it may introduce a memory fault. We currentl handle this
3405 // by rejecting all loads.
3406 }
3407 }
3408
3409 for (const auto &PM : EpilogueMatchers)
3410 PM->emitPredicateOpcodes(Table, *this);
3411
3412 for (const auto &MA : Actions)
3413 MA->emitActionOpcodes(Table, *this);
3414
3415 if (Table.isWithCoverage())
3416 Table << MatchTable::Opcode("GIR_Coverage") << MatchTable::IntValue(RuleID)
3417 << MatchTable::LineBreak;
3418 else
3419 Table << MatchTable::Comment(("GIR_Coverage, " + Twine(RuleID) + ",").str())
3420 << MatchTable::LineBreak;
3421
3422 Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak
3423 << MatchTable::Label(LabelID);
3424 ++NumPatternEmitted;
3425 }
3426
isHigherPriorityThan(const RuleMatcher & B) const3427 bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
3428 // Rules involving more match roots have higher priority.
3429 if (Matchers.size() > B.Matchers.size())
3430 return true;
3431 if (Matchers.size() < B.Matchers.size())
3432 return false;
3433
3434 for (auto Matcher : zip(Matchers, B.Matchers)) {
3435 if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher)))
3436 return true;
3437 if (std::get<1>(Matcher)->isHigherPriorityThan(*std::get<0>(Matcher)))
3438 return false;
3439 }
3440
3441 return false;
3442 }
3443
countRendererFns() const3444 unsigned RuleMatcher::countRendererFns() const {
3445 return std::accumulate(
3446 Matchers.begin(), Matchers.end(), 0,
3447 [](unsigned A, const std::unique_ptr<InstructionMatcher> &Matcher) {
3448 return A + Matcher->countRendererFns();
3449 });
3450 }
3451
isHigherPriorityThan(const OperandPredicateMatcher & B) const3452 bool OperandPredicateMatcher::isHigherPriorityThan(
3453 const OperandPredicateMatcher &B) const {
3454 // Generally speaking, an instruction is more important than an Int or a
3455 // LiteralInt because it can cover more nodes but theres an exception to
3456 // this. G_CONSTANT's are less important than either of those two because they
3457 // are more permissive.
3458
3459 const InstructionOperandMatcher *AOM =
3460 dyn_cast<InstructionOperandMatcher>(this);
3461 const InstructionOperandMatcher *BOM =
3462 dyn_cast<InstructionOperandMatcher>(&B);
3463 bool AIsConstantInsn = AOM && AOM->getInsnMatcher().isConstantInstruction();
3464 bool BIsConstantInsn = BOM && BOM->getInsnMatcher().isConstantInstruction();
3465
3466 if (AOM && BOM) {
3467 // The relative priorities between a G_CONSTANT and any other instruction
3468 // don't actually matter but this code is needed to ensure a strict weak
3469 // ordering. This is particularly important on Windows where the rules will
3470 // be incorrectly sorted without it.
3471 if (AIsConstantInsn != BIsConstantInsn)
3472 return AIsConstantInsn < BIsConstantInsn;
3473 return false;
3474 }
3475
3476 if (AOM && AIsConstantInsn && (B.Kind == OPM_Int || B.Kind == OPM_LiteralInt))
3477 return false;
3478 if (BOM && BIsConstantInsn && (Kind == OPM_Int || Kind == OPM_LiteralInt))
3479 return true;
3480
3481 return Kind < B.Kind;
3482 }
3483
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const3484 void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
3485 RuleMatcher &Rule) const {
3486 const OperandMatcher &OtherOM = Rule.getOperandMatcher(MatchingName);
3487 unsigned OtherInsnVarID = Rule.getInsnVarID(OtherOM.getInstructionMatcher());
3488 assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getInsnVarID());
3489
3490 Table << MatchTable::Opcode("GIM_CheckIsSameOperand")
3491 << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
3492 << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx)
3493 << MatchTable::Comment("OtherMI")
3494 << MatchTable::IntValue(OtherInsnVarID)
3495 << MatchTable::Comment("OtherOpIdx")
3496 << MatchTable::IntValue(OtherOM.getOpIdx())
3497 << MatchTable::LineBreak;
3498 }
3499
3500 //===- GlobalISelEmitter class --------------------------------------------===//
3501
getInstResultType(const TreePatternNode * Dst)3502 static Expected<LLTCodeGen> getInstResultType(const TreePatternNode *Dst) {
3503 ArrayRef<TypeSetByHwMode> ChildTypes = Dst->getExtTypes();
3504 if (ChildTypes.size() != 1)
3505 return failedImport("Dst pattern child has multiple results");
3506
3507 Optional<LLTCodeGen> MaybeOpTy;
3508 if (ChildTypes.front().isMachineValueType()) {
3509 MaybeOpTy =
3510 MVTToLLT(ChildTypes.front().getMachineValueType().SimpleTy);
3511 }
3512
3513 if (!MaybeOpTy)
3514 return failedImport("Dst operand has an unsupported type");
3515 return *MaybeOpTy;
3516 }
3517
3518 class GlobalISelEmitter {
3519 public:
3520 explicit GlobalISelEmitter(RecordKeeper &RK);
3521 void run(raw_ostream &OS);
3522
3523 private:
3524 const RecordKeeper &RK;
3525 const CodeGenDAGPatterns CGP;
3526 const CodeGenTarget &Target;
3527 CodeGenRegBank &CGRegs;
3528
3529 /// Keep track of the equivalence between SDNodes and Instruction by mapping
3530 /// SDNodes to the GINodeEquiv mapping. We need to map to the GINodeEquiv to
3531 /// check for attributes on the relation such as CheckMMOIsNonAtomic.
3532 /// This is defined using 'GINodeEquiv' in the target description.
3533 DenseMap<Record *, Record *> NodeEquivs;
3534
3535 /// Keep track of the equivalence between ComplexPattern's and
3536 /// GIComplexOperandMatcher. Map entries are specified by subclassing
3537 /// GIComplexPatternEquiv.
3538 DenseMap<const Record *, const Record *> ComplexPatternEquivs;
3539
3540 /// Keep track of the equivalence between SDNodeXForm's and
3541 /// GICustomOperandRenderer. Map entries are specified by subclassing
3542 /// GISDNodeXFormEquiv.
3543 DenseMap<const Record *, const Record *> SDNodeXFormEquivs;
3544
3545 /// Keep track of Scores of PatternsToMatch similar to how the DAG does.
3546 /// This adds compatibility for RuleMatchers to use this for ordering rules.
3547 DenseMap<uint64_t, int> RuleMatcherScores;
3548
3549 // Map of predicates to their subtarget features.
3550 SubtargetFeatureInfoMap SubtargetFeatures;
3551
3552 // Rule coverage information.
3553 Optional<CodeGenCoverage> RuleCoverage;
3554
3555 /// Variables used to help with collecting of named operands for predicates
3556 /// with 'let PredicateCodeUsesOperands = 1'. WaitingForNamedOperands is set
3557 /// to the number of named operands that predicate expects. Store locations in
3558 /// StoreIdxForName correspond to the order in which operand names appear in
3559 /// predicate's argument list.
3560 /// When we visit named leaf operand and WaitingForNamedOperands is not zero,
3561 /// add matcher that will record operand and decrease counter.
3562 unsigned WaitingForNamedOperands = 0;
3563 StringMap<unsigned> StoreIdxForName;
3564
3565 void gatherOpcodeValues();
3566 void gatherTypeIDValues();
3567 void gatherNodeEquivs();
3568
3569 Record *findNodeEquiv(Record *N) const;
3570 const CodeGenInstruction *getEquivNode(Record &Equiv,
3571 const TreePatternNode *N) const;
3572
3573 Error importRulePredicates(RuleMatcher &M, ArrayRef<Record *> Predicates);
3574 Expected<InstructionMatcher &>
3575 createAndImportSelDAGMatcher(RuleMatcher &Rule,
3576 InstructionMatcher &InsnMatcher,
3577 const TreePatternNode *Src, unsigned &TempOpIdx);
3578 Error importComplexPatternOperandMatcher(OperandMatcher &OM, Record *R,
3579 unsigned &TempOpIdx) const;
3580 Error importChildMatcher(RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
3581 const TreePatternNode *SrcChild,
3582 bool OperandIsAPointer, bool OperandIsImmArg,
3583 unsigned OpIdx, unsigned &TempOpIdx);
3584
3585 Expected<BuildMIAction &> createAndImportInstructionRenderer(
3586 RuleMatcher &M, InstructionMatcher &InsnMatcher,
3587 const TreePatternNode *Src, const TreePatternNode *Dst);
3588 Expected<action_iterator> createAndImportSubInstructionRenderer(
3589 action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst,
3590 unsigned TempReg);
3591 Expected<action_iterator>
3592 createInstructionRenderer(action_iterator InsertPt, RuleMatcher &M,
3593 const TreePatternNode *Dst);
3594
3595 Expected<action_iterator>
3596 importExplicitDefRenderers(action_iterator InsertPt, RuleMatcher &M,
3597 BuildMIAction &DstMIBuilder,
3598 const TreePatternNode *Dst);
3599
3600 Expected<action_iterator>
3601 importExplicitUseRenderers(action_iterator InsertPt, RuleMatcher &M,
3602 BuildMIAction &DstMIBuilder,
3603 const llvm::TreePatternNode *Dst);
3604 Expected<action_iterator>
3605 importExplicitUseRenderer(action_iterator InsertPt, RuleMatcher &Rule,
3606 BuildMIAction &DstMIBuilder,
3607 TreePatternNode *DstChild);
3608 Error importDefaultOperandRenderers(action_iterator InsertPt, RuleMatcher &M,
3609 BuildMIAction &DstMIBuilder,
3610 DagInit *DefaultOps) const;
3611 Error
3612 importImplicitDefRenderers(BuildMIAction &DstMIBuilder,
3613 const std::vector<Record *> &ImplicitDefs) const;
3614
3615 void emitCxxPredicateFns(raw_ostream &OS, StringRef CodeFieldName,
3616 StringRef TypeIdentifier, StringRef ArgType,
3617 StringRef ArgName, StringRef AdditionalArgs,
3618 StringRef AdditionalDeclarations,
3619 std::function<bool(const Record *R)> Filter);
3620 void emitImmPredicateFns(raw_ostream &OS, StringRef TypeIdentifier,
3621 StringRef ArgType,
3622 std::function<bool(const Record *R)> Filter);
3623 void emitMIPredicateFns(raw_ostream &OS);
3624
3625 /// Analyze pattern \p P, returning a matcher for it if possible.
3626 /// Otherwise, return an Error explaining why we don't support it.
3627 Expected<RuleMatcher> runOnPattern(const PatternToMatch &P);
3628
3629 void declareSubtargetFeature(Record *Predicate);
3630
3631 MatchTable buildMatchTable(MutableArrayRef<RuleMatcher> Rules, bool Optimize,
3632 bool WithCoverage);
3633
3634 /// Infer a CodeGenRegisterClass for the type of \p SuperRegNode. The returned
3635 /// CodeGenRegisterClass will support the CodeGenRegisterClass of
3636 /// \p SubRegNode, and the subregister index defined by \p SubRegIdxNode.
3637 /// If no register class is found, return None.
3638 Optional<const CodeGenRegisterClass *>
3639 inferSuperRegisterClassForNode(const TypeSetByHwMode &Ty,
3640 TreePatternNode *SuperRegNode,
3641 TreePatternNode *SubRegIdxNode);
3642 Optional<CodeGenSubRegIndex *>
3643 inferSubRegIndexForNode(TreePatternNode *SubRegIdxNode);
3644
3645 /// Infer a CodeGenRegisterClass which suppoorts \p Ty and \p SubRegIdxNode.
3646 /// Return None if no such class exists.
3647 Optional<const CodeGenRegisterClass *>
3648 inferSuperRegisterClass(const TypeSetByHwMode &Ty,
3649 TreePatternNode *SubRegIdxNode);
3650
3651 /// Return the CodeGenRegisterClass associated with \p Leaf if it has one.
3652 Optional<const CodeGenRegisterClass *>
3653 getRegClassFromLeaf(TreePatternNode *Leaf);
3654
3655 /// Return a CodeGenRegisterClass for \p N if one can be found. Return None
3656 /// otherwise.
3657 Optional<const CodeGenRegisterClass *>
3658 inferRegClassFromPattern(TreePatternNode *N);
3659
3660 /// Return the size of the MemoryVT in this predicate, if possible.
3661 Optional<unsigned>
3662 getMemSizeBitsFromPredicate(const TreePredicateFn &Predicate);
3663
3664 // Add builtin predicates.
3665 Expected<InstructionMatcher &>
3666 addBuiltinPredicates(const Record *SrcGIEquivOrNull,
3667 const TreePredicateFn &Predicate,
3668 InstructionMatcher &InsnMatcher, bool &HasAddedMatcher);
3669
3670 public:
3671 /// Takes a sequence of \p Rules and group them based on the predicates
3672 /// they share. \p MatcherStorage is used as a memory container
3673 /// for the group that are created as part of this process.
3674 ///
3675 /// What this optimization does looks like if GroupT = GroupMatcher:
3676 /// Output without optimization:
3677 /// \verbatim
3678 /// # R1
3679 /// # predicate A
3680 /// # predicate B
3681 /// ...
3682 /// # R2
3683 /// # predicate A // <-- effectively this is going to be checked twice.
3684 /// // Once in R1 and once in R2.
3685 /// # predicate C
3686 /// \endverbatim
3687 /// Output with optimization:
3688 /// \verbatim
3689 /// # Group1_2
3690 /// # predicate A // <-- Check is now shared.
3691 /// # R1
3692 /// # predicate B
3693 /// # R2
3694 /// # predicate C
3695 /// \endverbatim
3696 template <class GroupT>
3697 static std::vector<Matcher *> optimizeRules(
3698 ArrayRef<Matcher *> Rules,
3699 std::vector<std::unique_ptr<Matcher>> &MatcherStorage);
3700 };
3701
gatherOpcodeValues()3702 void GlobalISelEmitter::gatherOpcodeValues() {
3703 InstructionOpcodeMatcher::initOpcodeValuesMap(Target);
3704 }
3705
gatherTypeIDValues()3706 void GlobalISelEmitter::gatherTypeIDValues() {
3707 LLTOperandMatcher::initTypeIDValuesMap();
3708 }
3709
gatherNodeEquivs()3710 void GlobalISelEmitter::gatherNodeEquivs() {
3711 assert(NodeEquivs.empty());
3712 for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
3713 NodeEquivs[Equiv->getValueAsDef("Node")] = Equiv;
3714
3715 assert(ComplexPatternEquivs.empty());
3716 for (Record *Equiv : RK.getAllDerivedDefinitions("GIComplexPatternEquiv")) {
3717 Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
3718 if (!SelDAGEquiv)
3719 continue;
3720 ComplexPatternEquivs[SelDAGEquiv] = Equiv;
3721 }
3722
3723 assert(SDNodeXFormEquivs.empty());
3724 for (Record *Equiv : RK.getAllDerivedDefinitions("GISDNodeXFormEquiv")) {
3725 Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
3726 if (!SelDAGEquiv)
3727 continue;
3728 SDNodeXFormEquivs[SelDAGEquiv] = Equiv;
3729 }
3730 }
3731
findNodeEquiv(Record * N) const3732 Record *GlobalISelEmitter::findNodeEquiv(Record *N) const {
3733 return NodeEquivs.lookup(N);
3734 }
3735
3736 const CodeGenInstruction *
getEquivNode(Record & Equiv,const TreePatternNode * N) const3737 GlobalISelEmitter::getEquivNode(Record &Equiv, const TreePatternNode *N) const {
3738 if (N->getNumChildren() >= 1) {
3739 // setcc operation maps to two different G_* instructions based on the type.
3740 if (!Equiv.isValueUnset("IfFloatingPoint") &&
3741 MVT(N->getChild(0)->getSimpleType(0)).isFloatingPoint())
3742 return &Target.getInstruction(Equiv.getValueAsDef("IfFloatingPoint"));
3743 }
3744
3745 for (const TreePredicateCall &Call : N->getPredicateCalls()) {
3746 const TreePredicateFn &Predicate = Call.Fn;
3747 if (!Equiv.isValueUnset("IfSignExtend") && Predicate.isLoad() &&
3748 Predicate.isSignExtLoad())
3749 return &Target.getInstruction(Equiv.getValueAsDef("IfSignExtend"));
3750 if (!Equiv.isValueUnset("IfZeroExtend") && Predicate.isLoad() &&
3751 Predicate.isZeroExtLoad())
3752 return &Target.getInstruction(Equiv.getValueAsDef("IfZeroExtend"));
3753 }
3754
3755 return &Target.getInstruction(Equiv.getValueAsDef("I"));
3756 }
3757
GlobalISelEmitter(RecordKeeper & RK)3758 GlobalISelEmitter::GlobalISelEmitter(RecordKeeper &RK)
3759 : RK(RK), CGP(RK), Target(CGP.getTargetInfo()),
3760 CGRegs(Target.getRegBank()) {}
3761
3762 //===- Emitter ------------------------------------------------------------===//
3763
importRulePredicates(RuleMatcher & M,ArrayRef<Record * > Predicates)3764 Error GlobalISelEmitter::importRulePredicates(RuleMatcher &M,
3765 ArrayRef<Record *> Predicates) {
3766 for (Record *Pred : Predicates) {
3767 if (Pred->getValueAsString("CondString").empty())
3768 continue;
3769 declareSubtargetFeature(Pred);
3770 M.addRequiredFeature(Pred);
3771 }
3772
3773 return Error::success();
3774 }
3775
getMemSizeBitsFromPredicate(const TreePredicateFn & Predicate)3776 Optional<unsigned> GlobalISelEmitter::getMemSizeBitsFromPredicate(const TreePredicateFn &Predicate) {
3777 Optional<LLTCodeGen> MemTyOrNone =
3778 MVTToLLT(getValueType(Predicate.getMemoryVT()));
3779
3780 if (!MemTyOrNone)
3781 return None;
3782
3783 // Align so unusual types like i1 don't get rounded down.
3784 return llvm::alignTo(MemTyOrNone->get().getSizeInBits(), 8);
3785 }
3786
addBuiltinPredicates(const Record * SrcGIEquivOrNull,const TreePredicateFn & Predicate,InstructionMatcher & InsnMatcher,bool & HasAddedMatcher)3787 Expected<InstructionMatcher &> GlobalISelEmitter::addBuiltinPredicates(
3788 const Record *SrcGIEquivOrNull, const TreePredicateFn &Predicate,
3789 InstructionMatcher &InsnMatcher, bool &HasAddedMatcher) {
3790 if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
3791 if (const ListInit *AddrSpaces = Predicate.getAddressSpaces()) {
3792 SmallVector<unsigned, 4> ParsedAddrSpaces;
3793
3794 for (Init *Val : AddrSpaces->getValues()) {
3795 IntInit *IntVal = dyn_cast<IntInit>(Val);
3796 if (!IntVal)
3797 return failedImport("Address space is not an integer");
3798 ParsedAddrSpaces.push_back(IntVal->getValue());
3799 }
3800
3801 if (!ParsedAddrSpaces.empty()) {
3802 InsnMatcher.addPredicate<MemoryAddressSpacePredicateMatcher>(
3803 0, ParsedAddrSpaces);
3804 }
3805 }
3806
3807 int64_t MinAlign = Predicate.getMinAlignment();
3808 if (MinAlign > 0)
3809 InsnMatcher.addPredicate<MemoryAlignmentPredicateMatcher>(0, MinAlign);
3810 }
3811
3812 // G_LOAD is used for both non-extending and any-extending loads.
3813 if (Predicate.isLoad() && Predicate.isNonExtLoad()) {
3814 InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3815 0, MemoryVsLLTSizePredicateMatcher::EqualTo, 0);
3816 return InsnMatcher;
3817 }
3818 if (Predicate.isLoad() && Predicate.isAnyExtLoad()) {
3819 InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3820 0, MemoryVsLLTSizePredicateMatcher::LessThan, 0);
3821 return InsnMatcher;
3822 }
3823
3824 if (Predicate.isStore()) {
3825 if (Predicate.isTruncStore()) {
3826 if (Predicate.getMemoryVT() != nullptr) {
3827 // FIXME: If MemoryVT is set, we end up with 2 checks for the MMO size.
3828 auto MemSizeInBits = getMemSizeBitsFromPredicate(Predicate);
3829 if (!MemSizeInBits)
3830 return failedImport("MemVT could not be converted to LLT");
3831
3832 InsnMatcher.addPredicate<MemorySizePredicateMatcher>(0, *MemSizeInBits /
3833 8);
3834 } else {
3835 InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3836 0, MemoryVsLLTSizePredicateMatcher::LessThan, 0);
3837 }
3838 return InsnMatcher;
3839 }
3840 if (Predicate.isNonTruncStore()) {
3841 // We need to check the sizes match here otherwise we could incorrectly
3842 // match truncating stores with non-truncating ones.
3843 InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3844 0, MemoryVsLLTSizePredicateMatcher::EqualTo, 0);
3845 }
3846 }
3847
3848 // No check required. We already did it by swapping the opcode.
3849 if (!SrcGIEquivOrNull->isValueUnset("IfSignExtend") &&
3850 Predicate.isSignExtLoad())
3851 return InsnMatcher;
3852
3853 // No check required. We already did it by swapping the opcode.
3854 if (!SrcGIEquivOrNull->isValueUnset("IfZeroExtend") &&
3855 Predicate.isZeroExtLoad())
3856 return InsnMatcher;
3857
3858 // No check required. G_STORE by itself is a non-extending store.
3859 if (Predicate.isNonTruncStore())
3860 return InsnMatcher;
3861
3862 if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
3863 if (Predicate.getMemoryVT() != nullptr) {
3864 auto MemSizeInBits = getMemSizeBitsFromPredicate(Predicate);
3865 if (!MemSizeInBits)
3866 return failedImport("MemVT could not be converted to LLT");
3867
3868 InsnMatcher.addPredicate<MemorySizePredicateMatcher>(0,
3869 *MemSizeInBits / 8);
3870 return InsnMatcher;
3871 }
3872 }
3873
3874 if (Predicate.isLoad() || Predicate.isStore()) {
3875 // No check required. A G_LOAD/G_STORE is an unindexed load.
3876 if (Predicate.isUnindexed())
3877 return InsnMatcher;
3878 }
3879
3880 if (Predicate.isAtomic()) {
3881 if (Predicate.isAtomicOrderingMonotonic()) {
3882 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Monotonic");
3883 return InsnMatcher;
3884 }
3885 if (Predicate.isAtomicOrderingAcquire()) {
3886 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Acquire");
3887 return InsnMatcher;
3888 }
3889 if (Predicate.isAtomicOrderingRelease()) {
3890 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Release");
3891 return InsnMatcher;
3892 }
3893 if (Predicate.isAtomicOrderingAcquireRelease()) {
3894 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3895 "AcquireRelease");
3896 return InsnMatcher;
3897 }
3898 if (Predicate.isAtomicOrderingSequentiallyConsistent()) {
3899 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3900 "SequentiallyConsistent");
3901 return InsnMatcher;
3902 }
3903 }
3904
3905 if (Predicate.isAtomicOrderingAcquireOrStronger()) {
3906 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3907 "Acquire", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
3908 return InsnMatcher;
3909 }
3910 if (Predicate.isAtomicOrderingWeakerThanAcquire()) {
3911 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3912 "Acquire", AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
3913 return InsnMatcher;
3914 }
3915
3916 if (Predicate.isAtomicOrderingReleaseOrStronger()) {
3917 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3918 "Release", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
3919 return InsnMatcher;
3920 }
3921 if (Predicate.isAtomicOrderingWeakerThanRelease()) {
3922 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3923 "Release", AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
3924 return InsnMatcher;
3925 }
3926 HasAddedMatcher = false;
3927 return InsnMatcher;
3928 }
3929
createAndImportSelDAGMatcher(RuleMatcher & Rule,InstructionMatcher & InsnMatcher,const TreePatternNode * Src,unsigned & TempOpIdx)3930 Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher(
3931 RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
3932 const TreePatternNode *Src, unsigned &TempOpIdx) {
3933 Record *SrcGIEquivOrNull = nullptr;
3934 const CodeGenInstruction *SrcGIOrNull = nullptr;
3935
3936 // Start with the defined operands (i.e., the results of the root operator).
3937 if (Src->getExtTypes().size() > 1)
3938 return failedImport("Src pattern has multiple results");
3939
3940 if (Src->isLeaf()) {
3941 Init *SrcInit = Src->getLeafValue();
3942 if (isa<IntInit>(SrcInit)) {
3943 InsnMatcher.addPredicate<InstructionOpcodeMatcher>(
3944 &Target.getInstruction(RK.getDef("G_CONSTANT")));
3945 } else
3946 return failedImport(
3947 "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
3948 } else {
3949 SrcGIEquivOrNull = findNodeEquiv(Src->getOperator());
3950 if (!SrcGIEquivOrNull)
3951 return failedImport("Pattern operator lacks an equivalent Instruction" +
3952 explainOperator(Src->getOperator()));
3953 SrcGIOrNull = getEquivNode(*SrcGIEquivOrNull, Src);
3954
3955 // The operators look good: match the opcode
3956 InsnMatcher.addPredicate<InstructionOpcodeMatcher>(SrcGIOrNull);
3957 }
3958
3959 unsigned OpIdx = 0;
3960 for (const TypeSetByHwMode &VTy : Src->getExtTypes()) {
3961 // Results don't have a name unless they are the root node. The caller will
3962 // set the name if appropriate.
3963 OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
3964 if (auto Error = OM.addTypeCheckPredicate(VTy, false /* OperandIsAPointer */))
3965 return failedImport(toString(std::move(Error)) +
3966 " for result of Src pattern operator");
3967 }
3968
3969 for (const TreePredicateCall &Call : Src->getPredicateCalls()) {
3970 const TreePredicateFn &Predicate = Call.Fn;
3971 bool HasAddedBuiltinMatcher = true;
3972 if (Predicate.isAlwaysTrue())
3973 continue;
3974
3975 if (Predicate.isImmediatePattern()) {
3976 InsnMatcher.addPredicate<InstructionImmPredicateMatcher>(Predicate);
3977 continue;
3978 }
3979
3980 auto InsnMatcherOrError = addBuiltinPredicates(
3981 SrcGIEquivOrNull, Predicate, InsnMatcher, HasAddedBuiltinMatcher);
3982 if (auto Error = InsnMatcherOrError.takeError())
3983 return std::move(Error);
3984
3985 if (Predicate.hasGISelPredicateCode()) {
3986 if (Predicate.usesOperands()) {
3987 assert(WaitingForNamedOperands == 0 &&
3988 "previous predicate didn't find all operands or "
3989 "nested predicate that uses operands");
3990 TreePattern *TP = Predicate.getOrigPatFragRecord();
3991 WaitingForNamedOperands = TP->getNumArgs();
3992 for (unsigned i = 0; i < WaitingForNamedOperands; ++i)
3993 StoreIdxForName[getScopedName(Call.Scope, TP->getArgName(i))] = i;
3994 }
3995 InsnMatcher.addPredicate<GenericInstructionPredicateMatcher>(Predicate);
3996 continue;
3997 }
3998 if (!HasAddedBuiltinMatcher) {
3999 return failedImport("Src pattern child has predicate (" +
4000 explainPredicates(Src) + ")");
4001 }
4002 }
4003
4004 bool IsAtomic = false;
4005 if (SrcGIEquivOrNull && SrcGIEquivOrNull->getValueAsBit("CheckMMOIsNonAtomic"))
4006 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("NotAtomic");
4007 else if (SrcGIEquivOrNull && SrcGIEquivOrNull->getValueAsBit("CheckMMOIsAtomic")) {
4008 IsAtomic = true;
4009 InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
4010 "Unordered", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
4011 }
4012
4013 if (Src->isLeaf()) {
4014 Init *SrcInit = Src->getLeafValue();
4015 if (IntInit *SrcIntInit = dyn_cast<IntInit>(SrcInit)) {
4016 OperandMatcher &OM =
4017 InsnMatcher.addOperand(OpIdx++, Src->getName(), TempOpIdx);
4018 OM.addPredicate<LiteralIntOperandMatcher>(SrcIntInit->getValue());
4019 } else
4020 return failedImport(
4021 "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
4022 } else {
4023 assert(SrcGIOrNull &&
4024 "Expected to have already found an equivalent Instruction");
4025 if (SrcGIOrNull->TheDef->getName() == "G_CONSTANT" ||
4026 SrcGIOrNull->TheDef->getName() == "G_FCONSTANT") {
4027 // imm/fpimm still have operands but we don't need to do anything with it
4028 // here since we don't support ImmLeaf predicates yet. However, we still
4029 // need to note the hidden operand to get GIM_CheckNumOperands correct.
4030 InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
4031 return InsnMatcher;
4032 }
4033
4034 // Special case because the operand order is changed from setcc. The
4035 // predicate operand needs to be swapped from the last operand to the first
4036 // source.
4037
4038 unsigned NumChildren = Src->getNumChildren();
4039 bool IsFCmp = SrcGIOrNull->TheDef->getName() == "G_FCMP";
4040
4041 if (IsFCmp || SrcGIOrNull->TheDef->getName() == "G_ICMP") {
4042 TreePatternNode *SrcChild = Src->getChild(NumChildren - 1);
4043 if (SrcChild->isLeaf()) {
4044 DefInit *DI = dyn_cast<DefInit>(SrcChild->getLeafValue());
4045 Record *CCDef = DI ? DI->getDef() : nullptr;
4046 if (!CCDef || !CCDef->isSubClassOf("CondCode"))
4047 return failedImport("Unable to handle CondCode");
4048
4049 OperandMatcher &OM =
4050 InsnMatcher.addOperand(OpIdx++, SrcChild->getName(), TempOpIdx);
4051 StringRef PredType = IsFCmp ? CCDef->getValueAsString("FCmpPredicate") :
4052 CCDef->getValueAsString("ICmpPredicate");
4053
4054 if (!PredType.empty()) {
4055 OM.addPredicate<CmpPredicateOperandMatcher>(std::string(PredType));
4056 // Process the other 2 operands normally.
4057 --NumChildren;
4058 }
4059 }
4060 }
4061
4062 // Hack around an unfortunate mistake in how atomic store (and really
4063 // atomicrmw in general) operands were ordered. A ISD::STORE used the order
4064 // <stored value>, <pointer> order. ISD::ATOMIC_STORE used the opposite,
4065 // <pointer>, <stored value>. In GlobalISel there's just the one store
4066 // opcode, so we need to swap the operands here to get the right type check.
4067 if (IsAtomic && SrcGIOrNull->TheDef->getName() == "G_STORE") {
4068 assert(NumChildren == 2 && "wrong operands for atomic store");
4069
4070 TreePatternNode *PtrChild = Src->getChild(0);
4071 TreePatternNode *ValueChild = Src->getChild(1);
4072
4073 if (auto Error = importChildMatcher(Rule, InsnMatcher, PtrChild, true,
4074 false, 1, TempOpIdx))
4075 return std::move(Error);
4076
4077 if (auto Error = importChildMatcher(Rule, InsnMatcher, ValueChild, false,
4078 false, 0, TempOpIdx))
4079 return std::move(Error);
4080 return InsnMatcher;
4081 }
4082
4083 // Match the used operands (i.e. the children of the operator).
4084 bool IsIntrinsic =
4085 SrcGIOrNull->TheDef->getName() == "G_INTRINSIC" ||
4086 SrcGIOrNull->TheDef->getName() == "G_INTRINSIC_W_SIDE_EFFECTS";
4087 const CodeGenIntrinsic *II = Src->getIntrinsicInfo(CGP);
4088 if (IsIntrinsic && !II)
4089 return failedImport("Expected IntInit containing intrinsic ID)");
4090
4091 for (unsigned i = 0; i != NumChildren; ++i) {
4092 TreePatternNode *SrcChild = Src->getChild(i);
4093
4094 // We need to determine the meaning of a literal integer based on the
4095 // context. If this is a field required to be an immediate (such as an
4096 // immarg intrinsic argument), the required predicates are different than
4097 // a constant which may be materialized in a register. If we have an
4098 // argument that is required to be an immediate, we should not emit an LLT
4099 // type check, and should not be looking for a G_CONSTANT defined
4100 // register.
4101 bool OperandIsImmArg = SrcGIOrNull->isOperandImmArg(i);
4102
4103 // SelectionDAG allows pointers to be represented with iN since it doesn't
4104 // distinguish between pointers and integers but they are different types in GlobalISel.
4105 // Coerce integers to pointers to address space 0 if the context indicates a pointer.
4106 //
4107 bool OperandIsAPointer = SrcGIOrNull->isOperandAPointer(i);
4108
4109 if (IsIntrinsic) {
4110 // For G_INTRINSIC/G_INTRINSIC_W_SIDE_EFFECTS, the operand immediately
4111 // following the defs is an intrinsic ID.
4112 if (i == 0) {
4113 OperandMatcher &OM =
4114 InsnMatcher.addOperand(OpIdx++, SrcChild->getName(), TempOpIdx);
4115 OM.addPredicate<IntrinsicIDOperandMatcher>(II);
4116 continue;
4117 }
4118
4119 // We have to check intrinsics for llvm_anyptr_ty and immarg parameters.
4120 //
4121 // Note that we have to look at the i-1th parameter, because we don't
4122 // have the intrinsic ID in the intrinsic's parameter list.
4123 OperandIsAPointer |= II->isParamAPointer(i - 1);
4124 OperandIsImmArg |= II->isParamImmArg(i - 1);
4125 }
4126
4127 if (auto Error =
4128 importChildMatcher(Rule, InsnMatcher, SrcChild, OperandIsAPointer,
4129 OperandIsImmArg, OpIdx++, TempOpIdx))
4130 return std::move(Error);
4131 }
4132 }
4133
4134 return InsnMatcher;
4135 }
4136
importComplexPatternOperandMatcher(OperandMatcher & OM,Record * R,unsigned & TempOpIdx) const4137 Error GlobalISelEmitter::importComplexPatternOperandMatcher(
4138 OperandMatcher &OM, Record *R, unsigned &TempOpIdx) const {
4139 const auto &ComplexPattern = ComplexPatternEquivs.find(R);
4140 if (ComplexPattern == ComplexPatternEquivs.end())
4141 return failedImport("SelectionDAG ComplexPattern (" + R->getName() +
4142 ") not mapped to GlobalISel");
4143
4144 OM.addPredicate<ComplexPatternOperandMatcher>(OM, *ComplexPattern->second);
4145 TempOpIdx++;
4146 return Error::success();
4147 }
4148
4149 // Get the name to use for a pattern operand. For an anonymous physical register
4150 // input, this should use the register name.
getSrcChildName(const TreePatternNode * SrcChild,Record * & PhysReg)4151 static StringRef getSrcChildName(const TreePatternNode *SrcChild,
4152 Record *&PhysReg) {
4153 StringRef SrcChildName = SrcChild->getName();
4154 if (SrcChildName.empty() && SrcChild->isLeaf()) {
4155 if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
4156 auto *ChildRec = ChildDefInit->getDef();
4157 if (ChildRec->isSubClassOf("Register")) {
4158 SrcChildName = ChildRec->getName();
4159 PhysReg = ChildRec;
4160 }
4161 }
4162 }
4163
4164 return SrcChildName;
4165 }
4166
importChildMatcher(RuleMatcher & Rule,InstructionMatcher & InsnMatcher,const TreePatternNode * SrcChild,bool OperandIsAPointer,bool OperandIsImmArg,unsigned OpIdx,unsigned & TempOpIdx)4167 Error GlobalISelEmitter::importChildMatcher(
4168 RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
4169 const TreePatternNode *SrcChild, bool OperandIsAPointer,
4170 bool OperandIsImmArg, unsigned OpIdx, unsigned &TempOpIdx) {
4171
4172 Record *PhysReg = nullptr;
4173 std::string SrcChildName = std::string(getSrcChildName(SrcChild, PhysReg));
4174 if (!SrcChild->isLeaf() &&
4175 SrcChild->getOperator()->isSubClassOf("ComplexPattern")) {
4176 // The "name" of a non-leaf complex pattern (MY_PAT $op1, $op2) is
4177 // "MY_PAT:op1:op2" and the ones with same "name" represent same operand.
4178 std::string PatternName = std::string(SrcChild->getOperator()->getName());
4179 for (unsigned i = 0; i < SrcChild->getNumChildren(); ++i) {
4180 PatternName += ":";
4181 PatternName += SrcChild->getChild(i)->getName();
4182 }
4183 SrcChildName = PatternName;
4184 }
4185
4186 OperandMatcher &OM =
4187 PhysReg ? InsnMatcher.addPhysRegInput(PhysReg, OpIdx, TempOpIdx)
4188 : InsnMatcher.addOperand(OpIdx, SrcChildName, TempOpIdx);
4189 if (OM.isSameAsAnotherOperand())
4190 return Error::success();
4191
4192 ArrayRef<TypeSetByHwMode> ChildTypes = SrcChild->getExtTypes();
4193 if (ChildTypes.size() != 1)
4194 return failedImport("Src pattern child has multiple results");
4195
4196 // Check MBB's before the type check since they are not a known type.
4197 if (!SrcChild->isLeaf()) {
4198 if (SrcChild->getOperator()->isSubClassOf("SDNode")) {
4199 auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator());
4200 if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
4201 OM.addPredicate<MBBOperandMatcher>();
4202 return Error::success();
4203 }
4204 if (SrcChild->getOperator()->getName() == "timm") {
4205 OM.addPredicate<ImmOperandMatcher>();
4206
4207 // Add predicates, if any
4208 for (const TreePredicateCall &Call : SrcChild->getPredicateCalls()) {
4209 const TreePredicateFn &Predicate = Call.Fn;
4210
4211 // Only handle immediate patterns for now
4212 if (Predicate.isImmediatePattern()) {
4213 OM.addPredicate<OperandImmPredicateMatcher>(Predicate);
4214 }
4215 }
4216
4217 return Error::success();
4218 }
4219 }
4220 }
4221
4222 // Immediate arguments have no meaningful type to check as they don't have
4223 // registers.
4224 if (!OperandIsImmArg) {
4225 if (auto Error =
4226 OM.addTypeCheckPredicate(ChildTypes.front(), OperandIsAPointer))
4227 return failedImport(toString(std::move(Error)) + " for Src operand (" +
4228 to_string(*SrcChild) + ")");
4229 }
4230
4231 // Check for nested instructions.
4232 if (!SrcChild->isLeaf()) {
4233 if (SrcChild->getOperator()->isSubClassOf("ComplexPattern")) {
4234 // When a ComplexPattern is used as an operator, it should do the same
4235 // thing as when used as a leaf. However, the children of the operator
4236 // name the sub-operands that make up the complex operand and we must
4237 // prepare to reference them in the renderer too.
4238 unsigned RendererID = TempOpIdx;
4239 if (auto Error = importComplexPatternOperandMatcher(
4240 OM, SrcChild->getOperator(), TempOpIdx))
4241 return Error;
4242
4243 for (unsigned i = 0, e = SrcChild->getNumChildren(); i != e; ++i) {
4244 auto *SubOperand = SrcChild->getChild(i);
4245 if (!SubOperand->getName().empty()) {
4246 if (auto Error = Rule.defineComplexSubOperand(
4247 SubOperand->getName(), SrcChild->getOperator(), RendererID, i,
4248 SrcChildName))
4249 return Error;
4250 }
4251 }
4252
4253 return Error::success();
4254 }
4255
4256 auto MaybeInsnOperand = OM.addPredicate<InstructionOperandMatcher>(
4257 InsnMatcher.getRuleMatcher(), SrcChild->getName());
4258 if (!MaybeInsnOperand.hasValue()) {
4259 // This isn't strictly true. If the user were to provide exactly the same
4260 // matchers as the original operand then we could allow it. However, it's
4261 // simpler to not permit the redundant specification.
4262 return failedImport("Nested instruction cannot be the same as another operand");
4263 }
4264
4265 // Map the node to a gMIR instruction.
4266 InstructionOperandMatcher &InsnOperand = **MaybeInsnOperand;
4267 auto InsnMatcherOrError = createAndImportSelDAGMatcher(
4268 Rule, InsnOperand.getInsnMatcher(), SrcChild, TempOpIdx);
4269 if (auto Error = InsnMatcherOrError.takeError())
4270 return Error;
4271
4272 return Error::success();
4273 }
4274
4275 if (SrcChild->hasAnyPredicate())
4276 return failedImport("Src pattern child has unsupported predicate");
4277
4278 // Check for constant immediates.
4279 if (auto *ChildInt = dyn_cast<IntInit>(SrcChild->getLeafValue())) {
4280 if (OperandIsImmArg) {
4281 // Checks for argument directly in operand list
4282 OM.addPredicate<LiteralIntOperandMatcher>(ChildInt->getValue());
4283 } else {
4284 // Checks for materialized constant
4285 OM.addPredicate<ConstantIntOperandMatcher>(ChildInt->getValue());
4286 }
4287 return Error::success();
4288 }
4289
4290 // Check for def's like register classes or ComplexPattern's.
4291 if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
4292 auto *ChildRec = ChildDefInit->getDef();
4293
4294 if (WaitingForNamedOperands) {
4295 auto PA = SrcChild->getNamesAsPredicateArg().begin();
4296 std::string Name = getScopedName(PA->getScope(), PA->getIdentifier());
4297 OM.addPredicate<RecordNamedOperandMatcher>(StoreIdxForName[Name], Name);
4298 --WaitingForNamedOperands;
4299 }
4300
4301 // Check for register classes.
4302 if (ChildRec->isSubClassOf("RegisterClass") ||
4303 ChildRec->isSubClassOf("RegisterOperand")) {
4304 OM.addPredicate<RegisterBankOperandMatcher>(
4305 Target.getRegisterClass(getInitValueAsRegClass(ChildDefInit)));
4306 return Error::success();
4307 }
4308
4309 if (ChildRec->isSubClassOf("Register")) {
4310 // This just be emitted as a copy to the specific register.
4311 ValueTypeByHwMode VT = ChildTypes.front().getValueTypeByHwMode();
4312 const CodeGenRegisterClass *RC
4313 = CGRegs.getMinimalPhysRegClass(ChildRec, &VT);
4314 if (!RC) {
4315 return failedImport(
4316 "Could not determine physical register class of pattern source");
4317 }
4318
4319 OM.addPredicate<RegisterBankOperandMatcher>(*RC);
4320 return Error::success();
4321 }
4322
4323 // Check for ValueType.
4324 if (ChildRec->isSubClassOf("ValueType")) {
4325 // We already added a type check as standard practice so this doesn't need
4326 // to do anything.
4327 return Error::success();
4328 }
4329
4330 // Check for ComplexPattern's.
4331 if (ChildRec->isSubClassOf("ComplexPattern"))
4332 return importComplexPatternOperandMatcher(OM, ChildRec, TempOpIdx);
4333
4334 if (ChildRec->isSubClassOf("ImmLeaf")) {
4335 return failedImport(
4336 "Src pattern child def is an unsupported tablegen class (ImmLeaf)");
4337 }
4338
4339 // Place holder for SRCVALUE nodes. Nothing to do here.
4340 if (ChildRec->getName() == "srcvalue")
4341 return Error::success();
4342
4343 const bool ImmAllOnesV = ChildRec->getName() == "immAllOnesV";
4344 if (ImmAllOnesV || ChildRec->getName() == "immAllZerosV") {
4345 auto MaybeInsnOperand = OM.addPredicate<InstructionOperandMatcher>(
4346 InsnMatcher.getRuleMatcher(), SrcChild->getName(), false);
4347 InstructionOperandMatcher &InsnOperand = **MaybeInsnOperand;
4348
4349 ValueTypeByHwMode VTy = ChildTypes.front().getValueTypeByHwMode();
4350
4351 const CodeGenInstruction &BuildVector
4352 = Target.getInstruction(RK.getDef("G_BUILD_VECTOR"));
4353 const CodeGenInstruction &BuildVectorTrunc
4354 = Target.getInstruction(RK.getDef("G_BUILD_VECTOR_TRUNC"));
4355
4356 // Treat G_BUILD_VECTOR as the canonical opcode, and G_BUILD_VECTOR_TRUNC
4357 // as an alternative.
4358 InsnOperand.getInsnMatcher().addPredicate<InstructionOpcodeMatcher>(
4359 makeArrayRef({&BuildVector, &BuildVectorTrunc}));
4360
4361 // TODO: Handle both G_BUILD_VECTOR and G_BUILD_VECTOR_TRUNC We could
4362 // theoretically not emit any opcode check, but getOpcodeMatcher currently
4363 // has to succeed.
4364 OperandMatcher &OM =
4365 InsnOperand.getInsnMatcher().addOperand(0, "", TempOpIdx);
4366 if (auto Error =
4367 OM.addTypeCheckPredicate(VTy, false /* OperandIsAPointer */))
4368 return failedImport(toString(std::move(Error)) +
4369 " for result of Src pattern operator");
4370
4371 InsnOperand.getInsnMatcher().addPredicate<VectorSplatImmPredicateMatcher>(
4372 ImmAllOnesV ? VectorSplatImmPredicateMatcher::AllOnes
4373 : VectorSplatImmPredicateMatcher::AllZeros);
4374 return Error::success();
4375 }
4376
4377 return failedImport(
4378 "Src pattern child def is an unsupported tablegen class");
4379 }
4380
4381 return failedImport("Src pattern child is an unsupported kind");
4382 }
4383
importExplicitUseRenderer(action_iterator InsertPt,RuleMatcher & Rule,BuildMIAction & DstMIBuilder,TreePatternNode * DstChild)4384 Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderer(
4385 action_iterator InsertPt, RuleMatcher &Rule, BuildMIAction &DstMIBuilder,
4386 TreePatternNode *DstChild) {
4387
4388 const auto &SubOperand = Rule.getComplexSubOperand(DstChild->getName());
4389 if (SubOperand.hasValue()) {
4390 DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
4391 *std::get<0>(*SubOperand), DstChild->getName(),
4392 std::get<1>(*SubOperand), std::get<2>(*SubOperand));
4393 return InsertPt;
4394 }
4395
4396 if (!DstChild->isLeaf()) {
4397 if (DstChild->getOperator()->isSubClassOf("SDNodeXForm")) {
4398 auto Child = DstChild->getChild(0);
4399 auto I = SDNodeXFormEquivs.find(DstChild->getOperator());
4400 if (I != SDNodeXFormEquivs.end()) {
4401 Record *XFormOpc = DstChild->getOperator()->getValueAsDef("Opcode");
4402 if (XFormOpc->getName() == "timm") {
4403 // If this is a TargetConstant, there won't be a corresponding
4404 // instruction to transform. Instead, this will refer directly to an
4405 // operand in an instruction's operand list.
4406 DstMIBuilder.addRenderer<CustomOperandRenderer>(*I->second,
4407 Child->getName());
4408 } else {
4409 DstMIBuilder.addRenderer<CustomRenderer>(*I->second,
4410 Child->getName());
4411 }
4412
4413 return InsertPt;
4414 }
4415 return failedImport("SDNodeXForm " + Child->getName() +
4416 " has no custom renderer");
4417 }
4418
4419 // We accept 'bb' here. It's an operator because BasicBlockSDNode isn't
4420 // inline, but in MI it's just another operand.
4421 if (DstChild->getOperator()->isSubClassOf("SDNode")) {
4422 auto &ChildSDNI = CGP.getSDNodeInfo(DstChild->getOperator());
4423 if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
4424 DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
4425 return InsertPt;
4426 }
4427 }
4428
4429 // Similarly, imm is an operator in TreePatternNode's view but must be
4430 // rendered as operands.
4431 // FIXME: The target should be able to choose sign-extended when appropriate
4432 // (e.g. on Mips).
4433 if (DstChild->getOperator()->getName() == "timm") {
4434 DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
4435 return InsertPt;
4436 } else if (DstChild->getOperator()->getName() == "imm") {
4437 DstMIBuilder.addRenderer<CopyConstantAsImmRenderer>(DstChild->getName());
4438 return InsertPt;
4439 } else if (DstChild->getOperator()->getName() == "fpimm") {
4440 DstMIBuilder.addRenderer<CopyFConstantAsFPImmRenderer>(
4441 DstChild->getName());
4442 return InsertPt;
4443 }
4444
4445 if (DstChild->getOperator()->isSubClassOf("Instruction")) {
4446 auto OpTy = getInstResultType(DstChild);
4447 if (!OpTy)
4448 return OpTy.takeError();
4449
4450 unsigned TempRegID = Rule.allocateTempRegID();
4451 InsertPt = Rule.insertAction<MakeTempRegisterAction>(
4452 InsertPt, *OpTy, TempRegID);
4453 DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
4454
4455 auto InsertPtOrError = createAndImportSubInstructionRenderer(
4456 ++InsertPt, Rule, DstChild, TempRegID);
4457 if (auto Error = InsertPtOrError.takeError())
4458 return std::move(Error);
4459 return InsertPtOrError.get();
4460 }
4461
4462 return failedImport("Dst pattern child isn't a leaf node or an MBB" + llvm::to_string(*DstChild));
4463 }
4464
4465 // It could be a specific immediate in which case we should just check for
4466 // that immediate.
4467 if (const IntInit *ChildIntInit =
4468 dyn_cast<IntInit>(DstChild->getLeafValue())) {
4469 DstMIBuilder.addRenderer<ImmRenderer>(ChildIntInit->getValue());
4470 return InsertPt;
4471 }
4472
4473 // Otherwise, we're looking for a bog-standard RegisterClass operand.
4474 if (auto *ChildDefInit = dyn_cast<DefInit>(DstChild->getLeafValue())) {
4475 auto *ChildRec = ChildDefInit->getDef();
4476
4477 ArrayRef<TypeSetByHwMode> ChildTypes = DstChild->getExtTypes();
4478 if (ChildTypes.size() != 1)
4479 return failedImport("Dst pattern child has multiple results");
4480
4481 Optional<LLTCodeGen> OpTyOrNone = None;
4482 if (ChildTypes.front().isMachineValueType())
4483 OpTyOrNone = MVTToLLT(ChildTypes.front().getMachineValueType().SimpleTy);
4484 if (!OpTyOrNone)
4485 return failedImport("Dst operand has an unsupported type");
4486
4487 if (ChildRec->isSubClassOf("Register")) {
4488 DstMIBuilder.addRenderer<AddRegisterRenderer>(Target, ChildRec);
4489 return InsertPt;
4490 }
4491
4492 if (ChildRec->isSubClassOf("RegisterClass") ||
4493 ChildRec->isSubClassOf("RegisterOperand") ||
4494 ChildRec->isSubClassOf("ValueType")) {
4495 if (ChildRec->isSubClassOf("RegisterOperand") &&
4496 !ChildRec->isValueUnset("GIZeroRegister")) {
4497 DstMIBuilder.addRenderer<CopyOrAddZeroRegRenderer>(
4498 DstChild->getName(), ChildRec->getValueAsDef("GIZeroRegister"));
4499 return InsertPt;
4500 }
4501
4502 DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
4503 return InsertPt;
4504 }
4505
4506 if (ChildRec->isSubClassOf("SubRegIndex")) {
4507 CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(ChildRec);
4508 DstMIBuilder.addRenderer<ImmRenderer>(SubIdx->EnumValue);
4509 return InsertPt;
4510 }
4511
4512 if (ChildRec->isSubClassOf("ComplexPattern")) {
4513 const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
4514 if (ComplexPattern == ComplexPatternEquivs.end())
4515 return failedImport(
4516 "SelectionDAG ComplexPattern not mapped to GlobalISel");
4517
4518 const OperandMatcher &OM = Rule.getOperandMatcher(DstChild->getName());
4519 DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
4520 *ComplexPattern->second, DstChild->getName(),
4521 OM.getAllocatedTemporariesBaseID());
4522 return InsertPt;
4523 }
4524
4525 return failedImport(
4526 "Dst pattern child def is an unsupported tablegen class");
4527 }
4528 return failedImport("Dst pattern child is an unsupported kind");
4529 }
4530
createAndImportInstructionRenderer(RuleMatcher & M,InstructionMatcher & InsnMatcher,const TreePatternNode * Src,const TreePatternNode * Dst)4531 Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
4532 RuleMatcher &M, InstructionMatcher &InsnMatcher, const TreePatternNode *Src,
4533 const TreePatternNode *Dst) {
4534 auto InsertPtOrError = createInstructionRenderer(M.actions_end(), M, Dst);
4535 if (auto Error = InsertPtOrError.takeError())
4536 return std::move(Error);
4537
4538 action_iterator InsertPt = InsertPtOrError.get();
4539 BuildMIAction &DstMIBuilder = *static_cast<BuildMIAction *>(InsertPt->get());
4540
4541 for (auto PhysInput : InsnMatcher.getPhysRegInputs()) {
4542 InsertPt = M.insertAction<BuildMIAction>(
4543 InsertPt, M.allocateOutputInsnID(),
4544 &Target.getInstruction(RK.getDef("COPY")));
4545 BuildMIAction &CopyToPhysRegMIBuilder =
4546 *static_cast<BuildMIAction *>(InsertPt->get());
4547 CopyToPhysRegMIBuilder.addRenderer<AddRegisterRenderer>(Target,
4548 PhysInput.first,
4549 true);
4550 CopyToPhysRegMIBuilder.addRenderer<CopyPhysRegRenderer>(PhysInput.first);
4551 }
4552
4553 if (auto Error = importExplicitDefRenderers(InsertPt, M, DstMIBuilder, Dst)
4554 .takeError())
4555 return std::move(Error);
4556
4557 if (auto Error = importExplicitUseRenderers(InsertPt, M, DstMIBuilder, Dst)
4558 .takeError())
4559 return std::move(Error);
4560
4561 return DstMIBuilder;
4562 }
4563
4564 Expected<action_iterator>
createAndImportSubInstructionRenderer(const action_iterator InsertPt,RuleMatcher & M,const TreePatternNode * Dst,unsigned TempRegID)4565 GlobalISelEmitter::createAndImportSubInstructionRenderer(
4566 const action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst,
4567 unsigned TempRegID) {
4568 auto InsertPtOrError = createInstructionRenderer(InsertPt, M, Dst);
4569
4570 // TODO: Assert there's exactly one result.
4571
4572 if (auto Error = InsertPtOrError.takeError())
4573 return std::move(Error);
4574
4575 BuildMIAction &DstMIBuilder =
4576 *static_cast<BuildMIAction *>(InsertPtOrError.get()->get());
4577
4578 // Assign the result to TempReg.
4579 DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID, true);
4580
4581 InsertPtOrError =
4582 importExplicitUseRenderers(InsertPtOrError.get(), M, DstMIBuilder, Dst);
4583 if (auto Error = InsertPtOrError.takeError())
4584 return std::move(Error);
4585
4586 // We need to make sure that when we import an INSERT_SUBREG as a
4587 // subinstruction that it ends up being constrained to the correct super
4588 // register and subregister classes.
4589 auto OpName = Target.getInstruction(Dst->getOperator()).TheDef->getName();
4590 if (OpName == "INSERT_SUBREG") {
4591 auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
4592 if (!SubClass)
4593 return failedImport(
4594 "Cannot infer register class from INSERT_SUBREG operand #1");
4595 Optional<const CodeGenRegisterClass *> SuperClass =
4596 inferSuperRegisterClassForNode(Dst->getExtType(0), Dst->getChild(0),
4597 Dst->getChild(2));
4598 if (!SuperClass)
4599 return failedImport(
4600 "Cannot infer register class for INSERT_SUBREG operand #0");
4601 // The destination and the super register source of an INSERT_SUBREG must
4602 // be the same register class.
4603 M.insertAction<ConstrainOperandToRegClassAction>(
4604 InsertPt, DstMIBuilder.getInsnID(), 0, **SuperClass);
4605 M.insertAction<ConstrainOperandToRegClassAction>(
4606 InsertPt, DstMIBuilder.getInsnID(), 1, **SuperClass);
4607 M.insertAction<ConstrainOperandToRegClassAction>(
4608 InsertPt, DstMIBuilder.getInsnID(), 2, **SubClass);
4609 return InsertPtOrError.get();
4610 }
4611
4612 if (OpName == "EXTRACT_SUBREG") {
4613 // EXTRACT_SUBREG selects into a subregister COPY but unlike most
4614 // instructions, the result register class is controlled by the
4615 // subregisters of the operand. As a result, we must constrain the result
4616 // class rather than check that it's already the right one.
4617 auto SuperClass = inferRegClassFromPattern(Dst->getChild(0));
4618 if (!SuperClass)
4619 return failedImport(
4620 "Cannot infer register class from EXTRACT_SUBREG operand #0");
4621
4622 auto SubIdx = inferSubRegIndexForNode(Dst->getChild(1));
4623 if (!SubIdx)
4624 return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
4625
4626 const auto SrcRCDstRCPair =
4627 (*SuperClass)->getMatchingSubClassWithSubRegs(CGRegs, *SubIdx);
4628 assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
4629 M.insertAction<ConstrainOperandToRegClassAction>(
4630 InsertPt, DstMIBuilder.getInsnID(), 0, *SrcRCDstRCPair->second);
4631 M.insertAction<ConstrainOperandToRegClassAction>(
4632 InsertPt, DstMIBuilder.getInsnID(), 1, *SrcRCDstRCPair->first);
4633
4634 // We're done with this pattern! It's eligible for GISel emission; return
4635 // it.
4636 return InsertPtOrError.get();
4637 }
4638
4639 // Similar to INSERT_SUBREG, we also have to handle SUBREG_TO_REG as a
4640 // subinstruction.
4641 if (OpName == "SUBREG_TO_REG") {
4642 auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
4643 if (!SubClass)
4644 return failedImport(
4645 "Cannot infer register class from SUBREG_TO_REG child #1");
4646 auto SuperClass = inferSuperRegisterClass(Dst->getExtType(0),
4647 Dst->getChild(2));
4648 if (!SuperClass)
4649 return failedImport(
4650 "Cannot infer register class for SUBREG_TO_REG operand #0");
4651 M.insertAction<ConstrainOperandToRegClassAction>(
4652 InsertPt, DstMIBuilder.getInsnID(), 0, **SuperClass);
4653 M.insertAction<ConstrainOperandToRegClassAction>(
4654 InsertPt, DstMIBuilder.getInsnID(), 2, **SubClass);
4655 return InsertPtOrError.get();
4656 }
4657
4658 if (OpName == "REG_SEQUENCE") {
4659 auto SuperClass = inferRegClassFromPattern(Dst->getChild(0));
4660 M.insertAction<ConstrainOperandToRegClassAction>(
4661 InsertPt, DstMIBuilder.getInsnID(), 0, **SuperClass);
4662
4663 unsigned Num = Dst->getNumChildren();
4664 for (unsigned I = 1; I != Num; I += 2) {
4665 TreePatternNode *SubRegChild = Dst->getChild(I + 1);
4666
4667 auto SubIdx = inferSubRegIndexForNode(SubRegChild);
4668 if (!SubIdx)
4669 return failedImport("REG_SEQUENCE child is not a subreg index");
4670
4671 const auto SrcRCDstRCPair =
4672 (*SuperClass)->getMatchingSubClassWithSubRegs(CGRegs, *SubIdx);
4673 assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
4674 M.insertAction<ConstrainOperandToRegClassAction>(
4675 InsertPt, DstMIBuilder.getInsnID(), I, *SrcRCDstRCPair->second);
4676 }
4677
4678 return InsertPtOrError.get();
4679 }
4680
4681 M.insertAction<ConstrainOperandsToDefinitionAction>(InsertPt,
4682 DstMIBuilder.getInsnID());
4683 return InsertPtOrError.get();
4684 }
4685
createInstructionRenderer(action_iterator InsertPt,RuleMatcher & M,const TreePatternNode * Dst)4686 Expected<action_iterator> GlobalISelEmitter::createInstructionRenderer(
4687 action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst) {
4688 Record *DstOp = Dst->getOperator();
4689 if (!DstOp->isSubClassOf("Instruction")) {
4690 if (DstOp->isSubClassOf("ValueType"))
4691 return failedImport(
4692 "Pattern operator isn't an instruction (it's a ValueType)");
4693 return failedImport("Pattern operator isn't an instruction");
4694 }
4695 CodeGenInstruction *DstI = &Target.getInstruction(DstOp);
4696
4697 // COPY_TO_REGCLASS is just a copy with a ConstrainOperandToRegClassAction
4698 // attached. Similarly for EXTRACT_SUBREG except that's a subregister copy.
4699 StringRef Name = DstI->TheDef->getName();
4700 if (Name == "COPY_TO_REGCLASS" || Name == "EXTRACT_SUBREG")
4701 DstI = &Target.getInstruction(RK.getDef("COPY"));
4702
4703 return M.insertAction<BuildMIAction>(InsertPt, M.allocateOutputInsnID(),
4704 DstI);
4705 }
4706
importExplicitDefRenderers(action_iterator InsertPt,RuleMatcher & M,BuildMIAction & DstMIBuilder,const TreePatternNode * Dst)4707 Expected<action_iterator> GlobalISelEmitter::importExplicitDefRenderers(
4708 action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
4709 const TreePatternNode *Dst) {
4710 const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
4711 const unsigned NumDefs = DstI->Operands.NumDefs;
4712 if (NumDefs == 0)
4713 return InsertPt;
4714
4715 DstMIBuilder.addRenderer<CopyRenderer>(DstI->Operands[0].Name);
4716
4717 // Some instructions have multiple defs, but are missing a type entry
4718 // (e.g. s_cc_out operands).
4719 if (Dst->getExtTypes().size() < NumDefs)
4720 return failedImport("unhandled discarded def");
4721
4722 // Patterns only handle a single result, so any result after the first is an
4723 // implicitly dead def.
4724 for (unsigned I = 1; I < NumDefs; ++I) {
4725 const TypeSetByHwMode &ExtTy = Dst->getExtType(I);
4726 if (!ExtTy.isMachineValueType())
4727 return failedImport("unsupported typeset");
4728
4729 auto OpTy = MVTToLLT(ExtTy.getMachineValueType().SimpleTy);
4730 if (!OpTy)
4731 return failedImport("unsupported type");
4732
4733 unsigned TempRegID = M.allocateTempRegID();
4734 InsertPt =
4735 M.insertAction<MakeTempRegisterAction>(InsertPt, *OpTy, TempRegID);
4736 DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID, true, nullptr, true);
4737 }
4738
4739 return InsertPt;
4740 }
4741
importExplicitUseRenderers(action_iterator InsertPt,RuleMatcher & M,BuildMIAction & DstMIBuilder,const llvm::TreePatternNode * Dst)4742 Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderers(
4743 action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
4744 const llvm::TreePatternNode *Dst) {
4745 const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
4746 CodeGenInstruction *OrigDstI = &Target.getInstruction(Dst->getOperator());
4747
4748 StringRef Name = OrigDstI->TheDef->getName();
4749 unsigned ExpectedDstINumUses = Dst->getNumChildren();
4750
4751 // EXTRACT_SUBREG needs to use a subregister COPY.
4752 if (Name == "EXTRACT_SUBREG") {
4753 if (!Dst->getChild(1)->isLeaf())
4754 return failedImport("EXTRACT_SUBREG child #1 is not a leaf");
4755 DefInit *SubRegInit = dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue());
4756 if (!SubRegInit)
4757 return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
4758
4759 CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
4760 TreePatternNode *ValChild = Dst->getChild(0);
4761 if (!ValChild->isLeaf()) {
4762 // We really have to handle the source instruction, and then insert a
4763 // copy from the subregister.
4764 auto ExtractSrcTy = getInstResultType(ValChild);
4765 if (!ExtractSrcTy)
4766 return ExtractSrcTy.takeError();
4767
4768 unsigned TempRegID = M.allocateTempRegID();
4769 InsertPt = M.insertAction<MakeTempRegisterAction>(
4770 InsertPt, *ExtractSrcTy, TempRegID);
4771
4772 auto InsertPtOrError = createAndImportSubInstructionRenderer(
4773 ++InsertPt, M, ValChild, TempRegID);
4774 if (auto Error = InsertPtOrError.takeError())
4775 return std::move(Error);
4776
4777 DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID, false, SubIdx);
4778 return InsertPt;
4779 }
4780
4781 // If this is a source operand, this is just a subregister copy.
4782 Record *RCDef = getInitValueAsRegClass(ValChild->getLeafValue());
4783 if (!RCDef)
4784 return failedImport("EXTRACT_SUBREG child #0 could not "
4785 "be coerced to a register class");
4786
4787 CodeGenRegisterClass *RC = CGRegs.getRegClass(RCDef);
4788
4789 const auto SrcRCDstRCPair =
4790 RC->getMatchingSubClassWithSubRegs(CGRegs, SubIdx);
4791 if (SrcRCDstRCPair.hasValue()) {
4792 assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
4793 if (SrcRCDstRCPair->first != RC)
4794 return failedImport("EXTRACT_SUBREG requires an additional COPY");
4795 }
4796
4797 DstMIBuilder.addRenderer<CopySubRegRenderer>(Dst->getChild(0)->getName(),
4798 SubIdx);
4799 return InsertPt;
4800 }
4801
4802 if (Name == "REG_SEQUENCE") {
4803 if (!Dst->getChild(0)->isLeaf())
4804 return failedImport("REG_SEQUENCE child #0 is not a leaf");
4805
4806 Record *RCDef = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
4807 if (!RCDef)
4808 return failedImport("REG_SEQUENCE child #0 could not "
4809 "be coerced to a register class");
4810
4811 if ((ExpectedDstINumUses - 1) % 2 != 0)
4812 return failedImport("Malformed REG_SEQUENCE");
4813
4814 for (unsigned I = 1; I != ExpectedDstINumUses; I += 2) {
4815 TreePatternNode *ValChild = Dst->getChild(I);
4816 TreePatternNode *SubRegChild = Dst->getChild(I + 1);
4817
4818 if (DefInit *SubRegInit =
4819 dyn_cast<DefInit>(SubRegChild->getLeafValue())) {
4820 CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
4821
4822 auto InsertPtOrError =
4823 importExplicitUseRenderer(InsertPt, M, DstMIBuilder, ValChild);
4824 if (auto Error = InsertPtOrError.takeError())
4825 return std::move(Error);
4826 InsertPt = InsertPtOrError.get();
4827 DstMIBuilder.addRenderer<SubRegIndexRenderer>(SubIdx);
4828 }
4829 }
4830
4831 return InsertPt;
4832 }
4833
4834 // Render the explicit uses.
4835 unsigned DstINumUses = OrigDstI->Operands.size() - OrigDstI->Operands.NumDefs;
4836 if (Name == "COPY_TO_REGCLASS") {
4837 DstINumUses--; // Ignore the class constraint.
4838 ExpectedDstINumUses--;
4839 }
4840
4841 // NumResults - This is the number of results produced by the instruction in
4842 // the "outs" list.
4843 unsigned NumResults = OrigDstI->Operands.NumDefs;
4844
4845 // Number of operands we know the output instruction must have. If it is
4846 // variadic, we could have more operands.
4847 unsigned NumFixedOperands = DstI->Operands.size();
4848
4849 // Loop over all of the fixed operands of the instruction pattern, emitting
4850 // code to fill them all in. The node 'N' usually has number children equal to
4851 // the number of input operands of the instruction. However, in cases where
4852 // there are predicate operands for an instruction, we need to fill in the
4853 // 'execute always' values. Match up the node operands to the instruction
4854 // operands to do this.
4855 unsigned Child = 0;
4856
4857 // Similarly to the code in TreePatternNode::ApplyTypeConstraints, count the
4858 // number of operands at the end of the list which have default values.
4859 // Those can come from the pattern if it provides enough arguments, or be
4860 // filled in with the default if the pattern hasn't provided them. But any
4861 // operand with a default value _before_ the last mandatory one will be
4862 // filled in with their defaults unconditionally.
4863 unsigned NonOverridableOperands = NumFixedOperands;
4864 while (NonOverridableOperands > NumResults &&
4865 CGP.operandHasDefault(DstI->Operands[NonOverridableOperands - 1].Rec))
4866 --NonOverridableOperands;
4867
4868 unsigned NumDefaultOps = 0;
4869 for (unsigned I = 0; I != DstINumUses; ++I) {
4870 unsigned InstOpNo = DstI->Operands.NumDefs + I;
4871
4872 // Determine what to emit for this operand.
4873 Record *OperandNode = DstI->Operands[InstOpNo].Rec;
4874
4875 // If the operand has default values, introduce them now.
4876 if (CGP.operandHasDefault(OperandNode) &&
4877 (InstOpNo < NonOverridableOperands || Child >= Dst->getNumChildren())) {
4878 // This is a predicate or optional def operand which the pattern has not
4879 // overridden, or which we aren't letting it override; emit the 'default
4880 // ops' operands.
4881
4882 const CGIOperandList::OperandInfo &DstIOperand = DstI->Operands[InstOpNo];
4883 DagInit *DefaultOps = DstIOperand.Rec->getValueAsDag("DefaultOps");
4884 if (auto Error = importDefaultOperandRenderers(
4885 InsertPt, M, DstMIBuilder, DefaultOps))
4886 return std::move(Error);
4887 ++NumDefaultOps;
4888 continue;
4889 }
4890
4891 auto InsertPtOrError = importExplicitUseRenderer(InsertPt, M, DstMIBuilder,
4892 Dst->getChild(Child));
4893 if (auto Error = InsertPtOrError.takeError())
4894 return std::move(Error);
4895 InsertPt = InsertPtOrError.get();
4896 ++Child;
4897 }
4898
4899 if (NumDefaultOps + ExpectedDstINumUses != DstINumUses)
4900 return failedImport("Expected " + llvm::to_string(DstINumUses) +
4901 " used operands but found " +
4902 llvm::to_string(ExpectedDstINumUses) +
4903 " explicit ones and " + llvm::to_string(NumDefaultOps) +
4904 " default ones");
4905
4906 return InsertPt;
4907 }
4908
importDefaultOperandRenderers(action_iterator InsertPt,RuleMatcher & M,BuildMIAction & DstMIBuilder,DagInit * DefaultOps) const4909 Error GlobalISelEmitter::importDefaultOperandRenderers(
4910 action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
4911 DagInit *DefaultOps) const {
4912 for (const auto *DefaultOp : DefaultOps->getArgs()) {
4913 Optional<LLTCodeGen> OpTyOrNone = None;
4914
4915 // Look through ValueType operators.
4916 if (const DagInit *DefaultDagOp = dyn_cast<DagInit>(DefaultOp)) {
4917 if (const DefInit *DefaultDagOperator =
4918 dyn_cast<DefInit>(DefaultDagOp->getOperator())) {
4919 if (DefaultDagOperator->getDef()->isSubClassOf("ValueType")) {
4920 OpTyOrNone = MVTToLLT(getValueType(
4921 DefaultDagOperator->getDef()));
4922 DefaultOp = DefaultDagOp->getArg(0);
4923 }
4924 }
4925 }
4926
4927 if (const DefInit *DefaultDefOp = dyn_cast<DefInit>(DefaultOp)) {
4928 auto Def = DefaultDefOp->getDef();
4929 if (Def->getName() == "undef_tied_input") {
4930 unsigned TempRegID = M.allocateTempRegID();
4931 M.insertAction<MakeTempRegisterAction>(
4932 InsertPt, OpTyOrNone.getValue(), TempRegID);
4933 InsertPt = M.insertAction<BuildMIAction>(
4934 InsertPt, M.allocateOutputInsnID(),
4935 &Target.getInstruction(RK.getDef("IMPLICIT_DEF")));
4936 BuildMIAction &IDMIBuilder = *static_cast<BuildMIAction *>(
4937 InsertPt->get());
4938 IDMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
4939 DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
4940 } else {
4941 DstMIBuilder.addRenderer<AddRegisterRenderer>(Target, Def);
4942 }
4943 continue;
4944 }
4945
4946 if (const IntInit *DefaultIntOp = dyn_cast<IntInit>(DefaultOp)) {
4947 DstMIBuilder.addRenderer<ImmRenderer>(DefaultIntOp->getValue());
4948 continue;
4949 }
4950
4951 return failedImport("Could not add default op");
4952 }
4953
4954 return Error::success();
4955 }
4956
importImplicitDefRenderers(BuildMIAction & DstMIBuilder,const std::vector<Record * > & ImplicitDefs) const4957 Error GlobalISelEmitter::importImplicitDefRenderers(
4958 BuildMIAction &DstMIBuilder,
4959 const std::vector<Record *> &ImplicitDefs) const {
4960 if (!ImplicitDefs.empty())
4961 return failedImport("Pattern defines a physical register");
4962 return Error::success();
4963 }
4964
4965 Optional<const CodeGenRegisterClass *>
getRegClassFromLeaf(TreePatternNode * Leaf)4966 GlobalISelEmitter::getRegClassFromLeaf(TreePatternNode *Leaf) {
4967 assert(Leaf && "Expected node?");
4968 assert(Leaf->isLeaf() && "Expected leaf?");
4969 Record *RCRec = getInitValueAsRegClass(Leaf->getLeafValue());
4970 if (!RCRec)
4971 return None;
4972 CodeGenRegisterClass *RC = CGRegs.getRegClass(RCRec);
4973 if (!RC)
4974 return None;
4975 return RC;
4976 }
4977
4978 Optional<const CodeGenRegisterClass *>
inferRegClassFromPattern(TreePatternNode * N)4979 GlobalISelEmitter::inferRegClassFromPattern(TreePatternNode *N) {
4980 if (!N)
4981 return None;
4982
4983 if (N->isLeaf())
4984 return getRegClassFromLeaf(N);
4985
4986 // We don't have a leaf node, so we have to try and infer something. Check
4987 // that we have an instruction that we an infer something from.
4988
4989 // Only handle things that produce a single type.
4990 if (N->getNumTypes() != 1)
4991 return None;
4992 Record *OpRec = N->getOperator();
4993
4994 // We only want instructions.
4995 if (!OpRec->isSubClassOf("Instruction"))
4996 return None;
4997
4998 // Don't want to try and infer things when there could potentially be more
4999 // than one candidate register class.
5000 auto &Inst = Target.getInstruction(OpRec);
5001 if (Inst.Operands.NumDefs > 1)
5002 return None;
5003
5004 // Handle any special-case instructions which we can safely infer register
5005 // classes from.
5006 StringRef InstName = Inst.TheDef->getName();
5007 bool IsRegSequence = InstName == "REG_SEQUENCE";
5008 if (IsRegSequence || InstName == "COPY_TO_REGCLASS") {
5009 // If we have a COPY_TO_REGCLASS, then we need to handle it specially. It
5010 // has the desired register class as the first child.
5011 TreePatternNode *RCChild = N->getChild(IsRegSequence ? 0 : 1);
5012 if (!RCChild->isLeaf())
5013 return None;
5014 return getRegClassFromLeaf(RCChild);
5015 }
5016 if (InstName == "INSERT_SUBREG") {
5017 TreePatternNode *Child0 = N->getChild(0);
5018 assert(Child0->getNumTypes() == 1 && "Unexpected number of types!");
5019 const TypeSetByHwMode &VTy = Child0->getExtType(0);
5020 return inferSuperRegisterClassForNode(VTy, Child0, N->getChild(2));
5021 }
5022 if (InstName == "EXTRACT_SUBREG") {
5023 assert(N->getNumTypes() == 1 && "Unexpected number of types!");
5024 const TypeSetByHwMode &VTy = N->getExtType(0);
5025 return inferSuperRegisterClass(VTy, N->getChild(1));
5026 }
5027
5028 // Handle destination record types that we can safely infer a register class
5029 // from.
5030 const auto &DstIOperand = Inst.Operands[0];
5031 Record *DstIOpRec = DstIOperand.Rec;
5032 if (DstIOpRec->isSubClassOf("RegisterOperand")) {
5033 DstIOpRec = DstIOpRec->getValueAsDef("RegClass");
5034 const CodeGenRegisterClass &RC = Target.getRegisterClass(DstIOpRec);
5035 return &RC;
5036 }
5037
5038 if (DstIOpRec->isSubClassOf("RegisterClass")) {
5039 const CodeGenRegisterClass &RC = Target.getRegisterClass(DstIOpRec);
5040 return &RC;
5041 }
5042
5043 return None;
5044 }
5045
5046 Optional<const CodeGenRegisterClass *>
inferSuperRegisterClass(const TypeSetByHwMode & Ty,TreePatternNode * SubRegIdxNode)5047 GlobalISelEmitter::inferSuperRegisterClass(const TypeSetByHwMode &Ty,
5048 TreePatternNode *SubRegIdxNode) {
5049 assert(SubRegIdxNode && "Expected subregister index node!");
5050 // We need a ValueTypeByHwMode for getSuperRegForSubReg.
5051 if (!Ty.isValueTypeByHwMode(false))
5052 return None;
5053 if (!SubRegIdxNode->isLeaf())
5054 return None;
5055 DefInit *SubRegInit = dyn_cast<DefInit>(SubRegIdxNode->getLeafValue());
5056 if (!SubRegInit)
5057 return None;
5058 CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
5059
5060 // Use the information we found above to find a minimal register class which
5061 // supports the subregister and type we want.
5062 auto RC =
5063 Target.getSuperRegForSubReg(Ty.getValueTypeByHwMode(), CGRegs, SubIdx,
5064 /* MustBeAllocatable */ true);
5065 if (!RC)
5066 return None;
5067 return *RC;
5068 }
5069
5070 Optional<const CodeGenRegisterClass *>
inferSuperRegisterClassForNode(const TypeSetByHwMode & Ty,TreePatternNode * SuperRegNode,TreePatternNode * SubRegIdxNode)5071 GlobalISelEmitter::inferSuperRegisterClassForNode(
5072 const TypeSetByHwMode &Ty, TreePatternNode *SuperRegNode,
5073 TreePatternNode *SubRegIdxNode) {
5074 assert(SuperRegNode && "Expected super register node!");
5075 // Check if we already have a defined register class for the super register
5076 // node. If we do, then we should preserve that rather than inferring anything
5077 // from the subregister index node. We can assume that whoever wrote the
5078 // pattern in the first place made sure that the super register and
5079 // subregister are compatible.
5080 if (Optional<const CodeGenRegisterClass *> SuperRegisterClass =
5081 inferRegClassFromPattern(SuperRegNode))
5082 return *SuperRegisterClass;
5083 return inferSuperRegisterClass(Ty, SubRegIdxNode);
5084 }
5085
5086 Optional<CodeGenSubRegIndex *>
inferSubRegIndexForNode(TreePatternNode * SubRegIdxNode)5087 GlobalISelEmitter::inferSubRegIndexForNode(TreePatternNode *SubRegIdxNode) {
5088 if (!SubRegIdxNode->isLeaf())
5089 return None;
5090
5091 DefInit *SubRegInit = dyn_cast<DefInit>(SubRegIdxNode->getLeafValue());
5092 if (!SubRegInit)
5093 return None;
5094 return CGRegs.getSubRegIdx(SubRegInit->getDef());
5095 }
5096
runOnPattern(const PatternToMatch & P)5097 Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
5098 // Keep track of the matchers and actions to emit.
5099 int Score = P.getPatternComplexity(CGP);
5100 RuleMatcher M(P.getSrcRecord()->getLoc());
5101 RuleMatcherScores[M.getRuleID()] = Score;
5102 M.addAction<DebugCommentAction>(llvm::to_string(*P.getSrcPattern()) +
5103 " => " +
5104 llvm::to_string(*P.getDstPattern()));
5105
5106 SmallVector<Record *, 4> Predicates;
5107 P.getPredicateRecords(Predicates);
5108 if (auto Error = importRulePredicates(M, Predicates))
5109 return std::move(Error);
5110
5111 // Next, analyze the pattern operators.
5112 TreePatternNode *Src = P.getSrcPattern();
5113 TreePatternNode *Dst = P.getDstPattern();
5114
5115 // If the root of either pattern isn't a simple operator, ignore it.
5116 if (auto Err = isTrivialOperatorNode(Dst))
5117 return failedImport("Dst pattern root isn't a trivial operator (" +
5118 toString(std::move(Err)) + ")");
5119 if (auto Err = isTrivialOperatorNode(Src))
5120 return failedImport("Src pattern root isn't a trivial operator (" +
5121 toString(std::move(Err)) + ")");
5122
5123 // The different predicates and matchers created during
5124 // addInstructionMatcher use the RuleMatcher M to set up their
5125 // instruction ID (InsnVarID) that are going to be used when
5126 // M is going to be emitted.
5127 // However, the code doing the emission still relies on the IDs
5128 // returned during that process by the RuleMatcher when issuing
5129 // the recordInsn opcodes.
5130 // Because of that:
5131 // 1. The order in which we created the predicates
5132 // and such must be the same as the order in which we emit them,
5133 // and
5134 // 2. We need to reset the generation of the IDs in M somewhere between
5135 // addInstructionMatcher and emit
5136 //
5137 // FIXME: Long term, we don't want to have to rely on this implicit
5138 // naming being the same. One possible solution would be to have
5139 // explicit operator for operation capture and reference those.
5140 // The plus side is that it would expose opportunities to share
5141 // the capture accross rules. The downside is that it would
5142 // introduce a dependency between predicates (captures must happen
5143 // before their first use.)
5144 InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher(Src->getName());
5145 unsigned TempOpIdx = 0;
5146 auto InsnMatcherOrError =
5147 createAndImportSelDAGMatcher(M, InsnMatcherTemp, Src, TempOpIdx);
5148 if (auto Error = InsnMatcherOrError.takeError())
5149 return std::move(Error);
5150 InstructionMatcher &InsnMatcher = InsnMatcherOrError.get();
5151
5152 if (Dst->isLeaf()) {
5153 Record *RCDef = getInitValueAsRegClass(Dst->getLeafValue());
5154 if (RCDef) {
5155 const CodeGenRegisterClass &RC = Target.getRegisterClass(RCDef);
5156
5157 // We need to replace the def and all its uses with the specified
5158 // operand. However, we must also insert COPY's wherever needed.
5159 // For now, emit a copy and let the register allocator clean up.
5160 auto &DstI = Target.getInstruction(RK.getDef("COPY"));
5161 const auto &DstIOperand = DstI.Operands[0];
5162
5163 OperandMatcher &OM0 = InsnMatcher.getOperand(0);
5164 OM0.setSymbolicName(DstIOperand.Name);
5165 M.defineOperand(OM0.getSymbolicName(), OM0);
5166 OM0.addPredicate<RegisterBankOperandMatcher>(RC);
5167
5168 auto &DstMIBuilder =
5169 M.addAction<BuildMIAction>(M.allocateOutputInsnID(), &DstI);
5170 DstMIBuilder.addRenderer<CopyRenderer>(DstIOperand.Name);
5171 DstMIBuilder.addRenderer<CopyRenderer>(Dst->getName());
5172 M.addAction<ConstrainOperandToRegClassAction>(0, 0, RC);
5173
5174 // We're done with this pattern! It's eligible for GISel emission; return
5175 // it.
5176 ++NumPatternImported;
5177 return std::move(M);
5178 }
5179
5180 return failedImport("Dst pattern root isn't a known leaf");
5181 }
5182
5183 // Start with the defined operands (i.e., the results of the root operator).
5184 Record *DstOp = Dst->getOperator();
5185 if (!DstOp->isSubClassOf("Instruction"))
5186 return failedImport("Pattern operator isn't an instruction");
5187
5188 auto &DstI = Target.getInstruction(DstOp);
5189 StringRef DstIName = DstI.TheDef->getName();
5190
5191 if (DstI.Operands.NumDefs < Src->getExtTypes().size())
5192 return failedImport("Src pattern result has more defs than dst MI (" +
5193 to_string(Src->getExtTypes().size()) + " def(s) vs " +
5194 to_string(DstI.Operands.NumDefs) + " def(s))");
5195
5196 // The root of the match also has constraints on the register bank so that it
5197 // matches the result instruction.
5198 unsigned OpIdx = 0;
5199 for (const TypeSetByHwMode &VTy : Src->getExtTypes()) {
5200 (void)VTy;
5201
5202 const auto &DstIOperand = DstI.Operands[OpIdx];
5203 Record *DstIOpRec = DstIOperand.Rec;
5204 if (DstIName == "COPY_TO_REGCLASS") {
5205 DstIOpRec = getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());
5206
5207 if (DstIOpRec == nullptr)
5208 return failedImport(
5209 "COPY_TO_REGCLASS operand #1 isn't a register class");
5210 } else if (DstIName == "REG_SEQUENCE") {
5211 DstIOpRec = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
5212 if (DstIOpRec == nullptr)
5213 return failedImport("REG_SEQUENCE operand #0 isn't a register class");
5214 } else if (DstIName == "EXTRACT_SUBREG") {
5215 auto InferredClass = inferRegClassFromPattern(Dst->getChild(0));
5216 if (!InferredClass)
5217 return failedImport("Could not infer class for EXTRACT_SUBREG operand #0");
5218
5219 // We can assume that a subregister is in the same bank as it's super
5220 // register.
5221 DstIOpRec = (*InferredClass)->getDef();
5222 } else if (DstIName == "INSERT_SUBREG") {
5223 auto MaybeSuperClass = inferSuperRegisterClassForNode(
5224 VTy, Dst->getChild(0), Dst->getChild(2));
5225 if (!MaybeSuperClass)
5226 return failedImport(
5227 "Cannot infer register class for INSERT_SUBREG operand #0");
5228 // Move to the next pattern here, because the register class we found
5229 // doesn't necessarily have a record associated with it. So, we can't
5230 // set DstIOpRec using this.
5231 OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
5232 OM.setSymbolicName(DstIOperand.Name);
5233 M.defineOperand(OM.getSymbolicName(), OM);
5234 OM.addPredicate<RegisterBankOperandMatcher>(**MaybeSuperClass);
5235 ++OpIdx;
5236 continue;
5237 } else if (DstIName == "SUBREG_TO_REG") {
5238 auto MaybeRegClass = inferSuperRegisterClass(VTy, Dst->getChild(2));
5239 if (!MaybeRegClass)
5240 return failedImport(
5241 "Cannot infer register class for SUBREG_TO_REG operand #0");
5242 OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
5243 OM.setSymbolicName(DstIOperand.Name);
5244 M.defineOperand(OM.getSymbolicName(), OM);
5245 OM.addPredicate<RegisterBankOperandMatcher>(**MaybeRegClass);
5246 ++OpIdx;
5247 continue;
5248 } else if (DstIOpRec->isSubClassOf("RegisterOperand"))
5249 DstIOpRec = DstIOpRec->getValueAsDef("RegClass");
5250 else if (!DstIOpRec->isSubClassOf("RegisterClass"))
5251 return failedImport("Dst MI def isn't a register class" +
5252 to_string(*Dst));
5253
5254 OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
5255 OM.setSymbolicName(DstIOperand.Name);
5256 M.defineOperand(OM.getSymbolicName(), OM);
5257 OM.addPredicate<RegisterBankOperandMatcher>(
5258 Target.getRegisterClass(DstIOpRec));
5259 ++OpIdx;
5260 }
5261
5262 auto DstMIBuilderOrError =
5263 createAndImportInstructionRenderer(M, InsnMatcher, Src, Dst);
5264 if (auto Error = DstMIBuilderOrError.takeError())
5265 return std::move(Error);
5266 BuildMIAction &DstMIBuilder = DstMIBuilderOrError.get();
5267
5268 // Render the implicit defs.
5269 // These are only added to the root of the result.
5270 if (auto Error = importImplicitDefRenderers(DstMIBuilder, P.getDstRegs()))
5271 return std::move(Error);
5272
5273 DstMIBuilder.chooseInsnToMutate(M);
5274
5275 // Constrain the registers to classes. This is normally derived from the
5276 // emitted instruction but a few instructions require special handling.
5277 if (DstIName == "COPY_TO_REGCLASS") {
5278 // COPY_TO_REGCLASS does not provide operand constraints itself but the
5279 // result is constrained to the class given by the second child.
5280 Record *DstIOpRec =
5281 getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());
5282
5283 if (DstIOpRec == nullptr)
5284 return failedImport("COPY_TO_REGCLASS operand #1 isn't a register class");
5285
5286 M.addAction<ConstrainOperandToRegClassAction>(
5287 0, 0, Target.getRegisterClass(DstIOpRec));
5288
5289 // We're done with this pattern! It's eligible for GISel emission; return
5290 // it.
5291 ++NumPatternImported;
5292 return std::move(M);
5293 }
5294
5295 if (DstIName == "EXTRACT_SUBREG") {
5296 auto SuperClass = inferRegClassFromPattern(Dst->getChild(0));
5297 if (!SuperClass)
5298 return failedImport(
5299 "Cannot infer register class from EXTRACT_SUBREG operand #0");
5300
5301 auto SubIdx = inferSubRegIndexForNode(Dst->getChild(1));
5302 if (!SubIdx)
5303 return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
5304
5305 // It would be nice to leave this constraint implicit but we're required
5306 // to pick a register class so constrain the result to a register class
5307 // that can hold the correct MVT.
5308 //
5309 // FIXME: This may introduce an extra copy if the chosen class doesn't
5310 // actually contain the subregisters.
5311 assert(Src->getExtTypes().size() == 1 &&
5312 "Expected Src of EXTRACT_SUBREG to have one result type");
5313
5314 const auto SrcRCDstRCPair =
5315 (*SuperClass)->getMatchingSubClassWithSubRegs(CGRegs, *SubIdx);
5316 if (!SrcRCDstRCPair) {
5317 return failedImport("subreg index is incompatible "
5318 "with inferred reg class");
5319 }
5320
5321 assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
5322 M.addAction<ConstrainOperandToRegClassAction>(0, 0, *SrcRCDstRCPair->second);
5323 M.addAction<ConstrainOperandToRegClassAction>(0, 1, *SrcRCDstRCPair->first);
5324
5325 // We're done with this pattern! It's eligible for GISel emission; return
5326 // it.
5327 ++NumPatternImported;
5328 return std::move(M);
5329 }
5330
5331 if (DstIName == "INSERT_SUBREG") {
5332 assert(Src->getExtTypes().size() == 1 &&
5333 "Expected Src of INSERT_SUBREG to have one result type");
5334 // We need to constrain the destination, a super regsister source, and a
5335 // subregister source.
5336 auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
5337 if (!SubClass)
5338 return failedImport(
5339 "Cannot infer register class from INSERT_SUBREG operand #1");
5340 auto SuperClass = inferSuperRegisterClassForNode(
5341 Src->getExtType(0), Dst->getChild(0), Dst->getChild(2));
5342 if (!SuperClass)
5343 return failedImport(
5344 "Cannot infer register class for INSERT_SUBREG operand #0");
5345 M.addAction<ConstrainOperandToRegClassAction>(0, 0, **SuperClass);
5346 M.addAction<ConstrainOperandToRegClassAction>(0, 1, **SuperClass);
5347 M.addAction<ConstrainOperandToRegClassAction>(0, 2, **SubClass);
5348 ++NumPatternImported;
5349 return std::move(M);
5350 }
5351
5352 if (DstIName == "SUBREG_TO_REG") {
5353 // We need to constrain the destination and subregister source.
5354 assert(Src->getExtTypes().size() == 1 &&
5355 "Expected Src of SUBREG_TO_REG to have one result type");
5356
5357 // Attempt to infer the subregister source from the first child. If it has
5358 // an explicitly given register class, we'll use that. Otherwise, we will
5359 // fail.
5360 auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
5361 if (!SubClass)
5362 return failedImport(
5363 "Cannot infer register class from SUBREG_TO_REG child #1");
5364 // We don't have a child to look at that might have a super register node.
5365 auto SuperClass =
5366 inferSuperRegisterClass(Src->getExtType(0), Dst->getChild(2));
5367 if (!SuperClass)
5368 return failedImport(
5369 "Cannot infer register class for SUBREG_TO_REG operand #0");
5370 M.addAction<ConstrainOperandToRegClassAction>(0, 0, **SuperClass);
5371 M.addAction<ConstrainOperandToRegClassAction>(0, 2, **SubClass);
5372 ++NumPatternImported;
5373 return std::move(M);
5374 }
5375
5376 if (DstIName == "REG_SEQUENCE") {
5377 auto SuperClass = inferRegClassFromPattern(Dst->getChild(0));
5378
5379 M.addAction<ConstrainOperandToRegClassAction>(0, 0, **SuperClass);
5380
5381 unsigned Num = Dst->getNumChildren();
5382 for (unsigned I = 1; I != Num; I += 2) {
5383 TreePatternNode *SubRegChild = Dst->getChild(I + 1);
5384
5385 auto SubIdx = inferSubRegIndexForNode(SubRegChild);
5386 if (!SubIdx)
5387 return failedImport("REG_SEQUENCE child is not a subreg index");
5388
5389 const auto SrcRCDstRCPair =
5390 (*SuperClass)->getMatchingSubClassWithSubRegs(CGRegs, *SubIdx);
5391
5392 M.addAction<ConstrainOperandToRegClassAction>(0, I,
5393 *SrcRCDstRCPair->second);
5394 }
5395
5396 ++NumPatternImported;
5397 return std::move(M);
5398 }
5399
5400 M.addAction<ConstrainOperandsToDefinitionAction>(0);
5401
5402 // We're done with this pattern! It's eligible for GISel emission; return it.
5403 ++NumPatternImported;
5404 return std::move(M);
5405 }
5406
5407 // Emit imm predicate table and an enum to reference them with.
5408 // The 'Predicate_' part of the name is redundant but eliminating it is more
5409 // trouble than it's worth.
emitCxxPredicateFns(raw_ostream & OS,StringRef CodeFieldName,StringRef TypeIdentifier,StringRef ArgType,StringRef ArgName,StringRef AdditionalArgs,StringRef AdditionalDeclarations,std::function<bool (const Record * R)> Filter)5410 void GlobalISelEmitter::emitCxxPredicateFns(
5411 raw_ostream &OS, StringRef CodeFieldName, StringRef TypeIdentifier,
5412 StringRef ArgType, StringRef ArgName, StringRef AdditionalArgs,
5413 StringRef AdditionalDeclarations,
5414 std::function<bool(const Record *R)> Filter) {
5415 std::vector<const Record *> MatchedRecords;
5416 const auto &Defs = RK.getAllDerivedDefinitions("PatFrags");
5417 std::copy_if(Defs.begin(), Defs.end(), std::back_inserter(MatchedRecords),
5418 [&](Record *Record) {
5419 return !Record->getValueAsString(CodeFieldName).empty() &&
5420 Filter(Record);
5421 });
5422
5423 if (!MatchedRecords.empty()) {
5424 OS << "// PatFrag predicates.\n"
5425 << "enum {\n";
5426 std::string EnumeratorSeparator =
5427 (" = GIPFP_" + TypeIdentifier + "_Invalid + 1,\n").str();
5428 for (const auto *Record : MatchedRecords) {
5429 OS << " GIPFP_" << TypeIdentifier << "_Predicate_" << Record->getName()
5430 << EnumeratorSeparator;
5431 EnumeratorSeparator = ",\n";
5432 }
5433 OS << "};\n";
5434 }
5435
5436 OS << "bool " << Target.getName() << "InstructionSelector::test" << ArgName
5437 << "Predicate_" << TypeIdentifier << "(unsigned PredicateID, " << ArgType << " "
5438 << ArgName << AdditionalArgs <<") const {\n"
5439 << AdditionalDeclarations;
5440 if (!AdditionalDeclarations.empty())
5441 OS << "\n";
5442 if (!MatchedRecords.empty())
5443 OS << " switch (PredicateID) {\n";
5444 for (const auto *Record : MatchedRecords) {
5445 OS << " case GIPFP_" << TypeIdentifier << "_Predicate_"
5446 << Record->getName() << ": {\n"
5447 << " " << Record->getValueAsString(CodeFieldName) << "\n"
5448 << " llvm_unreachable(\"" << CodeFieldName
5449 << " should have returned\");\n"
5450 << " return false;\n"
5451 << " }\n";
5452 }
5453 if (!MatchedRecords.empty())
5454 OS << " }\n";
5455 OS << " llvm_unreachable(\"Unknown predicate\");\n"
5456 << " return false;\n"
5457 << "}\n";
5458 }
5459
emitImmPredicateFns(raw_ostream & OS,StringRef TypeIdentifier,StringRef ArgType,std::function<bool (const Record * R)> Filter)5460 void GlobalISelEmitter::emitImmPredicateFns(
5461 raw_ostream &OS, StringRef TypeIdentifier, StringRef ArgType,
5462 std::function<bool(const Record *R)> Filter) {
5463 return emitCxxPredicateFns(OS, "ImmediateCode", TypeIdentifier, ArgType,
5464 "Imm", "", "", Filter);
5465 }
5466
emitMIPredicateFns(raw_ostream & OS)5467 void GlobalISelEmitter::emitMIPredicateFns(raw_ostream &OS) {
5468 return emitCxxPredicateFns(
5469 OS, "GISelPredicateCode", "MI", "const MachineInstr &", "MI",
5470 ", const std::array<const MachineOperand *, 3> &Operands",
5471 " const MachineFunction &MF = *MI.getParent()->getParent();\n"
5472 " const MachineRegisterInfo &MRI = MF.getRegInfo();\n"
5473 " (void)MRI;",
5474 [](const Record *R) { return true; });
5475 }
5476
5477 template <class GroupT>
optimizeRules(ArrayRef<Matcher * > Rules,std::vector<std::unique_ptr<Matcher>> & MatcherStorage)5478 std::vector<Matcher *> GlobalISelEmitter::optimizeRules(
5479 ArrayRef<Matcher *> Rules,
5480 std::vector<std::unique_ptr<Matcher>> &MatcherStorage) {
5481
5482 std::vector<Matcher *> OptRules;
5483 std::unique_ptr<GroupT> CurrentGroup = std::make_unique<GroupT>();
5484 assert(CurrentGroup->empty() && "Newly created group isn't empty!");
5485 unsigned NumGroups = 0;
5486
5487 auto ProcessCurrentGroup = [&]() {
5488 if (CurrentGroup->empty())
5489 // An empty group is good to be reused:
5490 return;
5491
5492 // If the group isn't large enough to provide any benefit, move all the
5493 // added rules out of it and make sure to re-create the group to properly
5494 // re-initialize it:
5495 if (CurrentGroup->size() < 2)
5496 append_range(OptRules, CurrentGroup->matchers());
5497 else {
5498 CurrentGroup->finalize();
5499 OptRules.push_back(CurrentGroup.get());
5500 MatcherStorage.emplace_back(std::move(CurrentGroup));
5501 ++NumGroups;
5502 }
5503 CurrentGroup = std::make_unique<GroupT>();
5504 };
5505 for (Matcher *Rule : Rules) {
5506 // Greedily add as many matchers as possible to the current group:
5507 if (CurrentGroup->addMatcher(*Rule))
5508 continue;
5509
5510 ProcessCurrentGroup();
5511 assert(CurrentGroup->empty() && "A group wasn't properly re-initialized");
5512
5513 // Try to add the pending matcher to a newly created empty group:
5514 if (!CurrentGroup->addMatcher(*Rule))
5515 // If we couldn't add the matcher to an empty group, that group type
5516 // doesn't support that kind of matchers at all, so just skip it:
5517 OptRules.push_back(Rule);
5518 }
5519 ProcessCurrentGroup();
5520
5521 LLVM_DEBUG(dbgs() << "NumGroups: " << NumGroups << "\n");
5522 assert(CurrentGroup->empty() && "The last group wasn't properly processed");
5523 return OptRules;
5524 }
5525
5526 MatchTable
buildMatchTable(MutableArrayRef<RuleMatcher> Rules,bool Optimize,bool WithCoverage)5527 GlobalISelEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules,
5528 bool Optimize, bool WithCoverage) {
5529 std::vector<Matcher *> InputRules;
5530 for (Matcher &Rule : Rules)
5531 InputRules.push_back(&Rule);
5532
5533 if (!Optimize)
5534 return MatchTable::buildTable(InputRules, WithCoverage);
5535
5536 unsigned CurrentOrdering = 0;
5537 StringMap<unsigned> OpcodeOrder;
5538 for (RuleMatcher &Rule : Rules) {
5539 const StringRef Opcode = Rule.getOpcode();
5540 assert(!Opcode.empty() && "Didn't expect an undefined opcode");
5541 if (OpcodeOrder.count(Opcode) == 0)
5542 OpcodeOrder[Opcode] = CurrentOrdering++;
5543 }
5544
5545 llvm::stable_sort(InputRules, [&OpcodeOrder](const Matcher *A,
5546 const Matcher *B) {
5547 auto *L = static_cast<const RuleMatcher *>(A);
5548 auto *R = static_cast<const RuleMatcher *>(B);
5549 return std::make_tuple(OpcodeOrder[L->getOpcode()], L->getNumOperands()) <
5550 std::make_tuple(OpcodeOrder[R->getOpcode()], R->getNumOperands());
5551 });
5552
5553 for (Matcher *Rule : InputRules)
5554 Rule->optimize();
5555
5556 std::vector<std::unique_ptr<Matcher>> MatcherStorage;
5557 std::vector<Matcher *> OptRules =
5558 optimizeRules<GroupMatcher>(InputRules, MatcherStorage);
5559
5560 for (Matcher *Rule : OptRules)
5561 Rule->optimize();
5562
5563 OptRules = optimizeRules<SwitchMatcher>(OptRules, MatcherStorage);
5564
5565 return MatchTable::buildTable(OptRules, WithCoverage);
5566 }
5567
optimize()5568 void GroupMatcher::optimize() {
5569 // Make sure we only sort by a specific predicate within a range of rules that
5570 // all have that predicate checked against a specific value (not a wildcard):
5571 auto F = Matchers.begin();
5572 auto T = F;
5573 auto E = Matchers.end();
5574 while (T != E) {
5575 while (T != E) {
5576 auto *R = static_cast<RuleMatcher *>(*T);
5577 if (!R->getFirstConditionAsRootType().get().isValid())
5578 break;
5579 ++T;
5580 }
5581 std::stable_sort(F, T, [](Matcher *A, Matcher *B) {
5582 auto *L = static_cast<RuleMatcher *>(A);
5583 auto *R = static_cast<RuleMatcher *>(B);
5584 return L->getFirstConditionAsRootType() <
5585 R->getFirstConditionAsRootType();
5586 });
5587 if (T != E)
5588 F = ++T;
5589 }
5590 GlobalISelEmitter::optimizeRules<GroupMatcher>(Matchers, MatcherStorage)
5591 .swap(Matchers);
5592 GlobalISelEmitter::optimizeRules<SwitchMatcher>(Matchers, MatcherStorage)
5593 .swap(Matchers);
5594 }
5595
run(raw_ostream & OS)5596 void GlobalISelEmitter::run(raw_ostream &OS) {
5597 if (!UseCoverageFile.empty()) {
5598 RuleCoverage = CodeGenCoverage();
5599 auto RuleCoverageBufOrErr = MemoryBuffer::getFile(UseCoverageFile);
5600 if (!RuleCoverageBufOrErr) {
5601 PrintWarning(SMLoc(), "Missing rule coverage data");
5602 RuleCoverage = None;
5603 } else {
5604 if (!RuleCoverage->parse(*RuleCoverageBufOrErr.get(), Target.getName())) {
5605 PrintWarning(SMLoc(), "Ignoring invalid or missing rule coverage data");
5606 RuleCoverage = None;
5607 }
5608 }
5609 }
5610
5611 // Track the run-time opcode values
5612 gatherOpcodeValues();
5613 // Track the run-time LLT ID values
5614 gatherTypeIDValues();
5615
5616 // Track the GINodeEquiv definitions.
5617 gatherNodeEquivs();
5618
5619 emitSourceFileHeader(("Global Instruction Selector for the " +
5620 Target.getName() + " target").str(), OS);
5621 std::vector<RuleMatcher> Rules;
5622 // Look through the SelectionDAG patterns we found, possibly emitting some.
5623 for (const PatternToMatch &Pat : CGP.ptms()) {
5624 ++NumPatternTotal;
5625
5626 auto MatcherOrErr = runOnPattern(Pat);
5627
5628 // The pattern analysis can fail, indicating an unsupported pattern.
5629 // Report that if we've been asked to do so.
5630 if (auto Err = MatcherOrErr.takeError()) {
5631 if (WarnOnSkippedPatterns) {
5632 PrintWarning(Pat.getSrcRecord()->getLoc(),
5633 "Skipped pattern: " + toString(std::move(Err)));
5634 } else {
5635 consumeError(std::move(Err));
5636 }
5637 ++NumPatternImportsSkipped;
5638 continue;
5639 }
5640
5641 if (RuleCoverage) {
5642 if (RuleCoverage->isCovered(MatcherOrErr->getRuleID()))
5643 ++NumPatternsTested;
5644 else
5645 PrintWarning(Pat.getSrcRecord()->getLoc(),
5646 "Pattern is not covered by a test");
5647 }
5648 Rules.push_back(std::move(MatcherOrErr.get()));
5649 }
5650
5651 // Comparison function to order records by name.
5652 auto orderByName = [](const Record *A, const Record *B) {
5653 return A->getName() < B->getName();
5654 };
5655
5656 std::vector<Record *> ComplexPredicates =
5657 RK.getAllDerivedDefinitions("GIComplexOperandMatcher");
5658 llvm::sort(ComplexPredicates, orderByName);
5659
5660 std::vector<StringRef> CustomRendererFns;
5661 transform(RK.getAllDerivedDefinitions("GICustomOperandRenderer"),
5662 std::back_inserter(CustomRendererFns), [](const auto &Record) {
5663 return Record->getValueAsString("RendererFn");
5664 });
5665 // Sort and remove duplicates to get a list of unique renderer functions, in
5666 // case some were mentioned more than once.
5667 llvm::sort(CustomRendererFns);
5668 CustomRendererFns.erase(
5669 std::unique(CustomRendererFns.begin(), CustomRendererFns.end()),
5670 CustomRendererFns.end());
5671
5672 unsigned MaxTemporaries = 0;
5673 for (const auto &Rule : Rules)
5674 MaxTemporaries = std::max(MaxTemporaries, Rule.countRendererFns());
5675
5676 OS << "#ifdef GET_GLOBALISEL_PREDICATE_BITSET\n"
5677 << "const unsigned MAX_SUBTARGET_PREDICATES = " << SubtargetFeatures.size()
5678 << ";\n"
5679 << "using PredicateBitset = "
5680 "llvm::PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;\n"
5681 << "#endif // ifdef GET_GLOBALISEL_PREDICATE_BITSET\n\n";
5682
5683 OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n"
5684 << " mutable MatcherState State;\n"
5685 << " typedef "
5686 "ComplexRendererFns("
5687 << Target.getName()
5688 << "InstructionSelector::*ComplexMatcherMemFn)(MachineOperand &) const;\n"
5689
5690 << " typedef void(" << Target.getName()
5691 << "InstructionSelector::*CustomRendererFn)(MachineInstrBuilder &, const "
5692 "MachineInstr &, int) "
5693 "const;\n"
5694 << " const ISelInfoTy<PredicateBitset, ComplexMatcherMemFn, "
5695 "CustomRendererFn> "
5696 "ISelInfo;\n";
5697 OS << " static " << Target.getName()
5698 << "InstructionSelector::ComplexMatcherMemFn ComplexPredicateFns[];\n"
5699 << " static " << Target.getName()
5700 << "InstructionSelector::CustomRendererFn CustomRenderers[];\n"
5701 << " bool testImmPredicate_I64(unsigned PredicateID, int64_t Imm) const "
5702 "override;\n"
5703 << " bool testImmPredicate_APInt(unsigned PredicateID, const APInt &Imm) "
5704 "const override;\n"
5705 << " bool testImmPredicate_APFloat(unsigned PredicateID, const APFloat "
5706 "&Imm) const override;\n"
5707 << " const int64_t *getMatchTable() const override;\n"
5708 << " bool testMIPredicate_MI(unsigned PredicateID, const MachineInstr &MI"
5709 ", const std::array<const MachineOperand *, 3> &Operands) "
5710 "const override;\n"
5711 << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n";
5712
5713 OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n"
5714 << ", State(" << MaxTemporaries << "),\n"
5715 << "ISelInfo(TypeObjects, NumTypeObjects, FeatureBitsets"
5716 << ", ComplexPredicateFns, CustomRenderers)\n"
5717 << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";
5718
5719 OS << "#ifdef GET_GLOBALISEL_IMPL\n";
5720 SubtargetFeatureInfo::emitSubtargetFeatureBitEnumeration(SubtargetFeatures,
5721 OS);
5722
5723 // Separate subtarget features by how often they must be recomputed.
5724 SubtargetFeatureInfoMap ModuleFeatures;
5725 std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
5726 std::inserter(ModuleFeatures, ModuleFeatures.end()),
5727 [](const SubtargetFeatureInfoMap::value_type &X) {
5728 return !X.second.mustRecomputePerFunction();
5729 });
5730 SubtargetFeatureInfoMap FunctionFeatures;
5731 std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
5732 std::inserter(FunctionFeatures, FunctionFeatures.end()),
5733 [](const SubtargetFeatureInfoMap::value_type &X) {
5734 return X.second.mustRecomputePerFunction();
5735 });
5736
5737 SubtargetFeatureInfo::emitComputeAvailableFeatures(
5738 Target.getName(), "InstructionSelector", "computeAvailableModuleFeatures",
5739 ModuleFeatures, OS);
5740
5741
5742 OS << "void " << Target.getName() << "InstructionSelector"
5743 "::setupGeneratedPerFunctionState(MachineFunction &MF) {\n"
5744 " AvailableFunctionFeatures = computeAvailableFunctionFeatures("
5745 "(const " << Target.getName() << "Subtarget *)&MF.getSubtarget(), &MF);\n"
5746 "}\n";
5747
5748 SubtargetFeatureInfo::emitComputeAvailableFeatures(
5749 Target.getName(), "InstructionSelector",
5750 "computeAvailableFunctionFeatures", FunctionFeatures, OS,
5751 "const MachineFunction *MF");
5752
5753 // Emit a table containing the LLT objects needed by the matcher and an enum
5754 // for the matcher to reference them with.
5755 std::vector<LLTCodeGen> TypeObjects;
5756 append_range(TypeObjects, KnownTypes);
5757 llvm::sort(TypeObjects);
5758 OS << "// LLT Objects.\n"
5759 << "enum {\n";
5760 for (const auto &TypeObject : TypeObjects) {
5761 OS << " ";
5762 TypeObject.emitCxxEnumValue(OS);
5763 OS << ",\n";
5764 }
5765 OS << "};\n";
5766 OS << "const static size_t NumTypeObjects = " << TypeObjects.size() << ";\n"
5767 << "const static LLT TypeObjects[] = {\n";
5768 for (const auto &TypeObject : TypeObjects) {
5769 OS << " ";
5770 TypeObject.emitCxxConstructorCall(OS);
5771 OS << ",\n";
5772 }
5773 OS << "};\n\n";
5774
5775 // Emit a table containing the PredicateBitsets objects needed by the matcher
5776 // and an enum for the matcher to reference them with.
5777 std::vector<std::vector<Record *>> FeatureBitsets;
5778 for (auto &Rule : Rules)
5779 FeatureBitsets.push_back(Rule.getRequiredFeatures());
5780 llvm::sort(FeatureBitsets, [&](const std::vector<Record *> &A,
5781 const std::vector<Record *> &B) {
5782 if (A.size() < B.size())
5783 return true;
5784 if (A.size() > B.size())
5785 return false;
5786 for (auto Pair : zip(A, B)) {
5787 if (std::get<0>(Pair)->getName() < std::get<1>(Pair)->getName())
5788 return true;
5789 if (std::get<0>(Pair)->getName() > std::get<1>(Pair)->getName())
5790 return false;
5791 }
5792 return false;
5793 });
5794 FeatureBitsets.erase(
5795 std::unique(FeatureBitsets.begin(), FeatureBitsets.end()),
5796 FeatureBitsets.end());
5797 OS << "// Feature bitsets.\n"
5798 << "enum {\n"
5799 << " GIFBS_Invalid,\n";
5800 for (const auto &FeatureBitset : FeatureBitsets) {
5801 if (FeatureBitset.empty())
5802 continue;
5803 OS << " " << getNameForFeatureBitset(FeatureBitset) << ",\n";
5804 }
5805 OS << "};\n"
5806 << "const static PredicateBitset FeatureBitsets[] {\n"
5807 << " {}, // GIFBS_Invalid\n";
5808 for (const auto &FeatureBitset : FeatureBitsets) {
5809 if (FeatureBitset.empty())
5810 continue;
5811 OS << " {";
5812 for (const auto &Feature : FeatureBitset) {
5813 const auto &I = SubtargetFeatures.find(Feature);
5814 assert(I != SubtargetFeatures.end() && "Didn't import predicate?");
5815 OS << I->second.getEnumBitName() << ", ";
5816 }
5817 OS << "},\n";
5818 }
5819 OS << "};\n\n";
5820
5821 // Emit complex predicate table and an enum to reference them with.
5822 OS << "// ComplexPattern predicates.\n"
5823 << "enum {\n"
5824 << " GICP_Invalid,\n";
5825 for (const auto &Record : ComplexPredicates)
5826 OS << " GICP_" << Record->getName() << ",\n";
5827 OS << "};\n"
5828 << "// See constructor for table contents\n\n";
5829
5830 emitImmPredicateFns(OS, "I64", "int64_t", [](const Record *R) {
5831 bool Unset;
5832 return !R->getValueAsBitOrUnset("IsAPFloat", Unset) &&
5833 !R->getValueAsBit("IsAPInt");
5834 });
5835 emitImmPredicateFns(OS, "APFloat", "const APFloat &", [](const Record *R) {
5836 bool Unset;
5837 return R->getValueAsBitOrUnset("IsAPFloat", Unset);
5838 });
5839 emitImmPredicateFns(OS, "APInt", "const APInt &", [](const Record *R) {
5840 return R->getValueAsBit("IsAPInt");
5841 });
5842 emitMIPredicateFns(OS);
5843 OS << "\n";
5844
5845 OS << Target.getName() << "InstructionSelector::ComplexMatcherMemFn\n"
5846 << Target.getName() << "InstructionSelector::ComplexPredicateFns[] = {\n"
5847 << " nullptr, // GICP_Invalid\n";
5848 for (const auto &Record : ComplexPredicates)
5849 OS << " &" << Target.getName()
5850 << "InstructionSelector::" << Record->getValueAsString("MatcherFn")
5851 << ", // " << Record->getName() << "\n";
5852 OS << "};\n\n";
5853
5854 OS << "// Custom renderers.\n"
5855 << "enum {\n"
5856 << " GICR_Invalid,\n";
5857 for (const auto &Fn : CustomRendererFns)
5858 OS << " GICR_" << Fn << ",\n";
5859 OS << "};\n";
5860
5861 OS << Target.getName() << "InstructionSelector::CustomRendererFn\n"
5862 << Target.getName() << "InstructionSelector::CustomRenderers[] = {\n"
5863 << " nullptr, // GICR_Invalid\n";
5864 for (const auto &Fn : CustomRendererFns)
5865 OS << " &" << Target.getName() << "InstructionSelector::" << Fn << ",\n";
5866 OS << "};\n\n";
5867
5868 llvm::stable_sort(Rules, [&](const RuleMatcher &A, const RuleMatcher &B) {
5869 int ScoreA = RuleMatcherScores[A.getRuleID()];
5870 int ScoreB = RuleMatcherScores[B.getRuleID()];
5871 if (ScoreA > ScoreB)
5872 return true;
5873 if (ScoreB > ScoreA)
5874 return false;
5875 if (A.isHigherPriorityThan(B)) {
5876 assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
5877 "and less important at "
5878 "the same time");
5879 return true;
5880 }
5881 return false;
5882 });
5883
5884 OS << "bool " << Target.getName()
5885 << "InstructionSelector::selectImpl(MachineInstr &I, CodeGenCoverage "
5886 "&CoverageInfo) const {\n"
5887 << " MachineFunction &MF = *I.getParent()->getParent();\n"
5888 << " MachineRegisterInfo &MRI = MF.getRegInfo();\n"
5889 << " const PredicateBitset AvailableFeatures = getAvailableFeatures();\n"
5890 << " NewMIVector OutMIs;\n"
5891 << " State.MIs.clear();\n"
5892 << " State.MIs.push_back(&I);\n\n"
5893 << " if (executeMatchTable(*this, OutMIs, State, ISelInfo"
5894 << ", getMatchTable(), TII, MRI, TRI, RBI, AvailableFeatures"
5895 << ", CoverageInfo)) {\n"
5896 << " return true;\n"
5897 << " }\n\n"
5898 << " return false;\n"
5899 << "}\n\n";
5900
5901 const MatchTable Table =
5902 buildMatchTable(Rules, OptimizeMatchTable, GenerateCoverage);
5903 OS << "const int64_t *" << Target.getName()
5904 << "InstructionSelector::getMatchTable() const {\n";
5905 Table.emitDeclaration(OS);
5906 OS << " return ";
5907 Table.emitUse(OS);
5908 OS << ";\n}\n";
5909 OS << "#endif // ifdef GET_GLOBALISEL_IMPL\n";
5910
5911 OS << "#ifdef GET_GLOBALISEL_PREDICATES_DECL\n"
5912 << "PredicateBitset AvailableModuleFeatures;\n"
5913 << "mutable PredicateBitset AvailableFunctionFeatures;\n"
5914 << "PredicateBitset getAvailableFeatures() const {\n"
5915 << " return AvailableModuleFeatures | AvailableFunctionFeatures;\n"
5916 << "}\n"
5917 << "PredicateBitset\n"
5918 << "computeAvailableModuleFeatures(const " << Target.getName()
5919 << "Subtarget *Subtarget) const;\n"
5920 << "PredicateBitset\n"
5921 << "computeAvailableFunctionFeatures(const " << Target.getName()
5922 << "Subtarget *Subtarget,\n"
5923 << " const MachineFunction *MF) const;\n"
5924 << "void setupGeneratedPerFunctionState(MachineFunction &MF) override;\n"
5925 << "#endif // ifdef GET_GLOBALISEL_PREDICATES_DECL\n";
5926
5927 OS << "#ifdef GET_GLOBALISEL_PREDICATES_INIT\n"
5928 << "AvailableModuleFeatures(computeAvailableModuleFeatures(&STI)),\n"
5929 << "AvailableFunctionFeatures()\n"
5930 << "#endif // ifdef GET_GLOBALISEL_PREDICATES_INIT\n";
5931 }
5932
declareSubtargetFeature(Record * Predicate)5933 void GlobalISelEmitter::declareSubtargetFeature(Record *Predicate) {
5934 if (SubtargetFeatures.count(Predicate) == 0)
5935 SubtargetFeatures.emplace(
5936 Predicate, SubtargetFeatureInfo(Predicate, SubtargetFeatures.size()));
5937 }
5938
optimize()5939 void RuleMatcher::optimize() {
5940 for (auto &Item : InsnVariableIDs) {
5941 InstructionMatcher &InsnMatcher = *Item.first;
5942 for (auto &OM : InsnMatcher.operands()) {
5943 // Complex Patterns are usually expensive and they relatively rarely fail
5944 // on their own: more often we end up throwing away all the work done by a
5945 // matching part of a complex pattern because some other part of the
5946 // enclosing pattern didn't match. All of this makes it beneficial to
5947 // delay complex patterns until the very end of the rule matching,
5948 // especially for targets having lots of complex patterns.
5949 for (auto &OP : OM->predicates())
5950 if (isa<ComplexPatternOperandMatcher>(OP))
5951 EpilogueMatchers.emplace_back(std::move(OP));
5952 OM->eraseNullPredicates();
5953 }
5954 InsnMatcher.optimize();
5955 }
5956 llvm::sort(EpilogueMatchers, [](const std::unique_ptr<PredicateMatcher> &L,
5957 const std::unique_ptr<PredicateMatcher> &R) {
5958 return std::make_tuple(L->getKind(), L->getInsnVarID(), L->getOpIdx()) <
5959 std::make_tuple(R->getKind(), R->getInsnVarID(), R->getOpIdx());
5960 });
5961 }
5962
hasFirstCondition() const5963 bool RuleMatcher::hasFirstCondition() const {
5964 if (insnmatchers_empty())
5965 return false;
5966 InstructionMatcher &Matcher = insnmatchers_front();
5967 if (!Matcher.predicates_empty())
5968 return true;
5969 for (auto &OM : Matcher.operands())
5970 for (auto &OP : OM->predicates())
5971 if (!isa<InstructionOperandMatcher>(OP))
5972 return true;
5973 return false;
5974 }
5975
getFirstCondition() const5976 const PredicateMatcher &RuleMatcher::getFirstCondition() const {
5977 assert(!insnmatchers_empty() &&
5978 "Trying to get a condition from an empty RuleMatcher");
5979
5980 InstructionMatcher &Matcher = insnmatchers_front();
5981 if (!Matcher.predicates_empty())
5982 return **Matcher.predicates_begin();
5983 // If there is no more predicate on the instruction itself, look at its
5984 // operands.
5985 for (auto &OM : Matcher.operands())
5986 for (auto &OP : OM->predicates())
5987 if (!isa<InstructionOperandMatcher>(OP))
5988 return *OP;
5989
5990 llvm_unreachable("Trying to get a condition from an InstructionMatcher with "
5991 "no conditions");
5992 }
5993
popFirstCondition()5994 std::unique_ptr<PredicateMatcher> RuleMatcher::popFirstCondition() {
5995 assert(!insnmatchers_empty() &&
5996 "Trying to pop a condition from an empty RuleMatcher");
5997
5998 InstructionMatcher &Matcher = insnmatchers_front();
5999 if (!Matcher.predicates_empty())
6000 return Matcher.predicates_pop_front();
6001 // If there is no more predicate on the instruction itself, look at its
6002 // operands.
6003 for (auto &OM : Matcher.operands())
6004 for (auto &OP : OM->predicates())
6005 if (!isa<InstructionOperandMatcher>(OP)) {
6006 std::unique_ptr<PredicateMatcher> Result = std::move(OP);
6007 OM->eraseNullPredicates();
6008 return Result;
6009 }
6010
6011 llvm_unreachable("Trying to pop a condition from an InstructionMatcher with "
6012 "no conditions");
6013 }
6014
candidateConditionMatches(const PredicateMatcher & Predicate) const6015 bool GroupMatcher::candidateConditionMatches(
6016 const PredicateMatcher &Predicate) const {
6017
6018 if (empty()) {
6019 // Sharing predicates for nested instructions is not supported yet as we
6020 // currently don't hoist the GIM_RecordInsn's properly, therefore we can
6021 // only work on the original root instruction (InsnVarID == 0):
6022 if (Predicate.getInsnVarID() != 0)
6023 return false;
6024 // ... otherwise an empty group can handle any predicate with no specific
6025 // requirements:
6026 return true;
6027 }
6028
6029 const Matcher &Representative = **Matchers.begin();
6030 const auto &RepresentativeCondition = Representative.getFirstCondition();
6031 // ... if not empty, the group can only accomodate matchers with the exact
6032 // same first condition:
6033 return Predicate.isIdentical(RepresentativeCondition);
6034 }
6035
addMatcher(Matcher & Candidate)6036 bool GroupMatcher::addMatcher(Matcher &Candidate) {
6037 if (!Candidate.hasFirstCondition())
6038 return false;
6039
6040 const PredicateMatcher &Predicate = Candidate.getFirstCondition();
6041 if (!candidateConditionMatches(Predicate))
6042 return false;
6043
6044 Matchers.push_back(&Candidate);
6045 return true;
6046 }
6047
finalize()6048 void GroupMatcher::finalize() {
6049 assert(Conditions.empty() && "Already finalized?");
6050 if (empty())
6051 return;
6052
6053 Matcher &FirstRule = **Matchers.begin();
6054 for (;;) {
6055 // All the checks are expected to succeed during the first iteration:
6056 for (const auto &Rule : Matchers)
6057 if (!Rule->hasFirstCondition())
6058 return;
6059 const auto &FirstCondition = FirstRule.getFirstCondition();
6060 for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
6061 if (!Matchers[I]->getFirstCondition().isIdentical(FirstCondition))
6062 return;
6063
6064 Conditions.push_back(FirstRule.popFirstCondition());
6065 for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
6066 Matchers[I]->popFirstCondition();
6067 }
6068 }
6069
emit(MatchTable & Table)6070 void GroupMatcher::emit(MatchTable &Table) {
6071 unsigned LabelID = ~0U;
6072 if (!Conditions.empty()) {
6073 LabelID = Table.allocateLabelID();
6074 Table << MatchTable::Opcode("GIM_Try", +1)
6075 << MatchTable::Comment("On fail goto")
6076 << MatchTable::JumpTarget(LabelID) << MatchTable::LineBreak;
6077 }
6078 for (auto &Condition : Conditions)
6079 Condition->emitPredicateOpcodes(
6080 Table, *static_cast<RuleMatcher *>(*Matchers.begin()));
6081
6082 for (const auto &M : Matchers)
6083 M->emit(Table);
6084
6085 // Exit the group
6086 if (!Conditions.empty())
6087 Table << MatchTable::Opcode("GIM_Reject", -1) << MatchTable::LineBreak
6088 << MatchTable::Label(LabelID);
6089 }
6090
isSupportedPredicateType(const PredicateMatcher & P)6091 bool SwitchMatcher::isSupportedPredicateType(const PredicateMatcher &P) {
6092 return isa<InstructionOpcodeMatcher>(P) || isa<LLTOperandMatcher>(P);
6093 }
6094
candidateConditionMatches(const PredicateMatcher & Predicate) const6095 bool SwitchMatcher::candidateConditionMatches(
6096 const PredicateMatcher &Predicate) const {
6097
6098 if (empty()) {
6099 // Sharing predicates for nested instructions is not supported yet as we
6100 // currently don't hoist the GIM_RecordInsn's properly, therefore we can
6101 // only work on the original root instruction (InsnVarID == 0):
6102 if (Predicate.getInsnVarID() != 0)
6103 return false;
6104 // ... while an attempt to add even a root matcher to an empty SwitchMatcher
6105 // could fail as not all the types of conditions are supported:
6106 if (!isSupportedPredicateType(Predicate))
6107 return false;
6108 // ... or the condition might not have a proper implementation of
6109 // getValue() / isIdenticalDownToValue() yet:
6110 if (!Predicate.hasValue())
6111 return false;
6112 // ... otherwise an empty Switch can accomodate the condition with no
6113 // further requirements:
6114 return true;
6115 }
6116
6117 const Matcher &CaseRepresentative = **Matchers.begin();
6118 const auto &RepresentativeCondition = CaseRepresentative.getFirstCondition();
6119 // Switch-cases must share the same kind of condition and path to the value it
6120 // checks:
6121 if (!Predicate.isIdenticalDownToValue(RepresentativeCondition))
6122 return false;
6123
6124 const auto Value = Predicate.getValue();
6125 // ... but be unique with respect to the actual value they check:
6126 return Values.count(Value) == 0;
6127 }
6128
addMatcher(Matcher & Candidate)6129 bool SwitchMatcher::addMatcher(Matcher &Candidate) {
6130 if (!Candidate.hasFirstCondition())
6131 return false;
6132
6133 const PredicateMatcher &Predicate = Candidate.getFirstCondition();
6134 if (!candidateConditionMatches(Predicate))
6135 return false;
6136 const auto Value = Predicate.getValue();
6137 Values.insert(Value);
6138
6139 Matchers.push_back(&Candidate);
6140 return true;
6141 }
6142
finalize()6143 void SwitchMatcher::finalize() {
6144 assert(Condition == nullptr && "Already finalized");
6145 assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");
6146 if (empty())
6147 return;
6148
6149 llvm::stable_sort(Matchers, [](const Matcher *L, const Matcher *R) {
6150 return L->getFirstCondition().getValue() <
6151 R->getFirstCondition().getValue();
6152 });
6153 Condition = Matchers[0]->popFirstCondition();
6154 for (unsigned I = 1, E = Values.size(); I < E; ++I)
6155 Matchers[I]->popFirstCondition();
6156 }
6157
emitPredicateSpecificOpcodes(const PredicateMatcher & P,MatchTable & Table)6158 void SwitchMatcher::emitPredicateSpecificOpcodes(const PredicateMatcher &P,
6159 MatchTable &Table) {
6160 assert(isSupportedPredicateType(P) && "Predicate type is not supported");
6161
6162 if (const auto *Condition = dyn_cast<InstructionOpcodeMatcher>(&P)) {
6163 Table << MatchTable::Opcode("GIM_SwitchOpcode") << MatchTable::Comment("MI")
6164 << MatchTable::IntValue(Condition->getInsnVarID());
6165 return;
6166 }
6167 if (const auto *Condition = dyn_cast<LLTOperandMatcher>(&P)) {
6168 Table << MatchTable::Opcode("GIM_SwitchType") << MatchTable::Comment("MI")
6169 << MatchTable::IntValue(Condition->getInsnVarID())
6170 << MatchTable::Comment("Op")
6171 << MatchTable::IntValue(Condition->getOpIdx());
6172 return;
6173 }
6174
6175 llvm_unreachable("emitPredicateSpecificOpcodes is broken: can not handle a "
6176 "predicate type that is claimed to be supported");
6177 }
6178
emit(MatchTable & Table)6179 void SwitchMatcher::emit(MatchTable &Table) {
6180 assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");
6181 if (empty())
6182 return;
6183 assert(Condition != nullptr &&
6184 "Broken SwitchMatcher, hasn't been finalized?");
6185
6186 std::vector<unsigned> LabelIDs(Values.size());
6187 std::generate(LabelIDs.begin(), LabelIDs.end(),
6188 [&Table]() { return Table.allocateLabelID(); });
6189 const unsigned Default = Table.allocateLabelID();
6190
6191 const int64_t LowerBound = Values.begin()->getRawValue();
6192 const int64_t UpperBound = Values.rbegin()->getRawValue() + 1;
6193
6194 emitPredicateSpecificOpcodes(*Condition, Table);
6195
6196 Table << MatchTable::Comment("[") << MatchTable::IntValue(LowerBound)
6197 << MatchTable::IntValue(UpperBound) << MatchTable::Comment(")")
6198 << MatchTable::Comment("default:") << MatchTable::JumpTarget(Default);
6199
6200 int64_t J = LowerBound;
6201 auto VI = Values.begin();
6202 for (unsigned I = 0, E = Values.size(); I < E; ++I) {
6203 auto V = *VI++;
6204 while (J++ < V.getRawValue())
6205 Table << MatchTable::IntValue(0);
6206 V.turnIntoComment();
6207 Table << MatchTable::LineBreak << V << MatchTable::JumpTarget(LabelIDs[I]);
6208 }
6209 Table << MatchTable::LineBreak;
6210
6211 for (unsigned I = 0, E = Values.size(); I < E; ++I) {
6212 Table << MatchTable::Label(LabelIDs[I]);
6213 Matchers[I]->emit(Table);
6214 Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
6215 }
6216 Table << MatchTable::Label(Default);
6217 }
6218
getInsnVarID() const6219 unsigned OperandMatcher::getInsnVarID() const { return Insn.getInsnVarID(); }
6220
6221 } // end anonymous namespace
6222
6223 //===----------------------------------------------------------------------===//
6224
6225 namespace llvm {
EmitGlobalISel(RecordKeeper & RK,raw_ostream & OS)6226 void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS) {
6227 GlobalISelEmitter(RK).run(OS);
6228 }
6229 } // End llvm namespace
6230