What & Why

Foundations

Algorithm

Experimental Results

Fast Liveness Checking for SSA-Form Programs
Benoit Boissinot
E.N.S Lyon

Sebastian Hack
E.N.S Lyon

Fabrice Rastello
E.N.S. Lyon

Daniel Grund
Saarland University

Benoı̂t Dupont de Dinechin
STMicroelectronics

April 7, 2008

Conclusion

What & Why

Foundations

Algorithm

Outline1

Liveness checking: what & why

2

Foundations

3

Algorithm

4

Experimental Results

5

Conclusion

Experimental Results

Conclusion

What & Why

Foundations

Algorithm

Outline1

Liveness checking: what & why

2

Foundations

3

Algorithm

4

Experimental Results

5

ConclusionExperimental Results

Conclusion

What & Why

Foundations

Algorithm

Experimental Results

Conclusion

Why do we need liveness analysis?

a=Resources analysis
Scheduling
Coalescing/Register-allocationb==aPRE sensitive to register pressure=babWhat & Why

Foundations

Algorithm

Experimental Results

Two approaches
Classical Approach: Liveness Sets (LS)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
Our Approach: Liveness Checking (LC)Answer on demand: Is 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

Conclusion

What & WhyFoundations

Algorithm

Outline1

Liveness checking: what & why

2

Foundations

3

Algorithm

4

Experimental Results

5

Conclusion

Experimental Results

Conclusion

What & Why

Foundations

Algorithm

Experimental Results

Conclusion

Dominance
r=0

1

Control Flow Graph
Intermediate representation is aControl Flow Graph (CFG):

5

6

one entry node r
every node reachable from r

927Definitiona dominates b if every path fromthe root r to b contains a.

834

What & WhyFoundations

Algorithm

Experimental Results

Conclusion

Dominance
r=01

Control Flow Graph
Intermediate representation is a
Control Flow Graph (CFG):

56

one entry node r
every node reachable from r

92
7

Definitiona dominates b if every path fromthe root r to b contains a.

83

4

1 dominates 4?

What & WhyFoundations

Algorithm

Experimental Results

Conclusion

Dominance
r=0

1

Control Flow Graph
Intermediate representation is a
Control Flow Graph (CFG):

56

one entry node r
every node reachable from r

92
7

Definitiona dominates b if every path fromthe root r to b contains a.

83

4

1 dominates 4

What & WhyFoundations

Algorithm

Experimental Results

Conclusion

Dominance
r=0

1

Control Flow Graph
Intermediate representation is a
Control Flow Graph (CFG):

5

6

one entry node r
every node reachable from r

92
7

Definitiona dominates b if every path fromthe root r to b contains a.

83

4

2 dominate 4?

What & WhyFoundations

Algorithm

Experimental Results

ConclusionDominance
r=01

Control Flow Graph
Intermediate representation is a
Control Flow Graph (CFG):

5

6

one entry node r
every node reachable from r

927Definitiona dominates b if every path fromthe root r to b contains a.

8

2 does not
3dominate 44

What & WhyFoundations

Algorithm

Experimental Results

Conclusion

SSA with dominance property
r=0x=1

Static Single Assignement (SSA)

5

Static Single Assignement (SSA)
with dominance property:(textually) only one
definition per variable

96=x27the definition d dominates
all its uses ui

834=xWhat & Why

Foundations

Algorithm

Experimental Results

Conclusion

SSA with dominance property
r=0x=1

Static Single Assignement (SSA)

5

Static Single Assignement (SSA)
with dominance property:(textually) only one
definition per variable

96=x

2
7

the definition d dominates
all its uses ui

834=xWhat & Why

Foundations

Algorithm

Experimental Results

Conclusion

SSA with dominance property
r=0x=1

Static Single Assignement (SSA)

5

Static Single Assignement (SSA)
with dominance property:(textually) only one
definition per variable

96=x

2
7

the definition d dominates
all its uses ui

834=xWhat & Why

Foundations

Algorithm

Experimental Results

Conclusion

Liveness
r=0

Concept
Defined in the past:
reaching definition

x=1

5

Used in the future:
upward exposed use

6=x2

Definition (live-in)
A variable a is live-in at a node q
if there exists a path from q to anode u where a is used and thatpath does not contain its
definition d97834

What & Why

Foundations

Algorithm

Experimental Results

Conclusion

Liveness
r=0

Concept
Defined in the past:
reaching definitionx=

15

Used in the future:
upward exposed use

6=x2

