contrib/llvm/lib/CodeGen/GlobalISel/LegalizerInfo.cpp

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