[AsmPrinter][CallGraphSection] Emit call graph section

[Prabhuk]

Summary

Collect the necessary information for constructing the call graph section, and
emit to .callgraph section of the binary.

Numeric type identifiers for indirect calls and targets are computed from type
identifiers passed from clang front-end.

CGSectionFuncComdatCreator pass is used to create comdats for functions whose
symbols will be referenced from the call graph section. A call graph section
is created per function group, and is linked to the relevant function. This
enables dead-stripping of call graph symbols if linked function gets removed.

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]

The AsmPrinter stuff seems overly complicated by a non-optimal data structure choice.

Rather than two maps (FuncEntryLabels, CallSiteLabels) that get rearranged later, how about a single structure that captures the grouping we want?
Something like:

struct FunctionInfo {
  MCSymbol *EntryLabel;  // nullptr if this function is not a potential indirect target
  DenseMap<CGTypeId, MCSymbol *> CallSiteLabels;
};
DenseMap<Function *, FunctionInfo> FunctionLabels;

Then we can simply iterate this structure once to emit the call graph sections. Inside the loop we can obtain the section for the current Function * key, compute its type ID if EntryLabel != nullptr, and emit the appropriate labels.
I think this would cut out a lot of code.

llvm/include/llvm/CodeGen/AsmPrinter.h

909

I'm a little confused since FuncEntryLabels and CallSiteLabels are class members that I wouldn't expect need to be passed as parameters. But the types are different here.

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1601

Nit: El.second.first and El.second.second seem clearer to me.

1613

This is confusing since we now have both a type and a variable named Labels.

1618

This whole loop seems a little pointless. We're copying from a Func -> TypeId -> Labels map to a FuncSection -> TypeId -> Labels map. Where FuncSection is directly attainable if we have Func.

Actually, the other loop also seems unnecessary. It is restructuring from Func -> {TypeId, Label} map to a FuncSection -> TypeId -> Label map.

1716

Interesting. So metadata persists on functions all the way to asm printing? Do any LLVM optimizations drop this metadata?

1734

Can we share this logic with MachineFunction.h?

1751

Why is it safe to ignore callbacks?

1760–1761

1768–1769

1861

1866

[necipfazil]

Adapt to new call graph section layout, no longer use comdats

• Emit the call graph section following the new call graph section layout.
• No longer use comdats. Instead, use only SHF_LINK_ORDER to link call graph sections to function symbols.
• The code is refactored with usage of better data-structures. This increased the readability and the efficiency.

https://reviews.llvm.org/D105909 switches to using operand bundles for propagating indirect callsite type ids. When a C/C++ source is compiled to llvm assembly (.ll) using clang -fcall-graph-section, then to object file using llc --call-graph-section, an error is raised due to using metadata as operand bundles value. This is further explained in the test case coming with this revision. The test case is marked as expected fail. This issue will be shortly addressed. Though, it is not clear if the issue is due to the call graph section implementation or llc.
Otherwise, when a C/C++ source is directly compiled to an object file with clang -fcall-graph-section, no issues appear.

[MaskRay]

The usage is similar to .stack_sizes (metadata section not referenced by text) , so SHF_LINK_ORDER suffices, no need for comdat noduplicates.

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1586

expand auto https://llvm.org/docs/CodingStandards.html#use-auto-type-deduction-to-make-code-more-readable

1747

expand auto

https://llvm.org/docs/CodingStandards.html#use-auto-type-deduction-to-make-code-more-readable

1751

clang-format and clang-tidy bugprone-argument-comment prefer /*IgnoreCallbackUses=*/true

llvm/lib/MC/MCObjectFileInfo.cpp

1100

Use the style of getStackSizesSection. Pass in the MCSection &TextSec, and do SHF_LINK_ORDER/SHF_GROUP here, instead of at the call site.

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

6

Why is this XFAIL?

[MaskRay]

llvm/include/llvm/CodeGen/AsmPrinter.h

210

