From 511bbfc081de83a600197450a023131655592eaf Mon Sep 17 00:00:00 2001
From: Cliff Click <cliffc@acm.org>
Date: Thu, 5 Sep 2024 15:58:08 -0700
Subject: Fix possible monotonicity bug

Allow Add to smartly add ranges.
---
 chapter14/src/main/java/com/seaofnodes/simple/node/AddNode.java | 9 +++++++++
 chapter14/src/main/java/com/seaofnodes/simple/node/DivNode.java | 1 +
 chapter14/src/main/java/com/seaofnodes/simple/node/MulNode.java | 1 +
 chapter14/src/main/java/com/seaofnodes/simple/node/SubNode.java | 1 +
 4 files changed, 12 insertions(+)

(limited to 'chapter14/src/main/java/com/seaofnodes')

diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/AddNode.java
index d2dfce16..e653597e 100644
--- a/chapter14/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/chapter14/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -23,12 +23,21 @@ public class AddNode extends Node {
     public Type compute() {
         if( in(1)._type instanceof TypeInteger i0 &&
             in(2)._type instanceof TypeInteger i1 ) {
+            if( i0.isHigh() || i1.isHigh() ) return TypeInteger.TOP;
             if (i0.isConstant() && i1.isConstant())
                 return TypeInteger.constant(i0.value()+i1.value());
+            // Fold ranges like {0-1} + {2-3} into {2-4}.
+            if( !overflow(i0._min,i1._min) &&
+                !overflow(i0._max,i1._max) )
+                return TypeInteger.make(i0._min+i1._min,i0._max+i1._max);
         }
         return TypeInteger.BOT;
     }
 
+    private static boolean overflow( long x, long y ) {
+        if( (x ^    y ) < 0 ) return false; // unequal signs, never overflow
+        return (x ^ (x + y)) < 0; // sum has unequal signs, so overflow
+    }
     @Override
     public Node idealize () {
         Node lhs = in(1);
diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/DivNode.java
index 329c5824..5a176000 100644
--- a/chapter14/src/main/java/com/seaofnodes/simple/node/DivNode.java
+++ b/chapter14/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -23,6 +23,7 @@ public class DivNode extends Node {
     public Type compute() {
         if (in(1)._type instanceof TypeInteger i0 &&
             in(2)._type instanceof TypeInteger i1) {
+            if( i0.isHigh() || i1.isHigh() ) return TypeInteger.TOP;
             if (i0.isConstant() && i1.isConstant())
                 return i1.value() == 0
                     ? TypeInteger.ZERO
diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/MulNode.java
index f5166a66..f779989b 100644
--- a/chapter14/src/main/java/com/seaofnodes/simple/node/MulNode.java
+++ b/chapter14/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -23,6 +23,7 @@ public class MulNode extends Node {
     public Type compute() {
         if (in(1)._type instanceof TypeInteger i0 &&
             in(2)._type instanceof TypeInteger i1) {
+            if( i0.isHigh() || i1.isHigh() ) return TypeInteger.TOP;
             if (i0.isConstant() && i1.isConstant())
                 return TypeInteger.constant(i0.value()*i1.value());
         }
diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/SubNode.java
index 5e91ae53..6c64bc4f 100644
--- a/chapter14/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/chapter14/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -24,6 +24,7 @@ public class SubNode extends Node {
     public Type compute() {
         if (in(1)._type instanceof TypeInteger i0 &&
             in(2)._type instanceof TypeInteger i1) {
+            if( i0.isHigh() || i1.isHigh() ) return TypeInteger.TOP;
             if (i0.isConstant() && i1.isConstant())
                 return TypeInteger.constant(i0.value()-i1.value());
         }
-- 
cgit v1.2.3