lib/CodeGen/GlobalISel/LegalizerInfo.cpp

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