diff --git a/llvm/lib/Transforms/Scalar/EarlyCSE.cpp b/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
--- a/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
+++ b/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
@@ -152,13 +152,50 @@
     std::swap(A, B);
   }
 
-  // Set flavor if we find a match, or set it to unknown otherwise; in
-  // either case, return true to indicate that this is a select we can
-  // process.
-  if (auto *CmpI = dyn_cast<ICmpInst>(Cond))
-    Flavor = matchDecomposedSelectPattern(CmpI, A, B, A, B).Flavor;
-  else
-    Flavor = SPF_UNKNOWN;
+  // Match canonical forms of abs/nabs/min/max. We are not using ValueTracking's
+  // more powerful matchSelectPattern() because it may rely on instruction flags
+  // such as "nsw". That would be incompatible with the current hashing
+  // mechanism that may remove flags to increase the likelihood of CSE.
+
+  // These are the canonical forms of abs(X) and nabs(X) created by instcombine:
+  // %N = sub i32 0, %X
+  // %C = icmp slt i32 %X, 0
+  // %ABS = select i1 %C, i32 %N, i32 %X
+  //
+  // %N = sub i32 0, %X
+  // %C = icmp slt i32 %X, 0
+  // %NABS = select i1 %C, i32 %X, i32 %N
+  Flavor = SPF_UNKNOWN;
+  CmpInst::Predicate Pred;
+  if (match(Cond, m_ICmp(Pred, m_Specific(B), m_ZeroInt())) &&
+      Pred == ICmpInst::ICMP_SLT && match(A, m_Neg(m_Specific(B)))) {
+    // ABS: B < 0 ? -B : B
+    Flavor = SPF_ABS;
+    return true;
+  }
+  if (match(Cond, m_ICmp(Pred, m_Specific(A), m_ZeroInt())) &&
+      Pred == ICmpInst::ICMP_SLT && match(B, m_Neg(m_Specific(A)))) {
+    // NABS: A < 0 ? A : -A
+    Flavor = SPF_NABS;
+    return true;
+  }
+
+  if (!match(Cond, m_ICmp(Pred, m_Specific(A), m_Specific(B)))) {
+    // Check for commuted variants of min/max by swapping predicate.
+    // If we do not match the standard or commuted patterns, this is not a
+    // recognized form of min/max, but it is still a select, so return true.
+    if (!match(Cond, m_ICmp(Pred, m_Specific(B), m_Specific(A))))
+      return true;
+    Pred = ICmpInst::getSwappedPredicate(Pred);
+  }
+
+  switch (Pred) {
+  case CmpInst::ICMP_UGT: Flavor = SPF_UMAX; break;
+  case CmpInst::ICMP_ULT: Flavor = SPF_UMIN; break;
+  case CmpInst::ICMP_SGT: Flavor = SPF_SMAX; break;
+  case CmpInst::ICMP_SLT: Flavor = SPF_SMIN; break;
+  default: break;
+  }
 
   return true;
 }
diff --git a/llvm/test/Transforms/EarlyCSE/commute.ll b/llvm/test/Transforms/EarlyCSE/commute.ll
--- a/llvm/test/Transforms/EarlyCSE/commute.ll
+++ b/llvm/test/Transforms/EarlyCSE/commute.ll
@@ -279,6 +279,8 @@
 }
 
 ; Min/max may exist with non-canonical operands. Value tracking can match those.
