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