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/Debug.h"
28 #include "llvm/Support/ErrorHandling.h"
29 #include "llvm/Support/LowLevelTypeImpl.h"
30 #include "llvm/Support/MathExtras.h"
31 #include <algorithm>
32 #include <map>
33 
34 using namespace llvm;
35 using namespace LegalizeActions;
36 
37 #define DEBUG_TYPE "legalizer-info"
38 
39 raw_ostream &LegalityQuery::print(raw_ostream &OS) const {
40   OS << Opcode << ", {";
41   for (const auto &Type : Types) {
42     OS << Type << ", ";
43   }
44   OS << "}";
45   return OS;
46 }
47 
48 LegalizeActionStep LegalizeRuleSet::apply(const LegalityQuery &Query) const {
49   DEBUG(dbgs() << "Applying legalizer ruleset to: "; Query.print(dbgs());
50         dbgs() << "\n");
51   if (Rules.empty()) {
52     DEBUG(dbgs() << ".. fallback to legacy rules (no rules defined)\n");
53     return {LegalizeAction::UseLegacyRules, 0, LLT{}};
54   }
55   for (const auto &Rule : Rules) {
56     if (Rule.match(Query)) {
57       DEBUG(dbgs() << ".. match\n");
58       std::pair<unsigned, LLT> Mutation = Rule.determineMutation(Query);
59       DEBUG(dbgs() << ".. .. " << (unsigned)Rule.getAction() << ", "
60                    << Mutation.first << ", " << Mutation.second << "\n");
61       assert(Query.Types[Mutation.first] != Mutation.second &&
62              "Simple loop detected");
63       return {Rule.getAction(), Mutation.first, Mutation.second};
64     } else
65       DEBUG(dbgs() << ".. no match\n");
66   }
67   DEBUG(dbgs() << ".. unsupported\n");
68   return {LegalizeAction::Unsupported, 0, LLT{}};
69 }
70 
71 LegalizerInfo::LegalizerInfo() : TablesInitialized(false) {
72   // Set defaults.
73   // FIXME: these two (G_ANYEXT and G_TRUNC?) can be legalized to the
74   // fundamental load/store Jakob proposed. Once loads & stores are supported.
75   setScalarAction(TargetOpcode::G_ANYEXT, 1, {{1, Legal}});
76   setScalarAction(TargetOpcode::G_ZEXT, 1, {{1, Legal}});
77   setScalarAction(TargetOpcode::G_SEXT, 1, {{1, Legal}});
78   setScalarAction(TargetOpcode::G_TRUNC, 0, {{1, Legal}});
79   setScalarAction(TargetOpcode::G_TRUNC, 1, {{1, Legal}});
80 
81   setScalarAction(TargetOpcode::G_INTRINSIC, 0, {{1, Legal}});
82   setScalarAction(TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS, 0, {{1, Legal}});
83 
84   setLegalizeScalarToDifferentSizeStrategy(
85       TargetOpcode::G_IMPLICIT_DEF, 0, narrowToSmallerAndUnsupportedIfTooSmall);
86   setLegalizeScalarToDifferentSizeStrategy(
87       TargetOpcode::G_ADD, 0, widenToLargerTypesAndNarrowToLargest);
88   setLegalizeScalarToDifferentSizeStrategy(
89       TargetOpcode::G_OR, 0, widenToLargerTypesAndNarrowToLargest);
90   setLegalizeScalarToDifferentSizeStrategy(
91       TargetOpcode::G_LOAD, 0, narrowToSmallerAndUnsupportedIfTooSmall);
92   setLegalizeScalarToDifferentSizeStrategy(
93       TargetOpcode::G_STORE, 0, narrowToSmallerAndUnsupportedIfTooSmall);
94 
95   setLegalizeScalarToDifferentSizeStrategy(
96       TargetOpcode::G_BRCOND, 0, widenToLargerTypesUnsupportedOtherwise);
97   setLegalizeScalarToDifferentSizeStrategy(
98       TargetOpcode::G_INSERT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
99   setLegalizeScalarToDifferentSizeStrategy(
100       TargetOpcode::G_EXTRACT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
101   setLegalizeScalarToDifferentSizeStrategy(
102       TargetOpcode::G_EXTRACT, 1, narrowToSmallerAndUnsupportedIfTooSmall);
103   setScalarAction(TargetOpcode::G_FNEG, 0, {{1, Lower}});
104 }
105 
106 void LegalizerInfo::computeTables() {
107   assert(TablesInitialized == false);
108 
109   for (unsigned OpcodeIdx = 0; OpcodeIdx <= LastOp - FirstOp; ++OpcodeIdx) {
110     const unsigned Opcode = FirstOp + OpcodeIdx;
111     for (unsigned TypeIdx = 0; TypeIdx != SpecifiedActions[OpcodeIdx].size();
112          ++TypeIdx) {
113       // 0. Collect information specified through the setAction API, i.e.
114       // for specific bit sizes.
115       // For scalar types:
116       SizeAndActionsVec ScalarSpecifiedActions;
117       // For pointer types:
118       std::map<uint16_t, SizeAndActionsVec> AddressSpace2SpecifiedActions;
119       // For vector types:
120       std::map<uint16_t, SizeAndActionsVec> ElemSize2SpecifiedActions;
121       for (auto LLT2Action : SpecifiedActions[OpcodeIdx][TypeIdx]) {
122         const LLT Type = LLT2Action.first;
123         const LegalizeAction Action = LLT2Action.second;
124 
125         auto SizeAction = std::make_pair(Type.getSizeInBits(), Action);
126         if (Type.isPointer())
127           AddressSpace2SpecifiedActions[Type.getAddressSpace()].push_back(
128               SizeAction);
129         else if (Type.isVector())
130           ElemSize2SpecifiedActions[Type.getElementType().getSizeInBits()]
131               .push_back(SizeAction);
132         else
133           ScalarSpecifiedActions.push_back(SizeAction);
134       }
135 
136       // 1. Handle scalar types
137       {
138         // Decide how to handle bit sizes for which no explicit specification
139         // was given.
140         SizeChangeStrategy S = &unsupportedForDifferentSizes;
141         if (TypeIdx < ScalarSizeChangeStrategies[OpcodeIdx].size() &&
142             ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
143           S = ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx];
144         std::sort(ScalarSpecifiedActions.begin(), ScalarSpecifiedActions.end());
145         checkPartialSizeAndActionsVector(ScalarSpecifiedActions);
146         setScalarAction(Opcode, TypeIdx, S(ScalarSpecifiedActions));
147       }
148 
149       // 2. Handle pointer types
150       for (auto PointerSpecifiedActions : AddressSpace2SpecifiedActions) {
151         std::sort(PointerSpecifiedActions.second.begin(),
152                   PointerSpecifiedActions.second.end());
153         checkPartialSizeAndActionsVector(PointerSpecifiedActions.second);
154         // For pointer types, we assume that there isn't a meaningfull way
155         // to change the number of bits used in the pointer.
156         setPointerAction(
157             Opcode, TypeIdx, PointerSpecifiedActions.first,
158             unsupportedForDifferentSizes(PointerSpecifiedActions.second));
159       }
160 
161       // 3. Handle vector types
162       SizeAndActionsVec ElementSizesSeen;
163       for (auto VectorSpecifiedActions : ElemSize2SpecifiedActions) {
164         std::sort(VectorSpecifiedActions.second.begin(),
165                   VectorSpecifiedActions.second.end());
166         const uint16_t ElementSize = VectorSpecifiedActions.first;
167         ElementSizesSeen.push_back({ElementSize, Legal});
168         checkPartialSizeAndActionsVector(VectorSpecifiedActions.second);
169         // For vector types, we assume that the best way to adapt the number
170         // of elements is to the next larger number of elements type for which
171         // the vector type is legal, unless there is no such type. In that case,
172         // legalize towards a vector type with a smaller number of elements.
173         SizeAndActionsVec NumElementsActions;
174         for (SizeAndAction BitsizeAndAction : VectorSpecifiedActions.second) {
175           assert(BitsizeAndAction.first % ElementSize == 0);
176           const uint16_t NumElements = BitsizeAndAction.first / ElementSize;
177           NumElementsActions.push_back({NumElements, BitsizeAndAction.second});
178         }
179         setVectorNumElementAction(
180             Opcode, TypeIdx, ElementSize,
181             moreToWiderTypesAndLessToWidest(NumElementsActions));
182       }
183       std::sort(ElementSizesSeen.begin(), ElementSizesSeen.end());
184       SizeChangeStrategy VectorElementSizeChangeStrategy =
185           &unsupportedForDifferentSizes;
186       if (TypeIdx < VectorElementSizeChangeStrategies[OpcodeIdx].size() &&
187           VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
188         VectorElementSizeChangeStrategy =
189             VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx];
190       setScalarInVectorAction(
191           Opcode, TypeIdx, VectorElementSizeChangeStrategy(ElementSizesSeen));
192     }
193   }
194 
195   TablesInitialized = true;
196 }
197 
198 // FIXME: inefficient implementation for now. Without ComputeValueVTs we're
199 // probably going to need specialized lookup structures for various types before
200 // we have any hope of doing well with something like <13 x i3>. Even the common
201 // cases should do better than what we have now.
202 std::pair<LegalizeAction, LLT>
203 LegalizerInfo::getAspectAction(const InstrAspect &Aspect) const {
204   assert(TablesInitialized && "backend forgot to call computeTables");
205   // These *have* to be implemented for now, they're the fundamental basis of
206   // how everything else is transformed.
207   if (Aspect.Type.isScalar() || Aspect.Type.isPointer())
208     return findScalarLegalAction(Aspect);
209   assert(Aspect.Type.isVector());
210   return findVectorLegalAction(Aspect);
211 }
212 
213 /// Helper function to get LLT for the given type index.
214 static LLT getTypeFromTypeIdx(const MachineInstr &MI,
215                               const MachineRegisterInfo &MRI, unsigned OpIdx,
216                               unsigned TypeIdx) {
217   assert(TypeIdx < MI.getNumOperands() && "Unexpected TypeIdx");
218   // G_UNMERGE_VALUES has variable number of operands, but there is only
219   // one source type and one destination type as all destinations must be the
220   // same type. So, get the last operand if TypeIdx == 1.
221   if (MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && TypeIdx == 1)
222     return MRI.getType(MI.getOperand(MI.getNumOperands() - 1).getReg());
223   return MRI.getType(MI.getOperand(OpIdx).getReg());
224 }
225 
226 unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
227   assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
228   return Opcode - FirstOp;
229 }
230 
231 unsigned LegalizerInfo::getActionDefinitionsIdx(unsigned Opcode) const {
232   unsigned OpcodeIdx = getOpcodeIdxForOpcode(Opcode);
233   if (unsigned Alias = RulesForOpcode[OpcodeIdx].getAlias()) {
234     DEBUG(dbgs() << ".. opcode " << Opcode << " is aliased to " << Alias
235                  << "\n");
236     OpcodeIdx = getOpcodeIdxForOpcode(Alias);
237     DEBUG(dbgs() << ".. opcode " << Alias << " is aliased to "
238                  << RulesForOpcode[OpcodeIdx].getAlias() << "\n");
239     assert(RulesForOpcode[OpcodeIdx].getAlias() == 0 && "Cannot chain aliases");
240   }
241 
242   return OpcodeIdx;
243 }
244 
245 const LegalizeRuleSet &
246 LegalizerInfo::getActionDefinitions(unsigned Opcode) const {
247   unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
248   return RulesForOpcode[OpcodeIdx];
249 }
250 
251 LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(unsigned Opcode) {
252   unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
253   auto &Result = RulesForOpcode[OpcodeIdx];
254   assert(!Result.isAliasedByAnother() && "Modifying this opcode will modify aliases");
255   return Result;
256 }
257 
258 LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(
259     std::initializer_list<unsigned> Opcodes) {
260   unsigned Representative = *Opcodes.begin();
261 
262   for (auto I = Opcodes.begin() + 1, E = Opcodes.end(); I != E; ++I)
263     aliasActionDefinitions(Representative, *I);
264 
265   auto &Return = getActionDefinitionsBuilder(Representative);
266   Return.setIsAliasedByAnother();
267   return Return;
268 }
269 
270 void LegalizerInfo::aliasActionDefinitions(unsigned OpcodeTo,
271                                            unsigned OpcodeFrom) {
272   assert(OpcodeTo != OpcodeFrom && "Cannot alias to self");
273   assert(OpcodeTo >= FirstOp && OpcodeTo <= LastOp && "Unsupported opcode");
274   const unsigned OpcodeFromIdx = getOpcodeIdxForOpcode(OpcodeFrom);
275   RulesForOpcode[OpcodeFromIdx].aliasTo(OpcodeTo);
276 }
277 
278 LegalizeActionStep
279 LegalizerInfo::getAction(const LegalityQuery &Query) const {
280   LegalizeActionStep Step = getActionDefinitions(Query.Opcode).apply(Query);
281   if (Step.Action != LegalizeAction::UseLegacyRules) {
282     return Step;
283   }
284 
285   for (unsigned i = 0; i < Query.Types.size(); ++i) {
286     auto Action = getAspectAction({Query.Opcode, i, Query.Types[i]});
287     if (Action.first != Legal) {
288       DEBUG(dbgs() << ".. (legacy) Type " << i << " Action="
289                    << (unsigned)Action.first << ", " << Action.second << "\n");
290       return {Action.first, i, Action.second};
291     } else
292       DEBUG(dbgs() << ".. (legacy) Type " << i << " Legal\n");
293   }
294   DEBUG(dbgs() << ".. (legacy) Legal\n");
295   return {Legal, 0, LLT{}};
296 }
297 
298 LegalizeActionStep
299 LegalizerInfo::getAction(const MachineInstr &MI,
300                          const MachineRegisterInfo &MRI) const {
301   SmallVector<LLT, 2> Types;
302   SmallBitVector SeenTypes(8);
303   const MCOperandInfo *OpInfo = MI.getDesc().OpInfo;
304   // FIXME: probably we'll need to cache the results here somehow?
305   for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) {
306     if (!OpInfo[i].isGenericType())
307       continue;
308 
309     // We must only record actions once for each TypeIdx; otherwise we'd
310     // try to legalize operands multiple times down the line.
311     unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
312     if (SeenTypes[TypeIdx])
313       continue;
314 
315     SeenTypes.set(TypeIdx);
316 
317     LLT Ty = getTypeFromTypeIdx(MI, MRI, i, TypeIdx);
318     Types.push_back(Ty);
319   }
320   return getAction({MI.getOpcode(), Types});
321 }
322 
323 bool LegalizerInfo::isLegal(const MachineInstr &MI,
324                             const MachineRegisterInfo &MRI) const {
325   return getAction(MI, MRI).Action == Legal;
326 }
327 
328 bool LegalizerInfo::legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI,
329                                    MachineIRBuilder &MIRBuilder) const {
330   return false;
331 }
332 
333 LegalizerInfo::SizeAndActionsVec
334 LegalizerInfo::increaseToLargerTypesAndDecreaseToLargest(
335     const SizeAndActionsVec &v, LegalizeAction IncreaseAction,
336     LegalizeAction DecreaseAction) {
337   SizeAndActionsVec result;
338   unsigned LargestSizeSoFar = 0;
339   if (v.size() >= 1 && v[0].first != 1)
340     result.push_back({1, IncreaseAction});
341   for (size_t i = 0; i < v.size(); ++i) {
342     result.push_back(v[i]);
343     LargestSizeSoFar = v[i].first;
344     if (i + 1 < v.size() && v[i + 1].first != v[i].first + 1) {
345       result.push_back({LargestSizeSoFar + 1, IncreaseAction});
346       LargestSizeSoFar = v[i].first + 1;
347     }
348   }
349   result.push_back({LargestSizeSoFar + 1, DecreaseAction});
350   return result;
351 }
352 
353 LegalizerInfo::SizeAndActionsVec
354 LegalizerInfo::decreaseToSmallerTypesAndIncreaseToSmallest(
355     const SizeAndActionsVec &v, LegalizeAction DecreaseAction,
356     LegalizeAction IncreaseAction) {
357   SizeAndActionsVec result;
358   if (v.size() == 0 || v[0].first != 1)
359     result.push_back({1, IncreaseAction});
360   for (size_t i = 0; i < v.size(); ++i) {
361     result.push_back(v[i]);
362     if (i + 1 == v.size() || v[i + 1].first != v[i].first + 1) {
363       result.push_back({v[i].first + 1, DecreaseAction});
364     }
365   }
366   return result;
367 }
368 
369 LegalizerInfo::SizeAndAction
370 LegalizerInfo::findAction(const SizeAndActionsVec &Vec, const uint32_t Size) {
371   assert(Size >= 1);
372   // Find the last element in Vec that has a bitsize equal to or smaller than
373   // the requested bit size.
374   // That is the element just before the first element that is bigger than Size.
375   auto VecIt = std::upper_bound(
376       Vec.begin(), Vec.end(), Size,
377       [](const uint32_t Size, const SizeAndAction lhs) -> bool {
378         return Size < lhs.first;
379       });
380   assert(VecIt != Vec.begin() && "Does Vec not start with size 1?");
381   --VecIt;
382   int VecIdx = VecIt - Vec.begin();
383 
384   LegalizeAction Action = Vec[VecIdx].second;
385   switch (Action) {
386   case Legal:
387   case Lower:
388   case Libcall:
389   case Custom:
390     return {Size, Action};
391   case FewerElements:
392     // FIXME: is this special case still needed and correct?
393     // Special case for scalarization:
394     if (Vec == SizeAndActionsVec({{1, FewerElements}}))
395       return {1, FewerElements};
396     LLVM_FALLTHROUGH;
397   case NarrowScalar: {
398     // The following needs to be a loop, as for now, we do allow needing to
399     // go over "Unsupported" bit sizes before finding a legalizable bit size.
400     // e.g. (s8, WidenScalar), (s9, Unsupported), (s32, Legal). if Size==8,
401     // we need to iterate over s9, and then to s32 to return (s32, Legal).
402     // If we want to get rid of the below loop, we should have stronger asserts
403     // when building the SizeAndActionsVecs, probably not allowing
404     // "Unsupported" unless at the ends of the vector.
405     for (int i = VecIdx - 1; i >= 0; --i)
406       if (!needsLegalizingToDifferentSize(Vec[i].second) &&
407           Vec[i].second != Unsupported)
408         return {Vec[i].first, Action};
409     llvm_unreachable("");
410   }
411   case WidenScalar:
412   case MoreElements: {
413     // See above, the following needs to be a loop, at least for now.
414     for (std::size_t i = VecIdx + 1; i < Vec.size(); ++i)
415       if (!needsLegalizingToDifferentSize(Vec[i].second) &&
416           Vec[i].second != Unsupported)
417         return {Vec[i].first, Action};
418     llvm_unreachable("");
419   }
420   case Unsupported:
421     return {Size, Unsupported};
422   case NotFound:
423   case UseLegacyRules:
424     llvm_unreachable("NotFound");
425   }
426   llvm_unreachable("Action has an unknown enum value");
427 }
428 
429 std::pair<LegalizeAction, LLT>
430 LegalizerInfo::findScalarLegalAction(const InstrAspect &Aspect) const {
431   assert(Aspect.Type.isScalar() || Aspect.Type.isPointer());
432   if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
433     return {NotFound, LLT()};
434   const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
435   if (Aspect.Type.isPointer() &&
436       AddrSpace2PointerActions[OpcodeIdx].find(Aspect.Type.getAddressSpace()) ==
437           AddrSpace2PointerActions[OpcodeIdx].end()) {
438     return {NotFound, LLT()};
439   }
440   const SmallVector<SizeAndActionsVec, 1> &Actions =
441       Aspect.Type.isPointer()
442           ? AddrSpace2PointerActions[OpcodeIdx]
443                 .find(Aspect.Type.getAddressSpace())
444                 ->second
445           : ScalarActions[OpcodeIdx];
446   if (Aspect.Idx >= Actions.size())
447     return {NotFound, LLT()};
448   const SizeAndActionsVec &Vec = Actions[Aspect.Idx];
449   // FIXME: speed up this search, e.g. by using a results cache for repeated
450   // queries?
451   auto SizeAndAction = findAction(Vec, Aspect.Type.getSizeInBits());
452   return {SizeAndAction.second,
453           Aspect.Type.isScalar() ? LLT::scalar(SizeAndAction.first)
454                                  : LLT::pointer(Aspect.Type.getAddressSpace(),
455                                                 SizeAndAction.first)};
456 }
457 
458 std::pair<LegalizeAction, LLT>
459 LegalizerInfo::findVectorLegalAction(const InstrAspect &Aspect) const {
460   assert(Aspect.Type.isVector());
461   // First legalize the vector element size, then legalize the number of
462   // lanes in the vector.
463   if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
464     return {NotFound, Aspect.Type};
465   const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
466   const unsigned TypeIdx = Aspect.Idx;
467   if (TypeIdx >= ScalarInVectorActions[OpcodeIdx].size())
468     return {NotFound, Aspect.Type};
469   const SizeAndActionsVec &ElemSizeVec =
470       ScalarInVectorActions[OpcodeIdx][TypeIdx];
471 
472   LLT IntermediateType;
473   auto ElementSizeAndAction =
474       findAction(ElemSizeVec, Aspect.Type.getScalarSizeInBits());
475   IntermediateType =
476       LLT::vector(Aspect.Type.getNumElements(), ElementSizeAndAction.first);
477   if (ElementSizeAndAction.second != Legal)
478     return {ElementSizeAndAction.second, IntermediateType};
479 
480   auto i = NumElements2Actions[OpcodeIdx].find(
481       IntermediateType.getScalarSizeInBits());
482   if (i == NumElements2Actions[OpcodeIdx].end()) {
483     return {NotFound, IntermediateType};
484   }
485   const SizeAndActionsVec &NumElementsVec = (*i).second[TypeIdx];
486   auto NumElementsAndAction =
487       findAction(NumElementsVec, IntermediateType.getNumElements());
488   return {NumElementsAndAction.second,
489           LLT::vector(NumElementsAndAction.first,
490                       IntermediateType.getScalarSizeInBits())};
491 }
492