llvm dev - Dec 2012 - [LLVMdev] [RFC] Scoped no-alias metadata

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.

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).

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

This is the simplest thing that I've thought of so far; does anyone have a
better way? Is there some reason that this won't work?

Thanks again,
Hal

-- 
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory

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>

----- Original Message -----
> From: "Chandler Carruth" <chandlerc at google.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "LLVM Developers Mailing List" <llvmdev at
cs.uiuc.edu>, "Clang Developers" <cfe-dev at cs.uiuc.edu>,
"Dan Gohman"
> <dan433584 at gmail.com>
> Sent: Sunday, December 2, 2012 7:02:52 PM
> Subject: Re: [RFC] Scoped no-alias metadata
> 
> 
> 
> 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...
This is also a good use case. When a function is inlined, you'd like to
preserve the 'noalias', but only when comparing pointers from the
callee, not when comparing pointers from the callee to pointers in the caller.
> 
> 
> 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?
I'm not completely sure I understand your point. A particular GEP could
carry multiple scope ids, the real danger comes with sharing a GEP between a
restrict pointer in one scope and a non-restrict pointer from a different scope.
From my understanding of how Clang CodeGen works, this won't happen (because
each statement and initializer gets its own set of instructions; there is no
effective CSE).
> 
> 
> 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.
Fair enough; this would make the LLVM-side of the implementation easier too (I
suspect). But it involves moving the 'dataflow analysis' part of this
into Clang. Any load or store would need to be marked with metadata
corresponding to the scope of the underlying restrict pointer (if any). This
will either requiring walking up the expression chain on each load/store (which
seems inefficient), or some kind of forward propagation phase in Clang prior to
CodeGen. Is there currently a good place to do this?
> 
> 
> 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.
Good point.

Thanks again,
Hal
> 
> 
> Dan, thoughts?
-- 
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory

On 12/2/2012 2:48 PM, Hal Finkel wrote:
>
> [...] 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).
Whether restricted pointer is declared in the middle of a block or not, 
does not matter from the standard's perspective.  Although I don't think
it changes much in your proposal (other than possibly eliminating some 
difficult cases that could otherwise appear).

---

"Let D be a declaration of an ordinary identifier that provides a means 
of designating an object P as a restrict-qualified pointer to type T.

If D appears inside a block and does not have storage class extern, let 
B denote the block. If D appears in the list of parameter declarations 
of a function definition, let B denote the associated block. Otherwise, 
let B denote the block of main (or the block of whatever function is 
called at program startup in a freestanding environment)."

The above does not specify where in the block B, the declaration D 
appears.  At the same time, the section below applies to the entire block B:

"During each execution of B, let L be any lvalue that has &L based on
P.
If L is used to access the value of the object X that it designates, and 
X is also modified (by any means), then the following requirements 
apply: T shall not be const-qualified. Every other lvalue used to access 
the value of X shall also have its address based on P."


-Krzysztof


-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation

----- Original Message -----
> From: "Krzysztof Parzyszek" <kparzysz at codeaurora.org>
> To: llvmdev at cs.uiuc.edu
> Sent: Monday, December 3, 2012 1:30:31 PM
> Subject: Re: [LLVMdev] [RFC] Scoped no-alias metadata
> 
> On 12/2/2012 2:48 PM, Hal Finkel wrote:
> >
> > [...] 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).
> 
> Whether restricted pointer is declared in the middle of a block or
> not,
> does not matter from the standard's perspective.  Although I don't
> think
> it changes much in your proposal (other than possibly eliminating
> some
> difficult cases that could otherwise appear).
Yes, good, thank you. The rationale (which I just re-read a minute ago) also
makes this clear:

"Cacheing the value in an object designated through
a restrict-qualified pointer is safe at the beginning of the block in which the
pointer is declared, because no pre-existing aliases may also be used to
reference
that object. The cached value must be restored to the object by the end of the
block, where pre-existing aliases again become available."

This is convenient, but also makes 'restrict' somewhat unique: It
retroactively imposes a restriction on code that comes before it. If feasible,
we may want to come up with a good way to warn about this if the user is
flagrantly violating it.

Thanks again,
Hal
> 
> ---
> 
> "Let D be a declaration of an ordinary identifier that provides a
> means
> of designating an object P as a restrict-qualified pointer to type T.
> 
> If D appears inside a block and does not have storage class extern,
> let
> B denote the block. If D appears in the list of parameter
> declarations
> of a function definition, let B denote the associated block.
> Otherwise,
> let B denote the block of main (or the block of whatever function is
> called at program startup in a freestanding environment)."
> 
> The above does not specify where in the block B, the declaration D
> appears.  At the same time, the section below applies to the entire
> block B:
> 
> "During each execution of B, let L be any lvalue that has &L based
on
> P.
> If L is used to access the value of the object X that it designates,
> and
> X is also modified (by any means), then the following requirements
> apply: T shall not be const-qualified. Every other lvalue used to
> access
> the value of X shall also have its address based on P."
> 
> 
> -Krzysztof
> 
> 
> --
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum,
> hosted by The Linux Foundation
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
-- 
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory