[GlobalISel] Combine: (G_*MULO x, 0) -> 0 + no carry out

[paquette]

Summary

Similar to the following combine in DAGCombiner::visitMULO:

// fold (mulo x, 0) -> 0 + no carry out
if (isNullOrNullSplat(N1))
return CombineTo(N, DAG.getConstant(0, DL, VT),
                    DAG.getConstant(0, DL, CarryVT));

This fixes some generally poor codegen for *mulo:

https://godbolt.org/z/eTxYsvz8f

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

4598–4600

This query won't work correctly for vectors

[paquette]

Check both G_BUILD_VECTOR and G_CONSTANT for vector types.

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

4600–4613

This condition is way too complicated and common to put here like this. We probably should have a predicate like isConstantUnsupported in the artifact combiner somewhere

[foad]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

4616

How does this work? Don't you need to build a single instruction that has two results (just like G_*MULO)?

[paquette]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

4600–4613

I tried to clean it up a bit in a follow up (D118655) but maybe the artifact combiner is a better place to handle it.

4616

I don't think it matters; although G_*MULO instructions produce two results, those results are just regular vregs. As long as they are still defined, the uses should work out.

So, we should be able to replace this with two instructions if we know what the results are going to be. In the case of

%mul, %o = G_*MULO %x, <zero>

We know that the value of %mul and %o must both be 0. So replacing them both with appropriately-sized 0s ought to be safe.

[foad]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

4615

Can't you copy from the RHS of the mul here? And hence there should be no need to check legality for this constant?

4616

Oh yeah, sorry. I was forgetting that (unlike sdag) it is just writing to two vregs.

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

public:
   ///       and rename: s/bool tryEmit/void emit/
   bool tryEmitMemcpyInline(MachineInstr &MI);
 
   /// Match:
   ///   (G_UMULO x, 2) -> (G_UADDO x, x)
   ///   (G_SMULO x, 2) -> (G_SADDO x, x)
   bool matchMulOBy2(MachineInstr &MI, BuildFnTy &MatchInfo);
 
+  /// Match:
+  /// (G_*MULO x, 0) -> 0 + no carry out
+  bool matchMulOBy0(MachineInstr &MI, BuildFnTy &MatchInfo);
+
   /// Transform (fadd x, fneg(y)) -> (fsub x, y)
   ///           (fadd fneg(x), y) -> (fsub y, x)
   ///           (fsub x, fneg(y)) -> (fadd x, y)
   ///           (fmul fneg(x), fneg(y)) -> (fmul x, y)
   ///           (fdiv fneg(x), fneg(y)) -> (fdiv x, y)
   ///           (fmad fneg(x), fneg(y), z) -> (fmad x, y, z)
   ///           (fma fneg(x), fneg(y), z) -> (fma x, y, z)
   bool matchRedundantNegOperands(MachineInstr &MI, BuildFnTy &MatchInfo);

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

def constant_fold : GICombineRule<
   (apply [{ Helper.replaceInstWithConstant(*${d}, ${matchinfo}); }])>;
 
 def mulo_by_2: GICombineRule<
   (defs root:$root, build_fn_matchinfo:$matchinfo),
   (match (wip_match_opcode G_UMULO, G_SMULO):$root,
          [{ return Helper.matchMulOBy2(*${root}, ${matchinfo}); }]),
   (apply [{ Helper.applyBuildFnNoErase(*${root}, ${matchinfo}); }])>;
 
+def mulo_by_0: GICombineRule<
+  (defs root:$root, build_fn_matchinfo:$matchinfo),
+  (match (wip_match_opcode G_UMULO, G_SMULO):$root,
+         [{ return Helper.matchMulOBy0(*${root}, ${matchinfo}); }]),
+  (apply [{ Helper.applyBuildFn(*${root}, ${matchinfo}); }])>;
+
 def mulh_to_lshr : GICombineRule<
   (defs root:$root),
   (match (wip_match_opcode G_UMULH):$root,
          [{ return Helper.matchUMulHToLShr(*${root}); }]),
   (apply [{ Helper.applyUMulHToLShr(*${root}); }])>;
 
 def mulh_combines : GICombineGroup<[mulh_to_lshr]>;
 

 
 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]>;
 
 def const_combines : GICombineGroup<[constant_fp_op, const_ptradd_to_i2p,
-                                     overlapping_and, mulo_by_2]>;
+                                     overlapping_and, mulo_by_2, mulo_by_0]>;
 
 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]>;
 
 def width_reduction_combines : GICombineGroup<[reduce_shl_of_extend,
                                                narrow_binop_feeding_and]>;
 

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

unsigned NewOpc = Opc == TargetOpcode::G_UMULO ? TargetOpcode::G_UADDO
                                                    : TargetOpcode::G_SADDO;
     MI.setDesc(Builder.getTII().get(NewOpc));
     MI.getOperand(3).setReg(MI.getOperand(2).getReg());
     Observer.changedInstr(MI);
   };
   return true;
 }
 
