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"
35 Statistic<> numSpills("spiller", "Number of register spills");
36 Statistic<> numStores("spiller", "Number of stores added");
37 Statistic<> numLoads ("spiller", "Number of loads added");
39 enum SpillerName { simple, local };
43 cl::desc("Spiller to use: (default: local)"),
45 cl::values(clEnumVal(simple, " simple spiller"),
46 clEnumVal(local, " local spiller"),
51 int VirtRegMap::assignVirt2StackSlot(unsigned virtReg)
53 assert(MRegisterInfo::isVirtualRegister(virtReg));
54 assert(v2ssMap_[virtReg] == NO_STACK_SLOT &&
55 "attempt to assign stack slot to already spilled register");
56 const TargetRegisterClass* rc =
57 mf_->getSSARegMap()->getRegClass(virtReg);
58 int frameIndex = mf_->getFrameInfo()->CreateStackObject(rc);
59 v2ssMap_[virtReg] = frameIndex;
64 void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int frameIndex)
66 assert(MRegisterInfo::isVirtualRegister(virtReg));
67 assert(v2ssMap_[virtReg] == NO_STACK_SLOT &&
68 "attempt to assign stack slot to already spilled register");
69 v2ssMap_[virtReg] = frameIndex;
72 void VirtRegMap::virtFolded(unsigned virtReg,
76 // move previous memory references folded to new instruction
77 MI2VirtMap::iterator i, e;
78 std::vector<MI2VirtMap::mapped_type> regs;
79 for (tie(i, e) = mi2vMap_.equal_range(oldMI); i != e; ) {
80 regs.push_back(i->second);
83 for (unsigned i = 0, e = regs.size(); i != e; ++i)
84 mi2vMap_.insert(std::make_pair(newMI, i));
86 // add new memory reference
87 mi2vMap_.insert(std::make_pair(newMI, virtReg));
90 std::ostream& llvm::operator<<(std::ostream& os, const VirtRegMap& vrm)
92 const MRegisterInfo* mri = vrm.mf_->getTarget().getRegisterInfo();
94 std::cerr << "********** REGISTER MAP **********\n";
95 for (unsigned i = MRegisterInfo::FirstVirtualRegister,
96 e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
97 if (vrm.v2pMap_[i] != VirtRegMap::NO_PHYS_REG)
98 std::cerr << "[reg" << i << " -> "
99 << mri->getName(vrm.v2pMap_[i]) << "]\n";
101 for (unsigned i = MRegisterInfo::FirstVirtualRegister,
102 e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
103 if (vrm.v2ssMap_[i] != VirtRegMap::NO_STACK_SLOT)
104 std::cerr << "[reg" << i << " -> fi#"
105 << vrm.v2ssMap_[i] << "]\n";
107 return std::cerr << '\n';
117 class SimpleSpiller : public Spiller {
119 bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap& vrm) {
120 DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
121 DEBUG(std::cerr << "********** Function: "
122 << mf.getFunction()->getName() << '\n');
123 const TargetMachine& tm = mf.getTarget();
124 const MRegisterInfo& mri = *tm.getRegisterInfo();
126 typedef DenseMap<bool, VirtReg2IndexFunctor> Loaded;
129 for (MachineFunction::iterator mbbi = mf.begin(),
130 mbbe = mf.end(); mbbi != mbbe; ++mbbi) {
131 DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n");
132 for (MachineBasicBlock::iterator mii = mbbi->begin(),
133 mie = mbbi->end(); mii != mie; ++mii) {
134 loaded.grow(mf.getSSARegMap()->getLastVirtReg());
135 for (unsigned i = 0,e = mii->getNumOperands(); i != e; ++i){
136 MachineOperand& mop = mii->getOperand(i);
137 if (mop.isRegister() && mop.getReg() &&
138 MRegisterInfo::isVirtualRegister(mop.getReg())) {
139 unsigned virtReg = mop.getReg();
140 unsigned physReg = vrm.getPhys(virtReg);
142 vrm.hasStackSlot(mop.getReg()) &&
144 mri.loadRegFromStackSlot(
148 vrm.getStackSlot(virtReg),
149 mf.getSSARegMap()->getRegClass(virtReg));
150 loaded[virtReg] = true;
151 DEBUG(std::cerr << '\t';
152 prior(mii)->print(std::cerr, tm));
156 vrm.hasStackSlot(mop.getReg())) {
157 mri.storeRegToStackSlot(
161 vrm.getStackSlot(virtReg),
162 mf.getSSARegMap()->getRegClass(virtReg));
165 mii->SetMachineOperandReg(i, physReg);
168 DEBUG(std::cerr << '\t'; mii->print(std::cerr, tm));
176 class LocalSpiller : public Spiller {
177 typedef std::vector<unsigned> Phys2VirtMap;
178 typedef std::vector<bool> PhysFlag;
179 typedef DenseMap<MachineInstr*, VirtReg2IndexFunctor> Virt2MI;
181 MachineFunction* mf_;
182 const TargetMachine* tm_;
183 const TargetInstrInfo* tii_;
184 const MRegisterInfo* mri_;
185 const VirtRegMap* vrm_;
186 Phys2VirtMap p2vMap_;
191 bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap& vrm) {
193 tm_ = &mf_->getTarget();
194 tii_ = &tm_->getInstrInfo();
195 mri_ = tm_->getRegisterInfo();
197 p2vMap_.assign(mri_->getNumRegs(), 0);
198 dirty_.assign(mri_->getNumRegs(), false);
200 DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
201 DEBUG(std::cerr << "********** Function: "
202 << mf_->getFunction()->getName() << '\n');
204 for (MachineFunction::iterator mbbi = mf_->begin(),
205 mbbe = mf_->end(); mbbi != mbbe; ++mbbi) {
206 lastDef_.grow(mf_->getSSARegMap()->getLastVirtReg());
207 DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n");
208 eliminateVirtRegsInMbb(*mbbi);
209 // clear map, dirty flag and last ref
210 p2vMap_.assign(p2vMap_.size(), 0);
211 dirty_.assign(dirty_.size(), false);
218 void vacateJustPhysReg(MachineBasicBlock& mbb,
219 MachineBasicBlock::iterator mii,
221 unsigned virtReg = p2vMap_[physReg];
222 if (dirty_[physReg] && vrm_->hasStackSlot(virtReg)) {
223 assert(lastDef_[virtReg] && "virtual register is mapped "
224 "to a register and but was not defined!");
225 MachineBasicBlock::iterator lastDef = lastDef_[virtReg];
226 MachineBasicBlock::iterator nextLastRef = next(lastDef);
227 mri_->storeRegToStackSlot(*lastDef->getParent(),
230 vrm_->getStackSlot(virtReg),
231 mri_->getRegClass(physReg));
233 DEBUG(std::cerr << "added: ";
234 prior(nextLastRef)->print(std::cerr, *tm_);
235 std::cerr << "after: ";
236 lastDef->print(std::cerr, *tm_));
237 lastDef_[virtReg] = 0;
239 p2vMap_[physReg] = 0;
240 dirty_[physReg] = false;
243 void vacatePhysReg(MachineBasicBlock& mbb,
244 MachineBasicBlock::iterator mii,
246 vacateJustPhysReg(mbb, mii, physReg);
247 for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as)
248 vacateJustPhysReg(mbb, mii, *as);
251 void handleUse(MachineBasicBlock& mbb,
252 MachineBasicBlock::iterator mii,
255 // check if we are replacing a previous mapping
256 if (p2vMap_[physReg] != virtReg) {
257 vacatePhysReg(mbb, mii, physReg);
258 p2vMap_[physReg] = virtReg;
260 if (vrm_->hasStackSlot(virtReg)) {
261 mri_->loadRegFromStackSlot(mbb, mii, physReg,
262 vrm_->getStackSlot(virtReg),
263 mri_->getRegClass(physReg));
265 DEBUG(std::cerr << "added: ";
266 prior(mii)->print(std::cerr, *tm_));
267 lastDef_[virtReg] = mii;
272 void handleDef(MachineBasicBlock& mbb,
273 MachineBasicBlock::iterator mii,
276 // check if we are replacing a previous mapping
277 if (p2vMap_[physReg] != virtReg)
278 vacatePhysReg(mbb, mii, physReg);
280 p2vMap_[physReg] = virtReg;
281 dirty_[physReg] = true;
282 lastDef_[virtReg] = mii;
285 void eliminateVirtRegsInMbb(MachineBasicBlock& mbb) {
286 for (MachineBasicBlock::iterator mii = mbb.begin(),
287 mie = mbb.end(); mii != mie; ++mii) {
289 // if we have references to memory operands make sure
290 // we clear all physical registers that may contain
291 // the value of the spilled virtual register
292 VirtRegMap::MI2VirtMap::const_iterator i, e;
293 for (tie(i, e) = vrm_->getFoldedVirts(mii); i != e; ++i) {
294 if (vrm_->hasPhys(i->second))
295 vacateJustPhysReg(mbb, mii, vrm_->getPhys(i->second));
298 // rewrite all used operands
299 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
300 MachineOperand& op = mii->getOperand(i);
301 if (op.isRegister() && op.getReg() && op.isUse() &&
302 MRegisterInfo::isVirtualRegister(op.getReg())) {
303 unsigned virtReg = op.getReg();
304 unsigned physReg = vrm_->getPhys(virtReg);
305 handleUse(mbb, mii, virtReg, physReg);
306 mii->SetMachineOperandReg(i, physReg);
307 // mark as dirty if this is def&use
309 dirty_[physReg] = true;
310 lastDef_[virtReg] = mii;
315 // spill implicit physical register defs
316 const TargetInstrDescriptor& tid = tii_->get(mii->getOpcode());
317 for (const unsigned* id = tid.ImplicitDefs; *id; ++id)
318 vacatePhysReg(mbb, mii, *id);
320 // spill explicit physical register defs
321 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
322 MachineOperand& op = mii->getOperand(i);
323 if (op.isRegister() && op.getReg() && !op.isUse() &&
324 MRegisterInfo::isPhysicalRegister(op.getReg()))
325 vacatePhysReg(mbb, mii, op.getReg());
328 // rewrite def operands (def&use was handled with the
329 // uses so don't check for those here)
330 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
331 MachineOperand& op = mii->getOperand(i);
332 if (op.isRegister() && op.getReg() && !op.isUse())
333 if (MRegisterInfo::isPhysicalRegister(op.getReg()))
334 vacatePhysReg(mbb, mii, op.getReg());
336 unsigned physReg = vrm_->getPhys(op.getReg());
337 handleDef(mbb, mii, op.getReg(), physReg);
338 mii->SetMachineOperandReg(i, physReg);
342 DEBUG(std::cerr << '\t'; mii->print(std::cerr, *tm_));
345 for (unsigned i = 1, e = p2vMap_.size(); i != e; ++i)
346 vacateJustPhysReg(mbb, mbb.getFirstTerminator(), i);
352 llvm::Spiller* llvm::createSpiller()
354 switch (SpillerOpt) {
356 std::cerr << "no spiller selected";
359 return new LocalSpiller();
361 return new SimpleSpiller();