Teach LiveDebugValues about lexical scopes.

This addresses PR26055 LiveDebugValues is very slow.

Contrary to the old LiveDebugVariables pass LiveDebugValues currently
doesn't look at the lexical scopes before inserting a DBG_VALUE
intrinsic. This means that we often propagate DBG_VALUEs much further
down than necessary. This is especially noticeable in large C++
functions with many inlined method calls that all use the same
"this"-pointer.

For example, in the following code it makes no sense to propagate the
inlined variable a from the first inlined call to f() into any of the
subsequent basic blocks, because the variable will always be out of
scope:

void sink(int a);
void __attribute((always_inline)) f(int a) { sink(a); }
void foo(int i) {
   f(i);
   if (i)
     f(i);
   f(i);
}

This patch reuses the LexicalScopes infrastructure we have for
LiveDebugVariables to take this into account.

The effect on compile time and memory consumption is quite noticeable:
I tested a benchmark that is a large C++ source with an enormous
amount of inlined "this"-pointers that would previously eat >24GiB
(most of them for DBG_VALUE intrinsics) and whose compile time was
dominated by LiveDebugValues. With this patch applied the memory
consumption is 1GiB and 1.7% of the time is spent in LiveDebugValues.

https://reviews.llvm.org/D24994
Thanks to Daniel Berlin and Keith Walker for reviewing!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@282611 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 228 insertions, 0 deletions

