#ifndef LLVM_CODEGEN_LIVEVARIABLES_H
#define LLVM_CODEGEN_LIVEVARIABLES_H
-#include "llvm/CodeGen/MachineFunctionPass.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
- /// 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,
/// 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<MachineInstr*> 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.
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<VarInfo> VirtRegInfo;
+ IndexedMap<VarInfo, VirtReg2IndexFunctor> 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;
// 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<MachineInstr *> 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<MachineInstr *> PhysRegUse;
- SmallVector<unsigned, 4> *PHIVarInfo;
+ std::vector<SmallVector<unsigned, 4>> PHIVarInfo;
// DistanceMap - Keep track the distance of a MI from the start of the
// current basic block.
/// 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,
+ SmallVectorImpl<unsigned> &Defs);
+ void UpdatePhysRegDefs(MachineInstr *MI, SmallVectorImpl<unsigned> &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<unsigned,4> &PartDefRegs);
/// 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<unsigned> &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.
}
assert(Removed && "Register is not used by this instruction!");
+ (void)Removed;
return true;
}
}
}
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();
}
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