X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FVirtRegMap.h;h=ca174d5127af3435752fc9ae3ffa68b25abe5395;hb=25d812bd7d1f58f2ba1b598b1425a2e146e27381;hp=3b8c3621a9828ee4f6f6a72dc0685f4c19146e89;hpb=4ee451de366474b9c228b4e5fa573795a715216d;p=oota-llvm.git diff --git a/lib/CodeGen/VirtRegMap.h b/lib/CodeGen/VirtRegMap.h index 3b8c3621a98..ca174d5127a 100644 --- a/lib/CodeGen/VirtRegMap.h +++ b/lib/CodeGen/VirtRegMap.h @@ -17,18 +17,26 @@ #ifndef LLVM_CODEGEN_VIRTREGMAP_H #define LLVM_CODEGEN_VIRTREGMAP_H -#include "llvm/Target/MRegisterInfo.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/Support/Streams.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" #include 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, @@ -41,9 +49,13 @@ namespace llvm { std::pair > MI2VirtMapTy; private: - const TargetInstrInfo &TII; + MachineRegisterInfo *MRI; + const TargetInstrInfo *TII; + const TargetRegisterInfo *TRI; + MachineFunction *MF; + + DenseMap 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 @@ -57,7 +69,7 @@ namespace llvm { /// at. IndexedMap 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 Virt2ReMatIdMap; @@ -68,7 +80,7 @@ namespace llvm { /// Virt2SplitKillMap - This is splitted virtual register to its last use /// (kill) index mapping. - IndexedMap Virt2SplitKillMap; + IndexedMap Virt2SplitKillMap; /// ReMatMap - This is virtual register to re-materialized instruction /// mapping. Each virtual register whose definition is going to be @@ -92,17 +104,53 @@ namespace llvm { /// splitting. std::map > 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 > 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 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 /// conflicts with stack slot numbers. int ReMatId; + /// LowSpillSlot, HighSpillSlot - Lowest and highest spill slot indexes. + int LowSpillSlot, HighSpillSlot; + + /// SpillSlotToUsesMap - Records uses for each register spill slot. + SmallVector, 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(MachineInstrIndex()), 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(); @@ -115,15 +163,15 @@ namespace llvm { /// @brief returns the physical register mapped to the specified /// virtual register unsigned getPhys(unsigned virtReg) const { - assert(MRegisterInfo::isVirtualRegister(virtReg)); + assert(TargetRegisterInfo::isVirtualRegister(virtReg)); return Virt2PhysMap[virtReg]; } /// @brief creates a mapping for the specified virtual register to /// the specified physical register void assignVirt2Phys(unsigned virtReg, unsigned physReg) { - assert(MRegisterInfo::isVirtualRegister(virtReg) && - MRegisterInfo::isPhysicalRegister(physReg)); + assert(TargetRegisterInfo::isVirtualRegister(virtReg) && + TargetRegisterInfo::isPhysicalRegister(physReg)); assert(Virt2PhysMap[virtReg] == NO_PHYS_REG && "attempt to assign physical register to already mapped " "virtual register"); @@ -133,7 +181,7 @@ namespace llvm { /// @brief clears the specified virtual register's, physical /// register mapping void clearVirt(unsigned virtReg) { - assert(MRegisterInfo::isVirtualRegister(virtReg)); + assert(TargetRegisterInfo::isVirtualRegister(virtReg)); assert(Virt2PhysMap[virtReg] != NO_PHYS_REG && "attempt to clear a not assigned virtual register"); Virt2PhysMap[virtReg] = NO_PHYS_REG; @@ -145,6 +193,9 @@ namespace llvm { 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; @@ -155,7 +206,7 @@ namespace llvm { 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 && @@ -169,14 +220,14 @@ namespace llvm { /// @brief returns the stack slot mapped to the specified virtual /// register int getStackSlot(unsigned virtReg) const { - assert(MRegisterInfo::isVirtualRegister(virtReg)); + assert(TargetRegisterInfo::isVirtualRegister(virtReg)); return Virt2StackSlotMap[virtReg]; } /// @brief returns the rematerialization id mapped to the specified virtual /// register int getReMatId(unsigned virtReg) const { - assert(MRegisterInfo::isVirtualRegister(virtReg)); + assert(TargetRegisterInfo::isVirtualRegister(virtReg)); return Virt2ReMatIdMap[virtReg]; } @@ -215,17 +266,17 @@ namespace llvm { } /// @brief record the last use (kill) of a split virtual register. - void addKillPoint(unsigned virtReg, unsigned index) { + void addKillPoint(unsigned virtReg, MachineInstrIndex index) { Virt2SplitKillMap[virtReg] = index; } - unsigned getKillPoint(unsigned virtReg) const { + MachineInstrIndex 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] = MachineInstrIndex(); } /// @brief returns true if the specified MachineInstr is a spill point. @@ -241,8 +292,10 @@ namespace llvm { /// @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 > >::iterator + I = SpillPt2VirtMap.find(Pt); + if (I != SpillPt2VirtMap.end()) + I->second.push_back(std::make_pair(virtReg, isKill)); else { std::vector > Virts; Virts.push_back(std::make_pair(virtReg, isKill)); @@ -250,8 +303,10 @@ namespace llvm { } } + /// @brief - transfer spill point information from one instruction to + /// another. void transferSpillPts(MachineInstr *Old, MachineInstr *New) { - std::map > >::iterator + std::map > >::iterator I = SpillPt2VirtMap.find(Old); if (I == SpillPt2VirtMap.end()) return; @@ -277,8 +332,10 @@ namespace llvm { /// @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 >::iterator I = + RestorePt2VirtMap.find(Pt); + if (I != RestorePt2VirtMap.end()) + I->second.push_back(virtReg); else { std::vector Virts; Virts.push_back(virtReg); @@ -286,8 +343,10 @@ namespace llvm { } } + /// @brief - transfer restore point information from one instruction to + /// another. void transferRestorePts(MachineInstr *Old, MachineInstr *New) { - std::map >::iterator I = + std::map >::iterator I = RestorePt2VirtMap.find(Old); if (I == RestorePt2VirtMap.end()) return; @@ -299,6 +358,77 @@ namespace llvm { 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 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 &getEmergencySpills(MachineInstr *MI) { + return EmergencySpillMap[MI]; + } + + /// @brief - transfer emergency spill information from one instruction to + /// another. + void transferEmergencySpills(MachineInstr *Old, MachineInstr *New) { + std::map >::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; + } + + /// @brief Return highest spill slot index. + int getHighSpillSlot() const { + return HighSpillSlot; + } + + /// @brief Records a spill slot use. + void addSpillSlotUse(int FrameIndex, MachineInstr *MI); + + /// @brief Returns true if spill slot has been used. + bool isSpillSlotUsed(int FrameIndex) const { + assert(FrameIndex >= 0 && "Spill slot index should not be negative!"); + 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, @@ -317,38 +447,49 @@ namespace llvm { /// RemoveMachineInstrFromMaps - MI is being erased, remove it from the /// the folded instruction map and spill point map. - void RemoveMachineInstrFromMaps(MachineInstr *MI) { - MI2VirtMap.erase(MI); - SpillPt2VirtMap.erase(MI); - RestorePt2VirtMap.erase(MI); + void RemoveMachineInstrFromMaps(MachineInstr *MI); + + /// 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(); } - void print(std::ostream &OS) const; - void print(std::ostream *OS) const { if (OS) print(*OS); } + /// 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