[LLVMdev] mem2reg optimization

David Greene dag at cray.com
Mon Oct 6 09:47:24 PDT 2008

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


> 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.


> 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?


More information about the llvm-dev mailing list