[AArch64][GlobalISel] Simplify out of range rotate amount.

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

3924

I think one off MIRBuilders should never be used

[aemerson]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

3924

What do you suggest here instead?

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

3924

The combiner helper should have a universal builder

[paquette]

llvm/test/CodeGen/AArch64/GlobalISel/postlegalizercombiner-rotate.mir

4

Maybe a couple boundary tests would be nice here?

G_CONSTANT == bit size, G_CONSTANT == bit size - 1?

[aemerson]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

3924

The universal builder is a CSE one, and I need a constant folding one here. Maybe CSE should do it too?

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

3924

I honestly don't see the point of having all of these MIRBuilder flavors. Why don't we have just one that does everything?

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

3924

I thought the CSE builder did do constant folding. Also can't you just directly call the constant folding utility function?

[foad]

What's the point of this? Does it somehow end up generating better code?

If it is useful, you could also do the same for FSHL and FSHR.

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

3924

Yes the CSE builder does constant folding. I think ConstantFoldingMIRBuilder should be deleted. It's unused and I was told it was just an experiment.

[aemerson]

In D101005#2707670, @foad wrote:

What's the point of this? Does it somehow end up generating better code?

If it is useful, you could also do the same for FSHL and FSHR.

It allows us to select immediate forms of rotate instructions for AArch64.

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

3924

Thanks, I hadn't realized since we didn't enable CSEInfo for this combiner pass so it wasn't working.

[aemerson]

• Add more tests.
• Factor out the APInt checking part of the constant folder to be used as a query.
• Enable CSEInfo in the postlegalizer combiner so that we don't have to instantiate a constant-folding MIRBuilder.

[foad]

What's the point of this? Does it somehow end up generating better code?

It allows us to select immediate forms of rotate instructions for AArch64.

I would expect most targets to handle that during instruction selection by ignoring the high bits of the rotate amount, but perhaps there's some reason why it's awkward to do that for AArch64. Would it make sense for your new combine to be completely AArch64-specific? Currently you have added it to all_combines so it will be run on other targets too.

llvm/include/llvm/Target/GlobalISel/Combine.td

615

Seems a bit odd to include this in "funnel_shift_combines" since it doesn't actually touch funnel shifts.

[aemerson]

In D101005#2711425, @foad wrote:

What's the point of this? Does it somehow end up generating better code?

It allows us to select immediate forms of rotate instructions for AArch64.

I would expect most targets to handle that during instruction selection by ignoring the high bits of the rotate amount, but perhaps there's some reason why it's awkward to do that for AArch64. Would it make sense for your new combine to be completely AArch64-specific? Currently you have added it to all_combines so it will be run on other targets too.

That's possible, but I assumed that generic code wanted this since this is already done in DAGCombine for rotates.

[aemerson]

Only run this for AArch64.

[foad]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

3918–3919

Why not just return true? Why would this ever fail?

[aemerson]

Remove constant folding check.

[foad]

Looks fine to me. Could also do it for funnel shifts if you want.

[aemerson]

In D101005#2725074, @foad wrote:

Looks fine to me. Could also do it for funnel shifts if you want.

Thanks. We lower funnel shifts though so it's not something we can test for AArch64.

llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h

void applyExtractAllEltsFromBuildVector(
       MachineInstr &MI,
       SmallVectorImpl<std::pair<Register, MachineInstr *>> &MatchInfo);
 
   /// Use a function which takes in a MachineIRBuilder to perform a combine.
   bool applyBuildFn(MachineInstr &MI,
                     std::function<void(MachineIRBuilder &)> &MatchInfo);
   bool matchFunnelShiftToRotate(MachineInstr &MI);
   void applyFunnelShiftToRotate(MachineInstr &MI);