unstable iteration order. may consider MapVector https://llvm.org/docs/ProgrammersManual.html#llvm-adt-mapvector-h

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1529

unstable iteration order

[morehouse]

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1537

Pushing the section without popping it later seems wrong.

If we don't need push/pop, let's not use it. Otherwise, let's put it outside the loop.

1565

I don't think we need to share it anymore, since the only use is here.

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

6

Yes, we should figure this out before landing. Probably we need to fix an assumption in the llc parser that no longer holds due to the new operand bundle type.

[necipfazil]

Fix creating call graph section

• For call graph section, set SHF_GROUP if the text section has.
• Remove XFAIL from test. A seperate revision to fix llc will be sent.
• Fix nits.

llvm/include/llvm/CodeGen/AsmPrinter.h

210

We iterate over FunctionLabels only once when emitting the labels, and do not mutate the map while so.

If there is no other specific reason, we may keep using DenseMap as there is no need for emitting the functions in a certain order.

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1716

Based on the experiments with SPEC CPU2006 483.xalancbmk, no metadata was dropped for -O{0,1,2,3}. However, I have no additional evidence to support whether the metadata is guaranteed to be preserved for functions.

Besides this, the current implementation does not set metadata for some functions in the first place. These include compiler intrinsics like __clang_call_terminate, asan.module_ctor, _GLOBAL__sub_I_*. I have no other solution than handling these per-case at where LLVM functions are created for these. I will look into them shortly. On the other hand, these functions are not interesting for our use case.

To cover for all, the layout supports listing indirect targets with unknown type ids. We use it when we capture the indirect-targetness at the back-end, yet cannot find any type id metadata.

llvm/lib/MC/MCObjectFileInfo.cpp

1100

I am not sure if I understand this. We need the function symbol for creating the section, to which we will link the section. I am already doing SHF_LINK_ORDER at getCallGraphSection. Could you please elaborate?

Update:
@MaskRay, thanks for elaborating this per my help request in a chat. Per your suggestion, getCallGraphSection now sets SHF_GROUP in the text section by passing the text section as parameter.

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

6

I have fix for llc that I will shortly push with another revision.

Besides, XFAIL is now removed.

[necipfazil]

D106523 fixes the issue with llc by parsing metadata value from operand bundles. The test case will pass with this fix.

[morehouse]

LGTM

[MaskRay]

llvm/include/llvm/CodeGen/AsmPrinter.h

210

there is no need for emitting the functions in a certain order.

The compiler must enforce an order for reproducible builds. Non-determinism is bad for build cache.

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1556

Move this outside and make it clear that the section consumer needs to synchronize with the values.

1590

Perhaps consider a compact style where you place comments on the right side of the code.

llvm/lib/MC/MCObjectFileInfo.cpp

1133

getStackSizesSection uses getBeginSYmbol on TextSec.

[necipfazil]

llvm/lib/MC/MCObjectFileInfo.cpp

1133

Could you please provide more information on the requested change?

When the section is linked to getBeginSymbol(TextSec) (i.e., getBeginSymbol(TextSec) is passed as the last argument to getELFSection() call), we still experience issues with garbage collection:

`.text.FUNCNAME' referenced in section `.callgraph' of OBJFILE.o: defined in discarded section

Therefore, I am passing function symbol as parameter to getCallGraphSection() so that we can link the newly created section to it.

Where else do we need to use getBeginSymbol()?

[MaskRay]

llvm/lib/MC/MCObjectFileInfo.cpp

1133

You may need to provide instructions to reproduce the linker error.

The .stack_sizes scheme definitely works. If not, the current code must miss some stuff.

[necipfazil]

Several fixes and refactoring

