• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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