Change allowsUnalignedMemoryAccesses to take type argument since some targets
[llvm/avr.git] / lib / CodeGen / VirtRegMap.cpp
blob7ee4eeb6981d2cd91f8f5b9b7c8dbf024b8f8c0e
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.
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.
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/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/BitVector.h"
35 #include "llvm/ADT/DenseMap.h"
36 #include "llvm/ADT/DepthFirstIterator.h"
37 #include "llvm/ADT/Statistic.h"
38 #include "llvm/ADT/STLExtras.h"
39 #include "llvm/ADT/SmallSet.h"
40 #include <algorithm>
41 using namespace llvm;
43 STATISTIC(NumSpills , "Number of register spills");
45 //===----------------------------------------------------------------------===//
46 // VirtRegMap implementation
47 //===----------------------------------------------------------------------===//
49 char VirtRegMap::ID = 0;
51 static RegisterPass<VirtRegMap>
52 X("virtregmap", "Virtual Register Map");
54 bool VirtRegMap::runOnMachineFunction(MachineFunction &mf) {
55 MRI = &mf.getRegInfo();
56 TII = mf.getTarget().getInstrInfo();
57 TRI = mf.getTarget().getRegisterInfo();
58 MF = &mf;
60 ReMatId = MAX_STACK_SLOT+1;
61 LowSpillSlot = HighSpillSlot = NO_STACK_SLOT;
63 Virt2PhysMap.clear();
64 Virt2StackSlotMap.clear();
65 Virt2ReMatIdMap.clear();
66 Virt2SplitMap.clear();
67 Virt2SplitKillMap.clear();
68 ReMatMap.clear();
69 ImplicitDefed.clear();
70 SpillSlotToUsesMap.clear();
71 MI2VirtMap.clear();
72 SpillPt2VirtMap.clear();
73 RestorePt2VirtMap.clear();
74 EmergencySpillMap.clear();
75 EmergencySpillSlots.clear();
77 SpillSlotToUsesMap.resize(8);
78 ImplicitDefed.resize(MF->getRegInfo().getLastVirtReg()+1-
79 TargetRegisterInfo::FirstVirtualRegister);
81 allocatableRCRegs.clear();
82 for (TargetRegisterInfo::regclass_iterator I = TRI->regclass_begin(),
83 E = TRI->regclass_end(); I != E; ++I)
84 allocatableRCRegs.insert(std::make_pair(*I,
85 TRI->getAllocatableSet(mf, *I)));
87 grow();
89 return false;
92 void VirtRegMap::grow() {
93 unsigned LastVirtReg = MF->getRegInfo().getLastVirtReg();
94 Virt2PhysMap.grow(LastVirtReg);
95 Virt2StackSlotMap.grow(LastVirtReg);
96 Virt2ReMatIdMap.grow(LastVirtReg);
97 Virt2SplitMap.grow(LastVirtReg);
98 Virt2SplitKillMap.grow(LastVirtReg);
99 ReMatMap.grow(LastVirtReg);
100 ImplicitDefed.resize(LastVirtReg-TargetRegisterInfo::FirstVirtualRegister+1);
103 unsigned VirtRegMap::getRegAllocPref(unsigned virtReg) {
104 std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(virtReg);
105 unsigned physReg = Hint.second;
106 if (physReg &&
107 TargetRegisterInfo::isVirtualRegister(physReg) && hasPhys(physReg))
108 physReg = getPhys(physReg);
109 if (Hint.first == 0)
110 return (physReg && TargetRegisterInfo::isPhysicalRegister(physReg))
111 ? physReg : 0;
112 return TRI->ResolveRegAllocHint(Hint.first, physReg, *MF);
115 int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) {
116 assert(TargetRegisterInfo::isVirtualRegister(virtReg));
117 assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
118 "attempt to assign stack slot to already spilled register");
119 const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(virtReg);
120 int SS = MF->getFrameInfo()->CreateStackObject(RC->getSize(),
121 RC->getAlignment());
122 if (LowSpillSlot == NO_STACK_SLOT)
123 LowSpillSlot = SS;
124 if (HighSpillSlot == NO_STACK_SLOT || SS > HighSpillSlot)
125 HighSpillSlot = SS;
126 unsigned Idx = SS-LowSpillSlot;
127 while (Idx >= SpillSlotToUsesMap.size())
128 SpillSlotToUsesMap.resize(SpillSlotToUsesMap.size()*2);
129 Virt2StackSlotMap[virtReg] = SS;
130 ++NumSpills;
131 return SS;
134 void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) {
135 assert(TargetRegisterInfo::isVirtualRegister(virtReg));
136 assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
137 "attempt to assign stack slot to already spilled register");
138 assert((SS >= 0 ||
139 (SS >= MF->getFrameInfo()->getObjectIndexBegin())) &&
140 "illegal fixed frame index");
141 Virt2StackSlotMap[virtReg] = SS;
144 int VirtRegMap::assignVirtReMatId(unsigned virtReg) {
145 assert(TargetRegisterInfo::isVirtualRegister(virtReg));
146 assert(Virt2ReMatIdMap[virtReg] == NO_STACK_SLOT &&
147 "attempt to assign re-mat id to already spilled register");
148 Virt2ReMatIdMap[virtReg] = ReMatId;
149 return ReMatId++;
152 void VirtRegMap::assignVirtReMatId(unsigned virtReg, int id) {
153 assert(TargetRegisterInfo::isVirtualRegister(virtReg));
154 assert(Virt2ReMatIdMap[virtReg] == NO_STACK_SLOT &&
155 "attempt to assign re-mat id to already spilled register");
156 Virt2ReMatIdMap[virtReg] = id;
159 int VirtRegMap::getEmergencySpillSlot(const TargetRegisterClass *RC) {
160 std::map<const TargetRegisterClass*, int>::iterator I =
161 EmergencySpillSlots.find(RC);
162 if (I != EmergencySpillSlots.end())
163 return I->second;
164 int SS = MF->getFrameInfo()->CreateStackObject(RC->getSize(),
165 RC->getAlignment());
166 if (LowSpillSlot == NO_STACK_SLOT)
167 LowSpillSlot = SS;
168 if (HighSpillSlot == NO_STACK_SLOT || SS > HighSpillSlot)
169 HighSpillSlot = SS;
170 EmergencySpillSlots[RC] = SS;
171 return SS;
174 void VirtRegMap::addSpillSlotUse(int FI, MachineInstr *MI) {
175 if (!MF->getFrameInfo()->isFixedObjectIndex(FI)) {
176 // If FI < LowSpillSlot, this stack reference was produced by
177 // instruction selection and is not a spill
178 if (FI >= LowSpillSlot) {
179 assert(FI >= 0 && "Spill slot index should not be negative!");
180 assert((unsigned)FI-LowSpillSlot < SpillSlotToUsesMap.size()
181 && "Invalid spill slot");
182 SpillSlotToUsesMap[FI-LowSpillSlot].insert(MI);
187 void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *OldMI,
188 MachineInstr *NewMI, ModRef MRInfo) {
189 // Move previous memory references folded to new instruction.
190 MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(NewMI);
191 for (MI2VirtMapTy::iterator I = MI2VirtMap.lower_bound(OldMI),
192 E = MI2VirtMap.end(); I != E && I->first == OldMI; ) {
193 MI2VirtMap.insert(IP, std::make_pair(NewMI, I->second));
194 MI2VirtMap.erase(I++);
197 // add new memory reference
198 MI2VirtMap.insert(IP, std::make_pair(NewMI, std::make_pair(VirtReg, MRInfo)));
201 void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *MI, ModRef MRInfo) {
202 MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(MI);
203 MI2VirtMap.insert(IP, std::make_pair(MI, std::make_pair(VirtReg, MRInfo)));
206 void VirtRegMap::RemoveMachineInstrFromMaps(MachineInstr *MI) {
207 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
208 MachineOperand &MO = MI->getOperand(i);
209 if (!MO.isFI())
210 continue;
211 int FI = MO.getIndex();
212 if (MF->getFrameInfo()->isFixedObjectIndex(FI))
213 continue;
214 // This stack reference was produced by instruction selection and
215 // is not a spill
216 if (FI < LowSpillSlot)
217 continue;
218 assert((unsigned)FI-LowSpillSlot < SpillSlotToUsesMap.size()
219 && "Invalid spill slot");
220 SpillSlotToUsesMap[FI-LowSpillSlot].erase(MI);
222 MI2VirtMap.erase(MI);
223 SpillPt2VirtMap.erase(MI);
224 RestorePt2VirtMap.erase(MI);
225 EmergencySpillMap.erase(MI);
228 /// FindUnusedRegisters - Gather a list of allocatable registers that
229 /// have not been allocated to any virtual register.
230 bool VirtRegMap::FindUnusedRegisters(LiveIntervals* LIs) {
231 unsigned NumRegs = TRI->getNumRegs();
232 UnusedRegs.reset();
233 UnusedRegs.resize(NumRegs);
235 BitVector Used(NumRegs);
236 for (unsigned i = TargetRegisterInfo::FirstVirtualRegister,
237 e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i)
238 if (Virt2PhysMap[i] != (unsigned)VirtRegMap::NO_PHYS_REG)
239 Used.set(Virt2PhysMap[i]);
241 BitVector Allocatable = TRI->getAllocatableSet(*MF);
242 bool AnyUnused = false;
243 for (unsigned Reg = 1; Reg < NumRegs; ++Reg) {
244 if (Allocatable[Reg] && !Used[Reg] && !LIs->hasInterval(Reg)) {
245 bool ReallyUnused = true;
246 for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
247 if (Used[*AS] || LIs->hasInterval(*AS)) {
248 ReallyUnused = false;
249 break;
252 if (ReallyUnused) {
253 AnyUnused = true;
254 UnusedRegs.set(Reg);
259 return AnyUnused;
262 void VirtRegMap::print(std::ostream &OS, const Module* M) const {
263 raw_os_ostream RawOS(OS);
264 print(RawOS, M);
267 void VirtRegMap::print(raw_ostream &OS, const Module* M) const {
268 const TargetRegisterInfo* TRI = MF->getTarget().getRegisterInfo();
270 OS << "********** REGISTER MAP **********\n";
271 for (unsigned i = TargetRegisterInfo::FirstVirtualRegister,
272 e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i) {
273 if (Virt2PhysMap[i] != (unsigned)VirtRegMap::NO_PHYS_REG)
274 OS << "[reg" << i << " -> " << TRI->getName(Virt2PhysMap[i])
275 << "]\n";
278 for (unsigned i = TargetRegisterInfo::FirstVirtualRegister,
279 e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i)
280 if (Virt2StackSlotMap[i] != VirtRegMap::NO_STACK_SLOT)
281 OS << "[reg" << i << " -> fi#" << Virt2StackSlotMap[i] << "]\n";
282 OS << '\n';
285 void VirtRegMap::dump() const {
286 print(cerr);