[SCEV] Model (xor (shl x, C), (-1 << C)) as (shl (xor x, -1), C)

[bjope]

Summary

InstCombine may fold a left shift over a not (xor by -1).
This patch teaches ScalarEvolution to detect such patterns, creating
a SCEV based on the reverse fold. Without this patch the instcombine
rewrite could lead to missed oppurtunities later in the pipeline
due to not being able to calculate a SCEV for the xor.

An alternative solution could be to modify InstCombine (e.g. in
canShiftBinOpWithConstantRHS) to avoid the fold that creates the
xor that isn't recognized by ScalarEvolution.

Fixes: https://bugs.llvm.org/show_bug.cgi?id=47136

[spatel]

I don't have much experience with SCEV either, but I think your draft change for instcombine made sense:
https://bugs.llvm.org/show_bug.cgi?id=47136#c8

As hinted there, that's the same direction as:
D32255 / rG23bd33c6acc4

So I'm not sure if we would consider this a worthwhile improvement independently and still make a change to SCEV or only change instcombine (or if there's some reason to *not* change instcombine, I'd like to understand that).

[bjope]

In D85969#2218048, @spatel wrote:

I don't have much experience with SCEV either, but I think your draft change for instcombine made sense:
https://bugs.llvm.org/show_bug.cgi?id=47136#c8

As hinted there, that's the same direction as:
D32255 / rG23bd33c6acc4

So I'm not sure if we would consider this a worthwhile improvement independently and still make a change to SCEV or only change instcombine (or if there's some reason to *not* change instcombine, I'd like to understand that).

Well, I'm not exactly sure why instcombine is folding the shift over the operands of binary operators in the first place. Afaict it does that regardless of it being beneficial or not (e.g. triggering more combines). So maybe it is some kind of canonicalization?
If it is a canonicalization it seem weird to be assymetric and do different things depending on the value of the constant operand (and which binary operator that is used), isn't it?
If we decide that the canoncial form of (xor (shl x, C), (-1 << C)) should be (shl (xor x, -1), C), then I figure we need to inplement that reverse transform instead of the one present in instcombine today (specially considering that ScalarEvolution only undestand (shl (xor x, -1), C) without this patch).

So all-in-all, I figured that patching ScalarEvolution would be a more general solution (being a bit more independent on what instcombine and other passes are doing). However, it still depends on the shift being present directly as the xor operand, so it is still not perfect in that sense.

One more thing. I wrote PR47136 because of regressions in three test cases. This patch restore things to the old cycle counts. When testing the other patch from PR47136, simply avoiding some shift folding in instcombine, it also resolved the three regressions. But with the instcombine patch I got another regressions instead. So it seemed like that solution had other implications.

[spatel]

In D85969#2219937, @bjope wrote:

In D85969#2218048, @spatel wrote:

I don't have much experience with SCEV either, but I think your draft change for instcombine made sense:
https://bugs.llvm.org/show_bug.cgi?id=47136#c8

As hinted there, that's the same direction as:
D32255 / rG23bd33c6acc4

So I'm not sure if we would consider this a worthwhile improvement independently and still make a change to SCEV or only change instcombine (or if there's some reason to *not* change instcombine, I'd like to understand that).

Well, I'm not exactly sure why instcombine is folding the shift over the operands of binary operators in the first place. Afaict it does that regardless of it being beneficial or not (e.g. triggering more combines). So maybe it is some kind of canonicalization?

Yes, it looks like it is just a canonicalization, so we standardize on a single pattern. I don't think there's anything inherently better/worse about one form or the other. If we reverse the canonicalization, we may find regressions because we have come to expect the current patterns.

If it is a canonicalization it seem weird to be assymetric and do different things depending on the value of the constant operand (and which binary operator that is used), isn't it?

I agree with that in general, but 'not' is treated as a special-case in instcombine and other passes, so there's precedence to do that for this case too.

