1 //===-- llvm/CodeGen/VirtRegMap.cpp - Virtual Register Map ----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the VirtRegMap class.
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
17 //===----------------------------------------------------------------------===//
19 #define DEBUG_TYPE "virtregmap"
20 #include "VirtRegMap.h"
21 #include "llvm/Function.h"
22 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
23 #include "llvm/CodeGen/MachineFrameInfo.h"
24 #include "llvm/CodeGen/MachineFunction.h"
25 #include "llvm/CodeGen/MachineInstrBuilder.h"
26 #include "llvm/CodeGen/MachineRegisterInfo.h"
27 #include "llvm/Target/TargetMachine.h"
28 #include "llvm/Target/TargetInstrInfo.h"
29 #include "llvm/Support/CommandLine.h"
30 #include "llvm/Support/Compiler.h"
31 #include "llvm/Support/Debug.h"
32 #include "llvm/ADT/BitVector.h"
33 #include "llvm/ADT/DenseMap.h"
34 #include "llvm/ADT/DepthFirstIterator.h"
35 #include "llvm/ADT/Statistic.h"
36 #include "llvm/ADT/STLExtras.h"
37 #include "llvm/ADT/SmallSet.h"
41 STATISTIC(NumSpills
, "Number of register spills");
43 //===----------------------------------------------------------------------===//
44 // VirtRegMap implementation
45 //===----------------------------------------------------------------------===//
47 char VirtRegMap::ID
= 0;
49 static RegisterPass
<VirtRegMap
>
50 X("virtregmap", "Virtual Register Map");
52 bool VirtRegMap::runOnMachineFunction(MachineFunction
&mf
) {
53 TII
= mf
.getTarget().getInstrInfo();
56 ReMatId
= MAX_STACK_SLOT
+1;
57 LowSpillSlot
= HighSpillSlot
= NO_STACK_SLOT
;
60 Virt2StackSlotMap
.clear();
61 Virt2ReMatIdMap
.clear();
62 Virt2SplitMap
.clear();
63 Virt2SplitKillMap
.clear();
65 ImplicitDefed
.clear();
66 SpillSlotToUsesMap
.clear();
68 SpillPt2VirtMap
.clear();
69 RestorePt2VirtMap
.clear();
70 EmergencySpillMap
.clear();
71 EmergencySpillSlots
.clear();
73 SpillSlotToUsesMap
.resize(8);
74 ImplicitDefed
.resize(MF
->getRegInfo().getLastVirtReg()+1-
75 TargetRegisterInfo::FirstVirtualRegister
);
81 void VirtRegMap::grow() {
82 unsigned LastVirtReg
= MF
->getRegInfo().getLastVirtReg();
83 Virt2PhysMap
.grow(LastVirtReg
);
84 Virt2StackSlotMap
.grow(LastVirtReg
);
85 Virt2ReMatIdMap
.grow(LastVirtReg
);
86 Virt2SplitMap
.grow(LastVirtReg
);
87 Virt2SplitKillMap
.grow(LastVirtReg
);
88 ReMatMap
.grow(LastVirtReg
);
89 ImplicitDefed
.resize(LastVirtReg
-TargetRegisterInfo::FirstVirtualRegister
+1);
92 int VirtRegMap::assignVirt2StackSlot(unsigned virtReg
) {
93 assert(TargetRegisterInfo::isVirtualRegister(virtReg
));
94 assert(Virt2StackSlotMap
[virtReg
] == NO_STACK_SLOT
&&
95 "attempt to assign stack slot to already spilled register");
96 const TargetRegisterClass
* RC
= MF
->getRegInfo().getRegClass(virtReg
);
97 int SS
= MF
->getFrameInfo()->CreateStackObject(RC
->getSize(),
99 if (LowSpillSlot
== NO_STACK_SLOT
)
101 if (HighSpillSlot
== NO_STACK_SLOT
|| SS
> HighSpillSlot
)
103 unsigned Idx
= SS
-LowSpillSlot
;
104 while (Idx
>= SpillSlotToUsesMap
.size())
105 SpillSlotToUsesMap
.resize(SpillSlotToUsesMap
.size()*2);
106 Virt2StackSlotMap
[virtReg
] = SS
;
111 void VirtRegMap::assignVirt2StackSlot(unsigned virtReg
, int SS
) {
112 assert(TargetRegisterInfo::isVirtualRegister(virtReg
));
113 assert(Virt2StackSlotMap
[virtReg
] == NO_STACK_SLOT
&&
114 "attempt to assign stack slot to already spilled register");
116 (SS
>= MF
->getFrameInfo()->getObjectIndexBegin())) &&
117 "illegal fixed frame index");
118 Virt2StackSlotMap
[virtReg
] = SS
;
121 int VirtRegMap::assignVirtReMatId(unsigned virtReg
) {
122 assert(TargetRegisterInfo::isVirtualRegister(virtReg
));
123 assert(Virt2ReMatIdMap
[virtReg
] == NO_STACK_SLOT
&&
124 "attempt to assign re-mat id to already spilled register");
125 Virt2ReMatIdMap
[virtReg
] = ReMatId
;
129 void VirtRegMap::assignVirtReMatId(unsigned virtReg
, int id
) {
130 assert(TargetRegisterInfo::isVirtualRegister(virtReg
));
131 assert(Virt2ReMatIdMap
[virtReg
] == NO_STACK_SLOT
&&
132 "attempt to assign re-mat id to already spilled register");
133 Virt2ReMatIdMap
[virtReg
] = id
;
136 int VirtRegMap::getEmergencySpillSlot(const TargetRegisterClass
*RC
) {
137 std::map
<const TargetRegisterClass
*, int>::iterator I
=
138 EmergencySpillSlots
.find(RC
);
139 if (I
!= EmergencySpillSlots
.end())
141 int SS
= MF
->getFrameInfo()->CreateStackObject(RC
->getSize(),
143 if (LowSpillSlot
== NO_STACK_SLOT
)
145 if (HighSpillSlot
== NO_STACK_SLOT
|| SS
> HighSpillSlot
)
147 EmergencySpillSlots
[RC
] = SS
;
151 void VirtRegMap::addSpillSlotUse(int FI
, MachineInstr
*MI
) {
152 if (!MF
->getFrameInfo()->isFixedObjectIndex(FI
)) {
153 // If FI < LowSpillSlot, this stack reference was produced by
154 // instruction selection and is not a spill
155 if (FI
>= LowSpillSlot
) {
156 assert(FI
>= 0 && "Spill slot index should not be negative!");
157 assert((unsigned)FI
-LowSpillSlot
< SpillSlotToUsesMap
.size()
158 && "Invalid spill slot");
159 SpillSlotToUsesMap
[FI
-LowSpillSlot
].insert(MI
);
164 void VirtRegMap::virtFolded(unsigned VirtReg
, MachineInstr
*OldMI
,
165 MachineInstr
*NewMI
, ModRef MRInfo
) {
166 // Move previous memory references folded to new instruction.
167 MI2VirtMapTy::iterator IP
= MI2VirtMap
.lower_bound(NewMI
);
168 for (MI2VirtMapTy::iterator I
= MI2VirtMap
.lower_bound(OldMI
),
169 E
= MI2VirtMap
.end(); I
!= E
&& I
->first
== OldMI
; ) {
170 MI2VirtMap
.insert(IP
, std::make_pair(NewMI
, I
->second
));
171 MI2VirtMap
.erase(I
++);
174 // add new memory reference
175 MI2VirtMap
.insert(IP
, std::make_pair(NewMI
, std::make_pair(VirtReg
, MRInfo
)));
178 void VirtRegMap::virtFolded(unsigned VirtReg
, MachineInstr
*MI
, ModRef MRInfo
) {
179 MI2VirtMapTy::iterator IP
= MI2VirtMap
.lower_bound(MI
);
180 MI2VirtMap
.insert(IP
, std::make_pair(MI
, std::make_pair(VirtReg
, MRInfo
)));
183 void VirtRegMap::RemoveMachineInstrFromMaps(MachineInstr
*MI
) {
184 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
185 MachineOperand
&MO
= MI
->getOperand(i
);
188 int FI
= MO
.getIndex();
189 if (MF
->getFrameInfo()->isFixedObjectIndex(FI
))
191 // This stack reference was produced by instruction selection and
193 if (FI
< LowSpillSlot
)
195 assert((unsigned)FI
-LowSpillSlot
< SpillSlotToUsesMap
.size()
196 && "Invalid spill slot");
197 SpillSlotToUsesMap
[FI
-LowSpillSlot
].erase(MI
);
199 MI2VirtMap
.erase(MI
);
200 SpillPt2VirtMap
.erase(MI
);
201 RestorePt2VirtMap
.erase(MI
);
202 EmergencySpillMap
.erase(MI
);
205 /// FindUnusedRegisters - Gather a list of allocatable registers that
206 /// have not been allocated to any virtual register.
207 bool VirtRegMap::FindUnusedRegisters(const TargetRegisterInfo
*TRI
,
208 LiveIntervals
* LIs
) {
209 unsigned NumRegs
= TRI
->getNumRegs();
211 UnusedRegs
.resize(NumRegs
);
213 BitVector
Used(NumRegs
);
214 for (unsigned i
= TargetRegisterInfo::FirstVirtualRegister
,
215 e
= MF
->getRegInfo().getLastVirtReg(); i
<= e
; ++i
)
216 if (Virt2PhysMap
[i
] != (unsigned)VirtRegMap::NO_PHYS_REG
)
217 Used
.set(Virt2PhysMap
[i
]);
219 BitVector Allocatable
= TRI
->getAllocatableSet(*MF
);
220 bool AnyUnused
= false;
221 for (unsigned Reg
= 1; Reg
< NumRegs
; ++Reg
) {
222 if (Allocatable
[Reg
] && !Used
[Reg
] && !LIs
->hasInterval(Reg
)) {
223 bool ReallyUnused
= true;
224 for (const unsigned *AS
= TRI
->getAliasSet(Reg
); *AS
; ++AS
) {
225 if (Used
[*AS
] || LIs
->hasInterval(*AS
)) {
226 ReallyUnused
= false;
240 void VirtRegMap::print(std::ostream
&OS
, const Module
* M
) const {
241 const TargetRegisterInfo
* TRI
= MF
->getTarget().getRegisterInfo();
243 OS
<< "********** REGISTER MAP **********\n";
244 for (unsigned i
= TargetRegisterInfo::FirstVirtualRegister
,
245 e
= MF
->getRegInfo().getLastVirtReg(); i
<= e
; ++i
) {
246 if (Virt2PhysMap
[i
] != (unsigned)VirtRegMap::NO_PHYS_REG
)
247 OS
<< "[reg" << i
<< " -> " << TRI
->getName(Virt2PhysMap
[i
])
251 for (unsigned i
= TargetRegisterInfo::FirstVirtualRegister
,
252 e
= MF
->getRegInfo().getLastVirtReg(); i
<= e
; ++i
)
253 if (Virt2StackSlotMap
[i
] != VirtRegMap::NO_STACK_SLOT
)
254 OS
<< "[reg" << i
<< " -> fi#" << Virt2StackSlotMap
[i
] << "]\n";
258 void VirtRegMap::dump() const {