[LLVMdev] Hoisting constant arguments from recursive functions

[Jon Harrop]

On Wednesday 28 January 2009 07:28:38 Chris Lattner wrote:
> On Jan 25, 2009, at 12:21 AM, Jon Harrop wrote:
> > My question is: will LLVM optimize this back into a function
> > containing a loop
> > that runs inside a single stack frame that contains the constants
> > "a" and "x"
> > or should my compiler perform this rewrite itself?
>
> The easiest way to answer this is to write the moral equivalent in C,
> and see if it happens for it.

Ok:

Firstly, LLVM optimizes a recursive C function:

  int f(int c, int n) { return (n<0 ? n : f(c, n-c*c)); }

into tail recursion using a branch instead of a tail call. I assumed it would 
preserve stack consumption.

Secondly, LLVM hoists the constant from the resulting loop and unrolls it 
eight times.

So LLVM is already doing exactly the optimizations that I need.

However, the equivalent imperative loop is even better optimized:

  int g(int c, int n) {
    while (n>=0) {
      int c2 = c*c;
      n -= c2;
    }
    return n;
  }

Specifically, LLVM does algorithmic optimizations and produces code that runs 
instantaneously.

> > Also, would any simple rearrangements help LLVM, such as putting the
> > constant
> > function arguments to the back of the argument list?
>
> I don't think that should matter.  If there are cases that LLVM could
> catch but doesn't (either in LLVM IR or in C code), please file a
> bugzilla.

I will if I see any. I've noticed an unwanted anomaly within SciMark2 which 
I'll post about separately...

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e