High-level optimizations have to be done mostly by the front-end because
the back-end usually doesn't know about the high-level constructs of D.
So this is the right place to ask for some of such optimizations, while
asking for them on the LLVM or LDC IRC channels is not the best thing to
do (even if LDC developers usually try to do what I ask them, they are
very gentle).
---------------------
Recently here I've shown a link to some of the optimizations done by the
Scala compiler (that the JavaVM back-end isn't able to perform), but
that post was ignored. The most important thing it does is to inline
most closures of a Scala program. Such optimization is important for
functional-style programming, because (like tail-call optimization) if
present allows the programmer to use certain idioms with more freedom
(like passing delegates to higher order functions, etc), essentially
allowing a different programming style. Probably this optimization isn't
easy to implement, it requires some code. Is someone interested in
adding this to D?
---------------------
This comes from successive simplification of some code of mine, it's a
loop with a kernel over an array, a common operation in my kind of code:
version(Tango) import tango.stdc.stdio: printf;
void main() {
auto a = new int[30];
for (int x = 2; x < a.length-2; x++)
foreach (s; [-2, -1, 0, 1, 2])
a[x] += a[x + s];
printf("%d\n", a[5]);
}
This is the asm produced by LDC of the inner foreach loop:
.LBB1_1:
movl $4294967294, 132(%esp)
movl $4294967295, 136(%esp)
movl $0, 140(%esp)
movl $1, 144(%esp)
movl $2, 148(%esp)
movl 20(%esp,%eax,4), %ecx
addl 12(%esp,%eax,4), %ecx
movl %ecx, 20(%esp,%eax,4)
addl 16(%esp,%eax,4), %ecx
movl %ecx, 20(%esp,%eax,4)
addl %ecx, %ecx
movl %ecx, 20(%esp,%eax,4)
addl 24(%esp,%eax,4), %ecx
movl %ecx, 20(%esp,%eax,4)
addl 28(%esp,%eax,4), %ecx
movl %ecx, 20(%esp,%eax,4)
incl %eax
cmpl $26, %eax
The [-2, -1, 0, 1, 2] array is immutable (and the variable 's' of the
foreach isn't by ref), so can't the following initializations of such
array moved out of the inner loop?
movl $4294967294, 132(%esp)
movl $4294967295, 136(%esp)
movl $0, 140(%esp)
movl $1, 144(%esp)
movl $2, 148(%esp)
This is a variant of the same code:
version(Tango) import tango.stdc.stdio: printf;
template Tuple(T...) { alias T Tuple; }
alias Tuple!(-2, -1, 0, 1, 2) move;
void main() {
auto a = new int[30];
for (int x = 2; x < a.length-2; x++)
foreach (s; move)
a[x] += a[x + s];
printf("%d\n", a[5]);
}
The relative asm is much better:
main:
pushl %edi
subl $128, %esp
xorl %eax, %eax
movl $30, %ecx
leal 8(%esp), %edi
rep;stosl
xorl %eax, %eax
.align 16
.LBB1_1:
movl 16(%esp,%eax,4), %ecx
addl 8(%esp,%eax,4), %ecx
movl %ecx, 16(%esp,%eax,4)
addl 12(%esp,%eax,4), %ecx
addl %ecx, %ecx
movl %ecx, 16(%esp,%eax,4)
addl 20(%esp,%eax,4), %ecx
movl %ecx, 16(%esp,%eax,4)
addl 24(%esp,%eax,4), %ecx
movl %ecx, 16(%esp,%eax,4)
incl %eax
cmpl $26, %eax
jne .LBB1_1
movl 28(%esp), %eax
movl %eax, 4(%esp)
movl $.str, (%esp)
call printf
xorl %eax, %eax
addl $128, %esp
popl %edi
ret $8
This is a less reduced version of the code, that I'd like the D (LDC)
compiler to optimize very well:
version(Tango) import tango.stdc.stdio: printf;
struct P {
int x, y;
P opAdd(P o) { return P(x+o.x, y+o.y); }
}
struct Rect {
int lx, ly;
int opIn_r(P p) {
return p.x >= 0 && p.x < lx && p.y >= 0 && p.y < ly;
}
}
void main() {
const int SIZE = 20;
auto m = new int[][](SIZE, SIZE);
auto p = P(10, 10);
// there's another loop for the rows here
for (int i; i < SIZE; i++)
foreach (shift;
[P(-2,-1),P(-1,-2),P(1,-2),P(2,-1),P(2,1),P(1,2),P(-1,2),P(-2,1)])
if (shift + p in Rect(SIZE, SIZE))
printf("OK\n");
}
Eventually the compiler can produce asm similar to (well, this uses an
uint to avoid testing >= 0, I don't think the LDC compiler will soon
learn this trick too):
template Tuple(T...) { alias T Tuple; }
alias Tuple!(-1,-2,-2,-1,+1,+2,+2,+1) movex;
alias Tuple!(-2,-1,+1,+2,+2,+1,-1,-2) movey;
foreach (uint i, sx; movex)
if (x + sx < SIZE && y + movey[i] < SIZE)
printf("OK\n");
If you need more info please ask.
Bye,
bearophile
