llvm-reduce: Fix not removing first instruction in MachineBasicBlock

[arsenm]

Summary

This had the surprising behavior of using whatever instruction
happened to be first in the block as an anchor point to stick random
implicit defs on. Use a real implicit_def instead.

[arsenm]

Fix test for generic registers

[markus]

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

111

When I originally decided to just slap a implicit-def to the first MI in the entry block instead of building a new instruction I thought it would be unsafe for the delta debugging algorithm to add instructions here. I did not dig deep into that though so maybe it is of no concern.

[arsenm]

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

111

It’s not unsafe, but gives suboptimal results. D124049 tries to address this problem

[arsenm]

aabea3b2ea84a0a93c276d0abfa4219986721f38

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

 # REQUIRES: amdgpu-registered-target
 # RUN: llvm-reduce -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: G_ADD
 # CHECK-INTERESTINGNESS: G_IMPLICIT_DEF
 # CHECK-INTERESTINGNESS: G_STORE
 
-# RESULT: %v0:vgpr(s32) = COPY $vgpr0, implicit-def %9(<2 x s16>), implicit-def %10(s64), implicit-def %11(s64), implicit-def %12(<2 x s32>)
-# RESULT-NEXT: %unused_load_ptr:sgpr(p1) = G_IMPLICIT_DEF
-# RESULT-NEXT: %aoeu:_(s64) = G_BITCAST %12(<2 x s32>)
+# 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: %aoeu:_(s64) = G_BITCAST %14(<2 x s32>)
 # RESULT-NEXT: %add:_(s64) = G_ADD %aoeu, %aoeu
 # RESULT-NEXT: %ptr:_(p1) = G_IMPLICIT_DEF
-# RESULT-NEXT: G_STORE %v0(s32), %ptr(p1) :: (store (s32), addrspace 1)
-# RESULT-NEXT: S_ENDPGM 0, implicit %add(s64), implicit %9(<2 x s16>), implicit %11(s64)
+# RESULT-NEXT: G_STORE %{{[0-9]+}}(s32), %ptr(p1) :: (store (s32), addrspace 1)
+# RESULT-NEXT: S_ENDPGM 0, implicit %add(s64), implicit %{{[0-9]+}}(<2 x s16>), implicit %{{[0-9]+}}(s64)
 
 ---
 name:            f
 tracksRegLiveness: true
 body:             |
   bb.0:
     liveins: $vgpr0, $vgpr1, $vgpr2_vgpr3
     %v0:vgpr(s32) = COPY $vgpr0

llvm/test/tools/llvm-reduce/mir/instr-reduce.mir

 # RUN: llvm-reduce -mtriple=riscv32 --test %python --test-arg %p/instr-reduce.py %s -o %t
 # RUN: cat %t | FileCheck --match-full-lines %s
 
 # REQUIRES: riscv-registered-target
 
 # Verify that after reduction the following instruction sequence remains. The
 # interestingness-test 'instr-reduce.py' matches a '%[0-9]+:gpr = ADDI %[0-9]+, 5'
 # pattern in the output and that combined with that the MIR has to be valid
 # (pass verify) results in the given sequence.
 
-# CHECK:      %0:gpr = COPY $x10
-# CHECK-NEXT: %2:gpr = ADDI %0, 5
+# CHECK:      [[IMPDEF:%[0-9]+]]:gpr = IMPLICIT_DEF
+# CHECK-NEXT: %{{[0-9]+}}:gpr = ADDI [[IMPDEF]], 5
 # CHECK-NEXT: PseudoRET implicit $x10
 
 ...
 ---
 name:            f
 tracksRegLiveness: true
 body:             |
   bb.0:

llvm/test/tools/llvm-reduce/mir/preserve-frame-info.mir

 # RESULT-NEXT:  - { id: 5, name: m1, size: 2052, alignment: 4, local-offset: 0 }
 # RESULT-NEXT:  - { id: 6, name: m2, size: 2060, alignment: 32, local-offset: 2080 }
 # RESULT-NEXT:  - { id: 7, offset: 48, size: 4, alignment: 4, callee-saved-register: '$sgpr40' }
 # RESULT-NEXT:  - { id: 8, offset: 52, size: 4, alignment: 4, callee-saved-register: '$sgpr41',
 # RESULT-NEXT:      callee-saved-restored: false }
 # RESULT-NEXT:  - { id: 9, name: guard, offset: 128, size: 4, alignment: 4 }
 
 
