[DAGCombine] Mask doesn't have to be (EltSize - 1) exactly when combining rotation

[• pcwang-thead]

Summary

I think what we need is the least Log2(EltSize) significant bits are known to be ones.

[• pcwang-thead]

Rebase on precommit test.

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

7301–7302

It might be worthwhile to replace the ISD::AND case with SimplifyMultipleUseDemandedBits:

if (IsRotate && isPowerOf2_64(EltSize)) {
  unsigned Bits = Log2_64(EltSize);
  APInt DemandedBits = APInt::getLowBitsSet(EltSize, Bits);
  if (SDValue Inner = SimplifyMultipleUseDemandedBits(Neg, DemandedBits, DAG)) {
    Neg = Inner;
    MaskLoBits = Bits;
  }
}

[• pcwang-thead]

Address comment.

[• pcwang-thead]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

7301–7302

Thanks! I think it makes sense!

[RKSimon]

LGTM

[• pcwang-thead]

Rebased on new tests.

[• pcwang-thead]

Any thoughts about comments? I think they may be not matched with implementation now. @RKSimon

[RKSimon]

In D130251#3675036, @pcwang-thead wrote:

Any thoughts about comments? I think they may be not matched with implementation now. @RKSimon

You mean the pseudo-code that refers to 'Neg & (EltSize - 1)' etc?

[• pcwang-thead]

In D130251#3675652, @RKSimon wrote:

In D130251#3675036, @pcwang-thead wrote:

Any thoughts about comments? I think they may be not matched with implementation now. @RKSimon

You mean the pseudo-code that refers to 'Neg & (EltSize - 1)' etc?

Yes. Is it OK to keep the same?

[RKSimon]

How about this?

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

7295–7297

// This allows us to peek through any operations that only the affect Mask's un-demanded bits.

[• pcwang-thead]

Update comments.

[• pcwang-thead]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

7295–7297

Make sense to me. Thanks!

[RKSimon]

LGTM

[mysterymath]

This seems to be hitting assertions when compiling BoringSSL:
https://luci-milo.appspot.com/ui/p/fuchsia/builders/ci/clang_toolchain.ci.core.x64-release/b8807566603550542609/overview

Haven't conclusively proven that it's this change, but it's the only one in the blamelist that could affect X86 ISel.

[RKSimon]

In D130251#3680036, @mysterymath wrote:

This seems to be hitting assertions when compiling BoringSSL:
https://luci-milo.appspot.com/ui/p/fuchsia/builders/ci/clang_toolchain.ci.core.x64-release/b8807566603550542609/overview

Haven't conclusively proven that it's this change, but it's the only one in the blamelist that could affect X86 ISel.

More likely its exposed something - demanded bits tends to do that. Any chance you can send us the IR file? Or even just the pre-processed source.

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

7304

I'm only guessing but you might need to use Neg.getScalarValueSizeInBits instead of EltSize - it might be that the shift amount type doesn't match the result type

7324

Pos.getScalarValueSizeInBits instead of EltSize

[RKSimon]

@mysterymath I've pushed rG1ea7b9c6ee6420dd6e87489534f44b92e1b6f220 as a tentative fix

[mysterymath]

In D130251#3680141, @RKSimon wrote:

@mysterymath I've pushed rG1ea7b9c6ee6420dd6e87489534f44b92e1b6f220 as a tentative fix

Thanks, looks like that did the trick.

[• pcwang-thead]

