SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Revisiting Out-of-SSA Translation
for Correctness, Code Quality, and Efficiency
Benoit Boissinot (LIP), Alain Darte (LIP),
Benoı̂t Dupont de Dinechin (STMicro),
Christophe Guillon (STMicro), Fabrice Rastello (LIP)
Compsys Team
Laboratoire de l’Informatique du Parallélisme (LIP)
École normale supérieure de Lyon

CGO’09, March 24, 2009, Seattle, WA

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Outline1

SSA foundations
Out-of-SSA translation

2

Correctness and code quality
Translation with copy insertions
Improving code quality
Qualitative experiments

3

Speed and memory footprint
Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

4

Conclusion

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Out-of-SSA translation

Outline1

SSA foundations
Out-of-SSA translation

2

Correctness and code quality
Translation with copy insertions
Improving code quality
Qualitative experiments

3

Speed and memory footprint
Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

4

Conclusion

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Out-of-SSA translation

Static single assignment (SSA)
SSA with dominance property
Unique definition for each variable;
Each definition dominates its uses.

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Out-of-SSA translation

Static single assignment (SSA)
SSA with dominance property
Unique definition for each variable;
Each definition dominates its uses.

a = ...
b = ...
B0

B1

n=b
b=a
a=n

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Out-of-SSA translation

Static single assignment (SSA)
SSA with dominance property
Unique definition for each variable;
Each definition dominates its uses.
Conversion into SSA
Need to introduce φ-functions atdominance frontier.

a = ...
b = ...
B0

B1

n=b
b=a
a=n

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Out-of-SSA translation

Static single assignment (SSA)
SSA with dominance property
Unique definition for each variable;
Each definition dominates its uses.
Conversion into SSA
Need to introduce φ-functions atdominance frontier.

Benoit Boissinot

a1 = . . .
b1 = . . .
B0

B1
a2 = φ(a1 , a3 )b2 = φ(b1 , b3 )n = b2b3 = a2
a3 = n

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Out-of-SSA translation

Static single assignment (SSA)
SSA with dominance property
Unique definition for each variable;
Each definition dominates its uses.
Conversion into SSA
Need to introduce φ-functions atdominance frontier.
Interests of SSA
Code optimizations: efficient,easy-to-implement, fast;

a1 = . . .
b1 = . . .
B0

B1
a2 = φ(a1 , a3 )b2 = φ(b1 , b3 )n = b2b3 = a2
a3 = nTwo-phases register allocation;
Program analysis/verification.
Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Out-of-SSA translation

Static single assignment (SSA)
SSA with dominance property
Unique definition for each variable;
Each definition dominates its uses.
Conversion into SSA
Need to introduce φ-functions atdominance frontier.

a1 = . . .
b1 = . . .
B0

B1
a2 = φ(a1 , b2 )b2 = φ(b1 , a2 )Interests of SSA
Code optimizations: efficient,easy-to-implement, fast;Two-phases register allocation;
Program analysis/verification.
Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Out-of-SSA translation

Why is out-of-SSA translation difficult?
Swap problem
Cytron et al. (1991): copies inpredecessor basic blocks.

a1 = . . .
b1 = . . .
B0

B1
a2 = φ(a1 , b2 )b2 = φ(b1 , a2 )Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Out-of-SSA translation

Why is out-of-SSA translation difficult?
Swap problem
Cytron et al. (1991): copies inpredecessor basic blocks.

B0

a1 = . . .
b1 = . . .
a2 = a1b2 = b1

B1
a2 = φ(a1 , b2 )b2 = φ(b1 , a2 )a2 = b2
b2 = a2

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Out-of-SSA translation

Why is out-of-SSA translation difficult?
Swap problem
Cytron et al. (1991): copies inpredecessor basic blocks. Incorrect!

B0

Bad understanding of parallel copies.

a1 = . . .
b1 = . . .
a2 = a1b2 = b1

B1

a2 = b 2
b2 = a2

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Out-of-SSA translation

Why is out-of-SSA translation difficult?
Lost copy problem
Cytron et al. (1991): copies inpredecessor basic blocks. Incorrect!

x = ...
B0

