1 //===- lib/CodeGen/GlobalISel/LegalizerInfo.cpp - Legalizer ---------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Implement an interface to specify and query how an illegal operation on a
11 // given type should be expanded.
12 //
13 // Issues to be resolved:
14 //   + Make it fast.
15 //   + Support weird types like i3, <7 x i3>, ...
16 //   + Operations with more than one type (ICMP, CMPXCHG, intrinsics, ...)
17 //
18 //===----------------------------------------------------------------------===//
19 
20 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
21 #include "llvm/ADT/SmallBitVector.h"
22 #include "llvm/CodeGen/MachineInstr.h"
23 #include "llvm/CodeGen/MachineOperand.h"
24 #include "llvm/CodeGen/MachineRegisterInfo.h"
25 #include "llvm/CodeGen/TargetOpcodes.h"
26 #include "llvm/MC/MCInstrDesc.h"
27 #include "llvm/Support/ErrorHandling.h"
28 #include "llvm/Support/LowLevelTypeImpl.h"
29 #include "llvm/Support/MathExtras.h"
30 #include <algorithm>
31 #include <map>
32 using namespace llvm;
33 
34 LegalizerInfo::LegalizerInfo() : TablesInitialized(false) {
35   // Set defaults.
36   // FIXME: these two (G_ANYEXT and G_TRUNC?) can be legalized to the
37   // fundamental load/store Jakob proposed. Once loads & stores are supported.
38   setScalarAction(TargetOpcode::G_ANYEXT, 1, {{1, Legal}});
39   setScalarAction(TargetOpcode::G_ZEXT, 1, {{1, Legal}});
40   setScalarAction(TargetOpcode::G_SEXT, 1, {{1, Legal}});
41   setScalarAction(TargetOpcode::G_TRUNC, 0, {{1, Legal}});
42   setScalarAction(TargetOpcode::G_TRUNC, 1, {{1, Legal}});
43 
44   setScalarAction(TargetOpcode::G_INTRINSIC, 0, {{1, Legal}});
45   setScalarAction(TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS, 0, {{1, Legal}});
46 
47   setLegalizeScalarToDifferentSizeStrategy(
48       TargetOpcode::G_IMPLICIT_DEF, 0, narrowToSmallerAndUnsupportedIfTooSmall);
49   setLegalizeScalarToDifferentSizeStrategy(
50       TargetOpcode::G_ADD, 0, widenToLargerTypesAndNarrowToLargest);
51   setLegalizeScalarToDifferentSizeStrategy(
52       TargetOpcode::G_OR, 0, widenToLargerTypesAndNarrowToLargest);
53   setLegalizeScalarToDifferentSizeStrategy(
54       TargetOpcode::G_LOAD, 0, narrowToSmallerAndUnsupportedIfTooSmall);
55   setLegalizeScalarToDifferentSizeStrategy(
56       TargetOpcode::G_STORE, 0, narrowToSmallerAndUnsupportedIfTooSmall);
57 
58   setLegalizeScalarToDifferentSizeStrategy(
59       TargetOpcode::G_BRCOND, 0, widenToLargerTypesUnsupportedOtherwise);
60   setLegalizeScalarToDifferentSizeStrategy(
61       TargetOpcode::G_INSERT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
62   setLegalizeScalarToDifferentSizeStrategy(
63       TargetOpcode::G_EXTRACT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
64   setLegalizeScalarToDifferentSizeStrategy(
65       TargetOpcode::G_EXTRACT, 1, narrowToSmallerAndUnsupportedIfTooSmall);
66   setScalarAction(TargetOpcode::G_FNEG, 0, {{1, Lower}});
67 }
68 
69 void LegalizerInfo::computeTables() {
70   assert(TablesInitialized == false);
71 
72   for (unsigned OpcodeIdx = 0; OpcodeIdx <= LastOp - FirstOp; ++OpcodeIdx) {
73     const unsigned Opcode = FirstOp + OpcodeIdx;
74     for (unsigned TypeIdx = 0; TypeIdx != SpecifiedActions[OpcodeIdx].size();
75          ++TypeIdx) {
76       // 0. Collect information specified through the setAction API, i.e.
77       // for specific bit sizes.
78       // For scalar types:
79       SizeAndActionsVec ScalarSpecifiedActions;
80       // For pointer types:
81       std::map<uint16_t, SizeAndActionsVec> AddressSpace2SpecifiedActions;
82       // For vector types:
83       std::map<uint16_t, SizeAndActionsVec> ElemSize2SpecifiedActions;
84       for (auto LLT2Action : SpecifiedActions[OpcodeIdx][TypeIdx]) {
85         const LLT Type = LLT2Action.first;
86         const LegalizeAction Action = LLT2Action.second;
87 
88         auto SizeAction = std::make_pair(Type.getSizeInBits(), Action);
89         if (Type.isPointer())
90           AddressSpace2SpecifiedActions[Type.getAddressSpace()].push_back(
91               SizeAction);
92         else if (Type.isVector())
93           ElemSize2SpecifiedActions[Type.getElementType().getSizeInBits()]
94               .push_back(SizeAction);
95         else
96           ScalarSpecifiedActions.push_back(SizeAction);
97       }
98 
99       // 1. Handle scalar types
100       {
101         // Decide how to handle bit sizes for which no explicit specification
102         // was given.
103         SizeChangeStrategy S = &unsupportedForDifferentSizes;
104         if (TypeIdx < ScalarSizeChangeStrategies[OpcodeIdx].size() &&
105             ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
106           S = ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx];
107         std::sort(ScalarSpecifiedActions.begin(), ScalarSpecifiedActions.end());
108         checkPartialSizeAndActionsVector(ScalarSpecifiedActions);
109         setScalarAction(Opcode, TypeIdx, S(ScalarSpecifiedActions));
110       }
111 
112       // 2. Handle pointer types
113       for (auto PointerSpecifiedActions : AddressSpace2SpecifiedActions) {
114         std::sort(PointerSpecifiedActions.second.begin(),
115                   PointerSpecifiedActions.second.end());
116         checkPartialSizeAndActionsVector(PointerSpecifiedActions.second);
117         // For pointer types, we assume that there isn't a meaningfull way
118         // to change the number of bits used in the pointer.
119         setPointerAction(
120             Opcode, TypeIdx, PointerSpecifiedActions.first,
121             unsupportedForDifferentSizes(PointerSpecifiedActions.second));
122       }
123 
124       // 3. Handle vector types
125       SizeAndActionsVec ElementSizesSeen;
126       for (auto VectorSpecifiedActions : ElemSize2SpecifiedActions) {
127         std::sort(VectorSpecifiedActions.second.begin(),
128                   VectorSpecifiedActions.second.end());
129         const uint16_t ElementSize = VectorSpecifiedActions.first;
130         ElementSizesSeen.push_back({ElementSize, Legal});
131         checkPartialSizeAndActionsVector(VectorSpecifiedActions.second);
132         // For vector types, we assume that the best way to adapt the number
133         // of elements is to the next larger number of elements type for which
134         // the vector type is legal, unless there is no such type. In that case,
135         // legalize towards a vector type with a smaller number of elements.
136         SizeAndActionsVec NumElementsActions;
137         for (SizeAndAction BitsizeAndAction : VectorSpecifiedActions.second) {
138           assert(BitsizeAndAction.first % ElementSize == 0);
139           const uint16_t NumElements = BitsizeAndAction.first / ElementSize;
140           NumElementsActions.push_back({NumElements, BitsizeAndAction.second});
141         }
142         setVectorNumElementAction(
143             Opcode, TypeIdx, ElementSize,
144             moreToWiderTypesAndLessToWidest(NumElementsActions));
145       }
146       std::sort(ElementSizesSeen.begin(), ElementSizesSeen.end());
147       SizeChangeStrategy VectorElementSizeChangeStrategy =
148           &unsupportedForDifferentSizes;
149       if (TypeIdx < VectorElementSizeChangeStrategies[OpcodeIdx].size() &&
150           VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
151         VectorElementSizeChangeStrategy =
152             VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx];
153       setScalarInVectorAction(
154           Opcode, TypeIdx, VectorElementSizeChangeStrategy(ElementSizesSeen));
155     }
156   }
157 
158   TablesInitialized = true;
159 }
160 
161 // FIXME: inefficient implementation for now. Without ComputeValueVTs we're
162 // probably going to need specialized lookup structures for various types before
163 // we have any hope of doing well with something like <13 x i3>. Even the common
164 // cases should do better than what we have now.
165 std::pair<LegalizerInfo::LegalizeAction, LLT>
166 LegalizerInfo::getAction(const InstrAspect &Aspect) const {
167   assert(TablesInitialized && "backend forgot to call computeTables");
168   // These *have* to be implemented for now, they're the fundamental basis of
169   // how everything else is transformed.
170 
171   // FIXME: the long-term plan calls for expansion in terms of load/store (if
172   // they're not legal).
173   if (Aspect.Opcode == TargetOpcode::G_MERGE_VALUES ||
174       Aspect.Opcode == TargetOpcode::G_UNMERGE_VALUES)
175     return std::make_pair(Legal, Aspect.Type);
176 
177   if (Aspect.Type.isScalar() || Aspect.Type.isPointer())
178     return findScalarLegalAction(Aspect);
179   assert(Aspect.Type.isVector());
180   return findVectorLegalAction(Aspect);
181 }
182 
183 std::tuple<LegalizerInfo::LegalizeAction, unsigned, LLT>
184 LegalizerInfo::getAction(const MachineInstr &MI,
185                          const MachineRegisterInfo &MRI) const {
186   SmallBitVector SeenTypes(8);
187   const MCOperandInfo *OpInfo = MI.getDesc().OpInfo;
188   // FIXME: probably we'll need to cache the results here somehow?
189   for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) {
190     if (!OpInfo[i].isGenericType())
191       continue;
192 
193     // We must only record actions once for each TypeIdx; otherwise we'd
194     // try to legalize operands multiple times down the line.
195     unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
196     if (SeenTypes[TypeIdx])
197       continue;
198 
199     SeenTypes.set(TypeIdx);
200 
201     LLT Ty = MRI.getType(MI.getOperand(i).getReg());
202     auto Action = getAction({MI.getOpcode(), TypeIdx, Ty});
203     if (Action.first != Legal)
204       return std::make_tuple(Action.first, TypeIdx, Action.second);
205   }
206   return std::make_tuple(Legal, 0, LLT{});
207 }
208 
209 bool LegalizerInfo::isLegal(const MachineInstr &MI,
210                             const MachineRegisterInfo &MRI) const {
211   return std::get<0>(getAction(MI, MRI)) == Legal;
212 }
213 
214 bool LegalizerInfo::legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI,
215                                    MachineIRBuilder &MIRBuilder) const {
216   return false;
217 }
218 
219 LegalizerInfo::SizeAndActionsVec
220 LegalizerInfo::increaseToLargerTypesAndDecreaseToLargest(
221     const SizeAndActionsVec &v, LegalizeAction IncreaseAction,
222     LegalizeAction DecreaseAction) {
223   SizeAndActionsVec result;
224   unsigned LargestSizeSoFar = 0;
225   if (v.size() >= 1 && v[0].first != 1)
226     result.push_back({1, IncreaseAction});
227   for (size_t i = 0; i < v.size(); ++i) {
228     result.push_back(v[i]);
229     LargestSizeSoFar = v[i].first;
230     if (i + 1 < v.size() && v[i + 1].first != v[i].first + 1) {
231       result.push_back({LargestSizeSoFar + 1, IncreaseAction});
232       LargestSizeSoFar = v[i].first + 1;
233     }
234   }
235   result.push_back({LargestSizeSoFar + 1, DecreaseAction});
236   return result;
237 }
238 
239 LegalizerInfo::SizeAndActionsVec
240 LegalizerInfo::decreaseToSmallerTypesAndIncreaseToSmallest(
241     const SizeAndActionsVec &v, LegalizeAction DecreaseAction,
242     LegalizeAction IncreaseAction) {
243   SizeAndActionsVec result;
244   if (v.size() == 0 || v[0].first != 1)
245     result.push_back({1, IncreaseAction});
246   for (size_t i = 0; i < v.size(); ++i) {
247     result.push_back(v[i]);
248     if (i + 1 == v.size() || v[i + 1].first != v[i].first + 1) {
249       result.push_back({v[i].first + 1, DecreaseAction});
250     }
251   }
252   return result;
253 }
254 
255 LegalizerInfo::SizeAndAction
256 LegalizerInfo::findAction(const SizeAndActionsVec &Vec, const uint32_t Size) {
257   assert(Size >= 1);
258   // Find the last element in Vec that has a bitsize equal to or smaller than
259   // the requested bit size.
260   // That is the element just before the first element that is bigger than Size.
261   auto VecIt = std::upper_bound(
262       Vec.begin(), Vec.end(), Size,
263       [](const uint32_t Size, const SizeAndAction lhs) -> bool {
264         return Size < lhs.first;
265       });
266   assert(VecIt != Vec.begin() && "Does Vec not start with size 1?");
267   --VecIt;
268   int VecIdx = VecIt - Vec.begin();
269 
270   LegalizeAction Action = Vec[VecIdx].second;
271   switch (Action) {
272   case Legal:
273   case Lower:
274   case Libcall:
275   case Custom:
276     return {Size, Action};
277   case FewerElements:
278     // FIXME: is this special case still needed and correct?
279     // Special case for scalarization:
280     if (Vec == SizeAndActionsVec({{1, FewerElements}}))
281       return {1, FewerElements};
282     LLVM_FALLTHROUGH;
283   case NarrowScalar: {
284     // The following needs to be a loop, as for now, we do allow needing to
285     // go over "Unsupported" bit sizes before finding a legalizable bit size.
286     // e.g. (s8, WidenScalar), (s9, Unsupported), (s32, Legal). if Size==8,
287     // we need to iterate over s9, and then to s32 to return (s32, Legal).
288     // If we want to get rid of the below loop, we should have stronger asserts
289     // when building the SizeAndActionsVecs, probably not allowing
290     // "Unsupported" unless at the ends of the vector.
291     for (int i = VecIdx - 1; i >= 0; --i)
292       if (!needsLegalizingToDifferentSize(Vec[i].second) &&
293           Vec[i].second != Unsupported)
294         return {Vec[i].first, Action};
295     llvm_unreachable("");
296   }
297   case WidenScalar:
298   case MoreElements: {
299     // See above, the following needs to be a loop, at least for now.
300     for (std::size_t i = VecIdx + 1; i < Vec.size(); ++i)
301       if (!needsLegalizingToDifferentSize(Vec[i].second) &&
302           Vec[i].second != Unsupported)
303         return {Vec[i].first, Action};
304     llvm_unreachable("");
305   }
306   case Unsupported:
307     return {Size, Unsupported};
308   case NotFound:
309     llvm_unreachable("NotFound");
310   }
311   llvm_unreachable("Action has an unknown enum value");
312 }
313 
314 std::pair<LegalizerInfo::LegalizeAction, LLT>
315 LegalizerInfo::findScalarLegalAction(const InstrAspect &Aspect) const {
316   assert(Aspect.Type.isScalar() || Aspect.Type.isPointer());
317   if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
318     return {NotFound, LLT()};
319   const unsigned OpcodeIdx = Aspect.Opcode - FirstOp;
320   if (Aspect.Type.isPointer() &&
321       AddrSpace2PointerActions[OpcodeIdx].find(Aspect.Type.getAddressSpace()) ==
322           AddrSpace2PointerActions[OpcodeIdx].end()) {
323     return {NotFound, LLT()};
324   }
325   const SmallVector<SizeAndActionsVec, 1> &Actions =
326       Aspect.Type.isPointer()
327           ? AddrSpace2PointerActions[OpcodeIdx]
328                 .find(Aspect.Type.getAddressSpace())
329                 ->second
330           : ScalarActions[OpcodeIdx];
331   if (Aspect.Idx >= Actions.size())
332     return {NotFound, LLT()};
333   const SizeAndActionsVec &Vec = Actions[Aspect.Idx];
334   // FIXME: speed up this search, e.g. by using a results cache for repeated
335   // queries?
336   auto SizeAndAction = findAction(Vec, Aspect.Type.getSizeInBits());
337   return {SizeAndAction.second,
338           Aspect.Type.isScalar() ? LLT::scalar(SizeAndAction.first)
339                                  : LLT::pointer(Aspect.Type.getAddressSpace(),
340                                                 SizeAndAction.first)};
341 }
342 
343 std::pair<LegalizerInfo::LegalizeAction, LLT>
344 LegalizerInfo::findVectorLegalAction(const InstrAspect &Aspect) const {
345   assert(Aspect.Type.isVector());
346   // First legalize the vector element size, then legalize the number of
347   // lanes in the vector.
348   if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
349     return {NotFound, Aspect.Type};
350   const unsigned OpcodeIdx = Aspect.Opcode - FirstOp;
351   const unsigned TypeIdx = Aspect.Idx;
352   if (TypeIdx >= ScalarInVectorActions[OpcodeIdx].size())
353     return {NotFound, Aspect.Type};
354   const SizeAndActionsVec &ElemSizeVec =
355       ScalarInVectorActions[OpcodeIdx][TypeIdx];
356 
357   LLT IntermediateType;
358   auto ElementSizeAndAction =
359       findAction(ElemSizeVec, Aspect.Type.getScalarSizeInBits());
360   IntermediateType =
361       LLT::vector(Aspect.Type.getNumElements(), ElementSizeAndAction.first);
362   if (ElementSizeAndAction.second != Legal)
363     return {ElementSizeAndAction.second, IntermediateType};
364 
365   auto i = NumElements2Actions[OpcodeIdx].find(
366       IntermediateType.getScalarSizeInBits());
367   if (i == NumElements2Actions[OpcodeIdx].end()) {
368     return {NotFound, IntermediateType};
369   }
370   const SizeAndActionsVec &NumElementsVec = (*i).second[TypeIdx];
371   auto NumElementsAndAction =
372       findAction(NumElementsVec, IntermediateType.getNumElements());
373   return {NumElementsAndAction.second,
374           LLT::vector(NumElementsAndAction.first,
375                       IntermediateType.getScalarSizeInBits())};
376 }
377