enhancements FlowGraph

## page was renamed from enhancements/Ast/FlowGraph

CEP904 - Control Flow Graph

• Status: Wanted
• Implementation status: Prototyped (not published)
• Comments: This is part of FabrizioM's GSoC 2008 project proposal
• Test status

NOTE: The text below is a stub.

Further information on Control Flow Graphs:

Wikipedia:

• http://en.wikipedia.org/wiki/Control_flow_graph
• http://en.wikipedia.org/wiki/Control_flow_analysis

PyPy:

• http://codespeak.net/pypy/dist/pypy/doc/translation.html#flow-model

---

This document describes the flow graph structure and some of the issues that it resolves:

Note: I assume that the readers knows what a flow graph is

Structure

The Basic Structure of the Flow Graph is composed as follows:

* FunctionGraph

• Variable
• Operation
• Link
• Block
• Costant

:

FunctionGraph:
      start : Block
      return : Block

Link:
      args : (Costant | Variable )*
      target : Block
      prevblock : Block

Block:
      inputargs : (Constant | Variable)*
      operations : Operation*
      exits : Link+

Variable:
      name : id

Constant:
      type : Type
      value : Object?

Operation:
      name : id
      args : (Costant | Variable )*
      result : Costant | Variable

FlowSpace:
      # maps a string to a generic object

FlowGraph

FunctionGraph

Variable

Operation

Link

Block

Costant

More description here

Flow Graph Construction from the AST

Look to AST

Using an Ast visitor you can produce a flowgraph example: visiting the Ast of the following code

#!python
def foo(L):
    for x in L:
        if x < 0:
            continue
        if x < 10:
            return x

will produce a structure, that can be represented as

digraph FuncGraph {
     BlockIterSetup(L) - Link(L) -> BlockIter
     BlockIter  - Link(x) ->  BlockTest1
     BlockTest1(True) -> BlockIter
     BlockTest1(False) -> BlockTest2
     BlockTest2(True)  -> ExitBlock
     BlockTest2(False) -> BlockIter

BlockTest1:
   Operation(LESS , x, Const(0)))

BlockTest2
   Operation(LESS , x, Const(10)))

ExitBlock:
   return
}

Resolution of existing Problems

Locals

Let's look to the Locals problem (this will be one fo the final goal of the Soc).

:

Scope

The Scope problem

#!python
def foo(x):
    print y
    y = x

How it will be resolved?

when the Ast of the above function will be visited by the FlowGeneratorVisitor it will try to do:

scope = FlowSpace()
ast.visit (FlowGeneratorVisitor(scope))

#...
class FlowGeneratorVisitor:
   def visitFunction(self, node)
    #...
    node.argnames.accept(self)
    node.code.accept(self)
    #...

 def visitArgs (self, node):
     #...
     self.scope.add(node.name, Variable(id=node.name))
     #..

 def visitCode (self, node):
     #... calling the other subnodes would produce something like
     return Block([ Operation (FUNCTION_CALL, func.name,
                    self.scope.get (func.arg.name),               # here it will raise an Error.
                                                                  # It will not find the 'y' name in the current scope.
                    result=self.scope.get(func.name).result)])


# the above function names are only for clearness, they are not part of the real AST

Comments