+bool CombinerHelper::matchMulOBy0(MachineInstr &MI, BuildFnTy &MatchInfo) {
+  // (G_*MULO x, 0) -> 0 + no carry out
+  unsigned Opc = MI.getOpcode();
+  assert(Opc == TargetOpcode::G_UMULO || Opc == TargetOpcode::G_SMULO);
+  if (!mi_match(MI.getOperand(3).getReg(), MRI, m_SpecificICstOrSplat(0)))
+    return false;
+  Register Dst = MI.getOperand(0).getReg();
+  Register Carry = MI.getOperand(1).getReg();
+  LLT DstTy = MRI.getType(Dst);
+  LLT CarryTy = MRI.getType(Carry);
+  if (DstTy.isVector()) {
+    LLT DstEltTy = DstTy.getElementType();
+    if (!isLegalOrBeforeLegalizer(
+            {TargetOpcode::G_BUILD_VECTOR, {DstTy, DstEltTy}}) ||
+        !isLegalOrBeforeLegalizer({TargetOpcode::G_CONSTANT, {DstEltTy}}))
+      return false;
+    LLT CarryEltTy = CarryTy.getElementType();
+    if (!isLegalOrBeforeLegalizer(
+            {TargetOpcode::G_BUILD_VECTOR, {CarryTy, CarryEltTy}}) ||
+        !isLegalOrBeforeLegalizer({TargetOpcode::G_CONSTANT, {CarryEltTy}}))
+      return false;
+  } else {
+    if (!isLegalOrBeforeLegalizer({TargetOpcode::G_CONSTANT, {DstTy}}) ||
+        !isLegalOrBeforeLegalizer({TargetOpcode::G_CONSTANT, {CarryTy}}))
+      return false;
+  }
+  MatchInfo = [=](MachineIRBuilder &B) {
+    B.buildConstant(Dst, 0);
+    B.buildConstant(Carry, 0);
+  };
+  return true;
+}
+
 MachineInstr *CombinerHelper::buildUDivUsingMul(MachineInstr &MI) {
   assert(MI.getOpcode() == TargetOpcode::G_UDIV);
   auto &UDiv = cast<GenericMachineInstr>(MI);
   Register Dst = UDiv.getReg(0);
   Register LHS = UDiv.getReg(1);
   Register RHS = UDiv.getReg(2);
   LLT Ty = MRI.getType(Dst);
   LLT ScalarTy = Ty.getScalarType();

llvm/test/CodeGen/AArch64/GlobalISel/prelegalizer-combiner-mulo-zero.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple aarch64 -debugify-and-strip-all-safe -run-pass=aarch64-prelegalizer-combiner --aarch64prelegalizercombinerhelper-only-enable-rule="mulo_by_0" -global-isel -verify-machineinstrs %s -o - | FileCheck %s
+# REQUIRES: asserts
+
+# (G_*MULO x, 0) -> 0 + no carry out
+
+...
+---
+name:            umulo_zero
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $w0, $w1
+    ; CHECK-LABEL: name: umulo_zero
+    ; CHECK: liveins: $w0, $w1
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: %zero:_(s32) = G_CONSTANT i32 0
+    ; CHECK-NEXT: %mulo:_(s32) = COPY %zero(s32)
+    ; CHECK-NEXT: %carry:_(s1) = G_CONSTANT i1 false
+    ; CHECK-NEXT: %carry_wide:_(s32) = G_ZEXT %carry(s1)
+    ; CHECK-NEXT: $w0 = COPY %mulo(s32)
+    ; CHECK-NEXT: $w1 = COPY %carry_wide(s32)
+    ; CHECK-NEXT: RET_ReallyLR implicit $w0
+    %lhs:_(s32) = COPY $w0
+    %zero:_(s32) = G_CONSTANT i32 0
+    %mulo:_(s32), %carry:_(s1) = G_UMULO %lhs, %zero
+    %carry_wide:_(s32) = G_ZEXT %carry(s1)
+    $w0 = COPY %mulo(s32)
+    $w1 = COPY %carry_wide
+    RET_ReallyLR implicit $w0
+...
+---
+name:            smulo_zero
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $w0, $w1
+    ; CHECK-LABEL: name: smulo_zero
+    ; CHECK: liveins: $w0, $w1
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: %zero:_(s32) = G_CONSTANT i32 0
+    ; CHECK-NEXT: %mulo:_(s32) = COPY %zero(s32)
+    ; CHECK-NEXT: %carry:_(s1) = G_CONSTANT i1 false
+    ; CHECK-NEXT: %carry_wide:_(s32) = G_ZEXT %carry(s1)
+    ; CHECK-NEXT: $w0 = COPY %mulo(s32)
+    ; CHECK-NEXT: $w1 = COPY %carry_wide(s32)
+    ; CHECK-NEXT: RET_ReallyLR implicit $w0
+    %lhs:_(s32) = COPY $w0
+    %zero:_(s32) = G_CONSTANT i32 0
+    %mulo:_(s32), %carry:_(s1) = G_SMULO %lhs, %zero
+    %carry_wide:_(s32) = G_ZEXT %carry(s1)
+    $w0 = COPY %mulo(s32)
+    $w1 = COPY %carry_wide
+    RET_ReallyLR implicit $w0
+...
+---
+name:            wrong_cst
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $w0, $w1
+    ; CHECK-LABEL: name: wrong_cst
+    ; CHECK: liveins: $w0, $w1
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: %lhs:_(s32) = COPY $w0
+    ; CHECK-NEXT: %not_zero:_(s32) = G_CONSTANT i32 3
+    ; CHECK-NEXT: %mulo:_(s32), %carry:_(s1) = G_UMULO %lhs, %not_zero
+    ; CHECK-NEXT: %carry_wide:_(s32) = G_ZEXT %carry(s1)
+    ; CHECK-NEXT: $w0 = COPY %mulo(s32)
+    ; CHECK-NEXT: $w1 = COPY %carry_wide(s32)
+    ; CHECK-NEXT: RET_ReallyLR implicit $w0
+    %lhs:_(s32) = COPY $w0
+    %not_zero:_(s32) = G_CONSTANT i32 3
+    %mulo:_(s32), %carry:_(s1) = G_UMULO %lhs, %not_zero
+    %carry_wide:_(s32) = G_ZEXT %carry(s1)
+    $w0 = COPY %mulo(s32)
+    $w1 = COPY %carry_wide
+    RET_ReallyLR implicit $w0
+...
+---
+name:            umulo_vec_zero
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $q0, $x0
+    ; CHECK-LABEL: name: umulo_vec_zero
+    ; CHECK: liveins: $q0, $x0
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: %zero:_(s64) = G_CONSTANT i64 0
+    ; CHECK-NEXT: %mulo:_(<2 x s64>) = G_BUILD_VECTOR %zero(s64), %zero(s64)
+    ; CHECK-NEXT: [[C:%[0-9]+]]:_(s1) = G_CONSTANT i1 false
+    ; CHECK-NEXT: %carry:_(<2 x s1>) = G_BUILD_VECTOR [[C]](s1), [[C]](s1)
+    ; CHECK-NEXT: %carry_elt_0:_(s1) = G_EXTRACT_VECTOR_ELT %carry(<2 x s1>), %zero(s64)
+    ; CHECK-NEXT: %carry_wide:_(s64) = G_ZEXT %carry_elt_0(s1)
+    ; CHECK-NEXT: $q0 = COPY %mulo(<2 x s64>)
+    ; CHECK-NEXT: $x0 = COPY %carry_wide(s64)
+    ; CHECK-NEXT: RET_ReallyLR implicit $q0
+    %lhs:_(<2 x s64>) = COPY $q0
+    %zero:_(s64) = G_CONSTANT i64 0
+    %zero_vec:_(<2 x s64>) = G_BUILD_VECTOR %zero, %zero
+    %mulo:_(<2 x s64>), %carry:_(<2 x s1>) = G_UMULO %lhs, %zero_vec
+    %carry_elt_0:_(s1) = G_EXTRACT_VECTOR_ELT %carry:_(<2 x s1>), %zero:_(s64)
+    %carry_wide:_(s64) = G_ZEXT %carry_elt_0
+    $q0 = COPY %mulo(<2 x s64>)
+    $x0 = COPY %carry_wide
+    RET_ReallyLR implicit $q0
+...
+---
+name:            smulo_vec_zero
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $q0, $x0
+    ; CHECK-LABEL: name: smulo_vec_zero
+    ; CHECK: liveins: $q0, $x0
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: %zero:_(s64) = G_CONSTANT i64 0
+    ; CHECK-NEXT: %mulo:_(<2 x s64>) = G_BUILD_VECTOR %zero(s64), %zero(s64)
+    ; CHECK-NEXT: [[C:%[0-9]+]]:_(s1) = G_CONSTANT i1 false
+    ; CHECK-NEXT: %carry:_(<2 x s1>) = G_BUILD_VECTOR [[C]](s1), [[C]](s1)
+    ; CHECK-NEXT: %carry_elt_0:_(s1) = G_EXTRACT_VECTOR_ELT %carry(<2 x s1>), %zero(s64)
+    ; CHECK-NEXT: %carry_wide:_(s64) = G_ZEXT %carry_elt_0(s1)
+    ; CHECK-NEXT: $q0 = COPY %mulo(<2 x s64>)
+    ; CHECK-NEXT: $x0 = COPY %carry_wide(s64)
+    ; CHECK-NEXT: RET_ReallyLR implicit $q0
+    %lhs:_(<2 x s64>) = COPY $q0
+    %zero:_(s64) = G_CONSTANT i64 0
+    %zero_vec:_(<2 x s64>) = G_BUILD_VECTOR %zero, %zero
+    %mulo:_(<2 x s64>), %carry:_(<2 x s1>) = G_SMULO %lhs, %zero_vec
+    %carry_elt_0:_(s1) = G_EXTRACT_VECTOR_ELT %carry:_(<2 x s1>), %zero:_(s64)
+    %carry_wide:_(s64) = G_ZEXT %carry_elt_0
+    $q0 = COPY %mulo(<2 x s64>)
+    $x0 = COPY %carry_wide
+    RET_ReallyLR implicit $q0