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/Target/TargetMachine.h"
23 #include "llvm/Target/TargetInstrInfo.h"
24 #include "Support/Statistic.h"
25 #include "Support/Debug.h"
26 #include "Support/DenseMap.h"
27 #include "Support/STLExtras.h"
33 Statistic<> numSpills("spiller", "Number of register spills");
34 Statistic<> numStores("spiller", "Number of stores added");
35 Statistic<> numLoads ("spiller", "Number of loads added");
39 int VirtRegMap::assignVirt2StackSlot(unsigned virtReg)
41 assert(MRegisterInfo::isVirtualRegister(virtReg));
42 assert(v2ssMap_[virtReg] == NO_STACK_SLOT &&
43 "attempt to assign stack slot to already spilled register");
44 const TargetRegisterClass* rc =
45 mf_->getSSARegMap()->getRegClass(virtReg);
46 int frameIndex = mf_->getFrameInfo()->CreateStackObject(rc);
47 v2ssMap_[virtReg] = frameIndex;
52 std::ostream& llvm::operator<<(std::ostream& os, const VirtRegMap& vrm)
54 const MRegisterInfo* mri = vrm.mf_->getTarget().getRegisterInfo();
56 std::cerr << "********** REGISTER MAP **********\n";
57 for (unsigned i = MRegisterInfo::FirstVirtualRegister,
58 e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
59 if (vrm.v2pMap_[i] != VirtRegMap::NO_PHYS_REG)
60 std::cerr << "[reg" << i << " -> "
61 << mri->getName(vrm.v2pMap_[i]) << "]\n";
63 for (unsigned i = MRegisterInfo::FirstVirtualRegister,
64 e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
65 if (vrm.v2ssMap_[i] != VirtRegMap::NO_STACK_SLOT)
66 std::cerr << "[reg" << i << " -> fi#"
67 << vrm.v2ssMap_[i] << "]\n";
69 return std::cerr << '\n';
75 typedef std::vector<unsigned> Phys2VirtMap;
76 typedef std::vector<bool> PhysFlag;
77 typedef DenseMap<MachineInstr*, VirtReg2IndexFunctor> Virt2MI;
80 const TargetMachine& tm_;
81 const TargetInstrInfo& tii_;
82 const MRegisterInfo& mri_;
83 const VirtRegMap& vrm_;
89 Spiller(MachineFunction& mf, const VirtRegMap& vrm)
92 tii_(tm_.getInstrInfo()),
93 mri_(*tm_.getRegisterInfo()),
95 p2vMap_(mri_.getNumRegs(), 0),
96 dirty_(mri_.getNumRegs(), false),
98 DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
99 DEBUG(std::cerr << "********** Function: "
100 << mf_.getFunction()->getName() << '\n');
103 void eliminateVirtRegs() {
104 for (MachineFunction::iterator mbbi = mf_.begin(),
105 mbbe = mf_.end(); mbbi != mbbe; ++mbbi) {
106 lastDef_.grow(mf_.getSSARegMap()->getLastVirtReg());
107 DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n");
108 eliminateVirtRegsInMbb(*mbbi);
109 // clear map, dirty flag and last ref
110 p2vMap_.assign(p2vMap_.size(), 0);
111 dirty_.assign(dirty_.size(), false);
117 void vacateJustPhysReg(MachineBasicBlock& mbb,
118 MachineBasicBlock::iterator mii,
120 unsigned virtReg = p2vMap_[physReg];
121 if (dirty_[physReg] && vrm_.hasStackSlot(virtReg)) {
122 assert(lastDef_[virtReg] && "virtual register is mapped "
123 "to a register and but was not defined!");
124 MachineBasicBlock::iterator lastDef = lastDef_[virtReg];
125 MachineBasicBlock::iterator nextLastRef = next(lastDef);
126 mri_.storeRegToStackSlot(*lastDef->getParent(),
129 vrm_.getStackSlot(virtReg),
130 mri_.getRegClass(physReg));
132 DEBUG(std::cerr << "\t\tadded: ";
133 prior(nextLastRef)->print(std::cerr, tm_);
134 std::cerr << "\t\tafter: ";
135 lastDef->print(std::cerr, tm_));
136 lastDef_[virtReg] = 0;
138 p2vMap_[physReg] = 0;
139 dirty_[physReg] = false;
142 void vacatePhysReg(MachineBasicBlock& mbb,
143 MachineBasicBlock::iterator mii,
145 vacateJustPhysReg(mbb, mii, physReg);
146 for (const unsigned* as = mri_.getAliasSet(physReg); *as; ++as)
147 vacateJustPhysReg(mbb, mii, *as);
150 void handleUse(MachineBasicBlock& mbb,
151 MachineBasicBlock::iterator mii,
154 // check if we are replacing a previous mapping
155 if (p2vMap_[physReg] != virtReg) {
156 vacatePhysReg(mbb, mii, physReg);
157 p2vMap_[physReg] = virtReg;
159 if (vrm_.hasStackSlot(virtReg)) {
160 mri_.loadRegFromStackSlot(mbb, mii, physReg,
161 vrm_.getStackSlot(virtReg),
162 mri_.getRegClass(physReg));
164 DEBUG(std::cerr << "\t\tadded: ";
165 prior(mii)->print(std::cerr,tm_);
166 std::cerr << "\t\tbefore: ";
167 mii->print(std::cerr, tm_));
168 lastDef_[virtReg] = mii;
173 void handleDef(MachineBasicBlock& mbb,
174 MachineBasicBlock::iterator mii,
177 // check if we are replacing a previous mapping
178 if (p2vMap_[physReg] != virtReg)
179 vacatePhysReg(mbb, mii, physReg);
181 p2vMap_[physReg] = virtReg;
182 dirty_[physReg] = true;
183 lastDef_[virtReg] = mii;
186 void eliminateVirtRegsInMbb(MachineBasicBlock& mbb) {
187 for (MachineBasicBlock::iterator mii = mbb.begin(),
188 mie = mbb.end(); mii != mie; ++mii) {
189 // rewrite all used operands
190 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
191 MachineOperand& op = mii->getOperand(i);
192 if (op.isRegister() && op.getReg() && op.isUse() &&
193 MRegisterInfo::isVirtualRegister(op.getReg())) {
194 unsigned virtReg = op.getReg();
195 unsigned physReg = vrm_.getPhys(virtReg);
196 handleUse(mbb, mii, virtReg, physReg);
197 mii->SetMachineOperandReg(i, physReg);
198 // mark as dirty if this is def&use
200 dirty_[physReg] = true;
201 lastDef_[virtReg] = mii;
206 // spill implicit defs
207 const TargetInstrDescriptor& tid =tii_.get(mii->getOpcode());
208 for (const unsigned* id = tid.ImplicitDefs; *id; ++id)
209 vacatePhysReg(mbb, mii, *id);
211 // rewrite def operands (def&use was handled with the
212 // uses so don't check for those here)
213 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
214 MachineOperand& op = mii->getOperand(i);
215 if (op.isRegister() && op.getReg() && !op.isUse())
216 if (MRegisterInfo::isPhysicalRegister(op.getReg()))
217 vacatePhysReg(mbb, mii, op.getReg());
219 unsigned physReg = vrm_.getPhys(op.getReg());
220 handleDef(mbb, mii, op.getReg(), physReg);
221 mii->SetMachineOperandReg(i, physReg);
225 DEBUG(std::cerr << '\t'; mii->print(std::cerr, tm_));
228 for (unsigned i = 1, e = p2vMap_.size(); i != e; ++i)
229 vacateJustPhysReg(mbb, mbb.getFirstTerminator(), i);
236 void llvm::eliminateVirtRegs(MachineFunction& mf, const VirtRegMap& vrm)
238 Spiller(mf, vrm).eliminateVirtRegs();