Home

[RegAlloc] Add a last chance recoloring mechanism when everything else failed to

Press ? to show keyboard shortcuts.
Committed
qcolombetFeb 5 2014, 2:13 PM
Parents
rL200882: Don't print out "script" results twice.
Branches
Unknown
Tags
Unknown
Subscribers
None
Projects
None
Description

[RegAlloc] Add a last chance recoloring mechanism when everything else failed to
find a register.

The idea is to choose a color for the variable that cannot be allocated and
recolor its interferences around. Unlike the current register allocation scheme,
it is allowed to change the color of an already assigned (but maybe not
splittable or spillable) live interval while propagating this change to its
neighbors.
In other word, there are two things that may help finding an available color:

  • Already assigned variables (RS_Done) can be recolored to different color.
  • The recoloring allows to catch solutions that needs to touch more that just the neighbors of the current allocated variable.

E.g.,
vA can use {R1, R2 }
vB can use { R2, R3}
vC can use {R1 }
Where vA, vB, and vC cannot be split anymore (they are reloads for instance) and
they all interfere.

vA is assigned R1
vB is assigned R2
vC tries to evict vA but vA is already done.

> Regular register allocation heuristic fails.

Last chance recoloring kicks in:
vC does as if vA was evicted => vC uses R1.
vC is marked as fixed.
vA needs to find a color.
None are available.
vA cannot evict vC: vC is a fixed virtual register now.
vA does as if vB was evicted => vA uses R2.
vB needs to find a color.
R3 is available.
Recoloring => vC = R1, vA = R2, vB = R3.

rdar://problem/15947839

rL200883

llvm/trunk/lib/CodeGen/RegAllocGreedy.cpp

Loading...

llvm/trunk/test/CodeGen/X86/ragreedy-last-chance-recoloring.ll

Loading...

Add Comment