[RegAllocGreedy] Attempt to split unspillable live intervals

[dylanmckay]

Summary

Previously, when allocating unspillable live ranges, we would never
attempt to split. We would always bail out and try last ditch graph
recoloring.

This patch changes this by attempting to split all live intervals before
performing recoloring.

This fixes LLVM bug PR14879.

I can't add test cases for any backends other than AVR because none of
them have small enough register classes to trigger the bug.

[dylanmckay]

Here's the bug that this fixes

https://llvm.org/bugs/show_bug.cgi?id=14879

[dylanmckay]

This was accidentally committed and immediately reverted.

[qcolombet]

+llvm-commits

[qcolombet]

Hi,

As it is, I don't think this will do what you want.
Namely, I think when we spilt a live-range, we do not mark the new live-ranges as unspillable. Thus, I believe we may spill the new split products of an unspillable live-range.

At the very least, I would expect we walk the NewVRegs list and mark the elements as unspillable.
That being said, the proper fix is probably within LiveRangeEdit.

I let you have a look and get back to me if you have any question.

Cheers,
-Quentin

[dylanmckay]

Don't split an unspillable live interval into spillable live intervals

[dylanmckay]

Hey Quentin,

That was a nice catch. I've updated the diff so that it no longer splits unspillable live intervals into spillable live intervals.

[qcolombet]

Hi Dylan,

I don't know if phabricator is acting strange but there is something odd with the diff.
I see things that do not seem to be part of that diff (AVRMCInstLower.*) and the changes in RegAllocGreedy.cpp disappeared.

Could you check the uploaded patch?

Thanks,
-Quentin

lib/CodeGen/LiveRangeEdit.cpp

443

No brackets for one line blocks per LLVM coding style.

[dylanmckay]

Remove extraneous braces from if block.

Also fixed a rebase-gone-wrong and removed the AVRMCInstLower stuff that I recently committed to trunk.

[qcolombet]

Hi Dylan,

LGTM.

Few nitpicks inlined, no need for another round of review.

Cheers,
-Quentin

lib/CodeGen/RegAllocGreedy.cpp

2557

if (Stage < RS_Spill) should do the trick and is more understandable IMO.

test/CodeGen/AVR/high-pressure-on-ptrregs.ll

37

Also check that the generated code looks reasonable.

51

Use opt -instnamer to get rid of the [0-9]+ variables.

[dylanmckay]

Code cleanups from Quentin

• Use the instnamer pass to clean up the testcase
• Change condition from 'is split 1 or is split 2' to 'less than spill'

test/CodeGen/AVR/high-pressure-on-ptrregs.ll

51

Didn't know of that - nice.

[dylanmckay]

Committed in r283838

