Obtaining the Python Control Flow Graph

[brianlum]

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-0339/#ast-to-cfg-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/doc/objspace.html#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

 

[Carl Friedrich Bolz]

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-0339/#ast-to-cfg-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/doc/objspace.html#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/doc/translation.html#the-annotation-pass

Feel free to also contact the PyPy mailing list ([email protected])
if you have PyPy-specific questions.

Cheers,

Carl Friedrich Bolz

 

[Paul Boddie]

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