-# RESULT: S_NOP 0
+# RESULT: bb.0:
 # RESULT-NEXT: [[FI0:%[0-9]+]]:vgpr_32 = V_MOV_B32_e32 %stack.1, implicit $exec
 # RESULT-NEXT: [[FI1:%[0-9]+]]:vgpr_32 = V_MOV_B32_e32 %stack.0.bigalloca, implicit $exec
 # RESULT-NEXT: [[FI2:%[0-9]+]]:vgpr_32 = V_MOV_B32_e32 %stack.2, implicit $exec
 # RESULT-NEXT: [[FI3:%[0-9]+]]:vgpr_32 = V_MOV_B32_e32 %stack.3, implicit $exec
 # RESULT-NEXT: [[FI4:%[0-9]+]]:vgpr_32 = V_MOV_B32_e32 %stack.4.dynamic_alloca, implicit $exec
 # RESULT-NEXT: [[FI5:%[0-9]+]]:vgpr_32 = V_MOV_B32_e32 %stack.5.m1, implicit $exec
 # RESULT-NEXT: [[FI6:%[0-9]+]]:vgpr_32 = V_MOV_B32_e32 %stack.6.m2, implicit $exec
 # RESULT-NEXT: [[FI7:%[0-9]+]]:vgpr_32 = V_MOV_B32_e32 %stack.7, implicit $exec

llvm/test/tools/llvm-reduce/mir/subreg-def0.mir

 # REQUIRES: amdgpu-registered-target
 # RUN: llvm-reduce -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
 
 # CHECK-INTERESTINGNESS: V_ADD_U32
 
-# RESULT: S_WAITCNT 0, implicit-def undef %2.sub1, implicit-def %3.sub0
+# RESULT: undef %2.sub1:vreg_64 = IMPLICIT_DEF
+# RESULT-NEXT: %3.sub0:vreg_64 = IMPLICIT_DEF
 # RESULT-NEXT: %1:vgpr_32 = V_ADD_U32_e32 %2.sub0, %2.sub1, implicit $exec
 # RESULT-NEXT: S_ENDPGM 0, implicit %1
 
 ---
 name:            f
 tracksRegLiveness: true
 body:             |
   bb.0:
     S_WAITCNT 0
     undef %0.sub1:vreg_64 = V_MOV_B32_e32 0, implicit $exec
     %0.sub0:vreg_64 = V_MOV_B32_e32 1, implicit $exec
     %1:vgpr_32 = V_ADD_U32_e32 %0.sub0, %0.sub1, implicit $exec
     S_ENDPGM 0, implicit %1
 ...

llvm/test/tools/llvm-reduce/mir/subreg-def1.mir

 # REQUIRES: amdgpu-registered-target
 # RUN: llvm-reduce -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
 
 # CHECK-INTERESTINGNESS: %{{[0-9]+}}.sub0:vreg_64 = V_ADD_U32_e32 %{{[0-9]+}}.sub1, %{{[0-9]+}}.sub0, implicit $exec
 # CHECK-INTERESTINGNESS: %{{[0-9]+}}.sub0:vreg_64 = V_ADD_U32_e32 4, %{{[0-9]+}}.sub0, implicit $exec
 
