VirtRegMap.cpp revision 5f37502bfbadfa65de087627bd67fd58bb03725c 
1//===-- llvm/CodeGen/VirtRegMap.cpp - Virtual Register Map ----------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
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.
7//
8//===----------------------------------------------------------------------===//
9//
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
14// code as necessary.
15//
16//===----------------------------------------------------------------------===//
17
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/Statistic.h"
26#include "Support/Debug.h"
27#include "Support/DenseMap.h"
28#include "Support/STLExtras.h"
29#include <iostream>
30
31using namespace llvm;
32
33namespace {
34    Statistic<> numSpills("spiller", "Number of register spills");
35    Statistic<> numStores("spiller", "Number of stores added");
36    Statistic<> numLoads ("spiller", "Number of loads added");
37
38}
39
40int VirtRegMap::assignVirt2StackSlot(unsigned virtReg)
41{
42    assert(MRegisterInfo::isVirtualRegister(virtReg));
43    assert(v2ssMap_[virtReg] == NO_STACK_SLOT &&
44           "attempt to assign stack slot to already spilled register");
45    const TargetRegisterClass* rc =
46        mf_->getSSARegMap()->getRegClass(virtReg);
47    int frameIndex = mf_->getFrameInfo()->CreateStackObject(rc);
48    v2ssMap_[virtReg] = frameIndex;
49    ++numSpills;
50    return frameIndex;
51}
52
53void VirtRegMap::virtFolded(unsigned virtReg,
54                            MachineInstr* oldMI,
55                            MachineInstr* newMI)
56{
57    // move previous memory references folded to new instruction
58    MI2VirtMap::iterator i, e;
59    std::vector<MI2VirtMap::mapped_type> regs;
60    for (tie(i, e) = mi2vMap_.equal_range(oldMI); i != e; ) {
61        regs.push_back(i->second);
62        mi2vMap_.erase(i++);
63    }
64    for (unsigned i = 0, e = regs.size(); i != e; ++i)
65        mi2vMap_.insert(std::make_pair(newMI, i));
66
67    // add new memory reference
68    mi2vMap_.insert(std::make_pair(newMI, virtReg));
69}
70
71std::ostream& llvm::operator<<(std::ostream& os, const VirtRegMap& vrm)
72{
73    const MRegisterInfo* mri = vrm.mf_->getTarget().getRegisterInfo();
74
75    std::cerr << "********** REGISTER MAP **********\n";
76    for (unsigned i = MRegisterInfo::FirstVirtualRegister,
77             e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
78        if (vrm.v2pMap_[i] != VirtRegMap::NO_PHYS_REG)
79            std::cerr << "[reg" << i << " -> "
80                      << mri->getName(vrm.v2pMap_[i]) << "]\n";
81    }
82    for (unsigned i = MRegisterInfo::FirstVirtualRegister,
83             e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
84        if (vrm.v2ssMap_[i] != VirtRegMap::NO_STACK_SLOT)
85            std::cerr << "[reg" << i << " -> fi#"
86                      << vrm.v2ssMap_[i] << "]\n";
87    }
88    return std::cerr << '\n';
89}
90
91namespace {
92
93    class Spiller {
94        typedef std::vector<unsigned> Phys2VirtMap;
95        typedef std::vector<bool> PhysFlag;
96        typedef DenseMap<MachineInstr*, VirtReg2IndexFunctor> Virt2MI;
97
98        MachineFunction& mf_;
99        const TargetMachine& tm_;
100        const TargetInstrInfo& tii_;
101        const MRegisterInfo& mri_;
102        const VirtRegMap& vrm_;
103        Phys2VirtMap p2vMap_;
104        PhysFlag dirty_;
105        Virt2MI lastDef_;
106
107    public:
108        Spiller(MachineFunction& mf, const VirtRegMap& vrm)
109            : mf_(mf),
110              tm_(mf_.getTarget()),
111              tii_(tm_.getInstrInfo()),
112              mri_(*tm_.getRegisterInfo()),
113              vrm_(vrm),
114              p2vMap_(mri_.getNumRegs(), 0),
115              dirty_(mri_.getNumRegs(), false),
116              lastDef_() {
117            DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
118            DEBUG(std::cerr << "********** Function: "
119                  << mf_.getFunction()->getName() << '\n');
120        }
121
122        void eliminateVirtRegs() {
123            for (MachineFunction::iterator mbbi = mf_.begin(),
124                     mbbe = mf_.end(); mbbi != mbbe; ++mbbi) {
125                lastDef_.grow(mf_.getSSARegMap()->getLastVirtReg());
126                DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n");
127                eliminateVirtRegsInMbb(*mbbi);
128                // clear map, dirty flag and last ref
129                p2vMap_.assign(p2vMap_.size(), 0);
130                dirty_.assign(dirty_.size(), false);
131                lastDef_.clear();
132            }
133        }
134
135    private:
136        void vacateJustPhysReg(MachineBasicBlock& mbb,
137                               MachineBasicBlock::iterator mii,
138                               unsigned physReg) {
139            unsigned virtReg = p2vMap_[physReg];
140            if (dirty_[physReg] && vrm_.hasStackSlot(virtReg)) {
141                assert(lastDef_[virtReg] && "virtual register is mapped "
142                       "to a register and but was not defined!");
143                MachineBasicBlock::iterator lastDef = lastDef_[virtReg];
144                MachineBasicBlock::iterator nextLastRef = next(lastDef);
145                mri_.storeRegToStackSlot(*lastDef->getParent(),
146                                         nextLastRef,
147                                         physReg,
148                                         vrm_.getStackSlot(virtReg),
149                                         mri_.getRegClass(physReg));
150                ++numStores;
151                DEBUG(std::cerr << "added: ";
152                      prior(nextLastRef)->print(std::cerr, tm_);
153                      std::cerr << "after: ";
154                      lastDef->print(std::cerr, tm_));
155                lastDef_[virtReg] = 0;
156            }
157            p2vMap_[physReg] = 0;
158            dirty_[physReg] = false;
159        }
160
161        void vacatePhysReg(MachineBasicBlock& mbb,
162                           MachineBasicBlock::iterator mii,
163                           unsigned physReg) {
164            vacateJustPhysReg(mbb, mii, physReg);
165            for (const unsigned* as = mri_.getAliasSet(physReg); *as; ++as)
166                vacateJustPhysReg(mbb, mii, *as);
167        }
168
169        void handleUse(MachineBasicBlock& mbb,
170                       MachineBasicBlock::iterator mii,
171                       unsigned virtReg,
172                       unsigned physReg) {
173            // check if we are replacing a previous mapping
174            if (p2vMap_[physReg] != virtReg) {
175                vacatePhysReg(mbb, mii, physReg);
176                p2vMap_[physReg] = virtReg;
177                // load if necessary
178                if (vrm_.hasStackSlot(virtReg)) {
179                    mri_.loadRegFromStackSlot(mbb, mii, physReg,
180                                              vrm_.getStackSlot(virtReg),
181                                              mri_.getRegClass(physReg));
182                    ++numLoads;
183                    DEBUG(std::cerr << "added: ";
184                          prior(mii)->print(std::cerr,tm_));
185                    lastDef_[virtReg] = mii;
186                }
187            }
188        }
189
190        void handleDef(MachineBasicBlock& mbb,
191                       MachineBasicBlock::iterator mii,
192                       unsigned virtReg,
193                       unsigned physReg) {
194            // check if we are replacing a previous mapping
195            if (p2vMap_[physReg] != virtReg)
196                vacatePhysReg(mbb, mii, physReg);
197
198            p2vMap_[physReg] = virtReg;
199            dirty_[physReg] = true;
200            lastDef_[virtReg] = mii;
201        }
202
203        void eliminateVirtRegsInMbb(MachineBasicBlock& mbb) {
204            for (MachineBasicBlock::iterator mii = mbb.begin(),
205                     mie = mbb.end(); mii != mie; ++mii) {
206
207                // if we have references to memory operands make sure
208                // we clear all physical registers that may contain
209                // the value of the spilled virtual register
210                VirtRegMap::MI2VirtMap::const_iterator i, e;
211                for (tie(i, e) = vrm_.getFoldedVirts(mii); i != e; ++i) {
212                    unsigned physReg = vrm_.getPhys(i->second);
213                    if (physReg) vacateJustPhysReg(mbb, mii, physReg);
214                }
215
216                // rewrite all used operands
217                for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
218                    MachineOperand& op = mii->getOperand(i);
219                    if (op.isRegister() && op.getReg() && op.isUse() &&
220                        MRegisterInfo::isVirtualRegister(op.getReg())) {
221                        unsigned virtReg = op.getReg();
222                        unsigned physReg = vrm_.getPhys(virtReg);
223                        handleUse(mbb, mii, virtReg, physReg);
224                        mii->SetMachineOperandReg(i, physReg);
225                        // mark as dirty if this is def&use
226                        if (op.isDef()) {
227                            dirty_[physReg] = true;
228                            lastDef_[virtReg] = mii;
229                        }
230                    }
231                }
232
233                // spill implicit defs
234                const TargetInstrDescriptor& tid =tii_.get(mii->getOpcode());
235                for (const unsigned* id = tid.ImplicitDefs; *id; ++id)
236                    vacatePhysReg(mbb, mii, *id);
237
238                // rewrite def operands (def&use was handled with the
239                // uses so don't check for those here)
240                for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
241                    MachineOperand& op = mii->getOperand(i);
242                    if (op.isRegister() && op.getReg() && !op.isUse())
243                        if (MRegisterInfo::isPhysicalRegister(op.getReg()))
244                            vacatePhysReg(mbb, mii, op.getReg());
245                        else {
246                            unsigned physReg = vrm_.getPhys(op.getReg());
247                            handleDef(mbb, mii, op.getReg(), physReg);
248                            mii->SetMachineOperandReg(i, physReg);
249                        }
250                }
251
252                DEBUG(std::cerr << '\t'; mii->print(std::cerr, tm_));
253            }
254
255            for (unsigned i = 1, e = p2vMap_.size(); i != e; ++i)
256                vacateJustPhysReg(mbb, mbb.getFirstTerminator(), i);
257
258        }
259    };
260}
261
262
263void llvm::eliminateVirtRegs(MachineFunction& mf, const VirtRegMap& vrm)
264{
265    Spiller(mf, vrm).eliminateVirtRegs();
266}
267