CIS-4050 Homework #5 (Liveness Analysis)

Due: Friday, May 10, 2019

Review Chapter 8 in the text. Liveness analysis is discussed Section 8.6.1. It is also discussed in Chapter 9, Section 9.2.2.

In this assignment you will complete the liveness analysis in the Augusta compiler. Proceed as follows:

Update your working copy of Augusta. The object Analysis contains a method named liveness that does a liveness analysis of the control flow graph it is given. This method is intended to modify the sets attached to each basic block of the CFG (in other words it mutates the CFG it is given). The goal of this assignment is to complete this method.

  1. In the file Analysis.scala handle the "TODO" item in the liveness method. Replace the use of at the end of the following line by a call to a new method that computes intersect (NOT successor.kill). Specifically this method should return a set that consists of all variable names in the live set that are not also in the kill set.

  2. Complete the private method computeUEAndKillSets in the same object. Follow the pseudo-code in the comments. Notice that this will entail traversing an arbitrary expression looking for all variables mentioned in that expression. You will probably want to create a recursive helper method to do this (yes, this is a bit involved since you need to account for all expression forms).

  3. Modify the Main object to actually call the liveness analysis and print warning messages if uninitialized variables are noted.

If you apply the compiler in CHECK mode to the file uninitialized.adb in the testData folder you should get a report that z might be used uninitialized.

Submit your modified files, Main.scala and Analysis.scala, in a zip archive to Moodle.

Last Revised: 2019-04-22
© Copyright 2019 by Peter C. Chapin <>