Coherent clusters in source code

This paper presents the results of a large scale empirical study of coherent
dependence clusters. All statements in a coherent dependence cluster depend
upon the same set of statements and a↵ect the same set of statements; a coherent
cluster’s statements have ‘coherent’ shared backward and forward dependence.
We introduce an approximation to efficiently locate coherent clusters and show
that it has a minimum precision of 97.76%. Our empirical study also finds
that, despite their tight coherence constraints, coherent dependence clusters
are in abundance: 23 of the 30 programs studied have coherent clusters that
contain at least 10% of the whole program. Studying patterns of clustering in
these programs reveals that most programs contain multiple significant coherent
clusters. A series of case studies reveals that these major clusters map to logical
functionality and program structure. For example, we show that for the program
acct, the top five coherent clusters all map to specific, yet otherwise non-obvious,
functionality. Cluster visualization can also reveal subtle deficiencies in program
structure and identify potential candidates for refactoring e↵orts. Finally a
study of inter-cluster dependence is used to highlight how coherent clusters
built are connected to each other, revealing higher-level structures, which can
be used in reverse engineering.