[DAGCombiner] Fix issue with rot chain pattern

[bcl5980]

Summary

faa35fc87370 fix the case of negative input shift. But when c1, c2 is not the same side, it will also cause negative shift amount.
And that negative shift amount can't normalize by urem. So add one more bit size to normalize the last shift amount.

Fix: https://github.com/llvm/llvm-project/issues/59898

[RKSimon]

Please can you rebase? I've updated the tests so the patch should just show the codegen diff

[bcl5980]

rebase code

[RKSimon]

LGTM with one minor - cheers

llvm/test/CodeGen/AArch64/rotate.ll

19–35

;; This used to cause a miscompile because rot combine

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (N1.getOpcode() == ISD::TRUNCATE &&
       N1.getOperand(0).getOpcode() == ISD::AND) {
     if (SDValue NewOp1 = distributeTruncateThroughAnd(N1.getNode()))
       return DAG.getNode(N->getOpcode(), dl, VT, N0, NewOp1);
   }
 
   unsigned NextOp = N0.getOpcode();
 
   // fold (rot* (rot* x, c2), c1)
-  //   -> (rot* x, ((c1 % bitsize) +- (c2 % bitsize)) % bitsize)
+  //   -> (rot* x, ((c1 % bitsize) +- (c2 % bitsize) + bitsize) % bitsize)
   if (NextOp == ISD::ROTL || NextOp == ISD::ROTR) {
     SDNode *C1 = DAG.isConstantIntBuildVectorOrConstantInt(N1);
     SDNode *C2 = DAG.isConstantIntBuildVectorOrConstantInt(N0.getOperand(1));
     if (C1 && C2 && C1->getValueType(0) == C2->getValueType(0)) {
       EVT ShiftVT = C1->getValueType(0);
       bool SameSide = (N->getOpcode() == NextOp);
       unsigned CombineOp = SameSide ? ISD::ADD : ISD::SUB;
       SDValue BitsizeC = DAG.getConstant(Bitsize, dl, ShiftVT);
       SDValue Norm1 = DAG.FoldConstantArithmetic(ISD::UREM, dl, ShiftVT,
                                                  {N1, BitsizeC});
       SDValue Norm2 = DAG.FoldConstantArithmetic(ISD::UREM, dl, ShiftVT,
                                                  {N0.getOperand(1), BitsizeC});
       if (Norm1 && Norm2)
         if (SDValue CombinedShift = DAG.FoldConstantArithmetic(
                 CombineOp, dl, ShiftVT, {Norm1, Norm2})) {
+          CombinedShift = DAG.FoldConstantArithmetic(ISD::ADD, dl, ShiftVT,
+                                                     {CombinedShift, BitsizeC});
           SDValue CombinedShiftNorm = DAG.FoldConstantArithmetic(
               ISD::UREM, dl, ShiftVT, {CombinedShift, BitsizeC});
           return DAG.getNode(N->getOpcode(), dl, VT, N0->getOperand(0),
                              CombinedShiftNorm);
         }
     }
   }
   return SDValue();

llvm/test/CodeGen/AArch64/rotate.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=aarch64--linux-gnueabihf | FileCheck %s
 
 ;; This used to cause a backend crash about not being able to
 ;; select ROTL. Make sure if generates the basic ushr/shl.
 define <2 x i64> @testcase(ptr %in) {
-; CHECK-LABEL: testcase
-; CHECK: ushr {{v[0-9]+}}.2d
-; CHECK: shl  {{v[0-9]+}}.2d
+; CHECK-LABEL: testcase:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    ldr q0, [x0]
+; CHECK-NEXT:    ushr v1.2d, v0.2d, #8
+; CHECK-NEXT:    shl v0.2d, v0.2d, #56
+; CHECK-NEXT:    orr v0.16b, v0.16b, v1.16b
+; CHECK-NEXT:    ret
   %1 = load <2 x i64>, ptr %in
   %2 = lshr <2 x i64> %1, <i64 8, i64 8>
   %3 = shl <2 x i64> %1, <i64 56, i64 56>
   %4 = or <2 x i64> %2, %3
   ret <2 x i64> %4
 }
+
+;; This used to cause miscompile because rot combine
+;; doesn't handle negative shift well.
+define i5 @pr59898(i5 %x) {
+; CHECK-LABEL: rotr_merge_i5:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    ubfx w8, w0, #1, #4
+; CHECK-NEXT:    orr w0, w8, w0, lsl #4
+; CHECK-NEXT:    ret
+  %r1 = call i5 @llvm.fshr.i5(i5 %x, i5 %x, i5 3)
+  %r2 = call i5 @llvm.fshl.i5(i5 %r1, i5 %r1, i5 2)
+  ret i5 %r2
+}
+
+declare i5 @llvm.fshl.i5(i5, i5, i5)
+declare i5 @llvm.fshr.i5(i5, i5, i5)