#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 {
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
/// through. This is a bit set which uses the basic block number as an
/// index.
///
- BitVector AliveBlocks;
-
- /// UsedBlocks - Set of blocks in 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;
+
+ /// 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;
/// ReservedRegisters - This vector keeps track of which registers
/// are reserved register which are not allocatable by the target machine.
/// 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<unsigned, 4> &Defs);
+ void UpdatePhysRegDefs(MachineInstr *MI, SmallVector<unsigned, 4> &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
}
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 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