Algorithms for Compiler Design

There are three main difficulties that we face when attempting to generate efficient object code, namely:

1. Selection of the most-efficient instructions to represent the computation specified by the three-address statement;

2. Deciding on a computation order that leads to the generation of the more-efficient object code; and

3. Deciding which registers to use.

Selecting the Most-Efficient Instructions to Represent the Computation Specified by the Three-Address Statement

Many machines allow certain computations to be done in more than one way. For example, if a machine permits an instruction AOS for incrementing the contents of a storage location directly, then for a three-address statement a = a + 1, it is possible to generate the instruction AOS a, rather than a sequence of instructions like the following:

MOVE a, R
 ADD #1, R
 MOVE R, a

Now, deciding which instruction sequence is better is the problem. This decision requires an extensive knowledge about the context in which these three-address statements will appear.

Deciding on the Computation Order that Will Lead to the Generation of More-Efficient Object Code

Some computation orders require fewer registers to hold intermediate results than others. Now, deciding the best order is very difficult. For example, consider the basic block:

If the order of computation used is the one given in the basic block t1-t2-t3-t4, then the number of registers required for holding the intermediate result is more than when the order t2-t3-t1-t4 is used.

Deciding on Registers

Deciding which register should handle the computation is another problem that stands in the way of good code generation. The problem is further complicated when a machine requires register-pairs for some operands and results.