Improve disassembly of branch targets in non-relocatable objects

[jhenderson]

Summary

llvm-objdump currently tries to pick symbols for branch targets based on the nearest section. However, if there are multiple sections with the same address, it only looks in one of them for the symbols before falling back to using absolute symbols. We should at least look in all sections with the same address for the candidate symbol (but see also https://bugs.llvm.org/show_bug.cgi?id=45627). This change does that, meaning that in some cases we now print a branch target when we didn't before. When there are multiple competing sections, we prefer symbols in the non-empty one over those in empty sections, as the former are more likely to be the "correct" one.

At some point, we should try to fix https://bugs.llvm.org/show_bug.cgi?id=45627 properly, but that might have performance implications with only minor gains, so for now, I'm just improving the situation.

[grimar]

llvm/test/tools/llvm-objdump/X86/disassemble-same-section-addr.test

63

SHN_ABS?

Also a suggestion: what about making it:

Index: [[INDEX]]

And then stop using # RUN: llvm-objcopy -N absolute %t5 %t6 to remove it,
but also add a test for something else, like SHN_COMMON or SHN_LOPROC etc?

77

Could you expand "too high"?

97

##

llvm/tools/llvm-objdump/llvm-objdump.cpp

1257

Perhaps I'd rewrite this body slightly.
Often sort comparators check one field at once, it is easier to read and mantain them:

if (LHS.first != RHS.first)
  return LHS.first < RHS.first;
return LHS.second.getSize() < RHS.second.getSize();

1560

Perhaps just It? (consistent with the code above + I guess might look nicer after clang format).

1569

Missing a space after if. Perhaps 'if (TargetSym)' would be more consistent with the code in this file.

[jhenderson]

Addressed review comments:

• clang-formatted
• improved comments and variable names
• slight tweak to lambda
• used SHN_ABS and provided it via yaml2obj to allow removal of llvm-objcopy run in test.

llvm/tools/llvm-objdump/llvm-objdump.cpp

1569

Thanks. Somehow I forgot to clang-format.

[grimar]

LGTM. Lets see what other reviewers think.

[Higuoxing]

LGTM with one minor suggestion :)

llvm/test/tools/llvm-objdump/X86/disassemble-same-section-addr.test

24

# RUN: yaml2obj ... -o %5 ...
#                      ^ Should be '%6', right?

[jhenderson]

llvm/test/tools/llvm-objdump/X86/disassemble-same-section-addr.test

24

Oops, good spot. That actually is a test bug. The %t6 was left lying around on my machine due to the previous runs using llvm-objcopy. When I fixed %t5 to %t6 here, the test started failing as apparently llvm-objdump treats all symbols without a section (including those with a section index of SHN_LOPROC) as absolute symbols.

I think therefore the only way to do this test is to revert back to my original version using llvm-objcopy (or create an entirely new input).

[jhenderson]

Reinstate llvm-objcopy usage to check behaviour of no symbol being found. Also add case for SHN_LOPROC being counted as an absolute symbol.

[jhenderson]

@grimar or @Higuoxing, could I get another review please?

[grimar]

LGTM

llvm/test/tools/llvm-objdump/X86/disassemble-same-section-addr.test

 ## This test shows that llvm-objdump can handle sections with the same address
 ## when symbols in those sections are referenced. In the past, the section
 ## picked was non-deterministic, resulting in different symbols being found for
 ## the section. The test uses YAML for the input, as we need a fully linked ELF
 ## to reproduce the original failure.
 
-# RUN: yaml2obj %s -o %t1 -D SECTION=.second
-# RUN: llvm-objdump -d %t1 | FileCheck %s
-# RUN: yaml2obj %s -o %t2 -D SECTION=.first
-## FIXME: this case should print "<target>" too.
-# RUN: llvm-objdump -d %t2 | FileCheck %s --check-prefix=FAIL
+## Two empty sections, one with symbol in, one without.
+# RUN: yaml2obj %s --docnum=1 -o %t1 -D SIZE1=0 -D SIZE2=0 -D SECTION=.second -D INDEX=SHN_ABS
+# RUN: llvm-objdump -d %t1 | FileCheck %s --check-prefix=TARGET
+# RUN: yaml2obj %s --docnum=1 -o %t2 -D SIZE1=0 -D SIZE2=0 -D SECTION=.first -D INDEX=SHN_ABS
+# RUN: llvm-objdump -d %t2 | FileCheck %s --check-prefix=TARGET
 
