Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Towards an SSA based compiler back-end:
some interesting properties of SSA and its
extensions
Benoit Boissinot
Équipe Compsys
Laboratoire de l’Informatique du Parallélisme (LIP)
École normale supérieure de Lyon
Membres du jury :Albert Cohen (rapporteur)
Anton Ertl (examinateur)David Monniaux (rapporteur)
Fabrice Rastello (directeur de thèse)
Yves Robert (examinateur)

INRIA Saclay
TU WienVerimag
ENS de Lyon
ENS de Lyon

1 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Compiling, compilers

2 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Compiling, compilers

Two compilation phases
1

On a workstation: compile to architecture independant
bytecode2

On the target processor, compile bytecode to native code

3 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Compiling, compilers

Two compilation phases
1

On a workstation: compile to architecture independant
bytecode2

On the target processor, compile bytecode to native code

Challenges
Reduce compilation time (speed of compilation),while keeping a high code quality (speed of execution).

3 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Control flow graphControl flow graph (CFG)x←1y←2b ← ?(x > y)branch b

Program is represented as agraph
Node: sequence of
instruction without branch
Edge: possible execution
flow (branch instructions)

r←y

r←x

return r

4 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Static Single Assignment

Static Single Assignment (SSA)

x
y

←
←

x0
y0

...
...

x ← ...

y ← ...

z←x+y

←
←

y1 ← . . .

x1 ← . . .

x2
y2
z

←
←
←

...
...

φ(x1 , x0 )φ(y0 , y1 )x2 + y2

For each variable:
Only one textual definition (⇒ renaming)
No use of undefined variable (dominance property)
Add φ-function at merge points, acts as parallel switch
5 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Static Single Assignment

Use of SSA
Goal
One static definition per variable ⇒ attach properties to variable(sparse representation)
Properties
Dominance property
Unique definition⇒ simpler and more efficient algorithms

6 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Static Single Assignment

Use of SSA
Goal
One static definition per variable ⇒ attach properties to variable(sparse representation)
Properties
Dominance property
Unique definition⇒ simpler and more efficient algorithms
Drawbacks
Create more variables (memory)
Cost of maintainance
Need to get rid of φ-functions
6 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Static Single Assignment

OutlineSparseSSA

SSI
live-range

Live-range

SSI
debunking

SSA
destruction

Interfcheck

Value
Live-check7 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

OutlineSparseSSA

SSI
live-range

Live-range

SSI
debunking

SSA
destruction

Interfcheck

Value
Live-check8 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Liveness
r=01
x = ...

2

Definition (live-in)
4

Existence of a path to a use that
does not contain the definition.

5... = x

3
6

Definition (live-range)
Set of program points where avariable is live-in.

7
8
9
10

9 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

What to compute?
Classical Approach: Liveness Sets
For every block boundary, the set of all live variables.
Expensive precomputation (space & time), fast query
Usually, not all computed information is needed
Adding, (re-)moving instructions ⇒ recompute information

10 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

What to compute?
Classical Approach: Liveness Sets
For every block boundary, the set of all live variables.
Expensive precomputation (space & time), fast query
Usually, not all computed information is needed
Adding, (re-)moving instructions ⇒ recompute information
Alternative approach: Liveness Checking
Answer on demand: Is a variable live at program point?
Faster precomputation, slower queries
Information depends only on CFG and def-use chains
Information invariant to adding, (re-) moving instructions
10 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Different approaches

Data-flow{}
x = . . . r=0{}
1{}

Traditional approach (not SSA specific)
Backward data-flow propagation:
propagates the information about every
variable inside the CFG.
Wait for a fixed-point.
⇒ number of iterations depends on thecyclic structure.

y = ...

2
4{}... = y{}5{}... = x 3

{} 6
{}
7
{}
8
{}
9
{}
10
11 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Different approaches

Data-flow{}
x = . . . r=0
{x}
1
{x}

Traditional approach (not SSA specific)
Backward data-flow propagation:
propagates the information about every
variable inside the CFG.
Wait for a fixed-point.
⇒ number of iterations depends on thecyclic structure.

y = ...

24{y}... = y{}5{x}... = x 3

{} 6
{}
7
{}
8
{}
9
{}
10
11 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Different approaches

Data-flow{}
x = . . . r=0
{x}
1
{x}

