1 //===- lib/CodeGen/GlobalISel/LegalizerInfo.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/LegalizerInfo.h" 20 #include "llvm/ADT/SmallBitVector.h" 21 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.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/MC/MCInstrInfo.h" 28 #include "llvm/Support/Debug.h" 29 #include "llvm/Support/ErrorHandling.h" 30 #include "llvm/Support/LowLevelTypeImpl.h" 31 #include "llvm/Support/MathExtras.h" 32 #include <algorithm> 33 #include <map> 34 35 using namespace llvm; 36 using namespace LegalizeActions; 37 38 #define DEBUG_TYPE "legalizer-info" 39 40 cl::opt<bool> llvm::DisableGISelLegalityCheck( 41 "disable-gisel-legality-check", 42 cl::desc("Don't verify that MIR is fully legal between GlobalISel passes"), 43 cl::Hidden); 44 45 raw_ostream &llvm::operator<<(raw_ostream &OS, LegalizeAction Action) { 46 switch (Action) { 47 case Legal: 48 OS << "Legal"; 49 break; 50 case NarrowScalar: 51 OS << "NarrowScalar"; 52 break; 53 case WidenScalar: 54 OS << "WidenScalar"; 55 break; 56 case FewerElements: 57 OS << "FewerElements"; 58 break; 59 case MoreElements: 60 OS << "MoreElements"; 61 break; 62 case Lower: 63 OS << "Lower"; 64 break; 65 case Libcall: 66 OS << "Libcall"; 67 break; 68 case Custom: 69 OS << "Custom"; 70 break; 71 case Unsupported: 72 OS << "Unsupported"; 73 break; 74 case NotFound: 75 OS << "NotFound"; 76 break; 77 case UseLegacyRules: 78 OS << "UseLegacyRules"; 79 break; 80 } 81 return OS; 82 } 83 84 raw_ostream &LegalityQuery::print(raw_ostream &OS) const { 85 OS << Opcode << ", Tys={"; 86 for (const auto &Type : Types) { 87 OS << Type << ", "; 88 } 89 OS << "}, Opcode="; 90 91 OS << Opcode << ", MMOs={"; 92 for (const auto &MMODescr : MMODescrs) { 93 OS << MMODescr.SizeInBits << ", "; 94 } 95 OS << "}"; 96 97 return OS; 98 } 99 100 #ifndef NDEBUG 101 // Make sure the rule won't (trivially) loop forever. 102 static bool hasNoSimpleLoops(const LegalizeRule &Rule, const LegalityQuery &Q, 103 const std::pair<unsigned, LLT> &Mutation) { 104 switch (Rule.getAction()) { 105 case Custom: 106 case Lower: 107 case MoreElements: 108 case FewerElements: 109 break; 110 default: 111 return Q.Types[Mutation.first] != Mutation.second; 112 } 113 return true; 114 } 115 116 // Make sure the returned mutation makes sense for the match type. 117 static bool mutationIsSane(const LegalizeRule &Rule, 118 const LegalityQuery &Q, 119 std::pair<unsigned, LLT> Mutation) { 120 // If the user wants a custom mutation, then we can't really say much about 121 // it. Return true, and trust that they're doing the right thing. 122 if (Rule.getAction() == Custom) 123 return true; 124 125 const unsigned TypeIdx = Mutation.first; 126 const LLT OldTy = Q.Types[TypeIdx]; 127 const LLT NewTy = Mutation.second; 128 129 switch (Rule.getAction()) { 130 case FewerElements: 131 case MoreElements: { 132 if (!OldTy.isVector()) 133 return false; 134 135 if (NewTy.isVector()) { 136 if (Rule.getAction() == FewerElements) { 137 // Make sure the element count really decreased. 138 if (NewTy.getNumElements() >= OldTy.getNumElements()) 139 return false; 140 } else { 141 // Make sure the element count really increased. 142 if (NewTy.getNumElements() <= OldTy.getNumElements()) 143 return false; 144 } 145 } 146 147 // Make sure the element type didn't change. 148 return NewTy.getScalarType() == OldTy.getElementType(); 149 } 150 case NarrowScalar: 151 case WidenScalar: { 152 if (OldTy.isVector()) { 153 // Number of elements should not change. 154 if (!NewTy.isVector() || OldTy.getNumElements() != NewTy.getNumElements()) 155 return false; 156 } else { 157 // Both types must be vectors 158 if (NewTy.isVector()) 159 return false; 160 } 161 162 if (Rule.getAction() == NarrowScalar) { 163 // Make sure the size really decreased. 164 if (NewTy.getScalarSizeInBits() >= OldTy.getScalarSizeInBits()) 165 return false; 166 } else { 167 // Make sure the size really increased. 168 if (NewTy.getScalarSizeInBits() <= OldTy.getScalarSizeInBits()) 169 return false; 170 } 171 172 return true; 173 } 174 default: 175 return true; 176 } 177 } 178 #endif 179 180 LegalizeActionStep LegalizeRuleSet::apply(const LegalityQuery &Query) const { 181 LLVM_DEBUG(dbgs() << "Applying legalizer ruleset to: "; Query.print(dbgs()); 182 dbgs() << "\n"); 183 if (Rules.empty()) { 184 LLVM_DEBUG(dbgs() << ".. fallback to legacy rules (no rules defined)\n"); 185 return {LegalizeAction::UseLegacyRules, 0, LLT{}}; 186 } 187 for (const LegalizeRule &Rule : Rules) { 188 if (Rule.match(Query)) { 189 LLVM_DEBUG(dbgs() << ".. match\n"); 190 std::pair<unsigned, LLT> Mutation = Rule.determineMutation(Query); 191 LLVM_DEBUG(dbgs() << ".. .. " << Rule.getAction() << ", " 192 << Mutation.first << ", " << Mutation.second << "\n"); 193 assert(mutationIsSane(Rule, Query, Mutation) && 194 "legality mutation invalid for match"); 195 assert(hasNoSimpleLoops(Rule, Query, Mutation) && "Simple loop detected"); 196 return {Rule.getAction(), Mutation.first, Mutation.second}; 197 } else 198 LLVM_DEBUG(dbgs() << ".. no match\n"); 199 } 200 LLVM_DEBUG(dbgs() << ".. unsupported\n"); 201 return {LegalizeAction::Unsupported, 0, LLT{}}; 202 } 203 204 bool LegalizeRuleSet::verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const { 205 #ifndef NDEBUG 206 if (Rules.empty()) { 207 LLVM_DEBUG( 208 dbgs() << ".. type index coverage check SKIPPED: no rules defined\n"); 209 return true; 210 } 211 const int64_t FirstUncovered = TypeIdxsCovered.find_first_unset(); 212 if (FirstUncovered < 0) { 213 LLVM_DEBUG(dbgs() << ".. type index coverage check SKIPPED:" 214 " user-defined predicate detected\n"); 215 return true; 216 } 217 const bool AllCovered = (FirstUncovered >= NumTypeIdxs); 218 LLVM_DEBUG(dbgs() << ".. the first uncovered type index: " << FirstUncovered 219 << ", " << (AllCovered ? "OK" : "FAIL") << "\n"); 220 return AllCovered; 221 #else 222 return true; 223 #endif 224 } 225 226 LegalizerInfo::LegalizerInfo() : TablesInitialized(false) { 227 // Set defaults. 228 // FIXME: these two (G_ANYEXT and G_TRUNC?) can be legalized to the 229 // fundamental load/store Jakob proposed. Once loads & stores are supported. 230 setScalarAction(TargetOpcode::G_ANYEXT, 1, {{1, Legal}}); 231 setScalarAction(TargetOpcode::G_ZEXT, 1, {{1, Legal}}); 232 setScalarAction(TargetOpcode::G_SEXT, 1, {{1, Legal}}); 233 setScalarAction(TargetOpcode::G_TRUNC, 0, {{1, Legal}}); 234 setScalarAction(TargetOpcode::G_TRUNC, 1, {{1, Legal}}); 235 236 setScalarAction(TargetOpcode::G_INTRINSIC, 0, {{1, Legal}}); 237 setScalarAction(TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS, 0, {{1, Legal}}); 238 239 setLegalizeScalarToDifferentSizeStrategy( 240 TargetOpcode::G_IMPLICIT_DEF, 0, narrowToSmallerAndUnsupportedIfTooSmall); 241 setLegalizeScalarToDifferentSizeStrategy( 242 TargetOpcode::G_ADD, 0, widenToLargerTypesAndNarrowToLargest); 243 setLegalizeScalarToDifferentSizeStrategy( 244 TargetOpcode::G_OR, 0, widenToLargerTypesAndNarrowToLargest); 245 setLegalizeScalarToDifferentSizeStrategy( 246 TargetOpcode::G_LOAD, 0, narrowToSmallerAndUnsupportedIfTooSmall); 247 setLegalizeScalarToDifferentSizeStrategy( 248 TargetOpcode::G_STORE, 0, narrowToSmallerAndUnsupportedIfTooSmall); 249 250 setLegalizeScalarToDifferentSizeStrategy( 251 TargetOpcode::G_BRCOND, 0, widenToLargerTypesUnsupportedOtherwise); 252 setLegalizeScalarToDifferentSizeStrategy( 253 TargetOpcode::G_INSERT, 0, narrowToSmallerAndUnsupportedIfTooSmall); 254 setLegalizeScalarToDifferentSizeStrategy( 255 TargetOpcode::G_EXTRACT, 0, narrowToSmallerAndUnsupportedIfTooSmall); 256 setLegalizeScalarToDifferentSizeStrategy( 257 TargetOpcode::G_EXTRACT, 1, narrowToSmallerAndUnsupportedIfTooSmall); 258 setScalarAction(TargetOpcode::G_FNEG, 0, {{1, Lower}}); 259 } 260 261 void LegalizerInfo::computeTables() { 262 assert(TablesInitialized == false); 263 264 for (unsigned OpcodeIdx = 0; OpcodeIdx <= LastOp - FirstOp; ++OpcodeIdx) { 265 const unsigned Opcode = FirstOp + OpcodeIdx; 266 for (unsigned TypeIdx = 0; TypeIdx != SpecifiedActions[OpcodeIdx].size(); 267 ++TypeIdx) { 268 // 0. Collect information specified through the setAction API, i.e. 269 // for specific bit sizes. 270 // For scalar types: 271 SizeAndActionsVec ScalarSpecifiedActions; 272 // For pointer types: 273 std::map<uint16_t, SizeAndActionsVec> AddressSpace2SpecifiedActions; 274 // For vector types: 275 std::map<uint16_t, SizeAndActionsVec> ElemSize2SpecifiedActions; 276 for (auto LLT2Action : SpecifiedActions[OpcodeIdx][TypeIdx]) { 277 const LLT Type = LLT2Action.first; 278 const LegalizeAction Action = LLT2Action.second; 279 280 auto SizeAction = std::make_pair(Type.getSizeInBits(), Action); 281 if (Type.isPointer()) 282 AddressSpace2SpecifiedActions[Type.getAddressSpace()].push_back( 283 SizeAction); 284 else if (Type.isVector()) 285 ElemSize2SpecifiedActions[Type.getElementType().getSizeInBits()] 286 .push_back(SizeAction); 287 else 288 ScalarSpecifiedActions.push_back(SizeAction); 289 } 290 291 // 1. Handle scalar types 292 { 293 // Decide how to handle bit sizes for which no explicit specification 294 // was given. 295 SizeChangeStrategy S = &unsupportedForDifferentSizes; 296 if (TypeIdx < ScalarSizeChangeStrategies[OpcodeIdx].size() && 297 ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr) 298 S = ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx]; 299 llvm::sort(ScalarSpecifiedActions); 300 checkPartialSizeAndActionsVector(ScalarSpecifiedActions); 301 setScalarAction(Opcode, TypeIdx, S(ScalarSpecifiedActions)); 302 } 303 304 // 2. Handle pointer types 305 for (auto PointerSpecifiedActions : AddressSpace2SpecifiedActions) { 306 llvm::sort(PointerSpecifiedActions.second); 307 checkPartialSizeAndActionsVector(PointerSpecifiedActions.second); 308 // For pointer types, we assume that there isn't a meaningfull way 309 // to change the number of bits used in the pointer. 310 setPointerAction( 311 Opcode, TypeIdx, PointerSpecifiedActions.first, 312 unsupportedForDifferentSizes(PointerSpecifiedActions.second)); 313 } 314 315 // 3. Handle vector types 316 SizeAndActionsVec ElementSizesSeen; 317 for (auto VectorSpecifiedActions : ElemSize2SpecifiedActions) { 318 llvm::sort(VectorSpecifiedActions.second); 319 const uint16_t ElementSize = VectorSpecifiedActions.first; 320 ElementSizesSeen.push_back({ElementSize, Legal}); 321 checkPartialSizeAndActionsVector(VectorSpecifiedActions.second); 322 // For vector types, we assume that the best way to adapt the number 323 // of elements is to the next larger number of elements type for which 324 // the vector type is legal, unless there is no such type. In that case, 325 // legalize towards a vector type with a smaller number of elements. 326 SizeAndActionsVec NumElementsActions; 327 for (SizeAndAction BitsizeAndAction : VectorSpecifiedActions.second) { 328 assert(BitsizeAndAction.first % ElementSize == 0); 329 const uint16_t NumElements = BitsizeAndAction.first / ElementSize; 330 NumElementsActions.push_back({NumElements, BitsizeAndAction.second}); 331 } 332 setVectorNumElementAction( 333 Opcode, TypeIdx, ElementSize, 334 moreToWiderTypesAndLessToWidest(NumElementsActions)); 335 } 336 llvm::sort(ElementSizesSeen); 337 SizeChangeStrategy VectorElementSizeChangeStrategy = 338 &unsupportedForDifferentSizes; 339 if (TypeIdx < VectorElementSizeChangeStrategies[OpcodeIdx].size() && 340 VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr) 341 VectorElementSizeChangeStrategy = 342 VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx]; 343 setScalarInVectorAction( 344 Opcode, TypeIdx, VectorElementSizeChangeStrategy(ElementSizesSeen)); 345 } 346 } 347 348 TablesInitialized = true; 349 } 350 351 // FIXME: inefficient implementation for now. Without ComputeValueVTs we're 352 // probably going to need specialized lookup structures for various types before 353 // we have any hope of doing well with something like <13 x i3>. Even the common 354 // cases should do better than what we have now. 355 std::pair<LegalizeAction, LLT> 356 LegalizerInfo::getAspectAction(const InstrAspect &Aspect) const { 357 assert(TablesInitialized && "backend forgot to call computeTables"); 358 // These *have* to be implemented for now, they're the fundamental basis of 359 // how everything else is transformed. 360 if (Aspect.Type.isScalar() || Aspect.Type.isPointer()) 361 return findScalarLegalAction(Aspect); 362 assert(Aspect.Type.isVector()); 363 return findVectorLegalAction(Aspect); 364 } 365 366 /// Helper function to get LLT for the given type index. 367 static LLT getTypeFromTypeIdx(const MachineInstr &MI, 368 const MachineRegisterInfo &MRI, unsigned OpIdx, 369 unsigned TypeIdx) { 370 assert(TypeIdx < MI.getNumOperands() && "Unexpected TypeIdx"); 371 // G_UNMERGE_VALUES has variable number of operands, but there is only 372 // one source type and one destination type as all destinations must be the 373 // same type. So, get the last operand if TypeIdx == 1. 374 if (MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && TypeIdx == 1) 375 return MRI.getType(MI.getOperand(MI.getNumOperands() - 1).getReg()); 376 return MRI.getType(MI.getOperand(OpIdx).getReg()); 377 } 378 379 unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const { 380 assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode"); 381 return Opcode - FirstOp; 382 } 383 384 unsigned LegalizerInfo::getActionDefinitionsIdx(unsigned Opcode) const { 385 unsigned OpcodeIdx = getOpcodeIdxForOpcode(Opcode); 386 if (unsigned Alias = RulesForOpcode[OpcodeIdx].getAlias()) { 387 LLVM_DEBUG(dbgs() << ".. opcode " << Opcode << " is aliased to " << Alias 388 << "\n"); 389 OpcodeIdx = getOpcodeIdxForOpcode(Alias); 390 LLVM_DEBUG(dbgs() << ".. opcode " << Alias << " is aliased to " 391 << RulesForOpcode[OpcodeIdx].getAlias() << "\n"); 392 assert(RulesForOpcode[OpcodeIdx].getAlias() == 0 && "Cannot chain aliases"); 393 } 394 395 return OpcodeIdx; 396 } 397 398 const LegalizeRuleSet & 399 LegalizerInfo::getActionDefinitions(unsigned Opcode) const { 400 unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode); 401 return RulesForOpcode[OpcodeIdx]; 402 } 403 404 LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(unsigned Opcode) { 405 unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode); 406 auto &Result = RulesForOpcode[OpcodeIdx]; 407 assert(!Result.isAliasedByAnother() && "Modifying this opcode will modify aliases"); 408 return Result; 409 } 410 411 LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder( 412 std::initializer_list<unsigned> Opcodes) { 413 unsigned Representative = *Opcodes.begin(); 414 415 assert(!empty(Opcodes) && Opcodes.begin() + 1 != Opcodes.end() && 416 "Initializer list must have at least two opcodes"); 417 418 for (auto I = Opcodes.begin() + 1, E = Opcodes.end(); I != E; ++I) 419 aliasActionDefinitions(Representative, *I); 420 421 auto &Return = getActionDefinitionsBuilder(Representative); 422 Return.setIsAliasedByAnother(); 423 return Return; 424 } 425 426 void LegalizerInfo::aliasActionDefinitions(unsigned OpcodeTo, 427 unsigned OpcodeFrom) { 428 assert(OpcodeTo != OpcodeFrom && "Cannot alias to self"); 429 assert(OpcodeTo >= FirstOp && OpcodeTo <= LastOp && "Unsupported opcode"); 430 const unsigned OpcodeFromIdx = getOpcodeIdxForOpcode(OpcodeFrom); 431 RulesForOpcode[OpcodeFromIdx].aliasTo(OpcodeTo); 432 } 433 434 LegalizeActionStep 435 LegalizerInfo::getAction(const LegalityQuery &Query) const { 436 LegalizeActionStep Step = getActionDefinitions(Query.Opcode).apply(Query); 437 if (Step.Action != LegalizeAction::UseLegacyRules) { 438 return Step; 439 } 440 441 for (unsigned i = 0; i < Query.Types.size(); ++i) { 442 auto Action = getAspectAction({Query.Opcode, i, Query.Types[i]}); 443 if (Action.first != Legal) { 444 LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Action=" 445 << Action.first << ", " << Action.second << "\n"); 446 return {Action.first, i, Action.second}; 447 } else 448 LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Legal\n"); 449 } 450 LLVM_DEBUG(dbgs() << ".. (legacy) Legal\n"); 451 return {Legal, 0, LLT{}}; 452 } 453 454 LegalizeActionStep 455 LegalizerInfo::getAction(const MachineInstr &MI, 456 const MachineRegisterInfo &MRI) const { 457 SmallVector<LLT, 2> Types; 458 SmallBitVector SeenTypes(8); 459 const MCOperandInfo *OpInfo = MI.getDesc().OpInfo; 460 // FIXME: probably we'll need to cache the results here somehow? 461 for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) { 462 if (!OpInfo[i].isGenericType()) 463 continue; 464 465 // We must only record actions once for each TypeIdx; otherwise we'd 466 // try to legalize operands multiple times down the line. 467 unsigned TypeIdx = OpInfo[i].getGenericTypeIndex(); 468 if (SeenTypes[TypeIdx]) 469 continue; 470 471 SeenTypes.set(TypeIdx); 472 473 LLT Ty = getTypeFromTypeIdx(MI, MRI, i, TypeIdx); 474 Types.push_back(Ty); 475 } 476 477 SmallVector<LegalityQuery::MemDesc, 2> MemDescrs; 478 for (const auto &MMO : MI.memoperands()) 479 MemDescrs.push_back({8 * MMO->getSize() /* in bits */, 480 8 * MMO->getAlignment(), 481 MMO->getOrdering()}); 482 483 return getAction({MI.getOpcode(), Types, MemDescrs}); 484 } 485 486 bool LegalizerInfo::isLegal(const MachineInstr &MI, 487 const MachineRegisterInfo &MRI) const { 488 return getAction(MI, MRI).Action == Legal; 489 } 490 491 bool LegalizerInfo::isLegalOrCustom(const MachineInstr &MI, 492 const MachineRegisterInfo &MRI) const { 493 auto Action = getAction(MI, MRI).Action; 494 // If the action is custom, it may not necessarily modify the instruction, 495 // so we have to assume it's legal. 496 return Action == Legal || Action == Custom; 497 } 498 499 bool LegalizerInfo::legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI, 500 MachineIRBuilder &MIRBuilder, 501 GISelChangeObserver &Observer) const { 502 return false; 503 } 504 505 LegalizerInfo::SizeAndActionsVec 506 LegalizerInfo::increaseToLargerTypesAndDecreaseToLargest( 507 const SizeAndActionsVec &v, LegalizeAction IncreaseAction, 508 LegalizeAction DecreaseAction) { 509 SizeAndActionsVec result; 510 unsigned LargestSizeSoFar = 0; 511 if (v.size() >= 1 && v[0].first != 1) 512 result.push_back({1, IncreaseAction}); 513 for (size_t i = 0; i < v.size(); ++i) { 514 result.push_back(v[i]); 515 LargestSizeSoFar = v[i].first; 516 if (i + 1 < v.size() && v[i + 1].first != v[i].first + 1) { 517 result.push_back({LargestSizeSoFar + 1, IncreaseAction}); 518 LargestSizeSoFar = v[i].first + 1; 519 } 520 } 521 result.push_back({LargestSizeSoFar + 1, DecreaseAction}); 522 return result; 523 } 524 525 LegalizerInfo::SizeAndActionsVec 526 LegalizerInfo::decreaseToSmallerTypesAndIncreaseToSmallest( 527 const SizeAndActionsVec &v, LegalizeAction DecreaseAction, 528 LegalizeAction IncreaseAction) { 529 SizeAndActionsVec result; 530 if (v.size() == 0 || v[0].first != 1) 531 result.push_back({1, IncreaseAction}); 532 for (size_t i = 0; i < v.size(); ++i) { 533 result.push_back(v[i]); 534 if (i + 1 == v.size() || v[i + 1].first != v[i].first + 1) { 535 result.push_back({v[i].first + 1, DecreaseAction}); 536 } 537 } 538 return result; 539 } 540 541 LegalizerInfo::SizeAndAction 542 LegalizerInfo::findAction(const SizeAndActionsVec &Vec, const uint32_t Size) { 543 assert(Size >= 1); 544 // Find the last element in Vec that has a bitsize equal to or smaller than 545 // the requested bit size. 546 // That is the element just before the first element that is bigger than Size. 547 auto It = partition_point( 548 Vec, [=](const SizeAndAction &A) { return A.first <= Size; }); 549 assert(It != Vec.begin() && "Does Vec not start with size 1?"); 550 int VecIdx = It - Vec.begin() - 1; 551 552 LegalizeAction Action = Vec[VecIdx].second; 553 switch (Action) { 554 case Legal: 555 case Lower: 556 case Libcall: 557 case Custom: 558 return {Size, Action}; 559 case FewerElements: 560 // FIXME: is this special case still needed and correct? 561 // Special case for scalarization: 562 if (Vec == SizeAndActionsVec({{1, FewerElements}})) 563 return {1, FewerElements}; 564 LLVM_FALLTHROUGH; 565 case NarrowScalar: { 566 // The following needs to be a loop, as for now, we do allow needing to 567 // go over "Unsupported" bit sizes before finding a legalizable bit size. 568 // e.g. (s8, WidenScalar), (s9, Unsupported), (s32, Legal). if Size==8, 569 // we need to iterate over s9, and then to s32 to return (s32, Legal). 570 // If we want to get rid of the below loop, we should have stronger asserts 571 // when building the SizeAndActionsVecs, probably not allowing 572 // "Unsupported" unless at the ends of the vector. 573 for (int i = VecIdx - 1; i >= 0; --i) 574 if (!needsLegalizingToDifferentSize(Vec[i].second) && 575 Vec[i].second != Unsupported) 576 return {Vec[i].first, Action}; 577 llvm_unreachable(""); 578 } 579 case WidenScalar: 580 case MoreElements: { 581 // See above, the following needs to be a loop, at least for now. 582 for (std::size_t i = VecIdx + 1; i < Vec.size(); ++i) 583 if (!needsLegalizingToDifferentSize(Vec[i].second) && 584 Vec[i].second != Unsupported) 585 return {Vec[i].first, Action}; 586 llvm_unreachable(""); 587 } 588 case Unsupported: 589 return {Size, Unsupported}; 590 case NotFound: 591 case UseLegacyRules: 592 llvm_unreachable("NotFound"); 593 } 594 llvm_unreachable("Action has an unknown enum value"); 595 } 596 597 std::pair<LegalizeAction, LLT> 598 LegalizerInfo::findScalarLegalAction(const InstrAspect &Aspect) const { 599 assert(Aspect.Type.isScalar() || Aspect.Type.isPointer()); 600 if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp) 601 return {NotFound, LLT()}; 602 const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode); 603 if (Aspect.Type.isPointer() && 604 AddrSpace2PointerActions[OpcodeIdx].find(Aspect.Type.getAddressSpace()) == 605 AddrSpace2PointerActions[OpcodeIdx].end()) { 606 return {NotFound, LLT()}; 607 } 608 const SmallVector<SizeAndActionsVec, 1> &Actions = 609 Aspect.Type.isPointer() 610 ? AddrSpace2PointerActions[OpcodeIdx] 611 .find(Aspect.Type.getAddressSpace()) 612 ->second 613 : ScalarActions[OpcodeIdx]; 614 if (Aspect.Idx >= Actions.size()) 615 return {NotFound, LLT()}; 616 const SizeAndActionsVec &Vec = Actions[Aspect.Idx]; 617 // FIXME: speed up this search, e.g. by using a results cache for repeated 618 // queries? 619 auto SizeAndAction = findAction(Vec, Aspect.Type.getSizeInBits()); 620 return {SizeAndAction.second, 621 Aspect.Type.isScalar() ? LLT::scalar(SizeAndAction.first) 622 : LLT::pointer(Aspect.Type.getAddressSpace(), 623 SizeAndAction.first)}; 624 } 625 626 std::pair<LegalizeAction, LLT> 627 LegalizerInfo::findVectorLegalAction(const InstrAspect &Aspect) const { 628 assert(Aspect.Type.isVector()); 629 // First legalize the vector element size, then legalize the number of 630 // lanes in the vector. 631 if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp) 632 return {NotFound, Aspect.Type}; 633 const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode); 634 const unsigned TypeIdx = Aspect.Idx; 635 if (TypeIdx >= ScalarInVectorActions[OpcodeIdx].size()) 636 return {NotFound, Aspect.Type}; 637 const SizeAndActionsVec &ElemSizeVec = 638 ScalarInVectorActions[OpcodeIdx][TypeIdx]; 639 640 LLT IntermediateType; 641 auto ElementSizeAndAction = 642 findAction(ElemSizeVec, Aspect.Type.getScalarSizeInBits()); 643 IntermediateType = 644 LLT::vector(Aspect.Type.getNumElements(), ElementSizeAndAction.first); 645 if (ElementSizeAndAction.second != Legal) 646 return {ElementSizeAndAction.second, IntermediateType}; 647 648 auto i = NumElements2Actions[OpcodeIdx].find( 649 IntermediateType.getScalarSizeInBits()); 650 if (i == NumElements2Actions[OpcodeIdx].end()) { 651 return {NotFound, IntermediateType}; 652 } 653 const SizeAndActionsVec &NumElementsVec = (*i).second[TypeIdx]; 654 auto NumElementsAndAction = 655 findAction(NumElementsVec, IntermediateType.getNumElements()); 656 return {NumElementsAndAction.second, 657 LLT::vector(NumElementsAndAction.first, 658 IntermediateType.getScalarSizeInBits())}; 659 } 660 661 bool LegalizerInfo::legalizeIntrinsic(MachineInstr &MI, 662 MachineRegisterInfo &MRI, 663 MachineIRBuilder &MIRBuilder) const { 664 return true; 665 } 666 667 /// \pre Type indices of every opcode form a dense set starting from 0. 668 void LegalizerInfo::verify(const MCInstrInfo &MII) const { 669 #ifndef NDEBUG 670 std::vector<unsigned> FailedOpcodes; 671 for (unsigned Opcode = FirstOp; Opcode <= LastOp; ++Opcode) { 672 const MCInstrDesc &MCID = MII.get(Opcode); 673 const unsigned NumTypeIdxs = std::accumulate( 674 MCID.opInfo_begin(), MCID.opInfo_end(), 0U, 675 [](unsigned Acc, const MCOperandInfo &OpInfo) { 676 return OpInfo.isGenericType() 677 ? std::max(OpInfo.getGenericTypeIndex() + 1U, Acc) 678 : Acc; 679 }); 680 LLVM_DEBUG(dbgs() << MII.getName(Opcode) << " (opcode " << Opcode 681 << "): " << NumTypeIdxs << " type ind" 682 << (NumTypeIdxs == 1 ? "ex" : "ices") << "\n"); 683 const LegalizeRuleSet &RuleSet = getActionDefinitions(Opcode); 684 if (!RuleSet.verifyTypeIdxsCoverage(NumTypeIdxs)) 685 FailedOpcodes.push_back(Opcode); 686 } 687 if (!FailedOpcodes.empty()) { 688 errs() << "The following opcodes have ill-defined legalization rules:"; 689 for (unsigned Opcode : FailedOpcodes) 690 errs() << " " << MII.getName(Opcode); 691 errs() << "\n"; 692 693 report_fatal_error("ill-defined LegalizerInfo" 694 ", try -debug-only=legalizer-info for details"); 695 } 696 #endif 697 } 698 699 #ifndef NDEBUG 700 // FIXME: This should be in the MachineVerifier, but it can't use the 701 // LegalizerInfo as it's currently in the separate GlobalISel library. 702 // Note that RegBankSelected property already checked in the verifier 703 // has the same layering problem, but we only use inline methods so 704 // end up not needing to link against the GlobalISel library. 705 const MachineInstr *llvm::machineFunctionIsIllegal(const MachineFunction &MF) { 706 if (const LegalizerInfo *MLI = MF.getSubtarget().getLegalizerInfo()) { 707 const MachineRegisterInfo &MRI = MF.getRegInfo(); 708 for (const MachineBasicBlock &MBB : MF) 709 for (const MachineInstr &MI : MBB) 710 if (isPreISelGenericOpcode(MI.getOpcode()) && 711 !MLI->isLegalOrCustom(MI, MRI)) 712 return &MI; 713 } 714 return nullptr; 715 } 716 #endif 717