Definition (live-in)
A variable a is live-in at a node q
if there exists a path from q to anode u where a is used and thatpath does not contain its
definition d9

7

8

34

What & Why

Foundations

Algorithm

Experimental Results

Conclusion

Liveness
r=0

Concept
Defined in the past:
reaching definition

x=

1

5

Used in the future:
upward exposed use

6=x2

Definition (live-in)
A variable a is live-in at a node q
if there exists a path from q to anode u where a is used and thatpath does not contain its
definition d

97834

What & Why

Foundations

Algorithm

Experimental Results

Conclusion

Liveness
r=0Concept
Defined in the past:
reaching definition

x=1

5

Used in the future:
upward exposed use

6=x2

Definition (live-in)
A variable a is live-in at a node q
if there exists a path from q to anode u where a is used and thatpath does not contain its
definition d

97834

What & Why

Foundations

Algorithm

Experimental Results

Conclusion

Liveness
r=0Concept
Defined in the past:
reaching definition

x=

1

5

Used in the future:
upward exposed use

6=x2

Definition (live-in)
A variable a is live-in at a node q
if there exists a path from q to anode u where a is used and thatpath does not contain its
definition d97

834

What & WhyFoundations

Algorithm

Experimental Results

Conclusion

Liveness
r=0

Concept
Defined in the past:
reaching definition

x=

1

5

Used in the future:
upward exposed use

6=x2

Definition (live-in)
A variable a is live-in at a node q
if there exists a path from q to anode u where a is used and thatpath does not contain its
definition d

97834

What & Why

Foundations

Algorithm

Experimental Results

Conclusion

Liveness
r=0Concept
Defined in the past:
reaching definition

x=1

5

Used in the future:
upward exposed use

6=x2

Definition (live-in)
A variable a is live-in at a node q
if there exists a path from q to anode u where a is used and thatpath does not contain its
definition d

97834

What & Why

Foundations

Algorithm

Experimental Results

Conclusion

Liveness
r=0

Concept
Defined in the past:
reaching definitionx=

15

Used in the future:
upward exposed use

6=x2

Definition (live-in)
A variable a is live-in at a node q
if there exists a path from q to anode u where a is used and thatpath does not contain its
definition d

9

7

8

3

4

What & Why

Foundations

Algorithm

Experimental Results

Conclusion

Liveness
r=0

Concept
Defined in the past:
reaching definition

x=

1

5

Used in the future:
upward exposed use

6=x2

Definition (live-in)
A variable a is live-in at a node q
if there exists a path from q to anode u where a is used and thatpath does not contain its
definition d

97834

What & Why

Foundations

Algorithm

Experimental Results

Conclusion

Liveness
r=0Concept
Defined in the past:
reaching definition

x=1

5

Used in the future:
upward exposed use

6=x2

Definition (live-in)
A variable a is live-in at a node q
if there exists a path from q to anode u where a is used and thatpath does not contain its
definition d

97834

What & Why

Foundations

Algorithm

Experimental Results

Conclusion

Liveness
r=0Concept
Defined in the past:
reaching definition

x=1

5

Used in the future:
upward exposed use

6=x2

Definition (live-in)
A variable a is live-in at a node q
if there exists a path from q to anode u where a is used and thatpath does not contain its
definition d97

8

3

4

What & Why

Foundations

Algorithm

Experimental Results

Conclusion

Liveness
r=0

Concept
Defined in the past:
reaching definition

x=1

95

Used in the future:
upward exposed use

6=x2

Definition (live-in)
A variable a is live-in at a node q
if there exists a path from q to anode u where a is used and thatpath does not contain its
definition d

78x is not live at q

34q

What & WhyFoundations

Algorithm

Experimental Results

Conclusion

Liveness
r=0

Concept
Defined in the past:
reaching definition

x=

1

5

Used in the future:
upward exposed use

6=x2

Definition (live-in)
A variable a is live-in at a node q
if there exists a path from q to anode u where a is used and thatpath does not contain its
definition d

97834qx is live at q

What & WhyFoundationsAlgorithm

Experimental Results

Liveness: precomputation versus queries

Classical liveness (data-flow):
Costly precomputation
Almost constant queries

Our solution:
Fast precomputation
Queries almost linear in the number of uses

Conclusion

What & Why

Foundations

Algorithm

Experimental Results

Conclusion

Avg

Cycles400k

newnative

300k
200k
100k
0k

0200

400

600

800

1000Queries

What & Why

Foundations

Algorithm

Outline1Liveness checking: what & why

2Foundations