Bad understanding of parallel copies.
B1
y =x
x =x +1yBenoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Out-of-SSA translation

Why is out-of-SSA translation difficult?
Lost copy problem
Cytron et al. (1991): copies inpredecessor basic blocks. Incorrect!

x1 = . . .
B0

Bad understanding of parallel copies.
B1
x2 = φ(x1 , x3 )y = x2x3 = x2 + 1

yBenoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Out-of-SSA translation

Why is out-of-SSA translation difficult?
Lost copy problem
Cytron et al. (1991): copies inpredecessor basic blocks. Incorrect!

x1 = . . .
B0

Bad understanding of parallel copies.
B1
x2 = φ(x1 , x3 )x3 = x2 + 1

x2

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Out-of-SSA translation

Why is out-of-SSA translation difficult?
Cytron et al. (1991): copies inpredecessor basic blocks. Incorrect!
Bad understanding of parallel copies.

Lost copy problem
x1 = . . .
x2 = x1

B0

B1
x2 = φ(x1 , x3 )x3 = x2 + 1
x2 = x3

x2

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Out-of-SSA translation

Why is out-of-SSA translation difficult?
Cytron et al. (1991): copies inpredecessor basic blocks. Incorrect!
Bad understanding of parallel copies;
Bad understanding of critical edges andinterferences.

Lost copy problem
x1 = . . .
x2 = x1

B0

B1

x3 = x2 + 1
x2 = x3

x2

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Out-of-SSA translation

Why is out-of-SSA translation difficult?
Cytron et al. (1991): copies inpredecessor basic blocks. Incorrect!
Bad understanding of parallel copies;
Bad understanding of critical edges andinterferences.

Briggs et al. (1998): both problems
identified. General correctness unclear.

Lost copy problem
x1 = . . .
x2 = x1

B0

B1

x3 = x2 + 1
x2 = x3

x2

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Out-of-SSA translation

Why is out-of-SSA translation difficult?
Cytron et al. (1991): copies inpredecessor basic blocks. Incorrect!
Bad understanding of parallel copies;
Bad understanding of critical edges andinterferences.

Briggs et al. (1998): both problems
identified. General correctness unclear.
Sreedhar et al. (1999): correct but
handling of complex branching
instructions unclear;interplay with coalescing unclear;“virtualization” hard to implement.

Benoit Boissinot

Lost copy problem
x1 = . . .
x2 = x1

B0

B1

x3 = x2 + 1
x2 = x3

x2

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Out-of-SSA translation

Why is out-of-SSA translation difficult?
Cytron et al. (1991): copies inpredecessor basic blocks. Incorrect!
Bad understanding of parallel copies;
Bad understanding of critical edges andinterferences.

Briggs et al. (1998): both problems
identified. General correctness unclear.
Sreedhar et al. (1999): correct but
handling of complex branching
instructions unclear;interplay with coalescing unclear;“virtualization” hard to implement.

Lost copy problem
x1 = . . .
x2 = x1

B0

B1

x3 = x2 + 1
x2 = x3

x2* Many SSA optimizations turned off in gcc and Jikes.
Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Translation with copy insertions
Improving code quality
Qualitative experiments

Outline1

SSA foundations
Out-of-SSA translation

2

Correctness and code quality
Translation with copy insertions
Improving code quality
Qualitative experiments

3

Speed and memory footprint
Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

4

Conclusion

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Translation with copy insertions
Improving code quality
Qualitative experiments

Going to CSSA (conventional SSA)

Conventional SSA (CSSA)

From SSA to CSSA

For any φ-function
a0 = φ(a1 , . . . , an ), the variables
a0 , . . . , an can be safely replaced
by a common ressource.

B1

B0

Benoit BoissinotBia0 = φ(a1 , . . . , an )Revisiting Out-of-SSA Translation

Bn

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Translation with copy insertions
Improving code quality
Qualitative experiments

Going to CSSA (conventional SSA)

Conventional SSA (CSSA)

From SSA to CSSA

For any φ-function
a0 = φ(a1 , . . . , an ), the variables
a0 , . . . , an can be safely replaced
by a common ressource.
Correctness
Add copies with new local
variables around every φ.
=⇒ CSSA

