Redundancy elimination is a well-known technique to optimize code by reusing the result of previously computed values. Some of the redundancy elimination techniques commonly used in optimizing compilers are common-subexpression elimination, loop-invariant code motion, and partial-redundancy elimination[10]. However, all these techniques are intraprocedural in that they do not consider effects of function calls. Function calls are treated as always necessary. If there is a way to gather information about whether a function call might be redundant, then, together with standard data-flow analysis techniques, the information allows a compiler to extend redundancy elimination by removing redundant function calls.
An inherent prerequisite of knowing whether a function call is redundant is to know whether the function call generates any side-effects. This problem, the problem of interprocedural side-effect analysis, has been investigated for many years, so this is a mature area of research. In fact, there are a few algorithms that have been invented to solve the problem of interprocedural side-effect analysis ([2], [1], [11], [4], [3]). These algorithms invariably require the construction of the call graph of the program. It has been shown that, with the presence of pointers and procedure variables, which can be prevalent in a typical C program, the construction of a call graph is PSPACE-hard[13]. Furthermore, Myers showed that a certain type of side-effect analysis (flow-sensitive side-effect analysis) is co-NP-complete[11]. However, in a typical compilation of a program, the complexity of the compilation stages has to be tractable. And although some of the existing algorithms are already proven to be tractable, those algorithms are designed to compute more information than what we need.
This paper describes a stripped-down interprocedural side-effect analysis method. The contribution of this method is that it uses the side-effect information to determine whether a function might be reusable, i.e. multiple calls to this function with the same parameters will yield the same results and generate no side effects. The method does not derive from any of the existing algorithms for interprocedural side-effect analysis. Because the tractability of the method is a requirement of the method, it might be the case that it is more conservative compared to the ideal side-effect analysis, and even most of the existing algorithms. However, as will be shown later in the paper, this does not hinder the method to gather useful information to decide whether function calls might be redundant.
The other half of the picture is to use the information from the analysis to actually optimize redundant function calls. It turns out that the solution to this problem has been found and implemented in a widely used compiler. The GNU Compiler Collection (GCC)[5] accepts an extension to the C language where functions known to generate no or minimal side effects can be annotated as such. Given such an annotation, the compiler can actually determine whether a call to a certain function is redundant. However, GCC relies on the programmer to manually annotate the functions. Since we do not wish to reinvent the wheel, we focus on providing the technique to automatically annotate functions with no or minimal side effects while relying on GCC to do the optimization based on our annotations.