X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FLiveVariables.h;h=3bb134b8fb2ad5ff45a912f7ea4e463f1e061ee9;hb=3d71688476951d56ac00a81b17c2f83fd781b208;hp=18fa6f1f02b825dbb46a760158930286abec8d70;hpb=ae73dc1448d25b02cabc7c64c86c64371453dda8;p=oota-llvm.git diff --git a/include/llvm/CodeGen/LiveVariables.h b/include/llvm/CodeGen/LiveVariables.h index 18fa6f1f02b..3bb134b8fb2 100644 --- a/include/llvm/CodeGen/LiveVariables.h +++ b/include/llvm/CodeGen/LiveVariables.h @@ -29,11 +29,16 @@ #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/Target/TargetRegisterInfo.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" namespace llvm { @@ -43,24 +48,26 @@ 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 - /// information: the instruction that uniquely defines the value, the set of - /// blocks the instruction is live into and live out of, and the set of - /// non-phi instructions that are the last users of the value. + /// information: the set of blocks in which the instruction is live + /// throughout, the set of blocks in which the instruction is actually used, + /// and the set of non-phi instructions that are the last users of the value. /// /// In the common case where a value is defined and killed in the same block, - /// There is one killing instruction, and AliveBlocks is empty. + /// There is one killing instruction, and AliveBlocks is empty. /// /// Otherwise, the value is live out of the block. If the value is live - /// across any blocks, these blocks are listed in AliveBlocks. Blocks where - /// the liveness range ends are not included in AliveBlocks, instead being - /// captured by the Kills set. In these blocks, the value is live into the - /// block (unless the value is defined and killed in the same block) and lives - /// until the specified instruction. Note that there cannot ever be a value - /// whose Kills set contains two instructions from the same basic block. + /// throughout any blocks, these blocks are listed in AliveBlocks. Blocks + /// where the liveness range ends are not included in AliveBlocks, instead + /// being captured by the Kills set. In these blocks, the value is live into + /// the block (unless the value is defined and killed in the same block) and + /// lives until the specified instruction. Note that there cannot ever be a + /// value whose Kills set contains two instructions from the same basic block. /// /// PHI nodes complicate things a bit. If a PHI node is the last user of a /// value in one of its predecessor blocks, it is not listed in the kills set, @@ -72,27 +79,17 @@ public: /// included). This is sensical because the value must be live to the end of /// the block, but is not live in any successor blocks. struct VarInfo { - /// AliveBlocks - Set of blocks of which this value is alive completely + /// AliveBlocks - Set of blocks in which this value is alive completely /// through. This is a bit set which uses the basic block number as an /// index. /// - BitVector AliveBlocks; - - /// UsedBlocks - Set of blocks of which this value is actually used. This - /// is a bit set which uses the basic block number as an index. - BitVector UsedBlocks; - - /// NumUses - Number of uses of this register across the entire function. - /// - unsigned NumUses; + SparseBitVector<> AliveBlocks; /// 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. @@ -104,22 +101,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; @@ -147,19 +152,25 @@ private: // Intermediate data structures /// HandlePhysRegKill - Add kills of Reg and its sub-registers to the /// uses. Pay special attention to the sub-register uses which may come below /// the last use of the whole register. - bool HandlePhysRegKill(unsigned Reg); + 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); + void HandlePhysRegDef(unsigned Reg, MachineInstr *MI, + SmallVector &Defs); + void UpdatePhysRegDefs(MachineInstr *MI, SmallVector &Defs); - /// FindLastPartialDef - Return the last partial def of the specified register. - /// Also returns the sub-register that's defined. - MachineInstr *FindLastPartialDef(unsigned Reg, unsigned &PartDefReg); + /// FindLastRefOrPartRef - Return the last reference or partial reference of + /// the specified register. + MachineInstr *FindLastRefOrPartRef(unsigned Reg); - /// hasRegisterUseBelow - Return true if the specified register is used after - /// the current instruction and before it's next definition. - bool hasRegisterUseBelow(unsigned Reg, MachineBasicBlock::iterator I, - MachineBasicBlock *MBB); + /// 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); /// analyzePHINodes - Gather information about the PHI nodes in here. In /// particular, we want to map the variable information of a virtual @@ -203,7 +214,7 @@ public: bool Removed = false; for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); - if (MO.isRegister() && MO.isKill() && MO.getReg() == reg) { + if (MO.isReg() && MO.isKill() && MO.getReg() == reg) { MO.setIsKill(false); Removed = true; break; @@ -211,6 +222,7 @@ public: } assert(Removed && "Register is not used by this instruction!"); + (void)Removed; return true; } @@ -238,13 +250,14 @@ public: bool Removed = false; for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); - if (MO.isRegister() && MO.isDef() && MO.getReg() == reg) { + if (MO.isReg() && MO.isDef() && MO.getReg() == reg) { MO.setIsDead(false); Removed = true; break; } } assert(Removed && "Register is not defined by this instruction!"); + (void)Removed; return true; } @@ -263,8 +276,32 @@ public: void MarkVirtRegAliveInBlock(VarInfo& VRInfo, MachineBasicBlock* DefBlock, MachineBasicBlock *BB, std::vector &WorkList); + 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