#ifndef LLVM_CODEGEN_VIRTREGMAP_H
#define LLVM_CODEGEN_VIRTREGMAP_H
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/Target/TargetRegisterInfo.h"
+#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/IndexedMap.h"
#include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/Support/Streams.h"
+#include "llvm/ADT/SmallVector.h"
#include <map>
namespace llvm {
+ class LiveIntervals;
class MachineInstr;
class MachineFunction;
+ class MachineRegisterInfo;
class TargetInstrInfo;
+ class TargetRegisterInfo;
+ class raw_ostream;
- class VirtRegMap {
+ class VirtRegMap : public MachineFunctionPass {
public:
enum {
NO_PHYS_REG = 0,
std::pair<unsigned, ModRef> > MI2VirtMapTy;
private:
- const TargetInstrInfo &TII;
+ MachineRegisterInfo *MRI;
+ const TargetInstrInfo *TII;
+ const TargetRegisterInfo *TRI;
+ MachineFunction *MF;
+
+ DenseMap<const TargetRegisterClass*, BitVector> allocatableRCRegs;
- MachineFunction &MF;
/// Virt2PhysMap - This is a virtual to physical register
/// mapping. Each virtual register is required to have an entry in
/// it; even spilled virtual registers (the register mapped to a
/// at.
IndexedMap<int, VirtReg2IndexFunctor> Virt2StackSlotMap;
- /// Virt2StackSlotMap - This is virtual register to rematerialization id
+ /// Virt2ReMatIdMap - This is virtual register to rematerialization id
/// mapping. Each spilled virtual register that should be remat'd has an
/// entry in it which corresponds to the remat id.
IndexedMap<int, VirtReg2IndexFunctor> Virt2ReMatIdMap;
/// Virt2SplitKillMap - This is splitted virtual register to its last use
/// (kill) index mapping.
- IndexedMap<unsigned> Virt2SplitKillMap;
+ IndexedMap<SlotIndex> Virt2SplitKillMap;
/// ReMatMap - This is virtual register to re-materialized instruction
/// mapping. Each virtual register whose definition is going to be
/// splitting.
std::map<MachineInstr*, std::vector<unsigned> > RestorePt2VirtMap;
+ /// EmergencySpillMap - This records the physical registers that should
+ /// be spilled / restored around the MachineInstr since the register
+ /// allocator has run out of registers.
+ std::map<MachineInstr*, std::vector<unsigned> > EmergencySpillMap;
+
+ /// EmergencySpillSlots - This records emergency spill slots used to
+ /// spill physical registers when the register allocator runs out of
+ /// registers. Ideally only one stack slot is used per function per
+ /// register class.
+ std::map<const TargetRegisterClass*, int> EmergencySpillSlots;
+
/// ReMatId - Instead of assigning a stack slot to a to be rematerialized
/// virtual register, an unique id is being assigned. This keeps track of
/// the highest id used so far. Note, this starts at (1<<18) to avoid
/// SpillSlotToUsesMap - Records uses for each register spill slot.
SmallVector<SmallPtrSet<MachineInstr*, 4>, 8> SpillSlotToUsesMap;
+ /// ImplicitDefed - One bit for each virtual register. If set it indicates
+ /// the register is implicitly defined.
+ BitVector ImplicitDefed;
+
+ /// UnusedRegs - A list of physical registers that have not been used.
+ BitVector UnusedRegs;
+
VirtRegMap(const VirtRegMap&); // DO NOT IMPLEMENT
void operator=(const VirtRegMap&); // DO NOT IMPLEMENT
public:
- explicit VirtRegMap(MachineFunction &mf);
+ static char ID;
+ VirtRegMap() : MachineFunctionPass(&ID), Virt2PhysMap(NO_PHYS_REG),
+ Virt2StackSlotMap(NO_STACK_SLOT),
+ Virt2ReMatIdMap(NO_STACK_SLOT), Virt2SplitMap(0),
+ Virt2SplitKillMap(SlotIndex()), ReMatMap(NULL),
+ ReMatId(MAX_STACK_SLOT+1),
+ LowSpillSlot(NO_STACK_SLOT), HighSpillSlot(NO_STACK_SLOT) { }
+ virtual bool runOnMachineFunction(MachineFunction &MF);
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesAll();
+ MachineFunctionPass::getAnalysisUsage(AU);
+ }
void grow();
grow();
}
+ /// @brief returns the register allocation preference.
+ unsigned getRegAllocPref(unsigned virtReg);
+
/// @brief records virtReg is a split live interval from SReg.
void setIsSplitFromReg(unsigned virtReg, unsigned SReg) {
Virt2SplitMap[virtReg] = SReg;
return Virt2SplitMap[virtReg];
}
- /// @brief returns true is the specified virtual register is not
+ /// @brief returns true if the specified virtual register is not
/// mapped to a stack slot or rematerialized.
bool isAssignedReg(unsigned virtReg) const {
if (getStackSlot(virtReg) == NO_STACK_SLOT &&
}
/// @brief record the last use (kill) of a split virtual register.
- void addKillPoint(unsigned virtReg, unsigned index) {
+ void addKillPoint(unsigned virtReg, SlotIndex index) {
Virt2SplitKillMap[virtReg] = index;
}
- unsigned getKillPoint(unsigned virtReg) const {
+ SlotIndex getKillPoint(unsigned virtReg) const {
return Virt2SplitKillMap[virtReg];
}
/// @brief remove the last use (kill) of a split virtual register.
void removeKillPoint(unsigned virtReg) {
- Virt2SplitKillMap[virtReg] = 0;
+ Virt2SplitKillMap[virtReg] = SlotIndex();
}
/// @brief returns true if the specified MachineInstr is a spill point.
/// @brief records the specified MachineInstr as a spill point for virtReg.
void addSpillPoint(unsigned virtReg, bool isKill, MachineInstr *Pt) {
- if (SpillPt2VirtMap.find(Pt) != SpillPt2VirtMap.end())
- SpillPt2VirtMap[Pt].push_back(std::make_pair(virtReg, isKill));
+ std::map<MachineInstr*, std::vector<std::pair<unsigned,bool> > >::iterator
+ I = SpillPt2VirtMap.find(Pt);
+ if (I != SpillPt2VirtMap.end())
+ I->second.push_back(std::make_pair(virtReg, isKill));
else {
std::vector<std::pair<unsigned,bool> > Virts;
Virts.push_back(std::make_pair(virtReg, isKill));
}
}
+ /// @brief - transfer spill point information from one instruction to
+ /// another.
void transferSpillPts(MachineInstr *Old, MachineInstr *New) {
- std::map<MachineInstr*,std::vector<std::pair<unsigned,bool> > >::iterator
+ std::map<MachineInstr*, std::vector<std::pair<unsigned,bool> > >::iterator
I = SpillPt2VirtMap.find(Old);
if (I == SpillPt2VirtMap.end())
return;
/// @brief records the specified MachineInstr as a restore point for virtReg.
void addRestorePoint(unsigned virtReg, MachineInstr *Pt) {
- if (RestorePt2VirtMap.find(Pt) != RestorePt2VirtMap.end())
- RestorePt2VirtMap[Pt].push_back(virtReg);
+ std::map<MachineInstr*, std::vector<unsigned> >::iterator I =
+ RestorePt2VirtMap.find(Pt);
+ if (I != RestorePt2VirtMap.end())
+ I->second.push_back(virtReg);
else {
std::vector<unsigned> Virts;
Virts.push_back(virtReg);
}
}
+ /// @brief - transfer restore point information from one instruction to
+ /// another.
void transferRestorePts(MachineInstr *Old, MachineInstr *New) {
- std::map<MachineInstr*,std::vector<unsigned> >::iterator I =
+ std::map<MachineInstr*, std::vector<unsigned> >::iterator I =
RestorePt2VirtMap.find(Old);
if (I == RestorePt2VirtMap.end())
return;
RestorePt2VirtMap.erase(I);
}
+ /// @brief records that the specified physical register must be spilled
+ /// around the specified machine instr.
+ void addEmergencySpill(unsigned PhysReg, MachineInstr *MI) {
+ if (EmergencySpillMap.find(MI) != EmergencySpillMap.end())
+ EmergencySpillMap[MI].push_back(PhysReg);
+ else {
+ std::vector<unsigned> PhysRegs;
+ PhysRegs.push_back(PhysReg);
+ EmergencySpillMap.insert(std::make_pair(MI, PhysRegs));
+ }
+ }
+
+ /// @brief returns true if one or more physical registers must be spilled
+ /// around the specified instruction.
+ bool hasEmergencySpills(MachineInstr *MI) const {
+ return EmergencySpillMap.find(MI) != EmergencySpillMap.end();
+ }
+
+ /// @brief returns the physical registers to be spilled and restored around
+ /// the instruction.
+ std::vector<unsigned> &getEmergencySpills(MachineInstr *MI) {
+ return EmergencySpillMap[MI];
+ }
+
+ /// @brief - transfer emergency spill information from one instruction to
+ /// another.
+ void transferEmergencySpills(MachineInstr *Old, MachineInstr *New) {
+ std::map<MachineInstr*,std::vector<unsigned> >::iterator I =
+ EmergencySpillMap.find(Old);
+ if (I == EmergencySpillMap.end())
+ return;
+ while (!I->second.empty()) {
+ unsigned virtReg = I->second.back();
+ I->second.pop_back();
+ addEmergencySpill(virtReg, New);
+ }
+ EmergencySpillMap.erase(I);
+ }
+
+ /// @brief return or get a emergency spill slot for the register class.
+ int getEmergencySpillSlot(const TargetRegisterClass *RC);
+
/// @brief Return lowest spill slot index.
int getLowSpillSlot() const {
return LowSpillSlot;
return !SpillSlotToUsesMap[FrameIndex-LowSpillSlot].empty();
}
+ /// @brief Mark the specified register as being implicitly defined.
+ void setIsImplicitlyDefined(unsigned VirtReg) {
+ ImplicitDefed.set(VirtReg-TargetRegisterInfo::FirstVirtualRegister);
+ }
+
+ /// @brief Returns true if the virtual register is implicitly defined.
+ bool isImplicitlyDefined(unsigned VirtReg) const {
+ return ImplicitDefed[VirtReg-TargetRegisterInfo::FirstVirtualRegister];
+ }
+
/// @brief Updates information about the specified virtual register's value
/// folded into newMI machine instruction.
void virtFolded(unsigned VirtReg, MachineInstr *OldMI, MachineInstr *NewMI,
/// the folded instruction map and spill point map.
void RemoveMachineInstrFromMaps(MachineInstr *MI);
- void print(std::ostream &OS) const;
- void print(std::ostream *OS) const { if (OS) print(*OS); }
+ /// FindUnusedRegisters - Gather a list of allocatable registers that
+ /// have not been allocated to any virtual register.
+ bool FindUnusedRegisters(LiveIntervals* LIs);
+
+ /// HasUnusedRegisters - Return true if there are any allocatable registers
+ /// that have not been allocated to any virtual register.
+ bool HasUnusedRegisters() const {
+ return !UnusedRegs.none();
+ }
+
+ /// setRegisterUsed - Remember the physical register is now used.
+ void setRegisterUsed(unsigned Reg) {
+ UnusedRegs.reset(Reg);
+ }
+
+ /// isRegisterUnused - Return true if the physical register has not been
+ /// used.
+ bool isRegisterUnused(unsigned Reg) const {
+ return UnusedRegs[Reg];
+ }
+
+ /// getFirstUnusedRegister - Return the first physical register that has not
+ /// been used.
+ unsigned getFirstUnusedRegister(const TargetRegisterClass *RC) {
+ int Reg = UnusedRegs.find_first();
+ while (Reg != -1) {
+ if (allocatableRCRegs[RC][Reg])
+ return (unsigned)Reg;
+ Reg = UnusedRegs.find_next(Reg);
+ }
+ return 0;
+ }
+
+ void print(raw_ostream &OS, const Module* M = 0) const;
void dump() const;
};
- inline std::ostream *operator<<(std::ostream *OS, const VirtRegMap &VRM) {
+ inline raw_ostream &operator<<(raw_ostream &OS, const VirtRegMap &VRM) {
VRM.print(OS);
return OS;
}
- inline std::ostream &operator<<(std::ostream &OS, const VirtRegMap &VRM) {
- VRM.print(OS);
- return OS;
- }
-
- /// Spiller interface: Implementations of this interface assign spilled
- /// virtual registers to stack slots, rewriting the code.
- struct Spiller {
- virtual ~Spiller();
- virtual bool runOnMachineFunction(MachineFunction &MF,
- VirtRegMap &VRM) = 0;
- };
-
- /// createSpiller - Create an return a spiller object, as specified on the
- /// command line.
- Spiller* createSpiller();
-
} // End llvm namespace
#endif