[GlobalISel] Combine zext(trunc x) to x

[Petar.Avramovic]

Summary

Combine zext(trunc x) to x when truncated bits are known to be zero.

[arsenm]

Maybe should add a vector test, although known bits vector support may be too weak to test it

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

2306

getScalarSizeInBits

[foad]

Looks good but I think it needs more test coverage. Does it work on vector types? (You might need to use getScalarSizeInBits instead of getSizeInBits?) If it does work on vectors then that needs tests.

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

2304

Maybe add a test case to check that this combine does nothing if the inner and outer types don't match?

[Petar.Avramovic]

Adding vectors.

[foad]

LGTM.

llvm/test/CodeGen/AMDGPU/GlobalISel/combine-zext-trunc.mir

61–62

In this case you could just use a trunc from s64 to s32. No need for the zext. That could be a follow-up though.

[foad]

Reverse ping.

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

public:
   // Transform G_PTR_ADD (G_PTRTOINT C1), C2 -> C1 + C2
   bool matchCombineConstPtrAddToI2P(MachineInstr &MI, int64_t &NewCst);
   bool applyCombineConstPtrAddToI2P(MachineInstr &MI, int64_t &NewCst);
 
   /// Transform anyext(trunc(x)) to x.
   bool matchCombineAnyExtTrunc(MachineInstr &MI, Register &Reg);
   bool applyCombineAnyExtTrunc(MachineInstr &MI, Register &Reg);
 
+  /// Transform zext(trunc(x)) to x.
+  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);
   bool applyCombineExtOfExt(MachineInstr &MI,
                             std::tuple<Register, unsigned> &MatchInfo);
 
   /// Transform fneg(fneg(x)) to x.
   bool matchCombineFNegOfFNeg(MachineInstr &MI, Register &Reg);

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

 def anyext_trunc_fold_matchinfo : GIDefMatchData<"Register">;
 def anyext_trunc_fold: GICombineRule <
   (defs root:$root, anyext_trunc_fold_matchinfo:$matchinfo),
   (match (wip_match_opcode G_ANYEXT):$root,
          [{ return Helper.matchCombineAnyExtTrunc(*${root}, ${matchinfo}); }]),
   (apply [{ return Helper.replaceSingleDefInstWithReg(*${root}, ${matchinfo}); }])
 >;
 
