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 387