[LLVMdev] [RFC] Scoped no-alias metadata

[Daniel Berlin]

On Mon, Dec 3, 2012 at 11:43 AM, Hal Finkel <hfinkel at anl.gov> wrote:
> ----- Original Message -----
>> From: "Daniel Berlin" <dberlin at dberlin.org>
>> To: "Hal Finkel" <hfinkel at anl.gov>
>> Cc: "Chandler Carruth" <chandlerc at google.com>, "Clang Developers" <cfe-dev at cs.uiuc.edu>, "LLVM Developers Mailing
>> List" <llvmdev at cs.uiuc.edu>
>> Sent: Monday, December 3, 2012 12:10:55 PM
>> Subject: Re: [LLVMdev] [RFC] Scoped no-alias metadata
>>
>> On Mon, Dec 3, 2012 at 6:19 AM, Hal Finkel <hfinkel at anl.gov> wrote:
>> > ----- Original Message -----
>> >> From: "Daniel Berlin" <dberlin at dberlin.org>
>> >> To: "Hal Finkel" <hfinkel at anl.gov>
>> >> Cc: "Chandler Carruth" <chandlerc at google.com>, "Clang Developers"
>> >> <cfe-dev at cs.uiuc.edu>, "LLVM Developers Mailing
>> >> List" <llvmdev at cs.uiuc.edu>
>> >> Sent: Sunday, December 2, 2012 11:21:00 PM
>> >> Subject: Re: [LLVMdev] [RFC] Scoped no-alias metadata
>> >>
>> >> On Sun, Dec 2, 2012 at 8:05 PM, Hal Finkel <hfinkel at anl.gov>
>> >> wrote:
>> >> > ----- 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.
>> >>
>> >> C99 also states that
>> >> >>
>> >> >>
>> >> >>
>> >> >> 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).
>> >>
>> >> Well, actually, you have a number of problems if you attach
>> >> noalias
>> >> to GEP's.
>> >> From C99 (6.7.3.1, example 3):
>> >> "
>> >>
>> >> The function parameter declarations
>> >>
>> >> void h(int n, int * restrict p, int * restrict q, int * restrict
>> >> r)
>> >> {
>> >> int i;
>> >> for (i = 0; i < n; i++)
>> >> p[i] = q[i] + r[i];
>> >> }
>> >> illustrate how an unmodified object can be aliased through two
>> >> restricted pointers. In particular, if a and b
>> >> are disjoint arrays, a call of the form h(100, a, b, b) has defined
>> >> behavior, because array b is not
>> >> modified within function h.
>> >> "
>> >>
>> >> If you claim q and r (which may or may not share a GEP) noalias
>> >> each
>> >> other, that would be wrong.
>> >> That's easy to handle, since you say they won't share a GEP.
>> >> But you can make the examples arbitrarily complex,  because the
>> >> restrict behavior is only really applicable *if you modify the
>> >> object*.
>> >> "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:
>> >> ...
>> >> If these requirements are not met, then the behavior is undefined
>> >> "
>> >> (Note the last clause, requiring a modification for the
>> >> requirements
>> >> to apply).
>> >>
>> >> So you can come up with arbitrarily complex aliased restrict
>> >> pointers
>> >> and scopes, all of which share values,and as long as you don't
>> >> modify
>> >> any of the objects, it's all okay.
>> >> Worse, none of the scoping requirements around restrict lifetimes
>> >> apply *unless* you modify the objects, since those are inside the
>> >> "..." part above.
>> >> Worse still, even if you modify the objects, you've only made the
>> >> restrict requirements valid for the pointers that point to that
>> >> object.
>> >>
>> >> This all seems a bit complex to handle just by attaching the
>> >> noalias
>> >> info to GEP's.
>> >
>> > Agreed (especially before mem2reg is run). But I don't understand
>> > why we need to worry about looking for modifications. For one
>> > thing, > checking for the modifications is impossible (it says "by
>> > any means" -- this includes by calling external functions, other
>> > threads,
>> > interrupt handlers, etc., no?), and the behavior otherwise is
>> > simply undefined.
>> Maybe i'm confused, but i don't see how it's otherwise undefined.
>
> Maybe I'm missing something here, but the paragraph from which you quoted in 6.7.3.1 says so. It says, "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: ... If these requirements are not met, then the behavior is undefined."
>
> From a user's perspective, this language is fairly constraining. If I want restrict to have a defined meaning, then I need to make sure to > update the relevant pointee objects.
I think you are reading it differently than me.

