X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;ds=sidebyside;f=include%2Fllvm%2FCodeGen%2FLiveVariables.h;h=55b97dc3e71d94306be66c173fb50e4f56a36c3a;hb=fcc330abfef50ecb692d72e5c853b2668cfedcc2;hp=45c72f5fe89cc3fb8ebb139a892d93dd340c5120;hpb=296925dc169b45e7535abdccc8dc143a8bec7f0a;p=oota-llvm.git diff --git a/include/llvm/CodeGen/LiveVariables.h b/include/llvm/CodeGen/LiveVariables.h index 45c72f5fe89..55b97dc3e71 100644 --- a/include/llvm/CodeGen/LiveVariables.h +++ b/include/llvm/CodeGen/LiveVariables.h @@ -29,24 +29,26 @@ #ifndef LLVM_CODEGEN_LIVEVARIABLES_H #define LLVM_CODEGEN_LIVEVARIABLES_H -#include "llvm/CodeGen/MachineBasicBlock.h" -#include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/CodeGen/MachineInstr.h" -#include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/IndexedMap.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/SparseBitVector.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/Target/TargetRegisterInfo.h" namespace llvm { +class MachineBasicBlock; class MachineRegisterInfo; -class TargetRegisterInfo; class LiveVariables : public MachineFunctionPass { public: static char ID; // Pass identification, replacement for typeid - LiveVariables() : MachineFunctionPass(&ID) {} + LiveVariables() : MachineFunctionPass(ID) { + initializeLiveVariablesPass(*PassRegistry::getPassRegistry()); + } /// VarInfo - This represents the regions where a virtual register is live in /// the program. We represent this with three different pieces of @@ -81,17 +83,11 @@ public: /// SparseBitVector<> AliveBlocks; - /// NumUses - Number of uses of this register across the entire function. - /// - unsigned NumUses; - /// Kills - List of MachineInstruction's which are the last use of this /// virtual register (kill it) in their basic block. /// std::vector Kills; - VarInfo() : NumUses(0) {} - /// removeKill - Delete a kill corresponding to the specified /// machine instruction. Returns true if there was a kill /// corresponding to this instruction, false otherwise. @@ -103,22 +99,30 @@ public: Kills.erase(I); return true; } - + + /// findKill - Find a kill instruction in MBB. Return NULL if none is found. + MachineInstr *findKill(const MachineBasicBlock *MBB) const; + + /// isLiveIn - Is Reg live in to MBB? This means that Reg is live through + /// MBB, or it is killed in MBB. If Reg is only used by PHI instructions in + /// MBB, it is not considered live in. + bool isLiveIn(const MachineBasicBlock &MBB, + unsigned Reg, + MachineRegisterInfo &MRI); + void dump() const; }; private: /// VirtRegInfo - This list is a mapping from virtual register number to - /// variable information. FirstVirtualRegister is subtracted from the virtual - /// register number before indexing into this list. + /// variable information. /// - std::vector VirtRegInfo; + IndexedMap VirtRegInfo; - /// ReservedRegisters - This vector keeps track of which registers - /// are reserved register which are not allocatable by the target machine. - /// We can not track liveness for values that are in this set. - /// - BitVector ReservedRegisters; + /// PHIJoins - list of virtual registers that are PHI joins. These registers + /// may have multiple definitions, and they require special handling when + /// building live intervals. + SparseBitVector<> PHIJoins; private: // Intermediate data structures MachineFunction *MF; @@ -130,14 +134,14 @@ private: // Intermediate data structures // PhysRegInfo - Keep track of which instruction was the last def of a // physical register. This is a purely local property, because all physical // register references are presumed dead across basic blocks. - MachineInstr **PhysRegDef; + std::vector PhysRegDef; // PhysRegInfo - Keep track of which instruction was the last use of a // physical register. This is a purely local property, because all physical // register references are presumed dead across basic blocks. - MachineInstr **PhysRegUse; + std::vector PhysRegUse; - SmallVector *PHIVarInfo; + std::vector> PHIVarInfo; // DistanceMap - Keep track the distance of a MI from the start of the // current basic block. @@ -148,31 +152,36 @@ private: // Intermediate data structures /// the last use of the whole register. bool HandlePhysRegKill(unsigned Reg, MachineInstr *MI); + /// HandleRegMask - Call HandlePhysRegKill for all registers clobbered by Mask. + void HandleRegMask(const MachineOperand&); + void HandlePhysRegUse(unsigned Reg, MachineInstr *MI); void HandlePhysRegDef(unsigned Reg, MachineInstr *MI, - SmallVector &Defs, - SmallVector &SuperDefs); - void UpdatePhysRegDefs(MachineInstr *MI, SmallVector &Defs); - void UpdateSuperRegDefs(MachineInstr *MI, SmallVector &Defs); + SmallVectorImpl &Defs); + void UpdatePhysRegDefs(MachineInstr *MI, SmallVectorImpl &Defs); - /// FindLastPartialDef - Return the last partial def of the specified register. - /// Also returns the sub-registers that're defined by the instruction. + /// FindLastRefOrPartRef - Return the last reference or partial reference of + /// the specified register. + MachineInstr *FindLastRefOrPartRef(unsigned Reg); + + /// FindLastPartialDef - Return the last partial def of the specified + /// register. Also returns the sub-registers that're defined by the + /// instruction. MachineInstr *FindLastPartialDef(unsigned Reg, SmallSet &PartDefRegs); - /// hasRegisterUseBelow - Return true if the specified register is used after - /// the current instruction and before its next definition. - bool hasRegisterUseBelow(unsigned Reg, MachineBasicBlock::iterator I, - MachineBasicBlock *MBB); - /// analyzePHINodes - Gather information about the PHI nodes in here. In /// particular, we want to map the variable information of a virtual /// register which is used in a PHI node. We map that to the BB the vreg /// is coming from. void analyzePHINodes(const MachineFunction& Fn); + + void runOnInstr(MachineInstr *MI, SmallVectorImpl &Defs); + + void runOnBlock(MachineBasicBlock *MBB, unsigned NumRegs); public: - virtual bool runOnMachineFunction(MachineFunction &MF); + bool runOnMachineFunction(MachineFunction &MF) override; /// RegisterDefIsDead - Return true if the specified instruction defines the /// specified register, but that definition is dead. @@ -215,6 +224,7 @@ public: } assert(Removed && "Register is not used by this instruction!"); + (void)Removed; return true; } @@ -249,12 +259,13 @@ public: } } assert(Removed && "Register is not defined by this instruction!"); + (void)Removed; return true; } - - void getAnalysisUsage(AnalysisUsage &AU) const; - virtual void releaseMemory() { + void getAnalysisUsage(AnalysisUsage &AU) const override; + + void releaseMemory() override { VirtRegInfo.clear(); } @@ -270,6 +281,29 @@ public: void HandleVirtRegDef(unsigned reg, MachineInstr *MI); void HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB, MachineInstr *MI); + + bool isLiveIn(unsigned Reg, const MachineBasicBlock &MBB) { + return getVarInfo(Reg).isLiveIn(MBB, Reg, *MRI); + } + + /// isLiveOut - Determine if Reg is live out from MBB, when not considering + /// PHI nodes. This means that Reg is either killed by a successor block or + /// passed through one. + bool isLiveOut(unsigned Reg, const MachineBasicBlock &MBB); + + /// addNewBlock - Add a new basic block BB between DomBB and SuccBB. All + /// variables that are live out of DomBB and live into SuccBB will be marked + /// as passing live through BB. This method assumes that the machine code is + /// still in SSA form. + void addNewBlock(MachineBasicBlock *BB, + MachineBasicBlock *DomBB, + MachineBasicBlock *SuccBB); + + /// isPHIJoin - Return true if Reg is a phi join register. + bool isPHIJoin(unsigned Reg) { return PHIJoins.test(Reg); } + + /// setPHIJoin - Mark Reg as a phi join register. + void setPHIJoin(unsigned Reg) { PHIJoins.set(Reg); } }; } // End llvm namespace