Simplify `x >=u x >> y` and `x >=u x udiv y`

[arthurprs]

Summary

Extends InstSimplify to handle both x >=u x >> y and x >=u x udiv y.

This is a folloup of rL258422 and https://github.com/rust-lang/rust/pull/30917
where llvm failed to optimize away the bounds checking in a binary search.

[arthurprs]

Added Sanjoy Das as the contribution guide suggests.

[sanjoy]

Please upload with full context or use arcanist: http://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface

[arthurprs]

Update diff to include more context.

[arthurprs]

Add more tests covering all 4 cases.

[sanjoy]

lgtm

[arthurprs]

Thank you @sanjoy, could you commit it or point me to someone?

llvm/trunk/lib/Analysis/InstructionSimplify.cpp

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);
   }
 
+  // x >=u x >> y
+  // x >=u x udiv y.
+  if (RBO && (match(RBO, m_LShr(m_Specific(LHS), m_Value())) ||
+              match(RBO, m_UDiv(m_Specific(LHS), m_Value())))) {
+    // icmp pred X, (X op Y)
+    if (Pred == ICmpInst::ICMP_ULT)
+      return getFalse(ITy);
+    if (Pred == ICmpInst::ICMP_UGE)
+      return getTrue(ITy);
+  }
+
   // handle:
   //   CI2 << X == CI
   //   CI2 << X != CI
   //
   //   where CI2 is a power of 2 and CI isn't
   if (auto *CI = dyn_cast<ConstantInt>(RHS)) {
     const APInt *CI2Val, *CIVal = &CI->getValue();
     if (LBO && match(LBO, m_Shl(m_APInt(CI2Val), m_Value())) &&

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

 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 @lshr6(i32 %X, i32 %Y) {
+; CHECK-LABEL: @lshr6(
+  %A = lshr i32 %X, %Y
+  %C = icmp ult i32 %X, %A
+  ret i1 %C
+; CHECK: ret i1 false
+}
+
+define i1 @lshr7(i32 %X, i32 %Y) {
+; CHECK-LABEL: @lshr7(
+  %A = lshr i32 %X, %Y
+  %C = icmp uge i32 %X, %A
+  ret i1 %C
+; CHECK: ret i1 true
+}
+
 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
 }
 

 define i1 @udiv6(i32 %X) nounwind {
 ; CHECK-LABEL: @udiv6(
   %A = udiv i32 1, %X
   %C = icmp eq i32 %A, 0
   ret i1 %C
 ; CHECK: ret i1 %C
 }
 
+define i1 @udiv7(i32 %X, i32 %Y) {
+; CHECK-LABEL: @udiv7(
+  %A = udiv i32 %X, %Y
+  %C = icmp ult i32 %X, %A
+  ret i1 %C
+; CHECK: ret i1 false
+}
+
+define i1 @udiv8(i32 %X, i32 %Y) {
+; CHECK-LABEL: @udiv8(
+  %A = udiv i32 %X, %Y
+  %C = icmp uge i32 %X, %A
+  ret i1 %C
+; CHECK: ret i1 true
+}
+
 define i1 @mul1(i32 %X) {
 ; CHECK-LABEL: @mul1(
 ; Square of a non-zero number is non-zero if there is no overflow.
   %Y = or i32 %X, 1
   %M = mul nuw i32 %Y, %Y
   %C = icmp eq i32 %M, 0
   ret i1 %C
 ; CHECK: ret i1 false