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,10 @@ /// Greedily minimize the cost of assigning register banks. /// This should produce code of greater quality, but will /// require more compile time. - Greedy + Greedy, + /// Find optimal solution. This should increase code quality, + /// but at the cost of longer compile time. + Optimal }; /// Abstract class used to represent an insertion point in a CFG. @@ -481,6 +485,52 @@ } }; + /// 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. + 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 register where the result of each InstructionMapping resides. + InstrMapDestRegisters Registers; + + /// The cost of each InstructionMapping. + InstrMapCosts Costs; + + /// The current status of each InstructionMapping. + InstrMapStatuses Statuses; + + GlobalStateOfInstr(MachineInstr &MI, + RegisterBankInfo::InstructionMappings Mappings, + InstrMapDestRegBanks DestRBs, + InstrMapDestRegisters Registers, InstrMapCosts Costs, + InstrMapStatuses Statuses) + : MI(MI), Mappings(Mappings), DestRBs(DestRBs), Registers(Registers), + Costs(Costs), Statuses(Statuses) {} + }; + /// Interface to the target lowering info related /// to register banks. const RegisterBankInfo *RBI = nullptr; @@ -503,6 +553,13 @@ /// Current optimization remark emitter. Used to report failures. std::unique_ptr MORE; + /// Global regbank-select state for a particular instruction. + DenseMap GSIMIMap; + + /// Map a virtual register, before instruction updates, to its corresponding + /// global regbank-select state. + DenseMap GSIRegMap; + /// Helper class used for every code morphing. MachineIRBuilder MIRBuilder; @@ -614,6 +671,60 @@ 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 optimal selection of register banks (bottom up). + /// 3. Assign register banks (top down). + /// This is run when in Optimal 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, + const RegisterBankInfo::InstructionMapping *IMap); + + /// Selects the \p InstructionMapping with lowest cost for the given \p MI. + void selectOptimalInstrMapping(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. Conversion instructions are inserted using \p MIB, and the number of + /// such instructions are returned through \p NumInserted. + void assignRegBank(MachineInstr &MI, MachineIRBuilder &MIB, + unsigned &NumInserted); + 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::Optimal, "regbankselect-optimal", + "Use the Optimal mode (best local mapping)"))); char RegBankSelect::ID = 0; @@ -674,53 +676,10 @@ } #endif - // 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); - for (MachineBasicBlock *MBB : RPOT) { - // Set a sensible insertion point so that 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. - MachineInstr &MI = *MII++; - - // Ignore target-specific post-isel instructions: they should use proper - // regclasses. - if (isTargetSpecificOpcode(MI.getOpcode()) && !MI.isPreISelOpcode()) - continue; - - // Ignore inline asm instructions: they should use physical - // registers/regclasses - if (MI.isInlineAsm()) - continue; - - // Ignore debug info. - if (MI.isDebugInstr()) - continue; - - if (!assignInstr(MI)) { - reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect", - "unable to map instruction", MI); - return false; - } - - // 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(); - } - } - } - } + if (OptMode == Mode::Optimal) + assignRegBanksMultiPass(MF); + else + assignRegBanksSinglePass(MF); OptMode = SaveOptMode; return false; @@ -1081,3 +1040,539 @@ } OS << LocalFreq << " * " << LocalCost << " + " << NonLocalCost; } + +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); + for (MachineBasicBlock *MBB : RPOT) { + // Set a sensible insertion point so that 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. + MachineInstr &MI = *MII++; + + // Ignore target-specific post-isel instructions: they should use proper + // regclasses. + if (isTargetSpecificOpcode(MI.getOpcode()) && !MI.isPreISelOpcode()) + continue; + + // Ignore inline asm instructions: they should use physical + // registers/regclasses + if (MI.isInlineAsm()) + continue; + + // Ignore debug info. + if (MI.isDebugInstr()) + continue; + + if (!assignInstr(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::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 the optimal 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 optimal 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; + } + + selectOptimalInstrMapping(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; ++MII) { + MachineInstr &MI = *MII; + + if (MI.isDebugInstr()) { + continue; + } + + MIB.setInsertPt(*MBB, std::next(MII)); // Insert new instructions after + // the current MI. + unsigned NumInserted = 0; + assignRegBank(MI, MIB, NumInserted); + MII = std::next(MII, NumInserted); + } + } + + 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); + GSI.Registers.emplace_back(DestReg); + + return BestCost; +} + +bool RegBankSelect::computeGlobalCost( + MachineInstr &MI, RegisterBankInfo::InstructionMappings &Mappings) { + LLVM_DEBUG(dbgs() << "- Processing " << MI); + + // Compute costs for each InstructionMapping + InstrMapCosts IMCosts; + InstrMapDestRegBanks DestRBs; + InstrMapDestRegisters Registers; + InstrMapStatuses Statuses; + Register DestReg = + MI.getNumExplicitDefs() ? MI.getOperand(0).getReg() : Register(0); + for (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"); + + const RegisterBank *DestRB = + DestReg ? getRegBankOfOpInInstrMap(IMap, 0) : nullptr; + IMCosts.emplace_back(Cost); + DestRBs.emplace_back(DestRB); + Statuses.emplace_back(NOTHING); + Registers.emplace_back(DestReg); + } + auto Res = GSIMIMap.try_emplace(&MI, MI, Mappings, DestRBs, Registers, + IMCosts, Statuses); + auto &GSI = (*Res.first).second; + if (DestReg) { + GSIRegMap.try_emplace(DestReg, &GSI); + } + + // If destination register is already pre-assigned a register bank, ensure + // that the register ends up in the correct place. + if (DestReg) { + const RegisterBank *RB = MRI->getRegBankOrNull(DestReg); + if (RB) { + computeLowestCostOfDstInRegBank(GSI, RB); + unsigned RBIdx = getIdxOfMatchingDestRegBank(GSI, RB); + GSI.Statuses[RBIdx] = SELECTED; + + // If this needs a copy, rename the destination register of the + // instruction such that the result of the copy ends up in the original + // register. + if (getRegBankOfOpInInstrMap(GSI.Mappings[RBIdx], 0) != RB) { + Register NewReg = MRI->cloneVirtualRegister(DestReg); + for (unsigned Idx = 0, NumMaps = GSI.Mappings.size(); Idx < NumMaps; + ++Idx) { + GSI.Registers[Idx] = NewReg; + } + GSI.Registers[RBIdx] = DestReg; + MI.getOperand(0).setReg(NewReg); + } + } + } + + return true; +} + +void RegBankSelect::markOperandsAsUsed( + MachineInstr &MI, 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); + 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) { + auto DI = GSIRegMap.find(Reg); + assert(DI != GSIRegMap.end() && "No such instruction in GSIRegMap!"); + return *DI->second; +} + +void RegBankSelect::selectOptimalInstrMapping(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 mapping with lowest cost, mark all its uses as used, and then + // mark it as selected. + const unsigned ImpossibleCost = std::numeric_limits::max(); + unsigned BestCost = ImpossibleCost; + int BestIdx = -1; + for (unsigned Idx = 0; Idx < NumIMaps; ++Idx) { + unsigned Cost = GSI.Costs[Idx]; + if (Cost < BestCost) { + BestCost = Cost; + BestIdx = Idx; + } + } + assert(BestIdx >= 0 && "No InstructionMapping found!"); + const auto *IMap = GSI.Mappings[BestIdx]; + LLVM_DEBUG(dbgs() << " * Selecting "; IMap->print(dbgs()); + dbgs() << ", cost: " << GSI.Costs[BestIdx] << "\n"); + markOperandsAsUsed(MI, IMap); + GSI.Statuses[BestIdx] = SELECTED; + } else { + // For each mapping marked as used, mark all its uses as used and then + // mark the mapping as selected. + for (unsigned Idx = 0; Idx < NumIMaps; ++Idx) { + if (GSI.Statuses[Idx] == USED) { + const auto *IMap = GSI.Mappings[Idx]; + markOperandsAsUsed(MI, IMap); + GSI.Statuses[Idx] = SELECTED; + } + } + } +} + +void RegBankSelect::assignRegBank(MachineInstr &MI, MachineIRBuilder &MIB, + unsigned &NumInserted) { + LLVM_DEBUG(dbgs() << "- Processing " << MI); + + auto &GSI = getGSIOfMI(MI); + SmallVector, 4> MIsToUpdate; + + // If there are multiple InstructionMappings selected, pick the cheapest and + // try to copy the other mappings from that one. If the latter fails, + // rematerialize the instruction. Note that the costs will no longer be + // accurate, but that doesn't matter as we won't make any further decisions + // based on them. + // FIXME: This might break optimality, but I don't have a better fix at the + // moment. + signed BestIdx = -1; + const unsigned ImpossibleCost = std::numeric_limits::max(); + unsigned BestCost = ImpossibleCost; + const unsigned NumIMaps = GSI.Mappings.size(); + for (unsigned Idx = 0; Idx < NumIMaps; ++Idx) { + if (GSI.Statuses[Idx] == SELECTED) { + if (GSI.Costs[Idx] < BestCost) { + BestIdx = Idx; + BestCost = GSI.Costs[Idx]; + } + } + } + assert(BestIdx >= 0 && "No InstructionMapping selected!"); + MIsToUpdate.emplace_back(&MI, BestIdx); + const auto *BestIMap = GSI.Mappings[BestIdx]; + LLVM_DEBUG(dbgs() << " - Best mapping: "; BestIMap->print(dbgs()); + dbgs() << "\n"); + if (MI.getNumExplicitDefs() > 0) { + const RegisterBank *BestRB = getRegBankOfOpInInstrMap(BestIMap, 0); + Register DestReg = MI.getOperand(0).getReg(); + for (unsigned Idx = 0; Idx < NumIMaps; ++Idx) { + if (Idx == (unsigned)BestIdx || GSI.Statuses[Idx] != SELECTED) { + continue; + } + + const auto *IMap = GSI.Mappings[Idx]; + LLVM_DEBUG(dbgs() << " - Checking "; IMap->print(dbgs()); + dbgs() << "\n"); + + // If the InstructionMappings are the same, then we know for sure that it + // is possible to copy between the register banks as we have already + // checked this when computing the costs. + if (IMap == GSI.Mappings[BestIdx]) { + continue; + } + + const RegisterBank *DestRB = GSI.DestRBs[Idx]; + unsigned CopyCost = RBI->copyCost( + *DestRB, *BestRB, RBI->getSizeInBits(DestReg, *MRI, *TRI)); + if (CopyCost == ImpossibleCost) { + LLVM_DEBUG(dbgs() << " Cannot copy between register banks\n" + << " Rematerializing instruction"); + MachineInstrBuilder MInstrB(MIB.getMF(), MI); + MachineInstr *NewMI = MIB.insertInstr(MInstrB).getInstr(); + ++NumInserted; + Register NewReg = MRI->cloneVirtualRegister(DestReg); + NewMI->getOperand(0).setReg(NewReg); + GSI.Registers[Idx] = NewReg; + MIsToUpdate.emplace_back(NewMI, Idx); + } + } + } + + // Update the use operands and destination register of the original and + // rematerialized machine instructions to fit the selected + // InstructionMappings. + for (auto T : MIsToUpdate) { + MachineInstr *CurMI = std::get<0>(T); + auto IMap = GSI.Mappings[std::get<1>(T)]; + LLVM_DEBUG(dbgs() << " - Updating " << *CurMI // Implicit \n. + << " to fit "; IMap->print(dbgs()); dbgs() << "\n"); + + // Update registers of the use operands + for (unsigned Opx = 1, NumOps = IMap->getNumOperands(); Opx < NumOps; + ++Opx) { + MachineOperand &MO = CurMI->getOperand(Opx); + if (!MO.isVirtualReg() || + MRI->getRegClassOrNull(MO.getReg())) { + continue; + } + + const RegisterBank *RBOfOp = getRegBankOfOpInInstrMap(IMap, Opx); + auto GSIOfOp = getGSIOfDefOfReg(MO.getReg()); + unsigned MapIdx = getIdxOfMatchingDestRegBank(GSIOfOp, RBOfOp); + Register Reg = GSIOfOp.Registers[MapIdx]; + if (MO.getReg() != Reg) { + MO.setReg(Reg); + LLVM_DEBUG(dbgs() << " Updated operand " << Opx << " to " << MO + << "\n"); + } + } + + // Assign register bank to result of instruction + if (CurMI->getNumExplicitDefs() > 0) { + MachineOperand &DestMO = CurMI->getOperand(0); + if (DestMO.isVirtualReg() && !MRI->getRegClassOrNull(DestMO.getReg())) { + Register DestReg = DestMO.getReg(); + assert(DestReg && "Instruction has no destination register!"); + const RegisterBank *RBOfIMap = getRegBankOfOpInInstrMap(IMap, 0); + LLVM_DEBUG(dbgs() << " Constrained " << DestMO << " to " + << *RBOfIMap << "\n"); + MRI->setRegBank(DestReg, *RBOfIMap); + } + } + } + + // Emit necessary copies + if (MI.getNumExplicitDefs() > 0) { + assert(MI.getNumExplicitDefs() == 1 && + "Cannot handle instructions with multiple explicit defs!"); + MachineOperand &DestMO = MI.getOperand(0); + Register DestReg = DestMO.getReg(); + for (unsigned Idx = 0; Idx < NumIMaps; ++Idx) { + if (GSI.Statuses[Idx] != SELECTED) { + continue; + } + + const RegisterBank *RBOfIMap = + getRegBankOfOpInInstrMap(GSI.Mappings[Idx], 0); + const RegisterBank *DestRB = GSI.DestRBs[Idx]; + if (RBOfIMap != DestRB) { + Register DestReg2 = DestReg == GSI.Registers[Idx] + ? MRI->cloneVirtualRegister(DestReg) + : GSI.Registers[Idx]; + MRI->setRegBank(DestReg2, *DestRB); + auto MIR = MIB.buildCopy(DestReg2, DestReg); + ++NumInserted; + LLVM_DEBUG(dbgs() << " Emitted: " << *MIR.getInstr()); + GSI.Registers[Idx] = DestReg2; + } + } + } +} + +void RegBankSelect::clearGlobalState() { + GSIMIMap.clear(); + GSIRegMap.clear(); +} 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()); +}