Homework # 9
due December 5

Reading

Read the ``Inference Rules'' primer. Read Section 1.5 (Abstract Interpretation) of the textbook.

Book Problems

Do the exercises in the ``Inference Rules'' primer.

Writing Rules

Finish the work from lecture: write inference rules describing inter-procedural effects analysis using judgments of the following forms:

$$A \vdash s \:!\: W \qquad A \vdash s \:?\: R \qquad e \textrm{ uses } R$$

where $A$ is a set of procedures currently being analyzed, $s$ is a statement, $W$ is a set of definitely written variables and $R$ is a set of variables that are read before being written. Recall that the middle relation depend on the left relation, albeit with an empty $A$. You may use the ``uses'' relation without defining it.

The $A$ set prevents infinite recursion in the analysis. If a procedure call to a procedure already under analysis is encountered, then return the infinite set for must-write and the empty set for may-read. Otherwise analyze the body and be sure to mask out the locals and both kinds of formal parameters.

Programming

Implement inter-procedural definitely-assigned analysis using the rules you developed:

1. Define two recursive methods; one for each relation. Each recursive method should use the VISITOR design pattern to handle each syntactic case and return a set of variables.
2. Write a driver that uses these recursive methods to determine whether
   1. every procedure or program correctly defines its results; if not, then indicate the problems.
   2. some procedure body may read (directly or indirectly through a procedure call) any local variable or result before it has been assigned; list such variables.
   3. the program main body may read any non-input variables before they are set; list any such variables.
   Your code should assume function calls are cheap: it should NOT cache analysis results. Instead whenever it needs analysis information, it should call one of the two recursive methods. You may copy in the getUsed method from the solution LiveVariableAnalysis.

Submission

Turn in your inference rules on paper, or send PDF by email to boyouen. Do all your programming work in a class CheckDefined in the default package. Do not use any other classes other than those in the sklnst.jar file. Send the source of this class by email.

About this document