Correctly modify the CFG in IfConverter, and then remove the
CorrectExtraCFGEdges function.
The latter was a workaround for "Various pieces of code" leaving bogus
extra CFG edges in place. Where by "various" it meant only
IfConverter::MergeBlocks, which failed to clear all of the successors
of dead blocks it emptied out. This wouldn't matter a whole lot,
except that the dead blocks remained listed as predecessors of
still-useful blocks, inhibiting optimizations.
This fix slightly changed two thumb tests, because the correct CFG
successors allowed for the "diamond" if-conversion pattern to be
detected, when it could only use "simple" before.
Additionally, the removal of a now-redundant call to analyzeBranch
(with AllowModify=true) in BranchFolder::OptimizeFunction caused a
later check for an empty block in BranchFolder::OptimizeBlock to
fail. Correct this by moving the call to analyzeBranch in
OptimizeBlock higher.
Differential Revision: https://reviews.llvm.org/D79527
diff --git a/llvm/lib/CodeGen/BranchFolding.cpp b/llvm/lib/CodeGen/BranchFolding.cpp
index 7cf3eab..eb72542 100644
--- a/llvm/lib/CodeGen/BranchFolding.cpp
+++ b/llvm/lib/CodeGen/BranchFolding.cpp
@@ -202,14 +202,7 @@
if (!UpdateLiveIns)
MRI.invalidateLiveness();
- // Fix CFG. The later algorithms expect it to be right.
bool MadeChange = false;
- for (MachineBasicBlock &MBB : MF) {
- MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
- SmallVector<MachineOperand, 4> Cond;
- if (!TII->analyzeBranch(MBB, TBB, FBB, Cond, true))
- MadeChange |= MBB.CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
- }
// Recalculate EH scope membership.
EHScopeMembership = getEHScopeMembership(MF);
@@ -1336,6 +1329,13 @@
SameEHScope = MBBEHScope->second == FallThroughEHScope->second;
}
+ // Analyze the branch in the current block. As a side-effect, this may cause
+ // the block to become empty.
+ MachineBasicBlock *CurTBB = nullptr, *CurFBB = nullptr;
+ SmallVector<MachineOperand, 4> CurCond;
+ bool CurUnAnalyzable =
+ TII->analyzeBranch(*MBB, CurTBB, CurFBB, CurCond, true);
+
// If this block is empty, make everyone use its fall-through, not the block
// explicitly. Landing pads should not do this since the landing-pad table
// points to this block. Blocks with their addresses taken shouldn't be
@@ -1378,10 +1378,6 @@
bool PriorUnAnalyzable =
TII->analyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, true);
if (!PriorUnAnalyzable) {
- // If the CFG for the prior block has extra edges, remove them.
- MadeChange |= PrevBB.CorrectExtraCFGEdges(PriorTBB, PriorFBB,
- !PriorCond.empty());
-
// If the previous branch is conditional and both conditions go to the same
// destination, remove the branch, replacing it with an unconditional one or
// a fall-through.
@@ -1549,15 +1545,7 @@
}
}
- // Analyze the branch in the current block.
- MachineBasicBlock *CurTBB = nullptr, *CurFBB = nullptr;
- SmallVector<MachineOperand, 4> CurCond;
- bool CurUnAnalyzable =
- TII->analyzeBranch(*MBB, CurTBB, CurFBB, CurCond, true);
if (!CurUnAnalyzable) {
- // If the CFG for the prior block has extra edges, remove them.
- MadeChange |= MBB->CorrectExtraCFGEdges(CurTBB, CurFBB, !CurCond.empty());
-
// If this is a two-way branch, and the FBB branches to this block, reverse
// the condition so the single-basic-block loop is faster. Instead of:
// Loop: xxx; jcc Out; jmp Loop
@@ -1634,7 +1622,7 @@
PMBB->ReplaceUsesOfBlockWith(MBB, CurTBB);
// If this change resulted in PMBB ending in a conditional
// branch where both conditions go to the same destination,
- // change this to an unconditional branch (and fix the CFG).
+ // change this to an unconditional branch.
MachineBasicBlock *NewCurTBB = nullptr, *NewCurFBB = nullptr;
SmallVector<MachineOperand, 4> NewCurCond;
bool NewCurUnAnalyzable = TII->analyzeBranch(
@@ -1646,7 +1634,6 @@
TII->insertBranch(*PMBB, NewCurTBB, nullptr, NewCurCond, pdl);
MadeChange = true;
++NumBranchOpts;
- PMBB->CorrectExtraCFGEdges(NewCurTBB, nullptr, false);
}
}
}
diff --git a/llvm/lib/CodeGen/IfConversion.cpp b/llvm/lib/CodeGen/IfConversion.cpp
index c332824..a3cace8 100644
--- a/llvm/lib/CodeGen/IfConversion.cpp
+++ b/llvm/lib/CodeGen/IfConversion.cpp
@@ -2243,10 +2243,10 @@
}
/// Move all instructions from FromBB to the end of ToBB. This will leave
-/// FromBB as an empty block, so remove all of its successor edges except for
-/// the fall-through edge. If AddEdges is true, i.e., when FromBBI's branch is
-/// being moved, add those successor edges to ToBBI and remove the old edge
-/// from ToBBI to FromBBI.
+/// FromBB as an empty block, so remove all of its successor edges and move it
+/// to the end of the function. If AddEdges is true, i.e., when FromBBI's
+/// branch is being moved, add those successor edges to ToBBI and remove the old
+/// edge from ToBBI to FromBBI.
void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) {
MachineBasicBlock &FromMBB = *FromBBI.BB;
assert(!FromMBB.hasAddressTaken() &&
@@ -2286,8 +2286,10 @@
for (MachineBasicBlock *Succ : FromSuccs) {
// Fallthrough edge can't be transferred.
- if (Succ == FallThrough)
+ if (Succ == FallThrough) {
+ FromMBB.removeSuccessor(Succ);
continue;
+ }
auto NewProb = BranchProbability::getZero();
if (AddEdges) {
diff --git a/llvm/lib/CodeGen/MachineBasicBlock.cpp b/llvm/lib/CodeGen/MachineBasicBlock.cpp
index 09e31af..9abd24e 100644
--- a/llvm/lib/CodeGen/MachineBasicBlock.cpp
+++ b/llvm/lib/CodeGen/MachineBasicBlock.cpp
@@ -1261,68 +1261,6 @@
}
}
-/// Various pieces of code can cause excess edges in the CFG to be inserted. If
-/// we have proven that MBB can only branch to DestA and DestB, remove any other
-/// MBB successors from the CFG. DestA and DestB can be null.
-///
-/// Besides DestA and DestB, retain other edges leading to LandingPads
-/// (currently there can be only one; we don't check or require that here).
-/// Note it is possible that DestA and/or DestB are LandingPads.
-bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA,
- MachineBasicBlock *DestB,
- bool IsCond) {
- // The values of DestA and DestB frequently come from a call to the
- // 'TargetInstrInfo::analyzeBranch' method. We take our meaning of the initial
- // values from there.
- //
- // 1. If both DestA and DestB are null, then the block ends with no branches
- // (it falls through to its successor).
- // 2. If DestA is set, DestB is null, and IsCond is false, then the block ends
- // with only an unconditional branch.
- // 3. If DestA is set, DestB is null, and IsCond is true, then the block ends
- // with a conditional branch that falls through to a successor (DestB).
- // 4. If DestA and DestB is set and IsCond is true, then the block ends with a
- // conditional branch followed by an unconditional branch. DestA is the
- // 'true' destination and DestB is the 'false' destination.
-
- bool Changed = false;
-
- MachineBasicBlock *FallThru = getNextNode();
-
- if (!DestA && !DestB) {
- // Block falls through to successor.
- DestA = FallThru;
- DestB = FallThru;
- } else if (DestA && !DestB) {
- if (IsCond)
- // Block ends in conditional jump that falls through to successor.
- DestB = FallThru;
- } else {
- assert(DestA && DestB && IsCond &&
- "CFG in a bad state. Cannot correct CFG edges");
- }
-
- // Remove superfluous edges. I.e., those which aren't destinations of this
- // basic block, duplicate edges, or landing pads.
- SmallPtrSet<const MachineBasicBlock*, 8> SeenMBBs;
- MachineBasicBlock::succ_iterator SI = succ_begin();
- while (SI != succ_end()) {
- const MachineBasicBlock *MBB = *SI;
- if (!SeenMBBs.insert(MBB).second ||
- (MBB != DestA && MBB != DestB && !MBB->isEHPad())) {
- // This is a superfluous edge, remove it.
- SI = removeSuccessor(SI);
- Changed = true;
- } else {
- ++SI;
- }
- }
-
- if (Changed)
- normalizeSuccProbs();
- return Changed;
-}
-
/// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE
/// instructions. Return UnknownLoc if there is none.
DebugLoc