gcc-does-no-flow-analysis


(from the Stalin 0.10 manpage)

Stalin now generates code that is properly tail recursive, by default, in all but the rarest of circumstances. And it can be coerced into generating properly tail-recursive code in all circumstances by appropriate options. Some tail-recursive calls, those where the call site is in-lined in the target, are translated as C goto statements and always result in properly tail-recursive code. The rest are translated as C function calls in tail position. This relies on the C compiler to perform tail-call optimization. gcc(1) versions 2.96 and 3.0.2 (and perhaps other versions) perform tail-call optimization on IA32 (and perhaps other architectures) when -foptimize-sibling-calls is specified. (-O2 implies -foptimize-sibling-calls.) gcc(1) only performs tail-call optimization on IA32 in certain circumstances.

First, the target and the call site must have compatible signatures. To guarantee compatible signatures, Stalin passes parame­ ters to C functions that are part of tail-recursive loops in global variables.

Second, the target must not be declared __attribute__ ((noreturn)). Thus Stalin will not generate a __attribute__ ((noreturn)) declaration for a function that is part of a tail-recursive loop even if Stalin knows that it never returns.

Third, the function containing the call site cannot call alloca(3). gcc(1) does no flow analysis. Any call to alloca(3) in the function containing the call site, no matter whether the allocated data escapes, will disable tail-call optimization.

Thus Stalin disables stack allocation of data in any procedure in-lined in a procedure that is part of a tail-recursive loop. Finally, the call site cannot contain a reentrant region because reentrant regions are freed upon procedure exit and a tail call would require an intervening region reclamation. Thus Stalin disables allocation of data on a reentrant region in any proce­ dure that is part of a tail-recursive loop. Disabling these optimizations incurs a cost for the benefit of achieving tail-call optimization.

If your C compiler does not perform tail-call optimization then you may wish not to pay the cost. The -no-tail-call-optimization option causes Stalin not to take these above four measures to generate code on which gcc(1) would perform tail-call optimization. Even when specifying this option, Stalin still translates calls, where the call site is in-lined in the target, as C goto statements. There are three rare occasions that can still foil proper tail recursion.

First, if you specify -dC you may force Stalin to use stack or region allocation even in a tail-call cycle. You can avoid this by not specifying -dC.

Second, gcc(1) will not perform tail-call optimization when the function containing the call site applies unary & to a local variable. gcc(1) does no flow analysis. Any application of unary & to a local variable in the function containing the call site, no matter whether the pointer escapes, will disable tail-call optimization. Stalin can generate such uses of unary & when you specify -de or don't specify -df. You can avoid such cases by specifying -df and not specifying -de.

Finally, gcc(1) will not perform tail-call optimization when the function containing the call site calls setjmp(3). gcc(1) does no flow analysis. Any call to setjmp(3) in the func­ tion containing the call site, no matter whether the jmp_buf escapes, will disable tail-call optimization. Stalin translates certain calls to call-with-current-continuation as calls to setjmp(3). You can force Stalin not to do so by specifying -fully-convert-to-CPS. Stalin will generate a warning in the first and third cases, namely, when tail-call optimization is foiled by reentrant-region allocation or calls to alloca(3) or setjmp(3). So you can hold off specifying -fully-convert-to-CPS or refraining from specifying -dC until you see such warnings. No such warning is generated, how­ ever, when uses of unary & foil tail-call optimization.

So you might want to always specify -df and refrain from specifying -de if you desire your programs to be properly tail recursive.

Everything clear now?


The above is not true for newer gcc versions. Particularly, the "GCC does no flow analysis". In fact, it sounds a lot like the author just has something against GCC, because GCC has done this type of flow analysis for many years now.

Of course, GCC, as any compiler, is conservative when performing data-flow analysis. This is not equal to "no flow analysis".

Jorgen-Schäfer

The question is not whether gcc does any kind of flow analysis, but about some very specific ones:

But yes, the phrasing "gcc(1) does no flow analysis" is not true. I guess it was used as a catchy phrase.


Momchil Velikov

These are incorrect questions, because no compiler will always be able to answer whether or not pointers escape. The correct ones are:

"Stalin now generates code that is properly tail recursive, by default, in all but the rarest of circumstances."

Shall we say then "Stalin does not generate properly tail recursive code."



category-humor