[LLVMdev] mem2reg optimization

[Chris Lattner]

On Oct 3, 2008, at 10:34 AM, Dan Gohman wrote:
>> 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.

I agree with Dan here.  It would be an interesting property, but it  
just isn't feasible to maintain any sane ordering here.

-Chris