If we decide that the canoncial form of (xor (shl x, C), (-1 << C)) should be (shl (xor x, -1), C), then I figure we need to inplement that reverse transform instead of the one present in instcombine today (specially considering that ScalarEvolution only undestand (shl (xor x, -1), C) without this patch).

Yes, we should implement the reverse transform in instcombine to make things canonical - even if that form is not entirely consistent. :)

So all-in-all, I figured that patching ScalarEvolution would be a more general solution (being a bit more independent on what instcombine and other passes are doing). However, it still depends on the shift being present directly as the xor operand, so it is still not perfect in that sense.

One more thing. I wrote PR47136 because of regressions in three test cases. This patch restore things to the old cycle counts. When testing the other patch from PR47136, simply avoiding some shift folding in instcombine, it also resolved the three regressions. But with the instcombine patch I got another regressions instead. So it seemed like that solution had other implications.

Would that be resolved by adding the reverse canonicalization?

[lebedev.ri]

Modelling this in SCEV is totally justifiable even if InstCombine knows how to fix the pattern,
iff having this complexity actually helps. E.g. InstCombine has one-use check, so it won't fix everything.

To find that out, add a STATISTIC() and prove that the code actually fires on some codebase.

Marking as reviewed for now.

llvm/lib/Analysis/ScalarEvolution.cpp

6229–6230

Add statistic here

[bjope]

Haven't seen any gains from this patch, after having rebased to https://reviews.llvm.org/rGec06b381304140b2553cfdfae5a063f39c5c59ff .
The test I ran included bunch of application code, compiled with -O3, for our OOT target.

So I have no plan to pursue landing this, at least not right now.

llvm/include/llvm/Analysis/ScalarEvolution.h

 //===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS,
     return getMulExpr(Ops, Flags, Depth);
   }
   const SCEV *getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
                          SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
                          unsigned Depth = 0) {
     SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
     return getMulExpr(Ops, Flags, Depth);
   }
+  const SCEV *getShlByConstantExpr(const SCEV *LHS, ConstantInt *SA,
+                                   SCEV::NoWrapFlags ShlFlags);
   const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS);
   const SCEV *getUDivExactExpr(const SCEV *LHS, const SCEV *RHS);
   const SCEV *getURemExpr(const SCEV *LHS, const SCEV *RHS);
   const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L,
                             SCEV::NoWrapFlags Flags);
   const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
                             const Loop *L, SCEV::NoWrapFlags Flags);
   const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands,

llvm/lib/Analysis/ScalarEvolution.cpp

 //===- ScalarEvolution.cpp - Scalar Evolution Analysis --------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
     // next one.
   }
 
   // Okay, it looks like we really DO need an mul expr.  Check to see if we
   // already have one, otherwise create a new one.
   return getOrCreateMulExpr(Ops, Flags);
 }
 
