[LLVMdev] Profiling in LLVM Patch

[Daniel Dunbar]

On Wed, Jul 1, 2009 at 2:36 AM, Andreas
Neustifter<e0325716 at student.tuwien.ac.at> wrote:
>> [...]
>>
>> 1. The intent of ProfileInfo is that it is the public interface used by the rest
>> of LLVM for all "profiling" related analyses. As such, we want it to have a
>> thin, well-defined interface which can be implemented by multiple analysis
>> providers, just like we have with the current alias analysis interface. Your
>> current patch has a large number of changes to ProfileInfo which should instead
>> be inside a subclass of ProfileInfo, where most of the implementation details
>> are private.
>>
>> I think the first task should be to separate out the changes which are
>> appropriate for the ProfileInfo class itself and apply those to the tree. I
>> believe that the important changes which are worth reflecting in the API are
>> changed the weights to return a double instead of an int, and defining -1 as a
>> sentinel, "don't know", value.
> So you want the ProfileInfo to be untouched except for the double weights and the MissingValue? Then mark all methods virtual and do a subclass that has this sort of heavy implementation that I am using?

Exactly.

> Do you have any name suggestions for this subclass?

Not really. As with other interfaces, the actual implementation will
be completely hidden, so the only public part of the name is the
create...Pass call (and the options which end up being exposed to
'opt', etc). I would imagine something like DynamicProfileInfo,
OptimalEdgeDynamicProfileInfo, and StaticProfileInfoEstimator for the
main implementations.

> One thing I would like to patch in the current ProfileInfo implementation is the consistent use of the (0,entry) edge which is necessary to profile functions with only one block (namely the entry block).

Yes, I agree, that should be part of the ProfileInfo API changes.

Eventually we will want to change the ProfileInfo API so that it is
easier to chain various ProfileInfo implementations. That way a client
can use dynamic profile information, but still get useful results for
code which wasn't profiled using the static estimator. Currently the
interfaces can't really accommodate this, because they return absolute
counts and there is no way to interpret results from two separate
profile info providers. However, I think for now its more important to
get stuff working than to worry about this problem.

>> This is the most important thing to separate out, and to do early, because it is
>> the main interface that is shared with LLVM. It is also important for my GSoC
>> student, who was going to work on static profiling for LLVM and will depend on
>> any changes to this interface.
> Yes, I thought so, I will try to do this quick.

Great, thanks!

...

>> 2. We shouldn't worry too much about preserving the functionality of the current
>> llvm-prof tool, which uses the ProfileInfoLoader directly. llvm-prof should be
>> rewritten to just use the public API provided by ProfileInfo. This should be
>> done early so there are less dependencies on the ProfileInfoLoader interface.
> Okay, thats no problem. I guess it makes sense to rewrite llvm-prof but I was not sure if this sort of changes would be appreciated.

I'm pretty sure that no one uses llvm-prof, and I'm almost positive
that no one depends on it. I see its purpose as primarily to aid
developers working on profiling instrumentation -- it should be
useful, but not constraint the API or hinder development.

>> In fact, it might even make sense to just get rid of llvm-prof and instead
>> implement a module level pass which consumes profiling information and prints it
>> out as part of the pass. This would allow us to debug the preservation of
>> profiling information once we start modifying optimization passes to update it.
> Good point.

Unless anyone objects I may end up just doing this if a rainy day
presents itself.

>> 3. The static profiling estimator should be implemented as just another
>> ProfileInfo implementation. I believe this can be a separate patch. Similarly
>> the profile verifier is just another consumer of ProfileInfo and can be a
>> separate patch.
> The ProfileEstimator is already a subclass of ProfileInfo and implements that interface. Yes, these two are easily split into separate patches.

Right. One nice benefit of having the ProfileInterface be completely
abstract is that it should be straightforward to move the
ProfileEstimator to being lazy and only computing information when a
client requests it.

>> 4. Finally, the new optimal edge instrumentation & ProfileInfo implementation
>> can be brought in.
>>
>> Does this sound like a reasonable plan? Although it is a bit of work, I don't
>> think it will be that difficult and I am happy to help out with splitting up the
>> patch / refactoring the existing code.
> Yes, sounds good. I will try to split it up myself first and ask when there are decisions to be made I'm not sure about.

Ok!

>>> +  /// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
>>> +  /// (Modelled after getExitingBlocks().)
>>> +  typedef std::pair<BlockT*,BlockT*> Edge;
>>> +  void getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const {
>>> +    // Sort the blocks vector so that we can use binary search to do quick
>>> +    // lookups.
>>> +    SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
>>> +    std::sort(LoopBBs.begin(), LoopBBs.end());
>>
>> Would it be better to use a DenseSet for this lookup?
> Well, its the same that is used in getExitBlocks() where I got the implementation from. I really don't know but I think the current implementation is okay from what I gather form the LLVM Programmer's Manual.

There is nothing wrong with it, but using a DenseSet has better
asymptotic performance and shortens the code. OTOH it may have a
higher construction cost in most practical scenarios, some I'm not
convinced about which is really best.

Thanks,
 - Daniel