470,835 Members | 1,838 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 470,835 developers. It's quick & easy.

Obtaining the Python Control Flow Graph

Hi,

I have been looking for a good way to convert python code into a
control flow graph.

I know of Python functions that will convert an expression into an
abstract syntax tree (i.e. ast = parser.expr('(x+5)*5') then t =
ast.totuple() then t), but I am not sure how to obtain a CFG.

I've gone through the compiler and it has code that converts the AST
into a CFG (described here:
http://www.python.org/doc/peps/pep-0...g-to-bytecode).
Basically, PyAST_Compile() in Python/compile.c coverts the AST to a CFG
and outputs final bytecode from the CFG by calling two functions:
PySymtable_Build() in Python/symtable.c and compiler_mod() in
Python/compile.c. PySymtable_Build() will build a symtable and
compiler_mod() will create the CFG.

PyPy also offers a way to obtain a control flow graph:
http://codespeak.net/pypy/dist/pypy/...the-flow-model

I was wondering if anyone had any advice on the best way to obtain a
control flow graph. I need the control flow graph because I am trying
figure out if there is a way to bound the integer ranges and list
lengths at compile time.

Thank you for your help

Apr 3 '06 #1
2 4661
Hi!

br******@gmail.com wrote:
I have been looking for a good way to convert python code into a
control flow graph.

I know of Python functions that will convert an expression into an
abstract syntax tree (i.e. ast = parser.expr('(x+5)*5') then t =
ast.totuple() then t), but I am not sure how to obtain a CFG.

I've gone through the compiler and it has code that converts the AST
into a CFG (described here:
http://www.python.org/doc/peps/pep-0...g-to-bytecode).
Basically, PyAST_Compile() in Python/compile.c coverts the AST to a CFG
and outputs final bytecode from the CFG by calling two functions:
PySymtable_Build() in Python/symtable.c and compiler_mod() in
Python/compile.c. PySymtable_Build() will build a symtable and
compiler_mod() will create the CFG.

PyPy also offers a way to obtain a control flow graph:
http://codespeak.net/pypy/dist/pypy/...the-flow-model
(Disclaimer: I am a PyPy developer) This works quite well in most cases
but not in all, e.g. generators are not supported. It has other
problems: The result will be (due to the used approach) in SSA form,
which might be good or bad, depending on what you want. I don't know the
CPython compiler well enough to say whether it is easy to get a CFG out
of it. I know of no other easy method to get a CFG graph from Python code.
I was wondering if anyone had any advice on the best way to obtain a
control flow graph. I need the control flow graph because I am trying
figure out if there is a way to bound the integer ranges and list
lengths at compile time.


This might be quite hard, for generic Python code. You might possibly
(depending again on what your exact plans are) also look into the type
inference part of PyPy:

http://codespeak.net/pypy/dist/pypy/...nnotation-pass

Feel free to also contact the PyPy mailing list (py******@codespeak.net)
if you have PyPy-specific questions.

Cheers,

Carl Friedrich Bolz

Apr 3 '06 #2
br******@gmail.com wrote:

I was wondering if anyone had any advice on the best way to obtain a
control flow graph. I need the control flow graph because I am trying
figure out if there is a way to bound the integer ranges and list
lengths at compile time.


Although I haven't actually been generating control flow graphs as
such, the analysis distribution [1] produces both HTML summaries and C
source code for Python programs of a certain level of sophistication,
and I'm currently trying to finish off a new release which exposes
different strategies for deducing types and specialising functions. You
probably want to read Mark Dufour's ShedSkin paper [2] to get an idea
about how hard this kind of stuff is, and a dose of defeatism might
also be necessary given that your problem may not be solvable in
general. ;-)

Paul

[1] http://www.boddie.org.uk/python/analysis.html
[2] http://kascade.org/optimizing_python.pdf

Apr 3 '06 #3

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

2 posts views Thread by Samir Patel | last post: by
42 posts views Thread by Fred Ma | last post: by
reply views Thread by Rick Hilburger | last post: by
267 posts views Thread by Xah Lee | last post: by
reply views Thread by mihailmihai484 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.