[GlobalISel] Fold xor(cmp(pred, _, _), 1) -> cmp(inverse(pred), _, _)

[aemerson]

Summary

This is needed for an upcoming change to how we translate conditional branches which might generate these.

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

1988–1994

Can generalize for not-i1 by checking the target boolean contents

[aemerson]

Use getBooleanContents and update AMDGPU tests.

[aemerson]

Check for multiple uses of the cmp.

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

1994

Swap the order of these checks?

llvm/test/CodeGen/AArch64/GlobalISel/prelegalizercombiner-invert-cmp.mir

137

Test with vectors?

[foad]

One of the globalisel code quality regressions vs selectiondag that I'm tracking comes from code like this:

%40:_(s1) = G_ICMP intpred(uge), %35:_(s32), %37:_
%41:_(s1) = G_ICMP intpred(uge), %36:_(s32), %38:_
%42:_(s1) = G_OR %40:_, %41:_
%43:_(s1) = G_CONSTANT i1 true
%44:sreg_64_xexec(s1) = G_XOR %42:_, %43:_
%46:sreg_64_xexec(s64) = SI_IF %44:sreg_64_xexec(s1), %bb.3, implicit-def $exec, implicit-def $scc, implicit $exec

So... is there any chance of extending this patch to be able to invert a whole tree of comparisons combined with ANDs and ORs?

[foad]

In D86383#2241544, @foad wrote:

So... is there any chance of extending this patch to be able to invert a whole tree of comparisons combined with ANDs and ORs?

I've had a go at this in D86709.

[aemerson]

Add support for vectors.

[arsenm]

llvm/lib/CodeGen/GlobalISel/Utils.cpp

708 ↗