Benoit Boissinot

B0

B1

Bi

Bn

a10 = a1

ai0 = aian0 = ana00 = φ(a10 , . . . , an0 )a0 = a00

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Translation with copy insertions
Improving code quality
Qualitative experiments

Code quality

Removing copies
Useless copies can be removed by standard aggressive coalescing.
Using an accurate notion of interference (value-based) gives
excellent results.

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Translation with copy insertions
Improving code quality
Qualitative experiments

Code quality

Removing copies
Useless copies can be removed by standard aggressive coalescing.
Using an accurate notion of interference (value-based) gives
excellent results.
“Liveness of φ” defined by the ai0 . ? Be careful with potential bugs
due to conditional branches that use or define variables.

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Translation with copy insertions
Improving code quality
Qualitative experiments

Coalesced example: the swap problem
a1 = . . .
b1 = . . .
B0

B0

B1

a1 = . . .
b1 = . . .
(u1 , v1 ) = (a1 , b1 )B1
a2 = φ(a1 , b2 )b2 = φ(b1 , a2 )u0 = φ(u1 , u2 )v0 = φ(v1 , v2 )(a2 , b2 ) = (u0 , v0 )(u2 , v2 ) = (b2 , a2 )Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Translation with copy insertions
Improving code quality
Qualitative experiments

Coalesced example: the swap problem

B0a1

u = (u0 , u1 , u2 )a1 = . . .
b1 = . . .
(u1 , v1 ) = (a1 , b1 )a2

B1
u0 = φ(u1 , u2 )v0 = φ(v1 , v2 )(a2 , b2 ) = (u0 , v0 )b1

v = (v0 , v1 , v2 )b2

Benoit Boissinot(u2 , v2 ) = (b2 , a2 )Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Translation with copy insertions
Improving code quality
Qualitative experiments

Coalesced example: the swap problem

B0a1

u = (u0 , u1 , u2 )a1 = . . .
b1 = . . .
(u1 , v1 ) = (a1 , b1 )a2

B1
u0 = φ(u1 , u2 )v0 = φ(v1 , v2 )(a2 , b2 ) = (u0 , v0 )b1

v = (v0 , v1 , v2 )b2

(u2 , v2 ) = (b2 , a2 )Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Translation with copy insertions
Improving code quality
Qualitative experiments

Coalesced example: the swap problem
a1 = . . .
b1 = . . .
B0

B0

B1

B1

a1 = . . .
b1 = . . .
(u1 , v1 ) = (a1 , b1 )u0 = φ(u1 , u2 )v0 = φ(v1 , v2 )(a2 , b2 ) = (u0 , v0 )(u2 , v2 ) = (b2 , a2 )

(u2 , v2 ) = (b2 , a2 )Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Translation with copy insertions
Improving code quality
Qualitative experiments

Coalesced example: the swap problem
a1 = . . .
b1 = . . .

a1 = . . .
b1 = . . .

B0

B0

B1

B1

n = b1b 1 = a1
a1 = n(u2 , v2 ) = (b2 , a2 )Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Translation with copy insertions
Improving code quality
Qualitative experiments

Coalesced example: the lost copy problem
x1 = . . .
B0x1 = . . .
u1 = x1

B0

B1

B1
x2 = φ(x1 , x3 )u0 = φ(u1 , u2 )x2 = u0x3 = x2 + 1

x3 = x2 + 1

u2 = x3

x2

x2

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Translation with copy insertions
Improving code quality
Qualitative experiments

Coalesced example: the lost copy problem
x1 = . . .
u1 = x1

B0x1

u = (u0 , u1 , u2 ) x3

B1
u0 = φ(u1 , u2 )x2 = u0x3 = x2 + 1

x2

u2 = x3

x2

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Translation with copy insertions
Improving code quality
Qualitative experiments

Coalesced example: the lost copy problem
x1 = . . .
u1 = x1

B0x1

u = (u0 , u1 , u2 ) x3

B1
u0 = φ(u1 , u2 )x2 = u0x3 = x2 + 1

x2

u2 = x3

x2

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Translation with copy insertions
Improving code quality
Qualitative experiments

Coalesced example: the lost copy problem
x1 = . . .
B0

