[LLVMdev] df_ext_iterator in LiveIntervalAnalysis

Fernando Magno Quintao Pereira fernando at CS.UCLA.EDU
Fri Jun 22 11:28:00 PDT 2007


That is very true. Holes appear mostly due to phi-elimination. That is why 
I said you would have to change the implementation a bit. To avoid these 
holes, one must assign registers before SSA-elimination. In general this 
tends to reduce spill, but increases the number of copies in the final 
code.

>
> You can still have holes due to phi elimination, copy coallescing, live
> ranges for physregs, etc.
>
> -Chris
>
> On Fri, 22 Jun 2007, Fernando Magno Quintao Pereira wrote:
>> Actually, changing the ordering, with the current implementation of linear
>> scan that LLVM uses, will not bring improvements to the code. The register
>> allocator must be aware that the intervals are been visited in the order
>> of dominance between basic blocks. This allows to simplify the
>> implementation a bit, because you don't have to handle holes in the live
>> ranges: the new ordering has the property that, once a program point is
>> visited (i.e the intervals starting at that program poin), all the program
>> points that dominate it have already been visited.
>
>>> Just my two cents:
>>>
>>> If I recall correctly, in some papers on the linear scan register
>>> allocation people described that they tried different orderings for
>>> instruction numbering, e.g. including DFS or based on the loop nesting
>>> levels, etc. There was no clear winner though.
>>>
>>> But let's see the numbers anyway. May be it really brings some improvements.



More information about the llvm-dev mailing list