LLVM  7.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"
22 #include "llvm/ADT/SmallVector.h"
25 #include <cassert>
26 #include <cstdint>
27 #include <tuple>
28 #include <unordered_map>
29 #include <utility>
30 
31 namespace llvm {
32 
33 class MachineInstr;
34 class MachineIRBuilder;
35 class MachineRegisterInfo;
36 
37 /// Legalization is decided based on an instruction's opcode, which type slot
38 /// we're considering, and what the existing type is. These aspects are gathered
39 /// together for convenience in the InstrAspect class.
40 struct InstrAspect {
41  unsigned Opcode;
42  unsigned Idx = 0;
44 
45  InstrAspect(unsigned Opcode, LLT Type) : Opcode(Opcode), Type(Type) {}
46  InstrAspect(unsigned Opcode, unsigned Idx, LLT Type)
47  : Opcode(Opcode), Idx(Idx), Type(Type) {}
48 
49  bool operator==(const InstrAspect &RHS) const {
50  return Opcode == RHS.Opcode && Idx == RHS.Idx && Type == RHS.Type;
51  }
52 };
53 
55 public:
56  enum LegalizeAction : std::uint8_t {
57  /// The operation is expected to be selectable directly by the target, and
58  /// no transformation is necessary.
60 
61  /// The operation should be synthesized from multiple instructions acting on
62  /// a narrower scalar base-type. For example a 64-bit add might be
63  /// implemented in terms of 32-bit add-with-carry.
65 
66  /// The operation should be implemented in terms of a wider scalar
67  /// base-type. For example a <2 x s8> add could be implemented as a <2
68  /// x s32> add (ignoring the high bits).
70 
71  /// The (vector) operation should be implemented by splitting it into
72  /// sub-vectors where the operation is legal. For example a <8 x s64> add
73  /// might be implemented as 4 separate <2 x s64> adds.
75 
76  /// The (vector) operation should be implemented by widening the input
77  /// vector and ignoring the lanes added by doing so. For example <2 x i8> is
78  /// rarely legal, but you might perform an <8 x i8> and then only look at
79  /// the first two results.
81 
82  /// The operation itself must be expressed in terms of simpler actions on
83  /// this target. E.g. a SREM replaced by an SDIV and subtraction.
85 
86  /// The operation should be implemented as a call to some kind of runtime
87  /// support library. For example this usually happens on machines that don't
88  /// support floating-point operations natively.
90 
91  /// The target wants to do something special with this combination of
92  /// operand and type. A callback will be issued when it is needed.
94 
95  /// This operation is completely unsupported on the target. A programming
96  /// error has occurred.
98 
99  /// Sentinel value for when no action was found in the specified table.
101  };
102 
103  LegalizerInfo();
104  virtual ~LegalizerInfo() = default;
105 
106  /// Compute any ancillary tables needed to quickly decide how an operation
107  /// should be handled. This must be called after all "set*Action"methods but
108  /// before any query is made or incorrect results may be returned.
109  void computeTables();
110 
111  static bool needsLegalizingToDifferentSize(const LegalizeAction Action) {
112  switch (Action) {
113  case NarrowScalar:
114  case WidenScalar:
115  case FewerElements:
116  case MoreElements:
117  case Unsupported:
118  return true;
119  default:
120  return false;
121  }
122  }
123 
124  using SizeAndAction = std::pair<uint16_t, LegalizeAction>;
125  using SizeAndActionsVec = std::vector<SizeAndAction>;
126  using SizeChangeStrategy =
127  std::function<SizeAndActionsVec(const SizeAndActionsVec &v)>;
128 
129  /// More friendly way to set an action for common types that have an LLT
130  /// representation.
131  /// The LegalizeAction must be one for which NeedsLegalizingToDifferentSize
132  /// returns false.
133  void setAction(const InstrAspect &Aspect, LegalizeAction Action) {
134  assert(!needsLegalizingToDifferentSize(Action));
135  TablesInitialized = false;
136  const unsigned OpcodeIdx = Aspect.Opcode - FirstOp;
137  if (SpecifiedActions[OpcodeIdx].size() <= Aspect.Idx)
138  SpecifiedActions[OpcodeIdx].resize(Aspect.Idx + 1);
139  SpecifiedActions[OpcodeIdx][Aspect.Idx][Aspect.Type] = Action;
140  }
141 
142  /// The setAction calls record the non-size-changing legalization actions
143  /// to take on specificly-sized types. The SizeChangeStrategy defines what
144  /// to do when the size of the type needs to be changed to reach a legally
145  /// sized type (i.e., one that was defined through a setAction call).
146  /// e.g.
147  /// setAction ({G_ADD, 0, LLT::scalar(32)}, Legal);
148  /// setLegalizeScalarToDifferentSizeStrategy(
149  /// G_ADD, 0, widenToLargerTypesAndNarrowToLargest);
150  /// will end up defining getAction({G_ADD, 0, T}) to return the following
151  /// actions for different scalar types T:
152  /// LLT::scalar(1)..LLT::scalar(31): {WidenScalar, 0, LLT::scalar(32)}
153  /// LLT::scalar(32): {Legal, 0, LLT::scalar(32)}
154  /// LLT::scalar(33)..: {NarrowScalar, 0, LLT::scalar(32)}
155  ///
156  /// If no SizeChangeAction gets defined, through this function,
157  /// the default is unsupportedForDifferentSizes.
159  const unsigned TypeIdx,
160  SizeChangeStrategy S) {
161  const unsigned OpcodeIdx = Opcode - FirstOp;
162  if (ScalarSizeChangeStrategies[OpcodeIdx].size() <= TypeIdx)
163  ScalarSizeChangeStrategies[OpcodeIdx].resize(TypeIdx + 1);
164  ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] = S;
165  }
166 
167  /// See also setLegalizeScalarToDifferentSizeStrategy.
168  /// This function allows to set the SizeChangeStrategy for vector elements.
170  const unsigned TypeIdx,
171  SizeChangeStrategy S) {
172  const unsigned OpcodeIdx = Opcode - FirstOp;
173  if (VectorElementSizeChangeStrategies[OpcodeIdx].size() <= TypeIdx)
174  VectorElementSizeChangeStrategies[OpcodeIdx].resize(TypeIdx + 1);
175  VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] = S;
176  }
177 
178  /// A SizeChangeStrategy for the common case where legalization for a
179  /// particular operation consists of only supporting a specific set of type
180  /// sizes. E.g.
181  /// setAction ({G_DIV, 0, LLT::scalar(32)}, Legal);
182  /// setAction ({G_DIV, 0, LLT::scalar(64)}, Legal);
183  /// setLegalizeScalarToDifferentSizeStrategy(
184  /// G_DIV, 0, unsupportedForDifferentSizes);
185  /// will result in getAction({G_DIV, 0, T}) to return Legal for s32 and s64,
186  /// and Unsupported for all other scalar types T.
187  static SizeAndActionsVec
189  return increaseToLargerTypesAndDecreaseToLargest(v, Unsupported,
190  Unsupported);
191  }
192 
193  /// A SizeChangeStrategy for the common case where legalization for a
194  /// particular operation consists of widening the type to a large legal type,
195  /// unless there is no such type and then instead it should be narrowed to the
196  /// largest legal type.
197  static SizeAndActionsVec
199  assert(v.size() > 0 &&
200  "At least one size that can be legalized towards is needed"
201  " for this SizeChangeStrategy");
202  return increaseToLargerTypesAndDecreaseToLargest(v, WidenScalar,
203  NarrowScalar);
204  }
205 
206  static SizeAndActionsVec
208  return increaseToLargerTypesAndDecreaseToLargest(v, WidenScalar,
209  Unsupported);
210  }
211 
212  static SizeAndActionsVec
214  return decreaseToSmallerTypesAndIncreaseToSmallest(v, NarrowScalar,
215  Unsupported);
216  }
217 
218  static SizeAndActionsVec
220  assert(v.size() > 0 &&
221  "At least one size that can be legalized towards is needed"
222  " for this SizeChangeStrategy");
223  return decreaseToSmallerTypesAndIncreaseToSmallest(v, NarrowScalar,
224  WidenScalar);
225  }
226 
227  /// A SizeChangeStrategy for the common case where legalization for a
228  /// particular vector operation consists of having more elements in the
229  /// vector, to a type that is legal. Unless there is no such type and then
230  /// instead it should be legalized towards the widest vector that's still
231  /// legal. E.g.
232  /// setAction({G_ADD, LLT::vector(8, 8)}, Legal);
233  /// setAction({G_ADD, LLT::vector(16, 8)}, Legal);
234  /// setAction({G_ADD, LLT::vector(2, 32)}, Legal);
235  /// setAction({G_ADD, LLT::vector(4, 32)}, Legal);
236  /// setLegalizeVectorElementToDifferentSizeStrategy(
237  /// G_ADD, 0, moreToWiderTypesAndLessToWidest);
238  /// will result in the following getAction results:
239  /// * getAction({G_ADD, LLT::vector(8,8)}) returns
240  /// (Legal, vector(8,8)).
241  /// * getAction({G_ADD, LLT::vector(9,8)}) returns
242  /// (MoreElements, vector(16,8)).
243  /// * getAction({G_ADD, LLT::vector(8,32)}) returns
244  /// (FewerElements, vector(4,32)).
245  static SizeAndActionsVec
247  return increaseToLargerTypesAndDecreaseToLargest(v, MoreElements,
248  FewerElements);
249  }
250 
251  /// Helper function to implement many typical SizeChangeStrategy functions.
252  static SizeAndActionsVec
253  increaseToLargerTypesAndDecreaseToLargest(const SizeAndActionsVec &v,
254  LegalizeAction IncreaseAction,
255  LegalizeAction DecreaseAction);
256  /// Helper function to implement many typical SizeChangeStrategy functions.
257  static SizeAndActionsVec
258  decreaseToSmallerTypesAndIncreaseToSmallest(const SizeAndActionsVec &v,
259  LegalizeAction DecreaseAction,
260  LegalizeAction IncreaseAction);
261 
262  /// Determine what action should be taken to legalize the given generic
263  /// instruction opcode, type-index and type. Requires computeTables to have
264  /// been called.
265  ///
266  /// \returns a pair consisting of the kind of legalization that should be
267  /// performed and the destination type.
268  std::pair<LegalizeAction, LLT> getAction(const InstrAspect &Aspect) const;
269 
270  /// Determine what action should be taken to legalize the given generic
271  /// instruction.
272  ///
273  /// \returns a tuple consisting of the LegalizeAction that should be
274  /// performed, the type-index it should be performed on and the destination
275  /// type.
276  std::tuple<LegalizeAction, unsigned, LLT>
277  getAction(const MachineInstr &MI, const MachineRegisterInfo &MRI) const;
278 
279  bool isLegal(const MachineInstr &MI, const MachineRegisterInfo &MRI) const;
280 
281  virtual bool legalizeCustom(MachineInstr &MI,
282  MachineRegisterInfo &MRI,
283  MachineIRBuilder &MIRBuilder) const;
284 
285 private:
286  /// The SizeAndActionsVec is a representation mapping between all natural
287  /// numbers and an Action. The natural number represents the bit size of
288  /// the InstrAspect. For example, for a target with native support for 32-bit
289  /// and 64-bit additions, you'd express that as:
290  /// setScalarAction(G_ADD, 0,
291  /// {{1, WidenScalar}, // bit sizes [ 1, 31[
292  /// {32, Legal}, // bit sizes [32, 33[
293  /// {33, WidenScalar}, // bit sizes [33, 64[
294  /// {64, Legal}, // bit sizes [64, 65[
295  /// {65, NarrowScalar} // bit sizes [65, +inf[
296  /// });
297  /// It may be that only 64-bit pointers are supported on your target:
298  /// setPointerAction(G_GEP, 0, LLT:pointer(1),
299  /// {{1, Unsupported}, // bit sizes [ 1, 63[
300  /// {64, Legal}, // bit sizes [64, 65[
301  /// {65, Unsupported}, // bit sizes [65, +inf[
302  /// });
303  void setScalarAction(const unsigned Opcode, const unsigned TypeIndex,
304  const SizeAndActionsVec &SizeAndActions) {
305  const unsigned OpcodeIdx = Opcode - FirstOp;
306  SmallVector<SizeAndActionsVec, 1> &Actions = ScalarActions[OpcodeIdx];
307  setActions(TypeIndex, Actions, SizeAndActions);
308  }
309  void setPointerAction(const unsigned Opcode, const unsigned TypeIndex,
310  const unsigned AddressSpace,
311  const SizeAndActionsVec &SizeAndActions) {
312  const unsigned OpcodeIdx = Opcode - FirstOp;
313  if (AddrSpace2PointerActions[OpcodeIdx].find(AddressSpace) ==
314  AddrSpace2PointerActions[OpcodeIdx].end())
315  AddrSpace2PointerActions[OpcodeIdx][AddressSpace] = {{}};
317  AddrSpace2PointerActions[OpcodeIdx].find(AddressSpace)->second;
318  setActions(TypeIndex, Actions, SizeAndActions);
319  }
320 
321  /// If an operation on a given vector type (say <M x iN>) isn't explicitly
322  /// specified, we proceed in 2 stages. First we legalize the underlying scalar
323  /// (so that there's at least one legal vector with that scalar), then we
324  /// adjust the number of elements in the vector so that it is legal. The
325  /// desired action in the first step is controlled by this function.
326  void setScalarInVectorAction(const unsigned Opcode, const unsigned TypeIndex,
327  const SizeAndActionsVec &SizeAndActions) {
328  unsigned OpcodeIdx = Opcode - FirstOp;
330  ScalarInVectorActions[OpcodeIdx];
331  setActions(TypeIndex, Actions, SizeAndActions);
332  }
333 
334  /// See also setScalarInVectorAction.
335  /// This function let's you specify the number of elements in a vector that
336  /// are legal for a legal element size.
337  void setVectorNumElementAction(const unsigned Opcode,
338  const unsigned TypeIndex,
339  const unsigned ElementSize,
340  const SizeAndActionsVec &SizeAndActions) {
341  const unsigned OpcodeIdx = Opcode - FirstOp;
342  if (NumElements2Actions[OpcodeIdx].find(ElementSize) ==
343  NumElements2Actions[OpcodeIdx].end())
344  NumElements2Actions[OpcodeIdx][ElementSize] = {{}};
346  NumElements2Actions[OpcodeIdx].find(ElementSize)->second;
347  setActions(TypeIndex, Actions, SizeAndActions);
348  }
349 
350  /// A partial SizeAndActionsVec potentially doesn't cover all bit sizes,
351  /// i.e. it's OK if it doesn't start from size 1.
352  static void checkPartialSizeAndActionsVector(const SizeAndActionsVec& v) {
353 #ifndef NDEBUG
354  // The sizes should be in increasing order
355  int prev_size = -1;
356  for(auto SizeAndAction: v) {
357  assert(SizeAndAction.first > prev_size);
358  prev_size = SizeAndAction.first;
359  }
360  // - for every Widen action, there should be a larger bitsize that
361  // can be legalized towards (e.g. Legal, Lower, Libcall or Custom
362  // action).
363  // - for every Narrow action, there should be a smaller bitsize that
364  // can be legalized towards.
365  int SmallestNarrowIdx = -1;
366  int LargestWidenIdx = -1;
367  int SmallestLegalizableToSameSizeIdx = -1;
368  int LargestLegalizableToSameSizeIdx = -1;
369  for(size_t i=0; i<v.size(); ++i) {
370  switch (v[i].second) {
371  case FewerElements:
372  case NarrowScalar:
373  if (SmallestNarrowIdx == -1)
374  SmallestNarrowIdx = i;
375  break;
376  case WidenScalar:
377  case MoreElements:
378  LargestWidenIdx = i;
379  break;
380  case Unsupported:
381  break;
382  default:
383  if (SmallestLegalizableToSameSizeIdx == -1)
384  SmallestLegalizableToSameSizeIdx = i;
385  LargestLegalizableToSameSizeIdx = i;
386  }
387  }
388  if (SmallestNarrowIdx != -1) {
389  assert(SmallestLegalizableToSameSizeIdx != -1);
390  assert(SmallestNarrowIdx > SmallestLegalizableToSameSizeIdx);
391  }
392  if (LargestWidenIdx != -1)
393  assert(LargestWidenIdx < LargestLegalizableToSameSizeIdx);
394 #endif
395  }
396 
397  /// A full SizeAndActionsVec must cover all bit sizes, i.e. must start with
398  /// from size 1.
399  static void checkFullSizeAndActionsVector(const SizeAndActionsVec& v) {
400 #ifndef NDEBUG
401  // Data structure invariant: The first bit size must be size 1.
402  assert(v.size() >= 1);
403  assert(v[0].first == 1);
404  checkPartialSizeAndActionsVector(v);
405 #endif
406  }
407 
408  /// Sets actions for all bit sizes on a particular generic opcode, type
409  /// index and scalar or pointer type.
410  void setActions(unsigned TypeIndex,
412  const SizeAndActionsVec &SizeAndActions) {
413  checkFullSizeAndActionsVector(SizeAndActions);
414  if (Actions.size() <= TypeIndex)
415  Actions.resize(TypeIndex + 1);
416  Actions[TypeIndex] = SizeAndActions;
417  }
418 
419  static SizeAndAction findAction(const SizeAndActionsVec &Vec,
420  const uint32_t Size);
421 
422  /// Returns the next action needed to get the scalar or pointer type closer
423  /// to being legal
424  /// E.g. findLegalAction({G_REM, 13}) should return
425  /// (WidenScalar, 32). After that, findLegalAction({G_REM, 32}) will
426  /// probably be called, which should return (Lower, 32).
427  /// This is assuming the setScalarAction on G_REM was something like:
428  /// setScalarAction(G_REM, 0,
429  /// {{1, WidenScalar}, // bit sizes [ 1, 31[
430  /// {32, Lower}, // bit sizes [32, 33[
431  /// {33, NarrowScalar} // bit sizes [65, +inf[
432  /// });
433  std::pair<LegalizeAction, LLT>
434  findScalarLegalAction(const InstrAspect &Aspect) const;
435 
436  /// Returns the next action needed towards legalizing the vector type.
437  std::pair<LegalizeAction, LLT>
438  findVectorLegalAction(const InstrAspect &Aspect) const;
439 
440  static const int FirstOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_START;
441  static const int LastOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_END;
442 
443  // Data structures used temporarily during construction of legality data:
445  SmallVector<TypeMap, 1> SpecifiedActions[LastOp - FirstOp + 1];
447  ScalarSizeChangeStrategies[LastOp - FirstOp + 1];
449  VectorElementSizeChangeStrategies[LastOp - FirstOp + 1];
450  bool TablesInitialized;
451 
452  // Data structures used by getAction:
453  SmallVector<SizeAndActionsVec, 1> ScalarActions[LastOp - FirstOp + 1];
454  SmallVector<SizeAndActionsVec, 1> ScalarInVectorActions[LastOp - FirstOp + 1];
455  std::unordered_map<uint16_t, SmallVector<SizeAndActionsVec, 1>>
456  AddrSpace2PointerActions[LastOp - FirstOp + 1];
457  std::unordered_map<uint16_t, SmallVector<SizeAndActionsVec, 1>>
458  NumElements2Actions[LastOp - FirstOp + 1];
459 };
460 
461 } // end namespace llvm.
462 
463 #endif // LLVM_CODEGEN_GLOBALISEL_LEGALIZERINFO_H
InstrAspect(unsigned Opcode, unsigned Idx, LLT Type)
Definition: LegalizerInfo.h:46
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:245
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
std::function< SizeAndActionsVec(const SizeAndActionsVec &v)> SizeChangeStrategy
std::vector< SizeAndAction > SizeAndActionsVec
static SizeAndActionsVec narrowToSmallerAndUnsupportedIfTooSmall(const SizeAndActionsVec &v)
unsigned second
static SizeAndActionsVec unsupportedForDifferentSizes(const SizeAndActionsVec &v)
A SizeChangeStrategy for the common case where legalization for a particular operation consists of on...
static SizeAndActionsVec widenToLargerTypesUnsupportedOtherwise(const SizeAndActionsVec &v)
Sentinel value for when no action was found in the specified table.
InstrAspect(unsigned Opcode, LLT Type)
Definition: LegalizerInfo.h:45
The target wants to do something special with this combination of operand and type.
Definition: LegalizerInfo.h:93
unsigned const MachineRegisterInfo * MRI
The (vector) operation should be implemented by splitting it into sub-vectors where the operation is ...
Definition: LegalizerInfo.h:74
Helper class to build MachineInstr.
The (vector) operation should be implemented by widening the input vector and ignoring the lanes adde...
Definition: LegalizerInfo.h:80
Legalization is decided based on an instruction&#39;s opcode, which type slot we&#39;re considering, and what the existing type is.
Definition: LegalizerInfo.h:40
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:835
unsigned first
static SizeAndActionsVec narrowToSmallerAndWidenToSmallest(const SizeAndActionsVec &v)
The operation should be synthesized from multiple instructions acting on a narrower scalar base-type...
Definition: LegalizerInfo.h:64
The operation should be implemented as a call to some kind of runtime support library.
Definition: LegalizerInfo.h:89
void setLegalizeVectorElementToDifferentSizeStrategy(const unsigned Opcode, const unsigned TypeIdx, SizeChangeStrategy S)
See also setLegalizeScalarToDifferentSizeStrategy.
AddressSpace
Definition: NVPTXBaseInfo.h:22
The operation should be implemented in terms of a wider scalar base-type.
Definition: LegalizerInfo.h:69
The operation itself must be expressed in terms of simpler actions on this target.
Definition: LegalizerInfo.h:84
The operation is expected to be selectable directly by the target, and no transformation is necessary...
Definition: LegalizerInfo.h:59
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:60
static bool needsLegalizingToDifferentSize(const LegalizeAction Action)
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...
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...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
This operation is completely unsupported on the target.
Definition: LegalizerInfo.h:97
bool operator==(const InstrAspect &RHS) const
Definition: LegalizerInfo.h:49
IRTranslator LLVM IR MI
void setAction(const InstrAspect &Aspect, LegalizeAction Action)
More friendly way to set an action for common types that have an LLT representation.
std::pair< uint16_t, LegalizeAction > SizeAndAction
void resize(size_type N)
Definition: SmallVector.h:353