1 //===-- llvm/CodeGen/VirtRegMap.cpp - Virtual Register Map ----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the virtual register map. It also implements
11 // the eliminateVirtRegs() function that given a virtual register map
12 // and a machine function it eliminates all virtual references by
13 // replacing them with physical register references and adds spill
16 //===----------------------------------------------------------------------===//
18 #define DEBUG_TYPE "regalloc"
19 #include "VirtRegMap.h"
20 #include "llvm/Function.h"
21 #include "llvm/CodeGen/MachineFrameInfo.h"
22 #include "llvm/CodeGen/MachineInstr.h"
23 #include "llvm/Target/TargetMachine.h"
24 #include "llvm/Target/TargetInstrInfo.h"
25 #include "Support/CommandLine.h"
26 #include "Support/Debug.h"
27 #include "Support/DenseMap.h"
28 #include "Support/Statistic.h"
29 #include "Support/STLExtras.h"
34 Statistic<> numSpills("spiller", "Number of register spills");
35 Statistic<> numStores("spiller", "Number of stores added");
36 Statistic<> numLoads ("spiller", "Number of loads added");
38 enum SpillerName { simple, local };
42 cl::desc("Spiller to use: (default: local)"),
44 cl::values(clEnumVal(simple, " simple spiller"),
45 clEnumVal(local, " local spiller"),
50 int VirtRegMap::assignVirt2StackSlot(unsigned virtReg)
52 assert(MRegisterInfo::isVirtualRegister(virtReg));
53 assert(v2ssMap_[virtReg] == NO_STACK_SLOT &&
54 "attempt to assign stack slot to already spilled register");
55 const TargetRegisterClass* rc =
56 mf_->getSSARegMap()->getRegClass(virtReg);
57 int frameIndex = mf_->getFrameInfo()->CreateStackObject(rc);
58 v2ssMap_[virtReg] = frameIndex;
63 void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int frameIndex)
65 assert(MRegisterInfo::isVirtualRegister(virtReg));
66 assert(v2ssMap_[virtReg] == NO_STACK_SLOT &&
67 "attempt to assign stack slot to already spilled register");
68 v2ssMap_[virtReg] = frameIndex;
71 void VirtRegMap::virtFolded(unsigned virtReg,
75 // move previous memory references folded to new instruction
76 MI2VirtMap::iterator i, e;
77 std::vector<MI2VirtMap::mapped_type> regs;
78 for (tie(i, e) = mi2vMap_.equal_range(oldMI); i != e; ) {
79 regs.push_back(i->second);
82 for (unsigned i = 0, e = regs.size(); i != e; ++i)
83 mi2vMap_.insert(std::make_pair(newMI, i));
85 // add new memory reference
86 mi2vMap_.insert(std::make_pair(newMI, virtReg));
89 std::ostream& llvm::operator<<(std::ostream& os, const VirtRegMap& vrm)
91 const MRegisterInfo* mri = vrm.mf_->getTarget().getRegisterInfo();
93 std::cerr << "********** REGISTER MAP **********\n";
94 for (unsigned i = MRegisterInfo::FirstVirtualRegister,
95 e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
96 if (vrm.v2pMap_[i] != VirtRegMap::NO_PHYS_REG)
97 std::cerr << "[reg" << i << " -> "
98 << mri->getName(vrm.v2pMap_[i]) << "]\n";
100 for (unsigned i = MRegisterInfo::FirstVirtualRegister,
101 e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
102 if (vrm.v2ssMap_[i] != VirtRegMap::NO_STACK_SLOT)
103 std::cerr << "[reg" << i << " -> fi#"
104 << vrm.v2ssMap_[i] << "]\n";
106 return std::cerr << '\n';
116 class SimpleSpiller : public Spiller {
118 bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap& vrm) {
119 DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
120 DEBUG(std::cerr << "********** Function: "
121 << mf.getFunction()->getName() << '\n');
122 const TargetMachine& tm = mf.getTarget();
123 const MRegisterInfo& mri = *tm.getRegisterInfo();
125 typedef DenseMap<bool, VirtReg2IndexFunctor> Loaded;
128 for (MachineFunction::iterator mbbi = mf.begin(),
129 mbbe = mf.end(); mbbi != mbbe; ++mbbi) {
130 DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n");
131 for (MachineBasicBlock::iterator mii = mbbi->begin(),
132 mie = mbbi->end(); mii != mie; ++mii) {
133 loaded.grow(mf.getSSARegMap()->getLastVirtReg());
134 for (unsigned i = 0,e = mii->getNumOperands(); i != e; ++i){
135 MachineOperand& mop = mii->getOperand(i);
136 if (mop.isRegister() && mop.getReg() &&
137 MRegisterInfo::isVirtualRegister(mop.getReg())) {
138 unsigned virtReg = mop.getReg();
139 unsigned physReg = vrm.getPhys(virtReg);
141 vrm.hasStackSlot(mop.getReg()) &&
143 mri.loadRegFromStackSlot(
147 vrm.getStackSlot(virtReg),
148 mf.getSSARegMap()->getRegClass(virtReg));
149 loaded[virtReg] = true;
150 DEBUG(std::cerr << '\t';
151 prior(mii)->print(std::cerr, &tm));
155 vrm.hasStackSlot(mop.getReg())) {
156 mri.storeRegToStackSlot(
160 vrm.getStackSlot(virtReg),
161 mf.getSSARegMap()->getRegClass(virtReg));
164 mii->SetMachineOperandReg(i, physReg);
167 DEBUG(std::cerr << '\t'; mii->print(std::cerr, &tm));
175 class LocalSpiller : public Spiller {
176 typedef std::vector<unsigned> Phys2VirtMap;
177 typedef std::vector<bool> PhysFlag;
178 typedef DenseMap<MachineInstr*, VirtReg2IndexFunctor> Virt2MI;
180 MachineFunction* mf_;
181 const TargetMachine* tm_;
182 const TargetInstrInfo* tii_;
183 const MRegisterInfo* mri_;
184 const VirtRegMap* vrm_;
185 Phys2VirtMap p2vMap_;
190 bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap& vrm) {
192 tm_ = &mf_->getTarget();
193 tii_ = tm_->getInstrInfo();
194 mri_ = tm_->getRegisterInfo();
196 p2vMap_.assign(mri_->getNumRegs(), 0);
197 dirty_.assign(mri_->getNumRegs(), false);
199 DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
200 DEBUG(std::cerr << "********** Function: "
201 << mf_->getFunction()->getName() << '\n');
203 for (MachineFunction::iterator mbbi = mf_->begin(),
204 mbbe = mf_->end(); mbbi != mbbe; ++mbbi) {
205 lastDef_.grow(mf_->getSSARegMap()->getLastVirtReg());
206 DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n");
207 eliminateVirtRegsInMbb(*mbbi);
208 // clear map, dirty flag and last ref
209 p2vMap_.assign(p2vMap_.size(), 0);
210 dirty_.assign(dirty_.size(), false);
217 void vacateJustPhysReg(MachineBasicBlock& mbb,
218 MachineBasicBlock::iterator mii,
220 unsigned virtReg = p2vMap_[physReg];
221 if (dirty_[physReg] && vrm_->hasStackSlot(virtReg)) {
222 assert(lastDef_[virtReg] && "virtual register is mapped "
223 "to a register and but was not defined!");
224 MachineBasicBlock::iterator lastDef = lastDef_[virtReg];
225 MachineBasicBlock::iterator nextLastRef = next(lastDef);
226 mri_->storeRegToStackSlot(*lastDef->getParent(),
229 vrm_->getStackSlot(virtReg),
230 mri_->getRegClass(physReg));
232 DEBUG(std::cerr << "added: ";
233 prior(nextLastRef)->print(std::cerr, tm_);
234 std::cerr << "after: ";
235 lastDef->print(std::cerr, tm_));
236 lastDef_[virtReg] = 0;
238 p2vMap_[physReg] = 0;
239 dirty_[physReg] = false;
242 void vacatePhysReg(MachineBasicBlock& mbb,
243 MachineBasicBlock::iterator mii,
245 vacateJustPhysReg(mbb, mii, physReg);
246 for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as)
247 vacateJustPhysReg(mbb, mii, *as);
250 void handleUse(MachineBasicBlock& mbb,
251 MachineBasicBlock::iterator mii,
254 // check if we are replacing a previous mapping
255 if (p2vMap_[physReg] != virtReg) {
256 vacatePhysReg(mbb, mii, physReg);
257 p2vMap_[physReg] = virtReg;
259 if (vrm_->hasStackSlot(virtReg)) {
260 mri_->loadRegFromStackSlot(mbb, mii, physReg,
261 vrm_->getStackSlot(virtReg),
262 mri_->getRegClass(physReg));
264 DEBUG(std::cerr << "added: ";
265 prior(mii)->print(std::cerr, tm_));
266 lastDef_[virtReg] = mii;
271 void handleDef(MachineBasicBlock& mbb,
272 MachineBasicBlock::iterator mii,
275 // check if we are replacing a previous mapping
276 if (p2vMap_[physReg] != virtReg)
277 vacatePhysReg(mbb, mii, physReg);
279 p2vMap_[physReg] = virtReg;
280 dirty_[physReg] = true;
281 lastDef_[virtReg] = mii;
284 void eliminateVirtRegsInMbb(MachineBasicBlock& mbb) {
285 for (MachineBasicBlock::iterator mii = mbb.begin(),
286 mie = mbb.end(); mii != mie; ++mii) {
288 // if we have references to memory operands make sure
289 // we clear all physical registers that may contain
290 // the value of the spilled virtual register
291 VirtRegMap::MI2VirtMap::const_iterator i, e;
292 for (tie(i, e) = vrm_->getFoldedVirts(mii); i != e; ++i) {
293 if (vrm_->hasPhys(i->second))
294 vacateJustPhysReg(mbb, mii, vrm_->getPhys(i->second));
297 // rewrite all used operands
298 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
299 MachineOperand& op = mii->getOperand(i);
300 if (op.isRegister() && op.getReg() && op.isUse() &&
301 MRegisterInfo::isVirtualRegister(op.getReg())) {
302 unsigned virtReg = op.getReg();
303 unsigned physReg = vrm_->getPhys(virtReg);
304 handleUse(mbb, mii, virtReg, physReg);
305 mii->SetMachineOperandReg(i, physReg);
306 // mark as dirty if this is def&use
308 dirty_[physReg] = true;
309 lastDef_[virtReg] = mii;
314 // spill implicit physical register defs
315 const TargetInstrDescriptor& tid = tii_->get(mii->getOpcode());
316 for (const unsigned* id = tid.ImplicitDefs; *id; ++id)
317 vacatePhysReg(mbb, mii, *id);
319 // spill explicit physical register defs
320 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
321 MachineOperand& op = mii->getOperand(i);
322 if (op.isRegister() && op.getReg() && !op.isUse() &&
323 MRegisterInfo::isPhysicalRegister(op.getReg()))
324 vacatePhysReg(mbb, mii, op.getReg());
327 // rewrite def operands (def&use was handled with the
328 // uses so don't check for those here)
329 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
330 MachineOperand& op = mii->getOperand(i);
331 if (op.isRegister() && op.getReg() && !op.isUse())
332 if (MRegisterInfo::isPhysicalRegister(op.getReg()))
333 vacatePhysReg(mbb, mii, op.getReg());
335 unsigned physReg = vrm_->getPhys(op.getReg());
336 handleDef(mbb, mii, op.getReg(), physReg);
337 mii->SetMachineOperandReg(i, physReg);
341 DEBUG(std::cerr << '\t'; mii->print(std::cerr, tm_));
344 for (unsigned i = 1, e = p2vMap_.size(); i != e; ++i)
345 vacateJustPhysReg(mbb, mbb.getFirstTerminator(), i);
351 llvm::Spiller* llvm::createSpiller()
353 switch (SpillerOpt) {
355 std::cerr << "no spiller selected";
358 return new LocalSpiller();
360 return new SimpleSpiller();