[PATCH 0/2] Improved flow graphs

[PATCH 0/2] Improved flow graphs

[Dan Sheridan]

Dear all,

It doesn't look like this 0/2 made it the first time round...

These two patches are the first of several implementing improved graph
generation for Sparse. Initially, I am dealing with straight-forward
control flow. Forthcoming patches will add program dependency graphs (a
control and data flow representation suitable for program slicing) and
simple pointer alias analysis (for handling indirect calls).

I've tried to keep the C part of the flow graph relatively simple, and
put the hard stuff (like return edges and subgraph processing) in
post-processing scripts. 

Example graph can be seen at
http://www.postman.org.uk/djs52/example.png, generated with

  ./graph validation/context.c | gvpr -f gvpr/return-paths | \
    gvpr -f gvpr/subg-fwd -a good_while3 | dot -Tpng > /tmp/example.png

Comments welcome.

	Dan Sheridan.

-- 
Daniel Sheridan (djs@adelard.com), Consultant
Adelard LLP, College Building, Northampton Square, London  EC1V 0HB, UK
Tel: +44 (0)20 7490 9455, Fax: +44 (0)20 7490 9451, 
Web: http://www.adelard.com

Re: [PATCH 0/2] Improved flow graphs

[Anderson Lizardo]

On 5/16/07, Dan Sheridan <djs@postman.org.uk> wrote:
> Example graph can be seen at
> http://www.postman.org.uk/djs52/example.png, generated with
>
>   ./graph validation/context.c | gvpr -f gvpr/return-paths | \
>     gvpr -f gvpr/subg-fwd -a good_while3 | dot -Tpng > /tmp/example.png

Hi,

I have a question regarding this specific example:

If I understand the code correctly, the node name is the stream line
number of the first instruction of the BB right? Is that why the call
edge for r() comes from 169/173 (and not from 170/174, as I would
expect)?

Nice work BTW.

Regards,
-- 
Anderson Lizardo

Re: [PATCH 0/2] Improved flow graphs

[Josh Triplett]

[-- Attachment #1: Type: text/plain, Size: 1677 bytes --]

Dan Sheridan wrote:
> These two patches are the first of several implementing improved graph
> generation for Sparse.

Very nice work.  I've applied both patches in this series.

I also added shebangs to the gvpr scripts and made them executable, so you
can just run graph ... | gvpr/return-paths | dot ...

I noticed one minor issue: gvpr/return-paths seems to turn some internal
edges in functions into dotted-line return paths.

Also, unprocessed graphs have now become far more messy; for instance,
graphing validation/context.c generates numerous edges to a() and r().  Any
way you could prevent these edges from crossing other subgraphs?  Any way to
make these edges just point to a separate node "a()" and let people look up
a() themselves, removing the excess edges?  Perhaps with a gvpr script?

> Initially, I am dealing with straight-forward
> control flow. Forthcoming patches will add program dependency graphs (a
> control and data flow representation suitable for program slicing) and
> simple pointer alias analysis (for handling indirect calls).

I look forward to seeing these future enhancements.  Pointer alias analysis
would help greatly with many other things in Sparse.

> I've tried to keep the C part of the flow graph relatively simple, and
> put the hard stuff (like return edges and subgraph processing) in
> post-processing scripts. 
> 
> Example graph can be seen at
> http://www.postman.org.uk/djs52/example.png, generated with
> 
>   ./graph validation/context.c | gvpr -f gvpr/return-paths | \
>     gvpr -f gvpr/subg-fwd -a good_while3 | dot -Tpng > /tmp/example.png

Impressive work.

- Josh Triplett


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]

Re: [PATCH 0/2] Improved flow graphs

[Dan Sheridan]

On Tue, 2007-05-22 at 15:11 -0700, Josh Triplett wrote:
> Dan Sheridan wrote:
> > These two patches are the first of several implementing improved graph
> > generation for Sparse.
> 
> Very nice work.  I've applied both patches in this series.

Thanks.

> I noticed one minor issue: gvpr/return-paths seems to turn some internal
> edges in functions into dotted-line return paths.

I think you are talking about the edges which connect call sites to
return sites. These are needed to keep the layout of the graph sane, but
could be made invisible. It would at least help if they looked different
to the return edges.

> Also, unprocessed graphs have now become far more messy; for instance,
> graphing validation/context.c generates numerous edges to a() and r().  Any
> way you could prevent these edges from crossing other subgraphs? 

Probably not. There's a lot of tweaking possible with weights, which
I'll experiment with a bit, but your suggestion of separate a() and r()
nodes might be simpler. Should be very easy to obtain with a gvpr
script.

	Dan.