llvm dev - Jan 2009 - [LLVMdev] Hoisting constant arguments from recursive functions

I am just considering various different designs for the code emitted by a HLVM 
and one alluring approach is to make all local variables immutable and 
replace loops with (tail) recursive functions. This makes it much easier to 
reason about injected code such as GC checks. However, I am concerned about 
the performance of the generated code.

Specifically, this is likely to result in small recursive functions that 
accept a large number of arguments, many of which have values that remain the 
same from one application/iteration to the next.

For example, a function to fill an array might become:

  let rec fill a i x     if i < length a then
      a.(i) <- x
      fill a (i + 1) x

where "a" and "x" have the same value from one call to the
next and only the
loop variable "i" changes.

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?

Also, would any simple rearrangements help LLVM, such as putting the constant 
function arguments to the back of the argument list?

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

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.
> 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.

-Chris

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