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. @@ -481,6 +486,49 @@ } }; + /// 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 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. + InstrMapCosts 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 +551,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; @@ -594,6 +645,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 +680,58 @@ const RegisterBankInfo::InstructionMapping &InstrMapping, SmallVectorImpl &RepairPts); + /// Make a single pass over the instructions and assigns register banks. This + /// is run when in Fast or Greedy mode. + void assignRegBanksSinglePass(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 assignRegBanksMultiPass(MachineFunction &MF); + + /// Clears all variables used for containing the global regbank-select state. + void clearGlobalState(); + + /// 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. + unsigned computeLowestCostOfDstInRegBank(GlobalStateOfInstr &GSI, + const RegisterBank *DesiredRegBank); + + /// Assign register bank to the destination register of the given \p MI. This + /// also updates the use operands in cases where conversions need to be + /// made. + bool assignRegBank(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) { @@ -649,35 +707,16 @@ 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 isMachineInstrWithRegClasses(const MachineInstr &MI) { + return (isTargetSpecificOpcode(MI.getOpcode()) && !MI.isPreISelOpcode()) || + MI.isInlineAsm(); +} +void RegBankSelect::assignRegBanksSinglePass(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. @@ -705,7 +744,101 @@ if (!assignInstr(MI)) { reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect", "unable to map instruction", MI); - return false; + 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::assignRegBanksMultiPass(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) { + for (MachineBasicBlock::iterator MII = MBB->begin(), End = MBB->end(); + MII != End; MII++) { + MachineInstr &MI = *MII; + + if (MI.isDebugInstr()) { + continue; + } + + RegisterBankInfo::InstructionMappings PossibleMappings; + if (!isMachineInstrWithRegClasses(MI)) { + PossibleMappings = RBI->getInstrPossibleMappings(MI); + if (PossibleMappings.empty()) { + reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect", + "unable to find mappings for instruction", MI); + return; + } + } else { + PossibleMappings.emplace_back( + &RBI->getInstructionMapping(0, 0, MI, *MRI, *TRI)); + } + + if (!computeGlobalCost(MI, PossibleMappings)) { + reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect", + "unable to compute cost for instruction", MI); + return; + } + } + } + + // 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() << "Finding register bank selection...\n"); + for (MachineBasicBlock *MBB : post_order(&MF)) { + bool ReachedBegin = false; + for (auto MII = std::prev(MBB->end()), Begin = MBB->begin(); !ReachedBegin; + MII--) { + if (MII == Begin) { + ReachedBegin = true; + } + + auto &MI = *MII; + if (MI.isDebugInstr()) { + continue; + } + + if (!selectGlobalInstrMapping(MI)) { + reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect", + "unable to select register banks", MI); + } + } + } + + // Assign register banks. Walk the instructions top down. + LLVM_DEBUG(dbgs() << "Assigning register banks...\n"); + MachineIRBuilder MIB(MF); + for (MachineBasicBlock *MBB : RPOT) { + for (MachineBasicBlock::iterator MII = MBB->begin(), End = MBB->end(); + MII != End; ) { + // MI might be invalidated by the assignment, so move the iterator before + // hand. + MachineInstr &MI = *MII++; + + if (MI.isDebugInstr()) { + continue; + } + + if (!assignRegBank(MI)) { + reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect", + "unable to assign register banks", MI); } // It's possible the mapping changed control flow, and moved the following @@ -722,6 +855,322 @@ } } + 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; +} + +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!"); +} + +unsigned RegBankSelect::computeLowestCostOfDstInRegBank( + GlobalStateOfInstr &GSI, const RegisterBank *DesiredRegBank) { + auto &MI = GSI.MI; + LLVM_DEBUG(dbgs() << " DefMI: " << MI); + + auto &IM = GSI.Mappings; + assert(IM.size() > 0 && "No InstructionMappings found!"); + assert(IM.size() == GSI.DestRBs.size() && "Mismatching sizes!"); + assert(IM.size() == GSI.Costs.size() && "Mismatching sizes!"); + + // Find dst with matching register bank + for (unsigned Idx = 0; Idx < IM.size(); ++Idx) { + if (GSI.DestRBs[Idx] == DesiredRegBank) { + unsigned 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 unsigned ImpossibleCost = std::numeric_limits::max(); + unsigned BestCost = ImpossibleCost; + for (unsigned Idx = 0; Idx < IM.size(); ++Idx) { + unsigned Cost = GSI.Costs[Idx]; + + LLVM_DEBUG(dbgs() << " - InstructionMapping: " << *IM[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)); + if (CopyCost == ImpossibleCost) { + LLVM_DEBUG(dbgs() << " No such copy\n"); + continue; + } + LLVM_DEBUG(dbgs() << " Cost of copying: " << CopyCost << "\n"); + Cost += 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: " << *IM[BestIdx] + << "\n"); + + // Make new entry for converting register bank for dest. + IM.emplace_back(IM[BestIdx]); + GSI.DestRBs.emplace_back(DesiredRegBank); + GSI.Costs.emplace_back(BestCost); + GSI.Statuses.emplace_back(NOTHING); + + return BestCost; +} + +bool RegBankSelect::computeGlobalCost( + MachineInstr &MI, RegisterBankInfo::InstructionMappings &Mappings) { + LLVM_DEBUG(dbgs() << "- Processing " << MI); + + 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. + unsigned Cost = 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. + for (unsigned Opx = 1, NumOps = IMap->getNumOperands(); Opx < NumOps; + ++Opx) { + LLVM_DEBUG(dbgs() << " - Operand: " << Opx << "\n"); + + auto MO = MI.getOperand(Opx); + if (!MO.isVirtualReg()) { + continue; + } + + const RegisterBank *RB = getRegBankOfOpInInstrMap(IMap, Opx); + auto &GSI = getGSIOfDefOfReg(MO.getReg()); + unsigned DefMICost = computeLowestCostOfDstInRegBank(GSI, RB); + LLVM_DEBUG(dbgs() << " Cost of operand: " << DefMICost << "\n"); + Cost += DefMICost; + } + 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) { + LLVM_DEBUG(dbgs() << " - Processing mapping "; IMap->print(dbgs()); + dbgs() << "\n"); + + for (unsigned Idx = 1, NumOps = IMap->getNumOperands(); Idx < NumOps; ++Idx) { + MachineOperand &MO = MI.getOperand(Idx); + if (!MO.isVirtualReg()) { + continue; + } + const RegisterBank *RB = getRegBankOfOpInInstrMap(IMap, Idx); + LLVM_DEBUG(dbgs() << " - Operand: " << Idx << ", reg bank: " << *RB + << "\n"); + + auto &GSI = getGSIOfDefOfReg(MO.getReg()); + unsigned MapIdx = getIdxOfMatchingDestRegBank(GSI, RB); + GSI.UtilScores[MapIdx] += Score; + if (GSI.Statuses[MapIdx] == NOTHING) { + GSI.Statuses[MapIdx] = USED; + } + } +} + +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) { + LLVM_DEBUG(dbgs() << "- Processing " << 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 IsLeaf = true; + for (unsigned Idx = 0; Idx < NumIMaps; ++Idx) { + if (GSI.Statuses[Idx] != NOTHING) { + IsLeaf = false; + break; + } + } + + if (IsLeaf) { + LLVM_DEBUG(dbgs() << " Is leaf\n"); + + // Find and select mapping with lowest cost. + const unsigned ImpossibleCost = std::numeric_limits::max(); + unsigned BestCost = ImpossibleCost; + int BestIdx = -1; + for (unsigned Idx = 0; Idx < NumIMaps; ++Idx) { + const unsigned Cost = GSI.Costs[Idx]; + if (Cost < BestCost) { + BestCost = Cost; + BestIdx = Idx; + } + } + if (BestIdx < 0) { + LLVM_DEBUG(dbgs() << " No mapping found for " << MI); + return false; + } + const auto *IMap = GSI.Mappings[BestIdx]; + const unsigned Cost = GSI.Costs[BestIdx]; + LLVM_DEBUG(dbgs() << " * Selecting "; IMap->print(dbgs()); + dbgs() << ", cost: " << Cost << "\n"); + GSI.Statuses[BestIdx] = SELECTED; + + LLVM_DEBUG(dbgs() << " - Marking uses"); + markOperandsAsUsed(MI, Cost, IMap); + } else { + // Find and select mapping with highest utility score. + unsigned BestScore = 0; + int BestIdx = -1; + for (unsigned Idx = 0; Idx < NumIMaps; ++Idx) { + if (GSI.Statuses[Idx] != USED) { + continue; + } + const unsigned Score = GSI.UtilScores[Idx]; + if (Score > BestScore) { + BestScore = Score; + BestIdx = Idx; + } + } + assert(BestIdx >= 0 && "Instruction mapping without use!"); + const auto *IMap = GSI.Mappings[BestIdx]; + LLVM_DEBUG(dbgs() << " * Selecting "; IMap->print(dbgs()); + dbgs() << ", score: " << BestScore << "\n"); + GSI.Statuses[BestIdx] = SELECTED; + + LLVM_DEBUG(dbgs() << " - Marking uses"); + markOperandsAsUsed(MI, GSI.Costs[BestIdx], GSI.Mappings[BestIdx]); + } + + return true; +} + +bool RegBankSelect::assignRegBank(MachineInstr &MI) { + LLVM_DEBUG(dbgs() << "- Processing " << 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) + assignRegBanksMultiPass(MF); + else + assignRegBanksSinglePass(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()); +}