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/STLExtras.h"
32 Statistic<> numSpills("spiller", "Number of register spills");
33 Statistic<> numStores("spiller", "Number of stores added");
34 Statistic<> numLoads ("spiller", "Number of loads added");
38 int VirtRegMap::assignVirt2StackSlot(unsigned virtReg)
40 assert(MRegisterInfo::isVirtualRegister(virtReg));
41 assert(v2ssMap_[virtReg] == NO_STACK_SLOT &&
42 "attempt to assign stack slot to already spilled register");
43 const TargetRegisterClass* rc =
44 mf_->getSSARegMap()->getRegClass(virtReg);
45 int frameIndex = mf_->getFrameInfo()->CreateStackObject(rc);
46 v2ssMap_[virtReg] = frameIndex;
51 std::ostream& llvm::operator<<(std::ostream& os, const VirtRegMap& vrm)
53 const MRegisterInfo* mri = vrm.mf_->getTarget().getRegisterInfo();
55 std::cerr << "********** REGISTER MAP **********\n";
56 for (unsigned i = MRegisterInfo::FirstVirtualRegister,
57 e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
58 if (vrm.v2pMap_[i] != VirtRegMap::NO_PHYS_REG)
59 std::cerr << "[reg" << i << " -> "
60 << mri->getName(vrm.v2pMap_[i]) << "]\n";
62 for (unsigned i = MRegisterInfo::FirstVirtualRegister,
63 e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
64 if (vrm.v2ssMap_[i] != VirtRegMap::NO_STACK_SLOT)
65 std::cerr << "[reg" << i << " -> fi#"
66 << vrm.v2ssMap_[i] << "]\n";
68 return std::cerr << '\n';
74 typedef std::vector<unsigned> Phys2VirtMap;
75 typedef std::vector<bool> PhysFlag;
78 const TargetMachine& tm_;
79 const TargetInstrInfo& tii_;
80 const MRegisterInfo& mri_;
81 const VirtRegMap& vrm_;
86 Spiller(MachineFunction& mf, const VirtRegMap& vrm)
89 tii_(tm_.getInstrInfo()),
90 mri_(*tm_.getRegisterInfo()),
92 p2vMap_(mri_.getNumRegs()),
93 dirty_(mri_.getNumRegs()) {
94 DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
95 DEBUG(std::cerr << "********** Function: "
96 << mf_.getFunction()->getName() << '\n');
99 void eliminateVirtRegs() {
100 for (MachineFunction::iterator mbbi = mf_.begin(),
101 mbbe = mf_.end(); mbbi != mbbe; ++mbbi) {
102 // clear map and dirty flag
103 p2vMap_.assign(p2vMap_.size(), 0);
104 dirty_.assign(dirty_.size(), false);
105 DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n");
106 eliminateVirtRegsInMbb(*mbbi);
111 void vacateJustPhysReg(MachineBasicBlock& mbb,
112 MachineBasicBlock::iterator mii,
114 unsigned virtReg = p2vMap_[physReg];
115 if (dirty_[physReg] && vrm_.hasStackSlot(virtReg)) {
116 mri_.storeRegToStackSlot(mbb, mii, physReg,
117 vrm_.getStackSlot(virtReg),
118 mri_.getRegClass(physReg));
120 DEBUG(std::cerr << "*\t"; prior(mii)->print(std::cerr, tm_));
122 p2vMap_[physReg] = 0;
123 dirty_[physReg] = false;
126 void vacatePhysReg(MachineBasicBlock& mbb,
127 MachineBasicBlock::iterator mii,
129 vacateJustPhysReg(mbb, mii, physReg);
130 for (const unsigned* as = mri_.getAliasSet(physReg); *as; ++as)
131 vacateJustPhysReg(mbb, mii, *as);
134 void handleUse(MachineBasicBlock& mbb,
135 MachineBasicBlock::iterator mii,
138 // check if we are replacing a previous mapping
139 if (p2vMap_[physReg] != virtReg) {
140 vacatePhysReg(mbb, mii, physReg);
141 p2vMap_[physReg] = virtReg;
143 if (vrm_.hasStackSlot(virtReg)) {
144 mri_.loadRegFromStackSlot(mbb, mii, physReg,
145 vrm_.getStackSlot(virtReg),
146 mri_.getRegClass(physReg));
148 DEBUG(std::cerr << "*\t"; prior(mii)->print(std::cerr,tm_));
153 void handleDef(MachineBasicBlock& mbb,
154 MachineBasicBlock::iterator mii,
157 // check if we are replacing a previous mapping
158 if (p2vMap_[physReg] != virtReg)
159 vacatePhysReg(mbb, mii, physReg);
161 p2vMap_[physReg] = virtReg;
162 dirty_[physReg] = true;
165 void eliminateVirtRegsInMbb(MachineBasicBlock& mbb) {
166 for (MachineBasicBlock::iterator mii = mbb.begin(),
167 mie = mbb.end(); mii != mie; ++mii) {
168 // rewrite all used operands
169 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
170 MachineOperand& op = mii->getOperand(i);
171 if (op.isRegister() && op.isUse() &&
172 MRegisterInfo::isVirtualRegister(op.getReg())) {
173 unsigned physReg = vrm_.getPhys(op.getReg());
174 handleUse(mbb, mii, op.getReg(), physReg);
175 mii->SetMachineOperandReg(i, physReg);
176 // mark as dirty if this is def&use
177 if (op.isDef()) dirty_[physReg] = true;
181 // spill implicit defs
182 const TargetInstrDescriptor& tid =tii_.get(mii->getOpcode());
183 for (const unsigned* id = tid.ImplicitDefs; *id; ++id)
184 vacatePhysReg(mbb, mii, *id);
186 // rewrite def operands (def&use was handled with the
187 // uses so don't check for those here)
188 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
189 MachineOperand& op = mii->getOperand(i);
190 if (op.isRegister() && !op.isUse())
191 if (MRegisterInfo::isPhysicalRegister(op.getReg()))
192 vacatePhysReg(mbb, mii, op.getReg());
194 unsigned physReg = vrm_.getPhys(op.getReg());
195 handleDef(mbb, mii, op.getReg(), physReg);
196 mii->SetMachineOperandReg(i, physReg);
200 DEBUG(std::cerr << '\t'; mii->print(std::cerr, tm_));
203 for (unsigned i = 1, e = p2vMap_.size(); i != e; ++i)
204 vacateJustPhysReg(mbb, mbb.getFirstTerminator(), i);
211 void llvm::eliminateVirtRegs(MachineFunction& mf, const VirtRegMap& vrm)
213 Spiller(mf, vrm).eliminateVirtRegs();