Traditional approach (not SSA specific)
Backward data-flow propagation:
propagates the information about every
variable inside the CFG.
Wait for a fixed-point.
⇒ number of iterations depends on thecyclic structure.

y = ...

2
4{x, y}... = y{x, y}

5{x}... = x 3

{x, y} 6
{x}
7
{x}
8
{x}
9
{}
10
11 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Different approaches

Data-flow{}
x = . . . r=0
{x}
1
{x}

Traditional approach (not SSA specific)
Backward data-flow propagation:
propagates the information about every
variable inside the CFG.
Wait for a fixed-point.
⇒ number of iterations depends on thecyclic structure.

y = ...

2
4{x, y}... = y{x, y}

5{x}... = x 3

{x, y} 6{x, y}
7
{x}
8
{x}
9
{}
10
11 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Different approaches

Path exploration (principle)
Context
Found in some modern compiler
textbooks, requires or builds use
and def sets.
Discover live-range: starting fromthe uses, mark the ancestors in the
CFG, stop when a definition isfound.
Efficiency
Few uses per variables.
Under SSA: short live-ranges,
use-def chains and def-use chainsavailable.

r=0
1
x = ...

2
4
5... = x

3
6
7
8
9
10

12 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Different approaches

Path exploration (principle)
Context
Found in some modern compiler
textbooks, requires or builds use
and def sets.
Discover live-range: starting fromthe uses, mark the ancestors in the
CFG, stop when a definition isfound.
Efficiency
Few uses per variables.
Under SSA: short live-ranges,
use-def chains and def-use chainsavailable.

r=0
1
x = ...

2
4
5... = x

3
6
7
8
9
10

12 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Different approaches

Path exploration (principle)
Context
Found in some modern compiler
textbooks, requires or builds use
and def sets.
Discover live-range: starting fromthe uses, mark the ancestors in the
CFG, stop when a definition isfound.
Efficiency
Few uses per variables.
Under SSA: short live-ranges,
use-def chains and def-use chainsavailable.

r=0
1
x = ...

2
4
5... = x

3
6
7
8
9
10

12 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Different approaches

Path exploration (principle)
Context
Found in some modern compiler
textbooks, requires or builds use
and def sets.
Discover live-range: starting fromthe uses, mark the ancestors in the
CFG, stop when a definition isfound.
Efficiency
Few uses per variables.
Under SSA: short live-ranges,
use-def chains and def-use chainsavailable.

r=0
1
x = ...

2
4
5... = x

3
6
7
8
9
10

12 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Different approaches

Path exploration (principle)
Context
Found in some modern compiler
textbooks, requires or builds use
and def sets.
Discover live-range: starting fromthe uses, mark the ancestors in the
CFG, stop when a definition isfound.
Efficiency
Few uses per variables.
Under SSA: short live-ranges,
use-def chains and def-use chainsavailable.

r=0
1
x = ...

2
4
5... = x

3
6
7
8
9
10

12 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Different approaches

Path exploration (principle)
Context
Found in some modern compiler
textbooks, requires or builds use
and def sets.
Discover live-range: starting fromthe uses, mark the ancestors in the
CFG, stop when a definition isfound.
Efficiency
Few uses per variables.
Under SSA: short live-ranges,
use-def chains and def-use chainsavailable.

r=0
1
x = ...

2
4
5... = x

3
6
7
8
9
10

12 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Different approaches

Path exploration (principle)
Context
Found in some modern compiler
textbooks, requires or builds use
and def sets.
Discover live-range: starting fromthe uses, mark the ancestors in the
CFG, stop when a definition isfound.
Efficiency
Few uses per variables.
Under SSA: short live-ranges,
use-def chains and def-use chainsavailable.

r=0
1
x = ...

2
4
5... = x

3
6
7
8
9
10

12 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Different approaches

Path exploration (algorithm)

Live-sets
For each variable:
1build the live-range

2

update the live-sets

Complexity: size of resulting sets (cost of insertions)Live-check
Given a variable x and a program point p, build the live-range of x,
test membership of p.

13 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Loop-based liveness

Loops

Loop
Decomposition of the CFG in strongly connected components
Headers: distinguished nodes (usually entry points)
Form a tree structure

14 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Loop-based liveness

Loops (example)
r=0
Lr

1

L1
2
4

L4

5
L5

3
6
7

r

1

2

3

