changeset 149:2b8260064100

Flow: the flow analysis now takes an (optional) auxillary function distribute Choosing how data should flow from parent to child-node.
author Sigurd Meldgaard <stm@daimi.au.dk>
date Thu, 03 Dec 2009 14:49:20 +0100
parents c1d958858721
children 23c816838ca2
files pysmcl/flow.py
diffstat 1 files changed, 29 insertions(+), 10 deletions(-) [+]
line wrap: on
line diff
--- a/pysmcl/flow.py	Thu Dec 03 14:47:43 2009 +0100
+++ b/pysmcl/flow.py	Thu Dec 03 14:49:20 2009 +0100
@@ -1,12 +1,13 @@
 import pysmcl.ast_wrapper as ast
 import StringIO
+from copy import copy
 
 # Import PySMCL packages.
 from pysmcl.pretty_print import PrettyPrinter, pprint
 
 from pysmcl.graph import Node
 
-def analyze(function, join, combine, key, bottom):
+def analyze(function, join, combine, key, init, distribute=None):
     """
     Doing a simple intra procedural forward analysis using the
     iterative worklist algorithm. Parametrized by the functions join
@@ -14,18 +15,36 @@
     stored in each statement-node in_values and out_values, under the
     *key*.
 
-    function (FunctionDef) The function to analyze join (function) A
-    function which takes a set of nodes to be joined combine
-    (function) A function which implement the least upper bound or the
-    greates lower bound key (String) A string used to index into the
-    out_values dictionary bottom (function) A function which computes
-    the bottom element of the lattice
+    function (FunctionDef) The function to analyze 
+
+    join (function) A function which takes a set of nodes to be joined
+
+    combine (function) A function which implement the least upper
+    bound or the greatest lower bound
+
+    key (String) A string used to index into the out_values dictionary
+
+    init (Lattice point) The initial lattice point
     """
+    def default_distribute(x):
+            for child in x.children:
+                child.in_values[key] = x.out_values[key]
+
+    #if distribute is None:
+    distribute = default_distribute
+
     # initialization
-    worklist = []
 
     Flow().flow(function)
-    worklist+=[i for i in ast.walk(function) if isinstance(i,ast.stmt)]
+
+    statements = [i for i in ast.walk(function) if isinstance(i,ast.stmt)]
+
+    function.out_values[key]=copy(init)
+    for s in statements:
+        s.out_values[key] = copy(init)
+        s.in_values[key] = copy(init)
+
+    worklist=statements
 
     # main cycle
     while len(worklist) != 0:
@@ -33,9 +52,9 @@
         oldout = x.out_values[key]
         x.out_values[key] = combine(x, join(x.parents))
         if oldout != x.out_values[key]:
+            distribute(x)
             for child in x.children:
                 worklist.append(child)
-                child.in_values[key] = x.out_values[key]
 
 
 class Flow():