[AArch64][GlobalISel] combine (and (or x, c1), c2) => (and x, c2) iff c1 & c2 == 0

[jroelofs]

Summary

https://godbolt.org/z/h8ejrG4hb

rdar://83597585

[paquette]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

4030

Could you just replace the operands of the existing G_AND rather than building a new G_AND?

llvm/test/CodeGen/AArch64/GlobalISel/combine-and-or-disjoint-mask.mir

6

maybe a vector testcase too?

[jroelofs]

Modify the G_AND in-place, and ignore vector types.

[jroelofs]

ping

[paquette]

LGTM

(Maybe add a comment explaining why you're ignoring vectors here though.)

[foad]

This is another case that would ideally be handled with demanded bits analysis. We would visit (or x, c1), see that none of the bits set in c1 are demanded, and simplify to x.

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

public:
   bool matchICmpToTrueFalseKnownBits(MachineInstr &MI, int64_t &MatchInfo);
 
   /// \returns true if a G_ICMP \p MI can be replaced with its LHS based off of
   /// KnownBits information.
   bool
   matchICmpToLHSKnownBits(MachineInstr &MI,
                           BuildFnTy &MatchInfo);
 
+  /// \returns true if (and (or x, c1), c2) can be replaced with (and x, c2)
+  bool matchAndOrDisjointMask(MachineInstr &MI, BuildFnTy &MatchInfo);
+
   bool matchBitfieldExtractFromSExtInReg(MachineInstr &MI,
                                          BuildFnTy &MatchInfo);
   /// Match: and (lshr x, cst), mask -> ubfx x, cst, width
   bool matchBitfieldExtractFromAnd(MachineInstr &MI, BuildFnTy &MatchInfo);
 
   /// Match: shr (shl x, n), k -> sbfx/ubfx x, pos, width
   bool matchBitfieldExtractFromShr(MachineInstr &MI, BuildFnTy &MatchInfo);
 

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

def icmp_to_true_false_known_bits : GICombineRule<
   (apply [{ Helper.replaceInstWithConstant(*${d}, ${matchinfo}); }])>;
 
 def icmp_to_lhs_known_bits : GICombineRule<
   (defs root:$root, build_fn_matchinfo:$info),
   (match (wip_match_opcode G_ICMP):$root,
          [{ return Helper.matchICmpToLHSKnownBits(*${root}, ${info}); }]),
   (apply [{ Helper.applyBuildFn(*${root}, ${info}); }])>;
 
+def and_or_disjoint_mask : GICombineRule<
+  (defs root:$root, build_fn_matchinfo:$info),
+  (match (wip_match_opcode G_AND):$root,
+         [{ return Helper.matchAndOrDisjointMask(*${root}, ${info}); }]),
+  (apply [{ Helper.applyBuildFnNoErase(*${root}, ${info}); }])>;
+
 def bitfield_extract_from_and : GICombineRule<
   (defs root:$root, build_fn_matchinfo:$info),
   (match (wip_match_opcode G_AND):$root,
     [{ return Helper.matchBitfieldExtractFromAnd(*${root}, ${info}); }]),
   (apply [{ Helper.applyBuildFn(*${root}, ${info}); }])>;
 
 def funnel_shift_combines : GICombineGroup<[funnel_shift_to_rotate]>;
 
def all_combines : GICombineGroup<[trivial_combines, insert_vec_elt_combines,
     known_bits_simplifications, ext_ext_fold,
     not_cmp_fold, opt_brcond_by_inverting_cond,
     unmerge_merge, fabs_fabs_fold, unmerge_cst, unmerge_dead_to_trunc,
     unmerge_zext_to_zext, merge_unmerge, trunc_ext_fold, trunc_shl,
     const_combines, xor_of_and_with_same_reg, ptr_add_with_zero,
     shift_immed_chain, shift_of_shifted_logic_chain, load_or_combine,
     truncstore_merge, div_rem_to_divrem, funnel_shift_combines,
     form_bitfield_extract, constant_fold, fabs_fneg_fold,
-    intdiv_combines, mulh_combines, redundant_neg_operands]>;
+    intdiv_combines, mulh_combines, redundant_neg_operands,
+    and_or_disjoint_mask ]>;
 
 // A combine group used to for prelegalizer combiners at -O0. The combines in
 // this group have been selected based on experiments to balance code size and
 // compile time performance.
 def optnone_combines : GICombineGroup<[trivial_combines,
     ptr_add_immed_chain, combines_for_extload,
     not_cmp_fold, opt_brcond_by_inverting_cond]>;

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

bool CombinerHelper::matchICmpToLHSKnownBits(
   if (DstSize != LHSSize)
     Op = DstSize < LHSSize ? TargetOpcode::G_TRUNC : TargetOpcode::G_ZEXT;
   if (!isLegalOrBeforeLegalizer({Op, {DstTy, LHSTy}}))
     return false;
   MatchInfo = [=](MachineIRBuilder &B) { B.buildInstr(Op, {Dst}, {LHS}); };
   return true;
 }
 
