[LLVMdev] Path profiling interface proposal

[Slobodan Pejic]

David Greene wrote:
> On Friday 10 July 2009 18:06, Slobodan Pejic wrote:
>> Hello,
>>
>> I am planning on contributing path profiling to LLVM by the end of
>> August.  I have written a document of what the interface to the path
>> profiles would look like at that time.  If someone has any amendments, I
>> can incorporate them.
>>
>> http://www.cs.ualberta.ca/~pejic/PathProfiling.html
> 
> Slobodan,
> 
> This looks interesting.  I have a few questions.

Thanks for taking the time to look through!

> 
> Is there anything about your proposed profiling method that requires the 
> use of lli or llvm-ld?  I'm assuming the instrumentor itself will simply
> be a Pass.  Will this work in setups that use the machine's native linker
> as long as it links in libprofile_rt?

The current static library libprofile_rt is being built as a .bca file
(archive of .bc files.)  Presumably the build process can be changed to
create a native archive, thus allowing the native linker to be used.  I
will give this a try when I get a chance.

This section was included because running edge profiling from c sources
to the final executable threw me off when I was familiarizing myself
with LLVM.  The edge instrumentor can only instrument modules with a
main function, so any modules that one wants instrumented must be linked
to the module with main first.  My Instrumetor is similar in structure.

> 
> Is libprofile_rt built during the LLVM build process?  Is the intent for
> libprofile_rt to be the home for all profiling runtime or just path
> profiling?  If the latter, I'd suggest a different name, like 
> libpathprofile_rt.  I'm not knowledgeable about the LLVM profiling 
> infrastructure, so maybe libprofile_rt is something that already exists.

Yes, libprofile_rt already exists, however it must be built by invoking
make in runtime/.

> 
>> PathProfileInfo& profileInfo = getAnalysis <PathProfileInfo>();
> 
> PathProfileInfo is an ImmutablePass, yes?
> 
>> /*
>>  * The following method allows querying for path numbers by specifying
>>  *     F, the function that the paths are in;
>>  *     start, starting iterator over basic blocks;
>>  *     end, ending iterator over basic blocks;
>>  *     order, ascending or descending ordering by count.
>>  * Returns an iterator over Path objects.
>>  */
>> PathProfileInfo::iterator PathProfileInfo::selectPaths (
>>     Function &F,
>>     std::vector<BasicBlock*>::iterator start,
>>     std::vector<BasicBlock*>::iterator end,
>>     PathProfileInfo::Order order);
> 
> I don't understand what this means.  Is this an interface to get at the paths 
> in some subset of a Function's basic blocks?  If so, how would one specify a 
> disjoint set of basic blocks to examine?  I don't know if that's useful but if 
> you're  providing an interface to iterate over subsets of path data it seems 
> natural to want to generalize it.

The function is supposed to allow the compiler developer to find the
subset of paths that contain certain basic blocks. E.g. consider this CFG:

  A
 / \
B   C
 \ /
  D
 / \
E   F
    |\
    H I


If one passes basic blocks B, and F, then selectPaths would return an
iterator over ( (A,B,D,F,H), (A,B,D,F,I) ).

I will need to make this clearer in the document.

> 
> I also don't understand the "order" parameter.  How are paths ordered?  By 
> number?  Why does the returned order of paths matter?

The idea is to load as little as possible from the on-disk profile if
the entire profile is not required.  In order to delay loading the
profile (which may have been sorted by count in the runtime library
saving the profile), the iterator over paths can load the data lazily.
Some potential passes may want to look at the top paths that account for
80% execution, and will not require the majority of the path profile.

> 
>> /* 
>>  * Returns the execution count for a path. 
>>  */
>> unsigned long Path::getCount()
> 
>> /* 
>>  * Returns the execution frequency for a path. 
>>  */
>> float Path::getFrequency()
> 
> The naming is a bit confusing here.  "getCount" makes sense, but 
> "getFrequency" could mean a few different things.  My assumption is that it 
> means the % of times this path was taken vs. the number of times the Function 
> was invoked.  It could also mean the % of times this path was executed 
> relative to some "parent" path (think of a subpath through conditional code, 
> i.e. for getting branch taken/not taken frequencies).

Your assumption is correct.  This function can be renamed to
getFrequencyPerFunction().

> 
> Some of these questions are answered later in your document but they really 
> need to be specified up front.  PathProfileInfo::DESC, for example, has no
> meaning outside of the comments in this context:
> 
>> /* Query for paths in hot to cold order. */
>> PathProfileInfo::iterator path = PI.selectPaths(F, blocksRequired.begin(),
>> 	blocksRequired.end(), PathProfileInfo::DESC);
> 
> All in all, looks good.  This will be a useful addition.

Thanks for the feedback.

> 
>                                -Dave
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 


-- 
Slobodan Pejic