Registers exhausted with lots of pointer use

[dylanmckay]

This bug description is what I can piece together from CalcSpillWeights.cpp and this email.

When compiling functions for AVR that contain much pointer use, the register allocator fail with the error ran out of registers. A hack is currently in place so that any function marked unspillable that has a lot of pointer access will be forced into being spillable.

The error message is as follows:

LLVM ERROR: ran out of registers during register allocation

Here is the code comment where the hack is implemented (in lib/CodeGen/CalcSpillWeights.cpp): It was commited in r247.

// HACK HACK: This is a workaround until PR14879 gets fixed!
// This code allows us to compile memory intensive functions when only the Z
// register is available, otherwise we get the "Ran out of registers ..."
// assertion inside the regalloc.
// Here we avoid marking as not spillable live intervals that use the
// PTRDISPREGS class and have a size greater than 8, smaller ones
// get filtered out, generating better code.

An old llvmdev mailing list thread discussing the hack can be found here, and continued here.

An LLVM bug is filed for the issue - see LLVM BugZilla bug 14879.

[dylanmckay]

Reproduction code (from LLVM bug report 14879):

main.c:

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;
  }
}

Command line:

clang --target avr-none main.c -mcpu=avrxmega1

Or alternatively, in LLVM IR form:

main.ll:

target datalayout = "e-p:16:8:8-i8:8:8-i16:8:8-i32:8:8-i64:8:8-f32:8:8-f64:8:8-n8"
target triple = "avr-none"

%struct.ss = type { i16, i16, i16 }

; Function Attrs: nounwind
define void @loop(%struct.ss* %x, %struct.ss** %y, i16 %z) {
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
  %0 = load i16, i16* %i, align 2
  %1 = load i16, i16* %z.addr, align 2
  %cmp = icmp slt i16 %0, %1
  br i1 %cmp, label %for.body, label %for.end

for.body:                                         ; preds = %for.cond
  %2 = load i16, i16* %i, align 2
  %3 = load %struct.ss**, %struct.ss*** %y.addr, align 2
  %arrayidx = getelementptr inbounds %struct.ss*, %struct.ss** %3, i16 %2
  %4 = load %struct.ss*, %struct.ss** %arrayidx, align 2
  %b = getelementptr inbounds %struct.ss, %struct.ss* %4, i32 0, i32 1
  %5 = load i16, i16* %b, align 2
  %6 = load %struct.ss*, %struct.ss** %x.addr, align 2
  %c = getelementptr inbounds %struct.ss, %struct.ss* %6, i32 0, i32 2
  %7 = load i16, i16* %c, align 2
  %add = add nsw i16 %7, %5
  store i16 %add, i16* %c, align 2
  br label %for.inc

for.inc:                                          ; preds = %for.body
  %8 = load i16, i16* %i, align 2
  %inc = add nsw i16 %8, 1
  store i16 %inc, i16* %i, align 2
  br label %for.cond

for.end:                                          ; preds = %for.cond
  ret void
}

Command line:

llc -march=avr -mcpu=avrxmega1 main.ll

[dylanmckay]

I have removed the hack from the tree. A proper fix needs to be created.

[dylanmckay]

The error is also triggered in the unit test test/CodeGen/AVR/dynalloca.ll and test/CodeGen/AVR/store.ll.

[dylanmckay]

@agnat I removed part of the hack in 7f4cc26. Do you want to revert it and see where it gets us?

[agnat]

Nah, no worries. Now that I know where the missing pieces are... ;)

[dylanmckay]

I reapplied the hack in f07a0fd.

I'm fairly certain that the Y register preservation hack and the constrained register class hacks are separate entities.

[dylanmckay]

Added a test for this locally

b705c4b

[dylanmckay]

I think this is triggered by this isSpillable() check in RegAllocGreedy.cpp. When I remove the check, the file compiles successfully.

This makes sense, because the existing hacky workaround works by explicitly marking all small live intervals as spillable, even if they were previously marked unspillable.

RegAllocGreedy.cpp

Looking at the generated assembly, we are infact spilling a pointer register when I remove the check. The comment on the original BugZilla mentions that it should be perfectly possible to avoid spilling by simply copying the PTRREG to one of the many DREGS. The problem is likely that LLVM sees that there are no free PTRREGS to copy to, and doesn't take into account we can save/restore to another register class.

This makes sense, because in most backends that LLVM supports, there isn't much overlap between register classes.

The best fix may be to simple support saving/restoring to alternative register classes where possible.

[dylanmckay]

I have a fix pending the test suite which attempts to fix this by attempting to spill live intervals before bailing out like what we do currently (PR #224)

[dylanmckay]

I have merged the fix. Once reviews.llvm.org comes back online, I'll upstream the fix.

[dylanmckay]

Fix merged upstream in r283838