[LangRef][AliasAnalysis] Clarify `noalias` affects only modified objects

[jdoerfert]

Summary

We already mention that noalias is modeled after the C99 restrict
qualifier but we did omit one important requirement in the description.
For the restrict guarantees the object affected has to be modified
during the execution of the function, in any way (see 6.7.3.1.4 in [0]).

There are two reasons we want this restriction as well:

1. To match the restrict semantics when we lower it to noalias.
2. To allow the reasoning that the object pointed to by a noalias pointer is not modified through means not derived from this pointer. Hence, following the uses of that pointer is sufficient to determine potential modifications.

The discussion on this came up as part of D73428. In that patch the
Attributor is taught to derive noalias for call site arguments based
on alias queries against objects that are accessed in the callee. This
is possible even if the pointer passed at the call site was "not-noalias".
To simplify the logic there *and* to allow the use of noalias as
described in 2) above, it is beneficial to follow the C restrict
semantics in cases where there might be "read-read-aliases". Note that
AliasAnalysis* queries for read only objects already result in
NoAlias even if the pointers might "alias".

• From this point of view our Alias Analysis is basically a Dependence Analysis.

[0] http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf

[efriedma]

I'm not sure I like the wording; it's a complicated sentence to understand. Can we make it sort of list-like? "for each memory location accessed through a noalias pointer, either: 1. the location is not modified during the execution of the function. 2. all accesses to that memory location are based on the noalias argument". Or something like that.

Semantically, this seems consistent with the way we handle aliasing in other contexts. I think all our current optimizations are consistent with this interpretation.

[aqjune]

Hi,
The term 'object' seems ambiguous to me. For example,

void f(i32* noalias x, i32* noalias y) {
  *x = 1;
  *y = 2;
}

int x[2];
f(&x[0], &x[1]);

If object means an allocation, this should be UB, because x and y are pointing to the same object.
Memory location seems clearer to me.

[jdoerfert]

Tried to simplify the wording by making it two sentences. @efriedma's wording is another option.

[aqjune]

Never mind, I see that the keyword object comes from the alias analysis document. The alias analysis document is using the term object consistently.
I was confused because the term is used at llvm.objectsize intrinsic's LangRef documentation, which seems to refer an allocation unit. gep inbounds text also used term 'allocated object', but I guess it is different from that.

[jdoerfert]

Remove leftover word

[nhaehnle]

I find this phrasing pretty confusing. How about the following:

This indicates that objects accessed via pointer values based on the argument or return value are not modified, during the execution of the function, via pointer values not based on the argument or return value. The attribute on a return value also has additional semantics [...]

Does this exactly capture your intended meaning? If yes, can we please use that instead because it seems much clearer at least to me. If not, can you give an example for why it is different?

[nlopes]

I agree with @aqjune that stating clearly the definition of object in this context.
See this example in the C spec:

For example, the second call of f in g has undefined behavior because each of d[1] through d[49] is accessed through both p and q.

void g(void) {
extern int d[100];
f(50, d + 50, d); // valid
f(50, d + 1, d); // undefined behavior
}

Restrict just guarantees that accesses are to disjoint memory locations, not that they point at different objects (in the sense of they were allocated separately).

[efriedma]

In D74935#1886020, @nhaehnle wrote:

I find this phrasing pretty confusing. How about the following:

This indicates that objects accessed via pointer values based on the argument or return value are not modified, during the execution of the function, via pointer values not based on the argument or return value. [...]

This isn't equivalent. If the memory location is modified, we want to forbid both reads and writes that aren't based on the noalias pointer.

[nhaehnle]

In D74935#1887245, @efriedma wrote:

In D74935#1886020, @nhaehnle wrote:

I find this phrasing pretty confusing. How about the following:

This indicates that objects accessed via pointer values based on the argument or return value are not modified, during the execution of the function, via pointer values not based on the argument or return value. [...]

This isn't equivalent. If the memory location is modified, we want to forbid both reads and writes that aren't based on the noalias pointer.

Oh I see. So another way to put this is:

• If an object is accessed via a pointer based on the noalias argument, then it cannot be modified via other pointer values.
• If an object is modified via a pointer based on the noalias argument, then it cannot be accessed via other pointer values in any way.

Correct? I think it's useful to spell it out like this, because it makes the alias implications clearer (at least to me).

[jdoerfert]

Update language to memory locations instead of objects

[jdoerfert]

In D74935#1887960, @nhaehnle wrote:

In D74935#1887245, @efriedma wrote:

