Empirical investigation of SEA-based dependence cluster properties

• Calculated dependence clusters based on SEA relations for medium and big programs.
• Proposed metrics for measuring clusterization level.
• Calculated linchpin vertices by brute-force method.
• Proposed a heuristic method to approximate linchpins.
• Application to impact analysis.

Dependence clusters are (maximal) groups of source code entities that each depend on the other according to some dependence relation. Such clusters are generally seen as detrimental to many software engineering activities, but their formation and overall structure are not well understood yet. In a set of subject programs from moderate to large sizes, we observed frequent occurrence of dependence clusters using Static Execute After (SEA) dependences (SEA is a conservative yet efficiently computable dependence relation on program procedures). We identified potential linchpins; these are procedures that can primarily be made responsible for keeping the cluster together. Furthermore, we found that as the size of the system increases, it is more likely that multiple procedures are jointly responsible as sets of linchpins. We also give a heuristic method based on structural metrics for locating possible linchpins as their exact identification is unfeasible in practice, and presently there are no better ways than the brute-force method. We defined novel metrics to be able to uncover clusters of different sizes in programs, and also to relate programs in terms of their degree of clusterization. Finally, we present a possible application of SEA-based dependences in change impact analysis, and investigate the effect of dependence clusters on the successfulness of this activity.