diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
--- a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
@@ -5132,12 +5132,14 @@
     return WillIncrement ? !C->isMaxValue(IsSigned) : !C->isMinValue(IsSigned);
   };
 
-  // For scalars, SimplifyICmpInst should have already handled
-  // the edge cases for us, so we just assert on them.
+  // For scalars, SimplifyICmpInst should have already handled the edge cases
+  // for us, although that depends on if we already have visited the ICmp
+  // instruction or not (we might have to wait for the next iteration).
   // For vectors, we must handle the edge cases.
   if (isa<ConstantInt>(C)) {
+    if (!ConstantIsOk(cast<ConstantInt>(C)))
+      return llvm::None;
     // A <= MAX -> TRUE ; A >= MIN -> TRUE
-    assert(ConstantIsOk(cast<ConstantInt>(C)));
   } else if (Type->isVectorTy()) {
     // TODO? If the edge cases for vectors were guaranteed to be handled as they
     // are for scalar, we could remove the min/max checks. However, to do that,
diff --git a/llvm/test/Transforms/InstCombine/pr43376-getFlippedStrictnessPredicateAndConstant-assert.ll b/llvm/test/Transforms/InstCombine/pr43376-getFlippedStrictnessPredicateAndConstant-assert.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/InstCombine/pr43376-getFlippedStrictnessPredicateAndConstant-assert.ll
@@ -0,0 +1,36 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+; We used to hit an assertion in getFlippedStrictnessPredicateAndConstant due
+; to assuming that edge cases such as %cmp (ult x, 0) already has been
+; simplified. But that depends on the worklist order, so that is not always
+; guaranteed.
+
+define i16 @d(i16* %d.a, i16* %d.b) {
+; CHECK-LABEL: @d(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[T0:%.*]] = load i16, i16* [[D_A:%.*]], align 1
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i16 [[T0]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[LAND_END:%.*]], label [[LAND_RHS:%.*]]
+; CHECK:       land.rhs:
+; CHECK-NEXT:    br label [[LAND_END]]
+; CHECK:       land.end:
+; CHECK-NEXT:    ret i16 -1
+;
+entry:
+  %t0 = load i16, i16* %d.a, align 1
+  %tobool = icmp ne i16 %t0, 0
+  br i1 %tobool, label %land.rhs, label %land.end
+
+land.rhs:
+  %t1 = load i16, i16* %d.b, align 1
+  %cmp = icmp ult i16 %t1, 0
+  br label %land.end
+
+land.end:
+  %t2 = phi i1 [ false, %entry ], [ %cmp, %land.rhs ]
+  %land.ext = zext i1 %t2 to i16
+  %mul = mul nsw i16 %land.ext, 3
+  %neg = xor i16 %mul, -1
+  ret i16 %neg
+}