[GlobalISel] Rewrite some simple rules using MIR Patterns

[Pierre-vh]

Summary

Rewrites some simple rules that cause little to no codegen regressions as MIR patterns.

I may have missed some easy cases, but some other rules have intentionally been left as-is because bigger
changes are needed to make them work.

[Pierre-vh]

Rebase

[foad]

Thanks! These are some really nice examples to study.

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

674–675

Is the order of instructions significant here? Would it still match if I wrote (match (G_FABS $dst, $tmp), (G_FNEG $tmp, $x)) instead?

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

12–14

What has caused this difference?

[Pierre-vh]

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

674–675

The order doesn't matter at all, it emits patterns by walking the "tree" from the root instruction, following the operands to their defs recursively
For instance below add_sub_reg_frags orders the patterns differently

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

12–14

Below in test_combine_select_undef_res0_res1 we have a copy $x0 instead of $x1, not sure why

[Pierre-vh]

llvm/test/CodeGen/AArch64/GlobalISel/prelegalizercombiner-not-really-equiv-insts.mir

53

It'd be nice if CSE allowed simple invariant loads, then this wouldn't be an issue, but I assume CSEing loads is not a trivial task?

[foad]

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

12–14

Oh I see, nothing has really changed in test_combine_select_same_res. Could you precommit a patch that just regenerates the checks for this file?

[Pierre-vh]

Rebase on regenerated checks

[foad]

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

364

This 2 was a bug - in G_SELECT $dst, $undef, $x, $y it was picking $x but the comment says "y".

[arsenm]

llvm/test/CodeGen/AArch64/GlobalISel/prelegalizercombiner-trivial-arith.mir

313–316

This regressed?

[arsenm]

llvm/test/CodeGen/AArch64/GlobalISel/prelegalizercombiner-trivial-arith.mir

313–316

I think I see why, this is the lack of constant folding extensions which I have a patch for. I think we need less look through handling and more consistent constant and copy folding

[aemerson]

Very nice to see the first concrete improvements!

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

public:
   bool matchCombineZextTrunc(MachineInstr &MI, Register &Reg);
 
   /// Transform [asz]ext([asz]ext(x)) to [asz]ext x.
   bool matchCombineExtOfExt(MachineInstr &MI,
                             std::tuple<Register, unsigned> &MatchInfo);
   void applyCombineExtOfExt(MachineInstr &MI,
                             std::tuple<Register, unsigned> &MatchInfo);
 
-  /// Transform fabs(fabs(x)) to fabs(x).
-  void applyCombineFAbsOfFAbs(MachineInstr &MI, Register &Src);
-
-  /// Transform fabs(fneg(x)) to fabs(x).
-  bool matchCombineFAbsOfFNeg(MachineInstr &MI, BuildFnTy &MatchInfo);
-
   /// Transform trunc ([asz]ext x) to x or ([asz]ext x) or (trunc x).
   bool matchCombineTruncOfExt(MachineInstr &MI,
                               std::pair<Register, unsigned> &MatchInfo);
   void applyCombineTruncOfExt(MachineInstr &MI,
                               std::pair<Register, unsigned> &MatchInfo);
 
   /// Transform trunc (shl x, K) to shl (trunc x), K
   ///    if K < VT.getScalarSizeInBits().

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

def select_same_val: GICombineRule<
   (defs root:$root),
   (match (wip_match_opcode G_SELECT):$root,
     [{ return Helper.matchSelectSameVal(*${root}); }]),
   (apply [{ Helper.replaceSingleDefInstWithOperand(*${root}, 2); }])
 >;
 
 // Fold (undef ? x : y) -> y
 def select_undef_cmp: GICombineRule<
