Introduction: Optimization is the process of transforming a piece of code to make more efficient (either in terms of time or space) without changing its output or side-effects. The only difference visible to the code’s user should be that it runs faster and/or consumes less memory. It is really a misnomer that the name implies you are finding an "optimal" solution— in truth, optimization aims to improve, not perfect, the result.

We can often obtain a substantial improvement in the running time of code merely by performing local optimization within each basic block by itself. More thorough global optimization, which looks at how information flows among the basic blocks of a program, is covered in later chapters, starting with Chapter 9. It is a complex subject, with many different techniques to consider.

The DAG Representation of Basic Blocks: Many important techniques for local optimization begin by transforming a basic block into a DAG (directed acyclic graph). In Section 6.1.1, we introduced the DAG as a representation for single expressions. The idea extends naturally to the collection of expressions that are created within one basic block. We construct a DAG for a basic blockas follows:

1.  There is a node in the DAG for each of the initial values of the variables appearing in the basic block.

2. There is a node N associated with each statement s within the block. The children of N are those nodes corresponding to statements that are the last definitions, prior to s, of the operands used by s.

3.  Node N is labeled by the operator applied at s, and also attached to N is the list of variables for which it is the last definition within the block.

4.  Certain nodes are designated output nodes. These are the nodes whose variables are live on exit from the block; that is, their values may be used later, in another block of the flow graph. Calculation of these "live variables" is a matter for global flow analysis, discussed in Section 9.2.5.

The DAG representation of a basic block lets us perform several code improving transformations on the code represented by the block.

a)  We can eliminate local common subexpressions, that is, instructions that compute a value that has already been computed.

b)  We can eliminate dead code, that is, instructions that compute a value that is never used.

c)  We can reorder statements that do not depend on one another; such reordering may reduce the time a temporary value needs to be preserved in a register.

d)  We can apply algebraic laws to reorder operands of three-addaddress instructions, and sometimes thereby simplify the computation.

Finding Local Common Subexpressions: Common subexpressions can be detected by noticing, as a new node M is aboutto be added, whether there is an existing node N with the same children, inthe same order, and with the same operator. If so, TV computes the same valueas M and may be used in its place. This technique was introduced as the"value-number" method of detecting common subexpressions in Section 6.1.1.

Example: A DAG for the block

a = b c

b = a - d

c = b c

d = a - d

is shown in Fig. 8.12. When we construct the node for the third statement c = b c, we know that the use of b in b c refers to the node of Fig. 8.12 labeled -, because that is the most recent definition of b. Thus, we do not confuse the values computed at statements one and three.

However, the node corresponding to the fourth statement d = a - d has the operator - and the nodes with attached variables a and do as children. Since the operator and the children are the same as those for the node corresponding to statement two, we do not create this node, but add d to the list of definitions for the node labeled.

It might appear that, since there are only three nonleaf nodes in the DAG of Fig. 8.12, the basic block in Example 8.10 can be replaced by a block with only three statements. In fact, if b is not live on exit from the block, then we do not need to compute that variable, and can use d to receive the value represented by the node labeled —. in Fig. 8.12. The block then becomes However, if both b and d are live on exit, then a fourth statement must be used to copy the value from one to the other.

Previous Next