[cfe-dev] [LLVMdev] Does LLVM optimize recursive call?

[John McCall]

On Oct 3, 2012, at 12:22 AM, Journeyer J. Joh wrote:
> Hi David Blaikie and others who might be interested on this
> 
> Thank you very much!
> 
> #1. Then I'd like to know, to make Clang/LLVM optimize a recursion
> into an iteration, how a recursion has to be implemented with any
> compiler option? (if the language is C/C++)

Simple recursive algorithms are likely to be optimized to use iteration
even at -O1.  You can verify this with, for example:

struct A {
  unsigned value;
  struct A *next;
};

unsigned count(struct A *a) {
  if (!a) return 0;
  return a->value + count(a->next);
}

Note that this algorithm was not originally iterative;  changing it
to use accumulation reassociates the arithmetic and would not
be legal for, say, floating point.

> Clang uses recursions, especially it uses recursive decent and
> operator-precedence parser.
> #2. I wonder if this kind of recursion is optimized to a iteration.

No, and it might not be an optimization even if we did it.  The
recursion vs. iteration performance tradeoffs are far more complex
than "we need to use iterations [rather] than recursions".

Transforming recursion to iteration can be critical, e.g. to avoid blowing
out the stack.  It can also be good for performance, e.g. when an
algorithm can be easily adapted to use constant space and would
otherwise spend a high proportion of its time in call overhead.  But
the general recursion-to-iteration transformation basically involves
emulating the call stack on the heap and often makes performance
worse, not better.

If your teachers are really making this sort of superficial generalization,
they're doing you a disservice.

John.