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