(On Diff #288461)

One of these parameters is isVector, which is getting lost here

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

1995–2007

I think this isConstTrue logic should be merged into a separate function (at least the getScalarSizeInBits() == 1 case and check TLI for the extended version should be together)

2014

I guess technically TargetBooleanContents also depends on isFloat in the fcmp case

[aemerson]

Simplify and refactor code with FP case.

[aemerson]

Ping

[paquette]

Personally I can't see anything wrong with this at this point.

@arsenm?

[rupprecht]

FYI, I reverted this (and D86413 which depends on it) in 8693ddc74371dedc742c9f3d3e4eda1da72c13ea to keep the build green, as it was causing surprising crashes when running ninja check-llvm-codegen-aarch64-globalisel in release builds.

In case it goes away, the buildbot error is:

FAIL: LLVM :: CodeGen/AArch64/GlobalISel/prelegalizercombiner-invert-cmp.mir (33345 of 67618)
******************** TEST 'LLVM :: CodeGen/AArch64/GlobalISel/prelegalizercombiner-invert-cmp.mir' FAILED ********************
Script:
--
: 'RUN: at line 2';   /home/buildslave/ps4-buildslave1/clang-with-thin-lto-ubuntu/build/stage1/bin/llc -mtriple aarch64-apple-ios  -run-pass=aarch64-prelegalizer-combiner --aarch64prelegalizercombinerhelper-only-enable-rule="not_cmp_fold" /home/buildslave/ps4-buildslave1/clang-with-thin-lto-ubuntu/llvm-project/llvm/test/CodeGen/AArch64/GlobalISel/prelegalizercombiner-invert-cmp.mir -o - -verify-machineinstrs | /home/buildslave/ps4-buildslave1/clang-with-thin-lto-ubuntu/build/stage1/bin/FileCheck /home/buildslave/ps4-buildslave1/clang-with-thin-lto-ubuntu/llvm-project/llvm/test/CodeGen/AArch64/GlobalISel/prelegalizercombiner-invert-cmp.mir
--
Exit Code: 2

Command Output (stderr):
--
LLVM ERROR: Invalid rule identifier
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace.
Stack dump:
0.	Program arguments: /home/buildslave/ps4-buildslave1/clang-with-thin-lto-ubuntu/build/stage1/bin/llc -mtriple aarch64-apple-ios -run-pass=aarch64-prelegalizer-combiner --aarch64prelegalizercombinerhelper-only-enable-rule=not_cmp_fold /home/buildslave/ps4-buildslave1/clang-with-thin-lto-ubuntu/llvm-project/llvm/test/CodeGen/AArch64/GlobalISel/prelegalizercombiner-invert-cmp.mir -o - -verify-machineinstrs 
1.	Running pass 'Function Pass Manager' on module '/home/buildslave/ps4-buildslave1/clang-with-thin-lto-ubuntu/llvm-project/llvm/test/CodeGen/AArch64/GlobalISel/prelegalizercombiner-invert-cmp.mir'.
2.	Running pass 'AArch64PreLegalizerCombiner' on function '@icmp'
 #0 0x00005651667a183c llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/home/buildslave/ps4-buildslave1/clang-with-thin-lto-ubuntu/build/stage1/bin/llc+0x25cc83c)
 #1 0x000056516679f694 llvm::sys::RunSignalHandlers() (/home/buildslave/ps4-buildslave1/clang-with-thin-lto-ubuntu/build/stage1/bin/llc+0x25ca694)
 #2 0x000056516679f7e3 SignalHandler(int) (/home/buildslave/ps4-buildslave1/clang-with-thin-lto-ubuntu/build/stage1/bin/llc+0x25ca7e3)
 #3 0x00007f71603c58a0 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x128a0)
 #4 0x00007f715f293f47 raise (/lib/x86_64-linux-gnu/libc.so.6+0x3ef47)
 #5 0x00007f715f2958b1 abort (/lib/x86_64-linux-gnu/libc.so.6+0x408b1)
 #6 0x000056516671a1d6 llvm::report_fatal_error(llvm::Twine const&, bool) (/home/buildslave/ps4-buildslave1/clang-with-thin-lto-ubuntu/build/stage1/bin/llc+0x25451d6)
 #7 0x000056516671a2f8 (/home/buildslave/ps4-buildslave1/clang-with-thin-lto-ubuntu/build/stage1/bin/llc+0x25452f8)
 #8 0x0000565164a62751 (anonymous namespace)::AArch64PreLegalizerCombiner::runOnMachineFunction(llvm::MachineFunction&) (/home/buildslave/ps4-buildslave1/clang-with-thin-lto-ubuntu/build/stage1/bin/llc+0x88d751)
 #9 0x0000565165d08b78 llvm::MachineFunctionPass::runOnFunction(llvm::Function&) (/home/buildslave/ps4-buildslave1/clang-with-thin-lto-ubuntu/build/stage1/bin/llc+0x1b33b78)
#10 0x00005651660d9af7 llvm::FPPassManager::runOnFunction(llvm::Function&) (/home/buildslave/ps4-buildslave1/clang-with-thin-lto-ubuntu/build/stage1/bin/llc+0x1f04af7)
#11 0x00005651660da211 llvm::FPPassManager::runOnModule(llvm::Module&) (/home/buildslave/ps4-buildslave1/clang-with-thin-lto-ubuntu/build/stage1/bin/llc+0x1f05211)
#12 0x00005651660d8e6f llvm::legacy::PassManagerImpl::run(llvm::Module&) (/home/buildslave/ps4-buildslave1/clang-with-thin-lto-ubuntu/build/stage1/bin/llc+0x1f03e6f)
#13 0x000056516491a6e7 compileModule(char**, llvm::LLVMContext&) (/home/buildslave/ps4-buildslave1/clang-with-thin-lto-ubuntu/build/stage1/bin/llc+0x7456e7)
#14 0x0000565164871cf7 main (/home/buildslave/ps4-buildslave1/clang-with-thin-lto-ubuntu/build/stage1/bin/llc+0x69ccf7)
#15 0x00007f715f276b97 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b97)
#16 0x000056516491380a _start (/home/buildslave/ps4-buildslave1/clang-with-thin-lto-ubuntu/build/stage1/bin/llc+0x73e80a)
FileCheck error: '<stdin>' is empty.
FileCheck command line:  /home/buildslave/ps4-buildslave1/clang-with-thin-lto-ubuntu/build/stage1/bin/FileCheck /home/buildslave/ps4-buildslave1/clang-with-thin-lto-ubuntu/llvm-project/llvm/test/CodeGen/AArch64/GlobalISel/prelegalizercombiner-invert-cmp.mir

[aemerson]

Thanks, it seems the test doesn't work without asserts enabled. I've re-committed it fixed in 520ab710fb6f9829b4e70fda1dcc91ed4f614d0a

[rupprecht]

Thanks!

Usually, tests that are marked # REQUIRES: asserts are done so because they make use of some code that is only available behind NDEBUG. However, in this case, it's outright crashing on certain inputs when not in debug mode. At a first glance, that doesn't seem like a correct fix to me -- after all, the crashing bug is still there -- but I'm not familiar with this code, so I'm probably missing something?

[aemerson]

In D86383#2250882, @rupprecht wrote:

Thanks!

Usually, tests that are marked # REQUIRES: asserts are done so because they make use of some code that is only available behind NDEBUG. However, in this case, it's outright crashing on certain inputs when not in debug mode. At a first glance, that doesn't seem like a correct fix to me -- after all, the crashing bug is still there -- but I'm not familiar with this code, so I'm probably missing something?

There's no bug in the actual patch, the crash is because the testing flag --aarch64prelegalizercombinerhelper-only-enable-rule doesn't work without assertions enabled. It's not an elegant failure mode, but nothing to worry I think.

[rupprecht]

Ok. Thanks for confirming!

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

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);
 