-  (defs root:$root),
-  (match (wip_match_opcode G_SELECT):$root,
-    [{ return Helper.matchUndefSelectCmp(*${root}); }]),
-  (apply [{ Helper.replaceSingleDefInstWithOperand(*${root}, 2); }])
+  (defs root:$dst),
+  (match (G_IMPLICIT_DEF $undef),
+         (G_SELECT $dst, $undef, $x, $y)),
+  (apply (COPY $dst, $y))
 >;
 
 // Fold (true ? x : y) -> x
 // Fold (false ? x : y) -> y
 def select_constant_cmp_matchdata : GIDefMatchData<"unsigned">;
 def select_constant_cmp: GICombineRule<
   (defs root:$root, select_constant_cmp_matchdata:$matchinfo),
   (match (wip_match_opcode G_SELECT):$root,
(apply [{
     Register RHSReg = ${root}->getOperand(2).getReg();
     ${root}->getOperand(1).setReg(RHSReg);
     ${root}->getOperand(2).setReg(LHSReg);
     Observer.changedInstr(*${root});
   }])
 >;
 
 // Fold x op 0 -> x
+def right_identity_zero_frags : GICombinePatFrag<
+  (outs root:$dst), (ins $x),
+  !foreach(op,
+           [G_SUB, G_ADD, G_OR, G_XOR, G_SHL, G_ASHR,
+            G_LSHR, G_PTR_ADD, G_ROTL, G_ROTR],
+           (pattern (op $dst, $x, 0)))>;
 def right_identity_zero: GICombineRule<
-  (defs root:$root),
-  (match (wip_match_opcode G_SUB, G_ADD, G_OR, G_XOR, G_SHL, G_ASHR, G_LSHR,
-                           G_PTR_ADD, G_ROTL, G_ROTR):$root,
-    [{ return Helper.matchConstantOp(${root}->getOperand(2), 0); }]),
-  (apply [{ Helper.replaceSingleDefInstWithOperand(*${root}, 1); }])
+  (defs root:$dst),
+  (match (right_identity_zero_frags $dst, $lhs)),
+  (apply (COPY $dst, $lhs))
 >;
 
 // Fold x op 1 -> x
 def right_identity_one: GICombineRule<
-  (defs root:$root),
-  (match (wip_match_opcode G_MUL):$root,
-    [{ return Helper.matchConstantOp(${root}->getOperand(2), 1); }]),
-  (apply [{ Helper.replaceSingleDefInstWithOperand(*${root}, 1); }])
+  (defs root:$dst),
+  (match (G_MUL $dst, $x, 1)),
+  (apply (COPY $dst, $x))
 >;
 
 // Fold (x op x) - > x
+def binop_same_val_frags : GICombinePatFrag<
+  (outs root:$dst), (ins $x),
+  [
+    (pattern (G_AND $dst, $x, $x)),
+    (pattern (G_OR $dst, $x, $x)),
+  ]
+>;
 def binop_same_val: GICombineRule<
-  (defs root:$root),
-  (match (wip_match_opcode G_AND, G_OR):$root,
-    [{ return Helper.matchBinOpSameVal(*${root}); }]),
-  (apply [{ Helper.replaceSingleDefInstWithOperand(*${root}, 1); }])
+  (defs root:$dst),
+  (match (binop_same_val_frags $dst, $src)),
+  (apply (COPY $dst, $src))
 >;
 
 // Fold (0 op x) - > 0
 def binop_left_to_zero: GICombineRule<
   (defs root:$root),
   (match (wip_match_opcode G_SDIV, G_UDIV, G_SREM, G_UREM):$root,
     [{ return Helper.matchOperandIsZero(*${root}, 1); }]),
   (apply [{ Helper.replaceSingleDefInstWithOperand(*${root}, 1); }])
def div_rem_to_divrem : GICombineRule<
   (defs root:$root, div_rem_to_divrem_matchdata:$matchinfo),
   (match (wip_match_opcode G_SDIV, G_UDIV, G_SREM, G_UREM):$root,
     [{ return Helper.matchCombineDivRem(*${root}, ${matchinfo}); }]),
   (apply [{ Helper.applyCombineDivRem(*${root}, ${matchinfo}); }])
 >;
 
 // Fold (x op 0) - > 0
 def binop_right_to_zero: GICombineRule<
-  (defs root:$root),
-  (match (wip_match_opcode G_MUL):$root,
-    [{ return Helper.matchOperandIsZero(*${root}, 2); }]),
-  (apply [{ Helper.replaceSingleDefInstWithOperand(*${root}, 2); }])
+  (defs root:$dst),
+  (match (G_MUL $dst, $lhs, 0:$zero)),
+  (apply (COPY $dst, $zero))
 >;
 
 // 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 [{ Helper.eraseInst(*${root}); }])
def not_cmp_fold : GICombineRule<
   (defs root:$d, not_cmp_fold_matchinfo:$info),
   (match (wip_match_opcode G_XOR): $d,
   [{ return Helper.matchNotCmp(*${d}, ${info}); }]),
   (apply [{ Helper.applyNotCmp(*${d}, ${info}); }])
 >;
 
 // Fold (fneg (fneg x)) -> x.
 def fneg_fneg_fold: GICombineRule <
-  (defs root:$dst, register_matchinfo:$matchinfo),
+  (defs root:$dst),
   (match (G_FNEG $t, $src),
-         (G_FNEG $dst, $t):$mi,
-         [{ ${matchinfo} = ${src}.getReg(); return true; }]),
-  (apply [{ Helper.replaceSingleDefInstWithReg(*${mi}, ${matchinfo}); }])
+         (G_FNEG $dst, $t)),
+  (apply (COPY $dst, $src))
 >;
 
 // Fold (unmerge(merge x, y, z)) -> z, y, z.
 def unmerge_merge_matchinfo : GIDefMatchData<"SmallVector<Register, 8>">;
 def unmerge_merge : GICombineRule<
   (defs root:$d, unmerge_merge_matchinfo:$info),
   (match (wip_match_opcode G_UNMERGE_VALUES): $d,
   [{ return Helper.matchCombineUnmergeMergeToPlainValues(*${d}, ${info}); }]),
   (apply [{ Helper.applyCombineUnmergeMergeToPlainValues(*${d}, ${info}); }])
 >;
 
 // Fold merge(unmerge).
 def merge_unmerge : GICombineRule<
   (defs root:$d, register_matchinfo:$matchinfo),
   (match (wip_match_opcode G_MERGE_VALUES):$d,
   [{ return Helper.matchCombineMergeUnmerge(*${d}, ${matchinfo}); }]),
   (apply [{ Helper.replaceSingleDefInstWithReg(*${d}, ${matchinfo}); }])
 >;
 
 // Fold (fabs (fneg x)) -> (fabs x).
 def fabs_fneg_fold: GICombineRule <
