Homework # 6
due 2010/11/30

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

• this is never null.
• The result of a constructor call (dispatch where the type of the receiver and the method name are the same) is never null.
• Nothing of type Int, Boolean or Unit is ever null.
• A let expression is non-null if its body is.
• An if expression is non-null if both its branches are.
• A branch is non-null if its body is.
• A case expression is non-null if all its branches are.

It's possible to be smarter than this using the technique described next.

0-CFA

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) virtual methods.

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$:

$$S(\alpha) \ni D(T)$$

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

$$S(\mu) = E(b)$$

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

$x$

$x$ := $e'$

,

super.$m$($e_1$,...,$e_n$)

Let $\mu' = M(C',m)$ be $m$($x_1$:$T_1$,...,$x_n$:$T_n$):$T$ is $e'$ end; in , , ... ,

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.

$e_0$.$m$($e_1$,...,$e_n$)

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 , , ... ,

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 , , ... ,

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$

while ($e_0$) $e_1$

$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 $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 $E(e) \supseteq E(e_i)$ and $S(x_i) \supseteq \left\{{c}\right\}$. (Don't traverse branches unless they are selected!)

{}

$e_1$; ...; $e_n$

($n>0$)

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

,

$e_1$ $o$ $e_2$

For $o \in\left\{{\mathtt{+},\mathtt{-},\mathtt{*},\mathtt{/}}\right\}$

For $o \in \left\{{\mathtt{<},\mathtt{<=}}\right\}$

-$e_1$

!$e_1$

$\mathit{literal}$

If literal is a string constant, . Similarly with boolean, integer, unit and null literals.

native

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
Any	toString
Any	equals
IO	abort
IO	out
IO	in
IO	symbol
IO	symbol_name
Unit	Unit
Int	Int
Int	toString
Int	equals
Boolean	Boolean
Boolean	equals
String	String
String	equals
String	concat
String	substring
String	charAt
Symbol	Symbol
ArrayAny	ArrayAny
ArrayAny	resize
ArrayAny	get
ArrayAny	set
Statistics	clear
Statistics	get
Statistics	print

The occurrence of in the rule for get 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:

case clauses

If a ``case'' clause is impossible, it should be removed. It could be the code generator will choke if you remove all cases; ignore this possibility. I will change the code generator if so.

dispatch

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.

methods

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).

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

You need to write a test case (as one big file test.cool, for 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:

• Static size of compiled code
  1. total lines of code (``wc xxx.s'')
  2. percentage of dispatch nodes converted into static dispatch nodes in generated code (don't count dispatches in code that is removed by one of the other optimizations).
  3. percentage of ``case'' branches removed
  4. percentage of method bodies omitted
• Dynamic number of instructions executed: with subtotals for reads/writes/branches. (Use the Statistics class with the CS854 version of spim.)

You should use the benchmark files and inputs in

/afs/cs.uwm.edu/users/classes/cs854/src/homework6/benchmark

(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 README.pdf instead.

Deliverables

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:

Analysis.scala

All your analysis code should go here.

test.cool

Test case for CHA and 0-CFA.

README

Your results.