#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 SlotIndexes;
- 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, VirtReg2IndexFunctor> Virt2SplitKillMap;
/// ReMatMap - This is virtual register to re-materialized instruction
/// mapping. Each virtual register whose definition is going to be
/// 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;
+
+ /// createSpillSlot - Allocate a spill slot for RC from MFI.
+ unsigned createSpillSlot(const TargetRegisterClass *RC);
+
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);
+ }
+
+ MachineFunction &getMachineFunction() const {
+ assert(MF && "getMachineFunction called before runOnMachineFunction");
+ return *MF;
+ }
+
+ MachineRegisterInfo &getRegInfo() const { return *MRI; }
+ const TargetRegisterInfo &getTargetRegInfo() const { return *TRI; }
void grow();
grow();
}
+ /// @brief returns the register allocation preference.
+ unsigned getRegAllocPref(unsigned virtReg);
+
+ /// @brief returns true if VirtReg is assigned to its preferred physreg.
+ bool hasPreferredPhys(unsigned VirtReg) {
+ return getPhys(VirtReg) == getRegAllocPref(VirtReg);
+ }
+
/// @brief records virtReg is a split live interval from SReg.
void setIsSplitFromReg(unsigned virtReg, unsigned SReg) {
Virt2SplitMap[virtReg] = SReg;
}
/// @brief returns the live interval virtReg is split from.
- unsigned getPreSplitReg(unsigned virtReg) {
+ unsigned getPreSplitReg(unsigned virtReg) const {
return Virt2SplitMap[virtReg];
}
- /// @brief returns true is the specified virtual register is not
+ /// getOriginal - Return the original virtual register that VirtReg descends
+ /// from through splitting.
+ /// A register that was not created by splitting is its own original.
+ /// This operation is idempotent.
+ unsigned getOriginal(unsigned VirtReg) const {
+ unsigned Orig = getPreSplitReg(VirtReg);
+ return Orig ? Orig : VirtReg;
+ }
+
+ /// @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;
return !SpillSlotToUsesMap[FrameIndex-LowSpillSlot].empty();
}
+ /// @brief Mark the specified register as being implicitly defined.
+ void setIsImplicitlyDefined(unsigned VirtReg) {
+ ImplicitDefed.set(TargetRegisterInfo::virtReg2Index(VirtReg));
+ }
+
+ /// @brief Returns true if the virtual register is implicitly defined.
+ bool isImplicitlyDefined(unsigned VirtReg) const {
+ return ImplicitDefed[TargetRegisterInfo::virtReg2Index(VirtReg)];
+ }
+
/// @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;
+ }
+
+ /// rewrite - Rewrite all instructions in MF to use only physical registers
+ /// by mapping all virtual register operands to their assigned physical
+ /// registers.
+ ///
+ /// @param Indexes Optionally remove deleted instructions from indexes.
+ void rewrite(SlotIndexes *Indexes);
+
+ void print(raw_ostream &OS, const Module* M = 0) const;
void dump() const;
};
- inline std::ostream *operator<<(std::ostream *OS, const VirtRegMap &VRM) {
- VRM.print(OS);
- return OS;
- }
- 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;
}
-
- /// 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