[LLVMdev] Some questions about live intervals

[Roman Levenstein]

> > Actually, Sarkar's algorithm can split only at block boundaries, as
> far as I understand. This can be an obstacle for very long basic
> blocks.
> > One of the interesting ideas could be to introduce live-range
> splitting into his algorithm.
> 
> As far as I understand it, it can also split in the interior of basic

> blocks, because of pre-colored registers, otherwise it would  not be 
> optimal.

Well, I cannot find anything about in my copy of the paper. The paper
neither talk about splitting in the interior of basicc blocks, nor
about handling of pre-colored registers. And Sarkar also does not claim
the optimality of the algorithm. He claims that it is inherently more
scalable and efficient, i.e. linear as compared to O(n^2) for Graph
coloring. 

But of course this is required and I'm going to extend the algorithm to
support it by doing splitting before pre-colored uses.


BTW, there are some other missing features in the Sarkar's algorithm.
For example, it spills only whole intervals, which is very similar to
typical GC regallocs, but not very efficient. I think, some of the
known methods for live-range splitting around high-pressure regions in
GC world, can be also applied here. This should improve the quality of
allocation. 

Actually, I'm wondering if interval-splitting, handling of pre-colored
registers, handling of high-pressure regions would slow down the
algorithm to a very big extent or not?


> > I've seen references to it on your page. But this debugger is in
> Java, or? So, one has to dump the results of register allocation and
> input problem and it would do some checks, or?
> 
> It is implemented in Java. You must dump some output and run the
> debugger  on this output.

OK. Then my understanding was correct.
 
> > Actually, I already implemented something very similar for Wimmer's
> > linear scan. The main issue was to order the copies in the right
> way and to introduce stores/loads to handle circular dependencies. Or
> do you say that register classes of different sizes introduce
> additional problems?
> 
> Well, it makes it a little bit more complicated, but only a little
> bit. A  problem that I had was when the lower and higher bits of 
> registers were swapped.

Oh, now I see. My version of Wimmer's algorithm was written before LLVM
introduced support for sub-regs. Therefore I didn't have this problem
;-) But now I have to cope with it. Anyway, I think it is a minor
extension. I guess, I should just take aliasing information into
account when ordering register moves.

-Roman


      Heute schon einen Blick in die Zukunft von E-Mails wagen? Versuchen Sie´s mit dem neuen Yahoo! Mail. www.yahoo.de/mail