[LLVMdev] mem2reg optimization

[David Greene]

On Saturday 04 October 2008 17:05, Chris Lattner wrote:

> Looking more closely at the approach, I infer that the (logical in
> hindsight) issue are cases where mem2reg scans a BB to see the
> relative ordering of two instructions.  For example, the single store

Correct.

> case.  I could imagine that if you saw lots of single store allocas in
> the middle of a large BB that mem2reg would be very very slow.

Right.

> As far as the approach goes, here's a counterproposal that is a bit
> less complex.  I suggest adding a single DenseMap<Instruction*,
> unsigned> to Mem2reg.  If there is an entry in this map for a load/
> store instruction, it would store the instruction's index in its basic
> block.  This means that to check dominance of two instrs in a block,
> you just need to compare their two indices (which is fast).  Really
> small blocks (< 10 instructions?) would never be entered into map, to
> keep the size of the map low.  The first time a query is made within a
> large block, it would compute the indices of all loads and stores
> within the block.

This is a simpler approach and should have the same effect.  I'll code it up.

> The nice thing about using a single map is that it makes updating the
> map really trivial.  Just use TheMap.erase(I) when deleting load and
> store instructions.  The numbering can be purely local to a block and
> the relative ordering of memops don't get invalidated when a load or
> store is nuked.

Good points.

> Does this seem like a reasonable approach?  If so, please split the
> various parts of mem2reg out into helper methods as a prepatch.  This
> will make review of the subsequent changes much easier.

Which various parts are you referring to?  You mean the stuff that populates 
and updates the map?

                                               -Dave