B0

B1

B1

x1 = . . .
u1 = x1

u0 = φ(u1 , u2 )x2 = u0x3 = x2 + 1

x2 = x1
x1 = x2 + 1

u2 = x3

x2

x2

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Translation with copy insertions
Improving code quality
Qualitative experiments

Exploiting SSA: value-based interferences
Definition (Chaitin interference)
Two variables interfere if one is liveat the definition of the other, and it
is not a copy of the first.

b = ...

c = ...

a = φ(b, c)

d = φ(b, a)

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Translation with copy insertions
Improving code quality
Qualitative experiments

Exploiting SSA: value-based interferences
Definition (Chaitin interference)
Two variables interfere if one is liveat the definition of the other, and it
is not a copy of the first.

b = ...
a0 = bd0 = bc = ...
a0 = ca = a0d0 = ad = d0
b

c
a0

d0
d

Benoit Boissinot

Revisiting Out-of-SSA TranslationaSSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Translation with copy insertions
Improving code quality
Qualitative experiments

Exploiting SSA: value-based interferences
Definition (Chaitin interference)
Two variables interfere if one is liveat the definition of the other, and it
is not a copy of the first.

b = ...
a0 = bd0 = bc = ...
a0 = ca = a0d0 = ad = d0
b

c
a0

d0
d

Benoit Boissinot

Revisiting Out-of-SSA TranslationaSSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Translation with copy insertions
Improving code quality
Qualitative experiments

Exploiting SSA: value-based interferences
Definition (Chaitin interference)
Two variables interfere if one is liveat the definition of the other, and it
is not a copy of the first.

b = ...
c =b* Need to update interferencegraph after coalescing.

c = ...

b=c

b
b

c
a0

d0
d

Benoit Boissinot

Revisiting Out-of-SSA TranslationaSSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Translation with copy insertions
Improving code quality
Qualitative experiments

Exploiting SSA: value-based interferences
Definition (Chaitin interference)
Two variables interfere if one is liveat the definition of the other, and it
is not a copy of the first.
* Need to update interferencegraph after coalescing.
Unique value V of a SSA variable
For a copy b = a, V (b) = V (a)(traversal of dominance tree).

b = ...
a0 = bd0 = bc = ...
a0 = ca = a0d0 = ad = d0b

Value-based interferencea and b interfere if V (a) 6= V (b) andLive-range(a) ∩ Live-range(b) 6= ∅.
Benoit Boissinot

c
a0

d0
d

Revisiting Out-of-SSA TranslationaSSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Translation with copy insertions
Improving code quality
Qualitative experiments

Exploiting SSA: value-based interferences
Definition (Chaitin interference)
Two variables interfere if one is liveat the definition of the other, and it
is not a copy of the first.

b = ...

b = ...

* Need to update interferencegraph after coalescing.
Unique value V of a SSA variable
For a copy b = a, V (b) = V (a)(traversal of dominance tree).

bbValue-based interferencea and b interfere if V (a) 6= V (b) andLive-range(a) ∩ Live-range(b) 6= ∅.
Benoit Boissinot

c
a0

d0
d

Revisiting Out-of-SSA TranslationaSSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Translation with copy insertions
Improving code quality
Qualitative experiments

Qualitative experiments with SPEC CINT2000

Number of remaining moves

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Translation with copy insertions
Improving code quality
Qualitative experiments

Qualitative experiments with SPEC CINT2000

Key points of the out-of-SSA translation
Copy insertion (to go to CSSA and to handle register
renaming constraints) followed by coalescing.
Value-based interferences * coalescing is improved andindependent of virtualization (i.e., as in Sreedhar III).
Parallel copies followed by sequentialization.

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

Outline1

SSA foundations
Out-of-SSA translation

2

Correctness and code quality
Translation with copy insertions
Improving code quality
Qualitative experiments

3

Speed and memory footprint
Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

4

Conclusion

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

How to coalesce variables?

Two alternatives
Use a working interference graph where, in case of coalescing,corresponding vertices are merged. O(1) interference query.
Manipulate congruence classes, i.e., sets of coalescedvariables. Interferences must be tested between sets.
Chaitin, Sreedhar, Budimlić use congruence classes. Also useful toavoid interference graph. Naive algorithm: quadratic complexity.

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

