VirtRegMap.cpp revision 57f1b67c347b9ba1f8a1cdc3a55362d4f2aa8653 
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/CommandLine.h"
26#include "Support/Debug.h"
27#include "Support/DenseMap.h"
28#include "Support/Statistic.h"
29#include "Support/STLExtras.h"
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    enum SpillerName { simple, local };
39
40    cl::opt<SpillerName>
41    SpillerOpt("spiller",
42               cl::desc("Spiller to use: (default: local)"),
43               cl::Prefix,
44               cl::values(clEnumVal(simple, "  simple spiller"),
45                          clEnumVal(local,  "  local spiller"),
46                          clEnumValEnd),
47               cl::init(local));
48}
49
50int VirtRegMap::assignVirt2StackSlot(unsigned virtReg)
51{
52    assert(MRegisterInfo::isVirtualRegister(virtReg));
53    assert(v2ssMap_[virtReg] == NO_STACK_SLOT &&
54           "attempt to assign stack slot to already spilled register");
55    const TargetRegisterClass* rc =
56        mf_->getSSARegMap()->getRegClass(virtReg);
57    int frameIndex = mf_->getFrameInfo()->CreateStackObject(rc);
58    v2ssMap_[virtReg] = frameIndex;
59    ++numSpills;
60    return frameIndex;
61}
62
63void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int frameIndex)
64{
65    assert(MRegisterInfo::isVirtualRegister(virtReg));
66    assert(v2ssMap_[virtReg] == NO_STACK_SLOT &&
67           "attempt to assign stack slot to already spilled register");
68     v2ssMap_[virtReg] = frameIndex;
69}
70
71void VirtRegMap::virtFolded(unsigned virtReg,
72                            MachineInstr* oldMI,
73                            MachineInstr* newMI)
74{
75    // move previous memory references folded to new instruction
76    MI2VirtMap::iterator i, e;
77    std::vector<MI2VirtMap::mapped_type> regs;
78    for (tie(i, e) = mi2vMap_.equal_range(oldMI); i != e; ) {
79        regs.push_back(i->second);
80        mi2vMap_.erase(i++);
81    }
82    for (unsigned i = 0, e = regs.size(); i != e; ++i)
83        mi2vMap_.insert(std::make_pair(newMI, i));
84
85    // add new memory reference
86    mi2vMap_.insert(std::make_pair(newMI, virtReg));
87}
88
89std::ostream& llvm::operator<<(std::ostream& os, const VirtRegMap& vrm)
90{
91    const MRegisterInfo* mri = vrm.mf_->getTarget().getRegisterInfo();
92
93    std::cerr << "********** REGISTER MAP **********\n";
94    for (unsigned i = MRegisterInfo::FirstVirtualRegister,
95             e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
96        if (vrm.v2pMap_[i] != VirtRegMap::NO_PHYS_REG)
97            std::cerr << "[reg" << i << " -> "
98                      << mri->getName(vrm.v2pMap_[i]) << "]\n";
99    }
100    for (unsigned i = MRegisterInfo::FirstVirtualRegister,
101             e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
102        if (vrm.v2ssMap_[i] != VirtRegMap::NO_STACK_SLOT)
103            std::cerr << "[reg" << i << " -> fi#"
104                      << vrm.v2ssMap_[i] << "]\n";
105    }
106    return std::cerr << '\n';
107}
108
109Spiller::~Spiller()
110{
111
112}
113
114namespace {
115
116    class SimpleSpiller : public Spiller {
117    public:
118        bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap& vrm) {
119            DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
120            DEBUG(std::cerr << "********** Function: "
121              << mf.getFunction()->getName() << '\n');
122            const TargetMachine& tm = mf.getTarget();
123            const MRegisterInfo& mri = *tm.getRegisterInfo();
124
125            typedef DenseMap<bool, VirtReg2IndexFunctor> Loaded;
126            Loaded loaded;
127
128            for (MachineFunction::iterator mbbi = mf.begin(),
129                     mbbe = mf.end(); mbbi != mbbe; ++mbbi) {
130                DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n");
131                for (MachineBasicBlock::iterator mii = mbbi->begin(),
132                         mie = mbbi->end(); mii != mie; ++mii) {
133                    loaded.grow(mf.getSSARegMap()->getLastVirtReg());
134                    for (unsigned i = 0,e = mii->getNumOperands(); i != e; ++i){
135                        MachineOperand& mop = mii->getOperand(i);
136                        if (mop.isRegister() && mop.getReg() &&
137                            MRegisterInfo::isVirtualRegister(mop.getReg())) {
138                            unsigned virtReg = mop.getReg();
139                            unsigned physReg = vrm.getPhys(virtReg);
140                            if (mop.isUse() &&
141                                vrm.hasStackSlot(mop.getReg()) &&
142                                !loaded[virtReg]) {
143                                mri.loadRegFromStackSlot(
144                                    *mbbi,
145                                    mii,
146                                    physReg,
147                                    vrm.getStackSlot(virtReg));
148                                loaded[virtReg] = true;
149                                DEBUG(std::cerr << '\t';
150                                      prior(mii)->print(std::cerr, &tm));
151                                ++numLoads;
152                            }
153                            if (mop.isDef() &&
154                                vrm.hasStackSlot(mop.getReg())) {
155                                mri.storeRegToStackSlot(
156                                    *mbbi,
157                                    next(mii),
158                                    physReg,
159                                    vrm.getStackSlot(virtReg));
160                                ++numStores;
161                            }
162                            mii->SetMachineOperandReg(i, physReg);
163                        }
164                    }
165                    DEBUG(std::cerr << '\t'; mii->print(std::cerr, &tm));
166                    loaded.clear();
167                }
168            }
169            return true;
170        }
171    };
172
173    class LocalSpiller : public Spiller {
174        typedef std::vector<unsigned> Phys2VirtMap;
175        typedef std::vector<bool> PhysFlag;
176        typedef DenseMap<MachineInstr*, VirtReg2IndexFunctor> Virt2MI;
177
178        MachineFunction* mf_;
179        const TargetMachine* tm_;
180        const TargetInstrInfo* tii_;
181        const MRegisterInfo* mri_;
182        const VirtRegMap* vrm_;
183        Phys2VirtMap p2vMap_;
184        PhysFlag dirty_;
185        Virt2MI lastDef_;
186
187    public:
188        bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap& vrm) {
189            mf_ = &mf;
190            tm_ = &mf_->getTarget();
191            tii_ = tm_->getInstrInfo();
192            mri_ = tm_->getRegisterInfo();
193            vrm_ = &vrm;
194            p2vMap_.assign(mri_->getNumRegs(), 0);
195            dirty_.assign(mri_->getNumRegs(), false);
196
197            DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
198            DEBUG(std::cerr << "********** Function: "
199                  << mf_->getFunction()->getName() << '\n');
200
201            for (MachineFunction::iterator mbbi = mf_->begin(),
202                     mbbe = mf_->end(); mbbi != mbbe; ++mbbi) {
203                lastDef_.grow(mf_->getSSARegMap()->getLastVirtReg());
204                DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n");
205                eliminateVirtRegsInMbb(*mbbi);
206                // clear map, dirty flag and last ref
207                p2vMap_.assign(p2vMap_.size(), 0);
208                dirty_.assign(dirty_.size(), false);
209                lastDef_.clear();
210            }
211            return true;
212        }
213
214    private:
215        void vacateJustPhysReg(MachineBasicBlock& mbb,
216                               MachineBasicBlock::iterator mii,
217                               unsigned physReg) {
218            unsigned virtReg = p2vMap_[physReg];
219            if (dirty_[physReg] && vrm_->hasStackSlot(virtReg)) {
220                assert(lastDef_[virtReg] && "virtual register is mapped "
221                       "to a register and but was not defined!");
222                MachineBasicBlock::iterator lastDef = lastDef_[virtReg];
223                MachineBasicBlock::iterator nextLastRef = next(lastDef);
224                mri_->storeRegToStackSlot(*lastDef->getParent(),
225                                          nextLastRef,
226                                          physReg,
227                                          vrm_->getStackSlot(virtReg));
228                ++numStores;
229                DEBUG(std::cerr << "added: ";
230                      prior(nextLastRef)->print(std::cerr, tm_);
231                      std::cerr << "after: ";
232                      lastDef->print(std::cerr, tm_));
233                lastDef_[virtReg] = 0;
234            }
235            p2vMap_[physReg] = 0;
236            dirty_[physReg] = false;
237        }
238
239        void vacatePhysReg(MachineBasicBlock& mbb,
240                           MachineBasicBlock::iterator mii,
241                           unsigned physReg) {
242            vacateJustPhysReg(mbb, mii, physReg);
243            for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as)
244                vacateJustPhysReg(mbb, mii, *as);
245        }
246
247        void handleUse(MachineBasicBlock& mbb,
248                       MachineBasicBlock::iterator mii,
249                       unsigned virtReg,
250                       unsigned physReg) {
251            // check if we are replacing a previous mapping
252            if (p2vMap_[physReg] != virtReg) {
253                vacatePhysReg(mbb, mii, physReg);
254                p2vMap_[physReg] = virtReg;
255                // load if necessary
256                if (vrm_->hasStackSlot(virtReg)) {
257                    mri_->loadRegFromStackSlot(mbb, mii, physReg,
258                                               vrm_->getStackSlot(virtReg));
259                    ++numLoads;
260                    DEBUG(std::cerr << "added: ";
261                          prior(mii)->print(std::cerr, tm_));
262                    lastDef_[virtReg] = mii;
263                }
264            }
265        }
266
267        void handleDef(MachineBasicBlock& mbb,
268                       MachineBasicBlock::iterator mii,
269                       unsigned virtReg,
270                       unsigned physReg) {
271            // check if we are replacing a previous mapping
272            if (p2vMap_[physReg] != virtReg)
273                vacatePhysReg(mbb, mii, physReg);
274
275            p2vMap_[physReg] = virtReg;
276            dirty_[physReg] = true;
277            lastDef_[virtReg] = mii;
278        }
279
280        void eliminateVirtRegsInMbb(MachineBasicBlock& mbb) {
281            for (MachineBasicBlock::iterator mii = mbb.begin(),
282                     mie = mbb.end(); mii != mie; ++mii) {
283
284                // if we have references to memory operands make sure
285                // we clear all physical registers that may contain
286                // the value of the spilled virtual register
287                VirtRegMap::MI2VirtMap::const_iterator i, e;
288                for (tie(i, e) = vrm_->getFoldedVirts(mii); i != e; ++i) {
289                    if (vrm_->hasPhys(i->second))
290                        vacateJustPhysReg(mbb, mii, vrm_->getPhys(i->second));
291                }
292
293                // rewrite all used operands
294                for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
295                    MachineOperand& op = mii->getOperand(i);
296                    if (op.isRegister() && op.getReg() && op.isUse() &&
297                        MRegisterInfo::isVirtualRegister(op.getReg())) {
298                        unsigned virtReg = op.getReg();
299                        unsigned physReg = vrm_->getPhys(virtReg);
300                        handleUse(mbb, mii, virtReg, physReg);
301                        mii->SetMachineOperandReg(i, physReg);
302                        // mark as dirty if this is def&use
303                        if (op.isDef()) {
304                            dirty_[physReg] = true;
305                            lastDef_[virtReg] = mii;
306                        }
307                    }
308                }
309
310                // spill implicit physical register defs
311                const TargetInstrDescriptor& tid = tii_->get(mii->getOpcode());
312                for (const unsigned* id = tid.ImplicitDefs; *id; ++id)
313                    vacatePhysReg(mbb, mii, *id);
314
315                // spill explicit physical register defs
316                for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
317                    MachineOperand& op = mii->getOperand(i);
318                    if (op.isRegister() && op.getReg() && !op.isUse() &&
319                        MRegisterInfo::isPhysicalRegister(op.getReg()))
320                        vacatePhysReg(mbb, mii, op.getReg());
321                }
322
323                // rewrite def operands (def&use was handled with the
324                // uses so don't check for those here)
325                for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
326                    MachineOperand& op = mii->getOperand(i);
327                    if (op.isRegister() && op.getReg() && !op.isUse())
328                        if (MRegisterInfo::isPhysicalRegister(op.getReg()))
329                            vacatePhysReg(mbb, mii, op.getReg());
330                        else {
331                            unsigned physReg = vrm_->getPhys(op.getReg());
332                            handleDef(mbb, mii, op.getReg(), physReg);
333                            mii->SetMachineOperandReg(i, physReg);
334                        }
335                }
336
337                DEBUG(std::cerr << '\t'; mii->print(std::cerr, tm_));
338            }
339
340            for (unsigned i = 1, e = p2vMap_.size(); i != e; ++i)
341                vacateJustPhysReg(mbb, mbb.getFirstTerminator(), i);
342
343        }
344    };
345}
346
347llvm::Spiller* llvm::createSpiller()
348{
349    switch (SpillerOpt) {
350    default:
351        std::cerr << "no spiller selected";
352        abort();
353    case local:
354        return new LocalSpiller();
355    case simple:
356        return new SimpleSpiller();
357    }
358}
359