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