VirtRegMap.cpp revision 860d482b5940d0e7fff09f50f2df409de4b989ff 
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
46VirtRegMap::VirtRegMap(MachineFunction &mf)
47  : TII(*mf.getTarget().getInstrInfo()), MF(mf),
48    Virt2PhysMap(NO_PHYS_REG), Virt2StackSlotMap(NO_STACK_SLOT),
49    Virt2ReMatIdMap(NO_STACK_SLOT), Virt2SplitMap(0),
50    Virt2SplitKillMap(0), ReMatMap(NULL), ReMatId(MAX_STACK_SLOT+1),
51    LowSpillSlot(NO_STACK_SLOT), HighSpillSlot(NO_STACK_SLOT) {
52  SpillSlotToUsesMap.resize(8);
53  ImplicitDefed.resize(MF.getRegInfo().getLastVirtReg()+1-
54                       TargetRegisterInfo::FirstVirtualRegister);
55  grow();
56}
57
58void VirtRegMap::grow() {
59  unsigned LastVirtReg = MF.getRegInfo().getLastVirtReg();
60  Virt2PhysMap.grow(LastVirtReg);
61  Virt2StackSlotMap.grow(LastVirtReg);
62  Virt2ReMatIdMap.grow(LastVirtReg);
63  Virt2SplitMap.grow(LastVirtReg);
64  Virt2SplitKillMap.grow(LastVirtReg);
65  ReMatMap.grow(LastVirtReg);
66  ImplicitDefed.resize(LastVirtReg-TargetRegisterInfo::FirstVirtualRegister+1);
67}
68
69int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) {
70  assert(TargetRegisterInfo::isVirtualRegister(virtReg));
71  assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
72         "attempt to assign stack slot to already spilled register");
73  const TargetRegisterClass* RC = MF.getRegInfo().getRegClass(virtReg);
74  int SS = MF.getFrameInfo()->CreateStackObject(RC->getSize(),
75                                                RC->getAlignment());
76  if (LowSpillSlot == NO_STACK_SLOT)
77    LowSpillSlot = SS;
78  if (HighSpillSlot == NO_STACK_SLOT || SS > HighSpillSlot)
79    HighSpillSlot = SS;
80  unsigned Idx = SS-LowSpillSlot;
81  while (Idx >= SpillSlotToUsesMap.size())
82    SpillSlotToUsesMap.resize(SpillSlotToUsesMap.size()*2);
83  Virt2StackSlotMap[virtReg] = SS;
84  ++NumSpills;
85  return SS;
86}
87
88void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) {
89  assert(TargetRegisterInfo::isVirtualRegister(virtReg));
90  assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
91         "attempt to assign stack slot to already spilled register");
92  assert((SS >= 0 ||
93          (SS >= MF.getFrameInfo()->getObjectIndexBegin())) &&
94         "illegal fixed frame index");
95  Virt2StackSlotMap[virtReg] = SS;
96}
97
98int VirtRegMap::assignVirtReMatId(unsigned virtReg) {
99  assert(TargetRegisterInfo::isVirtualRegister(virtReg));
100  assert(Virt2ReMatIdMap[virtReg] == NO_STACK_SLOT &&
101         "attempt to assign re-mat id to already spilled register");
102  Virt2ReMatIdMap[virtReg] = ReMatId;
103  return ReMatId++;
104}
105
106void VirtRegMap::assignVirtReMatId(unsigned virtReg, int id) {
107  assert(TargetRegisterInfo::isVirtualRegister(virtReg));
108  assert(Virt2ReMatIdMap[virtReg] == NO_STACK_SLOT &&
109         "attempt to assign re-mat id to already spilled register");
110  Virt2ReMatIdMap[virtReg] = id;
111}
112
113int VirtRegMap::getEmergencySpillSlot(const TargetRegisterClass *RC) {
114  std::map<const TargetRegisterClass*, int>::iterator I =
115    EmergencySpillSlots.find(RC);
116  if (I != EmergencySpillSlots.end())
117    return I->second;
118  int SS = MF.getFrameInfo()->CreateStackObject(RC->getSize(),
119                                                RC->getAlignment());
120  if (LowSpillSlot == NO_STACK_SLOT)
121    LowSpillSlot = SS;
122  if (HighSpillSlot == NO_STACK_SLOT || SS > HighSpillSlot)
123    HighSpillSlot = SS;
124  EmergencySpillSlots[RC] = SS;
125  return SS;
126}
127
128void VirtRegMap::addSpillSlotUse(int FI, MachineInstr *MI) {
129  if (!MF.getFrameInfo()->isFixedObjectIndex(FI)) {
130    // If FI < LowSpillSlot, this stack reference was produced by
131    // instruction selection and is not a spill
132    if (FI >= LowSpillSlot) {
133      assert(FI >= 0 && "Spill slot index should not be negative!");
134      assert((unsigned)FI-LowSpillSlot < SpillSlotToUsesMap.size()
135             && "Invalid spill slot");
136      SpillSlotToUsesMap[FI-LowSpillSlot].insert(MI);
137    }
138  }
139}
140
141void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *OldMI,
142                            MachineInstr *NewMI, ModRef MRInfo) {
143  // Move previous memory references folded to new instruction.
144  MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(NewMI);
145  for (MI2VirtMapTy::iterator I = MI2VirtMap.lower_bound(OldMI),
146         E = MI2VirtMap.end(); I != E && I->first == OldMI; ) {
147    MI2VirtMap.insert(IP, std::make_pair(NewMI, I->second));
148    MI2VirtMap.erase(I++);
149  }
150
151  // add new memory reference
152  MI2VirtMap.insert(IP, std::make_pair(NewMI, std::make_pair(VirtReg, MRInfo)));
153}
154
155void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *MI, ModRef MRInfo) {
156  MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(MI);
157  MI2VirtMap.insert(IP, std::make_pair(MI, std::make_pair(VirtReg, MRInfo)));
158}
159
160void VirtRegMap::RemoveMachineInstrFromMaps(MachineInstr *MI) {
161  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
162    MachineOperand &MO = MI->getOperand(i);
163    if (!MO.isFI())
164      continue;
165    int FI = MO.getIndex();
166    if (MF.getFrameInfo()->isFixedObjectIndex(FI))
167      continue;
168    // This stack reference was produced by instruction selection and
169    // is not a spill
170    if (FI < LowSpillSlot)
171      continue;
172    assert((unsigned)FI-LowSpillSlot < SpillSlotToUsesMap.size()
173           && "Invalid spill slot");
174    SpillSlotToUsesMap[FI-LowSpillSlot].erase(MI);
175  }
176  MI2VirtMap.erase(MI);
177  SpillPt2VirtMap.erase(MI);
178  RestorePt2VirtMap.erase(MI);
179  EmergencySpillMap.erase(MI);
180}
181
182void VirtRegMap::print(std::ostream &OS) const {
183  const TargetRegisterInfo* TRI = MF.getTarget().getRegisterInfo();
184
185  OS << "********** REGISTER MAP **********\n";
186  for (unsigned i = TargetRegisterInfo::FirstVirtualRegister,
187         e = MF.getRegInfo().getLastVirtReg(); i <= e; ++i) {
188    if (Virt2PhysMap[i] != (unsigned)VirtRegMap::NO_PHYS_REG)
189      OS << "[reg" << i << " -> " << TRI->getName(Virt2PhysMap[i])
190         << "]\n";
191  }
192
193  for (unsigned i = TargetRegisterInfo::FirstVirtualRegister,
194         e = MF.getRegInfo().getLastVirtReg(); i <= e; ++i)
195    if (Virt2StackSlotMap[i] != VirtRegMap::NO_STACK_SLOT)
196      OS << "[reg" << i << " -> fi#" << Virt2StackSlotMap[i] << "]\n";
197  OS << '\n';
198}
199
200void VirtRegMap::dump() const {
201  print(cerr);
202}