llvm dev - Feb 2015 - [LLVMdev] RFC: PerfGuide for frontend authors

----- Original Message -----
> From: "Philip Reames" <listmail at philipreames.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu>
> Sent: Friday, February 27, 2015 11:25:12 PM
> Subject: Re: [LLVMdev] RFC: PerfGuide for frontend authors
> 
> 
> > On Feb 27, 2015, at 3:58 PM, Hal Finkel <hfinkel at anl.gov>
wrote:
> > 
> > ----- Original Message -----
> >> From: "Philip Reames" <listmail at
philipreames.com>
> >> To: "LLVM Developers Mailing List" <llvmdev at
cs.uiuc.edu>
> >> Sent: Friday, February 27, 2015 5:34:36 PM
> >> Subject: Re: [LLVMdev] RFC: PerfGuide for frontend authors
> >> 
> >> The first version of this document is now live:
> >> http://llvm.org/docs/Frontend/PerformanceTips.html
> >> 
> >> Please feel free to add to it directly.  Alternatively, feel free
> >> to
> >> reply to this thread with text describing an issue that should be
> >> documented.  I'll make sure text gets turned into patches.
> > 
> > First, thanks for working on this! Some things (perhaps) worth
> > mentioning:
> I'll add these Monday, but am not going to take the time to write
> much. Any expansion you (or anyone else) want to do would be welcome
Thanks!
> 
> > 
> > 1. Make sure that a DataLayout is provided (this will likely become
> > required in the near future, but is certainly important for
> > optimization).
> > 
> > 2. Add nsw/nuw/fast-math flags as appropriate
> > 
> > 3. Add noalias/align/dereferenceable/nonnull to function arguments
> > and return values as appropriate
> I was thinking of a more general: use metadata and function
> attributes.
> 
> I don't want to end up duplicating content from the Lang ref here.  I
> was thinking that this page should cover the things you can't learn
> by just reading langref.
I agree, I don't want to duplicate the LangRef, but I think that mentioning
some of the more-important attributes and metadata for optimization is useful.
Unless you read the LangRef quite carefully, and also understand what the
optimizer does, it is easy to miss which things are relevant to optimizations.
I'd mention them here, and let people look at the LangRef for the
definitions.
> 
> > 
> > 4. Mark functions as readnone/readonly/nounwind when known
> > (especially for external functions)
> > 
> > 5. Use ptrtoint/inttoptr sparingly (they interfere with pointer
> > aliasing analysis), prefer GEPs
> > 
> > 6. Use the lifetime.start/lifetime.end and
> > invariant.start/invariant.end intrinsics where possible
> Do you find these help in practice?  The few experiments I ran were
> neutral at best and harmful in one or two cases.  Do you have
> suggestions on how and when to use them?
Good point, we should be more specific here. My, admittedly limited, experience
with these is that they're most useful when their properties are not dynamic
-- which perhaps means that they post-dominate the entry, and are applied to
allocas in the entry block -- and the larger the objects in question, the more
the potential stack-space savings, etc.
> 
> I am using invariant.load, tbaas is constant flag, and a custom hook
> for zero initialized memory from my allocation routines.
We should discuss this custom hook -- perhaps we'd also benefit from
something similar upstream (from calloc, etc.). [Different thread however, I
suppose].

 -Hal
> > 
> > 7. Use pointer aliasing metadata, especially tbaa metadata, to
> > communicate otherwise-non-deducible pointer aliasing facts
> > 
> > 8. Use the "most-private" possible linkage types for the
functions
> > being defined (private, internal or linkonce_odr preferably)
> > 
> > -Hal
> > 
> >> 
> >> Philip
> >> 
> >>> On 02/23/2015 04:46 PM, Philip Reames wrote:
> >>> I'd like to propose that we create a new Performance Guide
> >>> document.
> >>> The target of this document will be frontend authors, not
> >>> necessarily
> >>> LLVM contributors.  The content will be a collection of items
a
> >>> frontend author might want to know about how to generate LLVM
IR
> >>> which
> >>> will optimize well.
> >>> 
> >>> Some ideas on topics that might be worthwhile:
> >>> - Prefer sext over zext when value is known to be positive in
the
> >>> language (e.g. range checked index on a GEP)
> >>> - Avoid loading and storing first class aggregates (i.e.
they're
> >>> not
> >>> well supported in the optimizer)
> >>> - Mark invariant locations - i.e. link to !invariant.load and
> >>> TBAA
> >>> constant flags
> >>> - Use globals not inttoptr for runtime structures - this gives
> >>> you
> >>> dereferenceability information
> >>> - Use function attributes where possible (nonnull, deref,
etc..)
> >>> - Be ware of ordered and atomic memory operations (not well
> >>> optimized), depending on source language, might be faster to
use
> >>> fences.
> >>> - Range checks - make sure you test with the IRCE pass
> >>> 
> >>> If folks are happy with the idea of having such a document, I
> >>> volunteer to create version 0.1 with one or two items.  After
> >>> that,
> >>> we
> >>> can add to it as folks encounter ideas.  The initial content
will
> >>> be
> >>> fairly minimal, I just want a link I can send to folks in
reviews
> >>> to
> >>> record comments made.  :)
> >>> 
> >>> Philip
> >>> _______________________________________________
> >>> LLVM Developers mailing list
> >>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> >>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> >> 
> >> _______________________________________________
> >> LLVM Developers mailing list
> >> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> > 
> > --
> > Hal Finkel
> > Assistant Computational Scientist
> > Leadership Computing Facility
> > Argonne National Laboratory
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

