Prevent explosion of debug intrinsics during jump threading

[StephenTozer]

Summary

This patch is a fix following the revert of 72ce759 (https://reviews.llvm.org/rG72ce759928e6dfee6a9efa310b966c19722352ba) and fixes the failure that it caused.

The above patch failed on the Thread Sanitizer buildbot with an out of memory error. After an investigation, the cause was identified as an explosion in debug intrinsics while running the Jump Threading pass on ModuleMap.ll. The above patched prevented debug intrinsics from being dropped when their Basic Block was deleted due to being "empty". In this case, one of the functions in ModuleMap.ll had (after many optimization passes) a very large number of debug intrinsics representing a set of repeatedly inlined variables. Previously the vast majority of these were silently dropped during Jump Threading when their blocks were deleted, but as of the above patch they survived for longer, causing a large increase in the number of debug intrinsics. These intrinsics were then repeatedly cloned by the Jump Threading pass as edges were threaded, multiplying the intrinsic count further. The memory consumed by this process spiralled out of control, crashing the buildbot that uses TSan (which has an estimated 5-10x memory overhead compared to non-sanitized builds).

In order to rein in the number of debug intrinsics, I have added RemoveRedundantDbgInstrs to the Jump Threading pass. This recently added function (https://reviews.llvm.org/D71478) processes a Basic Block and removes any debug intrinsics that are "redundant", i.e. they are either identical to a previous intrinsic for the same source variable in the same block, or immediately overwritten by another intrinsic with no intermediate instructions. As many intrinsics for the same variable end up propagated into the same blocks during this case, the removal of redundant intrinsics from each block as they are processed is effective are reducing the number of intrinsics from exploding in the same manner.

This seems to bring the number of intrinsics for this case down to a manageable level in practice, and should be sufficient to unblock the above patch for remerging. It does seem likely to me that there are other passes for which this function would also be appropriate; this is probably worth looking into after the immediate problem is solved.

[djtodoro]

Thanks for working on this! Please add a test case.

[Orlando]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

432

nit: I think RemoveRedundantDbgInsts should moved above the comment it currently follows.

[StephenTozer]

Add test, address nit comment. Note that some of the current test checks should pass even without this patch if commit 636c93 is not reverted, as some of the redundant debug info would be dropped.

[djtodoro]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

6

*threading*

[StephenTozer]

Fix spelling error.

llvm/lib/Transforms/Scalar/JumpThreading.cpp

 //===- JumpThreading.cpp - Thread control through conditional blocks ------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the Jump Threading pass.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/JumpThreading.h"
 #include "llvm/ADT/DenseMap.h"
for (auto &BB : F) {
         DeleteDeadBlock(&BB, DTU);
         Changed = true;
         continue;
       }
 
       // ProcessBlock doesn't thread BBs with unconditional TIs. However, if BB
       // is "almost empty", we attempt to merge BB with its sole successor.
       auto *BI = dyn_cast<BranchInst>(BB.getTerminator());
-      if (BI && BI->isUnconditional() &&
+      if (BI && BI->isUnconditional()) {
+        BasicBlock *Succ = BI->getSuccessor(0);
+        if (
             // The terminator must be the only non-phi instruction in BB.
             BB.getFirstNonPHIOrDbg()->isTerminator() &&
             // Don't alter Loop headers and latches to ensure another pass can
             // detect and transform nested loops later.
-          !LoopHeaders.count(&BB) && !LoopHeaders.count(BI->getSuccessor(0)) &&
+            !LoopHeaders.count(&BB) && !LoopHeaders.count(Succ) &&
             TryToSimplifyUncondBranchFromEmptyBlock(&BB, DTU)) {
           // BB is valid for cleanup here because we passed in DTU. F remains
           // BB's parent until a DTU->getDomTree() event.
+          RemoveRedundantDbgInstrs(Succ);
           LVI->eraseBlock(&BB);
           Changed = true;
         }
       }
+    }
     EverChanged |= Changed;
   } while (Changed);
 
   LoopHeaders.clear();
   // Flush only the Dominator Tree.
   DTU->getDomTree();
   LVI->enableDT();
   return EverChanged;