3

Algorithm

4

Experimental Results

5Conclusion

Experimental Results

Conclusion

What & Why

Foundations

Algorithm

Experimental Results

ConclusionPrinciple
r=0

Goal:
From all the paths from query touse, remove those going through
def .

def

1

95

6

Highest point
Last point of the path such that
all the following points are below.

2use

78

If the highest point is dominatedby def then the whole path is.
34

query

What & Why

Foundations

Algorithm

Experimental Results

Conclusion

Principle
r=0

Goal:
From all the paths from query touse, remove those going through
def .

def

1

95

6

Highest point
Last point of the path such that
all the following points are below.

2use

78If the highest point is dominatedby def then the whole path is.
34queryWhat & Why

Foundations

Algorithm

Experimental Results

Conclusion

Principle
r=0

Goal:
From all the paths from query touse, remove those going through
def .

def

1

95

6

Highest point
Last point of the path such that
all the following points are below.

2use

78

If the highest point is dominatedby def then the whole path is.
34queryWhat & Why

Foundations

Algorithm

Experimental Results

Conclusion

Principle
r=0

def

1

9For each node q of the CFG,
compute the set of potential
highest points of every pathstarting at q.
From this set, remove thepoints above def (notdominated by def ).
From the remaining highest
points, test the descending
reachability to use.

562use7834

q

Example 1

What & Why

Foundations

Algorithm

Experimental Results

Conclusion

Principle
r=0def1

9For each node q of the CFG,
compute the set of potential
highest points of every pathstarting at q.
From this set, remove thepoints above def (notdominated by def ).
From the remaining highest
points, test the descending
reachability to use.

562use7834q

Example 1

What & Why

Foundations

Algorithm

Experimental Results

Conclusion

Principle
r=0def1

9For each node q of the CFG,
compute the set of potential
highest points of every pathstarting at q.
From this set, remove thepoints above def (notdominated by def ).
From the remaining highest
points, test the descending
reachability to use.

562use7834q

Example 1

What & Why

Foundations

Algorithm

Experimental Results

Conclusion

Principle
r=0def1

9For each node q of the CFG,
compute the set of potential
highest points of every pathstarting at q.
From this set, remove thepoints above def (notdominated by def ).
From the remaining highestpoints, test the descending
reachability to use.

562use

7

83

4

q

Example 1

What & WhyFoundations

Algorithm

Experimental Results

Conclusion

Principle
r=0def1

9For each node q of the CFG,
compute the set of potential
highest points of every pathstarting at q.
From this set, remove thepoints above def (notdominated by def ).
From the remaining highest
points, test the descending
reachability to use.

562use7834q

Example 1

What & Why

Foundations

Algorithm

Experimental Results

Conclusion

Principle
r=0def1

9For each node q of the CFG,
compute the set of potential
highest points of every pathstarting at q.
From this set, remove thepoints above def (notdominated by def ).
From the remaining highest
points, test the descending
reachability to use.

562use7834q

Example 2

What & Why

Foundations

Algorithm

Experimental Results

ConclusionPrinciple
r=0def1

9For each node q of the CFG,
compute the set of potential
highest points of every pathstarting at q.
From this set, remove thepoints above def (notdominated by def ).
From the remaining highestpoints, test the descending
reachability to use.

562use7834q

Example 2

What & WhyFoundations

Algorithm

Experimental Results

Conclusion

Principle
r=0def1

9For each node q of the CFG,
compute the set of potential
highest points of every pathstarting at q.
From this set, remove thepoints above def (notdominated by def ).
From the remaining highest
points, test the descending
reachability to use.

562use7834q

Example 2

What & WhyFoundations

Algorithm

Experimental Results

Conclusion

Principle
r=0

def

1

9For each node q of the CFG,
compute the set of potential
highest points of every pathstarting at q.
From this set, remove thepoints above def (notdominated by def ).
From the remaining highest
points, test the descending
reachability to use.

562use7834q

Example 2

What & WhyFoundationsAlgorithm

Experimental Results

Conclusion

Principle
r=0def1

9For each node q of the CFG,
compute the set of potential
highest points of every pathstarting at q.
From this set, remove thepoints above def (notdominated by def ).
From the remaining highest
points, test the descending
reachability to use.

562use7834q

Example 2

What & WhyFoundations

Algorithm

Experimental Results

Conclusion

Principle
r=0

def

1

9For each node q of the CFG,
compute the set of potential
highest points of every pathstarting at q.
From this set, remove thepoints above def (notdominated by def ).
From the remaining highest
points, test the descending
reachability to use.

