Homework # 6
due March 6

Book Problems

Do problem 2.10 and the first part of problem 2.13.

Discussion

The ``similar result'' in the second half is true for WHILE, but neither is true for fluid Java flow graphs. Use Yang Zhao's tool to find a simple counter-example (for the forward or backward direction).

Look at the proof that for distributive transfer functions and determine an additional restriction on the transfer functions that ensures that is still maintained even if Exercise 2.13 is false. Explain this restriction intuitively.

Analysis of Stack-Based Evaluation

In Fluid, the control-flow graph has one node for each atomic action, such as reading a variable, assigning a variable, or ignoring a value. Thus the CFG for the code

x = (y = z) + a;

consists of the straight-line sequence of nodes that

1. reads z onto the stack;
2. copies the top of the stack into y;
3. reads a onto the stack;
4. pops the top two values on the stack, adds them and pushes the result;
5. copies the top of the stack into x;
6. pops the top of the stack.

(Actually the CFG has many more nodes than even this list would indicate, but they can be ignored.)

Now: we need to be careful about side-effects. Assignments to local faint variables can be safely ignored, but anything returned from the method, passed in a method call, or stored in a field is strongly live. Furthermore, anything that influences whether an exception is thrown is strongly live as well. For simplicity, we also assume that anything that affects control flow is strongly live, for example, the condition of a if statement.

First define the lattice to be used for SVLA in fluid.

Then for each of the following points in the control-flow graph, give the transfer function to be used. We identify the control points by a syntactic fragment and a brief explanation of the dynamic (forward!) semantics.

$n$

push literal number $n$ on stack.

_*_

pop two elements from the stack, multiply them and push the result.

_/_

pop two elements from the stack, divide them and push the result.

_==_

pop two elements from the stack, compare them and push the result.

$x$

read variable $x$ onto the stack.

$x$ = _

copy top element into variable $x$.

_.$f$

pop off an object reference; push its $f$ field onto the stack.

_.$f$ = _

swap the top two elements of the stack; pop off an object reference; copy the new top of the stack into field $f$ of the object.

_.$f$(_)

pop off $n$ actual parameters and also a receiver object and perform a call; push on the result.

new $C$(_)

pop off $n$ actual parameters; create a new object of type $C$ and call the constructor with it; push new object on stack.

_;

pop off the top stack element and discard it.

return _;

pop off the top stack element and return it.

if (_)

pop off the top stack element to determine branch.

Submission

As with all homeworks, please turn in your homework on paper at the beginning of lecture.

About this document