[LLVMdev] repeated recursion with "frozen" arguments

[Vikram S. Adve]

The optimization you are describing is called procedure cloning, where the
body of a procedure is copied and then specialized for particular call
sites.  It is usually driven by interprocedural constant propagation, and
often by profiling to find which cases are frequent enough to make it
worthwhile (here the recursive calls would make both cases -- x=1 and x=2 --
worthwhile).

LLVM would be very well suited to this though we don't have any of the above
capabilities yet.

--Vikram
http://www.cs.uiuc.edu/~vadve


> -----Original Message-----
> From: llvmdev-admin at cs.uiuc.edu
> [mailto:llvmdev-admin at cs.uiuc.edu]On Behalf Of Валерий Хаменя
> Sent: Tuesday, August 26, 2003 9:54 AM
> To: llvmdev at cs.uiuc.edu
> Subject: [LLVMdev] repeated recursion with "frozen" arguments
>
>
> Hi llvm-devels,
>
> 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?
> }
> void main() {
>   rec_func(1, 1000);
>   rec_func(2, 2000);
> }
> //-----------
>
> Guys, don't focus on a stupid mathematics beyond this function :)
> 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 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?).
>
> However, I guess in classical code generation approaches
> argument `x' (like `this' pointer) is always pushed into
> a stack with _every_ call.
>
> 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 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.
>
> So, my questions are:
>
> Q1. should/might the optimization like this be resolved at LLVM layer?
>
> if "yes" then
>
> Q2. is LLVM capable of doing things like that today?
>
> Thanks.
> --
> Valery
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://mail.cs.uiuc.edu/mailman/listinfo/llvmdev
>