[GlobalISel] Implement identity transforms for x op x -> x

[paquette]

Summary

When we have

a = G_OR x, x

or

b = G_AND y, y

We can drop the G_OR/G_AND and just use x/y respectively.

Also update arm64-fallback.ll because there was an or in there which hits this transformation.

[qcolombet]

Where do these patterns come from?
I would expect they would be eliminated by InstCombine in the IR.

[paquette]

@qcolombet I'm not entirely sure, but patterns like this do hit a couple times in CTMark (but not very frequently, just once or twice.)

I'm surprised that they aren't entirely handled by InstCombine, but I'm guessing that they tend to appear in codegen at least once in a while considering they all exist in the DAGCombiner as well.

My best guess is that more complex combines simplify things enough that these patterns become obvious and thus can be eliminated.

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

public:
 
   /// Return true if \p MOP is defined by a G_CONSTANT with a value equal to
   /// \p C.
   bool matchConstantOp(const MachineOperand &MOP, int64_t C);
 
   /// Optimize (cond ? x : x) -> x
   bool matchSelectSameVal(MachineInstr &MI);
 
+  /// Optimize (x op x) -> x
+  bool matchBinOpSameVal(MachineInstr &MI);
+
   /// 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/Target/GlobalISel/Combine.td

 // 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); }])
 >;
 
+// Fold (x op x) - > x
+def binop_same_val: GICombineRule<
+  (defs root:$root),
+  (match (wip_match_opcode G_AND, G_OR):$root,
+    [{ return Helper.matchBinOpSameVal(*${root}); }]),
+  (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]>;
 
-def identity_combines : GICombineGroup<[select_same_val, right_identity_zero]>;
+def identity_combines : GICombineGroup<[select_same_val, right_identity_zero,
+                                        binop_same_val]>;
 
 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]>;

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

 bool CombinerHelper::matchSelectSameVal(MachineInstr &MI) {
   assert(MI.getOpcode() == TargetOpcode::G_SELECT);
   // Match (cond ? x : x)
   return matchEqualDefs(MI.getOperand(2), MI.getOperand(3)) &&
          canReplaceReg(MI.getOperand(0).getReg(), MI.getOperand(2).getReg(),
                        MRI);
 }
 
+bool CombinerHelper::matchBinOpSameVal(MachineInstr &MI) {
+  return matchEqualDefs(MI.getOperand(1), MI.getOperand(2)) &&
+         canReplaceReg(MI.getOperand(0).getReg(), MI.getOperand(1).getReg(),
+                       MRI);
+}
+
 bool CombinerHelper::replaceInstWithFConstant(MachineInstr &MI, double C) {
   assert(MI.getNumDefs() == 1 && "Expected only one def?");
   Builder.setInstr(MI);
   Builder.buildFConstant(MI.getOperand(0), C);
   MI.eraseFromParent();
   return true;
 }
 

