• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===-- llvm/CodeGen/VirtRegMap.h - Virtual Register Map -*- C++ -*--------===//
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 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.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #ifndef LLVM_CODEGEN_VIRTREGMAP_H
18 #define LLVM_CODEGEN_VIRTREGMAP_H
19 
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"
28 #include <map>
29 
30 namespace llvm {
31   class LiveIntervals;
32   class MachineInstr;
33   class MachineFunction;
34   class MachineRegisterInfo;
35   class TargetInstrInfo;
36   class TargetRegisterInfo;
37   class raw_ostream;
38   class SlotIndexes;
39 
40   class VirtRegMap : public MachineFunctionPass {
41   public:
42     enum {
43       NO_PHYS_REG = 0,
44       NO_STACK_SLOT = (1L << 30)-1,
45       MAX_STACK_SLOT = (1L << 18)-1
46     };
47 
48     enum ModRef { isRef = 1, isMod = 2, isModRef = 3 };
49     typedef std::multimap<MachineInstr*,
50                           std::pair<unsigned, ModRef> > MI2VirtMapTy;
51 
52   private:
53     MachineRegisterInfo *MRI;
54     const TargetInstrInfo *TII;
55     const TargetRegisterInfo *TRI;
56     MachineFunction *MF;
57 
58     DenseMap<const TargetRegisterClass*, BitVector> allocatableRCRegs;
59 
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
64     /// stack).
65     IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2PhysMap;
66 
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
70     /// at.
71     IndexedMap<int, VirtReg2IndexFunctor> Virt2StackSlotMap;
72 
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;
77 
78     /// Virt2SplitMap - This is virtual register to splitted virtual register
79     /// mapping.
80     IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2SplitMap;
81 
82     /// Virt2SplitKillMap - This is splitted virtual register to its last use
83     /// (kill) index mapping.
84     IndexedMap<SlotIndex, VirtReg2IndexFunctor> Virt2SplitKillMap;
85 
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;
90 
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;
96 
97     /// SpillPt2VirtMap - This records the virtual registers which should
98     /// be spilled right after the MachineInstr due to live interval
99     /// splitting.
100     std::map<MachineInstr*, std::vector<std::pair<unsigned,bool> > >
101     SpillPt2VirtMap;
102 
103     /// RestorePt2VirtMap - This records the virtual registers which should
104     /// be restored right before the MachineInstr due to live interval
105     /// splitting.
106     std::map<MachineInstr*, std::vector<unsigned> > RestorePt2VirtMap;
107 
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;
112 
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
116     /// register class.
117     std::map<const TargetRegisterClass*, int> EmergencySpillSlots;
118 
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.
123     int ReMatId;
124 
125     /// LowSpillSlot, HighSpillSlot - Lowest and highest spill slot indexes.
126     int LowSpillSlot, HighSpillSlot;
127 
128     /// SpillSlotToUsesMap - Records uses for each register spill slot.
129     SmallVector<SmallPtrSet<MachineInstr*, 4>, 8> SpillSlotToUsesMap;
130 
131     /// ImplicitDefed - One bit for each virtual register. If set it indicates
132     /// the register is implicitly defined.
133     BitVector ImplicitDefed;
134 
135     /// UnusedRegs - A list of physical registers that have not been used.
136     BitVector UnusedRegs;
137 
138     /// createSpillSlot - Allocate a spill slot for RC from MFI.
139     unsigned createSpillSlot(const TargetRegisterClass *RC);
140 
141     VirtRegMap(const VirtRegMap&);     // DO NOT IMPLEMENT
142     void operator=(const VirtRegMap&); // DO NOT IMPLEMENT
143 
144   public:
145     static char ID;
VirtRegMap()146     VirtRegMap() : MachineFunctionPass(ID), Virt2PhysMap(NO_PHYS_REG),
147                    Virt2StackSlotMap(NO_STACK_SLOT),
148                    Virt2ReMatIdMap(NO_STACK_SLOT), Virt2SplitMap(0),
149                    Virt2SplitKillMap(SlotIndex()), ReMatMap(NULL),
150                    ReMatId(MAX_STACK_SLOT+1),
151                    LowSpillSlot(NO_STACK_SLOT), HighSpillSlot(NO_STACK_SLOT) { }
152     virtual bool runOnMachineFunction(MachineFunction &MF);
153 
getAnalysisUsage(AnalysisUsage & AU)154     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
155       AU.setPreservesAll();
156       MachineFunctionPass::getAnalysisUsage(AU);
157     }
158 
getMachineFunction()159     MachineFunction &getMachineFunction() const {
160       assert(MF && "getMachineFunction called before runOnMachineFunction");
161       return *MF;
162     }
163 
getRegInfo()164     MachineRegisterInfo &getRegInfo() const { return *MRI; }
getTargetRegInfo()165     const TargetRegisterInfo &getTargetRegInfo() const { return *TRI; }
166 
167     void grow();
168 
169     /// @brief returns true if the specified virtual register is
170     /// mapped to a physical register
hasPhys(unsigned virtReg)171     bool hasPhys(unsigned virtReg) const {
172       return getPhys(virtReg) != NO_PHYS_REG;
173     }
174 
175     /// @brief returns the physical register mapped to the specified
176     /// virtual register
getPhys(unsigned virtReg)177     unsigned getPhys(unsigned virtReg) const {
178       assert(TargetRegisterInfo::isVirtualRegister(virtReg));
179       return Virt2PhysMap[virtReg];
180     }
181 
182     /// @brief creates a mapping for the specified virtual register to
183     /// the specified physical register
assignVirt2Phys(unsigned virtReg,unsigned physReg)184     void assignVirt2Phys(unsigned virtReg, unsigned physReg) {
185       assert(TargetRegisterInfo::isVirtualRegister(virtReg) &&
186              TargetRegisterInfo::isPhysicalRegister(physReg));
187       assert(Virt2PhysMap[virtReg] == NO_PHYS_REG &&
188              "attempt to assign physical register to already mapped "
189              "virtual register");
190       Virt2PhysMap[virtReg] = physReg;
191     }
192 
193     /// @brief clears the specified virtual register's, physical
194     /// register mapping
clearVirt(unsigned virtReg)195     void clearVirt(unsigned virtReg) {
196       assert(TargetRegisterInfo::isVirtualRegister(virtReg));
197       assert(Virt2PhysMap[virtReg] != NO_PHYS_REG &&
198              "attempt to clear a not assigned virtual register");
199       Virt2PhysMap[virtReg] = NO_PHYS_REG;
200     }
201 
202     /// @brief clears all virtual to physical register mappings
clearAllVirt()203     void clearAllVirt() {
204       Virt2PhysMap.clear();
205       grow();
206     }
207 
208     /// @brief returns the register allocation preference.
209     unsigned getRegAllocPref(unsigned virtReg);
210 
211     /// @brief returns true if VirtReg is assigned to its preferred physreg.
hasPreferredPhys(unsigned VirtReg)212     bool hasPreferredPhys(unsigned VirtReg) {
213       return getPhys(VirtReg) == getRegAllocPref(VirtReg);
214     }
215 
216     /// @brief records virtReg is a split live interval from SReg.
setIsSplitFromReg(unsigned virtReg,unsigned SReg)217     void setIsSplitFromReg(unsigned virtReg, unsigned SReg) {
218       Virt2SplitMap[virtReg] = SReg;
219     }
220 
221     /// @brief returns the live interval virtReg is split from.
getPreSplitReg(unsigned virtReg)222     unsigned getPreSplitReg(unsigned virtReg) const {
223       return Virt2SplitMap[virtReg];
224     }
225 
226     /// getOriginal - Return the original virtual register that VirtReg descends
227     /// from through splitting.
228     /// A register that was not created by splitting is its own original.
229     /// This operation is idempotent.
getOriginal(unsigned VirtReg)230     unsigned getOriginal(unsigned VirtReg) const {
231       unsigned Orig = getPreSplitReg(VirtReg);
232       return Orig ? Orig : VirtReg;
233     }
234 
235     /// @brief returns true if the specified virtual register is not
236     /// mapped to a stack slot or rematerialized.
isAssignedReg(unsigned virtReg)237     bool isAssignedReg(unsigned virtReg) const {
238       if (getStackSlot(virtReg) == NO_STACK_SLOT &&
239           getReMatId(virtReg) == NO_STACK_SLOT)
240         return true;
241       // Split register can be assigned a physical register as well as a
242       // stack slot or remat id.
243       return (Virt2SplitMap[virtReg] && Virt2PhysMap[virtReg] != NO_PHYS_REG);
244     }
245 
246     /// @brief returns the stack slot mapped to the specified virtual
247     /// register
getStackSlot(unsigned virtReg)248     int getStackSlot(unsigned virtReg) const {
249       assert(TargetRegisterInfo::isVirtualRegister(virtReg));
250       return Virt2StackSlotMap[virtReg];
251     }
252 
253     /// @brief returns the rematerialization id mapped to the specified virtual
254     /// register
getReMatId(unsigned virtReg)255     int getReMatId(unsigned virtReg) const {
256       assert(TargetRegisterInfo::isVirtualRegister(virtReg));
257       return Virt2ReMatIdMap[virtReg];
258     }
259 
260     /// @brief create a mapping for the specifed virtual register to
261     /// the next available stack slot
262     int assignVirt2StackSlot(unsigned virtReg);
263     /// @brief create a mapping for the specified virtual register to
264     /// the specified stack slot
265     void assignVirt2StackSlot(unsigned virtReg, int frameIndex);
266 
267     /// @brief assign an unique re-materialization id to the specified
268     /// virtual register.
269     int assignVirtReMatId(unsigned virtReg);
270     /// @brief assign an unique re-materialization id to the specified
271     /// virtual register.
272     void assignVirtReMatId(unsigned virtReg, int id);
273 
274     /// @brief returns true if the specified virtual register is being
275     /// re-materialized.
isReMaterialized(unsigned virtReg)276     bool isReMaterialized(unsigned virtReg) const {
277       return ReMatMap[virtReg] != NULL;
278     }
279 
280     /// @brief returns the original machine instruction being re-issued
281     /// to re-materialize the specified virtual register.
getReMaterializedMI(unsigned virtReg)282     MachineInstr *getReMaterializedMI(unsigned virtReg) const {
283       return ReMatMap[virtReg];
284     }
285 
286     /// @brief records the specified virtual register will be
287     /// re-materialized and the original instruction which will be re-issed
288     /// for this purpose.  If parameter all is true, then all uses of the
289     /// registers are rematerialized and it's safe to delete the definition.
setVirtIsReMaterialized(unsigned virtReg,MachineInstr * def)290     void setVirtIsReMaterialized(unsigned virtReg, MachineInstr *def) {
291       ReMatMap[virtReg] = def;
292     }
293 
294     /// @brief record the last use (kill) of a split virtual register.
addKillPoint(unsigned virtReg,SlotIndex index)295     void addKillPoint(unsigned virtReg, SlotIndex index) {
296       Virt2SplitKillMap[virtReg] = index;
297     }
298 
getKillPoint(unsigned virtReg)299     SlotIndex getKillPoint(unsigned virtReg) const {
300       return Virt2SplitKillMap[virtReg];
301     }
302 
303     /// @brief remove the last use (kill) of a split virtual register.
removeKillPoint(unsigned virtReg)304     void removeKillPoint(unsigned virtReg) {
305       Virt2SplitKillMap[virtReg] = SlotIndex();
306     }
307 
308     /// @brief returns true if the specified MachineInstr is a spill point.
isSpillPt(MachineInstr * Pt)309     bool isSpillPt(MachineInstr *Pt) const {
310       return SpillPt2VirtMap.find(Pt) != SpillPt2VirtMap.end();
311     }
312 
313     /// @brief returns the virtual registers that should be spilled due to
314     /// splitting right after the specified MachineInstr.
getSpillPtSpills(MachineInstr * Pt)315     std::vector<std::pair<unsigned,bool> > &getSpillPtSpills(MachineInstr *Pt) {
316       return SpillPt2VirtMap[Pt];
317     }
318 
319     /// @brief records the specified MachineInstr as a spill point for virtReg.
addSpillPoint(unsigned virtReg,bool isKill,MachineInstr * Pt)320     void addSpillPoint(unsigned virtReg, bool isKill, MachineInstr *Pt) {
321       std::map<MachineInstr*, std::vector<std::pair<unsigned,bool> > >::iterator
322         I = SpillPt2VirtMap.find(Pt);
323       if (I != SpillPt2VirtMap.end())
324         I->second.push_back(std::make_pair(virtReg, isKill));
325       else {
326         std::vector<std::pair<unsigned,bool> > Virts;
327         Virts.push_back(std::make_pair(virtReg, isKill));
328         SpillPt2VirtMap.insert(std::make_pair(Pt, Virts));
329       }
330     }
331 
332     /// @brief - transfer spill point information from one instruction to
333     /// another.
transferSpillPts(MachineInstr * Old,MachineInstr * New)334     void transferSpillPts(MachineInstr *Old, MachineInstr *New) {
335       std::map<MachineInstr*, std::vector<std::pair<unsigned,bool> > >::iterator
336         I = SpillPt2VirtMap.find(Old);
337       if (I == SpillPt2VirtMap.end())
338         return;
339       while (!I->second.empty()) {
340         unsigned virtReg = I->second.back().first;
341         bool isKill = I->second.back().second;
342         I->second.pop_back();
343         addSpillPoint(virtReg, isKill, New);
344       }
345       SpillPt2VirtMap.erase(I);
346     }
347 
348     /// @brief returns true if the specified MachineInstr is a restore point.
isRestorePt(MachineInstr * Pt)349     bool isRestorePt(MachineInstr *Pt) const {
350       return RestorePt2VirtMap.find(Pt) != RestorePt2VirtMap.end();
351     }
352 
353     /// @brief returns the virtual registers that should be restoreed due to
354     /// splitting right after the specified MachineInstr.
getRestorePtRestores(MachineInstr * Pt)355     std::vector<unsigned> &getRestorePtRestores(MachineInstr *Pt) {
356       return RestorePt2VirtMap[Pt];
357     }
358 
359     /// @brief records the specified MachineInstr as a restore point for virtReg.
addRestorePoint(unsigned virtReg,MachineInstr * Pt)360     void addRestorePoint(unsigned virtReg, MachineInstr *Pt) {
361       std::map<MachineInstr*, std::vector<unsigned> >::iterator I =
362         RestorePt2VirtMap.find(Pt);
363       if (I != RestorePt2VirtMap.end())
364         I->second.push_back(virtReg);
365       else {
366         std::vector<unsigned> Virts;
367         Virts.push_back(virtReg);
368         RestorePt2VirtMap.insert(std::make_pair(Pt, Virts));
369       }
370     }
371 
372     /// @brief - transfer restore point information from one instruction to
373     /// another.
transferRestorePts(MachineInstr * Old,MachineInstr * New)374     void transferRestorePts(MachineInstr *Old, MachineInstr *New) {
375       std::map<MachineInstr*, std::vector<unsigned> >::iterator I =
376         RestorePt2VirtMap.find(Old);
377       if (I == RestorePt2VirtMap.end())
378         return;
379       while (!I->second.empty()) {
380         unsigned virtReg = I->second.back();
381         I->second.pop_back();
382         addRestorePoint(virtReg, New);
383       }
384       RestorePt2VirtMap.erase(I);
385     }
386 
387     /// @brief records that the specified physical register must be spilled
388     /// around the specified machine instr.
addEmergencySpill(unsigned PhysReg,MachineInstr * MI)389     void addEmergencySpill(unsigned PhysReg, MachineInstr *MI) {
390       if (EmergencySpillMap.find(MI) != EmergencySpillMap.end())
391         EmergencySpillMap[MI].push_back(PhysReg);
392       else {
393         std::vector<unsigned> PhysRegs;
394         PhysRegs.push_back(PhysReg);
395         EmergencySpillMap.insert(std::make_pair(MI, PhysRegs));
396       }
397     }
398 
399     /// @brief returns true if one or more physical registers must be spilled
400     /// around the specified instruction.
hasEmergencySpills(MachineInstr * MI)401     bool hasEmergencySpills(MachineInstr *MI) const {
402       return EmergencySpillMap.find(MI) != EmergencySpillMap.end();
403     }
404 
405     /// @brief returns the physical registers to be spilled and restored around
406     /// the instruction.
getEmergencySpills(MachineInstr * MI)407     std::vector<unsigned> &getEmergencySpills(MachineInstr *MI) {
408       return EmergencySpillMap[MI];
409     }
410 
411     /// @brief - transfer emergency spill information from one instruction to
412     /// another.
transferEmergencySpills(MachineInstr * Old,MachineInstr * New)413     void transferEmergencySpills(MachineInstr *Old, MachineInstr *New) {
414       std::map<MachineInstr*,std::vector<unsigned> >::iterator I =
415         EmergencySpillMap.find(Old);
416       if (I == EmergencySpillMap.end())
417         return;
418       while (!I->second.empty()) {
419         unsigned virtReg = I->second.back();
420         I->second.pop_back();
421         addEmergencySpill(virtReg, New);
422       }
423       EmergencySpillMap.erase(I);
424     }
425 
426     /// @brief return or get a emergency spill slot for the register class.
427     int getEmergencySpillSlot(const TargetRegisterClass *RC);
428 
429     /// @brief Return lowest spill slot index.
getLowSpillSlot()430     int getLowSpillSlot() const {
431       return LowSpillSlot;
432     }
433 
434     /// @brief Return highest spill slot index.
getHighSpillSlot()435     int getHighSpillSlot() const {
436       return HighSpillSlot;
437     }
438 
439     /// @brief Records a spill slot use.
440     void addSpillSlotUse(int FrameIndex, MachineInstr *MI);
441 
442     /// @brief Returns true if spill slot has been used.
isSpillSlotUsed(int FrameIndex)443     bool isSpillSlotUsed(int FrameIndex) const {
444       assert(FrameIndex >= 0 && "Spill slot index should not be negative!");
445       return !SpillSlotToUsesMap[FrameIndex-LowSpillSlot].empty();
446     }
447 
448     /// @brief Mark the specified register as being implicitly defined.
setIsImplicitlyDefined(unsigned VirtReg)449     void setIsImplicitlyDefined(unsigned VirtReg) {
450       ImplicitDefed.set(TargetRegisterInfo::virtReg2Index(VirtReg));
451     }
452 
453     /// @brief Returns true if the virtual register is implicitly defined.
isImplicitlyDefined(unsigned VirtReg)454     bool isImplicitlyDefined(unsigned VirtReg) const {
455       return ImplicitDefed[TargetRegisterInfo::virtReg2Index(VirtReg)];
456     }
457 
458     /// @brief Updates information about the specified virtual register's value
459     /// folded into newMI machine instruction.
460     void virtFolded(unsigned VirtReg, MachineInstr *OldMI, MachineInstr *NewMI,
461                     ModRef MRInfo);
462 
463     /// @brief Updates information about the specified virtual register's value
464     /// folded into the specified machine instruction.
465     void virtFolded(unsigned VirtReg, MachineInstr *MI, ModRef MRInfo);
466 
467     /// @brief returns the virtual registers' values folded in memory
468     /// operands of this instruction
469     std::pair<MI2VirtMapTy::const_iterator, MI2VirtMapTy::const_iterator>
getFoldedVirts(MachineInstr * MI)470     getFoldedVirts(MachineInstr* MI) const {
471       return MI2VirtMap.equal_range(MI);
472     }
473 
474     /// RemoveMachineInstrFromMaps - MI is being erased, remove it from the
475     /// the folded instruction map and spill point map.
476     void RemoveMachineInstrFromMaps(MachineInstr *MI);
477 
478     /// FindUnusedRegisters - Gather a list of allocatable registers that
479     /// have not been allocated to any virtual register.
480     bool FindUnusedRegisters(LiveIntervals* LIs);
481 
482     /// HasUnusedRegisters - Return true if there are any allocatable registers
483     /// that have not been allocated to any virtual register.
HasUnusedRegisters()484     bool HasUnusedRegisters() const {
485       return !UnusedRegs.none();
486     }
487 
488     /// setRegisterUsed - Remember the physical register is now used.
setRegisterUsed(unsigned Reg)489     void setRegisterUsed(unsigned Reg) {
490       UnusedRegs.reset(Reg);
491     }
492 
493     /// isRegisterUnused - Return true if the physical register has not been
494     /// used.
isRegisterUnused(unsigned Reg)495     bool isRegisterUnused(unsigned Reg) const {
496       return UnusedRegs[Reg];
497     }
498 
499     /// getFirstUnusedRegister - Return the first physical register that has not
500     /// been used.
getFirstUnusedRegister(const TargetRegisterClass * RC)501     unsigned getFirstUnusedRegister(const TargetRegisterClass *RC) {
502       int Reg = UnusedRegs.find_first();
503       while (Reg != -1) {
504         if (allocatableRCRegs[RC][Reg])
505           return (unsigned)Reg;
506         Reg = UnusedRegs.find_next(Reg);
507       }
508       return 0;
509     }
510 
511     /// rewrite - Rewrite all instructions in MF to use only physical registers
512     /// by mapping all virtual register operands to their assigned physical
513     /// registers.
514     ///
515     /// @param Indexes Optionally remove deleted instructions from indexes.
516     void rewrite(SlotIndexes *Indexes);
517 
518     void print(raw_ostream &OS, const Module* M = 0) const;
519     void dump() const;
520   };
521 
522   inline raw_ostream &operator<<(raw_ostream &OS, const VirtRegMap &VRM) {
523     VRM.print(OS);
524     return OS;
525   }
526 } // End llvm namespace
527 
528 #endif
529