Page MenuHomePhabricator

Heat Coloring (3/3): Adding Heat Functionality to CallPrinter
Needs ReviewPublic

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.Fri, May 1, 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 TranscriptFri, May 1, 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.Tue, May 5, 2:36 PM
llvm/include/llvm/Analysis/HeatUtils.h
34

Use CallBase instead of CallSite

llvm/lib/Analysis/CallPrinter.cpp
34

ShowEdgeWeight and callgraph-show-weights ?

170

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

175

why max but not sum?

212

can directly use insert method and check its return value

216

what is this check for?

llvm/lib/Analysis/HeatUtils.cpp
46

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.

57

where does the '5' come from?

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

Addressed @davidxl 's comments, did some refactoring