[NFC] Move RemoveRedundantDbgInstrs outside of inner loop in JumpThreading

[huangjd]

This cleanup action only needs to be performed once when the entire optimization is converged. Doing it in every iteration has a very high time-complexity, as it queries every dbg value in a dense map

Compare before and after for one internal source file with many basic blocks

90% reduction in this extreme case.

[llvmbot]

@llvm/pr-subscribers-llvm-transforms

Author: William Huang (huangjd)

Changes

This cleanup action only needs to be performed once when the entire optimization is converged. Doing it in every iteration has a very high time-complexity, as it queries every dbg value in a dense map

Compare before and after for one internal source file with many basic blocks

>90% reduction in this extreme case.

---

Full diff: https://github.com/llvm/llvm-project/pull/123008.diff

1 Files Affected:

• (modified) llvm/lib/Transforms/Scalar/JumpThreading.cpp (+7-6)

diff --git a/llvm/lib/Transforms/Scalar/JumpThreading.cpp b/llvm/lib/Transforms/Scalar/JumpThreading.cpp
index 300a564e222e16..aae54d9763789b 100644
--- a/llvm/lib/Transforms/Scalar/JumpThreading.cpp
+++ b/llvm/lib/Transforms/Scalar/JumpThreading.cpp
@@ -330,11 +330,6 @@ bool JumpThreadingPass::runImpl(Function &F_, FunctionAnalysisManager *FAM_,
       while (processBlock(&BB)) // Thread all of the branches we can over BB.
         Changed = ChangedSinceLastAnalysisUpdate = true;
 
-      // Jump threading may have introduced redundant debug values into BB
-      // which should be removed.
-      if (Changed)
-        RemoveRedundantDbgInstrs(&BB);
-
       // Stop processing BB if it's the entry or is now deleted. The following
       // routines attempt to eliminate BB and locating a suitable replacement
       // for the entry is non-trivial.
@@ -366,7 +361,6 @@ bool JumpThreadingPass::runImpl(Function &F_, FunctionAnalysisManager *FAM_,
             // detect and transform nested loops later.
             !LoopHeaders.count(&BB) && !LoopHeaders.count(Succ) &&
             TryToSimplifyUncondBranchFromEmptyBlock(&BB, DTU.get())) {
-          RemoveRedundantDbgInstrs(Succ);
           // BB is valid for cleanup here because we passed in DTU. F remains
           // BB's parent until a DTU->getDomTree() event.
           LVI->eraseBlock(&BB);
@@ -377,6 +371,13 @@ bool JumpThreadingPass::runImpl(Function &F_, FunctionAnalysisManager *FAM_,
     EverChanged |= Changed;
   } while (Changed);
 
+  // Jump threading may have introduced redundant debug values into BB which
+  // should be removed.
+  if (EverChanged)
+    for (auto &BB : *F) {
+      RemoveRedundantDbgInstrs(&BB);
+    }
+
   LoopHeaders.clear();
   return EverChanged;
 }

[huangjd]

@SLTozer I saw the patch fe6f6cd giving the reason for introducing the dbg instruction cleanup step. It was causing a compiler performance issue where there's a function with many dbg values and jump threading runs many iteration to converge. I think moving dbg instruction cleanup outside the loop is ok?