[LLVMdev] Optimization of array access

[Don Quixote de la Mancha]

On Mon, Nov 21, 2011 at 8:58 AM, Michael Smith
<Michael.Smith at synopsys.com> wrote:
> The two patterns are:
>
>                 Stack[0] = 0;
>                 Stack[1] = 1;
>                 Stack[2] = 42;
>
> And
>
>                 Int I = 0;
>
>                 Stack[i++] = 0;
>                 Stack[i++] = 1;
>                 Stack[i++] = 42;

The optimizer is probably not sophisticated enough to figure out that
the array indices in your first pattern are sequentially incrementing
integers.  So the generated code has to store each individual array
index constant somewhere, load it into a register, multiply it by the
size of your array elements, then add it to the pointer to the base of
the array.  It does that for each array access.

On some architectures, loading constant values can be expensive
because the machine code words do not provide enough bits to encode
arbitrary immediate constants.  The constants are most often stored
just after the end of the function's executable code, then read into a
register with PC-relative addressing.

Other architectures allow one to load any immediate constant, but this
comes at the cost of placing the value of the constant just after the
instruction that loads it.  But that stalls the processor's pipeline
until the constant has been loaded into the register.

In your second pattern, the simple way would be to have a fixed
pointer to the base of your array, and a register that is used as an
offset.  Most architectures offer autoincrement/autodecrement modes
for access patterns just as you describe, in which that index register
is incremented by the size of your array elements just after it is
used as an offset.

But in this case the optimizer is smart enough to see that you're
indexing through an array.  Rather than using a base register and an
offset register, the initial value of i is added to the base register,
then this register is used all by itself, again with autoincrementing.

Not having to use a second register for the index allows that second
register to be used for some other purpose, so that other parts of
your code can be optimized more effectively.


-- 
Don Quixote de la Mancha
Dulcinea Technologies Corporation
Software of Elegance and Beauty
http://www.dulcineatech.com
quixote at dulcineatech.com