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