Refining Interprocedural Change-Impact Analysis using Equivalence Relations

Change-impact analysis (CIA) is the task of determining the set
of program elements impacted by a program change. Precise CIA
has great potential to avoid expensive testing and code reviews for
(parts of) changes that are refactorings (semantics-preserving). Existing
CIA is imprecise because it is coarse-grained, deals with only
few refactoring patterns, or is unaware of the change semantics.
We formalize the notion of change impact in terms of the trace
semantics of two program versions. We show how to leverage
equivalence relations to make dataow-based CIA aware of the
change semantics, thereby improving precision in the presence of
semantics-preserving changes. We propose an anytime algorithm
that allows applying costly equivalence relation inference incrementally
to rene the set of impacted statements. We have implemented
a prototype in SymDiff, and evaluated it on 322 real-world changes
from open-source projects and benchmark programs used by prior
research. The evaluation results show an average 35% improvement
in the size of the set of impacted statements compared to standard
dataow-based techniques.