[EarlyCSE] detect equivalence of selects with inverse conditions and commuted operands (PR41101)

[spatel]

Summary

This is 1 of the problems discussed in the post-commit thread for:
rL355741 / http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20190311/635516.html
and filed as:
https://bugs.llvm.org/show_bug.cgi?id=41101

Instcombine tries to canonicalize some of these cases (and there's room for improvement there independently of this patch), but it can't always do that because of extra uses. So we need to recognize these commuted operand patterns here in EarlyCSE. This is similar to how we detect commuted compares and commuted min/max/abs.

The 2 patterns (inverted pred and 'not' cond) are independent, so I can commit those separately if this looks ok.

[spatel]

https://rise4fun.com/Alive/NJl

Name: Inverted predicate
%cond = icmp sgt i8 %x, 42
%invcond = icmp sle i8 %x, 42
%m1 = select i1 %cond, i32 %t, i32 %f
%m2 = select i1 %invcond, i32 %f, i32 %t
%r = xor i32 %m1, %m2
=>
%r = i32 0

Name: 'not' predicate
%invcond = xor i1 %cond, -1
%m1 = select i1 %cond, i32 %t, i32 %f
%m2 = select i1 %invcond, i32 %f, i32 %t
%r = xor i32 %m1, %m2
=>
%r = i32 0

[nikic]

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

185 ↗

(On Diff #195212)

Shouldn't the cmp operands be hashed as well?

[spatel]

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

185 ↗

(On Diff #195212)

Good question. IIUC, this is not logically wrong, but using the cmp operands would improve the hashing (reduce chances of collision). Does that sound right?

[nikic]

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

185 ↗

(On Diff #195212)

That would be my understanding as well.

195 ↗

(On Diff #195212)

I think this check should be moved above the cmp handling: You can have a select(not(cmp(pred x, y)), t, f) where canonicalization is prevented both on the select and the not due to multiple uses. In this case we'd presumably still want to treat it exactly the same way as a select(cmp(pred x, y), f, t), including the predicate canonicalization above.

[spatel]

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

195 ↗

(On Diff #195212)

That seems like a good enhancement, but now I definitely will want to split things up when committing because we will have 3 independent changes in this review.

[spatel]

Patch updated:

1. Improve hashing as suggested (I don't know how to expose that in a test, so no extra tests for that).
2. Add a "double-negation" matcher to recognize selects with same true/false ops but different conditions (positive and negative tests added).

[nikic]

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

311 ↗

(On Diff #195255)

This *looks* correct to me, but it seems like some pretty tricky code where it's easy to miss something. I'd suggest to add a helper to get rid of the not (which can be used both in the hashing and comparison code):

static bool matchSelect(Value *V, Value *&Cond, Value *&T, Value *&F) {
  if (match(V, m_Select(m_Value(Cond), m_Value(T), m_Value(F)))) {
    Value *CondNot;
    if (match(Cond, m_Not(m_Value(CondNot)))) {
      Cond = CondNot;
      std::swap(T, F);
    }
    return true;
  }
  return false;
}

And then only leave the handling of the comparison here:

Value *CondL, *CondR, *TL, *TR, *FL, *FR;
if (matchSelect(LHSI, CondL, TL, FL) && matchSelect(RHSI, CondR, TR, FR)) {
  if (TL == TR && FL == FR)
    return CondL == CondR;

  if (TL == FR && FL == TR) {
    CmpInst::Predicate PredL, PredR;
    Value *X, *Y;
    if (match(CondL, m_Cmp(PredL, m_Value(X), m_Value(Y))) &&
        match(CondR, m_Cmp(PredR, m_Specific(X), m_Specific(Y))) &&
        CmpInst::getInversePredicate(PredL) == PredR)
      return true;
  }
}

I think that would go a way towards making this more "obviously correct".

[spatel]

Patch updated:
Redo equivalency matching to reduce code.

[nikic]

LGTM

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

279 ↗

(On Diff #195398)

I'd still suggest to move this into a static function and use it in the hashing code as well. (But as-is is also fine.)

[spatel]

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

279 ↗

(On Diff #195398)

Yes, good point. I missed the symmetry.

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

template <> struct DenseMapInfo<SimpleValue> {
   }
 
   static unsigned getHashValue(SimpleValue Val);
   static bool isEqual(SimpleValue LHS, SimpleValue RHS);
 };
 
 } // end namespace llvm
 
+/// Match a 'select' including an optional 'not' of the condition.
+static bool matchSelectWithOptionalNotCond(Value *V, Value *&Cond,
+                                           Value *&T, Value *&F) {
+  if (match(V, m_Select(m_Value(Cond), m_Value(T), m_Value(F)))) {
+    // Look through a 'not' of the condition operand by swapping true/false.
+    Value *CondNot;
+    if (match(Cond, m_Not(m_Value(CondNot)))) {
+      Cond = CondNot;
+      std::swap(T, F);
+    }
+    return true;
+  }
+  return false;
+}
+
 unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
   Instruction *Inst = Val.Inst;
   // Hash in all of the operands as pointers.
   if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst)) {
     Value *LHS = BinOp->getOperand(0);
     Value *RHS = BinOp->getOperand(1);
     if (BinOp->isCommutative() && BinOp->getOperand(0) > BinOp->getOperand(1))
       std::swap(LHS, RHS);
if (A > B)
       std::swap(A, B);
     return hash_combine(Inst->getOpcode(), SPF, A, B);
   }
   if (SPF == SPF_ABS || SPF == SPF_NABS) {
     // ABS/NABS always puts the input in A and its negation in B.
     return hash_combine(Inst->getOpcode(), SPF, A, B);
   }
 
+  // Hash general selects to allow matching commuted true/false operands.
+  Value *Cond, *TVal, *FVal;
+  if (matchSelectWithOptionalNotCond(Inst, Cond, TVal, FVal)) {
+    // If we do not have a compare as the condition, just hash in the condition.
+    CmpInst::Predicate Pred;
+    Value *X, *Y;
+    if (!match(Cond, m_Cmp(Pred, m_Value(X), m_Value(Y))))
+      return hash_combine(Inst->getOpcode(), Cond, TVal, FVal);
+
+    // Similar to cmp normalization (above) - canonicalize the predicate value:
+    // select (icmp Pred, X, Y), T, F --> select (icmp InvPred, X, Y), F, T
+    if (CmpInst::getInversePredicate(Pred) < Pred) {
+      Pred = CmpInst::getInversePredicate(Pred);
+      std::swap(TVal, FVal);
+    }
+    return hash_combine(Inst->getOpcode(), Pred, X, Y, TVal, FVal);
+  }
+
   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))
     return hash_combine(IVI->getOpcode(), IVI->getOperand(0),
                         IVI->getOperand(1),
                         hash_combine_range(IVI->idx_begin(), IVI->idx_end()));
 
-  assert((isa<CallInst>(Inst) || isa<BinaryOperator>(Inst) ||
-          isa<GetElementPtrInst>(Inst) || isa<SelectInst>(Inst) ||
+  assert((isa<CallInst>(Inst) || isa<GetElementPtrInst>(Inst) ||
           isa<ExtractElementInst>(Inst) || isa<InsertElementInst>(Inst) ||
           isa<ShuffleVectorInst>(Inst)) &&
          "Invalid/unknown instruction");
 
   // Mix in the opcode.
   return hash_combine(
       Inst->getOpcode(),
       hash_combine_range(Inst->value_op_begin(), Inst->value_op_end()));
if (LSPF == RSPF) {
       // Abs results are placed in a defined order by matchSelectPattern.
       if (LSPF == SPF_ABS || LSPF == SPF_NABS)
         return LHSA == RHSA && LHSB == RHSB;
       return ((LHSA == RHSA && LHSB == RHSB) ||
               (LHSA == RHSB && LHSB == RHSA));
     }
   }
 
+  // Selects can be non-trivially equivalent via inverted conditions and swaps.
+  Value *CondL, *CondR, *TrueL, *TrueR, *FalseL, *FalseR;
+  if (matchSelectWithOptionalNotCond(LHSI, CondL, TrueL, FalseL) &&
+      matchSelectWithOptionalNotCond(RHSI, CondR, TrueR, FalseR)) {
+    // select Cond, T, F <--> select not(Cond), F, T
+    if (CondL == CondR && TrueL == TrueR && FalseL == FalseR)
+      return true;
+
+    // If the true/false operands are swapped and the conditions are compares
+    // with inverted predicates, the selects are equal:
+    // select (icmp Pred, X, Y), T, F <--> select (icmp InvPred, X, Y), F, T
+    //
+    // This also handles patterns with a double-negation because we looked
+    // through a 'not' in the matching function and swapped T/F:
+    // select (cmp Pred, X, Y), T, F <--> select (not (cmp InvPred, X, Y)), T, F
+    if (TrueL == FalseR && FalseL == TrueR) {
+      CmpInst::Predicate PredL, PredR;
+      Value *X, *Y;
+      if (match(CondL, m_Cmp(PredL, m_Value(X), m_Value(Y))) &&
+          match(CondR, m_Cmp(PredR, m_Specific(X), m_Specific(Y))) &&
+          CmpInst::getInversePredicate(PredL) == PredR)
+        return true;
+    }
+  }
+
   return false;
 }
 
 //===----------------------------------------------------------------------===//
 // CallValue
 //===----------------------------------------------------------------------===//
 
 namespace {

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

;
   %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
 }
 
 ; https://bugs.llvm.org/show_bug.cgi?id=41101
-; TODO: Detect equivalence of selects with commuted operands: 'not' cond.
+; Detect equivalence of selects with commuted operands: 'not' cond.
 
 define i32 @select_not_cond(i1 %cond, i32 %t, i32 %f) {
 ; CHECK-LABEL: @select_not_cond(
 ; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[COND:%.*]], true
 ; CHECK-NEXT:    [[M1:%.*]] = select i1 [[COND]], i32 [[T:%.*]], i32 [[F:%.*]]
-; CHECK-NEXT:    [[M2:%.*]] = select i1 [[NOT]], i32 [[F]], i32 [[T]]
-; CHECK-NEXT:    [[R:%.*]] = xor i32 [[M2]], [[M1]]
-; CHECK-NEXT:    ret i32 [[R]]
+; CHECK-NEXT:    ret i32 0
 ;
   %not = xor i1 %cond, -1
   %m1 = select i1 %cond, i32 %t, i32 %f
   %m2 = select i1 %not, i32 %f, i32 %t
   %r = xor i32 %m2, %m1
   ret i32 %r
 }
 
-; TODO: Detect equivalence of selects with commuted operands: 'not' cond with vector select.
+; Detect equivalence of selects with commuted operands: 'not' cond with vector select.
 
 define <2 x double> @select_not_cond_commute_vec(<2 x i1> %cond, <2 x double> %t, <2 x double> %f) {
 ; CHECK-LABEL: @select_not_cond_commute_vec(
 ; CHECK-NEXT:    [[NOT:%.*]] = xor <2 x i1> [[COND:%.*]], <i1 true, i1 true>
 ; CHECK-NEXT:    [[M1:%.*]] = select <2 x i1> [[COND]], <2 x double> [[T:%.*]], <2 x double> [[F:%.*]]
-; CHECK-NEXT:    [[M2:%.*]] = select <2 x i1> [[NOT]], <2 x double> [[F]], <2 x double> [[T]]
-; CHECK-NEXT:    [[R:%.*]] = fdiv nnan <2 x double> [[M1]], [[M2]]
-; CHECK-NEXT:    ret <2 x double> [[R]]
+; CHECK-NEXT:    ret <2 x double> <double 1.000000e+00, double 1.000000e+00>
 ;
   %not = xor <2 x i1> %cond, <i1 -1, i1 -1>
   %m1 = select <2 x i1> %cond, <2 x double> %t, <2 x double> %f
   %m2 = select <2 x i1> %not, <2 x double> %f, <2 x double> %t
   %r = fdiv nnan <2 x double> %m1, %m2
   ret <2 x double> %r
 }
 

 ;
   %not = xor i1 %cond, -2
   %m1 = select i1 %cond, i32 %t, i32 %f
   %m2 = select i1 %not, i32 %f, i32 %t
   %r = xor i32 %m2, %m1
   ret i32 %r
 }
 
-; TODO: Detect equivalence of selects with commuted operands: inverted pred with fcmps.
+; Detect equivalence of selects with commuted operands: inverted pred with fcmps.
 
 define i32 @select_invert_pred_cond(float %x, i32 %t, i32 %f) {
 ; CHECK-LABEL: @select_invert_pred_cond(
 ; CHECK-NEXT:    [[COND:%.*]] = fcmp ueq float [[X:%.*]], 4.200000e+01
 ; CHECK-NEXT:    [[INVCOND:%.*]] = fcmp one float [[X]], 4.200000e+01
 ; CHECK-NEXT:    [[M1:%.*]] = select i1 [[COND]], i32 [[T:%.*]], i32 [[F:%.*]]
-; CHECK-NEXT:    [[M2:%.*]] = select i1 [[INVCOND]], i32 [[F]], i32 [[T]]
-; CHECK-NEXT:    [[R:%.*]] = xor i32 [[M2]], [[M1]]
-; CHECK-NEXT:    ret i32 [[R]]
+; CHECK-NEXT:    ret i32 0
 ;
   %cond = fcmp ueq float %x, 42.0
   %invcond = fcmp one float %x, 42.0
   %m1 = select i1 %cond, i32 %t, i32 %f
   %m2 = select i1 %invcond, i32 %f, i32 %t
   %r = xor i32 %m2, %m1
   ret i32 %r
 }
 
-; TODO: Detect equivalence of selects with commuted operands: inverted pred with icmps and vectors.
+; Detect equivalence of selects with commuted operands: inverted pred with icmps and vectors.
 
 define <2 x i32> @select_invert_pred_cond_commute_vec(<2 x i8> %x, <2 x i32> %t, <2 x i32> %f) {
 ; CHECK-LABEL: @select_invert_pred_cond_commute_vec(
 ; CHECK-NEXT:    [[COND:%.*]] = icmp sgt <2 x i8> [[X:%.*]], <i8 42, i8 -1>
 ; CHECK-NEXT:    [[INVCOND:%.*]] = icmp sle <2 x i8> [[X]], <i8 42, i8 -1>
 ; CHECK-NEXT:    [[M1:%.*]] = select <2 x i1> [[COND]], <2 x i32> [[T:%.*]], <2 x i32> [[F:%.*]]
-; CHECK-NEXT:    [[M2:%.*]] = select <2 x i1> [[INVCOND]], <2 x i32> [[F]], <2 x i32> [[T]]
-; CHECK-NEXT:    [[R:%.*]] = xor <2 x i32> [[M1]], [[M2]]
-; CHECK-NEXT:    ret <2 x i32> [[R]]
+; CHECK-NEXT:    ret <2 x i32> zeroinitializer
 ;
   %cond = icmp sgt <2 x i8> %x, <i8 42, i8 -1>
   %invcond = icmp sle <2 x i8> %x, <i8 42, i8 -1>
   %m1 = select <2 x i1> %cond, <2 x i32> %t, <2 x i32> %f
   %m2 = select <2 x i1> %invcond, <2 x i32> %f, <2 x i32> %t
   %r = xor <2 x i32> %m1, %m2
   ret <2 x i32> %r
 }
;
   %cond = fcmp ueq float %x, 42.0
   %invcond = fcmp one float %x, 43.0
   %m1 = select i1 %cond, i32 %t, i32 %f
   %m2 = select i1 %invcond, i32 %f, i32 %t
   %r = xor i32 %m2, %m1
   ret i32 %r
 }
 
-; TODO: If we have both an inverted predicate and a 'not' op, recognize the double-negation.
+; If we have both an inverted predicate and a 'not' op, recognize the double-negation.
 
 define i32 @select_not_invert_pred_cond(i8 %x, i32 %t, i32 %f) {
 ; CHECK-LABEL: @select_not_invert_pred_cond(
 ; CHECK-NEXT:    [[COND:%.*]] = icmp ugt i8 [[X:%.*]], 42
 ; CHECK-NEXT:    [[INVCOND:%.*]] = icmp ule i8 [[X]], 42
 ; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[INVCOND]], true
 ; CHECK-NEXT:    [[M1:%.*]] = select i1 [[COND]], i32 [[T:%.*]], i32 [[F:%.*]]
-; CHECK-NEXT:    [[M2:%.*]] = select i1 [[NOT]], i32 [[T]], i32 [[F]]
-; CHECK-NEXT:    [[R:%.*]] = sub i32 [[M1]], [[M2]]
-; CHECK-NEXT:    ret i32 [[R]]
+; CHECK-NEXT:    ret i32 0
 ;
   %cond = icmp ugt i8 %x, 42
   %invcond = icmp ule i8 %x, 42
   %not = xor i1 %invcond, -1
   %m1 = select i1 %cond, i32 %t, i32 %f
   %m2 = select i1 %not, i32 %t, i32 %f
   %r = sub i32 %m1, %m2
   ret i32 %r
 }
 
-; TODO: If we have both an inverted predicate and a 'not' op, recognize the double-negation.
+; If we have both an inverted predicate and a 'not' op, recognize the double-negation.
 
 define i32 @select_not_invert_pred_cond_commute(i8 %x, i8 %y, i32 %t, i32 %f) {
 ; CHECK-LABEL: @select_not_invert_pred_cond_commute(
 ; CHECK-NEXT:    [[INVCOND:%.*]] = icmp ule i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[INVCOND]], true
 ; CHECK-NEXT:    [[M2:%.*]] = select i1 [[NOT]], i32 [[T:%.*]], i32 [[F:%.*]]
 ; CHECK-NEXT:    [[COND:%.*]] = icmp ugt i8 [[X]], [[Y]]
-; CHECK-NEXT:    [[M1:%.*]] = select i1 [[COND]], i32 [[T]], i32 [[F]]
-; CHECK-NEXT:    [[R:%.*]] = sub i32 [[M2]], [[M1]]
-; CHECK-NEXT:    ret i32 [[R]]
+; CHECK-NEXT:    ret i32 0
 ;
   %invcond = icmp ule i8 %x, %y
   %not = xor i1 %invcond, -1
   %m2 = select i1 %not, i32 %t, i32 %f
   %cond = icmp ugt i8 %x, %y
   %m1 = select i1 %cond, i32 %t, i32 %f
   %r = sub i32 %m2, %m1
   ret i32 %r