[InstSimplify] Peephole optimization for icmp (urem X, Y), X

[• xldenis]

Summary

This revision adds the following peephole optimization and it's negation:

%a = urem i64 %x, %y
%b = icmp ule i64 %a, %x

====>
%b = true

With John Regehr's help this optimization was checked with Alive2 which suggests it should be valid.

This pattern occurs in the bound checks of Rust code, the program

const N: usize = 3;
const T = u8;

pub fn split_mutiple(slice: &[T]) -> (&[T], &[T]) {
    let len = slice.len() / N;
    slice.split_at(len * N)
}

the method call slice.split_at will check that len * N is within the bounds of slice, this bounds check is after some transformations turned into the urem seen above and then LLVM fails to optimize it any further. Adding this optimization would cause this bounds check to be fully optimized away.

ref: https://github.com/rust-lang/rust/issues/74938

[lebedev.ri]

Thank you for the patch!

llvm/lib/Analysis/InstructionSimplify.cpp

2967

This appears correct, but you also need to handle icmp pred Y, (urem Y, X) case.
I know that naively one would expect it to be canonicalized by complexity sorting,
and i think said complexity sorting is a subtle evil.

llvm/test/Transforms/InstSimplify/compare.ll

726

I think these could be i8, to simplify the life of alive :)

[nikic]

llvm/lib/Analysis/InstructionSimplify.cpp

2967

I've applied some cleanup in https://github.com/llvm/llvm-project/commit/a0addbb4ec8c7bf791139699d46b08413c46eed7 to only explicitly handle the binop on the LHS and treat the other side via swapped predicate.

[• xldenis]

Added the symmetric case for icmp X (urem X Y) and changed the test bitwidths to i8.

[• xldenis]

llvm/lib/Analysis/InstructionSimplify.cpp

2967

ah I just added the mirrored version of the opt, should I remove it then? I'll leave the test cases.

[• xldenis]

Removed mirror transformation since it is unnecessary and fix the additional mirrored tests.

[lebedev.ri]

llvm/lib/Analysis/InstructionSimplify.cpp

2967

You need to rebase the patch, moving a single variant of the fold into simplifyICmpWithBinOpOnLHS()

[bugadani]

I think it's also possible to apply the same logic to both X % Y <= Y and X % Y <= X

[• xldenis]

Rebase patch on latest master.

[• xldenis]

In D85092#2189498, @bugadani wrote:

I think it's also possible to apply the same logic to both X % Y <= Y and X % Y <= X

The first optimization already exists (line 2787, sorry having a hard time in this UI). And I'm adding the second one, unless I misunderstood?

[nikic]

llvm/test/Transforms/InstSimplify/compare.ll

731

These tests aren't testing the right fold. You are checking for (X % Y) <= Y, which is a fold that already exists. What you add here is (X % Y) <= X.

[lebedev.ri]

llvm/lib/Analysis/InstructionSimplify.cpp

2756

Minor nit: icmp pred (urem X, Y), X might be better for readability

2757

LBO && part is not needed, we know it's a non-null ptr already.

[nikic]

LGTM

[lebedev.ri]

@xldenis if you need help committing do state so, and specify the Author: name <[e-mail]> line for commit attribution.

[• xldenis]

@lebedev.ri yes, I do, I don't actually know what the next step is here.

For the attribution

Author: Xavier Denis <[e-mail]>

is fine. Unless you want me to edit the patch message directly?

llvm/lib/Analysis/InstructionSimplify.cpp

if (RHS_CR.contains(LHS_CR))
       return ConstantInt::getTrue(ITy);
     if (RHS_CR.inverse().contains(LHS_CR))
       return ConstantInt::getFalse(ITy);
   }
 
   return nullptr;
 }
 
 /// TODO: A large part of this logic is duplicated in InstCombine's
 /// foldICmpBinOp(). We should be able to share that and avoid the code
 /// duplication.
 static Value *simplifyICmpWithBinOp(CmpInst::Predicate Pred, Value *LHS,
                                     Value *RHS, const SimplifyQuery &Q,
                                     unsigned MaxRecurse) {
   Type *ITy = GetCompareTy(LHS); // The return type.
 
   BinaryOperator *LBO = dyn_cast<BinaryOperator>(LHS);
   BinaryOperator *RBO = dyn_cast<BinaryOperator>(RHS);
if (RBO && match(RBO, m_URem(m_Value(), m_Specific(LHS)))) {
     }
     case ICmpInst::ICMP_EQ:
     case ICmpInst::ICMP_ULT:
     case ICmpInst::ICMP_ULE:
       return getFalse(ITy);
     }
   }
 
+  // icmp pred (urem Y, X), Y
+  if (LBO && match(LBO, m_URem(m_Specific(RHS), m_Value()))) {
+    if (Pred == ICmpInst::ICMP_ULE)
+      return getTrue(ITy);
+    if (Pred == ICmpInst::ICMP_UGT)
+      return getFalse(ITy);
+  }
+
+  // icmp pred Y, (urem Y, X),
+  if (RBO && match(RBO, m_URem(m_Specific(LHS), m_Value()))) {
+    if (Pred == ICmpInst::ICMP_ULE)
+      return getFalse(ITy);
+    if (Pred == ICmpInst::ICMP_UGT)
+      return getTrue(ITy);
+  }
+
   // x >> y <=u x
   // x udiv y <=u x.
   if (LBO && (match(LBO, m_LShr(m_Specific(RHS), m_Value())) ||
               match(LBO, m_UDiv(m_Specific(RHS), m_Value())))) {
     // icmp pred (X op Y), X
     if (Pred == ICmpInst::ICMP_UGT)
       return getFalse(ITy);
     if (Pred == ICmpInst::ICMP_ULE)

llvm/test/Transforms/InstSimplify/compare.ll

 ; CHECK-NEXT:    [[B:%.*]] = icmp sgt i32 [[A]], [[X]]
 ; CHECK-NEXT:    ret i1 [[B]]
 ;
   %A = urem i32 1, %X
   %B = icmp sgt i32 %A, %X
   ret i1 %B
 }
 
+define i1 @urem8(i32 %X, i32 %Y) {
+  ; CHECK-LABEL: @urem8(
+  ; CHECK-NEXT: ret i1 true
+  %A = urem i32 %X, %Y
+  %B = icmp ule i32 %A, %Y
+  ret i1 %B
+}
+
+define i1 @urem9(i32 %X, i32 %Y) {
+  ; CHECK-LABEL: @urem9(
+  ; CHECK-NEXT: ret i1 false
+  %A = urem i32 %X, %Y
+  %B = icmp ugt i32 %A, %Y
+  ret i1 %B
+}
+
+define i1 @urem10(i8 %X, i8 %Y) {
+  ; CHECK-LABEL: @urem8(
+  ; CHECK-NEXT: ret i1 true
+  %A = urem i8 %X, %Y
+  %B = icmp ule i8 %Y, %A
+  ret i1 %B
+}
+
+define i1 @ure11(i8 %X, i8 %Y) {
+  ; CHECK-LABEL: @urem9(
+  ; CHECK-NEXT: ret i1 false
+  %A = urem i8 %X, %Y
+  %B = icmp ugt i8 %Y, %A
+  ret i1 %B
+}
+
 ; PR9343 #15
 define i1 @srem2(i16 %X, i32 %Y) {
 ; CHECK-LABEL: @srem2(
 ; CHECK-NEXT:    ret i1 false
 ;
   %A = zext i16 %X to i32
   %B = add nsw i32 %A, 1
   %C = srem i32 %B, %Y