The Joy of
Programming The Basics of Compiler Optimisers It is fun to write programs that do not work and see how they fail (or work, by chance!). In this column, we use this idea to understand the basics of the optimiser part of a compiler. recently read an interesting article [C++ Report, Vol. 6, no. 3, ‘How to write buggy programs’ by Andrew Koenig], which is about writing incorrect programs. I’ve taken the following (slightly modified) piece of code from that article to illustrate how compiler optimisers work:
I
extern void foo(); int main() { if(0) foo(); }
The foo function is just declared and is not defined in the program. The if condition always evaluates to ‘false’. Should this program link fine or result in a linker error complaining that the definition of foo is not found? That will depend on the compiler. Some smart compilers see that the statement for if(0) will never get executed, and will therefore not generate a call to foo at all—so the linker won’t complain. However, not all compilers do such smart work in default compilation mode and hence we might get a linker error. (Such compilers might detect the ‘unreachable function call’ at higher levels of optimisation!) The following is what I got when I tried a compiler: $ cc foo.c ld: Undefined symbol foo; first referenced in file foo.o $ cc –O foo.c $
Try it and see how your compiler behaves. Sounds interesting, isn’t it? Now, what if we modify the expression in the if condition, as shown: const int val = 0; int main() { if(val) foo();
S.G. GANESH
of a const variable also—enum { val = 0 }. Why? Because enums are just constant values and are only for integral values. How about this statement: const volatile int val = 0;? Yes, first, it is valid to qualify a variable with both const and volatile: the volatile keyword tells the compiler optimiser not to optimise the code involving that variable and the const keyword says that the programmer cannot programmatically change the value of the variable. So, a compiler will not optimise the code and the linker will give an unsat for this program. What if the variable is a plain global variable (int val;)? The program will almost always result in an unsat for foo. Why? Note that the global variables can be modified by any function in the program, which might be available from some other translation unit (independent program file) also. Though it is clear from the control flow of the program that the value of val cannot be changed before the if condition is executed, in general, the optimiser cannot assume anything about the value of val. Global variables put compiler optimisers into much trouble. Globals will require the optimisers to do extensive analysis across translation units, which usually takes too much time. And compiler optimisers are not expected to take unreasonable amounts of compilation time to do runtime speedups; so, typically, optimisers do not perform much optimisation on global variables. But optimisers do perform optimisation for functions across translation units, which is known as Inter-Procedural Optimisation (IPO). IPO can yield significant performance improvements for the program, and it is typically invoked at higher optimisation levels (usually, -O3 level and above). We all know that the compiler invokes the linker for linking programs. But, since only the linker knows the details about all translation units (the .o files) when it attempts to create the final shared library or executable, for IPO, the linker will invoke the compiler (optimiser) again and do the actual linking work later!
}
Yes, the compiler might detect the unreachable code at a higher optimisation level and can remove the call to foo. Even the compiler can optimise it fine for an enum instead
122
DECEMBER 2007
|
LINUX FOR YOU
|
By: S.G. Ganesh is a research engineer in Siemens (Corporate Technology). He has authored a book called ‘Deep C’ (ISBN 81-7656-501-6). You can reach him at
[email protected]
www.linuxforu.com
CMYK