Hello,
In lib/Analysis/InlineCost.cpp, inlining of recursive functions is
disabled because it is
like loop unrolling. But
- I could not find a way to have loop unrolling do the job
- In the context of functionnal languages (I am implementing one), inlining
small recursive functions is often a great gain
My question is what is the cleanest and simplest way to inline small
recursive functions ?
Just commenting out this test (which is probably not correct)
gives on fibonacci (C code attached) on my intel dual core old mac :
clang -O3 with inlining 0.16s
gcc -O3 0.50s
clang -O3 without inlining 1.20s
fibonacci is really useless but if you look at OCaml or GHC libraries,
you will find plenty of very small recursive functions on lists for
instance (map, fold_left, ...).
And the figure here should apply there to ... with probably a less
dramatic effect in general.
Best regards,
Christophe
---- C code ----
#include<stdio.h>
long long fib(long long n) {
if (n == 0 || n == 1) return 1;
else return (fib (n - 2) + fib (n - 1));
}
void test(long long f (long long), long long n, long long m) {
long long r = f(n);
printf("%lld ", r);
if (n < m) test (f,n+1, m);
}
int main() {
test(&fib,0,37);
printf("\n");
return 0;
}
On Oct 4, 2011, at 4:36 PM, Christophe Raffalli wrote:> > Hello, > > In lib/Analysis/InlineCost.cpp, inlining of recursive functions is > disabled because it is > like loop unrolling. But > > - I could not find a way to have loop unrolling do the job > - In the context of functionnal languages (I am implementing one), inlining > small recursive functions is often a great gain > > My question is what is the cleanest and simplest way to inline small > recursive functions ? > Just commenting out this test (which is probably not correct) > gives on fibonacci (C code attached) on my intel dual core old mac : > > clang -O3 with inlining 0.16s > gcc -O3 0.50s > clang -O3 without inlining 1.20s > > fibonacci is really useless but if you look at OCaml or GHC libraries, > you will find plenty of very small recursive functions on lists for > instance (map, fold_left, ...). > And the figure here should apply there to ... with probably a less > dramatic effect in general.It could, and having it turn on when you turn on loop unrolling or some such might not be a bad idea. A lot of algorithms are recursive and the code bloat from that sort of change could be significant. Largely I'd want to see a wider range of tests before we can look at turning it on in general. I haven't done them and can't recall when anyone else did either. Now, if code bloat isn't an issue we could turn it on - maybe at O3 or something. -eric
> > Now, if code bloat isn't an issue we could turn it on - maybe at O3 or something.An option like -inline-rec (on by default at O3 if the option for limiting code size are not set ?) might be good. Then, one might want to unroll a recursive definition more than once (for very small functions). And I am not sure this is done if we just authorize inlining in the current code ... Christophe> > -eric-- Christophe Raffalli Universite de Savoie Batiment Le Chablais, bureau 21 73376 Le Bourget-du-Lac Cedex tel: (33) 4 79 75 81 03 fax: (33) 4 79 75 87 42 mail: Christophe.Raffalli at univ-savoie.fr www: http://www.lama.univ-savoie.fr/~RAFFALLI --------------------------------------------- IMPORTANT: this mail is signed using PGP/MIME At least Enigmail/Mozilla, mutt or evolution can check this signature. The public key is stored on www.keyserver.net --------------------------------------------- -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 262 bytes Desc: OpenPGP digital signature URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20111010/5d0fd5cb/attachment.sig>