1 //===- lib/CodeGen/GlobalISel/LegalizerInfo.cpp - Legalizer ---------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Implement an interface to specify and query how an illegal operation on a
11 // given type should be expanded.
13 // Issues to be resolved:
15 // + Support weird types like i3, <7 x i3>, ...
16 // + Operations with more than one type (ICMP, CMPXCHG, intrinsics, ...)
18 //===----------------------------------------------------------------------===//
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"
34 LegalizerInfo::LegalizerInfo() : TablesInitialized(false) {
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}});
44 setScalarAction(TargetOpcode::G_INTRINSIC, 0, {{1, Legal}});
45 setScalarAction(TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS, 0, {{1, Legal}});
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);
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}});
69 void LegalizerInfo::computeTables() {
70 assert(TablesInitialized == false);
72 for (unsigned OpcodeIdx = 0; OpcodeIdx <= LastOp - FirstOp; ++OpcodeIdx) {
73 const unsigned Opcode = FirstOp + OpcodeIdx;
74 for (unsigned TypeIdx = 0; TypeIdx != SpecifiedActions[OpcodeIdx].size();
76 // 0. Collect information specified through the setAction API, i.e.
77 // for specific bit sizes.
79 SizeAndActionsVec ScalarSpecifiedActions;
81 std::map<uint16_t, SizeAndActionsVec> AddressSpace2SpecifiedActions;
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;
88 auto SizeAction = std::make_pair(Type.getSizeInBits(), Action);
90 AddressSpace2SpecifiedActions[Type.getAddressSpace()].push_back(
92 else if (Type.isVector())
93 ElemSize2SpecifiedActions[Type.getElementType().getSizeInBits()]
94 .push_back(SizeAction);
96 ScalarSpecifiedActions.push_back(SizeAction);
99 // 1. Handle scalar types
101 // Decide how to handle bit sizes for which no explicit specification
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));
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.
120 Opcode, TypeIdx, PointerSpecifiedActions.first,
121 unsupportedForDifferentSizes(PointerSpecifiedActions.second));
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});
142 setVectorNumElementAction(
143 Opcode, TypeIdx, ElementSize,
144 moreToWiderTypesAndLessToWidest(NumElementsActions));
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));
158 TablesInitialized = true;
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 if (Aspect.Type.isScalar() || Aspect.Type.isPointer())
171 return findScalarLegalAction(Aspect);
172 assert(Aspect.Type.isVector());
173 return findVectorLegalAction(Aspect);
176 /// Helper function to get LLT for the given type index.
177 static LLT getTypeFromTypeIdx(const MachineInstr &MI,
178 const MachineRegisterInfo &MRI, unsigned OpIdx,
180 assert(TypeIdx < MI.getNumOperands() && "Unexpected TypeIdx");
181 // G_UNMERGE_VALUES has variable number of operands, but there is only
182 // one source type and one destination type as all destinations must be the
183 // same type. So, get the last operand if TypeIdx == 1.
184 if (MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && TypeIdx == 1)
185 return MRI.getType(MI.getOperand(MI.getNumOperands() - 1).getReg());
186 return MRI.getType(MI.getOperand(OpIdx).getReg());
189 std::tuple<LegalizerInfo::LegalizeAction, unsigned, LLT>
190 LegalizerInfo::getAction(const MachineInstr &MI,
191 const MachineRegisterInfo &MRI) const {
192 SmallBitVector SeenTypes(8);
193 const MCOperandInfo *OpInfo = MI.getDesc().OpInfo;
194 // FIXME: probably we'll need to cache the results here somehow?
195 for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) {
196 if (!OpInfo[i].isGenericType())
199 // We must only record actions once for each TypeIdx; otherwise we'd
200 // try to legalize operands multiple times down the line.
201 unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
202 if (SeenTypes[TypeIdx])
205 SeenTypes.set(TypeIdx);
207 LLT Ty = getTypeFromTypeIdx(MI, MRI, i, TypeIdx);
208 auto Action = getAction({MI.getOpcode(), TypeIdx, Ty});
209 if (Action.first != Legal)
210 return std::make_tuple(Action.first, TypeIdx, Action.second);
212 return std::make_tuple(Legal, 0, LLT{});
215 bool LegalizerInfo::isLegal(const MachineInstr &MI,
216 const MachineRegisterInfo &MRI) const {
217 return std::get<0>(getAction(MI, MRI)) == Legal;
220 bool LegalizerInfo::legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI,
221 MachineIRBuilder &MIRBuilder) const {
225 LegalizerInfo::SizeAndActionsVec
226 LegalizerInfo::increaseToLargerTypesAndDecreaseToLargest(
227 const SizeAndActionsVec &v, LegalizeAction IncreaseAction,
228 LegalizeAction DecreaseAction) {
229 SizeAndActionsVec result;
230 unsigned LargestSizeSoFar = 0;
231 if (v.size() >= 1 && v[0].first != 1)
232 result.push_back({1, IncreaseAction});
233 for (size_t i = 0; i < v.size(); ++i) {
234 result.push_back(v[i]);
235 LargestSizeSoFar = v[i].first;
236 if (i + 1 < v.size() && v[i + 1].first != v[i].first + 1) {
237 result.push_back({LargestSizeSoFar + 1, IncreaseAction});
238 LargestSizeSoFar = v[i].first + 1;
241 result.push_back({LargestSizeSoFar + 1, DecreaseAction});
245 LegalizerInfo::SizeAndActionsVec
246 LegalizerInfo::decreaseToSmallerTypesAndIncreaseToSmallest(
247 const SizeAndActionsVec &v, LegalizeAction DecreaseAction,
248 LegalizeAction IncreaseAction) {
249 SizeAndActionsVec result;
250 if (v.size() == 0 || v[0].first != 1)
251 result.push_back({1, IncreaseAction});
252 for (size_t i = 0; i < v.size(); ++i) {
253 result.push_back(v[i]);
254 if (i + 1 == v.size() || v[i + 1].first != v[i].first + 1) {
255 result.push_back({v[i].first + 1, DecreaseAction});
261 LegalizerInfo::SizeAndAction
262 LegalizerInfo::findAction(const SizeAndActionsVec &Vec, const uint32_t Size) {
264 // Find the last element in Vec that has a bitsize equal to or smaller than
265 // the requested bit size.
266 // That is the element just before the first element that is bigger than Size.
267 auto VecIt = std::upper_bound(
268 Vec.begin(), Vec.end(), Size,
269 [](const uint32_t Size, const SizeAndAction lhs) -> bool {
270 return Size < lhs.first;
272 assert(VecIt != Vec.begin() && "Does Vec not start with size 1?");
274 int VecIdx = VecIt - Vec.begin();
276 LegalizeAction Action = Vec[VecIdx].second;
282 return {Size, Action};
284 // FIXME: is this special case still needed and correct?
285 // Special case for scalarization:
286 if (Vec == SizeAndActionsVec({{1, FewerElements}}))
287 return {1, FewerElements};
290 // The following needs to be a loop, as for now, we do allow needing to
291 // go over "Unsupported" bit sizes before finding a legalizable bit size.
292 // e.g. (s8, WidenScalar), (s9, Unsupported), (s32, Legal). if Size==8,
293 // we need to iterate over s9, and then to s32 to return (s32, Legal).
294 // If we want to get rid of the below loop, we should have stronger asserts
295 // when building the SizeAndActionsVecs, probably not allowing
296 // "Unsupported" unless at the ends of the vector.
297 for (int i = VecIdx - 1; i >= 0; --i)
298 if (!needsLegalizingToDifferentSize(Vec[i].second) &&
299 Vec[i].second != Unsupported)
300 return {Vec[i].first, Action};
301 llvm_unreachable("");
305 // See above, the following needs to be a loop, at least for now.
306 for (std::size_t i = VecIdx + 1; i < Vec.size(); ++i)
307 if (!needsLegalizingToDifferentSize(Vec[i].second) &&
308 Vec[i].second != Unsupported)
309 return {Vec[i].first, Action};
310 llvm_unreachable("");
313 return {Size, Unsupported};
315 llvm_unreachable("NotFound");
317 llvm_unreachable("Action has an unknown enum value");
320 std::pair<LegalizerInfo::LegalizeAction, LLT>
321 LegalizerInfo::findScalarLegalAction(const InstrAspect &Aspect) const {
322 assert(Aspect.Type.isScalar() || Aspect.Type.isPointer());
323 if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
324 return {NotFound, LLT()};
325 const unsigned OpcodeIdx = Aspect.Opcode - FirstOp;
326 if (Aspect.Type.isPointer() &&
327 AddrSpace2PointerActions[OpcodeIdx].find(Aspect.Type.getAddressSpace()) ==
328 AddrSpace2PointerActions[OpcodeIdx].end()) {
329 return {NotFound, LLT()};
331 const SmallVector<SizeAndActionsVec, 1> &Actions =
332 Aspect.Type.isPointer()
333 ? AddrSpace2PointerActions[OpcodeIdx]
334 .find(Aspect.Type.getAddressSpace())
336 : ScalarActions[OpcodeIdx];
337 if (Aspect.Idx >= Actions.size())
338 return {NotFound, LLT()};
339 const SizeAndActionsVec &Vec = Actions[Aspect.Idx];
340 // FIXME: speed up this search, e.g. by using a results cache for repeated
342 auto SizeAndAction = findAction(Vec, Aspect.Type.getSizeInBits());
343 return {SizeAndAction.second,
344 Aspect.Type.isScalar() ? LLT::scalar(SizeAndAction.first)
345 : LLT::pointer(Aspect.Type.getAddressSpace(),
346 SizeAndAction.first)};
349 std::pair<LegalizerInfo::LegalizeAction, LLT>
350 LegalizerInfo::findVectorLegalAction(const InstrAspect &Aspect) const {
351 assert(Aspect.Type.isVector());
352 // First legalize the vector element size, then legalize the number of
353 // lanes in the vector.
354 if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
355 return {NotFound, Aspect.Type};
356 const unsigned OpcodeIdx = Aspect.Opcode - FirstOp;
357 const unsigned TypeIdx = Aspect.Idx;
358 if (TypeIdx >= ScalarInVectorActions[OpcodeIdx].size())
359 return {NotFound, Aspect.Type};
360 const SizeAndActionsVec &ElemSizeVec =
361 ScalarInVectorActions[OpcodeIdx][TypeIdx];
363 LLT IntermediateType;
364 auto ElementSizeAndAction =
365 findAction(ElemSizeVec, Aspect.Type.getScalarSizeInBits());
367 LLT::vector(Aspect.Type.getNumElements(), ElementSizeAndAction.first);
368 if (ElementSizeAndAction.second != Legal)
369 return {ElementSizeAndAction.second, IntermediateType};
371 auto i = NumElements2Actions[OpcodeIdx].find(
372 IntermediateType.getScalarSizeInBits());
373 if (i == NumElements2Actions[OpcodeIdx].end()) {
374 return {NotFound, IntermediateType};
376 const SizeAndActionsVec &NumElementsVec = (*i).second[TypeIdx];
377 auto NumElementsAndAction =
378 findAction(NumElementsVec, IntermediateType.getNumElements());
379 return {NumElementsAndAction.second,
380 LLT::vector(NumElementsAndAction.first,
381 IntermediateType.getScalarSizeInBits())};