LCOV - code coverage report
Current view: top level - lib/CodeGen/GlobalISel - LegalizerInfo.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 182 206 88.3 %
Date: 2018-10-20 13:21:21 Functions: 19 23 82.6 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13