An award is due to LDC.

LDC deserves some kind of gold medal for optimising this to just a couple of mul instructions and the trimmings and no loop at all! Incredible job from LDC. with -O3

uint foo( in uint x ) { if (x ==0) return 0 else return x + foo( x - 1 );}

 Since the answer is n(n+1)/2 I’m not sure why there are two mul instructions.

Golden onion for GDC, does tail-end recursion but then with -O3 -march=native -frelease it generations an evil-looking brew of SIMD and a loop with some unrolling. GDC just doesn’t grok the algorithmic intent like LDC does. I’m assuming that induction variable analysis is the key that gives LDC the superb win?

The two mul instructions will presumably run in parallel due to ILP so actually doesn’t mean much just a bit odd.

On Saturday, 1 August 2020 at 02:48:20 UTC, Cecil Ward wrote:
> An award is due to LDC.
>
> LDC deserves some kind of gold medal for optimising this to just a couple of mul instructions and the trimmings and no loop at all! Incredible job from LDC. with -O3
>
> uint foo( in uint x ) { if (x ==0) return 0 else return x + foo( x - 1 );}
>
>  Since the answer is n(n+1)/2 I’m not sure why there are two mul instructions.
>
> Golden onion for GDC, does tail-end recursion but then with -O3 -march=native -frelease it generations an evil-looking brew of SIMD and a loop with some unrolling. GDC just doesn’t grok the algorithmic intent like LDC does. I’m assuming that induction variable analysis is the key that gives LDC the superb win?

Cheers, but it's LLVM that is doing the optimization, not LDC.
Maybe this gives some insight: https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geometric-sums.html

- Johan