260 lines · cpp
1//===-- RegAllocBasic.cpp - Basic Register Allocator ----------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8///9/// \file10/// This file defines the RABasic function pass, which provides a minimal11/// implementation of the basic register allocator.12///13//===----------------------------------------------------------------------===//14 15#include "RegAllocBasic.h"16#include "AllocationOrder.h"17#include "llvm/Analysis/AliasAnalysis.h"18#include "llvm/Analysis/ProfileSummaryInfo.h"19#include "llvm/CodeGen/CalcSpillWeights.h"20#include "llvm/CodeGen/LiveDebugVariables.h"21#include "llvm/CodeGen/LiveIntervals.h"22#include "llvm/CodeGen/LiveRegMatrix.h"23#include "llvm/CodeGen/LiveStacks.h"24#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"25#include "llvm/CodeGen/MachineDominators.h"26#include "llvm/CodeGen/MachineLoopInfo.h"27#include "llvm/CodeGen/Passes.h"28#include "llvm/CodeGen/RegAllocRegistry.h"29#include "llvm/CodeGen/VirtRegMap.h"30#include "llvm/Pass.h"31#include "llvm/Support/Debug.h"32#include "llvm/Support/raw_ostream.h"33 34using namespace llvm;35 36#define DEBUG_TYPE "regalloc"37 38static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator",39 createBasicRegisterAllocator);40 41char RABasic::ID = 0;42 43char &llvm::RABasicID = RABasic::ID;44 45INITIALIZE_PASS_BEGIN(RABasic, "regallocbasic", "Basic Register Allocator",46 false, false)47INITIALIZE_PASS_DEPENDENCY(LiveDebugVariablesWrapperLegacy)48INITIALIZE_PASS_DEPENDENCY(SlotIndexesWrapperPass)49INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)50INITIALIZE_PASS_DEPENDENCY(RegisterCoalescerLegacy)51INITIALIZE_PASS_DEPENDENCY(MachineSchedulerLegacy)52INITIALIZE_PASS_DEPENDENCY(LiveStacksWrapperLegacy)53INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)54INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)55INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)56INITIALIZE_PASS_DEPENDENCY(VirtRegMapWrapperLegacy)57INITIALIZE_PASS_DEPENDENCY(LiveRegMatrixWrapperLegacy)58INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)59INITIALIZE_PASS_END(RABasic, "regallocbasic", "Basic Register Allocator", false,60 false)61 62bool RABasic::LRE_CanEraseVirtReg(Register VirtReg) {63 LiveInterval &LI = LIS->getInterval(VirtReg);64 if (VRM->hasPhys(VirtReg)) {65 Matrix->unassign(LI);66 aboutToRemoveInterval(LI);67 return true;68 }69 // Unassigned virtreg is probably in the priority queue.70 // RegAllocBase will erase it after dequeueing.71 // Nonetheless, clear the live-range so that the debug72 // dump will show the right state for that VirtReg.73 LI.clear();74 return false;75}76 77void RABasic::LRE_WillShrinkVirtReg(Register VirtReg) {78 if (!VRM->hasPhys(VirtReg))79 return;80 81 // Register is assigned, put it back on the queue for reassignment.82 LiveInterval &LI = LIS->getInterval(VirtReg);83 Matrix->unassign(LI);84 enqueue(&LI);85}86 87RABasic::RABasic(RegAllocFilterFunc F)88 : MachineFunctionPass(ID), RegAllocBase(F) {}89 90void RABasic::getAnalysisUsage(AnalysisUsage &AU) const {91 AU.setPreservesCFG();92 AU.addRequired<AAResultsWrapperPass>();93 AU.addPreserved<AAResultsWrapperPass>();94 AU.addRequired<LiveIntervalsWrapperPass>();95 AU.addPreserved<LiveIntervalsWrapperPass>();96 AU.addPreserved<SlotIndexesWrapperPass>();97 AU.addRequired<LiveDebugVariablesWrapperLegacy>();98 AU.addPreserved<LiveDebugVariablesWrapperLegacy>();99 AU.addRequired<LiveStacksWrapperLegacy>();100 AU.addPreserved<LiveStacksWrapperLegacy>();101 AU.addRequired<ProfileSummaryInfoWrapperPass>();102 AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();103 AU.addPreserved<MachineBlockFrequencyInfoWrapperPass>();104 AU.addRequired<MachineDominatorTreeWrapperPass>();105 AU.addRequiredID(MachineDominatorsID);106 AU.addPreservedID(MachineDominatorsID);107 AU.addRequired<MachineLoopInfoWrapperPass>();108 AU.addPreserved<MachineLoopInfoWrapperPass>();109 AU.addRequired<VirtRegMapWrapperLegacy>();110 AU.addPreserved<VirtRegMapWrapperLegacy>();111 AU.addRequired<LiveRegMatrixWrapperLegacy>();112 AU.addPreserved<LiveRegMatrixWrapperLegacy>();113 MachineFunctionPass::getAnalysisUsage(AU);114}115 116void RABasic::releaseMemory() {117 SpillerInstance.reset();118}119 120 121// Spill or split all live virtual registers currently unified under PhysReg122// that interfere with VirtReg. The newly spilled or split live intervals are123// returned by appending them to SplitVRegs.124bool RABasic::spillInterferences(const LiveInterval &VirtReg,125 MCRegister PhysReg,126 SmallVectorImpl<Register> &SplitVRegs) {127 // Record each interference and determine if all are spillable before mutating128 // either the union or live intervals.129 SmallVector<const LiveInterval *, 8> Intfs;130 131 // Collect interferences assigned to any alias of the physical register.132 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {133 LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, Unit);134 for (const auto *Intf : reverse(Q.interferingVRegs())) {135 if (!Intf->isSpillable() || Intf->weight() > VirtReg.weight())136 return false;137 Intfs.push_back(Intf);138 }139 }140 LLVM_DEBUG(dbgs() << "spilling " << printReg(PhysReg, TRI)141 << " interferences with " << VirtReg << "\n");142 assert(!Intfs.empty() && "expected interference");143 144 // Spill each interfering vreg allocated to PhysReg or an alias.145 for (const LiveInterval *Spill : Intfs) {146 // Skip duplicates.147 if (!VRM->hasPhys(Spill->reg()))148 continue;149 150 // Deallocate the interfering vreg by removing it from the union.151 // A LiveInterval instance may not be in a union during modification!152 Matrix->unassign(*Spill);153 154 // Spill the extracted interval.155 LiveRangeEdit LRE(Spill, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats);156 spiller().spill(LRE);157 }158 return true;159}160 161// Driver for the register assignment and splitting heuristics.162// Manages iteration over the LiveIntervalUnions.163//164// This is a minimal implementation of register assignment and splitting that165// spills whenever we run out of registers.166//167// selectOrSplit can only be called once per live virtual register. We then do a168// single interference test for each register the correct class until we find an169// available register. So, the number of interference tests in the worst case is170// |vregs| * |machineregs|. And since the number of interference tests is171// minimal, there is no value in caching them outside the scope of172// selectOrSplit().173MCRegister RABasic::selectOrSplit(const LiveInterval &VirtReg,174 SmallVectorImpl<Register> &SplitVRegs) {175 // Populate a list of physical register spill candidates.176 SmallVector<MCRegister, 8> PhysRegSpillCands;177 178 // Check for an available register in this class.179 auto Order =180 AllocationOrder::create(VirtReg.reg(), *VRM, RegClassInfo, Matrix);181 for (MCRegister PhysReg : Order) {182 assert(PhysReg.isValid());183 // Check for interference in PhysReg184 switch (Matrix->checkInterference(VirtReg, PhysReg)) {185 case LiveRegMatrix::IK_Free:186 // PhysReg is available, allocate it.187 return PhysReg;188 189 case LiveRegMatrix::IK_VirtReg:190 // Only virtual registers in the way, we may be able to spill them.191 PhysRegSpillCands.push_back(PhysReg);192 continue;193 194 default:195 // RegMask or RegUnit interference.196 continue;197 }198 }199 200 // Try to spill another interfering reg with less spill weight.201 for (MCRegister &PhysReg : PhysRegSpillCands) {202 if (!spillInterferences(VirtReg, PhysReg, SplitVRegs))203 continue;204 205 assert(!Matrix->checkInterference(VirtReg, PhysReg) &&206 "Interference after spill.");207 // Tell the caller to allocate to this newly freed physical register.208 return PhysReg;209 }210 211 // No other spill candidates were found, so spill the current VirtReg.212 LLVM_DEBUG(dbgs() << "spilling: " << VirtReg << '\n');213 if (!VirtReg.isSpillable())214 return ~0u;215 LiveRangeEdit LRE(&VirtReg, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats);216 spiller().spill(LRE);217 218 // The live virtual register requesting allocation was spilled, so tell219 // the caller not to allocate anything during this round.220 return 0;221}222 223bool RABasic::runOnMachineFunction(MachineFunction &mf) {224 LLVM_DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n"225 << "********** Function: " << mf.getName() << '\n');226 227 MF = &mf;228 auto &MBFI = getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();229 auto &LiveStks = getAnalysis<LiveStacksWrapperLegacy>().getLS();230 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();231 232 RegAllocBase::init(getAnalysis<VirtRegMapWrapperLegacy>().getVRM(),233 getAnalysis<LiveIntervalsWrapperPass>().getLIS(),234 getAnalysis<LiveRegMatrixWrapperLegacy>().getLRM());235 VirtRegAuxInfo VRAI(*MF, *LIS, *VRM,236 getAnalysis<MachineLoopInfoWrapperPass>().getLI(), MBFI,237 &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI());238 VRAI.calculateSpillWeightsAndHints();239 240 SpillerInstance.reset(241 createInlineSpiller({*LIS, LiveStks, MDT, MBFI}, *MF, *VRM, VRAI));242 243 allocatePhysRegs();244 postOptimization();245 246 // Diagnostic output before rewriting247 LLVM_DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n");248 249 releaseMemory();250 return true;251}252 253FunctionPass* llvm::createBasicRegisterAllocator() {254 return new RABasic();255}256 257FunctionPass *llvm::createBasicRegisterAllocator(RegAllocFilterFunc F) {258 return new RABasic(F);259}260