Obtaining the Python Control Flow Graph

Discussion in 'Python' started by brianlum@gmail.com, Apr 3, 2006.

  1. Guest

    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
    , Apr 3, 2006
    #1
    1. Advertising

  2. Hi!

    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 ()
    if you have PyPy-specific questions.

    Cheers,

    Carl Friedrich Bolz
    Carl Friedrich Bolz, Apr 3, 2006
    #2
    1. Advertising

  3. Paul Boddie Guest

    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
    Paul Boddie, Apr 3, 2006
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. pavs

    CONTROL FLOW GRAPH

    pavs, Feb 28, 2005, in forum: Java
    Replies:
    1
    Views:
    720
    bugbear
    Mar 7, 2005
  2. Replies:
    0
    Views:
    372
  3. Weng Tianxiang
    Replies:
    3
    Views:
    1,373
    Weng Tianxiang
    Jul 25, 2006
  4. Jack Dowson
    Replies:
    0
    Views:
    448
    Jack Dowson
    May 7, 2007
  5. Emilio Mayorga
    Replies:
    6
    Views:
    318
    Martien Verbruggen
    Oct 8, 2003
Loading...

Share This Page