Emit 'no line' information for interesting 'orphan' instructions

[probinson]

Summary

(Based on D16569 by friss; that revision was 'abandoned' so I needed to
create a new one. The following description is derived from his.)

There will always be instructions with no line information attached.
One example is the LocalValue constants generated by FastISel, but
it's by far not the only one. Compiler generated code will have no
line info and might get inlined. SelectionDAG is full of nodes that
won't have any line information (because they could be shared).

Multiple attempts have been made over time to fix the FastISel issue,
but none have felt satisfactory enough to be committed. As the problem
is much more general than just FastISel, this patch addresses it
at line table emission time rather than instruction selection time.

It also doesn't try to give accurate line information for these
instructions, but rather marks them with a 'no line' indicator so that
the debugger can safely ignore them.

The implemented heuristic will add 'no line' information to every insn
without explicit line information and either:

• at the beginning of a basic-block
• first instruction after a label

The first condition handles the FastISel case, while the second
enforces that any instruction referenced by anything (including debug
info) has line information.

The patch handles both DWARF and Codeview, using line number 0 for
DWARF and the reserved 'NeverStepIntoLineNumber' value for Codeview.
(I know almost nothing about Codeview so that might not be best...)

The initial measurements on DWARF line table size show an impact
between 5% and 15% (the latter is for a control-flow heavy code
eg. ASANified).

There was already an option to use DWARF 'line 0' information for all
the instructions with no debug locations. The commit history for this
code show that it was disabled because it caused issues with GDB and
with the line table size. Note that this code was unconditionally
emitting the line 0 information and not using a heuristic to find
interesting instructions like this one.

This patch has been tested on GDB-7.8 and current LLDB (pretty
sure I got the LLDB part right, but it's hard to tell). GDB showed no
differences, and LLDB had one XPASS (but I am not sure that isn't
just a fluke, as it was 'test_process_interrupt_dwarf' and I've had
flakiness problems with GDB thread-related tests in the past).
I don't know how to test the Codeview side.

[probinson]

Ping.

[rnk]

I don't know if you have the time or interest in doing this, but here's how I'd test the codeview side.

First, compile something like a main function with ~5 volatile stores to a .s file with clang -g -gcodeview foo.c -o foo.s. Manually insert nops and .cv_loc directives in between the stores. Assemble it and link it into a complete program with clang. Run windbg -Q foo.exe, break on foo!main, and step by line from there and see what happens.

Once we do that, then we can know what NeverStepIntoLineNumber really does. Right now, I have no idea what it does, and without some information about that, I'd rather not record anything for these kinds of instructions so that we can have more compact line tables.

[probinson]

Thanks for the codeview recipe! I'll try that when I get a chance.

[probinson]

In D24180#545101, @rnk wrote:

I don't know if you have the time or interest in doing this, but here's how I'd test the codeview side.

Even with spending most of a day on it, I completely fail at getting windbg to find 'main' and set a breakpoint. Even for a test program built with Visual Studio, I can't figure out how to persuade windbg to find the symbols.

Once we do that, then we can know what NeverStepIntoLineNumber really does. Right now, I have no idea what it does, and without some information about that, I'd rather not record anything for these kinds of instructions so that we can have more compact line tables.

I guess that means I should undo the CV parts of this patch.

We will need to figure out *something* for CV, because it is already the case that some places are explicitly setting a DebugLoc with line 0, and actually emitting line 0 into CV seems like the wrong result.

[probinson]

Updated patch to take care of four things.

1. Internal testing came up with situations where the patch would emit multiple line-0 records in a row. We now avoid that.

2. We also found cases along these lines:

.loc 1 9 0
instr1
instr2
.loc 1 0 0
instr3
.loc 1 9 0
instr4

The naive statement-marking algorithm would put is_stmt 1 on both instr1 and instr4, which is not good for debugging. The updated patch detects this situation and puts is_stmt 0 on instr4.

3. We aren't sure what to emit for CodeView, so as advised by @rnk this patch now does nothing for CodeView.

4. The updated patch exposed an inadvertent flaw in test/CodeGen/X86/stack-protector.ll where a function marked as having debug info actually had no source location attached to any instructions. This led to emitting .loc 1 0 0 prologue_end which is obviously flawed. Attaching an actual source location to one of the instructions emits a much more sensible line table.

[rnk]

I'm fine leaving CV alone for now until we learn more.

lib/CodeGen/AsmPrinter/DebugHandlerBase.h

46

If you initialize this here to nullptr, you don't have to change the constructor.

[dblaikie]

Haven't fully followed the change, but did some tests at least - about a 7-7.5% regression (compressed or uncompressed) on a large program at Google. The line table's already larger (in absolute, and relative to the .text size (which is about about 11% smaller for LLVM)) than GCC's, but not by much (also somewhat not surprising that smaller .text might have larger line table - code might've been shuffled around more, have finer grained line table entries, etc).

