[LLVMdev] Unrolling power sum calculations into constant time expressions

[Frits van Bommel]

On Tue, Nov 23, 2010 at 12:25 PM, Juliusz Sompolski
<julek at vectorwise.com> wrote:
> A sum \sum_{i=0}^{n} i^k can be derived into a formula which is a
> polynomial of degree k+1, but it is not a trivial derivation (I wouldn't
> do it by hand for k > 2) and I thought that someone hardcoded such a
> case into llvm loop optimizer, and I've been looking through the loop
> analysis and loop passes code, but couldn't find it anywhere...
> And what llvm generates doesn't look like hard-coded formulas for sums
> of powers, because it doesn't do it as optimally as it could, e.g.
> sum20(x) could be expressed as a 21-degree polynomial with constant
> coefficients, so it could be compiled to about 21 muls, 21 adds and 1
> div. Yet, llvm generates about 300 instructions -- but no looping,
> constant time regardless of x!
>
> So I suppose the unrolling of this loop is made by a combination of
> simpler optimizations... which is just... "wow".
> I've been looking through the analyses and passes code and have no clue
> what may be able to make such great optimizations -- I am really
> impressed by the derivation power of this.
> Any clue what can trigger such optimizations (I am totally new to llvm
> code...)?

My guess is something based on Scalar Evolution.