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