Aaron Garth Enright is a Ph.D. student at the University of Massachusetts Lowell. His current research interests include high performance compilation techniques, massively parallel systems, and object-oriented languages. He can be reached at aenright@cs.uml.edu.
Dr. Linda M Wilkens is an Assistant Professor of Computer Science at Bridgewater State College. Her research interests include object-oriented languages and software engineering. Her e-mail address is lwilkens@bridgew.edu.
For several years, it has been considered bad style to use goto statements in programs. Use of the goto statement is generally discouraged because it is considered "unstructured." Edsger Dijkstra's classic article, "Goto statement considered harmful," [1] presents gotos — or any "arbitrary" control transfer statements — as constructs that make code difficult to read and understand. Although this was only his view of gotos, many computing professionals agreed, and, over the next 20 years, this view had a profound impact on software engineering practices. In a large percentage of software engineering institutions, goto statements are considered the ultimate evil.
In an age when programmers strive to get the most out of optimizing compilers, gotos present an even greater threat: they tend to thwart certain compiler optimizations. We performed a study of this phenomenon, and found that many compilers which perform loop optimizations on do-while, for, and while loops fail to do so when equivalent loops are written using goto statements. We compared nine popular compilers' performance in optimizing a simple program. Out of the nine, only the Microsoft C/C++ compiler optimizes loops formed by goto statements.
In each case, we used the maximum level of optimization described in the compiler's documentation. The complete list of compiler switches, and a more detailed description of the experiment are given in our original technical report [2].
The test program is shown below. We also ran three equivalent test programs, replacing goto and associated label with for, while, and do-while structures. They all perform an equivalent computation. The printed results for all four programs are either "7000 7000000" for 32-bit processors or "7000 -12352" on 16-bit processors.
#include <stdio.h> void main(){ int i=0,a=0,n; loop: if(i<1000){ a+=7; n=1000; i++; goto loop; } n=n*a; printf("%d %d\n",a,n); }The optimizations we expected to see were code motion, to move the n=1000; statement outside the loop, and induction analysis to reduce the loop to a=7000; followed by a removal of the loop body. (For a brief description of these techniques, see the sidebar.) (We needed to use a printf or some statement that actually uses a and n, otherwise the more aggressive compilers would have removed them from the program entirely.) The results are summarized in Table 1.We obtained our results by studying the generated assembly language from each compiler. We assume that the assembly language which the compiler generated was the actual assembly language used to generate object code. However, the VAX C Compiler documentation claims to utilize an "object code optimizer." This implies that the generated assembly language may not reflect the optimizations being performed. We still include the results from the VAX test, but note they may be misleading.
Conclusion
We chose nine compilers in widespread use today; we do not claim that our list is exhaustive. Out of nine widely-used compilers, only one optimized loops formed out of gotos. Rather than criticize compilers (listed here or not) that fail to optimize goto loops, we think it makes more sense to say, "here's another reason to stay away from gotos."
References
[1] E. Dijkstra. "Goto statement considered harmful." Communications of the ACM, 11(3), March: 1968.[2] A. Enright and L. Wilkens. A Comparative Study of How C Compilers Optimize Loops Formed by goto Statements. University of Massachusetts Lowell Dept. of Computer Science Technical Report R-95-026. August: 1995.
[3] A. Aho, R. Sethi, and J. Ullman. Compilers: Principles, Techniques, and Tools (Addison-Wesley, 1986).
[4] J. Hennessy and D. Patterson. Computer Architecture: A Quantitative Approach (Morgan Kaufmann Publishers, Inc., 1990).