1 //===- RegAllocBase.cpp - Register Allocator Base Class -------------------===//
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-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines the RegAllocBase class which provides common functionality
10 // for LiveIntervalUnion-based register allocators.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "RegAllocBase.h"
15 #include "llvm/ADT/SmallVector.h"
16 #include "llvm/ADT/Statistic.h"
17 #include "llvm/CodeGen/LiveInterval.h"
18 #include "llvm/CodeGen/LiveIntervals.h"
19 #include "llvm/CodeGen/LiveRegMatrix.h"
20 #include "llvm/CodeGen/MachineInstr.h"
21 #include "llvm/CodeGen/MachineModuleInfo.h"
22 #include "llvm/CodeGen/MachineRegisterInfo.h"
23 #include "llvm/CodeGen/Spiller.h"
24 #include "llvm/CodeGen/TargetRegisterInfo.h"
25 #include "llvm/CodeGen/VirtRegMap.h"
26 #include "llvm/IR/Module.h"
27 #include "llvm/Pass.h"
28 #include "llvm/Support/CommandLine.h"
29 #include "llvm/Support/Debug.h"
30 #include "llvm/Support/ErrorHandling.h"
31 #include "llvm/Support/Timer.h"
32 #include "llvm/Support/raw_ostream.h"
33 #include <cassert>
34 
35 using namespace llvm;
36 
37 #define DEBUG_TYPE "regalloc"
38 
39 STATISTIC(NumNewQueued    , "Number of new live ranges queued");
40 
41 // Temporary verification option until we can put verification inside
42 // MachineVerifier.
43 static cl::opt<bool, true>
44     VerifyRegAlloc("verify-regalloc", cl::location(RegAllocBase::VerifyEnabled),
45                    cl::Hidden, cl::desc("Verify during register allocation"));
46 
47 const char RegAllocBase::TimerGroupName[] = "regalloc";
48 const char RegAllocBase::TimerGroupDescription[] = "Register Allocation";
49 bool RegAllocBase::VerifyEnabled = false;
50 
51 //===----------------------------------------------------------------------===//
52 //                         RegAllocBase Implementation
53 //===----------------------------------------------------------------------===//
54 
55 // Pin the vtable to this file.
56 void RegAllocBase::anchor() {}
57 
58 void RegAllocBase::init(VirtRegMap &vrm,
59                         LiveIntervals &lis,
60                         LiveRegMatrix &mat) {
61   TRI = &vrm.getTargetRegInfo();
62   MRI = &vrm.getRegInfo();
63   VRM = &vrm;
64   LIS = &lis;
65   Matrix = &mat;
66   MRI->freezeReservedRegs(vrm.getMachineFunction());
67   RegClassInfo.runOnMachineFunction(vrm.getMachineFunction());
68 }
69 
70 // Visit all the live registers. If they are already assigned to a physical
71 // register, unify them with the corresponding LiveIntervalUnion, otherwise push
72 // them on the priority queue for later assignment.
73 void RegAllocBase::seedLiveRegs() {
74   NamedRegionTimer T("seed", "Seed Live Regs", TimerGroupName,
75                      TimerGroupDescription, TimePassesIsEnabled);
76   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
77     unsigned Reg = Register::index2VirtReg(i);
78     if (MRI->reg_nodbg_empty(Reg))
79       continue;
80     enqueue(&LIS->getInterval(Reg));
81   }
82 }
83 
84 // Top-level driver to manage the queue of unassigned VirtRegs and call the
85 // selectOrSplit implementation.
86 void RegAllocBase::allocatePhysRegs() {
87   seedLiveRegs();
88 
89   // Continue assigning vregs one at a time to available physical registers.
90   while (LiveInterval *VirtReg = dequeue()) {
91     assert(!VRM->hasPhys(VirtReg->reg) && "Register already assigned");
92 
93     // Unused registers can appear when the spiller coalesces snippets.
94     if (MRI->reg_nodbg_empty(VirtReg->reg)) {
95       LLVM_DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n');
96       aboutToRemoveInterval(*VirtReg);
97       LIS->removeInterval(VirtReg->reg);
98       continue;
99     }
100 
101     // Invalidate all interference queries, live ranges could have changed.
102     Matrix->invalidateVirtRegs();
103 
104     // selectOrSplit requests the allocator to return an available physical
105     // register if possible and populate a list of new live intervals that
106     // result from splitting.
107     LLVM_DEBUG(dbgs() << "\nselectOrSplit "
108                       << TRI->getRegClassName(MRI->getRegClass(VirtReg->reg))
109                       << ':' << *VirtReg << " w=" << VirtReg->weight << '\n');
110 
111     using VirtRegVec = SmallVector<Register, 4>;
112 
113     VirtRegVec SplitVRegs;
114     unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs);
115 
116     if (AvailablePhysReg == ~0u) {
117       // selectOrSplit failed to find a register!
118       // Probably caused by an inline asm.
119       MachineInstr *MI = nullptr;
120       for (MachineRegisterInfo::reg_instr_iterator
121            I = MRI->reg_instr_begin(VirtReg->reg), E = MRI->reg_instr_end();
122            I != E; ) {
123         MI = &*(I++);
124         if (MI->isInlineAsm())
125           break;
126       }
127       if (MI && MI->isInlineAsm()) {
128         MI->emitError("inline assembly requires more registers than available");
129       } else if (MI) {
130         LLVMContext &Context =
131             MI->getParent()->getParent()->getMMI().getModule()->getContext();
132         Context.emitError("ran out of registers during register allocation");
133       } else {
134         report_fatal_error("ran out of registers during register allocation");
135       }
136       // Keep going after reporting the error.
137       VRM->assignVirt2Phys(VirtReg->reg,
138                  RegClassInfo.getOrder(MRI->getRegClass(VirtReg->reg)).front());
139       continue;
140     }
141 
142     if (AvailablePhysReg)
143       Matrix->assign(*VirtReg, AvailablePhysReg);
144 
145     for (unsigned Reg : SplitVRegs) {
146       assert(LIS->hasInterval(Reg));
147 
148       LiveInterval *SplitVirtReg = &LIS->getInterval(Reg);
149       assert(!VRM->hasPhys(SplitVirtReg->reg) && "Register already assigned");
150       if (MRI->reg_nodbg_empty(SplitVirtReg->reg)) {
151         assert(SplitVirtReg->empty() && "Non-empty but used interval");
152         LLVM_DEBUG(dbgs() << "not queueing unused  " << *SplitVirtReg << '\n');
153         aboutToRemoveInterval(*SplitVirtReg);
154         LIS->removeInterval(SplitVirtReg->reg);
155         continue;
156       }
157       LLVM_DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n");
158       assert(Register::isVirtualRegister(SplitVirtReg->reg) &&
159              "expect split value in virtual register");
160       enqueue(SplitVirtReg);
161       ++NumNewQueued;
162     }
163   }
164 }
165 
166 void RegAllocBase::postOptimization() {
167   spiller().postOptimization();
168   for (auto DeadInst : DeadRemats) {
169     LIS->RemoveMachineInstrFromMaps(*DeadInst);
170     DeadInst->eraseFromParent();
171   }
172   DeadRemats.clear();
173 }
174