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]) {
379 PhysRegUse[
SS] = LastRefOrPartRef;
384 }
else if (LastRefOrPartRef == PhysRegDef[Reg] && LastRefOrPartRef !=
MI) {
409void LiveVariables::HandleRegMask(
const MachineOperand &MO,
unsigned NumRegs) {
413 for (
unsigned Reg = 1;
Reg != NumRegs; ++
Reg) {
415 if (!PhysRegDef[Reg] && !PhysRegUse[Reg])
422 unsigned Super =
Reg;
424 if (SR < NumRegs && (PhysRegDef[SR] || PhysRegUse[SR]) &&
427 HandlePhysRegKill(Super,
nullptr);
435 if (PhysRegDef[Reg] || PhysRegUse[Reg]) {
457 HandlePhysRegKill(Reg,
MI);
472 while (!Defs.
empty()) {
476 PhysRegUse[
SubReg] =
nullptr;
486 unsigned NumOperandsToProcess =
MI.getNumOperands();
491 NumOperandsToProcess = 1;
497 for (
unsigned i = 0; i != NumOperandsToProcess; ++i) {
523 for (
unsigned MOReg : UseRegs) {
527 HandlePhysRegUse(MOReg,
MI);
531 for (
unsigned Mask : RegMasks)
532 HandleRegMask(
MI.getOperand(Mask), NumRegs);
535 for (
unsigned MOReg : DefRegs) {
539 HandlePhysRegDef(MOReg, &
MI, Defs);
541 UpdatePhysRegDefs(
MI, Defs);
549 "Cannot have a live-in virtual register!");
550 HandlePhysRegDef(LI.PhysReg,
nullptr, Defs);
557 if (
MI.isDebugOrPseudoInstr())
559 DistanceMap.insert(std::make_pair(&
MI, Dist++));
561 runOnInstr(
MI, Defs, NumRegs);
571 for (
unsigned I : VarInfoVec)
581 if (SuccMBB->isEHPad())
583 for (
const auto &LI : SuccMBB->liveins()) {
586 LiveOuts.
insert(LI.PhysReg);
592 for (
unsigned i = 0; i != NumRegs; ++i)
593 if ((PhysRegDef[i] || PhysRegUse[i]) && !LiveOuts.
count(i))
594 HandlePhysRegDef(i,
nullptr, Defs);
603 PhysRegDef.assign(NumRegs,
nullptr);
604 PhysRegUse.assign(NumRegs,
nullptr);
623 runOnBlock(
MBB, NumRegs);
625 PhysRegDef.assign(NumRegs,
nullptr);
626 PhysRegUse.assign(NumRegs,
nullptr);
631 for (
unsigned i = 0, e1 =
VirtRegInfo.size(); i != e1; ++i) {
633 for (
unsigned j = 0, e2 =
VirtRegInfo[Reg].Kills.size(); j != e2; ++j)
635 VirtRegInfo[Reg].Kills[j]->addRegisterDead(Reg, TRI);
637 VirtRegInfo[Reg].Kills[j]->addRegisterKilled(Reg, TRI);
659 VI.AliveBlocks.clear();
671 unsigned NumRealUses = 0;
673 UseMO.setIsKill(
false);
674 if (!UseMO.readsReg())
683 unsigned Idx = UseMO.getOperandNo();
685 }
else if (&UseBB == &DefBB) {
694 if (NumRealUses == 0) {
695 VI.Kills.push_back(&
DefMI);
696 DefMI.addRegisterDead(Reg,
nullptr);
699 DefMI.clearRegisterDeads(Reg);
702 bool LiveToEndOfDefBB =
false;
703 while (!LiveToEndBlocks.
empty()) {
706 LiveToEndOfDefBB =
true;
718 for (
unsigned UseBBNum : UseBlocks) {
719 if (VI.AliveBlocks.test(UseBBNum))
722 if (&UseBB == &DefBB && LiveToEndOfDefBB)
725 if (
MI.isDebugOrPseudoInstr())
729 if (
MI.readsVirtualRegister(Reg)) {
731 MI.addRegisterKilled(Reg,
nullptr);
732 VI.Kills.push_back(&
MI);
744 std::replace(VI.Kills.begin(), VI.Kills.end(), &OldMI, &NewMI);
754 if (Reg.isVirtual()) {
756 assert(removed &&
"kill not in register's VarInfo?");
768 for (
const auto &
MBB : Fn)
769 for (
const auto &BBI :
MBB) {
772 for (
unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2)
773 if (BBI.getOperand(i).readsReg())
774 PHIVarInfo[BBI.getOperand(i + 1).getMBB()->getNumber()]
775 .push_back(BBI.getOperand(i).getReg());
784 if (AliveBlocks.test(Num))
789 if (Def && Def->getParent() == &
MBB)
793 return findKill(&
MBB);
807 unsigned SuccIdx = SuccMBB->getNumber();
808 if (VI.AliveBlocks.test(SuccIdx))
811 if (Kills.
count(SuccMBB))
829 for (; BBI != BBE && BBI->isPHI(); ++BBI) {
831 Defs.
insert(BBI->getOperand(0).getReg());
834 for (
unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
835 if (BBI->getOperand(i+1).getMBB() == BB)
840 for (; BBI != BBE; ++BBI) {
842 if (
Op.isReg() &&
Op.getReg().isVirtual()) {
845 else if (
Op.isKill())
863 VI.AliveBlocks.set(NumNew);
878 for (
unsigned R : BV) {
881 VI.AliveBlocks.set(NumNew);
886 BBI != BBE && BBI->isPHI(); ++BBI) {
887 for (
unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
888 if (BBI->getOperand(i + 1).getMBB() == BB &&
889 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, bool isDead=false, bool Overlap=false, const TargetRegisterInfo *TRI=nullptr)
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.