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