c compiler-optimization restrict-qualifier

Is the C restrict qualifier transitive?

While there are many examples [1][2][3] that address how the restrict keyword works, I am not completely sure if the restrictified relation is transitive on the pointers that it can point to. For instance, the following code declares a structure that contains an integer and a pointer to an integer.

typedef struct container_s {
  int x;
  int *i;
} container_s;


int bar(container_s *c, int *i) {
  int* tmp = c->i;
  *tmp = 5;      
  *i = 4;
  return *tmp;
}

int main(){
  return 0;
}

Does the compiler need an extra load instruction for the last access of tmp (the returned value) because it cannot infer that *i and *tmp do not alias?

If so, would this new definition fix that load?

int bar(container_s *c, int* restrict i) { ... }

EDIT

This case int bar(container_s *c, int * restrict i) { ... } removes the extract load when I produce LLVM IR (clang -S -O3 -emit-llvm). However, I do not understand why the next two modifications do not remove that final load when:

I update the definition of the function (is the restrict transitively considered for c->i?) to:
```
int bar(container_s * restrict c, int *i) { ... }
```

I update the structure as below (Why cannot the compiler infer that there is no need for an extra load?):

typedef struct container_s {
  int x;
  int * restrict i;
} container_s;

int bar(container_s *c, int *i) { ... }

Solution

I'm having trouble seeing how transitivity applies here, but I can speak to your example.

Does the compiler need an extra load instruction for the last access of tmp (the returned value) because it cannot infer that *i and *tmp do not alias?

The compiler indeed cannot safely infer that *i and *tmp do not alias in your original code, as you have aptly demonstrated. It does not follow that the compiler specifically needs emit the load instruction implied by the abstract machine semantics of the * operator, but it does need to take care to deal with the aliasing issue somehow.

If so, would [restrict-qualifying parameter i] fix that load?

Adding restrict-qualification to parameter i in the function definition places the following additional requirement on the behavior of the program (derived from the text of C2011, 6.7.3.1/4): during each execution of bar(), because i is (trivially) based on i, and *i is used to access the object it designates, and that designated object is modified during the execution of bar() (via *i at least), every other lvalue used to access the object designated by *i shall also have its address based on i.

*tmp is accessed, and its address, tmp, is not based on i. Therefore, if i == tmp (that is, if on some call, i == c->i) then the program fails to conform. Its behavior is undefined in that case. The compiler is free to emit code that assumes the program conforms, so in particular, in the restrict-qualified case it can emit code that assumes both that the statement

  *i = 4;

does not modify *tmp, and that the statement

  *tmp = 5;

does not modify *i. Indeed, it seems consistent with the definition and express intent of restrict that compilers be free to make precisely those assumptions.

In particular, if the compiler chooses to handle the possibility of aliasing in the original code by performing the possibly-redundant load of *tmp, then in the restrict-qualified version it might choose to optimize by omitting that load. However, the resulting machine code is by no means required to differ in any way between the two cases. That is, you cannot, in general, rely on the compiler to make use of all the optimizations available to it.

Update:

The followup questions ask why clang does not perform a particular optimization under particular circumstances. Before anything else, it is essential to reiterate that C compilers have no responsibility whatever for performing any particular optimization that may be possible for given source code, except as they themselves document. Therefore, one generally cannot draw any conclusions from the fact that a given optimization is not performed, and it is rarely useful to ask why a given optimization was not performed.

About as far as you can go -- and I am interpreting the questions in this light -- is to ask whether the optimization in question is one that a conforming compiler could have performed. In this case the standard underscores that by taking the unusual step of clarifying that restrict imposes no optimization obligation on implementations:

A translator is free to ignore any or all aliasing implications of uses of restrict.

(C2011, 6.7.3.1/6)

With that said, on to the questions.

In this code variant, *tmp is an lvalue whose address is based on restrict-qualified pointer c. The object it designates is accessed via that lvalue within the scope of the function, and also modified within that scope (via *tmp, so the compiler can certainly see it). The address of *i is not based on c, so the compiler is free to assume that *i does not alias *tmp, just as in the original question.
This case is different. Although it is permitted to restrict-qualify struct members, restrict has effect only when it qualifies an ordinary identifier (C2011, 6.7.3.1/1), which struct member names are not (C2011, 6.2.3). In this case, restrict has no effect, and to ensure conforming behavior, the compiler must account for the possibility that c->i and *i (and *tmp) are aliases.