CIS-4050 Homework #5 (Reaching Definitions)

Due: Friday, May 10, 2019

Review Chapters 8 and 9 in the text. Reaching definitions are discussed in Section 9.2.4

In this assignment you will implement a reaching definitino analysis for Augusta. Proceed as follows:

Update your working copy of Augusta.

  1. Modify the definition of the basic blocks so they hold a set of reaching definitions for each block. To do this you'll need to decide how to represent the definitions in a CFG. One possibility is to simply number them (arbitrarly). However, this will require that a CFG be associated with a data structure of some sort that maps definition numbers to the definitions themselves.

  2. In the file Analysis.scala write a method that traverses a CFG and numbers the definitions contined in it. Notice that this might require two maps. This is because sometimes you'll need to look up a definition given its number, but sometimes you'll need to look up the number assigned to a definition.

  3. In the file Analysis.scala write a method to compute the downwardly exposed definitions and the definition kill sets for each node. You'll need to add suitable sets to the basic blocks for this.

  4. In the file Analysis.scala write a method that computes the reaching definitions for each block.

  5. Modify the Main object to actually call the reaching definition analysis and output some results for checking.

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 <pchapin@vtc.edu>