Performing Incremental Updates to the Flow-Sensitive Dominance Relationship

Chandrashekhar Garud, 
CIS Dept, 
University of Delaware

ABSTRACT

The problem of establishing dominance relationship between points in a
program,  and updating this information  after  a particular change in
the program representation has been addressed in  previous work in the
area  of intraprocedural   data-flow  analysis. This   paper  presents
techniques for computing and incrementally updating dominance relation
for a flow-sensitive interprocedural representation.  Our first result
is that for  flow-sensitive interprocedural analysis, dominance cannot
be represented as  a tree, but   rather needs to  be represented  as a
Directed Acyclic Graph (DAG).  We present techniques for incrementally
updating this  DAG as the source code  is modified.  In certain cases,
we  can directly  determine what updates   are required, in some other
cases, we require  an  iterative method on   a possibly affected  set.
Measurements from a set of benchmark  Fortran and C programs show that
the average cardinality of  these affected sets  is 4.6% of the  total
number   of  elements in  the graph,   and therefore,  the incremental
technique is very efficient.  Our work forms  the basis for performing
incremental  flow-sensitive analysis in    the presence of  structural
changes.