Wrong code at -Os on x86_64 (recent regression since 6ed152a)

[shao-hua-li]

Clang at -Os produced the wrong code.

Bisected to 6ed152a, which was committed by @caojoshua

Compiler explorer: https://godbolt.org/z/aMEWqd9dP

% cat a.c
int printf(const char *, ...);
int a, b, c;
long d;
const unsigned *e;
const unsigned **f[3];
static char(g)(unsigned h, int j) { return h > j ? h : h << j; }
static short k() {
  char l = 1;
  b = 0;
  for (; b <= 3; b++) {
    char *m = &l;
    int *n = &c;
    int i = 0;
    for (; i < 3; i++)
      f[i] = &e;
    *n = g((*m)--, 7);
    if (*n)
      ;
    else {
      for (; i < 9; i++)
        f[0] || (d = 2);
      if (0 < *n)
        ;
      else
        return 0;
    }
    printf("%d\n", *n);
  }
  return 1;
}
int main() {
  k();
}
%
% clang -O0 a.c && ./a.out
-128
0
% clang -Os a.c && ./a.out
-128
0
-128
0
%

[dzaima]

Simplified, and failing on all optimization levels other than -O0:

int printf(const char *, ...);
int main() {
  unsigned char l = 1;
  for (unsigned char b = 0; b <= 3; b++) {
    unsigned char c = l << 7;
    l--;
    if (c == 0) {
        return 0;
    }
    printf("%d\n", c);
  }
}

https://godbolt.org/z/eeWMWajnb (also works with any integer type & accordingly adjusted shift such that it shifts LSB to MSB)

[nikic]

Reduced (https://llvm.godbolt.org/z/773zqx7Yb):

; RUN: opt -S -passes=indvars < %s
define void @test() {
entry:
  br label %loop

loop:
  %iv = phi i8 [ 1, %entry ], [ %iv.dec, %loop ]
  %iv.dec = add i8 %iv, -1
  %shl = shl i8 %iv, 7
  %cmp = icmp eq i8 %shl, 0
  br i1 %cmp, label %exit, label %loop

exit:
  ret void
}

The comparison gets folded to false.

[nikic]

Here's the relevant bit of the SCEV dump (https://llvm.godbolt.org/z/7PbrGEvE3):

  %shl = shl i8 %iv, 7
  -->  {-128,+,-128}<nsw><%loop> U: [-128,-127) S: [-128,-127)		

The range here is incorrect and should be [-128,1). This in turn is caused by the incorrect <nsw>.

[nikic]

SCEV assumes that {start,+,step}<nsw> *<nsw> scale is {start*scale,+,step*scale}<nsw>, but this isn't correct in this case. {1,+,-1}<nsw> *<nsw> -128 is the sequence {1,0} * -128 = {-128, 0} where each individual multiplication is indeed nsw, but the resulting addrec {-128,+,-128} does wrap.

This is basically what is happening here: https://alive2.llvm.org/ce/z/mergCt It's correct for nuw but not for nsw.

For this to be correct in the nsw case, we need that start*scale and step*scale both don't overflow: https://alive2.llvm.org/ce/z/fXCqUh