llvm dev - Aug 2003 - [LLVMdev] repeated recursion with "frozen" arguments

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

On Wed, 27 Aug 2003, [koi8-r] "������� ������" 
wrote:
> funny, that if even so, I got two similar and concrete
> answers already:
> "it is suitable for LLVM, though not implemented yet"
> :)
:)
> 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:
Ok, Vikram is right.  This is known as procedure cloning, where the
compiler makes a specialized version of the function for an invocation
with constant arguments (thus making it so you don't have to pass the
arguments).
> 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:
Ok, I see why I was confused here.  The problem is that a particular
"this" is not, in general, a compile time constant: if the object is
allocated dynamically on the stack or heap, the static compiler doesn't
know which value to specialize with.  Obviously a dynamic compiler could
though...
> 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')
Ok, I understand now.  When I think of lexical closures, I think if a
piece of memory which holds the variables used by a block of code, coupled
with a generic version of the code.  Converting a "this" pointer to
use
this style of closure means that you have to add a closure pointer  :)

So, in sum, yes, LLVM is a good representation to do this kind of thing
on.  :)

-Chris

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

Hello Chris,

Wednesday, August 27, 2003, 4:27:21 PM, you wrote:

CL> Ok, Vikram is right.  This is known as procedure cloning, where the
CL> compiler makes a specialized version of the function for an invocation
CL> with constant arguments (thus making it so you don't have to pass the
CL> arguments).

just one remark: it would be better to say "known arguments" instead
of "constant arguments" :)

CL> Ok, I see why I was confused here.  The problem is that a particular
CL> "this" is not, in general, a compile time constant: if the
object is
CL> allocated dynamically on the stack or heap, the static compiler
doesn't
CL> know which value to specialize with.  Obviously a dynamic compiler could
CL> though...

exactly :)

CL> Ok, I understand now.  When I think of lexical closures, I think if a
CL> piece of memory which holds the variables used by a block of code,
coupled
CL> with a generic version of the code.  Converting a "this"
pointer to use
CL> this style of closure means that you have to add a closure pointer  :)

:)

CL> So, in sum, yes, LLVM is a good representation to do this kind of thing
CL> on.  :)

is LLVM a kind of paradise promises?..
I should definitely check this out :)

-- 
Best regards,
Valery A.Khamenya                       mailto:khamenya at mail.ru
Local Time: 19:36