RegAllocFast: Set MayLiveAcrossBlocks when allocating uses

[arsenm]

Summary

Setting mayLiveOut based only on use instructions after allocating the
def block did not work if the use block was allocated before the def
block, since the virtual register uses were already removed.

Fixes bug 41973.

[brooksmoses]

Thanks for the quick fix for bug 41973!

lib/CodeGen/RegAllocFast.cpp

295

Are you expecting future uses of this to want to use the return value? Looks like it's currently unused, and removing it would simplify some things.

[arsenm]

lib/CodeGen/RegAllocFast.cpp

295

Possibly? The set of rewrite patches inverts the spill logic to restore on use, so these may swap but I haven't tried to rebase it yet

[arsenm]

ping

[qcolombet]

lib/CodeGen/RegAllocFast.cpp

297

We should return !MBB->pred_empty()

305

Ditto

310

Refactoring suggestion:
Use the same base code for both live-in and live-out the difference being:

1. The returned value for early exits (pred_empty vs such_empty)
2. The list we iterate on (defs vs uses)

[qcolombet]

test/CodeGen/X86/bug41973.ll

2 ↗

(On Diff #200706)

BTW we should probably go with a .mir test if at all possible to be sure the layout of the use and basic blocks remains the same in the future. I.e., that this test keeps testing what it was aimed for.

[arsenm]

lib/CodeGen/RegAllocFast.cpp

297

Does it matter for an unreachable block?

[qcolombet]

lib/CodeGen/RegAllocFast.cpp

297

It could be the entry block, couldn't it?

[arsenm]

Check pred_empty, use mir test

lib/CodeGen/RegAllocFast.cpp

297

This doesn't really matter because the entry block is always visited first

310

I tried this, but largely due to the return inside the block, it gets pretty ugly

[qcolombet]

LGTM.
Nitpicks on the test below.

lib/CodeGen/RegAllocFast.cpp

310

Thanks for trying.

test/CodeGen/X86/bug41973.mir

2

Could you give a more descriptive name (regalloc-fast-missing-live-out-spill) to the file and list the PR number in the test?
Also add a description of what are the characteristic of the test (use appears before def in different blocks).

[arsenm]

r361781

lib/CodeGen/RegAllocFast.cpp

private:
 
     int getStackSpaceFor(unsigned VirtReg);
     void spill(MachineBasicBlock::iterator Before, unsigned VirtReg,
                MCPhysReg AssignedReg, bool Kill);
     void reload(MachineBasicBlock::iterator Before, unsigned VirtReg,
                 MCPhysReg PhysReg);
 
     bool mayLiveOut(unsigned VirtReg);
+    bool mayLiveIn(unsigned VirtReg);
 
     void dumpState();
   };
 
 } // end anonymous namespace
 
 char RegAllocFast::ID = 0;
 

 bool RegAllocFast::mayLiveOut(unsigned VirtReg) {
   if (MayLiveAcrossBlocks.test(TargetRegisterInfo::virtReg2Index(VirtReg))) {
     // Cannot be live-out if there are no successors.
     return !MBB->succ_empty();
   }
 
   // If this block loops back to itself, it would be necessary to check whether
   // the use comes after the def.
-  if (MBB->isSuccessor(MBB))
+  if (MBB->isSuccessor(MBB)) {
+    MayLiveAcrossBlocks.set(TargetRegisterInfo::virtReg2Index(VirtReg));
     return true;
+  }
 
   // See if the first \p Limit uses of the register are all in the current
   // block.
   static const unsigned Limit = 8;
   unsigned C = 0;
   for (const MachineInstr &UseInst : MRI->reg_nodbg_instructions(VirtReg)) {
     if (UseInst.getParent() != MBB || ++C >= Limit) {
       MayLiveAcrossBlocks.set(TargetRegisterInfo::virtReg2Index(VirtReg));
       // Cannot be live-out if there are no successors.
       return !MBB->succ_empty();
     }
   }
 
   return false;
 }
 
