[LLVMdev] Scalar replacement of arrays

[Nicolas Capens]

Hi Eli,

I was surprised to see that you're getting more optimal code. But I'm 
using the JIT so I realized there must be some extra optimization passes 
in -O2 which I wasn't using. It turns out that a second scalarrepl 
followed by ADCE did the trick for that small sample.

Initially it didn't work for my larger project though. So I dug a little 
deeper and found out that scalarrepl uses a default threshold of 128 
bytes for arrays. Increasing that to the size of the virtual processor's 
register array made it work as expected! That is, as long as the array 
isn't being dynamically indexed. In any case this is a little more 
promising than I thought since scalarrepl does handle arrays.

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

Thanks,
Nicolas


On 07/03/2012 4:00 PM, Eli Friedman wrote:
> 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