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
;
39 class VirtRegMap
: public MachineFunctionPass
{
43 NO_STACK_SLOT
= (1L << 30)-1,
44 MAX_STACK_SLOT
= (1L << 18)-1
47 enum ModRef
{ isRef
= 1, isMod
= 2, isModRef
= 3 };
48 typedef std::multimap
<MachineInstr
*,
49 std::pair
<unsigned, ModRef
> > MI2VirtMapTy
;
52 MachineRegisterInfo
*MRI
;
53 const TargetInstrInfo
*TII
;
54 const TargetRegisterInfo
*TRI
;
57 DenseMap
<const TargetRegisterClass
*, BitVector
> allocatableRCRegs
;
59 /// Virt2PhysMap - This is a virtual to physical register
60 /// mapping. Each virtual register is required to have an entry in
61 /// it; even spilled virtual registers (the register mapped to a
62 /// spilled register is the temporary used to load it from the
64 IndexedMap
<unsigned, VirtReg2IndexFunctor
> Virt2PhysMap
;
66 /// Virt2StackSlotMap - This is virtual register to stack slot
67 /// mapping. Each spilled virtual register has an entry in it
68 /// which corresponds to the stack slot this register is spilled
70 IndexedMap
<int, VirtReg2IndexFunctor
> Virt2StackSlotMap
;
72 /// Virt2ReMatIdMap - This is virtual register to rematerialization id
73 /// mapping. Each spilled virtual register that should be remat'd has an
74 /// entry in it which corresponds to the remat id.
75 IndexedMap
<int, VirtReg2IndexFunctor
> Virt2ReMatIdMap
;
77 /// Virt2SplitMap - This is virtual register to splitted virtual register
79 IndexedMap
<unsigned, VirtReg2IndexFunctor
> Virt2SplitMap
;
81 /// Virt2SplitKillMap - This is splitted virtual register to its last use
82 /// (kill) index mapping.
83 IndexedMap
<SlotIndex
, VirtReg2IndexFunctor
> Virt2SplitKillMap
;
85 /// ReMatMap - This is virtual register to re-materialized instruction
86 /// mapping. Each virtual register whose definition is going to be
87 /// re-materialized has an entry in it.
88 IndexedMap
<MachineInstr
*, VirtReg2IndexFunctor
> ReMatMap
;
90 /// MI2VirtMap - This is MachineInstr to virtual register
91 /// mapping. In the case of memory spill code being folded into
92 /// instructions, we need to know which virtual register was
93 /// read/written by this instruction.
94 MI2VirtMapTy MI2VirtMap
;
96 /// SpillPt2VirtMap - This records the virtual registers which should
97 /// be spilled right after the MachineInstr due to live interval
99 std::map
<MachineInstr
*, std::vector
<std::pair
<unsigned,bool> > >
102 /// RestorePt2VirtMap - This records the virtual registers which should
103 /// be restored right before the MachineInstr due to live interval
105 std::map
<MachineInstr
*, std::vector
<unsigned> > RestorePt2VirtMap
;
107 /// EmergencySpillMap - This records the physical registers that should
108 /// be spilled / restored around the MachineInstr since the register
109 /// allocator has run out of registers.
110 std::map
<MachineInstr
*, std::vector
<unsigned> > EmergencySpillMap
;
112 /// EmergencySpillSlots - This records emergency spill slots used to
113 /// spill physical registers when the register allocator runs out of
114 /// registers. Ideally only one stack slot is used per function per
116 std::map
<const TargetRegisterClass
*, int> EmergencySpillSlots
;
118 /// ReMatId - Instead of assigning a stack slot to a to be rematerialized
119 /// virtual register, an unique id is being assigned. This keeps track of
120 /// the highest id used so far. Note, this starts at (1<<18) to avoid
121 /// conflicts with stack slot numbers.
124 /// LowSpillSlot, HighSpillSlot - Lowest and highest spill slot indexes.
125 int LowSpillSlot
, HighSpillSlot
;
127 /// SpillSlotToUsesMap - Records uses for each register spill slot.
128 SmallVector
<SmallPtrSet
<MachineInstr
*, 4>, 8> SpillSlotToUsesMap
;
130 /// ImplicitDefed - One bit for each virtual register. If set it indicates
131 /// the register is implicitly defined.
132 BitVector ImplicitDefed
;
134 /// UnusedRegs - A list of physical registers that have not been used.
135 BitVector UnusedRegs
;
137 /// createSpillSlot - Allocate a spill slot for RC from MFI.
138 unsigned createSpillSlot(const TargetRegisterClass
*RC
);
140 VirtRegMap(const VirtRegMap
&); // DO NOT IMPLEMENT
141 void operator=(const VirtRegMap
&); // DO NOT IMPLEMENT
145 VirtRegMap() : MachineFunctionPass(ID
), Virt2PhysMap(NO_PHYS_REG
),
146 Virt2StackSlotMap(NO_STACK_SLOT
),
147 Virt2ReMatIdMap(NO_STACK_SLOT
), Virt2SplitMap(0),
148 Virt2SplitKillMap(SlotIndex()), ReMatMap(NULL
),
149 ReMatId(MAX_STACK_SLOT
+1),
150 LowSpillSlot(NO_STACK_SLOT
), HighSpillSlot(NO_STACK_SLOT
) { }
151 virtual bool runOnMachineFunction(MachineFunction
&MF
);
153 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const {
154 AU
.setPreservesAll();
155 MachineFunctionPass::getAnalysisUsage(AU
);
158 MachineFunction
&getMachineFunction() const {
159 assert(MF
&& "getMachineFunction called before runOnMachineFunction");
163 MachineRegisterInfo
&getRegInfo() const { return *MRI
; }
164 const TargetRegisterInfo
&getTargetRegInfo() const { return *TRI
; }
168 /// @brief returns true if the specified virtual register is
169 /// mapped to a physical register
170 bool hasPhys(unsigned virtReg
) const {
171 return getPhys(virtReg
) != NO_PHYS_REG
;
174 /// @brief returns the physical register mapped to the specified
176 unsigned getPhys(unsigned virtReg
) const {
177 assert(TargetRegisterInfo::isVirtualRegister(virtReg
));
178 return Virt2PhysMap
[virtReg
];
181 /// @brief creates a mapping for the specified virtual register to
182 /// the specified physical register
183 void assignVirt2Phys(unsigned virtReg
, unsigned physReg
) {
184 assert(TargetRegisterInfo::isVirtualRegister(virtReg
) &&
185 TargetRegisterInfo::isPhysicalRegister(physReg
));
186 assert(Virt2PhysMap
[virtReg
] == NO_PHYS_REG
&&
187 "attempt to assign physical register to already mapped "
189 Virt2PhysMap
[virtReg
] = physReg
;
192 /// @brief clears the specified virtual register's, physical
194 void clearVirt(unsigned virtReg
) {
195 assert(TargetRegisterInfo::isVirtualRegister(virtReg
));
196 assert(Virt2PhysMap
[virtReg
] != NO_PHYS_REG
&&
197 "attempt to clear a not assigned virtual register");
198 Virt2PhysMap
[virtReg
] = NO_PHYS_REG
;
201 /// @brief clears all virtual to physical register mappings
202 void clearAllVirt() {
203 Virt2PhysMap
.clear();
207 /// @brief returns the register allocation preference.
208 unsigned getRegAllocPref(unsigned virtReg
);
210 /// @brief records virtReg is a split live interval from SReg.
211 void setIsSplitFromReg(unsigned virtReg
, unsigned SReg
) {
212 Virt2SplitMap
[virtReg
] = SReg
;
215 /// @brief returns the live interval virtReg is split from.
216 unsigned getPreSplitReg(unsigned virtReg
) {
217 return Virt2SplitMap
[virtReg
];
220 /// @brief returns true if the specified virtual register is not
221 /// mapped to a stack slot or rematerialized.
222 bool isAssignedReg(unsigned virtReg
) const {
223 if (getStackSlot(virtReg
) == NO_STACK_SLOT
&&
224 getReMatId(virtReg
) == NO_STACK_SLOT
)
226 // Split register can be assigned a physical register as well as a
227 // stack slot or remat id.
228 return (Virt2SplitMap
[virtReg
] && Virt2PhysMap
[virtReg
] != NO_PHYS_REG
);
231 /// @brief returns the stack slot mapped to the specified virtual
233 int getStackSlot(unsigned virtReg
) const {
234 assert(TargetRegisterInfo::isVirtualRegister(virtReg
));
235 return Virt2StackSlotMap
[virtReg
];
238 /// @brief returns the rematerialization id mapped to the specified virtual
240 int getReMatId(unsigned virtReg
) const {
241 assert(TargetRegisterInfo::isVirtualRegister(virtReg
));
242 return Virt2ReMatIdMap
[virtReg
];
245 /// @brief create a mapping for the specifed virtual register to
246 /// the next available stack slot
247 int assignVirt2StackSlot(unsigned virtReg
);
248 /// @brief create a mapping for the specified virtual register to
249 /// the specified stack slot
250 void assignVirt2StackSlot(unsigned virtReg
, int frameIndex
);
252 /// @brief assign an unique re-materialization id to the specified
253 /// virtual register.
254 int assignVirtReMatId(unsigned virtReg
);
255 /// @brief assign an unique re-materialization id to the specified
256 /// virtual register.
257 void assignVirtReMatId(unsigned virtReg
, int id
);
259 /// @brief returns true if the specified virtual register is being
261 bool isReMaterialized(unsigned virtReg
) const {
262 return ReMatMap
[virtReg
] != NULL
;
265 /// @brief returns the original machine instruction being re-issued
266 /// to re-materialize the specified virtual register.
267 MachineInstr
*getReMaterializedMI(unsigned virtReg
) const {
268 return ReMatMap
[virtReg
];
271 /// @brief records the specified virtual register will be
272 /// re-materialized and the original instruction which will be re-issed
273 /// for this purpose. If parameter all is true, then all uses of the
274 /// registers are rematerialized and it's safe to delete the definition.
275 void setVirtIsReMaterialized(unsigned virtReg
, MachineInstr
*def
) {
276 ReMatMap
[virtReg
] = def
;
279 /// @brief record the last use (kill) of a split virtual register.
280 void addKillPoint(unsigned virtReg
, SlotIndex index
) {
281 Virt2SplitKillMap
[virtReg
] = index
;
284 SlotIndex
getKillPoint(unsigned virtReg
) const {
285 return Virt2SplitKillMap
[virtReg
];
288 /// @brief remove the last use (kill) of a split virtual register.
289 void removeKillPoint(unsigned virtReg
) {
290 Virt2SplitKillMap
[virtReg
] = SlotIndex();
293 /// @brief returns true if the specified MachineInstr is a spill point.
294 bool isSpillPt(MachineInstr
*Pt
) const {
295 return SpillPt2VirtMap
.find(Pt
) != SpillPt2VirtMap
.end();
298 /// @brief returns the virtual registers that should be spilled due to
299 /// splitting right after the specified MachineInstr.
300 std::vector
<std::pair
<unsigned,bool> > &getSpillPtSpills(MachineInstr
*Pt
) {
301 return SpillPt2VirtMap
[Pt
];
304 /// @brief records the specified MachineInstr as a spill point for virtReg.
305 void addSpillPoint(unsigned virtReg
, bool isKill
, MachineInstr
*Pt
) {
306 std::map
<MachineInstr
*, std::vector
<std::pair
<unsigned,bool> > >::iterator
307 I
= SpillPt2VirtMap
.find(Pt
);
308 if (I
!= SpillPt2VirtMap
.end())
309 I
->second
.push_back(std::make_pair(virtReg
, isKill
));
311 std::vector
<std::pair
<unsigned,bool> > Virts
;
312 Virts
.push_back(std::make_pair(virtReg
, isKill
));
313 SpillPt2VirtMap
.insert(std::make_pair(Pt
, Virts
));
317 /// @brief - transfer spill point information from one instruction to
319 void transferSpillPts(MachineInstr
*Old
, MachineInstr
*New
) {
320 std::map
<MachineInstr
*, std::vector
<std::pair
<unsigned,bool> > >::iterator
321 I
= SpillPt2VirtMap
.find(Old
);
322 if (I
== SpillPt2VirtMap
.end())
324 while (!I
->second
.empty()) {
325 unsigned virtReg
= I
->second
.back().first
;
326 bool isKill
= I
->second
.back().second
;
327 I
->second
.pop_back();
328 addSpillPoint(virtReg
, isKill
, New
);
330 SpillPt2VirtMap
.erase(I
);
333 /// @brief returns true if the specified MachineInstr is a restore point.
334 bool isRestorePt(MachineInstr
*Pt
) const {
335 return RestorePt2VirtMap
.find(Pt
) != RestorePt2VirtMap
.end();
338 /// @brief returns the virtual registers that should be restoreed due to
339 /// splitting right after the specified MachineInstr.
340 std::vector
<unsigned> &getRestorePtRestores(MachineInstr
*Pt
) {
341 return RestorePt2VirtMap
[Pt
];
344 /// @brief records the specified MachineInstr as a restore point for virtReg.
345 void addRestorePoint(unsigned virtReg
, MachineInstr
*Pt
) {
346 std::map
<MachineInstr
*, std::vector
<unsigned> >::iterator I
=
347 RestorePt2VirtMap
.find(Pt
);
348 if (I
!= RestorePt2VirtMap
.end())
349 I
->second
.push_back(virtReg
);
351 std::vector
<unsigned> Virts
;
352 Virts
.push_back(virtReg
);
353 RestorePt2VirtMap
.insert(std::make_pair(Pt
, Virts
));
357 /// @brief - transfer restore point information from one instruction to
359 void transferRestorePts(MachineInstr
*Old
, MachineInstr
*New
) {
360 std::map
<MachineInstr
*, std::vector
<unsigned> >::iterator I
=
361 RestorePt2VirtMap
.find(Old
);
362 if (I
== RestorePt2VirtMap
.end())
364 while (!I
->second
.empty()) {
365 unsigned virtReg
= I
->second
.back();
366 I
->second
.pop_back();
367 addRestorePoint(virtReg
, New
);
369 RestorePt2VirtMap
.erase(I
);
372 /// @brief records that the specified physical register must be spilled
373 /// around the specified machine instr.
374 void addEmergencySpill(unsigned PhysReg
, MachineInstr
*MI
) {
375 if (EmergencySpillMap
.find(MI
) != EmergencySpillMap
.end())
376 EmergencySpillMap
[MI
].push_back(PhysReg
);
378 std::vector
<unsigned> PhysRegs
;
379 PhysRegs
.push_back(PhysReg
);
380 EmergencySpillMap
.insert(std::make_pair(MI
, PhysRegs
));
384 /// @brief returns true if one or more physical registers must be spilled
385 /// around the specified instruction.
386 bool hasEmergencySpills(MachineInstr
*MI
) const {
387 return EmergencySpillMap
.find(MI
) != EmergencySpillMap
.end();
390 /// @brief returns the physical registers to be spilled and restored around
392 std::vector
<unsigned> &getEmergencySpills(MachineInstr
*MI
) {
393 return EmergencySpillMap
[MI
];
396 /// @brief - transfer emergency spill information from one instruction to
398 void transferEmergencySpills(MachineInstr
*Old
, MachineInstr
*New
) {
399 std::map
<MachineInstr
*,std::vector
<unsigned> >::iterator I
=
400 EmergencySpillMap
.find(Old
);
401 if (I
== EmergencySpillMap
.end())
403 while (!I
->second
.empty()) {
404 unsigned virtReg
= I
->second
.back();
405 I
->second
.pop_back();
406 addEmergencySpill(virtReg
, New
);
408 EmergencySpillMap
.erase(I
);
411 /// @brief return or get a emergency spill slot for the register class.
412 int getEmergencySpillSlot(const TargetRegisterClass
*RC
);
414 /// @brief Return lowest spill slot index.
415 int getLowSpillSlot() const {
419 /// @brief Return highest spill slot index.
420 int getHighSpillSlot() const {
421 return HighSpillSlot
;
424 /// @brief Records a spill slot use.
425 void addSpillSlotUse(int FrameIndex
, MachineInstr
*MI
);
427 /// @brief Returns true if spill slot has been used.
428 bool isSpillSlotUsed(int FrameIndex
) const {
429 assert(FrameIndex
>= 0 && "Spill slot index should not be negative!");
430 return !SpillSlotToUsesMap
[FrameIndex
-LowSpillSlot
].empty();
433 /// @brief Mark the specified register as being implicitly defined.
434 void setIsImplicitlyDefined(unsigned VirtReg
) {
435 ImplicitDefed
.set(TargetRegisterInfo::virtReg2Index(VirtReg
));
438 /// @brief Returns true if the virtual register is implicitly defined.
439 bool isImplicitlyDefined(unsigned VirtReg
) const {
440 return ImplicitDefed
[TargetRegisterInfo::virtReg2Index(VirtReg
)];
443 /// @brief Updates information about the specified virtual register's value
444 /// folded into newMI machine instruction.
445 void virtFolded(unsigned VirtReg
, MachineInstr
*OldMI
, MachineInstr
*NewMI
,
448 /// @brief Updates information about the specified virtual register's value
449 /// folded into the specified machine instruction.
450 void virtFolded(unsigned VirtReg
, MachineInstr
*MI
, ModRef MRInfo
);
452 /// @brief returns the virtual registers' values folded in memory
453 /// operands of this instruction
454 std::pair
<MI2VirtMapTy::const_iterator
, MI2VirtMapTy::const_iterator
>
455 getFoldedVirts(MachineInstr
* MI
) const {
456 return MI2VirtMap
.equal_range(MI
);
459 /// RemoveMachineInstrFromMaps - MI is being erased, remove it from the
460 /// the folded instruction map and spill point map.
461 void RemoveMachineInstrFromMaps(MachineInstr
*MI
);
463 /// FindUnusedRegisters - Gather a list of allocatable registers that
464 /// have not been allocated to any virtual register.
465 bool FindUnusedRegisters(LiveIntervals
* LIs
);
467 /// HasUnusedRegisters - Return true if there are any allocatable registers
468 /// that have not been allocated to any virtual register.
469 bool HasUnusedRegisters() const {
470 return !UnusedRegs
.none();
473 /// setRegisterUsed - Remember the physical register is now used.
474 void setRegisterUsed(unsigned Reg
) {
475 UnusedRegs
.reset(Reg
);
478 /// isRegisterUnused - Return true if the physical register has not been
480 bool isRegisterUnused(unsigned Reg
) const {
481 return UnusedRegs
[Reg
];
484 /// getFirstUnusedRegister - Return the first physical register that has not
486 unsigned getFirstUnusedRegister(const TargetRegisterClass
*RC
) {
487 int Reg
= UnusedRegs
.find_first();
489 if (allocatableRCRegs
[RC
][Reg
])
490 return (unsigned)Reg
;
491 Reg
= UnusedRegs
.find_next(Reg
);
496 void print(raw_ostream
&OS
, const Module
* M
= 0) const;
500 inline raw_ostream
&operator<<(raw_ostream
&OS
, const VirtRegMap
&VRM
) {
504 } // End llvm namespace