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