Keywords

1 Introduction

An expression is partially redundant if the value computed by the expression is already available on some but not all paths in a DFG of a program to that expression. A PRE algorithm is a method for transforming partial redundancy of an expression in a DFG into fully redundancy and eliminates the redundancy. A PRE algorithm based on safe insertions is treated to be optimal if no other PRE algorithm that uses safe insertions gives a DFG which contains fewer computations (less insertions and more deletions) in any path.

Morel and Renvoise (MRA) [1] first proposed a bidirectional data flow analysis algorithm to eliminate partial redundancies. But it does not really eliminate all partial redundancies in a program, and it lacks both computational and lifetime optimality as well. As MRA fails to split edges, optimization is not possible in many loops. Though Dhamdhere [2, 3] through edge placement algorithm (EPA) performs insertions both in nodes and on edges in a DFG, he cannot completely eliminate redundant code motion. EPA does not provide lifetime optimality in many cases too.

It is already shown by Vineeth Kumar that the papers [4,5,6,7] have one or more of the problems of redundant code motion, unremoved redundancies, or limited applicability due to reducibility restriction of the flow graph.

The PRE algorithm developed by Vineeth Kumar [8] does not give much importance for eliminating edge splitting(s), and the edge splitting is more expensive than inserting a computation at an existing node of a DFG though. The insert equation of the PRE algorithm for an expression at a nodei in a DFG returns true only if the nodei computes the expression concerned, otherwise it returns false. This may lead to unnecessary edge splitting(s). This paper enriches the insert equation of the PRE algorithm to avoid the edge splitting as much as possible.

2 PRE Algorithm by Vineeth Kumar Paleri

Vineeth Kumar Paleri, YN Srikant, and Priti Shankar proposed a unidirectional data flow analysis algorithm for PRE titled “PRE: a simple, pragmatic, and provably correct algorithm.” As the name suggests the algorithm is really simple and computationally and lifetime optimal. The algorithm assumes that all local redundancies are already eliminated by using standard techniques for common subexpression elimination on the basic blocks [9]. The algorithm utilizes the concepts of availability, anticipability, safe partial availability, and safe partial anticipability.

An expression is available at a program point p, if it is computed along all paths from the start node to p without a modification to any of its operands since the last computation, and it is partially available at p if it is computed at least along any path. An expression is anticipated at p if all paths from p have a computation of that expression from the values of the operands of the expression available at p, and it is partially anticipated if it is computed at least along any path from p. A program point is safe for an expression if it is either available or anticipated at that point.

Safe partial availability needs all points on the path along which the computation is partially available to be safe, and safe partial anticipability needs all points on the path along which the computation is partially anticipated to be safe.

The local data flow property ANTLOCi represents a locally anticipated upward exposed expression e in nodei, COMPi represents a locally available downward exposed e in nodei, and TRANSPi reflects the absence of assignments to the operand(s) of e in nodei. The global properties of availability, anticipability, safe partial availability, and safe partial anticipability are used to collect global information. INSERTi and INSERT(i, j), identify e to be inserted in nodei, and on edge (i, j), respectively, and REPLACEi identifies e to be replaced in nodei with a temporary variable, say t. The INSERTi and INSERT(i, j) equations of the PRE algorithm are as follows:

$$ {\text{INSERT}}_{i} = {\text{COMP}}_{i} \cdot {\text{SPANTOUT}}_{i} \neg \left( {{\text{TRANSP}}_{i.} {\text{SPAVIN}}_{i} } \right). $$
(1)
$$ {\text{INSERT}}_{(i,j)} = \neg {\text{SPAVOUT}}_{i} {\text{SPAVIN}}_{j} {\text{SPANTIN}}_{j} $$
(2)

2.1 An Example

Figure 1a shows a DFG with 6 nodes, and Fig. 1b is a DFG after applying the PRE algorithm. The algorithm inserts a computation at nodes n1 and n5 with the Eq. (1). Here, the algorithm fails to insert a computation at the node n2 as it does not contain the computation a * b. So the algorithm splits the edges (n2, n3) and (n2, n6) for inserting a node in each edge with the Eq. (2) in order to make the expression fully redundant along all paths to n4 and n6.

Fig. 1
figure 1

Partial redundancy elimination using PRE algorithm

Full size image

3 A Supplement to PRE Algorithm

As the PRE algorithm inserts a computation at a node only if the node contains a computation of the expression, it leads to edge splitting as shown in Fig. 1b. Being the edge splitting is very expensive as compared to inserting a computation at a node already existing in a DFG, the INSERT equation of the PRE algorithm is modified by using a program segment code without sacrificing the algorithm’s computational and lifetime optimality. The program segment is as follows:

where j is a predecessor of the nodei, and all other equations of the PRE algorithm remain the same.

3.1 An Example

Consider Fig. 1a again. Figure 2 is the DFG after applying the new program code. Note that it has only three insertions and four replacements without any edge splitting.

Fig. 2
figure 2

Partial redundancy elimination using new program segment code

Full size image

4 Conclusion

The goal of this paper stated in the introduction is to eliminate the edge splitting as far as possible. As the insert equation of the PRE algorithm by Vineeth Kumar fails to take care of eliminating the edge splitting much, this paper, by simply updating the INSERT equation of the PRE algorithm, eliminates the edge splitting of the DFG of a program as far as possible, and hence the PRE algorithm is now more clever and attractive without sacrificing the algorithm’s computational and lifetime optimality.