[StripDeadDebugInfo] Drop dead CUs

[bader]

Summary

In situations when a submodule is extracted from big module (i.e. using
CloneModule) a lot of debug info is copied via metadata nodes. Despite of
the fact that part of that info is not linked to any instruction in extracted
IR file, StripDeadDebugInfo pass doesn't drop them.
Strengthen criteria for debug info that should be kept in a module:

• Only those compile units are left that referenced by a subprogram debug info

node that is attached to a function definition in the module or to an instruction
in the module that belongs to an inlined function.

• Compile units are not left explicitly if they have const global expression.

They should be left if that const global is used in a function that is contained
in extracted module.

Signed-off-by: Mikhail Lychkov <[e-mail]>

[mlychkov]

Reduce code duplication.

[mlychkov]

Added a check that an instruction is inlined before to try to find inlined CUs.

[aprantl]

llvm/lib/Transforms/IPO/StripSymbols.cpp

299

Can you add a doxygen comment explaining what this function does?

300

This is highly subjective, but to me, 32 seems a bit large for a smallptrset. Did you base that number on any performance measurements?

337

This change seems to be unrelated to the above change, and it might be better to discuss it in a separate review. Is this going to drop all constant globals?

373

how about sinking the getInlinedAt() into collectCUsForInlinedFuncs() so we don't check for if(Loc) twice?

[bader]

Applied code review suggestions.

[bader]

@aprantl, sorry for the delay. I'd like to finish this patch on behalf of @mlychkov.
I've applied all your suggestions. Please, take a look.

llvm/lib/Transforms/IPO/StripSymbols.cpp

300

I reduced 32 -> 8, but I haven't done any performance measurements, so let me know if it sounds reasonable to you.

337

I removed this part of the patch, so let discuss it in a separate review.

[bader]

llvm/lib/Transforms/IPO/StripSymbols.cpp

337

I moved that change to https://reviews.llvm.org/D131179.

[bader]

Apply clang-format. No functional changes.

[bader]

Ping.

[bader]

@aprantl, thank you a lot for reviewing this patch. Could you also take a look at the part moved to https://reviews.llvm.org/D131179, please?

llvm/lib/Transforms/IPO/StripSymbols.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/IPO/StripSymbols.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/TypeFinder.h"
 #include "llvm/IR/ValueSymbolTable.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Transforms/IPO.h"

 }
 
 bool StripDebugDeclare::runOnModule(Module &M) {
   if (skipModule(M))
     return false;
   return stripDebugDeclareImpl(M);
 }
 