-# CHECK: callq 0x5 <target>
-# FAIL:  callq 0x5{{$}}
+## Two sections, one empty with symbol, other non-empty, without symbol.
+# RUN: yaml2obj %s --docnum=1 -o %t3 -D SIZE1=1 -D SIZE2=0 -D SECTION=.second -D INDEX=SHN_ABS
+# RUN: llvm-objdump -d %t3 | FileCheck %s --check-prefix=TARGET
+# RUN: yaml2obj %s --docnum=1 -o %t4 -D SIZE1=0 -D SIZE2=1 -D SECTION=.first -D INDEX=SHN_ABS
+# RUN: llvm-objdump -d %t4 | FileCheck %s --check-prefix=TARGET
+
+## Fall back to absolute symbol if no symbol found in candidate sections.
+# RUN: yaml2obj %s --docnum=1 -o %t5 -D SIZE1=1 -D SIZE2=0 -D SECTION=.caller -D INDEX=SHN_ABS
+# RUN: llvm-objdump -d %t5 | FileCheck %s --check-prefix=ABSOLUTE
+
+## Show that other symbols with reserved st_shndx values are treated as absolute
+## symbols.
+# RUN: yaml2obj %s --docnum=1 -o %t6 -D SIZE1=1 -D SIZE2=0 -D SECTION=.caller -D INDEX=SHN_LOPROC
+# RUN: llvm-objdump -d %t6 | FileCheck %s --check-prefix=ABSOLUTE
+
+## Print no target if no symbol in section/absolute symbol found.
+# RUN: llvm-objcopy %t5 %t7 -N other
+# RUN: llvm-objdump -d %t7 | FileCheck %s --check-prefix=FAIL
+
+# TARGET:   callq 0x5 <target>
+# ABSOLUTE: callq 0x5 <other+0x5>
+# FAIL:     callq 0x5{{$}}
 
 --- !ELF
 FileHeader:
   Class:   ELFCLASS64
   Data:    ELFDATA2LSB
   Type:    ET_EXEC
   Machine: EM_X86_64
 Sections:
   - Name:    .caller
     Type:    SHT_PROGBITS
     Flags:   [SHF_ALLOC, SHF_EXECINSTR]
     Address: 0x0
-    Content: e800000000 # Call instruction to next address.
+    Content: e800000000 ## Call instruction to next address.
   - Name:    .first
     Type:    SHT_PROGBITS
     Flags:   [SHF_ALLOC, SHF_EXECINSTR]
     Address: 0x5
+    Size:    [[SIZE1]]
   - Name:    .second
     Type:    SHT_PROGBITS
     Flags:   [SHF_ALLOC, SHF_EXECINSTR]
     Address: 0x5
+    Size:    [[SIZE2]]
 Symbols:
   - Name:    target
     Section: [[SECTION]]
     Value:   0x5
+  - Name:    other
+    Index:   [[INDEX]]
+    Value:   0x0
+
+## Two empty sections, both with symbols.
+# RUN: yaml2obj %s --docnum=2 -o %t7 -D SIZE1=0 -D SIZE2=0 -D SYMVAL1=0x5 -D SYMVAL2=0x5
+# RUN: llvm-objdump -d %t7 | FileCheck %s --check-prefix=SECOND
+
+## Two sections, both with symbols, one empty, the other not.
+# RUN: yaml2obj %s --docnum=2 -o %t8 -D SIZE1=1 -D SIZE2=0 -D SYMVAL1=0x5 -D SYMVAL2=0x5
+# RUN: llvm-objdump -d %t8 | FileCheck %s --check-prefix=FIRST
+# RUN: yaml2obj %s --docnum=2 -o %t9 -D SIZE1=0 -D SIZE2=1 -D SYMVAL1=0x5 -D SYMVAL2=0x5
+# RUN: llvm-objdump -d %t9 | FileCheck %s --check-prefix=SECOND
+
+## Two sections, both with symbols, one empty, other not, symbol in non-empty
+## section has value higher than target address.
+# RUN: yaml2obj %s --docnum=2 -o %t10 -D SIZE1=1 -D SIZE2=0 -D SYMVAL1=0x6 -D SYMVAL2=0x5
+# RUN: llvm-objdump -d %t10 | FileCheck %s --check-prefix=SECOND
+# RUN: yaml2obj %s --docnum=2 -o %t11 -D SIZE1=0 -D SIZE2=1 -D SYMVAL1=0x5 -D SYMVAL2=0x6
+# RUN: llvm-objdump -d %t11 | FileCheck %s --check-prefix=FIRST
+
+# FIRST:  callq 0x5 <first>
+# SECOND: callq 0x5 <second>
+
+--- !ELF
+FileHeader:
+  Class:   ELFCLASS64
+  Data:    ELFDATA2LSB
+  Type:    ET_EXEC
+  Machine: EM_X86_64
+Sections:
+  - Name:    .caller
+    Type:    SHT_PROGBITS
+    Flags:   [SHF_ALLOC, SHF_EXECINSTR]
+    Address: 0x0
+    Content: e800000000 ## Call instruction to next address.
+  - Name:    .first
+    Type:    SHT_PROGBITS
+    Flags:   [SHF_ALLOC, SHF_EXECINSTR]
+    Address: 0x5
+    Size:    [[SIZE1]]
+  - Name:    .second
+    Type:    SHT_PROGBITS
+    Flags:   [SHF_ALLOC, SHF_EXECINSTR]
+    Address: 0x5
+    Size:    [[SIZE2]]
+Symbols:
+  - Name:    first
+    Section: .first
+    Value:   [[SYMVAL1]]
+  - Name:    second
+    Section: .second
+    Value:   [[SYMVAL2]]

llvm/tools/llvm-objdump/llvm-objdump.cpp

