Name
Title | ||
|---|---|---|
A non-iterative data-flow algorithm for computing liveness sets in strict SSA programs |
Abstract | ||
|---|---|---|
We revisit the problem of computing liveness sets (the sets of variables live-in and live-out of basic blocks) for programs in strict static single assignment (SSA). In strict SSA, aka SSA with dominance property, the definition of a variable always dominates all its uses. We exploit this property and the concept of loop-nesting forest to design a fast two-phases data-flow algorithm: a first pass traverses the control-flow graph (CFG), propagating liveness information backwards, a second pass traverses a loop-nesting forest, updating liveness sets within loops. The algorithm is proved correct even for irreducible CFGs. We analyze its algorithmic complexity and evaluate its efficiency on SPECINT 2000. Compared to traditional iterative data-flow approaches, which perform updates until a fixed point is reached, our algorithm is 2 times faster on average. Other approaches are possible that propagate from uses to definitions, one variable at a time, instead of unioning sets as in data-flow analysis. Our algorithm is 1.43 times faster than the fastest alternative on average, when sets are represented as bitsets and for optimized programs, which have non-trivial live-ranges and a larger number of variables. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-25318-8_13 | APLAS |
Keywords | Field | DocType |
data-flow analysis,traditional iterative data-flow approach,strict ssa program,liveness set,strict static single assignment,strict ssa,liveness information,data-flow algorithm,non-iterative data-flow algorithm,dominance property,aka ssa,loop-nesting forest | Register allocation,Computer science,Algorithm,Theoretical computer science,Exploit,Basic block,SPECint,Fixed point,Static single assignment form,Liveness,Data flow diagram | Conference |
Citations | PageRank | References |
2 | 0.37 | 29 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Benoit Boissinot | 1 | 42 | 2.51 |
| Florian Brandner | 2 | 202 | 14.97 |
| Alain Darte | 3 | 888 | 56.40 |
| Benoît Dupont de Dinechin | 4 | 197 | 12.60 |
| Fabrice Rastello | 5 | 482 | 38.30 |