diff options
Diffstat (limited to 'llvm/lib/Transforms/Scalar/GVNHoist.cpp')
-rw-r--r-- | llvm/lib/Transforms/Scalar/GVNHoist.cpp | 77 |
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) && |