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/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/CodeGen/SlotIndexes.h"
28 #include "llvm/Target/TargetMachine.h"
29 #include "llvm/Target/TargetInstrInfo.h"
30 #include "llvm/Target/TargetRegisterInfo.h"
31 #include "llvm/Support/CommandLine.h"
32 #include "llvm/Support/Compiler.h"
33 #include "llvm/Support/Debug.h"
34 #include "llvm/Support/raw_ostream.h"
35 #include "llvm/ADT/BitVector.h"
36 #include "llvm/ADT/DenseMap.h"
37 #include "llvm/ADT/DepthFirstIterator.h"
38 #include "llvm/ADT/Statistic.h"
39 #include "llvm/ADT/STLExtras.h"
40 #include "llvm/ADT/SmallSet.h"
41 #include <algorithm>
42 using namespace llvm;
43 
44 STATISTIC(NumSpills  , "Number of register spills");
45 
46 //===----------------------------------------------------------------------===//
47 //  VirtRegMap implementation
48 //===----------------------------------------------------------------------===//
49 
50 char VirtRegMap::ID = 0;
51 
52 INITIALIZE_PASS(VirtRegMap, "virtregmap", "Virtual Register Map", false, false)
53 
54 bool VirtRegMap::runOnMachineFunction(MachineFunction &mf) {
55   MRI = &mf.getRegInfo();
56   TII = mf.getTarget().getInstrInfo();
57   TRI = mf.getTarget().getRegisterInfo();
58   MF = &mf;
59 
60   ReMatId = MAX_STACK_SLOT+1;
61   LowSpillSlot = HighSpillSlot = NO_STACK_SLOT;
62 
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();
76 
77   SpillSlotToUsesMap.resize(8);
78   ImplicitDefed.resize(MF->getRegInfo().getNumVirtRegs());
79 
80   allocatableRCRegs.clear();
81   for (TargetRegisterInfo::regclass_iterator I = TRI->regclass_begin(),
82          E = TRI->regclass_end(); I != E; ++I)
83     allocatableRCRegs.insert(std::make_pair(*I,
84                                             TRI->getAllocatableSet(mf, *I)));
85 
86   grow();
87 
88   return false;
89 }
90 
91 void VirtRegMap::grow() {
92   unsigned NumRegs = MF->getRegInfo().getNumVirtRegs();
93   Virt2PhysMap.resize(NumRegs);
94   Virt2StackSlotMap.resize(NumRegs);
95   Virt2ReMatIdMap.resize(NumRegs);
96   Virt2SplitMap.resize(NumRegs);
97   Virt2SplitKillMap.resize(NumRegs);
98   ReMatMap.resize(NumRegs);
99   ImplicitDefed.resize(NumRegs);
100 }
101 
102 unsigned VirtRegMap::createSpillSlot(const TargetRegisterClass *RC) {
103   int SS = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(),
104                                                       RC->getAlignment());
105   if (LowSpillSlot == NO_STACK_SLOT)
106     LowSpillSlot = SS;
107   if (HighSpillSlot == NO_STACK_SLOT || SS > HighSpillSlot)
108     HighSpillSlot = SS;
109   assert(SS >= LowSpillSlot && "Unexpected low spill slot");
110   unsigned Idx = SS-LowSpillSlot;
111   while (Idx >= SpillSlotToUsesMap.size())
112     SpillSlotToUsesMap.resize(SpillSlotToUsesMap.size()*2);
113   return SS;
114 }
115 
116 unsigned VirtRegMap::getRegAllocPref(unsigned virtReg) {
117   std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(virtReg);
118   unsigned physReg = Hint.second;
119   if (TargetRegisterInfo::isVirtualRegister(physReg) && hasPhys(physReg))
120     physReg = getPhys(physReg);
121   if (Hint.first == 0)
122     return (TargetRegisterInfo::isPhysicalRegister(physReg))
123       ? physReg : 0;
124   return TRI->ResolveRegAllocHint(Hint.first, physReg, *MF);
125 }
126 
127 int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) {
128   assert(TargetRegisterInfo::isVirtualRegister(virtReg));
129   assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
130          "attempt to assign stack slot to already spilled register");
131   const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(virtReg);
132   ++NumSpills;
133   return Virt2StackSlotMap[virtReg] = createSpillSlot(RC);
134 }
135 
136 void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) {
137   assert(TargetRegisterInfo::isVirtualRegister(virtReg));
138   assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
139          "attempt to assign stack slot to already spilled register");
140   assert((SS >= 0 ||
141           (SS >= MF->getFrameInfo()->getObjectIndexBegin())) &&
142          "illegal fixed frame index");
143   Virt2StackSlotMap[virtReg] = SS;
144 }
145 
146 int VirtRegMap::assignVirtReMatId(unsigned virtReg) {
147   assert(TargetRegisterInfo::isVirtualRegister(virtReg));
148   assert(Virt2ReMatIdMap[virtReg] == NO_STACK_SLOT &&
149          "attempt to assign re-mat id to already spilled register");
150   Virt2ReMatIdMap[virtReg] = ReMatId;
151   return ReMatId++;
152 }
153 
154 void VirtRegMap::assignVirtReMatId(unsigned virtReg, int id) {
155   assert(TargetRegisterInfo::isVirtualRegister(virtReg));
156   assert(Virt2ReMatIdMap[virtReg] == NO_STACK_SLOT &&
157          "attempt to assign re-mat id to already spilled register");
158   Virt2ReMatIdMap[virtReg] = id;
159 }
160 
161 int VirtRegMap::getEmergencySpillSlot(const TargetRegisterClass *RC) {
162   std::map<const TargetRegisterClass*, int>::iterator I =
163     EmergencySpillSlots.find(RC);
164   if (I != EmergencySpillSlots.end())
165     return I->second;
166   return EmergencySpillSlots[RC] = createSpillSlot(RC);
167 }
168 
169 void VirtRegMap::addSpillSlotUse(int FI, MachineInstr *MI) {
170   if (!MF->getFrameInfo()->isFixedObjectIndex(FI)) {
171     // If FI < LowSpillSlot, this stack reference was produced by
172     // instruction selection and is not a spill
173     if (FI >= LowSpillSlot) {
174       assert(FI >= 0 && "Spill slot index should not be negative!");
175       assert((unsigned)FI-LowSpillSlot < SpillSlotToUsesMap.size()
176              && "Invalid spill slot");
177       SpillSlotToUsesMap[FI-LowSpillSlot].insert(MI);
178     }
179   }
180 }
181 
182 void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *OldMI,
183                             MachineInstr *NewMI, ModRef MRInfo) {
184   // Move previous memory references folded to new instruction.
185   MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(NewMI);
186   for (MI2VirtMapTy::iterator I = MI2VirtMap.lower_bound(OldMI),
187          E = MI2VirtMap.end(); I != E && I->first == OldMI; ) {
188     MI2VirtMap.insert(IP, std::make_pair(NewMI, I->second));
189     MI2VirtMap.erase(I++);
190   }
191 
192   // add new memory reference
193   MI2VirtMap.insert(IP, std::make_pair(NewMI, std::make_pair(VirtReg, MRInfo)));
194 }
195 
196 void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *MI, ModRef MRInfo) {
197   MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(MI);
198   MI2VirtMap.insert(IP, std::make_pair(MI, std::make_pair(VirtReg, MRInfo)));
199 }
200 
201 void VirtRegMap::RemoveMachineInstrFromMaps(MachineInstr *MI) {
202   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
203     MachineOperand &MO = MI->getOperand(i);
204     if (!MO.isFI())
205       continue;
206     int FI = MO.getIndex();
207     if (MF->getFrameInfo()->isFixedObjectIndex(FI))
208       continue;
209     // This stack reference was produced by instruction selection and
210     // is not a spill
211     if (FI < LowSpillSlot)
212       continue;
213     assert((unsigned)FI-LowSpillSlot < SpillSlotToUsesMap.size()
214            && "Invalid spill slot");
215     SpillSlotToUsesMap[FI-LowSpillSlot].erase(MI);
216   }
217   MI2VirtMap.erase(MI);
218   SpillPt2VirtMap.erase(MI);
219   RestorePt2VirtMap.erase(MI);
220   EmergencySpillMap.erase(MI);
221 }
222 
223 /// FindUnusedRegisters - Gather a list of allocatable registers that
224 /// have not been allocated to any virtual register.
225 bool VirtRegMap::FindUnusedRegisters(LiveIntervals* LIs) {
226   unsigned NumRegs = TRI->getNumRegs();
227   UnusedRegs.reset();
228   UnusedRegs.resize(NumRegs);
229 
230   BitVector Used(NumRegs);
231   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
232     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
233     if (Virt2PhysMap[Reg] != (unsigned)VirtRegMap::NO_PHYS_REG)
234       Used.set(Virt2PhysMap[Reg]);
235   }
236 
237   BitVector Allocatable = TRI->getAllocatableSet(*MF);
238   bool AnyUnused = false;
239   for (unsigned Reg = 1; Reg < NumRegs; ++Reg) {
240     if (Allocatable[Reg] && !Used[Reg] && !LIs->hasInterval(Reg)) {
241       bool ReallyUnused = true;
242       for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
243         if (Used[*AS] || LIs->hasInterval(*AS)) {
244           ReallyUnused = false;
245           break;
246         }
247       }
248       if (ReallyUnused) {
249         AnyUnused = true;
250         UnusedRegs.set(Reg);
251       }
252     }
253   }
254 
255   return AnyUnused;
256 }
257 
258 void VirtRegMap::rewrite(SlotIndexes *Indexes) {
259   DEBUG(dbgs() << "********** REWRITE VIRTUAL REGISTERS **********\n"
260                << "********** Function: "
261                << MF->getFunction()->getName() << '\n');
262   DEBUG(dump());
263   SmallVector<unsigned, 8> SuperKills;
264 
265   for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
266        MBBI != MBBE; ++MBBI) {
267     DEBUG(MBBI->print(dbgs(), Indexes));
268     for (MachineBasicBlock::iterator MII = MBBI->begin(), MIE = MBBI->end();
269          MII != MIE;) {
270       MachineInstr *MI = MII;
271       ++MII;
272 
273       for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
274            MOE = MI->operands_end(); MOI != MOE; ++MOI) {
275         MachineOperand &MO = *MOI;
276         if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
277           continue;
278         unsigned VirtReg = MO.getReg();
279         unsigned PhysReg = getPhys(VirtReg);
280         assert(PhysReg != NO_PHYS_REG && "Instruction uses unmapped VirtReg");
281 
282         // Preserve semantics of sub-register operands.
283         if (MO.getSubReg()) {
284           // A virtual register kill refers to the whole register, so we may
285           // have to add <imp-use,kill> operands for the super-register.
286           if (MO.isUse() && MO.isKill() && !MO.isUndef())
287             SuperKills.push_back(PhysReg);
288 
289           // We don't have to deal with sub-register defs because
290           // LiveIntervalAnalysis already added the necessary <imp-def>
291           // operands.
292 
293           // PhysReg operands cannot have subregister indexes.
294           PhysReg = TRI->getSubReg(PhysReg, MO.getSubReg());
295           assert(PhysReg && "Invalid SubReg for physical register");
296           MO.setSubReg(0);
297         }
298         // Rewrite. Note we could have used MachineOperand::substPhysReg(), but
299         // we need the inlining here.
300         MO.setReg(PhysReg);
301       }
302 
303       // Add any missing super-register kills after rewriting the whole
304       // instruction.
305       while (!SuperKills.empty())
306         MI->addRegisterKilled(SuperKills.pop_back_val(), TRI, true);
307 
308       DEBUG(dbgs() << "> " << *MI);
309 
310       // Finally, remove any identity copies.
311       if (MI->isIdentityCopy()) {
312         if (MI->getNumOperands() == 2) {
313           DEBUG(dbgs() << "Deleting identity copy.\n");
314           RemoveMachineInstrFromMaps(MI);
315           if (Indexes)
316             Indexes->removeMachineInstrFromMaps(MI);
317           // It's safe to erase MI because MII has already been incremented.
318           MI->eraseFromParent();
319         } else {
320           // Transform identity copy to a KILL to deal with subregisters.
321           MI->setDesc(TII->get(TargetOpcode::KILL));
322           DEBUG(dbgs() << "Identity copy: " << *MI);
323         }
324       }
325     }
326   }
327 
328   // Tell MRI about physical registers in use.
329   for (unsigned Reg = 1, RegE = TRI->getNumRegs(); Reg != RegE; ++Reg)
330     if (!MRI->reg_nodbg_empty(Reg))
331       MRI->setPhysRegUsed(Reg);
332 }
333 
334 void VirtRegMap::print(raw_ostream &OS, const Module* M) const {
335   const TargetRegisterInfo* TRI = MF->getTarget().getRegisterInfo();
336   const MachineRegisterInfo &MRI = MF->getRegInfo();
337 
338   OS << "********** REGISTER MAP **********\n";
339   for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) {
340     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
341     if (Virt2PhysMap[Reg] != (unsigned)VirtRegMap::NO_PHYS_REG) {
342       OS << '[' << PrintReg(Reg, TRI) << " -> "
343          << PrintReg(Virt2PhysMap[Reg], TRI) << "] "
344          << MRI.getRegClass(Reg)->getName() << "\n";
345     }
346   }
347 
348   for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) {
349     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
350     if (Virt2StackSlotMap[Reg] != VirtRegMap::NO_STACK_SLOT) {
351       OS << '[' << PrintReg(Reg, TRI) << " -> fi#" << Virt2StackSlotMap[Reg]
352          << "] " << MRI.getRegClass(Reg)->getName() << "\n";
353     }
354   }
355   OS << '\n';
356 }
357 
358 void VirtRegMap::dump() const {
359   print(dbgs());
360 }
361