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::virtFolded(unsigned virtReg,
68 // move previous memory references folded to new instruction
69 MI2VirtMap::iterator i, e;
70 std::vector<MI2VirtMap::mapped_type> regs;
71 for (tie(i, e) = mi2vMap_.equal_range(oldMI); i != e; ) {
72 regs.push_back(i->second);
75 for (unsigned i = 0, e = regs.size(); i != e; ++i)
76 mi2vMap_.insert(std::make_pair(newMI, i));
78 // add new memory reference
79 mi2vMap_.insert(std::make_pair(newMI, virtReg));
82 std::ostream& llvm::operator<<(std::ostream& os, const VirtRegMap& vrm)
84 const MRegisterInfo* mri = vrm.mf_->getTarget().getRegisterInfo();
86 std::cerr << "********** REGISTER MAP **********\n";
87 for (unsigned i = MRegisterInfo::FirstVirtualRegister,
88 e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
89 if (vrm.v2pMap_[i] != VirtRegMap::NO_PHYS_REG)
90 std::cerr << "[reg" << i << " -> "
91 << mri->getName(vrm.v2pMap_[i]) << "]\n";
93 for (unsigned i = MRegisterInfo::FirstVirtualRegister,
94 e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
95 if (vrm.v2ssMap_[i] != VirtRegMap::NO_STACK_SLOT)
96 std::cerr << "[reg" << i << " -> fi#"
97 << vrm.v2ssMap_[i] << "]\n";
99 return std::cerr << '\n';
109 class SimpleSpiller : public Spiller {
111 bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap& vrm) {
112 DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
113 DEBUG(std::cerr << "********** Function: "
114 << mf.getFunction()->getName() << '\n');
115 const TargetMachine& tm = mf.getTarget();
116 const MRegisterInfo& mri = *tm.getRegisterInfo();
118 typedef DenseMap<bool, VirtReg2IndexFunctor> Loaded;
121 for (MachineFunction::iterator mbbi = mf.begin(),
122 mbbe = mf.end(); mbbi != mbbe; ++mbbi) {
123 DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n");
124 for (MachineBasicBlock::iterator mii = mbbi->begin(),
125 mie = mbbi->end(); mii != mie; ++mii) {
126 loaded.grow(mf.getSSARegMap()->getLastVirtReg());
127 for (unsigned i = 0,e = mii->getNumOperands(); i != e; ++i){
128 MachineOperand& mop = mii->getOperand(i);
129 if (mop.isRegister() && mop.getReg() &&
130 MRegisterInfo::isVirtualRegister(mop.getReg())) {
131 unsigned virtReg = mop.getReg();
132 unsigned physReg = vrm.getPhys(virtReg);
134 vrm.hasStackSlot(mop.getReg()) &&
136 mri.loadRegFromStackSlot(
140 vrm.getStackSlot(virtReg),
141 mf.getSSARegMap()->getRegClass(virtReg));
142 loaded[virtReg] = true;
143 DEBUG(std::cerr << '\t';
144 prior(mii)->print(std::cerr, tm));
148 vrm.hasStackSlot(mop.getReg())) {
149 mri.storeRegToStackSlot(
153 vrm.getStackSlot(virtReg),
154 mf.getSSARegMap()->getRegClass(virtReg));
157 mii->SetMachineOperandReg(i, physReg);
160 DEBUG(std::cerr << '\t'; mii->print(std::cerr, tm));
168 class LocalSpiller : public Spiller {
169 typedef std::vector<unsigned> Phys2VirtMap;
170 typedef std::vector<bool> PhysFlag;
171 typedef DenseMap<MachineInstr*, VirtReg2IndexFunctor> Virt2MI;
173 MachineFunction* mf_;
174 const TargetMachine* tm_;
175 const TargetInstrInfo* tii_;
176 const MRegisterInfo* mri_;
177 const VirtRegMap* vrm_;
178 Phys2VirtMap p2vMap_;
183 bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap& vrm) {
185 tm_ = &mf_->getTarget();
186 tii_ = &tm_->getInstrInfo();
187 mri_ = tm_->getRegisterInfo();
189 p2vMap_.assign(mri_->getNumRegs(), 0);
190 dirty_.assign(mri_->getNumRegs(), false);
192 DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
193 DEBUG(std::cerr << "********** Function: "
194 << mf_->getFunction()->getName() << '\n');
196 for (MachineFunction::iterator mbbi = mf_->begin(),
197 mbbe = mf_->end(); mbbi != mbbe; ++mbbi) {
198 lastDef_.grow(mf_->getSSARegMap()->getLastVirtReg());
199 DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n");
200 eliminateVirtRegsInMbb(*mbbi);
201 // clear map, dirty flag and last ref
202 p2vMap_.assign(p2vMap_.size(), 0);
203 dirty_.assign(dirty_.size(), false);
210 void vacateJustPhysReg(MachineBasicBlock& mbb,
211 MachineBasicBlock::iterator mii,
213 unsigned virtReg = p2vMap_[physReg];
214 if (dirty_[physReg] && vrm_->hasStackSlot(virtReg)) {
215 assert(lastDef_[virtReg] && "virtual register is mapped "
216 "to a register and but was not defined!");
217 MachineBasicBlock::iterator lastDef = lastDef_[virtReg];
218 MachineBasicBlock::iterator nextLastRef = next(lastDef);
219 mri_->storeRegToStackSlot(*lastDef->getParent(),
222 vrm_->getStackSlot(virtReg),
223 mri_->getRegClass(physReg));
225 DEBUG(std::cerr << "added: ";
226 prior(nextLastRef)->print(std::cerr, *tm_);
227 std::cerr << "after: ";
228 lastDef->print(std::cerr, *tm_));
229 lastDef_[virtReg] = 0;
231 p2vMap_[physReg] = 0;
232 dirty_[physReg] = false;
235 void vacatePhysReg(MachineBasicBlock& mbb,
236 MachineBasicBlock::iterator mii,
238 vacateJustPhysReg(mbb, mii, physReg);
239 for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as)
240 vacateJustPhysReg(mbb, mii, *as);
243 void handleUse(MachineBasicBlock& mbb,
244 MachineBasicBlock::iterator mii,
247 // check if we are replacing a previous mapping
248 if (p2vMap_[physReg] != virtReg) {
249 vacatePhysReg(mbb, mii, physReg);
250 p2vMap_[physReg] = virtReg;
252 if (vrm_->hasStackSlot(virtReg)) {
253 mri_->loadRegFromStackSlot(mbb, mii, physReg,
254 vrm_->getStackSlot(virtReg),
255 mri_->getRegClass(physReg));
257 DEBUG(std::cerr << "added: ";
258 prior(mii)->print(std::cerr, *tm_));
259 lastDef_[virtReg] = mii;
264 void handleDef(MachineBasicBlock& mbb,
265 MachineBasicBlock::iterator mii,
268 // check if we are replacing a previous mapping
269 if (p2vMap_[physReg] != virtReg)
270 vacatePhysReg(mbb, mii, physReg);
272 p2vMap_[physReg] = virtReg;
273 dirty_[physReg] = true;
274 lastDef_[virtReg] = mii;
277 void eliminateVirtRegsInMbb(MachineBasicBlock& mbb) {
278 for (MachineBasicBlock::iterator mii = mbb.begin(),
279 mie = mbb.end(); mii != mie; ++mii) {
281 // if we have references to memory operands make sure
282 // we clear all physical registers that may contain
283 // the value of the spilled virtual register
284 VirtRegMap::MI2VirtMap::const_iterator i, e;
285 for (tie(i, e) = vrm_->getFoldedVirts(mii); i != e; ++i) {
286 if (vrm_->hasPhys(i->second))
287 vacateJustPhysReg(mbb, mii, vrm_->getPhys(i->second));
290 // rewrite all used operands
291 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
292 MachineOperand& op = mii->getOperand(i);
293 if (op.isRegister() && op.getReg() && op.isUse() &&
294 MRegisterInfo::isVirtualRegister(op.getReg())) {
295 unsigned virtReg = op.getReg();
296 unsigned physReg = vrm_->getPhys(virtReg);
297 handleUse(mbb, mii, virtReg, physReg);
298 mii->SetMachineOperandReg(i, physReg);
299 // mark as dirty if this is def&use
301 dirty_[physReg] = true;
302 lastDef_[virtReg] = mii;
307 // spill implicit physical register defs
308 const TargetInstrDescriptor& tid = tii_->get(mii->getOpcode());
309 for (const unsigned* id = tid.ImplicitDefs; *id; ++id)
310 vacatePhysReg(mbb, mii, *id);
312 // spill explicit physical register defs
313 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
314 MachineOperand& op = mii->getOperand(i);
315 if (op.isRegister() && op.getReg() && !op.isUse() &&
316 MRegisterInfo::isPhysicalRegister(op.getReg()))
317 vacatePhysReg(mbb, mii, op.getReg());
320 // rewrite def operands (def&use was handled with the
321 // uses so don't check for those here)
322 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
323 MachineOperand& op = mii->getOperand(i);
324 if (op.isRegister() && op.getReg() && !op.isUse())
325 if (MRegisterInfo::isPhysicalRegister(op.getReg()))
326 vacatePhysReg(mbb, mii, op.getReg());
328 unsigned physReg = vrm_->getPhys(op.getReg());
329 handleDef(mbb, mii, op.getReg(), physReg);
330 mii->SetMachineOperandReg(i, physReg);
334 DEBUG(std::cerr << '\t'; mii->print(std::cerr, *tm_));
337 for (unsigned i = 1, e = p2vMap_.size(); i != e; ++i)
338 vacateJustPhysReg(mbb, mbb.getFirstTerminator(), i);
344 llvm::Spiller* llvm::createSpiller()
346 switch (SpillerOpt) {
348 std::cerr << "no spiller selected";
351 return new LocalSpiller();
353 return new SimpleSpiller();