[EarlyCSE] make abs recognization not depend on instcombine abs canonicalize

[shchenz]

Summary

EarlyCSE pass runs very early at the pipeline of opt binary, before inst combine pass.

For now EarlyCSE pass only recognizes the abs pattern after the canonicalize of abs in instcombine pass. This will make EarlyCSE miss some opportunities.

Also only recognizing some abs pattern will make equal instructions have different hash value. For example, see https://bugs.llvm.org/show_bug.cgi?id=48058

  %neg = sub i8 0, %a
  %cmp1 = icmp slt i8 %a, 0
  %cmp2 = icmp sge 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
`

%m1 and %m2 are recognized as same instructions in isEqualImpl because of inverse predicate and same operands for these two select.

But in getHashValueImpl, %m1 is recognized as NABS because it is already in canonicalize form of abs. But %m2 is not in canonicalize form of abs, so it is not recognized as NABS.

[spatel]

The medium-term solution (hopefully not too far away now) is to canonicalize to intrinsics - D87188. Once we get D90554 in, we can try that canonicalization again.

So I'm not sure that we want to add to the complexity of early-cse to handle this right now. What if we just delete the code that matches to SPF_ABS / SPF_NABS. I'm not seeing any regression test failures with that, and it avoids the bug?

[shchenz]

In D90734#2381468, @spatel wrote:

The medium-term solution (hopefully not too far away now) is to canonicalize to intrinsics - D87188. Once we get D90554 in, we can try that canonicalization again.

So I'm not sure that we want to add to the complexity of early-cse to handle this right now. What if we just delete the code that matches to SPF_ABS / SPF_NABS. I'm not seeing any regression test failures with that, and it avoids the bug?

Thanks for your comments. I am fine to delete the SPF_ABS/SPF_NABS related codes in earlycse pass. In current opt pipeline, passes between the first earlycse and the first instcombine should not be sensitive to earlycse's result or will be rerun after instcombine? Please let me know if you need me to delete them.

[spatel]

In D90734#2382164, @shchenz wrote:

In D90734#2381468, @spatel wrote:

The medium-term solution (hopefully not too far away now) is to canonicalize to intrinsics - D87188. Once we get D90554 in, we can try that canonicalization again.

So I'm not sure that we want to add to the complexity of early-cse to handle this right now. What if we just delete the code that matches to SPF_ABS / SPF_NABS. I'm not seeing any regression test failures with that, and it avoids the bug?

Thanks for your comments. I am fine to delete the SPF_ABS/SPF_NABS related codes in earlycse pass. In current opt pipeline, passes between the first earlycse and the first instcombine should not be sensitive to earlycse's result or will be rerun after instcombine? Please let me know if you need me to delete them.

We run earlycse at least once after instcombine in the typical optimization pipeline, so I don't think there is much chance for regression.

Can you update this patch to remove the SPF_ABS/SPF_NABS block and keep the new test to verify that we are not failing the hash matching?

[shchenz]

fix according to comments:
1: delete abs handling in earlycse pass.

[shchenz]

@spatel updated. I guess we need to add abs handling later in earlycse pass after D87188 is committed?

[spatel]

In D90734#2384460, @shchenz wrote:

@spatel updated. I guess we need to add abs handling later in earlycse pass after D87188 is committed?

I am not seeing what we would need to do with this pass - if we canonicalize to the intrinsic form, then CSE just becomes a simple match of the intrinsic arguments.
Do you have an example of something that would fail to optimize or hash properly?

[shchenz]

I am thinking llvm.abs(A) and llvm.abs(-A) can not be optimized in current earlyCSE phase? There are logics for commutative intrinsics and intrinsics with same operands in EarlyCSE pass. Am I missing something?

[shchenz]

In D90734#2385565, @shchenz wrote:

I am thinking llvm.abs(A) and llvm.abs(-A) can not be optimized in current earlyCSE phase? There are logics for commutative intrinsics and intrinsics with same operands in EarlyCSE pass. Am I missing something?

Ah, I know your ideas ^-^. Instcombine should canonicalize llvm.abs(-A) to llvm.abs(A). So after instcombine, in earlycse, we will not see llvm.abs(-A) right? I don't have other concerns. Thanks.

[spatel]

In D90734#2385581, @shchenz wrote:

In D90734#2385565, @shchenz wrote:

I am thinking llvm.abs(A) and llvm.abs(-A) can not be optimized in current earlyCSE phase? There are logics for commutative intrinsics and intrinsics with same operands in EarlyCSE pass. Am I missing something?

Ah, I know your ideas ^-^. Instcombine should canonicalize llvm.abs(-A) to llvm.abs(A). So after instcombine, in earlycse, we will not see llvm.abs(-A) right? I don't have other concerns. Thanks.

Right - I do not think we should put any extra pattern matching logic into this pass unless it is very simple. Everything else is dangerous - as this bug/patch (and a few before it) have already shown. :)
LGTM.

[shchenz]

In D90734#2385582, @spatel wrote:

In D90734#2385581, @shchenz wrote:

In D90734#2385565, @shchenz wrote:

I am thinking llvm.abs(A) and llvm.abs(-A) can not be optimized in current earlyCSE phase? There are logics for commutative intrinsics and intrinsics with same operands in EarlyCSE pass. Am I missing something?

Ah, I know your ideas ^-^. Instcombine should canonicalize llvm.abs(-A) to llvm.abs(A). So after instcombine, in earlycse, we will not see llvm.abs(-A) right? I don't have other concerns. Thanks.

Right - I do not think we should put any extra pattern matching logic into this pass unless it is very simple. Everything else is dangerous - as this bug/patch (and a few before it) have already shown. :)
LGTM.

Thank you!

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);
   }
 
-  // Match canonical forms of abs/nabs/min/max. We are not using ValueTracking's
+  // Match canonical forms of 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
   Flavor = SPF_UNKNOWN;
   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);
if (CmpInst *CI = dyn_cast<CmpInst>(Inst)) {
     }
     return hash_combine(Inst->getOpcode(), Pred, LHS, RHS);
   }
 
   // Hash general selects to allow matching commuted true/false operands.
   SelectPatternFlavor SPF;
   Value *Cond, *A, *B;
   if (matchSelectWithOptionalNotCond(Inst, Cond, A, B, SPF)) {
-    // Hash min/max/abs (cmp + select) to allow for commuted operands.
+    // Hash min/max (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.
     // TODO: We should also detect 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 (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.
 
     // 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, A, B);
static bool isEqualImpl(SimpleValue LHS, SimpleValue RHS) {
   auto *LII = dyn_cast<IntrinsicInst>(LHSI);
   auto *RII = dyn_cast<IntrinsicInst>(RHSI);
   if (LII && RII && LII->getIntrinsicID() == RII->getIntrinsicID() &&
       LII->isCommutative() && LII->getNumArgOperands() == 2) {
     return LII->getArgOperand(0) == RII->getArgOperand(1) &&
            LII->getArgOperand(1) == RII->getArgOperand(0);
   }
 
-  // Min/max/abs can occur with commuted operands, non-canonical predicates,
+  // Min/max can occur with commuted operands, non-canonical predicates,
   // and/or non-canonical operands.
   // Selects can be non-trivially equivalent via inverted conditions and swaps.
   SelectPatternFlavor LSPF, RSPF;
   Value *CondL, *CondR, *LHSA, *RHSA, *LHSB, *RHSB;
   if (matchSelectWithOptionalNotCond(LHSI, CondL, LHSA, LHSB, LSPF) &&
       matchSelectWithOptionalNotCond(RHSI, CondR, RHSA, RHSB, RSPF)) {
     if (LSPF == RSPF) {
       // TODO: We should also detect FP min/max.
       if (LSPF == SPF_SMIN || LSPF == SPF_SMAX ||
           LSPF == SPF_UMIN || LSPF == SPF_UMAX)
         return ((LHSA == RHSA && LHSB == RHSB) ||
                 (LHSA == RHSB && LHSB == RHSA));
 
-      if (LSPF == SPF_ABS || LSPF == SPF_NABS) {
-        // Abs results are placed in a defined order by matchSelectPattern.
-        return LHSA == RHSA && LHSB == RHSB;
-      }
-
       // select Cond, A, B <--> select not(Cond), B, A
       if (CondL == CondR && LHSA == RHSA && LHSB == RHSB)
         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), A, B <--> select (icmp InvPred, X, Y), B, A
     //
     // This also handles patterns with a double-negation in the sense of not +
     // inverse, because we looked through a 'not' in the matching function and
     // swapped A/B:
     // select (cmp Pred, X, Y), A, B <--> select (not (cmp InvPred, X, Y)), B, A
     //
     // This intentionally does NOT handle patterns with a double-negation in
     // the sense of not + not, because doing so could result in values
     // comparing
-    // as equal that hash differently in the min/max/abs cases like:
+    // as equal that hash differently in the min/max cases like:
     // select (cmp slt, X, Y), X, Y <--> select (not (not (cmp slt, X, Y))), X, Y
     //   ^ hashes as min                  ^ would not hash as min
     // In the context of the EarlyCSE pass, however, such cases never reach
     // this code, as we simplify the double-negation before hashing the second
     // select (and so still succeed at CSEing them).
     if (LHSA == RHSB && LHSB == RHSA) {
       CmpInst::Predicate PredL, PredR;
       Value *X, *Y;

llvm/test/Transforms/EarlyCSE/commute.ll

;
   %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
 }
 
+
+define i8 @abs_swapped_sge(i8 %a) {
+; CHECK-LABEL: @abs_swapped_sge(
+; CHECK-NEXT:    [[NEG:%.*]] = sub i8 0, [[A:%.*]]
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp sge 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 0
+;
+  %neg = sub i8 0, %a
+  %cmp1 = icmp sge 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 = xor i8 %m2, %m1
+  ret i8 %r
+}
+
+define i8 @nabs_swapped_sge(i8 %a) {
+; CHECK-LABEL: @nabs_swapped_sge(
+; CHECK-NEXT:    [[NEG:%.*]] = sub i8 0, [[A:%.*]]
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i8 [[A]], 0
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sge i8 [[A]], 0
+; 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 sge 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
+}
+
 ; 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

 ; values, and we run this test with -earlycse-debug-hash which would catch
 ; the disagreement and fail if it regressed.
 ; EarlyCSE should be able to detect the 2nd redundant `select` and eliminate
 ; it.
 define i32 @inverted_max(i32 %i) {
 ; CHECK-LABEL: @inverted_max(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sle i32 0, [[I:%.*]]
 ; CHECK-NEXT:    [[M1:%.*]] = select i1 [[CMP]], i32 [[I]], i32 0
-; CHECK-NEXT:    [[CMPINV:%.*]] = icmp sgt i32 0, [[I:%.*]]
+; CHECK-NEXT:    [[CMPINV:%.*]] = icmp sgt i32 0, [[I]]
 ; CHECK-NEXT:    [[R:%.*]] = add i32 [[M1]], [[M1]]
 ; CHECK-NEXT:    ret i32 [[R]]
+;
   %cmp = icmp sle i32 0, %i
   %m1 = select i1 %cmp, i32 %i, i32 0
   %cmpinv = icmp sgt i32 0, %i
   %m2 = select i1 %cmpinv, i32 0, i32 %i
   %r = add i32 %m1, %m2
   ret i32 %r
 }