Homework # 6
due 2015/11/28

Static virtual function resolution

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 of 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

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:

It's quite possible to be smarter than the result of applying these rules, but additional rules often require looking elsewhere in the tree (for instance, looking for assignments or previous uses of a variable). For that reason, you should stick to this analysis for CHA. It will also make it easier to compare with the reference compiler. The next section describes a much more ambitious analysis.


This analysis determines the set of types (classes) each expression could evaluate to using an iterative whole-program analysis. The $S(x)$ sets described below will need to be saved and then the inequations below are iterated until there are no changes in these sets. The $E(e)$ sets will be computed on-the-fly using (recursive) methods within the compiler. The computation may involve side-effects on $S$ sets. In several places the rules show that an $E$ computation is ignored; these computations cannot be skipped even though their result is unused.

Let $\mu = M(C,m)$ be the method named $m$ selected for an object of dynamic type $C$. Let $\sigma_\mu = \mathtt{this}$ be the defining occurrence of this in method $\mu$; in the AST this is the class declaration itself, but for this assignment, you will need a separating defining occurrence for each method. Let $D(C)$ be the class/null for the default value of class $C$. We have $D(C) = C$ for $C\in\left\{{\mathtt{Int},\mathtt{Unit},\mathtt{Boolean}}\right\}$ and ``Null'' for all other classes.

Let $S(x)$ be the least set for each defining occurrence $x$ (we assume all defining occurrences are unique) satisfying the equations below. We will distinguish $S(\mu)$, the possible classes of return values of method $\mu$, from $S(\sigma_\mu)$, the possible classes of receivers (this) of this method. Thus each method will need two $S$ sets, which complicates the implementation. Let $E(e)$ be the least set for each expression $e$ in the program such that $S$ and $E$ satisfy the conditions below.

To get the analysis started, we note that the constructor for class Main will be called:

S(\sigma_{\mu}) \supseteq \left\{{\texttt{Main}}\right\}

where $\mu$ is the constructor for class Main).

For each attribute $\alpha= \texttt{var } x:T$ in each class $C$:

\begin{displaymath}S(\alpha) \ni D(T) \end{displaymath}

For each expression body $b$ of method $\mu$ of class $C$ inheriting from class $C'$: if $S(\sigma_\mu)$ is non-empty (the method can be called) we have

\begin{displaymath}S(\mu) = E(b) \end{displaymath}

; otherwise it is the empty set. Then (again, if the method could be called) for each expression $e$ somewhere within $b$:


\(E(e) = S(x)\)

$x$ := $e'$

