[LLVMdev] scalarrepl tuning

[Bob Wilson]

In svn r95224 I modified the scalar replacement (SROA) pass to use different criteria to decide when it is likely to be profitable to split up an aggregate into its separate elements.  The commit message has a pretty decent explanation, but I wanted to give some further detail here.  I am hoping that the llvm-dev list allows messages with attachments.  If the graphs get stripped off, this won't be very interesting.

I was inspired by Jakob's approach to using SCIENCE to adjust our inlining heuristics, so I did a few experiments for SROA.  For these experiments, I ran the llvm nightly test benchmarks, including 3 different versions of SPEC and various other applications.  The first thing measured was the total size and number of elements for each aggregate encountered by SROA.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: sroa-stats.png
Type: image/png
Size: 6939 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100203/23fb1e8a/attachment.png>
-------------- next part --------------


The old SROA code would only consider the points in the lower left quadrant: size <= 128 bytes and elements <= 32.  The obvious diagonal lines made me realize that most of the large aggregates are arrays (duh!) and that it would be a good idea to look at structs and arrays separately.  So, I repeated the experiment, looking only at struct types:
-------------- next part --------------
A non-text attachment was scrubbed...
Name: sroa-structs.png
Type: image/png
Size: 5427 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100203/23fb1e8a/attachment-0001.png>
-------------- next part --------------

This confirmed my intuition that there are a reasonable number of large (in bytes) structs with a relatively small number of elements.  Those structs should be candidates for SROA.  I have not done the experiment to see how many of them we actually succeed in transforming.  The current limit of 32 elements looks to me like a reasonable cutoff point.  There are a few  points above that green line, and chances are that structs with so many elements will not be safe to SROA anyway.

The last experiment was to test my intuition that SROA will rarely apply to arrays, since it requires that they be accessed with only constant indices.  I was expecting that we could get away with setting a very low limit on the number of array elements for SROA candidates.  To test this, I compiled all the benchmarks and accumulated counts of array sizes in cases where we succeeded with SROA.  I don't have a graph for this, but I was surprised in several ways.  First there were 8377 arrays transformed by SROA.  That's a lot more than I expected.  Second, I was guessing that we would almost never split up an array with more than 4 elements, but there were 350 cases where that happened.  I decided to go with a limit of 8 elements, since that caught all but 16 cases.