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