CodeGen: Make computeRegisterLiveness search forward first

[arsenm]

Summary

If there is an unused def, this would previously
report that the register was live. Check for uses
first so that it is reported as dead if never used.

[MatzeB]

This change LGTM and should be committed.

Though reading the code I think there is a pre-existing bug hiding: The live-outs for return blocks is not the union of the successor live-ins but the callee saved registers (see for example the code in LivePhysRegs/LiveRegUnits dealing with this)...

[arsenm]

r341027

lib/CodeGen/MachineBasicBlock.cpp

 /// Neighborhood instructions before (searching for defs or kills) and N
 /// instructions after (searching just for defs) MI.
 MachineBasicBlock::LivenessQueryResult
 MachineBasicBlock::computeRegisterLiveness(const TargetRegisterInfo *TRI,
                                            unsigned Reg, const_iterator Before,
                                            unsigned Neighborhood) const {
   unsigned N = Neighborhood;
 
-  // Start by searching backwards from Before, looking for kills, reads or defs.
+  // Try searching forwards from Before, looking for reads or defs.
   const_iterator I(Before);
+  // If this is the last insn in the block, don't search forwards.
+  if (I != end()) {
+    for (++I; I != end() && N > 0; ++I, --N) {
+      MachineOperandIteratorBase::PhysRegInfo Info =
+          ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
+
+      // Register is live when we read it here.
+      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;
+  }
+
+
+  N = Neighborhood;
+
+  // Start by searching backwards from Before, looking for kills, reads or defs.
+  I = const_iterator(Before);
   // If this is the first insn in the block, don't search backwards.
   if (I != begin()) {
     do {
       --I;
 
       MachineOperandIteratorBase::PhysRegInfo Info =
           ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
 
if (I == begin()) {
     for (MCRegAliasIterator RAI(Reg, TRI, /*IncludeSelf=*/true); RAI.isValid();
          ++RAI)
       if (isLiveIn(*RAI))
         return LQR_Live;
 
     return LQR_Dead;
   }
 
-  N = Neighborhood;
-
-  // Try searching forwards from Before, looking for reads or defs.
-  I = const_iterator(Before);
-  // If this is the last insn in the block, don't search forwards.
-  if (I != end()) {
-    for (++I; I != end() && N > 0; ++I, --N) {
-      MachineOperandIteratorBase::PhysRegInfo Info =
-          ConstMIOperands(*I).analyzePhysReg(Reg, TRI);
-
-      // Register is live when we read it here.
-      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.

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

 tracksRegLiveness: true
 
 body:             |
   ; 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:   [[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_e64_]]
+  ; GCN:   S_ENDPGM implicit [[V_ADD_I32_e32_]]
   bb.0:
     successors: %bb.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/Thumb/frame-access.ll

 ; Setup frame pointer
 ; CHECK:       add r7, sp, #8
 ; Align stack
 ; CHECK:       mov  r4, sp
 ; CHECK-NEXT:  lsrs r4, r4, #4
 ; CHECK-NEXT:  lsls r4, r4, #4
 ; CHECK-NEXT:  mov  sp, r4
 ; Incoming register varargs stored via FP
-; CHECK:       str r3, [r7, #16]
-; CHECK-NEXT:  str r2, [r7, #12]
-; CHECK-NEXT:  str r1, [r7, #8]
-
+; CHECK: mov  r0, r7
+; CHECK-NEXT: adds r0, #8
+; CHECK-NEXT: stm r0!, {r1, r2, r3}
 ; VLAs present, access via FP
 ; int test_args_vla(int a, int b, int c, int d, int e) {
 ;   int v[a];
 ;   return g(v, a, b, c, d, e);
 ; }
 define dso_local i32 @test_args_vla(i32 %a, i32 %b, i32 %c, i32 %d, i32 %e) local_unnamed_addr  {
 entry:
   %vla = alloca i32, i32 %a, align 4