3 ms·

From the linked John Regehr blog post (http://blog.regehr.org/archives/767 http://blog.regehr.org/archives/767): Nick Lewycky submitted this code: #incl

From the linked John Regehr blog post (http://blog.regehr.org/archives/767 http://blog.regehr.org/archives/767): Nick Lewycky submitted this code: #include <stdio.h> #include <stdlib.h> int main() { int *p = (int*)malloc(sizeof(int)); int *q = (int*)realloc(p, sizeof(int)); *p = 1; *q = 2; if (p == q) printf("%d %d\n", *p, *q); } This got my attention for a lot longer than the OP, because it maintains the surprising behavior (prints different values for * p and * q even if p == q) if you move the assignments inside the if-statement: http://codepad.org/PBUAgnQq http://codepad.org/PBUAgnQq I'm told that a pointer passed to realloc has to be assumed to be invalidated, even if it's exactly equal to another pointer that you know is valid, but it's hard to wrap my head around that and I certainly didn't get that out of looking at the C89 standard.

eridius 12y ago
Under what circumstances does it print different values? I just tried your code locally with clang on OS X, and I get `2 2` at all optimization levels. If the compiler is indeed allowed to assume that the pointer passed to realloc() becomes invalid, then I would expect it to actually optimize out that entire if-check, under the assumption that the `*p` is undefined behavior, and therefore that `p == q` must never be true. Getting different values for the print if you move the assignments inside the if statement suggests to me that a) it's assuming the pointers don't alias, and therefore b) that it assumes it doesn't have to read the values back out of the pointer when printing them but can just reuse the values it knows it wrote to the pointer. But if it assumes the pointers don't alias, then I would think it would assume that means `p == q` can't be true.
- eridius 12y ago
  FWIW, inspecting the LLVM IR of `clang -O3`, I get the equivalent of the following: #include <stdio.h> #include <stdlib.h> int main() { int *p = (int*)malloc(sizeof(int)); int *q = (int*)reallocf(p, sizeof(int)); if (p == q) { *q = 2; printf("%d %d\n", 2, 2); } return 0; } Note how it removed the write to p and removed the read of the pointer value. Here what it's done is assumed that because p == q, that means they alias, and therefore the write to p will be overwritten by the write to q, and that it doesn't have to read the value again to know what will be printed. So the optimization here seems to be proceeding under the assumption that realloc() does not necessarily invalidate the pointer. And it behaves the same way with reallocf() as well.
- ben0x539 12y ago
  clang -O3 on linux amd64. I'm told that aliasing is unrelated to equality, and I guess the trick is that realloc's returned pointer is attributed noalias. I get assembly that does the check, does the stores, but omits the loads: cmp rbx, rax jne .LBB0_2 mov dword ptr [rax], 2 mov dword ptr [rbx], 1 mov edi, .L.str mov esi, 1 mov edx, 2 xor eax, eax call printf .LBB0_2:
  - eridius 12y ago
    Omitting the loads doesn't mean it thinks the pointer is invalid, it just means it thinks the pointer doesn't alias. If it doesn't alias, and it's not volatile, then it can assume that what it just stored is what it would get by loading, so it can skip the load. I guess the only difference between what you described and what I'm seeing is my clang recognizes that since p == q, then a store to one will overwrite the store to the other, and therefore it can skip storing the 1 and it can assuming reading both will return 2.
- spc476 12y ago
  It's undefined behavior, so the compiler is free to do pretty much anything it wants. It can always assume it's true; it can always assume it's false; it can omit code to return true 50% of the time.
  - eridius 12y ago
    In theory it can do whatever it wants. In practice, it generally just assumes undefined behavior won't happen, and will therefore assume that any conditions that could lead to undefined behavior are false (and prune any dead code that results from those assumptions). The other thing that can happen is LLVM has the concept of a undefined value, which is distinct from undefined behavior. Undefined values may be unknown, but the compiler can assume that any possible value still results in defined behavior, and optimize accordingly. As an example, an un-initialized stack variable has an undefined value, but various operations on it may still result in defined behavior regardless of the value. You can read more about undefined values in LLVM at http://llvm.org/docs/LangRef.html#undefined-values http://llvm.org/docs/LangRef.html#undefined-values if you're interested.

eridius 12y ago

Under what circumstances does it print different values? I just tried your code locally with clang on OS X, and I get `2 2` at all optimization levels. If the compiler is indeed allowed to assume that the pointer passed to realloc() becomes invalid, then I would expect it to actually optimize out that entire if-check, under the assumption that the `*p` is undefined behavior, and therefore that `p == q` must never be true. Getting different values for the print if you move the assignments inside the if statement suggests to me that a) it's assuming the pointers don't alias, and therefore b) that it assumes it doesn't have to read the values back out of the pointer when printing them but can just reuse the values it knows it wrote to the pointer. But if it assumes the pointers don't alias, then I would think it would assume that means `p == q` can't be true.

eridius 12y ago
FWIW, inspecting the LLVM IR of `clang -O3`, I get the equivalent of the following: #include <stdio.h> #include <stdlib.h> int main() { int *p = (int*)malloc(sizeof(int)); int *q = (int*)reallocf(p, sizeof(int)); if (p == q) { *q = 2; printf("%d %d\n", 2, 2); } return 0; } Note how it removed the write to p and removed the read of the pointer value. Here what it's done is assumed that because p == q, that means they alias, and therefore the write to p will be overwritten by the write to q, and that it doesn't have to read the value again to know what will be printed. So the optimization here seems to be proceeding under the assumption that realloc() does not necessarily invalidate the pointer. And it behaves the same way with reallocf() as well.
ben0x539 12y ago
clang -O3 on linux amd64. I'm told that aliasing is unrelated to equality, and I guess the trick is that realloc's returned pointer is attributed noalias. I get assembly that does the check, does the stores, but omits the loads: cmp rbx, rax jne .LBB0_2 mov dword ptr [rax], 2 mov dword ptr [rbx], 1 mov edi, .L.str mov esi, 1 mov edx, 2 xor eax, eax call printf .LBB0_2:
- eridius 12y ago
  Omitting the loads doesn't mean it thinks the pointer is invalid, it just means it thinks the pointer doesn't alias. If it doesn't alias, and it's not volatile, then it can assume that what it just stored is what it would get by loading, so it can skip the load. I guess the only difference between what you described and what I'm seeing is my clang recognizes that since p == q, then a store to one will overwrite the store to the other, and therefore it can skip storing the 1 and it can assuming reading both will return 2.
spc476 12y ago
It's undefined behavior, so the compiler is free to do pretty much anything it wants. It can always assume it's true; it can always assume it's false; it can omit code to return true 50% of the time.
- eridius 12y ago
  In theory it can do whatever it wants. In practice, it generally just assumes undefined behavior won't happen, and will therefore assume that any conditions that could lead to undefined behavior are false (and prune any dead code that results from those assumptions). The other thing that can happen is LLVM has the concept of a undefined value, which is distinct from undefined behavior. Undefined values may be unknown, but the compiler can assume that any possible value still results in defined behavior, and optimize accordingly. As an example, an un-initialized stack variable has an undefined value, but various operations on it may still result in defined behavior regardless of the value. You can read more about undefined values in LLVM at http://llvm.org/docs/LangRef.html#undefined-values http://llvm.org/docs/LangRef.html#undefined-values if you're interested.