Updated Feb 20 18:15am
Update, Feb 20: There is a problem with the
yacc benchmark. Ignore that benchmark.
Update, Feb 20: Sample output files for the
wc benchmark can be found here.
In addition to the files created by DomMain, this tarball
also contains PostScript files for every DOT file.
Before you start this assignment, you should make sure that Java 2 SDK
Early Release 1.5.0 is installed on your system. It is also
recommended that you install the dot program.
Instructions on how to install these programs can be found here.
compiler.jar, utility.jar, and functor.jar).
DomMain.java, Dominators.java, and
Loop.java.
Impact32.mdes).
benchmarks/*.X)
Set your CLASSPATH environment variable to:
.:./compiler.jar:./utility.jar:./functor.jarjavac -source 1.5 DomMain.javawc benchmark using the command:
java DomMain wc
DomMain class in this assignment creates a
Dominators object for each procedure in its input
program. The purpose of a Dominators object is to
perform dominator analysis calculations on the procedure it is
operating on. It also provides methods that print dominator analysis
information in a human-readable format.
Fill in the computeDomSets() method in
Dominators.java with code that computes the dominator
sets for each control block. Using this information, this method
should fill in the field dom_sets, which is a mapping
from control blocks to their dominator sets.
Run DomMain again. For each procedure proc in the
program, you should get a file named
proc.sets.txt. This file contains the dominator
sets for each control block. Verify that the output is correct!
computeImmDoms() method in
Dominators.java to calculate the immediate dominators of
each control block. This method can assume that the dominator sets
are already in dom_sets. It should store its results in
idoms, which is a mapping from control blocks to their
immediate dominators, before returning.
Run DomMain again. For each procedure proc in the
program, you should get a file named
proc.tree.dot. This file contains the dominator tree for the procedure in DOT format. If you have the dot program installed, you can convert this file to PostScript using the command:
dot -Tps -o proc.tree.ps proc.tree.dot
detectLoops() method in
Dominators.java so that it detects all loops in the
procedure, and creates a Loop object for each loop found.
The Loop objects thus created should be stored in
loops, which is a list of all loops in the procedure.
Also, fill in the computeBody() method in
Loop.java so that it puts all control blocks that belong
to the body of the loop into the body set.
Run DomMain again. For each procedure proc in the
program, you should get a file named
proc.cfg.dot. This file contains the
control-flow graph of the procedure in DOT format. In this graph,
loop bodies appear in different colors according to their level of
nesting. Outer loops appear in blue, loops at a depth of 2 appear in
red, and loops at a depth of 3 and up appear in green. Convert this
file to PostScript and browse it, to verify the results.
addPreHeaders() method in
Dominator.java so that it inserts an empty pre-header
block before each loop header, and redirects all control-flow edges
from outside the loop to the loop's header to point to the pre-header
instead.
Run DomMain again. For each procedure you will get a second
control-flow graph file, named proc.ph.cfg.dot,
that contains the preheaders you have inserted. Loops appear in
different colors, just as before. Browse it to verify that you
inserted the pre-headers correctly.
Note: Notice that main() in
DomMain.java recomputes dominator information after the
pre-headers are inserted! This is because inserting new control
blocks invalidates any preexisting information.