• Emit call graph section per function right after the function information is gathered rather than collection all and emitting once. This simplifies the code with less book keeping. Also, emitting the section at AsmPrinter::doFinalization() was wrong, leading to linker issues when section is not linked with function symbol.
• Use function begin symbol as function entry label in call graph section. Avoid emitting yet another temp symbol.
• Fix MCObjectFileInfo::getCallGraphSection(). Create section based on text section instead of the function symbol.
• Move FunctionKind to AsmPrinter::FunctionInfo to make the FunctionKind values clear to call graph section consumers.
• Propagate some more call graph section logic from AsmPrinter::emitFunctionBody() to AsmPrinter::emitCallGraphSection(). This also means less bookkeeping in AsmPrinter::FunctionInfo.

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1556

Done. Please see AsmPrinter::FunctionInfo.

llvm/lib/MC/MCObjectFileInfo.cpp

1133

Thanks for the clarifications.

Looks like emitting call graph section later in AsmPrinter::doFinalization() was the issue.

MCObjectFileInfo::getCallGraphSection() now has almost the same logic as MCObjectFileInfo::getStackSizesSection(), with only difference at the section name. Do we need to share logic between two?

[necipfazil]

Add function begin symbol for call graph section if does not exist

A function begin symbol is not always emitted. Similar to how it is done
for stack sizes section, emit a function begin symbol for call graph section
if it does not already exist.

[morehouse]

llvm/include/llvm/CodeGen/AsmPrinter.h

200

[necipfazil]

ADd further docs for FunctionKind

[necipfazil]

Could you please take another look, @MaskRay?

Tomorrow is the last day of my internship. I would like to address any issues before then.

[MaskRay]

Tomorrow is the last day of my internship. I would like to address any issues before then.

You may continue working on this or ask mentors for help:)
I added some reviewers to your previous patches and made some comments by myself.
(But the important thing is that the duration of internship cannot be used to skip review process, especially for such a patch which needs to touch so many components in llvm-project.)

My feelings in https://reviews.llvm.org/D105907#2886280 still stand.
Perhaps naming the feature "indirect ..." is more suitable. People can likely get confused by the lack of direct call edges.

[necipfazil]

In D105916#2915350, @MaskRay wrote:

Tomorrow is the last day of my internship. I would like to address any issues before then.

You may continue working on this or ask mentors for help:)
I added some reviewers to your previous patches and made some comments by myself.
(But the important thing is that the duration of internship cannot be used to skip review process, especially for such a patch which needs to touch so many components in llvm-project.)

Contrary to the assumption, I would like to contribute as much as I can in the remaining time. Whether the review process is completed or not by then is irrelevant.

My feelings in https://reviews.llvm.org/D105907#2886280 still stand.
Perhaps naming the feature "indirect ..." is more suitable. People can likely get confused by the lack of direct call edges.

Thanks for your continued help. I will address the outstanding issues shortly.

