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 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. 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. Peter