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

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.

Differential Revision: https://reviews.llvm.org/D60723

llvm-svn: 358523

1 files changed, 59 insertions, 2 deletions

diff --git a/llvm/lib/Transforms/Scalar/EarlyCSE.cpp b/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
index eb81ac6aafa..892a12315ce 100644
--- a/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
+++ b/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
@@ -130,6 +130,21 @@ template <> struct DenseMapInfo<SimpleValue> {
 
 } // 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.
@@ -171,6 +186,24 @@ unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
     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));
 
@@ -183,8 +216,7 @@ unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
                         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");
@@ -248,6 +280,31 @@ bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {
     }
   }
 
+  // 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;
 }