static void disassembleObject(const Target *TheTarget, const ObjectFile *Obj,
   if (AllSymbols.empty() && Obj->isELF())
     addDynamicElfSymbols(Obj, AllSymbols);
 
   BumpPtrAllocator A;
   StringSaver Saver(A);
   addPltEntries(Obj, AllSymbols, Saver);
 
   // Create a mapping from virtual address to section. An empty section can
-  // cause more than one section at the same address. Use a stable sort to
-  // stabilize the output.
+  // cause more than one section at the same address. Sort such sections to be
+  // before same-addressed non-empty sections so that symbol lookups prefer the
+  // non-empty section.
   std::vector<std::pair<uint64_t, SectionRef>> SectionAddresses;
   for (SectionRef Sec : Obj->sections())
     SectionAddresses.emplace_back(Sec.getAddress(), Sec);
-  llvm::stable_sort(SectionAddresses, llvm::less_first());
+  llvm::stable_sort(SectionAddresses, [](const auto &LHS, const auto &RHS) {
+    if (LHS.first != RHS.first)
+      return LHS.first < RHS.first;
+    return LHS.second.getSize() < RHS.second.getSize();
+  });
 
   // Linked executables (.exe and .dll files) typically don't include a real
   // symbol table but they might contain an export table.
   if (const auto *COFFObj = dyn_cast<COFFObjectFile>(Obj)) {
     for (const auto &ExportEntry : COFFObj->export_directories()) {
       StringRef Name;
       if (std::error_code EC = ExportEntry.getSymbolName(Name))
         reportError(errorCodeToError(EC), Obj->getFileName());
for (unsigned SI = 0, SE = Symbols.size(); SI != SE; ++SI) {
              MIA->isConditionalBranch(Inst))) {
           uint64_t Target;
           if (MIA->evaluateBranch(Inst, SectionAddr + Index, Size, Target)) {
             // In a relocatable object, the target's section must reside in
             // the same section as the call instruction or it is accessed
             // through a relocation.
             //
             // In a non-relocatable object, the target may be in any section.
+            // In that case, locate the section(s) containing the target address
+            // and find the symbol in one of those, if possible.
             //
             // N.B. We don't walk the relocations in the relocatable case yet.
-            auto *TargetSectionSymbols = &Symbols;
+            std::vector<const SectionSymbolsTy *> TargetSectionSymbols;
             if (!Obj->isRelocatableObject()) {
-              auto It = partition_point(
+              auto It = llvm::partition_point(
                   SectionAddresses,
                   [=](const std::pair<uint64_t, SectionRef> &O) {
                     return O.first <= Target;
                   });
-              if (It != SectionAddresses.begin()) {
+              uint64_t TargetSecAddr = 0;
+              while (It != SectionAddresses.begin()) {
                 --It;
-                TargetSectionSymbols = &AllSymbols[It->second];
-              } else {
-                TargetSectionSymbols = &AbsoluteSymbols;
+                if (TargetSecAddr == 0)
+                  TargetSecAddr = It->first;
+                if (It->first != TargetSecAddr)
+                  break;
+                TargetSectionSymbols.push_back(&AllSymbols[It->second]);
               }
+            } else {
+              TargetSectionSymbols.push_back(&Symbols);
             }
+            TargetSectionSymbols.push_back(&AbsoluteSymbols);
 
-            // Find the last symbol in the section whose offset is less than
-            // or equal to the target. If there isn't a section that contains
-            // the target, find the nearest preceding absolute symbol.
-            auto TargetSym = partition_point(
-                *TargetSectionSymbols,
-                [=](const SymbolInfoTy &O) {
-                  return O.Addr <= Target;
-                });
-            if (TargetSym == TargetSectionSymbols->begin()) {
-              TargetSectionSymbols = &AbsoluteSymbols;
-              TargetSym = partition_point(
-                  AbsoluteSymbols,
-                  [=](const SymbolInfoTy &O) {
-                    return O.Addr <= Target;
-                  });
+            // Find the last symbol in the first candidate section whose offset
+            // is less than or equal to the target. If there are no such
+            // symbols, try in the next section and so on, before finally using
+            // the nearest preceding absolute symbol (if any), if there are no
+            // other valid symbols.
+            const SymbolInfoTy *TargetSym = nullptr;
+            for (const SectionSymbolsTy *TargetSymbols : TargetSectionSymbols) {
+              auto It = llvm::partition_point(
+                  *TargetSymbols,
+                  [=](const SymbolInfoTy &O) { return O.Addr <= Target; });
+              if (It != TargetSymbols->begin()) {
+                TargetSym = &*(It - 1);
+                break;
               }
-            if (TargetSym != TargetSectionSymbols->begin()) {
-              --TargetSym;
+            }
+
+            if (TargetSym != nullptr) {
               uint64_t TargetAddress = TargetSym->Addr;
               std::string TargetName = TargetSym->Name.str();
               if (Demangle)
                 TargetName = demangle(TargetName);
 
               outs() << " <" << TargetName;
               uint64_t Disp = Target - TargetAddress;
               if (Disp)