[DAGCombine] Match a greater range of rotate when not all bits are demanded.

[deadalnix]

Summary

Only match trunc for now, as integrating into the SimplifyDemandedBits proved to be a significant challenge.

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

548

The change to returning SDValue looks like an NFC that you can do right away?

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

548

I can do that, indeed. Let me land this part and rebase.

[deadalnix]

Rebase on top of NFC changes

[RKSimon]

vector tests?

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

6135

Shouldn't this be: APInt::getMaxValue(LHS.getScalarValueSizeInBits()) ?

TBH I'd prefer getAllOnesValue as well as it avoids the signed/unsigned ambiguity of getMaxValue.

6234

isSubsetOf ?

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

6135

That wouldn't generate the proper pattern for vectors and would leave things such as only the last element is demanded.

[deadalnix]

Add test for vector - but nothing changes for them (see rL374043 ) and use isSubsetOf and getAllOnesValue.

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

6226

Use getLimitedValue()

6230–6235

I don't understand the logic here.
This might need some comments.

6233

Should this use getAllOnesValue() directly?

6240–6243

Precommit.

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

private:
     SDValue MatchBSwapHWordLow(SDNode *N, SDValue N0, SDValue N1,
                                bool DemandHighBits = true);
     SDValue MatchBSwapHWord(SDNode *N, SDValue N0, SDValue N1);
     SDValue MatchRotatePosNeg(SDValue Shifted, SDValue Pos, SDValue Neg,
                               SDValue InnerPos, SDValue InnerNeg,
                               unsigned PosOpcode, unsigned NegOpcode,
                               const SDLoc &DL);
     SDValue MatchRotate(SDValue LHS, SDValue RHS, const SDLoc &DL);
+    SDValue MatchRotate(SDValue LHS, SDValue RHS, const SDLoc &DL,
+                        const APInt &DemandedBits);
     SDValue MatchLoadCombine(SDNode *N);
     SDValue MatchStoreCombine(StoreSDNode *N);
     SDValue ReduceLoadWidth(SDNode *N);
     SDValue ReduceLoadOpStoreWidth(SDNode *N);
     SDValue splitMergedValStore(StoreSDNode *ST);
     SDValue TransformFPLoadStorePair(SDNode *N);
     SDValue convertBuildVecZextToZext(SDNode *N);
     SDValue reduceBuildVecExtToExtBuildVec(SDNode *N);
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);
   }
 
   return SDValue();
 }
 
+SDValue DAGCombiner::MatchRotate(SDValue LHS, SDValue RHS, const SDLoc &DL) {
+  return MatchRotate(
+      LHS, RHS, DL, APInt::getAllOnesValue(LHS.getValueType().getSizeInBits()));
+}
+
 // MatchRotate - Handle an 'or' of two operands.  If this is one of the many
 // idioms for rotate, and if the target supports rotation instructions, generate
 // a rot[lr].