[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.

[Prabhuk]

Rebased the patchset and addressed the compilation failures

[nickdesaulniers]

This smells a lot like https://clang.llvm.org/docs/SanitizerCoverage.html#tracing-control-flow. I wonder if any of that infra could be reused here?

We're encoding data into .callgraph; they are in sancov_cfs.

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.
private:
   // Internal Implementation Details
   //===------------------------------------------------------------------===//
 
   void emitJumpTableEntry(const MachineJumpTableInfo *MJTI,
                           const MachineBasicBlock *MBB, unsigned uid) const;
   void emitLLVMUsedList(const ConstantArray *InitList);
   /// Emit llvm.ident metadata in an '.ident' directive.
   void emitModuleIdents(Module &M);
   /// Emit bytes for llvm.commandline metadata.
   virtual void emitModuleCommandLines(Module &M);
 
   GCMetadataPrinter *getOrCreateGCPrinter(GCStrategy &S);
   void emitGlobalAlias(Module &M, const GlobalAlias &GA);
   void emitGlobalIFunc(Module &M, const GlobalIFunc &GI);
 
   /// This method decides whether the specified basic block requires a label.
   bool shouldEmitLabelForBasicBlock(const MachineBasicBlock &MBB) const;

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) {
   const Function &F = MF.getFunction();
   if (PCSectionsSymbols.empty() && !F.hasMetadata(LLVMContext::MD_pcsections))
     return;
 
   const CodeModel::Model CM = MF.getTarget().getCodeModel();
   const unsigned RelativeRelocSize =
       (CM == CodeModel::Medium || CM == CodeModel::Large) ? getPointerSize()
                                                           : 4;
 
   // Switch to PCSection, short-circuiting the common case where the current
   // section is still valid (assume most MD_pcsections contain just 1 section).
   auto SwitchSection = [&, Prev = StringRef()](const StringRef &Sec) mutable {
     if (Sec == Prev)
       return;
     MCSection *S = getObjFileLowering().getPCSection(Sec, MF.getSection());
     assert(S && "PC section is not initialized");
     OutStreamer->switchSection(S);
     Prev = Sec;
   };
   // Emit symbols into sections and data as specified in the pcsections MDNode.
   auto EmitForMD = [&](const MDNode &MD, ArrayRef<const MCSymbol *> Syms,
                        bool Deltas) {
     // Expect the first operand to be a section name. After that, a tuple of
     // constants may appear, which will simply be emitted into the current
static bool needFuncLabels(const MachineFunction &MF) {
   return !isNoOpWithoutInvoke(
       classifyEHPersonality(MF.getFunction().getPersonalityFn()));
 }
 
 /// EmitFunctionBody - This method emits the body and trailer for a
 /// function.
 void AsmPrinter::emitFunctionBody() {
   emitFunctionHeader();
 
   // Emit target-specific gunk before the function body.
   emitFunctionBodyStart();
 
   if (isVerbose()) {
     // Get MachineDominatorTree or compute it on the fly if it's unavailable
     MDT = getAnalysisIfAvailable<MachineDominatorTree>();
     if (!MDT) {
       OwnedMDT = std::make_unique<MachineDominatorTree>();
       OwnedMDT->getBase().recalculate(*MF);
       MDT = OwnedMDT.get();
     }
 
     // Get MachineLoopInfo or compute it on the fly if it's unavailable
     MLI = getAnalysisIfAvailable<MachineLoopInfo>();
     if (!MLI) {
       OwnedMLI = std::make_unique<MachineLoopInfo>();
       OwnedMLI->getBase().analyze(MDT->getBase());
       MLI = OwnedMLI.get();
     }
   }
 
   // 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()) {
         HasAnyRealCode = true;
         ++NumInstsInFunction;
       }
 
       // If there is a pre-instruction symbol, emit a label for it here.
       if (MCSymbol *S = MI.getPreInstrSymbol())
         OutStreamer->emitLabel(S);
 
       if (MDNode *MD = MI.getPCSections())
         emitPCSectionsLabel(*MF, *MD);
 
       for (const HandlerInfo &HI : Handlers) {
         NamedRegionTimer T(HI.TimerName, HI.TimerDescription, HI.TimerGroupName,
                            HI.TimerGroupDescription, TimePassesIsEnabled);
         HI.Handler->beginInstruction(&MI);
       }
 
       if (isVerbose())
         emitComments(MI, OutStreamer->getCommentOS());
 
       switch (MI.getOpcode()) {
       case TargetOpcode::CFI_INSTRUCTION:
         emitCFIInstruction(MI);
         break;
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);
 }

 }
 
 MCSection *MCObjectFileInfo::getDwarfComdatSection(const char *Name,
                                                    uint64_t Hash) const {
   switch (Ctx->getTargetTriple().getObjectFormat()) {
   case Triple::ELF:
     return Ctx->getELFSection(Name, ELF::SHT_PROGBITS, ELF::SHF_GROUP, 0,
                               utostr(Hash), /*IsComdat=*/true);
   case Triple::Wasm:
     return Ctx->getWasmSection(Name, SectionKind::getMetadata(), 0,
                                utostr(Hash), MCContext::GenericSectionID);
   case Triple::MachO:
   case Triple::COFF:
   case Triple::GOFF:
   case Triple::SPIRV:
   case Triple::XCOFF:
   case Triple::DXContainer:
   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"}