Hi,
I have worked a little on the PBQP register allocator, and it is quite clear (at
least to me) that it is not even a serious alternative to RegAllocGreedy at the
moment, due to the poor handling of spilling. As Arnaud wrote below, it is not
optimizing spilling at all, but rather just spills anything that does not get an
assignment. The result is a lot more spill/reload instructions than needed.
In RegAllocBase.h it says "...Register allocation complexity, and generated
code performance is determined by the effectiveness of live range splitting
rather than optimal coloring...". I would then think that any register
allocation algorithm should benefit from this, but find that only RegAllocGreedy
is doing live range splitting, and that the code for doing this is local to that
allocator.
I would like to suggest a refactoring to make RAGreedy::trySplit() and its sub
functions callable from any register allocator. Perhaps part of SplitEditor?
What do you think about this?
/Jonas
From: Arnaud A. de Grandmaison [mailto:arnaud.degrandmaison at arm.com]
Sent: den 4 mars 2015 15:43
To: Jonas Paulsson; Lang Hames
Cc: llvmdev at cs.uiuc.edu
Subject: RE: PBQP spilling
Yes, for now the spilling is done in the most basic way, i.e. it's
functionally correct --- but not efficient. The focus was on the allocator
itself, not on the spilling. As you noticed, the work still to be done in this
area is live range splitting, and smarter spill code insertion. Another area is
improving the reduction order, to make the allocator less sensitive to the
reduction order.
There is no official plan; we started to discuss that with Lang some time ago,
but none of us had time to dive into it yet. Any help appreciated there :).
Cheers,
Arnaud
From: Jonas Paulsson [mailto:jonas.paulsson at ericsson.com]
Sent: 04 March 2015 13:51
To: Lang Hames; Arnaud De Grandmaison
Cc: llvmdev at cs.uiuc.edu<mailto:llvmdev at cs.uiuc.edu>
Subject: PBQP spilling
Hi,
I would like to ask about PBQPs use of InlineSpiller. The code output when using
PBQP gets a lot bigger compared to when using RegAllocGreedy. PBQP does not
split the live intervals, and a lot more (often redundant) reload instructions
are emitted as a result, it seems. I wonder why this is, and if there are any
plans to improve on this point?
/Jonas Paulsson
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150306/102169de/attachment.html>