diff options
| author | Cliff Click <cliffc@acm.org> | 2024-08-06 13:09:38 +0100 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2025-04-24 14:38:36 -0700 |
| commit | 773344c88d5be5efc2a5b8397e764375cd9c16a8 (patch) | |
| tree | 38357a72a4fdc17eeb8318c292fc3deb61288294 | |
| parent | fffa2b9d187985e50d6c2de1b5fc9334040d0479 (diff) | |
| download | Simple-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>
39 files changed, 2489 insertions, 183 deletions
@@ -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. + + + +### 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->XCTRL -->
+<g id="edge1" class="edge">
+<title>TOP->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->INT_TOP -->
+<g id="edge4" class="edge">
+<title>TOP->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->FLT_TOP -->
+<g id="edge18" class="edge">
+<title>TOP->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->PTR -->
+<g id="edge33" class="edge">
+<title>TOP->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->STRUCT_TOP -->
+<g id="edge36" class="edge">
+<title>TOP->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->MEM_TOP -->
+<g id="edge46" class="edge">
+<title>TOP->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->TUPLE_TOP -->
+<g id="edge56" class="edge">
+<title>TOP->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->CTRL -->
+<g id="edge2" class="edge">
+<title>XCTRL->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->BOT -->
+<g id="edge3" class="edge">
+<title>CTRL->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 < min</text>
+</g>
+<!-- INT_TOP->INT_HI -->
+<g id="edge5" class="edge">
+<title>INT_TOP->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->BOT -->
+<g id="edge15" class="edge">
+<title>INT_BOT->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->INT_XBOOL -->
+<g id="edge6" class="edge">
+<title>INT_HI->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->INT_CON -->
+<g id="edge9" class="edge">
+<title>INT_HI->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->INT_CON0 -->
+<g id="edge7" class="edge">
+<title>INT_XBOOL->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->INT_CON1 -->
+<g id="edge8" class="edge">
+<title>INT_XBOOL->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 > min</text>
+</g>
+<!-- INT_CON->INT_LO -->
+<g id="edge13" class="edge">
+<title>INT_CON->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->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->INT_BOOL -->
+<g id="edge10" class="edge">
+<title>INT_CON0->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->INT_CON -->
+<!-- INT_CON1->INT_BOOL -->
+<g id="edge11" class="edge">
+<title>INT_CON1->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->INT_LO -->
+<g id="edge12" class="edge">
+<title>INT_BOOL->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->INT_BOT -->
+<g id="edge14" class="edge">
+<title>INT_LO->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->FLT_CON64 -->
+<g id="edge19" class="edge">
+<title>FLT_TOP->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->FLT_CONPI -->
+<g id="edge20" class="edge">
+<title>FLT_TOP->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->FLT_X32 -->
+<g id="edge23" class="edge">
+<title>FLT_TOP->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->BOT -->
+<g id="edge29" class="edge">
+<title>FLT_BOT->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->FLT_BOT -->
+<g id="edge21" class="edge">
+<title>FLT_CON64->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->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->FLT_32 -->
+<g id="edge27" class="edge">
+<title>FLT_CON32->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->FLT_BOT -->
+<g id="edge22" class="edge">
+<title>FLT_CONPI->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->FLT_CON64 -->
+<!-- FLT_X32->FLT_CON32 -->
+<g id="edge25" class="edge">
+<title>FLT_X32->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->FLT_CON0 -->
+<g id="edge24" class="edge">
+<title>FLT_X32->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->FLT_CON32 -->
+<!-- FLT_CON0->FLT_32 -->
+<g id="edge26" class="edge">
+<title>FLT_CON0->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->FLT_BOT -->
+<g id="edge28" class="edge">
+<title>FLT_32->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->PTR0 -->
+<g id="edge34" class="edge">
+<title>PTR->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->BOT -->
+<g id="edge35" class="edge">
+<title>PTR0->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->STRUCT_S1 -->
+<g id="edge37" class="edge">
+<title>STRUCT_TOP->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->STRUCT_S2 -->
+<g id="edge38" class="edge">
+<title>STRUCT_TOP->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">...  </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->STRUCT_SN -->
+<g id="edge39" class="edge">
+<title>STRUCT_TOP->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->BOT -->
+<g id="edge43" class="edge">
+<title>STRUCT_BOT->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->STRUCT_BOT -->
+<g id="edge40" class="edge">
+<title>STRUCT_S1->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->STRUCT_S2 -->
+<!-- STRUCT_S2->STRUCT_BOT -->
+<g id="edge41" class="edge">
+<title>STRUCT_S2->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->STRUCT_SN -->
+<!-- STRUCT_SN->STRUCT_BOT -->
+<g id="edge42" class="edge">
+<title>STRUCT_SN->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->MEM_ALIAS1 -->
+<g id="edge47" class="edge">
+<title>MEM_TOP->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->MEM_ALIASDOTS -->
+<g id="edge48" class="edge">
+<title>MEM_TOP->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->MEM_ALIASN -->
+<g id="edge49" class="edge">
+<title>MEM_TOP->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->BOT -->
+<g id="edge53" class="edge">
+<title>MEM_BOT->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->MEM_BOT -->
+<g id="edge50" class="edge">
+<title>MEM_ALIAS1->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->MEM_ALIASDOTS -->
+<!-- MEM_ALIASDOTS->MEM_BOT -->
+<g id="edge51" class="edge">
+<title>MEM_ALIASDOTS->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->MEM_ALIASN -->
+<!-- MEM_ALIASN->MEM_BOT -->
+<g id="edge52" class="edge">
+<title>MEM_ALIASN->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->TUPLE1 -->
+<g id="edge57" class="edge">
+<title>TUPLE_TOP->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->TUPLE2 -->
+<g id="edge58" class="edge">
+<title>TUPLE_TOP->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->TUPLEN -->
+<g id="edge59" class="edge">
+<title>TUPLE_TOP->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->BOT -->
+<g id="edge63" class="edge">
+<title>TUPLE_BOT->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->TUPLE_BOT -->
+<g id="edge60" class="edge">
+<title>TUPLE1->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->TUPLE_BOT -->
+<g id="edge61" class="edge">
+<title>TUPLE2->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->TUPLE_BOT -->
+<g id="edge62" class="edge">
+<title>TUPLEN->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"); |
