[EarlyCSE] recognize commuted and swapped variants of min/max as equivalent (PR35642)

[spatel]

Summary

As shown in:
https://bugs.llvm.org/show_bug.cgi?id=35642
...we can have different forms of min/max, so we should recognize those here in EarlyCSE similar to how we already handle binops and compares that can commute.

[hfinkel]

Could you use matchSelectPattern (from ValueTracking) here instead of matching the individual min/max patterns? That will also give us absolute value and the floating-point min/max as well. I think that you can hash_combine the fields of SelectPatternResult, and the logic might be simpler overall too (hopefully).

[spatel]

In D41136#953249, @hfinkel wrote:

Could you use matchSelectPattern (from ValueTracking) here instead of matching the individual min/max patterns? That will also give us absolute value and the floating-point min/max as well. I think that you can hash_combine the fields of SelectPatternResult, and the logic might be simpler overall too (hopefully).

Yes, that's better. I was purposely postponing FP in this patch because it's not clear to me what we need to handle in those cases (intrinsics and/or IR patterns). But either way, using value tracking should simplify the code here.

[spatel]

Patch updated:
Use ValueTracking's matchSelectPattern() rather than pattern matchers for min/max. This:

1. Makes the patch smaller
2. Catches more cases (extra test added)
3. Allows follow-up patches to enable abs() and FP min/max more easily

[hfinkel]

lib/Transforms/Scalar/EarlyCSE.cpp

151 ↗

