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