[EarlyCSE] avoid crashing when detecting min/max/abs patterns (PR41083)

[spatel]

Summary

As discussed in PR41083:
https://bugs.llvm.org/show_bug.cgi?id=41083
...we can assert/crash in EarlyCSE using the current hashing scheme and instructions with flags.

ValueTracking's matchSelectPattern() may rely on overflow (nsw, etc) or other flags when detecting patterns such as min/max/abs composed of compare+select. But the value numbering / hashing mechanism used by EarlyCSE intersects those flags to allow more CSE.

Several alternatives to solve this are discussed in the bug report. This patch avoids the issue by doing simple matching of min/max/abs patterns that never requires instruction flags. We give up some CSE power because of that, but that is not expected to result in much actual performance difference because InstCombine will canonicalize these patterns when possible. It even has this comment for abs/nabs:

/// Canonicalize all these variants to 1 pattern.
/// This makes CSE more likely.

I left this code to use ValueTracking's "flavor" enum values, so we don't have to change the callers' code. If we decide to go back to using the ValueTracking call (by changing the hashing algorithm instead), it should be obvious how to replace this chunk.

[samparker]

llvm/test/Transforms/EarlyCSE/commute.ll

344

Probably worth adding a run line to run instcombine before earlycse to test this expectation?

[spatel]

Patch updated:
Add tests for -O1 to show that the standard pipelines (the combination of -instcombine and -early-cse) can reduce select patterns formed from different basic ops.

llvm/test/Transforms/EarlyCSE/commute.ll

344

Yes, good point. I prefer to make the tests part of "PhaseOrdering" though. That way we can easily test the standard optimization pipelines for each pass manager.

[efriedma]

LGTM. Thanks for looking into this.

[spatel]

Patch updated:
The phase ordering test results were wrong in the earlier rev - I must have used a stale binary to generate the CHECK lines.
I fixed a bug in instcombine that was hindering the abs/nabs tests with:
rG62ce7e650a5a

There's another bug for min/max, but I don't see a one-liner fix, so I've marked that test with a FIXME note after pushing
the baseline testing with:
rG0ad6e726ec7e

[JosephTremoulet]

LGTM, thanks.

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

static bool matchSelectWithOptionalNotCond(Value *V, Value *&Cond, Value *&A,
 
   // Look through a 'not' of the condition operand by swapping A/B.
   Value *CondNot;
   if (match(Cond, m_Not(m_Value(CondNot)))) {
     Cond = CondNot;
     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
+  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;
 }
 
 static unsigned getHashValueImpl(SimpleValue Val) {
   Instruction *Inst = Val.Inst;
   // Hash in all of the operands as pointers.
   if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst)) {

llvm/test/Transforms/EarlyCSE/commute.ll

;
   %cmp2 = xor i1 %cmp1, -1
   %m1 = select i1 %cmp1, i8 %a, i8 %b
   %m2 = select i1 %cmp2, i8 %b, i8 %a
   %r = icmp eq i8 %m1, %m2
   ret i1 %r
 }
 
 ; 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(
 ; 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:    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
   %cmp2 = icmp sgt i8 %sub, 0
   %m1 = select i1 %cmp1, i8 0, i8 %sub
   %m2 = select i1 %cmp2, i8 %sub, i8 0
   %r = sub i8 %m2, %m1
   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
   %cmp2 = icmp slt i8 %a, 0
   %m1 = select i1 %cmp1, i8 %a, i8 %neg
   %m2 = select i1 %cmp2, i8 %neg, i8 %a
   %r = or i8 %m2, %m1
   ret i8 %r
;
   %cmp1 = icmp sgt i8 %a, 0
   %cmp2 = xor i1 %cmp1, -1
   %m1 = select i1 %cmp1, i8 %a, i8 %neg
   %m2 = select i1 %cmp2, i8 %neg, i8 %a
   %r = or i8 %m2, %m1
   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
   %cmp2 = icmp sgt i8 %a, 0
   %m1 = select i1 %cmp1, i8 %a, i8 %neg
   %m2 = select i1 %cmp2, i8 %neg, i8 %a
   %r = xor i8 %m2, %m1
   ret i8 %r
;
   %cmp1 = icmp slt i8 %a, 0
   %cmp2 = xor i1 %cmp1, -1
   %m1 = select i1 %cmp1, i8 %a, i8 %neg
   %m2 = select i1 %cmp2, i8 %neg, i8 %a
   %r = xor i8 %m2, %m1
   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(
 ; CHECK-NEXT:    [[NEG:%.*]] = sub i8 0, [[A:%.*]]
 ; 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
   %cmp2 = icmp slt i8 %a, 0
   %m1 = select i1 %cmp1, i8 %a, i8 %neg
   %m2 = select i1 %cmp2, i8 %neg, i8 %a
   %r = or i8 %m2, %m1
   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
   %cmp2 = icmp sgt i8 %a, -1
   %m1 = select i1 %cmp1, i8 %a, i8 %neg
   %m2 = select i1 %cmp2, i8 %neg, i8 %a
   %r = xor i8 %m2, %m1
   ret i8 %r
;
   %rb = select i1 %cmpb, i32 %y, i32 %x
   %rc = select i1 %cmpc, i32 %x, i32 %y
   store volatile i32 %ra, i32* %pout
   store volatile i32 %rb, i32* %pout
   store volatile i32 %rc, i32* %pout
 
   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
+}

llvm/test/Transforms/PhaseOrdering/min-max-abs-cse.ll

 ; 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
   %cmp2 = icmp sgt i8 %sub, 0
   %m1 = select i1 %cmp1, i8 0, i8 %sub
   %m2 = select i1 %cmp2, i8 %sub, i8 0
   %r = sub i8 %m2, %m1
   ret i8 %r