AMDGPU: Fix LiveVariables verifier error for values defined before SI_END_CF

[arsenm]

Summary

GlobalISel happens to insert some constant materializes before SI_END_CF
in one test. These need to be excluded from AliveBlocks since they
are defined in the original block and used in the split block,
so they aren't fully alive through either block.

The case where the value defined in the first block which was originally used
in a later block is still broken.

Avoids a verifier error in a future patch.

[Pierre-vh]

Patch LGTM, I just have a few questions to try and understand it better

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

519

What does live through mean in this context?

llvm/test/CodeGen/AMDGPU/lower-control-flow-live-variables-update.xfail.mir

3

Is this a test case that will be fixed in a future patch?

[arsenm]

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

519

Defined in a predecessor and used in a successor

llvm/test/CodeGen/AMDGPU/lower-control-flow-live-variables-update.xfail.mir

3

Ideally yes but this turned out to be more work than I expected and I wanted to unblock the other patch

[ruiling]

llvm/test/CodeGen/AMDGPU/lower-control-flow-live-variables-update.mir

248

Can we teach the previous pass to insert the instruction after prologue instruction? like through SkipPHIsAndLabels().

[arsenm]

llvm/test/CodeGen/AMDGPU/lower-control-flow-live-variables-update.mir

248

I think the prolog logic gets too complicated and we would need to scan through the entire block. Terminator placement is universally understood

[ruiling]

llvm/test/CodeGen/AMDGPU/lower-control-flow-live-variables-update.mir

248

I don't see why we need to scan through the entire block?

[arsenm]

llvm/test/CodeGen/AMDGPU/lower-control-flow-live-variables-update.mir

248

We currently treat the prolog as instructions that modify exec. The problem here is spills get inserted which don’t modify exec. In case a prolog appears anywhere, we would need to scan the whole block. The prolog concept is really frail as it is. We’d be better off removing it given that we sometimes need to insert more instructions in the prolog

[ruiling]

llvm/test/CodeGen/AMDGPU/lower-control-flow-live-variables-update.mir

248

If an instruction modifies EXEC does not immediately follow PHI or other prolog instruction, I think it is not prolog anymore. So I think we should never look for prolog by scanning the whole block. I agree the prolog concept is fragile. But I don't have a good idea to replace it now. I like the other change to always split the block and let the s_or_exec be the terminator. With that change, do we still have a case to insert vector instructions before the s_or_exec afterward?

For this case, I would like we teach the constant materializer respect the basic block prolog unless we decided deprecating the prolog idea. Otherwise, such pattern can be easily broken by machine optimization passes (like sinking a vector operation before SI_END_CF).

[arsenm]

llvm/test/CodeGen/AMDGPU/lower-control-flow-live-variables-update.mir

248

SI_END_CF is a hack to force placement of the instruction after phi lowering. It's fine if instruction end up inserted before it. In a better world where we have block arguments instead of phis, we wouldn't need to have this

[ruiling]

llvm/test/CodeGen/AMDGPU/lower-control-flow-live-variables-update.mir

248

IMHO, a vector instruction inserted before SI_END_CF is not ok. In a typical if/endif case, vector instructions in endif block should be executed with restored EXEC mask, which was done by SI_END_CF. I am not quite sure whether that would happen because vector instructions usually have dependency on EXEC, moving vector instruction across block should not be easy. Maybe I miss something, but I think it would be safer to keep SI_END_CF being prolog instruction.

[arsenm]

llvm/test/CodeGen/AMDGPU/lower-control-flow-live-variables-update.mir

248

SI_END_CF was never a prolog instruction since it doesn’t have the exec def on it. It only exists because of the requirement for phis to be the first instructions in the block. It’s always eliminated before regalloc where the prolog matters

[ruiling]

llvm/test/CodeGen/AMDGPU/lower-control-flow-live-variables-update.mir

248

