University of Arizona, Department of Computer Science

CSc 553 : Programming Assignment 2 (Machine-independent Code Optimization)

Mon Oct 8, 2018

Due: 11:59 PM, Mon Oct 22 Tue Oct 23, 2018

1. General

This assignment involves the implementation of dataflow analysis and machine-independent optimizations. These optimizations are to be carried out if your program is invoked with the command-line option –O1.

You are to test the effectiveness of your optimizations by testing programs compiled with and without the –O1 option and report the results in a README file.

1.1. Optimizations Independent of Flow Information

You should implement the following optimizations:
  1. Collapsing jump chains: chains of jump instructions should be collapsed so that each jump branches directly to its final destination.

  2. Simple machine-independent peephole optimizations. E.g., transform the sequence (where R is a relational operator)
    if x R y goto L1
    goto L2
    label L1

    to the following (where, S is the complement operator of R):

    if x S y goto L2
    label L1

    Examine the code generated by your compiler on several programs of reasonable size, of your choosing, to determine what patterns to use for your peephole optimizations.

  3. Intra-block copy propagation: given a copy instruction d: x := y and a subsequent use u of x within a basic block, if it can be guaranteed that x is not redefined between d and u, then the reference to x at u can be replaced by a reference to y, as illustrated by the following:
    Before       After
    t1 := z   t1 := z
    u := t1+1   u := z+1

1.2. Intra-Procedural Liveness Analysis and Dead Code Elimination

You should carry out liveness analysis at the intra-procedural level. For this, you may assume that global variables are always live. To simplify the problem, you may also assume that all elements of an array are live if any of its elements is (i.e., treat the array as a single variable).

Copy propagation can cause some instructions to become dead. You are to use the information obtained from your liveness analysis to eliminate dead code, i.e., code whose results are never used.

Note that the elimination of some dead code can cause additional instructions to become dead. A naive approach would be to repeat the liveness analysis all over again, eliminate some more dead code, and so on. Such an approach would be hopelessly inefficient, and should not be used. Instead, during liveness analysis, you should propagate information about what instructions are dead, and use this to improve the liveness analysis. The idea is as follows:

At the end of the analysis all instructions that are marked "dead" represent dead code and can be eliminated.

Grading

In order to get credit, your optimizations must satisfy the following criteria:

  1. It must be correct, i.e., it must not change the behavior of any program.

  2. It must be effective, i.e., for programs that contain code instances to which the optimization is applicable, it should in fact optimize those code instances.

Effectiveness will be evaluated using instruction execution counts.

Partial credit: You may be eligible for partial credit if your program works for some inputs but not others: see the Greding Procedure described in the class grading policies document for details of how to go about this. Note that you have to initiate the partial credit process by submitting the necessary information (described in this document).

2. Output

As before, your program will take its input from stdin and generate all output on stdout.

Error messages, if any, will be sent to stderr. (Note that the input programs used fo testing your code will not contain syntax or semantic errors.)

3. Invoking Your Program

Your program will be called compile, and will take an optional command-line switch -O1 that will specify whether or not code optimization is to be carried out.

4. Turnin

You should turn in the following:

  1. All of the source files to your compiler, together with a Makefile that supports at least the following:
    make compile
    Creates an executable file called compile in the current directory that implements your compiler. Note that this should build your compiler from scratch, i.e. starting from the lex and yacc specifications.
    make clean
    Deletes the following files from the current directory: lex.yy.c, y.tab.*, y.output, all object files (*.o) and the executable file compile.

  2. A README file that describes the different optimizations your compiler implements, as well as the cost/benefit of using these optimizations, based on testing at least five different nontrivial programs.

To turn in your program, execute the command "turnin   cs553f18_assg2   files".

5. Evaluating Your Optimizations

You can evaluate the cost of your optimizations by measuring the additional runtime overhead of the optimizations themselves together with the program analyses needed to support the optimizations.

The benefits of optimizations can be estimated by the percentage reduction in the number of instructions executed. This can be obtained using a version of SPIM that provides statistics on different kinds of instructions executed by a program. The source code for this version of SPIM is available here and also in /home/cs553/fall18/spim-7.2.1-keepstats; the executable for this version of SPIM is in

/home/cs553/fall18/bin/spim
To get execution count statistics for an assembly file foo.s, use the command
spim -keepstats -file foo.s