[GISel] Add new GISel combiners for G_SELECT

[mkitzan]

Summary

Patch adds two new GICombinerRules for G_SELECT. The rules include: combining selects with undef comparisons into their first selectee value, and to combine away selects with constant comparisons. Patch additionally adds a new combiner test for the AArch64 target to test these new G_SELECT combiner rules and the existing select_same_val combiner rule.

[arsenm]

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

214

This may not be correct? See 1cf6f210a2ed87dcda2183fffd6f9aa17b5c493c

[mkitzan]

Looks like my local build wasn't building all the targets (sorry, fixed now). The AMDGPU test failed as a result of moving the existing select_same_val combiner out of the identity_combines group. The diff update moves select_same_val back to identity_combines group. The update does not address @arsenm's comment (waiting on feedback from @craig.topper).

[paquette]

I think all you should need is an equivalent to the NotPoison check in 1cf6f210a2ed87dcda2183fffd6f9aa17b5c493c, plus appropriate testcases.

[mkitzan]

Maybe? It's unclear to me what makes a ConstantExpr poison in the first place, and how combining with it would result in incorrect code (...new hire rolling through).

[arsenm]

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

206

This matches InstSimplify, although I do wonder why the choice isn't to select the RHS in this case. Since we generally prefer to canonicalize lower complexity expressions to the RHS, it seems like that would generally be the cheaper choice. I do think this should match the InstSimplify behavior though

214

Probably should split this into its own patch since it's questionable?

227

I've been thinking GIMatchData has the annoying property where every combine that uses the same thing needs to define its own GIDefMatchData.

[mkitzan]

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

214

Sounds reasonable. Will split that combine off into another patch.

[mkitzan]

Removed the combine for undef selectee value. Will open a separate patch to track that work.

[arsenm]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

1548–1549

I'm thinking there's no reason this needs to distinguish the undef and constant cases with D84165. However, that's making me second guess whether accepting G_IMPLICIT_DEF as an ordinary constant is a good idea if it can trigger the potentially poison case

[arsenm]

LGTM, although the undef and case can probably be merged

[mkitzan]

Thanks for the reviews. I don't have commit access, would be appreciated if someone could commit on my behalf. Thanks!

[mkitzan]

• Rebased and resolved conflicts
• Fixed test/CodeGen/AMDGPU/GlobalISel/postlegalizercombiner-select.mir to continue testing unmerge with same regs

[aditya_nandakumar]

I can commit for you if no one has gotten to it yet.

[mkitzan]

It was conflicted until the rebase update, so I doubt it was committed. Thanks for committing this!

[aditya_nandakumar]

rGdb464a3dbf0e

[aditya_nandakumar]

rGdb464a3dbf0e

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

public:
   bool matchAllExplicitUsesAreUndef(MachineInstr &MI);
 
   /// Return true if a G_SHUFFLE_VECTOR instruction \p MI has an undef mask.
   bool matchUndefShuffleVectorMask(MachineInstr &MI);
 
   /// Return true if a G_STORE instruction \p MI is storing an undef value.
   bool matchUndefStore(MachineInstr &MI);
 
+  /// Return true if a G_SELECT instruction \p MI has an undef comparison.
+  bool matchUndefSelectCmp(MachineInstr &MI);
+
+  /// Return true if a G_SELECT instruction \p MI has an undef select value. If
+  /// true, \p OpIdx will store the operand index of the known selected value.
+  bool matchUndefSelectVals(MachineInstr &MI, unsigned &ValIdx);
+
+  /// Return true if a G_SELECT instruction \p MI has a constant comparison. If
+  /// true, \p OpIdx will store the operand index of the known selected value.
+  bool matchConstantSelectCmp(MachineInstr &MI, unsigned &OpIdx);
+
   /// Replace an instruction with a G_FCONSTANT with value \p C.
   bool replaceInstWithFConstant(MachineInstr &MI, double C);
 
   /// Replace an instruction with a G_CONSTANT with value \p C.
   bool replaceInstWithConstant(MachineInstr &MI, int64_t C);
 
   /// Replace an instruction with a G_IMPLICIT_DEF.
   bool replaceInstWithUndef(MachineInstr &MI);

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

 // Fold (cond ? x : x) -> x
 def select_same_val: GICombineRule<
   (defs root:$root),
   (match (wip_match_opcode G_SELECT):$root,
     [{ return Helper.matchSelectSameVal(*${root}); }]),
   (apply [{ return Helper.replaceSingleDefInstWithOperand(*${root}, 2); }])
 >;
 
