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

> CL> Probably not, at least not in the near future.  At some point I have
had
> CL> thoughts about implementing a tail recursion pass, but without prior
> CL> transformation, this function would not be a candidate.
>
> wait... if you break this C-example at the place as you did then it is
> absolutely not what I have meant. Indeed, sense of my example comes
> iff the top-level call is given, i.e. it might be optimized in
> the context of concrete external call.
Yup, I think I completely missed your point.  :)
> 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.
> CL> In terms of LLVM you could certainly do this.  For example you could
> CL> translate it to use an explicit stack:
> then I have to dig LLVM docs about explicit stack :)
I just mean you have an explicit stack data structure to store just the
elements the recursive call needs.
> CL> Sure, but you still need the 'this' pointer, to know WHICH
valarray you
> CL> are talking about... ?
>
> sure. But what if this `this' was set once for 1mio calls?
> Today I have a lot heavy math function working with two spectra and
> every time I have to think twice before making another member function
> which is invoked in deeper stack frames.
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...
> In other words, just imagine the situation, when for a given object
> really a lot of *its* members function are called without changing
> `this'. Today compilers can't eliminate this _extra_ `this'.
And real
> C++ code has tendency to be slower.
I really am not sure I understand what transformation you are proposing.
Can you elaborate more?  :)

Thanks,

-Chris

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

Hello Chris,

Tuesday, August 26, 2003, 11:02:45 PM, you wrote:
>> 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?
>> }
CL> Probably not, at least not in the near future.  At some point I have had
CL> thoughts about implementing a tail recursion pass, but without prior
CL> transformation, this function would not be a candidate.

wait... if you break this C-example at the place as you did then it is
absolutely not what I have meant. Indeed, sense of my example comes
iff the top-level call is given, i.e. it might be optimized in
the context of concrete external call.

CL> The problem with "lexical closures", at least in this instance,
is
CL> that you have to pass a pointer to the closure around: if you only
CL> have one parameter which can use it, you aren't saving anything.

generally you are right. But only generally :)
In particular, my example showed a feature of typical lexical closure.
>> 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?).
CL> In C++, the 'this' object pointer can actually be thought of as a
CL> closure in some sense already...

this is exactly what I have meant. If the C example I gave might be
optimized with LLVM engine, than `this' and lexical closures might be
boosted as well.
>> But, it is possible to generate individual code implementations
>> for every top-level call of `rec_func' to avoid big number of
>> extra `push'.
CL> In terms of LLVM you could certainly do this.  For example you could
CL> translate it to use an explicit stack:

CL> int rec_func(int x, int y) {
CL>   if(y<0) return x;
CL>   return y + rec_func(x, y-1); // should we really push x?
CL> }

then I have to dig LLVM docs about explicit stack :)

CL> Or you could just perform an aggressive dead code elimination pass
CL> which would realize that this function returns the same value for
CL> X no matter what the value of Y is.

you misunderstood this function a bit, but it is not important, dead
code elimination was out of my scope.
>> In terms of C++: there should be a possibility to regenerate
>> non-static member functions for a given instantiated object
>> of the classes where performance is critical, e.g. for classes
>> like valarray.
CL> Sure, but you still need the 'this' pointer, to know WHICH
valarray you
CL> are talking about... ?

sure. But what if this `this' was set once for 1mio calls?
Today I have a lot heavy math function working with two spectra and
every time I have to think twice before making another member function
which is invoked in deeper stack frames.

In other words, just imagine the situation, when for a given object
really a lot of *its* members function are called without changing
`this'. Today compilers can't eliminate this _extra_ `this'. And
real
C++ code has tendency to be slower.

I'd say it is not just a problem of current compilers. It is problem
of ultimate static compilation. In cases when `this' comes in run-time
even a super-smart static compilers can't recompile a function with
"built-in" `this'.
>> So, my questions are:
>> Q1. should/might the optimization like this be resolved at LLVM layer?
CL> Yes, LLVM is designed for spiffy optimizations like this.  :)

nicccce.
>> if "yes" then
>> Q2. is LLVM capable of doing things like that today?
CL> Nope, not yet.  Contributions are always appreciated though.  :)

now I have to prepare for sleeping, that's for sure. Probably this
nice patch from me doesn't come today :))

Have a nice day!

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

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