diff --git a/test/DebugInfo/MIR/X86/livedebugvalues-limit.mir b/test/DebugInfo/MIR/X86/livedebugvalues-limit.mir
new file mode 100644
index 00000000000..4c87543636d
--- /dev/null
+++ b/test/DebugInfo/MIR/X86/livedebugvalues-limit.mir
@@ -0,0 +1,228 @@
+--- |
+  ; RUN: llc -run-pass=livedebugvalues -march=x86-64 -o - %s | FileCheck %s
+  ; Created from:
+  ; void sink(int a);
+  ; void __attribute((always_inline)) f(int a) { sink(a); }
+  ; void foo(int i) {
+  ;   f(i);
+  ;   if (i)
+  ;     f(i);
+  ;   f(i);
+  ; }
+  ;
+  ; This test verifies that LiveDebugValues doesn't propagate DBG_VALUEs into
+  ; basic blocks that are beyond the scope of the source variable.
+  ;
+  ; CHECK:  bb.1.if.then:
+  ; CHECK:      DBG_VALUE debug-use %ebx, debug-use _, !19, !13, debug-location !20
+  ; CHECK-NOT:  DBG_VALUE debug-use %ebx, debug-use _, !12, !13, debug-location !21
+  ; CHECK:      DBG_VALUE debug-use %ebx, debug-use _, !12, !13, debug-location !27
+  ; CHECK: bb.2.if.end:
+  ; CHECK:     DBG_VALUE debug-use %ebx, debug-use _, !19, !13, debug-location !20
+  ; CHECK-NOT: DBG_VALUE debug-use %ebx, debug-use _, !12, !13, debug-location !21
+  ; CHECK:     DBG_VALUE debug-use %ebx, debug-use _, !12, !13, debug-location !31
+  ;
+  ; ModuleID = 'livedebugvalues-limit.ll'
+  source_filename = "livedebugvalues-limit.c"
+  target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+  target triple = "x86_64-apple-macosx"
+  
+  ; Function Attrs: alwaysinline nounwind ssp uwtable
+  define void @f(i32 %a) local_unnamed_addr #0 !dbg !7 {
+  entry:
+    tail call void @llvm.dbg.value(metadata i32 %a, i64 0, metadata !12, metadata !13), !dbg !14
+    tail call void @sink(i32 %a) #4, !dbg !15
+    ret void, !dbg !16
+  }
+  
+  declare void @sink(i32) local_unnamed_addr
+  
+  ; Function Attrs: nounwind ssp uwtable
+  define void @foo(i32 %i) local_unnamed_addr #2 !dbg !17 {
+  entry:
+    tail call void @llvm.dbg.value(metadata i32 %i, i64 0, metadata !19, metadata !13), !dbg !20
+    tail call void @llvm.dbg.value(metadata i32 %i, i64 0, metadata !12, metadata !13) #4, !dbg !21
+    tail call void @sink(i32 %i) #4, !dbg !23
+    %tobool = icmp eq i32 %i, 0, !dbg !24
+    br i1 %tobool, label %if.end, label %if.then, !dbg !26
+  
+  if.then:                                          ; preds = %entry
+    tail call void @llvm.dbg.value(metadata i32 %i, i64 0, metadata !12, metadata !13) #4, !dbg !27
+    tail call void @sink(i32 %i) #4, !dbg !29
+    br label %if.end, !dbg !30
+  
+  if.end:                                           ; preds = %if.then, %entry
+    tail call void @llvm.dbg.value(metadata i32 %i, i64 0, metadata !12, metadata !13) #4, !dbg !31
+    tail call void @sink(i32 %i) #4, !dbg !33
+    ret void, !dbg !34
+  }
+  
+  ; Function Attrs: nounwind readnone
+  declare void @llvm.dbg.value(metadata, i64, metadata, metadata) #3
+  
+  ; Function Attrs: nounwind
+  declare void @llvm.stackprotector(i8*, i8**) #4
+  
+  attributes #0 = { alwaysinline nounwind ssp uwtable }
+  attributes #2 = { nounwind ssp uwtable }
+  attributes #3 = { nounwind readnone }
+  attributes #4 = { nounwind }
+  
+  !llvm.dbg.cu = !{!0}
+  !llvm.module.flags = !{!3, !4, !5}
+  !llvm.ident = !{!6}
+  
+  !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 4.0.0 (trunk 281923) (llvm/trunk 281916)", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
+  !1 = !DIFile(filename: "livedebugvalues-limit.c", directory: "/Volumes/Fusion/Data/llvm")
+  !2 = !{}
+  !3 = !{i32 2, !"Dwarf Version", i32 4}
+  !4 = !{i32 2, !"Debug Info Version", i32 3}
+  !5 = !{i32 1, !"PIC Level", i32 2}
+  !6 = !{!"clang version 4.0.0 (trunk 281923) (llvm/trunk 281916)"}
+  !7 = distinct !DISubprogram(name: "f", scope: !1, file: !1, line: 3, type: !8, isLocal: false, isDefinition: true, scopeLine: 3, flags: DIFlagPrototyped, isOptimized: true, unit: !0, variables: !11)
+  !8 = !DISubroutineType(types: !9)
+  !9 = !{null, !10}
+  !10 = !DIBasicType(name: "int", size: 32, align: 32, encoding: DW_ATE_signed)
+  !11 = !{!12}
+  !12 = !DILocalVariable(name: "a", arg: 1, scope: !7, file: !1, line: 3, type: !10)
+  !13 = !DIExpression()
+  !14 = !DILocation(line: 3, column: 41, scope: !7)
+  !15 = !DILocation(line: 3, column: 46, scope: !7)
+  !16 = !DILocation(line: 3, column: 55, scope: !7)
+  !17 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 4, type: !8, isLocal: false, isDefinition: true, scopeLine: 4, flags: DIFlagPrototyped, isOptimized: true, unit: !0, variables: !18)
+  !18 = !{!19}
+  !19 = !DILocalVariable(name: "i", arg: 1, scope: !17, file: !1, line: 4, type: !10)
+  !20 = !DILocation(line: 4, column: 14, scope: !17)
+  !21 = !DILocation(line: 3, column: 41, scope: !7, inlinedAt: !22)
+  !22 = distinct !DILocation(line: 5, column: 3, scope: !17)
+  !23 = !DILocation(line: 3, column: 46, scope: !7, inlinedAt: !22)
+  !24 = !DILocation(line: 6, column: 7, scope: !25)
+  !25 = distinct !DILexicalBlock(scope: !17, file: !1, line: 6, column: 7)
+  !26 = !DILocation(line: 6, column: 7, scope: !17)
+  !27 = !DILocation(line: 3, column: 41, scope: !7, inlinedAt: !28)
+  !28 = distinct !DILocation(line: 7, column: 5, scope: !25)
+  !29 = !DILocation(line: 3, column: 46, scope: !7, inlinedAt: !28)
+  !30 = !DILocation(line: 7, column: 5, scope: !25)
+  !31 = !DILocation(line: 3, column: 41, scope: !7, inlinedAt: !32)
+  !32 = distinct !DILocation(line: 8, column: 3, scope: !17)
+  !33 = !DILocation(line: 3, column: 46, scope: !7, inlinedAt: !32)
+  !34 = !DILocation(line: 9, column: 1, scope: !17)
+
+...
+---
+name:            f
+alignment:       4
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+tracksRegLiveness: true
+liveins:         
+  - { reg: '%edi' }
+calleeSavedRegisters: [ '%bh', '%bl', '%bp', '%bpl', '%bx', '%ebp', '%ebx', 
+                        '%rbp', '%rbx', '%r12', '%r13', '%r14', '%r15', 
+                        '%r12b', '%r13b', '%r14b', '%r15b', '%r12d', '%r13d', 
+                        '%r14d', '%r15d', '%r12w', '%r13w', '%r14w', '%r15w' ]
+frameInfo:       
+  isFrameAddressTaken: false
+  isReturnAddressTaken: false
+  hasStackMap:     false
+  hasPatchPoint:   false
+  stackSize:       8
+  offsetAdjustment: 0
+  maxAlignment:    0
+  adjustsStack:    false
+  hasCalls:        false
+  maxCallFrameSize: 0
+  hasOpaqueSPAdjustment: false
+  hasVAStart:      false
+  hasMustTailInVarArgFunc: false
+fixedStack:      
+  - { id: 0, type: spill-slot, offset: -16, size: 8, alignment: 16 }
+body:             |
+  bb.0.entry:
+    liveins: %edi, %rbp
+  
+    frame-setup PUSH64r killed %rbp, implicit-def %rsp, implicit %rsp
+    CFI_INSTRUCTION def_cfa_offset 16
+    CFI_INSTRUCTION offset %rbp, -16
+    %rbp = frame-setup MOV64rr %rsp
+    CFI_INSTRUCTION def_cfa_register %rbp
+    DBG_VALUE debug-use %edi, debug-use _, !12, !13, debug-location !14
+    %rbp = POP64r implicit-def %rsp, implicit %rsp, debug-location !15
+    TAILJMPd64 @sink, csr_64, implicit %rsp, implicit %rsp, implicit %edi, debug-location !15
+
+...
+---
+name:            foo
+alignment:       4
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+tracksRegLiveness: true
+liveins:         
+  - { reg: '%edi' }
+calleeSavedRegisters: [ '%bh', '%bl', '%bp', '%bpl', '%bx', '%ebp', '%ebx', 
+                        '%rbp', '%rbx', '%r12', '%r13', '%r14', '%r15', 
+                        '%r12b', '%r13b', '%r14b', '%r15b', '%r12d', '%r13d', 
+                        '%r14d', '%r15d', '%r12w', '%r13w', '%r14w', '%r15w' ]
+frameInfo:       
+  isFrameAddressTaken: false
+  isReturnAddressTaken: false
+  hasStackMap:     false
+  hasPatchPoint:   false
+  stackSize:       24
+  offsetAdjustment: -8
+  maxAlignment:    0
+  adjustsStack:    true
+  hasCalls:        true
+  maxCallFrameSize: 0
+  hasOpaqueSPAdjustment: false
+  hasVAStart:      false
+  hasMustTailInVarArgFunc: false
+fixedStack:      
+  - { id: 0, type: spill-slot, offset: -24, size: 8, alignment: 8, callee-saved-register: '%rbx' }
+  - { id: 1, type: spill-slot, offset: -16, size: 8, alignment: 16 }
+body:             |
+  bb.0.entry:
+    successors: %bb.2.if.end, %bb.1.if.then
+    liveins: %edi, %rbx, %rbp
+  
+    frame-setup PUSH64r killed %rbp, implicit-def %rsp, implicit %rsp
+    CFI_INSTRUCTION def_cfa_offset 16
+    CFI_INSTRUCTION offset %rbp, -16
+    %rbp = frame-setup MOV64rr %rsp
+    CFI_INSTRUCTION def_cfa_register %rbp
+    frame-setup PUSH64r killed %rbx, implicit-def %rsp, implicit %rsp
+    frame-setup PUSH64r undef %rax, implicit-def %rsp, implicit %rsp
+    CFI_INSTRUCTION offset %rbx, -24
+    DBG_VALUE debug-use %edi, debug-use _, !19, !13, debug-location !20
+    %ebx = MOV32rr %edi
+    DBG_VALUE debug-use %ebx, debug-use _, !12, !13, debug-location !21
+    DBG_VALUE debug-use %ebx, debug-use _, !19, !13, debug-location !20
+    CALL64pcrel32 @sink, csr_64, implicit %rsp, implicit %edi, implicit-def %rsp, debug-location !23
+    TEST32rr %ebx, %ebx, implicit-def %eflags, debug-location !24
+    JE_1 %bb.2.if.end, implicit %eflags
+  
+  bb.1.if.then:
+    successors: %bb.2.if.end
+    liveins: %ebx, %rbp
+  
+    DBG_VALUE debug-use %ebx, debug-use _, !19, !13, debug-location !20
+    DBG_VALUE debug-use %ebx, debug-use _, !12, !13, debug-location !27
+    %edi = MOV32rr %ebx, debug-location !29
+    CALL64pcrel32 @sink, csr_64, implicit %rsp, implicit %edi, implicit-def %rsp, debug-location !29
+  
+  bb.2.if.end:
+    liveins: %ebx, %rbp
+  
+    DBG_VALUE debug-use %ebx, debug-use _, !19, !13, debug-location !20
+    %edi = MOV32rr killed %ebx, debug-location !33
+    %rsp = ADD64ri8 %rsp, 8, implicit-def dead %eflags, debug-location !33
+    DBG_VALUE debug-use %ebx, debug-use _, !12, !13, debug-location !31
+    %rbx = POP64r implicit-def %rsp, implicit %rsp, debug-location !33
+    %rbp = POP64r implicit-def %rsp, implicit %rsp, debug-location !33
+    TAILJMPd64 @sink, csr_64, implicit %rsp, implicit %rsp, implicit %edi, debug-location !33
+
+...