diff options
| author | Cliff Click <cliffc@acm.org> | 2024-08-06 13:09:38 +0100 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-10-08 16:52:27 -0700 |
| commit | 6653a056b0d82568c40ca6e31b9fcc9ce3a8e9ee (patch) | |
| tree | 6f0db328a23980dffc834fca87f2c21ab9797956 | |
| parent | fc06aa2bebec45aa93df5450ebf4c327f9f51496 (diff) | |
| download | Simple-6653a056b0d82568c40ca6e31b9fcc9ce3a8e9ee.tar.gz Simple-6653a056b0d82568c40ca6e31b9fcc9ce3a8e9ee.zip | |
Chapter 14: Numeric 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: Hsiang-Ying Fu <66062782+fuhsnn@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: fuhsnn <66062782+fuhsnn@users.noreply.github.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>
Co-authored-by: Jun Kawasaki <jun784@gmail.com>
51 files changed, 3712 insertions, 188 deletions
diff --git a/README.ja.md b/README.ja.md index a35cc238..d4ad30b1 100644 --- a/README.ja.md +++ b/README.ja.md @@ -50,7 +50,7 @@ Simple 言語のスタイルは、C または Java のサブセットに倣っ * [第11章](docs/chapter11/README.ja.md)：同値類によるエイリアス解析。`MemMerge`、`MemPhi`、`BulkMemPhi` による必要時のメモリ分割。 * [第12章](docs/chapter12/README.ja.md)：参照フィールド、前方参照、再帰的な構造体。 * [第13章](docs/chapter13/README.ja.md)：大域的コード移動とスケジューリング。 -* 第14章：数値型。浮動小数点数、狭い整数型、範囲、`f32` への丸め。 +* [第14章](docs/chapter14/README.ja.md)：数値型。浮動小数点数、狭い整数型、範囲、`f32` への丸め。 * 第15章：静的な長さを持つ一次元配列型。配列のロードとストア。 * 第16章：コンストラクタ。 * 第17a章：束縛の可変性、参照の権限、深い読み取り専用ビュー。 @@ -59,7 +59,7 @@ The Simple language is styled after a subset of C or Java. partitioning with `MemMerge`, `MemPhi`, and `BulkMemPhi`. * [Chapter 12](docs/chapter12/README.md): Reference fields, forward references and recursive structs. * [Chapter 13](docs/chapter13/README.md): Global Code Motion - Scheduling. -* Chapter 14: Numeric types: floats, narrow integers, ranges and rounding to `f32`. +* [Chapter 14](docs/chapter14/README.md): Numeric types: floats, narrow integers, ranges and rounding to `f32`. * Chapter 15: One dimensional static length array type, with array loads and stores. * Chapter 16: Constructors * Chapter 17a: Binding mutability, reference permissions, and deep read-only views. diff --git a/chapter13.iml b/chapter14.iml index 6fa60f3f..4c719b6d 100644 --- a/chapter13.iml +++ b/chapter14.iml @@ -1,8 +1,8 @@ <?xml version="1.0" encoding="UTF-8"?> <module type="JAVA_MODULE" version="4"> <component name="NewModuleRootManager" inherit-compiler-output="false"> - <output url="file://$MODULE_DIR$/../build/idea/production/chapter13" /> - <output-test url="file://$MODULE_DIR$/../build/idea/test/chapter13" /> + <output url="file://$MODULE_DIR$/../build/idea/production/chapter14" /> + <output-test url="file://$MODULE_DIR$/../build/idea/test/chapter14" /> <exclude-output /> <content url="file://$MODULE_DIR$"> <sourceFolder url="file://$MODULE_DIR$/src/main/java" isTestSource="false" /> diff --git a/docs/chapter14/14-grammar.ja.md b/docs/chapter14/14-grammar.ja.md new file mode 100644 index 00000000..2432ac72 --- /dev/null +++ b/docs/chapter14/14-grammar.ja.md @@ -0,0 +1,128 @@ +# 第14章の文法 + +[English](14-grammar.md) | 日本語 + +この文書は [原文](14-grammar.md) の日本語訳です。 + +[第14章に戻る](README.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program : block EOF ; + +block : statement+ ; + + +statement + : '{' block '}' + | returnStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatement + | structDeclaration + | expressionStatement + ; + + +returnStatement : 'return' expression ';' ; + +ifStatement : 'if' '(' expression ')' statement ('else' statement)? ; + +whileStatement : 'while' '(' expression ')' statement ; + +breakStatement : 'break' ';' ; + +continueStatement : 'continue' ';' ; + + +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/14-grammar.md b/docs/chapter14/14-grammar.md new file mode 100644 index 00000000..a5258925 --- /dev/null +++ b/docs/chapter14/14-grammar.md @@ -0,0 +1,124 @@ +# Grammar for Chapter 14 + +English | [日本語](14-grammar.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program : block EOF ; + +block : statement+ ; + + +statement + : '{' block '}' + | returnStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatement + | structDeclaration + | expressionStatement + ; + + +returnStatement : 'return' expression ';' ; + +ifStatement : 'if' '(' expression ')' statement ('else' statement)? ; + +whileStatement : 'while' '(' expression ')' statement ; + +breakStatement : 'break' ';' ; + +continueStatement : 'continue' ';' ; + + +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.ja.md b/docs/chapter14/README.ja.md new file mode 100644 index 00000000..eea61136 --- /dev/null +++ b/docs/chapter14/README.ja.md @@ -0,0 +1,407 @@ +# 第14章: 数値型 + +[English](README.md) | 日本語 + +[前: 第13章](../chapter13/README.ja.md) | +[次: 第15章](../chapter15/README.ja.md) + +この文書は [原文](README.md) の日本語訳です。 + +# 目次 + +1. [浮動小数点演算](#浮動小数点演算) +2. [狭いワード型](#狭い型とサブワード型) +3. [オーバーフローの処理](#オーバーフローの処理) +4. [整数の範囲](#整数の範囲) +5. [ビット演算](#ビット演算) +6. [優先順位](#優先順位) +7. [型の束](#型の実装) + +構造体、参照フィールド、スケジューリングがそろったので、この章では、それらが運ぶ数値を拡張します。浮動小数点演算、狭い整数型と浮動小数点型、整数の範囲を追加します。 + +[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチの線形の Git リビジョン履歴で[この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter14)を読むことや、前章との[差分](https://github.com/SeaOfNodes/Simple/compare/linear-chapter13...linear-chapter14)を見ることもできます。 + +## 浮動小数点演算 + +浮動小数点値は `flt` 型から始まり、IEEE754 の64ビット演算を行います。整数式は、浮動小数点式に含まれると自動的に浮動小数点へ拡張されます。 + +```java +flt f = 0.5; +int x = 2; +f = f+x; // Auto-widen x to 2.0, result is 2.5 +f = f+true; // Since bools are just synonyms for integers 0,1 they auto-widen also +``` + +今のところ、逆に `flt` を丸めて `int` に戻す方法はありません。 + +```java +int x = 3.14; // error +``` + +平方根を計算するニュートン法を示します。 + +```java +flt guess = arg; // Initial guess is just argument +while( true ) { + // Next guess from Newton's method + flt next = (arg/guess + guess)/2; + // Break if hit fixed point + if( next == guess ) break; + guess = next; +} +return guess; +``` + +引数 2 で実行すると 1.414213562373095 を生成します。 + +浮動小数点演算には専用の Node があります。 + +| ノード | 演算 | +|---|---| +| AddF, SubF, MulF, DivF | 基本的な二項浮動小数点演算 | +| MinusF | 単項の符号反転 | +| EQF, LTF, LEF | 浮動小数点の比較演算子 | + +パーサーは [`Node.widen()`](../../src/main/java/com/seaofnodes/simple/node/Node.java) を使って浮動小数点演算を選び、`ToFloatNode` による変換を挿入します。浮動小数点の束は、範囲導入前の整数の束のように、`TOP` と `BOT` の間に定数を持ちます。[`TypeFloat`](../../src/main/java/com/seaofnodes/simple/type/TypeFloat.java) は、値が `f32` に収まるかどうかも記録します。`f32` への代入では、その精度に丸めます。浮動小数点から整数への変換は、別の未実装の言語機能として残ります。 + +## 狭い型とサブワード型 + +狭い整数型、またはサブワード整数型とは、システムやプログラミング言語が提供する標準的な「全幅」（通常32または64ビット）の整数型よりも、使用するメモリ（ビット数）が少ない整数データ型のことです。 + +配列、特にあらゆるネットワークコードでよく使うバイト配列の前段階として、Simple にはサブワード整数型を操作する方法が必要です。整数と浮動小数点の演算は、常に64ビットで計算しますが、変数やフィールドへの代入時には切り詰め（丸め）、ロード時には（符号）拡張します。 + +```java +i8 x = 123456789; +if( x != 21 ) + return false; +return true; +``` + +変数 `x` は符号付き8ビットに制限されます。非常に大きい値 `123456789`（16進数では `0x75BCD15`）を代入すると、単に8ビットに切り詰めて `21 (0x15)` になります。ロード時には符号拡張されます。 + +```java +i16 x = 123456789; +if( x != -13035 ) + return false; +return true; +``` + +変数 `x` は符号付き16ビットに制限されます。非常に大きい値 `0x75BCD15` を代入すると、単に16ビットに切り詰めて `0xCD15` になります。ロード時には符号拡張され、`-13035 (0xFFFF FFFF FFFF CD15)` になります。 + +```java +u16 x = 123456789; +if( x != 52501 ) + return false; +return true; +``` + +変数 `x` は符号なし16ビットに制限されます。非常に大きい値 `0x75BCD15` を代入すると、単に16ビットに切り詰めて `0xCD15` になります。ロード時にはゼロ拡張され、`52501 (0x0000 0000 0000 CD15)` になります。 + +同様に、浮動小数点数を IEEE754 の標準32ビット形式に制限できます。代入時には丸め、ロード時には64ビットに拡張します。 + +これでプリミティブ型の完全な一覧は次のようになります。 + +| データ型 | サイズ（ビット） | 説明 | +|---|---|---| +| `int`, `i64` | 64 | 現代のハードウェアに対応する64ビット符号付き整数。 | +| `u64` | 64 | **未実装**。64ビットを超える振る舞いを示唆します。 | +| `i32` | 32 | 32ビット符号付き整数。ロード時に符号拡張。 | +| `u32` | 32 | 32ビット符号なし整数。ロード時にゼロ拡張。 | +| `i16` | 16 | 16ビット符号付き整数。ロード時に符号拡張。 | +| `u16` | 16 | 16ビット符号なし整数。ロード時にゼロ拡張。 | +| `i8` | 8 | 8ビット符号付き整数。ロード時に符号拡張。 | +| `u8` | 8 | 8ビット符号なし整数。ロード時にゼロ拡張。 | +| `i1` | 1 | 1ビット符号付き整数。ロード時に符号拡張。 | +| `u1` | 1 | 1ビット符号なし整数。ロード時にゼロ拡張。 | +| `bool` | 1 | `u1` の別名。 | +| `flt`, `f64` | 64 | IEEE 754 の64ビット浮動小数点数。一般に double と呼ばれます。 | +| `f32` | 32 | IEEE 754 の32ビット浮動小数点数。 | + +## オーバーフローの処理 + +整数変数が保持できる最大値より大きな値を、その変数に格納しようとすると整数オーバーフローが起きます。オーバーフローにはいくつかの場合があります。 + +#### 符号なし（固定幅）整数のオーバーフロー + +```java +u8 a = 255; +u8 b = a + 1; // match u8 type against expr.type +// a = 256 +// u8 = [0...255] +return b; +``` + +式の型は、指定した型に一致しません。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); +} +``` + +符号なしなので、指定した型からあふれる新しい値にビットマスクをかけるだけです。「ビットごとの AND」のオペランドは、値（256）とマスク（255、上限）です。これを切り詰めと呼びます。 + +`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(); +} +``` + +切り詰めは `AndNode` が行います。 + +```java +... +if( t0._min==0 ) // Unsigned + return new AndNode(val,con(t0._max)).peephole(); +``` + +これらは定数なので、peephole を呼ぶと `256 & 255` = 0 になります。出力は次の通りです。 + +``` +return 0; +``` + +#### 最大整数のオーバーフロー + +```java +i64 a = 9223372036854775807; +i64 b = a + 1; +return b; +``` + +加算の計算時には、オーバーフローしないことを確認します。 + +`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); +``` + +ここで **x + y** はオーバーフローして**負**になり、x ^ 負の値 = 負の値になります。負の数はすべて 0 より小さいので、true を返します。**オーバーフロー**する場合、TypeInteger のボトム型を返すだけです。 + +``` + return TypeInteger.BOT; // [] +``` + +ただし、この例では定数を扱っているので、ここではそのまま自然にオーバーフローさせます。 + +```java +// i1: 9223372036854775807 +// i2: 1 +// i1 + i2 will overflow. +return TypeInteger.constant(i1.value()+i2.value()); // -9223372036854775808; +``` + +#### 定数の範囲の加算 + +```java +u8 a = 12; +u8 b = 13; +u8 c = 124; +u8 d = a + b + c; +return d; +``` + +`is_con` が true なら、一般に `min = max` と言えます。したがって次のようになります。 + +```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)); +``` + +- この結果は次の通りです。 + +```java +return make(con, con); +``` + +`value()` は定数に対してだけ呼ばれます。つまり `_min == _max;` という不変条件が成り立つため、`min_` と `max_` は等しく、どちらを返してもかまいません。 + +これは通常の加算と同じです。 + +```java +public long value() { assert isConstant(); return _min; } +``` + +#### さらに切り詰める + +```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 +``` + +前と同じく、**arg** は **(arg&255)** になります。このノードを **GVN** テーブルに挿入し、**b** はその値を取得します。AddNode のピープホール最適化はこれらを `((arg&255)*2)` に変え、式に追加のマスクをかけて有効な境界内に保ちます。 + +## 整数の範囲 + +一般的な範囲の計算については、Hacker's Delight を参照してください。[^1] + +## ビット演算 + +次のビット演算子をサポートします。 +AND `&`、OR `|`、XOR `^`、左シフト `<<`、右シフト `>>`、ゼロ埋め右シフト `>>>` + +| 演算子 | 記号 | 説明 | +|---|---|---| +| **AND** | `&` | ビットごとの AND 演算。 | +| **OR** | `\|` | ビットごとの OR（包含的論理和）演算。 | +| **XOR** | `^` | ビットごとの XOR（排他的論理和）演算。 | +| **左シフト** | `<<` | ビットを左にずらし、ゼロで埋めます。 | +| **右シフト** | `>>` | ビットを右にずらし、空いた位置に符号ビットの値を複製して埋めます。 | +| **符号なし右シフト** | `>>>` | ビットを右にずらし、空いた位置を常にゼロで埋めます。 | + +`>>>` は算術シフトではなく論理シフトです。 + +これらの論理演算のピープホール最適化の例を示します。 + +#### 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; + +``` + +#### 右シフト + +lhs >> 0 = lhs; + +```java +// Sar of 0. +if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 ) + return lhs; +``` + +#### 左シフト + +lhs << 0 = lhs; + +```java +// Shl of 0. +if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 ) + return lhs; + +``` + +#### 符号なし右シフト + +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; + +``` + +### 優先順位 + +ビット演算子の優先順位は最も低くなります。たとえば次のようになります。 + +``` +arg + 123 & 3 = (arg + 123) & 3 +``` + +## 型の実装 + +の `TypeInteger` クラスを作り直し、min/max 値のあらゆる範囲をサポートします。今のところ、プログラマーに公開するのはサイズが2のべき乗になる一部の範囲だけですが、最適化器の内部ではすべての範囲をサポートします。MEET 操作は最小値の最小と最大値の最大を取ります。DUAL 操作は最小値と最大値を入れ替えます。 + +例: 定数 `0` は `[0...0]` です。 + +例: `bool` 型は範囲 `[0...1]` を持ちます。 + +例: `u8` 型は範囲 `[0...255]` を持ちます。 + +例: `i8` 型は範囲 `[-128...127]` を持ちます。 + +例: `bool` の `dual` は `[1...0]` です（最小値と最大値を交換するだけです）。 + +ここで導入するの `TypeFloat` クラスは、32ビットと64ビットの両方のサイズをサポートします。 + +整数範囲の図は模式図で、取り得る範囲の例としてブール値の範囲とその双対を示しています。ほかの領域は、前の章の名前付き構造体、null 許容ポインタ、精密なメモリエイリアスを維持します。 + + + +### meet: + +2つの範囲の Meet は次の通りです。 + +```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)); +} +``` + +これによって、どちらかの範囲内に起こり得るすべての値を組み合わせます。また、実装もごく単純です。 + +[^1]: Hacker's delight. + 4-2 Propagating Bounds through Adds and Subtracts + +次の章では、これらの数値型を配列の長さ、添字、バイト配列を含む要素の格納に使います。 diff --git a/docs/chapter14/README.md b/docs/chapter14/README.md new file mode 100644 index 00000000..e22b1138 --- /dev/null +++ b/docs/chapter14/README.md @@ -0,0 +1,418 @@ +# Chapter 14: Numeric Types + +English | [日本語](README.ja.md) + +[Previous: Chapter 13](../chapter13/README.md) | +[Next: Chapter 15](../chapter15/README.md) + +# Table of Contents + +1. [Floating-point arithmetic](#floating-point-arithmetic) +2. [Narrow Word Types](#narrow-or-sub-word-types) +3. [Overflow handling](#overflow-handling) +4. [Integer ranges](#integer-ranges) +5. [Bitwise operations](#bitwise-operations) +6. [Precedence](#precedence) +7. [Type lattice](#type-implementation) + + +With structs, reference fields, and scheduling in place, this chapter extends +the numeric values they carry. We add floating-point arithmetic, narrow +integer and float types, and integer ranges. + +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. + +## Floating-point arithmetic + +Floating point values start with the `flt` type and compute IEEE754 64-bit arithmetic. +Integer expressions auto-widen to floats when involved in a float expression. + +```java +flt f = 0.5; +int x = 2; +f = f+x; // Auto-widen x to 2.0, result is 2.5 +f = f+true; // Since bools are just synonyms for integers 0,1 they auto-widen also +``` + +Assigning a float to an integer truncates toward zero: +```java +int rounded = 17.3/2.5; // 6 +rounded = -17.3/2.5; // -6 +``` +This applies to variable initialization, reassignment, and stores to integer +fields or array elements. Conversion first produces a signed 64-bit integer: +NaN becomes zero, and values outside the range (including infinities) clamp to +the nearest limit. Narrow integer destinations then apply the same bit +truncation and sign/zero extension as integer-to-integer assignments. + +Here is Newton's method for computing a square root: +```java +flt guess = arg; // Initial guess is just argument +while( true ) { + // Next guess from Newton's method + flt next = (arg/guess + guess)/2; + // Break if hit fixed point + if( next == guess ) break; + guess = next; +} +return guess; +``` +When run with argument 2, produces 1.414213562373095. + +Floating point operations have their own Nodes: + +| Node | Op | +|------------------------|----------------------| +| AddF, SubF, MulF, DivF | Basic binary FP ops | +| MinusF | Unary negate | +| EQF, LTF, LEF | FP compare operators | +| ToFloat, ToInteger | Numeric conversions | +| RoundF32 | Round to f32 precision | + +The parser uses [`Node.widen()`](../../src/main/java/com/seaofnodes/simple/node/Node.java) +to choose the floating-point operation and insert `ToFloatNode` conversions. +The float lattice has constants between `TOP` and `BOT`, like the integer +lattice before ranges. [`TypeFloat`](../../src/main/java/com/seaofnodes/simple/type/TypeFloat.java) +also records whether a value fits `f32`; assigning to `f32` rounds it to that +precision. `ToIntegerNode` performs the inverse numeric conversion on assignment +to an integer destination, folding constants with the same rules as runtime +conversion. + + +## Narrow or sub-word types + +Narrow or sub-word 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 very 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 very 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 very 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 turns 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;` invariant 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; } +``` + +#### More Truncate + +```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 + +For general range math, visit Hackers Delight:[^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 positions are filled by replicating the value of the sign bit. | +| **Unsigned Right Shift** | `>>>` | Shifts bits to the right, any vacated bit positions are always filled with zero | + +Note `>>>` is a logical shift and not an arithmetic shift. + +Here is a sample of peephole opts on these logical operations: + +#### 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  `TypeInteger` 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  `TypeFloat` class introduced here supports +both 32-bit and 64-bit sizes. + +The integer range diagram is schematic: it shows the boolean range and its +dual as examples among the possible ranges. The other domains retain the +named structs, nullable pointers, and precise memory aliases from earlier chapters. + + + +### meet: + +The 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)); +} +``` + +This combines all values that could possibly occur within either range. +Also, the implementation is trivial. + + + +[^1]: Hacker's delight. + 4-2 Propagating Bounds through Adds and Subtracts + +The next chapter uses these numeric types for array lengths, indexing, and +element storage, including byte arrays. diff --git a/docs/chapter14/lattice.gv b/docs/chapter14/lattice.gv new file mode 100644 index 00000000..5fd97a52 --- /dev/null +++ b/docs/chapter14/lattice.gv @@ -0,0 +1,178 @@ +digraph Lattice { + rankdir=TB; + newrank=true; + // Preserve the same-rank ordering edges through cluster layout. + remincross=false; + nodesep=0.22; + ranksep=0.65; + node [shape=ellipse, style=filled, fontname="DejaVu Sans", fontsize=13]; + edge [color="#555555", arrowsize=0.6]; + + // These arrows are lattice-order edges, not use/definition edges. + TOP [label="⊤", fillcolor=black, fontcolor=white]; + BOT [label="⊥", fillcolor=black, fontcolor=white]; + + subgraph cluster_control { + label="Control"; fontname="Arial"; color="#cccccc"; + node [fillcolor="#ffff00"]; + XCTRL [label="⊤:ctrl"]; + CTRL [label="⊥:ctrl"]; + XCTRL -> CTRL; + } + + subgraph cluster_integer { + label="Integer ranges (schematic)"; fontname="Arial"; color="#cccccc"; + 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]; + + 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_CON0 -> INT_CON1 -> INT_CON [style=invis]; + + {rank=same; INT_CON0; INT_CON1; INT_CON;} + } + + subgraph cluster_float { + label="Float"; fontname="Arial"; color="#cccccc"; + 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]; + + 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_CON0 -> FLT_CON32 -> FLT_CONPI -> FLT_CON64 [style=invis]; + + + {rank=same; FLT_CON0; FLT_CON32; FLT_CONPI; FLT_CON64;} + } + + subgraph cluster_pointer { + label="Pointer = nullability × struct type"; + fontname="Arial"; color="#cccccc"; + node [fillcolor="#008000", fontcolor=white]; + PTR_TOP [label="⊤:ptr\n[*⊤:struct]"]; + PTR_BOT [label="⊥:ptr\n[*⊥:struct?]"]; + PTR_NULL [label="null"]; + PTR_ANY [label="*⊥:struct\n[ptr any struct]"]; + PTR_PERSON [label="*Person"]; + PTR_S1 [label="*s1"]; + PTR_MORE [label="*s2, …"]; + PTR_PERSON_NIL [label="*Person?"]; + PTR_S1_NIL [label="*s1?"]; + PTR_MORE_NIL [label="*s2?, …"]; + {rank=same; PTR_PERSON; PTR_S1; PTR_MORE; PTR_NULL;} + {rank=same; PTR_ANY; PTR_PERSON_NIL; PTR_S1_NIL; PTR_MORE_NIL;} + PTR_PERSON -> PTR_S1 -> PTR_MORE -> PTR_NULL [style=invis]; + PTR_ANY -> PTR_PERSON_NIL -> PTR_S1_NIL -> PTR_MORE_NIL [style=invis]; + PTR_TOP -> {PTR_PERSON PTR_S1 PTR_MORE PTR_NULL}; + {PTR_PERSON PTR_S1 PTR_MORE} -> PTR_ANY; + PTR_PERSON -> PTR_PERSON_NIL; + PTR_S1 -> PTR_S1_NIL; + PTR_MORE -> PTR_MORE_NIL; + PTR_NULL -> {PTR_PERSON_NIL PTR_S1_NIL PTR_MORE_NIL}; + {PTR_ANY PTR_PERSON_NIL PTR_S1_NIL PTR_MORE_NIL} -> PTR_BOT; + } + + subgraph cluster_struct { + label="Struct\nnamed collection of named scalar types"; + fontname="Arial"; color="#cccccc"; + node [fillcolor="#90ee90"]; + STRUCT_TOP [label="⊤:struct\n[struct top]"]; + STRUCT_BOT [label="⊥:struct\n[struct bottom]"]; + STRUCT_PERSON [label="Person\nage: int", shape=box]; + STRUCT_S1 [label="s1\nx: int", shape=box]; + STRUCT_S2 [label="s2\nx: int, y: *s1", shape=box]; + STRUCT_MORE [label="…", shape=box]; + {rank=same; STRUCT_PERSON; STRUCT_S1; STRUCT_S2; STRUCT_MORE;} + STRUCT_PERSON -> STRUCT_S1 -> STRUCT_S2 -> STRUCT_MORE [style=invis]; + STRUCT_TOP -> {STRUCT_PERSON STRUCT_S1 STRUCT_S2 STRUCT_MORE}; + {STRUCT_PERSON STRUCT_S1 STRUCT_S2 STRUCT_MORE} -> STRUCT_BOT; + } + + subgraph cluster_memory { + label="Memory\nprecise alias slices"; fontname="Arial"; color="#cccccc"; + node [fillcolor="#00008b", fontcolor=white]; + MEM_TOP [label="⊤:mem"]; + MEM_BOT [label="⊥:mem"]; + MEM_ALIAS2 [label="MEM#2"]; + MEM_ALIAS3 [label="MEM#3"]; + MEM_MORE [label="…"]; + {rank=same; MEM_ALIAS2; MEM_ALIAS3; MEM_MORE;} + MEM_ALIAS2 -> MEM_ALIAS3 -> MEM_MORE [style=invis]; + MEM_TOP -> {MEM_ALIAS2 MEM_ALIAS3 MEM_MORE}; + {MEM_ALIAS2 MEM_ALIAS3 MEM_MORE} -> MEM_BOT; + } + + subgraph cluster_tuple { + label="Tuple\ncollection of types"; + fontname="Arial"; color="#cccccc"; + node [fillcolor="#ffc0cb"]; + TUPLE_TOP [label="⊤:tuple"]; + TUPLE_BOT [label="⊥:tuple"]; + // Each black element stands for a recursively nested type lattice. + TUPLE1 [shape=plain, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="#ffc0cb">tuple</TD></TR> + <TR><TD BGCOLOR="black"><FONT COLOR="white">type</FONT></TD></TR> + </TABLE> + >]; + TUPLE2 [shape=plain, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="#ffc0cb">tuple</TD></TR> + <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=plain, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="#ffc0cb">tuple</TD></TR> + <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> + >]; + {rank=same; TUPLE1; TUPLE2; TUPLEN;} + TUPLE1 -> TUPLE2 -> TUPLEN [style=invis]; + TUPLE_TOP -> {TUPLE1 TUPLE2 TUPLEN}; + {TUPLE1 TUPLE2 TUPLEN} -> TUPLE_BOT; + } + + TOP -> {XCTRL INT_TOP FLT_TOP PTR_TOP STRUCT_TOP MEM_TOP TUPLE_TOP}; + {CTRL INT_BOT FLT_BOT PTR_BOT STRUCT_BOT MEM_BOT TUPLE_BOT} -> BOT; + {rank=same; XCTRL; INT_TOP; FLT_TOP; PTR_TOP; STRUCT_TOP; MEM_TOP; TUPLE_TOP;} + {rank=same; CTRL; INT_BOT; FLT_BOT; PTR_BOT; STRUCT_BOT; MEM_BOT; TUPLE_BOT;} + XCTRL -> INT_TOP -> FLT_TOP -> PTR_TOP -> STRUCT_TOP -> MEM_TOP -> TUPLE_TOP [style=invis]; +} diff --git a/docs/chapter14/lattice.svg b/docs/chapter14/lattice.svg new file mode 100644 index 00000000..9db77f7a --- /dev/null +++ b/docs/chapter14/lattice.svg @@ -0,0 +1,827 @@ +<?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="2191pt" height="881pt" + viewBox="0.00 0.00 2191.00 880.78" 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 876.78)"> +<title>Lattice</title> +<polygon fill="white" stroke="none" points="-4,4 -4,-876.78 2187,-876.78 2187,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_control</title> +<polygon fill="none" stroke="#cccccc" points="8,-85.99 8,-802.04 98,-802.04 98,-85.99 8,-85.99"/> +<text text-anchor="middle" x="53" y="-784.74" font-family="Arial" font-size="14.00">Control</text> +</g> +<g id="clust2" class="cluster"> +<title>cluster_integer</title> +<polygon fill="none" stroke="#cccccc" points="106,-85.99 106,-802.04 372,-802.04 372,-85.99 106,-85.99"/> +<text text-anchor="middle" x="239" y="-784.74" font-family="Arial" font-size="14.00">Integer ranges (schematic)</text> +</g> +<g id="clust4" class="cluster"> +<title>cluster_float</title> +<polygon fill="none" stroke="#cccccc" points="380,-85.99 380,-802.04 864,-802.04 864,-85.99 380,-85.99"/> +<text text-anchor="middle" x="622" y="-784.74" font-family="Arial" font-size="14.00">Float</text> +</g> +<g id="clust6" class="cluster"> +<title>cluster_pointer</title> +<polygon fill="none" stroke="#cccccc" points="872,-75 872,-813.03 1353,-813.03 1353,-75 872,-75"/> +<text text-anchor="middle" x="1112.5" y="-795.73" font-family="Arial" font-size="14.00">Pointer = nullability × struct type</text> +</g> +<g id="clust13" class="cluster"> +<title>cluster_struct</title> +<polygon fill="none" stroke="#cccccc" points="1361,-75 1361,-828.78 1697,-828.78 1697,-75 1361,-75"/> +<text text-anchor="middle" x="1529" y="-811.48" font-family="Arial" font-size="14.00">Struct</text> +<text text-anchor="middle" x="1529" y="-795.73" font-family="Arial" font-size="14.00">named collection of named scalar types</text> +</g> +<g id="clust17" class="cluster"> +<title>cluster_memory</title> +<polygon fill="none" stroke="#cccccc" points="1705,-85.99 1705,-817.79 1987,-817.79 1987,-85.99 1705,-85.99"/> +<text text-anchor="middle" x="1846" y="-800.49" font-family="Arial" font-size="14.00">Memory</text> +<text text-anchor="middle" x="1846" y="-784.74" font-family="Arial" font-size="14.00">precise alias slices</text> +</g> +<g id="clust21" class="cluster"> +<title>cluster_tuple</title> +<polygon fill="none" stroke="#cccccc" points="1995,-85.99 1995,-817.79 2175,-817.79 2175,-85.99 1995,-85.99"/> +<text text-anchor="middle" x="2085" y="-800.49" font-family="Arial" font-size="14.00">Tuple</text> +<text text-anchor="middle" x="2085" y="-784.74" font-family="Arial" font-size="14.00">collection of types</text> +</g> +<!-- TOP --> +<g id="node1" class="node"> +<title>TOP</title> +<ellipse fill="black" stroke="black" cx="1093" cy="-854.78" rx="27" ry="18"/> +<text text-anchor="middle" x="1093" y="-850.68" font-family="DejaVu Sans" font-size="13.00" fill="white">⊤</text> +</g> +<!-- XCTRL --> +<g id="node3" class="node"> +<title>XCTRL</title> +<ellipse fill="#ffff00" stroke="black" cx="53" cy="-752.29" rx="36.51" ry="18"/> +<text text-anchor="middle" x="53" y="-748.19" font-family="DejaVu Sans" font-size="13.00">⊤:ctrl</text> +</g> +<!-- TOP->XCTRL --> +<g id="edge77" class="edge"> +<title>TOP->XCTRL</title> +<path fill="none" stroke="#555555" d="M1065.75,-853.81C910.7,-853.87 145.18,-852.94 102,-828.78 82.14,-817.67 69.01,-794.76 61.39,-777.08"/> +<polygon fill="#555555" stroke="#555555" points="63.43,-776.52 59.22,-771.76 59.54,-778.1 63.43,-776.52"/> +</g> +<!-- INT_TOP --> +<g id="node5" class="node"> +<title>INT_TOP</title> +<ellipse fill="lightblue" stroke="black" cx="330" cy="-752.29" rx="33.95" ry="18"/> +<text text-anchor="start" x="313.12" y="-749.19" font-family="DejaVu Sans" font-weight="bold" font-size="13.00">⊤</text> +<text text-anchor="start" x="325.12" y="-749.19" font-family="DejaVu Sans" font-size="13.00">:int</text> +</g> +<!-- TOP->INT_TOP --> +<g id="edge78" class="edge"> +<title>TOP->INT_TOP</title> +<path fill="none" stroke="#555555" d="M1065.76,-853.55C938.37,-852.39 406.27,-846.49 376,-828.78 356.7,-817.5 344.47,-794.61 337.51,-776.98"/> +<polygon fill="#555555" stroke="#555555" points="339.61,-776.59 335.55,-771.7 335.67,-778.05 339.61,-776.59"/> +</g> +<!-- FLT_TOP --> +<g id="node14" class="node"> +<title>FLT_TOP</title> +<ellipse fill="aqua" stroke="black" cx="720" cy="-752.29" rx="31.39" ry="18"/> +<text text-anchor="start" x="705" y="-749.19" font-family="DejaVu Sans" font-weight="bold" font-size="13.00">⊤</text> +<text text-anchor="start" x="717" y="-749.19" font-family="DejaVu Sans" font-size="13.00">:flt</text> +</g> +<!-- TOP->FLT_TOP --> +<g id="edge79" class="edge"> +<title>TOP->FLT_TOP</title> +<path fill="none" stroke="#555555" d="M1065.71,-853.88C1022.73,-853.35 937.09,-849.49 868,-828.78 822.79,-815.23 774.91,-788.16 746.24,-770.39"/> +<polygon fill="#555555" stroke="#555555" points="747.56,-768.74 741.36,-767.33 745.33,-772.3 747.56,-768.74"/> +</g> +<!-- PTR_TOP --> +<g id="node22" class="node"> +<title>PTR_TOP</title> +<ellipse fill="#008000" stroke="black" cx="1093" cy="-752.29" rx="61.7" ry="28.99"/> +<text text-anchor="middle" x="1093" y="-756.44" font-family="DejaVu Sans" font-size="13.00" fill="white">⊤:ptr</text> +<text text-anchor="middle" x="1093" y="-739.94" font-family="DejaVu Sans" font-size="13.00" fill="white">[*⊤:struct]</text> +</g> +<!-- TOP->PTR_TOP --> +<g id="edge80" class="edge"> +<title>TOP->PTR_TOP</title> +<path fill="none" stroke="#555555" d="M1093,-836.74C1093,-823.62 1093,-805.05 1093,-788.76"/> +<polygon fill="#555555" stroke="#555555" points="1095.1,-788.97 1093,-782.97 1090.9,-788.97 1095.1,-788.97"/> +</g> +<!-- STRUCT_TOP --> +<g id="node32" class="node"> +<title>STRUCT_TOP</title> +<ellipse fill="#90ee90" stroke="black" cx="1480" cy="-752.29" rx="64.35" ry="28.99"/> +<text text-anchor="middle" x="1480" y="-756.44" font-family="DejaVu Sans" font-size="13.00">⊤:struct</text> +<text text-anchor="middle" x="1480" y="-739.94" font-family="DejaVu Sans" font-size="13.00">[struct top]</text> +</g> +<!-- TOP->STRUCT_TOP --> +<g id="edge81" class="edge"> +<title>TOP->STRUCT_TOP</title> +<path fill="none" stroke="#555555" d="M1119.97,-852.78C1178.13,-850.35 1313.55,-843.3 1357,-828.78 1388.2,-818.36 1419.74,-798.78 1443.07,-782.17"/> +<polygon fill="#555555" stroke="#555555" points="1444.26,-783.9 1447.9,-778.68 1441.8,-780.49 1444.26,-783.9"/> +</g> +<!-- MEM_TOP --> +<g id="node38" class="node"> +<title>MEM_TOP</title> +<ellipse fill="#00008b" stroke="black" cx="1807" cy="-752.29" rx="44.7" ry="18"/> +<text text-anchor="middle" x="1807" y="-748.19" font-family="DejaVu Sans" font-size="13.00" fill="white">⊤:mem</text> +</g> +<!-- TOP->MEM_TOP --> +<g id="edge82" class="edge"> +<title>TOP->MEM_TOP</title> +<path fill="none" stroke="#555555" d="M1120.14,-853.58C1230.92,-852.61 1645.66,-847.74 1701,-828.78 1734.02,-817.47 1765.78,-792.33 1785.79,-774.16"/> +<polygon fill="#555555" stroke="#555555" points="1787.02,-775.88 1790,-770.26 1784.17,-772.8 1787.02,-775.88"/> +</g> +<!-- TUPLE_TOP --> +<g id="node43" class="node"> +<title>TUPLE_TOP</title> +<ellipse fill="#ffc0cb" stroke="black" cx="2048" cy="-752.29" rx="44.7" ry="18"/> +<text text-anchor="middle" x="2048" y="-748.19" font-family="DejaVu Sans" font-size="13.00">⊤:tuple</text> +</g> +<!-- TOP->TUPLE_TOP --> +<g id="edge83" class="edge"> +<title>TOP->TUPLE_TOP</title> +<path fill="none" stroke="#555555" d="M1120.01,-853.69C1265.56,-853.09 1951.36,-849.22 1991,-828.78 2012.45,-817.73 2028.06,-794.49 2037.46,-776.7"/> +<polygon fill="#555555" stroke="#555555" points="2039.12,-778.07 2039.96,-771.77 2035.37,-776.17 2039.12,-778.07"/> +</g> +<!-- BOT --> +<g id="node2" class="node"> +<title>BOT</title> +<ellipse fill="black" stroke="black" cx="1158" cy="-18" rx="27" ry="18"/> +<text text-anchor="middle" x="1158" y="-13.9" font-family="DejaVu Sans" font-size="13.00" fill="white">⊥</text> +</g> +<!-- CTRL --> +<g id="node4" class="node"> +<title>CTRL</title> +<ellipse fill="#ffff00" stroke="black" cx="53" cy="-111.99" rx="36.51" ry="18"/> +<text text-anchor="middle" x="53" y="-107.89" font-family="DejaVu Sans" font-size="13.00">⊥:ctrl</text> +</g> +<!-- XCTRL->CTRL --> +<g id="edge1" class="edge"> +<title>XCTRL->CTRL</title> +<path fill="none" stroke="#555555" d="M53,-733.84C53,-699.39 53,-620.21 53,-553.64 53,-553.64 53,-553.64 53,-292.98 53,-237.49 53,-172.38 53,-137.7"/> +<polygon fill="#555555" stroke="#555555" points="55.1,-137.88 53,-131.88 50.9,-137.88 55.1,-137.88"/> +</g> +<!-- XCTRL->INT_TOP --> +<!-- CTRL->BOT --> +<g id="edge84" class="edge"> +<title>CTRL->BOT</title> +<path fill="none" stroke="#555555" d="M68.82,-95.67C77.79,-87.99 89.68,-79.4 102,-75 199.9,-40.01 951.33,-23.1 1123.11,-19.66"/> +<polygon fill="#555555" stroke="#555555" points="1123.14,-21.76 1129.1,-19.55 1123.06,-17.57 1123.14,-21.76"/> +</g> +<!-- INT_HI --> +<g id="node7" class="node"> +<title>INT_HI</title> +<ellipse fill="lightblue" stroke="black" cx="303" cy="-658.3" rx="61.08" ry="18"/> +<text text-anchor="middle" x="303" y="-654.2" font-family="DejaVu Sans" font-size="13.00">max < min</text> +</g> +<!-- INT_TOP->INT_HI --> +<g id="edge2" class="edge"> +<title>INT_TOP->INT_HI</title> +<path fill="none" stroke="#555555" d="M325.05,-734.42C320.88,-720.2 314.85,-699.69 310.16,-683.69"/> +<polygon fill="#555555" stroke="#555555" points="312.24,-683.31 308.53,-678.14 308.21,-684.49 312.24,-683.31"/> +</g> +<!-- INT_TOP->FLT_TOP --> +<!-- INT_BOT --> +<g id="node6" class="node"> +<title>INT_BOT</title> +<ellipse fill="lightblue" stroke="black" cx="316" cy="-111.99" rx="33.95" ry="18"/> +<text text-anchor="start" x="299.12" y="-108.89" font-family="DejaVu Sans" font-weight="bold" font-size="13.00">⊥</text> +<text text-anchor="start" x="311.12" y="-108.89" font-family="DejaVu Sans" font-size="13.00">:int</text> +</g> +<!-- INT_BOT->BOT --> +<g id="edge85" class="edge"> +<title>INT_BOT->BOT</title> +<path fill="none" stroke="#555555" d="M334.62,-96.69C345.94,-88.82 361.06,-79.72 376,-75 518.37,-30.04 991.01,-21.01 1123.31,-19.35"/> +<polygon fill="#555555" stroke="#555555" points="1123.32,-21.45 1129.3,-19.28 1123.27,-17.25 1123.32,-21.45"/> +</g> +<!-- INT_XBOOL --> +<g id="node8" class="node"> +<title>INT_XBOOL</title> +<ellipse fill="lightblue" stroke="black" cx="211" cy="-552.64" rx="31.39" ry="18"/> +<text text-anchor="middle" x="211" y="-548.54" font-family="DejaVu Sans" font-size="13.00">1...0</text> +</g> +<!-- INT_HI->INT_XBOOL --> +<g id="edge3" class="edge"> +<title>INT_HI->INT_XBOOL</title> +<path fill="none" stroke="#555555" d="M288.22,-640.65C272.25,-622.65 246.77,-593.94 229.48,-574.47"/> +<polygon fill="#555555" stroke="#555555" points="231.4,-573.46 225.85,-570.37 228.26,-576.25 231.4,-573.46"/> +</g> +<!-- INT_CON --> +<g id="node9" class="node"> +<title>INT_CON</title> +<ellipse fill="lightblue" stroke="black" cx="309" cy="-411.98" rx="54.93" ry="18"/> +<text text-anchor="middle" x="309" y="-407.88" font-family="DejaVu Sans" font-size="13.00">constants</text> +</g> +<!-- INT_HI->INT_CON --> +<g id="edge6" class="edge"> +<title>INT_HI->INT_CON</title> +<path fill="none" stroke="#555555" d="M303.42,-640.12C304.47,-597.64 307.17,-487.54 308.39,-437.9"/> +<polygon fill="#555555" stroke="#555555" points="310.49,-438.03 308.53,-431.98 306.29,-437.93 310.49,-438.03"/> +</g> +<!-- INT_CON0 --> +<g id="node10" class="node"> +<title>INT_CON0</title> +<ellipse fill="lightblue" stroke="black" cx="141" cy="-411.98" rx="27" ry="18"/> +<text text-anchor="middle" x="141" y="-407.88" font-family="DejaVu Sans" font-size="13.00">0</text> +</g> +<!-- INT_XBOOL->INT_CON0 --> +<g id="edge4" class="edge"> +<title>INT_XBOOL->INT_CON0</title> +<path fill="none" stroke="#555555" d="M202.56,-534.92C190.09,-510.21 166.7,-463.9 152.62,-436.01"/> +<polygon fill="#555555" stroke="#555555" points="154.52,-435.1 149.94,-430.69 150.77,-436.99 154.52,-435.1"/> +</g> +<!-- INT_CON1 --> +<g id="node11" class="node"> +<title>INT_CON1</title> +<ellipse fill="lightblue" stroke="black" cx="211" cy="-411.98" rx="27" ry="18"/> +<text text-anchor="middle" x="211" y="-407.88" font-family="DejaVu Sans" font-size="13.00">1</text> +</g> +<!-- INT_XBOOL->INT_CON1 --> +<g id="edge5" class="edge"> +<title>INT_XBOOL->INT_CON1</title> +<path fill="none" stroke="#555555" d="M211,-534.36C211,-510.07 211,-465.7 211,-437.86"/> +<polygon fill="#555555" stroke="#555555" points="213.1,-437.99 211,-431.99 208.9,-437.99 213.1,-437.99"/> +</g> +<!-- INT_LO --> +<g id="node13" class="node"> +<title>INT_LO</title> +<ellipse fill="lightblue" stroke="black" cx="303" cy="-208.48" rx="61.08" ry="18"/> +<text text-anchor="middle" x="303" y="-204.38" font-family="DejaVu Sans" font-size="13.00">max > min</text> +</g> +<!-- INT_CON->INT_LO --> +<g id="edge10" class="edge"> +<title>INT_CON->INT_LO</title> +<path fill="none" stroke="#555555" d="M308.49,-393.8C307.43,-358.13 304.98,-275.9 303.74,-234.4"/> +<polygon fill="#555555" stroke="#555555" points="305.84,-234.35 303.56,-228.42 301.64,-234.48 305.84,-234.35"/> +</g> +<!-- INT_CON0->INT_CON1 --> +<!-- INT_BOOL --> +<g id="node12" class="node"> +<title>INT_BOOL</title> +<ellipse fill="lightblue" stroke="black" cx="211" cy="-293.98" rx="31.39" ry="18"/> +<text text-anchor="middle" x="211" y="-289.88" font-family="DejaVu Sans" font-size="13.00">0...1</text> +</g> +<!-- INT_CON0->INT_BOOL --> +<g id="edge7" class="edge"> +<title>INT_CON0->INT_BOOL</title> +<path fill="none" stroke="#555555" d="M150.73,-394.85C162.84,-374.8 183.57,-340.43 197.28,-317.71"/> +<polygon fill="#555555" stroke="#555555" points="199.04,-318.87 200.34,-312.64 195.44,-316.7 199.04,-318.87"/> +</g> +<!-- INT_CON1->INT_CON --> +<!-- INT_CON1->INT_BOOL --> +<g id="edge8" class="edge"> +<title>INT_CON1->INT_BOOL</title> +<path fill="none" stroke="#555555" d="M211,-393.62C211,-374.05 211,-342.1 211,-319.88"/> +<polygon fill="#555555" stroke="#555555" points="213.1,-319.98 211,-313.98 208.9,-319.98 213.1,-319.98"/> +</g> +<!-- INT_BOOL->INT_LO --> +<g id="edge9" class="edge"> +<title>INT_BOOL->INT_LO</title> +<path fill="none" stroke="#555555" d="M227.03,-278.44C241.55,-265.26 263.13,-245.67 279.59,-230.73"/> +<polygon fill="#555555" stroke="#555555" points="280.8,-232.47 283.83,-226.88 277.98,-229.36 280.8,-232.47"/> +</g> +<!-- INT_LO->INT_BOT --> +<g id="edge11" class="edge"> +<title>INT_LO->INT_BOT</title> +<path fill="none" stroke="#555555" d="M305.38,-190.15C307.42,-175.37 310.37,-153.94 312.64,-137.42"/> +<polygon fill="#555555" stroke="#555555" points="314.69,-137.94 313.42,-131.71 310.53,-137.37 314.69,-137.94"/> +</g> +<!-- FLT_CON64 --> +<g id="node16" class="node"> +<title>FLT_CON64</title> +<ellipse fill="aqua" stroke="black" cx="790" cy="-552.64" rx="65.94" ry="40.66"/> +<text text-anchor="middle" x="790" y="-565.04" font-family="DejaVu Sans" font-size="13.00">64b consts</text> +<text text-anchor="middle" x="790" y="-548.54" font-family="DejaVu Sans" font-size="13.00">[excludes</text> +<text text-anchor="middle" x="790" y="-532.04" font-family="DejaVu Sans" font-size="13.00">32b consts]</text> +</g> +<!-- FLT_TOP->FLT_CON64 --> +<g id="edge14" class="edge"> +<title>FLT_TOP->FLT_CON64</title> +<path fill="none" stroke="#555555" d="M725.97,-734.44C736.43,-704.9 758.41,-642.83 773.68,-599.71"/> +<polygon fill="#555555" stroke="#555555" points="775.64,-600.48 775.66,-594.12 771.68,-599.08 775.64,-600.48"/> +</g> +<!-- FLT_CONPI --> +<g id="node18" class="node"> +<title>FLT_CONPI</title> +<ellipse fill="aqua" stroke="black" cx="651" cy="-552.64" rx="56.98" ry="18"/> +<text text-anchor="middle" x="651" y="-548.54" font-family="DejaVu Sans" font-size="13.00">3.14159...</text> +</g> +<!-- FLT_TOP->FLT_CONPI --> +<g id="edge15" class="edge"> +<title>FLT_TOP->FLT_CONPI</title> +<path fill="none" stroke="#555555" d="M714.12,-734.44C701.88,-699.39 673.65,-618.52 659.46,-577.88"/> +<polygon fill="#555555" stroke="#555555" points="661.52,-577.42 657.56,-572.44 657.56,-578.8 661.52,-577.42"/> +</g> +<!-- FLT_X32 --> +<g id="node19" class="node"> +<title>FLT_X32</title> +<ellipse fill="aqua" stroke="black" cx="518" cy="-658.3" rx="32.93" ry="18"/> +<text text-anchor="middle" x="518" y="-654.2" font-family="DejaVu Sans" font-size="13.00">~f32</text> +</g> +<!-- FLT_TOP->FLT_X32 --> +<g id="edge18" class="edge"> +<title>FLT_TOP->FLT_X32</title> +<path fill="none" stroke="#555555" d="M696.03,-740.38C659.58,-723.78 590.16,-692.16 549.62,-673.7"/> +<polygon fill="#555555" stroke="#555555" points="550.59,-671.83 544.26,-671.26 548.85,-675.66 550.59,-671.83"/> +</g> +<!-- FLT_TOP->PTR_TOP --> +<!-- FLT_BOT --> +<g id="node15" class="node"> +<title>FLT_BOT</title> +<ellipse fill="aqua" stroke="black" cx="720" cy="-111.99" rx="31.39" ry="18"/> +<text text-anchor="start" x="705" y="-108.89" font-family="DejaVu Sans" font-weight="bold" font-size="13.00">⊥</text> +<text text-anchor="start" x="717" y="-108.89" font-family="DejaVu Sans" font-size="13.00">:flt</text> +</g> +<!-- FLT_BOT->BOT --> +<g id="edge86" class="edge"> +<title>FLT_BOT->BOT</title> +<path fill="none" stroke="#555555" d="M748.28,-103.69C778,-96.11 826.14,-84.12 868,-75 960.59,-54.81 1070.63,-34.59 1124.67,-24.9"/> +<polygon fill="#555555" stroke="#555555" points="1124.89,-26.99 1130.43,-23.87 1124.15,-22.86 1124.89,-26.99"/> +</g> +<!-- FLT_CON64->FLT_BOT --> +<g id="edge16" class="edge"> +<title>FLT_CON64->FLT_BOT</title> +<path fill="none" stroke="#555555" d="M783.66,-511.94C769.47,-423.02 735.48,-210 723.92,-137.58"/> +<polygon fill="#555555" stroke="#555555" points="726.01,-137.32 722.99,-131.73 721.86,-137.98 726.01,-137.32"/> +</g> +<!-- FLT_CON32 --> +<g id="node17" class="node"> +<title>FLT_CON32</title> +<ellipse fill="aqua" stroke="black" cx="518" cy="-552.64" rx="60.05" ry="18"/> +<text text-anchor="middle" x="518" y="-548.54" font-family="DejaVu Sans" font-size="13.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="518" cy="-411.98" rx="27" ry="18"/> +<text text-anchor="middle" x="518" y="-407.88" font-family="DejaVu Sans" font-size="13.00">f32</text> +</g> +<!-- FLT_CON32->FLT_32 --> +<g id="edge22" class="edge"> +<title>FLT_CON32->FLT_32</title> +<path fill="none" stroke="#555555" d="M518,-534.36C518,-510.07 518,-465.7 518,-437.86"/> +<polygon fill="#555555" stroke="#555555" points="520.1,-437.99 518,-431.99 515.9,-437.99 520.1,-437.99"/> +</g> +<!-- FLT_CONPI->FLT_BOT --> +<g id="edge17" class="edge"> +<title>FLT_CONPI->FLT_BOT</title> +<path fill="none" stroke="#555555" d="M653.75,-534.18C664.5,-465.79 703.78,-216.13 716.2,-137.13"/> +<polygon fill="#555555" stroke="#555555" points="718.23,-137.78 717.08,-131.53 714.08,-137.13 718.23,-137.78"/> +</g> +<!-- FLT_CONPI->FLT_CON64 --> +<!-- FLT_X32->FLT_CON32 --> +<g id="edge20" class="edge"> +<title>FLT_X32->FLT_CON32</title> +<path fill="none" stroke="#555555" d="M518,-640.18C518,-623.4 518,-597.64 518,-578.58"/> +<polygon fill="#555555" stroke="#555555" points="520.1,-578.64 518,-572.64 515.9,-578.64 520.1,-578.64"/> +</g> +<!-- FLT_CON0 --> +<g id="node20" class="node"> +<title>FLT_CON0</title> +<ellipse fill="aqua" stroke="black" cx="415" cy="-552.64" rx="27" ry="18"/> +<text text-anchor="middle" x="415" y="-548.54" font-family="DejaVu Sans" font-size="13.00">0.</text> +</g> +<!-- FLT_X32->FLT_CON0 --> +<g id="edge19" class="edge"> +<title>FLT_X32->FLT_CON0</title> +<path fill="none" stroke="#555555" d="M501.38,-642.45C487.36,-629.74 466.92,-610.77 450,-593.3 444.13,-587.24 437.97,-580.42 432.47,-574.17"/> +<polygon fill="#555555" stroke="#555555" points="434.16,-572.91 428.64,-569.77 431,-575.67 434.16,-572.91"/> +</g> +<!-- FLT_CON0->FLT_CON32 --> +<!-- FLT_CON0->FLT_32 --> +<g id="edge21" class="edge"> +<title>FLT_CON0->FLT_32</title> +<path fill="none" stroke="#555555" d="M426.62,-536.01C445.1,-511.12 481.26,-462.44 502.13,-434.35"/> +<polygon fill="#555555" stroke="#555555" points="503.79,-435.63 505.68,-429.57 500.42,-433.13 503.79,-435.63"/> +</g> +<!-- FLT_32->FLT_BOT --> +<g id="edge23" class="edge"> +<title>FLT_32->FLT_BOT</title> +<path fill="none" stroke="#555555" d="M528.58,-395.38C562.1,-345.93 666.07,-192.55 705.04,-135.05"/> +<polygon fill="#555555" stroke="#555555" points="706.56,-136.56 708.19,-130.41 703.08,-134.2 706.56,-136.56"/> +</g> +<!-- PTR_NULL --> +<g id="node24" class="node"> +<title>PTR_NULL</title> +<ellipse fill="#008000" stroke="black" cx="1219" cy="-658.3" rx="27.3" ry="18"/> +<text text-anchor="middle" x="1219" y="-654.2" font-family="DejaVu Sans" font-size="13.00" fill="white">null</text> +</g> +<!-- PTR_TOP->PTR_NULL --> +<g id="edge33" class="edge"> +<title>PTR_TOP->PTR_NULL</title> +<path fill="none" stroke="#555555" d="M1125.78,-727.36C1147.49,-711.51 1175.48,-691.07 1195.1,-676.75"/> +<polygon fill="#555555" stroke="#555555" points="1196.33,-678.45 1199.93,-673.22 1193.85,-675.06 1196.33,-678.45"/> +</g> +<!-- PTR_PERSON --> +<g id="node26" class="node"> +<title>PTR_PERSON</title> +<ellipse fill="#008000" stroke="black" cx="962" cy="-658.3" rx="45.72" ry="18"/> +<text text-anchor="middle" x="962" y="-654.2" font-family="DejaVu Sans" font-size="13.00" fill="white">*Person</text> +</g> +<!-- PTR_TOP->PTR_PERSON --> +<g id="edge34" class="edge"> +<title>PTR_TOP->PTR_PERSON</title> +<path fill="none" stroke="#555555" d="M1059.26,-727.6C1037.69,-712.45 1010.05,-693.04 989.76,-678.79"/> +<polygon fill="#555555" stroke="#555555" points="991.06,-677.14 984.95,-675.41 988.65,-680.58 991.06,-677.14"/> +</g> +<!-- PTR_S1 --> +<g id="node27" class="node"> +<title>PTR_S1</title> +<ellipse fill="#008000" stroke="black" cx="1051" cy="-658.3" rx="27" ry="18"/> +<text text-anchor="middle" x="1051" y="-654.2" font-family="DejaVu Sans" font-size="13.00" fill="white">*s1</text> +</g> +<!-- PTR_TOP->PTR_S1 --> +<g id="edge35" class="edge"> +<title>PTR_TOP->PTR_S1</title> +<path fill="none" stroke="#555555" d="M1080.4,-723.69C1074.4,-710.56 1067.32,-695.04 1061.6,-682.53"/> +<polygon fill="#555555" stroke="#555555" points="1063.62,-681.88 1059.22,-677.29 1059.8,-683.62 1063.62,-681.88"/> +</g> +<!-- PTR_MORE --> +<g id="node28" class="node"> +<title>PTR_MORE</title> +<ellipse fill="#008000" stroke="black" cx="1135" cy="-658.3" rx="40.6" ry="18"/> +<text text-anchor="middle" x="1135" y="-654.2" font-family="DejaVu Sans" font-size="13.00" fill="white">*s2, …</text> +</g> +<!-- PTR_TOP->PTR_MORE --> +<g id="edge36" class="edge"> +<title>PTR_TOP->PTR_MORE</title> +<path fill="none" stroke="#555555" d="M1105.6,-723.69C1111.55,-710.65 1118.59,-695.25 1124.28,-682.78"/> +<polygon fill="#555555" stroke="#555555" points="1126.08,-683.9 1126.66,-677.57 1122.26,-682.15 1126.08,-683.9"/> +</g> +<!-- PTR_TOP->STRUCT_TOP --> +<!-- PTR_BOT --> +<g id="node23" class="node"> +<title>PTR_BOT</title> +<ellipse fill="#008000" stroke="black" cx="1158" cy="-111.99" rx="66.47" ry="28.99"/> +<text text-anchor="middle" x="1158" y="-116.14" font-family="DejaVu Sans" font-size="13.00" fill="white">⊥:ptr</text> +<text text-anchor="middle" x="1158" y="-99.64" font-family="DejaVu Sans" font-size="13.00" fill="white">[*⊥:struct?]</text> +</g> +<!-- PTR_BOT->BOT --> +<g id="edge87" class="edge"> +<title>PTR_BOT->BOT</title> +<path fill="none" stroke="#555555" d="M1158,-82.64C1158,-70.25 1158,-55.86 1158,-43.89"/> +<polygon fill="#555555" stroke="#555555" points="1160.1,-43.94 1158,-37.94 1155.9,-43.94 1160.1,-43.94"/> +</g> +<!-- PTR_PERSON_NIL --> +<g id="node29" class="node"> +<title>PTR_PERSON_NIL</title> +<ellipse fill="#008000" stroke="black" cx="1111" cy="-552.64" rx="50.33" ry="18"/> +<text text-anchor="middle" x="1111" y="-548.54" font-family="DejaVu Sans" font-size="13.00" fill="white">*Person?</text> +</g> +<!-- PTR_NULL->PTR_PERSON_NIL --> +<g id="edge43" class="edge"> +<title>PTR_NULL->PTR_PERSON_NIL</title> +<path fill="none" stroke="#555555" d="M1203.98,-642.89C1185.68,-625.32 1154.58,-595.47 1133.44,-575.18"/> +<polygon fill="#555555" stroke="#555555" points="1134.9,-573.67 1129.12,-571.03 1131.99,-576.7 1134.9,-573.67"/> +</g> +<!-- PTR_S1_NIL --> +<g id="node30" class="node"> +<title>PTR_S1_NIL</title> +<ellipse fill="#008000" stroke="black" cx="1208" cy="-552.64" rx="30.37" ry="18"/> +<text text-anchor="middle" x="1208" y="-548.54" font-family="DejaVu Sans" font-size="13.00" fill="white">*s1?</text> +</g> +<!-- PTR_NULL->PTR_S1_NIL --> +<g id="edge44" class="edge"> +<title>PTR_NULL->PTR_S1_NIL</title> +<path fill="none" stroke="#555555" d="M1217.18,-640.18C1215.39,-623.3 1212.64,-597.33 1210.61,-578.24"/> +<polygon fill="#555555" stroke="#555555" points="1212.7,-578.03 1209.98,-572.29 1208.52,-578.48 1212.7,-578.03"/> +</g> +<!-- PTR_MORE_NIL --> +<g id="node31" class="node"> +<title>PTR_MORE_NIL</title> +<ellipse fill="#008000" stroke="black" cx="1300" cy="-552.64" rx="45.21" ry="18"/> +<text text-anchor="middle" x="1300" y="-548.54" font-family="DejaVu Sans" font-size="13.00" fill="white">*s2?, …</text> +</g> +<!-- PTR_NULL->PTR_MORE_NIL --> +<g id="edge45" class="edge"> +<title>PTR_NULL->PTR_MORE_NIL</title> +<path fill="none" stroke="#555555" d="M1230.95,-642C1244.59,-624.55 1267.02,-595.85 1282.6,-575.91"/> +<polygon fill="#555555" stroke="#555555" points="1284.22,-577.24 1286.26,-571.22 1280.92,-574.65 1284.22,-577.24"/> +</g> +<!-- PTR_ANY --> +<g id="node25" class="node"> +<title>PTR_ANY</title> +<ellipse fill="#008000" stroke="black" cx="962" cy="-552.64" rx="82.38" ry="28.99"/> +<text text-anchor="middle" x="962" y="-556.79" font-family="DejaVu Sans" font-size="13.00" fill="white">*⊥:struct</text> +<text text-anchor="middle" x="962" y="-540.29" font-family="DejaVu Sans" font-size="13.00" fill="white">[ptr any struct]</text> +</g> +<!-- PTR_ANY->PTR_BOT --> +<g id="edge46" class="edge"> +<title>PTR_ANY->PTR_BOT</title> +<path fill="none" stroke="#555555" d="M974.56,-523.53C1008.99,-446.47 1104.84,-231.98 1142.51,-147.66"/> +<polygon fill="#555555" stroke="#555555" points="1144.4,-148.58 1144.93,-142.25 1140.56,-146.87 1144.4,-148.58"/> +</g> +<!-- PTR_ANY->PTR_PERSON_NIL --> +<!-- PTR_PERSON->PTR_ANY --> +<g id="edge37" class="edge"> +<title>PTR_PERSON->PTR_ANY</title> +<path fill="none" stroke="#555555" d="M962,-640.18C962,-626.3 962,-606.26 962,-588.96"/> +<polygon fill="#555555" stroke="#555555" points="964.1,-589.25 962,-583.25 959.9,-589.25 964.1,-589.25"/> +</g> +<!-- PTR_PERSON->PTR_S1 --> +<!-- PTR_PERSON->PTR_PERSON_NIL --> +<g id="edge40" class="edge"> +<title>PTR_PERSON->PTR_PERSON_NIL</title> +<path fill="none" stroke="#555555" d="M983.67,-642.23C1009.89,-623.98 1054.1,-593.22 1082.92,-573.18"/> +<polygon fill="#555555" stroke="#555555" points="1083.85,-575.09 1087.58,-569.94 1081.45,-571.64 1083.85,-575.09"/> +</g> +<!-- PTR_S1->PTR_ANY --> +<g id="edge38" class="edge"> +<title>PTR_S1->PTR_ANY</title> +<path fill="none" stroke="#555555" d="M1038.25,-642.45C1025.79,-627.94 1006.41,-605.36 990.3,-586.6"/> +<polygon fill="#555555" stroke="#555555" points="991.91,-585.25 986.4,-582.07 988.72,-587.99 991.91,-585.25"/> +</g> +<!-- PTR_S1->PTR_MORE --> +<!-- PTR_S1->PTR_S1_NIL --> +<g id="edge41" class="edge"> +<title>PTR_S1->PTR_S1_NIL</title> +<path fill="none" stroke="#555555" d="M1072.08,-646.82C1101.29,-632.14 1152.34,-605.85 1169,-593.3 1176.35,-587.76 1183.64,-580.85 1189.88,-574.36"/> +<polygon fill="#555555" stroke="#555555" points="1191.26,-575.96 1193.83,-570.14 1188.2,-573.09 1191.26,-575.96"/> +</g> +<!-- PTR_MORE->PTR_NULL --> +<!-- PTR_MORE->PTR_ANY --> +<g id="edge39" class="edge"> +<title>PTR_MORE->PTR_ANY</title> +<path fill="none" stroke="#555555" d="M1111.67,-643.32C1085.45,-627.61 1042.2,-601.69 1008.92,-581.75"/> +<polygon fill="#555555" stroke="#555555" points="1010.35,-580.16 1004.12,-578.88 1008.19,-583.77 1010.35,-580.16"/> +</g> +<!-- PTR_MORE->PTR_MORE_NIL --> +<g id="edge42" class="edge"> +<title>PTR_MORE->PTR_MORE_NIL</title> +<path fill="none" stroke="#555555" d="M1160.16,-643.83C1182.97,-631.38 1217.31,-612.02 1246,-593.3 1255.42,-587.15 1265.42,-579.99 1274.23,-573.46"/> +<polygon fill="#555555" stroke="#555555" points="1275.36,-575.24 1278.9,-569.97 1272.84,-571.88 1275.36,-575.24"/> +</g> +<!-- PTR_PERSON_NIL->PTR_BOT --> +<g id="edge47" class="edge"> +<title>PTR_PERSON_NIL->PTR_BOT</title> +<path fill="none" stroke="#555555" d="M1112.87,-534.18C1119.87,-468.84 1144.61,-238.01 1154.18,-148.67"/> +<polygon fill="#555555" stroke="#555555" points="1156.26,-148.92 1154.81,-142.73 1152.09,-148.47 1156.26,-148.92"/> +</g> +<!-- PTR_PERSON_NIL->PTR_S1_NIL --> +<!-- PTR_S1_NIL->PTR_BOT --> +<g id="edge48" class="edge"> +<title>PTR_S1_NIL->PTR_BOT</title> +<path fill="none" stroke="#555555" d="M1206.04,-534.45C1198.64,-469.49 1172.28,-238.26 1162.08,-148.74"/> +<polygon fill="#555555" stroke="#555555" points="1164.16,-148.51 1161.4,-142.79 1159.99,-148.99 1164.16,-148.51"/> +</g> +<!-- PTR_S1_NIL->PTR_MORE_NIL --> +<!-- PTR_MORE_NIL->PTR_BOT --> +<g id="edge49" class="edge"> +<title>PTR_MORE_NIL->PTR_BOT</title> +<path fill="none" stroke="#555555" d="M1294.43,-534.45C1273.34,-469.29 1198.07,-236.78 1169.3,-147.89"/> +<polygon fill="#555555" stroke="#555555" points="1171.38,-147.49 1167.53,-142.43 1167.38,-148.78 1171.38,-147.49"/> +</g> +<!-- STRUCT_PERSON --> +<g id="node34" class="node"> +<title>STRUCT_PERSON</title> +<polygon fill="#90ee90" stroke="black" points="1436.5,-228.98 1369.5,-228.98 1369.5,-187.98 1436.5,-187.98 1436.5,-228.98"/> +<text text-anchor="middle" x="1403" y="-212.63" font-family="DejaVu Sans" font-size="13.00">Person</text> +<text text-anchor="middle" x="1403" y="-196.13" font-family="DejaVu Sans" font-size="13.00">age: int</text> +</g> +<!-- STRUCT_TOP->STRUCT_PERSON --> +<g id="edge53" class="edge"> +<title>STRUCT_TOP->STRUCT_PERSON</title> +<path fill="none" stroke="#555555" d="M1468.98,-723.31C1455.09,-685.46 1433,-615.54 1433,-553.64 1433,-553.64 1433,-553.64 1433,-410.98 1433,-347.98 1418.48,-275.1 1409.64,-236.59"/> +<polygon fill="#555555" stroke="#555555" points="1411.7,-236.2 1408.3,-230.83 1407.61,-237.15 1411.7,-236.2"/> +</g> +<!-- STRUCT_S1 --> +<g id="node35" class="node"> +<title>STRUCT_S1</title> +<polygon fill="#90ee90" stroke="black" points="1507,-228.98 1453,-228.98 1453,-187.98 1507,-187.98 1507,-228.98"/> +<text text-anchor="middle" x="1480" y="-212.63" font-family="DejaVu Sans" font-size="13.00">s1</text> +<text text-anchor="middle" x="1480" y="-196.13" font-family="DejaVu Sans" font-size="13.00">x: int</text> +</g> +<!-- STRUCT_TOP->STRUCT_S1 --> +<g id="edge54" class="edge"> +<title>STRUCT_TOP->STRUCT_S1</title> +<path fill="none" stroke="#555555" d="M1480,-722.82C1480,-684.41 1480,-613.86 1480,-553.64 1480,-553.64 1480,-553.64 1480,-410.98 1480,-348.51 1480,-275.13 1480,-236.47"/> +<polygon fill="#555555" stroke="#555555" points="1482.1,-236.73 1480,-230.73 1477.9,-236.73 1482.1,-236.73"/> +</g> +<!-- STRUCT_S2 --> +<g id="node36" class="node"> +<title>STRUCT_S2</title> +<polygon fill="#90ee90" stroke="black" points="1619.12,-228.98 1522.88,-228.98 1522.88,-187.98 1619.12,-187.98 1619.12,-228.98"/> +<text text-anchor="middle" x="1571" y="-212.63" font-family="DejaVu Sans" font-size="13.00">s2</text> +<text text-anchor="middle" x="1571" y="-196.13" font-family="DejaVu Sans" font-size="13.00">x: int, y: *s1</text> +</g> +<!-- STRUCT_TOP->STRUCT_S2 --> +<g id="edge55" class="edge"> +<title>STRUCT_TOP->STRUCT_S2</title> +<path fill="none" stroke="#555555" d="M1492.66,-723.47C1508.62,-685.79 1534,-616.07 1534,-553.64 1534,-553.64 1534,-553.64 1534,-410.98 1534,-347.63 1551.91,-274.88 1562.81,-236.49"/> +<polygon fill="#555555" stroke="#555555" points="1564.83,-237.08 1564.47,-230.74 1560.79,-235.92 1564.83,-237.08"/> +</g> +<!-- STRUCT_MORE --> +<g id="node37" class="node"> +<title>STRUCT_MORE</title> +<polygon fill="#90ee90" stroke="black" points="1689,-226.48 1635,-226.48 1635,-190.48 1689,-190.48 1689,-226.48"/> +<text text-anchor="middle" x="1662" y="-204.38" font-family="DejaVu Sans" font-size="13.00">…</text> +</g> +<!-- STRUCT_TOP->STRUCT_MORE --> +<g id="edge56" class="edge"> +<title>STRUCT_TOP->STRUCT_MORE</title> +<path fill="none" stroke="#555555" d="M1509.78,-726.19C1547.31,-691.55 1607,-625.22 1607,-553.64 1607,-553.64 1607,-553.64 1607,-410.98 1607,-344.76 1634.99,-270.47 1651.04,-233.33"/> +<polygon fill="#555555" stroke="#555555" points="1652.79,-234.56 1653.28,-228.22 1648.94,-232.87 1652.79,-234.56"/> +</g> +<!-- STRUCT_TOP->MEM_TOP --> +<!-- STRUCT_BOT --> +<g id="node33" class="node"> +<title>STRUCT_BOT</title> +<ellipse fill="#90ee90" stroke="black" cx="1480" cy="-111.99" rx="82.91" ry="28.99"/> +<text text-anchor="middle" x="1480" y="-116.14" font-family="DejaVu Sans" font-size="13.00">⊥:struct</text> +<text text-anchor="middle" x="1480" y="-99.64" font-family="DejaVu Sans" font-size="13.00">[struct bottom]</text> +</g> +<!-- STRUCT_BOT->BOT --> +<g id="edge88" class="edge"> +<title>STRUCT_BOT->BOT</title> +<path fill="none" stroke="#555555" d="M1417.46,-92.56C1398.09,-86.88 1376.68,-80.65 1357,-75 1298.06,-58.08 1229.14,-38.8 1189.83,-27.85"/> +<polygon fill="#555555" stroke="#555555" points="1190.64,-25.89 1184.3,-26.31 1189.52,-29.94 1190.64,-25.89"/> +</g> +<!-- STRUCT_PERSON->STRUCT_BOT --> +<g id="edge57" class="edge"> +<title>STRUCT_PERSON->STRUCT_BOT</title> +<path fill="none" stroke="#555555" d="M1418.95,-187.9C1428.91,-175.69 1441.97,-159.66 1453.46,-145.57"/> +<polygon fill="#555555" stroke="#555555" points="1454.82,-147.22 1456.98,-141.24 1451.56,-144.57 1454.82,-147.22"/> +</g> +<!-- STRUCT_PERSON->STRUCT_S1 --> +<!-- STRUCT_S1->STRUCT_BOT --> +<g id="edge58" class="edge"> +<title>STRUCT_S1->STRUCT_BOT</title> +<path fill="none" stroke="#555555" d="M1480,-187.9C1480,-176.5 1480,-161.78 1480,-148.41"/> +<polygon fill="#555555" stroke="#555555" points="1482.1,-148.66 1480,-142.66 1477.9,-148.66 1482.1,-148.66"/> +</g> +<!-- STRUCT_S1->STRUCT_S2 --> +<!-- STRUCT_S2->STRUCT_BOT --> +<g id="edge59" class="edge"> +<title>STRUCT_S2->STRUCT_BOT</title> +<path fill="none" stroke="#555555" d="M1552.14,-187.9C1540.18,-175.48 1524.43,-159.12 1510.69,-144.86"/> +<polygon fill="#555555" stroke="#555555" points="1512.46,-143.67 1506.78,-140.8 1509.43,-146.58 1512.46,-143.67"/> +</g> +<!-- STRUCT_S2->STRUCT_MORE --> +<!-- STRUCT_MORE->STRUCT_BOT --> +<g id="edge60" class="edge"> +<title>STRUCT_MORE->STRUCT_BOT</title> +<path fill="none" stroke="#555555" d="M1634.54,-192.06C1632,-190.67 1629.45,-189.29 1627,-187.98 1596.23,-171.57 1561.48,-153.81 1533.49,-139.69"/> +<polygon fill="#555555" stroke="#555555" points="1534.55,-137.87 1528.25,-137.05 1532.67,-141.62 1534.55,-137.87"/> +</g> +<!-- MEM_ALIAS2 --> +<g id="node40" class="node"> +<title>MEM_ALIAS2</title> +<ellipse fill="#00008b" stroke="black" cx="1758" cy="-293.98" rx="45.21" ry="18"/> +<text text-anchor="middle" x="1758" y="-289.88" font-family="DejaVu Sans" font-size="13.00" fill="white">MEM#2</text> +</g> +<!-- MEM_TOP->MEM_ALIAS2 --> +<g id="edge63" class="edge"> +<title>MEM_TOP->MEM_ALIAS2</title> +<path fill="none" stroke="#555555" d="M1805.14,-733.96C1797.62,-663.94 1769.47,-401.76 1760.65,-319.7"/> +<polygon fill="#555555" stroke="#555555" points="1762.75,-319.58 1760.02,-313.84 1758.58,-320.03 1762.75,-319.58"/> +</g> +<!-- MEM_ALIAS3 --> +<g id="node41" class="node"> +<title>MEM_ALIAS3</title> +<ellipse fill="#00008b" stroke="black" cx="1864" cy="-293.98" rx="45.21" ry="18"/> +<text text-anchor="middle" x="1864" y="-289.88" font-family="DejaVu Sans" font-size="13.00" fill="white">MEM#3</text> +</g> +<!-- MEM_TOP->MEM_ALIAS3 --> +<g id="edge64" class="edge"> +<title>MEM_TOP->MEM_ALIAS3</title> +<path fill="none" stroke="#555555" d="M1809.16,-733.96C1817.91,-663.94 1850.66,-401.76 1860.91,-319.7"/> +<polygon fill="#555555" stroke="#555555" points="1862.99,-320.05 1861.65,-313.83 1858.82,-319.53 1862.99,-320.05"/> +</g> +<!-- MEM_MORE --> +<g id="node42" class="node"> +<title>MEM_MORE</title> +<ellipse fill="#00008b" stroke="black" cx="1952" cy="-293.98" rx="27" ry="18"/> +<text text-anchor="middle" x="1952" y="-289.88" font-family="DejaVu Sans" font-size="13.00" fill="white">…</text> +</g> +<!-- MEM_TOP->MEM_MORE --> +<g id="edge65" class="edge"> +<title>MEM_TOP->MEM_MORE</title> +<path fill="none" stroke="#555555" d="M1812.51,-733.96C1834.85,-663.64 1918.78,-399.51 1944.48,-318.66"/> +<polygon fill="#555555" stroke="#555555" points="1946.37,-319.64 1946.18,-313.29 1942.36,-318.37 1946.37,-319.64"/> +</g> +<!-- MEM_TOP->TUPLE_TOP --> +<!-- MEM_BOT --> +<g id="node39" class="node"> +<title>MEM_BOT</title> +<ellipse fill="#00008b" stroke="black" cx="1811" cy="-111.99" rx="44.7" ry="18"/> +<text text-anchor="middle" x="1811" y="-107.89" font-family="DejaVu Sans" font-size="13.00" fill="white">⊥:mem</text> +</g> +<!-- MEM_BOT->BOT --> +<g id="edge89" class="edge"> +<title>MEM_BOT->BOT</title> +<path fill="none" stroke="#555555" d="M1779.72,-98.78C1757.97,-90.77 1728.12,-80.77 1701,-75 1511.81,-34.78 1279.16,-23.1 1192.59,-20.01"/> +<polygon fill="#555555" stroke="#555555" points="1192.74,-17.92 1186.67,-19.81 1192.59,-22.11 1192.74,-17.92"/> +</g> +<!-- MEM_ALIAS2->MEM_BOT --> +<g id="edge66" class="edge"> +<title>MEM_ALIAS2->MEM_BOT</title> +<path fill="none" stroke="#555555" d="M1763.08,-275.72C1772.58,-243.47 1793.04,-173.99 1803.9,-137.12"/> +<polygon fill="#555555" stroke="#555555" points="1805.83,-138 1805.51,-131.65 1801.8,-136.81 1805.83,-138"/> +</g> +<!-- MEM_ALIAS2->MEM_ALIAS3 --> +<!-- MEM_ALIAS3->MEM_BOT --> +<g id="edge67" class="edge"> +<title>MEM_ALIAS3->MEM_BOT</title> +<path fill="none" stroke="#555555" d="M1858.92,-275.72C1849.42,-243.47 1828.96,-173.99 1818.1,-137.12"/> +<polygon fill="#555555" stroke="#555555" points="1820.2,-136.81 1816.49,-131.65 1816.17,-138 1820.2,-136.81"/> +</g> +<!-- MEM_ALIAS3->MEM_MORE --> +<!-- MEM_MORE->MEM_BOT --> +<g id="edge68" class="edge"> +<title>MEM_MORE->MEM_BOT</title> +<path fill="none" stroke="#555555" d="M1939.98,-277.64C1915.01,-245.76 1857.44,-172.28 1828.41,-135.22"/> +<polygon fill="#555555" stroke="#555555" points="1830.29,-134.21 1824.94,-130.79 1826.99,-136.8 1830.29,-134.21"/> +</g> +<!-- TUPLE1 --> +<g id="node45" class="node"> +<title>TUPLE1</title> +<polygon fill="#ffc0cb" stroke="none" points="2046.88,-438.48 2003.12,-438.48 2003.12,-385.48 2046.88,-385.48 2046.88,-438.48"/> +<polygon fill="#ffc0cb" stroke="none" points="2003.12,-411.98 2003.12,-438.48 2046.88,-438.48 2046.88,-411.98 2003.12,-411.98"/> +<polygon fill="none" stroke="black" points="2003.12,-411.98 2003.12,-438.48 2046.88,-438.48 2046.88,-411.98 2003.12,-411.98"/> +<text text-anchor="start" x="2008.12" y="-421.13" font-family="DejaVu Sans" font-size="13.00">tuple</text> +<polygon fill="black" stroke="none" points="2003.12,-385.48 2003.12,-411.98 2046.88,-411.98 2046.88,-385.48 2003.12,-385.48"/> +<polygon fill="none" stroke="black" points="2003.12,-385.48 2003.12,-411.98 2046.88,-411.98 2046.88,-385.48 2003.12,-385.48"/> +<text text-anchor="start" x="2010.38" y="-394.63" font-family="DejaVu Sans" font-size="13.00" fill="white">type</text> +</g> +<!-- TUPLE_TOP->TUPLE1 --> +<g id="edge71" class="edge"> +<title>TUPLE_TOP->TUPLE1</title> +<path fill="none" stroke="#555555" d="M2046.83,-734.05C2043.18,-680.39 2031.99,-515.78 2027.21,-445.42"/> +<polygon fill="#555555" stroke="#555555" points="2029.31,-445.47 2026.81,-439.63 2025.12,-445.75 2029.31,-445.47"/> +</g> +<!-- TUPLE2 --> +<g id="node46" class="node"> +<title>TUPLE2</title> +<polygon fill="#ffc0cb" stroke="none" points="2106.88,-451.73 2063.12,-451.73 2063.12,-372.23 2106.88,-372.23 2106.88,-451.73"/> +<polygon fill="#ffc0cb" stroke="none" points="2063.12,-425.23 2063.12,-451.73 2106.88,-451.73 2106.88,-425.23 2063.12,-425.23"/> +<polygon fill="none" stroke="black" points="2063.12,-425.23 2063.12,-451.73 2106.88,-451.73 2106.88,-425.23 2063.12,-425.23"/> +<text text-anchor="start" x="2068.12" y="-434.38" font-family="DejaVu Sans" font-size="13.00">tuple</text> +<polygon fill="black" stroke="none" points="2063.12,-398.73 2063.12,-425.23 2106.88,-425.23 2106.88,-398.73 2063.12,-398.73"/> +<polygon fill="none" stroke="black" points="2063.12,-398.73 2063.12,-425.23 2106.88,-425.23 2106.88,-398.73 2063.12,-398.73"/> +<text text-anchor="start" x="2070.38" y="-407.88" font-family="DejaVu Sans" font-size="13.00" fill="white">type</text> +<polygon fill="black" stroke="none" points="2063.12,-372.23 2063.12,-398.73 2106.88,-398.73 2106.88,-372.23 2063.12,-372.23"/> +<polygon fill="none" stroke="black" points="2063.12,-372.23 2063.12,-398.73 2106.88,-398.73 2106.88,-372.23 2063.12,-372.23"/> +<text text-anchor="start" x="2070.38" y="-381.38" font-family="DejaVu Sans" font-size="13.00" fill="white">type</text> +</g> +<!-- TUPLE_TOP->TUPLE2 --> +<g id="edge72" class="edge"> +<title>TUPLE_TOP->TUPLE2</title> +<path fill="none" stroke="#555555" d="M2049.89,-734.05C2055.41,-683.57 2071.67,-534.87 2079.98,-458.86"/> +<polygon fill="#555555" stroke="#555555" points="2082.03,-459.43 2080.6,-453.24 2077.86,-458.97 2082.03,-459.43"/> +</g> +<!-- TUPLEN --> +<g id="node47" class="node"> +<title>TUPLEN</title> +<polygon fill="#ffc0cb" stroke="none" points="2166.88,-464.98 2123.12,-464.98 2123.12,-358.98 2166.88,-358.98 2166.88,-464.98"/> +<polygon fill="#ffc0cb" stroke="none" points="2123.12,-438.48 2123.12,-464.98 2166.88,-464.98 2166.88,-438.48 2123.12,-438.48"/> +<polygon fill="none" stroke="black" points="2123.12,-438.48 2123.12,-464.98 2166.88,-464.98 2166.88,-438.48 2123.12,-438.48"/> +<text text-anchor="start" x="2128.12" y="-447.63" font-family="DejaVu Sans" font-size="13.00">tuple</text> +<polygon fill="black" stroke="none" points="2123.12,-411.98 2123.12,-438.48 2166.88,-438.48 2166.88,-411.98 2123.12,-411.98"/> +<polygon fill="none" stroke="black" points="2123.12,-411.98 2123.12,-438.48 2166.88,-438.48 2166.88,-411.98 2123.12,-411.98"/> +<text text-anchor="start" x="2130.38" y="-421.13" font-family="DejaVu Sans" font-size="13.00" fill="white">type</text> +<polygon fill="black" stroke="none" points="2123.12,-385.48 2123.12,-411.98 2166.88,-411.98 2166.88,-385.48 2123.12,-385.48"/> +<polygon fill="none" stroke="black" points="2123.12,-385.48 2123.12,-411.98 2166.88,-411.98 2166.88,-385.48 2123.12,-385.48"/> +<text text-anchor="start" x="2138.62" y="-394.63" font-family="DejaVu Sans" font-size="13.00" fill="white">…</text> +<polygon fill="black" stroke="none" points="2123.12,-358.98 2123.12,-385.48 2166.88,-385.48 2166.88,-358.98 2123.12,-358.98"/> +<polygon fill="none" stroke="black" points="2123.12,-358.98 2123.12,-385.48 2166.88,-385.48 2166.88,-358.98 2123.12,-358.98"/> +<text text-anchor="start" x="2130.38" y="-368.13" font-family="DejaVu Sans" font-size="13.00" fill="white">type</text> +</g> +<!-- TUPLE_TOP->TUPLEN --> +<g id="edge73" class="edge"> +<title>TUPLE_TOP->TUPLEN</title> +<path fill="none" stroke="#555555" d="M2052.94,-734.05C2066.64,-686.28 2105.56,-550.54 2128.17,-471.69"/> +<polygon fill="#555555" stroke="#555555" points="2130.12,-472.51 2129.75,-466.17 2126.08,-471.35 2130.12,-472.51"/> +</g> +<!-- TUPLE_BOT --> +<g id="node44" class="node"> +<title>TUPLE_BOT</title> +<ellipse fill="#ffc0cb" stroke="black" cx="2066" cy="-111.99" rx="44.7" ry="18"/> +<text text-anchor="middle" x="2066" y="-107.89" font-family="DejaVu Sans" font-size="13.00">⊥:tuple</text> +</g> +<!-- TUPLE_BOT->BOT --> +<g id="edge90" class="edge"> +<title>TUPLE_BOT->BOT</title> +<path fill="none" stroke="#555555" d="M2041.91,-96.52C2027.63,-88.7 2008.88,-79.7 1991,-75 1836.4,-34.32 1329.78,-22.17 1192.55,-19.58"/> +<polygon fill="#555555" stroke="#555555" points="1192.72,-17.49 1186.68,-19.47 1192.64,-21.69 1192.72,-17.49"/> +</g> +<!-- TUPLE1->TUPLE_BOT --> +<g id="edge74" class="edge"> +<title>TUPLE1->TUPLE_BOT</title> +<path fill="none" stroke="#555555" d="M2028.5,-385.58C2036.28,-328.98 2054.97,-193.16 2062.63,-137.46"/> +<polygon fill="#555555" stroke="#555555" points="2064.7,-137.88 2063.43,-131.65 2060.53,-137.3 2064.7,-137.88"/> +</g> +<!-- TUPLE1->TUPLE2 --> +<!-- TUPLE2->TUPLE_BOT --> +<g id="edge75" class="edge"> +<title>TUPLE2->TUPLE_BOT</title> +<path fill="none" stroke="#555555" d="M2082.54,-372.33C2078.57,-310.17 2070.89,-189.71 2067.58,-137.79"/> +<polygon fill="#555555" stroke="#555555" points="2069.68,-137.72 2067.2,-131.86 2065.49,-137.98 2069.68,-137.72"/> +</g> +<!-- TUPLE2->TUPLEN --> +<!-- TUPLEN->TUPLE_BOT --> +<g id="edge76" class="edge"> +<title>TUPLEN->TUPLE_BOT</title> +<path fill="none" stroke="#555555" d="M2131.24,-359.08C2114.03,-294.18 2085.29,-185.76 2072.49,-137.48"/> +<polygon fill="#555555" stroke="#555555" points="2074.53,-136.98 2070.97,-131.72 2070.47,-138.06 2074.53,-136.98"/> +</g> +</g> +</svg> diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 3c8d8f40..0602d290 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -64,10 +64,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"); @@ -75,6 +84,10 @@ public class Parser { add("return"); add("struct"); add("true"); + add("u1"); + add("u16"); + add("u32"); + add("u8"); add("while"); }}; @@ -96,7 +109,20 @@ public class Parser { Node.reset(); IterPeeps.reset(); TYPES.clear(); - TYPES.put("int",TypeInteger.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(); @@ -200,7 +226,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"); @@ -220,7 +246,7 @@ public class Parser { TYPES.put(typeName, ts); // Insert the struct name in the collection of all struct names _aliases.put(typeName,_alias); _alias += ts._fields.length; - return null; + return parseStatement(); } /** @@ -435,6 +461,11 @@ public class Parser { throw error("Undefined name '" + name + "'"); t = _scope.lookupDeclaredType(name); } + // 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 ) @@ -476,7 +507,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: @@ -487,7 +540,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 @@ -500,8 +553,8 @@ 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 = lhs.peephole(); + lhs.setDef(idx,parseShift()); + lhs = lhs.widen().peephole(); if( negate ) // Extra negate for != lhs = new NotNode(lhs).peephole(); } @@ -512,6 +565,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} @@ -524,7 +599,7 @@ public class Parser { else if( match("-") ) lhs = new SubNode(lhs,null); else break; lhs.setDef(2,parseMultiplication()); - lhs = lhs.peephole(); + lhs = lhs.widen().peephole(); } return lhs; } @@ -545,7 +620,7 @@ public class Parser { else if( match("/") ) lhs = new DivNode(lhs,null); else break; lhs.setDef(2,parseUnary()); - lhs = lhs.peephole(); + lhs = lhs.widen().peephole(); } return lhs; } @@ -559,7 +634,7 @@ public class Parser { * @return a unary expression {@link Node}, never {@code null} */ private Node parseUnary() { - if (match("-")) return new MinusNode(parseUnary()).peephole(); + if (match("-")) return new MinusNode(parseUnary()).widen().peephole(); if (match("!")) return new NotNode(parseUnary()).peephole(); return parsePostfix(parsePrimary()); } @@ -644,6 +719,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); store(name,alias,glb,expr,val,false); return expr; // "obj.a = expr" returns the expression while updating memory } @@ -653,11 +730,34 @@ public class Parser { return parsePostfix(new LoadNode(name, alias, declaredType.glb(), mem(), 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 TypeFloat && t instanceof TypeInteger ) + val = new ToIntegerNode(val).peephole(); + 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 * * <pre> * integerLiteral: [1-9][0-9]* | [0] + * floatLiteral: [digits].[digits]?[e [digits]]? * </pre> */ private ConstantNode parseLiteral() { @@ -815,19 +915,37 @@ public class Parser { return String.valueOf(peek()); } - boolean isNumber() {return isNumber(peek());} + boolean isNumber(char ch) {return Character.isDigit(ch);} + // Return a constant Type, either TypeInteger or TypeFloat private Type parseNumber() { - String snum = parseNumberString(); - if (snum.length() > 1 && snum.charAt(0) == '0') - throw error("Syntax error: integer values cannot start with '0'"); - return TypeInteger.constant(Long.parseLong(snum)); + int old = _position; + int len = isLongOrDouble(); + if( len > 0 ) { + if( len > 1 && _input[old]=='0' ) + throw error("Syntax error: integer values cannot start with '0'"); + return TypeInteger.constant(Long.parseLong(new String(_input,old,len))); + } + return TypeFloat.constant(Double.parseDouble(new String(_input,old,-len))); } private String parseNumberString() { - int start = _position; - while (isNumber(nextChar())) ; - return new String(_input, start, --_position - start); + int old = _position; + int len = Math.abs(isLongOrDouble()); + _position += len; + return new String(_input,old,len); + } + + // Return +len that ends a long + // Return -len that ends a double + private int isLongOrDouble() { + int old = _position; + char c; + while( Character.isDigit(c=nextChar()) ) ; + if( !(c=='e' || c=='.') ) + return --_position - old; + while( Character.isDigit(c=nextChar()) || c=='e' || c=='.' ) ; + return -(--_position - old); } // First letter of an identifier diff --git a/src/main/java/com/seaofnodes/simple/node/AddFNode.java b/src/main/java/com/seaofnodes/simple/node/AddFNode.java new file mode 100644 index 00000000..fd713156 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/AddFNode.java @@ -0,0 +1,37 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; + + +public class AddFNode extends Node { + public AddFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "AddF"; } + + @Override protected String format() { return "(%1+%2)"; } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeFloat i0 && + in(2)._type instanceof TypeFloat i1) { + if (i0.isConstant() && i1.isConstant()) + return TypeFloat.constant(i0.value()+i1.value()); + } + return in(1)._type.meet(in(2)._type); + } + + @Override + public Node idealize() { + Node lhs = in(1); + Type t2 = in(2)._type; + + // Add of 0. + if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==0 ) + return lhs; + + return null; + } + @Override Node copy(Node lhs, Node rhs) { return new AddFNode(lhs,rhs); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index eb7e2793..0046bd03 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -15,17 +15,23 @@ public class AddNode extends Node { @Override public Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; - if( t1==Type.TOP || t1==TypeInteger.TOP || - t2==Type.TOP || t2==TypeInteger.TOP ) - return TypeInteger.TOP; - if( t1 instanceof TypeInteger i0 && - t2 instanceof TypeInteger i1 ) { - if (i0.isConstant() && i1.isConstant()) - return TypeInteger.constant(i0.value()+i1.value()); + 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 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); @@ -34,7 +40,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 && lhs._type instanceof TypeInteger ) return lhs; // Add of same to a multiply by 2 @@ -97,7 +103,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) { @@ -169,6 +175,7 @@ public class AddNode extends Node { } @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); } + @Override Node copyF() { return new AddFNode(null,null); } @Override public String err() { if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type; if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type; 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..e2729e60 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/AndNode.java @@ -0,0 +1,59 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + + +public class AndNode extends Node { + public AndNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "And"; } + + @Override protected String format() { return "(%1&%2)"; } + + @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 && lhs._type instanceof TypeInteger ) + 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 63452dba..8a25e8d9 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -2,10 +2,14 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.type.TypeFloat; import com.seaofnodes.simple.type.TypeMemPtr; +import static com.seaofnodes.simple.type.TypeInteger.*; abstract public class BoolNode extends Node { @@ -23,52 +27,84 @@ abstract public class BoolNode extends Node { } @Override - public Type compute() { - Type t1 = in(1)._type, t2 = in(2)._type; - if( t1==Type.TOP || t1==TypeInteger.TOP || - t2==Type.TOP || t2==TypeInteger.TOP ) - return TypeInteger.TOP; - if( t1 instanceof TypeInteger i0 && - t2 instanceof TypeInteger 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; } - abstract boolean doOp(long lhs, long rhs); + 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) ) { // con==noncon becomes noncon==con - if( in(1) instanceof ConstantNode ) - return new EQ(in(2),in(1)); + if( in(1) instanceof ConstantNode || in(1)._nid > in(2)._nid ) // Equals sorts by NID otherwise: non.high == non.low becomes non.low == non.high - else if( in(1)._nid > in(2)._nid ) - return new EQ(in(2),in(1)); + 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 ((phi cons) cmp con) ? - // Do we have ((phi cons) cmp (phi cons)) ? - // Push the compare up through the phi: (phi con0 cmp con, con1 cmp con...) - 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); } } - 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); } } - 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); } } + 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 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/DivFNode.java b/src/main/java/com/seaofnodes/simple/node/DivFNode.java new file mode 100644 index 00000000..a3f4318d --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/DivFNode.java @@ -0,0 +1,39 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; + + +public class DivFNode extends Node { + public DivFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "DivF"; } + + @Override protected String format() { return "(%1/%2)"; } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeFloat i0 && + in(2)._type instanceof TypeFloat i1) { + if (i0.isConstant() && i1.isConstant()) + return TypeFloat.constant(i0.value()/i1.value()); + } + return in(1)._type.meet(in(2)._type); + } + + @Override + public Node idealize() { + Node lhs = in(1); + Node rhs = in(2); + Type t1 = lhs._type; + Type t2 = rhs._type; + + // Div of 1. + if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==1 ) + return lhs; + + return null; + } + @Override Node copy(Node lhs, Node rhs) { return new DivFNode(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 d7244ace..e725ace4 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -15,15 +15,14 @@ public class DivNode extends Node { @Override public Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; - if( t1==Type.TOP || t1==TypeInteger.TOP || - t2==Type.TOP || t2==TypeInteger.TOP ) + if( t1.isHigh() || t2.isHigh() ) return TypeInteger.TOP; - if (t1 instanceof TypeInteger i0 && - t2 instanceof TypeInteger i1) { - if (i0.isConstant() && i1.isConstant()) - return i1.value() == 0 + 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 TypeInteger.BOT; } @@ -31,10 +30,11 @@ public class DivNode extends Node { @Override public Node idealize() { // Div of 1. - if( in(2)._type.isConstant() && in(2)._type instanceof TypeInteger i && i.value()==1 ) + if( in(2)._type.isConstant() && in(2)._type instanceof TypeInteger i && i.value()==1 && in(1)._type instanceof TypeInteger ) return in(1); return null; } @Override Node copy(Node lhs, Node rhs) { return new DivNode(lhs,rhs); } + @Override Node copyF() { return new DivFNode(null,null); } } diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 277644f5..3191061c 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -96,4 +96,8 @@ public class LoadNode extends MemOpNode { Node px = phi.in(idx); return px!=null && px.addDep(this) instanceof StoreNode st1 && ptr()==st1.ptr() && _alias==st1._alias; } + + 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 7c6afb0c..29d302cb 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/MinusFNode.java b/src/main/java/com/seaofnodes/simple/node/MinusFNode.java new file mode 100644 index 00000000..1b45c7c5 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/MinusFNode.java @@ -0,0 +1,30 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; + + +public class MinusFNode extends Node { + public MinusFNode(Node in) { super(null, in); } + + @Override public String label() { return "MinusF"; } + + @Override protected String format() { return "(-%1)"; } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeFloat i0) + return i0.isConstant() ? TypeFloat.constant(-i0.value()) : i0; + return TypeFloat.BOT; + } + + @Override + public Node idealize() { + // -(-x) is x + if( in(1) instanceof MinusFNode minus ) + return minus.in(1); + + return null; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 5b65b3fb..f56c423e 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -14,9 +14,13 @@ public class MinusNode extends Node { @Override public Type compute() { - if (in(1)._type instanceof TypeInteger i0) - return i0.isConstant() ? TypeInteger.constant(-i0.value()) : i0; - return in(1)._type==Type.TOP ? TypeInteger.TOP : TypeInteger.BOT; + 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 in(1)._type.isHigh() ? TypeInteger.TOP : TypeInteger.BOT; } @Override @@ -27,4 +31,5 @@ public class MinusNode extends Node { return null; } + @Override Node copyF() { return new MinusFNode(null); } } diff --git a/src/main/java/com/seaofnodes/simple/node/MulFNode.java b/src/main/java/com/seaofnodes/simple/node/MulFNode.java new file mode 100644 index 00000000..6a57f3c5 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/MulFNode.java @@ -0,0 +1,44 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; + + +public class MulFNode extends Node { + public MulFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "MulF"; } + + @Override protected String format() { return "(%1*%2)"; } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeFloat i0 && + in(2)._type instanceof TypeFloat i1) { + if (i0.isConstant() && i1.isConstant()) + return TypeFloat.constant(i0.value()*i1.value()); + } + return in(1)._type.meet(in(2)._type); + } + + @Override + public Node idealize() { + Node lhs = in(1); + Node rhs = in(2); + Type t1 = lhs._type; + Type t2 = rhs._type; + + // Mul of 1. We do not check for (1*x) because this will already + // canonicalize to (x*1) + if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==1 ) + return lhs; + + // Move constants to RHS: con*arg becomes arg*con + if ( t1.isConstant() && !t2.isConstant() ) + return swap12(); + + return null; + } + @Override Node copy(Node lhs, Node rhs) { return new MulFNode(lhs,rhs); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index b0359a52..c16edb4b 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -15,13 +15,12 @@ public class MulNode extends Node { @Override public Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; - if( t1==Type.TOP || t1==TypeInteger.TOP || - t2==Type.TOP || t2==TypeInteger.TOP ) + if( t1.isHigh() || t2.isHigh() ) return TypeInteger.TOP; - if (t1 instanceof TypeInteger i0 && - t2 instanceof TypeInteger i1) { - if (i0.isConstant() && i1.isConstant()) - return TypeInteger.constant(i0.value()*i1.value()); + if( t1 instanceof TypeInteger i1 && + t2 instanceof TypeInteger i2 ) { + if (i1.isConstant() && i2.isConstant()) + return TypeInteger.constant(i1.value()*i2.value()); } return TypeInteger.BOT; } @@ -35,7 +34,7 @@ public class MulNode extends Node { // Mul 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 ) + if ( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==1 && lhs._type instanceof TypeInteger ) return lhs; // Move constants to RHS: con*arg becomes arg*con @@ -51,6 +50,7 @@ public class MulNode extends Node { return null; } @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); } + @Override Node copyF() { return new MulFNode(null,null); } @Override public String err() { if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type; if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type; diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 2c8596fa..4ee82187 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -8,6 +8,7 @@ import com.seaofnodes.simple.IRPrinter; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; import java.util.*; import java.util.function.Function; @@ -496,6 +497,26 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable /** Return block start from a isCFG() */ public Node getBlockStart() { return null; } + // Semantic change to the graph (so NOT a peephole), used by the Parser. + // If any input is a float, flip to a float-flavored opcode and widen any + // non-float input. + public final Node widen() { + if( !hasFloatInput() ) return this; + Node flt = copyF(); + if( flt==null ) return this; + for( int i=1; i<nIns(); i++ ) + flt.setDef(i, in(i)._type instanceof TypeFloat ? in(i) : new ToFloatNode(in(i)).peephole()); + kill(); + return flt; + } + private boolean hasFloatInput() { + for( int i=1; i<nIns(); i++ ) + if( in(i)._type instanceof TypeFloat ) + return true; + return false; + } + Node copyF() { return null; } + // ------------------------------------------------------------------------ // Peephole utilities @@ -572,7 +593,12 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable 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 5e556390..2e89f013 100644 --- a/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -14,9 +14,11 @@ 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) : TypeInteger.BOT; case TypeMemPtr p0: // top->top, bot->bot, null->1, *void->0, not-null ptr->0, ptr/nil->bot // If input in null then true 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..67585423 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/OrNode.java @@ -0,0 +1,56 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + + +public class OrNode extends Node { + public OrNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "Or"; } + + @Override protected String format() { return "(%1|%2)"; } + + @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 && lhs._type instanceof TypeInteger ) + 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 8dfa04cf..309cd8b5 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -12,7 +12,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; } 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..6be071a2 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java @@ -0,0 +1,34 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; + + +public class RoundF32Node extends Node { + public RoundF32Node(Node lhs) { super(null, lhs); } + + @Override public String label() { return "RoundF32"; } + + @Override protected String format() { return "((f32)%1)"; } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeFloat i0 && i0.isConstant() ) + return TypeFloat.constant((float)i0.value()); + if( in(1)._type==TypeFloat.BOT ) return TypeFloat.B32; + 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..6ab7141f --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/SarNode.java @@ -0,0 +1,49 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + + +public class SarNode extends Node { + public SarNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "Sar"; } + + @Override protected String format() { return "(%1>>%2)"; } + + @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 && lhs._type instanceof TypeInteger ) + 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..999fc7da --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -0,0 +1,46 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + + +public class ShlNode extends Node { + public ShlNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "Shl"; } + + @Override protected String format() { return "(%1<<%2)"; } + + @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 && lhs._type instanceof TypeInteger ) + 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..b89f5191 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -0,0 +1,49 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + + +public class ShrNode extends Node { + public ShrNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "Shr"; } + + @Override protected String format() { return "(%1>>>%2)"; } + + @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 && lhs._type instanceof TypeInteger ) + 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 new file mode 100644 index 00000000..2d218a03 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/SubFNode.java @@ -0,0 +1,37 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; + + +public class SubFNode extends Node { + public SubFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "SubF"; } + + @Override protected String format() { return "(%1-%2)"; } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeFloat i0 && + in(2)._type instanceof TypeFloat i1) { + if (i0.isConstant() && i1.isConstant()) + return TypeFloat.constant(i0.value()-i1.value()); + } + return in(1)._type.meet(in(2)._type); + } + + @Override + public Node idealize() { + Node lhs = in(1); + Type t2 = in(2)._type; + + // Sub of 0. + if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==0 ) + return lhs; + + return null; + } + @Override Node copy(Node lhs, Node rhs) { return new SubFNode(lhs,rhs); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index 1589abe7..d5e54e73 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -15,18 +15,17 @@ public class SubNode extends Node { @Override public Type compute() { - Type t1 = in(1)._type, t2 = in(2)._type; - if( t1==Type.TOP || t1==TypeInteger.TOP || - t2==Type.TOP || t2==TypeInteger.TOP ) - return TypeInteger.TOP; // Sub of same is 0 if( in(1)==in(2) ) return TypeInteger.ZERO; - if (t1 instanceof TypeInteger i0 && - t2 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 TypeInteger.BOT; @@ -57,4 +56,5 @@ public class SubNode extends Node { } @Override Node copy(Node lhs, Node rhs) { return new SubNode(lhs,rhs); } + @Override Node copyF() { return new SubFNode(null,null); } } diff --git a/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java b/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java new file mode 100644 index 00000000..26cf50e1 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java @@ -0,0 +1,25 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; +import com.seaofnodes.simple.type.TypeInteger; + + +public class ToFloatNode extends Node { + public ToFloatNode(Node lhs) { super(null, lhs); } + + @Override public String label() { return "ToFloat"; } + + @Override protected String format() { return "(flt)%1"; } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0 && i0.isConstant() ) + return TypeFloat.constant(i0.value()); + return TypeFloat.BOT; + } + + @Override public Node idealize() { return null; } + @Override Node copy(Node lhs, Node rhs) { return new ToFloatNode(lhs); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/ToIntegerNode.java b/src/main/java/com/seaofnodes/simple/node/ToIntegerNode.java new file mode 100644 index 00000000..df740202 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ToIntegerNode.java @@ -0,0 +1,23 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; +import com.seaofnodes.simple.type.TypeInteger; + +// Truncate toward zero, saturating overflow; NaN converts to zero. +public class ToIntegerNode extends Node { + public ToIntegerNode(Node lhs) { super(null,lhs); } + @Override public String label() { return "ToInteger"; } + @Override protected String format() { return "(int)%1"; } + + @Override public Type compute() { + Type t = in(1)._type; + if( t.isHigh() ) return TypeInteger.TOP; + if( t instanceof TypeFloat tf && tf.isConstant() ) + return TypeInteger.constant((long)tf.value()); + return TypeInteger.BOT; + } + + @Override public Node idealize() { return null; } + @Override Node copy(Node lhs, Node rhs) { return new ToIntegerNode(lhs); } +} 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..720fb8e4 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/XorNode.java @@ -0,0 +1,56 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + + +public class XorNode extends Node { + public XorNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "Xor"; } + + @Override protected String format() { return "(%1^%2)"; } + + @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 && lhs._type instanceof TypeInteger ) + 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/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index e65963db..26897a7c 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -6,7 +6,7 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.type.TypeMem; -/** Chapter 12's view of the IR; browser, transport and layout are shared. */ +/** Chapter 14's view of the IR; browser, transport and layout are shared. */ public class SimpleGraphAdapter extends GraphAdapter<Node> { @Override protected String[] edgeNames(Node n) { diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index 3aabd79f..202aa9d9 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.io.IOException; -/** Chapter 13's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 14's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture<Node> { private Parser _parser; private Node _ret; diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index 93e27c76..49dc090a 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -33,11 +33,12 @@ public class Type { static final byte TXCTRL = 3; // Ctrl flow top (mini-lattice: any-xctrl-ctrl-all) static final byte TSIMPLE = 4; // End of the Simple Types static final byte TINT = 5; // All Integers; see TypeInteger - static final byte TTUPLE = 6; // Tuples; finite collections of unrelated Types, kept in parallel - static final byte TMEM = 7; // All memory (alias 0) or A slice of memory - with specific alias - static final byte TMEMPTR = 8; // Memory pointer type - static final byte TSTRUCT = 9; // Structs; tuples with named fields - static final byte TFLD =10; // Fields into struct + static final byte TFLT = 6; // All Integers; see TypeInteger + static final byte TTUPLE = 7; // Tuples; finite collections of unrelated Types, kept in parallel + static final byte TMEM = 8; // All memory (alias 0) or A slice of memory - with specific alias + static final byte TMEMPTR = 9; // Memory pointer type + static final byte TSTRUCT =10; // Structs; tuples with named fields + static final byte TFLD =11; // Fields into struct public final byte _type; @@ -55,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); @@ -66,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. @@ -81,14 +84,16 @@ public class Type { // ---------------------------------------------------------- - // Notes on Type interning. - // At the moment it is not easy to reset the interned types - // because we hold static references to several types and these are scattered - // around. This means the INTERN cache will retain all types from - // every run of the Parser. For this to work correctly types must be - // rigorous about defining when they are the same. Also types need to be - // immutable once defined. - // The rationale for interning is performance. + // Notes on Type interning: At the moment it is not easy to reset the + // interned types because we hold static references to several types and + // these are scattered around. This means the INTERN cache will retain all + // types from every run of the Parser. For this to work correctly types + // must be rigorous about defining when they are the same. Also types need + // to be immutable once defined. The rationale for interning is + // *correctness* with cyclic type definitions. Simple structural recursive + // checks go exponential with merely sharing, but with cycles they will + // stack overflow and crash. Intering means we do not need to have sharing + // checks with every type compare, only during interning. // Factory method which interns "this" public <T extends Type> T intern() { diff --git a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java new file mode 100644 index 00000000..975c1a9e --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java @@ -0,0 +1,114 @@ +package com.seaofnodes.simple.type; + +import java.util.ArrayList; + +/** + * Float Type + */ +public class TypeFloat extends Type { + + 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); + + /** +/-64 for double; +/-32 for float, or 0 for constants */ + public final byte _sz; + + /** + * The constant value or 0 + */ + public final double _con; + + private TypeFloat(byte sz, double con) { + super(TFLT); + _sz = sz ; + _con = con; + } + private static TypeFloat make(byte sz, double con) { + return new TypeFloat(sz,con).intern(); + } + + public static TypeFloat constant(double con) { return make((byte)0, con); } + + 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+(isF32() ? "f" : ""); + } + + /** + * Display Type name in a format that's good for IR printer + */ + @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(isF32() ? "F32" : "Flt"); + } + + 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; } + + @Override + public Type xmeet(Type other) { + // Invariant from caller: 'this' != 'other' and same class (TypeFloat) + TypeFloat i = (TypeFloat)other; // Contract + // 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 i0.isF32() && i1.isF32() ? B32 : BOT; + } + + @Override + public Type dual() { + if( _sz==0 ) return this; // Constants are a self-dual + return make((byte)-_sz,0); + } + + @Override + public Type glb() { return BOT; } + + @Override public TypeFloat makeInit() { return ZERO; } + + @Override + int hash() { return (int)(Double.hashCode(_con) ^ _sz); } + @Override + public boolean eq( Type t ) { + TypeFloat i = (TypeFloat)t; // Contract + 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 5caa816d..e6e40fe2 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/main/java/com/seaofnodes/simple/type/TypeStruct.java b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 02de7cc8..8ad59a39 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -38,7 +38,7 @@ public class TypeStruct extends Type { private static final TypeStruct S1F = make("S1"); private static final TypeStruct S2F = make("S2"); public static final TypeStruct S1 = make("S1", new Field[]{ Field.make("a", TypeInteger.BOT), Field.make("s2",TypeMemPtr.make(S2F,false)) }); - private static final TypeStruct S2 = make("S2", new Field[]{ Field.make("b", TypeInteger.BOT), Field.make("s1",TypeMemPtr.make(S1F,false)) }); + private static final TypeStruct S2 = make("S2", new Field[]{ Field.make("b", TypeFloat .BOT), Field.make("s1",TypeMemPtr.make(S1F,false)) }); public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(BOT); ts.add(S1); ts.add(S2); } public int find(String fname) { diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java index 43e46a5d..c5664c9d 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(Region17,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(Region40,42,5);", stop.toString()); + assertEquals("return Phi(Region35,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 222982e7..443b0d17 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/Chapter12Test.java b/src/test/java/com/seaofnodes/simple/Chapter12Test.java index cbb50dba..cbe5c523 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -12,6 +12,17 @@ import static org.junit.Assert.assertNull; import static org.junit.Assert.assertSame; public class Chapter12Test { + @Ignore + @Test + public void testJig() { + Parser parser = new Parser( +""" +return 3.14; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 3.14;", stop.toString()); + assertEquals(3.14, Evaluator.evaluate(stop, 0)); + } @Test public void testLinkedList0() { @@ -59,22 +70,22 @@ return next.i; public void testCoRecur() { Parser parser = new Parser( """ -struct Left { int i; Right? f; } -struct Right { int f; Left? i; } -Left left = new Left; -left.i = 17; -Right right = new Right; -right.f = 314; -left.f = right; -right.i = left; -return right.i.f.i.i; +struct int0 { int i; flt0? f; } +struct flt0 { flt f; int0? i; } +int0 i0 = new int0; +i0.i = 17; +flt0 f0 = new flt0; +f0.f = 3.14; +i0.f = f0; +f0.i = i0; +return f0.i.f.i.i; """); StopNode stop = parser.parse().iterate(); assertEquals("return 17;", stop.toString()); } @Test - public void testNullReright() { + public void testNullRef0() { Parser parser = new Parser( """ struct N { N next; int i; } @@ -111,6 +122,17 @@ return n.next; catch( Exception e ) { assertEquals("Cannot store null into field *N next",e.getMessage()); } } + @Test + public void testNullRef3() { + Parser parser = new Parser( +""" +struct N { N next; int i; } +N n = new N; +n.i = 3.14; +return n.i; +"""); + assertEquals("3",com.seaofnodes.simple.evaluator.Evaluator.evaluate(parser.parse().iterate(),0).toString()); + } @Test public void testNullRef4() { @@ -137,7 +159,7 @@ struct S{}; } @Test - public void testForwardReright() { + public void testForwardRef0() { Parser parser = new Parser( """ struct S1 { S2 s; } diff --git a/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/src/test/java/com/seaofnodes/simple/Chapter13Test.java index 2929d1a4..34d71d9b 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -293,7 +293,7 @@ else { } """); StopNode stop = parser.parse().iterate(); - 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/Chapter14FloatTest.java b/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java new file mode 100644 index 00000000..f79b758d --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java @@ -0,0 +1,114 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.StopNode; +import org.junit.Ignore; +import org.junit.Test; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +public class Chapter14FloatTest { + @Test public void testNumericAssignments() { + String[][] tests = { + {"int rounded=17.3/2.5; return rounded;", "6", "6"}, + {"int rounded=arg/2.5; return rounded;", "6", "-6"}, + {"int rounded=0; rounded=arg/2.5; return rounded;", "6", "-6"}, + {"i8 rounded=arg*16.0; return rounded;", "16", "-16"}, + {"int rounded=1e100; return rounded;", "9223372036854775807", "9223372036854775807"}, + {"int rounded=-1e100; return rounded;", "-9223372036854775808", "-9223372036854775808"}, + {"int rounded=1e300*1e300-1e300*1e300; return rounded;", "0", "0"}, + {"f32 rounded=arg+16777216.0; return rounded;", "1.6777232E7", "1.6777199E7"} + }; + for( String[] test : tests ) { + var stop = new Parser(test[0]).parse().iterate(); + assertEquals(test[0],test[1],Evaluator.evaluate(stop,17).toString()); + assertEquals(test[0],test[2],Evaluator.evaluate(stop,-17).toString()); + } + } + + + @Test public void testSubZeroFloat() { + var stop = new Parser("flt x = arg; return 0-x;").parse().iterate(); + // Compare strings so +0.0 and -0.0 remain distinct. + assertEquals("0.0", Evaluator.evaluate(stop,0).toString()); + assertEquals("-1.0", Evaluator.evaluate(stop,1).toString()); + } + + @Test public void testDeadNumericReturns() { + for( String[] test : new String[][] { + {"if(1) return 7; else return 2.5;", "7"}, + {"if(0) return 7; else return 2.5;", "2.5"}, + {"return 7; return 2.5;", "7"}, + {"return 2.5; return 7;", "2.5"} + } ) { + String src = test[0]; + var stop = new Parser(src).parse().iterate(); + assertEquals(src,test[1],com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,0).toString()); + } + } + + + @Ignore + @Test + public void testJig() { + Parser parser = new Parser( +""" +return 3.14; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 3.14;", stop.toString()); + assertEquals(3.14, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testFloat() { + Parser parser = new Parser( +""" +return 3.14; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 3.14;", stop.toString()); + assertEquals(3.14, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testSquareRoot() { + Parser parser = new Parser( +""" +flt guess = arg; +while( 1 ) { + flt next = (arg/guess + guess)/2; + if( next == guess ) break; + guess = next; +} +return guess; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop10,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)/2.0));", stop.toString()); + assertEquals(3.0, Evaluator.evaluate(stop, 9)); + assertEquals(1.414213562373095, Evaluator.evaluate(stop, 2)); + } + + @Test + public void testFPOps() { + Parser parser = new Parser( +""" +flt x = arg; +return x+1==x; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return ((flt)arg==(ToFloat+1.0));", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 1)); + } + @Test + public void testReferenceFieldConvertsFloat() { + Parser parser = new Parser( +""" +struct N { N next; int i; } +N n = new N; +n.i = 3.14; +return n.i; +"""); + assertEquals("3",com.seaofnodes.simple.evaluator.Evaluator.evaluate(parser.parse().iterate(),0).toString()); + } +} 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..968054bd --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -0,0 +1,319 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.StopNode; +import org.junit.Ignore; +import org.junit.Test; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +public class Chapter14Test { + + @Ignore + @Test + public void testJig() { + Parser parser = new Parser( +""" +return 3.14; +"""); + StopNode stop = parser.parse().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().iterate(); + 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().iterate(); + 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().iterate(); + assertEquals("return Phi(Loop10,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().iterate(); + 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().iterate(); + 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().iterate(); + 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().iterate(); + 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().iterate(); + 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().iterate(); + 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().iterate(); + assertEquals("return Phi(Region29,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().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().iterate(); + 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().iterate(); + assertEquals("return Phi(Region34,.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().iterate(); + assertEquals("return ((arg>>Phi(Region33,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().iterate(); + assertEquals("return Phi(Region35,(arg==1),((flt)arg==Phi(Region24,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().iterate(); + assertEquals("return (arg==Phi(Region19,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().iterate(); + assertEquals("return (Phi(Region44,((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(); + 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 355d906b..afa35372 100644 --- a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -2,10 +2,7 @@ package com.seaofnodes.simple.evaluator; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.type.Field; -import com.seaofnodes.simple.type.TypeInteger; -import com.seaofnodes.simple.type.TypeMemPtr; -import com.seaofnodes.simple.type.TypeStruct; +import com.seaofnodes.simple.type.*; import java.lang.invoke.MethodHandle; import java.lang.invoke.MethodHandles; @@ -80,6 +77,10 @@ public class Evaluator { long in2 = vall(div.in(2)); return in2 == 0 ? 0 : vall(div.in(1)) / in2; } + private double div(DivFNode div) { + double in2 = vald(div.in(2)); + return in2 == 0 ? 0 : vald(div.in(1)) / in2; + } private Object alloc(NewNode alloc) { var type = ((TypeMemPtr)alloc.compute())._obj; @@ -115,10 +116,16 @@ public class Evaluator { if (v instanceof Number n) return n.longValue(); throw new AssertionError("Not a long " + v); } + private double vald(Node node) { + var v = val(node); + if (v instanceof Number n) return n.doubleValue(); + throw new AssertionError("Not a double " + v); + } private Object cons(ConstantNode cons) { var type = cons.compute(); if (type instanceof TypeInteger i) return i.value(); + if (type instanceof TypeFloat i) return i.value(); assert type instanceof TypeMemPtr; return null; } @@ -127,15 +134,32 @@ public class Evaluator { return switch (node) { case ConstantNode cons -> cons(cons); case AddNode add -> vall(add.in(1)) + vall(add.in(2)); + case AddFNode add -> vald(add.in(1)) + vald(add.in(2)); + case BoolNode.EQF eq -> vald(eq.in(1)) == vald(eq.in(2)) ? 1L : 0L; + case BoolNode.LEF le -> vald(le.in(1)) <= vald(le.in(2)) ? 1L : 0L; + case BoolNode.LTF lt -> vald(lt.in(1)) < vald(lt.in(2)) ? 1L : 0L; case BoolNode.EQ eq -> Objects.equals(val(eq.in(1)), val(eq.in(2))) ? 1L : 0L; case BoolNode.LE le -> vall(le.in(1)) <= vall(le.in(2)) ? 1L : 0L; case BoolNode.LT lt -> vall(lt.in(1)) < vall(lt.in(2)) ? 1L : 0L; case DivNode div -> div(div); + case DivFNode div -> div(div); case MinusNode minus -> -vall(minus.in(1)); + case MinusFNode minus -> -vald(minus.in(1)); case MulNode mul -> vall(mul.in(1)) * vall(mul.in(2)); + case MulFNode mul -> vald(mul.in(1)) * vald(mul.in(2)); 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 RoundF32Node rnd -> (double)(float)vald(rnd.in(1)); + case ToIntegerNode cvt -> (long)vald(cvt.in(1)); + case ToFloatNode cast -> (double)vall(cast.in(1)); case LoadNode load -> load(load); case StoreNode store -> store(store); case MemMergeNode merge -> MEMORY; diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java index 14baadba..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. */ @@ -87,8 +91,33 @@ public class ScriptGenerator { } - private static final Type TYPE_INT = new Type("int"); + private static final Type TYPE_FLT = new Type("flt"); + + private static class TypeInt extends Type { + + TypeInt(String name) { + super(name); + } + + @Override + boolean isa(Type other) { + return super.isa(other) || other == TYPE_FLT || other instanceof 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; @@ -347,13 +376,18 @@ 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); if (i>0) return forwardStructs.get(i-1).nullable; @@ -433,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 { @@ -546,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) { @@ -592,7 +626,7 @@ public class ScriptGenerator { */ public int genWhile() { sb.append("while("); - genExpression(TYPE_INT, true); + genExpression(TYPE_BOOL, true); sb.append(") "); loopDepth++; genStatementBlock(); @@ -710,7 +744,7 @@ public class ScriptGenerator { */ public void genExpression(Type type, boolean change) { if (change && generateInvalid()) type = getType(); - if (type != TYPE_INT) { + if (!(type instanceof TypeInt) && type != TYPE_FLT) { genUnary(type, false); return; } @@ -727,7 +761,7 @@ public class ScriptGenerator { */ public void genUnary(Type type, boolean change) { if (change && generateInvalid()) type = getType(); - if (type != TYPE_INT) { + if (!(type instanceof TypeInt) && type != TYPE_FLT) { genSuffix(type, false); return; } @@ -807,14 +841,15 @@ public class ScriptGenerator { */ public void genConst(Type type) { if (generateInvalid()) type = getType(); - if (type == TYPE_INT) { + if (type instanceof TypeInt || (type == TYPE_FLT && random.nextBoolean())) { var rand = random.nextInt(10); switch (rand) { case 0 -> sb.append("true"); case 1 -> sb.append("false"); default -> sb.append(random.nextInt(1<<(rand-2))); } - + } else if (type == TYPE_FLT) { + sb.append(random.nextFloat()); } else if (type instanceof TypeNullable n) { if ((n.base instanceof TypeStruct s && s.fields == null) || random.nextBoolean()) { sb.append("null"); |
