llvm/lib/CodeGen/GlobalISel/LegacyLegalizerInfo.cpp

   1 //===- lib/CodeGen/GlobalISel/LegacyLegalizerInfo.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/LegacyLegalizerInfo.h"
  20 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
  21 #include <map>
  22
  23 using namespace llvm;
  24 using namespace LegacyLegalizeActions;
  25
  26 #define DEBUG_TYPE "legalizer-info"
  27
  28 raw_ostream &llvm::operator<<(raw_ostream &OS, LegacyLegalizeAction Action) {
  29   switch (Action) {
  30   case Legal:
  31     OS << "Legal";
  32     break;
  33   case NarrowScalar:
  34     OS << "NarrowScalar";
  35     break;
  36   case WidenScalar:
  37     OS << "WidenScalar";
  38     break;
  39   case FewerElements:
  40     OS << "FewerElements";
  41     break;
  42   case MoreElements:
  43     OS << "MoreElements";
  44     break;
  45   case Bitcast:
  46     OS << "Bitcast";
  47     break;
  48   case Lower:
  49     OS << "Lower";
  50     break;
  51   case Libcall:
  52     OS << "Libcall";
  53     break;
  54   case Custom:
  55     OS << "Custom";
  56     break;
  57   case Unsupported:
  58     OS << "Unsupported";
  59     break;
  60   case NotFound:
  61     OS << "NotFound";
  62     break;
  63   }
  64   return OS;
  65 }
  66
  67 LegacyLegalizerInfo::LegacyLegalizerInfo() {
  68   // Set defaults.
  69   // FIXME: these two (G_ANYEXT and G_TRUNC?) can be legalized to the
  70   // fundamental load/store Jakob proposed. Once loads & stores are supported.
  71   setScalarAction(TargetOpcode::G_ANYEXT, 1, {{1, Legal}});
  72   setScalarAction(TargetOpcode::G_ZEXT, 1, {{1, Legal}});
  73   setScalarAction(TargetOpcode::G_SEXT, 1, {{1, Legal}});
  74   setScalarAction(TargetOpcode::G_TRUNC, 0, {{1, Legal}});
  75   setScalarAction(TargetOpcode::G_TRUNC, 1, {{1, Legal}});
  76
  77   setScalarAction(TargetOpcode::G_INTRINSIC, 0, {{1, Legal}});
  78   setScalarAction(TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS, 0, {{1, Legal}});
  79   setScalarAction(TargetOpcode::G_INTRINSIC_CONVERGENT, 0, {{1, Legal}});
  80   setScalarAction(TargetOpcode::G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS, 0,
  81                   {{1, Legal}});
  82
  83   setLegalizeScalarToDifferentSizeStrategy(
  84       TargetOpcode::G_IMPLICIT_DEF, 0, narrowToSmallerAndUnsupportedIfTooSmall);
  85   setLegalizeScalarToDifferentSizeStrategy(
  86       TargetOpcode::G_ADD, 0, widenToLargerTypesAndNarrowToLargest);
  87   setLegalizeScalarToDifferentSizeStrategy(
  88       TargetOpcode::G_OR, 0, widenToLargerTypesAndNarrowToLargest);
  89   setLegalizeScalarToDifferentSizeStrategy(
  90       TargetOpcode::G_LOAD, 0, narrowToSmallerAndUnsupportedIfTooSmall);
  91   setLegalizeScalarToDifferentSizeStrategy(
  92       TargetOpcode::G_STORE, 0, narrowToSmallerAndUnsupportedIfTooSmall);
  93
  94   setLegalizeScalarToDifferentSizeStrategy(
  95       TargetOpcode::G_BRCOND, 0, widenToLargerTypesUnsupportedOtherwise);
  96   setLegalizeScalarToDifferentSizeStrategy(
  97       TargetOpcode::G_INSERT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
  98   setLegalizeScalarToDifferentSizeStrategy(
  99       TargetOpcode::G_EXTRACT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
 100   setLegalizeScalarToDifferentSizeStrategy(
 101       TargetOpcode::G_EXTRACT, 1, narrowToSmallerAndUnsupportedIfTooSmall);
 102   setScalarAction(TargetOpcode::G_FNEG, 0, {{1, Lower}});
 103 }
 104
 105 void LegacyLegalizerInfo::computeTables() {
 106   assert(TablesInitialized == false);
 107
 108   for (unsigned OpcodeIdx = 0; OpcodeIdx <= LastOp - FirstOp; ++OpcodeIdx) {
 109     const unsigned Opcode = FirstOp + OpcodeIdx;
 110     for (unsigned TypeIdx = 0; TypeIdx != SpecifiedActions[OpcodeIdx].size();
 111          ++TypeIdx) {
 112       // 0. Collect information specified through the setAction API, i.e.
 113       // for specific bit sizes.
 114       // For scalar types:
 115       SizeAndActionsVec ScalarSpecifiedActions;
 116       // For pointer types:
 117       std::map<uint16_t, SizeAndActionsVec> AddressSpace2SpecifiedActions;
 118       // For vector types:
 119       std::map<uint16_t, SizeAndActionsVec> ElemSize2SpecifiedActions;
 120       for (auto LLT2Action : SpecifiedActions[OpcodeIdx][TypeIdx]) {
 121         const LLT Type = LLT2Action.first;
 122         const LegacyLegalizeAction Action = LLT2Action.second;
 123
 124         auto SizeAction = std::make_pair(Type.getSizeInBits(), Action);
 125         if (Type.isPointer())
 126           AddressSpace2SpecifiedActions[Type.getAddressSpace()].push_back(
 127               SizeAction);
 128         else if (Type.isVector())
 129           ElemSize2SpecifiedActions[Type.getElementType().getSizeInBits()]
 130               .push_back(SizeAction);
 131         else
 132           ScalarSpecifiedActions.push_back(SizeAction);
 133       }
 134
 135       // 1. Handle scalar types
 136       {
 137         // Decide how to handle bit sizes for which no explicit specification
 138         // was given.
 139         SizeChangeStrategy S = &unsupportedForDifferentSizes;
 140         if (TypeIdx < ScalarSizeChangeStrategies[OpcodeIdx].size() &&
 141             ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
 142           S = ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx];
 143         llvm::sort(ScalarSpecifiedActions);
 144         checkPartialSizeAndActionsVector(ScalarSpecifiedActions);
 145         setScalarAction(Opcode, TypeIdx, S(ScalarSpecifiedActions));
 146       }
 147
 148       // 2. Handle pointer types
 149       for (auto PointerSpecifiedActions : AddressSpace2SpecifiedActions) {
 150         llvm::sort(PointerSpecifiedActions.second);
 151         checkPartialSizeAndActionsVector(PointerSpecifiedActions.second);
 152         // For pointer types, we assume that there isn't a meaningfull way
 153         // to change the number of bits used in the pointer.
 154         setPointerAction(
 155             Opcode, TypeIdx, PointerSpecifiedActions.first,
 156             unsupportedForDifferentSizes(PointerSpecifiedActions.second));
 157       }
 158
 159       // 3. Handle vector types
 160       SizeAndActionsVec ElementSizesSeen;
 161       for (auto VectorSpecifiedActions : ElemSize2SpecifiedActions) {
 162         llvm::sort(VectorSpecifiedActions.second);
 163         const uint16_t ElementSize = VectorSpecifiedActions.first;
 164         ElementSizesSeen.push_back({ElementSize, Legal});
 165         checkPartialSizeAndActionsVector(VectorSpecifiedActions.second);
 166         // For vector types, we assume that the best way to adapt the number
 167         // of elements is to the next larger number of elements type for which
 168         // the vector type is legal, unless there is no such type. In that case,
 169         // legalize towards a vector type with a smaller number of elements.
 170         SizeAndActionsVec NumElementsActions;
 171         for (SizeAndAction BitsizeAndAction : VectorSpecifiedActions.second) {
 172           assert(BitsizeAndAction.first % ElementSize == 0);
 173           const uint16_t NumElements = BitsizeAndAction.first / ElementSize;
 174           NumElementsActions.push_back({NumElements, BitsizeAndAction.second});
 175         }
 176         setVectorNumElementAction(
 177             Opcode, TypeIdx, ElementSize,
 178             moreToWiderTypesAndLessToWidest(NumElementsActions));
 179       }
 180       llvm::sort(ElementSizesSeen);
 181       SizeChangeStrategy VectorElementSizeChangeStrategy =
 182           &unsupportedForDifferentSizes;
 183       if (TypeIdx < VectorElementSizeChangeStrategies[OpcodeIdx].size() &&
 184           VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
 185         VectorElementSizeChangeStrategy =
 186             VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx];
 187       setScalarInVectorAction(
 188           Opcode, TypeIdx, VectorElementSizeChangeStrategy(ElementSizesSeen));
 189     }
 190   }
 191
 192   TablesInitialized = true;
 193 }
 194
 195 // FIXME: inefficient implementation for now. Without ComputeValueVTs we're
 196 // probably going to need specialized lookup structures for various types before
 197 // we have any hope of doing well with something like <13 x i3>. Even the common
 198 // cases should do better than what we have now.
 199 std::pair<LegacyLegalizeAction, LLT>
 200 LegacyLegalizerInfo::getAspectAction(const InstrAspect &Aspect) const {
 201   assert(TablesInitialized && "backend forgot to call computeTables");
 202   // These *have* to be implemented for now, they're the fundamental basis of
 203   // how everything else is transformed.
 204   if (Aspect.Type.isScalar() || Aspect.Type.isPointer())
 205     return findScalarLegalAction(Aspect);
 206   assert(Aspect.Type.isVector());
 207   return findVectorLegalAction(Aspect);
 208 }
 209
 210 LegacyLegalizerInfo::SizeAndActionsVec
 211 LegacyLegalizerInfo::increaseToLargerTypesAndDecreaseToLargest(
 212     const SizeAndActionsVec &v, LegacyLegalizeAction IncreaseAction,
 213     LegacyLegalizeAction DecreaseAction) {
 214   SizeAndActionsVec result;
 215   unsigned LargestSizeSoFar = 0;
 216   if (v.size() >= 1 && v[0].first != 1)
 217     result.push_back({1, IncreaseAction});
 218   for (size_t i = 0; i < v.size(); ++i) {
 219     result.push_back(v[i]);
 220     LargestSizeSoFar = v[i].first;
 221     if (i + 1 < v.size() && v[i + 1].first != v[i].first + 1) {
 222       result.push_back({LargestSizeSoFar + 1, IncreaseAction});
 223       LargestSizeSoFar = v[i].first + 1;
 224     }
 225   }
 226   result.push_back({LargestSizeSoFar + 1, DecreaseAction});
 227   return result;
 228 }
 229
 230 LegacyLegalizerInfo::SizeAndActionsVec
 231 LegacyLegalizerInfo::decreaseToSmallerTypesAndIncreaseToSmallest(
 232     const SizeAndActionsVec &v, LegacyLegalizeAction DecreaseAction,
 233     LegacyLegalizeAction IncreaseAction) {
 234   SizeAndActionsVec result;
 235   if (v.size() == 0 || v[0].first != 1)
 236     result.push_back({1, IncreaseAction});
 237   for (size_t i = 0; i < v.size(); ++i) {
 238     result.push_back(v[i]);
 239     if (i + 1 == v.size() || v[i + 1].first != v[i].first + 1) {
 240       result.push_back({v[i].first + 1, DecreaseAction});
 241     }
 242   }
 243   return result;
 244 }
 245
 246 LegacyLegalizerInfo::SizeAndAction
 247 LegacyLegalizerInfo::findAction(const SizeAndActionsVec &Vec, const uint32_t Size) {
 248   assert(Size >= 1);
 249   // Find the last element in Vec that has a bitsize equal to or smaller than
 250   // the requested bit size.
 251   // That is the element just before the first element that is bigger than Size.
 252   auto It = partition_point(
 253       Vec, [=](const SizeAndAction &A) { return A.first <= Size; });
 254   assert(It != Vec.begin() && "Does Vec not start with size 1?");
 255   int VecIdx = It - Vec.begin() - 1;
 256
 257   LegacyLegalizeAction Action = Vec[VecIdx].second;
 258   switch (Action) {
 259   case Legal:
 260   case Bitcast:
 261   case Lower:
 262   case Libcall:
 263   case Custom:
 264     return {Size, Action};
 265   case FewerElements:
 266     // FIXME: is this special case still needed and correct?
 267     // Special case for scalarization:
 268     if (Vec == SizeAndActionsVec({{1, FewerElements}}))
 269       return {1, FewerElements};
 270     [[fallthrough]];
 271   case NarrowScalar: {
 272     // The following needs to be a loop, as for now, we do allow needing to
 273     // go over "Unsupported" bit sizes before finding a legalizable bit size.
 274     // e.g. (s8, WidenScalar), (s9, Unsupported), (s32, Legal). if Size==8,
 275     // we need to iterate over s9, and then to s32 to return (s32, Legal).
 276     // If we want to get rid of the below loop, we should have stronger asserts
 277     // when building the SizeAndActionsVecs, probably not allowing
 278     // "Unsupported" unless at the ends of the vector.
 279     for (int i = VecIdx - 1; i >= 0; --i)
 280       if (!needsLegalizingToDifferentSize(Vec[i].second) &&
 281           Vec[i].second != Unsupported)
 282         return {Vec[i].first, Action};
 283     llvm_unreachable("");
 284   }
 285   case WidenScalar:
 286   case MoreElements: {
 287     // See above, the following needs to be a loop, at least for now.
 288     for (std::size_t i = VecIdx + 1; i < Vec.size(); ++i)
 289       if (!needsLegalizingToDifferentSize(Vec[i].second) &&
 290           Vec[i].second != Unsupported)
 291         return {Vec[i].first, Action};
 292     llvm_unreachable("");
 293   }
 294   case Unsupported:
 295     return {Size, Unsupported};
 296   case NotFound:
 297     llvm_unreachable("NotFound");
 298   }
 299   llvm_unreachable("Action has an unknown enum value");
 300 }
 301
 302 std::pair<LegacyLegalizeAction, LLT>
 303 LegacyLegalizerInfo::findScalarLegalAction(const InstrAspect &Aspect) const {
 304   assert(Aspect.Type.isScalar() || Aspect.Type.isPointer());
 305   if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
 306     return {NotFound, LLT()};
 307   const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
 308   if (Aspect.Type.isPointer() &&
 309       AddrSpace2PointerActions[OpcodeIdx].find(Aspect.Type.getAddressSpace()) ==
 310           AddrSpace2PointerActions[OpcodeIdx].end()) {
 311     return {NotFound, LLT()};
 312   }
 313   const SmallVector<SizeAndActionsVec, 1> &Actions =
 314       Aspect.Type.isPointer()
 315           ? AddrSpace2PointerActions[OpcodeIdx]
 316                 .find(Aspect.Type.getAddressSpace())
 317                 ->second
 318           : ScalarActions[OpcodeIdx];
 319   if (Aspect.Idx >= Actions.size())
 320     return {NotFound, LLT()};
 321   const SizeAndActionsVec &Vec = Actions[Aspect.Idx];
 322   // FIXME: speed up this search, e.g. by using a results cache for repeated
 323   // queries?
 324   auto SizeAndAction = findAction(Vec, Aspect.Type.getSizeInBits());
 325   return {SizeAndAction.second,
 326           Aspect.Type.isScalar() ? LLT::scalar(SizeAndAction.first)
 327                                  : LLT::pointer(Aspect.Type.getAddressSpace(),
 328                                                 SizeAndAction.first)};
 329 }
 330
 331 std::pair<LegacyLegalizeAction, LLT>
 332 LegacyLegalizerInfo::findVectorLegalAction(const InstrAspect &Aspect) const {
 333   assert(Aspect.Type.isVector());
 334   // First legalize the vector element size, then legalize the number of
 335   // lanes in the vector.
 336   if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
 337     return {NotFound, Aspect.Type};
 338   const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
 339   const unsigned TypeIdx = Aspect.Idx;
 340   if (TypeIdx >= ScalarInVectorActions[OpcodeIdx].size())
 341     return {NotFound, Aspect.Type};
 342   const SizeAndActionsVec &ElemSizeVec =
 343       ScalarInVectorActions[OpcodeIdx][TypeIdx];
 344
 345   LLT IntermediateType;
 346   auto ElementSizeAndAction =
 347       findAction(ElemSizeVec, Aspect.Type.getScalarSizeInBits());
 348   IntermediateType = LLT::fixed_vector(Aspect.Type.getNumElements(),
 349                                        ElementSizeAndAction.first);
 350   if (ElementSizeAndAction.second != Legal)
 351     return {ElementSizeAndAction.second, IntermediateType};
 352
 353   auto i = NumElements2Actions[OpcodeIdx].find(
 354       IntermediateType.getScalarSizeInBits());
 355   if (i == NumElements2Actions[OpcodeIdx].end()) {
 356     return {NotFound, IntermediateType};
 357   }
 358   const SizeAndActionsVec &NumElementsVec = (*i).second[TypeIdx];
 359   auto NumElementsAndAction =
 360       findAction(NumElementsVec, IntermediateType.getNumElements());
 361   return {NumElementsAndAction.second,
 362           LLT::fixed_vector(NumElementsAndAction.first,
 363                             IntermediateType.getScalarSizeInBits())};
 364 }
 365
 366 unsigned LegacyLegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
 367   assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
 368   return Opcode - FirstOp;
 369 }
 370
 371
 372 LegacyLegalizeActionStep
 373 LegacyLegalizerInfo::getAction(const LegalityQuery &Query) const {
 374   for (unsigned i = 0; i < Query.Types.size(); ++i) {
 375     auto Action = getAspectAction({Query.Opcode, i, Query.Types[i]});
 376     if (Action.first != Legal) {
 377       LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Action="
 378                         << Action.first << ", " << Action.second << "\n");
 379       return {Action.first, i, Action.second};
 380     } else
 381       LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Legal\n");
 382   }
 383   LLVM_DEBUG(dbgs() << ".. (legacy) Legal\n");
 384   return {Legal, 0, LLT{}};
 385 }
 386