1 //===- GlobalISelEmitter.cpp - Generate an instruction selector -----------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 /// \file
11 /// This tablegen backend emits code for use by the GlobalISel instruction
12 /// selector. See include/llvm/CodeGen/TargetGlobalISel.td.
13 ///
14 /// This file analyzes the patterns recognized by the SelectionDAGISel tablegen
15 /// backend, filters out the ones that are unsupported, maps
16 /// SelectionDAG-specific constructs to their GlobalISel counterpart
17 /// (when applicable: MVT to LLT;  SDNode to generic Instruction).
18 ///
19 /// Not all patterns are supported: pass the tablegen invocation
20 /// "-warn-on-skipped-patterns" to emit a warning when a pattern is skipped,
21 /// as well as why.
22 ///
23 /// The generated file defines a single method:
24 ///     bool <Target>InstructionSelector::selectImpl(MachineInstr &I) const;
25 /// intended to be used in InstructionSelector::select as the first-step
26 /// selector for the patterns that don't require complex C++.
27 ///
28 /// FIXME: We'll probably want to eventually define a base
29 /// "TargetGenInstructionSelector" class.
30 ///
31 //===----------------------------------------------------------------------===//
32 
33 #include "CodeGenDAGPatterns.h"
34 #include "SubtargetFeatureInfo.h"
35 #include "llvm/ADT/Optional.h"
36 #include "llvm/ADT/SmallSet.h"
37 #include "llvm/ADT/Statistic.h"
38 #include "llvm/Support/CodeGenCoverage.h"
39 #include "llvm/Support/CommandLine.h"
40 #include "llvm/Support/Error.h"
41 #include "llvm/Support/LowLevelTypeImpl.h"
42 #include "llvm/Support/MachineValueType.h"
43 #include "llvm/Support/ScopedPrinter.h"
44 #include "llvm/TableGen/Error.h"
45 #include "llvm/TableGen/Record.h"
46 #include "llvm/TableGen/TableGenBackend.h"
47 #include <numeric>
48 #include <string>
49 using namespace llvm;
50 
51 #define DEBUG_TYPE "gisel-emitter"
52 
53 STATISTIC(NumPatternTotal, "Total number of patterns");
54 STATISTIC(NumPatternImported, "Number of patterns imported from SelectionDAG");
55 STATISTIC(NumPatternImportsSkipped, "Number of SelectionDAG imports skipped");
56 STATISTIC(NumPatternsTested, "Number of patterns executed according to coverage information");
57 STATISTIC(NumPatternEmitted, "Number of patterns emitted");
58 
59 cl::OptionCategory GlobalISelEmitterCat("Options for -gen-global-isel");
60 
61 static cl::opt<bool> WarnOnSkippedPatterns(
62     "warn-on-skipped-patterns",
63     cl::desc("Explain why a pattern was skipped for inclusion "
64              "in the GlobalISel selector"),
65     cl::init(false), cl::cat(GlobalISelEmitterCat));
66 
67 static cl::opt<bool> GenerateCoverage(
68     "instrument-gisel-coverage",
69     cl::desc("Generate coverage instrumentation for GlobalISel"),
70     cl::init(false), cl::cat(GlobalISelEmitterCat));
71 
72 static cl::opt<std::string> UseCoverageFile(
73     "gisel-coverage-file", cl::init(""),
74     cl::desc("Specify file to retrieve coverage information from"),
75     cl::cat(GlobalISelEmitterCat));
76 
77 static cl::opt<bool> OptimizeMatchTable(
78     "optimize-match-table",
79     cl::desc("Generate an optimized version of the match table"),
80     cl::init(true), cl::cat(GlobalISelEmitterCat));
81 
82 namespace {
83 //===- Helper functions ---------------------------------------------------===//
84 
85 /// Get the name of the enum value used to number the predicate function.
getEnumNameForPredicate(const TreePredicateFn & Predicate)86 std::string getEnumNameForPredicate(const TreePredicateFn &Predicate) {
87   if (Predicate.hasGISelPredicateCode())
88     return "GIPFP_MI_" + Predicate.getFnName();
89   return "GIPFP_" + Predicate.getImmTypeIdentifier().str() + "_" +
90          Predicate.getFnName();
91 }
92 
93 /// Get the opcode used to check this predicate.
getMatchOpcodeForPredicate(const TreePredicateFn & Predicate)94 std::string getMatchOpcodeForPredicate(const TreePredicateFn &Predicate) {
95   return "GIM_Check" + Predicate.getImmTypeIdentifier().str() + "ImmPredicate";
96 }
97 
98 /// This class stands in for LLT wherever we want to tablegen-erate an
99 /// equivalent at compiler run-time.
100 class LLTCodeGen {
101 private:
102   LLT Ty;
103 
104 public:
105   LLTCodeGen() = default;
LLTCodeGen(const LLT & Ty)106   LLTCodeGen(const LLT &Ty) : Ty(Ty) {}
107 
getCxxEnumValue() const108   std::string getCxxEnumValue() const {
109     std::string Str;
110     raw_string_ostream OS(Str);
111 
112     emitCxxEnumValue(OS);
113     return OS.str();
114   }
115 
emitCxxEnumValue(raw_ostream & OS) const116   void emitCxxEnumValue(raw_ostream &OS) const {
117     if (Ty.isScalar()) {
118       OS << "GILLT_s" << Ty.getSizeInBits();
119       return;
120     }
121     if (Ty.isVector()) {
122       OS << "GILLT_v" << Ty.getNumElements() << "s" << Ty.getScalarSizeInBits();
123       return;
124     }
125     if (Ty.isPointer()) {
126       OS << "GILLT_p" << Ty.getAddressSpace();
127       if (Ty.getSizeInBits() > 0)
128         OS << "s" << Ty.getSizeInBits();
129       return;
130     }
131     llvm_unreachable("Unhandled LLT");
132   }
133 
emitCxxConstructorCall(raw_ostream & OS) const134   void emitCxxConstructorCall(raw_ostream &OS) const {
135     if (Ty.isScalar()) {
136       OS << "LLT::scalar(" << Ty.getSizeInBits() << ")";
137       return;
138     }
139     if (Ty.isVector()) {
140       OS << "LLT::vector(" << Ty.getNumElements() << ", "
141          << Ty.getScalarSizeInBits() << ")";
142       return;
143     }
144     if (Ty.isPointer() && Ty.getSizeInBits() > 0) {
145       OS << "LLT::pointer(" << Ty.getAddressSpace() << ", "
146          << Ty.getSizeInBits() << ")";
147       return;
148     }
149     llvm_unreachable("Unhandled LLT");
150   }
151 
get() const152   const LLT &get() const { return Ty; }
153 
154   /// This ordering is used for std::unique() and llvm::sort(). There's no
155   /// particular logic behind the order but either A < B or B < A must be
156   /// true if A != B.
operator <(const LLTCodeGen & Other) const157   bool operator<(const LLTCodeGen &Other) const {
158     if (Ty.isValid() != Other.Ty.isValid())
159       return Ty.isValid() < Other.Ty.isValid();
160     if (!Ty.isValid())
161       return false;
162 
163     if (Ty.isVector() != Other.Ty.isVector())
164       return Ty.isVector() < Other.Ty.isVector();
165     if (Ty.isScalar() != Other.Ty.isScalar())
166       return Ty.isScalar() < Other.Ty.isScalar();
167     if (Ty.isPointer() != Other.Ty.isPointer())
168       return Ty.isPointer() < Other.Ty.isPointer();
169 
170     if (Ty.isPointer() && Ty.getAddressSpace() != Other.Ty.getAddressSpace())
171       return Ty.getAddressSpace() < Other.Ty.getAddressSpace();
172 
173     if (Ty.isVector() && Ty.getNumElements() != Other.Ty.getNumElements())
174       return Ty.getNumElements() < Other.Ty.getNumElements();
175 
176     return Ty.getSizeInBits() < Other.Ty.getSizeInBits();
177   }
178 
operator ==(const LLTCodeGen & B) const179   bool operator==(const LLTCodeGen &B) const { return Ty == B.Ty; }
180 };
181 
182 // Track all types that are used so we can emit the corresponding enum.
183 std::set<LLTCodeGen> KnownTypes;
184 
185 class InstructionMatcher;
186 /// Convert an MVT to an equivalent LLT if possible, or the invalid LLT() for
187 /// MVTs that don't map cleanly to an LLT (e.g., iPTR, *any, ...).
MVTToLLT(MVT::SimpleValueType SVT)188 static Optional<LLTCodeGen> MVTToLLT(MVT::SimpleValueType SVT) {
189   MVT VT(SVT);
190 
191   if (VT.isVector() && VT.getVectorNumElements() != 1)
192     return LLTCodeGen(
193         LLT::vector(VT.getVectorNumElements(), VT.getScalarSizeInBits()));
194 
195   if (VT.isInteger() || VT.isFloatingPoint())
196     return LLTCodeGen(LLT::scalar(VT.getSizeInBits()));
197   return None;
198 }
199 
explainPredicates(const TreePatternNode * N)200 static std::string explainPredicates(const TreePatternNode *N) {
201   std::string Explanation = "";
202   StringRef Separator = "";
203   for (const auto &P : N->getPredicateFns()) {
204     Explanation +=
205         (Separator + P.getOrigPatFragRecord()->getRecord()->getName()).str();
206     Separator = ", ";
207 
208     if (P.isAlwaysTrue())
209       Explanation += " always-true";
210     if (P.isImmediatePattern())
211       Explanation += " immediate";
212 
213     if (P.isUnindexed())
214       Explanation += " unindexed";
215 
216     if (P.isNonExtLoad())
217       Explanation += " non-extload";
218     if (P.isAnyExtLoad())
219       Explanation += " extload";
220     if (P.isSignExtLoad())
221       Explanation += " sextload";
222     if (P.isZeroExtLoad())
223       Explanation += " zextload";
224 
225     if (P.isNonTruncStore())
226       Explanation += " non-truncstore";
227     if (P.isTruncStore())
228       Explanation += " truncstore";
229 
230     if (Record *VT = P.getMemoryVT())
231       Explanation += (" MemVT=" + VT->getName()).str();
232     if (Record *VT = P.getScalarMemoryVT())
233       Explanation += (" ScalarVT(MemVT)=" + VT->getName()).str();
234 
235     if (P.isAtomicOrderingMonotonic())
236       Explanation += " monotonic";
237     if (P.isAtomicOrderingAcquire())
238       Explanation += " acquire";
239     if (P.isAtomicOrderingRelease())
240       Explanation += " release";
241     if (P.isAtomicOrderingAcquireRelease())
242       Explanation += " acq_rel";
243     if (P.isAtomicOrderingSequentiallyConsistent())
244       Explanation += " seq_cst";
245     if (P.isAtomicOrderingAcquireOrStronger())
246       Explanation += " >=acquire";
247     if (P.isAtomicOrderingWeakerThanAcquire())
248       Explanation += " <acquire";
249     if (P.isAtomicOrderingReleaseOrStronger())
250       Explanation += " >=release";
251     if (P.isAtomicOrderingWeakerThanRelease())
252       Explanation += " <release";
253   }
254   return Explanation;
255 }
256 
explainOperator(Record * Operator)257 std::string explainOperator(Record *Operator) {
258   if (Operator->isSubClassOf("SDNode"))
259     return (" (" + Operator->getValueAsString("Opcode") + ")").str();
260 
261   if (Operator->isSubClassOf("Intrinsic"))
262     return (" (Operator is an Intrinsic, " + Operator->getName() + ")").str();
263 
264   if (Operator->isSubClassOf("ComplexPattern"))
265     return (" (Operator is an unmapped ComplexPattern, " + Operator->getName() +
266             ")")
267         .str();
268 
269   if (Operator->isSubClassOf("SDNodeXForm"))
270     return (" (Operator is an unmapped SDNodeXForm, " + Operator->getName() +
271             ")")
272         .str();
273 
274   return (" (Operator " + Operator->getName() + " not understood)").str();
275 }
276 
277 /// Helper function to let the emitter report skip reason error messages.
failedImport(const Twine & Reason)278 static Error failedImport(const Twine &Reason) {
279   return make_error<StringError>(Reason, inconvertibleErrorCode());
280 }
281 
isTrivialOperatorNode(const TreePatternNode * N)282 static Error isTrivialOperatorNode(const TreePatternNode *N) {
283   std::string Explanation = "";
284   std::string Separator = "";
285 
286   bool HasUnsupportedPredicate = false;
287   for (const auto &Predicate : N->getPredicateFns()) {
288     if (Predicate.isAlwaysTrue())
289       continue;
290 
291     if (Predicate.isImmediatePattern())
292       continue;
293 
294     if (Predicate.isNonExtLoad() || Predicate.isAnyExtLoad() ||
295         Predicate.isSignExtLoad() || Predicate.isZeroExtLoad())
296       continue;
297 
298     if (Predicate.isNonTruncStore())
299       continue;
300 
301     if (Predicate.isLoad() && Predicate.getMemoryVT())
302       continue;
303 
304     if (Predicate.isLoad() || Predicate.isStore()) {
305       if (Predicate.isUnindexed())
306         continue;
307     }
308 
309     if (Predicate.isAtomic() && Predicate.getMemoryVT())
310       continue;
311 
312     if (Predicate.isAtomic() &&
313         (Predicate.isAtomicOrderingMonotonic() ||
314          Predicate.isAtomicOrderingAcquire() ||
315          Predicate.isAtomicOrderingRelease() ||
316          Predicate.isAtomicOrderingAcquireRelease() ||
317          Predicate.isAtomicOrderingSequentiallyConsistent() ||
318          Predicate.isAtomicOrderingAcquireOrStronger() ||
319          Predicate.isAtomicOrderingWeakerThanAcquire() ||
320          Predicate.isAtomicOrderingReleaseOrStronger() ||
321          Predicate.isAtomicOrderingWeakerThanRelease()))
322       continue;
323 
324     if (Predicate.hasGISelPredicateCode())
325       continue;
326 
327     HasUnsupportedPredicate = true;
328     Explanation = Separator + "Has a predicate (" + explainPredicates(N) + ")";
329     Separator = ", ";
330     Explanation += (Separator + "first-failing:" +
331                     Predicate.getOrigPatFragRecord()->getRecord()->getName())
332                        .str();
333     break;
334   }
335 
336   if (!HasUnsupportedPredicate)
337     return Error::success();
338 
339   return failedImport(Explanation);
340 }
341 
getInitValueAsRegClass(Init * V)342 static Record *getInitValueAsRegClass(Init *V) {
343   if (DefInit *VDefInit = dyn_cast<DefInit>(V)) {
344     if (VDefInit->getDef()->isSubClassOf("RegisterOperand"))
345       return VDefInit->getDef()->getValueAsDef("RegClass");
346     if (VDefInit->getDef()->isSubClassOf("RegisterClass"))
347       return VDefInit->getDef();
348   }
349   return nullptr;
350 }
351 
352 std::string
getNameForFeatureBitset(const std::vector<Record * > & FeatureBitset)353 getNameForFeatureBitset(const std::vector<Record *> &FeatureBitset) {
354   std::string Name = "GIFBS";
355   for (const auto &Feature : FeatureBitset)
356     Name += ("_" + Feature->getName()).str();
357   return Name;
358 }
359 
360 //===- MatchTable Helpers -------------------------------------------------===//
361 
362 class MatchTable;
363 
364 /// A record to be stored in a MatchTable.
365 ///
366 /// This class represents any and all output that may be required to emit the
367 /// MatchTable. Instances  are most often configured to represent an opcode or
368 /// value that will be emitted to the table with some formatting but it can also
369 /// represent commas, comments, and other formatting instructions.
370 struct MatchTableRecord {
371   enum RecordFlagsBits {
372     MTRF_None = 0x0,
373     /// Causes EmitStr to be formatted as comment when emitted.
374     MTRF_Comment = 0x1,
375     /// Causes the record value to be followed by a comma when emitted.
376     MTRF_CommaFollows = 0x2,
377     /// Causes the record value to be followed by a line break when emitted.
378     MTRF_LineBreakFollows = 0x4,
379     /// Indicates that the record defines a label and causes an additional
380     /// comment to be emitted containing the index of the label.
381     MTRF_Label = 0x8,
382     /// Causes the record to be emitted as the index of the label specified by
383     /// LabelID along with a comment indicating where that label is.
384     MTRF_JumpTarget = 0x10,
385     /// Causes the formatter to add a level of indentation before emitting the
386     /// record.
387     MTRF_Indent = 0x20,
388     /// Causes the formatter to remove a level of indentation after emitting the
389     /// record.
390     MTRF_Outdent = 0x40,
391   };
392 
393   /// When MTRF_Label or MTRF_JumpTarget is used, indicates a label id to
394   /// reference or define.
395   unsigned LabelID;
396   /// The string to emit. Depending on the MTRF_* flags it may be a comment, a
397   /// value, a label name.
398   std::string EmitStr;
399 
400 private:
401   /// The number of MatchTable elements described by this record. Comments are 0
402   /// while values are typically 1. Values >1 may occur when we need to emit
403   /// values that exceed the size of a MatchTable element.
404   unsigned NumElements;
405 
406 public:
407   /// A bitfield of RecordFlagsBits flags.
408   unsigned Flags;
409 
410   /// The actual run-time value, if known
411   int64_t RawValue;
412 
MatchTableRecord__anon879284f50111::MatchTableRecord413   MatchTableRecord(Optional<unsigned> LabelID_, StringRef EmitStr,
414                    unsigned NumElements, unsigned Flags,
415                    int64_t RawValue = std::numeric_limits<int64_t>::min())
416       : LabelID(LabelID_.hasValue() ? LabelID_.getValue() : ~0u),
417         EmitStr(EmitStr), NumElements(NumElements), Flags(Flags),
418         RawValue(RawValue) {
419 
420     assert((!LabelID_.hasValue() || LabelID != ~0u) &&
421            "This value is reserved for non-labels");
422   }
423   MatchTableRecord(const MatchTableRecord &Other) = default;
424   MatchTableRecord(MatchTableRecord &&Other) = default;
425 
426   /// Useful if a Match Table Record gets optimized out
turnIntoComment__anon879284f50111::MatchTableRecord427   void turnIntoComment() {
428     Flags |= MTRF_Comment;
429     Flags &= ~MTRF_CommaFollows;
430     NumElements = 0;
431   }
432 
433   /// For Jump Table generation purposes
operator <__anon879284f50111::MatchTableRecord434   bool operator<(const MatchTableRecord &Other) const {
435     return RawValue < Other.RawValue;
436   }
getRawValue__anon879284f50111::MatchTableRecord437   int64_t getRawValue() const { return RawValue; }
438 
439   void emit(raw_ostream &OS, bool LineBreakNextAfterThis,
440             const MatchTable &Table) const;
size__anon879284f50111::MatchTableRecord441   unsigned size() const { return NumElements; }
442 };
443 
444 class Matcher;
445 
446 /// Holds the contents of a generated MatchTable to enable formatting and the
447 /// necessary index tracking needed to support GIM_Try.
448 class MatchTable {
449   /// An unique identifier for the table. The generated table will be named
450   /// MatchTable${ID}.
451   unsigned ID;
452   /// The records that make up the table. Also includes comments describing the
453   /// values being emitted and line breaks to format it.
454   std::vector<MatchTableRecord> Contents;
455   /// The currently defined labels.
456   DenseMap<unsigned, unsigned> LabelMap;
457   /// Tracks the sum of MatchTableRecord::NumElements as the table is built.
458   unsigned CurrentSize = 0;
459   /// A unique identifier for a MatchTable label.
460   unsigned CurrentLabelID = 0;
461   /// Determines if the table should be instrumented for rule coverage tracking.
462   bool IsWithCoverage;
463 
464 public:
465   static MatchTableRecord LineBreak;
Comment(StringRef Comment)466   static MatchTableRecord Comment(StringRef Comment) {
467     return MatchTableRecord(None, Comment, 0, MatchTableRecord::MTRF_Comment);
468   }
Opcode(StringRef Opcode,int IndentAdjust=0)469   static MatchTableRecord Opcode(StringRef Opcode, int IndentAdjust = 0) {
470     unsigned ExtraFlags = 0;
471     if (IndentAdjust > 0)
472       ExtraFlags |= MatchTableRecord::MTRF_Indent;
473     if (IndentAdjust < 0)
474       ExtraFlags |= MatchTableRecord::MTRF_Outdent;
475 
476     return MatchTableRecord(None, Opcode, 1,
477                             MatchTableRecord::MTRF_CommaFollows | ExtraFlags);
478   }
NamedValue(StringRef NamedValue)479   static MatchTableRecord NamedValue(StringRef NamedValue) {
480     return MatchTableRecord(None, NamedValue, 1,
481                             MatchTableRecord::MTRF_CommaFollows);
482   }
NamedValue(StringRef NamedValue,int64_t RawValue)483   static MatchTableRecord NamedValue(StringRef NamedValue, int64_t RawValue) {
484     return MatchTableRecord(None, NamedValue, 1,
485                             MatchTableRecord::MTRF_CommaFollows, RawValue);
486   }
NamedValue(StringRef Namespace,StringRef NamedValue)487   static MatchTableRecord NamedValue(StringRef Namespace,
488                                      StringRef NamedValue) {
489     return MatchTableRecord(None, (Namespace + "::" + NamedValue).str(), 1,
490                             MatchTableRecord::MTRF_CommaFollows);
491   }
NamedValue(StringRef Namespace,StringRef NamedValue,int64_t RawValue)492   static MatchTableRecord NamedValue(StringRef Namespace, StringRef NamedValue,
493                                      int64_t RawValue) {
494     return MatchTableRecord(None, (Namespace + "::" + NamedValue).str(), 1,
495                             MatchTableRecord::MTRF_CommaFollows, RawValue);
496   }
IntValue(int64_t IntValue)497   static MatchTableRecord IntValue(int64_t IntValue) {
498     return MatchTableRecord(None, llvm::to_string(IntValue), 1,
499                             MatchTableRecord::MTRF_CommaFollows);
500   }
Label(unsigned LabelID)501   static MatchTableRecord Label(unsigned LabelID) {
502     return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 0,
503                             MatchTableRecord::MTRF_Label |
504                                 MatchTableRecord::MTRF_Comment |
505                                 MatchTableRecord::MTRF_LineBreakFollows);
506   }
JumpTarget(unsigned LabelID)507   static MatchTableRecord JumpTarget(unsigned LabelID) {
508     return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 1,
509                             MatchTableRecord::MTRF_JumpTarget |
510                                 MatchTableRecord::MTRF_Comment |
511                                 MatchTableRecord::MTRF_CommaFollows);
512   }
513 
514   static MatchTable buildTable(ArrayRef<Matcher *> Rules, bool WithCoverage);
515 
MatchTable(bool WithCoverage,unsigned ID=0)516   MatchTable(bool WithCoverage, unsigned ID = 0)
517       : ID(ID), IsWithCoverage(WithCoverage) {}
518 
isWithCoverage() const519   bool isWithCoverage() const { return IsWithCoverage; }
520 
push_back(const MatchTableRecord & Value)521   void push_back(const MatchTableRecord &Value) {
522     if (Value.Flags & MatchTableRecord::MTRF_Label)
523       defineLabel(Value.LabelID);
524     Contents.push_back(Value);
525     CurrentSize += Value.size();
526   }
527 
allocateLabelID()528   unsigned allocateLabelID() { return CurrentLabelID++; }
529 
defineLabel(unsigned LabelID)530   void defineLabel(unsigned LabelID) {
531     LabelMap.insert(std::make_pair(LabelID, CurrentSize));
532   }
533 
getLabelIndex(unsigned LabelID) const534   unsigned getLabelIndex(unsigned LabelID) const {
535     const auto I = LabelMap.find(LabelID);
536     assert(I != LabelMap.end() && "Use of undeclared label");
537     return I->second;
538   }
539 
emitUse(raw_ostream & OS) const540   void emitUse(raw_ostream &OS) const { OS << "MatchTable" << ID; }
541 
emitDeclaration(raw_ostream & OS) const542   void emitDeclaration(raw_ostream &OS) const {
543     unsigned Indentation = 4;
544     OS << "  constexpr static int64_t MatchTable" << ID << "[] = {";
545     LineBreak.emit(OS, true, *this);
546     OS << std::string(Indentation, ' ');
547 
548     for (auto I = Contents.begin(), E = Contents.end(); I != E;
549          ++I) {
550       bool LineBreakIsNext = false;
551       const auto &NextI = std::next(I);
552 
553       if (NextI != E) {
554         if (NextI->EmitStr == "" &&
555             NextI->Flags == MatchTableRecord::MTRF_LineBreakFollows)
556           LineBreakIsNext = true;
557       }
558 
559       if (I->Flags & MatchTableRecord::MTRF_Indent)
560         Indentation += 2;
561 
562       I->emit(OS, LineBreakIsNext, *this);
563       if (I->Flags & MatchTableRecord::MTRF_LineBreakFollows)
564         OS << std::string(Indentation, ' ');
565 
566       if (I->Flags & MatchTableRecord::MTRF_Outdent)
567         Indentation -= 2;
568     }
569     OS << "};\n";
570   }
571 };
572 
573 MatchTableRecord MatchTable::LineBreak = {
574     None, "" /* Emit String */, 0 /* Elements */,
575     MatchTableRecord::MTRF_LineBreakFollows};
576 
emit(raw_ostream & OS,bool LineBreakIsNextAfterThis,const MatchTable & Table) const577 void MatchTableRecord::emit(raw_ostream &OS, bool LineBreakIsNextAfterThis,
578                             const MatchTable &Table) const {
579   bool UseLineComment =
580       LineBreakIsNextAfterThis | (Flags & MTRF_LineBreakFollows);
581   if (Flags & (MTRF_JumpTarget | MTRF_CommaFollows))
582     UseLineComment = false;
583 
584   if (Flags & MTRF_Comment)
585     OS << (UseLineComment ? "// " : "/*");
586 
587   OS << EmitStr;
588   if (Flags & MTRF_Label)
589     OS << ": @" << Table.getLabelIndex(LabelID);
590 
591   if (Flags & MTRF_Comment && !UseLineComment)
592     OS << "*/";
593 
594   if (Flags & MTRF_JumpTarget) {
595     if (Flags & MTRF_Comment)
596       OS << " ";
597     OS << Table.getLabelIndex(LabelID);
598   }
599 
600   if (Flags & MTRF_CommaFollows) {
601     OS << ",";
602     if (!LineBreakIsNextAfterThis && !(Flags & MTRF_LineBreakFollows))
603       OS << " ";
604   }
605 
606   if (Flags & MTRF_LineBreakFollows)
607     OS << "\n";
608 }
609 
operator <<(MatchTable & Table,const MatchTableRecord & Value)610 MatchTable &operator<<(MatchTable &Table, const MatchTableRecord &Value) {
611   Table.push_back(Value);
612   return Table;
613 }
614 
615 //===- Matchers -----------------------------------------------------------===//
616 
617 class OperandMatcher;
618 class MatchAction;
619 class PredicateMatcher;
620 class RuleMatcher;
621 
622 class Matcher {
623 public:
624   virtual ~Matcher() = default;
optimize()625   virtual void optimize() {}
626   virtual void emit(MatchTable &Table) = 0;
627 
628   virtual bool hasFirstCondition() const = 0;
629   virtual const PredicateMatcher &getFirstCondition() const = 0;
630   virtual std::unique_ptr<PredicateMatcher> popFirstCondition() = 0;
631 };
632 
buildTable(ArrayRef<Matcher * > Rules,bool WithCoverage)633 MatchTable MatchTable::buildTable(ArrayRef<Matcher *> Rules,
634                                   bool WithCoverage) {
635   MatchTable Table(WithCoverage);
636   for (Matcher *Rule : Rules)
637     Rule->emit(Table);
638 
639   return Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
640 }
641 
642 class GroupMatcher final : public Matcher {
643   /// Conditions that form a common prefix of all the matchers contained.
644   SmallVector<std::unique_ptr<PredicateMatcher>, 1> Conditions;
645 
646   /// All the nested matchers, sharing a common prefix.
647   std::vector<Matcher *> Matchers;
648 
649   /// An owning collection for any auxiliary matchers created while optimizing
650   /// nested matchers contained.
651   std::vector<std::unique_ptr<Matcher>> MatcherStorage;
652 
653 public:
654   /// Add a matcher to the collection of nested matchers if it meets the
655   /// requirements, and return true. If it doesn't, do nothing and return false.
656   ///
657   /// Expected to preserve its argument, so it could be moved out later on.
658   bool addMatcher(Matcher &Candidate);
659 
660   /// Mark the matcher as fully-built and ensure any invariants expected by both
661   /// optimize() and emit(...) methods. Generally, both sequences of calls
662   /// are expected to lead to a sensible result:
663   ///
664   /// addMatcher(...)*; finalize(); optimize(); emit(...); and
665   /// addMatcher(...)*; finalize(); emit(...);
666   ///
667   /// or generally
668   ///
669   /// addMatcher(...)*; finalize(); { optimize()*; emit(...); }*
670   ///
671   /// Multiple calls to optimize() are expected to be handled gracefully, though
672   /// optimize() is not expected to be idempotent. Multiple calls to finalize()
673   /// aren't generally supported. emit(...) is expected to be non-mutating and
674   /// producing the exact same results upon repeated calls.
675   ///
676   /// addMatcher() calls after the finalize() call are not supported.
677   ///
678   /// finalize() and optimize() are both allowed to mutate the contained
679   /// matchers, so moving them out after finalize() is not supported.
680   void finalize();
681   void optimize() override;
682   void emit(MatchTable &Table) override;
683 
684   /// Could be used to move out the matchers added previously, unless finalize()
685   /// has been already called. If any of the matchers are moved out, the group
686   /// becomes safe to destroy, but not safe to re-use for anything else.
matchers()687   iterator_range<std::vector<Matcher *>::iterator> matchers() {
688     return make_range(Matchers.begin(), Matchers.end());
689   }
size() const690   size_t size() const { return Matchers.size(); }
empty() const691   bool empty() const { return Matchers.empty(); }
692 
popFirstCondition()693   std::unique_ptr<PredicateMatcher> popFirstCondition() override {
694     assert(!Conditions.empty() &&
695            "Trying to pop a condition from a condition-less group");
696     std::unique_ptr<PredicateMatcher> P = std::move(Conditions.front());
697     Conditions.erase(Conditions.begin());
698     return P;
699   }
getFirstCondition() const700   const PredicateMatcher &getFirstCondition() const override {
701     assert(!Conditions.empty() &&
702            "Trying to get a condition from a condition-less group");
703     return *Conditions.front();
704   }
hasFirstCondition() const705   bool hasFirstCondition() const override { return !Conditions.empty(); }
706 
707 private:
708   /// See if a candidate matcher could be added to this group solely by
709   /// analyzing its first condition.
710   bool candidateConditionMatches(const PredicateMatcher &Predicate) const;
711 };
712 
713 class SwitchMatcher : public Matcher {
714   /// All the nested matchers, representing distinct switch-cases. The first
715   /// conditions (as Matcher::getFirstCondition() reports) of all the nested
716   /// matchers must share the same type and path to a value they check, in other
717   /// words, be isIdenticalDownToValue, but have different values they check
718   /// against.
719   std::vector<Matcher *> Matchers;
720 
721   /// The representative condition, with a type and a path (InsnVarID and OpIdx
722   /// in most cases)  shared by all the matchers contained.
723   std::unique_ptr<PredicateMatcher> Condition = nullptr;
724 
725   /// Temporary set used to check that the case values don't repeat within the
726   /// same switch.
727   std::set<MatchTableRecord> Values;
728 
729   /// An owning collection for any auxiliary matchers created while optimizing
730   /// nested matchers contained.
731   std::vector<std::unique_ptr<Matcher>> MatcherStorage;
732 
733 public:
734   bool addMatcher(Matcher &Candidate);
735 
736   void finalize();
737   void emit(MatchTable &Table) override;
738 
matchers()739   iterator_range<std::vector<Matcher *>::iterator> matchers() {
740     return make_range(Matchers.begin(), Matchers.end());
741   }
size() const742   size_t size() const { return Matchers.size(); }
empty() const743   bool empty() const { return Matchers.empty(); }
744 
popFirstCondition()745   std::unique_ptr<PredicateMatcher> popFirstCondition() override {
746     // SwitchMatcher doesn't have a common first condition for its cases, as all
747     // the cases only share a kind of a value (a type and a path to it) they
748     // match, but deliberately differ in the actual value they match.
749     llvm_unreachable("Trying to pop a condition from a condition-less group");
750   }
getFirstCondition() const751   const PredicateMatcher &getFirstCondition() const override {
752     llvm_unreachable("Trying to pop a condition from a condition-less group");
753   }
hasFirstCondition() const754   bool hasFirstCondition() const override { return false; }
755 
756 private:
757   /// See if the predicate type has a Switch-implementation for it.
758   static bool isSupportedPredicateType(const PredicateMatcher &Predicate);
759 
760   bool candidateConditionMatches(const PredicateMatcher &Predicate) const;
761 
762   /// emit()-helper
763   static void emitPredicateSpecificOpcodes(const PredicateMatcher &P,
764                                            MatchTable &Table);
765 };
766 
767 /// Generates code to check that a match rule matches.
768 class RuleMatcher : public Matcher {
769 public:
770   using ActionList = std::list<std::unique_ptr<MatchAction>>;
771   using action_iterator = ActionList::iterator;
772 
773 protected:
774   /// A list of matchers that all need to succeed for the current rule to match.
775   /// FIXME: This currently supports a single match position but could be
776   /// extended to support multiple positions to support div/rem fusion or
777   /// load-multiple instructions.
778   using MatchersTy = std::vector<std::unique_ptr<InstructionMatcher>> ;
779   MatchersTy Matchers;
780 
781   /// A list of actions that need to be taken when all predicates in this rule
782   /// have succeeded.
783   ActionList Actions;
784 
785   using DefinedInsnVariablesMap = std::map<InstructionMatcher *, unsigned>;
786 
787   /// A map of instruction matchers to the local variables
788   DefinedInsnVariablesMap InsnVariableIDs;
789 
790   using MutatableInsnSet = SmallPtrSet<InstructionMatcher *, 4>;
791 
792   // The set of instruction matchers that have not yet been claimed for mutation
793   // by a BuildMI.
794   MutatableInsnSet MutatableInsns;
795 
796   /// A map of named operands defined by the matchers that may be referenced by
797   /// the renderers.
798   StringMap<OperandMatcher *> DefinedOperands;
799 
800   /// ID for the next instruction variable defined with implicitlyDefineInsnVar()
801   unsigned NextInsnVarID;
802 
803   /// ID for the next output instruction allocated with allocateOutputInsnID()
804   unsigned NextOutputInsnID;
805 
806   /// ID for the next temporary register ID allocated with allocateTempRegID()
807   unsigned NextTempRegID;
808 
809   std::vector<Record *> RequiredFeatures;
810   std::vector<std::unique_ptr<PredicateMatcher>> EpilogueMatchers;
811 
812   ArrayRef<SMLoc> SrcLoc;
813 
814   typedef std::tuple<Record *, unsigned, unsigned>
815       DefinedComplexPatternSubOperand;
816   typedef StringMap<DefinedComplexPatternSubOperand>
817       DefinedComplexPatternSubOperandMap;
818   /// A map of Symbolic Names to ComplexPattern sub-operands.
819   DefinedComplexPatternSubOperandMap ComplexSubOperands;
820 
821   uint64_t RuleID;
822   static uint64_t NextRuleID;
823 
824 public:
RuleMatcher(ArrayRef<SMLoc> SrcLoc)825   RuleMatcher(ArrayRef<SMLoc> SrcLoc)
826       : Matchers(), Actions(), InsnVariableIDs(), MutatableInsns(),
827         DefinedOperands(), NextInsnVarID(0), NextOutputInsnID(0),
828         NextTempRegID(0), SrcLoc(SrcLoc), ComplexSubOperands(),
829         RuleID(NextRuleID++) {}
830   RuleMatcher(RuleMatcher &&Other) = default;
831   RuleMatcher &operator=(RuleMatcher &&Other) = default;
832 
getRuleID() const833   uint64_t getRuleID() const { return RuleID; }
834 
835   InstructionMatcher &addInstructionMatcher(StringRef SymbolicName);
836   void addRequiredFeature(Record *Feature);
837   const std::vector<Record *> &getRequiredFeatures() const;
838 
839   template <class Kind, class... Args> Kind &addAction(Args &&... args);
840   template <class Kind, class... Args>
841   action_iterator insertAction(action_iterator InsertPt, Args &&... args);
842 
843   /// Define an instruction without emitting any code to do so.
844   unsigned implicitlyDefineInsnVar(InstructionMatcher &Matcher);
845 
846   unsigned getInsnVarID(InstructionMatcher &InsnMatcher) const;
defined_insn_vars_begin() const847   DefinedInsnVariablesMap::const_iterator defined_insn_vars_begin() const {
848     return InsnVariableIDs.begin();
849   }
defined_insn_vars_end() const850   DefinedInsnVariablesMap::const_iterator defined_insn_vars_end() const {
851     return InsnVariableIDs.end();
852   }
853   iterator_range<typename DefinedInsnVariablesMap::const_iterator>
defined_insn_vars() const854   defined_insn_vars() const {
855     return make_range(defined_insn_vars_begin(), defined_insn_vars_end());
856   }
857 
mutatable_insns_begin() const858   MutatableInsnSet::const_iterator mutatable_insns_begin() const {
859     return MutatableInsns.begin();
860   }
mutatable_insns_end() const861   MutatableInsnSet::const_iterator mutatable_insns_end() const {
862     return MutatableInsns.end();
863   }
864   iterator_range<typename MutatableInsnSet::const_iterator>
mutatable_insns() const865   mutatable_insns() const {
866     return make_range(mutatable_insns_begin(), mutatable_insns_end());
867   }
reserveInsnMatcherForMutation(InstructionMatcher * InsnMatcher)868   void reserveInsnMatcherForMutation(InstructionMatcher *InsnMatcher) {
869     bool R = MutatableInsns.erase(InsnMatcher);
870     assert(R && "Reserving a mutatable insn that isn't available");
871     (void)R;
872   }
873 
actions_begin()874   action_iterator actions_begin() { return Actions.begin(); }
actions_end()875   action_iterator actions_end() { return Actions.end(); }
actions()876   iterator_range<action_iterator> actions() {
877     return make_range(actions_begin(), actions_end());
878   }
879 
880   void defineOperand(StringRef SymbolicName, OperandMatcher &OM);
881 
defineComplexSubOperand(StringRef SymbolicName,Record * ComplexPattern,unsigned RendererID,unsigned SubOperandID)882   void defineComplexSubOperand(StringRef SymbolicName, Record *ComplexPattern,
883                                unsigned RendererID, unsigned SubOperandID) {
884     assert(ComplexSubOperands.count(SymbolicName) == 0 && "Already defined");
885     ComplexSubOperands[SymbolicName] =
886         std::make_tuple(ComplexPattern, RendererID, SubOperandID);
887   }
888   Optional<DefinedComplexPatternSubOperand>
getComplexSubOperand(StringRef SymbolicName) const889   getComplexSubOperand(StringRef SymbolicName) const {
890     const auto &I = ComplexSubOperands.find(SymbolicName);
891     if (I == ComplexSubOperands.end())
892       return None;
893     return I->second;
894   }
895 
896   InstructionMatcher &getInstructionMatcher(StringRef SymbolicName) const;
897   const OperandMatcher &getOperandMatcher(StringRef Name) const;
898 
899   void optimize() override;
900   void emit(MatchTable &Table) override;
901 
902   /// Compare the priority of this object and B.
903   ///
904   /// Returns true if this object is more important than B.
905   bool isHigherPriorityThan(const RuleMatcher &B) const;
906 
907   /// Report the maximum number of temporary operands needed by the rule
908   /// matcher.
909   unsigned countRendererFns() const;
910 
911   std::unique_ptr<PredicateMatcher> popFirstCondition() override;
912   const PredicateMatcher &getFirstCondition() const override;
913   LLTCodeGen getFirstConditionAsRootType();
914   bool hasFirstCondition() const override;
915   unsigned getNumOperands() const;
916   StringRef getOpcode() const;
917 
918   // FIXME: Remove this as soon as possible
insnmatchers_front() const919   InstructionMatcher &insnmatchers_front() const { return *Matchers.front(); }
920 
allocateOutputInsnID()921   unsigned allocateOutputInsnID() { return NextOutputInsnID++; }
allocateTempRegID()922   unsigned allocateTempRegID() { return NextTempRegID++; }
923 
insnmatchers()924   iterator_range<MatchersTy::iterator> insnmatchers() {
925     return make_range(Matchers.begin(), Matchers.end());
926   }
insnmatchers_empty() const927   bool insnmatchers_empty() const { return Matchers.empty(); }
insnmatchers_pop_front()928   void insnmatchers_pop_front() { Matchers.erase(Matchers.begin()); }
929 };
930 
931 uint64_t RuleMatcher::NextRuleID = 0;
932 
933 using action_iterator = RuleMatcher::action_iterator;
934 
935 template <class PredicateTy> class PredicateListMatcher {
936 private:
937   /// Template instantiations should specialize this to return a string to use
938   /// for the comment emitted when there are no predicates.
939   std::string getNoPredicateComment() const;
940 
941 protected:
942   using PredicatesTy = std::deque<std::unique_ptr<PredicateTy>>;
943   PredicatesTy Predicates;
944 
945   /// Track if the list of predicates was manipulated by one of the optimization
946   /// methods.
947   bool Optimized = false;
948 
949 public:
950   /// Construct a new predicate and add it to the matcher.
951   template <class Kind, class... Args>
952   Optional<Kind *> addPredicate(Args &&... args);
953 
predicates_begin()954   typename PredicatesTy::iterator predicates_begin() {
955     return Predicates.begin();
956   }
predicates_end()957   typename PredicatesTy::iterator predicates_end() {
958     return Predicates.end();
959   }
predicates()960   iterator_range<typename PredicatesTy::iterator> predicates() {
961     return make_range(predicates_begin(), predicates_end());
962   }
predicates_size() const963   typename PredicatesTy::size_type predicates_size() const {
964     return Predicates.size();
965   }
predicates_empty() const966   bool predicates_empty() const { return Predicates.empty(); }
967 
predicates_pop_front()968   std::unique_ptr<PredicateTy> predicates_pop_front() {
969     std::unique_ptr<PredicateTy> Front = std::move(Predicates.front());
970     Predicates.pop_front();
971     Optimized = true;
972     return Front;
973   }
974 
prependPredicate(std::unique_ptr<PredicateTy> && Predicate)975   void prependPredicate(std::unique_ptr<PredicateTy> &&Predicate) {
976     Predicates.push_front(std::move(Predicate));
977   }
978 
eraseNullPredicates()979   void eraseNullPredicates() {
980     const auto NewEnd =
981         std::stable_partition(Predicates.begin(), Predicates.end(),
982                               std::logical_not<std::unique_ptr<PredicateTy>>());
983     if (NewEnd != Predicates.begin()) {
984       Predicates.erase(Predicates.begin(), NewEnd);
985       Optimized = true;
986     }
987   }
988 
989   /// Emit MatchTable opcodes that tests whether all the predicates are met.
990   template <class... Args>
emitPredicateListOpcodes(MatchTable & Table,Args &&...args)991   void emitPredicateListOpcodes(MatchTable &Table, Args &&... args) {
992     if (Predicates.empty() && !Optimized) {
993       Table << MatchTable::Comment(getNoPredicateComment())
994             << MatchTable::LineBreak;
995       return;
996     }
997 
998     for (const auto &Predicate : predicates())
999       Predicate->emitPredicateOpcodes(Table, std::forward<Args>(args)...);
1000   }
1001 };
1002 
1003 class PredicateMatcher {
1004 public:
1005   /// This enum is used for RTTI and also defines the priority that is given to
1006   /// the predicate when generating the matcher code. Kinds with higher priority
1007   /// must be tested first.
1008   ///
1009   /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter
1010   /// but OPM_Int must have priority over OPM_RegBank since constant integers
1011   /// are represented by a virtual register defined by a G_CONSTANT instruction.
1012   ///
1013   /// Note: The relative priority between IPM_ and OPM_ does not matter, they
1014   /// are currently not compared between each other.
1015   enum PredicateKind {
1016     IPM_Opcode,
1017     IPM_NumOperands,
1018     IPM_ImmPredicate,
1019     IPM_AtomicOrderingMMO,
1020     IPM_MemoryLLTSize,
1021     IPM_MemoryVsLLTSize,
1022     IPM_GenericPredicate,
1023     OPM_SameOperand,
1024     OPM_ComplexPattern,
1025     OPM_IntrinsicID,
1026     OPM_Instruction,
1027     OPM_Int,
1028     OPM_LiteralInt,
1029     OPM_LLT,
1030     OPM_PointerToAny,
1031     OPM_RegBank,
1032     OPM_MBB,
1033   };
1034 
1035 protected:
1036   PredicateKind Kind;
1037   unsigned InsnVarID;
1038   unsigned OpIdx;
1039 
1040 public:
PredicateMatcher(PredicateKind Kind,unsigned InsnVarID,unsigned OpIdx=~0)1041   PredicateMatcher(PredicateKind Kind, unsigned InsnVarID, unsigned OpIdx = ~0)
1042       : Kind(Kind), InsnVarID(InsnVarID), OpIdx(OpIdx) {}
1043 
getInsnVarID() const1044   unsigned getInsnVarID() const { return InsnVarID; }
getOpIdx() const1045   unsigned getOpIdx() const { return OpIdx; }
1046 
1047   virtual ~PredicateMatcher() = default;
1048   /// Emit MatchTable opcodes that check the predicate for the given operand.
1049   virtual void emitPredicateOpcodes(MatchTable &Table,
1050                                     RuleMatcher &Rule) const = 0;
1051 
getKind() const1052   PredicateKind getKind() const { return Kind; }
1053 
isIdentical(const PredicateMatcher & B) const1054   virtual bool isIdentical(const PredicateMatcher &B) const {
1055     return B.getKind() == getKind() && InsnVarID == B.InsnVarID &&
1056            OpIdx == B.OpIdx;
1057   }
1058 
isIdenticalDownToValue(const PredicateMatcher & B) const1059   virtual bool isIdenticalDownToValue(const PredicateMatcher &B) const {
1060     return hasValue() && PredicateMatcher::isIdentical(B);
1061   }
1062 
getValue() const1063   virtual MatchTableRecord getValue() const {
1064     assert(hasValue() && "Can not get a value of a value-less predicate!");
1065     llvm_unreachable("Not implemented yet");
1066   }
hasValue() const1067   virtual bool hasValue() const { return false; }
1068 
1069   /// Report the maximum number of temporary operands needed by the predicate
1070   /// matcher.
countRendererFns() const1071   virtual unsigned countRendererFns() const { return 0; }
1072 };
1073 
1074 /// Generates code to check a predicate of an operand.
1075 ///
1076 /// Typical predicates include:
1077 /// * Operand is a particular register.
1078 /// * Operand is assigned a particular register bank.
1079 /// * Operand is an MBB.
1080 class OperandPredicateMatcher : public PredicateMatcher {
1081 public:
OperandPredicateMatcher(PredicateKind Kind,unsigned InsnVarID,unsigned OpIdx)1082   OperandPredicateMatcher(PredicateKind Kind, unsigned InsnVarID,
1083                           unsigned OpIdx)
1084       : PredicateMatcher(Kind, InsnVarID, OpIdx) {}
~OperandPredicateMatcher()1085   virtual ~OperandPredicateMatcher() {}
1086 
1087   /// Compare the priority of this object and B.
1088   ///
1089   /// Returns true if this object is more important than B.
1090   virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const;
1091 };
1092 
1093 template <>
1094 std::string
getNoPredicateComment() const1095 PredicateListMatcher<OperandPredicateMatcher>::getNoPredicateComment() const {
1096   return "No operand predicates";
1097 }
1098 
1099 /// Generates code to check that a register operand is defined by the same exact
1100 /// one as another.
1101 class SameOperandMatcher : public OperandPredicateMatcher {
1102   std::string MatchingName;
1103 
1104 public:
SameOperandMatcher(unsigned InsnVarID,unsigned OpIdx,StringRef MatchingName)1105   SameOperandMatcher(unsigned InsnVarID, unsigned OpIdx, StringRef MatchingName)
1106       : OperandPredicateMatcher(OPM_SameOperand, InsnVarID, OpIdx),
1107         MatchingName(MatchingName) {}
1108 
classof(const PredicateMatcher * P)1109   static bool classof(const PredicateMatcher *P) {
1110     return P->getKind() == OPM_SameOperand;
1111   }
1112 
1113   void emitPredicateOpcodes(MatchTable &Table,
1114                             RuleMatcher &Rule) const override;
1115 
isIdentical(const PredicateMatcher & B) const1116   bool isIdentical(const PredicateMatcher &B) const override {
1117     return OperandPredicateMatcher::isIdentical(B) &&
1118            MatchingName == cast<SameOperandMatcher>(&B)->MatchingName;
1119   }
1120 };
1121 
1122 /// Generates code to check that an operand is a particular LLT.
1123 class LLTOperandMatcher : public OperandPredicateMatcher {
1124 protected:
1125   LLTCodeGen Ty;
1126 
1127 public:
1128   static std::map<LLTCodeGen, unsigned> TypeIDValues;
1129 
initTypeIDValuesMap()1130   static void initTypeIDValuesMap() {
1131     TypeIDValues.clear();
1132 
1133     unsigned ID = 0;
1134     for (const LLTCodeGen LLTy : KnownTypes)
1135       TypeIDValues[LLTy] = ID++;
1136   }
1137 
LLTOperandMatcher(unsigned InsnVarID,unsigned OpIdx,const LLTCodeGen & Ty)1138   LLTOperandMatcher(unsigned InsnVarID, unsigned OpIdx, const LLTCodeGen &Ty)
1139       : OperandPredicateMatcher(OPM_LLT, InsnVarID, OpIdx), Ty(Ty) {
1140     KnownTypes.insert(Ty);
1141   }
1142 
classof(const PredicateMatcher * P)1143   static bool classof(const PredicateMatcher *P) {
1144     return P->getKind() == OPM_LLT;
1145   }
isIdentical(const PredicateMatcher & B) const1146   bool isIdentical(const PredicateMatcher &B) const override {
1147     return OperandPredicateMatcher::isIdentical(B) &&
1148            Ty == cast<LLTOperandMatcher>(&B)->Ty;
1149   }
getValue() const1150   MatchTableRecord getValue() const override {
1151     const auto VI = TypeIDValues.find(Ty);
1152     if (VI == TypeIDValues.end())
1153       return MatchTable::NamedValue(getTy().getCxxEnumValue());
1154     return MatchTable::NamedValue(getTy().getCxxEnumValue(), VI->second);
1155   }
hasValue() const1156   bool hasValue() const override {
1157     if (TypeIDValues.size() != KnownTypes.size())
1158       initTypeIDValuesMap();
1159     return TypeIDValues.count(Ty);
1160   }
1161 
getTy() const1162   LLTCodeGen getTy() const { return Ty; }
1163 
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1164   void emitPredicateOpcodes(MatchTable &Table,
1165                             RuleMatcher &Rule) const override {
1166     Table << MatchTable::Opcode("GIM_CheckType") << MatchTable::Comment("MI")
1167           << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
1168           << MatchTable::IntValue(OpIdx) << MatchTable::Comment("Type")
1169           << getValue() << MatchTable::LineBreak;
1170   }
1171 };
1172 
1173 std::map<LLTCodeGen, unsigned> LLTOperandMatcher::TypeIDValues;
1174 
1175 /// Generates code to check that an operand is a pointer to any address space.
1176 ///
1177 /// In SelectionDAG, the types did not describe pointers or address spaces. As a
1178 /// result, iN is used to describe a pointer of N bits to any address space and
1179 /// PatFrag predicates are typically used to constrain the address space. There's
1180 /// no reliable means to derive the missing type information from the pattern so
1181 /// imported rules must test the components of a pointer separately.
1182 ///
1183 /// If SizeInBits is zero, then the pointer size will be obtained from the
1184 /// subtarget.
1185 class PointerToAnyOperandMatcher : public OperandPredicateMatcher {
1186 protected:
1187   unsigned SizeInBits;
1188 
1189 public:
PointerToAnyOperandMatcher(unsigned InsnVarID,unsigned OpIdx,unsigned SizeInBits)1190   PointerToAnyOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1191                              unsigned SizeInBits)
1192       : OperandPredicateMatcher(OPM_PointerToAny, InsnVarID, OpIdx),
1193         SizeInBits(SizeInBits) {}
1194 
classof(const OperandPredicateMatcher * P)1195   static bool classof(const OperandPredicateMatcher *P) {
1196     return P->getKind() == OPM_PointerToAny;
1197   }
1198 
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1199   void emitPredicateOpcodes(MatchTable &Table,
1200                             RuleMatcher &Rule) const override {
1201     Table << MatchTable::Opcode("GIM_CheckPointerToAny")
1202           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1203           << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1204           << MatchTable::Comment("SizeInBits")
1205           << MatchTable::IntValue(SizeInBits) << MatchTable::LineBreak;
1206   }
1207 };
1208 
1209 /// Generates code to check that an operand is a particular target constant.
1210 class ComplexPatternOperandMatcher : public OperandPredicateMatcher {
1211 protected:
1212   const OperandMatcher &Operand;
1213   const Record &TheDef;
1214 
1215   unsigned getAllocatedTemporariesBaseID() const;
1216 
1217 public:
isIdentical(const PredicateMatcher & B) const1218   bool isIdentical(const PredicateMatcher &B) const override { return false; }
1219 
ComplexPatternOperandMatcher(unsigned InsnVarID,unsigned OpIdx,const OperandMatcher & Operand,const Record & TheDef)1220   ComplexPatternOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1221                                const OperandMatcher &Operand,
1222                                const Record &TheDef)
1223       : OperandPredicateMatcher(OPM_ComplexPattern, InsnVarID, OpIdx),
1224         Operand(Operand), TheDef(TheDef) {}
1225 
classof(const PredicateMatcher * P)1226   static bool classof(const PredicateMatcher *P) {
1227     return P->getKind() == OPM_ComplexPattern;
1228   }
1229 
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1230   void emitPredicateOpcodes(MatchTable &Table,
1231                             RuleMatcher &Rule) const override {
1232     unsigned ID = getAllocatedTemporariesBaseID();
1233     Table << MatchTable::Opcode("GIM_CheckComplexPattern")
1234           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1235           << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1236           << MatchTable::Comment("Renderer") << MatchTable::IntValue(ID)
1237           << MatchTable::NamedValue(("GICP_" + TheDef.getName()).str())
1238           << MatchTable::LineBreak;
1239   }
1240 
countRendererFns() const1241   unsigned countRendererFns() const override {
1242     return 1;
1243   }
1244 };
1245 
1246 /// Generates code to check that an operand is in a particular register bank.
1247 class RegisterBankOperandMatcher : public OperandPredicateMatcher {
1248 protected:
1249   const CodeGenRegisterClass &RC;
1250 
1251 public:
RegisterBankOperandMatcher(unsigned InsnVarID,unsigned OpIdx,const CodeGenRegisterClass & RC)1252   RegisterBankOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1253                              const CodeGenRegisterClass &RC)
1254       : OperandPredicateMatcher(OPM_RegBank, InsnVarID, OpIdx), RC(RC) {}
1255 
isIdentical(const PredicateMatcher & B) const1256   bool isIdentical(const PredicateMatcher &B) const override {
1257     return OperandPredicateMatcher::isIdentical(B) &&
1258            RC.getDef() == cast<RegisterBankOperandMatcher>(&B)->RC.getDef();
1259   }
1260 
classof(const PredicateMatcher * P)1261   static bool classof(const PredicateMatcher *P) {
1262     return P->getKind() == OPM_RegBank;
1263   }
1264 
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1265   void emitPredicateOpcodes(MatchTable &Table,
1266                             RuleMatcher &Rule) const override {
1267     Table << MatchTable::Opcode("GIM_CheckRegBankForClass")
1268           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1269           << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1270           << MatchTable::Comment("RC")
1271           << MatchTable::NamedValue(RC.getQualifiedName() + "RegClassID")
1272           << MatchTable::LineBreak;
1273   }
1274 };
1275 
1276 /// Generates code to check that an operand is a basic block.
1277 class MBBOperandMatcher : public OperandPredicateMatcher {
1278 public:
MBBOperandMatcher(unsigned InsnVarID,unsigned OpIdx)1279   MBBOperandMatcher(unsigned InsnVarID, unsigned OpIdx)
1280       : OperandPredicateMatcher(OPM_MBB, InsnVarID, OpIdx) {}
1281 
classof(const PredicateMatcher * P)1282   static bool classof(const PredicateMatcher *P) {
1283     return P->getKind() == OPM_MBB;
1284   }
1285 
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1286   void emitPredicateOpcodes(MatchTable &Table,
1287                             RuleMatcher &Rule) const override {
1288     Table << MatchTable::Opcode("GIM_CheckIsMBB") << MatchTable::Comment("MI")
1289           << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
1290           << MatchTable::IntValue(OpIdx) << MatchTable::LineBreak;
1291   }
1292 };
1293 
1294 /// Generates code to check that an operand is a G_CONSTANT with a particular
1295 /// int.
1296 class ConstantIntOperandMatcher : public OperandPredicateMatcher {
1297 protected:
1298   int64_t Value;
1299 
1300 public:
ConstantIntOperandMatcher(unsigned InsnVarID,unsigned OpIdx,int64_t Value)1301   ConstantIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value)
1302       : OperandPredicateMatcher(OPM_Int, InsnVarID, OpIdx), Value(Value) {}
1303 
isIdentical(const PredicateMatcher & B) const1304   bool isIdentical(const PredicateMatcher &B) const override {
1305     return OperandPredicateMatcher::isIdentical(B) &&
1306            Value == cast<ConstantIntOperandMatcher>(&B)->Value;
1307   }
1308 
classof(const PredicateMatcher * P)1309   static bool classof(const PredicateMatcher *P) {
1310     return P->getKind() == OPM_Int;
1311   }
1312 
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1313   void emitPredicateOpcodes(MatchTable &Table,
1314                             RuleMatcher &Rule) const override {
1315     Table << MatchTable::Opcode("GIM_CheckConstantInt")
1316           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1317           << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1318           << MatchTable::IntValue(Value) << MatchTable::LineBreak;
1319   }
1320 };
1321 
1322 /// Generates code to check that an operand is a raw int (where MO.isImm() or
1323 /// MO.isCImm() is true).
1324 class LiteralIntOperandMatcher : public OperandPredicateMatcher {
1325 protected:
1326   int64_t Value;
1327 
1328 public:
LiteralIntOperandMatcher(unsigned InsnVarID,unsigned OpIdx,int64_t Value)1329   LiteralIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value)
1330       : OperandPredicateMatcher(OPM_LiteralInt, InsnVarID, OpIdx),
1331         Value(Value) {}
1332 
isIdentical(const PredicateMatcher & B) const1333   bool isIdentical(const PredicateMatcher &B) const override {
1334     return OperandPredicateMatcher::isIdentical(B) &&
1335            Value == cast<LiteralIntOperandMatcher>(&B)->Value;
1336   }
1337 
classof(const PredicateMatcher * P)1338   static bool classof(const PredicateMatcher *P) {
1339     return P->getKind() == OPM_LiteralInt;
1340   }
1341 
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1342   void emitPredicateOpcodes(MatchTable &Table,
1343                             RuleMatcher &Rule) const override {
1344     Table << MatchTable::Opcode("GIM_CheckLiteralInt")
1345           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1346           << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1347           << MatchTable::IntValue(Value) << MatchTable::LineBreak;
1348   }
1349 };
1350 
1351 /// Generates code to check that an operand is an intrinsic ID.
1352 class IntrinsicIDOperandMatcher : public OperandPredicateMatcher {
1353 protected:
1354   const CodeGenIntrinsic *II;
1355 
1356 public:
IntrinsicIDOperandMatcher(unsigned InsnVarID,unsigned OpIdx,const CodeGenIntrinsic * II)1357   IntrinsicIDOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1358                             const CodeGenIntrinsic *II)
1359       : OperandPredicateMatcher(OPM_IntrinsicID, InsnVarID, OpIdx), II(II) {}
1360 
isIdentical(const PredicateMatcher & B) const1361   bool isIdentical(const PredicateMatcher &B) const override {
1362     return OperandPredicateMatcher::isIdentical(B) &&
1363            II == cast<IntrinsicIDOperandMatcher>(&B)->II;
1364   }
1365 
classof(const PredicateMatcher * P)1366   static bool classof(const PredicateMatcher *P) {
1367     return P->getKind() == OPM_IntrinsicID;
1368   }
1369 
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1370   void emitPredicateOpcodes(MatchTable &Table,
1371                             RuleMatcher &Rule) const override {
1372     Table << MatchTable::Opcode("GIM_CheckIntrinsicID")
1373           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1374           << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
1375           << MatchTable::NamedValue("Intrinsic::" + II->EnumName)
1376           << MatchTable::LineBreak;
1377   }
1378 };
1379 
1380 /// Generates code to check that a set of predicates match for a particular
1381 /// operand.
1382 class OperandMatcher : public PredicateListMatcher<OperandPredicateMatcher> {
1383 protected:
1384   InstructionMatcher &Insn;
1385   unsigned OpIdx;
1386   std::string SymbolicName;
1387 
1388   /// The index of the first temporary variable allocated to this operand. The
1389   /// number of allocated temporaries can be found with
1390   /// countRendererFns().
1391   unsigned AllocatedTemporariesBaseID;
1392 
1393 public:
OperandMatcher(InstructionMatcher & Insn,unsigned OpIdx,const std::string & SymbolicName,unsigned AllocatedTemporariesBaseID)1394   OperandMatcher(InstructionMatcher &Insn, unsigned OpIdx,
1395                  const std::string &SymbolicName,
1396                  unsigned AllocatedTemporariesBaseID)
1397       : Insn(Insn), OpIdx(OpIdx), SymbolicName(SymbolicName),
1398         AllocatedTemporariesBaseID(AllocatedTemporariesBaseID) {}
1399 
hasSymbolicName() const1400   bool hasSymbolicName() const { return !SymbolicName.empty(); }
getSymbolicName() const1401   const StringRef getSymbolicName() const { return SymbolicName; }
setSymbolicName(StringRef Name)1402   void setSymbolicName(StringRef Name) {
1403     assert(SymbolicName.empty() && "Operand already has a symbolic name");
1404     SymbolicName = Name;
1405   }
1406 
1407   /// Construct a new operand predicate and add it to the matcher.
1408   template <class Kind, class... Args>
addPredicate(Args &&...args)1409   Optional<Kind *> addPredicate(Args &&... args) {
1410     if (isSameAsAnotherOperand())
1411       return None;
1412     Predicates.emplace_back(llvm::make_unique<Kind>(
1413         getInsnVarID(), getOpIdx(), std::forward<Args>(args)...));
1414     return static_cast<Kind *>(Predicates.back().get());
1415   }
1416 
getOpIdx() const1417   unsigned getOpIdx() const { return OpIdx; }
1418   unsigned getInsnVarID() const;
1419 
getOperandExpr(unsigned InsnVarID) const1420   std::string getOperandExpr(unsigned InsnVarID) const {
1421     return "State.MIs[" + llvm::to_string(InsnVarID) + "]->getOperand(" +
1422            llvm::to_string(OpIdx) + ")";
1423   }
1424 
getInstructionMatcher() const1425   InstructionMatcher &getInstructionMatcher() const { return Insn; }
1426 
1427   Error addTypeCheckPredicate(const TypeSetByHwMode &VTy,
1428                               bool OperandIsAPointer);
1429 
1430   /// Emit MatchTable opcodes that test whether the instruction named in
1431   /// InsnVarID matches all the predicates and all the operands.
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule)1432   void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) {
1433     if (!Optimized) {
1434       std::string Comment;
1435       raw_string_ostream CommentOS(Comment);
1436       CommentOS << "MIs[" << getInsnVarID() << "] ";
1437       if (SymbolicName.empty())
1438         CommentOS << "Operand " << OpIdx;
1439       else
1440         CommentOS << SymbolicName;
1441       Table << MatchTable::Comment(CommentOS.str()) << MatchTable::LineBreak;
1442     }
1443 
1444     emitPredicateListOpcodes(Table, Rule);
1445   }
1446 
1447   /// Compare the priority of this object and B.
1448   ///
1449   /// Returns true if this object is more important than B.
isHigherPriorityThan(OperandMatcher & B)1450   bool isHigherPriorityThan(OperandMatcher &B) {
1451     // Operand matchers involving more predicates have higher priority.
1452     if (predicates_size() > B.predicates_size())
1453       return true;
1454     if (predicates_size() < B.predicates_size())
1455       return false;
1456 
1457     // This assumes that predicates are added in a consistent order.
1458     for (auto &&Predicate : zip(predicates(), B.predicates())) {
1459       if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate)))
1460         return true;
1461       if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate)))
1462         return false;
1463     }
1464 
1465     return false;
1466   };
1467 
1468   /// Report the maximum number of temporary operands needed by the operand
1469   /// matcher.
countRendererFns()1470   unsigned countRendererFns() {
1471     return std::accumulate(
1472         predicates().begin(), predicates().end(), 0,
1473         [](unsigned A,
1474            const std::unique_ptr<OperandPredicateMatcher> &Predicate) {
1475           return A + Predicate->countRendererFns();
1476         });
1477   }
1478 
getAllocatedTemporariesBaseID() const1479   unsigned getAllocatedTemporariesBaseID() const {
1480     return AllocatedTemporariesBaseID;
1481   }
1482 
isSameAsAnotherOperand()1483   bool isSameAsAnotherOperand() {
1484     for (const auto &Predicate : predicates())
1485       if (isa<SameOperandMatcher>(Predicate))
1486         return true;
1487     return false;
1488   }
1489 };
1490 
addTypeCheckPredicate(const TypeSetByHwMode & VTy,bool OperandIsAPointer)1491 Error OperandMatcher::addTypeCheckPredicate(const TypeSetByHwMode &VTy,
1492                                             bool OperandIsAPointer) {
1493   if (!VTy.isMachineValueType())
1494     return failedImport("unsupported typeset");
1495 
1496   if (VTy.getMachineValueType() == MVT::iPTR && OperandIsAPointer) {
1497     addPredicate<PointerToAnyOperandMatcher>(0);
1498     return Error::success();
1499   }
1500 
1501   auto OpTyOrNone = MVTToLLT(VTy.getMachineValueType().SimpleTy);
1502   if (!OpTyOrNone)
1503     return failedImport("unsupported type");
1504 
1505   if (OperandIsAPointer)
1506     addPredicate<PointerToAnyOperandMatcher>(OpTyOrNone->get().getSizeInBits());
1507   else
1508     addPredicate<LLTOperandMatcher>(*OpTyOrNone);
1509   return Error::success();
1510 }
1511 
getAllocatedTemporariesBaseID() const1512 unsigned ComplexPatternOperandMatcher::getAllocatedTemporariesBaseID() const {
1513   return Operand.getAllocatedTemporariesBaseID();
1514 }
1515 
1516 /// Generates code to check a predicate on an instruction.
1517 ///
1518 /// Typical predicates include:
1519 /// * The opcode of the instruction is a particular value.
1520 /// * The nsw/nuw flag is/isn't set.
1521 class InstructionPredicateMatcher : public PredicateMatcher {
1522 public:
InstructionPredicateMatcher(PredicateKind Kind,unsigned InsnVarID)1523   InstructionPredicateMatcher(PredicateKind Kind, unsigned InsnVarID)
1524       : PredicateMatcher(Kind, InsnVarID) {}
~InstructionPredicateMatcher()1525   virtual ~InstructionPredicateMatcher() {}
1526 
1527   /// Compare the priority of this object and B.
1528   ///
1529   /// Returns true if this object is more important than B.
1530   virtual bool
isHigherPriorityThan(const InstructionPredicateMatcher & B) const1531   isHigherPriorityThan(const InstructionPredicateMatcher &B) const {
1532     return Kind < B.Kind;
1533   };
1534 };
1535 
1536 template <>
1537 std::string
getNoPredicateComment() const1538 PredicateListMatcher<PredicateMatcher>::getNoPredicateComment() const {
1539   return "No instruction predicates";
1540 }
1541 
1542 /// Generates code to check the opcode of an instruction.
1543 class InstructionOpcodeMatcher : public InstructionPredicateMatcher {
1544 protected:
1545   const CodeGenInstruction *I;
1546 
1547   static DenseMap<const CodeGenInstruction *, unsigned> OpcodeValues;
1548 
1549 public:
initOpcodeValuesMap(const CodeGenTarget & Target)1550   static void initOpcodeValuesMap(const CodeGenTarget &Target) {
1551     OpcodeValues.clear();
1552 
1553     unsigned OpcodeValue = 0;
1554     for (const CodeGenInstruction *I : Target.getInstructionsByEnumValue())
1555       OpcodeValues[I] = OpcodeValue++;
1556   }
1557 
InstructionOpcodeMatcher(unsigned InsnVarID,const CodeGenInstruction * I)1558   InstructionOpcodeMatcher(unsigned InsnVarID, const CodeGenInstruction *I)
1559       : InstructionPredicateMatcher(IPM_Opcode, InsnVarID), I(I) {}
1560 
classof(const PredicateMatcher * P)1561   static bool classof(const PredicateMatcher *P) {
1562     return P->getKind() == IPM_Opcode;
1563   }
1564 
isIdentical(const PredicateMatcher & B) const1565   bool isIdentical(const PredicateMatcher &B) const override {
1566     return InstructionPredicateMatcher::isIdentical(B) &&
1567            I == cast<InstructionOpcodeMatcher>(&B)->I;
1568   }
getValue() const1569   MatchTableRecord getValue() const override {
1570     const auto VI = OpcodeValues.find(I);
1571     if (VI != OpcodeValues.end())
1572       return MatchTable::NamedValue(I->Namespace, I->TheDef->getName(),
1573                                     VI->second);
1574     return MatchTable::NamedValue(I->Namespace, I->TheDef->getName());
1575   }
hasValue() const1576   bool hasValue() const override { return OpcodeValues.count(I); }
1577 
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1578   void emitPredicateOpcodes(MatchTable &Table,
1579                             RuleMatcher &Rule) const override {
1580     Table << MatchTable::Opcode("GIM_CheckOpcode") << MatchTable::Comment("MI")
1581           << MatchTable::IntValue(InsnVarID) << getValue()
1582           << MatchTable::LineBreak;
1583   }
1584 
1585   /// Compare the priority of this object and B.
1586   ///
1587   /// Returns true if this object is more important than B.
1588   bool
isHigherPriorityThan(const InstructionPredicateMatcher & B) const1589   isHigherPriorityThan(const InstructionPredicateMatcher &B) const override {
1590     if (InstructionPredicateMatcher::isHigherPriorityThan(B))
1591       return true;
1592     if (B.InstructionPredicateMatcher::isHigherPriorityThan(*this))
1593       return false;
1594 
1595     // Prioritize opcodes for cosmetic reasons in the generated source. Although
1596     // this is cosmetic at the moment, we may want to drive a similar ordering
1597     // using instruction frequency information to improve compile time.
1598     if (const InstructionOpcodeMatcher *BO =
1599             dyn_cast<InstructionOpcodeMatcher>(&B))
1600       return I->TheDef->getName() < BO->I->TheDef->getName();
1601 
1602     return false;
1603   };
1604 
isConstantInstruction() const1605   bool isConstantInstruction() const {
1606     return I->TheDef->getName() == "G_CONSTANT";
1607   }
1608 
getOpcode() const1609   StringRef getOpcode() const { return I->TheDef->getName(); }
getNumOperands() const1610   unsigned getNumOperands() const { return I->Operands.size(); }
1611 
getOperandType(unsigned OpIdx) const1612   StringRef getOperandType(unsigned OpIdx) const {
1613     return I->Operands[OpIdx].OperandType;
1614   }
1615 };
1616 
1617 DenseMap<const CodeGenInstruction *, unsigned>
1618     InstructionOpcodeMatcher::OpcodeValues;
1619 
1620 class InstructionNumOperandsMatcher final : public InstructionPredicateMatcher {
1621   unsigned NumOperands = 0;
1622 
1623 public:
InstructionNumOperandsMatcher(unsigned InsnVarID,unsigned NumOperands)1624   InstructionNumOperandsMatcher(unsigned InsnVarID, unsigned NumOperands)
1625       : InstructionPredicateMatcher(IPM_NumOperands, InsnVarID),
1626         NumOperands(NumOperands) {}
1627 
classof(const PredicateMatcher * P)1628   static bool classof(const PredicateMatcher *P) {
1629     return P->getKind() == IPM_NumOperands;
1630   }
1631 
isIdentical(const PredicateMatcher & B) const1632   bool isIdentical(const PredicateMatcher &B) const override {
1633     return InstructionPredicateMatcher::isIdentical(B) &&
1634            NumOperands == cast<InstructionNumOperandsMatcher>(&B)->NumOperands;
1635   }
1636 
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1637   void emitPredicateOpcodes(MatchTable &Table,
1638                             RuleMatcher &Rule) const override {
1639     Table << MatchTable::Opcode("GIM_CheckNumOperands")
1640           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1641           << MatchTable::Comment("Expected")
1642           << MatchTable::IntValue(NumOperands) << MatchTable::LineBreak;
1643   }
1644 };
1645 
1646 /// Generates code to check that this instruction is a constant whose value
1647 /// meets an immediate predicate.
1648 ///
1649 /// Immediates are slightly odd since they are typically used like an operand
1650 /// but are represented as an operator internally. We typically write simm8:$src
1651 /// in a tablegen pattern, but this is just syntactic sugar for
1652 /// (imm:i32)<<P:Predicate_simm8>>:$imm which more directly describes the nodes
1653 /// that will be matched and the predicate (which is attached to the imm
1654 /// operator) that will be tested. In SelectionDAG this describes a
1655 /// ConstantSDNode whose internal value will be tested using the simm8 predicate.
1656 ///
1657 /// The corresponding GlobalISel representation is %1 = G_CONSTANT iN Value. In
1658 /// this representation, the immediate could be tested with an
1659 /// InstructionMatcher, InstructionOpcodeMatcher, OperandMatcher, and a
1660 /// OperandPredicateMatcher-subclass to check the Value meets the predicate but
1661 /// there are two implementation issues with producing that matcher
1662 /// configuration from the SelectionDAG pattern:
1663 /// * ImmLeaf is a PatFrag whose root is an InstructionMatcher. This means that
1664 ///   were we to sink the immediate predicate to the operand we would have to
1665 ///   have two partial implementations of PatFrag support, one for immediates
1666 ///   and one for non-immediates.
1667 /// * At the point we handle the predicate, the OperandMatcher hasn't been
1668 ///   created yet. If we were to sink the predicate to the OperandMatcher we
1669 ///   would also have to complicate (or duplicate) the code that descends and
1670 ///   creates matchers for the subtree.
1671 /// Overall, it's simpler to handle it in the place it was found.
1672 class InstructionImmPredicateMatcher : public InstructionPredicateMatcher {
1673 protected:
1674   TreePredicateFn Predicate;
1675 
1676 public:
InstructionImmPredicateMatcher(unsigned InsnVarID,const TreePredicateFn & Predicate)1677   InstructionImmPredicateMatcher(unsigned InsnVarID,
1678                                  const TreePredicateFn &Predicate)
1679       : InstructionPredicateMatcher(IPM_ImmPredicate, InsnVarID),
1680         Predicate(Predicate) {}
1681 
isIdentical(const PredicateMatcher & B) const1682   bool isIdentical(const PredicateMatcher &B) const override {
1683     return InstructionPredicateMatcher::isIdentical(B) &&
1684            Predicate.getOrigPatFragRecord() ==
1685                cast<InstructionImmPredicateMatcher>(&B)
1686                    ->Predicate.getOrigPatFragRecord();
1687   }
1688 
classof(const PredicateMatcher * P)1689   static bool classof(const PredicateMatcher *P) {
1690     return P->getKind() == IPM_ImmPredicate;
1691   }
1692 
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1693   void emitPredicateOpcodes(MatchTable &Table,
1694                             RuleMatcher &Rule) const override {
1695     Table << MatchTable::Opcode(getMatchOpcodeForPredicate(Predicate))
1696           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1697           << MatchTable::Comment("Predicate")
1698           << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
1699           << MatchTable::LineBreak;
1700   }
1701 };
1702 
1703 /// Generates code to check that a memory instruction has a atomic ordering
1704 /// MachineMemoryOperand.
1705 class AtomicOrderingMMOPredicateMatcher : public InstructionPredicateMatcher {
1706 public:
1707   enum AOComparator {
1708     AO_Exactly,
1709     AO_OrStronger,
1710     AO_WeakerThan,
1711   };
1712 
1713 protected:
1714   StringRef Order;
1715   AOComparator Comparator;
1716 
1717 public:
AtomicOrderingMMOPredicateMatcher(unsigned InsnVarID,StringRef Order,AOComparator Comparator=AO_Exactly)1718   AtomicOrderingMMOPredicateMatcher(unsigned InsnVarID, StringRef Order,
1719                                     AOComparator Comparator = AO_Exactly)
1720       : InstructionPredicateMatcher(IPM_AtomicOrderingMMO, InsnVarID),
1721         Order(Order), Comparator(Comparator) {}
1722 
classof(const PredicateMatcher * P)1723   static bool classof(const PredicateMatcher *P) {
1724     return P->getKind() == IPM_AtomicOrderingMMO;
1725   }
1726 
isIdentical(const PredicateMatcher & B) const1727   bool isIdentical(const PredicateMatcher &B) const override {
1728     if (!InstructionPredicateMatcher::isIdentical(B))
1729       return false;
1730     const auto &R = *cast<AtomicOrderingMMOPredicateMatcher>(&B);
1731     return Order == R.Order && Comparator == R.Comparator;
1732   }
1733 
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1734   void emitPredicateOpcodes(MatchTable &Table,
1735                             RuleMatcher &Rule) const override {
1736     StringRef Opcode = "GIM_CheckAtomicOrdering";
1737 
1738     if (Comparator == AO_OrStronger)
1739       Opcode = "GIM_CheckAtomicOrderingOrStrongerThan";
1740     if (Comparator == AO_WeakerThan)
1741       Opcode = "GIM_CheckAtomicOrderingWeakerThan";
1742 
1743     Table << MatchTable::Opcode(Opcode) << MatchTable::Comment("MI")
1744           << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Order")
1745           << MatchTable::NamedValue(("(int64_t)AtomicOrdering::" + Order).str())
1746           << MatchTable::LineBreak;
1747   }
1748 };
1749 
1750 /// Generates code to check that the size of an MMO is exactly N bytes.
1751 class MemorySizePredicateMatcher : public InstructionPredicateMatcher {
1752 protected:
1753   unsigned MMOIdx;
1754   uint64_t Size;
1755 
1756 public:
MemorySizePredicateMatcher(unsigned InsnVarID,unsigned MMOIdx,unsigned Size)1757   MemorySizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, unsigned Size)
1758       : InstructionPredicateMatcher(IPM_MemoryLLTSize, InsnVarID),
1759         MMOIdx(MMOIdx), Size(Size) {}
1760 
classof(const PredicateMatcher * P)1761   static bool classof(const PredicateMatcher *P) {
1762     return P->getKind() == IPM_MemoryLLTSize;
1763   }
isIdentical(const PredicateMatcher & B) const1764   bool isIdentical(const PredicateMatcher &B) const override {
1765     return InstructionPredicateMatcher::isIdentical(B) &&
1766            MMOIdx == cast<MemorySizePredicateMatcher>(&B)->MMOIdx &&
1767            Size == cast<MemorySizePredicateMatcher>(&B)->Size;
1768   }
1769 
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1770   void emitPredicateOpcodes(MatchTable &Table,
1771                             RuleMatcher &Rule) const override {
1772     Table << MatchTable::Opcode("GIM_CheckMemorySizeEqualTo")
1773           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1774           << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
1775           << MatchTable::Comment("Size") << MatchTable::IntValue(Size)
1776           << MatchTable::LineBreak;
1777   }
1778 };
1779 
1780 /// Generates code to check that the size of an MMO is less-than, equal-to, or
1781 /// greater than a given LLT.
1782 class MemoryVsLLTSizePredicateMatcher : public InstructionPredicateMatcher {
1783 public:
1784   enum RelationKind {
1785     GreaterThan,
1786     EqualTo,
1787     LessThan,
1788   };
1789 
1790 protected:
1791   unsigned MMOIdx;
1792   RelationKind Relation;
1793   unsigned OpIdx;
1794 
1795 public:
MemoryVsLLTSizePredicateMatcher(unsigned InsnVarID,unsigned MMOIdx,enum RelationKind Relation,unsigned OpIdx)1796   MemoryVsLLTSizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
1797                                   enum RelationKind Relation,
1798                                   unsigned OpIdx)
1799       : InstructionPredicateMatcher(IPM_MemoryVsLLTSize, InsnVarID),
1800         MMOIdx(MMOIdx), Relation(Relation), OpIdx(OpIdx) {}
1801 
classof(const PredicateMatcher * P)1802   static bool classof(const PredicateMatcher *P) {
1803     return P->getKind() == IPM_MemoryVsLLTSize;
1804   }
isIdentical(const PredicateMatcher & B) const1805   bool isIdentical(const PredicateMatcher &B) const override {
1806     return InstructionPredicateMatcher::isIdentical(B) &&
1807            MMOIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->MMOIdx &&
1808            Relation == cast<MemoryVsLLTSizePredicateMatcher>(&B)->Relation &&
1809            OpIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->OpIdx;
1810   }
1811 
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1812   void emitPredicateOpcodes(MatchTable &Table,
1813                             RuleMatcher &Rule) const override {
1814     Table << MatchTable::Opcode(Relation == EqualTo
1815                                     ? "GIM_CheckMemorySizeEqualToLLT"
1816                                     : Relation == GreaterThan
1817                                           ? "GIM_CheckMemorySizeGreaterThanLLT"
1818                                           : "GIM_CheckMemorySizeLessThanLLT")
1819           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1820           << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx)
1821           << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx)
1822           << MatchTable::LineBreak;
1823   }
1824 };
1825 
1826 /// Generates code to check an arbitrary C++ instruction predicate.
1827 class GenericInstructionPredicateMatcher : public InstructionPredicateMatcher {
1828 protected:
1829   TreePredicateFn Predicate;
1830 
1831 public:
GenericInstructionPredicateMatcher(unsigned InsnVarID,TreePredicateFn Predicate)1832   GenericInstructionPredicateMatcher(unsigned InsnVarID,
1833                                      TreePredicateFn Predicate)
1834       : InstructionPredicateMatcher(IPM_GenericPredicate, InsnVarID),
1835         Predicate(Predicate) {}
1836 
classof(const InstructionPredicateMatcher * P)1837   static bool classof(const InstructionPredicateMatcher *P) {
1838     return P->getKind() == IPM_GenericPredicate;
1839   }
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1840   void emitPredicateOpcodes(MatchTable &Table,
1841                             RuleMatcher &Rule) const override {
1842     Table << MatchTable::Opcode("GIM_CheckCxxInsnPredicate")
1843           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
1844           << MatchTable::Comment("FnId")
1845           << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
1846           << MatchTable::LineBreak;
1847   }
1848 };
1849 
1850 /// Generates code to check that a set of predicates and operands match for a
1851 /// particular instruction.
1852 ///
1853 /// Typical predicates include:
1854 /// * Has a specific opcode.
1855 /// * Has an nsw/nuw flag or doesn't.
1856 class InstructionMatcher final : public PredicateListMatcher<PredicateMatcher> {
1857 protected:
1858   typedef std::vector<std::unique_ptr<OperandMatcher>> OperandVec;
1859 
1860   RuleMatcher &Rule;
1861 
1862   /// The operands to match. All rendered operands must be present even if the
1863   /// condition is always true.
1864   OperandVec Operands;
1865   bool NumOperandsCheck = true;
1866 
1867   std::string SymbolicName;
1868   unsigned InsnVarID;
1869 
1870 public:
InstructionMatcher(RuleMatcher & Rule,StringRef SymbolicName)1871   InstructionMatcher(RuleMatcher &Rule, StringRef SymbolicName)
1872       : Rule(Rule), SymbolicName(SymbolicName) {
1873     // We create a new instruction matcher.
1874     // Get a new ID for that instruction.
1875     InsnVarID = Rule.implicitlyDefineInsnVar(*this);
1876   }
1877 
1878   /// Construct a new instruction predicate and add it to the matcher.
1879   template <class Kind, class... Args>
addPredicate(Args &&...args)1880   Optional<Kind *> addPredicate(Args &&... args) {
1881     Predicates.emplace_back(
1882         llvm::make_unique<Kind>(getInsnVarID(), std::forward<Args>(args)...));
1883     return static_cast<Kind *>(Predicates.back().get());
1884   }
1885 
getRuleMatcher() const1886   RuleMatcher &getRuleMatcher() const { return Rule; }
1887 
getInsnVarID() const1888   unsigned getInsnVarID() const { return InsnVarID; }
1889 
1890   /// Add an operand to the matcher.
addOperand(unsigned OpIdx,const std::string & SymbolicName,unsigned AllocatedTemporariesBaseID)1891   OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName,
1892                              unsigned AllocatedTemporariesBaseID) {
1893     Operands.emplace_back(new OperandMatcher(*this, OpIdx, SymbolicName,
1894                                              AllocatedTemporariesBaseID));
1895     if (!SymbolicName.empty())
1896       Rule.defineOperand(SymbolicName, *Operands.back());
1897 
1898     return *Operands.back();
1899   }
1900 
getOperand(unsigned OpIdx)1901   OperandMatcher &getOperand(unsigned OpIdx) {
1902     auto I = std::find_if(Operands.begin(), Operands.end(),
1903                           [&OpIdx](const std::unique_ptr<OperandMatcher> &X) {
1904                             return X->getOpIdx() == OpIdx;
1905                           });
1906     if (I != Operands.end())
1907       return **I;
1908     llvm_unreachable("Failed to lookup operand");
1909   }
1910 
getSymbolicName() const1911   StringRef getSymbolicName() const { return SymbolicName; }
getNumOperands() const1912   unsigned getNumOperands() const { return Operands.size(); }
operands_begin()1913   OperandVec::iterator operands_begin() { return Operands.begin(); }
operands_end()1914   OperandVec::iterator operands_end() { return Operands.end(); }
operands()1915   iterator_range<OperandVec::iterator> operands() {
1916     return make_range(operands_begin(), operands_end());
1917   }
operands_begin() const1918   OperandVec::const_iterator operands_begin() const { return Operands.begin(); }
operands_end() const1919   OperandVec::const_iterator operands_end() const { return Operands.end(); }
operands() const1920   iterator_range<OperandVec::const_iterator> operands() const {
1921     return make_range(operands_begin(), operands_end());
1922   }
operands_empty() const1923   bool operands_empty() const { return Operands.empty(); }
1924 
pop_front()1925   void pop_front() { Operands.erase(Operands.begin()); }
1926 
1927   void optimize();
1928 
1929   /// Emit MatchTable opcodes that test whether the instruction named in
1930   /// InsnVarName matches all the predicates and all the operands.
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule)1931   void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) {
1932     if (NumOperandsCheck)
1933       InstructionNumOperandsMatcher(InsnVarID, getNumOperands())
1934           .emitPredicateOpcodes(Table, Rule);
1935 
1936     emitPredicateListOpcodes(Table, Rule);
1937 
1938     for (const auto &Operand : Operands)
1939       Operand->emitPredicateOpcodes(Table, Rule);
1940   }
1941 
1942   /// Compare the priority of this object and B.
1943   ///
1944   /// Returns true if this object is more important than B.
isHigherPriorityThan(InstructionMatcher & B)1945   bool isHigherPriorityThan(InstructionMatcher &B) {
1946     // Instruction matchers involving more operands have higher priority.
1947     if (Operands.size() > B.Operands.size())
1948       return true;
1949     if (Operands.size() < B.Operands.size())
1950       return false;
1951 
1952     for (auto &&P : zip(predicates(), B.predicates())) {
1953       auto L = static_cast<InstructionPredicateMatcher *>(std::get<0>(P).get());
1954       auto R = static_cast<InstructionPredicateMatcher *>(std::get<1>(P).get());
1955       if (L->isHigherPriorityThan(*R))
1956         return true;
1957       if (R->isHigherPriorityThan(*L))
1958         return false;
1959     }
1960 
1961     for (const auto &Operand : zip(Operands, B.Operands)) {
1962       if (std::get<0>(Operand)->isHigherPriorityThan(*std::get<1>(Operand)))
1963         return true;
1964       if (std::get<1>(Operand)->isHigherPriorityThan(*std::get<0>(Operand)))
1965         return false;
1966     }
1967 
1968     return false;
1969   };
1970 
1971   /// Report the maximum number of temporary operands needed by the instruction
1972   /// matcher.
countRendererFns()1973   unsigned countRendererFns() {
1974     return std::accumulate(
1975                predicates().begin(), predicates().end(), 0,
1976                [](unsigned A,
1977                   const std::unique_ptr<PredicateMatcher> &Predicate) {
1978                  return A + Predicate->countRendererFns();
1979                }) +
1980            std::accumulate(
1981                Operands.begin(), Operands.end(), 0,
1982                [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) {
1983                  return A + Operand->countRendererFns();
1984                });
1985   }
1986 
getOpcodeMatcher()1987   InstructionOpcodeMatcher &getOpcodeMatcher() {
1988     for (auto &P : predicates())
1989       if (auto *OpMatcher = dyn_cast<InstructionOpcodeMatcher>(P.get()))
1990         return *OpMatcher;
1991     llvm_unreachable("Didn't find an opcode matcher");
1992   }
1993 
isConstantInstruction()1994   bool isConstantInstruction() {
1995     return getOpcodeMatcher().isConstantInstruction();
1996   }
1997 
getOpcode()1998   StringRef getOpcode() { return getOpcodeMatcher().getOpcode(); }
1999 };
2000 
getOpcode() const2001 StringRef RuleMatcher::getOpcode() const {
2002   return Matchers.front()->getOpcode();
2003 }
2004 
getNumOperands() const2005 unsigned RuleMatcher::getNumOperands() const {
2006   return Matchers.front()->getNumOperands();
2007 }
2008 
getFirstConditionAsRootType()2009 LLTCodeGen RuleMatcher::getFirstConditionAsRootType() {
2010   InstructionMatcher &InsnMatcher = *Matchers.front();
2011   if (!InsnMatcher.predicates_empty())
2012     if (const auto *TM =
2013             dyn_cast<LLTOperandMatcher>(&**InsnMatcher.predicates_begin()))
2014       if (TM->getInsnVarID() == 0 && TM->getOpIdx() == 0)
2015         return TM->getTy();
2016   return {};
2017 }
2018 
2019 /// Generates code to check that the operand is a register defined by an
2020 /// instruction that matches the given instruction matcher.
2021 ///
2022 /// For example, the pattern:
2023 ///   (set $dst, (G_MUL (G_ADD $src1, $src2), $src3))
2024 /// would use an InstructionOperandMatcher for operand 1 of the G_MUL to match
2025 /// the:
2026 ///   (G_ADD $src1, $src2)
2027 /// subpattern.
2028 class InstructionOperandMatcher : public OperandPredicateMatcher {
2029 protected:
2030   std::unique_ptr<InstructionMatcher> InsnMatcher;
2031 
2032 public:
InstructionOperandMatcher(unsigned InsnVarID,unsigned OpIdx,RuleMatcher & Rule,StringRef SymbolicName)2033   InstructionOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
2034                             RuleMatcher &Rule, StringRef SymbolicName)
2035       : OperandPredicateMatcher(OPM_Instruction, InsnVarID, OpIdx),
2036         InsnMatcher(new InstructionMatcher(Rule, SymbolicName)) {}
2037 
classof(const PredicateMatcher * P)2038   static bool classof(const PredicateMatcher *P) {
2039     return P->getKind() == OPM_Instruction;
2040   }
2041 
getInsnMatcher() const2042   InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; }
2043 
emitCaptureOpcodes(MatchTable & Table,RuleMatcher & Rule) const2044   void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const {
2045     const unsigned NewInsnVarID = InsnMatcher->getInsnVarID();
2046     Table << MatchTable::Opcode("GIM_RecordInsn")
2047           << MatchTable::Comment("DefineMI")
2048           << MatchTable::IntValue(NewInsnVarID) << MatchTable::Comment("MI")
2049           << MatchTable::IntValue(getInsnVarID())
2050           << MatchTable::Comment("OpIdx") << MatchTable::IntValue(getOpIdx())
2051           << MatchTable::Comment("MIs[" + llvm::to_string(NewInsnVarID) + "]")
2052           << MatchTable::LineBreak;
2053   }
2054 
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const2055   void emitPredicateOpcodes(MatchTable &Table,
2056                             RuleMatcher &Rule) const override {
2057     emitCaptureOpcodes(Table, Rule);
2058     InsnMatcher->emitPredicateOpcodes(Table, Rule);
2059   }
2060 
isHigherPriorityThan(const OperandPredicateMatcher & B) const2061   bool isHigherPriorityThan(const OperandPredicateMatcher &B) const override {
2062     if (OperandPredicateMatcher::isHigherPriorityThan(B))
2063       return true;
2064     if (B.OperandPredicateMatcher::isHigherPriorityThan(*this))
2065       return false;
2066 
2067     if (const InstructionOperandMatcher *BP =
2068             dyn_cast<InstructionOperandMatcher>(&B))
2069       if (InsnMatcher->isHigherPriorityThan(*BP->InsnMatcher))
2070         return true;
2071     return false;
2072   }
2073 };
2074 
optimize()2075 void InstructionMatcher::optimize() {
2076   SmallVector<std::unique_ptr<PredicateMatcher>, 8> Stash;
2077   const auto &OpcMatcher = getOpcodeMatcher();
2078 
2079   Stash.push_back(predicates_pop_front());
2080   if (Stash.back().get() == &OpcMatcher) {
2081     if (NumOperandsCheck && OpcMatcher.getNumOperands() < getNumOperands())
2082       Stash.emplace_back(
2083           new InstructionNumOperandsMatcher(InsnVarID, getNumOperands()));
2084     NumOperandsCheck = false;
2085 
2086     for (auto &OM : Operands)
2087       for (auto &OP : OM->predicates())
2088         if (isa<IntrinsicIDOperandMatcher>(OP)) {
2089           Stash.push_back(std::move(OP));
2090           OM->eraseNullPredicates();
2091           break;
2092         }
2093   }
2094 
2095   if (InsnVarID > 0) {
2096     assert(!Operands.empty() && "Nested instruction is expected to def a vreg");
2097     for (auto &OP : Operands[0]->predicates())
2098       OP.reset();
2099     Operands[0]->eraseNullPredicates();
2100   }
2101   for (auto &OM : Operands) {
2102     for (auto &OP : OM->predicates())
2103       if (isa<LLTOperandMatcher>(OP))
2104         Stash.push_back(std::move(OP));
2105     OM->eraseNullPredicates();
2106   }
2107   while (!Stash.empty())
2108     prependPredicate(Stash.pop_back_val());
2109 }
2110 
2111 //===- Actions ------------------------------------------------------------===//
2112 class OperandRenderer {
2113 public:
2114   enum RendererKind {
2115     OR_Copy,
2116     OR_CopyOrAddZeroReg,
2117     OR_CopySubReg,
2118     OR_CopyConstantAsImm,
2119     OR_CopyFConstantAsFPImm,
2120     OR_Imm,
2121     OR_Register,
2122     OR_TempRegister,
2123     OR_ComplexPattern,
2124     OR_Custom
2125   };
2126 
2127 protected:
2128   RendererKind Kind;
2129 
2130 public:
OperandRenderer(RendererKind Kind)2131   OperandRenderer(RendererKind Kind) : Kind(Kind) {}
~OperandRenderer()2132   virtual ~OperandRenderer() {}
2133 
getKind() const2134   RendererKind getKind() const { return Kind; }
2135 
2136   virtual void emitRenderOpcodes(MatchTable &Table,
2137                                  RuleMatcher &Rule) const = 0;
2138 };
2139 
2140 /// A CopyRenderer emits code to copy a single operand from an existing
2141 /// instruction to the one being built.
2142 class CopyRenderer : public OperandRenderer {
2143 protected:
2144   unsigned NewInsnID;
2145   /// The name of the operand.
2146   const StringRef SymbolicName;
2147 
2148 public:
CopyRenderer(unsigned NewInsnID,StringRef SymbolicName)2149   CopyRenderer(unsigned NewInsnID, StringRef SymbolicName)
2150       : OperandRenderer(OR_Copy), NewInsnID(NewInsnID),
2151         SymbolicName(SymbolicName) {
2152     assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
2153   }
2154 
classof(const OperandRenderer * R)2155   static bool classof(const OperandRenderer *R) {
2156     return R->getKind() == OR_Copy;
2157   }
2158 
getSymbolicName() const2159   const StringRef getSymbolicName() const { return SymbolicName; }
2160 
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2161   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2162     const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2163     unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2164     Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
2165           << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID")
2166           << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2167           << MatchTable::IntValue(Operand.getOpIdx())
2168           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2169   }
2170 };
2171 
2172 /// A CopyOrAddZeroRegRenderer emits code to copy a single operand from an
2173 /// existing instruction to the one being built. If the operand turns out to be
2174 /// a 'G_CONSTANT 0' then it replaces the operand with a zero register.
2175 class CopyOrAddZeroRegRenderer : public OperandRenderer {
2176 protected:
2177   unsigned NewInsnID;
2178   /// The name of the operand.
2179   const StringRef SymbolicName;
2180   const Record *ZeroRegisterDef;
2181 
2182 public:
CopyOrAddZeroRegRenderer(unsigned NewInsnID,StringRef SymbolicName,Record * ZeroRegisterDef)2183   CopyOrAddZeroRegRenderer(unsigned NewInsnID,
2184                            StringRef SymbolicName, Record *ZeroRegisterDef)
2185       : OperandRenderer(OR_CopyOrAddZeroReg), NewInsnID(NewInsnID),
2186         SymbolicName(SymbolicName), ZeroRegisterDef(ZeroRegisterDef) {
2187     assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
2188   }
2189 
classof(const OperandRenderer * R)2190   static bool classof(const OperandRenderer *R) {
2191     return R->getKind() == OR_CopyOrAddZeroReg;
2192   }
2193 
getSymbolicName() const2194   const StringRef getSymbolicName() const { return SymbolicName; }
2195 
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2196   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2197     const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2198     unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2199     Table << MatchTable::Opcode("GIR_CopyOrAddZeroReg")
2200           << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2201           << MatchTable::Comment("OldInsnID")
2202           << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2203           << MatchTable::IntValue(Operand.getOpIdx())
2204           << MatchTable::NamedValue(
2205                  (ZeroRegisterDef->getValue("Namespace")
2206                       ? ZeroRegisterDef->getValueAsString("Namespace")
2207                       : ""),
2208                  ZeroRegisterDef->getName())
2209           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2210   }
2211 };
2212 
2213 /// A CopyConstantAsImmRenderer emits code to render a G_CONSTANT instruction to
2214 /// an extended immediate operand.
2215 class CopyConstantAsImmRenderer : public OperandRenderer {
2216 protected:
2217   unsigned NewInsnID;
2218   /// The name of the operand.
2219   const std::string SymbolicName;
2220   bool Signed;
2221 
2222 public:
CopyConstantAsImmRenderer(unsigned NewInsnID,StringRef SymbolicName)2223   CopyConstantAsImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
2224       : OperandRenderer(OR_CopyConstantAsImm), NewInsnID(NewInsnID),
2225         SymbolicName(SymbolicName), Signed(true) {}
2226 
classof(const OperandRenderer * R)2227   static bool classof(const OperandRenderer *R) {
2228     return R->getKind() == OR_CopyConstantAsImm;
2229   }
2230 
getSymbolicName() const2231   const StringRef getSymbolicName() const { return SymbolicName; }
2232 
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2233   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2234     InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2235     unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2236     Table << MatchTable::Opcode(Signed ? "GIR_CopyConstantAsSImm"
2237                                        : "GIR_CopyConstantAsUImm")
2238           << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2239           << MatchTable::Comment("OldInsnID")
2240           << MatchTable::IntValue(OldInsnVarID)
2241           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2242   }
2243 };
2244 
2245 /// A CopyFConstantAsFPImmRenderer emits code to render a G_FCONSTANT
2246 /// instruction to an extended immediate operand.
2247 class CopyFConstantAsFPImmRenderer : public OperandRenderer {
2248 protected:
2249   unsigned NewInsnID;
2250   /// The name of the operand.
2251   const std::string SymbolicName;
2252 
2253 public:
CopyFConstantAsFPImmRenderer(unsigned NewInsnID,StringRef SymbolicName)2254   CopyFConstantAsFPImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
2255       : OperandRenderer(OR_CopyFConstantAsFPImm), NewInsnID(NewInsnID),
2256         SymbolicName(SymbolicName) {}
2257 
classof(const OperandRenderer * R)2258   static bool classof(const OperandRenderer *R) {
2259     return R->getKind() == OR_CopyFConstantAsFPImm;
2260   }
2261 
getSymbolicName() const2262   const StringRef getSymbolicName() const { return SymbolicName; }
2263 
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2264   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2265     InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2266     unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2267     Table << MatchTable::Opcode("GIR_CopyFConstantAsFPImm")
2268           << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2269           << MatchTable::Comment("OldInsnID")
2270           << MatchTable::IntValue(OldInsnVarID)
2271           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2272   }
2273 };
2274 
2275 /// A CopySubRegRenderer emits code to copy a single register operand from an
2276 /// existing instruction to the one being built and indicate that only a
2277 /// subregister should be copied.
2278 class CopySubRegRenderer : public OperandRenderer {
2279 protected:
2280   unsigned NewInsnID;
2281   /// The name of the operand.
2282   const StringRef SymbolicName;
2283   /// The subregister to extract.
2284   const CodeGenSubRegIndex *SubReg;
2285 
2286 public:
CopySubRegRenderer(unsigned NewInsnID,StringRef SymbolicName,const CodeGenSubRegIndex * SubReg)2287   CopySubRegRenderer(unsigned NewInsnID, StringRef SymbolicName,
2288                      const CodeGenSubRegIndex *SubReg)
2289       : OperandRenderer(OR_CopySubReg), NewInsnID(NewInsnID),
2290         SymbolicName(SymbolicName), SubReg(SubReg) {}
2291 
classof(const OperandRenderer * R)2292   static bool classof(const OperandRenderer *R) {
2293     return R->getKind() == OR_CopySubReg;
2294   }
2295 
getSymbolicName() const2296   const StringRef getSymbolicName() const { return SymbolicName; }
2297 
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2298   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2299     const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
2300     unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
2301     Table << MatchTable::Opcode("GIR_CopySubReg")
2302           << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
2303           << MatchTable::Comment("OldInsnID")
2304           << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
2305           << MatchTable::IntValue(Operand.getOpIdx())
2306           << MatchTable::Comment("SubRegIdx")
2307           << MatchTable::IntValue(SubReg->EnumValue)
2308           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2309   }
2310 };
2311 
2312 /// Adds a specific physical register to the instruction being built.
2313 /// This is typically useful for WZR/XZR on AArch64.
2314 class AddRegisterRenderer : public OperandRenderer {
2315 protected:
2316   unsigned InsnID;
2317   const Record *RegisterDef;
2318 
2319 public:
AddRegisterRenderer(unsigned InsnID,const Record * RegisterDef)2320   AddRegisterRenderer(unsigned InsnID, const Record *RegisterDef)
2321       : OperandRenderer(OR_Register), InsnID(InsnID), RegisterDef(RegisterDef) {
2322   }
2323 
classof(const OperandRenderer * R)2324   static bool classof(const OperandRenderer *R) {
2325     return R->getKind() == OR_Register;
2326   }
2327 
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2328   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2329     Table << MatchTable::Opcode("GIR_AddRegister")
2330           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2331           << MatchTable::NamedValue(
2332                  (RegisterDef->getValue("Namespace")
2333                       ? RegisterDef->getValueAsString("Namespace")
2334                       : ""),
2335                  RegisterDef->getName())
2336           << MatchTable::LineBreak;
2337   }
2338 };
2339 
2340 /// Adds a specific temporary virtual register to the instruction being built.
2341 /// This is used to chain instructions together when emitting multiple
2342 /// instructions.
2343 class TempRegRenderer : public OperandRenderer {
2344 protected:
2345   unsigned InsnID;
2346   unsigned TempRegID;
2347   bool IsDef;
2348 
2349 public:
TempRegRenderer(unsigned InsnID,unsigned TempRegID,bool IsDef=false)2350   TempRegRenderer(unsigned InsnID, unsigned TempRegID, bool IsDef = false)
2351       : OperandRenderer(OR_Register), InsnID(InsnID), TempRegID(TempRegID),
2352         IsDef(IsDef) {}
2353 
classof(const OperandRenderer * R)2354   static bool classof(const OperandRenderer *R) {
2355     return R->getKind() == OR_TempRegister;
2356   }
2357 
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2358   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2359     Table << MatchTable::Opcode("GIR_AddTempRegister")
2360           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2361           << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID)
2362           << MatchTable::Comment("TempRegFlags");
2363     if (IsDef)
2364       Table << MatchTable::NamedValue("RegState::Define");
2365     else
2366       Table << MatchTable::IntValue(0);
2367     Table << MatchTable::LineBreak;
2368   }
2369 };
2370 
2371 /// Adds a specific immediate to the instruction being built.
2372 class ImmRenderer : public OperandRenderer {
2373 protected:
2374   unsigned InsnID;
2375   int64_t Imm;
2376 
2377 public:
ImmRenderer(unsigned InsnID,int64_t Imm)2378   ImmRenderer(unsigned InsnID, int64_t Imm)
2379       : OperandRenderer(OR_Imm), InsnID(InsnID), Imm(Imm) {}
2380 
classof(const OperandRenderer * R)2381   static bool classof(const OperandRenderer *R) {
2382     return R->getKind() == OR_Imm;
2383   }
2384 
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2385   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2386     Table << MatchTable::Opcode("GIR_AddImm") << MatchTable::Comment("InsnID")
2387           << MatchTable::IntValue(InsnID) << MatchTable::Comment("Imm")
2388           << MatchTable::IntValue(Imm) << MatchTable::LineBreak;
2389   }
2390 };
2391 
2392 /// Adds operands by calling a renderer function supplied by the ComplexPattern
2393 /// matcher function.
2394 class RenderComplexPatternOperand : public OperandRenderer {
2395 private:
2396   unsigned InsnID;
2397   const Record &TheDef;
2398   /// The name of the operand.
2399   const StringRef SymbolicName;
2400   /// The renderer number. This must be unique within a rule since it's used to
2401   /// identify a temporary variable to hold the renderer function.
2402   unsigned RendererID;
2403   /// When provided, this is the suboperand of the ComplexPattern operand to
2404   /// render. Otherwise all the suboperands will be rendered.
2405   Optional<unsigned> SubOperand;
2406 
getNumOperands() const2407   unsigned getNumOperands() const {
2408     return TheDef.getValueAsDag("Operands")->getNumArgs();
2409   }
2410 
2411 public:
RenderComplexPatternOperand(unsigned InsnID,const Record & TheDef,StringRef SymbolicName,unsigned RendererID,Optional<unsigned> SubOperand=None)2412   RenderComplexPatternOperand(unsigned InsnID, const Record &TheDef,
2413                               StringRef SymbolicName, unsigned RendererID,
2414                               Optional<unsigned> SubOperand = None)
2415       : OperandRenderer(OR_ComplexPattern), InsnID(InsnID), TheDef(TheDef),
2416         SymbolicName(SymbolicName), RendererID(RendererID),
2417         SubOperand(SubOperand) {}
2418 
classof(const OperandRenderer * R)2419   static bool classof(const OperandRenderer *R) {
2420     return R->getKind() == OR_ComplexPattern;
2421   }
2422 
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2423   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2424     Table << MatchTable::Opcode(SubOperand.hasValue() ? "GIR_ComplexSubOperandRenderer"
2425                                                       : "GIR_ComplexRenderer")
2426           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2427           << MatchTable::Comment("RendererID")
2428           << MatchTable::IntValue(RendererID);
2429     if (SubOperand.hasValue())
2430       Table << MatchTable::Comment("SubOperand")
2431             << MatchTable::IntValue(SubOperand.getValue());
2432     Table << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2433   }
2434 };
2435 
2436 class CustomRenderer : public OperandRenderer {
2437 protected:
2438   unsigned InsnID;
2439   const Record &Renderer;
2440   /// The name of the operand.
2441   const std::string SymbolicName;
2442 
2443 public:
CustomRenderer(unsigned InsnID,const Record & Renderer,StringRef SymbolicName)2444   CustomRenderer(unsigned InsnID, const Record &Renderer,
2445                  StringRef SymbolicName)
2446       : OperandRenderer(OR_Custom), InsnID(InsnID), Renderer(Renderer),
2447         SymbolicName(SymbolicName) {}
2448 
classof(const OperandRenderer * R)2449   static bool classof(const OperandRenderer *R) {
2450     return R->getKind() == OR_Custom;
2451   }
2452 
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2453   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2454     InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2455     unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2456     Table << MatchTable::Opcode("GIR_CustomRenderer")
2457           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2458           << MatchTable::Comment("OldInsnID")
2459           << MatchTable::IntValue(OldInsnVarID)
2460           << MatchTable::Comment("Renderer")
2461           << MatchTable::NamedValue(
2462                  "GICR_" + Renderer.getValueAsString("RendererFn").str())
2463           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2464   }
2465 };
2466 
2467 /// An action taken when all Matcher predicates succeeded for a parent rule.
2468 ///
2469 /// Typical actions include:
2470 /// * Changing the opcode of an instruction.
2471 /// * Adding an operand to an instruction.
2472 class MatchAction {
2473 public:
~MatchAction()2474   virtual ~MatchAction() {}
2475 
2476   /// Emit the MatchTable opcodes to implement the action.
2477   virtual void emitActionOpcodes(MatchTable &Table,
2478                                  RuleMatcher &Rule) const = 0;
2479 };
2480 
2481 /// Generates a comment describing the matched rule being acted upon.
2482 class DebugCommentAction : public MatchAction {
2483 private:
2484   std::string S;
2485 
2486 public:
DebugCommentAction(StringRef S)2487   DebugCommentAction(StringRef S) : S(S) {}
2488 
emitActionOpcodes(MatchTable & Table,RuleMatcher & Rule) const2489   void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2490     Table << MatchTable::Comment(S) << MatchTable::LineBreak;
2491   }
2492 };
2493 
2494 /// Generates code to build an instruction or mutate an existing instruction
2495 /// into the desired instruction when this is possible.
2496 class BuildMIAction : public MatchAction {
2497 private:
2498   unsigned InsnID;
2499   const CodeGenInstruction *I;
2500   InstructionMatcher *Matched;
2501   std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers;
2502 
2503   /// True if the instruction can be built solely by mutating the opcode.
canMutate(RuleMatcher & Rule,const InstructionMatcher * Insn) const2504   bool canMutate(RuleMatcher &Rule, const InstructionMatcher *Insn) const {
2505     if (!Insn)
2506       return false;
2507 
2508     if (OperandRenderers.size() != Insn->getNumOperands())
2509       return false;
2510 
2511     for (const auto &Renderer : enumerate(OperandRenderers)) {
2512       if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) {
2513         const OperandMatcher &OM = Rule.getOperandMatcher(Copy->getSymbolicName());
2514         if (Insn != &OM.getInstructionMatcher() ||
2515             OM.getOpIdx() != Renderer.index())
2516           return false;
2517       } else
2518         return false;
2519     }
2520 
2521     return true;
2522   }
2523 
2524 public:
BuildMIAction(unsigned InsnID,const CodeGenInstruction * I)2525   BuildMIAction(unsigned InsnID, const CodeGenInstruction *I)
2526       : InsnID(InsnID), I(I), Matched(nullptr) {}
2527 
getInsnID() const2528   unsigned getInsnID() const { return InsnID; }
getCGI() const2529   const CodeGenInstruction *getCGI() const { return I; }
2530 
chooseInsnToMutate(RuleMatcher & Rule)2531   void chooseInsnToMutate(RuleMatcher &Rule) {
2532     for (auto *MutateCandidate : Rule.mutatable_insns()) {
2533       if (canMutate(Rule, MutateCandidate)) {
2534         // Take the first one we're offered that we're able to mutate.
2535         Rule.reserveInsnMatcherForMutation(MutateCandidate);
2536         Matched = MutateCandidate;
2537         return;
2538       }
2539     }
2540   }
2541 
2542   template <class Kind, class... Args>
2543   Kind &addRenderer(Args&&... args) {
2544     OperandRenderers.emplace_back(
2545         llvm::make_unique<Kind>(InsnID, std::forward<Args>(args)...));
2546     return *static_cast<Kind *>(OperandRenderers.back().get());
2547   }
2548 
emitActionOpcodes(MatchTable & Table,RuleMatcher & Rule) const2549   void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2550     if (Matched) {
2551       assert(canMutate(Rule, Matched) &&
2552              "Arranged to mutate an insn that isn't mutatable");
2553 
2554       unsigned RecycleInsnID = Rule.getInsnVarID(*Matched);
2555       Table << MatchTable::Opcode("GIR_MutateOpcode")
2556             << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2557             << MatchTable::Comment("RecycleInsnID")
2558             << MatchTable::IntValue(RecycleInsnID)
2559             << MatchTable::Comment("Opcode")
2560             << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
2561             << MatchTable::LineBreak;
2562 
2563       if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) {
2564         for (auto Def : I->ImplicitDefs) {
2565           auto Namespace = Def->getValue("Namespace")
2566                                ? Def->getValueAsString("Namespace")
2567                                : "";
2568           Table << MatchTable::Opcode("GIR_AddImplicitDef")
2569                 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2570                 << MatchTable::NamedValue(Namespace, Def->getName())
2571                 << MatchTable::LineBreak;
2572         }
2573         for (auto Use : I->ImplicitUses) {
2574           auto Namespace = Use->getValue("Namespace")
2575                                ? Use->getValueAsString("Namespace")
2576                                : "";
2577           Table << MatchTable::Opcode("GIR_AddImplicitUse")
2578                 << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2579                 << MatchTable::NamedValue(Namespace, Use->getName())
2580                 << MatchTable::LineBreak;
2581         }
2582       }
2583       return;
2584     }
2585 
2586     // TODO: Simple permutation looks like it could be almost as common as
2587     //       mutation due to commutative operations.
2588 
2589     Table << MatchTable::Opcode("GIR_BuildMI") << MatchTable::Comment("InsnID")
2590           << MatchTable::IntValue(InsnID) << MatchTable::Comment("Opcode")
2591           << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
2592           << MatchTable::LineBreak;
2593     for (const auto &Renderer : OperandRenderers)
2594       Renderer->emitRenderOpcodes(Table, Rule);
2595 
2596     if (I->mayLoad || I->mayStore) {
2597       Table << MatchTable::Opcode("GIR_MergeMemOperands")
2598             << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2599             << MatchTable::Comment("MergeInsnID's");
2600       // Emit the ID's for all the instructions that are matched by this rule.
2601       // TODO: Limit this to matched instructions that mayLoad/mayStore or have
2602       //       some other means of having a memoperand. Also limit this to
2603       //       emitted instructions that expect to have a memoperand too. For
2604       //       example, (G_SEXT (G_LOAD x)) that results in separate load and
2605       //       sign-extend instructions shouldn't put the memoperand on the
2606       //       sign-extend since it has no effect there.
2607       std::vector<unsigned> MergeInsnIDs;
2608       for (const auto &IDMatcherPair : Rule.defined_insn_vars())
2609         MergeInsnIDs.push_back(IDMatcherPair.second);
2610       llvm::sort(MergeInsnIDs.begin(), MergeInsnIDs.end());
2611       for (const auto &MergeInsnID : MergeInsnIDs)
2612         Table << MatchTable::IntValue(MergeInsnID);
2613       Table << MatchTable::NamedValue("GIU_MergeMemOperands_EndOfList")
2614             << MatchTable::LineBreak;
2615     }
2616 
2617     // FIXME: This is a hack but it's sufficient for ISel. We'll need to do
2618     //        better for combines. Particularly when there are multiple match
2619     //        roots.
2620     if (InsnID == 0)
2621       Table << MatchTable::Opcode("GIR_EraseFromParent")
2622             << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2623             << MatchTable::LineBreak;
2624   }
2625 };
2626 
2627 /// Generates code to constrain the operands of an output instruction to the
2628 /// register classes specified by the definition of that instruction.
2629 class ConstrainOperandsToDefinitionAction : public MatchAction {
2630   unsigned InsnID;
2631 
2632 public:
ConstrainOperandsToDefinitionAction(unsigned InsnID)2633   ConstrainOperandsToDefinitionAction(unsigned InsnID) : InsnID(InsnID) {}
2634 
emitActionOpcodes(MatchTable & Table,RuleMatcher & Rule) const2635   void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2636     Table << MatchTable::Opcode("GIR_ConstrainSelectedInstOperands")
2637           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2638           << MatchTable::LineBreak;
2639   }
2640 };
2641 
2642 /// Generates code to constrain the specified operand of an output instruction
2643 /// to the specified register class.
2644 class ConstrainOperandToRegClassAction : public MatchAction {
2645   unsigned InsnID;
2646   unsigned OpIdx;
2647   const CodeGenRegisterClass &RC;
2648 
2649 public:
ConstrainOperandToRegClassAction(unsigned InsnID,unsigned OpIdx,const CodeGenRegisterClass & RC)2650   ConstrainOperandToRegClassAction(unsigned InsnID, unsigned OpIdx,
2651                                    const CodeGenRegisterClass &RC)
2652       : InsnID(InsnID), OpIdx(OpIdx), RC(RC) {}
2653 
emitActionOpcodes(MatchTable & Table,RuleMatcher & Rule) const2654   void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2655     Table << MatchTable::Opcode("GIR_ConstrainOperandRC")
2656           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2657           << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
2658           << MatchTable::Comment("RC " + RC.getName())
2659           << MatchTable::IntValue(RC.EnumValue) << MatchTable::LineBreak;
2660   }
2661 };
2662 
2663 /// Generates code to create a temporary register which can be used to chain
2664 /// instructions together.
2665 class MakeTempRegisterAction : public MatchAction {
2666 private:
2667   LLTCodeGen Ty;
2668   unsigned TempRegID;
2669 
2670 public:
MakeTempRegisterAction(const LLTCodeGen & Ty,unsigned TempRegID)2671   MakeTempRegisterAction(const LLTCodeGen &Ty, unsigned TempRegID)
2672       : Ty(Ty), TempRegID(TempRegID) {}
2673 
emitActionOpcodes(MatchTable & Table,RuleMatcher & Rule) const2674   void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2675     Table << MatchTable::Opcode("GIR_MakeTempReg")
2676           << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID)
2677           << MatchTable::Comment("TypeID")
2678           << MatchTable::NamedValue(Ty.getCxxEnumValue())
2679           << MatchTable::LineBreak;
2680   }
2681 };
2682 
addInstructionMatcher(StringRef SymbolicName)2683 InstructionMatcher &RuleMatcher::addInstructionMatcher(StringRef SymbolicName) {
2684   Matchers.emplace_back(new InstructionMatcher(*this, SymbolicName));
2685   MutatableInsns.insert(Matchers.back().get());
2686   return *Matchers.back();
2687 }
2688 
addRequiredFeature(Record * Feature)2689 void RuleMatcher::addRequiredFeature(Record *Feature) {
2690   RequiredFeatures.push_back(Feature);
2691 }
2692 
getRequiredFeatures() const2693 const std::vector<Record *> &RuleMatcher::getRequiredFeatures() const {
2694   return RequiredFeatures;
2695 }
2696 
2697 // Emplaces an action of the specified Kind at the end of the action list.
2698 //
2699 // Returns a reference to the newly created action.
2700 //
2701 // Like std::vector::emplace_back(), may invalidate all iterators if the new
2702 // size exceeds the capacity. Otherwise, only invalidates the past-the-end
2703 // iterator.
2704 template <class Kind, class... Args>
2705 Kind &RuleMatcher::addAction(Args &&... args) {
2706   Actions.emplace_back(llvm::make_unique<Kind>(std::forward<Args>(args)...));
2707   return *static_cast<Kind *>(Actions.back().get());
2708 }
2709 
2710 // Emplaces an action of the specified Kind before the given insertion point.
2711 //
2712 // Returns an iterator pointing at the newly created instruction.
2713 //
2714 // Like std::vector::insert(), may invalidate all iterators if the new size
2715 // exceeds the capacity. Otherwise, only invalidates the iterators from the
2716 // insertion point onwards.
2717 template <class Kind, class... Args>
insertAction(action_iterator InsertPt,Args &&...args)2718 action_iterator RuleMatcher::insertAction(action_iterator InsertPt,
2719                                           Args &&... args) {
2720   return Actions.emplace(InsertPt,
2721                          llvm::make_unique<Kind>(std::forward<Args>(args)...));
2722 }
2723 
implicitlyDefineInsnVar(InstructionMatcher & Matcher)2724 unsigned RuleMatcher::implicitlyDefineInsnVar(InstructionMatcher &Matcher) {
2725   unsigned NewInsnVarID = NextInsnVarID++;
2726   InsnVariableIDs[&Matcher] = NewInsnVarID;
2727   return NewInsnVarID;
2728 }
2729 
getInsnVarID(InstructionMatcher & InsnMatcher) const2730 unsigned RuleMatcher::getInsnVarID(InstructionMatcher &InsnMatcher) const {
2731   const auto &I = InsnVariableIDs.find(&InsnMatcher);
2732   if (I != InsnVariableIDs.end())
2733     return I->second;
2734   llvm_unreachable("Matched Insn was not captured in a local variable");
2735 }
2736 
defineOperand(StringRef SymbolicName,OperandMatcher & OM)2737 void RuleMatcher::defineOperand(StringRef SymbolicName, OperandMatcher &OM) {
2738   if (DefinedOperands.find(SymbolicName) == DefinedOperands.end()) {
2739     DefinedOperands[SymbolicName] = &OM;
2740     return;
2741   }
2742 
2743   // If the operand is already defined, then we must ensure both references in
2744   // the matcher have the exact same node.
2745   OM.addPredicate<SameOperandMatcher>(OM.getSymbolicName());
2746 }
2747 
2748 InstructionMatcher &
getInstructionMatcher(StringRef SymbolicName) const2749 RuleMatcher::getInstructionMatcher(StringRef SymbolicName) const {
2750   for (const auto &I : InsnVariableIDs)
2751     if (I.first->getSymbolicName() == SymbolicName)
2752       return *I.first;
2753   llvm_unreachable(
2754       ("Failed to lookup instruction " + SymbolicName).str().c_str());
2755 }
2756 
2757 const OperandMatcher &
getOperandMatcher(StringRef Name) const2758 RuleMatcher::getOperandMatcher(StringRef Name) const {
2759   const auto &I = DefinedOperands.find(Name);
2760 
2761   if (I == DefinedOperands.end())
2762     PrintFatalError(SrcLoc, "Operand " + Name + " was not declared in matcher");
2763 
2764   return *I->second;
2765 }
2766 
emit(MatchTable & Table)2767 void RuleMatcher::emit(MatchTable &Table) {
2768   if (Matchers.empty())
2769     llvm_unreachable("Unexpected empty matcher!");
2770 
2771   // The representation supports rules that require multiple roots such as:
2772   //    %ptr(p0) = ...
2773   //    %elt0(s32) = G_LOAD %ptr
2774   //    %1(p0) = G_ADD %ptr, 4
2775   //    %elt1(s32) = G_LOAD p0 %1
2776   // which could be usefully folded into:
2777   //    %ptr(p0) = ...
2778   //    %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr
2779   // on some targets but we don't need to make use of that yet.
2780   assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
2781 
2782   unsigned LabelID = Table.allocateLabelID();
2783   Table << MatchTable::Opcode("GIM_Try", +1)
2784         << MatchTable::Comment("On fail goto")
2785         << MatchTable::JumpTarget(LabelID)
2786         << MatchTable::Comment(("Rule ID " + Twine(RuleID) + " //").str())
2787         << MatchTable::LineBreak;
2788 
2789   if (!RequiredFeatures.empty()) {
2790     Table << MatchTable::Opcode("GIM_CheckFeatures")
2791           << MatchTable::NamedValue(getNameForFeatureBitset(RequiredFeatures))
2792           << MatchTable::LineBreak;
2793   }
2794 
2795   Matchers.front()->emitPredicateOpcodes(Table, *this);
2796 
2797   // We must also check if it's safe to fold the matched instructions.
2798   if (InsnVariableIDs.size() >= 2) {
2799     // Invert the map to create stable ordering (by var names)
2800     SmallVector<unsigned, 2> InsnIDs;
2801     for (const auto &Pair : InsnVariableIDs) {
2802       // Skip the root node since it isn't moving anywhere. Everything else is
2803       // sinking to meet it.
2804       if (Pair.first == Matchers.front().get())
2805         continue;
2806 
2807       InsnIDs.push_back(Pair.second);
2808     }
2809     llvm::sort(InsnIDs.begin(), InsnIDs.end());
2810 
2811     for (const auto &InsnID : InsnIDs) {
2812       // Reject the difficult cases until we have a more accurate check.
2813       Table << MatchTable::Opcode("GIM_CheckIsSafeToFold")
2814             << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
2815             << MatchTable::LineBreak;
2816 
2817       // FIXME: Emit checks to determine it's _actually_ safe to fold and/or
2818       //        account for unsafe cases.
2819       //
2820       //        Example:
2821       //          MI1--> %0 = ...
2822       //                 %1 = ... %0
2823       //          MI0--> %2 = ... %0
2824       //          It's not safe to erase MI1. We currently handle this by not
2825       //          erasing %0 (even when it's dead).
2826       //
2827       //        Example:
2828       //          MI1--> %0 = load volatile @a
2829       //                 %1 = load volatile @a
2830       //          MI0--> %2 = ... %0
2831       //          It's not safe to sink %0's def past %1. We currently handle
2832       //          this by rejecting all loads.
2833       //
2834       //        Example:
2835       //          MI1--> %0 = load @a
2836       //                 %1 = store @a
2837       //          MI0--> %2 = ... %0
2838       //          It's not safe to sink %0's def past %1. We currently handle
2839       //          this by rejecting all loads.
2840       //
2841       //        Example:
2842       //                   G_CONDBR %cond, @BB1
2843       //                 BB0:
2844       //          MI1-->   %0 = load @a
2845       //                   G_BR @BB1
2846       //                 BB1:
2847       //          MI0-->   %2 = ... %0
2848       //          It's not always safe to sink %0 across control flow. In this
2849       //          case it may introduce a memory fault. We currentl handle this
2850       //          by rejecting all loads.
2851     }
2852   }
2853 
2854   for (const auto &PM : EpilogueMatchers)
2855     PM->emitPredicateOpcodes(Table, *this);
2856 
2857   for (const auto &MA : Actions)
2858     MA->emitActionOpcodes(Table, *this);
2859 
2860   if (Table.isWithCoverage())
2861     Table << MatchTable::Opcode("GIR_Coverage") << MatchTable::IntValue(RuleID)
2862           << MatchTable::LineBreak;
2863   else
2864     Table << MatchTable::Comment(("GIR_Coverage, " + Twine(RuleID) + ",").str())
2865           << MatchTable::LineBreak;
2866 
2867   Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak
2868         << MatchTable::Label(LabelID);
2869   ++NumPatternEmitted;
2870 }
2871 
isHigherPriorityThan(const RuleMatcher & B) const2872 bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
2873   // Rules involving more match roots have higher priority.
2874   if (Matchers.size() > B.Matchers.size())
2875     return true;
2876   if (Matchers.size() < B.Matchers.size())
2877     return false;
2878 
2879   for (const auto &Matcher : zip(Matchers, B.Matchers)) {
2880     if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher)))
2881       return true;
2882     if (std::get<1>(Matcher)->isHigherPriorityThan(*std::get<0>(Matcher)))
2883       return false;
2884   }
2885 
2886   return false;
2887 }
2888 
countRendererFns() const2889 unsigned RuleMatcher::countRendererFns() const {
2890   return std::accumulate(
2891       Matchers.begin(), Matchers.end(), 0,
2892       [](unsigned A, const std::unique_ptr<InstructionMatcher> &Matcher) {
2893         return A + Matcher->countRendererFns();
2894       });
2895 }
2896 
isHigherPriorityThan(const OperandPredicateMatcher & B) const2897 bool OperandPredicateMatcher::isHigherPriorityThan(
2898     const OperandPredicateMatcher &B) const {
2899   // Generally speaking, an instruction is more important than an Int or a
2900   // LiteralInt because it can cover more nodes but theres an exception to
2901   // this. G_CONSTANT's are less important than either of those two because they
2902   // are more permissive.
2903 
2904   const InstructionOperandMatcher *AOM =
2905       dyn_cast<InstructionOperandMatcher>(this);
2906   const InstructionOperandMatcher *BOM =
2907       dyn_cast<InstructionOperandMatcher>(&B);
2908   bool AIsConstantInsn = AOM && AOM->getInsnMatcher().isConstantInstruction();
2909   bool BIsConstantInsn = BOM && BOM->getInsnMatcher().isConstantInstruction();
2910 
2911   if (AOM && BOM) {
2912     // The relative priorities between a G_CONSTANT and any other instruction
2913     // don't actually matter but this code is needed to ensure a strict weak
2914     // ordering. This is particularly important on Windows where the rules will
2915     // be incorrectly sorted without it.
2916     if (AIsConstantInsn != BIsConstantInsn)
2917       return AIsConstantInsn < BIsConstantInsn;
2918     return false;
2919   }
2920 
2921   if (AOM && AIsConstantInsn && (B.Kind == OPM_Int || B.Kind == OPM_LiteralInt))
2922     return false;
2923   if (BOM && BIsConstantInsn && (Kind == OPM_Int || Kind == OPM_LiteralInt))
2924     return true;
2925 
2926   return Kind < B.Kind;
2927 }
2928 
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const2929 void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
2930                                               RuleMatcher &Rule) const {
2931   const OperandMatcher &OtherOM = Rule.getOperandMatcher(MatchingName);
2932   unsigned OtherInsnVarID = Rule.getInsnVarID(OtherOM.getInstructionMatcher());
2933   assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getInsnVarID());
2934 
2935   Table << MatchTable::Opcode("GIM_CheckIsSameOperand")
2936         << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
2937         << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx)
2938         << MatchTable::Comment("OtherMI")
2939         << MatchTable::IntValue(OtherInsnVarID)
2940         << MatchTable::Comment("OtherOpIdx")
2941         << MatchTable::IntValue(OtherOM.getOpIdx())
2942         << MatchTable::LineBreak;
2943 }
2944 
2945 //===- GlobalISelEmitter class --------------------------------------------===//
2946 
2947 class GlobalISelEmitter {
2948 public:
2949   explicit GlobalISelEmitter(RecordKeeper &RK);
2950   void run(raw_ostream &OS);
2951 
2952 private:
2953   const RecordKeeper &RK;
2954   const CodeGenDAGPatterns CGP;
2955   const CodeGenTarget &Target;
2956   CodeGenRegBank CGRegs;
2957 
2958   /// Keep track of the equivalence between SDNodes and Instruction by mapping
2959   /// SDNodes to the GINodeEquiv mapping. We need to map to the GINodeEquiv to
2960   /// check for attributes on the relation such as CheckMMOIsNonAtomic.
2961   /// This is defined using 'GINodeEquiv' in the target description.
2962   DenseMap<Record *, Record *> NodeEquivs;
2963 
2964   /// Keep track of the equivalence between ComplexPattern's and
2965   /// GIComplexOperandMatcher. Map entries are specified by subclassing
2966   /// GIComplexPatternEquiv.
2967   DenseMap<const Record *, const Record *> ComplexPatternEquivs;
2968 
2969   /// Keep track of the equivalence between SDNodeXForm's and
2970   /// GICustomOperandRenderer. Map entries are specified by subclassing
2971   /// GISDNodeXFormEquiv.
2972   DenseMap<const Record *, const Record *> SDNodeXFormEquivs;
2973 
2974   /// Keep track of Scores of PatternsToMatch similar to how the DAG does.
2975   /// This adds compatibility for RuleMatchers to use this for ordering rules.
2976   DenseMap<uint64_t, int> RuleMatcherScores;
2977 
2978   // Map of predicates to their subtarget features.
2979   SubtargetFeatureInfoMap SubtargetFeatures;
2980 
2981   // Rule coverage information.
2982   Optional<CodeGenCoverage> RuleCoverage;
2983 
2984   void gatherOpcodeValues();
2985   void gatherTypeIDValues();
2986   void gatherNodeEquivs();
2987   // Instruction predicate code that will be emitted in generated functions.
2988   SmallVector<std::string, 2> InstructionPredicateCodes;
2989   unsigned getOrCreateInstructionPredicateFnId(StringRef Code);
2990 
2991   Record *findNodeEquiv(Record *N) const;
2992   const CodeGenInstruction *getEquivNode(Record &Equiv,
2993                                          const TreePatternNode *N) const;
2994 
2995   Error importRulePredicates(RuleMatcher &M, ArrayRef<Predicate> Predicates);
2996   Expected<InstructionMatcher &>
2997   createAndImportSelDAGMatcher(RuleMatcher &Rule,
2998                                InstructionMatcher &InsnMatcher,
2999                                const TreePatternNode *Src, unsigned &TempOpIdx);
3000   Error importComplexPatternOperandMatcher(OperandMatcher &OM, Record *R,
3001                                            unsigned &TempOpIdx) const;
3002   Error importChildMatcher(RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
3003                            const TreePatternNode *SrcChild,
3004                            bool OperandIsAPointer, unsigned OpIdx,
3005                            unsigned &TempOpIdx);
3006 
3007   Expected<BuildMIAction &>
3008   createAndImportInstructionRenderer(RuleMatcher &M,
3009                                      const TreePatternNode *Dst);
3010   Expected<action_iterator> createAndImportSubInstructionRenderer(
3011       action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst,
3012       unsigned TempReg);
3013   Expected<action_iterator>
3014   createInstructionRenderer(action_iterator InsertPt, RuleMatcher &M,
3015                             const TreePatternNode *Dst);
3016   void importExplicitDefRenderers(BuildMIAction &DstMIBuilder);
3017   Expected<action_iterator>
3018   importExplicitUseRenderers(action_iterator InsertPt, RuleMatcher &M,
3019                              BuildMIAction &DstMIBuilder,
3020                              const llvm::TreePatternNode *Dst);
3021   Expected<action_iterator>
3022   importExplicitUseRenderer(action_iterator InsertPt, RuleMatcher &Rule,
3023                             BuildMIAction &DstMIBuilder,
3024                             TreePatternNode *DstChild);
3025   Error importDefaultOperandRenderers(BuildMIAction &DstMIBuilder,
3026                                       DagInit *DefaultOps) const;
3027   Error
3028   importImplicitDefRenderers(BuildMIAction &DstMIBuilder,
3029                              const std::vector<Record *> &ImplicitDefs) const;
3030 
3031   void emitCxxPredicateFns(raw_ostream &OS, StringRef CodeFieldName,
3032                            StringRef TypeIdentifier, StringRef ArgType,
3033                            StringRef ArgName, StringRef AdditionalDeclarations,
3034                            std::function<bool(const Record *R)> Filter);
3035   void emitImmPredicateFns(raw_ostream &OS, StringRef TypeIdentifier,
3036                            StringRef ArgType,
3037                            std::function<bool(const Record *R)> Filter);
3038   void emitMIPredicateFns(raw_ostream &OS);
3039 
3040   /// Analyze pattern \p P, returning a matcher for it if possible.
3041   /// Otherwise, return an Error explaining why we don't support it.
3042   Expected<RuleMatcher> runOnPattern(const PatternToMatch &P);
3043 
3044   void declareSubtargetFeature(Record *Predicate);
3045 
3046   MatchTable buildMatchTable(MutableArrayRef<RuleMatcher> Rules, bool Optimize,
3047                              bool WithCoverage);
3048 
3049 public:
3050   /// Takes a sequence of \p Rules and group them based on the predicates
3051   /// they share. \p MatcherStorage is used as a memory container
3052   /// for the group that are created as part of this process.
3053   ///
3054   /// What this optimization does looks like if GroupT = GroupMatcher:
3055   /// Output without optimization:
3056   /// \verbatim
3057   /// # R1
3058   ///  # predicate A
3059   ///  # predicate B
3060   ///  ...
3061   /// # R2
3062   ///  # predicate A // <-- effectively this is going to be checked twice.
3063   ///                //     Once in R1 and once in R2.
3064   ///  # predicate C
3065   /// \endverbatim
3066   /// Output with optimization:
3067   /// \verbatim
3068   /// # Group1_2
3069   ///  # predicate A // <-- Check is now shared.
3070   ///  # R1
3071   ///   # predicate B
3072   ///  # R2
3073   ///   # predicate C
3074   /// \endverbatim
3075   template <class GroupT>
3076   static std::vector<Matcher *> optimizeRules(
3077       ArrayRef<Matcher *> Rules,
3078       std::vector<std::unique_ptr<Matcher>> &MatcherStorage);
3079 };
3080 
gatherOpcodeValues()3081 void GlobalISelEmitter::gatherOpcodeValues() {
3082   InstructionOpcodeMatcher::initOpcodeValuesMap(Target);
3083 }
3084 
gatherTypeIDValues()3085 void GlobalISelEmitter::gatherTypeIDValues() {
3086   LLTOperandMatcher::initTypeIDValuesMap();
3087 }
getOrCreateInstructionPredicateFnId(StringRef Code)3088 unsigned GlobalISelEmitter::getOrCreateInstructionPredicateFnId(StringRef Code) {
3089   // There's not very many predicates that need to be here at the moment so we
3090   // just maintain a simple set-like vector. If it grows then we'll need to do
3091   // something more efficient.
3092   const auto &I = std::find(InstructionPredicateCodes.begin(),
3093                             InstructionPredicateCodes.end(),
3094                             Code);
3095   if (I == InstructionPredicateCodes.end()) {
3096     unsigned ID = InstructionPredicateCodes.size();
3097     InstructionPredicateCodes.push_back(Code);
3098     return ID;
3099   }
3100   return std::distance(InstructionPredicateCodes.begin(), I);
3101 }
3102 
gatherNodeEquivs()3103 void GlobalISelEmitter::gatherNodeEquivs() {
3104   assert(NodeEquivs.empty());
3105   for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
3106     NodeEquivs[Equiv->getValueAsDef("Node")] = Equiv;
3107 
3108   assert(ComplexPatternEquivs.empty());
3109   for (Record *Equiv : RK.getAllDerivedDefinitions("GIComplexPatternEquiv")) {
3110     Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
3111     if (!SelDAGEquiv)
3112       continue;
3113     ComplexPatternEquivs[SelDAGEquiv] = Equiv;
3114  }
3115 
3116  assert(SDNodeXFormEquivs.empty());
3117  for (Record *Equiv : RK.getAllDerivedDefinitions("GISDNodeXFormEquiv")) {
3118    Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
3119    if (!SelDAGEquiv)
3120      continue;
3121    SDNodeXFormEquivs[SelDAGEquiv] = Equiv;
3122  }
3123 }
3124 
findNodeEquiv(Record * N) const3125 Record *GlobalISelEmitter::findNodeEquiv(Record *N) const {
3126   return NodeEquivs.lookup(N);
3127 }
3128 
3129 const CodeGenInstruction *
getEquivNode(Record & Equiv,const TreePatternNode * N) const3130 GlobalISelEmitter::getEquivNode(Record &Equiv, const TreePatternNode *N) const {
3131   for (const auto &Predicate : N->getPredicateFns()) {
3132     if (!Equiv.isValueUnset("IfSignExtend") && Predicate.isLoad() &&
3133         Predicate.isSignExtLoad())
3134       return &Target.getInstruction(Equiv.getValueAsDef("IfSignExtend"));
3135     if (!Equiv.isValueUnset("IfZeroExtend") && Predicate.isLoad() &&
3136         Predicate.isZeroExtLoad())
3137       return &Target.getInstruction(Equiv.getValueAsDef("IfZeroExtend"));
3138   }
3139   return &Target.getInstruction(Equiv.getValueAsDef("I"));
3140 }
3141 
GlobalISelEmitter(RecordKeeper & RK)3142 GlobalISelEmitter::GlobalISelEmitter(RecordKeeper &RK)
3143     : RK(RK), CGP(RK), Target(CGP.getTargetInfo()),
3144       CGRegs(RK, Target.getHwModes()) {}
3145 
3146 //===- Emitter ------------------------------------------------------------===//
3147 
3148 Error
importRulePredicates(RuleMatcher & M,ArrayRef<Predicate> Predicates)3149 GlobalISelEmitter::importRulePredicates(RuleMatcher &M,
3150                                         ArrayRef<Predicate> Predicates) {
3151   for (const Predicate &P : Predicates) {
3152     if (!P.Def)
3153       continue;
3154     declareSubtargetFeature(P.Def);
3155     M.addRequiredFeature(P.Def);
3156   }
3157 
3158   return Error::success();
3159 }
3160 
createAndImportSelDAGMatcher(RuleMatcher & Rule,InstructionMatcher & InsnMatcher,const TreePatternNode * Src,unsigned & TempOpIdx)3161 Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher(
3162     RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
3163     const TreePatternNode *Src, unsigned &TempOpIdx) {
3164   Record *SrcGIEquivOrNull = nullptr;
3165   const CodeGenInstruction *SrcGIOrNull = nullptr;
3166 
3167   // Start with the defined operands (i.e., the results of the root operator).
3168   if (Src->getExtTypes().size() > 1)
3169     return failedImport("Src pattern has multiple results");
3170 
3171   if (Src->isLeaf()) {
3172     Init *SrcInit = Src->getLeafValue();
3173     if (isa<IntInit>(SrcInit)) {
3174       InsnMatcher.addPredicate<InstructionOpcodeMatcher>(
3175           &Target.getInstruction(RK.getDef("G_CONSTANT")));
3176     } else
3177       return failedImport(
3178           "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
3179   } else {
3180     SrcGIEquivOrNull = findNodeEquiv(Src->getOperator());
3181     if (!SrcGIEquivOrNull)
3182       return failedImport("Pattern operator lacks an equivalent Instruction" +
3183                           explainOperator(Src->getOperator()));
3184     SrcGIOrNull = getEquivNode(*SrcGIEquivOrNull, Src);
3185 
3186     // The operators look good: match the opcode
3187     InsnMatcher.addPredicate<InstructionOpcodeMatcher>(SrcGIOrNull);
3188   }
3189 
3190   unsigned OpIdx = 0;
3191   for (const TypeSetByHwMode &VTy : Src->getExtTypes()) {
3192     // Results don't have a name unless they are the root node. The caller will
3193     // set the name if appropriate.
3194     OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
3195     if (auto Error = OM.addTypeCheckPredicate(VTy, false /* OperandIsAPointer */))
3196       return failedImport(toString(std::move(Error)) +
3197                           " for result of Src pattern operator");
3198   }
3199 
3200   for (const auto &Predicate : Src->getPredicateFns()) {
3201     if (Predicate.isAlwaysTrue())
3202       continue;
3203 
3204     if (Predicate.isImmediatePattern()) {
3205       InsnMatcher.addPredicate<InstructionImmPredicateMatcher>(Predicate);
3206       continue;
3207     }
3208 
3209     // G_LOAD is used for both non-extending and any-extending loads.
3210     if (Predicate.isLoad() && Predicate.isNonExtLoad()) {
3211       InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3212           0, MemoryVsLLTSizePredicateMatcher::EqualTo, 0);
3213       continue;
3214     }
3215     if (Predicate.isLoad() && Predicate.isAnyExtLoad()) {
3216       InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
3217           0, MemoryVsLLTSizePredicateMatcher::LessThan, 0);
3218       continue;
3219     }
3220 
3221     // No check required. We already did it by swapping the opcode.
3222     if (!SrcGIEquivOrNull->isValueUnset("IfSignExtend") &&
3223         Predicate.isSignExtLoad())
3224       continue;
3225 
3226     // No check required. We already did it by swapping the opcode.
3227     if (!SrcGIEquivOrNull->isValueUnset("IfZeroExtend") &&
3228         Predicate.isZeroExtLoad())
3229       continue;
3230 
3231     // No check required. G_STORE by itself is a non-extending store.
3232     if (Predicate.isNonTruncStore())
3233       continue;
3234 
3235     if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
3236       if (Predicate.getMemoryVT() != nullptr) {
3237         Optional<LLTCodeGen> MemTyOrNone =
3238             MVTToLLT(getValueType(Predicate.getMemoryVT()));
3239 
3240         if (!MemTyOrNone)
3241           return failedImport("MemVT could not be converted to LLT");
3242 
3243         // MMO's work in bytes so we must take care of unusual types like i1
3244         // don't round down.
3245         unsigned MemSizeInBits =
3246             llvm::alignTo(MemTyOrNone->get().getSizeInBits(), 8);
3247 
3248         InsnMatcher.addPredicate<MemorySizePredicateMatcher>(
3249             0, MemSizeInBits / 8);
3250         continue;
3251       }
3252     }
3253 
3254     if (Predicate.isLoad() || Predicate.isStore()) {
3255       // No check required. A G_LOAD/G_STORE is an unindexed load.
3256       if (Predicate.isUnindexed())
3257         continue;
3258     }
3259 
3260     if (Predicate.isAtomic()) {
3261       if (Predicate.isAtomicOrderingMonotonic()) {
3262         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3263             "Monotonic");
3264         continue;
3265       }
3266       if (Predicate.isAtomicOrderingAcquire()) {
3267         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Acquire");
3268         continue;
3269       }
3270       if (Predicate.isAtomicOrderingRelease()) {
3271         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Release");
3272         continue;
3273       }
3274       if (Predicate.isAtomicOrderingAcquireRelease()) {
3275         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3276             "AcquireRelease");
3277         continue;
3278       }
3279       if (Predicate.isAtomicOrderingSequentiallyConsistent()) {
3280         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3281             "SequentiallyConsistent");
3282         continue;
3283       }
3284 
3285       if (Predicate.isAtomicOrderingAcquireOrStronger()) {
3286         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3287             "Acquire", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
3288         continue;
3289       }
3290       if (Predicate.isAtomicOrderingWeakerThanAcquire()) {
3291         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3292             "Acquire", AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
3293         continue;
3294       }
3295 
3296       if (Predicate.isAtomicOrderingReleaseOrStronger()) {
3297         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3298             "Release", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
3299         continue;
3300       }
3301       if (Predicate.isAtomicOrderingWeakerThanRelease()) {
3302         InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
3303             "Release", AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
3304         continue;
3305       }
3306     }
3307 
3308     if (Predicate.hasGISelPredicateCode()) {
3309       InsnMatcher.addPredicate<GenericInstructionPredicateMatcher>(Predicate);
3310       continue;
3311     }
3312 
3313     return failedImport("Src pattern child has predicate (" +
3314                         explainPredicates(Src) + ")");
3315   }
3316   if (SrcGIEquivOrNull && SrcGIEquivOrNull->getValueAsBit("CheckMMOIsNonAtomic"))
3317     InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("NotAtomic");
3318 
3319   if (Src->isLeaf()) {
3320     Init *SrcInit = Src->getLeafValue();
3321     if (IntInit *SrcIntInit = dyn_cast<IntInit>(SrcInit)) {
3322       OperandMatcher &OM =
3323           InsnMatcher.addOperand(OpIdx++, Src->getName(), TempOpIdx);
3324       OM.addPredicate<LiteralIntOperandMatcher>(SrcIntInit->getValue());
3325     } else
3326       return failedImport(
3327           "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
3328   } else {
3329     assert(SrcGIOrNull &&
3330            "Expected to have already found an equivalent Instruction");
3331     if (SrcGIOrNull->TheDef->getName() == "G_CONSTANT" ||
3332         SrcGIOrNull->TheDef->getName() == "G_FCONSTANT") {
3333       // imm/fpimm still have operands but we don't need to do anything with it
3334       // here since we don't support ImmLeaf predicates yet. However, we still
3335       // need to note the hidden operand to get GIM_CheckNumOperands correct.
3336       InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
3337       return InsnMatcher;
3338     }
3339 
3340     // Match the used operands (i.e. the children of the operator).
3341     for (unsigned i = 0, e = Src->getNumChildren(); i != e; ++i) {
3342       TreePatternNode *SrcChild = Src->getChild(i);
3343 
3344       // SelectionDAG allows pointers to be represented with iN since it doesn't
3345       // distinguish between pointers and integers but they are different types in GlobalISel.
3346       // Coerce integers to pointers to address space 0 if the context indicates a pointer.
3347       bool OperandIsAPointer = SrcGIOrNull->isOperandAPointer(i);
3348 
3349       // For G_INTRINSIC/G_INTRINSIC_W_SIDE_EFFECTS, the operand immediately
3350       // following the defs is an intrinsic ID.
3351       if ((SrcGIOrNull->TheDef->getName() == "G_INTRINSIC" ||
3352            SrcGIOrNull->TheDef->getName() == "G_INTRINSIC_W_SIDE_EFFECTS") &&
3353           i == 0) {
3354         if (const CodeGenIntrinsic *II = Src->getIntrinsicInfo(CGP)) {
3355           OperandMatcher &OM =
3356               InsnMatcher.addOperand(OpIdx++, SrcChild->getName(), TempOpIdx);
3357           OM.addPredicate<IntrinsicIDOperandMatcher>(II);
3358           continue;
3359         }
3360 
3361         return failedImport("Expected IntInit containing instrinsic ID)");
3362       }
3363 
3364       if (auto Error =
3365               importChildMatcher(Rule, InsnMatcher, SrcChild, OperandIsAPointer,
3366                                  OpIdx++, TempOpIdx))
3367         return std::move(Error);
3368     }
3369   }
3370 
3371   return InsnMatcher;
3372 }
3373 
importComplexPatternOperandMatcher(OperandMatcher & OM,Record * R,unsigned & TempOpIdx) const3374 Error GlobalISelEmitter::importComplexPatternOperandMatcher(
3375     OperandMatcher &OM, Record *R, unsigned &TempOpIdx) const {
3376   const auto &ComplexPattern = ComplexPatternEquivs.find(R);
3377   if (ComplexPattern == ComplexPatternEquivs.end())
3378     return failedImport("SelectionDAG ComplexPattern (" + R->getName() +
3379                         ") not mapped to GlobalISel");
3380 
3381   OM.addPredicate<ComplexPatternOperandMatcher>(OM, *ComplexPattern->second);
3382   TempOpIdx++;
3383   return Error::success();
3384 }
3385 
importChildMatcher(RuleMatcher & Rule,InstructionMatcher & InsnMatcher,const TreePatternNode * SrcChild,bool OperandIsAPointer,unsigned OpIdx,unsigned & TempOpIdx)3386 Error GlobalISelEmitter::importChildMatcher(RuleMatcher &Rule,
3387                                             InstructionMatcher &InsnMatcher,
3388                                             const TreePatternNode *SrcChild,
3389                                             bool OperandIsAPointer,
3390                                             unsigned OpIdx,
3391                                             unsigned &TempOpIdx) {
3392   OperandMatcher &OM =
3393       InsnMatcher.addOperand(OpIdx, SrcChild->getName(), TempOpIdx);
3394   if (OM.isSameAsAnotherOperand())
3395     return Error::success();
3396 
3397   ArrayRef<TypeSetByHwMode> ChildTypes = SrcChild->getExtTypes();
3398   if (ChildTypes.size() != 1)
3399     return failedImport("Src pattern child has multiple results");
3400 
3401   // Check MBB's before the type check since they are not a known type.
3402   if (!SrcChild->isLeaf()) {
3403     if (SrcChild->getOperator()->isSubClassOf("SDNode")) {
3404       auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator());
3405       if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
3406         OM.addPredicate<MBBOperandMatcher>();
3407         return Error::success();
3408       }
3409     }
3410   }
3411 
3412   if (auto Error =
3413           OM.addTypeCheckPredicate(ChildTypes.front(), OperandIsAPointer))
3414     return failedImport(toString(std::move(Error)) + " for Src operand (" +
3415                         to_string(*SrcChild) + ")");
3416 
3417   // Check for nested instructions.
3418   if (!SrcChild->isLeaf()) {
3419     if (SrcChild->getOperator()->isSubClassOf("ComplexPattern")) {
3420       // When a ComplexPattern is used as an operator, it should do the same
3421       // thing as when used as a leaf. However, the children of the operator
3422       // name the sub-operands that make up the complex operand and we must
3423       // prepare to reference them in the renderer too.
3424       unsigned RendererID = TempOpIdx;
3425       if (auto Error = importComplexPatternOperandMatcher(
3426               OM, SrcChild->getOperator(), TempOpIdx))
3427         return Error;
3428 
3429       for (unsigned i = 0, e = SrcChild->getNumChildren(); i != e; ++i) {
3430         auto *SubOperand = SrcChild->getChild(i);
3431         if (!SubOperand->getName().empty())
3432           Rule.defineComplexSubOperand(SubOperand->getName(),
3433                                        SrcChild->getOperator(), RendererID, i);
3434       }
3435 
3436       return Error::success();
3437     }
3438 
3439     auto MaybeInsnOperand = OM.addPredicate<InstructionOperandMatcher>(
3440         InsnMatcher.getRuleMatcher(), SrcChild->getName());
3441     if (!MaybeInsnOperand.hasValue()) {
3442       // This isn't strictly true. If the user were to provide exactly the same
3443       // matchers as the original operand then we could allow it. However, it's
3444       // simpler to not permit the redundant specification.
3445       return failedImport("Nested instruction cannot be the same as another operand");
3446     }
3447 
3448     // Map the node to a gMIR instruction.
3449     InstructionOperandMatcher &InsnOperand = **MaybeInsnOperand;
3450     auto InsnMatcherOrError = createAndImportSelDAGMatcher(
3451         Rule, InsnOperand.getInsnMatcher(), SrcChild, TempOpIdx);
3452     if (auto Error = InsnMatcherOrError.takeError())
3453       return Error;
3454 
3455     return Error::success();
3456   }
3457 
3458   if (SrcChild->hasAnyPredicate())
3459     return failedImport("Src pattern child has unsupported predicate");
3460 
3461   // Check for constant immediates.
3462   if (auto *ChildInt = dyn_cast<IntInit>(SrcChild->getLeafValue())) {
3463     OM.addPredicate<ConstantIntOperandMatcher>(ChildInt->getValue());
3464     return Error::success();
3465   }
3466 
3467   // Check for def's like register classes or ComplexPattern's.
3468   if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
3469     auto *ChildRec = ChildDefInit->getDef();
3470 
3471     // Check for register classes.
3472     if (ChildRec->isSubClassOf("RegisterClass") ||
3473         ChildRec->isSubClassOf("RegisterOperand")) {
3474       OM.addPredicate<RegisterBankOperandMatcher>(
3475           Target.getRegisterClass(getInitValueAsRegClass(ChildDefInit)));
3476       return Error::success();
3477     }
3478 
3479     // Check for ValueType.
3480     if (ChildRec->isSubClassOf("ValueType")) {
3481       // We already added a type check as standard practice so this doesn't need
3482       // to do anything.
3483       return Error::success();
3484     }
3485 
3486     // Check for ComplexPattern's.
3487     if (ChildRec->isSubClassOf("ComplexPattern"))
3488       return importComplexPatternOperandMatcher(OM, ChildRec, TempOpIdx);
3489 
3490     if (ChildRec->isSubClassOf("ImmLeaf")) {
3491       return failedImport(
3492           "Src pattern child def is an unsupported tablegen class (ImmLeaf)");
3493     }
3494 
3495     return failedImport(
3496         "Src pattern child def is an unsupported tablegen class");
3497   }
3498 
3499   return failedImport("Src pattern child is an unsupported kind");
3500 }
3501 
importExplicitUseRenderer(action_iterator InsertPt,RuleMatcher & Rule,BuildMIAction & DstMIBuilder,TreePatternNode * DstChild)3502 Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderer(
3503     action_iterator InsertPt, RuleMatcher &Rule, BuildMIAction &DstMIBuilder,
3504     TreePatternNode *DstChild) {
3505 
3506   const auto &SubOperand = Rule.getComplexSubOperand(DstChild->getName());
3507   if (SubOperand.hasValue()) {
3508     DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
3509         *std::get<0>(*SubOperand), DstChild->getName(),
3510         std::get<1>(*SubOperand), std::get<2>(*SubOperand));
3511     return InsertPt;
3512   }
3513 
3514   if (!DstChild->isLeaf()) {
3515 
3516     if (DstChild->getOperator()->isSubClassOf("SDNodeXForm")) {
3517       auto Child = DstChild->getChild(0);
3518       auto I = SDNodeXFormEquivs.find(DstChild->getOperator());
3519       if (I != SDNodeXFormEquivs.end()) {
3520         DstMIBuilder.addRenderer<CustomRenderer>(*I->second, Child->getName());
3521         return InsertPt;
3522       }
3523       return failedImport("SDNodeXForm " + Child->getName() +
3524                           " has no custom renderer");
3525     }
3526 
3527     // We accept 'bb' here. It's an operator because BasicBlockSDNode isn't
3528     // inline, but in MI it's just another operand.
3529     if (DstChild->getOperator()->isSubClassOf("SDNode")) {
3530       auto &ChildSDNI = CGP.getSDNodeInfo(DstChild->getOperator());
3531       if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
3532         DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
3533         return InsertPt;
3534       }
3535     }
3536 
3537     // Similarly, imm is an operator in TreePatternNode's view but must be
3538     // rendered as operands.
3539     // FIXME: The target should be able to choose sign-extended when appropriate
3540     //        (e.g. on Mips).
3541     if (DstChild->getOperator()->getName() == "imm") {
3542       DstMIBuilder.addRenderer<CopyConstantAsImmRenderer>(DstChild->getName());
3543       return InsertPt;
3544     } else if (DstChild->getOperator()->getName() == "fpimm") {
3545       DstMIBuilder.addRenderer<CopyFConstantAsFPImmRenderer>(
3546           DstChild->getName());
3547       return InsertPt;
3548     }
3549 
3550     if (DstChild->getOperator()->isSubClassOf("Instruction")) {
3551       ArrayRef<TypeSetByHwMode> ChildTypes = DstChild->getExtTypes();
3552       if (ChildTypes.size() != 1)
3553         return failedImport("Dst pattern child has multiple results");
3554 
3555       Optional<LLTCodeGen> OpTyOrNone = None;
3556       if (ChildTypes.front().isMachineValueType())
3557         OpTyOrNone =
3558             MVTToLLT(ChildTypes.front().getMachineValueType().SimpleTy);
3559       if (!OpTyOrNone)
3560         return failedImport("Dst operand has an unsupported type");
3561 
3562       unsigned TempRegID = Rule.allocateTempRegID();
3563       InsertPt = Rule.insertAction<MakeTempRegisterAction>(
3564           InsertPt, OpTyOrNone.getValue(), TempRegID);
3565       DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
3566 
3567       auto InsertPtOrError = createAndImportSubInstructionRenderer(
3568           ++InsertPt, Rule, DstChild, TempRegID);
3569       if (auto Error = InsertPtOrError.takeError())
3570         return std::move(Error);
3571       return InsertPtOrError.get();
3572     }
3573 
3574     return failedImport("Dst pattern child isn't a leaf node or an MBB" + llvm::to_string(*DstChild));
3575   }
3576 
3577   // It could be a specific immediate in which case we should just check for
3578   // that immediate.
3579   if (const IntInit *ChildIntInit =
3580           dyn_cast<IntInit>(DstChild->getLeafValue())) {
3581     DstMIBuilder.addRenderer<ImmRenderer>(ChildIntInit->getValue());
3582     return InsertPt;
3583   }
3584 
3585   // Otherwise, we're looking for a bog-standard RegisterClass operand.
3586   if (auto *ChildDefInit = dyn_cast<DefInit>(DstChild->getLeafValue())) {
3587     auto *ChildRec = ChildDefInit->getDef();
3588 
3589     ArrayRef<TypeSetByHwMode> ChildTypes = DstChild->getExtTypes();
3590     if (ChildTypes.size() != 1)
3591       return failedImport("Dst pattern child has multiple results");
3592 
3593     Optional<LLTCodeGen> OpTyOrNone = None;
3594     if (ChildTypes.front().isMachineValueType())
3595       OpTyOrNone = MVTToLLT(ChildTypes.front().getMachineValueType().SimpleTy);
3596     if (!OpTyOrNone)
3597       return failedImport("Dst operand has an unsupported type");
3598 
3599     if (ChildRec->isSubClassOf("Register")) {
3600       DstMIBuilder.addRenderer<AddRegisterRenderer>(ChildRec);
3601       return InsertPt;
3602     }
3603 
3604     if (ChildRec->isSubClassOf("RegisterClass") ||
3605         ChildRec->isSubClassOf("RegisterOperand") ||
3606         ChildRec->isSubClassOf("ValueType")) {
3607       if (ChildRec->isSubClassOf("RegisterOperand") &&
3608           !ChildRec->isValueUnset("GIZeroRegister")) {
3609         DstMIBuilder.addRenderer<CopyOrAddZeroRegRenderer>(
3610             DstChild->getName(), ChildRec->getValueAsDef("GIZeroRegister"));
3611         return InsertPt;
3612       }
3613 
3614       DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
3615       return InsertPt;
3616     }
3617 
3618     if (ChildRec->isSubClassOf("ComplexPattern")) {
3619       const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
3620       if (ComplexPattern == ComplexPatternEquivs.end())
3621         return failedImport(
3622             "SelectionDAG ComplexPattern not mapped to GlobalISel");
3623 
3624       const OperandMatcher &OM = Rule.getOperandMatcher(DstChild->getName());
3625       DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
3626           *ComplexPattern->second, DstChild->getName(),
3627           OM.getAllocatedTemporariesBaseID());
3628       return InsertPt;
3629     }
3630 
3631     return failedImport(
3632         "Dst pattern child def is an unsupported tablegen class");
3633   }
3634 
3635   return failedImport("Dst pattern child is an unsupported kind");
3636 }
3637 
createAndImportInstructionRenderer(RuleMatcher & M,const TreePatternNode * Dst)3638 Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
3639     RuleMatcher &M, const TreePatternNode *Dst) {
3640   auto InsertPtOrError = createInstructionRenderer(M.actions_end(), M, Dst);
3641   if (auto Error = InsertPtOrError.takeError())
3642     return std::move(Error);
3643 
3644   action_iterator InsertPt = InsertPtOrError.get();
3645   BuildMIAction &DstMIBuilder = *static_cast<BuildMIAction *>(InsertPt->get());
3646 
3647   importExplicitDefRenderers(DstMIBuilder);
3648 
3649   if (auto Error = importExplicitUseRenderers(InsertPt, M, DstMIBuilder, Dst)
3650                        .takeError())
3651     return std::move(Error);
3652 
3653   return DstMIBuilder;
3654 }
3655 
3656 Expected<action_iterator>
createAndImportSubInstructionRenderer(const action_iterator InsertPt,RuleMatcher & M,const TreePatternNode * Dst,unsigned TempRegID)3657 GlobalISelEmitter::createAndImportSubInstructionRenderer(
3658     const action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst,
3659     unsigned TempRegID) {
3660   auto InsertPtOrError = createInstructionRenderer(InsertPt, M, Dst);
3661 
3662   // TODO: Assert there's exactly one result.
3663 
3664   if (auto Error = InsertPtOrError.takeError())
3665     return std::move(Error);
3666 
3667   BuildMIAction &DstMIBuilder =
3668       *static_cast<BuildMIAction *>(InsertPtOrError.get()->get());
3669 
3670   // Assign the result to TempReg.
3671   DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID, true);
3672 
3673   InsertPtOrError =
3674       importExplicitUseRenderers(InsertPtOrError.get(), M, DstMIBuilder, Dst);
3675   if (auto Error = InsertPtOrError.takeError())
3676     return std::move(Error);
3677 
3678   M.insertAction<ConstrainOperandsToDefinitionAction>(InsertPt,
3679                                                       DstMIBuilder.getInsnID());
3680   return InsertPtOrError.get();
3681 }
3682 
createInstructionRenderer(action_iterator InsertPt,RuleMatcher & M,const TreePatternNode * Dst)3683 Expected<action_iterator> GlobalISelEmitter::createInstructionRenderer(
3684     action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst) {
3685   Record *DstOp = Dst->getOperator();
3686   if (!DstOp->isSubClassOf("Instruction")) {
3687     if (DstOp->isSubClassOf("ValueType"))
3688       return failedImport(
3689           "Pattern operator isn't an instruction (it's a ValueType)");
3690     return failedImport("Pattern operator isn't an instruction");
3691   }
3692   CodeGenInstruction *DstI = &Target.getInstruction(DstOp);
3693 
3694   // COPY_TO_REGCLASS is just a copy with a ConstrainOperandToRegClassAction
3695   // attached. Similarly for EXTRACT_SUBREG except that's a subregister copy.
3696   if (DstI->TheDef->getName() == "COPY_TO_REGCLASS")
3697     DstI = &Target.getInstruction(RK.getDef("COPY"));
3698   else if (DstI->TheDef->getName() == "EXTRACT_SUBREG")
3699     DstI = &Target.getInstruction(RK.getDef("COPY"));
3700   else if (DstI->TheDef->getName() == "REG_SEQUENCE")
3701     return failedImport("Unable to emit REG_SEQUENCE");
3702 
3703   return M.insertAction<BuildMIAction>(InsertPt, M.allocateOutputInsnID(),
3704                                        DstI);
3705 }
3706 
importExplicitDefRenderers(BuildMIAction & DstMIBuilder)3707 void GlobalISelEmitter::importExplicitDefRenderers(
3708     BuildMIAction &DstMIBuilder) {
3709   const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
3710   for (unsigned I = 0; I < DstI->Operands.NumDefs; ++I) {
3711     const CGIOperandList::OperandInfo &DstIOperand = DstI->Operands[I];
3712     DstMIBuilder.addRenderer<CopyRenderer>(DstIOperand.Name);
3713   }
3714 }
3715 
importExplicitUseRenderers(action_iterator InsertPt,RuleMatcher & M,BuildMIAction & DstMIBuilder,const llvm::TreePatternNode * Dst)3716 Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderers(
3717     action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
3718     const llvm::TreePatternNode *Dst) {
3719   const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
3720   CodeGenInstruction *OrigDstI = &Target.getInstruction(Dst->getOperator());
3721 
3722   // EXTRACT_SUBREG needs to use a subregister COPY.
3723   if (OrigDstI->TheDef->getName() == "EXTRACT_SUBREG") {
3724     if (!Dst->getChild(0)->isLeaf())
3725       return failedImport("EXTRACT_SUBREG child #1 is not a leaf");
3726 
3727     if (DefInit *SubRegInit =
3728             dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue())) {
3729       Record *RCDef = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
3730       if (!RCDef)
3731         return failedImport("EXTRACT_SUBREG child #0 could not "
3732                             "be coerced to a register class");
3733 
3734       CodeGenRegisterClass *RC = CGRegs.getRegClass(RCDef);
3735       CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
3736 
3737       const auto &SrcRCDstRCPair =
3738           RC->getMatchingSubClassWithSubRegs(CGRegs, SubIdx);
3739       if (SrcRCDstRCPair.hasValue()) {
3740         assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
3741         if (SrcRCDstRCPair->first != RC)
3742           return failedImport("EXTRACT_SUBREG requires an additional COPY");
3743       }
3744 
3745       DstMIBuilder.addRenderer<CopySubRegRenderer>(Dst->getChild(0)->getName(),
3746                                                    SubIdx);
3747       return InsertPt;
3748     }
3749 
3750     return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
3751   }
3752 
3753   // Render the explicit uses.
3754   unsigned DstINumUses = OrigDstI->Operands.size() - OrigDstI->Operands.NumDefs;
3755   unsigned ExpectedDstINumUses = Dst->getNumChildren();
3756   if (OrigDstI->TheDef->getName() == "COPY_TO_REGCLASS") {
3757     DstINumUses--; // Ignore the class constraint.
3758     ExpectedDstINumUses--;
3759   }
3760 
3761   unsigned Child = 0;
3762   unsigned NumDefaultOps = 0;
3763   for (unsigned I = 0; I != DstINumUses; ++I) {
3764     const CGIOperandList::OperandInfo &DstIOperand =
3765         DstI->Operands[DstI->Operands.NumDefs + I];
3766 
3767     // If the operand has default values, introduce them now.
3768     // FIXME: Until we have a decent test case that dictates we should do
3769     // otherwise, we're going to assume that operands with default values cannot
3770     // be specified in the patterns. Therefore, adding them will not cause us to
3771     // end up with too many rendered operands.
3772     if (DstIOperand.Rec->isSubClassOf("OperandWithDefaultOps")) {
3773       DagInit *DefaultOps = DstIOperand.Rec->getValueAsDag("DefaultOps");
3774       if (auto Error = importDefaultOperandRenderers(DstMIBuilder, DefaultOps))
3775         return std::move(Error);
3776       ++NumDefaultOps;
3777       continue;
3778     }
3779 
3780     auto InsertPtOrError = importExplicitUseRenderer(InsertPt, M, DstMIBuilder,
3781                                                      Dst->getChild(Child));
3782     if (auto Error = InsertPtOrError.takeError())
3783       return std::move(Error);
3784     InsertPt = InsertPtOrError.get();
3785     ++Child;
3786   }
3787 
3788   if (NumDefaultOps + ExpectedDstINumUses != DstINumUses)
3789     return failedImport("Expected " + llvm::to_string(DstINumUses) +
3790                         " used operands but found " +
3791                         llvm::to_string(ExpectedDstINumUses) +
3792                         " explicit ones and " + llvm::to_string(NumDefaultOps) +
3793                         " default ones");
3794 
3795   return InsertPt;
3796 }
3797 
importDefaultOperandRenderers(BuildMIAction & DstMIBuilder,DagInit * DefaultOps) const3798 Error GlobalISelEmitter::importDefaultOperandRenderers(
3799     BuildMIAction &DstMIBuilder, DagInit *DefaultOps) const {
3800   for (const auto *DefaultOp : DefaultOps->getArgs()) {
3801     // Look through ValueType operators.
3802     if (const DagInit *DefaultDagOp = dyn_cast<DagInit>(DefaultOp)) {
3803       if (const DefInit *DefaultDagOperator =
3804               dyn_cast<DefInit>(DefaultDagOp->getOperator())) {
3805         if (DefaultDagOperator->getDef()->isSubClassOf("ValueType"))
3806           DefaultOp = DefaultDagOp->getArg(0);
3807       }
3808     }
3809 
3810     if (const DefInit *DefaultDefOp = dyn_cast<DefInit>(DefaultOp)) {
3811       DstMIBuilder.addRenderer<AddRegisterRenderer>(DefaultDefOp->getDef());
3812       continue;
3813     }
3814 
3815     if (const IntInit *DefaultIntOp = dyn_cast<IntInit>(DefaultOp)) {
3816       DstMIBuilder.addRenderer<ImmRenderer>(DefaultIntOp->getValue());
3817       continue;
3818     }
3819 
3820     return failedImport("Could not add default op");
3821   }
3822 
3823   return Error::success();
3824 }
3825 
importImplicitDefRenderers(BuildMIAction & DstMIBuilder,const std::vector<Record * > & ImplicitDefs) const3826 Error GlobalISelEmitter::importImplicitDefRenderers(
3827     BuildMIAction &DstMIBuilder,
3828     const std::vector<Record *> &ImplicitDefs) const {
3829   if (!ImplicitDefs.empty())
3830     return failedImport("Pattern defines a physical register");
3831   return Error::success();
3832 }
3833 
runOnPattern(const PatternToMatch & P)3834 Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
3835   // Keep track of the matchers and actions to emit.
3836   int Score = P.getPatternComplexity(CGP);
3837   RuleMatcher M(P.getSrcRecord()->getLoc());
3838   RuleMatcherScores[M.getRuleID()] = Score;
3839   M.addAction<DebugCommentAction>(llvm::to_string(*P.getSrcPattern()) +
3840                                   "  =>  " +
3841                                   llvm::to_string(*P.getDstPattern()));
3842 
3843   if (auto Error = importRulePredicates(M, P.getPredicates()))
3844     return std::move(Error);
3845 
3846   // Next, analyze the pattern operators.
3847   TreePatternNode *Src = P.getSrcPattern();
3848   TreePatternNode *Dst = P.getDstPattern();
3849 
3850   // If the root of either pattern isn't a simple operator, ignore it.
3851   if (auto Err = isTrivialOperatorNode(Dst))
3852     return failedImport("Dst pattern root isn't a trivial operator (" +
3853                         toString(std::move(Err)) + ")");
3854   if (auto Err = isTrivialOperatorNode(Src))
3855     return failedImport("Src pattern root isn't a trivial operator (" +
3856                         toString(std::move(Err)) + ")");
3857 
3858   // The different predicates and matchers created during
3859   // addInstructionMatcher use the RuleMatcher M to set up their
3860   // instruction ID (InsnVarID) that are going to be used when
3861   // M is going to be emitted.
3862   // However, the code doing the emission still relies on the IDs
3863   // returned during that process by the RuleMatcher when issuing
3864   // the recordInsn opcodes.
3865   // Because of that:
3866   // 1. The order in which we created the predicates
3867   //    and such must be the same as the order in which we emit them,
3868   //    and
3869   // 2. We need to reset the generation of the IDs in M somewhere between
3870   //    addInstructionMatcher and emit
3871   //
3872   // FIXME: Long term, we don't want to have to rely on this implicit
3873   // naming being the same. One possible solution would be to have
3874   // explicit operator for operation capture and reference those.
3875   // The plus side is that it would expose opportunities to share
3876   // the capture accross rules. The downside is that it would
3877   // introduce a dependency between predicates (captures must happen
3878   // before their first use.)
3879   InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher(Src->getName());
3880   unsigned TempOpIdx = 0;
3881   auto InsnMatcherOrError =
3882       createAndImportSelDAGMatcher(M, InsnMatcherTemp, Src, TempOpIdx);
3883   if (auto Error = InsnMatcherOrError.takeError())
3884     return std::move(Error);
3885   InstructionMatcher &InsnMatcher = InsnMatcherOrError.get();
3886 
3887   if (Dst->isLeaf()) {
3888     Record *RCDef = getInitValueAsRegClass(Dst->getLeafValue());
3889 
3890     const CodeGenRegisterClass &RC = Target.getRegisterClass(RCDef);
3891     if (RCDef) {
3892       // We need to replace the def and all its uses with the specified
3893       // operand. However, we must also insert COPY's wherever needed.
3894       // For now, emit a copy and let the register allocator clean up.
3895       auto &DstI = Target.getInstruction(RK.getDef("COPY"));
3896       const auto &DstIOperand = DstI.Operands[0];
3897 
3898       OperandMatcher &OM0 = InsnMatcher.getOperand(0);
3899       OM0.setSymbolicName(DstIOperand.Name);
3900       M.defineOperand(OM0.getSymbolicName(), OM0);
3901       OM0.addPredicate<RegisterBankOperandMatcher>(RC);
3902 
3903       auto &DstMIBuilder =
3904           M.addAction<BuildMIAction>(M.allocateOutputInsnID(), &DstI);
3905       DstMIBuilder.addRenderer<CopyRenderer>(DstIOperand.Name);
3906       DstMIBuilder.addRenderer<CopyRenderer>(Dst->getName());
3907       M.addAction<ConstrainOperandToRegClassAction>(0, 0, RC);
3908 
3909       // We're done with this pattern!  It's eligible for GISel emission; return
3910       // it.
3911       ++NumPatternImported;
3912       return std::move(M);
3913     }
3914 
3915     return failedImport("Dst pattern root isn't a known leaf");
3916   }
3917 
3918   // Start with the defined operands (i.e., the results of the root operator).
3919   Record *DstOp = Dst->getOperator();
3920   if (!DstOp->isSubClassOf("Instruction"))
3921     return failedImport("Pattern operator isn't an instruction");
3922 
3923   auto &DstI = Target.getInstruction(DstOp);
3924   if (DstI.Operands.NumDefs != Src->getExtTypes().size())
3925     return failedImport("Src pattern results and dst MI defs are different (" +
3926                         to_string(Src->getExtTypes().size()) + " def(s) vs " +
3927                         to_string(DstI.Operands.NumDefs) + " def(s))");
3928 
3929   // The root of the match also has constraints on the register bank so that it
3930   // matches the result instruction.
3931   unsigned OpIdx = 0;
3932   for (const TypeSetByHwMode &VTy : Src->getExtTypes()) {
3933     (void)VTy;
3934 
3935     const auto &DstIOperand = DstI.Operands[OpIdx];
3936     Record *DstIOpRec = DstIOperand.Rec;
3937     if (DstI.TheDef->getName() == "COPY_TO_REGCLASS") {
3938       DstIOpRec = getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());
3939 
3940       if (DstIOpRec == nullptr)
3941         return failedImport(
3942             "COPY_TO_REGCLASS operand #1 isn't a register class");
3943     } else if (DstI.TheDef->getName() == "EXTRACT_SUBREG") {
3944       if (!Dst->getChild(0)->isLeaf())
3945         return failedImport("EXTRACT_SUBREG operand #0 isn't a leaf");
3946 
3947       // We can assume that a subregister is in the same bank as it's super
3948       // register.
3949       DstIOpRec = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
3950 
3951       if (DstIOpRec == nullptr)
3952         return failedImport(
3953             "EXTRACT_SUBREG operand #0 isn't a register class");
3954     } else if (DstIOpRec->isSubClassOf("RegisterOperand"))
3955       DstIOpRec = DstIOpRec->getValueAsDef("RegClass");
3956     else if (!DstIOpRec->isSubClassOf("RegisterClass"))
3957       return failedImport("Dst MI def isn't a register class" +
3958                           to_string(*Dst));
3959 
3960     OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
3961     OM.setSymbolicName(DstIOperand.Name);
3962     M.defineOperand(OM.getSymbolicName(), OM);
3963     OM.addPredicate<RegisterBankOperandMatcher>(
3964         Target.getRegisterClass(DstIOpRec));
3965     ++OpIdx;
3966   }
3967 
3968   auto DstMIBuilderOrError = createAndImportInstructionRenderer(M, Dst);
3969   if (auto Error = DstMIBuilderOrError.takeError())
3970     return std::move(Error);
3971   BuildMIAction &DstMIBuilder = DstMIBuilderOrError.get();
3972 
3973   // Render the implicit defs.
3974   // These are only added to the root of the result.
3975   if (auto Error = importImplicitDefRenderers(DstMIBuilder, P.getDstRegs()))
3976     return std::move(Error);
3977 
3978   DstMIBuilder.chooseInsnToMutate(M);
3979 
3980   // Constrain the registers to classes. This is normally derived from the
3981   // emitted instruction but a few instructions require special handling.
3982   if (DstI.TheDef->getName() == "COPY_TO_REGCLASS") {
3983     // COPY_TO_REGCLASS does not provide operand constraints itself but the
3984     // result is constrained to the class given by the second child.
3985     Record *DstIOpRec =
3986         getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());
3987 
3988     if (DstIOpRec == nullptr)
3989       return failedImport("COPY_TO_REGCLASS operand #1 isn't a register class");
3990 
3991     M.addAction<ConstrainOperandToRegClassAction>(
3992         0, 0, Target.getRegisterClass(DstIOpRec));
3993 
3994     // We're done with this pattern!  It's eligible for GISel emission; return
3995     // it.
3996     ++NumPatternImported;
3997     return std::move(M);
3998   }
3999 
4000   if (DstI.TheDef->getName() == "EXTRACT_SUBREG") {
4001     // EXTRACT_SUBREG selects into a subregister COPY but unlike most
4002     // instructions, the result register class is controlled by the
4003     // subregisters of the operand. As a result, we must constrain the result
4004     // class rather than check that it's already the right one.
4005     if (!Dst->getChild(0)->isLeaf())
4006       return failedImport("EXTRACT_SUBREG child #1 is not a leaf");
4007 
4008     DefInit *SubRegInit = dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue());
4009     if (!SubRegInit)
4010       return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
4011 
4012     // Constrain the result to the same register bank as the operand.
4013     Record *DstIOpRec =
4014         getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
4015 
4016     if (DstIOpRec == nullptr)
4017       return failedImport("EXTRACT_SUBREG operand #1 isn't a register class");
4018 
4019     CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
4020     CodeGenRegisterClass *SrcRC = CGRegs.getRegClass(DstIOpRec);
4021 
4022     // It would be nice to leave this constraint implicit but we're required
4023     // to pick a register class so constrain the result to a register class
4024     // that can hold the correct MVT.
4025     //
4026     // FIXME: This may introduce an extra copy if the chosen class doesn't
4027     //        actually contain the subregisters.
4028     assert(Src->getExtTypes().size() == 1 &&
4029              "Expected Src of EXTRACT_SUBREG to have one result type");
4030 
4031     const auto &SrcRCDstRCPair =
4032         SrcRC->getMatchingSubClassWithSubRegs(CGRegs, SubIdx);
4033     assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
4034     M.addAction<ConstrainOperandToRegClassAction>(0, 0, *SrcRCDstRCPair->second);
4035     M.addAction<ConstrainOperandToRegClassAction>(0, 1, *SrcRCDstRCPair->first);
4036 
4037     // We're done with this pattern!  It's eligible for GISel emission; return
4038     // it.
4039     ++NumPatternImported;
4040     return std::move(M);
4041   }
4042 
4043   M.addAction<ConstrainOperandsToDefinitionAction>(0);
4044 
4045   // We're done with this pattern!  It's eligible for GISel emission; return it.
4046   ++NumPatternImported;
4047   return std::move(M);
4048 }
4049 
4050 // Emit imm predicate table and an enum to reference them with.
4051 // The 'Predicate_' part of the name is redundant but eliminating it is more
4052 // trouble than it's worth.
emitCxxPredicateFns(raw_ostream & OS,StringRef CodeFieldName,StringRef TypeIdentifier,StringRef ArgType,StringRef ArgName,StringRef AdditionalDeclarations,std::function<bool (const Record * R)> Filter)4053 void GlobalISelEmitter::emitCxxPredicateFns(
4054     raw_ostream &OS, StringRef CodeFieldName, StringRef TypeIdentifier,
4055     StringRef ArgType, StringRef ArgName, StringRef AdditionalDeclarations,
4056     std::function<bool(const Record *R)> Filter) {
4057   std::vector<const Record *> MatchedRecords;
4058   const auto &Defs = RK.getAllDerivedDefinitions("PatFrag");
4059   std::copy_if(Defs.begin(), Defs.end(), std::back_inserter(MatchedRecords),
4060                [&](Record *Record) {
4061                  return !Record->getValueAsString(CodeFieldName).empty() &&
4062                         Filter(Record);
4063                });
4064 
4065   if (!MatchedRecords.empty()) {
4066     OS << "// PatFrag predicates.\n"
4067        << "enum {\n";
4068     std::string EnumeratorSeparator =
4069         (" = GIPFP_" + TypeIdentifier + "_Invalid + 1,\n").str();
4070     for (const auto *Record : MatchedRecords) {
4071       OS << "  GIPFP_" << TypeIdentifier << "_Predicate_" << Record->getName()
4072          << EnumeratorSeparator;
4073       EnumeratorSeparator = ",\n";
4074     }
4075     OS << "};\n";
4076   }
4077 
4078   OS << "bool " << Target.getName() << "InstructionSelector::test" << ArgName
4079      << "Predicate_" << TypeIdentifier << "(unsigned PredicateID, " << ArgType << " "
4080      << ArgName << ") const {\n"
4081      << AdditionalDeclarations;
4082   if (!AdditionalDeclarations.empty())
4083     OS << "\n";
4084   if (!MatchedRecords.empty())
4085     OS << "  switch (PredicateID) {\n";
4086   for (const auto *Record : MatchedRecords) {
4087     OS << "  case GIPFP_" << TypeIdentifier << "_Predicate_"
4088        << Record->getName() << ": {\n"
4089        << "    " << Record->getValueAsString(CodeFieldName) << "\n"
4090        << "    llvm_unreachable(\"" << CodeFieldName
4091        << " should have returned\");\n"
4092        << "    return false;\n"
4093        << "  }\n";
4094   }
4095   if (!MatchedRecords.empty())
4096     OS << "  }\n";
4097   OS << "  llvm_unreachable(\"Unknown predicate\");\n"
4098      << "  return false;\n"
4099      << "}\n";
4100 }
4101 
emitImmPredicateFns(raw_ostream & OS,StringRef TypeIdentifier,StringRef ArgType,std::function<bool (const Record * R)> Filter)4102 void GlobalISelEmitter::emitImmPredicateFns(
4103     raw_ostream &OS, StringRef TypeIdentifier, StringRef ArgType,
4104     std::function<bool(const Record *R)> Filter) {
4105   return emitCxxPredicateFns(OS, "ImmediateCode", TypeIdentifier, ArgType,
4106                              "Imm", "", Filter);
4107 }
4108 
emitMIPredicateFns(raw_ostream & OS)4109 void GlobalISelEmitter::emitMIPredicateFns(raw_ostream &OS) {
4110   return emitCxxPredicateFns(
4111       OS, "GISelPredicateCode", "MI", "const MachineInstr &", "MI",
4112       "  const MachineFunction &MF = *MI.getParent()->getParent();\n"
4113       "  const MachineRegisterInfo &MRI = MF.getRegInfo();\n"
4114       "  (void)MRI;",
4115       [](const Record *R) { return true; });
4116 }
4117 
4118 template <class GroupT>
optimizeRules(ArrayRef<Matcher * > Rules,std::vector<std::unique_ptr<Matcher>> & MatcherStorage)4119 std::vector<Matcher *> GlobalISelEmitter::optimizeRules(
4120     ArrayRef<Matcher *> Rules,
4121     std::vector<std::unique_ptr<Matcher>> &MatcherStorage) {
4122 
4123   std::vector<Matcher *> OptRules;
4124   std::unique_ptr<GroupT> CurrentGroup = make_unique<GroupT>();
4125   assert(CurrentGroup->empty() && "Newly created group isn't empty!");
4126   unsigned NumGroups = 0;
4127 
4128   auto ProcessCurrentGroup = [&]() {
4129     if (CurrentGroup->empty())
4130       // An empty group is good to be reused:
4131       return;
4132 
4133     // If the group isn't large enough to provide any benefit, move all the
4134     // added rules out of it and make sure to re-create the group to properly
4135     // re-initialize it:
4136     if (CurrentGroup->size() < 2)
4137       for (Matcher *M : CurrentGroup->matchers())
4138         OptRules.push_back(M);
4139     else {
4140       CurrentGroup->finalize();
4141       OptRules.push_back(CurrentGroup.get());
4142       MatcherStorage.emplace_back(std::move(CurrentGroup));
4143       ++NumGroups;
4144     }
4145     CurrentGroup = make_unique<GroupT>();
4146   };
4147   for (Matcher *Rule : Rules) {
4148     // Greedily add as many matchers as possible to the current group:
4149     if (CurrentGroup->addMatcher(*Rule))
4150       continue;
4151 
4152     ProcessCurrentGroup();
4153     assert(CurrentGroup->empty() && "A group wasn't properly re-initialized");
4154 
4155     // Try to add the pending matcher to a newly created empty group:
4156     if (!CurrentGroup->addMatcher(*Rule))
4157       // If we couldn't add the matcher to an empty group, that group type
4158       // doesn't support that kind of matchers at all, so just skip it:
4159       OptRules.push_back(Rule);
4160   }
4161   ProcessCurrentGroup();
4162 
4163   LLVM_DEBUG(dbgs() << "NumGroups: " << NumGroups << "\n");
4164   assert(CurrentGroup->empty() && "The last group wasn't properly processed");
4165   return OptRules;
4166 }
4167 
4168 MatchTable
buildMatchTable(MutableArrayRef<RuleMatcher> Rules,bool Optimize,bool WithCoverage)4169 GlobalISelEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules,
4170                                    bool Optimize, bool WithCoverage) {
4171   std::vector<Matcher *> InputRules;
4172   for (Matcher &Rule : Rules)
4173     InputRules.push_back(&Rule);
4174 
4175   if (!Optimize)
4176     return MatchTable::buildTable(InputRules, WithCoverage);
4177 
4178   unsigned CurrentOrdering = 0;
4179   StringMap<unsigned> OpcodeOrder;
4180   for (RuleMatcher &Rule : Rules) {
4181     const StringRef Opcode = Rule.getOpcode();
4182     assert(!Opcode.empty() && "Didn't expect an undefined opcode");
4183     if (OpcodeOrder.count(Opcode) == 0)
4184       OpcodeOrder[Opcode] = CurrentOrdering++;
4185   }
4186 
4187   std::stable_sort(InputRules.begin(), InputRules.end(),
4188                    [&OpcodeOrder](const Matcher *A, const Matcher *B) {
4189                      auto *L = static_cast<const RuleMatcher *>(A);
4190                      auto *R = static_cast<const RuleMatcher *>(B);
4191                      return std::make_tuple(OpcodeOrder[L->getOpcode()],
4192                                             L->getNumOperands()) <
4193                             std::make_tuple(OpcodeOrder[R->getOpcode()],
4194                                             R->getNumOperands());
4195                    });
4196 
4197   for (Matcher *Rule : InputRules)
4198     Rule->optimize();
4199 
4200   std::vector<std::unique_ptr<Matcher>> MatcherStorage;
4201   std::vector<Matcher *> OptRules =
4202       optimizeRules<GroupMatcher>(InputRules, MatcherStorage);
4203 
4204   for (Matcher *Rule : OptRules)
4205     Rule->optimize();
4206 
4207   OptRules = optimizeRules<SwitchMatcher>(OptRules, MatcherStorage);
4208 
4209   return MatchTable::buildTable(OptRules, WithCoverage);
4210 }
4211 
optimize()4212 void GroupMatcher::optimize() {
4213   // Make sure we only sort by a specific predicate within a range of rules that
4214   // all have that predicate checked against a specific value (not a wildcard):
4215   auto F = Matchers.begin();
4216   auto T = F;
4217   auto E = Matchers.end();
4218   while (T != E) {
4219     while (T != E) {
4220       auto *R = static_cast<RuleMatcher *>(*T);
4221       if (!R->getFirstConditionAsRootType().get().isValid())
4222         break;
4223       ++T;
4224     }
4225     std::stable_sort(F, T, [](Matcher *A, Matcher *B) {
4226       auto *L = static_cast<RuleMatcher *>(A);
4227       auto *R = static_cast<RuleMatcher *>(B);
4228       return L->getFirstConditionAsRootType() <
4229              R->getFirstConditionAsRootType();
4230     });
4231     if (T != E)
4232       F = ++T;
4233   }
4234   GlobalISelEmitter::optimizeRules<GroupMatcher>(Matchers, MatcherStorage)
4235       .swap(Matchers);
4236   GlobalISelEmitter::optimizeRules<SwitchMatcher>(Matchers, MatcherStorage)
4237       .swap(Matchers);
4238 }
4239 
run(raw_ostream & OS)4240 void GlobalISelEmitter::run(raw_ostream &OS) {
4241   if (!UseCoverageFile.empty()) {
4242     RuleCoverage = CodeGenCoverage();
4243     auto RuleCoverageBufOrErr = MemoryBuffer::getFile(UseCoverageFile);
4244     if (!RuleCoverageBufOrErr) {
4245       PrintWarning(SMLoc(), "Missing rule coverage data");
4246       RuleCoverage = None;
4247     } else {
4248       if (!RuleCoverage->parse(*RuleCoverageBufOrErr.get(), Target.getName())) {
4249         PrintWarning(SMLoc(), "Ignoring invalid or missing rule coverage data");
4250         RuleCoverage = None;
4251       }
4252     }
4253   }
4254 
4255   // Track the run-time opcode values
4256   gatherOpcodeValues();
4257   // Track the run-time LLT ID values
4258   gatherTypeIDValues();
4259 
4260   // Track the GINodeEquiv definitions.
4261   gatherNodeEquivs();
4262 
4263   emitSourceFileHeader(("Global Instruction Selector for the " +
4264                        Target.getName() + " target").str(), OS);
4265   std::vector<RuleMatcher> Rules;
4266   // Look through the SelectionDAG patterns we found, possibly emitting some.
4267   for (const PatternToMatch &Pat : CGP.ptms()) {
4268     ++NumPatternTotal;
4269 
4270     auto MatcherOrErr = runOnPattern(Pat);
4271 
4272     // The pattern analysis can fail, indicating an unsupported pattern.
4273     // Report that if we've been asked to do so.
4274     if (auto Err = MatcherOrErr.takeError()) {
4275       if (WarnOnSkippedPatterns) {
4276         PrintWarning(Pat.getSrcRecord()->getLoc(),
4277                      "Skipped pattern: " + toString(std::move(Err)));
4278       } else {
4279         consumeError(std::move(Err));
4280       }
4281       ++NumPatternImportsSkipped;
4282       continue;
4283     }
4284 
4285     if (RuleCoverage) {
4286       if (RuleCoverage->isCovered(MatcherOrErr->getRuleID()))
4287         ++NumPatternsTested;
4288       else
4289         PrintWarning(Pat.getSrcRecord()->getLoc(),
4290                      "Pattern is not covered by a test");
4291     }
4292     Rules.push_back(std::move(MatcherOrErr.get()));
4293   }
4294 
4295   // Comparison function to order records by name.
4296   auto orderByName = [](const Record *A, const Record *B) {
4297     return A->getName() < B->getName();
4298   };
4299 
4300   std::vector<Record *> ComplexPredicates =
4301       RK.getAllDerivedDefinitions("GIComplexOperandMatcher");
4302   llvm::sort(ComplexPredicates.begin(), ComplexPredicates.end(), orderByName);
4303 
4304   std::vector<Record *> CustomRendererFns =
4305       RK.getAllDerivedDefinitions("GICustomOperandRenderer");
4306   llvm::sort(CustomRendererFns.begin(), CustomRendererFns.end(), orderByName);
4307 
4308   unsigned MaxTemporaries = 0;
4309   for (const auto &Rule : Rules)
4310     MaxTemporaries = std::max(MaxTemporaries, Rule.countRendererFns());
4311 
4312   OS << "#ifdef GET_GLOBALISEL_PREDICATE_BITSET\n"
4313      << "const unsigned MAX_SUBTARGET_PREDICATES = " << SubtargetFeatures.size()
4314      << ";\n"
4315      << "using PredicateBitset = "
4316         "llvm::PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;\n"
4317      << "#endif // ifdef GET_GLOBALISEL_PREDICATE_BITSET\n\n";
4318 
4319   OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n"
4320      << "  mutable MatcherState State;\n"
4321      << "  typedef "
4322         "ComplexRendererFns("
4323      << Target.getName()
4324      << "InstructionSelector::*ComplexMatcherMemFn)(MachineOperand &) const;\n"
4325 
4326      << "  typedef void(" << Target.getName()
4327      << "InstructionSelector::*CustomRendererFn)(MachineInstrBuilder &, const "
4328         "MachineInstr&) "
4329         "const;\n"
4330      << "  const ISelInfoTy<PredicateBitset, ComplexMatcherMemFn, "
4331         "CustomRendererFn> "
4332         "ISelInfo;\n";
4333   OS << "  static " << Target.getName()
4334      << "InstructionSelector::ComplexMatcherMemFn ComplexPredicateFns[];\n"
4335      << "  static " << Target.getName()
4336      << "InstructionSelector::CustomRendererFn CustomRenderers[];\n"
4337      << "  bool testImmPredicate_I64(unsigned PredicateID, int64_t Imm) const "
4338         "override;\n"
4339      << "  bool testImmPredicate_APInt(unsigned PredicateID, const APInt &Imm) "
4340         "const override;\n"
4341      << "  bool testImmPredicate_APFloat(unsigned PredicateID, const APFloat "
4342         "&Imm) const override;\n"
4343      << "  const int64_t *getMatchTable() const override;\n"
4344      << "  bool testMIPredicate_MI(unsigned PredicateID, const MachineInstr &MI) "
4345         "const override;\n"
4346      << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n";
4347 
4348   OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n"
4349      << ", State(" << MaxTemporaries << "),\n"
4350      << "ISelInfo(TypeObjects, NumTypeObjects, FeatureBitsets"
4351      << ", ComplexPredicateFns, CustomRenderers)\n"
4352      << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";
4353 
4354   OS << "#ifdef GET_GLOBALISEL_IMPL\n";
4355   SubtargetFeatureInfo::emitSubtargetFeatureBitEnumeration(SubtargetFeatures,
4356                                                            OS);
4357 
4358   // Separate subtarget features by how often they must be recomputed.
4359   SubtargetFeatureInfoMap ModuleFeatures;
4360   std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
4361                std::inserter(ModuleFeatures, ModuleFeatures.end()),
4362                [](const SubtargetFeatureInfoMap::value_type &X) {
4363                  return !X.second.mustRecomputePerFunction();
4364                });
4365   SubtargetFeatureInfoMap FunctionFeatures;
4366   std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
4367                std::inserter(FunctionFeatures, FunctionFeatures.end()),
4368                [](const SubtargetFeatureInfoMap::value_type &X) {
4369                  return X.second.mustRecomputePerFunction();
4370                });
4371 
4372   SubtargetFeatureInfo::emitComputeAvailableFeatures(
4373       Target.getName(), "InstructionSelector", "computeAvailableModuleFeatures",
4374       ModuleFeatures, OS);
4375   SubtargetFeatureInfo::emitComputeAvailableFeatures(
4376       Target.getName(), "InstructionSelector",
4377       "computeAvailableFunctionFeatures", FunctionFeatures, OS,
4378       "const MachineFunction *MF");
4379 
4380   // Emit a table containing the LLT objects needed by the matcher and an enum
4381   // for the matcher to reference them with.
4382   std::vector<LLTCodeGen> TypeObjects;
4383   for (const auto &Ty : KnownTypes)
4384     TypeObjects.push_back(Ty);
4385   llvm::sort(TypeObjects.begin(), TypeObjects.end());
4386   OS << "// LLT Objects.\n"
4387      << "enum {\n";
4388   for (const auto &TypeObject : TypeObjects) {
4389     OS << "  ";
4390     TypeObject.emitCxxEnumValue(OS);
4391     OS << ",\n";
4392   }
4393   OS << "};\n";
4394   OS << "const static size_t NumTypeObjects = " << TypeObjects.size() << ";\n"
4395      << "const static LLT TypeObjects[] = {\n";
4396   for (const auto &TypeObject : TypeObjects) {
4397     OS << "  ";
4398     TypeObject.emitCxxConstructorCall(OS);
4399     OS << ",\n";
4400   }
4401   OS << "};\n\n";
4402 
4403   // Emit a table containing the PredicateBitsets objects needed by the matcher
4404   // and an enum for the matcher to reference them with.
4405   std::vector<std::vector<Record *>> FeatureBitsets;
4406   for (auto &Rule : Rules)
4407     FeatureBitsets.push_back(Rule.getRequiredFeatures());
4408   llvm::sort(
4409       FeatureBitsets.begin(), FeatureBitsets.end(),
4410       [&](const std::vector<Record *> &A, const std::vector<Record *> &B) {
4411         if (A.size() < B.size())
4412           return true;
4413         if (A.size() > B.size())
4414           return false;
4415         for (const auto &Pair : zip(A, B)) {
4416           if (std::get<0>(Pair)->getName() < std::get<1>(Pair)->getName())
4417             return true;
4418           if (std::get<0>(Pair)->getName() > std::get<1>(Pair)->getName())
4419             return false;
4420         }
4421         return false;
4422       });
4423   FeatureBitsets.erase(
4424       std::unique(FeatureBitsets.begin(), FeatureBitsets.end()),
4425       FeatureBitsets.end());
4426   OS << "// Feature bitsets.\n"
4427      << "enum {\n"
4428      << "  GIFBS_Invalid,\n";
4429   for (const auto &FeatureBitset : FeatureBitsets) {
4430     if (FeatureBitset.empty())
4431       continue;
4432     OS << "  " << getNameForFeatureBitset(FeatureBitset) << ",\n";
4433   }
4434   OS << "};\n"
4435      << "const static PredicateBitset FeatureBitsets[] {\n"
4436      << "  {}, // GIFBS_Invalid\n";
4437   for (const auto &FeatureBitset : FeatureBitsets) {
4438     if (FeatureBitset.empty())
4439       continue;
4440     OS << "  {";
4441     for (const auto &Feature : FeatureBitset) {
4442       const auto &I = SubtargetFeatures.find(Feature);
4443       assert(I != SubtargetFeatures.end() && "Didn't import predicate?");
4444       OS << I->second.getEnumBitName() << ", ";
4445     }
4446     OS << "},\n";
4447   }
4448   OS << "};\n\n";
4449 
4450   // Emit complex predicate table and an enum to reference them with.
4451   OS << "// ComplexPattern predicates.\n"
4452      << "enum {\n"
4453      << "  GICP_Invalid,\n";
4454   for (const auto &Record : ComplexPredicates)
4455     OS << "  GICP_" << Record->getName() << ",\n";
4456   OS << "};\n"
4457      << "// See constructor for table contents\n\n";
4458 
4459   emitImmPredicateFns(OS, "I64", "int64_t", [](const Record *R) {
4460     bool Unset;
4461     return !R->getValueAsBitOrUnset("IsAPFloat", Unset) &&
4462            !R->getValueAsBit("IsAPInt");
4463   });
4464   emitImmPredicateFns(OS, "APFloat", "const APFloat &", [](const Record *R) {
4465     bool Unset;
4466     return R->getValueAsBitOrUnset("IsAPFloat", Unset);
4467   });
4468   emitImmPredicateFns(OS, "APInt", "const APInt &", [](const Record *R) {
4469     return R->getValueAsBit("IsAPInt");
4470   });
4471   emitMIPredicateFns(OS);
4472   OS << "\n";
4473 
4474   OS << Target.getName() << "InstructionSelector::ComplexMatcherMemFn\n"
4475      << Target.getName() << "InstructionSelector::ComplexPredicateFns[] = {\n"
4476      << "  nullptr, // GICP_Invalid\n";
4477   for (const auto &Record : ComplexPredicates)
4478     OS << "  &" << Target.getName()
4479        << "InstructionSelector::" << Record->getValueAsString("MatcherFn")
4480        << ", // " << Record->getName() << "\n";
4481   OS << "};\n\n";
4482 
4483   OS << "// Custom renderers.\n"
4484      << "enum {\n"
4485      << "  GICR_Invalid,\n";
4486   for (const auto &Record : CustomRendererFns)
4487     OS << "  GICR_" << Record->getValueAsString("RendererFn") << ", \n";
4488   OS << "};\n";
4489 
4490   OS << Target.getName() << "InstructionSelector::CustomRendererFn\n"
4491      << Target.getName() << "InstructionSelector::CustomRenderers[] = {\n"
4492      << "  nullptr, // GICP_Invalid\n";
4493   for (const auto &Record : CustomRendererFns)
4494     OS << "  &" << Target.getName()
4495        << "InstructionSelector::" << Record->getValueAsString("RendererFn")
4496        << ", // " << Record->getName() << "\n";
4497   OS << "};\n\n";
4498 
4499   std::stable_sort(Rules.begin(), Rules.end(), [&](const RuleMatcher &A,
4500                                                    const RuleMatcher &B) {
4501     int ScoreA = RuleMatcherScores[A.getRuleID()];
4502     int ScoreB = RuleMatcherScores[B.getRuleID()];
4503     if (ScoreA > ScoreB)
4504       return true;
4505     if (ScoreB > ScoreA)
4506       return false;
4507     if (A.isHigherPriorityThan(B)) {
4508       assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
4509                                            "and less important at "
4510                                            "the same time");
4511       return true;
4512     }
4513     return false;
4514   });
4515 
4516   OS << "bool " << Target.getName()
4517      << "InstructionSelector::selectImpl(MachineInstr &I, CodeGenCoverage "
4518         "&CoverageInfo) const {\n"
4519      << "  MachineFunction &MF = *I.getParent()->getParent();\n"
4520      << "  MachineRegisterInfo &MRI = MF.getRegInfo();\n"
4521      << "  // FIXME: This should be computed on a per-function basis rather "
4522         "than per-insn.\n"
4523      << "  AvailableFunctionFeatures = computeAvailableFunctionFeatures(&STI, "
4524         "&MF);\n"
4525      << "  const PredicateBitset AvailableFeatures = getAvailableFeatures();\n"
4526      << "  NewMIVector OutMIs;\n"
4527      << "  State.MIs.clear();\n"
4528      << "  State.MIs.push_back(&I);\n\n"
4529      << "  if (executeMatchTable(*this, OutMIs, State, ISelInfo"
4530      << ", getMatchTable(), TII, MRI, TRI, RBI, AvailableFeatures"
4531      << ", CoverageInfo)) {\n"
4532      << "    return true;\n"
4533      << "  }\n\n"
4534      << "  return false;\n"
4535      << "}\n\n";
4536 
4537   const MatchTable Table =
4538       buildMatchTable(Rules, OptimizeMatchTable, GenerateCoverage);
4539   OS << "const int64_t *" << Target.getName()
4540      << "InstructionSelector::getMatchTable() const {\n";
4541   Table.emitDeclaration(OS);
4542   OS << "  return ";
4543   Table.emitUse(OS);
4544   OS << ";\n}\n";
4545   OS << "#endif // ifdef GET_GLOBALISEL_IMPL\n";
4546 
4547   OS << "#ifdef GET_GLOBALISEL_PREDICATES_DECL\n"
4548      << "PredicateBitset AvailableModuleFeatures;\n"
4549      << "mutable PredicateBitset AvailableFunctionFeatures;\n"
4550      << "PredicateBitset getAvailableFeatures() const {\n"
4551      << "  return AvailableModuleFeatures | AvailableFunctionFeatures;\n"
4552      << "}\n"
4553      << "PredicateBitset\n"
4554      << "computeAvailableModuleFeatures(const " << Target.getName()
4555      << "Subtarget *Subtarget) const;\n"
4556      << "PredicateBitset\n"
4557      << "computeAvailableFunctionFeatures(const " << Target.getName()
4558      << "Subtarget *Subtarget,\n"
4559      << "                                 const MachineFunction *MF) const;\n"
4560      << "#endif // ifdef GET_GLOBALISEL_PREDICATES_DECL\n";
4561 
4562   OS << "#ifdef GET_GLOBALISEL_PREDICATES_INIT\n"
4563      << "AvailableModuleFeatures(computeAvailableModuleFeatures(&STI)),\n"
4564      << "AvailableFunctionFeatures()\n"
4565      << "#endif // ifdef GET_GLOBALISEL_PREDICATES_INIT\n";
4566 }
4567 
declareSubtargetFeature(Record * Predicate)4568 void GlobalISelEmitter::declareSubtargetFeature(Record *Predicate) {
4569   if (SubtargetFeatures.count(Predicate) == 0)
4570     SubtargetFeatures.emplace(
4571         Predicate, SubtargetFeatureInfo(Predicate, SubtargetFeatures.size()));
4572 }
4573 
optimize()4574 void RuleMatcher::optimize() {
4575   for (auto &Item : InsnVariableIDs) {
4576     InstructionMatcher &InsnMatcher = *Item.first;
4577     for (auto &OM : InsnMatcher.operands()) {
4578       // Complex Patterns are usually expensive and they relatively rarely fail
4579       // on their own: more often we end up throwing away all the work done by a
4580       // matching part of a complex pattern because some other part of the
4581       // enclosing pattern didn't match. All of this makes it beneficial to
4582       // delay complex patterns until the very end of the rule matching,
4583       // especially for targets having lots of complex patterns.
4584       for (auto &OP : OM->predicates())
4585         if (isa<ComplexPatternOperandMatcher>(OP))
4586           EpilogueMatchers.emplace_back(std::move(OP));
4587       OM->eraseNullPredicates();
4588     }
4589     InsnMatcher.optimize();
4590   }
4591   llvm::sort(
4592       EpilogueMatchers.begin(), EpilogueMatchers.end(),
4593       [](const std::unique_ptr<PredicateMatcher> &L,
4594          const std::unique_ptr<PredicateMatcher> &R) {
4595         return std::make_tuple(L->getKind(), L->getInsnVarID(), L->getOpIdx()) <
4596                std::make_tuple(R->getKind(), R->getInsnVarID(), R->getOpIdx());
4597       });
4598 }
4599 
hasFirstCondition() const4600 bool RuleMatcher::hasFirstCondition() const {
4601   if (insnmatchers_empty())
4602     return false;
4603   InstructionMatcher &Matcher = insnmatchers_front();
4604   if (!Matcher.predicates_empty())
4605     return true;
4606   for (auto &OM : Matcher.operands())
4607     for (auto &OP : OM->predicates())
4608       if (!isa<InstructionOperandMatcher>(OP))
4609         return true;
4610   return false;
4611 }
4612 
getFirstCondition() const4613 const PredicateMatcher &RuleMatcher::getFirstCondition() const {
4614   assert(!insnmatchers_empty() &&
4615          "Trying to get a condition from an empty RuleMatcher");
4616 
4617   InstructionMatcher &Matcher = insnmatchers_front();
4618   if (!Matcher.predicates_empty())
4619     return **Matcher.predicates_begin();
4620   // If there is no more predicate on the instruction itself, look at its
4621   // operands.
4622   for (auto &OM : Matcher.operands())
4623     for (auto &OP : OM->predicates())
4624       if (!isa<InstructionOperandMatcher>(OP))
4625         return *OP;
4626 
4627   llvm_unreachable("Trying to get a condition from an InstructionMatcher with "
4628                    "no conditions");
4629 }
4630 
popFirstCondition()4631 std::unique_ptr<PredicateMatcher> RuleMatcher::popFirstCondition() {
4632   assert(!insnmatchers_empty() &&
4633          "Trying to pop a condition from an empty RuleMatcher");
4634 
4635   InstructionMatcher &Matcher = insnmatchers_front();
4636   if (!Matcher.predicates_empty())
4637     return Matcher.predicates_pop_front();
4638   // If there is no more predicate on the instruction itself, look at its
4639   // operands.
4640   for (auto &OM : Matcher.operands())
4641     for (auto &OP : OM->predicates())
4642       if (!isa<InstructionOperandMatcher>(OP)) {
4643         std::unique_ptr<PredicateMatcher> Result = std::move(OP);
4644         OM->eraseNullPredicates();
4645         return Result;
4646       }
4647 
4648   llvm_unreachable("Trying to pop a condition from an InstructionMatcher with "
4649                    "no conditions");
4650 }
4651 
candidateConditionMatches(const PredicateMatcher & Predicate) const4652 bool GroupMatcher::candidateConditionMatches(
4653     const PredicateMatcher &Predicate) const {
4654 
4655   if (empty()) {
4656     // Sharing predicates for nested instructions is not supported yet as we
4657     // currently don't hoist the GIM_RecordInsn's properly, therefore we can
4658     // only work on the original root instruction (InsnVarID == 0):
4659     if (Predicate.getInsnVarID() != 0)
4660       return false;
4661     // ... otherwise an empty group can handle any predicate with no specific
4662     // requirements:
4663     return true;
4664   }
4665 
4666   const Matcher &Representative = **Matchers.begin();
4667   const auto &RepresentativeCondition = Representative.getFirstCondition();
4668   // ... if not empty, the group can only accomodate matchers with the exact
4669   // same first condition:
4670   return Predicate.isIdentical(RepresentativeCondition);
4671 }
4672 
addMatcher(Matcher & Candidate)4673 bool GroupMatcher::addMatcher(Matcher &Candidate) {
4674   if (!Candidate.hasFirstCondition())
4675     return false;
4676 
4677   const PredicateMatcher &Predicate = Candidate.getFirstCondition();
4678   if (!candidateConditionMatches(Predicate))
4679     return false;
4680 
4681   Matchers.push_back(&Candidate);
4682   return true;
4683 }
4684 
finalize()4685 void GroupMatcher::finalize() {
4686   assert(Conditions.empty() && "Already finalized?");
4687   if (empty())
4688     return;
4689 
4690   Matcher &FirstRule = **Matchers.begin();
4691   for (;;) {
4692     // All the checks are expected to succeed during the first iteration:
4693     for (const auto &Rule : Matchers)
4694       if (!Rule->hasFirstCondition())
4695         return;
4696     const auto &FirstCondition = FirstRule.getFirstCondition();
4697     for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
4698       if (!Matchers[I]->getFirstCondition().isIdentical(FirstCondition))
4699         return;
4700 
4701     Conditions.push_back(FirstRule.popFirstCondition());
4702     for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
4703       Matchers[I]->popFirstCondition();
4704   }
4705 }
4706 
emit(MatchTable & Table)4707 void GroupMatcher::emit(MatchTable &Table) {
4708   unsigned LabelID = ~0U;
4709   if (!Conditions.empty()) {
4710     LabelID = Table.allocateLabelID();
4711     Table << MatchTable::Opcode("GIM_Try", +1)
4712           << MatchTable::Comment("On fail goto")
4713           << MatchTable::JumpTarget(LabelID) << MatchTable::LineBreak;
4714   }
4715   for (auto &Condition : Conditions)
4716     Condition->emitPredicateOpcodes(
4717         Table, *static_cast<RuleMatcher *>(*Matchers.begin()));
4718 
4719   for (const auto &M : Matchers)
4720     M->emit(Table);
4721 
4722   // Exit the group
4723   if (!Conditions.empty())
4724     Table << MatchTable::Opcode("GIM_Reject", -1) << MatchTable::LineBreak
4725           << MatchTable::Label(LabelID);
4726 }
4727 
isSupportedPredicateType(const PredicateMatcher & P)4728 bool SwitchMatcher::isSupportedPredicateType(const PredicateMatcher &P) {
4729   return isa<InstructionOpcodeMatcher>(P) || isa<LLTOperandMatcher>(P);
4730 }
4731 
candidateConditionMatches(const PredicateMatcher & Predicate) const4732 bool SwitchMatcher::candidateConditionMatches(
4733     const PredicateMatcher &Predicate) const {
4734 
4735   if (empty()) {
4736     // Sharing predicates for nested instructions is not supported yet as we
4737     // currently don't hoist the GIM_RecordInsn's properly, therefore we can
4738     // only work on the original root instruction (InsnVarID == 0):
4739     if (Predicate.getInsnVarID() != 0)
4740       return false;
4741     // ... while an attempt to add even a root matcher to an empty SwitchMatcher
4742     // could fail as not all the types of conditions are supported:
4743     if (!isSupportedPredicateType(Predicate))
4744       return false;
4745     // ... or the condition might not have a proper implementation of
4746     // getValue() / isIdenticalDownToValue() yet:
4747     if (!Predicate.hasValue())
4748       return false;
4749     // ... otherwise an empty Switch can accomodate the condition with no
4750     // further requirements:
4751     return true;
4752   }
4753 
4754   const Matcher &CaseRepresentative = **Matchers.begin();
4755   const auto &RepresentativeCondition = CaseRepresentative.getFirstCondition();
4756   // Switch-cases must share the same kind of condition and path to the value it
4757   // checks:
4758   if (!Predicate.isIdenticalDownToValue(RepresentativeCondition))
4759     return false;
4760 
4761   const auto Value = Predicate.getValue();
4762   // ... but be unique with respect to the actual value they check:
4763   return Values.count(Value) == 0;
4764 }
4765 
addMatcher(Matcher & Candidate)4766 bool SwitchMatcher::addMatcher(Matcher &Candidate) {
4767   if (!Candidate.hasFirstCondition())
4768     return false;
4769 
4770   const PredicateMatcher &Predicate = Candidate.getFirstCondition();
4771   if (!candidateConditionMatches(Predicate))
4772     return false;
4773   const auto Value = Predicate.getValue();
4774   Values.insert(Value);
4775 
4776   Matchers.push_back(&Candidate);
4777   return true;
4778 }
4779 
finalize()4780 void SwitchMatcher::finalize() {
4781   assert(Condition == nullptr && "Already finalized");
4782   assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");
4783   if (empty())
4784     return;
4785 
4786   std::stable_sort(Matchers.begin(), Matchers.end(),
4787                    [](const Matcher *L, const Matcher *R) {
4788                      return L->getFirstCondition().getValue() <
4789                             R->getFirstCondition().getValue();
4790                    });
4791   Condition = Matchers[0]->popFirstCondition();
4792   for (unsigned I = 1, E = Values.size(); I < E; ++I)
4793     Matchers[I]->popFirstCondition();
4794 }
4795 
emitPredicateSpecificOpcodes(const PredicateMatcher & P,MatchTable & Table)4796 void SwitchMatcher::emitPredicateSpecificOpcodes(const PredicateMatcher &P,
4797                                                  MatchTable &Table) {
4798   assert(isSupportedPredicateType(P) && "Predicate type is not supported");
4799 
4800   if (const auto *Condition = dyn_cast<InstructionOpcodeMatcher>(&P)) {
4801     Table << MatchTable::Opcode("GIM_SwitchOpcode") << MatchTable::Comment("MI")
4802           << MatchTable::IntValue(Condition->getInsnVarID());
4803     return;
4804   }
4805   if (const auto *Condition = dyn_cast<LLTOperandMatcher>(&P)) {
4806     Table << MatchTable::Opcode("GIM_SwitchType") << MatchTable::Comment("MI")
4807           << MatchTable::IntValue(Condition->getInsnVarID())
4808           << MatchTable::Comment("Op")
4809           << MatchTable::IntValue(Condition->getOpIdx());
4810     return;
4811   }
4812 
4813   llvm_unreachable("emitPredicateSpecificOpcodes is broken: can not handle a "
4814                    "predicate type that is claimed to be supported");
4815 }
4816 
emit(MatchTable & Table)4817 void SwitchMatcher::emit(MatchTable &Table) {
4818   assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");
4819   if (empty())
4820     return;
4821   assert(Condition != nullptr &&
4822          "Broken SwitchMatcher, hasn't been finalized?");
4823 
4824   std::vector<unsigned> LabelIDs(Values.size());
4825   std::generate(LabelIDs.begin(), LabelIDs.end(),
4826                 [&Table]() { return Table.allocateLabelID(); });
4827   const unsigned Default = Table.allocateLabelID();
4828 
4829   const int64_t LowerBound = Values.begin()->getRawValue();
4830   const int64_t UpperBound = Values.rbegin()->getRawValue() + 1;
4831 
4832   emitPredicateSpecificOpcodes(*Condition, Table);
4833 
4834   Table << MatchTable::Comment("[") << MatchTable::IntValue(LowerBound)
4835         << MatchTable::IntValue(UpperBound) << MatchTable::Comment(")")
4836         << MatchTable::Comment("default:") << MatchTable::JumpTarget(Default);
4837 
4838   int64_t J = LowerBound;
4839   auto VI = Values.begin();
4840   for (unsigned I = 0, E = Values.size(); I < E; ++I) {
4841     auto V = *VI++;
4842     while (J++ < V.getRawValue())
4843       Table << MatchTable::IntValue(0);
4844     V.turnIntoComment();
4845     Table << MatchTable::LineBreak << V << MatchTable::JumpTarget(LabelIDs[I]);
4846   }
4847   Table << MatchTable::LineBreak;
4848 
4849   for (unsigned I = 0, E = Values.size(); I < E; ++I) {
4850     Table << MatchTable::Label(LabelIDs[I]);
4851     Matchers[I]->emit(Table);
4852     Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
4853   }
4854   Table << MatchTable::Label(Default);
4855 }
4856 
getInsnVarID() const4857 unsigned OperandMatcher::getInsnVarID() const { return Insn.getInsnVarID(); }
4858 
4859 } // end anonymous namespace
4860 
4861 //===----------------------------------------------------------------------===//
4862 
4863 namespace llvm {
EmitGlobalISel(RecordKeeper & RK,raw_ostream & OS)4864 void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS) {
4865   GlobalISelEmitter(RK).run(OS);
4866 }
4867 } // End llvm namespace
4868