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
19#include "llvm/CodeGen/GlobalISel/LegacyLegalizerInfo.h"
20#include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
21#include <map>
22
23using namespace llvm;
24using namespace LegacyLegalizeActions;
25
26#define DEBUG_TYPE "legalizer-info"
27
28raw_ostream &llvm::operator<<(raw_ostream &OS, LegacyLegalizeAction Action) {
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
67LegacyLegalizerInfo::LegacyLegalizerInfo() {
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(Opcode: TargetOpcode::G_ANYEXT, TypeIndex: 1, SizeAndActions: {{1, Legal}});
72 setScalarAction(Opcode: TargetOpcode::G_ZEXT, TypeIndex: 1, SizeAndActions: {{1, Legal}});
73 setScalarAction(Opcode: TargetOpcode::G_SEXT, TypeIndex: 1, SizeAndActions: {{1, Legal}});
74 setScalarAction(Opcode: TargetOpcode::G_TRUNC, TypeIndex: 0, SizeAndActions: {{1, Legal}});
75 setScalarAction(Opcode: TargetOpcode::G_TRUNC, TypeIndex: 1, SizeAndActions: {{1, Legal}});
76
77 setScalarAction(Opcode: TargetOpcode::G_INTRINSIC, TypeIndex: 0, SizeAndActions: {{1, Legal}});
78 setScalarAction(Opcode: TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS, TypeIndex: 0, SizeAndActions: {{1, Legal}});
79 setScalarAction(Opcode: TargetOpcode::G_INTRINSIC_CONVERGENT, TypeIndex: 0, SizeAndActions: {{1, Legal}});
80 setScalarAction(Opcode: TargetOpcode::G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS, TypeIndex: 0,
81 SizeAndActions: {{1, Legal}});
82
83 setLegalizeScalarToDifferentSizeStrategy(
84 Opcode: TargetOpcode::G_IMPLICIT_DEF, TypeIdx: 0, S: narrowToSmallerAndUnsupportedIfTooSmall);
85 setLegalizeScalarToDifferentSizeStrategy(
86 Opcode: TargetOpcode::G_ADD, TypeIdx: 0, S: widenToLargerTypesAndNarrowToLargest);
87 setLegalizeScalarToDifferentSizeStrategy(
88 Opcode: TargetOpcode::G_OR, TypeIdx: 0, S: widenToLargerTypesAndNarrowToLargest);
89 setLegalizeScalarToDifferentSizeStrategy(
90 Opcode: TargetOpcode::G_LOAD, TypeIdx: 0, S: narrowToSmallerAndUnsupportedIfTooSmall);
91 setLegalizeScalarToDifferentSizeStrategy(
92 Opcode: TargetOpcode::G_STORE, TypeIdx: 0, S: narrowToSmallerAndUnsupportedIfTooSmall);
93
94 setLegalizeScalarToDifferentSizeStrategy(
95 Opcode: TargetOpcode::G_BRCOND, TypeIdx: 0, S: widenToLargerTypesUnsupportedOtherwise);
96 setLegalizeScalarToDifferentSizeStrategy(
97 Opcode: TargetOpcode::G_INSERT, TypeIdx: 0, S: narrowToSmallerAndUnsupportedIfTooSmall);
98 setLegalizeScalarToDifferentSizeStrategy(
99 Opcode: TargetOpcode::G_EXTRACT, TypeIdx: 0, S: narrowToSmallerAndUnsupportedIfTooSmall);
100 setLegalizeScalarToDifferentSizeStrategy(
101 Opcode: TargetOpcode::G_EXTRACT, TypeIdx: 1, S: narrowToSmallerAndUnsupportedIfTooSmall);
102 setScalarAction(Opcode: TargetOpcode::G_FNEG, TypeIndex: 0, SizeAndActions: {{1, Lower}});
103}
104
105void LegacyLegalizerInfo::computeTables() {
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(x: Type.getSizeInBits(), y: Action);
125 if (Type.isPointer())
126 AddressSpace2SpecifiedActions[Type.getAddressSpace()].push_back(
127 x: SizeAction);
128 else if (Type.isVector())
129 ElemSize2SpecifiedActions[Type.getElementType().getSizeInBits()]
130 .push_back(x: SizeAction);
131 else
132 ScalarSpecifiedActions.push_back(x: SizeAction);
133 }
134
135 // 1. Handle scalar types
136 {
137 // Decide how to handle bit sizes for which no explicit specification
138 // was given.
139 SizeChangeStrategy S = &unsupportedForDifferentSizes;
140 if (TypeIdx < ScalarSizeChangeStrategies[OpcodeIdx].size() &&
141 ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
142 S = ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx];
143 llvm::sort(C&: ScalarSpecifiedActions);
144 checkPartialSizeAndActionsVector(v: ScalarSpecifiedActions);
145 setScalarAction(Opcode, TypeIndex: TypeIdx, SizeAndActions: S(ScalarSpecifiedActions));
146 }
147
148 // 2. Handle pointer types
149 for (auto PointerSpecifiedActions : AddressSpace2SpecifiedActions) {
150 llvm::sort(C&: PointerSpecifiedActions.second);
151 checkPartialSizeAndActionsVector(v: 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, TypeIndex: TypeIdx, AddressSpace: PointerSpecifiedActions.first,
156 SizeAndActions: unsupportedForDifferentSizes(v: PointerSpecifiedActions.second));
157 }
158
159 // 3. Handle vector types
160 SizeAndActionsVec ElementSizesSeen;
161 for (auto VectorSpecifiedActions : ElemSize2SpecifiedActions) {
162 llvm::sort(C&: VectorSpecifiedActions.second);
163 const uint16_t ElementSize = VectorSpecifiedActions.first;
164 ElementSizesSeen.push_back(x: {ElementSize, Legal});
165 checkPartialSizeAndActionsVector(v: 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(x: {NumElements, BitsizeAndAction.second});
175 }
176 setVectorNumElementAction(
177 Opcode, TypeIndex: TypeIdx, ElementSize,
178 SizeAndActions: moreToWiderTypesAndLessToWidest(v: NumElementsActions));
179 }
180 llvm::sort(C&: ElementSizesSeen);
181 SizeChangeStrategy VectorElementSizeChangeStrategy =
182 &unsupportedForDifferentSizes;
183 if (TypeIdx < VectorElementSizeChangeStrategies[OpcodeIdx].size() &&
184 VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
185 VectorElementSizeChangeStrategy =
186 VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx];
187 setScalarInVectorAction(
188 Opcode, TypeIndex: TypeIdx, SizeAndActions: 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
210LegacyLegalizerInfo::SizeAndActionsVec
211LegacyLegalizerInfo::increaseToLargerTypesAndDecreaseToLargest(
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(x: {1, IncreaseAction});
218 for (size_t i = 0; i < v.size(); ++i) {
219 result.push_back(x: 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(x: {LargestSizeSoFar + 1, IncreaseAction});
223 LargestSizeSoFar = v[i].first + 1;
224 }
225 }
226 result.push_back(x: {LargestSizeSoFar + 1, DecreaseAction});
227 return result;
228}
229
230LegacyLegalizerInfo::SizeAndActionsVec
231LegacyLegalizerInfo::decreaseToSmallerTypesAndIncreaseToSmallest(
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(x: {1, IncreaseAction});
237 for (size_t i = 0; i < v.size(); ++i) {
238 result.push_back(x: v[i]);
239 if (i + 1 == v.size() || v[i + 1].first != v[i].first + 1) {
240 result.push_back(x: {v[i].first + 1, DecreaseAction});
241 }
242 }
243 return result;
244}
245
246LegacyLegalizerInfo::SizeAndAction
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 Range: Vec, P: [=](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(Action: Vec[i].second) &&
281 Vec[i].second != Unsupported)
282 return {Vec[i].first, Action};
283 llvm_unreachable("");
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(Action: Vec[i].second) &&
290 Vec[i].second != Unsupported)
291 return {Vec[i].first, Action};
292 llvm_unreachable("");
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(Opcode: Aspect.Opcode);
308 ArrayRef<SizeAndActionsVec> Actions;
309 if (Aspect.Type.isPointer()) {
310 auto &PA = AddrSpace2PointerActions[OpcodeIdx];
311 auto It = PA.find(x: Aspect.Type.getAddressSpace());
312 if (It == PA.end())
313 return {NotFound, LLT()};
314 Actions = It->second;
315 } else {
316 Actions = ScalarActions[OpcodeIdx];
317 }
318 if (Aspect.Idx >= Actions.size())
319 return {NotFound, LLT()};
320 const SizeAndActionsVec &Vec = Actions[Aspect.Idx];
321 // FIXME: speed up this search, e.g. by using a results cache for repeated
322 // queries?
323 auto SizeAndAction = findAction(Vec, Size: Aspect.Type.getSizeInBits());
324 return {SizeAndAction.second,
325 Aspect.Type.isScalar() ? LLT::scalar(SizeInBits: SizeAndAction.first)
326 : LLT::pointer(AddressSpace: Aspect.Type.getAddressSpace(),
327 SizeInBits: SizeAndAction.first)};
328}
329
330std::pair<LegacyLegalizeAction, LLT>
331LegacyLegalizerInfo::findVectorLegalAction(const InstrAspect &Aspect) const {
332 assert(Aspect.Type.isVector());
333 // First legalize the vector element size, then legalize the number of
334 // lanes in the vector.
335 if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
336 return {NotFound, Aspect.Type};
337 const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Opcode: Aspect.Opcode);
338 const unsigned TypeIdx = Aspect.Idx;
339 if (TypeIdx >= ScalarInVectorActions[OpcodeIdx].size())
340 return {NotFound, Aspect.Type};
341 const SizeAndActionsVec &ElemSizeVec =
342 ScalarInVectorActions[OpcodeIdx][TypeIdx];
343
344 LLT IntermediateType;
345 auto ElementSizeAndAction =
346 findAction(Vec: ElemSizeVec, Size: Aspect.Type.getScalarSizeInBits());
347 IntermediateType = LLT::fixed_vector(NumElements: Aspect.Type.getNumElements(),
348 ScalarSizeInBits: ElementSizeAndAction.first);
349 if (ElementSizeAndAction.second != Legal)
350 return {ElementSizeAndAction.second, IntermediateType};
351
352 auto i = NumElements2Actions[OpcodeIdx].find(
353 x: IntermediateType.getScalarSizeInBits());
354 if (i == NumElements2Actions[OpcodeIdx].end()) {
355 return {NotFound, IntermediateType};
356 }
357 const SizeAndActionsVec &NumElementsVec = (*i).second[TypeIdx];
358 auto NumElementsAndAction =
359 findAction(Vec: NumElementsVec, Size: IntermediateType.getNumElements());
360 return {NumElementsAndAction.second,
361 LLT::fixed_vector(NumElements: NumElementsAndAction.first,
362 ScalarSizeInBits: IntermediateType.getScalarSizeInBits())};
363}
364
365unsigned LegacyLegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
366 assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
367 return Opcode - FirstOp;
368}
369
370
371LegacyLegalizeActionStep
372LegacyLegalizerInfo::getAction(const LegalityQuery &Query) const {
373 for (unsigned i = 0; i < Query.Types.size(); ++i) {
374 auto Action = getAspectAction(Aspect: {Query.Opcode, i, Query.Types[i]});
375 if (Action.first != Legal) {
376 LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Action="
377 << Action.first << ", " << Action.second << "\n");
378 return {Action.first, i, Action.second};
379 } else
380 LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Legal\n");
381 }
382 LLVM_DEBUG(dbgs() << ".. (legacy) Legal\n");
383 return {Legal, 0, LLT{}};
384}
385
386