[DAGCombiner] Match (add X, X) as (shl X, 1) when detecting rotate.

[deadalnix]

Summary

The combiner transforms (shl X, 1) into (add X, X).

[lebedev.ri]

Pattern look good to me, but i recall having disscussion in https://reviews.llvm.org/D64275#inline-576684
Granted, that is InstCombine, but what happens here if we create instruction but then fail to fold?

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

6019

Is there any easy way that we can avoid creating nodes like this? Its purpose seems purely to be matched again later.

[deadalnix]

In D66882#1649078, @lebedev.ri wrote:

Pattern look good to me, but i recall having disscussion in https://reviews.llvm.org/D64275#inline-576684
Granted, that is InstCombine, but what happens here if we create instruction but then fail to fold?

The node created this way end up added to PruningList by WorklistInserter are are removed when poping the next element from the worklist in clearAddedDanglingWorklistEntries.

@RKSimon Let me try that. This will require to refactor MatchRotate quite a bit, but it may be possible.

[deadalnix]

I looked at the problem that @spatel ran into. It is not applicable to DAGCombiner, because the DAG is processed only once rather than in a loop as long as it is modified. I wouldn't be possible to change it to work like InstCombine does as there are a ton of A -> B -> A type of tranforms. That being said, it's not a good reason to add more, so it's worth looking into improving this if possible.

[deadalnix]

• Avoid creating the shift node when not stricly required.
• Add negative tests.

[deadalnix]

Tighten the checks before creating the node.

[lebedev.ri]

Precommit tests pls.
Please add commutative test - or is commutative.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

6026

I suppose add v v implies that c can only be bitwidth-1

[deadalnix]

Add tests for the commutative case.
Precommit tests.

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

6120

Hm, this function already handles non-shifts.
Can it simply be extended with a similar block?

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

6120

The whole function is about reconstructing shifts from something else.

[RKSimon]

LGTM - cheers!

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

6120