\(S(x) \supseteq E(e')\), \(E(e) = \left\{{\mathtt{Unit}}\right\}\)


Let $\mu' = M(C',m)$ be $m$($x_1$:$T_1$,...,$x_n$:$T_n$):$T$ is $e'$ end; in \(S(\sigma_{\mu'}) \supseteq S(\sigma_\mu)\), \(S(x_1) \supseteq E(e_1)\), ... \(S(x_n) \supseteq E(e_n)\), \(E(e) = S(\mu')\)

NB: internally, a super calls will be represented by a static_dispatch node. Unlike with normal dispatch nodes, the method $\mu'$ is known from the binding, you don't need to do the lookup $M(C',m)$.

Make sure that you use the stored value of $S(\mu')$ rather than computing it on the fly, which can lead to infinite recursion.


For each $c \in E(e_0)$ with $c \neq \texttt{null}$, let $\mu' = M(c,m)$ be $m$($x_1$:$T_1$,...,$x_n$:$T_n$):$T$ is $e'$ end; in \(S(\sigma_{\mu'}) \supseteq \left\{{c}\right\}\), \(S(x_1) \supseteq E(e_1)\), ... \(S(x_n) \supseteq E(e_n)\), \(E(e) \supseteq S(\mu')\)

NB: for dispatch nodes, the method binding is not useful. You will need to re-implement method lookup $M(C,m)$ (or use the code the skeleton provides). And as with static_dispatch, you should use the stored value of $S(\mu')$.

new $c$($e_1$,...,$e_n$)

Let $\mu' = M(c,c)$ be $m$($x_1$:$T_1$,...,$x_n$:$T_n$) is $e'$ end; in \(S(\sigma_{\mu'}) \supseteq \left\{{c}\right\}\), \(S(x_1) \supseteq E(e_1)\), ... \(S(x_n) \supseteq E(e_n)\), \(E(e) = \left\{{c}\right\}\)

NB This case occurs in the AST as a combination of alloc (where $E(e) = \left\{{c}\right\}$) and a dispatch. It should fall out of your analysis that these calls are always statically resolved.

if ($e_0$) $e_1$ else $e_2$

\(\mathit{ignored} = E(e_0)\), \(E(e) = E(e_1) \cup E(e_2)\)

while ($e_0$) $e_1$

\(\mathit{ignored} = E(e_0) \cup E(e_1)\), \(E(e) = \left\{{\mathtt{Unit}}\right\}\)

$e_0$ match { case $x_1:T_1$ => $e_1$ ... case $x_n:T_n$ => $e_n$

If $\texttt{Null} \in E(e_0)$, and $T_i = \texttt{Null}$, then $S(x_i) \ni \texttt{Null}$ and $E(e) \supseteq E(e_i)$. For each $c \in E(e_0)$ with $c \neq \texttt{Null}$, if exists $T_i = \min_{i} \left\{{T_i \mid c \leq T_i}\right\}$, then $S(x_i) \ni c$ and $E(e) \supseteq E(e_i)$. (Don't traverse branches unless they are selected!)


\(E(e) = \left\{{\texttt{Unit}}\right\}\)

$e_1$; ...; $e_n$

($n>0$) \(\mathit{ignored} = E(e_1)\), ..., \(\mathit{ignored} = E(e_{n-1})\), \(E(e) = E(e_n)\)

var $x$:$T$ = $e_1$; $e_2$

\(S(x) \supseteq E(e_1)\), \(E(e) = E(e_2)\)

$e_1$ $o$ $e_2$

\(\mathit{ignored} = E(e_1) \cup E(e_2)\), For $o \in\left\{{\mathtt{+},\mathtt{-},\mathtt{*},\mathtt{/}}\right\}$ \(E(e) = \left\{{\mathtt{Integer}}\right\}\)

For $o \in \left\{{\mathtt{<},\mathtt{<=}}\right\}$ \(E(e) = \left\{{\mathtt{Boolean}}\right\}\)


\(\mathit{ignored} = E(e_1),\) \(E(e) = \left\{{\mathtt{Integer}}\right\}\)


\(\mathit{ignored} = E(e_1),\) \(E(e) = \left\{{\mathtt{Boolean}}\right\}\)


If literal is a string constant, \(E(e) = \left\{{\mathtt{String}}\right\}\). Similarly with boolean, integer, unit and null literals.


Internally a native body is represented by no_expr() nodes. This term may come from one of the following sources:

Class Method $E(\mathtt{native})$
Any Any \(S(\sigma_{\mu})\)
Any toString \(\left\{{\mathtt{String}}\right\}\)
Any equals \(\left\{{\mathtt{Boolean}}\right\}\)
IO abort \(\left\{{}\right\}\)
IO out \(S(\sigma_{\mu})\)
IO in \(\left\{{\mathtt{String},\mathtt{Null}}\right\}\)
IO symbol \(\left\{{\mathtt{Symbol}}\right\}\)
IO symbol_name \(\left\{{\mathtt{String}}\right\}\)
Unit Unit \(\left\{{\mathtt{Unit}}\right\}\)
Int Int \(\left\{{\mathtt{Int}}\right\}\)
Int toString \(\left\{{\mathtt{String}}\right\}\)
Int equals \(\left\{{\mathtt{Boolean}}\right\}\)
Boolean Boolean \(\left\{{\mathtt{Boolean}}\right\}\)
Boolean equals \(\left\{{\mathtt{Boolean}}\right\}\)
String String \(\left\{{\mathtt{String}}\right\}\)
String equals \(\left\{{\mathtt{Boolean}}\right\}\)
String concat \(\left\{{\mathtt{String}}\right\}\)
String substring \(\left\{{\mathtt{String}}\right\}\)
String charAt \(\left\{{\mathtt{Int}}\right\}\)
Symbol Symbol \(\left\{{\mathtt{Symbol}}\right\}\)
ArrayAny ArrayAny \(S(\sigma_{\mu})\)
ArrayAny resize \(S(\sigma_{\mu})\)
ArrayAny get \(S(\texttt{obj})\cup\left\{{\mathtt{Null}}\right\}\)
ArrayAny set \(S(\texttt{obj})\cup\left\{{\mathtt{Null}}\right\}\)
Statistics clear \(S(\sigma_{\mu})\)
Statistics get \(\left\{{\mathtt{Int}}\right\}\)
Statistics print \(S(\sigma_{\mu})\)

The occurrence of \( S(\texttt{obj}) \) in the rule for get and set refers the formal parameter of this name in set.

Implementing Optimizations

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:

If a dispatch is statically resolvable (only one possible method and the receiver cannot be null), it is replaced by a static dispatch. The binding will be to the method that the static resolution determines.
case clauses
If 0-CFA determines that a ``case'' clause is impossible, that branch should be removed. It could be that all branches are removed.
If 0-CFA determines that a method will never be called, no code needs to be generated for it. As a close approximation to this, the body (of a non-native method!) should be replaced with a null node. (Not a no_expr node because that would mean it was native, and would get link errors.)
The skeleton optimizer mentions other optimizations (inlining and dead-let removal), but limit yourself to virtual method resolution. The Resolution class is instantiated with the program, the level (1 for CHA and 2 for 0-CFA) and the `next node id'' (see below). The CHA analysis is paired with the simple non-null analysis described; the 0-CFA analysis does non-null analysis as part of it.

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 $S$ 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 $E$ sets can be computed by recursive methods. 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 $S$ 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.

Testing & Measurement

Evaluate the results of optimization (or the non-optimized ``control'' case) in two ways:

You should use the benchmark files that come when you run the Makefile:
Simple ASCII graphics program
The semantic analyzer of the Cool compiler written completely in Cool. It is run on its own parse tree.
A test suite for method call resolution.
Please create a readable table summarizing your results in README. If you would rather, you may produce a README.pdf instead.


To get started, type

make -f /afs/cs.uwm.edu/users/classes/cs854/src/homework6/Makefile
This will get a number of files. The files you will edit are:
All your analysis code should go here.
Your results.

John Tang Boyland 2015-11-11