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

"Валерий Хаменя" khamenya at mail.ru
Wed Aug 27 03:41:02 PDT 2003

```Hi LLVM-devels,

> Yup, I think I completely missed your point.  :)

funny, that if even so, I got two similar and concrete
"it is suitable for LLVM, though not implemented yet"
:)

> > generally you are right. But only generally :)
> > In particular, my example showed a feature of typical lexical closure.
>
> Can you explain more about what you mean.  I don't think I understand.

I will try. But then perhaps I should separte statements in
order to know where I was unclear.

S1. Example just shows simple phenomenon when every recursive
(i.e. not from main) call of function `rec_func' does
*not* change variable `x' anymore. It means, that every
recursive call just makes extra/redundant copy of the
`x'.

S2. Theoretically this redundant copy might be eliminated.
The idea is simple: at first (i.e. non-recursive) call
generate `rec_func' code which does not push `x' on
the stack because it will remain the same from the
first non-recursive call. For example initial
non-recursive call `rec_func(1, 1000)' should be
instantiated as:

int rec_func(int y) {
if(y<0) return 1;
return y + rec_func(y-1);
}

so, this instantiation of function `rec_func' doesn't
need to push `x' on stack anymore.

S3. This example is just a C-analogy of how pushing `this'
onto stack might be eliminated. Just think of `x' as
it would be `this', and think of `rec_func' as it
would be a non-static member function. For example:

struct Math {

Math(int _y) : y(_y) {}

int rec_func() {
if(y<0) return 42;
y--;
return y
+ rec_func(); // here `this' will be the same
// up to destruction of the object
}

};

void main() {
Math m1(1000), m2(2000);

m1.rec_func(); // initial `this' is supplied here and will
// be the same for evry next call of rec_func
// from this object

m2.rec_func(); // as above,
// initial `this' is supplied here and will
// remain the same for evry next call of
// rec_func from this object
}

S4. in optimization of C-example (see S2.) we just made a
lexical closure in respet to variable `x'. (And by analogy,
in C++ example we could consider similar optimization which
in a sense is a lexical closure in respect to `this')

Now, Chris, please locate the point where I am unclear :)

> varray's do not have any recursive function calls, and the
> methods tend to be simple.  For that reason, they are
> typically all inlined, eliminating
> the parameter passing completely...

you are right.

However, my classes for spectra analysis I deal with should be as
fast as valarray is, but they may not be so oversimplified
as valarray... I have to break my fat non-static member functions
into smaller pieces and those simple pieces are called a lot
of times with the same `this'. So, the `valarray'-like classes
in real life are not always that nice.

> I really am not sure I understand what transformation you are proposing.
> Can you elaborate more?  :)

perhaps, I showed the point above. It looks like
Vikram S. Adve got my point already, and if he is near
you then probably he could reformulate my thoughts in
correct English just orally without typing :)

Kind regards,
---
Valery

```