[DebugInfo] getMergedLocation: Maintain the line number if they match

[jmmartinez]

Summary

getMergedLocation returns a 'line 0' DILocaiton if the two locations
being merged don't perfecly match, even if they are in the same line but
a different column.

This commit adds support to keep the line number if it matches (but only
the column differs). The merged column number is the leftmost between the
two.

For comparison,

• the GCC output: https://godbolt.org/z/4Mqxfa983
• the Clang output: https://godbolt.org/z/zWaT14Yqr

Notice that gcc seems to use the location of "a" in both cases, while Clang return a line 0 location even if both locations are on the same line.

Should Clang give the correct line number but with column 0? or the left-most? or the line 0 location is in fact more accurate? And should it use the inlined-at scope+line+column in the case it matches?

I have yet to read the source-code of gcc to understand exactly how it works.

Any advice on the subject is welcomed.

[jmmartinez]

Remove from drafts

[dblaikie]

Could we use zero column instead of the leftmost - less chance of misleading someone, perhaps?

[dblaikie]

I'm cautious about adding a one-off iterator abstraction as is done here - meeting iterator requirements is non-trivial (eg: returning values from op* is questionable - since then to the iterator requirements you also need op-> which can't return by value... ). So might be best sticking with the existing code style of an explicit loop.

[jmmartinez]

• Remove iterators
• Use column 0 instead of leftmost-column

[jmmartinez]

llvm/lib/IR/DebugInfoMetadata.cpp

156

Style: Remove the brackets

[dblaikie]

llvm/lib/IR/DebugInfoMetadata.cpp

165

Could you walk me through why the line/col get set to zero at this point? I'd maybe have thought they should get set to the line/col of the InlinedAt location?

[jmmartinez]

• Keep the line and column number from the inlined at instead of setting it to 0

[jmmartinez]

llvm/lib/IR/DebugInfoMetadata.cpp

165

It was my mistake. Your comment made me have second thoughts about that change.

I added some extra unit-tests for the cases where the InlinedAt line/column is used.

[dblaikie]

Looks pretty reasonable to me.

Got a rough sense of how this changes debug info size (especially .debug_line growth) - maybe on a clang self-host?

[Orlando]

Hi, sorry, I have been meaning to comment here but it's taken me a while to get to.

Use column 0 instead of leftmost-column

+1 I think this is the right move (please update the patch description / comment before you commit).

"line 0" has a special meaning - that the instruction can't be attributed a single line number (e.g. because the instruction represents some merged instruction). I don't think that is actually mentioned anywhere in the DWARF spec but is more of a convention between DWARF emitters and consumers. Does column 0 convey the same meaning I wonder? I guess if your debugger uses column info and points at the start of the line (column 0) then that is an intuitive indication that column number isn't known, even if it's not explicit.

