2

Below is a snippet that gets programmatically generated for a toy programming language, actual code is different but following shows what it does when executed,



class Base{ };

Base b;

class Derived{
      int fibo(int i){
        if(i SMALLER 2)
          return 1;
        else
          return (Derived)b.fibo(i-1) + (Derived)b.fibo(i-2);
      }
};

//then somewhere in main

b = new Derived();
int i = (Derived)b.fibo(10);

My question is will GCC consider this for tail call elimination?

EDIT: Turns out my my view of TOC is a bit flawed, so in a different case a different function with a single return positioned at the tail, would that be considered for optimization? The reason I ask is that there bunch of scheme to c compilers and AFAIK scheme mandates TOC so there must be a way to force this?

Hamza Yerlikaya
  • 49,047
  • 44
  • 147
  • 241

1 Answers1

6

How can it eliminate a tail call if there is no tail call? It's only a tail call if it's the very last thing done before a return - but you're calling it twice, storing the results somewhere, add them and then you return. So: Generally, no.

If the method is not virtual (i.e. GCC can be sure there's only one implementation of fibo that's called), it may still be able to optimize it (at least it worked for one user with a free function), but you'll have to test it and propably shouldn't rely on it. Turning recursion into tail recursion is generally the programmer's job.

Community
  • 1
  • 1
  • 1
    There are some languages that require in specification the compiler/interpreter does tail-call elimination. It is however still programmer's job to ensure it is a tail-call and this one indeed is not. – Jan Hudec May 10 '11 at 12:29
  • @Jan: Yes. I just realized the last sentence is nonsense for that very reason. Changed it to what I really meant. –  May 10 '11 at 12:32
  • @delnan, assuming a different function with a single return positioned at the tail? or more specifically how can i hint gcc that certain calls should be optimized? – Hamza Yerlikaya May 10 '11 at 12:39
  • Eliminating tail recursion is easy if the tail call is there (and detecting *that* is equally easy), so I'd expect most modern compilers to do it. You'd have to try it for your concrete code to be sure, but I for one would to assume GCC will eliminate tail calls. All of this assuming it's not a virtual call. Re hints: There is `__attribute__` etc. but you rarely need to do this for this kind of optimization (they're for things like packing structures, declaring functions as pure or stating that a pointer won't be null). –  May 10 '11 at 12:47
  • @delnan, So for my case it won't do due to Derived derived from a function interface and fibo is actually a virtual function called 'call' – Hamza Yerlikaya May 10 '11 at 13:09
  • Is there flag, or what have you, that enables one to detect at compile time if the compiler was able to make the function tail recursive. So, I decorate the function with, say, an tail recursive attribute and if the compiler fails to optimize it, it flags and error and stops. – Mohamed Bana May 10 '11 at 21:51
  • @bruce: None that I'm aware of, and neither google nor Ctrl+F in the GCC documentation helped. Perhaps tail recursion isn't used so frequently that there was significant demand for such an assertion. –  May 11 '11 at 15:18