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