[LLVMdev] mem2reg optimization
dag at cray.com
Tue Oct 21 10:16:02 PDT 2008
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
> > 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
> > 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.
More information about the llvm-dev