llvm-reduce: Add reduction for instruction defs

[arsenm]

Summary

Try to insert an implicit_def to replace the instruction's value,
replacing the original instruction's def with a dead register. If all
defs are delete the instruction entirely.

This is pretty similar to the instruction reduction, but leaves the
new defs in the same place as the original instruction. This could
possibly replace it. I'm not sure if we should directly delete the
instructions here, or leave dead ones behind.

This could also further work to replace physical register defs.

[arsenm]

ping

[MatzeB]

LGTM

llvm/tools/llvm-reduce/deltas/ReduceRegisterDefs.h

10

it's register defs isn't it?

[arsenm]

e24b390dbc4eb052241103265496ba34c8305723

llvm/test/tools/llvm-reduce/mir/generic-vreg.mir

 # REQUIRES: amdgpu-registered-target
 # RUN: llvm-reduce -abort-on-invalid-reduction -mtriple=amdgcn-amd-amdhsa --test FileCheck --test-arg --check-prefix=CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t 2> %t.log
 # RUN: FileCheck --match-full-lines --check-prefix=RESULT %s < %t
 
 # Verify that reduction works with generic virtual registers, and the
 # properties like register banks, types and names.
 
 
 # CHECK-INTERESTINGNESS: G_IMPLICIT_DEF
 # CHECK-INTERESTINGNESS: G_BITCAST
+# CHECK-INTERESTINGNESS: S_NOP 0, implicit %unused_load_ptr
 # CHECK-INTERESTINGNESS: G_ADD
 # CHECK-INTERESTINGNESS: G_IMPLICIT_DEF
 # CHECK-INTERESTINGNESS: G_STORE
+# CHECK-INTERESTINGNESS: S_ENDPGM 0, implicit %add(s64), implicit %v1(<2 x s16>), implicit %{{[0-9]+}}(s64)
 
 # RESULT: %{{[0-9]+}}:vgpr(s32) = G_IMPLICIT_DEF
-# RESULT-NEXT: %{{[0-9]+}}:vgpr(<2 x s16>) = G_IMPLICIT_DEF
-# RESULT-NEXT: %{{[0-9]+}}:sgpr(p1) = G_IMPLICIT_DEF
-# RESULT-NEXT: %{{[0-9]+}}:_(s64) = G_IMPLICIT_DEF
 # RESULT-NEXT: %{{[0-9]+}}:vreg_64(s64) = IMPLICIT_DEF
 # RESULT-NEXT: %{{[0-9]+}}:_(<2 x s32>) = G_IMPLICIT_DEF
+# RESULT-NEXT: %v1:vgpr(<2 x s16>) = G_IMPLICIT_DEF
+# RESULT-NEXT: %unused_load_ptr:sgpr(p1) = G_IMPLICIT_DEF
 # RESULT-NEXT: %aoeu:_(s64) = G_BITCAST %{{[0-9]+}}(<2 x s32>)
+# RESULT-NEXT: S_NOP 0, implicit %unused_load_ptr(p1)
 # RESULT-NEXT: %add:_(s64) = G_ADD %aoeu, %aoeu
 # RESULT-NEXT: %ptr:_(p1) = G_IMPLICIT_DEF
 # RESULT-NEXT: G_STORE %{{[0-9]+}}(s32), %ptr(p1) :: (store (s32), addrspace 1)
-# RESULT-NEXT: S_ENDPGM 0{{$}}
+# RESULT-NEXT: S_ENDPGM 0, implicit %add(s64), implicit %v1(<2 x s16>), implicit %14(s64)
 
 ---
 name:            f
 tracksRegLiveness: true
 body:             |
   bb.0:
     liveins: $vgpr0, $vgpr1, $vgpr2_vgpr3
     %v0:vgpr(s32) = COPY $vgpr0
     %v1:vgpr(<2 x s16>) = COPY $vgpr1
     %unused_load_ptr:sgpr(p1) = G_IMPLICIT_DEF
     %unused_load:_(s64) = G_LOAD %unused_load_ptr :: (load (s64), addrspace 1)
     G_STORE %unused_load, %unused_load_ptr :: (store (s64), addrspace 1)
     %2:vreg_64(s64) = COPY $vgpr2_vgpr3
     %arst:_(<2 x s32>) = G_IMPLICIT_DEF
     %aoeu:_(s64) = G_BITCAST %arst
