Computer Science 253 -- Homework #3

Due: Thursday, April 7, 2005 before class

In this assignment you'll build a dead-code elimination pass along the lines of the algorithm handed out in class. Actually, you'll build two versions of it, one using a reaching-definitions analyzer like the one in homework #2, and the other using SSA form. Both versions will use facilities of Machine SUIF's CFG and CFA (control flow analysis) libraries.

The object of the exercise is to gain experience with an important optimizing transformation and to compare classical data-flow analysis against SSA form, as to both convenience and compile-time performance.

What we provide:

• Class ReachingDefs has been added to the shared BVD library; you don't need to use your own solution to homework #2. In fact, you should cd into your own bvd subdirectory and, with your SUIF environment setup in place, run

  make clean

  That will delete your version of the library and its header files and expose the shared installation.
• Directory ~cs253r/hw3/dce_rd holds the skeleton of a DCE pass that uses class ReachingDefs. Directory ~cs253r/hw3/dce_ssa holds the skeleton of a DCE pass that uses the SSA form instead of classical data-flow analysis.
• A four-page excerpt on dead-code elimination from Robert Morgan's book Building an Optimizing Compiler was handed out in class on Tuesday 3/15. We give hints below about how to adapt it.
• An updated page on Using the Machine SUIF Compiler. This time, it links to the document for the system's SSA library.

What to do:

• Make your own copies of ~cs253r/hw3/dce_rd and ~cs253r/hw3/dce_ssa.

• Read Morgan's DCE algorithm and use it as a guide in completing both versions of the pass. Use class ReachingDefs as sketched in dce_rd and the SSA library as sketched in dce_ssa. Add whatever additional declarations and code you think are necessary to files dce_rd.{h,cpp} and dce_ssa.{h,cpp}. (The gaps are not all marked with comments this time.)

  Some guidelines:

  • You may treat any instruction that writes memory as if it "stores into external data". Machine SUIF has a predicate on instructions called writes_memory.
  • In addition to procedure calls, procedure-return instructions are "necessary". There are predicates is_call and is_return for instructions.
  • Label instructions (for which the predicate is is_label) need to be preserved, but their dependences shouldn't be traced like those of "real" instructions. The same is true of pseudo-op instructions, for which the predicate is is_dot. Null instructions (predicate is_null) also need to be kept; they typically carry useful annotations, and even if not, they generate no assembly code.
  • Morgan's pseudocode preserves I/O instructions. Assume that all I/O is performed by procedure calls, so that your DCE passes see no I/O instructions.
  • Morgan also preserves instructions that "store into external data." We're assuming (see above) that this includes any instruction satisfying writes_memory. But there can also be register-to-register instructions that store into external data, if the scope of the destination register is external to the current optimization region. And in a language like C, it's possible for side effects even on a local variable to be felt outside the current region if the variable's address is made available externally.
    To make it easier to test for such cases, the skeleton code includes a helper predicate on instructions called writes_volatile. It returns true for an instruction that stores into a variable whose lifetime extends beyond the current procedure invocation, or whose address is taken at any point.

• In each pass, keep a count of the number of dead instructions eliminated. When the pass is invoked with -debug n for n > 0, print a message on standard error giving the number of instructions eliminated for each procedure.
• Compile and test your passes. The procedure for creating test inputs is similar to that for homework #2. Copy ~cs253r/hw3/Makefile.hw3 to your own area. To derive fun.sfg from a C source file called fun.c, run

  make -f Makefile.hw3 fun.sfg

  To run the dce_rd pass on the resulting intermediate file:

  do_dce_rd fun.sfg fun.dce_rd

  Similarly for dce_ssa.
• Once both passes are working, make a rough comparison of their compile-time performance. Don't make a detailed study, since SUIF is not built for speed and it has currently has lots of assertion checking turned on. But at least use the time command and a large input file to get a sense of whether one approach seems more efficient than the other. For example, try this

  time do_dce_rd ~cs253r/hw3/toke.sfg

  and then do the same thing with do_dce_ssa.

Hints:

• Morgan talks about multiple branching statements per basic block. Machine SUIF puts at most one control-transfer instruction (CTI) in a basic block.
• Morgan looks for branches on which a block B is control dependent by enumerating the edges that it's control dependent upon. Since a Machine SUIF block has at most one branch instruction, you only need to find the blocks that B is control dependent on, then consider the branches that terminate them. Computing control dependence was discussed in class. The CFA library provides a class DominanceInfo, which gives you a way to compute reverse-graph dominance frontiers.
• The SSA library adds a type Operation that subsumes instructions and phi-nodes. Some opi functions on instructions that have been extended to type Operation are map_opnds (which applies a function-like "filter" object to the operands of an operation), take_note and set_note (which manipulate annotations), and get_parent_node (which returns the basic block that contains the given operation).
• Morgan's pseudocode says that when you have an unnecessary branch, you should change it into a branch to the immediate postdominator of its containing block. To make this easier, we provide a helper method called retarget_unneeded_ctis. It takes a set of basic block numbers, i.e., those whose terminating branch instructions are dead. You just need to insert the numbers of such blocks into the set called unneeded_cti_blocks.
• The CFG library gives you a function get_cti that returns the control-transfer instruction of a CFG node, if there is one, and otherwise NULL. When you know the CTI is non-null, you can obtain an InstrHandle for it by using get_cti_handle instead of get_cti. An InstrHandle allows you to insert or delete instructions, and it is also needed with the SSA library for coercing an instruction to type Operation.
• Don't assume that because other blocks are control dependent on some block B, block B must contain a branch instruction. It is customary to root the control-dependence tree in a single node. For our CFA library, this is the entry node of the CFG, so some basic blocks will appear to be control-dependent on the entry. But the entry node has no branch instruction.
• If you invoke either DCE pass with the option -debug n for n > 4, you will get a dump on standard error of the input code before and after processing.
• To create a text representation of the contents of an intermediate file, either before or after DCE, use the do_print command. For example,

  do_print fun.sfg{,.txt}

  Once a pass is starting to run without crashing, it can be very helpful to use a text-comparison tool on these "before" and "after" files.

What NOT to do:

The full source tree for Machine SUIF contains code for both kinds of DCE passes. Please don't peek until after you've turned in your own versions.

What to turn in:

Please mail your completed versions the source files dce_rd.{h,cpp} and dce_ssa.{h,cpp} to Glenn before the due date/time.