[SelectionDAG] Provide default expansion for rotates

[kparzysz]

Summary

Implement default legalization of rotates: either in terms of the rotation in the opposite direction (if legal), or in terms of shifts and ors.

Implement generating of rotate instructions for Hexagon. Hexagon only supports rotates by an immediate value, so implement custom lowering of ROTL/ROTR on Hexagon. If a rotate is not legal, use the default expansion.

[efriedma]

Please split ReassociateOrForRotate into a separate patch; it's conceptually separate and likely to affect other targets.

lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

3929

This lowering is wrong (consider c==0, c==64). Maybe (or (shl x, (and c, w-1), (srl x, (and (sub 0, c), w-1)) instead?

[kparzysz]

Removed the rotation generation from this patch, applied Eli's suggestions.

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5079

This might be useful as general helper function - add it to the DAGCombiner class for reuse?

lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

3912

Use OpVT.getScalarSizeInBits() - hopefully we might be able to use this for vector cases as well at some point soon.

3918

Move the Sub = DAG.getNode into the if() case? I don't think its used anywhere else.

lib/Target/Hexagon/HexagonISelLowering.cpp

1359

Is this relevant to rotation support?

1363

Is this relevant to rotation support?

2099

I don't think you need the getNode() here

[kparzysz]

lib/Target/Hexagon/HexagonISelLowering.cpp

2099

I try to keep the SDValue->SDNode conversions explicit in general.

[kparzysz]

Applied Simon's comments.

[RKSimon]

lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

3924

Is there any way that we can get here with a bit width that isn't power-of-two? In which case we'd have to adjust this and use UREM not AND........

[kparzysz]

Replaced (and x, w-1) with (urem x, w).

[kparzysz]

Remove incorrect assertion that was added in the previous patch. The version with urem works for non-power-of-2 as well.

[efriedma]

Currently it's impossible to reach LegalizeDAG with an integer that isn't a power of two (only power-of-two integers can be specified as legal types), but I guess it's better to future-proof.

I like to see a test with explicit CHECK lines for the assembly generated using the legalization in SelectionDAGLegalize::ExpandNode, so we'll know if something changes.

[kparzysz]

Turns out the UREM approach has a downside: the UREM is legalized before it gets to the combiner, so on architectures that don't have div/mod, it will be expanded into a libcall. I'm going to change it back to an AND.

The testcase rotate.ll already has a couple of cases where the expansion takes place (f1, f3, f5, and f7), but now it only checks that there was no rotate used. I can add check for the actual assembly.

[kparzysz]

Using UREM ended up calling runtime functions (since UREM is a libcall on Hexagon), so I switched it back to using AND. Eli's comment confirms that only types that are power-of-2 bits wide can exist at this point.

Per Eli's request, expanded the testcase to include checks for the actual expansion code.

[efriedma]

test/CodeGen/Hexagon/rotate.ll

108

This looks correct, but low quality. Trunk generates 3 instructions, the ideal rotate expansion would generate 5 instructions (I think), this is 6 instructions.

[kparzysz]

Removed a redundant AND from rotate expansion.

[RKSimon]

LGTM @efriedma any more comments?

[efriedma]

The AND you removed wasn't redundant: 32-0 is 32, not 0.

[efriedma]

(When I said there was a redundant operation, I was referring to the second SUB.)

[kparzysz]

In D47725#1126768, @efriedma wrote:

(When I said there was a redundant operation, I was referring to the second SUB.)

Yeah, the first sub came from ROTR->ROTL conversion, so it was actually 5 instructions for the ROTL alone. I think we should be able to optimize it further on targets where large shift amounts generate 0 (in DAG combiner?).

[kparzysz]

It's now 5 instructions everywhere, and the and is back.

[efriedma]

Hmm... yes, I guess the AND isn't necessary if the shift produces either zero or the input, which is true for every target I can think of. But (SHL x, 32) is defined to produce undef for a 32-bit input, not some target-specific result, so you can't depend on that. Might make sense to add a dedicated target-independent opcode to represent it.

[efriedma]

LGTM

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

private:
     SDValue buildSqrtEstimateImpl(SDValue Op, SDNodeFlags Flags, bool Recip);
     SDValue buildSqrtNROneConst(SDValue Op, SDValue Est, unsigned Iterations,
                                 SDNodeFlags Flags, bool Reciprocal);
     SDValue buildSqrtNRTwoConst(SDValue Op, SDValue Est, unsigned Iterations,
                                 SDNodeFlags Flags, bool Reciprocal);
     SDValue MatchBSwapHWordLow(SDNode *N, SDValue N0, SDValue N1,
                                bool DemandHighBits = true);
     SDValue MatchBSwapHWord(SDNode *N, SDValue N0, SDValue N1);
+    SDNode *ReassociateOrForRotate(SDValue Op0, SDValue Op1, const SDLoc &dl);
     SDNode *MatchRotatePosNeg(SDValue Shifted, SDValue Pos, SDValue Neg,
                               SDValue InnerPos, SDValue InnerNeg,
                               unsigned PosOpcode, unsigned NegOpcode,
                               const SDLoc &DL);
     SDNode *MatchRotate(SDValue LHS, SDValue RHS, const SDLoc &DL);
     SDValue MatchLoadCombine(SDNode *N);
     SDValue ReduceLoadWidth(SDNode *N);
     SDValue ReduceLoadOpStoreWidth(SDNode *N);
SDValue DAGCombiner::visitOR(SDNode *N) {
   // Simplify: (or (op x...), (op y...))  -> (op (or x, y))
   if (N0.getOpcode() == N1.getOpcode())
     if (SDValue Tmp = SimplifyBinOpWithSameOpcodeHands(N))
       return Tmp;
 
   // See if this is some rotate idiom.
   if (SDNode *Rot = MatchRotate(N0, N1, SDLoc(N)))
     return SDValue(Rot, 0);
+  // If N0 or N1 are themselves ORs, there is still a potential for a rotate
+  // whose parts got reassociated with some other stuff.
+  if (N0.getOpcode() == ISD::OR || N1.getOpcode() == ISD::OR)
+    if (SDNode *Or = ReassociateOrForRotate(N0, N1, SDLoc(N)))
+      return SDValue(Or, 0);
 
   if (SDValue Load = MatchLoadCombine(N))
     return Load;
 
   // Simplify the operands using demanded-bits information.
   if (SimplifyDemandedBits(SDValue(N, 0)))
     return SDValue(N, 0);
 
   return SDValue();
 }
 
+SDNode *DAGCombiner::ReassociateOrForRotate(SDValue Op0, SDValue Op1,
+                                            const SDLoc &dl) {
+  EVT VT = Op0.getValueType();
+  if (LegalOperations && !TLI.isOperationLegal(ISD::ROTL, VT) &&
+                         !TLI.isOperationLegal(ISD::ROTR, VT))
+    return nullptr;
+  if (!LegalOperations && !TLI.isOperationLegalOrCustom(ISD::ROTL, VT) &&
+                          !TLI.isOperationLegalOrCustom(ISD::ROTR, VT))
+    return nullptr;
+
+  // Expand all single-use ORs into a list (OredOps).
+  SmallVector<SDValue,8> WorkQ = { Op0, Op1 };
+  SmallVector<SDValue,8> OredOps;
+  for (unsigned i = 0; i != WorkQ.size(); ++i) {
+    SDValue V = WorkQ[i];
+    if (V.getOpcode() == ISD::OR && V.hasOneUse()) {
+      WorkQ.push_back(V.getOperand(0));
+      WorkQ.push_back(V.getOperand(1));
+    } else
+      OredOps.push_back(V);
+  }
+
+  // Sort the ORed values with respect to the opcodes. This is to isolate
+  // the SHL operations into one contiguous block and same for SRL.
+  auto OpcOrder = [](SDValue A, SDValue B) {
+    // SHL < SRL < ...
+    unsigned OA = A.getOpcode(), OB = B.getOpcode();
+    if (OA == ISD::SHL)
+      return true;
+    if (OB == ISD::SHL)
+      return false;
+    if (OA == ISD::SRL)
+      return true;
+    if (OB == ISD::SRL)
+      return false;
+    return OA < OB;
+  };
+  std::stable_sort(OredOps.begin(), OredOps.end(), OpcOrder);
+
+  // Find the number of SHLs and SRLs.
+  auto TmpL = find_if(OredOps,
+                      [](SDValue V) { return V.getOpcode() != ISD::SHL; });
+  unsigned LeftCount = std::distance(OredOps.begin(), TmpL);
+  auto TmpR = find_if(make_range(OredOps.begin()+LeftCount, OredOps.end()),
+                      [](SDValue V) { return V.getOpcode() != ISD::SRL; });
+  unsigned TotalCount = std::distance(OredOps.begin(), TmpR);
+
+  // If there is at least one left and right shift, do pairwise matching.
+  if (LeftCount == 0 || LeftCount == TotalCount)
+    return nullptr;
+
+  bool CreatedRotate = false;
+  for (unsigned L = 0; L != LeftCount; ++L) {
+    for (unsigned R = LeftCount; R != TotalCount; ++R) {
+      if (!OredOps[R])
+        continue;
+      // If a rotate was generated, nullify original pieces and append
+      // the rotate to the list.
+      if (SDNode *T = MatchRotate(OredOps[L], OredOps[R], dl)) {
+        OredOps.push_back(SDValue(T, 0));
+        OredOps[L] = OredOps[R] = SDValue();
+        CreatedRotate = true;
+        break;
+      }
+    }
+  }
+
+  // All pairs of left-right shifts have been examined. Now, re-package
+  // the values back into an OR tree.
+  if (!CreatedRotate)
+    return nullptr;
+
+  auto OredEnd = remove_if(OredOps, [](SDValue V) { return !bool(V); });
+  unsigned Size = OredEnd - OredOps.begin();
+  while (Size != 1) {
+    for (unsigned i = 0; i != Size/2; ++i)
+      OredOps[i] = DAG.getNode(ISD::OR, dl, VT, OredOps[2*i], OredOps[2*i+1]);
+    if (Size % 2 != 0) {
+      OredOps[Size/2+1] = OredOps[Size-1];
+      Size = Size/2 + 1;
+    } else
+      Size /= 2;
+  }
+
+  // The last remaining op is the root.
+  return OredOps[0].getNode();
+}
+
 /// Match "(X shl/srl V1) & V2" where V2 may not be present.
 bool DAGCombiner::MatchRotateHalf(SDValue Op, SDValue &Shift, SDValue &Mask) {
   if (Op.getOpcode() == ISD::AND) {
     if (DAG.isConstantIntBuildVectorOrConstantInt(Op.getOperand(1))) {
       Mask = Op.getOperand(1);
       Op = Op.getOperand(0);
     } else {
       return false;

 // idioms for rotate, and if the target supports rotation instructions, generate
 // a rot[lr].
 SDNode *DAGCombiner::MatchRotate(SDValue LHS, SDValue RHS, const SDLoc &DL) {
   // Must be a legal type.  Expanded 'n promoted things won't work with rotates.
   EVT VT = LHS.getValueType();
   if (!TLI.isTypeLegal(VT)) return nullptr;
 
   // The target must have at least one rotate flavor.
-  bool HasROTL = TLI.isOperationLegalOrCustom(ISD::ROTL, VT);
-  bool HasROTR = TLI.isOperationLegalOrCustom(ISD::ROTR, VT);
+  auto HasOperation = [this] (unsigned Opc, EVT T) {
+    if (LegalOperations)
+      return TLI.isOperationLegal(Opc, T);
+    return TLI.isOperationLegalOrCustom(Opc, T);
+  };
+  bool HasROTL = HasOperation(ISD::ROTL, VT);
+  bool HasROTR = HasOperation(ISD::ROTR, VT);
   if (!HasROTL && !HasROTR) return nullptr;
 
   // Check for truncated rotate.
   if (LHS.getOpcode() == ISD::TRUNCATE && RHS.getOpcode() == ISD::TRUNCATE &&
       LHS.getOperand(0).getValueType() == RHS.getOperand(0).getValueType()) {
     assert(LHS.getValueType() == RHS.getValueType());
     if (SDNode *Rot = MatchRotate(LHS.getOperand(0), RHS.getOperand(0), DL)) {
       return DAG.getNode(ISD::TRUNCATE, SDLoc(LHS), LHS.getValueType(),

lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

for (unsigned Idx = 0; Idx < NumElem; Idx++) {
       Scalars.push_back(DAG.getNode(Node->getOpcode(), dl,
                                     VT.getScalarType(), Ex, Sh));
     }
 
     SDValue Result = DAG.getBuildVector(Node->getValueType(0), dl, Scalars);
     ReplaceNode(SDValue(Node, 0), Result);
     break;
   }
+  case ISD::ROTL:
+  case ISD::ROTR: {
+    bool IsLeft = Node->getOpcode() == ISD::ROTL;
+    SDValue Op0 = Node->getOperand(0), Op1 = Node->getOperand(1);
+    EVT ResVT = Node->getValueType(0);
+    EVT OpVT = Op0.getValueType();
+    assert(OpVT == ResVT &&
+           "The result and the operand types of rotate should match");
+    EVT ShVT = Op1.getValueType();
+    SDValue Width = DAG.getConstant(OpVT.getSizeInBits(), dl, ShVT);
+    SDValue Sub = DAG.getNode(ISD::SUB, dl, ShVT, Width, Op1);
+
+    // If a rotate in the other direction is legal, use it.
+    unsigned RevRot = IsLeft ? ISD::ROTR : ISD::ROTL;
+    if (TLI.isOperationLegal(RevRot, ResVT)) {
+      Results.push_back(DAG.getNode(RevRot, dl, ResVT, Op0, Sub));
+      break;
+    }
+
+    // Otherwise, (rotl x, c) -> (or (shl x, c), (srl x, w-c))
+    //            (rotr x, c) -> (or (srl x, c), (shl x, w-c))
+    //
+    unsigned ShOpc = IsLeft ? ISD::SHL : ISD::SRL;
+    unsigned HsOpc = IsLeft ? ISD::SRL : ISD::SHL;
+    SDValue Or = DAG.getNode(ISD::OR, dl, ResVT,
+                             DAG.getNode(ShOpc, dl, ResVT, Op0, Op1),
+                             DAG.getNode(HsOpc, dl, ResVT, Op0, Sub));
+    Results.push_back(Or);
+    break;
+  }
+
   case ISD::GLOBAL_OFFSET_TABLE:
   case ISD::GlobalAddress:
   case ISD::GlobalTLSAddress:
   case ISD::ExternalSymbol:
   case ISD::ConstantPool:
   case ISD::JumpTable:
   case ISD::INTRINSIC_W_CHAIN:
   case ISD::INTRINSIC_WO_CHAIN:

lib/Target/Hexagon/HexagonISelLowering.h

public:
     SDValue LowerBUILD_VECTOR(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerCONCAT_VECTORS(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerEXTRACT_VECTOR_ELT(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerEXTRACT_SUBVECTOR(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerINSERT_VECTOR_ELT(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerINSERT_SUBVECTOR(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerVECTOR_SHUFFLE(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerVECTOR_SHIFT(SDValue Op, SelectionDAG &DAG) const;
+    SDValue LowerROTL(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerBITCAST(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerANY_EXTEND(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerSIGN_EXTEND(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerZERO_EXTEND(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerUnalignedLoad(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerAddSubCarry(SDValue Op, SelectionDAG &DAG) const;
 
     SDValue LowerDYNAMIC_STACKALLOC(SDValue Op, SelectionDAG &DAG) const;

lib/Target/Hexagon/HexagonISelLowering.cpp

HexagonTargetLowering::HexagonTargetLowering(const TargetMachine &TM,
   setOperationAction(ISD::CTPOP, MVT::i16, Promote);
   setOperationAction(ISD::CTPOP, MVT::i32, Promote);
   setOperationAction(ISD::CTPOP, MVT::i64, Legal);
 
   setOperationAction(ISD::BITREVERSE, MVT::i32, Legal);
   setOperationAction(ISD::BITREVERSE, MVT::i64, Legal);
   setOperationAction(ISD::BSWAP, MVT::i32, Legal);
   setOperationAction(ISD::BSWAP, MVT::i64, Legal);
-  setOperationAction(ISD::MUL,   MVT::i64, Legal);
 
   for (unsigned IntExpOp :
        { ISD::SDIV,      ISD::UDIV,      ISD::SREM,      ISD::UREM,
-         ISD::SDIVREM,   ISD::UDIVREM,   ISD::ROTL,      ISD::ROTR,
-         ISD::SHL_PARTS, ISD::SRA_PARTS, ISD::SRL_PARTS,
-         ISD::SMUL_LOHI, ISD::UMUL_LOHI }) {
-    setOperationAction(IntExpOp, MVT::i32, Expand);
-    setOperationAction(IntExpOp, MVT::i64, Expand);
+         ISD::SDIVREM,   ISD::UDIVREM,   ISD::ROTR,      ISD::SHL_PARTS,
+         ISD::SRA_PARTS, ISD::SRL_PARTS, ISD::SMUL_LOHI, ISD::UMUL_LOHI }) {
+    for (MVT VT : MVT::integer_valuetypes())
+      setOperationAction(IntExpOp, VT, Expand);
   }
 
   for (unsigned FPExpOp :
        {ISD::FDIV, ISD::FREM, ISD::FSQRT, ISD::FSIN, ISD::FCOS, ISD::FSINCOS,
         ISD::FPOW, ISD::FCOPYSIGN}) {
     setOperationAction(FPExpOp, MVT::f32, Expand);
     setOperationAction(FPExpOp, MVT::f64, Expand);
   }
HexagonTargetLowering::HexagonTargetLowering(const TargetMachine &TM,
   setOperationAction(ISD::SETCC,          MVT::v2i16, Custom);
   setOperationAction(ISD::VSELECT,        MVT::v2i16, Custom);
   setOperationAction(ISD::VECTOR_SHUFFLE, MVT::v4i8,  Custom);
   setOperationAction(ISD::VECTOR_SHUFFLE, MVT::v4i16, Custom);
   setOperationAction(ISD::VECTOR_SHUFFLE, MVT::v8i8,  Custom);
 
   // Subtarget-specific operation actions.
   //
+  if (Subtarget.hasV60TOps()) {
+    setOperationAction(ISD::ROTL, MVT::i32, Custom);
+    setOperationAction(ISD::ROTL, MVT::i64, Custom);
+  }
   if (Subtarget.hasV5TOps()) {
     setOperationAction(ISD::FMA,  MVT::f64, Expand);
     setOperationAction(ISD::FADD, MVT::f64, Expand);
     setOperationAction(ISD::FSUB, MVT::f64, Expand);
     setOperationAction(ISD::FMUL, MVT::f64, Expand);
 
     setOperationAction(ISD::FMINNUM, MVT::f32, Legal);
     setOperationAction(ISD::FMAXNUM, MVT::f32, Legal);

 }
 
 SDValue
 HexagonTargetLowering::LowerVECTOR_SHIFT(SDValue Op, SelectionDAG &DAG) const {
   return getVectorShiftByInt(Op, DAG);
 }
 
 SDValue
+HexagonTargetLowering::LowerROTL(SDValue Op, SelectionDAG &DAG) const {
+  if (isa<ConstantSDNode>(Op.getOperand(1).getNode()))
+    return Op;
+  return SDValue();
+}
+
+SDValue
 HexagonTargetLowering::LowerBITCAST(SDValue Op, SelectionDAG &DAG) const {
   MVT ResTy = ty(Op);
   SDValue InpV = Op.getOperand(0);
   MVT InpTy = ty(InpV);
   assert(ResTy.getSizeInBits() == InpTy.getSizeInBits());
   const SDLoc &dl(Op);
 
   // Handle conversion from i8 to v8i1.
#endif
     case ISD::VECTOR_SHUFFLE:       return LowerVECTOR_SHUFFLE(Op, DAG);
     case ISD::BITCAST:              return LowerBITCAST(Op, DAG);
     case ISD::LOAD:                 return LowerUnalignedLoad(Op, DAG);
     case ISD::ADDCARRY:
     case ISD::SUBCARRY:             return LowerAddSubCarry(Op, DAG);
     case ISD::SRA:
     case ISD::SHL:
     case ISD::SRL:                  return LowerVECTOR_SHIFT(Op, DAG);
+    case ISD::ROTL:                 return LowerROTL(Op, DAG);
     case ISD::ConstantPool:         return LowerConstantPool(Op, DAG);
     case ISD::JumpTable:            return LowerJumpTable(Op, DAG);
     case ISD::EH_RETURN:            return LowerEH_RETURN(Op, DAG);
     case ISD::RETURNADDR:           return LowerRETURNADDR(Op, DAG);
     case ISD::FRAMEADDR:            return LowerFRAMEADDR(Op, DAG);
     case ISD::GlobalTLSAddress:     return LowerGlobalTLSAddress(Op, DAG);
     case ISD::ATOMIC_FENCE:         return LowerATOMIC_FENCE(Op, DAG);
     case ISD::GlobalAddress:        return LowerGLOBALADDRESS(Op, DAG);

lib/Target/Hexagon/HexagonPatterns.td

 }
 
 
 // Frags for commonly used SDNodes.
 def Add: pf2<add>;    def And: pf2<and>;    def Sra: pf2<sra>;
 def Sub: pf2<sub>;    def Or:  pf2<or>;     def Srl: pf2<srl>;
 def Mul: pf2<mul>;    def Xor: pf2<xor>;    def Shl: pf2<shl>;
 
+def Rol: pf2<rotl>;
 
 // --(1) Immediate -------------------------------------------------------
 //
 
 def SDTHexagonCONST32
   : SDTypeProfile<1, 1, [SDTCisVT<0, i32>, SDTCisVT<1, i32>, SDTCisPtrTy<0>]>;
 
 def HexagonJT:          SDNode<"HexagonISD::JT",          SDTIntUnaryOp>;

 
 def: OpR_RR_pat<S2_asr_r_r, Sra, i32, I32, I32>;
 def: OpR_RR_pat<S2_lsr_r_r, Srl, i32, I32, I32>;
 def: OpR_RR_pat<S2_asl_r_r, Shl, i32, I32, I32>;
 def: OpR_RR_pat<S2_asr_r_p, Sra, i64, I64, I32>;
 def: OpR_RR_pat<S2_lsr_r_p, Srl, i64, I64, I32>;
 def: OpR_RR_pat<S2_asl_r_p, Shl, i64, I64, I32>;
 
+let Predicates = [HasV60T] in {
+  def: OpR_RI_pat<S6_rol_i_r, Rol, i32, I32, u5_0ImmPred>;
+  def: OpR_RI_pat<S6_rol_i_p, Rol, i64, I64, u6_0ImmPred>;
+}
 
 def: Pat<(sra (add (sra I32:$Rs, u5_0ImmPred:$u5), 1), (i32 1)),
          (S2_asr_i_r_rnd I32:$Rs, imm:$u5)>;
 def: Pat<(sra (add (sra I64:$Rs, u6_0ImmPred:$u6), 1), (i32 1)),
          (S2_asr_i_p_rnd I64:$Rs, imm:$u6)>, Requires<[HasV5T]>;
 
 // Prefer S2_addasl_rrri over S2_asl_i_r_acc.
 let AddedComplexity = 120 in
let AddedComplexity = 100 in {
   def: AccRRI_pat<S2_asl_i_r_or,    Or,  Su<Shl>, I32, u5_0ImmPred>;
   def: AccRRI_pat<S2_asl_i_r_xacc,  Xor, Su<Shl>, I32, u5_0ImmPred>;
 
   def: AccRRI_pat<S2_asl_i_p_acc,   Add, Su<Shl>, I64, u6_0ImmPred>;
   def: AccRRI_pat<S2_asl_i_p_nac,   Sub, Su<Shl>, I64, u6_0ImmPred>;
   def: AccRRI_pat<S2_asl_i_p_and,   And, Su<Shl>, I64, u6_0ImmPred>;
   def: AccRRI_pat<S2_asl_i_p_or,    Or,  Su<Shl>, I64, u6_0ImmPred>;
   def: AccRRI_pat<S2_asl_i_p_xacc,  Xor, Su<Shl>, I64, u6_0ImmPred>;
+
+  let Predicates = [HasV60T] in {
+    def: AccRRI_pat<S6_rol_i_r_acc,   Add, Su<Rol>, I32, u5_0ImmPred>;
+    def: AccRRI_pat<S6_rol_i_r_nac,   Sub, Su<Rol>, I32, u5_0ImmPred>;
+    def: AccRRI_pat<S6_rol_i_r_and,   And, Su<Rol>, I32, u5_0ImmPred>;
+    def: AccRRI_pat<S6_rol_i_r_or,    Or,  Su<Rol>, I32, u5_0ImmPred>;
+    def: AccRRI_pat<S6_rol_i_r_xacc,  Xor, Su<Rol>, I32, u5_0ImmPred>;
+
+    def: AccRRI_pat<S6_rol_i_p_acc,   Add, Su<Rol>, I64, u6_0ImmPred>;
+    def: AccRRI_pat<S6_rol_i_p_nac,   Sub, Su<Rol>, I64, u6_0ImmPred>;
+    def: AccRRI_pat<S6_rol_i_p_and,   And, Su<Rol>, I64, u6_0ImmPred>;
+    def: AccRRI_pat<S6_rol_i_p_or,    Or,  Su<Rol>, I64, u6_0ImmPred>;
+    def: AccRRI_pat<S6_rol_i_p_xacc,  Xor, Su<Rol>, I64, u6_0ImmPred>;
+  }
 }
 
 let AddedComplexity = 100 in {
   def: AccRRR_pat<S2_asr_r_r_acc,   Add, Su<Sra>, I32, I32, I32>;
   def: AccRRR_pat<S2_asr_r_r_nac,   Sub, Su<Sra>, I32, I32, I32>;
   def: AccRRR_pat<S2_asr_r_r_and,   And, Su<Sra>, I32, I32, I32>;
   def: AccRRR_pat<S2_asr_r_r_or,    Or,  Su<Sra>, I32, I32, I32>;
 

test/CodeGen/Hexagon/rotate.ll

+; RUN: llc -march=hexagon < %s | FileCheck %s
+
+target triple = "hexagon"
+
+; CHECK-LABEL: f0
+; CHECK: r0 = rol(r0,#7)
+define dso_local i32 @f0(i32 %a0) local_unnamed_addr #0 {
+b0:
+  %v0 = shl i32 %a0, 7
+  %v1 = lshr i32 %a0, 25
+  %v2 = or i32 %v0, %v1
+  ret i32 %v2
+}
+
+; CHECK-LABEL: f1
+; No variable-shift rotates.
+; CHECK-NOT: rol
+define dso_local i32 @f1(i32 %a0, i32 %a1) local_unnamed_addr #0 {
+b0:
+  %v0 = shl i32 %a0, %a1
+  %v1 = sub i32 32, %a1
+  %v2 = lshr i32 %a0, %v1
+  %v3 = or i32 %v2, %v0
+  ret i32 %v3
+}
+
+; CHECK-LABEL: f2
+; CHECK: r0 = rol(r0,#25)
+define dso_local i32 @f2(i32 %a0) local_unnamed_addr #0 {
+b0:
+  %v0 = lshr i32 %a0, 7
+  %v1 = shl i32 %a0, 25
+  %v2 = or i32 %v0, %v1
+  ret i32 %v2
+}
+
+; CHECK-LABEL: f3
+; No variable-shift rotates.
+; CHECK-NOT: rol
+define dso_local i32 @f3(i32 %a0, i32 %a1) local_unnamed_addr #0 {
+b0:
+  %v0 = lshr i32 %a0, %a1
+  %v1 = sub i32 32, %a1
+  %v2 = shl i32 %a0, %v1
+  %v3 = or i32 %v2, %v0
+  ret i32 %v3
+}
+
+; CHECK-LABEL: f4
+; CHECK: r1:0 = rol(r1:0,#7)
+define dso_local i64 @f4(i64 %a0) local_unnamed_addr #0 {
+b0:
+  %v0 = shl i64 %a0, 7
+  %v1 = lshr i64 %a0, 57
+  %v2 = or i64 %v0, %v1
+  ret i64 %v2
+}
+
+; CHECK-LABEL: f5
+; CHECK-NOT: rol
+define dso_local i64 @f5(i64 %a0, i32 %a1) local_unnamed_addr #0 {
+b0:
+  %v0 = zext i32 %a1 to i64
+  %v1 = shl i64 %a0, %v0
+  %v2 = sub i32 64, %a1
+  %v3 = zext i32 %v2 to i64
+  %v4 = lshr i64 %a0, %v3
+  %v5 = or i64 %v4, %v1
+  ret i64 %v5
+}
+
+; CHECK-LABEL: f6
+; CHECK: r1:0 = rol(r1:0,#57)
+define dso_local i64 @f6(i64 %a0) local_unnamed_addr #0 {
+b0:
+  %v0 = lshr i64 %a0, 7
+  %v1 = shl i64 %a0, 57
+  %v2 = or i64 %v0, %v1
+  ret i64 %v2
+}
+
+; CHECK-LABEL: f7
+; CHECK-NOT: rol
+define dso_local i64 @f7(i64 %a0, i32 %a1) local_unnamed_addr #0 {
+b0:
+  %v0 = zext i32 %a1 to i64
+  %v1 = lshr i64 %a0, %v0
+  %v2 = sub i32 64, %a1
+  %v3 = zext i32 %v2 to i64
+  %v4 = shl i64 %a0, %v3
+  %v5 = or i64 %v4, %v1
+  ret i64 %v5
+}
+
+; CHECK-LABEL: f8
+; CHECK: r0 += rol(r1,#7)
+define dso_local i32 @f8(i32 %a0, i32 %a1) local_unnamed_addr #0 {
+b0:
+  %v0 = shl i32 %a1, 7
+  %v1 = lshr i32 %a1, 25
+  %v2 = or i32 %v0, %v1
+  %v3 = add i32 %v2, %a0
+  ret i32 %v3
+}
+
+; CHECK-LABEL: f9
+; CHECK: r0 -= rol(r1,#7)
+define dso_local i32 @f9(i32 %a0, i32 %a1) local_unnamed_addr #0 {
+b0:
+  %v0 = shl i32 %a1, 7
+  %v1 = lshr i32 %a1, 25
+  %v2 = or i32 %v0, %v1
+  %v3 = sub i32 %a0, %v2
+  ret i32 %v3
+}
+
+; CHECK-LABEL: f10
+; CHECK: r0 &= rol(r1,#7)
+define dso_local i32 @f10(i32 %a0, i32 %a1) local_unnamed_addr #0 {
+b0:
+  %v0 = shl i32 %a1, 7
+  %v1 = lshr i32 %a1, 25
+  %v2 = or i32 %v0, %v1
+  %v3 = and i32 %v2, %a0
+  ret i32 %v3
+}
+
+; CHECK-LABEL: f11
+; CHECK: r0 |= rol(r1,#7)
+define dso_local i32 @f11(i32 %a0, i32 %a1) local_unnamed_addr #0 {
+b0:
+  %v0 = shl i32 %a1, 7
+  %v1 = lshr i32 %a1, 25
+  %v2 = or i32 %v1, %a0
+  %v3 = or i32 %v2, %v0
+  ret i32 %v3
+}
+
+; CHECK-LABEL: f12
+; CHECK: r0 ^= rol(r1,#7)
+define dso_local i32 @f12(i32 %a0, i32 %a1) local_unnamed_addr #0 {
+b0:
+  %v0 = shl i32 %a1, 7
+  %v1 = lshr i32 %a1, 25
+  %v2 = or i32 %v0, %v1
+  %v3 = xor i32 %v2, %a0
+  ret i32 %v3
+}
+
+; CHECK-LABEL: f13
+; CHECK: r1:0 += rol(r3:2,#7)
+define dso_local i64 @f13(i64 %a0, i64 %a1) local_unnamed_addr #0 {
+b0:
+  %v0 = shl i64 %a1, 7
+  %v1 = lshr i64 %a1, 57
+  %v2 = or i64 %v0, %v1
+  %v3 = add i64 %v2, %a0
+  ret i64 %v3
+}
+
+; CHECK-LABEL: f14
+; CHECK: r1:0 -= rol(r3:2,#7)
+define dso_local i64 @f14(i64 %a0, i64 %a1) local_unnamed_addr #0 {
+b0:
+  %v0 = shl i64 %a1, 7
+  %v1 = lshr i64 %a1, 57
+  %v2 = or i64 %v0, %v1
+  %v3 = sub i64 %a0, %v2
+  ret i64 %v3
+}
+
+; CHECK-LABEL: f15
+; CHECK: r1:0 &= rol(r3:2,#7)
+define dso_local i64 @f15(i64 %a0, i64 %a1) local_unnamed_addr #0 {
+b0:
+  %v0 = shl i64 %a1, 7
+  %v1 = lshr i64 %a1, 57
+  %v2 = or i64 %v0, %v1
+  %v3 = and i64 %v2, %a0
+  ret i64 %v3
+}
+
+; CHECK-LABEL: f16
+; CHECK: r1:0 |= rol(r3:2,#7)
+define dso_local i64 @f16(i64 %a0, i64 %a1) local_unnamed_addr #0 {
+b0:
+  %v0 = shl i64 %a1, 7
+  %v1 = lshr i64 %a1, 57
+  %v2 = or i64 %v1, %a0
+  %v3 = or i64 %v2, %v0
+  ret i64 %v3
+}
+
+; CHECK-LABEL: f17
+; CHECK: r1:0 ^= rol(r3:2,#7)
+define dso_local i64 @f17(i64 %a0, i64 %a1) local_unnamed_addr #0 {
+b0:
+  %v0 = shl i64 %a1, 7
+  %v1 = lshr i64 %a1, 57
+  %v2 = or i64 %v0, %v1
+  %v3 = xor i64 %v2, %a0
+  ret i64 %v3
+}
+
+attributes #0 = { norecurse nounwind readnone "target-cpu"="hexagonv60" }

test/CodeGen/Hexagon/rotl-i64.ll

 ; RUN: llc -march=hexagon < %s | FileCheck %s
-; CHECK: asl
+; CHECK: rol
 
 ; Function Attrs: nounwind
 define fastcc void @f0() #0 {
 b0:
   br label %b1
 
 b1:                                               ; preds = %b1, %b0
   br i1 undef, label %b2, label %b1
 
 b2:                                               ; preds = %b1
   br label %b3
 
 b3:                                               ; preds = %b3, %b2
   %v0 = load i64, i64* undef, align 8, !tbaa !0
   %v1 = lshr i64 %v0, 8
   %v2 = shl i64 %v0, 56
   %v3 = or i64 %v2, %v1
   %v4 = xor i64 %v3, 0
   %v5 = xor i64 %v4, 0
   %v6 = add i64 0, %v5
   store i64 %v6, i64* undef, align 8, !tbaa !0
   br label %b3
 }
 
-attributes #0 = { nounwind }
+attributes #0 = { nounwind "target-cpu"="hexagonv60" }
 
 !0 = !{!1, !1, i64 0}
 !1 = !{!"long long", !2}
 !2 = !{!"omnipotent char", !3}
 !3 = !{!"Simple C/C++ TBAA"}