[DWARF] Fix a bug in line info handling

[loladiro]

Summary

This fixes a bug in the line info handling in the dwarf code, based on a
problem I when implementing RelocVisitor support for MachO.
Since addr+size will give the first address past the end of the function,
we need to back up one line table entry. Fix this by looking up the end_addr-1,
which is the last address in the range. Also factor out the common functionality
into a separate function.
This comes up on MachO much more than on ELF, since MachO
doesn't store the symbol size separately, hence making
said situation always occur.

[dblaikie]

+Alexey

[samsonov]

lib/DebugInfo/DWARF/DWARFDebugLine.cpp

608

I don't understand this part. Looks like row_pos should be the first row that contains "address". It means that the lookup here should be similar to the one done in lookupAddress function (of course, I'd prefer this code to be shared).

628

Can you simply find the number of row that describes the address "end_addr - 1"?

[loladiro]

Yes, I tried, just using address - 1 for the second patch and it passes the testcase, so I'm happy. I don't know enough about this code to decide which is better, so just let me know and I'll update the code accordingly.

[samsonov]

Personally, I would prefer to have a single function that would take an address, and a Sequence, describing this address, and return a row in that sequence, describing this address. Then we can use this function in several places (lookupAddress, lookupAddressRange).

[loladiro]

Updated to factor out common code into a separate function.

[samsonov]

lib/DebugInfo/DWARF/DWARFDebugLine.cpp

525

consider moving this constant to LineTable struct in the header (and rename to smth. like UnknownRowIndex)

571

Looks like this condition should be checked in findRowInSequence function above.

603

I'd rather not provide default value for variables, if we're unconditionally initializing them later.

608

Just a ternary operator?

uint32_t first_row_index = (seq_pos == start_pos) ? findRowInSeq(cur_seq, address) : cur_seq.FirstRowIndex;

614

Fun fact: if you add the call to Sequence::containsPC() at the beginning of findRowInSequence, as suggested above, you won't need this special case:

uint32_t last_row_index = findRowInSequnce(cur_seq, end_addr - 1);
if (last_row_index == UnknownRowIndex)
  last_row_index = cur_seq.LastRowIndex - 1;

621

assert that both first_row_index and last_row_index are valid? Or return false in this case.

[loladiro]

lib/DebugInfo/DWARF/DWARFDebugLine.cpp

525

Will do.

571

Sure, it wasn't there before below, so I didn't pull it, but seems reasonable.

603

We're not, this also handles the case when seq_pos == start_pos is false.

608

But that wouldn't capture the case where findRowInSeq returns an UnknownRowIndex.

614

Sounds good.

[loladiro]

Updated again. I also noticed that we were duplicating the last row before (the end_sequence one, which is not in general valid - I believe), so I fixed the test as well - please make sure that seems correct.

[samsonov]

I don't know about the data needed for llvm-rtdyld, so can't comment about the changes to test/DebugInfo/debuglineinfo.test. Otherwise, the patch now looks fine to me (modulo comments below).

include/llvm/DebugInfo/DWARF/DWARFDebugLine.h

208

Fix a comment about lookupAddress return value to mention this. Also, lookupAddress should probably be private, the public interface is getFileLineInfoForAddress. Looks like LineTable is now a class, not a struct.

lib/DebugInfo/DWARF/DWARFDebugLine.cpp

538

Run patch through clang-format

601

Hm, should this be a const reference instead?

[samsonov]

Thank you!

[loladiro]

llvm-rtdyld just uses getLineInfoForAddressRange and dumps that out, so the change in the test case directly corresponds to a change in the return value of that function. However, I do believe that this is correct now, because the extra line was marked with end_sequence, which the DWARF standard says is A boolean indicating that the current address is that of the first byte after the end of a sequence, so I believe it shouldn't be included if you're asking for just the rows that cover the function. Will do the stylistic changes you note.

[loladiro]

Run everything through clang-format, also change cur_seq to a const reference as suggested. I didn't adjust the visibility of LineTable, as that seems to be a separate commit, preferably done by somebody who knows which part of the interface should be public.

[loladiro]

Note that this is currently uncommitable, because llvm-rtdyld can no longer figure out the size of MachO symbols due to rL238028. Maybe @rafael can help fix llvm-rtdyld.

include/llvm/DebugInfo/DWARF/DWARFDebugLine.h

       return LHS.Address < RHS.Address;
     }
 
+    static bool orderByAddressLeq(const Row& LHS, const Row& RHS) {
+      return LHS.Address <= RHS.Address;
+    }
+
     // The program-counter value corresponding to a machine instruction
     // generated by the compiler.
     uint64_t Address;