-    S_NOP 0
+    S_NOP 0, implicit %unused_load_ptr
     %add:_(s64) = G_ADD %aoeu, %aoeu
     %ptr:_(p1) = G_IMPLICIT_DEF
     G_STORE %v0, %ptr :: (store 4, addrspace 1)
     S_ENDPGM 0, implicit %add, implicit %v1, implicit %2
 ...

llvm/test/tools/llvm-reduce/mir/reduce-register-defs.mir

+# REQUIRES: amdgpu-registered-target
+# RUN: llvm-reduce -abort-on-invalid-reduction -simplify-mir --delta-passes=register-defs -mtriple=amdgcn-amd-amdhsa --test FileCheck --test-arg --check-prefixes=CHECK-INTERESTINGNESS0,ALL --test-arg %s --test-arg --input-file %s -o %t 2> %t.log
+# RUN: FileCheck --match-full-lines --check-prefixes=RESULT0,ALL %s < %t
+
+# ALL-LABEL: name: func0
+# CHECK-INTERESTINGNESS0: V_MUL_F32
+
+# RESULT0: %mul1:vgpr_32 = IMPLICIT_DEF
+# RESULT0-NOT: V_ADD_CO_U32
+# RESULT0: %addco0:vgpr_32 = IMPLICIT_DEF
+# RESULT0-NEXT: %addco1:sreg_64_xexec = IMPLICIT_DEF
+# RESULT0-NOT: V_ADD_CO_U32
+
+---
+name: func0
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $vgpr0, $vgpr1
+
+    S_WAITCNT 0
+    %vgpr0:vgpr_32 = COPY $vgpr0
+    %vgpr1:vgpr_32 = COPY $vgpr1
+    %mul0:vgpr_32 = V_MUL_F32_e32 %vgpr0, %vgpr1, implicit $mode, implicit $exec
+    %mul1:vgpr_32 = V_MUL_F32_e32 %vgpr1, %vgpr0, implicit $mode, implicit $exec
+    %addco0:vgpr_32, %addco1:sreg_64_xexec = V_ADD_CO_U32_e64 %vgpr0, %vgpr1, 0, implicit $exec
+    S_NOP 0, implicit %addco0
+    S_NOP 0, implicit %addco1
+    S_ENDPGM 0, implicit %mul0, implicit %mul1
+...
+
+# ALL-LABEL: name: subreg_def
+# CHECK-INTERESTINGNESS0: %super.sub0
+
+# RESULT0: undef %super.sub1:vreg_64 = IMPLICIT_DEF
+---
+name: subreg_def
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $vgpr0, $vgpr1
+
+    %vgpr0:vgpr_32 = COPY $vgpr0
+    %vgpr1:vgpr_32 = COPY $vgpr1
+    undef %super.sub1:vreg_64 = V_ADD_F32_e32 %vgpr0, %vgpr1, implicit $mode, implicit $exec
+
+    S_NOP 0, implicit %super.sub0
+    S_ENDPGM 0, implicit %super.sub0
+...
+
+# Make sure we don't introduce multiple implicit_defs if an
+# instruction has repeated, identical defs.
+# ALL-LABEL: name: multi_def
+# CHECK-INTERESTINGNESS0: S_NOP 2
+
+# RESULT0: %redef:vgpr_32 = IMPLICIT_DEF
+# RESULT0-NOT: %redef:vgpr_32 = IMPLICIT_DEF
+---
+name: multi_def
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $vgpr0, $vgpr1
+
+    %vgpr0:vgpr_32 = COPY $vgpr0
+    %vgpr1:vgpr_32 = COPY $vgpr1
+    S_NOP 1, implicit-def %redef:vgpr_32, implicit-def %redef:vgpr_32
+    S_NOP 2, implicit %redef
+...
+
+# ALL-LABEL: name: multi_def_keep_two
+# CHECK-INTERESTINGNESS0: implicit-def %def0
+# CHECK-INTERESTINGNESS0: implicit-def %def2
+
+# RESULT0: %def1:vgpr_32 = IMPLICIT_DEF
+# RESULT0-NEXT: S_NOP 1, implicit-def %def0, implicit-def %def2
+# RESULT0-NEXT: S_NOP 2, implicit %def0, implicit %def1, implicit %def2
+
+---
+name: multi_def_keep_two
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $vgpr0, $vgpr1
+
+    %vgpr0:vgpr_32 = COPY $vgpr0
+    %vgpr1:vgpr_32 = COPY $vgpr1
+    S_NOP 1, implicit-def %def0:vgpr_32, implicit-def %def1:vgpr_32, implicit-def %def2:vgpr_32
+    S_NOP 2, implicit %def0, implicit %def1, implicit %def2
+...
+
+# ALL-LABEL: name: multi_def_subreg
+# CHECK-INTERESTINGNESS0: S_NOP 4
+
+# RESULT0: %redef.sub0:vreg_64 = IMPLICIT_DEF
+# RESULT0: %redef.sub1:vreg_64 = IMPLICIT_DEF
+---
+name: multi_def_subreg
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $vgpr0, $vgpr1
+
+    %vgpr0:vgpr_32 = COPY $vgpr0
+    %vgpr1:vgpr_32 = COPY $vgpr1
+    S_NOP 3, implicit-def %redef.sub0:vreg_64, implicit-def %redef.sub1:vreg_64
+    S_NOP 4, implicit %redef
+...
+
+# ALL-LABEL: name: multi_def_subreg_same_subreg
+# CHECK-INTERESTINGNESS0: S_NOP 4
+
+# RESULT0-NOT: implicit-def %redef
+# RESULT0: %redef.sub0:vreg_64 = IMPLICIT_DEF
+# RESULT0-NOT: implicit-def %redef
+---
+name: multi_def_subreg_same_subreg
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $vgpr0, $vgpr1
+
+    %vgpr0:vgpr_32 = COPY $vgpr0
+    %vgpr1:vgpr_32 = COPY $vgpr1
+    S_NOP 3, implicit-def %redef.sub0:vreg_64, implicit-def %redef.sub0:vreg_64
+    S_NOP 4, implicit %redef
+...
+
+# ALL-LABEL: name: tied_def
+# CHECK-INTERESTINGNESS0: V_MAC_F32
+
+# RESULT0: %mac0:vgpr_32 = V_MAC_F32_e32 %vgpr0, %vgpr1, %mac0, implicit $mode, implicit $exec
+# RESULT0: %mac1:vgpr_32 = IMPLICIT_DEF
+---
+name: tied_def
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $vgpr0, $vgpr1
+
+    S_WAITCNT 0
+    %vgpr0:vgpr_32 = COPY $vgpr0
+    %vgpr1:vgpr_32 = COPY $vgpr1
+    %mac0:vgpr_32 = V_MAC_F32_e32 %vgpr0, %vgpr1, %mac0, implicit $mode, implicit $exec
+    %mac1:vgpr_32 = V_MAC_F32_e32 %vgpr1, %vgpr0, %mac0, implicit $mode, implicit $exec
+    S_ENDPGM 0, implicit %mac0, implicit %mac1
+...
+
+# ALL-LABEL: name: generic_reg
+# CHECK-INTERESTINGNESS0: %fmul:vgpr(s32) =
+# RESULT0: %fmul:vgpr(s32) = G_IMPLICIT_DEF
+---
+name: generic_reg
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $vgpr0, $vgpr1
+
+    %vgpr0:vgpr_32(s32) = COPY $vgpr0
+    %vgpr1:vgpr_32(s32) = COPY $vgpr1
+    %fmul:vgpr(s32) = G_FMUL %vgpr0, %vgpr1
+    S_ENDPGM 0, implicit %fmul
+...
+
+# ALL-LABEL: name: terminator_def
+
+# CHECK-INTERESTINGNESS0: %exec_copy0:sreg_64_xexec = S_MOV_B64_term $exec
+
+# RESULT0: %exec_copy0:sreg_64_xexec = S_MOV_B64_term $exec
+# RESULT0-NEXT: %exec_copy1:sreg_64_xexec = S_MOV_B64_term $exec
+# RESULT-NEXT: S_CBRANCH_EXECZ
+---
+name: terminator_def
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $sgpr8_sgpr9
+
+    %exec_copy0:sreg_64_xexec = S_MOV_B64_term $exec
+    %exec_copy1:sreg_64_xexec = S_MOV_B64_term $exec
+    S_CBRANCH_EXECZ %bb.2, implicit $exec
+
+  bb.1:
+    S_NOP 7
+
+  bb.2:
+    S_ENDPGM 0, implicit %exec_copy0, implicit %exec_copy1
+...