+// Replace (and (or x, c1), c2) with (and x, c2) iff c1 & c2 == 0
+bool CombinerHelper::matchAndOrDisjointMask(
+    MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) {
+  assert(MI.getOpcode() == TargetOpcode::G_AND);
+
+  // Ignore vector types to simplify matching the two constants.
+  // TODO: do this for vectors and scalars via a demanded bits analysis.
+  LLT Ty = MRI.getType(MI.getOperand(0).getReg());
+  if (Ty.isVector())
+    return false;
+
+  Register Src;
+  int64_t MaskAnd;
+  int64_t MaskOr;
+  if (!mi_match(MI, MRI,
+                m_GAnd(m_GOr(m_Reg(Src), m_ICst(MaskOr)), m_ICst(MaskAnd))))
+    return false;
+
+  // Check if MaskOr could turn on any bits in Src.
+  if (MaskAnd & MaskOr)
+    return false;
+
+  MatchInfo = [=, &MI](MachineIRBuilder &B) {
+    Observer.changingInstr(MI);
+    MI.getOperand(1).setReg(Src);
+    Observer.changedInstr(MI);
+  };
+  return true;
+}
+
 /// Form a G_SBFX from a G_SEXT_INREG fed by a right shift.
 bool CombinerHelper::matchBitfieldExtractFromSExtInReg(
     MachineInstr &MI, std::function<void(MachineIRBuilder &)> &MatchInfo) {
   assert(MI.getOpcode() == TargetOpcode::G_SEXT_INREG);
   Register Dst = MI.getOperand(0).getReg();
   Register Src = MI.getOperand(1).getReg();
   LLT Ty = MRI.getType(Src);
   LLT ExtractTy = getTargetLowering().getPreferredShiftAmountTy(Ty);

llvm/test/CodeGen/AArch64/GlobalISel/combine-and-or-disjoint-mask.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+
+# RUN: llc -mtriple aarch64 -run-pass=aarch64-prelegalizer-combiner --aarch64prelegalizercombinerhelper-only-enable-rule="and_or_disjoint_mask" -global-isel -verify-machineinstrs %s -o - | FileCheck %s
+# REQUIRES: asserts
+
+...
+---
+name:            disjoint_masks
+tracksRegLiveness: true
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    liveins: $w0
+    ; CHECK-LABEL: name: disjoint_masks
+    ; CHECK: liveins: $w0
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: %x:_(s32) = COPY $w0
+    ; CHECK-NEXT: %two:_(s32) = G_CONSTANT i32 2
+    ; CHECK-NEXT: %and:_(s32) = G_AND %x, %two
+    ; CHECK-NEXT: $w0 = COPY %and(s32)
+    ; CHECK-NEXT: RET_ReallyLR implicit $w0
+    %x:_(s32) = COPY $w0
+    %one:_(s32) = G_CONSTANT i32 1
+    %two:_(s32) = G_CONSTANT i32 2
+    %or:_(s32) = G_OR %x, %one
+    %and:_(s32) = G_AND %or, %two
+    $w0 = COPY %and(s32)
+    RET_ReallyLR implicit $w0
+...
+---
+name:            intersecting_masks
+tracksRegLiveness: true
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    liveins: $w0
+    ; CHECK-LABEL: name: intersecting_masks
+    ; CHECK: liveins: $w0
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: %x:_(s32) = COPY $w0
+    ; CHECK-NEXT: %one:_(s32) = G_CONSTANT i32 3
+    ; CHECK-NEXT: %two:_(s32) = G_CONSTANT i32 2
+    ; CHECK-NEXT: %or:_(s32) = G_OR %x, %one
+    ; CHECK-NEXT: %and:_(s32) = G_AND %or, %two
+    ; CHECK-NEXT: $w0 = COPY %and(s32)
+    ; CHECK-NEXT: RET_ReallyLR implicit $w0
+    %x:_(s32) = COPY $w0
+    %one:_(s32) = G_CONSTANT i32 3
+    %two:_(s32) = G_CONSTANT i32 2
+    %or:_(s32) = G_OR %x, %one
+    %and:_(s32) = G_AND %or, %two
+    $w0 = COPY %and(s32)
+    RET_ReallyLR implicit $w0
+...
+---
+name:            disjoint_masks_v
+tracksRegLiveness: true
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    liveins: $x0
+    ; CHECK-LABEL: name: disjoint_masks_v
+    ; CHECK: liveins: $x0
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: %x:_(<2 x s32>) = COPY $x0
+    ; CHECK-NEXT: %one:_(s32) = G_CONSTANT i32 1
+    ; CHECK-NEXT: %one_v:_(<2 x s32>) = G_DUP %one(s32)
+    ; CHECK-NEXT: %two:_(s32) = G_CONSTANT i32 2
+    ; CHECK-NEXT: %two_v:_(<2 x s32>) = G_DUP %two(s32)
+    ; CHECK-NEXT: %or:_(<2 x s32>) = G_OR %x, %one_v
+    ; CHECK-NEXT: %and:_(<2 x s32>) = G_AND %or, %two_v
+    ; CHECK-NEXT: $x0 = COPY %and(<2 x s32>)
+    ; CHECK-NEXT: RET_ReallyLR implicit $x0
+    %x:_(<2 x s32>) = COPY $x0
+    %one:_(s32) = G_CONSTANT i32 1
+    %one_v:_(<2 x s32>) = G_DUP %one
+    %two:_(s32) = G_CONSTANT i32 2
+    %two_v:_(<2 x s32>) = G_DUP %two
+    %or:_(<2 x s32>) = G_OR %x, %one_v
+    %and:_(<2 x s32>) = G_AND %or, %two_v
+    $x0 = COPY %and(<2 x s32>)
+    RET_ReallyLR implicit $x0
+...