[EarlyCSE] Improve EarlyCSE of some absolute value cases.

[craig.topper]

Summary

Change matchSelectPattern to return X and -X for ABS/NABS in a well defined order. Adjust EarlyCSE to account for this. Ensure the SPF result is some kind of min/max and not abs/nabs in one place in InstCombine that made me nervous.

Prevously we returned the two operands of the compare part of the abs pattern. The RHS is always going to be a 0 or -1 constant. This isn't very meaning thing to return for any one. There's also some freedom in the abs pattern as to what happens when the value is equal to 0. This freedom led to early cse failing to match when different constants were used in otherwise equivalent operations. By returning the input and its negation in a defined order we can ensure an exact match. This also makes sure both patterns use the exact same subtract instruction for the negation. I believe CSE should evebntually make this happen and properly merge the nsw/nuw flags. But I'm not familiar with CSE and what order it does things in so it seemed like it might be good to really enforce that they were the same.

[spatel]

lib/Transforms/InstCombine/InstCombineSelect.cpp

941–942 ↗

(On Diff #147404)

Can you check that in as a preliminary cleanup? I think this patch should be just about EarlyCSE.

Ideally, we'd clean this up more - put the min/max predicate over the subsequent 3 transforms too and simplify that code (can FP min/max get in here?).

Even better would be to move these folds to instsimplify. We're not creating new values here.

[craig.topper]

lib/Transforms/InstCombine/InstCombineSelect.cpp

941–942 ↗

(On Diff #147404)

I don't see any reason FP min/max can't get here.

What simplification does the min/max check provide for the other 3 transforms?

[spatel]

lib/Transforms/InstCombine/InstCombineSelect.cpp

941–942 ↗

(On Diff #147404)

I might've been seeing something that isn't there. I was imagining if this block was pulled out as its own function, then you'd early exit if (!isMinOrMax), and that allows rearranging the subsequent checks into some shared form.

Do you know if the corresponding FP folds are done elsewhere, or are they missing, or does something prevent those?

[craig.topper]

Remove the InstCombine change.

[spatel]

lib/Analysis/ValueTracking.cpp

4577–4579

This new ABS/NABS behavior should be documented in the header comment.

lib/Transforms/Scalar/EarlyCSE.cpp

163–166

This is dead code unless we remove the ABS/NABS checks above here?

[craig.topper]

Update comment. Fix dead code.

[spatel]

LGTM.

include/llvm/Analysis/ValueTracking.h

struct SelectPatternResult {
     static bool isMinOrMax(SelectPatternFlavor SPF) {
       return SPF != SPF_UNKNOWN && SPF != SPF_ABS && SPF != SPF_NABS;
     }
   };
 
   /// Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind
   /// and providing the out parameter results if we successfully match.
   ///
+  /// For ABS/NABS, LHS will be set to the input to the abs idiom. RHS will be
+  /// the negation instruction from the idiom.
+  ///
   /// If CastOp is not nullptr, also match MIN/MAX idioms where the type does
   /// not match that of the original select. If this is the case, the cast
   /// operation (one of Trunc,SExt,Zext) that must be done to transform the
   /// type of LHS and RHS into the type of V is returned in CastOp.
   ///
   /// For example:
   ///   %1 = icmp slt i32 %a, i32 4
   ///   %2 = sext i32 %a to i64

lib/Analysis/ValueTracking.cpp

if (TrueVal == CmpLHS && FalseVal == CmpRHS) {
     case FCmpInst::FCMP_OLE: return {SPF_FMINNUM, NaNBehavior, Ordered};
     }
   }
 
   const APInt *C1;
   if (match(CmpRHS, m_APInt(C1))) {
     if ((CmpLHS == TrueVal && match(FalseVal, m_Neg(m_Specific(CmpLHS)))) ||
         (CmpLHS == FalseVal && match(TrueVal, m_Neg(m_Specific(CmpLHS))))) {
+      // Set RHS to the negate operand. LHS was assigned to CmpLHS earlier.
+      RHS = (CmpLHS == TrueVal) ? FalseVal : TrueVal;
 
       // ABS(X) ==> (X >s 0) ? X : -X and (X >s -1) ? X : -X
       // NABS(X) ==> (X >s 0) ? -X : X and (X >s -1) ? -X : X
       if (Pred == ICmpInst::ICMP_SGT &&
           (C1->isNullValue() || C1->isAllOnesValue())) {
         return {(CmpLHS == TrueVal) ? SPF_ABS : SPF_NABS, SPNB_NA, false};
       }
 
       // ABS(X) ==> (X <s 0) ? -X : X and (X <s 1) ? -X : X

lib/Transforms/Scalar/EarlyCSE.cpp

unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
   // Hash min/max/abs (cmp + select) to allow for commuted operands.
   // Min/max may also have 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 FP min/max.
   if (SPF == SPF_SMIN || SPF == SPF_SMAX ||
-      SPF == SPF_UMIN || SPF == SPF_UMAX ||
-      SPF == SPF_ABS || SPF == SPF_NABS) {
+      SPF == SPF_UMIN || SPF == SPF_UMAX) {
     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);
+  }
 
   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()));
 
bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {
   Value *LHSA, *LHSB;
   SelectPatternFlavor LSPF = matchSelectPattern(LHSI, LHSA, LHSB).Flavor;
   // TODO: We should also detect FP min/max.
   if (LSPF == SPF_SMIN || LSPF == SPF_SMAX ||
       LSPF == SPF_UMIN || LSPF == SPF_UMAX ||
       LSPF == SPF_ABS || LSPF == SPF_NABS) {
     Value *RHSA, *RHSB;
     SelectPatternFlavor RSPF = matchSelectPattern(RHSI, RHSA, RHSB).Flavor;
-    return (LSPF == RSPF && ((LHSA == RHSA && LHSB == RHSB) ||
-                             (LHSA == RHSB && LHSB == RHSA)));
+    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));
+    }
   }
 
   return false;
 }
 
 //===----------------------------------------------------------------------===//
 // CallValue
 //===----------------------------------------------------------------------===//

test/Transforms/EarlyCSE/commute.ll

;
   %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
 }
 
+; These two tests make sure we still consider it a match when the RHS of the
+; 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]]
+;
+  %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
+}
+
+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
+;
+  %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
+}
+