Liveness Checking for SSA-form programs Using Merge sets and DJ graphs

In this work we show that we can check for liveness quickly and efficiently by using Merge sets. The Merge
set of node n, Merge(n), consists of all nodes where a Φ- needs to be placed, if a define of a variable
appears in n. By computing the merge sets statically using a top-down iterative algorithm on the DJ graph
equivalent of a CFG, we can answer the liveness query by utilizing the dominator tree and the merge sets.
Using Merge sets has advantages over computing Tq – the set of target nodes of backedges that affect the
liveness computation (as defined in [1]). Merge sets on an average have been shown to be of a small size
and can be computed very quickly for all kinds of applications. We have also devised a new algorithm for
answering the IsLiveIn query that precludes the need of using and storing both Tq and Rv – the reduced
reachability set[1]. At the same time, the new algorithm does not require a high query time. As the merge
sets do not change unless the CFG structure changes, we would not need to re-compute these sets often.