+/// Helper to get a SCEV representing a left shift of \p LHS by \p SA steps.
+/// Returns nullptr when unsuccessful.
+const SCEV *ScalarEvolution::getShlByConstantExpr(const SCEV *LHS,
+                                                  ConstantInt *SA,
+                                                  SCEV::NoWrapFlags ShlFlags) {
+  uint32_t BitWidth = cast<IntegerType>(SA->getType())->getBitWidth();
+
+  // If the shift count is not less than the bitwidth, the result of
+  // the shift is undefined. Don't try to analyze it, because the
+  // resolution chosen here may differ from the resolution chosen in
+  // other parts of the compiler.
+  if (SA->getValue().uge(BitWidth))
+    return nullptr;
+
+  // We can safely preserve the nuw flag in all cases. It's also safe to turn a
+  // nuw nsw shl into a nuw nsw mul. However, nsw in isolation requires special
+  // handling. It can be preserved as long as we're not left shifting by
+  // bitwidth - 1.
+  auto Flags = SCEV::FlagAnyWrap;
+  if ((ShlFlags & SCEV::FlagNSW) &&
+      ((ShlFlags & SCEV::FlagNUW) || SA->getValue().ult(BitWidth - 1)))
+    Flags = (SCEV::NoWrapFlags)(Flags | SCEV::FlagNSW);
+  if (ShlFlags & SCEV::FlagNUW)
+    Flags = (SCEV::NoWrapFlags)(Flags | SCEV::FlagNUW);
+
+  Constant *X = ConstantInt::get(
+      getContext(), APInt::getOneBitSet(BitWidth, SA->getZExtValue()));
+  return getMulExpr(LHS, getSCEV(X), Flags);
+}
+
 /// Represents an unsigned remainder expression based on unsigned division.
 const SCEV *ScalarEvolution::getURemExpr(const SCEV *LHS,
                                          const SCEV *RHS) {
   assert(getEffectiveSCEVType(LHS->getType()) ==
          getEffectiveSCEVType(RHS->getType()) &&
          "SCEVURemExpr operand types don't match!");
 
   // Short-circuit easy cases
case Instruction::Xor:
                 // before the zero-extend. In this case, represent the xor
                 // using an add, which is equivalent, and re-apply the zext.
                 APInt Trunc = CI->getValue().trunc(Z0TySize);
                 if (Trunc.zext(getTypeSizeInBits(UTy)) == CI->getValue() &&
                     Trunc.isSignMask())
                   return getZeroExtendExpr(getAddExpr(Z0, getConstant(Trunc)),
                                            UTy);
               }
