summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/GVNHoist.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Transforms/Scalar/GVNHoist.cpp')
-rw-r--r--llvm/lib/Transforms/Scalar/GVNHoist.cpp77
1 files changed, 46 insertions, 31 deletions
diff --git a/llvm/lib/Transforms/Scalar/GVNHoist.cpp b/llvm/lib/Transforms/Scalar/GVNHoist.cpp
index 53f76dfcfe9..e287ba71e0b 100644
--- a/llvm/lib/Transforms/Scalar/GVNHoist.cpp
+++ b/llvm/lib/Transforms/Scalar/GVNHoist.cpp
@@ -273,24 +273,32 @@ private:
return false;
}
- // Return true when all paths from A to the end of the function pass through
- // either B or C.
- bool hoistingFromAllPaths(const BasicBlock *A, const BasicBlock *B,
- const BasicBlock *C) {
- // We fully copy the WL in order to be able to remove items from it.
- SmallPtrSet<const BasicBlock *, 2> WL;
- WL.insert(B);
- WL.insert(C);
-
- for (auto It = df_begin(A), E = df_end(A); It != E;) {
- // There exists a path from A to the exit of the function if we are still
- // iterating in DF traversal and we removed all instructions from the work
- // list.
- if (WL.empty())
+ // Return true when a successor of BB dominates A.
+ bool successorDominate(const BasicBlock *BB, const BasicBlock *A) {
+ for (const BasicBlock *Succ : BB->getTerminator()->successors())
+ if (DT->dominates(Succ, A))
+ return true;
+
+ return false;
+ }
+
+ // Return true when all paths from HoistBB to the end of the function pass
+ // through one of the blocks in WL.
+ bool hoistingFromAllPaths(const BasicBlock *HoistBB,
+ SmallPtrSetImpl<const BasicBlock *> &WL) {
+
+ // Copy WL as the loop will remove elements from it.
+ SmallPtrSet<const BasicBlock *, 2> WorkList(WL.begin(), WL.end());
+
+ for (auto It = df_begin(HoistBB), E = df_end(HoistBB); It != E;) {
+ // There exists a path from HoistBB to the exit of the function if we are
+ // still iterating in DF traversal and we removed all instructions from
+ // the work list.
+ if (WorkList.empty())
return false;
const BasicBlock *BB = *It;
- if (WL.erase(BB)) {
+ if (WorkList.erase(BB)) {
// Stop DFS traversal when BB is in the work list.
It.skipChildren();
continue;
@@ -300,6 +308,11 @@ private:
if (!isGuaranteedToTransferExecutionToSuccessor(BB->getTerminator()))
return false;
+ // When reaching the back-edge of a loop, there may be a path through the
+ // loop that does not pass through B or C before exiting the loop.
+ if (successorDominate(BB, HoistBB))
+ return false;
+
// Increment DFS traversal when not skipping children.
++It;
}
@@ -476,23 +489,21 @@ private:
return true;
}
- // Return true when it is safe to hoist scalar instructions from BB1 and BB2
- // to HoistBB.
- bool safeToHoistScalar(const BasicBlock *HoistBB, const BasicBlock *BB1,
- const BasicBlock *BB2, int &NBBsOnAllPaths) {
- // Check that the hoisted expression is needed on all paths. When HoistBB
- // already contains an instruction to be hoisted, the expression is needed
- // on all paths. Enable scalar hoisting at -Oz as it is safe to hoist
- // scalars to a place where they are partially needed.
- if (!OptForMinSize && BB1 != HoistBB &&
- !hoistingFromAllPaths(HoistBB, BB1, BB2))
+ // Return true when it is safe to hoist scalar instructions from all blocks in
+ // WL to HoistBB.
+ bool safeToHoistScalar(const BasicBlock *HoistBB,
+ SmallPtrSetImpl<const BasicBlock *> &WL,
+ int &NBBsOnAllPaths) {
+ // Check that the hoisted expression is needed on all paths. Enable scalar
+ // hoisting at -Oz as it is safe to hoist scalars to a place where they are
+ // partially needed.
+ if (!OptForMinSize && !hoistingFromAllPaths(HoistBB, WL))
return false;
- if (hasEHOnPath(HoistBB, BB1, NBBsOnAllPaths) ||
- hasEHOnPath(HoistBB, BB2, NBBsOnAllPaths))
- return false;
+ for (const BasicBlock *BB : WL)
+ if (hasEHOnPath(HoistBB, BB, NBBsOnAllPaths))
+ return false;
- // Safe to hoist scalars from BB1 and BB2 to HoistBB.
return true;
}
@@ -542,8 +553,12 @@ private:
NewHoistPt = NewHoistBB->getTerminator();
}
+ SmallPtrSet<const BasicBlock *, 2> WL;
+ WL.insert(HoistBB);
+ WL.insert(BB);
+
if (K == InsKind::Scalar) {
- if (safeToHoistScalar(NewHoistBB, HoistBB, BB, NBBsOnAllPaths)) {
+ if (safeToHoistScalar(NewHoistBB, WL, NBBsOnAllPaths)) {
// Extend HoistPt to NewHoistPt.
HoistPt = NewHoistPt;
HoistBB = NewHoistBB;
@@ -557,7 +572,7 @@ private:
// loading from the same address: for instance there may be a branch on
// which the address of the load may not be initialized.
if ((HoistBB == NewHoistBB || BB == NewHoistBB ||
- hoistingFromAllPaths(NewHoistBB, HoistBB, BB)) &&
+ hoistingFromAllPaths(NewHoistBB, WL)) &&
// Also check that it is safe to move the load or store from HoistPt
// to NewHoistPt, and from Insn to NewHoistPt.
safeToHoistLdSt(NewHoistPt, HoistPt, UD, K, NBBsOnAllPaths) &&
OpenPOWER on IntegriCloud