Page MenuHomePhabricator

Heat Coloring for CFGPrinter and CallPrinter
AbandonedPublic

Authored by knaumov on Jan 21 2020, 2:25 PM.

Details

Summary

Extends the CFGPrinter and CallPrinter with heat colors based on heuristics or profiling information.

This patch was firstly published by Rodrigo Caetano Rocha (@rcorcs) on 11/24/17. After several rounds of reviews, it was deployed, but, mainly due to the conflict with Polly, it was reverted. After that, the conflict with Polly alongside some other small issues was fixed, but never deployed. The diff then was closed due to the commit that probably happened during migration. I would like to bring this change upstream. I have taken it up to me to make some changes regarding flags initialization and refactoring some older tests to match the new output of CFGPrinter specifically. All the further info on the patch you can find in the previous reviews.

Initial diff: reviews.llvm.org/D40425
First commit: reviews.llvm.org/rL335996
Revert commit: reviews.llvm.org/rL336000
Polly fix: reviews.llvm.org/D49154

Diff Detail

Event Timeline

knaumov created this revision.Jan 21 2020, 2:25 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 21 2020, 2:25 PM
davidxl added inline comments.Jan 28 2020, 10:00 AM
llvm/lib/Analysis/HeatUtils.cpp
40

You can use ProfileSummaryInfo::hasProfileSummary interface.

67

parameter not used

68

clang-format

74

The function entry count should have the information

100

for the program's max count, max function count, get it from ProfileSummaryInfo.

I'm embarrassed to say I though the old patches landed after the Polly fix, so I really appreciate you taking the time to update the patches.

I've added a few comments to start/ One thing I would suggest is running clang-format over all the changes.

llvm/include/llvm/Analysis/CFGPrinter.h
260–263

Minor nit: Fix the extra white space.

268

Remove extra blank line.

277

const unsigned MaxEdgeWidth = 2
so shouldn't this just be double Width = 1.0 + WeightPercent;

279

Can we convert the else block into an early return instead -->

if (!CFGInfo->useRawEdgeWeights())
  return formatv("label=\"{0:P}\" penwidth={1}", WeightPercent, Width).str();
knaumov updated this revision to Diff 242186.EditedFeb 3 2020, 2:24 PM
knaumov marked 8 inline comments as done.

Addressed @davidxl and @sfertile comments.

Answering @davidxl 's comment on "The function entry count should have the information", line 73, HeatUtils.cpp:
This function counts the number of calls of one specific function by another specific function while Function.entryCount() returns number entries for this function.

Answering @davidxl 's comment on "for the program's max count, max function count, get it from ProfileSummaryInfo.", line 99, HeatUtils.cpp:
ProfileSummaryInfo doesn't contain info on the maximum frequency in the module, it needs to be calculated.

Updates:

  • Ran clang-format through all the files
  • Deleted some function which had no use (see hasProfiling function)
  • Deleted const unsigned variables
knaumov marked an inline comment as done.Feb 13 2020, 6:52 AM

ping

Addressed @davidxl and @sfertile comments.

Answering @davidxl 's comment on "The function entry count should have the information", line 73, HeatUtils.cpp:
This function counts the number of calls of one specific function by another specific function while Function.entryCount() returns number entries for this function.

Answering @davidxl 's comment on "for the program's max count, max function count, get it from ProfileSummaryInfo.", line 99, HeatUtils.cpp:
ProfileSummaryInfo doesn't contain info on the maximum frequency in the module, it needs to be calculated.

Updates:

  • Ran clang-format through all the files
  • Deleted some function which had no use (see hasProfiling function)
  • Deleted const unsigned variables

The max count info from a module can be misleading. The module itself in most of the cases are cold, so profile summary should be used for cases when profile data is available.

Another major issue is that when real profile is not available (when heurstic is used), the blockfrequency value is relative to the a function, so you can not really compare block frequency values across function boundaries. For that, a round of synthetic profile count propagation is needed.