Fast interference test for a set of variables

Key properties for linear-complexity live range intersection
2 SSA variables intersect if one is live at the definition of theother.
In this case, the first definition dominates the second one.
Budimlić: If a and b intersect (a dom b), then∀c with a dom c and c dom b: b and c interferes.
=⇒ For each variable, the only test needed is with the “closest”
dominating variable

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

Fast interference test for a set of variablesa ← ···b ← a + ···c ← b + ···← cd ← ···e ← d + ···← a+eBenoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

Fast interference test for a set of variablesa ← ···b ← a + ···c ← b + ···← cd ← ···e ← d + ···← a+eBenoit Boissinot

Revisiting Out-of-SSA TranslationaSSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

Fast interference test for a set of variablesa ← ···b ← a + ···c ← b + ···← cd ← ···e ← d + ···← a+eBenoit Boissinot

Revisiting Out-of-SSA Translationba

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

Fast interference test for a set of variablesa ← ···b ← a + ···c ← b + ···← cd ← ···e ← d + ···← a+eBenoit Boissinot

Revisiting Out-of-SSA Translationcba

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

Fast interference test for a set of variablesa ← ···b ← a + ···c ← b + ···← cd ← ···e ← d + ···← a+eBenoit Boissinot

Revisiting Out-of-SSA Translationcba

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

Fast interference test for a set of variablesa ← ···b ← a + ···c ← b + ···← cd ← ···e ← d + ···← a+eBenoit Boissinot

Revisiting Out-of-SSA Translationba

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

Fast interference test for a set of variablesa ← ···b ← a + ···c ← b + ···← cd ← ···e ← d + ···← a+eBenoit Boissinot

Revisiting Out-of-SSA TranslationaSSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

Fast interference test for a set of variablesa ← ···b ← a + ···c ← b + ···← cd ← ···e ← d + ···← a+eBenoit Boissinot

Revisiting Out-of-SSA TranslationdaSSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

Fast interference test for a set of variablesa ← ···b ← a + ···c ← b + ···← cd ← ···e ← d + ···← a+eBenoit Boissinot

Revisiting Out-of-SSA TranslationedaSSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

Fast interference test for a set of variablesa ← ···b ← a + ···c ← b + ···← cd ← ···e ← d + ···← a+eBenoit Boissinot

Revisiting Out-of-SSA TranslationedaSSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

Fast interference test for a set of variablesa ← ···b ← a + ···c ← b + ···← cd ← ···e ← d + ···← a+eBenoit Boissinot

Revisiting Out-of-SSA TranslationdaSSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

Fast interference test for a set of variablesa ← ···b ← a + ···c ← b + ···← cd ← ···e ← d + ···← a+eBenoit Boissinot

Revisiting Out-of-SSA TranslationaSSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

Fast interference test for a set of variablesa ← ···b ← a + ···c ← b + ···← cd ← ···e ← d + ···← a+eBenoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

Linear interference test of two congruence classes
Generalization to interference test of two sets
Emulate a stack-based DFS traversal of dominance tree, for
two sorted sets instead of one * linear number of tests. Alsono need to test intersection of variables in the same set.
Take values into account for value-based interference: needlinks of “equal ancestors”, which may increase complexity.
Sort in linear time the resulting set, in case of coalescing.

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

Linear interference test of two congruence classes
Generalization to interference test of two sets
Emulate a stack-based DFS traversal of dominance tree, for
two sorted sets instead of one * linear number of tests. Alsono need to test intersection of variables in the same set.
Take values into account for value-based interference: needlinks of “equal ancestors”, which may increase complexity.
Sort in linear time the resulting set, in case of coalescing.
Fewer intersection tests * possible now to use more expensive
queries for intersection and liveness and avoid interference graph:
Budimlić intersection test, still using liveness sets.
Fast liveness checking of Boissinot et al. (CGO’08).
Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

Speed-up for SPEC CINT2000: x2

Time to go out of SSA (valgrind cycles)
Default: Liveness sets + interference graphBenoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

