1234353Sdim//===-- RegAllocBasic.cpp - Basic Register Allocator ----------------------===// 2218885Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6218885Sdim// 7218885Sdim//===----------------------------------------------------------------------===// 8218885Sdim// 9218885Sdim// This file defines the RABasic function pass, which provides a minimal 10218885Sdim// implementation of the basic register allocator. 11218885Sdim// 12218885Sdim//===----------------------------------------------------------------------===// 13218885Sdim 14239462Sdim#include "AllocationOrder.h" 15249423Sdim#include "LiveDebugVariables.h" 16223017Sdim#include "RegAllocBase.h" 17218885Sdim#include "Spiller.h" 18218885Sdim#include "llvm/Analysis/AliasAnalysis.h" 19218885Sdim#include "llvm/CodeGen/CalcSpillWeights.h" 20327952Sdim#include "llvm/CodeGen/LiveIntervals.h" 21234353Sdim#include "llvm/CodeGen/LiveRangeEdit.h" 22249423Sdim#include "llvm/CodeGen/LiveRegMatrix.h" 23327952Sdim#include "llvm/CodeGen/LiveStacks.h" 24261991Sdim#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 25218885Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 26218885Sdim#include "llvm/CodeGen/MachineInstr.h" 27218885Sdim#include "llvm/CodeGen/MachineLoopInfo.h" 28218885Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 29321369Sdim#include "llvm/CodeGen/Passes.h" 30218885Sdim#include "llvm/CodeGen/RegAllocRegistry.h" 31327952Sdim#include "llvm/CodeGen/TargetRegisterInfo.h" 32249423Sdim#include "llvm/CodeGen/VirtRegMap.h" 33249423Sdim#include "llvm/PassAnalysisSupport.h" 34249423Sdim#include "llvm/Support/Debug.h" 35249423Sdim#include "llvm/Support/raw_ostream.h" 36218885Sdim#include <cstdlib> 37219077Sdim#include <queue> 38218885Sdim 39218885Sdimusing namespace llvm; 40218885Sdim 41276479Sdim#define DEBUG_TYPE "regalloc" 42276479Sdim 43218885Sdimstatic RegisterRegAlloc basicRegAlloc("basic", "basic register allocator", 44218885Sdim createBasicRegisterAllocator); 45218885Sdim 46218885Sdimnamespace { 47219077Sdim struct CompSpillWeight { 48219077Sdim bool operator()(LiveInterval *A, LiveInterval *B) const { 49219077Sdim return A->weight < B->weight; 50219077Sdim } 51219077Sdim }; 52219077Sdim} 53219077Sdim 54219077Sdimnamespace { 55218885Sdim/// RABasic provides a minimal implementation of the basic register allocation 56218885Sdim/// algorithm. It prioritizes live virtual registers by spill weight and spills 57218885Sdim/// whenever a register is unavailable. This is not practical in production but 58218885Sdim/// provides a useful baseline both for measuring other allocators and comparing 59218885Sdim/// the speed of the basic algorithm against other styles of allocators. 60321369Sdimclass RABasic : public MachineFunctionPass, 61321369Sdim public RegAllocBase, 62321369Sdim private LiveRangeEdit::Delegate { 63218885Sdim // context 64218885Sdim MachineFunction *MF; 65218885Sdim 66218885Sdim // state 67276479Sdim std::unique_ptr<Spiller> SpillerInstance; 68219077Sdim std::priority_queue<LiveInterval*, std::vector<LiveInterval*>, 69219077Sdim CompSpillWeight> Queue; 70234353Sdim 71234353Sdim // Scratch space. Allocated here to avoid repeated malloc calls in 72234353Sdim // selectOrSplit(). 73234353Sdim BitVector UsableRegs; 74234353Sdim 75321369Sdim bool LRE_CanEraseVirtReg(unsigned) override; 76321369Sdim void LRE_WillShrinkVirtReg(unsigned) override; 77321369Sdim 78218885Sdimpublic: 79218885Sdim RABasic(); 80218885Sdim 81218885Sdim /// Return the pass name. 82314564Sdim StringRef getPassName() const override { return "Basic Register Allocator"; } 83218885Sdim 84218885Sdim /// RABasic analysis usage. 85276479Sdim void getAnalysisUsage(AnalysisUsage &AU) const override; 86218885Sdim 87276479Sdim void releaseMemory() override; 88218885Sdim 89276479Sdim Spiller &spiller() override { return *SpillerInstance; } 90218885Sdim 91276479Sdim void enqueue(LiveInterval *LI) override { 92219077Sdim Queue.push(LI); 93219077Sdim } 94219077Sdim 95276479Sdim LiveInterval *dequeue() override { 96219077Sdim if (Queue.empty()) 97276479Sdim return nullptr; 98219077Sdim LiveInterval *LI = Queue.top(); 99219077Sdim Queue.pop(); 100219077Sdim return LI; 101219077Sdim } 102219077Sdim 103276479Sdim unsigned selectOrSplit(LiveInterval &VirtReg, 104276479Sdim SmallVectorImpl<unsigned> &SplitVRegs) override; 105218885Sdim 106218885Sdim /// Perform register allocation. 107276479Sdim bool runOnMachineFunction(MachineFunction &mf) override; 108218885Sdim 109314564Sdim MachineFunctionProperties getRequiredProperties() const override { 110314564Sdim return MachineFunctionProperties().set( 111314564Sdim MachineFunctionProperties::Property::NoPHIs); 112314564Sdim } 113314564Sdim 114234353Sdim // Helper for spilling all live virtual registers currently unified under preg 115234353Sdim // that interfere with the most recently queried lvr. Return true if spilling 116234353Sdim // was successful, and append any new spilled/split intervals to splitLVRs. 117234353Sdim bool spillInterferences(LiveInterval &VirtReg, unsigned PhysReg, 118261991Sdim SmallVectorImpl<unsigned> &SplitVRegs); 119234353Sdim 120218885Sdim static char ID; 121218885Sdim}; 122218885Sdim 123218885Sdimchar RABasic::ID = 0; 124218885Sdim 125218885Sdim} // end anonymous namespace 126218885Sdim 127321369Sdimchar &llvm::RABasicID = RABasic::ID; 128321369Sdim 129321369SdimINITIALIZE_PASS_BEGIN(RABasic, "regallocbasic", "Basic Register Allocator", 130321369Sdim false, false) 131321369SdimINITIALIZE_PASS_DEPENDENCY(LiveDebugVariables) 132321369SdimINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 133321369SdimINITIALIZE_PASS_DEPENDENCY(LiveIntervals) 134321369SdimINITIALIZE_PASS_DEPENDENCY(RegisterCoalescer) 135321369SdimINITIALIZE_PASS_DEPENDENCY(MachineScheduler) 136321369SdimINITIALIZE_PASS_DEPENDENCY(LiveStacks) 137321369SdimINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 138321369SdimINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 139321369SdimINITIALIZE_PASS_DEPENDENCY(VirtRegMap) 140321369SdimINITIALIZE_PASS_DEPENDENCY(LiveRegMatrix) 141321369SdimINITIALIZE_PASS_END(RABasic, "regallocbasic", "Basic Register Allocator", false, 142321369Sdim false) 143321369Sdim 144321369Sdimbool RABasic::LRE_CanEraseVirtReg(unsigned VirtReg) { 145327952Sdim LiveInterval &LI = LIS->getInterval(VirtReg); 146321369Sdim if (VRM->hasPhys(VirtReg)) { 147321369Sdim Matrix->unassign(LI); 148321369Sdim aboutToRemoveInterval(LI); 149321369Sdim return true; 150321369Sdim } 151321369Sdim // Unassigned virtreg is probably in the priority queue. 152321369Sdim // RegAllocBase will erase it after dequeueing. 153327952Sdim // Nonetheless, clear the live-range so that the debug 154327952Sdim // dump will show the right state for that VirtReg. 155327952Sdim LI.clear(); 156321369Sdim return false; 157321369Sdim} 158321369Sdim 159321369Sdimvoid RABasic::LRE_WillShrinkVirtReg(unsigned VirtReg) { 160321369Sdim if (!VRM->hasPhys(VirtReg)) 161321369Sdim return; 162321369Sdim 163321369Sdim // Register is assigned, put it back on the queue for reassignment. 164321369Sdim LiveInterval &LI = LIS->getInterval(VirtReg); 165321369Sdim Matrix->unassign(LI); 166321369Sdim enqueue(&LI); 167321369Sdim} 168321369Sdim 169218885SdimRABasic::RABasic(): MachineFunctionPass(ID) { 170218885Sdim} 171218885Sdim 172218885Sdimvoid RABasic::getAnalysisUsage(AnalysisUsage &AU) const { 173218885Sdim AU.setPreservesCFG(); 174296417Sdim AU.addRequired<AAResultsWrapperPass>(); 175296417Sdim AU.addPreserved<AAResultsWrapperPass>(); 176218885Sdim AU.addRequired<LiveIntervals>(); 177239462Sdim AU.addPreserved<LiveIntervals>(); 178218885Sdim AU.addPreserved<SlotIndexes>(); 179221345Sdim AU.addRequired<LiveDebugVariables>(); 180221345Sdim AU.addPreserved<LiveDebugVariables>(); 181218885Sdim AU.addRequired<LiveStacks>(); 182218885Sdim AU.addPreserved<LiveStacks>(); 183261991Sdim AU.addRequired<MachineBlockFrequencyInfo>(); 184261991Sdim AU.addPreserved<MachineBlockFrequencyInfo>(); 185218885Sdim AU.addRequiredID(MachineDominatorsID); 186218885Sdim AU.addPreservedID(MachineDominatorsID); 187218885Sdim AU.addRequired<MachineLoopInfo>(); 188218885Sdim AU.addPreserved<MachineLoopInfo>(); 189218885Sdim AU.addRequired<VirtRegMap>(); 190218885Sdim AU.addPreserved<VirtRegMap>(); 191239462Sdim AU.addRequired<LiveRegMatrix>(); 192239462Sdim AU.addPreserved<LiveRegMatrix>(); 193218885Sdim MachineFunctionPass::getAnalysisUsage(AU); 194218885Sdim} 195218885Sdim 196218885Sdimvoid RABasic::releaseMemory() { 197276479Sdim SpillerInstance.reset(); 198218885Sdim} 199218885Sdim 200218885Sdim 201218885Sdim// Spill or split all live virtual registers currently unified under PhysReg 202218885Sdim// that interfere with VirtReg. The newly spilled or split live intervals are 203218885Sdim// returned by appending them to SplitVRegs. 204234353Sdimbool RABasic::spillInterferences(LiveInterval &VirtReg, unsigned PhysReg, 205261991Sdim SmallVectorImpl<unsigned> &SplitVRegs) { 206218885Sdim // Record each interference and determine if all are spillable before mutating 207218885Sdim // either the union or live intervals. 208239462Sdim SmallVector<LiveInterval*, 8> Intfs; 209239462Sdim 210218885Sdim // Collect interferences assigned to any alias of the physical register. 211239462Sdim for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 212239462Sdim LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units); 213239462Sdim Q.collectInterferingVRegs(); 214239462Sdim for (unsigned i = Q.interferingVRegs().size(); i; --i) { 215239462Sdim LiveInterval *Intf = Q.interferingVRegs()[i - 1]; 216239462Sdim if (!Intf->isSpillable() || Intf->weight > VirtReg.weight) 217239462Sdim return false; 218239462Sdim Intfs.push_back(Intf); 219218885Sdim } 220218885Sdim } 221341825Sdim LLVM_DEBUG(dbgs() << "spilling " << printReg(PhysReg, TRI) 222341825Sdim << " interferences with " << VirtReg << "\n"); 223239462Sdim assert(!Intfs.empty() && "expected interference"); 224218885Sdim 225218885Sdim // Spill each interfering vreg allocated to PhysReg or an alias. 226239462Sdim for (unsigned i = 0, e = Intfs.size(); i != e; ++i) { 227239462Sdim LiveInterval &Spill = *Intfs[i]; 228239462Sdim 229239462Sdim // Skip duplicates. 230239462Sdim if (!VRM->hasPhys(Spill.reg)) 231239462Sdim continue; 232239462Sdim 233239462Sdim // Deallocate the interfering vreg by removing it from the union. 234239462Sdim // A LiveInterval instance may not be in a union during modification! 235239462Sdim Matrix->unassign(Spill); 236239462Sdim 237239462Sdim // Spill the extracted interval. 238321369Sdim LiveRangeEdit LRE(&Spill, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats); 239239462Sdim spiller().spill(LRE); 240239462Sdim } 241218885Sdim return true; 242218885Sdim} 243218885Sdim 244218885Sdim// Driver for the register assignment and splitting heuristics. 245218885Sdim// Manages iteration over the LiveIntervalUnions. 246218885Sdim// 247218885Sdim// This is a minimal implementation of register assignment and splitting that 248218885Sdim// spills whenever we run out of registers. 249218885Sdim// 250218885Sdim// selectOrSplit can only be called once per live virtual register. We then do a 251218885Sdim// single interference test for each register the correct class until we find an 252218885Sdim// available register. So, the number of interference tests in the worst case is 253218885Sdim// |vregs| * |machineregs|. And since the number of interference tests is 254218885Sdim// minimal, there is no value in caching them outside the scope of 255218885Sdim// selectOrSplit(). 256218885Sdimunsigned RABasic::selectOrSplit(LiveInterval &VirtReg, 257261991Sdim SmallVectorImpl<unsigned> &SplitVRegs) { 258218885Sdim // Populate a list of physical register spill candidates. 259218885Sdim SmallVector<unsigned, 8> PhysRegSpillCands; 260218885Sdim 261218885Sdim // Check for an available register in this class. 262296417Sdim AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo, Matrix); 263239462Sdim while (unsigned PhysReg = Order.next()) { 264239462Sdim // Check for interference in PhysReg 265239462Sdim switch (Matrix->checkInterference(VirtReg, PhysReg)) { 266239462Sdim case LiveRegMatrix::IK_Free: 267239462Sdim // PhysReg is available, allocate it. 268239462Sdim return PhysReg; 269218885Sdim 270239462Sdim case LiveRegMatrix::IK_VirtReg: 271239462Sdim // Only virtual registers in the way, we may be able to spill them. 272239462Sdim PhysRegSpillCands.push_back(PhysReg); 273234353Sdim continue; 274234353Sdim 275239462Sdim default: 276239462Sdim // RegMask or RegUnit interference. 277239462Sdim continue; 278218885Sdim } 279239462Sdim } 280218885Sdim 281218885Sdim // Try to spill another interfering reg with less spill weight. 282218885Sdim for (SmallVectorImpl<unsigned>::iterator PhysRegI = PhysRegSpillCands.begin(), 283239462Sdim PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) { 284239462Sdim if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs)) 285239462Sdim continue; 286218885Sdim 287239462Sdim assert(!Matrix->checkInterference(VirtReg, *PhysRegI) && 288218885Sdim "Interference after spill."); 289218885Sdim // Tell the caller to allocate to this newly freed physical register. 290218885Sdim return *PhysRegI; 291218885Sdim } 292223017Sdim 293218885Sdim // No other spill candidates were found, so spill the current VirtReg. 294341825Sdim LLVM_DEBUG(dbgs() << "spilling: " << VirtReg << '\n'); 295223017Sdim if (!VirtReg.isSpillable()) 296223017Sdim return ~0u; 297321369Sdim LiveRangeEdit LRE(&VirtReg, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats); 298221345Sdim spiller().spill(LRE); 299218885Sdim 300218885Sdim // The live virtual register requesting allocation was spilled, so tell 301218885Sdim // the caller not to allocate anything during this round. 302218885Sdim return 0; 303218885Sdim} 304218885Sdim 305218885Sdimbool RABasic::runOnMachineFunction(MachineFunction &mf) { 306341825Sdim LLVM_DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n" 307341825Sdim << "********** Function: " << mf.getName() << '\n'); 308218885Sdim 309218885Sdim MF = &mf; 310239462Sdim RegAllocBase::init(getAnalysis<VirtRegMap>(), 311239462Sdim getAnalysis<LiveIntervals>(), 312239462Sdim getAnalysis<LiveRegMatrix>()); 313261991Sdim 314296417Sdim calculateSpillWeightsAndHints(*LIS, *MF, VRM, 315261991Sdim getAnalysis<MachineLoopInfo>(), 316261991Sdim getAnalysis<MachineBlockFrequencyInfo>()); 317261991Sdim 318221345Sdim SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); 319218885Sdim 320218885Sdim allocatePhysRegs(); 321309124Sdim postOptimization(); 322218885Sdim 323218885Sdim // Diagnostic output before rewriting 324341825Sdim LLVM_DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n"); 325218885Sdim 326218885Sdim releaseMemory(); 327218885Sdim return true; 328218885Sdim} 329218885Sdim 330218885SdimFunctionPass* llvm::createBasicRegisterAllocator() 331218885Sdim{ 332218885Sdim return new RABasic(); 333218885Sdim} 334