[LLVMdev] [RFC] Scoped no-alias metadata

[Chandler Carruth]

On Sun, Dec 2, 2012 at 12:48 PM, Hal Finkel <hfinkel at anl.gov> wrote:

> Hello,
>
> I'd like to propose a new form of memory-aliasing metadata: scoped
> no-alias metadata. This can be used to model local 'restrict' pointers in
> C99, but should also be useful for other frontends (I think, for example,
> that Fortran will want this as well). Currently, we only use the restrict
> qualifier on function arguments in Clang where we translate the restrict
> qualifier as a 'noalias' function parameter attribute.
>
> In C99, the 'restrict' guarantee holds only for the lifetime of the
> pointer, and different lifetime regions can exist within a single function.
> Furthermore, these lifetime regions can be nested. As a result, we'll need
> to assign a unique identifier to each lifetime region (roughly a block in
> C99, although this may be only a partial block if a restrict pointer is
> declared in the middle of the block). Also, during optimization,
> instructions from these different lifetime regions can be merged, so a
> particular pointer value may end up associated with multiple lifetime
> regions.
>

I think a good way to think about this is through the inliner. When we
inline a function that has a noalias parameter, we should preserve that
noalias for the region of code inlined, no? This might be simpler than
describing it in terms of C99 initially, but I think we'll be able to
support everything we need... Anyways, not really relevant to the
proposal...


> Similar to TBAA, the scoped lifetime regions are arranged into disjoint
> tree structures:
> !0 = metadata !{ metadata !"scope of foo()" }
> !1 = metadata !{ metadata !"scope 1", metadata !0 }
> !2 = metadata !{ metadata !"scope 2", metadata !0 }
> !3 = metadata !{ metadata !"scope 2.1", metadata !2 }
> !4 = metadata !{ metadata !"scope 2.2", metadata !2 }
>
> and these are used to mark the pointer values:
>  %arrayidx = getelementptr inbounds %struct.ST* %s, i64 1, i32 2, i32 1,
> i64 5, i64 13, !sna !3
>
> in C99 this corresponds to something like:
> void foo(...) {
>   // begin root scope for foo()
>   int *restrict a = ...;
>   ...
>   {
>     // things in this block have scope 1
>     int *restrict b = ...;
>     ...
>   }
>   ...
>   {
>     // things here have scope 2
>     int *restrict b = ...;
>     ...
>     {
>       // a new scope 2.1
>     }
>     ...
>     *b += 1; // some use of a restrict pointer
>     ...
>     // more restrict pointers are declared, start a new nested scope 2.2
>     int *restrict c = ...;
>     ...
>   }
> }
>
> When BasicAA compares to pointers for aliasing, as it recurses to find
> each pointer's base pointer, it collects a list of scope ids associated
> with each pointer. If one of the pointers is associated with a scope id
> that is identical to one associated with the other pointer, or is a
> descendant or parent to one associated with the other pointer, then the two
> pointers are assumed not to alias. When merging two pointer values, if both
> have scope ids, then the resulting value can carry both scope ids. If one
> does not have a scope id, then the resulting pointer must carry none (we
> can preserve optimization ability by moving the metadata from the value to
> be merged to its uses that are also pointer-manipulation instructions).
>

Maybe I'm misunderstanding, but why can you assume that a particular scope
will have a distinct GEP to produce the pointer? Or are you really relying
on the propagation from the pre-optimization copy of the pointer the
frontend emits to the load/store instructions during optimization?

Why not just directly attach !noalias metadata to the loads and stores? It
feels like that would simplify the rules here, and more closely match the
way TBAA metadata works.


> I think that the most difficult part of implementing this proposal would
> be updating the various transformation passes to preserve this metadata.
>

I think by directly attaching the aliasing information to loads and stores,
this is made somewhat easier.

Dan, thoughts?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121202/90d0f6e8/attachment.html>