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