CodeGen: Make computeRegisterLiveness consider successors

[arsenm]

Summary

If the end of the block is reached during the scan, check
the live ins of the successors. This was already done in the
other direction if the block entry was reached.

[MatzeB]

LGTM

[arsenm]

r341026

[uabelho]

I have a post-review question about this change.

lib/CodeGen/MachineBasicBlock.cpp

1446

In the already existing loop in this function when we check live-ins, we use MCRegAliasIterator rather than MCSubRegIterator. Why not do the same here?

We are using computeRegisterLiveness in my out-of-tree target, and after D51350 we've found a case that goes wrong since this MCSubRegIterator loop decides that the register is dead, while the other loop thought that is was live (which it is).

In the case it fails we're interested in register $a0_32 (which consists of $a0h, $a0h and $a0l) and then we find that $a10h (which consists of $a0h and $a1h) is livein, but this new loop then determines that $a0_32 is dead.

So with MCSubRegIterator I think it might draw the wrong conclusions in cases where Reg and liveins are overlapping but neither is subregister of the other.

[arsenm]

lib/CodeGen/MachineBasicBlock.cpp

1446

I'm not really sure what the difference is between these. MCRegAliasIterator visits sub and super registers vs. just subregisters?

[MatzeB]

lib/CodeGen/MachineBasicBlock.cpp

1446

