VirtRegMap.cpp revision 2d44e02533cdc2ae011121ef651dda93769ced2b 
1//===-- llvm/CodeGen/VirtRegMap.cpp - Virtual Register Map ----------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the VirtRegMap class.
11//
12// It also contains implementations of 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 "virtregmap"
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/MachineInstrBuilder.h"
25#include "llvm/CodeGen/MachineRegisterInfo.h"
26#include "llvm/CodeGen/SlotIndexes.h"
27#include "llvm/Target/TargetMachine.h"
28#include "llvm/Target/TargetInstrInfo.h"
29#include "llvm/Target/TargetRegisterInfo.h"
30#include "llvm/Support/CommandLine.h"
31#include "llvm/Support/Compiler.h"
32#include "llvm/Support/Debug.h"
33#include "llvm/Support/raw_ostream.h"
34#include "llvm/ADT/Statistic.h"
35#include "llvm/ADT/STLExtras.h"
36#include <algorithm>
37using namespace llvm;
38
39STATISTIC(NumSpillSlots, "Number of spill slots allocated");
40STATISTIC(NumIdCopies,   "Number of identity moves eliminated after rewriting");
41
42//===----------------------------------------------------------------------===//
43//  VirtRegMap implementation
44//===----------------------------------------------------------------------===//
45
46char VirtRegMap::ID = 0;
47
48INITIALIZE_PASS(VirtRegMap, "virtregmap", "Virtual Register Map", false, false)
49
50bool VirtRegMap::runOnMachineFunction(MachineFunction &mf) {
51  MRI = &mf.getRegInfo();
52  TII = mf.getTarget().getInstrInfo();
53  TRI = mf.getTarget().getRegisterInfo();
54  MF = &mf;
55
56  Virt2PhysMap.clear();
57  Virt2StackSlotMap.clear();
58  Virt2SplitMap.clear();
59
60  grow();
61  return false;
62}
63
64void VirtRegMap::grow() {
65  unsigned NumRegs = MF->getRegInfo().getNumVirtRegs();
66  Virt2PhysMap.resize(NumRegs);
67  Virt2StackSlotMap.resize(NumRegs);
68  Virt2SplitMap.resize(NumRegs);
69}
70
71unsigned VirtRegMap::createSpillSlot(const TargetRegisterClass *RC) {
72  int SS = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(),
73                                                      RC->getAlignment());
74  ++NumSpillSlots;
75  return SS;
76}
77
78unsigned VirtRegMap::getRegAllocPref(unsigned virtReg) {
79  std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(virtReg);
80  unsigned physReg = Hint.second;
81  if (TargetRegisterInfo::isVirtualRegister(physReg) && hasPhys(physReg))
82    physReg = getPhys(physReg);
83  if (Hint.first == 0)
84    return (TargetRegisterInfo::isPhysicalRegister(physReg))
85      ? physReg : 0;
86  return TRI->ResolveRegAllocHint(Hint.first, physReg, *MF);
87}
88
89int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) {
90  assert(TargetRegisterInfo::isVirtualRegister(virtReg));
91  assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
92         "attempt to assign stack slot to already spilled register");
93  const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(virtReg);
94  return Virt2StackSlotMap[virtReg] = createSpillSlot(RC);
95}
96
97void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) {
98  assert(TargetRegisterInfo::isVirtualRegister(virtReg));
99  assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
100         "attempt to assign stack slot to already spilled register");
101  assert((SS >= 0 ||
102          (SS >= MF->getFrameInfo()->getObjectIndexBegin())) &&
103         "illegal fixed frame index");
104  Virt2StackSlotMap[virtReg] = SS;
105}
106
107void VirtRegMap::rewrite(SlotIndexes *Indexes) {
108  DEBUG(dbgs() << "********** REWRITE VIRTUAL REGISTERS **********\n"
109               << "********** Function: "
110               << MF->getFunction()->getName() << '\n');
111  DEBUG(dump());
112  SmallVector<unsigned, 8> SuperDeads;
113  SmallVector<unsigned, 8> SuperDefs;
114  SmallVector<unsigned, 8> SuperKills;
115#ifndef NDEBUG
116  BitVector Reserved = TRI->getReservedRegs(*MF);
117#endif
118
119  for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
120       MBBI != MBBE; ++MBBI) {
121    DEBUG(MBBI->print(dbgs(), Indexes));
122    for (MachineBasicBlock::iterator MII = MBBI->begin(), MIE = MBBI->end();
123         MII != MIE;) {
124      MachineInstr *MI = MII;
125      ++MII;
126
127      for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
128           MOE = MI->operands_end(); MOI != MOE; ++MOI) {
129        MachineOperand &MO = *MOI;
130        if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
131          continue;
132        unsigned VirtReg = MO.getReg();
133        unsigned PhysReg = getPhys(VirtReg);
134        assert(PhysReg != NO_PHYS_REG && "Instruction uses unmapped VirtReg");
135        assert(!Reserved.test(PhysReg) && "Reserved register assignment");
136
137        // Preserve semantics of sub-register operands.
138        if (MO.getSubReg()) {
139          // A virtual register kill refers to the whole register, so we may
140          // have to add <imp-use,kill> operands for the super-register.  A
141          // partial redef always kills and redefines the super-register.
142          if (MO.readsReg() && (MO.isDef() || MO.isKill()))
143            SuperKills.push_back(PhysReg);
144
145          if (MO.isDef()) {
146            // The <def,undef> flag only makes sense for sub-register defs, and
147            // we are substituting a full physreg.  An <imp-use,kill> operand
148            // from the SuperKills list will represent the partial read of the
149            // super-register.
150            MO.setIsUndef(false);
151
152            // Also add implicit defs for the super-register.
153            if (MO.isDead())
154              SuperDeads.push_back(PhysReg);
155            else
156              SuperDefs.push_back(PhysReg);
157          }
158
159          // PhysReg operands cannot have subregister indexes.
160          PhysReg = TRI->getSubReg(PhysReg, MO.getSubReg());
161          assert(PhysReg && "Invalid SubReg for physical register");
162          MO.setSubReg(0);
163        }
164        // Rewrite. Note we could have used MachineOperand::substPhysReg(), but
165        // we need the inlining here.
166        MO.setReg(PhysReg);
167      }
168
169      // Add any missing super-register kills after rewriting the whole
170      // instruction.
171      while (!SuperKills.empty())
172        MI->addRegisterKilled(SuperKills.pop_back_val(), TRI, true);
173
174      while (!SuperDeads.empty())
175        MI->addRegisterDead(SuperDeads.pop_back_val(), TRI, true);
176
177      while (!SuperDefs.empty())
178        MI->addRegisterDefined(SuperDefs.pop_back_val(), TRI);
179
180      DEBUG(dbgs() << "> " << *MI);
181
182      // Finally, remove any identity copies.
183      if (MI->isIdentityCopy()) {
184        ++NumIdCopies;
185        if (MI->getNumOperands() == 2) {
186          DEBUG(dbgs() << "Deleting identity copy.\n");
187          if (Indexes)
188            Indexes->removeMachineInstrFromMaps(MI);
189          // It's safe to erase MI because MII has already been incremented.
190          MI->eraseFromParent();
191        } else {
192          // Transform identity copy to a KILL to deal with subregisters.
193          MI->setDesc(TII->get(TargetOpcode::KILL));
194          DEBUG(dbgs() << "Identity copy: " << *MI);
195        }
196      }
197    }
198  }
199
200  // Tell MRI about physical registers in use.
201  for (unsigned Reg = 1, RegE = TRI->getNumRegs(); Reg != RegE; ++Reg)
202    if (!MRI->reg_nodbg_empty(Reg))
203      MRI->setPhysRegUsed(Reg);
204}
205
206void VirtRegMap::print(raw_ostream &OS, const Module* M) const {
207  const TargetRegisterInfo* TRI = MF->getTarget().getRegisterInfo();
208  const MachineRegisterInfo &MRI = MF->getRegInfo();
209
210  OS << "********** REGISTER MAP **********\n";
211  for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) {
212    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
213    if (Virt2PhysMap[Reg] != (unsigned)VirtRegMap::NO_PHYS_REG) {
214      OS << '[' << PrintReg(Reg, TRI) << " -> "
215         << PrintReg(Virt2PhysMap[Reg], TRI) << "] "
216         << MRI.getRegClass(Reg)->getName() << "\n";
217    }
218  }
219
220  for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) {
221    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
222    if (Virt2StackSlotMap[Reg] != VirtRegMap::NO_STACK_SLOT) {
223      OS << '[' << PrintReg(Reg, TRI) << " -> fi#" << Virt2StackSlotMap[Reg]
224         << "] " << MRI.getRegClass(Reg)->getName() << "\n";
225    }
226  }
227  OS << '\n';
228}
229
230void VirtRegMap::dump() const {
231  print(dbgs());
232}
233