lib/DebugInfo/DWARF/DWARFDebugLine.cpp

       RowIter first_row = Rows.begin() + cur_seq.FirstRowIndex;
       RowIter last_row = Rows.begin() + cur_seq.LastRowIndex;
       RowIter row_pos = std::upper_bound(first_row, last_row, row,
-                                         DWARFDebugLine::Row::orderByAddress);
+                                         DWARFDebugLine::Row::orderByAddressLeq);
       // The 'row_pos' iterator references the first row that is greater than
-      // our start address. Unless that's the first row, we want to start at
-      // the row before that.
+      // our or equal to start address.
       first_row_index = cur_seq.FirstRowIndex + (row_pos - first_row);
-      if (row_pos != first_row)
-        --first_row_index;
     } else
       first_row_index = cur_seq.FirstRowIndex;
 

       RowIter first_row = Rows.begin() + cur_seq.FirstRowIndex;
       RowIter last_row = Rows.begin() + cur_seq.LastRowIndex;
       RowIter row_pos = std::upper_bound(first_row, last_row, row,
-                                         DWARFDebugLine::Row::orderByAddress);
+                                         DWARFDebugLine::Row::orderByAddressLeq);
       // The 'row_pos' iterator references the first row that is greater than
-      // our end address.  The row before that is the last row we want.
+      // or equal our end address. The row before that is the last row we want,
+      // since end_address is the first address past the end of the range we're
+      // looking up.
       last_row_index = cur_seq.FirstRowIndex + (row_pos - first_row) - 1;
     } else
       // Contrary to what you might expect, DWARFDebugLine::SequenceLastRowIndex

test/DebugInfo/debuglineinfo-macho.test

 RUN: llvm-dwarfdump %p/Inputs/test-multiple-macho.o | FileCheck %s
 
 CHECK-NOT: error: failed to compute relocation: X86_64_RELOC_UNSIGNED
+
+# Check that relocations get applied correctly
+RUN: llvm-rtdyld -printobjline %p/Inputs/test-simple-macho.o \
+RUN:   | FileCheck %s -check-prefix TEST_SIMPLE
+RUN: llvm-rtdyld -printline %p/Inputs/test-simple-macho.o \
+RUN:   | FileCheck %s -check-prefix TEST_SIMPLE
+RUN: llvm-rtdyld -printobjline %p/Inputs/test-multiple-macho.o \
+RUN:   | FileCheck %s -check-prefix TEST_MULTIPLE
+RUN: llvm-rtdyld -printline %p/Inputs/test-multiple-macho.o \
+RUN:   | FileCheck %s -check-prefix TEST_MULTIPLE
+
+TEST_SIMPLE:      Function: _foo, Size = 11
+TEST_SIMPLE-NEXT:  Line info @ 0: simple.c, line:1
+TEST_SIMPLE-NEXT:  Line info @ 7: simple.c, line:2
+TEST_SIMPLE-NEXT:  Line info @ 11: simple.c, line:2
+
+TEST_MULTIPLE:      Function: _bar, Size = 48
+TEST_MULTIPLE-NEXT:   Line info @ 0: multiple.c, line:5
+TEST_MULTIPLE-NEXT:   Line info @ 7: multiple.c, line:6
+TEST_MULTIPLE-NEXT:   Line info @ 16: multiple.c, line:9
+TEST_MULTIPLE-NEXT:   Line info @ 21: multiple.c, line:9
+TEST_MULTIPLE-NEXT:   Line info @ 26: multiple.c, line:7
+TEST_MULTIPLE-NEXT:   Line info @ 33: multiple.c, line:10
+TEST_MULTIPLE-NOT:    Line info @ 48: multiple.c, line:12
+TEST_MULTIPLE-NEXT: Function: _foo, Size = 16
+TEST_MULTIPLE-NEXT:   Line info @ 0: multiple.c, line:1
+TEST_MULTIPLE-NEXT:   Line info @ 7: multiple.c, line:2
+TEST_MULTIPLE-NOT:    Line info @ 16: multiple.c, line:5
+TEST_MULTIPLE-NEXT: Function: _fubar, Size = 46
+TEST_MULTIPLE-NEXT:   Line info @ 0: multiple.c, line:12
+TEST_MULTIPLE-NEXT:   Line info @ 7: multiple.c, line:13
+TEST_MULTIPLE-NEXT:   Line info @ 12: multiple.c, line:17
+TEST_MULTIPLE-NEXT:   Line info @ 25: multiple.c, line:15
+TEST_MULTIPLE-NEXT:   Line info @ 34: multiple.c, line:19
+TEST_MULTIPLE-NEXT:   Line info @ 41: multiple.c, line:21
+TEST_MULTIPLE-NEXT:   Line info @ 46: multiple.c, line:21