+  /// Combine inverting a result of a compare into the opposite cond code.
+  bool matchNotCmp(MachineInstr &MI, Register &CmpReg);
+  bool applyNotCmp(MachineInstr &MI, Register &CmpReg);
+
   /// Try to transform \p MI by using all of the above
   /// combine functions. Returns true if changed.
   bool tryCombine(MachineInstr &MI);
 
 private:
   // Memcpy family optimization helpers.
   bool optimizeMemcpy(MachineInstr &MI, Register Dst, Register Src,
                       unsigned KnownLen, Align DstAlign, Align SrcAlign,

llvm/include/llvm/CodeGen/GlobalISel/MIPatternMatch.h

 
 template <typename LHS, typename RHS>
 inline BinaryOp_match<LHS, RHS, TargetOpcode::G_AND, true>
 m_GAnd(const LHS &L, const RHS &R) {
   return BinaryOp_match<LHS, RHS, TargetOpcode::G_AND, true>(L, R);
 }
 
 template <typename LHS, typename RHS>
+inline BinaryOp_match<LHS, RHS, TargetOpcode::G_XOR, true>
+m_GXor(const LHS &L, const RHS &R) {
+  return BinaryOp_match<LHS, RHS, TargetOpcode::G_XOR, true>(L, R);
+}
+
+template <typename LHS, typename RHS>
 inline BinaryOp_match<LHS, RHS, TargetOpcode::G_OR, true> m_GOr(const LHS &L,
                                                                 const RHS &R) {
   return BinaryOp_match<LHS, RHS, TargetOpcode::G_OR, true>(L, R);
 }
 
 template <typename LHS, typename RHS>
 inline BinaryOp_match<LHS, RHS, TargetOpcode::G_SHL, false>
 m_GShl(const LHS &L, const RHS &R) {

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

 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});}])
 >;
 
+def not_cmp_fold_matchinfo : GIDefMatchData<"Register">;
+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 [{ return Helper.applyNotCmp(*${d}, ${info}); }])
+>;
+
 // FIXME: These should use the custom predicate feature once it lands.
 def undef_combines : GICombineGroup<[undef_to_fp_zero, undef_to_int_zero,
                                      undef_to_negative_one,
                                      propagate_undef_any_op,
                                      propagate_undef_all_ops,
                                      propagate_undef_shuffle_mask,
                                      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]>;
 
 def trivial_combines : GICombineGroup<[copy_prop, mul_to_shl]>;
 def all_combines : GICombineGroup<[trivial_combines, ptr_add_immed_chain,
     combines_for_extload, combine_indexed_load_store, undef_combines,
     identity_combines, simplify_add_to_sub,
     hoist_logic_op_with_same_opcode_hands,
-    shl_ashr_to_sext_inreg, sext_inreg_of_load]>;
+    shl_ashr_to_sext_inreg, sext_inreg_of_load,
+    not_cmp_fold]>;

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;
 }
 
+bool CombinerHelper::matchNotCmp(MachineInstr &MI, Register &CmpReg) {
+  assert(MI.getOpcode() == TargetOpcode::G_XOR);
+  LLT I1 = LLT::scalar(1);
+  Register XorSrc;
+  int64_t Cst;
+  // We match xor(src, i1) here.
+  if (!mi_match(
+          MI.getOperand(0).getReg(), MRI,
+          m_all_of(m_SpecificType(I1), m_GXor(m_Reg(XorSrc), m_ICst(Cst)))))
+    return false;
+  // The i1 true is be represented as a -1 as a sign-extended constant.
+  if (Cst != -1)
+    return false;
+
+  // Now try match src to either icmp or fcmp.
+  if (!mi_match(XorSrc, MRI, m_GICmp(m_Pred(), m_Reg(), m_Reg()))) {
+    // Try fcmp.
+    if (!mi_match(XorSrc, MRI, m_GFCmp(m_Pred(), m_Reg(), m_Reg())))
+      return false;
+  }
+  CmpReg = XorSrc;
+  return true;
+}
+
+bool CombinerHelper::applyNotCmp(MachineInstr &MI, Register &CmpReg) {
+  MachineInstr *CmpDef = MRI.getVRegDef(CmpReg);
+  assert(CmpDef && "Should have been given an MI reg");
+  assert(CmpDef->getOpcode() == TargetOpcode::G_ICMP ||
+         CmpDef->getOpcode() == TargetOpcode::G_FCMP);
+
+  Observer.changingInstr(*CmpDef);
+  MachineOperand &PredOp = CmpDef->getOperand(1);
+  CmpInst::Predicate NewP = CmpInst::getInversePredicate(
+      (CmpInst::Predicate)PredOp.getPredicate());
+  PredOp.setPredicate(NewP);
+  Observer.changedInstr(*CmpDef);
+
+  replaceRegWith(MRI, MI.getOperand(0).getReg(),
+                 CmpDef->getOperand(0).getReg());
+  MI.eraseFromParent();
+  return true;
+}
+
 bool CombinerHelper::tryCombine(MachineInstr &MI) {
   if (tryCombineCopy(MI))
     return true;
   if (tryCombineExtendingLoads(MI))
     return true;
   if (tryCombineIndexedLoadStore(MI))
     return true;
   return false;
 }

