Liveness Analysis

4th March 2010

These are lecture notes from my Computer Science course, not a general reference for "Liveness Analysis"

Liveness analysis is related to allocating registers. Two temporary values can fit in the same register if they’re never ‘live’ at the same time. A temporary is live if it holds a value that will be used in the future.

He talked about what Control-Flow Graphs are, they’re pretty obvious though. Draw lines between nodes, nodes are instructions in the program; no labels. Lines indicate control flow.

There’s a bunch of definitions on slide 143 which are then used later in equations etc.

How do you compute ‘Liveness’?

out(n) = set of in(s) where s is the 'successive' nodes
         of n (note that because you work backwards, this
             is the 'previous' ones.

             The final node has no `out` bit.


    in(n)  = use(n) + (out(n) - def(n))

         (where + is union and - is intersection)

Repeat this in a table until it is stable.

Comments