[GlobalISel] Simplify G_ADD when it has (0-X) on the LHS or RHS

[paquette]

Summary

This implements the following combines:

((0-A) + B) -> B-A
(A + (0-B)) -> A-B

Porting over the basic algebraic combines from the DAGCombiner. There are several combines which fold adds away into subtracts. This is just the simplest one.

I noticed that add combines are some of the most commonly hit across CTMark, (via print statements when they fire), so I'm porting over some of the obvious ones.

This gives some minor code size improvements on CTMark at -O3 on AArch64.

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

1701

Should this preserve any flags?

[paquette]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

1701

In the DAGCombiner, it doesn't seem to:

// fold ((0-A) + B) -> B-A
if (N0.getOpcode() == ISD::SUB && isNullOrNullSplat(N0.getOperand(0)))
  return DAG.getNode(ISD::SUB, DL, VT, N1, N0.getOperand(1));

but maybe we should? It would make sense.

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

1701

Nobody ever really went back to preserve flags in DAGCombiner (to some degree for FP ops). I would check what InstCombine does

[arsenm]

LGTM. InstCombine seems to not preserve flags in this case

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

1686–1687

We should add an m_Zero() at some point

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

public:
   bool matchBinOpSameVal(MachineInstr &MI);
 
   /// Check if operand \p OpIdx is zero.
   bool matchOperandIsZero(MachineInstr &MI, unsigned OpIdx);
 
   /// Erase \p MI
   bool eraseInst(MachineInstr &MI);
 
+  /// Return true if MI is a G_ADD which can be simplified to a G_SUB.
+  bool matchSimplifyAddToSub(MachineInstr &MI,
+                             std::tuple<Register, Register> &MatchInfo);
+  bool applySimplifyAddToSub(MachineInstr &MI,
+                             std::tuple<Register, Register> &MatchInfo);
+
   /// 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,
                       unsigned KnownLen, Align DstAlign, Align SrcAlign,

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

 // Erase stores of undef values.
 def erase_undef_store : GICombineRule<
   (defs root:$root),
   (match (wip_match_opcode G_STORE):$root,
     [{ return Helper.matchUndefStore(*${root}); }]),
   (apply [{ return Helper.eraseInst(*${root}); }])
 >;
 
+def simplify_add_to_sub_matchinfo: GIDefMatchData<"std::tuple<Register, Register>">;
+def simplify_add_to_sub: GICombineRule <
+  (defs root:$root, simplify_add_to_sub_matchinfo:$info),
+  (match (wip_match_opcode G_ADD):$root,
+    [{ return Helper.matchSimplifyAddToSub(*${root}, ${info}); }]),
+  (apply [{ return Helper.applySimplifyAddToSub(*${root}, ${info});}])
+>;
+
 // 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,
                                      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]>;
 
 def trivial_combines : GICombineGroup<[copy_prop, mul_to_shl]>;
 def all_combines : GICombineGroup<[trivial_combines, ptr_add_immed_chain,
     combines_for_extload, combine_indexed_load_store, undef_combines,
-    identity_combines]>;
+    identity_combines, simplify_add_to_sub]>;

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

 bool CombinerHelper::replaceInstWithUndef(MachineInstr &MI) {
   assert(MI.getNumDefs() == 1 && "Expected only one def?");
   Builder.setInstr(MI);
   Builder.buildUndef(MI.getOperand(0));
   MI.eraseFromParent();
   return true;
 }
 
+bool CombinerHelper::matchSimplifyAddToSub(
+    MachineInstr &MI, std::tuple<Register, Register> &MatchInfo) {
+  Register LHS = MI.getOperand(1).getReg();
+  Register RHS = MI.getOperand(2).getReg();
+  Register &NewLHS = std::get<0>(MatchInfo);
+  Register &NewRHS = std::get<1>(MatchInfo);
+
+  // Helper lambda to check for opportunities for
+  // ((0-A) + B) -> B - A
+  // (A + (0-B)) -> A - B
+  auto CheckFold = [&](Register &MaybeSub, Register &MaybeNewLHS) {
+    int64_t Cst;
+    if (!mi_match(MaybeSub, MRI, m_GSub(m_ICst(Cst), m_Reg(NewRHS))) ||
+        Cst != 0)
+      return false;
+    NewLHS = MaybeNewLHS;
+    return true;
+  };
+
+  return CheckFold(LHS, RHS) || CheckFold(RHS, LHS);
+}
+
+bool CombinerHelper::applySimplifyAddToSub(
+    MachineInstr &MI, std::tuple<Register, Register> &MatchInfo) {
+  Builder.setInstr(MI);
+  Register SubLHS, SubRHS;
+  std::tie(SubLHS, SubRHS) = MatchInfo;
+  Builder.buildSub(MI.getOperand(0).getReg(), SubLHS, SubRHS);
+  MI.eraseFromParent();
+  return true;
+}
+
 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/prelegalizercombiner-simplify-add.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple aarch64 -run-pass=aarch64-prelegalizer-combiner -verify-machineinstrs %s -o - | FileCheck %s
+
+name:            pat1
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $x0, $x1
+    ; Fold ((0-A) + B) -> B - A
+    ; CHECK-LABEL: name: pat1
+    ; CHECK: liveins: $x0, $x1
+    ; CHECK: %copy1:_(s64) = COPY $x0
+    ; CHECK: %copy2:_(s64) = COPY $x1
+    ; CHECK: %add:_(s64) = G_SUB %copy2, %copy1
+    ; CHECK: $x0 = COPY %add(s64)
+    ; CHECK: RET_ReallyLR implicit $x0
+    %copy1:_(s64) = COPY $x0
+    %copy2:_(s64) = COPY $x1
+    %zero:_(s64) = G_CONSTANT i64 0
+    %sub:_(s64) = G_SUB %zero, %copy1
+    %add:_(s64) = G_ADD %sub, %copy2
+    $x0 = COPY %add(s64)
+    RET_ReallyLR implicit $x0
+
+...
+---
+name:            pat2
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $x0, $x1
+    ; Fold (A + (0-B)) -> A - B
+    ; CHECK-LABEL: name: pat2
+    ; CHECK: liveins: $x0, $x1
+    ; CHECK: %copy1:_(s64) = COPY $x0
+    ; CHECK: %copy2:_(s64) = COPY $x1
+    ; CHECK: %add:_(s64) = G_SUB %copy1, %copy2
+    ; CHECK: $x0 = COPY %add(s64)
+    ; CHECK: RET_ReallyLR implicit $x0
+    %copy1:_(s64) = COPY $x0
+    %copy2:_(s64) = COPY $x1
+    %zero:_(s64) = G_CONSTANT i64 0
+    %sub:_(s64) = G_SUB %zero, %copy2
+    %add:_(s64) = G_ADD %copy1, %sub
+    $x0 = COPY %add(s64)
+    RET_ReallyLR implicit $x0
+
+...