[LLVMdev] mem2reg optimization

[Chris Lattner]

On Oct 6, 2008, at 9:47 AM, David Greene wrote:
>> 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.

Great! Thanks,

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

I'm criticizing the existing code :), which is just very poorly  
structured.  It would be nice to do a refactoring patch first which  
just splits the various "scan a BB" places out into helper methods,  
instead of them being inlined into larger pieces of code.  This will  
make the mem2reg algo easier to read and will make the algorithmic  
change easier to review.

If you want, I can change one of the places that does a scan to show  
what I mean,

-Chris