+// Fold (undef ? x : y) -> x
+def select_undef_cmp: GICombineRule<
+  (defs root:$root),
+  (match (wip_match_opcode G_SELECT):$root,
+    [{ return Helper.matchUndefSelectCmp(*${root}); }]),
+  (apply [{ return Helper.replaceSingleDefInstWithOperand(*${root}, 2); }])
+>;
+
+// Fold (cmp ? x : undef) -> x
+// Fold (cmp ? undef : y) -> y
+// Fold (cmp ? undef : undef) -> undef
+def select_undef_val_matchdata : GIDefMatchData<"unsigned">;
+def select_undef_val: GICombineRule<
+  (defs root:$root, select_undef_val_matchdata:$matchinfo),
+  (match (wip_match_opcode G_SELECT):$root,
+    [{ return Helper.matchUndefSelectVals(*${root}, ${matchinfo}); }]),
+  (apply [{ return Helper.replaceSingleDefInstWithOperand(*${root}, ${matchinfo}); }])
+>;
+
+// Fold (true ? x : y) -> x
+// Fold (false ? x : y) -> y
+def select_constant_cmp_matchdata : GIDefMatchData<"unsigned">;
+def select_constant_cmp: GICombineRule<
+  (defs root:$root, select_constant_cmp_matchdata:$matchinfo),
+  (match (wip_match_opcode G_SELECT):$root,
+    [{ return Helper.matchConstantSelectCmp(*${root}, ${matchinfo}); }]),
+  (apply [{ return Helper.replaceSingleDefInstWithOperand(*${root}, ${matchinfo}); }])
+>;
+
 // Fold x op 0 -> x
 def right_identity_zero: GICombineRule<
   (defs root:$root),
   (match (wip_match_opcode G_SUB, G_ADD, G_OR, G_XOR, G_SHL, G_ASHR, G_LSHR):$root,
     [{ return Helper.matchConstantOp(${root}->getOperand(2), 0); }]),
   (apply [{ return Helper.replaceSingleDefInstWithOperand(*${root}, 1); }])
 >;
 

 // 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]>;
+def identity_combines : GICombineGroup<[right_identity_zero, binop_same_val,
+                                        binop_left_to_zero, binop_right_to_zero]>;
+
+def select_combines : GICombineGroup<[select_same_val, select_undef_cmp, 
+                                      select_undef_val, select_constant_cmp]>;
 
 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]>;
+    select_combines, identity_combines, simplify_add_to_sub]>;

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

 }
 
 bool CombinerHelper::matchUndefStore(MachineInstr &MI) {
   assert(MI.getOpcode() == TargetOpcode::G_STORE);
   return getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF, MI.getOperand(0).getReg(),
                       MRI);
 }
 
