Linux Kernel Architecture

Mauerer app03.tex V1 - 09/04/2008 6:11pm Page 1189

Appendix C: Notes on C

subl $8, %esp

andl $-16, %esp

movl $0, 4(%esp)

movl $.LC0, (%esp)

call printf

movl $1, 4(%esp)

movl $.LC0, (%esp)

call printf

movl $2, 4(%esp)

movl $.LC0, (%esp)

call printf

movl %ebp, %esp

popl %ebp

ret

.Lfe1:

.size main,.Lfe1-main

.ident "GCC: (GNU) 3.2.1"

It should be noted that if this method is used, the size of the program code generated can increase

drastically. The technical difficultyassociated with this method is actuallydecidingwhether to apply

optimization or not. The optimal number of loop passes for which an improvement is achieved depends

not only on the code in the loop body, but also on the processor type. The definition of corresponding

heuristics in the compiler is therefore difficult, although the result they produce is easy to understand.

Common SubexpressionElimination

This optimization feature involves enhancing recurring algebraic expressions in a program. However,

these are no longer static expressions that can be simplified by various manipulations. In this case, the

compiler searches for recurringsubexpressionsin a program section. If the variables used for computa-

tion purposes are unchanged, explicit recomputation can be skipped by reusing the result of the first

computation. In other words, this technique necessitates a search for frequently used or common subex-

pressions, some of which can be eliminated in order to optimize program code. Not surprisingly, the

technique is known ascommon subexpression elimination.^7 The technique is best illustrated by reference to

the following short example:

int p,x,y,z;

scanf("%u", &x);

y = 42;

p = x*y;

if (x > 23) {

z = x*y;

}

else {

z = 61*x*y;

}

The recurringexpressionis obviouslyx*y. An analysis of program execution (usually referred to as pro-

gram flow analysis in technical documents and research papers) reveals that this expression must be

evaluated at least twice. Thescanfstatement reads the value forxfrom the console — that is, users

(^7) To be strictly accurate, there are two different versions of this elimination technique. Which is used depends on whether the goal
of optimization is to shorten execution time or to reduce code size — each option employs different algorithms.