+; But we do not use value tracking, so we expect instcombine will canonicalize
+; this code to a form that allows CSE.
 
 define i8 @smax_nsw(i8 %a, i8 %b) {
 ; CHECK-LABEL: @smax_nsw(
@@ -286,7 +288,9 @@
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i8 [[A]], [[B]]
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i8 [[SUB]], 0
 ; CHECK-NEXT:    [[M1:%.*]] = select i1 [[CMP1]], i8 0, i8 [[SUB]]
-; CHECK-NEXT:    ret i8 0
+; CHECK-NEXT:    [[M2:%.*]] = select i1 [[CMP2]], i8 [[SUB]], i8 0
+; CHECK-NEXT:    [[R:%.*]] = sub i8 [[M2]], [[M1]]
+; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sub = sub nsw i8 %a, %b
   %cmp1 = icmp slt i8 %a, %b
@@ -297,13 +301,19 @@
   ret i8 %r
 }
 
+; Abs/nabs may exist with non-canonical operands. Value tracking can match those.
+; But we do not use value tracking, so we expect instcombine will canonicalize
+; this code to a form that allows CSE.
+
 define i8 @abs_swapped(i8 %a) {
 ; CHECK-LABEL: @abs_swapped(
 ; CHECK-NEXT:    [[NEG:%.*]] = sub i8 0, [[A:%.*]]
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sgt i8 [[A]], 0
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i8 [[A]], 0
 ; CHECK-NEXT:    [[M1:%.*]] = select i1 [[CMP1]], i8 [[A]], i8 [[NEG]]
-; CHECK-NEXT:    ret i8 [[M1]]
+; CHECK-NEXT:    [[M2:%.*]] = select i1 [[CMP2]], i8 [[NEG]], i8 [[A]]
+; CHECK-NEXT:    [[R:%.*]] = or i8 [[M2]], [[M1]]
+; CHECK-NEXT:    ret i8 [[R]]
 ;
   %neg = sub i8 0, %a
   %cmp1 = icmp sgt i8 %a, 0
@@ -331,13 +341,19 @@
   ret i8 %r
 }
 
+; Abs/nabs may exist with non-canonical operands. Value tracking can match those.
+; But we do not use value tracking, so we expect instcombine will canonicalize
+; this code to a form that allows CSE.
+
 define i8 @nabs_swapped(i8 %a) {
 ; CHECK-LABEL: @nabs_swapped(
 ; CHECK-NEXT:    [[NEG:%.*]] = sub i8 0, [[A:%.*]]
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i8 [[A]], 0
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i8 [[A]], 0
 ; CHECK-NEXT:    [[M1:%.*]] = select i1 [[CMP1]], i8 [[A]], i8 [[NEG]]
-; CHECK-NEXT:    ret i8 0
+; CHECK-NEXT:    [[M2:%.*]] = select i1 [[CMP2]], i8 [[NEG]], i8 [[A]]
+; CHECK-NEXT:    [[R:%.*]] = xor i8 [[M2]], [[M1]]
+; CHECK-NEXT:    ret i8 [[R]]
 ;
   %neg = sub i8 0, %a
   %cmp1 = icmp slt i8 %a, 0
@@ -365,7 +381,10 @@
   ret i8 %r
 }
 
-; These two tests make sure we still consider it a match when the RHS of the
+; Abs/nabs may exist with non-canonical operands. Value tracking can match those.
+; But we do not use value tracking, so we expect instcombine will canonicalize
+; this code to a form that allows CSE.
+
 ; compares are different.
 define i8 @abs_different_constants(i8 %a) {
 ; CHECK-LABEL: @abs_different_constants(
@@ -373,7 +392,9 @@
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sgt i8 [[A]], -1
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i8 [[A]], 0
 ; CHECK-NEXT:    [[M1:%.*]] = select i1 [[CMP1]], i8 [[A]], i8 [[NEG]]
-; CHECK-NEXT:    ret i8 [[M1]]
+; CHECK-NEXT:    [[M2:%.*]] = select i1 [[CMP2]], i8 [[NEG]], i8 [[A]]
+; CHECK-NEXT:    [[R:%.*]] = or i8 [[M2]], [[M1]]
+; CHECK-NEXT:    ret i8 [[R]]
 ;
   %neg = sub i8 0, %a
   %cmp1 = icmp sgt i8 %a, -1
@@ -384,13 +405,19 @@
   ret i8 %r
 }
 
+; Abs/nabs may exist with non-canonical operands. Value tracking can match those.
+; But we do not use value tracking, so we expect instcombine will canonicalize
+; this code to a form that allows CSE.
+
 define i8 @nabs_different_constants(i8 %a) {
 ; CHECK-LABEL: @nabs_different_constants(
 ; CHECK-NEXT:    [[NEG:%.*]] = sub i8 0, [[A:%.*]]
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i8 [[A]], 0
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i8 [[A]], -1
 ; CHECK-NEXT:    [[M1:%.*]] = select i1 [[CMP1]], i8 [[A]], i8 [[NEG]]
-; CHECK-NEXT:    ret i8 0
+; CHECK-NEXT:    [[M2:%.*]] = select i1 [[CMP2]], i8 [[NEG]], i8 [[A]]
+; CHECK-NEXT:    [[R:%.*]] = xor i8 [[M2]], [[M1]]
+; CHECK-NEXT:    ret i8 [[R]]
 ;
   %neg = sub i8 0, %a
   %cmp1 = icmp slt i8 %a, 0
@@ -689,3 +716,49 @@
 
   ret void
 }
+
+; This would cause an assert/crash because we matched
+; a ValueTracking select pattern that required 'nsw'
+; on an operand, but we remove that flag as part of
+; CSE matching/hashing.
+
+define void @PR41083_1(i32 %span_left, i32 %clip_left) {
+; CHECK-LABEL: @PR41083_1(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[CLIP_LEFT:%.*]], [[SPAN_LEFT:%.*]]
+; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[CLIP_LEFT]], [[SPAN_LEFT]]
+; CHECK-NEXT:    [[COND:%.*]] = select i1 [[CMP]], i32 [[SUB]], i32 0
+; CHECK-NEXT:    ret void
+;
+  %cmp = icmp sgt i32 %clip_left, %span_left
+  %sub = sub nsw i32 %clip_left, %span_left
+  %cond = select i1 %cmp, i32 %sub, i32 0
+  %cmp83292 = icmp slt i32 %cond, undef
+  %sub2 = sub i32 %clip_left, %span_left
+  %sel2 = select i1 %cmp, i32 %sub2, i32 0
+  ret void
+}
+
+; This would cause an assert/crash because we matched
+; a ValueTracking select pattern that required 'nsw'
+; on an operand, but we remove that flag as part of
+; CSE matching/hashing.
+
+define i32 @PR41083_2(i32 %p) {
+; CHECK-LABEL: @PR41083_2(
+; CHECK-NEXT:    [[S:%.*]] = sub i32 0, [[P:%.*]]
+; CHECK-NEXT:    [[A:%.*]] = ashr exact i32 [[S]], 2
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 0, [[A]]
+; CHECK-NEXT:    [[SUB:%.*]] = sub i32 0, [[A]]
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i32 [[SUB]], i32 0
+; CHECK-NEXT:    [[M:%.*]] = mul i32 [[SEL]], [[SUB]]
+; CHECK-NEXT:    ret i32 [[M]]
+;
+  %s = sub i32 0, %p
+  %a = ashr exact i32 %s, 2
+  %cmp = icmp sgt i32 0, %a
+  %sub = sub nsw i32 0, %a
+  %sel = select i1 %cmp, i32 %sub, i32 0
+  %s2 = sub i32 0, %a
+  %m = mul i32 %sel, %s2
+  ret i32 %m
+}
diff --git a/llvm/test/Transforms/PhaseOrdering/min-max-abs-cse.ll b/llvm/test/Transforms/PhaseOrdering/min-max-abs-cse.ll
--- a/llvm/test/Transforms/PhaseOrdering/min-max-abs-cse.ll
+++ b/llvm/test/Transforms/PhaseOrdering/min-max-abs-cse.ll
@@ -1,15 +1,24 @@
 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -S -O1 | FileCheck %s
-; RUN: opt -passes='default<O1>' -S < %s  | FileCheck %s
+; RUN: opt -passes='default<O1>' -S < %s | FileCheck %s
 
 ; In all tests, expect instcombine to canonicalize the select patterns
 ; for min/max/abs to allow CSE and subsequent simplification.
 
 ; sub (smax a,b), (smax a,b) --> 0
 
+; FIXME: We should canonicalize min/max to a form
+; where the cmp operands match the select operands.
+
 define i8 @smax_nsw(i8 %a, i8 %b) {
 ; CHECK-LABEL: @smax_nsw(
-; CHECK-NEXT:    ret i8 0
+; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i8 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i8 [[A]], [[B]]
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i8 [[SUB]], 0
+; CHECK-NEXT:    [[M1:%.*]] = select i1 [[CMP1]], i8 0, i8 [[SUB]]
+; CHECK-NEXT:    [[M2:%.*]] = select i1 [[CMP2]], i8 [[SUB]], i8 0
+; CHECK-NEXT:    [[R:%.*]] = sub nsw i8 [[M2]], [[M1]]
+; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sub = sub nsw i8 %a, %b
   %cmp1 = icmp slt i8 %a, %b