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