4

5

6

7

8

9

10

8
9
10

15 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Loop-based liveness

Loops (example)
r=0
Lr

1

L1
2
4

L4

5
L5

3
6
7

r

1

2

3

4

5

6

7

8

9

10

8
9
10

15 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Loop-based liveness

Loops (example)
r=0
Lr

1

L1
2
4

L4

5
L5

3
6
7

r

1

2

3

4

5

6

7

8

9

10

8
9
10

15 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Loop-based liveness

Loops (example)
r=0
Lr

1

L1
2
4

L4

5
L5

3
6
7

r

1

2

3

4

5

6

7

8

9

10

8
9
10

15 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Loop-based liveness

Loops (example)
r=0
Lr

1

L1
2
4

L4

5
L5

3
6
7

r

1

2

3

4

5

6

7

8

9

10

8
9
10

15 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Loop-based liveness

Loops (example)
r=0
Lr

1

L1
2
4

L4

5
L5

3
6
7

r

1

2

3

4

5

6

7

8

9

10

8
9
10

15 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Loop-based liveness

Loops (example)
r=0
Lr

1

L1
2
4

L4

5
L5

3
6
7

r

1

2

3

4

5

6

7

8

9

10

8
9
10

15 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Loop-based liveness

Irreducible CFG
r=012

Strongly connectedcomponents with several
entry points

4
5
3

Unstructured original code
(goto)

6
7

More complex algorithms
89
10

16 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Loop-based liveness

Loop-based liveness (principle)
Build partial livenessLiveness is easy to compute on directed acyclic graphs (DAG)⇒ partial liveness on the CFG without the loop-edges (reduced
DAG)

17 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Loop-based liveness

Loop-based liveness (principle)
Build partial livenessLiveness is easy to compute on directed acyclic graphs (DAG)⇒ partial liveness on the CFG without the loop-edges (reduced
DAG)
Fix liveness using loops
For every SSA variable x and program point p such that x is live-in
at p:either p is found live-in with partial liveness,or there exists a header of a loop containing p: h, such that h
is found live-in with partial liveness.
Reciprocally, if x is live-in of a loop header h, it is also live-in of
every node contained in the loop.
17 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Loop-based livenessTwo-pass data-flow (live-sets){}x = r=0{}1

First pass (build partial liveness){}y=

One pass of data-flow in reverse
topological order of the reduced acyclic
graph.

2
4

{}
=y
{}

5

{}
=x 3

{} 6

Second pass (fix liveness){}

Add the missing variables to the
live-sets with a top-down pass in theloop forest.

7
{}
8
{}
9
{}
10
18 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Loop-based livenessTwo-pass data-flow (live-sets){}x = r=0{x}1First pass (build partial liveness){x}y=

One pass of data-flow in reverse
topological order of the reduced acyclic
graph.

2
4

{y}
=y
{}

5

{x}
=x 3

{} 6

Second pass (fix liveness){}

Add the missing variables to the
live-sets with a top-down pass in theloop forest.

7
{}
8
{}
9
{}
10
18 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Loop-based livenessTwo-pass data-flow (live-sets){}x = r=0{x}1First pass (build partial liveness){x}y=

One pass of data-flow in reverse
topological order of the reduced acyclic
graph.

2
4{x, y}
=y
{x}

5

{x}
=x 3

{x} 6

Second pass (fix liveness){x}

Add the missing variables to the
live-sets with a top-down pass in theloop forest.

7
{x}
8
{x}
9
{}
10
18 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Loop-based livenessTwo-pass data-flow (live-sets){}x = r=0{x}1First pass (build partial liveness){x}y=

One pass of data-flow in reverse
topological order of the reduced acyclic
graph.

2
4{x, y}=y{x, y}

5

{x}
=x 3

{x, y} 6

Second pass (fix liveness){x, y}

Add the missing variables to the
live-sets with a top-down pass in theloop forest.

7
{x}
8
{x}
9
{}
10
18 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Loop-based livenessTwo-pass data-flow (live-sets){}x = r=0{x}1First pass (build partial liveness){x}y=

One pass of data-flow in reverse
topological order of the reduced acyclic
graph.

2
4{x, y}=y{x, y}

5

{x}
=x 3

{x, y} 6

Second pass (fix liveness){x, y}

Add the missing variables to the
live-sets with a top-down pass in theloop forest.

