LoopStrengthReduce incorrectly rewrites UREM (wrong code at -O3 on x86_64-linux-gnu in 64-bit mode (not in 32-bit mode))

[zhendongsu]

Bugzilla Link	39499
Version	unspecified
OS	All
CC	@hfinkel,@zygoloid,@rotateright

Extended Description

Tested with trunk revision 345488.

$ clangpolly -v
clang version 8.0.0 (http://llvm.org/git/clang.git 8029b38886dd239769e3501dac21438e16886ce8) (llvm/trunk 345488)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /home/su/bin
Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/4.9
Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/4.9.4
Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/5
Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/5.3.0
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.4
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.4.7
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.6
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.6.4
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.7
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.7.3
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.8
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.8.5
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.9
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.9.4
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/5
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/5.3.0
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/6
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/6.2.0
Selected GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.9
Candidate multilib: .;@m64
Candidate multilib: 32;@m32
Candidate multilib: x32;@MX32
Selected multilib: .;@m64
$
$ clangpolly -m64 -O2 small.c
$ ./a.out
$
$ clangpolly -m32 -O3 small.c
$ ./a.out
$
$ clangpolly -m64 -O3 small.c
$ ./a.out
Floating point exception (core dumped)
$

---

int printf (const char *, ...);

long a, b, i;
int c, f, g = 1, j, k, l, m = 6, n = 3;
short d = 4;
char e, h;

int main () 
{
  while (1)
    {
    L:
      for (; j < 10; j++)
	{
	  for (h = 2; h >= 0; h--)
	    while (1)
	      {
		if (l)
		  f = 2;
		int q = 9L / g / ~e | (n ^ c) | f, t = 9 & -(~e / q & g);
		char aa = ~(~i * -c & ~f) / n ^ t ^ 9;
		long ab;
		if (d)
		  break;
		if (e)
		  ab = i = ~(e & 9L * (g * aa) & ~c & f) & n;
		e = ~(n / -i * e & ab) | -(-aa | g);
		i = ~i / ~e / q ^ ~t;
		if (g)
		  {
		    printf ("%d\n", e);
		    goto L;
		  }
		while (h > b)
		  ;
		g = c = e;
		break;
	      }
	  for (n = 0; n < 10; n++)
	    if (a && h < c)
	      break;
	  if (k)
	    {
	      printf ("%d\n", k);
	      continue;
	    }
	  f = h % (unsigned) 9;
	}

      if (f > 3)
	m = 0;
      int s = 46744073709551608 % m;
      if (s)
	break;
    }
  return 0;
}

[rotateright]

Marking as confirmed - this still shows the same failure at r346802.

[fhahn]

The latest version this reproduces with the C code is 12.0 with the following extra flags -O3 -fno-unroll-loops -flegacy-pass-manager : https://godbolt.org/z/YbW6x4MMd

[fhahn]

It looks like the issue here is in LoopStrengthReduce: https://godbolt.org/z/M6T1Y59hP

I think I managed to isolate the incorrect transform to the following: https://godbolt.org/z/PxGzTWrqr

 target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx"

declare void @use(i64)

define i32 @test() {
entry:
  br label %loop

loop:
  %iv = phi i8 [ 1, %entry ], [ %iv.next, %loop ]
  %iv.next = add nsw i8 %iv, -1
  %ext = zext i8 %iv to i64
  call void @use(i64 %ext)
  %cmp2 = icmp sgt i8 %iv.next, -1
  br i1 %cmp2, label %loop, label %exit

exit:
  %sext = sext i8 %iv.next to i32
  %rem = urem i32 %sext, 9
  ret i32 %rem
}

opt -loop-reduce:

define i32 @test() {
entry:
  br label %loop

loop:                                             ; preds = %loop, %entry
  %lsr.iv = phi i64 [ %lsr.iv.next, %loop ], [ 1, %entry ]
  call void @use(i64 %lsr.iv)
  %lsr.iv.next = add nsw i64 %lsr.iv, -1
  %tmp1 = trunc i64 %lsr.iv.next to i8
  %cmp2 = icmp sgt i8 %tmp1, -1
  br i1 %cmp2, label %loop, label %exit

exit:                                             ; preds = %loop
  %0 = udiv i64 %lsr.iv.next, 9
  %1 = mul i64 %0, 4294967287
  %2 = add i64 %1, %lsr.iv.next
  %tmp = trunc i64 %2 to i32
  ret i32 %tmp
}

This can lead to an incorrect return value: https://alive2.llvm.org/ce/z/7Ztnov

[fhahn]

Proposed fix https://reviews.llvm.org/D151394