llvm dev - Jul 2017 - A bug related with undef value when bootstrap MemorySSA.cpp

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.

Hi Wei,

[+CC the other undef folks]

This is the same bug as https://bugs.llvm.org/show_bug.cgi?id=31652.
The short answer here is that the loop unswitch transform and the GVN
transform are justified via conflicting specifications of undef (that
is, LoopUnswitch and GVN don't agree on the definition of undef).  The
long(er) answer is in the bug.

Unfortunately, there is no real way to fix this in the IR today
(beyond hacking GVN / LoopUnswitch to back off on these transforms
enough to not trigger this case).  We will need to specify and
implement a consistent definition of undef / poison to truly fix this,
one of which we've already proposed.

Thanks!
-- Sanjoy

Cool, thanks for debugging this issue and letting us know.

We have a few patches to fix this issue:
 - Introduce freeze in IR: https://reviews.llvm.org/D29011
 - Lowering freeze: https://reviews.llvm.org/D29014
 - Fix loop unswitch: https://reviews.llvm.org/D29015

Bonus patches to recover perf:
 - Be less conservative in loop unswitching: https://reviews.llvm.org/D29016
 - Instcombine support for freeze: https://reviews.llvm.org/D29013

It would be great if you could try out these patches to see if the bug goes
away.

Thanks,
Nuno


-----Original Message-----
From: Sanjoy Das
Sent: 16 de julho de 2017 02:47
To: Wei Mi 
Cc: llvm-dev; Xinliang David Li; Sanjoy Das; Nuno Lopes; John Regehr; Juneyoung
Lee
Subject: Re: [llvm-dev] A bug related with undef value when bootstrap
MemorySSA.cpp

Hi Wei,

[+CC the other undef folks]

This is the same bug as
https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fbugs.llvm.org%2Fshow_bug.cgi%3Fid%3D31652&data=02%7C01%7Cnlopes%40microsoft.com%7C971ae2063c8b420d2f1008d4cbec8f22%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C636357664258073352&sdata=iCy8kUlWwJzQpXbXvOuhHpKyXBnntZPGvn%2FtxWsqun8%3D&reserved=0.
The short answer here is that the loop unswitch transform and the GVN transform
are justified via conflicting specifications of undef (that is, LoopUnswitch and
GVN don't agree on the definition of undef).  The
long(er) answer is in the bug.

Unfortunately, there is no real way to fix this in the IR today (beyond hacking
GVN / LoopUnswitch to back off on these transforms enough to not trigger this
case).  We will need to specify and implement a consistent definition of undef /
poison to truly fix this, one of which we've already proposed.

Thanks!
-- Sanjoy