Next: Implementation
Up: ENABLING OPTIMIZATION
Previous: ENABLING OPTIMIZATION
Our optimization replaces each dynamic
function call with a switch statement and a set of static function calls.
Since existing compilers can analyze static functions calls, the compiler
is in a better position to perform other optimizations after our
optimization is applied. The replacement has the following steps:
Step 1.
Compute the class hierarchy to determine the set of functions that each virtual
function call may invoke.
Step 2.
Replace each virtual function call with a switch statement and
a set of static function calls.
The switch statement uses the type of the receiving object to
determine which function is called.
The set of static calls used in the switch statement is determined
by the following three rules:
Rule 1.
Based on the declared type of a pointer in C++, the set of
functions that may be invoked by a virtual function call-site is limited. For
example, consider a virtual function call to function fmade though a
pointer to class C. This call may result only in a call to the version
of fdeclared in class Cor any class derived from C.
Rule 2.
Classes that call the same virtual function are consolidated.
For example, if Band Cboth derive from A, and Band Cdo not implement their own version
of A::f, then A, B, and Call call A::f. Putting all three classes into one branch of the case
statement shortens the code, and makes the compiler's jump table
smaller.
Rule 3.
Any class that contains pure virtual functions can be eliminated
from the switch statement.
C++ forbids the creation of objects of a class that contains a
pure virtual function;
thus, there will never be a call to a function in such a class.
It is possible that, after applying these rules, only a single case remains.
If so, we replace the switch statement with a single static call.
Example. Figure 2 shows the transformed functions
Base::bar(), Sub1::bar(), and process() from
Figure 1.
Using Rule 2, the cases for Base and Sub2 in function
process() are consolidated because Sub2 does not implement its own
version of bar().
Also, since Sub1 has no subclasses, Rule 1 leaves a case statement with
only one arm.
After further optimization, this becomes the static call sub1::foo().
Like many interprocedural optimizations, ours is most effective when the entire
source is analyzed at one time.
Complete source allows the optimization to obtain complete information
about class hierarchies and the use of virtual functions.
It is possible to optimize procedures compiled separately, with some loss
in the effectiveness.
It is also possible to perform the optimization at link time;
however, some local optimizations, such as constant propagation, that we hope
to enable would be missed.
An alternative is the use of a programming environment that incrementally
computes summary information for large systems (often as a background task);
thus, reducing the need to examine the entire program on each compile without
sacrificing the effectiveness of the optimization.
Such an environment for SELF programs is described in [8].
Next: Implementation
Up: ENABLING OPTIMIZATION
Previous: ENABLING OPTIMIZATION
Copyright © 1995, 1996 Bradley M. Kuhn, David W. Binkley.
Verbatim copying and distribution of this entire paper is permitted in any
medium, provided this notice is preserved.