program slicing (was Re: random software speculations)
Bradley M. Kuhn
Sat, 7 Aug 1999 16:12:33 -0400
Kragen Sitaker wrote:
[..lots of stuff about program slicing deleted...]
> This same kind of analysis can be used to follow the effects of a variable
> assignment or initialization downstream. (Brad, wc? Tell us more!)
I assume you are talking about the DSDS that I wrote in college. This was
based on the PhD thesis of one of the faculty at my undergrad institution
(Keith Gallagher: http://www.cs.loyola.edu/~kbg).
What you are talking about is all stuff that has been researched heavily.
Look into program slicing, and how it can be used for software engineering.
There is a group at Wisconsin-Madison lead by Reps and Horawitz doing a lot
of work in this area. There is a group at NIST doing work in this area, as
well. I am sure there are others but a lot of key research comes out of
Decomposition slicing (invented by Keith Gallagher) seemed to me when I was
reading the literature to be the only piece of work directly applied to do
doing the kind of things you are talking about with program slicing.
I don't know the state of kbg's slicing tool. His tool is described at
In 1995, the only thing it had ever sliced was the wc(1) program. I don't
know if anything else has ever been sliced. :)
I tried to talk him into releasing it as free software once, and he scoffed
at me because he feared people in the proprietary software realm would do
bad things. I didn't understand the GPL well enough at the time to make the
Kragen, if you are interested in this, I can contact him again and ask him
to do so. Let me know.
(I could release the DSDS as free software, as I own the copyright on most
of it; however, it's useless without the Surgeon's Assistant's output.)
> - what basic blocks pass control to what other basic blocks
> - what statements or expressions change the values of what variables
> - what statements or expressions get aliases to what variables, and where
> they put them
Most slicing tools get this information by building a PDG and getting
def-use edge information.
Aliasing is the hard problem.
> Why Doesn't Somebody modify gcc to output this information? It has to
> compute most of it anyway.
Another faculty member from where I went undergraduate, David Binkley
(http://www.cs.loyola.edu/~binkley), was working on just that at one point.
I don't know how far he got. If you are interested, I could ask him.
>  Look Brad, no killfile!
Well, you should've kill-filed yourself. :) Using a curse word in a post.
ecommitt would have had you for lunch. :0
- email@example.com - Bradley M. Kuhn - firstname.lastname@example.org -