Memory footprint reduction for SPEC CINT2000: x10
Interference graph: half-size bit matrix.
Liveness sets: enumerated sets. Does not count construction.
Livenesss check: bit sets. Construction taken into account.
Data structures grow during virtualization. “Perfect memory”
evaluated, with both enumerated/bit sets for liveness sets.

Max of memory footprint
Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Outline1

SSA foundations
Out-of-SSA translation

2

Correctness and code quality
Translation with copy insertions
Improving code quality
Qualitative experiments

3

Speed and memory footprint
Linear-time algorithm for coalescing congruence classes
Experimental results for speed and memory footprint

4

Conclusion

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

General framework
Correctness clarified even for complex cases
Two phases solution, based on coalescing
Results
Value-based interference as good as Sreedhar III
Fast algorithm: Speed-up x2, memory reduction x10.
Implementation
No need to virtualize (at least for us)
Simple implementation

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

General framework
Correctness clarified even for complex cases
Two phases solution, based on coalescing
Results
Value-based interference as good as Sreedhar III
Fast algorithm: Speed-up x2, memory reduction x10.
Implementation
No need to virtualize (at least for us)
Simple implementation
Journal version should contain:
Virtualization of register renaming constraints.
All pseudo-codes, e.g., virtualization in general case.
Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

The EndThank you!

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Bug tracking RVM-254 of Jikes RVM

Problems with SSA form: lack of loop unrolling breaks VM

This problem is probably one of the most serious in the RVM currently. When loop
unrolling is disabled and SSA enabled the created IR is corrupt. The error has in thepast look like we were suffering from the ”lost copy” problem, but implementing anaive solution to this didn’t solve the problem. Their is sound logic behind the code so
we need to identify a small test case where things are broken and then reason about
what’s wrong in leave SSA. This has been attempted once (with the code thatremoves an element from the live set) but the problem no longer appears to surface
here. Currently these optimizations are disabled but by RVM 3.0 they should be
re-enable and this bug cured.

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Potential bugs with conditional branches

B0

B0

u = ...
v = ...

B1

B2

B1

B2

B4
w = φ(u, v )...= w

Initial code

B3

B4

w = ...
v = ...

B1

B2

v0 = vBr(u, B3 , B4 )Br(u, B3 , B4 )B3

B0

u = ...
v = ...

w =v
Br(w , B3 , B4 )

B3

B4

0

w = φ(u, v )...= w...= w“Blind” Sreedhar III

Wrong output code

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Unfeasible out-of-SSA translation example
u

u0
B1

B2

u1 = φ(u0 , u2 )
u2 = u1 − 1
t0 = u2Br(u2 , B1 , B2 )B1

t1 = φ(t0 , t2 )t2 = t1 + . . .
Br(t2 , B1 , B2 )

B2

u
B1

Br dec(u, B1 , B2 )t0 = ut1 = φ(u, t2 )t2 = t1 + . . .
Br(t2 , B1 , B2 )B3

B3
. . . = u2

Initial code

Br dec(u, B1 , B2 )B2

t1 = φ(t0 , t2 )t2 = t1 + . . .
Br(t2 , B1 , B2 )B3...= u...= uAfter optimization

Benoit Boissinot

Needs edge splitting

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Sum of memory over benchmarks
Sum of memory footprint
1.2

1

0.8

0.6

0.4

0.2

0
Measured

Evaluated (Ordered sets)
Benoit Boissinot

Evaluated (Bit sets)

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Speedup

Benoit Boissinot

Revisiting Out-of-SSA Translation

SSA foundations
Correctness and code quality
Speed and memory footprint
Conclusion

Qualitatives

1
0.9
0.8
Intersection
Sreedhar I
Chaitin
Value
Sreedhar III
Value IS
Sharing

0.7
0.6
0.5

tw

m
su

ol
f

2
0.

bz
6.
25

30

rt

ip

ex

p
25

5.

vo

4.
25

rlb
pe

Benoit Boissinot

ga

m

se
pa
r

3.
25

19

7.

cr
6.
18

k

r

af
ty

m
1.
18

6.

gc

cf

c

r
vp
17

5.
17

16

4.

gz

ip

0.4

Revisiting Out-of-SSA Translation