Skip to contentSkip to conversation

Improved flow graphs

PATCH In review Dan Sheridan 3 participants 4 messages May 16, 2007 – May 29, 2007 Sparse checker

lore
Share & tools
lore
#0 lore raw

cover Improved flow graphs

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.

Signature · 4 lines
Daniel Sheridan ([email protected]), 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
#1 lore raw
Quoted 5 lines · Dan Sheridan

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,

Signature · 1 line
Anderson Lizardo
#2 lore raw
In reply to Dan Sheridan
Quoted 2 lines · Dan Sheridan

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?

Quoted 4 lines

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.

Quoted 9 lines

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

#3 lore raw
Quoted 5 lines · Josh Triplett
Quoted 2 lines · Dan Sheridan

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.

Quoted 2 lines

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.

Quoted 3 lines

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.