llvm dev - Oct 2011 - [LLVMdev] inlining of recursive functions

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>