1 //===- GlobalISelMatchTable.h ---------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 /// \file
10 /// This file contains the code related to the GlobalISel Match Table emitted by
11 /// GlobalISelEmitter.cpp. The generated match table is interpreted at runtime
12 /// by `GIMatchTableExecutorImpl.h` to match & apply ISel patterns.
13 ///
14 //===----------------------------------------------------------------------===//
15
16 #ifndef LLVM_UTILS_TABLEGEN_GLOBALISELMATCHTABLE_H
17 #define LLVM_UTILS_TABLEGEN_GLOBALISELMATCHTABLE_H
18
19 #include "CodeGenDAGPatterns.h"
20 #include "llvm/ADT/ArrayRef.h"
21 #include "llvm/ADT/DenseMap.h"
22 #include "llvm/ADT/SmallPtrSet.h"
23 #include "llvm/ADT/StringMap.h"
24 #include "llvm/ADT/StringRef.h"
25 #include "llvm/CodeGen/LowLevelType.h"
26 #include "llvm/Support/Error.h"
27 #include "llvm/Support/SaveAndRestore.h"
28 #include <deque>
29 #include <list>
30 #include <map>
31 #include <memory>
32 #include <optional>
33 #include <set>
34 #include <string>
35 #include <vector>
36
37 namespace llvm {
38
39 class raw_ostream;
40 class Record;
41 class SMLoc;
42 class CodeGenRegisterClass;
43
44 // Use a namespace to avoid conflicts because there's some fairly generic names
45 // in there (e.g. Matcher).
46 namespace gi {
47 class MatchTable;
48 class Matcher;
49 class OperandMatcher;
50 class MatchAction;
51 class PredicateMatcher;
52 class InstructionMatcher;
53
54 enum {
55 GISF_IgnoreCopies = 0x1,
56 };
57
58 using GISelFlags = std::uint16_t;
59
60 //===- Helper functions ---------------------------------------------------===//
61
62 void emitEncodingMacrosDef(raw_ostream &OS);
63 void emitEncodingMacrosUndef(raw_ostream &OS);
64
65 std::string getNameForFeatureBitset(const std::vector<Record *> &FeatureBitset,
66 int HwModeIdx);
67
68 /// Takes a sequence of \p Rules and group them based on the predicates
69 /// they share. \p MatcherStorage is used as a memory container
70 /// for the group that are created as part of this process.
71 ///
72 /// What this optimization does looks like if GroupT = GroupMatcher:
73 /// Output without optimization:
74 /// \verbatim
75 /// # R1
76 /// # predicate A
77 /// # predicate B
78 /// ...
79 /// # R2
80 /// # predicate A // <-- effectively this is going to be checked twice.
81 /// // Once in R1 and once in R2.
82 /// # predicate C
83 /// \endverbatim
84 /// Output with optimization:
85 /// \verbatim
86 /// # Group1_2
87 /// # predicate A // <-- Check is now shared.
88 /// # R1
89 /// # predicate B
90 /// # R2
91 /// # predicate C
92 /// \endverbatim
93 template <class GroupT>
94 std::vector<Matcher *>
95 optimizeRules(ArrayRef<Matcher *> Rules,
96 std::vector<std::unique_ptr<Matcher>> &MatcherStorage);
97
98 /// A record to be stored in a MatchTable.
99 ///
100 /// This class represents any and all output that may be required to emit the
101 /// MatchTable. Instances are most often configured to represent an opcode or
102 /// value that will be emitted to the table with some formatting but it can also
103 /// represent commas, comments, and other formatting instructions.
104 struct MatchTableRecord {
105 enum RecordFlagsBits {
106 MTRF_None = 0x0,
107 /// Causes EmitStr to be formatted as comment when emitted.
108 MTRF_Comment = 0x1,
109 /// Causes the record value to be followed by a comma when emitted.
110 MTRF_CommaFollows = 0x2,
111 /// Causes the record value to be followed by a line break when emitted.
112 MTRF_LineBreakFollows = 0x4,
113 /// Indicates that the record defines a label and causes an additional
114 /// comment to be emitted containing the index of the label.
115 MTRF_Label = 0x8,
116 /// Causes the record to be emitted as the index of the label specified by
117 /// LabelID along with a comment indicating where that label is.
118 MTRF_JumpTarget = 0x10,
119 /// Causes the formatter to add a level of indentation before emitting the
120 /// record.
121 MTRF_Indent = 0x20,
122 /// Causes the formatter to remove a level of indentation after emitting the
123 /// record.
124 MTRF_Outdent = 0x40,
125 /// Causes the formatter to not use encoding macros to emit this multi-byte
126 /// value.
127 MTRF_PreEncoded = 0x80,
128 };
129
130 /// When MTRF_Label or MTRF_JumpTarget is used, indicates a label id to
131 /// reference or define.
132 unsigned LabelID;
133 /// The string to emit. Depending on the MTRF_* flags it may be a comment, a
134 /// value, a label name.
135 std::string EmitStr;
136
137 private:
138 /// The number of MatchTable elements described by this record. Comments are 0
139 /// while values are typically 1. Values >1 may occur when we need to emit
140 /// values that exceed the size of a MatchTable element.
141 unsigned NumElements;
142
143 public:
144 /// A bitfield of RecordFlagsBits flags.
145 unsigned Flags;
146
147 /// The actual run-time value, if known
148 int64_t RawValue;
149
150 MatchTableRecord(std::optional<unsigned> LabelID_, StringRef EmitStr,
151 unsigned NumElements, unsigned Flags,
152 int64_t RawValue = std::numeric_limits<int64_t>::min())
153 : LabelID(LabelID_.value_or(~0u)), EmitStr(EmitStr),
154 NumElements(NumElements), Flags(Flags), RawValue(RawValue) {
155 assert((!LabelID_ || LabelID != ~0u) &&
156 "This value is reserved for non-labels");
157 }
158 MatchTableRecord(const MatchTableRecord &Other) = default;
159 MatchTableRecord(MatchTableRecord &&Other) = default;
160
161 /// Useful if a Match Table Record gets optimized out
turnIntoCommentMatchTableRecord162 void turnIntoComment() {
163 Flags |= MTRF_Comment;
164 Flags &= ~MTRF_CommaFollows;
165 NumElements = 0;
166 }
167
168 /// For Jump Table generation purposes
169 bool operator<(const MatchTableRecord &Other) const {
170 return RawValue < Other.RawValue;
171 }
getRawValueMatchTableRecord172 int64_t getRawValue() const { return RawValue; }
173
174 void emit(raw_ostream &OS, bool LineBreakNextAfterThis,
175 const MatchTable &Table) const;
sizeMatchTableRecord176 unsigned size() const { return NumElements; }
177 };
178
179 /// Holds the contents of a generated MatchTable to enable formatting and the
180 /// necessary index tracking needed to support GIM_Try.
181 class MatchTable {
182 /// An unique identifier for the table. The generated table will be named
183 /// MatchTable${ID}.
184 unsigned ID;
185 /// The records that make up the table. Also includes comments describing the
186 /// values being emitted and line breaks to format it.
187 std::vector<MatchTableRecord> Contents;
188 /// The currently defined labels.
189 DenseMap<unsigned, unsigned> LabelMap;
190 /// Tracks the sum of MatchTableRecord::NumElements as the table is built.
191 unsigned CurrentSize = 0;
192 /// A unique identifier for a MatchTable label.
193 unsigned CurrentLabelID = 0;
194 /// Determines if the table should be instrumented for rule coverage tracking.
195 bool IsWithCoverage;
196 /// Whether this table is for the GISel combiner.
197 bool IsCombinerTable;
198
199 public:
200 static MatchTableRecord LineBreak;
201 static MatchTableRecord Comment(StringRef Comment);
202 static MatchTableRecord Opcode(StringRef Opcode, int IndentAdjust = 0);
203 static MatchTableRecord NamedValue(unsigned NumBytes, StringRef NamedValue);
204 static MatchTableRecord NamedValue(unsigned NumBytes, StringRef NamedValue,
205 int64_t RawValue);
206 static MatchTableRecord NamedValue(unsigned NumBytes, StringRef Namespace,
207 StringRef NamedValue);
208 static MatchTableRecord NamedValue(unsigned NumBytes, StringRef Namespace,
209 StringRef NamedValue, int64_t RawValue);
210 static MatchTableRecord IntValue(unsigned NumBytes, int64_t IntValue);
211 static MatchTableRecord ULEB128Value(uint64_t IntValue);
212 static MatchTableRecord Label(unsigned LabelID);
213 static MatchTableRecord JumpTarget(unsigned LabelID);
214
215 static MatchTable buildTable(ArrayRef<Matcher *> Rules, bool WithCoverage,
216 bool IsCombiner = false);
217
218 MatchTable(bool WithCoverage, bool IsCombinerTable, unsigned ID = 0)
ID(ID)219 : ID(ID), IsWithCoverage(WithCoverage), IsCombinerTable(IsCombinerTable) {
220 }
221
isWithCoverage()222 bool isWithCoverage() const { return IsWithCoverage; }
isCombiner()223 bool isCombiner() const { return IsCombinerTable; }
224
push_back(const MatchTableRecord & Value)225 void push_back(const MatchTableRecord &Value) {
226 if (Value.Flags & MatchTableRecord::MTRF_Label)
227 defineLabel(Value.LabelID);
228 Contents.push_back(Value);
229 CurrentSize += Value.size();
230 }
231
allocateLabelID()232 unsigned allocateLabelID() { return CurrentLabelID++; }
233
defineLabel(unsigned LabelID)234 void defineLabel(unsigned LabelID) {
235 LabelMap.insert(std::make_pair(LabelID, CurrentSize));
236 }
237
getLabelIndex(unsigned LabelID)238 unsigned getLabelIndex(unsigned LabelID) const {
239 const auto I = LabelMap.find(LabelID);
240 assert(I != LabelMap.end() && "Use of undeclared label");
241 return I->second;
242 }
243
244 void emitUse(raw_ostream &OS) const;
245 void emitDeclaration(raw_ostream &OS) const;
246 };
247
248 inline MatchTable &operator<<(MatchTable &Table,
249 const MatchTableRecord &Value) {
250 Table.push_back(Value);
251 return Table;
252 }
253
254 /// This class stands in for LLT wherever we want to tablegen-erate an
255 /// equivalent at compiler run-time.
256 class LLTCodeGen {
257 private:
258 LLT Ty;
259
260 public:
261 LLTCodeGen() = default;
LLTCodeGen(const LLT & Ty)262 LLTCodeGen(const LLT &Ty) : Ty(Ty) {}
263
264 std::string getCxxEnumValue() const;
265
266 void emitCxxEnumValue(raw_ostream &OS) const;
267 void emitCxxConstructorCall(raw_ostream &OS) const;
268
get()269 const LLT &get() const { return Ty; }
270
271 /// This ordering is used for std::unique() and llvm::sort(). There's no
272 /// particular logic behind the order but either A < B or B < A must be
273 /// true if A != B.
274 bool operator<(const LLTCodeGen &Other) const;
275 bool operator==(const LLTCodeGen &B) const { return Ty == B.Ty; }
276 };
277
278 // Track all types that are used so we can emit the corresponding enum.
279 extern std::set<LLTCodeGen> KnownTypes;
280
281 /// Convert an MVT to an equivalent LLT if possible, or the invalid LLT() for
282 /// MVTs that don't map cleanly to an LLT (e.g., iPTR, *any, ...).
283 std::optional<LLTCodeGen> MVTToLLT(MVT::SimpleValueType SVT);
284
285 using TempTypeIdx = int64_t;
286 class LLTCodeGenOrTempType {
287 public:
LLTCodeGenOrTempType(const LLTCodeGen & LLT)288 LLTCodeGenOrTempType(const LLTCodeGen &LLT) : Data(LLT) {}
LLTCodeGenOrTempType(TempTypeIdx TempTy)289 LLTCodeGenOrTempType(TempTypeIdx TempTy) : Data(TempTy) {}
290
isLLTCodeGen()291 bool isLLTCodeGen() const { return std::holds_alternative<LLTCodeGen>(Data); }
isTempTypeIdx()292 bool isTempTypeIdx() const {
293 return std::holds_alternative<TempTypeIdx>(Data);
294 }
295
getLLTCodeGen()296 const LLTCodeGen &getLLTCodeGen() const {
297 assert(isLLTCodeGen());
298 return std::get<LLTCodeGen>(Data);
299 }
300
getTempTypeIdx()301 TempTypeIdx getTempTypeIdx() const {
302 assert(isTempTypeIdx());
303 return std::get<TempTypeIdx>(Data);
304 }
305
306 private:
307 std::variant<LLTCodeGen, TempTypeIdx> Data;
308 };
309
310 inline MatchTable &operator<<(MatchTable &Table,
311 const LLTCodeGenOrTempType &Ty) {
312 if (Ty.isLLTCodeGen())
313 Table << MatchTable::NamedValue(1, Ty.getLLTCodeGen().getCxxEnumValue());
314 else
315 Table << MatchTable::IntValue(1, Ty.getTempTypeIdx());
316 return Table;
317 }
318
319 //===- Matchers -----------------------------------------------------------===//
320 class Matcher {
321 public:
322 virtual ~Matcher();
323 virtual void optimize();
324 virtual void emit(MatchTable &Table) = 0;
325
326 virtual bool hasFirstCondition() const = 0;
327 virtual const PredicateMatcher &getFirstCondition() const = 0;
328 virtual std::unique_ptr<PredicateMatcher> popFirstCondition() = 0;
329 };
330
331 class GroupMatcher final : public Matcher {
332 /// Conditions that form a common prefix of all the matchers contained.
333 SmallVector<std::unique_ptr<PredicateMatcher>, 1> Conditions;
334
335 /// All the nested matchers, sharing a common prefix.
336 std::vector<Matcher *> Matchers;
337
338 /// An owning collection for any auxiliary matchers created while optimizing
339 /// nested matchers contained.
340 std::vector<std::unique_ptr<Matcher>> MatcherStorage;
341
342 public:
343 /// Add a matcher to the collection of nested matchers if it meets the
344 /// requirements, and return true. If it doesn't, do nothing and return false.
345 ///
346 /// Expected to preserve its argument, so it could be moved out later on.
347 bool addMatcher(Matcher &Candidate);
348
349 /// Mark the matcher as fully-built and ensure any invariants expected by both
350 /// optimize() and emit(...) methods. Generally, both sequences of calls
351 /// are expected to lead to a sensible result:
352 ///
353 /// addMatcher(...)*; finalize(); optimize(); emit(...); and
354 /// addMatcher(...)*; finalize(); emit(...);
355 ///
356 /// or generally
357 ///
358 /// addMatcher(...)*; finalize(); { optimize()*; emit(...); }*
359 ///
360 /// Multiple calls to optimize() are expected to be handled gracefully, though
361 /// optimize() is not expected to be idempotent. Multiple calls to finalize()
362 /// aren't generally supported. emit(...) is expected to be non-mutating and
363 /// producing the exact same results upon repeated calls.
364 ///
365 /// addMatcher() calls after the finalize() call are not supported.
366 ///
367 /// finalize() and optimize() are both allowed to mutate the contained
368 /// matchers, so moving them out after finalize() is not supported.
369 void finalize();
370 void optimize() override;
371 void emit(MatchTable &Table) override;
372
373 /// Could be used to move out the matchers added previously, unless finalize()
374 /// has been already called. If any of the matchers are moved out, the group
375 /// becomes safe to destroy, but not safe to re-use for anything else.
matchers()376 iterator_range<std::vector<Matcher *>::iterator> matchers() {
377 return make_range(Matchers.begin(), Matchers.end());
378 }
size()379 size_t size() const { return Matchers.size(); }
empty()380 bool empty() const { return Matchers.empty(); }
381
popFirstCondition()382 std::unique_ptr<PredicateMatcher> popFirstCondition() override {
383 assert(!Conditions.empty() &&
384 "Trying to pop a condition from a condition-less group");
385 std::unique_ptr<PredicateMatcher> P = std::move(Conditions.front());
386 Conditions.erase(Conditions.begin());
387 return P;
388 }
getFirstCondition()389 const PredicateMatcher &getFirstCondition() const override {
390 assert(!Conditions.empty() &&
391 "Trying to get a condition from a condition-less group");
392 return *Conditions.front();
393 }
hasFirstCondition()394 bool hasFirstCondition() const override { return !Conditions.empty(); }
395
396 private:
397 /// See if a candidate matcher could be added to this group solely by
398 /// analyzing its first condition.
399 bool candidateConditionMatches(const PredicateMatcher &Predicate) const;
400 };
401
402 class SwitchMatcher : public Matcher {
403 /// All the nested matchers, representing distinct switch-cases. The first
404 /// conditions (as Matcher::getFirstCondition() reports) of all the nested
405 /// matchers must share the same type and path to a value they check, in other
406 /// words, be isIdenticalDownToValue, but have different values they check
407 /// against.
408 std::vector<Matcher *> Matchers;
409
410 /// The representative condition, with a type and a path (InsnVarID and OpIdx
411 /// in most cases) shared by all the matchers contained.
412 std::unique_ptr<PredicateMatcher> Condition = nullptr;
413
414 /// Temporary set used to check that the case values don't repeat within the
415 /// same switch.
416 std::set<MatchTableRecord> Values;
417
418 /// An owning collection for any auxiliary matchers created while optimizing
419 /// nested matchers contained.
420 std::vector<std::unique_ptr<Matcher>> MatcherStorage;
421
422 public:
423 bool addMatcher(Matcher &Candidate);
424
425 void finalize();
426 void emit(MatchTable &Table) override;
427
matchers()428 iterator_range<std::vector<Matcher *>::iterator> matchers() {
429 return make_range(Matchers.begin(), Matchers.end());
430 }
size()431 size_t size() const { return Matchers.size(); }
empty()432 bool empty() const { return Matchers.empty(); }
433
popFirstCondition()434 std::unique_ptr<PredicateMatcher> popFirstCondition() override {
435 // SwitchMatcher doesn't have a common first condition for its cases, as all
436 // the cases only share a kind of a value (a type and a path to it) they
437 // match, but deliberately differ in the actual value they match.
438 llvm_unreachable("Trying to pop a condition from a condition-less group");
439 }
440
getFirstCondition()441 const PredicateMatcher &getFirstCondition() const override {
442 llvm_unreachable("Trying to pop a condition from a condition-less group");
443 }
444
hasFirstCondition()445 bool hasFirstCondition() const override { return false; }
446
447 private:
448 /// See if the predicate type has a Switch-implementation for it.
449 static bool isSupportedPredicateType(const PredicateMatcher &Predicate);
450
451 bool candidateConditionMatches(const PredicateMatcher &Predicate) const;
452
453 /// emit()-helper
454 static void emitPredicateSpecificOpcodes(const PredicateMatcher &P,
455 MatchTable &Table);
456 };
457
458 /// Generates code to check that a match rule matches.
459 class RuleMatcher : public Matcher {
460 public:
461 using ActionList = std::list<std::unique_ptr<MatchAction>>;
462 using action_iterator = ActionList::iterator;
463
464 protected:
465 /// A list of matchers that all need to succeed for the current rule to match.
466 /// FIXME: This currently supports a single match position but could be
467 /// extended to support multiple positions to support div/rem fusion or
468 /// load-multiple instructions.
469 using MatchersTy = std::vector<std::unique_ptr<InstructionMatcher>>;
470 MatchersTy Matchers;
471
472 /// A list of actions that need to be taken when all predicates in this rule
473 /// have succeeded.
474 ActionList Actions;
475
476 using DefinedInsnVariablesMap = std::map<InstructionMatcher *, unsigned>;
477
478 /// A map of instruction matchers to the local variables
479 DefinedInsnVariablesMap InsnVariableIDs;
480
481 using MutatableInsnSet = SmallPtrSet<InstructionMatcher *, 4>;
482
483 // The set of instruction matchers that have not yet been claimed for mutation
484 // by a BuildMI.
485 MutatableInsnSet MutatableInsns;
486
487 /// A map of named operands defined by the matchers that may be referenced by
488 /// the renderers.
489 StringMap<OperandMatcher *> DefinedOperands;
490
491 /// A map of anonymous physical register operands defined by the matchers that
492 /// may be referenced by the renderers.
493 DenseMap<Record *, OperandMatcher *> PhysRegOperands;
494
495 /// ID for the next instruction variable defined with
496 /// implicitlyDefineInsnVar()
497 unsigned NextInsnVarID;
498
499 /// ID for the next output instruction allocated with allocateOutputInsnID()
500 unsigned NextOutputInsnID;
501
502 /// ID for the next temporary register ID allocated with allocateTempRegID()
503 unsigned NextTempRegID;
504
505 /// ID for the next recorded type. Starts at -1 and counts down.
506 TempTypeIdx NextTempTypeIdx = -1;
507
508 // HwMode predicate index for this rule. -1 if no HwMode.
509 int HwModeIdx = -1;
510
511 /// Current GISelFlags
512 GISelFlags Flags = 0;
513
514 std::vector<std::string> RequiredSimplePredicates;
515 std::vector<Record *> RequiredFeatures;
516 std::vector<std::unique_ptr<PredicateMatcher>> EpilogueMatchers;
517
518 DenseSet<unsigned> ErasedInsnIDs;
519
520 ArrayRef<SMLoc> SrcLoc;
521
522 typedef std::tuple<Record *, unsigned, unsigned>
523 DefinedComplexPatternSubOperand;
524 typedef StringMap<DefinedComplexPatternSubOperand>
525 DefinedComplexPatternSubOperandMap;
526 /// A map of Symbolic Names to ComplexPattern sub-operands.
527 DefinedComplexPatternSubOperandMap ComplexSubOperands;
528 /// A map used to for multiple referenced error check of ComplexSubOperand.
529 /// ComplexSubOperand can't be referenced multiple from different operands,
530 /// however multiple references from same operand are allowed since that is
531 /// how 'same operand checks' are generated.
532 StringMap<std::string> ComplexSubOperandsParentName;
533
534 uint64_t RuleID;
535 static uint64_t NextRuleID;
536
537 GISelFlags updateGISelFlag(GISelFlags CurFlags, const Record *R,
538 StringRef FlagName, GISelFlags FlagBit);
539
540 public:
RuleMatcher(ArrayRef<SMLoc> SrcLoc)541 RuleMatcher(ArrayRef<SMLoc> SrcLoc)
542 : NextInsnVarID(0), NextOutputInsnID(0), NextTempRegID(0), SrcLoc(SrcLoc),
543 RuleID(NextRuleID++) {}
544 RuleMatcher(RuleMatcher &&Other) = default;
545 RuleMatcher &operator=(RuleMatcher &&Other) = default;
546
getNextTempTypeIdx()547 TempTypeIdx getNextTempTypeIdx() { return NextTempTypeIdx--; }
548
getRuleID()549 uint64_t getRuleID() const { return RuleID; }
550
551 InstructionMatcher &addInstructionMatcher(StringRef SymbolicName);
552 void addRequiredFeature(Record *Feature);
553 const std::vector<Record *> &getRequiredFeatures() const;
554
addHwModeIdx(unsigned Idx)555 void addHwModeIdx(unsigned Idx) { HwModeIdx = Idx; }
getHwModeIdx()556 int getHwModeIdx() const { return HwModeIdx; }
557
558 void addRequiredSimplePredicate(StringRef PredName);
559 const std::vector<std::string> &getRequiredSimplePredicates();
560
561 /// Attempts to mark \p ID as erased (GIR_EraseFromParent called on it).
562 /// If \p ID has already been erased, returns false and GIR_EraseFromParent
563 /// should NOT be emitted.
tryEraseInsnID(unsigned ID)564 bool tryEraseInsnID(unsigned ID) { return ErasedInsnIDs.insert(ID).second; }
565
566 // Emplaces an action of the specified Kind at the end of the action list.
567 //
568 // Returns a reference to the newly created action.
569 //
570 // Like std::vector::emplace_back(), may invalidate all iterators if the new
571 // size exceeds the capacity. Otherwise, only invalidates the past-the-end
572 // iterator.
addAction(Args &&...args)573 template <class Kind, class... Args> Kind &addAction(Args &&...args) {
574 Actions.emplace_back(std::make_unique<Kind>(std::forward<Args>(args)...));
575 return *static_cast<Kind *>(Actions.back().get());
576 }
577
578 // Emplaces an action of the specified Kind before the given insertion point.
579 //
580 // Returns an iterator pointing at the newly created instruction.
581 //
582 // Like std::vector::insert(), may invalidate all iterators if the new size
583 // exceeds the capacity. Otherwise, only invalidates the iterators from the
584 // insertion point onwards.
585 template <class Kind, class... Args>
insertAction(action_iterator InsertPt,Args &&...args)586 action_iterator insertAction(action_iterator InsertPt, Args &&...args) {
587 return Actions.emplace(InsertPt,
588 std::make_unique<Kind>(std::forward<Args>(args)...));
589 }
590
setPermanentGISelFlags(GISelFlags V)591 void setPermanentGISelFlags(GISelFlags V) { Flags = V; }
592
593 // Update the active GISelFlags based on the GISelFlags Record R.
594 // A SaveAndRestore object is returned so the old GISelFlags are restored
595 // at the end of the scope.
596 SaveAndRestore<GISelFlags> setGISelFlags(const Record *R);
getGISelFlags()597 GISelFlags getGISelFlags() const { return Flags; }
598
599 /// Define an instruction without emitting any code to do so.
600 unsigned implicitlyDefineInsnVar(InstructionMatcher &Matcher);
601
602 unsigned getInsnVarID(InstructionMatcher &InsnMatcher) const;
defined_insn_vars_begin()603 DefinedInsnVariablesMap::const_iterator defined_insn_vars_begin() const {
604 return InsnVariableIDs.begin();
605 }
defined_insn_vars_end()606 DefinedInsnVariablesMap::const_iterator defined_insn_vars_end() const {
607 return InsnVariableIDs.end();
608 }
609 iterator_range<typename DefinedInsnVariablesMap::const_iterator>
defined_insn_vars()610 defined_insn_vars() const {
611 return make_range(defined_insn_vars_begin(), defined_insn_vars_end());
612 }
613
mutatable_insns_begin()614 MutatableInsnSet::const_iterator mutatable_insns_begin() const {
615 return MutatableInsns.begin();
616 }
mutatable_insns_end()617 MutatableInsnSet::const_iterator mutatable_insns_end() const {
618 return MutatableInsns.end();
619 }
620 iterator_range<typename MutatableInsnSet::const_iterator>
mutatable_insns()621 mutatable_insns() const {
622 return make_range(mutatable_insns_begin(), mutatable_insns_end());
623 }
reserveInsnMatcherForMutation(InstructionMatcher * InsnMatcher)624 void reserveInsnMatcherForMutation(InstructionMatcher *InsnMatcher) {
625 bool R = MutatableInsns.erase(InsnMatcher);
626 assert(R && "Reserving a mutatable insn that isn't available");
627 (void)R;
628 }
629
actions_begin()630 action_iterator actions_begin() { return Actions.begin(); }
actions_end()631 action_iterator actions_end() { return Actions.end(); }
actions()632 iterator_range<action_iterator> actions() {
633 return make_range(actions_begin(), actions_end());
634 }
635
636 void defineOperand(StringRef SymbolicName, OperandMatcher &OM);
637
638 void definePhysRegOperand(Record *Reg, OperandMatcher &OM);
639
640 Error defineComplexSubOperand(StringRef SymbolicName, Record *ComplexPattern,
641 unsigned RendererID, unsigned SubOperandID,
642 StringRef ParentSymbolicName);
643
644 std::optional<DefinedComplexPatternSubOperand>
getComplexSubOperand(StringRef SymbolicName)645 getComplexSubOperand(StringRef SymbolicName) const {
646 const auto &I = ComplexSubOperands.find(SymbolicName);
647 if (I == ComplexSubOperands.end())
648 return std::nullopt;
649 return I->second;
650 }
651
652 InstructionMatcher &getInstructionMatcher(StringRef SymbolicName) const;
653 OperandMatcher &getOperandMatcher(StringRef Name);
654 const OperandMatcher &getOperandMatcher(StringRef Name) const;
655 const OperandMatcher &getPhysRegOperandMatcher(Record *) const;
656
657 void optimize() override;
658 void emit(MatchTable &Table) override;
659
660 /// Compare the priority of this object and B.
661 ///
662 /// Returns true if this object is more important than B.
663 bool isHigherPriorityThan(const RuleMatcher &B) const;
664
665 /// Report the maximum number of temporary operands needed by the rule
666 /// matcher.
667 unsigned countRendererFns() const;
668
669 std::unique_ptr<PredicateMatcher> popFirstCondition() override;
670 const PredicateMatcher &getFirstCondition() const override;
671 LLTCodeGen getFirstConditionAsRootType();
672 bool hasFirstCondition() const override;
673 unsigned getNumOperands() const;
674 StringRef getOpcode() const;
675
676 // FIXME: Remove this as soon as possible
insnmatchers_front()677 InstructionMatcher &insnmatchers_front() const { return *Matchers.front(); }
678
allocateOutputInsnID()679 unsigned allocateOutputInsnID() { return NextOutputInsnID++; }
allocateTempRegID()680 unsigned allocateTempRegID() { return NextTempRegID++; }
681
insnmatchers()682 iterator_range<MatchersTy::iterator> insnmatchers() {
683 return make_range(Matchers.begin(), Matchers.end());
684 }
insnmatchers_empty()685 bool insnmatchers_empty() const { return Matchers.empty(); }
insnmatchers_pop_front()686 void insnmatchers_pop_front() { Matchers.erase(Matchers.begin()); }
687 };
688
689 template <class PredicateTy> class PredicateListMatcher {
690 private:
691 /// Template instantiations should specialize this to return a string to use
692 /// for the comment emitted when there are no predicates.
693 std::string getNoPredicateComment() const;
694
695 protected:
696 using PredicatesTy = std::deque<std::unique_ptr<PredicateTy>>;
697 PredicatesTy Predicates;
698
699 /// Track if the list of predicates was manipulated by one of the optimization
700 /// methods.
701 bool Optimized = false;
702
703 public:
predicates_begin()704 typename PredicatesTy::iterator predicates_begin() {
705 return Predicates.begin();
706 }
predicates_end()707 typename PredicatesTy::iterator predicates_end() { return Predicates.end(); }
predicates()708 iterator_range<typename PredicatesTy::iterator> predicates() {
709 return make_range(predicates_begin(), predicates_end());
710 }
predicates_size()711 typename PredicatesTy::size_type predicates_size() const {
712 return Predicates.size();
713 }
predicates_empty()714 bool predicates_empty() const { return Predicates.empty(); }
715
contains()716 template <typename Ty> bool contains() const {
717 return any_of(Predicates, [&](auto &P) { return isa<Ty>(P.get()); });
718 }
719
predicates_pop_front()720 std::unique_ptr<PredicateTy> predicates_pop_front() {
721 std::unique_ptr<PredicateTy> Front = std::move(Predicates.front());
722 Predicates.pop_front();
723 Optimized = true;
724 return Front;
725 }
726
prependPredicate(std::unique_ptr<PredicateTy> && Predicate)727 void prependPredicate(std::unique_ptr<PredicateTy> &&Predicate) {
728 Predicates.push_front(std::move(Predicate));
729 }
730
eraseNullPredicates()731 void eraseNullPredicates() {
732 const auto NewEnd =
733 std::stable_partition(Predicates.begin(), Predicates.end(),
734 std::logical_not<std::unique_ptr<PredicateTy>>());
735 if (NewEnd != Predicates.begin()) {
736 Predicates.erase(Predicates.begin(), NewEnd);
737 Optimized = true;
738 }
739 }
740
741 /// Emit MatchTable opcodes that tests whether all the predicates are met.
742 template <class... Args>
emitPredicateListOpcodes(MatchTable & Table,Args &&...args)743 void emitPredicateListOpcodes(MatchTable &Table, Args &&...args) {
744 if (Predicates.empty() && !Optimized) {
745 Table << MatchTable::Comment(getNoPredicateComment())
746 << MatchTable::LineBreak;
747 return;
748 }
749
750 for (const auto &Predicate : predicates())
751 Predicate->emitPredicateOpcodes(Table, std::forward<Args>(args)...);
752 }
753
754 /// Provide a function to avoid emitting certain predicates. This is used to
755 /// defer some predicate checks until after others
756 using PredicateFilterFunc = std::function<bool(const PredicateTy &)>;
757
758 /// Emit MatchTable opcodes for predicates which satisfy \p
759 /// ShouldEmitPredicate. This should be called multiple times to ensure all
760 /// predicates are eventually added to the match table.
761 template <class... Args>
emitFilteredPredicateListOpcodes(PredicateFilterFunc ShouldEmitPredicate,MatchTable & Table,Args &&...args)762 void emitFilteredPredicateListOpcodes(PredicateFilterFunc ShouldEmitPredicate,
763 MatchTable &Table, Args &&...args) {
764 if (Predicates.empty() && !Optimized) {
765 Table << MatchTable::Comment(getNoPredicateComment())
766 << MatchTable::LineBreak;
767 return;
768 }
769
770 for (const auto &Predicate : predicates()) {
771 if (ShouldEmitPredicate(*Predicate))
772 Predicate->emitPredicateOpcodes(Table, std::forward<Args>(args)...);
773 }
774 }
775 };
776
777 class PredicateMatcher {
778 public:
779 /// This enum is used for RTTI and also defines the priority that is given to
780 /// the predicate when generating the matcher code. Kinds with higher priority
781 /// must be tested first.
782 ///
783 /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter
784 /// but OPM_Int must have priority over OPM_RegBank since constant integers
785 /// are represented by a virtual register defined by a G_CONSTANT instruction.
786 ///
787 /// Note: The relative priority between IPM_ and OPM_ does not matter, they
788 /// are currently not compared between each other.
789 enum PredicateKind {
790 IPM_Opcode,
791 IPM_NumOperands,
792 IPM_ImmPredicate,
793 IPM_Imm,
794 IPM_AtomicOrderingMMO,
795 IPM_MemoryLLTSize,
796 IPM_MemoryVsLLTSize,
797 IPM_MemoryAddressSpace,
798 IPM_MemoryAlignment,
799 IPM_VectorSplatImm,
800 IPM_NoUse,
801 IPM_GenericPredicate,
802 IPM_MIFlags,
803 OPM_SameOperand,
804 OPM_ComplexPattern,
805 OPM_IntrinsicID,
806 OPM_CmpPredicate,
807 OPM_Instruction,
808 OPM_Int,
809 OPM_LiteralInt,
810 OPM_LLT,
811 OPM_PointerToAny,
812 OPM_RegBank,
813 OPM_MBB,
814 OPM_RecordNamedOperand,
815 OPM_RecordRegType,
816 };
817
818 protected:
819 PredicateKind Kind;
820 unsigned InsnVarID;
821 unsigned OpIdx;
822
823 public:
824 PredicateMatcher(PredicateKind Kind, unsigned InsnVarID, unsigned OpIdx = ~0)
Kind(Kind)825 : Kind(Kind), InsnVarID(InsnVarID), OpIdx(OpIdx) {}
826 virtual ~PredicateMatcher();
827
getInsnVarID()828 unsigned getInsnVarID() const { return InsnVarID; }
getOpIdx()829 unsigned getOpIdx() const { return OpIdx; }
830
831 /// Emit MatchTable opcodes that check the predicate for the given operand.
832 virtual void emitPredicateOpcodes(MatchTable &Table,
833 RuleMatcher &Rule) const = 0;
834
getKind()835 PredicateKind getKind() const { return Kind; }
836
dependsOnOperands()837 bool dependsOnOperands() const {
838 // Custom predicates really depend on the context pattern of the
839 // instruction, not just the individual instruction. This therefore
840 // implicitly depends on all other pattern constraints.
841 return Kind == IPM_GenericPredicate;
842 }
843
isIdentical(const PredicateMatcher & B)844 virtual bool isIdentical(const PredicateMatcher &B) const {
845 return B.getKind() == getKind() && InsnVarID == B.InsnVarID &&
846 OpIdx == B.OpIdx;
847 }
848
isIdenticalDownToValue(const PredicateMatcher & B)849 virtual bool isIdenticalDownToValue(const PredicateMatcher &B) const {
850 return hasValue() && PredicateMatcher::isIdentical(B);
851 }
852
getValue()853 virtual MatchTableRecord getValue() const {
854 assert(hasValue() && "Can not get a value of a value-less predicate!");
855 llvm_unreachable("Not implemented yet");
856 }
hasValue()857 virtual bool hasValue() const { return false; }
858
859 /// Report the maximum number of temporary operands needed by the predicate
860 /// matcher.
countRendererFns()861 virtual unsigned countRendererFns() const { return 0; }
862 };
863
864 /// Generates code to check a predicate of an operand.
865 ///
866 /// Typical predicates include:
867 /// * Operand is a particular register.
868 /// * Operand is assigned a particular register bank.
869 /// * Operand is an MBB.
870 class OperandPredicateMatcher : public PredicateMatcher {
871 public:
OperandPredicateMatcher(PredicateKind Kind,unsigned InsnVarID,unsigned OpIdx)872 OperandPredicateMatcher(PredicateKind Kind, unsigned InsnVarID,
873 unsigned OpIdx)
874 : PredicateMatcher(Kind, InsnVarID, OpIdx) {}
875 virtual ~OperandPredicateMatcher();
876
877 /// Compare the priority of this object and B.
878 ///
879 /// Returns true if this object is more important than B.
880 virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const;
881 };
882
883 template <>
884 inline std::string
getNoPredicateComment()885 PredicateListMatcher<OperandPredicateMatcher>::getNoPredicateComment() const {
886 return "No operand predicates";
887 }
888
889 /// Generates code to check that a register operand is defined by the same exact
890 /// one as another.
891 class SameOperandMatcher : public OperandPredicateMatcher {
892 std::string MatchingName;
893 unsigned OrigOpIdx;
894
895 GISelFlags Flags;
896
897 public:
SameOperandMatcher(unsigned InsnVarID,unsigned OpIdx,StringRef MatchingName,unsigned OrigOpIdx,GISelFlags Flags)898 SameOperandMatcher(unsigned InsnVarID, unsigned OpIdx, StringRef MatchingName,
899 unsigned OrigOpIdx, GISelFlags Flags)
900 : OperandPredicateMatcher(OPM_SameOperand, InsnVarID, OpIdx),
901 MatchingName(MatchingName), OrigOpIdx(OrigOpIdx), Flags(Flags) {}
902
classof(const PredicateMatcher * P)903 static bool classof(const PredicateMatcher *P) {
904 return P->getKind() == OPM_SameOperand;
905 }
906
907 void emitPredicateOpcodes(MatchTable &Table,
908 RuleMatcher &Rule) const override;
909
isIdentical(const PredicateMatcher & B)910 bool isIdentical(const PredicateMatcher &B) const override {
911 return OperandPredicateMatcher::isIdentical(B) &&
912 OrigOpIdx == cast<SameOperandMatcher>(&B)->OrigOpIdx &&
913 MatchingName == cast<SameOperandMatcher>(&B)->MatchingName;
914 }
915 };
916
917 /// Generates code to check that an operand is a particular LLT.
918 class LLTOperandMatcher : public OperandPredicateMatcher {
919 protected:
920 LLTCodeGen Ty;
921
922 public:
923 static std::map<LLTCodeGen, unsigned> TypeIDValues;
924
initTypeIDValuesMap()925 static void initTypeIDValuesMap() {
926 TypeIDValues.clear();
927
928 unsigned ID = 0;
929 for (const LLTCodeGen &LLTy : KnownTypes)
930 TypeIDValues[LLTy] = ID++;
931 }
932
LLTOperandMatcher(unsigned InsnVarID,unsigned OpIdx,const LLTCodeGen & Ty)933 LLTOperandMatcher(unsigned InsnVarID, unsigned OpIdx, const LLTCodeGen &Ty)
934 : OperandPredicateMatcher(OPM_LLT, InsnVarID, OpIdx), Ty(Ty) {
935 KnownTypes.insert(Ty);
936 }
937
classof(const PredicateMatcher * P)938 static bool classof(const PredicateMatcher *P) {
939 return P->getKind() == OPM_LLT;
940 }
941
isIdentical(const PredicateMatcher & B)942 bool isIdentical(const PredicateMatcher &B) const override {
943 return OperandPredicateMatcher::isIdentical(B) &&
944 Ty == cast<LLTOperandMatcher>(&B)->Ty;
945 }
946
947 MatchTableRecord getValue() const override;
948 bool hasValue() const override;
949
getTy()950 LLTCodeGen getTy() const { return Ty; }
951
952 void emitPredicateOpcodes(MatchTable &Table,
953 RuleMatcher &Rule) const override;
954 };
955
956 /// Generates code to check that an operand is a pointer to any address space.
957 ///
958 /// In SelectionDAG, the types did not describe pointers or address spaces. As a
959 /// result, iN is used to describe a pointer of N bits to any address space and
960 /// PatFrag predicates are typically used to constrain the address space.
961 /// There's no reliable means to derive the missing type information from the
962 /// pattern so imported rules must test the components of a pointer separately.
963 ///
964 /// If SizeInBits is zero, then the pointer size will be obtained from the
965 /// subtarget.
966 class PointerToAnyOperandMatcher : public OperandPredicateMatcher {
967 protected:
968 unsigned SizeInBits;
969
970 public:
PointerToAnyOperandMatcher(unsigned InsnVarID,unsigned OpIdx,unsigned SizeInBits)971 PointerToAnyOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
972 unsigned SizeInBits)
973 : OperandPredicateMatcher(OPM_PointerToAny, InsnVarID, OpIdx),
974 SizeInBits(SizeInBits) {}
975
classof(const PredicateMatcher * P)976 static bool classof(const PredicateMatcher *P) {
977 return P->getKind() == OPM_PointerToAny;
978 }
979
isIdentical(const PredicateMatcher & B)980 bool isIdentical(const PredicateMatcher &B) const override {
981 return OperandPredicateMatcher::isIdentical(B) &&
982 SizeInBits == cast<PointerToAnyOperandMatcher>(&B)->SizeInBits;
983 }
984
985 void emitPredicateOpcodes(MatchTable &Table,
986 RuleMatcher &Rule) const override;
987 };
988
989 /// Generates code to record named operand in RecordedOperands list at StoreIdx.
990 /// Predicates with 'let PredicateCodeUsesOperands = 1' get RecordedOperands as
991 /// an argument to predicate's c++ code once all operands have been matched.
992 class RecordNamedOperandMatcher : public OperandPredicateMatcher {
993 protected:
994 unsigned StoreIdx;
995 std::string Name;
996
997 public:
RecordNamedOperandMatcher(unsigned InsnVarID,unsigned OpIdx,unsigned StoreIdx,StringRef Name)998 RecordNamedOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
999 unsigned StoreIdx, StringRef Name)
1000 : OperandPredicateMatcher(OPM_RecordNamedOperand, InsnVarID, OpIdx),
1001 StoreIdx(StoreIdx), Name(Name) {}
1002
classof(const PredicateMatcher * P)1003 static bool classof(const PredicateMatcher *P) {
1004 return P->getKind() == OPM_RecordNamedOperand;
1005 }
1006
isIdentical(const PredicateMatcher & B)1007 bool isIdentical(const PredicateMatcher &B) const override {
1008 return OperandPredicateMatcher::isIdentical(B) &&
1009 StoreIdx == cast<RecordNamedOperandMatcher>(&B)->StoreIdx &&
1010 Name == cast<RecordNamedOperandMatcher>(&B)->Name;
1011 }
1012
1013 void emitPredicateOpcodes(MatchTable &Table,
1014 RuleMatcher &Rule) const override;
1015 };
1016
1017 /// Generates code to store a register operand's type into the set of temporary
1018 /// LLTs.
1019 class RecordRegisterType : public OperandPredicateMatcher {
1020 protected:
1021 TempTypeIdx Idx;
1022
1023 public:
RecordRegisterType(unsigned InsnVarID,unsigned OpIdx,TempTypeIdx Idx)1024 RecordRegisterType(unsigned InsnVarID, unsigned OpIdx, TempTypeIdx Idx)
1025 : OperandPredicateMatcher(OPM_RecordRegType, InsnVarID, OpIdx), Idx(Idx) {
1026 }
1027
classof(const PredicateMatcher * P)1028 static bool classof(const PredicateMatcher *P) {
1029 return P->getKind() == OPM_RecordRegType;
1030 }
1031
isIdentical(const PredicateMatcher & B)1032 bool isIdentical(const PredicateMatcher &B) const override {
1033 return OperandPredicateMatcher::isIdentical(B) &&
1034 Idx == cast<RecordRegisterType>(&B)->Idx;
1035 }
1036
1037 void emitPredicateOpcodes(MatchTable &Table,
1038 RuleMatcher &Rule) const override;
1039 };
1040
1041 /// Generates code to check that an operand is a particular target constant.
1042 class ComplexPatternOperandMatcher : public OperandPredicateMatcher {
1043 protected:
1044 const OperandMatcher &Operand;
1045 const Record &TheDef;
1046
1047 unsigned getAllocatedTemporariesBaseID() const;
1048
1049 public:
isIdentical(const PredicateMatcher & B)1050 bool isIdentical(const PredicateMatcher &B) const override { return false; }
1051
ComplexPatternOperandMatcher(unsigned InsnVarID,unsigned OpIdx,const OperandMatcher & Operand,const Record & TheDef)1052 ComplexPatternOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1053 const OperandMatcher &Operand,
1054 const Record &TheDef)
1055 : OperandPredicateMatcher(OPM_ComplexPattern, InsnVarID, OpIdx),
1056 Operand(Operand), TheDef(TheDef) {}
1057
classof(const PredicateMatcher * P)1058 static bool classof(const PredicateMatcher *P) {
1059 return P->getKind() == OPM_ComplexPattern;
1060 }
1061
1062 void emitPredicateOpcodes(MatchTable &Table,
1063 RuleMatcher &Rule) const override;
countRendererFns()1064 unsigned countRendererFns() const override { return 1; }
1065 };
1066
1067 /// Generates code to check that an operand is in a particular register bank.
1068 class RegisterBankOperandMatcher : public OperandPredicateMatcher {
1069 protected:
1070 const CodeGenRegisterClass &RC;
1071
1072 public:
RegisterBankOperandMatcher(unsigned InsnVarID,unsigned OpIdx,const CodeGenRegisterClass & RC)1073 RegisterBankOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1074 const CodeGenRegisterClass &RC)
1075 : OperandPredicateMatcher(OPM_RegBank, InsnVarID, OpIdx), RC(RC) {}
1076
1077 bool isIdentical(const PredicateMatcher &B) const override;
1078
classof(const PredicateMatcher * P)1079 static bool classof(const PredicateMatcher *P) {
1080 return P->getKind() == OPM_RegBank;
1081 }
1082
1083 void emitPredicateOpcodes(MatchTable &Table,
1084 RuleMatcher &Rule) const override;
1085 };
1086
1087 /// Generates code to check that an operand is a basic block.
1088 class MBBOperandMatcher : public OperandPredicateMatcher {
1089 public:
MBBOperandMatcher(unsigned InsnVarID,unsigned OpIdx)1090 MBBOperandMatcher(unsigned InsnVarID, unsigned OpIdx)
1091 : OperandPredicateMatcher(OPM_MBB, InsnVarID, OpIdx) {}
1092
classof(const PredicateMatcher * P)1093 static bool classof(const PredicateMatcher *P) {
1094 return P->getKind() == OPM_MBB;
1095 }
1096
1097 void emitPredicateOpcodes(MatchTable &Table,
1098 RuleMatcher &Rule) const override;
1099 };
1100
1101 class ImmOperandMatcher : public OperandPredicateMatcher {
1102 public:
ImmOperandMatcher(unsigned InsnVarID,unsigned OpIdx)1103 ImmOperandMatcher(unsigned InsnVarID, unsigned OpIdx)
1104 : OperandPredicateMatcher(IPM_Imm, InsnVarID, OpIdx) {}
1105
classof(const PredicateMatcher * P)1106 static bool classof(const PredicateMatcher *P) {
1107 return P->getKind() == IPM_Imm;
1108 }
1109
1110 void emitPredicateOpcodes(MatchTable &Table,
1111 RuleMatcher &Rule) const override;
1112 };
1113
1114 /// Generates code to check that an operand is a G_CONSTANT with a particular
1115 /// int.
1116 class ConstantIntOperandMatcher : public OperandPredicateMatcher {
1117 protected:
1118 int64_t Value;
1119
1120 public:
ConstantIntOperandMatcher(unsigned InsnVarID,unsigned OpIdx,int64_t Value)1121 ConstantIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value)
1122 : OperandPredicateMatcher(OPM_Int, InsnVarID, OpIdx), Value(Value) {}
1123
isIdentical(const PredicateMatcher & B)1124 bool isIdentical(const PredicateMatcher &B) const override {
1125 return OperandPredicateMatcher::isIdentical(B) &&
1126 Value == cast<ConstantIntOperandMatcher>(&B)->Value;
1127 }
1128
classof(const PredicateMatcher * P)1129 static bool classof(const PredicateMatcher *P) {
1130 return P->getKind() == OPM_Int;
1131 }
1132
1133 void emitPredicateOpcodes(MatchTable &Table,
1134 RuleMatcher &Rule) const override;
1135 };
1136
1137 /// Generates code to check that an operand is a raw int (where MO.isImm() or
1138 /// MO.isCImm() is true).
1139 class LiteralIntOperandMatcher : public OperandPredicateMatcher {
1140 protected:
1141 int64_t Value;
1142
1143 public:
LiteralIntOperandMatcher(unsigned InsnVarID,unsigned OpIdx,int64_t Value)1144 LiteralIntOperandMatcher(unsigned InsnVarID, unsigned OpIdx, int64_t Value)
1145 : OperandPredicateMatcher(OPM_LiteralInt, InsnVarID, OpIdx),
1146 Value(Value) {}
1147
isIdentical(const PredicateMatcher & B)1148 bool isIdentical(const PredicateMatcher &B) const override {
1149 return OperandPredicateMatcher::isIdentical(B) &&
1150 Value == cast<LiteralIntOperandMatcher>(&B)->Value;
1151 }
1152
classof(const PredicateMatcher * P)1153 static bool classof(const PredicateMatcher *P) {
1154 return P->getKind() == OPM_LiteralInt;
1155 }
1156
1157 void emitPredicateOpcodes(MatchTable &Table,
1158 RuleMatcher &Rule) const override;
1159 };
1160
1161 /// Generates code to check that an operand is an CmpInst predicate
1162 class CmpPredicateOperandMatcher : public OperandPredicateMatcher {
1163 protected:
1164 std::string PredName;
1165
1166 public:
CmpPredicateOperandMatcher(unsigned InsnVarID,unsigned OpIdx,std::string P)1167 CmpPredicateOperandMatcher(unsigned InsnVarID, unsigned OpIdx, std::string P)
1168 : OperandPredicateMatcher(OPM_CmpPredicate, InsnVarID, OpIdx),
1169 PredName(P) {}
1170
isIdentical(const PredicateMatcher & B)1171 bool isIdentical(const PredicateMatcher &B) const override {
1172 return OperandPredicateMatcher::isIdentical(B) &&
1173 PredName == cast<CmpPredicateOperandMatcher>(&B)->PredName;
1174 }
1175
classof(const PredicateMatcher * P)1176 static bool classof(const PredicateMatcher *P) {
1177 return P->getKind() == OPM_CmpPredicate;
1178 }
1179
1180 void emitPredicateOpcodes(MatchTable &Table,
1181 RuleMatcher &Rule) const override;
1182 };
1183
1184 /// Generates code to check that an operand is an intrinsic ID.
1185 class IntrinsicIDOperandMatcher : public OperandPredicateMatcher {
1186 protected:
1187 const CodeGenIntrinsic *II;
1188
1189 public:
IntrinsicIDOperandMatcher(unsigned InsnVarID,unsigned OpIdx,const CodeGenIntrinsic * II)1190 IntrinsicIDOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1191 const CodeGenIntrinsic *II)
1192 : OperandPredicateMatcher(OPM_IntrinsicID, InsnVarID, OpIdx), II(II) {}
1193
isIdentical(const PredicateMatcher & B)1194 bool isIdentical(const PredicateMatcher &B) const override {
1195 return OperandPredicateMatcher::isIdentical(B) &&
1196 II == cast<IntrinsicIDOperandMatcher>(&B)->II;
1197 }
1198
classof(const PredicateMatcher * P)1199 static bool classof(const PredicateMatcher *P) {
1200 return P->getKind() == OPM_IntrinsicID;
1201 }
1202
1203 void emitPredicateOpcodes(MatchTable &Table,
1204 RuleMatcher &Rule) const override;
1205 };
1206
1207 /// Generates code to check that this operand is an immediate whose value meets
1208 /// an immediate predicate.
1209 class OperandImmPredicateMatcher : public OperandPredicateMatcher {
1210 protected:
1211 TreePredicateFn Predicate;
1212
1213 public:
OperandImmPredicateMatcher(unsigned InsnVarID,unsigned OpIdx,const TreePredicateFn & Predicate)1214 OperandImmPredicateMatcher(unsigned InsnVarID, unsigned OpIdx,
1215 const TreePredicateFn &Predicate)
1216 : OperandPredicateMatcher(IPM_ImmPredicate, InsnVarID, OpIdx),
1217 Predicate(Predicate) {}
1218
isIdentical(const PredicateMatcher & B)1219 bool isIdentical(const PredicateMatcher &B) const override {
1220 return OperandPredicateMatcher::isIdentical(B) &&
1221 Predicate.getOrigPatFragRecord() ==
1222 cast<OperandImmPredicateMatcher>(&B)
1223 ->Predicate.getOrigPatFragRecord();
1224 }
1225
classof(const PredicateMatcher * P)1226 static bool classof(const PredicateMatcher *P) {
1227 return P->getKind() == IPM_ImmPredicate;
1228 }
1229
1230 void emitPredicateOpcodes(MatchTable &Table,
1231 RuleMatcher &Rule) const override;
1232 };
1233
1234 /// Generates code to check that a set of predicates match for a particular
1235 /// operand.
1236 class OperandMatcher : public PredicateListMatcher<OperandPredicateMatcher> {
1237 protected:
1238 InstructionMatcher &Insn;
1239 unsigned OpIdx;
1240 std::string SymbolicName;
1241
1242 /// The index of the first temporary variable allocated to this operand. The
1243 /// number of allocated temporaries can be found with
1244 /// countRendererFns().
1245 unsigned AllocatedTemporariesBaseID;
1246
1247 TempTypeIdx TTIdx = 0;
1248
1249 public:
OperandMatcher(InstructionMatcher & Insn,unsigned OpIdx,const std::string & SymbolicName,unsigned AllocatedTemporariesBaseID)1250 OperandMatcher(InstructionMatcher &Insn, unsigned OpIdx,
1251 const std::string &SymbolicName,
1252 unsigned AllocatedTemporariesBaseID)
1253 : Insn(Insn), OpIdx(OpIdx), SymbolicName(SymbolicName),
1254 AllocatedTemporariesBaseID(AllocatedTemporariesBaseID) {}
1255
hasSymbolicName()1256 bool hasSymbolicName() const { return !SymbolicName.empty(); }
getSymbolicName()1257 StringRef getSymbolicName() const { return SymbolicName; }
setSymbolicName(StringRef Name)1258 void setSymbolicName(StringRef Name) {
1259 assert(SymbolicName.empty() && "Operand already has a symbolic name");
1260 SymbolicName = std::string(Name);
1261 }
1262
1263 /// Construct a new operand predicate and add it to the matcher.
1264 template <class Kind, class... Args>
addPredicate(Args &&...args)1265 std::optional<Kind *> addPredicate(Args &&...args) {
1266 if (isSameAsAnotherOperand())
1267 return std::nullopt;
1268 Predicates.emplace_back(std::make_unique<Kind>(
1269 getInsnVarID(), getOpIdx(), std::forward<Args>(args)...));
1270 return static_cast<Kind *>(Predicates.back().get());
1271 }
1272
getOpIdx()1273 unsigned getOpIdx() const { return OpIdx; }
1274 unsigned getInsnVarID() const;
1275
1276 /// If this OperandMatcher has not been assigned a TempTypeIdx yet, assigns it
1277 /// one and adds a `RecordRegisterType` predicate to this matcher. If one has
1278 /// already been assigned, simply returns it.
1279 TempTypeIdx getTempTypeIdx(RuleMatcher &Rule);
1280
1281 std::string getOperandExpr(unsigned InsnVarID) const;
1282
getInstructionMatcher()1283 InstructionMatcher &getInstructionMatcher() const { return Insn; }
1284
1285 Error addTypeCheckPredicate(const TypeSetByHwMode &VTy,
1286 bool OperandIsAPointer);
1287
1288 /// Emit MatchTable opcodes that test whether the instruction named in
1289 /// InsnVarID matches all the predicates and all the operands.
1290 void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule);
1291
1292 /// Compare the priority of this object and B.
1293 ///
1294 /// Returns true if this object is more important than B.
1295 bool isHigherPriorityThan(OperandMatcher &B);
1296
1297 /// Report the maximum number of temporary operands needed by the operand
1298 /// matcher.
1299 unsigned countRendererFns();
1300
getAllocatedTemporariesBaseID()1301 unsigned getAllocatedTemporariesBaseID() const {
1302 return AllocatedTemporariesBaseID;
1303 }
1304
isSameAsAnotherOperand()1305 bool isSameAsAnotherOperand() {
1306 for (const auto &Predicate : predicates())
1307 if (isa<SameOperandMatcher>(Predicate))
1308 return true;
1309 return false;
1310 }
1311 };
1312
1313 /// Generates code to check a predicate on an instruction.
1314 ///
1315 /// Typical predicates include:
1316 /// * The opcode of the instruction is a particular value.
1317 /// * The nsw/nuw flag is/isn't set.
1318 class InstructionPredicateMatcher : public PredicateMatcher {
1319 public:
InstructionPredicateMatcher(PredicateKind Kind,unsigned InsnVarID)1320 InstructionPredicateMatcher(PredicateKind Kind, unsigned InsnVarID)
1321 : PredicateMatcher(Kind, InsnVarID) {}
~InstructionPredicateMatcher()1322 virtual ~InstructionPredicateMatcher() {}
1323
1324 /// Compare the priority of this object and B.
1325 ///
1326 /// Returns true if this object is more important than B.
1327 virtual bool
isHigherPriorityThan(const InstructionPredicateMatcher & B)1328 isHigherPriorityThan(const InstructionPredicateMatcher &B) const {
1329 return Kind < B.Kind;
1330 };
1331 };
1332
1333 template <>
1334 inline std::string
getNoPredicateComment()1335 PredicateListMatcher<PredicateMatcher>::getNoPredicateComment() const {
1336 return "No instruction predicates";
1337 }
1338
1339 /// Generates code to check the opcode of an instruction.
1340 class InstructionOpcodeMatcher : public InstructionPredicateMatcher {
1341 protected:
1342 // Allow matching one to several, similar opcodes that share properties. This
1343 // is to handle patterns where one SelectionDAG operation maps to multiple
1344 // GlobalISel ones (e.g. G_BUILD_VECTOR and G_BUILD_VECTOR_TRUNC). The first
1345 // is treated as the canonical opcode.
1346 SmallVector<const CodeGenInstruction *, 2> Insts;
1347
1348 static DenseMap<const CodeGenInstruction *, unsigned> OpcodeValues;
1349
1350 MatchTableRecord getInstValue(const CodeGenInstruction *I) const;
1351
1352 public:
1353 static void initOpcodeValuesMap(const CodeGenTarget &Target);
1354
InstructionOpcodeMatcher(unsigned InsnVarID,ArrayRef<const CodeGenInstruction * > I)1355 InstructionOpcodeMatcher(unsigned InsnVarID,
1356 ArrayRef<const CodeGenInstruction *> I)
1357 : InstructionPredicateMatcher(IPM_Opcode, InsnVarID),
1358 Insts(I.begin(), I.end()) {
1359 assert((Insts.size() == 1 || Insts.size() == 2) &&
1360 "unexpected number of opcode alternatives");
1361 }
1362
classof(const PredicateMatcher * P)1363 static bool classof(const PredicateMatcher *P) {
1364 return P->getKind() == IPM_Opcode;
1365 }
1366
isIdentical(const PredicateMatcher & B)1367 bool isIdentical(const PredicateMatcher &B) const override {
1368 return InstructionPredicateMatcher::isIdentical(B) &&
1369 Insts == cast<InstructionOpcodeMatcher>(&B)->Insts;
1370 }
1371
hasValue()1372 bool hasValue() const override {
1373 return Insts.size() == 1 && OpcodeValues.count(Insts[0]);
1374 }
1375
1376 // TODO: This is used for the SwitchMatcher optimization. We should be able to
1377 // return a list of the opcodes to match.
1378 MatchTableRecord getValue() const override;
1379
1380 void emitPredicateOpcodes(MatchTable &Table,
1381 RuleMatcher &Rule) const override;
1382
1383 /// Compare the priority of this object and B.
1384 ///
1385 /// Returns true if this object is more important than B.
1386 bool
1387 isHigherPriorityThan(const InstructionPredicateMatcher &B) const override;
1388
1389 bool isConstantInstruction() const;
1390
1391 // The first opcode is the canonical opcode, and later are alternatives.
1392 StringRef getOpcode() const;
getAlternativeOpcodes()1393 ArrayRef<const CodeGenInstruction *> getAlternativeOpcodes() { return Insts; }
1394 bool isVariadicNumOperands() const;
1395 StringRef getOperandType(unsigned OpIdx) const;
1396 };
1397
1398 class InstructionNumOperandsMatcher final : public InstructionPredicateMatcher {
1399 unsigned NumOperands = 0;
1400
1401 public:
InstructionNumOperandsMatcher(unsigned InsnVarID,unsigned NumOperands)1402 InstructionNumOperandsMatcher(unsigned InsnVarID, unsigned NumOperands)
1403 : InstructionPredicateMatcher(IPM_NumOperands, InsnVarID),
1404 NumOperands(NumOperands) {}
1405
classof(const PredicateMatcher * P)1406 static bool classof(const PredicateMatcher *P) {
1407 return P->getKind() == IPM_NumOperands;
1408 }
1409
isIdentical(const PredicateMatcher & B)1410 bool isIdentical(const PredicateMatcher &B) const override {
1411 return InstructionPredicateMatcher::isIdentical(B) &&
1412 NumOperands == cast<InstructionNumOperandsMatcher>(&B)->NumOperands;
1413 }
1414
1415 void emitPredicateOpcodes(MatchTable &Table,
1416 RuleMatcher &Rule) const override;
1417 };
1418
1419 /// Generates code to check that this instruction is a constant whose value
1420 /// meets an immediate predicate.
1421 ///
1422 /// Immediates are slightly odd since they are typically used like an operand
1423 /// but are represented as an operator internally. We typically write simm8:$src
1424 /// in a tablegen pattern, but this is just syntactic sugar for
1425 /// (imm:i32)<<P:Predicate_simm8>>:$imm which more directly describes the nodes
1426 /// that will be matched and the predicate (which is attached to the imm
1427 /// operator) that will be tested. In SelectionDAG this describes a
1428 /// ConstantSDNode whose internal value will be tested using the simm8
1429 /// predicate.
1430 ///
1431 /// The corresponding GlobalISel representation is %1 = G_CONSTANT iN Value. In
1432 /// this representation, the immediate could be tested with an
1433 /// InstructionMatcher, InstructionOpcodeMatcher, OperandMatcher, and a
1434 /// OperandPredicateMatcher-subclass to check the Value meets the predicate but
1435 /// there are two implementation issues with producing that matcher
1436 /// configuration from the SelectionDAG pattern:
1437 /// * ImmLeaf is a PatFrag whose root is an InstructionMatcher. This means that
1438 /// were we to sink the immediate predicate to the operand we would have to
1439 /// have two partial implementations of PatFrag support, one for immediates
1440 /// and one for non-immediates.
1441 /// * At the point we handle the predicate, the OperandMatcher hasn't been
1442 /// created yet. If we were to sink the predicate to the OperandMatcher we
1443 /// would also have to complicate (or duplicate) the code that descends and
1444 /// creates matchers for the subtree.
1445 /// Overall, it's simpler to handle it in the place it was found.
1446 class InstructionImmPredicateMatcher : public InstructionPredicateMatcher {
1447 protected:
1448 TreePredicateFn Predicate;
1449
1450 public:
InstructionImmPredicateMatcher(unsigned InsnVarID,const TreePredicateFn & Predicate)1451 InstructionImmPredicateMatcher(unsigned InsnVarID,
1452 const TreePredicateFn &Predicate)
1453 : InstructionPredicateMatcher(IPM_ImmPredicate, InsnVarID),
1454 Predicate(Predicate) {}
1455
1456 bool isIdentical(const PredicateMatcher &B) const override;
1457
classof(const PredicateMatcher * P)1458 static bool classof(const PredicateMatcher *P) {
1459 return P->getKind() == IPM_ImmPredicate;
1460 }
1461
1462 void emitPredicateOpcodes(MatchTable &Table,
1463 RuleMatcher &Rule) const override;
1464 };
1465
1466 /// Generates code to check that a memory instruction has a atomic ordering
1467 /// MachineMemoryOperand.
1468 class AtomicOrderingMMOPredicateMatcher : public InstructionPredicateMatcher {
1469 public:
1470 enum AOComparator {
1471 AO_Exactly,
1472 AO_OrStronger,
1473 AO_WeakerThan,
1474 };
1475
1476 protected:
1477 StringRef Order;
1478 AOComparator Comparator;
1479
1480 public:
1481 AtomicOrderingMMOPredicateMatcher(unsigned InsnVarID, StringRef Order,
1482 AOComparator Comparator = AO_Exactly)
InstructionPredicateMatcher(IPM_AtomicOrderingMMO,InsnVarID)1483 : InstructionPredicateMatcher(IPM_AtomicOrderingMMO, InsnVarID),
1484 Order(Order), Comparator(Comparator) {}
1485
classof(const PredicateMatcher * P)1486 static bool classof(const PredicateMatcher *P) {
1487 return P->getKind() == IPM_AtomicOrderingMMO;
1488 }
1489
1490 bool isIdentical(const PredicateMatcher &B) const override;
1491
1492 void emitPredicateOpcodes(MatchTable &Table,
1493 RuleMatcher &Rule) const override;
1494 };
1495
1496 /// Generates code to check that the size of an MMO is exactly N bytes.
1497 class MemorySizePredicateMatcher : public InstructionPredicateMatcher {
1498 protected:
1499 unsigned MMOIdx;
1500 uint64_t Size;
1501
1502 public:
MemorySizePredicateMatcher(unsigned InsnVarID,unsigned MMOIdx,unsigned Size)1503 MemorySizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, unsigned Size)
1504 : InstructionPredicateMatcher(IPM_MemoryLLTSize, InsnVarID),
1505 MMOIdx(MMOIdx), Size(Size) {}
1506
classof(const PredicateMatcher * P)1507 static bool classof(const PredicateMatcher *P) {
1508 return P->getKind() == IPM_MemoryLLTSize;
1509 }
isIdentical(const PredicateMatcher & B)1510 bool isIdentical(const PredicateMatcher &B) const override {
1511 return InstructionPredicateMatcher::isIdentical(B) &&
1512 MMOIdx == cast<MemorySizePredicateMatcher>(&B)->MMOIdx &&
1513 Size == cast<MemorySizePredicateMatcher>(&B)->Size;
1514 }
1515
1516 void emitPredicateOpcodes(MatchTable &Table,
1517 RuleMatcher &Rule) const override;
1518 };
1519
1520 class MemoryAddressSpacePredicateMatcher : public InstructionPredicateMatcher {
1521 protected:
1522 unsigned MMOIdx;
1523 SmallVector<unsigned, 4> AddrSpaces;
1524
1525 public:
MemoryAddressSpacePredicateMatcher(unsigned InsnVarID,unsigned MMOIdx,ArrayRef<unsigned> AddrSpaces)1526 MemoryAddressSpacePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
1527 ArrayRef<unsigned> AddrSpaces)
1528 : InstructionPredicateMatcher(IPM_MemoryAddressSpace, InsnVarID),
1529 MMOIdx(MMOIdx), AddrSpaces(AddrSpaces.begin(), AddrSpaces.end()) {}
1530
classof(const PredicateMatcher * P)1531 static bool classof(const PredicateMatcher *P) {
1532 return P->getKind() == IPM_MemoryAddressSpace;
1533 }
1534
1535 bool isIdentical(const PredicateMatcher &B) const override;
1536
1537 void emitPredicateOpcodes(MatchTable &Table,
1538 RuleMatcher &Rule) const override;
1539 };
1540
1541 class MemoryAlignmentPredicateMatcher : public InstructionPredicateMatcher {
1542 protected:
1543 unsigned MMOIdx;
1544 int MinAlign;
1545
1546 public:
MemoryAlignmentPredicateMatcher(unsigned InsnVarID,unsigned MMOIdx,int MinAlign)1547 MemoryAlignmentPredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
1548 int MinAlign)
1549 : InstructionPredicateMatcher(IPM_MemoryAlignment, InsnVarID),
1550 MMOIdx(MMOIdx), MinAlign(MinAlign) {
1551 assert(MinAlign > 0);
1552 }
1553
classof(const PredicateMatcher * P)1554 static bool classof(const PredicateMatcher *P) {
1555 return P->getKind() == IPM_MemoryAlignment;
1556 }
1557
1558 bool isIdentical(const PredicateMatcher &B) const override;
1559
1560 void emitPredicateOpcodes(MatchTable &Table,
1561 RuleMatcher &Rule) const override;
1562 };
1563
1564 /// Generates code to check that the size of an MMO is less-than, equal-to, or
1565 /// greater than a given LLT.
1566 class MemoryVsLLTSizePredicateMatcher : public InstructionPredicateMatcher {
1567 public:
1568 enum RelationKind {
1569 GreaterThan,
1570 EqualTo,
1571 LessThan,
1572 };
1573
1574 protected:
1575 unsigned MMOIdx;
1576 RelationKind Relation;
1577 unsigned OpIdx;
1578
1579 public:
MemoryVsLLTSizePredicateMatcher(unsigned InsnVarID,unsigned MMOIdx,enum RelationKind Relation,unsigned OpIdx)1580 MemoryVsLLTSizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx,
1581 enum RelationKind Relation, unsigned OpIdx)
1582 : InstructionPredicateMatcher(IPM_MemoryVsLLTSize, InsnVarID),
1583 MMOIdx(MMOIdx), Relation(Relation), OpIdx(OpIdx) {}
1584
classof(const PredicateMatcher * P)1585 static bool classof(const PredicateMatcher *P) {
1586 return P->getKind() == IPM_MemoryVsLLTSize;
1587 }
1588 bool isIdentical(const PredicateMatcher &B) const override;
1589
1590 void emitPredicateOpcodes(MatchTable &Table,
1591 RuleMatcher &Rule) const override;
1592 };
1593
1594 // Matcher for immAllOnesV/immAllZerosV
1595 class VectorSplatImmPredicateMatcher : public InstructionPredicateMatcher {
1596 public:
1597 enum SplatKind { AllZeros, AllOnes };
1598
1599 private:
1600 SplatKind Kind;
1601
1602 public:
VectorSplatImmPredicateMatcher(unsigned InsnVarID,SplatKind K)1603 VectorSplatImmPredicateMatcher(unsigned InsnVarID, SplatKind K)
1604 : InstructionPredicateMatcher(IPM_VectorSplatImm, InsnVarID), Kind(K) {}
1605
classof(const PredicateMatcher * P)1606 static bool classof(const PredicateMatcher *P) {
1607 return P->getKind() == IPM_VectorSplatImm;
1608 }
1609
isIdentical(const PredicateMatcher & B)1610 bool isIdentical(const PredicateMatcher &B) const override {
1611 return InstructionPredicateMatcher::isIdentical(B) &&
1612 Kind == static_cast<const VectorSplatImmPredicateMatcher &>(B).Kind;
1613 }
1614
1615 void emitPredicateOpcodes(MatchTable &Table,
1616 RuleMatcher &Rule) const override;
1617 };
1618
1619 /// Generates code to check an arbitrary C++ instruction predicate.
1620 class GenericInstructionPredicateMatcher : public InstructionPredicateMatcher {
1621 protected:
1622 std::string EnumVal;
1623
1624 public:
1625 GenericInstructionPredicateMatcher(unsigned InsnVarID,
1626 TreePredicateFn Predicate);
1627
GenericInstructionPredicateMatcher(unsigned InsnVarID,const std::string & EnumVal)1628 GenericInstructionPredicateMatcher(unsigned InsnVarID,
1629 const std::string &EnumVal)
1630 : InstructionPredicateMatcher(IPM_GenericPredicate, InsnVarID),
1631 EnumVal(EnumVal) {}
1632
classof(const InstructionPredicateMatcher * P)1633 static bool classof(const InstructionPredicateMatcher *P) {
1634 return P->getKind() == IPM_GenericPredicate;
1635 }
1636 bool isIdentical(const PredicateMatcher &B) const override;
1637 void emitPredicateOpcodes(MatchTable &Table,
1638 RuleMatcher &Rule) const override;
1639 };
1640
1641 class MIFlagsInstructionPredicateMatcher : public InstructionPredicateMatcher {
1642 SmallVector<StringRef, 2> Flags;
1643 bool CheckNot; // false = GIM_MIFlags, true = GIM_MIFlagsNot
1644
1645 public:
1646 MIFlagsInstructionPredicateMatcher(unsigned InsnVarID,
1647 ArrayRef<StringRef> FlagsToCheck,
1648 bool CheckNot = false)
InstructionPredicateMatcher(IPM_MIFlags,InsnVarID)1649 : InstructionPredicateMatcher(IPM_MIFlags, InsnVarID),
1650 Flags(FlagsToCheck), CheckNot(CheckNot) {
1651 sort(Flags);
1652 }
1653
classof(const InstructionPredicateMatcher * P)1654 static bool classof(const InstructionPredicateMatcher *P) {
1655 return P->getKind() == IPM_MIFlags;
1656 }
1657
1658 bool isIdentical(const PredicateMatcher &B) const override;
1659 void emitPredicateOpcodes(MatchTable &Table,
1660 RuleMatcher &Rule) const override;
1661 };
1662
1663 /// Generates code to check for the absence of use of the result.
1664 // TODO? Generalize this to support checking for one use.
1665 class NoUsePredicateMatcher : public InstructionPredicateMatcher {
1666 public:
NoUsePredicateMatcher(unsigned InsnVarID)1667 NoUsePredicateMatcher(unsigned InsnVarID)
1668 : InstructionPredicateMatcher(IPM_NoUse, InsnVarID) {}
1669
classof(const PredicateMatcher * P)1670 static bool classof(const PredicateMatcher *P) {
1671 return P->getKind() == IPM_NoUse;
1672 }
1673
isIdentical(const PredicateMatcher & B)1674 bool isIdentical(const PredicateMatcher &B) const override {
1675 return InstructionPredicateMatcher::isIdentical(B);
1676 }
1677
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule)1678 void emitPredicateOpcodes(MatchTable &Table,
1679 RuleMatcher &Rule) const override {
1680 Table << MatchTable::Opcode("GIM_CheckHasNoUse")
1681 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1682 << MatchTable::LineBreak;
1683 }
1684 };
1685
1686 /// Generates code to check that a set of predicates and operands match for a
1687 /// particular instruction.
1688 ///
1689 /// Typical predicates include:
1690 /// * Has a specific opcode.
1691 /// * Has an nsw/nuw flag or doesn't.
1692 class InstructionMatcher final : public PredicateListMatcher<PredicateMatcher> {
1693 protected:
1694 typedef std::vector<std::unique_ptr<OperandMatcher>> OperandVec;
1695
1696 RuleMatcher &Rule;
1697
1698 /// The operands to match. All rendered operands must be present even if the
1699 /// condition is always true.
1700 OperandVec Operands;
1701 bool NumOperandsCheck = true;
1702
1703 std::string SymbolicName;
1704 unsigned InsnVarID;
1705
1706 /// PhysRegInputs - List list has an entry for each explicitly specified
1707 /// physreg input to the pattern. The first elt is the Register node, the
1708 /// second is the recorded slot number the input pattern match saved it in.
1709 SmallVector<std::pair<Record *, unsigned>, 2> PhysRegInputs;
1710
1711 public:
1712 InstructionMatcher(RuleMatcher &Rule, StringRef SymbolicName,
1713 bool NumOpsCheck = true)
Rule(Rule)1714 : Rule(Rule), NumOperandsCheck(NumOpsCheck), SymbolicName(SymbolicName) {
1715 // We create a new instruction matcher.
1716 // Get a new ID for that instruction.
1717 InsnVarID = Rule.implicitlyDefineInsnVar(*this);
1718 }
1719
1720 /// Construct a new instruction predicate and add it to the matcher.
1721 template <class Kind, class... Args>
addPredicate(Args &&...args)1722 std::optional<Kind *> addPredicate(Args &&...args) {
1723 Predicates.emplace_back(
1724 std::make_unique<Kind>(getInsnVarID(), std::forward<Args>(args)...));
1725 return static_cast<Kind *>(Predicates.back().get());
1726 }
1727
getRuleMatcher()1728 RuleMatcher &getRuleMatcher() const { return Rule; }
1729
getInsnVarID()1730 unsigned getInsnVarID() const { return InsnVarID; }
1731
1732 /// Add an operand to the matcher.
1733 OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName,
1734 unsigned AllocatedTemporariesBaseID);
1735 OperandMatcher &getOperand(unsigned OpIdx);
1736 OperandMatcher &addPhysRegInput(Record *Reg, unsigned OpIdx,
1737 unsigned TempOpIdx);
1738
getPhysRegInputs()1739 ArrayRef<std::pair<Record *, unsigned>> getPhysRegInputs() const {
1740 return PhysRegInputs;
1741 }
1742
getSymbolicName()1743 StringRef getSymbolicName() const { return SymbolicName; }
getNumOperands()1744 unsigned getNumOperands() const { return Operands.size(); }
operands_begin()1745 OperandVec::iterator operands_begin() { return Operands.begin(); }
operands_end()1746 OperandVec::iterator operands_end() { return Operands.end(); }
operands()1747 iterator_range<OperandVec::iterator> operands() {
1748 return make_range(operands_begin(), operands_end());
1749 }
operands_begin()1750 OperandVec::const_iterator operands_begin() const { return Operands.begin(); }
operands_end()1751 OperandVec::const_iterator operands_end() const { return Operands.end(); }
operands()1752 iterator_range<OperandVec::const_iterator> operands() const {
1753 return make_range(operands_begin(), operands_end());
1754 }
operands_empty()1755 bool operands_empty() const { return Operands.empty(); }
1756
pop_front()1757 void pop_front() { Operands.erase(Operands.begin()); }
1758
1759 void optimize();
1760
1761 /// Emit MatchTable opcodes that test whether the instruction named in
1762 /// InsnVarName matches all the predicates and all the operands.
1763 void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule);
1764
1765 /// Compare the priority of this object and B.
1766 ///
1767 /// Returns true if this object is more important than B.
1768 bool isHigherPriorityThan(InstructionMatcher &B);
1769
1770 /// Report the maximum number of temporary operands needed by the instruction
1771 /// matcher.
1772 unsigned countRendererFns();
1773
getOpcodeMatcher()1774 InstructionOpcodeMatcher &getOpcodeMatcher() {
1775 for (auto &P : predicates())
1776 if (auto *OpMatcher = dyn_cast<InstructionOpcodeMatcher>(P.get()))
1777 return *OpMatcher;
1778 llvm_unreachable("Didn't find an opcode matcher");
1779 }
1780
isConstantInstruction()1781 bool isConstantInstruction() {
1782 return getOpcodeMatcher().isConstantInstruction();
1783 }
1784
getOpcode()1785 StringRef getOpcode() { return getOpcodeMatcher().getOpcode(); }
1786 };
1787
1788 /// Generates code to check that the operand is a register defined by an
1789 /// instruction that matches the given instruction matcher.
1790 ///
1791 /// For example, the pattern:
1792 /// (set $dst, (G_MUL (G_ADD $src1, $src2), $src3))
1793 /// would use an InstructionOperandMatcher for operand 1 of the G_MUL to match
1794 /// the:
1795 /// (G_ADD $src1, $src2)
1796 /// subpattern.
1797 class InstructionOperandMatcher : public OperandPredicateMatcher {
1798 protected:
1799 std::unique_ptr<InstructionMatcher> InsnMatcher;
1800
1801 GISelFlags Flags;
1802
1803 public:
1804 InstructionOperandMatcher(unsigned InsnVarID, unsigned OpIdx,
1805 RuleMatcher &Rule, StringRef SymbolicName,
1806 bool NumOpsCheck = true)
OperandPredicateMatcher(OPM_Instruction,InsnVarID,OpIdx)1807 : OperandPredicateMatcher(OPM_Instruction, InsnVarID, OpIdx),
1808 InsnMatcher(new InstructionMatcher(Rule, SymbolicName, NumOpsCheck)),
1809 Flags(Rule.getGISelFlags()) {}
1810
classof(const PredicateMatcher * P)1811 static bool classof(const PredicateMatcher *P) {
1812 return P->getKind() == OPM_Instruction;
1813 }
1814
getInsnMatcher()1815 InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; }
1816
1817 void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const;
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule)1818 void emitPredicateOpcodes(MatchTable &Table,
1819 RuleMatcher &Rule) const override {
1820 emitCaptureOpcodes(Table, Rule);
1821 InsnMatcher->emitPredicateOpcodes(Table, Rule);
1822 }
1823
1824 bool isHigherPriorityThan(const OperandPredicateMatcher &B) const override;
1825
1826 /// Report the maximum number of temporary operands needed by the predicate
1827 /// matcher.
countRendererFns()1828 unsigned countRendererFns() const override {
1829 return InsnMatcher->countRendererFns();
1830 }
1831 };
1832
1833 //===- Actions ------------------------------------------------------------===//
1834 class OperandRenderer {
1835 public:
1836 enum RendererKind {
1837 OR_Copy,
1838 OR_CopyOrAddZeroReg,
1839 OR_CopySubReg,
1840 OR_CopyPhysReg,
1841 OR_CopyConstantAsImm,
1842 OR_CopyFConstantAsFPImm,
1843 OR_Imm,
1844 OR_SubRegIndex,
1845 OR_Register,
1846 OR_TempRegister,
1847 OR_ComplexPattern,
1848 OR_Custom,
1849 OR_CustomOperand
1850 };
1851
1852 protected:
1853 RendererKind Kind;
1854
1855 public:
OperandRenderer(RendererKind Kind)1856 OperandRenderer(RendererKind Kind) : Kind(Kind) {}
1857 virtual ~OperandRenderer();
1858
getKind()1859 RendererKind getKind() const { return Kind; }
1860
1861 virtual void emitRenderOpcodes(MatchTable &Table,
1862 RuleMatcher &Rule) const = 0;
1863 };
1864
1865 /// A CopyRenderer emits code to copy a single operand from an existing
1866 /// instruction to the one being built.
1867 class CopyRenderer : public OperandRenderer {
1868 protected:
1869 unsigned NewInsnID;
1870 /// The name of the operand.
1871 const StringRef SymbolicName;
1872
1873 public:
CopyRenderer(unsigned NewInsnID,StringRef SymbolicName)1874 CopyRenderer(unsigned NewInsnID, StringRef SymbolicName)
1875 : OperandRenderer(OR_Copy), NewInsnID(NewInsnID),
1876 SymbolicName(SymbolicName) {
1877 assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
1878 }
1879
classof(const OperandRenderer * R)1880 static bool classof(const OperandRenderer *R) {
1881 return R->getKind() == OR_Copy;
1882 }
1883
getSymbolicName()1884 StringRef getSymbolicName() const { return SymbolicName; }
1885
1886 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
1887 };
1888
1889 /// A CopyRenderer emits code to copy a virtual register to a specific physical
1890 /// register.
1891 class CopyPhysRegRenderer : public OperandRenderer {
1892 protected:
1893 unsigned NewInsnID;
1894 Record *PhysReg;
1895
1896 public:
CopyPhysRegRenderer(unsigned NewInsnID,Record * Reg)1897 CopyPhysRegRenderer(unsigned NewInsnID, Record *Reg)
1898 : OperandRenderer(OR_CopyPhysReg), NewInsnID(NewInsnID), PhysReg(Reg) {
1899 assert(PhysReg);
1900 }
1901
classof(const OperandRenderer * R)1902 static bool classof(const OperandRenderer *R) {
1903 return R->getKind() == OR_CopyPhysReg;
1904 }
1905
getPhysReg()1906 Record *getPhysReg() const { return PhysReg; }
1907
1908 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
1909 };
1910
1911 /// A CopyOrAddZeroRegRenderer emits code to copy a single operand from an
1912 /// existing instruction to the one being built. If the operand turns out to be
1913 /// a 'G_CONSTANT 0' then it replaces the operand with a zero register.
1914 class CopyOrAddZeroRegRenderer : public OperandRenderer {
1915 protected:
1916 unsigned NewInsnID;
1917 /// The name of the operand.
1918 const StringRef SymbolicName;
1919 const Record *ZeroRegisterDef;
1920
1921 public:
CopyOrAddZeroRegRenderer(unsigned NewInsnID,StringRef SymbolicName,Record * ZeroRegisterDef)1922 CopyOrAddZeroRegRenderer(unsigned NewInsnID, StringRef SymbolicName,
1923 Record *ZeroRegisterDef)
1924 : OperandRenderer(OR_CopyOrAddZeroReg), NewInsnID(NewInsnID),
1925 SymbolicName(SymbolicName), ZeroRegisterDef(ZeroRegisterDef) {
1926 assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
1927 }
1928
classof(const OperandRenderer * R)1929 static bool classof(const OperandRenderer *R) {
1930 return R->getKind() == OR_CopyOrAddZeroReg;
1931 }
1932
getSymbolicName()1933 StringRef getSymbolicName() const { return SymbolicName; }
1934
1935 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
1936 };
1937
1938 /// A CopyConstantAsImmRenderer emits code to render a G_CONSTANT instruction to
1939 /// an extended immediate operand.
1940 class CopyConstantAsImmRenderer : public OperandRenderer {
1941 protected:
1942 unsigned NewInsnID;
1943 /// The name of the operand.
1944 const std::string SymbolicName;
1945 bool Signed;
1946
1947 public:
CopyConstantAsImmRenderer(unsigned NewInsnID,StringRef SymbolicName)1948 CopyConstantAsImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
1949 : OperandRenderer(OR_CopyConstantAsImm), NewInsnID(NewInsnID),
1950 SymbolicName(SymbolicName), Signed(true) {}
1951
classof(const OperandRenderer * R)1952 static bool classof(const OperandRenderer *R) {
1953 return R->getKind() == OR_CopyConstantAsImm;
1954 }
1955
getSymbolicName()1956 StringRef getSymbolicName() const { return SymbolicName; }
1957
1958 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
1959 };
1960
1961 /// A CopyFConstantAsFPImmRenderer emits code to render a G_FCONSTANT
1962 /// instruction to an extended immediate operand.
1963 class CopyFConstantAsFPImmRenderer : public OperandRenderer {
1964 protected:
1965 unsigned NewInsnID;
1966 /// The name of the operand.
1967 const std::string SymbolicName;
1968
1969 public:
CopyFConstantAsFPImmRenderer(unsigned NewInsnID,StringRef SymbolicName)1970 CopyFConstantAsFPImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
1971 : OperandRenderer(OR_CopyFConstantAsFPImm), NewInsnID(NewInsnID),
1972 SymbolicName(SymbolicName) {}
1973
classof(const OperandRenderer * R)1974 static bool classof(const OperandRenderer *R) {
1975 return R->getKind() == OR_CopyFConstantAsFPImm;
1976 }
1977
getSymbolicName()1978 StringRef getSymbolicName() const { return SymbolicName; }
1979
1980 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
1981 };
1982
1983 /// A CopySubRegRenderer emits code to copy a single register operand from an
1984 /// existing instruction to the one being built and indicate that only a
1985 /// subregister should be copied.
1986 class CopySubRegRenderer : public OperandRenderer {
1987 protected:
1988 unsigned NewInsnID;
1989 /// The name of the operand.
1990 const StringRef SymbolicName;
1991 /// The subregister to extract.
1992 const CodeGenSubRegIndex *SubReg;
1993
1994 public:
CopySubRegRenderer(unsigned NewInsnID,StringRef SymbolicName,const CodeGenSubRegIndex * SubReg)1995 CopySubRegRenderer(unsigned NewInsnID, StringRef SymbolicName,
1996 const CodeGenSubRegIndex *SubReg)
1997 : OperandRenderer(OR_CopySubReg), NewInsnID(NewInsnID),
1998 SymbolicName(SymbolicName), SubReg(SubReg) {}
1999
classof(const OperandRenderer * R)2000 static bool classof(const OperandRenderer *R) {
2001 return R->getKind() == OR_CopySubReg;
2002 }
2003
getSymbolicName()2004 StringRef getSymbolicName() const { return SymbolicName; }
2005
2006 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
2007 };
2008
2009 /// Adds a specific physical register to the instruction being built.
2010 /// This is typically useful for WZR/XZR on AArch64.
2011 class AddRegisterRenderer : public OperandRenderer {
2012 protected:
2013 unsigned InsnID;
2014 const Record *RegisterDef;
2015 bool IsDef;
2016 const CodeGenTarget &Target;
2017
2018 public:
2019 AddRegisterRenderer(unsigned InsnID, const CodeGenTarget &Target,
2020 const Record *RegisterDef, bool IsDef = false)
OperandRenderer(OR_Register)2021 : OperandRenderer(OR_Register), InsnID(InsnID), RegisterDef(RegisterDef),
2022 IsDef(IsDef), Target(Target) {}
2023
classof(const OperandRenderer * R)2024 static bool classof(const OperandRenderer *R) {
2025 return R->getKind() == OR_Register;
2026 }
2027
2028 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
2029 };
2030
2031 /// Adds a specific temporary virtual register to the instruction being built.
2032 /// This is used to chain instructions together when emitting multiple
2033 /// instructions.
2034 class TempRegRenderer : public OperandRenderer {
2035 protected:
2036 unsigned InsnID;
2037 unsigned TempRegID;
2038 const CodeGenSubRegIndex *SubRegIdx;
2039 bool IsDef;
2040 bool IsDead;
2041
2042 public:
2043 TempRegRenderer(unsigned InsnID, unsigned TempRegID, bool IsDef = false,
2044 const CodeGenSubRegIndex *SubReg = nullptr,
2045 bool IsDead = false)
OperandRenderer(OR_Register)2046 : OperandRenderer(OR_Register), InsnID(InsnID), TempRegID(TempRegID),
2047 SubRegIdx(SubReg), IsDef(IsDef), IsDead(IsDead) {}
2048
classof(const OperandRenderer * R)2049 static bool classof(const OperandRenderer *R) {
2050 return R->getKind() == OR_TempRegister;
2051 }
2052
2053 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
2054 };
2055
2056 /// Adds a specific immediate to the instruction being built.
2057 /// If a LLT is passed, a ConstantInt immediate is created instead.
2058 class ImmRenderer : public OperandRenderer {
2059 protected:
2060 unsigned InsnID;
2061 int64_t Imm;
2062 std::optional<LLTCodeGenOrTempType> CImmLLT;
2063
2064 public:
ImmRenderer(unsigned InsnID,int64_t Imm)2065 ImmRenderer(unsigned InsnID, int64_t Imm)
2066 : OperandRenderer(OR_Imm), InsnID(InsnID), Imm(Imm) {}
2067
ImmRenderer(unsigned InsnID,int64_t Imm,const LLTCodeGenOrTempType & CImmLLT)2068 ImmRenderer(unsigned InsnID, int64_t Imm, const LLTCodeGenOrTempType &CImmLLT)
2069 : OperandRenderer(OR_Imm), InsnID(InsnID), Imm(Imm), CImmLLT(CImmLLT) {
2070 if (CImmLLT.isLLTCodeGen())
2071 KnownTypes.insert(CImmLLT.getLLTCodeGen());
2072 }
2073
classof(const OperandRenderer * R)2074 static bool classof(const OperandRenderer *R) {
2075 return R->getKind() == OR_Imm;
2076 }
2077
2078 static void emitAddImm(MatchTable &Table, RuleMatcher &RM, unsigned InsnID,
2079 int64_t Imm, StringRef ImmName = "Imm");
2080
2081 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
2082 };
2083
2084 /// Adds an enum value for a subreg index to the instruction being built.
2085 class SubRegIndexRenderer : public OperandRenderer {
2086 protected:
2087 unsigned InsnID;
2088 const CodeGenSubRegIndex *SubRegIdx;
2089
2090 public:
SubRegIndexRenderer(unsigned InsnID,const CodeGenSubRegIndex * SRI)2091 SubRegIndexRenderer(unsigned InsnID, const CodeGenSubRegIndex *SRI)
2092 : OperandRenderer(OR_SubRegIndex), InsnID(InsnID), SubRegIdx(SRI) {}
2093
classof(const OperandRenderer * R)2094 static bool classof(const OperandRenderer *R) {
2095 return R->getKind() == OR_SubRegIndex;
2096 }
2097
2098 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
2099 };
2100
2101 /// Adds operands by calling a renderer function supplied by the ComplexPattern
2102 /// matcher function.
2103 class RenderComplexPatternOperand : public OperandRenderer {
2104 private:
2105 unsigned InsnID;
2106 const Record &TheDef;
2107 /// The name of the operand.
2108 const StringRef SymbolicName;
2109 /// The renderer number. This must be unique within a rule since it's used to
2110 /// identify a temporary variable to hold the renderer function.
2111 unsigned RendererID;
2112 /// When provided, this is the suboperand of the ComplexPattern operand to
2113 /// render. Otherwise all the suboperands will be rendered.
2114 std::optional<unsigned> SubOperand;
2115 /// The subregister to extract. Render the whole register if not specified.
2116 const CodeGenSubRegIndex *SubReg;
2117
getNumOperands()2118 unsigned getNumOperands() const {
2119 return TheDef.getValueAsDag("Operands")->getNumArgs();
2120 }
2121
2122 public:
2123 RenderComplexPatternOperand(unsigned InsnID, const Record &TheDef,
2124 StringRef SymbolicName, unsigned RendererID,
2125 std::optional<unsigned> SubOperand = std::nullopt,
2126 const CodeGenSubRegIndex *SubReg = nullptr)
OperandRenderer(OR_ComplexPattern)2127 : OperandRenderer(OR_ComplexPattern), InsnID(InsnID), TheDef(TheDef),
2128 SymbolicName(SymbolicName), RendererID(RendererID),
2129 SubOperand(SubOperand), SubReg(SubReg) {}
2130
classof(const OperandRenderer * R)2131 static bool classof(const OperandRenderer *R) {
2132 return R->getKind() == OR_ComplexPattern;
2133 }
2134
2135 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
2136 };
2137
2138 class CustomRenderer : public OperandRenderer {
2139 protected:
2140 unsigned InsnID;
2141 const Record &Renderer;
2142 /// The name of the operand.
2143 const std::string SymbolicName;
2144
2145 public:
CustomRenderer(unsigned InsnID,const Record & Renderer,StringRef SymbolicName)2146 CustomRenderer(unsigned InsnID, const Record &Renderer,
2147 StringRef SymbolicName)
2148 : OperandRenderer(OR_Custom), InsnID(InsnID), Renderer(Renderer),
2149 SymbolicName(SymbolicName) {}
2150
classof(const OperandRenderer * R)2151 static bool classof(const OperandRenderer *R) {
2152 return R->getKind() == OR_Custom;
2153 }
2154
2155 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
2156 };
2157
2158 class CustomOperandRenderer : public OperandRenderer {
2159 protected:
2160 unsigned InsnID;
2161 const Record &Renderer;
2162 /// The name of the operand.
2163 const std::string SymbolicName;
2164
2165 public:
CustomOperandRenderer(unsigned InsnID,const Record & Renderer,StringRef SymbolicName)2166 CustomOperandRenderer(unsigned InsnID, const Record &Renderer,
2167 StringRef SymbolicName)
2168 : OperandRenderer(OR_CustomOperand), InsnID(InsnID), Renderer(Renderer),
2169 SymbolicName(SymbolicName) {}
2170
classof(const OperandRenderer * R)2171 static bool classof(const OperandRenderer *R) {
2172 return R->getKind() == OR_CustomOperand;
2173 }
2174
2175 void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
2176 };
2177
2178 /// An action taken when all Matcher predicates succeeded for a parent rule.
2179 ///
2180 /// Typical actions include:
2181 /// * Changing the opcode of an instruction.
2182 /// * Adding an operand to an instruction.
2183 class MatchAction {
2184 public:
2185 enum ActionKind {
2186 AK_DebugComment,
2187 AK_CustomCXX,
2188 AK_BuildMI,
2189 AK_BuildConstantMI,
2190 AK_EraseInst,
2191 AK_ReplaceReg,
2192 AK_ConstraintOpsToDef,
2193 AK_ConstraintOpsToRC,
2194 AK_MakeTempReg,
2195 };
2196
MatchAction(ActionKind K)2197 MatchAction(ActionKind K) : Kind(K) {}
2198
getKind()2199 ActionKind getKind() const { return Kind; }
2200
~MatchAction()2201 virtual ~MatchAction() {}
2202
2203 // Some actions may need to add extra predicates to ensure they can run.
emitAdditionalPredicates(MatchTable & Table,RuleMatcher & Rule)2204 virtual void emitAdditionalPredicates(MatchTable &Table,
2205 RuleMatcher &Rule) const {}
2206
2207 /// Emit the MatchTable opcodes to implement the action.
2208 virtual void emitActionOpcodes(MatchTable &Table,
2209 RuleMatcher &Rule) const = 0;
2210
2211 private:
2212 ActionKind Kind;
2213 };
2214
2215 /// Generates a comment describing the matched rule being acted upon.
2216 class DebugCommentAction : public MatchAction {
2217 private:
2218 std::string S;
2219
2220 public:
DebugCommentAction(StringRef S)2221 DebugCommentAction(StringRef S)
2222 : MatchAction(AK_DebugComment), S(std::string(S)) {}
2223
classof(const MatchAction * A)2224 static bool classof(const MatchAction *A) {
2225 return A->getKind() == AK_DebugComment;
2226 }
2227
emitActionOpcodes(MatchTable & Table,RuleMatcher & Rule)2228 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2229 Table << MatchTable::Comment(S) << MatchTable::LineBreak;
2230 }
2231 };
2232
2233 class CustomCXXAction : public MatchAction {
2234 std::string FnEnumName;
2235
2236 public:
CustomCXXAction(StringRef FnEnumName)2237 CustomCXXAction(StringRef FnEnumName)
2238 : MatchAction(AK_CustomCXX), FnEnumName(FnEnumName.str()) {}
2239
classof(const MatchAction * A)2240 static bool classof(const MatchAction *A) {
2241 return A->getKind() == AK_CustomCXX;
2242 }
2243
2244 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
2245 };
2246
2247 /// Generates code to build an instruction or mutate an existing instruction
2248 /// into the desired instruction when this is possible.
2249 class BuildMIAction : public MatchAction {
2250 private:
2251 unsigned InsnID;
2252 const CodeGenInstruction *I;
2253 InstructionMatcher *Matched;
2254 std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers;
2255 SmallPtrSet<Record *, 4> DeadImplicitDefs;
2256
2257 std::vector<const InstructionMatcher *> CopiedFlags;
2258 std::vector<StringRef> SetFlags;
2259 std::vector<StringRef> UnsetFlags;
2260
2261 /// True if the instruction can be built solely by mutating the opcode.
2262 bool canMutate(RuleMatcher &Rule, const InstructionMatcher *Insn) const;
2263
2264 public:
BuildMIAction(unsigned InsnID,const CodeGenInstruction * I)2265 BuildMIAction(unsigned InsnID, const CodeGenInstruction *I)
2266 : MatchAction(AK_BuildMI), InsnID(InsnID), I(I), Matched(nullptr) {}
2267
classof(const MatchAction * A)2268 static bool classof(const MatchAction *A) {
2269 return A->getKind() == AK_BuildMI;
2270 }
2271
getInsnID()2272 unsigned getInsnID() const { return InsnID; }
getCGI()2273 const CodeGenInstruction *getCGI() const { return I; }
2274
addSetMIFlags(StringRef Flag)2275 void addSetMIFlags(StringRef Flag) { SetFlags.push_back(Flag); }
addUnsetMIFlags(StringRef Flag)2276 void addUnsetMIFlags(StringRef Flag) { UnsetFlags.push_back(Flag); }
addCopiedMIFlags(const InstructionMatcher & IM)2277 void addCopiedMIFlags(const InstructionMatcher &IM) {
2278 CopiedFlags.push_back(&IM);
2279 }
2280
2281 void chooseInsnToMutate(RuleMatcher &Rule);
2282
setDeadImplicitDef(Record * R)2283 void setDeadImplicitDef(Record *R) { DeadImplicitDefs.insert(R); }
2284
addRenderer(Args &&...args)2285 template <class Kind, class... Args> Kind &addRenderer(Args &&...args) {
2286 OperandRenderers.emplace_back(
2287 std::make_unique<Kind>(InsnID, std::forward<Args>(args)...));
2288 return *static_cast<Kind *>(OperandRenderers.back().get());
2289 }
2290
2291 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
2292 };
2293
2294 /// Generates code to create a constant that defines a TempReg.
2295 /// The instruction created is usually a G_CONSTANT but it could also be a
2296 /// G_BUILD_VECTOR for vector types.
2297 class BuildConstantAction : public MatchAction {
2298 unsigned TempRegID;
2299 int64_t Val;
2300
2301 public:
BuildConstantAction(unsigned TempRegID,int64_t Val)2302 BuildConstantAction(unsigned TempRegID, int64_t Val)
2303 : MatchAction(AK_BuildConstantMI), TempRegID(TempRegID), Val(Val) {}
2304
classof(const MatchAction * A)2305 static bool classof(const MatchAction *A) {
2306 return A->getKind() == AK_BuildConstantMI;
2307 }
2308
2309 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
2310 };
2311
2312 class EraseInstAction : public MatchAction {
2313 unsigned InsnID;
2314
2315 public:
EraseInstAction(unsigned InsnID)2316 EraseInstAction(unsigned InsnID)
2317 : MatchAction(AK_EraseInst), InsnID(InsnID) {}
2318
classof(const MatchAction * A)2319 static bool classof(const MatchAction *A) {
2320 return A->getKind() == AK_EraseInst;
2321 }
2322
2323 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
2324 static void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule,
2325 unsigned InsnID);
2326 };
2327
2328 class ReplaceRegAction : public MatchAction {
2329 unsigned OldInsnID, OldOpIdx;
2330 unsigned NewInsnId = -1, NewOpIdx;
2331 unsigned TempRegID = -1;
2332
2333 public:
ReplaceRegAction(unsigned OldInsnID,unsigned OldOpIdx,unsigned NewInsnId,unsigned NewOpIdx)2334 ReplaceRegAction(unsigned OldInsnID, unsigned OldOpIdx, unsigned NewInsnId,
2335 unsigned NewOpIdx)
2336 : MatchAction(AK_EraseInst), OldInsnID(OldInsnID), OldOpIdx(OldOpIdx),
2337 NewInsnId(NewInsnId), NewOpIdx(NewOpIdx) {}
2338
ReplaceRegAction(unsigned OldInsnID,unsigned OldOpIdx,unsigned TempRegID)2339 ReplaceRegAction(unsigned OldInsnID, unsigned OldOpIdx, unsigned TempRegID)
2340 : MatchAction(AK_EraseInst), OldInsnID(OldInsnID), OldOpIdx(OldOpIdx),
2341 TempRegID(TempRegID) {}
2342
classof(const MatchAction * A)2343 static bool classof(const MatchAction *A) {
2344 return A->getKind() == AK_ReplaceReg;
2345 }
2346
2347 void emitAdditionalPredicates(MatchTable &Table,
2348 RuleMatcher &Rule) const override;
2349 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
2350 };
2351
2352 /// Generates code to constrain the operands of an output instruction to the
2353 /// register classes specified by the definition of that instruction.
2354 class ConstrainOperandsToDefinitionAction : public MatchAction {
2355 unsigned InsnID;
2356
2357 public:
ConstrainOperandsToDefinitionAction(unsigned InsnID)2358 ConstrainOperandsToDefinitionAction(unsigned InsnID)
2359 : MatchAction(AK_ConstraintOpsToDef), InsnID(InsnID) {}
2360
classof(const MatchAction * A)2361 static bool classof(const MatchAction *A) {
2362 return A->getKind() == AK_ConstraintOpsToDef;
2363 }
2364
emitActionOpcodes(MatchTable & Table,RuleMatcher & Rule)2365 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
2366 Table << MatchTable::Opcode("GIR_ConstrainSelectedInstOperands")
2367 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
2368 << MatchTable::LineBreak;
2369 }
2370 };
2371
2372 /// Generates code to constrain the specified operand of an output instruction
2373 /// to the specified register class.
2374 class ConstrainOperandToRegClassAction : public MatchAction {
2375 unsigned InsnID;
2376 unsigned OpIdx;
2377 const CodeGenRegisterClass &RC;
2378
2379 public:
ConstrainOperandToRegClassAction(unsigned InsnID,unsigned OpIdx,const CodeGenRegisterClass & RC)2380 ConstrainOperandToRegClassAction(unsigned InsnID, unsigned OpIdx,
2381 const CodeGenRegisterClass &RC)
2382 : MatchAction(AK_ConstraintOpsToRC), InsnID(InsnID), OpIdx(OpIdx),
2383 RC(RC) {}
2384
classof(const MatchAction * A)2385 static bool classof(const MatchAction *A) {
2386 return A->getKind() == AK_ConstraintOpsToRC;
2387 }
2388
2389 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
2390 };
2391
2392 /// Generates code to create a temporary register which can be used to chain
2393 /// instructions together.
2394 class MakeTempRegisterAction : public MatchAction {
2395 private:
2396 LLTCodeGenOrTempType Ty;
2397 unsigned TempRegID;
2398
2399 public:
MakeTempRegisterAction(const LLTCodeGenOrTempType & Ty,unsigned TempRegID)2400 MakeTempRegisterAction(const LLTCodeGenOrTempType &Ty, unsigned TempRegID)
2401 : MatchAction(AK_MakeTempReg), Ty(Ty), TempRegID(TempRegID) {
2402 if (Ty.isLLTCodeGen())
2403 KnownTypes.insert(Ty.getLLTCodeGen());
2404 }
2405
classof(const MatchAction * A)2406 static bool classof(const MatchAction *A) {
2407 return A->getKind() == AK_MakeTempReg;
2408 }
2409
2410 void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
2411 };
2412
2413 } // namespace gi
2414 } // namespace llvm
2415
2416 #endif
2417