Obtaining the Python Control Flow Graph

[brianlum@gmail.com]

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_Buil d() in Python/symtable.c and compiler_mod() in
Python/compile.c. PySymtable_Buil d() 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]

Re: Obtaining the Python Control Flow Graph

Hi!

brianlum@gmail. com wrote:[color=blue]
> 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_Buil d() in Python/symtable.c and compiler_mod() in
> Python/compile.c. PySymtable_Buil d() 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[/color]

(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.
[color=blue]
> 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.[/color]

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 (pypy-dev@codespeak.n et)
if you have PyPy-specific questions.

Cheers,

Carl Friedrich Bolz

[Paul Boddie]

Re: Obtaining the Python Control Flow Graph

brianlum@gmail. com wrote:[color=blue]
>
> 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.[/color]

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