RE: repeated recursion with "frozen" arguments

<Chris is cleaning out his inbox>

Valery A.Khamenya wrote (in

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) {
        br label %tailrecurse

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

then: ; preds = %tailrecurse
        ret int

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

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