7
{x}
8
{x}
9
{}
10
18 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Loop-based liveness

Loop-based liveness (live-check)

Query
Given a variable x, a program point p and a u a use of x:
1

Find h: header of largest loop containing p but not thedefinition of x.

2

Check existence of path from h to u in the reduced DAG.

Step 1 can be reduced to the least-common ancestor problem inthe loop-nesting tree.

19 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Loop-based liveness

Loop-based liveness (irreducible graphs)

Graph transformation preserving liveness
Given a graph that is not reducible, we can transform it, while
preserving liveness and loop structure, so that it becomes
reducible:
1

For every loop, choose an entry node as unique header

2

For every edge entering the loop, redirect them to the chosen
headerNo need to actually modify the graph.

20 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Loop-based liveness

Summary
Algorithms
Data-flow
Path exploration
Loop

Live-sets
X
X
X

Live-check–X
X

21 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Loop-based liveness

Summary
Algorithms
Data-flow
Path exploration
Loop

Live-sets
X
X
X

Live-check–
X
X

Requirements
Path exploration:
Sets of use and definitions
Loop-based liveness:
Loop-nesting tree
SSA
Def-use chains for live-check21 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Loop-based liveness

Summary

Loop-based livenessUse SSA properties to derive a new way to find livenessLive-check
New way to use liveness information:easy to pre-computeno maintainance needed
overall speedup depending on the number of queries

22 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

OutlineSparseSSA

SSI
live-range

Live-range

SSI
debunking

SSA
destruction

Interfcheck

Value
Live-check23 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Clean approach

Previous approaches

Cytron et al. (1991): copies in predecessor basic blocks.
Incorrect because of a bad understanding of:parallel nature of φ-functions;critical edges.

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.

24 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Clean approach

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

Bi

Bn

a0 = φ(a1 , . . . , an )25 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Clean approach

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

B0

B1

Bi

Bn

a10 = a1

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

25 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Clean approach

Code quality

Removing copies
Useless copies can be removed by standard aggressive coalescing.
⇒ use an accurate notion of interference

26 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Improving code quality

Traditional interference
Definition (ultimate interference)
Two variables interfere if they can be simultaneously live while
having different values.

27 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Improving code quality

Traditional interference
Definition (ultimate interference)
Two variables interfere if they can be simultaneously live while
having different values.
Chaintin’s approximation
Two variables interfere if one is live at the definition of the other,and it is not a copy of the first.

x ← ...
y ← ...
z←x

z←y

x ← z
y ← z
... ← xIn both cases, x interferes with y.

27 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Improving code quality

Exploiting SSA: value-based interference

Unique value V of a SSA variable
For a copy x ← y, V (x) = V (y) (traversal of dominance tree).
Value-based interference
Two variables x and y interfere if V (x) 6= V (y) and one is live at
the definition of the other.

28 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Improving code quality

Qualitative experiments with SPEC CINT2000

Number of remaining moves

29 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Efficiency

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.

30 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Efficiency

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

31 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Efficiency

Linear interference test of two congruence classes
Generalization to interference test of two sets
DFS traversal of a tree
⇒ Emulate traversal
Interference inside a set⇒ Interference between two sets
Take values into account⇒ Test and merge linearly two sets of variables

32 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Efficiency

Linear interference test of two congruence classes
Generalization to interference test of two sets
DFS traversal of a tree
⇒ Emulate traversal
Interference inside a set⇒ Interference between two sets
Take values into account⇒ Test and merge linearly two sets of variables
Fewer intersection tests ⇒ more expensive queries for intersection,
avoid interference graph:
Budimlić intersection test, using liveness sets.
Liveness checking (presented earlier)
32 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Efficiency

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.

Max of memory footprint
33 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Efficiency

Speed-up for SPEC CINT2000: x2

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

34 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Efficiency

Summary

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.
Simple implementation

35 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Conclusion
SSI
live-range

SparseSSI Zoo

SSA

Live-range

SSI
debunking

TreeScanSSA
destruction

Interfcheck

Value
Live-check

36 / 37

Context

Intermediate representation

Liveness

SSA destruction

Conclusion

Perspectives
SSI
live-range

SparseSSI Zoo

SSA

Live-range

SSI
debunking

TreeScanSSA
destruction

Interfcheck

Value
Live-check37 / 37