In D74935#1886020, @nhaehnle wrote:

I find this phrasing pretty confusing. How about the following:

This indicates that objects accessed via pointer values based on the argument or return value are not modified, during the execution of the function, via pointer values not based on the argument or return value. [...]

This isn't equivalent. If the memory location is modified, we want to forbid both reads and writes that aren't based on the noalias pointer.

Oh I see. So another way to put this is:

• If an object is accessed via a pointer based on the noalias argument, then it cannot be modified via other pointer values.
• If an object is modified via a pointer based on the noalias argument, then it cannot be accessed via other pointer values in any way.

Correct? I think it's useful to spell it out like this, because it makes the alias implications clearer (at least to me).

I think it might make sense to actually add a page with examples and more details. I don't have a strong opinion on the wording for this short paragraph though.

[arsenm]

Another related point I’ve never been clear on is if a readnone function is allowed to read constant memory

[jdoerfert]

In D74935#1888506, @arsenm wrote:

Another related point I’ve never been clear on is if a readnone function is allowed to read constant memory

Right, ... I basically did assume something for the Attributor readnone deduction but I am certain it is under-specified.
As far as I can tell, current behavior would suggest readnone *is allowed* to read constant memory.

[aqjune]

I agree readnone functions can read constant memory; at least LangRef doesn't fully restrict readnone functions from accessing memory (unless it changesdepends on a state visible to caller). I see that readnone is also attached to a function that loads from/stores to alloca: https://godbolt.org/z/RMAbWa

[efriedma]

Current language seems fine. LGTM

[jeroen.dobbelaere]

Be aware that c99 restrict has a special case for nested restrict that makes the rules stronger:

void f(int* restrict *restrict pA, int* restrict * restrict pB) {
  **pA=**pB;
}

although pA and pB are only read, (c99 6.7.3.1 #4) specifies that, writing to **pA is as if you are also writing to *pA.
Which means for this case, that pA and pB will point to there own sets of objects, and because of that, *pA and *pB also point to their own (different) sets of objects.

[jeroen.dobbelaere]

The reason I bring this up, is that in the full restrict implementation (D68484), the alias analysis will do a recursive analysis, proving that *pA and *pB will never alias, because pA and pB will never alias. But this phrasing will break that assumption.

[jdoerfert]

In D74935#1905026, @jeroen.dobbelaere wrote:

The reason I bring this up, is that in the full restrict implementation (D68484), the alias analysis will do a recursive analysis, proving that *pA and *pB will never alias, because pA and pB will never alias. But this phrasing will break that assumption.

I don't understand how this will break. It will just mean in the IR below we *cannot* assume %0 and %1 are different. Given that the IR below does not represent the nested restrict it seems like this is exactly what we want. After all, we cannot determine if the IR came from your example or one with a single restrict qualifier per argument.

; Function Attrs: nofree norecurse nounwind uwtable
define dso_local void @f(i32** noalias nocapture readonly %0, i32** noalias nocapture readonly %1) local_unnamed_addr #0 {
  %3 = load i32*, i32** %1, align 8, !tbaa !2
  %4 = load i32, i32* %3, align 4, !tbaa !6
  %5 = load i32*, i32** %0, align 8, !tbaa !2
  store i32 %4, i32* %5, align 4, !tbaa !6
  ret void
}

[jeroen.dobbelaere]

Just to give an example:

int foo(int* restrict *pA, int* restrict *pB) {
  int tmp=**pB;
  **pA=42;
  return tmp - **pB; // **pA and **pB can refer to the same objects
}

This gives following llvm-ir code with the 'full noalias' clang version (after optimizations):

; Function Attrs: nofree nounwind uwtable
define dso_local i32 @foo(i32** nocapture %pA, i32** nocapture readonly %pB) local_unnamed_addr #0 !noalias !2 {
entry:
  %0 = load i32*, i32** %pB, noalias_sidechannel i32** undef, align 8, !tbaa !5, !noalias !2
  %1 = tail call i32* @llvm.side.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i64(i32* %0, i8* null, i32** %pB, i32** undef, i64 0, metadata !2), !tbaa !5, !noalias !2
  %2 = load i32, i32* %0, noalias_sidechannel i32* %1, align 4, !tbaa !9, !noalias !2
  %3 = load i32*, i32** %pA, noalias_sidechannel i32** undef, align 8, !tbaa !5, !noalias !2
  %4 = tail call i32* @llvm.side.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i64(i32* %3, i8* null, i32** %pA, i32** undef, i64 0, metadata !2), !tbaa !5, !noalias !2
  store i32 42, i32* %3, noalias_sidechannel i32* %4, align 4, !tbaa !9, !noalias !2
  %5 = load i32, i32* %0, noalias_sidechannel i32* %1, align 4, !tbaa !9, !noalias !2
  %sub = sub nsw i32 %2, %5
  ret i32 %sub
}