Thanks for the fix! :-) @RKSimon

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

 // reduces to a rotate in direction shift2 by Pos or (equivalently) a rotate
 // in direction shift1 by Neg.  The range [0, EltSize) means that we only need
 // to consider shift amounts with defined behavior.
 //
 // The IsRotate flag should be set when the LHS of both shifts is the same.
 // Otherwise if matching a general funnel shift, it should be clear.
 static bool matchRotateSub(SDValue Pos, SDValue Neg, unsigned EltSize,
                            SelectionDAG &DAG, bool IsRotate) {
+  const auto &TLI = DAG.getTargetLoweringInfo();
   // If EltSize is a power of 2 then:
   //
   //  (a) (Pos == 0 ? 0 : EltSize - Pos) == (EltSize - Pos) & (EltSize - 1)
   //  (b) Neg == Neg & (EltSize - 1) whenever Neg is in [0, EltSize).
   //
   // So if EltSize is a power of 2 and Neg is (and Neg', EltSize-1), we check
   // for the stronger condition:
   //
static bool matchRotateSub(SDValue Pos, SDValue Neg, unsigned EltSize,
   // where Neg and Pos are never in range at the same time.  E.g. for
   // EltSize == 32, using [A] would allow a Neg of the form (sub 64, Pos)
   // as well as (sub 32, Pos), but:
   //
   //     (or (shift1 X, (sub 64, Pos)), (shift2 X, Pos))
   //
   // always invokes undefined behavior for 32-bit X.
   //
   // Below, Mask == EltSize - 1 when using [A] and is all-ones otherwise.
+  // This allows us to peek through any operations that only affect Mask's
+  // un-demanded bits.
   //
-  // NOTE: We can only do this when matching an AND and not a general
-  // funnel shift.
+  // NOTE: We can only do this when matching operations which won't modify the
+  // least Log2(EltSize) significant bits and not a general funnel shift.
   unsigned MaskLoBits = 0;
-  if (IsRotate && Neg.getOpcode() == ISD::AND && isPowerOf2_64(EltSize)) {
-    if (ConstantSDNode *NegC = isConstOrConstSplat(Neg.getOperand(1))) {
-      KnownBits Known = DAG.computeKnownBits(Neg.getOperand(0));
-      unsigned Bits = Log2_64(EltSize);
-      if (NegC->getAPIntValue().getActiveBits() <= Bits &&
-          ((NegC->getAPIntValue() | Known.Zero).countTrailingOnes() >= Bits)) {
-        Neg = Neg.getOperand(0);
-        MaskLoBits = Bits;
-      }
-    }
-  }
+  if (IsRotate && isPowerOf2_64(EltSize)) {
+    APInt DemandedBits = APInt::getLowBitsSet(EltSize, Bits);
+    if (SDValue Inner =
+            TLI.SimplifyMultipleUseDemandedBits(Neg, DemandedBits, DAG)) {
+      Neg = Inner;
 
   // Check whether Neg has the form (sub NegC, NegOp1) for some NegC and NegOp1.
   if (Neg.getOpcode() != ISD::SUB)
     return false;
   ConstantSDNode *NegC = isConstOrConstSplat(Neg.getOperand(0));
   if (!NegC)
     return false;
   SDValue NegOp1 = Neg.getOperand(1);
 
-  // On the RHS of [A], if Pos is Pos' & (EltSize - 1), just replace Pos with
-  // Pos'.  The truncation is redundant for the purpose of the equality.
-  if (MaskLoBits && Pos.getOpcode() == ISD::AND) {
-    if (ConstantSDNode *PosC = isConstOrConstSplat(Pos.getOperand(1))) {
-      KnownBits Known = DAG.computeKnownBits(Pos.getOperand(0));
-      if (PosC->getAPIntValue().getActiveBits() <= MaskLoBits &&
-          ((PosC->getAPIntValue() | Known.Zero).countTrailingOnes() >=
-           MaskLoBits))
-        Pos = Pos.getOperand(0);
+  // On the RHS of [A], if Pos is the result of operation on Pos' that won't
+  // affect Mask's demanded bits, just replace Pos with Pos'. These operations
+  // are redundant for the purpose of the equality.
+  if (MaskLoBits) {
+    APInt DemandedBits = APInt::getLowBitsSet(EltSize, MaskLoBits);
+    if (SDValue Inner =
+            TLI.SimplifyMultipleUseDemandedBits(Pos, DemandedBits, DAG)) {
+      Pos = Inner;
     }
   }
 
   // The condition we need is now:
   //
   //     (NegC - NegOp1) & Mask == (EltSize - Pos) & Mask
   //
   // If NegOp1 == Pos then we need:

llvm/test/CodeGen/RISCV/rotl-rotr.ll

 ; RV64I-NEXT:    sllw a2, a0, a1
 ; RV64I-NEXT:    negw a1, a1
 ; RV64I-NEXT:    srlw a0, a0, a1
 ; RV64I-NEXT:    or a0, a2, a0
 ; RV64I-NEXT:    ret
 ;
 ; RV32ZBB-LABEL: rotl_32_mask_and_63_and_31:
 ; RV32ZBB:       # %bb.0:
-; RV32ZBB-NEXT:    sll a2, a0, a1
-; RV32ZBB-NEXT:    neg a1, a1
-; RV32ZBB-NEXT:    srl a0, a0, a1
-; RV32ZBB-NEXT:    or a0, a2, a0
+; RV32ZBB-NEXT:    rol a0, a0, a1
 ; RV32ZBB-NEXT:    ret
 ;
 ; RV64ZBB-LABEL: rotl_32_mask_and_63_and_31:
 ; RV64ZBB:       # %bb.0:
-; RV64ZBB-NEXT:    sllw a2, a0, a1
-; RV64ZBB-NEXT:    negw a1, a1
-; RV64ZBB-NEXT:    srlw a0, a0, a1
-; RV64ZBB-NEXT:    or a0, a2, a0
+; RV64ZBB-NEXT:    rolw a0, a0, a1
 ; RV64ZBB-NEXT:    ret
   %a = and i32 %y, 63
   %b = shl i32 %x, %a
   %c = sub i32 0, %y
   %d = and i32 %c, 31
   %e = lshr i32 %x, %d
   %f = or i32 %b, %e
   ret i32 %f

 ; RV64I-NEXT:    sllw a2, a0, a1
 ; RV64I-NEXT:    negw a1, a1
 ; RV64I-NEXT:    srlw a0, a0, a1
 ; RV64I-NEXT:    or a0, a2, a0
 ; RV64I-NEXT:    ret
 ;
 ; RV32ZBB-LABEL: rotl_32_mask_or_64_or_32:
 ; RV32ZBB:       # %bb.0:
-; RV32ZBB-NEXT:    ori a2, a1, 64
-; RV32ZBB-NEXT:    sll a2, a0, a2
-; RV32ZBB-NEXT:    neg a1, a1
-; RV32ZBB-NEXT:    ori a1, a1, 32
-; RV32ZBB-NEXT:    srl a0, a0, a1
-; RV32ZBB-NEXT:    or a0, a2, a0
+; RV32ZBB-NEXT:    rol a0, a0, a1
 ; RV32ZBB-NEXT:    ret
 ;
 ; RV64ZBB-LABEL: rotl_32_mask_or_64_or_32:
 ; RV64ZBB:       # %bb.0:
-; RV64ZBB-NEXT:    sllw a2, a0, a1
-; RV64ZBB-NEXT:    negw a1, a1
-; RV64ZBB-NEXT:    srlw a0, a0, a1
-; RV64ZBB-NEXT:    or a0, a2, a0
+; RV64ZBB-NEXT:    rolw a0, a0, a1
 ; RV64ZBB-NEXT:    ret
   %a = or i32 %y, 64
   %b = shl i32 %x, %a
   %c = sub i32 0, %y
   %d = or i32 %c, 32
   %e = lshr i32 %x, %d
   %f = or i32 %b, %e
   ret i32 %f

 ; RV64I-NEXT:    srlw a2, a0, a1
 ; RV64I-NEXT:    negw a1, a1
 ; RV64I-NEXT:    sllw a0, a0, a1
 ; RV64I-NEXT:    or a0, a2, a0
 ; RV64I-NEXT:    ret
 ;
 ; RV32ZBB-LABEL: rotr_32_mask_and_63_and_31:
 ; RV32ZBB:       # %bb.0:
-; RV32ZBB-NEXT:    srl a2, a0, a1
-; RV32ZBB-NEXT:    neg a1, a1
-; RV32ZBB-NEXT:    sll a0, a0, a1
-; RV32ZBB-NEXT:    or a0, a2, a0
+; RV32ZBB-NEXT:    ror a0, a0, a1
 ; RV32ZBB-NEXT:    ret
 ;
 ; RV64ZBB-LABEL: rotr_32_mask_and_63_and_31:
 ; RV64ZBB:       # %bb.0:
-; RV64ZBB-NEXT:    srlw a2, a0, a1
-; RV64ZBB-NEXT:    negw a1, a1
-; RV64ZBB-NEXT:    sllw a0, a0, a1
-; RV64ZBB-NEXT:    or a0, a2, a0
+; RV64ZBB-NEXT:    rorw a0, a0, a1
 ; RV64ZBB-NEXT:    ret
   %a = and i32 %y, 63
   %b = lshr i32 %x, %a
   %c = sub i32 0, %y
   %d = and i32 %c, 31
   %e = shl i32 %x, %d
   %f = or i32 %b, %e
   ret i32 %f

 ; RV64I-NEXT:    srlw a2, a0, a1
 ; RV64I-NEXT:    negw a1, a1
 ; RV64I-NEXT:    sllw a0, a0, a1
 ; RV64I-NEXT:    or a0, a2, a0
 ; RV64I-NEXT:    ret
 ;
 ; RV32ZBB-LABEL: rotr_32_mask_or_64_or_32:
 ; RV32ZBB:       # %bb.0:
-; RV32ZBB-NEXT:    ori a2, a1, 64
-; RV32ZBB-NEXT:    srl a2, a0, a2
-; RV32ZBB-NEXT:    neg a1, a1
-; RV32ZBB-NEXT:    ori a1, a1, 32
-; RV32ZBB-NEXT:    sll a0, a0, a1
-; RV32ZBB-NEXT:    or a0, a2, a0
+; RV32ZBB-NEXT:    ror a0, a0, a1
 ; RV32ZBB-NEXT:    ret
 ;
 ; RV64ZBB-LABEL: rotr_32_mask_or_64_or_32:
 ; RV64ZBB:       # %bb.0:
-; RV64ZBB-NEXT:    srlw a2, a0, a1
-; RV64ZBB-NEXT:    negw a1, a1
-; RV64ZBB-NEXT:    sllw a0, a0, a1
-; RV64ZBB-NEXT:    or a0, a2, a0
+; RV64ZBB-NEXT:    rorw a0, a0, a1
 ; RV64ZBB-NEXT:    ret
   %a = or i32 %y, 64
   %b = lshr i32 %x, %a
   %c = sub i32 0, %y
   %d = or i32 %c, 32
   %e = shl i32 %x, %d
   %f = or i32 %b, %e
   ret i32 %f

 ; RV32ZBB-NEXT:    sll a0, a0, a2
 ; RV32ZBB-NEXT:    or a4, a4, a0
 ; RV32ZBB-NEXT:  .LBB11_7:
 ; RV32ZBB-NEXT:    mv a0, a4
 ; RV32ZBB-NEXT:    ret
 ;
 ; RV64ZBB-LABEL: rotl_64_mask_and_127_and_63:
 ; RV64ZBB:       # %bb.0:
-; RV64ZBB-NEXT:    sll a2, a0, a1
-; RV64ZBB-NEXT:    neg a1, a1
-; RV64ZBB-NEXT:    srl a0, a0, a1
-; RV64ZBB-NEXT:    or a0, a2, a0
+; RV64ZBB-NEXT:    rol a0, a0, a1
 ; RV64ZBB-NEXT:    ret
   %a = and i64 %y, 127
   %b = shl i64 %x, %a
   %c = sub i64 0, %y
   %d = and i64 %c, 63
   %e = lshr i64 %x, %d
   %f = or i64 %b, %e
   ret i64 %f

 ; RV32ZBB-NEXT:    sll a3, a0, a2
 ; RV32ZBB-NEXT:    neg a0, a2
 ; RV32ZBB-NEXT:    srl a0, a1, a0
 ; RV32ZBB-NEXT:    mv a1, a3
 ; RV32ZBB-NEXT:    ret
 ;
 ; RV64ZBB-LABEL: rotl_64_mask_or_128_or_64:
 ; RV64ZBB:       # %bb.0:
-; RV64ZBB-NEXT:    ori a2, a1, 128
-; RV64ZBB-NEXT:    sll a2, a0, a2
-; RV64ZBB-NEXT:    neg a1, a1
-; RV64ZBB-NEXT:    ori a1, a1, 64
-; RV64ZBB-NEXT:    srl a0, a0, a1
-; RV64ZBB-NEXT:    or a0, a2, a0
+; RV64ZBB-NEXT:    rol a0, a0, a1
 ; RV64ZBB-NEXT:    ret
   %a = or i64 %y, 128
   %b = shl i64 %x, %a
   %c = sub i64 0, %y
   %d = or i64 %c, 64
   %e = lshr i64 %x, %d
   %f = or i64 %b, %e
   ret i64 %f

 ; RV32ZBB-NEXT:    srl a1, a1, a2
 ; RV32ZBB-NEXT:    or a4, a4, a1
 ; RV32ZBB-NEXT:  .LBB14_7:
 ; RV32ZBB-NEXT:    mv a1, a4
 ; RV32ZBB-NEXT:    ret
 ;
 ; RV64ZBB-LABEL: rotr_64_mask_and_127_and_63:
 ; RV64ZBB:       # %bb.0:
-; RV64ZBB-NEXT:    srl a2, a0, a1
-; RV64ZBB-NEXT:    neg a1, a1
-; RV64ZBB-NEXT:    sll a0, a0, a1
-; RV64ZBB-NEXT:    or a0, a2, a0
+; RV64ZBB-NEXT:    ror a0, a0, a1
 ; RV64ZBB-NEXT:    ret
   %a = and i64 %y, 127
   %b = lshr i64 %x, %a
   %c = sub i64 0, %y
   %d = and i64 %c, 63
   %e = shl i64 %x, %d
   %f = or i64 %b, %e
   ret i64 %f

 ; RV32ZBB-NEXT:    srl a3, a1, a2
 ; RV32ZBB-NEXT:    neg a1, a2
 ; RV32ZBB-NEXT:    sll a1, a0, a1
 ; RV32ZBB-NEXT:    mv a0, a3
 ; RV32ZBB-NEXT:    ret
 ;
 ; RV64ZBB-LABEL: rotr_64_mask_or_128_or_64:
 ; RV64ZBB:       # %bb.0:
-; RV64ZBB-NEXT:    ori a2, a1, 128
-; RV64ZBB-NEXT:    srl a2, a0, a2
-; RV64ZBB-NEXT:    neg a1, a1
-; RV64ZBB-NEXT:    ori a1, a1, 64
-; RV64ZBB-NEXT:    sll a0, a0, a1
-; RV64ZBB-NEXT:    or a0, a2, a0
+; RV64ZBB-NEXT:    ror a0, a0, a1
 ; RV64ZBB-NEXT:    ret
   %a = or i64 %y, 128
   %b = lshr i64 %x, %a
   %c = sub i64 0, %y
   %d = or i64 %c, 64
   %e = shl i64 %x, %d
   %f = or i64 %b, %e
   ret i64 %f