[llvm-dev] A bug related with undef value when bootstrap MemorySSA.cpp

[Wei Mi via llvm-dev]

This is a bug found by internal compiler bootstrap, and possibly it is
the root cause of https://bugs.llvm.org/show_bug.cgi?id=33652 and
https://bugs.llvm.org/show_bug.cgi?id=33626.

Here is the testcase 1.c. The original code is at MemorySSA.cpp:586
for rL307764.

------------------------- 1.c ---------------------------
long a, c, d, e, f, m, cnt, i_hasval;
volatile long b;
void goo(long);
void hoo();
long ioo();

void foo(long hasval) {
  long i, k;
  if (hasval) {
    i = b;
  }

  k = 0;
  do {
    if (i_hasval != hasval)
      return;
    if (i_hasval) {
      m = m + 1;
      if (a == i) {
        c = a + d + e + f;
        return;
      }
    }
    c = a + b;
    i_hasval = 3;
    k++;
  } while (k < cnt);
}

void hoo() {
  foo(0);
}
------------------------------------------------------

I verified the problem existed from
llvm-r295736 to the head of trunk using 1.c (I didn't try older version)

~/workarea/llvm-r295736/dbuild/bin/clang -O3 -S 1.c -mllvm
-jump-threading-threshold=0 -fno-vectorize

Here is hoo's assembly code, note that there is no store to c(%rip)
inside of it, and it is wrong.

hoo:                                    # @hoo
        .cfi_startproc
# BB#0:                                 # %entry
        movq    cnt(%rip), %rax
        cmpq    $0, i_hasval(%rip)
        sete    %dl
        xorl    %ecx, %ecx
        .p2align        4, 0x90
.LBB1_1:                                # %do.body.us.i
                                        # =>This Inner Loop Header: Depth=1
        testb   $1, %dl
        je      .LBB1_3
# BB#2:                                 # %if.end2.us.i
                                        #   in Loop: Header=BB1_1 Depth=1
        movq    b(%rip), %rdx
        movq    $3, i_hasval(%rip)
        incq    %rcx
        xorl    %edx, %edx
        cmpq    %rax, %rcx
        jl      .LBB1_1
.LBB1_3:                                # %foo.exit
        retq

Here are the related llvm transformations (Note: look at the value of
i, i is undef when hasval is 0.):

1. The condition expr of if (a == i) is a loop invariant and is
promoted outside of do-while loop.

t = (a == i);         // loop invariant code motion
do {
    if (i_hasval != hasval)
      return;
    if (i_hasval) {
      m = m + 1;
      if (t) {
        c = a + d + e + f;
        return;
      }
    }
    c = a + b;
    i_hasval = 3;
    k++;
  } while (k < cnt);

2. Then the do-while loop is unswitched by if (a == i):

if (a == i) {
  do {
      if (i_hasval != hasval)
        return;
      if (i_hasval) {
        m = m + 1;
        if (true) {
          c = a + d + e + f;
          return;
        }
      }
      c = a + b;
      i_hasval = 3;
      k++;
   } while (k < cnt);
} else {
  do {
      if (i_hasval != hasval)
        return;
      if (i_hasval) {
        m = m + 1;
        if (false) {
          c = a + d + e + f;
          return;
        }
      }
      c = a + b;
      i_hasval = 3;
      k++;
    } while (k < cnt);
}

3. GVN does equality propagation to replace a with i inside of the first loop.

if (a == i) {
  do {
      if (i_hasval != hasval)
        return;
      if (i_hasval) {
        m = m + 1;
        if (true) {
          c = i + d + e + f;      // a is replaced with i.
          return;
        }
      }
      c = i + b;                     // a is replaced with i.
      i_hasval = 3;
      k++;
   } while (k < cnt);
} else {
  do {
      if (i_hasval != hasval)
        return;
      if (i_hasval) {
        m = m + 1;
        if (false) {
          c = a + d + e + f;
          return;
        }
      }
      c = a + b;
      i_hasval = 3;
      k++;
    } while (k < cnt);
}

4. after the callsite foo(0) is inlined into hoo, i becomes undef and
inliner propagates the undef of i to all the uses of i.

if (a == undef) {             // i is replaced with undef
  do {
      if (i_hasval != hasval)
        return;
      if (i_hasval) {
        m = m + 1;
        if (true) {
          c = undef + d + e + f;      // i is replaced with undef.
          return;
        }
      }
      c = undef + b;                     // i is replaced with undef.
      i_hasval = 3;
      k++;
   } while (k < cnt);
} else {
  do {
      if (i_hasval != hasval)
        return;
      if (i_hasval) {
        m = m + 1;
        if (false) {
          c = a + d + e + f;
          return;
        }
      }
      c = a + b;
      i_hasval = 3;
      k++;
    } while (k < cnt);
}

5. a == undef is simplified into true and the else branch is removed.

  do {
      if (i_hasval != hasval)
        return;
      if (i_hasval) {
        m = m + 1;
        if (true) {
          c = undef + d + e + f;      // store to c
          return;
        }
      }
      c = undef + b;                     // store to c
      i_hasval = 3;
      k++;
   } while (k < cnt);

We can see that c is always an undef value now after all these
transformations. That is why we cannot see store to c in the final
assembly. In the original program, c has a valid value at the end of
hoo.

Every transformation above seems of no problem, but the composition
result is wrong. It is still not clear which transformation to blame.

Thanks,
Wei.