Liveness Analysis

These are lecture notes from my Computer Science course.

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.

This entry was posted in cgo, lecture. Bookmark the permalink.