diff --git a/llvm/include/llvm/CodeGen/GlobalISel/RegBankSelect.h b/llvm/include/llvm/CodeGen/GlobalISel/RegBankSelect.h --- a/llvm/include/llvm/CodeGen/GlobalISel/RegBankSelect.h +++ b/llvm/include/llvm/CodeGen/GlobalISel/RegBankSelect.h @@ -63,6 +63,7 @@ #ifndef LLVM_CODEGEN_GLOBALISEL_REGBANKSELECT_H #define LLVM_CODEGEN_GLOBALISEL_REGBANKSELECT_H +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h" #include "llvm/CodeGen/GlobalISel/RegisterBankInfo.h" @@ -98,7 +99,11 @@ /// Greedily minimize the cost of assigning register banks. /// This should produce code of greater quality, but will /// require more compile time. - Greedy + Greedy, + /// Globally minimize the cost of assigning register banks. + /// This should increase code quality, but at the cost of + /// longer compile time. + Global }; /// Abstract class used to represent an insertion point in a CFG. @@ -457,6 +462,30 @@ /// impossible mapping. static MappingCost ImpossibleCost(); + /// Return this cost a single value. This value saturates in case of + /// overflow. + uint64_t getFlattenedValue() const { + uint64_t FlattenedValue = LocalFreq * LocalCost; + if (LocalFreq > 0 && FlattenedValue < LocalCost) { + return UINT64_MAX; + } + FlattenedValue += NonLocalCost; + if (FlattenedValue < NonLocalCost) { + return UINT64_MAX; + } + return FlattenedValue; + } + + /// Return this cost a single value without taking the frequency into + /// account. This value saturates in case of overflow. + uint64_t getFlattenedValueWithoutFreq() const { + uint64_t FlattenedValue = LocalCost + NonLocalCost; + if (FlattenedValue < LocalCost) { + return UINT64_MAX; + } + return FlattenedValue; + } + /// Check if this is less than \p Cost. bool operator<(const MappingCost &Cost) const; /// Check if this is equal to \p Cost. @@ -467,6 +496,10 @@ bool operator>(const MappingCost &Cost) const { return *this != Cost && Cost < *this; } + /// Check if this is greater than or equal to \p Cost. + bool operator>=(const MappingCost &Cost) const { + return !(*this < Cost); + } /// Print this on dbgs() stream. void dump() const; @@ -481,6 +514,50 @@ } }; + /// Determines the state of an InstructionMapping. + enum InstrMapStatus { + /// This mapping should not be considered. + NOTHING, + /// This mapping has been selected. + SELECTED, + /// This mapping is needed and therefore will be selected at a later point. + USED + }; + + /// Convenient types to represent vectors with different content but equal + /// lengths. + /// TODO: use MappingCost for costs + using InstrMapCosts = SmallVector; + using InstrMapScores = SmallVector; + using InstrMapDestRegBanks = SmallVector; + using InstrMapDestRegisters = SmallVector; + using InstrMapStatuses = SmallVector; + + /// Contains the global regbank-select state for an instruction. + struct GlobalStateOfInstr { + /// The instruction of this state. + MachineInstr &MI; + + /// The InstructionMappings available for this instruction. + RegisterBankInfo::InstructionMappings Mappings; + + /// The register bank of each InstructionMapping. + InstrMapDestRegBanks DestRBs; + + /// The cost of applying each InstructionMapping. + InstrMapCosts Costs; + + /// The total utility score of each InstructionMapping. The utility score + /// is the sum of the costs of all instructions that make use of a given + /// InstructionMapping. + InstrMapScores UtilScores; + + /// The current status of each InstructionMapping. + InstrMapStatuses Statuses; + + GlobalStateOfInstr(MachineInstr &MI) : MI(MI) {} + }; + /// Interface to the target lowering info related /// to register banks. const RegisterBankInfo *RBI = nullptr; @@ -503,6 +580,9 @@ /// Current optimization remark emitter. Used to report failures. std::unique_ptr MORE; + /// Global regbank-select state for a particular instruction. + DenseMap GSIMIMap; + /// Helper class used for every code morphing. MachineIRBuilder MIRBuilder; @@ -512,9 +592,10 @@ /// Current target configuration. Controls how the pass handles errors. const TargetPassConfig *TPC; - /// Assign the register bank of each operand of \p MI. + /// Assign the register bank of each operand of \p MI. This is used in fast + /// or greedy mode. /// \return True on success, false otherwise. - bool assignInstr(MachineInstr &MI); + bool assignInstrLocal(MachineInstr &MI); /// Initialize the field members using \p MF. void init(MachineFunction &MF); @@ -594,6 +675,21 @@ SmallVectorImpl &RepairPts, const MappingCost *BestCost = nullptr); + /// Compute the repairing placement for applying \p InstrMapping to \p MI. + /// This clears \p RepairPts before adding new placements. + /// \return True if repairs were successfully computed. + bool computeRepair(MachineInstr &MI, + const RegisterBankInfo::InstructionMapping &InstrMapping, + SmallVectorImpl &RepairPts); + + /// Compute the repairing placement for applying \p ValMapping to operand at + /// \p OpIdx in \p MI. + /// \return True if repairs were successfully computed. + bool computeRepair(MachineInstr &MI, + const RegisterBankInfo::ValueMapping &ValMapping, + unsigned OpIdx, + SmallVectorImpl &RepairPts); + /// When \p RepairPt involves splitting to repair \p MO for the /// given \p ValMapping, try to change the way we repair such that /// the splitting is not required anymore. @@ -614,6 +710,62 @@ const RegisterBankInfo::InstructionMapping &InstrMapping, SmallVectorImpl &RepairPts); + /// Make a single pass over the instructions and select register banks. This + /// is run when in Fast or Greedy mode. + void selectRegBanksSinglePass(MachineFunction &MF); + + /// Make multiple passes over the instructions: + /// 1. Compute the costs of selecting a particular register bank (top down). + /// 2. Find the selection of register banks (bottom up). + /// 3. Assign register banks (top down). + /// This is run when in Global mode. + void selectRegBanksMultiPass(MachineFunction &MF); + + /// Clears all variables used for containing the global regbank-select state. + void clearGlobalState(); + + /// Check if \p MI has a global regbank-select state associated with it. + bool hasGSIOfMI(MachineInstr &MI); + + /// Get the global regbank-select state associated with \p MI. + GlobalStateOfInstr &getGSIOfMI(MachineInstr &MI); + + /// Get the global regbank-select state associated with the instruction that + /// defines \p Reg. + GlobalStateOfInstr &getGSIOfDefOfReg(Register Reg); + + unsigned getIdxOfMatchingDestRegBank(GlobalStateOfInstr &GSI, + const RegisterBank *DesiredRegBank); + + /// Compute cost for the given instruction and mappings. If \p Mappings + /// contains a \p NULL entry, then the instruction will be treated as an + /// instruction whose operands use registers that have been pre-assigned + /// either a register bank or register class. + /// \return True if successful, false otherwise. + bool computeGlobalCost(MachineInstr &MI, + RegisterBankInfo::InstructionMappings &Mappings); + + /// Mark the corresponding InstructionMapping of each operand in the given + /// InstructionMapping as used. + void markOperandsAsUsed(MachineInstr &MI, unsigned Score, + const RegisterBankInfo::InstructionMapping *IMap); + + /// Selects the \p InstructionMapping with lowest cost for the given \p MI. + bool selectGlobalInstrMapping(MachineInstr &MI); + + /// Compute lowest cost for getting the value associated with the given \p GSI + /// into the desired register bank. The cost is cached in \p GSI for + /// subsequent lookups. + /// \return Lowest cost. + MappingCost + computeLowestCostOfDstInRegBank(GlobalStateOfInstr &GSI, + const RegisterBank *DesiredRegBank); + + /// Assign the register bank of each operand of \p MI. This is used in global + /// mode. + /// \return True on success, false otherwise. + bool assignInstrGlobal(MachineInstr &MI); + public: /// Create a RegBankSelect pass with the specified \p RunningMode. RegBankSelect(Mode RunningMode = Fast); diff --git a/llvm/include/llvm/CodeGen/GlobalISel/RegisterBankInfo.h b/llvm/include/llvm/CodeGen/GlobalISel/RegisterBankInfo.h --- a/llvm/include/llvm/CodeGen/GlobalISel/RegisterBankInfo.h +++ b/llvm/include/llvm/CodeGen/GlobalISel/RegisterBankInfo.h @@ -534,6 +534,13 @@ const InstructionMapping &getInvalidInstructionMapping() const { return getInstructionMappingImpl(/*IsInvalid*/ true); } + + /// Method to get a InstructionMapping that corresponds to a given + /// MachineInstruction. + const InstructionMapping & + getInstructionMapping(unsigned ID, unsigned Cost, const MachineInstr &MI, + const MachineRegisterInfo &MRI, + const TargetRegisterInfo &TRI) const; /// @} /// Get the register bank for the \p OpIdx-th operand of \p MI form diff --git a/llvm/include/llvm/CodeGen/MachineOperand.h b/llvm/include/llvm/CodeGen/MachineOperand.h --- a/llvm/include/llvm/CodeGen/MachineOperand.h +++ b/llvm/include/llvm/CodeGen/MachineOperand.h @@ -317,6 +317,9 @@ /// isReg - Tests if this is a MO_Register operand. bool isReg() const { return OpKind == MO_Register; } + /// isVirtualReg - Tests if this is a MO_Register operand and that its + /// register is virtual. + bool isVirtualReg() const { return isReg() && getReg().isVirtual(); } /// isImm - Tests if this is a MO_Immediate operand. bool isImm() const { return OpKind == MO_Immediate; } /// isCImm - Test if this is a MO_CImmediate operand. diff --git a/llvm/lib/CodeGen/GlobalISel/RegBankSelect.cpp b/llvm/lib/CodeGen/GlobalISel/RegBankSelect.cpp --- a/llvm/lib/CodeGen/GlobalISel/RegBankSelect.cpp +++ b/llvm/lib/CodeGen/GlobalISel/RegBankSelect.cpp @@ -56,7 +56,9 @@ cl::values(clEnumValN(RegBankSelect::Mode::Fast, "regbankselect-fast", "Run the Fast mode (default mapping)"), clEnumValN(RegBankSelect::Mode::Greedy, "regbankselect-greedy", - "Use the Greedy mode (best local mapping)"))); + "Use the Greedy mode (better local mapping)"), + clEnumValN(RegBankSelect::Mode::Global, "regbankselect-global", + "Use the Global mode (better global mapping)"))); char RegBankSelect::ID = 0; @@ -472,37 +474,25 @@ Register Reg = MO.getReg(); if (!Reg) continue; - LLVM_DEBUG(dbgs() << "Opd" << OpIdx << '\n'); + LLVM_DEBUG(dbgs() << "Opd " << OpIdx << '\n'); + + // Compute repairing placement, if needed. const RegisterBankInfo::ValueMapping &ValMapping = InstrMapping.getOperandMapping(OpIdx); - // If Reg is already properly mapped, this is free. - bool Assign; - if (assignmentMatch(Reg, ValMapping, Assign)) { - LLVM_DEBUG(dbgs() << "=> is free (match).\n"); - continue; + unsigned NumPrevRepairs = RepairPts.size(); + if (!computeRepair(MI, ValMapping, OpIdx, RepairPts)) { + return MappingCost::ImpossibleCost(); } - if (Assign) { - LLVM_DEBUG(dbgs() << "=> is free (simple assignment).\n"); - RepairPts.emplace_back(RepairingPlacement(MI, OpIdx, *TRI, *this, - RepairingPlacement::Reassign)); + unsigned NumAddedRepairs = RepairPts.size() - NumPrevRepairs; + if (NumAddedRepairs == 0) { continue; } - - // Find the insertion point for the repairing code. - RepairPts.emplace_back( - RepairingPlacement(MI, OpIdx, *TRI, *this, RepairingPlacement::Insert)); + assert(NumAddedRepairs == 1 && + "Cannot handle situation when multiple repairing placements has " \ + "been added!"); RepairingPlacement &RepairPt = RepairPts.back(); - - // If we need to split a basic block to materialize this insertion point, - // we may give a higher cost to this mapping. - // Nevertheless, we may get away with the split, so try that first. - if (RepairPt.hasSplit()) - tryAvoidingSplit(RepairPt, MO, ValMapping); - - // Check that the materialization of the repairing is possible. - if (!RepairPt.canMaterialize()) { - LLVM_DEBUG(dbgs() << "Mapping involves impossible repairing\n"); - return MappingCost::ImpossibleCost(); + if (RepairPt.getKind() != RepairingPlacement::Insert) { + continue; } // Account for the split cost and repair cost. @@ -578,6 +568,74 @@ return Cost; } +bool RegBankSelect::computeRepair( + MachineInstr &MI, const RegisterBankInfo::InstructionMapping &InstrMapping, + SmallVectorImpl &RepairPts) { + RepairPts.clear(); + + LLVM_DEBUG(dbgs() << " - Compute repairs for " << MI); + + for (unsigned OpIdx = 0, EndOpIdx = InstrMapping.getNumOperands(); + OpIdx != EndOpIdx; ++OpIdx) { + LLVM_DEBUG(dbgs() << " - Operand " << OpIdx << '\n'); + + // Compute repairing placement, if needed. + const RegisterBankInfo::ValueMapping &ValMapping = + InstrMapping.getOperandMapping(OpIdx); + if (!computeRepair(MI, ValMapping, OpIdx, RepairPts)) { + return false; + } + } + + return true; +} + +bool RegBankSelect::computeRepair( + MachineInstr &MI, const RegisterBankInfo::ValueMapping &ValMapping, + unsigned OpIdx, SmallVectorImpl &RepairPts) { + const MachineOperand &MO = MI.getOperand(OpIdx); + if (!MO.isReg()) { + return true; + } + Register Reg = MO.getReg(); + if (!Reg) { + return true; + } + + // If Reg is already properly mapped, this is free. + bool Assign; + if (assignmentMatch(Reg, ValMapping, Assign)) { + LLVM_DEBUG(dbgs() << "=> matching assignment (free).\n"); + return true; + } + if (Assign) { + LLVM_DEBUG(dbgs() << "=> simple assignment (free).\n"); + RepairPts.emplace_back(RepairingPlacement(MI, OpIdx, *TRI, *this, + RepairingPlacement::Reassign)); + return true; + } + + // Find the insertion point for the repairing code. + LLVM_DEBUG(dbgs() << "=> repair code (not free).\n"); + RepairPts.emplace_back( + RepairingPlacement(MI, OpIdx, *TRI, *this, RepairingPlacement::Insert)); + RepairingPlacement &RepairPt = RepairPts.back(); + + // If we need to split a basic block to materialize this insertion point, we + // may give a higher cost to this mapping. Nevertheless, we may get away with + // the split, so try that first. + if (RepairPt.hasSplit()) + tryAvoidingSplit(RepairPt, MO, ValMapping); + + // Check that the materialization of the repairing is possible. + if (!RepairPt.canMaterialize()) { + LLVM_DEBUG(dbgs() << "Mapping involves impossible repairing\n"); + return false; + } + + return true; +} + bool RegBankSelect::applyMapping( MachineInstr &MI, const RegisterBankInfo::InstructionMapping &InstrMapping, SmallVectorImpl &RepairPts) { @@ -620,7 +678,7 @@ return true; } -bool RegBankSelect::assignInstr(MachineInstr &MI) { +bool RegBankSelect::assignInstrLocal(MachineInstr &MI) { LLVM_DEBUG(dbgs() << "Assign: " << MI); // Remember the repairing placement for all the operands. SmallVector RepairPts; @@ -649,63 +707,193 @@ return applyMapping(MI, *BestMapping, RepairPts); } -bool RegBankSelect::runOnMachineFunction(MachineFunction &MF) { - // If the ISel pipeline failed, do not bother running that pass. - if (MF.getProperties().hasProperty( - MachineFunctionProperties::Property::FailedISel)) - return false; - - LLVM_DEBUG(dbgs() << "Assign register banks for: " << MF.getName() << '\n'); - const Function &F = MF.getFunction(); - Mode SaveOptMode = OptMode; - if (F.hasOptNone()) - OptMode = Mode::Fast; - init(MF); - -#ifndef NDEBUG - // Check that our input is fully legal: we require the function to have the - // Legalized property, so it should be. - // FIXME: This should be in the MachineVerifier. - if (!DisableGISelLegalityCheck) - if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) { - reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect", - "instruction is not legal", *MI); - return false; - } -#endif +static inline bool isUnassignableMachineInstr(const MachineInstr &MI) { + return + // Ignore target-specific post-isel instructions: they should use proper + // regclasses. + (isTargetSpecificOpcode(MI.getOpcode()) && !MI.isPreISelOpcode()) || + // Ignore inline asm instructions: they should use physical + // registers/regclasses. + MI.isInlineAsm() || + // Ignore debug info. + MI.isDebugInstr(); +} +void RegBankSelect::selectRegBanksSinglePass(MachineFunction &MF) { // Walk the function and assign register banks to all operands. // Use a RPOT to make sure all registers are assigned before we choose // the best mapping of the current instruction. - ReversePostOrderTraversal RPOT(&MF); + ReversePostOrderTraversal RPOT(&MF); for (MachineBasicBlock *MBB : RPOT) { - // Set a sensible insertion point so that subsequent calls to - // MIRBuilder. + // Set a sensible insertion point for subsequent calls to MIRBuilder. MIRBuilder.setMBB(*MBB); for (MachineBasicBlock::iterator MII = MBB->begin(), End = MBB->end(); MII != End;) { // MI might be invalidated by the assignment, so move the - // iterator before hand. + // iterator beforehand. MachineInstr &MI = *MII++; - // Ignore target-specific post-isel instructions: they should use proper - // regclasses. - if (isTargetSpecificOpcode(MI.getOpcode()) && !MI.isPreISelOpcode()) + if (isUnassignableMachineInstr(MI)) { + continue; + } + + if (!assignInstrLocal(MI)) { + reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect", + "unable to map instruction", MI); + return; + } + + // It's possible the mapping changed control flow, and moved the following + // instruction to a new block, so figure out the new parent. + if (MII != End) { + MachineBasicBlock *NextInstBB = MII->getParent(); + if (NextInstBB != MBB) { + LLVM_DEBUG(dbgs() << "Instruction mapping changed control flow\n"); + MBB = NextInstBB; + MIRBuilder.setMBB(*MBB); + End = MBB->end(); + } + } + } + } +} + +void RegBankSelect::selectRegBanksMultiPass(MachineFunction &MF) { + // Compute the costs of selecting a particular register bank. Walk the + // instructions top-down to make sure all registers have been assigned costs + // before computing cost of current instruction. + LLVM_DEBUG(dbgs() << "Computing costs...\n"); + ReversePostOrderTraversal RPOT(&MF); + for (MachineBasicBlock *MBB : RPOT) { + // Set a sensible insertion point for subsequent calls to MIRBuilder. + MIRBuilder.setMBB(*MBB); + for (MachineBasicBlock::iterator MII = MBB->begin(), End = MBB->end(); + MII != End; ) { + // MI might be invalidated by the assignment, so move the iterator + // beforehand. + MachineInstr &MI = *MII++; + + if (isUnassignableMachineInstr(MI)) { + continue; + } + + RegisterBankInfo::InstructionMappings PossibleMappings; + PossibleMappings = RBI->getInstrPossibleMappings(MI); + if (PossibleMappings.empty()) { + reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect", + "unable to find mappings for instruction", MI); + return; + } + + LLVM_DEBUG(dbgs() << "- Processing " << MI); + + if (!computeGlobalCost(MI, PossibleMappings)) { + reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect", + "unable to compute cost for instruction", MI); + return; + } + + // If there is only one mapping, select it directly. This is primarily to + // get expected result for targets that only return one mapping instead of + // all possible mappings, and the single mapping returned assumes that all + // input operands have already been assigned. + if (PossibleMappings.size() == 1) { + LLVM_DEBUG(dbgs() << " Has only one mapping, select it now\n"); + auto &GSI = getGSIOfMI(MI); + GSI.Statuses[0] = SELECTED; + const auto &SelectedMapping = GSI.Mappings[0]; + assert(SelectedMapping->verify(MI) && "Invalid instruction mapping"); + SmallVector RepairPts; + if (!computeRepair(MI, *SelectedMapping, RepairPts)) { + reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect", + "unable to compute repairs for instruction", MI); + } + if (!applyMapping(MI, *SelectedMapping, RepairPts)) { + reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect", + "unable to apply mapping for instruction", MI); + } + } + + // It's possible the mapping changed control flow, and moved the following + // instruction to a new block, so figure out the new parent. + if (MII != End) { + MachineBasicBlock *NextInstBB = MII->getParent(); + if (NextInstBB != MBB) { + LLVM_DEBUG(dbgs() << "Instruction mapping changed control flow\n"); + MBB = NextInstBB; + MIRBuilder.setMBB(*MBB); + End = MBB->end(); + } + } + } + } + + // Find selection of register banks. Walk the instructions bottom-up to make + // sure that that all uses of a register have been selected before selecting + // the register bank of the current instruction. + LLVM_DEBUG(dbgs() << "Selecting register bank selection...\n"); + for (MachineBasicBlock *MBB : post_order(&MF)) { + if (MBB->empty()) { + continue; + } + + bool ReachedBegin = false; + for (auto MII = std::prev(MBB->end()), Begin = MBB->begin(); !ReachedBegin; + MII--) { + if (MII == Begin) { + ReachedBegin = true; + } + + auto &MI = *MII; + if (isUnassignableMachineInstr(MI)) { + continue; + } + + LLVM_DEBUG(dbgs() << "- Processing " << MI); + if (!hasGSIOfMI(MI)) { + LLVM_DEBUG(dbgs() << " Part of repair, do not process\n"); continue; + } + if (getGSIOfMI(MI).Mappings.size() == 1) { + LLVM_DEBUG(dbgs() << " Only one mapping, already selected\n"); + continue; + } - // Ignore inline asm instructions: they should use physical - // registers/regclasses - if (MI.isInlineAsm()) + if (!selectGlobalInstrMapping(MI)) { + reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect", + "unable to select register banks", MI); + } + } + } + + // Assign instructions. Walk the instructions top down. + LLVM_DEBUG(dbgs() << "Assigning instructions...\n"); + for (MachineBasicBlock *MBB : RPOT) { + // Set a sensible insertion point for subsequent calls to MIRBuilder. + MIRBuilder.setMBB(*MBB); + for (MachineBasicBlock::iterator MII = MBB->begin(), End = MBB->end(); + MII != End; ) { + // MI might be invalidated by the assignment, so move the iterator + // beforehand. + MachineInstr &MI = *MII++; + + if (isUnassignableMachineInstr(MI)) { continue; + } - // Ignore debug info. - if (MI.isDebugInstr()) + LLVM_DEBUG(dbgs() << "- Processing " << MI); + if (!hasGSIOfMI(MI)) { + LLVM_DEBUG(dbgs() << " Part of repair, do not process\n"); + continue; + } + if (getGSIOfMI(MI).Mappings.size() == 1) { + LLVM_DEBUG(dbgs() << " Only one mapping, already selected\n"); continue; + } - if (!assignInstr(MI)) { + if (!assignInstrGlobal(MI)) { reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect", - "unable to map instruction", MI); - return false; + "unable to assign instruction", MI); } // It's possible the mapping changed control flow, and moved the following @@ -722,6 +910,334 @@ } } + clearGlobalState(); +} + +static inline const RegisterBank * +getRegBankOfOpInInstrMap(const RegisterBankInfo::InstructionMapping *InstrMap, + unsigned Opx) { + assert(InstrMap->getNumOperands() >= Opx && + "InstructionMapping has too few operands!"); + const auto &ValMap = InstrMap->getOperandMapping(Opx); + assert(ValMap.NumBreakDowns > 0 && "No breakdowns in ValueMapping!"); + return ValMap.BreakDown[0].RegBank; +} + +static inline bool +isAssignableReg(Register Reg, const MachineRegisterInfo &MRI) { + return MRI.getRegClassOrNull(Reg) || MRI.getRegBankOrNull(Reg); +} + +unsigned +RegBankSelect::getIdxOfMatchingDestRegBank(GlobalStateOfInstr &GSI, + const RegisterBank *DesiredRegBank) { + unsigned Idx = 0; + const unsigned NumIMaps = GSI.DestRBs.size(); + assert(NumIMaps > 0 && "Instruction has no destination register banks!"); + for (; Idx < NumIMaps; ++Idx) { + if (GSI.DestRBs[Idx] == DesiredRegBank) { + return Idx; + } + } + llvm_unreachable("Found no InstructionMapping with matching register bank!"); +} + +RegBankSelect::MappingCost RegBankSelect::computeLowestCostOfDstInRegBank( + GlobalStateOfInstr &GSI, + const RegisterBank *DesiredRegBank) { + auto &MI = GSI.MI; + LLVM_DEBUG(dbgs() << " DefMI: " << MI); + + auto &Mappings = GSI.Mappings; + assert(Mappings.size() > 0 && "No InstructionMappings found!"); + assert(Mappings.size() == GSI.DestRBs.size() && "Mismatching sizes!"); + assert(Mappings.size() == GSI.Costs.size() && "Mismatching sizes!"); + + // Find dst with matching register bank + for (unsigned Idx = 0; Idx < Mappings.size(); ++Idx) { + if (GSI.DestRBs[Idx] == DesiredRegBank) { + auto &Cost = GSI.Costs[Idx]; + LLVM_DEBUG(dbgs() << " Found register bank match at cost " << Cost + << "\n"); + return Cost; + } + } + + // No match found. Find lowest cost of converting dest to register bank. + LLVM_DEBUG(dbgs() << " No matching register bank found\n"); + assert(MI.getNumExplicitDefs() > 0 && "Instruction has no defs!"); + Register DestReg = MI.getOperand(0).getReg(); + int BestIdx = -1; + const MappingCost ImpossibleCost = MappingCost::ImpossibleCost(); + MappingCost BestCost = ImpossibleCost; + for (unsigned Idx = 0; Idx < Mappings.size(); ++Idx) { + MappingCost Cost = GSI.Costs[Idx]; + + LLVM_DEBUG(dbgs() << " - InstructionMapping: " << *Mappings[Idx] << + "\n"); + LLVM_DEBUG(dbgs() << " Cost: " << Cost << "\n"); + + // Skip mappings that already has too high cost. + if (Cost >= BestCost) { + LLVM_DEBUG(dbgs() << " Too expensive mapping\n"); + continue; + } + + assert(MI.getNumExplicitDefs() > 0 && "Instruction has no defs!"); + const RegisterBank *CurRegBank = + getRegBankOfOpInInstrMap(GSI.Mappings[Idx], 0); + unsigned CopyCost = RBI->copyCost(*DesiredRegBank, *CurRegBank, + RBI->getSizeInBits(DestReg, *MRI, *TRI)); + // TODO: use a dedicated constant for impossible copy cost. + if (CopyCost == std::numeric_limits::max()) { + LLVM_DEBUG(dbgs() << " No such copy\n"); + continue; + } + LLVM_DEBUG(dbgs() << " Cost of copying: " << CopyCost << "\n"); + Cost.addLocalCost(CopyCost); + if (Cost < BestCost) { + BestIdx = Idx; + BestCost = Cost; + LLVM_DEBUG(dbgs() << " * New best cost: " << BestCost << "\n"); + } + } + assert(BestIdx >= 0 && "No register bank conversion found!"); + LLVM_DEBUG(dbgs() << " Best InstructionMapping: " << *Mappings[BestIdx] + << "\n"); + + // Make new entry for converting register bank for dest. + Mappings.emplace_back(Mappings[BestIdx]); + GSI.DestRBs.emplace_back(DesiredRegBank); + GSI.Costs.emplace_back(BestCost); + GSI.UtilScores.emplace_back(0); + GSI.Statuses.emplace_back(NOTHING); + + return BestCost; +} + +bool RegBankSelect::computeGlobalCost( + MachineInstr &MI, RegisterBankInfo::InstructionMappings &Mappings) { + auto Res = GSIMIMap.try_emplace(&MI, MI); + auto &GSI = (*Res.first).second; + + // Compute costs for each InstructionMapping + for (const auto *IMap : Mappings) { + LLVM_DEBUG(dbgs() << " - Processing mapping "; IMap->print(dbgs()); + dbgs() << "\n"); + + // Start with cost of instruction itself. + MappingCost Cost(MBFI ? MBFI->getBlockFreq(MI.getParent()) : 1); + Cost.addLocalCost(IMap->getCost()); + + // Add cost for getting each operand into the right register bank. For each + // operand, this cost is the cost of producing the operand plus the cost of + // putting it in the right register bank. + // + // NOTE: We could get a more accurate cost by simulating a repair, but that + // would be more expensive (and the question is whether that's worth it). + const unsigned NumOps = IMap->getNumOperands(); + for (unsigned Opx = MI.getNumExplicitDefs(); Opx < NumOps; ++Opx) { + auto MO = MI.getOperand(Opx); + if (!MO.isVirtualReg() || !isAssignableReg(MO.getReg(), *MRI)) { + continue; + } + + LLVM_DEBUG(dbgs() << " - Operand: " << Opx << "\n"); + + const RegisterBank *RB = getRegBankOfOpInInstrMap(IMap, Opx); + auto &GSI = getGSIOfDefOfReg(MO.getReg()); + MappingCost DefMICost = computeLowestCostOfDstInRegBank(GSI, RB); + LLVM_DEBUG(dbgs() << " Cost of operand: " << DefMICost << "\n"); + uint64_t FlattenedDefMICost = DefMICost.getFlattenedValueWithoutFreq(); + LLVM_DEBUG(dbgs() << " Amount to count towards mapping cost: " << + FlattenedDefMICost << "\n"); + Cost.addLocalCost(FlattenedDefMICost); + } + LLVM_DEBUG(dbgs() << " Cost of mapping: " << Cost << "\n"); + + bool HasDest = MI.getNumExplicitDefs() > 0; + const RegisterBank *DestRB = + HasDest ? getRegBankOfOpInInstrMap(IMap, 0) : nullptr; + GSI.Mappings.emplace_back(IMap); + GSI.Costs.emplace_back(Cost); + GSI.UtilScores.emplace_back(0); + GSI.DestRBs.emplace_back(DestRB); + GSI.Statuses.emplace_back(NOTHING); + } + + return true; +} + +void RegBankSelect::markOperandsAsUsed( + MachineInstr &MI, unsigned Score, + const RegisterBankInfo::InstructionMapping *IMap) { + const unsigned NumOps = IMap->getNumOperands(); + for (unsigned Opx = MI.getNumExplicitDefs(); Opx < NumOps; ++Opx) { + MachineOperand &MO = MI.getOperand(Opx); + if (!MO.isVirtualReg() || !isAssignableReg(MO.getReg(), *MRI)) { + continue; + } + + const RegisterBank *RB = getRegBankOfOpInInstrMap(IMap, Opx); + LLVM_DEBUG(dbgs() << " - Operand: " << Opx << ", reg bank: " << *RB + << "\n"); + + auto &GSI = getGSIOfDefOfReg(MO.getReg()); + unsigned MapIdx = getIdxOfMatchingDestRegBank(GSI, RB); + uint64_t UtilScore = GSI.UtilScores[MapIdx] + Score; + if (UtilScore < Score) { + // Sum has overflown; saturate value. + UtilScore = UINT64_MAX; + } + GSI.UtilScores[MapIdx] = UtilScore; + if (GSI.Statuses[MapIdx] == NOTHING) { + GSI.Statuses[MapIdx] = USED; + } + } +} + +bool RegBankSelect::hasGSIOfMI(MachineInstr &MI) { + auto DI = GSIMIMap.find(&MI); + return DI != GSIMIMap.end(); +} + +RegBankSelect::GlobalStateOfInstr &RegBankSelect::getGSIOfMI(MachineInstr &MI) { + auto DI = GSIMIMap.find(&MI); + assert(DI != GSIMIMap.end() && "No such instruction in GSIMIMap!"); + return DI->second; +} + +RegBankSelect::GlobalStateOfInstr & +RegBankSelect::getGSIOfDefOfReg(Register Reg) { + MachineInstr *DefMI = MRI->getVRegDef(Reg); + assert(DefMI && "No defining instruction"); + return getGSIOfMI(*DefMI); +} + +bool RegBankSelect::selectGlobalInstrMapping(MachineInstr &MI) { + auto &GSI = getGSIOfMI(MI); + + // Determine whether this instruction is a leaf in the data-flow graph. + const unsigned NumIMaps = GSI.Mappings.size(); + assert(NumIMaps > 0 && "Instruction has no InstructionMappings!"); + bool HasUses = false; + for (unsigned Idx = 0; Idx < NumIMaps; ++Idx) { + int Status = GSI.Statuses[Idx]; + if (Status == USED) { + HasUses = true; + break; + } + } + + int BestIdx = -1; + if (HasUses) { + LLVM_DEBUG(dbgs() << " Looking for mapping with highest utility score\n"); + uint64_t BestScore = 0; + for (unsigned Idx = 0; Idx < NumIMaps; ++Idx) { + if (GSI.Statuses[Idx] != USED) { + continue; + } + const uint64_t Score = GSI.UtilScores[Idx]; + if (BestIdx < 0 || Score > BestScore) { + BestScore = Score; + BestIdx = Idx; + } + } + } + else { + LLVM_DEBUG(dbgs() << " Looking for mapping with lowest cost\n"); + MappingCost BestCost = MappingCost::ImpossibleCost(); + for (unsigned Idx = 0; Idx < NumIMaps; ++Idx) { + const MappingCost &Cost = GSI.Costs[Idx]; + if (Cost < BestCost) { + BestCost = Cost; + BestIdx = Idx; + } + } + } + assert(BestIdx >= 0 && "No mapping found!"); + + GSI.Statuses[BestIdx] = SELECTED; + const auto *Mapping = GSI.Mappings[BestIdx]; + MappingCost Cost = GSI.Costs[BestIdx]; + LLVM_DEBUG(dbgs() << " * Selecting "; Mapping->print(dbgs())); + if (HasUses) { + uint64_t Score = GSI.UtilScores[BestIdx]; + LLVM_DEBUG(dbgs() << ", score: " << Score << "\n"); + } else { + LLVM_DEBUG(dbgs() << ", cost: " << Cost << "\n"); + + } + markOperandsAsUsed(MI, Cost.getFlattenedValue(), Mapping); + + return true; +} + +bool RegBankSelect::assignInstrGlobal(MachineInstr &MI) { + auto &GSI = getGSIOfMI(MI); + + // Find selected instruction mapping. + int SelectedIdx = -1; + for (unsigned Idx = 0, NumIMaps = GSI.Mappings.size(); Idx < NumIMaps; + ++Idx) { + if (GSI.Statuses[Idx] == SELECTED) { + SelectedIdx = Idx; + break; + } + } + assert(SelectedIdx >= 0 && "No instruction mapping selected!"); + const auto *SelectedMapping = GSI.Mappings[SelectedIdx]; + LLVM_DEBUG(dbgs() << " - Best mapping: "; SelectedMapping->print(dbgs()); + dbgs() << "\n"); + + // Apply the mapping. + assert(SelectedMapping->verify(MI) && "Invalid instruction mapping"); + SmallVector RepairPts; + if (!computeRepair(MI, *SelectedMapping, RepairPts)) { + return false; + } + if (!applyMapping(MI, *SelectedMapping, RepairPts)) { + return false; + } + + return true; +} + +void RegBankSelect::clearGlobalState() { + GSIMIMap.clear(); +} + +bool RegBankSelect::runOnMachineFunction(MachineFunction &MF) { + // If the ISel pipeline failed, do not bother running that pass. + if (MF.getProperties().hasProperty( + MachineFunctionProperties::Property::FailedISel)) + return false; + + LLVM_DEBUG(dbgs() << "Assign register banks for: " << MF.getName() << '\n'); + const Function &F = MF.getFunction(); + Mode SaveOptMode = OptMode; + if (F.hasOptNone()) + OptMode = Mode::Fast; + init(MF); + +#ifndef NDEBUG + // Check that our input is fully legal: we require the function to have the + // Legalized property, so it should be. + // FIXME: This should be in the MachineVerifier. + if (!DisableGISelLegalityCheck) + if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) { + reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect", + "instruction is not legal", *MI); + return false; + } +#endif + + if (OptMode == Mode::Global) { + selectRegBanksMultiPass(MF); + } else { + selectRegBanksSinglePass(MF); + } + OptMode = SaveOptMode; return false; } diff --git a/llvm/lib/CodeGen/GlobalISel/RegisterBankInfo.cpp b/llvm/lib/CodeGen/GlobalISel/RegisterBankInfo.cpp --- a/llvm/lib/CodeGen/GlobalISel/RegisterBankInfo.cpp +++ b/llvm/lib/CodeGen/GlobalISel/RegisterBankInfo.cpp @@ -804,3 +804,27 @@ OS << "])"; } } + +const RegisterBankInfo::InstructionMapping & +RegisterBankInfo::getInstructionMapping(unsigned ID, unsigned Cost, + const MachineInstr &MI, + const MachineRegisterInfo &MRI, + const TargetRegisterInfo &TRI) const { + SmallVector OMapVec; + for (auto MO : MI.operands()) { + const RegisterBank *RegBank; + if (MO.isReg()) { + RegBank = getRegBank(MO.getReg(), MRI, TRI); + } else { + // Since this operand is not a register but we still need to provide a + // ValueMapping, any register bank will do as this value will never be + // looked at. + RegBank = &getRegBank(0); + } + assert(RegBank && "Could not find register bank!"); + unsigned Len = RegBank->getSize(); + OMapVec.emplace_back(&getValueMapping(0, Len, *RegBank)); + } + return getInstructionMapping(ID, Cost, getOperandsMapping(OMapVec), + OMapVec.size()); +}