465 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// Implement an interface to specify and query how an illegal operation on a10// 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 27using namespace llvm;28using namespace LegalizeActions;29 30#define DEBUG_TYPE "legalizer-info"31 32cl::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 37static 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 43raw_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 85raw_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 NDEBUG100// Make sure the rule won't (trivially) loop forever.101static 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.118static 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 about122 // 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 vectors168 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#endif192 193LegalizeActionStep 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 } else211 LLVM_DEBUG(dbgs() << ".. no match\n");212 }213 LLVM_DEBUG(dbgs() << ".. unsupported\n");214 return {LegalizeAction::Unsupported, 0, LLT{}};215}216 217bool LegalizeRuleSet::verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const {218#ifndef NDEBUG219 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#else244 return true;245#endif246}247 248bool LegalizeRuleSet::verifyImmIdxsCoverage(unsigned NumImmIdxs) const {249#ifndef NDEBUG250 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: " << FirstUncovered268 << ", " << (AllCovered ? "OK" : "FAIL") << "\n");269 }270 return AllCovered;271#else272 return true;273#endif274}275 276/// Helper function to get LLT for the given type index.277static 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 only282 // one source type and one destination type as all destinations must be the283 // 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 289unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {290 assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");291 return Opcode - FirstOp;292}293 294unsigned 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 " << Alias299 << "\n");300 }301 OpcodeIdx = getOpcodeIdxForOpcode(Alias);302 assert(RulesForOpcode[OpcodeIdx].getAlias() == 0 && "Cannot chain aliases");303 }304 305 return OpcodeIdx;306}307 308const LegalizeRuleSet &309LegalizerInfo::getActionDefinitions(unsigned Opcode) const {310 unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);311 return RulesForOpcode[OpcodeIdx];312}313 314LegalizeRuleSet &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 321LegalizeRuleSet &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 336void 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 344LegalizeActionStep345LegalizerInfo::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 354LegalizeActionStep355LegalizerInfo::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'd366 // 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 384bool LegalizerInfo::isLegal(const MachineInstr &MI,385 const MachineRegisterInfo &MRI) const {386 return getAction(MI, MRI).Action == Legal;387}388 389bool 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 397unsigned 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.402void LegalizerInfo::verify(const MCInstrInfo &MII) const {403#ifndef NDEBUG404 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 " << Opcode423 << "): " << 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#endif445}446 447#ifndef NDEBUG448// FIXME: This should be in the MachineVerifier, but it can't use the449// LegalizerInfo as it's currently in the separate GlobalISel library.450// Note that RegBankSelected property already checked in the verifier451// has the same layering problem, but we only use inline methods so452// end up not needing to link against the GlobalISel library.453const 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#endif465