llvm dev - Aug 2018 - local restrict - again

On 06/28/2018 10:59 AM, Hal Finkel wrote:
> Hi, Jeroen,
>
> We should move these conversations to llvm-dev so that they don't get
> missed and others can contribute. Can I cc the list?
[+llvm-dev] - Jeroen consented.
>
> Doing this will mean that the logic for when to remove dead llvm.noalias
> intrinsics will become more complicated. That might be worthwhile. So
> long as we can answer the basic question:
>
>   Given two memory accesses with the same noalias scope metadata, is one
> pointer derived from a noalias intrinic with the right scope and the
> other not so derived? We don't know this full derivation chain up
front,
> and the chain can grow over time (after we do store-to-load forwarding
> in GVN or similar), so we'd need to have something in the pipeline that
> would add this metadata, but this certainly might all be workable.
>
> I think that this is worth exploring.
>
> Thanks again,
>
> Hal
>
>
> On 05/30/2018 09:46 AM, Jeroen Dobbelaere wrote:
>> Hi Hal,
>>
>> we are currently investigating if we can reduce the local restrict
issues by making use of a 'side channel'.
>>
>> The rough idea is to start from a base form coming from clang, where we
have something like:
>>
>>   ...
>>   %p = ...
>>   %rp =llvm.noalias %p , !scope.., !noalias ...
>>   ...
>>   store %rp, 10, !scope..., !noalias ...
>>   ...
>>
>>
>> and convert it (early, with an llvm-ir pass) to a form like:
>>   ...
>>   %p = ...
>>   %rp =llvm.noalias %p , !scope.., !noalias ...
>>   ...
>>   store %p, 10, !side_gep %rp, !scope..., !noalias ...  //@
Introduction of '!side_gep %rp, and removing the 'direct dependency'
on %rp for the store address
>>   ...   
>>
>> This second form, is the version where we can deduce restrictness
(through the 'side_gep')
>> We believe that this might help us fix the possible issues with LSR
>> We also think that a variant of this can help us to implement support
for a restrict pointer that is member of a struct (and as an extension, for
proposal n4150).
>>
>> Do you expect any issue with adding such a 'side channel'
metadata to load/store instructions ?
>>
>> Thanks,
>>
>> Jeroen Dobbelaere
>>
>>
>>
>>
>>
-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

