LLVM 19.0.0git
LegacyLegalizerInfo.cpp
Go to the documentation of this file.
1//===- lib/CodeGen/GlobalISel/LegacyLegalizerInfo.cpp - Legalizer ---------===//
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// Implement an interface to specify and query how an illegal operation on a
10// given type should be expanded.
11//
12// Issues to be resolved:
13// + Make it fast.
14// + Support weird types like i3, <7 x i3>, ...
15// + Operations with more than one type (ICMP, CMPXCHG, intrinsics, ...)
16//
17//===----------------------------------------------------------------------===//
18
21#include <map>
22
23using namespace llvm;
24using namespace LegacyLegalizeActions;
25
26#define DEBUG_TYPE "legalizer-info"
27
29 switch (Action) {
30 case Legal:
31 OS << "Legal";
32 break;
33 case NarrowScalar:
34 OS << "NarrowScalar";
35 break;
36 case WidenScalar:
37 OS << "WidenScalar";
38 break;
39 case FewerElements:
40 OS << "FewerElements";
41 break;
42 case MoreElements:
43 OS << "MoreElements";
44 break;
45 case Bitcast:
46 OS << "Bitcast";
47 break;
48 case Lower:
49 OS << "Lower";
50 break;
51 case Libcall:
52 OS << "Libcall";
53 break;
54 case Custom:
55 OS << "Custom";
56 break;
57 case Unsupported:
58 OS << "Unsupported";
59 break;
60 case NotFound:
61 OS << "NotFound";
62 break;
63 }
64 return OS;
65}
66
68 // Set defaults.
69 // FIXME: these two (G_ANYEXT and G_TRUNC?) can be legalized to the
70 // fundamental load/store Jakob proposed. Once loads & stores are supported.
71 setScalarAction(TargetOpcode::G_ANYEXT, 1, {{1, Legal}});
72 setScalarAction(TargetOpcode::G_ZEXT, 1, {{1, Legal}});
73 setScalarAction(TargetOpcode::G_SEXT, 1, {{1, Legal}});
74 setScalarAction(TargetOpcode::G_TRUNC, 0, {{1, Legal}});
75 setScalarAction(TargetOpcode::G_TRUNC, 1, {{1, Legal}});
76
77 setScalarAction(TargetOpcode::G_INTRINSIC, 0, {{1, Legal}});
78 setScalarAction(TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS, 0, {{1, Legal}});
79 setScalarAction(TargetOpcode::G_INTRINSIC_CONVERGENT, 0, {{1, Legal}});
80 setScalarAction(TargetOpcode::G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS, 0,
81 {{1, Legal}});
82
84 TargetOpcode::G_IMPLICIT_DEF, 0, narrowToSmallerAndUnsupportedIfTooSmall);
86 TargetOpcode::G_ADD, 0, widenToLargerTypesAndNarrowToLargest);
88 TargetOpcode::G_OR, 0, widenToLargerTypesAndNarrowToLargest);
90 TargetOpcode::G_LOAD, 0, narrowToSmallerAndUnsupportedIfTooSmall);
92 TargetOpcode::G_STORE, 0, narrowToSmallerAndUnsupportedIfTooSmall);
93
95 TargetOpcode::G_BRCOND, 0, widenToLargerTypesUnsupportedOtherwise);
97 TargetOpcode::G_INSERT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
99 TargetOpcode::G_EXTRACT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
101 TargetOpcode::G_EXTRACT, 1, narrowToSmallerAndUnsupportedIfTooSmall);
102 setScalarAction(TargetOpcode::G_FNEG, 0, {{1, Lower}});
103}
104
106 assert(TablesInitialized == false);
107
108 for (unsigned OpcodeIdx = 0; OpcodeIdx <= LastOp - FirstOp; ++OpcodeIdx) {
109 const unsigned Opcode = FirstOp + OpcodeIdx;
110 for (unsigned TypeIdx = 0; TypeIdx != SpecifiedActions[OpcodeIdx].size();
111 ++TypeIdx) {
112 // 0. Collect information specified through the setAction API, i.e.
113 // for specific bit sizes.
114 // For scalar types:
115 SizeAndActionsVec ScalarSpecifiedActions;
116 // For pointer types:
117 std::map<uint16_t, SizeAndActionsVec> AddressSpace2SpecifiedActions;
118 // For vector types:
119 std::map<uint16_t, SizeAndActionsVec> ElemSize2SpecifiedActions;
120 for (auto LLT2Action : SpecifiedActions[OpcodeIdx][TypeIdx]) {
121 const LLT Type = LLT2Action.first;
122 const LegacyLegalizeAction Action = LLT2Action.second;
123
124 auto SizeAction = std::make_pair(Type.getSizeInBits(), Action);
125 if (Type.isPointer())
126 AddressSpace2SpecifiedActions[Type.getAddressSpace()].push_back(
127 SizeAction);
128 else if (Type.isVector())
129 ElemSize2SpecifiedActions[Type.getElementType().getSizeInBits()]
130 .push_back(SizeAction);
131 else
132 ScalarSpecifiedActions.push_back(SizeAction);
133 }
134
135 // 1. Handle scalar types
136 {
137 // Decide how to handle bit sizes for which no explicit specification
138 // was given.
140 if (TypeIdx < ScalarSizeChangeStrategies[OpcodeIdx].size() &&
141 ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
142 S = ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx];
143 llvm::sort(ScalarSpecifiedActions);
144 checkPartialSizeAndActionsVector(ScalarSpecifiedActions);
145 setScalarAction(Opcode, TypeIdx, S(ScalarSpecifiedActions));
146 }
147
148 // 2. Handle pointer types
149 for (auto PointerSpecifiedActions : AddressSpace2SpecifiedActions) {
150 llvm::sort(PointerSpecifiedActions.second);
151 checkPartialSizeAndActionsVector(PointerSpecifiedActions.second);
152 // For pointer types, we assume that there isn't a meaningfull way
153 // to change the number of bits used in the pointer.
154 setPointerAction(
155 Opcode, TypeIdx, PointerSpecifiedActions.first,
156 unsupportedForDifferentSizes(PointerSpecifiedActions.second));
157 }
158
159 // 3. Handle vector types
160 SizeAndActionsVec ElementSizesSeen;
161 for (auto VectorSpecifiedActions : ElemSize2SpecifiedActions) {
162 llvm::sort(VectorSpecifiedActions.second);
163 const uint16_t ElementSize = VectorSpecifiedActions.first;
164 ElementSizesSeen.push_back({ElementSize, Legal});
165 checkPartialSizeAndActionsVector(VectorSpecifiedActions.second);
166 // For vector types, we assume that the best way to adapt the number
167 // of elements is to the next larger number of elements type for which
168 // the vector type is legal, unless there is no such type. In that case,
169 // legalize towards a vector type with a smaller number of elements.
170 SizeAndActionsVec NumElementsActions;
171 for (SizeAndAction BitsizeAndAction : VectorSpecifiedActions.second) {
172 assert(BitsizeAndAction.first % ElementSize == 0);
173 const uint16_t NumElements = BitsizeAndAction.first / ElementSize;
174 NumElementsActions.push_back({NumElements, BitsizeAndAction.second});
175 }
176 setVectorNumElementAction(
177 Opcode, TypeIdx, ElementSize,
178 moreToWiderTypesAndLessToWidest(NumElementsActions));
179 }
180 llvm::sort(ElementSizesSeen);
181 SizeChangeStrategy VectorElementSizeChangeStrategy =
183 if (TypeIdx < VectorElementSizeChangeStrategies[OpcodeIdx].size() &&
184 VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
185 VectorElementSizeChangeStrategy =
186 VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx];
187 setScalarInVectorAction(
188 Opcode, TypeIdx, VectorElementSizeChangeStrategy(ElementSizesSeen));
189 }
190 }
191
192 TablesInitialized = true;
193}
194
195// FIXME: inefficient implementation for now. Without ComputeValueVTs we're
196// probably going to need specialized lookup structures for various types before
197// we have any hope of doing well with something like <13 x i3>. Even the common
198// cases should do better than what we have now.
199std::pair<LegacyLegalizeAction, LLT>
200LegacyLegalizerInfo::getAspectAction(const InstrAspect &Aspect) const {
201 assert(TablesInitialized && "backend forgot to call computeTables");
202 // These *have* to be implemented for now, they're the fundamental basis of
203 // how everything else is transformed.
204 if (Aspect.Type.isScalar() || Aspect.Type.isPointer())
205 return findScalarLegalAction(Aspect);
206 assert(Aspect.Type.isVector());
207 return findVectorLegalAction(Aspect);
208}
209
212 const SizeAndActionsVec &v, LegacyLegalizeAction IncreaseAction,
213 LegacyLegalizeAction DecreaseAction) {
214 SizeAndActionsVec result;
215 unsigned LargestSizeSoFar = 0;
216 if (v.size() >= 1 && v[0].first != 1)
217 result.push_back({1, IncreaseAction});
218 for (size_t i = 0; i < v.size(); ++i) {
219 result.push_back(v[i]);
220 LargestSizeSoFar = v[i].first;
221 if (i + 1 < v.size() && v[i + 1].first != v[i].first + 1) {
222 result.push_back({LargestSizeSoFar + 1, IncreaseAction});
223 LargestSizeSoFar = v[i].first + 1;
224 }
225 }
226 result.push_back({LargestSizeSoFar + 1, DecreaseAction});
227 return result;
228}
229
232 const SizeAndActionsVec &v, LegacyLegalizeAction DecreaseAction,
233 LegacyLegalizeAction IncreaseAction) {
234 SizeAndActionsVec result;
235 if (v.size() == 0 || v[0].first != 1)
236 result.push_back({1, IncreaseAction});
237 for (size_t i = 0; i < v.size(); ++i) {
238 result.push_back(v[i]);
239 if (i + 1 == v.size() || v[i + 1].first != v[i].first + 1) {
240 result.push_back({v[i].first + 1, DecreaseAction});
241 }
242 }
243 return result;
244}
245
247LegacyLegalizerInfo::findAction(const SizeAndActionsVec &Vec, const uint32_t Size) {
248 assert(Size >= 1);
249 // Find the last element in Vec that has a bitsize equal to or smaller than
250 // the requested bit size.
251 // That is the element just before the first element that is bigger than Size.
252 auto It = partition_point(
253 Vec, [=](const SizeAndAction &A) { return A.first <= Size; });
254 assert(It != Vec.begin() && "Does Vec not start with size 1?");
255 int VecIdx = It - Vec.begin() - 1;
256
257 LegacyLegalizeAction Action = Vec[VecIdx].second;
258 switch (Action) {
259 case Legal:
260 case Bitcast:
261 case Lower:
262 case Libcall:
263 case Custom:
264 return {Size, Action};
265 case FewerElements:
266 // FIXME: is this special case still needed and correct?
267 // Special case for scalarization:
268 if (Vec == SizeAndActionsVec({{1, FewerElements}}))
269 return {1, FewerElements};
270 [[fallthrough]];
271 case NarrowScalar: {
272 // The following needs to be a loop, as for now, we do allow needing to
273 // go over "Unsupported" bit sizes before finding a legalizable bit size.
274 // e.g. (s8, WidenScalar), (s9, Unsupported), (s32, Legal). if Size==8,
275 // we need to iterate over s9, and then to s32 to return (s32, Legal).
276 // If we want to get rid of the below loop, we should have stronger asserts
277 // when building the SizeAndActionsVecs, probably not allowing
278 // "Unsupported" unless at the ends of the vector.
279 for (int i = VecIdx - 1; i >= 0; --i)
280 if (!needsLegalizingToDifferentSize(Vec[i].second) &&
281 Vec[i].second != Unsupported)
282 return {Vec[i].first, Action};
284 }
285 case WidenScalar:
286 case MoreElements: {
287 // See above, the following needs to be a loop, at least for now.
288 for (std::size_t i = VecIdx + 1; i < Vec.size(); ++i)
289 if (!needsLegalizingToDifferentSize(Vec[i].second) &&
290 Vec[i].second != Unsupported)
291 return {Vec[i].first, Action};
293 }
294 case Unsupported:
295 return {Size, Unsupported};
296 case NotFound:
297 llvm_unreachable("NotFound");
298 }
299 llvm_unreachable("Action has an unknown enum value");
300}
301
302std::pair<LegacyLegalizeAction, LLT>
303LegacyLegalizerInfo::findScalarLegalAction(const InstrAspect &Aspect) const {
304 assert(Aspect.Type.isScalar() || Aspect.Type.isPointer());
305 if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
306 return {NotFound, LLT()};
307 const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
308 if (Aspect.Type.isPointer() &&
309 AddrSpace2PointerActions[OpcodeIdx].find(Aspect.Type.getAddressSpace()) ==
310 AddrSpace2PointerActions[OpcodeIdx].end()) {
311 return {NotFound, LLT()};
312 }
313 const SmallVector<SizeAndActionsVec, 1> &Actions =
314 Aspect.Type.isPointer()
315 ? AddrSpace2PointerActions[OpcodeIdx]
316 .find(Aspect.Type.getAddressSpace())
317 ->second
318 : ScalarActions[OpcodeIdx];
319 if (Aspect.Idx >= Actions.size())
320 return {NotFound, LLT()};
321 const SizeAndActionsVec &Vec = Actions[Aspect.Idx];
322 // FIXME: speed up this search, e.g. by using a results cache for repeated
323 // queries?
324 auto SizeAndAction = findAction(Vec, Aspect.Type.getSizeInBits());
325 return {SizeAndAction.second,
326 Aspect.Type.isScalar() ? LLT::scalar(SizeAndAction.first)
327 : LLT::pointer(Aspect.Type.getAddressSpace(),
328 SizeAndAction.first)};
329}
330
331std::pair<LegacyLegalizeAction, LLT>
332LegacyLegalizerInfo::findVectorLegalAction(const InstrAspect &Aspect) const {
333 assert(Aspect.Type.isVector());
334 // First legalize the vector element size, then legalize the number of
335 // lanes in the vector.
336 if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
337 return {NotFound, Aspect.Type};
338 const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
339 const unsigned TypeIdx = Aspect.Idx;
340 if (TypeIdx >= ScalarInVectorActions[OpcodeIdx].size())
341 return {NotFound, Aspect.Type};
342 const SizeAndActionsVec &ElemSizeVec =
343 ScalarInVectorActions[OpcodeIdx][TypeIdx];
344
345 LLT IntermediateType;
346 auto ElementSizeAndAction =
347 findAction(ElemSizeVec, Aspect.Type.getScalarSizeInBits());
348 IntermediateType = LLT::fixed_vector(Aspect.Type.getNumElements(),
349 ElementSizeAndAction.first);
350 if (ElementSizeAndAction.second != Legal)
351 return {ElementSizeAndAction.second, IntermediateType};
352
353 auto i = NumElements2Actions[OpcodeIdx].find(
354 IntermediateType.getScalarSizeInBits());
355 if (i == NumElements2Actions[OpcodeIdx].end()) {
356 return {NotFound, IntermediateType};
357 }
358 const SizeAndActionsVec &NumElementsVec = (*i).second[TypeIdx];
359 auto NumElementsAndAction =
360 findAction(NumElementsVec, IntermediateType.getNumElements());
361 return {NumElementsAndAction.second,
362 LLT::fixed_vector(NumElementsAndAction.first,
363 IntermediateType.getScalarSizeInBits())};
364}
365
366unsigned LegacyLegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
367 assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
368 return Opcode - FirstOp;
369}
370
371
374 for (unsigned i = 0; i < Query.Types.size(); ++i) {
375 auto Action = getAspectAction({Query.Opcode, i, Query.Types[i]});
376 if (Action.first != Legal) {
377 LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Action="
378 << Action.first << ", " << Action.second << "\n");
379 return {Action.first, i, Action.second};
380 } else
381 LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Legal\n");
382 }
383 LLVM_DEBUG(dbgs() << ".. (legacy) Legal\n");
384 return {Legal, 0, LLT{}};
385}
386
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
uint64_t Size
Interface for Targets to specify which operations they can successfully select and how the others sho...
Interface for Targets to specify which operations they can successfully select and how the others sho...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
constexpr unsigned getScalarSizeInBits() const
Definition: LowLevelType.h:259
constexpr bool isScalar() const
Definition: LowLevelType.h:139
static constexpr LLT scalar(unsigned SizeInBits)
Get a low-level scalar or aggregate "bag of bits".
Definition: LowLevelType.h:42
constexpr uint16_t getNumElements() const
Returns the number of elements in a vector LLT.
Definition: LowLevelType.h:151
constexpr bool isVector() const
Definition: LowLevelType.h:147
constexpr TypeSize getSizeInBits() const
Returns the total size of the type. Must only be called on sized types.
Definition: LowLevelType.h:185
constexpr bool isPointer() const
Definition: LowLevelType.h:141
constexpr unsigned getAddressSpace() const
Definition: LowLevelType.h:272
static constexpr LLT fixed_vector(unsigned NumElements, unsigned ScalarSizeInBits)
Get a low-level fixed-width vector of some number of elements and element width.
Definition: LowLevelType.h:92
std::pair< uint16_t, LegacyLegalizeActions::LegacyLegalizeAction > SizeAndAction
static SizeAndActionsVec decreaseToSmallerTypesAndIncreaseToSmallest(const SizeAndActionsVec &v, LegacyLegalizeActions::LegacyLegalizeAction DecreaseAction, LegacyLegalizeActions::LegacyLegalizeAction IncreaseAction)
Helper function to implement many typical SizeChangeStrategy functions.
static SizeAndActionsVec widenToLargerTypesUnsupportedOtherwise(const SizeAndActionsVec &v)
static SizeAndActionsVec moreToWiderTypesAndLessToWidest(const SizeAndActionsVec &v)
A SizeChangeStrategy for the common case where legalization for a particular vector operation consist...
void computeTables()
Compute any ancillary tables needed to quickly decide how an operation should be handled.
std::vector< SizeAndAction > SizeAndActionsVec
static bool needsLegalizingToDifferentSize(const LegacyLegalizeActions::LegacyLegalizeAction Action)
unsigned getOpcodeIdxForOpcode(unsigned Opcode) const
static SizeAndActionsVec widenToLargerTypesAndNarrowToLargest(const SizeAndActionsVec &v)
A SizeChangeStrategy for the common case where legalization for a particular operation consists of wi...
LegacyLegalizeActionStep getAction(const LegalityQuery &Query) const
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...
static SizeAndActionsVec unsupportedForDifferentSizes(const SizeAndActionsVec &v)
A SizeChangeStrategy for the common case where legalization for a particular operation consists of on...
static SizeAndActionsVec increaseToLargerTypesAndDecreaseToLargest(const SizeAndActionsVec &v, LegacyLegalizeActions::LegacyLegalizeAction IncreaseAction, LegacyLegalizeActions::LegacyLegalizeAction DecreaseAction)
Helper function to implement many typical SizeChangeStrategy functions.
static SizeAndActionsVec narrowToSmallerAndUnsupportedIfTooSmall(const SizeAndActionsVec &v)
std::function< SizeAndActionsVec(const SizeAndActionsVec &v)> SizeChangeStrategy
size_t size() const
Definition: SmallVector.h:91
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
AddressSpace getAddressSpace(T *V)
Definition: AVR.h:65
@ Bitcast
Perform the operation on a different, but equivalently sized type.
@ MoreElements
The (vector) operation should be implemented by widening the input vector and ignoring the lanes adde...
@ FewerElements
The (vector) operation should be implemented by splitting it into sub-vectors where the operation is ...
@ Unsupported
This operation is completely unsupported on the target.
@ NarrowScalar
The operation should be synthesized from multiple instructions acting on a narrower scalar base-type.
@ Lower
The operation itself must be expressed in terms of simpler actions on this target.
@ Custom
The target wants to do something special with this combination of operand and type.
@ NotFound
Sentinel value for when no action was found in the specified table.
@ WidenScalar
The operation should be implemented in terms of a wider scalar base-type.
@ Libcall
The operation should be implemented as a call to some kind of runtime support library.
ManagedStatic< cl::opt< FnT >, OptCreatorT > Action
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:237
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1689
auto partition_point(R &&Range, Predicate P)
Binary search for the first iterator in a range where a predicate is false.
Definition: STLExtras.h:1988
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1656
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:293
Legalization is decided based on an instruction's opcode, which type slot we're considering,...
The LegalityQuery object bundles together all the information that's needed to decide whether a given...
ArrayRef< LLT > Types