summaryrefslogtreecommitdiffstats
path: root/llvm/lib
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib')
-rw-r--r--llvm/lib/Analysis/DomTreeUpdater.cpp123
-rw-r--r--llvm/lib/Transforms/Scalar/CallSiteSplitting.cpp2
-rw-r--r--llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp2
-rw-r--r--llvm/lib/Transforms/Scalar/JumpThreading.cpp25
-rw-r--r--llvm/lib/Transforms/Utils/BasicBlockUtils.cpp4
-rw-r--r--llvm/lib/Transforms/Utils/Local.cpp32
6 files changed, 95 insertions, 93 deletions
diff --git a/llvm/lib/Analysis/DomTreeUpdater.cpp b/llvm/lib/Analysis/DomTreeUpdater.cpp
index e4d505b8f1a..49215889cfd 100644
--- a/llvm/lib/Analysis/DomTreeUpdater.cpp
+++ b/llvm/lib/Analysis/DomTreeUpdater.cpp
@@ -12,11 +12,13 @@
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/DomTreeUpdater.h"
+#include "llvm/ADT/SmallSet.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/IR/Dominators.h"
#include "llvm/Support/GenericDomTree.h"
#include <algorithm>
#include <functional>
+#include <utility>
namespace llvm {
@@ -53,41 +55,6 @@ bool DomTreeUpdater::isSelfDominance(
return Update.getFrom() == Update.getTo();
}
-bool DomTreeUpdater::applyLazyUpdate(DominatorTree::UpdateKind Kind,
- BasicBlock *From, BasicBlock *To) {
- assert((DT || PDT) &&
- "Call applyLazyUpdate() when both DT and PDT are nullptrs.");
- assert(Strategy == DomTreeUpdater::UpdateStrategy::Lazy &&
- "Call applyLazyUpdate() with Eager strategy error");
- // Analyze pending updates to determine if the update is unnecessary.
- const DominatorTree::UpdateType Update = {Kind, From, To};
- const DominatorTree::UpdateType Invert = {Kind != DominatorTree::Insert
- ? DominatorTree::Insert
- : DominatorTree::Delete,
- From, To};
- // Only check duplicates in updates that are not applied by both trees.
- auto I =
- PendUpdates.begin() + std::max(PendDTUpdateIndex, PendPDTUpdateIndex);
- const auto E = PendUpdates.end();
-
- assert(I <= E && "Iterator out of range.");
-
- for (; I != E; ++I) {
- if (Update == *I)
- return false; // Discard duplicate updates.
-
- if (Invert == *I) {
- // Update and Invert are both valid (equivalent to a no-op). Remove
- // Invert from PendUpdates and discard the Update.
- PendUpdates.erase(I);
- return false;
- }
- }
-
- PendUpdates.push_back(Update); // Save the valid update.
- return true;
-}
-
void DomTreeUpdater::applyDomTreeUpdates() {
// No pending DomTreeUpdates.
if (Strategy != UpdateStrategy::Lazy || !DT)
@@ -261,31 +228,15 @@ void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) {
new UnreachableInst(DelBB->getContext(), DelBB);
}
-void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
- bool ForceRemoveDuplicates) {
+void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates) {
if (!DT && !PDT)
return;
- if (Strategy == UpdateStrategy::Lazy || ForceRemoveDuplicates) {
- SmallVector<DominatorTree::UpdateType, 8> Seen;
+ if (Strategy == UpdateStrategy::Lazy) {
for (const auto U : Updates)
- // For Lazy UpdateStrategy, avoid duplicates to applyLazyUpdate() to save
- // on analysis.
- if (llvm::none_of(
- Seen,
- [U](const DominatorTree::UpdateType S) { return S == U; }) &&
- isUpdateValid(U) && !isSelfDominance(U)) {
- Seen.push_back(U);
- if (Strategy == UpdateStrategy::Lazy)
- applyLazyUpdate(U.getKind(), U.getFrom(), U.getTo());
- }
- if (Strategy == UpdateStrategy::Lazy)
- return;
+ if (!isSelfDominance(U))
+ PendUpdates.push_back(U);
- if (DT)
- DT->applyUpdates(Seen);
- if (PDT)
- PDT->applyUpdates(Seen);
return;
}
@@ -295,6 +246,60 @@ void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
PDT->applyUpdates(Updates);
}
+void DomTreeUpdater::applyUpdatesPermissive(
+ ArrayRef<DominatorTree::UpdateType> Updates) {
+ if (!DT && !PDT)
+ return;
+
+ SmallSet<std::pair<BasicBlock *, BasicBlock *>, 8> Seen;
+ SmallVector<DominatorTree::UpdateType, 8> DeduplicatedUpdates;
+ for (const auto U : Updates) {
+ auto Edge = std::make_pair(U.getFrom(), U.getTo());
+ // Because it is illegal to submit updates that have already been applied
+ // and updates to an edge need to be strictly ordered,
+ // it is safe to infer the existence of an edge from the first update
+ // to this edge.
+ // If the first update to an edge is "Delete", it means that the edge
+ // existed before. If the first update to an edge is "Insert", it means
+ // that the edge didn't exist before.
+ //
+ // For example, if the user submits {{Delete, A, B}, {Insert, A, B}},
+ // because
+ // 1. it is illegal to submit updates that have already been applied,
+ // i.e., user cannot delete an nonexistent edge,
+ // 2. updates to an edge need to be strictly ordered,
+ // So, initially edge A -> B existed.
+ // We can then safely ignore future updates to this edge and directly
+ // inspect the current CFG:
+ // a. If the edge still exists, because the user cannot insert an existent
+ // edge, so both {Delete, A, B}, {Insert, A, B} actually happened and
+ // resulted in a no-op. DTU won't submit any update in this case.
+ // b. If the edge doesn't exist, we can then infer that {Delete, A, B}
+ // actually happened but {Insert, A, B} was an invalid update which never
+ // happened. DTU will submit {Delete, A, B} in this case.
+ if (!isSelfDominance(U) && Seen.count(Edge) == 0) {
+ Seen.insert(Edge);
+ // If the update doesn't appear in the CFG, it means that
+ // either the change isn't made or relevant operations
+ // result in a no-op.
+ if (isUpdateValid(U)) {
+ if (isLazy())
+ PendUpdates.push_back(U);
+ else
+ DeduplicatedUpdates.push_back(U);
+ }
+ }
+ }
+
+ if (Strategy == UpdateStrategy::Lazy)
+ return;
+
+ if (DT)
+ DT->applyUpdates(DeduplicatedUpdates);
+ if (PDT)
+ PDT->applyUpdates(DeduplicatedUpdates);
+}
+
DominatorTree &DomTreeUpdater::getDomTree() {
assert(DT && "Invalid acquisition of a null DomTree");
applyDomTreeUpdates();
@@ -331,7 +336,7 @@ void DomTreeUpdater::insertEdge(BasicBlock *From, BasicBlock *To) {
return;
}
- applyLazyUpdate(DominatorTree::Insert, From, To);
+ PendUpdates.push_back({DominatorTree::Insert, From, To});
}
void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
@@ -352,7 +357,7 @@ void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
return;
}
- applyLazyUpdate(DominatorTree::Insert, From, To);
+ PendUpdates.push_back({DominatorTree::Insert, From, To});
}
void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) {
@@ -377,7 +382,7 @@ void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) {
return;
}
- applyLazyUpdate(DominatorTree::Delete, From, To);
+ PendUpdates.push_back({DominatorTree::Delete, From, To});
}
void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
@@ -398,7 +403,7 @@ void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
return;
}
- applyLazyUpdate(DominatorTree::Delete, From, To);
+ PendUpdates.push_back({DominatorTree::Delete, From, To});
}
void DomTreeUpdater::dropOutOfDateUpdates() {
diff --git a/llvm/lib/Transforms/Scalar/CallSiteSplitting.cpp b/llvm/lib/Transforms/Scalar/CallSiteSplitting.cpp
index 8463cebbe79..6b749238d2b 100644
--- a/llvm/lib/Transforms/Scalar/CallSiteSplitting.cpp
+++ b/llvm/lib/Transforms/Scalar/CallSiteSplitting.cpp
@@ -366,7 +366,7 @@ static void splitCallSite(
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 755bf344fb4..e6dd42d893f 100644
--- a/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
+++ b/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
@@ -373,7 +373,7 @@ static bool processSwitch(SwitchInst *SI, LazyValueInfo *LVI,
++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 80b3cd79750..7d6ffa0e0e4 100644
--- a/llvm/lib/Transforms/Scalar/JumpThreading.cpp
+++ b/llvm/lib/Transforms/Scalar/JumpThreading.cpp
@@ -1091,7 +1091,7 @@ bool JumpThreadingPass::ProcessBlock(BasicBlock *BB) {
<< "' 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 @@ bool JumpThreadingPass::ProcessBlock(BasicBlock *BB) {
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 @@ bool JumpThreadingPass::ProcessImpliedCondition(BasicBlock *BB) {
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 @@ bool JumpThreadingPass::ProcessThreadableEdges(Value *Cond, BasicBlock *BB,
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 @@ bool JumpThreadingPass::ThreadEdge(BasicBlock *BB,
}
// 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 @@ BasicBlock *JumpThreadingPass::SplitBlockPreds(BasicBlock *BB,
BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
}
- DTU->applyUpdates(Updates);
+ DTU->applyUpdatesPermissive(Updates);
return NewBBs[0];
}
@@ -2387,7 +2388,7 @@ bool JumpThreadingPass::DuplicateCondBranchOnPHIIntoPred(
// 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 @@ void JumpThreadingPass::UnfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB,
// 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 @@ bool JumpThreadingPass::TryToUnfoldSelectInCurrBB(BasicBlock *BB) {
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 0d6d1022502..0557b7d7442 100644
--- a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp
+++ b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp
@@ -101,7 +101,7 @@ void llvm::DeleteDeadBlocks(ArrayRef <BasicBlock *> BBs, DomTreeUpdater *DTU,
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 @@ bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU,
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 3ef549429b3..d14384fe576 100644
--- a/llvm/lib/Transforms/Utils/Local.cpp
+++ b/llvm/lib/Transforms/Utils/Local.cpp
@@ -128,8 +128,7 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
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 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
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 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
if (DeleteDeadConditions)
RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
if (DTU)
- DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(Updates);
return true;
}
@@ -332,7 +331,7 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
}
if (DTU)
- DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(Updates);
return true;
}
}
@@ -666,8 +665,7 @@ void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred,
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 @@ void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB,
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 @@ bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
"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 @@ unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap,
++NumInstrsRemoved;
}
if (DTU)
- DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(Updates);
return NumInstrsRemoved;
}
@@ -1970,8 +1968,7 @@ static void changeToCall(InvokeInst *II, DomTreeUpdater *DTU = nullptr) {
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 @@ static bool markAliveBlocks(Function &F,
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 @@ void llvm::removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU) {
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 @@ bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI,
}
if (DTU) {
- DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(Updates);
bool Deleted = false;
for (auto *BB : DeadBlockSet) {
if (DTU->isBBPendingDeletion(BB))
OpenPOWER on IntegriCloud