MCRegAliasIterator iterates through subregs, superregs and aliased registers. (Aliased registers are used pretty much nowhere in LLVM... I think last time I looked I only found a single target unnecessarily using them which made me wonder whether we couldn't just drop the whole concept. Anyway today aliased registers are a thing).

How about changing this loop to:

for (const MachineBasicBlock::RegisterMaskPair &LI : Succ->liveins()) {
  if (TRI->regsOverlap(LI.PhysReg, Reg)
    return LQR_Live;
}

[uabelho]

lib/CodeGen/MachineBasicBlock.cpp

1446

Yep using overlap seems to work too since it catches my cases like $a0_32 vs $a10h that the original loop misses.

(Btw if I grep for MCRegAliasIterator in lib/Target I get 24 hits so it doesn't seem to be totally unused. I've no idea if those 24 uses are pointless and could easily be switched into something else though.)

[uabelho]

lib/CodeGen/MachineBasicBlock.cpp

1446

Ok, so what do we do with this? Should I create a patch where we use overlap in both loops? Like:

@ -1402,13 +1402,12 @@ MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI,
 
   // If we reached the end, it is safe to clobber Reg at the end of a block of
   // no successor has it live in.
   if (I == end()) {
     for (MachineBasicBlock *S : successors()) {
-      for (MCSubRegIterator SubReg(Reg, TRI, /*IncludeSelf*/true);
-           SubReg.isValid(); ++SubReg) {
-        if (S->isLiveIn(*SubReg))
+      for (const MachineBasicBlock::RegisterMaskPair &LI : S->liveins()) {
+        if (TRI->regsOverlap(LI.PhysReg, Reg))
           return LQR_Live;
       }
     }
 
     return LQR_Dead;
@@ -1458,13 +1457,12 @@ MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI,
   }
 
   // Did we get to the start of the block?
   if (I == begin()) {
     // If so, the register's state is definitely defined by the live-in state.
-    for (MCRegAliasIterator RAI(Reg, TRI, /*IncludeSelf=*/true); RAI.isValid();
-         ++RAI)
-      if (isLiveIn(*RAI))
+    for (const MachineBasicBlock::RegisterMaskPair &LI : liveins())
+      if (TRI->regsOverlap(LI.PhysReg, Reg))
         return LQR_Live;
 
     return LQR_Dead;
   }

?

[arsenm]

lib/CodeGen/MachineBasicBlock.cpp

1446

This looks right to me. I think it might be possible to construct an AMDGPU testcase where VCC_LO or VCC_HI is defined and VCC is the live out

[uabelho]

lib/CodeGen/MachineBasicBlock.cpp

1446

I created https://reviews.llvm.org/D52410 where I use regsOverlap instead of the MCSubRegIterator/MCRegAliasIterator loops. Let's continue there.

lib/CodeGen/MachineBasicBlock.cpp

for (++I; I != end() && N > 0; ++I, --N) {
       if (Info.Read)
         return LQR_Live;
       // Register is dead if we can fully overwrite or clobber it here.
       if (Info.FullyDefined || Info.Clobbered)
         return LQR_Dead;
     }
   }
 
+  // If we reached the end, it is safe to clobber Reg at the end of a block of
+  // no successor has it live in.
+  if (I == end()) {
+    for (MachineBasicBlock *S : successors()) {
+      for (MCSubRegIterator SubReg(Reg, TRI, /*IncludeSelf*/true);
+           SubReg.isValid(); ++SubReg) {
+        if (S->isLiveIn(*SubReg))
+          return LQR_Live;
+      }
+    }
+
+    return LQR_Dead;
+  }
+
   // At this point we have no idea of the liveness of the register.
   return LQR_Unknown;
 }
 
 const uint32_t *
 MachineBasicBlock::getBeginClobberMask(const TargetRegisterInfo *TRI) const {
   // EH funclet entry does not preserve any registers.
   return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr;

test/CodeGen/AMDGPU/fold-immediate-operand-shrink.mir

bb.0:
     %1:sreg_32_xm0 = S_MOV_B32 12345
     %2:vgpr_32, %3:sreg_64 = V_SUBREV_I32_e64 %0, %1, implicit $exec
     S_ENDPGM implicit %2
 
 ...
 
 ---
 
+# We know this is OK because vcc isn't live out of the block.
+
+name: shrink_scalar_imm_vgpr_v_add_i32_e64_known_no_liveout
+tracksRegLiveness: true
+
+body:             |
+  ; GCN-LABEL: name: shrink_scalar_imm_vgpr_v_add_i32_e64_known_no_liveout
+  ; GCN: bb.0:
+  ; GCN:   successors: %bb.1(0x80000000)
+  ; GCN:   [[S_MOV_B32_:%[0-9]+]]:sreg_32_xm0 = S_MOV_B32 12345
+  ; GCN:   [[DEF:%[0-9]+]]:vgpr_32 = IMPLICIT_DEF
+  ; GCN:   [[V_ADD_I32_e32_:%[0-9]+]]:vgpr_32 = V_ADD_I32_e32 [[S_MOV_B32_]], [[DEF]], implicit-def $vcc, implicit $exec
+  ; GCN: bb.1:
+  ; GCN:   S_ENDPGM implicit [[V_ADD_I32_e32_]]
+  bb.0:
+    successors: %bb.1
+
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    %0:sreg_32_xm0 = S_MOV_B32 12345
+    %1:vgpr_32 = IMPLICIT_DEF
+    %2:vgpr_32, %3:sreg_64 = V_ADD_I32_e64 %0, %1, implicit $exec
+    S_NOP 0
+    S_NOP 0
+
+  bb.1:
+    S_ENDPGM implicit %2
+
+...
+
+---
+
 # We know this is OK because vcc isn't live out of the block, even
-# though it had a defined value
+# though it had a defined but unused. value
 
-name: shrink_scalar_imm_vgpr_v_add_i32_e64_known_dead_no_liveout
+name: shrink_scalar_imm_vgpr_v_add_i32_e64_known_no_liveout_dead_vcc_def
 tracksRegLiveness: true
 
 body:             |
-  ; GCN-LABEL: name: shrink_scalar_imm_vgpr_v_add_i32_e64_known_dead_no_liveout
+  ; GCN-LABEL: name: shrink_scalar_imm_vgpr_v_add_i32_e64_known_no_liveout_dead_vcc_def
   ; GCN: bb.0:
   ; GCN:   successors: %bb.1(0x80000000)
   ; GCN:   [[S_MOV_B32_:%[0-9]+]]:sreg_32_xm0 = S_MOV_B32 12345
   ; GCN:   [[DEF:%[0-9]+]]:vgpr_32 = IMPLICIT_DEF
   ; GCN:   [[V_ADD_I32_e64_:%[0-9]+]]:vgpr_32, [[V_ADD_I32_e64_1:%[0-9]+]]:sreg_64 = V_ADD_I32_e64 [[S_MOV_B32_]], [[DEF]], implicit $exec
   ; GCN: bb.1:
   ; GCN:   S_ENDPGM implicit [[V_ADD_I32_e64_]]
   bb.0:
     successors: %bb.1
 
-    $vcc = S_MOV_B64 -1
+    S_NOP 0, implicit-def $vcc
     %0:sreg_32_xm0 = S_MOV_B32 12345
     %1:vgpr_32 = IMPLICIT_DEF
     %2:vgpr_32, %3:sreg_64 = V_ADD_I32_e64 %0, %1, implicit $exec
+    S_NOP 0
+    S_NOP 0
 
   bb.1:
     S_ENDPGM implicit %2
 
 ...

test/CodeGen/AMDGPU/split-scalar-i64-add.ll

 ; RUN: llc -march=amdgcn -verify-machineinstrs < %s | FileCheck -check-prefix=SI -check-prefix=FUNC %s
 
 declare i32 @llvm.amdgcn.workitem.id.x() readnone
 
 ; This is broken because the low half of the 64-bit add remains on the
 ; SALU, but the upper half does not. The addc expects the carry bit
 ; set in vcc, which is undefined since the low scalar half add sets
 ; scc instead.
 
 ; FIXME: SIShrinkInstructions should force immediate fold.
 
 ; FUNC-LABEL: {{^}}imp_def_vcc_split_i64_add_0:
-; SI: s_movk_i32 [[K:s[0-9]+]], 0x18f
-; SI: v_add_i32_e32 v{{[0-9]+}}, vcc, [[K]], v{{[0-9]+}}
+; SI: v_mov_b32_e32 [[V_VAL:v[0-9]+]], s
+; SI: v_add_i32_e32 v{{[0-9]+}}, vcc, 0x18f, [[V_VAL]]
 ; SI: v_addc_u32_e32 v{{[0-9]+}}, vcc, 0, v{{[0-9]+}}, vcc
 define amdgpu_kernel void @imp_def_vcc_split_i64_add_0(i64 addrspace(1)* %out, i32 addrspace(1)* %in, i32 %s.val) {
   %v.val = load volatile i32, i32 addrspace(1)* %in
   %vec.0 = insertelement <2 x i32> undef, i32 %s.val, i32 0
   %vec.1 = insertelement <2 x i32> %vec.0, i32 %v.val, i32 1
   %bc = bitcast <2 x i32> %vec.1 to i64
   %add = add i64 %bc, 399
   store i64 %add, i64 addrspace(1)* %out, align 8