When adding 'noalias' to the arguments (my understanding is that this is what the attributer would deduce, as pA and pB are only read):

; Function Attrs: nofree nounwind uwtable
define dso_local i32 @foo(i32** noalias nocapture %pA, i32** noalias nocapture readonly %pB) local_unnamed_addr #0 !noalias !2 {
entry:
  %0 = load i32*, i32** %pB, noalias_sidechannel i32** undef, align 8, !tbaa !5, !noalias !2
  %1 = tail call i32* @llvm.side.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i64(i32* %0, i8* null, i32** %pB, i32** undef, i64 0, metadata !2), !tbaa !5, !noalias !2
  %2 = load i32, i32* %0, noalias_sidechannel i32* %1, align 4, !tbaa !9, !noalias !2
  %3 = load i32*, i32** %pA, noalias_sidechannel i32** undef, align 8, !tbaa !5, !noalias !2
  %4 = tail call i32* @llvm.side.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i64(i32* %3, i8* null, i32** %pA, i32** undef, i64 0, metadata !2), !tbaa !5, !noalias !2
  store i32 42, i32* %3, noalias_sidechannel i32* %4, align 4, !tbaa !9, !noalias !2
  %5 = load i32, i32* %0, noalias_sidechannel i32* %1, align 4, !tbaa !9, !noalias !2
  %sub = sub nsw i32 %2, %5
  ret i32 %sub
}

and reoptimizing, we now get:

; Function Attrs: nofree nounwind uwtable
define dso_local i32 @foo(i32** noalias nocapture %pA, i32** noalias nocapture readonly %pB) local_unnamed_addr #0 !noalias !2 {
entry:
  %0 = load i32*, i32** %pA, noalias_sidechannel i32** undef, align 8, !tbaa !5, !noalias !2
  %1 = tail call i32* @llvm.side.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i64(i32* %0, i8* null, i32** %pA, i32** undef, i64 0, metadata !2), !tbaa !5, !noalias !2
  store i32 42, i32* %0, noalias_sidechannel i32* %1, align 4, !tbaa !9, !noalias !2
  ret i32 0
}

'%sub' is optimized away because the now the alias analyzer deduces that '%pA' and '%pB' cannot refer to the same objects. This implies (because of restrict) that '*%pA' and '*%pB' cannot refer to the same objects and because of that, the 'store i32' could not have interfered with the 'load i32'.

[jdoerfert]

In D74935#1907100, @jeroen.dobbelaere wrote:

Just to give an example:

int foo(int* restrict *pA, int* restrict *pB) {
  int tmp=**pB;
  **pA=42;
  return tmp - **pB; // **pA and **pB can refer to the same objects
}

[...]

*pA and *pB are both restrict qualified pointers, are they not?
If so, why can they point to the same location?

