[llvm-bugs] [Bug 46943] New: Loop Strength Reduction (`opt -loop-reduce`) reorders `icmp` with -1 and `add nuw`, yielding poison

[via llvm-bugs]

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

            Bug ID: 46943
           Summary: Loop Strength Reduction (`opt -loop-reduce`) reorders
                    `icmp` with -1 and `add nuw`, yielding poison
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: Loop Optimizer
          Assignee: unassignedbugs at nondot.org
          Reporter: pnkfelix at pnkfx.org
                CC: llvm-bugs at lists.llvm.org

Created attachment 23802
  --> https://bugs.llvm.org/attachment.cgi?id=23802&action=edit
input LLVM IR to demonstrate bug

This is taken from
https://github.com/rust-lang/rust/issues/74498#issuecomment-661950983

Take this LLVM IR (attached as rust-issue-74498-comex.ll):


```
target datalayout =
"e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

declare void @dummy(i8 zeroext)

define i8 @test() {
  br label %1

1:
  %2 = phi i8 [ 0, %0 ], [ %4, %1 ]
  call void @dummy(i8 %2)

  %3 = icmp eq i8 %2, -1
  %4 = add nuw i8 %2, 1
  br i1 %3, label %5, label %1

5:
  ret i8 %4
}
```

In this IR, %2 is being incremented until it reaches -1, at which point we
break. We use `add nuw` for the increments, which yields poison in %4, but the
poison should not matter because we will break out of the loop before using the
poison.


Now, feed that into `opt -loop-reduce`, you get the following result:

```
% ./bin/opt -loop-reduce -S rust-issue-74498-comex.ll -o
rust-issue-74498-comex2.ll
% cat rust-issue-74498-comex2.ll 
; ModuleID = 'rust-issue-74498-comex.ll'
source_filename = "rust-issue-74498-comex.ll"
target datalayout =
"e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

declare void @dummy(i8 zeroext)

define i8 @test() {
  br label %1

1:                                                ; preds = %1, %0
  %2 = phi i8 [ 0, %0 ], [ %3, %1 ]
  call void @dummy(i8 %2)
  %3 = add nuw i8 %2, 1
  %4 = icmp eq i8 %3, 0
  br i1 %4, label %5, label %1

5:                                                ; preds = %1
  ret i8 %3
}
% 
```

The problem, as also pointed out on the Rust issue, is that the `add nuw` is
moved up above the `icmp`, which means that now we will get the poison result
and feed *that* into the icmp.

In our original program that drove this investigation, that then led to the
loop being further incorrectly optimized into an infinite loop. But I think
that in general this incorrect optimization could yield arbitrary undefined
behavior, if I understand correctly.

-- 
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/20200801/1b08a29a/attachment.html>