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