InstCombine cannot blindly assume that inttoptr(ptrtoint x) -> x

[nunoplopes]

Bugzilla Link	34548
Version	trunk
OS	All
Blocks	#34577 #39193
CC	@comex,@majnemer,@vns-mn,@dwblaikie,@efriedma-quic,@fhahn,@hfinkel,@jensmaurer,@dobbelaj-snps,@aqjune,@RKSimon,@Meinersbur,@sunfishcode,@MattPD,@uecker,@RalfJung,@regehr,@rnk,@sanjoy,@rotateright,@yuanfang-chen

Extended Description

Example of an end-to-end miscompilation by clang of the following code involving ptrtoint:

$ cat c.c
#include <stdio.h>

void f(int*, int*);

int main()
{
int a=0, y[1], x = 0;
uintptr_t pi = (uintptr_t) &x;
uintptr_t yi = (uintptr_t) (y+1);
uintptr_t n = pi != yi;

if (n) {
a = 100;
pi = yi;
}

if (n) {
a = 100;
pi = (uintptr_t) y;
}

*(int *)pi = 15;

printf("a=%d x=%d\n", a, x);

f(&x,y);

return 0;
}

$ cat b.c
void f(intx, inty) {}

$ clang -O2 c.c b.c -o foo

$ ./foo
a=0 x=0

This result is wrong. The two possible outcomes are: a=0 x=15, and a=100 x=0.

The bug is in Instcombine that treats inttoptr(ptrtoint(x)) == x, which is incorrect. This transformation can only be done if x is dereferenceable for the accesses through inttoptr.
Compare the following:
clang -O0 -S -emit-llvm -o - c.c | opt -S -sroa
clang -O0 -S -emit-llvm -o - c.c | opt -S -sroa -instcombine

Integer compares are replaces with pointer compares (wrong) and load/stores are changed from inttoptr to pointers directly (also wrong).

Test case by Gil Hur.

[rnk]

Personally I get "a=100 x=0" for this test case.

Does the soundness issue go away if we stop optimizing 'n' to 1? That seems like a much better fix, IMO. Integer/pointer casts are far more important to optimize through than

[regehr]

Reid, try this change:

int a = 0, y[1], x = 0;
//int a=0, x = 0, y[1];

[llvmbot]

Reid, try this change:

int a = 0, y[1], x = 0;
//int a=0, x = 0, y[1];

Doesn't seem to repro here as well (x86-64_linux) [same happens with John's suggested change].

[davide@cupiditate bin]$ ./clang c.c b.c -O1 -o foo && ./foo
a=100 x=0
[davide@cupiditate bin]$ ./clang c.c b.c -O2 -o foo && ./foo
a=100 x=0
[davide@cupiditate bin]$ ./clang c.c b.c -O3 -o foo && ./foo
a=100 x=0

[llvmbot]

Also

[davide@cupiditate bin]$ ./clang c.c -O0 -S -emit-llvm -o - | ./opt -S -sroa > pre.ll
[davide@cupiditate bin]$ ./clang c.c -O0 -S -emit-llvm -o - | ./opt -S -sroa -instcombine > post.ll
[davide@cupiditate bin]$ diff -u pre.ll post.ll
[davide@cupiditate bin]$

Presumably this might have been fixed/hidden? Which revision are you at?
I'm at clang version 6.0.0 (trunk 312918) (llvm/trunk 312925)

Side note, I had to add <stdint.h> to the code to get it compile.

[regehr]

Weird, I see "a=0 x=0" at -O2 using both 4.0 and 5.0 on OS X and Ubuntu 16.04 on x86-64.

[llvmbot]

Weird, I see "a=0 x=0" at -O2 using both 4.0 and 5.0 on OS X and Ubuntu
16.04 on x86-64.

Can you verify this still happen on ToT ? In the meanwhile, I'm going to try with 5.0 on my machine (see if that applies, and bisect in case).

[david-xl]

I could not reproduce the problem either (same IR)

[regehr]

