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 
23 using namespace llvm;
24 using namespace LegacyLegalizeActions;
25 
26 #define DEBUG_TYPE "legalizer-info"
27 
28 raw_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 
67 LegacyLegalizerInfo::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(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 
80   setLegalizeScalarToDifferentSizeStrategy(
81       TargetOpcode::G_IMPLICIT_DEF, 0, narrowToSmallerAndUnsupportedIfTooSmall);
82   setLegalizeScalarToDifferentSizeStrategy(
83       TargetOpcode::G_ADD, 0, widenToLargerTypesAndNarrowToLargest);
84   setLegalizeScalarToDifferentSizeStrategy(
85       TargetOpcode::G_OR, 0, widenToLargerTypesAndNarrowToLargest);
86   setLegalizeScalarToDifferentSizeStrategy(
87       TargetOpcode::G_LOAD, 0, narrowToSmallerAndUnsupportedIfTooSmall);
88   setLegalizeScalarToDifferentSizeStrategy(
89       TargetOpcode::G_STORE, 0, narrowToSmallerAndUnsupportedIfTooSmall);
90 
91   setLegalizeScalarToDifferentSizeStrategy(
92       TargetOpcode::G_BRCOND, 0, widenToLargerTypesUnsupportedOtherwise);
93   setLegalizeScalarToDifferentSizeStrategy(
94       TargetOpcode::G_INSERT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
95   setLegalizeScalarToDifferentSizeStrategy(
96       TargetOpcode::G_EXTRACT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
97   setLegalizeScalarToDifferentSizeStrategy(
98       TargetOpcode::G_EXTRACT, 1, narrowToSmallerAndUnsupportedIfTooSmall);
99   setScalarAction(TargetOpcode::G_FNEG, 0, {{1, Lower}});
100 }
101 
102 void LegacyLegalizerInfo::computeTables() {
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.
136         SizeChangeStrategy S = &unsupportedForDifferentSizes;
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 =
179           &unsupportedForDifferentSizes;
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.
196 std::pair<LegacyLegalizeAction, LLT>
197 LegacyLegalizerInfo::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 
207 LegacyLegalizerInfo::SizeAndActionsVec
208 LegacyLegalizerInfo::increaseToLargerTypesAndDecreaseToLargest(
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 
227 LegacyLegalizerInfo::SizeAndActionsVec
228 LegacyLegalizerInfo::decreaseToSmallerTypesAndIncreaseToSmallest(
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 
243 LegacyLegalizerInfo::SizeAndAction
244 LegacyLegalizerInfo::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};
280     llvm_unreachable("");
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};
289     llvm_unreachable("");
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 
299 std::pair<LegacyLegalizeAction, LLT>
300 LegacyLegalizerInfo::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 
328 std::pair<LegacyLegalizeAction, LLT>
329 LegacyLegalizerInfo::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 
363 unsigned LegacyLegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
364   assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
365   return Opcode - FirstOp;
366 }
367 
368 
369 LegacyLegalizeActionStep
370 LegacyLegalizerInfo::getAction(const LegalityQuery &Query) const {
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 
384