X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FVirtRegMap.h;h=8b494a7c617bc3de183a0b0bc31716b9b59b77dd;hb=ef4cfc749a61d0d0252196c957697436ba7ec068;hp=dc2f1cd70d0dae9b6ac5708e8e4e7d0f0b3212e6;hpb=81a038218171860ee4c382849c647d3dc841fe8b;p=oota-llvm.git diff --git a/lib/CodeGen/VirtRegMap.h b/lib/CodeGen/VirtRegMap.h index dc2f1cd70d0..8b494a7c617 100644 --- a/lib/CodeGen/VirtRegMap.h +++ b/lib/CodeGen/VirtRegMap.h @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -17,9 +17,11 @@ #ifndef LLVM_CODEGEN_VIRTREGMAP_H #define LLVM_CODEGEN_VIRTREGMAP_H -#include "llvm/Target/MRegisterInfo.h" -#include "llvm/ADT/DenseMap.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/ADT/BitVector.h" #include "llvm/ADT/IndexedMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/Support/Streams.h" #include @@ -57,7 +59,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; @@ -66,6 +68,10 @@ namespace llvm { /// mapping. IndexedMap Virt2SplitMap; + /// Virt2SplitKillMap - This is splitted virtual register to its last use + /// (kill) index mapping. + IndexedMap Virt2SplitKillMap; + /// ReMatMap - This is virtual register to re-materialized instruction /// mapping. Each virtual register whose definition is going to be /// re-materialized has an entry in it. @@ -80,12 +86,24 @@ namespace llvm { /// SpillPt2VirtMap - This records the virtual registers which should /// be spilled right after the MachineInstr due to live interval /// splitting. - DenseMap > SpillPt2VirtMap; + std::map > > + SpillPt2VirtMap; + + /// RestorePt2VirtMap - This records the virtual registers which should + /// be restored right before the MachineInstr due to live interval + /// 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; - /// Virt2SplitMap - This records the MachineInstrs where a virtual - /// register should be spilled due to live interval splitting. - IndexedMap, VirtReg2IndexFunctor> - Virt2SpillPtsMap; + /// 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 @@ -93,6 +111,16 @@ namespace llvm { /// 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; + VirtRegMap(const VirtRegMap&); // DO NOT IMPLEMENT void operator=(const VirtRegMap&); // DO NOT IMPLEMENT @@ -110,15 +138,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"); @@ -128,7 +156,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; @@ -150,7 +178,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 && @@ -164,14 +192,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]; } @@ -209,67 +237,170 @@ namespace llvm { ReMatMap[virtReg] = def; } + /// @brief record the last use (kill) of a split virtual register. + void addKillPoint(unsigned virtReg, unsigned index) { + Virt2SplitKillMap[virtReg] = index; + } + + unsigned 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; + } + + /// @brief returns true if the specified MachineInstr is a spill point. + bool isSpillPt(MachineInstr *Pt) const { + return SpillPt2VirtMap.find(Pt) != SpillPt2VirtMap.end(); + } + /// @brief returns the virtual registers that should be spilled due to /// splitting right after the specified MachineInstr. - std::vector &getSpillPtSpills(MachineInstr *Pt) { + std::vector > &getSpillPtSpills(MachineInstr *Pt) { return SpillPt2VirtMap[Pt]; } /// @brief records the specified MachineInstr as a spill point for virtReg. - void addSpillPoint(unsigned virtReg, MachineInstr *Pt) { - SpillPt2VirtMap[Pt].push_back(virtReg); - Virt2SpillPtsMap[virtReg].push_back(Pt); - } - - /// @brief remove the virtReg from the list of registers that should be - /// spilled (due to splitting) right after the specified MachineInstr. - void removeRegFromSpillPt(MachineInstr *Pt, unsigned virtReg) { - std::vector &Regs = SpillPt2VirtMap[Pt]; - if (Regs.back() == virtReg) // Most common case. - Regs.pop_back(); - for (unsigned i = 0, e = Regs.size(); i != e; ++i) - if (Regs[i] == virtReg) { - Regs.erase(Regs.begin()+i-1); - break; - } - } - - /// @brief specify virtReg is no longer being spilled due to splitting. - void removeAllSpillPtsForReg(unsigned virtReg) { - std::vector &SpillPts = Virt2SpillPtsMap[virtReg]; - for (unsigned i = 0, e = SpillPts.size(); i != e; ++i) - removeRegFromSpillPt(SpillPts[i], virtReg); - Virt2SpillPtsMap[virtReg].clear(); - } - - /// @brief remove the specified MachineInstr as a spill point for the - /// specified register. - void removeRegSpillPt(unsigned virtReg, MachineInstr *Pt) { - std::vector &SpillPts = Virt2SpillPtsMap[virtReg]; - if (SpillPts.back() == Pt) // Most common case. - SpillPts.pop_back(); - for (unsigned i = 0, e = SpillPts.size(); i != e; ++i) - if (SpillPts[i] == Pt) { - SpillPts.erase(SpillPts.begin()+i-1); - break; - } + void addSpillPoint(unsigned virtReg, bool isKill, MachineInstr *Pt) { + if (SpillPt2VirtMap.find(Pt) != SpillPt2VirtMap.end()) + SpillPt2VirtMap[Pt].push_back(std::make_pair(virtReg, isKill)); + else { + std::vector > Virts; + Virts.push_back(std::make_pair(virtReg, isKill)); + SpillPt2VirtMap.insert(std::make_pair(Pt, Virts)); + } } + /// @brief - transfer spill point information from one instruction to + /// another. void transferSpillPts(MachineInstr *Old, MachineInstr *New) { - std::vector &OldRegs = SpillPt2VirtMap[Old]; - while (!OldRegs.empty()) { - unsigned virtReg = OldRegs.back(); - OldRegs.pop_back(); - removeRegSpillPt(virtReg, Old); - addSpillPoint(virtReg, New); + std::map > >::iterator + I = SpillPt2VirtMap.find(Old); + if (I == SpillPt2VirtMap.end()) + return; + while (!I->second.empty()) { + unsigned virtReg = I->second.back().first; + bool isKill = I->second.back().second; + I->second.pop_back(); + addSpillPoint(virtReg, isKill, New); + } + SpillPt2VirtMap.erase(I); + } + + /// @brief returns true if the specified MachineInstr is a restore point. + bool isRestorePt(MachineInstr *Pt) const { + return RestorePt2VirtMap.find(Pt) != RestorePt2VirtMap.end(); + } + + /// @brief returns the virtual registers that should be restoreed due to + /// splitting right after the specified MachineInstr. + std::vector &getRestorePtRestores(MachineInstr *Pt) { + return RestorePt2VirtMap[Pt]; + } + + /// @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); + else { + std::vector Virts; + Virts.push_back(virtReg); + RestorePt2VirtMap.insert(std::make_pair(Pt, Virts)); + } + } + + /// @brief - transfer restore point information from one instruction to + /// another. + void transferRestorePts(MachineInstr *Old, MachineInstr *New) { + std::map >::iterator I = + RestorePt2VirtMap.find(Old); + if (I == RestorePt2VirtMap.end()) + return; + while (!I->second.empty()) { + unsigned virtReg = I->second.back(); + I->second.pop_back(); + addRestorePoint(virtReg, New); } + 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. The OpNum argument indicates the - /// operand number of OldMI that is folded. - void virtFolded(unsigned VirtReg, MachineInstr *OldMI, unsigned OpNum, - MachineInstr *NewMI); + /// folded into newMI machine instruction. + void virtFolded(unsigned VirtReg, MachineInstr *OldMI, MachineInstr *NewMI, + ModRef MRInfo); /// @brief Updates information about the specified virtual register's value /// folded into the specified machine instruction. @@ -282,11 +413,9 @@ namespace llvm { return MI2VirtMap.equal_range(MI); } - /// RemoveFromFoldedVirtMap - If the specified machine instruction is in - /// the folded instruction map, remove its entry from the map. - void RemoveFromFoldedVirtMap(MachineInstr *MI) { - MI2VirtMap.erase(MI); - } + /// RemoveMachineInstrFromMaps - MI is being erased, remove it from the + /// 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); }