[GISel] Add new combines for G_ADD

[mkitzan]

Summary

Patch adds new GICombineRules for G_ADD:

• G_ADD(x, G_SUB(y, x)) -> y
• G_ADD(G_SUB(y, x), x) -> y

Patch additionally adds new combine tests for AArch64 target for these new rules.

[tschuett]

Out of curiosity, is the first rule a win or canonicalisation?

[arsenm]

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

415

APInt to allow it to work for wide integers?

llvm/test/CodeGen/AArch64/GlobalISel/combine-add.mir

86

Add an s128 case? This currently won't work for vectors, but it would be nice to handle a few vector tests too

llvm/test/CodeGen/AMDGPU/GlobalISel/extractelement.i128.ll

23–24 ↗

(On Diff #292884)

I don't understand where this regression came from (but isn't particularly important)

54–62 ↗

(On Diff #292884)

This is a much more interesting regression

[mkitzan]

In D87936#2282772, @tschuett wrote:

Out of curiosity, is the first rule a win or canonicalisation?

Primarily canonicalization, however depending on the target there can be perf wins. By eliminating the signed constant, there's a better chance the constant can be folded into the opcode as an immediate operand rather than being loaded into a register before being used (if the target supports immediate operands, otherwise nothing lost, eh?).

Assume hypothetical target only supports 2b immediate operands to arithmetic ops and registers are 8b. Here's an example where the combine is a perf win.

mov r1, -1
add r0, r1
---
sub r0, 1

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

415

Make sense, will add

llvm/test/CodeGen/AArch64/GlobalISel/combine-add.mir

86

Will add an s128 and a vector test case for each of these

llvm/test/CodeGen/AMDGPU/GlobalISel/extractelement.i128.ll

54–62 ↗

(On Diff #292884)

I noticed regressions in this test file too. The combine causing them is the: G_ADD(x, y) -> G_OR(x, y) (iff x and y share no common bits). That combine rule is the cause of nearly all the AMDGPU test changes (with the exception of three or four tests).

[arsenm]

llvm/test/CodeGen/AMDGPU/GlobalISel/extractelement.i128.ll

54–62 ↗

(On Diff #292884)

So we need the equivalent utility for SelectionDAG::isBaseWithConstantOffset(

[mkitzan]

llvm/test/CodeGen/AMDGPU/GlobalISel/extractelement.i128.ll

54–62 ↗

(On Diff #292884)

Not quite sure where that fits into the implementation of the combine. The added GlobalISel/Utils.cpp:haveNoCommonBitsSet acts the same as SelectionDAG.pp:haveNoCommonBitsSet which is used to gate the DAG combine version (x + y) -> (x | y) iff x and y share no bits.

[mkitzan]

• Changed G_ADD(x, -cst) -> G_SUB(x, cst) to use APInt
• Added vector and s128 test cases (though some combines don't fire with these input types)

[arsenm]

llvm/test/CodeGen/AMDGPU/GlobalISel/extractelement.i128.ll

54–62 ↗

(On Diff #292884)

It's not for the combine itself, it's for all of the other code to deal with the side effect of it. In general this is a terrible combine because nobody expects adds to turn into ors. Without a utility function you can easily use to match adds that were turned into ors, I think it's generally worse to do this combine. I think having this utility function is a prerequisite for this

[mkitzan]

I can remove the G_ADD(x, y)->G_OR(x, y) combine if that's a blocker. Let me know if there's anything else specifically blocking the approval of this patch.

[mkitzan]

Updates:

• Rebased patch
• Removed G_ADD(x, y) -> G_OR(x, y) combine
• Exchanged my custom applyAddSubSameReg function for replaceSingleDefInstWithReg
• Add @aemerson and @foad to reviewers list

[arsenm]

I do think the add -> or has some value, but it should be separate with the helper function

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

5638–5643

Probably should use m_match here (maybe even have a negative constant matcher)

[mkitzan]

Good point about using mi_match, updated the diff.

Can work on the add -> or combine + helper function in a future patch. Better to not block committing the simpler combines.

[foad]

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

739

Does SelectionDAG do this? I suppose it can be useful to canonicalize, but my gut feeling is that it would be better to do the converse, i.e. canonicalize G_SUB(x, cst) -> G_ADD(x, -cst). That way you are canonicalizing on using G_ADD instead of G_SUB wherever possible, which feels more useful than using positive constants instead of negative constants wherever possible. E.g. if you're writing a pattern to match a "reg + simm" addressing mode you would only need to match G_ADD.

[mkitzan]

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

739

No, I can't seem to find it in DAGCombiner. Would you rather it be removed from the patch?

[arsenm]

I think addressing modes are less of a factor given that g_ptr_add is separate

[arsenm]

In D87936#3525578, @arsenm wrote:

I think addressing modes are less of a factor given that g_ptr_add is separate

I guess this breaks down as soon as you have a 2 component mode

[mkitzan]

I'll remove that combine as well. If there's more discussion and it's found to be beneficial then I can open another revision for it.

[mkitzan]

Updates:

• Removed G_ADD(x, -cst) -> G_SUB(x, cst)
• Very minor NFC addressing https://reviews.llvm.org/D125819#inline-1207969

[paquette]

I think this looks reasonable now? I basically only have one nit.

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

5644

FYI, in Register.h:

/// Wrapper class representing virtual and physical registers. Should be passed
/// by value.
class Register {
  unsigned Reg;

Since neither MaybeSub nor MaybeSameReg is being mutated, they might as well be passed by value.

[mkitzan]

Thanks for the review @paquette. I'll update the diff addressing your nit when I push the patch

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

public:
   /// Transform trunc (shl x, K) to shl (trunc x),
   /// K => K < VT.getScalarSizeInBits().
   bool matchCombineTruncOfShl(MachineInstr &MI,
                               std::pair<Register, Register> &MatchInfo);
   void applyCombineTruncOfShl(MachineInstr &MI,
                               std::pair<Register, Register> &MatchInfo);
 
   /// Transform G_MUL(x, -1) to G_SUB(0, x)
   void applyCombineMulByNegativeOne(MachineInstr &MI);
 
   /// Return true if any explicit use operand on \p MI is defined by a
   /// G_IMPLICIT_DEF.
   bool matchAnyExplicitUseIsUndef(MachineInstr &MI);
 
   /// Return true if all register explicit use operands on \p MI are defined by
   /// a G_IMPLICIT_DEF.
   bool matchAllExplicitUsesAreUndef(MachineInstr &MI);
public:
   bool matchCombineFSubFpExtFNegFMulToFMadOrFMA(MachineInstr &MI,
                                                 BuildFnTy &MatchInfo);
 
   /// Fold boolean selects to logical operations.
   bool matchSelectToLogical(MachineInstr &MI, BuildFnTy &MatchInfo);
 
   bool matchCombineFMinMaxNaN(MachineInstr &MI, unsigned &Info);
 
+  /// Transform G_ADD(x, G_SUB(y, x)) to y.
+  /// Transform G_ADD(G_SUB(y, x), x) to y.
+  bool matchAddSubSameReg(MachineInstr &MI, Register &Src);
+
 private:
   /// Given a non-indexed load or store instruction \p MI, find an offset that
   /// can be usefully and legally folded into it as a post-indexing operation.
   ///
   /// \returns true if a candidate is found.
   bool findPostIndexCandidate(MachineInstr &MI, Register &Addr, Register &Base,
                               Register &Offset);
 

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

 //           (fneg (fma (fpext x), (fpext y), z))
 def combine_fsub_fpext_fneg_fmul_to_fmad_or_fma: GICombineRule<
   (defs root:$root, build_fn_matchinfo:$info),
   (match (wip_match_opcode G_FSUB):$root,
          [{ return Helper.matchCombineFSubFpExtFNegFMulToFMadOrFMA(
                                             *${root}, ${info}); }]),
   (apply [{ Helper.applyBuildFn(*${root}, ${info}); }])>;
 
-def combine_minmax_nan_matchinfo: GIDefMatchData<"unsigned">;
 def combine_minmax_nan: GICombineRule<
-  (defs root:$root, combine_minmax_nan_matchinfo:$info),
+  (defs root:$root, unsigned_matchinfo:$info),
   (match (wip_match_opcode G_FMINNUM, G_FMAXNUM, G_FMINIMUM, G_FMAXIMUM):$root,
          [{ return Helper.matchCombineFMinMaxNaN(*${root}, ${info}); }]),
   (apply [{ Helper.replaceSingleDefInstWithOperand(*${root}, ${info}); }])>;
 
+// Transform (add x, (sub y, x)) -> y
+// Transform (add (sub y, x), x) -> y
+def add_sub_reg: GICombineRule <
+  (defs root:$root, register_matchinfo:$matchinfo),
+  (match (wip_match_opcode G_ADD):$root,
+         [{ return Helper.matchAddSubSameReg(*${root}, ${matchinfo}); }]),
+  (apply [{ return Helper.replaceSingleDefInstWithReg(*${root},
+                                                      ${matchinfo}); }])>;
+
 // 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,
                                      binop_right_undef_to_undef,
                                      propagate_undef_any_op,
                                      propagate_undef_all_ops,
                                      propagate_undef_shuffle_mask,
                                      erase_undef_store,
                                      unmerge_undef]>;
 
 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]>;
+                                        fneg_fneg_fold, right_identity_one,
+                                        add_sub_reg]>;
 
 def const_combines : GICombineGroup<[constant_fp_op, const_ptradd_to_i2p,
                                      overlapping_and, mulo_by_2, mulo_by_0,
                                      addo_by_0, combine_minmax_nan]>;
 
 def known_bits_simplifications : GICombineGroup<[
   redundant_and, redundant_sext_inreg, redundant_or, urem_pow2_to_mask,
   zext_trunc_fold, icmp_to_true_false_known_bits, icmp_to_lhs_known_bits]>;

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

if (!MaybeCst || !MaybeCst->getValueAPF().isNaN())
       return false;
     IdxToPropagate = PropagateNaN ? Idx : (Idx == 1 ? 2 : 1);
     return true;
   };
 
   return MatchNaN(1) || MatchNaN(2);
 }
 
+bool CombinerHelper::matchAddSubSameReg(MachineInstr &MI, Register &Src) {
+  assert(MI.getOpcode() == TargetOpcode::G_ADD && "Expected a G_ADD");
+  Register LHS = MI.getOperand(1).getReg();
+  Register RHS = MI.getOperand(2).getReg();
+
+  // Helper lambda to check for opportunities for
+  // A + (B - A) -> B
+  // (B - A) + A -> B
+  auto CheckFold = [&](Register MaybeSub, Register MaybeSameReg) {
+    Register Reg;
+    return mi_match(MaybeSub, MRI, m_GSub(m_Reg(Src), m_Reg(Reg))) &&
+           Reg == MaybeSameReg;
+  };
+  return CheckFold(LHS, RHS) || CheckFold(RHS, LHS);
+}
+
 bool CombinerHelper::tryCombine(MachineInstr &MI) {
   if (tryCombineCopy(MI))
     return true;
   if (tryCombineExtendingLoads(MI))
     return true;
   if (tryCombineIndexedLoadStore(MI))
     return true;
   return false;
 }

llvm/test/CodeGen/AArch64/GlobalISel/combine-add.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -run-pass=aarch64-prelegalizer-combiner -verify-machineinstrs -mtriple aarch64-unknown-unknown %s -o - | FileCheck %s
+
+---
+name:            add_lhs_sub_reg
+alignment:       4
+tracksRegLiveness: true
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    liveins: $w0, $w1
+    ; CHECK-LABEL: name: add_lhs_sub_reg
+    ; CHECK: liveins: $w0, $w1
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(s32) = COPY $w0
+    ; CHECK-NEXT: $w0 = COPY [[COPY]](s32)
+    %0:_(s32) = COPY $w0
+    %1:_(s32) = COPY $w1
+    %2:_(s32) = G_SUB %0, %1
+    %3:_(s32) = G_ADD %2, %1
+    $w0 = COPY %3
+...
+---
+name:            add_lhs_sub_reg_wide
+alignment:       4
+tracksRegLiveness: true
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    liveins: $q0, $q1
+    ; CHECK-LABEL: name: add_lhs_sub_reg_wide
+    ; CHECK: liveins: $q0, $q1
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(s128) = COPY $q0
+    ; CHECK-NEXT: $q0 = COPY [[COPY]](s128)
+    %0:_(s128) = COPY $q0
+    %1:_(s128) = COPY $q1
+    %2:_(s128) = G_SUB %0, %1
+    %3:_(s128) = G_ADD %2, %1
+    $q0 = COPY %3
+...
+---
+name:            add_lhs_sub_reg_vec
+alignment:       4
+tracksRegLiveness: true
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    liveins: $x0, $x1
+    ; CHECK-LABEL: name: add_lhs_sub_reg_vec
+    ; CHECK: liveins: $x0, $x1
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(<4 x s16>) = COPY $x0
+    ; CHECK-NEXT: $x0 = COPY [[COPY]](<4 x s16>)
+    %0:_(<4 x s16>) = COPY $x0
+    %1:_(<4 x s16>) = COPY $x1
+    %2:_(<4 x s16>) = G_SUB %0, %1
+    %3:_(<4 x s16>) = G_ADD %2, %1
+    $x0 = COPY %3
+...
+---
+name:            add_rhs_sub_reg
+alignment:       4
+tracksRegLiveness: true
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    liveins: $w0, $w1
+    ; CHECK-LABEL: name: add_rhs_sub_reg
+    ; CHECK: liveins: $w0, $w1
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(s32) = COPY $w0
+    ; CHECK-NEXT: $w0 = COPY [[COPY]](s32)
+    %0:_(s32) = COPY $w0
+    %1:_(s32) = COPY $w1
+    %2:_(s32) = G_SUB %0, %1
+    %3:_(s32) = G_ADD %1, %2
+    $w0 = COPY %3
+...
+---
+name:            add_rhs_sub_reg_wide
+alignment:       4
+tracksRegLiveness: true
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    liveins: $q0, $q1
+    ; CHECK-LABEL: name: add_rhs_sub_reg_wide
+    ; CHECK: liveins: $q0, $q1
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(s128) = COPY $q0
+    ; CHECK-NEXT: $q0 = COPY [[COPY]](s128)
+    %0:_(s128) = COPY $q0
+    %1:_(s128) = COPY $q1
+    %2:_(s128) = G_SUB %0, %1
+    %3:_(s128) = G_ADD %1, %2
+    $q0 = COPY %3
+...
+---
+name:            add_rhs_sub_reg_vec
+alignment:       4
+tracksRegLiveness: true
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    liveins: $x0, $x1
+    ; CHECK-LABEL: name: add_rhs_sub_reg_vec
+    ; CHECK: liveins: $x0, $x1
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(<4 x s16>) = COPY $x0
+    ; CHECK-NEXT: $x0 = COPY [[COPY]](<4 x s16>)
+    %0:_(<4 x s16>) = COPY $x0
+    %1:_(<4 x s16>) = COPY $x1
+    %2:_(<4 x s16>) = G_SUB %0, %1
+    %3:_(<4 x s16>) = G_ADD %1, %2
+    $x0 = COPY %3
+...