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