[Kryo] Cannonicalize commutative operands based on LSLFast

[haicheng]

Summary

LSLFast - a logical shift left up to 3 places.

In Kryo if an commutative instruction has a LSL for both operands and if the LSL can be folded into the instruction's shifted register (e.g., add x0, x1, x2, lsl #3) then we should canonicalize the operands so the smaller (in terms of the number of shifts) is the operands that is folded.

For example, rather than

lsl x1, x1, #1
add x0, x1, x2, lsl #4

we should prefer

lsl x2, x2, #4
add x0, x2, x1, lsl #1

as this safes a cycle on the add instruction.

I will add commutative instructions after this patch is approved.

[mcrosier]

Any particular reason this is being done in the MachineCombiner pass? My first thought would be to do this as a DAG combine..

[haicheng]

Reimplemented in DAG Combine.

[mcrosier]

lib/Target/AArch64/AArch64ISelLowering.cpp

8292

I would further narrow this such that we only commute the operands when we know the shift is 3 or fewer. Otherwise, code will be perturbed for no real reason.

[haicheng]

Restrict further.

[t.p.northover]

lib/Target/AArch64/AArch64ISelLowering.cpp

8292

I'd be very tempted to turn this on for all CPUs (perhaps with a comment that Kryo is particularly keen on it). The optimal checks would be slightly different for others, but it's already a transformation that allows the formation of extra "ldr Dst, [xA, xB, lsl #N]" instructions for everyone.

[mcrosier]

lib/Target/AArch64/AArch64ISelLowering.cpp

8292

I very much agree with you, Tim. If the optimization is applicable to all subtargets we should not guard this with isKryo.

[haicheng]

Move to D18949 which supports Add/Xor/Or/And, includes llvm-commits for review, and enables this feature for all AArch64 back-ends.

lib/Target/AArch64/AArch64ISelLowering.cpp

 }
 
 // The folding we want to perform is:
 // (add x, [zext] (setcc cc ...) )
 //   -->
 // (csel x, (add x, 1), !cc ...)
 //
 // The latter will get matched to a CSINC instruction.