(On Diff #126784)

Is there anything to do to address this TODO except for removing this check, the corresponding check below, and, to be good, adding a few test cases?

I don't want this artificially restricted, but I'm fine enabling the others in a follow-up commit (so that we can revert separately if necessary). This LGTM, but please do take care of the other cases in a follow-up commit, or add a comment explaining why that's non-trivial.

[spatel]

lib/Transforms/Scalar/EarlyCSE.cpp

151 ↗

(On Diff #126784)

For abs, it should just be fixing the check and adding tests. I need to look closer at which FP variants are commutable. But yes, I'll do both of those after this patch.

[hfinkel]

lib/Transforms/Scalar/EarlyCSE.cpp

151 ↗

(On Diff #126784)

I need to look closer at which FP variants are commutable. But yes, I'll do both of those after this patch.

Ah, I should have mentioned. I looked through the code before I made the suggestion. I think that you only need exclude SPF_UNKNOWN. It looks like all of the others commute because matchSelectPattern specifically excludes matching floating-point forms that don't commute (it specifically excludes cases where signed-zeros could cause problems, NaNs might cause problems, etc.).

[spatel]

lib/Transforms/Scalar/EarlyCSE.cpp

151 ↗

(On Diff #126784)

Great - I was coming to that conclusion too now that I'm reading the code. Just need to come up with N test cases (and probably a pile of negative tests too). :)

I think we will need to handle the 'num' intrinsics separately (but similarly):

define double @maxnum_intrinsic(double %x, double %y) {
  %m1 = call double @llvm.maxnum.f64(double %x, double %y)
  %m2 = call double @llvm.maxnum.f64(double %y, double %x)
  %r = fadd double %m1, %m2
  ret double %r
}

[hfinkel]

lib/Transforms/Scalar/EarlyCSE.cpp

151 ↗

(On Diff #126784)

Cool. Regarding [max|min]num, I agree.

[spatel]

On closer inspection, I think matchSelectPattern is either not sufficient or broken because it doesn't handle -0.0 as we would require here:

declare void @self_destruct_if_neg_zero(double)  
define double @fmin_any_ordered_commute(double %x, double %y) {
  %cmp1 = fcmp nnan olt double %x, %y                            ; if x=+0.0 and y=-0.0, returns false
  %cmp2 = fcmp nnan olt double %y, %x                            ; if x=+0.0 and y=-0.0, returns false
  %neg_zero_if_false = select i1 %cmp1, double %x, double %y     ; returns -0.0
  %pos_zero_if_false = select i1 %cmp2, double %y, double %x     ; returns +0.0
  call void @self_destruct_if_neg_zero(double %pos_zero_if_false)
  ret double %neg_zero_if_false
}

If we use what is returned by matchSelectPattern ( {SPF_FMINNUM, SPNB_RETURNS_ANY, false} ), we get:

$ ./opt -early-cse fminmax.ll -S

define double @fmin_any_ordered_commute(double %x, double %y) {
  %cmp1 = fcmp nnan olt double %x, %y
  %cmp2 = fcmp nnan olt double %y, %x
  %neg_zero_if_false = select i1 %cmp1, double %x, double %y
  call void @self_destruct_if_neg_zero(double %neg_zero_if_false)  ; boom!
  ret double %neg_zero_if_false
}

[hfinkel]

In D41136#955455, @spatel wrote:

On closer inspection, I think matchSelectPattern is either not sufficient or broken because it doesn't handle -0.0 as we would require here:

declare void @self_destruct_if_neg_zero(double)  
define double @fmin_any_ordered_commute(double %x, double %y) {
  %cmp1 = fcmp nnan olt double %x, %y                            ; if x=+0.0 and y=-0.0, returns false
  %cmp2 = fcmp nnan olt double %y, %x                            ; if x=+0.0 and y=-0.0, returns false
  %neg_zero_if_false = select i1 %cmp1, double %x, double %y     ; returns -0.0
  %pos_zero_if_false = select i1 %cmp2, double %y, double %x     ; returns +0.0
  call void @self_destruct_if_neg_zero(double %pos_zero_if_false)
  ret double %neg_zero_if_false
}

If we use what is returned by matchSelectPattern ( {SPF_FMINNUM, SPNB_RETURNS_ANY, false} ), we get:

$ ./opt -early-cse fminmax.ll -S

define double @fmin_any_ordered_commute(double %x, double %y) {
  %cmp1 = fcmp nnan olt double %x, %y
  %cmp2 = fcmp nnan olt double %y, %x
  %neg_zero_if_false = select i1 %cmp1, double %x, double %y
  call void @self_destruct_if_neg_zero(double %neg_zero_if_false)  ; boom!
  ret double %neg_zero_if_false
}

This seems inconsistent with the intent of matchSelectPattern, at least based on the comment:

// If the predicate is an "or-equal"  (FP) predicate, then signed zeroes may
// return inconsistent results between implementations.
//   (0.0 <= -0.0) ? 0.0 : -0.0 // Returns 0.0
//   minNum(0.0, -0.0)          // May return -0.0 or 0.0 (IEEE 754-2008 5.3.1)
// Therefore we behave conservatively and only proceed if at least one of the
// operands is known to not be zero, or if we don't care about signed zeroes.
switch (Pred) {
default: break;
case CmpInst::FCMP_OGE: case CmpInst::FCMP_OLE:
case CmpInst::FCMP_UGE: case CmpInst::FCMP_ULE:
  if (!FMF.noSignedZeros() && !isKnownNonZero(CmpLHS) &&
      !isKnownNonZero(CmpRHS))
    return {SPF_UNKNOWN, SPNB_NA, false};
}

It seems like there are cases missing here (e.g., this does not apply only to the GE/LE predicates)? Based on your example, it seems like we have the same problem with the GT/LT predicates.

[spatel]

In D41136#955627, @hfinkel wrote:

// If the predicate is an "or-equal"  (FP) predicate, then signed zeroes may
// return inconsistent results between implementations.
//   (0.0 <= -0.0) ? 0.0 : -0.0 // Returns 0.0
//   minNum(0.0, -0.0)          // May return -0.0 or 0.0 (IEEE 754-2008 5.3.1)
// Therefore we behave conservatively and only proceed if at least one of the
// operands is known to not be zero, or if we don't care about signed zeroes.
switch (Pred) {
default: break;
case CmpInst::FCMP_OGE: case CmpInst::FCMP_OLE:
case CmpInst::FCMP_UGE: case CmpInst::FCMP_ULE:
  if (!FMF.noSignedZeros() && !isKnownNonZero(CmpLHS) &&
      !isKnownNonZero(CmpRHS))
    return {SPF_UNKNOWN, SPNB_NA, false};
}

It seems like there are cases missing here (e.g., this does not apply only to the GE/LE predicates)? Based on your example, it seems like we have the same problem with the GT/LT predicates.

Yep - that's the quick fix; add the other preds. A better solution might be to distinguish signed zero behavior in the same way that we're doing for NAN. But let me try the easy patch first and see if anything breaks. :)

[spatel]

In D41136#955784, @spatel wrote:

It seems like there are cases missing here (e.g., this does not apply only to the GE/LE predicates)? Based on your example, it seems like we have the same problem with the GT/LT predicates.

Yep - that's the quick fix; add the other preds. A better solution might be to distinguish signed zero behavior in the same way that we're doing for NAN. But let me try the easy patch first and see if anything breaks. :)

Unfortunately, we would regress this test:

define i8 @t9(float %a) {
  %t1 = fcmp ult float %a, 0.0
  %t2 = fptosi float %a to i8
  %t3 = select i1 %t1, i8 %t2, i8 0
  ret i8 %t3
}

Currently, we recognize that as fmin with a cast and canonicalize to:

define i8 @t9(float %a) {
  %.inv = fcmp oge float %a, 0.0
  %t31 = select i1 %.inv, float 0.0, float %a
  %1 = fptosi float %t31 to i8
  ret i8 %1
}

We could set the 'nsz' bit that we're sending to the matcher to avoid the regression in the case of a min/max with cast.

llvm/trunk/lib/Transforms/Scalar/EarlyCSE.cpp

 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
if (CmpInst *CI = dyn_cast<CmpInst>(Inst)) {
     CmpInst::Predicate Pred = CI->getPredicate();
     if (Inst->getOperand(0) > Inst->getOperand(1)) {
       std::swap(LHS, RHS);
       Pred = CI->getSwappedPredicate();
     }
     return hash_combine(Inst->getOpcode(), Pred, LHS, RHS);
   }
 
+  // Hash min/max (cmp + select) to allow for commuted operands, non-canonical
+  // compare predicate (eg, the compare for smin may use 'sgt' rather than
+  // 'slt'), and non-canonical operands in the compare.
+  Value *A, *B;
+  SelectPatternFlavor SPF = matchSelectPattern(Inst, A, B).Flavor;
+  // TODO: We should also detect abs and FP min/max.
+  if (SPF == SPF_SMIN || SPF == SPF_SMAX ||
+      SPF == SPF_UMIN || SPF == SPF_UMAX) {
+    if (A > B)
+      std::swap(A, B);
+    return hash_combine(Inst->getOpcode(), SPF, A, B);
+  }
+
   if (CastInst *CI = dyn_cast<CastInst>(Inst))
     return hash_combine(CI->getOpcode(), CI->getType(), CI->getOperand(0));
 
   if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Inst))
     return hash_combine(EVI->getOpcode(), EVI->getOperand(0),
                         hash_combine_range(EVI->idx_begin(), EVI->idx_end()));
 
   if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Inst))
