[LLVMdev] Separating loop nests based on profile information?

[Xinliang David Li]

On Mon, Jan 19, 2015 at 5:41 PM, Philip Reames <listmail at philipreames.com>
wrote:

>
> On 01/12/2015 07:27 PM, Xinliang David Li wrote:
>
>
>
> On Wed, Jan 7, 2015 at 5:19 PM, Philip Reames <listmail at philipreames.com>
> wrote:
>
>>  The basic idea of this patch is to use profiling information about the
>> frequency of a backedges to separate a loop with multiple latches into a
>> loop nest with the rare backedge being the outer loop. We already use a set
>> of static heuristics based on non-varying arguments to PHI nodes to do the
>> same type of thing.
>>
>> The motivation is that doing this pulls rarely executed code out of the
>> innermost loop and tends to greatly simplify analysis and optimization of
>> that loop.
>>
>
>  This is good thing to do from the code/block placement point of view --
> to improve icache utilization. Code layout is one of the most important
> passes that can benefit from profile data.
>
> We already try to do that using profile information at a later point.  I
> don't know how effective that is and how much room we might have to
> improve, but that really wasn't a motivation for this approach.
>
>
>
>
>>   In particular, it can enable substantial LICM gains when there are
>> clobbering calls down rare paths.
>>
>
>  How can this enable more LICM?
>
> Given you now have a loop nest with a simpler inner loop, we can sometimes
> perform LICM on that inner loop.
>
> Note that this is equivalent to running a smarter PRE on the original loop
> structure.
>


yes -- it works around the weakness of PRE (of existing implementation).



>
>
>>
>>    - I chose to implement this without relying on the existing block
>>    frequency analysis. My reasoning was that a) this is a rarely taken case
>>    and adding an expensive analysis dependency probably wasn't worthwhile and
>>    b) that block frequency analysis was more expensive/precise than I really
>>    needed. Is this reasonable?
>>
>>
>  IMO no. Remember your pass should also work with real profile data
> (instrumentation or sample based) -- you should  rely on existing profile
> infrastructure to provide what you need. (Ideally you should treat it as
> something that is always available for query).
>
> There's a distinction here between 'source of information' and 'source of
> heuristics'.  By accessing the metadata directly, I'm still using whatever
> profile information the user provided.
>
>
By accessing meta data directly, you basically bypass the static branch
prediction and only make use of  real profile data or data from user
annotation.


> I'm currently exploring other approaches to this problem, but if I do end
> up exploring this further, I'll likely rewrite to use one the existing
> analyses.
>

David


>
> Philip
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150119/ce169f27/attachment.html>