386 lines · 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-exception6//7//===----------------------------------------------------------------------===//8//9// Implement an interface to specify and query how an illegal operation on a10// 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 23using namespace llvm;24using namespace LegacyLegalizeActions;25 26#define DEBUG_TYPE "legalizer-info"27 28raw_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 67LegacyLegalizerInfo::LegacyLegalizerInfo() {68 // Set defaults.69 // FIXME: these two (G_ANYEXT and G_TRUNC?) can be legalized to the70 // 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 105void 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 else132 ScalarSpecifiedActions.push_back(SizeAction);133 }134 135 // 1. Handle scalar types136 {137 // Decide how to handle bit sizes for which no explicit specification138 // 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 types149 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 way153 // 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 types160 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 number167 // of elements is to the next larger number of elements type for which168 // 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're196// probably going to need specialized lookup structures for various types before197// we have any hope of doing well with something like <13 x i3>. Even the common198// cases should do better than what we have now.199std::pair<LegacyLegalizeAction, LLT>200LegacyLegalizerInfo::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 of203 // 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 210LegacyLegalizerInfo::SizeAndActionsVec211LegacyLegalizerInfo::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 230LegacyLegalizerInfo::SizeAndActionsVec231LegacyLegalizerInfo::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 246LegacyLegalizerInfo::SizeAndAction247LegacyLegalizerInfo::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 than250 // 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 to273 // 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 asserts277 // when building the SizeAndActionsVecs, probably not allowing278 // "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 302std::pair<LegacyLegalizeAction, LLT>303LegacyLegalizerInfo::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 ArrayRef<SizeAndActionsVec> Actions;309 if (Aspect.Type.isPointer()) {310 auto &PA = AddrSpace2PointerActions[OpcodeIdx];311 auto It = PA.find(Aspect.Type.getAddressSpace());312 if (It == PA.end())313 return {NotFound, LLT()};314 Actions = It->second;315 } else {316 Actions = ScalarActions[OpcodeIdx];317 }318 if (Aspect.Idx >= Actions.size())319 return {NotFound, LLT()};320 const SizeAndActionsVec &Vec = Actions[Aspect.Idx];321 // FIXME: speed up this search, e.g. by using a results cache for repeated322 // queries?323 auto SizeAndAction = findAction(Vec, Aspect.Type.getSizeInBits());324 return {SizeAndAction.second,325 Aspect.Type.isScalar() ? LLT::scalar(SizeAndAction.first)326 : LLT::pointer(Aspect.Type.getAddressSpace(),327 SizeAndAction.first)};328}329 330std::pair<LegacyLegalizeAction, LLT>331LegacyLegalizerInfo::findVectorLegalAction(const InstrAspect &Aspect) const {332 assert(Aspect.Type.isVector());333 // First legalize the vector element size, then legalize the number of334 // lanes in the vector.335 if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)336 return {NotFound, Aspect.Type};337 const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);338 const unsigned TypeIdx = Aspect.Idx;339 if (TypeIdx >= ScalarInVectorActions[OpcodeIdx].size())340 return {NotFound, Aspect.Type};341 const SizeAndActionsVec &ElemSizeVec =342 ScalarInVectorActions[OpcodeIdx][TypeIdx];343 344 LLT IntermediateType;345 auto ElementSizeAndAction =346 findAction(ElemSizeVec, Aspect.Type.getScalarSizeInBits());347 IntermediateType = LLT::fixed_vector(Aspect.Type.getNumElements(),348 ElementSizeAndAction.first);349 if (ElementSizeAndAction.second != Legal)350 return {ElementSizeAndAction.second, IntermediateType};351 352 auto i = NumElements2Actions[OpcodeIdx].find(353 IntermediateType.getScalarSizeInBits());354 if (i == NumElements2Actions[OpcodeIdx].end()) {355 return {NotFound, IntermediateType};356 }357 const SizeAndActionsVec &NumElementsVec = (*i).second[TypeIdx];358 auto NumElementsAndAction =359 findAction(NumElementsVec, IntermediateType.getNumElements());360 return {NumElementsAndAction.second,361 LLT::fixed_vector(NumElementsAndAction.first,362 IntermediateType.getScalarSizeInBits())};363}364 365unsigned LegacyLegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {366 assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");367 return Opcode - FirstOp;368}369 370 371LegacyLegalizeActionStep372LegacyLegalizerInfo::getAction(const LegalityQuery &Query) const {373 for (unsigned i = 0; i < Query.Types.size(); ++i) {374 auto Action = getAspectAction({Query.Opcode, i, Query.Types[i]});375 if (Action.first != Legal) {376 LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Action="377 << Action.first << ", " << Action.second << "\n");378 return {Action.first, i, Action.second};379 } else380 LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Legal\n");381 }382 LLVM_DEBUG(dbgs() << ".. (legacy) Legal\n");383 return {Legal, 0, LLT{}};384}385 386