[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 
answers already:
"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

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; 
    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,

More information about the llvm-dev mailing list