-static SDValue performSetccAddFolding(SDNode *Op, SelectionDAG &DAG) {
+static SDValue performAddFolding(SDNode *Op, SelectionDAG &DAG,
+                                 const AArch64Subtarget *Subtarget) {
   assert(Op && Op->getOpcode() == ISD::ADD && "Unexpected operation!");
   SDValue LHS = Op->getOperand(0);
   SDValue RHS = Op->getOperand(1);
+  SDLoc dl(Op);
+  EVT VT = Op->getValueType(0);
+
+  // (add shl(x, c1), shl(y, c2)) -> (add shl(y, c2), shl(x, c1)) if c1 < c2
+  if (Subtarget->isKryo())
+    if (LHS.getOpcode() == ISD::SHL && RHS.getOpcode() == ISD::SHL) {
+      ConstantSDNode *C0 = dyn_cast<ConstantSDNode>(LHS.getOperand(1));
+      ConstantSDNode *C1 = dyn_cast<ConstantSDNode>(RHS.getOperand(1));
+      if (C0 && C1 && C0->getAPIntValue().ult(C1->getAPIntValue()))
+        return DAG.getNode(Op->getOpcode(), dl, VT, RHS, LHS); 
+    }
+
   SetCCInfoAndKind InfoAndKind;
 
   // If neither operand is a SET_CC, give up.
   if (!isSetCCOrZExtSetCC(LHS, InfoAndKind)) {
     std::swap(LHS, RHS);
     if (!isSetCCOrZExtSetCC(LHS, InfoAndKind))
       return SDValue();
   }
 
   // FIXME: This could be generatized to work for FP comparisons.
   EVT CmpVT = InfoAndKind.IsAArch64
                   ? InfoAndKind.Info.AArch64.Cmp->getOperand(0).getValueType()
                   : InfoAndKind.Info.Generic.Opnd0->getValueType();
   if (CmpVT != MVT::i32 && CmpVT != MVT::i64)
     return SDValue();
 
   SDValue CCVal;
   SDValue Cmp;
-  SDLoc dl(Op);
   if (InfoAndKind.IsAArch64) {
     CCVal = DAG.getConstant(
         AArch64CC::getInvertedCondCode(InfoAndKind.Info.AArch64.CC), dl,
         MVT::i32);
     Cmp = *InfoAndKind.Info.AArch64.Cmp;
   } else
     Cmp = getAArch64Cmp(*InfoAndKind.Info.Generic.Opnd0,
                       *InfoAndKind.Info.Generic.Opnd1,
                       ISD::getSetCCInverse(InfoAndKind.Info.Generic.CC, true),
                       CCVal, DAG, dl);
 
-  EVT VT = Op->getValueType(0);
   LHS = DAG.getNode(ISD::ADD, dl, VT, RHS, DAG.getConstant(1, dl, VT));
   return DAG.getNode(AArch64ISD::CSEL, dl, VT, RHS, LHS, CCVal, Cmp);
 }
 
 // The basic add/sub long vector instructions have variants with "2" on the end
 // which act on the high-half of their inputs. They are normally matched by
 // patterns like:
 //
 // (add (zeroext (extract_high LHS)),
 //      (zeroext (extract_high RHS)))
 // -> uaddl2 vD, vN, vM
 //
 // However, if one of the extracts is something like a duplicate, this
 // instruction can still be used profitably. This function puts the DAG into a
 // more appropriate form for those patterns to trigger.
 static SDValue performAddSubLongCombine(SDNode *N,
                                         TargetLowering::DAGCombinerInfo &DCI,
-                                        SelectionDAG &DAG) {
+                                        SelectionDAG &DAG,
+                                        const AArch64Subtarget *Subtarget) {
   if (DCI.isBeforeLegalizeOps())
     return SDValue();
 
   MVT VT = N->getSimpleValueType(0);
   if (!VT.is128BitVector()) {
     if (N->getOpcode() == ISD::ADD)
-      return performSetccAddFolding(N, DAG);
+      return performAddFolding(N, DAG, Subtarget);
     return SDValue();
   }
 
   // Make sure both branches are extended in the same way.
   SDValue LHS = N->getOperand(0);
   SDValue RHS = N->getOperand(1);
   if ((LHS.getOpcode() != ISD::ZERO_EXTEND &&
        LHS.getOpcode() != ISD::SIGN_EXTEND) ||

 SDValue AArch64TargetLowering::PerformDAGCombine(SDNode *N,
                                                  DAGCombinerInfo &DCI) const {
   SelectionDAG &DAG = DCI.DAG;
   switch (N->getOpcode()) {
   default:
     break;
   case ISD::ADD:
   case ISD::SUB:
-    return performAddSubLongCombine(N, DCI, DAG);
+    return performAddSubLongCombine(N, DCI, DAG, Subtarget);
   case ISD::XOR:
     return performXorCombine(N, DAG, DCI, Subtarget);
   case ISD::MUL:
     return performMulCombine(N, DAG, DCI, Subtarget);
   case ISD::SINT_TO_FP:
   case ISD::UINT_TO_FP:
     return performIntToFpCombine(N, DAG, Subtarget);
   case ISD::FP_TO_SINT:

test/CodeGen/AArch64/kryo-lsl.ll

+; RUN: llc -mtriple=aarch64-gnu-linux -mcpu=kryo < %s | FileCheck %s
+
+; Verify that the shift amount in the add instruction is alwarys the smaller 
+; one.
+
+define i32 @lsl_add1(i32 %a, i32 %b) {
+; CHECK-LABEL:   lsl_add1:
+; CHECK:         lsl   w8, w0, #3 
+; CHECK-NEXT:    add   w0, w8, w1, lsl #2   
+; CHECK-NEXT:    ret
+entry:
+  %shl = shl i32 %a, 3
+  %shl1 = shl i32 %b, 2
+  %add = add i32 %shl1, %shl
+  ret i32 %add
+}
+
+define i32 @lsl_add2(i32 %a, i32 %b) {
+; CHECK-LABEL:   lsl_add2:
+; CHECK:         lsl    w8, w1, #3 
+; CHECK-NEXT:    add    w0, w8, w0, lsl #2   
+; CHECK-NEXT:    ret
+
+entry:
+  %shl = shl i32 %a, 2
+  %shl1 = shl i32 %b, 3
+  %add = add i32 %shl1, %shl
+  ret i32 %add
+}
+
+define i64 @lsl_add3(i64 %a, i64 %b) {
+; CHECK-LABEL:   lsl_add3:
+; CHECK:         lsl    x8, x0, #3 
+; CHECK-NEXT:    add    x0, x8, x1, lsl #2   
+; CHECK-NEXT:    ret
+
+entry:
+  %shl = shl i64 %a, 3
+  %shl1 = shl i64 %b, 2
+  %add = add i64 %shl1, %shl
+  ret i64 %add
+}
+
+define i64 @lsl_add4(i64 %a, i64 %b) {
+; CHECK-LABEL:   lsl_add4:
+; CHECK:         lsl    x8, x1, #3 
+; CHECK-NEXT:    add    x0, x8, x0, lsl #2   
+; CHECK-NEXT:    ret
+entry:
+  %shl = shl i64 %a, 2
+  %shl1 = shl i64 %b, 3
+  %add = add i64 %shl1, %shl
+  ret i64 %add
+}
+