RFC - Improvements to PGO profile support

Relative hotness across functions is a major requirement for most
profile-based inter-procedural optimizations - e.g. profile-based
inlining, optimizations for code size, function placement.

The proposed CFG edge/BB profile execution counts will overcome this
issue. In addition to Bob's arguments, one challenge for edge/BB execution
counts would be scaling. For example, if we reroll a loop and execution
counts for BBs/edges in the loop exceed the limit, then scaling is needed.
However this scaling will necessitate scaling BBs/edges execution counts
for the entire module. Another similar example is function merging.

On the other hand, how could we incrementally extend the current approach
of branch metadata/branch probabilities/block frequencies to provide
support for the relative hotness across functions? One idea is to
introduce a metadata for function entry count (FEC) - which is currently
available as region counter 0 in clang - and properly update it through
transformations. Take for example the inliner. When we inline callee B in
function A, we need to decrease FEC(B) by BB execution count of the
callsite, and (incrementally) recompute BlockFrequencyInfo for function A.
One issue here is the lack of function-level metadata.


Date: Thu, 5 Mar 2015 08:29:52 -0800
From: Bob Wilson <bob.wilson@apple.com>
To: Diego Novillo <dnovillo@google.com>
Cc: Xinliang David Li <davidxl@google.com>, LLVM Developers Mailing
  List <llvmdev@cs.uiuc.edu>
Subject: Re: [LLVMdev] RFC - Improvements to PGO profile support

Message-ID: <AC046380-247D-4AFA-8375-C59158D70083@apple.com>

Content-Type: text/plain; charset="utf-8"

I've created a few bugzilla issues with details of some of the things

I'll be looking into. I'm not yet done wordsmithing the overall design
document. I'll try to finish it by early next week at the latest. The
document is available at

Improvements to LLVM's Profile Infrastructure - Google Docs?

<Improvements to LLVM's Profile Infrastructure - Google Docs;
There are several topics covered. Ideally, I would prefer that we
discuss each topic separately. The main ones I will start working on are

the ones described in the bugzilla links we have in the doc.
This is just a starting point for us. I am not at all concerned with

implementing exactly what is proposed in the document. In fact, if we can
get the same value using the existing support, all the better. OTOH, any
other ideas that folks may have that work better than this are

more than welcome. I don't have really strong opinions on the matter. I

am fine with whatever works.

Thanks for the detailed write-up on this. Some of the issues definitely

need to be addressed. I am concerned, though, that some of the ideas may
be leading toward a scenario where we have essentially two completely
different ways of representing profile information in LLVM IR. It is great

to have two complementary approaches to collecting profile data, but two

representations in the IR would not make sense.

The first issue raised is that profile execution counts are not
represented in the IR. This was a very intentional decision. I know it

goes against what other compilers have done in the past. It took me a
while to get used to the idea when Andy first suggested it, so I know it
seems awkward at first. The advantage is that branch probabilities are
much easier to keep updated in the face of compiler transformations,
compared to execution counts. We are definitely missing the per-function
execution counts that are needed to be able to compare relative

across functions, and I think that would be a good place to start making

improvements. In the long term, we should keep our options open to making

major changes, but before we go there, we should try to make incremental

improvements to fix the existing infrastructure.

Many of the other issues you raise seem like they could also be


without major changes to the existing infrastructure. Let?s try to fix

those first.