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

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

3922

I think one off MIRBuilders should never be used

[aemerson]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

3922

What do you suggest here instead?

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

3922

The combiner helper should have a universal builder

[paquette]

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

5

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

3922

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

3922

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

3922

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

3922

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

3922

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

622

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

3916–3917

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 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]>;
 
 // 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,
                                      erase_undef_store]>;
 
 def identity_combines : GICombineGroup<[select_same_val, right_identity_zero,
                                         binop_same_val, binop_left_to_zero,
                                         binop_right_to_zero, p2i_to_i2p,
                                         i2p_to_p2i, anyext_trunc_fold,
                                         fneg_fneg_fold, right_identity_one]>;

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

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();
+  Register AmtReg = MI.getOperand(2).getReg();
+  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, AmtReg, 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);
+  Amt = Builder.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/lib/Target/AArch64/GISel/AArch64PostLegalizerCombiner.cpp

void AArch64PostLegalizerCombiner::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<TargetPassConfig>();
   AU.setPreservesCFG();
   getSelectionDAGFallbackAnalysisUsage(AU);
   AU.addRequired<GISelKnownBitsAnalysis>();
   AU.addPreserved<GISelKnownBitsAnalysis>();
   if (!IsOptNone) {
     AU.addRequired<MachineDominatorTree>();
     AU.addPreserved<MachineDominatorTree>();
+    AU.addRequired<GISelCSEAnalysisWrapperPass>();
+    AU.addPreserved<GISelCSEAnalysisWrapperPass>();
   }
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
 AArch64PostLegalizerCombiner::AArch64PostLegalizerCombiner(bool IsOptNone)
     : MachineFunctionPass(ID), IsOptNone(IsOptNone) {
   initializeAArch64PostLegalizerCombinerPass(*PassRegistry::getPassRegistry());
 }
bool AArch64PostLegalizerCombiner::runOnMachineFunction(MachineFunction &MF) {
   const Function &F = MF.getFunction();
   bool EnableOpt =
       MF.getTarget().getOptLevel() != CodeGenOpt::None && !skipFunction(F);
   GISelKnownBits *KB = &getAnalysis<GISelKnownBitsAnalysis>().get(MF);
   MachineDominatorTree *MDT =
       IsOptNone ? nullptr : &getAnalysis<MachineDominatorTree>();
   AArch64PostLegalizerCombinerInfo PCInfo(EnableOpt, F.hasOptSize(),
                                           F.hasMinSize(), KB, MDT);
+  GISelCSEAnalysisWrapper &Wrapper =
+      getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
+  auto *CSEInfo = &Wrapper.get(TPC->getCSEConfig());
   Combiner C(PCInfo, TPC);
-  return C.combineMachineInstrs(MF, /*CSEInfo*/ nullptr);
+  return C.combineMachineInstrs(MF, CSEInfo);
 }
 
 char AArch64PostLegalizerCombiner::ID = 0;
 INITIALIZE_PASS_BEGIN(AArch64PostLegalizerCombiner, DEBUG_TYPE,
                       "Combine AArch64 MachineInstrs after legalization", false,
                       false)
 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
 INITIALIZE_PASS_DEPENDENCY(GISelKnownBitsAnalysis)

llvm/test/CodeGen/AArch64/GlobalISel/form-bitfield-extract-from-sextinreg.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 can fold a G_SEXT_INREG fed by a G_ASHR/G_LSHR into a G_SBFX.
 
 ...
 ---
 name:            sextinreg_ashr_to_sbfx
 tracksRegLiveness: true
 legalized: true
 body:             |
   bb.0:
     liveins: $w0
     ; CHECK-LABEL: name: sextinreg_ashr_to_sbfx
     ; CHECK: liveins: $w0
     ; CHECK: %x:_(s32) = COPY $w0
-    ; CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 5
-    ; CHECK: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 14
-    ; CHECK: %sext_inreg:_(s32) = G_SBFX %x, [[C]](s32), [[C1]]
+    ; CHECK: %lsb:_(s32) = G_CONSTANT i32 5
+    ; CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 14
+    ; CHECK: %sext_inreg:_(s32) = G_SBFX %x, %lsb(s32), [[C]]
     ; CHECK: $w0 = COPY %sext_inreg(s32)
     ; CHECK: RET_ReallyLR implicit $w0
     %x:_(s32) = COPY $w0
     %lsb:_(s32) = G_CONSTANT i32 5
     %shift:_(s32) = G_ASHR %x, %lsb
     %sext_inreg:_(s32) = G_SEXT_INREG %shift, 10
     $w0 = COPY %sext_inreg
     RET_ReallyLR implicit $w0
 
 ...
 ---
 name:            sextinreg_lshr_to_sbfx
 tracksRegLiveness: true
 legalized: true
 body:             |
   bb.0:
     liveins: $w0
     ; CHECK-LABEL: name: sextinreg_lshr_to_sbfx
     ; CHECK: liveins: $w0
     ; CHECK: %x:_(s32) = COPY $w0
-    ; CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 5
-    ; CHECK: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 14
-    ; CHECK: %sext_inreg:_(s32) = G_SBFX %x, [[C]](s32), [[C1]]
+    ; CHECK: %lsb:_(s32) = G_CONSTANT i32 5
+    ; CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 14
+    ; CHECK: %sext_inreg:_(s32) = G_SBFX %x, %lsb(s32), [[C]]
     ; CHECK: $w0 = COPY %sext_inreg(s32)
     ; CHECK: RET_ReallyLR implicit $w0
     %x:_(s32) = COPY $w0
     %lsb:_(s32) = G_CONSTANT i32 5
     %shift:_(s32) = G_LSHR %x, %lsb
     %sext_inreg:_(s32) = G_SEXT_INREG %shift, 10
     $w0 = COPY %sext_inreg
     RET_ReallyLR implicit $w0

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
+
+...
+---
+name:            rotl_bitwidth_cst
+alignment:       4
+legalized:       true
+tracksRegLiveness: true
+liveins:
+  - { reg: '$w0' }
+body:             |
+  bb.1.entry:
+    liveins: $w0
+
+    ; CHECK-LABEL: name: rotl_bitwidth_cst
+    ; CHECK: liveins: $w0
+    ; CHECK: [[COPY:%[0-9]+]]:_(s32) = COPY $w0
+    ; CHECK: [[C:%[0-9]+]]:_(s64) = G_CONSTANT i64 0
+    ; 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 32
+    %2:_(s32) = G_ROTL %0, %5(s64)
+    $w0 = COPY %2(s32)
+    RET_ReallyLR implicit $w0
+
+...
+---
+name:            rotl_bitwidth_minus_one_cst
+alignment:       4
+legalized:       true
+tracksRegLiveness: true
+liveins:
+  - { reg: '$w0' }
+body:             |
+  bb.1.entry:
+    liveins: $w0
+
+    ; CHECK-LABEL: name: rotl_bitwidth_minus_one_cst
+    ; CHECK: liveins: $w0
+    ; CHECK: [[COPY:%[0-9]+]]:_(s32) = COPY $w0
+    ; CHECK: [[C:%[0-9]+]]:_(s64) = G_CONSTANT i64 31
+    ; 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 31
+    %2:_(s32) = G_ROTL %0, %5(s64)
+    $w0 = COPY %2(s32)
+    RET_ReallyLR implicit $w0
+
+...