Wei Mi via llvm-dev
2017-Jul-16 00:11 UTC
[llvm-dev] 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.
Sanjoy Das via llvm-dev
2017-Jul-16 01:46 UTC
[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://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
Nuno Lopes via llvm-dev
2017-Jul-17 08:24 UTC
[llvm-dev] A bug related with undef value when bootstrap MemorySSA.cpp
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