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