[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

6033

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

6111

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

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

6111

The whole function is about reconstructing shifts from something else.

[RKSimon]

LGTM - cheers!

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

6111

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

6111

But this code DOES build a shift node.

6136

This is where the shift node is built.

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

6136

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

6136

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

 /// Match "(X shl/srl V1) & V2" where V2 may not be present.
 static bool matchRotateHalf(SelectionDAG &DAG, SDValue Op, SDValue &Shift,
                             SDValue &Mask) {
   Op = stripConstantMask(DAG, Op, Mask);
   if (Op.getOpcode() == ISD::SRL || Op.getOpcode() == ISD::SHL) {
     Shift = Op;
     return true;
   }
+  if (Op.getOpcode() == ISD::ADD && Op.getOperand(0) == Op.getOperand(1)) {
+    SDLoc DL(Op);
+    EVT VT = Op.getValueType();
+    Shift = DAG.getNode(ISD::SHL, DL, VT, Op.getOperand(0),
+                        DAG.getShiftAmountConstant(1, VT, DL));
+    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 (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)
 ///
static SDValue extractShiftForRotate(SelectionDAG &DAG, SDValue OppShift,
   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
 }

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
 }