llvm/tools/llvm-reduce/CMakeLists.txt

add_llvm_tool(llvm-reduce
   deltas/ReduceOperands.cpp
   deltas/ReduceOperandsSkip.cpp
   deltas/ReduceOperandsToArgs.cpp
   deltas/ReduceInstructionsMIR.cpp
   deltas/ReduceInstructionFlagsMIR.cpp
   deltas/ReduceIRReferences.cpp
   deltas/ReduceVirtualRegisters.cpp
   deltas/ReduceRegisterMasks.cpp
+  deltas/ReduceRegisterDefs.cpp
   deltas/ReduceRegisterUses.cpp
   deltas/SimplifyInstructions.cpp
   llvm-reduce.cpp
 
   DEPENDS
   intrinsics_gen
   )

llvm/tools/llvm-reduce/DeltaManager.cpp

 #include "deltas/ReduceInstructions.h"
 #include "deltas/ReduceInstructionsMIR.h"
 #include "deltas/ReduceMetadata.h"
 #include "deltas/ReduceModuleData.h"
 #include "deltas/ReduceOperandBundles.h"
 #include "deltas/ReduceOperands.h"
 #include "deltas/ReduceOperandsSkip.h"
 #include "deltas/ReduceOperandsToArgs.h"
+#include "deltas/ReduceRegisterDefs.h"
 #include "deltas/ReduceRegisterMasks.h"
 #include "deltas/ReduceRegisterUses.h"
 #include "deltas/ReduceSpecialGlobals.h"
 #include "deltas/ReduceVirtualRegisters.h"
 #include "deltas/SimplifyInstructions.h"
 #include "llvm/Support/CommandLine.h"
 
 using namespace llvm;

 #define DELTA_PASSES_MIR                                                       \
   DELTA_PASS("instructions", reduceInstructionsMIRDeltaPass)                   \
   DELTA_PASS("ir-instruction-references",                                      \
              reduceIRInstructionReferencesDeltaPass)                           \
   DELTA_PASS("ir-block-references", reduceIRBlockReferencesDeltaPass)          \
   DELTA_PASS("ir-function-references", reduceIRFunctionReferencesDeltaPass)    \
   DELTA_PASS("instruction-flags", reduceInstructionFlagsMIRDeltaPass)          \
   DELTA_PASS("register-uses", reduceRegisterUsesMIRDeltaPass)                  \
