Is this redundant load/store optimization allowed in C99?

Question

Consider the following:

extern void bar(int *restrict);

void foo(int *restrict p) {
  int tmp;
  bar(&tmp);
  *p = tmp;
}

Does C99 spec permit to optimize foo to the following?

extern void bar(int *restrict);

void foo(int *restrict p) {
  bar(p);
}

I tried gcc, Clang and Intel Compiler in -O3 mode and neither generated code which reflects the above optimization. This lead me to suspect that this optimization breaks the spec. If it is not allowed, where does it say so in the spec?

Note: my question is inspired by this SO question

I can see that these snippets might not be equivalent to each other if they weren't `restrict` pointers. But I don't know why these aren't being optimized in the `restrict` case. — Oliver Charlesworth, Jun 04 '13 at 08:50
What if `foo` gets a pointer to write-only memory (e.g. memory mapped I/O)? Without the optimization it's OK, but no with it - `bar` may write-read-write. — ugoren, Jun 04 '13 at 12:33
@ugoren: For such pointers, you absolutely should use the `volatile` qualifier. Otherwise, the compiler is allowed to optimize it anyway (in some cases, like knowing the body of `bar`). — jpalecek, Jun 04 '13 at 13:11
@jpalecek, `foo` only writes to `*p` once, so the compiler can't optimize it away. Surely it doesn't know the body of `bar`, which is declared `extern`. So here, `bar` could serve as an adapter between a write-only pointer, and the `bar` function, which may be unsafe in such a case. — ugoren, Jun 04 '13 at 18:48

score 18 · Accepted Answer · answered Jun 06 '13 at 09:44

18

The answer is a definitive NO, this is not allowed.

Consider what happens if foo and bar are mutually recursive. For example, this implementation of bar:

void bar(int *restrict p)
{
    static int q;
    if (p == &q) {
        printf("pointers match!\n");
    } else if (p == NULL) {
        foo(&q);
    }
}

bar never dereferences p, so the restrict qualifier is irrelevant. It is obvious that the static variable q cannot have the same address as the automatic variable tmp in foo. Therefore, foo cannot pass its parameter back to bar, and the given optimization is not allowed.

answered Jun 06 '13 at 09:44

ridiculous_fish

17,273
1
54
61

1

Great! A more simple "bar" that behaves differently with the optimization could be "void bar(int * restrict p){ if (p == NULL) printf("NULL!\n"); }" – Giuseppe Guerrini Jun 06 '13 at 21:11
1

@GiuseppeGuerrini: but that would only make a difference when the argument to foo is NULL, which would invoke undefined behaviour. – Oliver Charlesworth Jun 09 '13 at 11:02
@Oli Charlesworth So let's add an "exit(0)" after the printf. The point is that (as "ridiculous_fish" has well explained) the compiler cannot freely change the value of a function parameter if the implementation of the function isn't known. C parameters are "by value", and the compiler must assure that the function receives the parameter value consistently. In the case of pointers the value is an address, but what the function does with that address is a matter of the function implementation. (continue) – Giuseppe Guerrini Jun 10 '13 at 06:41
@Oli Charleswort (continue) An extreme example is "void bar(int *restric p) { printf("p=%p\n", (void *)p); }". The output in the optimized version would be different. – Giuseppe Guerrini Jun 10 '13 at 06:53

ugoren · Answer 2 · 2013-06-06T09:23:01.840

1

For the compiler to do the optimization, it must be sure that regardless of how bar is implemented, and how foo is called, well-defined behavior will not change.
Since the implementation of bar and the call to foo are unknown to the compiler, when it compiles foo, the theoretical existence of such a case is enough to prevent the optimization, even if it doesn't happen in reality.

Here's an example for such a situation. The important points are: 1. The parameter p points to write-only memory (e.g. memory mapped I/O).
2. bar is unsafe for use with a write-only pointer (maybe it writes it and then reads it back, expecting the same value).
The function foo is safe for use with a write-only pointer, because it only writes p. This is true even if bar is unsafe, because bar never gets p. With the suggested optiomization, bar does get p, which may cause trouble.

Here's an example for the file containing bar and the call to foo.

static int increment;

void bar(int *restrict p) {
    (*p)=0;
    if (increment) (*p)++;
}

void foo(int *restrict p);

int main(int ac, char **av) {
    int *p = get_io_addr();    /* Get a write-only memory mapped I/O address */
    increment = atoi(av[1]);
    foo(p);
    return 0;
}

edited Jun 06 '13 at 09:23

answered Jun 05 '13 at 07:45

ugoren

16,023
3
35
65

1

Good point. But please note that a (actually very very smart) compiler could translate "bar" into something like "*p = increment ? 1: 0;". Unless the pointer is "volatile", but it's not our case :-( – Giuseppe Guerrini Jun 05 '13 at 08:17
@GiuseppeGuerrini so GCC is a very very smart compiler :) – zr. Jun 05 '13 at 09:06
@GiuseppeGuerrini, But the compiler compiling `foo` can't assume that the compiler compiling `bar` will make this optimization, right? – ugoren Jun 05 '13 at 10:22
1