duh?
That is not what i was talking about.
This code already matches non-shifts - multiplications, divisions,
I'm wondering if it can be extended to also handle add's, without adding that explicit return DAG.getNode(ISD::SHL,

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

6120

But this code DOES build a shift node.

6145

This is where the shift node is built.

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

6145

Err, this is actually exactly what i'm saying :)
I'm simply wondering if the current implementation, i.e.

// Value and Type of the shift.
SDValue OppShiftLHS = OppShift.getOperand(0);
EVT ShiftedVT = OppShiftLHS.getValueType();

// Amount of the existing shift.
ConstantSDNode *OppShiftCst = isConstOrConstSplat(OppShift.getOperand(1));

// (add v v) -> (shl v 1)
if (OppShift.getOpcode() == ISD::SRL && OppShiftCst &&
    ExtractFrom.getOpcode() == ISD::ADD &&
    ExtractFrom.getOperand(0) == ExtractFrom.getOperand(1) &&
    ExtractFrom.getOperand(0) == OppShiftLHS &&
    OppShiftCst->getAPIntValue() == ShiftedVT.getScalarSizeInBits() - 1)
  return DAG.getNode(ISD::SHL, DL, ShiftedVT, OppShiftLHS,
                     DAG.getShiftAmountConstant(1, ShiftedVT, DL));

is the simplest solution here, or the code that is located later in the function
can be refactored to handle this new add %x, %x case too, just like it already
handles div/rem nodes?

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

6145

The code is written in a style where it bail when something is wrong. As a result it either need to be rewritten, or new patterns need to be added early on.

Sorry for not understanding what you were hinting at before.

[lebedev.ri]

No further comments, thanks.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

static bool matchRotateHalf(SelectionDAG &DAG, SDValue Op, SDValue &Shift,
   if (Op.getOpcode() == ISD::SRL || Op.getOpcode() == ISD::SHL) {
     Shift = Op;
     return true;
   }
   return false;
 }
 
 /// Helper function for visitOR to extract the needed side of a rotate idiom
 /// from a shl/srl/mul/udiv.  This is meant to handle cases where
 /// InstCombine merged some outside op with one of the shifts from
 /// the rotate pattern.
 /// \returns An empty \c SDValue if the needed shift couldn't be extracted.
 /// Otherwise, returns an expansion of \p ExtractFrom based on the following
 /// patterns:
 ///
+///   (or (add v v) (shrl v bitwidth-1)):
+///     expands (add v v) -> (shl v 1)
+///
 ///   (or (mul v c0) (shrl (mul v c1) c2)):
 ///     expands (mul v c0) -> (shl (mul v c1) c3)
 ///
 ///   (or (udiv v c0) (shl (udiv v c1) c2)):
 ///     expands (udiv v c0) -> (shrl (udiv v c1) c3)
 ///
 ///   (or (shl v c0) (shrl (shl v c1) c2)):
 ///     expands (shl v c0) -> (shl (shl v c1) c3)
 ///
 ///   (or (shrl v c0) (shl (shrl v c1) c2)):
 ///     expands (shrl v c0) -> (shrl (shrl v c1) c3)
 ///
 /// Such that in all cases, c3+c2==bitwidth(op v c1).
 static SDValue extractShiftForRotate(SelectionDAG &DAG, SDValue OppShift,
                                      SDValue ExtractFrom, SDValue &Mask,
                                      const SDLoc &DL) {
   assert(OppShift && ExtractFrom && "Empty SDValue");
   assert(
       (OppShift.getOpcode() == ISD::SHL || OppShift.getOpcode() == ISD::SRL) &&
       "Existing shift must be valid as a rotate half");
 
   ExtractFrom = stripConstantMask(DAG, ExtractFrom, Mask);
+
+  // Value and Type of the shift.
+  SDValue OppShiftLHS = OppShift.getOperand(0);
+  EVT ShiftedVT = OppShiftLHS.getValueType();
+
+  // Amount of the existing shift.
+  ConstantSDNode *OppShiftCst = isConstOrConstSplat(OppShift.getOperand(1));
+
+  // (add v v) -> (shl v 1)
+  if (OppShift.getOpcode() == ISD::SRL && OppShiftCst &&
+      ExtractFrom.getOpcode() == ISD::ADD &&
+      ExtractFrom.getOperand(0) == ExtractFrom.getOperand(1) &&
+      ExtractFrom.getOperand(0) == OppShiftLHS &&
+      OppShiftCst->getAPIntValue() == ShiftedVT.getScalarSizeInBits() - 1)
+    return DAG.getNode(ISD::SHL, DL, ShiftedVT, OppShiftLHS,
+                       DAG.getShiftAmountConstant(1, ShiftedVT, DL));
+
   // Preconditions:
   //    (or (op0 v c0) (shiftl/r (op0 v c1) c2))
   //
   // Find opcode of the needed shift to be extracted from (op0 v c0).
   unsigned Opcode = ISD::DELETED_NODE;
   bool IsMulOrDiv = false;
   // Set Opcode and IsMulOrDiv if the extract opcode matches the needed shift
   // opcode or its arithmetic (mul or udiv) variant.
   auto SelectOpcode = [&](unsigned NeededShift, unsigned MulOrDivVariant) {
     IsMulOrDiv = ExtractFrom.getOpcode() == MulOrDivVariant;
     if (!IsMulOrDiv && ExtractFrom.getOpcode() != NeededShift)
       return false;
     Opcode = NeededShift;
     return true;
   };
   // op0 must be either the needed shift opcode or the mul/udiv equivalent
   // that the needed shift can be extracted from.
   if ((OppShift.getOpcode() != ISD::SRL || !SelectOpcode(ISD::SHL, ISD::MUL)) &&
       (OppShift.getOpcode() != ISD::SHL || !SelectOpcode(ISD::SRL, ISD::UDIV)))
     return SDValue();
 
   // op0 must be the same opcode on both sides, have the same LHS argument,
   // and produce the same value type.
-  SDValue OppShiftLHS = OppShift.getOperand(0);
-  EVT ShiftedVT = OppShiftLHS.getValueType();
   if (OppShiftLHS.getOpcode() != ExtractFrom.getOpcode() ||
       OppShiftLHS.getOperand(0) != ExtractFrom.getOperand(0) ||
       ShiftedVT != ExtractFrom.getValueType())
     return SDValue();
 
-  // Amount of the existing shift.
-  ConstantSDNode *OppShiftCst = isConstOrConstSplat(OppShift.getOperand(1));
   // Constant mul/udiv/shift amount from the RHS of the shift's LHS op.
   ConstantSDNode *OppLHSCst = isConstOrConstSplat(OppShiftLHS.getOperand(1));
   // Constant mul/udiv/shift amount from the RHS of the ExtractFrom op.
   ConstantSDNode *ExtractFromCst =
       isConstOrConstSplat(ExtractFrom.getOperand(1));
   // TODO: We should be able to handle non-uniform constant vectors for these values
   // Check that we have constant values.
   if (!OppShiftCst || !OppShiftCst->getAPIntValue() ||
       !OppLHSCst || !OppLHSCst->getAPIntValue() ||
       !ExtractFromCst || !ExtractFromCst->getAPIntValue())
     return SDValue();
 
   // Compute the shift amount we need to extract to complete the rotate.
   const unsigned VTWidth = ShiftedVT.getScalarSizeInBits();
   if (OppShiftCst->getAPIntValue().ugt(VTWidth))
     return SDValue();
   APInt NeededShiftAmt = VTWidth - OppShiftCst->getAPIntValue();
   // Normalize the bitwidth of the two mul/udiv/shift constant operands.
   APInt ExtractFromAmt = ExtractFromCst->getAPIntValue();
   APInt OppLHSAmt = OppLHSCst->getAPIntValue();
   zeroExtendToMatch(ExtractFromAmt, OppLHSAmt);
 
   // Now try extract the needed shift from the ExtractFrom op and see if the
   // result matches up with the existing shift's LHS op.
   if (IsMulOrDiv) {
     // Op to extract from is a mul or udiv by a constant.
     // Check:
     //     c2 / (1 << (bitwidth(op0 v c0) - c1)) == c0
     //     c2 % (1 << (bitwidth(op0 v c0) - c1)) == 0
     const APInt ExtractDiv = APInt::getOneBitSet(ExtractFromAmt.getBitWidth(),
                                                  NeededShiftAmt.getZExtValue());
     APInt ResultAmt;
     APInt Rem;
     APInt::udivrem(ExtractFromAmt, ExtractDiv, ResultAmt, Rem);
     if (Rem != 0 || ResultAmt != OppLHSAmt)
       return SDValue();
   } else {
     // Op to extract from is a shift by a constant.
     // Check:
     //      c2 - (bitwidth(op0 v c0) - c1) == c0
     if (OppLHSAmt != ExtractFromAmt - NeededShiftAmt.zextOrTrunc(
                                           ExtractFromAmt.getBitWidth()))
       return SDValue();
   }
 
   // Return the expanded shift op that should allow a rotate to be formed.
   EVT ShiftVT = OppShift.getOperand(1).getValueType();
   EVT ResVT = ExtractFrom.getValueType();
   SDValue NewShiftNode = DAG.getConstant(NeededShiftAmt, DL, ShiftVT);
   return DAG.getNode(Opcode, DL, ResVT, OppShiftLHS, NewShiftNode);
 }
 
 // Return true if we can prove that, whenever Neg and Pos are both in the
 // 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))
 //

test/CodeGen/X86/rotate-extract-vector.ll

; X64-NEXT:    retq
   %out = or <2 x i64> %lhs_shift, %rhs_div
   ret <2 x i64> %out
 }
 
 ; DAGCombiner transforms shl X, 1 into add X, X.
 define <4 x i32> @extract_add_1(<4 x i32> %i) nounwind {
 ; CHECK-LABEL: extract_add_1:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    vpaddd %xmm0, %xmm0, %xmm1
-; CHECK-NEXT:    vpsrld $31, %xmm0, %xmm0
-; CHECK-NEXT:    vpor %xmm0, %xmm1, %xmm0
+; CHECK-NEXT:    # kill: def $xmm0 killed $xmm0 def $zmm0
+; CHECK-NEXT:    vprold $1, %zmm0, %zmm0
+; CHECK-NEXT:    # kill: def $xmm0 killed $xmm0 killed $zmm0
+; CHECK-NEXT:    vzeroupper
 ; CHECK-NEXT:    ret{{[l|q]}}
   %ii = add <4 x i32> %i, %i
   %rhs = lshr <4 x i32> %i, <i32 31, i32 31, i32 31, i32 31>
   %out = or <4 x i32> %ii, %rhs
   ret <4 x i32> %out
 }
 
 define <4 x i32> @extract_add_1_comut(<4 x i32> %i) nounwind {
 ; CHECK-LABEL: extract_add_1_comut:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    vpaddd %xmm0, %xmm0, %xmm1
-; CHECK-NEXT:    vpsrld $31, %xmm0, %xmm0
-; CHECK-NEXT:    vpor %xmm1, %xmm0, %xmm0
+; CHECK-NEXT:    # kill: def $xmm0 killed $xmm0 def $zmm0
+; CHECK-NEXT:    vprold $1, %zmm0, %zmm0
+; CHECK-NEXT:    # kill: def $xmm0 killed $xmm0 killed $zmm0
+; CHECK-NEXT:    vzeroupper
 ; CHECK-NEXT:    ret{{[l|q]}}
   %ii = add <4 x i32> %i, %i
   %lhs = lshr <4 x i32> %i, <i32 31, i32 31, i32 31, i32 31>
   %out = or <4 x i32> %lhs, %ii
   ret <4 x i32> %out
 }
 
 define <4 x i32> @no_extract_add_1(<4 x i32> %i) nounwind {

test/CodeGen/X86/rotate-extract.ll

; X64-NEXT:    retq
   %out = or i8 %lhs_shift, %rhs_div
   ret i8 %out
 }
 
 ; DAGCombiner transforms shl X, 1 into add X, X.
 define i32 @extract_add_1(i32 %i) nounwind {
 ; X86-LABEL: extract_add_1:
 ; X86:       # %bb.0:
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    leal (%ecx,%ecx), %eax
-; X86-NEXT:    shrl $31, %ecx
-; X86-NEXT:    orl %ecx, %eax
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    roll %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: extract_add_1:
 ; X64:       # %bb.0:
-; X64-NEXT:    # kill: def $edi killed $edi def $rdi
-; X64-NEXT:    leal (%rdi,%rdi), %eax
-; X64-NEXT:    shrl $31, %edi
-; X64-NEXT:    orl %edi, %eax
+; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    roll %eax
 ; X64-NEXT:    retq
   %ii = add i32 %i, %i
   %rhs = lshr i32 %i, 31
   %out = or i32 %ii, %rhs
   ret i32 %out
 }
 
 define i32 @extract_add_1_comut(i32 %i) nounwind {
 ; X86-LABEL: extract_add_1_comut:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    leal (%eax,%eax), %ecx
-; X86-NEXT:    shrl $31, %eax
-; X86-NEXT:    orl %ecx, %eax
+; X86-NEXT:    roll %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: extract_add_1_comut:
 ; X64:       # %bb.0:
-; X64-NEXT:    # kill: def $edi killed $edi def $rdi
-; X64-NEXT:    leal (%rdi,%rdi), %eax
-; X64-NEXT:    shrl $31, %edi
-; X64-NEXT:    orl %edi, %eax
+; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    roll %eax
 ; X64-NEXT:    retq
   %ii = add i32 %i, %i
   %lhs = lshr i32 %i, 31
   %out = or i32 %lhs, %ii
   ret i32 %out
 }
 
 define i32 @no_extract_add_1(i32 %i) nounwind {