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 
operator <<(raw_ostream & OS,LegacyLegalizeAction Action)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 
LegacyLegalizerInfo()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   setScalarAction(TargetOpcode::G_INTRINSIC_CONVERGENT, 0, {{1, Legal}});
80   setScalarAction(TargetOpcode::G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS, 0,
81                   {{1, Legal}});
82 
83   setLegalizeScalarToDifferentSizeStrategy(
84       TargetOpcode::G_IMPLICIT_DEF, 0, narrowToSmallerAndUnsupportedIfTooSmall);
85   setLegalizeScalarToDifferentSizeStrategy(
86       TargetOpcode::G_ADD, 0, widenToLargerTypesAndNarrowToLargest);
87   setLegalizeScalarToDifferentSizeStrategy(
88       TargetOpcode::G_OR, 0, widenToLargerTypesAndNarrowToLargest);
89   setLegalizeScalarToDifferentSizeStrategy(
90       TargetOpcode::G_LOAD, 0, narrowToSmallerAndUnsupportedIfTooSmall);
91   setLegalizeScalarToDifferentSizeStrategy(
92       TargetOpcode::G_STORE, 0, narrowToSmallerAndUnsupportedIfTooSmall);
93 
94   setLegalizeScalarToDifferentSizeStrategy(
95       TargetOpcode::G_BRCOND, 0, widenToLargerTypesUnsupportedOtherwise);
96   setLegalizeScalarToDifferentSizeStrategy(
97       TargetOpcode::G_INSERT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
98   setLegalizeScalarToDifferentSizeStrategy(
99       TargetOpcode::G_EXTRACT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
100   setLegalizeScalarToDifferentSizeStrategy(
101       TargetOpcode::G_EXTRACT, 1, narrowToSmallerAndUnsupportedIfTooSmall);
102   setScalarAction(TargetOpcode::G_FNEG, 0, {{1, Lower}});
103 }
104 
computeTables()105 void 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(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.
139         SizeChangeStrategy S = &unsupportedForDifferentSizes;
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 =
182           &unsupportedForDifferentSizes;
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.
199 std::pair<LegacyLegalizeAction, LLT>
getAspectAction(const InstrAspect & Aspect) const200 LegacyLegalizerInfo::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 
210 LegacyLegalizerInfo::SizeAndActionsVec
increaseToLargerTypesAndDecreaseToLargest(const SizeAndActionsVec & v,LegacyLegalizeAction IncreaseAction,LegacyLegalizeAction DecreaseAction)211 LegacyLegalizerInfo::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({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 
230 LegacyLegalizerInfo::SizeAndActionsVec
decreaseToSmallerTypesAndIncreaseToSmallest(const SizeAndActionsVec & v,LegacyLegalizeAction DecreaseAction,LegacyLegalizeAction IncreaseAction)231 LegacyLegalizerInfo::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({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 
246 LegacyLegalizerInfo::SizeAndAction
findAction(const SizeAndActionsVec & Vec,const uint32_t Size)247 LegacyLegalizerInfo::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};
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(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 
302 std::pair<LegacyLegalizeAction, LLT>
findScalarLegalAction(const InstrAspect & Aspect) const303 LegacyLegalizerInfo::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 
331 std::pair<LegacyLegalizeAction, LLT>
findVectorLegalAction(const InstrAspect & Aspect) const332 LegacyLegalizerInfo::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 
getOpcodeIdxForOpcode(unsigned Opcode) const366 unsigned LegacyLegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
367   assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
368   return Opcode - FirstOp;
369 }
370 
371 
372 LegacyLegalizeActionStep
getAction(const LegalityQuery & Query) const373 LegacyLegalizerInfo::getAction(const LegalityQuery &Query) const {
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 
387