Johns-MacBook-Pro-2:code regehr$ clang -v
clang version 6.0.0 (trunk 312932)
Target: x86_64-apple-darwin16.7.0
Thread model: posix
InstalledDir: /Users/regehr/llvm-install/bin

Johns-MacBook-Pro-2:code regehr$ clang -O2 alias4.c alias4-b.c
Johns-MacBook-Pro-2:code regehr$ ./a.out
a=0 x=0

Johns-MacBook-Pro-2:code regehr$ cat alias4.c
#include <stdint.h>
#include <stdio.h>

void f(int *, int *);

int main() {
int a = 0, y[1], x = 0;
//int a=0, x = 0, y[1];
uintptr_t pi = (uintptr_t)&x;
uintptr_t yi = (uintptr_t)(y + 1);
uintptr_t n = pi != yi;

if (n) {
a = 100;
pi = yi;
}

if (n) {
a = 100;
pi = (uintptr_t)y;
}

*(int *)pi = 15;

printf("a=%d x=%d\n", a, x);

f(&x, y);

return 0;
}

Johns-MacBook-Pro-2:code regehr$ cat alias4-b.c
void f(int *x, int *y) {}

[efriedma-quic]

Does the soundness issue go away if we stop optimizing 'n' to 1?

I don't think we do that? At least, I can't reproduce that with trunk clang... and it's pretty clearly not a legal transform. See https://reviews.llvm.org/rL249490 .

[nunoplopes]

Ok, so I guess some of you cannot reproduce this because your clang has a default option to enable some sanitization.
Try with clang -cc1 (adjust paths as needed):

$ ./bin/clang -cc1 -triple x86_64-pc-linux-gnu -emit-obj -O2 -o c.o c.c -internal-externc-isystem /usr/include/ -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-isystem /home/nuno/llvm-build/lib/clang/6.0.0/include

$ ./bin/clang -o foo b.c c.o

$ ./foo

[rnk]

I was able to repro with John's reordering of the variables, but that doesn't seem that important.

Why can't we assume inttoptr(ptrtoint(x)) is a no-op? What's wrong with that in principle? "a=0 x=0" seems like a real bug, but I'm not convinced this is the cause.

[llvmbot]

Can someone attach a ll file and the opt commandline to reproduce the problem consistently?

[efriedma-quic]

The problem really stems the following rule from http://llvm.org/docs/LangRef.html#pointer-aliasing-rules:

• A pointer value formed by an inttoptr is based on all pointer values that contribute (directly or indirectly) to the computation of the pointer’s value.

I think Nuno wrote up a good description somewhere, but essentially the problem is that we end up erasing dependencies, so alias analysis returns the wrong result.

[llvmbot]

The problem really stems the following rule from
http://llvm.org/docs/LangRef.html#pointer-aliasing-rules:

• A pointer value formed by an inttoptr is based on all pointer values that
  contribute (directly or indirectly) to the computation of the pointer’s
  value.

I think Nuno wrote up a good description somewhere, but essentially the
problem is that we end up erasing dependencies, so alias analysis returns
the wrong result.

Is this the problem:

inttoptr(ptrtoint(x)) + int_value

where the int_value is actually a pointer but x is not.

If the llvm folds the first, this becomes a getelementptr with x as the base, then the result value won't aliased with what int_value points to anymore?

[hfinkel]

The problem really stems the following rule from
http://llvm.org/docs/LangRef.html#pointer-aliasing-rules:

• A pointer value formed by an inttoptr is based on all pointer values that
  contribute (directly or indirectly) to the computation of the pointer’s
  value.

I think Nuno wrote up a good description somewhere, but essentially the
problem is that we end up erasing dependencies, so alias analysis returns
the wrong result.

I think that this is essentially correct. The problem here is that inttoptr(ptrtoint(x)) only appears be based on x. However, in this case, the inttoptr is also control dependent on a comparison between some other pointer values. The resulting pointer, therefore, is based on all of these pointers. AA won't see this, just based on inttoptr(ptrtoint(x)) == x, because it will only see x.