[CallGraphSection] Add call graph section options and documentation

[Prabhuk]

Summary

This is the first of the patch series that adds the support for
computing, storing, and restoring call graphs with LLVM. This adds the
options and the design documentation for computing and storing the call
graphs.

Inferring indirect call targets from a binary is challenging without
source-level information. Hence, the reconstruction of a fine-grained
call graph from the binary is unfeasible for indirect/virtual calls.
To address this, designed solution is to collect the necessary information
to construct the call graph while the source information is present, and
store it in a non-code section of the binary. To enable, use
-fcall-graph-section for Clang, or --call-graph-section for LLVM.

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]

clang/docs/CallGraphSection.rst

58 ↗

(On Diff #358319)

Why would a type ID be repeated?

61 ↗

(On Diff #358319)

69 ↗

(On Diff #358319)

148 ↗

(On Diff #358319)

Why quotes around these table headers/entries?

160 ↗

(On Diff #358319)

Why is this?

174 ↗

(On Diff #358319)

Do we need to list functions that don't match any callsites (e.g., main)?

183 ↗

(On Diff #358319)

So this section is useful for constructing the call graph, but we don't really need it for stack trace reconstruction, right?

[necipfazil]

clang/docs/CallGraphSection.rst

58 ↗

(On Diff #358319)

Current implementation [1] creates a call graph section per function comdat group, to which the assembly printer writes the call graph entries related to the function. This is done to enable dead-stripping of call graph entries. Consequently, the callsites from two functions may share the same type ID but appear as distinct entries as they will be written to distinct sections. Although they are merged to a single section by the linker, the type ID repetition persists since the linker only concatenates.

Eliminating this to ensure that type IDs are not repeated should only decrease the binary size overhead.

[1] https://reviews.llvm.org/D105916 , see MCObjectFileInfo::getCallGraphSection()

148 ↗

(On Diff #358319)

Quotes are placed to espace commas (actually, there is only one) in the table cells. They are not visible in the output html.

160 ↗

(On Diff #358319)

Please see the response above.

174 ↗

(On Diff #358319)

They may be needed for dynamically loaded objects whose functions are called indirectly outside the object.

183 ↗

(On Diff #358319)

For stack trace reconstruction, we need the full reverse call graph, thus, this section. Without this section, which function makes the indirect call is unknown.

During stack trace reconstruction, let's say we end up in a state where an indirect call is seen. To take another step, we need to know which function made this indirect call, so that we can continue the search through the callers of that function.

[necipfazil]

rebase, fix nits in docs

[morehouse]

We should also tests for the new flags in clang/test/Driver/clang_f_opts.c.

clang/docs/CallGraphSection.rst

58 ↗

(On Diff #358319)

Indeed, this is a tricky problem. The current solution is probably OK, but maybe we can simplify the callgraph section format in light of this solution. e.g.,

Format version, Type id, IsFuncEntry, PC
  0, NumericTypeId(foo), 1, FuncEntryPc(foo)
  0, NumericTypeId(foo), 0, CallSitePc(fp_foo())
  0, NumericTypeId(main), 1, FuncEntryPc(main)

cc @MaskRay

[necipfazil]

• test new clang flags
• rebase

[morehouse]

clang/test/Driver/clang_f_opts.c

603 ↗

(On Diff #359010)

For completeness, we should also test

-fcall-graph-section -fno-call-graph-section

and

-fno-call-graph-section -fcall-graph-section

[MaskRay]

clang/test/Driver/clang_f_opts.c

603 ↗

(On Diff #359010)

I find it usually a bit wasteful to have too many RUN lines for a boolean option.

Testing just -fcall-graph-section and -fcall-graph-section -fno-call-graph-section will look good enough to me. See coverage.c for an example.

I think nowadays the practice is to have boolean options tested in separate files, instead of the monolithic clang_f_opts.c

(I saw you CCed me. I have applied the patch series locally. I need to experiment it a bit before commenting.)

[necipfazil]

Change call graph section layout

• Changed the call graph section layout
• Extended the example
• Updated the documentation

In the previous version, the call graph section layout was optimized for
entries with unique type ids in which to list any indirect calls and targets
with such type id. However, the implementation requirements prevented sharing
information from different functions in the same entry. The main reason is
the need for separate entries per functions to allow dead-stripping.

As the previous layout was suboptimal for per-function call graph section
entries, a new layout is created. Please see the updated documentation for the
new layout.

The new layout has the following advantages:

• The previous layout allowed multiple indirect targets to be listed in a single entry. However, there was no use since each entry was created for a single function. With the new layout, an entry is said to belong to a function, and lists info on the function and its indirect callsites. Consequently, the layout is designed for per-function entry approach.
• The previous layout listed callsites per type id as (TypeId, CallSitesWithTypeIdCount, [CallSite1WithTypeId, ...]). However, now that the callsites are listed per function, a small number of callsites are expected for each type id. Therefore, they are now listed as (TypeId, CallSite) pairs to avoid wasting space on count values that are usually 1.
• In the previous layout, if a function was not an indirect target, its entry PC was not included. This prevented making the distinction between
  1. the non-indirect target functions and 2) those functions that we had no information about (e.g., functions from linked objects with no call graph section). With the new layout, the function entry PC is always listed. It is marked as non-indirect target if so. For completeness, the user still needs to take any function with missing information as receiver to any indirect calls. However, the user can avoid doing the same for the non-indirect targets as their entry PCs are now listed, which improves the precision for the resulting call graph.

[MaskRay]

High-level comments:

I'd use a bottom-up patch order. llvm patches are before clang patches.
The clang driver patch is the last - having the user-facing option requires the functionality to be fully available.
llvm-objdump patch is orthogonal to clang patches, so its order is flexible.

If the section only contains indirect call edges, perhaps it should have indirect in the option name.

clang/docs/CallGraphSection.rst

9 ↗

(On Diff #359592)

object file

20 ↗

(On Diff #359592)

missing

21 ↗

(On Diff #359592)

due to having unneeded edges

29 ↗

(On Diff #359592)

`--call-graph-info`

clang/include/clang/Basic/CodeGenOptions.def

423 ↗

(On Diff #359592)

make sense to move it near EmitCallSiteInfo

clang/include/clang/Driver/Options.td

1258 ↗

(On Diff #359592)

make sense to move it near stacksizessection

clang/lib/CodeGen/BackendUtil.cpp

571 ↗

(On Diff #359592)

make sense to move it near EmitCallSiteInfo

clang/lib/Driver/ToolChains/Clang.cpp

6416 ↗

(On Diff #359592)

make sense to move it near stacksizessection

[morehouse]

New .callgraph section layout LGTM.

Please also address any further feedback from Fangrui.

[necipfazil]

Fix nits in documentation and tests

[MaskRay]

My previous feeling still applies. It seems to me that the clang driver patch should be the last.

[dblaikie]

Looks like the RFC threads didn't have any discussion - I think that'll be necessary before moving forward with/committing any work here, for what it's worth. Perhaps some Apple folks would have some interest since they use ARM and sanitizers a lot & probably care about performance of those things together too?

Might be worth looking at the overall feature this is part of - efficient call stack retrieval/rebuilding, by the sounds of it/from what I understand of the original proposal.

[Prabhuk]

https://discourse.llvm.org/t/rfc-computing-storing-and-restoring-conservative-call-graphs-with-llvm/58446/3?u=prabhuk

[Prabhuk]

Rebased the patchset and addressed the compilation failures

llvm/include/llvm/CodeGen/AsmPrinter.h

 // all asm writers.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_ASMPRINTER_H
 #define LLVM_CODEGEN_ASMPRINTER_H
 
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/CodeGen/AsmPrinterHandler.h"
 #include "llvm/CodeGen/DwarfStringPoolEntry.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/StackMaps.h"
 #include "llvm/DebugInfo/CodeView/CodeView.h"
private:
   std::unique_ptr<AddrLabelMap> AddrLabelSymbols;
 
   /// The garbage collection metadata printer table.
   DenseMap<GCStrategy *, std::unique_ptr<GCMetadataPrinter>> GCMetadataPrinters;
 
   /// Emit comments in assembly output if this is true.
   bool VerboseAsm;
 
+  /// Store symbols and type identifiers used to create call graph section
+  /// entries related to a function.
+  struct FunctionInfo {
+    /// Numeric type identifier used in call graph section for indirect calls
+    /// and targets.
+    using CGTypeId = uint64_t;
+
+    /// Enumeration of function kinds, and their mapping to function kind values
+    /// stored in call graph section entries.
+    /// Must match the enum in llvm/tools/llvm-objdump/llvm-objdump.cpp.
+    enum FunctionKind {
+      /// Function cannot be target to indirect calls.
+      NOT_INDIRECT_TARGET = 0,
+
+      /// Function may be target to indirect calls but its type id is unknown.
+      INDIRECT_TARGET_UNKNOWN_TID = 1,
+
+      /// Function may be target to indirect calls and its type id is known.
+      INDIRECT_TARGET_KNOWN_TID = 2,
+    };
+
+    /// Map type identifiers to callsite labels. Labels are only for indirect
+    /// calls and inclusive of all indirect calls of the function.
+    SmallVector<std::pair<CGTypeId, MCSymbol *>> CallSiteLabels;
+  };
+
   /// Output stream for the stack usage file (i.e., .su file).
   std::unique_ptr<raw_fd_ostream> StackUsageStream;
 
   /// List of symbols to be inserted into PC sections.
   DenseMap<const MDNode *, SmallVector<const MCSymbol *>> PCSectionsSymbols;
 
   static char ID;
 
public:
 
   void emitStackUsage(const MachineFunction &MF);
 
   void emitBBAddrMapSection(const MachineFunction &MF);
 
   void emitKCFITrapEntry(const MachineFunction &MF, const MCSymbol *Symbol);
   virtual void emitKCFITypeId(const MachineFunction &MF);
 
+  void emitCallGraphSection(const MachineFunction &MF, FunctionInfo &FuncInfo);
+
   void emitPseudoProbe(const MachineInstr &MI);
 
   void emitRemarksSection(remarks::RemarkStreamer &RS);
 
   /// Emits a label as reference for PC sections.
   void emitPCSectionsLabel(const MachineFunction &MF, const MDNode &MD);
 
   /// Emits the PC sections collected from instructions.

llvm/include/llvm/MC/MCObjectFileInfo.h

protected:
   /// various bits of code will fall back to using the data section for
   /// constants.
   MCSection *ReadOnlySection = nullptr;
 
   /// If exception handling is supported by the target, this is the section the
   /// Language Specific Data Area information is emitted to.
   MCSection *LSDASection = nullptr;
 
+  /// Section containing metadata on call graph.
+  MCSection *CallGraphSection = nullptr;
+
   /// If exception handling is supported by the target and the target can
   /// support a compact representation of the CIE and FDE, this is the section
   /// to emit them into.
   MCSection *CompactUnwindSection = nullptr;
 
   // Dwarf sections for debug info.  If a target supports debug info, these must
   // be set.
   MCSection *DwarfAbbrevSection = nullptr;
public:
   MCSection *getTLSExtraDataSection() const { return TLSExtraDataSection; }
   const MCSection *getTLSDataSection() const { return TLSDataSection; }
   MCSection *getTLSBSSSection() const { return TLSBSSSection; }
 
   MCSection *getStackMapSection() const { return StackMapSection; }
   MCSection *getFaultMapSection() const { return FaultMapSection; }
   MCSection *getRemarksSection() const { return RemarksSection; }
 
+  MCSection *getCallGraphSection(const MCSection &TextSec) const;
+
   MCSection *getStackSizesSection(const MCSection &TextSec) const;
 
   MCSection *getBBAddrMapSection(const MCSection &TextSec) const;
 
   MCSection *getKCFITrapSection(const MCSection &TextSec) const;
 
   MCSection *getPseudoProbeSection(const MCSection &TextSec) const;
 

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

void AsmPrinter::emitStackUsage(const MachineFunction &MF) {
 
   *StackUsageStream << ':' << MF.getName() << '\t' << StackSize << '\t';
   if (FrameInfo.hasVarSizedObjects())
     *StackUsageStream << "dynamic\n";
   else
     *StackUsageStream << "static\n";
 }
 
+/// Extracts a generalized numeric type identifier of a Function's type from
+/// type metadata. Returns null if metadata cannot be found.
+static ConstantInt *extractNumericCGTypeId(const Function &F) {
+  SmallVector<MDNode *, 2> Types;
+  F.getMetadata(LLVMContext::MD_type, Types);
+  MDString *MDGeneralizedTypeId = nullptr;
+  for (const auto &Type : Types) {
+    if (Type->getNumOperands() == 2 && isa<MDString>(Type->getOperand(1))) {
+      auto *TMDS = cast<MDString>(Type->getOperand(1));
+      if (TMDS->getString().endswith("generalized")) {
+        MDGeneralizedTypeId = TMDS;
+        break;
+      }
+    }
+  }
+
+  if (!MDGeneralizedTypeId) {
+    errs() << "warning: can't find indirect target type id metadata "
+           << "for " << F.getName() << "\n";
+    return nullptr;
+  }
+
+  uint64_t TypeIdVal = llvm::MD5Hash(MDGeneralizedTypeId->getString());
+  Type *Int64Ty = Type::getInt64Ty(F.getContext());
+  return cast<ConstantInt>(ConstantInt::get(Int64Ty, TypeIdVal));
+}
+
+/// Emits call graph section.
+void AsmPrinter::emitCallGraphSection(const MachineFunction &MF,
+                                      FunctionInfo &FuncInfo) {
+  if (!MF.getTarget().Options.EmitCallGraphSection)
+    return;
+
+  // Switch to the call graph section for the function
+  MCSection *FuncCGSection =
+      getObjFileLowering().getCallGraphSection(*getCurrentSection());
+  assert(FuncCGSection && "null call graph section");
+  OutStreamer->pushSection();
+  OutStreamer->switchSection(FuncCGSection);
+
+  // Emit format version number.
+  OutStreamer->emitInt64(0);
+
+  // Emit function's self information, which is composed of:
+  //  1) FunctionEntryPc
+  //  2) FunctionKind: Whether the function is indirect target, and if so,
+  //     whether its type id is known.
+  //  3) FunctionTypeId: Emit only when the function is an indirect target
+  //     and its type id is known.
+
+  // Emit function entry pc.
+  const MCSymbol *FunctionSymbol = getFunctionBegin();
+  OutStreamer->emitSymbolValue(FunctionSymbol, TM.getProgramPointerSize());
+
+  // If this function has external linkage or has its address taken and
+  // it is not a callback, then anything could call it.
+  const Function &F = MF.getFunction();
+  bool IsIndirectTarget =
+      !F.hasLocalLinkage() || F.hasAddressTaken(nullptr,
+                                                /*IgnoreCallbackUses=*/true,
+                                                /*IgnoreAssumeLikeCalls=*/true,
+                                                /*IgnoreLLVMUsed=*/false);
+
+  // FIXME: FunctionKind takes a few values but emitted as a 64-bit value.
+  // Can be optimized to occupy 2 bits instead.
+  // Emit function kind, and type id if available.
+  if (!IsIndirectTarget) {
+    OutStreamer->emitInt64(FunctionInfo::FunctionKind::NOT_INDIRECT_TARGET);
+  } else {
+    const auto *TypeId = extractNumericCGTypeId(F);
+    if (TypeId) {
+      OutStreamer->emitInt64(
+          FunctionInfo::FunctionKind::INDIRECT_TARGET_KNOWN_TID);
+      OutStreamer->emitInt64(TypeId->getZExtValue());
+    } else {
+      OutStreamer->emitInt64(
+          FunctionInfo::FunctionKind::INDIRECT_TARGET_UNKNOWN_TID);
+    }
+  }
+
+  // Emit callsite labels, where each element is a pair of type id and
+  // indirect callsite pc.
+  const auto &CallSiteLabels = FuncInfo.CallSiteLabels;
+
+  // Emit the count of pairs.
+  OutStreamer->emitInt64(CallSiteLabels.size());
+
+  // Emit the type id and call site label pairs.
+  for (const std::pair<uint64_t, MCSymbol *> &El : CallSiteLabels) {
+    auto TypeId = El.first;
+    const auto &Label = El.second;
+    OutStreamer->emitInt64(TypeId);
+    OutStreamer->emitSymbolValue(Label, TM.getProgramPointerSize());
+  }
+  FuncInfo.CallSiteLabels.clear();
+
+  OutStreamer->popSection();
+}
+
 void AsmPrinter::emitPCSectionsLabel(const MachineFunction &MF,
                                      const MDNode &MD) {
   MCSymbol *S = MF.getContext().createTempSymbol("pcsection");
   OutStreamer->emitLabel(S);
   PCSectionsSymbols[&MD].emplace_back(S);
 }
 
 void AsmPrinter::emitPCSections(const MachineFunction &MF) {
void AsmPrinter::emitFunctionBody() {
   }
 
   // Print out code for the function.
   bool HasAnyRealCode = false;
   int NumInstsInFunction = 0;
   bool IsEHa = MMI->getModule()->getModuleFlag("eh-asynch");
 
   bool CanDoExtraAnalysis = ORE->allowExtraAnalysis(DEBUG_TYPE);
+  FunctionInfo FuncInfo;
+  const auto &CallSitesInfoMap = MF->getCallSitesInfo();
   for (auto &MBB : *MF) {
     // Print a label for the basic block.
     emitBasicBlockStart(MBB);
     DenseMap<StringRef, unsigned> MnemonicCounts;
     for (auto &MI : MBB) {
       // Print the assembly for the instruction.
       if (!MI.isPosition() && !MI.isImplicitDef() && !MI.isKill() &&
           !MI.isDebugInstr()) {
for (auto &MI : MBB) {
           MCI.setOpcode(MI.getOpcode());
           auto Name = OutStreamer->getMnemonic(MCI);
           auto I = MnemonicCounts.insert({Name, 0u});
           I.first->second++;
         }
         break;
       }
 
+      // FIXME: Some indirect calls can get lowered to jump instructions,
+      // resulting in emitting labels for them. The extra information can
+      // be neglected while disassembling but still takes space in the binary.
+      if (TM.Options.EmitCallGraphSection && MI.isCall()) {
+        // Only indirect calls have type identifiers set.
+        const auto &CallSiteInfo = CallSitesInfoMap.find(&MI);
+        if (CallSiteInfo != CallSitesInfoMap.end()) {
+          if (auto *TypeId = CallSiteInfo->second.TypeId) {
+            // Emit label.
+            MCSymbol *S = MF->getContext().createTempSymbol();
+            OutStreamer->emitLabel(S);
+
+            // Get type id value.
+            uint64_t TypeIdVal = TypeId->getZExtValue();
+
+            // Add to function's callsite labels.
+            FuncInfo.CallSiteLabels.emplace_back(TypeIdVal, S);
+          }
+        }
+      }
       // If there is a post-instruction symbol, emit a label for it here.
       if (MCSymbol *S = MI.getPostInstrSymbol())
         OutStreamer->emitLabel(S);
 
       for (const HandlerInfo &HI : Handlers) {
         NamedRegionTimer T(HI.TimerName, HI.TimerDescription, HI.TimerGroupName,
                            HI.TimerGroupDescription, TimePassesIsEnabled);
         HI.Handler->endInstruction();
if (MF->hasBBLabels() && HasAnyRealCode)
     emitBBAddrMapSection(*MF);
 
   // Emit sections containing instruction and function PCs.
   emitPCSections(*MF);
 
   // Emit section containing stack size metadata.
   emitStackSizeSection(*MF);
 
+  // Emit section containing call graph metadata.
+  emitCallGraphSection(*MF, FuncInfo);
+
   // Emit .su file containing function stack size information.
   emitStackUsage(*MF);
 
   emitPatchableFunctionEntries();
 
   if (isVerbose())
     OutStreamer->getCommentOS() << "-- End function\n";
 
void AsmPrinter::SetupMachineFunction(MachineFunction &MF) {
   CurrentSectionBeginSym = nullptr;
   MBBSectionRanges.clear();
   MBBSectionExceptionSyms.clear();
   bool NeedsLocalForSize = MAI->needsLocalForSize();
   if (F.hasFnAttribute("patchable-function-entry") ||
       F.hasFnAttribute("function-instrument") ||
       F.hasFnAttribute("xray-instruction-threshold") ||
       needFuncLabels(MF) || NeedsLocalForSize ||
-      MF.getTarget().Options.EmitStackSizeSection || MF.hasBBLabels()) {
+      MF.getTarget().Options.EmitStackSizeSection ||
+      MF.getTarget().Options.EmitCallGraphSection || MF.hasBBLabels()) {
     CurrentFnBegin = createTempSymbol("func_begin");
     if (NeedsLocalForSize)
       CurrentFnSymForSize = CurrentFnBegin;
   }
 
   ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
 }
 

llvm/lib/MC/MCObjectFileInfo.cpp

StackMapSection =
       Ctx->getELFSection(".llvm_stackmaps", ELF::SHT_PROGBITS, ELF::SHF_ALLOC);
 
   FaultMapSection =
       Ctx->getELFSection(".llvm_faultmaps", ELF::SHT_PROGBITS, ELF::SHF_ALLOC);
 
   EHFrameSection =
       Ctx->getELFSection(".eh_frame", EHSectionType, EHSectionFlags);
 
+  CallGraphSection = Ctx->getELFSection(".callgraph", ELF::SHT_PROGBITS, 0);
+
   StackSizesSection = Ctx->getELFSection(".stack_sizes", ELF::SHT_PROGBITS, 0);
 
   PseudoProbeSection = Ctx->getELFSection(".pseudo_probe", DebugSecType, 0);
   PseudoProbeDescSection =
       Ctx->getELFSection(".pseudo_probe_desc", DebugSecType, 0);
 
   LLVMStatsSection = Ctx->getELFSection(".llvm_stats", ELF::SHT_PROGBITS, 0);
 }
case Triple::UnknownObjectFormat:
     report_fatal_error("Cannot get DWARF comdat section for this object file "
                        "format: not implemented.");
     break;
   }
   llvm_unreachable("Unknown ObjectFormatType");
 }
 
 MCSection *
+MCObjectFileInfo::getCallGraphSection(const MCSection &TextSec) const {
+  if (Ctx->getObjectFileType() != MCContext::IsELF)
+    return CallGraphSection;
+
+  const MCSectionELF &ElfSec = static_cast<const MCSectionELF &>(TextSec);
+  unsigned Flags = ELF::SHF_LINK_ORDER;
+  StringRef GroupName;
+  if (const MCSymbol *Group = ElfSec.getGroup()) {
+    GroupName = Group->getName();
+    Flags |= ELF::SHF_GROUP;
+  }
+
+  return Ctx->getELFSection(".callgraph", ELF::SHT_PROGBITS, Flags, 0,
+                            GroupName, true, ElfSec.getUniqueID(),
+                            cast<MCSymbolELF>(TextSec.getBeginSymbol()));
+}
+
+MCSection *
 MCObjectFileInfo::getStackSizesSection(const MCSection &TextSec) const {
   if ((Ctx->getObjectFileType() != MCContext::IsELF) ||
       Ctx->getTargetTriple().isPS4())
     return StackSizesSection;
 
   const MCSectionELF &ElfSec = static_cast<const MCSectionELF &>(TextSec);
   unsigned Flags = ELF::SHF_LINK_ORDER;
   StringRef GroupName;

llvm/test/CodeGen/call-graph-section.ll

+; Tests that we store the type identifiers in .callgraph section of the binary.
+
+; RUN: llc --call-graph-section -filetype=obj -o - < %s | \
+; RUN: llvm-readelf -x .callgraph - | FileCheck %s
+
+target triple = "x86_64-unknown-linux-gnu"
+
+define dso_local void @foo() #0 !type !4 {
+entry:
+  ret void
+}
+
+define dso_local i32 @bar(i8 signext %a) #0 !type !5 {
+entry:
+  %a.addr = alloca i8, align 1
+  store i8 %a, i8* %a.addr, align 1
+  ret i32 0
+}
+
+define dso_local i32* @baz(i8* %a) #0 !type !6 {
+entry:
+  %a.addr = alloca i8*, align 8
+  store i8* %a, i8** %a.addr, align 8
+  ret i32* null
+}
+
+define dso_local i32 @main() #0 !type !7 {
+entry:
+  %retval = alloca i32, align 4
+  %fp_foo = alloca void (...)*, align 8
+  %a = alloca i8, align 1
+  %fp_bar = alloca i32 (i8)*, align 8
+  %fp_baz = alloca i32* (i8*)*, align 8
+  store i32 0, i32* %retval, align 4
+  store void (...)* bitcast (void ()* @foo to void (...)*), void (...)** %fp_foo, align 8
+  %0 = load void (...)*, void (...)** %fp_foo, align 8
+  call void (...) %0() [ "type"(metadata !"_ZTSFvE.generalized") ]
+  store i32 (i8)* @bar, i32 (i8)** %fp_bar, align 8
+  %1 = load i32 (i8)*, i32 (i8)** %fp_bar, align 8
+  %2 = load i8, i8* %a, align 1
+  %call = call i32 %1(i8 signext %2) [ "type"(metadata !"_ZTSFicE.generalized") ]
+  store i32* (i8*)* @baz, i32* (i8*)** %fp_baz, align 8
+  %3 = load i32* (i8*)*, i32* (i8*)** %fp_baz, align 8
+  %call1 = call i32* %3(i8* %a) [ "type"(metadata !"_ZTSFPvS_E.generalized") ]
+  call void @foo() [ "type"(metadata !"_ZTSFvE.generalized") ]
+  %4 = load i8, i8* %a, align 1
+  %call2 = call i32 @bar(i8 signext %4) [ "type"(metadata !"_ZTSFicE.generalized") ]
+  %call3 = call i32* @baz(i8* %a) [ "type"(metadata !"_ZTSFPvS_E.generalized") ]
+  ret i32 0
+}
+
+attributes #0 = { noinline nounwind optnone uwtable "frame-pointer"="all" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
+
+!llvm.module.flags = !{!0, !1, !2}
+!llvm.ident = !{!3}
+
+; Check that the numeric type id (md5 hash) for the below type ids are emitted
+; to the callgraph section.
+
+; CHECK: Hex dump of section '.callgraph':
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{i32 7, !"uwtable", i32 1}
+!2 = !{i32 7, !"frame-pointer", i32 2}
+!3 = !{!"clang version 13.0.0 ([e-mail]:llvm/llvm-project.git 6d35f403b91c2f2c604e23763f699d580370ca96)"}
+; CHECK-DAG: 2444f731 f5eecb3e
+!4 = !{i64 0, !"_ZTSFvE.generalized"}
+; CHECK-DAG: 5486bc59 814b8e30
+!5 = !{i64 0, !"_ZTSFicE.generalized"}
+; CHECK-DAG: 7ade6814 f897fd77
+!6 = !{i64 0, !"_ZTSFPvS_E.generalized"}
+; CHECK-DAG: caaf769a 600968fa
+!7 = !{i64 0, !"_ZTSFiE.generalized"}