+/// Returns false if \p VirtReg is known to not be live into the current block.
+bool RegAllocFast::mayLiveIn(unsigned VirtReg) {
+  if (MayLiveAcrossBlocks.test(TargetRegisterInfo::virtReg2Index(VirtReg)))
+    return !MBB->pred_empty();
+
+  // See if the first \p Limit def of the register are all in the current block.
+  static const unsigned Limit = 8;
+  unsigned C = 0;
+  for (const MachineInstr &DefInst : MRI->def_instructions(VirtReg)) {
+    if (DefInst.getParent() != MBB || ++C >= Limit) {
+      MayLiveAcrossBlocks.set(TargetRegisterInfo::virtReg2Index(VirtReg));
+      return !MBB->pred_empty();
+    }
+  }
+
+  return false;
+}
+
 /// Insert spill instruction for \p AssignedReg before \p Before. Update
 /// DBG_VALUEs with \p VirtReg operands with the stack slot.
 void RegAllocFast::spill(MachineBasicBlock::iterator Before, unsigned VirtReg,
                          MCPhysReg AssignedReg, bool Kill) {
   LLVM_DEBUG(dbgs() << "Spilling " << printReg(VirtReg, TRI)
                     << " in " << printReg(AssignedReg, TRI));
   int FI = getStackSpaceFor(VirtReg);
   LLVM_DEBUG(dbgs() << " to stack slot #" << FI << '\n');
for (unsigned I = 0; I != VirtOpEnd; ++I) {
     unsigned Reg = MO.getReg();
     if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue;
     if (MO.isUse()) {
       if (MO.isUndef()) {
         HasUndefUse = true;
         // There is no need to allocate a register for an undef use.
         continue;
       }
+
+      // Populate MayLiveAcrossBlocks in case the use block is allocated before
+      // the def block (removing the vreg uses).
+      mayLiveIn(Reg);
+
       LiveReg &LR = reloadVirtReg(MI, I, Reg, CopyDstReg);
       MCPhysReg PhysReg = LR.PhysReg;
       CopySrcReg = (CopySrcReg == Reg || CopySrcReg == PhysReg) ? PhysReg : 0;
       if (setPhysReg(MI, MO, PhysReg))
         killVirtReg(LR);
     }
   }
 

test/CodeGen/X86/bug41973.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple=x86_64-grtev4-linux-gnu -run-pass=regallocfast -o - %s | FileCheck %s
+
+---
+name:            main
+tracksRegLiveness: true
+body:             |
+  ; CHECK-LABEL: name: main
+  ; CHECK: bb.0:
+  ; CHECK:   successors: %bb.3(0x80000000)
+  ; CHECK:   liveins: $edi, $rsi
+  ; CHECK:   MOV64mr %stack.0, 1, $noreg, 0, $noreg, killed $rsi :: (store 8 into %stack.0)
+  ; CHECK:   JMP_1 %bb.3
+  ; CHECK: bb.1:
+  ; CHECK:   successors:
+  ; CHECK: bb.2:
+  ; CHECK:   successors: %bb.3(0x80000000)
+  ; CHECK:   $rax = MOV64rm %stack.1, 1, $noreg, 0, $noreg :: (load 8 from %stack.1)
+  ; CHECK:   renamable $ecx = MOV32r0 implicit-def $eflags
+  ; CHECK:   renamable $rdx = SUBREG_TO_REG 0, killed renamable $ecx, %subreg.sub_32bit
+  ; CHECK:   MOV64mi32 killed renamable $rax, 1, $noreg, 0, $noreg, 0 :: (volatile store 8)
+  ; CHECK:   MOV64mr %stack.0, 1, $noreg, 0, $noreg, killed $rdx :: (store 8 into %stack.0)
+  ; CHECK: bb.3:
+  ; CHECK:   successors: %bb.2(0x40000000), %bb.1(0x40000000)
+  ; CHECK:   $rax = MOV64rm %stack.0, 1, $noreg, 0, $noreg :: (load 8 from %stack.0)
+  ; CHECK:   renamable $ecx = MOV32r0 implicit-def dead $eflags
+  ; CHECK:   renamable $rdx = SUBREG_TO_REG 0, killed renamable $ecx, %subreg.sub_32bit
+  ; CHECK:   MOV64mr %stack.1, 1, $noreg, 0, $noreg, killed $rdx :: (store 8 into %stack.1)
+  ; CHECK:   JMP64r killed renamable $rax
+  bb.0:
+    liveins: $edi, $rsi
+
+    %4:gr64 = COPY $rsi
+    %2:gr32 = COPY $edi
+    %3:gr32 = COPY killed %2
+    %5:gr64 = COPY killed %4
+    %13:gr64 = COPY %5
+    JMP_1 %bb.3
+
+  bb.1:
+    successors:
+
+
+  bb.2:
+    %0:gr64 = COPY %12
+    %10:gr32 = MOV32r0 implicit-def $eflags
+    %11:gr64 = SUBREG_TO_REG 0, %10, %subreg.sub_32bit
+    MOV64mi32 %0, 1, $noreg, 0, $noreg, 0 :: (volatile store 8)
+    %13:gr64 = COPY %11
+
+  bb.3:
+    successors: %bb.2, %bb.1
+
+    %1:gr64 = COPY %13
+    %9:gr32 = MOV32r0 implicit-def dead $eflags
+    %8:gr64 = SUBREG_TO_REG 0, killed %9, %subreg.sub_32bit
+    %12:gr64 = COPY %8
+    JMP64r %1
+
+...