Peter Bergner wrote:
On Mon, 2008-04-28 at 16:01 -0400, Vladimir Makarov wrote:
Thanks, Peter. That was clever and email is very enlightening. I have
analogous idea for more compact conflict matrix representation. IRA
builds allocno live ranges first (they are ranges of program points
where the allocno lives). I can use this information for fast searching
potential conflicts to sort the allocnos. Probably the matrix will be
even more compact because live ranges contain more detail info than
basic blocks where the local allocnos live. For example, the ranges
even can show that allocnos local in the same block will never
conflicts. It means that matrix even for fppp can be compressed.
You say you use your analogous idea now? Can you point me to the code?
I thought I heard you (maybe someone else?) that your conflict information
was much bigger than old mainline. If this is true and you are compacting
the bit matrix like I am, why is it so big?
I am currently working on bit matrix compression. It is not implemented
yet. I hope it will be ready in a week.
Live ranges were implemented long ago. They are quit important for fast
transformation of regional IR into one region IR (before this I just
rebuilt IR which was simple code but very time consuming). IRA can
create additional allocnos because of live range splitting on the region
borders and remove some of them during the transformation. The
transformation is complicated because allocnos on upper levels of the
region tree accumulate a lot of info (including conflicts) from allocnos
on lower levels.
I tried to use sparsets for the same purposes (only for maintaining and
processing allocnos currently living). But usage of sparsets for this
purposes gave practically nothing (I had to use valgrind lackey to see
the difference). Therefore I decided not to introduce the additional
data and use just bitmaps for this.
Sparsets already exists in a compiler. I am thinking about their usage
too. May be you have a benchmark where the sparsets give a visible
compiler speed improvement (my favorite was combine.i). I'd appreciate
if you point me such benchmark. It could help me to make a decision to
use sparsets.
Yes, I added the sparseset implementation that has been in since gcc 4.3.
Did you use my sparseset implementation or did you write your own for your
tests? I don't recall which file(s) I saw the difference on. All I recall
is I tried it both ways, saw a difference somewhere and promptly threw the
slower code away along with which file(s) I saw the difference on. Sorry I
can't be of more help.
I had own implementation which I used for YARA project.
Given how sparsesets are implemented, I cannot see how they could ever be
slower than bitmaps for the use of "live", but I can see how they might be
faster. That said, if your allocator is spending enough time elsewhere,
then I can easily imagine the difference being swamped such that you don't
see any difference at all.
Yes, that is true. I found that the code using sparsets (or bitmaps)
are far away to be a bottleneck.
