19#define DEBUG_TYPE "reaching-deps-analysis"
26 return MO.isReg() && MO.getReg();
30 return isValidReg(MO) && MO.
isUse();
37 return TRI->regsOverlap(MO.
getReg(), PhysReg);
41 return isValidReg(MO) && MO.
isDef();
48 return TRI->regsOverlap(MO.
getReg(), PhysReg);
54 "Unexpected basic block number.");
55 MBBReachingDefs[MBBNumber].
resize(NumRegUnits);
63 LiveRegs.assign(NumRegUnits, ReachingDefDefaultVal);
72 if (LiveRegs[*Unit] != -1) {
74 MBBReachingDefs[MBBNumber][*Unit].
push_back(-1);
85 "Should have pre-allocated MBBInfos for all MBBs");
86 const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[
pred->getNumber()];
93 for (
unsigned Unit = 0; Unit != NumRegUnits; ++Unit)
94 LiveRegs[Unit] = std::max(LiveRegs[Unit], Incoming[Unit]);
98 for (
unsigned Unit = 0; Unit != NumRegUnits; ++Unit)
99 if (LiveRegs[Unit] != ReachingDefDefaultVal)
100 MBBReachingDefs[MBBNumber][Unit].
push_back(LiveRegs[Unit]);
104 assert(!LiveRegs.empty() &&
"Must enter basic block first.");
107 "Unexpected basic block number.");
109 MBBOutRegsInfos[MBBNumber] = LiveRegs;
115 for (
int &OutLiveReg : MBBOutRegsInfos[MBBNumber])
116 if (OutLiveReg != ReachingDefDefaultVal)
117 OutLiveReg -= CurInstr;
122 assert(!
MI->isDebugInstr() &&
"Won't process debug instructions");
124 unsigned MBBNumber =
MI->getParent()->getNumber();
126 "Unexpected basic block number.");
128 for (
auto &MO :
MI->operands()) {
138 if (LiveRegs[*Unit] != CurInstr) {
139 LiveRegs[*Unit] = CurInstr;
140 MBBReachingDefs[MBBNumber][*Unit].
push_back(CurInstr);
144 InstIds[
MI] = CurInstr;
151 "Unexpected basic block number.");
156 int NumInsts = std::distance(NonDbgInsts.begin(), NonDbgInsts.end());
162 "Should have pre-allocated MBBInfos for all MBBs");
163 const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[
pred->getNumber()];
165 if (Incoming.empty())
168 for (
unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
169 int Def = Incoming[Unit];
170 if (Def == ReachingDefDefaultVal)
173 auto Start = MBBReachingDefs[MBBNumber][Unit].
begin();
174 if (Start != MBBReachingDefs[MBBNumber][Unit].
end() && *Start < 0) {
182 MBBReachingDefs[MBBNumber][Unit].
insert(Start, Def);
187 if (MBBOutRegsInfos[MBBNumber][Unit] < Def - NumInsts)
188 MBBOutRegsInfos[MBBNumber][Unit] =
Def - NumInsts;
193void ReachingDefAnalysis::processBasicBlock(
197 << (!TraversedMBB.
IsDone ?
": incomplete\n"
198 :
": all preds known\n"));
202 reprocessBasicBlock(
MBB);
206 enterBasicBlock(
MBB);
210 leaveBasicBlock(
MBB);
216 LLVM_DEBUG(
dbgs() <<
"********** REACHING DEFINITION ANALYSIS **********\n");
224 MBBOutRegsInfos.
clear();
225 MBBReachingDefs.
clear();
242 TraversedMBBOrder = Traversal.
traverse(*MF);
248 processBasicBlock(TraversedMBB);
251 for (MBBDefsInfo &MBBDefs : MBBReachingDefs) {
253 int LastDef = ReachingDefDefaultVal;
254 for (
int Def : RegUnitDefs) {
255 assert(Def > LastDef &&
"Defs must be sorted and unique");
265 assert(InstIds.count(
MI) &&
"Unexpected machine instuction.");
266 int InstId = InstIds.lookup(
MI);
267 int DefRes = ReachingDefDefaultVal;
268 unsigned MBBNumber =
MI->getParent()->getNumber();
270 "Unexpected basic block number.");
271 int LatestDef = ReachingDefDefaultVal;
273 for (
int Def : MBBReachingDefs[MBBNumber][*Unit]) {
278 LatestDef = std::max(LatestDef, DefRes);
295 if (ParentA != ParentB)
304 "Unexpected basic block number.");
306 "Unexpected instruction id.");
311 for (
auto &
MI : *
MBB) {
312 auto F = InstIds.find(&
MI);
313 if (
F != InstIds.end() &&
F->second == InstId)
322 assert(InstIds.count(
MI) &&
"Unexpected machine instuction.");
337 if (
MI->isDebugInstr())
342 if (getReachingLocalMIDef(&*
MI, PhysReg) != Def)
345 for (
auto &MO :
MI->operands()) {
361 for (
auto &MO :
MI.operands()) {
389 while (!ToVisit.
empty()) {
408 for (
auto *
MBB :
MI->getParent()->predecessors())
442 if (LocalDef && InstIds.lookup(LocalDef) < InstIds.lookup(
MI))
453 if (Incoming.
size() == 1 && (*Incoming.
begin())->getParent() != Parent)
454 return *Incoming.
begin();
459 unsigned Idx)
const {
460 assert(
MI->getOperand(
Idx).isReg() &&
"Expected register operand");
486 return InstIds.lookup(&
Last) > InstIds.lookup(
MI);
500 return Def == getReachingLocalMIDef(
MI, PhysReg);
519 for (
auto &MO :
Last->operands())
539 for (
auto &MO :
Last->operands())
543 return Def < 0 ? nullptr : getInstFromId(
MBB, Def);
547 return MI.mayLoadOrStore() ||
MI.mayRaiseFPException() ||
548 MI.hasUnmodeledSideEffects() ||
MI.isTerminator() ||
549 MI.isCall() ||
MI.isBarrier() ||
MI.isBranch() ||
MI.isReturn();
555template<
typename Iterator>
563 for (
auto &MO :
From->operands()) {
575 for (
auto I = ++Iterator(
From),
E = Iterator(To);
I !=
E; ++
I) {
578 for (
auto &MO :
I->operands())
579 if (MO.isReg() && MO.getReg() && Defs.
count(MO.getReg()))
589 for (
auto I = Iterator(
From),
E =
From->getParent()->end();
I !=
E; ++
I)
591 return isSafeToMove<Iterator>(
From, To);
599 for (
auto I = Iterator(
From),
E =
From->getParent()->rend();
I !=
E; ++
I)
601 return isSafeToMove<Iterator>(
From, To);
631 for (
auto &MO :
MI->operands()) {
638 for (
auto *
I :
Uses) {
656 unsigned LiveDefs = 0;
657 for (
auto &MO : Def->operands()) {
672 for (
auto &MO :
MI->operands()) {
676 if (
IsDead(Def, MO.getReg()))
691 if (
auto *Def = getReachingLocalMIDef(
MI, PhysReg)) {
707 for (
auto &MO :
I->operands())
ReachingDefAnalysis InstSet & ToRemove
ReachingDefAnalysis InstSet InstSet & Ignore
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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
Rewrite Partial Register Uses
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
unsigned const TargetRegisterInfo * TRI
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
static bool mayHaveSideEffects(MachineInstr &MI)
static bool isValidRegDefOf(const MachineOperand &MO, MCRegister PhysReg, const TargetRegisterInfo *TRI)
static bool isValidRegDef(const MachineOperand &MO)
static bool isValidRegUseOf(const MachineOperand &MO, MCRegister PhysReg, const TargetRegisterInfo *TRI)
static bool isValidRegUse(const MachineOperand &MO)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines generic set operations that may be used on set's of different types,...
This file defines the SmallSet class.
A set of physical registers with utility functions to track liveness when walking backward/forward th...
bool available(const MachineRegisterInfo &MRI, MCPhysReg Reg) const
Returns true if register Reg and no aliasing register is in the set.
void stepBackward(const MachineInstr &MI)
Simulates liveness when stepping backwards over an instruction(bundle).
void addLiveOuts(const MachineBasicBlock &MBB)
Adds all live-out registers of basic block MBB.
This class provides the basic blocks traversal order used by passes like ReachingDefAnalysis and Exec...
TraversalOrder traverse(MachineFunction &MF)
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
Wrapper class representing physical registers. Should be passed by value.
instr_iterator instr_begin()
iterator_range< livein_iterator > liveins() const
reverse_instr_iterator instr_rbegin()
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
reverse_instr_iterator instr_rend()
iterator getLastNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the last non-debug instruction in the basic block, or end().
MachineInstrBundleIterator< MachineInstr, true > reverse_iterator
instr_iterator instr_end()
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator_range< succ_iterator > successors()
iterator_range< pred_iterator > predecessors()
MachineInstrBundleIterator< MachineInstr > iterator
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.
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
Representation of each machine instruction.
const MachineBasicBlock * getParent() const
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Register getReg() const
getReg - Returns the register number.
This class provides the reaching def analysis.
void traverse()
Traverse the machine function, mapping definitions.
bool isSafeToMoveForwards(MachineInstr *From, MachineInstr *To) const
Return whether From can be moved forwards to just before To.
bool isSafeToDefRegAt(MachineInstr *MI, MCRegister PhysReg) const
Return whether a MachineInstr could be inserted at MI and safely define the given register without af...
bool getLiveInUses(MachineBasicBlock *MBB, MCRegister PhysReg, InstSet &Uses) const
For the given block, collect the instructions that use the live-in value of the provided register.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
bool isSafeToRemove(MachineInstr *MI, InstSet &ToRemove) const
Return whether removing this instruction will have no effect on the program, returning the redundant ...
MachineInstr * getLocalLiveOutMIDef(MachineBasicBlock *MBB, MCRegister PhysReg) const
Return the local MI that produces the live out value for PhysReg, or nullptr for a non-live out or no...
MachineInstr * getMIOperand(MachineInstr *MI, unsigned Idx) const
If a single MachineInstr creates the reaching definition, for MIs operand at Idx, then return it.
void getReachingLocalUses(MachineInstr *MI, MCRegister PhysReg, InstSet &Uses) const
Provides the uses, in the same block as MI, of register that MI defines.
void reset()
Re-run the analysis.
bool isRegUsedAfter(MachineInstr *MI, MCRegister PhysReg) const
Return whether the given register is used after MI, whether it's a local use or a live out.
bool hasLocalDefBefore(MachineInstr *MI, MCRegister PhysReg) const
Provide whether the register has been defined in the same basic block as, and before,...
void init()
Initialize data structures.
void getLiveOuts(MachineBasicBlock *MBB, MCRegister PhysReg, InstSet &Defs, BlockSet &VisitedBBs) const
Search MBB for a definition of PhysReg and insert it into Defs.
bool hasSameReachingDef(MachineInstr *A, MachineInstr *B, MCRegister PhysReg) const
Return whether A and B use the same def of PhysReg.
void getGlobalUses(MachineInstr *MI, MCRegister PhysReg, InstSet &Uses) const
Collect the users of the value stored in PhysReg, which is defined by MI.
void collectKilledOperands(MachineInstr *MI, InstSet &Dead) const
Assuming MI is dead, recursively search the incoming operands which are killed by MI and collect thos...
bool isRegDefinedAfter(MachineInstr *MI, MCRegister PhysReg) const
Return whether the given register is defined after MI.
int getReachingDef(MachineInstr *MI, MCRegister PhysReg) const
Provides the instruction id of the closest reaching def instruction of PhysReg that reaches MI,...
bool isSafeToMoveBackwards(MachineInstr *From, MachineInstr *To) const
Return whether From can be moved backwards to just after To.
void getGlobalReachingDefs(MachineInstr *MI, MCRegister PhysReg, InstSet &Defs) const
Collect all possible definitions of the value stored in PhysReg, which is used by MI.
MachineInstr * getUniqueReachingMIDef(MachineInstr *MI, MCRegister PhysReg) const
If a single MachineInstr creates the reaching definition, then return it.
bool isReachingDefLiveOut(MachineInstr *MI, MCRegister PhysReg) const
Return whether the reaching def for MI also is live out of its parent block.
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
int getClearance(MachineInstr *MI, MCRegister PhysReg) const
Provides the clearance - the number of instructions since the closest reaching def instuction of Phys...
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
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.
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.
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.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
const_iterator end(StringRef path)
Get end iterator over path.
This is an optimization pass for GlobalISel generic memory operations.
Printable printRegUnit(unsigned Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
auto instructionsWithoutDebug(IterT It, IterT End, bool SkipPseudoOp=true)
Construct a range iterator which begins at It and moves forwards until End is reached,...
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
MachineBasicBlock * MBB
The basic block.
bool IsDone
True if the block that is ready for its final round of processing.
bool PrimaryPass
True if this is the first time we process the basic block.