+// Fold (zext (trunc x)) -> x if the source type is same as the destination type
+// and truncated bits are known to be zero.
+def zext_trunc_fold_matchinfo : GIDefMatchData<"Register">;
+def zext_trunc_fold: GICombineRule <
+  (defs root:$root, zext_trunc_fold_matchinfo:$matchinfo),
+  (match (wip_match_opcode G_ZEXT):$root,
+         [{ return Helper.matchCombineZextTrunc(*${root}, ${matchinfo}); }]),
+  (apply [{ return Helper.replaceSingleDefInstWithReg(*${root}, ${matchinfo}); }])
+>;
+
 // Fold ([asz]ext ([asz]ext x)) -> ([asz]ext x).
 def ext_ext_fold_matchinfo : GIDefMatchData<"std::tuple<Register, unsigned>">;
 def ext_ext_fold: GICombineRule <
   (defs root:$root, ext_ext_fold_matchinfo:$matchinfo),
   (match (wip_match_opcode G_ANYEXT, G_SEXT, G_ZEXT):$root,
          [{ return Helper.matchCombineExtOfExt(*${root}, ${matchinfo}); }]),
   (apply [{ return Helper.applyCombineExtOfExt(*${root}, ${matchinfo}); }])
 >;
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]>;
 
 def known_bits_simplifications : GICombineGroup<[
-  redundant_and, redundant_sext_inreg, redundant_or, urem_pow2_to_mask]>;
+  redundant_and, redundant_sext_inreg, redundant_or, urem_pow2_to_mask,
+  zext_trunc_fold]>;
 
 def width_reduction_combines : GICombineGroup<[reduce_shl_of_extend]>;
 
 def phi_combines : GICombineGroup<[extend_through_phis]>;
 
 def select_combines : GICombineGroup<[select_undef_cmp, select_constant_cmp]>;
 
 def trivial_combines : GICombineGroup<[copy_prop, mul_to_shl, add_p2i_to_ptradd,

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

bool CombinerHelper::matchCombineAnyExtTrunc(MachineInstr &MI, Register &Reg) {
   assert(MI.getOpcode() == TargetOpcode::G_ANYEXT && "Expected a G_ANYEXT");
   Register DstReg = MI.getOperand(0).getReg();
   Register SrcReg = MI.getOperand(1).getReg();
   LLT DstTy = MRI.getType(DstReg);
   return mi_match(SrcReg, MRI,
                   m_GTrunc(m_all_of(m_Reg(Reg), m_SpecificType(DstTy))));
 }
 
+bool CombinerHelper::matchCombineZextTrunc(MachineInstr &MI, Register &Reg) {
+  assert(MI.getOpcode() == TargetOpcode::G_ZEXT && "Expected a G_ZEXT");
+  Register DstReg = MI.getOperand(0).getReg();
+  Register SrcReg = MI.getOperand(1).getReg();
+  LLT DstTy = MRI.getType(DstReg);
+  if (mi_match(SrcReg, MRI,
+               m_GTrunc(m_all_of(m_Reg(Reg), m_SpecificType(DstTy))))) {
+    unsigned DstSize = DstTy.getScalarSizeInBits();
+    unsigned SrcSize = MRI.getType(SrcReg).getScalarSizeInBits();
+    return KB->getKnownBits(Reg).countMinLeadingZeros() >= DstSize - SrcSize;
+  }
+  return false;
+}
+
 bool CombinerHelper::matchCombineExtOfExt(
     MachineInstr &MI, std::tuple<Register, unsigned> &MatchInfo) {
   assert((MI.getOpcode() == TargetOpcode::G_ANYEXT ||
           MI.getOpcode() == TargetOpcode::G_SEXT ||
           MI.getOpcode() == TargetOpcode::G_ZEXT) &&
          "Expected a G_[ASZ]EXT");
   Register SrcReg = MI.getOperand(1).getReg();
   MachineInstr *SrcMI = MRI.getVRegDef(SrcReg);

llvm/test/CodeGen/AMDGPU/GlobalISel/combine-zext-trunc.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple=amdgcn-mesa-mesa3d -mcpu=gfx1010 -run-pass=amdgpu-prelegalizer-combiner -verify-machineinstrs %s -o - | FileCheck -check-prefix=GCN %s
+
+---
+name: zext_trunc_s32_s16_s32
+tracksRegLiveness: true
+body: |
+  bb.0:
+    liveins: $vgpr0
+
+    ; GCN-LABEL: name: zext_trunc_s32_s16_s32
+    ; GCN: liveins: $vgpr0
+    ; GCN: %var:_(s32) = COPY $vgpr0
+    ; GCN: %c3FFF:_(s32) = G_CONSTANT i32 16383
+    ; GCN: %low_bits:_(s32) = G_AND %var, %c3FFF
+    ; GCN: $vgpr0 = COPY %low_bits(s32)
+    %var:_(s32) = COPY $vgpr0
+    %c3FFF:_(s32) = G_CONSTANT i32 16383
+    %low_bits:_(s32) = G_AND %var, %c3FFF
+    %trunc:_(s16) = G_TRUNC %low_bits(s32)
+    %zext:_(s32) = G_ZEXT %trunc(s16)
+    $vgpr0 = COPY %zext(s32)
+...
+
+---
+name: zext_trunc_s32_s16_s32_unknown_high_bits
+tracksRegLiveness: true
+body: |
+  bb.0:
+    liveins: $vgpr0
+
+    ; GCN-LABEL: name: zext_trunc_s32_s16_s32_unknown_high_bits
+    ; GCN: liveins: $vgpr0
+    ; GCN: %var:_(s32) = COPY $vgpr0
+    ; GCN: %cFFFFF:_(s32) = G_CONSTANT i32 1048575
+    ; GCN: %low_bits:_(s32) = G_AND %var, %cFFFFF
+    ; GCN: %trunc:_(s16) = G_TRUNC %low_bits(s32)
+    ; GCN: %zext:_(s32) = G_ZEXT %trunc(s16)
+    ; GCN: $vgpr0 = COPY %zext(s32)
+    %var:_(s32) = COPY $vgpr0
+    %cFFFFF:_(s32) = G_CONSTANT i32 1048575
+    %low_bits:_(s32) = G_AND %var, %cFFFFF
+    %trunc:_(s16) = G_TRUNC %low_bits(s32)
+    %zext:_(s32) = G_ZEXT %trunc(s16)
+    $vgpr0 = COPY %zext(s32)
+...
+
+---
+name: zext_trunc_s64_s16_s32
+tracksRegLiveness: true
+body: |
+  bb.0:
+    liveins: $vgpr0_vgpr1
+
+    ; GCN-LABEL: name: zext_trunc_s64_s16_s32
+    ; GCN: liveins: $vgpr0_vgpr1
+    ; GCN: %var:_(s64) = COPY $vgpr0_vgpr1
+    ; GCN: %c3FFF:_(s64) = G_CONSTANT i64 16383
+    ; GCN: %low_bits:_(s64) = G_AND %var, %c3FFF
+    ; GCN: %trunc:_(s16) = G_TRUNC %low_bits(s64)
+    ; GCN: %zext:_(s32) = G_ZEXT %trunc(s16)
+    ; GCN: $vgpr0 = COPY %zext(s32)
+    %var:_(s64) = COPY $vgpr0_vgpr1
+    %c3FFF:_(s64) = G_CONSTANT i64 16383
+    %low_bits:_(s64) = G_AND %var, %c3FFF
+    %trunc:_(s16) = G_TRUNC %low_bits(s64)
+    %zext:_(s32) = G_ZEXT %trunc(s16)
+    $vgpr0 = COPY %zext(s32)
+...
+
+---
+name: zext_trunc_s32_s16_s64
+tracksRegLiveness: true
+body: |
+  bb.0:
+    liveins: $vgpr0
+
+    ; GCN-LABEL: name: zext_trunc_s32_s16_s64
+    ; GCN: liveins: $vgpr0
+    ; GCN: %var:_(s32) = COPY $vgpr0
+    ; GCN: %c3FFF:_(s32) = G_CONSTANT i32 16383
+    ; GCN: %low_bits:_(s32) = G_AND %var, %c3FFF
+    ; GCN: %trunc:_(s16) = G_TRUNC %low_bits(s32)
+    ; GCN: %zext:_(s64) = G_ZEXT %trunc(s16)
+    ; GCN: $vgpr0_vgpr1 = COPY %zext(s64)
+    %var:_(s32) = COPY $vgpr0
+    %c3FFF:_(s32) = G_CONSTANT i32 16383
+    %low_bits:_(s32) = G_AND %var, %c3FFF
+    %trunc:_(s16) = G_TRUNC %low_bits(s32)
+    %zext:_(s64) = G_ZEXT %trunc(s16)
+    $vgpr0_vgpr1 = COPY %zext(s64)
+...
+
+---
+name: zext_trunc_v2s32_v2s16_v2s32
+tracksRegLiveness: true
+body: |
+  bb.0:
+    liveins: $vgpr0_vgpr1
+
+    ; GCN-LABEL: name: zext_trunc_v2s32_v2s16_v2s32
+    ; GCN: liveins: $vgpr0_vgpr1
+    ; GCN: %var:_(<2 x s32>) = COPY $vgpr0_vgpr1
+    ; GCN: %c3FFF:_(s32) = G_CONSTANT i32 16383
+    ; GCN: %c7FFF:_(s32) = G_CONSTANT i32 32767
+    ; GCN: %c:_(<2 x s32>) = G_BUILD_VECTOR %c3FFF(s32), %c7FFF(s32)
+    ; GCN: %low_bits:_(<2 x s32>) = G_AND %var, %c
+    ; GCN: $vgpr0_vgpr1 = COPY %low_bits(<2 x s32>)
+    %var:_(<2 x s32>) = COPY $vgpr0_vgpr1
+    %c3FFF:_(s32) = G_CONSTANT i32 16383
+    %c7FFF:_(s32) = G_CONSTANT i32 32767
+    %c:_(<2 x s32>) = G_BUILD_VECTOR %c3FFF(s32), %c7FFF(s32)
+    %low_bits:_(<2 x s32>) = G_AND %var, %c
+    %trunc:_(<2 x s16>) = G_TRUNC %low_bits(<2 x s32>)
+    %zext:_(<2 x s32>) = G_ZEXT %trunc(<2 x s16>)
+    $vgpr0_vgpr1 = COPY %zext(<2 x s32>)
+...
+
+---
+name: zext_trunc_v2s32_v2s16_v2s32_unknown_high_bits
+tracksRegLiveness: true
+body: |
+  bb.0:
+    liveins: $vgpr0_vgpr1
+
+    ; GCN-LABEL: name: zext_trunc_v2s32_v2s16_v2s32_unknown_high_bits
+    ; GCN: liveins: $vgpr0_vgpr1
+    ; GCN: %var:_(<2 x s32>) = COPY $vgpr0_vgpr1
+    ; GCN: %cFFFFF:_(s32) = G_CONSTANT i32 1048575
+    ; GCN: %c7FFF:_(s32) = G_CONSTANT i32 32767
+    ; GCN: %c:_(<2 x s32>) = G_BUILD_VECTOR %cFFFFF(s32), %c7FFF(s32)
+    ; GCN: %low_bits:_(<2 x s32>) = G_AND %var, %c
+    ; GCN: %trunc:_(<2 x s16>) = G_TRUNC %low_bits(<2 x s32>)
+    ; GCN: %zext:_(<2 x s32>) = G_ZEXT %trunc(<2 x s16>)
+    ; GCN: $vgpr0_vgpr1 = COPY %zext(<2 x s32>)
+    %var:_(<2 x s32>) = COPY $vgpr0_vgpr1
+    %cFFFFF:_(s32) = G_CONSTANT i32 1048575
+    %c7FFF:_(s32) = G_CONSTANT i32 32767
+    %c:_(<2 x s32>) = G_BUILD_VECTOR %cFFFFF(s32), %c7FFF(s32)
+    %low_bits:_(<2 x s32>) = G_AND %var, %c
+    %trunc:_(<2 x s16>) = G_TRUNC %low_bits(<2 x s32>)
+    %zext:_(<2 x s32>) = G_ZEXT %trunc(<2 x s16>)
+    $vgpr0_vgpr1 = COPY %zext(<2 x s32>)
+...
+
+---
+name: zext_trunc_v2s64_v2s16_v2s32
+tracksRegLiveness: true
+body: |
+  bb.0:
+    liveins: $vgpr0_vgpr1_vgpr2_vgpr3
+
+    ; GCN-LABEL: name: zext_trunc_v2s64_v2s16_v2s32
+    ; GCN: liveins: $vgpr0_vgpr1_vgpr2_vgpr3
+    ; GCN: %var:_(<2 x s64>) = COPY $vgpr0_vgpr1_vgpr2_vgpr3
+    ; GCN: %c3FFF:_(s64) = G_CONSTANT i64 16383
+    ; GCN: %c7FFF:_(s64) = G_CONSTANT i64 32767
+    ; GCN: %c:_(<2 x s64>) = G_BUILD_VECTOR %c3FFF(s64), %c7FFF(s64)
+    ; GCN: %low_bits:_(<2 x s64>) = G_AND %var, %c
+    ; GCN: %trunc:_(<2 x s16>) = G_TRUNC %low_bits(<2 x s64>)
+    ; GCN: %zext:_(<2 x s32>) = G_ZEXT %trunc(<2 x s16>)
+    ; GCN: $vgpr0_vgpr1 = COPY %zext(<2 x s32>)
+    %var:_(<2 x s64>) = COPY $vgpr0_vgpr1_vgpr2_vgpr3
+    %c3FFF:_(s64) = G_CONSTANT i64 16383
+    %c7FFF:_(s64) = G_CONSTANT i64 32767
+    %c:_(<2 x s64>) = G_BUILD_VECTOR %c3FFF(s64), %c7FFF(s64)
+    %low_bits:_(<2 x s64>) = G_AND %var, %c
+    %trunc:_(<2 x s16>) = G_TRUNC %low_bits(<2 x s64>)
+    %zext:_(<2 x s32>) = G_ZEXT %trunc(<2 x s16>)
+    $vgpr0_vgpr1 = COPY %zext(<2 x s32>)
+...
+
+---
+name: zext_trunc_v2s32_v2s16_v2s64
+tracksRegLiveness: true
+body: |
+  bb.0:
+    liveins: $vgpr0_vgpr1
+
+    ; GCN-LABEL: name: zext_trunc_v2s32_v2s16_v2s64
+    ; GCN: liveins: $vgpr0_vgpr1
+    ; GCN: %var:_(<2 x s32>) = COPY $vgpr0_vgpr1
+    ; GCN: %c3FFF:_(s32) = G_CONSTANT i32 16383
+    ; GCN: %c7FFF:_(s32) = G_CONSTANT i32 32767
+    ; GCN: %c:_(<2 x s32>) = G_BUILD_VECTOR %c3FFF(s32), %c7FFF(s32)
+    ; GCN: %low_bits:_(<2 x s32>) = G_AND %var, %c
+    ; GCN: %trunc:_(<2 x s16>) = G_TRUNC %low_bits(<2 x s32>)
+    ; GCN: %zext:_(<2 x s64>) = G_ZEXT %trunc(<2 x s16>)
+    ; GCN: $vgpr0_vgpr1_vgpr2_vgpr3 = COPY %zext(<2 x s64>)
+    %var:_(<2 x s32>) = COPY $vgpr0_vgpr1
+    %c3FFF:_(s32) = G_CONSTANT i32 16383
+    %c7FFF:_(s32) = G_CONSTANT i32 32767
+    %c:_(<2 x s32>) = G_BUILD_VECTOR %c3FFF(s32), %c7FFF(s32)
+    %low_bits:_(<2 x s32>) = G_AND %var, %c
+    %trunc:_(<2 x s16>) = G_TRUNC %low_bits(<2 x s32>)
+    %zext:_(<2 x s64>) = G_ZEXT %trunc(<2 x s16>)
+    $vgpr0_vgpr1_vgpr2_vgpr3 = COPY %zext(<2 x s64>)
+...

llvm/test/CodeGen/AMDGPU/GlobalISel/shl-ext-reduce.ll

 ; GFX7-NEXT:    s_lshl_b32 s0, s0, 2
 ; GFX7-NEXT:    s_and_b32 s0, s0, 0xffff
 ; GFX7-NEXT:    ; return to shader part epilog
 ;
 ; GFX8-LABEL: s_shl_i32_zext_i16:
 ; GFX8:       ; %bb.0:
 ; GFX8-NEXT:    s_and_b32 s0, s0, 0xffff
 ; GFX8-NEXT:    s_and_b32 s0, s0, 0x3fff
-; GFX8-NEXT:    s_bfe_u32 s1, 2, 0x100000
-; GFX8-NEXT:    s_lshl_b32 s0, s0, s1
-; GFX8-NEXT:    s_bfe_u32 s0, s0, 0x100000
+; GFX8-NEXT:    s_lshl_b32 s0, s0, 2
 ; GFX8-NEXT:    ; return to shader part epilog
 ;
 ; GFX9-LABEL: s_shl_i32_zext_i16:
 ; GFX9:       ; %bb.0:
 ; GFX9-NEXT:    s_and_b32 s0, s0, 0xffff
 ; GFX9-NEXT:    s_and_b32 s0, s0, 0x3fff
-; GFX9-NEXT:    s_bfe_u32 s1, 2, 0x100000
-; GFX9-NEXT:    s_lshl_b32 s0, s0, s1
-; GFX9-NEXT:    s_bfe_u32 s0, s0, 0x100000
+; GFX9-NEXT:    s_lshl_b32 s0, s0, 2
 ; GFX9-NEXT:    ; return to shader part epilog
   %and = and i16 %x, 16383
   %ext = zext i16 %and to i32
   %shl = shl i32 %ext, 2
   ret i32 %shl
 }
 
 define i32 @v_shl_i32_zext_i16(i16 %x) {

 ; GFX7-NEXT:    s_and_b32 s0, s0, 0xffff
 ; GFX7-NEXT:    s_lshl_b32 s0, s0, 2
 ; GFX7-NEXT:    s_lshl_b32 s1, s1, 2
 ; GFX7-NEXT:    ; return to shader part epilog
 ;
 ; GFX8-LABEL: s_shl_v2i32_zext_v2i16:
 ; GFX8:       ; %bb.0:
 ; GFX8-NEXT:    s_movk_i32 s2, 0x3fff
-; GFX8-NEXT:    s_mov_b32 s4, 0xffff
 ; GFX8-NEXT:    s_lshr_b32 s1, s0, 16
 ; GFX8-NEXT:    s_mov_b32 s3, s2
-; GFX8-NEXT:    s_and_b32 s0, s0, s4
+; GFX8-NEXT:    s_and_b32 s0, s0, 0xffff
 ; GFX8-NEXT:    s_and_b64 s[0:1], s[0:1], s[2:3]
-; GFX8-NEXT:    s_mov_b32 s5, s4
-; GFX8-NEXT:    s_and_b64 s[0:1], s[0:1], s[4:5]
 ; GFX8-NEXT:    s_lshl_b32 s0, s0, 2
 ; GFX8-NEXT:    s_lshl_b32 s1, s1, 2
 ; GFX8-NEXT:    ; return to shader part epilog
 ;
 ; GFX9-LABEL: s_shl_v2i32_zext_v2i16:
 ; GFX9:       ; %bb.0:
 ; GFX9-NEXT:    s_and_b32 s0, s0, 0x3fff3fff
 ; GFX9-NEXT:    s_lshr_b32 s1, s0, 16