J.C. Pizarro wrote:
On Tue, 29 Apr 2008 20:25:56 +0200, "Steven Bosscher"
<[EMAIL PROTECTED]> wrote:
On Tue, Apr 29, 2008 at 6:22 PM, Mark Mitchell <[EMAIL PROTECTED]> wrote:
Vladimir, if you feel that Peter's code cannot be used directly in IRA,
would you please explain why not?
I think he already has explained, see
http://gcc.gnu.org/ml/gcc/2008-04/msg00730.html
Having looked at IRA a bit, I think I have to agree with Vlad that
Peter's code is not easily adapted to IRA. Peter's code works for a
single, immutable conflict graph for the whole function. IRA works
with inter-region and intra-region conflicts (as far as I understand,
documentation in ira-conflict.c would be welcome), so the sorting
trick that Peter uses, doesn't translate one-to-one to Vlad's
allocator.
Having said that, I think the "square" approach with
mirror_conflicts() that IRA currently has, is a big step backward from
what we have now. IRA should at least have a representation for
conflicts that does not duplicate information unnecessary. The bits
that seem to be bad in this respect are build_conflict_bit_table() and
mirror_conflicts(). It's not clear to me how these are used, but it
looks like you can end up building a square conflict graph for the
whole function, like GCC did before Peter's work. This could be a
huge memory and speed regression if it isn't addressed.
Another note: IRA uses VARRAYs, and I was under the impression we are
trying to move away from those. Vlad, please use VECs instead.
Gr.
Steven
Use my idea of flexible chained upper triangulars & rectangulars as
indicated briefly in
http://gcc.gnu.org/ml/gcc/2008-04/msg00707.html
http://gcc.gnu.org/ml/gcc/2008-04/msg00681.html
You can update easily these structures through subroutines that
traverse the chains and update their chained local structures when
is needed, and is similar to the Observer pattern (when the subjects
are modified then it update the views of the observers too).
Your approach was interesting but it needs some partition of allocnos.
This partition is present in Peter's code (local allocnos in each BB and
global allocnos). Partition is not easy to do when live ranges are
used to find potential conflicts. Also such partition is less accurate
and will result bigger matrices than using live ranges to find potential
conflict for each allocno pair.
The part of what you are proposing (partitioning allocnos) is close to
many implementation of register allocators, e.g. Chow in his
implementation of priority coloring built conflicts only for global
allocnos to save memory.
