diff options
| author | Cliff Click <cliffc@acm.org> | 2024-09-05 15:58:08 -0700 |
|---|---|---|
| committer | Thalia Archibald <thalia@archibald.dev> | 2024-09-07 10:54:48 -0700 |
| commit | 511bbfc081de83a600197450a023131655592eaf (patch) | |
| tree | 18a7b78c093a0aef7f364f6e447a933de2707f58 /chapter14 | |
| parent | cb1adaabe4f78a30937a93abdcc2dfddd65e6f99 (diff) | |
| download | Simple-511bbfc081de83a600197450a023131655592eaf.tar.gz Simple-511bbfc081de83a600197450a023131655592eaf.zip | |
Fix possible monotonicity bug
Allow Add to smartly add ranges.
Diffstat (limited to 'chapter14')
4 files changed, 12 insertions, 0 deletions
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()); } |