llvm/test/CodeGen/AArch64/GlobalISel/prelegalizercombiner-invert-cmp.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple aarch64-apple-ios  -run-pass=aarch64-prelegalizer-combiner %s -o - -verify-machineinstrs | FileCheck %s
+
+# Check that we fold an compare result inverted into just inverting the condition code.
+---
+name: icmp
+tracksRegLiveness: true
+body:             |
+  bb.1:
+    liveins: $x0
+
+    ; CHECK-LABEL: name: icmp
+    ; CHECK: liveins: $x0
+    ; CHECK: [[COPY:%[0-9]+]]:_(s64) = COPY $x0
+    ; CHECK: [[C:%[0-9]+]]:_(s64) = G_CONSTANT i64 1
+    ; CHECK: [[ICMP:%[0-9]+]]:_(s1) = G_ICMP intpred(sle), [[COPY]](s64), [[C]]
+    ; CHECK: [[ANYEXT:%[0-9]+]]:_(s32) = G_ANYEXT [[ICMP]](s1)
+    ; CHECK: $w0 = COPY [[ANYEXT]](s32)
+    ; CHECK: RET_ReallyLR implicit $w0
+    %0:_(s64) = COPY $x0
+    %1:_(s64) = G_CONSTANT i64 1
+    %2:_(s1) = G_CONSTANT i1 1
+    %3:_(s1) = G_ICMP intpred(sgt), %0(s64), %1
+    %4:_(s1) = G_XOR %3, %2
+    %5:_(s32) = G_ANYEXT %4
+    $w0 = COPY %5(s32)
+    RET_ReallyLR implicit $w0
+...
+---
+name: fcmp
+tracksRegLiveness: true
+body:             |
+  bb.1:
+    liveins: $x0
+
+    ; CHECK-LABEL: name: fcmp
+    ; CHECK: liveins: $x0
+    ; CHECK: [[COPY:%[0-9]+]]:_(s64) = COPY $x0
+    ; CHECK: [[C:%[0-9]+]]:_(s64) = G_CONSTANT i64 1
+    ; CHECK: [[FCMP:%[0-9]+]]:_(s1) = G_FCMP floatpred(ule), [[COPY]](s64), [[C]]
+    ; CHECK: [[ANYEXT:%[0-9]+]]:_(s32) = G_ANYEXT [[FCMP]](s1)
+    ; CHECK: $w0 = COPY [[ANYEXT]](s32)
+    ; CHECK: RET_ReallyLR implicit $w0
+    %0:_(s64) = COPY $x0
+    %1:_(s64) = G_CONSTANT i64 1
+    %2:_(s1) = G_CONSTANT i1 1
+    %3:_(s1) = G_FCMP floatpred(ogt), %0(s64), %1
+    %4:_(s1) = G_XOR %3, %2
+    %5:_(s32) = G_ANYEXT %4
+    $w0 = COPY %5(s32)
+    RET_ReallyLR implicit $w0
+...
+---
+name: icmp_not_xor_with_1
+tracksRegLiveness: true
+body:             |
+  bb.1:
+    liveins: $x0
+
+    ; CHECK-LABEL: name: icmp_not_xor_with_1
+    ; CHECK: liveins: $x0
+    ; CHECK: [[COPY:%[0-9]+]]:_(s64) = COPY $x0
+    ; CHECK: [[C:%[0-9]+]]:_(s64) = G_CONSTANT i64 1
+    ; CHECK: [[ICMP:%[0-9]+]]:_(s1) = G_ICMP intpred(sgt), [[COPY]](s64), [[C]]
+    ; CHECK: [[ANYEXT:%[0-9]+]]:_(s32) = G_ANYEXT [[ICMP]](s1)
+    ; CHECK: $w0 = COPY [[ANYEXT]](s32)
+    ; CHECK: RET_ReallyLR implicit $w0
+    %0:_(s64) = COPY $x0
+    %1:_(s64) = G_CONSTANT i64 1
+    %2:_(s1) = G_CONSTANT i1 0
+    %3:_(s1) = G_ICMP intpred(sgt), %0(s64), %1
+    %4:_(s1) = G_XOR %3, %2
+    %5:_(s32) = G_ANYEXT %4
+    $w0 = COPY %5(s32)
+    RET_ReallyLR implicit $w0
+...