[LLVMdev] mem2reg optimization

[Chris Lattner]

On Oct 4, 2008, at 2:51 PM, Chris Lattner wrote:
>>> 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.
>>
>> I got my patch updated to work with TOT.  Here it is.  Comments
>> welcome.
>
> Hi Dave,
>
> Great.  I'd like to get this in, but would really like to do a profile
> first.  Could you please include a testcase?  Even if it is something
> contrived with llvm-gcc, I would really like to understand what is
> going on.

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.

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.

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.

-Chris