Obtaining the Python Control Flow Graph

[Carl Friedrich Bolz]

Hi!

brianlum at 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-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 (pypy-dev at codespeak.net) 
if you have PyPy-specific questions.

Cheers,

Carl Friedrich Bolz