There was another thread recently ("alias.scope and local restricted C
pointers") where it seemed understood that the present noalias and
alias.scope IR was sufficient to model local restrict, but that Clang wasn't
making use of it.  This thread implies that even if Clang were to make use of
it, there would need to be changes in LLVM to help support it.  Which is it?

Is the problem perhaps that noalias is presently an attribute of function
parameters (as set by CodeGenFunction::EmitFunctionProlog in Clang) and there is
no way to attach it to, say, the alloca used to create a local pointer?  Thus
this proposal of the additional "%rp = llvm.noalias ..."?

-Troy

-----Original Message-----
From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of Hal
Finkel via llvm-dev
Sent: Friday, August 17, 2018 10:31 AM
To: LLVM Dev <llvm-dev at lists.llvm.org>
Subject: Re: [llvm-dev] local restrict - again


On 06/28/2018 10:59 AM, Hal Finkel wrote:
> Hi, Jeroen,
>
> We should move these conversations to llvm-dev so that they don't get 
> missed and others can contribute. Can I cc the list?
[+llvm-dev] - Jeroen consented.
>
> Doing this will mean that the logic for when to remove dead 
> llvm.noalias intrinsics will become more complicated. That might be 
> worthwhile. So long as we can answer the basic question:
>
>   Given two memory accesses with the same noalias scope metadata, is 
> one pointer derived from a noalias intrinic with the right scope and 
> the other not so derived? We don't know this full derivation chain up 
> front, and the chain can grow over time (after we do store-to-load 
> forwarding in GVN or similar), so we'd need to have something in the 
> pipeline that would add this metadata, but this certainly might all be
workable.
>
> I think that this is worth exploring.
>
> Thanks again,
>
> Hal
>
>
> On 05/30/2018 09:46 AM, Jeroen Dobbelaere wrote:
>> Hi Hal,
>>
>> we are currently investigating if we can reduce the local restrict
issues by making use of a 'side channel'.
>>
>> The rough idea is to start from a base form coming from clang, where we
have something like:
>>
>>   ...
>>   %p = ...
>>   %rp =llvm.noalias %p , !scope.., !noalias ...
>>   ...
>>   store %rp, 10, !scope..., !noalias ...
>>   ...
>>
>>
>> and convert it (early, with an llvm-ir pass) to a form like:
>>   ...
>>   %p = ...
>>   %rp =llvm.noalias %p , !scope.., !noalias ...
>>   ...
>>   store %p, 10, !side_gep %rp, !scope..., !noalias ...  //@
Introduction of '!side_gep %rp, and removing the 'direct dependency'
on %rp for the store address
>>   ...   
>>
>> This second form, is the version where we can deduce restrictness 
>> (through the 'side_gep') We believe that this might help us fix
the
>> possible issues with LSR We also think that a variant of this can help
us to implement support for a restrict pointer that is member of a struct (and
as an extension, for proposal n4150).
>>
>> Do you expect any issue with adding such a 'side channel'
metadata to load/store instructions ?
>>
>> Thanks,
>>
>> Jeroen Dobbelaere
>>
>>
>>
>>
>>
--
Hal Finkel
Lead, Compiler Technology and Programming Languages Leadership Computing
Facility Argonne National Laboratory

_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

Hi Troy,

Some time ago (a few years by now), Hal created a set of patches that, together,
provide an implementation of 'local restrict'.
They also contain a fix for the issue when functions with restrict parameters
are inlined inside a loop, making it possible to see if the restrictness is
only valid in a single iteration or across iterations. (The llvm.noalias
intrinsics (together with the !noalias and !scope metadata) helps with
identifying if the restrictness ends inside or outside the loop)

These patches are available here: <https://reviews.llvm.org/D9375>
Some of them have been committed to the main llvm, but not all of them.

A number of people that are using all of these patches have found some issues in
certain circumstances.  One of the bigger problems is, that
some optimization passes optimize away some (but not all) of the llvm.noalias
intrinsics in a function. Because of that, the alias analysis can get confused
and can identify two pointers as not-aliasing where they should be aliasing.

In the past llvm conferences, there has been some discussions about possible
solutions (like making llvm.noalias opaque), but these have other drawbacks.
(worse optimization behavior).

Greetings,

Jeroen Dobbelaere

> -----Original Message-----
> From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of
Troy
> Johnson via llvm-dev
> Sent: Tuesday, August 21, 2018 19:36
> To: llvm-dev at lists.llvm.org
> Subject: Re: [llvm-dev] local restrict - again
> 
> There was another thread recently ("alias.scope and local restricted C
> pointers") where it seemed understood that the present noalias and
> alias.scope IR was sufficient to model local restrict, but that Clang
wasn't
> making use of it.  This thread implies that even if Clang were to make use
of
> it, there would need to be changes in LLVM to help support it.  Which is
it?
> 
> Is the problem perhaps that noalias is presently an attribute of function
> parameters (as set by CodeGenFunction::EmitFunctionProlog in Clang) and
> there is no way to attach it to, say, the alloca used to create a local
pointer?
> Thus this proposal of the additional "%rp = llvm.noalias ..."?
> 
> -Troy
> 
> -----Original Message-----
> From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of Hal
Finkel
> via llvm-dev
> Sent: Friday, August 17, 2018 10:31 AM
> To: LLVM Dev <llvm-dev at lists.llvm.org>
> Subject: Re: [llvm-dev] local restrict - again
> 
> 
> On 06/28/2018 10:59 AM, Hal Finkel wrote:
> > Hi, Jeroen,
> >
> > We should move these conversations to llvm-dev so that they don't
get
> > missed and others can contribute. Can I cc the list?
> 
> [+llvm-dev] - Jeroen consented.
> 
> >
> > Doing this will mean that the logic for when to remove dead
> > llvm.noalias intrinsics will become more complicated. That might be
> > worthwhile. So long as we can answer the basic question:
> >
> >   Given two memory accesses with the same noalias scope metadata, is
> > one pointer derived from a noalias intrinic with the right scope and
> > the other not so derived? We don't know this full derivation chain
up
> > front, and the chain can grow over time (after we do store-to-load
> > forwarding in GVN or similar), so we'd need to have something in
the
> > pipeline that would add this metadata, but this certainly might all be
> workable.
> >
> > I think that this is worth exploring.
> >
> > Thanks again,
> >
> > Hal
> >
> >
> > On 05/30/2018 09:46 AM, Jeroen Dobbelaere wrote:
> >> Hi Hal,
> >>
> >> we are currently investigating if we can reduce the local restrict
issues by
> making use of a 'side channel'.
> >>
> >> The rough idea is to start from a base form coming from clang,
where we
> have something like:
> >>
> >>   ...
> >>   %p = ...
> >>   %rp =llvm.noalias %p , !scope.., !noalias ...
> >>   ...
> >>   store %rp, 10, !scope..., !noalias ...
> >>   ...
> >>
> >>
> >> and convert it (early, with an llvm-ir pass) to a form like:
> >>   ...
> >>   %p = ...
> >>   %rp =llvm.noalias %p , !scope.., !noalias ...
> >>   ...
> >>   store %p, 10, !side_gep %rp, !scope..., !noalias ...  //@
Introduction of
> '!side_gep %rp, and removing the 'direct dependency' on %rp for
the store
> address
> >>   ...
> >>
> >> This second form, is the version where we can deduce restrictness
> >> (through the 'side_gep') We believe that this might help
us fix the
> >> possible issues with LSR We also think that a variant of this can
help us to
> implement support for a restrict pointer that is member of a struct (and as
an
> extension, for proposal n4150).
> >>
> >> Do you expect any issue with adding such a 'side channel'
metadata to
> load/store instructions ?
> >>
> >> Thanks,
> >>
> >> Jeroen Dobbelaere
> >>
> >>
> >>
> >>
> >>
> 
> --
> Hal Finkel
> Lead, Compiler Technology and Programming Languages Leadership
> Computing Facility Argonne National Laboratory
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.llvm.org_cgi-
> 2Dbin_mailman_listinfo_llvm-
> 2Ddev&d=DwIGaQ&c=DPL6_X_6JkXFx7AXWqB0tg&r=ELyOnT0WepII6UnFk-
> OSzxlGOXXSfAvOLT6E8iPwwJk&m=vxsM9gIzWHJKzyPBVSon4t0mByMAja6H
> w1ijrzh7tmk&s=JAxozo3YFCCTXC7LE9LhiBz9dRsIi9h1oBEjFt-oaSI&e>
_______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.llvm.org_cgi-
> 2Dbin_mailman_listinfo_llvm-
> 2Ddev&d=DwIGaQ&c=DPL6_X_6JkXFx7AXWqB0tg&r=ELyOnT0WepII6UnFk-
> OSzxlGOXXSfAvOLT6E8iPwwJk&m=vxsM9gIzWHJKzyPBVSon4t0mByMAja6H
> w1ijrzh7tmk&s=JAxozo3YFCCTXC7LE9LhiBz9dRsIi9h1oBEjFt-oaSI&e=