[DTU] Refine the interface and logic of applyUpdates
Summary:
This patch separates two semantics of `applyUpdates`:
1. User provides an accurate CFG diff and the dominator tree is updated according to the difference of `the number of edge insertions` and `the number of edge deletions` to infer the status of an edge before and after the update.
2. User provides a sequence of hints. Updates mentioned in this sequence might never happened and even duplicated.
Logic changes:
Previously, removing invalid updates is considered a side-effect of deduplication and is not guaranteed to be reliable. To handle the second semantic, `applyUpdates` does validity checking before deduplication, which can cause updates that have already been applied to be submitted again. Then, different calls to `applyUpdates` might cause unintended consequences, for example,
```
DTU(Lazy) and Edge A->B exists.
1. DTU.applyUpdates({{Delete, A, B}, {Insert, A, B}}) // User expects these 2 updates result in a no-op, but {Insert, A, B} is queued
2. Remove A->B
3. DTU.applyUpdates({{Delete, A, B}}) // DTU cancels this update with {Insert, A, B} mentioned above together (Unintended)
```
But by restricting the precondition that updates of an edge need to be strictly ordered as how CFG changes were made, we can infer the initial status of this edge to resolve this issue.
Interface changes:
The second semantic of `applyUpdates` is separated to `applyUpdatesPermissive`.
These changes enable DTU(Lazy) to use the first semantic if needed, which is quite useful in `transforms/utils`.
Reviewers: kuhar, brzycki, dmgreen, grosser
Reviewed By: brzycki
Subscribers: hiraditya, llvm-commits
Tags: #llvm
Differential Revision: https://reviews.llvm.org/D58170
llvm-svn: 354669
diff --git a/llvm/lib/Transforms/Scalar/CallSiteSplitting.cpp b/llvm/lib/Transforms/Scalar/CallSiteSplitting.cpp
index 8463ceb..6b74923 100644
--- a/llvm/lib/Transforms/Scalar/CallSiteSplitting.cpp
+++ b/llvm/lib/Transforms/Scalar/CallSiteSplitting.cpp
@@ -366,7 +366,7 @@
assert(Splits.size() == 2 && "Expected exactly 2 splits!");
for (unsigned i = 0; i < Splits.size(); i++) {
Splits[i]->getTerminator()->eraseFromParent();
- DTU.applyUpdates({{DominatorTree::Delete, Splits[i], TailBB}});
+ DTU.applyUpdatesPermissive({{DominatorTree::Delete, Splits[i], TailBB}});
}
// Erase the tail block once done with musttail patching
diff --git a/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp b/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
index 755bf34..e6dd42d 100644
--- a/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
+++ b/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
@@ -373,7 +373,7 @@
++NumDeadCases;
Changed = true;
if (--SuccessorsCount[Succ] == 0)
- DTU.applyUpdates({{DominatorTree::Delete, BB, Succ}});
+ DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB, Succ}});
continue;
}
if (State == LazyValueInfo::True) {
diff --git a/llvm/lib/Transforms/Scalar/JumpThreading.cpp b/llvm/lib/Transforms/Scalar/JumpThreading.cpp
index 80b3cd7..7d6ffa0 100644
--- a/llvm/lib/Transforms/Scalar/JumpThreading.cpp
+++ b/llvm/lib/Transforms/Scalar/JumpThreading.cpp
@@ -1091,7 +1091,7 @@
<< "' folding undef terminator: " << *BBTerm << '\n');
BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm);
BBTerm->eraseFromParent();
- DTU->applyUpdates(Updates);
+ DTU->applyUpdatesPermissive(Updates);
return true;
}
@@ -1159,7 +1159,8 @@
ConstantInt::getFalse(CondCmp->getType());
ReplaceFoldableUses(CondCmp, CI);
}
- DTU->applyUpdates({{DominatorTree::Delete, BB, ToRemoveSucc}});
+ DTU->applyUpdatesPermissive(
+ {{DominatorTree::Delete, BB, ToRemoveSucc}});
return true;
}
@@ -1246,7 +1247,7 @@
RemoveSucc->removePredecessor(BB);
BranchInst::Create(KeepSucc, BI);
BI->eraseFromParent();
- DTU->applyUpdates({{DominatorTree::Delete, BB, RemoveSucc}});
+ DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, RemoveSucc}});
return true;
}
CurrentBB = CurrentPred;
@@ -1676,7 +1677,7 @@
Instruction *Term = BB->getTerminator();
BranchInst::Create(OnlyDest, Term);
Term->eraseFromParent();
- DTU->applyUpdates(Updates);
+ DTU->applyUpdatesPermissive(Updates);
// If the condition is now dead due to the removal of the old terminator,
// erase it.
@@ -2018,9 +2019,9 @@
}
// Enqueue required DT updates.
- DTU->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB},
- {DominatorTree::Insert, PredBB, NewBB},
- {DominatorTree::Delete, PredBB, BB}});
+ DTU->applyUpdatesPermissive({{DominatorTree::Insert, NewBB, SuccBB},
+ {DominatorTree::Insert, PredBB, NewBB},
+ {DominatorTree::Delete, PredBB, BB}});
// If there were values defined in BB that are used outside the block, then we
// now have to update all uses of the value to use either the original value,
@@ -2114,7 +2115,7 @@
BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
}
- DTU->applyUpdates(Updates);
+ DTU->applyUpdatesPermissive(Updates);
return NewBBs[0];
}
@@ -2387,7 +2388,7 @@
// Remove the unconditional branch at the end of the PredBB block.
OldPredBranch->eraseFromParent();
- DTU->applyUpdates(Updates);
+ DTU->applyUpdatesPermissive(Updates);
++NumDupes;
return true;
@@ -2423,8 +2424,8 @@
// The select is now dead.
SI->eraseFromParent();
- DTU->applyUpdates({{DominatorTree::Insert, NewBB, BB},
- {DominatorTree::Insert, Pred, NewBB}});
+ DTU->applyUpdatesPermissive({{DominatorTree::Insert, NewBB, BB},
+ {DominatorTree::Insert, Pred, NewBB}});
// Update any other PHI nodes in BB.
for (BasicBlock::iterator BI = BB->begin();
@@ -2601,7 +2602,7 @@
Updates.push_back({DominatorTree::Delete, BB, Succ});
Updates.push_back({DominatorTree::Insert, SplitBB, Succ});
}
- DTU->applyUpdates(Updates);
+ DTU->applyUpdatesPermissive(Updates);
return true;
}
return false;
diff --git a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp
index 0d6d102..0557b7d 100644
--- a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp
+++ b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp
@@ -101,7 +101,7 @@
DetatchDeadBlocks(BBs, DTU ? &Updates : nullptr, KeepOneInputPHIs);
if (DTU)
- DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(Updates);
for (BasicBlock *BB : BBs)
if (DTU)
@@ -235,7 +235,7 @@
isa<UnreachableInst>(BB->getTerminator()) &&
"The successor list of BB isn't empty before "
"applying corresponding DTU updates.");
- DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(Updates);
DTU->deleteBB(BB);
}
diff --git a/llvm/lib/Transforms/Utils/Local.cpp b/llvm/lib/Transforms/Utils/Local.cpp
index 3ef5494..d14384f 100644
--- a/llvm/lib/Transforms/Utils/Local.cpp
+++ b/llvm/lib/Transforms/Utils/Local.cpp
@@ -128,8 +128,7 @@
Builder.CreateBr(Destination);
BI->eraseFromParent();
if (DTU)
- DTU->applyUpdates({{DominatorTree::Delete, BB, OldDest}},
- /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, OldDest}});
return true;
}
@@ -205,8 +204,8 @@
i = SI->removeCase(i);
e = SI->case_end();
if (DTU)
- DTU->applyUpdates({{DominatorTree::Delete, ParentBB, DefaultDest}},
- /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(
+ {{DominatorTree::Delete, ParentBB, DefaultDest}});
continue;
}
@@ -254,7 +253,7 @@
if (DeleteDeadConditions)
RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
if (DTU)
- DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(Updates);
return true;
}
@@ -332,7 +331,7 @@
}
if (DTU)
- DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(Updates);
return true;
}
}
@@ -666,8 +665,7 @@
if (PhiIt != OldPhiIt) PhiIt = &BB->front();
}
if (DTU)
- DTU->applyUpdates({{DominatorTree::Delete, Pred, BB}},
- /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive({{DominatorTree::Delete, Pred, BB}});
}
/// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its
@@ -736,7 +734,7 @@
isa<UnreachableInst>(PredBB->getTerminator()) &&
"The successor list of PredBB isn't empty before "
"applying corresponding DTU updates.");
- DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(Updates);
DTU->deleteBB(PredBB);
// Recalculation of DomTree is needed when updating a forward DomTree and
// the Entry BB is replaced.
@@ -1078,7 +1076,7 @@
"applying corresponding DTU updates.");
if (DTU) {
- DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(Updates);
DTU->deleteBB(BB);
} else {
BB->eraseFromParent(); // Delete the old basic block.
@@ -1942,7 +1940,7 @@
++NumInstrsRemoved;
}
if (DTU)
- DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(Updates);
return NumInstrsRemoved;
}
@@ -1970,8 +1968,7 @@
UnwindDestBB->removePredecessor(BB);
II->eraseFromParent();
if (DTU)
- DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}},
- /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, UnwindDestBB}});
}
BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI,
@@ -2118,8 +2115,8 @@
UnwindDestBB->removePredecessor(II->getParent());
II->eraseFromParent();
if (DTU)
- DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}},
- /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(
+ {{DominatorTree::Delete, BB, UnwindDestBB}});
} else
changeToCall(II, DTU);
Changed = true;
@@ -2208,8 +2205,7 @@
TI->replaceAllUsesWith(NewTI);
TI->eraseFromParent();
if (DTU)
- DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDest}},
- /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, UnwindDest}});
}
/// removeUnreachableBlocks - Remove blocks that are not reachable, even
@@ -2274,7 +2270,7 @@
}
if (DTU) {
- DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(Updates);
bool Deleted = false;
for (auto *BB : DeadBlockSet) {
if (DTU->isBBPendingDeletion(BB))