changeset 151:d4601a70d734

Range analysis has its own distribute. Meaning that it can take meaningfull decisions about how the conditions of while and if influences the analysis. (But nothing clever yet).
author Sigurd Meldgaard <stm@daimi.au.dk>
date Thu, 03 Dec 2009 14:52:17 +0100
parents 23c816838ca2
children cf44c73dc17f
files pysmcl/range_analysis.py
diffstat 1 files changed, 42 insertions(+), 3 deletions(-) [+]
line wrap: on
line diff
--- a/pysmcl/range_analysis.py	Thu Dec 03 14:50:37 2009 +0100
+++ b/pysmcl/range_analysis.py	Thu Dec 03 14:52:17 2009 +0100
@@ -63,12 +63,15 @@
         """prime (integer) defines the field of computation, Zp."""
         self.prime = prime
 
-    def apply(self, function):
+    def apply(self, function, initial_env = {}):
         """Perform the analysis
 
         function (FunctioDef)
         """
-        flow.analyze(function, self.join, self.combine, self.key, lambda : {})
+        flow.analyze(function, self.join, self.combine, self.key,
+                     combine_env({'True' : (1,1), 'False' : (0,0)},
+                                  initial_env),
+                     self.distribute)
 
     def join(self, in_nodes):
         """The join function in the monotome framework.
@@ -84,6 +87,29 @@
             env = combine_env(env, n.out_values[self.key])
         return env
 
+    def is_comparison(self, test):
+        return (isinstance(test, ast.Compare) and
+                isinstance(test.ops[0], ast.LtE) and
+                isinstance(test.left, ast.Name) and
+                isinstance(test.comparators[0], ast.Num))
+
+    def distribute(self, x):
+        if isinstance(x, ast.If):
+            if self.is_comparison(x.test):
+                a = dict(x.out_values[self.key])
+                old = a[x.test.left.id]
+                compared_value = RangeVisitor(self.prime, x.out_values[self.key]).visit(x.test.comparators[0])
+                a[x.test.left.id] = (min(old[0], compared_value[1]),
+                                         min(old[1], compared_value[1]))
+                print(a, x.test.left.id)
+                x.body[0].in_values[self.key] = a
+                if len(x.orelse)>0:
+                    x.orelse[0].in_values[self.key] = x.out_values[self.key]
+        else:
+            for child in x.children:
+                child.in_values[self.key] = x.out_values[self.key]
+
+
     def combine(self, node, env):
         """The least upper bound of the node and the environment.
 
@@ -111,8 +137,18 @@
                 return env
 
             def visit_FunctionDef(self, node):
+                decorator = ast.get_ideal_functionality(node)
+                param_range = {}
+                if not decorator is None:
+                    for keyword in decorator.keywords:
+                        if keyword.arg == 'range':
+                            param_range = ast.literal_eval(keyword.value)
+                            break
                 for arg in node.args.args:
-                    env[arg.id] = full_range(self.prime)
+                    if not arg.id in param_range:
+                        env[arg.id] = full_range(self.prime)
+                    else:
+                        env[arg.id] = param_range[arg.id]
                 return env
 
             def visit_If(self, node):
@@ -127,6 +163,7 @@
             def visit_Expr(self, node):
                 return env
 
+
             def generic_visit(self, node):
                 assert False, "Not implemented: "+str(type(node))
 
@@ -208,6 +245,8 @@
         # expected functions
         if node.func.id == "random":
             return full_range(self.prime)
+        if node.func.id == "open":
+            return self.visit(node.args[0])
         if node.func.id == "random_bit":
             return (0, 1)
         return full_range(self.prime)