Virtual method calls can contribute substantial overhead to the execution of a program in a highly object-oriented language, such as Cool. For this assignment, you will implement two different kinds of static virtual function resolution by determining what are the possible classes of the receiving object. At a dispatch, we see if the limited set of classes mean that only one possible method is the result. At the same time, we will check to see if the receiver could be null. If the receiver will never be null and the target of the dispatch can be statically resolved, a dispatch node will be converted into a static dispatch. In a real compiler, we would want to make use the cases when only one of the two conditions can be verified, but for here, it is easiest to require both (since the code generation of static dispatch assumes that the receiver cannot be null).
Similarly, with the information about what classes an expression can evaluate to and whether null is possible, one can prune a case expression to remove branches that will not execute.
Class hierarchy analysis uses the static type of the receiver to do static virtual function resolution. If none of the classes under the static type override the method, it can be statically resolved. As a special case, if the static class of a (non-null) receiver has no subclasses, it can be statically resolved. An easy way to do the task is to keep a list of overriding methods for every method.
However, as mentioned above, we also require that the receiver be guaranteed non-null in order to convert it into a static dispatch. For this task, we will use a simple local analysis:
thisis never null.
This analysis determines the set of types (classes) each expression could evaluate to using an iterative whole-program analysis. The sets described below will need to be saved and then the inequations below are iterated until there are no changes in these sets. The sets will be computed on-the-fly using (recursive) virtual methods.
Let be the method named selected for an object of dynamic
type . Let
be the defining occurrence of
this in method ; in the AST this is the class declaration
itself, but for this assignment, you will need a separating defining
occurrence for each method.
Let be the class/null for the default value of class
. We have for
``null'' for all other classes.
Let be the least set for each defining occurrence (we assume all defining occurrences are unique) satisfying the equations below. We will distinguish , the possible classes of return values of method , from , the possible classes of receivers (this) of this method. Thus each method will need two sets, which complicates the implementation. Let be the least set for each expression in the program such that and satisfy the conditions below.
To get the analysis started, we note that the constructor for class
Main will be called:
For each attribute
in each class :
Let be (:,...,:): is end; in , , ... ,
NB: internally, a
super calls will be represented by a
static_dispatch node. Unlike with normal
dispatch nodes, the method is known from the
binding, you don't need to do the lookup .
Make sure that you use the stored value of rather than computing it on the fly, which can lead to infinite recursion.
For each with , let be (:,...,:): is end; in , , ... ,
dispatch nodes, the method binding is
not useful. You will need to re-implement method lookup
(or use the code the skeleton provides).
And as with
static_dispatch, you should use the stored value of
Let be (:,...,:) is end; in , , ... ,
NB This case occurs in the AST as a combination of alloc (where ) and a dispatch. It should fall out of your analysis that these calls are always statically resolved.
If , and , then . For each with , if exists , then and . (Don't traverse branches unless they are selected!)
If literal is a string constant, . Similarly with boolean, integer, unit and null literals.
native body is represented by
This term may come from one of the following sources:
The occurrence of in the rule for get refers the formal parameter of this name in set.
You will be given a skeleton optimizer that accepts analysis options. You should implement static class resolution and should use it to perform the following changes:
nullnode. (Not a
no_exprnode because that would mean it was native, and would get link errors.)
Resolutionclass is instantiated with the program, the level (1 for CHA and 2 for 0-CFA) and the `next node id'' (see below).
Optimization at the AST level requires changing the AST for expressions. The node classes (now) have setter methods for changing children of a node (caution: do not create a DAG or worse, a cyclic graph, the AST should still be an abstract syntax TREE). We provide a new visitor, a ``modifying visitor'' which makes is easier to substitute in new subtrees. Override the visit method for any node which might need to be replaced with something. You can call ``super'' to have it traverse the nodes inside this node.
When you create a new node, you need to ensure that new nodes are given appropriate line numbers and unique node identifiers. We provide a class AdditionalNodeFactory that does most of the work here. It should be passed a tree modifier visitor and the ``next node id.'' Don't call the node constructors directly.
The 0-CFA analysis requires that a set be stored for every set: We associate with every formal parameter, every attribute, every let bound variable, every `when' bound variable and every method body a set of classes, initially empty. The sets can be computed by recursive member functions. Each set may also contain an indication that the variable could be null. Then we make repeated passes over the program in which we compute the set for every expression and use this to update the sets involved. Once a fixed point is reached, we can use the information for a receiver to determine whether it is statically resolvable. The analysis must be implemented to carry along possible null-ness as well.
You may use ``Extended Cool'' (aka Scala), especially its collection libraries, to do your work. This way you avoid the need to implement set classes. The solution, however, will be in strict Cool.
You need to write a test case (as one big file
easy of testing)
that checks for bugs in your implementations. Optimizations are very
easy to do wrong, so testing is important.
Evaluate the results of optimization (or the non-optimized ``control'' case) in two ways:
(For simplicity, each benchmark is a standalone Cool program.)Please create a readable table summarizing your results in README. If you would rather, you may produce a
To get started, type
make -f /afs/cs.uwm.edu/users/classes/cs854/src/homework6/MakefileThis will get a number of files. The files you will edit are: