Displaying dependence graphs: a hierarchical approach

We present a method to extract and handle data and control dependences of programs, which we represent as simplified system dependence graphs. Ordinary dependence graphs contain too many nodes and edges for them to be easily comprehended, even for medium sized programs. That is why we propose decomposing programs into a hierarchy of groups for which the corresponding dependence graphs are likely to be of manageable size. In order to realize this, we first implement a tool that builds this hierarchy and stores it in a database. Then a graphical interface provides means to browse the hierarchy, to visualize the dependences of each group, to possibly refine the proposed hierarchy and to annotate nodes or groups. This paper introduces our approach for dependence graph handling, it describes our tool for graph exploration and discusses the results we obtained with a set of real-world programs. Copyright (C) 2004 John Wiley Sons, Ltd.