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
@@ -2301,21 +2301,95 @@
   return false;
 }
 
+// Helper for `isKnownNonNullFromDominatingCondition` to actually check the
+// dominating condition.
+static bool checkDominatingConditionForNonNull(const Value *V, const User *U,
+                                               const Query &Q) {
+  const Instruction *CtxI = Q.CxtI;
+  const DominatorTree *DT = Q.DT;
+
+  // Consider only compare instructions uniquely controlling a branch
+  Value *RHS;
+  CmpInst::Predicate Pred;
+  bool NonNullIfTrue;
+  const User *CmpUse = nullptr;
+  if (match(U, m_c_ICmp(Pred, m_Specific(V), m_Value(RHS)))) {
+    CmpUse = U;
+    if (cmpExcludesZero(Pred, RHS))
+      NonNullIfTrue = true;
+    else if (cmpExcludesZero(CmpInst::getInversePredicate(Pred), RHS))
+      NonNullIfTrue = false;
+    else
+      return false;
+  } else
+    return false;
+
+  SmallVector<const User *, 4> WorkList;
+  SmallPtrSet<const User *, 4> Visited;
+  for (const auto *CmpU : CmpUse->users()) {
+
+    assert(WorkList.empty() && "Should be!");
+    if (Visited.insert(CmpU).second)
+      WorkList.push_back(CmpU);
+
+    while (!WorkList.empty()) {
+      auto *Curr = WorkList.pop_back_val();
+
+      // If a user is an AND, add all its users to the work list. We only
+      // propagate "pred != null" condition through AND because it is only
+      // correct to assume that all conditions of AND are met in true
+      // branch.
+      // TODO: Support similar logic of OR and EQ predicate?
+      if (NonNullIfTrue)
+        if (match(Curr, m_LogicalAnd(m_Value(), m_Value()))) {
+          for (const auto *CurrU : Curr->users())
+            if (Visited.insert(CurrU).second)
+              WorkList.push_back(CurrU);
+          continue;
+        }
+
+      if (const BranchInst *BI = dyn_cast<BranchInst>(Curr)) {
+        assert(BI->isConditional() && "uses a comparison!");
+
+        BasicBlock *NonNullSuccessor = BI->getSuccessor(NonNullIfTrue ? 0 : 1);
+        BasicBlockEdge Edge(BI->getParent(), NonNullSuccessor);
+        if (Edge.isSingleEdge() && DT->dominates(Edge, CtxI->getParent()))
+          return true;
+      } else if (NonNullIfTrue && isGuard(Curr) &&
+                 DT->dominates(cast<Instruction>(Curr), CtxI)) {
+        return true;
+      }
+    }
+  }
+
+  return false;
+}
+
 static bool isKnownNonNullFromDominatingCondition(const Value *V,
-                                                  const Instruction *CtxI,
-                                                  const DominatorTree *DT) {
+                                                  unsigned DomDepth,
+                                                  const Query &Q) {
+  const Instruction *CtxI = Q.CxtI;
+  const DominatorTree *DT = Q.DT;
+
   if (isa<Constant>(V))
     return false;
 
   if (!CtxI || !DT)
     return false;
 
-  unsigned NumUsesExplored = 0;
+  if (isa<Constant>(V))
+    return false;
+
+  if (DomDepth++ >= MaxAnalysisRecursionDepth)
+    return false;
+
+  // Scale down number of uses explored with depth to avoid otherwise
+  // potentially very large exponential explosition.
+  unsigned NumUsesRemaining = (DomConditionsMaxUses / DomDepth) + 1;
   for (const auto *U : V->users()) {
     // Avoid massive lists
-    if (NumUsesExplored >= DomConditionsMaxUses)
+    if (NumUsesRemaining-- == 0)
       break;
-    NumUsesExplored++;
 
     // If the value is used as an argument to a call or invoke, then argument
     // attributes may provide an answer about null-ness.
@@ -2336,56 +2410,44 @@
         return true;
     }
 
-    // Consider only compare instructions uniquely controlling a branch
-    Value *RHS;
-    CmpInst::Predicate Pred;
-    if (!match(U, m_c_ICmp(Pred, m_Specific(V), m_Value(RHS))))
-      continue;
-
-    bool NonNullIfTrue;
-    if (cmpExcludesZero(Pred, RHS))
-      NonNullIfTrue = true;
-    else if (cmpExcludesZero(CmpInst::getInversePredicate(Pred), RHS))
-      NonNullIfTrue = false;
-    else
-      continue;
+    bool ImpliesNonZero = false;
+    if (auto *OpU = dyn_cast<Operator>(U)) {
+      switch (OpU->getOpcode()) {
+      case Instruction::ICmp:
+        if (checkDominatingConditionForNonNull(V, U, Q))
+          return true;
+        break;
 
-    SmallVector<const User *, 4> WorkList;
-    SmallPtrSet<const User *, 4> Visited;
-    for (const auto *CmpU : U->users()) {
-      assert(WorkList.empty() && "Should be!");
-      if (Visited.insert(CmpU).second)
-        WorkList.push_back(CmpU);
-
-      while (!WorkList.empty()) {
-        auto *Curr = WorkList.pop_back_val();
-
-        // If a user is an AND, add all its users to the work list. We only
-        // propagate "pred != null" condition through AND because it is only
-        // correct to assume that all conditions of AND are met in true branch.
-        // TODO: Support similar logic of OR and EQ predicate?
-        if (NonNullIfTrue)
-          if (match(Curr, m_LogicalAnd(m_Value(), m_Value()))) {
-            for (const auto *CurrU : Curr->users())
-              if (Visited.insert(CurrU).second)
-                WorkList.push_back(CurrU);
-            continue;
+      case Instruction::And:
+        ImpliesNonZero = true;
+        break;
+      case Instruction::Sub:
+        if (auto *C = dyn_cast<Constant>(OpU->getOperand(0)))
+          ImpliesNonZero = C->isNullValue();
+        break;
+      case Instruction::Call:
+      case Instruction::Invoke:
+        if (auto *II = dyn_cast<IntrinsicInst>(OpU)) {
+          switch (II->getIntrinsicID()) {
+          case Intrinsic::abs:
+          case Intrinsic::bitreverse:
+          case Intrinsic::bswap:
+          case Intrinsic::ctpop:
+            ImpliesNonZero = true;
+            break;
+          default:
+            break;
           }
-
-        if (const BranchInst *BI = dyn_cast<BranchInst>(Curr)) {
-          assert(BI->isConditional() && "uses a comparison!");
-
-          BasicBlock *NonNullSuccessor =
-              BI->getSuccessor(NonNullIfTrue ? 0 : 1);
-          BasicBlockEdge Edge(BI->getParent(), NonNullSuccessor);
-          if (Edge.isSingleEdge() && DT->dominates(Edge, CtxI->getParent()))
-            return true;
-        } else if (NonNullIfTrue && isGuard(Curr) &&
-                   DT->dominates(cast<Instruction>(Curr), CtxI)) {
-          return true;
         }
+        break;
+      default:
+        break;
       }
     }
+    if (ImpliesNonZero &&
+        (isKnownNonZeroFromAssume(U, Q) ||
+         isKnownNonNullFromDominatingCondition(U, DomDepth, Q)))
+      return true;
   }
 
   return false;
@@ -2547,7 +2609,7 @@
   }
 
   if (!isa<Constant>(V) &&
-      isKnownNonNullFromDominatingCondition(V, Q.CxtI, Q.DT))
+      isKnownNonNullFromDominatingCondition(V, /*DomDepth*/ 0, Q))
     return true;
 
   const Operator *I = dyn_cast<Operator>(V);
diff --git a/llvm/test/Analysis/ValueTracking/known-non-zero-through-dom-use.ll b/llvm/test/Analysis/ValueTracking/known-non-zero-through-dom-use.ll
--- a/llvm/test/Analysis/ValueTracking/known-non-zero-through-dom-use.ll
+++ b/llvm/test/Analysis/ValueTracking/known-non-zero-through-dom-use.ll
@@ -19,9 +19,7 @@
 ; CHECK-NEXT:    [[NE:%.*]] = icmp ugt i8 [[Z]], 4
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[NE]])
 ; CHECK-NEXT:    [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[Y]], 0
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[CMP0]], [[CMP1]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 [[CMP0]]
 ;
   %z = sub i8 0, %x
   %ne = icmp ugt i8 %z, 4
@@ -60,9 +58,7 @@
 ; CHECK-NEXT:    br i1 [[NE]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
 ; CHECK-NEXT:    [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[Y]], 0
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[CMP0]], [[CMP1]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 [[CMP0]]
 ; CHECK:       false:
 ; CHECK-NEXT:    call void @use1(i1 [[NE]])
 ; CHECK-NEXT:    ret i1 [[NE]]
@@ -87,9 +83,7 @@
 ; CHECK-NEXT:    [[NE:%.*]] = icmp sgt i16 [[Z]], 3
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[NE]])
 ; CHECK-NEXT:    [[CMP0:%.*]] = icmp ugt i16 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i16 [[Y]], 0
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[CMP0]], [[CMP1]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 [[CMP0]]
 ;
   %z = call i16 @llvm.bswap.i16(i16 %x)
   %ne = icmp sgt i16 %z, 3
@@ -111,11 +105,7 @@
 ; CHECK-NEXT:    ret i1 [[RT]]
 ; CHECK:       true:
 ; CHECK-NEXT:    [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[Y]], 0
-; CHECK-NEXT:    [[R1:%.*]] = or i1 [[CMP0]], [[CMP1]]
-; CHECK-NEXT:    [[RF:%.*]] = icmp eq i8 [[X]], 0
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[R1]], [[RF]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 [[CMP0]]
 ;
   %z = call i8 @llvm.bitreverse.i8(i8 %x)
   %ne = icmp slt i8 %z, -4
@@ -145,9 +135,7 @@
 ; CHECK-NEXT:    br i1 [[NE]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
 ; CHECK-NEXT:    [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[Y]], 0
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[CMP0]], [[CMP1]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 [[CMP0]]
 ; CHECK:       false:
 ; CHECK-NEXT:    call void @use1(i1 [[NE]])
 ; CHECK-NEXT:    ret i1 [[NE]]
@@ -205,9 +193,7 @@
 ; CHECK-NEXT:    br i1 [[NE]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
 ; CHECK-NEXT:    [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[Y]], 0
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[CMP0]], [[CMP1]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 [[CMP0]]
 ; CHECK:       false:
 ; CHECK-NEXT:    [[RT:%.*]] = icmp eq i8 [[X]], 0
 ; CHECK-NEXT:    call void @use1(i1 [[RT]])
@@ -243,9 +229,8 @@
 ; CHECK-NEXT:    [[R:%.*]] = or i1 [[CMP0]], [[CMP1]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ; CHECK:       false:
-; CHECK-NEXT:    [[RT:%.*]] = icmp eq i8 [[X]], 0
-; CHECK-NEXT:    call void @use1(i1 [[RT]])
-; CHECK-NEXT:    ret i1 [[RT]]
+; CHECK-NEXT:    call void @use1(i1 false)
+; CHECK-NEXT:    ret i1 false
 ;
   %z = and i8 %x, 123
   %ne = icmp slt i8 %z, 5
@@ -306,9 +291,7 @@
 ; CHECK-NEXT:    ret i1 [[RT]]
 ; CHECK:       false:
 ; CHECK-NEXT:    [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[Y]], 0
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[CMP0]], [[CMP1]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 [[CMP0]]
 ;
   %z = and i8 %x, 123
   %z2 = sub i8 0, %z
@@ -343,9 +326,7 @@
 ; CHECK-NEXT:    ret i1 [[RT]]
 ; CHECK:       false:
 ; CHECK-NEXT:    [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[Y]], 0
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[CMP0]], [[CMP1]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 [[CMP0]]
 ;
   %z = and i8 %x, 123
   %z2 = sub i8 0, %z
@@ -381,9 +362,7 @@
 ; CHECK-NEXT:    ret i1 [[RT]]
 ; CHECK:       false:
 ; CHECK-NEXT:    [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[Y]], 0
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[CMP0]], [[CMP1]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 [[CMP0]]
 ;
   %z = and i8 %x, 123
   %z2 = sub i8 0, %z
@@ -415,9 +394,7 @@
 ; CHECK-NEXT:    [[NE:%.*]] = icmp ne i8 [[Z4]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[NE]])
 ; CHECK-NEXT:    [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[Y]], 0
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[CMP0]], [[CMP1]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 [[CMP0]]
 ;
   %z = and i8 %x, 123
   %z2 = sub i8 0, %z