aboutsummaryrefslogtreecommitdiff
path: root/contrib/llvm-project/llvm/lib/CodeGen/ReachingDefAnalysis.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/llvm-project/llvm/lib/CodeGen/ReachingDefAnalysis.cpp')
-rw-r--r--contrib/llvm-project/llvm/lib/CodeGen/ReachingDefAnalysis.cpp186
1 files changed, 110 insertions, 76 deletions
diff --git a/contrib/llvm-project/llvm/lib/CodeGen/ReachingDefAnalysis.cpp b/contrib/llvm-project/llvm/lib/CodeGen/ReachingDefAnalysis.cpp
index 5bd8b4b8e27f..d16e90a7e0b4 100644
--- a/contrib/llvm-project/llvm/lib/CodeGen/ReachingDefAnalysis.cpp
+++ b/contrib/llvm-project/llvm/lib/CodeGen/ReachingDefAnalysis.cpp
@@ -29,7 +29,7 @@ static bool isValidRegUse(const MachineOperand &MO) {
return isValidReg(MO) && MO.isUse();
}
-static bool isValidRegUseOf(const MachineOperand &MO, int PhysReg) {
+static bool isValidRegUseOf(const MachineOperand &MO, MCRegister PhysReg) {
return isValidRegUse(MO) && MO.getReg() == PhysReg;
}
@@ -37,7 +37,7 @@ static bool isValidRegDef(const MachineOperand &MO) {
return isValidReg(MO) && MO.isDef();
}
-static bool isValidRegDefOf(const MachineOperand &MO, int PhysReg) {
+static bool isValidRegDefOf(const MachineOperand &MO, MCRegister PhysReg) {
return isValidRegDef(MO) && MO.getReg() == PhysReg;
}
@@ -121,7 +121,8 @@ void ReachingDefAnalysis::processDefs(MachineInstr *MI) {
for (auto &MO : MI->operands()) {
if (!isValidRegDef(MO))
continue;
- for (MCRegUnitIterator Unit(MO.getReg(), TRI); Unit.isValid(); ++Unit) {
+ for (MCRegUnitIterator Unit(MO.getReg().asMCReg(), TRI); Unit.isValid();
+ ++Unit) {
// This instruction explicitly defines the current reg unit.
LLVM_DEBUG(dbgs() << printReg(*Unit, TRI) << ":\t" << CurInstr
<< '\t' << *MI);
@@ -143,10 +144,9 @@ void ReachingDefAnalysis::reprocessBasicBlock(MachineBasicBlock *MBB) {
"Unexpected basic block number.");
// Count number of non-debug instructions for end of block adjustment.
- int NumInsts = 0;
- for (const MachineInstr &MI : *MBB)
- if (!MI.isDebugInstr())
- NumInsts++;
+ auto NonDbgInsts =
+ instructionsWithoutDebug(MBB->instr_begin(), MBB->instr_end());
+ int NumInsts = std::distance(NonDbgInsts.begin(), NonDbgInsts.end());
// When reprocessing a block, the only thing we need to do is check whether
// there is now a more recent incoming reaching definition from a predecessor.
@@ -197,10 +197,9 @@ void ReachingDefAnalysis::processBasicBlock(
}
enterBasicBlock(MBB);
- for (MachineInstr &MI : *MBB) {
- if (!MI.isDebugInstr())
- processDefs(&MI);
- }
+ for (MachineInstr &MI :
+ instructionsWithoutDebug(MBB->instr_begin(), MBB->instr_end()))
+ processDefs(&MI);
leaveBasicBlock(MBB);
}
@@ -254,7 +253,8 @@ void ReachingDefAnalysis::traverse() {
#endif
}
-int ReachingDefAnalysis::getReachingDef(MachineInstr *MI, int PhysReg) const {
+int ReachingDefAnalysis::getReachingDef(MachineInstr *MI,
+ MCRegister PhysReg) const {
assert(InstIds.count(MI) && "Unexpected machine instuction.");
int InstId = InstIds.lookup(MI);
int DefRes = ReachingDefDefaultVal;
@@ -273,13 +273,16 @@ int ReachingDefAnalysis::getReachingDef(MachineInstr *MI, int PhysReg) const {
return LatestDef;
}
-MachineInstr* ReachingDefAnalysis::getReachingLocalMIDef(MachineInstr *MI,
- int PhysReg) const {
- return getInstFromId(MI->getParent(), getReachingDef(MI, PhysReg));
+MachineInstr *
+ReachingDefAnalysis::getReachingLocalMIDef(MachineInstr *MI,
+ MCRegister PhysReg) const {
+ return hasLocalDefBefore(MI, PhysReg)
+ ? getInstFromId(MI->getParent(), getReachingDef(MI, PhysReg))
+ : nullptr;
}
bool ReachingDefAnalysis::hasSameReachingDef(MachineInstr *A, MachineInstr *B,
- int PhysReg) const {
+ MCRegister PhysReg) const {
MachineBasicBlock *ParentA = A->getParent();
MachineBasicBlock *ParentB = B->getParent();
if (ParentA != ParentB)
@@ -307,18 +310,19 @@ MachineInstr *ReachingDefAnalysis::getInstFromId(MachineBasicBlock *MBB,
return nullptr;
}
-int
-ReachingDefAnalysis::getClearance(MachineInstr *MI, MCPhysReg PhysReg) const {
+int ReachingDefAnalysis::getClearance(MachineInstr *MI,
+ MCRegister PhysReg) const {
assert(InstIds.count(MI) && "Unexpected machine instuction.");
return InstIds.lookup(MI) - getReachingDef(MI, PhysReg);
}
-bool
-ReachingDefAnalysis::hasLocalDefBefore(MachineInstr *MI, int PhysReg) const {
+bool ReachingDefAnalysis::hasLocalDefBefore(MachineInstr *MI,
+ MCRegister PhysReg) const {
return getReachingDef(MI, PhysReg) >= 0;
}
-void ReachingDefAnalysis::getReachingLocalUses(MachineInstr *Def, int PhysReg,
+void ReachingDefAnalysis::getReachingLocalUses(MachineInstr *Def,
+ MCRegister PhysReg,
InstSet &Uses) const {
MachineBasicBlock *MBB = Def->getParent();
MachineBasicBlock::iterator MI = MachineBasicBlock::iterator(Def);
@@ -342,12 +346,11 @@ void ReachingDefAnalysis::getReachingLocalUses(MachineInstr *Def, int PhysReg,
}
}
-bool
-ReachingDefAnalysis::getLiveInUses(MachineBasicBlock *MBB, int PhysReg,
- InstSet &Uses) const {
- for (auto &MI : *MBB) {
- if (MI.isDebugInstr())
- continue;
+bool ReachingDefAnalysis::getLiveInUses(MachineBasicBlock *MBB,
+ MCRegister PhysReg,
+ InstSet &Uses) const {
+ for (MachineInstr &MI :
+ instructionsWithoutDebug(MBB->instr_begin(), MBB->instr_end())) {
for (auto &MO : MI.operands()) {
if (!isValidRegUseOf(MO, PhysReg))
continue;
@@ -356,12 +359,14 @@ ReachingDefAnalysis::getLiveInUses(MachineBasicBlock *MBB, int PhysReg,
Uses.insert(&MI);
}
}
- return isReachingDefLiveOut(&MBB->back(), PhysReg);
+ auto Last = MBB->getLastNonDebugInstr();
+ if (Last == MBB->end())
+ return true;
+ return isReachingDefLiveOut(&*Last, PhysReg);
}
-void
-ReachingDefAnalysis::getGlobalUses(MachineInstr *MI, int PhysReg,
- InstSet &Uses) const {
+void ReachingDefAnalysis::getGlobalUses(MachineInstr *MI, MCRegister PhysReg,
+ InstSet &Uses) const {
MachineBasicBlock *MBB = MI->getParent();
// Collect the uses that each def touches within the block.
@@ -372,9 +377,7 @@ ReachingDefAnalysis::getGlobalUses(MachineInstr *MI, int PhysReg,
if (LiveOut != MI)
return;
- SmallVector<MachineBasicBlock*, 4> ToVisit;
- ToVisit.insert(ToVisit.begin(), MBB->successors().begin(),
- MBB->successors().end());
+ SmallVector<MachineBasicBlock *, 4> ToVisit(MBB->successors());
SmallPtrSet<MachineBasicBlock*, 4>Visited;
while (!ToVisit.empty()) {
MachineBasicBlock *MBB = ToVisit.back();
@@ -382,22 +385,33 @@ ReachingDefAnalysis::getGlobalUses(MachineInstr *MI, int PhysReg,
if (Visited.count(MBB) || !MBB->isLiveIn(PhysReg))
continue;
if (getLiveInUses(MBB, PhysReg, Uses))
- ToVisit.insert(ToVisit.end(), MBB->successors().begin(),
- MBB->successors().end());
+ llvm::append_range(ToVisit, MBB->successors());
Visited.insert(MBB);
}
}
}
-void ReachingDefAnalysis::getLiveOuts(MachineBasicBlock *MBB, int PhysReg,
- InstSet &Defs) const {
+void ReachingDefAnalysis::getGlobalReachingDefs(MachineInstr *MI,
+ MCRegister PhysReg,
+ InstSet &Defs) const {
+ if (auto *Def = getUniqueReachingMIDef(MI, PhysReg)) {
+ Defs.insert(Def);
+ return;
+ }
+
+ for (auto *MBB : MI->getParent()->predecessors())
+ getLiveOuts(MBB, PhysReg, Defs);
+}
+
+void ReachingDefAnalysis::getLiveOuts(MachineBasicBlock *MBB,
+ MCRegister PhysReg, InstSet &Defs) const {
SmallPtrSet<MachineBasicBlock*, 2> VisitedBBs;
getLiveOuts(MBB, PhysReg, Defs, VisitedBBs);
}
-void
-ReachingDefAnalysis::getLiveOuts(MachineBasicBlock *MBB, int PhysReg,
- InstSet &Defs, BlockSet &VisitedBBs) const {
+void ReachingDefAnalysis::getLiveOuts(MachineBasicBlock *MBB,
+ MCRegister PhysReg, InstSet &Defs,
+ BlockSet &VisitedBBs) const {
if (VisitedBBs.count(MBB))
return;
@@ -414,26 +428,25 @@ ReachingDefAnalysis::getLiveOuts(MachineBasicBlock *MBB, int PhysReg,
getLiveOuts(Pred, PhysReg, Defs, VisitedBBs);
}
-MachineInstr *ReachingDefAnalysis::getUniqueReachingMIDef(MachineInstr *MI,
- int PhysReg) const {
+MachineInstr *
+ReachingDefAnalysis::getUniqueReachingMIDef(MachineInstr *MI,
+ MCRegister PhysReg) const {
// If there's a local def before MI, return it.
MachineInstr *LocalDef = getReachingLocalMIDef(MI, PhysReg);
if (LocalDef && InstIds.lookup(LocalDef) < InstIds.lookup(MI))
return LocalDef;
- SmallPtrSet<MachineBasicBlock*, 4> VisitedBBs;
SmallPtrSet<MachineInstr*, 2> Incoming;
- for (auto *Pred : MI->getParent()->predecessors())
- getLiveOuts(Pred, PhysReg, Incoming, VisitedBBs);
-
- // If we have a local def and an incoming instruction, then there's not a
- // unique instruction def.
- if (!Incoming.empty() && LocalDef)
- return nullptr;
- else if (Incoming.size() == 1)
+ MachineBasicBlock *Parent = MI->getParent();
+ for (auto *Pred : Parent->predecessors())
+ getLiveOuts(Pred, PhysReg, Incoming);
+
+ // Check that we have a single incoming value and that it does not
+ // come from the same block as MI - since it would mean that the def
+ // is executed after MI.
+ if (Incoming.size() == 1 && (*Incoming.begin())->getParent() != Parent)
return *Incoming.begin();
- else
- return LocalDef;
+ return nullptr;
}
MachineInstr *ReachingDefAnalysis::getMIOperand(MachineInstr *MI,
@@ -448,7 +461,8 @@ MachineInstr *ReachingDefAnalysis::getMIOperand(MachineInstr *MI,
return getUniqueReachingMIDef(MI, MO.getReg());
}
-bool ReachingDefAnalysis::isRegUsedAfter(MachineInstr *MI, int PhysReg) const {
+bool ReachingDefAnalysis::isRegUsedAfter(MachineInstr *MI,
+ MCRegister PhysReg) const {
MachineBasicBlock *MBB = MI->getParent();
LivePhysRegs LiveRegs(*TRI);
LiveRegs.addLiveOuts(*MBB);
@@ -459,18 +473,21 @@ bool ReachingDefAnalysis::isRegUsedAfter(MachineInstr *MI, int PhysReg) const {
// Walk backwards through the block to see if the register is live at some
// point.
- for (auto Last = MBB->rbegin(), End = MBB->rend(); Last != End; ++Last) {
- LiveRegs.stepBackward(*Last);
+ for (MachineInstr &Last :
+ instructionsWithoutDebug(MBB->instr_rbegin(), MBB->instr_rend())) {
+ LiveRegs.stepBackward(Last);
if (LiveRegs.contains(PhysReg))
- return InstIds.lookup(&*Last) > InstIds.lookup(MI);
+ return InstIds.lookup(&Last) > InstIds.lookup(MI);
}
return false;
}
bool ReachingDefAnalysis::isRegDefinedAfter(MachineInstr *MI,
- int PhysReg) const {
+ MCRegister PhysReg) const {
MachineBasicBlock *MBB = MI->getParent();
- if (getReachingDef(MI, PhysReg) != getReachingDef(&MBB->back(), PhysReg))
+ auto Last = MBB->getLastNonDebugInstr();
+ if (Last != MBB->end() &&
+ getReachingDef(MI, PhysReg) != getReachingDef(&*Last, PhysReg))
return true;
if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg))
@@ -479,17 +496,17 @@ bool ReachingDefAnalysis::isRegDefinedAfter(MachineInstr *MI,
return false;
}
-bool
-ReachingDefAnalysis::isReachingDefLiveOut(MachineInstr *MI, int PhysReg) const {
+bool ReachingDefAnalysis::isReachingDefLiveOut(MachineInstr *MI,
+ MCRegister PhysReg) const {
MachineBasicBlock *MBB = MI->getParent();
LivePhysRegs LiveRegs(*TRI);
LiveRegs.addLiveOuts(*MBB);
if (!LiveRegs.contains(PhysReg))
return false;
- MachineInstr *Last = &MBB->back();
+ auto Last = MBB->getLastNonDebugInstr();
int Def = getReachingDef(MI, PhysReg);
- if (getReachingDef(Last, PhysReg) != Def)
+ if (Last != MBB->end() && getReachingDef(&*Last, PhysReg) != Def)
return false;
// Finally check that the last instruction doesn't redefine the register.
@@ -500,18 +517,22 @@ ReachingDefAnalysis::isReachingDefLiveOut(MachineInstr *MI, int PhysReg) const {
return true;
}
-MachineInstr* ReachingDefAnalysis::getLocalLiveOutMIDef(MachineBasicBlock *MBB,
- int PhysReg) const {
+MachineInstr *
+ReachingDefAnalysis::getLocalLiveOutMIDef(MachineBasicBlock *MBB,
+ MCRegister PhysReg) const {
LivePhysRegs LiveRegs(*TRI);
LiveRegs.addLiveOuts(*MBB);
if (!LiveRegs.contains(PhysReg))
return nullptr;
- MachineInstr *Last = &MBB->back();
- int Def = getReachingDef(Last, PhysReg);
+ auto Last = MBB->getLastNonDebugInstr();
+ if (Last == MBB->end())
+ return nullptr;
+
+ int Def = getReachingDef(&*Last, PhysReg);
for (auto &MO : Last->operands())
if (isValidRegDefOf(MO, PhysReg))
- return Last;
+ return &*Last;
return Def < 0 ? nullptr : getInstFromId(MBB, Def);
}
@@ -528,7 +549,7 @@ static bool mayHaveSideEffects(MachineInstr &MI) {
template<typename Iterator>
bool ReachingDefAnalysis::isSafeToMove(MachineInstr *From,
MachineInstr *To) const {
- if (From->getParent() != To->getParent())
+ if (From->getParent() != To->getParent() || From == To)
return false;
SmallSet<int, 2> Defs;
@@ -557,12 +578,22 @@ bool ReachingDefAnalysis::isSafeToMove(MachineInstr *From,
bool ReachingDefAnalysis::isSafeToMoveForwards(MachineInstr *From,
MachineInstr *To) const {
- return isSafeToMove<MachineBasicBlock::reverse_iterator>(From, To);
+ using Iterator = MachineBasicBlock::iterator;
+ // Walk forwards until we find the instruction.
+ for (auto I = Iterator(From), E = From->getParent()->end(); I != E; ++I)
+ if (&*I == To)
+ return isSafeToMove<Iterator>(From, To);
+ return false;
}
bool ReachingDefAnalysis::isSafeToMoveBackwards(MachineInstr *From,
MachineInstr *To) const {
- return isSafeToMove<MachineBasicBlock::iterator>(From, To);
+ using Iterator = MachineBasicBlock::reverse_iterator;
+ // Walk backwards until we find the instruction.
+ for (auto I = Iterator(From), E = From->getParent()->rend(); I != E; ++I)
+ if (&*I == To)
+ return isSafeToMove<Iterator>(From, To);
+ return false;
}
bool ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI,
@@ -612,7 +643,10 @@ ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI, InstSet &Visited,
void ReachingDefAnalysis::collectKilledOperands(MachineInstr *MI,
InstSet &Dead) const {
Dead.insert(MI);
- auto IsDead = [this, &Dead](MachineInstr *Def, int PhysReg) {
+ auto IsDead = [this, &Dead](MachineInstr *Def, MCRegister PhysReg) {
+ if (mayHaveSideEffects(*Def))
+ return false;
+
unsigned LiveDefs = 0;
for (auto &MO : Def->operands()) {
if (!isValidRegDef(MO))
@@ -642,18 +676,18 @@ void ReachingDefAnalysis::collectKilledOperands(MachineInstr *MI,
}
bool ReachingDefAnalysis::isSafeToDefRegAt(MachineInstr *MI,
- int PhysReg) const {
+ MCRegister PhysReg) const {
SmallPtrSet<MachineInstr*, 1> Ignore;
return isSafeToDefRegAt(MI, PhysReg, Ignore);
}
-bool ReachingDefAnalysis::isSafeToDefRegAt(MachineInstr *MI, int PhysReg,
+bool ReachingDefAnalysis::isSafeToDefRegAt(MachineInstr *MI, MCRegister PhysReg,
InstSet &Ignore) const {
// Check for any uses of the register after MI.
if (isRegUsedAfter(MI, PhysReg)) {
if (auto *Def = getReachingLocalMIDef(MI, PhysReg)) {
SmallPtrSet<MachineInstr*, 2> Uses;
- getReachingLocalUses(Def, PhysReg, Uses);
+ getGlobalUses(Def, PhysReg, Uses);
for (auto *Use : Uses)
if (!Ignore.count(Use))
return false;
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-19 23:32:15 +0000