Skip to content

Commit

Permalink
[RegAllocGreedy] Attempt to split unspillable live intervals
Browse files Browse the repository at this point in the history
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.

Reviewers: qcolombet

Subscribers: MatzeB

Differential Revision: https://reviews.llvm.org/D25070

llvm-svn: 282852
Dylan McKay committed Sep 30, 2016
1 parent f50bafc commit 2a80cc6
Showing 2 changed files with 86 additions and 6 deletions.
14 changes: 8 additions & 6 deletions llvm/lib/CodeGen/RegAllocGreedy.cpp
Original file line number Diff line number Diff line change
@@ -2556,18 +2556,20 @@ unsigned RAGreedy::selectOrSplitImpl(LiveInterval &VirtReg,
return 0;
}

if (Stage == RS_Split || Stage == RS_Split2) {
// 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);

// Try splitting VirtReg or interferences.
unsigned NewVRegSizeBefore = NewVRegs.size();
unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs);
if (PhysReg || (NewVRegs.size() - NewVRegSizeBefore))
return PhysReg;

// Finally spill VirtReg itself.
if (EnableDeferredSpilling && getStage(VirtReg) < RS_Memory) {
// TODO: This is experimental and in particular, we do not model
78 changes: 78 additions & 0 deletions llvm/test/CodeGen/AVR/high-pressure-on-ptrregs.ll
Original file line number Diff line number Diff line change
@@ -0,0 +1,78 @@
; 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) {
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
}

0 comments on commit 2a80cc6

Please sign in to comment.