[GlobalISel] Combine (x op 0) -> x for operations with a right identity of 0

[paquette]

Summary

Implement identity combines for operations like the following:

%a = G_SUB %b, 0

This can just be replaced with %b.

Over CTMark, this gives some minor size improvements at -O3.

[arsenm]

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

222

The people on your twitter poll are insane and MO is the clearly dominant abbreviation

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

198

Why not also handle add at the same time?

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

1527

Why not just getConstantVRegVal?

1527–1529

CombinerHelper seems to be reproducing bits that should belong in MIPatternMatch but I guess this case is fine. MIPatternMatch doesn't try to do any look throughs now.

We should really have an isZeroConstant that will also handle splat vectors

llvm/test/CodeGen/AArch64/GlobalISel/prelegalizercombiner-trivial-arith.mir

5–6

... at the end of the function

[aemerson]

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

222

Yes, this is terrible. And for that reason, I'm out.

[paquette]

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

222

58.93 twitter users agree that MOP is the morally superior abbreviation

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

198

Sure. It didn't show up too often, but I'll add it.

[paquette]

• Just do every right identity I can think of instead of just G_SUB
• Use mi_match
• Keep MOP because it's the right thing to do

[arsenm]

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

222

There's no word beginning with P here

[aemerson]

I'm back in.

[paquette]

71% of 92 twitter users (65.32 humans) agree that MOP is clearly better than MO, I'm going to stand by my principles here

MOP is

• Cleaner (it's a mop!)
• Contains the most important letter in "operand" (P)
• More fun to say

[arsenm]

In D76640#1939971, @paquette wrote:

71% of 92 twitter users (65.32 humans) agree that MOP is clearly better than MO, I'm going to stand by my principles here

MOP is

• Cleaner (it's a mop!)
• Contains the most important letter in "operand" (P)
• More fun to say

I am more objecting to the capitalization for something that is not an acronym. MO>MOp>>MOP

[paquette]

fix obvious misuse of mi_match

keep MOP

[aemerson]

Changed my mind again, I won't be a part of this.

[paquette]

You know, matchEqualDefs in this very file already uses MOP

[arsenm]

LGTM but MOp still better than MOP

[aemerson]

LGTM too. One day I'm going to change all MOPs to MOp when you're not looking anyway.

[dsanders]

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

222

FWIW, I'd prefer it if we didn't invent unconventional conventions when there already is a conventional convention

Also,
grep -rw MO llvm/ | wc -l

5113

grep -rw MOP llvm/ | wc -l

100

grep -rw MOp llvm/ | wc -l

21

:-)

[qcolombet]

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

222

+1.
MO has been the convention for quite some time now.

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

public:
 
   /// Delete \p MI and replace all of its uses with its \p OpIdx-th operand.
   bool replaceSingleDefInstWithOperand(MachineInstr &MI, unsigned OpIdx);
 
   /// Return true if \p MOP1 and \p MOP2 are register operands are defined by
   /// equivalent instructions.
   bool matchEqualDefs(const MachineOperand &MOP1, const MachineOperand &MOP2);
 
+  /// 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);
 
   /// Try to transform \p MI by using all of the above
   /// combine functions. Returns true if changed.
   bool tryCombine(MachineInstr &MI);
 
 private:

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 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]>;
 
-def identity_combines : GICombineGroup<[select_same_val]>;
+def identity_combines : GICombineGroup<[select_same_val, right_identity_zero]>;
 
 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

 //===-- lib/CodeGen/GlobalISel/GICombinerHelper.cpp -----------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 #include "llvm/CodeGen/GlobalISel/CombinerHelper.h"
 #include "llvm/CodeGen/GlobalISel/Combiner.h"
 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
 #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h"
+#include "llvm/CodeGen/GlobalISel/MIPatternMatch.h"
 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
 #include "llvm/CodeGen/GlobalISel/Utils.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/CodeGen/TargetLowering.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Target/TargetMachine.h"
 
 #define DEBUG_TYPE "gi-combiner"
 
 using namespace llvm;
