[llvm-bugs] [Bug 30428] New: Infer nsw/nuw flags for increment/decrement if relational comparison succeeded

[via llvm-bugs]

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

            Bug ID: 30428
           Summary: Infer nsw/nuw flags for increment/decrement if
                    relational comparison succeeded
           Product: new-bugs
           Version: trunk
          Hardware: All
                OS: All
            Status: NEW
          Keywords: code-quality
          Severity: enhancement
          Priority: P
         Component: new bugs
          Assignee: unassignedbugs at nondot.org
          Reporter: matti.niemenmaa+llvmbugs at iki.fi
                CC: llvm-bugs at lists.llvm.org
    Classification: Unclassified

Created attachment 17300
  --> https://llvm.org/bugs/attachment.cgi?id=17300&action=edit
LLVM emitted for simple Rust example

Consider the following example:


define i1 @func(i64 %a, i64 %b, i64 %c) {
  %sgt = icmp sgt i64 %a, %b
  br i1 %sgt, label %greater, label %lesser

greater:
  %add = add i64 %b, 1
  %sgt.add = icmp sgt i64 %add, %c
  ret i1 %sgt.add

lesser:
  ret i1 true
}


At the point where %add is executed we know that %sgt was true, i.e. %a > %b.
We then know that incrementing %b cannot wrap: there is "room" in the value
range for at least %a before we would wrap. More generally:

1. If (X s< Y), then both X + 1 and Y - 1 are nsw.
2. If (X u< Y), then both X + 1 and Y - 1 are nuw. [1]

Currently (LLVM trunk r281814, or release version 3.9.0) this kind of analysis
is not performed. I'm not sure where it would belong, either. It doesn't feel
important enough to me to have its own pass.

This arose from looking at why a bounds check in Rust is not eliminated [2]: it
would require this kind of analysis in addition to my patch from
https://reviews.llvm.org/D24700 to simplify unsigned comparisons. Attached is a
complete example of LLVM emitted by the Rust compiler including a bounds check
that could be eliminated. Adding a nuw flag to the increment and using a
version of opt that includes D24700, the whole function can be optimized down
to a 'ret void'.

[1]: Due to the current canonicalization from 'sub nuw Y, 1' to 'add Y, -1' the
latter flag would not be so helpful. But as I mention in D24700, this
canonicalization seems misguided to me: keeping the nuw would be useful.
[2]: https://github.com/rust-lang/rust/issues/35981

-- 
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/20160917/e4d3ff90/attachment.html>