[LLVMdev] mem2reg optimization

[David Greene]

On Thursday 25 September 2008 07:40, Nicolas Capens wrote:
> Hi Dave,
>
> As an exercise I tried to fix this myself, and I think I have a working
> patch (attached). My own tests are all working wonderfully, and at
> fantastic performance!
>
> I'm looking forward to your patch to see whether we used the same approach
> or whether things could be improved further.
>
> Anyway, I've re-profiled the code and found ComputeLiveInBlocks to be the
> main hotspot now. Again it uses a linear search over the instructions so
> there's a chance this can be optimized as well...

I don't quite understand how the logic of your patch is the same.  In the 
original code, we're looking for a Load that uses the alloca before it is
stored.  Your code loops through the use list, first looking for the use
that is the store.  It then keeps going and if it sees a match with a load,
it prevents promotion.

Are use lists guaranteed to be ordered in reverse instruction order?  That
is instructions that use values later appear earlier in the use list?  Can we
really rely on ordering of the use list?

My patch builds a map from BasicBlock to lists of loads and stores in that
block in an initialization phase along with ordering information about the
loads and stores.  RewriteSingleStoreAlloca then queries that information
to determine if a load appears before the single store.

I like your approach of using the use lists but I'm not sure the ordering is
guaranteed.  If it is, your approach is superior.

                                                    -Dave