assert(isa<CmpInst>(RHSI) &&
            "same opcode, but different instruction type?");
     CmpInst *RHSCmp = cast<CmpInst>(RHSI);
     // Commuted equality
     return LHSCmp->getOperand(0) == RHSCmp->getOperand(1) &&
            LHSCmp->getOperand(1) == RHSCmp->getOperand(0) &&
            LHSCmp->getSwappedPredicate() == RHSCmp->getPredicate();
   }
 
+  // Min/max can occur with commuted operands, non-canonical predicates, and/or
+  // non-canonical operands.
+  Value *LHSA, *LHSB;
+  SelectPatternFlavor LSPF = matchSelectPattern(LHSI, LHSA, LHSB).Flavor;
+  // TODO: We should also detect abs and FP min/max.
+  if (LSPF == SPF_SMIN || LSPF == SPF_SMAX ||
+      LSPF == SPF_UMIN || LSPF == SPF_UMAX) {
+    Value *RHSA, *RHSB;
+    SelectPatternFlavor RSPF = matchSelectPattern(RHSI, RHSA, RHSB).Flavor;
+    return (LSPF == RSPF && ((LHSA == RHSA && LHSB == RHSB) ||
+                             (LHSA == RHSB && LHSB == RHSA)));
+  }
+
   return false;
 }
 
 //===----------------------------------------------------------------------===//
 // CallValue
 //===----------------------------------------------------------------------===//
 
 namespace {

llvm/trunk/test/Transforms/EarlyCSE/commute.ll

 
 ; Min/max operands may be commuted in the compare and select.
 
 define i8 @smin_commute(i8 %a, i8 %b) {
 ; CHECK-LABEL: @smin_commute(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i8 %a, %b
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i8 %b, %a
 ; CHECK-NEXT:    [[M1:%.*]] = select i1 [[CMP1]], i8 %a, i8 %b
-; CHECK-NEXT:    [[M2:%.*]] = select i1 [[CMP2]], i8 %b, i8 %a
-; CHECK-NEXT:    [[R:%.*]] = mul i8 [[M1]], [[M2]]
+; CHECK-NEXT:    [[R:%.*]] = mul i8 [[M1]], [[M1]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %cmp1 = icmp slt i8 %a, %b
   %cmp2 = icmp slt i8 %b, %a
   %m1 = select i1 %cmp1, i8 %a, i8 %b
   %m2 = select i1 %cmp2, i8 %b, i8 %a
   %r = mul i8 %m1, %m2
   ret i8 %r
 }
 
 ; Min/max can also have a swapped predicate and select operands.
 
 define i1 @smin_swapped(i8 %a, i8 %b) {
 ; CHECK-LABEL: @smin_swapped(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sgt i8 %a, %b
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i8 %a, %b
 ; CHECK-NEXT:    [[M1:%.*]] = select i1 [[CMP1]], i8 %b, i8 %a
-; CHECK-NEXT:    [[M2:%.*]] = select i1 [[CMP2]], i8 %a, i8 %b
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[M2]], [[M1]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 true
 ;
   %cmp1 = icmp sgt i8 %a, %b
   %cmp2 = icmp slt i8 %a, %b
   %m1 = select i1 %cmp1, i8 %b, i8 %a
   %m2 = select i1 %cmp2, i8 %a, i8 %b
   %r = icmp eq i8 %m2, %m1
   ret i1 %r
 }
 
 define i8 @smax_commute(i8 %a, i8 %b) {
 ; CHECK-LABEL: @smax_commute(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sgt i8 %a, %b
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i8 %b, %a
 ; CHECK-NEXT:    [[M1:%.*]] = select i1 [[CMP1]], i8 %a, i8 %b
-; CHECK-NEXT:    [[M2:%.*]] = select i1 [[CMP2]], i8 %b, i8 %a
-; CHECK-NEXT:    [[R:%.*]] = urem i8 [[M2]], [[M1]]
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 0
 ;
   %cmp1 = icmp sgt i8 %a, %b
   %cmp2 = icmp sgt i8 %b, %a
   %m1 = select i1 %cmp1, i8 %a, i8 %b
   %m2 = select i1 %cmp2, i8 %b, i8 %a
   %r = urem i8 %m2, %m1
   ret i8 %r
 }
 
 define i8 @smax_swapped(i8 %a, i8 %b) {
 ; CHECK-LABEL: @smax_swapped(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i8 %a, %b
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i8 %a, %b
 ; CHECK-NEXT:    [[M1:%.*]] = select i1 [[CMP1]], i8 %b, i8 %a
-; CHECK-NEXT:    [[M2:%.*]] = select i1 [[CMP2]], i8 %a, i8 %b
-; CHECK-NEXT:    [[R:%.*]] = sdiv i8 [[M1]], [[M2]]
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 1
 ;
   %cmp1 = icmp slt i8 %a, %b
   %cmp2 = icmp sgt i8 %a, %b
   %m1 = select i1 %cmp1, i8 %b, i8 %a
   %m2 = select i1 %cmp2, i8 %a, i8 %b
   %r = sdiv i8 %m1, %m2
   ret i8 %r
 }
 
 define i8 @umin_commute(i8 %a, i8 %b) {
 ; CHECK-LABEL: @umin_commute(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i8 %a, %b
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i8 %b, %a
 ; CHECK-NEXT:    [[M1:%.*]] = select i1 [[CMP1]], i8 %a, i8 %b
-; CHECK-NEXT:    [[M2:%.*]] = select i1 [[CMP2]], i8 %b, i8 %a
-; CHECK-NEXT:    [[R:%.*]] = sub i8 [[M2]], [[M1]]
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 0
 ;
   %cmp1 = icmp ult i8 %a, %b
   %cmp2 = icmp ult i8 %b, %a
   %m1 = select i1 %cmp1, i8 %a, i8 %b
   %m2 = select i1 %cmp2, i8 %b, i8 %a
   %r = sub i8 %m2, %m1
   ret i8 %r
 }
 
 ; Choose a vector type just to show that works.
 
 define <2 x i8> @umin_swapped(<2 x i8> %a, <2 x i8> %b) {
 ; CHECK-LABEL: @umin_swapped(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp ugt <2 x i8> %a, %b
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult <2 x i8> %a, %b
 ; CHECK-NEXT:    [[M1:%.*]] = select <2 x i1> [[CMP1]], <2 x i8> %b, <2 x i8> %a
-; CHECK-NEXT:    [[M2:%.*]] = select <2 x i1> [[CMP2]], <2 x i8> %a, <2 x i8> %b
-; CHECK-NEXT:    [[R:%.*]] = sub <2 x i8> [[M2]], [[M1]]
-; CHECK-NEXT:    ret <2 x i8> [[R]]
+; CHECK-NEXT:    ret <2 x i8> zeroinitializer
 ;
   %cmp1 = icmp ugt <2 x i8> %a, %b
   %cmp2 = icmp ult <2 x i8> %a, %b
   %m1 = select <2 x i1> %cmp1, <2 x i8> %b, <2 x i8> %a
   %m2 = select <2 x i1> %cmp2, <2 x i8> %a, <2 x i8> %b
   %r = sub <2 x i8> %m2, %m1
   ret <2 x i8> %r
 }
 
 define i8 @umax_commute(i8 %a, i8 %b) {
 ; CHECK-LABEL: @umax_commute(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp ugt i8 %a, %b
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ugt i8 %b, %a
 ; CHECK-NEXT:    [[M1:%.*]] = select i1 [[CMP1]], i8 %a, i8 %b
-; CHECK-NEXT:    [[M2:%.*]] = select i1 [[CMP2]], i8 %b, i8 %a
-; CHECK-NEXT:    [[R:%.*]] = udiv i8 [[M1]], [[M2]]
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 1
 ;
   %cmp1 = icmp ugt i8 %a, %b
   %cmp2 = icmp ugt i8 %b, %a
   %m1 = select i1 %cmp1, i8 %a, i8 %b
   %m2 = select i1 %cmp2, i8 %b, i8 %a
   %r = udiv i8 %m1, %m2
   ret i8 %r
 }
 
 define i8 @umax_swapped(i8 %a, i8 %b) {
 ; CHECK-LABEL: @umax_swapped(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i8 %a, %b
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ugt i8 %a, %b
 ; CHECK-NEXT:    [[M1:%.*]] = select i1 [[CMP1]], i8 %b, i8 %a
-; CHECK-NEXT:    [[M2:%.*]] = select i1 [[CMP2]], i8 %a, i8 %b
-; CHECK-NEXT:    [[R:%.*]] = add i8 [[M2]], [[M1]]
+; CHECK-NEXT:    [[R:%.*]] = add i8 [[M1]], [[M1]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %cmp1 = icmp ult i8 %a, %b
   %cmp2 = icmp ugt i8 %a, %b
   %m1 = select i1 %cmp1, i8 %b, i8 %a
   %m2 = select i1 %cmp2, i8 %a, i8 %b
   %r = add i8 %m2, %m1
   ret i8 %r
 }
 
+; Min/max may exist with non-canonical operands. Value tracking can match those.
+
+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
+;
+  %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
+}
+