| //===- lib/CodeGen/GlobalISel/LegalizerInfo.cpp - Legalizer ---------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // Implement an interface to specify and query how an illegal operation on a |
| // given type should be expanded. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h" |
| #include "llvm/ADT/SmallBitVector.h" |
| #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h" |
| #include "llvm/CodeGen/MachineInstr.h" |
| #include "llvm/CodeGen/MachineOperand.h" |
| #include "llvm/CodeGen/MachineRegisterInfo.h" |
| #include "llvm/CodeGen/TargetOpcodes.h" |
| #include "llvm/MC/MCInstrDesc.h" |
| #include "llvm/MC/MCInstrInfo.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/ErrorHandling.h" |
| #include "llvm/Support/LowLevelTypeImpl.h" |
| #include "llvm/Support/MathExtras.h" |
| #include <algorithm> |
| #include <map> |
| |
| using namespace llvm; |
| using namespace LegalizeActions; |
| |
| #define DEBUG_TYPE "legalizer-info" |
| |
| cl::opt<bool> llvm::DisableGISelLegalityCheck( |
| "disable-gisel-legality-check", |
| cl::desc("Don't verify that MIR is fully legal between GlobalISel passes"), |
| cl::Hidden); |
| |
| raw_ostream &llvm::operator<<(raw_ostream &OS, LegalizeAction Action) { |
| switch (Action) { |
| case Legal: |
| OS << "Legal"; |
| break; |
| case NarrowScalar: |
| OS << "NarrowScalar"; |
| break; |
| case WidenScalar: |
| OS << "WidenScalar"; |
| break; |
| case FewerElements: |
| OS << "FewerElements"; |
| break; |
| case MoreElements: |
| OS << "MoreElements"; |
| break; |
| case Bitcast: |
| OS << "Bitcast"; |
| break; |
| case Lower: |
| OS << "Lower"; |
| break; |
| case Libcall: |
| OS << "Libcall"; |
| break; |
| case Custom: |
| OS << "Custom"; |
| break; |
| case Unsupported: |
| OS << "Unsupported"; |
| break; |
| case NotFound: |
| OS << "NotFound"; |
| break; |
| case UseLegacyRules: |
| OS << "UseLegacyRules"; |
| break; |
| } |
| return OS; |
| } |
| |
| raw_ostream &LegalityQuery::print(raw_ostream &OS) const { |
| OS << Opcode << ", Tys={"; |
| for (const auto &Type : Types) { |
| OS << Type << ", "; |
| } |
| OS << "}, Opcode="; |
| |
| OS << Opcode << ", MMOs={"; |
| for (const auto &MMODescr : MMODescrs) { |
| OS << MMODescr.MemoryTy << ", "; |
| } |
| OS << "}"; |
| |
| return OS; |
| } |
| |
| #ifndef NDEBUG |
| // Make sure the rule won't (trivially) loop forever. |
| static bool hasNoSimpleLoops(const LegalizeRule &Rule, const LegalityQuery &Q, |
| const std::pair<unsigned, LLT> &Mutation) { |
| switch (Rule.getAction()) { |
| case Legal: |
| case Custom: |
| case Lower: |
| case MoreElements: |
| case FewerElements: |
| break; |
| default: |
| return Q.Types[Mutation.first] != Mutation.second; |
| } |
| return true; |
| } |
| |
| // Make sure the returned mutation makes sense for the match type. |
| static bool mutationIsSane(const LegalizeRule &Rule, |
| const LegalityQuery &Q, |
| std::pair<unsigned, LLT> Mutation) { |
| // If the user wants a custom mutation, then we can't really say much about |
| // it. Return true, and trust that they're doing the right thing. |
| if (Rule.getAction() == Custom || Rule.getAction() == Legal) |
| return true; |
| |
| const unsigned TypeIdx = Mutation.first; |
| const LLT OldTy = Q.Types[TypeIdx]; |
| const LLT NewTy = Mutation.second; |
| |
| switch (Rule.getAction()) { |
| case FewerElements: |
| if (!OldTy.isVector()) |
| return false; |
| LLVM_FALLTHROUGH; |
| case MoreElements: { |
| // MoreElements can go from scalar to vector. |
| const unsigned OldElts = OldTy.isVector() ? OldTy.getNumElements() : 1; |
| if (NewTy.isVector()) { |
| if (Rule.getAction() == FewerElements) { |
| // Make sure the element count really decreased. |
| if (NewTy.getNumElements() >= OldElts) |
| return false; |
| } else { |
| // Make sure the element count really increased. |
| if (NewTy.getNumElements() <= OldElts) |
| return false; |
| } |
| } else if (Rule.getAction() == MoreElements) |
| return false; |
| |
| // Make sure the element type didn't change. |
| return NewTy.getScalarType() == OldTy.getScalarType(); |
| } |
| case NarrowScalar: |
| case WidenScalar: { |
| if (OldTy.isVector()) { |
| // Number of elements should not change. |
| if (!NewTy.isVector() || OldTy.getNumElements() != NewTy.getNumElements()) |
| return false; |
| } else { |
| // Both types must be vectors |
| if (NewTy.isVector()) |
| return false; |
| } |
| |
| if (Rule.getAction() == NarrowScalar) { |
| // Make sure the size really decreased. |
| if (NewTy.getScalarSizeInBits() >= OldTy.getScalarSizeInBits()) |
| return false; |
| } else { |
| // Make sure the size really increased. |
| if (NewTy.getScalarSizeInBits() <= OldTy.getScalarSizeInBits()) |
| return false; |
| } |
| |
| return true; |
| } |
| case Bitcast: { |
| return OldTy != NewTy && OldTy.getSizeInBits() == NewTy.getSizeInBits(); |
| } |
| default: |
| return true; |
| } |
| } |
| #endif |
| |
| LegalizeActionStep LegalizeRuleSet::apply(const LegalityQuery &Query) const { |
| LLVM_DEBUG(dbgs() << "Applying legalizer ruleset to: "; Query.print(dbgs()); |
| dbgs() << "\n"); |
| if (Rules.empty()) { |
| LLVM_DEBUG(dbgs() << ".. fallback to legacy rules (no rules defined)\n"); |
| return {LegalizeAction::UseLegacyRules, 0, LLT{}}; |
| } |
| for (const LegalizeRule &Rule : Rules) { |
| if (Rule.match(Query)) { |
| LLVM_DEBUG(dbgs() << ".. match\n"); |
| std::pair<unsigned, LLT> Mutation = Rule.determineMutation(Query); |
| LLVM_DEBUG(dbgs() << ".. .. " << Rule.getAction() << ", " |
| << Mutation.first << ", " << Mutation.second << "\n"); |
| assert(mutationIsSane(Rule, Query, Mutation) && |
| "legality mutation invalid for match"); |
| assert(hasNoSimpleLoops(Rule, Query, Mutation) && "Simple loop detected"); |
| return {Rule.getAction(), Mutation.first, Mutation.second}; |
| } else |
| LLVM_DEBUG(dbgs() << ".. no match\n"); |
| } |
| LLVM_DEBUG(dbgs() << ".. unsupported\n"); |
| return {LegalizeAction::Unsupported, 0, LLT{}}; |
| } |
| |
| bool LegalizeRuleSet::verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const { |
| #ifndef NDEBUG |
| if (Rules.empty()) { |
| LLVM_DEBUG( |
| dbgs() << ".. type index coverage check SKIPPED: no rules defined\n"); |
| return true; |
| } |
| const int64_t FirstUncovered = TypeIdxsCovered.find_first_unset(); |
| if (FirstUncovered < 0) { |
| LLVM_DEBUG(dbgs() << ".. type index coverage check SKIPPED:" |
| " user-defined predicate detected\n"); |
| return true; |
| } |
| const bool AllCovered = (FirstUncovered >= NumTypeIdxs); |
| if (NumTypeIdxs > 0) |
| LLVM_DEBUG(dbgs() << ".. the first uncovered type index: " << FirstUncovered |
| << ", " << (AllCovered ? "OK" : "FAIL") << "\n"); |
| return AllCovered; |
| #else |
| return true; |
| #endif |
| } |
| |
| bool LegalizeRuleSet::verifyImmIdxsCoverage(unsigned NumImmIdxs) const { |
| #ifndef NDEBUG |
| if (Rules.empty()) { |
| LLVM_DEBUG( |
| dbgs() << ".. imm index coverage check SKIPPED: no rules defined\n"); |
| return true; |
| } |
| const int64_t FirstUncovered = ImmIdxsCovered.find_first_unset(); |
| if (FirstUncovered < 0) { |
| LLVM_DEBUG(dbgs() << ".. imm index coverage check SKIPPED:" |
| " user-defined predicate detected\n"); |
| return true; |
| } |
| const bool AllCovered = (FirstUncovered >= NumImmIdxs); |
| LLVM_DEBUG(dbgs() << ".. the first uncovered imm index: " << FirstUncovered |
| << ", " << (AllCovered ? "OK" : "FAIL") << "\n"); |
| return AllCovered; |
| #else |
| return true; |
| #endif |
| } |
| |
| /// Helper function to get LLT for the given type index. |
| static LLT getTypeFromTypeIdx(const MachineInstr &MI, |
| const MachineRegisterInfo &MRI, unsigned OpIdx, |
| unsigned TypeIdx) { |
| assert(TypeIdx < MI.getNumOperands() && "Unexpected TypeIdx"); |
| // G_UNMERGE_VALUES has variable number of operands, but there is only |
| // one source type and one destination type as all destinations must be the |
| // same type. So, get the last operand if TypeIdx == 1. |
| if (MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && TypeIdx == 1) |
| return MRI.getType(MI.getOperand(MI.getNumOperands() - 1).getReg()); |
| return MRI.getType(MI.getOperand(OpIdx).getReg()); |
| } |
| |
| unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const { |
| assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode"); |
| return Opcode - FirstOp; |
| } |
| |
| unsigned LegalizerInfo::getActionDefinitionsIdx(unsigned Opcode) const { |
| unsigned OpcodeIdx = getOpcodeIdxForOpcode(Opcode); |
| if (unsigned Alias = RulesForOpcode[OpcodeIdx].getAlias()) { |
| LLVM_DEBUG(dbgs() << ".. opcode " << Opcode << " is aliased to " << Alias |
| << "\n"); |
| OpcodeIdx = getOpcodeIdxForOpcode(Alias); |
| assert(RulesForOpcode[OpcodeIdx].getAlias() == 0 && "Cannot chain aliases"); |
| } |
| |
| return OpcodeIdx; |
| } |
| |
| const LegalizeRuleSet & |
| LegalizerInfo::getActionDefinitions(unsigned Opcode) const { |
| unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode); |
| return RulesForOpcode[OpcodeIdx]; |
| } |
| |
| LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(unsigned Opcode) { |
| unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode); |
| auto &Result = RulesForOpcode[OpcodeIdx]; |
| assert(!Result.isAliasedByAnother() && "Modifying this opcode will modify aliases"); |
| return Result; |
| } |
| |
| LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder( |
| std::initializer_list<unsigned> Opcodes) { |
| unsigned Representative = *Opcodes.begin(); |
| |
| assert(!llvm::empty(Opcodes) && Opcodes.begin() + 1 != Opcodes.end() && |
| "Initializer list must have at least two opcodes"); |
| |
| for (unsigned Op : llvm::drop_begin(Opcodes)) |
| aliasActionDefinitions(Representative, Op); |
| |
| auto &Return = getActionDefinitionsBuilder(Representative); |
| Return.setIsAliasedByAnother(); |
| return Return; |
| } |
| |
| void LegalizerInfo::aliasActionDefinitions(unsigned OpcodeTo, |
| unsigned OpcodeFrom) { |
| assert(OpcodeTo != OpcodeFrom && "Cannot alias to self"); |
| assert(OpcodeTo >= FirstOp && OpcodeTo <= LastOp && "Unsupported opcode"); |
| const unsigned OpcodeFromIdx = getOpcodeIdxForOpcode(OpcodeFrom); |
| RulesForOpcode[OpcodeFromIdx].aliasTo(OpcodeTo); |
| } |
| |
| LegalizeActionStep |
| LegalizerInfo::getAction(const LegalityQuery &Query) const { |
| LegalizeActionStep Step = getActionDefinitions(Query.Opcode).apply(Query); |
| if (Step.Action != LegalizeAction::UseLegacyRules) { |
| return Step; |
| } |
| |
| return getLegacyLegalizerInfo().getAction(Query); |
| } |
| |
| LegalizeActionStep |
| LegalizerInfo::getAction(const MachineInstr &MI, |
| const MachineRegisterInfo &MRI) const { |
| SmallVector<LLT, 8> Types; |
| SmallBitVector SeenTypes(8); |
| const MCOperandInfo *OpInfo = MI.getDesc().OpInfo; |
| // FIXME: probably we'll need to cache the results here somehow? |
| for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) { |
| if (!OpInfo[i].isGenericType()) |
| continue; |
| |
| // We must only record actions once for each TypeIdx; otherwise we'd |
| // try to legalize operands multiple times down the line. |
| unsigned TypeIdx = OpInfo[i].getGenericTypeIndex(); |
| if (SeenTypes[TypeIdx]) |
| continue; |
| |
| SeenTypes.set(TypeIdx); |
| |
| LLT Ty = getTypeFromTypeIdx(MI, MRI, i, TypeIdx); |
| Types.push_back(Ty); |
| } |
| |
| SmallVector<LegalityQuery::MemDesc, 2> MemDescrs; |
| for (const auto &MMO : MI.memoperands()) |
| MemDescrs.push_back({*MMO}); |
| |
| return getAction({MI.getOpcode(), Types, MemDescrs}); |
| } |
| |
| bool LegalizerInfo::isLegal(const MachineInstr &MI, |
| const MachineRegisterInfo &MRI) const { |
| return getAction(MI, MRI).Action == Legal; |
| } |
| |
| bool LegalizerInfo::isLegalOrCustom(const MachineInstr &MI, |
| const MachineRegisterInfo &MRI) const { |
| auto Action = getAction(MI, MRI).Action; |
| // If the action is custom, it may not necessarily modify the instruction, |
| // so we have to assume it's legal. |
| return Action == Legal || Action == Custom; |
| } |
| |
| unsigned LegalizerInfo::getExtOpcodeForWideningConstant(LLT SmallTy) const { |
| return SmallTy.isByteSized() ? TargetOpcode::G_SEXT : TargetOpcode::G_ZEXT; |
| } |
| |
| /// \pre Type indices of every opcode form a dense set starting from 0. |
| void LegalizerInfo::verify(const MCInstrInfo &MII) const { |
| #ifndef NDEBUG |
| std::vector<unsigned> FailedOpcodes; |
| for (unsigned Opcode = FirstOp; Opcode <= LastOp; ++Opcode) { |
| const MCInstrDesc &MCID = MII.get(Opcode); |
| const unsigned NumTypeIdxs = std::accumulate( |
| MCID.opInfo_begin(), MCID.opInfo_end(), 0U, |
| [](unsigned Acc, const MCOperandInfo &OpInfo) { |
| return OpInfo.isGenericType() |
| ? std::max(OpInfo.getGenericTypeIndex() + 1U, Acc) |
| : Acc; |
| }); |
| const unsigned NumImmIdxs = std::accumulate( |
| MCID.opInfo_begin(), MCID.opInfo_end(), 0U, |
| [](unsigned Acc, const MCOperandInfo &OpInfo) { |
| return OpInfo.isGenericImm() |
| ? std::max(OpInfo.getGenericImmIndex() + 1U, Acc) |
| : Acc; |
| }); |
| LLVM_DEBUG(dbgs() << MII.getName(Opcode) << " (opcode " << Opcode |
| << "): " << NumTypeIdxs << " type ind" |
| << (NumTypeIdxs == 1 ? "ex" : "ices") << ", " |
| << NumImmIdxs << " imm ind" |
| << (NumImmIdxs == 1 ? "ex" : "ices") << "\n"); |
| const LegalizeRuleSet &RuleSet = getActionDefinitions(Opcode); |
| if (!RuleSet.verifyTypeIdxsCoverage(NumTypeIdxs)) |
| FailedOpcodes.push_back(Opcode); |
| else if (!RuleSet.verifyImmIdxsCoverage(NumImmIdxs)) |
| FailedOpcodes.push_back(Opcode); |
| } |
| if (!FailedOpcodes.empty()) { |
| errs() << "The following opcodes have ill-defined legalization rules:"; |
| for (unsigned Opcode : FailedOpcodes) |
| errs() << " " << MII.getName(Opcode); |
| errs() << "\n"; |
| |
| report_fatal_error("ill-defined LegalizerInfo" |
| ", try -debug-only=legalizer-info for details"); |
| } |
| #endif |
| } |
| |
| #ifndef NDEBUG |
| // FIXME: This should be in the MachineVerifier, but it can't use the |
| // LegalizerInfo as it's currently in the separate GlobalISel library. |
| // Note that RegBankSelected property already checked in the verifier |
| // has the same layering problem, but we only use inline methods so |
| // end up not needing to link against the GlobalISel library. |
| const MachineInstr *llvm::machineFunctionIsIllegal(const MachineFunction &MF) { |
| if (const LegalizerInfo *MLI = MF.getSubtarget().getLegalizerInfo()) { |
| const MachineRegisterInfo &MRI = MF.getRegInfo(); |
| for (const MachineBasicBlock &MBB : MF) |
| for (const MachineInstr &MI : MBB) |
| if (isPreISelGenericOpcode(MI.getOpcode()) && |
| !MLI->isLegalOrCustom(MI, MRI)) |
| return &MI; |
| } |
| return nullptr; |
| } |
| #endif |