@urogen: If the pointer is not "volatile", the compiler is free to optimize its use, only the correctness of the final value of "*p" must be assured, regardless the number of times the variable is actually read or written inside "bar". In the case you showed, p MUST be declared "volatile", since optimizations on it will not work. In particular, in your example you have a write-only address, it should not be read at all! If you don't inform the compiler of this issue (by "volatile") it can assume that "*p = 1; x=*p; *p=2" is equivalent to "x=1; *p=2". – Giuseppe Guerrini Jun 05 '13 at 12:37
@GiuseppeGuerrini, which `p` needs to be declared volatile? Surely not in `bar`, which must not be used with a write-only pointer (and in my example, it isn't). In `foo`, I don't see why volatile is needed - it only accesses `p` once. – ugoren Jun 05 '13 at 14:15
@ugoren you should use "volatile" wherever the write-only pointer is used: in "foo", because the function must know that it's manipulating a write-only address (or "foo" could be optimized in the second form, although it's unlikely), and (for correctness - good practice) in main. "bar" doesn't need it, as long as you use the first version of "foo", because "bar" receives "&tmp" as parameter – Giuseppe Guerrini Jun 05 '13 at 14:54
@GiuseppeGuerrini, bottom line, you're saying that a write-only pointer must be declared volatile, even when accessed exactly once (as in `foo` here). I think it's OK not to declare it volatile, as long as your code doesn't write it. The answer must be in the standard. – ugoren Jun 05 '13 at 15:03
let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/31275/discussion-between-giuseppe-guerrini-and-ugoren) – Giuseppe Guerrini Jun 05 '13 at 18:03

score 1 · Answer 3 · edited May 23 '17 at 10:29

A brief reading of this SO question and this wikipedia enrty suggests that the restrict keyword can only have effect in the arguments of a function. However, reading the C99 standard, section 6.7.3.1 in particular, makes it clear that the restrict applies to the whole context in which the restrict is used. So by using

void foo(int *restrict p);

you are guaranteeing that the only reading of and writing into the memory block pointed to by p will be via p.

However, even with this information, when compiling foo, the compiler has no idea what bar will do with the information it is sent. For example, consider:

void bar (unsigned long long int *p) {
    *p = ((unsigned long long int) p) % 2000;
    }

The result is dependent on the value of the pointer set, which means that when compiling foo the optimisation assumption you suggest cannot definitively be made, as the result will be different if the optimisation you suggest is made.

`restrict` is not only about parameters to the same function. For example, giving `foo` a pointer to a global variable, which is accessed in `bar`, violates the requirement of `restrict`. — ugoren, Jun 06 '13 at 09:24
Also, your last example has two problems - first, you can't apply `%` to a pointer. Second, the behavior isn't well-defined with the unoptimized `foo`, so optimization won't break anything. — ugoren, Jun 06 '13 at 10:02

Giuseppe Guerrini · Answer 4 · 2013-06-04T12:53:29.910

0

The two codes are NOT equivalent: in the first case, the function "bar" receives the pointer (and probably uses the value) of "tmp", that is a local (and non initalised!) variable. In the second case, "bar" works directly on "p", and in general it will find a different value in "*p". Things would be different if the "bar" function declared its parameter as "output only" (e.g. in M$ VS via the OUT macro), since the initial value of the variable would be (supposed to be) ignored. (NOTE: most VS versions actually define the OUT macro as nothing at all. Too sad...)

edited Jun 04 '13 at 12:53

answered Jun 04 '13 at 12:33

Giuseppe Guerrini

4,274
17
32

Why do you assume that bar reads from its argument before writing to it? Let's only look at the cases where there is no undefined behavior which the C99 spec covers. – zr. Jun 04 '13 at 13:16
The problem is that THE COMPILER cannot assume that "bar" writes *p before reading it. That's why it cannot remove the reference to "tmp". – Giuseppe Guerrini Jun 04 '13 at 13:37
2

@GiuseppeGuerrini I think the compiler can assume that if `bar` uses its argument at all, then it must first write to it. If `bar` reads before it writes, the behaviour is undefined, so everything the compiler does is valid. If `bar` writes first, both variants produce the same observable behaviour, as far as I can see. – Daniel Fischer Jun 04 '13 at 14:05
IMHO the compiler can't take any assumption. Let's consider this implementation of "bar": void bar(int *restrict p) { printf("%d\n", *p); *p=1234; } . The function is expected to print the original value of *p instead of 1234; – Giuseppe Guerrini Jun 04 '13 at 14:10
2

If the argument is the address of an uninitialised automatic variable, the behaviour of that is undefined. The compiler can assume that your code doesn't invoke UB. – Daniel Fischer Jun 04 '13 at 14:43
1

Actually, a good compiler should produce a warning (and, yes, the behaviour is undefined). Anyway teh compiler should not apply any particular optimization since in general it doesn't know what "bar" does with the address of tmp. – Giuseppe Guerrini Jun 04 '13 at 15:28
"If the argument is the address of an uninitialised automatic variable, the behaviour of that is undefined. The compiler can assume that your code doesn't invoke UB". It's a matter of implementation. Yes, a compiler in theory COULD assume that the programmer isn't invoking an undefined behavior. But the majority of compilers (as "zr." has observed in his experiment) tend to assume that the programmer knows what is doing and let him take advantage of system-specific features. In our testcase all the compilers "zr." has tested seem to assume that the programmer --(continue) – Giuseppe Guerrini Jun 05 '13 at 07:40
"wants" to pass the address of a uninitialized memory word. It's weird, ugly, foolish, but it's what the programmer wants. C language has evolved much, but it's still based on the manipulation of memory cells and their addresses... – Giuseppe Guerrini Jun 05 '13 at 07:40

Is this redundant load/store optimization allowed in C99?

4 Answers4