changeset 59:088168175adb

Seems to pass the test now
author Sigurd Meldgaard <stm@daimi.au.dk>
date Tue, 26 May 2009 18:14:12 +0200
parents b8b250033b5e
children 06088bcf6ab3 f5f904ab0f46
files pysmcl/range_analysis.py
diffstat 1 files changed, 22 insertions(+), 16 deletions(-) [+]
line wrap: on
line diff
--- a/pysmcl/range_analysis.py	Tue May 26 17:35:27 2009 +0200
+++ b/pysmcl/range_analysis.py	Tue May 26 18:14:12 2009 +0200
@@ -3,10 +3,10 @@
 #
 #
 
-""" This module implements a range analysis of expressions in the 
+""" This module implements a range analysis of expressions in the
 core PySMCL language.
 
-The lattice is the power set lattice over all variables and their range in a given 
+The lattice is the power set lattice over all variables and their range in a given
 function. A range is represented as a tuple of two numbers or the bottom element.
 """
 
@@ -21,7 +21,7 @@
 
 class Bottom(object):
     """The element used to represent intervals that are not between 0 and p.
-    
+
     e.g. for the expression x = 2-5 yields the range for x (Bottom(), Bottom())
     """
     def __eq__(self, other):
@@ -51,7 +51,7 @@
 
     def join(self, in_nodes):
         """The join function in the monotome framework.
-        
+
         in_nodes (Set) a set of predecessor nodes.
         """
         if debug:
@@ -112,7 +112,7 @@
     return rangeVisitor.visit(node)
 
 class RangeVisitor(ast.NodeVisitor):
-    """RangeVisitor is the visitor which actually implements the 
+    """RangeVisitor is the visitor which actually implements the
     range computation."""
 
     def __init__(self, prime, env):
@@ -132,6 +132,15 @@
         return (0, self.prime)
 
     def visit_BinOp(self, node):
+        def liftMinus(a,b):
+            if(isinstance(a, Bottom) or
+               isinstance(b, Bottom)):
+                return Bottom()
+            c = a-b
+            if(c < 0):
+                return Bottom()
+            return c
+
         # operator = Add | Sub | Mult | Div | Mod | Pow | LShift
         #          | RShift | BitOr | BitXor | BitAnd | FloorDiv
         left = self.visit(node.left)
@@ -147,12 +156,8 @@
             return (r0, r1)
 
         if isinstance(node.op, ast.Sub):
-            r0 = left[0] - right[1]
-            r1 = left[1] - right[0]
-            if r0 < 0:
-                r0 = Bottom()
-            if r1 < 0:
-                r1 = Bottom()
+            r0 = liftMinus(left[0], right[1])
+            r1 = liftMinus(left[1], right[0])
             return (r0, r1)
 
         if isinstance(node.op, ast.Mult):
@@ -222,14 +227,15 @@
 
 def combine_range((l1, h1), (l2, h2)):
     """Combine the two ranges."""
-    r = (Buttom(),Buttom())
+    (r0, r1) = (Bottom(),Bottom())
     if l1 < l2:
         r[0] = l1
+        r0 = l1
     else:
-        r[0] = l2
+        r0 = l2
 
     if h1 > h2:
-        r[1] = h1
+        r1 = h1
     else:
-        r[1] = h2
-    return r
+        r1 = h2
+    return (r0,r1)