This is an archive of the discontinued LLVM Phabricator instance.

[AsmPrinter][CallGraphSection] Emit call graph section
Needs ReviewPublic

Authored by Prabhuk on Jul 13 2021, 10:38 AM.

Details

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

Diff Detail

Event Timeline

necipfazil created this revision.Jul 13 2021, 10:38 AM
necipfazil requested review of this revision.Jul 13 2021, 10:38 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 13 2021, 10:39 AM

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

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.

necipfazil marked 8 inline comments as done.Jul 17 2021, 8:51 PM

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
1747
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 added inline comments.Jul 18 2021, 2:25 PM
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 added inline comments.Jul 19 2021, 2:22 PM
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.

lattner resigned from this revision.Jul 21 2021, 7:59 AM
necipfazil marked 11 inline comments as done.

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.

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

This revision is now accepted and ready to land.Jul 22 2021, 9:24 AM
MaskRay requested changes to this revision.Jul 22 2021, 12:51 PM
MaskRay added inline comments.
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.

This revision now requires changes to proceed.Jul 22 2021, 12:51 PM
necipfazil added inline comments.Jul 22 2021, 1:18 PM
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 added inline comments.Jul 22 2021, 1:35 PM
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 marked 4 inline comments as done.

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?

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 accepted this revision.Jul 29 2021, 2:01 PM
morehouse added inline comments.
llvm/include/llvm/CodeGen/AsmPrinter.h
200
necipfazil marked an inline comment as done.

ADd further docs for FunctionKind

Could you please take another look, @MaskRay?

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

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.

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.

Herald added a project: Restricted Project. · View Herald TranscriptWed, Nov 22, 1:52 PM
Prabhuk updated this revision to Diff 558149.Wed, Nov 22, 2:02 PM

Rebased the patchset and addressed the compilation failures.

Prabhuk updated this revision to Diff 558157.Wed, Nov 22, 2:16 PM

Rebased the patchset and addressed the compilation failures

phosek added a subscriber: phosek.Mon, Nov 27, 9:53 AM

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.