CS 480: Translators

Winter Term, 2004, Professor Budd

Programming Assignment 5

Due Wednesday, March 3

Optimizations

When you are finished, hand in both the files Parser.java and Ast.java, which should be the only two files you modify for this assignment.

Start by adding the following method to the class Ast; you will subsequently override this in BinaryNode, UnaryNode, and FunctionCallNode:

	class Ast {
		
		public Ast optimize () { return this; }
	}

Optimization

In this assignment you will fill in the optimize methods in the subclasses of Ast. These methods should optimize an abstract syntax tree, returning a new tree. A call on this routine will then be inserted before you generate code for the left and right sides of an assignment statement, before you generate code for a function call in functionOrAssign, the expression returned by a return statement, and before you test the conditions in an if or while statement. Here are some examples:

	e.optimize().branchIfFalse(labOne);
	codeGen.genReturn(e.optimize());
	codeGen.genAssign(e.optimize(), f.optimize());

In general the idea will be to try to combine integer constants at compile time, try to move constants to the right and the top of an expression tree (so that they might be combined with other constants).

The optimizations you should recognize are the following:

• - c
  Unary negation of a constant, can be performed at compile time to create a new or real integer constant. The type should be the same as the original node.

• t + 0
  Adding an integer zero. Need not be performed, result should be just the left tree. However, the type should be changed to be the same as the type of the original addition node.

• c + c
  The addition of two integer constants. Can be replaced by the sum, computed at compile time.

• c + t
  Change to t + c, which might result in further optimizations.

• (t + c) + c
  The two constants can be combined. The resulting type should be unchanged.

• (t + c) + t2
  Move the constant up, so that the resulting tree is (t + t2) + c. The type associated with the topmost node should remain unchanged. The type associated with the new left node should be the same as the type of the root node.

• t + (t2 + c)
  Rearrange the expression, so that the resulting tree is (t + t2) + c. Again, the type of the root node should be unchanged. Again, just make the type of the new left child the same as the type of the root.

• t - c
  Change a subtraction of an integer constant into the addition of the negation. The result might be combined with later optizations.

• t * 0
  Multiplication by zero simply becomes zero. Type should be integer.

• t * 1
  Multiplication by one simply becomes the left argument. Type should be integer.

• c * c
  Multiplication of two integer constants can be performed at compile time.

• (t + c1) * c2
  We can distribute the muliplication and multiply the two constant values AT COMPile time, yielding t * c2 + c1 * c2. The latter can, of course, be computed at compile time. the type of the final result should be unchanged.

Consider an expression 3 + (4 + a) * 7. This would be optimized in the following fashion

	3 + (4 + a) * 7
	3 + (a + 4) * 7
	3 + (a * 7) + 28
	(a * 7) + 28 + 3
	(a * 7) + 31

I have selected only the most common transformations. Others that a real compiler might consider include transformations on floating values, transformations on unary operators (negating a constant, for example), and transformations on relationals and logical operators. In lecture I will discuss many other types of optimizations.

Although most of the work will be in the optimize method for binary nodes, the optimize method will impact every node class.

• Ast Default, simply return the node
• UnaryNode Optimize the child tree. Look for unary negation of integer constants. If so create a new integer constant. Otherwise, create a new Unary Node with the optimized child. Otherwise, create a new unary node with the same type and category as the current, but optimize the child.
• BinaryNode Optimize the two children, then look for the patterns described earlier. If none of these apply, return a new binary node with the same type and category, but the optimized children.
• FunctionCallNode Return a new function call node with the same return type, code and symbol table, but in which each of the parameters has been optimized.

Major Hint

You can make this assignment vastly easier by adding three protected functions to the class AST. The first returns true if the node is an integer constant, the second returns the integer value if it is a constant, and the third return a binary node if the receiver is a binary addition.