[llvm-objdump][CallGraphInfo] Parse .callgraph section

[necipfazil]

Summary

Parse the .callgraph section for indirect call graph information. Print type
identifier mappings for indirect calls and targets.

Patch 6/6: Extract call graph information from binary

Original RFC: https://lists.llvm.org/pipermail/llvm-dev/2021-June/151044.html
Updated RFC: https://lists.llvm.org/pipermail/llvm-dev/2021-July/151739.html

[morehouse]

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

2148

We probably want sorted maps to avoid tests breaking in the future.

[necipfazil]

Use stable iteration order and adapt tests

Use MapVector instead of DenseMap for structs that would break the tests
in the future due to unstable iteration order.

[morehouse]

LGTM

[jhenderson]

Apologies, I haven't had a chance to get back to this or the rest of the patch series, and I'm off work next week, so won't be able to until after getting back.

It might be worth trying to get some people to comment on your upstream RFC and see if they are happy for the additional functionality to be added.

llvm/test/tools/llvm-objdump/ELF/call-graph-info-callgraph-section-warnings.test

+## Tests --call-graph-info warnings for missing/invalid .callgraph section
+## contents.
+
+# RUN: llvm-mc %s -filetype=obj -triple=x86_64-pc-linux -o %t
+# RUN: llvm-objdump --call-graph-info %t 2>&1 | FileCheck %s -DFILE=%t
+
+# CHECK: [[FILE]]: file format elf64-x86-64
+# CHECK-NEXT: llvm-objdump: warning: '[[FILE]]': callgraph section has type ids for 1 instructions which are not indirect calls
+# CHECK-NEXT: llvm-objdump: warning: '[[FILE]]': callgraph section does not have type ids for 1 indirect calls
+# CHECK-NEXT: llvm-objdump: warning: '[[FILE]]': callgraph section does not have information for 1 functions
+# CHECK-NEXT: llvm-objdump: warning: '[[FILE]]': callgraph section has unknown type id for 1 indirect targets
+
+.text
+.globl foo
+.type foo,@function
+foo:
+.Lfoo_begin:
+.Lnot_indirect_call:
+ retq
+
+.globl bar
+.type bar,@function
+bar:
+ callq  *%rcx
+
+.section  .callgraph,"o",@progbits,.text
+.quad 0             #< Format version number.
+.quad .Lfoo_begin   #< foo()'s entry address.
+.quad 1             #< A warning: function kind is 1: the type id for indirect target foo is unknown.
+.quad 1             #< Count of indirect call sites that follow: 1.
+.quad 0             #< Indirect call type id.
+.quad .Lnot_indirect_call  #< A warning: type id for non-indirect call instruction.
+# A warning: .callgraph section does not have information for 1 function (bar).
+# A warning: .callgraph section does not have type id for 1 indirect call (one in bar).
+.text

llvm/test/tools/llvm-objdump/ELF/call-graph-info-callgraph-section.test

