llvm dev - Nov 2013 - [LLVMdev] [RFC] Scoped no-alias metadata (redux)

Hello everyone,

In December, I had started a thread on scoped no-alias metadata in order to
represent C99 'restrict' pointer information at the IR level:
http://lists.cs.uiuc.edu/pipermail/llvmdev/2012-December/056586.html

At this point, we also have another important use case: preserving the existing
'noalias' attributes on pointers after inlining. My original proposal
was technically flawed, and based on the original feedback, and subsequent
discussions with Arnold and Andy, a new scheme has emerged:

First, we'll add some metadata to define a hierarchy of scopes. For
preserving noalias during function inlining, the inliner will fabricate a unique
scope node for the inlined function (and then tag all memory accesses in the
function). For use in representing C99 restrict pointers, a scope may represent
the entire function, or some other statement block within the function (or a
block within a block, etc.) created by the frontend.

As in my previous proposal, and similar to how TBAA is implemented, we define
some scopes:
!scope0 = metadata !{ metadata !"scope of foo()" }
!scope1 = metadata !{ metadata !"scope 1", metadata !scope0 }
!scope2 = metadata !{ metadata !"scope 2", metadata !scope0 }
!scope3 = metadata !{ metadata !"scope 2.1", metadata !scope2 }
!scope4 = metadata !{ metadata !"scope 2.2", metadata !scope2 }

The language reference defines 'noalias' as indicating "that
pointer values based on the argument or return value do not alias pointer values
which are not based on it...", and so we need to tag all loads and stores
in some scope with the scope metadata, and then additionally tag the
'noalias' loads and stores that don't alias with the various loads
and stores in that scope (not just with the other noalias loads and stores).

  = load %ptr1, !alias.scope !scope1
  = load %ptr2, !alias.scope !scope1, !noalias !scope1

Generally, when BasicAA is evaluating an aliasing query, if one of the
instructions is associated with an alias.scope id that is identical to the
noalias scope associated with the other instruction, or is a descendant (in the
scope hierarchy) of the noalias scope associated with the other instruction,
then the two memory accesses are assumed not to alias. When merging two
instructions with noalias metadata, if the transformation wants to maximally
preserve the information, it can add both noalias metadata references to the new
'merged' instruction (likewise, all alias.scope references should be
added).

This scheme should allow us to preserve noalias when inlining, and also
adequately model C99 restrict semantics, in addition to being useful for other
frontends.

If anyone has any feedback, please share.

Thanks again,
Hal

-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

On Nov 4, 2013, at 11:58 AM, Hal Finkel <hfinkel at anl.gov> wrote:
> The language reference defines 'noalias' as indicating "that
pointer values based on the argument or return value do not alias pointer values
which are not based on it...", and so we need to tag all loads and stores
in some scope with the scope metadata, and then additionally tag the
'noalias' loads and stores that don't alias with the various loads
and stores in that scope (not just with the other noalias loads and stores).
This may be obvious, but to be clear, this would only happen when the scope
actually contains some noalias memory references.
-Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20131104/538f1f4f/attachment.html>

Hello again,

When I had originally discussed this proposal, it was thought that we would not
have to worry about control dependencies on the noalias metadata because such
dependencies could only present a problem when loads or stores are merged (RAUW
is called), and transformations should drop metadata when that happens.

Now I'm worried that this is not true. Here's a simple example:

entry:
  %x1 = load %ptr1 // loading from ptr here to make all subsequent loads of %ptr
safe to speculate
  %x2 = load %ptr2
  ...

somewhere:
  ...
  call i_may_throw()
  %y = load %ptr1, !alias.scope !{ !s1 }
  ...
  %z = store %ptr2, !alias.scope !{ !s1 }, !noalias !{ !s1 }

So now some well-meaning pass swaps the order of the call and the load (legal
because it is legal to speculate the load):

