[LLVMdev] df_ext_iterator in LiveIntervalAnalysis

[Fernando Magno Quintao Pereira]

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.

Fernando

> Hi,
>
> 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.
>
> -Roman