[LLVMdev] [RFC] Scoped no-alias metadata

[Daniel Berlin]

On Mon, Dec 3, 2012 at 12:26 PM, 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 1:51:48 PM
>> Subject: Re: [LLVMdev] [RFC] Scoped no-alias metadata
>>
>> 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.
>
> Okay, thank you for explaining this. You're right, the paragraph explicitly calls (B) "requirements", but does not classify (A) as such.
>
> We both agree, however, that the compiler has no way of knowing whether or not (A) might be satisfied (because the standard says, "by any means
> ", which seems to allow the requirement to be satisfied by mechanisms outside the scope of the standard). That being the case, safety demands that the compiler assume that (A) is satisfied.


I agree, I just want us to understand what we are doing is technically
not standards-compliant (because the standard is very likely defective
in this particular case), and make sure we document it.

>What's worse, (A) is actually a statement about the dynamic state of the execution environment of the program; and more than that, the >standard simply states that the value needs to be "modified", not that such a modification needs to have any affect on the execution of >the C program -- the value could be changed and then changed back -- a memory refresh cycle might count ;)

Yes.  It asks you to verify the impossible.

>
> And in case you think I'm just being sarcastic, the standard says in 3.1:
> "NOTE 2: "Modify" includes the case where the new value being stored is the same as the previous value."
>

Sigh
:)

> Alright, I'm being slightly sarcastic, but nevertheless... ;)
>
> Thanks again,
> Hal
>
>>
>>
>>
>>
>>
>> > 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
>>
>
> --
> Hal Finkel
> Postdoctoral Appointee
> Leadership Computing Facility
> Argonne National Laboratory