somewhere:
  ...
  %y = load %ptr1, !alias.scope !{ !s1 }
  call i_may_throw()
  ...
  %z = store %ptr2, !alias.scope !{ !s1 }, !noalias !{ !s1 }

and now the load and the store could alias. In this particular situation,
although the two instructions might alias, they will never alias any time that
both are executed. So the question is: does NoAlias include any implicit
execution requirement? (and is this the right question to ask?)

Thanks again,
Hal

----- Original Message -----
> Hello everyone,
> 
> In December, I had started a thread on scoped no-alias metadata in
> order to represent C99 'restrict' pointer information at the IR
> level:
> http://lists.cs.uiuc.edu/pipermail/llvmdev/2012-December/056586.html
> 
> At this point, we also have another important use case: preserving
> the existing 'noalias' attributes on pointers after inlining. My
> original proposal was technically flawed, and based on the original
> feedback, and subsequent discussions with Arnold and Andy, a new
> scheme has emerged:
> 
> First, we'll add some metadata to define a hierarchy of scopes. For
> preserving noalias during function inlining, the inliner will
> fabricate a unique scope node for the inlined function (and then tag
> all memory accesses in the function). For use in representing C99
> restrict pointers, a scope may represent the entire function, or
> some other statement block within the function (or a block within a
> block, etc.) created by the frontend.
> 
> As in my previous proposal, and similar to how TBAA is implemented,
> we define some scopes:
> !scope0 = metadata !{ metadata !"scope of foo()" }
> !scope1 = metadata !{ metadata !"scope 1", metadata !scope0 }
> !scope2 = metadata !{ metadata !"scope 2", metadata !scope0 }
> !scope3 = metadata !{ metadata !"scope 2.1", metadata !scope2 }
> !scope4 = metadata !{ metadata !"scope 2.2", metadata !scope2 }
> 
> The language reference defines 'noalias' as indicating "that
pointer
> values based on the argument or return value do not alias pointer
> values which are not based on it...", and so we need to tag all
> loads and stores in some scope with the scope metadata, and then
> additionally tag the 'noalias' loads and stores that don't
alias
> with the various loads and stores in that scope (not just with the
> other noalias loads and stores).
> 
>   = load %ptr1, !alias.scope !scope1
>   = load %ptr2, !alias.scope !scope1, !noalias !scope1
> 
> Generally, when BasicAA is evaluating an aliasing query, if one of
> the instructions is associated with an alias.scope id that is
> identical to the noalias scope associated with the other
> instruction, or is a descendant (in the scope hierarchy) of the
> noalias scope associated with the other instruction, then the two
> memory accesses are assumed not to alias. When merging two
> instructions with noalias metadata, if the transformation wants to
> maximally preserve the information, it can add both noalias metadata
> references to the new 'merged' instruction (likewise, all
> alias.scope references should be added).
> 
> This scheme should allow us to preserve noalias when inlining, and
> also adequately model C99 restrict semantics, in addition to being
> useful for other frontends.
> 
> If anyone has any feedback, please share.
> 
> Thanks again,
> Hal
> 
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
> _______________________________________________
> 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

On Nov 14, 2013, at 9:44 AM, Hal Finkel <hfinkel at anl.gov> wrote:
> Hello again,
> 
> When I had originally discussed this proposal, it was thought that we would
not have to worry about control dependencies on the noalias metadata because
such dependencies could only present a problem when loads or stores are merged
(RAUW is called), and transformations should drop metadata when that happens.
> 
> Now I'm worried that this is not true. Here's a simple example:
> 
> entry:
>  %x1 = load %ptr1 // loading from ptr here to make all subsequent loads of
%ptr safe to speculate
>  %x2 = load %ptr2
>  ...
> 
> somewhere:
>  ...
>  call i_may_throw()
>  %y = load %ptr1, !alias.scope !{ !s1 }
>  ...
>  %z = store %ptr2, !alias.scope !{ !s1 }, !noalias !{ !s1 }
> 
> So now some well-meaning pass swaps the order of the call and the load
(legal because it is legal to speculate the load):
> 
> somewhere:
>  ...
>  %y = load %ptr1, !alias.scope !{ !s1 }
>  call i_may_throw()
>  ...
>  %z = store %ptr2, !alias.scope !{ !s1 }, !noalias !{ !s1 }
> 
> and now the load and the store could alias. In this particular situation,
although the two instructions might alias, they will never alias any time that
both are executed. So the question is: does NoAlias include any implicit
execution requirement? (and is this the right question to ask?)
I think the question is, can a transformation cause a store to execute on a new
path? Otherwise, I don’t think we can introduce aliasing.

