Local optimization of Three-Address-Code

Some compilers are using Three-Address-Code (TAC) as an intermediate representation. This representation is very simple to understand and write. Moreover, it's easy to run some optimization on this representation.

Each TAC statement has this general form : result = operand1 operator operand2

For example, here are some TAC statements:

a = 1
x = a * 3
if x > a goto test
param "dddd"
call print
test:
param "asdf"
call print

In this post, we will see some of the local optimizations that can be applied on TAC. A local optimization is an optimization that is applied locally to a basic block. A basic block is a set of TAC statements that has only one entry point and one exit point. Once the first instruction of the basic block is executed, the rest of the instructions are necessarily executed exactly once. These optimizations are easy to design and implement. If you want to run global optimizations (through all the basic blocks of a function) or even Interprocedural Optimization (IPO), you will need a far more complex framework to run optimizations. I will try to write something on global optimization when I will have implemented some of them in EDDI.

The goal of optimization is of course to replace some statements with more efficient statements.

The list presented in this post is not exhaustive, this is only the optimizations that I've implemented in EDDIC, but this represent most of the local optimizations.

The first three optimization techniques can be applied independently on each statement of the program.

1. Arithmetic Identities

The first optimization is about arithmetic identities. There are some properties in math that we can use to simplify simple TAC statement.

Here are all the identities that are simplified in EDDIC:

• x = a + 0 or x = 0 + a => x = a
• x = a - 0 => x = a
• x = 0 - a => x = -a
• x = a - a => x = 0
• x = a * 1 or x = 1 * a => x = a
• x = a * 0 or x = 0 * a => x = 0
• x = a * -1 or x = -1 * a => x = -a
• x = a / 1 => x = a
• x = a / -1 => x = -a
• x = 0 / a => x = 0
• x = a / a => x = 1

All the expressions on the right are more efficient to compute than the one on the left.

2. Reduce in strength

Another easy optimization is the reduction of strength of some math operations. For example, an addition is cheaper than multiplication and multiplication is cheaper than division. If your language does not have floating point math, the only reduction that can be done is this one:

Here are all the identities that are simplified in EDDIC:

• x = 2 * a or x = a * 2 => x = a + a

With floating point math, we can do a little better:

• x = a / 2 => x = a * 0.5
• x = a / 4 => x = a * 0.25
• etc...

3. Constant folding

When both operands on the right side of the TAC statement are integers, we can replace the math operation directly by the result of the computation.

With a and b being any integer, we can transform these TAC statements:

• x = 1 + 2 => x = 3
• x = 3 - 1 => x = 2
• x = 3 * 2 => x = 6
• x = 5 / 2 => x = 2
• x = 5 % 2 => x = 1

We can also use this optimization to simplify conditional jumps. For example, if 3 > 2 goto B2 can be replaced by goto B2.

More than being way more efficient statements, it also enables other optimization to be performed on the TAC program.

The next two optimizations cannot be made on each statement independently. They have to be made on each basic blocks. They are replacing some variables by other variables or values.

4. Constant propagation

This optimization consists in replacing a variable by its constant value at each place we know it's constant. For example, this basic block:

a = 2
b = c * a 
a = 5
a = a + b
c = a + 2

can be optimized into:

a = 2
b = c * 2
a = 5
a = 5 + b
c = a + 2

Two use of a variable have been replaced by its value. In this case, we cannot replace the last use of a because we do not know its value there.

This optimization can be made using a simple algorithm on each statement of a basic block:

1. If the statement is of the form x = constant, c[x] = constant
2. If the statement is of the form x = a + b, c[x] = null
3. For each variable appearing in an operand of a statement, if c[x] is not null, replace the variable by c[x]

5. Copy propagation

Copy propagation is almost the same as constant propagation. We replace a variable by the variable it refers to. For example, we can optimize:

b = a
c = b + 2

into:

b = a
c = a + 2

The algorithm is the same as the one for constant propagation but we keep track of the variables that are assigned to a variable.

These two optimizations does not create a more efficient code, but the optimized code can be optimized again.

6. Remove assign

We can often find some assigns that are useless in a basic blocks. There are three types of assigns that can be removed:

1. x = x is never useful
2. An assignment to a temporary variable that is not used after this assignment is not useful. A temporary is a variable created by the compiler to perform some complex expressions. They are not stored and are used only within one basic block, so its value is not useful after the basic block.
3. An assignment to x following another assignment to x, with no use of x between the two assignments, is not useful.

7. Remove temporaries

When compiling some expression, we often generate this kind of code:

t1 = a + b
x = t1

We can simplify this code into:

x = a + b

For that optimization, we can apply a more complex propagation. For each assignment to a temporary, we store the right side of the assignment. Then, for each assignment of a temporary to another variable (x = t1) if this use of the temporary is the only one, we replace the right side by the right side of the assignment to the temporary.

8. Remove needless jumps

We can also find some jumps from basic blocks to basic that are not useful. A jump (conditional or not) to the next basic blocks is not useful. If we have two basic blocks:

B1:
a = 2
goto B2
B2: 
b = a

we can optimize into:

B1:
a = 2
B2: 
b = a

For that optimization, we have to test each jump for the distance of the target block. If the distance is only one, we can remove the jump. This works also for conditional jumps. A conditional has two exit points. If the condition is true, we jump to the specified block, otherwise we jump to the next block. If the target block is the next one, the effect is the same has a non-conditional jump and then can be removed.

The last two optimizations are not really local, but are simple versions of global optimizations. There are not as powerful as they are not following a data-flow, but they can be greatly improve the efficiency of some function, even if they don't have the power of the equivalent global optimization.

9. Remove dead basic blocks

Sometimes after having simplified some conditional jumps into simple jumps or even removed some of them, some basic blocks are not reachable. For example, this set of basic block:

B1:
a = 2
goto B3
B2: 
b = a
B3:
b = 33

can be optimized into:

B1:
a = 2
goto B3
B3:
b = 33

There are no general algorithm for applying that. It depends on the instruction set that you TAC language has.

10. Merge basic blocks

Finally, another optimization, not really local again, is to merge some basic blocks. After the basic blocks have been optimized, we often have some blocks that are redundant. For example:

B1:
a = 2
B2: 
b = a

can be optimized into:

B1:
a = 2
b = a

Of course, the second basic block that is merged with the first one must not be referred by a jump.

Optimization passes

When you have ten optimization techniques, you will have to find a way to make them interact correctly. As you certainly saw on the examples, some of the optimized sample can be optimized again with another optimization.

There are no general algorithm to make all optimization techniques work together in an optimal way. I chose a simple technique in EDDI. All the techniques are run on the complete code one after another. Then, if one or more techniques have had an effect on the program, we run again all the optimization techniques. So the optimizations run until there are no more changes to the program.

Conclusion

By using all the techniques described in this post, you will be able to have an efficient code. It won't be as good as with local optimization coupled to global optimization, but it's a good start for a simple compiler.

I hope I will have the time to implement some global optimization techniques into eddic and then write about it on this blog.

Related articles