[LLVMdev] Does LLVM optimize recursive call?

Preston Briggs preston.briggs at gmail.com
Wed Oct 3 10:28:57 PDT 2012

On Wed, Oct 3, 2012 at 10:15 AM, Matthieu Moy
<Matthieu.Moy at grenoble-inp.fr> wrote:
> Preston Briggs <preston.briggs at gmail.com> writes:
>> Think about costs asymptotically; that's what matters. Calls and
>> returns require constant time, just like addition and multiplication.
> Constant time, but not necessarily constant memory.
> Deep recursion will blow up your stack (AKA "segmentation fault" :-( )
> if the compiler could not optimize it (tail recursion optimization).

Only if the recursion is very deep. In practice, a recursive descent
parser isn't going to run out of stack space, nor will a quicksort or
binary-tree walker,

You're distracting this man from his job of learning how to program.

Yes, it's a mistake to have a set of mutually recursive routines that
chew up all your stack space; but it's a mistake to reply on a
compiler optimization to avoid such problems. Write an explicit loop
if it's a possibility.


More information about the llvm-dev mailing list