[llvm-bugs] [Bug 30429] New: Should recognize redundant comparisons with constant offsets

[via llvm-bugs]

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

            Bug ID: 30429
           Summary: Should recognize redundant comparisons with constant
                    offsets
           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

Consider the following pair of C functions that are both equivalent to "return
0":


int one(int i, int len) {
   return i < len && i + 1 > len;
}

int two(int i, int len) {
   return i + 1 < len && i + 2 > len;
}


They map to the following LLVM functions (simplified a bit):


define i32 @one(i32 %i, i32 %len) {
  %1 = icmp slt i32 %i, %len
  %2 = add nsw i32 %i, 1
  %3 = icmp sgt i32 %2, %len
  %4 = and i1 %1, %3
  %5 = zext i1 %4 to i32
  ret i32 %5
}

define i32 @two(i32 %i, i32 %len) {
  %1 = add nsw i32 %i, 1
  %2 = icmp slt i32 %1, %len
  %3 = add nsw i32 %i, 2
  %4 = icmp sgt i32 %3, %len
  %5 = and i1 %2, %4
  %6 = zext i1 %5 to i32
  ret i32 %6
}


Now, opt -instcombine optimizes @one to "ret i32 0" but leaves @two untouched.
This is because InstCombineCompares.cpp has logic for "icmp sgt (X + 1), Y ->
icmp sge X, Y" which starts the chain of optimizations required in @one. I
considered extending this to "icmp sgt (X + C), Y -> icmp sge (X + (C - 1)), Y"
(and analogously for the other similar icmp optimizations) but this isn't
always a profitable transformation and seems oddly specific anyway. It's only
worth it here because we happen to have "icmp slt (X + (C - 1)), Y" nearby and
can combine the two.

Overall this kind of thing seems like something LLVM should be able to
optimize, but I'm not sure how it should go about doing it. I would imagine
cases like these to show up in e.g. array bounds checks on occasion.

This was with LLVM trunk r281814 and release version 3.9.0.

For what it's worth, GCC 6.2.1 can optimize both C functions to return 0, but
even it is stumped by the following:

int two_trickier(int i, int len) {
   return i + 1 < len && i + 1 > len - 1;
}

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