Lecture 16 - 480/580 (compiler construction)

Algebraic simplification

There are three topics we need to deal with for the remainder of the
course:
	* intermediate form generation
	* optimization
	* code generation

The problem is that these three are intimately tied together; and it is
difficult to discuss one without discussing the others.
Optimization, in particular, can be viewed at many levels.  One popular
compiler system (the Amsterdam Compiler Kit, or ACK) performs the following
eight steps (ref: CACM 26, 9, Sept 1983):

	preprocessing
	front end (parsing)
	peephole optimizer
	global optimizer
	back end (code generation)
	target optimizer
	assembler and linker

Of these steps, steps one and two covers everything we have done in this 
course up to now.  Three of these steps are optimization, two of which 
are based on a machine-independent internal form, and one of which is 
specific to the particular machine the compiler is working on.

The plan I have in mind is to continue a more or less chronological tour
through a compiler; that is, dicusss topics in the order that they would
occur in a real compiler.  However, since from now on these three topics
would be all mixed up, even in a real compiler, that means that from now on
in the course the topics will be mixed up as well.

Today I want to talk about algebraic simplification of abstract syntax
trees.  I do this because (1) it is your next programming assignment, so I
might as well get you thinking about it now, and (2) since it is an
optimization that is performed on the internal representation (AST's); it
would probably be done very early in a real compiler; unlike other
optimizations which are specific to machine instructions and thus
necessarily come later.

In your assignment I give you several different algebraic transformations that
could be made to trees.  We can think of these as patterns to be applied to
trees to give you other trees.

Let us take an example.  Suppose we have a declaration something like
the following:
var
    a : array [ 2 ... 40 ] of record
	  c: integer;
	  b: integer;
	end;

Let us consider the tree that would be generated for something like:

	a [ 4 + j].b

Assume a begins at 8(r6), and let j be a global variable.

	[ write tree ]
How might we optimize this ?

	rewrite 4 + j as j + 4
	rewrite -2 as + (-2)
	replace j + 4 + -2 with j + 2
	replace (j + 2) * 8 with j * 8 + 16
	replace j * 8 with j << 3
	linearize
	move shift down, 8 up
	replace 8 + 16 with 25
	replace 24 + 4 with 28

	Resulting expression (r6 + (@j << 3)) + 28
	This expression is considerably simpler than the original;
	and will generate many fewer instructions.

This problem shows optimization by pattern matching (we are looking for
patterns in the original tree, replacing it by other expression).
Pattern matching is important in compiler construction; in a way parsing is
simply just a matter of pattern matching.  We will see the technique of
pattern matching occur at least once more before we are done.

Before we leave this technique, let me mention some other patterns that
often occur and that a compiler might want to look for:

	(convertoreal integerconstant) => realconstant
	negate (constant * tree) => ((-constant) * tree) (same with division)
	t ** 2 => t * t
	2 * t => t + t
	t / 2 => t * 0.5


	Some optimizations might seem locally good, but might not be so
	good when viewed from a more global perspective.  For example,
	suppose we have:

		if (a-b < 0) then

	We might want to replace (a-b < 0) with (a>b), which would seem to
	do the same thing.  But if the preceeding statement had been:
		x := y * (a-b);
		if (a-b < 0)
	
	we might already have the computation of a-b lying around (say in a
	register) and thus the original might be the better form.

	Here is another common pattern:
		adr := adr + constant
	there is no reason to compute the address twice; nor, on many
	machines, to even compute the result in registers, we might want to
	internally represent this as:
		(adr address constant)
	Many machines make a special case out of 1, giving us:
		(incr address)


There are literally dozens of other patterns that might be useful or
important in a real system.