[LLVMdev] repeated recursion with "frozen" arguments

[Valery A.Khamenya]

Hello Chris,

Tuesday, August 26, 2003, 11:02:45 PM, you wrote:

>> 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?
>> }

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

wait... if you break this C-example at the place as you did then it is
absolutely not what I have meant. Indeed, sense of my example comes
iff the top-level call is given, i.e. it might be optimized in
the context of concrete external call.

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

generally you are right. But only generally :)
In particular, my example showed a feature of typical lexical closure.

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

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

this is exactly what I have meant. If the C example I gave might be
optimized with LLVM engine, than `this' and lexical closures might be
boosted as well.

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

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

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

then I have to dig LLVM docs about explicit stack :)

CL> Or you could just perform an aggressive dead code elimination pass
CL> which would realize that this function returns the same value for
CL> X no matter what the value of Y is.

you misunderstood this function a bit, but it is not important, dead
code elimination was out of my scope.

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

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

sure. But what if this `this' was set once for 1mio calls?
Today I have a lot heavy math function working with two spectra and
every time I have to think twice before making another member function
which is invoked in deeper stack frames.

In other words, just imagine the situation, when for a given object
really a lot of *its* members function are called without changing
`this'. Today compilers can't eliminate this _extra_ `this'. And real
C++ code has tendency to be slower.

I'd say it is not just a problem of current compilers. It is problem
of ultimate static compilation. In cases when `this' comes in run-time
even a super-smart static compilers can't recompile a function with
"built-in" `this'.

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

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

nicccce.

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

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

now I have to prepare for sleeping, that's for sure. Probably this
nice patch from me doesn't come today :))

Have a nice day!

-- 
Best regards,
Valery A.Khamenya                       mailto:khamenya at mail.ru
Local Time: 23:01