[LLVMdev] mem2reg optimization

[Dan Gohman]

On Thu, October 2, 2008 10:17 am, Nicolas Capens wrote:
> Hi all,
>
> I haven't had a chance yet to do some accurate profiling, but does anyone
> have some more insight in the use list order? *bump*

I thought this was answered; use lists are not currently in
any intentional order.

>
> It seems very valuable to me (from a performance standpoint) to keep the
> use
> list in (reverse) order. But if this can't be guaranteed it might still be
> interesting to have some fast variants of passes that do make some
> assumptions (like my patch for mem2reg). I believe I can optimize more
> passes by making such assumption about the order of the use lists, so any
> and all information about that is welcome.

Keeping use lists sorted, in general, seems expensive. Take a pass
like LICM; when an Instruction is hoisted from a loop, its position
in any use lists it's on may need to change if they are to remain
sorted. Determining the new position would require determining
where the other instructions in the list are.

The property of being able to arbitrarily reorder LLVM passes
is an important design goal. I don't think we want to have variants
that make assumptions about use list ordering unless there are
very significant advantages.

That said, it's an interesting idea. Would you be able to
perform the same optimizations using an analysis pass that
provides a topological ordering for all Instructions?

Dan