[llvm-objdump][CallGraphInfo] Extract and print call site info

[necipfazil]

Summary

Collect the call site information through disassembly and print per function.
For direct calls, include the target address.

Patch 3/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

228

[necipfazil]

Adapt tests to stable function order, refactor FunctionInfo::DirectCallSite

[morehouse]

LGTM

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

+## Tests --call-graph-info prints call sites.
+
+# 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 CALL SITES (CALLER_ADDR [CALL_SITE_ADDR,])
+# CHECK-NEXT: 1 8
+# CHECK-NEXT: 12 14
+# CHECK-EMPTY:
+# CHECK-NEXT: DIRECT CALL SITES (CALLER_ADDR [(CALL_SITE_ADDR, TARGET_ADDR),])
+# CHECK-NEXT: 1 6 6 d d 12 12
+# CHECK-NEXT: 12 19 19
+# CHECK-EMPTY:
+# CHECK-NEXT: FUNCTIONS (FUNC_ENTRY_ADDR, SYM_NAME)
+# CHECK-NEXT: 0 foo
+# CHECK-NEXT: 1 bar
+# CHECK-NEXT: 12 baz
+
+.text
+
+.globl foo
+.type foo,@function
+foo:
+ retq
+
+.globl bar
+.type bar,@function
+bar:
+ callq foo
+ callq  *%rcx
+ callq bar
+ callq foo
+
+.globl baz
+.type baz,@function
+baz:
+ callq *%rcx
+ callq foo

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

 #     foo();
 #     bar();
 #     baz(a);
 #
 #     return 0;
 #   }
 
 # CHECK: [[FILE]]: file format elf64-x86-64
-# CHECK: FUNCTIONS (FUNC_ENTRY_ADDR, SYM_NAME)
+# CHECK: INDIRECT CALL SITES (CALLER_ADDR [CALL_SITE_ADDR,])
+# CHECK-NEXT: 401000 401012
+# CHECK-NEXT: 401020 40104a
+# CHECK-NEXT: 401140 401165 40117b 401195
+# CHECK-NEXT: 4011c0 401205
+# CHECK-EMPTY:
+# CHECK-NEXT: DIRECT CALL SITES (CALLER_ADDR [(CALL_SITE_ADDR, TARGET_ADDR),])
+# CHECK-NEXT: 4010d0 4010e2 401060
+# CHECK-NEXT: 401140 40119a 401110 40119f 401120 4011aa 401130
+# CHECK-NEXT: 4011c0 4011ed 401000
+# CHECK-EMPTY:
+# CHECK-NEXT: FUNCTIONS (FUNC_ENTRY_ADDR, SYM_NAME)
 # CHECK-NEXT: 401000 _init
 # CHECK-NEXT: 401020 _start
 # CHECK-NEXT: 401050 _dl_relocate_static_pie
 # CHECK-NEXT: 401060 deregister_tm_clones
 # CHECK-NEXT: 401090 register_tm_clones
 # CHECK-NEXT: 4010d0 __do_global_dtors_aux
 # CHECK-NEXT: 401100 frame_dummy
 # CHECK-NEXT: 401110 foo

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

 static bool Wide;
 std::string objdump::Prefix;
 uint32_t objdump::PrefixStrip;
 
 static bool QuietDisasm = false;
 
 struct FunctionInfo {
   std::string Name;
+
+  struct DirectCallSite {
+    uint64_t CallSite;
+    uint64_t Callee;
+    DirectCallSite(uint64_t CallSite, uint64_t Callee)
+        : CallSite(CallSite), Callee(Callee) {}
+  };
+  SmallVector<DirectCallSite> DirectCallSites;
+  SmallVector<uint64_t> IndirectCallSites;
 };
 
 // Map function entry pc to function info.
 MapVector<uint64_t, FunctionInfo> FuncInfo;
 
 DebugVarsFormat objdump::DbgVariables = DVDisabled;
 
 int objdump::DbgIndent = 52;
for (unsigned SI = 0, SE = Symbols.size(); SI != SE; ++SI) {
               DisAsm->getInstruction(Inst, Size, Bytes.slice(Index),
                                      SectionAddr + Index, CommentStream);
           if (Size == 0)
             Size = 1;
 
           LVP.update({Index, Section.getIndex()},
                      {Index + Size, Section.getIndex()}, Index + Size != End);
 
+          if (CallGraphInfo) {
+            if (Disassembled && MIA->isCall(Inst)) {
+              // Call site address is the address of the instruction just
+              // next to the call instruction. This is the return address
+              // as appears on the stack trace.
+              uint64_t CallSitePc = SectionAddr + Index + Size;
+              uint64_t CallerPc = Symbols[SI].Addr;
+              // Check the operands to decide whether this is an direct or
+              // indirect call.
+              // Assumption: a call instruction with at least one register
+              // operand is an indirect call. Otherwise, it is a direct call
+              // with exactly one immediate operand.
+              bool HasRegOperand = false;
+              unsigned int ImmOperandCount = 0;
+              const MCOperand *ImmOperand = NULL;
+              for (unsigned int I = 0; I < Inst.getNumOperands(); I++) {
+                const auto &Operand = Inst.getOperand(I);
+                if (Operand.isReg()) {
+                  HasRegOperand = true;
+                } else if (Operand.isImm()) {
+                  ImmOperandCount++;
+                  ImmOperand = &Operand;
+                }
+              }
+              // 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.
+                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,
+                                                                CalleePc);
+              }
+            }
+          }
+
           IP->setCommentStream(CommentStream);
 
           PIP.printInst(
               *IP, Disassembled ? &Inst : nullptr, Bytes.slice(Index, Size),
               {SectionAddr + Index + VMAAdjustment, Section.getIndex()}, FOS,
               "", *STI, &SP, Obj->getFileName(), &Rels, LVP);
 
           IP->setCommentStream(llvm::nulls());
void objdump::printSymbol(const ObjectFile *O, const SymbolRef &Symbol,
   else
     outs() << ' ' << Name << '\n';
 }
 
 static void printCallGraphInfo(const ObjectFile *Obj) {
   // Get function info through disassembly.
   disassembleObject(Obj, /*InlineRelocs=*/false);
 
+  // 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)
+        outs() << " " << format("%lx", IndirCallSitePc);
+    }
+  }
+
+  // Print function entry to direct call site and target function entry
+  // addresses mapping from disasm.
+  outs()
+      << "\n\nDIRECT CALL SITES (CALLER_ADDR [(CALL_SITE_ADDR, TARGET_ADDR),])";
+  for (const auto &El : FuncInfo) {
+    auto CallerPc = El.first;
+    auto FuncDirCallSites = El.second.DirectCallSites;
+    if (!FuncDirCallSites.empty()) {
+      outs() << "\n" << format("%lx", CallerPc);
+      for (const FunctionInfo::DirectCallSite &DCS : FuncDirCallSites) {
+        outs() << " " << format("%lx", DCS.CallSite) << " "
+               << format("%lx", DCS.Callee);
+      }
+    }
+  }
+
   // Print function entry pc to function name mapping.
   outs() << "\n\nFUNCTIONS (FUNC_ENTRY_ADDR, SYM_NAME)";
   for (const auto &El : FuncInfo) {
     uint64_t EntryPc = El.first;
     const auto &Name = El.second.Name;
     outs() << "\n" << format("%lx", EntryPc) << " " << Name;
   }
   outs() << "\n";