Seems acceptable to me - just need to understand the code better when I or someone else gets a chance.

[probinson]

I was wondering if maybe I should restructure the DwarfDebug.cpp bit. Currently it's like

beginInstruction() {
  if (!MI->isDebugValue()) {
    if (DL != PrevInstLoc) {
      if (DL) {
        // case for a new, explicit location
      } else if (somewhat complicated condition) {
        // case for emitting line-0
      }
    } else if (DL) {
      if (DL.getLine() != LastAsmLine) {
        // case for restoring a previous line after emitting line-0
      }
    }
  }
} // end of function

and this could easily be redone as a sequence of much-less-indented cases:

beginInstruction() {
  if (MI->isDebugValue())
    return;
  if (DL == PrevInstLoc) {
    if (DL && DL.getLine() != LastAsmLine) {
      // case for restoring a previous line after emitting line-0
    }
    return;
  }
  // DL != PrevInstLoc
  if (DL) {
    // case for a new, explicit location
    return;
  }
  if (somewhat complicated condition) {
    // case for emitting line-0
  }
}

Would that help? The diff would be harder to read but the result might make more sense.

[probinson]

Refactor patch after r287686 (D26982). Also took this opportunity to try to clarify the commentary.
Hopefully it's all rather easier to follow now.

[dblaikie]

Looks good (you could reduce some indentation in nthe newly introduced blocks if you like by using "if (!cond) return; work; return; " rather than "if (cond) { work; }" but leave it up to you if it feels better or not.

lib/CodeGen/AsmPrinter/DwarfDebug.cpp

1041–1049

I would've expected this conditional to be:

if (UnknownLocations || (...))

(essentially UnknownLocations triggers this in all cases, otherwise we trigger it in the subset of cases you're trying to implement (at the beginning of BB's, etc))

I'm assuming recordSourceLine does the appropriate thing to avoid producing redundant entries (eg: calling it with 0 twice is a no-op) - so the reordering of the condition you've done here is a minor optimization (to avoid calling recordSourceLine(0..) when it was already called last anyway), not a functional change?

1046

Yeah - we have column info off by default (& it does make the line table significantly larger) if I recall correctly. But would be nice to have this improvement to this change at some point.

[probinson]

In D24180#604826, @dblaikie wrote:

