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

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