diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -7909,14 +7909,38 @@
   case CmpInst::ICMP_ULE: {
     const APInt *C;
 
-    // LHS u<= LHS +_{nuw} C   for any C
-    if (match(RHS, m_NUWAdd(m_Specific(LHS), m_APInt(C))))
+    // LHS u<= LHS +_{nuw} V for any V
+    if (match(RHS, m_NUWAdd(m_Specific(LHS), m_Value())))
       return true;
 
+    // RHS -_{nuw} V u<= RHS for any V
+    if (match(LHS, m_NUWSub(m_Specific(RHS), m_Value())))
+      return true;
+
+    // LHS u<= LHS *_{nuw} C if C is not zero
+    if (match(RHS, m_NUWMul(m_Specific(LHS), m_APInt(C))))
+      return !C->isZero();
+
+    // RHS u/ C u<= RHS if C is not Zero
+    if (match(LHS, m_UDiv(m_Specific(RHS), m_APInt(C))))
+      return !C->isZero();
+
+    // RHS u% C u<= RHS if C is not zero
+    if (match(LHS, m_URem(m_Specific(RHS), m_APInt(C))))
+      return !C->isZero();
+
     // RHS >> V u<= RHS for any V
     if (match(LHS, m_LShr(m_Specific(RHS), m_Value())))
       return true;
 
+    // LHS u<= LHS <<_{nuw} V for any V
+    if (match(RHS, m_NUWShl(m_Specific(LHS), m_Value())))
+      return true;
+
+    // RHS & V u<= RHS for any V
+    if (match(LHS, m_And(m_Specific(RHS), m_Value())))
+      return true;
+
     // Match A to (X +_{nuw} CA) and B to (X +_{nuw} CB)
     auto MatchNUWAddsToSameValue = [&](const Value *A, const Value *B,
                                        const Value *&X,
diff --git a/llvm/test/Transforms/InstSimplify/implies.ll b/llvm/test/Transforms/InstSimplify/implies.ll
--- a/llvm/test/Transforms/InstSimplify/implies.ll
+++ b/llvm/test/Transforms/InstSimplify/implies.ll
@@ -478,11 +478,7 @@
 ; i +_{nuw} V <u L ==> i <u L
 define i1 @add(i32 %length.i, i32 %i, i32 %v) {
 ; CHECK-LABEL: @add(
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw i32 [[I:%.*]], [[V:%.*]]
-; CHECK-NEXT:    [[COND1:%.*]] = icmp ult i32 [[I]], [[LENGTH_I:%.*]]
-; CHECK-NEXT:    [[COND2:%.*]] = icmp ult i32 [[ADD]], [[LENGTH_I]]
-; CHECK-NEXT:    [[RES:%.*]] = icmp ule i1 [[COND2]], [[COND1]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %add = add nuw i32 %i, %v
   %cond1 = icmp ult i32 %i, %length.i
@@ -494,11 +490,7 @@
 ; i <u L ==> i -_{nuw} V <u L
 define i1 @sub(i32 %length.i, i32 %i, i32 %v) {
 ; CHECK-LABEL: @sub(
-; CHECK-NEXT:    [[SUB:%.*]] = sub nuw i32 [[I:%.*]], [[V:%.*]]
-; CHECK-NEXT:    [[COND1:%.*]] = icmp ult i32 [[I]], [[LENGTH_I:%.*]]
-; CHECK-NEXT:    [[COND2:%.*]] = icmp ult i32 [[SUB]], [[LENGTH_I]]
-; CHECK-NEXT:    [[RES:%.*]] = icmp ule i1 [[COND1]], [[COND2]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %sub = sub nuw i32 %i, %v
   %cond1 = icmp ult i32 %i, %length.i
@@ -510,11 +502,7 @@
 ; i *_{nuw} C <u L ==> i <u L for C != 0
 define i1 @mul(i32 %length.i, i32 %i) {
 ; CHECK-LABEL: @mul(
-; CHECK-NEXT:    [[MUL:%.*]] = mul nuw i32 [[I:%.*]], 2
-; CHECK-NEXT:    [[COND1:%.*]] = icmp ult i32 [[I]], [[LENGTH_I:%.*]]
-; CHECK-NEXT:    [[COND2:%.*]] = icmp ult i32 [[MUL]], [[LENGTH_I]]
-; CHECK-NEXT:    [[RES:%.*]] = icmp ule i1 [[COND2]], [[COND1]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %mul = mul nuw i32 %i, 2
   %cond1 = icmp ult i32 %i, %length.i
@@ -540,11 +528,7 @@
 ; i <u L ==> i / C <u L for C != 0
 define i1 @udiv(i32 %length.i, i32 %i) {
 ; CHECK-LABEL: @udiv(
-; CHECK-NEXT:    [[UDIV:%.*]] = udiv i32 [[I:%.*]], 3
-; CHECK-NEXT:    [[COND1:%.*]] = icmp ult i32 [[I]], [[LENGTH_I:%.*]]
-; CHECK-NEXT:    [[COND2:%.*]] = icmp ult i32 [[UDIV]], [[LENGTH_I]]
-; CHECK-NEXT:    [[RES:%.*]] = icmp ule i1 [[COND1]], [[COND2]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %udiv = udiv i32 %i, 3
   %cond1 = icmp ult i32 %i, %length.i
@@ -556,11 +540,7 @@
 ; i <u L ==> i % C <u L for C != 0
 define i1 @urem(i32 %length.i, i32 %i) {
 ; CHECK-LABEL: @urem(
-; CHECK-NEXT:    [[UREM:%.*]] = urem i32 [[I:%.*]], 2
-; CHECK-NEXT:    [[COND1:%.*]] = icmp ult i32 [[I]], [[LENGTH_I:%.*]]
-; CHECK-NEXT:    [[COND2:%.*]] = icmp ult i32 [[UREM]], [[LENGTH_I]]
-; CHECK-NEXT:    [[RES:%.*]] = icmp ule i1 [[COND1]], [[COND2]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %urem = urem i32 %i, 2
   %cond1 = icmp ult i32 %i, %length.i
@@ -596,11 +576,7 @@
 ; i <<_{nuw} V <u L ==> i <u L
 define i1 @shl(i32 %length.i, i32 %i, i32 %v) {
 ; CHECK-LABEL: @shl(
-; CHECK-NEXT:    [[SHL:%.*]] = shl nuw i32 [[I:%.*]], [[V:%.*]]
-; CHECK-NEXT:    [[COND1:%.*]] = icmp ult i32 [[I]], [[LENGTH_I:%.*]]
-; CHECK-NEXT:    [[COND2:%.*]] = icmp ult i32 [[SHL]], [[LENGTH_I]]
-; CHECK-NEXT:    [[RES:%.*]] = icmp ule i1 [[COND2]], [[COND1]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %shl = shl nuw i32 %i, %v
   %cond1 = icmp ult i32 %i, %length.i
@@ -609,14 +585,10 @@
   ret i1 %res
 }
 
-; i <u L ==> i && C <u L
+; i <u L ==> i & C <u L
 define i1 @and(i32 %length.i, i32 %i, i32 %v) {
 ; CHECK-LABEL: @and(
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[I:%.*]], [[V:%.*]]
-; CHECK-NEXT:    [[COND1:%.*]] = icmp ult i32 [[I]], [[LENGTH_I:%.*]]
-; CHECK-NEXT:    [[COND2:%.*]] = icmp ult i32 [[AND]], [[LENGTH_I]]
-; CHECK-NEXT:    [[RES:%.*]] = icmp ule i1 [[COND1]], [[COND2]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %and = and i32 %i, %v
   %cond1 = icmp ult i32 %i, %length.i