+## Tests --call-graph-info prints information from call graph section.
+
+# RUN: llvm-mc %s -filetype=obj -triple=x86_64-pc-linux -o %t
+# RUN: llvm-objdump --call-graph-info %t 2>&1 | FileCheck %s -DFILE=%t
+
+# CHECK: [[FILE]]: file format elf64-x86-64
+
+# CHECK: INDIRECT TARGET TYPES (TYPEID [FUNC_ADDR,])
+# CHECK-NEXT: UNKNOWN b 6
+# CHECK-NEXT: 20 a
+# CHECK-EMPTY:
+# CHECK-NEXT: INDIRECT CALL TYPES (TYPEID [CALL_SITE_ADDR,])
+# CHECK-NEXT: 10 9
+# CHECK-EMPTY:
+# CHECK-NEXT: INDIRECT CALL SITES (CALLER_ADDR [CALL_SITE_ADDR,])
+# CHECK-NEXT: 6 9
+# CHECK-EMPTY:
+# CHECK-NEXT: DIRECT CALL SITES (CALLER_ADDR [(CALL_SITE_ADDR, TARGET_ADDR),])
+# CHECK-NEXT: 0 5 5
+# CHECK-EMPTY:
+# CHECK-NEXT: FUNCTIONS (FUNC_ENTRY_ADDR, SYM_NAME)
+# CHECK-NEXT: 0 foo
+# CHECK-NEXT: b qux
+# CHECK-NEXT: 6 bar
+# CHECK-NEXT: a baz
+
+.text
+
+.globl foo
+.type foo,@function
+foo:                  #< foo is at 0.
+.Lfoo_begin:
+ callq foo            #< direct call is at 5. target is foo (5).
+ retq
+
+.globl bar
+.type bar,@function
+bar:                  #< bar is at 6.
+ callq  *-40(%rbp)    #< indirect call is at 9.
+ retq
+
+.globl baz
+.type baz,@function
+baz:                  #< baz is at 10 (a).
+ retq
+
+.globl qux
+.type qux,@function
+qux:                  #< qux is at 11 (b).
+ retq
+
+.section  .callgraph,"o",@progbits,.text
+.quad 0       #< Format version number.
+.quad 0       #< foo()'s entry address.
+.quad 0       #< Function kind: not an indirect target.
+.quad 0       #< Count of indirect call sites that follow: 0.
+
+.quad 0       #< Format version number.
+.quad 6       #< bar()'s entry address.
+.quad 1       #< Function kind: indirect target with unknown type id.
+.quad 1       #< Count of indirect call sites that follow: 1.
+.quad 16      #< Indirect call type id.
+.quad 9       #< Indirect call site.
+
+.quad 0       #< Format version number.
+.quad 10      #< baz()'s entry address.
+.quad 2       #< Function kind: indirect target with known type id.
+.quad 32      #< Indirect target type id.
+.quad 0       #< Count of indirect call sites that follow: 1.
+
+# No call graph section entry for qux: will be printed as unknown target.
+
+.text

llvm/test/tools/llvm-objdump/ELF/call-graph-info-err-invalid-format-version.test

+## Tests that --call-graph-info fails if .callgraph section has unknown format
+## version number.
+
+# RUN: llvm-mc %s -filetype=obj -triple=x86_64-pc-linux -o %t
+# RUN: not llvm-objdump --call-graph-info %t 2>&1 | FileCheck %s -DFILE=%t --check-prefix=ERR
+
+# CHECK: [[FILE]]: file format elf64-x86-64
+# ERR: llvm-objdump: error: '[[FILE]]': Unknown format version in .callgraph section.
+
+.text
+.globl _Z3foov
+.type _Z3foov,@function
+_Z3foov:
+ callq _Z3foov@PLT
+
+.section  .callgraph,"o",@progbits,.text
+.quad 1  #< Invalid format version number: the only supported version is 0.
+.text

llvm/test/tools/llvm-objdump/ELF/call-graph-info-err-invalid-func-entry.test

+## Tests that --call-graph-info fails if .callgraph section has invalid
+## function entry address.
+
+# RUN: llvm-mc %s -filetype=obj -triple=x86_64-pc-linux -o %t
+# RUN: not llvm-objdump --call-graph-info %t 2>&1 | FileCheck %s -DFILE=%t --check-prefix=ERR
+
+# CHECK: [[FILE]]: file format elf64-x86-64
+# ERR: llvm-objdump: error: '[[FILE]]': Invalid function entry pc in .callgraph section.
+
+.text
+.globl _Z3foov
+.type _Z3foov,@function
+_Z3foov:
+ callq _Z3foov@PLT
+
+.section  .callgraph,"o",@progbits,.text
+.quad 0     #< Format version number.
+.quad 12345 #< Invalid function entry address.
+.text

llvm/test/tools/llvm-objdump/ELF/call-graph-info-err-invalid-func-kind.test

+## Tests that --call-graph-info fails if .callgraph section has invalid
+## function kind value.
+
+# RUN: llvm-mc %s -filetype=obj -triple=x86_64-pc-linux -o %t
+# RUN: not llvm-objdump --call-graph-info %t 2>&1 | FileCheck %s -DFILE=%t --check-prefix=ERR
+
+# CHECK: [[FILE]]: file format elf64-x86-64
+# ERR: llvm-objdump: error: '[[FILE]]': Unknown function kind in .callgraph section.
+
+.text
+.globl _Z3foov
+.type _Z3foov,@function
+_Z3foov:
+ callq _Z3foov@PLT
+
+.section  .callgraph,"o",@progbits,.text
+.quad 0   #< Format version number.
+.quad 0   #< Function entry address.
+.quad 3   #< Invalid function kind: must be one of 0, 1, 2.
+.text

