VirtRegMap.cpp revision fbdad53f9e2f40ef0624390eef0ea3ccef782f71 
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 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/Target/TargetMachine.h"
27#include "llvm/Target/TargetInstrInfo.h"
28#include "llvm/Support/CommandLine.h"
29#include "llvm/Support/Compiler.h"
30#include "llvm/Support/Debug.h"
31#include "llvm/ADT/BitVector.h"
32#include "llvm/ADT/DenseMap.h"
33#include "llvm/ADT/DepthFirstIterator.h"
34#include "llvm/ADT/Statistic.h"
35#include "llvm/ADT/STLExtras.h"
36#include "llvm/ADT/SmallSet.h"
37#include <algorithm>
38using namespace llvm;
39
40STATISTIC(NumSpills  , "Number of register spills");
41
42//===----------------------------------------------------------------------===//
43//  VirtRegMap implementation
44//===----------------------------------------------------------------------===//
45
46char VirtRegMap::ID = 0;
47
48static RegisterPass<VirtRegMap>
49X("virtregmap", "Virtual Register Map");
50
51bool VirtRegMap::runOnMachineFunction(MachineFunction &mf) {
52  TII = mf.getTarget().getInstrInfo();
53  MF = &mf;
54
55  ReMatId = MAX_STACK_SLOT+1;
56  LowSpillSlot = HighSpillSlot = NO_STACK_SLOT;
57
58  Virt2PhysMap.clear();
59  Virt2StackSlotMap.clear();
60  Virt2ReMatIdMap.clear();
61  Virt2SplitMap.clear();
62  Virt2SplitKillMap.clear();
63  ReMatMap.clear();
64  ImplicitDefed.clear();
65  SpillSlotToUsesMap.clear();
66  MI2VirtMap.clear();
67  SpillPt2VirtMap.clear();
68  RestorePt2VirtMap.clear();
69  EmergencySpillMap.clear();
70  EmergencySpillSlots.clear();
71
72  SpillSlotToUsesMap.resize(8);
73  ImplicitDefed.resize(MF->getRegInfo().getLastVirtReg()+1-
74                       TargetRegisterInfo::FirstVirtualRegister);
75  grow();
76
77  return false;
78}
79
80void VirtRegMap::grow() {
81  unsigned LastVirtReg = MF->getRegInfo().getLastVirtReg();
82  Virt2PhysMap.grow(LastVirtReg);
83  Virt2StackSlotMap.grow(LastVirtReg);
84  Virt2ReMatIdMap.grow(LastVirtReg);
85  Virt2SplitMap.grow(LastVirtReg);
86  Virt2SplitKillMap.grow(LastVirtReg);
87  ReMatMap.grow(LastVirtReg);
88  ImplicitDefed.resize(LastVirtReg-TargetRegisterInfo::FirstVirtualRegister+1);
89}
90
91int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) {
92  assert(TargetRegisterInfo::isVirtualRegister(virtReg));
93  assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
94         "attempt to assign stack slot to already spilled register");
95  const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(virtReg);
96  int SS = MF->getFrameInfo()->CreateStackObject(RC->getSize(),
97                                                RC->getAlignment());
98  if (LowSpillSlot == NO_STACK_SLOT)
99    LowSpillSlot = SS;
100  if (HighSpillSlot == NO_STACK_SLOT || SS > HighSpillSlot)
101    HighSpillSlot = SS;
102  unsigned Idx = SS-LowSpillSlot;
103  while (Idx >= SpillSlotToUsesMap.size())
104    SpillSlotToUsesMap.resize(SpillSlotToUsesMap.size()*2);
105  Virt2StackSlotMap[virtReg] = SS;
106  ++NumSpills;
107  return SS;
108}
109
110void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) {
111  assert(TargetRegisterInfo::isVirtualRegister(virtReg));
112  assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
113         "attempt to assign stack slot to already spilled register");
114  assert((SS >= 0 ||
115          (SS >= MF->getFrameInfo()->getObjectIndexBegin())) &&
116         "illegal fixed frame index");
117  Virt2StackSlotMap[virtReg] = SS;
118}
119
120int VirtRegMap::assignVirtReMatId(unsigned virtReg) {
121  assert(TargetRegisterInfo::isVirtualRegister(virtReg));
122  assert(Virt2ReMatIdMap[virtReg] == NO_STACK_SLOT &&
123         "attempt to assign re-mat id to already spilled register");
124  Virt2ReMatIdMap[virtReg] = ReMatId;
125  return ReMatId++;
126}
127
128void VirtRegMap::assignVirtReMatId(unsigned virtReg, int id) {
129  assert(TargetRegisterInfo::isVirtualRegister(virtReg));
130  assert(Virt2ReMatIdMap[virtReg] == NO_STACK_SLOT &&
131         "attempt to assign re-mat id to already spilled register");
132  Virt2ReMatIdMap[virtReg] = id;
133}
134
135int VirtRegMap::getEmergencySpillSlot(const TargetRegisterClass *RC) {
136  std::map<const TargetRegisterClass*, int>::iterator I =
137    EmergencySpillSlots.find(RC);
138  if (I != EmergencySpillSlots.end())
139    return I->second;
140  int SS = MF->getFrameInfo()->CreateStackObject(RC->getSize(),
141                                                RC->getAlignment());
142  if (LowSpillSlot == NO_STACK_SLOT)
143    LowSpillSlot = SS;
144  if (HighSpillSlot == NO_STACK_SLOT || SS > HighSpillSlot)
145    HighSpillSlot = SS;
146  EmergencySpillSlots[RC] = SS;
147  return SS;
148}
149
150void VirtRegMap::addSpillSlotUse(int FI, MachineInstr *MI) {
151  if (!MF->getFrameInfo()->isFixedObjectIndex(FI)) {
152    // If FI < LowSpillSlot, this stack reference was produced by
153    // instruction selection and is not a spill
154    if (FI >= LowSpillSlot) {
155      assert(FI >= 0 && "Spill slot index should not be negative!");
156      assert((unsigned)FI-LowSpillSlot < SpillSlotToUsesMap.size()
157             && "Invalid spill slot");
158      SpillSlotToUsesMap[FI-LowSpillSlot].insert(MI);
159    }
160  }
161}
162
163void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *OldMI,
164                            MachineInstr *NewMI, ModRef MRInfo) {
165  // Move previous memory references folded to new instruction.
166  MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(NewMI);
167  for (MI2VirtMapTy::iterator I = MI2VirtMap.lower_bound(OldMI),
168         E = MI2VirtMap.end(); I != E && I->first == OldMI; ) {
169    MI2VirtMap.insert(IP, std::make_pair(NewMI, I->second));
170    MI2VirtMap.erase(I++);
171  }
172
173  // add new memory reference
174  MI2VirtMap.insert(IP, std::make_pair(NewMI, std::make_pair(VirtReg, MRInfo)));
175}
176
177void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *MI, ModRef MRInfo) {
178  MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(MI);
179  MI2VirtMap.insert(IP, std::make_pair(MI, std::make_pair(VirtReg, MRInfo)));
180}
181
182void VirtRegMap::RemoveMachineInstrFromMaps(MachineInstr *MI) {
183  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
184    MachineOperand &MO = MI->getOperand(i);
185    if (!MO.isFI())
186      continue;
187    int FI = MO.getIndex();
188    if (MF->getFrameInfo()->isFixedObjectIndex(FI))
189      continue;
190    // This stack reference was produced by instruction selection and
191    // is not a spill
192    if (FI < LowSpillSlot)
193      continue;
194    assert((unsigned)FI-LowSpillSlot < SpillSlotToUsesMap.size()
195           && "Invalid spill slot");
196    SpillSlotToUsesMap[FI-LowSpillSlot].erase(MI);
197  }
198  MI2VirtMap.erase(MI);
199  SpillPt2VirtMap.erase(MI);
200  RestorePt2VirtMap.erase(MI);
201  EmergencySpillMap.erase(MI);
202}
203
204void VirtRegMap::print(std::ostream &OS, const Module* M) const {
205  const TargetRegisterInfo* TRI = MF->getTarget().getRegisterInfo();
206
207  OS << "********** REGISTER MAP **********\n";
208  for (unsigned i = TargetRegisterInfo::FirstVirtualRegister,
209         e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i) {
210    if (Virt2PhysMap[i] != (unsigned)VirtRegMap::NO_PHYS_REG)
211      OS << "[reg" << i << " -> " << TRI->getName(Virt2PhysMap[i])
212         << "]\n";
213  }
214
215  for (unsigned i = TargetRegisterInfo::FirstVirtualRegister,
216         e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i)
217    if (Virt2StackSlotMap[i] != VirtRegMap::NO_STACK_SLOT)
218      OS << "[reg" << i << " -> fi#" << Virt2StackSlotMap[i] << "]\n";
219  OS << '\n';
220}
221
222void VirtRegMap::dump() const {
223  print(cerr);
224}
225