Global Value Numbering on SSA representation based on Redundancy Class

[Ajit Kumar Agarwal <ajit dot kumar dot agarwal at xilinx dot com>]

Hello All:

Please find the different Global Value numbering techniques on SSA representation  and proposing in GCC Global Value Numbering on SSA representation based on Redundancy Class. Can this be proposed.

SSA representation with control graph can be formulated with Global Value Numbering Algorithm. The GVN Algorithm assigns the value numbers for the expression based on hashing, value partitioning, SCC on SSA Graph and Dominator. Value partitioning is based on congruent classes and the Dominator is based on traversing the dominator tree in reverse post order and assign the values to the expression. The SCC based on SSA graph is based on traversing the SSA graph in reverse post order and assign the value numbers based on optimistic and valid table.

Different optimization based on GVN are useful like redundant expression elimination, redundant load and stores , Common Sub expression elimination, reassociation and value redundancy.

Global value numbering is proposed on redundancy class assign to expression based on renaming scheme on SSA representation. The variable renaming scheme is extended to expressions in the SSA representation. The redundancy class along with the SSA graph and the SCC representation of the SSA Graph is proposed in this paper. The redundancy class concept is taken from the Fred Chow paper on PRE on SSA. Based on the redundancy class new set of nodes like phi are inserted which takes the operands as redundancy class and this set of phi nodes are used along with redundancy class number are used using the optimistic table and the valid table as suggested by Simpson on value numbering on SCC based SSA Graphs.

This will help to perform the optimization as mentioned above in the SSA representation.

 Value based partitioning:

Value based partitioning assigns the values based on partitoning the congruent classes. Two expressions are congruent if they have same opcode and each operand has to be congruent. This is the recursive based definition. Based on the congruency initial partition is created which keep on growing with different iterations till the partitions became stable.

For the expressions given below:

A= x - y

B = y - x

C = A + B

For the expressions above the initial partition created with {x}, {y}, { A, B, C}. Then the algorithm will work as follows. The worklist will be the set of the congruence class. For each class like {x} is selected. For x the derivation is A and the position of A is subset of the class {A,B,C} then the new partition will be created{A}. Similarly the {B} and {C} partition are created and added to the worklist and the above algorithm continues till the partitions become stable. So the final partitions will be {x},{y},{A},{B},{C}.

SCC based value numbering on SSA Graph

The SCC(strongly connected component) is found on the SSA graph with cycle. The Set of nodes in each SCC will be a single node in the cycle. For such strongly connected component mapped to single nodes, each node will be traversed and the value numbers are assigned.

For following SSA representation of the control flow graph 

i0 = 1

j0 = 1

while(..)

{

i1 = phi(i0, i2)

j1 = phi(j0,j2)

i2 = i1 +1

j2 = j1 +1

}
For the above example the SSA graph will be formed with Strongly connected component with the cycle and the each node of the SCC will be traversed.

Traversing the SSA graph in reverse post order for variable i the initial value is 1 which will be added to optimistic table so the lattice initial value is 1. At the point of i1 = phi(i0,i2) 1 will be added to optimistic table and assign the value of i1. At the first iteration i2 will be 2 as the initial value of i1 is propagated. In the second iteration the i1 = phi(i0,i2) will be added to the optimistic table and assign the value i1.

Traversing the SSA graph in reverse post order for variable j the initial value is 1 and j1 will be 1 at the first iteration. Since the value of i1 is assigned 1 and j is hashed to same value j1 will be equal to i1. At the first iteration j2 will be 2 and j2 will be i2 as same value is hashed. In the second iteration the j1 = phi(j0,j2) will become i1 = phi(i0,i2) and this entry is already mapped to optimistic table. This leads to i is congruent to j . so the same value is assigned to i and j and the optimization will remove the jth entry and related phi node for jth entry.

 Global Value Numbering based on redundancy class

The redundancy class is formed as given in PRE on SSA by Fred Chow using SSA variable renaming. The SSA variables used to form the expressions is assigned the redundancy class similar to renaming scheme of SSA variables. 

For the following example:

i0 = 1

j0 = 1

while(..)

{

i1 = phi(i0, i2)

j1 = phi(j0,j2)

i2 = i1 +1

j2 = j1 +1

}

The above SSA program is represented with redundancy class and the new phi node based on the redundancy class.
The above SSA program is modified as follows

i0 = 1

j0 = 1

while(..)

{

i1 = phi(i0, i2)

r1 = new_phi(r0,r2)

j1 = phi(j0,j2)

p1 = new_phi(p0,p2)

i2 = i1 +1(redundancy class r2)

j2 = j1 +1(redundancy class p2)

}

The r0 is the redundancy class for the initial value of i0 and the r2 is the redundancy class for the expression i1+1. Similarly the p0 is the redundancy class for the initial value of j0 and the p2 is the redundancy class for j1+1.

Using the redundancy class the expressions and the operands used for the expression in the redundancy class is populated. Once the operands and the SSA variables names of the operands of the expression is populate the algorithm using the optimistic table and the valid table is populated as given above in the Section SCC based GVN on SSA graph. There will one level of indirection and the optimistic and valid table will have new phi nodes and the SSA graph is traversed using reverse post order. This will help to form the congruent class for the variable i and j as given above in Section II.

For the expressions with the same operands constitute the expression will have same redundancy class and form the basis of congruency.

Traversing the SSA graph in reverse post order for new_phi node for redundancy class r the initial value is 1 which will be added to optimistic table so the lattice initial value is 1. At the point of r1 = new_phi(r0,r2) 1 will be added to optimistic table and assign the value of r1. At the first iteration r2 which will be the second operand of the new_phi node for r will be 2 as the initial value of r1 is propagated. In the second iteration the r1 = new_phi(r0,r2) will be added to the optimistic table and assign the value r1.

Traversing the SSA graph in reverse post order for new_phi node for redundancy class p the initial value is 1 and p1 will be 1 at the first iteration. Since the value of r1 is assigned 1 and p1 j is hashed to same value p1 will be equal to r1. At the first iteration which will be second operand of new_phi node for p , p2 will be 2 and p2 will be r2 as same value is hashed. In the second iteration the p1 = new_phi(p0,p2) will become r1 = new_phi(r0,r2) and this entry is already mapped to optimistic table. This leads to r is congruent to p . so the same value is assigned to i and j and the optimization will remove the jth entry and related phi node for jth entry since the redundancy class remains congruent.

The alternate algorithm will be traversing the dominator tree in reverse postorder and search for new phi node inserted for redundancy class. With the help of data structure having redundancy class mapping to the expression and the operands of the expressions.

The GVN keeps the values numbering information which is useful for the optimization performed like redundant expressions, common sub expression elimination and also the redundant load and store. The main advantages of GVN based on redundancy class over the value partitioning, hashing and also the SCC based numbering is after the PRE is performed on SSA representation the redundant expression that are partial redundant become fully redundant. The fully redundancy is part of PRE transformation. The same redundancy class that are formed as part of PRE can be used further for Global Value numbering and the optimization with respect to redundant load and stores, redundant expressions and common sub expression elimination can be performed on the redundancy class and the numbering scheme based on redundancy class.

The value driven redundancy elimination cause the register pressure to be high for some cases and this can be reduced by Live range shrinking and rematerialization as proposed by Simpson thesis.

Thanks & Regards
Ajit