Page MenuHomePhabricator

[llvm][Instrumentation] Add Call Graph Profile pass

Authored by Bigcheese on Jun 12 2018, 4:03 PM.



This patch adds support for generating a call graph profile from Branch Frequency Info.

Generating the CG Profile

The CGProfile module pass simply gets the block profile count for each BB and scans for call instructions. For each call instruction it adds an edge from the current function to the called function with the current BB block profile count as the weight.

After scanning all the functions, it generates an appending module flag containing the data. The format looks like:

!llvm.module.flags = !{!0} 
!0 = !{i32 5, !"CG Profile", !1} 
!1 = !{!2, !3, !4} ; List of edges
!2 = !{void ()* @a, void ()* @b, i64 32} ; Edge from a to b with a weight of 32
!3 = !{void (i1)* @freq, void ()* @a, i64 11} 
!4 = !{void (i1)* @freq, void ()* @b, i64 20}

Diff Detail

Event Timeline

Bigcheese created this revision.Jun 12 2018, 4:03 PM
compnerd added inline comments.Jun 12 2018, 8:31 PM

Can this not be const auto &F : M?


Can this not be const auto &BB : F?


Can this not be const auto &I : BB?

Bigcheese marked 2 inline comments as done.

Address review comments by adding const where applicable.


No, because of getAnalysis.

compnerd accepted this revision.Jun 13 2018, 1:33 PM

I assume that there is/will be a different change to the frontend to enable this for users?


Probably would be nice to hoist the Streamer.getContext() out of the loop.

auto &C = Streamer.getContext();

Would be nice to move this (L75-88) into a helper function (UpdateModuleMetadata?)

This revision is now accepted and ready to land.Jun 13 2018, 1:33 PM
Bigcheese updated this revision to Diff 151265.Jun 13 2018, 3:45 PM
Bigcheese marked 2 inline comments as done.
Bigcheese edited the summary of this revision. (Show Details)

Address review comments.

Change to using ValueAsMetadata instead of strings and add a check to the verifier.

This is enabled by default as the time and size overhead is so small.

Bigcheese updated this revision to Diff 151266.Jun 13 2018, 3:47 PM

Use the correct diff.

compnerd accepted this revision.Jun 20 2018, 9:36 PM

Thanks for the changes!

This revision was automatically updated to reflect the committed changes.

This patch totally fell out of my radar. I will take a closer look at it.

I am with Chandler here. Adding this pass to the legacy PM only will slow down the eventual migration to the new PM. It is better to do the new PM or both.

52 ↗(On Diff #152406)

You can check the existence of function entry count to decide whether to skip function earlier.

61 ↗(On Diff #152406)

Use CallSite interface instead so that InvokeInst is handled as well:

CallSite CS(&I);
 if (!CS) continue;

Chandler has plan to unify the CallInst and InvokeInst in the future, but for now, CallSIte is the way to go.

65 ↗(On Diff #152406)

you may want to check TTI to see if isLoweredToCall returns true.

68 ↗(On Diff #152406)

You may also check indirect callsite to see if it has value profile data (indirect call target). If it has, you can create edges to the targets as well.

(I assume this information is for function layout purpose by the linker).

I had to revert this because the embedded function analysis runner inside the legacy pass manager for module passes appears to leak. =/ At least we found LeakSanitizer reports on the bots because of this commit.

Up to you whether you want to try and fix LegacyPM here or just switch to working on this w/ the new PM.

Bigcheese updated this revision to Diff 152826.Jun 25 2018, 7:40 PM
Bigcheese marked 3 inline comments as done.
  • Move to new PM
  • Use CallSite
  • Bail early if no profile counts
  • Use TargetTransformInfo::isLoweredToCall
68 ↗(On Diff #152406)

Is there an example where this is used? I'm not familiar with value profile data.

The interface to get indirect call target value profile is bool getValueProfDataFromInst. See how it is used in ICallPromotionAnalysis::getPromotionCandidatesForInstruction(..) method.

Bigcheese updated this revision to Diff 152983.Jun 26 2018, 3:27 PM

Add support for indirect calls using value profiling data.

davidxl added inline comments.Jun 26 2018, 3:36 PM

The lowering check and count update code is shared between indirect and direct calls, so perhaps add a helper lambda function for it?

Bigcheese updated this revision to Diff 152985.Jun 26 2018, 3:51 PM
Bigcheese marked an inline comment as done.

Remove duplication on updating Counts.

vasich added a subscriber: vasich.Jul 2 2018, 3:58 AM