Scalar replacement of arrays

Nicolas Capens wrote:

I'm not sure if that's going to help achieve optimal code
for when the array is sometimes being dynamically indexed.
Essentially there should be some kind of store to load copy
propagation. As far as I know that's exactly what mem2reg
does, except that it only considers scalars and not elements
of arrays.

So would it be hard to extend mem2reg to also consider elements
of arrays for promotion? It should obviously not perform the promotion
when in between the store and load there's a dynamically indexed
access to the array. Correct me if I'm wrong, but that seems it would
be superior to scalarrepl itself (for arrays).

Is there anyone experienced with mem2reg who wants to implement this?
If not, any advice on how to best approach this?

Classically, we use dependence analysis to support such optimizations.
For example, see Chapter 8 in Allen & Kennedy's book,
"Optimizing Compilers for Modern Architectures."


Hi Preston,

Thanks for the suggestion. Unfortunately I don't know how to apply it to LLVM.

I'm struggling with the problem of spilling. Basically scalarrepl makes the original array alloca disappear and replaces it with individual scalar allocas, which then also disappear when mem2reg puts them into SSA form. Then register allocation puts stuff on the stack again, but not where the allocas were. That's a problem when you actually expect to be able to dynamically index the array.

I'd like the array alloca to stay where it is, but to see the same optimizations as achieved by scalarrepl+mem2reg in sections of code where no dynamic indexing is occuring, and the register allocator should spill and restore to/from the original array so that for dynamic indexing a minimal number of registers is written back to memory.

I'm starting to think this actually can't be achieved with SSA at all. Perhaps I shouldn't run scalarrepl and see if the optimizations can be performed at the register allocator level instead?