Browse Prior Art Database

Method for Partitioning a Program Call Graph into Functional Clusters

IP.com Disclosure Number: IPCOM000116392D
Original Publication Date: 1995-Sep-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 6 page(s) / 185K

Publishing Venue

IBM

Related People

Mays, RG: AUTHOR [+3]

Abstract

A method is disclosed for partitioning the call tree diagram of a program into clusters of routines that are closely related by function. Routines are included in the cluster with the calling routine if there is only one call statement to the target routine from among all the routines in the set. Routines with this one-call relationship are essentially functional extensions of the calling routine.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 34% of the total text.

Method for Partitioning a Program Call Graph into Functional Clusters

      A method is disclosed for partitioning the call tree diagram of
a program into clusters of routines that are closely related by
function.
Routines are included in the cluster with the calling routine if
there
is only one call statement to the target routine from among all the
routines in the set.  Routines with this one-call relationship are
essentially functional extensions of the calling routine.

      In order to design and code enhancements and fixes to software
programs, it is necessary to understand the structure of the
software.
This includes how routines (also called procedures or functions)
relate
to one another by CALLs: for example, which procedure, function or
routine calls which one, how the called routine performs certain work
for the calling routine, and so on.  To visualize these
relationships,
a "calling tree" or "structure chart" (Fig. 1) is frequently drawn.
Such
diagrams show the hierarchical calling relationship between routines.

      The calling tree type diagrams have limitations, however,
because it is difficult to distinguish routines that are closely
related
to the calling routine (i.e., perform a function that is integrally
related to just the calling routine) from the routines that are
loosely
related (i.e., perform a utility function for many calling routines).
As a result the calling tree diagram is frequently very large,
complex
and difficult to understand and contains information at too detailed
a
level.

      The method disclosed here provides a way to partition the call
tree diagram into clusters of routines that are closely related by
function.  Routines are included with the calling routine if there is
only one call statement to the target routine from among all the
routines in the set.  In other words the calling routine calls the
target routine only from one place in the code and none of the other
routines in the set call the target routine.

      Routines with this one-call relationship are essentially
functional extensions of the calling routine.  In fact, frequently
these routines were originally part of the calling routine and were
subsequently split off from it to make the overall program more
understandable.  Since a given one-call routine may call its own
one-call routines, the cluster may include a number of one-call
routines.

      The cluster of related routines then represents a functionally
cohesive portion of the program which can be viewed as a unit.  The
clusters are then a higher-level abstraction of the program's
function
and the calling diagram of the clusters is simplified (Fig. 2).

      In this figure routines A, B, C and X are clustered together as
a single function and form a cohesive group.  Routine Y is called
more than once (i.e., a utility subroutine) and becomes its own
cluster.  Routine D likewise is called more than once and becomes a
separate cluster with...