I mean, w/o the side channel stuff the two int * values may alias
even if you have noalias on the arguments (https://godbolt.org/z/J9v_gK).

[jeroen.dobbelaere]

In D74935#1907939, @jdoerfert wrote:

In D74935#1907100, @jeroen.dobbelaere wrote:

Just to give an example:

int foo(int* restrict *pA, int* restrict *pB) {
  int tmp=**pB;
  **pA=42;
  return tmp - **pB; // **pA and **pB can refer to the same objects
}

[...]

*pA and *pB are both restrict qualified pointers, are they not?
If so, why can they point to the same location?

For the original example, *pA and *pB might be the same restrict pointer:

int* restrict pC = ....;
foo(&pC, &pC);

I mean, w/o the side channel stuff the two int * values may alias
even if you have noalias on the arguments (https://godbolt.org/z/J9v_gK).

And that is correct, as *pA might be equal to *pB for that case (even if pA and pB are not equal).

Restrictness adds additional information (ignoring for a moment the 'read only' case (see note *4)):

 // case A
 int * restrict prC;
 int * restrict prD;
 // pC and pD are separate (*1) restrict pointers  => they point to their own separate sets of objects set(prC), set(prD), aka prC != prD (*2)

 // case B
 int * restrict * prpE; 
 int * restrict * prpF;
 // prpE and prpF are _not_ restrict pointers, so prpE could be equal to prpF (prpE == prpF) or not (prpE != prpF)
 // *prpE and *prpF are restrict pointers. When prpE == prpF, they represent the same restrict pointer.
 // *prpE could point to prC or prD or a different restrict pointer => set(*prpE) =union(set(prC), set(prD), ...)
 // also *prpF can point to union(set(prC), set(prD), ...)

 // case C
 int * restrict * restrict prprG;  
 int * restrict * restrict prprH;
 // prprG and prprH are separate (*3) restrict pointers => they point to their own separate sets of objects set(prprG) and set(prprH)
 // because of that: prprG != prprH
 // and *prprG and *prprH represent also separate (see previous line) restrict points
 // So *prprG and *prprH must point to their own separate sets of objects set(*prprG) and set(*prprH) 

 // The difference between between case B and case C is that in B, prpE could be equal to prpF (mayAlias), and because of that, *prpE could be equal to *prpF.
 // By proving that prprG != prprH, it automatically follows that *prprG != *prprH (except for (*4))

// Notes:
// (*1)  &prC != &prD 
// (*2) it actually is: for all i,j for which prC[i] and prD[j] are 'valid',  &prC[i] != &prD[j]
// (*3)  &prprG != &prprH
// (*4) The restrict definition contains a relaxation when restrict pointers are only used for reading memory: 
//   In that case, separate restrict pointers are allowed to point to the same set of objects... except for:
//  But: it also states that (6.7.3.1 paragraph 4 : '.. Every  access  that modifies X shall be considered also to modify P,for the purposes of this subclause. .. '
//  Which means that if your write to **prprG, it is _as if_ you also write to *prprG and because of that, both prprG and *prprG must point to their own set of objects set(prprG) and set(*prprG)
//  and those sets must also be different from set(prprH) and set(*prprH)

Now, in the original example, we have 'case B'. pA could be equal to pB (mayAlias), and because of that, *pA could be equal to *pB.

int foo(int* restrict *pA, int* restrict *pB);

When we can proof that pA != pB (noalias), then *pA and *pB represent different restrict pointers and *pA != *pB. (different restrict pointers point to their own set of objects)

So, adding the 'noalias' attribute to %pA and %pB will change the behavior of foo().

hmm... this explanation is maybe getting too long ?
The short conclusion should be:

• adding 'noalias' to a pointer argument, because it is only used to read memory, might lead to 'wrong code'
• two 'noalias' pointer arguments should not overlap

or relaxed:

• two 'noalias' pointer arguments can only overlap if they (at any level of indirection) are never used to write to memory.

[jdoerfert]

In D74935#1908607, @jeroen.dobbelaere wrote:

[...]
So, adding the 'noalias' attribute to %pA and %pB will change the behavior of foo().

hmm... this explanation is maybe getting too long ?
The short conclusion should be:

• adding 'noalias' to a pointer argument, because it is only used to read memory, might lead to 'wrong code'
• two 'noalias' pointer arguments should not overlap

or relaxed:

• two 'noalias' pointer arguments can only overlap if they (at any level of indirection) are never used to write to memory.

I think we conflate two things here:

1. The modifications to the LangRef which should be in accordance with the C standard (at least I haven't seen you contradict the new wording directly).
2. The extended noalias deduction D73428.

If you look at the commit message in D73428, it says that noalias is not just derived for all readonly arguments.
In your example we access unknown memory, e.g., **pA=42, so case (1) cannot be applied.
For case (2) we need to show that the loads of pA and pB do not alias, which we cannot.

WDYT?

[jeroen.dobbelaere]

In D74935#1908665, @jdoerfert wrote:

I think we conflate two things here:

1. The modifications to the LangRef which should be in accordance with the C standard (at least I haven't seen you contradict the new wording directly).

imho, the proposed wording is still confusing, and does not handle the case with the extra indirections.
Unless the 'by any means' was meant to also include the '.. Every access that modifies X shall be considered also to modify P,for the purposes of this subclause. .. ' from the restrict specification.
If that is the idea, we should mention it explicitly.

2. The extended noalias deduction D73428.

If you look at the commit message in D73428, it says that noalias is not just derived for all readonly arguments.
In your example we access unknown memory, e.g., **pA=42, so case (1) cannot be applied.
For case (2) we need to show that the loads of pA and pB do not alias, which we cannot.

That sounds good. Is there also a testcase (similar to D74935#1907100 or D74935#1907939 ) that explicitly checks that 'noalias' is not deduced ?

[jdoerfert]

In D74935#1909054, @jeroen.dobbelaere wrote:

In D74935#1908665, @jdoerfert wrote:

I think we conflate two things here:

1. The modifications to the LangRef which should be in accordance with the C standard (at least I haven't seen you contradict the new wording directly).

imho, the proposed wording is still confusing, and does not handle the case with the extra indirections.
Unless the 'by any means' was meant to also include the '.. Every access that modifies X shall be considered also to modify P,for the purposes of this subclause. .. ' from the restrict specification.
If that is the idea, we should mention it explicitly.

I would say that once we get modeling for indirect restrict we can adapt the lang ref accordingly. For now there is only have outer level restrict/noalias.

2. The extended noalias deduction D73428.

If you look at the commit message in D73428, it says that noalias is not just derived for all readonly arguments.
In your example we access unknown memory, e.g., **pA=42, so case (1) cannot be applied.
For case (2) we need to show that the loads of pA and pB do not alias, which we cannot.

That sounds good. Is there also a testcase (similar to D74935#1907100 or D74935#1907939 ) that explicitly checks that 'noalias' is not deduced ?

I'll add one :)

[jeroen.dobbelaere]

In D74935#1909909, @jdoerfert wrote:

I would say that once we get modeling for indirect restrict we can adapt the lang ref accordingly. For now there is only have outer level restrict/noalias.

Why not try to get right now ? The first reason that you give for the change in wording is

'1. To match the restrict semantics when we lower it to noalias.'

Currently there is no mechanism to accurately describe nested restrict pointers in LLVM-IR. imho, that means that
we should adapt the wording in a more specific way. Something like:

  This guarantee only holds for memory locations that are *modified*, by any means, during the execution the function.
+ Note that, just like C99 restrict, in this context, memory locations whose content is used as a pointer value to modify a memory location,
+ are also considered to modify the former memory locations.
  The attribute....

2. The extended noalias deduction D73428.

[..]

That sounds good. Is there also a testcase (similar to D74935#1907100 or D74935#1907939 ) that explicitly checks that 'noalias' is not deduced ?

I'll add one :)

thanks !

[jdoerfert]

In D74935#1915311, @jeroen.dobbelaere wrote:

In D74935#1909909, @jdoerfert wrote:

I would say that once we get modeling for indirect restrict we can adapt the lang ref accordingly. For now there is only have outer level restrict/noalias.

Why not try to get right now ? The first reason that you give for the change in wording is

'1. To match the restrict semantics when we lower it to noalias.'

Right. Match the semantics of what we lower to noalias, not of everything we do not lower yet.

Currently there is no mechanism to accurately describe nested restrict pointers in LLVM-IR. imho, that means that
we should adapt the wording in a more specific way. Something like:

We also have no restrict on nested pointers. Since we only model (=use) restrict on the outermost level I don't see a problem not to talk about the inner levels.
That said, we have to add wording as we add support.

  This guarantee only holds for memory locations that are *modified*, by any means, during the execution the function.
+ Note that, just like C99 restrict, in this context, memory locations whose content is used as a pointer value to modify a memory location,
+ are also considered to modify the former memory locations.
  The attribute....

The reason is that we need to come up and agree on clear, non-confusing, wording.

llvm/docs/LangRef.rst

``align <n>``
     ``byval`` attribute, which are documented there.
 
 .. _noalias:
 
 ``noalias``
     This indicates that objects accessed via pointer values
     :ref:`based <pointeraliasing>` on the argument or return value are not also
     accessed, during the execution of the function, via pointer values not
-    *based* on the argument or return value. The attribute on a return value
-    also has additional semantics described below. The caller shares the
-    responsibility with the callee for ensuring that these requirements are met.
-    For further details, please see the discussion of the NoAlias response in
-    :ref:`alias analysis <Must, May, or No>`.
+    *based* on the argument or return value. This guarantee only holds for
+    objects that are *modified*, by any means, during the execution of the
+    function. The attribute on a return value also has additional semantics
+    described below. The caller shares the responsibility with the callee for
+    ensuring that these requirements are met.  For further details, please see
+    the discussion of the NoAlias response in :ref:`alias analysis <Must, May,
+    or No>`.
 
     Note that this definition of ``noalias`` is intentionally similar
     to the definition of ``restrict`` in C99 for function arguments.
 
     For function return values, C99's ``restrict`` is not meaningful,
     while LLVM's ``noalias`` is. Furthermore, the semantics of the ``noalias``
     attribute on return values are stronger than the semantics of the attribute
     when used on function arguments. On function return values, the ``noalias``