[DAGCombiner] Use computeKnownBits to match rotate patterns that have had their amount masking modified by simplifyDemandedBits.

[craig.topper]

Summary

SimplifyDemandedBits can remove bits from the masks for the shift amounts we need to see to detect rotates.

This patch uses zeroes from computeKnownBits to fill in some of these mask bits to make the match work.

As currently written this calls computeKnownBits even when the mask hasn't been simplified because it made the code simpler. If we're worried about compile time performance we can improve this.

I know we're talking about making a rotate intrinsic, but hopefully we can go ahead and do this change and just make sure the rotate intrinsic also handles it.

[RKSimon]

Add some similar vector tests to combine-rotates.ll ?

[craig.topper]

Add vector tests too.

[RKSimon]

LGTM - I don't think the cost of computeKnownBits will be a perf drain, but we can revisit if necessary

test/CodeGen/X86/combine-rotates.ll

68 ↗

(On Diff #147850)

Can you fix this please? Old CHECKS that didn't get stripped.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

 // range [0, EltSize), Neg == (Pos == 0 ? 0 : EltSize - Pos).  This means that
 // for two opposing shifts shift1 and shift2 and a value X with OpBits bits:
 //
 //     (or (shift1 X, Neg), (shift2 X, Pos))
 //
 // 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.
-static bool matchRotateSub(SDValue Pos, SDValue Neg, unsigned EltSize) {
+static bool matchRotateSub(SDValue Pos, SDValue Neg, unsigned EltSize,
+                           SelectionDAG &DAG) {
   // 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,
   //     (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.
   unsigned MaskLoBits = 0;
   if (Neg.getOpcode() == ISD::AND && isPowerOf2_64(EltSize)) {
     if (ConstantSDNode *NegC = isConstOrConstSplat(Neg.getOperand(1))) {
-      if (NegC->getAPIntValue() == EltSize - 1) {
+      KnownBits Known;
+      DAG.computeKnownBits(Neg.getOperand(0), Known);
+      unsigned Bits = Log2_64(EltSize);
+      if (NegC->getAPIntValue().getActiveBits() <= Bits &&
+          ((NegC->getAPIntValue() | Known.Zero).countTrailingOnes() >= Bits)) {
         Neg = Neg.getOperand(0);
-        MaskLoBits = Log2_64(EltSize);
+        MaskLoBits = Bits;
       }
     }
   }
 
   // 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)))
-      if (PosC->getAPIntValue() == EltSize - 1)
+  if (MaskLoBits && Pos.getOpcode() == ISD::AND) {
+    if (ConstantSDNode *PosC = isConstOrConstSplat(Pos.getOperand(1))) {
+      KnownBits Known;
+      DAG.computeKnownBits(Pos.getOperand(0), Known);
+      if (PosC->getAPIntValue().getActiveBits() <= MaskLoBits &&
+          ((PosC->getAPIntValue() | Known.Zero).countTrailingOnes() >=
+           MaskLoBits))
         Pos = Pos.getOperand(0);
+    }
+  }
 
   // The condition we need is now:
   //
   //     (NegC - NegOp1) & Mask == (EltSize - Pos) & Mask
   //
   // If NegOp1 == Pos then we need:
   //
   //              EltSize & Mask == NegC & Mask
SDNode *DAGCombiner::MatchRotatePosNeg(SDValue Shifted, SDValue Pos,
   // fold (or (shl x, (*ext y)),
   //          (srl x, (*ext (sub 32, y)))) ->
   //   (rotl x, y) or (rotr x, (sub 32, y))
   //
   // fold (or (shl x, (*ext (sub 32, y))),
   //          (srl x, (*ext y))) ->
   //   (rotr x, y) or (rotl x, (sub 32, y))
   EVT VT = Shifted.getValueType();
-  if (matchRotateSub(InnerPos, InnerNeg, VT.getScalarSizeInBits())) {
+  if (matchRotateSub(InnerPos, InnerNeg, VT.getScalarSizeInBits(), DAG)) {
     bool HasPos = TLI.isOperationLegalOrCustom(PosOpcode, VT);
     return DAG.getNode(HasPos ? PosOpcode : NegOpcode, DL, VT, Shifted,
                        HasPos ? Pos : Neg).getNode();
   }
 
   return nullptr;
 }
 

test/CodeGen/X86/rotate4.ll

; CHECK-NEXT:    retq
   %or = or i16 %shl, %shr
   store i16 %or, i16* %p, align 1
   ret void
 }
 
 define i32 @rotate_demanded_bits(i32, i32) {
 ; CHECK-LABEL: rotate_demanded_bits:
 ; CHECK:       # %bb.0:
+; CHECK-NEXT:    andb $30, %sil
 ; CHECK-NEXT:    movl %esi, %ecx
-; CHECK-NEXT:    andl $30, %ecx
-; CHECK-NEXT:    movl %edi, %eax
-; CHECK-NEXT:    shll %cl, %eax
-; CHECK-NEXT:    negl %ecx
-; CHECK-NEXT:    andb $30, %cl
-; CHECK-NEXT:    # kill: def $cl killed $cl killed $ecx
-; CHECK-NEXT:    shrl %cl, %edi
-; CHECK-NEXT:    orl %eax, %edi
+; CHECK-NEXT:    roll %cl, %edi
 ; CHECK-NEXT:    movl %edi, %eax
 ; CHECK-NEXT:    retq
   %3 = and i32 %1, 30
   %4 = shl i32 %0, %3
   %5 = sub nsw i32 0, %3
   %6 = and i32 %5, 30
   %7 = lshr i32 %0, %6
   %8 = or i32 %7, %4
; CHECK-NEXT:    retq
   %7 = lshr i32 %0, %6
   %8 = or i32 %7, %4
   ret i32 %8
 }
 
 define i32 @rotate_demanded_bits_3(i32, i32) {
 ; CHECK-LABEL: rotate_demanded_bits_3:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    addl %esi, %esi
-; CHECK-NEXT:    movl %esi, %ecx
-; CHECK-NEXT:    andb $30, %cl
-; CHECK-NEXT:    movl %edi, %eax
-; CHECK-NEXT:    shll %cl, %eax
-; CHECK-NEXT:    negl %esi
+; CHECK-NEXT:    addb %sil, %sil
 ; CHECK-NEXT:    andb $30, %sil
 ; CHECK-NEXT:    movl %esi, %ecx
-; CHECK-NEXT:    shrl %cl, %edi
-; CHECK-NEXT:    orl %eax, %edi
+; CHECK-NEXT:    roll %cl, %edi
 ; CHECK-NEXT:    movl %edi, %eax
 ; CHECK-NEXT:    retq
   %3 = shl i32 %1, 1
   %4 = and i32 %3, 30
   %5 = shl i32 %0, %4
   %6 = sub i32 0, %3
   %7 = and i32 %6, 30
   %8 = lshr i32 %0, %7
   %9 = or i32 %5, %8
   ret i32 %9
 }