-  (defs root:$root, build_fn_matchinfo:$matchinfo),
-  (match (wip_match_opcode G_FABS):$root,
-         [{ return Helper.matchCombineFAbsOfFNeg(*${root}, ${matchinfo}); }]),
-  (apply [{ Helper.applyBuildFnNoErase(*${root}, ${matchinfo}); }])>;
+  (defs root:$dst),
+  (match  (G_FNEG $tmp, $x),
+          (G_FABS $dst, $tmp)),
+  (apply (G_FABS $dst, $x))>;
 
 // Fold (unmerge cst) -> cst1, cst2, ...
 def unmerge_cst_matchinfo : GIDefMatchData<"SmallVector<APInt, 8>">;
 def unmerge_cst : GICombineRule<
   (defs root:$d, unmerge_cst_matchinfo:$info),
   (match (wip_match_opcode G_UNMERGE_VALUES): $d,
   [{ return Helper.matchCombineUnmergeConstant(*${d}, ${info}); }]),
   (apply [{ Helper.applyCombineUnmergeConstant(*${d}, ${info}); }])

 def combine_minmax_nan: GICombineRule<
   (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_frags : GICombinePatFrag<
+  (outs root:$dst), (ins $src),
+  [
+    (pattern (G_ADD $dst, $x, $tmp), (G_SUB $tmp, $src, $x)),
+    (pattern (G_ADD $dst, $tmp, $x), (G_SUB $tmp, $src, $x))
+  ]>;
 def add_sub_reg: GICombineRule <
-  (defs root:$root, register_matchinfo:$matchinfo),
-  (match (wip_match_opcode G_ADD):$root,
-         [{ return Helper.matchAddSubSameReg(*${root}, ${matchinfo}); }]),
-  (apply [{ Helper.replaceSingleDefInstWithReg(*${root},
-                                                      ${matchinfo}); }])>;
+  (defs root:$dst),
+  (match (add_sub_reg_frags $dst, $src)),
+  (apply (COPY $dst, $src))>;
 
 def buildvector_identity_fold : GICombineRule<
   (defs root:$build_vector, register_matchinfo:$matchinfo),
   (match (wip_match_opcode G_BUILD_VECTOR_TRUNC, G_BUILD_VECTOR):$build_vector,
          [{ return Helper.matchBuildVectorIdentityFold(*${build_vector}, ${matchinfo}); }]),
   (apply [{ Helper.replaceSingleDefInstWithReg(*${build_vector}, ${matchinfo}); }])>;
 
 def trunc_buildvector_fold : GICombineRule<

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

void CombinerHelper::applyCombineMulByNegativeOne(MachineInstr &MI) {
   LLT DstTy = MRI.getType(DstReg);
 
   Builder.setInstrAndDebugLoc(MI);
   Builder.buildSub(DstReg, Builder.buildConstant(DstTy, 0), SrcReg,
                    MI.getFlags());
   MI.eraseFromParent();
 }
 
-bool CombinerHelper::matchCombineFAbsOfFNeg(MachineInstr &MI,
-                                            BuildFnTy &MatchInfo) {
-  assert(MI.getOpcode() == TargetOpcode::G_FABS && "Expected a G_FABS");
-  Register Src = MI.getOperand(1).getReg();
-  Register NegSrc;
-
-  if (!mi_match(Src, MRI, m_GFNeg(m_Reg(NegSrc))))
-    return false;
-
-  MatchInfo = [=, &MI](MachineIRBuilder &B) {
-    Observer.changingInstr(MI);
-    MI.getOperand(1).setReg(NegSrc);
-    Observer.changedInstr(MI);
-  };
-  return true;
-}
-
 bool CombinerHelper::matchCombineTruncOfExt(
     MachineInstr &MI, std::pair<Register, unsigned> &MatchInfo) {
   assert(MI.getOpcode() == TargetOpcode::G_TRUNC && "Expected a G_TRUNC");
   Register SrcReg = MI.getOperand(1).getReg();
   MachineInstr *SrcMI = MRI.getVRegDef(SrcReg);
   unsigned SrcOpc = SrcMI->getOpcode();
   if (SrcOpc == TargetOpcode::G_ANYEXT || SrcOpc == TargetOpcode::G_SEXT ||
       SrcOpc == TargetOpcode::G_ZEXT) {

llvm/test/CodeGen/AArch64/GlobalISel/combine-select.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- --aarch64postlegalizercombiner-only-enable-rule="select_to_logical" %s -o - | FileCheck %s
 # RUN: llc -debugify-and-strip-all-safe -run-pass=aarch64-prelegalizer-combiner -verify-machineinstrs -mtriple aarch64-unknown-unknown %s -o - | FileCheck %s
 # REQUIRES: asserts
 ---
 # select (c, x, x) -> x
 name:            test_combine_select_same_res
 body:             |
   bb.1:
     liveins: $x0, $x1
     ; CHECK-LABEL: name: test_combine_select_same_res
     ; CHECK: liveins: $x0, $x1
     ; CHECK-NEXT: {{  $}}
     ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(s64) = COPY $x0
     ; CHECK-NEXT: $x0 = COPY [[COPY]](s64)
     %0:_(s64) = COPY $x0
     %1:_(s1) = G_TRUNC %0
     %2:_(s64) = G_SELECT %1, %0, %0
     $x0 = COPY %2(s64)
 ...
 ---
 # select (undef, x, y) -> y
 name:            test_combine_select_undef_res0_res1
 body:             |
   bb.1:
     liveins: $x0, $x1
     ; CHECK-LABEL: name: test_combine_select_undef_res0_res1
     ; CHECK: liveins: $x0, $x1
     ; CHECK-NEXT: {{  $}}
-    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(s64) = COPY $x0
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(s64) = COPY $x1
     ; CHECK-NEXT: $x0 = COPY [[COPY]](s64)
     %0:_(s64) = COPY $x0
     %1:_(s64) = COPY $x1
     %2:_(s1) = G_IMPLICIT_DEF
     %3:_(s64) = G_SELECT %2, %0, %1
     $x0 = COPY %3(s64)
 ...
 ---

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

 name:            test_combine_select_undef_res0_res1
 legalized:       true
 body:             |
   bb.1:
     liveins: $x0, $x1
     ; CHECK-LABEL: name: test_combine_select_undef_res0_res1
     ; CHECK: liveins: $x0, $x1
     ; CHECK-NEXT: {{  $}}
-    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(s64) = COPY $x0
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:_(s64) = COPY $x1
     ; CHECK-NEXT: $x0 = COPY [[COPY]](s64)
     %0:_(s64) = COPY $x0
     %1:_(s64) = COPY $x1
     %2:_(s1) = G_IMPLICIT_DEF
     %3:_(s64) = G_SELECT %2, %0, %1
     $x0 = COPY %3(s64)
 ...
 ---

llvm/test/CodeGen/AArch64/GlobalISel/prelegalizercombiner-not-really-equiv-insts.mir

 ---
 name:            invariant_loads
 tracksRegLiveness: true
 machineFunctionInfo: {}
 body:             |
   bb.0:
 
     ; %load1 || %load2 == %load1 is fine here, because the loads are invariant.
+    ; TODO: Loads need to be CSE'd for this to work.
 
     ; CHECK-LABEL: name: invariant_loads
     ; CHECK: %ptr:_(p0) = G_GLOBAL_VALUE @g
+    ; CHECK-NEXT: %load1:_(s32) = G_LOAD %ptr(p0) :: (dereferenceable invariant load (s32) from @g)
     ; CHECK-NEXT: %load2:_(s32) = G_LOAD %ptr(p0) :: (dereferenceable invariant load (s32) from @g)
-    ; CHECK-NEXT: G_STORE %load2(s32), %ptr(p0) :: (store (s32) into @g)
+    ; CHECK-NEXT: %or:_(s32) = G_OR %load2, %load1
+    ; CHECK-NEXT: G_STORE %or(s32), %ptr(p0) :: (store (s32) into @g)
     ; CHECK-NEXT: RET_ReallyLR
     %ptr:_(p0) = G_GLOBAL_VALUE @g
     %load1:_(s32) = G_LOAD %ptr(p0) :: (dereferenceable invariant load (s32) from @g)
     %load2:_(s32) = G_LOAD %ptr(p0) :: (dereferenceable invariant load (s32) from @g)
     %or:_(s32) = G_OR %load2, %load1
     G_STORE %or(s32), %ptr(p0) :: (store (s32) into @g)
     RET_ReallyLR
 

llvm/test/CodeGen/AArch64/GlobalISel/prelegalizercombiner-trivial-arith.mir

bb.1.entry:
     %x:_(s32) = COPY $w0
     %cst:_(s32) = G_CONSTANT i32 0
     %op:_(s32) = G_MUL %x(s32), %cst
     $w0 = COPY %op(s32)
     RET_ReallyLR implicit $w0
 
 ...
 
-# FIXME: Probably should be able to replace this.
 ---
 name:            mul_0_cant_replace
 tracksRegLiveness: true
 body:             |
   bb.1.entry:
     liveins: $w0
     ; Fold (x * 0) -> 0
     ;
     ; CHECK-LABEL: name: mul_0_cant_replace
     ; CHECK: liveins: $w0
     ; CHECK-NEXT: {{  $}}
-    ; CHECK-NEXT: %x:_(s32) = COPY $w0
     ; CHECK-NEXT: %cst:_(s32) = G_CONSTANT i32 0
-    ; CHECK-NEXT: %op:gpr(s32) = G_MUL %x, %cst
+    ; CHECK-NEXT: %op:gpr(s32) = COPY %cst(s32)
     ; CHECK-NEXT: $w0 = COPY %op(s32)
     ; CHECK-NEXT: RET_ReallyLR implicit $w0
     %x:_(s32) = COPY $w0
     %cst:_(s32) = G_CONSTANT i32 0
     %op:gpr(s32) = G_MUL %x(s32), %cst
     $w0 = COPY %op(s32)
     RET_ReallyLR implicit $w0
 

 body:             |
   bb.0:
     liveins: $x0
     ; CHECK-LABEL: name: look_through_zext
     ; CHECK: liveins: $x0
     ; CHECK-NEXT: {{  $}}
     ; CHECK-NEXT: %zero:_(s8) = G_CONSTANT i8 0
     ; CHECK-NEXT: %zext_zero:_(s64) = G_ZEXT %zero(s8)
-    ; CHECK-NEXT: $x0 = COPY %zext_zero(s64)
+    ; CHECK-NEXT: %c:_(s64) = G_CONSTANT i64 72340172838076673
+    ; CHECK-NEXT: %mul:_(s64) = G_MUL %zext_zero, %c
+    ; CHECK-NEXT: $x0 = COPY %mul(s64)
     ; CHECK-NEXT: RET_ReallyLR implicit $x0
     %zero:_(s8) = G_CONSTANT i8 0
     %zext_zero:_(s64) = G_ZEXT %zero(s8)
     %c:_(s64) = G_CONSTANT i64 72340172838076673
     %mul:_(s64) = G_MUL %c, %zext_zero
     $x0 = COPY %mul(s64)
     RET_ReallyLR implicit $x0
 ...
 ---