Implementation

The optimization is presently implemented as a source-to-source transformation that essentially applies the steps and rules given above. The three rules are currently implemented by hand. Implementing the optimization as a source-to-source transformation was intentional; it allows us to examine the resulting source code, which has led to several improvements in the three filtering rules. An internal (to the compiler) implementation should produce more efficient code and thus slightly better performance results.

The only interesting part in the construction of the switch statements is the implementation of the function typeof. To implement typeof, each class is assigned a unique type code. This involves adding a new integer attribute, type-of, to each class. Class constructors assign the class' type code to this attribute when objects are created. The function typeof() simply inspects it to determine the type of an object. The algorithm requires only that each class have a unique type code; consequently, multiple inheritance poses no additional difficulties. As illustrated below, constant propagation of this attribute is one of the optimizations we hope to enable.

Figure 2: Code from Figure 1 After Optimization

The implementation requires two modifications to handle separate compilation. First, to ensure that the same type-of attribute is assigned to a class when it appears in two different modules, the translator maintains a mapping from class names to type-of attributes. Second, when the complete class hierarchy is not available, a default case is added to each switch statement. The default case uses the unmodified virtual function call. For example, if the entire source were not available, the optimized switch statement for Base::bar() from Figure 2 would be the following:

      switch(typeof(this)) {
          case Base:
            Base::foo(); break;
          case Sub1:
            Sub1::foo(); break;
          case Sub2:
            Sub2::foo(); break;
          default:
            this->foo(); break;   
            // `this->' is optional
      }

Adding a default case restricts existing optimizations, but allows incremental program development. As with any interprocedural optimization the quality of the optimization improves when the entire source is available. Once development is complete, the entire program can be compiled without need for the default cases.

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.