llvm/test/tools/llvm-objdump/ELF/call-graph-info-err-malformed-callgraph-section.test

+## Tests that --call-graph-info fails if .callgraph section has invalid size.
+
+# RUN: llvm-mc %s -filetype=obj -triple=x86_64-pc-linux -o %t
+# RUN: not llvm-objdump --call-graph-info %t 2>&1 | FileCheck %s -DFILE=%t --check-prefix=ERR
+
+# CHECK: [[FILE]]: file format elf64-x86-64
+# ERR: llvm-objdump: error: '[[FILE]]': Malformed .callgraph section.
+
+.text
+.globl _Z3foov
+.type _Z3foov,@function
+_Z3foov:
+ callq _Z3foov@PLT
+
+.section  .callgraph,"o",@progbits,.text
+# Each unit in .callgraph section must have 64bit size. Therefore, byte size
+# must be divisible by 64.
+.quad 0
+.quad 0
+.quad 0
+.byte 0
+.text

llvm/test/tools/llvm-objdump/ELF/call-graph-info-err-malformed-callgraph-section2.test

+## Tests that --call-graph-info fails if .callgraph section does not have
+## an expected value, e.g., not as much call sites as the given count.
+
+# RUN: llvm-mc %s -filetype=obj -triple=x86_64-pc-linux -o %t
+# RUN: not llvm-objdump --call-graph-info %t 2>&1 | FileCheck %s -DFILE=%t --check-prefix=ERR
+
+# CHECK: [[FILE]]: file format elf64-x86-64
+# ERR: llvm-objdump: error: '[[FILE]]': Malformed .callgraph section.
+
+.text
+.globl _Z3foov
+.type _Z3foov,@function
+_Z3foov:
+ callq _Z3foov@PLT
+
+.section  .callgraph,"o",@progbits,.text
+.quad 0  #< Format version number.
+.quad 0  #< Function entry address.
+.quad 0  #< Function kind.
+.quad 2  #< Indirect call site count that follows.
+         #< Missing indirect calls?
+.text

llvm/test/tools/llvm-objdump/ELF/call-graph-info.test

 #     foo();
 #     bar();
 #     baz(a);
 #
 #     return 0;
 #   }
 
 # CHECK: [[FILE]]: file format elf64-x86-64
-# CHECK: INDIRECT CALL SITES (CALLER_ADDR [CALL_SITE_ADDR,])
+# CHECK-NEXT: llvm-objdump: warning: '[[FILE]]': callgraph section does not have type ids for 3 indirect calls
+# CHECK-NEXT: llvm-objdump: warning: '[[FILE]]': callgraph section does not have information for 10 functions
+# CHECK-EMPTY:
+# CHECK-NEXT: INDIRECT TARGET TYPES (TYPEID [FUNC_ADDR,])
+# CHECK-NEXT: UNKNOWN 401000 401100 4011c0 401050 401090 4010d0 401020 401060 401220 401224
+# CHECK-NEXT: 308e4b8159bc8654 401130
+# CHECK-NEXT: fa6809609a76afca 401140
+# CHECK-NEXT: 3ecbeef531f74424 401110 401120
+# CHECK-EMPTY:
+# CHECK-NEXT: INDIRECT CALL TYPES (TYPEID [CALL_SITE_ADDR,])
+# CHECK-NEXT: 308e4b8159bc8654 401195
+# CHECK-NEXT: 3ecbeef531f74424 401165 40117b
+# CHECK-EMPTY:
+# CHECK-NEXT: INDIRECT CALL SITES (CALLER_ADDR [CALL_SITE_ADDR,])
 # CHECK-NEXT: 401000 401012
 # CHECK-NEXT: 401140 401165 40117b 401195
 # CHECK-NEXT: 4011c0 401205
 # CHECK-NEXT: 401020 40104a
 # CHECK-EMPTY:
 # CHECK-NEXT: DIRECT CALL SITES (CALLER_ADDR [(CALL_SITE_ADDR, TARGET_ADDR),])
 # CHECK-NEXT: 401140 40119a 401110 40119f 401120 4011aa 401130
 # CHECK-NEXT: 4011c0 4011ed 401000

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

