CODEWITHSUNDEEP
cgccrecursionstatic
paradigmatic
paradigmatic

Reputation: 40461

Recursion and `static` keyword with GCC

I read recently several recursive functions which were declared static.

Does adding static in front of functions declarations help GCC to optimize tail-recursive function? Is this mandatory to get optimizations?

Upvotes: 2

Views: 328

Answers (3)

AnT stands with Russia
AnT stands with Russia

Reputation: 320481

One effect static (i.e. internal linkage) has on a function is that it tells the compiler that all possible use cases for the direct calls to given function are localized in the current translation unit. This might indeed have effect on certain optimizations. For example, if the compiler decided to inline all calls to given function in a translation unit (and no address of that function is ever taken), it immediately knows that the function needs no standalone body. Or, for another example, if the function is always called with 1 as an argument, then technically this argument can be eliminated entirely. And so on.

With externally-linked functions such optimizations are also possible, but require global knowledge about the entire program (which is why they are often referred to as global optimizations). With internally-linked functions all these possibilities are open within one translation unit.

However, for such optimizations as tail recursion elimination it should not matter.

Upvotes: 1

hmakholm left over Monica
hmakholm left over Monica

Reputation: 23332

I don't see any reason why a function being static should help the compiler optimize recursive calls in particular.

Immediately, it sounds more likely that the recursive functions you have seen were simply internal to the compilation unit. A recursive function will often need a richer interface than one wants to expose to the rest of the program -- for example there might be extra parameters that are only used by the recursive calls, or the return value from a general call may need to be adjusted in order to fit with the abstraction one wants to present to the rest of the code. Therefore it is usual to write a wrapper function that sets default values for the extra parameters and in general adjusts the interface of the recursive function to something nice that makes sense externally.

Now since the recursive function is only called by itself and the wrapper function, it is natural to declare it static -- not because of the recursion itself, but in order to prevent polluting the global namespace with it. It is also possible that the compiler can use more efficient calling conventions (adapted to that particular function body) for static functions, because it knows all of the call sites and does not have to follow an ABI that will let separately compiled code call it.

Upvotes: 8

Carl Norum
Carl Norum

Reputation: 224944

No, static has nothing to do with any recursion optimizations. When a function is declared static, it gets internal linkage, so that it can't be called/used except from other functions in the same translation unit.

Upvotes: 3

Related Questions