+
+        // Model xor(shl(x, C), (-1 << C)) as shl(xor(x, -1), C).
+        // This is a variant of the check for xor with -1, and it handles
+        // the case where instcombine has folded the shift over the xor.
+        if (auto *LBO = dyn_cast<BinaryOperator>(BO->LHS))
+          if (ConstantInt *SA = dyn_cast<ConstantInt>(LBO->getOperand(1))) {
+            uint32_t BitWidth = cast<IntegerType>(SA->getType())->getBitWidth();
+            APInt MinusOne = APInt::getAllOnesValue(BitWidth);
+            // Looking for a left shift. Shift count must be less than
+            // bitwidth. And (-1 <<< SA) should be equal to CI.
+            if (LBO->getOpcode() == Instruction::Shl &&
+                SA->getValue().ult(BitWidth) &&
+                CI->getValue() == MinusOne.shl(SA->getValue())) {
+              // We can preserve the flags from the shift. Wrapping behavior
+              // won't change when inverting all bits before the shift.
+              auto Flags = getNoWrapFlagsFromUB(LBO);
+              const SCEV *NotXSCEV = getNotSCEV(getSCEV(LBO->getOperand(0)));
+              if (auto *SCEV = getShlByConstantExpr(NotXSCEV, SA, Flags))
+                return SCEV;
+            }
+          }
       }
       break;
 
     case Instruction::Shl:
       // Turn shift left of a constant amount into a multiply.
       if (ConstantInt *SA = dyn_cast<ConstantInt>(BO->RHS)) {
-        uint32_t BitWidth = cast<IntegerType>(SA->getType())->getBitWidth();
-
-        // If the shift count is not less than the bitwidth, the result of
-        // the shift is undefined. Don't try to analyze it, because the
-        // resolution chosen here may differ from the resolution chosen in
-        // other parts of the compiler.
-        if (SA->getValue().uge(BitWidth))
-          break;
-
-        // We can safely preserve the nuw flag in all cases. It's also safe to
-        // turn a nuw nsw shl into a nuw nsw mul. However, nsw in isolation
-        // requires special handling. It can be preserved as long as we're not
-        // left shifting by bitwidth - 1.
-        auto Flags = SCEV::FlagAnyWrap;
-        if (BO->Op) {
-          auto MulFlags = getNoWrapFlagsFromUB(BO->Op);
-          if ((MulFlags & SCEV::FlagNSW) &&
-              ((MulFlags & SCEV::FlagNUW) || SA->getValue().ult(BitWidth - 1)))
-            Flags = (SCEV::NoWrapFlags)(Flags | SCEV::FlagNSW);
-          if (MulFlags & SCEV::FlagNUW)
-            Flags = (SCEV::NoWrapFlags)(Flags | SCEV::FlagNUW);
-        }
-
-        Constant *X = ConstantInt::get(
-            getContext(), APInt::getOneBitSet(BitWidth, SA->getZExtValue()));
-        return getMulExpr(getSCEV(BO->LHS), getSCEV(X), Flags);
+        auto Flags = BO->Op ? getNoWrapFlagsFromUB(BO->Op) : SCEV::FlagAnyWrap;
+        if (auto *SCEV = getShlByConstantExpr(getSCEV(BO->LHS), SA, Flags))
+          return SCEV;
       }
       break;
 
     case Instruction::AShr: {
       // AShr X, C, where C is a constant.
       ConstantInt *CI = dyn_cast<ConstantInt>(BO->RHS);
       if (!CI)
         break;

llvm/test/Analysis/ScalarEvolution/xor-shl.ll

+; RUN: opt < %s -scalar-evolution -analyze -enable-new-pm=0 | FileCheck %s
+; RUN: opt < %s "-passes=print<scalar-evolution>" -disable-output 2>&1 | FileCheck %s
+
+; CHECK-LABEL: @test1a
+; CHECK:      %y =
+; CHECK-NEXT: --> (-2 + (-2 * %x)) U: [0,-1) S: [-2147483648,2147483647)
+define i32 @test1a(i32 %x) {
+  %n = shl i32 %x, 1
+  %y = xor i32 %n, -2
+  ret i32 %y
+}
+
+; CHECK-LABEL: @test1b
+; CHECK:      %y =
+; CHECK-NEXT: --> (-2 + (-2 * %x)) U: [0,-1) S: [-2147483648,2147483647)
+define i32 @test1b(i32 %x) {
+  %n = xor i32 %x, -1
+  %y = shl i32 %n, 1
+  ret i32 %y
+}
+
+; CHECK-LABEL: @test2a
+; CHECK:      %y =
+; CHECK-NEXT: -->  (-16 + (-16 * %x)) U: [0,-15) S: [-2147483648,2147483633)
+define i32 @test2a(i32 %x) {
+  %n = shl i32 %x, 4
+  %y = xor i32 %n, -16
+  ret i32 %y
+}
+
+; CHECK-LABEL: @test2b
+; CHECK:      %y =
+; CHECK-NEXT: -->  (-16 + (-16 * %x)) U: [0,-15) S: [-2147483648,2147483633)
+define i32 @test2b(i32 %x) {
+  %n = xor i32 %x, -1
+  %y = shl i32 %n, 4
+  ret i32 %y
+}
+
+; CHECK-LABEL: @test3a
+; CHECK:      %y =
+; CHECK-NEXT: -->  (-8 + (-8 * %x)) U: [0,-7) S: [-8,1)
+define i4 @test3a(i4 %x) {
+  %n = shl i4 %x, 3
+  %y = xor i4 %n, -8
+  ret i4 %y
+}
+
+; CHECK-LABEL: @test3b
+; CHECK:      %y =
+; CHECK-NEXT: -->  (-8 + (-8 * %x)) U: [0,-7) S: [-8,1)
+define i4 @test3b(i4 %x) {
+  %n = xor i4 %x, -1
+  %y = shl i4 %n, 3
+  ret i4 %y
+}
+
+; CHECK-LABEL: @test4a
+; CHECK:      %y =
+; CHECK-NEXT: -->  %y U: [0,-7) S: [-8,1)
+define i4 @test4a(i4 %x) {
+  %n = shl i4 %x, 4
+  %y = xor i4 %n, -16
+  ret i4 %y
+}
+
+; CHECK-LABEL: @test4b
+; CHECK:      %y =
+; CHECK-NEXT: -->  %y U: [0,-7) S: [-8,1)
+define i4 @test4b(i4 %x) {
+  %n = xor i4 %x, -1
+  %y = shl i4 %n, 4
+  ret i4 %y
+}