1 //===- llvm/CodeGen/GlobalISel/LegalizerInfo.h ------------------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 /// Interface for Targets to specify which operations they can successfully
11 /// select and how the others should be expanded most efficiently.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #ifndef LLVM_CODEGEN_GLOBALISEL_LEGALIZERINFO_H
16 #define LLVM_CODEGEN_GLOBALISEL_LEGALIZERINFO_H
17
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/None.h"
20 #include "llvm/ADT/Optional.h"
21 #include "llvm/ADT/STLExtras.h"
22 #include "llvm/ADT/SmallBitVector.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/CodeGen/MachineFunction.h"
25 #include "llvm/CodeGen/TargetOpcodes.h"
26 #include "llvm/Support/raw_ostream.h"
27 #include "llvm/Support/LowLevelTypeImpl.h"
28 #include <cassert>
29 #include <cstdint>
30 #include <tuple>
31 #include <unordered_map>
32 #include <utility>
33
34 namespace llvm {
35
36 extern cl::opt<bool> DisableGISelLegalityCheck;
37
38 class MachineInstr;
39 class MachineIRBuilder;
40 class MachineRegisterInfo;
41 class MCInstrInfo;
42 class GISelChangeObserver;
43
44 namespace LegalizeActions {
45 enum LegalizeAction : std::uint8_t {
46 /// The operation is expected to be selectable directly by the target, and
47 /// no transformation is necessary.
48 Legal,
49
50 /// The operation should be synthesized from multiple instructions acting on
51 /// a narrower scalar base-type. For example a 64-bit add might be
52 /// implemented in terms of 32-bit add-with-carry.
53 NarrowScalar,
54
55 /// The operation should be implemented in terms of a wider scalar
56 /// base-type. For example a <2 x s8> add could be implemented as a <2
57 /// x s32> add (ignoring the high bits).
58 WidenScalar,
59
60 /// The (vector) operation should be implemented by splitting it into
61 /// sub-vectors where the operation is legal. For example a <8 x s64> add
62 /// might be implemented as 4 separate <2 x s64> adds.
63 FewerElements,
64
65 /// The (vector) operation should be implemented by widening the input
66 /// vector and ignoring the lanes added by doing so. For example <2 x i8> is
67 /// rarely legal, but you might perform an <8 x i8> and then only look at
68 /// the first two results.
69 MoreElements,
70
71 /// The operation itself must be expressed in terms of simpler actions on
72 /// this target. E.g. a SREM replaced by an SDIV and subtraction.
73 Lower,
74
75 /// The operation should be implemented as a call to some kind of runtime
76 /// support library. For example this usually happens on machines that don't
77 /// support floating-point operations natively.
78 Libcall,
79
80 /// The target wants to do something special with this combination of
81 /// operand and type. A callback will be issued when it is needed.
82 Custom,
83
84 /// This operation is completely unsupported on the target. A programming
85 /// error has occurred.
86 Unsupported,
87
88 /// Sentinel value for when no action was found in the specified table.
89 NotFound,
90
91 /// Fall back onto the old rules.
92 /// TODO: Remove this once we've migrated
93 UseLegacyRules,
94 };
95 } // end namespace LegalizeActions
96
97 using LegalizeActions::LegalizeAction;
98
99 /// Legalization is decided based on an instruction's opcode, which type slot
100 /// we're considering, and what the existing type is. These aspects are gathered
101 /// together for convenience in the InstrAspect class.
102 struct InstrAspect {
103 unsigned Opcode;
104 unsigned Idx = 0;
105 LLT Type;
106
InstrAspectInstrAspect107 InstrAspect(unsigned Opcode, LLT Type) : Opcode(Opcode), Type(Type) {}
InstrAspectInstrAspect108 InstrAspect(unsigned Opcode, unsigned Idx, LLT Type)
109 : Opcode(Opcode), Idx(Idx), Type(Type) {}
110
111 bool operator==(const InstrAspect &RHS) const {
112 return Opcode == RHS.Opcode && Idx == RHS.Idx && Type == RHS.Type;
113 }
114 };
115
116 /// The LegalityQuery object bundles together all the information that's needed
117 /// to decide whether a given operation is legal or not.
118 /// For efficiency, it doesn't make a copy of Types so care must be taken not
119 /// to free it before using the query.
120 struct LegalityQuery {
121 unsigned Opcode;
122 ArrayRef<LLT> Types;
123
124 struct MemDesc {
125 uint64_t SizeInBits;
126 AtomicOrdering Ordering;
127 };
128
129 /// Operations which require memory can use this to place requirements on the
130 /// memory type for each MMO.
131 ArrayRef<MemDesc> MMODescrs;
132
LegalityQueryLegalityQuery133 constexpr LegalityQuery(unsigned Opcode, const ArrayRef<LLT> Types,
134 const ArrayRef<MemDesc> MMODescrs)
135 : Opcode(Opcode), Types(Types), MMODescrs(MMODescrs) {}
LegalityQueryLegalityQuery136 constexpr LegalityQuery(unsigned Opcode, const ArrayRef<LLT> Types)
137 : LegalityQuery(Opcode, Types, {}) {}
138
139 raw_ostream &print(raw_ostream &OS) const;
140 };
141
142 /// The result of a query. It either indicates a final answer of Legal or
143 /// Unsupported or describes an action that must be taken to make an operation
144 /// more legal.
145 struct LegalizeActionStep {
146 /// The action to take or the final answer.
147 LegalizeAction Action;
148 /// If describing an action, the type index to change. Otherwise zero.
149 unsigned TypeIdx;
150 /// If describing an action, the new type for TypeIdx. Otherwise LLT{}.
151 LLT NewType;
152
LegalizeActionStepLegalizeActionStep153 LegalizeActionStep(LegalizeAction Action, unsigned TypeIdx,
154 const LLT &NewType)
155 : Action(Action), TypeIdx(TypeIdx), NewType(NewType) {}
156
157 bool operator==(const LegalizeActionStep &RHS) const {
158 return std::tie(Action, TypeIdx, NewType) ==
159 std::tie(RHS.Action, RHS.TypeIdx, RHS.NewType);
160 }
161 };
162
163 using LegalityPredicate = std::function<bool (const LegalityQuery &)>;
164 using LegalizeMutation =
165 std::function<std::pair<unsigned, LLT>(const LegalityQuery &)>;
166
167 namespace LegalityPredicates {
168 struct TypePairAndMemSize {
169 LLT Type0;
170 LLT Type1;
171 uint64_t MemSize;
172
173 bool operator==(const TypePairAndMemSize &Other) const {
174 return Type0 == Other.Type0 && Type1 == Other.Type1 &&
175 MemSize == Other.MemSize;
176 }
177 };
178
179 /// True iff P0 and P1 are true.
180 template<typename Predicate>
all(Predicate P0,Predicate P1)181 Predicate all(Predicate P0, Predicate P1) {
182 return [=](const LegalityQuery &Query) {
183 return P0(Query) && P1(Query);
184 };
185 }
186 /// True iff all given predicates are true.
187 template<typename Predicate, typename... Args>
all(Predicate P0,Predicate P1,Args...args)188 Predicate all(Predicate P0, Predicate P1, Args... args) {
189 return all(all(P0, P1), args...);
190 }
191 /// True iff the given type index is the specified types.
192 LegalityPredicate typeIs(unsigned TypeIdx, LLT TypesInit);
193 /// True iff the given type index is one of the specified types.
194 LegalityPredicate typeInSet(unsigned TypeIdx,
195 std::initializer_list<LLT> TypesInit);
196 /// True iff the given types for the given pair of type indexes is one of the
197 /// specified type pairs.
198 LegalityPredicate
199 typePairInSet(unsigned TypeIdx0, unsigned TypeIdx1,
200 std::initializer_list<std::pair<LLT, LLT>> TypesInit);
201 /// True iff the given types for the given pair of type indexes is one of the
202 /// specified type pairs.
203 LegalityPredicate typePairAndMemSizeInSet(
204 unsigned TypeIdx0, unsigned TypeIdx1, unsigned MMOIdx,
205 std::initializer_list<TypePairAndMemSize> TypesAndMemSizeInit);
206 /// True iff the specified type index is a scalar.
207 LegalityPredicate isScalar(unsigned TypeIdx);
208 /// True iff the specified type index is a scalar that's narrower than the given
209 /// size.
210 LegalityPredicate narrowerThan(unsigned TypeIdx, unsigned Size);
211 /// True iff the specified type index is a scalar that's wider than the given
212 /// size.
213 LegalityPredicate widerThan(unsigned TypeIdx, unsigned Size);
214 /// True iff the specified type index is a scalar whose size is not a power of
215 /// 2.
216 LegalityPredicate sizeNotPow2(unsigned TypeIdx);
217 /// True iff the specified MMO index has a size that is not a power of 2
218 LegalityPredicate memSizeInBytesNotPow2(unsigned MMOIdx);
219 /// True iff the specified type index is a vector whose element count is not a
220 /// power of 2.
221 LegalityPredicate numElementsNotPow2(unsigned TypeIdx);
222 /// True iff the specified MMO index has at an atomic ordering of at Ordering or
223 /// stronger.
224 LegalityPredicate atomicOrderingAtLeastOrStrongerThan(unsigned MMOIdx,
225 AtomicOrdering Ordering);
226 } // end namespace LegalityPredicates
227
228 namespace LegalizeMutations {
229 /// Select this specific type for the given type index.
230 LegalizeMutation changeTo(unsigned TypeIdx, LLT Ty);
231 /// Keep the same type as the given type index.
232 LegalizeMutation changeTo(unsigned TypeIdx, unsigned FromTypeIdx);
233 /// Widen the type for the given type index to the next power of 2.
234 LegalizeMutation widenScalarToNextPow2(unsigned TypeIdx, unsigned Min = 0);
235 /// Add more elements to the type for the given type index to the next power of
236 /// 2.
237 LegalizeMutation moreElementsToNextPow2(unsigned TypeIdx, unsigned Min = 0);
238 } // end namespace LegalizeMutations
239
240 /// A single rule in a legalizer info ruleset.
241 /// The specified action is chosen when the predicate is true. Where appropriate
242 /// for the action (e.g. for WidenScalar) the new type is selected using the
243 /// given mutator.
244 class LegalizeRule {
245 LegalityPredicate Predicate;
246 LegalizeAction Action;
247 LegalizeMutation Mutation;
248
249 public:
250 LegalizeRule(LegalityPredicate Predicate, LegalizeAction Action,
251 LegalizeMutation Mutation = nullptr)
Predicate(Predicate)252 : Predicate(Predicate), Action(Action), Mutation(Mutation) {}
253
254 /// Test whether the LegalityQuery matches.
match(const LegalityQuery & Query)255 bool match(const LegalityQuery &Query) const {
256 return Predicate(Query);
257 }
258
getAction()259 LegalizeAction getAction() const { return Action; }
260
261 /// Determine the change to make.
determineMutation(const LegalityQuery & Query)262 std::pair<unsigned, LLT> determineMutation(const LegalityQuery &Query) const {
263 if (Mutation)
264 return Mutation(Query);
265 return std::make_pair(0, LLT{});
266 }
267 };
268
269 class LegalizeRuleSet {
270 /// When non-zero, the opcode we are an alias of
271 unsigned AliasOf;
272 /// If true, there is another opcode that aliases this one
273 bool IsAliasedByAnother;
274 SmallVector<LegalizeRule, 2> Rules;
275
276 #ifndef NDEBUG
277 /// If bit I is set, this rule set contains a rule that may handle (predicate
278 /// or perform an action upon (or both)) the type index I. The uncertainty
279 /// comes from free-form rules executing user-provided lambda functions. We
280 /// conservatively assume such rules do the right thing and cover all type
281 /// indices. The bitset is intentionally 1 bit wider than it absolutely needs
282 /// to be to distinguish such cases from the cases where all type indices are
283 /// individually handled.
284 SmallBitVector TypeIdxsCovered{MCOI::OPERAND_LAST_GENERIC -
285 MCOI::OPERAND_FIRST_GENERIC + 2};
286 #endif
287
typeIdx(unsigned TypeIdx)288 unsigned typeIdx(unsigned TypeIdx) {
289 assert(TypeIdx <=
290 (MCOI::OPERAND_LAST_GENERIC - MCOI::OPERAND_FIRST_GENERIC) &&
291 "Type Index is out of bounds");
292 #ifndef NDEBUG
293 TypeIdxsCovered.set(TypeIdx);
294 #endif
295 return TypeIdx;
296 }
markAllTypeIdxsAsCovered()297 void markAllTypeIdxsAsCovered() {
298 #ifndef NDEBUG
299 TypeIdxsCovered.set();
300 #endif
301 }
302
add(const LegalizeRule & Rule)303 void add(const LegalizeRule &Rule) {
304 assert(AliasOf == 0 &&
305 "RuleSet is aliased, change the representative opcode instead");
306 Rules.push_back(Rule);
307 }
308
always(const LegalityQuery &)309 static bool always(const LegalityQuery &) { return true; }
310
311 /// Use the given action when the predicate is true.
312 /// Action should not be an action that requires mutation.
actionIf(LegalizeAction Action,LegalityPredicate Predicate)313 LegalizeRuleSet &actionIf(LegalizeAction Action,
314 LegalityPredicate Predicate) {
315 add({Predicate, Action});
316 return *this;
317 }
318 /// Use the given action when the predicate is true.
319 /// Action should be an action that requires mutation.
actionIf(LegalizeAction Action,LegalityPredicate Predicate,LegalizeMutation Mutation)320 LegalizeRuleSet &actionIf(LegalizeAction Action, LegalityPredicate Predicate,
321 LegalizeMutation Mutation) {
322 add({Predicate, Action, Mutation});
323 return *this;
324 }
325 /// Use the given action when type index 0 is any type in the given list.
326 /// Action should not be an action that requires mutation.
actionFor(LegalizeAction Action,std::initializer_list<LLT> Types)327 LegalizeRuleSet &actionFor(LegalizeAction Action,
328 std::initializer_list<LLT> Types) {
329 using namespace LegalityPredicates;
330 return actionIf(Action, typeInSet(typeIdx(0), Types));
331 }
332 /// Use the given action when type index 0 is any type in the given list.
333 /// Action should be an action that requires mutation.
actionFor(LegalizeAction Action,std::initializer_list<LLT> Types,LegalizeMutation Mutation)334 LegalizeRuleSet &actionFor(LegalizeAction Action,
335 std::initializer_list<LLT> Types,
336 LegalizeMutation Mutation) {
337 using namespace LegalityPredicates;
338 return actionIf(Action, typeInSet(typeIdx(0), Types), Mutation);
339 }
340 /// Use the given action when type indexes 0 and 1 is any type pair in the
341 /// given list.
342 /// Action should not be an action that requires mutation.
actionFor(LegalizeAction Action,std::initializer_list<std::pair<LLT,LLT>> Types)343 LegalizeRuleSet &actionFor(LegalizeAction Action,
344 std::initializer_list<std::pair<LLT, LLT>> Types) {
345 using namespace LegalityPredicates;
346 return actionIf(Action, typePairInSet(typeIdx(0), typeIdx(1), Types));
347 }
348 /// Use the given action when type indexes 0 and 1 is any type pair in the
349 /// given list.
350 /// Action should be an action that requires mutation.
actionFor(LegalizeAction Action,std::initializer_list<std::pair<LLT,LLT>> Types,LegalizeMutation Mutation)351 LegalizeRuleSet &actionFor(LegalizeAction Action,
352 std::initializer_list<std::pair<LLT, LLT>> Types,
353 LegalizeMutation Mutation) {
354 using namespace LegalityPredicates;
355 return actionIf(Action, typePairInSet(typeIdx(0), typeIdx(1), Types),
356 Mutation);
357 }
358 /// Use the given action when type indexes 0 and 1 are both in the given list.
359 /// That is, the type pair is in the cartesian product of the list.
360 /// Action should not be an action that requires mutation.
actionForCartesianProduct(LegalizeAction Action,std::initializer_list<LLT> Types)361 LegalizeRuleSet &actionForCartesianProduct(LegalizeAction Action,
362 std::initializer_list<LLT> Types) {
363 using namespace LegalityPredicates;
364 return actionIf(Action, all(typeInSet(typeIdx(0), Types),
365 typeInSet(typeIdx(1), Types)));
366 }
367 /// Use the given action when type indexes 0 and 1 are both in their
368 /// respective lists.
369 /// That is, the type pair is in the cartesian product of the lists
370 /// Action should not be an action that requires mutation.
371 LegalizeRuleSet &
actionForCartesianProduct(LegalizeAction Action,std::initializer_list<LLT> Types0,std::initializer_list<LLT> Types1)372 actionForCartesianProduct(LegalizeAction Action,
373 std::initializer_list<LLT> Types0,
374 std::initializer_list<LLT> Types1) {
375 using namespace LegalityPredicates;
376 return actionIf(Action, all(typeInSet(typeIdx(0), Types0),
377 typeInSet(typeIdx(1), Types1)));
378 }
379 /// Use the given action when type indexes 0, 1, and 2 are all in their
380 /// respective lists.
381 /// That is, the type triple is in the cartesian product of the lists
382 /// Action should not be an action that requires mutation.
actionForCartesianProduct(LegalizeAction Action,std::initializer_list<LLT> Types0,std::initializer_list<LLT> Types1,std::initializer_list<LLT> Types2)383 LegalizeRuleSet &actionForCartesianProduct(
384 LegalizeAction Action, std::initializer_list<LLT> Types0,
385 std::initializer_list<LLT> Types1, std::initializer_list<LLT> Types2) {
386 using namespace LegalityPredicates;
387 return actionIf(Action, all(typeInSet(typeIdx(0), Types0),
388 all(typeInSet(typeIdx(1), Types1),
389 typeInSet(typeIdx(2), Types2))));
390 }
391
392 public:
LegalizeRuleSet()393 LegalizeRuleSet() : AliasOf(0), IsAliasedByAnother(false), Rules() {}
394
isAliasedByAnother()395 bool isAliasedByAnother() { return IsAliasedByAnother; }
setIsAliasedByAnother()396 void setIsAliasedByAnother() { IsAliasedByAnother = true; }
aliasTo(unsigned Opcode)397 void aliasTo(unsigned Opcode) {
398 assert((AliasOf == 0 || AliasOf == Opcode) &&
399 "Opcode is already aliased to another opcode");
400 assert(Rules.empty() && "Aliasing will discard rules");
401 AliasOf = Opcode;
402 }
getAlias()403 unsigned getAlias() const { return AliasOf; }
404
405 /// The instruction is legal if predicate is true.
legalIf(LegalityPredicate Predicate)406 LegalizeRuleSet &legalIf(LegalityPredicate Predicate) {
407 // We have no choice but conservatively assume that the free-form
408 // user-provided Predicate properly handles all type indices:
409 markAllTypeIdxsAsCovered();
410 return actionIf(LegalizeAction::Legal, Predicate);
411 }
412 /// The instruction is legal when type index 0 is any type in the given list.
legalFor(std::initializer_list<LLT> Types)413 LegalizeRuleSet &legalFor(std::initializer_list<LLT> Types) {
414 return actionFor(LegalizeAction::Legal, Types);
415 }
416 /// The instruction is legal when type indexes 0 and 1 is any type pair in the
417 /// given list.
legalFor(std::initializer_list<std::pair<LLT,LLT>> Types)418 LegalizeRuleSet &legalFor(std::initializer_list<std::pair<LLT, LLT>> Types) {
419 return actionFor(LegalizeAction::Legal, Types);
420 }
421 /// The instruction is legal when type indexes 0 and 1 along with the memory
422 /// size is any type and size tuple in the given list.
legalForTypesWithMemSize(std::initializer_list<LegalityPredicates::TypePairAndMemSize> TypesAndMemSize)423 LegalizeRuleSet &legalForTypesWithMemSize(
424 std::initializer_list<LegalityPredicates::TypePairAndMemSize>
425 TypesAndMemSize) {
426 return actionIf(LegalizeAction::Legal,
427 LegalityPredicates::typePairAndMemSizeInSet(
428 typeIdx(0), typeIdx(1), /*MMOIdx*/ 0, TypesAndMemSize));
429 }
430 /// The instruction is legal when type indexes 0 and 1 are both in the given
431 /// list. That is, the type pair is in the cartesian product of the list.
legalForCartesianProduct(std::initializer_list<LLT> Types)432 LegalizeRuleSet &legalForCartesianProduct(std::initializer_list<LLT> Types) {
433 return actionForCartesianProduct(LegalizeAction::Legal, Types);
434 }
435 /// The instruction is legal when type indexes 0 and 1 are both their
436 /// respective lists.
legalForCartesianProduct(std::initializer_list<LLT> Types0,std::initializer_list<LLT> Types1)437 LegalizeRuleSet &legalForCartesianProduct(std::initializer_list<LLT> Types0,
438 std::initializer_list<LLT> Types1) {
439 return actionForCartesianProduct(LegalizeAction::Legal, Types0, Types1);
440 }
441
442 /// The instruction is lowered.
lower()443 LegalizeRuleSet &lower() {
444 using namespace LegalizeMutations;
445 // We have no choice but conservatively assume that predicate-less lowering
446 // properly handles all type indices by design:
447 markAllTypeIdxsAsCovered();
448 return actionIf(LegalizeAction::Lower, always);
449 }
450 /// The instruction is lowered if predicate is true. Keep type index 0 as the
451 /// same type.
lowerIf(LegalityPredicate Predicate)452 LegalizeRuleSet &lowerIf(LegalityPredicate Predicate) {
453 using namespace LegalizeMutations;
454 // We have no choice but conservatively assume that lowering with a
455 // free-form user provided Predicate properly handles all type indices:
456 markAllTypeIdxsAsCovered();
457 return actionIf(LegalizeAction::Lower, Predicate);
458 }
459 /// The instruction is lowered if predicate is true.
lowerIf(LegalityPredicate Predicate,LegalizeMutation Mutation)460 LegalizeRuleSet &lowerIf(LegalityPredicate Predicate,
461 LegalizeMutation Mutation) {
462 // We have no choice but conservatively assume that lowering with a
463 // free-form user provided Predicate properly handles all type indices:
464 markAllTypeIdxsAsCovered();
465 return actionIf(LegalizeAction::Lower, Predicate, Mutation);
466 }
467 /// The instruction is lowered when type index 0 is any type in the given
468 /// list. Keep type index 0 as the same type.
lowerFor(std::initializer_list<LLT> Types)469 LegalizeRuleSet &lowerFor(std::initializer_list<LLT> Types) {
470 return actionFor(LegalizeAction::Lower, Types,
471 LegalizeMutations::changeTo(0, 0));
472 }
473 /// The instruction is lowered when type index 0 is any type in the given
474 /// list.
lowerFor(std::initializer_list<LLT> Types,LegalizeMutation Mutation)475 LegalizeRuleSet &lowerFor(std::initializer_list<LLT> Types,
476 LegalizeMutation Mutation) {
477 return actionFor(LegalizeAction::Lower, Types, Mutation);
478 }
479 /// The instruction is lowered when type indexes 0 and 1 is any type pair in
480 /// the given list. Keep type index 0 as the same type.
lowerFor(std::initializer_list<std::pair<LLT,LLT>> Types)481 LegalizeRuleSet &lowerFor(std::initializer_list<std::pair<LLT, LLT>> Types) {
482 return actionFor(LegalizeAction::Lower, Types,
483 LegalizeMutations::changeTo(0, 0));
484 }
485 /// The instruction is lowered when type indexes 0 and 1 is any type pair in
486 /// the given list.
lowerFor(std::initializer_list<std::pair<LLT,LLT>> Types,LegalizeMutation Mutation)487 LegalizeRuleSet &lowerFor(std::initializer_list<std::pair<LLT, LLT>> Types,
488 LegalizeMutation Mutation) {
489 return actionFor(LegalizeAction::Lower, Types, Mutation);
490 }
491 /// The instruction is lowered when type indexes 0 and 1 are both in their
492 /// respective lists.
lowerForCartesianProduct(std::initializer_list<LLT> Types0,std::initializer_list<LLT> Types1)493 LegalizeRuleSet &lowerForCartesianProduct(std::initializer_list<LLT> Types0,
494 std::initializer_list<LLT> Types1) {
495 using namespace LegalityPredicates;
496 return actionForCartesianProduct(LegalizeAction::Lower, Types0, Types1);
497 }
498 /// The instruction is lowered when when type indexes 0, 1, and 2 are all in
499 /// their respective lists.
lowerForCartesianProduct(std::initializer_list<LLT> Types0,std::initializer_list<LLT> Types1,std::initializer_list<LLT> Types2)500 LegalizeRuleSet &lowerForCartesianProduct(std::initializer_list<LLT> Types0,
501 std::initializer_list<LLT> Types1,
502 std::initializer_list<LLT> Types2) {
503 using namespace LegalityPredicates;
504 return actionForCartesianProduct(LegalizeAction::Lower, Types0, Types1,
505 Types2);
506 }
507
508 /// Like legalIf, but for the Libcall action.
libcallIf(LegalityPredicate Predicate)509 LegalizeRuleSet &libcallIf(LegalityPredicate Predicate) {
510 // We have no choice but conservatively assume that a libcall with a
511 // free-form user provided Predicate properly handles all type indices:
512 markAllTypeIdxsAsCovered();
513 return actionIf(LegalizeAction::Libcall, Predicate);
514 }
libcallFor(std::initializer_list<LLT> Types)515 LegalizeRuleSet &libcallFor(std::initializer_list<LLT> Types) {
516 return actionFor(LegalizeAction::Libcall, Types);
517 }
518 LegalizeRuleSet &
libcallFor(std::initializer_list<std::pair<LLT,LLT>> Types)519 libcallFor(std::initializer_list<std::pair<LLT, LLT>> Types) {
520 return actionFor(LegalizeAction::Libcall, Types);
521 }
522 LegalizeRuleSet &
libcallForCartesianProduct(std::initializer_list<LLT> Types)523 libcallForCartesianProduct(std::initializer_list<LLT> Types) {
524 return actionForCartesianProduct(LegalizeAction::Libcall, Types);
525 }
526 LegalizeRuleSet &
libcallForCartesianProduct(std::initializer_list<LLT> Types0,std::initializer_list<LLT> Types1)527 libcallForCartesianProduct(std::initializer_list<LLT> Types0,
528 std::initializer_list<LLT> Types1) {
529 return actionForCartesianProduct(LegalizeAction::Libcall, Types0, Types1);
530 }
531
532 /// Widen the scalar to the one selected by the mutation if the predicate is
533 /// true.
widenScalarIf(LegalityPredicate Predicate,LegalizeMutation Mutation)534 LegalizeRuleSet &widenScalarIf(LegalityPredicate Predicate,
535 LegalizeMutation Mutation) {
536 // We have no choice but conservatively assume that an action with a
537 // free-form user provided Predicate properly handles all type indices:
538 markAllTypeIdxsAsCovered();
539 return actionIf(LegalizeAction::WidenScalar, Predicate, Mutation);
540 }
541 /// Narrow the scalar to the one selected by the mutation if the predicate is
542 /// true.
narrowScalarIf(LegalityPredicate Predicate,LegalizeMutation Mutation)543 LegalizeRuleSet &narrowScalarIf(LegalityPredicate Predicate,
544 LegalizeMutation Mutation) {
545 // We have no choice but conservatively assume that an action with a
546 // free-form user provided Predicate properly handles all type indices:
547 markAllTypeIdxsAsCovered();
548 return actionIf(LegalizeAction::NarrowScalar, Predicate, Mutation);
549 }
550
551 /// Add more elements to reach the type selected by the mutation if the
552 /// predicate is true.
moreElementsIf(LegalityPredicate Predicate,LegalizeMutation Mutation)553 LegalizeRuleSet &moreElementsIf(LegalityPredicate Predicate,
554 LegalizeMutation Mutation) {
555 // We have no choice but conservatively assume that an action with a
556 // free-form user provided Predicate properly handles all type indices:
557 markAllTypeIdxsAsCovered();
558 return actionIf(LegalizeAction::MoreElements, Predicate, Mutation);
559 }
560 /// Remove elements to reach the type selected by the mutation if the
561 /// predicate is true.
fewerElementsIf(LegalityPredicate Predicate,LegalizeMutation Mutation)562 LegalizeRuleSet &fewerElementsIf(LegalityPredicate Predicate,
563 LegalizeMutation Mutation) {
564 // We have no choice but conservatively assume that an action with a
565 // free-form user provided Predicate properly handles all type indices:
566 markAllTypeIdxsAsCovered();
567 return actionIf(LegalizeAction::FewerElements, Predicate, Mutation);
568 }
569
570 /// The instruction is unsupported.
unsupported()571 LegalizeRuleSet &unsupported() {
572 return actionIf(LegalizeAction::Unsupported, always);
573 }
unsupportedIf(LegalityPredicate Predicate)574 LegalizeRuleSet &unsupportedIf(LegalityPredicate Predicate) {
575 return actionIf(LegalizeAction::Unsupported, Predicate);
576 }
unsupportedIfMemSizeNotPow2()577 LegalizeRuleSet &unsupportedIfMemSizeNotPow2() {
578 return actionIf(LegalizeAction::Unsupported,
579 LegalityPredicates::memSizeInBytesNotPow2(0));
580 }
581
customIf(LegalityPredicate Predicate)582 LegalizeRuleSet &customIf(LegalityPredicate Predicate) {
583 // We have no choice but conservatively assume that a custom action with a
584 // free-form user provided Predicate properly handles all type indices:
585 markAllTypeIdxsAsCovered();
586 return actionIf(LegalizeAction::Custom, Predicate);
587 }
customFor(std::initializer_list<LLT> Types)588 LegalizeRuleSet &customFor(std::initializer_list<LLT> Types) {
589 return actionFor(LegalizeAction::Custom, Types);
590 }
customForCartesianProduct(std::initializer_list<LLT> Types)591 LegalizeRuleSet &customForCartesianProduct(std::initializer_list<LLT> Types) {
592 return actionForCartesianProduct(LegalizeAction::Custom, Types);
593 }
594 LegalizeRuleSet &
customForCartesianProduct(std::initializer_list<LLT> Types0,std::initializer_list<LLT> Types1)595 customForCartesianProduct(std::initializer_list<LLT> Types0,
596 std::initializer_list<LLT> Types1) {
597 return actionForCartesianProduct(LegalizeAction::Custom, Types0, Types1);
598 }
599
600 /// Widen the scalar to the next power of two that is at least MinSize.
601 /// No effect if the type is not a scalar or is a power of two.
602 LegalizeRuleSet &widenScalarToNextPow2(unsigned TypeIdx,
603 unsigned MinSize = 0) {
604 using namespace LegalityPredicates;
605 return actionIf(LegalizeAction::WidenScalar, sizeNotPow2(typeIdx(TypeIdx)),
606 LegalizeMutations::widenScalarToNextPow2(TypeIdx, MinSize));
607 }
608
narrowScalar(unsigned TypeIdx,LegalizeMutation Mutation)609 LegalizeRuleSet &narrowScalar(unsigned TypeIdx, LegalizeMutation Mutation) {
610 using namespace LegalityPredicates;
611 return actionIf(LegalizeAction::NarrowScalar, isScalar(typeIdx(TypeIdx)),
612 Mutation);
613 }
614
615 /// Ensure the scalar is at least as wide as Ty.
minScalar(unsigned TypeIdx,const LLT & Ty)616 LegalizeRuleSet &minScalar(unsigned TypeIdx, const LLT &Ty) {
617 using namespace LegalityPredicates;
618 using namespace LegalizeMutations;
619 return actionIf(LegalizeAction::WidenScalar,
620 narrowerThan(TypeIdx, Ty.getSizeInBits()),
621 changeTo(typeIdx(TypeIdx), Ty));
622 }
623
624 /// Ensure the scalar is at most as wide as Ty.
maxScalar(unsigned TypeIdx,const LLT & Ty)625 LegalizeRuleSet &maxScalar(unsigned TypeIdx, const LLT &Ty) {
626 using namespace LegalityPredicates;
627 using namespace LegalizeMutations;
628 return actionIf(LegalizeAction::NarrowScalar,
629 widerThan(TypeIdx, Ty.getSizeInBits()),
630 changeTo(typeIdx(TypeIdx), Ty));
631 }
632
633 /// Conditionally limit the maximum size of the scalar.
634 /// For example, when the maximum size of one type depends on the size of
635 /// another such as extracting N bits from an M bit container.
maxScalarIf(LegalityPredicate Predicate,unsigned TypeIdx,const LLT & Ty)636 LegalizeRuleSet &maxScalarIf(LegalityPredicate Predicate, unsigned TypeIdx,
637 const LLT &Ty) {
638 using namespace LegalityPredicates;
639 using namespace LegalizeMutations;
640 return actionIf(LegalizeAction::NarrowScalar,
641 [=](const LegalityQuery &Query) {
642 return widerThan(TypeIdx, Ty.getSizeInBits()) &&
643 Predicate(Query);
644 },
645 changeTo(typeIdx(TypeIdx), Ty));
646 }
647
648 /// Limit the range of scalar sizes to MinTy and MaxTy.
clampScalar(unsigned TypeIdx,const LLT & MinTy,const LLT & MaxTy)649 LegalizeRuleSet &clampScalar(unsigned TypeIdx, const LLT &MinTy,
650 const LLT &MaxTy) {
651 assert(MinTy.isScalar() && MaxTy.isScalar() && "Expected scalar types");
652 return minScalar(TypeIdx, MinTy).maxScalar(TypeIdx, MaxTy);
653 }
654
655 /// Widen the scalar to match the size of another.
minScalarSameAs(unsigned TypeIdx,unsigned LargeTypeIdx)656 LegalizeRuleSet &minScalarSameAs(unsigned TypeIdx, unsigned LargeTypeIdx) {
657 typeIdx(TypeIdx);
658 return widenScalarIf(
659 [=](const LegalityQuery &Query) {
660 return Query.Types[LargeTypeIdx].getScalarSizeInBits() >
661 Query.Types[TypeIdx].getSizeInBits();
662 },
663 [=](const LegalityQuery &Query) {
664 return std::make_pair(TypeIdx,
665 Query.Types[LargeTypeIdx].getElementType());
666 });
667 }
668
669 /// Add more elements to the vector to reach the next power of two.
670 /// No effect if the type is not a vector or the element count is a power of
671 /// two.
moreElementsToNextPow2(unsigned TypeIdx)672 LegalizeRuleSet &moreElementsToNextPow2(unsigned TypeIdx) {
673 using namespace LegalityPredicates;
674 return actionIf(LegalizeAction::MoreElements,
675 numElementsNotPow2(typeIdx(TypeIdx)),
676 LegalizeMutations::moreElementsToNextPow2(TypeIdx));
677 }
678
679 /// Limit the number of elements in EltTy vectors to at least MinElements.
clampMinNumElements(unsigned TypeIdx,const LLT & EltTy,unsigned MinElements)680 LegalizeRuleSet &clampMinNumElements(unsigned TypeIdx, const LLT &EltTy,
681 unsigned MinElements) {
682 // Mark the type index as covered:
683 typeIdx(TypeIdx);
684 return actionIf(
685 LegalizeAction::MoreElements,
686 [=](const LegalityQuery &Query) {
687 LLT VecTy = Query.Types[TypeIdx];
688 return VecTy.isVector() && VecTy.getElementType() == EltTy &&
689 VecTy.getNumElements() < MinElements;
690 },
691 [=](const LegalityQuery &Query) {
692 LLT VecTy = Query.Types[TypeIdx];
693 return std::make_pair(
694 TypeIdx, LLT::vector(MinElements, VecTy.getScalarSizeInBits()));
695 });
696 }
697 /// Limit the number of elements in EltTy vectors to at most MaxElements.
clampMaxNumElements(unsigned TypeIdx,const LLT & EltTy,unsigned MaxElements)698 LegalizeRuleSet &clampMaxNumElements(unsigned TypeIdx, const LLT &EltTy,
699 unsigned MaxElements) {
700 // Mark the type index as covered:
701 typeIdx(TypeIdx);
702 return actionIf(
703 LegalizeAction::FewerElements,
704 [=](const LegalityQuery &Query) {
705 LLT VecTy = Query.Types[TypeIdx];
706 return VecTy.isVector() && VecTy.getElementType() == EltTy &&
707 VecTy.getNumElements() > MaxElements;
708 },
709 [=](const LegalityQuery &Query) {
710 LLT VecTy = Query.Types[TypeIdx];
711 if (MaxElements == 1)
712 return std::make_pair(TypeIdx, VecTy.getElementType());
713 return std::make_pair(
714 TypeIdx, LLT::vector(MaxElements, VecTy.getScalarSizeInBits()));
715 });
716 }
717 /// Limit the number of elements for the given vectors to at least MinTy's
718 /// number of elements and at most MaxTy's number of elements.
719 ///
720 /// No effect if the type is not a vector or does not have the same element
721 /// type as the constraints.
722 /// The element type of MinTy and MaxTy must match.
clampNumElements(unsigned TypeIdx,const LLT & MinTy,const LLT & MaxTy)723 LegalizeRuleSet &clampNumElements(unsigned TypeIdx, const LLT &MinTy,
724 const LLT &MaxTy) {
725 assert(MinTy.getElementType() == MaxTy.getElementType() &&
726 "Expected element types to agree");
727
728 const LLT &EltTy = MinTy.getElementType();
729 return clampMinNumElements(TypeIdx, EltTy, MinTy.getNumElements())
730 .clampMaxNumElements(TypeIdx, EltTy, MaxTy.getNumElements());
731 }
732
733 /// Fallback on the previous implementation. This should only be used while
734 /// porting a rule.
fallback()735 LegalizeRuleSet &fallback() {
736 add({always, LegalizeAction::UseLegacyRules});
737 return *this;
738 }
739
740 /// Check if there is no type index which is obviously not handled by the
741 /// LegalizeRuleSet in any way at all.
742 /// \pre Type indices of the opcode form a dense [0, \p NumTypeIdxs) set.
743 bool verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const;
744
745 /// Apply the ruleset to the given LegalityQuery.
746 LegalizeActionStep apply(const LegalityQuery &Query) const;
747 };
748
749 class LegalizerInfo {
750 public:
751 LegalizerInfo();
752 virtual ~LegalizerInfo() = default;
753
754 unsigned getOpcodeIdxForOpcode(unsigned Opcode) const;
755 unsigned getActionDefinitionsIdx(unsigned Opcode) const;
756
757 /// Compute any ancillary tables needed to quickly decide how an operation
758 /// should be handled. This must be called after all "set*Action"methods but
759 /// before any query is made or incorrect results may be returned.
760 void computeTables();
761
762 /// Perform simple self-diagnostic and assert if there is anything obviously
763 /// wrong with the actions set up.
764 void verify(const MCInstrInfo &MII) const;
765
needsLegalizingToDifferentSize(const LegalizeAction Action)766 static bool needsLegalizingToDifferentSize(const LegalizeAction Action) {
767 using namespace LegalizeActions;
768 switch (Action) {
769 case NarrowScalar:
770 case WidenScalar:
771 case FewerElements:
772 case MoreElements:
773 case Unsupported:
774 return true;
775 default:
776 return false;
777 }
778 }
779
780 using SizeAndAction = std::pair<uint16_t, LegalizeAction>;
781 using SizeAndActionsVec = std::vector<SizeAndAction>;
782 using SizeChangeStrategy =
783 std::function<SizeAndActionsVec(const SizeAndActionsVec &v)>;
784
785 /// More friendly way to set an action for common types that have an LLT
786 /// representation.
787 /// The LegalizeAction must be one for which NeedsLegalizingToDifferentSize
788 /// returns false.
setAction(const InstrAspect & Aspect,LegalizeAction Action)789 void setAction(const InstrAspect &Aspect, LegalizeAction Action) {
790 assert(!needsLegalizingToDifferentSize(Action));
791 TablesInitialized = false;
792 const unsigned OpcodeIdx = Aspect.Opcode - FirstOp;
793 if (SpecifiedActions[OpcodeIdx].size() <= Aspect.Idx)
794 SpecifiedActions[OpcodeIdx].resize(Aspect.Idx + 1);
795 SpecifiedActions[OpcodeIdx][Aspect.Idx][Aspect.Type] = Action;
796 }
797
798 /// The setAction calls record the non-size-changing legalization actions
799 /// to take on specificly-sized types. The SizeChangeStrategy defines what
800 /// to do when the size of the type needs to be changed to reach a legally
801 /// sized type (i.e., one that was defined through a setAction call).
802 /// e.g.
803 /// setAction ({G_ADD, 0, LLT::scalar(32)}, Legal);
804 /// setLegalizeScalarToDifferentSizeStrategy(
805 /// G_ADD, 0, widenToLargerTypesAndNarrowToLargest);
806 /// will end up defining getAction({G_ADD, 0, T}) to return the following
807 /// actions for different scalar types T:
808 /// LLT::scalar(1)..LLT::scalar(31): {WidenScalar, 0, LLT::scalar(32)}
809 /// LLT::scalar(32): {Legal, 0, LLT::scalar(32)}
810 /// LLT::scalar(33)..: {NarrowScalar, 0, LLT::scalar(32)}
811 ///
812 /// If no SizeChangeAction gets defined, through this function,
813 /// the default is unsupportedForDifferentSizes.
setLegalizeScalarToDifferentSizeStrategy(const unsigned Opcode,const unsigned TypeIdx,SizeChangeStrategy S)814 void setLegalizeScalarToDifferentSizeStrategy(const unsigned Opcode,
815 const unsigned TypeIdx,
816 SizeChangeStrategy S) {
817 const unsigned OpcodeIdx = Opcode - FirstOp;
818 if (ScalarSizeChangeStrategies[OpcodeIdx].size() <= TypeIdx)
819 ScalarSizeChangeStrategies[OpcodeIdx].resize(TypeIdx + 1);
820 ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] = S;
821 }
822
823 /// See also setLegalizeScalarToDifferentSizeStrategy.
824 /// This function allows to set the SizeChangeStrategy for vector elements.
setLegalizeVectorElementToDifferentSizeStrategy(const unsigned Opcode,const unsigned TypeIdx,SizeChangeStrategy S)825 void setLegalizeVectorElementToDifferentSizeStrategy(const unsigned Opcode,
826 const unsigned TypeIdx,
827 SizeChangeStrategy S) {
828 const unsigned OpcodeIdx = Opcode - FirstOp;
829 if (VectorElementSizeChangeStrategies[OpcodeIdx].size() <= TypeIdx)
830 VectorElementSizeChangeStrategies[OpcodeIdx].resize(TypeIdx + 1);
831 VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] = S;
832 }
833
834 /// A SizeChangeStrategy for the common case where legalization for a
835 /// particular operation consists of only supporting a specific set of type
836 /// sizes. E.g.
837 /// setAction ({G_DIV, 0, LLT::scalar(32)}, Legal);
838 /// setAction ({G_DIV, 0, LLT::scalar(64)}, Legal);
839 /// setLegalizeScalarToDifferentSizeStrategy(
840 /// G_DIV, 0, unsupportedForDifferentSizes);
841 /// will result in getAction({G_DIV, 0, T}) to return Legal for s32 and s64,
842 /// and Unsupported for all other scalar types T.
843 static SizeAndActionsVec
unsupportedForDifferentSizes(const SizeAndActionsVec & v)844 unsupportedForDifferentSizes(const SizeAndActionsVec &v) {
845 using namespace LegalizeActions;
846 return increaseToLargerTypesAndDecreaseToLargest(v, Unsupported,
847 Unsupported);
848 }
849
850 /// A SizeChangeStrategy for the common case where legalization for a
851 /// particular operation consists of widening the type to a large legal type,
852 /// unless there is no such type and then instead it should be narrowed to the
853 /// largest legal type.
854 static SizeAndActionsVec
widenToLargerTypesAndNarrowToLargest(const SizeAndActionsVec & v)855 widenToLargerTypesAndNarrowToLargest(const SizeAndActionsVec &v) {
856 using namespace LegalizeActions;
857 assert(v.size() > 0 &&
858 "At least one size that can be legalized towards is needed"
859 " for this SizeChangeStrategy");
860 return increaseToLargerTypesAndDecreaseToLargest(v, WidenScalar,
861 NarrowScalar);
862 }
863
864 static SizeAndActionsVec
widenToLargerTypesUnsupportedOtherwise(const SizeAndActionsVec & v)865 widenToLargerTypesUnsupportedOtherwise(const SizeAndActionsVec &v) {
866 using namespace LegalizeActions;
867 return increaseToLargerTypesAndDecreaseToLargest(v, WidenScalar,
868 Unsupported);
869 }
870
871 static SizeAndActionsVec
narrowToSmallerAndUnsupportedIfTooSmall(const SizeAndActionsVec & v)872 narrowToSmallerAndUnsupportedIfTooSmall(const SizeAndActionsVec &v) {
873 using namespace LegalizeActions;
874 return decreaseToSmallerTypesAndIncreaseToSmallest(v, NarrowScalar,
875 Unsupported);
876 }
877
878 static SizeAndActionsVec
narrowToSmallerAndWidenToSmallest(const SizeAndActionsVec & v)879 narrowToSmallerAndWidenToSmallest(const SizeAndActionsVec &v) {
880 using namespace LegalizeActions;
881 assert(v.size() > 0 &&
882 "At least one size that can be legalized towards is needed"
883 " for this SizeChangeStrategy");
884 return decreaseToSmallerTypesAndIncreaseToSmallest(v, NarrowScalar,
885 WidenScalar);
886 }
887
888 /// A SizeChangeStrategy for the common case where legalization for a
889 /// particular vector operation consists of having more elements in the
890 /// vector, to a type that is legal. Unless there is no such type and then
891 /// instead it should be legalized towards the widest vector that's still
892 /// legal. E.g.
893 /// setAction({G_ADD, LLT::vector(8, 8)}, Legal);
894 /// setAction({G_ADD, LLT::vector(16, 8)}, Legal);
895 /// setAction({G_ADD, LLT::vector(2, 32)}, Legal);
896 /// setAction({G_ADD, LLT::vector(4, 32)}, Legal);
897 /// setLegalizeVectorElementToDifferentSizeStrategy(
898 /// G_ADD, 0, moreToWiderTypesAndLessToWidest);
899 /// will result in the following getAction results:
900 /// * getAction({G_ADD, LLT::vector(8,8)}) returns
901 /// (Legal, vector(8,8)).
902 /// * getAction({G_ADD, LLT::vector(9,8)}) returns
903 /// (MoreElements, vector(16,8)).
904 /// * getAction({G_ADD, LLT::vector(8,32)}) returns
905 /// (FewerElements, vector(4,32)).
906 static SizeAndActionsVec
moreToWiderTypesAndLessToWidest(const SizeAndActionsVec & v)907 moreToWiderTypesAndLessToWidest(const SizeAndActionsVec &v) {
908 using namespace LegalizeActions;
909 return increaseToLargerTypesAndDecreaseToLargest(v, MoreElements,
910 FewerElements);
911 }
912
913 /// Helper function to implement many typical SizeChangeStrategy functions.
914 static SizeAndActionsVec
915 increaseToLargerTypesAndDecreaseToLargest(const SizeAndActionsVec &v,
916 LegalizeAction IncreaseAction,
917 LegalizeAction DecreaseAction);
918 /// Helper function to implement many typical SizeChangeStrategy functions.
919 static SizeAndActionsVec
920 decreaseToSmallerTypesAndIncreaseToSmallest(const SizeAndActionsVec &v,
921 LegalizeAction DecreaseAction,
922 LegalizeAction IncreaseAction);
923
924 /// Get the action definitions for the given opcode. Use this to run a
925 /// LegalityQuery through the definitions.
926 const LegalizeRuleSet &getActionDefinitions(unsigned Opcode) const;
927
928 /// Get the action definition builder for the given opcode. Use this to define
929 /// the action definitions.
930 ///
931 /// It is an error to request an opcode that has already been requested by the
932 /// multiple-opcode variant.
933 LegalizeRuleSet &getActionDefinitionsBuilder(unsigned Opcode);
934
935 /// Get the action definition builder for the given set of opcodes. Use this
936 /// to define the action definitions for multiple opcodes at once. The first
937 /// opcode given will be considered the representative opcode and will hold
938 /// the definitions whereas the other opcodes will be configured to refer to
939 /// the representative opcode. This lowers memory requirements and very
940 /// slightly improves performance.
941 ///
942 /// It would be very easy to introduce unexpected side-effects as a result of
943 /// this aliasing if it were permitted to request different but intersecting
944 /// sets of opcodes but that is difficult to keep track of. It is therefore an
945 /// error to request the same opcode twice using this API, to request an
946 /// opcode that already has definitions, or to use the single-opcode API on an
947 /// opcode that has already been requested by this API.
948 LegalizeRuleSet &
949 getActionDefinitionsBuilder(std::initializer_list<unsigned> Opcodes);
950 void aliasActionDefinitions(unsigned OpcodeTo, unsigned OpcodeFrom);
951
952 /// Determine what action should be taken to legalize the described
953 /// instruction. Requires computeTables to have been called.
954 ///
955 /// \returns a description of the next legalization step to perform.
956 LegalizeActionStep getAction(const LegalityQuery &Query) const;
957
958 /// Determine what action should be taken to legalize the given generic
959 /// instruction.
960 ///
961 /// \returns a description of the next legalization step to perform.
962 LegalizeActionStep getAction(const MachineInstr &MI,
963 const MachineRegisterInfo &MRI) const;
964
965 bool isLegal(const MachineInstr &MI, const MachineRegisterInfo &MRI) const;
966
967 virtual bool legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI,
968 MachineIRBuilder &MIRBuilder,
969 GISelChangeObserver &Observer) const;
970
971 private:
972 /// Determine what action should be taken to legalize the given generic
973 /// instruction opcode, type-index and type. Requires computeTables to have
974 /// been called.
975 ///
976 /// \returns a pair consisting of the kind of legalization that should be
977 /// performed and the destination type.
978 std::pair<LegalizeAction, LLT>
979 getAspectAction(const InstrAspect &Aspect) const;
980
981 /// The SizeAndActionsVec is a representation mapping between all natural
982 /// numbers and an Action. The natural number represents the bit size of
983 /// the InstrAspect. For example, for a target with native support for 32-bit
984 /// and 64-bit additions, you'd express that as:
985 /// setScalarAction(G_ADD, 0,
986 /// {{1, WidenScalar}, // bit sizes [ 1, 31[
987 /// {32, Legal}, // bit sizes [32, 33[
988 /// {33, WidenScalar}, // bit sizes [33, 64[
989 /// {64, Legal}, // bit sizes [64, 65[
990 /// {65, NarrowScalar} // bit sizes [65, +inf[
991 /// });
992 /// It may be that only 64-bit pointers are supported on your target:
993 /// setPointerAction(G_GEP, 0, LLT:pointer(1),
994 /// {{1, Unsupported}, // bit sizes [ 1, 63[
995 /// {64, Legal}, // bit sizes [64, 65[
996 /// {65, Unsupported}, // bit sizes [65, +inf[
997 /// });
setScalarAction(const unsigned Opcode,const unsigned TypeIndex,const SizeAndActionsVec & SizeAndActions)998 void setScalarAction(const unsigned Opcode, const unsigned TypeIndex,
999 const SizeAndActionsVec &SizeAndActions) {
1000 const unsigned OpcodeIdx = Opcode - FirstOp;
1001 SmallVector<SizeAndActionsVec, 1> &Actions = ScalarActions[OpcodeIdx];
1002 setActions(TypeIndex, Actions, SizeAndActions);
1003 }
setPointerAction(const unsigned Opcode,const unsigned TypeIndex,const unsigned AddressSpace,const SizeAndActionsVec & SizeAndActions)1004 void setPointerAction(const unsigned Opcode, const unsigned TypeIndex,
1005 const unsigned AddressSpace,
1006 const SizeAndActionsVec &SizeAndActions) {
1007 const unsigned OpcodeIdx = Opcode - FirstOp;
1008 if (AddrSpace2PointerActions[OpcodeIdx].find(AddressSpace) ==
1009 AddrSpace2PointerActions[OpcodeIdx].end())
1010 AddrSpace2PointerActions[OpcodeIdx][AddressSpace] = {{}};
1011 SmallVector<SizeAndActionsVec, 1> &Actions =
1012 AddrSpace2PointerActions[OpcodeIdx].find(AddressSpace)->second;
1013 setActions(TypeIndex, Actions, SizeAndActions);
1014 }
1015
1016 /// If an operation on a given vector type (say <M x iN>) isn't explicitly
1017 /// specified, we proceed in 2 stages. First we legalize the underlying scalar
1018 /// (so that there's at least one legal vector with that scalar), then we
1019 /// adjust the number of elements in the vector so that it is legal. The
1020 /// desired action in the first step is controlled by this function.
setScalarInVectorAction(const unsigned Opcode,const unsigned TypeIndex,const SizeAndActionsVec & SizeAndActions)1021 void setScalarInVectorAction(const unsigned Opcode, const unsigned TypeIndex,
1022 const SizeAndActionsVec &SizeAndActions) {
1023 unsigned OpcodeIdx = Opcode - FirstOp;
1024 SmallVector<SizeAndActionsVec, 1> &Actions =
1025 ScalarInVectorActions[OpcodeIdx];
1026 setActions(TypeIndex, Actions, SizeAndActions);
1027 }
1028
1029 /// See also setScalarInVectorAction.
1030 /// This function let's you specify the number of elements in a vector that
1031 /// are legal for a legal element size.
setVectorNumElementAction(const unsigned Opcode,const unsigned TypeIndex,const unsigned ElementSize,const SizeAndActionsVec & SizeAndActions)1032 void setVectorNumElementAction(const unsigned Opcode,
1033 const unsigned TypeIndex,
1034 const unsigned ElementSize,
1035 const SizeAndActionsVec &SizeAndActions) {
1036 const unsigned OpcodeIdx = Opcode - FirstOp;
1037 if (NumElements2Actions[OpcodeIdx].find(ElementSize) ==
1038 NumElements2Actions[OpcodeIdx].end())
1039 NumElements2Actions[OpcodeIdx][ElementSize] = {{}};
1040 SmallVector<SizeAndActionsVec, 1> &Actions =
1041 NumElements2Actions[OpcodeIdx].find(ElementSize)->second;
1042 setActions(TypeIndex, Actions, SizeAndActions);
1043 }
1044
1045 /// A partial SizeAndActionsVec potentially doesn't cover all bit sizes,
1046 /// i.e. it's OK if it doesn't start from size 1.
checkPartialSizeAndActionsVector(const SizeAndActionsVec & v)1047 static void checkPartialSizeAndActionsVector(const SizeAndActionsVec& v) {
1048 using namespace LegalizeActions;
1049 #ifndef NDEBUG
1050 // The sizes should be in increasing order
1051 int prev_size = -1;
1052 for(auto SizeAndAction: v) {
1053 assert(SizeAndAction.first > prev_size);
1054 prev_size = SizeAndAction.first;
1055 }
1056 // - for every Widen action, there should be a larger bitsize that
1057 // can be legalized towards (e.g. Legal, Lower, Libcall or Custom
1058 // action).
1059 // - for every Narrow action, there should be a smaller bitsize that
1060 // can be legalized towards.
1061 int SmallestNarrowIdx = -1;
1062 int LargestWidenIdx = -1;
1063 int SmallestLegalizableToSameSizeIdx = -1;
1064 int LargestLegalizableToSameSizeIdx = -1;
1065 for(size_t i=0; i<v.size(); ++i) {
1066 switch (v[i].second) {
1067 case FewerElements:
1068 case NarrowScalar:
1069 if (SmallestNarrowIdx == -1)
1070 SmallestNarrowIdx = i;
1071 break;
1072 case WidenScalar:
1073 case MoreElements:
1074 LargestWidenIdx = i;
1075 break;
1076 case Unsupported:
1077 break;
1078 default:
1079 if (SmallestLegalizableToSameSizeIdx == -1)
1080 SmallestLegalizableToSameSizeIdx = i;
1081 LargestLegalizableToSameSizeIdx = i;
1082 }
1083 }
1084 if (SmallestNarrowIdx != -1) {
1085 assert(SmallestLegalizableToSameSizeIdx != -1);
1086 assert(SmallestNarrowIdx > SmallestLegalizableToSameSizeIdx);
1087 }
1088 if (LargestWidenIdx != -1)
1089 assert(LargestWidenIdx < LargestLegalizableToSameSizeIdx);
1090 #endif
1091 }
1092
1093 /// A full SizeAndActionsVec must cover all bit sizes, i.e. must start with
1094 /// from size 1.
checkFullSizeAndActionsVector(const SizeAndActionsVec & v)1095 static void checkFullSizeAndActionsVector(const SizeAndActionsVec& v) {
1096 #ifndef NDEBUG
1097 // Data structure invariant: The first bit size must be size 1.
1098 assert(v.size() >= 1);
1099 assert(v[0].first == 1);
1100 checkPartialSizeAndActionsVector(v);
1101 #endif
1102 }
1103
1104 /// Sets actions for all bit sizes on a particular generic opcode, type
1105 /// index and scalar or pointer type.
setActions(unsigned TypeIndex,SmallVector<SizeAndActionsVec,1> & Actions,const SizeAndActionsVec & SizeAndActions)1106 void setActions(unsigned TypeIndex,
1107 SmallVector<SizeAndActionsVec, 1> &Actions,
1108 const SizeAndActionsVec &SizeAndActions) {
1109 checkFullSizeAndActionsVector(SizeAndActions);
1110 if (Actions.size() <= TypeIndex)
1111 Actions.resize(TypeIndex + 1);
1112 Actions[TypeIndex] = SizeAndActions;
1113 }
1114
1115 static SizeAndAction findAction(const SizeAndActionsVec &Vec,
1116 const uint32_t Size);
1117
1118 /// Returns the next action needed to get the scalar or pointer type closer
1119 /// to being legal
1120 /// E.g. findLegalAction({G_REM, 13}) should return
1121 /// (WidenScalar, 32). After that, findLegalAction({G_REM, 32}) will
1122 /// probably be called, which should return (Lower, 32).
1123 /// This is assuming the setScalarAction on G_REM was something like:
1124 /// setScalarAction(G_REM, 0,
1125 /// {{1, WidenScalar}, // bit sizes [ 1, 31[
1126 /// {32, Lower}, // bit sizes [32, 33[
1127 /// {33, NarrowScalar} // bit sizes [65, +inf[
1128 /// });
1129 std::pair<LegalizeAction, LLT>
1130 findScalarLegalAction(const InstrAspect &Aspect) const;
1131
1132 /// Returns the next action needed towards legalizing the vector type.
1133 std::pair<LegalizeAction, LLT>
1134 findVectorLegalAction(const InstrAspect &Aspect) const;
1135
1136 static const int FirstOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_START;
1137 static const int LastOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_END;
1138
1139 // Data structures used temporarily during construction of legality data:
1140 using TypeMap = DenseMap<LLT, LegalizeAction>;
1141 SmallVector<TypeMap, 1> SpecifiedActions[LastOp - FirstOp + 1];
1142 SmallVector<SizeChangeStrategy, 1>
1143 ScalarSizeChangeStrategies[LastOp - FirstOp + 1];
1144 SmallVector<SizeChangeStrategy, 1>
1145 VectorElementSizeChangeStrategies[LastOp - FirstOp + 1];
1146 bool TablesInitialized;
1147
1148 // Data structures used by getAction:
1149 SmallVector<SizeAndActionsVec, 1> ScalarActions[LastOp - FirstOp + 1];
1150 SmallVector<SizeAndActionsVec, 1> ScalarInVectorActions[LastOp - FirstOp + 1];
1151 std::unordered_map<uint16_t, SmallVector<SizeAndActionsVec, 1>>
1152 AddrSpace2PointerActions[LastOp - FirstOp + 1];
1153 std::unordered_map<uint16_t, SmallVector<SizeAndActionsVec, 1>>
1154 NumElements2Actions[LastOp - FirstOp + 1];
1155
1156 LegalizeRuleSet RulesForOpcode[LastOp - FirstOp + 1];
1157 };
1158
1159 #ifndef NDEBUG
1160 /// Checks that MIR is fully legal, returns an illegal instruction if it's not,
1161 /// nullptr otherwise
1162 const MachineInstr *machineFunctionIsIllegal(const MachineFunction &MF);
1163 #endif
1164
1165 } // end namespace llvm.
1166
1167 #endif // LLVM_CODEGEN_GLOBALISEL_LEGALIZERINFO_H
1168