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!");
189LiveVariables::FindLastPartialDef(
Register Reg,
191 unsigned LastDefReg = 0;
192 unsigned LastDefDist = 0;
198 unsigned Dist = DistanceMap[Def];
199 if (Dist > LastDefDist) {
209 PartDefRegs.
insert(LastDefReg);
211 if (MO.getReg() == 0)
228 if (!LastDef && !PhysRegUse[Reg]) {
238 MachineInstr *LastPartialDef = FindLastPartialDef(Reg, PartDefRegs);
240 if (LastPartialDef) {
243 PhysRegDef[
Reg] = LastPartialDef;
255 PhysRegDef[
SubReg] = LastPartialDef;
260 }
else if (LastDef && !PhysRegUse[Reg] &&
276 if (!LastDef && !LastUse)
279 MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef;
280 unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef];
281 unsigned LastPartDefDist = 0;
284 if (Def && Def != LastDef) {
287 unsigned Dist = DistanceMap[
Def];
288 if (Dist > LastPartDefDist)
289 LastPartDefDist = Dist;
291 unsigned Dist = DistanceMap[
Use];
292 if (Dist > LastRefOrPartRefDist) {
293 LastRefOrPartRefDist = Dist;
294 LastRefOrPartRef =
Use;
299 return LastRefOrPartRef;
305 if (!LastDef && !LastUse)
308 MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef;
309 unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef];
328 unsigned LastPartDefDist = 0;
332 if (Def && Def != LastDef) {
335 unsigned Dist = DistanceMap[
Def];
336 if (Dist > LastPartDefDist) {
337 LastPartDefDist = Dist;
345 unsigned Dist = DistanceMap[
Use];
346 if (Dist > LastRefOrPartRefDist) {
347 LastRefOrPartRefDist = Dist;
348 LastRefOrPartRef =
Use;
353 if (!PhysRegUse[Reg]) {
358 PhysRegDef[
Reg]->addRegisterDead(Reg, TRI,
true);
363 if (PhysRegDef[Reg] == PhysRegDef[
SubReg]) {
365 PhysRegDef[
Reg]->findRegisterDefOperand(
SubReg,
nullptr);
380 PhysRegUse[
SS] = LastRefOrPartRef;
385 }
else if (LastRefOrPartRef == PhysRegDef[Reg] && LastRefOrPartRef !=
MI) {
410void LiveVariables::HandleRegMask(
const MachineOperand &MO,
unsigned NumRegs) {
414 for (
unsigned Reg = 1;
Reg != NumRegs; ++
Reg) {
416 if (!PhysRegDef[Reg] && !PhysRegUse[Reg])
423 unsigned Super =
Reg;
425 if (SR < NumRegs && (PhysRegDef[SR] || PhysRegUse[SR]) &&
428 HandlePhysRegKill(Super,
nullptr);
436 if (PhysRegDef[Reg] || PhysRegUse[Reg]) {
458 HandlePhysRegKill(Reg,
MI);
473 while (!Defs.
empty()) {
477 PhysRegUse[
SubReg] =
nullptr;
487 unsigned NumOperandsToProcess =
MI.getNumOperands();
492 NumOperandsToProcess = 1;
498 for (
unsigned i = 0; i != NumOperandsToProcess; ++i) {
524 for (
unsigned MOReg : UseRegs) {
528 HandlePhysRegUse(MOReg,
MI);
532 for (
unsigned Mask : RegMasks)
533 HandleRegMask(
MI.getOperand(Mask), NumRegs);
536 for (
unsigned MOReg : DefRegs) {
540 HandlePhysRegDef(MOReg, &
MI, Defs);
542 UpdatePhysRegDefs(
MI, Defs);
550 "Cannot have a live-in virtual register!");
551 HandlePhysRegDef(LI.PhysReg,
nullptr, Defs);
558 if (
MI.isDebugOrPseudoInstr())
560 DistanceMap.insert(std::make_pair(&
MI, Dist++));
562 runOnInstr(
MI, Defs, NumRegs);
572 for (
unsigned I : VarInfoVec)
582 if (SuccMBB->isEHPad())
584 for (
const auto &LI : SuccMBB->liveins()) {
587 LiveOuts.
insert(LI.PhysReg);
593 for (
unsigned i = 0; i != NumRegs; ++i)
594 if ((PhysRegDef[i] || PhysRegUse[i]) && !LiveOuts.
count(i))
595 HandlePhysRegDef(i,
nullptr, Defs);
604 PhysRegDef.assign(NumRegs,
nullptr);
605 PhysRegUse.assign(NumRegs,
nullptr);
624 runOnBlock(
MBB, NumRegs);
626 PhysRegDef.assign(NumRegs,
nullptr);
627 PhysRegUse.assign(NumRegs,
nullptr);
632 for (
unsigned i = 0, e1 =
VirtRegInfo.size(); i != e1; ++i) {
634 for (
unsigned j = 0, e2 =
VirtRegInfo[Reg].Kills.size(); j != e2; ++j)
636 VirtRegInfo[Reg].Kills[j]->addRegisterDead(Reg, TRI);
638 VirtRegInfo[Reg].Kills[j]->addRegisterKilled(Reg, TRI);
660 VI.AliveBlocks.clear();
672 unsigned NumRealUses = 0;
674 UseMO.setIsKill(
false);
675 if (!UseMO.readsReg())
684 unsigned Idx = UseMO.getOperandNo();
686 }
else if (&UseBB == &DefBB) {
695 if (NumRealUses == 0) {
696 VI.Kills.push_back(&
DefMI);
697 DefMI.addRegisterDead(Reg,
nullptr);
700 DefMI.clearRegisterDeads(Reg);
703 bool LiveToEndOfDefBB =
false;
704 while (!LiveToEndBlocks.
empty()) {
707 LiveToEndOfDefBB =
true;
719 for (
unsigned UseBBNum : UseBlocks) {
720 if (VI.AliveBlocks.test(UseBBNum))
723 if (&UseBB == &DefBB && LiveToEndOfDefBB)
726 if (
MI.isDebugOrPseudoInstr())
730 if (
MI.readsVirtualRegister(Reg)) {
731 assert(!
MI.killsRegister(Reg,
nullptr));
732 MI.addRegisterKilled(Reg,
nullptr);
733 VI.Kills.push_back(&
MI);
745 std::replace(VI.Kills.begin(), VI.Kills.end(), &OldMI, &NewMI);
755 if (Reg.isVirtual()) {
757 assert(removed &&
"kill not in register's VarInfo?");
769 for (
const auto &
MBB : Fn)
770 for (
const auto &BBI :
MBB) {
773 for (
unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2)
774 if (BBI.getOperand(i).readsReg())
775 PHIVarInfo[BBI.getOperand(i + 1).getMBB()->getNumber()]
776 .push_back(BBI.getOperand(i).getReg());
785 if (AliveBlocks.test(Num))
790 if (Def && Def->getParent() == &
MBB)
794 return findKill(&
MBB);
808 unsigned SuccIdx = SuccMBB->getNumber();
809 if (VI.AliveBlocks.test(SuccIdx))
812 if (Kills.
count(SuccMBB))
830 for (; BBI != BBE && BBI->isPHI(); ++BBI) {
832 Defs.
insert(BBI->getOperand(0).getReg());
835 for (
unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
836 if (BBI->getOperand(i+1).getMBB() == BB)
841 for (; BBI != BBE; ++BBI) {
843 if (
Op.isReg() &&
Op.getReg().isVirtual()) {
846 else if (
Op.isKill())
864 VI.AliveBlocks.set(NumNew);
879 for (
unsigned R : BV) {
882 VI.AliveBlocks.set(NumNew);
887 BBI != BBE && BBI->isPHI(); ++BBI) {
888 for (
unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
889 if (BBI->getOperand(i + 1).getMBB() == BB &&
890 BBI->getOperand(i).readsReg())
unsigned const MachineRegisterInfo * MRI
MachineInstrBuilder & UseMI
MachineInstrBuilder MachineInstrBuilder & DefMI
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
Looks at all the uses of the given value Returns the Liveness deduced from the uses of this value Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses If the result is Live
This file defines the DenseSet and SmallDenseSet classes.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallSet class.
Represent the analysis usage information of a pass.
This class represents an Operation in the Expression.
Implements a dense probed hash-table based set.
void replaceKillInstruction(Register Reg, MachineInstr &OldMI, MachineInstr &NewMI)
replaceKillInstruction - Update register kill info by replacing a kill instruction with a new one.
void MarkVirtRegAliveInBlock(VarInfo &VRInfo, MachineBasicBlock *DefBlock, MachineBasicBlock *BB)
void removeVirtualRegistersKilled(MachineInstr &MI)
removeVirtualRegistersKilled - Remove all killed info for the specified instruction.
bool isLiveOut(Register Reg, const MachineBasicBlock &MBB)
isLiveOut - Determine if Reg is live out from MBB, when not considering PHI nodes.
void HandleVirtRegDef(Register reg, MachineInstr &MI)
void recomputeForSingleDefVirtReg(Register Reg)
Recompute liveness from scratch for a virtual register Reg that is known to have a single def that do...
void HandleVirtRegUse(Register reg, MachineBasicBlock *MBB, MachineInstr &MI)
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
VarInfo & getVarInfo(Register Reg)
getVarInfo - Return the VarInfo structure for the specified VIRTUAL register.
void addNewBlock(MachineBasicBlock *BB, MachineBasicBlock *DomBB, MachineBasicBlock *SuccBB)
addNewBlock - Add a new basic block BB between DomBB and SuccBB.
iterator_range< MCSuperRegIterator > superregs(MCRegister Reg) const
Return an iterator range over all super-registers of Reg, excluding Reg.
iterator_range< MCSubRegIterator > subregs_inclusive(MCRegister Reg) const
Return an iterator range over all sub-registers of Reg, including Reg.
bool isSubRegister(MCRegister RegA, MCRegister RegB) const
Returns true if RegB is a sub-register of RegA.
iterator_range< MCSubRegIterator > subregs(MCRegister Reg) const
Return an iterator range over all sub-registers of Reg, excluding Reg.
iterator_range< livein_iterator > liveins() const
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
pred_reverse_iterator pred_rbegin()
pred_reverse_iterator pred_rend()
pred_iterator pred_begin()
iterator_range< succ_iterator > successors()
iterator_range< pred_iterator > predecessors()
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
const MachineBasicBlock & front() const
Representation of each machine instruction.
const MachineBasicBlock * getParent() const
void addOperand(MachineFunction &MF, const MachineOperand &Op)
Add the specified operand to the instruction.
bool addRegisterKilled(Register IncomingReg, const TargetRegisterInfo *RegInfo, bool AddIfNotFound=false)
We have determined MI kills a register.
iterator_range< filtered_mop_iterator > all_defs()
Returns an iterator range over all operands that are (explicit or implicit) register defs.
MachineOperand * findRegisterDefOperand(Register Reg, const TargetRegisterInfo *TRI, bool isDead=false, bool Overlap=false)
Wrapper for findRegisterDefOperandIdx, it returns a pointer to the MachineOperand rather than an inde...
bool addRegisterDead(Register Reg, const TargetRegisterInfo *RegInfo, bool AddIfNotFound=false)
We have determined MI defined a register without a use.
MachineOperand class - Representation of each machine instruction operand.
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
void setIsDead(bool Val=true)
void setIsKill(bool Val=true)
void setIsEarlyClobber(bool Val=true)
bool isEarlyClobber() const
Register getReg() const
getReg - Returns the register number.
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
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)
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
iterator_range< use_nodbg_iterator > use_nodbg_operands(Register Reg) const
bool isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
MachineInstr * getUniqueVRegDef(Register Reg) const
getUniqueVRegDef - Return the unique machine instr that defines the specified virtual register or nul...
Wrapper class representing virtual and physical registers.
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
static constexpr bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
static constexpr bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
iterator insert(iterator I, T &&Elt)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
bool test(unsigned Idx) const
virtual unsigned getNumSupportedRegs(const MachineFunction &) const
Return the number of registers for the function. (may overestimate)
bool isInAllocatableClass(MCRegister RegNo) const
Return true if the register is in the allocation of any register class.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
A Use represents the edge between a Value definition and its users.
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.
Reg
All possible values of the reg field in the ModR/M byte.
NodeAddr< DefNode * > Def
This is an optimization pass for GlobalISel generic memory operations.
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
auto reverse(ContainerTy &&C)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
char & LiveVariablesID
LiveVariables pass - This pass computes the set of blocks in which each variable is life and sets mac...
char & UnreachableMachineBlockElimID
UnreachableMachineBlockElimination - This pass removes unreachable machine basic blocks.
VarInfo - This represents the regions where a virtual register is live in the program.
bool removeKill(MachineInstr &MI)
removeKill - Delete a kill corresponding to the specified machine instruction.
std::vector< MachineInstr * > Kills
Kills - List of MachineInstruction's which are the last use of this virtual register (kill it) in the...
SparseBitVector AliveBlocks
AliveBlocks - Set of blocks in which this value is alive completely through.
MachineInstr * findKill(const MachineBasicBlock *MBB) const
findKill - Find a kill instruction in MBB. Return NULL if none is found.
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.
VirtRegInfo - Information about a virtual register used by a set of operands.