21#define DEBUG_TYPE "reaching-defs-analysis"
32 return MO.isReg() && MO.getReg();
36 return isValidReg(MO) && MO.
isUse();
43 return TRI->regsOverlap(MO.
getReg(), Reg);
47 return isValidReg(MO) && MO.
isDef();
54 return TRI->regsOverlap(MO.
getReg(), Reg);
59 int DefFrameIndex = 0;
60 int SrcFrameIndex = 0;
62 TII->isStackSlotCopy(
MI, DefFrameIndex, SrcFrameIndex))
63 return DefFrameIndex == FrameIndex;
70 "Unexpected basic block number.");
79 LiveRegs.assign(NumRegUnits, ReachingDefDefaultVal);
88 if (LiveRegs[Unit] != -1) {
90 MBBReachingDefs.
append(MBBNumber, Unit, -1);
100 assert(
unsigned(pred->getNumber()) < MBBOutRegsInfos.
size() &&
101 "Should have pre-allocated MBBInfos for all MBBs");
102 const LiveRegsDefInfo &
Incoming = MBBOutRegsInfos[pred->getNumber()];
109 for (
unsigned Unit = 0; Unit != NumRegUnits; ++Unit)
110 LiveRegs[Unit] = std::max(LiveRegs[Unit],
Incoming[Unit]);
114 for (
unsigned Unit = 0; Unit != NumRegUnits; ++Unit)
115 if (LiveRegs[Unit] != ReachingDefDefaultVal)
116 MBBReachingDefs.
append(MBBNumber, Unit, LiveRegs[Unit]);
120 assert(!LiveRegs.empty() &&
"Must enter basic block first.");
123 "Unexpected basic block number.");
125 MBBOutRegsInfos[MBBNumber] = LiveRegs;
131 for (
int &OutLiveReg : MBBOutRegsInfos[MBBNumber])
132 if (OutLiveReg != ReachingDefDefaultVal)
133 OutLiveReg -= CurInstr;
138 assert(!
MI->isDebugInstr() &&
"Won't process debug instructions");
140 unsigned MBBNumber =
MI->getParent()->getNumber();
142 "Unexpected basic block number.");
144 for (
auto &MO :
MI->operands()) {
147 assert(FrameIndex >= 0 &&
"Can't handle negative frame indicies yet!");
150 MBBFrameObjsReachingDefs[{MBBNumber,
FrameIndex}].push_back(CurInstr);
160 if (LiveRegs[Unit] != CurInstr) {
161 LiveRegs[Unit] = CurInstr;
162 MBBReachingDefs.
append(MBBNumber, Unit, CurInstr);
166 InstIds[
MI] = CurInstr;
173 "Unexpected basic block number.");
178 int NumInsts = std::distance(NonDbgInsts.begin(), NonDbgInsts.end());
183 assert(
unsigned(pred->getNumber()) < MBBOutRegsInfos.
size() &&
184 "Should have pre-allocated MBBInfos for all MBBs");
185 const LiveRegsDefInfo &
Incoming = MBBOutRegsInfos[pred->getNumber()];
190 for (
unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
192 if (Def == ReachingDefDefaultVal)
195 auto Defs = MBBReachingDefs.
defs(MBBNumber, Unit);
196 if (!Defs.empty() && Defs.front() < 0) {
197 if (Defs.front() >= Def)
204 MBBReachingDefs.
prepend(MBBNumber, Unit, Def);
209 if (MBBOutRegsInfos[MBBNumber][Unit] < Def - NumInsts)
210 MBBOutRegsInfos[MBBNumber][Unit] =
Def - NumInsts;
215void ReachingDefAnalysis::processBasicBlock(
219 << (!TraversedMBB.
IsDone ?
": incomplete\n"
220 :
": all preds known\n"));
224 reprocessBasicBlock(
MBB);
228 enterBasicBlock(
MBB);
232 leaveBasicBlock(
MBB);
236 dbgs() <<
"RDA results for " << MF.
getName() <<
"\n";
245 int FrameIndex = MO.getIndex();
247 "Can't handle negative frame indicies yet!");
249 }
else if (MO.isReg()) {
259 MO.print(
dbgs(), TRI);
266 dbgs() << Num <<
" ";
269 dbgs() << Num <<
": " <<
MI <<
"\n";
270 InstToNumMap[&
MI] = Num;
281 LLVM_DEBUG(
dbgs() <<
"********** REACHING DEFINITION ANALYSIS **********\n");
291 MBBOutRegsInfos.
clear();
292 MBBReachingDefs.
clear();
293 MBBFrameObjsReachingDefs.
clear();
312 TraversedMBBOrder = Traversal.
traverse(*MF);
318 processBasicBlock(TraversedMBB);
322 MBBNumber != NumBlockIDs; ++MBBNumber) {
323 for (
unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
324 int LastDef = ReachingDefDefaultVal;
325 for (
int Def : MBBReachingDefs.
defs(MBBNumber, Unit)) {
326 assert(Def > LastDef &&
"Defs must be sorted and unique");
335 assert(InstIds.count(
MI) &&
"Unexpected machine instuction.");
336 int InstId = InstIds.lookup(
MI);
337 int DefRes = ReachingDefDefaultVal;
338 unsigned MBBNumber =
MI->getParent()->getNumber();
340 "Unexpected basic block number.");
341 int LatestDef = ReachingDefDefaultVal;
345 int FrameIndex = Reg.stackSlotIndex();
346 auto Lookup = MBBFrameObjsReachingDefs.
find({MBBNumber, FrameIndex});
347 if (
Lookup == MBBFrameObjsReachingDefs.
end())
349 auto &Defs =
Lookup->second;
350 for (
int Def : Defs) {
355 LatestDef = std::max(LatestDef, DefRes);
360 for (
int Def : MBBReachingDefs.
defs(MBBNumber, Unit)) {
365 LatestDef = std::max(LatestDef, DefRes);
381 if (ParentA != ParentB)
391 "Unexpected basic block number.");
393 "Unexpected instruction id.");
398 for (
auto &
MI : *
MBB) {
399 auto F = InstIds.find(&
MI);
400 if (
F != InstIds.end() &&
F->second == InstId)
408 assert(InstIds.count(
MI) &&
"Unexpected machine instuction.");
422 if (
MI->isDebugInstr())
427 if (getReachingLocalMIDef(&*
MI, Reg) != Def)
430 for (
auto &MO :
MI->operands()) {
445 for (
auto &MO :
MI.operands()) {
473 while (!ToVisit.
empty()) {
491 for (
auto *
MBB :
MI->getParent()->predecessors())
509 LiveRegs.addLiveOuts(*
MBB);
510 if (Reg.isPhysical() && LiveRegs.available(Reg))
524 if (LocalDef && InstIds.lookup(LocalDef) < InstIds.lookup(
MI))
541 unsigned Idx)
const {
542 assert(
MI->getOperand(
Idx).isReg() &&
"Expected register operand");
555 LiveRegs.addLiveOuts(*
MBB);
558 if (!LiveRegs.available(Reg))
565 LiveRegs.stepBackward(
Last);
566 if (!LiveRegs.available(Reg))
567 return InstIds.lookup(&
Last) > InstIds.lookup(
MI);
581 return Def == getReachingLocalMIDef(
MI, Reg);
590 LiveRegs.addLiveOuts(*
MBB);
591 if (Reg.isPhysical() && LiveRegs.available(Reg))
600 for (
auto &MO :
Last->operands())
610 LiveRegs.addLiveOuts(*
MBB);
611 if (Reg.isPhysical() && LiveRegs.available(Reg))
619 int FrameIndex = Reg.stackSlotIndex();
626 for (
auto &MO :
Last->operands())
630 return Def < 0 ? nullptr : getInstFromId(
MBB, Def);
634 return MI.mayLoadOrStore() ||
MI.mayRaiseFPException() ||
635 MI.hasUnmodeledSideEffects() ||
MI.isTerminator() ||
636 MI.isCall() ||
MI.isBarrier() ||
MI.isBranch() ||
MI.isReturn();
642template<
typename Iterator>
650 for (
auto &MO :
From->operands()) {
662 for (
auto I = ++Iterator(
From), E = Iterator(To);
I != E; ++
I) {
665 for (
auto &MO :
I->operands())
666 if (MO.isReg() && MO.getReg() && Defs.
count(MO.getReg()))
676 for (
auto I = Iterator(
From), E =
From->getParent()->end();
I != E; ++
I)
678 return isSafeToMove<Iterator>(
From, To);
686 for (
auto I = Iterator(
From), E =
From->getParent()->rend();
I != E; ++
I)
688 return isSafeToMove<Iterator>(
From, To);
718 for (
auto &MO :
MI->operands()) {
725 for (
auto *
I :
Uses) {
743 unsigned LiveDefs = 0;
744 for (
auto &MO : Def->operands()) {
759 for (
auto &MO :
MI->operands()) {
763 if (
IsDead(Def, MO.getReg()))
778 if (
auto *Def = getReachingLocalMIDef(
MI, Reg)) {
791 for (
auto E =
MBB->
end();
I != E; ++
I) {
794 for (
auto &MO :
I->operands())
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
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")
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
const HexagonInstrInfo * TII
Register const TargetRegisterInfo * TRI
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
static bool isValidRegUseOf(const MachineOperand &MO, Register Reg, const TargetRegisterInfo *TRI)
static bool mayHaveSideEffects(MachineInstr &MI)
static bool isFIDef(const MachineInstr &MI, int FrameIndex, const TargetInstrInfo *TII)
static bool isValidRegDef(const MachineOperand &MO)
static cl::opt< bool > PrintAllReachingDefs("print-all-reaching-defs", cl::Hidden, cl::desc("Used for test purpuses"), cl::Hidden)
static bool isValidRegDefOf(const MachineOperand &MO, Register Reg, const TargetRegisterInfo *TRI)
static bool isValidRegUse(const MachineOperand &MO)
Remove Loads Into Fake Uses
This file defines generic set operations that may be used on set's of different types,...
This file defines the SmallSet class.
static int Lookup(ArrayRef< TableEntry > Table, unsigned Opcode)
iterator find(const_arg_type_t< KeyT > Val)
Register isStoreToStackSlot(const MachineInstr &MI, int &FrameIndex) const override
If the specified machine instruction is a direct store to a stack slot, return the virtual or physica...
A set of register units used to track register liveness.
This class provides the basic blocks traversal order used by passes like ReachingDefAnalysis and Exec...
TraversalOrder traverse(MachineFunction &MF)
void append(unsigned MBBNumber, unsigned Unit, int Def)
ArrayRef< ReachingDef > defs(unsigned MBBNumber, unsigned Unit) const
void replaceFront(unsigned MBBNumber, unsigned Unit, int Def)
void init(unsigned NumBlockIDs)
void prepend(unsigned MBBNumber, unsigned Unit, int Def)
void startBasicBlock(unsigned MBBNumber, unsigned NumRegUnits)
unsigned numBlockIDs() const
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
iterator_range< MCRegUnitIterator > regunits(MCRegister Reg) const
Returns an iterator range over all regunits for Reg.
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...
reverse_instr_iterator instr_rend()
LLVM_ABI 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()
iterator_range< succ_iterator > successors()
iterator_range< pred_iterator > predecessors()
MachineInstrBundleIterator< MachineInstr > iterator
LLVM_ABI bool isLiveIn(MCRegister Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
unsigned getNumObjects() const
Return the number of objects.
int getObjectIndexBegin() const
Return the minimum frame object index.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
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.
MachineInstr * getLocalLiveOutMIDef(MachineBasicBlock *MBB, Register Reg) const
Return the local MI that produces the live out value for Reg, or nullptr for a non-live out or non-lo...
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 isRegUsedAfter(MachineInstr *MI, Register Reg) const
Return whether the given register is used after MI, whether it's a local use or a live out.
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 * getMIOperand(MachineInstr *MI, unsigned Idx) const
If a single MachineInstr creates the reaching definition, for MIs operand at Idx, then return it.
void printAllReachingDefs(MachineFunction &MF)
void reset()
Re-run the analysis.
int getReachingDef(MachineInstr *MI, Register Reg) const
Provides the instruction id of the closest reaching def instruction of Reg that reaches MI,...
void init()
Initialize data structures.
void getGlobalUses(MachineInstr *MI, Register Reg, InstSet &Uses) const
Collect the users of the value stored in Reg, 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 isSafeToMoveBackwards(MachineInstr *From, MachineInstr *To) const
Return whether From can be moved backwards to just after To.
void getLiveOuts(MachineBasicBlock *MBB, Register Reg, InstSet &Defs, BlockSet &VisitedBBs) const
Search MBB for a definition of Reg and insert it into Defs.
int getClearance(MachineInstr *MI, Register Reg) const
Provides the clearance - the number of instructions since the closest reaching def instuction of Reg ...
bool hasLocalDefBefore(MachineInstr *MI, Register Reg) const
Provide whether the register has been defined in the same basic block as, and before,...
bool isReachingDefLiveOut(MachineInstr *MI, Register Reg) const
Return whether the reaching def for MI also is live out of its parent block.
bool getLiveInUses(MachineBasicBlock *MBB, Register Reg, InstSet &Uses) const
For the given block, collect the instructions that use the live-in value of the provided register.
bool isSafeToDefRegAt(MachineInstr *MI, Register Reg) const
Return whether a MachineInstr could be inserted at MI and safely define the given register without af...
bool hasSameReachingDef(MachineInstr *A, MachineInstr *B, Register Reg) const
Return whether A and B use the same def of Reg.
void getReachingLocalUses(MachineInstr *MI, Register Reg, InstSet &Uses) const
Provides the uses, in the same block as MI, of register that MI defines.
bool isRegDefinedAfter(MachineInstr *MI, Register Reg) const
Return whether the given register is defined after MI.
MachineInstr * getUniqueReachingMIDef(MachineInstr *MI, Register Reg) const
If a single MachineInstr creates the reaching definition, then return it.
void getGlobalReachingDefs(MachineInstr *MI, Register Reg, InstSet &Defs) const
Collect all possible definitions of the value stored in Reg, which is used by MI.
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Wrapper class representing virtual and physical registers.
static Register index2StackSlot(int FI)
Convert a non-negative frame index to a stack slot register value.
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.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
TargetInstrInfo - Interface to description of machine instruction set.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetInstrInfo * getInstrInfo() const
virtual const TargetRegisterInfo * getRegisterInfo() const =0
Return the target's register information.
NodeAddr< DefNode * > Def
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ABI 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 range R to container C.
void sort(IteratorTy Start, IteratorTy End)
LLVM_ABI 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,...
LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...
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.