[RFC] Scoped no-alias metadata

[Finkel_Hal_J]

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

[Chandler_Carruth]

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?

[Finkel_Hal_J]

From: "Chandler Carruth" <chandlerc@google.com>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: "LLVM Developers Mailing List" <llvmdev@cs.uiuc.edu>, "Clang Developers" <cfe-dev@cs.uiuc.edu>, "Dan Gohman"
<dan433584@gmail.com>
Sent: Sunday, December 2, 2012 7:02:52 PM
Subject: Re: [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.

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

[Daniel_Berlin1]

From: "Chandler Carruth" <chandlerc@google.com>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: "LLVM Developers Mailing List" <llvmdev@cs.uiuc.edu>, "Clang Developers" <cfe-dev@cs.uiuc.edu>, "Dan Gohman"
<dan433584@gmail.com>
Sent: Sunday, December 2, 2012 7:02:52 PM
Subject: Re: [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.

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.

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

[Finkel_Hal_J]

From: "Daniel Berlin" <dberlin@dberlin.org>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: "Chandler Carruth" <chandlerc@google.com>, "Clang Developers" <cfe-dev@cs.uiuc.edu>, "LLVM Developers Mailing
List" <llvmdev@cs.uiuc.edu>
Sent: Sunday, December 2, 2012 11:21:00 PM
Subject: Re: [LLVMdev] [RFC] Scoped no-alias metadata

>> From: "Chandler Carruth" <chandlerc@google.com>
>> To: "Hal Finkel" <hfinkel@anl.gov>
>> Cc: "LLVM Developers Mailing List" <llvmdev@cs.uiuc.edu>, "Clang
>> Developers" <cfe-dev@cs.uiuc.edu>, "Dan Gohman"
>> <dan433584@gmail.com>
>> Sent: Sunday, December 2, 2012 7:02:52 PM
>> Subject: Re: [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.

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. As a result, we can define it to mean what the programmer would expect, right?

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

[Krzysztof_Parzyszek]

If the object isn't modified, then none of this matters. Nobody cares about aliasing between loads. What all this means is that is P is a restrict pointer that points to X, then no stores can modify X, unless they use addresses based on P. In other words, loads/stores to locations based on P can be aliased with each other, but not with any other loads or stores. This implies that we need grouping of loads and stores to properly isolate those based on P from all the others. Attaching information to loads and stores individually may not be sufficient.

-Krzysztof

[Daniel_Berlin1]

From: "Daniel Berlin" <dberlin@dberlin.org>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: "Chandler Carruth" <chandlerc@google.com>, "Clang Developers" <cfe-dev@cs.uiuc.edu>, "LLVM Developers Mailing
List" <llvmdev@cs.uiuc.edu>
Sent: Sunday, December 2, 2012 11:21:00 PM
Subject: Re: [LLVMdev] [RFC] Scoped no-alias metadata

>> From: "Chandler Carruth" <chandlerc@google.com>
>> To: "Hal Finkel" <hfinkel@anl.gov>
>> Cc: "LLVM Developers Mailing List" <llvmdev@cs.uiuc.edu>, "Clang
>> Developers" <cfe-dev@cs.uiuc.edu>, "Dan Gohman"
>> <dan433584@gmail.com>
>> Sent: Sunday, December 2, 2012 7:02:52 PM
>> Subject: Re: [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.

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.

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.

I'm actually not oppose to doing whatever we want, as long as we document it.

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.

[Daniel_Berlin1]

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

If the object isn't modified, then none of this matters. Nobody cares about
aliasing between loads.

It's funny.
This was essentially my argument on the GCC list about 4 years ago (or
maybe it's longer now. i'm getting old), and someone brought up some
good examples where they cared about load-load aliasing, even besides
loop dependences analysis.
Let me see if i can hunt them down in the mailing list archives.

What all this means is that is P is a restrict
pointer that points to X, then no stores can modify X, unless they use
addresses based on P. In other words, loads/stores to locations based on P
can be aliased with each other, but not with any other loads or stores.

Yes.

This implies that we need grouping of loads and stores to properly isolate
those based on P from all the others. Attaching information to loads and
stores individually may not be sufficient.

Yes.

[Krzysztof_Parzyszek]

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

[Finkel_Hal_J]

From: "Daniel Berlin" <dberlin@dberlin.org>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: "Chandler Carruth" <chandlerc@google.com>, "Clang Developers" <cfe-dev@cs.uiuc.edu>, "LLVM Developers Mailing
List" <llvmdev@cs.uiuc.edu>
Sent: Monday, December 3, 2012 12:10:55 PM
Subject: Re: [LLVMdev] [RFC] Scoped no-alias metadata

>> From: "Daniel Berlin" <dberlin@dberlin.org>
>> To: "Hal Finkel" <hfinkel@anl.gov>
>> Cc: "Chandler Carruth" <chandlerc@google.com>, "Clang Developers"
>> <cfe-dev@cs.uiuc.edu>, "LLVM Developers Mailing
>> List" <llvmdev@cs.uiuc.edu>
>> Sent: Sunday, December 2, 2012 11:21:00 PM
>> Subject: Re: [LLVMdev] [RFC] Scoped no-alias metadata
>>
>> >> From: "Chandler Carruth" <chandlerc@google.com>
>> >> To: "Hal Finkel" <hfinkel@anl.gov>
>> >> Cc: "LLVM Developers Mailing List" <llvmdev@cs.uiuc.edu>,
>> >> "Clang
>> >> Developers" <cfe-dev@cs.uiuc.edu>, "Dan Gohman"
>> >> <dan433584@gmail.com>
>> >> Sent: Sunday, December 2, 2012 7:02:52 PM
>> >> Subject: Re: [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.
>>
>> 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. 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

[Finkel_Hal_J]

From: "Krzysztof Parzyszek" <kparzysz@codeaurora.org>
To: llvmdev@cs.uiuc.edu
Sent: Monday, December 3, 2012 1:30:31 PM
Subject: Re: [LLVMdev] [RFC] Scoped no-alias metadata

>
> [...] 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

[Dan_Gohman]

LLVM IR already has faced this problem, with the noalias argument
attribute. My solution for this was to define NoAlias to ignore
load-load dependencies, on the theory that clients which would care
about load-load dependencies should know that they care, so they could
use a different API or pass a special flag into the AliasAnalysis API.

The current definition has a few vague aspects, but as far as I know
the basic concept works.

Dan

[Daniel_Berlin1]

From: "Daniel Berlin" <dberlin@dberlin.org>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: "Chandler Carruth" <chandlerc@google.com>, "Clang Developers" <cfe-dev@cs.uiuc.edu>, "LLVM Developers Mailing
List" <llvmdev@cs.uiuc.edu>
Sent: Monday, December 3, 2012 12:10:55 PM
Subject: Re: [LLVMdev] [RFC] Scoped no-alias metadata

>> From: "Daniel Berlin" <dberlin@dberlin.org>
>> To: "Hal Finkel" <hfinkel@anl.gov>
>> Cc: "Chandler Carruth" <chandlerc@google.com>, "Clang Developers"
>> <cfe-dev@cs.uiuc.edu>, "LLVM Developers Mailing
>> List" <llvmdev@cs.uiuc.edu>
>> Sent: Sunday, December 2, 2012 11:21:00 PM
>> Subject: Re: [LLVMdev] [RFC] Scoped no-alias metadata
>>
>> >> From: "Chandler Carruth" <chandlerc@google.com>
>> >> To: "Hal Finkel" <hfinkel@anl.gov>
>> >> Cc: "LLVM Developers Mailing List" <llvmdev@cs.uiuc.edu>,
>> >> "Clang
>> >> Developers" <cfe-dev@cs.uiuc.edu>, "Dan Gohman"
>> >> <dan433584@gmail.com>
>> >> Sent: Sunday, December 2, 2012 7:02:52 PM
>> >> Subject: Re: [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.
>>
>> 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.

[Daniel_Berlin1]

On Mon, Dec 3, 2012 at 6:29 AM, Krzysztof Parzyszek

If the object isn't modified, then none of this matters. Nobody cares about
aliasing between loads.

It's funny.
This was essentially my argument on the GCC list about 4 years ago (or
maybe it's longer now. i'm getting old), and someone brought up some
good examples where they cared about load-load aliasing, even besides
loop dependences analysis.
Let me see if i can hunt them down in the mailing list archives.

LLVM IR already has faced this problem, with the noalias argument
attribute. My solution for this was to define NoAlias to ignore
load-load dependencies, on the theory that clients which would care
about load-load dependencies should know that they care, so they could
use a different API or pass a special flag into the AliasAnalysis API.

The current definition has a few vague aspects, but as far as I know
the basic concept works.

SGTM.
I have no particular problem with this, as long as we are consistent
and explain this is the case

[Finkel_Hal_J]

From: "Daniel Berlin" <dberlin@dberlin.org>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: "Chandler Carruth" <chandlerc@google.com>, "Clang Developers" <cfe-dev@cs.uiuc.edu>, "LLVM Developers Mailing
List" <llvmdev@cs.uiuc.edu>
Sent: Monday, December 3, 2012 1:51:48 PM
Subject: Re: [LLVMdev] [RFC] Scoped no-alias metadata

>> From: "Daniel Berlin" <dberlin@dberlin.org>
>> To: "Hal Finkel" <hfinkel@anl.gov>
>> Cc: "Chandler Carruth" <chandlerc@google.com>, "Clang Developers"
>> <cfe-dev@cs.uiuc.edu>, "LLVM Developers Mailing
>> List" <llvmdev@cs.uiuc.edu>
>> Sent: Monday, December 3, 2012 12:10:55 PM
>> Subject: Re: [LLVMdev] [RFC] Scoped no-alias metadata
>>
>> >> From: "Daniel Berlin" <dberlin@dberlin.org>
>> >> To: "Hal Finkel" <hfinkel@anl.gov>
>> >> Cc: "Chandler Carruth" <chandlerc@google.com>, "Clang
>> >> Developers"
>> >> <cfe-dev@cs.uiuc.edu>, "LLVM Developers Mailing
>> >> List" <llvmdev@cs.uiuc.edu>
>> >> Sent: Sunday, December 2, 2012 11:21:00 PM
>> >> Subject: Re: [LLVMdev] [RFC] Scoped no-alias metadata
>> >>
>> >> >> From: "Chandler Carruth" <chandlerc@google.com>
>> >> >> To: "Hal Finkel" <hfinkel@anl.gov>
>> >> >> Cc: "LLVM Developers Mailing List" <llvmdev@cs.uiuc.edu>,
>> >> >> "Clang
>> >> >> Developers" <cfe-dev@cs.uiuc.edu>, "Dan Gohman"
>> >> >> <dan433584@gmail.com>
>> >> >> Sent: Sunday, December 2, 2012 7:02:52 PM
>> >> >> Subject: Re: [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.
>> >>
>> >> 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. 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

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

Alright, I'm being slightly sarcastic, but nevertheless...

Thanks again,
Hal

[Krzysztof_Parzyszek]

I don't see why this matters anyways. We can act as if the object was always modified (by _some_ means). The standard requires that (A)=>(B) is true, which is trivially satisfied if A is false.

-Krzysztof

[Daniel_Berlin1]

From: "Daniel Berlin" <dberlin@dberlin.org>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: "Chandler Carruth" <chandlerc@google.com>, "Clang Developers" <cfe-dev@cs.uiuc.edu>, "LLVM Developers Mailing
List" <llvmdev@cs.uiuc.edu>
Sent: Monday, December 3, 2012 1:51:48 PM
Subject: Re: [LLVMdev] [RFC] Scoped no-alias metadata

>> From: "Daniel Berlin" <dberlin@dberlin.org>
>> To: "Hal Finkel" <hfinkel@anl.gov>
>> Cc: "Chandler Carruth" <chandlerc@google.com>, "Clang Developers"
>> <cfe-dev@cs.uiuc.edu>, "LLVM Developers Mailing
>> List" <llvmdev@cs.uiuc.edu>
>> Sent: Monday, December 3, 2012 12:10:55 PM
>> Subject: Re: [LLVMdev] [RFC] Scoped no-alias metadata
>>
>> >> From: "Daniel Berlin" <dberlin@dberlin.org>
>> >> To: "Hal Finkel" <hfinkel@anl.gov>
>> >> Cc: "Chandler Carruth" <chandlerc@google.com>, "Clang
>> >> Developers"
>> >> <cfe-dev@cs.uiuc.edu>, "LLVM Developers Mailing
>> >> List" <llvmdev@cs.uiuc.edu>
>> >> Sent: Sunday, December 2, 2012 11:21:00 PM
>> >> Subject: Re: [LLVMdev] [RFC] Scoped no-alias metadata
>> >>
>> >> >> From: "Chandler Carruth" <chandlerc@google.com>
>> >> >> To: "Hal Finkel" <hfinkel@anl.gov>
>> >> >> Cc: "LLVM Developers Mailing List" <llvmdev@cs.uiuc.edu>,
>> >> >> "Clang
>> >> >> Developers" <cfe-dev@cs.uiuc.edu>, "Dan Gohman"
>> >> >> <dan433584@gmail.com>
>> >> >> Sent: Sunday, December 2, 2012 7:02:52 PM
>> >> >> Subject: Re: [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.
>> >>
>> >> 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