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:

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

   1 def foo(L):
   2     for x in L:
   3         if x < 0:
   4             continue
   5         if x < 10:
   6             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

   1 def foo(x):
   2     print y
   3     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