+  DELTA_PASS("register-defs", reduceRegisterDefsMIRDeltaPass)                  \
   DELTA_PASS("register-hints", reduceVirtualRegisterHintsDeltaPass)            \
   DELTA_PASS("register-masks", reduceRegisterMasksMIRDeltaPass)
 
 static void runAllDeltaPasses(TestRunner &Tester) {
 #define DELTA_PASS(NAME, FUNC) FUNC(Tester);
   if (Tester.getProgram().isMIR()) {
     DELTA_PASSES_MIR
   } else {

llvm/tools/llvm-reduce/deltas/ReduceRegisterDefs.h

+//===- ReduceRegisterDefs.h  - Specialized Delta Pass -----------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a function which calls the Generic Delta pass in order
+// to reduce uninteresting register uses from the MachineFunction.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEREGISTERDEFS_H
+#define LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEREGISTERDEFS_H
+
+#include "Delta.h"
+
+namespace llvm {
+void reduceRegisterDefsMIRDeltaPass(TestRunner &Test);
+} // namespace llvm
+
+#endif

llvm/tools/llvm-reduce/deltas/ReduceRegisterDefs.cpp

+//===- ReduceRegisterDefs.cpp - Specialized Delta Pass --------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a function which calls the Generic Delta pass in order
+// to reduce uninteresting register uses from the MachineFunction.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ReduceRegisterDefs.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/TargetInstrInfo.h"
+
+using namespace llvm;
+
+static void removeDefsFromFunction(Oracle &O, MachineFunction &MF) {
+  MachineRegisterInfo &MRI = MF.getRegInfo();
+  const TargetSubtargetInfo &STI = MF.getSubtarget();
+  const TargetInstrInfo *TII = STI.getInstrInfo();
+
+  DenseSet<MachineOperand *> KeepDefs;
+  DenseSet<TargetInstrInfo::RegSubRegPair> DeleteDefs;
+
+  for (MachineBasicBlock &MBB : MF) {
+    for (MachineBasicBlock::iterator It = MBB.begin(),
+                                     E = MBB.getFirstTerminator();
+         It != E;) {
+      MachineBasicBlock::iterator InsPt = It;
+      MachineInstr &MI = *It;
+      ++It;
+
+      KeepDefs.clear();
+      DeleteDefs.clear();
+
+      int NumOperands = MI.getNumOperands();
+      int NumRequiredOps = MI.getNumExplicitOperands() +
+                           MI.getDesc().getNumImplicitDefs() +
+                           MI.getDesc().getNumImplicitUses();
+
+      bool HaveDelete = false;
+      // Do an initial scan in case the instruction defines the same register
+      // multiple times.
+      for (int I = NumOperands - 1; I >= 0; --I) {
+        MachineOperand &MO = MI.getOperand(I);
+        if (!MO.isReg() || !MO.isDef())
+          continue;
+
+        TargetInstrInfo::RegSubRegPair RegPair(MO.getReg(), MO.getSubReg());
+        if (!RegPair.Reg.isVirtual())
+          continue;
+
+        if (O.shouldKeep())
+          KeepDefs.insert(&MO);
+        else
+          HaveDelete = true;
+      }
+
+      if (!HaveDelete)
+        continue;
+
+      bool HaveKeptDef = !KeepDefs.empty();
+      for (int I = NumOperands - 1; I >= 0; --I) {
+        MachineOperand &MO = MI.getOperand(I);
+        if (!MO.isReg() || !MO.isDef())
+          continue;
+
+        if (KeepDefs.count(&MO))
+          continue;
+
+        TargetInstrInfo::RegSubRegPair RegPair(MO.getReg(), MO.getSubReg());
+        if (!RegPair.Reg.isVirtual())
+          continue;
+
+        if (!DeleteDefs.insert(RegPair).second)
+          continue;
+
+        if (MRI.use_empty(RegPair.Reg)) {
+          if (I >= NumRequiredOps) {
+            // Delete implicit def operands that aren't part of the instruction
+            // definition
+            MI.removeOperand(I);
+          }
+
+          continue;
+        }
+
+        // If we aren't going to delete the instruction, replace it with a dead
+        // def.
+        if (HaveKeptDef)
+          MO.setReg(MRI.cloneVirtualRegister(MO.getReg()));
+
+        bool IsGeneric = MRI.getRegClassOrNull(RegPair.Reg) == nullptr;
+        unsigned ImpDef = IsGeneric ? TargetOpcode::G_IMPLICIT_DEF
+                                    : TargetOpcode::IMPLICIT_DEF;
+
+        unsigned OpFlags = getRegState(MO) & ~RegState::Implicit;
+        InsPt = BuildMI(MBB, InsPt, DebugLoc(), TII->get(ImpDef))
+          .addReg(RegPair.Reg, OpFlags, RegPair.SubReg);
+      }
+
+      if (!HaveKeptDef)
+        MI.eraseFromParent();
+    }
+  }
+}
+
+static void removeDefsFromModule(Oracle &O, ReducerWorkItem &WorkItem) {
+  for (const Function &F : WorkItem.getModule()) {
+    if (auto *MF = WorkItem.MMI->getMachineFunction(F))
+      removeDefsFromFunction(O, *MF);
+  }
+}
+
+void llvm::reduceRegisterDefsMIRDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing register defs...\n";
+  runDeltaPass(Test, removeDefsFromModule);
+}