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"),
52 int VirtRegMap::assignVirt2StackSlot(unsigned virtReg)
54 assert(MRegisterInfo::isVirtualRegister(virtReg));
55 assert(v2ssMap_[virtReg] == NO_STACK_SLOT &&
56 "attempt to assign stack slot to already spilled register");
57 const TargetRegisterClass* rc =
58 mf_->getSSARegMap()->getRegClass(virtReg);
59 int frameIndex = mf_->getFrameInfo()->CreateStackObject(rc);
60 v2ssMap_[virtReg] = frameIndex;
65 void VirtRegMap::virtFolded(unsigned virtReg,
69 // move previous memory references folded to new instruction
70 MI2VirtMap::iterator i, e;
71 std::vector<MI2VirtMap::mapped_type> regs;
72 for (tie(i, e) = mi2vMap_.equal_range(oldMI); i != e; ) {
73 regs.push_back(i->second);
76 for (unsigned i = 0, e = regs.size(); i != e; ++i)
77 mi2vMap_.insert(std::make_pair(newMI, i));
79 // add new memory reference
80 mi2vMap_.insert(std::make_pair(newMI, virtReg));
83 std::ostream& llvm::operator<<(std::ostream& os, const VirtRegMap& vrm)
85 const MRegisterInfo* mri = vrm.mf_->getTarget().getRegisterInfo();
87 std::cerr << "********** REGISTER MAP **********\n";
88 for (unsigned i = MRegisterInfo::FirstVirtualRegister,
89 e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
90 if (vrm.v2pMap_[i] != VirtRegMap::NO_PHYS_REG)
91 std::cerr << "[reg" << i << " -> "
92 << mri->getName(vrm.v2pMap_[i]) << "]\n";
94 for (unsigned i = MRegisterInfo::FirstVirtualRegister,
95 e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
96 if (vrm.v2ssMap_[i] != VirtRegMap::NO_STACK_SLOT)
97 std::cerr << "[reg" << i << " -> fi#"
98 << vrm.v2ssMap_[i] << "]\n";
100 return std::cerr << '\n';
110 class SimpleSpiller : public Spiller {
112 bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap& vrm) {
113 DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
114 DEBUG(std::cerr << "********** Function: "
115 << mf.getFunction()->getName() << '\n');
116 const TargetMachine& tm = mf.getTarget();
117 const MRegisterInfo& mri = *tm.getRegisterInfo();
119 typedef DenseMap<bool, VirtReg2IndexFunctor> Loaded;
122 for (MachineFunction::iterator mbbi = mf.begin(),
123 mbbe = mf.end(); mbbi != mbbe; ++mbbi) {
124 DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n");
125 for (MachineBasicBlock::iterator mii = mbbi->begin(),
126 mie = mbbi->end(); mii != mie; ++mii) {
127 loaded.grow(mf.getSSARegMap()->getLastVirtReg());
128 for (unsigned i = 0,e = mii->getNumOperands(); i != e; ++i){
129 MachineOperand& mop = mii->getOperand(i);
130 if (mop.isRegister() && mop.getReg() &&
131 MRegisterInfo::isVirtualRegister(mop.getReg())) {
132 unsigned virtReg = mop.getReg();
133 unsigned physReg = vrm.getPhys(virtReg);
135 vrm.hasStackSlot(mop.getReg()) &&
137 mri.loadRegFromStackSlot(
141 vrm.getStackSlot(virtReg),
142 mf.getSSARegMap()->getRegClass(virtReg));
143 loaded[virtReg] = true;
144 DEBUG(std::cerr << '\t';
145 prior(mii)->print(std::cerr, tm));
149 vrm.hasStackSlot(mop.getReg())) {
150 mri.storeRegToStackSlot(
154 vrm.getStackSlot(virtReg),
155 mf.getSSARegMap()->getRegClass(virtReg));
158 mii->SetMachineOperandReg(i, physReg);
161 DEBUG(std::cerr << '\t'; mii->print(std::cerr, tm));
169 class LocalSpiller : public Spiller {
170 typedef std::vector<unsigned> Phys2VirtMap;
171 typedef std::vector<bool> PhysFlag;
172 typedef DenseMap<MachineInstr*, VirtReg2IndexFunctor> Virt2MI;
174 MachineFunction* mf_;
175 const TargetMachine* tm_;
176 const TargetInstrInfo* tii_;
177 const MRegisterInfo* mri_;
178 const VirtRegMap* vrm_;
179 Phys2VirtMap p2vMap_;
184 bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap& vrm) {
186 tm_ = &mf_->getTarget();
187 tii_ = &tm_->getInstrInfo();
188 mri_ = tm_->getRegisterInfo();
190 p2vMap_.assign(mri_->getNumRegs(), 0);
191 dirty_.assign(mri_->getNumRegs(), false);
193 DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
194 DEBUG(std::cerr << "********** Function: "
195 << mf_->getFunction()->getName() << '\n');
197 for (MachineFunction::iterator mbbi = mf_->begin(),
198 mbbe = mf_->end(); mbbi != mbbe; ++mbbi) {
199 lastDef_.grow(mf_->getSSARegMap()->getLastVirtReg());
200 DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n");
201 eliminateVirtRegsInMbb(*mbbi);
202 // clear map, dirty flag and last ref
203 p2vMap_.assign(p2vMap_.size(), 0);
204 dirty_.assign(dirty_.size(), false);
211 void vacateJustPhysReg(MachineBasicBlock& mbb,
212 MachineBasicBlock::iterator mii,
214 unsigned virtReg = p2vMap_[physReg];
215 if (dirty_[physReg] && vrm_->hasStackSlot(virtReg)) {
216 assert(lastDef_[virtReg] && "virtual register is mapped "
217 "to a register and but was not defined!");
218 MachineBasicBlock::iterator lastDef = lastDef_[virtReg];
219 MachineBasicBlock::iterator nextLastRef = next(lastDef);
220 mri_->storeRegToStackSlot(*lastDef->getParent(),
223 vrm_->getStackSlot(virtReg),
224 mri_->getRegClass(physReg));
226 DEBUG(std::cerr << "added: ";
227 prior(nextLastRef)->print(std::cerr, *tm_);
228 std::cerr << "after: ";
229 lastDef->print(std::cerr, *tm_));
230 lastDef_[virtReg] = 0;
232 p2vMap_[physReg] = 0;
233 dirty_[physReg] = false;
236 void vacatePhysReg(MachineBasicBlock& mbb,
237 MachineBasicBlock::iterator mii,
239 vacateJustPhysReg(mbb, mii, physReg);
240 for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as)
241 vacateJustPhysReg(mbb, mii, *as);
244 void handleUse(MachineBasicBlock& mbb,
245 MachineBasicBlock::iterator mii,
248 // check if we are replacing a previous mapping
249 if (p2vMap_[physReg] != virtReg) {
250 vacatePhysReg(mbb, mii, physReg);
251 p2vMap_[physReg] = virtReg;
253 if (vrm_->hasStackSlot(virtReg)) {
254 mri_->loadRegFromStackSlot(mbb, mii, physReg,
255 vrm_->getStackSlot(virtReg),
256 mri_->getRegClass(physReg));
258 DEBUG(std::cerr << "added: ";
259 prior(mii)->print(std::cerr, *tm_));
260 lastDef_[virtReg] = mii;
265 void handleDef(MachineBasicBlock& mbb,
266 MachineBasicBlock::iterator mii,
269 // check if we are replacing a previous mapping
270 if (p2vMap_[physReg] != virtReg)
271 vacatePhysReg(mbb, mii, physReg);
273 p2vMap_[physReg] = virtReg;
274 dirty_[physReg] = true;
275 lastDef_[virtReg] = mii;
278 void eliminateVirtRegsInMbb(MachineBasicBlock& mbb) {
279 for (MachineBasicBlock::iterator mii = mbb.begin(),
280 mie = mbb.end(); mii != mie; ++mii) {
282 // if we have references to memory operands make sure
283 // we clear all physical registers that may contain
284 // the value of the spilled virtual register
285 VirtRegMap::MI2VirtMap::const_iterator i, e;
286 for (tie(i, e) = vrm_->getFoldedVirts(mii); i != e; ++i) {
287 unsigned physReg = vrm_->getPhys(i->second);
288 if (physReg) vacateJustPhysReg(mbb, mii, physReg);
291 // rewrite all used operands
292 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
293 MachineOperand& op = mii->getOperand(i);
294 if (op.isRegister() && op.getReg() && op.isUse() &&
295 MRegisterInfo::isVirtualRegister(op.getReg())) {
296 unsigned virtReg = op.getReg();
297 unsigned physReg = vrm_->getPhys(virtReg);
298 handleUse(mbb, mii, virtReg, physReg);
299 mii->SetMachineOperandReg(i, physReg);
300 // mark as dirty if this is def&use
302 dirty_[physReg] = true;
303 lastDef_[virtReg] = mii;
308 // spill implicit defs
309 const TargetInstrDescriptor& tid = tii_->get(mii->getOpcode());
310 for (const unsigned* id = tid.ImplicitDefs; *id; ++id)
311 vacatePhysReg(mbb, mii, *id);
313 // rewrite def operands (def&use was handled with the
314 // uses so don't check for those here)
315 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
316 MachineOperand& op = mii->getOperand(i);
317 if (op.isRegister() && op.getReg() && !op.isUse())
318 if (MRegisterInfo::isPhysicalRegister(op.getReg()))
319 vacatePhysReg(mbb, mii, op.getReg());
321 unsigned physReg = vrm_->getPhys(op.getReg());
322 handleDef(mbb, mii, op.getReg(), physReg);
323 mii->SetMachineOperandReg(i, physReg);
327 DEBUG(std::cerr << '\t'; mii->print(std::cerr, *tm_));
330 for (unsigned i = 1, e = p2vMap_.size(); i != e; ++i)
331 vacateJustPhysReg(mbb, mbb.getFirstTerminator(), i);
337 llvm::Spiller* llvm::createSpiller()
339 switch (SpillerOpt) {
341 std::cerr << "no spiller selected";
344 return new LocalSpiller();
346 return new SimpleSpiller();