-# RESULT: S_WAITCNT 0, implicit-def undef %2.sub1
-# RESULT-NEXT: %{{[0-9]+}}.sub0:vreg_64 = V_ADD_U32_e32 %{{[0-9]+}}.sub1, %{{[0-9]+}}.sub0, implicit $exec
-# RESULT-NEXT: %{{[0-9]+}}.sub0:vreg_64 = V_ADD_U32_e32 4, %{{[0-9]+}}.sub0, implicit $exec
-# RESULT-NEXT: S_ENDPGM 0, implicit %{{[0-9]+}}, implicit %{{[0-9]+}}.sub0
-
+# RESULT: undef %2.sub1:vreg_64 = IMPLICIT_DEF
+# RESULT-NEXT: %0.sub0:vreg_64 = V_ADD_U32_e32 %2.sub1, %2.sub0, implicit $exec
+# RESULT-NEXT: %1.sub0:vreg_64 = V_ADD_U32_e32 4, %2.sub0, implicit $exec
+# RESULT-NEXT: S_ENDPGM 0, implicit %2, implicit %2.sub0
 ---
 name:            f
 tracksRegLiveness: true
 body:             |
   bb.0:
     S_WAITCNT 0
     undef %0.sub1:vreg_64 = V_MOV_B32_e32 0, implicit $exec
     %1.sub1:vreg_64 = V_ADD_U32_e32 2, %0.sub1, implicit $exec
     %0.sub0:vreg_64 = V_ADD_U32_e32 %1.sub1, %0.sub0, implicit $exec
     %1.sub0:vreg_64 = V_ADD_U32_e32 4, %0.sub0, implicit $exec
     S_ENDPGM 0, implicit %1, implicit %0.sub0
 ...

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

 
 static void extractInstrFromFunction(Oracle &O, MachineFunction &MF) {
   MachineDominatorTree MDT;
   MDT.runOnMachineFunction(MF);
 
   auto MRI = &MF.getRegInfo();
   SetVector<MachineInstr *> ToDelete;
 
-  MachineInstr *TopMI = nullptr;
+  const TargetSubtargetInfo &STI = MF.getSubtarget();
+  const TargetInstrInfo *TII = STI.getInstrInfo();
+  MachineBasicBlock *EntryMBB = &*MF.begin();
+  MachineBasicBlock::iterator EntryInsPt =
+      EntryMBB->SkipPHIsLabelsAndDebug(EntryMBB->begin());
 
   // Mark MIs for deletion according to some criteria.
   for (auto &MBB : MF) {
     for (auto &MI : MBB) {
       if (MI.isTerminator())
         continue;
-      if (MBB.isEntryBlock() && !TopMI) {
-        TopMI = &MI;
-        continue;
-      }
       if (!O.shouldKeep())
         ToDelete.insert(&MI);
     }
   }
 
   // For each MI to be deleted update users of regs defined by that MI to use
   // some other dominating definition (that is not to be deleted).
   for (auto *MI : ToDelete) {
for (auto &MO : MI->operands()) {
             BB = IDM->getBlock();
             RI = BB->rbegin();
           } else {
             BB = nullptr;
           }
         }
       }
 
-      // If no dominating definition was found then add an implicit one to the
-      // first instruction in the entry block.
-
-      // FIXME: This should really insert IMPLICIT_DEF or G_IMPLICIT_DEF. We
-      // need to refine the reduction quality metric from number of serialized
-      // bytes to continue progressing if we're going to introduce new
-      // instructions.
-      if (!NewReg && TopMI) {
+      // If no dominating definition was found then add an implicit def to the
+      // top of the entry block.
+      if (!NewReg) {
         NewReg = MRI->cloneVirtualRegister(Reg);
-        TopMI->addOperand(MachineOperand::CreateReg(
-            NewReg, true /*IsDef*/, true /*IsImp*/, false /*IsKill*/,
-            MO.isDead(), MO.isUndef(), MO.isEarlyClobber(), MO.getSubReg(),
-            /*IsDebug*/ false, MO.isInternalRead()));
+        bool IsGeneric = MRI->getRegClassOrNull(Reg) == nullptr;
+        unsigned ImpDef = IsGeneric ? TargetOpcode::G_IMPLICIT_DEF
+                                    : TargetOpcode::IMPLICIT_DEF;
+        BuildMI(*EntryMBB, EntryInsPt, DebugLoc(), TII->get(ImpDef))
+          .addReg(NewReg, getRegState(MO), MO.getSubReg());
       }
 
       // Update all uses.
       while (UI != UE) {
         auto &UMO = *UI++;
         UMO.setReg(NewReg);
       }
     }