Hi,

On 2015.02.28 10:53:35 -0600, Hal Finkel wrote:
> ----- Original Message -----
> > From: "Philip Reames" <listmail at philipreames.com>
> > > 6. Use the lifetime.start/lifetime.end and
> > > invariant.start/invariant.end intrinsics where possible
> > Do you find these help in practice?  The few experiments I ran were
> > neutral at best and harmful in one or two cases.  Do you have
> > suggestions on how and when to use them?
> 
> Good point, we should be more specific here. My, admittedly limited,
> experience with these is that they're most useful when their
> properties are not dynamic -- which perhaps means that they
> post-dominate the entry, and are applied to allocas in the entry block
> -- and the larger the objects in question, the more the potential
> stack-space savings, etc.
my experience adding support for the lifetime intrinsics to the rust
compiler is largely positive (because our code is very stack heavy at
the moment), but we still suffer from missed memcpy optimizations.
That happens because I made the lifetime regions as small as possible,
and sometimes an alloca starts its lifetime too late for the optimization
to happen.  My new (but not yet implemented) approach to to "align"
the
calls to lifetime.start for allocas with overlapping lifetimes unless
there's actually a possibility for stack slot sharing.

For example we currently translate:

    let a = [0; 1000000]; // Array of 1000000 zeros
    {
      let b = a;
    }
    let c = something;

to roughly this:

    lifetime.start(a)
    memset(a, 0, 1000000)
    
    lifetime.start(b)
    memcpy(b, a)
    lifetime.end(b)
    
    lifetime.start(c)
    lifetime.end(c)
    
    lifetime.end(a)

The lifetime.start call for "b" stops the call-slot (I think)
optimization from being applied. So instead this should be translated to
something like:

    lifetime.start(a)
    lifetime.start(b)
    memset(a, 0, 1000000)
    
    memcpy(b, a)
    lifetime.end(b)
    
    lifetime.start(c)
    lifetime.end(c)
    
    lifetime.end(a)

extending the lifetime of "b" because it overlaps with that of
"a"
anyway. The lifetime of "c" still starts after the end of
"b"'s lifetime
because there's actually a possibility for stack slot sharing.

Björn

On 02/28/2015 10:04 AM, Björn Steinbrink wrote:
> Hi,
>
> On 2015.02.28 10:53:35 -0600, Hal Finkel wrote:
>> ----- Original Message -----
>>> From: "Philip Reames" <listmail at
philipreames.com>
>>>> 6. Use the lifetime.start/lifetime.end and
>>>> invariant.start/invariant.end intrinsics where possible
>>> Do you find these help in practice?  The few experiments I ran were
>>> neutral at best and harmful in one or two cases.  Do you have
>>> suggestions on how and when to use them?
>> Good point, we should be more specific here. My, admittedly limited,
>> experience with these is that they're most useful when their
>> properties are not dynamic -- which perhaps means that they
>> post-dominate the entry, and are applied to allocas in the entry block
>> -- and the larger the objects in question, the more the potential
>> stack-space savings, etc.
> my experience adding support for the lifetime intrinsics to the rust
> compiler is largely positive (because our code is very stack heavy at
> the moment), but we still suffer from missed memcpy optimizations.
> That happens because I made the lifetime regions as small as possible,
> and sometimes an alloca starts its lifetime too late for the optimization
> to happen.  My new (but not yet implemented) approach to to
"align" the
> calls to lifetime.start for allocas with overlapping lifetimes unless
> there's actually a possibility for stack slot sharing.
>
> For example we currently translate:
>
>      let a = [0; 1000000]; // Array of 1000000 zeros
>      {
>        let b = a;
>      }
>      let c = something;
>
> to roughly this:
>
>      lifetime.start(a)
>      memset(a, 0, 1000000)
>      
>      lifetime.start(b)
>      memcpy(b, a)
>      lifetime.end(b)
>      
>      lifetime.start(c)
>      lifetime.end(c)
>      
>      lifetime.end(a)
>
> The lifetime.start call for "b" stops the call-slot (I think)
> optimization from being applied. So instead this should be translated to
> something like:
>
>      lifetime.start(a)
>      lifetime.start(b)
>      memset(a, 0, 1000000)
>      
>      memcpy(b, a)
>      lifetime.end(b)
>      
>      lifetime.start(c)
>      lifetime.end(c)
>      
>      lifetime.end(a)
>
> extending the lifetime of "b" because it overlaps with that of
"a"
> anyway. The lifetime of "c" still starts after the end of
"b"'s lifetime
> because there's actually a possibility for stack slot sharing.
>
> Björn
I'd be interested in seeing the IR for this that you're currently 
generating.  Unless I'm misreading your example, everything in this is 
completely dead.  We should be able to reduce this to nothing and if we 
can't, it's clearly a missed optimization.  I'm particularly
interested
in how the difference in placement of the lifetime start for 'b' effects
optimization.  I really wouldn't expect that.

Philip

On 02/28/2015 08:53 AM, Hal Finkel wrote:
> ----- Original Message -----
>> I am using invariant.load, tbaas is constant flag, and a custom hook
>> for zero initialized memory from my allocation routines.
> We should discuss this custom hook -- perhaps we'd also benefit from
something similar upstream (from calloc, etc.). [Different thread however, I
suppose].
I think we already have this upstream for calloc.  Or at least I 
proposed patches several months back.  I don't remember what happened 
here...

Yep, we've got the basic checks in GVN.  It could be expanded, but we at 
least catch the simple cases.

Philip