[GlobalISel] Implement lowering for G_ROTR and G_ROTL.

[aemerson]

Summary

This is a straightforward port.

[foad]

llvm/include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h

970 ↗

(On Diff #333649)

buildConstant already does this.

llvm/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

5382

What does "Hs" mean?

[aemerson]

llvm/include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h

970 ↗

(On Diff #333649)

Indeed it does. The doc for it should make it clearer.

llvm/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

5382

Good question. This was a port of some code that you wrote in TargetLowering, do you remember?

[foad]

llvm/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

5382

Curses! Actually it predates me and originally comes from D47725. My only guess is that it's a cute way of indicating a reverse shift by "reversing" the letters S H, in which case I think it's too cute, and not in a good way.

I'll leave it up to you whether to change it to something more understandable or not.

[arsenm]

llvm/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

5372–5374

I believe alternate lowerings based on instruction legality should be split into separate lower* functions. That way custom lowering can pick the strategy itself, and the default function would then use these crude legality heuristics to pick which strategy to use.

[aemerson]

Split out the opposite rotate handling into separate method.

[foad]

Looks fine to me modulo the naming nit.

llvm/include/llvm/CodeGen/GlobalISel/LegalizerHelper.h

351

Nit: "opposite" is now the third word we're using for the same thing. The code calls it "reverse", and the equivalent funnel shift function (three lines up) calls it "inverse". Could we standardize on one? I'd vote for "reverse".

[aemerson]

llvm/include/llvm/CodeGen/GlobalISel/LegalizerHelper.h

351

Sure, I'll change that before landing.

llvm/include/llvm/CodeGen/GlobalISel/LegalizerHelper.h

public:
 
   LegalizeResult lowerBitcast(MachineInstr &MI);
   LegalizeResult lowerLoad(MachineInstr &MI);
   LegalizeResult lowerStore(MachineInstr &MI);
   LegalizeResult lowerBitCount(MachineInstr &MI);
   LegalizeResult lowerFunnelShiftWithInverse(MachineInstr &MI);
   LegalizeResult lowerFunnelShiftAsShifts(MachineInstr &MI);
   LegalizeResult lowerFunnelShift(MachineInstr &MI);
+  LegalizeResult lowerRotateWithReverseRotate(MachineInstr &MI);
+  LegalizeResult lowerRotate(MachineInstr &MI);
 
   LegalizeResult lowerU64ToF32BitOps(MachineInstr &MI);
   LegalizeResult lowerUITOFP(MachineInstr &MI);
   LegalizeResult lowerSITOFP(MachineInstr &MI);
   LegalizeResult lowerFPTOUI(MachineInstr &MI);
   LegalizeResult lowerFPTOSI(MachineInstr &MI);
 
   LegalizeResult lowerFPTRUNC_F64_TO_F16(MachineInstr &MI);

llvm/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

LegalizerHelper::lower(MachineInstr &MI, unsigned TypeIdx, LLT LowerHintTy) {
   case G_SELECT:
     return lowerSelect(MI);
   case G_SDIVREM:
   case G_UDIVREM:
     return lowerDIVREM(MI);
   case G_FSHL:
   case G_FSHR:
     return lowerFunnelShift(MI);
+  case G_ROTL:
+  case G_ROTR:
+    return lowerRotate(MI);
   }
 }
 
 Align LegalizerHelper::getStackTemporaryAlignment(LLT Ty,
                                                   Align MinAlign) const {
   // FIXME: We're missing a way to go back from LLT to llvm::Type to query the
   // datalayout for the preferred alignment. Also there should be a target hook
   // for this to allow targets to reduce the alignment and ignore the
LegalizerHelper::lowerFunnelShift(MachineInstr &MI) {
 
   bool IsFSHL = MI.getOpcode() == TargetOpcode::G_FSHL;
   unsigned RevOpcode = IsFSHL ? TargetOpcode::G_FSHR : TargetOpcode::G_FSHL;
   if (LI.getAction({RevOpcode, {Ty, ShTy}}).Action == Lower)
     return lowerFunnelShiftAsShifts(MI);
   return lowerFunnelShiftWithInverse(MI);
 }
 
+LegalizerHelper::LegalizeResult
+LegalizerHelper::lowerRotateWithReverseRotate(MachineInstr &MI) {
+  Register Dst = MI.getOperand(0).getReg();
+  Register Src = MI.getOperand(1).getReg();
+  Register Amt = MI.getOperand(2).getReg();
+  LLT AmtTy = MRI.getType(Amt);
+  auto Zero = MIRBuilder.buildConstant(AmtTy, 0);
+  bool IsLeft = MI.getOpcode() == TargetOpcode::G_ROTL;
+  unsigned RevRot = IsLeft ? TargetOpcode::G_ROTR : TargetOpcode::G_ROTL;
+  auto Neg = MIRBuilder.buildSub(AmtTy, Zero, Amt);
+  MIRBuilder.buildInstr(RevRot, {Dst}, {Src, Neg});
+  MI.eraseFromParent();
+  return Legalized;
+}
+
+LegalizerHelper::LegalizeResult LegalizerHelper::lowerRotate(MachineInstr &MI) {
+  Register Dst = MI.getOperand(0).getReg();
+  Register Src = MI.getOperand(1).getReg();
+  Register Amt = MI.getOperand(2).getReg();
+  LLT DstTy = MRI.getType(Dst);
+  LLT SrcTy = MRI.getType(Dst);
+  LLT AmtTy = MRI.getType(Amt);
+
+  unsigned EltSizeInBits = DstTy.getScalarSizeInBits();
+  bool IsLeft = MI.getOpcode() == TargetOpcode::G_ROTL;
+
+  MIRBuilder.setInstrAndDebugLoc(MI);
+
+  // If a rotate in the other direction is supported, use it.
+  unsigned RevRot = IsLeft ? TargetOpcode::G_ROTR : TargetOpcode::G_ROTL;
+  if (LI.isLegalOrCustom({RevRot, {DstTy, SrcTy}}) &&
+      isPowerOf2_32(EltSizeInBits))
+    return lowerRotateWithReverseRotate(MI);
+
+  auto Zero = MIRBuilder.buildConstant(AmtTy, 0);
+  unsigned ShOpc = IsLeft ? TargetOpcode::G_SHL : TargetOpcode::G_LSHR;
+  unsigned RevShiftOpc = IsLeft ? TargetOpcode::G_LSHR : TargetOpcode::G_SHL;
+  auto BitWidthMinusOneC = MIRBuilder.buildConstant(AmtTy, EltSizeInBits - 1);
+  Register ShVal;
+  Register RevShiftVal;
+  if (isPowerOf2_32(EltSizeInBits)) {
+    // (rotl x, c) -> x << (c & (w - 1)) | x >> (-c & (w - 1))
+    // (rotr x, c) -> x >> (c & (w - 1)) | x << (-c & (w - 1))
+    auto NegAmt = MIRBuilder.buildSub(AmtTy, Zero, Amt);
+    auto ShAmt = MIRBuilder.buildAnd(AmtTy, Amt, BitWidthMinusOneC);
+    ShVal = MIRBuilder.buildInstr(ShOpc, {DstTy}, {Src, ShAmt}).getReg(0);
+    auto RevAmt = MIRBuilder.buildAnd(AmtTy, NegAmt, BitWidthMinusOneC);
+    RevShiftVal =
+        MIRBuilder.buildInstr(RevShiftOpc, {DstTy}, {Src, RevAmt}).getReg(0);
+  } else {
+    // (rotl x, c) -> x << (c % w) | x >> 1 >> (w - 1 - (c % w))
+    // (rotr x, c) -> x >> (c % w) | x << 1 << (w - 1 - (c % w))
+    auto BitWidthC = MIRBuilder.buildConstant(AmtTy, EltSizeInBits);
+    auto ShAmt = MIRBuilder.buildURem(AmtTy, Amt, BitWidthC);
+    ShVal = MIRBuilder.buildInstr(ShOpc, {DstTy}, {Src, ShAmt}).getReg(0);
+    auto RevAmt = MIRBuilder.buildSub(AmtTy, BitWidthMinusOneC, ShAmt);
+    auto One = MIRBuilder.buildConstant(AmtTy, 1);
+    auto Inner = MIRBuilder.buildInstr(RevShiftOpc, {DstTy}, {Src, One});
+    RevShiftVal =
+        MIRBuilder.buildInstr(RevShiftOpc, {DstTy}, {Inner, RevAmt}).getReg(0);
+  }
+  MIRBuilder.buildOr(Dst, ShVal, RevShiftVal);
+  MI.eraseFromParent();
+  return Legalized;
+}
+
 // Expand s32 = G_UITOFP s64 using bit operations to an IEEE float
 // representation.
 LegalizerHelper::LegalizeResult
 LegalizerHelper::lowerU64ToF32BitOps(MachineInstr &MI) {
   Register Dst = MI.getOperand(0).getReg();
   Register Src = MI.getOperand(1).getReg();
   const LLT S64 = LLT::scalar(64);
   const LLT S32 = LLT::scalar(32);

llvm/unittests/CodeGen/GlobalISel/LegalizerHelperTest.cpp

 class DummyGISelObserver : public GISelChangeObserver {
 public:
   void changingInstr(MachineInstr &MI) override {}
   void changedInstr(MachineInstr &MI) override {}
   void createdInstr(MachineInstr &MI) override {}
   void erasingInstr(MachineInstr &MI) override {}
 };
 
+// Test G_ROTL/G_ROTR lowering.
+TEST_F(AArch64GISelMITest, LowerRotates) {
+  setUp();
+  if (!TM)
+    return;
+
+  // Declare your legalization info
+  DefineLegalizerInfo(A, {
+    getActionDefinitionsBuilder({G_ROTR, G_ROTL}).lower(); });
+
+  LLT S32 = LLT::scalar(32);
+  auto Src = B.buildTrunc(S32, Copies[0]);
+  auto Amt = B.buildTrunc(S32, Copies[1]);
+  auto ROTR = B.buildInstr(TargetOpcode::G_ROTR, {S32}, {Src, Amt});
+  auto ROTL = B.buildInstr(TargetOpcode::G_ROTL, {S32}, {Src, Amt});
+
+  AInfo Info(MF->getSubtarget());
+  DummyGISelObserver Observer;
+  LegalizerHelper Helper(*MF, Info, Observer, B);
+  // Perform Legalization
+  EXPECT_EQ(LegalizerHelper::LegalizeResult::Legalized,
+            Helper.lower(*ROTR, 0, S32));
+  EXPECT_EQ(LegalizerHelper::LegalizeResult::Legalized,
+            Helper.lower(*ROTL, 0, S32));
+
+  auto CheckStr = R"(
+  ; Check G_ROTR
+  CHECK: [[SRC:%[0-9]+]]:_(s32) = G_TRUNC
+  CHECK: [[AMT:%[0-9]+]]:_(s32) = G_TRUNC
+  CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 0
+  CHECK: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 31
+  CHECK: [[SUB:%[0-9]+]]:_(s32) = G_SUB [[C]]:_, [[AMT]]:_
+  CHECK: [[AND:%[0-9]+]]:_(s32) = G_AND [[AMT]]:_, [[C1]]:_
+  CHECK: [[LSHR:%[0-9]+]]:_(s32) = G_LSHR [[SRC]]:_, [[AND]]:_(s32)
+  CHECK: [[AND1:%[0-9]+]]:_(s32) = G_AND [[SUB]]:_, [[C1]]:_
+  CHECK: [[SHL:%[0-9]+]]:_(s32) = G_SHL [[SRC]]:_, [[AND1]]:_(s32)
+  CHECK: G_OR [[LSHR]]:_, [[SHL]]:_
+
+  ; Check G_ROTL
+  CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 0
+  CHECK: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 31
+  CHECK: [[SUB:%[0-9]+]]:_(s32) = G_SUB [[C]]:_, [[AMT]]:_
+  CHECK: [[AND:%[0-9]+]]:_(s32) = G_AND [[AMT]]:_, [[C1]]:_
+  CHECK: [[SHL:%[0-9]+]]:_(s32) = G_SHL [[SRC]]:_, [[AND]]:_(s32)
+  CHECK: [[AND1:%[0-9]+]]:_(s32) = G_AND [[SUB]]:_, [[C1]]:_
+  CHECK: [[LSHR:%[0-9]+]]:_(s32) = G_LSHR [[SRC]]:_, [[AND1]]:_(s32)
+  CHECK: G_OR [[SHL]]:_, [[LSHR]]:_
+  )";
+
+  // Check
+  EXPECT_TRUE(CheckMachineFunction(*MF, CheckStr)) << *MF;
+}
+
+// Test G_ROTL/G_ROTR non-pow2 lowering.
+TEST_F(AArch64GISelMITest, LowerRotatesNonPow2) {
+  setUp();
+  if (!TM)
+    return;
+
+  // Declare your legalization info
+  DefineLegalizerInfo(A, {
+    getActionDefinitionsBuilder({G_ROTR, G_ROTL}).lower(); });
+
+  LLT S24 = LLT::scalar(24);
+  auto Src = B.buildTrunc(S24, Copies[0]);
+  auto Amt = B.buildTrunc(S24, Copies[1]);
+  auto ROTR = B.buildInstr(TargetOpcode::G_ROTR, {S24}, {Src, Amt});
+  auto ROTL = B.buildInstr(TargetOpcode::G_ROTL, {S24}, {Src, Amt});
+
+  AInfo Info(MF->getSubtarget());
+  DummyGISelObserver Observer;
+  LegalizerHelper Helper(*MF, Info, Observer, B);
+  // Perform Legalization
+  EXPECT_EQ(LegalizerHelper::LegalizeResult::Legalized,
+            Helper.lower(*ROTR, 0, S24));
+  EXPECT_EQ(LegalizerHelper::LegalizeResult::Legalized,
+            Helper.lower(*ROTL, 0, S24));
+
+  auto CheckStr = R"(
+  ; Check G_ROTR
+  CHECK: [[SRC:%[0-9]+]]:_(s24) = G_TRUNC
+  CHECK: [[AMT:%[0-9]+]]:_(s24) = G_TRUNC
+  CHECK: [[C:%[0-9]+]]:_(s24) = G_CONSTANT i24 0
+  CHECK: [[C1:%[0-9]+]]:_(s24) = G_CONSTANT i24 23
+  CHECK: [[C2:%[0-9]+]]:_(s24) = G_CONSTANT i24 24
+  CHECK: [[UREM:%[0-9]+]]:_(s24) = G_UREM [[AMT]]:_, [[C2]]:_
+  CHECK: [[LSHR:%[0-9]+]]:_(s24) = G_LSHR [[SRC]]:_, [[UREM]]:_(s24)
+  CHECK: [[SUB:%[0-9]+]]:_(s24) = G_SUB [[C1]]:_, [[UREM]]:_
+  CHECK: [[C4:%[0-9]+]]:_(s24) = G_CONSTANT i24 1
+  CHECK: [[SHL:%[0-9]+]]:_(s24) = G_SHL [[SRC]]:_, [[C4]]:_(s24)
+  CHECK: [[SHL2:%[0-9]+]]:_(s24) = G_SHL [[SHL]]:_, [[SUB]]:_(s24)
+  CHECK: G_OR [[LSHR]]:_, [[SHL2]]:_
+
+  ; Check G_ROTL
+  CHECK: [[C:%[0-9]+]]:_(s24) = G_CONSTANT i24 0
+  CHECK: [[C1:%[0-9]+]]:_(s24) = G_CONSTANT i24 23
+  CHECK: [[C2:%[0-9]+]]:_(s24) = G_CONSTANT i24 24
+  CHECK: [[UREM:%[0-9]+]]:_(s24) = G_UREM [[AMT]]:_, [[C2]]:_
+  CHECK: [[SHL:%[0-9]+]]:_(s24) = G_SHL [[SRC]]:_, [[UREM]]:_(s24)
+  CHECK: [[SUB:%[0-9]+]]:_(s24) = G_SUB [[C1]]:_, [[UREM]]:_
+  CHECK: [[C4:%[0-9]+]]:_(s24) = G_CONSTANT i24 1
+  CHECK: [[LSHR:%[0-9]+]]:_(s24) = G_LSHR [[SRC]]:_, [[C4]]:_(s24)
+  CHECK: [[LSHR2:%[0-9]+]]:_(s24) = G_LSHR [[LSHR]]:_, [[SUB]]:_(s24)
+  CHECK: G_OR [[SHL]]:_, [[LSHR2]]:_
+  )";
+
+  // Check
+  EXPECT_TRUE(CheckMachineFunction(*MF, CheckStr)) << *MF;
+}
+
+// Test vector G_ROTR lowering.
+TEST_F(AArch64GISelMITest, LowerRotatesVector) {
+  setUp();
+  if (!TM)
+    return;
+
+  // Declare your legalization info
+  DefineLegalizerInfo(A, {
+    getActionDefinitionsBuilder({G_ROTR, G_ROTL}).lower(); });
+
+  LLT S32 = LLT::scalar(32);
+  LLT V4S32 = LLT::vector(4, S32);
+  auto SrcTrunc = B.buildTrunc(S32, Copies[0]);
+  auto Src = B.buildSplatVector(V4S32, SrcTrunc);
+  auto AmtTrunc = B.buildTrunc(S32, Copies[1]);
+  auto Amt = B.buildSplatVector(V4S32, AmtTrunc);
+  auto ROTR = B.buildInstr(TargetOpcode::G_ROTR, {V4S32}, {Src, Amt});
+
+  AInfo Info(MF->getSubtarget());
+  DummyGISelObserver Observer;
+  LegalizerHelper Helper(*MF, Info, Observer, B);
+  // Perform Legalization
+  EXPECT_EQ(LegalizerHelper::LegalizeResult::Legalized,
+            Helper.lower(*ROTR, 0, V4S32));
+
+  auto CheckStr = R"(
+  CHECK: [[SRCTRUNC:%[0-9]+]]:_(s32) = G_TRUNC
+  CHECK: [[SRC:%[0-9]+]]:_(<4 x s32>) = G_BUILD_VECTOR [[SRCTRUNC]]
+  CHECK: [[AMTTRUNC:%[0-9]+]]:_(s32) = G_TRUNC
+  CHECK: [[AMT:%[0-9]+]]:_(<4 x s32>) = G_BUILD_VECTOR [[AMTTRUNC]]
+  CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 0
+  CHECK: [[ZERO:%[0-9]+]]:_(<4 x s32>) = G_BUILD_VECTOR [[C]]
+  CHECK: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 31
+  CHECK: [[VEC31:%[0-9]+]]:_(<4 x s32>) = G_BUILD_VECTOR [[C1]]
+  CHECK: [[SUB:%[0-9]+]]:_(<4 x s32>) = G_SUB [[ZERO]]:_, [[AMT]]:_
+  CHECK: [[AND:%[0-9]+]]:_(<4 x s32>) = G_AND [[AMT]]:_, [[VEC31]]:_
+  CHECK: [[LSHR:%[0-9]+]]:_(<4 x s32>) = G_LSHR [[SRC]]:_, [[AND]]:_(<4 x s32>)
+  CHECK: [[AND1:%[0-9]+]]:_(<4 x s32>) = G_AND [[SUB]]:_, [[VEC31]]:_
+  CHECK: [[SHL:%[0-9]+]]:_(<4 x s32>) = G_SHL [[SRC]]:_, [[AND1]]:_(<4 x s32>)
+  CHECK: G_OR [[LSHR]]:_, [[SHL]]:_
+  )";
+
+  // Check
+  EXPECT_TRUE(CheckMachineFunction(*MF, CheckStr)) << *MF;
+}
+
 // Test CTTZ expansion when CTTZ_ZERO_UNDEF is legal or custom,
 // in which case it becomes CTTZ_ZERO_UNDEF with select.
 TEST_F(AArch64GISelMITest, LowerBitCountingCTTZ0) {
   setUp();
   if (!TM)
     return;
 
   // Declare your legalization info