VirtRegMap.cpp revision 8fa16e47f88975b577fe1cafce1a366b78b2c340 
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/Target/TargetMachine.h"
23#include "llvm/Target/TargetInstrInfo.h"
24#include "Support/Statistic.h"
25#include "Support/Debug.h"
26#include "Support/STLExtras.h"
27#include <iostream>
28
29using namespace llvm;
30
31namespace {
32    Statistic<> numSpills("spiller", "Number of register spills");
33    Statistic<> numStores("spiller", "Number of stores added");
34    Statistic<> numLoads ("spiller", "Number of loads added");
35
36}
37
38int VirtRegMap::assignVirt2StackSlot(unsigned virtReg)
39{
40    assert(MRegisterInfo::isVirtualRegister(virtReg));
41    assert(v2ssMap_[virtReg] == NO_STACK_SLOT &&
42           "attempt to assign stack slot to already spilled register");
43    const TargetRegisterClass* rc =
44        mf_->getSSARegMap()->getRegClass(virtReg);
45    int frameIndex = mf_->getFrameInfo()->CreateStackObject(rc);
46    v2ssMap_[virtReg] = frameIndex;
47    ++numSpills;
48    return frameIndex;
49}
50
51std::ostream& llvm::operator<<(std::ostream& os, const VirtRegMap& vrm)
52{
53    const MRegisterInfo* mri = vrm.mf_->getTarget().getRegisterInfo();
54
55    std::cerr << "********** REGISTER MAP **********\n";
56    for (unsigned i = MRegisterInfo::FirstVirtualRegister,
57             e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
58        if (vrm.v2pMap_[i] != VirtRegMap::NO_PHYS_REG)
59            std::cerr << "[reg" << i << " -> "
60                      << mri->getName(vrm.v2pMap_[i]) << "]\n";
61    }
62    for (unsigned i = MRegisterInfo::FirstVirtualRegister,
63             e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
64        if (vrm.v2ssMap_[i] != VirtRegMap::NO_STACK_SLOT)
65            std::cerr << "[reg" << i << " -> fi#"
66                      << vrm.v2ssMap_[i] << "]\n";
67    }
68    return std::cerr << '\n';
69}
70
71namespace {
72
73    class Spiller {
74        typedef std::vector<unsigned> Phys2VirtMap;
75        typedef std::vector<bool> PhysFlag;
76
77        MachineFunction& mf_;
78        const TargetMachine& tm_;
79        const TargetInstrInfo& tii_;
80        const MRegisterInfo& mri_;
81        const VirtRegMap& vrm_;
82        Phys2VirtMap p2vMap_;
83        PhysFlag dirty_;
84
85    public:
86        Spiller(MachineFunction& mf, const VirtRegMap& vrm)
87            : mf_(mf),
88              tm_(mf_.getTarget()),
89              tii_(tm_.getInstrInfo()),
90              mri_(*tm_.getRegisterInfo()),
91              vrm_(vrm),
92              p2vMap_(mri_.getNumRegs(), 0),
93              dirty_(mri_.getNumRegs(), false) {
94            DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
95            DEBUG(std::cerr << "********** Function: "
96                  << mf_.getFunction()->getName() << '\n');
97        }
98
99        void eliminateVirtRegs() {
100            for (MachineFunction::iterator mbbi = mf_.begin(),
101                     mbbe = mf_.end(); mbbi != mbbe; ++mbbi) {
102                DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n");
103                eliminateVirtRegsInMbb(*mbbi);
104                // clear map and dirty flag
105                p2vMap_.assign(p2vMap_.size(), 0);
106                dirty_.assign(dirty_.size(), false);
107            }
108        }
109
110    private:
111        void vacateJustPhysReg(MachineBasicBlock& mbb,
112                               MachineBasicBlock::iterator mii,
113                               unsigned physReg) {
114            unsigned virtReg = p2vMap_[physReg];
115            if (dirty_[physReg] && vrm_.hasStackSlot(virtReg)) {
116                mri_.storeRegToStackSlot(mbb, mii, physReg,
117                                         vrm_.getStackSlot(virtReg),
118                                         mri_.getRegClass(physReg));
119                ++numStores;
120                DEBUG(std::cerr << "*\t"; prior(mii)->print(std::cerr, tm_));
121            }
122            p2vMap_[physReg] = 0;
123            dirty_[physReg] = false;
124        }
125
126        void vacatePhysReg(MachineBasicBlock& mbb,
127                           MachineBasicBlock::iterator mii,
128                           unsigned physReg) {
129            vacateJustPhysReg(mbb, mii, physReg);
130            for (const unsigned* as = mri_.getAliasSet(physReg); *as; ++as)
131                vacateJustPhysReg(mbb, mii, *as);
132        }
133
134        void handleUse(MachineBasicBlock& mbb,
135                       MachineBasicBlock::iterator mii,
136                       unsigned virtReg,
137                       unsigned physReg) {
138            // check if we are replacing a previous mapping
139            if (p2vMap_[physReg] != virtReg) {
140                vacatePhysReg(mbb, mii, physReg);
141                p2vMap_[physReg] = virtReg;
142                // load if necessary
143                if (vrm_.hasStackSlot(virtReg)) {
144                    mri_.loadRegFromStackSlot(mbb, mii, physReg,
145                                              vrm_.getStackSlot(virtReg),
146                                              mri_.getRegClass(physReg));
147                    ++numLoads;
148                    DEBUG(std::cerr << "*\t"; prior(mii)->print(std::cerr,tm_));
149                }
150            }
151        }
152
153        void handleDef(MachineBasicBlock& mbb,
154                       MachineBasicBlock::iterator mii,
155                       unsigned virtReg,
156                       unsigned physReg) {
157            // check if we are replacing a previous mapping
158            if (p2vMap_[physReg] != virtReg)
159                vacatePhysReg(mbb, mii, physReg);
160
161            p2vMap_[physReg] = virtReg;
162            dirty_[physReg] = true;
163        }
164
165        void eliminateVirtRegsInMbb(MachineBasicBlock& mbb) {
166            for (MachineBasicBlock::iterator mii = mbb.begin(),
167                     mie = mbb.end(); mii != mie; ++mii) {
168                // rewrite all used operands
169                for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
170                    MachineOperand& op = mii->getOperand(i);
171                    if (op.isRegister() && op.getReg() && op.isUse() &&
172                        MRegisterInfo::isVirtualRegister(op.getReg())) {
173                        unsigned physReg = vrm_.getPhys(op.getReg());
174                        handleUse(mbb, mii, op.getReg(), physReg);
175                        mii->SetMachineOperandReg(i, physReg);
176                        // mark as dirty if this is def&use
177                        if (op.isDef()) dirty_[physReg] = true;
178                    }
179                }
180
181                // spill implicit defs
182                const TargetInstrDescriptor& tid =tii_.get(mii->getOpcode());
183                for (const unsigned* id = tid.ImplicitDefs; *id; ++id)
184                    vacatePhysReg(mbb, mii, *id);
185
186                // rewrite def operands (def&use was handled with the
187                // uses so don't check for those here)
188                for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
189                    MachineOperand& op = mii->getOperand(i);
190                    if (op.isRegister() && op.getReg() && !op.isUse())
191                        if (MRegisterInfo::isPhysicalRegister(op.getReg()))
192                            vacatePhysReg(mbb, mii, op.getReg());
193                        else {
194                            unsigned physReg = vrm_.getPhys(op.getReg());
195                            handleDef(mbb, mii, op.getReg(), physReg);
196                            mii->SetMachineOperandReg(i, physReg);
197                        }
198                }
199
200                DEBUG(std::cerr << '\t'; mii->print(std::cerr, tm_));
201            }
202
203            for (unsigned i = 1, e = p2vMap_.size(); i != e; ++i)
204                vacateJustPhysReg(mbb, mbb.getFirstTerminator(), i);
205
206        }
207    };
208}
209
210
211void llvm::eliminateVirtRegs(MachineFunction& mf, const VirtRegMap& vrm)
212{
213    Spiller(mf, vrm).eliminateVirtRegs();
214}
215