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
