This works was done in the Concert [8] compiler, so subsequent discussion of our optimization relies heavily on the framework of that compiler. Therefore, a brief overview is given of the two portions that we use: the analysis and cloning modules.
The Concert compiler has a global analysis framework (see [23, 22] for more detail) that does context sensitive flow analysis. Context sensitivity adapts, in a demand-driven manner, to program structure. A method contour [26] represents execution environments for a method, i.e. it is the unit of context sensitivity. Method contours can discriminate arbitrary data-flow properties of its caller and creator. An object contour represents method contours of the statements that created a given object. For method contours:
Contours are created on demand: they are created when the analysis needs to distinguish some property. The original use of this framework was type inference, which creates contours to distinguish type information. Method contours are created for different sets of argument types; for polymorphic fields, different object contours are built for the containing object to differentiate the types in the field. The analysis framework includes a mechanism for distinguishing object contours with respect to uses of objects.
Figure 6 illustrates type analysis on part of the program in Figures 4 and 5. In Figures 6 and 7, contours are signified by ``[<callers>, <creators>].'' The first graph is after one pass of analysis; the calls to do_rectangle have different argument types, so two contours are created to distinguish them; on the other hand, since both calls to Rectangle::area have the same types for their arguments, just one contour is created embracing both call sites. Within Rectangle::area the type of Rectangle::lower_left is ambiguous, so the demand-driven specialization comes into play. Since the type confusion is due to a field, the system creates object contours representing each creation statement of Rectangle to distinguish the types of Rectangle::lower_left. This results in Figure 7.
The Concert compiler includes a mechanism for cloning based upon data-flow properties discovered by analysis [24], which works on the contours. The mechanism uses a generic function that determines, for two given contours, whether they are compatible. Cloning is done upon both methods and classes.
For each method in the program, its method contours are grouped into sets of compatible contours, and a copy of the method is generated for each set. Caller information from the contours is used to reconstruct the call graph. The original use of this mechanism is to eliminate dynamic dispatches from the program, and so it marks contours as incompatible if they have different types for the target of any call in the method.
For example, the method Rectangle::area in Figure 7 has two contours to discriminate the type of the lower_left field of Rectangle. In the program, however, there is only one method, requiring that lower_left.area(upper_right) be dynamically dispatched. The cloning mechanism marks these two contours as incompatible as their types for the field lower_left of Rectangle differ; then, Rectangle::area() is duplicated and lower_left.area(upper_right) can be statically dispatched in each one since the type of lower_left is precise.
Note that cloning Rectangle::area creates problems in
do_rectangle: there are now two possible methods to call for
Rectangle::area. The cloning framework includes an iterative
mechanism to split caller methods when cloning a callee creates a
dynamic dispatch, which in this case splits do_rectangle as
well.
Cloning is also done on classes: classes are split based upon the object contours. As with methods, cloning works by grouping the contours based upon some discriminator function. Cloning a class does not necessarily require cloning all associated methods.
