summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorCliff Click <cliffc@acm.org>2024-08-06 13:09:38 +0100
committerCliff Click <cliffc@acm.org>2025-04-24 14:38:36 -0700
commit773344c88d5be5efc2a5b8397e764375cd9c16a8 (patch)
tree38357a72a4fdc17eeb8318c292fc3deb61288294
parentfffa2b9d187985e50d6c2de1b5fc9334040d0479 (diff)
downloadSimple-773344c88d5be5efc2a5b8397e764375cd9c16a8.tar.gz
Simple-773344c88d5be5efc2a5b8397e764375cd9c16a8.zip
Chapter 14: Narrow types
Co-authored-by: Thalia Archibald <thalia@archibald.dev> Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk> Co-authored-by: tannal <tannal2409@gmail.com> Co-authored-by: hadha <helsgithub15@gmail.com> Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: RobertObkircher <robert.obkircher@gmail.com> Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>
-rw-r--r--README.md2
-rw-r--r--docs/chapter14/14-grammar.md124
-rw-r--r--docs/chapter14/Makefile12
-rw-r--r--docs/chapter14/README.md350
-rw-r--r--docs/chapter14/lattice.gv202
-rw-r--r--docs/chapter14/lattice.svg691
-rw-r--r--src/main/java/com/seaofnodes/simple/Parser.java106
-rw-r--r--src/main/java/com/seaofnodes/simple/node/AddNode.java24
-rw-r--r--src/main/java/com/seaofnodes/simple/node/AndNode.java66
-rw-r--r--src/main/java/com/seaofnodes/simple/node/BoolNode.java88
-rw-r--r--src/main/java/com/seaofnodes/simple/node/DivNode.java15
-rw-r--r--src/main/java/com/seaofnodes/simple/node/LoadNode.java4
-rw-r--r--src/main/java/com/seaofnodes/simple/node/MemOpNode.java2
-rw-r--r--src/main/java/com/seaofnodes/simple/node/MinusNode.java8
-rw-r--r--src/main/java/com/seaofnodes/simple/node/MulNode.java13
-rw-r--r--src/main/java/com/seaofnodes/simple/node/Node.java13
-rw-r--r--src/main/java/com/seaofnodes/simple/node/NotNode.java3
-rw-r--r--src/main/java/com/seaofnodes/simple/node/OrNode.java63
-rw-r--r--src/main/java/com/seaofnodes/simple/node/PhiNode.java25
-rw-r--r--src/main/java/com/seaofnodes/simple/node/RoundF32Node.java38
-rw-r--r--src/main/java/com/seaofnodes/simple/node/SarNode.java56
-rw-r--r--src/main/java/com/seaofnodes/simple/node/ShlNode.java53
-rw-r--r--src/main/java/com/seaofnodes/simple/node/ShrNode.java56
-rw-r--r--src/main/java/com/seaofnodes/simple/node/SubFNode.java2
-rw-r--r--src/main/java/com/seaofnodes/simple/node/SubNode.java14
-rw-r--r--src/main/java/com/seaofnodes/simple/node/XorNode.java63
-rw-r--r--src/main/java/com/seaofnodes/simple/type/Type.java2
-rw-r--r--src/main/java/com/seaofnodes/simple/type/TypeFloat.java73
-rw-r--r--src/main/java/com/seaofnodes/simple/type/TypeInteger.java110
-rw-r--r--src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java2
-rw-r--r--src/test/java/com/seaofnodes/simple/Chapter06Test.java6
-rw-r--r--src/test/java/com/seaofnodes/simple/Chapter07Test.java1
-rw-r--r--src/test/java/com/seaofnodes/simple/Chapter10Test.java10
-rw-r--r--src/test/java/com/seaofnodes/simple/Chapter11Test.java2
-rw-r--r--src/test/java/com/seaofnodes/simple/Chapter12Test.java1
-rw-r--r--src/test/java/com/seaofnodes/simple/Chapter13Test.java2
-rw-r--r--src/test/java/com/seaofnodes/simple/Chapter14Test.java317
-rw-r--r--src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java6
-rw-r--r--src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java47
39 files changed, 2489 insertions, 183 deletions
diff --git a/README.md b/README.md
index b9f27495..0714d1c9 100644
--- a/README.md
+++ b/README.md
@@ -57,7 +57,7 @@ The Simple language is styled after a subset of C or Java.
* [Chapter 11](docs/chapter11/README.md): Global Code Motion - Scheduling.
* [Chapter 12](docs/chapter12/README.md): Float type.
* [Chapter 13](docs/chapter13/README.md): Nested references in Structs.
-* Chapter 14: Narrow primitive types (e.g. bytes)
+* [Chapter 14](docs/chapter14/README.md): Narrow primitive types (e.g. bytes)
* Chapter 15: One dimensional static length array type, with array loads and stores.
* Chapter 16: Constructors
* Chapter 17: Mutability & Syntax Sugar: `var`, `val`, `x+=y`, `for(init; test; next) body`
diff --git a/docs/chapter14/14-grammar.md b/docs/chapter14/14-grammar.md
new file mode 100644
index 00000000..a6d4df42
--- /dev/null
+++ b/docs/chapter14/14-grammar.md
@@ -0,0 +1,124 @@
+# Grammar for Chapter 14
+
+```antlrv4
+grammar SimpleLanguage;
+
+program : block EOF ;
+
+block : statement+ ;
+
+
+statement
+ : '{' block '}'
+ | returnStatement
+ | ifStatement
+ | whileStatement
+ | breakStatement
+ | continueStatement
+ | metaStatement
+ | structDeclaration
+ | expressionStatement
+ ;
+
+
+returnStatement : 'return' expression ';' ;
+
+ifStatement : 'if' '(' expression ')' statement ('else' statement)? ;
+
+whileStatement : 'while' '(' expression ')' statement ;
+
+breakStatement : 'break' ';' ;
+
+continueStatement : 'continue' ';' ;
+
+metaStatement : '#showGraph' ';' ;
+
+structDeclaration : 'struct' IDENTIFIER '{' fields '}' ;
+
+fields : field+ ;
+
+field : type IDENTIFIER ';' ;
+
+
+expressionStatement
+ : type IDENTIFIER ';'
+ | type IDENTIFIER '=' expression ';'
+ | IDENTIFIER '=' expression ';'
+ | expression
+ ;
+
+PRIMTYPE
+ : 'int'
+ | 'i8'
+ | 'i16'
+ | 'i32'
+ | 'i64'
+ | 'u8'
+ | 'u16'
+ | 'u32'
+ | 'flt'
+ | 'f32'
+ | 'f64'
+ | 'bool'
+ ;
+
+type
+ : PRIMTYPE
+ | typeName ('?')?
+ ;
+
+typeName : IDENTIFIER ;
+
+
+expression : bitWiseExpression ;
+
+bitWiseExpression
+ : comparisonExpression ( '&' | '|' | '^' ) comparisonExpression)*
+ ;
+
+comparisonExpression
+ : shiftExpression (('==' | '!='| '>'| '<'| '>='| '<=') shiftExpression)*
+ ;
+
+shiftExpression
+ : additiveExpression ( '<<' | '>>>' | '>>' ) additiveExpression)*
+ ;
+
+additiveExpression
+ : multiplicativeExpression (('+' | '-') multiplicativeExpression)*
+ ;
+
+multiplicativeExpression
+ : unaryExpression (('*' | '/') unaryExpression)*
+ ;
+
+unaryExpression
+ : ('-') unaryExpression
+ | '!' unaryExpression
+ | primaryExpression postFix*
+ ;
+
+primaryExpression
+ : INTEGER_LITERAL
+ | '(' expression ')'
+ | 'true'
+ | 'false'
+ | 'null'
+ | newExpression
+ | IDENTIFIER
+ ;
+
+newExpression : 'new' IDENTIFIER ;
+
+postFix : '.' IDENTIFIER [ '=' expression ] ;
+
+INTEGER_LITERAL
+ : [1-9]DIGIT*
+ | [0]
+ ;
+
+IDENTIFIER : NON_DIGIT (NON_DIGIT | DIGIT)* ;
+
+NON_DIGIT: [a-zA-Z_];
+DIGIT: [0-9];
+```
diff --git a/docs/chapter14/Makefile b/docs/chapter14/Makefile
new file mode 100644
index 00000000..12659b8f
--- /dev/null
+++ b/docs/chapter14/Makefile
@@ -0,0 +1,12 @@
+GV := $(wildcard *.gv)
+SVG := $(patsubst %.gv,%.svg,$(GV))
+
+.PHONY: all
+all: $(SVG)
+
+%.svg: %.gv
+ dot -Tsvg $< > $@
+
+.PHONY: clean
+clean:
+ @rm -f $(SVG)
diff --git a/docs/chapter14/README.md b/docs/chapter14/README.md
new file mode 100644
index 00000000..49b0c5b9
--- /dev/null
+++ b/docs/chapter14/README.md
@@ -0,0 +1,350 @@
+# Chapter 14: Narrow types
+
+# Table of Contents
+
+1. [Narrow Word Types](#narrow-or-sub-word-types)
+2. [OverFlow handling](#overflow-handling)
+3. [Integer ranges](#integer-ranges)
+4. [Bitwise operations](#examples)
+5. [Precedence](#precedence)
+6. [Type lattice](#type-implementation)
+7. [Nodes](#nodes)
+
+
+In this chapter, we add sub-word integer types.
+
+You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter14) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter13...linear-chapter14) it to the previous chapter.
+
+## Narrow or sub-word types
+
+Narrow or sub-worded integer types refer to integer data types that occupy less memory (fewer bits) than the standard or "full-width"(Typically 32, or 64 bits) integer types provided by a system or programming language.
+
+
+As a prelude to arrays, especially arrays of bytes common in all networking
+codes, Simple needs some way to manipulate sub-word integer types.
+Computations are always done in 64 bits for both integer and float ops, but
+will be truncated (rounded) on a variable or field assignment, and (sign)
+extended on a load.
+
+```java
+i8 x = 123456789;
+if( x != 21 )
+ return false;
+return true;
+```
+
+The variable `x` is limited to 8 bits signed. Assigning the vary large value
+`123456789` (hex `0x75BCD15`) simply truncates to 8 bits yielding `21 (0x15)`.
+The value is sign-extended on a load.
+
+```java
+i16 x = 123456789;
+if( x != -13035 )
+ return false;
+return true;
+```
+
+The variable `x` is limited to 16 bits signed. Assigning the vary large value
+`0x75BCD15` simply truncates to 16 bits yielding `0xCD15`. The value is
+sign-extended on a load yielding `-13035 (0xFFFF FFFF FFFF CD15)`.
+
+```java
+u16 x = 123456789;
+if( x != 52501 )
+ return false;
+return true;
+```
+
+The variable `x` is limited to 16 bits unsigned. Assigning the vary large value
+`0x75BCD15` simply truncates to 16 bits yielding `0xCD15`. The value is
+zero-extended on a load yielding `52501 (0x0000 0000 0000 CD15)`.
+
+Similarly, floats can be limited to IEEE754 32-bit standard format and will be
+rounded when assigned, and inflated to 64-bits when loaded.
+
+The complete list of primitive types is now:
+
+| Data Type | Size (Bits) | Description |
+|-----------|-------------|--------------------------------------------------------------|
+| `int`, `i64` | 64 | 64-bit signed integer, matching modern hardware. |
+| `u64` | 64 | **Not implemented**, hints at behavior beyond 64-bit. |
+| `i32` | 32 | 32-bit signed integer, sign-extended on load. |
+| `u32` | 32 | 32-bit unsigned integer, zero-extended on load. |
+| `i16` | 16 | 16-bit signed integer, sign-extended on load. |
+| `u16` | 16 | 16-bit unsigned integer, zero-extended on load. |
+| `i8` | 8 | 8-bit signed integer, sign-extended on load. |
+| `u8` | 8 | 8-bit unsigned integer, zero-extended on load. |
+| `i1` | 1 | 1-bit signed integer, sign-extended on load. |
+| `u1` | 1 | 1-bit unsigned integer, zero-extended on load. |
+| `bool` | 1 | Alias for `u1`. |
+| `flt`, `f64`| 64 | IEEE 754 64-bit floating-point number, often called a double. |
+| `f32` | 32 | IEEE 754 32-bit floating-point number. |
+
+## Overflow handling
+
+An integer overflow occurs when you attempt to store inside an integer variable a value that is larger than the maximum value the variable can hold.
+There are several cases of overflow:
+
+#### Unsigned(fixed-width) integer overflow:
+
+```java
+u8 a = 255;
+u8 b = a + 1; // match u8 type against expr.type
+// a = 256
+// u8 = [0...255]
+return b;
+```
+The expression type does not match the type that was provided. expr: ConstantNode(256) t: u8(0, 255)
+```java
+private Node parseExpressionStatement() {
+ Type t = type(); // u8 = [0...255]
+ ...
+ // expr.type = TypeInteger(256);
+ // Auto-narrow wide ints to narrow ints
+ expr = zsMask(expr,t);
+}
+```
+Since it is unsigned we just do a bitmask on the new value that overflows the specified type:
+The operands to the "bitwise AND" are the values(256) and the mask(255, max boundary).
+This is called truncating.
+
+`ZsMask:`
+```java
+ // zero/sign extend. "i" is limited to either classic unsigned (min==0) or
+ // classic signed (min=minus-power-of-2); max=power-of-2-minus-1.
+private Node zsMask(Node val, Type t ) {
+ if( !(val._type instanceof TypeInteger tval && t instanceof TypeInteger t0 && !tval.isa(t0)) ) {
+ if( !(val._type instanceof TypeFloat tval && t instanceof TypeFloat t0 && !tval.isa(t0)) )
+ return val;
+ // Float rounding
+ return new RoundF32Node(val).peephole();
+ }
+ if( t0._min==0 ) // Unsigned
+ return new AndNode(val,new ConstantNode(TypeInteger.constant(t0._max)).peephole()).peephole();
+ // Signed extension
+ int shift = Long.numberOfLeadingZeros(t0._max)-1;
+ Node shf = new ConstantNode(TypeInteger.constant(shift)).peephole();
+ if( shf._type==TypeInteger.ZERO )
+ return val;
+ return new SarNode(new ShlNode(val,shf.keep()).peephole(),shf.unkeep()).peephole();
+}
+```
+
+The truncation is done by the `AndNode`:
+```java
+...
+if( t0._min==0 ) // Unsigned
+ return new AndNode(val,con(t0._max)).peephole();
+```
+Since they are constants, after calling peephole it truns into`256 & 255` = 0;
+Output:
+```
+return 0;
+```
+
+#### Maximum integer overflow
+```java
+i64 a = 9223372036854775807;
+i64 b = a + 1;
+return b;
+```
+When we are computing the addition, we make sure they don't overflow:
+
+`AddNode.overflow:`
+```java
+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
+}
+```
+`AddNode.compute`
+```java
+...
+// Fold ranges like {0-1} + {2-3} into {2-4}.
+if( !overflow(i1._min,i2._min) &&
+ !overflow(i1._max,i2._max) )
+ return TypeInteger.make(i1._min+i2._min,i1._max+i2._max);
+```
+Here **x + y** overflows and becomes **negative**, x ^ negative = negative. Any negative number is less than 0, so it returns true.
+If it **overflows** we just return the bottom type of TypeInteger.
+```
+ return TypeInteger.BOT; // []
+```
+However, in our case we are dealing with constants, so we just allow the overflow naturally here:
+```java
+// i1: 9223372036854775807
+// i2: 1
+// i1 + i2 will overflow.
+return TypeInteger.constant(i1.value()+i2.value()); // -9223372036854775808;
+```
+
+#### Adding constant ranges
+```java
+u8 a = 12;
+u8 b = 13;
+u8 c = 124;
+u8 d = a + b + c;
+return d;
+```
+if `is_con` is true, then generally we can state: `min = max`.
+Such that:
+```java
+public static TypeInteger make(boolean is_con, long con) {
+ return make(is_con ? con : (con==0 ? Long.MAX_VALUE : Long.MIN_VALUE),
+ is_con ? con : (con==0 ? Long.MIN_VALUE : Long.MAX_VALUE));
+```
+- This results in:
+```java
+return make(con, con);
+```
+
+`value()` is only called in constants, e.g `_min == _max;` invariants holds, then since
+both `min_` and `max_` are equal, we can return either one.
+
+This is the same as regular additions:
+```java
+public long value() { assert isConstant(); return _min; }
+```
+
+#### Truncate(2)
+
+```java
+u8 a = arg; // arg & 255
+u8 b = arg; // arg & 255(same as a)
+u8 c = a + b; // (arg&255)*2, type = TypeInteger.BOT
+return c; // (((arg&255)*2)&255), type = TypeInteger.U8
+```
+
+Same as before, **arg** turns into **(arg&255)**, this node is then inserted into the **GVN** table and **b** retrieves this value.
+The AddNode peephole will change them into `((arg&255)*2`, and put on extra mask
+on the expression to keep it in the valid boundaries.
+
+
+## Integer ranges
+Link hacker's delight here.
+
+For range math, visit:[^1]
+## Bitwise operations
+We support the following bitwise operators:
+And `&`, Or `|`, Xor `^`, Shift left `<<`, Shift right `>>`, Shift right zero `>>>`
+
+| Operator | Symbol | Description |
+|--------------------------|---------|---------------------------------------------------------------------------------------------------------|
+| **And** | `&` | Performs a bitwise AND operation. |
+| **Or** | `\|` | Performs a bitwise OR (inclusive OR) operation. |
+| **Xor** | `^` | Performs a bitwise XOR (exclusive OR) operation. |
+| **Shift Left** | `<<` | Shifts bits to the left, filling with zeros. |
+| **Shift Right** | `>>` | Shifts bits to the right, any vacated bit postions are filled by replicating the value of the sign bit. |
+| **Unsigned Right Shift** | `>>>` | Shifts bits to the right, any vacated bit postions are always filled with zero |
+
+Note `>>>` is a logical shift and not an arithmetic shift.
+
+#### AndNode:
+
+##### lhs & -1 = lhs;
+```java
+// And of -1. We do not check for (-1&x) because this will already
+// canonicalize to (x&-1)
+if( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==-1 )
+return lhs;
+
+```
+
+#### OrNode:
+##### lhs | 0 = lhs;
+```java
+// Or of 0. We do not check for (0|x) because this will already
+// canonicalize to (x|0)
+if( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==0 )
+return lhs;
+
+```
+
+#### Shift right
+lhs >> 0 = lhs;
+```java
+// Sar of 0.
+if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 )
+ return lhs;
+```
+
+#### Shift left
+lhs << 0 = lhs;
+```java
+// Shl of 0.
+if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 )
+ return lhs;
+
+```
+#### Unsigned right shift
+lhs >>> 0 = lhs;
+```java
+// Shr of 0.
+if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 )
+return lhs;
+```
+
+#### XorNode:
+##### lhs ^ 0 = lhs;
+```java
+// Xor of 0. We do not check for (0^x) because this will already
+// canonicalize to (x^0)
+if( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==0 )
+ return lhs;
+
+```
+### precedence
+
+Bitwise operators have the lowest precedence, e.g
+```
+arg + 123 & 3 = (arg + 123) & 3
+```
+
+## Type Implementation
+
+The <font style="background-color:lightblue">TypeInteger type</font> class is
+reworked to support a full range of min/max values. At this time, only some
+power-of-2 sized ranges are exposed to the programmer but the optimizer
+internally supports all ranges. The MEET operation takes the min-of-mins and
+max-of-maxes. The DUAL operation inverts the min and max.
+
+Example: the constant `0` has `[0...0]`.
+
+Example: the `bool` type has the range `[0...1]`.
+
+Example: the `u8` type has the range `[0...255]`.
+
+Example: the `i8` type has the range `[-128...127]`.
+
+Example: the `dual` of `bool` is `[1...0]` (just swap min and max).
+
+The <font style="background-color:aqua">TypeFloat</font> class is also reworked to support 32-bit and 64-bit sizes.
+
+![Graph1](./lattice.svg)
+
+### meet:
+
+Meet of two ranges:
+```java
+@Override
+public Type xmeet(Type other) {
+// Invariant from caller: 'this' != 'other' and same class (TypeInteger)
+TypeInteger i = (TypeInteger)other; // Contract
+return make(Math.min(_min,i._min), Math.max(_max,i._max));
+}
+```
+Combine all values that could possibly occur within either range.
+
+## Nodes
+
+Added this Chapter are some bit-manipulation Nodes representing common hardware
+ops to mask, shift, sign-extend and round bits. The truncation and extension
+logic uses these. They are otherwise very similar to the previous
+`Add/Sub/Mul/Div` Nodes but with slightly different constant math and
+slightly different `idealize()` calls.
+
+
+
+[^1]: Hacker's delight.
+ 4-2 Propagating Bounds through Add's and Subtract's
+
diff --git a/docs/chapter14/lattice.gv b/docs/chapter14/lattice.gv
new file mode 100644
index 00000000..4a8b1d4c
--- /dev/null
+++ b/docs/chapter14/lattice.gv
@@ -0,0 +1,202 @@
+digraph Lattice {
+ compound = true;
+ // Define nodes
+ splines=false;
+ node [shape=circle, style=filled];
+ nodesep=0.6;
+
+ TOP [label=<<B>⊤</B >>, fillcolor=black, fontcolor=white];
+ BOT [label=<<B>⊥</B>>, fillcolor=black, fontcolor=white];
+
+ // ----------------------
+ // Control
+ XCTRL [label=<<B>⊤</B >:ctrl>, fillcolor=yellow, shape=oval];
+ CTRL [label=<<B>⊥</B>:ctrl>, fillcolor=yellow, shape=oval];
+
+ TOP -> XCTRL;
+ XCTRL -> CTRL;
+ CTRL -> BOT;
+
+ // ----------------------
+ // Integers
+ INT_TOP [label=<<B>⊤</B >:int>, fillcolor=lightblue, shape=oval];
+ INT_BOT [label=<<B>⊥</B>:int>, fillcolor=lightblue, shape=oval];
+
+ INT_HI [label="max < min" , fillcolor=lightblue, shape=oval];
+ INT_XBOOL [label="1...0", fillcolor=lightblue, shape=oval];
+ INT_CON [label="constants", fillcolor=lightblue, shape=oval];
+ INT_CON0 [label="0", fillcolor=lightblue];
+ INT_CON1 [label="1", fillcolor=lightblue];
+ INT_BOOL [label="0...1", fillcolor=lightblue,shape=oval];
+ INT_LO [label="max > min" , fillcolor=lightblue, shape=oval];
+
+ TOP -> INT_TOP;
+ INT_TOP -> INT_HI;
+ INT_HI -> INT_XBOOL;
+ INT_XBOOL -> INT_CON0;
+ INT_XBOOL -> INT_CON1;
+ INT_HI -> INT_CON;
+ INT_CON0 -> INT_BOOL;
+ INT_CON1 -> INT_BOOL;
+ INT_BOOL -> INT_LO;
+ INT_CON -> INT_LO;
+ INT_LO -> INT_BOT;
+ INT_BOT -> BOT;
+
+ INT_CON0 -> INT_CON1 -> INT_CON [style=invis];
+
+ // ----------------------
+ // Integers
+ FLT_TOP [label=<<B>⊤</B >:flt>, fillcolor=aqua, shape=oval];
+ FLT_BOT [label=<<B>⊥</B>:flt>, fillcolor=aqua, shape=oval];
+
+ FLT_CON64 [label="64b consts\n[excludes\n32b consts]" , fillcolor=aqua, shape=oval];
+ FLT_CON32 [label="32b consts", fillcolor=aqua, shape=oval];
+ FLT_CONPI [label="3.14159...", fillcolor=aqua, shape=oval];
+ FLT_X32 [label="~f32", fillcolor=aqua];
+ FLT_CON0 [label="0." , fillcolor=aqua];
+ FLT_32 [label="f32" , fillcolor=aqua];
+
+ TOP -> FLT_TOP;
+ FLT_TOP -> FLT_CON64
+ FLT_TOP -> FLT_CONPI
+ FLT_CON64 -> FLT_BOT
+ FLT_CONPI -> FLT_BOT
+
+ FLT_TOP -> FLT_X32;
+ FLT_X32 -> FLT_CON0;
+ FLT_X32 -> FLT_CON32;
+ FLT_CON0 -> FLT_32;
+ FLT_CON32 -> FLT_32;
+ FLT_32 -> FLT_BOT
+
+ FLT_BOT -> BOT;
+
+ FLT_CON0 -> FLT_CON32 -> FLT_CONPI -> FLT_CON64 [style=invis];
+
+
+ // ----------------------
+ // Pointers, just a boolean nil/not and a struct
+ PTR [shape=none, fillcolor=none, label=<
+ <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+ <TR><TD BGCOLOR="green"><FONT color="white">*ptr</FONT></TD></TR>
+ <TR><TD BGCOLOR="lightgreen">struct</TD></TR>
+ </TABLE>
+ >];
+ PTR0 [shape=none, fillcolor=none, label=<
+ <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+ <TR><TD BGCOLOR="green"><FONT color="white">*ptr?</FONT></TD></TR>
+ <TR><TD BGCOLOR="lightgreen">struct</TD></TR>
+ </TABLE>
+ >];
+
+ TOP -> PTR;
+ PTR -> PTR0;
+ PTR0 -> BOT;
+
+ // ----------------------
+ // Structs
+ STRUCT_TOP [label=<<B>⊤</B >:struct>, fillcolor=lightgreen, shape=oval];
+ STRUCT_BOT [label=<<B>⊥</B>:struct>, fillcolor=lightgreen, shape=oval];
+
+ STRUCT_S1 [shape=none, fillcolor=none, label=<
+ <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+ <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR>
+ </TABLE>
+ >];
+ STRUCT_S2 [shape=none, fillcolor=none, label=<
+ <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+ <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR>
+ <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR>
+ </TABLE>
+ >];
+ STRUCT_SN [shape=none, fillcolor=none, label=<
+ <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+ <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR>
+ <TR><TD BGCOLOR="lightgreen">... </TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR>
+ <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR>
+ </TABLE>
+ >];
+
+
+ TOP -> STRUCT_TOP;
+ STRUCT_TOP -> STRUCT_S1;
+ STRUCT_TOP -> STRUCT_S2;
+ STRUCT_TOP -> STRUCT_SN;
+ STRUCT_S1 -> STRUCT_BOT;
+ STRUCT_S2 -> STRUCT_BOT;
+ STRUCT_SN -> STRUCT_BOT;
+ STRUCT_BOT -> BOT;
+
+ STRUCT_S1 -> STRUCT_S2 -> STRUCT_SN [style=invis];
+
+ // ----------------------
+ // Memory
+ MEM_TOP [label=<<B>⊤</B >:mem>, fillcolor=blue, fontcolor=white, shape=oval];
+ MEM_BOT [label=<<B>⊥</B>:mem>, fillcolor=blue, fontcolor=white, shape=oval];
+ MEM_ALIAS1 [label="#1" , fillcolor=blue, fontcolor=white];
+ MEM_ALIASDOTS [label="..." , fillcolor=blue, fontcolor=white, shape=oval];
+ MEM_ALIASN [label="#n" , fillcolor=blue, fontcolor=white];
+
+ TOP -> MEM_TOP;
+ MEM_TOP -> MEM_ALIAS1;
+ MEM_TOP -> MEM_ALIASDOTS;
+ MEM_TOP -> MEM_ALIASN;
+ MEM_ALIAS1 -> MEM_BOT;
+ MEM_ALIASDOTS -> MEM_BOT;
+ MEM_ALIASN -> MEM_BOT;
+ MEM_BOT -> BOT;
+
+ MEM_ALIAS1 -> MEM_ALIASDOTS -> MEM_ALIASN [style=invis];
+
+ // ----------------------
+ // Tuples
+
+ TUPLE_TOP [label=<<B>⊤</B >:tuple>, fillcolor=pink, shape=oval];
+ TUPLE_BOT [label=<<B>⊥</B>:tuple>, fillcolor=pink, shape=oval];
+
+ TUPLE1 [shape=none, fillcolor=none, label=<
+ <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+ <TH><TD BGCOLOR="pink">Tuple</TD></TH>
+ <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR>
+ </TABLE>
+ >];
+ TUPLE2 [shape=none, fillcolor=none, label=<
+ <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+ <TH><TD BGCOLOR="pink">Tuple</TD></TH>
+ <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR>
+ <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR>
+ </TABLE>
+ >];
+ TUPLEN [shape=none, fillcolor=none, label=<
+ <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+ <TH><TD BGCOLOR="pink">Tuple</TD></TH>
+ <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR>
+ <TR><TD BGCOLOR="black" ><FONT color="white">...</FONT></TD></TR>
+ <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR>
+ </TABLE>
+ >];
+
+
+ TOP -> TUPLE_TOP;
+ TUPLE_TOP -> TUPLE1;
+ TUPLE_TOP -> TUPLE2;
+ TUPLE_TOP -> TUPLEN;
+ TUPLE1 -> TUPLE_BOT;
+ TUPLE2 -> TUPLE_BOT;
+ TUPLEN -> TUPLE_BOT;
+ TUPLE_BOT -> BOT;
+
+ // ----------------------
+ // Additional customization
+ {rank=same; TOP;}
+ {rank=same; INT_TOP; FLT_TOP; XCTRL; PTR; STRUCT_TOP; MEM_TOP; TUPLE_TOP}
+ {rank=same; INT_CON; INT_CON0; INT_CON1;
+ FLT_CON32; FLT_CON64; FLT_CON0; FLT_CONPI;
+ STRUCT_S1; STRUCT_S2; STRUCT_SN;
+ MEM_ALIAS1; MEM_ALIASDOTS; MEM_ALIASN;
+ TUPLE1; TUPLE2; TUPLEN;
+ }
+ {rank=same; INT_BOT; FLT_BOT; CTRL; PTR0; STRUCT_BOT; MEM_BOT; TUPLE_BOT}
+ {rank=same; BOT;}
+}
diff --git a/docs/chapter14/lattice.svg b/docs/chapter14/lattice.svg
new file mode 100644
index 00000000..99f74ed0
--- /dev/null
+++ b/docs/chapter14/lattice.svg
@@ -0,0 +1,691 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
+ "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+<!-- Generated by graphviz version 12.2.0 (20241103.1931)
+ -->
+<!-- Title: Lattice Pages: 1 -->
+<svg width="1800pt" height="760pt"
+ viewBox="0.00 0.00 1800.00 759.54" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
+<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 755.54)">
+<title>Lattice</title>
+<polygon fill="white" stroke="none" points="-4,4 -4,-755.54 1796,-755.54 1796,4 -4,4"/>
+<!-- TOP -->
+<g id="node1" class="node">
+<title>TOP</title>
+<ellipse fill="black" stroke="black" cx="829" cy="-730.42" rx="21.12" ry="21.12"/>
+<text text-anchor="start" x="821.12" y="-725.99" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00" fill="white">⊤</text>
+</g>
+<!-- XCTRL -->
+<g id="node3" class="node">
+<title>XCTRL</title>
+<ellipse fill="yellow" stroke="black" cx="45" cy="-646.79" rx="36.51" ry="18"/>
+<text text-anchor="start" x="26.25" y="-642.74" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text>
+<text text-anchor="start" x="42" y="-642.74" font-family="Times New Roman,serif" font-size="14.00">:ctrl</text>
+</g>
+<!-- TOP&#45;&gt;XCTRL -->
+<g id="edge1" class="edge">
+<title>TOP&#45;&gt;XCTRL</title>
+<path fill="none" stroke="black" d="M807.62,-727.19C702.73,-716.27 241.49,-668.25 91.97,-652.68"/>
+<polygon fill="black" stroke="black" points="92.33,-649.2 82.02,-651.65 91.61,-656.16 92.33,-649.2"/>
+</g>
+<!-- INT_TOP -->
+<g id="node5" class="node">
+<title>INT_TOP</title>
+<ellipse fill="lightblue" stroke="black" cx="404" cy="-646.79" rx="33.95" ry="18"/>
+<text text-anchor="start" x="387.12" y="-642.74" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text>
+<text text-anchor="start" x="402.88" y="-642.74" font-family="Times New Roman,serif" font-size="14.00">:int</text>
+</g>
+<!-- TOP&#45;&gt;INT_TOP -->
+<g id="edge4" class="edge">
+<title>TOP&#45;&gt;INT_TOP</title>
+<path fill="none" stroke="black" d="M808.21,-725.42C742.28,-712.76 536.86,-673.31 446.91,-656.03"/>
+<polygon fill="black" stroke="black" points="447.74,-652.63 437.26,-654.18 446.42,-659.5 447.74,-652.63"/>
+</g>
+<!-- FLT_TOP -->
+<g id="node14" class="node">
+<title>FLT_TOP</title>
+<ellipse fill="aqua" stroke="black" cx="636" cy="-646.79" rx="32.41" ry="18"/>
+<text text-anchor="start" x="620.25" y="-642.74" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text>
+<text text-anchor="start" x="636" y="-642.74" font-family="Times New Roman,serif" font-size="14.00">:flt</text>
+</g>
+<!-- TOP&#45;&gt;FLT_TOP -->
+<g id="edge18" class="edge">
+<title>TOP&#45;&gt;FLT_TOP</title>
+<path fill="none" stroke="black" d="M809.79,-721.29C777.65,-707.7 712.5,-680.14 671.73,-662.91"/>
+<polygon fill="black" stroke="black" points="673.15,-659.7 662.58,-659.03 670.42,-666.15 673.15,-659.7"/>
+</g>
+<!-- PTR -->
+<g id="node22" class="node">
+<title>PTR</title>
+<polygon fill="none" stroke="none" points="856,-673.29 802,-673.29 802,-620.29 856,-620.29 856,-673.29"/>
+<polygon fill="green" stroke="none" points="811,-646.79 811,-669.29 847,-669.29 847,-646.79 811,-646.79"/>
+<polygon fill="none" stroke="black" points="811,-646.79 811,-669.29 847,-669.29 847,-646.79 811,-646.79"/>
+<text text-anchor="start" x="818.12" y="-652.99" font-family="Times New Roman,serif" font-size="14.00" fill="white">*ptr</text>
+<polygon fill="lightgreen" stroke="none" points="811,-624.29 811,-646.79 847,-646.79 847,-624.29 811,-624.29"/>
+<polygon fill="none" stroke="black" points="811,-624.29 811,-646.79 847,-646.79 847,-624.29 811,-624.29"/>
+<text text-anchor="start" x="814" y="-630.49" font-family="Times New Roman,serif" font-size="14.00">struct</text>
+</g>
+<!-- TOP&#45;&gt;PTR -->
+<g id="edge33" class="edge">
+<title>TOP&#45;&gt;PTR</title>
+<path fill="none" stroke="black" d="M829,-708.82C829,-701.44 829,-692.87 829,-684.54"/>
+<polygon fill="black" stroke="black" points="832.5,-684.57 829,-674.57 825.5,-684.57 832.5,-684.57"/>
+</g>
+<!-- STRUCT_TOP -->
+<g id="node24" class="node">
+<title>STRUCT_TOP</title>
+<ellipse fill="lightgreen" stroke="black" cx="997" cy="-646.79" rx="44.7" ry="18"/>
+<text text-anchor="start" x="972.25" y="-642.74" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text>
+<text text-anchor="start" x="988" y="-642.74" font-family="Times New Roman,serif" font-size="14.00">:struct</text>
+</g>
+<!-- TOP&#45;&gt;STRUCT_TOP -->
+<g id="edge36" class="edge">
+<title>TOP&#45;&gt;STRUCT_TOP</title>
+<path fill="none" stroke="black" d="M847.95,-720.21C874.78,-707.18 924.42,-683.06 959.01,-666.25"/>
+<polygon fill="black" stroke="black" points="960.39,-669.47 967.86,-661.95 957.34,-663.17 960.39,-669.47"/>
+</g>
+<!-- MEM_TOP -->
+<g id="node29" class="node">
+<title>MEM_TOP</title>
+<ellipse fill="blue" stroke="black" cx="1346" cy="-646.79" rx="43.67" ry="18"/>
+<text text-anchor="start" x="1322" y="-642.74" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00" fill="white">⊤</text>
+<text text-anchor="start" x="1337.75" y="-642.74" font-family="Times New Roman,serif" font-size="14.00" fill="white">:mem</text>
+</g>
+<!-- TOP&#45;&gt;MEM_TOP -->
+<g id="edge46" class="edge">
+<title>TOP&#45;&gt;MEM_TOP</title>
+<path fill="none" stroke="black" d="M849.91,-726.12C925.08,-714.25 1183.05,-673.52 1294.28,-655.96"/>
+<polygon fill="black" stroke="black" points="1294.7,-659.44 1304.03,-654.42 1293.61,-652.52 1294.7,-659.44"/>
+</g>
+<!-- TUPLE_TOP -->
+<g id="node34" class="node">
+<title>TUPLE_TOP</title>
+<ellipse fill="pink" stroke="black" cx="1619" cy="-646.79" rx="42.65" ry="18"/>
+<text text-anchor="start" x="1595.75" y="-642.74" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text>
+<text text-anchor="start" x="1611.5" y="-642.74" font-family="Times New Roman,serif" font-size="14.00">:tuple</text>
+</g>
+<!-- TOP&#45;&gt;TUPLE_TOP -->
+<g id="edge56" class="edge">
+<title>TOP&#45;&gt;TUPLE_TOP</title>
+<path fill="none" stroke="black" d="M850.13,-727.23C953.9,-716.51 1410.83,-669.3 1566.7,-653.2"/>
+<polygon fill="black" stroke="black" points="1566.73,-656.71 1576.32,-652.2 1566.01,-649.75 1566.73,-656.71"/>
+</g>
+<!-- BOT -->
+<g id="node2" class="node">
+<title>BOT</title>
+<ellipse fill="black" stroke="black" cx="829" cy="-21.12" rx="21.12" ry="21.12"/>
+<text text-anchor="start" x="821.12" y="-16.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00" fill="white">⊥</text>
+</g>
+<!-- CTRL -->
+<g id="node4" class="node">
+<title>CTRL</title>
+<ellipse fill="yellow" stroke="black" cx="44" cy="-104.75" rx="36.51" ry="18"/>
+<text text-anchor="start" x="25.25" y="-100.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text>
+<text text-anchor="start" x="41" y="-100.7" font-family="Times New Roman,serif" font-size="14.00">:ctrl</text>
+</g>
+<!-- XCTRL&#45;&gt;CTRL -->
+<g id="edge2" class="edge">
+<title>XCTRL&#45;&gt;CTRL</title>
+<path fill="none" stroke="black" d="M44.97,-628.45C44.82,-548.91 44.24,-233.44 44.05,-134.55"/>
+<polygon fill="black" stroke="black" points="47.56,-134.6 44.04,-124.6 40.56,-134.61 47.56,-134.6"/>
+</g>
+<!-- CTRL&#45;&gt;BOT -->
+<g id="edge3" class="edge">
+<title>CTRL&#45;&gt;BOT</title>
+<path fill="none" stroke="black" d="M79.77,-100.03C211.83,-86.3 670.83,-38.57 796.8,-25.47"/>
+<polygon fill="black" stroke="black" points="796.84,-28.99 806.43,-24.47 796.12,-22.02 796.84,-28.99"/>
+</g>
+<!-- INT_HI -->
+<g id="node7" class="node">
+<title>INT_HI</title>
+<ellipse fill="lightblue" stroke="black" cx="203" cy="-566.29" rx="52.89" ry="18"/>
+<text text-anchor="middle" x="203" y="-561.24" font-family="Times New Roman,serif" font-size="14.00">max &lt; min</text>
+</g>
+<!-- INT_TOP&#45;&gt;INT_HI -->
+<g id="edge5" class="edge">
+<title>INT_TOP&#45;&gt;INT_HI</title>
+<path fill="none" stroke="black" d="M377.31,-635.37C344.15,-622.42 287.09,-600.13 247.33,-584.6"/>
+<polygon fill="black" stroke="black" points="248.85,-581.44 238.26,-581.06 246.31,-587.96 248.85,-581.44"/>
+</g>
+<!-- INT_BOT -->
+<g id="node6" class="node">
+<title>INT_BOT</title>
+<ellipse fill="lightblue" stroke="black" cx="404" cy="-104.75" rx="33.95" ry="18"/>
+<text text-anchor="start" x="387.12" y="-100.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text>
+<text text-anchor="start" x="402.88" y="-100.7" font-family="Times New Roman,serif" font-size="14.00">:int</text>
+</g>
+<!-- INT_BOT&#45;&gt;BOT -->
+<g id="edge15" class="edge">
+<title>INT_BOT&#45;&gt;BOT</title>
+<path fill="none" stroke="black" d="M435.6,-97.68C514.28,-82.57 718.3,-43.39 797.2,-28.23"/>
+<polygon fill="black" stroke="black" points="797.68,-31.7 806.84,-26.38 796.36,-24.83 797.68,-31.7"/>
+</g>
+<!-- INT_XBOOL -->
+<g id="node8" class="node">
+<title>INT_XBOOL</title>
+<ellipse fill="lightblue" stroke="black" cx="97" cy="-483.97" rx="27.81" ry="18"/>
+<text text-anchor="middle" x="97" y="-478.92" font-family="Times New Roman,serif" font-size="14.00">1...0</text>
+</g>
+<!-- INT_HI&#45;&gt;INT_XBOOL -->
+<g id="edge6" class="edge">
+<title>INT_HI&#45;&gt;INT_XBOOL</title>
+<path fill="none" stroke="black" d="M182.06,-549.42C165.21,-536.65 141.43,-518.64 123.29,-504.9"/>
+<polygon fill="black" stroke="black" points="125.68,-502.32 115.6,-499.07 121.46,-507.89 125.68,-502.32"/>
+</g>
+<!-- INT_CON -->
+<g id="node9" class="node">
+<title>INT_CON</title>
+<ellipse fill="lightblue" stroke="black" cx="203" cy="-370.65" rx="45.21" ry="18"/>
+<text text-anchor="middle" x="203" y="-365.6" font-family="Times New Roman,serif" font-size="14.00">constants</text>
+</g>
+<!-- INT_HI&#45;&gt;INT_CON -->
+<g id="edge9" class="edge">
+<title>INT_HI&#45;&gt;INT_CON</title>
+<path fill="none" stroke="black" d="M203,-547.89C203,-514.02 203,-441.56 203,-400.55"/>
+<polygon fill="black" stroke="black" points="206.5,-400.66 203,-390.66 199.5,-400.66 206.5,-400.66"/>
+</g>
+<!-- INT_CON0 -->
+<g id="node10" class="node">
+<title>INT_CON0</title>
+<ellipse fill="lightblue" stroke="black" cx="18" cy="-370.65" rx="18" ry="18"/>
+<text text-anchor="middle" x="18" y="-365.6" font-family="Times New Roman,serif" font-size="14.00">0</text>
+</g>
+<!-- INT_XBOOL&#45;&gt;INT_CON0 -->
+<g id="edge7" class="edge">
+<title>INT_XBOOL&#45;&gt;INT_CON0</title>
+<path fill="none" stroke="black" d="M85.68,-467.02C72.29,-448.15 49.88,-416.57 34.54,-394.96"/>
+<polygon fill="black" stroke="black" points="37.56,-393.17 28.92,-387.04 31.86,-397.22 37.56,-393.17"/>
+</g>
+<!-- INT_CON1 -->
+<g id="node11" class="node">
+<title>INT_CON1</title>
+<ellipse fill="lightblue" stroke="black" cx="97" cy="-370.65" rx="18" ry="18"/>
+<text text-anchor="middle" x="97" y="-365.6" font-family="Times New Roman,serif" font-size="14.00">1</text>
+</g>
+<!-- INT_XBOOL&#45;&gt;INT_CON1 -->
+<g id="edge8" class="edge">
+<title>INT_XBOOL&#45;&gt;INT_CON1</title>
+<path fill="none" stroke="black" d="M97,-465.58C97,-448.1 97,-420.85 97,-400.2"/>
+<polygon fill="black" stroke="black" points="100.5,-400.44 97,-390.44 93.5,-400.44 100.5,-400.44"/>
+</g>
+<!-- INT_LO -->
+<g id="node13" class="node">
+<title>INT_LO</title>
+<ellipse fill="lightblue" stroke="black" cx="203" cy="-185.25" rx="52.89" ry="18"/>
+<text text-anchor="middle" x="203" y="-180.2" font-family="Times New Roman,serif" font-size="14.00">max &gt; min</text>
+</g>
+<!-- INT_CON&#45;&gt;INT_LO -->
+<g id="edge13" class="edge">
+<title>INT_CON&#45;&gt;INT_LO</title>
+<path fill="none" stroke="black" d="M203,-352.2C203,-320.06 203,-253.57 203,-214.9"/>
+<polygon fill="black" stroke="black" points="206.5,-215.14 203,-205.14 199.5,-215.14 206.5,-215.14"/>
+</g>
+<!-- INT_CON0&#45;&gt;INT_CON1 -->
+<!-- INT_BOOL -->
+<g id="node12" class="node">
+<title>INT_BOOL</title>
+<ellipse fill="lightblue" stroke="black" cx="97" cy="-262.45" rx="27.81" ry="18"/>
+<text text-anchor="middle" x="97" y="-257.4" font-family="Times New Roman,serif" font-size="14.00">0...1</text>
+</g>
+<!-- INT_CON0&#45;&gt;INT_BOOL -->
+<g id="edge10" class="edge">
+<title>INT_CON0&#45;&gt;INT_BOOL</title>
+<path fill="none" stroke="black" d="M28.33,-355.77C41.09,-338.61 63.05,-309.09 78.7,-288.06"/>
+<polygon fill="black" stroke="black" points="81.32,-290.39 84.48,-280.28 75.71,-286.21 81.32,-290.39"/>
+</g>
+<!-- INT_CON1&#45;&gt;INT_CON -->
+<!-- INT_CON1&#45;&gt;INT_BOOL -->
+<g id="edge11" class="edge">
+<title>INT_CON1&#45;&gt;INT_BOOL</title>
+<path fill="none" stroke="black" d="M97,-352.59C97,-336.35 97,-311.6 97,-292.3"/>
+<polygon fill="black" stroke="black" points="100.5,-292.34 97,-282.34 93.5,-292.34 100.5,-292.34"/>
+</g>
+<!-- INT_BOOL&#45;&gt;INT_LO -->
+<g id="edge12" class="edge">
+<title>INT_BOOL&#45;&gt;INT_LO</title>
+<path fill="none" stroke="black" d="M114.98,-248.69C130.47,-237.7 153.19,-221.59 171.67,-208.48"/>
+<polygon fill="black" stroke="black" points="173.51,-211.46 179.65,-202.82 169.46,-205.75 173.51,-211.46"/>
+</g>
+<!-- INT_LO&#45;&gt;INT_BOT -->
+<g id="edge14" class="edge">
+<title>INT_LO&#45;&gt;INT_BOT</title>
+<path fill="none" stroke="black" d="M236.64,-171.11C272.65,-157.05 329.61,-134.8 366.9,-120.24"/>
+<polygon fill="black" stroke="black" points="367.88,-123.61 375.92,-116.72 365.33,-117.09 367.88,-123.61"/>
+</g>
+<!-- FLT_CON64 -->
+<g id="node16" class="node">
+<title>FLT_CON64</title>
+<ellipse fill="aqua" stroke="black" cx="709" cy="-370.65" rx="55.33" ry="40.66"/>
+<text text-anchor="middle" x="709" y="-382.1" font-family="Times New Roman,serif" font-size="14.00">64b consts</text>
+<text text-anchor="middle" x="709" y="-365.6" font-family="Times New Roman,serif" font-size="14.00">[excludes</text>
+<text text-anchor="middle" x="709" y="-349.1" font-family="Times New Roman,serif" font-size="14.00">32b consts]</text>
+</g>
+<!-- FLT_TOP&#45;&gt;FLT_CON64 -->
+<g id="edge19" class="edge">
+<title>FLT_TOP&#45;&gt;FLT_CON64</title>
+<path fill="none" stroke="black" d="M640.79,-628.67C651.74,-587.25 678.94,-484.36 695.5,-421.74"/>
+<polygon fill="black" stroke="black" points="698.8,-422.94 697.97,-412.38 692.03,-421.15 698.8,-422.94"/>
+</g>
+<!-- FLT_CONPI -->
+<g id="node18" class="node">
+<title>FLT_CONPI</title>
+<ellipse fill="aqua" stroke="black" cx="562" cy="-370.65" rx="48.79" ry="18"/>
+<text text-anchor="middle" x="562" y="-365.6" font-family="Times New Roman,serif" font-size="14.00">3.14159...</text>
+</g>
+<!-- FLT_TOP&#45;&gt;FLT_CONPI -->
+<g id="edge20" class="edge">
+<title>FLT_TOP&#45;&gt;FLT_CONPI</title>
+<path fill="none" stroke="black" d="M631.14,-628.67C618.63,-581.96 585.17,-457.11 569.85,-399.95"/>
+<polygon fill="black" stroke="black" points="573.23,-399.05 567.27,-390.3 566.47,-400.86 573.23,-399.05"/>
+</g>
+<!-- FLT_X32 -->
+<g id="node19" class="node">
+<title>FLT_X32</title>
+<ellipse fill="aqua" stroke="black" cx="420" cy="-483.97" rx="28.32" ry="28.32"/>
+<text text-anchor="middle" x="420" y="-478.92" font-family="Times New Roman,serif" font-size="14.00">~f32</text>
+</g>
+<!-- FLT_TOP&#45;&gt;FLT_X32 -->
+<g id="edge23" class="edge">
+<title>FLT_TOP&#45;&gt;FLT_X32</title>
+<path fill="none" stroke="black" d="M616.45,-632.06C579.12,-603.92 497.39,-542.31 451.99,-508.09"/>
+<polygon fill="black" stroke="black" points="454.19,-505.36 444.09,-502.13 449.97,-510.95 454.19,-505.36"/>
+</g>
+<!-- FLT_BOT -->
+<g id="node15" class="node">
+<title>FLT_BOT</title>
+<ellipse fill="aqua" stroke="black" cx="636" cy="-104.75" rx="32.41" ry="18"/>
+<text text-anchor="start" x="620.25" y="-100.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text>
+<text text-anchor="start" x="636" y="-100.7" font-family="Times New Roman,serif" font-size="14.00">:flt</text>
+</g>
+<!-- FLT_BOT&#45;&gt;BOT -->
+<g id="edge29" class="edge">
+<title>FLT_BOT&#45;&gt;BOT</title>
+<path fill="none" stroke="black" d="M661.23,-93.08C696.76,-78.05 761.4,-50.72 799.23,-34.72"/>
+<polygon fill="black" stroke="black" points="800.35,-38.04 808.2,-30.92 797.63,-31.59 800.35,-38.04"/>
+</g>
+<!-- FLT_CON64&#45;&gt;FLT_BOT -->
+<g id="edge21" class="edge">
+<title>FLT_CON64&#45;&gt;FLT_BOT</title>
+<path fill="none" stroke="black" d="M697.99,-330.56C683.16,-276.52 657.1,-181.62 644,-133.89"/>
+<polygon fill="black" stroke="black" points="647.39,-133 641.36,-124.29 640.64,-134.86 647.39,-133"/>
+</g>
+<!-- FLT_CON32 -->
+<g id="node17" class="node">
+<title>FLT_CON32</title>
+<ellipse fill="aqua" stroke="black" cx="420" cy="-370.65" rx="50.33" ry="18"/>
+<text text-anchor="middle" x="420" y="-365.6" font-family="Times New Roman,serif" font-size="14.00">32b consts</text>
+</g>
+<!-- FLT_CON32&#45;&gt;FLT_CONPI -->
+<!-- FLT_32 -->
+<g id="node21" class="node">
+<title>FLT_32</title>
+<ellipse fill="aqua" stroke="black" cx="420" cy="-262.45" rx="23.2" ry="23.2"/>
+<text text-anchor="middle" x="420" y="-257.4" font-family="Times New Roman,serif" font-size="14.00">f32</text>
+</g>
+<!-- FLT_CON32&#45;&gt;FLT_32 -->
+<g id="edge27" class="edge">
+<title>FLT_CON32&#45;&gt;FLT_32</title>
+<path fill="none" stroke="black" d="M420,-352.59C420,-337.77 420,-315.87 420,-297.49"/>
+<polygon fill="black" stroke="black" points="423.5,-297.54 420,-287.54 416.5,-297.54 423.5,-297.54"/>
+</g>
+<!-- FLT_CONPI&#45;&gt;FLT_BOT -->
+<g id="edge22" class="edge">
+<title>FLT_CONPI&#45;&gt;FLT_BOT</title>
+<path fill="none" stroke="black" d="M567.09,-352.38C579.71,-307.01 612.57,-188.95 627.9,-133.86"/>
+<polygon fill="black" stroke="black" points="631.26,-134.83 630.57,-124.26 624.52,-132.95 631.26,-134.83"/>
+</g>
+<!-- FLT_CONPI&#45;&gt;FLT_CON64 -->
+<!-- FLT_X32&#45;&gt;FLT_CON32 -->
+<g id="edge25" class="edge">
+<title>FLT_X32&#45;&gt;FLT_CON32</title>
+<path fill="none" stroke="black" d="M420,-455.17C420,-438.48 420,-417.3 420,-400.44"/>
+<polygon fill="black" stroke="black" points="423.5,-400.57 420,-390.57 416.5,-400.57 423.5,-400.57"/>
+</g>
+<!-- FLT_CON0 -->
+<g id="node20" class="node">
+<title>FLT_CON0</title>
+<ellipse fill="aqua" stroke="black" cx="309" cy="-370.65" rx="18.08" ry="18.08"/>
+<text text-anchor="middle" x="309" y="-365.6" font-family="Times New Roman,serif" font-size="14.00">0.</text>
+</g>
+<!-- FLT_X32&#45;&gt;FLT_CON0 -->
+<g id="edge24" class="edge">
+<title>FLT_X32&#45;&gt;FLT_CON0</title>
+<path fill="none" stroke="black" d="M400.41,-463.33C380.48,-443.34 349.72,-412.49 329.47,-392.18"/>
+<polygon fill="black" stroke="black" points="332.11,-389.87 322.57,-385.26 327.15,-394.82 332.11,-389.87"/>
+</g>
+<!-- FLT_CON0&#45;&gt;FLT_CON32 -->
+<!-- FLT_CON0&#45;&gt;FLT_32 -->
+<g id="edge26" class="edge">
+<title>FLT_CON0&#45;&gt;FLT_32</title>
+<path fill="none" stroke="black" d="M321.73,-357.47C339.61,-340.37 372.5,-308.9 395.28,-287.1"/>
+<polygon fill="black" stroke="black" points="397.56,-289.76 402.37,-280.32 392.72,-284.71 397.56,-289.76"/>
+</g>
+<!-- FLT_32&#45;&gt;FLT_BOT -->
+<g id="edge28" class="edge">
+<title>FLT_32&#45;&gt;FLT_BOT</title>
+<path fill="none" stroke="black" d="M438.79,-248.73C476.56,-221.15 561.91,-158.84 606.94,-125.97"/>
+<polygon fill="black" stroke="black" points="608.93,-128.85 614.94,-120.12 604.8,-123.19 608.93,-128.85"/>
+</g>
+<!-- PTR0 -->
+<g id="node23" class="node">
+<title>PTR0</title>
+<polygon fill="none" stroke="none" points="856,-131.25 802,-131.25 802,-78.25 856,-78.25 856,-131.25"/>
+<polygon fill="green" stroke="none" points="811,-104.75 811,-127.25 847,-127.25 847,-104.75 811,-104.75"/>
+<polygon fill="none" stroke="black" points="811,-104.75 811,-127.25 847,-127.25 847,-104.75 811,-104.75"/>
+<text text-anchor="start" x="815.12" y="-110.95" font-family="Times New Roman,serif" font-size="14.00" fill="white">*ptr?</text>
+<polygon fill="lightgreen" stroke="none" points="811,-82.25 811,-104.75 847,-104.75 847,-82.25 811,-82.25"/>
+<polygon fill="none" stroke="black" points="811,-82.25 811,-104.75 847,-104.75 847,-82.25 811,-82.25"/>
+<text text-anchor="start" x="814" y="-88.45" font-family="Times New Roman,serif" font-size="14.00">struct</text>
+</g>
+<!-- PTR&#45;&gt;PTR0 -->
+<g id="edge34" class="edge">
+<title>PTR&#45;&gt;PTR0</title>
+<path fill="none" stroke="black" d="M829,-620.65C829,-532.47 829,-245.72 829,-142.34"/>
+<polygon fill="black" stroke="black" points="832.5,-142.46 829,-132.46 825.5,-142.46 832.5,-142.46"/>
+</g>
+<!-- PTR0&#45;&gt;BOT -->
+<g id="edge35" class="edge">
+<title>PTR0&#45;&gt;BOT</title>
+<path fill="none" stroke="black" d="M829,-78.37C829,-70.63 829,-62.03 829,-53.93"/>
+<polygon fill="black" stroke="black" points="832.5,-54.09 829,-44.09 825.5,-54.09 832.5,-54.09"/>
+</g>
+<!-- STRUCT_S1 -->
+<g id="node26" class="node">
+<title>STRUCT_S1</title>
+<polygon fill="none" stroke="none" points="979.88,-388.65 894.12,-388.65 894.12,-352.65 979.88,-352.65 979.88,-388.65"/>
+<polygon fill="lightgreen" stroke="none" points="902.12,-359.4 902.12,-381.9 932.88,-381.9 932.88,-359.4 902.12,-359.4"/>
+<polygon fill="none" stroke="black" points="902.12,-359.4 902.12,-381.9 932.88,-381.9 932.88,-359.4 902.12,-359.4"/>
+<text text-anchor="start" x="905.12" y="-365.6" font-family="Times New Roman,serif" font-size="14.00">field</text>
+<defs>
+<linearGradient id="l_0" gradientUnits="userSpaceOnUse" x1="938.59" y1="-378.61" x2="966.16" y2="-362.7" >
+<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/>
+<stop offset="1" style="stop-color:green;stop-opacity:1.;"/>
+</linearGradient>
+</defs>
+<polygon fill="url(#l_0)" stroke="none" points="932.88,-359.4 932.88,-381.9 971.88,-381.9 971.88,-359.4 932.88,-359.4"/>
+<polygon fill="none" stroke="black" points="932.88,-359.4 932.88,-381.9 971.88,-381.9 971.88,-359.4 932.88,-359.4"/>
+<text text-anchor="start" x="935.88" y="-365.6" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text>
+</g>
+<!-- STRUCT_TOP&#45;&gt;STRUCT_S1 -->
+<g id="edge37" class="edge">
+<title>STRUCT_TOP&#45;&gt;STRUCT_S1</title>
+<path fill="none" stroke="black" d="M993.06,-628.67C982.89,-581.85 955.66,-456.51 943.28,-399.54"/>
+<polygon fill="black" stroke="black" points="946.74,-398.99 941.19,-389.96 939.9,-400.47 946.74,-398.99"/>
+</g>
+<!-- STRUCT_S2 -->
+<g id="node27" class="node">
+<title>STRUCT_S2</title>
+<polygon fill="none" stroke="none" points="1108.88,-397.15 1023.12,-397.15 1023.12,-344.15 1108.88,-344.15 1108.88,-397.15"/>
+<polygon fill="lightgreen" stroke="none" points="1031.12,-370.65 1031.12,-393.15 1061.88,-393.15 1061.88,-370.65 1031.12,-370.65"/>
+<polygon fill="none" stroke="black" points="1031.12,-370.65 1031.12,-393.15 1061.88,-393.15 1061.88,-370.65 1031.12,-370.65"/>
+<text text-anchor="start" x="1034.12" y="-376.85" font-family="Times New Roman,serif" font-size="14.00">field</text>
+<defs>
+<linearGradient id="l_1" gradientUnits="userSpaceOnUse" x1="1067.59" y1="-389.86" x2="1095.16" y2="-373.95" >
+<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/>
+<stop offset="1" style="stop-color:green;stop-opacity:1.;"/>
+</linearGradient>
+</defs>
+<polygon fill="url(#l_1)" stroke="none" points="1061.88,-370.65 1061.88,-393.15 1100.88,-393.15 1100.88,-370.65 1061.88,-370.65"/>
+<polygon fill="none" stroke="black" points="1061.88,-370.65 1061.88,-393.15 1100.88,-393.15 1100.88,-370.65 1061.88,-370.65"/>
+<text text-anchor="start" x="1064.88" y="-376.85" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text>
+<polygon fill="lightgreen" stroke="none" points="1031.12,-348.15 1031.12,-370.65 1061.88,-370.65 1061.88,-348.15 1031.12,-348.15"/>
+<polygon fill="none" stroke="black" points="1031.12,-348.15 1031.12,-370.65 1061.88,-370.65 1061.88,-348.15 1031.12,-348.15"/>
+<text text-anchor="start" x="1034.12" y="-354.35" font-family="Times New Roman,serif" font-size="14.00">field</text>
+<defs>
+<linearGradient id="l_2" gradientUnits="userSpaceOnUse" x1="1067.59" y1="-367.36" x2="1095.16" y2="-351.45" >
+<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/>
+<stop offset="1" style="stop-color:green;stop-opacity:1.;"/>
+</linearGradient>
+</defs>
+<polygon fill="url(#l_2)" stroke="none" points="1061.88,-348.15 1061.88,-370.65 1100.88,-370.65 1100.88,-348.15 1061.88,-348.15"/>
+<polygon fill="none" stroke="black" points="1061.88,-348.15 1061.88,-370.65 1100.88,-370.65 1100.88,-348.15 1061.88,-348.15"/>
+<text text-anchor="start" x="1064.88" y="-354.35" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text>
+</g>
+<!-- STRUCT_TOP&#45;&gt;STRUCT_S2 -->
+<g id="edge38" class="edge">
+<title>STRUCT_TOP&#45;&gt;STRUCT_S2</title>
+<path fill="none" stroke="black" d="M1001.53,-628.67C1012.68,-584.04 1041.67,-468.04 1056.68,-407.95"/>
+<polygon fill="black" stroke="black" points="1060,-409.09 1059.03,-398.54 1053.21,-407.39 1060,-409.09"/>
+</g>
+<!-- STRUCT_SN -->
+<g id="node28" class="node">
+<title>STRUCT_SN</title>
+<polygon fill="none" stroke="none" points="1237.88,-408.4 1152.12,-408.4 1152.12,-332.9 1237.88,-332.9 1237.88,-408.4"/>
+<polygon fill="lightgreen" stroke="none" points="1160.12,-381.9 1160.12,-404.4 1190.88,-404.4 1190.88,-381.9 1160.12,-381.9"/>
+<polygon fill="none" stroke="black" points="1160.12,-381.9 1160.12,-404.4 1190.88,-404.4 1190.88,-381.9 1160.12,-381.9"/>
+<text text-anchor="start" x="1163.12" y="-388.1" font-family="Times New Roman,serif" font-size="14.00">field</text>
+<defs>
+<linearGradient id="l_3" gradientUnits="userSpaceOnUse" x1="1196.59" y1="-401.11" x2="1224.16" y2="-385.2" >
+<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/>
+<stop offset="1" style="stop-color:green;stop-opacity:1.;"/>
+</linearGradient>
+</defs>
+<polygon fill="url(#l_3)" stroke="none" points="1190.88,-381.9 1190.88,-404.4 1229.88,-404.4 1229.88,-381.9 1190.88,-381.9"/>
+<polygon fill="none" stroke="black" points="1190.88,-381.9 1190.88,-404.4 1229.88,-404.4 1229.88,-381.9 1190.88,-381.9"/>
+<text text-anchor="start" x="1193.88" y="-388.1" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text>
+<polygon fill="lightgreen" stroke="none" points="1160.12,-359.4 1160.12,-381.9 1190.88,-381.9 1190.88,-359.4 1160.12,-359.4"/>
+<polygon fill="none" stroke="black" points="1160.12,-359.4 1160.12,-381.9 1190.88,-381.9 1190.88,-359.4 1160.12,-359.4"/>
+<text text-anchor="start" x="1166.12" y="-365.6" font-family="Times New Roman,serif" font-size="14.00">... &#160;</text>
+<defs>
+<linearGradient id="l_4" gradientUnits="userSpaceOnUse" x1="1196.59" y1="-378.61" x2="1224.16" y2="-362.7" >
+<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/>
+<stop offset="1" style="stop-color:green;stop-opacity:1.;"/>
+</linearGradient>
+</defs>
+<polygon fill="url(#l_4)" stroke="none" points="1190.88,-359.4 1190.88,-381.9 1229.88,-381.9 1229.88,-359.4 1190.88,-359.4"/>
+<polygon fill="none" stroke="black" points="1190.88,-359.4 1190.88,-381.9 1229.88,-381.9 1229.88,-359.4 1190.88,-359.4"/>
+<text text-anchor="start" x="1193.88" y="-365.6" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text>
+<polygon fill="lightgreen" stroke="none" points="1160.12,-336.9 1160.12,-359.4 1190.88,-359.4 1190.88,-336.9 1160.12,-336.9"/>
+<polygon fill="none" stroke="black" points="1160.12,-336.9 1160.12,-359.4 1190.88,-359.4 1190.88,-336.9 1160.12,-336.9"/>
+<text text-anchor="start" x="1163.12" y="-343.1" font-family="Times New Roman,serif" font-size="14.00">field</text>
+<defs>
+<linearGradient id="l_5" gradientUnits="userSpaceOnUse" x1="1196.59" y1="-356.11" x2="1224.16" y2="-340.2" >
+<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/>
+<stop offset="1" style="stop-color:green;stop-opacity:1.;"/>
+</linearGradient>
+</defs>
+<polygon fill="url(#l_5)" stroke="none" points="1190.88,-336.9 1190.88,-359.4 1229.88,-359.4 1229.88,-336.9 1190.88,-336.9"/>
+<polygon fill="none" stroke="black" points="1190.88,-336.9 1190.88,-359.4 1229.88,-359.4 1229.88,-336.9 1190.88,-336.9"/>
+<text text-anchor="start" x="1193.88" y="-343.1" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text>
+</g>
+<!-- STRUCT_TOP&#45;&gt;STRUCT_SN -->
+<g id="edge39" class="edge">
+<title>STRUCT_TOP&#45;&gt;STRUCT_SN</title>
+<path fill="none" stroke="black" d="M1009.69,-629.1C1039.89,-586.98 1116.85,-479.64 1161.52,-417.35"/>
+<polygon fill="black" stroke="black" points="1164.27,-419.52 1167.25,-409.35 1158.58,-415.44 1164.27,-419.52"/>
+</g>
+<!-- STRUCT_BOT -->
+<g id="node25" class="node">
+<title>STRUCT_BOT</title>
+<ellipse fill="lightgreen" stroke="black" cx="995" cy="-104.75" rx="44.7" ry="18"/>
+<text text-anchor="start" x="970.25" y="-100.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text>
+<text text-anchor="start" x="986" y="-100.7" font-family="Times New Roman,serif" font-size="14.00">:struct</text>
+</g>
+<!-- STRUCT_BOT&#45;&gt;BOT -->
+<g id="edge43" class="edge">
+<title>STRUCT_BOT&#45;&gt;BOT</title>
+<path fill="none" stroke="black" d="M967.59,-90.27C937.27,-75.36 888.65,-51.46 857.79,-36.28"/>
+<polygon fill="black" stroke="black" points="859.56,-33.25 849.04,-31.98 856.47,-39.53 859.56,-33.25"/>
+</g>
+<!-- STRUCT_S1&#45;&gt;STRUCT_BOT -->
+<g id="edge40" class="edge">
+<title>STRUCT_S1&#45;&gt;STRUCT_BOT</title>
+<path fill="none" stroke="black" d="M940.9,-352.79C950.72,-307.77 976.56,-189.3 988.62,-133.98"/>
+<polygon fill="black" stroke="black" points="992.01,-134.88 990.72,-124.36 985.17,-133.38 992.01,-134.88"/>
+</g>
+<!-- STRUCT_S1&#45;&gt;STRUCT_S2 -->
+<!-- STRUCT_S2&#45;&gt;STRUCT_BOT -->
+<g id="edge41" class="edge">
+<title>STRUCT_S2&#45;&gt;STRUCT_BOT</title>
+<path fill="none" stroke="black" d="M1058.93,-344.18C1045.59,-294.22 1016.79,-186.34 1002.86,-134.18"/>
+<polygon fill="black" stroke="black" points="1006.24,-133.28 1000.28,-124.52 999.48,-135.08 1006.24,-133.28"/>
+</g>
+<!-- STRUCT_S2&#45;&gt;STRUCT_SN -->
+<!-- STRUCT_SN&#45;&gt;STRUCT_BOT -->
+<g id="edge42" class="edge">
+<title>STRUCT_SN&#45;&gt;STRUCT_BOT</title>
+<path fill="none" stroke="black" d="M1166.77,-333.12C1125.77,-278.61 1050.75,-178.87 1014.99,-131.32"/>
+<polygon fill="black" stroke="black" points="1017.9,-129.37 1009.09,-123.48 1012.3,-133.58 1017.9,-129.37"/>
+</g>
+<!-- MEM_ALIAS1 -->
+<g id="node31" class="node">
+<title>MEM_ALIAS1</title>
+<ellipse fill="blue" stroke="black" cx="1301" cy="-370.65" rx="20.13" ry="20.13"/>
+<text text-anchor="middle" x="1301" y="-365.6" font-family="Times New Roman,serif" font-size="14.00" fill="white">#1</text>
+</g>
+<!-- MEM_TOP&#45;&gt;MEM_ALIAS1 -->
+<g id="edge47" class="edge">
+<title>MEM_TOP&#45;&gt;MEM_ALIAS1</title>
+<path fill="none" stroke="black" d="M1343.05,-628.67C1335.53,-582.52 1315.58,-460.09 1306.11,-402.04"/>
+<polygon fill="black" stroke="black" points="1309.57,-401.48 1304.51,-392.17 1302.66,-402.6 1309.57,-401.48"/>
+</g>
+<!-- MEM_ALIASDOTS -->
+<g id="node32" class="node">
+<title>MEM_ALIASDOTS</title>
+<ellipse fill="blue" stroke="black" cx="1391" cy="-370.65" rx="27" ry="18"/>
+<text text-anchor="middle" x="1391" y="-365.6" font-family="Times New Roman,serif" font-size="14.00" fill="white">...</text>
+</g>
+<!-- MEM_TOP&#45;&gt;MEM_ALIASDOTS -->
+<g id="edge48" class="edge">
+<title>MEM_TOP&#45;&gt;MEM_ALIASDOTS</title>
+<path fill="none" stroke="black" d="M1348.95,-628.67C1356.56,-581.96 1376.91,-457.11 1386.23,-399.95"/>
+<polygon fill="black" stroke="black" points="1389.64,-400.76 1387.79,-390.33 1382.73,-399.64 1389.64,-400.76"/>
+</g>
+<!-- MEM_ALIASN -->
+<g id="node33" class="node">
+<title>MEM_ALIASN</title>
+<ellipse fill="blue" stroke="black" cx="1481" cy="-370.65" rx="20.13" ry="20.13"/>
+<text text-anchor="middle" x="1481" y="-365.6" font-family="Times New Roman,serif" font-size="14.00" fill="white">#n</text>
+</g>
+<!-- MEM_TOP&#45;&gt;MEM_ALIASN -->
+<g id="edge49" class="edge">
+<title>MEM_TOP&#45;&gt;MEM_ALIASN</title>
+<path fill="none" stroke="black" d="M1354.86,-628.67C1377.84,-581.67 1439.5,-455.54 1467.2,-398.89"/>
+<polygon fill="black" stroke="black" points="1470.2,-400.72 1471.44,-390.2 1463.91,-397.64 1470.2,-400.72"/>
+</g>
+<!-- MEM_BOT -->
+<g id="node30" class="node">
+<title>MEM_BOT</title>
+<ellipse fill="blue" stroke="black" cx="1346" cy="-104.75" rx="43.67" ry="18"/>
+<text text-anchor="start" x="1322" y="-100.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00" fill="white">⊥</text>
+<text text-anchor="start" x="1337.75" y="-100.7" font-family="Times New Roman,serif" font-size="14.00" fill="white">:mem</text>
+</g>
+<!-- MEM_BOT&#45;&gt;BOT -->
+<g id="edge53" class="edge">
+<title>MEM_BOT&#45;&gt;BOT</title>
+<path fill="none" stroke="black" d="M1305.86,-97.41C1206.64,-81.75 951.34,-41.44 861.15,-27.2"/>
+<polygon fill="black" stroke="black" points="861.94,-23.78 851.52,-25.68 860.85,-30.7 861.94,-23.78"/>
+</g>
+<!-- MEM_ALIAS1&#45;&gt;MEM_BOT -->
+<g id="edge50" class="edge">
+<title>MEM_ALIAS1&#45;&gt;MEM_BOT</title>
+<path fill="none" stroke="black" d="M1304.38,-350.67C1312.23,-304.29 1331.71,-189.17 1340.97,-134.49"/>
+<polygon fill="black" stroke="black" points="1344.41,-135.12 1342.63,-124.67 1337.51,-133.95 1344.41,-135.12"/>
+</g>
+<!-- MEM_ALIAS1&#45;&gt;MEM_ALIASDOTS -->
+<!-- MEM_ALIASDOTS&#45;&gt;MEM_BOT -->
+<g id="edge51" class="edge">
+<title>MEM_ALIASDOTS&#45;&gt;MEM_BOT</title>
+<path fill="none" stroke="black" d="M1387.91,-352.38C1380.25,-307.12 1360.35,-189.52 1350.99,-134.26"/>
+<polygon fill="black" stroke="black" points="1354.49,-133.92 1349.37,-124.65 1347.58,-135.09 1354.49,-133.92"/>
+</g>
+<!-- MEM_ALIASDOTS&#45;&gt;MEM_ALIASN -->
+<!-- MEM_ALIASN&#45;&gt;MEM_BOT -->
+<g id="edge52" class="edge">
+<title>MEM_ALIASN&#45;&gt;MEM_BOT</title>
+<path fill="none" stroke="black" d="M1471.72,-352.38C1448.54,-306.73 1388,-187.47 1360.26,-132.83"/>
+<polygon fill="black" stroke="black" points="1363.5,-131.48 1355.85,-124.15 1357.26,-134.65 1363.5,-131.48"/>
+</g>
+<!-- TUPLE1 -->
+<g id="node36" class="node">
+<title>TUPLE1</title>
+<polygon fill="none" stroke="none" points="1598,-397.15 1544,-397.15 1544,-344.15 1598,-344.15 1598,-397.15"/>
+<polygon fill="pink" stroke="none" points="1552.25,-370.65 1552.25,-393.15 1589.75,-393.15 1589.75,-370.65 1552.25,-370.65"/>
+<polygon fill="none" stroke="black" points="1552.25,-370.65 1552.25,-393.15 1589.75,-393.15 1589.75,-370.65 1552.25,-370.65"/>
+<text text-anchor="start" x="1555.25" y="-376.85" font-family="Times New Roman,serif" font-size="14.00">Tuple</text>
+<polygon fill="black" stroke="none" points="1552.25,-348.15 1552.25,-370.65 1589.75,-370.65 1589.75,-348.15 1552.25,-348.15"/>
+<polygon fill="none" stroke="black" points="1552.25,-348.15 1552.25,-370.65 1589.75,-370.65 1589.75,-348.15 1552.25,-348.15"/>
+<text text-anchor="start" x="1559.38" y="-354.35" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+</g>
+<!-- TUPLE_TOP&#45;&gt;TUPLE1 -->
+<g id="edge57" class="edge">
+<title>TUPLE_TOP&#45;&gt;TUPLE1</title>
+<path fill="none" stroke="black" d="M1615.85,-628.67C1608.11,-584.13 1588.01,-468.52 1577.55,-408.33"/>
+<polygon fill="black" stroke="black" points="1581.01,-407.81 1575.85,-398.56 1574.12,-409.01 1581.01,-407.81"/>
+</g>
+<!-- TUPLE2 -->
+<g id="node37" class="node">
+<title>TUPLE2</title>
+<polygon fill="none" stroke="none" points="1695,-408.4 1641,-408.4 1641,-332.9 1695,-332.9 1695,-408.4"/>
+<polygon fill="pink" stroke="none" points="1649.25,-381.9 1649.25,-404.4 1686.75,-404.4 1686.75,-381.9 1649.25,-381.9"/>
+<polygon fill="none" stroke="black" points="1649.25,-381.9 1649.25,-404.4 1686.75,-404.4 1686.75,-381.9 1649.25,-381.9"/>
+<text text-anchor="start" x="1652.25" y="-388.1" font-family="Times New Roman,serif" font-size="14.00">Tuple</text>
+<polygon fill="black" stroke="none" points="1649.25,-359.4 1649.25,-381.9 1686.75,-381.9 1686.75,-359.4 1649.25,-359.4"/>
+<polygon fill="none" stroke="black" points="1649.25,-359.4 1649.25,-381.9 1686.75,-381.9 1686.75,-359.4 1649.25,-359.4"/>
+<text text-anchor="start" x="1656.38" y="-365.6" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+<polygon fill="black" stroke="none" points="1649.25,-336.9 1649.25,-359.4 1686.75,-359.4 1686.75,-336.9 1649.25,-336.9"/>
+<polygon fill="none" stroke="black" points="1649.25,-336.9 1649.25,-359.4 1686.75,-359.4 1686.75,-336.9 1649.25,-336.9"/>
+<text text-anchor="start" x="1656.38" y="-343.1" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+</g>
+<!-- TUPLE_TOP&#45;&gt;TUPLE2 -->
+<g id="edge58" class="edge">
+<title>TUPLE_TOP&#45;&gt;TUPLE2</title>
+<path fill="none" stroke="black" d="M1622.22,-628.67C1629.67,-586.65 1648.35,-481.4 1659.41,-419.08"/>
+<polygon fill="black" stroke="black" points="1662.81,-419.91 1661.11,-409.46 1655.92,-418.69 1662.81,-419.91"/>
+</g>
+<!-- TUPLEN -->
+<g id="node38" class="node">
+<title>TUPLEN</title>
+<polygon fill="none" stroke="none" points="1792,-419.65 1738,-419.65 1738,-321.65 1792,-321.65 1792,-419.65"/>
+<polygon fill="pink" stroke="none" points="1746.25,-393.15 1746.25,-415.65 1783.75,-415.65 1783.75,-393.15 1746.25,-393.15"/>
+<polygon fill="none" stroke="black" points="1746.25,-393.15 1746.25,-415.65 1783.75,-415.65 1783.75,-393.15 1746.25,-393.15"/>
+<text text-anchor="start" x="1749.25" y="-399.35" font-family="Times New Roman,serif" font-size="14.00">Tuple</text>
+<polygon fill="black" stroke="none" points="1746.25,-370.65 1746.25,-393.15 1783.75,-393.15 1783.75,-370.65 1746.25,-370.65"/>
+<polygon fill="none" stroke="black" points="1746.25,-370.65 1746.25,-393.15 1783.75,-393.15 1783.75,-370.65 1746.25,-370.65"/>
+<text text-anchor="start" x="1753.38" y="-376.85" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+<polygon fill="black" stroke="none" points="1746.25,-348.15 1746.25,-370.65 1783.75,-370.65 1783.75,-348.15 1746.25,-348.15"/>
+<polygon fill="none" stroke="black" points="1746.25,-348.15 1746.25,-370.65 1783.75,-370.65 1783.75,-348.15 1746.25,-348.15"/>
+<text text-anchor="start" x="1759.38" y="-354.35" font-family="Times New Roman,serif" font-size="14.00" fill="white">...</text>
+<polygon fill="black" stroke="none" points="1746.25,-325.65 1746.25,-348.15 1783.75,-348.15 1783.75,-325.65 1746.25,-325.65"/>
+<polygon fill="none" stroke="black" points="1746.25,-325.65 1746.25,-348.15 1783.75,-348.15 1783.75,-325.65 1746.25,-325.65"/>
+<text text-anchor="start" x="1753.38" y="-331.85" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+</g>
+<!-- TUPLE_TOP&#45;&gt;TUPLEN -->
+<g id="edge59" class="edge">
+<title>TUPLE_TOP&#45;&gt;TUPLEN</title>
+<path fill="none" stroke="black" d="M1628.36,-629.1C1649.26,-589.55 1700.57,-492.51 1734.02,-429.24"/>
+<polygon fill="black" stroke="black" points="1736.95,-431.2 1738.53,-420.73 1730.76,-427.93 1736.95,-431.2"/>
+</g>
+<!-- TUPLE_BOT -->
+<g id="node35" class="node">
+<title>TUPLE_BOT</title>
+<ellipse fill="pink" stroke="black" cx="1619" cy="-104.75" rx="42.65" ry="18"/>
+<text text-anchor="start" x="1595.75" y="-100.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text>
+<text text-anchor="start" x="1611.5" y="-100.7" font-family="Times New Roman,serif" font-size="14.00">:tuple</text>
+</g>
+<!-- TUPLE_BOT&#45;&gt;BOT -->
+<g id="edge63" class="edge">
+<title>TUPLE_BOT&#45;&gt;BOT</title>
+<path fill="none" stroke="black" d="M1577.91,-99.5C1438.76,-85.13 986.93,-38.44 861.54,-25.49"/>
+<polygon fill="black" stroke="black" points="861.93,-22.01 851.62,-24.46 861.21,-28.97 861.93,-22.01"/>
+</g>
+<!-- TUPLE1&#45;&gt;TUPLE_BOT -->
+<g id="edge60" class="edge">
+<title>TUPLE1&#45;&gt;TUPLE_BOT</title>
+<path fill="none" stroke="black" d="M1575.78,-344.18C1584.8,-294.22 1604.27,-186.34 1613.69,-134.18"/>
+<polygon fill="black" stroke="black" points="1617.09,-135.01 1615.43,-124.55 1610.21,-133.77 1617.09,-135.01"/>
+</g>
+<!-- TUPLE2&#45;&gt;TUPLE_BOT -->
+<g id="edge61" class="edge">
+<title>TUPLE2&#45;&gt;TUPLE_BOT</title>
+<path fill="none" stroke="black" d="M1661.08,-333.12C1651.23,-279.67 1633.37,-182.73 1624.42,-134.16"/>
+<polygon fill="black" stroke="black" points="1627.87,-133.59 1622.62,-124.39 1620.99,-134.86 1627.87,-133.59"/>
+</g>
+<!-- TUPLEN&#45;&gt;TUPLE_BOT -->
+<g id="edge62" class="edge">
+<title>TUPLEN&#45;&gt;TUPLE_BOT</title>
+<path fill="none" stroke="black" d="M1738.22,-321.88C1707.66,-266.22 1658.74,-177.12 1634.15,-132.34"/>
+<polygon fill="black" stroke="black" points="1637.34,-130.87 1629.45,-123.79 1631.2,-134.24 1637.34,-130.87"/>
+</g>
+</g>
+</svg>
diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java
index 71bd6d02..9e4b9eb6 100644
--- a/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/src/main/java/com/seaofnodes/simple/Parser.java
@@ -52,11 +52,19 @@ public class Parser {
* List of keywords disallowed as identifiers
*/
private static final HashSet<String> KEYWORDS = new HashSet<>(){{
+ add("bool");
add("break");
+ add("byte");
add("continue");
add("else");
+ add("f32");
+ add("f64");
add("false");
add("flt");
+ add("i16");
+ add("i32");
+ add("i64");
+ add("i8");
add("if");
add("int");
add("new");
@@ -64,6 +72,10 @@ public class Parser {
add("return");
add("struct");
add("true");
+ add("u1");
+ add("u16");
+ add("u32");
+ add("u8");
add("while");
}};
@@ -84,8 +96,20 @@ public class Parser {
Node.reset();
IterPeeps.reset();
TYPES.clear();
- TYPES.put("int",TypeInteger.BOT);
- TYPES.put("flt",TypeFloat .BOT);
+ TYPES.put("bool",TypeInteger.U1 );
+ TYPES.put("byte",TypeInteger.U8 );
+ TYPES.put("f32" ,TypeFloat .B32);
+ TYPES.put("f64" ,TypeFloat .BOT);
+ TYPES.put("flt" ,TypeFloat .BOT);
+ TYPES.put("i16" ,TypeInteger.I16);
+ TYPES.put("i32" ,TypeInteger.I32);
+ TYPES.put("i64" ,TypeInteger.BOT);
+ TYPES.put("i8" ,TypeInteger.I8 );
+ TYPES.put("int" ,TypeInteger.BOT);
+ TYPES.put("u1" ,TypeInteger.U1 );
+ TYPES.put("u16" ,TypeInteger.U16);
+ TYPES.put("u32" ,TypeInteger.U32);
+ TYPES.put("u8" ,TypeInteger.U8 );
SCHEDULED = false;
_lexer = new Lexer(source);
_scope = new ScopeNode();
@@ -191,7 +215,7 @@ public class Parser {
* Only allowed in top level scope.
* Structs cannot be redefined.
*
- * @return null
+ * @return The statement following the struct
*/
private Node parseStruct() {
if (_xScopes.size() > 1) throw errorSyntax("struct declarations can only appear in top level scope");
@@ -210,7 +234,7 @@ public class Parser {
TypeStruct ts = TypeStruct.make(typeName, fields);
TYPES.put(typeName, ts);
START.addMemProj(ts, _scope); // Insert memory edges
- return null;
+ return parseStatement();
}
/**
@@ -434,6 +458,8 @@ public class Parser {
// Auto-widen int to float
if( expr._type instanceof TypeInteger && t instanceof TypeFloat )
expr = new ToFloatNode(expr).peephole();
+ // Auto-narrow wide ints to narrow ints
+ expr = zsMask(expr,t);
// Auto-deepen forward ref types
Type e = expr._type;
if( e instanceof TypeMemPtr tmp && tmp._obj._fields==null )
@@ -475,7 +501,29 @@ public class Parser {
* </pre>
* @return an expression {@link Node}, never {@code null}
*/
- private Node parseExpression() { return parseComparison(); }
+ private Node parseExpression() { return parseBitwise(); }
+
+ /**
+ * Parse an bitwise expression
+ *
+ * <pre>
+ * bitwise : compareExpr (('&' | '|' | '^') compareExpr)*
+ * </pre>
+ * @return a bitwise expression {@link Node}, never {@code null}
+ */
+ private Node parseBitwise() {
+ Node lhs = parseComparison();
+ while( true ) {
+ if( false ) ;
+ else if( match("&") ) lhs = new AndNode(lhs,null);
+ else if( match("|") ) lhs = new OrNode(lhs,null);
+ else if( match("^") ) lhs = new XorNode(lhs,null);
+ else break;
+ lhs.setDef(2,parseComparison());
+ lhs = lhs.peephole();
+ }
+ return lhs;
+ }
/**
* Parse an expression of the form:
@@ -486,7 +534,7 @@ public class Parser {
* @return an comparator expression {@link Node}, never {@code null}
*/
private Node parseComparison() {
- var lhs = parseAddition();
+ var lhs = parseShift();
while( true ) {
int idx=0; boolean negate=false;
// Test for any local nodes made, and "keep" lhs during peepholes
@@ -499,7 +547,7 @@ public class Parser {
else if( match(">" ) ) { idx=1; lhs = new BoolNode.LT(null, lhs); }
else break;
// Peepholes can fire, but lhs is already "hooked", kept alive
- lhs.setDef(idx,parseAddition());
+ lhs.setDef(idx,parseShift());
lhs = lhs.widen().peephole();
if( negate ) // Extra negate for !=
lhs = new NotNode(lhs).peephole();
@@ -511,6 +559,28 @@ public class Parser {
* Parse an additive expression
*
* <pre>
+ * shiftExpr : additiveExpr (('<<' | '>>' | '>>>') additiveExpr)*
+ * </pre>
+ * @return a shift expression {@link Node}, never {@code null}
+ */
+ private Node parseShift() {
+ Node lhs = parseAddition();
+ while( true ) {
+ if( false ) ;
+ else if( match("<<") ) lhs = new ShlNode(lhs,null);
+ else if( match(">>>")) lhs = new ShrNode(lhs,null);
+ else if( match(">>") ) lhs = new SarNode(lhs,null);
+ else break;
+ lhs.setDef(2,parseAddition());
+ lhs = lhs.widen().peephole();
+ }
+ return lhs;
+ }
+
+ /**
+ * Parse an additive expression
+ *
+ * <pre>
* additiveExpr : multiplicativeExpr (('+' | '-') multiplicativeExpr)*
* </pre>
* @return an add expression {@link Node}, never {@code null}
@@ -640,6 +710,8 @@ public class Parser {
else {
Node val = parseExpression();
Type glb = base._fields[idx]._type;
+ // Auto-truncate when storing to narrow fields
+ val = zsMask(val,glb);
memAlias(alias, new StoreNode(name, alias,glb, ctrl(), memAlias(alias), expr, val, false).peephole());
return expr; // "obj.a = expr" returns the expression while updating memory
}
@@ -649,6 +721,26 @@ public class Parser {
return parsePostfix(new LoadNode(name, alias, declaredType.glb(), memAlias(alias), expr).peephole());
}
+ // zero/sign extend. "i" is limited to either classic unsigned (min==0) or
+ // classic signed (min=minus-power-of-2); max=power-of-2-minus-1.
+ private Node zsMask(Node val, Type t ) {
+ if( !(val._type instanceof TypeInteger tval && t instanceof TypeInteger t0 && !tval.isa(t0)) ) {
+ if( !(val._type instanceof TypeFloat tval && t instanceof TypeFloat t0 && !tval.isa(t0)) )
+ return val;
+ // Float rounding
+ return new RoundF32Node(val).peephole();
+ }
+ if( t0._min==0 ) // Unsigned
+ return new AndNode(val,new ConstantNode(TypeInteger.constant(t0._max)).peephole()).peephole();
+ // Signed extension
+ int shift = Long.numberOfLeadingZeros(t0._max)-1;
+ Node shf = new ConstantNode(TypeInteger.constant(shift)).peephole();
+ if( shf._type==TypeInteger.ZERO )
+ return val;
+ return new SarNode(new ShlNode(val,shf.keep()).peephole(),shf.unkeep()).peephole();
+ }
+
+
/**
* Parse integer literal
*
diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java
index 67eacd3a..bd1a9dcd 100644
--- a/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -21,14 +21,24 @@ public class AddNode extends Node {
@Override
public Type compute() {
- if( in(1)._type instanceof TypeInteger i0 &&
- in(2)._type instanceof TypeInteger i1 ) {
- if (i0.isConstant() && i1.isConstant())
- return TypeInteger.constant(i0.value()+i1.value());
+ Type t1 = in(1)._type, t2 = in(2)._type;
+ if( t1.isHigh() || t2.isHigh() ) return TypeInteger.TOP;
+ if( t1 instanceof TypeInteger i1 &&
+ t2 instanceof TypeInteger i2 ) {
+ if (i1.isConstant() && i2.isConstant())
+ return TypeInteger.constant(i1.value()+i2.value());
+ // Fold ranges like {0-1} + {2-3} into {2-4}.
+ if( !overflow(i1._min,i2._min) &&
+ !overflow(i1._max,i2._max) )
+ return TypeInteger.make(i1._min+i2._min,i1._max+i2._max);
}
- return in(1)._type.meet(in(2)._type);
+ 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);
@@ -37,7 +47,7 @@ public class AddNode extends Node {
// Add of 0. We do not check for (0+x) because this will already
// canonicalize to (x+0)
- if( t2 instanceof TypeInteger i && i.value()==0 )
+ if( t2 instanceof TypeInteger i && i.isConstant() && i.value()==0 )
return lhs;
// Add of same to a multiply by 2
@@ -100,7 +110,7 @@ public class AddNode extends Node {
return null;
}
- // Rotation is only valid for associative ops, e.g. Add, Mul, And, Or.
+ // Rotation is only valid for associative ops, e.g. Add, Mul, And, Or, Xor.
// Do we have ((phi cons)|(x + (phi cons)) + con|(phi cons)) ?
// Push constant up through the phi: x + (phi con0+con0 con1+con1...)
static Node phiCon(Node op, boolean rotate) {
diff --git a/src/main/java/com/seaofnodes/simple/node/AndNode.java b/src/main/java/com/seaofnodes/simple/node/AndNode.java
new file mode 100644
index 00000000..350859db
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/AndNode.java
@@ -0,0 +1,66 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+import java.util.BitSet;
+
+public class AndNode extends Node {
+ public AndNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+ @Override public String label() { return "And"; }
+
+ @Override public String glabel() { return "&"; }
+
+ @Override
+ StringBuilder _print1(StringBuilder sb, BitSet visited) {
+ in(1)._print0(sb.append("("), visited);
+ in(2)._print0(sb.append("&"), visited);
+ return sb.append(")");
+ }
+
+ @Override
+ public Type compute() {
+ if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP;
+ if( in(1)._type instanceof TypeInteger i0 &&
+ in(2)._type instanceof TypeInteger i1 ) {
+ if( i0.isConstant() && i1.isConstant() )
+ return TypeInteger.constant(i0.value()&i1.value());
+ // Sharpen allowed bits if either value is narrowed
+ long mask = i0.mask() & i1.mask();
+ return mask < 0 ? TypeInteger.BOT : TypeInteger.make(0,mask);
+ }
+ return TypeInteger.BOT;
+ }
+
+ @Override
+ public Node idealize() {
+ Node lhs = in(1);
+ Node rhs = in(2);
+ Type t1 = lhs._type;
+ Type t2 = rhs._type;
+
+ // And of -1. We do not check for (-1&x) because this will already
+ // canonicalize to (x&-1)
+ if( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==-1 )
+ return lhs;
+
+ // Move constants to RHS: con*arg becomes arg*con
+ if ( t1.isConstant() && !t2.isConstant() )
+ return swap12();
+
+ // Do we have ((x & (phi cons)) & con) ?
+ // Do we have ((x & (phi cons)) & (phi cons)) ?
+ // Push constant up through the phi: x & (phi con0&con0 con1&con1...)
+ Node phicon = AddNode.phiCon(this,true);
+ if( phicon!=null ) return phicon;
+
+ return null;
+ }
+ @Override Node copy(Node lhs, Node rhs) { return new AndNode(lhs,rhs); }
+ @Override String err() {
+ if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '&' " + in(1)._type;
+ if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '&' " + in(2)._type;
+ return null;
+ }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
index a31bd963..ae042f30 100644
--- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -8,6 +8,7 @@ import com.seaofnodes.simple.type.TypeFloat;
import com.seaofnodes.simple.type.TypeMemPtr;
import java.util.BitSet;
+import static com.seaofnodes.simple.type.TypeInteger.*;
abstract public class BoolNode extends Node {
@@ -31,29 +32,29 @@ abstract public class BoolNode extends Node {
}
@Override
- public Type compute() {
- if( in(1)._type instanceof TypeInteger i0 &&
- in(2)._type instanceof TypeInteger i1 ) {
- if (i0.isConstant() && i1.isConstant())
- return TypeInteger.constant(doOp(i0.value(), i1.value()) ? 1 : 0);
- }
- if( in(1)._type instanceof TypeFloat i0 &&
- in(2)._type instanceof TypeFloat i1 ) {
- if (i0.isConstant() && i1.isConstant())
- return TypeInteger.constant(doOp(i0.value(), i1.value()) ? 1 : 0);
- }
- return TypeInteger.BOT;
+ public TypeInteger compute() {
+ Type t1 = in(1)._type;
+ Type t2 = in(2)._type;
+ if( t1.isHigh() || t2.isHigh() )
+ return BOOL.dual();
+ // Compare of same
+ if( in(1)==in(2) )
+ return doOp(ZERO,ZERO);
+ if( t1 instanceof TypeInteger i1 &&
+ t2 instanceof TypeInteger i2 )
+ return doOp(i1,i2);
+ if( t1 instanceof TypeFloat f1 &&
+ t2 instanceof TypeFloat f2 &&
+ f1.isConstant() && f2.isConstant() )
+ return TypeInteger.constant(doOp(f1.value(), f2.value()) ? 1 : 0);
+ return BOOL;
}
- boolean doOp(long lhs, long rhs) { throw Utils.TODO(); }
+ TypeInteger doOp(TypeInteger t1, TypeInteger t2) { throw Utils.TODO(); }
boolean doOp(double lhs, double rhs) { throw Utils.TODO(); }
@Override
public Node idealize() {
- // Compare of same
- if( in(1)==in(2) )
- return new ConstantNode(TypeInteger.constant(doOp(3,3)?1:0));
-
// Equals pushes constant to the right; 5==X becomes X==5.
if( this instanceof EQ ) {
if( !(in(2) instanceof ConstantNode) ) {
@@ -63,25 +64,52 @@ abstract public class BoolNode extends Node {
return in(1)._type instanceof TypeFloat ? new EQF(in(2),in(1)) : new EQ(in(2),in(1));
}
// Equals X==0 becomes a !X
- if( (in(2)._type == TypeInteger.ZERO || in(2)._type == TypeMemPtr.NULLPTR) )
+ if( (in(2)._type == ZERO || in(2)._type == TypeMemPtr.NULLPTR) )
return new NotNode(in(1));
+ // Equals bool == 1 becomes bool
+ if( in(2)._type == TRUE && in(1)._type == BOOL )
+ return in(1);
}
- // Do we have ((x * (phi cons)) * con) ?
- // Do we have ((x * (phi cons)) * (phi cons)) ?
- // Push constant up through the phi: x * (phi con0*con0 con1*con1...)
- Node phicon = AddNode.phiCon(this,this instanceof EQ);
- if( phicon!=null ) return phicon;
-
return null;
}
- public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } Node copy(Node lhs, Node rhs) { return new EQ(lhs,rhs); } Node copyF() { return new EQF(null,null); } }
- public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs < rhs; } Node copy(Node lhs, Node rhs) { return new LT(lhs,rhs); } Node copyF() { return new LTF(null,null); }}
- public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } Node copy(Node lhs, Node rhs) { return new LE(lhs,rhs); } Node copyF() { return new LEF(null,null); } }
+ public static class EQ extends BoolNode {
+ public EQ(Node lhs, Node rhs) { super(lhs,rhs); }
+ String op() { return "=="; }
+ TypeInteger doOp(TypeInteger i1, TypeInteger i2) {
+ if( i1==i2 && i1.isConstant() ) return TRUE;
+ if( i1._max < i2._min || i1._min > i2._max ) return FALSE;
+ return BOOL;
+ }
+ Node copy(Node lhs, Node rhs) { return new EQ(lhs,rhs); }
+ Node copyF() { return new EQF(null,null); }
+ }
+ public static class LT extends BoolNode {
+ public LT(Node lhs, Node rhs) { super(lhs,rhs); }
+ String op() { return "<" ; }
+ TypeInteger doOp(TypeInteger i1, TypeInteger i2) {
+ if( i1._max < i2._min ) return TRUE;
+ if( i1._min >= i2._max ) return FALSE;
+ return BOOL;
+ }
+ Node copy(Node lhs, Node rhs) { return new LT(lhs,rhs); }
+ Node copyF() { return new LTF(null,null); }
+ }
+ public static class LE extends BoolNode {
+ public LE(Node lhs, Node rhs) { super(lhs,rhs); }
+ String op() { return "<="; }
+ TypeInteger doOp(TypeInteger i1, TypeInteger i2) {
+ if( i1._max <= i2._min ) return TRUE;
+ if( i1._min > i2._max ) return FALSE;
+ return BOOL;
+ }
+ Node copy(Node lhs, Node rhs) { return new LE(lhs,rhs); }
+ Node copyF() { return new LEF(null,null); }
+ }
- public static class EQF extends EQ { public EQF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs == rhs; } Node copyF() { return null; } }
- public static class LTF extends LT { public LTF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs < rhs; } Node copyF() { return null; } }
- public static class LEF extends LE { public LEF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs <= rhs; } Node copyF() { return null; } }
+ public static class EQF extends EQ { public EQF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs == rhs; } Node copy(Node lhs, Node rhs) { return new EQF(lhs,rhs); } }
+ public static class LTF extends LT { public LTF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs < rhs; } Node copy(Node lhs, Node rhs) { return new LTF(lhs,rhs); } }
+ public static class LEF extends LE { public LEF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs <= rhs; } Node copy(Node lhs, Node rhs) { return new LEF(lhs,rhs); } }
}
diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java
index e0c95019..da9571db 100644
--- a/src/main/java/com/seaofnodes/simple/node/DivNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -21,14 +21,17 @@ public class DivNode extends Node {
@Override
public Type compute() {
- if (in(1)._type instanceof TypeInteger i0 &&
- in(2)._type instanceof TypeInteger i1) {
- if (i0.isConstant() && i1.isConstant())
- return i1.value() == 0
+ Type t1 = in(1)._type, t2 = in(2)._type;
+ if( t1.isHigh() || t2.isHigh() )
+ return TypeInteger.TOP;
+ if( t1 instanceof TypeInteger i1 &&
+ t2 instanceof TypeInteger i2 ) {
+ if (i1.isConstant() && i2.isConstant())
+ return i2.value() == 0
? TypeInteger.ZERO
- : TypeInteger.constant(i0.value()/i1.value());
+ : TypeInteger.constant(i1.value()/i2.value());
}
- return in(1)._type.meet(in(2)._type);
+ return TypeInteger.BOT;
}
@Override
diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java
index a033a7cf..78ccc8a9 100644
--- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java
@@ -73,4 +73,8 @@ public class LoadNode extends MemOpNode {
Node px = phi.in(idx);
return px!=null && px.addDep(this) instanceof StoreNode st1 && ptr()==st1.ptr();
}
+
+ Node copy(Node mem, Node ptr) {
+ return new LoadNode(_name,_alias,_declaredType,mem,ptr);
+ }
}
diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
index 95319c24..76564db0 100644
--- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
@@ -14,7 +14,7 @@ public abstract class MemOpNode extends Node {
public final Type _declaredType;
- public MemOpNode(String name, int alias, Type glb, Node... nodes ) {
+ public MemOpNode(String name, int alias, Type glb, Node... nodes) {
super(nodes);
_name = name;
_alias = alias;
diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java
index ae8e9e1b..8ba45d26 100644
--- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java
@@ -20,8 +20,12 @@ public class MinusNode extends Node {
@Override
public Type compute() {
- if (in(1)._type instanceof TypeInteger i0)
- return i0.isConstant() ? TypeInteger.constant(-i0.value()) : i0;
+ if( in(1)._type instanceof TypeInteger i0 ) {
+ if( i0.isHigh() ) return TypeInteger.TOP;
+ // Catch overflow wrapping on `-Long.MIN_VALUE`
+ if( i0 == TypeInteger.BOT || i0._min == Long.MIN_VALUE ) return TypeInteger.BOT;
+ return TypeInteger.make(-i0._max,-i0._min);
+ }
return TypeInteger.TOP.meet(in(1)._type);
}
diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java
index 16915a1c..6f679462 100644
--- a/src/main/java/com/seaofnodes/simple/node/MulNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -21,12 +21,15 @@ public class MulNode extends Node {
@Override
public Type compute() {
- if (in(1)._type instanceof TypeInteger i0 &&
- in(2)._type instanceof TypeInteger i1) {
- if (i0.isConstant() && i1.isConstant())
- return TypeInteger.constant(i0.value()*i1.value());
+ Type t1 = in(1)._type, t2 = in(2)._type;
+ if( t1.isHigh() || t2.isHigh() )
+ return TypeInteger.TOP;
+ if( t1 instanceof TypeInteger i1 &&
+ t2 instanceof TypeInteger i2 ) {
+ if (i1.isConstant() && i2.isConstant())
+ return TypeInteger.constant(i1.value()*i2.value());
}
- return in(1)._type.meet(in(2)._type);
+ return TypeInteger.BOT;
}
@Override
diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java
index d846fcef..96b569b5 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -93,10 +93,8 @@ public abstract class Node implements OutNode {
@Override
public final String toString() { return print(); }
- // This is a *deep* print. This version will fail on cycles, which we will
- // correct later when we can parse programs with loops. We print with a
- // tik-tok style; the common _print0 calls the per-Node _print1, which
- // calls back to _print0;
+ // This is a *deep* print. We print with a tik-tok style; the common
+ // _print0 calls the per-Node _print1, which calls back to _print0;
public final String print() {
return _print0(new StringBuilder(), new BitSet()).toString();
}
@@ -633,7 +631,12 @@ public abstract class Node implements OutNode {
E x = pred.apply(this);
if( x != null ) return x;
for( Node def : _inputs ) if( def != null && (x = def._walk(pred)) != null ) return x;
- for( Node use : _outputs ) if( use != null && (x = use._walk(pred)) != null ) return x;
+ // Unroll iterator to survive junk CME
+ for( int i=0; i<_outputs.size(); i++ ) {
+ Node use = _outputs.get(i);
+ if( use != null && (x = use._walk(pred)) != null )
+ return x;
+ }
return null;
}
diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java
index 3cf69520..b3c77c45 100644
--- a/src/main/java/com/seaofnodes/simple/node/NotNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java
@@ -20,8 +20,9 @@ public class NotNode extends Node {
@Override
public Type compute() {
Type t0 = in(1)._type;
+ if( t0.isHigh() ) return TypeInteger.BOOL.dual();
switch( t0 ) {
- case TypeInteger i0: return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0;
+ case TypeInteger i0: return i0._max < 0 || i0._min > 0 ? TypeInteger.FALSE : (i0==TypeInteger.ZERO ? TypeInteger.TRUE : TypeInteger.BOT);
case TypeFloat i0: return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0;
case TypeMemPtr p0:
// top->top, bot->bot, null->1, *void->0, not-null ptr->0, ptr/nil->bot
diff --git a/src/main/java/com/seaofnodes/simple/node/OrNode.java b/src/main/java/com/seaofnodes/simple/node/OrNode.java
new file mode 100644
index 00000000..e18996b7
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/OrNode.java
@@ -0,0 +1,63 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+import java.util.BitSet;
+
+public class OrNode extends Node {
+ public OrNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+ @Override public String label() { return "Or"; }
+
+ @Override public String glabel() { return "|"; }
+
+ @Override
+ StringBuilder _print1(StringBuilder sb, BitSet visited) {
+ in(1)._print0(sb.append("("), visited);
+ in(2)._print0(sb.append("|"), visited);
+ return sb.append(")");
+ }
+
+ @Override
+ public Type compute() {
+ if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP;
+ if( in(1)._type instanceof TypeInteger i0 &&
+ in(2)._type instanceof TypeInteger i1 ) {
+ if( i0.isConstant() && i1.isConstant() )
+ return TypeInteger.constant(i0.value()|i1.value());
+ }
+ return TypeInteger.BOT;
+ }
+
+ @Override
+ public Node idealize() {
+ Node lhs = in(1);
+ Node rhs = in(2);
+ Type t1 = lhs._type;
+ Type t2 = rhs._type;
+
+ // Or of 0. We do not check for (0|x) because this will already
+ // canonicalize to (x|0)
+ if( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==0 )
+ return lhs;
+
+ // Move constants to RHS: con*arg becomes arg*con
+ if ( t1.isConstant() && !t2.isConstant() )
+ return swap12();
+
+ // Do we have ((x | (phi cons)) | con) ?
+ // Do we have ((x | (phi cons)) | (phi cons)) ?
+ // Push constant up through the phi: x | (phi con0|con0 con1|con1...)
+ Node phicon = AddNode.phiCon(this,true);
+ if( phicon!=null ) return phicon;
+
+ return null;
+ }
+ @Override Node copy(Node lhs, Node rhs) { return new OrNode(lhs,rhs); }
+ @Override String err() {
+ if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '|' " + in(1)._type;
+ if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '|' " + in(2)._type;
+ return null;
+ }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index ebed8dd1..05584423 100644
--- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -11,7 +11,7 @@ public class PhiNode extends Node {
final String _label;
// The Phi type we compute must stay within the domain of the Phi.
- // Example Int stays Int, Ptr stays Ptr, Control stays Control, Mem stays Mem.
+ // Example Int stays Int, Ptr stays Ptr, Mem stays Mem.
final Type _declaredType;
public PhiNode(String label, Type declaredType, Node... inputs) { super(inputs); _label = label; assert declaredType!=null; _declaredType = declaredType; }
@@ -81,9 +81,16 @@ public class PhiNode extends Node {
lhss[i] = in(i).in(1);
rhss[i] = in(i).in(2);
}
- Node phi_lhs = new PhiNode(_label, _declaredType,lhss).peephole();
- Node phi_rhs = new PhiNode(_label, _declaredType,rhss).peephole();
- return op.copy(phi_lhs,phi_rhs);
+ Node phi_lhs = new PhiNode(_label, in(1).in(1)._type.glb(),lhss).peephole();
+ Node phi_rhs = new PhiNode(_label, in(1).in(2)._type.glb(),rhss).peephole();
+ Node phi_op = op.copy(phi_lhs,phi_rhs);
+ phi_op.setType(phi_op.compute());
+ // If losing precision, don't do it
+ if( !phi_op._type.isa(_type) ) {
+ phi_op.kill();
+ return null;
+ }
+ return phi_op;
}
// If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove.
@@ -114,9 +121,13 @@ public class PhiNode extends Node {
}
private boolean same_op() {
- for( int i=2; i<nIns(); i++ )
- if( in(1).getClass() != in(i).getClass() )
- return false;
+ for( int i=2; i<nIns(); i++ ) {
+ if( in(1).getClass() != in(i).getClass() ) return false;
+ if( in(1).in(1)._type.glb() != in(i).in(1)._type.glb() ) return false;
+ if( in(1).in(2)._type.glb() != in(i).in(2)._type.glb() ) return false;
+ }
+ // Load merging needs an anti-dep check.
+ if( in(1) instanceof MemOpNode ) return false;
return true;
}
diff --git a/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java b/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java
new file mode 100644
index 00000000..44d3a587
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java
@@ -0,0 +1,38 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeFloat;
+
+import java.util.BitSet;
+
+public class RoundF32Node extends Node {
+ public RoundF32Node(Node lhs) { super(null, lhs); }
+
+ @Override public String label() { return "RoundF32"; }
+
+ @Override public String glabel() { return "(f32)"; }
+
+ @Override
+ StringBuilder _print1(StringBuilder sb, BitSet visited) {
+ return in(1)._print0(sb.append("((f32)"), visited).append(")");
+ }
+
+ @Override
+ public Type compute() {
+ if (in(1)._type instanceof TypeFloat i0 && i0.isConstant() )
+ return TypeFloat.constant((float)i0.value());
+ return in(1)._type;
+ }
+
+ @Override
+ public Node idealize() {
+ Node lhs = in(1);
+ Type t1 = lhs._type;
+
+ // RoundF32 of float
+ if( t1 instanceof TypeFloat tf && tf._sz==32 )
+ return lhs;
+
+ return null;
+ }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/SarNode.java b/src/main/java/com/seaofnodes/simple/node/SarNode.java
new file mode 100644
index 00000000..881a3812
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/SarNode.java
@@ -0,0 +1,56 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+import java.util.BitSet;
+
+public class SarNode extends Node {
+ public SarNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+ @Override public String label() { return "Sar"; }
+
+ @Override public String glabel() { return ">>"; }
+
+ @Override
+ StringBuilder _print1(StringBuilder sb, BitSet visited) {
+ in(1)._print0(sb.append("("), visited);
+ in(2)._print0(sb.append(">>"), visited);
+ return sb.append(")");
+ }
+
+ @Override
+ public Type compute() {
+ if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP;
+ if (in(1)._type instanceof TypeInteger i1 &&
+ in(2)._type instanceof TypeInteger i2) {
+ if( i1.isConstant() && i2.isConstant() )
+ return TypeInteger.constant(i1.value()>>i2.value());
+ if( i2._min < 0 || i2._max >= 64 )
+ return TypeInteger.BOT;
+ return TypeInteger.make(i1._min>>i2._min,i1._max>>i2._min);
+ }
+ return TypeInteger.BOT;
+ }
+
+ @Override
+ public Node idealize() {
+ Node lhs = in(1);
+ Node rhs = in(2);
+ Type t2 = rhs._type;
+
+ // Sar of 0.
+ if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 )
+ return lhs;
+
+ // TODO: x >> 3 >> (y ? 1 : 2) ==> x >> (y ? 4 : 5)
+
+ return null;
+ }
+ @Override Node copy(Node lhs, Node rhs) { return new SarNode(lhs,rhs); }
+ @Override String err() {
+ if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '>>' " + in(1)._type;
+ if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '>>' " + in(2)._type;
+ return null;
+ }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/ShlNode.java b/src/main/java/com/seaofnodes/simple/node/ShlNode.java
new file mode 100644
index 00000000..605c5d86
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/ShlNode.java
@@ -0,0 +1,53 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+import java.util.BitSet;
+
+public class ShlNode extends Node {
+ public ShlNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+ @Override public String label() { return "Shl"; }
+
+ @Override public String glabel() { return "<<"; }
+
+ @Override
+ StringBuilder _print1(StringBuilder sb, BitSet visited) {
+ in(1)._print0(sb.append("("), visited);
+ in(2)._print0(sb.append("<<"), visited);
+ return sb.append(")");
+ }
+
+ @Override
+ public Type compute() {
+ if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP;
+ if (in(1)._type instanceof TypeInteger i0 &&
+ in(2)._type instanceof TypeInteger i1) {
+ if( i0.isConstant() && i1.isConstant() )
+ return TypeInteger.constant(i0.value()<<i1.value());
+ }
+ return TypeInteger.BOT;
+ }
+
+ @Override
+ public Node idealize() {
+ Node lhs = in(1);
+ Node rhs = in(2);
+ Type t2 = rhs._type;
+
+ // Shl of 0.
+ if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 )
+ return lhs;
+
+ // TODO: x << 3 << (y ? 1 : 2) ==> x << (y ? 4 : 5)
+
+ return null;
+ }
+ @Override Node copy(Node lhs, Node rhs) { return new ShlNode(lhs,rhs); }
+ @Override String err() {
+ if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '<<' " + in(1)._type;
+ if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '<<' " + in(2)._type;
+ return null;
+ }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/ShrNode.java b/src/main/java/com/seaofnodes/simple/node/ShrNode.java
new file mode 100644
index 00000000..bed18d2b
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/ShrNode.java
@@ -0,0 +1,56 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+import java.util.BitSet;
+
+public class ShrNode extends Node {
+ public ShrNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+ @Override public String label() { return "Shr"; }
+
+ @Override public String glabel() { return ">>>"; }
+
+ @Override
+ StringBuilder _print1(StringBuilder sb, BitSet visited) {
+ in(1)._print0(sb.append("("), visited);
+ in(2)._print0(sb.append(">>>"), visited);
+ return sb.append(")");
+ }
+
+ @Override
+ public Type compute() {
+ if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP;
+ if (in(1)._type instanceof TypeInteger i1 &&
+ in(2)._type instanceof TypeInteger i2) {
+ if( i1.isConstant() && i2.isConstant() )
+ return TypeInteger.constant(i1.value()>>>i2.value());
+ if( i2._min < 0 || i2._max >= 64 )
+ return TypeInteger.BOT;
+ // Zero shifting a negative makes a larger positive
+ // so get the endpoints correct.
+ long s1 = i1._min>>>i2._min;
+ long s2 = i1._max>>>i2._min;
+ boolean wrap = i1._min < 0 && i1._max >=0;
+ return TypeInteger.make(wrap ? 0 : Math.min(s1,s2),Math.max(s1,s2));
+ }
+ return TypeInteger.BOT;
+ }
+
+ @Override
+ public Node idealize() {
+ Node lhs = in(1);
+ Node rhs = in(2);
+ Type t2 = rhs._type;
+
+ // Shr of 0.
+ if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 )
+ return lhs;
+
+ // TODO: x >>> 3 >>> (y ? 1 : 2) ==> x >>> (y ? 4 : 5)
+
+ return null;
+ }
+ @Override Node copy(Node lhs, Node rhs) { return new ShrNode(lhs,rhs); }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/src/main/java/com/seaofnodes/simple/node/SubFNode.java
index 682930e0..b591718d 100644
--- a/src/main/java/com/seaofnodes/simple/node/SubFNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/SubFNode.java
@@ -34,7 +34,7 @@ public class SubFNode extends Node {
Node lhs = in(1);
Type t2 = in(2)._type;
- // Sub of 1.
+ // Sub of 0.
if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==0 )
return lhs;
diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java
index 81cc6076..6d2f1711 100644
--- a/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -26,18 +26,20 @@ public class SubNode extends Node {
if( in(1)==in(2) )
return TypeInteger.ZERO;
- if (in(1)._type instanceof TypeInteger i0 &&
- in(2)._type instanceof TypeInteger i1) {
- if (i0.isConstant() && i1.isConstant())
- return TypeInteger.constant(i0.value()-i1.value());
+ Type t1 = in(1)._type, t2 = in(2)._type;
+ if( t1.isHigh() || t2.isHigh() )
+ return TypeInteger.TOP;
+ if( t1 instanceof TypeInteger i1 &&
+ t2 instanceof TypeInteger i2 ) {
+ if (i1.isConstant() && i2.isConstant())
+ return TypeInteger.constant(i1.value()-i2.value());
}
- return in(1)._type.meet(in(2)._type);
+ return TypeInteger.BOT;
}
@Override
public Node idealize() {
-
// x - (-y) is x+y
if( in(2) instanceof MinusNode minus )
return new AddNode(in(1),minus.in(1));
diff --git a/src/main/java/com/seaofnodes/simple/node/XorNode.java b/src/main/java/com/seaofnodes/simple/node/XorNode.java
new file mode 100644
index 00000000..3978f048
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/XorNode.java
@@ -0,0 +1,63 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+import java.util.BitSet;
+
+public class XorNode extends Node {
+ public XorNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+ @Override public String label() { return "Xor"; }
+
+ @Override public String glabel() { return "^"; }
+
+ @Override
+ StringBuilder _print1(StringBuilder sb, BitSet visited) {
+ in(1)._print0(sb.append("("), visited);
+ in(2)._print0(sb.append("^"), visited);
+ return sb.append(")");
+ }
+
+ @Override
+ public Type compute() {
+ if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP;
+ if( in(1)._type instanceof TypeInteger i0 &&
+ in(2)._type instanceof TypeInteger i1 ) {
+ if( i0.isConstant() && i1.isConstant() )
+ return TypeInteger.constant(i0.value()^i1.value());
+ }
+ return TypeInteger.BOT;
+ }
+
+ @Override
+ public Node idealize() {
+ Node lhs = in(1);
+ Node rhs = in(2);
+ Type t1 = lhs._type;
+ Type t2 = rhs._type;
+
+ // Xor of 0. We do not check for (0^x) because this will already
+ // canonicalize to (x^0)
+ if( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==0 )
+ return lhs;
+
+ // Move constants to RHS: con*arg becomes arg*con
+ if ( t1.isConstant() && !t2.isConstant() )
+ return swap12();
+
+ // Do we have ((x ^ (phi cons)) ^ con) ?
+ // Do we have ((x ^ (phi cons)) ^ (phi cons)) ?
+ // Push constant up through the phi: x ^ (phi con0^con0 con1^con1...)
+ Node phicon = AddNode.phiCon(this,true);
+ if( phicon!=null ) return phicon;
+
+ return null;
+ }
+ @Override Node copy(Node lhs, Node rhs) { return new XorNode(lhs,rhs); }
+ @Override String err() {
+ if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '^' " + in(1)._type;
+ if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '^' " + in(2)._type;
+ return null;
+ }
+}
diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java
index 1f211430..49dc090a 100644
--- a/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -56,6 +56,7 @@ public class Type {
ts.add(CONTROL);
Field.gather(ts);
TypeInteger.gather(ts);
+ TypeFloat.gather(ts);
TypeMem.gather(ts);
TypeMemPtr.gather(ts);
TypeStruct.gather(ts);
@@ -67,6 +68,7 @@ public class Type {
}
// Is high or on the lattice centerline.
+ public boolean isHigh () { return _type==TTOP || _type==TXCTRL; }
public boolean isHighOrConst() { return _type==TTOP || _type==TXCTRL; }
// Strict constant values, things on the lattice centerline.
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java
index 738aebc9..975c1a9e 100644
--- a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java
+++ b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java
@@ -7,44 +7,50 @@ import java.util.ArrayList;
*/
public class TypeFloat extends Type {
- public final static TypeFloat TOP = make(false, 0);
- public final static TypeFloat BOT = make(false, 1);
- public final static TypeFloat ZERO= make(true , 0);
+ public final static TypeFloat TOP = make((byte)-64, 0);
+ public final static TypeFloat T32 = make((byte)-32, 0);
+ public final static TypeFloat ZERO= make((byte) 0, 0);
+ public final static TypeFloat B32 = make((byte) 32, 0);
+ public final static TypeFloat BOT = make((byte) 64, 0);
- public final boolean _is_con;
+ /** +/-64 for double; +/-32 for float, or 0 for constants */
+ public final byte _sz;
/**
- * The constant value or
- * if not constant then 1=bottom, 0=top.
+ * The constant value or 0
*/
public final double _con;
- private TypeFloat(boolean is_con, double con) {
+ private TypeFloat(byte sz, double con) {
super(TFLT);
- _is_con = is_con;
+ _sz = sz ;
_con = con;
}
- public static TypeFloat make(boolean is_con, double con) {
- return new TypeFloat(is_con,con).intern();
+ private static TypeFloat make(byte sz, double con) {
+ return new TypeFloat(sz,con).intern();
}
- public static TypeFloat constant(double con) { return make(true, con); }
+ public static TypeFloat constant(double con) { return make((byte)0, con); }
- public static void gather(ArrayList<Type> ts) { ts.add(ZERO); ts.add(BOT); }
+ public static void gather(ArrayList<Type> ts) { ts.add(ZERO); ts.add(BOT); ts.add(B32); ts.add(constant(3.141592653589793)); }
// FIXME this display format is problematic
// In visualizer '#' gets prepended if its a constant
@Override
public StringBuilder print(StringBuilder sb) {
if( this==TOP ) return sb.append("FltTop");
+ if( this==T32 ) return sb.append("F32Top");
+ if( this==B32 ) return sb.append("F32Bot");
if( this==BOT ) return sb.append("FltBot");
return sb.append(_con);
}
@Override public String str() {
if( this==TOP ) return "~flt";
+ if( this==T32 ) return "~f32";
+ if( this==B32 ) return "f32";
if( this==BOT ) return "flt";
- return ""+_con;
+ return ""+_con+(isF32() ? "f" : "");
}
/**
@@ -53,15 +59,16 @@ public class TypeFloat extends Type {
@Override
public StringBuilder typeName(StringBuilder sb) {
if( this==TOP ) return sb.append("FltTop");
+ if( this==T32 ) return sb.append("F32Top");
+ if( this==B32 ) return sb.append("F32Bot");
if( this==BOT ) return sb.append("FltBot");
- return sb.append("Int");
+ return sb.append(isF32() ? "F32" : "Flt");
}
- @Override
- public boolean isHighOrConst() { return _is_con || _con==0; }
-
- @Override
- public boolean isConstant() { return _is_con; }
+ boolean isF32() { return ((float)_con)==_con; }
+ @Override public boolean isHigh() { return _sz< 0; }
+ @Override public boolean isHighOrConst() { return _sz<=0; }
+ @Override public boolean isConstant() { return _sz==0; }
public double value() { return _con; }
@@ -69,21 +76,27 @@ public class TypeFloat extends Type {
public Type xmeet(Type other) {
// Invariant from caller: 'this' != 'other' and same class (TypeFloat)
TypeFloat i = (TypeFloat)other; // Contract
- // BOT wins
- if ( this==BOT ) return this;
- if ( i ==BOT ) return i ;
- // TOP loses
- if ( i ==TOP ) return this;
- if ( this==TOP ) return i ;
+ // Larger size in i1, smaller in i0
+ TypeFloat i0 = _sz < i._sz ? this : i;
+ TypeFloat i1 = _sz < i._sz ? i : this;
+
+ if( i1._sz== 64 ) return BOT;
+ if( i0._sz==-64 ) return i1;
+ if( i1._sz== 32 )
+ return i0._sz==0 && !i0.isF32() ? BOT : B32;
+ if( i1._sz!= 0 ) return i1;
+ // i1 is a constant
+ if( i0._sz==-32 )
+ return i1.isF32() ? i1 : BOT;
// Since both are constants, and are never equals (contract) unequals
// constants fall to bottom
- return BOT;
+ return i0.isF32() && i1.isF32() ? B32 : BOT;
}
@Override
public Type dual() {
- if( isConstant() ) return this; // Constants are a self-dual
- return _con==0 ? BOT : TOP;
+ if( _sz==0 ) return this; // Constants are a self-dual
+ return make((byte)-_sz,0);
}
@Override
@@ -92,10 +105,10 @@ public class TypeFloat extends Type {
@Override public TypeFloat makeInit() { return ZERO; }
@Override
- int hash() { return (int)(Double.hashCode(_con) ^ (_is_con ? 0 : 0x4000)); }
+ int hash() { return (int)(Double.hashCode(_con) ^ _sz); }
@Override
public boolean eq( Type t ) {
TypeFloat i = (TypeFloat)t; // Contract
- return _con==i._con && _is_con==i._is_con;
+ return _con==i._con && _sz==i._sz;
}
}
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
index 8c77672b..aca3e06b 100644
--- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
+++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
@@ -9,42 +9,56 @@ public class TypeInteger extends Type {
public final static TypeInteger TOP = make(false, 0);
public final static TypeInteger BOT = make(false, 1);
- public final static TypeInteger ZERO= make(true , 0);
-
- public final boolean _is_con;
+ public final static TypeInteger ZERO= make(0,0);
+ public final static TypeInteger U1 = make(0,1);
+ public final static TypeInteger BOOL= U1;
+ public final static TypeInteger FALSE=ZERO;
+ public final static TypeInteger TRUE= make(1,1);
+ public final static TypeInteger I8 = make(-128,127);
+ public final static TypeInteger I16 = make(-32768,32767);
+ public final static TypeInteger I32 = make(-1L<<31,(1L<<31)-1);
+
+ public final static TypeInteger U8 = make(0,255);
+ public final static TypeInteger U16 = make(0,65535);
+ public final static TypeInteger U32 = make(0,(1L<<32)-1);
/**
- * The constant value or
- * if not constant then 1=bottom, 0=top.
+ * Describes an integer *range* - everything from min to max; both min and
+ * max are inclusive. If min==max, this is a constant.
+ *
+ * If min <= max, this is a below center (towards bottom).
+ * If min > max, this is an above center (towards top).
*/
- public final long _con;
+ public final long _min, _max;
- private TypeInteger(boolean is_con, long con) {
- super(TINT);
- _is_con = is_con;
- _con = con;
- }
+ private TypeInteger(long min, long max) { super(TINT); _min = min; _max = max; }
+ public static TypeInteger make(long lo, long hi) { return new TypeInteger(lo,hi).intern(); }
public static TypeInteger make(boolean is_con, long con) {
- return new TypeInteger(is_con,con).intern();
+ return make(is_con ? con : (con==0 ? Long.MAX_VALUE : Long.MIN_VALUE),
+ is_con ? con : (con==0 ? Long.MIN_VALUE : Long.MAX_VALUE));
}
public static TypeInteger constant(long con) { return make(true, con); }
- public static void gather(ArrayList<Type> ts) { ts.add(ZERO); ts.add(BOT); }
+ public static void gather(ArrayList<Type> ts) { ts.add(ZERO); ts.add(BOT); ts.add(U1); ts.add(U8); }
// FIXME this display format is problematic
// In visualizer '#' gets prepended if its a constant
@Override
- public StringBuilder print(StringBuilder sb) {
- if( this==TOP ) return sb.append("IntTop");
- if( this==BOT ) return sb.append("IntBot");
- return sb.append(_con);
- }
+ public StringBuilder print(StringBuilder sb) { return sb.append(str()); }
@Override public String str() {
if( this==TOP ) return "~int";
if( this==BOT ) return "int";
- return ""+_con;
+ if( this==BOOL) return ("bool");
+ if( this==I8 ) return ("i8");
+ if( this==I16 ) return ("i16");
+ if( this==I32 ) return ("i32");
+ if( this==U8 ) return ("u8");
+ if( this==U16 ) return ("u16");
+ if( this==U32 ) return ("u32");
+ if( isConstant() ) return ""+_min;
+ return "["+_min+"-"+_max+"]";
}
/**
@@ -57,45 +71,45 @@ public class TypeInteger extends Type {
return sb.append("Int");
}
- @Override
- public boolean isHighOrConst() { return _is_con || _con==0; }
-
- @Override
- public boolean isConstant() { return _is_con; }
-
- public long value() { return _con; }
+ @Override public boolean isHigh () { return _min > _max; }
+ @Override public boolean isHighOrConst() { return _min >= _max; }
+ @Override public boolean isConstant () { return _min == _max; }
+
+ public long value() { assert isConstant(); return _min; }
+
+ // AND-mask of forced zeros. e.g. unsigned types will return their mask;
+ // u8 will return 0xFF. But also a range of 16-18 (0x10-0x12) will return
+ // 0x13 - no value in the range {16,17,18} will allow bit 0x04 to be set.
+ public long mask() {
+ if( isHigh() ) return 0;
+ if( isConstant() ) return _min;
+ //if( _min<0 ) return -1L;
+ //if( _max==Long.MAX_VALUE ) return -1L;
+ // Those bit positions which differ min to max
+ long x = _min ^ _max;
+ // Highest '1' bit in the differ set. Since the range is from min to
+ // max, all values below here are possible.
+ long ff1 = Long.highestOneBit(x);
+ // Make a all-1's mask from ff1, and set over the same bits (either min
+ // or max is ok).
+ long mask = _min | (ff1-1) | ff1;
+ return mask;
+ }
@Override
public Type xmeet(Type other) {
// Invariant from caller: 'this' != 'other' and same class (TypeInteger)
TypeInteger i = (TypeInteger)other; // Contract
- // BOT wins
- if ( this==BOT ) return this;
- if ( i ==BOT ) return i ;
- // TOP loses
- if ( i ==TOP ) return this;
- if ( this==TOP ) return i ;
- // Since both are constants, and are never equals (contract) unequals
- // constants fall to bottom
- return BOT;
- }
-
- @Override
- public Type dual() {
- if( isConstant() ) return this; // Constants are a self-dual
- return _con==0 ? BOT : TOP;
+ return make(Math.min(_min,i._min), Math.max(_max,i._max));
}
- @Override
- public Type glb() { return BOT; }
-
+ @Override public TypeInteger dual() { return make(_max,_min); }
+ @Override public Type glb() { return BOT; }
@Override public TypeInteger makeInit() { return ZERO; }
-
- @Override
- int hash() { return (int)(_con ^ (_is_con ? 0 : 0x4000)); }
+ @Override int hash() { return (int)((_min ^ (_min>>32)) *(_max ^ (_max>>32))); }
@Override
public boolean eq( Type t ) {
TypeInteger i = (TypeInteger)t; // Contract
- return _con==i._con && _is_con==i._is_con;
+ return _min==i._min && _max==i._max;
}
}
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java
index 81725a87..c93c3074 100644
--- a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java
+++ b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java
@@ -55,6 +55,8 @@ public class TypeMemPtr extends Type {
public Type glb() { return make(_obj.glb(),true); }
@Override public TypeMemPtr makeInit() { return NULLPTR; }
+ @Override public boolean isHigh() { return this==TOP; }
+
@Override
int hash() { return _obj.hashCode() ^ (_nil ? 1024 : 0); }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java
index 633b25e0..99ce8fa5 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter06Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java
@@ -27,10 +27,10 @@ return 1;
int a = 1;
if (arg)
a = 2;
-return (arg < a) < 3;
+return (arg < a) < 3; // Because (arg < a) is a bool/uint1/[0-1], its always less than 3
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return ((arg<Phi(Region16,2,1))<3);", stop.toString());
+ assertEquals("return 1;", stop.toString());
}
@Test
@@ -65,7 +65,7 @@ else
b=5;
return b;""", TypeInteger.BOT);
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Region39,42,5);", stop.toString());
+ assertEquals("return Phi(Region34,42,5);", stop.toString());
}
@Test
diff --git a/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/src/test/java/com/seaofnodes/simple/Chapter07Test.java
index e604937c..e6e0560b 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter07Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter07Test.java
@@ -1,7 +1,6 @@
package com.seaofnodes.simple;
import com.seaofnodes.simple.node.*;
-import com.seaofnodes.simple.type.TypeInteger;
import org.junit.Test;
import static org.junit.Assert.*;
diff --git a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/src/test/java/com/seaofnodes/simple/Chapter10Test.java
index c9f695c9..fb324fd9 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter10Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter10Test.java
@@ -28,7 +28,7 @@ if( (arg/13)==0 ) {
int r = g+h;
return p-r;
""");
- StopNode stop = parser.parse().iterate(false);
+ StopNode stop = parser.parse(false).iterate(false);
assertEquals("return 0;", stop.toString());
}
@@ -48,7 +48,7 @@ bar.a = 1;
bar.a = 2;
return bar.a;
""");
- StopNode stop = parser.parse().iterate();
+ StopNode stop = parser.parse(false).iterate();
assertEquals("return 2;", stop.toString());
}
@@ -102,7 +102,7 @@ while (arg) {
}
return bar.a;
""");
- StopNode stop = parser.parse().iterate();
+ StopNode stop = parser.parse(false).iterate();
assertEquals("return Phi(Loop12,0,(Phi_a+2));", stop.toString());
}
@@ -154,7 +154,7 @@ if (arg) bar = null;
if( bar ) bar.a = 1;
return bar;
""");
- StopNode stop = parser.parse().iterate();
+ StopNode stop = parser.parse(false).iterate();
assertEquals("return Phi(Region31,(*void)Phi(Region19,null,new Bar),null);", stop.toString());
}
@@ -170,7 +170,7 @@ if( !bar ) rez=4;
else bar.a = 1;
return rez;
""");
- StopNode stop = parser.parse().iterate();
+ StopNode stop = parser.parse(false).iterate();
assertEquals("return Phi(Region37,4,3);", stop.toString());
}
diff --git a/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/src/test/java/com/seaofnodes/simple/Chapter11Test.java
index da0bc087..63cd511a 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter11Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter11Test.java
@@ -292,7 +292,7 @@ else {
}
""");
StopNode stop = parser.parse().iterate(false);
- assertEquals("Stop[ return 9; return 0; return 0; return 0; return 0; ]", stop.toString());
+ assertEquals("Stop[ return 9; return 0; return 0; return 0; ]", stop.toString());
}
diff --git a/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/src/test/java/com/seaofnodes/simple/Chapter12Test.java
index 62dce12b..972118be 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter12Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter12Test.java
@@ -59,5 +59,4 @@ return x+1==x;
assertEquals("return ((flt)arg==(ToFloat+1.0));", stop.toString());
assertEquals(0L, Evaluator.evaluate(stop, 1));
}
-
}
diff --git a/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/src/test/java/com/seaofnodes/simple/Chapter13Test.java
index 59f08963..807badd5 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter13Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter13Test.java
@@ -127,7 +127,7 @@ n.i = 3.14;
return n.i;
""");
try { parser.parse().iterate(); fail(); }
- catch( Exception e ) { assertEquals("Cannot store 3.14 into field IntBot i",e.getMessage()); }
+ catch( Exception e ) { assertEquals("Cannot store 3.14 into field int i",e.getMessage()); }
}
@Test
diff --git a/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/src/test/java/com/seaofnodes/simple/Chapter14Test.java
new file mode 100644
index 00000000..fcb7fa24
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/Chapter14Test.java
@@ -0,0 +1,317 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.evaluator.Evaluator;
+import com.seaofnodes.simple.node.StopNode;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.fail;
+
+public class Chapter14Test {
+
+ @Test
+ public void testJig() {
+ Parser parser = new Parser(
+"""
+return 3.14;
+""");
+ StopNode stop = parser.parse(false).iterate();
+ assertEquals("return 3.14;", stop.toString());
+ assertEquals(3.14, Evaluator.evaluate(stop, 0));
+ }
+
+ @Test
+ public void testRange() {
+ Parser parser = new Parser(
+"""
+int b;
+if( arg ) b=1; else b=0;
+int c = 99;
+if( b < 0 ) c = -1;
+if( b > 2 ) c = 1;
+return c;
+""");
+ StopNode stop = parser.parse(false).iterate(false);
+ assertEquals("return 99;", stop.toString());
+ assertEquals(99L, Evaluator.evaluate(stop, 0));
+ }
+
+ @Test
+ public void testU8() {
+ Parser parser = new Parser(
+"""
+u8 b = 123;
+b = b + 456;// Truncate
+return b;
+""");
+ StopNode stop = parser.parse(false).iterate(false);
+ assertEquals("return 67;", stop.toString());
+ assertEquals(67L, Evaluator.evaluate(stop, 0));
+ }
+
+
+ @Test
+ public void testU8While() {
+ Parser parser = new Parser(
+"""
+u8 b = 123;
+while( b ) b = b + 456;// Truncate
+return b;
+""");
+ StopNode stop = parser.parse(false).iterate(false);
+ assertEquals("return Phi(Loop9,123,((Phi_b+456)&255));", stop.toString());
+ }
+
+ @Test
+ public void testU1() {
+ Parser parser = new Parser(
+"""
+bool b = 123;
+b = b + 456;// Truncate
+u1 c = b; // No more truncate needed
+return c;
+""");
+ StopNode stop = parser.parse(false).iterate(false);
+ assertEquals("return 1;", stop.toString());
+ assertEquals(1L, Evaluator.evaluate(stop, 0));
+ }
+
+ @Test
+ public void testAnd() {
+ Parser parser = new Parser(
+"""
+int b = 123;
+b = b+456 & 31; // Precedence
+return b;
+""");
+ StopNode stop = parser.parse(false).iterate(false);
+ assertEquals("return 3;", stop.toString());
+ assertEquals(3L, Evaluator.evaluate(stop, 0));
+ }
+
+ @Test
+ public void testRefLoad() {
+ Parser parser = new Parser(
+"""
+struct Foo { u1 b; }
+Foo f = new Foo;
+f.b = 123;
+return f.b;
+""");
+ StopNode stop = parser.parse(false).iterate(false);
+ assertEquals("return 1;", stop.toString());
+ assertEquals(1L, Evaluator.evaluate(stop, 0));
+ }
+
+ @Test
+ public void testSigned() {
+ Parser parser = new Parser(
+"""
+i8 b = 255; // Chopped
+return b; // Sign extend
+""");
+ StopNode stop = parser.parse(false).iterate(false);
+ assertEquals("return -1;", stop.toString());
+ assertEquals(-1L, Evaluator.evaluate(stop, 0));
+ }
+
+ @Test
+ public void testI8() {
+ Parser parser = new Parser(
+"""
+i8 b = arg;
+b = b + 1;// Truncate
+return b;
+""");
+ StopNode stop = parser.parse(false).iterate(false);
+ assertEquals("return (((((arg<<56)>>56)+1)<<56)>>56);", stop.toString());
+ assertEquals(1L, Evaluator.evaluate(stop, 0));
+ }
+
+ @Test
+ public void testMask() {
+ Parser parser = new Parser(
+"""
+u16 mask = (1<<16)-1; // AND mask
+int c = 123456789 & mask;
+return c; //
+""");
+ StopNode stop = parser.parse(false).iterate(false);
+ assertEquals("return 52501;", stop.toString());
+ assertEquals(52501L, Evaluator.evaluate(stop, 0));
+ }
+
+ @Test
+ public void testWrapMinus() {
+ Parser parser = new Parser(
+"""
+int MAX = 9223372036854775807; //0x7FFFFFFFFFFFFFFF;
+int i = (arg&MAX) + -MAX + -1; // Basically (e0) + Long.MIN_VALUE
+int j = -i; // Negating Long.MIN_VALUE wraps, cannot constant fold
+if (arg) j = 1;
+return j;
+""");
+ StopNode stop = parser.parse(false).iterate();
+ assertEquals("return Phi(Region28,1,(-((arg&9223372036854775807)+-9223372036854775808)));", stop.toString());
+ assertEquals(-9223372036854775808L, Evaluator.evaluate(stop, 0));
+ assertEquals(1L, Evaluator.evaluate(stop, 1));
+ }
+
+ @Test
+ public void testWrapShr() {
+ Parser parser = new Parser(
+"""
+return (arg >>> 1)==0;
+""");
+ StopNode stop = parser.parse(false).iterate();
+ assertEquals("return (!(arg>>>1));", stop.toString());
+ assertEquals(1L, Evaluator.evaluate(stop, 0));
+ assertEquals(1L, Evaluator.evaluate(stop, 1));
+ assertEquals(0L, Evaluator.evaluate(stop, 2));
+ }
+
+ @Test
+ public void testOr() {
+ Parser parser = new Parser(
+"""
+return (arg | 123 ^ 456) >>> 1;
+""");
+ StopNode stop = parser.parse(false).iterate(false);
+ assertEquals("return (((arg|123)^456)>>>1);", stop.toString());
+ assertEquals(217L, Evaluator.evaluate(stop, 0));
+ }
+
+ @Test
+ public void testMaskFloat() {
+ Parser parser = new Parser(
+"""
+flt f = arg;
+arg = f & 0;
+return arg;
+""");
+ try { parser.parse().iterate(); fail(); }
+ catch( Exception e ) { assertEquals("Cannot '&' FltBot",e.getMessage()); }
+ }
+
+ @Test
+ public void testLoadBug() {
+ Parser parser = new Parser(
+"""
+struct A { int i; }
+struct B { int i; }
+A a = new A;
+A t1 = new A;
+B b = new B;
+B t2 = new B;
+int i;
+if (arg) i = a.i;
+else i = b.i;
+return i;
+""");
+ StopNode stop = parser.parse(false).iterate(false);
+ assertEquals("return Phi(Region31,.i,.i);", stop.toString());
+ assertEquals(0L, Evaluator.evaluate(stop, 0));
+ }
+
+ @Test
+ public void testBug2() {
+ Parser parser = new Parser(
+"""
+int z = 0;
+while (1) {
+ int j;
+ if (arg&3) {
+ j = arg >> 2;
+ } else {
+ j = (arg >> 3)+z;
+ }
+ return j+1;
+}
+""");
+ StopNode stop = parser.parse(false).iterate(false);
+ assertEquals("return ((arg>>Phi(Region32,2,3))+1);", stop.toString());
+ assertEquals(1L, Evaluator.evaluate(stop, 0));
+ assertEquals(1L, Evaluator.evaluate(stop, 1));
+ assertEquals(2L, Evaluator.evaluate(stop, 7));
+ assertEquals(2L, Evaluator.evaluate(stop, 8));
+ }
+
+ @Test
+ public void testBug3() {
+ Parser parser = new Parser(
+"""
+flt f = arg;
+bool b;
+if (arg&3) b = f == 1.0;
+else b = f == 2.0;
+if (arg&5) b = arg == 1;
+return b;
+""");
+ StopNode stop = parser.parse(false).iterate(false);
+ assertEquals("return Phi(Region37,(arg==1),((flt)arg==Phi(Region23,1.0,2.0)));", stop.toString());
+ assertEquals(1L, Evaluator.evaluate(stop, 1));
+ assertEquals(0L, Evaluator.evaluate(stop, 2));
+ assertEquals(0L, Evaluator.evaluate(stop, 3));
+ }
+
+ @Test
+ public void testBug4() {
+ Parser parser = new Parser(
+"""
+int i;
+if (arg&7) i=3;
+else i=2;
+return (arg == i) == 1;
+""");
+ StopNode stop = parser.parse(false).iterate();
+ assertEquals("return (arg==Phi(Region18,3,2));", stop.toString());
+ assertEquals(0L, Evaluator.evaluate(stop, 0));
+ assertEquals(0L, Evaluator.evaluate(stop, 1));
+ assertEquals(0L, Evaluator.evaluate(stop, 2));
+ assertEquals(1L, Evaluator.evaluate(stop, 3));
+ }
+
+ @Test
+ public void testBug5() {
+ Parser parser = new Parser(
+"""
+int d = -1;
+while (1) {
+ int i = (arg & 7) + (9223372036854775807 - 7);
+ if (arg & 1) i = ((arg&3) + (9223372036854775807 - 3)) & d;
+ return i + -1;
+}
+""");
+ StopNode stop = parser.parse(false).iterate();
+ assertEquals("return (Phi(Region43,((arg&3)+9223372036854775804),((arg&7)+9223372036854775800))+-1);", stop.toString());
+ assertEquals(0x7FFFFFFFFFFFFFF7L, Evaluator.evaluate(stop, 0));
+ assertEquals(0x7FFFFFFFFFFFFFFCL, Evaluator.evaluate(stop, 1));
+ }
+
+ @Test
+ public void testTypes() {
+ Parser parser = new Parser(
+"""
+i8 xi8 = 123456789; if( xi8 != 21 ) return -8;
+i16 xi16 = 123456789; if( xi16 != -13035 ) return -16;
+i32 xi32 = 123456789; if( xi32 != 123456789 ) return -32;
+i64 xi64 = 123456789; if( xi64 != 123456789 ) return -64;
+int xint = 123456789; if( xint != 123456789 ) return -64;
+
+u1 ui1 = 123456789; if( ui1 != 1 ) return 1;
+u8 ui8 = 123456789; if( ui8 != 21 ) return 8;
+u16 ui16 = 123456789; if( ui16 != 52501 ) return 16;
+u32 ui32 = 123456789; if( ui32 != 123456789 ) return 32;
+
+flt fflt = 3.141592653589793; if( fflt != 3.141592653589793 ) return 3;
+f64 ff64 = 3.141592653589793; if( ff64 != 3.141592653589793 ) return 3;
+f32 ff32 = 3.141592653589793; if( ff32 != 3.1415927410125732) return 5;
+
+return 0;
+""");
+ StopNode stop = parser.parse().iterate(false);
+ assertEquals("return 0;", stop.toString());
+ assertEquals(0L, Evaluator.evaluate(stop, 0));
+ }
+
+}
diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
index 3512d2e9..31a14c05 100644
--- a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
+++ b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
@@ -150,6 +150,12 @@ public class Evaluator {
case NotNode not -> isTrue(val(not.in(1))) ? 0L : 1L;
case SubNode sub -> vall(sub.in(1)) - vall(sub.in(2));
case SubFNode sub -> vald(sub.in(1)) - vald(sub.in(2));
+ case ShlNode shl -> vall(shl.in(1)) << vall(shl.in(2));
+ case ShrNode shr -> vall(shr.in(1)) >>> vall(shr.in(2));
+ case SarNode sar -> vall(sar.in(1)) >> vall(sar.in(2));
+ case AndNode and -> vall(and.in(1)) & vall(and.in(2));
+ case OrNode or -> vall(or .in(1)) | vall(or .in(2));
+ case XorNode xor -> vall(xor.in(1)) ^ vall(xor.in(2));
case CastNode cast -> val(cast.in(1));
case ToFloatNode cast -> (double)vall(cast.in(1));
case LoadNode load -> load(load);
diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
index 94929241..ec6e7816 100644
--- a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
+++ b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
@@ -2,8 +2,12 @@ package com.seaofnodes.simple.fuzzer;
import com.seaofnodes.simple.Parser;
import com.seaofnodes.simple.node.ScopeNode;
+import com.seaofnodes.simple.type.TypeInteger;
-import java.util.*;
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Random;
import java.util.function.Predicate;
/**
@@ -21,7 +25,7 @@ public class ScriptGenerator {
private static final int MAX_BLOCK_DEPTH = 4;
private static final int MAX_EXPRESSION_DEPTH = 10;
private static final int MAX_SUFFIX_RECURSIVE_DEPTH = 10;
-
+
/**
* Number of spaces per indentation
*/
@@ -54,7 +58,7 @@ public class ScriptGenerator {
/**
* Binary operators.
*/
- private static final String[] BINARY_OP = {"==", "!=", "<", "<=", ">", ">=", "+", "-", "*", "/"};
+ private static final String[] BINARY_OP = {"==", "!=", "<", "<=", ">", ">=", "+", "-", "*", "/", "&", ">>", ">>>", "<<"};
/**
* Unary operators.
*/
@@ -91,18 +95,29 @@ public class ScriptGenerator {
private static class TypeInt extends Type {
- TypeInt() {
- super("int");
+ TypeInt(String name) {
+ super(name);
}
@Override
boolean isa(Type other) {
- return super.isa(other) || other == TYPE_FLT;
+ return super.isa(other) || other == TYPE_FLT || other instanceof TypeInt;
}
}
- private static final Type TYPE_INT = new TypeInt();
+ private static final List<TypeInt> INTTYPES = new ArrayList<>();
+
+ static {
+ new Parser("", TypeInteger.BOT);
+ for(var e:Parser.TYPES.entrySet()) {
+ if (e.getValue() instanceof TypeInteger) {
+ INTTYPES.add(new TypeInt(e.getKey()));
+ }
+ }
+ }
+ private static final Type TYPE_INT = INTTYPES.stream().filter(t->t.name.equals("int")).findAny().get();
+ private static final Type TYPE_BOOL = INTTYPES.stream().filter(t->t.name.equals("bool")).findAny().get();
private static class Variable {
final String name;
@@ -361,13 +376,17 @@ public class ScriptGenerator {
return v;
}
+ public TypeInt getIntType() {
+ return randFromList(INTTYPES);
+ }
+
/**
* Get a random type
* @return A random type
*/
private Type getType(boolean allowForward) {
int t = random.nextInt(10);
- if( t<5 || structs.isEmpty() ) return TYPE_INT;
+ if( t<5 || structs.isEmpty() ) return getIntType();
if( t<7 ) return TYPE_FLT;
if (allowForward && random.nextInt(10)==0) {
int i=random.nextInt(forwardStructs.size()+1);
@@ -448,7 +467,7 @@ public class ScriptGenerator {
int idx = random.nextInt(forwardStructs.size()+10);
TypeStruct struct;
if (idx < 10) {
- var name = getStructName();
+ var name = getStructName();
struct = new TypeStruct(name);
forwardStructs.add(struct);
} else {
@@ -561,7 +580,7 @@ public class ScriptGenerator {
*/
public int genIf() {
sb.append("if(");
- genExpression(TYPE_INT, true);
+ genExpression(TYPE_BOOL, true);
sb.append(") ");
var stop = genStatementBlock();
if ((stop & FLAG_IF_WITHOUT_ELSE) == 0 && random.nextInt(10) > 3) {
@@ -607,7 +626,7 @@ public class ScriptGenerator {
*/
public int genWhile() {
sb.append("while(");
- genExpression(TYPE_INT, true);
+ genExpression(TYPE_BOOL, true);
sb.append(") ");
loopDepth++;
genStatementBlock();
@@ -725,7 +744,7 @@ public class ScriptGenerator {
*/
public void genExpression(Type type, boolean change) {
if (change && generateInvalid()) type = getType();
- if (type != TYPE_INT && type != TYPE_FLT) {
+ if (!(type instanceof TypeInt) && type != TYPE_FLT) {
genUnary(type, false);
return;
}
@@ -742,7 +761,7 @@ public class ScriptGenerator {
*/
public void genUnary(Type type, boolean change) {
if (change && generateInvalid()) type = getType();
- if (type != TYPE_INT && type != TYPE_FLT) {
+ if (!(type instanceof TypeInt) && type != TYPE_FLT) {
genSuffix(type, false);
return;
}
@@ -822,7 +841,7 @@ public class ScriptGenerator {
*/
public void genConst(Type type) {
if (generateInvalid()) type = getType();
- if (type == TYPE_INT || (type == TYPE_FLT && random.nextBoolean())) {
+ if (type instanceof TypeInt || (type == TYPE_FLT && random.nextBoolean())) {
var rand = random.nextInt(10);
switch (rand) {
case 0 -> sb.append("true");