[LLVMdev] Some questions about live intervals

[Roman Levenstein]

Hi Fernando,

For some reason, I discovered your mail just today.

Fernando Magno Quintao Pereira wrote:
> 
> Hi, Roman,
> 
>> 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.
> 
> I think in the description of the algorithm, in page seven, step 6, 
> it has to insert register moves to fix the coloring for each program 
> point P that is part of the program.

Well, as far as I understand this algorithm, it does not do any explicit 
interval splitting. But  it tries to color each live range of the live 
interval separately and may assign different colors to each of those 
live ranges. After color assignment is done, the algorithm needs to 
insert some move intsructions, which is done by step 6. In any case, it 
does not really mean each program point, but only end-points of live 
range belonging to an live interval.

So, it could be seen as some sort of live interval spliiting, but a very 
limited one, since it only splits at the end of live ranges of live 
intervals.

And for sure, Sarkar's algorithm does not handle pre-colored regs out of 
the box.

>> 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?
> 
> One thing that may happen is that, in order to reload spilled variables, 
> you will need registers available.

As far as I understand, it is guaranteed by the algorithm, no special 
reservation in advance is neccessary.

> So, either you spare two registers, 
> what would be very restrictive in x86, or you do backtracking, as the 
> current implementation of LLVM's linear scan does. Backtracking may 
> slowdown the implementation quite a bit. 

Agree. But it is not neccessary. The way how move instructions are 
inserted is very similar to Wimmer's linear scan algorithm. There is no 
need for any reservation of registers in advance or for any backtracking.

>I believe that the other factors will not cause too much slowdown.

Well, from my experience with the Wimmer's linear scan, book-keeping 
during the linear scan allocation becomes more complex and 
time-consuming, once you introduce interval-splitting. Also checks for 
interception of two live intervals are executed more frequently and 
consume a significant part of the execution time. Another rather 
time-consuming operation was the insertion of register moves to glue the 
splitted parts together. But this is mainly due to the current LLVM 
design, since such an operation require for each MBB a set of live-in 
live intervals. And LLVM currently computes live-ins for each MBB just 
for physical registers, but not for virtual live intervals.

Best,
   Roman