I think this kind of change might be worth documenting somewhere (release notes? I'm not sure how they work), given that it could reasonably affect DWARF consuming tools, @dblaikie wdyt?

[jmmartinez]

In D135166#3846325, @Orlando wrote:

"line 0" has a special meaning - that the instruction can't be attributed a single line number (e.g. because the instruction represents some merged instruction). I don't think that is actually mentioned anywhere in the DWARF spec but is more of a convention between DWARF emitters and consumers. Does column 0 convey the same meaning I wonder? I guess if your debugger uses column info and points at the start of the line (column 0) then that is an intuitive indication that column number isn't known, even if it's not explicit.

As far as I understand it's in the DWARF standard (in section 6.2.2 https://dwarfstd.org/doc/DWARF5.pdf ):

• line: An unsigned integer indicating a source line number. Lines are numbered beginning at 1. The compiler may emit the value 0 in cases where an instruction cannot be attributed to any source line.
• column: An unsigned integer indicating a column number within a source line. Columns are numbered beginning at 1. The value 0 is reserved to indicate that a statement begins at the “left edge” of the line.

The behaviour for the column is slightly different for declarations (in section 2.14): The value of the DW_AT_decl_column attribute represents the source column number at which the first character of the identifier of the declared object appears. The value 0 indicates that no column has been specified.

[Orlando]

In D135166#3846516, @jmmartinez wrote:

In D135166#3846325, @Orlando wrote:

"line 0" has a special meaning - that the instruction can't be attributed a single line number (e.g. because the instruction represents some merged instruction). I don't think that is actually mentioned anywhere in the DWARF spec but is more of a convention between DWARF emitters and consumers. Does column 0 convey the same meaning I wonder? I guess if your debugger uses column info and points at the start of the line (column 0) then that is an intuitive indication that column number isn't known, even if it's not explicit.

As far as I understand it's in the DWARF standard (in section 6.2.2 https://dwarfstd.org/doc/DWARF5.pdf ):

• line: An unsigned integer indicating a source line number. Lines are numbered beginning at 1. The compiler may emit the value 0 in cases where an instruction cannot be attributed to any source line.
• column: An unsigned integer indicating a column number within a source line. Columns are numbered beginning at 1. The value 0 is reserved to indicate that a statement begins at the “left edge” of the line.

The behaviour for the column is slightly different for declarations (in section 2.14): The value of the DW_AT_decl_column attribute represents the source column number at which the first character of the identifier of the declared object appears. The value 0 indicates that no column has been specified.

Oh, my mistake, thanks for finding that. In which case this change does seem to slightly bend the spec. IIUC, with your patch the compiler is trying to convey "the line is known but the column is unspecifiable", and DWARF doesn't give us a way to express that. Using column 0 does sound like a reasonable work-around to me (and looks like it should improve developer experience) but I think it's worth getting an opinion from someone who works on a DWARF-consumer. I've asked our (Sony's) debugger people what they think.

Perhaps we should seek input from an LLDB developer too (cc @JDevlieghere).

[jmmartinez]

In D135166#3843796, @dblaikie wrote:

Got a rough sense of how this changes debug info size (especially .debug_line growth) - maybe on a clang self-host?

I just finished mesuring this. I compiled in Release+-gline-tables-only and RelWithDebInfo. In both cases the size difference in clang's binary was pretty small (less than 100 bytes).

[dblaikie]

I'm generally OK with this.

Might be worth getting some feedback from folks - but I think it's probably fairly harmless (lots of code is built without column info anyway, so tools are likely fine with it) & things can be addressed in post-commit review. But also doesn't seem like it'd need to be rushed in either - so waiting for some Sony/Apple feedback for a bit seems fine - either way.

[jmmartinez]

@JDevlieghere Sorry to ping again, but would it be possible to get some input on this patch? I'm not sure about what could be the implications that this could have on LLDB's side.

[Orlando]

Hi, sorry for the delay following up on this.

I just wanted to mention that it turns out that SCE debugger tuning (-gsce) supresses column info by default and that our debugger ignores it. So no objections from me on that front.

I've left some inline nits, and I think it would be a good idea to update the function's comment in llvm/IR/DebugInfoMetadata.h too. Otherwise, I'm happy, thanks!

llvm/lib/IR/DebugInfoMetadata.cpp

166

If I'm reading this right, AdvanceToParentLoc walks the entire scope chain from the source location up to file scope. Then walks the entire scope chain of the inlined-at location of the original source location up to file scope. Then, the entire scope chain of the inline-at location of that one, and so on.

Is that right? I think it could be useful to add a comment explaining the traversal.

170

IMO it would be useful to add a comment here. Something along the lines of "Traverse the scope tree of LocB looking for the innermost match with LocB" maybe?

173

nit

[jmmartinez]

• Added comments

[jmmartinez]

llvm/lib/IR/DebugInfoMetadata.cpp

166

Exactly. I added a comment to explain the traversal. Thanks!

[Orlando]

There are a few outstanding review comments to be addressed:

1. I think it would be a good idea to update the function's comment in llvm/IR/DebugInfoMetadata.h.
2. The comments should end with a full stops (more info).
3. Your comment Style: Remove the brackets.