+/// Collects compilation units referenced by functions or lexical scopes.
+/// Accepts any DIScope and uses recursive bottom-up approach to reach either
+/// DISubprogram or DILexicalBlockBase.
+static void
+collectCUsWithScope(const DIScope *Scope, std::set<DICompileUnit *> &LiveCUs,
+                    SmallPtrSet<const DIScope *, 8> &VisitedScopes) {
+  if (!Scope)
+    return;
+
+  auto InS = VisitedScopes.insert(Scope);
+  if (!InS.second)
+    return;
+
+  if (const auto *SP = dyn_cast<DISubprogram>(Scope)) {
+    if (SP->getUnit())
+      LiveCUs.insert(SP->getUnit());
+    return;
+  }
+  if (const auto *LB = dyn_cast<DILexicalBlockBase>(Scope)) {
+    const DISubprogram *SP = LB->getSubprogram();
+    if (SP && SP->getUnit())
+      LiveCUs.insert(SP->getUnit());
+    return;
+  }
+
+  collectCUsWithScope(Scope->getScope(), LiveCUs, VisitedScopes);
+}
+
+static void
+collectCUsForInlinedFuncs(const DILocation *Loc,
+                          std::set<DICompileUnit *> &LiveCUs,
+                          SmallPtrSet<const DIScope *, 8> &VisitedScopes) {
+  if (!Loc || !Loc->getInlinedAt())
+    return;
+  collectCUsWithScope(Loc->getScope(), LiveCUs, VisitedScopes);
+  collectCUsForInlinedFuncs(Loc->getInlinedAt(), LiveCUs, VisitedScopes);
+}
+
 static bool stripDeadDebugInfoImpl(Module &M) {
   bool Changed = false;
 
   LLVMContext &C = M.getContext();
 
   // Find all debug info in F. This is actually overkill in terms of what we
   // want to do, but we want to try and be as resilient as possible in the face
   // of potential debug info changes by using the formal interfaces given to us
static bool stripDeadDebugInfoImpl(Module &M) {
   for (GlobalVariable &GV : M.globals()) {
     SmallVector<DIGlobalVariableExpression *, 1> GVEs;
     GV.getDebugInfo(GVEs);
     for (auto *GVE : GVEs)
       LiveGVs.insert(GVE);
   }
 
   std::set<DICompileUnit *> LiveCUs;
-  // Any CU referenced from a subprogram is live.
-  for (DISubprogram *SP : F.subprograms()) {
-    if (SP->getUnit())
-      LiveCUs.insert(SP->getUnit());
+  SmallPtrSet<const DIScope *, 8> VisitedScopes;
+  // Any CU is live if is referenced from a subprogram metadata that is attached
+  // to a function defined or inlined in the module.
+  for (const Function &Fn : M.functions()) {
+    collectCUsWithScope(Fn.getSubprogram(), LiveCUs, VisitedScopes);
+    for (const_inst_iterator I = inst_begin(&Fn), E = inst_end(&Fn); I != E;
+         ++I) {
+      if (!I->getDebugLoc())
+        continue;
+      const DILocation *DILoc = I->getDebugLoc().get();
+      collectCUsForInlinedFuncs(DILoc, LiveCUs, VisitedScopes);
+    }
   }
 
   bool HasDeadCUs = false;
   for (DICompileUnit *DIC : F.compile_units()) {
     // Create our live global variable list.
     bool GlobalVariableChange = false;
     for (auto *DIG : DIC->getGlobalVariables()) {
       if (DIG->getExpression() && DIG->getExpression()->isConstant())
         LiveGVs.insert(DIG);
 
       // Make sure we only visit each global variable only once.
       if (!VisitedSet.insert(DIG).second)
         continue;
 
       // If a global variable references DIG, the global variable is live.
       if (LiveGVs.count(DIG))
         LiveGlobalVariables.push_back(DIG);
       else

llvm/test/Transforms/StripSymbols/strip-cu-with-dangling-subprogram.ll

+; This test checks that strip-dead-debug-info pass deletes debug compile units
+; if functions from those units are absent in that module.
+
+; RUN: opt -passes='strip-dead-debug-info,verify' %s -S | FileCheck %s
+
+; CHECK: !llvm.dbg.cu = !{!{{[0-9]+}}, !{{[0-9]+}}}
+; CHECK-COUNT-2: !DICompileUnit
+
+;target datalayout = "e-i64:64-v16:16-v24:32-v32:32-v48:64-v96:128-v192:256-v256:256-v512:512-v1024:1024-n8:16:32:64"
+;target triple = "spir64-unknown-unknown"
+
+; Function Attrs: nounwind
+define void @dev_func1() #0 !dbg !13 {
+  ret void, !dbg !14
+}
+
+; Function Attrs: nounwind
+define void @dev_func2() #0 !dbg !15 {
+  ret void, !dbg !16
+}
+
+attributes #0 = { nounwind }
+
+!llvm.dbg.cu = !{!0, !3, !5}
+!llvm.module.flags = !{!12}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !1, producer: "clang", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, imports: !2, splitDebugInlining: false, nameTableKind: None)
+!1 = !DIFile(filename: "dev_func1.cpp", directory: "/home/user/test")
+!2 = !{}
+!3 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !4, producer: "clang", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, imports: !2, splitDebugInlining: false, nameTableKind: None)
+!4 = !DIFile(filename: "dev_func2.cpp", directory: "/home/user/test")
+!5 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !6, producer: "clang", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, retainedTypes: !2, imports: !7, splitDebugInlining: false, nameTableKind: None)
+!6 = !DIFile(filename: "dev_func3.cpp", directory: "/home/user/test")
+!7 = !{!8}
+!8 = !DIImportedEntity(tag: DW_TAG_imported_declaration, scope: !6, entity: !9, file: !6, line: 129)
+!9 = distinct !DISubprogram(name: "dev_func3", linkageName: "dev_func3", scope: !6, file: !6, line: 96, type: !10, scopeLine: 96, flags: DIFlagPrototyped, spFlags: DISPFlagLocalToUnit | DISPFlagDefinition, unit: !5, retainedNodes: !2)
+!10 = !DISubroutineType(types: !11)
+!11 = !{null}
+!12 = !{i32 2, !"Debug Info Version", i32 3}
+!13 = distinct !DISubprogram(name: "dev_func1", linkageName: "dev_func1", scope: !1, file: !1, line: 22, type: !10, scopeLine: 22, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)
+!14 = !DILocation(line: 29, column: 5, scope: !13)
+!15 = distinct !DISubprogram(name: "dev_func2", linkageName: "dev_func2", scope: !4, file: !4, line: 22, type: !10, scopeLine: 22, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !3, retainedNodes: !2)
+!16 = !DILocation(line: 29, column: 5, scope: !15)