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