Index: lib/Transforms/InstCombine/InstCombine.h
===================================================================
--- lib/Transforms/InstCombine/InstCombine.h
+++ lib/Transforms/InstCombine/InstCombine.h
@@ -191,6 +191,8 @@
                               ConstantInt *DivRHS);
   Instruction *FoldICmpCstShrCst(ICmpInst &I, Value *Op, Value *A,
                                  ConstantInt *CI1, ConstantInt *CI2);
+  Instruction *FoldUICmpCstShrCst(ICmpInst &I, Value *Op, Value *A,
+                                  ConstantInt *CI1, ConstantInt *CI2);
   Instruction *FoldICmpCstShlCst(ICmpInst &I, Value *Op, Value *A,
                                  ConstantInt *CI1, ConstantInt *CI2);
   Instruction *FoldICmpAddOpCst(Instruction &ICI, Value *X, ConstantInt *CI,
Index: lib/Transforms/InstCombine/InstCombineCompares.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineCompares.cpp
+++ lib/Transforms/InstCombine/InstCombineCompares.cpp
@@ -1135,6 +1135,94 @@
   return getConstant(false);
 }
 
+Instruction *InstCombiner::FoldUICmpCstShrCst(ICmpInst &I, Value *Op, Value *A,
+                                              ConstantInt *CI1,
+                                              ConstantInt *CI2) {
+
+  Instruction *Result = nullptr;
+
+  APInt AP1 = CI1->getValue();
+  APInt AP2 = CI2->getValue();
+
+  bool IsAShr = isa<AShrOperator>(Op);
+
+  // Both AP1, AP2 are non-zero
+  if (!AP1 || !AP2) {
+    return Result;
+  }
+
+  if (AP1 == AP2) {
+    if (AP1.isNegative() && IsAShr) {
+      if (!AP1.isAllOnesValue()) {
+        if (I.getPredicate() == I.ICMP_ULE) {
+          Result = new ICmpInst(I.ICMP_EQ, A,
+                                ConstantInt::getNullValue(A->getType()));
+        } else if (I.getPredicate() == I.ICMP_UGT) {
+          Result = new ICmpInst(I.ICMP_NE, A,
+                                ConstantInt::getNullValue(A->getType()));
+        }
+      }
+    } else if (I.getPredicate() == I.ICMP_ULT) {
+      Result =
+          new ICmpInst(I.ICMP_UGT, A, ConstantInt::getNullValue(A->getType()));
+    } else if (I.getPredicate() == I.ICMP_UGE) {
+      Result =
+          new ICmpInst(I.ICMP_EQ, A, ConstantInt::getNullValue(A->getType()));
+    }
+  } else if (IsAShr && AP1.isNegative()) {
+    if (AP2.slt(AP1) && !AP1.isAllOnesValue()) {
+      int Shift = (~AP2).logBase2() - (~AP1).logBase2();
+
+      if (AP2.ashr(Shift) == AP1) {
+        Result = new ICmpInst(I.getPredicate(), A,
+                              ConstantInt::get(A->getType(), Shift));
+      } else {
+        if (AP2.ashr(Shift).ugt(AP1))
+          Shift--;
+        if (I.getPredicate() == I.ICMP_ULT || I.getPredicate() == I.ICMP_ULE) {
+          Result = new ICmpInst(I.ICMP_ULT, A,
+                                ConstantInt::get(A->getType(), Shift + 1));
+        } else {
+          Result = new ICmpInst(I.ICMP_UGT, A,
+                                ConstantInt::get(A->getType(), Shift));
+        }
+      }
+    }
+  } else if (!IsAShr || !AP1.isNegative()) {
+    if (AP1.ule(AP2)) {
+      int Shift = AP1.countLeadingZeros() - AP2.countLeadingZeros();
+      if (AP1 == AP2.lshr(Shift)) {
+        if (I.getPredicate() == I.ICMP_ULT) {
+          Result = new ICmpInst(I.ICMP_UGT, A,
+                                ConstantInt::get(A->getType(), Shift));
+        } else if (I.getPredicate() == I.ICMP_ULE) {
+          Result = new ICmpInst(I.ICMP_UGE, A,
+                                ConstantInt::get(A->getType(), Shift));
+        } else if (I.getPredicate() == I.ICMP_UGT) {
+          Result = new ICmpInst(I.ICMP_ULT, A,
+                                ConstantInt::get(A->getType(), Shift));
+        } else {
+          Result = new ICmpInst(I.ICMP_ULE, A,
+                                ConstantInt::get(A->getType(), Shift));
+        }
+      } else {
+        if (AP1.ugt(AP2.lshr(Shift))) {
+          Shift--;
+        }
+        if (I.getPredicate() == I.ICMP_ULT || I.getPredicate() == I.ICMP_ULE) {
+          Result = new ICmpInst(I.ICMP_UGT, A,
+                                ConstantInt::get(A->getType(), Shift));
+        } else {
+          Result = new ICmpInst(I.ICMP_ULE, A,
+                                ConstantInt::get(A->getType(), Shift));
+        }
+      }
+    }
+  }
+
+  return Result;
+}
+
 /// visitICmpInstWithInstAndIntCst - Handle "icmp (instr, intcst)".
 ///
 Instruction *InstCombiner::visitICmpInstWithInstAndIntCst(ICmpInst &ICI,
@@ -1311,7 +1399,7 @@
               cast<ConstantInt>(ConstantExpr::getShl(AndCst, ShAmt));
             ConstantInt *ShiftedRHSCst =
               cast<ConstantInt>(ConstantExpr::getShl(RHS, ShAmt));
-            
+
             if (!ShiftedAndCst->isNegative() && !ShiftedRHSCst->isNegative())
               CanFold = true;
           }