Look at the example SI_END_CF killed %4, implicit-def $exec, implicit-def dead $scc, implicit $exec. There is a implicit-def $exec in SI_END_CF, and The MI.modifiesRegister(AMDGPU::EXEC, &RI) at (https://github.com/llvm-mirror/llvm/blob/master/lib/Target/AMDGPU/SIInstrInfo.cpp#L6187) will return true for SI_END_CF.
Block prolog also matters at machine optimization stage, like @critson did in D119399.

[arsenm]

2a9f1dad2cceb70be372310e46eaf93f32782a43

llvm/test/CodeGen/AMDGPU/lower-control-flow-live-variables-update.mir

248

OK, it is. I missed the implicit exec def. However that doesn't change anything. Without fundamentally changing the IR to avoid using phi instructions, this is always going to be an ugly hack with a true insert position with vector instructions before it.

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

MachineBasicBlock *SILowerControlFlow::emitEndCf(MachineInstr &MI) {
   MachineInstr *NewMI =
     BuildMI(MBB, InsPt, DL, TII->get(Opcode), Exec)
     .addReg(Exec)
     .add(MI.getOperand(0));
   if (LV) {
     LV->replaceKillInstruction(DataReg, MI, *NewMI);
 
     if (SplitBB != &MBB) {
-      // Track the set of registers defined in the split block so we don't
-      // accidentally add the original block to AliveBlocks.
-      DenseSet<Register> SplitDefs;
-      for (MachineInstr &X : *SplitBB) {
+      // Track the set of registers defined in the original block so we don't
+      // accidentally add the original block to AliveBlocks. AliveBlocks only
+      // includes blocks which are live through, which excludes live outs and
+      // local defs.
+      DenseSet<Register> DefInOrigBlock;
+
+      for (MachineBasicBlock *BlockPiece : {&MBB, SplitBB}) {
+        for (MachineInstr &X : *BlockPiece) {
           for (MachineOperand &Op : X.operands()) {
             if (Op.isReg() && Op.isDef() && Op.getReg().isVirtual())
-            SplitDefs.insert(Op.getReg());
+              DefInOrigBlock.insert(Op.getReg());
+          }
         }
       }
 
       for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
         Register Reg = Register::index2VirtReg(i);
         LiveVariables::VarInfo &VI = LV->getVarInfo(Reg);
 
         if (VI.AliveBlocks.test(MBB.getNumber()))
           VI.AliveBlocks.set(SplitBB->getNumber());
         else {
           for (MachineInstr *Kill : VI.Kills) {
-            if (Kill->getParent() == SplitBB && !SplitDefs.contains(Reg))
+            if (Kill->getParent() == SplitBB && !DefInOrigBlock.contains(Reg))
               VI.AliveBlocks.set(MBB.getNumber());
           }
         }
       }
     }
   }
 
   LoweredEndCf.insert(NewMI);

llvm/test/CodeGen/AMDGPU/lower-control-flow-live-variables-update.mir

bb.3:
 
     %10:vgpr_32 = PHI %9, %bb.2, %7, %bb.3, %1, %bb.0
     GLOBAL_STORE_DWORD undef %11:vreg_64, %10, 0, 0, implicit $exec :: (volatile store (s32), addrspace 1)
     %7:vgpr_32 = COPY killed %10
     %5:sreg_64_xexec = SI_IF %2, %bb.1, implicit-def $exec, implicit-def dead $scc, implicit $exec
     S_BRANCH %bb.3
 
 ...
+
+# Check we don't get "Block should not be in AliveBlocks" for
+# registers defined before si_end_cf
+---
+name:            live_variables_update_block_split_split_killed_def_before_si_end_cf
+tracksRegLiveness: true
+body:             |
+  ; CHECK-LABEL: name: live_variables_update_block_split_split_killed_def_before_si_end_cf
+  ; CHECK: bb.0:
+  ; CHECK-NEXT:   successors: %bb.1(0x40000000), %bb.2(0x40000000)
+  ; CHECK-NEXT:   liveins: $vgpr0
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[COPY:%[0-9]+]]:vgpr_32 = COPY killed $vgpr0
+  ; CHECK-NEXT:   [[V_MOV_B32_e32_:%[0-9]+]]:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
+  ; CHECK-NEXT:   [[V_CMP_EQ_U32_e64_:%[0-9]+]]:sreg_64_xexec = V_CMP_EQ_U32_e64 0, killed [[COPY]], implicit $exec
+  ; CHECK-NEXT:   [[COPY1:%[0-9]+]]:vgpr_32 = COPY [[V_MOV_B32_e32_]]
+  ; CHECK-NEXT:   [[COPY2:%[0-9]+]]:vgpr_32 = COPY killed [[V_MOV_B32_e32_]]
+  ; CHECK-NEXT:   [[COPY3:%[0-9]+]]:sreg_64 = COPY $exec, implicit-def $exec
+  ; CHECK-NEXT:   [[S_AND_B64_:%[0-9]+]]:sreg_64 = S_AND_B64 [[COPY3]], [[V_CMP_EQ_U32_e64_]], implicit-def dead $scc
+  ; CHECK-NEXT:   [[S_XOR_B64_:%[0-9]+]]:sreg_64_xexec = S_XOR_B64 [[S_AND_B64_]], [[COPY3]], implicit-def dead $scc
+  ; CHECK-NEXT:   $exec = S_MOV_B64_term killed [[S_AND_B64_]]
+  ; CHECK-NEXT:   [[S_MOV_B64_term:%[0-9]+]]:sreg_64_xexec = S_MOV_B64_term killed [[S_XOR_B64_]], implicit $exec
+  ; CHECK-NEXT:   S_CBRANCH_EXECZ %bb.1, implicit $exec
+  ; CHECK-NEXT:   S_BRANCH %bb.2
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.1:
+  ; CHECK-NEXT:   successors: %bb.3(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[COPY4:%[0-9]+]]:sreg_64_xexec = COPY killed [[S_MOV_B64_term]]
+  ; CHECK-NEXT:   [[S_MOV_B64_:%[0-9]+]]:sreg_64 = S_MOV_B64 1
+  ; CHECK-NEXT:   $exec = S_OR_B64_term $exec, killed [[COPY4]], implicit-def $scc
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.3:
+  ; CHECK-NEXT:   successors: %bb.2(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   S_NOP 0, implicit killed [[S_MOV_B64_]]
+  ; CHECK-NEXT:   [[COPY5:%[0-9]+]]:vgpr_32 = COPY killed [[COPY1]]
+  ; CHECK-NEXT:   [[V_ADD_U32_e32_:%[0-9]+]]:vgpr_32 = nsw V_ADD_U32_e32 1, killed [[COPY5]], implicit $exec
+  ; CHECK-NEXT:   [[COPY6:%[0-9]+]]:vgpr_32 = COPY killed [[V_ADD_U32_e32_]]
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.2:
+  ; CHECK-NEXT:   successors: %bb.2(0x40000000), %bb.1(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[COPY66:%[0-9]+]]:vgpr_32 = COPY killed [[COPY6]]
+  ; CHECK-NEXT:   GLOBAL_STORE_DWORD undef %11:vreg_64, [[COPY66]], 0, 0, implicit $exec :: (volatile store (s32), addrspace 1)
+  ; CHECK-NEXT:   [[COPY7:%[0-9]+]]:vgpr_32 = COPY killed [[COPY66]]
+  ; CHECK-NEXT:   [[COPY8:%[0-9]+]]:vgpr_32 = COPY [[COPY7]]
+  ; CHECK-NEXT:   [[COPY8:%[0-9]+]]:vgpr_32 = COPY killed [[COPY7]]
+  ; CHECK-NEXT:   [[COPY8:%[0-9]+]]:sreg_64 = COPY $exec, implicit-def $exec
+  ; CHECK-NEXT:   [[S_AND_B64_1:%[0-9]+]]:sreg_64 = S_AND_B64 [[COPY8]], [[V_CMP_EQ_U32_e64_]], implicit-def dead $scc
+  ; CHECK-NEXT:   [[S_XOR_B64_1:%[0-9]+]]:sreg_64_xexec = S_XOR_B64 [[S_AND_B64_1]], [[COPY8]], implicit-def dead $scc
+  ; CHECK-NEXT:   $exec = S_MOV_B64_term killed [[S_AND_B64_1]]
+  ; CHECK-NEXT:   [[S_MOV_B64_term1:%[0-9]+]]:sreg_64_xexec = S_MOV_B64_term killed [[S_XOR_B64_1]], implicit $exec
+  ; CHECK-NEXT:   S_CBRANCH_EXECZ %bb.1, implicit $exec
+  ; CHECK-NEXT:   S_BRANCH %bb.2
+  bb.0:
+    liveins: $vgpr0
+
+    %0:vgpr_32 = COPY killed $vgpr0
+    %1:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
+    %2:sreg_64_xexec = V_CMP_EQ_U32_e64 0, killed %0, implicit $exec
+    %3:sreg_64_xexec = SI_IF %2, %bb.1, implicit-def $exec, implicit-def dead $scc, implicit $exec
+    S_BRANCH %bb.2
+
+  bb.1:
+    %4:sreg_64_xexec = PHI %5, %bb.2, %3, %bb.0
+    %6:vgpr_32 = PHI %7, %bb.2, %1, %bb.0
+    %8:sreg_64 = S_MOV_B64 1
+    SI_END_CF killed %4, implicit-def $exec, implicit-def dead $scc, implicit $exec
+    S_NOP 0, implicit killed %8
+    %9:vgpr_32 = nsw V_ADD_U32_e32 1, killed %6, implicit $exec
+
+  bb.2:
+    successors: %bb.2(0x40000000), %bb.1(0x40000000)
+
+    %10:vgpr_32 = PHI %9, %bb.1, %7, %bb.2, %1, %bb.0
+    GLOBAL_STORE_DWORD undef %11:vreg_64, %10, 0, 0, implicit $exec :: (volatile store (s32), addrspace 1)
+    %7:vgpr_32 = COPY killed %10
+    %5:sreg_64_xexec = SI_IF %2, %bb.1, implicit-def $exec, implicit-def dead $scc, implicit $exec
+    S_BRANCH %bb.2
+
+...

llvm/test/CodeGen/AMDGPU/lower-control-flow-live-variables-update.xfail.mir

+# RUN: not --crash llc -mtriple=amdgcn-amd-amdhsa -start-before=livevars -stop-after=twoaddressinstruction -verify-machineinstrs -o - %s 2>&1  | FileCheck %s
+
+# CHECK: *** Bad machine code: LiveVariables: Block missing from AliveBlocks ***
+# CHECK-NEXT: function:    live_variables_update_block_split_split_def_before_si_end_cf_live_out
+# CHECK-NEXT: basic block: %bb.4
+# CHECK-NEXT: Virtual register %8 must be live through the block.
+
+
+# Same as
+# live_variables_update_block_split_split_killed_def_before_si_end_cf,
+# except the def before si_end_cf is live out of the block
+---
+name:            live_variables_update_block_split_split_def_before_si_end_cf_live_out
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $vgpr0
+
+    %0:vgpr_32 = COPY killed $vgpr0
+    %1:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
+    %2:sreg_64_xexec = V_CMP_EQ_U32_e64 0, killed %0, implicit $exec
+    %3:sreg_64_xexec = SI_IF %2, %bb.1, implicit-def $exec, implicit-def dead $scc, implicit $exec
+    S_BRANCH %bb.3
+
+  bb.1:
+    %4:sreg_64_xexec = PHI %5, %bb.3, %3, %bb.0
+    %6:vgpr_32 = PHI %7, %bb.3, %1, %bb.0
+    %8:sreg_64 = S_MOV_B64 1
+    SI_END_CF killed %4, implicit-def $exec, implicit-def dead $scc, implicit $exec
+    %9:vgpr_32 = nsw V_ADD_U32_e32 1, killed %6, implicit $exec
+
+  bb.2:
+    S_NOP 0, implicit killed %8
+
+  bb.3:
+    %10:vgpr_32 = PHI %9, %bb.2, %7, %bb.3, %1, %bb.0
+    GLOBAL_STORE_DWORD undef %11:vreg_64, %10, 0, 0, implicit $exec :: (volatile store (s32), addrspace 1)
+    %7:vgpr_32 = COPY killed %10
+    %5:sreg_64_xexec = SI_IF %2, %bb.1, implicit-def $exec, implicit-def dead $scc, implicit $exec
+    S_BRANCH %bb.3
+
+...