If a transformation does that, I think it should drop any meta-data that it
doesn’t understand. In my mind that is no longer the same store—it’s taking the
place of some other store on the new path so meta-data must be merged/dropped.

-Andy
> Thanks again,
> Hal
> 
> ----- Original Message -----
>> Hello everyone,
>> 
>> In December, I had started a thread on scoped no-alias metadata in
>> order to represent C99 'restrict' pointer information at the IR
>> level:
>> http://lists.cs.uiuc.edu/pipermail/llvmdev/2012-December/056586.html
>> 
>> At this point, we also have another important use case: preserving
>> the existing 'noalias' attributes on pointers after inlining.
My
>> original proposal was technically flawed, and based on the original
>> feedback, and subsequent discussions with Arnold and Andy, a new
>> scheme has emerged:
>> 
>> First, we'll add some metadata to define a hierarchy of scopes. For
>> preserving noalias during function inlining, the inliner will
>> fabricate a unique scope node for the inlined function (and then tag
>> all memory accesses in the function). For use in representing C99
>> restrict pointers, a scope may represent the entire function, or
>> some other statement block within the function (or a block within a
>> block, etc.) created by the frontend.
>> 
>> As in my previous proposal, and similar to how TBAA is implemented,
>> we define some scopes:
>> !scope0 = metadata !{ metadata !"scope of foo()" }
>> !scope1 = metadata !{ metadata !"scope 1", metadata !scope0 }
>> !scope2 = metadata !{ metadata !"scope 2", metadata !scope0 }
>> !scope3 = metadata !{ metadata !"scope 2.1", metadata !scope2
}
>> !scope4 = metadata !{ metadata !"scope 2.2", metadata !scope2
}
>> 
>> The language reference defines 'noalias' as indicating
"that pointer
>> values based on the argument or return value do not alias pointer
>> values which are not based on it...", and so we need to tag all
>> loads and stores in some scope with the scope metadata, and then
>> additionally tag the 'noalias' loads and stores that don't
alias
>> with the various loads and stores in that scope (not just with the
>> other noalias loads and stores).
>> 
>>  = load %ptr1, !alias.scope !scope1
>>  = load %ptr2, !alias.scope !scope1, !noalias !scope1
>> 
>> Generally, when BasicAA is evaluating an aliasing query, if one of
>> the instructions is associated with an alias.scope id that is
>> identical to the noalias scope associated with the other
>> instruction, or is a descendant (in the scope hierarchy) of the
>> noalias scope associated with the other instruction, then the two
>> memory accesses are assumed not to alias. When merging two
>> instructions with noalias metadata, if the transformation wants to
>> maximally preserve the information, it can add both noalias metadata
>> references to the new 'merged' instruction (likewise, all
>> alias.scope references should be added).
>> 
>> This scheme should allow us to preserve noalias when inlining, and
>> also adequately model C99 restrict semantics, in addition to being
>> useful for other frontends.
>> 
>> If anyone has any feedback, please share.
>> 
>> Thanks again,
>> Hal
>> 
>> --
>> Hal Finkel
>> Assistant Computational Scientist
>> Leadership Computing Facility
>> Argonne National Laboratory
>> _______________________________________________
>> 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