Feel free to address those before pushing (i.e. IMO no need for another round of review).

LGTM with those changes.

llvm/lib/IR/DebugInfoMetadata.cpp

168

nit: full stop.

171

nit: full stop.

175

nit: full stop.

186

nit: full stop.

llvm/unittests/IR/MetadataTest.cpp

1035

nit: full stop.

1065

nit: full stop.

llvm/lib/IR/DebugInfoMetadata.cpp

DILocation::getMergedLocations(ArrayRef<const DILocation *> Locs) {
   for (const DILocation *L : llvm::drop_begin(Locs)) {
     Merged = getMergedLocation(Merged, L);
     if (Merged == nullptr)
       break;
   }
   return Merged;
 }
 
+static auto TraverseDILocation(DILocation const *DL) {
+  class Range {
+    DILocation const *DL;
+
+  public:
+    class Iterator {
+      DIScope *S;
+      DILocation *L;
+      unsigned Line;
+      unsigned Col;
+
+    public:
+      Iterator(DILocation const *DL)
+          : S(DL->getScope()), L(DL->getInlinedAt()), Line(DL->getLine()),
+            Col(DL->getColumn()) {}
+
+      std::pair<std::pair<DIScope *, DILocation *>,
+                std::pair<unsigned, unsigned>>
+      operator*() const {
+        return std::make_pair(std::make_pair(S, L), std::make_pair(Line, Col));
+      }
+
+      struct EndSentinel {};
+      bool operator!=(EndSentinel) const {
+        // This only checks if 'this' reached the end. Ignore the other
+        // iterator.
+        return S != nullptr;
+      }
+
+      Iterator &operator++() {
+        S = S->getScope();
+        if (!S && L) {
+          Line = Col = 0;
+          S = L->getScope();
+          L = L->getInlinedAt();
+        }
+        return *this;
+      }
+    };
+
+    Range(DILocation const *DL) : DL(DL) {}
+    Iterator begin() const { return DL; }
+    Iterator::EndSentinel end() const { return {}; }
+  };
+
+  return Range(DL);
+}
+
 const DILocation *DILocation::getMergedLocation(const DILocation *LocA,
                                                 const DILocation *LocB) {
   if (!LocA || !LocB)
     return nullptr;
 
-  if (LocA == LocB)
+  if (LocA == LocB) {
     return LocA;
+  }
 
-  SmallSet<std::pair<DIScope *, DILocation *>, 5> Locations;
-  DIScope *S = LocA->getScope();
-  DILocation *L = LocA->getInlinedAt();
-  while (S) {
-    Locations.insert(std::make_pair(S, L));
-    S = S->getScope();
-    if (!S && L) {
-      S = L->getScope();
-      L = L->getInlinedAt();
+  LLVMContext &C = LocA->getContext();
+  SmallDenseMap<std::pair<DIScope *, DILocation *>,
+                std::pair<unsigned, unsigned>, 4>
+      Locations;
+  for (auto Loc : TraverseDILocation(LocA))
+    Locations.insert(Loc);
+
+  for (auto Loc : TraverseDILocation(LocB)) {
+    auto MatchLoc = Locations.find(Loc.first);
+    if (MatchLoc == Locations.end()) {
+      continue;
     }
+
+    if (!isa<DILocalScope>(Loc.first.first)) {
+      return DILocation::get(C, 0, 0, LocA->getScope(), Loc.first.second);
     }
-  S = LocB->getScope();
-  L = LocB->getInlinedAt();
-  while (S) {
-    if (Locations.count(std::make_pair(S, L)))
-      break;
-    S = S->getScope();
-    if (!S && L) {
-      S = L->getScope();
-      L = L->getInlinedAt();
+
+    unsigned Line = 0;
+    unsigned Col = 0;
+    // if the lines match, pick the leftmost column
+    if (MatchLoc->second.first == Loc.second.first) {
+      Line = Loc.second.first;
+      Col = std::min(Loc.second.second, MatchLoc->second.second);
     }
+    return DILocation::get(C, Line, Col, Loc.first.first, Loc.first.second);
   }
 
-  // If the two locations are irreconsilable, just pick one. This is misleading,
-  // but on the other hand, it's a "line 0" location.
-  if (!S || !isa<DILocalScope>(S))
-    S = LocA->getScope();
-  return DILocation::get(LocA->getContext(), 0, 0, S, L);
+  // If the two locations are irreconsilable, pick any scope.
+  // and return a "line 0" location
+  return DILocation::get(C, 0, 0, LocA->getScope());
 }
 
 Optional<unsigned> DILocation::encodeDiscriminator(unsigned BD, unsigned DF,
                                                    unsigned CI) {
   std::array<unsigned, 3> Components = {BD, DF, CI};
   uint64_t RemainingWork = 0U;
   // We use RemainingWork to figure out if we have no remaining components to
   // encode. For example: if BD != 0 but DF == 0 && CI == 0, we don't need to

llvm/test/DebugInfo/return-same-line-merge.ll

+; RUN: opt -simplifycfg -S < %s | FileCheck %s
+;
+; Simplified from the following code:
+; int foo() {
+;   if(c) { return a; } else { return b; }
+; }
+define i32 @foo(i32 %c, i32 %a, i32 %b) !dbg !4 {
+; CHECK: define i32 @foo({{.*}}) !dbg [[FOO_SUBPROGRAM:![0-9]+]]
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i32 [[C:%.*]], 0, !dbg [[DBG_CMP:![0-9]+]]
+; CHECK-NEXT:    [[A_B:%.*]] = select i1 [[TOBOOL]], i32 [[A:%.*]], i32 [[B:%.*]]
+; CHECK-NEXT:    ret i32 [[A_B]], !dbg [[DBG_RET:![0-9]+]]
+; CHECK: [[DBG_CMP]] = !DILocation(line: 2, column: 1, scope: [[FOO_SUBPROGRAM]])
+; CHECK: [[DBG_RET]] = !DILocation(line: 4, column: 1, scope: [[FOO_SUBPROGRAM]])
+entry:
+  %tobool = icmp ne i32 %c, 0, !dbg !7
+  br i1 %tobool, label %cond.true, label %cond.false, !dbg !8
+
+cond.true:                                        ; preds = %entry
+  ret i32 %a, !dbg !9
+
+cond.false:                                       ; preds = %entry
+  ret i32 %b, !dbg !10
+}
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!2, !3}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 16.0.0)", isOptimized: false, runtimeVersion: 0, emissionKind: LineTablesOnly, splitDebugInlining: false, nameTableKind: None)
+!1 = !DIFile(filename: "test.c", directory: "/")
+!2 = !{i32 7, !"Dwarf Version", i32 5}
+!3 = !{i32 2, !"Debug Info Version", i32 3}
+!4 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 1, type: !5, scopeLine: 1, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !6)
+!5 = !DISubroutineType(types: !6)
+!6 = !{}
+!7 = !DILocation(line: 2, column: 1, scope: !4)
+!8 = !DILocation(line: 3, column: 1, scope: !4)
+!9 = !DILocation(line: 4, column: 1, scope: !4)
+!10 = !DILocation(line: 4, column: 2, scope: !4)

llvm/unittests/IR/MetadataTest.cpp

DIScope *S = DILexicalBlock::get(Context, N, getFile(), 3, 4);
     EXPECT_EQ(N, M->getScope());
   }
 
   {
     // Identical, different scopes.
     auto *A = DILocation::get(Context, 2, 7, N);
     auto *B = DILocation::get(Context, 2, 7, S);
     auto *M = DILocation::getMergedLocation(A, B);
-    EXPECT_EQ(0u, M->getLine()); // FIXME: Should this be 2?
-    EXPECT_EQ(0u, M->getColumn()); // FIXME: Should this be 7?
+    EXPECT_EQ(2u, M->getLine());
+    EXPECT_EQ(7u, M->getColumn());
+    EXPECT_EQ(N, M->getScope());
+  }
+
+  {
+    // Same line, different column.
+    auto *A = DILocation::get(Context, 2, 7, N);
+    auto *B = DILocation::get(Context, 2, 10, S);
+    auto *M0 = DILocation::getMergedLocation(A, B);
+    auto *M1 = DILocation::getMergedLocation(B, A);
+    for (auto *M : {M0, M1}) {
+      EXPECT_EQ(2u, M->getLine());
+      EXPECT_EQ(7u, M->getColumn());
       EXPECT_EQ(N, M->getScope());
     }
+  }
 
   {
     // Different lines, same scopes.
     auto *A = DILocation::get(Context, 1, 6, N);
     auto *B = DILocation::get(Context, 2, 7, N);
     auto *M = DILocation::getMergedLocation(A, B);
     EXPECT_EQ(0u, M->getLine());
     EXPECT_EQ(0u, M->getColumn());
DIScope *S = DILexicalBlock::get(Context, N, getFile(), 3, 4);
     auto *B = DILocation::get(Context, 2, 7, SP2, I);
     auto *M = DILocation::getMergedLocation(A, B);
     EXPECT_EQ(0u, M->getLine());
     EXPECT_EQ(0u, M->getColumn());
     EXPECT_TRUE(isa<DILocalScope>(M->getScope()));
     EXPECT_EQ(I, M->getInlinedAt());
   }
 
-   {
     // Completely different.
     auto *I = DILocation::get(Context, 2, 7, N);
     auto *A = DILocation::get(Context, 1, 6, S, I);
     auto *B = DILocation::get(Context, 2, 7, getSubprogram());
     auto *M = DILocation::getMergedLocation(A, B);
     EXPECT_EQ(0u, M->getLine());
     EXPECT_EQ(0u, M->getColumn());
     EXPECT_TRUE(isa<DILocalScope>(M->getScope()));
     EXPECT_EQ(S, M->getScope());
     EXPECT_EQ(nullptr, M->getInlinedAt());
   }
+
+  // Two locations, same line/column different file, inlined at the same place
+  {
+    auto *FA = getFile();
+    auto *FB = getFile();
+    auto *FI = getFile();
+
+    auto *SPA = DISubprogram::getDistinct(Context, FA, "a", "a", FA, 0, nullptr,
+                                          0, nullptr, 0, 0, DINode::FlagZero,
+                                          DISubprogram::SPFlagZero, nullptr);
+
+    auto *SPB = DISubprogram::getDistinct(Context, FB, "b", "b", FB, 0, nullptr,
+                                          0, nullptr, 0, 0, DINode::FlagZero,
+                                          DISubprogram::SPFlagZero, nullptr);
+
+    auto *SPI = DISubprogram::getDistinct(Context, FI, "i", "i", FI, 0, nullptr,
+                                          0, nullptr, 0, 0, DINode::FlagZero,
+                                          DISubprogram::SPFlagZero, nullptr);
+
+    auto *I = DILocation::get(Context, 2, 7, SPI);
+    auto *A = DILocation::get(Context, 2, 7, SPA, I);
+    auto *B = DILocation::get(Context, 2, 7, SPB, I);
+    auto *M = DILocation::getMergedLocation(A, B);
+    EXPECT_EQ(0u, M->getLine());
+    EXPECT_EQ(0u, M->getColumn());
+    EXPECT_TRUE(isa<DILocalScope>(M->getScope()));
+    EXPECT_EQ(SPI, M->getScope());
+    EXPECT_EQ(nullptr, M->getInlinedAt());
+  }
 }
 
 TEST_F(DILocationTest, getDistinct) {
   MDNode *N = getSubprogram();
   DILocation *L0 = DILocation::getDistinct(Context, 2, 7, N);
   EXPECT_TRUE(L0->isDistinct());
   DILocation *L1 = DILocation::get(Context, 2, 7, N);
   EXPECT_FALSE(L1->isDistinct());
   EXPECT_EQ(L1, DILocation::get(Context, 2, 7, N));
 }