Go to the documentation of this file.
37 #include "llvm/Config/llvm-config.h"
47 "Live Variable Analysis",
false,
false)
62 if (
MI->getParent() ==
MBB)
67 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
69 dbgs() <<
" Alive in blocks: ";
70 for (
unsigned AB : AliveBlocks)
72 dbgs() <<
"\n Killed by:";
74 dbgs() <<
" No instructions.\n";
76 for (
unsigned i = 0,
e = Kills.size();
i !=
e; ++
i)
77 dbgs() <<
"\n #" <<
i <<
": " << *Kills[
i];
85 assert(
Reg.isVirtual() &&
"getVarInfo: not a virtual register!");
97 for (
unsigned i = 0,
e = VRInfo.
Kills.size();
i !=
e; ++
i)
98 if (VRInfo.
Kills[
i]->getParent() ==
MBB) {
103 if (
MBB == DefBlock)
return;
111 assert(
MBB != &MF->
front() &&
"Can't find reaching def for virtreg");
121 while (!WorkList.empty()) {
136 if (!VRInfo.
Kills.empty() && VRInfo.
Kills.back()->getParent() ==
MBB) {
145 assert(
Kill->getParent() !=
MBB &&
"entry should be at end!");
191 unsigned LastDefReg = 0;
192 unsigned LastDefDist = 0;
195 unsigned SubReg = *SubRegs;
199 unsigned Dist = DistanceMap[
Def];
200 if (Dist > LastDefDist) {
210 PartDefRegs.
insert(LastDefReg);
219 PartDefRegs.
insert(*SubRegs);
231 if (!LastDef && !PhysRegUse[
Reg]) {
243 if (LastPartialDef) {
246 PhysRegDef[
Reg] = LastPartialDef;
249 unsigned SubReg = *SubRegs;
259 PhysRegDef[
SubReg] = LastPartialDef;
264 }
else if (LastDef && !PhysRegUse[
Reg] &&
273 PhysRegUse[*SubRegs] = &
MI;
281 if (!LastDef && !LastUse)
284 MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef;
285 unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef];
286 unsigned LastPartDefDist = 0;
288 unsigned SubReg = *SubRegs;
290 if (
Def &&
Def != LastDef) {
293 unsigned Dist = DistanceMap[
Def];
294 if (Dist > LastPartDefDist)
295 LastPartDefDist = Dist;
297 unsigned Dist = DistanceMap[
Use];
298 if (Dist > LastRefOrPartRefDist) {
299 LastRefOrPartRefDist = Dist;
300 LastRefOrPartRef =
Use;
305 return LastRefOrPartRef;
311 if (!LastDef && !LastUse)
314 MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef;
315 unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef];
334 unsigned LastPartDefDist = 0;
337 unsigned SubReg = *SubRegs;
339 if (
Def &&
Def != LastDef) {
342 unsigned Dist = DistanceMap[
Def];
343 if (Dist > LastPartDefDist) {
344 LastPartDefDist = Dist;
353 unsigned Dist = DistanceMap[
Use];
354 if (Dist > LastRefOrPartRefDist) {
355 LastRefOrPartRefDist = Dist;
356 LastRefOrPartRef =
Use;
361 if (!PhysRegUse[
Reg]) {
366 PhysRegDef[
Reg]->addRegisterDead(
Reg, TRI,
true);
368 unsigned SubReg = *SubRegs;
372 if (PhysRegDef[
Reg] == PhysRegDef[
SubReg]) {
389 PhysRegUse[*
SS] = LastRefOrPartRef;
394 }
else if (LastRefOrPartRef == PhysRegDef[
Reg] && LastRefOrPartRef !=
MI) {
425 if (!PhysRegDef[
Reg] && !PhysRegUse[
Reg])
432 unsigned Super =
Reg;
436 HandlePhysRegKill(Super,
nullptr);
444 if (PhysRegDef[
Reg] || PhysRegUse[
Reg]) {
450 unsigned SubReg = *SubRegs;
469 HandlePhysRegKill(
Reg,
MI);
472 unsigned SubReg = *SubRegs;
485 while (!Defs.empty()) {
488 SubRegs.
isValid(); ++SubRegs) {
489 unsigned SubReg = *SubRegs;
491 PhysRegUse[
SubReg] =
nullptr;
500 unsigned NumOperandsToProcess =
MI.getNumOperands();
505 NumOperandsToProcess = 1;
511 for (
unsigned i = 0;
i != NumOperandsToProcess; ++
i) {
514 RegMasks.push_back(
i);
524 UseRegs.push_back(MOReg);
531 DefRegs.push_back(MOReg);
537 for (
unsigned MOReg : UseRegs) {
541 HandlePhysRegUse(MOReg,
MI);
545 for (
unsigned Mask : RegMasks)
546 HandleRegMask(
MI.getOperand(
Mask));
549 for (
unsigned MOReg : DefRegs) {
553 HandlePhysRegDef(MOReg, &
MI, Defs);
555 UpdatePhysRegDefs(
MI, Defs);
563 "Cannot have a live-in virtual register!");
564 HandlePhysRegDef(LI.PhysReg,
nullptr, Defs);
571 if (
MI.isDebugOrPseudoInstr())
573 DistanceMap.insert(std::make_pair(&
MI, Dist++));
575 runOnInstr(
MI, Defs);
585 for (
unsigned I : VarInfoVec)
595 if (SuccMBB->isEHPad())
597 for (
const auto &LI : SuccMBB->liveins()) {
600 LiveOuts.
insert(LI.PhysReg);
606 for (
unsigned i = 0;
i != NumRegs; ++
i)
607 if ((PhysRegDef[
i] || PhysRegUse[
i]) && !LiveOuts.
count(
i))
608 HandlePhysRegDef(
i,
nullptr, Defs);
617 PhysRegDef.assign(NumRegs,
nullptr);
618 PhysRegUse.assign(NumRegs,
nullptr);
638 runOnBlock(
MBB, NumRegs);
640 PhysRegDef.assign(NumRegs,
nullptr);
641 PhysRegUse.assign(NumRegs,
nullptr);
674 VI.AliveBlocks.clear();
683 DefMI.addRegisterDead(
Reg,
nullptr);
695 UseMO.setIsKill(
false);
702 unsigned Idx =
UseMI.getOperandNo(&UseMO);
703 LiveToEndBlocks.push_back(
UseMI.getOperand(Idx + 1).getMBB());
704 }
else if (&UseBB == &DefBB) {
713 bool LiveToEndOfDefBB =
false;
714 while (!LiveToEndBlocks.empty()) {
717 LiveToEndOfDefBB =
true;
720 if (
VI.AliveBlocks.test(
BB.getNumber()))
722 VI.AliveBlocks.set(
BB.getNumber());
723 LiveToEndBlocks.
append(
BB.pred_begin(),
BB.pred_end());
729 for (
unsigned UseBBNum : UseBlocks) {
730 if (
VI.AliveBlocks.test(UseBBNum))
733 if (&UseBB == &DefBB && LiveToEndOfDefBB)
736 if (
MI.isDebugOrPseudoInstr())
740 if (
MI.readsRegister(
Reg)) {
742 MI.addRegisterKilled(
Reg,
nullptr);
743 VI.Kills.push_back(&
MI);
765 if (
Reg.isVirtual()) {
779 for (
const auto &
MBB : Fn)
780 for (
const auto &BBI :
MBB) {
783 for (
unsigned i = 1,
e = BBI.getNumOperands();
i !=
e;
i += 2)
784 if (BBI.getOperand(
i).readsReg())
785 PHIVarInfo[BBI.getOperand(
i + 1).getMBB()->getNumber()]
786 .push_back(BBI.getOperand(
i).getReg());
795 if (AliveBlocks.test(Num))
804 return findKill(&
MBB);
818 unsigned SuccIdx = SuccMBB->getNumber();
819 if (
VI.AliveBlocks.test(SuccIdx))
822 if (Kills.
count(SuccMBB))
835 const unsigned NumNew =
BB->getNumber();
840 for (; BBI != BBE && BBI->isPHI(); ++BBI) {
842 Defs.
insert(BBI->getOperand(0).getReg());
845 for (
unsigned i = 1,
e = BBI->getNumOperands();
i !=
e;
i += 2)
846 if (BBI->getOperand(
i+1).getMBB() ==
BB)
851 for (; BBI != BBE; ++BBI) {
853 if (
Op.isReg() &&
Op.getReg().isVirtual()) {
856 else if (
Op.isKill())
874 VI.AliveBlocks.set(NumNew);
886 const unsigned NumNew =
BB->getNumber();
889 for (
unsigned R : BV) {
892 VI.AliveBlocks.set(NumNew);
897 BBI != BBE && BBI->isPHI(); ++BBI) {
898 for (
unsigned i = 1,
e = BBI->getNumOperands();
i !=
e;
i += 2)
899 if (BBI->getOperand(
i + 1).getMBB() ==
BB &&
900 BBI->getOperand(
i).readsReg())
bool isLiveIn(const MachineBasicBlock &MBB, Register Reg, MachineRegisterInfo &MRI)
isLiveIn - Is Reg live in to MBB? This means that Reg is live through MBB, or it is killed in MBB.
bool addRegisterDead(Register Reg, const TargetRegisterInfo *RegInfo, bool AddIfNotFound=false)
We have determined MI defined a register without a use.
pred_iterator pred_begin()
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This is an optimization pass for GlobalISel generic memory operations.
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
MachineInstrBuilder & UseMI
static MachineOperand CreateReg(Register Reg, bool isDef, bool isImp=false, bool isKill=false, bool isDead=false, bool isUndef=false, bool isEarlyClobber=false, unsigned SubReg=0, bool isDebug=false, bool isInternalRead=false, bool isRenamable=false)
void MarkVirtRegAliveInBlock(VarInfo &VRInfo, MachineBasicBlock *DefBlock, MachineBasicBlock *BB)
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
void setIsKill(bool Val=true)
std::vector< MachineInstr * > Kills
Kills - List of MachineInstruction's which are the last use of this virtual register (kill it) in the...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
bool isInAllocatableClass(MCRegister RegNo) const
Return true if the register is in the allocation of any register class.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
Reg
All possible values of the reg field in the ModR/M byte.
MachineInstr * getUniqueVRegDef(Register Reg) const
getUniqueVRegDef - Return the unique machine instr that defines the specified virtual register or nul...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
iterator_range< livein_iterator > liveins() const
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
static void replace(Module &M, GlobalVariable *Old, GlobalVariable *New)
std::pair< iterator, bool > insert(const ValueT &V)
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
MachineInstr * findKill(const MachineBasicBlock *MBB) const
findKill - Find a kill instruction in MBB. Return NULL if none is found.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
const MachineBasicBlock & front() const
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
bool removeKill(MachineInstr &MI)
removeKill - Delete a kill corresponding to the specified machine instruction.
iterator_range< use_nodbg_iterator > use_nodbg_operands(Register Reg) const
VarInfo - This represents the regions where a virtual register is live in the program.
const MachineOperand & getOperand(unsigned i) const
bool isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
void recomputeForSingleDefVirtReg(Register Reg)
Recompute liveness from scratch for a virtual register Reg that is known to have a single def that do...
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Represent the analysis usage information of a pass.
bool addRegisterKilled(Register IncomingReg, const TargetRegisterInfo *RegInfo, bool AddIfNotFound=false)
We have determined MI kills a register.
void replaceKillInstruction(Register Reg, MachineInstr &OldMI, MachineInstr &NewMI)
replaceKillInstruction - Update register kill info by replacing a kill instruction with a new one.
MachineOperand class - Representation of each machine instruction operand.
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
pred_reverse_iterator pred_rbegin()
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
void HandleVirtRegDef(Register reg, MachineInstr &MI)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
void addNewBlock(MachineBasicBlock *BB, MachineBasicBlock *DomBB, MachineBasicBlock *SuccBB)
addNewBlock - Add a new basic block BB between DomBB and SuccBB.
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
void setIsDead(bool Val=true)
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Representation of each machine instruction.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
bool test(unsigned Idx) const
char & LiveVariablesID
LiveVariables pass - This pass computes the set of blocks in which each variable is life and sets mac...
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isEarlyClobber() const
currently compiles eax eax je LBB0_3 testl eax jne LBB0_4 the testl could be removed
MCSuperRegIterator enumerates all super-registers of Reg.
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
Register getReg() const
getReg - Returns the register number.
iterator_range< pred_iterator > predecessors()
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
bool use_nodbg_empty(Register RegNo) const
use_nodbg_empty - Return true if there are no non-Debug instructions using the specified register.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
char & UnreachableMachineBlockElimID
UnreachableMachineBlockElimination - This pass removes unreachable machine basic blocks.
iterator_range< succ_iterator > successors()
void setIsEarlyClobber(bool Val=true)
bool isLiveOut(Register Reg, const MachineBasicBlock &MBB)
isLiveOut - Determine if Reg is live out from MBB, when not considering PHI nodes.
const MachineBasicBlock * getParent() const
unsigned const MachineRegisterInfo * MRI
Wrapper class representing virtual and physical registers.
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register.
bool isSubRegister(MCRegister RegA, MCRegister RegB) const
Returns true if RegB is a sub-register of RegA.
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
void removeVirtualRegistersKilled(MachineInstr &MI)
removeVirtualRegistersKilled - Remove all killed info for the specified instruction.
MCSubRegIterator enumerates all sub-registers of Reg.
@ Kill
The last use of a register.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
MachineInstrBuilder MachineInstrBuilder & DefMI
unsigned getNumOperands() const
Retuns the total number of operands.
void addOperand(MachineFunction &MF, const MachineOperand &Op)
Add the specified operand to the instruction.
void HandleVirtRegUse(Register reg, MachineBasicBlock *MBB, MachineInstr &MI)
VarInfo & getVarInfo(Register Reg)
getVarInfo - Return the VarInfo structure for the specified VIRTUAL register.
INITIALIZE_PASS_BEGIN(LiveVariables, "livevars", "Live Variable Analysis", false, false) INITIALIZE_PASS_END(LiveVariables
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
auto reverse(ContainerTy &&C)
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
pred_reverse_iterator pred_rend()
VirtRegInfo - Information about a virtual register used by a set of operands.
bool contains(ConstPtrType Ptr) const
MachineOperand * findRegisterDefOperand(Register Reg, bool isDead=false, bool Overlap=false, const TargetRegisterInfo *TRI=nullptr)
Wrapper for findRegisterDefOperandIdx, it returns a pointer to the MachineOperand rather than an inde...
A Use represents the edge between a Value definition and its users.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
iterator insert(iterator I, T &&Elt)
SparseBitVector AliveBlocks
AliveBlocks - Set of blocks in which this value is alive completely through.