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