llvm/test/CodeGen/AArch64/GlobalISel/arm64-fallback.ll

 }
 
 ; FALLBACK-WITH-REPORT-ERR remark: <unknown>:0:0: unable to legalize instruction: G_STORE %3, %4 :: (store 12 into `i96* undef`, align 16) (in function: nonpow2_add_narrowing)
 ; FALLBACK-WITH-REPORT-ERR: warning: Instruction selection used fallback path for nonpow2_or_narrowing
 ; FALLBACK-WITH-REPORT-OUT-LABEL: nonpow2_or_narrowing:
 define void @nonpow2_or_narrowing() {
   %a = add i128 undef, undef
   %b = trunc i128 %a to i96
-  %dummy = or i96 %b, %b
+  %a2 = add i128 undef, undef
+  %b2 = trunc i128 %a2 to i96
+  %dummy = or i96 %b, %b2
   store i96 %dummy, i96* undef
   ret void
 }
 
 ; FALLBACK-WITH-REPORT-ERR remark: <unknown>:0:0: unable to legalize instruction: G_STORE %0, %1 :: (store 12 into `i96* undef`, align 16) (in function: nonpow2_load_narrowing)
 ; FALLBACK-WITH-REPORT-ERR: warning: Instruction selection used fallback path for nonpow2_load_narrowing
 ; FALLBACK-WITH-REPORT-OUT-LABEL: nonpow2_load_narrowing:
 define void @nonpow2_load_narrowing() {

llvm/test/CodeGen/AArch64/GlobalISel/prelegalizercombiner-binop-same-val.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple aarch64 -run-pass=aarch64-prelegalizer-combiner -verify-machineinstrs %s -o - | FileCheck %s
+
+name:            or_same
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $x0
+
+    ; Fold: x or x -> x
+    ; CHECK-LABEL: name: or_same
+    ; CHECK: liveins: $x0
+    ; CHECK: %copy:_(s64) = COPY $x0
+    ; CHECK: $x0 = COPY %copy(s64)
+    ; CHECK: RET_ReallyLR implicit $x0
+    %copy:_(s64) = COPY $x0
+    %or:_(s64) = G_OR %copy, %copy
+    $x0 = COPY %or(s64)
+    RET_ReallyLR implicit $x0
+
+...
+---
+name:            and_same
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $x0
+
+    ; Fold: x and x -> x
+
+    ; CHECK-LABEL: name: and_same
+    ; CHECK: liveins: $x0
+    ; CHECK: %copy:_(s64) = COPY $x0
+    ; CHECK: $x0 = COPY %copy(s64)
+    ; CHECK: RET_ReallyLR implicit $x0
+    %copy:_(s64) = COPY $x0
+    %and:_(s64) = G_AND %copy, %copy
+    $x0 = COPY %and(s64)
+    RET_ReallyLR implicit $x0
+
+...
+---
+name:            and_same2
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $x0, $x1
+
+    ; We can fold when the LHS and RHS are guaranteed to be identical.
+
+    ; CHECK-LABEL: name: and_same2
+    ; CHECK: liveins: $x0, $x1
+    ; CHECK: %copy1:_(s64) = COPY $x0
+    ; CHECK: %copy2:_(s64) = COPY $x1
+    ; CHECK: %or:_(s64) = G_OR %copy1, %copy2
+    ; CHECK: $x0 = COPY %or(s64)
+    ; CHECK: RET_ReallyLR implicit $x0
+    %copy1:_(s64) = COPY $x0
+    %copy2:_(s64) = COPY $x1
+    %or:_(s64) = G_OR %copy1, %copy2
+    %same_as_or:_(s64) = COPY %or(s64)
+    %and:_(s64) = G_AND %or, %same_as_or
+    $x0 = COPY %and(s64)
+    RET_ReallyLR implicit $x0
+
+...
+---
+name:            or_and_not_same
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $x0, $x1, $x2
+
+    ; None of the G_ORs or G_ANDs should be eliminated here, because their LHS
+    ; and RHS values are different.
+
+    ; CHECK-LABEL: name: or_and_not_same
+    ; CHECK: liveins: $x0, $x1, $x2
+    ; CHECK: %copy1:_(s64) = COPY $x0
+    ; CHECK: %copy2:_(s64) = COPY $x1
+    ; CHECK: %copy3:_(s64) = COPY $x2
+    ; CHECK: %or1:_(s64) = G_OR %copy1, %copy2
+    ; CHECK: %or2:_(s64) = G_OR %copy1, %copy3
+    ; CHECK: %and:_(s64) = G_AND %or1, %or2
+    ; CHECK: $x0 = COPY %and(s64)
+    ; CHECK: RET_ReallyLR implicit $x0
+    %copy1:_(s64) = COPY $x0
+    %copy2:_(s64) = COPY $x1
+    %copy3:_(s64) = COPY $x2
+    %or1:_(s64) = G_OR %copy1, %copy2
+    %or2:_(s64) = G_OR %copy1, %copy3
+    %and:_(s64) = G_AND %or1, %or2
+    $x0 = COPY %and(s64)
+    RET_ReallyLR implicit $x0
+
+...