1 //===- lib/CodeGen/GlobalISel/LegalizerInfo.cpp - Legalizer ---------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Implement an interface to specify and query how an illegal operation on a
10 // given type should be expanded.
11 //
12 // Issues to be resolved:
13 //   + Make it fast.
14 //   + Support weird types like i3, <7 x i3>, ...
15 //   + Operations with more than one type (ICMP, CMPXCHG, intrinsics, ...)
16 //
17 //===----------------------------------------------------------------------===//
18 
19 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
20 #include "llvm/ADT/SmallBitVector.h"
21 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.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 
45 raw_ostream &llvm::operator<<(raw_ostream &OS, LegalizeAction Action) {
46   switch (Action) {
47   case Legal:
48     OS << "Legal";
49     break;
50   case NarrowScalar:
51     OS << "NarrowScalar";
52     break;
53   case WidenScalar:
54     OS << "WidenScalar";
55     break;
56   case FewerElements:
57     OS << "FewerElements";
58     break;
59   case MoreElements:
60     OS << "MoreElements";
61     break;
62   case Bitcast:
63     OS << "Bitcast";
64     break;
65   case Lower:
66     OS << "Lower";
67     break;
68   case Libcall:
69     OS << "Libcall";
70     break;
71   case Custom:
72     OS << "Custom";
73     break;
74   case Unsupported:
75     OS << "Unsupported";
76     break;
77   case NotFound:
78     OS << "NotFound";
79     break;
80   case UseLegacyRules:
81     OS << "UseLegacyRules";
82     break;
83   }
84   return OS;
85 }
86 
87 raw_ostream &LegalityQuery::print(raw_ostream &OS) const {
88   OS << Opcode << ", Tys={";
89   for (const auto &Type : Types) {
90     OS << Type << ", ";
91   }
92   OS << "}, Opcode=";
93 
94   OS << Opcode << ", MMOs={";
95   for (const auto &MMODescr : MMODescrs) {
96     OS << MMODescr.SizeInBits << ", ";
97   }
98   OS << "}";
99 
100   return OS;
101 }
102 
103 #ifndef NDEBUG
104 // Make sure the rule won't (trivially) loop forever.
105 static bool hasNoSimpleLoops(const LegalizeRule &Rule, const LegalityQuery &Q,
106                              const std::pair<unsigned, LLT> &Mutation) {
107   switch (Rule.getAction()) {
108   case Custom:
109   case Lower:
110   case MoreElements:
111   case FewerElements:
112     break;
113   default:
114     return Q.Types[Mutation.first] != Mutation.second;
115   }
116   return true;
117 }
118 
119 // Make sure the returned mutation makes sense for the match type.
120 static bool mutationIsSane(const LegalizeRule &Rule,
121                            const LegalityQuery &Q,
122                            std::pair<unsigned, LLT> Mutation) {
123   // If the user wants a custom mutation, then we can't really say much about
124   // it. Return true, and trust that they're doing the right thing.
125   if (Rule.getAction() == Custom)
126     return true;
127 
128   const unsigned TypeIdx = Mutation.first;
129   const LLT OldTy = Q.Types[TypeIdx];
130   const LLT NewTy = Mutation.second;
131 
132   switch (Rule.getAction()) {
133   case FewerElements:
134     if (!OldTy.isVector())
135       return false;
136     LLVM_FALLTHROUGH;
137   case MoreElements: {
138     // MoreElements can go from scalar to vector.
139     const unsigned OldElts = OldTy.isVector() ? OldTy.getNumElements() : 1;
140     if (NewTy.isVector()) {
141       if (Rule.getAction() == FewerElements) {
142         // Make sure the element count really decreased.
143         if (NewTy.getNumElements() >= OldElts)
144           return false;
145       } else {
146         // Make sure the element count really increased.
147         if (NewTy.getNumElements() <= OldElts)
148           return false;
149       }
150     }
151 
152     // Make sure the element type didn't change.
153     return NewTy.getScalarType() == OldTy.getScalarType();
154   }
155   case NarrowScalar:
156   case WidenScalar: {
157     if (OldTy.isVector()) {
158       // Number of elements should not change.
159       if (!NewTy.isVector() || OldTy.getNumElements() != NewTy.getNumElements())
160         return false;
161     } else {
162       // Both types must be vectors
163       if (NewTy.isVector())
164         return false;
165     }
166 
167     if (Rule.getAction() == NarrowScalar)  {
168       // Make sure the size really decreased.
169       if (NewTy.getScalarSizeInBits() >= OldTy.getScalarSizeInBits())
170         return false;
171     } else {
172       // Make sure the size really increased.
173       if (NewTy.getScalarSizeInBits() <= OldTy.getScalarSizeInBits())
174         return false;
175     }
176 
177     return true;
178   }
179   case Bitcast: {
180     return OldTy != NewTy && OldTy.getSizeInBits() == NewTy.getSizeInBits();
181   }
182   default:
183     return true;
184   }
185 }
186 #endif
187 
188 LegalizeActionStep LegalizeRuleSet::apply(const LegalityQuery &Query) const {
189   LLVM_DEBUG(dbgs() << "Applying legalizer ruleset to: "; Query.print(dbgs());
190              dbgs() << "\n");
191   if (Rules.empty()) {
192     LLVM_DEBUG(dbgs() << ".. fallback to legacy rules (no rules defined)\n");
193     return {LegalizeAction::UseLegacyRules, 0, LLT{}};
194   }
195   for (const LegalizeRule &Rule : Rules) {
196     if (Rule.match(Query)) {
197       LLVM_DEBUG(dbgs() << ".. match\n");
198       std::pair<unsigned, LLT> Mutation = Rule.determineMutation(Query);
199       LLVM_DEBUG(dbgs() << ".. .. " << Rule.getAction() << ", "
200                         << Mutation.first << ", " << Mutation.second << "\n");
201       assert(mutationIsSane(Rule, Query, Mutation) &&
202              "legality mutation invalid for match");
203       assert(hasNoSimpleLoops(Rule, Query, Mutation) && "Simple loop detected");
204       return {Rule.getAction(), Mutation.first, Mutation.second};
205     } else
206       LLVM_DEBUG(dbgs() << ".. no match\n");
207   }
208   LLVM_DEBUG(dbgs() << ".. unsupported\n");
209   return {LegalizeAction::Unsupported, 0, LLT{}};
210 }
211 
212 bool LegalizeRuleSet::verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const {
213 #ifndef NDEBUG
214   if (Rules.empty()) {
215     LLVM_DEBUG(
216         dbgs() << ".. type index coverage check SKIPPED: no rules defined\n");
217     return true;
218   }
219   const int64_t FirstUncovered = TypeIdxsCovered.find_first_unset();
220   if (FirstUncovered < 0) {
221     LLVM_DEBUG(dbgs() << ".. type index coverage check SKIPPED:"
222                          " user-defined predicate detected\n");
223     return true;
224   }
225   const bool AllCovered = (FirstUncovered >= NumTypeIdxs);
226   if (NumTypeIdxs > 0)
227     LLVM_DEBUG(dbgs() << ".. the first uncovered type index: " << FirstUncovered
228                       << ", " << (AllCovered ? "OK" : "FAIL") << "\n");
229   return AllCovered;
230 #else
231   return true;
232 #endif
233 }
234 
235 bool LegalizeRuleSet::verifyImmIdxsCoverage(unsigned NumImmIdxs) const {
236 #ifndef NDEBUG
237   if (Rules.empty()) {
238     LLVM_DEBUG(
239         dbgs() << ".. imm index coverage check SKIPPED: no rules defined\n");
240     return true;
241   }
242   const int64_t FirstUncovered = ImmIdxsCovered.find_first_unset();
243   if (FirstUncovered < 0) {
244     LLVM_DEBUG(dbgs() << ".. imm index coverage check SKIPPED:"
245                          " user-defined predicate detected\n");
246     return true;
247   }
248   const bool AllCovered = (FirstUncovered >= NumImmIdxs);
249   LLVM_DEBUG(dbgs() << ".. the first uncovered imm index: " << FirstUncovered
250                     << ", " << (AllCovered ? "OK" : "FAIL") << "\n");
251   return AllCovered;
252 #else
253   return true;
254 #endif
255 }
256 
257 LegalizerInfo::LegalizerInfo() : TablesInitialized(false) {
258   // Set defaults.
259   // FIXME: these two (G_ANYEXT and G_TRUNC?) can be legalized to the
260   // fundamental load/store Jakob proposed. Once loads & stores are supported.
261   setScalarAction(TargetOpcode::G_ANYEXT, 1, {{1, Legal}});
262   setScalarAction(TargetOpcode::G_ZEXT, 1, {{1, Legal}});
263   setScalarAction(TargetOpcode::G_SEXT, 1, {{1, Legal}});
264   setScalarAction(TargetOpcode::G_TRUNC, 0, {{1, Legal}});
265   setScalarAction(TargetOpcode::G_TRUNC, 1, {{1, Legal}});
266 
267   setScalarAction(TargetOpcode::G_INTRINSIC, 0, {{1, Legal}});
268   setScalarAction(TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS, 0, {{1, Legal}});
269 
270   setLegalizeScalarToDifferentSizeStrategy(
271       TargetOpcode::G_IMPLICIT_DEF, 0, narrowToSmallerAndUnsupportedIfTooSmall);
272   setLegalizeScalarToDifferentSizeStrategy(
273       TargetOpcode::G_ADD, 0, widenToLargerTypesAndNarrowToLargest);
274   setLegalizeScalarToDifferentSizeStrategy(
275       TargetOpcode::G_OR, 0, widenToLargerTypesAndNarrowToLargest);
276   setLegalizeScalarToDifferentSizeStrategy(
277       TargetOpcode::G_LOAD, 0, narrowToSmallerAndUnsupportedIfTooSmall);
278   setLegalizeScalarToDifferentSizeStrategy(
279       TargetOpcode::G_STORE, 0, narrowToSmallerAndUnsupportedIfTooSmall);
280 
281   setLegalizeScalarToDifferentSizeStrategy(
282       TargetOpcode::G_BRCOND, 0, widenToLargerTypesUnsupportedOtherwise);
283   setLegalizeScalarToDifferentSizeStrategy(
284       TargetOpcode::G_INSERT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
285   setLegalizeScalarToDifferentSizeStrategy(
286       TargetOpcode::G_EXTRACT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
287   setLegalizeScalarToDifferentSizeStrategy(
288       TargetOpcode::G_EXTRACT, 1, narrowToSmallerAndUnsupportedIfTooSmall);
289   setScalarAction(TargetOpcode::G_FNEG, 0, {{1, Lower}});
290 }
291 
292 void LegalizerInfo::computeTables() {
293   assert(TablesInitialized == false);
294 
295   for (unsigned OpcodeIdx = 0; OpcodeIdx <= LastOp - FirstOp; ++OpcodeIdx) {
296     const unsigned Opcode = FirstOp + OpcodeIdx;
297     for (unsigned TypeIdx = 0; TypeIdx != SpecifiedActions[OpcodeIdx].size();
298          ++TypeIdx) {
299       // 0. Collect information specified through the setAction API, i.e.
300       // for specific bit sizes.
301       // For scalar types:
302       SizeAndActionsVec ScalarSpecifiedActions;
303       // For pointer types:
304       std::map<uint16_t, SizeAndActionsVec> AddressSpace2SpecifiedActions;
305       // For vector types:
306       std::map<uint16_t, SizeAndActionsVec> ElemSize2SpecifiedActions;
307       for (auto LLT2Action : SpecifiedActions[OpcodeIdx][TypeIdx]) {
308         const LLT Type = LLT2Action.first;
309         const LegalizeAction Action = LLT2Action.second;
310 
311         auto SizeAction = std::make_pair(Type.getSizeInBits(), Action);
312         if (Type.isPointer())
313           AddressSpace2SpecifiedActions[Type.getAddressSpace()].push_back(
314               SizeAction);
315         else if (Type.isVector())
316           ElemSize2SpecifiedActions[Type.getElementType().getSizeInBits()]
317               .push_back(SizeAction);
318         else
319           ScalarSpecifiedActions.push_back(SizeAction);
320       }
321 
322       // 1. Handle scalar types
323       {
324         // Decide how to handle bit sizes for which no explicit specification
325         // was given.
326         SizeChangeStrategy S = &unsupportedForDifferentSizes;
327         if (TypeIdx < ScalarSizeChangeStrategies[OpcodeIdx].size() &&
328             ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
329           S = ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx];
330         llvm::sort(ScalarSpecifiedActions);
331         checkPartialSizeAndActionsVector(ScalarSpecifiedActions);
332         setScalarAction(Opcode, TypeIdx, S(ScalarSpecifiedActions));
333       }
334 
335       // 2. Handle pointer types
336       for (auto PointerSpecifiedActions : AddressSpace2SpecifiedActions) {
337         llvm::sort(PointerSpecifiedActions.second);
338         checkPartialSizeAndActionsVector(PointerSpecifiedActions.second);
339         // For pointer types, we assume that there isn't a meaningfull way
340         // to change the number of bits used in the pointer.
341         setPointerAction(
342             Opcode, TypeIdx, PointerSpecifiedActions.first,
343             unsupportedForDifferentSizes(PointerSpecifiedActions.second));
344       }
345 
346       // 3. Handle vector types
347       SizeAndActionsVec ElementSizesSeen;
348       for (auto VectorSpecifiedActions : ElemSize2SpecifiedActions) {
349         llvm::sort(VectorSpecifiedActions.second);
350         const uint16_t ElementSize = VectorSpecifiedActions.first;
351         ElementSizesSeen.push_back({ElementSize, Legal});
352         checkPartialSizeAndActionsVector(VectorSpecifiedActions.second);
353         // For vector types, we assume that the best way to adapt the number
354         // of elements is to the next larger number of elements type for which
355         // the vector type is legal, unless there is no such type. In that case,
356         // legalize towards a vector type with a smaller number of elements.
357         SizeAndActionsVec NumElementsActions;
358         for (SizeAndAction BitsizeAndAction : VectorSpecifiedActions.second) {
359           assert(BitsizeAndAction.first % ElementSize == 0);
360           const uint16_t NumElements = BitsizeAndAction.first / ElementSize;
361           NumElementsActions.push_back({NumElements, BitsizeAndAction.second});
362         }
363         setVectorNumElementAction(
364             Opcode, TypeIdx, ElementSize,
365             moreToWiderTypesAndLessToWidest(NumElementsActions));
366       }
367       llvm::sort(ElementSizesSeen);
368       SizeChangeStrategy VectorElementSizeChangeStrategy =
369           &unsupportedForDifferentSizes;
370       if (TypeIdx < VectorElementSizeChangeStrategies[OpcodeIdx].size() &&
371           VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
372         VectorElementSizeChangeStrategy =
373             VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx];
374       setScalarInVectorAction(
375           Opcode, TypeIdx, VectorElementSizeChangeStrategy(ElementSizesSeen));
376     }
377   }
378 
379   TablesInitialized = true;
380 }
381 
382 // FIXME: inefficient implementation for now. Without ComputeValueVTs we're
383 // probably going to need specialized lookup structures for various types before
384 // we have any hope of doing well with something like <13 x i3>. Even the common
385 // cases should do better than what we have now.
386 std::pair<LegalizeAction, LLT>
387 LegalizerInfo::getAspectAction(const InstrAspect &Aspect) const {
388   assert(TablesInitialized && "backend forgot to call computeTables");
389   // These *have* to be implemented for now, they're the fundamental basis of
390   // how everything else is transformed.
391   if (Aspect.Type.isScalar() || Aspect.Type.isPointer())
392     return findScalarLegalAction(Aspect);
393   assert(Aspect.Type.isVector());
394   return findVectorLegalAction(Aspect);
395 }
396 
397 /// Helper function to get LLT for the given type index.
398 static LLT getTypeFromTypeIdx(const MachineInstr &MI,
399                               const MachineRegisterInfo &MRI, unsigned OpIdx,
400                               unsigned TypeIdx) {
401   assert(TypeIdx < MI.getNumOperands() && "Unexpected TypeIdx");
402   // G_UNMERGE_VALUES has variable number of operands, but there is only
403   // one source type and one destination type as all destinations must be the
404   // same type. So, get the last operand if TypeIdx == 1.
405   if (MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && TypeIdx == 1)
406     return MRI.getType(MI.getOperand(MI.getNumOperands() - 1).getReg());
407   return MRI.getType(MI.getOperand(OpIdx).getReg());
408 }
409 
410 unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
411   assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
412   return Opcode - FirstOp;
413 }
414 
415 unsigned LegalizerInfo::getActionDefinitionsIdx(unsigned Opcode) const {
416   unsigned OpcodeIdx = getOpcodeIdxForOpcode(Opcode);
417   if (unsigned Alias = RulesForOpcode[OpcodeIdx].getAlias()) {
418     LLVM_DEBUG(dbgs() << ".. opcode " << Opcode << " is aliased to " << Alias
419                       << "\n");
420     OpcodeIdx = getOpcodeIdxForOpcode(Alias);
421     assert(RulesForOpcode[OpcodeIdx].getAlias() == 0 && "Cannot chain aliases");
422   }
423 
424   return OpcodeIdx;
425 }
426 
427 const LegalizeRuleSet &
428 LegalizerInfo::getActionDefinitions(unsigned Opcode) const {
429   unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
430   return RulesForOpcode[OpcodeIdx];
431 }
432 
433 LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(unsigned Opcode) {
434   unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
435   auto &Result = RulesForOpcode[OpcodeIdx];
436   assert(!Result.isAliasedByAnother() && "Modifying this opcode will modify aliases");
437   return Result;
438 }
439 
440 LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(
441     std::initializer_list<unsigned> Opcodes) {
442   unsigned Representative = *Opcodes.begin();
443 
444   assert(!llvm::empty(Opcodes) && Opcodes.begin() + 1 != Opcodes.end() &&
445          "Initializer list must have at least two opcodes");
446 
447   for (auto I = Opcodes.begin() + 1, E = Opcodes.end(); I != E; ++I)
448     aliasActionDefinitions(Representative, *I);
449 
450   auto &Return = getActionDefinitionsBuilder(Representative);
451   Return.setIsAliasedByAnother();
452   return Return;
453 }
454 
455 void LegalizerInfo::aliasActionDefinitions(unsigned OpcodeTo,
456                                            unsigned OpcodeFrom) {
457   assert(OpcodeTo != OpcodeFrom && "Cannot alias to self");
458   assert(OpcodeTo >= FirstOp && OpcodeTo <= LastOp && "Unsupported opcode");
459   const unsigned OpcodeFromIdx = getOpcodeIdxForOpcode(OpcodeFrom);
460   RulesForOpcode[OpcodeFromIdx].aliasTo(OpcodeTo);
461 }
462 
463 LegalizeActionStep
464 LegalizerInfo::getAction(const LegalityQuery &Query) const {
465   LegalizeActionStep Step = getActionDefinitions(Query.Opcode).apply(Query);
466   if (Step.Action != LegalizeAction::UseLegacyRules) {
467     return Step;
468   }
469 
470   for (unsigned i = 0; i < Query.Types.size(); ++i) {
471     auto Action = getAspectAction({Query.Opcode, i, Query.Types[i]});
472     if (Action.first != Legal) {
473       LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Action="
474                         << Action.first << ", " << Action.second << "\n");
475       return {Action.first, i, Action.second};
476     } else
477       LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Legal\n");
478   }
479   LLVM_DEBUG(dbgs() << ".. (legacy) Legal\n");
480   return {Legal, 0, LLT{}};
481 }
482 
483 LegalizeActionStep
484 LegalizerInfo::getAction(const MachineInstr &MI,
485                          const MachineRegisterInfo &MRI) const {
486   SmallVector<LLT, 2> Types;
487   SmallBitVector SeenTypes(8);
488   const MCOperandInfo *OpInfo = MI.getDesc().OpInfo;
489   // FIXME: probably we'll need to cache the results here somehow?
490   for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) {
491     if (!OpInfo[i].isGenericType())
492       continue;
493 
494     // We must only record actions once for each TypeIdx; otherwise we'd
495     // try to legalize operands multiple times down the line.
496     unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
497     if (SeenTypes[TypeIdx])
498       continue;
499 
500     SeenTypes.set(TypeIdx);
501 
502     LLT Ty = getTypeFromTypeIdx(MI, MRI, i, TypeIdx);
503     Types.push_back(Ty);
504   }
505 
506   SmallVector<LegalityQuery::MemDesc, 2> MemDescrs;
507   for (const auto &MMO : MI.memoperands())
508     MemDescrs.push_back({8 * MMO->getSize() /* in bits */,
509                          8 * MMO->getAlign().value(), MMO->getOrdering()});
510 
511   return getAction({MI.getOpcode(), Types, MemDescrs});
512 }
513 
514 bool LegalizerInfo::isLegal(const MachineInstr &MI,
515                             const MachineRegisterInfo &MRI) const {
516   return getAction(MI, MRI).Action == Legal;
517 }
518 
519 bool LegalizerInfo::isLegalOrCustom(const MachineInstr &MI,
520                                     const MachineRegisterInfo &MRI) const {
521   auto Action = getAction(MI, MRI).Action;
522   // If the action is custom, it may not necessarily modify the instruction,
523   // so we have to assume it's legal.
524   return Action == Legal || Action == Custom;
525 }
526 
527 LegalizerInfo::SizeAndActionsVec
528 LegalizerInfo::increaseToLargerTypesAndDecreaseToLargest(
529     const SizeAndActionsVec &v, LegalizeAction IncreaseAction,
530     LegalizeAction DecreaseAction) {
531   SizeAndActionsVec result;
532   unsigned LargestSizeSoFar = 0;
533   if (v.size() >= 1 && v[0].first != 1)
534     result.push_back({1, IncreaseAction});
535   for (size_t i = 0; i < v.size(); ++i) {
536     result.push_back(v[i]);
537     LargestSizeSoFar = v[i].first;
538     if (i + 1 < v.size() && v[i + 1].first != v[i].first + 1) {
539       result.push_back({LargestSizeSoFar + 1, IncreaseAction});
540       LargestSizeSoFar = v[i].first + 1;
541     }
542   }
543   result.push_back({LargestSizeSoFar + 1, DecreaseAction});
544   return result;
545 }
546 
547 LegalizerInfo::SizeAndActionsVec
548 LegalizerInfo::decreaseToSmallerTypesAndIncreaseToSmallest(
549     const SizeAndActionsVec &v, LegalizeAction DecreaseAction,
550     LegalizeAction IncreaseAction) {
551   SizeAndActionsVec result;
552   if (v.size() == 0 || v[0].first != 1)
553     result.push_back({1, IncreaseAction});
554   for (size_t i = 0; i < v.size(); ++i) {
555     result.push_back(v[i]);
556     if (i + 1 == v.size() || v[i + 1].first != v[i].first + 1) {
557       result.push_back({v[i].first + 1, DecreaseAction});
558     }
559   }
560   return result;
561 }
562 
563 LegalizerInfo::SizeAndAction
564 LegalizerInfo::findAction(const SizeAndActionsVec &Vec, const uint32_t Size) {
565   assert(Size >= 1);
566   // Find the last element in Vec that has a bitsize equal to or smaller than
567   // the requested bit size.
568   // That is the element just before the first element that is bigger than Size.
569   auto It = partition_point(
570       Vec, [=](const SizeAndAction &A) { return A.first <= Size; });
571   assert(It != Vec.begin() && "Does Vec not start with size 1?");
572   int VecIdx = It - Vec.begin() - 1;
573 
574   LegalizeAction Action = Vec[VecIdx].second;
575   switch (Action) {
576   case Legal:
577   case Bitcast:
578   case Lower:
579   case Libcall:
580   case Custom:
581     return {Size, Action};
582   case FewerElements:
583     // FIXME: is this special case still needed and correct?
584     // Special case for scalarization:
585     if (Vec == SizeAndActionsVec({{1, FewerElements}}))
586       return {1, FewerElements};
587     LLVM_FALLTHROUGH;
588   case NarrowScalar: {
589     // The following needs to be a loop, as for now, we do allow needing to
590     // go over "Unsupported" bit sizes before finding a legalizable bit size.
591     // e.g. (s8, WidenScalar), (s9, Unsupported), (s32, Legal). if Size==8,
592     // we need to iterate over s9, and then to s32 to return (s32, Legal).
593     // If we want to get rid of the below loop, we should have stronger asserts
594     // when building the SizeAndActionsVecs, probably not allowing
595     // "Unsupported" unless at the ends of the vector.
596     for (int i = VecIdx - 1; i >= 0; --i)
597       if (!needsLegalizingToDifferentSize(Vec[i].second) &&
598           Vec[i].second != Unsupported)
599         return {Vec[i].first, Action};
600     llvm_unreachable("");
601   }
602   case WidenScalar:
603   case MoreElements: {
604     // See above, the following needs to be a loop, at least for now.
605     for (std::size_t i = VecIdx + 1; i < Vec.size(); ++i)
606       if (!needsLegalizingToDifferentSize(Vec[i].second) &&
607           Vec[i].second != Unsupported)
608         return {Vec[i].first, Action};
609     llvm_unreachable("");
610   }
611   case Unsupported:
612     return {Size, Unsupported};
613   case NotFound:
614   case UseLegacyRules:
615     llvm_unreachable("NotFound");
616   }
617   llvm_unreachable("Action has an unknown enum value");
618 }
619 
620 std::pair<LegalizeAction, LLT>
621 LegalizerInfo::findScalarLegalAction(const InstrAspect &Aspect) const {
622   assert(Aspect.Type.isScalar() || Aspect.Type.isPointer());
623   if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
624     return {NotFound, LLT()};
625   const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
626   if (Aspect.Type.isPointer() &&
627       AddrSpace2PointerActions[OpcodeIdx].find(Aspect.Type.getAddressSpace()) ==
628           AddrSpace2PointerActions[OpcodeIdx].end()) {
629     return {NotFound, LLT()};
630   }
631   const SmallVector<SizeAndActionsVec, 1> &Actions =
632       Aspect.Type.isPointer()
633           ? AddrSpace2PointerActions[OpcodeIdx]
634                 .find(Aspect.Type.getAddressSpace())
635                 ->second
636           : ScalarActions[OpcodeIdx];
637   if (Aspect.Idx >= Actions.size())
638     return {NotFound, LLT()};
639   const SizeAndActionsVec &Vec = Actions[Aspect.Idx];
640   // FIXME: speed up this search, e.g. by using a results cache for repeated
641   // queries?
642   auto SizeAndAction = findAction(Vec, Aspect.Type.getSizeInBits());
643   return {SizeAndAction.second,
644           Aspect.Type.isScalar() ? LLT::scalar(SizeAndAction.first)
645                                  : LLT::pointer(Aspect.Type.getAddressSpace(),
646                                                 SizeAndAction.first)};
647 }
648 
649 std::pair<LegalizeAction, LLT>
650 LegalizerInfo::findVectorLegalAction(const InstrAspect &Aspect) const {
651   assert(Aspect.Type.isVector());
652   // First legalize the vector element size, then legalize the number of
653   // lanes in the vector.
654   if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
655     return {NotFound, Aspect.Type};
656   const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
657   const unsigned TypeIdx = Aspect.Idx;
658   if (TypeIdx >= ScalarInVectorActions[OpcodeIdx].size())
659     return {NotFound, Aspect.Type};
660   const SizeAndActionsVec &ElemSizeVec =
661       ScalarInVectorActions[OpcodeIdx][TypeIdx];
662 
663   LLT IntermediateType;
664   auto ElementSizeAndAction =
665       findAction(ElemSizeVec, Aspect.Type.getScalarSizeInBits());
666   IntermediateType =
667       LLT::vector(Aspect.Type.getNumElements(), ElementSizeAndAction.first);
668   if (ElementSizeAndAction.second != Legal)
669     return {ElementSizeAndAction.second, IntermediateType};
670 
671   auto i = NumElements2Actions[OpcodeIdx].find(
672       IntermediateType.getScalarSizeInBits());
673   if (i == NumElements2Actions[OpcodeIdx].end()) {
674     return {NotFound, IntermediateType};
675   }
676   const SizeAndActionsVec &NumElementsVec = (*i).second[TypeIdx];
677   auto NumElementsAndAction =
678       findAction(NumElementsVec, IntermediateType.getNumElements());
679   return {NumElementsAndAction.second,
680           LLT::vector(NumElementsAndAction.first,
681                       IntermediateType.getScalarSizeInBits())};
682 }
683 
684 unsigned LegalizerInfo::getExtOpcodeForWideningConstant(LLT SmallTy) const {
685   return SmallTy.isByteSized() ? TargetOpcode::G_SEXT : TargetOpcode::G_ZEXT;
686 }
687 
688 /// \pre Type indices of every opcode form a dense set starting from 0.
689 void LegalizerInfo::verify(const MCInstrInfo &MII) const {
690 #ifndef NDEBUG
691   std::vector<unsigned> FailedOpcodes;
692   for (unsigned Opcode = FirstOp; Opcode <= LastOp; ++Opcode) {
693     const MCInstrDesc &MCID = MII.get(Opcode);
694     const unsigned NumTypeIdxs = std::accumulate(
695         MCID.opInfo_begin(), MCID.opInfo_end(), 0U,
696         [](unsigned Acc, const MCOperandInfo &OpInfo) {
697           return OpInfo.isGenericType()
698                      ? std::max(OpInfo.getGenericTypeIndex() + 1U, Acc)
699                      : Acc;
700         });
701     const unsigned NumImmIdxs = std::accumulate(
702         MCID.opInfo_begin(), MCID.opInfo_end(), 0U,
703         [](unsigned Acc, const MCOperandInfo &OpInfo) {
704           return OpInfo.isGenericImm()
705                      ? std::max(OpInfo.getGenericImmIndex() + 1U, Acc)
706                      : Acc;
707         });
708     LLVM_DEBUG(dbgs() << MII.getName(Opcode) << " (opcode " << Opcode
709                       << "): " << NumTypeIdxs << " type ind"
710                       << (NumTypeIdxs == 1 ? "ex" : "ices") << ", "
711                       << NumImmIdxs << " imm ind"
712                       << (NumImmIdxs == 1 ? "ex" : "ices") << "\n");
713     const LegalizeRuleSet &RuleSet = getActionDefinitions(Opcode);
714     if (!RuleSet.verifyTypeIdxsCoverage(NumTypeIdxs))
715       FailedOpcodes.push_back(Opcode);
716     else if (!RuleSet.verifyImmIdxsCoverage(NumImmIdxs))
717       FailedOpcodes.push_back(Opcode);
718   }
719   if (!FailedOpcodes.empty()) {
720     errs() << "The following opcodes have ill-defined legalization rules:";
721     for (unsigned Opcode : FailedOpcodes)
722       errs() << " " << MII.getName(Opcode);
723     errs() << "\n";
724 
725     report_fatal_error("ill-defined LegalizerInfo"
726                        ", try -debug-only=legalizer-info for details");
727   }
728 #endif
729 }
730 
731 #ifndef NDEBUG
732 // FIXME: This should be in the MachineVerifier, but it can't use the
733 // LegalizerInfo as it's currently in the separate GlobalISel library.
734 // Note that RegBankSelected property already checked in the verifier
735 // has the same layering problem, but we only use inline methods so
736 // end up not needing to link against the GlobalISel library.
737 const MachineInstr *llvm::machineFunctionIsIllegal(const MachineFunction &MF) {
738   if (const LegalizerInfo *MLI = MF.getSubtarget().getLegalizerInfo()) {
739     const MachineRegisterInfo &MRI = MF.getRegInfo();
740     for (const MachineBasicBlock &MBB : MF)
741       for (const MachineInstr &MI : MBB)
742         if (isPreISelGenericOpcode(MI.getOpcode()) &&
743             !MLI->isLegalOrCustom(MI, MRI))
744           return &MI;
745   }
746   return nullptr;
747 }
748 #endif
749