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