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