[LLVMdev] repeated recursion with =?koi8-r?Q?=22?=frozen=?koi8-r?Q?=22=20?=arguments

[Chris Lattner]

> there is a very simple using case concerning LLVM and I am wondering
> whether it might be optimized at LLVM layer:
>
> //-----------
> int rec_func(int x, int y) {
>   if(y<0) return x;
>   return y + rec_func(x, y-1); // should we really push x?
> }

Probably not, at least not in the near future.  At some point I have had
thoughts about implementing a tail recursion pass, but without prior
transformation, this function would not be a candidate.

> Please focus your attention at the fact, that argument `x'
> is once supplied at the top level calls in `main' and
> never changed anymore from within `rec_func' function.
> This example is just quite close to a "lexical closures" specifics.

The problem with "lexical closures", at least in this instance, is that
you have to pass a pointer to the closure around: if you only have one
parameter which can use it, you aren't saving anything.

> The similar things we have when we pass `this' pointer
> to non-static member functions in C++ (why should we
> pass `this' pointer always if it was not changed?).

In C++, the 'this' object pointer can actually be thought of as a closure
in some sense already...

> However, I guess in classical code generation approaches
> argument `x' (like `this' pointer) is always pushed into
> a stack with _every_ call.

Absolutely.

> But, it is possible to generate individual code implementations
> for every top-level call of `rec_func' to avoid big number of
> extra `push'.

In terms of LLVM you could certainly do this.  For example you could
translate it to use an explicit stack:

int rec_func(int x, int y) {
  if(y<0) return x;
  return y + rec_func(x, y-1); // should we really push x?
}

Or you could just perform an aggressive dead code elimination pass which
would realize that this function returns the same value for X no matter
what the value of Y is.  There are other transformations that you can do
to work on this kind of thing, the functional language community has a lot
of ways to deal with this.

> In terms of C++: there should be a possibility to regenerate
> non-static member functions for a given instantiated object
> of the classes where performance is critical, e.g. for classes
> like valarray.

Sure, but you still need the 'this' pointer, to know WHICH valarray you
are talking about... ?

> So, my questions are:
> Q1. should/might the optimization like this be resolved at LLVM layer?

Yes, LLVM is designed for spiffy optimizations like this.  :)

> if "yes" then
> Q2. is LLVM capable of doing things like that today?

Nope, not yet.  Contributions are always appreciated though.  :)

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/