• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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/MC/MCInstrInfo.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/ErrorHandling.h"
30 #include "llvm/Support/LowLevelTypeImpl.h"
31 #include "llvm/Support/MathExtras.h"
32 #include <algorithm>
33 #include <map>
34 
35 using namespace llvm;
36 using namespace LegalizeActions;
37 
38 #define DEBUG_TYPE "legalizer-info"
39 
40 cl::opt<bool> llvm::DisableGISelLegalityCheck(
41     "disable-gisel-legality-check",
42     cl::desc("Don't verify that MIR is fully legal between GlobalISel passes"),
43     cl::Hidden);
44 
print(raw_ostream & OS) const45 raw_ostream &LegalityQuery::print(raw_ostream &OS) const {
46   OS << Opcode << ", Tys={";
47   for (const auto &Type : Types) {
48     OS << Type << ", ";
49   }
50   OS << "}, Opcode=";
51 
52   OS << Opcode << ", MMOs={";
53   for (const auto &MMODescr : MMODescrs) {
54     OS << MMODescr.Size << ", ";
55   }
56   OS << "}";
57 
58   return OS;
59 }
60 
apply(const LegalityQuery & Query) const61 LegalizeActionStep LegalizeRuleSet::apply(const LegalityQuery &Query) const {
62   LLVM_DEBUG(dbgs() << "Applying legalizer ruleset to: "; Query.print(dbgs());
63              dbgs() << "\n");
64   if (Rules.empty()) {
65     LLVM_DEBUG(dbgs() << ".. fallback to legacy rules (no rules defined)\n");
66     return {LegalizeAction::UseLegacyRules, 0, LLT{}};
67   }
68   for (const auto &Rule : Rules) {
69     if (Rule.match(Query)) {
70       LLVM_DEBUG(dbgs() << ".. match\n");
71       std::pair<unsigned, LLT> Mutation = Rule.determineMutation(Query);
72       LLVM_DEBUG(dbgs() << ".. .. " << (unsigned)Rule.getAction() << ", "
73                         << Mutation.first << ", " << Mutation.second << "\n");
74       assert((Query.Types[Mutation.first] != Mutation.second ||
75               Rule.getAction() == Lower ||
76               Rule.getAction() == MoreElements ||
77               Rule.getAction() == FewerElements) &&
78              "Simple loop detected");
79       return {Rule.getAction(), Mutation.first, Mutation.second};
80     } else
81       LLVM_DEBUG(dbgs() << ".. no match\n");
82   }
83   LLVM_DEBUG(dbgs() << ".. unsupported\n");
84   return {LegalizeAction::Unsupported, 0, LLT{}};
85 }
86 
verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const87 bool LegalizeRuleSet::verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const {
88 #ifndef NDEBUG
89   if (Rules.empty()) {
90     LLVM_DEBUG(
91         dbgs() << ".. type index coverage check SKIPPED: no rules defined\n");
92     return true;
93   }
94   const int64_t FirstUncovered = TypeIdxsCovered.find_first_unset();
95   if (FirstUncovered < 0) {
96     LLVM_DEBUG(dbgs() << ".. type index coverage check SKIPPED:"
97                          " user-defined predicate detected\n");
98     return true;
99   }
100   const bool AllCovered = (FirstUncovered >= NumTypeIdxs);
101   LLVM_DEBUG(dbgs() << ".. the first uncovered type index: " << FirstUncovered
102                     << ", " << (AllCovered ? "OK" : "FAIL") << "\n");
103   return AllCovered;
104 #else
105   return true;
106 #endif
107 }
108 
LegalizerInfo()109 LegalizerInfo::LegalizerInfo() : TablesInitialized(false) {
110   // Set defaults.
111   // FIXME: these two (G_ANYEXT and G_TRUNC?) can be legalized to the
112   // fundamental load/store Jakob proposed. Once loads & stores are supported.
113   setScalarAction(TargetOpcode::G_ANYEXT, 1, {{1, Legal}});
114   setScalarAction(TargetOpcode::G_ZEXT, 1, {{1, Legal}});
115   setScalarAction(TargetOpcode::G_SEXT, 1, {{1, Legal}});
116   setScalarAction(TargetOpcode::G_TRUNC, 0, {{1, Legal}});
117   setScalarAction(TargetOpcode::G_TRUNC, 1, {{1, Legal}});
118 
119   setScalarAction(TargetOpcode::G_INTRINSIC, 0, {{1, Legal}});
120   setScalarAction(TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS, 0, {{1, Legal}});
121 
122   setLegalizeScalarToDifferentSizeStrategy(
123       TargetOpcode::G_IMPLICIT_DEF, 0, narrowToSmallerAndUnsupportedIfTooSmall);
124   setLegalizeScalarToDifferentSizeStrategy(
125       TargetOpcode::G_ADD, 0, widenToLargerTypesAndNarrowToLargest);
126   setLegalizeScalarToDifferentSizeStrategy(
127       TargetOpcode::G_OR, 0, widenToLargerTypesAndNarrowToLargest);
128   setLegalizeScalarToDifferentSizeStrategy(
129       TargetOpcode::G_LOAD, 0, narrowToSmallerAndUnsupportedIfTooSmall);
130   setLegalizeScalarToDifferentSizeStrategy(
131       TargetOpcode::G_STORE, 0, narrowToSmallerAndUnsupportedIfTooSmall);
132 
133   setLegalizeScalarToDifferentSizeStrategy(
134       TargetOpcode::G_BRCOND, 0, widenToLargerTypesUnsupportedOtherwise);
135   setLegalizeScalarToDifferentSizeStrategy(
136       TargetOpcode::G_INSERT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
137   setLegalizeScalarToDifferentSizeStrategy(
138       TargetOpcode::G_EXTRACT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
139   setLegalizeScalarToDifferentSizeStrategy(
140       TargetOpcode::G_EXTRACT, 1, narrowToSmallerAndUnsupportedIfTooSmall);
141   setScalarAction(TargetOpcode::G_FNEG, 0, {{1, Lower}});
142 }
143 
computeTables()144 void LegalizerInfo::computeTables() {
145   assert(TablesInitialized == false);
146 
147   for (unsigned OpcodeIdx = 0; OpcodeIdx <= LastOp - FirstOp; ++OpcodeIdx) {
148     const unsigned Opcode = FirstOp + OpcodeIdx;
149     for (unsigned TypeIdx = 0; TypeIdx != SpecifiedActions[OpcodeIdx].size();
150          ++TypeIdx) {
151       // 0. Collect information specified through the setAction API, i.e.
152       // for specific bit sizes.
153       // For scalar types:
154       SizeAndActionsVec ScalarSpecifiedActions;
155       // For pointer types:
156       std::map<uint16_t, SizeAndActionsVec> AddressSpace2SpecifiedActions;
157       // For vector types:
158       std::map<uint16_t, SizeAndActionsVec> ElemSize2SpecifiedActions;
159       for (auto LLT2Action : SpecifiedActions[OpcodeIdx][TypeIdx]) {
160         const LLT Type = LLT2Action.first;
161         const LegalizeAction Action = LLT2Action.second;
162 
163         auto SizeAction = std::make_pair(Type.getSizeInBits(), Action);
164         if (Type.isPointer())
165           AddressSpace2SpecifiedActions[Type.getAddressSpace()].push_back(
166               SizeAction);
167         else if (Type.isVector())
168           ElemSize2SpecifiedActions[Type.getElementType().getSizeInBits()]
169               .push_back(SizeAction);
170         else
171           ScalarSpecifiedActions.push_back(SizeAction);
172       }
173 
174       // 1. Handle scalar types
175       {
176         // Decide how to handle bit sizes for which no explicit specification
177         // was given.
178         SizeChangeStrategy S = &unsupportedForDifferentSizes;
179         if (TypeIdx < ScalarSizeChangeStrategies[OpcodeIdx].size() &&
180             ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
181           S = ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx];
182         llvm::sort(ScalarSpecifiedActions.begin(),
183                    ScalarSpecifiedActions.end());
184         checkPartialSizeAndActionsVector(ScalarSpecifiedActions);
185         setScalarAction(Opcode, TypeIdx, S(ScalarSpecifiedActions));
186       }
187 
188       // 2. Handle pointer types
189       for (auto PointerSpecifiedActions : AddressSpace2SpecifiedActions) {
190         llvm::sort(PointerSpecifiedActions.second.begin(),
191                    PointerSpecifiedActions.second.end());
192         checkPartialSizeAndActionsVector(PointerSpecifiedActions.second);
193         // For pointer types, we assume that there isn't a meaningfull way
194         // to change the number of bits used in the pointer.
195         setPointerAction(
196             Opcode, TypeIdx, PointerSpecifiedActions.first,
197             unsupportedForDifferentSizes(PointerSpecifiedActions.second));
198       }
199 
200       // 3. Handle vector types
201       SizeAndActionsVec ElementSizesSeen;
202       for (auto VectorSpecifiedActions : ElemSize2SpecifiedActions) {
203         llvm::sort(VectorSpecifiedActions.second.begin(),
204                    VectorSpecifiedActions.second.end());
205         const uint16_t ElementSize = VectorSpecifiedActions.first;
206         ElementSizesSeen.push_back({ElementSize, Legal});
207         checkPartialSizeAndActionsVector(VectorSpecifiedActions.second);
208         // For vector types, we assume that the best way to adapt the number
209         // of elements is to the next larger number of elements type for which
210         // the vector type is legal, unless there is no such type. In that case,
211         // legalize towards a vector type with a smaller number of elements.
212         SizeAndActionsVec NumElementsActions;
213         for (SizeAndAction BitsizeAndAction : VectorSpecifiedActions.second) {
214           assert(BitsizeAndAction.first % ElementSize == 0);
215           const uint16_t NumElements = BitsizeAndAction.first / ElementSize;
216           NumElementsActions.push_back({NumElements, BitsizeAndAction.second});
217         }
218         setVectorNumElementAction(
219             Opcode, TypeIdx, ElementSize,
220             moreToWiderTypesAndLessToWidest(NumElementsActions));
221       }
222       llvm::sort(ElementSizesSeen.begin(), ElementSizesSeen.end());
223       SizeChangeStrategy VectorElementSizeChangeStrategy =
224           &unsupportedForDifferentSizes;
225       if (TypeIdx < VectorElementSizeChangeStrategies[OpcodeIdx].size() &&
226           VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
227         VectorElementSizeChangeStrategy =
228             VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx];
229       setScalarInVectorAction(
230           Opcode, TypeIdx, VectorElementSizeChangeStrategy(ElementSizesSeen));
231     }
232   }
233 
234   TablesInitialized = true;
235 }
236 
237 // FIXME: inefficient implementation for now. Without ComputeValueVTs we're
238 // probably going to need specialized lookup structures for various types before
239 // we have any hope of doing well with something like <13 x i3>. Even the common
240 // cases should do better than what we have now.
241 std::pair<LegalizeAction, LLT>
getAspectAction(const InstrAspect & Aspect) const242 LegalizerInfo::getAspectAction(const InstrAspect &Aspect) const {
243   assert(TablesInitialized && "backend forgot to call computeTables");
244   // These *have* to be implemented for now, they're the fundamental basis of
245   // how everything else is transformed.
246   if (Aspect.Type.isScalar() || Aspect.Type.isPointer())
247     return findScalarLegalAction(Aspect);
248   assert(Aspect.Type.isVector());
249   return findVectorLegalAction(Aspect);
250 }
251 
252 /// Helper function to get LLT for the given type index.
getTypeFromTypeIdx(const MachineInstr & MI,const MachineRegisterInfo & MRI,unsigned OpIdx,unsigned TypeIdx)253 static LLT getTypeFromTypeIdx(const MachineInstr &MI,
254                               const MachineRegisterInfo &MRI, unsigned OpIdx,
255                               unsigned TypeIdx) {
256   assert(TypeIdx < MI.getNumOperands() && "Unexpected TypeIdx");
257   // G_UNMERGE_VALUES has variable number of operands, but there is only
258   // one source type and one destination type as all destinations must be the
259   // same type. So, get the last operand if TypeIdx == 1.
260   if (MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && TypeIdx == 1)
261     return MRI.getType(MI.getOperand(MI.getNumOperands() - 1).getReg());
262   return MRI.getType(MI.getOperand(OpIdx).getReg());
263 }
264 
getOpcodeIdxForOpcode(unsigned Opcode) const265 unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
266   assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
267   return Opcode - FirstOp;
268 }
269 
getActionDefinitionsIdx(unsigned Opcode) const270 unsigned LegalizerInfo::getActionDefinitionsIdx(unsigned Opcode) const {
271   unsigned OpcodeIdx = getOpcodeIdxForOpcode(Opcode);
272   if (unsigned Alias = RulesForOpcode[OpcodeIdx].getAlias()) {
273     LLVM_DEBUG(dbgs() << ".. opcode " << Opcode << " is aliased to " << Alias
274                       << "\n");
275     OpcodeIdx = getOpcodeIdxForOpcode(Alias);
276     LLVM_DEBUG(dbgs() << ".. opcode " << Alias << " is aliased to "
277                       << RulesForOpcode[OpcodeIdx].getAlias() << "\n");
278     assert(RulesForOpcode[OpcodeIdx].getAlias() == 0 && "Cannot chain aliases");
279   }
280 
281   return OpcodeIdx;
282 }
283 
284 const LegalizeRuleSet &
getActionDefinitions(unsigned Opcode) const285 LegalizerInfo::getActionDefinitions(unsigned Opcode) const {
286   unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
287   return RulesForOpcode[OpcodeIdx];
288 }
289 
getActionDefinitionsBuilder(unsigned Opcode)290 LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(unsigned Opcode) {
291   unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
292   auto &Result = RulesForOpcode[OpcodeIdx];
293   assert(!Result.isAliasedByAnother() && "Modifying this opcode will modify aliases");
294   return Result;
295 }
296 
getActionDefinitionsBuilder(std::initializer_list<unsigned> Opcodes)297 LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(
298     std::initializer_list<unsigned> Opcodes) {
299   unsigned Representative = *Opcodes.begin();
300 
301   assert(Opcodes.begin() != Opcodes.end() &&
302          Opcodes.begin() + 1 != Opcodes.end() &&
303          "Initializer list must have at least two opcodes");
304 
305   for (auto I = Opcodes.begin() + 1, E = Opcodes.end(); I != E; ++I)
306     aliasActionDefinitions(Representative, *I);
307 
308   auto &Return = getActionDefinitionsBuilder(Representative);
309   Return.setIsAliasedByAnother();
310   return Return;
311 }
312 
aliasActionDefinitions(unsigned OpcodeTo,unsigned OpcodeFrom)313 void LegalizerInfo::aliasActionDefinitions(unsigned OpcodeTo,
314                                            unsigned OpcodeFrom) {
315   assert(OpcodeTo != OpcodeFrom && "Cannot alias to self");
316   assert(OpcodeTo >= FirstOp && OpcodeTo <= LastOp && "Unsupported opcode");
317   const unsigned OpcodeFromIdx = getOpcodeIdxForOpcode(OpcodeFrom);
318   RulesForOpcode[OpcodeFromIdx].aliasTo(OpcodeTo);
319 }
320 
321 LegalizeActionStep
getAction(const LegalityQuery & Query) const322 LegalizerInfo::getAction(const LegalityQuery &Query) const {
323   LegalizeActionStep Step = getActionDefinitions(Query.Opcode).apply(Query);
324   if (Step.Action != LegalizeAction::UseLegacyRules) {
325     return Step;
326   }
327 
328   for (unsigned i = 0; i < Query.Types.size(); ++i) {
329     auto Action = getAspectAction({Query.Opcode, i, Query.Types[i]});
330     if (Action.first != Legal) {
331       LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i
332                         << " Action=" << (unsigned)Action.first << ", "
333                         << Action.second << "\n");
334       return {Action.first, i, Action.second};
335     } else
336       LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Legal\n");
337   }
338   LLVM_DEBUG(dbgs() << ".. (legacy) Legal\n");
339   return {Legal, 0, LLT{}};
340 }
341 
342 LegalizeActionStep
getAction(const MachineInstr & MI,const MachineRegisterInfo & MRI) const343 LegalizerInfo::getAction(const MachineInstr &MI,
344                          const MachineRegisterInfo &MRI) const {
345   SmallVector<LLT, 2> Types;
346   SmallBitVector SeenTypes(8);
347   const MCOperandInfo *OpInfo = MI.getDesc().OpInfo;
348   // FIXME: probably we'll need to cache the results here somehow?
349   for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) {
350     if (!OpInfo[i].isGenericType())
351       continue;
352 
353     // We must only record actions once for each TypeIdx; otherwise we'd
354     // try to legalize operands multiple times down the line.
355     unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
356     if (SeenTypes[TypeIdx])
357       continue;
358 
359     SeenTypes.set(TypeIdx);
360 
361     LLT Ty = getTypeFromTypeIdx(MI, MRI, i, TypeIdx);
362     Types.push_back(Ty);
363   }
364 
365   SmallVector<LegalityQuery::MemDesc, 2> MemDescrs;
366   for (const auto &MMO : MI.memoperands())
367     MemDescrs.push_back(
368         {MMO->getSize() /* in bytes */ * 8, MMO->getOrdering()});
369 
370   return getAction({MI.getOpcode(), Types, MemDescrs});
371 }
372 
isLegal(const MachineInstr & MI,const MachineRegisterInfo & MRI) const373 bool LegalizerInfo::isLegal(const MachineInstr &MI,
374                             const MachineRegisterInfo &MRI) const {
375   return getAction(MI, MRI).Action == Legal;
376 }
377 
legalizeCustom(MachineInstr & MI,MachineRegisterInfo & MRI,MachineIRBuilder & MIRBuilder) const378 bool LegalizerInfo::legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI,
379                                    MachineIRBuilder &MIRBuilder) const {
380   return false;
381 }
382 
383 LegalizerInfo::SizeAndActionsVec
increaseToLargerTypesAndDecreaseToLargest(const SizeAndActionsVec & v,LegalizeAction IncreaseAction,LegalizeAction DecreaseAction)384 LegalizerInfo::increaseToLargerTypesAndDecreaseToLargest(
385     const SizeAndActionsVec &v, LegalizeAction IncreaseAction,
386     LegalizeAction DecreaseAction) {
387   SizeAndActionsVec result;
388   unsigned LargestSizeSoFar = 0;
389   if (v.size() >= 1 && v[0].first != 1)
390     result.push_back({1, IncreaseAction});
391   for (size_t i = 0; i < v.size(); ++i) {
392     result.push_back(v[i]);
393     LargestSizeSoFar = v[i].first;
394     if (i + 1 < v.size() && v[i + 1].first != v[i].first + 1) {
395       result.push_back({LargestSizeSoFar + 1, IncreaseAction});
396       LargestSizeSoFar = v[i].first + 1;
397     }
398   }
399   result.push_back({LargestSizeSoFar + 1, DecreaseAction});
400   return result;
401 }
402 
403 LegalizerInfo::SizeAndActionsVec
decreaseToSmallerTypesAndIncreaseToSmallest(const SizeAndActionsVec & v,LegalizeAction DecreaseAction,LegalizeAction IncreaseAction)404 LegalizerInfo::decreaseToSmallerTypesAndIncreaseToSmallest(
405     const SizeAndActionsVec &v, LegalizeAction DecreaseAction,
406     LegalizeAction IncreaseAction) {
407   SizeAndActionsVec result;
408   if (v.size() == 0 || v[0].first != 1)
409     result.push_back({1, IncreaseAction});
410   for (size_t i = 0; i < v.size(); ++i) {
411     result.push_back(v[i]);
412     if (i + 1 == v.size() || v[i + 1].first != v[i].first + 1) {
413       result.push_back({v[i].first + 1, DecreaseAction});
414     }
415   }
416   return result;
417 }
418 
419 LegalizerInfo::SizeAndAction
findAction(const SizeAndActionsVec & Vec,const uint32_t Size)420 LegalizerInfo::findAction(const SizeAndActionsVec &Vec, const uint32_t Size) {
421   assert(Size >= 1);
422   // Find the last element in Vec that has a bitsize equal to or smaller than
423   // the requested bit size.
424   // That is the element just before the first element that is bigger than Size.
425   auto VecIt = std::upper_bound(
426       Vec.begin(), Vec.end(), Size,
427       [](const uint32_t Size, const SizeAndAction lhs) -> bool {
428         return Size < lhs.first;
429       });
430   assert(VecIt != Vec.begin() && "Does Vec not start with size 1?");
431   --VecIt;
432   int VecIdx = VecIt - Vec.begin();
433 
434   LegalizeAction Action = Vec[VecIdx].second;
435   switch (Action) {
436   case Legal:
437   case Lower:
438   case Libcall:
439   case Custom:
440     return {Size, Action};
441   case FewerElements:
442     // FIXME: is this special case still needed and correct?
443     // Special case for scalarization:
444     if (Vec == SizeAndActionsVec({{1, FewerElements}}))
445       return {1, FewerElements};
446     LLVM_FALLTHROUGH;
447   case NarrowScalar: {
448     // The following needs to be a loop, as for now, we do allow needing to
449     // go over "Unsupported" bit sizes before finding a legalizable bit size.
450     // e.g. (s8, WidenScalar), (s9, Unsupported), (s32, Legal). if Size==8,
451     // we need to iterate over s9, and then to s32 to return (s32, Legal).
452     // If we want to get rid of the below loop, we should have stronger asserts
453     // when building the SizeAndActionsVecs, probably not allowing
454     // "Unsupported" unless at the ends of the vector.
455     for (int i = VecIdx - 1; i >= 0; --i)
456       if (!needsLegalizingToDifferentSize(Vec[i].second) &&
457           Vec[i].second != Unsupported)
458         return {Vec[i].first, Action};
459     llvm_unreachable("");
460   }
461   case WidenScalar:
462   case MoreElements: {
463     // See above, the following needs to be a loop, at least for now.
464     for (std::size_t i = VecIdx + 1; i < Vec.size(); ++i)
465       if (!needsLegalizingToDifferentSize(Vec[i].second) &&
466           Vec[i].second != Unsupported)
467         return {Vec[i].first, Action};
468     llvm_unreachable("");
469   }
470   case Unsupported:
471     return {Size, Unsupported};
472   case NotFound:
473   case UseLegacyRules:
474     llvm_unreachable("NotFound");
475   }
476   llvm_unreachable("Action has an unknown enum value");
477 }
478 
479 std::pair<LegalizeAction, LLT>
findScalarLegalAction(const InstrAspect & Aspect) const480 LegalizerInfo::findScalarLegalAction(const InstrAspect &Aspect) const {
481   assert(Aspect.Type.isScalar() || Aspect.Type.isPointer());
482   if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
483     return {NotFound, LLT()};
484   const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
485   if (Aspect.Type.isPointer() &&
486       AddrSpace2PointerActions[OpcodeIdx].find(Aspect.Type.getAddressSpace()) ==
487           AddrSpace2PointerActions[OpcodeIdx].end()) {
488     return {NotFound, LLT()};
489   }
490   const SmallVector<SizeAndActionsVec, 1> &Actions =
491       Aspect.Type.isPointer()
492           ? AddrSpace2PointerActions[OpcodeIdx]
493                 .find(Aspect.Type.getAddressSpace())
494                 ->second
495           : ScalarActions[OpcodeIdx];
496   if (Aspect.Idx >= Actions.size())
497     return {NotFound, LLT()};
498   const SizeAndActionsVec &Vec = Actions[Aspect.Idx];
499   // FIXME: speed up this search, e.g. by using a results cache for repeated
500   // queries?
501   auto SizeAndAction = findAction(Vec, Aspect.Type.getSizeInBits());
502   return {SizeAndAction.second,
503           Aspect.Type.isScalar() ? LLT::scalar(SizeAndAction.first)
504                                  : LLT::pointer(Aspect.Type.getAddressSpace(),
505                                                 SizeAndAction.first)};
506 }
507 
508 std::pair<LegalizeAction, LLT>
findVectorLegalAction(const InstrAspect & Aspect) const509 LegalizerInfo::findVectorLegalAction(const InstrAspect &Aspect) const {
510   assert(Aspect.Type.isVector());
511   // First legalize the vector element size, then legalize the number of
512   // lanes in the vector.
513   if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
514     return {NotFound, Aspect.Type};
515   const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
516   const unsigned TypeIdx = Aspect.Idx;
517   if (TypeIdx >= ScalarInVectorActions[OpcodeIdx].size())
518     return {NotFound, Aspect.Type};
519   const SizeAndActionsVec &ElemSizeVec =
520       ScalarInVectorActions[OpcodeIdx][TypeIdx];
521 
522   LLT IntermediateType;
523   auto ElementSizeAndAction =
524       findAction(ElemSizeVec, Aspect.Type.getScalarSizeInBits());
525   IntermediateType =
526       LLT::vector(Aspect.Type.getNumElements(), ElementSizeAndAction.first);
527   if (ElementSizeAndAction.second != Legal)
528     return {ElementSizeAndAction.second, IntermediateType};
529 
530   auto i = NumElements2Actions[OpcodeIdx].find(
531       IntermediateType.getScalarSizeInBits());
532   if (i == NumElements2Actions[OpcodeIdx].end()) {
533     return {NotFound, IntermediateType};
534   }
535   const SizeAndActionsVec &NumElementsVec = (*i).second[TypeIdx];
536   auto NumElementsAndAction =
537       findAction(NumElementsVec, IntermediateType.getNumElements());
538   return {NumElementsAndAction.second,
539           LLT::vector(NumElementsAndAction.first,
540                       IntermediateType.getScalarSizeInBits())};
541 }
542 
543 /// \pre Type indices of every opcode form a dense set starting from 0.
verify(const MCInstrInfo & MII) const544 void LegalizerInfo::verify(const MCInstrInfo &MII) const {
545 #ifndef NDEBUG
546   std::vector<unsigned> FailedOpcodes;
547   for (unsigned Opcode = FirstOp; Opcode <= LastOp; ++Opcode) {
548     const MCInstrDesc &MCID = MII.get(Opcode);
549     const unsigned NumTypeIdxs = std::accumulate(
550         MCID.opInfo_begin(), MCID.opInfo_end(), 0U,
551         [](unsigned Acc, const MCOperandInfo &OpInfo) {
552           return OpInfo.isGenericType()
553                      ? std::max(OpInfo.getGenericTypeIndex() + 1U, Acc)
554                      : Acc;
555         });
556     LLVM_DEBUG(dbgs() << MII.getName(Opcode) << " (opcode " << Opcode
557                       << "): " << NumTypeIdxs << " type ind"
558                       << (NumTypeIdxs == 1 ? "ex" : "ices") << "\n");
559     const LegalizeRuleSet &RuleSet = getActionDefinitions(Opcode);
560     if (!RuleSet.verifyTypeIdxsCoverage(NumTypeIdxs))
561       FailedOpcodes.push_back(Opcode);
562   }
563   if (!FailedOpcodes.empty()) {
564     errs() << "The following opcodes have ill-defined legalization rules:";
565     for (unsigned Opcode : FailedOpcodes)
566       errs() << " " << MII.getName(Opcode);
567     errs() << "\n";
568 
569     report_fatal_error("ill-defined LegalizerInfo"
570                        ", try -debug-only=legalizer-info for details");
571   }
572 #endif
573 }
574 
575 #ifndef NDEBUG
576 // FIXME: This should be in the MachineVerifier, but it can't use the
577 // LegalizerInfo as it's currently in the separate GlobalISel library.
578 // Note that RegBankSelected property already checked in the verifier
579 // has the same layering problem, but we only use inline methods so
580 // end up not needing to link against the GlobalISel library.
machineFunctionIsIllegal(const MachineFunction & MF)581 const MachineInstr *llvm::machineFunctionIsIllegal(const MachineFunction &MF) {
582   if (const LegalizerInfo *MLI = MF.getSubtarget().getLegalizerInfo()) {
583     const MachineRegisterInfo &MRI = MF.getRegInfo();
584     for (const MachineBasicBlock &MBB : MF)
585       for (const MachineInstr &MI : MBB)
586         if (isPreISelGenericOpcode(MI.getOpcode()) && !MLI->isLegal(MI, MRI))
587 	  return &MI;
588   }
589   return nullptr;
590 }
591 #endif
592