[llvm-bugs] [Bug 31652] New: Loop unswtich and GVN interact badly and miscompile

[via llvm-bugs]

https://llvm.org/bugs/show_bug.cgi?id=31652

            Bug ID: 31652
           Summary: Loop unswtich and GVN interact badly and miscompile
           Product: libraries
           Version: trunk
          Hardware: All
                OS: All
            Status: NEW
          Keywords: miscompilation
          Severity: normal
          Priority: P
         Component: Scalar Optimizations
          Assignee: unassignedbugs at nondot.org
          Reporter: nunoplopes at sapo.pt
                CC: david.majnemer at gmail.com, davide at freebsd.org,
                    dberlin at dberlin.org, gil.hur at sf.snu.ac.kr,
                    juneyoung.lee at sf.snu.ac.kr, llvm-bugs at lists.llvm.org,
                    regehr at cs.utah.edu, sanjoy at playingwithpointers.com
    Classification: Unclassified

Created attachment 17845
  --> https://llvm.org/bugs/attachment.cgi?id=17845&action=edit
Reduced IR test case

Loop unswitch and GVN when taken together can miscompile code due to
disagreeing semantics of branch on undef.
In our opinion it's loop unswitch that is incorrect.

Test case in C:
static volatile int always_false = 0;

void maybe_init(int *p) {}

int f(int limit0) {
  int maybe_undef_loc;
  maybe_init(&maybe_undef_loc);

  int limit = limit0;
  int total = 0;
  for (int i = 0; i < limit; i++) {
    total++;
    if (always_false) {
      if (maybe_undef_loc != (limit0 + 10)) {
        total++;
      }
    }
    limit = limit0 + 10;
  }
  return total;
}

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

int main(int argc, char **argv) {
  printf("f(10) = %d\n", f(10));
  return 0;
}


I believe this test case has no UB even at C level. It should print "f(10) =
20".

I've attached a reduced IR test case.


Running LICM, the comparison of maybe_undef_loc gets hoisted:

$ opt -S bug.ll -loop-rotate -licm
...
loop.body.lr.ph:
  %undef_loc = load i32, i32* %maybe_undef_loc, align 4
  %add = add nsw i32 %limit0, 10
  %cmp3 = icmp ne i32 %undef_loc, %add
  %limit2 = add nsw i32 %limit0, 10
  br label %loop.body
...


This is still ok. But then adding loop unswitch:

$ opt -S bug.ll -loop-rotate -licm -loop-unswitch
...
loop.body.lr.ph:
  %undef_loc = load i32, i32* %maybe_undef_loc, align 4
  %add = add nsw i32 %limit0, 10
  %cmp3 = icmp ne i32 %undef_loc, %add
  %limit2 = add nsw i32 %limit0, 10
  br i1 %cmp3, label %loop.body.lr.ph.split.us, label
%loop.body.lr.ph.loop.body.lr.ph.split_crit_edge
...

Loop unswitch introduce a branch on %cmp3, which will be undef once we inline
maybe_init(). Hence loop unswitch assumes branch on undef is a
non-deterministic jump (so not UB).
By running GVN after loop unswitch, we clearly see that GVN has a different
perspective on the semantics of branch on undef. It produces this diff:
-  %limit2 = add nsw i32 %limit0, 10
...
-  %cmp = icmp slt i32 %i2, %limit2
+  %cmp = icmp slt i32 %i2, %undef_loc

I'm not including the context here, but to be able to justify this
transformation, branch on undef has to be UB, not a non-deterministic jump as
assumed by loop unswitch above.

Putting all things together:
$ opt -S bug.ll -loop-rotate -licm -loop-unswitch -gvn | opt -S -O2 | llc -o
x.S && clang x.S -o x && ./x
f(10) = 1

This is wrong. Should be 20, not 1.

This example shows how Loop unswitch and GVN can produce a miscompilation
end-to-end. The bug can be fixed by using the proposed freeze instruction in
loop unswitch.

(Example by Sanjoy)

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20170116/52a56899/attachment.html>