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

21

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

409

*threading*

[StephenTozer]

Fix spelling error.

llvm/lib/Transforms/Scalar/JumpThreading.cpp

 #include "llvm/Transforms/Scalar/JumpThreading.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/GuardUtils.h"
 #include "llvm/Analysis/InstructionSimplify.h"
bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
   bool Changed;
   do {
     Changed = false;
     for (auto &BB : F) {
       if (Unreachable.count(&BB))
         continue;
       while (ProcessBlock(&BB)) // Thread all of the branches we can over BB.
         Changed = 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.
       if (&BB == &F.getEntryBlock() || DTU->isBBPendingDeletion(&BB))
         continue;
 
       if (pred_empty(&BB)) {
         // When ProcessBlock makes BB unreachable it doesn't bother to fix up
         // the instructions in it. We must remove BB to prevent invalid IR.
         LLVM_DEBUG(dbgs() << "  JT: Deleting dead block '" << BB.getName()
                           << "' with terminator: " << *BB.getTerminator()
                           << '\n');
         LoopHeaders.erase(&BB);
         LVI->eraseBlock(&BB);
         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)) {
+          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);
           Changed = true;
         }
       }
+    }
     EverChanged |= Changed;
   } while (Changed);
 
   LoopHeaders.clear();
   // Flush only the Dominator Tree.
   DTU->getDomTree();
   LVI->enableDT();
   return EverChanged;

llvm/test/Transforms/JumpThreading/redundant-dbg-info.ll

+; RUN: opt -jump-threading -S < %s | FileCheck %s
+
+define dso_local i32 @_Z3fooi(i32 %a) !dbg !7 {
+entry:
+  call void @llvm.dbg.value(metadata i32 %a, metadata !12, metadata !DIExpression()), !dbg !13
+  call void @llvm.dbg.value(metadata i32 1, metadata !14, metadata !DIExpression()), !dbg !13
+  %tobool = icmp ne i32 %a, 0, !dbg !15
+  br i1 %tobool, label %if.then, label %if.end, !dbg !17
+
+if.then:                                          ; preds = %entry
+  call void @_Z4callv(), !dbg !18
+  call void @llvm.dbg.value(metadata i32 0, metadata !14, metadata !DIExpression()), !dbg !13
+  br label %if.end, !dbg !20
+
+if.end:                                           ; preds = %if.then, %entry
+  %c.0 = phi i32 [ 0, %if.then ], [ 1, %entry ], !dbg !13
+  call void @llvm.dbg.value(metadata i32 %c.0, metadata !14, metadata !DIExpression()), !dbg !13
+  %tobool1 = icmp ne i32 %c.0, 0, !dbg !21
+  br i1 %tobool1, label %if.else, label %if.then2, !dbg !23
+
+; CHECK-LABEL: if.then2:
+; CHECK: call void @llvm.dbg.value({{.+}}, metadata ![[B:[0-9]+]], metadata !DIExpression())
+; CHECK: call void @llvm.dbg.value({{.+}}, metadata ![[B:[0-9]+]], metadata !DIExpression())
+; CHECK-NOT: call void @llvm.dbg.value({{.+}}, metadata ![[B]], metadata !DIExpression())
+if.then2:                                         ; preds = %if.end
+  call void @llvm.dbg.value(metadata i32 4, metadata !24, metadata !DIExpression()), !dbg !13
+  br label %if.end3, !dbg !25
+
+; CHECK-LABEL: if.end3:
+if.else:                                          ; preds = %if.end
+  call void @llvm.dbg.value(metadata i32 6, metadata !24, metadata !DIExpression()), !dbg !13
+  br label %if.end3
+
+if.end3:                                          ; preds = %if.else, %if.then2
+  %b.0 = phi i32 [ 6, %if.else ], [ 4, %if.then2 ], !dbg !27
+  call void @llvm.dbg.value(metadata i32 %b.0, metadata !24, metadata !DIExpression()), !dbg !13
+  ret i32 %b.0, !dbg !28
+}
+; Function Attrs: nounwind readnone speculatable willreturn
+declare void @llvm.dbg.declare(metadata, metadata, metadata)
+declare dso_local void @_Z4callv()
+; Function Attrs: nounwind readnone speculatable willreturn
+declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4, !5}
+!llvm.ident = !{!6}
+
+; CHECK: ![[B]] = !DILocalVariable(name: "b"
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !1, producer: "clang version 10.0.0", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
+!1 = !DIFile(filename: "test.cpp", directory: "/")
+!2 = !{}
+!3 = !{i32 7, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{i32 1, !"wchar_size", i32 4}
+!6 = !{!"clang version 10.0.0"}
+!7 = distinct !DISubprogram(name: "foo", linkageName: "_Z3fooi", scope: !8, file: !8, line: 3, type: !9, scopeLine: 3, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)
+!8 = !DIFile(filename: "./test.cpp", directory: "/")
+!9 = !DISubroutineType(types: !10)
+!10 = !{!11, !11}
+!11 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!12 = !DILocalVariable(name: "a", arg: 1, scope: !7, file: !8, line: 3, type: !11)
+!13 = !DILocation(line: 0, scope: !7)
+!14 = !DILocalVariable(name: "c", scope: !7, file: !8, line: 4, type: !11)
+!15 = !DILocation(line: 5, column: 7, scope: !16)
+!16 = distinct !DILexicalBlock(scope: !7, file: !8, line: 5, column: 7)
+!17 = !DILocation(line: 5, column: 7, scope: !7)
+!18 = !DILocation(line: 6, column: 5, scope: !19)
+!19 = distinct !DILexicalBlock(scope: !16, file: !8, line: 5, column: 10)
+!20 = !DILocation(line: 8, column: 3, scope: !19)
+!21 = !DILocation(line: 9, column: 8, scope: !22)
+!22 = distinct !DILexicalBlock(scope: !7, file: !8, line: 9, column: 7)
+!23 = !DILocation(line: 9, column: 7, scope: !7)
+!24 = !DILocalVariable(name: "b", scope: !7, file: !8, line: 4, type: !11)
+!25 = !DILocation(line: 11, column: 3, scope: !26)
+!26 = distinct !DILexicalBlock(scope: !22, file: !8, line: 9, column: 11)
+!27 = !DILocation(line: 0, scope: !22)
+!28 = !DILocation(line: 14, column: 3, scope: !7)