Pointer Assignments and Procedure Calls
Introduction: When we assign indirectly through a pointer, as in the assignments
x = *p
*q = y
we do not know what p or q point to. In effect, x = *p is a use of every variable whatsoever, and *q = y is a possible assignment to every variable. As a consequence, the operator =* must take all nodes that are currently associated with identifiers as arguments, which is relevant for dead-code elimination. More importantly, the *= operator kills all other nodes so far constructed in the DAG.
There are global pointer analyses one could perform that might limit the set of variables a pointer could reference at a given place in the code. Even local analysis could restrict the scope of a pointer. For instance, in the sequence
p = &x
*p = y
we know that x, and no other variable, is given the value of y, so we don't need to kill any node but the node to which x was attached.
Procedure calls behave much like assignments through pointers. In the absence of global data-flow information, we must assume that a procedure uses and changes any data to which it has access. Thus, if variable x is in the scope of a procedure P, a call to P both uses the node with attached variable x and kills that node.
Reassembling Basic Blocks from DAG's: After we perform whatever optimizations are possible while constructing the DAG or by manipulating the DAG once constructed, we may reconstitute the three-address code for the basic block from which we built the DAG. For each node that has one or more attached variables, we construct a three-address statement that computes the value of one of those variables. We prefer to compute the result into a variable that is live on exit from the block. However, if we do not have global live-variable information to work from, we need to assume that every variable of the program (but not temporaries that are generated by the compiler to process expressions) is live on exit from the block. If the node has more than one live variable attached, then we have to introduce copy statements to give the correct value to each of those variables.
Sometimes, global optimization can eliminate those copies, if we can arrange to use one of two variables in place of the other.
Example: Recall the DAG of Fig. 8.12, we decided that if b is not live on exit from the block, then the three statements
a = b c
d = a - d
c = d c
suffice to reconstruct the basic block. The third instruction, c = d c, must use d as an operand rather than b, because the optimized block never computes b. If both b and d are live on exit, or if we are not sure whether or not they are live on exit, then we need to compute b as well as d. We can do so with the sequence
a = b c
d = a - d
b = d
c = d c
This basic block is still more efficient than the original. Although the number of instructions is the same, we have replaced a subtraction by a copy, which tends to be less expensive on most machines. Further, it may be that by doing a global analysis, we can eliminate the use of this computation of b outside the block by replacing it by uses of d. In that case, we can come back to this basic block and eliminate b = d later. Intuitively, we can eliminate this copy if wherever this value of b is used, d is still holding the same value. That situation may or may not be true, depending on how the program recomputes d.
When reconstructing the basic block from a DAG, we not only need to worry about what variables are used to hold the values of the DAG's nodes, but we also need to worry about the order in which we list the instructions computing the values of the various nodes. The rules to remember are
1. The order of instructions must respect the order of nodes in the DAG. That is, we cannot compute a node's value until we have computed a value for each of its children.
2. Assignments to an array must follow all previous assignments to, or evaluations from, the same array, according to the order of these instructions in the original basic block.
3. Evaluations of array elements must follow any previous (according to the original block) assignments to the same array. The only permutation allowed is that two evaluations from the same array may be done in either order, as long as neither crosses over an assignment to that array.
4. Any use of a variable must follow all previous (according to the original block) procedure calls or indirect assignments through a pointer.
5. Any procedure call or indirect assignment through a pointer must follow all previous (according to the original block) evaluations of any variable.
That is, when reordering code, no statement may cross a procedure call or assignment through a pointer, and uses of the same array may cross each other only if both are array accesses, but not assignments to elements of the array.