6.035 - Fall 1999 - TA: Daniel Barkalow le04

Datapath Optimizations

le04 is...

Chris Laas (golem) Mike Phillips (mpp) Jim Waldrop (jlwfnord)

Division of Labor

Chris wrote the algebraic simplifications and the toplevel of the CopyPropagation FPA extension. Jim wrote the DeadCodeElimination FPA extension, and Mike wrote FixedPointAlgorithm.java and several of its friends. As usual, each member of the team at one point had full and solitary access to the entire code base and frobbed with things not directly under his jurisdiction.

Clarifications, Assumptions, Additions

To access the optimizations, use these switches on the command line:

• -cp, -opt cp: Copy propagation

• -dce, -opt dce: Dead code elimination

• -spim, -opt spim: output SPIM code instead of MIPS

Overview

This project was directed towards datapath optimization - cutting out pointless add’s, sub’s, mulo’s, loads and stores in the finished code. We attempted to implement 3 types of datapath optimization for this project, and in addition implemented a rather general framework for running any given FixedPointAlgorithm on a class.

Implementation and Insights

Our overall implementation took 2 paths. First, we implemented algebraic simplification as an integral part of our low-level intermediate representation. Our algebraic simplification cannot be turned off - then again, we decided that nobody in their right minds would want to do so.

Next, we implemented two fixed-point algorithms, dead code elimination and copy propagation, by creating a FixedPointAlgorithm class that would perform a generic FPA optimization on a CFG of DelocalizedInstructions (one step above machine code), and then extending the FPA class to DeadCodeElimination.java, a backward-traversing variable-based FPA, and CopyPropagation.java, a forward-traversing expression-based FPA.

Specific datapath improvements

Algebraic simplifications

Algebraic simplification makes use of the Traversable nature of our DelocalizedInstruction CFG to clean up any stray constants. This is handled in IR2/MethodDescriptor.java. and makes use of the Traversal class and Traversable interface.

Traversable interface

The Traversable interface was initially a general helper set of functions for performing algebraic simplifications (by traversing a CFG of DelocalizedInstructions) and for producing the BasicBlock “scaffolding” and for walking down the scaffolding to execute a FixedPointAlgorithm.

CFG (Control Flow Graph)

We use a Control Flow Graph (CFG) to keep track of where our DelocalizedInstructions are. DelocalizedInstructions are the successors to the lowIR we had in phase 4 of the compiler project.

FixedPointAlgorithm structure

Our FixedPointAlgorithm is a model of the framework given in class, with as much code that was considered independent of the actual subclass algorithms tossed in as possible, to keep things sane and reduce code duplication and in the interests of building an expandable system. We encountered a slight problem in that the abstract class was finished before either of the below concrete classes were implemented, so the initial debugging was a little tough. However, once we knew that FPA was solid, it simplified debugging.

BasicBlock “scaffolding”

In order to run our FixedPointAlgorithm on our code, we created the BasicBlock class. We construct a graph of BasicBlocks, each of which point to the start and end DelocalizedInstruction within the BasicBlock. This way, we construct a “scaffolding” which we use to run subclasses of FixedPointAlgorithm over our otherwise cumbersome CFG of DelocalizedInstructions.

DeadCodeElimination and CopyPropagation extensions of FPA

Dead Code Elimination is a backwards-traversal fixed point algorithm, with a union confluence operator. It operates on variables. Copy Propagation is a forward-traversal fixed point algorithm, with an intersection confluence operator. It operates on expressions. We implement a generate and a kill method within the concrete classes, which FixedPointAlgorithm calls to produce the gen/kill sets. We also implement the setInitialConditions method within the concrete classes (as they are specific to the type of optimization being performed) and the core optimize() function also resides within the concrete classes. MethodDescriptor calls a FixedPointAlgorithm’s getFixedPoint method, which calculates in/out sets for each BasicBlock being optimized, sets each BasicBlock’s initial conditions, and calls optimize() on each in turn.

Results

Order of Operations

We perform copy propagation before we perform dead code elimination, thus using the dead code elimination to clean up propagated copies that we don’t need.

Algebraic Simplification

Please see test 18-algebraic.dcf in our Dataflow/tests directory. 18-algebraic.dcf

class Program
{
    void main()
    {
int a;
a = 1 * 2 + 3 - 4 * 5 - 6 + 7 * 8;
callout("printf", "should be something or other: %d\n", a);
    }
}

Copy Propagation

This is a diff of a portion of 02-expr.dcf, found in our tests directory off of our Dataflow directory. Note the fact that several loads have been changed to load from the local variables at -36 and -32 on the stack.

> gdiff -u testcopy2.{unopt,opt}
--- testcopy2.unopt Sun Nov 28 19:16:47 1999
+++ testcopy2.opt   Sun Nov 28 19:18:00 1999
@ -56,19 +56,19 @
    sw $25,-36($30)
    lw $15,-36($30)
    sw $15,-28($30)
-   lw $15,-28($30)
+   lw $15,-36($30)
    sw $15,-16($30)
-   lw $15,-28($30)
+   lw $15,-36($30)
    lw $24,0($23)
    add $25,$15,$24
    sw $25,-32($30)
    lw $15,-32($30)
    sw $15,-24($30)

-   lw $15,-24($30)
+   lw $15,-32($30)
    sw $15,-12($30)
-   lw $15,-16($30)
+   lw $15,-36($30)
    sw $15,-20($30)
-   lw $15,-24($30)
+   lw $15,-32($30)
    sw $15,-28($30)
 label_1:
    nop     # test's epilogue

Dead Code Elimination

A sample of Decaf code containing dead code is provided below and in our repository under tests/03a-math-dead.dcf. We compiled this code with DCE turned both on and off, and we trimmed out the two offending dead code statements. The Code:

class Program
{
    void main ()
    {
        int i1, i2;
        i1 = -2147483647 - 1;
        callout("printf","min int operation: result should be -2147483648, is: %d\n",i1);
        i1 = (100-50)*2;
   callout("printf","paren assoc: result should be 100, is: %d\n",i1);
   i1 = 100 - 50 - 40;
        callout("printf","- assoc: result should be 10, is: %d\n",i1);
   i1 = 100 - 50 + 40;
        callout("printf","-,+ assoc: result should be 90, is: %d\n",i1);
   i1 = 100 - 5 * 4;
        callout("printf","- * assoc: result should be 80, is: %d\n",i1);
   i2 = 10 * 5 - 4;
        callout("printf","result should be 46, is: %d\n",i2);
   i1 = ----3;
i2 = 1 + 1;
        callout("printf","uminus: result should be 3, is: %d\n",i1);
   i1 = 3;
i1 = 3 + 4;
   i1 = i1 * i1 - -2;
        callout("printf","*, -, uses var: result should be 11, is: %d\n",i1);
        i1 = 3 * 4 - 2 * 5;
        callout("printf","*,- assoc: result should be 2, is: %d\n",i1);
    }

}

The diff:

--- 3a-opt      Mon Nov 29 10:32:10 1999
+++ 3a-unopt    Mon Nov 29 10:31:31 1999
@@ -143,6 +143,8 @@
li $24,1
add $25,$15,$24
sw $25,-96($30)
+       lw $15,-96($30)
+       sw $15,-12($30)
nop             # Function call: 2 args, 0 callersaves, 0 padding
nop             # Placement of arguments
lw $5,-16($30)
@@ -151,6 +153,8 @@
nop             # Clean up from callout
nop             # Function callout sequence completed
sw $2,-92($30)
+       li $15,3
+       sw $15,-16($30)
li $15,3
li $24,4
add $25,$15,$24