Examples

Our optimization increases the possibilities for inlining by turning dynamic function calls into static ones. This allows the compiler to match each call-site with a single (static) procedure. For example, inlining has the following affect on Base::bar():

        Base::bar() { 
            switch(typeof(this)) {
                case Base:
                  val = 1; break;
                case Sub1:
                  val = 2; break;
                case Sub2:
                  val = 3; break;
            }
            printf("%d\n", val);
        }

Since the resulting code for bar() is short, it is a candidate to be inlined into other functions such as process().

The inlining we enable allows the compiler to perform other optimizations such as code motion. For example, Figure 3 shows Pentium assembler output generated by GNU C++ for geqn (geqn and GNU C++ are discussed in Section 3). Notice that in the second column of the figure, the instructions ``pushl $0'' and ``pushl %esi'' are moved from each case to just before the ``jmp *L963(,%eax,4)'' instruction.

In addition to inlining, our optimization enables constant propagation by providing opportunities for both interprocedural and intraprocedural constant propagation. In particular, we hope to enable the propagation of class types. We illustrate this with two examples. First, suppose that the code in Figure 4a is added to the program in Figure 1. The result of our optimization and inlining on this code is shown in Figure 4b. The type of s1 can be propagated to the switch statement. For this example, s1's type is a constant as it has no derived classes. (In general, knowing a type allows the number of cases to be pruned.) In the resulting code, shown Figure 4c, our optimization, inlining, and constant propagation have combined to transform a dynamic call into a static call.

Figure 3: Enabling Code Motion

Figure 4: Enabling Constant Propagation

As a second example, consider inlining the two calls to bar() in function process() shown in Figure 2. Because our optimization introduces switch statements into bar(), the resulting code contains nested switch statements. Within each case of the outer switch statement, the typeof(x) is constant. Constant propagation of this value allows the nested switch statements to be flattened; after inlining the calls on foo(), and performing code motion, which moves the call to printf, process() becomes

        void process(Base * x) {             
              ... 
              switch(typeof(x)) {
                case Base:
                    val = 1; break;
                case Sub1:          
                    val = 2;
                    val++; break;
                case Sub2:          
                    val = 3; break;
              }                     
              printf("%d\n", val);
              ...
        }

Further constant propagation within the case for Sub1 allows the cases for Sub1 and Sub2 to be combined.

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.