lib/CodeGen/LiveRangeEdit.cpp

 // Keep track of new virtual registers created via
 // MachineRegisterInfo::createVirtualRegister.
 void
 LiveRangeEdit::MRI_NoteNewVirtualRegister(unsigned VReg)
 {
   if (VRM)
     VRM->grow();
 
+  if (Parent && !Parent->isSpillable())
+    LIS.getInterval(VReg).markNotSpillable();
+
   NewRegs.push_back(VReg);
 }
 
 void
 LiveRangeEdit::calculateRegClassAndHint(MachineFunction &MF,
                                         const MachineLoopInfo &Loops,
                                         const MachineBlockFrequencyInfo &MBFI) {
   VirtRegAuxInfo VRAI(MF, LIS, VRM, Loops, MBFI);

lib/CodeGen/RegAllocGreedy.cpp

unsigned RAGreedy::selectOrSplitImpl(LiveInterval &VirtReg,
   // This gives a better picture of the interference to split around.
   if (Stage < RS_Split) {
     setStage(VirtReg, RS_Split);
     DEBUG(dbgs() << "wait for second round\n");
     NewVRegs.push_back(VirtReg.reg);
     return 0;
   }
 
-  // If we couldn't allocate a register from spilling, there is probably some
-  // invalid inline assembly. The base class wil report it.
-  if (Stage >= RS_Done || !VirtReg.isSpillable())
-    return tryLastChanceRecoloring(VirtReg, Order, NewVRegs, FixedRegisters,
-                                   Depth);
-
+  if (Stage < RS_Spill) {
     // Try splitting VirtReg or interferences.
     unsigned NewVRegSizeBefore = NewVRegs.size();
     unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs);
     if (PhysReg || (NewVRegs.size() - NewVRegSizeBefore))
       return PhysReg;
+  }
+
+  // If we couldn't allocate a register from spilling, there is probably some
+  // invalid inline assembly. The base class wil report it.
+  if (Stage >= RS_Done || !VirtReg.isSpillable())
+    return tryLastChanceRecoloring(VirtReg, Order, NewVRegs, FixedRegisters,
+                                   Depth);
 
   // Finally spill VirtReg itself.
   if (EnableDeferredSpilling && getStage(VirtReg) < RS_Memory) {
     // TODO: This is experimental and in particular, we do not model
     // the live range splitting done by spilling correctly.
     // We would need a deep integration with the spiller to do the
     // right thing here. Anyway, that is still good for early testing.
     setStage(VirtReg, RS_Memory);

test/CodeGen/AVR/high-pressure-on-ptrregs.ll

+; RUN: llc < %s -march=avr | FileCheck %s
+
+; This tests how LLVM handles IR which puts very high
+; presure on the PTRREGS class for the register allocator.
+;
+; This causes a problem because we only have one small register
+; class for loading and storing from pointers - 'PTRREGS'.
+; One of these registers is also used for the frame pointer, meaning
+; that we only ever have two registers available for these operations.
+;
+; There is an existing bug filed for this issue - PR14879.
+;
+; The specific failure:
+; LLVM ERROR: ran out of registers during register allocation
+;
+; It has been assembled from the following c code:
+;
+; struct ss
+; {
+;   int a;
+;   int b;
+;   int c;
+; };
+;
+; void loop(struct ss *x, struct ss **y, int z)
+; {
+;   int i;
+;   for (i=0; i<z; ++i)
+;   {
+;     x->c += y[i]->b;
+;   }
+; }
+
+%struct.ss = type { i16, i16, i16 }
+
+; CHECK-LABEL: loop
+define void @loop(%struct.ss* %x, %struct.ss** %y, i16 %z) #0 {
+entry:
+  %x.addr = alloca %struct.ss*, align 2
+  %y.addr = alloca %struct.ss**, align 2
+  %z.addr = alloca i16, align 2
+  %i = alloca i16, align 2
+  store %struct.ss* %x, %struct.ss** %x.addr, align 2
+  store %struct.ss** %y, %struct.ss*** %y.addr, align 2
+  store i16 %z, i16* %z.addr, align 2
+  store i16 0, i16* %i, align 2
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %tmp = load i16, i16* %i, align 2
+  %tmp1 = load i16, i16* %z.addr, align 2
+  %cmp = icmp slt i16 %tmp, %tmp1
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp2 = load %struct.ss**, %struct.ss*** %y.addr, align 2
+  %tmp3 = load i16, i16* %i, align 2
+  %arrayidx = getelementptr inbounds %struct.ss*, %struct.ss** %tmp2, i16 %tmp3
+  %tmp4 = load %struct.ss*, %struct.ss** %arrayidx, align 2
+  %b = getelementptr inbounds %struct.ss, %struct.ss* %tmp4, i32 0, i32 1
+  %tmp5 = load i16, i16* %b, align 2
+  %tmp6 = load %struct.ss*, %struct.ss** %x.addr, align 2
+  %c = getelementptr inbounds %struct.ss, %struct.ss* %tmp6, i32 0, i32 2
+  %tmp7 = load i16, i16* %c, align 2
+  %add = add nsw i16 %tmp7, %tmp5
+  store i16 %add, i16* %c, align 2
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %tmp8 = load i16, i16* %i, align 2
+  %inc = add nsw i16 %tmp8, 1
+  store i16 %inc, i16* %i, align 2
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+