-SDValue DAGCombiner::MatchRotate(SDValue LHS, SDValue RHS, const SDLoc &DL) {
+SDValue DAGCombiner::MatchRotate(SDValue LHS, SDValue RHS, const SDLoc &DL,
+                                 const APInt &DemandedBits) {
   // Must be a legal type.  Expanded 'n promoted things won't work with rotates.
   EVT VT = LHS.getValueType();
   if (!TLI.isTypeLegal(VT))
     return SDValue();
 
   // The target must have at least one rotate flavor.
   bool HasROTL = hasOperation(ISD::ROTL, VT);
   bool HasROTR = hasOperation(ISD::ROTR, VT);
SDValue DAGCombiner::MatchRotate(SDValue LHS, SDValue RHS, const SDLoc &DL,
 
   // Canonicalize shl to left side in a shl/srl pair.
   if (RHSShift.getOpcode() == ISD::SHL) {
     std::swap(LHS, RHS);
     std::swap(LHSShift, RHSShift);
     std::swap(LHSMask, RHSMask);
   }
 
-  unsigned EltSizeInBits = VT.getScalarSizeInBits();
   SDValue LHSShiftArg = LHSShift.getOperand(0);
   SDValue LHSShiftAmt = LHSShift.getOperand(1);
   SDValue RHSShiftArg = RHSShift.getOperand(0);
   SDValue RHSShiftAmt = RHSShift.getOperand(1);
 
+  EVT RotVT = VT;
+
   // fold (or (shl x, C1), (srl x, C2)) -> (rotl x, C1)
   // fold (or (shl x, C1), (srl x, C2)) -> (rotr x, C2)
-  auto MatchRotateSum = [EltSizeInBits](ConstantSDNode *LHS,
+  auto MatchRotateSum = [this, &DemandedBits, &RotVT](ConstantSDNode *LHS,
                                                       ConstantSDNode *RHS) {
-    return (LHS->getAPIntValue() + RHS->getAPIntValue()) == EltSizeInBits;
+    uint64_t RotAmount =
+        (LHS->getAPIntValue() + RHS->getAPIntValue()).getZExtValue();
+    // For vectors, only allow exact match.
+    if (RotVT.isVector())
+      return RotAmount == RotVT.getScalarSizeInBits();
+    // For scalar, check that the type we use for rotation cover all demanded
+    // bits and is legal.
+    APInt RotMask =
+        APInt::getMaxValue(RotAmount).zextOrTrunc(DemandedBits.getBitWidth());
+    if (!DemandedBits.isSubsetOf(RotMask))
+      return false;
+    RotVT = EVT::getIntegerVT(*DAG.getContext(), RotAmount);
+    return TLI.isTypeLegal(RotVT);
   };
   if (ISD::matchBinaryPredicate(LHSShiftAmt, RHSShiftAmt, MatchRotateSum)) {
-    SDValue Rot = DAG.getNode(HasROTL ? ISD::ROTL : ISD::ROTR, DL, VT,
-                              LHSShiftArg, HasROTL ? LHSShiftAmt : RHSShiftAmt);
+    HasROTL = hasOperation(ISD::ROTL, RotVT);
+    HasROTR = hasOperation(ISD::ROTR, RotVT);
+    if (!HasROTL && !HasROTR)
+      return SDValue();
+
+    SDValue Rotated = DAG.getZExtOrTrunc(LHSShiftArg, DL, RotVT);
+    SDValue Rot = DAG.getNode(HasROTL ? ISD::ROTL : ISD::ROTR, DL, RotVT,
+                              Rotated, HasROTL ? LHSShiftAmt : RHSShiftAmt);
+    Rot = DAG.getAnyExtOrTrunc(Rot, DL, VT);
 
     // If there is an AND of either shifted operand, apply it to the result.
     if (LHSMask.getNode() || RHSMask.getNode()) {
       SDValue AllOnes = DAG.getAllOnesConstant(DL, VT);
       SDValue Mask = AllOnes;
 
       if (LHSMask.getNode()) {
         SDValue RHSBits = DAG.getNode(ISD::SRL, DL, VT, AllOnes, RHSShiftAmt);
SDValue DAGCombiner::visitTRUNCATE(SDNode *N) {
   if (SDValue NewVSel = matchVSelectOpSizesWithSetCC(N))
     return NewVSel;
 
   // Narrow a suitable binary operation with a non-opaque constant operand by
   // moving it ahead of the truncate. This is limited to pre-legalization
   // because targets may prefer a wider type during later combines and invert
   // this transform.
   switch (N0.getOpcode()) {
+  case ISD::OR: {
+    // TODO: This would idealy be part of the SimplifyDemandedBits mechanic, but
+    // there are no way to easily plug it in at the moment, so it is limited to
+    // TRUNC.
+    SDLoc DL(N);
+    if (SDValue Rot = MatchRotate(N0.getOperand(0), N0.getOperand(1), DL,
+                                  APInt::getMaxValue(VT.getSizeInBits())))
+      return DAG.getNode(ISD::TRUNCATE, DL, VT, Rot);
+    LLVM_FALLTHROUGH;
+  }
   case ISD::ADD:
   case ISD::SUB:
   case ISD::MUL:
   case ISD::AND:
-  case ISD::OR:
   case ISD::XOR:
     if (!LegalOperations && N0.hasOneUse() &&
         (isConstantOrConstantVector(N0.getOperand(0), true) ||
          isConstantOrConstantVector(N0.getOperand(1), true))) {
       // TODO: We already restricted this to pre-legalization, but for vectors
       // we are extra cautious to not create an unsupported operation.
       // Target-specific changes are likely needed to avoid regressions here.
       if (VT.isScalarInteger() || TLI.isOperationLegal(N0.getOpcode(), VT)) {

test/CodeGen/X86/rot16.ll

; X64-NEXT:    retq
   %t2 = or i32 %t0, %t1
   %t3 = and i32 %t2, 65535
   ret i32 %t3
 }
 
 define i16 @rot16_trunc(i32 %x, i32 %y) nounwind {
 ; X32-LABEL: rot16_trunc:
 ; X32:       # %bb.0:
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X32-NEXT:    movl %eax, %ecx
-; X32-NEXT:    shrl $11, %ecx
-; X32-NEXT:    shll $5, %eax
-; X32-NEXT:    orl %ecx, %eax
-; X32-NEXT:    # kill: def $ax killed $ax killed $eax
+; X32-NEXT:    movzwl {{[0-9]+}}(%esp), %eax
+; X32-NEXT:    rolw $5, %ax
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: rot16_trunc:
 ; X64:       # %bb.0:
 ; X64-NEXT:    movl %edi, %eax
-; X64-NEXT:    movl %edi, %ecx
-; X64-NEXT:    shrl $11, %ecx
-; X64-NEXT:    shll $5, %eax
-; X64-NEXT:    orl %ecx, %eax
+; X64-NEXT:    rolw $5, %ax
 ; X64-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X64-NEXT:    retq
   %t0 = lshr i32 %x, 11
   %t1 = shl i32 %x, 5
   %t2 = or i32 %t0, %t1
   %t3 = trunc i32 %t2 to i16
   ret i16 %t3
 }