+bool CombinerHelper::matchUndefSelectCmp(MachineInstr &MI) {
+  assert(MI.getOpcode() == TargetOpcode::G_SELECT);
+  return getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF, MI.getOperand(1).getReg(),
+                      MRI);
+}
+
+bool CombinerHelper::matchUndefSelectVals(MachineInstr &MI, unsigned &OpIdx) {
+  assert(MI.getOpcode() == TargetOpcode::G_SELECT);
+  if (getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF, MI.getOperand(2).getReg(),
+                   MRI)) {
+    // Select val0 is undef, choose select val1.
+    OpIdx = 3;
+    return true;
+  }
+  if (getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF, MI.getOperand(3).getReg(),
+                   MRI)) {
+    // Select val1 is undef, choose select val0.
+    OpIdx = 2;
+    return true;
+  }
+  return false;
+}
+
+bool CombinerHelper::matchConstantSelectCmp(MachineInstr &MI, unsigned &OpIdx) {
+  assert(MI.getOpcode() == TargetOpcode::G_SELECT);
+  if (auto MaybeCstCmp =
+          getConstantVRegValWithLookThrough(MI.getOperand(1).getReg(), MRI)) {
+    OpIdx = MaybeCstCmp->Value ? 2 : 3;
+    return true;
+  }
+  return false;
+}
+
 bool CombinerHelper::eraseInst(MachineInstr &MI) {
   MI.eraseFromParent();
   return true;
 }
 
 bool CombinerHelper::matchEqualDefs(const MachineOperand &MOP1,
                                     const MachineOperand &MOP2) {
   if (!MOP1.isReg() || !MOP2.isReg())

llvm/test/CodeGen/AArch64/GlobalISel/combine-select.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -run-pass=aarch64-prelegalizer-combiner -verify-machineinstrs -mtriple aarch64-unknown-unknown %s -o - | FileCheck %s
+# RUN: llc -debugify-and-strip-all-safe -run-pass=aarch64-prelegalizer-combiner -verify-machineinstrs -mtriple aarch64-unknown-unknown %s -o - | FileCheck %s
+---
+# select (c, x, x) -> x
+name:            agc.test_combine_select_same_res
+body:             |
+  bb.1:
+    liveins: $x0, $x1
+    ; CHECK-LABEL: name: agc.test_combine_select_same_res
+    ; CHECK: [[COPY:%[0-9]+]]:_(s64) = COPY $x0
+    ; CHECK: $x0 = COPY [[COPY]](s64)
+    %0:_(s64) = COPY $x0
+    %1:_(s1) = G_TRUNC %0
+    %2:_(s64) = G_SELECT %1, %0, %0
+    $x0 = COPY %2(s64)
+...
+---
+# select (undef, x, y) -> x
+name:            agc.test_combine_select_undef_res0_res1
+body:             |
+  bb.1:
+    liveins: $x0, $x1
+    ; CHECK-LABEL: name: agc.test_combine_select_undef_res0_res1
+    ; CHECK: [[COPY:%[0-9]+]]:_(s64) = COPY $x0
+    ; CHECK: $x0 = COPY [[COPY]](s64)
+    %0:_(s64) = COPY $x0
+    %1:_(s64) = COPY $x1
+    %2:_(s1) = G_IMPLICIT_DEF
+    %3:_(s64) = G_SELECT %2, %0, %1
+    $x0 = COPY %3(s64)
+...
+---
+# select (c, undef, y) -> y
+name:            agc.test_combine_select_cmp_undef_res1
+body:             |
+  bb.1:
+    liveins: $x0
+    ; CHECK-LABEL: name: agc.test_combine_select_cmp_undef_res1
+    ; CHECK: [[COPY:%[0-9]+]]:_(s64) = COPY $x0
+    ; CHECK: $x0 = COPY [[COPY]](s64)
+    %0:_(s64) = COPY $x0
+    %1:_(s1) = G_TRUNC %0
+    %2:_(s64) = G_IMPLICIT_DEF
+    %3:_(s64) = G_SELECT %1, %2, %0
+    $x0 = COPY %3(s64)
+...
+---
+# select (c, x, undef) -> x
+name:            agc.test_combine_select_cmp_res0_undef
+body:             |
+  bb.1:
+    liveins: $x0
+    ; CHECK-LABEL: name: agc.test_combine_select_cmp_res0_undef
+    ; CHECK: [[COPY:%[0-9]+]]:_(s64) = COPY $x0
+    ; CHECK: $x0 = COPY [[COPY]](s64)
+    %0:_(s64) = COPY $x0
+    %1:_(s1) = G_TRUNC %0
+    %2:_(s64) = G_IMPLICIT_DEF
+    %3:_(s64) = G_SELECT %1, %0, %2
+    $x0 = COPY %3(s64)
+...
+---
+# select (c, undef, undef) -> undef
+name:            agc.test_combine_select_cmp_undef_undef
+body:             |
+  bb.1:
+    liveins: $x0
+    ; CHECK-LABEL: name: agc.test_combine_select_cmp_undef_undef
+    ; CHECK: [[DEF:%[0-9]+]]:_(s64) = G_IMPLICIT_DEF
+    ; CHECK: $x0 = COPY [[DEF]](s64)
+    %0:_(s64) = COPY $x0
+    %1:_(s1) = G_TRUNC %0
+    %2:_(s64) = G_IMPLICIT_DEF
+    %3:_(s64) = G_IMPLICIT_DEF
+    %4:_(s64) = G_SELECT %1, %2, %3
+    $x0 = COPY %3(s64)
+...
+---
+# select (false, x, y) -> y
+name:            agc.test_combine_select_false_res0_res1
+body:             |
+  bb.1:
+    liveins: $x0, $x1
+    ; CHECK-LABEL: name: agc.test_combine_select_false_res0_res1
+    ; CHECK: [[COPY:%[0-9]+]]:_(s64) = COPY $x1
+    ; CHECK: $x0 = COPY [[COPY]](s64)
+    %0:_(s64) = COPY $x0
+    %1:_(s64) = COPY $x1
+    %2:_(s1) = G_CONSTANT i1 false
+    %3:_(s64) = G_SELECT %2, %0, %1
+    $x0 = COPY %3(s64)
+...
+---
+# select (true, x, y) -> x
+name:            agc.test_combine_select_true_res0_res1
+body:             |
+  bb.1:
+    liveins: $x0, $x1
+    ; CHECK-LABEL: name: agc.test_combine_select_true_res0_res1
+    ; CHECK: [[COPY:%[0-9]+]]:_(s64) = COPY $x0
+    ; CHECK: $x0 = COPY [[COPY]](s64)
+    %0:_(s64) = COPY $x0
+    %1:_(s64) = COPY $x1
+    %2:_(s1) = G_CONSTANT i1 true
+    %3:_(s64) = G_SELECT %2, %0, %1
+    $x0 = COPY %3(s64)
+...