[regalloc] Fix assertion error when LiveInterval is empty

[• pcwang-thead]

Summary

When evicting interference, it causes an asseertion error
since LiveIntervals::intervalIsInOneMBB assumes that input
is not empty.

This patch fixed bug mentioned in D118020.

[MatzeB]

This seems odd to me.

llvm/lib/CodeGen/RegAllocGreedy.cpp

497–500

If there are no live ranges in VirtReg then why didn't we bail out in the if 2 lines earlier? An empty liverange shouldn't interfere with anything. (I am also not sure how you end up with an empty life range in the first place, but I'd first investigate why the interference check did not end up returning IK_Free for you)

[craig.topper]

In D118124#3269622, @MatzeB wrote:

This seems odd to me.

I looked at this briefly. Here's the log leading up to one of the failures

# Machine code for function f: NoPHIs, TracksLiveness, TiedOpsRewritten, TracksDebugUserValues
Frame Objects:
  fi#0: size=8, align=8, at location [SP]

0B bb.0.entry:
16B  FSD undef %4:fpr64, %stack.0, 0 :: (store (s64) into %stack.0)         
32B  %2:gpr = LW %stack.0, 0 :: (load (s32) from %stack.0, align 8)         
48B  %3:gpr = LW %stack.0, 4 :: (load (s32) from %stack.0 + 4, basealign 8) 
64B  $x10 = COPY %2:gpr                                                     
80B  $x11 = COPY %3:gpr                                                     
96B  PseudoRET implicit killed $x10, implicit killed $x11                   

# End machine code for function f.

Enqueuing %2
AllocationOrder(GPR) = [ $x10 $x11 $x12 $x13 $x14 $x15 $x16 $x17 $x5 $x6 $x7 $x28 $x29 $x30 $x31 $x8 $x9 $x18 $x19 $x20 $x21 $x22 $x23 $x24 $x25 $x26 $x27 $x1 ]
Enqueuing %3
Enqueuing %4
AllocationOrder(FPR64) = [ $f0_d $f1_d $f2_d $f3_d $f4_d $f5_d $f6_d $f7_d $f10_d $f11_d $f12_d $f13_d $f14_d $f15_d $f16_d $f17_d $f28_d $f29_d $f30_d $f31_d $f8_d $f9_d $f18_d $f19_d $f20_d $f21_d $f22_d $f23_d $f24_d $f25_d $f26_d $f27_d ]

selectOrSplit GPR:%2 [32r,64r:0) 0@32r  weight:4.675926e-03 w=4.675926e-03       
AllocationOrder(GPR) = [ $x10 $x11 $x12 $x13 $x14 $x15 $x16 $x17 $x5 $x6 $x7 $x28 $x29 $x30 $x31 $x8 $x9 $x18 $x19 $x20 $x21 $x22 $x23 $x24 $x25 $x26 $x27 $x1 ]
hints: $x10
assigning %2 to $x10: X10 [32r,64r:0) 0@32r                                      
                                                                                 
selectOrSplit GPR:%3 [48r,80r:0) 0@48r  weight:4.675926e-03 w=4.675926e-03       
hints: $x11
assigning %3 to $x11: X11 [48r,80r:0) 0@48r

selectOrSplit FPR64:%4 EMPTY  weight:INF w=INF
AllocationOrder(FPR64) = [ $f0_d $f1_d $f2_d $f3_d $f4_d $f5_d $f6_d $f7_d $f10_d $f11_d $f12_d $f13_d $f14_d $f15_d $f16_d $f17_d $f28_d $f29_d $f30_d $f31_d $f8_d $f9_d $f18_d $f19_d $f20_d $f21_d $f22_d $f23_d $f24_d $f25_d $f26_d $f27_d ]
$f0_d is available at cost 1
Only trying the first 22 regs.

The %4 virtual register is undef, but the first register in the allocation order has a cost > 0. With D118020, only register f8_d-f17_d have cost of 0.

[MatzeB]

The thing that confuses me is that the very first thing in LiveRegMatrix::checkInterference() is this:

if (VirtReg.empty())
  return IK_Free;

so I don't see how we would even reach the intervalIsInOneMBB test if the live interval is empty...

[MatzeB]

In D118124#3270429, @MatzeB wrote:

The thing that confuses me is that the very first thing in LiveRegMatrix::checkInterference() is this:

if (VirtReg.empty())
  return IK_Free;

so I don't see how we would even reach the intervalIsInOneMBB test if the live interval is empty...

Oh wait, I confused the intention of that if in canEvictInterferenceBasedOnCost.

It's still odd to have the empty interval. But adding the check for empty() is fine with me then. LGTM

[• pcwang-thead]

Thanks!

llvm/lib/CodeGen/LiveIntervals.cpp

 CancelKill:
       MI->clearRegisterKills(Reg, nullptr);
     }
   }
 }
 
 MachineBasicBlock*
 LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const {
+  assert(!LI.empty() && "LiveInterval is empty.");
+
   // A local live range must be fully contained inside the block, meaning it is
   // defined and killed at instructions, not at block boundaries. It is not
   // live in or out of any block.
   //
   // It is technically possible to have a PHI-defined live range identical to a
   // single block, but we are going to return false in that case.
 
   SlotIndex Start = LI.beginIndex();

llvm/lib/CodeGen/RegAllocGreedy.cpp

 /// @param IsHint  True when PhysReg is VirtReg's preferred register.
 /// @param MaxCost Only look for cheaper candidates and update with new cost
 ///                when returning true.
 /// @returns True when interference can be evicted cheaper than MaxCost.
 bool DefaultEvictionAdvisor::canEvictInterferenceBasedOnCost(
     LiveInterval &VirtReg, MCRegister PhysReg, bool IsHint,
     EvictionCost &MaxCost, const SmallVirtRegSet &FixedRegisters) const {
   // It is only possible to evict virtual register interference.
   if (Matrix->checkInterference(VirtReg, PhysReg) > LiveRegMatrix::IK_VirtReg)
     return false;
 
-  bool IsLocal = LIS->intervalIsInOneMBB(VirtReg);
+  bool IsLocal = VirtReg.empty() || LIS->intervalIsInOneMBB(VirtReg);
 
   // Find VirtReg's cascade number. This will be unassigned if VirtReg was never
   // involved in an eviction before. If a cascade number was assigned, deny
   // evicting anything with the same or a newer cascade number. This prevents
   // infinite eviction loops.
   //
   // This works out so a register without a cascade number is allowed to evict
   // anything, and it can be evicted by anything.