@@ -2591,15 +2679,22 @@
                           Builder->getInt(CI->getValue()-1));
     }
 
-    if (I.isEquality()) {
-      ConstantInt *CI2;
-      if (match(Op0, m_AShr(m_ConstantInt(CI2), m_Value(A))) ||
-          match(Op0, m_LShr(m_ConstantInt(CI2), m_Value(A)))) {
+    ConstantInt *CI2;
+    if (match(Op0, m_AShr(m_ConstantInt(CI2), m_Value(A))) ||
+        match(Op0, m_LShr(m_ConstantInt(CI2), m_Value(A)))) {
+      if (I.isEquality()) {
         // (icmp eq/ne (ashr/lshr const2, A), const1)
         if (Instruction *Inst = FoldICmpCstShrCst(I, Op0, A, CI, CI2))
           return Inst;
       }
-      if (match(Op0, m_Shl(m_ConstantInt(CI2), m_Value(A)))) {
+      if (I.isUnsigned()) {
+        // (icmp ugt/uge/ult/ule (ashr/lshr const2, A), const1)
+        if (Instruction *Inst = FoldUICmpCstShrCst(I, Op0, A, CI, CI2))
+          return Inst;
+      }
+    }
+    if (match(Op0, m_Shl(m_ConstantInt(CI2), m_Value(A)))) {
+      if (I.isEquality()) {
         // (icmp eq/ne (shl const2, A), const1)
         if (Instruction *Inst = FoldICmpCstShlCst(I, Op0, A, CI, CI2))
           return Inst;
Index: test/Transforms/InstCombine/icmp-shr.ll
===================================================================
--- test/Transforms/InstCombine/icmp-shr.ll
+++ test/Transforms/InstCombine/icmp-shr.ll
@@ -376,3 +376,219 @@
   %cmp = icmp eq i32 %shr, -2
   ret i1 %cmp
 }
+
+define i1 @ashr_ult_ap1_equal_ap2(i8 %a) {
+; CHECK-LABEL: @ashr_ult_ap1_equal_ap2(
+; CHECK-NEXT: %cmp = icmp ne i8 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = ashr i8 13, %a
+  %cmp = icmp ult i8 %shr, 13
+  ret i1 %cmp
+}
+
+define i1 @ashr_uge_ap1_equal_ap2(i8 %a) {
+; CHECK-LABEL: @ashr_uge_ap1_equal_ap2(
+; CHECK-NEXT: %cmp = icmp eq i8 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = ashr i8 13, %a
+  %cmp = icmp uge i8 %shr, 13
+  ret i1 %cmp
+}
+
+define i1 @lshr_ult_ap1_equal_ap2(i8 %a) {
+; CHECK-LABEL: @lshr_ult_ap1_equal_ap2(
+; CHECK-NEXT: %cmp = icmp ne i8 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i8 13, %a
+  %cmp = icmp ult i8 %shr, 13
+  ret i1 %cmp
+}
+
+define i1 @lshr_uge_ap1_equal_ap2(i8 %a) {
+; CHECK-LABEL: @lshr_uge_ap1_equal_ap2(
+; CHECK-NEXT: %cmp = icmp eq i8 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i8 13, %a
+  %cmp = icmp uge i8 %shr, 13
+  ret i1 %cmp
+}
+
+define i1 @ashr_ugt_ap1_equal_ap2_negative(i8 %a) {
+; CHECK-LABEL: @ashr_ugt_ap1_equal_ap2_negative(
+; CHECK-NEXT: %cmp = icmp ne i8 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = ashr i8 -13, %a
+  %cmp = icmp ugt i8 %shr, -13
+  ret i1 %cmp
+}
+
+define i1 @ashr_ule_ap1_equal_ap2_negative(i8 %a) {
+; CHECK-LABEL: @ashr_ule_ap1_equal_ap2_negative(
+; CHECK-NEXT: %cmp = icmp eq i8 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = ashr i8 -13, %a
+  %cmp = icmp ule i8 %shr, -13
+  ret i1 %cmp
+}
+
+define i1 @lshr_uge_ap1_equal_ap2_negative(i8 %a) {
+; CHECK-LABEL: @lshr_uge_ap1_equal_ap2_negative(
+; CHECK-NEXT: %cmp = icmp eq i8 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i8 -13, %a
+  %cmp = icmp uge i8 %shr, -13
+  ret i1 %cmp
+}
+
+define i1 @lshr_ult_ap1_equal_ap2_negative(i8 %a) {
+; CHECK-LABEL: @lshr_ult_ap1_equal_ap2_negative(
+; CHECK-NEXT: %cmp = icmp ne i8 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i8 -13, %a
+  %cmp = icmp ult i8 %shr, -13
+  ret i1 %cmp
+}
+
+define i1 @ashr_ugt_ap1_negative_ap2_negative_ap1(i32 %a) {
+; CHECK-LABEL: @ashr_ugt_ap1_negative_ap2_negative_ap1(
+; CHECK-NEXT: %cmp = icmp ne i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = ashr i32 -22, %a
+  %cmp = icmp ugt i32 %shr, -14
+  ret i1 %cmp
+}
+
+define i1 @ashr_ult_ap1_negative_ap2_negative_ap1(i32 %a) {
+; CHECK-LABEL: @ashr_ult_ap1_negative_ap2_negative_ap1(
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = ashr i32 -22, %a
+  %cmp = icmp ult i32 %shr, -14
+  ret i1 %cmp
+}
+
+define i1 @ashr_uge_ap1_negative_ap2_negative_ap1(i32 %a) {
+; CHECK-LABEL: @ashr_uge_ap1_negative_ap2_negative_ap1(
+; CHECK-NEXT: %cmp = icmp ne i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = ashr i32 -22, %a
+  %cmp = icmp uge i32 %shr, -14
+  ret i1 %cmp
+}
+
+define i1 @ashr_ule_ap1_negative_ap2_negative_ap1(i32 %a) {
+; CHECK-LABEL: @ashr_ule_ap1_negative_ap2_negative_ap1(
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = ashr i32 -22, %a
+  %cmp = icmp ule i32 %shr, -14
+  ret i1 %cmp
+}
+
+define i1 @lshr_ugt_ap1_negative_ap2_negative_ap2(i32 %a) {
+; CHECK-LABEL: @lshr_ugt_ap1_negative_ap2_negative_ap2(
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 -14, %a
+  %cmp = icmp ugt i32 %shr, -22
+  ret i1 %cmp
+}
+
+define i1 @lshr_ult_ap1_negative_ap2_negative_ap2(i32 %a) {
+; CHECK-LABEL: @lshr_ult_ap1_negative_ap2_negative_ap2(
+; CHECK-NEXT: %cmp = icmp ne i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 -14, %a
+  %cmp = icmp ult i32 %shr, -22
+  ret i1 %cmp	
+}
+
+define i1 @lshr_uge_ap1_negative_ap2_negative_ap2(i32 %a) {
+; CHECK-LABEL: @lshr_uge_ap1_negative_ap2_negative_ap2(
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 -14, %a
+  %cmp = icmp uge i32 %shr, -22
+  ret i1 %cmp
+}
+
+define i1 @lshr_ule_ap1_negative_ap2_negative_ap2(i32 %a) {
+; CHECK-LABEL: @lshr_ule_ap1_negative_ap2_negative_ap2(
+; CHECK-NEXT: %cmp = icmp ne i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 -14, %a
+  %cmp = icmp ule i32 %shr, -22
+  ret i1 %cmp
+}
+
+define i1 @lshr_ugt_ap1_positive_ap2_positive_ap2(i32 %a) {
+; CHECK-LABEL: @lshr_ugt_ap1_positive_ap2_positive_ap2(
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 14, %a
+  %cmp = icmp ugt i32 %shr, 7
+  ret i1 %cmp
+}
+
+define i1 @lshr_ult_ap1_positive_ap2_positive_ap2(i32 %a) {
+; CHECK-LABEL: @lshr_ult_ap1_positive_ap2_positive_ap2(
+; CHECK-NEXT: %cmp = icmp ugt i32 %a, 1
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 14, %a
+  %cmp = icmp ult i32 %shr, 7
+  ret i1 %cmp	
+}
+
+define i1 @lshr_uge_ap1_positive_ap2_positive_ap2(i32 %a) {
+; CHECK-LABEL: @lshr_uge_ap1_positive_ap2_positive_ap2(
+; CHECK-NEXT: %cmp = icmp ult i32 %a, 2
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 14, %a
+  %cmp = icmp uge i32 %shr, 7
+  ret i1 %cmp
+}
+
+define i1 @lshr_ule_ap1_positive_ap2_positive_ap2(i32 %a) {
+; CHECK-LABEL: @lshr_ule_ap1_positive_ap2_positive_ap2(
+; CHECK-NEXT: %cmp = icmp ne i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 14, %a
+  %cmp = icmp ule i32 %shr, 7
+  ret i1 %cmp
+}
+
+define i1 @lshr_ugt_ap1_positive_ap2_negative(i32 %a) {
+; CHECK-LABEL: @lshr_ugt_ap1_positive_ap2_negative(
+; CHECK-NEXT: %cmp = icmp ult i32 %a, 29
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 -14, %a
+  %cmp = icmp ugt i32 %shr, 7
+  ret i1 %cmp
+}
+
+define i1 @lshr_ult_ap1_positive_ap2_negative(i32 %a) {
+; CHECK-LABEL: @lshr_ult_ap1_positive_ap2_negative(
+; CHECK-NEXT: %cmp = icmp ugt i32 %a, 29
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 -14, %a
+  %cmp = icmp ult i32 %shr, 7
+  ret i1 %cmp	
+}
+
+define i1 @lshr_uge_ap1_positive_ap2_negative(i32 %a) {
+; CHECK-LABEL: @lshr_uge_ap1_positive_ap2_negative(
+; CHECK-NEXT: %cmp = icmp ult i32 %a, 30
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 -14, %a
+  %cmp = icmp uge i32 %shr, 7
+  ret i1 %cmp
+}
+
+define i1 @lshr_ule_ap1_positive_ap2_negative(i32 %a) {
+; CHECK-LABEL: @lshr_ule_ap1_positive_ap2_negative(
+; CHECK-NEXT: %cmp = icmp ugt i32 %a, 28
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 -14, %a
+  %cmp = icmp ule i32 %shr, 7
+  ret i1 %cmp
+}