[LLVMdev] mem2reg optimization

[David Greene]

On Monday 20 October 2008 16:14, Chris Lattner wrote:

> Ok, if you need this direction, just use an
> std::vector<pair<unsigned,Instruction*>> as a forward map?  You can do
> fast binary searches in it.

I don't see how that helps.  I need a map from BasicBlock to a list of loads 
and stores.

> > I suppose we could resctrict the map to containing only load and store
> > instructions but if you've got a block with a lot of memory
> > instructions I'm
> > not sure it will be much faster, especially with the second loop.
>
> Yes, you only want load and stores that directly target allocas.  This
> won't impact the complexity of the routine but will be a nice speedup
> in practice I suspect.

But complexity is exactly what we have to attack.  We're talking LARGE basic 
blocks here.

> > The artificial testcase I've come up with does exactly this.  It
> > basically
> > does load-load-add-store-call over and over again.
>
> It would be nice if you could share the artificial testcase, e.g. by
> attaching it to a bugzilla.

I've got it and will file the bug.

> > I've got the original patch ready to go.  Should I commit that?  I'm
> > thinking
> > if we want to make things simpler later on we can do that and we'll
> > have the
> > testcase in the repository to catch whether we've simplified too
> > much and lost
> > the optimization.
>
> I'd really rather stick with the simple approach, instead of checking
> in the complex one and hoping someone fixes it later.  Thanks Dave,

Fundamentally, we need a map from BasicBlock to a list of ordered loads and 
stores in that block.  So that patch creates two maps: one from BasicBlock to 
a list of loads tagged with ordering information and one from BasicBlock to a 
list of stores tagged with ordering information.  Now, I might be able to 
merge those maps but you'd still be walking through a lot of unnecessary 
instructions (skipping loads when looking for stores and vice-versa).  It's 
this iteration through lists of instructions that's killing compile time.  
Thus we should make it as quick as possible.

                                              -Dave