CSE302 Lab 5-Dataflow Optimizations Solution

1 INTRODUCTION
In this lab you will implement the following dataflow optimizations:
• Global Copy Propagation (GCP)
• Global Dead Store Elimination (DSE)
You will work with input TAC files, which you will convert into CFG in (crude) SSA form using the starter code that is provided to you. Your target will be TAC in SSA form, which you will be able to interpret using the provided TAC interpreter.
This lab will be assessed. It is worth 10% of your final grade.

2 STARTER CODE: TAC, CFG, AND CRUDE SSA
The compiler pass you implement in this lab will slot in after the generation of TAC and before the invocation of the tac2x64.py pass you wrote in lab 4. The source language is therefore the same TAC that you already used in lab 4.
2.1 TAC Library: Parser and Interpreter
You are provided with an implementation of a TAC parser and interpreter in the file tac.py. This class represents TAC instructions, procedure declarations, and global variable declarations using the classes
Instr, Proc, and Gvar respectively. These classes are fairly self-documenting: read their __init__() member functions to see their relevant data attributes.
Parser This library can also load TAC in either textual or JSON form using the function load_tac(), which takes a single TAC file name as input. The function will either raise a ValueError exception or return a list of Proc and Gvar instances. The library performs some minimal sanity checks on the provided TAC, but does not make sure that all the labels and symbols are well formed.
Interpreter To execute a TAC program, use the execute() function. Note that this function requires two dictionaries, gvars and procs, that map global symbols to global variables and procedures respectively. You will have to construct these dictionaries yourself from the output of load_tac(); for example, you can do the following:
gvars, procs = dict(), dict() for decl in tac.load_tac('example.tac.json'):
if isinstance(decl, Gvar): gvars[decl.name] = decl else: procs[decl.name] = decl tac.execute(gvars, procs, '@main', [])
2.2 CFG library
The CFG library is in cfg.py. Most of the CFG class therein is self-documenting. To create a CFG from a TAC procedure, use the infer() function; dually, to linearize a CFG back into the body of a TAC procedure, use the linearize() function.
Liveness The live-in and live-out sets can be computed using the function recompute_liveness(). It takes two dictionaries, livein and liveout, as parameters; both of these map instructions (i.e., tac.Instr objects) to sets of temporaries. Both these dictionaries are emptied out and their contents are replaced with the corresponding live sets.
Display To help with debugging the CFG, you can use the write_dotfiles() function to generate a DOT file corresponding to the CFG. This is then processed with the Graphviz toolkit to produce a PDF. There is an example of its use in the driver code at the bottom of cfg.py.
2.3 Crude SSA Generation
The SSA generation is done in the file ssagen.py, specifically with the function crude_ssagen(). It takes a tac.Proc instance and its cfg.CFG instance (produced with cfg.infer()) as arguments, and updates the cfg.CFG instance with its SSA form (crude).
The φ-functions of SSA are represented in an extended TAC language with a new opcode, "phi", whose first argument is a dictionary mapping block entry labels to (versioned) temporaries. The meaning of this representation is explained in lecture 8.

[Continued…]
3 DATAFLOW OPTIMIZATIONS
You will implement two optimizations in this lab that make use of liveness and SSA form.
3.1 Global Dead Store Elimination (DSE)
without any alterations to the behavior of the code.
Note: Effectful Instructions
Note: Multiple Iterations
After every round of DSE, you should recompute liveness information and check again if there are any new instructions with dead stores. If so, you should run another round of DSE.
3.2 Copy Propagation (GCP)
In the CFG in SSA form, for every copy instruction of the form %u = copy %v;, you can globally replace every occurrence of %u by %v and delete the copy instruction. As a result your code should be free of all copy instructions. GCP is a “one shot” procedure; you do not need to rerun it.
3.3 Deliverables
You will write the program tac_dfopt.py that will read a TAC file specified in the command line and output the optimized TAC (with SSAphi instructions) to standard output, or to a file specified using the -o option.