[LLVMdev] RE: repeated recursion with "frozen" arguments

[Chris Lattner]

<Chris is cleaning out his inbox>

Valery A.Khamenya wrote (in
http://mail.cs.uiuc.edu/pipermail/llvmdev/2003-August/000455.html):

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

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

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

Hi Valery,

Since we originally had this discussion, and I got thoroughly confused,
LLVM has moved on.  The answer is now _yes_ on both points.  If you
compile the function above with the 1.1 (or later) compiler, you should
get something like this:

int %rec_func(int %x, int %y) {
entry:
        br label %tailrecurse

tailrecurse:            ; preds = %entry, %endif
        %cann-indvar = phi uint [ 0, %entry ], [ %next-indvar, %endif ]         ; <uint> [#uses=2]
        %accumulator.tr = phi int [ %x, %entry ], [ %tmp.9, %endif ]            ; <int> [#uses=2]
        %cann-indvar = cast uint %cann-indvar to int            ; <int> [#uses=1]
        %y.tr-scale = mul int %cann-indvar, -1          ; <int> [#uses=1]
        %y.tr = add int %y.tr-scale, %y         ; <int> [#uses=2]
        %next-indvar = add uint %cann-indvar, 1         ; <uint> [#uses=1]
        %tmp.1 = setlt int %y.tr, 0             ; <bool> [#uses=1]
        br bool %tmp.1, label %then, label %endif

then:           ; preds = %tailrecurse
        ret int %accumulator.tr

endif:          ; preds = %tailrecurse
        %tmp.9 = add int %accumulator.tr, %y.tr         ; <int> [#uses=1]
        br label %tailrecurse
}

... Note that this consumes _no_ stack space, because there are no
recursive calls.  :)

-Chris

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