+  bool matchRotateOutOfRange(MachineInstr &MI);
+  void applyRotateOutOfRange(MachineInstr &MI);
 
   /// Try to transform \p MI by using all of the above
   /// combine functions. Returns true if changed.
   bool tryCombine(MachineInstr &MI);
 
 private:
   // Memcpy family optimization helpers.
   bool optimizeMemcpy(MachineInstr &MI, Register Dst, Register Src,

llvm/include/llvm/Target/GlobalISel/Combine.td

 
 def funnel_shift_to_rotate : GICombineRule<
   (defs root:$root),
   (match (wip_match_opcode G_FSHL, G_FSHR):$root,
     [{ return Helper.matchFunnelShiftToRotate(*${root}); }]),
   (apply [{ Helper.applyFunnelShiftToRotate(*${root}); }])
 >;
 
-def funnel_shift_combines : GICombineGroup<[funnel_shift_to_rotate]>;
+def rotate_out_of_range : GICombineRule<
+  (defs root:$root),
+  (match (wip_match_opcode G_ROTR, G_ROTL):$root,
+    [{ return Helper.matchRotateOutOfRange(*${root}); }]),
+  (apply [{ Helper.applyRotateOutOfRange(*${root}); }])
+>;
+
+def funnel_shift_combines : GICombineGroup<[funnel_shift_to_rotate, rotate_out_of_range]>;
 
 // FIXME: These should use the custom predicate feature once it lands.
 def undef_combines : GICombineGroup<[undef_to_fp_zero, undef_to_int_zero,
                                      undef_to_negative_one,
                                      binop_left_undef_to_zero,
                                      propagate_undef_any_op,
                                      propagate_undef_all_ops,
                                      propagate_undef_shuffle_mask,

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

 //===-- lib/CodeGen/GlobalISel/GICombinerHelper.cpp -----------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 #include "llvm/CodeGen/GlobalISel/CombinerHelper.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallBitVector.h"
 #include "llvm/CodeGen/GlobalISel/Combiner.h"
+#include "llvm/CodeGen/GlobalISel/ConstantFoldingMIRBuilder.h"
 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
 #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h"
 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
 #include "llvm/CodeGen/GlobalISel/MIPatternMatch.h"
 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
 #include "llvm/CodeGen/GlobalISel/Utils.h"
 #include "llvm/CodeGen/LowLevelType.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/CodeGen/TargetLowering.h"
 #include "llvm/CodeGen/TargetOpcodes.h"
+#include "llvm/Support/Casting.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Target/TargetMachine.h"
 
 #define DEBUG_TYPE "gi-combiner"
 
 using namespace llvm;
 using namespace MIPatternMatch;
 
void CombinerHelper::applyFunnelShiftToRotate(MachineInstr &MI) {
   bool IsFSHL = Opc == TargetOpcode::G_FSHL;
   Observer.changingInstr(MI);
   MI.setDesc(Builder.getTII().get(IsFSHL ? TargetOpcode::G_ROTL
                                          : TargetOpcode::G_ROTR));
   MI.RemoveOperand(2);
   Observer.changedInstr(MI);
 }
 
+// Fold (rot x, c) -> (rot x, c % BitSize)
+bool CombinerHelper::matchRotateOutOfRange(MachineInstr &MI) {
+  assert(MI.getOpcode() == TargetOpcode::G_ROTL ||
+         MI.getOpcode() == TargetOpcode::G_ROTR);
+  unsigned Bitsize =
+      MRI.getType(MI.getOperand(0).getReg()).getScalarSizeInBits();
+  bool OutOfRange = false;
+  auto MatchOutOfRange = [Bitsize, &OutOfRange](const Constant *C) {
+    if (auto *CI = dyn_cast<ConstantInt>(C))
+      OutOfRange |= CI->getValue().uge(Bitsize);
+    return true;
+  };
+  return matchUnaryPredicate(MRI, MI.getOperand(2).getReg(), MatchOutOfRange) &&
+         OutOfRange;
+}
+
+void CombinerHelper::applyRotateOutOfRange(MachineInstr &MI) {
+  assert(MI.getOpcode() == TargetOpcode::G_ROTL ||
+         MI.getOpcode() == TargetOpcode::G_ROTR);
+  unsigned Bitsize =
+      MRI.getType(MI.getOperand(0).getReg()).getScalarSizeInBits();
+  Builder.setInstrAndDebugLoc(MI);
+  Register Amt = MI.getOperand(2).getReg();
+  LLT AmtTy = MRI.getType(Amt);
+  auto Bits = Builder.buildConstant(AmtTy, Bitsize);
+  ConstantFoldingMIRBuilder CFMIB(MI);
+  Amt = CFMIB.buildURem(AmtTy, MI.getOperand(2).getReg(), Bits).getReg(0);
+  Observer.changingInstr(MI);
+  MI.getOperand(2).setReg(Amt);
+  Observer.changedInstr(MI);
+}
+
 bool CombinerHelper::tryCombine(MachineInstr &MI) {
   if (tryCombineCopy(MI))
     return true;
   if (tryCombineExtendingLoads(MI))
     return true;
   if (tryCombineIndexedLoadStore(MI))
     return true;
   return false;
 }

llvm/lib/Target/AArch64/AArch64Combine.td

 def AArch64PostLegalizerCombinerHelper
     : GICombinerHelper<"AArch64GenPostLegalizerCombinerHelper",
                        [copy_prop, erase_undef_store, combines_for_extload,
                         sext_trunc_sextload,
                         hoist_logic_op_with_same_opcode_hands,
                         redundant_and, xor_of_and_with_same_reg,
                         extractvecelt_pairwise_add, redundant_or,
                         mul_const, redundant_sext_inreg,
-                        form_bitfield_extract]> {
+                        form_bitfield_extract, rotate_out_of_range]> {
   let DisableRuleOption = "aarch64postlegalizercombiner-disable-rule";
 }

llvm/test/CodeGen/AArch64/GlobalISel/postlegalizercombiner-rotate.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple aarch64 -run-pass=aarch64-postlegalizer-combiner -verify-machineinstrs %s -o - | FileCheck %s
+
+# Check that we simplify the constant rotate amount to be in range.
+---
+name:            rotl
+alignment:       4
+legalized:       true
+tracksRegLiveness: true
+liveins:
+  - { reg: '$w0' }
+body:             |
+  bb.1.entry:
+    liveins: $w0
+
+    ; CHECK-LABEL: name: rotl
+    ; CHECK: liveins: $w0
+    ; CHECK: [[COPY:%[0-9]+]]:_(s32) = COPY $w0
+    ; CHECK: [[C:%[0-9]+]]:_(s64) = G_CONSTANT i64 16
+    ; CHECK: [[ROTL:%[0-9]+]]:_(s32) = G_ROTL [[COPY]], [[C]](s64)
+    ; CHECK: $w0 = COPY [[ROTL]](s32)
+    ; CHECK: RET_ReallyLR implicit $w0
+    %0:_(s32) = COPY $w0
+    %5:_(s64) = G_CONSTANT i64 -16
+    %2:_(s32) = G_ROTL %0, %5(s64)
+    $w0 = COPY %2(s32)
+    RET_ReallyLR implicit $w0
+
+...
+---
+name:            rotr
+alignment:       4
+legalized:       true
+tracksRegLiveness: true
+liveins:
+  - { reg: '$w0' }
+body:             |
+  bb.1.entry:
+    liveins: $w0
+
+    ; CHECK-LABEL: name: rotr
+    ; CHECK: liveins: $w0
+    ; CHECK: [[COPY:%[0-9]+]]:_(s32) = COPY $w0
+    ; CHECK: [[C:%[0-9]+]]:_(s64) = G_CONSTANT i64 16
+    ; CHECK: [[ROTR:%[0-9]+]]:_(s32) = G_ROTR [[COPY]], [[C]](s64)
+    ; CHECK: $w0 = COPY [[ROTR]](s32)
+    ; CHECK: RET_ReallyLR implicit $w0
+    %0:_(s32) = COPY $w0
+    %5:_(s64) = G_CONSTANT i64 -16
+    %2:_(s32) = G_ROTR %0, %5(s64)
+    $w0 = COPY %2(s32)
+    RET_ReallyLR implicit $w0
+
+...