Simplify (x >> y) <= x

[ranma42]

Summary

This commit extends the patterns recognised by InstSimplify to also handle (x >> y) <= x in the same way as (x /u y) <= x.

The missing optimisation was found investigating why LLVM did not optimise away bound checks in a binary search: https://github.com/rust-lang/rust/pull/30917

I was did not like duplicating the code for udiv and lshr, so I tried to replicate the pattern match as in ValueTracking.cpp:1803.

[ranma42]

Added the author of the original code and the owner of IR Constant Folder, InstCombine as reviewers, as suggested by the code reviews guide.

[ranma42]

Phabricator says "Action required", but I do not know what is the next step.
The guide "Code Reviews with Phabricator" seems to indicate that this can now be committed to trunk, but I do not have commit access.

Sorry if I have misused the system, I have never used Phabricator nor posted patches for LLVM.

[mehdi_amini]

Usually you just mention that you don't have commit access and someone will commit it for you, if Sanjoy doesn't do it by tonight I'll commit it for you.

llvm/trunk/lib/Analysis/InstructionSimplify.cpp

case ICmpInst::ICMP_SLE:
       // fall-through
     case ICmpInst::ICMP_EQ:
     case ICmpInst::ICMP_ULT:
     case ICmpInst::ICMP_ULE:
       return getFalse(ITy);
     }
   }
 
+  // x >> y <=u x
   // x udiv y <=u x.
-  if (LBO && match(LBO, m_UDiv(m_Specific(RHS), m_Value()))) {
-    // icmp pred (X /u Y), 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)
       return getTrue(ITy);
   }
 
   // handle:
   //   CI2 << X == CI

llvm/trunk/test/Transforms/InstSimplify/compare.ll

 define i1 @lshr3(i32 %x) {
 ; CHECK-LABEL: @lshr3(
   %s = lshr i32 %x, %x
   %c = icmp eq i32 %s, 0
   ret i1 %c
 ; CHECK: ret i1 true
 }
 
+define i1 @lshr4(i32 %X, i32 %Y) {
+; CHECK-LABEL: @lshr4(
+  %A = lshr i32 %X, %Y
+  %C = icmp ule i32 %A, %X
+  ret i1 %C
+; CHECK: ret i1 true
+}
+
+define i1 @lshr5(i32 %X, i32 %Y) {
+; CHECK-LABEL: @lshr5(
+  %A = lshr i32 %X, %Y
+  %C = icmp ugt i32 %A, %X
+  ret i1 %C
+; CHECK: ret i1 false
+}
+
 define i1 @ashr1(i32 %x) {
 ; CHECK-LABEL: @ashr1(
   %s = ashr i32 -1, %x
   %c = icmp eq i32 %s, 0
   ret i1 %c
 ; CHECK: ret i1 false
 }