1 //===-- llvm/CodeGen/VirtRegMap.h - Virtual Register Map -*- C++ -*--------===//
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 a virtual register map. This maps virtual registers to
11 // physical registers and virtual registers to stack slots. It is created and
12 // updated by a register allocator and then used by a machine code rewriter that
13 // adds spill code and rewrites virtual into physical register references.
15 //===----------------------------------------------------------------------===//
17 #ifndef LLVM_CODEGEN_VIRTREGMAP_H
18 #define LLVM_CODEGEN_VIRTREGMAP_H
20 #include "llvm/CodeGen/MachineFunctionPass.h"
21 #include "llvm/CodeGen/LiveInterval.h"
22 #include "llvm/Target/TargetRegisterInfo.h"
23 #include "llvm/ADT/BitVector.h"
24 #include "llvm/ADT/DenseMap.h"
25 #include "llvm/ADT/IndexedMap.h"
26 #include "llvm/ADT/SmallPtrSet.h"
27 #include "llvm/ADT/SmallVector.h"
33 class MachineFunction;
34 class MachineRegisterInfo;
35 class TargetInstrInfo;
36 class TargetRegisterInfo;
40 class VirtRegMap : public MachineFunctionPass {
44 NO_STACK_SLOT = (1L << 30)-1,
45 MAX_STACK_SLOT = (1L << 18)-1
48 enum ModRef { isRef = 1, isMod = 2, isModRef = 3 };
49 typedef std::multimap<MachineInstr*,
50 std::pair<unsigned, ModRef> > MI2VirtMapTy;
53 MachineRegisterInfo *MRI;
54 const TargetInstrInfo *TII;
55 const TargetRegisterInfo *TRI;
58 DenseMap<const TargetRegisterClass*, BitVector> allocatableRCRegs;
60 /// Virt2PhysMap - This is a virtual to physical register
61 /// mapping. Each virtual register is required to have an entry in
62 /// it; even spilled virtual registers (the register mapped to a
63 /// spilled register is the temporary used to load it from the
65 IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2PhysMap;
67 /// Virt2StackSlotMap - This is virtual register to stack slot
68 /// mapping. Each spilled virtual register has an entry in it
69 /// which corresponds to the stack slot this register is spilled
71 IndexedMap<int, VirtReg2IndexFunctor> Virt2StackSlotMap;
73 /// Virt2ReMatIdMap - This is virtual register to rematerialization id
74 /// mapping. Each spilled virtual register that should be remat'd has an
75 /// entry in it which corresponds to the remat id.
76 IndexedMap<int, VirtReg2IndexFunctor> Virt2ReMatIdMap;
78 /// Virt2SplitMap - This is virtual register to splitted virtual register
80 IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2SplitMap;
82 /// Virt2SplitKillMap - This is splitted virtual register to its last use
83 /// (kill) index mapping.
84 IndexedMap<SlotIndex, VirtReg2IndexFunctor> Virt2SplitKillMap;
86 /// ReMatMap - This is virtual register to re-materialized instruction
87 /// mapping. Each virtual register whose definition is going to be
88 /// re-materialized has an entry in it.
89 IndexedMap<MachineInstr*, VirtReg2IndexFunctor> ReMatMap;
91 /// MI2VirtMap - This is MachineInstr to virtual register
92 /// mapping. In the case of memory spill code being folded into
93 /// instructions, we need to know which virtual register was
94 /// read/written by this instruction.
95 MI2VirtMapTy MI2VirtMap;
97 /// SpillPt2VirtMap - This records the virtual registers which should
98 /// be spilled right after the MachineInstr due to live interval
100 std::map<MachineInstr*, std::vector<std::pair<unsigned,bool> > >
103 /// RestorePt2VirtMap - This records the virtual registers which should
104 /// be restored right before the MachineInstr due to live interval
106 std::map<MachineInstr*, std::vector<unsigned> > RestorePt2VirtMap;
108 /// EmergencySpillMap - This records the physical registers that should
109 /// be spilled / restored around the MachineInstr since the register
110 /// allocator has run out of registers.
111 std::map<MachineInstr*, std::vector<unsigned> > EmergencySpillMap;
113 /// EmergencySpillSlots - This records emergency spill slots used to
114 /// spill physical registers when the register allocator runs out of
115 /// registers. Ideally only one stack slot is used per function per
117 std::map<const TargetRegisterClass*, int> EmergencySpillSlots;
119 /// ReMatId - Instead of assigning a stack slot to a to be rematerialized
120 /// virtual register, an unique id is being assigned. This keeps track of
121 /// the highest id used so far. Note, this starts at (1<<18) to avoid
122 /// conflicts with stack slot numbers.
125 /// LowSpillSlot, HighSpillSlot - Lowest and highest spill slot indexes.
126 int LowSpillSlot, HighSpillSlot;
128 /// SpillSlotToUsesMap - Records uses for each register spill slot.
129 SmallVector<SmallPtrSet<MachineInstr*, 4>, 8> SpillSlotToUsesMap;
131 /// ImplicitDefed - One bit for each virtual register. If set it indicates
132 /// the register is implicitly defined.
133 BitVector ImplicitDefed;
135 /// createSpillSlot - Allocate a spill slot for RC from MFI.
136 unsigned createSpillSlot(const TargetRegisterClass *RC);
138 VirtRegMap(const VirtRegMap&); // DO NOT IMPLEMENT
139 void operator=(const VirtRegMap&); // DO NOT IMPLEMENT
143 VirtRegMap() : MachineFunctionPass(ID), Virt2PhysMap(NO_PHYS_REG),
144 Virt2StackSlotMap(NO_STACK_SLOT),
145 Virt2ReMatIdMap(NO_STACK_SLOT), Virt2SplitMap(0),
146 Virt2SplitKillMap(SlotIndex()), ReMatMap(NULL),
147 ReMatId(MAX_STACK_SLOT+1),
148 LowSpillSlot(NO_STACK_SLOT), HighSpillSlot(NO_STACK_SLOT) { }
149 virtual bool runOnMachineFunction(MachineFunction &MF);
151 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
152 AU.setPreservesAll();
153 MachineFunctionPass::getAnalysisUsage(AU);
156 MachineFunction &getMachineFunction() const {
157 assert(MF && "getMachineFunction called before runOnMachineFunction");
161 MachineRegisterInfo &getRegInfo() const { return *MRI; }
162 const TargetRegisterInfo &getTargetRegInfo() const { return *TRI; }
166 /// @brief returns true if the specified virtual register is
167 /// mapped to a physical register
168 bool hasPhys(unsigned virtReg) const {
169 return getPhys(virtReg) != NO_PHYS_REG;
172 /// @brief returns the physical register mapped to the specified
174 unsigned getPhys(unsigned virtReg) const {
175 assert(TargetRegisterInfo::isVirtualRegister(virtReg));
176 return Virt2PhysMap[virtReg];
179 /// @brief creates a mapping for the specified virtual register to
180 /// the specified physical register
181 void assignVirt2Phys(unsigned virtReg, unsigned physReg) {
182 assert(TargetRegisterInfo::isVirtualRegister(virtReg) &&
183 TargetRegisterInfo::isPhysicalRegister(physReg));
184 assert(Virt2PhysMap[virtReg] == NO_PHYS_REG &&
185 "attempt to assign physical register to already mapped "
187 Virt2PhysMap[virtReg] = physReg;
190 /// @brief clears the specified virtual register's, physical
192 void clearVirt(unsigned virtReg) {
193 assert(TargetRegisterInfo::isVirtualRegister(virtReg));
194 assert(Virt2PhysMap[virtReg] != NO_PHYS_REG &&
195 "attempt to clear a not assigned virtual register");
196 Virt2PhysMap[virtReg] = NO_PHYS_REG;
199 /// @brief clears all virtual to physical register mappings
200 void clearAllVirt() {
201 Virt2PhysMap.clear();
205 /// @brief returns the register allocation preference.
206 unsigned getRegAllocPref(unsigned virtReg);
208 /// @brief returns true if VirtReg is assigned to its preferred physreg.
209 bool hasPreferredPhys(unsigned VirtReg) {
210 return getPhys(VirtReg) == getRegAllocPref(VirtReg);
213 /// @brief records virtReg is a split live interval from SReg.
214 void setIsSplitFromReg(unsigned virtReg, unsigned SReg) {
215 Virt2SplitMap[virtReg] = SReg;
218 /// @brief returns the live interval virtReg is split from.
219 unsigned getPreSplitReg(unsigned virtReg) const {
220 return Virt2SplitMap[virtReg];
223 /// getOriginal - Return the original virtual register that VirtReg descends
224 /// from through splitting.
225 /// A register that was not created by splitting is its own original.
226 /// This operation is idempotent.
227 unsigned getOriginal(unsigned VirtReg) const {
228 unsigned Orig = getPreSplitReg(VirtReg);
229 return Orig ? Orig : VirtReg;
232 /// @brief returns true if the specified virtual register is not
233 /// mapped to a stack slot or rematerialized.
234 bool isAssignedReg(unsigned virtReg) const {
235 if (getStackSlot(virtReg) == NO_STACK_SLOT &&
236 getReMatId(virtReg) == NO_STACK_SLOT)
238 // Split register can be assigned a physical register as well as a
239 // stack slot or remat id.
240 return (Virt2SplitMap[virtReg] && Virt2PhysMap[virtReg] != NO_PHYS_REG);
243 /// @brief returns the stack slot mapped to the specified virtual
245 int getStackSlot(unsigned virtReg) const {
246 assert(TargetRegisterInfo::isVirtualRegister(virtReg));
247 return Virt2StackSlotMap[virtReg];
250 /// @brief returns the rematerialization id mapped to the specified virtual
252 int getReMatId(unsigned virtReg) const {
253 assert(TargetRegisterInfo::isVirtualRegister(virtReg));
254 return Virt2ReMatIdMap[virtReg];
257 /// @brief create a mapping for the specifed virtual register to
258 /// the next available stack slot
259 int assignVirt2StackSlot(unsigned virtReg);
260 /// @brief create a mapping for the specified virtual register to
261 /// the specified stack slot
262 void assignVirt2StackSlot(unsigned virtReg, int frameIndex);
264 /// @brief assign an unique re-materialization id to the specified
265 /// virtual register.
266 int assignVirtReMatId(unsigned virtReg);
267 /// @brief assign an unique re-materialization id to the specified
268 /// virtual register.
269 void assignVirtReMatId(unsigned virtReg, int id);
271 /// @brief returns true if the specified virtual register is being
273 bool isReMaterialized(unsigned virtReg) const {
274 return ReMatMap[virtReg] != NULL;
277 /// @brief returns the original machine instruction being re-issued
278 /// to re-materialize the specified virtual register.
279 MachineInstr *getReMaterializedMI(unsigned virtReg) const {
280 return ReMatMap[virtReg];
283 /// @brief records the specified virtual register will be
284 /// re-materialized and the original instruction which will be re-issed
285 /// for this purpose. If parameter all is true, then all uses of the
286 /// registers are rematerialized and it's safe to delete the definition.
287 void setVirtIsReMaterialized(unsigned virtReg, MachineInstr *def) {
288 ReMatMap[virtReg] = def;
291 /// @brief record the last use (kill) of a split virtual register.
292 void addKillPoint(unsigned virtReg, SlotIndex index) {
293 Virt2SplitKillMap[virtReg] = index;
296 SlotIndex getKillPoint(unsigned virtReg) const {
297 return Virt2SplitKillMap[virtReg];
300 /// @brief remove the last use (kill) of a split virtual register.
301 void removeKillPoint(unsigned virtReg) {
302 Virt2SplitKillMap[virtReg] = SlotIndex();
305 /// @brief returns true if the specified MachineInstr is a spill point.
306 bool isSpillPt(MachineInstr *Pt) const {
307 return SpillPt2VirtMap.find(Pt) != SpillPt2VirtMap.end();
310 /// @brief returns the virtual registers that should be spilled due to
311 /// splitting right after the specified MachineInstr.
312 std::vector<std::pair<unsigned,bool> > &getSpillPtSpills(MachineInstr *Pt) {
313 return SpillPt2VirtMap[Pt];
316 /// @brief records the specified MachineInstr as a spill point for virtReg.
317 void addSpillPoint(unsigned virtReg, bool isKill, MachineInstr *Pt) {
318 std::map<MachineInstr*, std::vector<std::pair<unsigned,bool> > >::iterator
319 I = SpillPt2VirtMap.find(Pt);
320 if (I != SpillPt2VirtMap.end())
321 I->second.push_back(std::make_pair(virtReg, isKill));
323 std::vector<std::pair<unsigned,bool> > Virts;
324 Virts.push_back(std::make_pair(virtReg, isKill));
325 SpillPt2VirtMap.insert(std::make_pair(Pt, Virts));
329 /// @brief - transfer spill point information from one instruction to
331 void transferSpillPts(MachineInstr *Old, MachineInstr *New) {
332 std::map<MachineInstr*, std::vector<std::pair<unsigned,bool> > >::iterator
333 I = SpillPt2VirtMap.find(Old);
334 if (I == SpillPt2VirtMap.end())
336 while (!I->second.empty()) {
337 unsigned virtReg = I->second.back().first;
338 bool isKill = I->second.back().second;
339 I->second.pop_back();
340 addSpillPoint(virtReg, isKill, New);
342 SpillPt2VirtMap.erase(I);
345 /// @brief returns true if the specified MachineInstr is a restore point.
346 bool isRestorePt(MachineInstr *Pt) const {
347 return RestorePt2VirtMap.find(Pt) != RestorePt2VirtMap.end();
350 /// @brief returns the virtual registers that should be restoreed due to
351 /// splitting right after the specified MachineInstr.
352 std::vector<unsigned> &getRestorePtRestores(MachineInstr *Pt) {
353 return RestorePt2VirtMap[Pt];
356 /// @brief records the specified MachineInstr as a restore point for virtReg.
357 void addRestorePoint(unsigned virtReg, MachineInstr *Pt) {
358 std::map<MachineInstr*, std::vector<unsigned> >::iterator I =
359 RestorePt2VirtMap.find(Pt);
360 if (I != RestorePt2VirtMap.end())
361 I->second.push_back(virtReg);
363 std::vector<unsigned> Virts;
364 Virts.push_back(virtReg);
365 RestorePt2VirtMap.insert(std::make_pair(Pt, Virts));
369 /// @brief - transfer restore point information from one instruction to
371 void transferRestorePts(MachineInstr *Old, MachineInstr *New) {
372 std::map<MachineInstr*, std::vector<unsigned> >::iterator I =
373 RestorePt2VirtMap.find(Old);
374 if (I == RestorePt2VirtMap.end())
376 while (!I->second.empty()) {
377 unsigned virtReg = I->second.back();
378 I->second.pop_back();
379 addRestorePoint(virtReg, New);
381 RestorePt2VirtMap.erase(I);
384 /// @brief records that the specified physical register must be spilled
385 /// around the specified machine instr.
386 void addEmergencySpill(unsigned PhysReg, MachineInstr *MI) {
387 if (EmergencySpillMap.find(MI) != EmergencySpillMap.end())
388 EmergencySpillMap[MI].push_back(PhysReg);
390 std::vector<unsigned> PhysRegs;
391 PhysRegs.push_back(PhysReg);
392 EmergencySpillMap.insert(std::make_pair(MI, PhysRegs));
396 /// @brief returns true if one or more physical registers must be spilled
397 /// around the specified instruction.
398 bool hasEmergencySpills(MachineInstr *MI) const {
399 return EmergencySpillMap.find(MI) != EmergencySpillMap.end();
402 /// @brief returns the physical registers to be spilled and restored around
404 std::vector<unsigned> &getEmergencySpills(MachineInstr *MI) {
405 return EmergencySpillMap[MI];
408 /// @brief - transfer emergency spill information from one instruction to
410 void transferEmergencySpills(MachineInstr *Old, MachineInstr *New) {
411 std::map<MachineInstr*,std::vector<unsigned> >::iterator I =
412 EmergencySpillMap.find(Old);
413 if (I == EmergencySpillMap.end())
415 while (!I->second.empty()) {
416 unsigned virtReg = I->second.back();
417 I->second.pop_back();
418 addEmergencySpill(virtReg, New);
420 EmergencySpillMap.erase(I);
423 /// @brief return or get a emergency spill slot for the register class.
424 int getEmergencySpillSlot(const TargetRegisterClass *RC);
426 /// @brief Return lowest spill slot index.
427 int getLowSpillSlot() const {
431 /// @brief Return highest spill slot index.
432 int getHighSpillSlot() const {
433 return HighSpillSlot;
436 /// @brief Records a spill slot use.
437 void addSpillSlotUse(int FrameIndex, MachineInstr *MI);
439 /// @brief Returns true if spill slot has been used.
440 bool isSpillSlotUsed(int FrameIndex) const {
441 assert(FrameIndex >= 0 && "Spill slot index should not be negative!");
442 return !SpillSlotToUsesMap[FrameIndex-LowSpillSlot].empty();
445 /// @brief Mark the specified register as being implicitly defined.
446 void setIsImplicitlyDefined(unsigned VirtReg) {
447 ImplicitDefed.set(TargetRegisterInfo::virtReg2Index(VirtReg));
450 /// @brief Returns true if the virtual register is implicitly defined.
451 bool isImplicitlyDefined(unsigned VirtReg) const {
452 return ImplicitDefed[TargetRegisterInfo::virtReg2Index(VirtReg)];
455 /// @brief Updates information about the specified virtual register's value
456 /// folded into newMI machine instruction.
457 void virtFolded(unsigned VirtReg, MachineInstr *OldMI, MachineInstr *NewMI,
460 /// @brief Updates information about the specified virtual register's value
461 /// folded into the specified machine instruction.
462 void virtFolded(unsigned VirtReg, MachineInstr *MI, ModRef MRInfo);
464 /// @brief returns the virtual registers' values folded in memory
465 /// operands of this instruction
466 std::pair<MI2VirtMapTy::const_iterator, MI2VirtMapTy::const_iterator>
467 getFoldedVirts(MachineInstr* MI) const {
468 return MI2VirtMap.equal_range(MI);
471 /// RemoveMachineInstrFromMaps - MI is being erased, remove it from the
472 /// the folded instruction map and spill point map.
473 void RemoveMachineInstrFromMaps(MachineInstr *MI);
475 /// rewrite - Rewrite all instructions in MF to use only physical registers
476 /// by mapping all virtual register operands to their assigned physical
479 /// @param Indexes Optionally remove deleted instructions from indexes.
480 void rewrite(SlotIndexes *Indexes);
482 void print(raw_ostream &OS, const Module* M = 0) const;
486 inline raw_ostream &operator<<(raw_ostream &OS, const VirtRegMap &VRM) {
490 } // End llvm namespace