[LLVMdev] Scalar replacement of arrays

[Eli Friedman]

On Wed, Mar 7, 2012 at 12:47 PM, Nicolas Capens
<nicolas.capens at gmail.com> wrote:
> Hi all,
>
> I'm implementing a virtual processor which features dynamic register
> indexing, and I'm struggling to make LLVM 3.0 produce good code for it.
> The register set is implemented as an LLVM array so it can be
> dynamically indexed using GEP. However, most of the time the virtual
> processor's registers are just statically indexed, and so I
> expected/hoped the code would be as optimal as when the virtual
> registers are implemented using individual scalars, which are allocated
> to the target machine's physical registers as much as possible. But that
> turns out not to be the case and I end up with code which constantly
> reads and writes memory to access my virtual registers.
>
> The "Scalar Replacement of Aggregates" pass (scalarrepl) seems to be
> capable of splitting structures into separate fields so that mem2reg can
> produce efficient code which avoids redundant memory operations. But it
> skips my array entirely. Here's a small piece of C code which
> illustrates the problem:
>
> int foo(int x, int y)
> {
>     int r[2];
>     r[0] = x;
>     r[1] = y;
>     r[0] = r[0] + r[1];
>     return r[0];
> }

clang -O2 for that C code gives:

	pushl	%ebp
	movl	%esp, %ebp
	movl	12(%ebp), %eax
	addl	8(%ebp), %eax
	popl	%ebp
	ret


> If I replace the array with two individual scalars, I get the following
> perfect result instead:
>
>  mov         eax,dword ptr [esp+8]
>  add         eax,dword ptr [esp+4]
>  ret
>
> Unfortunately, I don't think that having scalarrepl handle arrays will
> do the trick. It will work for the above trivial example, but my array
> of registers does get indexed dynamically from time to time, and this
> would completely prevent scalarrepl from doing anything, right?

Yes; you wouldn't really want it to try.

> Ideally LLVM should keep things in physical registers as long as
> possible, and when the virtual register array is being dynamically
> indexed it should write the physical registers back to the array...
>
> So does anyone know if this can already be achieved using some other
> passes or settings? If not, what would be the best approach to implement it?

Conceptually, we ought to be able to handle that sort of issue with a
combination of GVN and dead store elimination (DSE).  Unfortunately,
LLVM's DSE pass is rather weak. so that approach might not be so
effective in practice.

-Eli