The *requirements* only apply *if* the modification occurs.
If no modification occurs, *no* requirements apply.

IE you seem to be reading it as:

"Here are some requirements:
If these requirements are not met behavior is undefined"

It actually says (IMHO, and the language lawyers i've talked to agreed :P):
"Here are some pre-requirements (A)
If these pre-requirements (A) are met, then the following requirements
(B) must *also* be met.
If the pre-requirements are met (A), and the above requirements (B)
are not met, then the behavior is undefined"


IE the undefined-ness only attached if A && B.
This also means that if the pre-requirements are not met (A), you do
not have to meet the requirements in (B) and the behavior is still
well defined.

Since "modification" is part of the pre-requirements, if you do not
modify it, there is no undefined behavior, no matter whether you meet
the requirements in B or not.





> But from a compiler-writer's perspective, I see this language as non-constraining. If the object is updated, then restrict has a useful
> meaning. If not (and I really have no definitive way of knowing this), the meaning of restrict is undefined and I can make it mean >whatever I'd like. The only reasonable course of action (as I have no way of really knowing that an object is not updated), is to always >treat the objects as though they are updated in the block.
>
>>
>> If you don't modify it, the behavior of load-load is quite defined,
>> and the aliasing is acceptable.
>> If you do modify it, the behavior of load-load is noalias, and the
>> behavior of load-store is noalias.
>>
>> So you can only mark the load-load pairs of two restricted pointers
>> noalias if there is a store somewhere for the address "based on" the
>> same restricted pointer.
>>
>> Unless i missed another clause in the standard
>>
>> I do agree this is basically impossible to comply with (particularly
>> the X is modified part, since as you point,  you can't always know
>> all
>> the must-aliases, only a set of may-aliases).  Our GCC "person on the
>> committee" agreed this was the case when we discussed it about 4
>> years
>> ago in GCC, and a defect report was supposed to be filed, but looking
>> at the DR list, it doesn't seem to have happened.
>
> Interesting.
>
>>
>> I'm actually not oppose to doing whatever we want, as long as we
>> document it.
>> :)
>
> Fair enough ;)
>
>>
>> > As a result, we can define it to mean what the programmer would
>> > expect, right?
>> Not in a standards compliant way, but i'm also pretty sure the
>> standard can't be complied with here except by ignoring the
>> usefulness
>> of restrict in a lot of cases.
>
> If the standard explicitly lists the behavior as undefined, and as far as I can tell it does, then we can't be in violation.
>
> Thanks again,
> Hal
>
>>
>> > Regardless, this is useful to consider because if there are no
>> > explicit updates to the object, it would be useful to issue a
>> > warning.
>> >
>> > Thanks again,
>> > Hal
>> >
>> >>
>> >>
>> >> I do realize most of this has to be done in the frontend, but
>> >> still,
>> >> you really are going to have to say in some cases, load alias load
>> >> but
>> >> load noalias store, regardless of what GEP they come from.
>> >>
>> >> Thus, IMHO, you really should attach these to loads/stores, so you
>> >> can
>> >> properly translate restrict into "load-load aliases, unless a
>> >> store
>> >> is
>> >> present into a noaliased pointer, and then all restricted
>> >>  pointers
>> >> that mustalias X now have to follow the rest of the rules"
>> >>
>> >> Note, BTW, that a number of compilers get the above wrong, and
>> >> simply
>> >> implement what most people want restrict to say, which is that
>> >> restricted pointers can't alias each other, rather than what the
>> >> standard actually says, because what the standard says is a bit
>> >> mind-numbing.
>> >>
>> >> GCC gets this right, BTW, by ignoring most of restrict :(
>> >>
>> >
>> > --
>> > Hal Finkel
>> > Postdoctoral Appointee
>> > Leadership Computing Facility
>> > Argonne National Laboratory
>>
>
> --
> Hal Finkel
> Postdoctoral Appointee
> Leadership Computing Facility
> Argonne National Laboratory