562use7834

q

Example 2

What & WhyFoundations

Algorithm

Experimental Results

Conclusion

Principle
r=0def1

9For each node q of the CFG,
compute the set of potential
highest points of every pathstarting at q.
From this set, remove thepoints above def (notdominated by def ).
From the remaining highest
points, test the descending
reachability to use.

562use7834qExample 2

What & WhyFoundations

Algorithm

Experimental Results

Conclusion

Algorithm

Precomputation
1

Compute transitive closure on the reduced graph G 0
G 0 = CFG without DFS back edges (cycle-free)
Simple to compute: post-order traversal

2

For each node q compute a set Tq of possible highest points(back-edge targets)
Also simple to compute: pre-order and post-order traversal

Query
For each use:
For each t ∈ Tq dominated by def :Test reachability in the reduced graphWhat & WhyFoundations

Algorithm

Experimental Results

Conclusion

Implementation TricksReachability and Tq can be efficiently implemented as bitsets
For reducible CFGs there is exactly one “highest” back-edge
targetdominates all the other back-edge targets
sufficient to check from there

Hence, order nodes according to dominance+ “highest” node is first set bit in Tq

What & Why

Foundations

Algorithm

Outline1

Liveness checking: what & why

2

Foundations

3

Algorithm

4

Experimental Results

5

Conclusion

Experimental Results

Conclusion

What & Why

Foundations

Algorithm

Experimental Results

Evaluation

Setup
Implemented in LAO, code generator developed bySTMicroelectronics
Benchmarked with a subset of SPEC2000 (CINT)
Liveness-analysis used during SSA deconstruction
The main factors influencing the speed of our algorithm are:the number of uses per variable (#uses)
the number of basic blocks (#BB)
the number of CFG edges (#edges)

Conclusion

What & WhyFoundations

Algorithm

Experimental Results

Quantitative Evaluation# of Uses per Variable
BenchmarkMaximum

%≤1

%≤2

%≤3

164.gzip
175.vpr176.gcc
181.mcf
186.crafty
197.parser
254.gap
255.vortex
256.bzip2300.twolf

5175
422
46620
96
156
254
36
165

65.6470.36
73.99
66.91
72.98
65.12
70.46
65.99
69.89
69.71

86.38
88.90
87.81
83.50
90.09
86.75
85.95
90.80
89.89
87.59

92.81
93.93
92.42
89.33
93.85
94.26
91.26
95.02
94.47
93.23

Total

620

71.30

87.85

92.76

Conclusion

What & Why

Foundations

Algorithm

Experimental Results

Quantitative Evaluation# of Basic Blocks
BenchmarkAverage% ≤ 32% ≤ 64

164.gzip
175.vpr176.gcc
181.mcf
186.crafty
197.parser
254.gap
255.vortex
256.bzip2
300.twolf

33.35
34.45
38.96
20.31
69.28
23.60
32.89
26.46
22.97
56.97

69.51
68.8872.85
84.61
59.63
84.82
67.60
77.57
78.37
59.47

85.36
84.44
86.03
100.00
76.14
93.49
87.44
90.68
91.89
77.36

Total

35.21

72.71

87.18

Conclusion

What & Why

Foundations

Algorithm

Experimental Results

Runtime Experiments
SpeedupBenchmarkPrecomputation

QueriesBoth164.gzip
175.vpr176.gcc
181.mcf
186.crafty
197.parser
254.gap
255.vortex
256.bzip2
300.twolf

3.12
2.17
3.03
1.85
2.78
2.13
3.45
1.67
3.45
4.76

0.53
0.48
0.26
0.44
0.49
0.49
0.52
0.45
0.51
0.49

1.16
1.41
1.00
1.39
0.73
1.54
2.08
1.32
2.32
1.92

Total

2.94

0.36

1.16

Conclusion

What & Why

Foundations

Algorithm

Outline1Liveness checking: what & why2Foundations

3

Algorithm

4

Experimental Results

5Conclusion

Experimental Results

Conclusion

What & Why

Foundations

Algorithm

Experimental Results

Conclusion

Contributions

Novel approach for liveness checking relying only on the CFG
Fast construction algorithm
Overall speedup in most cases

What & Why

Foundations

Algorithm

Experimental Results

Future Work

Dynamic update for CFG transformations
Memory efficient reachability
Use information available from the loop nesting forestConclusion

What & WhyFoundations

Algorithm

The EndThank you!

Experimental Results

Conclusion