Page MenuHomePhabricator

Heat Coloring (3/3): Adding Heat Functionality to CallPrinter
ClosedPublic

Authored by knaumov on Mar 31 2020, 1:56 PM.

Details

Summary

This patch is the third in the sequence of three patches related to the following diff (https://reviews.llvm.org/D73142). The first patch from the sequence that has introduced the structure for DOTFunction Information is found here - D76820. The second patch introduced similar functionality to the CFG - (D77161). This patch introduces the heat coloring of the CallPrinter which is based on the relative "hotness" of each function. All the functionality of this patch was developed and discussed in the preceding patches.

Diff Detail

Event Timeline

knaumov created this revision.Mar 31 2020, 1:56 PM
knaumov updated this revision to Diff 256594.Apr 10 2020, 9:56 AM

Transferred the getNumOfCalls functions from the previous review.

Can you also provide the test_for_loop.ll (perhaps as a test case?) which correspond to the pdf file attached to the original patch?

llvm/lib/Analysis/CallPrinter.cpp
38

callgraph-multigraph to be consistent with other option names

42

to be consistent with naming convention in PGO, perhaps use 'callgraph-entry-count'

knaumov updated this revision to Diff 257116.Apr 13 2020, 2:42 PM

Answering @davidxl 's comments:

  • Renamed flags

Attaching the file test_heat.ll for which the .pdf from the original patch was created:


Where do you want me to put it?

knaumov updated this revision to Diff 257118.Apr 13 2020, 2:44 PM

The wrong diff uploaded previously, reupload

Looked at the example .ll file for good_callgraph.pdf -- they don't seem to match. There is no callgraph edge from bar1 to bar2, but the pdf file shows there is one. Similarly for other edges between bar* functions.

knaumov updated this revision to Diff 258840.Apr 20 2020, 2:10 PM
  • Changed the flag in the test

Indeed, sorry, wrong .ll test.
This one should be the one:

The call edges now look correct, but the resulting hotness does not look right. The caller 'foo' is marked as hot with red color, but hot callees like 'bar1' etc in the loop are not (Note that the branches in the loop are not highly biased).

knaumov updated this revision to Diff 261463.May 1 2020, 8:46 AM
knaumov marked 2 inline comments as done.
  • Fixed the functionality of heat coloring - now the coloring of CallGraph is done by analyzing how many times the given function was called. The more times it's being called - the hotter ("redder") it will be on the graph.
Herald added a project: Restricted Project. · View Herald TranscriptMay 1 2020, 8:46 AM

Can you also upload the graph with the fix?

This Callgraph was generated from test_heat.ll
You can see, as foo is not being called by anyone, it is marked as the coldest block. Bar functions are ranked from the least number to the greatest by their hotness which makes sense - whenever function bar1 is called, it is calling all of the other bars that follow and so on. Thus, bar5 is the hottest function in the .ll file

thanks. The example graph looks great. Will take a look at the patch in details soon.

davidxl added inline comments.May 5 2020, 2:36 PM
llvm/include/llvm/Analysis/HeatUtils.h
29

Use CallBase instead of CallSite

llvm/lib/Analysis/CallPrinter.cpp
34

ShowEdgeWeight and callgraph-show-weights ?

158

This is O(N^2) to the number of functions. For a C++ module, this can be quite large.

163

why max but not sum?

200

can directly use insert method and check its return value

204

what is this check for?

llvm/lib/Analysis/HeatUtils.cpp
47

As I mentioned in one of the previous reviews, the blockfrequency is relative to the parent function (because of the final scaling step used in computing the integer frequency value which depends on the min and max value) and it will be meaningless to compare block frequency of callsites in different functions.

58

where does the '5' come from?

knaumov updated this revision to Diff 266629.May 27 2020, 12:39 PM

Addressed @davidxl 's comments, did some refactoring

davidxl added inline comments.Jun 2 2020, 11:52 AM
llvm/lib/Analysis/CallPrinter.cpp
29

Add a comment that this currently only shows static call counts. Also a FIXME to show real counts when profile data is available

80

This part can be folded into the previous loop that computes MaxFreq

knaumov updated this revision to Diff 268193.Jun 3 2020, 7:30 AM

Addressed @davidxl 's comments:

  • Added comments
  • Brought for-loop iteration over functions in the module into the previous one
davidxl added inline comments.Jun 3 2020, 9:12 AM
llvm/lib/Analysis/CallPrinter.cpp
79

Is this loop needed? Can you just check the *iter, *F pair? -- the enclosing loop should cover all caller,callee pairs in the module.

knaumov updated this revision to Diff 268549.Jun 4 2020, 11:46 AM
knaumov marked 10 inline comments as done.

I have noticed that MaxEdgeCount is essentially count the same thing as MaxFreq, so I replaced its uses in all the cases.

davidxl accepted this revision.Jun 16 2020, 9:02 AM

lgtm

This revision is now accepted and ready to land.Jun 16 2020, 9:02 AM
This revision was automatically updated to reflect the committed changes.
knaumov marked an inline comment as done.