[GISel] Eliminate redundant bitmasking

[jroelofs]

Summary

This was a GISel vs SDAG regression that showed up at -Os in:
SingleSource/Benchmarks/Adobe-C++/simple_types_constant_folding.test on aarch64

https://llvm.godbolt.org/z/aecjodsjG

[paquette]

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

660

Probably shouldn't be in this group since it doesn't use KnownBits?

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

3008

This doesn't use KnownBits?

(If this was yoinked from somewhere else, then we probably need to update a combine. GISelKnownBits supports vectors nowadays last time I checked.)

3025

Minor stylistic suggestion:

if (C1 & C2) {
  B.buildAnd(...);
  return;
}

B.buildCopy(...);

Is it actually necessary to emit the copy at all though? You could do

Dst = G_CONSTANT iN 0

right?

llvm/test/CodeGen/AArch64/GlobalISel/opt-overlapping-and.ll

1 ↗

(On Diff #348565)

Can this be a MIR test?

[jroelofs]

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

660

Oops, yeah. I thought I was going to need KnownBits, but didn't end up using it.

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

3008

https://github.com/llvm/llvm-project/blob/8a5f0d883832aa088460df87df99c40d8f238655/llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp#L3024

3025

Are we guaranteed that Dst is not a physical register? I wasn't sure.

[paquette]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

3025

With G_AND (and other generic opcodes) we can be certain that we only have vregs.

(You have to be careful with COPY instructions, but in this case, we don't have to worry.)

[jroelofs]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

3025

👍

llvm/test/CodeGen/AArch64/GlobalISel/opt-overlapping-and.ll

1 ↗

(On Diff #348565)

👍

[jroelofs]

simplify test

[jroelofs]

llvm/test/CodeGen/AArch64/GlobalISel/opt-overlapping-and.mir

4

This needs:

# REQUIRES: asserts

for the same reason it's needed in: https://reviews.llvm.org/D99283

[paquette]

LGTM with some minor comments

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

3022

I think you can just do

B.buildConstant(Dst, 0);

and omit the replaceRegWith (similar to the buildAnd case above.)

llvm/test/CodeGen/AArch64/GlobalISel/opt-overlapping-and.mir

44

You shouldn't need the registers section in any of the tests here.

You can also drop

• alignment
• liveins
• frameinfo
• machineFunctionInfo

(Technically you can drop tracksRegLiveness too, but it's useful if you want to test the pipeline beyond the combiner.)

[jroelofs]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

3022

When I tried it that way, it wasn't RAUW-ing Dst appropriately, and then the verifier complains:

*** Bad machine code: Reading virtual register without a def ***
- function:    bitmask_no_overlap
- basic block: %bb.0  (0x7fe69b06d6c8)
- instruction: $w0 = COPY %4:_(s32)
- operand 1:   %4:_

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

public:
   bool applyBuildInstructionSteps(MachineInstr &MI,
                                   InstructionStepsMatchInfo &MatchInfo);
 
   /// Match ashr (shl x, C), C -> sext_inreg (C)
   bool matchAshrShlToSextInreg(MachineInstr &MI,
                                std::tuple<Register, int64_t> &MatchInfo);
   bool applyAshShlToSextInreg(MachineInstr &MI,
                               std::tuple<Register, int64_t> &MatchInfo);
+
+  /// Fold and(and(x, C1), C2) -> C1&C2 ? and(x, C1&C2) : 0
+  bool matchOverlappingAnd(MachineInstr &MI,
+                           std::function<void(MachineIRBuilder &)> &MatchInfo);
+
   /// \return true if \p MI is a G_AND instruction whose operands are x and y
   /// where x & y == x or x & y == y. (E.g., one of operands is all-ones value.)
   ///
   /// \param [in] MI - The G_AND instruction.
   /// \param [out] Replacement - A register the G_AND should be replaced with on
   /// success.
   bool matchRedundantAnd(MachineInstr &MI, Register &Replacement);
 

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

 // Fold ashr (shl x, C), C -> sext_inreg (C)
 def shl_ashr_to_sext_inreg_matchinfo : GIDefMatchData<"std::tuple<Register, int64_t>">;
 def shl_ashr_to_sext_inreg : GICombineRule<
   (defs root:$root, shl_ashr_to_sext_inreg_matchinfo:$info),
   (match (wip_match_opcode G_ASHR): $root,
     [{ return Helper.matchAshrShlToSextInreg(*${root}, ${info}); }]),
   (apply [{ return Helper.applyAshShlToSextInreg(*${root}, ${info});}])
 >;
+
+// Fold and(and(x, C1), C2) -> C1&C2 ? and(x, C1&C2) : 0
+def overlapping_and: GICombineRule <
+  (defs root:$root, build_fn_matchinfo:$info),
+  (match (wip_match_opcode G_AND):$root,
+         [{ return Helper.matchOverlappingAnd(*${root}, ${info}); }]),
+  (apply [{ return Helper.applyBuildFn(*${root}, ${info}); }])
+>;
+
 // Fold (x & y) -> x or (x & y) -> y when (x & y) is known to equal x or equal y.
 def redundant_and: GICombineRule <
   (defs root:$root, register_matchinfo:$matchinfo),
   (match (wip_match_opcode G_AND):$root,
          [{ return Helper.matchRedundantAnd(*${root}, ${matchinfo}); }]),
   (apply [{ return Helper.replaceSingleDefInstWithReg(*${root}, ${matchinfo}); }])
 >;
 
def undef_combines : GICombineGroup<[undef_to_fp_zero, undef_to_int_zero,
                                      erase_undef_store]>;
 
 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 const_combines : GICombineGroup<[constant_fp_op, const_ptradd_to_i2p,
+                                     overlapping_and]>;
 
 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]>;
 
 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::applyAshShlToSextInreg(
   std::tie(Src, ShiftAmt) = MatchInfo;
   unsigned Size = MRI.getType(Src).getScalarSizeInBits();
   Builder.setInstrAndDebugLoc(MI);
   Builder.buildSExtInReg(MI.getOperand(0).getReg(), Src, Size - ShiftAmt);
   MI.eraseFromParent();
   return true;
 }
 
+/// and(and(x, C1), C2) -> C1&C2 ? and(x, C1&C2) : 0
+bool CombinerHelper::matchOverlappingAnd(
+    MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) {
+  assert(MI.getOpcode() == TargetOpcode::G_AND);
+
+  Register Dst = MI.getOperand(0).getReg();
+  LLT Ty = MRI.getType(Dst);
+
+  Register R;
+  int64_t C1;
+  int64_t C2;
+  if (!mi_match(
+          Dst, MRI,
+          m_GAnd(m_GAnd(m_Reg(R), m_ICst(C1)), m_ICst(C2))))
+    return false;
+
+  MatchInfo = [=](MachineIRBuilder &B) {
+    if (C1 & C2) {
+      B.buildAnd(Dst, R, B.buildConstant(Ty, C1 & C2));
+      return;
+    }
+    auto Zero = B.buildConstant(Ty, 0);
+    replaceRegWith(MRI, Dst, Zero->getOperand(0).getReg());
+  };
+  return true;
+}
+
 bool CombinerHelper::matchRedundantAnd(MachineInstr &MI,
                                        Register &Replacement) {
   // Given
   //
   // %y:_(sN) = G_SOMETHING
   // %x:_(sN) = G_SOMETHING
   // %res:_(sN) = G_AND %x, %y
   //

llvm/test/CodeGen/AArch64/GlobalISel/opt-overlapping-and.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -debugify-and-strip-all-safe -mtriple arm64-apple-ios -O0 -run-pass=aarch64-prelegalizer-combiner --aarch64prelegalizercombinerhelper-only-enable-rule="overlapping_and" -global-isel -verify-machineinstrs %s -o - | FileCheck %s
+# REQUIRES: asserts
+---
+name:            bitmask_overlap1
+body:             |
+  bb.1:
+    ; CHECK-LABEL: name: bitmask_overlap1
+    ; CHECK: [[COPY:%[0-9]+]]:_(s32) = COPY $w0
+    ; CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 128
+    ; CHECK: [[AND:%[0-9]+]]:_(s32) = G_AND [[COPY]], [[C]]
+    ; CHECK: $w0 = COPY [[AND]](s32)
+    ; CHECK: RET_ReallyLR implicit $w0
+    %0:_(s32) = COPY $w0
+    %1:_(s32) = G_CONSTANT i32 -128
+    %3:_(s32) = G_CONSTANT i32 255
+    %2:_(s32) = G_AND %0, %1
+    %4:_(s32) = G_AND %2, %3
+    $w0 = COPY %4(s32)
+    RET_ReallyLR implicit $w0
+
+...
+---
+name:            bitmask_overlap2
+body:             |
+  bb.1:
+    ; CHECK-LABEL: name: bitmask_overlap2
+    ; CHECK: [[COPY:%[0-9]+]]:_(s32) = COPY $w0
+    ; CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 128
+    ; CHECK: [[AND:%[0-9]+]]:_(s32) = G_AND [[COPY]], [[C]]
+    ; CHECK: $w0 = COPY [[AND]](s32)
+    ; CHECK: RET_ReallyLR implicit $w0
+    %0:_(s32) = COPY $w0
+    %1:_(s32) = G_CONSTANT i32 255
+    %3:_(s32) = G_CONSTANT i32 -128
+    %2:_(s32) = G_AND %1, %0
+    %4:_(s32) = G_AND %2, %3
+    $w0 = COPY %4(s32)
+    RET_ReallyLR implicit $w0
+
+...
+---
+name:            bitmask_overlap3
+body:             |
+  bb.1:
+    ; CHECK-LABEL: name: bitmask_overlap3
+    ; CHECK: [[COPY:%[0-9]+]]:_(s32) = COPY $w0
+    ; CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 128
+    ; CHECK: [[AND:%[0-9]+]]:_(s32) = G_AND [[COPY]], [[C]]
+    ; CHECK: $w0 = COPY [[AND]](s32)
+    ; CHECK: RET_ReallyLR implicit $w0
+    %0:_(s32) = COPY $w0
+    %1:_(s32) = G_CONSTANT i32 255
+    %3:_(s32) = G_CONSTANT i32 -128
+    %2:_(s32) = G_AND %1, %0
+    %4:_(s32) = G_AND %3, %2
+    $w0 = COPY %4(s32)
+    RET_ReallyLR implicit $w0
+
+...
+---
+name:            bitmask_overlap4
+body:             |
+  bb.1:
+    ; CHECK-LABEL: name: bitmask_overlap4
+    ; CHECK: [[COPY:%[0-9]+]]:_(s32) = COPY $w0
+    ; CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 128
+    ; CHECK: [[AND:%[0-9]+]]:_(s32) = G_AND [[COPY]], [[C]]
+    ; CHECK: $w0 = COPY [[AND]](s32)
+    ; CHECK: RET_ReallyLR implicit $w0
+    %0:_(s32) = COPY $w0
+    %1:_(s32) = G_CONSTANT i32 255
+    %3:_(s32) = G_CONSTANT i32 -128
+    %2:_(s32) = G_AND %0, %1
+    %4:_(s32) = G_AND %3, %2
+    $w0 = COPY %4(s32)
+    RET_ReallyLR implicit $w0
+
+...
+---
+name:            bitmask_no_overlap
+body:             |
+  bb.1:
+    ; CHECK-LABEL: name: bitmask_no_overlap
+    ; CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 0
+    ; CHECK: $w0 = COPY [[C]](s32)
+    ; CHECK: RET_ReallyLR implicit $w0
+    %0:_(s32) = COPY $w0
+    %1:_(s32) = G_CONSTANT i32 1
+    %3:_(s32) = G_CONSTANT i32 2
+    %2:_(s32) = G_AND %0, %1
+    %4:_(s32) = G_AND %2, %3
+    $w0 = COPY %4(s32)
+    RET_ReallyLR implicit $w0
+
+...
+---
+name:            bitmask_overlap_extrause
+body:             |
+  bb.1:
+    ; CHECK-LABEL: name: bitmask_overlap_extrause
+    ; CHECK: [[COPY:%[0-9]+]]:_(s32) = COPY $w0
+    ; CHECK: [[COPY1:%[0-9]+]]:_(p0) = COPY $x1
+    ; CHECK: [[C:%[0-9]+]]:_(s32) = G_CONSTANT i32 255
+    ; CHECK: [[AND:%[0-9]+]]:_(s32) = G_AND [[COPY]], [[C]]
+    ; CHECK: [[C1:%[0-9]+]]:_(s32) = G_CONSTANT i32 128
+    ; CHECK: [[AND1:%[0-9]+]]:_(s32) = G_AND [[COPY]], [[C1]]
+    ; CHECK: G_STORE [[AND]](s32), [[COPY1]](p0) :: (store 4)
+    ; CHECK: $w0 = COPY [[AND1]](s32)
+    ; CHECK: RET_ReallyLR implicit $w0
+    %0:_(s32) = COPY $w0
+    %1:_(p0) = COPY $x1
+    %2:_(s32) = G_CONSTANT i32 255
+    %4:_(s32) = G_CONSTANT i32 -128
+    %3:_(s32) = G_AND %0, %2
+    %5:_(s32) = G_AND %3, %4
+    G_STORE %3(s32), %1(p0) :: (store 4)
+    $w0 = COPY %5(s32)
+    RET_ReallyLR implicit $w0
+
+...

llvm/test/CodeGen/AMDGPU/GlobalISel/cvt_f32_ubyte.ll

 ; SI-NEXT:    v_cmp_eq_u32_e32 vcc, 0, v1
 ; SI-NEXT:    v_cndmask_b32_e32 v2, v3, v2, vcc
 ; SI-NEXT:    v_mov_b32_e32 v3, 0xbe
 ; SI-NEXT:    v_sub_i32_e32 v4, vcc, v3, v2
 ; SI-NEXT:    v_lshl_b64 v[2:3], v[0:1], v2
 ; SI-NEXT:    v_cmp_ne_u64_e32 vcc, 0, v[0:1]
 ; SI-NEXT:    v_and_b32_e32 v1, 0x7fffffff, v3
 ; SI-NEXT:    v_cndmask_b32_e32 v0, 0, v4, vcc
-; SI-NEXT:    v_and_b32_e32 v3, s6, v1
+; SI-NEXT:    v_and_b32_e32 v3, s6, v3
 ; SI-NEXT:    v_lshrrev_b32_e32 v1, 8, v1
 ; SI-NEXT:    v_lshlrev_b32_e32 v0, 23, v0
 ; SI-NEXT:    s_mov_b32 s4, 0
 ; SI-NEXT:    s_movk_i32 s5, 0x80
 ; SI-NEXT:    v_or_b32_e32 v0, v0, v1
 ; SI-NEXT:    v_cmp_eq_u64_e32 vcc, s[4:5], v[2:3]
 ; SI-NEXT:    v_and_b32_e32 v1, 1, v0
 ; SI-NEXT:    v_cndmask_b32_e32 v1, 0, v1, vcc

 ; VI-NEXT:    v_cmp_eq_u32_e32 vcc, 0, v1
 ; VI-NEXT:    v_cndmask_b32_e32 v2, v3, v2, vcc
 ; VI-NEXT:    v_mov_b32_e32 v3, 0xbe
 ; VI-NEXT:    v_sub_u32_e32 v4, vcc, v3, v2
 ; VI-NEXT:    v_lshlrev_b64 v[2:3], v2, v[0:1]
 ; VI-NEXT:    v_cmp_ne_u64_e32 vcc, 0, v[0:1]
 ; VI-NEXT:    v_and_b32_e32 v1, 0x7fffffff, v3
 ; VI-NEXT:    v_cndmask_b32_e32 v0, 0, v4, vcc
-; VI-NEXT:    v_and_b32_e32 v3, s6, v1
+; VI-NEXT:    v_and_b32_e32 v3, s6, v3
 ; VI-NEXT:    v_lshrrev_b32_e32 v1, 8, v1
 ; VI-NEXT:    v_lshlrev_b32_e32 v0, 23, v0
 ; VI-NEXT:    s_mov_b32 s4, 0
 ; VI-NEXT:    s_movk_i32 s5, 0x80
 ; VI-NEXT:    v_or_b32_e32 v0, v0, v1
 ; VI-NEXT:    v_cmp_eq_u64_e32 vcc, s[4:5], v[2:3]
 ; VI-NEXT:    v_and_b32_e32 v1, 1, v0
 ; VI-NEXT:    v_cndmask_b32_e32 v1, 0, v1, vcc

 ; SI-NEXT:    v_cmp_eq_u32_e64 vcc, 0, 0
 ; SI-NEXT:    v_cndmask_b32_e32 v2, v3, v2, vcc
 ; SI-NEXT:    v_mov_b32_e32 v1, 0
 ; SI-NEXT:    v_sub_i32_e32 v4, vcc, 0xbe, v2
 ; SI-NEXT:    v_lshl_b64 v[2:3], v[0:1], v2
 ; SI-NEXT:    v_cmp_ne_u64_e32 vcc, 0, v[0:1]
 ; SI-NEXT:    v_and_b32_e32 v1, 0x7fffffff, v3
 ; SI-NEXT:    v_cndmask_b32_e32 v0, 0, v4, vcc
-; SI-NEXT:    v_and_b32_e32 v3, s4, v1
+; SI-NEXT:    v_and_b32_e32 v3, s4, v3
 ; SI-NEXT:    v_lshrrev_b32_e32 v1, 8, v1
 ; SI-NEXT:    v_lshlrev_b32_e32 v0, 23, v0
 ; SI-NEXT:    s_mov_b32 s4, 0
 ; SI-NEXT:    s_movk_i32 s5, 0x80
 ; SI-NEXT:    v_or_b32_e32 v0, v0, v1
 ; SI-NEXT:    v_cmp_eq_u64_e32 vcc, s[4:5], v[2:3]
 ; SI-NEXT:    v_and_b32_e32 v1, 1, v0
 ; SI-NEXT:    v_cndmask_b32_e32 v1, 0, v1, vcc

 ; VI-NEXT:    v_cmp_eq_u32_e64 vcc, 0, 0
 ; VI-NEXT:    v_cndmask_b32_e32 v2, v3, v2, vcc
 ; VI-NEXT:    v_mov_b32_e32 v1, 0
 ; VI-NEXT:    v_sub_u32_e32 v4, vcc, 0xbe, v2
 ; VI-NEXT:    v_lshlrev_b64 v[2:3], v2, v[0:1]
 ; VI-NEXT:    v_cmp_ne_u64_e32 vcc, 0, v[0:1]
 ; VI-NEXT:    v_and_b32_e32 v1, 0x7fffffff, v3
 ; VI-NEXT:    v_cndmask_b32_e32 v0, 0, v4, vcc
-; VI-NEXT:    v_and_b32_e32 v3, s4, v1
+; VI-NEXT:    v_and_b32_e32 v3, s4, v3
 ; VI-NEXT:    v_lshrrev_b32_e32 v1, 8, v1
 ; VI-NEXT:    v_lshlrev_b32_e32 v0, 23, v0
 ; VI-NEXT:    s_mov_b32 s4, 0
 ; VI-NEXT:    s_movk_i32 s5, 0x80
 ; VI-NEXT:    v_or_b32_e32 v0, v0, v1
 ; VI-NEXT:    v_cmp_eq_u64_e32 vcc, s[4:5], v[2:3]
 ; VI-NEXT:    v_and_b32_e32 v1, 1, v0
 ; VI-NEXT:    v_cndmask_b32_e32 v1, 0, v1, vcc

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

 ; GFX7:       ; %bb.0:
 ; GFX7-NEXT:    s_and_b32 s0, s0, 0x3fff
 ; 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_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_lshl_b32 s0, s0, 2
 ; GFX9-NEXT:    ; return to shader part epilog
 ;
 ; GFX10-LABEL: s_shl_i32_zext_i16:
 ; GFX10:       ; %bb.0:
-; GFX10-NEXT:    s_and_b32 s0, s0, 0xffff
 ; GFX10-NEXT:    s_and_b32 s0, s0, 0x3fff
 ; GFX10-NEXT:    s_lshl_b32 s0, s0, 2
 ; GFX10-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
 }