xref: /freebsd/contrib/llvm-project/llvm/utils/TableGen/GlobalISelEmitter.cpp (revision 517e52b6c21ccff22c46df0dcd15c19baee3d86c)
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.
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.
93 std::string getMatchOpcodeForPredicate(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;
105   LLTCodeGen(const LLT &Ty) : Ty(Ty) {}
106 
107   std::string getCxxEnumValue() const {
108     std::string Str;
109     raw_string_ostream OS(Str);
110 
111     emitCxxEnumValue(OS);
112     return OS.str();
113   }
114 
115   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 
133   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 
151   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.
156   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 
178   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, ...).
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 
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 
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.
303 static Error failedImport(const Twine &Reason) {
304   return make_error<StringError>(Reason, inconvertibleErrorCode());
305 }
306 
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 
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
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 
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 
453   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
465   void turnIntoComment() {
466     Flags |= MTRF_Comment;
467     Flags &= ~MTRF_CommaFollows;
468     NumElements = 0;
469   }
470 
471   /// For Jump Table generation purposes
472   bool operator<(const MatchTableRecord &Other) const {
473     return RawValue < Other.RawValue;
474   }
475   int64_t getRawValue() const { return RawValue; }
476 
477   void emit(raw_ostream &OS, bool LineBreakNextAfterThis,
478             const MatchTable &Table) const;
479   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;
504   static MatchTableRecord Comment(StringRef Comment) {
505     return MatchTableRecord(None, Comment, 0, MatchTableRecord::MTRF_Comment);
506   }
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   }
517   static MatchTableRecord NamedValue(StringRef NamedValue) {
518     return MatchTableRecord(None, NamedValue, 1,
519                             MatchTableRecord::MTRF_CommaFollows);
520   }
521   static MatchTableRecord NamedValue(StringRef NamedValue, int64_t RawValue) {
522     return MatchTableRecord(None, NamedValue, 1,
523                             MatchTableRecord::MTRF_CommaFollows, RawValue);
524   }
525   static MatchTableRecord NamedValue(StringRef Namespace,
526                                      StringRef NamedValue) {
527     return MatchTableRecord(None, (Namespace + "::" + NamedValue).str(), 1,
528                             MatchTableRecord::MTRF_CommaFollows);
529   }
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   }
535   static MatchTableRecord IntValue(int64_t IntValue) {
536     return MatchTableRecord(None, llvm::to_string(IntValue), 1,
537                             MatchTableRecord::MTRF_CommaFollows);
538   }
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   }
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 
554   MatchTable(bool WithCoverage, unsigned ID = 0)
555       : ID(ID), IsWithCoverage(WithCoverage) {}
556 
557   bool isWithCoverage() const { return IsWithCoverage; }
558 
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 
566   unsigned allocateLabelID() { return CurrentLabelID++; }
567 
568   void defineLabel(unsigned LabelID) {
569     LabelMap.insert(std::make_pair(LabelID, CurrentSize));
570   }
571 
572   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 
578   void emitUse(raw_ostream &OS) const { OS << "MatchTable" << ID; }
579 
580   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 
615 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 
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;
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 
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.
725   iterator_range<std::vector<Matcher *>::iterator> matchers() {
726     return make_range(Matchers.begin(), Matchers.end());
727   }
728   size_t size() const { return Matchers.size(); }
729   bool empty() const { return Matchers.empty(); }
730 
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   }
738   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   }
743   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 
777   iterator_range<std::vector<Matcher *>::iterator> matchers() {
778     return make_range(Matchers.begin(), Matchers.end());
779   }
780   size_t size() const { return Matchers.size(); }
781   bool empty() const { return Matchers.empty(); }
782 
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   }
789   const PredicateMatcher &getFirstCondition() const override {
790     llvm_unreachable("Trying to pop a condition from a condition-less group");
791   }
792   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:
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 
880   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;
894   DefinedInsnVariablesMap::const_iterator defined_insn_vars_begin() const {
895     return InsnVariableIDs.begin();
896   }
897   DefinedInsnVariablesMap::const_iterator defined_insn_vars_end() const {
898     return InsnVariableIDs.end();
899   }
900   iterator_range<typename DefinedInsnVariablesMap::const_iterator>
901   defined_insn_vars() const {
902     return make_range(defined_insn_vars_begin(), defined_insn_vars_end());
903   }
904 
905   MutatableInsnSet::const_iterator mutatable_insns_begin() const {
906     return MutatableInsns.begin();
907   }
908   MutatableInsnSet::const_iterator mutatable_insns_end() const {
909     return MutatableInsns.end();
910   }
911   iterator_range<typename MutatableInsnSet::const_iterator>
912   mutatable_insns() const {
913     return make_range(mutatable_insns_begin(), mutatable_insns_end());
914   }
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 
921   action_iterator actions_begin() { return Actions.begin(); }
922   action_iterator actions_end() { return Actions.end(); }
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 
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>
956   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
987   InstructionMatcher &insnmatchers_front() const { return *Matchers.front(); }
988 
989   unsigned allocateOutputInsnID() { return NextOutputInsnID++; }
990   unsigned allocateTempRegID() { return NextTempRegID++; }
991 
992   iterator_range<MatchersTy::iterator> insnmatchers() {
993     return make_range(Matchers.begin(), Matchers.end());
994   }
995   bool insnmatchers_empty() const { return Matchers.empty(); }
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:
1018   typename PredicatesTy::iterator predicates_begin() {
1019     return Predicates.begin();
1020   }
1021   typename PredicatesTy::iterator predicates_end() {
1022     return Predicates.end();
1023   }
1024   iterator_range<typename PredicatesTy::iterator> predicates() {
1025     return make_range(predicates_begin(), predicates_end());
1026   }
1027   typename PredicatesTy::size_type predicates_size() const {
1028     return Predicates.size();
1029   }
1030   bool predicates_empty() const { return Predicates.empty(); }
1031 
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 
1039   void prependPredicate(std::unique_ptr<PredicateTy> &&Predicate) {
1040     Predicates.push_front(std::move(Predicate));
1041   }
1042 
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>
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>
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:
1133   PredicateMatcher(PredicateKind Kind, unsigned InsnVarID, unsigned OpIdx = ~0)
1134       : Kind(Kind), InsnVarID(InsnVarID), OpIdx(OpIdx) {}
1135 
1136   unsigned getInsnVarID() const { return InsnVarID; }
1137   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 
1144   PredicateKind getKind() const { return Kind; }
1145 
1146   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 
1153   virtual bool isIdentical(const PredicateMatcher &B) const {
1154     return B.getKind() == getKind() && InsnVarID == B.InsnVarID &&
1155            OpIdx == B.OpIdx;
1156   }
1157 
1158   virtual bool isIdenticalDownToValue(const PredicateMatcher &B) const {
1159     return hasValue() && PredicateMatcher::isIdentical(B);
1160   }
1161 
1162   virtual MatchTableRecord getValue() const {
1163     assert(hasValue() && "Can not get a value of a value-less predicate!");
1164     llvm_unreachable("Not implemented yet");
1165   }
1166   virtual bool hasValue() const { return false; }
1167 
1168   /// Report the maximum number of temporary operands needed by the predicate
1169   /// matcher.
1170   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:
1181   OperandPredicateMatcher(PredicateKind Kind, unsigned InsnVarID,
1182                           unsigned OpIdx)
1183       : PredicateMatcher(Kind, InsnVarID, OpIdx) {}
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
1194 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:
1204   SameOperandMatcher(unsigned InsnVarID, unsigned OpIdx, StringRef MatchingName)
1205       : OperandPredicateMatcher(OPM_SameOperand, InsnVarID, OpIdx),
1206         MatchingName(MatchingName) {}
1207 
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 
1215   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 
1229   static void initTypeIDValuesMap() {
1230     TypeIDValues.clear();
1231 
1232     unsigned ID = 0;
1233     for (const LLTCodeGen &LLTy : KnownTypes)
1234       TypeIDValues[LLTy] = ID++;
1235   }
1236 
1237   LLTOperandMatcher(unsigned InsnVarID, unsigned OpIdx, const LLTCodeGen &Ty)
1238       : OperandPredicateMatcher(OPM_LLT, InsnVarID, OpIdx), Ty(Ty) {
1239     KnownTypes.insert(Ty);
1240   }
1241 
1242   static bool classof(const PredicateMatcher *P) {
1243     return P->getKind() == OPM_LLT;
1244   }
1245   bool isIdentical(const PredicateMatcher &B) const override {
1246     return OperandPredicateMatcher::isIdentical(B) &&
1247            Ty == cast<LLTOperandMatcher>(&B)->Ty;
1248   }
1249   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   }
1255   bool hasValue() const override {
1256     if (TypeIDValues.size() != KnownTypes.size())
1257       initTypeIDValuesMap();
1258     return TypeIDValues.count(Ty);
1259   }
1260 
1261   LLTCodeGen getTy() const { return Ty; }
1262 
1263   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:
1289   PointerToAnyOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1290                              unsigned SizeInBits)
1291       : OperandPredicateMatcher(OPM_PointerToAny, InsnVarID, OpIdx),
1292         SizeInBits(SizeInBits) {}
1293 
1294   static bool classof(const PredicateMatcher *P) {
1295     return P->getKind() == OPM_PointerToAny;
1296   }
1297 
1298   bool isIdentical(const PredicateMatcher &B) const override {
1299     return OperandPredicateMatcher::isIdentical(B) &&
1300            SizeInBits == cast<PointerToAnyOperandMatcher>(&B)->SizeInBits;
1301   }
1302 
1303   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:
1322   RecordNamedOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1323                             unsigned StoreIdx, StringRef Name)
1324       : OperandPredicateMatcher(OPM_RecordNamedOperand, InsnVarID, OpIdx),
1325         StoreIdx(StoreIdx), Name(Name) {}
1326 
1327   static bool classof(const PredicateMatcher *P) {
1328     return P->getKind() == OPM_RecordNamedOperand;
1329   }
1330 
1331   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 
1337   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:
1356   bool isIdentical(const PredicateMatcher &B) const override { return false; }
1357 
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 
1364   static bool classof(const PredicateMatcher *P) {
1365     return P->getKind() == OPM_ComplexPattern;
1366   }
1367 
1368   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 
1379   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:
1390   RegisterBankOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1391                              const CodeGenRegisterClass &RC)
1392       : OperandPredicateMatcher(OPM_RegBank, InsnVarID, OpIdx), RC(RC) {}
1393 
1394   bool isIdentical(const PredicateMatcher &B) const override {
1395     return OperandPredicateMatcher::isIdentical(B) &&
1396            RC.getDef() == cast<RegisterBankOperandMatcher>(&B)->RC.getDef();
1397   }
1398 
1399   static bool classof(const PredicateMatcher *P) {
1400     return P->getKind() == OPM_RegBank;
1401   }
1402 
1403   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:
1417   MBBOperandMatcher(unsigned InsnVarID, unsigned OpIdx)
1418       : OperandPredicateMatcher(OPM_MBB, InsnVarID, OpIdx) {}
1419 
1420   static bool classof(const PredicateMatcher *P) {
1421     return P->getKind() == OPM_MBB;
1422   }
1423 
1424   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:
1434   ImmOperandMatcher(unsigned InsnVarID, unsigned OpIdx)
1435       : OperandPredicateMatcher(IPM_Imm, InsnVarID, OpIdx) {}
1436 
1437   static bool classof(const PredicateMatcher *P) {
1438     return P->getKind() == IPM_Imm;
1439   }
1440 
1441   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:
1456   ConstantIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value)
1457       : OperandPredicateMatcher(OPM_Int, InsnVarID, OpIdx), Value(Value) {}
1458 
1459   bool isIdentical(const PredicateMatcher &B) const override {
1460     return OperandPredicateMatcher::isIdentical(B) &&
1461            Value == cast<ConstantIntOperandMatcher>(&B)->Value;
1462   }
1463 
1464   static bool classof(const PredicateMatcher *P) {
1465     return P->getKind() == OPM_Int;
1466   }
1467 
1468   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:
1484   LiteralIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value)
1485       : OperandPredicateMatcher(OPM_LiteralInt, InsnVarID, OpIdx),
1486         Value(Value) {}
1487 
1488   bool isIdentical(const PredicateMatcher &B) const override {
1489     return OperandPredicateMatcher::isIdentical(B) &&
1490            Value == cast<LiteralIntOperandMatcher>(&B)->Value;
1491   }
1492 
1493   static bool classof(const PredicateMatcher *P) {
1494     return P->getKind() == OPM_LiteralInt;
1495   }
1496 
1497   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:
1512   CmpPredicateOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1513                              std::string P)
1514     : OperandPredicateMatcher(OPM_CmpPredicate, InsnVarID, OpIdx), PredName(P) {}
1515 
1516   bool isIdentical(const PredicateMatcher &B) const override {
1517     return OperandPredicateMatcher::isIdentical(B) &&
1518            PredName == cast<CmpPredicateOperandMatcher>(&B)->PredName;
1519   }
1520 
1521   static bool classof(const PredicateMatcher *P) {
1522     return P->getKind() == OPM_CmpPredicate;
1523   }
1524 
1525   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:
1542   IntrinsicIDOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1543                             const CodeGenIntrinsic *II)
1544       : OperandPredicateMatcher(OPM_IntrinsicID, InsnVarID, OpIdx), II(II) {}
1545 
1546   bool isIdentical(const PredicateMatcher &B) const override {
1547     return OperandPredicateMatcher::isIdentical(B) &&
1548            II == cast<IntrinsicIDOperandMatcher>(&B)->II;
1549   }
1550 
1551   static bool classof(const PredicateMatcher *P) {
1552     return P->getKind() == OPM_IntrinsicID;
1553   }
1554 
1555   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 a set of predicates match for a particular
1566 /// operand.
1567 class OperandMatcher : public PredicateListMatcher<OperandPredicateMatcher> {
1568 protected:
1569   InstructionMatcher &Insn;
1570   unsigned OpIdx;
1571   std::string SymbolicName;
1572 
1573   /// The index of the first temporary variable allocated to this operand. The
1574   /// number of allocated temporaries can be found with
1575   /// countRendererFns().
1576   unsigned AllocatedTemporariesBaseID;
1577 
1578 public:
1579   OperandMatcher(InstructionMatcher &Insn, unsigned OpIdx,
1580                  const std::string &SymbolicName,
1581                  unsigned AllocatedTemporariesBaseID)
1582       : Insn(Insn), OpIdx(OpIdx), SymbolicName(SymbolicName),
1583         AllocatedTemporariesBaseID(AllocatedTemporariesBaseID) {}
1584 
1585   bool hasSymbolicName() const { return !SymbolicName.empty(); }
1586   StringRef getSymbolicName() const { return SymbolicName; }
1587   void setSymbolicName(StringRef Name) {
1588     assert(SymbolicName.empty() && "Operand already has a symbolic name");
1589     SymbolicName = std::string(Name);
1590   }
1591 
1592   /// Construct a new operand predicate and add it to the matcher.
1593   template <class Kind, class... Args>
1594   Optional<Kind *> addPredicate(Args &&... args) {
1595     if (isSameAsAnotherOperand())
1596       return None;
1597     Predicates.emplace_back(std::make_unique<Kind>(
1598         getInsnVarID(), getOpIdx(), std::forward<Args>(args)...));
1599     return static_cast<Kind *>(Predicates.back().get());
1600   }
1601 
1602   unsigned getOpIdx() const { return OpIdx; }
1603   unsigned getInsnVarID() const;
1604 
1605   std::string getOperandExpr(unsigned InsnVarID) const {
1606     return "State.MIs[" + llvm::to_string(InsnVarID) + "]->getOperand(" +
1607            llvm::to_string(OpIdx) + ")";
1608   }
1609 
1610   InstructionMatcher &getInstructionMatcher() const { return Insn; }
1611 
1612   Error addTypeCheckPredicate(const TypeSetByHwMode &VTy,
1613                               bool OperandIsAPointer);
1614 
1615   /// Emit MatchTable opcodes that test whether the instruction named in
1616   /// InsnVarID matches all the predicates and all the operands.
1617   void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) {
1618     if (!Optimized) {
1619       std::string Comment;
1620       raw_string_ostream CommentOS(Comment);
1621       CommentOS << "MIs[" << getInsnVarID() << "] ";
1622       if (SymbolicName.empty())
1623         CommentOS << "Operand " << OpIdx;
1624       else
1625         CommentOS << SymbolicName;
1626       Table << MatchTable::Comment(CommentOS.str()) << MatchTable::LineBreak;
1627     }
1628 
1629     emitPredicateListOpcodes(Table, Rule);
1630   }
1631 
1632   /// Compare the priority of this object and B.
1633   ///
1634   /// Returns true if this object is more important than B.
1635   bool isHigherPriorityThan(OperandMatcher &B) {
1636     // Operand matchers involving more predicates have higher priority.
1637     if (predicates_size() > B.predicates_size())
1638       return true;
1639     if (predicates_size() < B.predicates_size())
1640       return false;
1641 
1642     // This assumes that predicates are added in a consistent order.
1643     for (auto &&Predicate : zip(predicates(), B.predicates())) {
1644       if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate)))
1645         return true;
1646       if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate)))
1647         return false;
1648     }
1649 
1650     return false;
1651   };
1652 
1653   /// Report the maximum number of temporary operands needed by the operand
1654   /// matcher.
1655   unsigned countRendererFns() {
1656     return std::accumulate(
1657         predicates().begin(), predicates().end(), 0,
1658         [](unsigned A,
1659            const std::unique_ptr<OperandPredicateMatcher> &Predicate) {
1660           return A + Predicate->countRendererFns();
1661         });
1662   }
1663 
1664   unsigned getAllocatedTemporariesBaseID() const {
1665     return AllocatedTemporariesBaseID;
1666   }
1667 
1668   bool isSameAsAnotherOperand() {
1669     for (const auto &Predicate : predicates())
1670       if (isa<SameOperandMatcher>(Predicate))
1671         return true;
1672     return false;
1673   }
1674 };
1675 
1676 Error OperandMatcher::addTypeCheckPredicate(const TypeSetByHwMode &VTy,
1677                                             bool OperandIsAPointer) {
1678   if (!VTy.isMachineValueType())
1679     return failedImport("unsupported typeset");
1680 
1681   if (VTy.getMachineValueType() == MVT::iPTR && OperandIsAPointer) {
1682     addPredicate<PointerToAnyOperandMatcher>(0);
1683     return Error::success();
1684   }
1685 
1686   auto OpTyOrNone = MVTToLLT(VTy.getMachineValueType().SimpleTy);
1687   if (!OpTyOrNone)
1688     return failedImport("unsupported type");
1689 
1690   if (OperandIsAPointer)
1691     addPredicate<PointerToAnyOperandMatcher>(OpTyOrNone->get().getSizeInBits());
1692   else if (VTy.isPointer())
1693     addPredicate<LLTOperandMatcher>(LLT::pointer(VTy.getPtrAddrSpace(),
1694                                                  OpTyOrNone->get().getSizeInBits()));
1695   else
1696     addPredicate<LLTOperandMatcher>(*OpTyOrNone);
1697   return Error::success();
1698 }
1699 
1700 unsigned ComplexPatternOperandMatcher::getAllocatedTemporariesBaseID() const {
1701   return Operand.getAllocatedTemporariesBaseID();
1702 }
1703 
1704 /// Generates code to check a predicate on an instruction.
1705 ///
1706 /// Typical predicates include:
1707 /// * The opcode of the instruction is a particular value.
1708 /// * The nsw/nuw flag is/isn't set.
1709 class InstructionPredicateMatcher : public PredicateMatcher {
1710 public:
1711   InstructionPredicateMatcher(PredicateKind Kind, unsigned InsnVarID)
1712       : PredicateMatcher(Kind, InsnVarID) {}
1713   virtual ~InstructionPredicateMatcher() {}
1714 
1715   /// Compare the priority of this object and B.
1716   ///
1717   /// Returns true if this object is more important than B.
1718   virtual bool
1719   isHigherPriorityThan(const InstructionPredicateMatcher &B) const {
1720     return Kind < B.Kind;
1721   };
1722 };
1723 
1724 template <>
1725 std::string
1726 PredicateListMatcher<PredicateMatcher>::getNoPredicateComment() const {
1727   return "No instruction predicates";
1728 }
1729 
1730 /// Generates code to check the opcode of an instruction.
1731 class InstructionOpcodeMatcher : public InstructionPredicateMatcher {
1732 protected:
1733   // Allow matching one to several, similar opcodes that share properties. This
1734   // is to handle patterns where one SelectionDAG operation maps to multiple
1735   // GlobalISel ones (e.g. G_BUILD_VECTOR and G_BUILD_VECTOR_TRUNC). The first
1736   // is treated as the canonical opcode.
1737   SmallVector<const CodeGenInstruction *, 2> Insts;
1738 
1739   static DenseMap<const CodeGenInstruction *, unsigned> OpcodeValues;
1740 
1741 
1742   MatchTableRecord getInstValue(const CodeGenInstruction *I) const {
1743     const auto VI = OpcodeValues.find(I);
1744     if (VI != OpcodeValues.end())
1745       return MatchTable::NamedValue(I->Namespace, I->TheDef->getName(),
1746                                     VI->second);
1747     return MatchTable::NamedValue(I->Namespace, I->TheDef->getName());
1748   }
1749 
1750 public:
1751   static void initOpcodeValuesMap(const CodeGenTarget &Target) {
1752     OpcodeValues.clear();
1753 
1754     unsigned OpcodeValue = 0;
1755     for (const CodeGenInstruction *I : Target.getInstructionsByEnumValue())
1756       OpcodeValues[I] = OpcodeValue++;
1757   }
1758 
1759   InstructionOpcodeMatcher(unsigned InsnVarID,
1760                            ArrayRef<const CodeGenInstruction *> I)
1761       : InstructionPredicateMatcher(IPM_Opcode, InsnVarID),
1762         Insts(I.begin(), I.end()) {
1763     assert((Insts.size() == 1 || Insts.size() == 2) &&
1764            "unexpected number of opcode alternatives");
1765   }
1766 
1767   static bool classof(const PredicateMatcher *P) {
1768     return P->getKind() == IPM_Opcode;
1769   }
1770 
1771   bool isIdentical(const PredicateMatcher &B) const override {
1772     return InstructionPredicateMatcher::isIdentical(B) &&
1773            Insts == cast<InstructionOpcodeMatcher>(&B)->Insts;
1774   }
1775 
1776   bool hasValue() const override {
1777     return Insts.size() == 1 && OpcodeValues.count(Insts[0]);
1778   }
1779 
1780   // TODO: This is used for the SwitchMatcher optimization. We should be able to
1781   // return a list of the opcodes to match.
1782   MatchTableRecord getValue() const override {
1783     assert(Insts.size() == 1);
1784 
1785     const CodeGenInstruction *I = Insts[0];
1786     const auto VI = OpcodeValues.find(I);
1787     if (VI != OpcodeValues.end())
1788       return MatchTable::NamedValue(I->Namespace, I->TheDef->getName(),
1789                                     VI->second);
1790     return MatchTable::NamedValue(I->Namespace, I->TheDef->getName());
1791   }
1792 
1793   void emitPredicateOpcodes(MatchTable &Table,
1794                             RuleMatcher &Rule) const override {
1795     StringRef CheckType = Insts.size() == 1 ?
1796                           "GIM_CheckOpcode" : "GIM_CheckOpcodeIsEither";
1797     Table << MatchTable::Opcode(CheckType) << MatchTable::Comment("MI")
1798           << MatchTable::IntValue(InsnVarID);
1799 
1800     for (const CodeGenInstruction *I : Insts)
1801       Table << getInstValue(I);
1802     Table << MatchTable::LineBreak;
1803   }
1804 
1805   /// Compare the priority of this object and B.
1806   ///
1807   /// Returns true if this object is more important than B.
1808   bool
1809   isHigherPriorityThan(const InstructionPredicateMatcher &B) const override {
1810     if (InstructionPredicateMatcher::isHigherPriorityThan(B))
1811       return true;
1812     if (B.InstructionPredicateMatcher::isHigherPriorityThan(*this))
1813       return false;
1814 
1815     // Prioritize opcodes for cosmetic reasons in the generated source. Although
1816     // this is cosmetic at the moment, we may want to drive a similar ordering
1817     // using instruction frequency information to improve compile time.
1818     if (const InstructionOpcodeMatcher *BO =
1819             dyn_cast<InstructionOpcodeMatcher>(&B))
1820       return Insts[0]->TheDef->getName() < BO->Insts[0]->TheDef->getName();
1821 
1822     return false;
1823   };
1824 
1825   bool isConstantInstruction() const {
1826     return Insts.size() == 1 && Insts[0]->TheDef->getName() == "G_CONSTANT";
1827   }
1828 
1829   // The first opcode is the canonical opcode, and later are alternatives.
1830   StringRef getOpcode() const {
1831     return Insts[0]->TheDef->getName();
1832   }
1833 
1834   ArrayRef<const CodeGenInstruction *> getAlternativeOpcodes() {
1835     return Insts;
1836   }
1837 
1838   bool isVariadicNumOperands() const {
1839     // If one is variadic, they all should be.
1840     return Insts[0]->Operands.isVariadic;
1841   }
1842 
1843   StringRef getOperandType(unsigned OpIdx) const {
1844     // Types expected to be uniform for all alternatives.
1845     return Insts[0]->Operands[OpIdx].OperandType;
1846   }
1847 };
1848 
1849 DenseMap<const CodeGenInstruction *, unsigned>
1850     InstructionOpcodeMatcher::OpcodeValues;
1851 
1852 class InstructionNumOperandsMatcher final : public InstructionPredicateMatcher {
1853   unsigned NumOperands = 0;
1854 
1855 public:
1856   InstructionNumOperandsMatcher(unsigned InsnVarID, unsigned NumOperands)
1857       : InstructionPredicateMatcher(IPM_NumOperands, InsnVarID),
1858         NumOperands(NumOperands) {}
1859 
1860   static bool classof(const PredicateMatcher *P) {
1861     return P->getKind() == IPM_NumOperands;
1862   }
1863 
1864   bool isIdentical(const PredicateMatcher &B) const override {
1865     return InstructionPredicateMatcher::isIdentical(B) &&
1866            NumOperands == cast<InstructionNumOperandsMatcher>(&B)->NumOperands;
1867   }
1868 
1869   void emitPredicateOpcodes(MatchTable &Table,
1870                             RuleMatcher &Rule) const override {
1871     Table << MatchTable::Opcode("GIM_CheckNumOperands")
1872           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1873           << MatchTable::Comment("Expected")
1874           << MatchTable::IntValue(NumOperands) << MatchTable::LineBreak;
1875   }
1876 };
1877 
1878 /// Generates code to check that this instruction is a constant whose value
1879 /// meets an immediate predicate.
1880 ///
1881 /// Immediates are slightly odd since they are typically used like an operand
1882 /// but are represented as an operator internally. We typically write simm8:$src
1883 /// in a tablegen pattern, but this is just syntactic sugar for
1884 /// (imm:i32)<<P:Predicate_simm8>>:$imm which more directly describes the nodes
1885 /// that will be matched and the predicate (which is attached to the imm
1886 /// operator) that will be tested. In SelectionDAG this describes a
1887 /// ConstantSDNode whose internal value will be tested using the simm8 predicate.
1888 ///
1889 /// The corresponding GlobalISel representation is %1 = G_CONSTANT iN Value. In
1890 /// this representation, the immediate could be tested with an
1891 /// InstructionMatcher, InstructionOpcodeMatcher, OperandMatcher, and a
1892 /// OperandPredicateMatcher-subclass to check the Value meets the predicate but
1893 /// there are two implementation issues with producing that matcher
1894 /// configuration from the SelectionDAG pattern:
1895 /// * ImmLeaf is a PatFrag whose root is an InstructionMatcher. This means that
1896 ///   were we to sink the immediate predicate to the operand we would have to
1897 ///   have two partial implementations of PatFrag support, one for immediates
1898 ///   and one for non-immediates.
1899 /// * At the point we handle the predicate, the OperandMatcher hasn't been
1900 ///   created yet. If we were to sink the predicate to the OperandMatcher we
1901 ///   would also have to complicate (or duplicate) the code that descends and
1902 ///   creates matchers for the subtree.
1903 /// Overall, it's simpler to handle it in the place it was found.
1904 class InstructionImmPredicateMatcher : public InstructionPredicateMatcher {
1905 protected:
1906   TreePredicateFn Predicate;
1907 
1908 public:
1909   InstructionImmPredicateMatcher(unsigned InsnVarID,
1910                                  const TreePredicateFn &Predicate)
1911       : InstructionPredicateMatcher(IPM_ImmPredicate, InsnVarID),
1912         Predicate(Predicate) {}
1913 
1914   bool isIdentical(const PredicateMatcher &B) const override {
1915     return InstructionPredicateMatcher::isIdentical(B) &&
1916            Predicate.getOrigPatFragRecord() ==
1917                cast<InstructionImmPredicateMatcher>(&B)
1918                    ->Predicate.getOrigPatFragRecord();
1919   }
1920 
1921   static bool classof(const PredicateMatcher *P) {
1922     return P->getKind() == IPM_ImmPredicate;
1923   }
1924 
1925   void emitPredicateOpcodes(MatchTable &Table,
1926                             RuleMatcher &Rule) const override {
1927     Table << MatchTable::Opcode(getMatchOpcodeForPredicate(Predicate))
1928           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1929           << MatchTable::Comment("Predicate")
1930           << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
1931           << MatchTable::LineBreak;
1932   }
1933 };
1934 
1935 /// Generates code to check that a memory instruction has a atomic ordering
1936 /// MachineMemoryOperand.
1937 class AtomicOrderingMMOPredicateMatcher : public InstructionPredicateMatcher {
1938 public:
1939   enum AOComparator {
1940     AO_Exactly,
1941     AO_OrStronger,
1942     AO_WeakerThan,
1943   };
1944 
1945 protected:
1946   StringRef Order;
1947   AOComparator Comparator;
1948 
1949 public:
1950   AtomicOrderingMMOPredicateMatcher(unsigned InsnVarID, StringRef Order,
1951                                     AOComparator Comparator = AO_Exactly)
1952       : InstructionPredicateMatcher(IPM_AtomicOrderingMMO, InsnVarID),
1953         Order(Order), Comparator(Comparator) {}
1954 
1955   static bool classof(const PredicateMatcher *P) {
1956     return P->getKind() == IPM_AtomicOrderingMMO;
1957   }
1958 
1959   bool isIdentical(const PredicateMatcher &B) const override {
1960     if (!InstructionPredicateMatcher::isIdentical(B))
1961       return false;
1962     const auto &R = *cast<AtomicOrderingMMOPredicateMatcher>(&B);
1963     return Order == R.Order && Comparator == R.Comparator;
1964   }
1965 
1966   void emitPredicateOpcodes(MatchTable &Table,
1967                             RuleMatcher &Rule) const override {
1968     StringRef Opcode = "GIM_CheckAtomicOrdering";
1969 
1970     if (Comparator == AO_OrStronger)
1971       Opcode = "GIM_CheckAtomicOrderingOrStrongerThan";
1972     if (Comparator == AO_WeakerThan)
1973       Opcode = "GIM_CheckAtomicOrderingWeakerThan";
1974 
1975     Table << MatchTable::Opcode(Opcode) << MatchTable::Comment("MI")
1976           << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Order")
1977           << MatchTable::NamedValue(("(int64_t)AtomicOrdering::" + Order).str())
1978           << MatchTable::LineBreak;
1979   }
1980 };
1981 
1982 /// Generates code to check that the size of an MMO is exactly N bytes.
1983 class MemorySizePredicateMatcher : public InstructionPredicateMatcher {
1984 protected:
1985   unsigned MMOIdx;
1986   uint64_t Size;
1987 
1988 public:
1989   MemorySizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, unsigned Size)
1990       : InstructionPredicateMatcher(IPM_MemoryLLTSize, InsnVarID),
1991         MMOIdx(MMOIdx), Size(Size) {}
1992 
1993   static bool classof(const PredicateMatcher *P) {
1994     return P->getKind() == IPM_MemoryLLTSize;
1995   }
1996   bool isIdentical(const PredicateMatcher &B) const override {
1997     return InstructionPredicateMatcher::isIdentical(B) &&
1998            MMOIdx == cast<MemorySizePredicateMatcher>(&B)->MMOIdx &&
1999            Size == cast<MemorySizePredicateMatcher>(&B)->Size;
2000   }
2001 
2002   void emitPredicateOpcodes(MatchTable &Table,
2003                             RuleMatcher &Rule) const override {
2004     Table << MatchTable::Opcode("GIM_CheckMemorySizeEqualTo")
2005           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
2006           << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
2007           << MatchTable::Comment("Size") << MatchTable::IntValue(Size)
2008           << MatchTable::LineBreak;
2009   }
2010 };
2011 
2012 class MemoryAddressSpacePredicateMatcher : public InstructionPredicateMatcher {
2013 protected:
2014   unsigned MMOIdx;
2015   SmallVector<unsigned, 4> AddrSpaces;
2016 
2017 public:
2018   MemoryAddressSpacePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
2019                                      ArrayRef<unsigned> AddrSpaces)
2020       : InstructionPredicateMatcher(IPM_MemoryAddressSpace, InsnVarID),
2021         MMOIdx(MMOIdx), AddrSpaces(AddrSpaces.begin(), AddrSpaces.end()) {}
2022 
2023   static bool classof(const PredicateMatcher *P) {
2024     return P->getKind() == IPM_MemoryAddressSpace;
2025   }
2026   bool isIdentical(const PredicateMatcher &B) const override {
2027     if (!InstructionPredicateMatcher::isIdentical(B))
2028       return false;
2029     auto *Other = cast<MemoryAddressSpacePredicateMatcher>(&B);
2030     return MMOIdx == Other->MMOIdx && AddrSpaces == Other->AddrSpaces;
2031   }
2032 
2033   void emitPredicateOpcodes(MatchTable &Table,
2034                             RuleMatcher &Rule) const override {
2035     Table << MatchTable::Opcode("GIM_CheckMemoryAddressSpace")
2036           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
2037           << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
2038         // Encode number of address spaces to expect.
2039           << MatchTable::Comment("NumAddrSpace")
2040           << MatchTable::IntValue(AddrSpaces.size());
2041     for (unsigned AS : AddrSpaces)
2042       Table << MatchTable::Comment("AddrSpace") << MatchTable::IntValue(AS);
2043 
2044     Table << MatchTable::LineBreak;
2045   }
2046 };
2047 
2048 class MemoryAlignmentPredicateMatcher : public InstructionPredicateMatcher {
2049 protected:
2050   unsigned MMOIdx;
2051   int MinAlign;
2052 
2053 public:
2054   MemoryAlignmentPredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
2055                                   int MinAlign)
2056       : InstructionPredicateMatcher(IPM_MemoryAlignment, InsnVarID),
2057         MMOIdx(MMOIdx), MinAlign(MinAlign) {
2058     assert(MinAlign > 0);
2059   }
2060 
2061   static bool classof(const PredicateMatcher *P) {
2062     return P->getKind() == IPM_MemoryAlignment;
2063   }
2064 
2065   bool isIdentical(const PredicateMatcher &B) const override {
2066     if (!InstructionPredicateMatcher::isIdentical(B))
2067       return false;
2068     auto *Other = cast<MemoryAlignmentPredicateMatcher>(&B);
2069     return MMOIdx == Other->MMOIdx && MinAlign == Other->MinAlign;
2070   }
2071 
2072   void emitPredicateOpcodes(MatchTable &Table,
2073                             RuleMatcher &Rule) const override {
2074     Table << MatchTable::Opcode("GIM_CheckMemoryAlignment")
2075           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
2076           << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
2077           << MatchTable::Comment("MinAlign") << MatchTable::IntValue(MinAlign)
2078           << MatchTable::LineBreak;
2079   }
2080 };
2081 
2082 /// Generates code to check that the size of an MMO is less-than, equal-to, or
2083 /// greater than a given LLT.
2084 class MemoryVsLLTSizePredicateMatcher : public InstructionPredicateMatcher {
2085 public:
2086   enum RelationKind {
2087     GreaterThan,
2088     EqualTo,
2089     LessThan,
2090   };
2091 
2092 protected:
2093   unsigned MMOIdx;
2094   RelationKind Relation;
2095   unsigned OpIdx;
2096 
2097 public:
2098   MemoryVsLLTSizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
2099                                   enum RelationKind Relation,
2100                                   unsigned OpIdx)
2101       : InstructionPredicateMatcher(IPM_MemoryVsLLTSize, InsnVarID),
2102         MMOIdx(MMOIdx), Relation(Relation), OpIdx(OpIdx) {}
2103 
2104   static bool classof(const PredicateMatcher *P) {
2105     return P->getKind() == IPM_MemoryVsLLTSize;
2106   }
2107   bool isIdentical(const PredicateMatcher &B) const override {
2108     return InstructionPredicateMatcher::isIdentical(B) &&
2109            MMOIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->MMOIdx &&
2110            Relation == cast<MemoryVsLLTSizePredicateMatcher>(&B)->Relation &&
2111            OpIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->OpIdx;
2112   }
2113 
2114   void emitPredicateOpcodes(MatchTable &Table,
2115                             RuleMatcher &Rule) const override {
2116     Table << MatchTable::Opcode(Relation == EqualTo
2117                                     ? "GIM_CheckMemorySizeEqualToLLT"
2118                                     : Relation == GreaterThan
2119                                           ? "GIM_CheckMemorySizeGreaterThanLLT"
2120                                           : "GIM_CheckMemorySizeLessThanLLT")
2121           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
2122           << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
2123           << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx)
2124           << MatchTable::LineBreak;
2125   }
2126 };
2127 
2128 // Matcher for immAllOnesV/immAllZerosV
2129 class VectorSplatImmPredicateMatcher : public InstructionPredicateMatcher {
2130 public:
2131   enum SplatKind {
2132     AllZeros,
2133     AllOnes
2134   };
2135 
2136 private:
2137   SplatKind Kind;
2138 
2139 public:
2140   VectorSplatImmPredicateMatcher(unsigned InsnVarID, SplatKind K)
2141       : InstructionPredicateMatcher(IPM_VectorSplatImm, InsnVarID), Kind(K) {}
2142 
2143   static bool classof(const PredicateMatcher *P) {
2144     return P->getKind() == IPM_VectorSplatImm;
2145   }
2146 
2147   bool isIdentical(const PredicateMatcher &B) const override {
2148     return InstructionPredicateMatcher::isIdentical(B) &&
2149            Kind == static_cast<const VectorSplatImmPredicateMatcher &>(B).Kind;
2150   }
2151 
2152   void emitPredicateOpcodes(MatchTable &Table,
2153                             RuleMatcher &Rule) const override {
2154     if (Kind == AllOnes)
2155       Table << MatchTable::Opcode("GIM_CheckIsBuildVectorAllOnes");
2156     else
2157       Table << MatchTable::Opcode("GIM_CheckIsBuildVectorAllZeros");
2158 
2159     Table << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID);
2160     Table << MatchTable::LineBreak;
2161   }
2162 };
2163 
2164 /// Generates code to check an arbitrary C++ instruction predicate.
2165 class GenericInstructionPredicateMatcher : public InstructionPredicateMatcher {
2166 protected:
2167   TreePredicateFn Predicate;
2168 
2169 public:
2170   GenericInstructionPredicateMatcher(unsigned InsnVarID,
2171                                      TreePredicateFn Predicate)
2172       : InstructionPredicateMatcher(IPM_GenericPredicate, InsnVarID),
2173         Predicate(Predicate) {}
2174 
2175   static bool classof(const InstructionPredicateMatcher *P) {
2176     return P->getKind() == IPM_GenericPredicate;
2177   }
2178   bool isIdentical(const PredicateMatcher &B) const override {
2179     return InstructionPredicateMatcher::isIdentical(B) &&
2180            Predicate ==
2181                static_cast<const GenericInstructionPredicateMatcher &>(B)
2182                    .Predicate;
2183   }
2184   void emitPredicateOpcodes(MatchTable &Table,
2185                             RuleMatcher &Rule) const override {
2186     Table << MatchTable::Opcode("GIM_CheckCxxInsnPredicate")
2187           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
2188           << MatchTable::Comment("FnId")
2189           << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
2190           << MatchTable::LineBreak;
2191   }
2192 };
2193 
2194 /// Generates code to check that a set of predicates and operands match for a
2195 /// particular instruction.
2196 ///
2197 /// Typical predicates include:
2198 /// * Has a specific opcode.
2199 /// * Has an nsw/nuw flag or doesn't.
2200 class InstructionMatcher final : public PredicateListMatcher<PredicateMatcher> {
2201 protected:
2202   typedef std::vector<std::unique_ptr<OperandMatcher>> OperandVec;
2203 
2204   RuleMatcher &Rule;
2205 
2206   /// The operands to match. All rendered operands must be present even if the
2207   /// condition is always true.
2208   OperandVec Operands;
2209   bool NumOperandsCheck = true;
2210 
2211   std::string SymbolicName;
2212   unsigned InsnVarID;
2213 
2214   /// PhysRegInputs - List list has an entry for each explicitly specified
2215   /// physreg input to the pattern.  The first elt is the Register node, the
2216   /// second is the recorded slot number the input pattern match saved it in.
2217   SmallVector<std::pair<Record *, unsigned>, 2> PhysRegInputs;
2218 
2219 public:
2220   InstructionMatcher(RuleMatcher &Rule, StringRef SymbolicName,
2221                      bool NumOpsCheck = true)
2222       : Rule(Rule), NumOperandsCheck(NumOpsCheck), SymbolicName(SymbolicName) {
2223     // We create a new instruction matcher.
2224     // Get a new ID for that instruction.
2225     InsnVarID = Rule.implicitlyDefineInsnVar(*this);
2226   }
2227 
2228   /// Construct a new instruction predicate and add it to the matcher.
2229   template <class Kind, class... Args>
2230   Optional<Kind *> addPredicate(Args &&... args) {
2231     Predicates.emplace_back(
2232         std::make_unique<Kind>(getInsnVarID(), std::forward<Args>(args)...));
2233     return static_cast<Kind *>(Predicates.back().get());
2234   }
2235 
2236   RuleMatcher &getRuleMatcher() const { return Rule; }
2237 
2238   unsigned getInsnVarID() const { return InsnVarID; }
2239 
2240   /// Add an operand to the matcher.
2241   OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName,
2242                              unsigned AllocatedTemporariesBaseID) {
2243     Operands.emplace_back(new OperandMatcher(*this, OpIdx, SymbolicName,
2244                                              AllocatedTemporariesBaseID));
2245     if (!SymbolicName.empty())
2246       Rule.defineOperand(SymbolicName, *Operands.back());
2247 
2248     return *Operands.back();
2249   }
2250 
2251   OperandMatcher &getOperand(unsigned OpIdx) {
2252     auto I = llvm::find_if(Operands,
2253                            [&OpIdx](const std::unique_ptr<OperandMatcher> &X) {
2254                              return X->getOpIdx() == OpIdx;
2255                            });
2256     if (I != Operands.end())
2257       return **I;
2258     llvm_unreachable("Failed to lookup operand");
2259   }
2260 
2261   OperandMatcher &addPhysRegInput(Record *Reg, unsigned OpIdx,
2262                                   unsigned TempOpIdx) {
2263     assert(SymbolicName.empty());
2264     OperandMatcher *OM = new OperandMatcher(*this, OpIdx, "", TempOpIdx);
2265     Operands.emplace_back(OM);
2266     Rule.definePhysRegOperand(Reg, *OM);
2267     PhysRegInputs.emplace_back(Reg, OpIdx);
2268     return *OM;
2269   }
2270 
2271   ArrayRef<std::pair<Record *, unsigned>> getPhysRegInputs() const {
2272     return PhysRegInputs;
2273   }
2274 
2275   StringRef getSymbolicName() const { return SymbolicName; }
2276   unsigned getNumOperands() const { return Operands.size(); }
2277   OperandVec::iterator operands_begin() { return Operands.begin(); }
2278   OperandVec::iterator operands_end() { return Operands.end(); }
2279   iterator_range<OperandVec::iterator> operands() {
2280     return make_range(operands_begin(), operands_end());
2281   }
2282   OperandVec::const_iterator operands_begin() const { return Operands.begin(); }
2283   OperandVec::const_iterator operands_end() const { return Operands.end(); }
2284   iterator_range<OperandVec::const_iterator> operands() const {
2285     return make_range(operands_begin(), operands_end());
2286   }
2287   bool operands_empty() const { return Operands.empty(); }
2288 
2289   void pop_front() { Operands.erase(Operands.begin()); }
2290 
2291   void optimize();
2292 
2293   /// Emit MatchTable opcodes that test whether the instruction named in
2294   /// InsnVarName matches all the predicates and all the operands.
2295   void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) {
2296     if (NumOperandsCheck)
2297       InstructionNumOperandsMatcher(InsnVarID, getNumOperands())
2298           .emitPredicateOpcodes(Table, Rule);
2299 
2300     // First emit all instruction level predicates need to be verified before we
2301     // can verify operands.
2302     emitFilteredPredicateListOpcodes(
2303       [](const PredicateMatcher &P) {
2304         return !P.dependsOnOperands();
2305       }, Table, Rule);
2306 
2307     // Emit all operand constraints.
2308     for (const auto &Operand : Operands)
2309       Operand->emitPredicateOpcodes(Table, Rule);
2310 
2311     // All of the tablegen defined predicates should now be matched. Now emit
2312     // any custom predicates that rely on all generated checks.
2313     emitFilteredPredicateListOpcodes(
2314       [](const PredicateMatcher &P) {
2315         return P.dependsOnOperands();
2316       }, Table, Rule);
2317   }
2318 
2319   /// Compare the priority of this object and B.
2320   ///
2321   /// Returns true if this object is more important than B.
2322   bool isHigherPriorityThan(InstructionMatcher &B) {
2323     // Instruction matchers involving more operands have higher priority.
2324     if (Operands.size() > B.Operands.size())
2325       return true;
2326     if (Operands.size() < B.Operands.size())
2327       return false;
2328 
2329     for (auto &&P : zip(predicates(), B.predicates())) {
2330       auto L = static_cast<InstructionPredicateMatcher *>(std::get<0>(P).get());
2331       auto R = static_cast<InstructionPredicateMatcher *>(std::get<1>(P).get());
2332       if (L->isHigherPriorityThan(*R))
2333         return true;
2334       if (R->isHigherPriorityThan(*L))
2335         return false;
2336     }
2337 
2338     for (auto Operand : zip(Operands, B.Operands)) {
2339       if (std::get<0>(Operand)->isHigherPriorityThan(*std::get<1>(Operand)))
2340         return true;
2341       if (std::get<1>(Operand)->isHigherPriorityThan(*std::get<0>(Operand)))
2342         return false;
2343     }
2344 
2345     return false;
2346   };
2347 
2348   /// Report the maximum number of temporary operands needed by the instruction
2349   /// matcher.
2350   unsigned countRendererFns() {
2351     return std::accumulate(
2352                predicates().begin(), predicates().end(), 0,
2353                [](unsigned A,
2354                   const std::unique_ptr<PredicateMatcher> &Predicate) {
2355                  return A + Predicate->countRendererFns();
2356                }) +
2357            std::accumulate(
2358                Operands.begin(), Operands.end(), 0,
2359                [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) {
2360                  return A + Operand->countRendererFns();
2361                });
2362   }
2363 
2364   InstructionOpcodeMatcher &getOpcodeMatcher() {
2365     for (auto &P : predicates())
2366       if (auto *OpMatcher = dyn_cast<InstructionOpcodeMatcher>(P.get()))
2367         return *OpMatcher;
2368     llvm_unreachable("Didn't find an opcode matcher");
2369   }
2370 
2371   bool isConstantInstruction() {
2372     return getOpcodeMatcher().isConstantInstruction();
2373   }
2374 
2375   StringRef getOpcode() { return getOpcodeMatcher().getOpcode(); }
2376 };
2377 
2378 StringRef RuleMatcher::getOpcode() const {
2379   return Matchers.front()->getOpcode();
2380 }
2381 
2382 unsigned RuleMatcher::getNumOperands() const {
2383   return Matchers.front()->getNumOperands();
2384 }
2385 
2386 LLTCodeGen RuleMatcher::getFirstConditionAsRootType() {
2387   InstructionMatcher &InsnMatcher = *Matchers.front();
2388   if (!InsnMatcher.predicates_empty())
2389     if (const auto *TM =
2390             dyn_cast<LLTOperandMatcher>(&**InsnMatcher.predicates_begin()))
2391       if (TM->getInsnVarID() == 0 && TM->getOpIdx() == 0)
2392         return TM->getTy();
2393   return {};
2394 }
2395 
2396 /// Generates code to check that the operand is a register defined by an
2397 /// instruction that matches the given instruction matcher.
2398 ///
2399 /// For example, the pattern:
2400 ///   (set $dst, (G_MUL (G_ADD $src1, $src2), $src3))
2401 /// would use an InstructionOperandMatcher for operand 1 of the G_MUL to match
2402 /// the:
2403 ///   (G_ADD $src1, $src2)
2404 /// subpattern.
2405 class InstructionOperandMatcher : public OperandPredicateMatcher {
2406 protected:
2407   std::unique_ptr<InstructionMatcher> InsnMatcher;
2408 
2409 public:
2410   InstructionOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
2411                             RuleMatcher &Rule, StringRef SymbolicName,
2412                             bool NumOpsCheck = true)
2413       : OperandPredicateMatcher(OPM_Instruction, InsnVarID, OpIdx),
2414         InsnMatcher(new InstructionMatcher(Rule, SymbolicName, NumOpsCheck)) {}
2415 
2416   static bool classof(const PredicateMatcher *P) {
2417     return P->getKind() == OPM_Instruction;
2418   }
2419 
2420   InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; }
2421 
2422   void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const {
2423     const unsigned NewInsnVarID = InsnMatcher->getInsnVarID();
2424     Table << MatchTable::Opcode("GIM_RecordInsn")
2425           << MatchTable::Comment("DefineMI")
2426           << MatchTable::IntValue(NewInsnVarID) << MatchTable::Comment("MI")
2427           << MatchTable::IntValue(getInsnVarID())
2428           << MatchTable::Comment("OpIdx") << MatchTable::IntValue(getOpIdx())
2429           << MatchTable::Comment("MIs[" + llvm::to_string(NewInsnVarID) + "]")
2430           << MatchTable::LineBreak;
2431   }
2432 
2433   void emitPredicateOpcodes(MatchTable &Table,
2434                             RuleMatcher &Rule) const override {
2435     emitCaptureOpcodes(Table, Rule);
2436     InsnMatcher->emitPredicateOpcodes(Table, Rule);
2437   }
2438 
2439   bool isHigherPriorityThan(const OperandPredicateMatcher &B) const override {
2440     if (OperandPredicateMatcher::isHigherPriorityThan(B))
2441       return true;
2442     if (B.OperandPredicateMatcher::isHigherPriorityThan(*this))
2443       return false;
2444 
2445     if (const InstructionOperandMatcher *BP =
2446             dyn_cast<InstructionOperandMatcher>(&B))
2447       if (InsnMatcher->isHigherPriorityThan(*BP->InsnMatcher))
2448         return true;
2449     return false;
2450   }
2451 };
2452 
2453 void InstructionMatcher::optimize() {
2454   SmallVector<std::unique_ptr<PredicateMatcher>, 8> Stash;
2455   const auto &OpcMatcher = getOpcodeMatcher();
2456 
2457   Stash.push_back(predicates_pop_front());
2458   if (Stash.back().get() == &OpcMatcher) {
2459     if (NumOperandsCheck && OpcMatcher.isVariadicNumOperands())
2460       Stash.emplace_back(
2461           new InstructionNumOperandsMatcher(InsnVarID, getNumOperands()));
2462     NumOperandsCheck = false;
2463 
2464     for (auto &OM : Operands)
2465       for (auto &OP : OM->predicates())
2466         if (isa<IntrinsicIDOperandMatcher>(OP)) {
2467           Stash.push_back(std::move(OP));
2468           OM->eraseNullPredicates();
2469           break;
2470         }
2471   }
2472 
2473   if (InsnVarID > 0) {
2474     assert(!Operands.empty() && "Nested instruction is expected to def a vreg");
2475     for (auto &OP : Operands[0]->predicates())
2476       OP.reset();
2477     Operands[0]->eraseNullPredicates();
2478   }
2479   for (auto &OM : Operands) {
2480     for (auto &OP : OM->predicates())
2481       if (isa<LLTOperandMatcher>(OP))
2482         Stash.push_back(std::move(OP));
2483     OM->eraseNullPredicates();
2484   }
2485   while (!Stash.empty())
2486     prependPredicate(Stash.pop_back_val());
2487 }
2488 
2489 //===- Actions ------------------------------------------------------------===//
2490 class OperandRenderer {
2491 public:
2492   enum RendererKind {
2493     OR_Copy,
2494     OR_CopyOrAddZeroReg,
2495     OR_CopySubReg,
2496     OR_CopyPhysReg,
2497     OR_CopyConstantAsImm,
2498     OR_CopyFConstantAsFPImm,
2499     OR_Imm,
2500     OR_SubRegIndex,
2501     OR_Register,
2502     OR_TempRegister,
2503     OR_ComplexPattern,
2504     OR_Custom,
2505     OR_CustomOperand
2506   };
2507 
2508 protected:
2509   RendererKind Kind;
2510 
2511 public:
2512   OperandRenderer(RendererKind Kind) : Kind(Kind) {}
2513   virtual ~OperandRenderer() {}
2514 
2515   RendererKind getKind() const { return Kind; }
2516 
2517   virtual void emitRenderOpcodes(MatchTable &Table,
2518                                  RuleMatcher &Rule) const = 0;
2519 };
2520 
2521 /// A CopyRenderer emits code to copy a single operand from an existing
2522 /// instruction to the one being built.
2523 class CopyRenderer : public OperandRenderer {
2524 protected:
2525   unsigned NewInsnID;
2526   /// The name of the operand.
2527   const StringRef SymbolicName;
2528 
2529 public:
2530   CopyRenderer(unsigned NewInsnID, StringRef SymbolicName)
2531       : OperandRenderer(OR_Copy), NewInsnID(NewInsnID),
2532         SymbolicName(SymbolicName) {
2533     assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
2534   }
2535 
2536   static bool classof(const OperandRenderer *R) {
2537     return R->getKind() == OR_Copy;
2538   }
2539 
2540   StringRef getSymbolicName() const { return SymbolicName; }
2541 
2542   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2543     const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2544     unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2545     Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
2546           << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID")
2547           << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2548           << MatchTable::IntValue(Operand.getOpIdx())
2549           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2550   }
2551 };
2552 
2553 /// A CopyRenderer emits code to copy a virtual register to a specific physical
2554 /// register.
2555 class CopyPhysRegRenderer : public OperandRenderer {
2556 protected:
2557   unsigned NewInsnID;
2558   Record *PhysReg;
2559 
2560 public:
2561   CopyPhysRegRenderer(unsigned NewInsnID, Record *Reg)
2562       : OperandRenderer(OR_CopyPhysReg), NewInsnID(NewInsnID),
2563         PhysReg(Reg) {
2564     assert(PhysReg);
2565   }
2566 
2567   static bool classof(const OperandRenderer *R) {
2568     return R->getKind() == OR_CopyPhysReg;
2569   }
2570 
2571   Record *getPhysReg() const { return PhysReg; }
2572 
2573   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2574     const OperandMatcher &Operand = Rule.getPhysRegOperandMatcher(PhysReg);
2575     unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2576     Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
2577           << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID")
2578           << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2579           << MatchTable::IntValue(Operand.getOpIdx())
2580           << MatchTable::Comment(PhysReg->getName())
2581           << MatchTable::LineBreak;
2582   }
2583 };
2584 
2585 /// A CopyOrAddZeroRegRenderer emits code to copy a single operand from an
2586 /// existing instruction to the one being built. If the operand turns out to be
2587 /// a 'G_CONSTANT 0' then it replaces the operand with a zero register.
2588 class CopyOrAddZeroRegRenderer : public OperandRenderer {
2589 protected:
2590   unsigned NewInsnID;
2591   /// The name of the operand.
2592   const StringRef SymbolicName;
2593   const Record *ZeroRegisterDef;
2594 
2595 public:
2596   CopyOrAddZeroRegRenderer(unsigned NewInsnID,
2597                            StringRef SymbolicName, Record *ZeroRegisterDef)
2598       : OperandRenderer(OR_CopyOrAddZeroReg), NewInsnID(NewInsnID),
2599         SymbolicName(SymbolicName), ZeroRegisterDef(ZeroRegisterDef) {
2600     assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
2601   }
2602 
2603   static bool classof(const OperandRenderer *R) {
2604     return R->getKind() == OR_CopyOrAddZeroReg;
2605   }
2606 
2607   StringRef getSymbolicName() const { return SymbolicName; }
2608 
2609   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2610     const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2611     unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2612     Table << MatchTable::Opcode("GIR_CopyOrAddZeroReg")
2613           << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2614           << MatchTable::Comment("OldInsnID")
2615           << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2616           << MatchTable::IntValue(Operand.getOpIdx())
2617           << MatchTable::NamedValue(
2618                  (ZeroRegisterDef->getValue("Namespace")
2619                       ? ZeroRegisterDef->getValueAsString("Namespace")
2620                       : ""),
2621                  ZeroRegisterDef->getName())
2622           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2623   }
2624 };
2625 
2626 /// A CopyConstantAsImmRenderer emits code to render a G_CONSTANT instruction to
2627 /// an extended immediate operand.
2628 class CopyConstantAsImmRenderer : public OperandRenderer {
2629 protected:
2630   unsigned NewInsnID;
2631   /// The name of the operand.
2632   const std::string SymbolicName;
2633   bool Signed;
2634 
2635 public:
2636   CopyConstantAsImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
2637       : OperandRenderer(OR_CopyConstantAsImm), NewInsnID(NewInsnID),
2638         SymbolicName(SymbolicName), Signed(true) {}
2639 
2640   static bool classof(const OperandRenderer *R) {
2641     return R->getKind() == OR_CopyConstantAsImm;
2642   }
2643 
2644   StringRef getSymbolicName() const { return SymbolicName; }
2645 
2646   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2647     InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2648     unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2649     Table << MatchTable::Opcode(Signed ? "GIR_CopyConstantAsSImm"
2650                                        : "GIR_CopyConstantAsUImm")
2651           << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2652           << MatchTable::Comment("OldInsnID")
2653           << MatchTable::IntValue(OldInsnVarID)
2654           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2655   }
2656 };
2657 
2658 /// A CopyFConstantAsFPImmRenderer emits code to render a G_FCONSTANT
2659 /// instruction to an extended immediate operand.
2660 class CopyFConstantAsFPImmRenderer : public OperandRenderer {
2661 protected:
2662   unsigned NewInsnID;
2663   /// The name of the operand.
2664   const std::string SymbolicName;
2665 
2666 public:
2667   CopyFConstantAsFPImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
2668       : OperandRenderer(OR_CopyFConstantAsFPImm), NewInsnID(NewInsnID),
2669         SymbolicName(SymbolicName) {}
2670 
2671   static bool classof(const OperandRenderer *R) {
2672     return R->getKind() == OR_CopyFConstantAsFPImm;
2673   }
2674 
2675   StringRef getSymbolicName() const { return SymbolicName; }
2676 
2677   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2678     InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2679     unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2680     Table << MatchTable::Opcode("GIR_CopyFConstantAsFPImm")
2681           << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2682           << MatchTable::Comment("OldInsnID")
2683           << MatchTable::IntValue(OldInsnVarID)
2684           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2685   }
2686 };
2687 
2688 /// A CopySubRegRenderer emits code to copy a single register operand from an
2689 /// existing instruction to the one being built and indicate that only a
2690 /// subregister should be copied.
2691 class CopySubRegRenderer : public OperandRenderer {
2692 protected:
2693   unsigned NewInsnID;
2694   /// The name of the operand.
2695   const StringRef SymbolicName;
2696   /// The subregister to extract.
2697   const CodeGenSubRegIndex *SubReg;
2698 
2699 public:
2700   CopySubRegRenderer(unsigned NewInsnID, StringRef SymbolicName,
2701                      const CodeGenSubRegIndex *SubReg)
2702       : OperandRenderer(OR_CopySubReg), NewInsnID(NewInsnID),
2703         SymbolicName(SymbolicName), SubReg(SubReg) {}
2704 
2705   static bool classof(const OperandRenderer *R) {
2706     return R->getKind() == OR_CopySubReg;
2707   }
2708 
2709   StringRef getSymbolicName() const { return SymbolicName; }
2710 
2711   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2712     const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2713     unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2714     Table << MatchTable::Opcode("GIR_CopySubReg")
2715           << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2716           << MatchTable::Comment("OldInsnID")
2717           << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2718           << MatchTable::IntValue(Operand.getOpIdx())
2719           << MatchTable::Comment("SubRegIdx")
2720           << MatchTable::IntValue(SubReg->EnumValue)
2721           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2722   }
2723 };
2724 
2725 /// Adds a specific physical register to the instruction being built.
2726 /// This is typically useful for WZR/XZR on AArch64.
2727 class AddRegisterRenderer : public OperandRenderer {
2728 protected:
2729   unsigned InsnID;
2730   const Record *RegisterDef;
2731   bool IsDef;
2732   const CodeGenTarget &Target;
2733 
2734 public:
2735   AddRegisterRenderer(unsigned InsnID, const CodeGenTarget &Target,
2736                       const Record *RegisterDef, bool IsDef = false)
2737       : OperandRenderer(OR_Register), InsnID(InsnID), RegisterDef(RegisterDef),
2738         IsDef(IsDef), Target(Target) {}
2739 
2740   static bool classof(const OperandRenderer *R) {
2741     return R->getKind() == OR_Register;
2742   }
2743 
2744   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2745     Table << MatchTable::Opcode("GIR_AddRegister")
2746           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID);
2747     if (RegisterDef->getName() != "zero_reg") {
2748       Table << MatchTable::NamedValue(
2749                    (RegisterDef->getValue("Namespace")
2750                         ? RegisterDef->getValueAsString("Namespace")
2751                         : ""),
2752                    RegisterDef->getName());
2753     } else {
2754       Table << MatchTable::NamedValue(Target.getRegNamespace(), "NoRegister");
2755     }
2756     Table << MatchTable::Comment("AddRegisterRegFlags");
2757 
2758     // TODO: This is encoded as a 64-bit element, but only 16 or 32-bits are
2759     // really needed for a physical register reference. We can pack the
2760     // register and flags in a single field.
2761     if (IsDef)
2762       Table << MatchTable::NamedValue("RegState::Define");
2763     else
2764       Table << MatchTable::IntValue(0);
2765     Table << MatchTable::LineBreak;
2766   }
2767 };
2768 
2769 /// Adds a specific temporary virtual register to the instruction being built.
2770 /// This is used to chain instructions together when emitting multiple
2771 /// instructions.
2772 class TempRegRenderer : public OperandRenderer {
2773 protected:
2774   unsigned InsnID;
2775   unsigned TempRegID;
2776   const CodeGenSubRegIndex *SubRegIdx;
2777   bool IsDef;
2778   bool IsDead;
2779 
2780 public:
2781   TempRegRenderer(unsigned InsnID, unsigned TempRegID, bool IsDef = false,
2782                   const CodeGenSubRegIndex *SubReg = nullptr,
2783                   bool IsDead = false)
2784       : OperandRenderer(OR_Register), InsnID(InsnID), TempRegID(TempRegID),
2785         SubRegIdx(SubReg), IsDef(IsDef), IsDead(IsDead) {}
2786 
2787   static bool classof(const OperandRenderer *R) {
2788     return R->getKind() == OR_TempRegister;
2789   }
2790 
2791   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2792     if (SubRegIdx) {
2793       assert(!IsDef);
2794       Table << MatchTable::Opcode("GIR_AddTempSubRegister");
2795     } else
2796       Table << MatchTable::Opcode("GIR_AddTempRegister");
2797 
2798     Table << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2799           << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID)
2800           << MatchTable::Comment("TempRegFlags");
2801 
2802     if (IsDef) {
2803       SmallString<32> RegFlags;
2804       RegFlags += "RegState::Define";
2805       if (IsDead)
2806         RegFlags += "|RegState::Dead";
2807       Table << MatchTable::NamedValue(RegFlags);
2808     } else
2809       Table << MatchTable::IntValue(0);
2810 
2811     if (SubRegIdx)
2812       Table << MatchTable::NamedValue(SubRegIdx->getQualifiedName());
2813     Table << MatchTable::LineBreak;
2814   }
2815 };
2816 
2817 /// Adds a specific immediate to the instruction being built.
2818 class ImmRenderer : public OperandRenderer {
2819 protected:
2820   unsigned InsnID;
2821   int64_t Imm;
2822 
2823 public:
2824   ImmRenderer(unsigned InsnID, int64_t Imm)
2825       : OperandRenderer(OR_Imm), InsnID(InsnID), Imm(Imm) {}
2826 
2827   static bool classof(const OperandRenderer *R) {
2828     return R->getKind() == OR_Imm;
2829   }
2830 
2831   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2832     Table << MatchTable::Opcode("GIR_AddImm") << MatchTable::Comment("InsnID")
2833           << MatchTable::IntValue(InsnID) << MatchTable::Comment("Imm")
2834           << MatchTable::IntValue(Imm) << MatchTable::LineBreak;
2835   }
2836 };
2837 
2838 /// Adds an enum value for a subreg index to the instruction being built.
2839 class SubRegIndexRenderer : public OperandRenderer {
2840 protected:
2841   unsigned InsnID;
2842   const CodeGenSubRegIndex *SubRegIdx;
2843 
2844 public:
2845   SubRegIndexRenderer(unsigned InsnID, const CodeGenSubRegIndex *SRI)
2846       : OperandRenderer(OR_SubRegIndex), InsnID(InsnID), SubRegIdx(SRI) {}
2847 
2848   static bool classof(const OperandRenderer *R) {
2849     return R->getKind() == OR_SubRegIndex;
2850   }
2851 
2852   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2853     Table << MatchTable::Opcode("GIR_AddImm") << MatchTable::Comment("InsnID")
2854           << MatchTable::IntValue(InsnID) << MatchTable::Comment("SubRegIndex")
2855           << MatchTable::IntValue(SubRegIdx->EnumValue)
2856           << MatchTable::LineBreak;
2857   }
2858 };
2859 
2860 /// Adds operands by calling a renderer function supplied by the ComplexPattern
2861 /// matcher function.
2862 class RenderComplexPatternOperand : public OperandRenderer {
2863 private:
2864   unsigned InsnID;
2865   const Record &TheDef;
2866   /// The name of the operand.
2867   const StringRef SymbolicName;
2868   /// The renderer number. This must be unique within a rule since it's used to
2869   /// identify a temporary variable to hold the renderer function.
2870   unsigned RendererID;
2871   /// When provided, this is the suboperand of the ComplexPattern operand to
2872   /// render. Otherwise all the suboperands will be rendered.
2873   Optional<unsigned> SubOperand;
2874 
2875   unsigned getNumOperands() const {
2876     return TheDef.getValueAsDag("Operands")->getNumArgs();
2877   }
2878 
2879 public:
2880   RenderComplexPatternOperand(unsigned InsnID, const Record &TheDef,
2881                               StringRef SymbolicName, unsigned RendererID,
2882                               Optional<unsigned> SubOperand = None)
2883       : OperandRenderer(OR_ComplexPattern), InsnID(InsnID), TheDef(TheDef),
2884         SymbolicName(SymbolicName), RendererID(RendererID),
2885         SubOperand(SubOperand) {}
2886 
2887   static bool classof(const OperandRenderer *R) {
2888     return R->getKind() == OR_ComplexPattern;
2889   }
2890 
2891   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2892     Table << MatchTable::Opcode(SubOperand.hasValue() ? "GIR_ComplexSubOperandRenderer"
2893                                                       : "GIR_ComplexRenderer")
2894           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2895           << MatchTable::Comment("RendererID")
2896           << MatchTable::IntValue(RendererID);
2897     if (SubOperand.hasValue())
2898       Table << MatchTable::Comment("SubOperand")
2899             << MatchTable::IntValue(SubOperand.getValue());
2900     Table << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2901   }
2902 };
2903 
2904 class CustomRenderer : public OperandRenderer {
2905 protected:
2906   unsigned InsnID;
2907   const Record &Renderer;
2908   /// The name of the operand.
2909   const std::string SymbolicName;
2910 
2911 public:
2912   CustomRenderer(unsigned InsnID, const Record &Renderer,
2913                  StringRef SymbolicName)
2914       : OperandRenderer(OR_Custom), InsnID(InsnID), Renderer(Renderer),
2915         SymbolicName(SymbolicName) {}
2916 
2917   static bool classof(const OperandRenderer *R) {
2918     return R->getKind() == OR_Custom;
2919   }
2920 
2921   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2922     InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2923     unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2924     Table << MatchTable::Opcode("GIR_CustomRenderer")
2925           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2926           << MatchTable::Comment("OldInsnID")
2927           << MatchTable::IntValue(OldInsnVarID)
2928           << MatchTable::Comment("Renderer")
2929           << MatchTable::NamedValue(
2930                  "GICR_" + Renderer.getValueAsString("RendererFn").str())
2931           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2932   }
2933 };
2934 
2935 class CustomOperandRenderer : public OperandRenderer {
2936 protected:
2937   unsigned InsnID;
2938   const Record &Renderer;
2939   /// The name of the operand.
2940   const std::string SymbolicName;
2941 
2942 public:
2943   CustomOperandRenderer(unsigned InsnID, const Record &Renderer,
2944                         StringRef SymbolicName)
2945       : OperandRenderer(OR_CustomOperand), InsnID(InsnID), Renderer(Renderer),
2946         SymbolicName(SymbolicName) {}
2947 
2948   static bool classof(const OperandRenderer *R) {
2949     return R->getKind() == OR_CustomOperand;
2950   }
2951 
2952   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2953     const OperandMatcher &OpdMatcher = Rule.getOperandMatcher(SymbolicName);
2954     Table << MatchTable::Opcode("GIR_CustomOperandRenderer")
2955           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2956           << MatchTable::Comment("OldInsnID")
2957           << MatchTable::IntValue(OpdMatcher.getInsnVarID())
2958           << MatchTable::Comment("OpIdx")
2959           << MatchTable::IntValue(OpdMatcher.getOpIdx())
2960           << MatchTable::Comment("OperandRenderer")
2961           << MatchTable::NamedValue(
2962             "GICR_" + Renderer.getValueAsString("RendererFn").str())
2963           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2964   }
2965 };
2966 
2967 /// An action taken when all Matcher predicates succeeded for a parent rule.
2968 ///
2969 /// Typical actions include:
2970 /// * Changing the opcode of an instruction.
2971 /// * Adding an operand to an instruction.
2972 class MatchAction {
2973 public:
2974   virtual ~MatchAction() {}
2975 
2976   /// Emit the MatchTable opcodes to implement the action.
2977   virtual void emitActionOpcodes(MatchTable &Table,
2978                                  RuleMatcher &Rule) const = 0;
2979 };
2980 
2981 /// Generates a comment describing the matched rule being acted upon.
2982 class DebugCommentAction : public MatchAction {
2983 private:
2984   std::string S;
2985 
2986 public:
2987   DebugCommentAction(StringRef S) : S(std::string(S)) {}
2988 
2989   void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2990     Table << MatchTable::Comment(S) << MatchTable::LineBreak;
2991   }
2992 };
2993 
2994 /// Generates code to build an instruction or mutate an existing instruction
2995 /// into the desired instruction when this is possible.
2996 class BuildMIAction : public MatchAction {
2997 private:
2998   unsigned InsnID;
2999   const CodeGenInstruction *I;
3000   InstructionMatcher *Matched;
3001   std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers;
3002 
3003   /// True if the instruction can be built solely by mutating the opcode.
3004   bool canMutate(RuleMatcher &Rule, const InstructionMatcher *Insn) const {
3005     if (!Insn)
3006       return false;
3007 
3008     if (OperandRenderers.size() != Insn->getNumOperands())
3009       return false;
3010 
3011     for (const auto &Renderer : enumerate(OperandRenderers)) {
3012       if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) {
3013         const OperandMatcher &OM = Rule.getOperandMatcher(Copy->getSymbolicName());
3014         if (Insn != &OM.getInstructionMatcher() ||
3015             OM.getOpIdx() != Renderer.index())
3016           return false;
3017       } else
3018         return false;
3019     }
3020 
3021     return true;
3022   }
3023 
3024 public:
3025   BuildMIAction(unsigned InsnID, const CodeGenInstruction *I)
3026       : InsnID(InsnID), I(I), Matched(nullptr) {}
3027 
3028   unsigned getInsnID() const { return InsnID; }
3029   const CodeGenInstruction *getCGI() const { return I; }
3030 
3031   void chooseInsnToMutate(RuleMatcher &Rule) {
3032     for (auto *MutateCandidate : Rule.mutatable_insns()) {
3033       if (canMutate(Rule, MutateCandidate)) {
3034         // Take the first one we're offered that we're able to mutate.
3035         Rule.reserveInsnMatcherForMutation(MutateCandidate);
3036         Matched = MutateCandidate;
3037         return;
3038       }
3039     }
3040   }
3041 
3042   template <class Kind, class... Args>
3043   Kind &addRenderer(Args&&... args) {
3044     OperandRenderers.emplace_back(
3045         std::make_unique<Kind>(InsnID, std::forward<Args>(args)...));
3046     return *static_cast<Kind *>(OperandRenderers.back().get());
3047   }
3048 
3049   void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
3050     if (Matched) {
3051       assert(canMutate(Rule, Matched) &&
3052              "Arranged to mutate an insn that isn't mutatable");
3053 
3054       unsigned RecycleInsnID = Rule.getInsnVarID(*Matched);
3055       Table << MatchTable::Opcode("GIR_MutateOpcode")
3056             << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
3057             << MatchTable::Comment("RecycleInsnID")
3058             << MatchTable::IntValue(RecycleInsnID)
3059             << MatchTable::Comment("Opcode")
3060             << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
3061             << MatchTable::LineBreak;
3062 
3063       if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) {
3064         for (auto Def : I->ImplicitDefs) {
3065           auto Namespace = Def->getValue("Namespace")
3066                                ? Def->getValueAsString("Namespace")
3067                                : "";
3068           Table << MatchTable::Opcode("GIR_AddImplicitDef")
3069                 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
3070                 << MatchTable::NamedValue(Namespace, Def->getName())
3071                 << MatchTable::LineBreak;
3072         }
3073         for (auto Use : I->ImplicitUses) {
3074           auto Namespace = Use->getValue("Namespace")
3075                                ? Use->getValueAsString("Namespace")
3076                                : "";
3077           Table << MatchTable::Opcode("GIR_AddImplicitUse")
3078                 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
3079                 << MatchTable::NamedValue(Namespace, Use->getName())
3080                 << MatchTable::LineBreak;
3081         }
3082       }
3083       return;
3084     }
3085 
3086     // TODO: Simple permutation looks like it could be almost as common as
3087     //       mutation due to commutative operations.
3088 
3089     Table << MatchTable::Opcode("GIR_BuildMI") << MatchTable::Comment("InsnID")
3090           << MatchTable::IntValue(InsnID) << MatchTable::Comment("Opcode")
3091           << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
3092           << MatchTable::LineBreak;
3093     for (const auto &Renderer : OperandRenderers)
3094       Renderer->emitRenderOpcodes(Table, Rule);
3095 
3096     if (I->mayLoad || I->mayStore) {
3097       Table << MatchTable::Opcode("GIR_MergeMemOperands")
3098             << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
3099             << MatchTable::Comment("MergeInsnID's");
3100       // Emit the ID's for all the instructions that are matched by this rule.
3101       // TODO: Limit this to matched instructions that mayLoad/mayStore or have
3102       //       some other means of having a memoperand. Also limit this to
3103       //       emitted instructions that expect to have a memoperand too. For
3104       //       example, (G_SEXT (G_LOAD x)) that results in separate load and
3105       //       sign-extend instructions shouldn't put the memoperand on the
3106       //       sign-extend since it has no effect there.
3107       std::vector<unsigned> MergeInsnIDs;
3108       for (const auto &IDMatcherPair : Rule.defined_insn_vars())
3109         MergeInsnIDs.push_back(IDMatcherPair.second);
3110       llvm::sort(MergeInsnIDs);
3111       for (const auto &MergeInsnID : MergeInsnIDs)
3112         Table << MatchTable::IntValue(MergeInsnID);
3113       Table << MatchTable::NamedValue("GIU_MergeMemOperands_EndOfList")
3114             << MatchTable::LineBreak;
3115     }
3116 
3117     // FIXME: This is a hack but it's sufficient for ISel. We'll need to do
3118     //        better for combines. Particularly when there are multiple match
3119     //        roots.
3120     if (InsnID == 0)
3121       Table << MatchTable::Opcode("GIR_EraseFromParent")
3122             << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
3123             << MatchTable::LineBreak;
3124   }
3125 };
3126 
3127 /// Generates code to constrain the operands of an output instruction to the
3128 /// register classes specified by the definition of that instruction.
3129 class ConstrainOperandsToDefinitionAction : public MatchAction {
3130   unsigned InsnID;
3131 
3132 public:
3133   ConstrainOperandsToDefinitionAction(unsigned InsnID) : InsnID(InsnID) {}
3134 
3135   void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
3136     Table << MatchTable::Opcode("GIR_ConstrainSelectedInstOperands")
3137           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
3138           << MatchTable::LineBreak;
3139   }
3140 };
3141 
3142 /// Generates code to constrain the specified operand of an output instruction
3143 /// to the specified register class.
3144 class ConstrainOperandToRegClassAction : public MatchAction {
3145   unsigned InsnID;
3146   unsigned OpIdx;
3147   const CodeGenRegisterClass &RC;
3148 
3149 public:
3150   ConstrainOperandToRegClassAction(unsigned InsnID, unsigned OpIdx,
3151                                    const CodeGenRegisterClass &RC)
3152       : InsnID(InsnID), OpIdx(OpIdx), RC(RC) {}
3153 
3154   void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
3155     Table << MatchTable::Opcode("GIR_ConstrainOperandRC")
3156           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
3157           << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
3158           << MatchTable::NamedValue(RC.getQualifiedName() + "RegClassID")
3159           << MatchTable::LineBreak;
3160   }
3161 };
3162 
3163 /// Generates code to create a temporary register which can be used to chain
3164 /// instructions together.
3165 class MakeTempRegisterAction : public MatchAction {
3166 private:
3167   LLTCodeGen Ty;
3168   unsigned TempRegID;
3169 
3170 public:
3171   MakeTempRegisterAction(const LLTCodeGen &Ty, unsigned TempRegID)
3172       : Ty(Ty), TempRegID(TempRegID) {
3173     KnownTypes.insert(Ty);
3174   }
3175 
3176   void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
3177     Table << MatchTable::Opcode("GIR_MakeTempReg")
3178           << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID)
3179           << MatchTable::Comment("TypeID")
3180           << MatchTable::NamedValue(Ty.getCxxEnumValue())
3181           << MatchTable::LineBreak;
3182   }
3183 };
3184 
3185 InstructionMatcher &RuleMatcher::addInstructionMatcher(StringRef SymbolicName) {
3186   Matchers.emplace_back(new InstructionMatcher(*this, SymbolicName));
3187   MutatableInsns.insert(Matchers.back().get());
3188   return *Matchers.back();
3189 }
3190 
3191 void RuleMatcher::addRequiredFeature(Record *Feature) {
3192   RequiredFeatures.push_back(Feature);
3193 }
3194 
3195 const std::vector<Record *> &RuleMatcher::getRequiredFeatures() const {
3196   return RequiredFeatures;
3197 }
3198 
3199 // Emplaces an action of the specified Kind at the end of the action list.
3200 //
3201 // Returns a reference to the newly created action.
3202 //
3203 // Like std::vector::emplace_back(), may invalidate all iterators if the new
3204 // size exceeds the capacity. Otherwise, only invalidates the past-the-end
3205 // iterator.
3206 template <class Kind, class... Args>
3207 Kind &RuleMatcher::addAction(Args &&... args) {
3208   Actions.emplace_back(std::make_unique<Kind>(std::forward<Args>(args)...));
3209   return *static_cast<Kind *>(Actions.back().get());
3210 }
3211 
3212 // Emplaces an action of the specified Kind before the given insertion point.
3213 //
3214 // Returns an iterator pointing at the newly created instruction.
3215 //
3216 // Like std::vector::insert(), may invalidate all iterators if the new size
3217 // exceeds the capacity. Otherwise, only invalidates the iterators from the
3218 // insertion point onwards.
3219 template <class Kind, class... Args>
3220 action_iterator RuleMatcher::insertAction(action_iterator InsertPt,
3221                                           Args &&... args) {
3222   return Actions.emplace(InsertPt,
3223                          std::make_unique<Kind>(std::forward<Args>(args)...));
3224 }
3225 
3226 unsigned RuleMatcher::implicitlyDefineInsnVar(InstructionMatcher &Matcher) {
3227   unsigned NewInsnVarID = NextInsnVarID++;
3228   InsnVariableIDs[&Matcher] = NewInsnVarID;
3229   return NewInsnVarID;
3230 }
3231 
3232 unsigned RuleMatcher::getInsnVarID(InstructionMatcher &InsnMatcher) const {
3233   const auto &I = InsnVariableIDs.find(&InsnMatcher);
3234   if (I != InsnVariableIDs.end())
3235     return I->second;
3236   llvm_unreachable("Matched Insn was not captured in a local variable");
3237 }
3238 
3239 void RuleMatcher::defineOperand(StringRef SymbolicName, OperandMatcher &OM) {
3240   if (DefinedOperands.find(SymbolicName) == DefinedOperands.end()) {
3241     DefinedOperands[SymbolicName] = &OM;
3242     return;
3243   }
3244 
3245   // If the operand is already defined, then we must ensure both references in
3246   // the matcher have the exact same node.
3247   OM.addPredicate<SameOperandMatcher>(OM.getSymbolicName());
3248 }
3249 
3250 void RuleMatcher::definePhysRegOperand(Record *Reg, OperandMatcher &OM) {
3251   if (PhysRegOperands.find(Reg) == PhysRegOperands.end()) {
3252     PhysRegOperands[Reg] = &OM;
3253     return;
3254   }
3255 }
3256 
3257 InstructionMatcher &
3258 RuleMatcher::getInstructionMatcher(StringRef SymbolicName) const {
3259   for (const auto &I : InsnVariableIDs)
3260     if (I.first->getSymbolicName() == SymbolicName)
3261       return *I.first;
3262   llvm_unreachable(
3263       ("Failed to lookup instruction " + SymbolicName).str().c_str());
3264 }
3265 
3266 const OperandMatcher &
3267 RuleMatcher::getPhysRegOperandMatcher(Record *Reg) const {
3268   const auto &I = PhysRegOperands.find(Reg);
3269 
3270   if (I == PhysRegOperands.end()) {
3271     PrintFatalError(SrcLoc, "Register " + Reg->getName() +
3272                     " was not declared in matcher");
3273   }
3274 
3275   return *I->second;
3276 }
3277 
3278 const OperandMatcher &
3279 RuleMatcher::getOperandMatcher(StringRef Name) const {
3280   const auto &I = DefinedOperands.find(Name);
3281 
3282   if (I == DefinedOperands.end())
3283     PrintFatalError(SrcLoc, "Operand " + Name + " was not declared in matcher");
3284 
3285   return *I->second;
3286 }
3287 
3288 void RuleMatcher::emit(MatchTable &Table) {
3289   if (Matchers.empty())
3290     llvm_unreachable("Unexpected empty matcher!");
3291 
3292   // The representation supports rules that require multiple roots such as:
3293   //    %ptr(p0) = ...
3294   //    %elt0(s32) = G_LOAD %ptr
3295   //    %1(p0) = G_ADD %ptr, 4
3296   //    %elt1(s32) = G_LOAD p0 %1
3297   // which could be usefully folded into:
3298   //    %ptr(p0) = ...
3299   //    %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr
3300   // on some targets but we don't need to make use of that yet.
3301   assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
3302 
3303   unsigned LabelID = Table.allocateLabelID();
3304   Table << MatchTable::Opcode("GIM_Try", +1)
3305         << MatchTable::Comment("On fail goto")
3306         << MatchTable::JumpTarget(LabelID)
3307         << MatchTable::Comment(("Rule ID " + Twine(RuleID) + " //").str())
3308         << MatchTable::LineBreak;
3309 
3310   if (!RequiredFeatures.empty()) {
3311     Table << MatchTable::Opcode("GIM_CheckFeatures")
3312           << MatchTable::NamedValue(getNameForFeatureBitset(RequiredFeatures))
3313           << MatchTable::LineBreak;
3314   }
3315 
3316   Matchers.front()->emitPredicateOpcodes(Table, *this);
3317 
3318   // We must also check if it's safe to fold the matched instructions.
3319   if (InsnVariableIDs.size() >= 2) {
3320     // Invert the map to create stable ordering (by var names)
3321     SmallVector<unsigned, 2> InsnIDs;
3322     for (const auto &Pair : InsnVariableIDs) {
3323       // Skip the root node since it isn't moving anywhere. Everything else is
3324       // sinking to meet it.
3325       if (Pair.first == Matchers.front().get())
3326         continue;
3327 
3328       InsnIDs.push_back(Pair.second);
3329     }
3330     llvm::sort(InsnIDs);
3331 
3332     for (const auto &InsnID : InsnIDs) {
3333       // Reject the difficult cases until we have a more accurate check.
3334       Table << MatchTable::Opcode("GIM_CheckIsSafeToFold")
3335             << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
3336             << MatchTable::LineBreak;
3337 
3338       // FIXME: Emit checks to determine it's _actually_ safe to fold and/or
3339       //        account for unsafe cases.
3340       //
3341       //        Example:
3342       //          MI1--> %0 = ...
3343       //                 %1 = ... %0
3344       //          MI0--> %2 = ... %0
3345       //          It's not safe to erase MI1. We currently handle this by not
3346       //          erasing %0 (even when it's dead).
3347       //
3348       //        Example:
3349       //          MI1--> %0 = load volatile @a
3350       //                 %1 = load volatile @a
3351       //          MI0--> %2 = ... %0
3352       //          It's not safe to sink %0's def past %1. We currently handle
3353       //          this by rejecting all loads.
3354       //
3355       //        Example:
3356       //          MI1--> %0 = load @a
3357       //                 %1 = store @a
3358       //          MI0--> %2 = ... %0
3359       //          It's not safe to sink %0's def past %1. We currently handle
3360       //          this by rejecting all loads.
3361       //
3362       //        Example:
3363       //                   G_CONDBR %cond, @BB1
3364       //                 BB0:
3365       //          MI1-->   %0 = load @a
3366       //                   G_BR @BB1
3367       //                 BB1:
3368       //          MI0-->   %2 = ... %0
3369       //          It's not always safe to sink %0 across control flow. In this
3370       //          case it may introduce a memory fault. We currentl handle this
3371       //          by rejecting all loads.
3372     }
3373   }
3374 
3375   for (const auto &PM : EpilogueMatchers)
3376     PM->emitPredicateOpcodes(Table, *this);
3377 
3378   for (const auto &MA : Actions)
3379     MA->emitActionOpcodes(Table, *this);
3380 
3381   if (Table.isWithCoverage())
3382     Table << MatchTable::Opcode("GIR_Coverage") << MatchTable::IntValue(RuleID)
3383           << MatchTable::LineBreak;
3384   else
3385     Table << MatchTable::Comment(("GIR_Coverage, " + Twine(RuleID) + ",").str())
3386           << MatchTable::LineBreak;
3387 
3388   Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak
3389         << MatchTable::Label(LabelID);
3390   ++NumPatternEmitted;
3391 }
3392 
3393 bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
3394   // Rules involving more match roots have higher priority.
3395   if (Matchers.size() > B.Matchers.size())
3396     return true;
3397   if (Matchers.size() < B.Matchers.size())
3398     return false;
3399 
3400   for (auto Matcher : zip(Matchers, B.Matchers)) {
3401     if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher)))
3402       return true;
3403     if (std::get<1>(Matcher)->isHigherPriorityThan(*std::get<0>(Matcher)))
3404       return false;
3405   }
3406 
3407   return false;
3408 }
3409 
3410 unsigned RuleMatcher::countRendererFns() const {
3411   return std::accumulate(
3412       Matchers.begin(), Matchers.end(), 0,
3413       [](unsigned A, const std::unique_ptr<InstructionMatcher> &Matcher) {
3414         return A + Matcher->countRendererFns();
3415       });
3416 }
3417 
3418 bool OperandPredicateMatcher::isHigherPriorityThan(
3419     const OperandPredicateMatcher &B) const {
3420   // Generally speaking, an instruction is more important than an Int or a
3421   // LiteralInt because it can cover more nodes but theres an exception to
3422   // this. G_CONSTANT's are less important than either of those two because they
3423   // are more permissive.
3424 
3425   const InstructionOperandMatcher *AOM =
3426       dyn_cast<InstructionOperandMatcher>(this);
3427   const InstructionOperandMatcher *BOM =
3428       dyn_cast<InstructionOperandMatcher>(&B);
3429   bool AIsConstantInsn = AOM && AOM->getInsnMatcher().isConstantInstruction();
3430   bool BIsConstantInsn = BOM && BOM->getInsnMatcher().isConstantInstruction();
3431 
3432   if (AOM && BOM) {
3433     // The relative priorities between a G_CONSTANT and any other instruction
3434     // don't actually matter but this code is needed to ensure a strict weak
3435     // ordering. This is particularly important on Windows where the rules will
3436     // be incorrectly sorted without it.
3437     if (AIsConstantInsn != BIsConstantInsn)
3438       return AIsConstantInsn < BIsConstantInsn;
3439     return false;
3440   }
3441 
3442   if (AOM && AIsConstantInsn && (B.Kind == OPM_Int || B.Kind == OPM_LiteralInt))
3443     return false;
3444   if (BOM && BIsConstantInsn && (Kind == OPM_Int || Kind == OPM_LiteralInt))
3445     return true;
3446 
3447   return Kind < B.Kind;
3448 }
3449 
3450 void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
3451                                               RuleMatcher &Rule) const {
3452   const OperandMatcher &OtherOM = Rule.getOperandMatcher(MatchingName);
3453   unsigned OtherInsnVarID = Rule.getInsnVarID(OtherOM.getInstructionMatcher());
3454   assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getInsnVarID());
3455 
3456   Table << MatchTable::Opcode("GIM_CheckIsSameOperand")
3457         << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
3458         << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx)
3459         << MatchTable::Comment("OtherMI")
3460         << MatchTable::IntValue(OtherInsnVarID)
3461         << MatchTable::Comment("OtherOpIdx")
3462         << MatchTable::IntValue(OtherOM.getOpIdx())
3463         << MatchTable::LineBreak;
3464 }
3465 
3466 //===- GlobalISelEmitter class --------------------------------------------===//
3467 
3468 static Expected<LLTCodeGen> getInstResultType(const TreePatternNode *Dst) {
3469   ArrayRef<TypeSetByHwMode> ChildTypes = Dst->getExtTypes();
3470   if (ChildTypes.size() != 1)
3471     return failedImport("Dst pattern child has multiple results");
3472 
3473   Optional<LLTCodeGen> MaybeOpTy;
3474   if (ChildTypes.front().isMachineValueType()) {
3475     MaybeOpTy =
3476       MVTToLLT(ChildTypes.front().getMachineValueType().SimpleTy);
3477   }
3478 
3479   if (!MaybeOpTy)
3480     return failedImport("Dst operand has an unsupported type");
3481   return *MaybeOpTy;
3482 }
3483 
3484 class GlobalISelEmitter {
3485 public:
3486   explicit GlobalISelEmitter(RecordKeeper &RK);
3487   void run(raw_ostream &OS);
3488 
3489 private:
3490   const RecordKeeper &RK;
3491   const CodeGenDAGPatterns CGP;
3492   const CodeGenTarget &Target;
3493   CodeGenRegBank &CGRegs;
3494 
3495   /// Keep track of the equivalence between SDNodes and Instruction by mapping
3496   /// SDNodes to the GINodeEquiv mapping. We need to map to the GINodeEquiv to
3497   /// check for attributes on the relation such as CheckMMOIsNonAtomic.
3498   /// This is defined using 'GINodeEquiv' in the target description.
3499   DenseMap<Record *, Record *> NodeEquivs;
3500 
3501   /// Keep track of the equivalence between ComplexPattern's and
3502   /// GIComplexOperandMatcher. Map entries are specified by subclassing
3503   /// GIComplexPatternEquiv.
3504   DenseMap<const Record *, const Record *> ComplexPatternEquivs;
3505 
3506   /// Keep track of the equivalence between SDNodeXForm's and
3507   /// GICustomOperandRenderer. Map entries are specified by subclassing
3508   /// GISDNodeXFormEquiv.
3509   DenseMap<const Record *, const Record *> SDNodeXFormEquivs;
3510 
3511   /// Keep track of Scores of PatternsToMatch similar to how the DAG does.
3512   /// This adds compatibility for RuleMatchers to use this for ordering rules.
3513   DenseMap<uint64_t, int> RuleMatcherScores;
3514 
3515   // Map of predicates to their subtarget features.
3516   SubtargetFeatureInfoMap SubtargetFeatures;
3517 
3518   // Rule coverage information.
3519   Optional<CodeGenCoverage> RuleCoverage;
3520 
3521   /// Variables used to help with collecting of named operands for predicates
3522   /// with 'let PredicateCodeUsesOperands = 1'. WaitingForNamedOperands is set
3523   /// to the number of named operands that predicate expects. Store locations in
3524   /// StoreIdxForName correspond to the order in which operand names appear in
3525   /// predicate's argument list.
3526   /// When we visit named leaf operand and WaitingForNamedOperands is not zero,
3527   /// add matcher that will record operand and decrease counter.
3528   unsigned WaitingForNamedOperands = 0;
3529   StringMap<unsigned> StoreIdxForName;
3530 
3531   void gatherOpcodeValues();
3532   void gatherTypeIDValues();
3533   void gatherNodeEquivs();
3534 
3535   Record *findNodeEquiv(Record *N) const;
3536   const CodeGenInstruction *getEquivNode(Record &Equiv,
3537                                          const TreePatternNode *N) const;
3538 
3539   Error importRulePredicates(RuleMatcher &M, ArrayRef<Predicate> Predicates);
3540   Expected<InstructionMatcher &>
3541   createAndImportSelDAGMatcher(RuleMatcher &Rule,
3542                                InstructionMatcher &InsnMatcher,
3543                                const TreePatternNode *Src, unsigned &TempOpIdx);
3544   Error importComplexPatternOperandMatcher(OperandMatcher &OM, Record *R,
3545                                            unsigned &TempOpIdx) const;
3546   Error importChildMatcher(RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
3547                            const TreePatternNode *SrcChild,
3548                            bool OperandIsAPointer, bool OperandIsImmArg,
3549                            unsigned OpIdx, unsigned &TempOpIdx);
3550 
3551   Expected<BuildMIAction &> createAndImportInstructionRenderer(
3552       RuleMatcher &M, InstructionMatcher &InsnMatcher,
3553       const TreePatternNode *Src, const TreePatternNode *Dst);
3554   Expected<action_iterator> createAndImportSubInstructionRenderer(
3555       action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst,
3556       unsigned TempReg);
3557   Expected<action_iterator>
3558   createInstructionRenderer(action_iterator InsertPt, RuleMatcher &M,
3559                             const TreePatternNode *Dst);
3560 
3561   Expected<action_iterator>
3562   importExplicitDefRenderers(action_iterator InsertPt, RuleMatcher &M,
3563                              BuildMIAction &DstMIBuilder,
3564                              const TreePatternNode *Dst);
3565 
3566   Expected<action_iterator>
3567   importExplicitUseRenderers(action_iterator InsertPt, RuleMatcher &M,
3568                              BuildMIAction &DstMIBuilder,
3569                              const llvm::TreePatternNode *Dst);
3570   Expected<action_iterator>
3571   importExplicitUseRenderer(action_iterator InsertPt, RuleMatcher &Rule,
3572                             BuildMIAction &DstMIBuilder,
3573                             TreePatternNode *DstChild);
3574   Error importDefaultOperandRenderers(action_iterator InsertPt, RuleMatcher &M,
3575                                       BuildMIAction &DstMIBuilder,
3576                                       DagInit *DefaultOps) const;
3577   Error
3578   importImplicitDefRenderers(BuildMIAction &DstMIBuilder,
3579                              const std::vector<Record *> &ImplicitDefs) const;
3580 
3581   void emitCxxPredicateFns(raw_ostream &OS, StringRef CodeFieldName,
3582                            StringRef TypeIdentifier, StringRef ArgType,
3583                            StringRef ArgName, StringRef AdditionalArgs,
3584                            StringRef AdditionalDeclarations,
3585                            std::function<bool(const Record *R)> Filter);
3586   void emitImmPredicateFns(raw_ostream &OS, StringRef TypeIdentifier,
3587                            StringRef ArgType,
3588                            std::function<bool(const Record *R)> Filter);
3589   void emitMIPredicateFns(raw_ostream &OS);
3590 
3591   /// Analyze pattern \p P, returning a matcher for it if possible.
3592   /// Otherwise, return an Error explaining why we don't support it.
3593   Expected<RuleMatcher> runOnPattern(const PatternToMatch &P);
3594 
3595   void declareSubtargetFeature(Record *Predicate);
3596 
3597   MatchTable buildMatchTable(MutableArrayRef<RuleMatcher> Rules, bool Optimize,
3598                              bool WithCoverage);
3599 
3600   /// Infer a CodeGenRegisterClass for the type of \p SuperRegNode. The returned
3601   /// CodeGenRegisterClass will support the CodeGenRegisterClass of
3602   /// \p SubRegNode, and the subregister index defined by \p SubRegIdxNode.
3603   /// If no register class is found, return None.
3604   Optional<const CodeGenRegisterClass *>
3605   inferSuperRegisterClassForNode(const TypeSetByHwMode &Ty,
3606                                  TreePatternNode *SuperRegNode,
3607                                  TreePatternNode *SubRegIdxNode);
3608   Optional<CodeGenSubRegIndex *>
3609   inferSubRegIndexForNode(TreePatternNode *SubRegIdxNode);
3610 
3611   /// Infer a CodeGenRegisterClass which suppoorts \p Ty and \p SubRegIdxNode.
3612   /// Return None if no such class exists.
3613   Optional<const CodeGenRegisterClass *>
3614   inferSuperRegisterClass(const TypeSetByHwMode &Ty,
3615                           TreePatternNode *SubRegIdxNode);
3616 
3617   /// Return the CodeGenRegisterClass associated with \p Leaf if it has one.
3618   Optional<const CodeGenRegisterClass *>
3619   getRegClassFromLeaf(TreePatternNode *Leaf);
3620 
3621   /// Return a CodeGenRegisterClass for \p N if one can be found. Return None
3622   /// otherwise.
3623   Optional<const CodeGenRegisterClass *>
3624   inferRegClassFromPattern(TreePatternNode *N);
3625 
3626   // Add builtin predicates.
3627   Expected<InstructionMatcher &>
3628   addBuiltinPredicates(const Record *SrcGIEquivOrNull,
3629                        const TreePredicateFn &Predicate,
3630                        InstructionMatcher &InsnMatcher, bool &HasAddedMatcher);
3631 
3632 public:
3633   /// Takes a sequence of \p Rules and group them based on the predicates
3634   /// they share. \p MatcherStorage is used as a memory container
3635   /// for the group that are created as part of this process.
3636   ///
3637   /// What this optimization does looks like if GroupT = GroupMatcher:
3638   /// Output without optimization:
3639   /// \verbatim
3640   /// # R1
3641   ///  # predicate A
3642   ///  # predicate B
3643   ///  ...
3644   /// # R2
3645   ///  # predicate A // <-- effectively this is going to be checked twice.
3646   ///                //     Once in R1 and once in R2.
3647   ///  # predicate C
3648   /// \endverbatim
3649   /// Output with optimization:
3650   /// \verbatim
3651   /// # Group1_2
3652   ///  # predicate A // <-- Check is now shared.
3653   ///  # R1
3654   ///   # predicate B
3655   ///  # R2
3656   ///   # predicate C
3657   /// \endverbatim
3658   template <class GroupT>
3659   static std::vector<Matcher *> optimizeRules(
3660       ArrayRef<Matcher *> Rules,
3661       std::vector<std::unique_ptr<Matcher>> &MatcherStorage);
3662 };
3663 
3664 void GlobalISelEmitter::gatherOpcodeValues() {
3665   InstructionOpcodeMatcher::initOpcodeValuesMap(Target);
3666 }
3667 
3668 void GlobalISelEmitter::gatherTypeIDValues() {
3669   LLTOperandMatcher::initTypeIDValuesMap();
3670 }
3671 
3672 void GlobalISelEmitter::gatherNodeEquivs() {
3673   assert(NodeEquivs.empty());
3674   for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
3675     NodeEquivs[Equiv->getValueAsDef("Node")] = Equiv;
3676 
3677   assert(ComplexPatternEquivs.empty());
3678   for (Record *Equiv : RK.getAllDerivedDefinitions("GIComplexPatternEquiv")) {
3679     Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
3680     if (!SelDAGEquiv)
3681       continue;
3682     ComplexPatternEquivs[SelDAGEquiv] = Equiv;
3683  }
3684 
3685  assert(SDNodeXFormEquivs.empty());
3686  for (Record *Equiv : RK.getAllDerivedDefinitions("GISDNodeXFormEquiv")) {
3687    Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
3688    if (!SelDAGEquiv)
3689      continue;
3690    SDNodeXFormEquivs[SelDAGEquiv] = Equiv;
3691  }
3692 }
3693 
3694 Record *GlobalISelEmitter::findNodeEquiv(Record *N) const {
3695   return NodeEquivs.lookup(N);
3696 }
3697 
3698 const CodeGenInstruction *
3699 GlobalISelEmitter::getEquivNode(Record &Equiv, const TreePatternNode *N) const {
3700   if (N->getNumChildren() >= 1) {
3701     // setcc operation maps to two different G_* instructions based on the type.
3702     if (!Equiv.isValueUnset("IfFloatingPoint") &&
3703         MVT(N->getChild(0)->getSimpleType(0)).isFloatingPoint())
3704       return &Target.getInstruction(Equiv.getValueAsDef("IfFloatingPoint"));
3705   }
3706 
3707   for (const TreePredicateCall &Call : N->getPredicateCalls()) {
3708     const TreePredicateFn &Predicate = Call.Fn;
3709     if (!Equiv.isValueUnset("IfSignExtend") && Predicate.isLoad() &&
3710         Predicate.isSignExtLoad())
3711       return &Target.getInstruction(Equiv.getValueAsDef("IfSignExtend"));
3712     if (!Equiv.isValueUnset("IfZeroExtend") && Predicate.isLoad() &&
3713         Predicate.isZeroExtLoad())
3714       return &Target.getInstruction(Equiv.getValueAsDef("IfZeroExtend"));
3715   }
3716 
3717   return &Target.getInstruction(Equiv.getValueAsDef("I"));
3718 }
3719 
3720 GlobalISelEmitter::GlobalISelEmitter(RecordKeeper &RK)
3721     : RK(RK), CGP(RK), Target(CGP.getTargetInfo()),
3722       CGRegs(Target.getRegBank()) {}
3723 
3724 //===- Emitter ------------------------------------------------------------===//
3725 
3726 Error
3727 GlobalISelEmitter::importRulePredicates(RuleMatcher &M,
3728                                         ArrayRef<Predicate> Predicates) {
3729   for (const Predicate &P : Predicates) {
3730     if (!P.Def || P.getCondString().empty())
3731       continue;
3732     declareSubtargetFeature(P.Def);
3733     M.addRequiredFeature(P.Def);
3734   }
3735 
3736   return Error::success();
3737 }
3738 
3739 Expected<InstructionMatcher &> GlobalISelEmitter::addBuiltinPredicates(
3740     const Record *SrcGIEquivOrNull, const TreePredicateFn &Predicate,
3741     InstructionMatcher &InsnMatcher, bool &HasAddedMatcher) {
3742   if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
3743     if (const ListInit *AddrSpaces = Predicate.getAddressSpaces()) {
3744       SmallVector<unsigned, 4> ParsedAddrSpaces;
3745 
3746       for (Init *Val : AddrSpaces->getValues()) {
3747         IntInit *IntVal = dyn_cast<IntInit>(Val);
3748         if (!IntVal)
3749           return failedImport("Address space is not an integer");
3750         ParsedAddrSpaces.push_back(IntVal->getValue());
3751       }
3752 
3753       if (!ParsedAddrSpaces.empty()) {
3754         InsnMatcher.addPredicate<MemoryAddressSpacePredicateMatcher>(
3755             0, ParsedAddrSpaces);
3756       }
3757     }
3758 
3759     int64_t MinAlign = Predicate.getMinAlignment();
3760     if (MinAlign > 0)
3761       InsnMatcher.addPredicate<MemoryAlignmentPredicateMatcher>(0, MinAlign);
3762   }
3763 
3764   // G_LOAD is used for both non-extending and any-extending loads.
3765   if (Predicate.isLoad() && Predicate.isNonExtLoad()) {
3766     InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3767         0, MemoryVsLLTSizePredicateMatcher::EqualTo, 0);
3768     return InsnMatcher;
3769   }
3770   if (Predicate.isLoad() && Predicate.isAnyExtLoad()) {
3771     InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3772         0, MemoryVsLLTSizePredicateMatcher::LessThan, 0);
3773     return InsnMatcher;
3774   }
3775 
3776   if (Predicate.isStore()) {
3777     if (Predicate.isTruncStore()) {
3778       // FIXME: If MemoryVT is set, we end up with 2 checks for the MMO size.
3779       InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3780           0, MemoryVsLLTSizePredicateMatcher::LessThan, 0);
3781       return InsnMatcher;
3782     }
3783     if (Predicate.isNonTruncStore()) {
3784       // We need to check the sizes match here otherwise we could incorrectly
3785       // match truncating stores with non-truncating ones.
3786       InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3787           0, MemoryVsLLTSizePredicateMatcher::EqualTo, 0);
3788     }
3789   }
3790 
3791   // No check required. We already did it by swapping the opcode.
3792   if (!SrcGIEquivOrNull->isValueUnset("IfSignExtend") &&
3793       Predicate.isSignExtLoad())
3794     return InsnMatcher;
3795 
3796   // No check required. We already did it by swapping the opcode.
3797   if (!SrcGIEquivOrNull->isValueUnset("IfZeroExtend") &&
3798       Predicate.isZeroExtLoad())
3799     return InsnMatcher;
3800 
3801   // No check required. G_STORE by itself is a non-extending store.
3802   if (Predicate.isNonTruncStore())
3803     return InsnMatcher;
3804 
3805   if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
3806     if (Predicate.getMemoryVT() != nullptr) {
3807       Optional<LLTCodeGen> MemTyOrNone =
3808           MVTToLLT(getValueType(Predicate.getMemoryVT()));
3809 
3810       if (!MemTyOrNone)
3811         return failedImport("MemVT could not be converted to LLT");
3812 
3813       // MMO's work in bytes so we must take care of unusual types like i1
3814       // don't round down.
3815       unsigned MemSizeInBits =
3816           llvm::alignTo(MemTyOrNone->get().getSizeInBits(), 8);
3817 
3818       InsnMatcher.addPredicate<MemorySizePredicateMatcher>(0,
3819                                                            MemSizeInBits / 8);
3820       return InsnMatcher;
3821     }
3822   }
3823 
3824   if (Predicate.isLoad() || Predicate.isStore()) {
3825     // No check required. A G_LOAD/G_STORE is an unindexed load.
3826     if (Predicate.isUnindexed())
3827       return InsnMatcher;
3828   }
3829 
3830   if (Predicate.isAtomic()) {
3831     if (Predicate.isAtomicOrderingMonotonic()) {
3832       InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Monotonic");
3833       return InsnMatcher;
3834     }
3835     if (Predicate.isAtomicOrderingAcquire()) {
3836       InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Acquire");
3837       return InsnMatcher;
3838     }
3839     if (Predicate.isAtomicOrderingRelease()) {
3840       InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Release");
3841       return InsnMatcher;
3842     }
3843     if (Predicate.isAtomicOrderingAcquireRelease()) {
3844       InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3845           "AcquireRelease");
3846       return InsnMatcher;
3847     }
3848     if (Predicate.isAtomicOrderingSequentiallyConsistent()) {
3849       InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3850           "SequentiallyConsistent");
3851       return InsnMatcher;
3852     }
3853   }
3854 
3855   if (Predicate.isAtomicOrderingAcquireOrStronger()) {
3856     InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3857         "Acquire", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
3858     return InsnMatcher;
3859   }
3860   if (Predicate.isAtomicOrderingWeakerThanAcquire()) {
3861     InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3862         "Acquire", AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
3863     return InsnMatcher;
3864   }
3865 
3866   if (Predicate.isAtomicOrderingReleaseOrStronger()) {
3867     InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3868         "Release", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
3869     return InsnMatcher;
3870   }
3871   if (Predicate.isAtomicOrderingWeakerThanRelease()) {
3872     InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3873         "Release", AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
3874     return InsnMatcher;
3875   }
3876   HasAddedMatcher = false;
3877   return InsnMatcher;
3878 }
3879 
3880 Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher(
3881     RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
3882     const TreePatternNode *Src, unsigned &TempOpIdx) {
3883   Record *SrcGIEquivOrNull = nullptr;
3884   const CodeGenInstruction *SrcGIOrNull = nullptr;
3885 
3886   // Start with the defined operands (i.e., the results of the root operator).
3887   if (Src->getExtTypes().size() > 1)
3888     return failedImport("Src pattern has multiple results");
3889 
3890   if (Src->isLeaf()) {
3891     Init *SrcInit = Src->getLeafValue();
3892     if (isa<IntInit>(SrcInit)) {
3893       InsnMatcher.addPredicate<InstructionOpcodeMatcher>(
3894           &Target.getInstruction(RK.getDef("G_CONSTANT")));
3895     } else
3896       return failedImport(
3897           "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
3898   } else {
3899     SrcGIEquivOrNull = findNodeEquiv(Src->getOperator());
3900     if (!SrcGIEquivOrNull)
3901       return failedImport("Pattern operator lacks an equivalent Instruction" +
3902                           explainOperator(Src->getOperator()));
3903     SrcGIOrNull = getEquivNode(*SrcGIEquivOrNull, Src);
3904 
3905     // The operators look good: match the opcode
3906     InsnMatcher.addPredicate<InstructionOpcodeMatcher>(SrcGIOrNull);
3907   }
3908 
3909   unsigned OpIdx = 0;
3910   for (const TypeSetByHwMode &VTy : Src->getExtTypes()) {
3911     // Results don't have a name unless they are the root node. The caller will
3912     // set the name if appropriate.
3913     OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
3914     if (auto Error = OM.addTypeCheckPredicate(VTy, false /* OperandIsAPointer */))
3915       return failedImport(toString(std::move(Error)) +
3916                           " for result of Src pattern operator");
3917   }
3918 
3919   for (const TreePredicateCall &Call : Src->getPredicateCalls()) {
3920     const TreePredicateFn &Predicate = Call.Fn;
3921     bool HasAddedBuiltinMatcher = true;
3922     if (Predicate.isAlwaysTrue())
3923       continue;
3924 
3925     if (Predicate.isImmediatePattern()) {
3926       InsnMatcher.addPredicate<InstructionImmPredicateMatcher>(Predicate);
3927       continue;
3928     }
3929 
3930     auto InsnMatcherOrError = addBuiltinPredicates(
3931         SrcGIEquivOrNull, Predicate, InsnMatcher, HasAddedBuiltinMatcher);
3932     if (auto Error = InsnMatcherOrError.takeError())
3933       return std::move(Error);
3934 
3935     if (Predicate.hasGISelPredicateCode()) {
3936       if (Predicate.usesOperands()) {
3937         assert(WaitingForNamedOperands == 0 &&
3938                "previous predicate didn't find all operands or "
3939                "nested predicate that uses operands");
3940         TreePattern *TP = Predicate.getOrigPatFragRecord();
3941         WaitingForNamedOperands = TP->getNumArgs();
3942         for (unsigned i = 0; i < WaitingForNamedOperands; ++i)
3943           StoreIdxForName[getScopedName(Call.Scope, TP->getArgName(i))] = i;
3944       }
3945       InsnMatcher.addPredicate<GenericInstructionPredicateMatcher>(Predicate);
3946       continue;
3947     }
3948     if (!HasAddedBuiltinMatcher) {
3949       return failedImport("Src pattern child has predicate (" +
3950                           explainPredicates(Src) + ")");
3951     }
3952   }
3953 
3954   bool IsAtomic = false;
3955   if (SrcGIEquivOrNull && SrcGIEquivOrNull->getValueAsBit("CheckMMOIsNonAtomic"))
3956     InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("NotAtomic");
3957   else if (SrcGIEquivOrNull && SrcGIEquivOrNull->getValueAsBit("CheckMMOIsAtomic")) {
3958     IsAtomic = true;
3959     InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3960       "Unordered", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
3961   }
3962 
3963   if (Src->isLeaf()) {
3964     Init *SrcInit = Src->getLeafValue();
3965     if (IntInit *SrcIntInit = dyn_cast<IntInit>(SrcInit)) {
3966       OperandMatcher &OM =
3967           InsnMatcher.addOperand(OpIdx++, Src->getName(), TempOpIdx);
3968       OM.addPredicate<LiteralIntOperandMatcher>(SrcIntInit->getValue());
3969     } else
3970       return failedImport(
3971           "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
3972   } else {
3973     assert(SrcGIOrNull &&
3974            "Expected to have already found an equivalent Instruction");
3975     if (SrcGIOrNull->TheDef->getName() == "G_CONSTANT" ||
3976         SrcGIOrNull->TheDef->getName() == "G_FCONSTANT") {
3977       // imm/fpimm still have operands but we don't need to do anything with it
3978       // here since we don't support ImmLeaf predicates yet. However, we still
3979       // need to note the hidden operand to get GIM_CheckNumOperands correct.
3980       InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
3981       return InsnMatcher;
3982     }
3983 
3984     // Special case because the operand order is changed from setcc. The
3985     // predicate operand needs to be swapped from the last operand to the first
3986     // source.
3987 
3988     unsigned NumChildren = Src->getNumChildren();
3989     bool IsFCmp = SrcGIOrNull->TheDef->getName() == "G_FCMP";
3990 
3991     if (IsFCmp || SrcGIOrNull->TheDef->getName() == "G_ICMP") {
3992       TreePatternNode *SrcChild = Src->getChild(NumChildren - 1);
3993       if (SrcChild->isLeaf()) {
3994         DefInit *DI = dyn_cast<DefInit>(SrcChild->getLeafValue());
3995         Record *CCDef = DI ? DI->getDef() : nullptr;
3996         if (!CCDef || !CCDef->isSubClassOf("CondCode"))
3997           return failedImport("Unable to handle CondCode");
3998 
3999         OperandMatcher &OM =
4000           InsnMatcher.addOperand(OpIdx++, SrcChild->getName(), TempOpIdx);
4001         StringRef PredType = IsFCmp ? CCDef->getValueAsString("FCmpPredicate") :
4002                                       CCDef->getValueAsString("ICmpPredicate");
4003 
4004         if (!PredType.empty()) {
4005           OM.addPredicate<CmpPredicateOperandMatcher>(std::string(PredType));
4006           // Process the other 2 operands normally.
4007           --NumChildren;
4008         }
4009       }
4010     }
4011 
4012     // Hack around an unfortunate mistake in how atomic store (and really
4013     // atomicrmw in general) operands were ordered. A ISD::STORE used the order
4014     // <stored value>, <pointer> order. ISD::ATOMIC_STORE used the opposite,
4015     // <pointer>, <stored value>. In GlobalISel there's just the one store
4016     // opcode, so we need to swap the operands here to get the right type check.
4017     if (IsAtomic && SrcGIOrNull->TheDef->getName() == "G_STORE") {
4018       assert(NumChildren == 2 && "wrong operands for atomic store");
4019 
4020       TreePatternNode *PtrChild = Src->getChild(0);
4021       TreePatternNode *ValueChild = Src->getChild(1);
4022 
4023       if (auto Error = importChildMatcher(Rule, InsnMatcher, PtrChild, true,
4024                                           false, 1, TempOpIdx))
4025         return std::move(Error);
4026 
4027       if (auto Error = importChildMatcher(Rule, InsnMatcher, ValueChild, false,
4028                                           false, 0, TempOpIdx))
4029         return std::move(Error);
4030       return InsnMatcher;
4031     }
4032 
4033     // Match the used operands (i.e. the children of the operator).
4034     bool IsIntrinsic =
4035         SrcGIOrNull->TheDef->getName() == "G_INTRINSIC" ||
4036         SrcGIOrNull->TheDef->getName() == "G_INTRINSIC_W_SIDE_EFFECTS";
4037     const CodeGenIntrinsic *II = Src->getIntrinsicInfo(CGP);
4038     if (IsIntrinsic && !II)
4039       return failedImport("Expected IntInit containing intrinsic ID)");
4040 
4041     for (unsigned i = 0; i != NumChildren; ++i) {
4042       TreePatternNode *SrcChild = Src->getChild(i);
4043 
4044       // We need to determine the meaning of a literal integer based on the
4045       // context. If this is a field required to be an immediate (such as an
4046       // immarg intrinsic argument), the required predicates are different than
4047       // a constant which may be materialized in a register. If we have an
4048       // argument that is required to be an immediate, we should not emit an LLT
4049       // type check, and should not be looking for a G_CONSTANT defined
4050       // register.
4051       bool OperandIsImmArg = SrcGIOrNull->isOperandImmArg(i);
4052 
4053       // SelectionDAG allows pointers to be represented with iN since it doesn't
4054       // distinguish between pointers and integers but they are different types in GlobalISel.
4055       // Coerce integers to pointers to address space 0 if the context indicates a pointer.
4056       //
4057       bool OperandIsAPointer = SrcGIOrNull->isOperandAPointer(i);
4058 
4059       if (IsIntrinsic) {
4060         // For G_INTRINSIC/G_INTRINSIC_W_SIDE_EFFECTS, the operand immediately
4061         // following the defs is an intrinsic ID.
4062         if (i == 0) {
4063           OperandMatcher &OM =
4064               InsnMatcher.addOperand(OpIdx++, SrcChild->getName(), TempOpIdx);
4065           OM.addPredicate<IntrinsicIDOperandMatcher>(II);
4066           continue;
4067         }
4068 
4069         // We have to check intrinsics for llvm_anyptr_ty and immarg parameters.
4070         //
4071         // Note that we have to look at the i-1th parameter, because we don't
4072         // have the intrinsic ID in the intrinsic's parameter list.
4073         OperandIsAPointer |= II->isParamAPointer(i - 1);
4074         OperandIsImmArg |= II->isParamImmArg(i - 1);
4075       }
4076 
4077       if (auto Error =
4078               importChildMatcher(Rule, InsnMatcher, SrcChild, OperandIsAPointer,
4079                                  OperandIsImmArg, OpIdx++, TempOpIdx))
4080         return std::move(Error);
4081     }
4082   }
4083 
4084   return InsnMatcher;
4085 }
4086 
4087 Error GlobalISelEmitter::importComplexPatternOperandMatcher(
4088     OperandMatcher &OM, Record *R, unsigned &TempOpIdx) const {
4089   const auto &ComplexPattern = ComplexPatternEquivs.find(R);
4090   if (ComplexPattern == ComplexPatternEquivs.end())
4091     return failedImport("SelectionDAG ComplexPattern (" + R->getName() +
4092                         ") not mapped to GlobalISel");
4093 
4094   OM.addPredicate<ComplexPatternOperandMatcher>(OM, *ComplexPattern->second);
4095   TempOpIdx++;
4096   return Error::success();
4097 }
4098 
4099 // Get the name to use for a pattern operand. For an anonymous physical register
4100 // input, this should use the register name.
4101 static StringRef getSrcChildName(const TreePatternNode *SrcChild,
4102                                  Record *&PhysReg) {
4103   StringRef SrcChildName = SrcChild->getName();
4104   if (SrcChildName.empty() && SrcChild->isLeaf()) {
4105     if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
4106       auto *ChildRec = ChildDefInit->getDef();
4107       if (ChildRec->isSubClassOf("Register")) {
4108         SrcChildName = ChildRec->getName();
4109         PhysReg = ChildRec;
4110       }
4111     }
4112   }
4113 
4114   return SrcChildName;
4115 }
4116 
4117 Error GlobalISelEmitter::importChildMatcher(
4118     RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
4119     const TreePatternNode *SrcChild, bool OperandIsAPointer,
4120     bool OperandIsImmArg, unsigned OpIdx, unsigned &TempOpIdx) {
4121 
4122   Record *PhysReg = nullptr;
4123   std::string SrcChildName = std::string(getSrcChildName(SrcChild, PhysReg));
4124   if (!SrcChild->isLeaf() &&
4125       SrcChild->getOperator()->isSubClassOf("ComplexPattern")) {
4126     // The "name" of a non-leaf complex pattern (MY_PAT $op1, $op2) is
4127     // "MY_PAT:op1:op2" and the ones with same "name" represent same operand.
4128     std::string PatternName = std::string(SrcChild->getOperator()->getName());
4129     for (unsigned i = 0; i < SrcChild->getNumChildren(); ++i) {
4130       PatternName += ":";
4131       PatternName += SrcChild->getChild(i)->getName();
4132     }
4133     SrcChildName = PatternName;
4134   }
4135 
4136   OperandMatcher &OM =
4137       PhysReg ? InsnMatcher.addPhysRegInput(PhysReg, OpIdx, TempOpIdx)
4138               : InsnMatcher.addOperand(OpIdx, SrcChildName, TempOpIdx);
4139   if (OM.isSameAsAnotherOperand())
4140     return Error::success();
4141 
4142   ArrayRef<TypeSetByHwMode> ChildTypes = SrcChild->getExtTypes();
4143   if (ChildTypes.size() != 1)
4144     return failedImport("Src pattern child has multiple results");
4145 
4146   // Check MBB's before the type check since they are not a known type.
4147   if (!SrcChild->isLeaf()) {
4148     if (SrcChild->getOperator()->isSubClassOf("SDNode")) {
4149       auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator());
4150       if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
4151         OM.addPredicate<MBBOperandMatcher>();
4152         return Error::success();
4153       }
4154       if (SrcChild->getOperator()->getName() == "timm") {
4155         OM.addPredicate<ImmOperandMatcher>();
4156         return Error::success();
4157       }
4158     }
4159   }
4160 
4161   // Immediate arguments have no meaningful type to check as they don't have
4162   // registers.
4163   if (!OperandIsImmArg) {
4164     if (auto Error =
4165             OM.addTypeCheckPredicate(ChildTypes.front(), OperandIsAPointer))
4166       return failedImport(toString(std::move(Error)) + " for Src operand (" +
4167                           to_string(*SrcChild) + ")");
4168   }
4169 
4170   // Check for nested instructions.
4171   if (!SrcChild->isLeaf()) {
4172     if (SrcChild->getOperator()->isSubClassOf("ComplexPattern")) {
4173       // When a ComplexPattern is used as an operator, it should do the same
4174       // thing as when used as a leaf. However, the children of the operator
4175       // name the sub-operands that make up the complex operand and we must
4176       // prepare to reference them in the renderer too.
4177       unsigned RendererID = TempOpIdx;
4178       if (auto Error = importComplexPatternOperandMatcher(
4179               OM, SrcChild->getOperator(), TempOpIdx))
4180         return Error;
4181 
4182       for (unsigned i = 0, e = SrcChild->getNumChildren(); i != e; ++i) {
4183         auto *SubOperand = SrcChild->getChild(i);
4184         if (!SubOperand->getName().empty()) {
4185           if (auto Error = Rule.defineComplexSubOperand(
4186                   SubOperand->getName(), SrcChild->getOperator(), RendererID, i,
4187                   SrcChildName))
4188             return Error;
4189         }
4190       }
4191 
4192       return Error::success();
4193     }
4194 
4195     auto MaybeInsnOperand = OM.addPredicate<InstructionOperandMatcher>(
4196         InsnMatcher.getRuleMatcher(), SrcChild->getName());
4197     if (!MaybeInsnOperand.hasValue()) {
4198       // This isn't strictly true. If the user were to provide exactly the same
4199       // matchers as the original operand then we could allow it. However, it's
4200       // simpler to not permit the redundant specification.
4201       return failedImport("Nested instruction cannot be the same as another operand");
4202     }
4203 
4204     // Map the node to a gMIR instruction.
4205     InstructionOperandMatcher &InsnOperand = **MaybeInsnOperand;
4206     auto InsnMatcherOrError = createAndImportSelDAGMatcher(
4207         Rule, InsnOperand.getInsnMatcher(), SrcChild, TempOpIdx);
4208     if (auto Error = InsnMatcherOrError.takeError())
4209       return Error;
4210 
4211     return Error::success();
4212   }
4213 
4214   if (SrcChild->hasAnyPredicate())
4215     return failedImport("Src pattern child has unsupported predicate");
4216 
4217   // Check for constant immediates.
4218   if (auto *ChildInt = dyn_cast<IntInit>(SrcChild->getLeafValue())) {
4219     if (OperandIsImmArg) {
4220       // Checks for argument directly in operand list
4221       OM.addPredicate<LiteralIntOperandMatcher>(ChildInt->getValue());
4222     } else {
4223       // Checks for materialized constant
4224       OM.addPredicate<ConstantIntOperandMatcher>(ChildInt->getValue());
4225     }
4226     return Error::success();
4227   }
4228 
4229   // Check for def's like register classes or ComplexPattern's.
4230   if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
4231     auto *ChildRec = ChildDefInit->getDef();
4232 
4233     if (WaitingForNamedOperands) {
4234       auto PA = SrcChild->getNamesAsPredicateArg().begin();
4235       std::string Name = getScopedName(PA->getScope(), PA->getIdentifier());
4236       OM.addPredicate<RecordNamedOperandMatcher>(StoreIdxForName[Name], Name);
4237       --WaitingForNamedOperands;
4238     }
4239 
4240     // Check for register classes.
4241     if (ChildRec->isSubClassOf("RegisterClass") ||
4242         ChildRec->isSubClassOf("RegisterOperand")) {
4243       OM.addPredicate<RegisterBankOperandMatcher>(
4244           Target.getRegisterClass(getInitValueAsRegClass(ChildDefInit)));
4245       return Error::success();
4246     }
4247 
4248     if (ChildRec->isSubClassOf("Register")) {
4249       // This just be emitted as a copy to the specific register.
4250       ValueTypeByHwMode VT = ChildTypes.front().getValueTypeByHwMode();
4251       const CodeGenRegisterClass *RC
4252         = CGRegs.getMinimalPhysRegClass(ChildRec, &VT);
4253       if (!RC) {
4254         return failedImport(
4255           "Could not determine physical register class of pattern source");
4256       }
4257 
4258       OM.addPredicate<RegisterBankOperandMatcher>(*RC);
4259       return Error::success();
4260     }
4261 
4262     // Check for ValueType.
4263     if (ChildRec->isSubClassOf("ValueType")) {
4264       // We already added a type check as standard practice so this doesn't need
4265       // to do anything.
4266       return Error::success();
4267     }
4268 
4269     // Check for ComplexPattern's.
4270     if (ChildRec->isSubClassOf("ComplexPattern"))
4271       return importComplexPatternOperandMatcher(OM, ChildRec, TempOpIdx);
4272 
4273     if (ChildRec->isSubClassOf("ImmLeaf")) {
4274       return failedImport(
4275           "Src pattern child def is an unsupported tablegen class (ImmLeaf)");
4276     }
4277 
4278     // Place holder for SRCVALUE nodes. Nothing to do here.
4279     if (ChildRec->getName() == "srcvalue")
4280       return Error::success();
4281 
4282     const bool ImmAllOnesV = ChildRec->getName() == "immAllOnesV";
4283     if (ImmAllOnesV || ChildRec->getName() == "immAllZerosV") {
4284       auto MaybeInsnOperand = OM.addPredicate<InstructionOperandMatcher>(
4285           InsnMatcher.getRuleMatcher(), SrcChild->getName(), false);
4286       InstructionOperandMatcher &InsnOperand = **MaybeInsnOperand;
4287 
4288       ValueTypeByHwMode VTy = ChildTypes.front().getValueTypeByHwMode();
4289 
4290       const CodeGenInstruction &BuildVector
4291         = Target.getInstruction(RK.getDef("G_BUILD_VECTOR"));
4292       const CodeGenInstruction &BuildVectorTrunc
4293         = Target.getInstruction(RK.getDef("G_BUILD_VECTOR_TRUNC"));
4294 
4295       // Treat G_BUILD_VECTOR as the canonical opcode, and G_BUILD_VECTOR_TRUNC
4296       // as an alternative.
4297       InsnOperand.getInsnMatcher().addPredicate<InstructionOpcodeMatcher>(
4298       makeArrayRef({&BuildVector, &BuildVectorTrunc}));
4299 
4300       // TODO: Handle both G_BUILD_VECTOR and G_BUILD_VECTOR_TRUNC We could
4301       // theoretically not emit any opcode check, but getOpcodeMatcher currently
4302       // has to succeed.
4303       OperandMatcher &OM =
4304           InsnOperand.getInsnMatcher().addOperand(0, "", TempOpIdx);
4305       if (auto Error =
4306               OM.addTypeCheckPredicate(VTy, false /* OperandIsAPointer */))
4307         return failedImport(toString(std::move(Error)) +
4308                             " for result of Src pattern operator");
4309 
4310       InsnOperand.getInsnMatcher().addPredicate<VectorSplatImmPredicateMatcher>(
4311           ImmAllOnesV ? VectorSplatImmPredicateMatcher::AllOnes
4312                       : VectorSplatImmPredicateMatcher::AllZeros);
4313       return Error::success();
4314     }
4315 
4316     return failedImport(
4317         "Src pattern child def is an unsupported tablegen class");
4318   }
4319 
4320   return failedImport("Src pattern child is an unsupported kind");
4321 }
4322 
4323 Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderer(
4324     action_iterator InsertPt, RuleMatcher &Rule, BuildMIAction &DstMIBuilder,
4325     TreePatternNode *DstChild) {
4326 
4327   const auto &SubOperand = Rule.getComplexSubOperand(DstChild->getName());
4328   if (SubOperand.hasValue()) {
4329     DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
4330         *std::get<0>(*SubOperand), DstChild->getName(),
4331         std::get<1>(*SubOperand), std::get<2>(*SubOperand));
4332     return InsertPt;
4333   }
4334 
4335   if (!DstChild->isLeaf()) {
4336     if (DstChild->getOperator()->isSubClassOf("SDNodeXForm")) {
4337       auto Child = DstChild->getChild(0);
4338       auto I = SDNodeXFormEquivs.find(DstChild->getOperator());
4339       if (I != SDNodeXFormEquivs.end()) {
4340         Record *XFormOpc = DstChild->getOperator()->getValueAsDef("Opcode");
4341         if (XFormOpc->getName() == "timm") {
4342           // If this is a TargetConstant, there won't be a corresponding
4343           // instruction to transform. Instead, this will refer directly to an
4344           // operand in an instruction's operand list.
4345           DstMIBuilder.addRenderer<CustomOperandRenderer>(*I->second,
4346                                                           Child->getName());
4347         } else {
4348           DstMIBuilder.addRenderer<CustomRenderer>(*I->second,
4349                                                    Child->getName());
4350         }
4351 
4352         return InsertPt;
4353       }
4354       return failedImport("SDNodeXForm " + Child->getName() +
4355                           " has no custom renderer");
4356     }
4357 
4358     // We accept 'bb' here. It's an operator because BasicBlockSDNode isn't
4359     // inline, but in MI it's just another operand.
4360     if (DstChild->getOperator()->isSubClassOf("SDNode")) {
4361       auto &ChildSDNI = CGP.getSDNodeInfo(DstChild->getOperator());
4362       if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
4363         DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
4364         return InsertPt;
4365       }
4366     }
4367 
4368     // Similarly, imm is an operator in TreePatternNode's view but must be
4369     // rendered as operands.
4370     // FIXME: The target should be able to choose sign-extended when appropriate
4371     //        (e.g. on Mips).
4372     if (DstChild->getOperator()->getName() == "timm") {
4373       DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
4374       return InsertPt;
4375     } else if (DstChild->getOperator()->getName() == "imm") {
4376       DstMIBuilder.addRenderer<CopyConstantAsImmRenderer>(DstChild->getName());
4377       return InsertPt;
4378     } else if (DstChild->getOperator()->getName() == "fpimm") {
4379       DstMIBuilder.addRenderer<CopyFConstantAsFPImmRenderer>(
4380           DstChild->getName());
4381       return InsertPt;
4382     }
4383 
4384     if (DstChild->getOperator()->isSubClassOf("Instruction")) {
4385       auto OpTy = getInstResultType(DstChild);
4386       if (!OpTy)
4387         return OpTy.takeError();
4388 
4389       unsigned TempRegID = Rule.allocateTempRegID();
4390       InsertPt = Rule.insertAction<MakeTempRegisterAction>(
4391           InsertPt, *OpTy, TempRegID);
4392       DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
4393 
4394       auto InsertPtOrError = createAndImportSubInstructionRenderer(
4395           ++InsertPt, Rule, DstChild, TempRegID);
4396       if (auto Error = InsertPtOrError.takeError())
4397         return std::move(Error);
4398       return InsertPtOrError.get();
4399     }
4400 
4401     return failedImport("Dst pattern child isn't a leaf node or an MBB" + llvm::to_string(*DstChild));
4402   }
4403 
4404   // It could be a specific immediate in which case we should just check for
4405   // that immediate.
4406   if (const IntInit *ChildIntInit =
4407           dyn_cast<IntInit>(DstChild->getLeafValue())) {
4408     DstMIBuilder.addRenderer<ImmRenderer>(ChildIntInit->getValue());
4409     return InsertPt;
4410   }
4411 
4412   // Otherwise, we're looking for a bog-standard RegisterClass operand.
4413   if (auto *ChildDefInit = dyn_cast<DefInit>(DstChild->getLeafValue())) {
4414     auto *ChildRec = ChildDefInit->getDef();
4415 
4416     ArrayRef<TypeSetByHwMode> ChildTypes = DstChild->getExtTypes();
4417     if (ChildTypes.size() != 1)
4418       return failedImport("Dst pattern child has multiple results");
4419 
4420     Optional<LLTCodeGen> OpTyOrNone = None;
4421     if (ChildTypes.front().isMachineValueType())
4422       OpTyOrNone = MVTToLLT(ChildTypes.front().getMachineValueType().SimpleTy);
4423     if (!OpTyOrNone)
4424       return failedImport("Dst operand has an unsupported type");
4425 
4426     if (ChildRec->isSubClassOf("Register")) {
4427       DstMIBuilder.addRenderer<AddRegisterRenderer>(Target, ChildRec);
4428       return InsertPt;
4429     }
4430 
4431     if (ChildRec->isSubClassOf("RegisterClass") ||
4432         ChildRec->isSubClassOf("RegisterOperand") ||
4433         ChildRec->isSubClassOf("ValueType")) {
4434       if (ChildRec->isSubClassOf("RegisterOperand") &&
4435           !ChildRec->isValueUnset("GIZeroRegister")) {
4436         DstMIBuilder.addRenderer<CopyOrAddZeroRegRenderer>(
4437             DstChild->getName(), ChildRec->getValueAsDef("GIZeroRegister"));
4438         return InsertPt;
4439       }
4440 
4441       DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
4442       return InsertPt;
4443     }
4444 
4445     if (ChildRec->isSubClassOf("SubRegIndex")) {
4446       CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(ChildRec);
4447       DstMIBuilder.addRenderer<ImmRenderer>(SubIdx->EnumValue);
4448       return InsertPt;
4449     }
4450 
4451     if (ChildRec->isSubClassOf("ComplexPattern")) {
4452       const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
4453       if (ComplexPattern == ComplexPatternEquivs.end())
4454         return failedImport(
4455             "SelectionDAG ComplexPattern not mapped to GlobalISel");
4456 
4457       const OperandMatcher &OM = Rule.getOperandMatcher(DstChild->getName());
4458       DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
4459           *ComplexPattern->second, DstChild->getName(),
4460           OM.getAllocatedTemporariesBaseID());
4461       return InsertPt;
4462     }
4463 
4464     return failedImport(
4465         "Dst pattern child def is an unsupported tablegen class");
4466   }
4467 
4468   return failedImport("Dst pattern child is an unsupported kind");
4469 }
4470 
4471 Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
4472     RuleMatcher &M, InstructionMatcher &InsnMatcher, const TreePatternNode *Src,
4473     const TreePatternNode *Dst) {
4474   auto InsertPtOrError = createInstructionRenderer(M.actions_end(), M, Dst);
4475   if (auto Error = InsertPtOrError.takeError())
4476     return std::move(Error);
4477 
4478   action_iterator InsertPt = InsertPtOrError.get();
4479   BuildMIAction &DstMIBuilder = *static_cast<BuildMIAction *>(InsertPt->get());
4480 
4481   for (auto PhysInput : InsnMatcher.getPhysRegInputs()) {
4482     InsertPt = M.insertAction<BuildMIAction>(
4483         InsertPt, M.allocateOutputInsnID(),
4484         &Target.getInstruction(RK.getDef("COPY")));
4485     BuildMIAction &CopyToPhysRegMIBuilder =
4486         *static_cast<BuildMIAction *>(InsertPt->get());
4487     CopyToPhysRegMIBuilder.addRenderer<AddRegisterRenderer>(Target,
4488                                                             PhysInput.first,
4489                                                             true);
4490     CopyToPhysRegMIBuilder.addRenderer<CopyPhysRegRenderer>(PhysInput.first);
4491   }
4492 
4493   if (auto Error = importExplicitDefRenderers(InsertPt, M, DstMIBuilder, Dst)
4494                        .takeError())
4495     return std::move(Error);
4496 
4497   if (auto Error = importExplicitUseRenderers(InsertPt, M, DstMIBuilder, Dst)
4498                        .takeError())
4499     return std::move(Error);
4500 
4501   return DstMIBuilder;
4502 }
4503 
4504 Expected<action_iterator>
4505 GlobalISelEmitter::createAndImportSubInstructionRenderer(
4506     const action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst,
4507     unsigned TempRegID) {
4508   auto InsertPtOrError = createInstructionRenderer(InsertPt, M, Dst);
4509 
4510   // TODO: Assert there's exactly one result.
4511 
4512   if (auto Error = InsertPtOrError.takeError())
4513     return std::move(Error);
4514 
4515   BuildMIAction &DstMIBuilder =
4516       *static_cast<BuildMIAction *>(InsertPtOrError.get()->get());
4517 
4518   // Assign the result to TempReg.
4519   DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID, true);
4520 
4521   InsertPtOrError =
4522       importExplicitUseRenderers(InsertPtOrError.get(), M, DstMIBuilder, Dst);
4523   if (auto Error = InsertPtOrError.takeError())
4524     return std::move(Error);
4525 
4526   // We need to make sure that when we import an INSERT_SUBREG as a
4527   // subinstruction that it ends up being constrained to the correct super
4528   // register and subregister classes.
4529   auto OpName = Target.getInstruction(Dst->getOperator()).TheDef->getName();
4530   if (OpName == "INSERT_SUBREG") {
4531     auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
4532     if (!SubClass)
4533       return failedImport(
4534           "Cannot infer register class from INSERT_SUBREG operand #1");
4535     Optional<const CodeGenRegisterClass *> SuperClass =
4536         inferSuperRegisterClassForNode(Dst->getExtType(0), Dst->getChild(0),
4537                                        Dst->getChild(2));
4538     if (!SuperClass)
4539       return failedImport(
4540           "Cannot infer register class for INSERT_SUBREG operand #0");
4541     // The destination and the super register source of an INSERT_SUBREG must
4542     // be the same register class.
4543     M.insertAction<ConstrainOperandToRegClassAction>(
4544         InsertPt, DstMIBuilder.getInsnID(), 0, **SuperClass);
4545     M.insertAction<ConstrainOperandToRegClassAction>(
4546         InsertPt, DstMIBuilder.getInsnID(), 1, **SuperClass);
4547     M.insertAction<ConstrainOperandToRegClassAction>(
4548         InsertPt, DstMIBuilder.getInsnID(), 2, **SubClass);
4549     return InsertPtOrError.get();
4550   }
4551 
4552   if (OpName == "EXTRACT_SUBREG") {
4553     // EXTRACT_SUBREG selects into a subregister COPY but unlike most
4554     // instructions, the result register class is controlled by the
4555     // subregisters of the operand. As a result, we must constrain the result
4556     // class rather than check that it's already the right one.
4557     auto SuperClass = inferRegClassFromPattern(Dst->getChild(0));
4558     if (!SuperClass)
4559       return failedImport(
4560         "Cannot infer register class from EXTRACT_SUBREG operand #0");
4561 
4562     auto SubIdx = inferSubRegIndexForNode(Dst->getChild(1));
4563     if (!SubIdx)
4564       return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
4565 
4566     const auto SrcRCDstRCPair =
4567       (*SuperClass)->getMatchingSubClassWithSubRegs(CGRegs, *SubIdx);
4568     assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
4569     M.insertAction<ConstrainOperandToRegClassAction>(
4570       InsertPt, DstMIBuilder.getInsnID(), 0, *SrcRCDstRCPair->second);
4571     M.insertAction<ConstrainOperandToRegClassAction>(
4572       InsertPt, DstMIBuilder.getInsnID(), 1, *SrcRCDstRCPair->first);
4573 
4574     // We're done with this pattern!  It's eligible for GISel emission; return
4575     // it.
4576     return InsertPtOrError.get();
4577   }
4578 
4579   // Similar to INSERT_SUBREG, we also have to handle SUBREG_TO_REG as a
4580   // subinstruction.
4581   if (OpName == "SUBREG_TO_REG") {
4582     auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
4583     if (!SubClass)
4584       return failedImport(
4585         "Cannot infer register class from SUBREG_TO_REG child #1");
4586     auto SuperClass = inferSuperRegisterClass(Dst->getExtType(0),
4587                                               Dst->getChild(2));
4588     if (!SuperClass)
4589       return failedImport(
4590         "Cannot infer register class for SUBREG_TO_REG operand #0");
4591     M.insertAction<ConstrainOperandToRegClassAction>(
4592       InsertPt, DstMIBuilder.getInsnID(), 0, **SuperClass);
4593     M.insertAction<ConstrainOperandToRegClassAction>(
4594       InsertPt, DstMIBuilder.getInsnID(), 2, **SubClass);
4595     return InsertPtOrError.get();
4596   }
4597 
4598   if (OpName == "REG_SEQUENCE") {
4599     auto SuperClass = inferRegClassFromPattern(Dst->getChild(0));
4600     M.insertAction<ConstrainOperandToRegClassAction>(
4601       InsertPt, DstMIBuilder.getInsnID(), 0, **SuperClass);
4602 
4603     unsigned Num = Dst->getNumChildren();
4604     for (unsigned I = 1; I != Num; I += 2) {
4605       TreePatternNode *SubRegChild = Dst->getChild(I + 1);
4606 
4607       auto SubIdx = inferSubRegIndexForNode(SubRegChild);
4608       if (!SubIdx)
4609         return failedImport("REG_SEQUENCE child is not a subreg index");
4610 
4611       const auto SrcRCDstRCPair =
4612         (*SuperClass)->getMatchingSubClassWithSubRegs(CGRegs, *SubIdx);
4613       assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
4614       M.insertAction<ConstrainOperandToRegClassAction>(
4615         InsertPt, DstMIBuilder.getInsnID(), I, *SrcRCDstRCPair->second);
4616     }
4617 
4618     return InsertPtOrError.get();
4619   }
4620 
4621   M.insertAction<ConstrainOperandsToDefinitionAction>(InsertPt,
4622                                                       DstMIBuilder.getInsnID());
4623   return InsertPtOrError.get();
4624 }
4625 
4626 Expected<action_iterator> GlobalISelEmitter::createInstructionRenderer(
4627     action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst) {
4628   Record *DstOp = Dst->getOperator();
4629   if (!DstOp->isSubClassOf("Instruction")) {
4630     if (DstOp->isSubClassOf("ValueType"))
4631       return failedImport(
4632           "Pattern operator isn't an instruction (it's a ValueType)");
4633     return failedImport("Pattern operator isn't an instruction");
4634   }
4635   CodeGenInstruction *DstI = &Target.getInstruction(DstOp);
4636 
4637   // COPY_TO_REGCLASS is just a copy with a ConstrainOperandToRegClassAction
4638   // attached. Similarly for EXTRACT_SUBREG except that's a subregister copy.
4639   StringRef Name = DstI->TheDef->getName();
4640   if (Name == "COPY_TO_REGCLASS" || Name == "EXTRACT_SUBREG")
4641     DstI = &Target.getInstruction(RK.getDef("COPY"));
4642 
4643   return M.insertAction<BuildMIAction>(InsertPt, M.allocateOutputInsnID(),
4644                                        DstI);
4645 }
4646 
4647 Expected<action_iterator> GlobalISelEmitter::importExplicitDefRenderers(
4648     action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
4649     const TreePatternNode *Dst) {
4650   const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
4651   const unsigned NumDefs = DstI->Operands.NumDefs;
4652   if (NumDefs == 0)
4653     return InsertPt;
4654 
4655   DstMIBuilder.addRenderer<CopyRenderer>(DstI->Operands[0].Name);
4656 
4657   // Some instructions have multiple defs, but are missing a type entry
4658   // (e.g. s_cc_out operands).
4659   if (Dst->getExtTypes().size() < NumDefs)
4660     return failedImport("unhandled discarded def");
4661 
4662   // Patterns only handle a single result, so any result after the first is an
4663   // implicitly dead def.
4664   for (unsigned I = 1; I < NumDefs; ++I) {
4665     const TypeSetByHwMode &ExtTy = Dst->getExtType(I);
4666     if (!ExtTy.isMachineValueType())
4667       return failedImport("unsupported typeset");
4668 
4669     auto OpTy = MVTToLLT(ExtTy.getMachineValueType().SimpleTy);
4670     if (!OpTy)
4671       return failedImport("unsupported type");
4672 
4673     unsigned TempRegID = M.allocateTempRegID();
4674     InsertPt =
4675       M.insertAction<MakeTempRegisterAction>(InsertPt, *OpTy, TempRegID);
4676     DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID, true, nullptr, true);
4677   }
4678 
4679   return InsertPt;
4680 }
4681 
4682 Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderers(
4683     action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
4684     const llvm::TreePatternNode *Dst) {
4685   const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
4686   CodeGenInstruction *OrigDstI = &Target.getInstruction(Dst->getOperator());
4687 
4688   StringRef Name = OrigDstI->TheDef->getName();
4689   unsigned ExpectedDstINumUses = Dst->getNumChildren();
4690 
4691   // EXTRACT_SUBREG needs to use a subregister COPY.
4692   if (Name == "EXTRACT_SUBREG") {
4693     if (!Dst->getChild(1)->isLeaf())
4694       return failedImport("EXTRACT_SUBREG child #1 is not a leaf");
4695     DefInit *SubRegInit = dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue());
4696     if (!SubRegInit)
4697       return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
4698 
4699     CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
4700     TreePatternNode *ValChild = Dst->getChild(0);
4701     if (!ValChild->isLeaf()) {
4702       // We really have to handle the source instruction, and then insert a
4703       // copy from the subregister.
4704       auto ExtractSrcTy = getInstResultType(ValChild);
4705       if (!ExtractSrcTy)
4706         return ExtractSrcTy.takeError();
4707 
4708       unsigned TempRegID = M.allocateTempRegID();
4709       InsertPt = M.insertAction<MakeTempRegisterAction>(
4710         InsertPt, *ExtractSrcTy, TempRegID);
4711 
4712       auto InsertPtOrError = createAndImportSubInstructionRenderer(
4713         ++InsertPt, M, ValChild, TempRegID);
4714       if (auto Error = InsertPtOrError.takeError())
4715         return std::move(Error);
4716 
4717       DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID, false, SubIdx);
4718       return InsertPt;
4719     }
4720 
4721     // If this is a source operand, this is just a subregister copy.
4722     Record *RCDef = getInitValueAsRegClass(ValChild->getLeafValue());
4723     if (!RCDef)
4724       return failedImport("EXTRACT_SUBREG child #0 could not "
4725                           "be coerced to a register class");
4726 
4727     CodeGenRegisterClass *RC = CGRegs.getRegClass(RCDef);
4728 
4729     const auto SrcRCDstRCPair =
4730       RC->getMatchingSubClassWithSubRegs(CGRegs, SubIdx);
4731     if (SrcRCDstRCPair.hasValue()) {
4732       assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
4733       if (SrcRCDstRCPair->first != RC)
4734         return failedImport("EXTRACT_SUBREG requires an additional COPY");
4735     }
4736 
4737     DstMIBuilder.addRenderer<CopySubRegRenderer>(Dst->getChild(0)->getName(),
4738                                                  SubIdx);
4739     return InsertPt;
4740   }
4741 
4742   if (Name == "REG_SEQUENCE") {
4743     if (!Dst->getChild(0)->isLeaf())
4744       return failedImport("REG_SEQUENCE child #0 is not a leaf");
4745 
4746     Record *RCDef = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
4747     if (!RCDef)
4748       return failedImport("REG_SEQUENCE child #0 could not "
4749                           "be coerced to a register class");
4750 
4751     if ((ExpectedDstINumUses - 1) % 2 != 0)
4752       return failedImport("Malformed REG_SEQUENCE");
4753 
4754     for (unsigned I = 1; I != ExpectedDstINumUses; I += 2) {
4755       TreePatternNode *ValChild = Dst->getChild(I);
4756       TreePatternNode *SubRegChild = Dst->getChild(I + 1);
4757 
4758       if (DefInit *SubRegInit =
4759               dyn_cast<DefInit>(SubRegChild->getLeafValue())) {
4760         CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
4761 
4762         auto InsertPtOrError =
4763             importExplicitUseRenderer(InsertPt, M, DstMIBuilder, ValChild);
4764         if (auto Error = InsertPtOrError.takeError())
4765           return std::move(Error);
4766         InsertPt = InsertPtOrError.get();
4767         DstMIBuilder.addRenderer<SubRegIndexRenderer>(SubIdx);
4768       }
4769     }
4770 
4771     return InsertPt;
4772   }
4773 
4774   // Render the explicit uses.
4775   unsigned DstINumUses = OrigDstI->Operands.size() - OrigDstI->Operands.NumDefs;
4776   if (Name == "COPY_TO_REGCLASS") {
4777     DstINumUses--; // Ignore the class constraint.
4778     ExpectedDstINumUses--;
4779   }
4780 
4781   // NumResults - This is the number of results produced by the instruction in
4782   // the "outs" list.
4783   unsigned NumResults = OrigDstI->Operands.NumDefs;
4784 
4785   // Number of operands we know the output instruction must have. If it is
4786   // variadic, we could have more operands.
4787   unsigned NumFixedOperands = DstI->Operands.size();
4788 
4789   // Loop over all of the fixed operands of the instruction pattern, emitting
4790   // code to fill them all in. The node 'N' usually has number children equal to
4791   // the number of input operands of the instruction.  However, in cases where
4792   // there are predicate operands for an instruction, we need to fill in the
4793   // 'execute always' values. Match up the node operands to the instruction
4794   // operands to do this.
4795   unsigned Child = 0;
4796 
4797   // Similarly to the code in TreePatternNode::ApplyTypeConstraints, count the
4798   // number of operands at the end of the list which have default values.
4799   // Those can come from the pattern if it provides enough arguments, or be
4800   // filled in with the default if the pattern hasn't provided them. But any
4801   // operand with a default value _before_ the last mandatory one will be
4802   // filled in with their defaults unconditionally.
4803   unsigned NonOverridableOperands = NumFixedOperands;
4804   while (NonOverridableOperands > NumResults &&
4805          CGP.operandHasDefault(DstI->Operands[NonOverridableOperands - 1].Rec))
4806     --NonOverridableOperands;
4807 
4808   unsigned NumDefaultOps = 0;
4809   for (unsigned I = 0; I != DstINumUses; ++I) {
4810     unsigned InstOpNo = DstI->Operands.NumDefs + I;
4811 
4812     // Determine what to emit for this operand.
4813     Record *OperandNode = DstI->Operands[InstOpNo].Rec;
4814 
4815     // If the operand has default values, introduce them now.
4816     if (CGP.operandHasDefault(OperandNode) &&
4817         (InstOpNo < NonOverridableOperands || Child >= Dst->getNumChildren())) {
4818       // This is a predicate or optional def operand which the pattern has not
4819       // overridden, or which we aren't letting it override; emit the 'default
4820       // ops' operands.
4821 
4822       const CGIOperandList::OperandInfo &DstIOperand = DstI->Operands[InstOpNo];
4823       DagInit *DefaultOps = DstIOperand.Rec->getValueAsDag("DefaultOps");
4824       if (auto Error = importDefaultOperandRenderers(
4825             InsertPt, M, DstMIBuilder, DefaultOps))
4826         return std::move(Error);
4827       ++NumDefaultOps;
4828       continue;
4829     }
4830 
4831     auto InsertPtOrError = importExplicitUseRenderer(InsertPt, M, DstMIBuilder,
4832                                                      Dst->getChild(Child));
4833     if (auto Error = InsertPtOrError.takeError())
4834       return std::move(Error);
4835     InsertPt = InsertPtOrError.get();
4836     ++Child;
4837   }
4838 
4839   if (NumDefaultOps + ExpectedDstINumUses != DstINumUses)
4840     return failedImport("Expected " + llvm::to_string(DstINumUses) +
4841                         " used operands but found " +
4842                         llvm::to_string(ExpectedDstINumUses) +
4843                         " explicit ones and " + llvm::to_string(NumDefaultOps) +
4844                         " default ones");
4845 
4846   return InsertPt;
4847 }
4848 
4849 Error GlobalISelEmitter::importDefaultOperandRenderers(
4850     action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
4851     DagInit *DefaultOps) const {
4852   for (const auto *DefaultOp : DefaultOps->getArgs()) {
4853     Optional<LLTCodeGen> OpTyOrNone = None;
4854 
4855     // Look through ValueType operators.
4856     if (const DagInit *DefaultDagOp = dyn_cast<DagInit>(DefaultOp)) {
4857       if (const DefInit *DefaultDagOperator =
4858               dyn_cast<DefInit>(DefaultDagOp->getOperator())) {
4859         if (DefaultDagOperator->getDef()->isSubClassOf("ValueType")) {
4860           OpTyOrNone = MVTToLLT(getValueType(
4861                                   DefaultDagOperator->getDef()));
4862           DefaultOp = DefaultDagOp->getArg(0);
4863         }
4864       }
4865     }
4866 
4867     if (const DefInit *DefaultDefOp = dyn_cast<DefInit>(DefaultOp)) {
4868       auto Def = DefaultDefOp->getDef();
4869       if (Def->getName() == "undef_tied_input") {
4870         unsigned TempRegID = M.allocateTempRegID();
4871         M.insertAction<MakeTempRegisterAction>(
4872           InsertPt, OpTyOrNone.getValue(), TempRegID);
4873         InsertPt = M.insertAction<BuildMIAction>(
4874           InsertPt, M.allocateOutputInsnID(),
4875           &Target.getInstruction(RK.getDef("IMPLICIT_DEF")));
4876         BuildMIAction &IDMIBuilder = *static_cast<BuildMIAction *>(
4877           InsertPt->get());
4878         IDMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
4879         DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
4880       } else {
4881         DstMIBuilder.addRenderer<AddRegisterRenderer>(Target, Def);
4882       }
4883       continue;
4884     }
4885 
4886     if (const IntInit *DefaultIntOp = dyn_cast<IntInit>(DefaultOp)) {
4887       DstMIBuilder.addRenderer<ImmRenderer>(DefaultIntOp->getValue());
4888       continue;
4889     }
4890 
4891     return failedImport("Could not add default op");
4892   }
4893 
4894   return Error::success();
4895 }
4896 
4897 Error GlobalISelEmitter::importImplicitDefRenderers(
4898     BuildMIAction &DstMIBuilder,
4899     const std::vector<Record *> &ImplicitDefs) const {
4900   if (!ImplicitDefs.empty())
4901     return failedImport("Pattern defines a physical register");
4902   return Error::success();
4903 }
4904 
4905 Optional<const CodeGenRegisterClass *>
4906 GlobalISelEmitter::getRegClassFromLeaf(TreePatternNode *Leaf) {
4907   assert(Leaf && "Expected node?");
4908   assert(Leaf->isLeaf() && "Expected leaf?");
4909   Record *RCRec = getInitValueAsRegClass(Leaf->getLeafValue());
4910   if (!RCRec)
4911     return None;
4912   CodeGenRegisterClass *RC = CGRegs.getRegClass(RCRec);
4913   if (!RC)
4914     return None;
4915   return RC;
4916 }
4917 
4918 Optional<const CodeGenRegisterClass *>
4919 GlobalISelEmitter::inferRegClassFromPattern(TreePatternNode *N) {
4920   if (!N)
4921     return None;
4922 
4923   if (N->isLeaf())
4924     return getRegClassFromLeaf(N);
4925 
4926   // We don't have a leaf node, so we have to try and infer something. Check
4927   // that we have an instruction that we an infer something from.
4928 
4929   // Only handle things that produce a single type.
4930   if (N->getNumTypes() != 1)
4931     return None;
4932   Record *OpRec = N->getOperator();
4933 
4934   // We only want instructions.
4935   if (!OpRec->isSubClassOf("Instruction"))
4936     return None;
4937 
4938   // Don't want to try and infer things when there could potentially be more
4939   // than one candidate register class.
4940   auto &Inst = Target.getInstruction(OpRec);
4941   if (Inst.Operands.NumDefs > 1)
4942     return None;
4943 
4944   // Handle any special-case instructions which we can safely infer register
4945   // classes from.
4946   StringRef InstName = Inst.TheDef->getName();
4947   bool IsRegSequence = InstName == "REG_SEQUENCE";
4948   if (IsRegSequence || InstName == "COPY_TO_REGCLASS") {
4949     // If we have a COPY_TO_REGCLASS, then we need to handle it specially. It
4950     // has the desired register class as the first child.
4951     TreePatternNode *RCChild = N->getChild(IsRegSequence ? 0 : 1);
4952     if (!RCChild->isLeaf())
4953       return None;
4954     return getRegClassFromLeaf(RCChild);
4955   }
4956   if (InstName == "INSERT_SUBREG") {
4957     TreePatternNode *Child0 = N->getChild(0);
4958     assert(Child0->getNumTypes() == 1 && "Unexpected number of types!");
4959     const TypeSetByHwMode &VTy = Child0->getExtType(0);
4960     return inferSuperRegisterClassForNode(VTy, Child0, N->getChild(2));
4961   }
4962   if (InstName == "EXTRACT_SUBREG") {
4963     assert(N->getNumTypes() == 1 && "Unexpected number of types!");
4964     const TypeSetByHwMode &VTy = N->getExtType(0);
4965     return inferSuperRegisterClass(VTy, N->getChild(1));
4966   }
4967 
4968   // Handle destination record types that we can safely infer a register class
4969   // from.
4970   const auto &DstIOperand = Inst.Operands[0];
4971   Record *DstIOpRec = DstIOperand.Rec;
4972   if (DstIOpRec->isSubClassOf("RegisterOperand")) {
4973     DstIOpRec = DstIOpRec->getValueAsDef("RegClass");
4974     const CodeGenRegisterClass &RC = Target.getRegisterClass(DstIOpRec);
4975     return &RC;
4976   }
4977 
4978   if (DstIOpRec->isSubClassOf("RegisterClass")) {
4979     const CodeGenRegisterClass &RC = Target.getRegisterClass(DstIOpRec);
4980     return &RC;
4981   }
4982 
4983   return None;
4984 }
4985 
4986 Optional<const CodeGenRegisterClass *>
4987 GlobalISelEmitter::inferSuperRegisterClass(const TypeSetByHwMode &Ty,
4988                                            TreePatternNode *SubRegIdxNode) {
4989   assert(SubRegIdxNode && "Expected subregister index node!");
4990   // We need a ValueTypeByHwMode for getSuperRegForSubReg.
4991   if (!Ty.isValueTypeByHwMode(false))
4992     return None;
4993   if (!SubRegIdxNode->isLeaf())
4994     return None;
4995   DefInit *SubRegInit = dyn_cast<DefInit>(SubRegIdxNode->getLeafValue());
4996   if (!SubRegInit)
4997     return None;
4998   CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
4999 
5000   // Use the information we found above to find a minimal register class which
5001   // supports the subregister and type we want.
5002   auto RC =
5003       Target.getSuperRegForSubReg(Ty.getValueTypeByHwMode(), CGRegs, SubIdx,
5004                                   /* MustBeAllocatable */ true);
5005   if (!RC)
5006     return None;
5007   return *RC;
5008 }
5009 
5010 Optional<const CodeGenRegisterClass *>
5011 GlobalISelEmitter::inferSuperRegisterClassForNode(
5012     const TypeSetByHwMode &Ty, TreePatternNode *SuperRegNode,
5013     TreePatternNode *SubRegIdxNode) {
5014   assert(SuperRegNode && "Expected super register node!");
5015   // Check if we already have a defined register class for the super register
5016   // node. If we do, then we should preserve that rather than inferring anything
5017   // from the subregister index node. We can assume that whoever wrote the
5018   // pattern in the first place made sure that the super register and
5019   // subregister are compatible.
5020   if (Optional<const CodeGenRegisterClass *> SuperRegisterClass =
5021           inferRegClassFromPattern(SuperRegNode))
5022     return *SuperRegisterClass;
5023   return inferSuperRegisterClass(Ty, SubRegIdxNode);
5024 }
5025 
5026 Optional<CodeGenSubRegIndex *>
5027 GlobalISelEmitter::inferSubRegIndexForNode(TreePatternNode *SubRegIdxNode) {
5028   if (!SubRegIdxNode->isLeaf())
5029     return None;
5030 
5031   DefInit *SubRegInit = dyn_cast<DefInit>(SubRegIdxNode->getLeafValue());
5032   if (!SubRegInit)
5033     return None;
5034   return CGRegs.getSubRegIdx(SubRegInit->getDef());
5035 }
5036 
5037 Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
5038   // Keep track of the matchers and actions to emit.
5039   int Score = P.getPatternComplexity(CGP);
5040   RuleMatcher M(P.getSrcRecord()->getLoc());
5041   RuleMatcherScores[M.getRuleID()] = Score;
5042   M.addAction<DebugCommentAction>(llvm::to_string(*P.getSrcPattern()) +
5043                                   "  =>  " +
5044                                   llvm::to_string(*P.getDstPattern()));
5045 
5046   if (auto Error = importRulePredicates(M, P.getPredicates()))
5047     return std::move(Error);
5048 
5049   // Next, analyze the pattern operators.
5050   TreePatternNode *Src = P.getSrcPattern();
5051   TreePatternNode *Dst = P.getDstPattern();
5052 
5053   // If the root of either pattern isn't a simple operator, ignore it.
5054   if (auto Err = isTrivialOperatorNode(Dst))
5055     return failedImport("Dst pattern root isn't a trivial operator (" +
5056                         toString(std::move(Err)) + ")");
5057   if (auto Err = isTrivialOperatorNode(Src))
5058     return failedImport("Src pattern root isn't a trivial operator (" +
5059                         toString(std::move(Err)) + ")");
5060 
5061   // The different predicates and matchers created during
5062   // addInstructionMatcher use the RuleMatcher M to set up their
5063   // instruction ID (InsnVarID) that are going to be used when
5064   // M is going to be emitted.
5065   // However, the code doing the emission still relies on the IDs
5066   // returned during that process by the RuleMatcher when issuing
5067   // the recordInsn opcodes.
5068   // Because of that:
5069   // 1. The order in which we created the predicates
5070   //    and such must be the same as the order in which we emit them,
5071   //    and
5072   // 2. We need to reset the generation of the IDs in M somewhere between
5073   //    addInstructionMatcher and emit
5074   //
5075   // FIXME: Long term, we don't want to have to rely on this implicit
5076   // naming being the same. One possible solution would be to have
5077   // explicit operator for operation capture and reference those.
5078   // The plus side is that it would expose opportunities to share
5079   // the capture accross rules. The downside is that it would
5080   // introduce a dependency between predicates (captures must happen
5081   // before their first use.)
5082   InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher(Src->getName());
5083   unsigned TempOpIdx = 0;
5084   auto InsnMatcherOrError =
5085       createAndImportSelDAGMatcher(M, InsnMatcherTemp, Src, TempOpIdx);
5086   if (auto Error = InsnMatcherOrError.takeError())
5087     return std::move(Error);
5088   InstructionMatcher &InsnMatcher = InsnMatcherOrError.get();
5089 
5090   if (Dst->isLeaf()) {
5091     Record *RCDef = getInitValueAsRegClass(Dst->getLeafValue());
5092     if (RCDef) {
5093       const CodeGenRegisterClass &RC = Target.getRegisterClass(RCDef);
5094 
5095       // We need to replace the def and all its uses with the specified
5096       // operand. However, we must also insert COPY's wherever needed.
5097       // For now, emit a copy and let the register allocator clean up.
5098       auto &DstI = Target.getInstruction(RK.getDef("COPY"));
5099       const auto &DstIOperand = DstI.Operands[0];
5100 
5101       OperandMatcher &OM0 = InsnMatcher.getOperand(0);
5102       OM0.setSymbolicName(DstIOperand.Name);
5103       M.defineOperand(OM0.getSymbolicName(), OM0);
5104       OM0.addPredicate<RegisterBankOperandMatcher>(RC);
5105 
5106       auto &DstMIBuilder =
5107           M.addAction<BuildMIAction>(M.allocateOutputInsnID(), &DstI);
5108       DstMIBuilder.addRenderer<CopyRenderer>(DstIOperand.Name);
5109       DstMIBuilder.addRenderer<CopyRenderer>(Dst->getName());
5110       M.addAction<ConstrainOperandToRegClassAction>(0, 0, RC);
5111 
5112       // We're done with this pattern!  It's eligible for GISel emission; return
5113       // it.
5114       ++NumPatternImported;
5115       return std::move(M);
5116     }
5117 
5118     return failedImport("Dst pattern root isn't a known leaf");
5119   }
5120 
5121   // Start with the defined operands (i.e., the results of the root operator).
5122   Record *DstOp = Dst->getOperator();
5123   if (!DstOp->isSubClassOf("Instruction"))
5124     return failedImport("Pattern operator isn't an instruction");
5125 
5126   auto &DstI = Target.getInstruction(DstOp);
5127   StringRef DstIName = DstI.TheDef->getName();
5128 
5129   if (DstI.Operands.NumDefs < Src->getExtTypes().size())
5130     return failedImport("Src pattern result has more defs than dst MI (" +
5131                         to_string(Src->getExtTypes().size()) + " def(s) vs " +
5132                         to_string(DstI.Operands.NumDefs) + " def(s))");
5133 
5134   // The root of the match also has constraints on the register bank so that it
5135   // matches the result instruction.
5136   unsigned OpIdx = 0;
5137   for (const TypeSetByHwMode &VTy : Src->getExtTypes()) {
5138     (void)VTy;
5139 
5140     const auto &DstIOperand = DstI.Operands[OpIdx];
5141     Record *DstIOpRec = DstIOperand.Rec;
5142     if (DstIName == "COPY_TO_REGCLASS") {
5143       DstIOpRec = getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());
5144 
5145       if (DstIOpRec == nullptr)
5146         return failedImport(
5147             "COPY_TO_REGCLASS operand #1 isn't a register class");
5148     } else if (DstIName == "REG_SEQUENCE") {
5149       DstIOpRec = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
5150       if (DstIOpRec == nullptr)
5151         return failedImport("REG_SEQUENCE operand #0 isn't a register class");
5152     } else if (DstIName == "EXTRACT_SUBREG") {
5153       auto InferredClass = inferRegClassFromPattern(Dst->getChild(0));
5154       if (!InferredClass)
5155         return failedImport("Could not infer class for EXTRACT_SUBREG operand #0");
5156 
5157       // We can assume that a subregister is in the same bank as it's super
5158       // register.
5159       DstIOpRec = (*InferredClass)->getDef();
5160     } else if (DstIName == "INSERT_SUBREG") {
5161       auto MaybeSuperClass = inferSuperRegisterClassForNode(
5162           VTy, Dst->getChild(0), Dst->getChild(2));
5163       if (!MaybeSuperClass)
5164         return failedImport(
5165             "Cannot infer register class for INSERT_SUBREG operand #0");
5166       // Move to the next pattern here, because the register class we found
5167       // doesn't necessarily have a record associated with it. So, we can't
5168       // set DstIOpRec using this.
5169       OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
5170       OM.setSymbolicName(DstIOperand.Name);
5171       M.defineOperand(OM.getSymbolicName(), OM);
5172       OM.addPredicate<RegisterBankOperandMatcher>(**MaybeSuperClass);
5173       ++OpIdx;
5174       continue;
5175     } else if (DstIName == "SUBREG_TO_REG") {
5176       auto MaybeRegClass = inferSuperRegisterClass(VTy, Dst->getChild(2));
5177       if (!MaybeRegClass)
5178         return failedImport(
5179             "Cannot infer register class for SUBREG_TO_REG operand #0");
5180       OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
5181       OM.setSymbolicName(DstIOperand.Name);
5182       M.defineOperand(OM.getSymbolicName(), OM);
5183       OM.addPredicate<RegisterBankOperandMatcher>(**MaybeRegClass);
5184       ++OpIdx;
5185       continue;
5186     } else if (DstIOpRec->isSubClassOf("RegisterOperand"))
5187       DstIOpRec = DstIOpRec->getValueAsDef("RegClass");
5188     else if (!DstIOpRec->isSubClassOf("RegisterClass"))
5189       return failedImport("Dst MI def isn't a register class" +
5190                           to_string(*Dst));
5191 
5192     OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
5193     OM.setSymbolicName(DstIOperand.Name);
5194     M.defineOperand(OM.getSymbolicName(), OM);
5195     OM.addPredicate<RegisterBankOperandMatcher>(
5196         Target.getRegisterClass(DstIOpRec));
5197     ++OpIdx;
5198   }
5199 
5200   auto DstMIBuilderOrError =
5201       createAndImportInstructionRenderer(M, InsnMatcher, Src, Dst);
5202   if (auto Error = DstMIBuilderOrError.takeError())
5203     return std::move(Error);
5204   BuildMIAction &DstMIBuilder = DstMIBuilderOrError.get();
5205 
5206   // Render the implicit defs.
5207   // These are only added to the root of the result.
5208   if (auto Error = importImplicitDefRenderers(DstMIBuilder, P.getDstRegs()))
5209     return std::move(Error);
5210 
5211   DstMIBuilder.chooseInsnToMutate(M);
5212 
5213   // Constrain the registers to classes. This is normally derived from the
5214   // emitted instruction but a few instructions require special handling.
5215   if (DstIName == "COPY_TO_REGCLASS") {
5216     // COPY_TO_REGCLASS does not provide operand constraints itself but the
5217     // result is constrained to the class given by the second child.
5218     Record *DstIOpRec =
5219         getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());
5220 
5221     if (DstIOpRec == nullptr)
5222       return failedImport("COPY_TO_REGCLASS operand #1 isn't a register class");
5223 
5224     M.addAction<ConstrainOperandToRegClassAction>(
5225         0, 0, Target.getRegisterClass(DstIOpRec));
5226 
5227     // We're done with this pattern!  It's eligible for GISel emission; return
5228     // it.
5229     ++NumPatternImported;
5230     return std::move(M);
5231   }
5232 
5233   if (DstIName == "EXTRACT_SUBREG") {
5234     auto SuperClass = inferRegClassFromPattern(Dst->getChild(0));
5235     if (!SuperClass)
5236       return failedImport(
5237         "Cannot infer register class from EXTRACT_SUBREG operand #0");
5238 
5239     auto SubIdx = inferSubRegIndexForNode(Dst->getChild(1));
5240     if (!SubIdx)
5241       return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
5242 
5243     // It would be nice to leave this constraint implicit but we're required
5244     // to pick a register class so constrain the result to a register class
5245     // that can hold the correct MVT.
5246     //
5247     // FIXME: This may introduce an extra copy if the chosen class doesn't
5248     //        actually contain the subregisters.
5249     assert(Src->getExtTypes().size() == 1 &&
5250              "Expected Src of EXTRACT_SUBREG to have one result type");
5251 
5252     const auto SrcRCDstRCPair =
5253       (*SuperClass)->getMatchingSubClassWithSubRegs(CGRegs, *SubIdx);
5254     if (!SrcRCDstRCPair) {
5255       return failedImport("subreg index is incompatible "
5256                           "with inferred reg class");
5257     }
5258 
5259     assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
5260     M.addAction<ConstrainOperandToRegClassAction>(0, 0, *SrcRCDstRCPair->second);
5261     M.addAction<ConstrainOperandToRegClassAction>(0, 1, *SrcRCDstRCPair->first);
5262 
5263     // We're done with this pattern!  It's eligible for GISel emission; return
5264     // it.
5265     ++NumPatternImported;
5266     return std::move(M);
5267   }
5268 
5269   if (DstIName == "INSERT_SUBREG") {
5270     assert(Src->getExtTypes().size() == 1 &&
5271            "Expected Src of INSERT_SUBREG to have one result type");
5272     // We need to constrain the destination, a super regsister source, and a
5273     // subregister source.
5274     auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
5275     if (!SubClass)
5276       return failedImport(
5277           "Cannot infer register class from INSERT_SUBREG operand #1");
5278     auto SuperClass = inferSuperRegisterClassForNode(
5279         Src->getExtType(0), Dst->getChild(0), Dst->getChild(2));
5280     if (!SuperClass)
5281       return failedImport(
5282           "Cannot infer register class for INSERT_SUBREG operand #0");
5283     M.addAction<ConstrainOperandToRegClassAction>(0, 0, **SuperClass);
5284     M.addAction<ConstrainOperandToRegClassAction>(0, 1, **SuperClass);
5285     M.addAction<ConstrainOperandToRegClassAction>(0, 2, **SubClass);
5286     ++NumPatternImported;
5287     return std::move(M);
5288   }
5289 
5290   if (DstIName == "SUBREG_TO_REG") {
5291     // We need to constrain the destination and subregister source.
5292     assert(Src->getExtTypes().size() == 1 &&
5293            "Expected Src of SUBREG_TO_REG to have one result type");
5294 
5295     // Attempt to infer the subregister source from the first child. If it has
5296     // an explicitly given register class, we'll use that. Otherwise, we will
5297     // fail.
5298     auto SubClass = inferRegClassFromPattern(Dst->getChild(1));
5299     if (!SubClass)
5300       return failedImport(
5301           "Cannot infer register class from SUBREG_TO_REG child #1");
5302     // We don't have a child to look at that might have a super register node.
5303     auto SuperClass =
5304         inferSuperRegisterClass(Src->getExtType(0), Dst->getChild(2));
5305     if (!SuperClass)
5306       return failedImport(
5307           "Cannot infer register class for SUBREG_TO_REG operand #0");
5308     M.addAction<ConstrainOperandToRegClassAction>(0, 0, **SuperClass);
5309     M.addAction<ConstrainOperandToRegClassAction>(0, 2, **SubClass);
5310     ++NumPatternImported;
5311     return std::move(M);
5312   }
5313 
5314   if (DstIName == "REG_SEQUENCE") {
5315     auto SuperClass = inferRegClassFromPattern(Dst->getChild(0));
5316 
5317     M.addAction<ConstrainOperandToRegClassAction>(0, 0, **SuperClass);
5318 
5319     unsigned Num = Dst->getNumChildren();
5320     for (unsigned I = 1; I != Num; I += 2) {
5321       TreePatternNode *SubRegChild = Dst->getChild(I + 1);
5322 
5323       auto SubIdx = inferSubRegIndexForNode(SubRegChild);
5324       if (!SubIdx)
5325         return failedImport("REG_SEQUENCE child is not a subreg index");
5326 
5327       const auto SrcRCDstRCPair =
5328         (*SuperClass)->getMatchingSubClassWithSubRegs(CGRegs, *SubIdx);
5329 
5330       M.addAction<ConstrainOperandToRegClassAction>(0, I,
5331                                                     *SrcRCDstRCPair->second);
5332     }
5333 
5334     ++NumPatternImported;
5335     return std::move(M);
5336   }
5337 
5338   M.addAction<ConstrainOperandsToDefinitionAction>(0);
5339 
5340   // We're done with this pattern!  It's eligible for GISel emission; return it.
5341   ++NumPatternImported;
5342   return std::move(M);
5343 }
5344 
5345 // Emit imm predicate table and an enum to reference them with.
5346 // The 'Predicate_' part of the name is redundant but eliminating it is more
5347 // trouble than it's worth.
5348 void GlobalISelEmitter::emitCxxPredicateFns(
5349     raw_ostream &OS, StringRef CodeFieldName, StringRef TypeIdentifier,
5350     StringRef ArgType, StringRef ArgName, StringRef AdditionalArgs,
5351     StringRef AdditionalDeclarations,
5352     std::function<bool(const Record *R)> Filter) {
5353   std::vector<const Record *> MatchedRecords;
5354   const auto &Defs = RK.getAllDerivedDefinitions("PatFrag");
5355   std::copy_if(Defs.begin(), Defs.end(), std::back_inserter(MatchedRecords),
5356                [&](Record *Record) {
5357                  return !Record->getValueAsString(CodeFieldName).empty() &&
5358                         Filter(Record);
5359                });
5360 
5361   if (!MatchedRecords.empty()) {
5362     OS << "// PatFrag predicates.\n"
5363        << "enum {\n";
5364     std::string EnumeratorSeparator =
5365         (" = GIPFP_" + TypeIdentifier + "_Invalid + 1,\n").str();
5366     for (const auto *Record : MatchedRecords) {
5367       OS << "  GIPFP_" << TypeIdentifier << "_Predicate_" << Record->getName()
5368          << EnumeratorSeparator;
5369       EnumeratorSeparator = ",\n";
5370     }
5371     OS << "};\n";
5372   }
5373 
5374   OS << "bool " << Target.getName() << "InstructionSelector::test" << ArgName
5375      << "Predicate_" << TypeIdentifier << "(unsigned PredicateID, " << ArgType << " "
5376      << ArgName << AdditionalArgs <<") const {\n"
5377      << AdditionalDeclarations;
5378   if (!AdditionalDeclarations.empty())
5379     OS << "\n";
5380   if (!MatchedRecords.empty())
5381     OS << "  switch (PredicateID) {\n";
5382   for (const auto *Record : MatchedRecords) {
5383     OS << "  case GIPFP_" << TypeIdentifier << "_Predicate_"
5384        << Record->getName() << ": {\n"
5385        << "    " << Record->getValueAsString(CodeFieldName) << "\n"
5386        << "    llvm_unreachable(\"" << CodeFieldName
5387        << " should have returned\");\n"
5388        << "    return false;\n"
5389        << "  }\n";
5390   }
5391   if (!MatchedRecords.empty())
5392     OS << "  }\n";
5393   OS << "  llvm_unreachable(\"Unknown predicate\");\n"
5394      << "  return false;\n"
5395      << "}\n";
5396 }
5397 
5398 void GlobalISelEmitter::emitImmPredicateFns(
5399     raw_ostream &OS, StringRef TypeIdentifier, StringRef ArgType,
5400     std::function<bool(const Record *R)> Filter) {
5401   return emitCxxPredicateFns(OS, "ImmediateCode", TypeIdentifier, ArgType,
5402                              "Imm", "", "", Filter);
5403 }
5404 
5405 void GlobalISelEmitter::emitMIPredicateFns(raw_ostream &OS) {
5406   return emitCxxPredicateFns(
5407       OS, "GISelPredicateCode", "MI", "const MachineInstr &", "MI",
5408       ", const std::array<const MachineOperand *, 3> &Operands",
5409       "  const MachineFunction &MF = *MI.getParent()->getParent();\n"
5410       "  const MachineRegisterInfo &MRI = MF.getRegInfo();\n"
5411       "  (void)MRI;",
5412       [](const Record *R) { return true; });
5413 }
5414 
5415 template <class GroupT>
5416 std::vector<Matcher *> GlobalISelEmitter::optimizeRules(
5417     ArrayRef<Matcher *> Rules,
5418     std::vector<std::unique_ptr<Matcher>> &MatcherStorage) {
5419 
5420   std::vector<Matcher *> OptRules;
5421   std::unique_ptr<GroupT> CurrentGroup = std::make_unique<GroupT>();
5422   assert(CurrentGroup->empty() && "Newly created group isn't empty!");
5423   unsigned NumGroups = 0;
5424 
5425   auto ProcessCurrentGroup = [&]() {
5426     if (CurrentGroup->empty())
5427       // An empty group is good to be reused:
5428       return;
5429 
5430     // If the group isn't large enough to provide any benefit, move all the
5431     // added rules out of it and make sure to re-create the group to properly
5432     // re-initialize it:
5433     if (CurrentGroup->size() < 2)
5434       append_range(OptRules, CurrentGroup->matchers());
5435     else {
5436       CurrentGroup->finalize();
5437       OptRules.push_back(CurrentGroup.get());
5438       MatcherStorage.emplace_back(std::move(CurrentGroup));
5439       ++NumGroups;
5440     }
5441     CurrentGroup = std::make_unique<GroupT>();
5442   };
5443   for (Matcher *Rule : Rules) {
5444     // Greedily add as many matchers as possible to the current group:
5445     if (CurrentGroup->addMatcher(*Rule))
5446       continue;
5447 
5448     ProcessCurrentGroup();
5449     assert(CurrentGroup->empty() && "A group wasn't properly re-initialized");
5450 
5451     // Try to add the pending matcher to a newly created empty group:
5452     if (!CurrentGroup->addMatcher(*Rule))
5453       // If we couldn't add the matcher to an empty group, that group type
5454       // doesn't support that kind of matchers at all, so just skip it:
5455       OptRules.push_back(Rule);
5456   }
5457   ProcessCurrentGroup();
5458 
5459   LLVM_DEBUG(dbgs() << "NumGroups: " << NumGroups << "\n");
5460   assert(CurrentGroup->empty() && "The last group wasn't properly processed");
5461   return OptRules;
5462 }
5463 
5464 MatchTable
5465 GlobalISelEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules,
5466                                    bool Optimize, bool WithCoverage) {
5467   std::vector<Matcher *> InputRules;
5468   for (Matcher &Rule : Rules)
5469     InputRules.push_back(&Rule);
5470 
5471   if (!Optimize)
5472     return MatchTable::buildTable(InputRules, WithCoverage);
5473 
5474   unsigned CurrentOrdering = 0;
5475   StringMap<unsigned> OpcodeOrder;
5476   for (RuleMatcher &Rule : Rules) {
5477     const StringRef Opcode = Rule.getOpcode();
5478     assert(!Opcode.empty() && "Didn't expect an undefined opcode");
5479     if (OpcodeOrder.count(Opcode) == 0)
5480       OpcodeOrder[Opcode] = CurrentOrdering++;
5481   }
5482 
5483   llvm::stable_sort(InputRules, [&OpcodeOrder](const Matcher *A,
5484                                                const Matcher *B) {
5485     auto *L = static_cast<const RuleMatcher *>(A);
5486     auto *R = static_cast<const RuleMatcher *>(B);
5487     return std::make_tuple(OpcodeOrder[L->getOpcode()], L->getNumOperands()) <
5488            std::make_tuple(OpcodeOrder[R->getOpcode()], R->getNumOperands());
5489   });
5490 
5491   for (Matcher *Rule : InputRules)
5492     Rule->optimize();
5493 
5494   std::vector<std::unique_ptr<Matcher>> MatcherStorage;
5495   std::vector<Matcher *> OptRules =
5496       optimizeRules<GroupMatcher>(InputRules, MatcherStorage);
5497 
5498   for (Matcher *Rule : OptRules)
5499     Rule->optimize();
5500 
5501   OptRules = optimizeRules<SwitchMatcher>(OptRules, MatcherStorage);
5502 
5503   return MatchTable::buildTable(OptRules, WithCoverage);
5504 }
5505 
5506 void GroupMatcher::optimize() {
5507   // Make sure we only sort by a specific predicate within a range of rules that
5508   // all have that predicate checked against a specific value (not a wildcard):
5509   auto F = Matchers.begin();
5510   auto T = F;
5511   auto E = Matchers.end();
5512   while (T != E) {
5513     while (T != E) {
5514       auto *R = static_cast<RuleMatcher *>(*T);
5515       if (!R->getFirstConditionAsRootType().get().isValid())
5516         break;
5517       ++T;
5518     }
5519     std::stable_sort(F, T, [](Matcher *A, Matcher *B) {
5520       auto *L = static_cast<RuleMatcher *>(A);
5521       auto *R = static_cast<RuleMatcher *>(B);
5522       return L->getFirstConditionAsRootType() <
5523              R->getFirstConditionAsRootType();
5524     });
5525     if (T != E)
5526       F = ++T;
5527   }
5528   GlobalISelEmitter::optimizeRules<GroupMatcher>(Matchers, MatcherStorage)
5529       .swap(Matchers);
5530   GlobalISelEmitter::optimizeRules<SwitchMatcher>(Matchers, MatcherStorage)
5531       .swap(Matchers);
5532 }
5533 
5534 void GlobalISelEmitter::run(raw_ostream &OS) {
5535   if (!UseCoverageFile.empty()) {
5536     RuleCoverage = CodeGenCoverage();
5537     auto RuleCoverageBufOrErr = MemoryBuffer::getFile(UseCoverageFile);
5538     if (!RuleCoverageBufOrErr) {
5539       PrintWarning(SMLoc(), "Missing rule coverage data");
5540       RuleCoverage = None;
5541     } else {
5542       if (!RuleCoverage->parse(*RuleCoverageBufOrErr.get(), Target.getName())) {
5543         PrintWarning(SMLoc(), "Ignoring invalid or missing rule coverage data");
5544         RuleCoverage = None;
5545       }
5546     }
5547   }
5548 
5549   // Track the run-time opcode values
5550   gatherOpcodeValues();
5551   // Track the run-time LLT ID values
5552   gatherTypeIDValues();
5553 
5554   // Track the GINodeEquiv definitions.
5555   gatherNodeEquivs();
5556 
5557   emitSourceFileHeader(("Global Instruction Selector for the " +
5558                        Target.getName() + " target").str(), OS);
5559   std::vector<RuleMatcher> Rules;
5560   // Look through the SelectionDAG patterns we found, possibly emitting some.
5561   for (const PatternToMatch &Pat : CGP.ptms()) {
5562     ++NumPatternTotal;
5563 
5564     auto MatcherOrErr = runOnPattern(Pat);
5565 
5566     // The pattern analysis can fail, indicating an unsupported pattern.
5567     // Report that if we've been asked to do so.
5568     if (auto Err = MatcherOrErr.takeError()) {
5569       if (WarnOnSkippedPatterns) {
5570         PrintWarning(Pat.getSrcRecord()->getLoc(),
5571                      "Skipped pattern: " + toString(std::move(Err)));
5572       } else {
5573         consumeError(std::move(Err));
5574       }
5575       ++NumPatternImportsSkipped;
5576       continue;
5577     }
5578 
5579     if (RuleCoverage) {
5580       if (RuleCoverage->isCovered(MatcherOrErr->getRuleID()))
5581         ++NumPatternsTested;
5582       else
5583         PrintWarning(Pat.getSrcRecord()->getLoc(),
5584                      "Pattern is not covered by a test");
5585     }
5586     Rules.push_back(std::move(MatcherOrErr.get()));
5587   }
5588 
5589   // Comparison function to order records by name.
5590   auto orderByName = [](const Record *A, const Record *B) {
5591     return A->getName() < B->getName();
5592   };
5593 
5594   std::vector<Record *> ComplexPredicates =
5595       RK.getAllDerivedDefinitions("GIComplexOperandMatcher");
5596   llvm::sort(ComplexPredicates, orderByName);
5597 
5598   std::vector<Record *> CustomRendererFns =
5599       RK.getAllDerivedDefinitions("GICustomOperandRenderer");
5600   llvm::sort(CustomRendererFns, orderByName);
5601 
5602   unsigned MaxTemporaries = 0;
5603   for (const auto &Rule : Rules)
5604     MaxTemporaries = std::max(MaxTemporaries, Rule.countRendererFns());
5605 
5606   OS << "#ifdef GET_GLOBALISEL_PREDICATE_BITSET\n"
5607      << "const unsigned MAX_SUBTARGET_PREDICATES = " << SubtargetFeatures.size()
5608      << ";\n"
5609      << "using PredicateBitset = "
5610         "llvm::PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;\n"
5611      << "#endif // ifdef GET_GLOBALISEL_PREDICATE_BITSET\n\n";
5612 
5613   OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n"
5614      << "  mutable MatcherState State;\n"
5615      << "  typedef "
5616         "ComplexRendererFns("
5617      << Target.getName()
5618      << "InstructionSelector::*ComplexMatcherMemFn)(MachineOperand &) const;\n"
5619 
5620      << "  typedef void(" << Target.getName()
5621      << "InstructionSelector::*CustomRendererFn)(MachineInstrBuilder &, const "
5622         "MachineInstr &, int) "
5623         "const;\n"
5624      << "  const ISelInfoTy<PredicateBitset, ComplexMatcherMemFn, "
5625         "CustomRendererFn> "
5626         "ISelInfo;\n";
5627   OS << "  static " << Target.getName()
5628      << "InstructionSelector::ComplexMatcherMemFn ComplexPredicateFns[];\n"
5629      << "  static " << Target.getName()
5630      << "InstructionSelector::CustomRendererFn CustomRenderers[];\n"
5631      << "  bool testImmPredicate_I64(unsigned PredicateID, int64_t Imm) const "
5632         "override;\n"
5633      << "  bool testImmPredicate_APInt(unsigned PredicateID, const APInt &Imm) "
5634         "const override;\n"
5635      << "  bool testImmPredicate_APFloat(unsigned PredicateID, const APFloat "
5636         "&Imm) const override;\n"
5637      << "  const int64_t *getMatchTable() const override;\n"
5638      << "  bool testMIPredicate_MI(unsigned PredicateID, const MachineInstr &MI"
5639         ", const std::array<const MachineOperand *, 3> &Operands) "
5640         "const override;\n"
5641      << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n";
5642 
5643   OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n"
5644      << ", State(" << MaxTemporaries << "),\n"
5645      << "ISelInfo(TypeObjects, NumTypeObjects, FeatureBitsets"
5646      << ", ComplexPredicateFns, CustomRenderers)\n"
5647      << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";
5648 
5649   OS << "#ifdef GET_GLOBALISEL_IMPL\n";
5650   SubtargetFeatureInfo::emitSubtargetFeatureBitEnumeration(SubtargetFeatures,
5651                                                            OS);
5652 
5653   // Separate subtarget features by how often they must be recomputed.
5654   SubtargetFeatureInfoMap ModuleFeatures;
5655   std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
5656                std::inserter(ModuleFeatures, ModuleFeatures.end()),
5657                [](const SubtargetFeatureInfoMap::value_type &X) {
5658                  return !X.second.mustRecomputePerFunction();
5659                });
5660   SubtargetFeatureInfoMap FunctionFeatures;
5661   std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
5662                std::inserter(FunctionFeatures, FunctionFeatures.end()),
5663                [](const SubtargetFeatureInfoMap::value_type &X) {
5664                  return X.second.mustRecomputePerFunction();
5665                });
5666 
5667   SubtargetFeatureInfo::emitComputeAvailableFeatures(
5668     Target.getName(), "InstructionSelector", "computeAvailableModuleFeatures",
5669       ModuleFeatures, OS);
5670 
5671 
5672   OS << "void " << Target.getName() << "InstructionSelector"
5673     "::setupGeneratedPerFunctionState(MachineFunction &MF) {\n"
5674     "  AvailableFunctionFeatures = computeAvailableFunctionFeatures("
5675     "(const " << Target.getName() << "Subtarget *)&MF.getSubtarget(), &MF);\n"
5676     "}\n";
5677 
5678   if (Target.getName() == "X86" || Target.getName() == "AArch64") {
5679     // TODO: Implement PGSO.
5680     OS << "static bool shouldOptForSize(const MachineFunction *MF) {\n";
5681     OS << "    return MF->getFunction().hasOptSize();\n";
5682     OS << "}\n\n";
5683   }
5684 
5685   SubtargetFeatureInfo::emitComputeAvailableFeatures(
5686       Target.getName(), "InstructionSelector",
5687       "computeAvailableFunctionFeatures", FunctionFeatures, OS,
5688       "const MachineFunction *MF");
5689 
5690   // Emit a table containing the LLT objects needed by the matcher and an enum
5691   // for the matcher to reference them with.
5692   std::vector<LLTCodeGen> TypeObjects;
5693   append_range(TypeObjects, KnownTypes);
5694   llvm::sort(TypeObjects);
5695   OS << "// LLT Objects.\n"
5696      << "enum {\n";
5697   for (const auto &TypeObject : TypeObjects) {
5698     OS << "  ";
5699     TypeObject.emitCxxEnumValue(OS);
5700     OS << ",\n";
5701   }
5702   OS << "};\n";
5703   OS << "const static size_t NumTypeObjects = " << TypeObjects.size() << ";\n"
5704      << "const static LLT TypeObjects[] = {\n";
5705   for (const auto &TypeObject : TypeObjects) {
5706     OS << "  ";
5707     TypeObject.emitCxxConstructorCall(OS);
5708     OS << ",\n";
5709   }
5710   OS << "};\n\n";
5711 
5712   // Emit a table containing the PredicateBitsets objects needed by the matcher
5713   // and an enum for the matcher to reference them with.
5714   std::vector<std::vector<Record *>> FeatureBitsets;
5715   for (auto &Rule : Rules)
5716     FeatureBitsets.push_back(Rule.getRequiredFeatures());
5717   llvm::sort(FeatureBitsets, [&](const std::vector<Record *> &A,
5718                                  const std::vector<Record *> &B) {
5719     if (A.size() < B.size())
5720       return true;
5721     if (A.size() > B.size())
5722       return false;
5723     for (auto Pair : zip(A, B)) {
5724       if (std::get<0>(Pair)->getName() < std::get<1>(Pair)->getName())
5725         return true;
5726       if (std::get<0>(Pair)->getName() > std::get<1>(Pair)->getName())
5727         return false;
5728     }
5729     return false;
5730   });
5731   FeatureBitsets.erase(
5732       std::unique(FeatureBitsets.begin(), FeatureBitsets.end()),
5733       FeatureBitsets.end());
5734   OS << "// Feature bitsets.\n"
5735      << "enum {\n"
5736      << "  GIFBS_Invalid,\n";
5737   for (const auto &FeatureBitset : FeatureBitsets) {
5738     if (FeatureBitset.empty())
5739       continue;
5740     OS << "  " << getNameForFeatureBitset(FeatureBitset) << ",\n";
5741   }
5742   OS << "};\n"
5743      << "const static PredicateBitset FeatureBitsets[] {\n"
5744      << "  {}, // GIFBS_Invalid\n";
5745   for (const auto &FeatureBitset : FeatureBitsets) {
5746     if (FeatureBitset.empty())
5747       continue;
5748     OS << "  {";
5749     for (const auto &Feature : FeatureBitset) {
5750       const auto &I = SubtargetFeatures.find(Feature);
5751       assert(I != SubtargetFeatures.end() && "Didn't import predicate?");
5752       OS << I->second.getEnumBitName() << ", ";
5753     }
5754     OS << "},\n";
5755   }
5756   OS << "};\n\n";
5757 
5758   // Emit complex predicate table and an enum to reference them with.
5759   OS << "// ComplexPattern predicates.\n"
5760      << "enum {\n"
5761      << "  GICP_Invalid,\n";
5762   for (const auto &Record : ComplexPredicates)
5763     OS << "  GICP_" << Record->getName() << ",\n";
5764   OS << "};\n"
5765      << "// See constructor for table contents\n\n";
5766 
5767   emitImmPredicateFns(OS, "I64", "int64_t", [](const Record *R) {
5768     bool Unset;
5769     return !R->getValueAsBitOrUnset("IsAPFloat", Unset) &&
5770            !R->getValueAsBit("IsAPInt");
5771   });
5772   emitImmPredicateFns(OS, "APFloat", "const APFloat &", [](const Record *R) {
5773     bool Unset;
5774     return R->getValueAsBitOrUnset("IsAPFloat", Unset);
5775   });
5776   emitImmPredicateFns(OS, "APInt", "const APInt &", [](const Record *R) {
5777     return R->getValueAsBit("IsAPInt");
5778   });
5779   emitMIPredicateFns(OS);
5780   OS << "\n";
5781 
5782   OS << Target.getName() << "InstructionSelector::ComplexMatcherMemFn\n"
5783      << Target.getName() << "InstructionSelector::ComplexPredicateFns[] = {\n"
5784      << "  nullptr, // GICP_Invalid\n";
5785   for (const auto &Record : ComplexPredicates)
5786     OS << "  &" << Target.getName()
5787        << "InstructionSelector::" << Record->getValueAsString("MatcherFn")
5788        << ", // " << Record->getName() << "\n";
5789   OS << "};\n\n";
5790 
5791   OS << "// Custom renderers.\n"
5792      << "enum {\n"
5793      << "  GICR_Invalid,\n";
5794   for (const auto &Record : CustomRendererFns)
5795     OS << "  GICR_" << Record->getValueAsString("RendererFn") << ",\n";
5796   OS << "};\n";
5797 
5798   OS << Target.getName() << "InstructionSelector::CustomRendererFn\n"
5799      << Target.getName() << "InstructionSelector::CustomRenderers[] = {\n"
5800      << "  nullptr, // GICR_Invalid\n";
5801   for (const auto &Record : CustomRendererFns)
5802     OS << "  &" << Target.getName()
5803        << "InstructionSelector::" << Record->getValueAsString("RendererFn")
5804        << ", // " << Record->getName() << "\n";
5805   OS << "};\n\n";
5806 
5807   llvm::stable_sort(Rules, [&](const RuleMatcher &A, const RuleMatcher &B) {
5808     int ScoreA = RuleMatcherScores[A.getRuleID()];
5809     int ScoreB = RuleMatcherScores[B.getRuleID()];
5810     if (ScoreA > ScoreB)
5811       return true;
5812     if (ScoreB > ScoreA)
5813       return false;
5814     if (A.isHigherPriorityThan(B)) {
5815       assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
5816                                            "and less important at "
5817                                            "the same time");
5818       return true;
5819     }
5820     return false;
5821   });
5822 
5823   OS << "bool " << Target.getName()
5824      << "InstructionSelector::selectImpl(MachineInstr &I, CodeGenCoverage "
5825         "&CoverageInfo) const {\n"
5826      << "  MachineFunction &MF = *I.getParent()->getParent();\n"
5827      << "  MachineRegisterInfo &MRI = MF.getRegInfo();\n"
5828      << "  const PredicateBitset AvailableFeatures = getAvailableFeatures();\n"
5829      << "  NewMIVector OutMIs;\n"
5830      << "  State.MIs.clear();\n"
5831      << "  State.MIs.push_back(&I);\n\n"
5832      << "  if (executeMatchTable(*this, OutMIs, State, ISelInfo"
5833      << ", getMatchTable(), TII, MRI, TRI, RBI, AvailableFeatures"
5834      << ", CoverageInfo)) {\n"
5835      << "    return true;\n"
5836      << "  }\n\n"
5837      << "  return false;\n"
5838      << "}\n\n";
5839 
5840   const MatchTable Table =
5841       buildMatchTable(Rules, OptimizeMatchTable, GenerateCoverage);
5842   OS << "const int64_t *" << Target.getName()
5843      << "InstructionSelector::getMatchTable() const {\n";
5844   Table.emitDeclaration(OS);
5845   OS << "  return ";
5846   Table.emitUse(OS);
5847   OS << ";\n}\n";
5848   OS << "#endif // ifdef GET_GLOBALISEL_IMPL\n";
5849 
5850   OS << "#ifdef GET_GLOBALISEL_PREDICATES_DECL\n"
5851      << "PredicateBitset AvailableModuleFeatures;\n"
5852      << "mutable PredicateBitset AvailableFunctionFeatures;\n"
5853      << "PredicateBitset getAvailableFeatures() const {\n"
5854      << "  return AvailableModuleFeatures | AvailableFunctionFeatures;\n"
5855      << "}\n"
5856      << "PredicateBitset\n"
5857      << "computeAvailableModuleFeatures(const " << Target.getName()
5858      << "Subtarget *Subtarget) const;\n"
5859      << "PredicateBitset\n"
5860      << "computeAvailableFunctionFeatures(const " << Target.getName()
5861      << "Subtarget *Subtarget,\n"
5862      << "                                 const MachineFunction *MF) const;\n"
5863      << "void setupGeneratedPerFunctionState(MachineFunction &MF) override;\n"
5864      << "#endif // ifdef GET_GLOBALISEL_PREDICATES_DECL\n";
5865 
5866   OS << "#ifdef GET_GLOBALISEL_PREDICATES_INIT\n"
5867      << "AvailableModuleFeatures(computeAvailableModuleFeatures(&STI)),\n"
5868      << "AvailableFunctionFeatures()\n"
5869      << "#endif // ifdef GET_GLOBALISEL_PREDICATES_INIT\n";
5870 }
5871 
5872 void GlobalISelEmitter::declareSubtargetFeature(Record *Predicate) {
5873   if (SubtargetFeatures.count(Predicate) == 0)
5874     SubtargetFeatures.emplace(
5875         Predicate, SubtargetFeatureInfo(Predicate, SubtargetFeatures.size()));
5876 }
5877 
5878 void RuleMatcher::optimize() {
5879   for (auto &Item : InsnVariableIDs) {
5880     InstructionMatcher &InsnMatcher = *Item.first;
5881     for (auto &OM : InsnMatcher.operands()) {
5882       // Complex Patterns are usually expensive and they relatively rarely fail
5883       // on their own: more often we end up throwing away all the work done by a
5884       // matching part of a complex pattern because some other part of the
5885       // enclosing pattern didn't match. All of this makes it beneficial to
5886       // delay complex patterns until the very end of the rule matching,
5887       // especially for targets having lots of complex patterns.
5888       for (auto &OP : OM->predicates())
5889         if (isa<ComplexPatternOperandMatcher>(OP))
5890           EpilogueMatchers.emplace_back(std::move(OP));
5891       OM->eraseNullPredicates();
5892     }
5893     InsnMatcher.optimize();
5894   }
5895   llvm::sort(EpilogueMatchers, [](const std::unique_ptr<PredicateMatcher> &L,
5896                                   const std::unique_ptr<PredicateMatcher> &R) {
5897     return std::make_tuple(L->getKind(), L->getInsnVarID(), L->getOpIdx()) <
5898            std::make_tuple(R->getKind(), R->getInsnVarID(), R->getOpIdx());
5899   });
5900 }
5901 
5902 bool RuleMatcher::hasFirstCondition() const {
5903   if (insnmatchers_empty())
5904     return false;
5905   InstructionMatcher &Matcher = insnmatchers_front();
5906   if (!Matcher.predicates_empty())
5907     return true;
5908   for (auto &OM : Matcher.operands())
5909     for (auto &OP : OM->predicates())
5910       if (!isa<InstructionOperandMatcher>(OP))
5911         return true;
5912   return false;
5913 }
5914 
5915 const PredicateMatcher &RuleMatcher::getFirstCondition() const {
5916   assert(!insnmatchers_empty() &&
5917          "Trying to get a condition from an empty RuleMatcher");
5918 
5919   InstructionMatcher &Matcher = insnmatchers_front();
5920   if (!Matcher.predicates_empty())
5921     return **Matcher.predicates_begin();
5922   // If there is no more predicate on the instruction itself, look at its
5923   // operands.
5924   for (auto &OM : Matcher.operands())
5925     for (auto &OP : OM->predicates())
5926       if (!isa<InstructionOperandMatcher>(OP))
5927         return *OP;
5928 
5929   llvm_unreachable("Trying to get a condition from an InstructionMatcher with "
5930                    "no conditions");
5931 }
5932 
5933 std::unique_ptr<PredicateMatcher> RuleMatcher::popFirstCondition() {
5934   assert(!insnmatchers_empty() &&
5935          "Trying to pop a condition from an empty RuleMatcher");
5936 
5937   InstructionMatcher &Matcher = insnmatchers_front();
5938   if (!Matcher.predicates_empty())
5939     return Matcher.predicates_pop_front();
5940   // If there is no more predicate on the instruction itself, look at its
5941   // operands.
5942   for (auto &OM : Matcher.operands())
5943     for (auto &OP : OM->predicates())
5944       if (!isa<InstructionOperandMatcher>(OP)) {
5945         std::unique_ptr<PredicateMatcher> Result = std::move(OP);
5946         OM->eraseNullPredicates();
5947         return Result;
5948       }
5949 
5950   llvm_unreachable("Trying to pop a condition from an InstructionMatcher with "
5951                    "no conditions");
5952 }
5953 
5954 bool GroupMatcher::candidateConditionMatches(
5955     const PredicateMatcher &Predicate) const {
5956 
5957   if (empty()) {
5958     // Sharing predicates for nested instructions is not supported yet as we
5959     // currently don't hoist the GIM_RecordInsn's properly, therefore we can
5960     // only work on the original root instruction (InsnVarID == 0):
5961     if (Predicate.getInsnVarID() != 0)
5962       return false;
5963     // ... otherwise an empty group can handle any predicate with no specific
5964     // requirements:
5965     return true;
5966   }
5967 
5968   const Matcher &Representative = **Matchers.begin();
5969   const auto &RepresentativeCondition = Representative.getFirstCondition();
5970   // ... if not empty, the group can only accomodate matchers with the exact
5971   // same first condition:
5972   return Predicate.isIdentical(RepresentativeCondition);
5973 }
5974 
5975 bool GroupMatcher::addMatcher(Matcher &Candidate) {
5976   if (!Candidate.hasFirstCondition())
5977     return false;
5978 
5979   const PredicateMatcher &Predicate = Candidate.getFirstCondition();
5980   if (!candidateConditionMatches(Predicate))
5981     return false;
5982 
5983   Matchers.push_back(&Candidate);
5984   return true;
5985 }
5986 
5987 void GroupMatcher::finalize() {
5988   assert(Conditions.empty() && "Already finalized?");
5989   if (empty())
5990     return;
5991 
5992   Matcher &FirstRule = **Matchers.begin();
5993   for (;;) {
5994     // All the checks are expected to succeed during the first iteration:
5995     for (const auto &Rule : Matchers)
5996       if (!Rule->hasFirstCondition())
5997         return;
5998     const auto &FirstCondition = FirstRule.getFirstCondition();
5999     for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
6000       if (!Matchers[I]->getFirstCondition().isIdentical(FirstCondition))
6001         return;
6002 
6003     Conditions.push_back(FirstRule.popFirstCondition());
6004     for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
6005       Matchers[I]->popFirstCondition();
6006   }
6007 }
6008 
6009 void GroupMatcher::emit(MatchTable &Table) {
6010   unsigned LabelID = ~0U;
6011   if (!Conditions.empty()) {
6012     LabelID = Table.allocateLabelID();
6013     Table << MatchTable::Opcode("GIM_Try", +1)
6014           << MatchTable::Comment("On fail goto")
6015           << MatchTable::JumpTarget(LabelID) << MatchTable::LineBreak;
6016   }
6017   for (auto &Condition : Conditions)
6018     Condition->emitPredicateOpcodes(
6019         Table, *static_cast<RuleMatcher *>(*Matchers.begin()));
6020 
6021   for (const auto &M : Matchers)
6022     M->emit(Table);
6023 
6024   // Exit the group
6025   if (!Conditions.empty())
6026     Table << MatchTable::Opcode("GIM_Reject", -1) << MatchTable::LineBreak
6027           << MatchTable::Label(LabelID);
6028 }
6029 
6030 bool SwitchMatcher::isSupportedPredicateType(const PredicateMatcher &P) {
6031   return isa<InstructionOpcodeMatcher>(P) || isa<LLTOperandMatcher>(P);
6032 }
6033 
6034 bool SwitchMatcher::candidateConditionMatches(
6035     const PredicateMatcher &Predicate) const {
6036 
6037   if (empty()) {
6038     // Sharing predicates for nested instructions is not supported yet as we
6039     // currently don't hoist the GIM_RecordInsn's properly, therefore we can
6040     // only work on the original root instruction (InsnVarID == 0):
6041     if (Predicate.getInsnVarID() != 0)
6042       return false;
6043     // ... while an attempt to add even a root matcher to an empty SwitchMatcher
6044     // could fail as not all the types of conditions are supported:
6045     if (!isSupportedPredicateType(Predicate))
6046       return false;
6047     // ... or the condition might not have a proper implementation of
6048     // getValue() / isIdenticalDownToValue() yet:
6049     if (!Predicate.hasValue())
6050       return false;
6051     // ... otherwise an empty Switch can accomodate the condition with no
6052     // further requirements:
6053     return true;
6054   }
6055 
6056   const Matcher &CaseRepresentative = **Matchers.begin();
6057   const auto &RepresentativeCondition = CaseRepresentative.getFirstCondition();
6058   // Switch-cases must share the same kind of condition and path to the value it
6059   // checks:
6060   if (!Predicate.isIdenticalDownToValue(RepresentativeCondition))
6061     return false;
6062 
6063   const auto Value = Predicate.getValue();
6064   // ... but be unique with respect to the actual value they check:
6065   return Values.count(Value) == 0;
6066 }
6067 
6068 bool SwitchMatcher::addMatcher(Matcher &Candidate) {
6069   if (!Candidate.hasFirstCondition())
6070     return false;
6071 
6072   const PredicateMatcher &Predicate = Candidate.getFirstCondition();
6073   if (!candidateConditionMatches(Predicate))
6074     return false;
6075   const auto Value = Predicate.getValue();
6076   Values.insert(Value);
6077 
6078   Matchers.push_back(&Candidate);
6079   return true;
6080 }
6081 
6082 void SwitchMatcher::finalize() {
6083   assert(Condition == nullptr && "Already finalized");
6084   assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");
6085   if (empty())
6086     return;
6087 
6088   llvm::stable_sort(Matchers, [](const Matcher *L, const Matcher *R) {
6089     return L->getFirstCondition().getValue() <
6090            R->getFirstCondition().getValue();
6091   });
6092   Condition = Matchers[0]->popFirstCondition();
6093   for (unsigned I = 1, E = Values.size(); I < E; ++I)
6094     Matchers[I]->popFirstCondition();
6095 }
6096 
6097 void SwitchMatcher::emitPredicateSpecificOpcodes(const PredicateMatcher &P,
6098                                                  MatchTable &Table) {
6099   assert(isSupportedPredicateType(P) && "Predicate type is not supported");
6100 
6101   if (const auto *Condition = dyn_cast<InstructionOpcodeMatcher>(&P)) {
6102     Table << MatchTable::Opcode("GIM_SwitchOpcode") << MatchTable::Comment("MI")
6103           << MatchTable::IntValue(Condition->getInsnVarID());
6104     return;
6105   }
6106   if (const auto *Condition = dyn_cast<LLTOperandMatcher>(&P)) {
6107     Table << MatchTable::Opcode("GIM_SwitchType") << MatchTable::Comment("MI")
6108           << MatchTable::IntValue(Condition->getInsnVarID())
6109           << MatchTable::Comment("Op")
6110           << MatchTable::IntValue(Condition->getOpIdx());
6111     return;
6112   }
6113 
6114   llvm_unreachable("emitPredicateSpecificOpcodes is broken: can not handle a "
6115                    "predicate type that is claimed to be supported");
6116 }
6117 
6118 void SwitchMatcher::emit(MatchTable &Table) {
6119   assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");
6120   if (empty())
6121     return;
6122   assert(Condition != nullptr &&
6123          "Broken SwitchMatcher, hasn't been finalized?");
6124 
6125   std::vector<unsigned> LabelIDs(Values.size());
6126   std::generate(LabelIDs.begin(), LabelIDs.end(),
6127                 [&Table]() { return Table.allocateLabelID(); });
6128   const unsigned Default = Table.allocateLabelID();
6129 
6130   const int64_t LowerBound = Values.begin()->getRawValue();
6131   const int64_t UpperBound = Values.rbegin()->getRawValue() + 1;
6132 
6133   emitPredicateSpecificOpcodes(*Condition, Table);
6134 
6135   Table << MatchTable::Comment("[") << MatchTable::IntValue(LowerBound)
6136         << MatchTable::IntValue(UpperBound) << MatchTable::Comment(")")
6137         << MatchTable::Comment("default:") << MatchTable::JumpTarget(Default);
6138 
6139   int64_t J = LowerBound;
6140   auto VI = Values.begin();
6141   for (unsigned I = 0, E = Values.size(); I < E; ++I) {
6142     auto V = *VI++;
6143     while (J++ < V.getRawValue())
6144       Table << MatchTable::IntValue(0);
6145     V.turnIntoComment();
6146     Table << MatchTable::LineBreak << V << MatchTable::JumpTarget(LabelIDs[I]);
6147   }
6148   Table << MatchTable::LineBreak;
6149 
6150   for (unsigned I = 0, E = Values.size(); I < E; ++I) {
6151     Table << MatchTable::Label(LabelIDs[I]);
6152     Matchers[I]->emit(Table);
6153     Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
6154   }
6155   Table << MatchTable::Label(Default);
6156 }
6157 
6158 unsigned OperandMatcher::getInsnVarID() const { return Insn.getInsnVarID(); }
6159 
6160 } // end anonymous namespace
6161 
6162 //===----------------------------------------------------------------------===//
6163 
6164 namespace llvm {
6165 void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS) {
6166   GlobalISelEmitter(RK).run(OS);
6167 }
6168 } // End llvm namespace
6169