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