LLVM 17.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
81 TargetOpcode::G_IMPLICIT_DEF, 0, narrowToSmallerAndUnsupportedIfTooSmall);
83 TargetOpcode::G_ADD, 0, widenToLargerTypesAndNarrowToLargest);
85 TargetOpcode::G_OR, 0, widenToLargerTypesAndNarrowToLargest);
87 TargetOpcode::G_LOAD, 0, narrowToSmallerAndUnsupportedIfTooSmall);
89 TargetOpcode::G_STORE, 0, narrowToSmallerAndUnsupportedIfTooSmall);
90
92 TargetOpcode::G_BRCOND, 0, widenToLargerTypesUnsupportedOtherwise);
94 TargetOpcode::G_INSERT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
96 TargetOpcode::G_EXTRACT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
98 TargetOpcode::G_EXTRACT, 1, narrowToSmallerAndUnsupportedIfTooSmall);
99 setScalarAction(TargetOpcode::G_FNEG, 0, {{1, Lower}});
100}
101
103 assert(TablesInitialized == false);
104
105 for (unsigned OpcodeIdx = 0; OpcodeIdx <= LastOp - FirstOp; ++OpcodeIdx) {
106 const unsigned Opcode = FirstOp + OpcodeIdx;
107 for (unsigned TypeIdx = 0; TypeIdx != SpecifiedActions[OpcodeIdx].size();
108 ++TypeIdx) {
109 // 0. Collect information specified through the setAction API, i.e.
110 // for specific bit sizes.
111 // For scalar types:
112 SizeAndActionsVec ScalarSpecifiedActions;
113 // For pointer types:
114 std::map<uint16_t, SizeAndActionsVec> AddressSpace2SpecifiedActions;
115 // For vector types:
116 std::map<uint16_t, SizeAndActionsVec> ElemSize2SpecifiedActions;
117 for (auto LLT2Action : SpecifiedActions[OpcodeIdx][TypeIdx]) {
118 const LLT Type = LLT2Action.first;
119 const LegacyLegalizeAction Action = LLT2Action.second;
120
121 auto SizeAction = std::make_pair(Type.getSizeInBits(), Action);
122 if (Type.isPointer())
123 AddressSpace2SpecifiedActions[Type.getAddressSpace()].push_back(
124 SizeAction);
125 else if (Type.isVector())
126 ElemSize2SpecifiedActions[Type.getElementType().getSizeInBits()]
127 .push_back(SizeAction);
128 else
129 ScalarSpecifiedActions.push_back(SizeAction);
130 }
131
132 // 1. Handle scalar types
133 {
134 // Decide how to handle bit sizes for which no explicit specification
135 // was given.
137 if (TypeIdx < ScalarSizeChangeStrategies[OpcodeIdx].size() &&
138 ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
139 S = ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx];
140 llvm::sort(ScalarSpecifiedActions);
141 checkPartialSizeAndActionsVector(ScalarSpecifiedActions);
142 setScalarAction(Opcode, TypeIdx, S(ScalarSpecifiedActions));
143 }
144
145 // 2. Handle pointer types
146 for (auto PointerSpecifiedActions : AddressSpace2SpecifiedActions) {
147 llvm::sort(PointerSpecifiedActions.second);
148 checkPartialSizeAndActionsVector(PointerSpecifiedActions.second);
149 // For pointer types, we assume that there isn't a meaningfull way
150 // to change the number of bits used in the pointer.
151 setPointerAction(
152 Opcode, TypeIdx, PointerSpecifiedActions.first,
153 unsupportedForDifferentSizes(PointerSpecifiedActions.second));
154 }
155
156 // 3. Handle vector types
157 SizeAndActionsVec ElementSizesSeen;
158 for (auto VectorSpecifiedActions : ElemSize2SpecifiedActions) {
159 llvm::sort(VectorSpecifiedActions.second);
160 const uint16_t ElementSize = VectorSpecifiedActions.first;
161 ElementSizesSeen.push_back({ElementSize, Legal});
162 checkPartialSizeAndActionsVector(VectorSpecifiedActions.second);
163 // For vector types, we assume that the best way to adapt the number
164 // of elements is to the next larger number of elements type for which
165 // the vector type is legal, unless there is no such type. In that case,
166 // legalize towards a vector type with a smaller number of elements.
167 SizeAndActionsVec NumElementsActions;
168 for (SizeAndAction BitsizeAndAction : VectorSpecifiedActions.second) {
169 assert(BitsizeAndAction.first % ElementSize == 0);
170 const uint16_t NumElements = BitsizeAndAction.first / ElementSize;
171 NumElementsActions.push_back({NumElements, BitsizeAndAction.second});
172 }
173 setVectorNumElementAction(
174 Opcode, TypeIdx, ElementSize,
175 moreToWiderTypesAndLessToWidest(NumElementsActions));
176 }
177 llvm::sort(ElementSizesSeen);
178 SizeChangeStrategy VectorElementSizeChangeStrategy =
180 if (TypeIdx < VectorElementSizeChangeStrategies[OpcodeIdx].size() &&
181 VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
182 VectorElementSizeChangeStrategy =
183 VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx];
184 setScalarInVectorAction(
185 Opcode, TypeIdx, VectorElementSizeChangeStrategy(ElementSizesSeen));
186 }
187 }
188
189 TablesInitialized = true;
190}
191
192// FIXME: inefficient implementation for now. Without ComputeValueVTs we're
193// probably going to need specialized lookup structures for various types before
194// we have any hope of doing well with something like <13 x i3>. Even the common
195// cases should do better than what we have now.
196std::pair<LegacyLegalizeAction, LLT>
197LegacyLegalizerInfo::getAspectAction(const InstrAspect &Aspect) const {
198 assert(TablesInitialized && "backend forgot to call computeTables");
199 // These *have* to be implemented for now, they're the fundamental basis of
200 // how everything else is transformed.
201 if (Aspect.Type.isScalar() || Aspect.Type.isPointer())
202 return findScalarLegalAction(Aspect);
203 assert(Aspect.Type.isVector());
204 return findVectorLegalAction(Aspect);
205}
206
209 const SizeAndActionsVec &v, LegacyLegalizeAction IncreaseAction,
210 LegacyLegalizeAction DecreaseAction) {
211 SizeAndActionsVec result;
212 unsigned LargestSizeSoFar = 0;
213 if (v.size() >= 1 && v[0].first != 1)
214 result.push_back({1, IncreaseAction});
215 for (size_t i = 0; i < v.size(); ++i) {
216 result.push_back(v[i]);
217 LargestSizeSoFar = v[i].first;
218 if (i + 1 < v.size() && v[i + 1].first != v[i].first + 1) {
219 result.push_back({LargestSizeSoFar + 1, IncreaseAction});
220 LargestSizeSoFar = v[i].first + 1;
221 }
222 }
223 result.push_back({LargestSizeSoFar + 1, DecreaseAction});
224 return result;
225}
226
229 const SizeAndActionsVec &v, LegacyLegalizeAction DecreaseAction,
230 LegacyLegalizeAction IncreaseAction) {
231 SizeAndActionsVec result;
232 if (v.size() == 0 || v[0].first != 1)
233 result.push_back({1, IncreaseAction});
234 for (size_t i = 0; i < v.size(); ++i) {
235 result.push_back(v[i]);
236 if (i + 1 == v.size() || v[i + 1].first != v[i].first + 1) {
237 result.push_back({v[i].first + 1, DecreaseAction});
238 }
239 }
240 return result;
241}
242
244LegacyLegalizerInfo::findAction(const SizeAndActionsVec &Vec, const uint32_t Size) {
245 assert(Size >= 1);
246 // Find the last element in Vec that has a bitsize equal to or smaller than
247 // the requested bit size.
248 // That is the element just before the first element that is bigger than Size.
249 auto It = partition_point(
250 Vec, [=](const SizeAndAction &A) { return A.first <= Size; });
251 assert(It != Vec.begin() && "Does Vec not start with size 1?");
252 int VecIdx = It - Vec.begin() - 1;
253
254 LegacyLegalizeAction Action = Vec[VecIdx].second;
255 switch (Action) {
256 case Legal:
257 case Bitcast:
258 case Lower:
259 case Libcall:
260 case Custom:
261 return {Size, Action};
262 case FewerElements:
263 // FIXME: is this special case still needed and correct?
264 // Special case for scalarization:
265 if (Vec == SizeAndActionsVec({{1, FewerElements}}))
266 return {1, FewerElements};
267 [[fallthrough]];
268 case NarrowScalar: {
269 // The following needs to be a loop, as for now, we do allow needing to
270 // go over "Unsupported" bit sizes before finding a legalizable bit size.
271 // e.g. (s8, WidenScalar), (s9, Unsupported), (s32, Legal). if Size==8,
272 // we need to iterate over s9, and then to s32 to return (s32, Legal).
273 // If we want to get rid of the below loop, we should have stronger asserts
274 // when building the SizeAndActionsVecs, probably not allowing
275 // "Unsupported" unless at the ends of the vector.
276 for (int i = VecIdx - 1; i >= 0; --i)
277 if (!needsLegalizingToDifferentSize(Vec[i].second) &&
278 Vec[i].second != Unsupported)
279 return {Vec[i].first, Action};
281 }
282 case WidenScalar:
283 case MoreElements: {
284 // See above, the following needs to be a loop, at least for now.
285 for (std::size_t i = VecIdx + 1; i < Vec.size(); ++i)
286 if (!needsLegalizingToDifferentSize(Vec[i].second) &&
287 Vec[i].second != Unsupported)
288 return {Vec[i].first, Action};
290 }
291 case Unsupported:
292 return {Size, Unsupported};
293 case NotFound:
294 llvm_unreachable("NotFound");
295 }
296 llvm_unreachable("Action has an unknown enum value");
297}
298
299std::pair<LegacyLegalizeAction, LLT>
300LegacyLegalizerInfo::findScalarLegalAction(const InstrAspect &Aspect) const {
301 assert(Aspect.Type.isScalar() || Aspect.Type.isPointer());
302 if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
303 return {NotFound, LLT()};
304 const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
305 if (Aspect.Type.isPointer() &&
306 AddrSpace2PointerActions[OpcodeIdx].find(Aspect.Type.getAddressSpace()) ==
307 AddrSpace2PointerActions[OpcodeIdx].end()) {
308 return {NotFound, LLT()};
309 }
310 const SmallVector<SizeAndActionsVec, 1> &Actions =
311 Aspect.Type.isPointer()
312 ? AddrSpace2PointerActions[OpcodeIdx]
313 .find(Aspect.Type.getAddressSpace())
314 ->second
315 : ScalarActions[OpcodeIdx];
316 if (Aspect.Idx >= Actions.size())
317 return {NotFound, LLT()};
318 const SizeAndActionsVec &Vec = Actions[Aspect.Idx];
319 // FIXME: speed up this search, e.g. by using a results cache for repeated
320 // queries?
321 auto SizeAndAction = findAction(Vec, Aspect.Type.getSizeInBits());
322 return {SizeAndAction.second,
323 Aspect.Type.isScalar() ? LLT::scalar(SizeAndAction.first)
324 : LLT::pointer(Aspect.Type.getAddressSpace(),
325 SizeAndAction.first)};
326}
327
328std::pair<LegacyLegalizeAction, LLT>
329LegacyLegalizerInfo::findVectorLegalAction(const InstrAspect &Aspect) const {
330 assert(Aspect.Type.isVector());
331 // First legalize the vector element size, then legalize the number of
332 // lanes in the vector.
333 if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
334 return {NotFound, Aspect.Type};
335 const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
336 const unsigned TypeIdx = Aspect.Idx;
337 if (TypeIdx >= ScalarInVectorActions[OpcodeIdx].size())
338 return {NotFound, Aspect.Type};
339 const SizeAndActionsVec &ElemSizeVec =
340 ScalarInVectorActions[OpcodeIdx][TypeIdx];
341
342 LLT IntermediateType;
343 auto ElementSizeAndAction =
344 findAction(ElemSizeVec, Aspect.Type.getScalarSizeInBits());
345 IntermediateType = LLT::fixed_vector(Aspect.Type.getNumElements(),
346 ElementSizeAndAction.first);
347 if (ElementSizeAndAction.second != Legal)
348 return {ElementSizeAndAction.second, IntermediateType};
349
350 auto i = NumElements2Actions[OpcodeIdx].find(
351 IntermediateType.getScalarSizeInBits());
352 if (i == NumElements2Actions[OpcodeIdx].end()) {
353 return {NotFound, IntermediateType};
354 }
355 const SizeAndActionsVec &NumElementsVec = (*i).second[TypeIdx];
356 auto NumElementsAndAction =
357 findAction(NumElementsVec, IntermediateType.getNumElements());
358 return {NumElementsAndAction.second,
359 LLT::fixed_vector(NumElementsAndAction.first,
360 IntermediateType.getScalarSizeInBits())};
361}
362
363unsigned LegacyLegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
364 assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
365 return Opcode - FirstOp;
366}
367
368
371 for (unsigned i = 0; i < Query.Types.size(); ++i) {
372 auto Action = getAspectAction({Query.Opcode, i, Query.Types[i]});
373 if (Action.first != Legal) {
374 LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Action="
375 << Action.first << ", " << Action.second << "\n");
376 return {Action.first, i, Action.second};
377 } else
378 LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Legal\n");
379 }
380 LLVM_DEBUG(dbgs() << ".. (legacy) Legal\n");
381 return {Legal, 0, LLT{}};
382}
383
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:233
constexpr bool isScalar() const
Definition: LowLevelType.h:123
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:133
constexpr bool isVector() const
Definition: LowLevelType.h:129
constexpr TypeSize getSizeInBits() const
Returns the total size of the type. Must only be called on sized types.
Definition: LowLevelType.h:159
constexpr bool isPointer() const
Definition: LowLevelType.h:125
constexpr unsigned getAddressSpace() const
Definition: LowLevelType.h:247
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:76
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:1200
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:66
@ 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:236
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:1777
auto partition_point(R &&Range, Predicate P)
Binary search for the first iterator in a range where a predicate is false.
Definition: STLExtras.h:2076
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1744
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:292
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