struct FunctionInfo {
   using DirectCallSite = std::pair<uint64_t /*CallSite*/, uint64_t /*Callee*/>;
   SmallVector<DirectCallSite> DirectCallSites;
   SmallVector<uint64_t> IndirectCallSites;
 };
 
 // Map function entry pc to function info.
 DenseMap<uint64_t, FunctionInfo> FuncInfo;
 
+// Set of all indirect call sites.
+DenseSet<uint64_t> IndirectCallSites;
+
 DebugVarsFormat objdump::DbgVariables = DVDisabled;
 
 int objdump::DbgIndent = 52;
 
 static StringSet<> DisasmSymbolSet;
 StringSet<> objdump::FoundSectionSet;
 static StringRef ToolName;
 
for (unsigned SI = 0, SE = Symbols.size(); SI != SE; ++SI) {
               // Check if the assumption holds true.
               assert(HasRegOperand ||
                      (!HasRegOperand && ImmOperandCount == 1) &&
                          "Call instruction is expected to have at least one "
                          "register operand (i.e., indirect call) or exactly "
                          "one immediate operand (i.e., direct call).");
               if (HasRegOperand) {
                 // Indirect call.
+                IndirectCallSites.insert(CallSitePc);
                 FuncInfo[CallerPc].IndirectCallSites.push_back(CallSitePc);
               } else {
                 // Direct call.
                 uint64_t CalleePc;
                 bool Res = MIA->evaluateBranch(Inst, SectionAddr + Index, Size,
                                                CalleePc);
                 assert(Res && "Failed to evaluate direct call target address.");
                 FuncInfo[CallerPc].DirectCallSites.emplace_back(CallSitePc,
for (auto Sec : ToolSectionFilter(*Obj)) {
     if (Name == CallGraphSectionName) {
       CallGraphSection = Sec;
       break;
     }
   }
   if (!CallGraphSection)
     reportWarning("there is no .callgraph section", Obj->getFileName());
 
+  // Map type id to indirect call sites.
+  DenseMap<uint64_t, SmallVector<uint64_t>> TypeIdToIndirCallSites;
+  // Map type id to indirect targets.
+  DenseMap<uint64_t, SmallVector<uint64_t>> TypeIdToIndirTargets;
+  // Instructions that are not indirect calls but have a type id are ignored.
+  uint64_t IgnoredICallIdCount = 0;
+  // Number of valid indirect calls with type ids.
+  uint64_t ICallWithTypeIdCount = 0;
+  if (CallGraphSection) {
+    StringRef CGSecContents = unwrapOrError(
+        CallGraphSection.getValue().getContents(), Obj->getFileName());
+    // TODO: some entries are written in pointer size. are they always 64-bit?
+    if (CGSecContents.size() % sizeof(uint64_t))
+      reportError(Obj->getFileName(), "Malformed .callgraph section.");
+
+    size_t Size = CGSecContents.size() / sizeof(uint64_t);
+    auto *It = reinterpret_cast<const uint64_t *>(CGSecContents.data());
+    const auto *const End = It + Size;
+
+    auto CGHasNext = [&]() { return It < End; };
+    auto CGNext = [&]() -> uint64_t {
+      if (!CGHasNext())
+        reportError(Obj->getFileName(), "Malformed .callgraph section.");
+      return *It++;
+    };
+
+    // Parse the content
+    while (CGHasNext()) {
+      // Format version number.
+      uint64_t FormatVersionNumber = CGNext();
+      if (FormatVersionNumber != 0)
+        reportError(Obj->getFileName(),
+                    "Unknown format version in .callgraph section.");
+
+      // Function entry pc.
+      uint64_t FuncEntryPc = CGNext();
+      if (!FuncInfo.count(FuncEntryPc))
+        reportError(Obj->getFileName(),
+                    "Invalid function entry pc in .callgraph section.");
+
+      // Function kind.
+      uint64_t Kind = CGNext();
+      switch (Kind) {
+      case 0: // not an indirect target
+        FuncInfo[FuncEntryPc].Kind = NOT_INDIRECT_TARGET;
+        break;
+      case 1: // indirect target with unknown type id
+        FuncInfo[FuncEntryPc].Kind = INDIRECT_TARGET_UNKNOWN_TID;
+        break;
+      case 2: // indirect target with known type id
+        FuncInfo[FuncEntryPc].Kind = INDIRECT_TARGET_KNOWN_TID;
+        TypeIdToIndirTargets[CGNext()].push_back(FuncEntryPc);
+        break;
+      default:
+        reportError(Obj->getFileName(),
+                    "Unknown function kind in .callgraph section.");
+      }
+
+      // Read call sites.
+      uint64_t CallSiteCount = CGNext();
+      for (unsigned long I = 0; I < CallSiteCount; I++) {
+        uint64_t TypeId = CGNext();
+        uint64_t CallSitePc = CGNext();
+        if (IndirectCallSites.count(CallSitePc)) {
+          TypeIdToIndirCallSites[TypeId].push_back(CallSitePc);
+          ICallWithTypeIdCount++;
+        } else {
+          // FIXME: .callgraph may have type ids for calls that are lowered to
+          // jump, which is why ignoring indirect call type ids are expected.
+          // However, actual indirect call site references stored as relocation
+          // entries here may also be discarded.
+          IgnoredICallIdCount++;
+        }
+      }
+    }
+
+    // Print any required warnings regarding the callgraph section.
+    if (IgnoredICallIdCount)
+      reportWarning("callgraph section has type ids for " +
+                        std::to_string(IgnoredICallIdCount) + " instructions " +
+                        "which are not indirect calls",
+                    Obj->getFileName());
+
+    if (auto ICallWithoutTypeIdCount =
+            IndirectCallSites.size() - ICallWithTypeIdCount)
+      reportWarning("callgraph section does not have type ids for " +
+                        std::to_string(ICallWithoutTypeIdCount) +
+                        " indirect calls",
+                    Obj->getFileName());
+
+    uint64_t NotListedCount = 0;
+    uint64_t UnknownCount = 0;
+    for (const auto &El : FuncInfo) {
+      NotListedCount += El.second.Kind == NOT_LISTED;
+      UnknownCount += El.second.Kind == INDIRECT_TARGET_UNKNOWN_TID;
+    }
+    if (NotListedCount)
+      reportWarning("callgraph section does not have information for " +
+                        std::to_string(NotListedCount) + " functions",
+                    Obj->getFileName());
+    if (UnknownCount)
+      reportWarning("callgraph section has unknown type id for " +
+                        std::to_string(UnknownCount) + " indirect targets",
+                    Obj->getFileName());
+
+    // Print indirect targets
+    outs() << "\nINDIRECT TARGET TYPES (TYPEID [FUNC_ADDR,])";
+
+    // Print indirect targets with unknown type.
+    // For completeness, functions for which the call graph section does not
+    // provide information are included.
+    if (NotListedCount || UnknownCount) {
+      outs() << "\nUNKNOWN";
+      for (const auto &El : FuncInfo) {
+        uint64_t FuncEntryPc = El.first;
+        FunctionKind FuncKind = El.second.Kind;
+        if (FuncKind == NOT_LISTED || FuncKind == INDIRECT_TARGET_UNKNOWN_TID)
+          outs() << " " << format("%lx", FuncEntryPc);
+      }
+    }
+
+    // Print indirect targets to type id mapping.
+    for (const auto &El : TypeIdToIndirTargets) {
+      uint64_t TypeId = El.first;
+      outs() << "\n" << format("%lx", TypeId);
+      for (uint64_t IndirTargetPc : El.second)
+        outs() << " " << format("%lx", IndirTargetPc);
+    }
+
+    // Print indirect calls to type id mapping. Any indirect call without a
+    // type id can be deduced by comparing this list to indirect call sites
+    // list.
+    outs() << "\n\nINDIRECT CALL TYPES (TYPEID [CALL_SITE_ADDR,])";
+    for (const auto &El : TypeIdToIndirCallSites) {
+      uint64_t TypeId = El.first;
+      outs() << "\n" << format("%lx", TypeId);
+      for (uint64_t IndirCallSitePc : El.second)
+        outs() << " " << format("%lx", IndirCallSitePc);
+    }
+  }
+
   // Print function entry to indirect call site addresses mapping from disasm.
   outs() << "\n\nINDIRECT CALL SITES (CALLER_ADDR [CALL_SITE_ADDR,])";
   for (const auto &El : FuncInfo) {
     auto CallerPc = El.first;
     auto FuncIndirCallSites = El.second.IndirectCallSites;
     if (!FuncIndirCallSites.empty()) {
       outs() << "\n" << format("%lx", CallerPc);
       for (auto IndirCallSitePc : FuncIndirCallSites)