[LLVMdev] [RFC] Scoped no-alias metadata (redux)

[Andrew Trick]

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