Examples of SSA based optimizers:
Global Value Numbering
• Global Value Numbering (GVN): Common Sub-expression
Elimination that does not depend on variable names.
– Assume that there is a table as a set of projections from
variables/expressions to their value numbers, such as { a ->
1, b -> 2, (⊕, 1, 2) -> 3 }, where each expression is
represented as a tuple with an operator and value numbers
of operands
– The uses of the same definition have the same value number.
– The left and right hand sides of a copy assignment such as
a = b have the same value number.
– Handling a statement x = a ⊕ b:
1. Search the value numbers of a and b in the table,
where let a and b be 1 and 2 respectively.
2. If (⊕, 1, 2) is found in the table, its value number is
assigned to x; otherwise, the new value number is
assigned to (⊕, 1, 2) and x.
An example of GVN
• GVN based on dominance relation：
copy propagation + redundancy elimination
t1=5
a1=x1+t1
s1=5
b1=x1+s1
q1=b1*5
p1=a1*5
t1=5
An example of GVN
• GVN based on dominance relation：
copy propagation + redundancy elimination
a1=x1+t1
a1=x1+5
s1=5
b1=x1+s1
q1=b1*5
p1=a1*5
t1=5
t1=5
a1=x1+5
An example of GVN
• GVN based on dominance relation：
copy propagation + redundancy elimination
a1=x1+5
s1=5
b1=x1+s1
q1=b1*5
p1=a1*5
t1=5
t1=5
a1=x1+5
a1=x1+5
s1=5
An example of GVN
• GVN based on dominance relation：
copy propagation + redundancy elimination
a1=x1+5
b1=x1+s1
b1=x1+5
b1=a1
q1=b1*5
p1=a1*5
t1=5
t1=5
a1=x1+5
a1=x1+5
s1=5
s1=5
b1=a1
An example of GVN
• GVN based on dominance relation：
copy propagation + redundancy elimination
a1=x1+5
q1=b1*5
q1=a1*5
p1=a1*5
t1=5
t1=5
a1=x1+5
a1=x1+5
s1=5
s1=5
b1=a1
b1=a1
q1=a1*5
An example of GVN
• GVN based on dominance relation：
copy propagation + redundancy elimination
a1=x1+5
q1=b1*5
q1=a1*5
p1=a1*5
p1=q1
t1=5
a1=x1+5
t1=5
s1=5
a1=x1+5
b1=a1
s1=5
q1=a1*5
b1=a1
p1=q1
q1=a1*5
© Copyright 2024 ExpyDoc