Looks good (you could reduce some indentation in nthe newly introduced blocks if you like by using "if (!cond) return; work; return; " rather than "if (cond) { work; }" but leave it up to you if it feels better or not.

I did a little bit of that, it does help break out the cases better. Thanks!

lib/CodeGen/AsmPrinter/DwarfDebug.cpp

1041–1049

Actually no, recordSourceLine does not suppress duplicates. And because I don't set PrevInstLoc = DL; here anymore, I have to use LastAsmLine to determine whether I've already emitted a line-0 record.
But I think it does make sense to pull out

if (LastAsmLine == 0)
  return;

separately, it makes the commentary flow better and makes UnknownLocations etc condition easier to understand.

1046

Can do.

lib/CodeGen/AsmPrinter/DebugHandlerBase.h

protected:
 
   /// Target of debug info emission.
   AsmPrinter *Asm;
 
   /// Collected machine module information.
   MachineModuleInfo *MMI;
 
   /// Previous instruction's location information. This is used to
-  /// determine label location to indicate scope boundries in dwarf
-  /// debug info.
+  /// determine label location to indicate scope boundaries in debug info.
+  /// We track the previous instruction's source location (if not line 0),
+  /// whether it was a label, and its parent BB.
   DebugLoc PrevInstLoc;
   MCSymbol *PrevLabel = nullptr;
+  const MachineBasicBlock *PrevInstBB = nullptr;
 
   /// This location indicates end of function prologue and beginning of
   /// function body.
   DebugLoc PrologEndLoc;
 
   /// If nonnull, stores the current machine instruction we're processing.
   const MachineInstr *CurMI = nullptr;
 

lib/CodeGen/AsmPrinter/DebugHandlerBase.cpp

 
 void DebugHandlerBase::endInstruction() {
   if (!MMI->hasDebugInfo())
     return;
 
   assert(CurMI != nullptr);
   // Don't create a new label after DBG_VALUE instructions.
   // They don't generate code.
-  if (!CurMI->isDebugValue())
+  if (!CurMI->isDebugValue()) {
     PrevLabel = nullptr;
+    PrevInstBB = CurMI->getParent();
+  }
 
   DenseMap<const MachineInstr *, MCSymbol *>::iterator I =
       LabelsAfterInsn.find(CurMI);
   CurMI = nullptr;
 
   // No label needed.
   if (I == LabelsAfterInsn.end())
     return;

lib/CodeGen/AsmPrinter/DwarfDebug.cpp

 void DwarfDebug::beginInstruction(const MachineInstr *MI) {
   DebugHandlerBase::beginInstruction(MI);
   assert(CurMI);
 
   // Check if source location changes, but ignore DBG_VALUE locations.
   if (MI->isDebugValue())
     return;
   const DebugLoc &DL = MI->getDebugLoc();
-  if (DL == PrevInstLoc)
+  // When we emit a line-0 record, we don't update PrevInstLoc; so look at
+  // the last line number actually emitted, to see if it was line 0.
+  unsigned LastAsmLine =
+    Asm->OutStreamer->getContext().getCurrentDwarfLoc().getLine();
+
+  if (DL == PrevInstLoc) {
+    if (DL) {
+      // We have an explicit location, same as the previous location.
+      // But we might be coming back to it after a line 0 record.
+      if (LastAsmLine == 0 && DL.getLine() != 0) {
+        // Reinstate the source location but not marked as a statement.
+        const MDNode *Scope = DL.getScope();
+        recordSourceLine(DL.getLine(), DL.getCol(), Scope, /*Flags=*/0);
+      }
+    }
+    // Else we have an ongoing unspecified location, nothing to do here.
     return;
+  }
 
   if (!DL) {
     // We have an unspecified location, which might want to be line 0.
-    if (UnknownLocations) {
-      PrevInstLoc = DL;
-      recordSourceLine(0, 0, nullptr, 0);
+    // If we haven't already emitted a line-0 record, see if we have a reason
+    // to emit it now. Reasons to emit a line-0 record include:
+    // - User asked for it (UnknownLocations).
+    // - Instruction has a label, so it's referenced from somewhere else,
+    //   possibly debug information; we want it to have a source location.
+    // - Instruction is at the top of a block; we don't want to inherit the
+    //   location from the physically previous (maybe unrelated) block.
+    if (LastAsmLine != 0 &&
+        (UnknownLocations || PrevLabel ||
+         (PrevInstBB && PrevInstBB != MI->getParent()))) {
+      // Preserve the file number, if we can, to save space in the line table.
+      // Do not update PrevInstLoc, it remembers the last non-0 line.
+      // FIXME: Also preserve the column number, to save more space?
+      const MDNode *Scope = PrevInstLoc ? PrevInstLoc.getScope() : nullptr;
+      recordSourceLine(0, 0, Scope, 0);
     }
     return;
   }
 
-  // We have a new, explicit location.
+  // We have an explicit location, different from the previous location.
+  // Don't repeat a line-0 record, but otherwise emit the new location.
+  // (The new location might be an explicit line 0, which we do emit.)
+  if (DL.getLine() == 0 && LastAsmLine == 0)
+    return;
   unsigned Flags = 0;
-  PrevInstLoc = DL;
   if (DL == PrologEndLoc) {
     Flags |= DWARF2_FLAG_PROLOGUE_END | DWARF2_FLAG_IS_STMT;
     PrologEndLoc = DebugLoc();
   }
-  if (DL.getLine() !=
-      Asm->OutStreamer->getContext().getCurrentDwarfLoc().getLine())
+  // If the line changed, we call that a new statement; unless we went to
+  // line 0 and came back, in which case it is not a new statement.
+  unsigned OldLine = PrevInstLoc ? PrevInstLoc.getLine() : LastAsmLine;
+  if (DL.getLine() && DL.getLine() != OldLine)
     Flags |= DWARF2_FLAG_IS_STMT;
 
   const MDNode *Scope = DL.getScope();
   recordSourceLine(DL.getLine(), DL.getCol(), Scope, Flags);
+
+  // If we're not at line 0, remember this location.
+  if (DL.getLine())
+    PrevInstLoc = DL;
 }
 
 static DebugLoc findPrologueEndLoc(const MachineFunction *MF) {
   // First known non-DBG_VALUE and non-frame setup location marks
   // the beginning of the function body.
   for (const auto &MBB : *MF)
     for (const auto &MI : MBB)
       if (!MI.isDebugValue() && !MI.getFlag(MachineInstr::FrameSetup) &&

test/CodeGen/X86/stack-protector.ll

 define void @__stack_chk_fail() #1 !dbg !6 {
 entry:
   ret void
 }
 
 define void @test32() #1 !dbg !7 {
 entry:
 ; LINUX-I386-LABEL: test32:
-; LINUX-I386:       .loc 1 0 0 prologue_end
+; LINUX-I386:       .loc 1 4 2 prologue_end
+; LINUX-I386:       .loc 1 0 0
 ; LINUX-I386-NEXT:  calll __stack_chk_fail
 
 ; LINUX-X64-LABEL: test32:
-; LINUX-X64:       .loc 1 0 0 prologue_end
+; LINUX-X64:       .loc 1 4 2 prologue_end
+; LINUX-X64:       .loc 1 0 0
 ; LINUX-X64-NEXT:  callq __stack_chk_fail
 
 ; LINUX-KERNEL-X64-LABEL: test32:
-; LINUX-KERNEL-X64:       .loc 1 0 0 prologue_end
+; LINUX-KERNEL-X64:       .loc 1 4 2 prologue_end
+; LINUX-KERNEL-X64:       .loc 1 0 0
 ; LINUX-KERNEL-X64-NEXT:  callq __stack_chk_fail
 
 ; OPENBSD-AMD64-LABEL: test32:
-; OPENBSD-AMD64:       .loc 1 0 0 prologue_end
+; OPENBSD-AMD64:       .loc 1 4 2 prologue_end
+; OPENBSD-AMD64:       .loc 1 0 0
 ; OPENBSD-AMD64-NEXT:  movl
 ; OPENBSD-AMD64-NEXT:  callq __stack_smash_handler
   %0 = alloca [5 x i8], align 1
-  ret void
+  ret void, !dbg !9
 }
 
 declare double @testi_aux()
 declare i8* @strcpy(i8*, i8*)
 declare i32 @printf(i8*, ...)
 declare void @funcall(i32*)
 declare void @funcall2(i32**)
 declare void @funfloat(float*)

 !1 = !DIFile(filename: "test.c", directory: "/tmp")
 !2 = !{}
 !3 = !{i32 2, !"Dwarf Version", i32 4}
 !4 = !{i32 2, !"Debug Info Version", i32 3}
 !5 = !{!"clang version x.y.z"}
 !6 = distinct !DISubprogram(name: "__stack_chk_fail", scope: !1, type: !8, unit: !0)
 !7 = distinct !DISubprogram(name: "test32", scope: !1, type: !8, unit: !0)
 !8 = !DISubroutineType(types: !2)
+!9 = !DILocation(line: 4, column: 2, scope: !7)

test/DebugInfo/AArch64/line-header.ll

 ; RUN: llc -mtriple=aarch64-none-linux -O0 -filetype=obj - < %S/../Inputs/line.ll | llvm-dwarfdump - | FileCheck %s
 ; RUN: llc -mtriple=aarch64_be-none-linux -O0 -filetype=obj - < %S/../Inputs/line.ll | llvm-dwarfdump - | FileCheck %s
 
 ; check line table length is correctly calculated for both big and little endian
 CHECK-LABEL: .debug_line contents:
-CHECK: total_length: 0x0000003c
+CHECK: total_length: 0x0000003e

test/DebugInfo/X86/dwarf-no-source-loc.ll

+; Verify "no source location" directives appear in appropriate places.
+; RUN: llc %s -o - | FileCheck %s
+
+; Generated from this .cpp targeting linux using -g
+; and then removed function attributes as clutter.
+;
+; void bar(int *);
+; void baz(int *);
+; # 5 "no-source-loc.cpp"
+; void foo(int x) {
+;   int z;
+;   if (x)
+; # 20 "include.h"
+;     bar(&z);
+; # 10 "no-source-loc.cpp"
+;   baz(&z);
+; }
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: uwtable
+define void @_Z3fooi(i32 %x) !dbg !6 {
+entry:
+  %x.addr = alloca i32, align 4
+  %z = alloca i32, align 4
+  store i32 %x, i32* %x.addr, align 4
+  %0 = load i32, i32* %x.addr, align 4, !dbg !8
+  %tobool = icmp ne i32 %0, 0, !dbg !8
+  br i1 %tobool, label %if.then, label %if.end, !dbg !8
+
+if.then:                                          ; preds = %entry
+  call void @_Z3barPi(i32* %z), !dbg !9
+  br label %if.end, !dbg !9
+
+if.end:                                           ; preds = %if.then, %entry
+  call void @_Z3bazPi(i32* %z), !dbg !12
+  ret void, !dbg !14
+}
+
+; CHECK:      .loc 1 7 7
+; CHECK-NOT:  .loc
+; CHECK:      .loc 1 0 0 is_stmt 0
+; CHECK-NOT:  .loc
+; CHECK:      .loc 2 20 5 is_stmt 1
+; CHECK:      .LBB0_2:
+; CHECK-NEXT: .loc 2 0 0 is_stmt 0
+; CHECK-NOT:  .loc
+; CHECK:      .loc 1 10 3 is_stmt 1
+
+
+declare void @_Z3barPi(i32*)
+
+declare void @_Z3bazPi(i32*)
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4}
+!llvm.ident = !{!5}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1, producer: "clang version 4.0.0 (trunk 278782)", isOptimized: false, runtimeVersion: 0, emissionKind: LineTablesOnly, enums: !2)
+!1 = !DIFile(filename: "no-source-loc.cpp", directory: "/tests")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{!"clang version 4.0.0 (trunk 278782)"}
+!6 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 5, type: !7, isLocal: false, isDefinition: true, scopeLine: 5, flags: DIFlagPrototyped, isOptimized: false, unit: !0, variables: !2)
+!7 = !DISubroutineType(types: !2)
+!8 = !DILocation(line: 7, column: 7, scope: !6)
+!9 = !DILocation(line: 20, column: 5, scope: !10)
+!10 = !DILexicalBlockFile(scope: !6, file: !11, discriminator: 0)
+!11 = !DIFile(filename: "include.h", directory: "/tests")
+!12 = !DILocation(line: 10, column: 3, scope: !13)
+!13 = !DILexicalBlockFile(scope: !6, file: !1, discriminator: 0)
+!14 = !DILocation(line: 11, column: 1, scope: !13)