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 //===----------------------------------------------------------------------===// 13 14 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h" 15 #include "llvm/ADT/SmallBitVector.h" 16 #include "llvm/CodeGen/MachineInstr.h" 17 #include "llvm/CodeGen/MachineOperand.h" 18 #include "llvm/CodeGen/MachineRegisterInfo.h" 19 #include "llvm/CodeGen/TargetOpcodes.h" 20 #include "llvm/CodeGenTypes/LowLevelType.h" 21 #include "llvm/MC/MCInstrDesc.h" 22 #include "llvm/MC/MCInstrInfo.h" 23 #include "llvm/Support/Debug.h" 24 #include "llvm/Support/ErrorHandling.h" 25 #include <algorithm> 26 27 using namespace llvm; 28 using namespace LegalizeActions; 29 30 #define DEBUG_TYPE "legalizer-info" 31 32 cl::opt<bool> llvm::DisableGISelLegalityCheck( 33 "disable-gisel-legality-check", 34 cl::desc("Don't verify that MIR is fully legal between GlobalISel passes"), 35 cl::Hidden); 36 37 cl::opt<bool> VerboseVerifyLegalizerInfo( 38 "verbose-gisel-verify-legalizer-info", 39 cl::desc("Print more information to dbgs about GlobalISel legalizer rules " 40 "being verified"), 41 cl::Hidden); 42 43 raw_ostream &llvm::operator<<(raw_ostream &OS, LegalizeAction Action) { 44 switch (Action) { 45 case Legal: 46 OS << "Legal"; 47 break; 48 case NarrowScalar: 49 OS << "NarrowScalar"; 50 break; 51 case WidenScalar: 52 OS << "WidenScalar"; 53 break; 54 case FewerElements: 55 OS << "FewerElements"; 56 break; 57 case MoreElements: 58 OS << "MoreElements"; 59 break; 60 case Bitcast: 61 OS << "Bitcast"; 62 break; 63 case Lower: 64 OS << "Lower"; 65 break; 66 case Libcall: 67 OS << "Libcall"; 68 break; 69 case Custom: 70 OS << "Custom"; 71 break; 72 case Unsupported: 73 OS << "Unsupported"; 74 break; 75 case NotFound: 76 OS << "NotFound"; 77 break; 78 case UseLegacyRules: 79 OS << "UseLegacyRules"; 80 break; 81 } 82 return OS; 83 } 84 85 raw_ostream &LegalityQuery::print(raw_ostream &OS) const { 86 OS << "Opcode=" << Opcode << ", Tys={"; 87 for (const auto &Type : Types) { 88 OS << Type << ", "; 89 } 90 OS << "}, MMOs={"; 91 for (const auto &MMODescr : MMODescrs) { 92 OS << MMODescr.MemoryTy << ", "; 93 } 94 OS << "}"; 95 96 return OS; 97 } 98 99 #ifndef NDEBUG 100 // Make sure the rule won't (trivially) loop forever. 101 static bool hasNoSimpleLoops(const LegalizeRule &Rule, const LegalityQuery &Q, 102 const std::pair<unsigned, LLT> &Mutation) { 103 switch (Rule.getAction()) { 104 case Legal: 105 case Custom: 106 case Lower: 107 case MoreElements: 108 case FewerElements: 109 case Libcall: 110 break; 111 default: 112 return Q.Types[Mutation.first] != Mutation.second; 113 } 114 return true; 115 } 116 117 // Make sure the returned mutation makes sense for the match type. 118 static bool mutationIsSane(const LegalizeRule &Rule, 119 const LegalityQuery &Q, 120 std::pair<unsigned, LLT> Mutation) { 121 // If the user wants a custom mutation, then we can't really say much about 122 // it. Return true, and trust that they're doing the right thing. 123 if (Rule.getAction() == Custom || Rule.getAction() == Legal) 124 return true; 125 126 // Skip null mutation. 127 if (!Mutation.second.isValid()) 128 return true; 129 130 const unsigned TypeIdx = Mutation.first; 131 const LLT OldTy = Q.Types[TypeIdx]; 132 const LLT NewTy = Mutation.second; 133 134 switch (Rule.getAction()) { 135 case FewerElements: 136 if (!OldTy.isVector()) 137 return false; 138 [[fallthrough]]; 139 case MoreElements: { 140 // MoreElements can go from scalar to vector. 141 const ElementCount OldElts = OldTy.isVector() ? 142 OldTy.getElementCount() : ElementCount::getFixed(1); 143 if (NewTy.isVector()) { 144 if (Rule.getAction() == FewerElements) { 145 // Make sure the element count really decreased. 146 if (ElementCount::isKnownGE(NewTy.getElementCount(), OldElts)) 147 return false; 148 } else { 149 // Make sure the element count really increased. 150 if (ElementCount::isKnownLE(NewTy.getElementCount(), OldElts)) 151 return false; 152 } 153 } else if (Rule.getAction() == MoreElements) 154 return false; 155 156 // Make sure the element type didn't change. 157 return NewTy.getScalarType() == OldTy.getScalarType(); 158 } 159 case NarrowScalar: 160 case WidenScalar: { 161 if (OldTy.isVector()) { 162 // Number of elements should not change. 163 if (!NewTy.isVector() || 164 OldTy.getElementCount() != NewTy.getElementCount()) 165 return false; 166 } else { 167 // Both types must be vectors 168 if (NewTy.isVector()) 169 return false; 170 } 171 172 if (Rule.getAction() == NarrowScalar) { 173 // Make sure the size really decreased. 174 if (NewTy.getScalarSizeInBits() >= OldTy.getScalarSizeInBits()) 175 return false; 176 } else { 177 // Make sure the size really increased. 178 if (NewTy.getScalarSizeInBits() <= OldTy.getScalarSizeInBits()) 179 return false; 180 } 181 182 return true; 183 } 184 case Bitcast: { 185 return OldTy != NewTy && OldTy.getSizeInBits() == NewTy.getSizeInBits(); 186 } 187 default: 188 return true; 189 } 190 } 191 #endif 192 193 LegalizeActionStep LegalizeRuleSet::apply(const LegalityQuery &Query) const { 194 LLVM_DEBUG(dbgs() << "Applying legalizer ruleset to: "; Query.print(dbgs()); 195 dbgs() << "\n"); 196 if (Rules.empty()) { 197 LLVM_DEBUG(dbgs() << ".. fallback to legacy rules (no rules defined)\n"); 198 return {LegalizeAction::UseLegacyRules, 0, LLT{}}; 199 } 200 for (const LegalizeRule &Rule : Rules) { 201 if (Rule.match(Query)) { 202 LLVM_DEBUG(dbgs() << ".. match\n"); 203 std::pair<unsigned, LLT> Mutation = Rule.determineMutation(Query); 204 LLVM_DEBUG(dbgs() << ".. .. " << Rule.getAction() << ", " 205 << Mutation.first << ", " << Mutation.second << "\n"); 206 assert(mutationIsSane(Rule, Query, Mutation) && 207 "legality mutation invalid for match"); 208 assert(hasNoSimpleLoops(Rule, Query, Mutation) && "Simple loop detected"); 209 return {Rule.getAction(), Mutation.first, Mutation.second}; 210 } else 211 LLVM_DEBUG(dbgs() << ".. no match\n"); 212 } 213 LLVM_DEBUG(dbgs() << ".. unsupported\n"); 214 return {LegalizeAction::Unsupported, 0, LLT{}}; 215 } 216 217 bool LegalizeRuleSet::verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const { 218 #ifndef NDEBUG 219 if (Rules.empty()) { 220 if (VerboseVerifyLegalizerInfo) { 221 LLVM_DEBUG(dbgs() << ".. type index coverage check SKIPPED: " 222 << "no rules defined\n"); 223 } 224 return true; 225 } 226 const int64_t FirstUncovered = TypeIdxsCovered.find_first_unset(); 227 if (FirstUncovered < 0) { 228 if (VerboseVerifyLegalizerInfo) { 229 LLVM_DEBUG(dbgs() << ".. type index coverage check SKIPPED:" 230 " user-defined predicate detected\n"); 231 } 232 return true; 233 } 234 const bool AllCovered = (FirstUncovered >= NumTypeIdxs); 235 if (NumTypeIdxs > 0) { 236 if (VerboseVerifyLegalizerInfo) { 237 LLVM_DEBUG(dbgs() << ".. the first uncovered type index: " 238 << FirstUncovered << ", " 239 << (AllCovered ? "OK" : "FAIL") << "\n"); 240 } 241 } 242 return AllCovered; 243 #else 244 return true; 245 #endif 246 } 247 248 bool LegalizeRuleSet::verifyImmIdxsCoverage(unsigned NumImmIdxs) const { 249 #ifndef NDEBUG 250 if (Rules.empty()) { 251 if (VerboseVerifyLegalizerInfo) { 252 LLVM_DEBUG(dbgs() << ".. imm index coverage check SKIPPED: " 253 << "no rules defined\n"); 254 } 255 return true; 256 } 257 const int64_t FirstUncovered = ImmIdxsCovered.find_first_unset(); 258 if (FirstUncovered < 0) { 259 if (VerboseVerifyLegalizerInfo) { 260 LLVM_DEBUG(dbgs() << ".. imm index coverage check SKIPPED:" 261 " user-defined predicate detected\n"); 262 } 263 return true; 264 } 265 const bool AllCovered = (FirstUncovered >= NumImmIdxs); 266 if (VerboseVerifyLegalizerInfo) { 267 LLVM_DEBUG(dbgs() << ".. the first uncovered imm index: " << FirstUncovered 268 << ", " << (AllCovered ? "OK" : "FAIL") << "\n"); 269 } 270 return AllCovered; 271 #else 272 return true; 273 #endif 274 } 275 276 /// Helper function to get LLT for the given type index. 277 static LLT getTypeFromTypeIdx(const MachineInstr &MI, 278 const MachineRegisterInfo &MRI, unsigned OpIdx, 279 unsigned TypeIdx) { 280 assert(TypeIdx < MI.getNumOperands() && "Unexpected TypeIdx"); 281 // G_UNMERGE_VALUES has variable number of operands, but there is only 282 // one source type and one destination type as all destinations must be the 283 // same type. So, get the last operand if TypeIdx == 1. 284 if (MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && TypeIdx == 1) 285 return MRI.getType(MI.getOperand(MI.getNumOperands() - 1).getReg()); 286 return MRI.getType(MI.getOperand(OpIdx).getReg()); 287 } 288 289 unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const { 290 assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode"); 291 return Opcode - FirstOp; 292 } 293 294 unsigned LegalizerInfo::getActionDefinitionsIdx(unsigned Opcode) const { 295 unsigned OpcodeIdx = getOpcodeIdxForOpcode(Opcode); 296 if (unsigned Alias = RulesForOpcode[OpcodeIdx].getAlias()) { 297 if (VerboseVerifyLegalizerInfo) { 298 LLVM_DEBUG(dbgs() << ".. opcode " << Opcode << " is aliased to " << Alias 299 << "\n"); 300 } 301 OpcodeIdx = getOpcodeIdxForOpcode(Alias); 302 assert(RulesForOpcode[OpcodeIdx].getAlias() == 0 && "Cannot chain aliases"); 303 } 304 305 return OpcodeIdx; 306 } 307 308 const LegalizeRuleSet & 309 LegalizerInfo::getActionDefinitions(unsigned Opcode) const { 310 unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode); 311 return RulesForOpcode[OpcodeIdx]; 312 } 313 314 LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(unsigned Opcode) { 315 unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode); 316 auto &Result = RulesForOpcode[OpcodeIdx]; 317 assert(!Result.isAliasedByAnother() && "Modifying this opcode will modify aliases"); 318 return Result; 319 } 320 321 LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder( 322 std::initializer_list<unsigned> Opcodes) { 323 unsigned Representative = *Opcodes.begin(); 324 325 assert(Opcodes.size() >= 2 && 326 "Initializer list must have at least two opcodes"); 327 328 for (unsigned Op : llvm::drop_begin(Opcodes)) 329 aliasActionDefinitions(Representative, Op); 330 331 auto &Return = getActionDefinitionsBuilder(Representative); 332 Return.setIsAliasedByAnother(); 333 return Return; 334 } 335 336 void LegalizerInfo::aliasActionDefinitions(unsigned OpcodeTo, 337 unsigned OpcodeFrom) { 338 assert(OpcodeTo != OpcodeFrom && "Cannot alias to self"); 339 assert(OpcodeTo >= FirstOp && OpcodeTo <= LastOp && "Unsupported opcode"); 340 const unsigned OpcodeFromIdx = getOpcodeIdxForOpcode(OpcodeFrom); 341 RulesForOpcode[OpcodeFromIdx].aliasTo(OpcodeTo); 342 } 343 344 LegalizeActionStep 345 LegalizerInfo::getAction(const LegalityQuery &Query) const { 346 LegalizeActionStep Step = getActionDefinitions(Query.Opcode).apply(Query); 347 if (Step.Action != LegalizeAction::UseLegacyRules) { 348 return Step; 349 } 350 351 return getLegacyLegalizerInfo().getAction(Query); 352 } 353 354 LegalizeActionStep 355 LegalizerInfo::getAction(const MachineInstr &MI, 356 const MachineRegisterInfo &MRI) const { 357 SmallVector<LLT, 8> Types; 358 SmallBitVector SeenTypes(8); 359 ArrayRef<MCOperandInfo> OpInfo = MI.getDesc().operands(); 360 // FIXME: probably we'll need to cache the results here somehow? 361 for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) { 362 if (!OpInfo[i].isGenericType()) 363 continue; 364 365 // We must only record actions once for each TypeIdx; otherwise we'd 366 // try to legalize operands multiple times down the line. 367 unsigned TypeIdx = OpInfo[i].getGenericTypeIndex(); 368 if (SeenTypes[TypeIdx]) 369 continue; 370 371 SeenTypes.set(TypeIdx); 372 373 LLT Ty = getTypeFromTypeIdx(MI, MRI, i, TypeIdx); 374 Types.push_back(Ty); 375 } 376 377 SmallVector<LegalityQuery::MemDesc, 2> MemDescrs; 378 for (const auto &MMO : MI.memoperands()) 379 MemDescrs.push_back({*MMO}); 380 381 return getAction({MI.getOpcode(), Types, MemDescrs}); 382 } 383 384 bool LegalizerInfo::isLegal(const MachineInstr &MI, 385 const MachineRegisterInfo &MRI) const { 386 return getAction(MI, MRI).Action == Legal; 387 } 388 389 bool LegalizerInfo::isLegalOrCustom(const MachineInstr &MI, 390 const MachineRegisterInfo &MRI) const { 391 auto Action = getAction(MI, MRI).Action; 392 // If the action is custom, it may not necessarily modify the instruction, 393 // so we have to assume it's legal. 394 return Action == Legal || Action == Custom; 395 } 396 397 unsigned LegalizerInfo::getExtOpcodeForWideningConstant(LLT SmallTy) const { 398 return SmallTy.isByteSized() ? TargetOpcode::G_SEXT : TargetOpcode::G_ZEXT; 399 } 400 401 /// \pre Type indices of every opcode form a dense set starting from 0. 402 void LegalizerInfo::verify(const MCInstrInfo &MII) const { 403 #ifndef NDEBUG 404 std::vector<unsigned> FailedOpcodes; 405 for (unsigned Opcode = FirstOp; Opcode <= LastOp; ++Opcode) { 406 const MCInstrDesc &MCID = MII.get(Opcode); 407 const unsigned NumTypeIdxs = std::accumulate( 408 MCID.operands().begin(), MCID.operands().end(), 0U, 409 [](unsigned Acc, const MCOperandInfo &OpInfo) { 410 return OpInfo.isGenericType() 411 ? std::max(OpInfo.getGenericTypeIndex() + 1U, Acc) 412 : Acc; 413 }); 414 const unsigned NumImmIdxs = std::accumulate( 415 MCID.operands().begin(), MCID.operands().end(), 0U, 416 [](unsigned Acc, const MCOperandInfo &OpInfo) { 417 return OpInfo.isGenericImm() 418 ? std::max(OpInfo.getGenericImmIndex() + 1U, Acc) 419 : Acc; 420 }); 421 if (VerboseVerifyLegalizerInfo) { 422 LLVM_DEBUG(dbgs() << MII.getName(Opcode) << " (opcode " << Opcode 423 << "): " << NumTypeIdxs << " type ind" 424 << (NumTypeIdxs == 1 ? "ex" : "ices") << ", " 425 << NumImmIdxs << " imm ind" 426 << (NumImmIdxs == 1 ? "ex" : "ices") << "\n"); 427 } 428 const LegalizeRuleSet &RuleSet = getActionDefinitions(Opcode); 429 if (!RuleSet.verifyTypeIdxsCoverage(NumTypeIdxs)) 430 FailedOpcodes.push_back(Opcode); 431 else if (!RuleSet.verifyImmIdxsCoverage(NumImmIdxs)) 432 FailedOpcodes.push_back(Opcode); 433 } 434 if (!FailedOpcodes.empty()) { 435 errs() << "The following opcodes have ill-defined legalization rules:"; 436 for (unsigned Opcode : FailedOpcodes) 437 errs() << " " << MII.getName(Opcode); 438 errs() << "\n"; 439 440 report_fatal_error("ill-defined LegalizerInfo, try " 441 "-debug-only=legalizer-info and " 442 "-verbose-gisel-verify-legalizer-info for details"); 443 } 444 #endif 445 } 446 447 #ifndef NDEBUG 448 // FIXME: This should be in the MachineVerifier, but it can't use the 449 // LegalizerInfo as it's currently in the separate GlobalISel library. 450 // Note that RegBankSelected property already checked in the verifier 451 // has the same layering problem, but we only use inline methods so 452 // end up not needing to link against the GlobalISel library. 453 const MachineInstr *llvm::machineFunctionIsIllegal(const MachineFunction &MF) { 454 if (const LegalizerInfo *MLI = MF.getSubtarget().getLegalizerInfo()) { 455 const MachineRegisterInfo &MRI = MF.getRegInfo(); 456 for (const MachineBasicBlock &MBB : MF) 457 for (const MachineInstr &MI : MBB) 458 if (isPreISelGenericOpcode(MI.getOpcode()) && 459 !MLI->isLegalOrCustom(MI, MRI)) 460 return &MI; 461 } 462 return nullptr; 463 } 464 #endif 465