+using namespace MIPatternMatch;
 
 // Option to allow testing of the combiner while no targets know about indexed
 // addressing.
 static cl::opt<bool>
     ForceLegalIndexing("force-legal-indexing", cl::Hidden, cl::init(false),
                        cl::desc("Force all indexed operations to be "
                                 "legal for the GlobalISel combiner"));
 
bool CombinerHelper::matchEqualDefs(const MachineOperand &MOP1,
   if (!I2)
     return false;
 
   // On the off-chance that there's some target instruction feeding into the
   // select, let's use produceSameValue instead of isIdenticalTo.
   return Builder.getTII().produceSameValue(*I1, *I2, &MRI);
 }
 
+bool CombinerHelper::matchConstantOp(const MachineOperand &MOP, int64_t C) {
+  if (!MOP.isReg())
+    return false;
+  int64_t Cst;
+  return mi_match(MOP.getReg(), MRI, m_ICst(Cst)) && Cst == C;
+}
+
 bool CombinerHelper::replaceSingleDefInstWithOperand(MachineInstr &MI,
                                                      unsigned OpIdx) {
   assert(MI.getNumExplicitDefs() == 1 && "Expected one explicit def?");
   Register OldReg = MI.getOperand(0).getReg();
   Register Replacement = MI.getOperand(OpIdx).getReg();
   assert(canReplaceReg(OldReg, Replacement, MRI) && "Cannot replace register?");
   MI.eraseFromParent();
   replaceRegWith(MRI, OldReg, Replacement);

llvm/test/CodeGen/AArch64/GlobalISel/prelegalizercombiner-trivial-arith.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:            right_ident_sub
+tracksRegLiveness: true
+body:             |
+  bb.1.entry:
+    liveins: $w0
+    ; Fold (x - 0) -> x
+    ;
+    ; CHECK-LABEL: name: right_ident_sub
+    ; CHECK: liveins: $w0
+    ; CHECK: %x:_(s32) = COPY $w0
+    ; CHECK: $w0 = COPY %x(s32)
+    ; CHECK: RET_ReallyLR implicit $w0
+    %x:_(s32) = COPY $w0
+    %cst:_(s32) = G_CONSTANT i32 0
+    %op:_(s32) = G_SUB %x(s32), %cst
+    $w0 = COPY %op(s32)
+    RET_ReallyLR implicit $w0
+
+...
+---
+name:            right_ident_add
+tracksRegLiveness: true
+body:             |
+  bb.1.entry:
+    liveins: $w0
+    ; Fold (x + 0) -> x
+    ;
+    ; CHECK-LABEL: name: right_ident_add
+    ; CHECK: liveins: $w0
+    ; CHECK: %x:_(s32) = COPY $w0
+    ; CHECK: $w0 = COPY %x(s32)
+    ; CHECK: RET_ReallyLR implicit $w0
+    %x:_(s32) = COPY $w0
+    %cst:_(s32) = G_CONSTANT i32 0
+    %op:_(s32) = G_ADD %x(s32), %cst
+    $w0 = COPY %op(s32)
+    RET_ReallyLR implicit $w0
+
+...
+---
+name:            right_ident_or
+tracksRegLiveness: true
+body:             |
+  bb.1.entry:
+    liveins: $w0
+    ; Fold (x || 0) -> x
+    ;
+    ; CHECK-LABEL: name: right_ident_or
+    ; CHECK: liveins: $w0
+    ; CHECK: %x:_(s32) = COPY $w0
+    ; CHECK: $w0 = COPY %x(s32)
+    ; CHECK: RET_ReallyLR implicit $w0
+    %x:_(s32) = COPY $w0
+    %cst:_(s32) = G_CONSTANT i32 0
+    %op:_(s32) = G_OR %x(s32), %cst
+    $w0 = COPY %op(s32)
+    RET_ReallyLR implicit $w0
+
+...
+---
+name:            right_ident_xor
+tracksRegLiveness: true
+body:             |
+  bb.1.entry:
+    liveins: $w0
+    ; Fold (x | 0) -> x
+    ;
+    ; CHECK-LABEL: name: right_ident_xor
+    ; CHECK: liveins: $w0
+    ; CHECK: %x:_(s32) = COPY $w0
+    ; CHECK: $w0 = COPY %x(s32)
+    ; CHECK: RET_ReallyLR implicit $w0
+    %x:_(s32) = COPY $w0
+    %cst:_(s32) = G_CONSTANT i32 0
+    %op:_(s32) = G_XOR %x(s32), %cst
+    $w0 = COPY %op(s32)
+    RET_ReallyLR implicit $w0
+
+...
+---
+name:            right_ident_shl
+tracksRegLiveness: true
+body:             |
+  bb.1.entry:
+    liveins: $w0
+    ; Fold (x << 0) -> x
+    ;
+    ; CHECK-LABEL: name: right_ident_shl
+    ; CHECK: liveins: $w0
+    ; CHECK: %x:_(s32) = COPY $w0
+    ; CHECK: $w0 = COPY %x(s32)
+    ; CHECK: RET_ReallyLR implicit $w0
+    %x:_(s32) = COPY $w0
+    %cst:_(s32) = G_CONSTANT i32 0
+    %op:_(s32) = G_SHL %x(s32), %cst
+    $w0 = COPY %op(s32)
+    RET_ReallyLR implicit $w0
+
+...
+---
+name:            right_ident_ashr
+tracksRegLiveness: true
+body:             |
+  bb.1.entry:
+    liveins: $w0
+    ; Fold (x ashr 0) -> x
+    ;
+    ; CHECK-LABEL: name: right_ident_ashr
+    ; CHECK: liveins: $w0
+    ; CHECK: %x:_(s32) = COPY $w0
+    ; CHECK: $w0 = COPY %x(s32)
+    ; CHECK: RET_ReallyLR implicit $w0
+    %x:_(s32) = COPY $w0
+    %cst:_(s32) = G_CONSTANT i32 0
+    %op:_(s32) = G_ASHR %x(s32), %cst
+    $w0 = COPY %op(s32)
+    RET_ReallyLR implicit $w0
+
+...
+---
+name:            right_ident_lshr
+tracksRegLiveness: true
+body:             |
+  bb.1.entry:
+    liveins: $w0
+    ; Fold (x lshr 0) -> x
+    ;
+    ; CHECK-LABEL: name: right_ident_lshr
+    ; CHECK: liveins: $w0
+    ; CHECK: %x:_(s32) = COPY $w0
+    ; CHECK: $w0 = COPY %x(s32)
+    ; CHECK: RET_ReallyLR implicit $w0
+    %x:_(s32) = COPY $w0
+    %cst:_(s32) = G_CONSTANT i32 0
+    %op:_(s32) = G_LSHR %x(s32), %cst
+    $w0 = COPY %op(s32)
+    RET_ReallyLR implicit $w0
+
+...
+---
+name:            dont_fold_sub
+tracksRegLiveness: true
+body:             |
+  bb.1.entry:
+    liveins: $w0
+    ; Not an identity, no folding.
+    ;
+    ; CHECK-LABEL: name: dont_fold_sub
+    ; CHECK: liveins: $w0
+    ; CHECK: %x:_(s32) = COPY $w0
+    ; CHECK: %cst:_(s32) = G_CONSTANT i32 1
+    ; CHECK: %op:_(s32) = G_SUB %x, %cst
+    ; CHECK: $w0 = COPY %op(s32)
+    ; CHECK: RET_ReallyLR implicit $w0
+    %x:_(s32) = COPY $w0
+    %cst:_(s32) = G_CONSTANT i32 1
+    %op:_(s32) = G_SUB %x(s32), %cst
+    $w0 = COPY %op(s32)
+    RET_ReallyLR implicit $w0
+...