llvm/lib/Analysis/CallPrinter.cpp
37

By looking at the code, it seems that the difference of 'full' vs 'nonfull' is a whether it is a multi-graph or not.

75

How can this be? The caller of the callsite can not be a declaration.

knaumov updated this revision to Diff 246262.Feb 24 2020, 11:22 AM

Changes:

  • Renamed a flag ("callgraph-full" -> "call-multigraph") to reflect its purpose more clearly
  • Removed unnecessary if-check
  • General refactoring and restructuring
  • Removed useHeuristic from the code - from the structure of the code it is vivid that useHeuristic variable used in getMaxFreq functions is always set to "true" and never becomes "false".

Addressing @davidxl 's comments:
ProfileSummaryInfo class will not be useful in this problem as it only gives the result on
whether the BB or the Function is hot or cold, without information on how hot or cold
it is when compared to the other BBs or Functions.
On the other hand, I agree with the fact that comparing local maximum BB frequencies
in function throughout the module is useless and can be misleading. However, I don't
see any "nice" way out of that, as the solution that you suggested (SyntheticCountsPropagation pass)
involves altering the module which should be avoided in a diagnostical pass. Also, as CallGraphs
are printed per function, there is no worry that the colors are going to be somewhat misleading.

Since it is meaningless to compare blockfrequency across function boundaries (and computing module max): the following can be done

  1. when profile is available, try to compute max block count (actual profile count) per module
  2. when profile is not available, try to do function scope heat coloring only.
knaumov updated this revision to Diff 246543.Feb 25 2020, 12:40 PM
  • Removed flag that was targeting coloring BB based on their relative hotness across the module.

I have decided to do that for the following reasons:

  1. The patch is self-contained without this feature. This feature can be added in a follow-up patch.
  2. The feature itself is not as important and valuable as was first thought of.

My suggestions for implementing this feature:
Although we only have a relative frequency of BB with respect to the function, using the relative frequency of a function with respect to the module we can translate it to be relative to the module. We can do that using ProfileSummary to get the number of entries per a function.

knaumov updated this revision to Diff 247362.Feb 28 2020, 1:40 PM
knaumov marked 2 inline comments as done.

Fixes:

  • Restoring the effect of clang-format

The effect of clang-format was restored for better readability of the patch

  • Deleted Heuristic fully

As I said in the previous diffs, Heuristic bool was always true and never changing.

  • Transferred CFGPrinter back to Function Pass

The patch was made module in order to implement the comparison between BB across functions. As this patch is not targeting this behavior, the pass was decided to remain Function Pass

  • Small stylistics changes

is there call graph related test case?

Also some sample output file of the CFG and CallGraph with heat color will be helpful.

llvm/include/llvm/Analysis/HeatUtils.h
29

Add documentation.

33

add documentation. Similarly for other interfaces.

llvm/lib/Analysis/CallPrinter.cpp
87

this quadratic behavior.

knaumov updated this revision to Diff 248787.Mar 6 2020, 10:20 AM

Fixes:

  • Added documentation to the new functions
  • Added two test cases - one for multigraph, the second one for heat CallGraph/CFG specifically
  • Reduced the quadratic behavior that was mentioned by @davidxl . There is no way to reduce the behavior to smaller than O(n^2), but I've made it to (n^2)/2. There is no need to go beyond this as this is just a debugging feature that is not to be used outside of debugging.

Also, I am attaching two samples of heat coloring - CFG and CallGraph.


The cfg example (and pdf) looks great. However the callgraph example looks not quite right. Can you provide the test_for_loop.ll file as well? thanks.

If you split the CFG part of the changes into a separate patch, I think it is almost in good shape to land first.

knaumov abandoned this revision.Jun 16 2020, 2:40 PM
knaumov marked 3 inline comments as done.

All of the related patches were successfully reviewed and landed!
Thanks to everyone who has participated in this long journey!