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 VirtRegMap class.
12 // It also contains implementations of the the Spiller interface, which, given a
13 // virtual register map and a machine function, eliminates all virtual
14 // references by replacing them with physical register references - adding spill
17 //===----------------------------------------------------------------------===//
19 #define DEBUG_TYPE "spiller"
20 #include "VirtRegMap.h"
21 #include "llvm/Function.h"
22 #include "llvm/CodeGen/MachineFrameInfo.h"
23 #include "llvm/CodeGen/MachineFunction.h"
24 #include "llvm/CodeGen/SSARegMap.h"
25 #include "llvm/Target/TargetMachine.h"
26 #include "llvm/Target/TargetInstrInfo.h"
27 #include "llvm/Support/CommandLine.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/ADT/Statistic.h"
30 #include "llvm/ADT/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 //===----------------------------------------------------------------------===//
51 // VirtRegMap implementation
52 //===----------------------------------------------------------------------===//
54 void VirtRegMap::grow() {
55 Virt2PhysMap.grow(MF.getSSARegMap()->getLastVirtReg());
56 Virt2StackSlotMap.grow(MF.getSSARegMap()->getLastVirtReg());
59 int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) {
60 assert(MRegisterInfo::isVirtualRegister(virtReg));
61 assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
62 "attempt to assign stack slot to already spilled register");
63 const TargetRegisterClass* RC = MF.getSSARegMap()->getRegClass(virtReg);
64 int frameIndex = MF.getFrameInfo()->CreateStackObject(RC->getSize(),
66 Virt2StackSlotMap[virtReg] = frameIndex;
71 void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int frameIndex) {
72 assert(MRegisterInfo::isVirtualRegister(virtReg));
73 assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
74 "attempt to assign stack slot to already spilled register");
75 Virt2StackSlotMap[virtReg] = frameIndex;
78 void VirtRegMap::virtFolded(unsigned virtReg,
80 MachineInstr* newMI) {
81 // move previous memory references folded to new instruction
82 MI2VirtMapTy::iterator i, e;
83 std::vector<MI2VirtMapTy::mapped_type> regs;
84 for (tie(i, e) = MI2VirtMap.equal_range(oldMI); i != e; ) {
85 regs.push_back(i->second);
86 MI2VirtMap.erase(i++);
88 for (unsigned i = 0, e = regs.size(); i != e; ++i)
89 MI2VirtMap.insert(std::make_pair(newMI, i));
91 // add new memory reference
92 MI2VirtMap.insert(std::make_pair(newMI, virtReg));
95 void VirtRegMap::print(std::ostream &OS) const {
96 const MRegisterInfo* MRI = MF.getTarget().getRegisterInfo();
98 OS << "********** REGISTER MAP **********\n";
99 for (unsigned i = MRegisterInfo::FirstVirtualRegister,
100 e = MF.getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
101 if (Virt2PhysMap[i] != (unsigned)VirtRegMap::NO_PHYS_REG)
102 OS << "[reg" << i << " -> " << MRI->getName(Virt2PhysMap[i]) << "]\n";
106 for (unsigned i = MRegisterInfo::FirstVirtualRegister,
107 e = MF.getSSARegMap()->getLastVirtReg(); i <= e; ++i)
108 if (Virt2StackSlotMap[i] != VirtRegMap::NO_STACK_SLOT)
109 OS << "[reg" << i << " -> fi#" << Virt2StackSlotMap[i] << "]\n";
113 void VirtRegMap::dump() const { print(std::cerr); }
116 //===----------------------------------------------------------------------===//
117 // Simple Spiller Implementation
118 //===----------------------------------------------------------------------===//
120 Spiller::~Spiller() {}
123 struct SimpleSpiller : public Spiller {
124 bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap &VRM);
128 bool SimpleSpiller::runOnMachineFunction(MachineFunction& MF,
129 const VirtRegMap& VRM) {
130 DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
131 DEBUG(std::cerr << "********** Function: "
132 << MF.getFunction()->getName() << '\n');
133 const TargetMachine& TM = MF.getTarget();
134 const MRegisterInfo& MRI = *TM.getRegisterInfo();
136 // LoadedRegs - Keep track of which vregs are loaded, so that we only load
137 // each vreg once (in the case where a spilled vreg is used by multiple
138 // operands). This is always smaller than the number of operands to the
139 // current machine instr, so it should be small.
140 std::vector<unsigned> LoadedRegs;
142 for (MachineFunction::iterator mbbi = MF.begin(), E = MF.end();
144 DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n");
145 for (MachineBasicBlock::iterator mii = mbbi->begin(),
146 mie = mbbi->end(); mii != mie; ++mii) {
147 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
148 MachineOperand& mop = mii->getOperand(i);
149 if (mop.isRegister() && mop.getReg() &&
150 MRegisterInfo::isVirtualRegister(mop.getReg())) {
151 unsigned virtReg = mop.getReg();
152 unsigned physReg = VRM.getPhys(virtReg);
153 if (mop.isUse() && VRM.hasStackSlot(mop.getReg()) &&
154 std::find(LoadedRegs.begin(), LoadedRegs.end(),
155 virtReg) == LoadedRegs.end()) {
156 MRI.loadRegFromStackSlot(*mbbi, mii, physReg,
157 VRM.getStackSlot(virtReg));
158 LoadedRegs.push_back(virtReg);
159 DEBUG(std::cerr << '\t';
160 prior(mii)->print(std::cerr, &TM));
164 if (mop.isDef() && VRM.hasStackSlot(mop.getReg())) {
165 MRI.storeRegToStackSlot(*mbbi, next(mii), physReg,
166 VRM.getStackSlot(virtReg));
169 mii->SetMachineOperandReg(i, physReg);
172 DEBUG(std::cerr << '\t'; mii->print(std::cerr, &TM));
179 //===----------------------------------------------------------------------===//
180 // Local Spiller Implementation
181 //===----------------------------------------------------------------------===//
184 class LocalSpiller : public Spiller {
185 typedef std::vector<unsigned> Phys2VirtMap;
186 typedef std::vector<bool> PhysFlag;
187 typedef DenseMap<MachineInstr*, VirtReg2IndexFunctor> Virt2MI;
190 const TargetMachine *TM;
191 const TargetInstrInfo *TII;
192 const MRegisterInfo *MRI;
193 const VirtRegMap *VRM;
194 Phys2VirtMap p2vMap_;
199 bool runOnMachineFunction(MachineFunction &MF, const VirtRegMap &VRM);
202 void vacateJustPhysReg(MachineBasicBlock& mbb,
203 MachineBasicBlock::iterator mii,
206 void vacatePhysReg(MachineBasicBlock& mbb,
207 MachineBasicBlock::iterator mii,
209 vacateJustPhysReg(mbb, mii, physReg);
210 for (const unsigned* as = MRI->getAliasSet(physReg); *as; ++as)
211 vacateJustPhysReg(mbb, mii, *as);
214 void handleUse(MachineBasicBlock& mbb,
215 MachineBasicBlock::iterator mii,
218 // check if we are replacing a previous mapping
219 if (p2vMap_[physReg] != virtReg) {
220 vacatePhysReg(mbb, mii, physReg);
221 p2vMap_[physReg] = virtReg;
223 if (VRM->hasStackSlot(virtReg)) {
224 MRI->loadRegFromStackSlot(mbb, mii, physReg,
225 VRM->getStackSlot(virtReg));
227 DEBUG(std::cerr << "added: ";
228 prior(mii)->print(std::cerr, TM));
229 lastDef_[virtReg] = mii;
234 void handleDef(MachineBasicBlock& mbb,
235 MachineBasicBlock::iterator mii,
238 // check if we are replacing a previous mapping
239 if (p2vMap_[physReg] != virtReg)
240 vacatePhysReg(mbb, mii, physReg);
242 p2vMap_[physReg] = virtReg;
243 dirty_[physReg] = true;
244 lastDef_[virtReg] = mii;
247 void eliminateVirtRegsInMbb(MachineBasicBlock& mbb);
251 bool LocalSpiller::runOnMachineFunction(MachineFunction &mf,
252 const VirtRegMap &vrm) {
254 TM = &MF->getTarget();
255 TII = TM->getInstrInfo();
256 MRI = TM->getRegisterInfo();
258 p2vMap_.assign(MRI->getNumRegs(), 0);
259 dirty_.assign(MRI->getNumRegs(), false);
261 DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
262 DEBUG(std::cerr << "********** Function: "
263 << MF->getFunction()->getName() << '\n');
265 for (MachineFunction::iterator mbbi = MF->begin(),
266 mbbe = MF->end(); mbbi != mbbe; ++mbbi) {
267 lastDef_.grow(MF->getSSARegMap()->getLastVirtReg());
268 DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n");
269 eliminateVirtRegsInMbb(*mbbi);
270 // clear map, dirty flag and last ref
271 p2vMap_.assign(p2vMap_.size(), 0);
272 dirty_.assign(dirty_.size(), false);
278 void LocalSpiller::vacateJustPhysReg(MachineBasicBlock& mbb,
279 MachineBasicBlock::iterator mii,
281 unsigned virtReg = p2vMap_[physReg];
282 if (dirty_[physReg] && VRM->hasStackSlot(virtReg)) {
283 assert(lastDef_[virtReg] && "virtual register is mapped "
284 "to a register and but was not defined!");
285 MachineBasicBlock::iterator lastDef = lastDef_[virtReg];
286 MachineBasicBlock::iterator nextLastRef = next(lastDef);
287 MRI->storeRegToStackSlot(*lastDef->getParent(),
290 VRM->getStackSlot(virtReg));
292 DEBUG(std::cerr << "added: ";
293 prior(nextLastRef)->print(std::cerr, TM);
294 std::cerr << "after: ";
295 lastDef->print(std::cerr, TM));
296 lastDef_[virtReg] = 0;
298 p2vMap_[physReg] = 0;
299 dirty_[physReg] = false;
302 void LocalSpiller::eliminateVirtRegsInMbb(MachineBasicBlock &MBB) {
303 for (MachineBasicBlock::iterator MI = MBB.begin(), E = MBB.end();
306 // if we have references to memory operands make sure
307 // we clear all physical registers that may contain
308 // the value of the spilled virtual register
309 VirtRegMap::MI2VirtMapTy::const_iterator i, e;
310 for (tie(i, e) = VRM->getFoldedVirts(MI); i != e; ++i) {
311 if (VRM->hasPhys(i->second))
312 vacateJustPhysReg(MBB, MI, VRM->getPhys(i->second));
315 // rewrite all used operands
316 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
317 MachineOperand& op = MI->getOperand(i);
318 if (op.isRegister() && op.getReg() && op.isUse() &&
319 MRegisterInfo::isVirtualRegister(op.getReg())) {
320 unsigned virtReg = op.getReg();
321 unsigned physReg = VRM->getPhys(virtReg);
322 handleUse(MBB, MI, virtReg, physReg);
323 MI->SetMachineOperandReg(i, physReg);
324 // mark as dirty if this is def&use
326 dirty_[physReg] = true;
327 lastDef_[virtReg] = MI;
332 // spill implicit physical register defs
333 const TargetInstrDescriptor& tid = TII->get(MI->getOpcode());
334 for (const unsigned* id = tid.ImplicitDefs; *id; ++id)
335 vacatePhysReg(MBB, MI, *id);
337 // spill explicit physical register defs
338 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
339 MachineOperand& op = MI->getOperand(i);
340 if (op.isRegister() && op.getReg() && !op.isUse() &&
341 MRegisterInfo::isPhysicalRegister(op.getReg()))
342 vacatePhysReg(MBB, MI, op.getReg());
345 // rewrite def operands (def&use was handled with the
346 // uses so don't check for those here)
347 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
348 MachineOperand& op = MI->getOperand(i);
349 if (op.isRegister() && op.getReg() && !op.isUse())
350 if (MRegisterInfo::isPhysicalRegister(op.getReg()))
351 vacatePhysReg(MBB, MI, op.getReg());
353 unsigned physReg = VRM->getPhys(op.getReg());
354 handleDef(MBB, MI, op.getReg(), physReg);
355 MI->SetMachineOperandReg(i, physReg);
359 DEBUG(std::cerr << '\t'; MI->print(std::cerr, TM));
362 for (unsigned i = 1, e = p2vMap_.size(); i != e; ++i)
363 vacateJustPhysReg(MBB, MBB.getFirstTerminator(), i);
367 llvm::Spiller* llvm::createSpiller() {
368 switch (SpillerOpt) {
369 default: assert(0 && "Unreachable!");
371 return new LocalSpiller();
373 return new SimpleSpiller();