summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorCliff Click <cliffc@acm.org>2024-07-17 18:11:56 +0100
committerCliff Click <cliffc@acm.org>2025-04-24 14:38:36 -0700
commit2274f4b59f9dedcd71a0438595cc65f98351b0a3 (patch)
treeb99d43df63cb36e00c828cb21117dee2dd6d194f
parentc46a61a0fa31c56ffeac0431d166f3637024f523 (diff)
downloadSimple-2274f4b59f9dedcd71a0438595cc65f98351b0a3.tar.gz
Simple-2274f4b59f9dedcd71a0438595cc65f98351b0a3.zip
Chapter 12: Floats
Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk> Co-authored-by: Thalia Archibald <thalia@archibald.dev> Co-authored-by: tannal <tannal2409@gmail.com> Co-authored-by: hadha <helsgithub15@gmail.com> Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: RobertObkircher <robert.obkircher@gmail.com> Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>
-rw-r--r--README.md2
-rw-r--r--docs/chapter12/12-grammar.md134
-rw-r--r--docs/chapter12/Makefile12
-rw-r--r--docs/chapter12/README.md58
-rw-r--r--docs/chapter12/lattice.gv182
-rw-r--r--docs/chapter12/lattice.svg598
-rw-r--r--src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java12
-rw-r--r--src/main/java/com/seaofnodes/simple/IterPeeps.java2
-rw-r--r--src/main/java/com/seaofnodes/simple/Parser.java125
-rw-r--r--src/main/java/com/seaofnodes/simple/node/AddFNode.java44
-rw-r--r--src/main/java/com/seaofnodes/simple/node/AddNode.java2
-rw-r--r--src/main/java/com/seaofnodes/simple/node/BoolNode.java30
-rw-r--r--src/main/java/com/seaofnodes/simple/node/CFGNode.java9
-rw-r--r--src/main/java/com/seaofnodes/simple/node/DivFNode.java46
-rw-r--r--src/main/java/com/seaofnodes/simple/node/DivNode.java1
-rw-r--r--src/main/java/com/seaofnodes/simple/node/LoadNode.java10
-rw-r--r--src/main/java/com/seaofnodes/simple/node/LoopNode.java9
-rw-r--r--src/main/java/com/seaofnodes/simple/node/MinusFNode.java36
-rw-r--r--src/main/java/com/seaofnodes/simple/node/MinusNode.java1
-rw-r--r--src/main/java/com/seaofnodes/simple/node/MulFNode.java51
-rw-r--r--src/main/java/com/seaofnodes/simple/node/MulNode.java1
-rw-r--r--src/main/java/com/seaofnodes/simple/node/MultiNode.java8
-rw-r--r--src/main/java/com/seaofnodes/simple/node/NeverNode.java4
-rw-r--r--src/main/java/com/seaofnodes/simple/node/Node.java24
-rw-r--r--src/main/java/com/seaofnodes/simple/node/NotNode.java4
-rw-r--r--src/main/java/com/seaofnodes/simple/node/PhiNode.java4
-rw-r--r--src/main/java/com/seaofnodes/simple/node/RegionNode.java4
-rw-r--r--src/main/java/com/seaofnodes/simple/node/StartNode.java2
-rw-r--r--src/main/java/com/seaofnodes/simple/node/StopNode.java2
-rw-r--r--src/main/java/com/seaofnodes/simple/node/SubFNode.java44
-rw-r--r--src/main/java/com/seaofnodes/simple/node/SubNode.java2
-rw-r--r--src/main/java/com/seaofnodes/simple/node/ToFloatNode.java30
-rw-r--r--src/main/java/com/seaofnodes/simple/type/Type.java11
-rw-r--r--src/main/java/com/seaofnodes/simple/type/TypeFloat.java101
-rw-r--r--src/test/java/com/seaofnodes/simple/Chapter08Test.java1
-rw-r--r--src/test/java/com/seaofnodes/simple/Chapter09Test.java1
-rw-r--r--src/test/java/com/seaofnodes/simple/Chapter10Test.java6
-rw-r--r--src/test/java/com/seaofnodes/simple/Chapter11Test.java42
-rw-r--r--src/test/java/com/seaofnodes/simple/Chapter12Test.java64
-rw-r--r--src/test/java/com/seaofnodes/simple/SchedulerTest.java4
-rw-r--r--src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java24
-rw-r--r--src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java119
42 files changed, 1678 insertions, 188 deletions
diff --git a/README.md b/README.md
index e3aabbc6..13ac0dce 100644
--- a/README.md
+++ b/README.md
@@ -55,7 +55,7 @@ The Simple language is styled after a subset of C or Java.
general memory edges in SSA. Equivalence class aliasing. Null pointer
analysis. Peephole optimization around load-after-store/store-after-store.
* [Chapter 11](docs/chapter11/README.md): Global Code Motion - Scheduling.
-* Chapter 12: Float type.
+* [Chapter 12](docs/chapter12/README.md): Float type.
* Chapter 13: Nested references in Structs.
* Chapter 14: Narrow primitive types (e.g. bytes)
* Chapter 15: One dimensional static length array type, with array loads and stores.
diff --git a/docs/chapter12/12-grammar.md b/docs/chapter12/12-grammar.md
new file mode 100644
index 00000000..f0fe2e40
--- /dev/null
+++ b/docs/chapter12/12-grammar.md
@@ -0,0 +1,134 @@
+# Grammar for Chapter 12
+
+```antlrv4
+grammar SimpleLanguage;
+
+program
+ : statement+ EOF
+ ;
+
+statement
+ : returnStatement
+ | structDeclaration
+ | declStatement
+ | blockStatment
+ | expressionStatement
+ | ifStatement
+ | whileStatement
+ | breakStatement
+ | continueStatment
+ | metaStatement
+ ;
+
+PRIMTYPE
+ : 'int'
+ | 'flt'
+ ;
+
+field
+ : PRIMTYPE IDENTIFIER ';'
+ ;
+
+fields
+ : field+
+ ;
+
+structDeclaration
+ : 'struct' IDENTIFIER '{' fields '}'
+ ;
+
+whileStatement
+ : 'while' '(' expression ')' statement
+ ;
+
+breakStatement
+ : 'break' ';'
+ ;
+
+continueStatement
+ : 'continue' ';'
+ ;
+
+ifStatement
+ : 'if' '(' expression ')' statement ('else' statement)?
+ ;
+
+metaStatement
+ : '#showGraph' ';'
+ ;
+
+expressionStatement
+ : IDENTIFIER '=' expression ';'
+ | fieldExpression '=' expression ';'
+ ;
+
+blockStatement
+ : '{' statement+ '}'
+ ;
+
+structName
+ : IDENTIFIER
+ ;
+
+declStatement
+ : PRIMTYPE IDENTIFIER '=' expression ';'
+ | structName ('?')? IDENTIFIER '=' expression ';'
+ ;
+
+returnStatement
+ : 'return' expression ';'
+ ;
+
+expression
+ : comparisonExpression
+ ;
+
+comparisonExpression
+ : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)*
+ ;
+
+additiveExpression
+ : multiplicativeExpression (('+' | '-') multiplicativeExpression)*
+ ;
+
+multiplicativeExpression
+ : unaryExpression (('*' | '/') unaryExpression)*
+ ;
+
+unaryExpression
+ : ('-') unaryExpression
+ | '!' unaryExpression
+ | primaryExpression
+ ;
+
+newExpression
+ : 'new' IDENTIFIER
+ ;
+
+fieldExpression
+ : primaryExpresson '.' IDENTIFIER
+ ;
+
+primaryExpression
+ : IDENTIFIER
+ | INTEGER_LITERAL
+ | 'true'
+ | 'false'
+ | 'null'
+ | newExpression
+ | '(' expression ')'
+ | fieldExpression
+ ;
+
+INTEGER_LITERAL
+ : [1-9][0-9]*
+ | [0]
+ ;
+
+IDENTIFIER
+ : NON_DIGIT (NON_DIGIT | DIGIT)*
+ ;
+
+NON_DIGIT: [a-zA-Z_];
+DEC_DIGIT: [0-9];
+```
diff --git a/docs/chapter12/Makefile b/docs/chapter12/Makefile
new file mode 100644
index 00000000..12659b8f
--- /dev/null
+++ b/docs/chapter12/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/chapter12/README.md b/docs/chapter12/README.md
new file mode 100644
index 00000000..8f4a2d2d
--- /dev/null
+++ b/docs/chapter12/README.md
@@ -0,0 +1,58 @@
+# Chapter 12: Floats
+
+# Table of Contents
+
+1. [Float](#floats)
+
+In this chapter, we add a floating point type and values.
+
+You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter12) 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-chapter11...linear-chapter12) it to the previous chapter.
+
+## Floats
+
+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
+```
+
+There is no corresponding way right now to round a `flt` back to an `int`:
+```java
+int x = 3.14; // error
+```
+
+Here is Newton's method to 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.0, 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 |
+
+And their own section in the Type lattice:
+
+Within the Type Lattice, we now add the following domain:
+
+* <font style="background-color:aqua">Float type</font> - Float values. The same shape as the Integer values, but floats
+ with a TOP, BOT and constants
+
+![Graph1](./lattice.svg)
+
diff --git a/docs/chapter12/lattice.gv b/docs/chapter12/lattice.gv
new file mode 100644
index 00000000..eec7cc1d
--- /dev/null
+++ b/docs/chapter12/lattice.gv
@@ -0,0 +1,182 @@
+digraph Lattice {
+ compound = true;
+ // Define nodes
+ splines=false;
+ node [shape=circle, style=filled];
+ nodesep=0.6;
+
+ TOP [label=<<B>⊤</B >>, fillcolor=black, fontcolor=white];
+ BOT [label=<<B>⊥</B>>, fillcolor=black, fontcolor=white];
+
+ // ----------------------
+ // Control
+ XCTRL [label=<<B>⊤</B >:ctrl>, fillcolor=yellow, shape=oval];
+ CTRL [label=<<B>⊥</B>:ctrl>, fillcolor=yellow, shape=oval];
+
+ TOP -> XCTRL;
+ XCTRL -> CTRL;
+ CTRL -> BOT;
+
+ // ----------------------
+ // Integers
+ INT_TOP [label=<<B>⊤</B >:int>, fillcolor=lightblue, shape=oval];
+ INT_BOT [label=<<B>⊥</B>:int>, fillcolor=lightblue, shape=oval];
+
+ INT_MINDOTS [label="...", fillcolor=lightblue, shape=oval];
+ INT_ZERO [label="0" , fillcolor=lightblue];
+ INT_MAXDOTS [label="...", fillcolor=lightblue, shape=oval];
+
+ TOP -> INT_TOP;
+ INT_TOP -> INT_MINDOTS;
+ INT_TOP -> INT_ZERO;
+ INT_TOP -> INT_MAXDOTS;
+ INT_MINDOTS -> INT_BOT;
+ INT_ZERO -> INT_BOT;
+ INT_MAXDOTS -> INT_BOT;
+ INT_BOT -> BOT;
+
+ INT_MINDOTS -> INT_ZERO -> INT_MAXDOTS [style=invis];
+
+ // ----------------------
+ // Integers
+ FLT_TOP [label=<<B>⊤</B >:flt>, fillcolor=aqua, shape=oval];
+ FLT_BOT [label=<<B>⊥</B>:flt>, fillcolor=aqua, shape=oval];
+
+ FLT_MINDOTS [label="...", fillcolor=aqua, shape=oval];
+ FLT_ZERO [label="0" , fillcolor=aqua];
+ FLT_MAXDOTS [label="...", fillcolor=aqua, shape=oval];
+
+ TOP -> FLT_TOP;
+ FLT_TOP -> FLT_MINDOTS;
+ FLT_TOP -> FLT_ZERO;
+ FLT_TOP -> FLT_MAXDOTS;
+ FLT_MINDOTS -> FLT_BOT;
+ FLT_ZERO -> FLT_BOT;
+ FLT_MAXDOTS -> FLT_BOT;
+ FLT_BOT -> BOT;
+
+ FLT_MINDOTS -> FLT_ZERO -> FLT_MAXDOTS [style=invis];
+
+ // ----------------------
+ // Pointers, just a boolean nil/not and a struct
+ PTR [shape=none, fillcolor=none, label=<
+ <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+ <TR><TD BGCOLOR="green"><FONT color="white">*ptr</FONT></TD></TR>
+ <TR><TD BGCOLOR="lightgreen">struct</TD></TR>
+ </TABLE>
+ >];
+ PTR0 [shape=none, fillcolor=none, label=<
+ <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+ <TR><TD BGCOLOR="green"><FONT color="white">*ptr?</FONT></TD></TR>
+ <TR><TD BGCOLOR="lightgreen">struct</TD></TR>
+ </TABLE>
+ >];
+
+ TOP -> PTR;
+ PTR -> PTR0;
+ PTR0 -> BOT;
+
+ // ----------------------
+ // Structs
+ STRUCT_TOP [label=<<B>⊤</B >:struct>, fillcolor=lightgreen, shape=oval];
+ STRUCT_BOT [label=<<B>⊥</B>:struct>, fillcolor=lightgreen, shape=oval];
+
+ STRUCT_S1 [shape=none, fillcolor=none, label=<
+ <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+ <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR>
+ </TABLE>
+ >];
+ STRUCT_S2 [shape=none, fillcolor=none, label=<
+ <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+ <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR>
+ <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR>
+ </TABLE>
+ >];
+ STRUCT_SN [shape=none, fillcolor=none, label=<
+ <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+ <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR>
+ <TR><TD BGCOLOR="lightgreen">... </TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR>
+ <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR>
+ </TABLE>
+ >];
+
+
+ TOP -> STRUCT_TOP;
+ STRUCT_TOP -> STRUCT_S1;
+ STRUCT_TOP -> STRUCT_S2;
+ STRUCT_TOP -> STRUCT_SN;
+ STRUCT_S1 -> STRUCT_BOT;
+ STRUCT_S2 -> STRUCT_BOT;
+ STRUCT_SN -> STRUCT_BOT;
+ STRUCT_BOT -> BOT;
+
+ STRUCT_S1 -> STRUCT_S2 -> STRUCT_SN [style=invis];
+
+ // ----------------------
+ // Memory
+ MEM_TOP [label=<<B>⊤</B >:mem>, fillcolor=blue, fontcolor=white, shape=oval];
+ MEM_BOT [label=<<B>⊥</B>:mem>, fillcolor=blue, fontcolor=white, shape=oval];
+ MEM_ALIAS1 [label="#1" , fillcolor=blue, fontcolor=white];
+ MEM_ALIASDOTS [label="..." , fillcolor=blue, fontcolor=white, shape=oval];
+ MEM_ALIASN [label="#n" , fillcolor=blue, fontcolor=white];
+
+ TOP -> MEM_TOP;
+ MEM_TOP -> MEM_ALIAS1;
+ MEM_TOP -> MEM_ALIASDOTS;
+ MEM_TOP -> MEM_ALIASN;
+ MEM_ALIAS1 -> MEM_BOT;
+ MEM_ALIASDOTS -> MEM_BOT;
+ MEM_ALIASN -> MEM_BOT;
+ MEM_BOT -> BOT;
+
+ MEM_ALIAS1 -> MEM_ALIASDOTS -> MEM_ALIASN [style=invis];
+
+ // ----------------------
+ // Tuples
+
+ TUPLE_TOP [label=<<B>⊤</B >:tuple>, fillcolor=pink, shape=oval];
+ TUPLE_BOT [label=<<B>⊥</B>:tuple>, fillcolor=pink, shape=oval];
+
+ TUPLE1 [shape=none, fillcolor=none, label=<
+ <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+ <TH><TD BGCOLOR="pink">Tuple</TD></TH>
+ <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR>
+ </TABLE>
+ >];
+ TUPLE2 [shape=none, fillcolor=none, label=<
+ <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+ <TH><TD BGCOLOR="pink">Tuple</TD></TH>
+ <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR>
+ <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR>
+ </TABLE>
+ >];
+ TUPLEN [shape=none, fillcolor=none, label=<
+ <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+ <TH><TD BGCOLOR="pink">Tuple</TD></TH>
+ <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR>
+ <TR><TD BGCOLOR="black" ><FONT color="white">...</FONT></TD></TR>
+ <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR>
+ </TABLE>
+ >];
+
+
+ TOP -> TUPLE_TOP;
+ TUPLE_TOP -> TUPLE1;
+ TUPLE_TOP -> TUPLE2;
+ TUPLE_TOP -> TUPLEN;
+ TUPLE1 -> TUPLE_BOT;
+ TUPLE2 -> TUPLE_BOT;
+ TUPLEN -> TUPLE_BOT;
+ TUPLE_BOT -> BOT;
+
+ // ----------------------
+ // Additional customization
+ {rank=same; TOP;}
+ {rank=same; INT_TOP; FLT_TOP; XCTRL; STRUCT_TOP; MEM_TOP; TUPLE_TOP}
+ {rank=same; INT_MINDOTS; INT_ZERO; INT_MAXDOTS;
+ FLT_MINDOTS; FLT_ZERO; FLT_MAXDOTS;
+ STRUCT_S1; STRUCT_S2; STRUCT_SN;
+ MEM_ALIAS1; MEM_ALIASDOTS; MEM_ALIASN;}
+ {rank=same; INT_BOT; FLT_BOT; CTRL; STRUCT_BOT; MEM_BOT; TUPLE_BOT}
+ {rank=same; BOT;}
+}
diff --git a/docs/chapter12/lattice.svg b/docs/chapter12/lattice.svg
new file mode 100644
index 00000000..1bb4f692
--- /dev/null
+++ b/docs/chapter12/lattice.svg
@@ -0,0 +1,598 @@
+<?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="1602pt" height="440pt"
+ viewBox="0.00 0.00 1601.51 440.50" 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 436.5)">
+<title>Lattice</title>
+<polygon fill="white" stroke="none" points="-4,4 -4,-436.5 1597.51,-436.5 1597.51,4 -4,4"/>
+<!-- TOP -->
+<g id="node1" class="node">
+<title>TOP</title>
+<ellipse fill="black" stroke="black" cx="630.51" cy="-411.37" rx="21.12" ry="21.12"/>
+<text text-anchor="start" x="622.63" y="-406.95" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00" fill="white">⊤</text>
+</g>
+<!-- XCTRL -->
+<g id="node3" class="node">
+<title>XCTRL</title>
+<ellipse fill="yellow" stroke="black" cx="36.51" cy="-327.75" rx="36.51" ry="18"/>
+<text text-anchor="start" x="17.76" y="-323.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text>
+<text text-anchor="start" x="33.51" y="-323.7" font-family="Times New Roman,serif" font-size="14.00">:ctrl</text>
+</g>
+<!-- TOP&#45;&gt;XCTRL -->
+<g id="edge1" class="edge">
+<title>TOP&#45;&gt;XCTRL</title>
+<path fill="none" stroke="black" d="M609.37,-407.47C523.96,-395.73 203.25,-351.66 82.7,-335.1"/>
+<polygon fill="black" stroke="black" points="83.22,-331.63 72.84,-333.74 82.27,-338.57 83.22,-331.63"/>
+</g>
+<!-- INT_TOP -->
+<g id="node5" class="node">
+<title>INT_TOP</title>
+<ellipse fill="lightblue" stroke="black" cx="226.51" cy="-327.75" rx="33.95" ry="18"/>
+<text text-anchor="start" x="209.63" y="-323.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text>
+<text text-anchor="start" x="225.38" y="-323.7" font-family="Times New Roman,serif" font-size="14.00">:int</text>
+</g>
+<!-- TOP&#45;&gt;INT_TOP -->
+<g id="edge4" class="edge">
+<title>TOP&#45;&gt;INT_TOP</title>
+<path fill="none" stroke="black" d="M609.64,-406.16C546.23,-393.34 354.92,-354.69 269.04,-337.34"/>
+<polygon fill="black" stroke="black" points="269.87,-333.94 259.37,-335.39 268.48,-340.8 269.87,-333.94"/>
+</g>
+<!-- FLT_TOP -->
+<g id="node10" class="node">
+<title>FLT_TOP</title>
+<ellipse fill="aqua" stroke="black" cx="489.51" cy="-327.75" rx="32.41" ry="18"/>
+<text text-anchor="start" x="473.76" y="-323.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text>
+<text text-anchor="start" x="489.51" y="-323.7" font-family="Times New Roman,serif" font-size="14.00">:flt</text>
+</g>
+<!-- TOP&#45;&gt;FLT_TOP -->
+<g id="edge14" class="edge">
+<title>TOP&#45;&gt;FLT_TOP</title>
+<path fill="none" stroke="black" d="M612.36,-399.87C589.31,-386.52 549.15,-363.27 521.04,-347"/>
+<polygon fill="black" stroke="black" points="523,-344.09 512.59,-342.11 519.49,-350.15 523,-344.09"/>
+</g>
+<!-- PTR -->
+<g id="node15" class="node">
+<title>PTR</title>
+<polygon fill="none" stroke="none" points="657.51,-354.25 603.51,-354.25 603.51,-301.25 657.51,-301.25 657.51,-354.25"/>
+<polygon fill="green" stroke="none" points="612.51,-327.75 612.51,-350.25 648.51,-350.25 648.51,-327.75 612.51,-327.75"/>
+<polygon fill="none" stroke="black" points="612.51,-327.75 612.51,-350.25 648.51,-350.25 648.51,-327.75 612.51,-327.75"/>
+<text text-anchor="start" x="619.63" y="-333.95" font-family="Times New Roman,serif" font-size="14.00" fill="white">*ptr</text>
+<polygon fill="lightgreen" stroke="none" points="612.51,-305.25 612.51,-327.75 648.51,-327.75 648.51,-305.25 612.51,-305.25"/>
+<polygon fill="none" stroke="black" points="612.51,-305.25 612.51,-327.75 648.51,-327.75 648.51,-305.25 612.51,-305.25"/>
+<text text-anchor="start" x="615.51" y="-311.45" font-family="Times New Roman,serif" font-size="14.00">struct</text>
+</g>
+<!-- TOP&#45;&gt;PTR -->
+<g id="edge24" class="edge">
+<title>TOP&#45;&gt;PTR</title>
+<path fill="none" stroke="black" d="M630.51,-389.78C630.51,-382.39 630.51,-373.83 630.51,-365.49"/>
+<polygon fill="black" stroke="black" points="634.01,-365.52 630.51,-355.52 627.01,-365.52 634.01,-365.52"/>
+</g>
+<!-- STRUCT_TOP -->
+<g id="node17" class="node">
+<title>STRUCT_TOP</title>
+<ellipse fill="lightgreen" stroke="black" cx="806.51" cy="-327.75" rx="44.7" ry="18"/>
+<text text-anchor="start" x="781.76" y="-323.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text>
+<text text-anchor="start" x="797.51" y="-323.7" font-family="Times New Roman,serif" font-size="14.00">:struct</text>
+</g>
+<!-- TOP&#45;&gt;STRUCT_TOP -->
+<g id="edge27" class="edge">
+<title>TOP&#45;&gt;STRUCT_TOP</title>
+<path fill="none" stroke="black" d="M649.68,-401.48C677.9,-388.39 731.22,-363.66 767.79,-346.71"/>
+<polygon fill="black" stroke="black" points="769.12,-349.95 776.71,-342.57 766.17,-343.6 769.12,-349.95"/>
+</g>
+<!-- MEM_TOP -->
+<g id="node22" class="node">
+<title>MEM_TOP</title>
+<ellipse fill="blue" stroke="black" cx="1147.51" cy="-327.75" rx="43.67" ry="18"/>
+<text text-anchor="start" x="1123.51" y="-323.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00" fill="white">⊤</text>
+<text text-anchor="start" x="1139.26" y="-323.7" font-family="Times New Roman,serif" font-size="14.00" fill="white">:mem</text>
+</g>
+<!-- TOP&#45;&gt;MEM_TOP -->
+<g id="edge37" class="edge">
+<title>TOP&#45;&gt;MEM_TOP</title>
+<path fill="none" stroke="black" d="M651.42,-407.07C726.59,-395.2 984.56,-354.47 1095.79,-336.91"/>
+<polygon fill="black" stroke="black" points="1096.21,-340.39 1105.54,-335.37 1095.12,-333.48 1096.21,-340.39"/>
+</g>
+<!-- TUPLE_TOP -->
+<g id="node27" class="node">
+<title>TUPLE_TOP</title>
+<ellipse fill="pink" stroke="black" cx="1420.51" cy="-327.75" rx="42.65" ry="18"/>
+<text text-anchor="start" x="1397.26" y="-323.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text>
+<text text-anchor="start" x="1413.01" y="-323.7" font-family="Times New Roman,serif" font-size="14.00">:tuple</text>
+</g>
+<!-- TOP&#45;&gt;TUPLE_TOP -->
+<g id="edge47" class="edge">
+<title>TOP&#45;&gt;TUPLE_TOP</title>
+<path fill="none" stroke="black" d="M651.64,-408.19C755.41,-397.47 1212.34,-350.26 1368.21,-334.15"/>
+<polygon fill="black" stroke="black" points="1368.24,-337.67 1377.83,-333.16 1367.52,-330.7 1368.24,-337.67"/>
+</g>
+<!-- BOT -->
+<g id="node2" class="node">
+<title>BOT</title>
+<ellipse fill="black" stroke="black" cx="630.51" cy="-21.12" rx="21.12" ry="21.12"/>
+<text text-anchor="start" x="622.63" y="-16.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00" fill="white">⊥</text>
+</g>
+<!-- CTRL -->
+<g id="node4" class="node">
+<title>CTRL</title>
+<ellipse fill="yellow" stroke="black" cx="36.51" cy="-104.75" rx="36.51" ry="18"/>
+<text text-anchor="start" x="17.76" y="-100.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text>
+<text text-anchor="start" x="33.51" y="-100.7" font-family="Times New Roman,serif" font-size="14.00">:ctrl</text>
+</g>
+<!-- XCTRL&#45;&gt;CTRL -->
+<g id="edge2" class="edge">
+<title>XCTRL&#45;&gt;CTRL</title>
+<path fill="none" stroke="black" d="M36.51,-309.5C36.51,-271.02 36.51,-181.25 36.51,-134.4"/>
+<polygon fill="black" stroke="black" points="40.01,-134.45 36.51,-124.45 33.01,-134.45 40.01,-134.45"/>
+</g>
+<!-- CTRL&#45;&gt;BOT -->
+<g id="edge3" class="edge">
+<title>CTRL&#45;&gt;BOT</title>
+<path fill="none" stroke="black" d="M71.45,-98.95C177.66,-84.35 495.68,-40.65 598.24,-26.56"/>
+<polygon fill="black" stroke="black" points="598.46,-30.06 607.89,-25.23 597.5,-23.13 598.46,-30.06"/>
+</g>
+<!-- INT_MINDOTS -->
+<g id="node7" class="node">
+<title>INT_MINDOTS</title>
+<ellipse fill="lightblue" stroke="black" cx="89.51" cy="-216.25" rx="27" ry="18"/>
+<text text-anchor="middle" x="89.51" y="-211.2" font-family="Times New Roman,serif" font-size="14.00">...</text>
+</g>
+<!-- INT_TOP&#45;&gt;INT_MINDOTS -->
+<g id="edge5" class="edge">
+<title>INT_TOP&#45;&gt;INT_MINDOTS</title>
+<path fill="none" stroke="black" d="M208.32,-312.21C184.36,-293.06 142.09,-259.28 114.97,-237.6"/>
+<polygon fill="black" stroke="black" points="117.24,-234.93 107.24,-231.42 112.87,-240.4 117.24,-234.93"/>
+</g>
+<!-- INT_ZERO -->
+<g id="node8" class="node">
+<title>INT_ZERO</title>
+<ellipse fill="lightblue" stroke="black" cx="177.51" cy="-216.25" rx="18" ry="18"/>
+<text text-anchor="middle" x="177.51" y="-211.2" font-family="Times New Roman,serif" font-size="14.00">0</text>
+</g>
+<!-- INT_TOP&#45;&gt;INT_ZERO -->
+<g id="edge6" class="edge">
+<title>INT_TOP&#45;&gt;INT_ZERO</title>
+<path fill="none" stroke="black" d="M219.07,-310.12C211.12,-292.37 198.43,-264.01 189.16,-243.29"/>
+<polygon fill="black" stroke="black" points="192.44,-242.05 185.16,-234.35 186.05,-244.91 192.44,-242.05"/>
+</g>
+<!-- INT_MAXDOTS -->
+<g id="node9" class="node">
+<title>INT_MAXDOTS</title>
+<ellipse fill="lightblue" stroke="black" cx="265.51" cy="-216.25" rx="27" ry="18"/>
+<text text-anchor="middle" x="265.51" y="-211.2" font-family="Times New Roman,serif" font-size="14.00">...</text>
+</g>
+<!-- INT_TOP&#45;&gt;INT_MAXDOTS -->
+<g id="edge7" class="edge">
+<title>INT_TOP&#45;&gt;INT_MAXDOTS</title>
+<path fill="none" stroke="black" d="M232.6,-309.64C238.76,-292.36 248.36,-265.39 255.61,-245.04"/>
+<polygon fill="black" stroke="black" points="258.89,-246.26 258.95,-235.66 252.3,-243.91 258.89,-246.26"/>
+</g>
+<!-- INT_BOT -->
+<g id="node6" class="node">
+<title>INT_BOT</title>
+<ellipse fill="lightblue" stroke="black" cx="226.51" cy="-104.75" rx="33.95" ry="18"/>
+<text text-anchor="start" x="209.63" y="-100.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text>
+<text text-anchor="start" x="225.38" y="-100.7" font-family="Times New Roman,serif" font-size="14.00">:int</text>
+</g>
+<!-- INT_BOT&#45;&gt;BOT -->
+<g id="edge11" class="edge">
+<title>INT_BOT&#45;&gt;BOT</title>
+<path fill="none" stroke="black" d="M257.87,-97.41C333.02,-82.23 522.71,-43.9 598.5,-28.59"/>
+<polygon fill="black" stroke="black" points="599.06,-32.05 608.17,-26.64 597.68,-25.19 599.06,-32.05"/>
+</g>
+<!-- INT_MINDOTS&#45;&gt;INT_BOT -->
+<g id="edge8" class="edge">
+<title>INT_MINDOTS&#45;&gt;INT_BOT</title>
+<path fill="none" stroke="black" d="M106.31,-201.82C129.55,-183.25 171.76,-149.5 199.47,-127.36"/>
+<polygon fill="black" stroke="black" points="201.45,-130.25 207.08,-121.28 197.08,-124.79 201.45,-130.25"/>
+</g>
+<!-- INT_MINDOTS&#45;&gt;INT_ZERO -->
+<!-- INT_ZERO&#45;&gt;INT_BOT -->
+<g id="edge9" class="edge">
+<title>INT_ZERO&#45;&gt;INT_BOT</title>
+<path fill="none" stroke="black" d="M184.53,-199.56C192.29,-182.22 204.94,-153.96 214.32,-132.98"/>
+<polygon fill="black" stroke="black" points="217.51,-134.42 218.4,-123.87 211.12,-131.56 217.51,-134.42"/>
+</g>
+<!-- INT_ZERO&#45;&gt;INT_MAXDOTS -->
+<!-- INT_MAXDOTS&#45;&gt;INT_BOT -->
+<g id="edge10" class="edge">
+<title>INT_MAXDOTS&#45;&gt;INT_BOT</title>
+<path fill="none" stroke="black" d="M259.59,-198.62C253.44,-181.35 243.71,-154.05 236.4,-133.51"/>
+<polygon fill="black" stroke="black" points="239.78,-132.57 233.12,-124.32 233.18,-134.92 239.78,-132.57"/>
+</g>
+<!-- FLT_MINDOTS -->
+<g id="node12" class="node">
+<title>FLT_MINDOTS</title>
+<ellipse fill="aqua" stroke="black" cx="362.51" cy="-216.25" rx="27" ry="18"/>
+<text text-anchor="middle" x="362.51" y="-211.2" font-family="Times New Roman,serif" font-size="14.00">...</text>
+</g>
+<!-- FLT_TOP&#45;&gt;FLT_MINDOTS -->
+<g id="edge15" class="edge">
+<title>FLT_TOP&#45;&gt;FLT_MINDOTS</title>
+<path fill="none" stroke="black" d="M472.38,-311.98C450.43,-293.06 412.23,-260.12 387.15,-238.5"/>
+<polygon fill="black" stroke="black" points="389.57,-235.96 379.71,-232.08 385,-241.26 389.57,-235.96"/>
+</g>
+<!-- FLT_ZERO -->
+<g id="node13" class="node">
+<title>FLT_ZERO</title>
+<ellipse fill="aqua" stroke="black" cx="450.51" cy="-216.25" rx="18" ry="18"/>
+<text text-anchor="middle" x="450.51" y="-211.2" font-family="Times New Roman,serif" font-size="14.00">0</text>
+</g>
+<!-- FLT_TOP&#45;&gt;FLT_ZERO -->
+<g id="edge16" class="edge">
+<title>FLT_TOP&#45;&gt;FLT_ZERO</title>
+<path fill="none" stroke="black" d="M483.42,-309.64C477.19,-292.16 467.43,-264.76 460.16,-244.33"/>
+<polygon fill="black" stroke="black" points="463.47,-243.2 456.81,-234.95 456.87,-245.54 463.47,-243.2"/>
+</g>
+<!-- FLT_MAXDOTS -->
+<g id="node14" class="node">
+<title>FLT_MAXDOTS</title>
+<ellipse fill="aqua" stroke="black" cx="538.51" cy="-216.25" rx="27" ry="18"/>
+<text text-anchor="middle" x="538.51" y="-211.2" font-family="Times New Roman,serif" font-size="14.00">...</text>
+</g>
+<!-- FLT_TOP&#45;&gt;FLT_MAXDOTS -->
+<g id="edge17" class="edge">
+<title>FLT_TOP&#45;&gt;FLT_MAXDOTS</title>
+<path fill="none" stroke="black" d="M496.95,-310.12C504.76,-292.67 517.15,-264.98 526.38,-244.36"/>
+<polygon fill="black" stroke="black" points="529.49,-245.97 530.38,-235.42 523.1,-243.12 529.49,-245.97"/>
+</g>
+<!-- FLT_BOT -->
+<g id="node11" class="node">
+<title>FLT_BOT</title>
+<ellipse fill="aqua" stroke="black" cx="489.51" cy="-104.75" rx="32.41" ry="18"/>
+<text text-anchor="start" x="473.76" y="-100.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text>
+<text text-anchor="start" x="489.51" y="-100.7" font-family="Times New Roman,serif" font-size="14.00">:flt</text>
+</g>
+<!-- FLT_BOT&#45;&gt;BOT -->
+<g id="edge21" class="edge">
+<title>FLT_BOT&#45;&gt;BOT</title>
+<path fill="none" stroke="black" d="M511.23,-91.17C535.78,-76.96 575.81,-53.79 602.65,-38.25"/>
+<polygon fill="black" stroke="black" points="604.36,-41.31 611.26,-33.27 600.85,-35.25 604.36,-41.31"/>
+</g>
+<!-- FLT_MINDOTS&#45;&gt;FLT_BOT -->
+<g id="edge18" class="edge">
+<title>FLT_MINDOTS&#45;&gt;FLT_BOT</title>
+<path fill="none" stroke="black" d="M378.59,-201.38C400.21,-182.74 438.85,-149.43 464.33,-127.46"/>
+<polygon fill="black" stroke="black" points="466.31,-130.37 471.6,-121.19 461.74,-125.07 466.31,-130.37"/>
+</g>
+<!-- FLT_MINDOTS&#45;&gt;FLT_ZERO -->
+<!-- FLT_ZERO&#45;&gt;FLT_BOT -->
+<g id="edge19" class="edge">
+<title>FLT_ZERO&#45;&gt;FLT_BOT</title>
+<path fill="none" stroke="black" d="M456.26,-199.09C462.41,-181.82 472.27,-154.14 479.66,-133.39"/>
+<polygon fill="black" stroke="black" points="482.91,-134.71 482.97,-124.12 476.31,-132.36 482.91,-134.71"/>
+</g>
+<!-- FLT_ZERO&#45;&gt;FLT_MAXDOTS -->
+<!-- FLT_MAXDOTS&#45;&gt;FLT_BOT -->
+<g id="edge20" class="edge">
+<title>FLT_MAXDOTS&#45;&gt;FLT_BOT</title>
+<path fill="none" stroke="black" d="M531.07,-198.62C523.26,-181.17 510.87,-153.48 501.64,-132.86"/>
+<polygon fill="black" stroke="black" points="504.92,-131.62 497.64,-123.92 498.53,-134.47 504.92,-131.62"/>
+</g>
+<!-- PTR0 -->
+<g id="node16" class="node">
+<title>PTR0</title>
+<polygon fill="none" stroke="none" points="657.51,-131.25 603.51,-131.25 603.51,-78.25 657.51,-78.25 657.51,-131.25"/>
+<polygon fill="green" stroke="none" points="612.51,-104.75 612.51,-127.25 648.51,-127.25 648.51,-104.75 612.51,-104.75"/>
+<polygon fill="none" stroke="black" points="612.51,-104.75 612.51,-127.25 648.51,-127.25 648.51,-104.75 612.51,-104.75"/>
+<text text-anchor="start" x="616.63" y="-110.95" font-family="Times New Roman,serif" font-size="14.00" fill="white">*ptr?</text>
+<polygon fill="lightgreen" stroke="none" points="612.51,-82.25 612.51,-104.75 648.51,-104.75 648.51,-82.25 612.51,-82.25"/>
+<polygon fill="none" stroke="black" points="612.51,-82.25 612.51,-104.75 648.51,-104.75 648.51,-82.25 612.51,-82.25"/>
+<text text-anchor="start" x="615.51" y="-88.45" font-family="Times New Roman,serif" font-size="14.00">struct</text>
+</g>
+<!-- PTR&#45;&gt;PTR0 -->
+<g id="edge25" class="edge">
+<title>PTR&#45;&gt;PTR0</title>
+<path fill="none" stroke="black" d="M630.51,-301.29C630.51,-261.89 630.51,-187.62 630.51,-142.52"/>
+<polygon fill="black" stroke="black" points="634.01,-142.68 630.51,-132.68 627.01,-142.68 634.01,-142.68"/>
+</g>
+<!-- PTR0&#45;&gt;BOT -->
+<g id="edge26" class="edge">
+<title>PTR0&#45;&gt;BOT</title>
+<path fill="none" stroke="black" d="M630.51,-78.37C630.51,-70.63 630.51,-62.03 630.51,-53.93"/>
+<polygon fill="black" stroke="black" points="634.01,-54.09 630.51,-44.09 627.01,-54.09 634.01,-54.09"/>
+</g>
+<!-- STRUCT_S1 -->
+<g id="node19" class="node">
+<title>STRUCT_S1</title>
+<polygon fill="none" stroke="none" points="781.38,-234.25 695.63,-234.25 695.63,-198.25 781.38,-198.25 781.38,-234.25"/>
+<polygon fill="lightgreen" stroke="none" points="703.63,-205 703.63,-227.5 734.38,-227.5 734.38,-205 703.63,-205"/>
+<polygon fill="none" stroke="black" points="703.63,-205 703.63,-227.5 734.38,-227.5 734.38,-205 703.63,-205"/>
+<text text-anchor="start" x="706.63" y="-211.2" font-family="Times New Roman,serif" font-size="14.00">field</text>
+<defs>
+<linearGradient id="l_0" gradientUnits="userSpaceOnUse" x1="740.1" y1="-224.2" x2="767.67" y2="-208.29" >
+<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/>
+<stop offset="1" style="stop-color:green;stop-opacity:1.;"/>
+</linearGradient>
+</defs>
+<polygon fill="url(#l_0)" stroke="none" points="734.38,-205 734.38,-227.5 773.38,-227.5 773.38,-205 734.38,-205"/>
+<polygon fill="none" stroke="black" points="734.38,-205 734.38,-227.5 773.38,-227.5 773.38,-205 734.38,-205"/>
+<text text-anchor="start" x="737.38" y="-211.2" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text>
+</g>
+<!-- STRUCT_TOP&#45;&gt;STRUCT_S1 -->
+<g id="edge28" class="edge">
+<title>STRUCT_TOP&#45;&gt;STRUCT_S1</title>
+<path fill="none" stroke="black" d="M796.18,-310.12C785.25,-292.51 767.83,-264.46 754.99,-243.79"/>
+<polygon fill="black" stroke="black" points="757.98,-241.97 749.73,-235.32 752.03,-245.66 757.98,-241.97"/>
+</g>
+<!-- STRUCT_S2 -->
+<g id="node20" class="node">
+<title>STRUCT_S2</title>
+<polygon fill="none" stroke="none" points="910.38,-242.75 824.63,-242.75 824.63,-189.75 910.38,-189.75 910.38,-242.75"/>
+<polygon fill="lightgreen" stroke="none" points="832.63,-216.25 832.63,-238.75 863.38,-238.75 863.38,-216.25 832.63,-216.25"/>
+<polygon fill="none" stroke="black" points="832.63,-216.25 832.63,-238.75 863.38,-238.75 863.38,-216.25 832.63,-216.25"/>
+<text text-anchor="start" x="835.63" y="-222.45" font-family="Times New Roman,serif" font-size="14.00">field</text>
+<defs>
+<linearGradient id="l_1" gradientUnits="userSpaceOnUse" x1="869.1" y1="-235.45" x2="896.67" y2="-219.54" >
+<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/>
+<stop offset="1" style="stop-color:green;stop-opacity:1.;"/>
+</linearGradient>
+</defs>
+<polygon fill="url(#l_1)" stroke="none" points="863.38,-216.25 863.38,-238.75 902.38,-238.75 902.38,-216.25 863.38,-216.25"/>
+<polygon fill="none" stroke="black" points="863.38,-216.25 863.38,-238.75 902.38,-238.75 902.38,-216.25 863.38,-216.25"/>
+<text text-anchor="start" x="866.38" y="-222.45" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text>
+<polygon fill="lightgreen" stroke="none" points="832.63,-193.75 832.63,-216.25 863.38,-216.25 863.38,-193.75 832.63,-193.75"/>
+<polygon fill="none" stroke="black" points="832.63,-193.75 832.63,-216.25 863.38,-216.25 863.38,-193.75 832.63,-193.75"/>
+<text text-anchor="start" x="835.63" y="-199.95" font-family="Times New Roman,serif" font-size="14.00">field</text>
+<defs>
+<linearGradient id="l_2" gradientUnits="userSpaceOnUse" x1="869.1" y1="-212.95" x2="896.67" y2="-197.04" >
+<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/>
+<stop offset="1" style="stop-color:green;stop-opacity:1.;"/>
+</linearGradient>
+</defs>
+<polygon fill="url(#l_2)" stroke="none" points="863.38,-193.75 863.38,-216.25 902.38,-216.25 902.38,-193.75 863.38,-193.75"/>
+<polygon fill="none" stroke="black" points="863.38,-193.75 863.38,-216.25 902.38,-216.25 902.38,-193.75 863.38,-193.75"/>
+<text text-anchor="start" x="866.38" y="-199.95" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text>
+</g>
+<!-- STRUCT_TOP&#45;&gt;STRUCT_S2 -->
+<g id="edge29" class="edge">
+<title>STRUCT_TOP&#45;&gt;STRUCT_S2</title>
+<path fill="none" stroke="black" d="M815.77,-310.12C824.25,-294.9 837.07,-271.89 847.82,-252.58"/>
+<polygon fill="black" stroke="black" points="850.84,-254.36 852.65,-243.92 844.73,-250.95 850.84,-254.36"/>
+</g>
+<!-- STRUCT_SN -->
+<g id="node21" class="node">
+<title>STRUCT_SN</title>
+<polygon fill="none" stroke="none" points="1039.38,-254 953.63,-254 953.63,-178.5 1039.38,-178.5 1039.38,-254"/>
+<polygon fill="lightgreen" stroke="none" points="961.63,-227.5 961.63,-250 992.38,-250 992.38,-227.5 961.63,-227.5"/>
+<polygon fill="none" stroke="black" points="961.63,-227.5 961.63,-250 992.38,-250 992.38,-227.5 961.63,-227.5"/>
+<text text-anchor="start" x="964.63" y="-233.7" font-family="Times New Roman,serif" font-size="14.00">field</text>
+<defs>
+<linearGradient id="l_3" gradientUnits="userSpaceOnUse" x1="998.1" y1="-246.7" x2="1025.67" y2="-230.79" >
+<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/>
+<stop offset="1" style="stop-color:green;stop-opacity:1.;"/>
+</linearGradient>
+</defs>
+<polygon fill="url(#l_3)" stroke="none" points="992.38,-227.5 992.38,-250 1031.38,-250 1031.38,-227.5 992.38,-227.5"/>
+<polygon fill="none" stroke="black" points="992.38,-227.5 992.38,-250 1031.38,-250 1031.38,-227.5 992.38,-227.5"/>
+<text text-anchor="start" x="995.38" y="-233.7" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text>
+<polygon fill="lightgreen" stroke="none" points="961.63,-205 961.63,-227.5 992.38,-227.5 992.38,-205 961.63,-205"/>
+<polygon fill="none" stroke="black" points="961.63,-205 961.63,-227.5 992.38,-227.5 992.38,-205 961.63,-205"/>
+<text text-anchor="start" x="967.63" y="-211.2" font-family="Times New Roman,serif" font-size="14.00">... &#160;</text>
+<defs>
+<linearGradient id="l_4" gradientUnits="userSpaceOnUse" x1="998.1" y1="-224.2" x2="1025.67" y2="-208.29" >
+<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/>
+<stop offset="1" style="stop-color:green;stop-opacity:1.;"/>
+</linearGradient>
+</defs>
+<polygon fill="url(#l_4)" stroke="none" points="992.38,-205 992.38,-227.5 1031.38,-227.5 1031.38,-205 992.38,-205"/>
+<polygon fill="none" stroke="black" points="992.38,-205 992.38,-227.5 1031.38,-227.5 1031.38,-205 992.38,-205"/>
+<text text-anchor="start" x="995.38" y="-211.2" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text>
+<polygon fill="lightgreen" stroke="none" points="961.63,-182.5 961.63,-205 992.38,-205 992.38,-182.5 961.63,-182.5"/>
+<polygon fill="none" stroke="black" points="961.63,-182.5 961.63,-205 992.38,-205 992.38,-182.5 961.63,-182.5"/>
+<text text-anchor="start" x="964.63" y="-188.7" font-family="Times New Roman,serif" font-size="14.00">field</text>
+<defs>
+<linearGradient id="l_5" gradientUnits="userSpaceOnUse" x1="998.1" y1="-201.7" x2="1025.67" y2="-185.79" >
+<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/>
+<stop offset="1" style="stop-color:green;stop-opacity:1.;"/>
+</linearGradient>
+</defs>
+<polygon fill="url(#l_5)" stroke="none" points="992.38,-182.5 992.38,-205 1031.38,-205 1031.38,-182.5 992.38,-182.5"/>
+<polygon fill="none" stroke="black" points="992.38,-182.5 992.38,-205 1031.38,-205 1031.38,-182.5 992.38,-182.5"/>
+<text text-anchor="start" x="995.38" y="-188.7" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text>
+</g>
+<!-- STRUCT_TOP&#45;&gt;STRUCT_SN -->
+<g id="edge30" class="edge">
+<title>STRUCT_TOP&#45;&gt;STRUCT_SN</title>
+<path fill="none" stroke="black" d="M831.35,-312.43C859.88,-295.99 907.49,-268.55 944.28,-247.35"/>
+<polygon fill="black" stroke="black" points="945.64,-250.61 952.55,-242.58 942.14,-244.54 945.64,-250.61"/>
+</g>
+<!-- STRUCT_BOT -->
+<g id="node18" class="node">
+<title>STRUCT_BOT</title>
+<ellipse fill="lightgreen" stroke="black" cx="806.51" cy="-104.75" rx="44.7" ry="18"/>
+<text text-anchor="start" x="781.76" y="-100.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text>
+<text text-anchor="start" x="797.51" y="-100.7" font-family="Times New Roman,serif" font-size="14.00">:struct</text>
+</g>
+<!-- STRUCT_BOT&#45;&gt;BOT -->
+<g id="edge34" class="edge">
+<title>STRUCT_BOT&#45;&gt;BOT</title>
+<path fill="none" stroke="black" d="M777.84,-90.45C745.37,-75.39 692.74,-50.98 659.95,-35.78"/>
+<polygon fill="black" stroke="black" points="661.57,-32.67 651.03,-31.64 658.63,-39.02 661.57,-32.67"/>
+</g>
+<!-- STRUCT_S1&#45;&gt;STRUCT_BOT -->
+<g id="edge31" class="edge">
+<title>STRUCT_S1&#45;&gt;STRUCT_BOT</title>
+<path fill="none" stroke="black" d="M748.84,-198.62C759.77,-181.01 777.19,-152.96 790.02,-132.29"/>
+<polygon fill="black" stroke="black" points="792.98,-134.16 795.29,-123.82 787.04,-130.47 792.98,-134.16"/>
+</g>
+<!-- STRUCT_S1&#45;&gt;STRUCT_S2 -->
+<!-- STRUCT_S2&#45;&gt;STRUCT_BOT -->
+<g id="edge32" class="edge">
+<title>STRUCT_S2&#45;&gt;STRUCT_BOT</title>
+<path fill="none" stroke="black" d="M853.36,-189.85C843.77,-172.63 831.12,-149.92 821.38,-132.44"/>
+<polygon fill="black" stroke="black" points="824.68,-131.18 816.76,-124.15 818.57,-134.59 824.68,-131.18"/>
+</g>
+<!-- STRUCT_S2&#45;&gt;STRUCT_SN -->
+<!-- STRUCT_SN&#45;&gt;STRUCT_BOT -->
+<g id="edge33" class="edge">
+<title>STRUCT_SN&#45;&gt;STRUCT_BOT</title>
+<path fill="none" stroke="black" d="M953.87,-190.67C919.81,-171.04 872.69,-143.89 840.98,-125.62"/>
+<polygon fill="black" stroke="black" points="842.99,-122.73 832.58,-120.77 839.49,-128.8 842.99,-122.73"/>
+</g>
+<!-- MEM_ALIAS1 -->
+<g id="node24" class="node">
+<title>MEM_ALIAS1</title>
+<ellipse fill="blue" stroke="black" cx="1102.51" cy="-216.25" rx="20.13" ry="20.13"/>
+<text text-anchor="middle" x="1102.51" y="-211.2" font-family="Times New Roman,serif" font-size="14.00" fill="white">#1</text>
+</g>
+<!-- MEM_TOP&#45;&gt;MEM_ALIAS1 -->
+<g id="edge38" class="edge">
+<title>MEM_TOP&#45;&gt;MEM_ALIAS1</title>
+<path fill="none" stroke="black" d="M1140.48,-309.64C1133.47,-292.59 1122.58,-266.09 1114.26,-245.84"/>
+<polygon fill="black" stroke="black" points="1117.55,-244.65 1110.52,-236.73 1111.08,-247.31 1117.55,-244.65"/>
+</g>
+<!-- MEM_ALIASDOTS -->
+<g id="node25" class="node">
+<title>MEM_ALIASDOTS</title>
+<ellipse fill="blue" stroke="black" cx="1192.51" cy="-216.25" rx="27" ry="18"/>
+<text text-anchor="middle" x="1192.51" y="-211.2" font-family="Times New Roman,serif" font-size="14.00" fill="white">...</text>
+</g>
+<!-- MEM_TOP&#45;&gt;MEM_ALIASDOTS -->
+<g id="edge39" class="edge">
+<title>MEM_TOP&#45;&gt;MEM_ALIASDOTS</title>
+<path fill="none" stroke="black" d="M1154.54,-309.64C1161.71,-292.18 1172.96,-264.82 1181.35,-244.4"/>
+<polygon fill="black" stroke="black" points="1184.54,-245.86 1185.1,-235.28 1178.06,-243.2 1184.54,-245.86"/>
+</g>
+<!-- MEM_ALIASN -->
+<g id="node26" class="node">
+<title>MEM_ALIASN</title>
+<ellipse fill="blue" stroke="black" cx="1282.51" cy="-216.25" rx="20.13" ry="20.13"/>
+<text text-anchor="middle" x="1282.51" y="-211.2" font-family="Times New Roman,serif" font-size="14.00" fill="white">#n</text>
+</g>
+<!-- MEM_TOP&#45;&gt;MEM_ALIASN -->
+<g id="edge40" class="edge">
+<title>MEM_TOP&#45;&gt;MEM_ALIASN</title>
+<path fill="none" stroke="black" d="M1166.56,-311.29C1190.65,-291.76 1232.11,-258.13 1258.38,-236.82"/>
+<polygon fill="black" stroke="black" points="1260.57,-239.55 1266.13,-230.53 1256.16,-234.11 1260.57,-239.55"/>
+</g>
+<!-- MEM_BOT -->
+<g id="node23" class="node">
+<title>MEM_BOT</title>
+<ellipse fill="blue" stroke="black" cx="1147.51" cy="-104.75" rx="43.67" ry="18"/>
+<text text-anchor="start" x="1123.51" y="-100.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00" fill="white">⊥</text>
+<text text-anchor="start" x="1139.26" y="-100.7" font-family="Times New Roman,serif" font-size="14.00" fill="white">:mem</text>
+</g>
+<!-- MEM_BOT&#45;&gt;BOT -->
+<g id="edge44" class="edge">
+<title>MEM_BOT&#45;&gt;BOT</title>
+<path fill="none" stroke="black" d="M1107.37,-97.41C1008.15,-81.75 752.85,-41.44 662.66,-27.2"/>
+<polygon fill="black" stroke="black" points="663.45,-23.78 653.03,-25.68 662.36,-30.7 663.45,-23.78"/>
+</g>
+<!-- MEM_ALIAS1&#45;&gt;MEM_BOT -->
+<g id="edge41" class="edge">
+<title>MEM_ALIAS1&#45;&gt;MEM_BOT</title>
+<path fill="none" stroke="black" d="M1109.94,-197.17C1117.07,-179.82 1127.93,-153.39 1136.15,-133.4"/>
+<polygon fill="black" stroke="black" points="1139.37,-134.75 1139.94,-124.17 1132.9,-132.09 1139.37,-134.75"/>
+</g>
+<!-- MEM_ALIAS1&#45;&gt;MEM_ALIASDOTS -->
+<!-- MEM_ALIASDOTS&#45;&gt;MEM_BOT -->
+<g id="edge42" class="edge">
+<title>MEM_ALIASDOTS&#45;&gt;MEM_BOT</title>
+<path fill="none" stroke="black" d="M1185.67,-198.62C1178.58,-181.35 1167.36,-154.05 1158.92,-133.51"/>
+<polygon fill="black" stroke="black" points="1162.17,-132.22 1155.13,-124.3 1155.7,-134.88 1162.17,-132.22"/>
+</g>
+<!-- MEM_ALIASDOTS&#45;&gt;MEM_ALIASN -->
+<!-- MEM_ALIASN&#45;&gt;MEM_BOT -->
+<g id="edge43" class="edge">
+<title>MEM_ALIASN&#45;&gt;MEM_BOT</title>
+<path fill="none" stroke="black" d="M1267.02,-202.69C1244.75,-184.62 1203.29,-151 1175.55,-128.49"/>
+<polygon fill="black" stroke="black" points="1177.86,-125.86 1167.89,-122.28 1173.45,-131.3 1177.86,-125.86"/>
+</g>
+<!-- TUPLE1 -->
+<g id="node29" class="node">
+<title>TUPLE1</title>
+<polygon fill="none" stroke="none" points="1399.51,-242.75 1345.51,-242.75 1345.51,-189.75 1399.51,-189.75 1399.51,-242.75"/>
+<polygon fill="pink" stroke="none" points="1353.76,-216.25 1353.76,-238.75 1391.26,-238.75 1391.26,-216.25 1353.76,-216.25"/>
+<polygon fill="none" stroke="black" points="1353.76,-216.25 1353.76,-238.75 1391.26,-238.75 1391.26,-216.25 1353.76,-216.25"/>
+<text text-anchor="start" x="1356.76" y="-222.45" font-family="Times New Roman,serif" font-size="14.00">Tuple</text>
+<polygon fill="black" stroke="none" points="1353.76,-193.75 1353.76,-216.25 1391.26,-216.25 1391.26,-193.75 1353.76,-193.75"/>
+<polygon fill="none" stroke="black" points="1353.76,-193.75 1353.76,-216.25 1391.26,-216.25 1391.26,-193.75 1353.76,-193.75"/>
+<text text-anchor="start" x="1360.88" y="-199.95" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+</g>
+<!-- TUPLE_TOP&#45;&gt;TUPLE1 -->
+<g id="edge48" class="edge">
+<title>TUPLE_TOP&#45;&gt;TUPLE1</title>
+<path fill="none" stroke="black" d="M1413.01,-309.64C1406.37,-294.48 1396.45,-271.87 1388.1,-252.81"/>
+<polygon fill="black" stroke="black" points="1391.35,-251.51 1384.13,-243.76 1384.94,-254.32 1391.35,-251.51"/>
+</g>
+<!-- TUPLE2 -->
+<g id="node30" class="node">
+<title>TUPLE2</title>
+<polygon fill="none" stroke="none" points="1496.51,-254 1442.51,-254 1442.51,-178.5 1496.51,-178.5 1496.51,-254"/>
+<polygon fill="pink" stroke="none" points="1450.76,-227.5 1450.76,-250 1488.26,-250 1488.26,-227.5 1450.76,-227.5"/>
+<polygon fill="none" stroke="black" points="1450.76,-227.5 1450.76,-250 1488.26,-250 1488.26,-227.5 1450.76,-227.5"/>
+<text text-anchor="start" x="1453.76" y="-233.7" font-family="Times New Roman,serif" font-size="14.00">Tuple</text>
+<polygon fill="black" stroke="none" points="1450.76,-205 1450.76,-227.5 1488.26,-227.5 1488.26,-205 1450.76,-205"/>
+<polygon fill="none" stroke="black" points="1450.76,-205 1450.76,-227.5 1488.26,-227.5 1488.26,-205 1450.76,-205"/>
+<text text-anchor="start" x="1457.88" y="-211.2" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+<polygon fill="black" stroke="none" points="1450.76,-182.5 1450.76,-205 1488.26,-205 1488.26,-182.5 1450.76,-182.5"/>
+<polygon fill="none" stroke="black" points="1450.76,-182.5 1450.76,-205 1488.26,-205 1488.26,-182.5 1450.76,-182.5"/>
+<text text-anchor="start" x="1457.88" y="-188.7" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+</g>
+<!-- TUPLE_TOP&#45;&gt;TUPLE2 -->
+<g id="edge49" class="edge">
+<title>TUPLE_TOP&#45;&gt;TUPLE2</title>
+<path fill="none" stroke="black" d="M1428.17,-309.64C1433.64,-297.4 1441.29,-280.3 1448.53,-264.14"/>
+<polygon fill="black" stroke="black" points="1451.68,-265.65 1452.57,-255.09 1445.3,-262.79 1451.68,-265.65"/>
+</g>
+<!-- TUPLEN -->
+<g id="node31" class="node">
+<title>TUPLEN</title>
+<polygon fill="none" stroke="none" points="1593.51,-265.25 1539.51,-265.25 1539.51,-167.25 1593.51,-167.25 1593.51,-265.25"/>
+<polygon fill="pink" stroke="none" points="1547.76,-238.75 1547.76,-261.25 1585.26,-261.25 1585.26,-238.75 1547.76,-238.75"/>
+<polygon fill="none" stroke="black" points="1547.76,-238.75 1547.76,-261.25 1585.26,-261.25 1585.26,-238.75 1547.76,-238.75"/>
+<text text-anchor="start" x="1550.76" y="-244.95" font-family="Times New Roman,serif" font-size="14.00">Tuple</text>
+<polygon fill="black" stroke="none" points="1547.76,-216.25 1547.76,-238.75 1585.26,-238.75 1585.26,-216.25 1547.76,-216.25"/>
+<polygon fill="none" stroke="black" points="1547.76,-216.25 1547.76,-238.75 1585.26,-238.75 1585.26,-216.25 1547.76,-216.25"/>
+<text text-anchor="start" x="1554.88" y="-222.45" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+<polygon fill="black" stroke="none" points="1547.76,-193.75 1547.76,-216.25 1585.26,-216.25 1585.26,-193.75 1547.76,-193.75"/>
+<polygon fill="none" stroke="black" points="1547.76,-193.75 1547.76,-216.25 1585.26,-216.25 1585.26,-193.75 1547.76,-193.75"/>
+<text text-anchor="start" x="1560.88" y="-199.95" font-family="Times New Roman,serif" font-size="14.00" fill="white">...</text>
+<polygon fill="black" stroke="none" points="1547.76,-171.25 1547.76,-193.75 1585.26,-193.75 1585.26,-171.25 1547.76,-171.25"/>
+<polygon fill="none" stroke="black" points="1547.76,-171.25 1547.76,-193.75 1585.26,-193.75 1585.26,-171.25 1547.76,-171.25"/>
+<text text-anchor="start" x="1554.88" y="-177.45" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+</g>
+<!-- TUPLE_TOP&#45;&gt;TUPLEN -->
+<g id="edge50" class="edge">
+<title>TUPLE_TOP&#45;&gt;TUPLEN</title>
+<path fill="none" stroke="black" d="M1440.81,-311.52C1463.97,-294.15 1502.28,-265.42 1530.53,-244.23"/>
+<polygon fill="black" stroke="black" points="1532.58,-247.07 1538.48,-238.27 1528.38,-241.47 1532.58,-247.07"/>
+</g>
+<!-- TUPLE_BOT -->
+<g id="node28" class="node">
+<title>TUPLE_BOT</title>
+<ellipse fill="pink" stroke="black" cx="1420.51" cy="-104.75" rx="42.65" ry="18"/>
+<text text-anchor="start" x="1397.26" y="-100.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text>
+<text text-anchor="start" x="1413.01" y="-100.7" font-family="Times New Roman,serif" font-size="14.00">:tuple</text>
+</g>
+<!-- TUPLE_BOT&#45;&gt;BOT -->
+<g id="edge54" class="edge">
+<title>TUPLE_BOT&#45;&gt;BOT</title>
+<path fill="none" stroke="black" d="M1379.42,-99.5C1240.27,-85.13 788.44,-38.44 663.04,-25.49"/>
+<polygon fill="black" stroke="black" points="663.44,-22.01 653.13,-24.46 662.72,-28.97 663.44,-22.01"/>
+</g>
+<!-- TUPLE1&#45;&gt;TUPLE_BOT -->
+<g id="edge51" class="edge">
+<title>TUPLE1&#45;&gt;TUPLE_BOT</title>
+<path fill="none" stroke="black" d="M1383.64,-189.85C1391.12,-172.8 1400.96,-150.34 1408.59,-132.93"/>
+<polygon fill="black" stroke="black" points="1411.61,-134.78 1412.41,-124.21 1405.19,-131.97 1411.61,-134.78"/>
+</g>
+<!-- TUPLE2&#45;&gt;TUPLE_BOT -->
+<g id="edge52" class="edge">
+<title>TUPLE2&#45;&gt;TUPLE_BOT</title>
+<path fill="none" stroke="black" d="M1453.19,-178.79C1446.51,-163.86 1438.92,-146.89 1432.73,-133.07"/>
+<polygon fill="black" stroke="black" points="1436.02,-131.83 1428.74,-124.13 1429.63,-134.69 1436.02,-131.83"/>
+</g>
+<!-- TUPLEN&#45;&gt;TUPLE_BOT -->
+<g id="edge53" class="edge">
+<title>TUPLEN&#45;&gt;TUPLE_BOT</title>
+<path fill="none" stroke="black" d="M1539.73,-195.16C1514.22,-176.03 1475.9,-147.29 1449.64,-127.59"/>
+<polygon fill="black" stroke="black" points="1451.86,-124.89 1441.76,-121.69 1447.66,-130.49 1451.86,-124.89"/>
+</g>
+</g>
+</svg>
diff --git a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
index 14540d46..4e0a31d5 100644
--- a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
+++ b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
@@ -10,7 +10,6 @@ public abstract class GlobalCodeMotion {
// Node.use(0) is always a block tail (either IfNode or head of the
// following block). There are no unreachable infinite loops.
public static void buildCFG( StopNode stop ) {
- fixLoops(stop);
schedEarly();
Parser.SCHEDULED = true;
schedLate(Parser.START);
@@ -20,7 +19,7 @@ public abstract class GlobalCodeMotion {
// Backwards walk on the CFG only, looking for unreachable code - which has
// to be an infinite loop. Insert a bogus never-taken exit to Stop, so the
// loop becomes reachable. Also, set loop nesting depth
- private static void fixLoops(StopNode stop) {
+ static void fixLoops(StopNode stop) {
// Backwards walk from Stop, looking for unreachable code
BitSet visit = new BitSet();
HashSet<CFGNode> unreach = new HashSet<>();
@@ -120,7 +119,7 @@ public abstract class GlobalCodeMotion {
ns[i].setDef(0,late[i]);
}
- // Forwards post-order pass. Schedule all outputs first, then draw an
+ // Forwards post-order pass. Schedule all outputs first, then draw a
// idom-tree line from the LCA of uses to the early schedule. Schedule is
// legal anywhere on this line; pick the most control-dependent (largest
// idepth) in the shallowest loop nest.
@@ -148,13 +147,13 @@ public abstract class GlobalCodeMotion {
assert early != null;
CFGNode lca = null;
for( Node use : n._outputs )
- lca = use_block(n,use, late).idom(lca);
+ lca = use_block(n,use, late)._idom(lca,null);
// Loads may need anti-dependencies, raising their LCA
if( n instanceof LoadNode load )
lca = find_anti_dep(lca,load,early,late);
- // Walk up from the LCA to the early, looking for best place. This is the
+ // Walk up from the LCA to the early, looking for best place. This is
// lowest execution frequency, approximated by least loop depth and
// deepest control flow.
CFGNode best = lca;
@@ -214,6 +213,7 @@ public abstract class GlobalCodeMotion {
break;
case LoadNode ld: break; // Loads do not cause anti-deps on other loads
case ReturnNode ret: break; // Load must already be ahead of Return
+ case NeverNode never: break;
default: throw Utils.TODO();
}
}
@@ -226,7 +226,7 @@ public abstract class GlobalCodeMotion {
for( ; stblk != defblk.idom(); stblk = stblk.idom() ) {
// Store and Load overlap, need anti-dependence
if( stblk._anti==load._nid ) {
- lca = stblk.idom(lca); // Raise Loads LCA
+ lca = stblk._idom(lca,null); // Raise Loads LCA
if( lca == stblk && st != null && Utils.find(st._inputs,load) == -1 ) // And if something moved,
st.addDef(load); // Add anti-dep as well
return lca; // Cap this stores' anti-dep to here
diff --git a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java
index b2b76777..121d0233 100644
--- a/src/main/java/com/seaofnodes/simple/IterPeeps.java
+++ b/src/main/java/com/seaofnodes/simple/IterPeeps.java
@@ -92,6 +92,8 @@ public abstract class IterPeeps {
n.kill(); // Just plain dead
}
+ // Break infinite loops, forcing a Never-branch to exit
+ GlobalCodeMotion.fixLoops(stop);
if( show )
System.out.println(new GraphVisualizer().generateDotOutput(stop,null,null));
GlobalCodeMotion.buildCFG(stop);
diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java
index e367f499..1a223726 100644
--- a/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/src/main/java/com/seaofnodes/simple/Parser.java
@@ -56,6 +56,7 @@ public class Parser {
add("continue");
add("else");
add("false");
+ add("flt");
add("if");
add("int");
add("new");
@@ -76,13 +77,15 @@ public class Parser {
ScopeNode _continueScope;
ScopeNode _breakScope;
- // Mapping from a Struct name to a Struct.
- public static Map<String, TypeStruct> OBJS = new HashMap<>();
+ // Mapping from a type name to a Type.
+ public static HashMap<String, Type> TYPES = new HashMap<>();
public Parser(String source, TypeInteger arg) {
Node.reset();
IterPeeps.reset();
- OBJS.clear();
+ TYPES.clear();
+ TYPES.put("int",TypeInteger.BOT);
+ TYPES.put("flt",TypeFloat .BOT);
SCHEDULED = false;
_lexer = new Lexer(source);
_scope = new ScopeNode();
@@ -157,7 +160,6 @@ public class Parser {
private Node parseStatement() {
if( false ) return null;
else if (matchx("return") ) return parseReturn();
- else if (matchx("int") ) return parseDecl(TypeInteger.BOT);
else if (match ("{") ) return require(parseBlock(),"}");
else if (matchx("if") ) return parseIf();
else if (matchx("while") ) return parseWhile();
@@ -174,13 +176,14 @@ public class Parser {
/**
* Parse a struct field.
* <pre>
- * int IDENTIFIER ;
+ * type IDENTIFIER ;
* </pre>
*/
private Field parseField(String sname) {
- if( matchx("int") ) // Currently only parsing "int" type fields
- return require(Field.make(requireId().intern(),TypeInteger.BOT),";");
- throw errorSyntax("A field type is expected, only type 'int' is supported at present");
+ Type t = type();
+ if( t==null )
+ throw errorSyntax("Requires a field type, found '"+_lexer.getAnyNextToken()+"'");
+ return require(Field.make(requireId().intern(),t),";");
}
/**
@@ -193,7 +196,7 @@ public class Parser {
private Node parseStruct() {
if (_xScopes.size() > 1) throw errorSyntax("struct declarations can only appear in top level scope");
String typeName = requireId();
- if ( OBJS.containsKey(typeName)) throw errorSyntax("struct '" + typeName + "' cannot be redefined");
+ if ( TYPES.containsKey(typeName)) throw errorSyntax("struct '" + typeName + "' cannot be redefined");
ArrayList<Field> fields = new ArrayList<>();
require("{");
while (!peek('}') && !_lexer.isEOF()) {
@@ -204,7 +207,7 @@ public class Parser {
require("}");
// Build and install the TypeStruct
TypeStruct ts = TypeStruct.make(typeName, fields);
- OBJS.put(typeName, ts); // Insert the struct name in the collection of all struct names
+ TYPES.put(typeName, ts); // Insert the struct name in the collection of all struct names
START.addMemProj(ts, _scope); // Insert memory edges
return parseStatement();
}
@@ -423,15 +426,17 @@ public class Parser {
if( _scope.define(name,t,expr) == null )
throw error("Redefining name '" + name + "'");
} else {
- Node n = _scope.lookup(name);
- t = _scope.lookupDeclaredType(name);
- if( n==null )
+ if( _scope.lookup(name)==null )
throw error("Undefined name '" + name + "'");
- _scope.update(name,expr);
+ t = _scope.lookupDeclaredType(name);
}
+ // Auto-widen int to float
+ if( expr._type instanceof TypeInteger && t instanceof TypeFloat )
+ expr = new ToFloatNode(expr).peephole();
+ // Type is sane
if( !expr._type.isa(t) )
throw error("Type " + expr._type.str() + " is not of declared type " + t.str());
- return expr;
+ return _scope.update(name,expr);
}
// Parse a type-or-null
@@ -439,35 +444,13 @@ public class Parser {
int old = _lexer._position;
String tname = _lexer.matchId();
if( tname==null ) return null;
- if( tname.equals("int") ) return TypeInteger.BOT;
- TypeStruct obj = OBJS.get(tname);
- if( obj != null )
- return TypeMemPtr.make(obj,match("?"));
- // Not a type; unwind the parse
- _lexer._position = old;
- return null;
- }
-
- /**
- * Parses a declStatement
- *
- * <pre>
- * type name = expression ';'
- * </pre>
- * @return an expression {@link Node}
- */
- private Node parseDecl(Type t) {
- var name = requireId();
- var expr = match(";")
- // Assign a null value
- ? new ConstantNode(t.makeInit()).peephole()
- // Assign "= expr;"
- : require(require("=").parseExpression(), ";");
- if( !expr._type.isa(t) )
- throw error("Type " + expr._type.str() + " is not of declared type " + t.str());
- if( _scope.define(name,t,expr) == null )
- throw error("Redefining name '" + name + "'");
- return expr;
+ Type t = TYPES.get(tname);
+ if( t == null ) {
+ // Not a type; unwind the parse
+ _lexer._position = old;
+ return null;
+ }
+ return t instanceof TypeStruct obj ? TypeMemPtr.make(obj,match("?")) : t;
}
@@ -504,7 +487,7 @@ public class Parser {
else break;
// Peepholes can fire, but lhs is already "hooked", kept alive
lhs.setDef(idx,parseAddition());
- lhs = lhs.peephole();
+ lhs = lhs.widen().peephole();
if( negate ) // Extra negate for !=
lhs = new NotNode(lhs).peephole();
}
@@ -527,7 +510,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;
}
@@ -541,14 +524,14 @@ public class Parser {
* @return a multiply expression {@link Node}, never {@code null}
*/
private Node parseMultiplication() {
- var lhs = parseUnary();
+ var lhs = parseUnary(); boolean mul;
while( true ) {
if( false ) ;
else if( match("*") ) lhs = new MulNode(lhs,null);
else if( match("/") ) lhs = new DivNode(lhs,null);
else break;
lhs.setDef(2,parseUnary());
- lhs = lhs.peephole();
+ lhs = lhs.widen().peephole();
}
return lhs;
}
@@ -562,7 +545,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());
}
@@ -576,15 +559,15 @@ public class Parser {
* @return a primary {@link Node}, never {@code null}
*/
private Node parsePrimary() {
- if( _lexer.isNumber() ) return parseIntegerLiteral();
+ if( _lexer.isNumber(_lexer.peek()) ) return parseLiteral();
if( match("(") ) return require(parseExpression(), ")");
if( matchx("true" ) ) return new ConstantNode(TypeInteger.constant(1)).peephole();
if( matchx("false") ) return ZERO;
if( matchx("null" ) ) return new ConstantNode(TypeMemPtr.NULLPTR).peephole();
if( matchx("new") ) {
String structName = requireId();
- TypeStruct obj = OBJS.get(structName);
- if( obj == null) throw errorSyntax("Unknown struct type '" + structName + "'");
+ Type t = TYPES.get(structName);
+ if( t == null || !(t instanceof TypeStruct obj) ) throw errorSyntax("Unknown struct type '" + structName + "'");
return newStruct(obj);
}
String name = _lexer.matchId();
@@ -630,6 +613,7 @@ public class Parser {
throw error("Expected struct reference but got " + expr._type.str());
String name = requireId().intern();
+ if( expr._type == TypeMemPtr.TOP ) throw error("Accessing field '" + name + "' from null");
int idx = ptr._obj==null ? -1 : ptr._obj.find(name);
if( idx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'");
int alias = START._aliasStarts.get(ptr._obj._name)+idx;
@@ -653,9 +637,10 @@ public class Parser {
*
* <pre>
* integerLiteral: [1-9][0-9]* | [0]
+ * floatLiteral: [1-9][0-9]* | [0]
* </pre>
*/
- private ConstantNode parseIntegerLiteral() {
+ private ConstantNode parseLiteral() {
return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole();
}
@@ -810,19 +795,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..7d4e2910
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/AddFNode.java
@@ -0,0 +1,44 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeFloat;
+
+import java.util.BitSet;
+
+public class AddFNode extends Node {
+ public AddFNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+ @Override public String label() { return "AddF"; }
+
+ @Override public String glabel() { return "+"; }
+
+ @Override
+ StringBuilder _print1(StringBuilder sb, BitSet visited) {
+ in(1)._print0(sb.append("("), visited);
+ in(2)._print0(sb.append("+"), visited);
+ return sb.append(")");
+ }
+
+ @Override
+ public Type compute() {
+ if (in(1)._type 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 2cc0b465..48350957 100644
--- a/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -106,6 +106,7 @@ public class AddNode extends Node {
static Node phiCon(Node op, boolean rotate) {
Node lhs = op.in(1);
Node rhs = op.in(2);
+ if( rhs._type==TypeInteger.TOP ) return null;
// LHS is either a Phi of constants, or another op with Phi of constants
PhiNode lphi = pcon(lhs,op);
if( rotate && lphi==null && lhs.nIns() > 2 ) {
@@ -171,4 +172,5 @@ 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); }
}
diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
index 9c15f01b..a31bd963 100644
--- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -1,7 +1,10 @@
package com.seaofnodes.simple.node;
+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 java.util.BitSet;
@@ -34,10 +37,16 @@ abstract public class BoolNode extends Node {
if (i0.isConstant() && i1.isConstant())
return TypeInteger.constant(doOp(i0.value(), i1.value()) ? 1 : 0);
}
- return in(1)._type.meet(in(2)._type);
+ if( in(1)._type instanceof TypeFloat i0 &&
+ in(2)._type instanceof TypeFloat i1 ) {
+ if (i0.isConstant() && i1.isConstant())
+ return TypeInteger.constant(doOp(i0.value(), i1.value()) ? 1 : 0);
+ }
+ return TypeInteger.BOT;
}
- abstract boolean doOp(long lhs, long rhs);
+ boolean doOp(long lhs, long rhs) { throw Utils.TODO(); }
+ boolean doOp(double lhs, double rhs) { throw Utils.TODO(); }
@Override
public Node idealize() {
@@ -49,11 +58,9 @@ abstract public class BoolNode extends Node {
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) )
@@ -69,7 +76,12 @@ abstract public class BoolNode extends Node {
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 "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } Node copy(Node lhs, Node rhs) { return new EQ(lhs,rhs); } Node copyF() { return new EQF(null,null); } }
+ public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs < rhs; } Node copy(Node lhs, Node rhs) { return new LT(lhs,rhs); } Node copyF() { return new LTF(null,null); }}
+ public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } Node copy(Node lhs, Node rhs) { return new LE(lhs,rhs); } Node copyF() { return new LEF(null,null); } }
+
+ public static class EQF extends EQ { public EQF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs == rhs; } Node copyF() { return null; } }
+ public static class LTF extends LT { public LTF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs < rhs; } Node copyF() { return null; } }
+ public static class LEF extends LE { public LEF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs <= rhs; } Node copyF() { return null; } }
+
}
diff --git a/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/src/main/java/com/seaofnodes/simple/node/CFGNode.java
index b605071b..07ba0fa4 100644
--- a/src/main/java/com/seaofnodes/simple/node/CFGNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/CFGNode.java
@@ -52,16 +52,17 @@ public abstract class CFGNode extends Node {
public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; }
// Return the immediate dominator of this Node and compute dom tree depth.
- public CFGNode idom() { return cfg(0); }
+ public CFGNode idom(Node dep) { return cfg(0); }
+ public final CFGNode idom() { return idom(null); }
// Return the LCA of two idoms
- public CFGNode idom(CFGNode rhs) {
+ public CFGNode _idom(CFGNode rhs, Node dep) {
if( rhs==null ) return this;
CFGNode lhs = this;
while( lhs != rhs ) {
var comp = lhs.idepth() - rhs.idepth();
- if( comp >= 0 ) lhs = lhs.idom();
- if( comp <= 0 ) rhs = rhs.idom();
+ if( comp >= 0 ) lhs = ((CFGNode)lhs.addDep(dep)).idom();
+ if( comp <= 0 ) rhs = ((CFGNode)rhs.addDep(dep)).idom();
}
return lhs;
}
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..36fd4524
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/DivFNode.java
@@ -0,0 +1,46 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeFloat;
+
+import java.util.BitSet;
+
+public class DivFNode extends Node {
+ public DivFNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+ @Override public String label() { return "DivF"; }
+
+ @Override public String glabel() { return "/"; }
+
+ @Override
+ StringBuilder _print1(StringBuilder sb, BitSet visited) {
+ in(1)._print0(sb.append("("), visited);
+ in(2)._print0(sb.append("/"), visited);
+ return sb.append(")");
+ }
+
+ @Override
+ public Type compute() {
+ if (in(1)._type 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 08ce70b8..e0c95019 100644
--- a/src/main/java/com/seaofnodes/simple/node/DivNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -40,4 +40,5 @@ public class DivNode extends Node {
}
@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 296237f4..244a0919 100644
--- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java
@@ -61,9 +61,13 @@ public class LoadNode extends MemOpNode {
if( profit(memphi,2) ||
// Else must not be a loop to count profit on LHS.
(!(memphi.region() instanceof LoopNode) && profit(memphi,1)) ) {
- Node ld1 = new LoadNode(_name,_alias,_declaredType,memphi.in(1),ptr()).peephole();
- Node ld2 = new LoadNode(_name,_alias,_declaredType,memphi.in(2),ptr()).peephole();
- return new PhiNode(_name,_type,memphi.region(),ld1,ld2);
+ if( ptr() instanceof NewNode || !(ptr() instanceof CastNode) ) {
+ if( !(ptr() instanceof NewNode) ) throw Utils.TODO(); // Validate
+
+ Node ld1 = new LoadNode(_name,_alias,_declaredType,memphi.in(1),ptr()).peephole();
+ Node ld2 = new LoadNode(_name,_alias,_declaredType,memphi.in(2),ptr()).peephole();
+ return new PhiNode(_name,_type,memphi.region(),ld1,ld2);
+ }
}
}
diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java
index c662dee6..22862cb9 100644
--- a/src/main/java/com/seaofnodes/simple/node/LoopNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java
@@ -30,7 +30,7 @@ public class LoopNode extends RegionNode {
// Bypass Region idom, same as the default idom() using use in(1) instead of in(0)
@Override public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; }
// Bypass Region idom, same as the default idom() using use in(1) instead of in(0)
- @Override public CFGNode idom() { return entry(); }
+ @Override public CFGNode idom(Node dep) { return entry(); }
@Override public int loopDepth() {
if( _loopDepth!=0 ) return _loopDepth; // Was already set
@@ -60,8 +60,11 @@ public class LoopNode extends RegionNode {
// directly on the If) we found our exit.
CFGNode x = back();
while( x != this ) {
- if( x instanceof CProjNode exit )
- return; // Found an exit, not an infinite loop
+ if( x instanceof CProjNode exit && exit.in(0) instanceof IfNode iff ) {
+ Node other = iff.cproj(1-exit._idx);
+ if( !(other.out(0) instanceof LoopNode loop) || loop.entry()==exit )
+ return; // Found an exit, not an infinite loop
+ }
x = x.idom();
}
// Found a no-exit loop. Insert an exit
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..9727f58b
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/MinusFNode.java
@@ -0,0 +1,36 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeFloat;
+
+import java.util.BitSet;
+
+public class MinusFNode extends Node {
+ public MinusFNode(Node in) { super(null, in); }
+
+ @Override public String label() { return "MinusF"; }
+
+ @Override public String glabel() { return "-"; }
+
+ @Override
+ StringBuilder _print1(StringBuilder sb, BitSet visited) {
+ in(1)._print0(sb.append("(-"), visited);
+ return sb.append(")");
+ }
+
+ @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 9b687613..ae8e9e1b 100644
--- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java
@@ -33,4 +33,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..2d44a9fb
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/MulFNode.java
@@ -0,0 +1,51 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeFloat;
+
+import java.util.BitSet;
+
+public class MulFNode extends Node {
+ public MulFNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+ @Override public String label() { return "MulF"; }
+
+ @Override public String glabel() { return "*"; }
+
+ @Override
+ StringBuilder _print1(StringBuilder sb, BitSet visited) {
+ in(1)._print0(sb.append("("), visited);
+ in(2)._print0(sb.append("*"), visited);
+ return sb.append(")");
+ }
+
+ @Override
+ public Type compute() {
+ if (in(1)._type 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 7e9f88a2..8c8a6e0a 100644
--- a/src/main/java/com/seaofnodes/simple/node/MulNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -54,4 +54,5 @@ 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); }
}
diff --git a/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/src/main/java/com/seaofnodes/simple/node/MultiNode.java
index 379e140d..ac9c0045 100644
--- a/src/main/java/com/seaofnodes/simple/node/MultiNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MultiNode.java
@@ -9,4 +9,12 @@ public interface MultiNode extends OutNode {
return prj;
return null;
}
+
+ // Find a projection by index
+ default CProjNode cproj( int idx ) {
+ for( Node out : outs() )
+ if( out instanceof CProjNode prj && prj._idx==idx )
+ return prj;
+ return null;
+ }
}
diff --git a/src/main/java/com/seaofnodes/simple/node/NeverNode.java b/src/main/java/com/seaofnodes/simple/node/NeverNode.java
index f50d3503..e77ed653 100644
--- a/src/main/java/com/seaofnodes/simple/node/NeverNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/NeverNode.java
@@ -3,6 +3,8 @@ package com.seaofnodes.simple.node;
import com.seaofnodes.simple.Parser;
import com.seaofnodes.simple.type.TypeInteger;
import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeTuple;
+
import java.util.BitSet;
// "Never true" for infinite loop exits
@@ -13,7 +15,7 @@ public class NeverNode extends IfNode {
@Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append("Never"); }
- @Override public Type compute() { return TypeInteger.BOT; }
+ @Override public Type compute() { return TypeTuple.IF_BOTH; }
@Override public Node idealize() { return null; }
}
diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java
index fc49ad6a..52282737 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -1,10 +1,10 @@
package com.seaofnodes.simple.node;
import com.seaofnodes.simple.IRPrinter;
-import com.seaofnodes.simple.Parser;
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;
@@ -236,6 +236,7 @@ public abstract class Node implements OutNode {
*/
public void kill( ) {
unlock();
+ moveDepsToWorklist();
assert isUnused(); // Has no uses, so it is dead
_type=null; // Flag as dead
while( nIns()>0 ) { // Set all inputs to null, recursively killing unused Nodes
@@ -546,6 +547,27 @@ public abstract class Node implements OutNode {
/** Pinned in the schedule */
public boolean isPinned() { return false; }
+ // 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
diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java
index 05e44eb0..3cf69520 100644
--- a/src/main/java/com/seaofnodes/simple/node/NotNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java
@@ -21,8 +21,8 @@ public class NotNode extends Node {
public Type compute() {
Type t0 = in(1)._type;
switch( t0 ) {
- case TypeInteger i0:
- return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0;
+ case TypeInteger i0: return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0;
+ case TypeFloat i0: return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0;
case TypeMemPtr p0:
// top->top, bot->bot, null->1, *void->0, not-null ptr->0, ptr/nil->bot
// If input in null then true
diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index a07dc140..ebed8dd1 100644
--- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -100,10 +100,10 @@ public class PhiNode extends Node {
if( in(2)._type == in(2)._type.makeInit() ) nullx = 2;
if( nullx != -1 ) {
Node val = in(3-nullx);
- if( region().idom() instanceof IfNode iff && iff.pred().addDep(this)==val ) {
+ if( region().idom(this) instanceof IfNode iff && iff.pred().addDep(this)==val ) {
// Must walk the idom on the null side to make sure we hit False.
CFGNode idom = (CFGNode)region().in(nullx);
- while( idom.in(0) != iff ) idom = idom.idom();
+ while( idom.nIns() > 0 && idom.in(0) != iff ) idom = idom.idom();
if( idom instanceof CProjNode proj && proj._idx==1 )
return val;
}
diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index dcc7ccef..d5105614 100644
--- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -99,12 +99,12 @@ public class RegionNode extends CFGNode {
return _idepth=d;
}
- @Override public CFGNode idom() {
+ @Override public CFGNode idom(Node dep) {
CFGNode lca = null;
// Walk the LHS & RHS idom trees in parallel until they match, or either fails.
// Because this does not cache, it can be linear in the size of the program.
for( int i=1; i<nIns(); i++ )
- lca = cfg(i).idom(lca);
+ lca = cfg(i)._idom(lca,dep);
return lca;
}
diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java
index 62fc8a6b..5f205ffd 100644
--- a/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -75,7 +75,7 @@ public class StartNode extends CFGNode implements MultiNode {
// No immediate dominator, and idepth==0
@Override public int idepth() { return 0; }
- @Override public CFGNode idom() { return null; }
+ @Override public CFGNode idom(Node dep) { return null; }
@Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { }
diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java
index 94b2ad6d..ab567bae 100644
--- a/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -59,7 +59,7 @@ public class StopNode extends CFGNode {
d = Math.max(d,((CFGNode)n).idepth()+1);
return _idepth=d;
}
- @Override public CFGNode idom() { return null; }
+ @Override public CFGNode idom(Node dep) { return null; }
@Override public int loopDepth() { return (_loopDepth=1); }
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..b591718d
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/SubFNode.java
@@ -0,0 +1,44 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeFloat;
+
+import java.util.BitSet;
+
+public class SubFNode extends Node {
+ public SubFNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+ @Override public String label() { return "SubF"; }
+
+ @Override public String glabel() { return "-"; }
+
+ @Override
+ StringBuilder _print1(StringBuilder sb, BitSet visited) {
+ in(1)._print0(sb.append("("), visited);
+ in(2)._print0(sb.append("-"), visited);
+ return sb.append(")");
+ }
+
+ @Override
+ public Type compute() {
+ if (in(1)._type 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 5ddcdb68..f0c77743 100644
--- a/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -31,6 +31,7 @@ public class SubNode extends Node {
if (i0.isConstant() && i1.isConstant())
return TypeInteger.constant(i0.value()-i1.value());
}
+
return in(1)._type.meet(in(2)._type);
}
@@ -48,4 +49,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..1d147cf6
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java
@@ -0,0 +1,30 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeFloat;
+import com.seaofnodes.simple.type.TypeInteger;
+
+import java.util.BitSet;
+
+public class ToFloatNode extends Node {
+ public ToFloatNode(Node lhs) { super(null, lhs); }
+
+ @Override public String label() { return "ToFloat"; }
+
+ @Override public String glabel() { return "(flt)"; }
+
+ @Override
+ StringBuilder _print1(StringBuilder sb, BitSet visited) {
+ return in(1)._print0(sb.append("(flt)"), visited);
+ }
+
+ @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/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java
index aa0ba1ea..f3152719 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;
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..36bc61f5
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java
@@ -0,0 +1,101 @@
+package com.seaofnodes.simple.type;
+
+import java.util.ArrayList;
+
+/**
+ * Float Type
+ */
+public class TypeFloat extends Type {
+
+ public final static TypeFloat TOP = make(false, 0);
+ public final static TypeFloat BOT = make(false, 1);
+ public final static TypeFloat ZERO= make(true , 0);
+
+ public final boolean _is_con;
+
+ /**
+ * The constant value or
+ * if not constant then 1=bottom, 0=top.
+ */
+ public final double _con;
+
+ private TypeFloat(boolean is_con, double con) {
+ super(TFLT);
+ _is_con = is_con;
+ _con = con;
+ }
+ public static TypeFloat make(boolean is_con, double con) {
+ return new TypeFloat(is_con,con).intern();
+ }
+
+ public static TypeFloat constant(double con) { return make(true, con); }
+
+ public static void gather(ArrayList<Type> ts) { ts.add(ZERO); ts.add(BOT); }
+
+ // 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==BOT ) return sb.append("FltBot");
+ return sb.append(_con);
+ }
+
+ @Override public String str() {
+ if( this==TOP ) return "~flt";
+ if( this==BOT ) return "flt";
+ return ""+_con;
+ }
+
+ /**
+ * 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==BOT ) return sb.append("FltBot");
+ return sb.append("Int");
+ }
+
+ @Override
+ public boolean isHighOrConst() { return _is_con || _con==0; }
+
+ @Override
+ public boolean isConstant() { return _is_con; }
+
+ 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
+ // 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;
+ }
+
+ @Override
+ public Type glb() { return BOT; }
+
+ @Override public TypeFloat makeInit() { return ZERO; }
+
+ @Override
+ int hash() { return (int)(Double.hashCode(_con) ^ (_is_con ? 0 : 0x4000)); }
+ @Override
+ public boolean eq( Type t ) {
+ TypeFloat i = (TypeFloat)t; // Contract
+ return _con==i._con && _is_con==i._is_con;
+ }
+}
diff --git a/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/src/test/java/com/seaofnodes/simple/Chapter08Test.java
index 98fd181b..6aa74125 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter08Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter08Test.java
@@ -2,7 +2,6 @@ package com.seaofnodes.simple;
import com.seaofnodes.simple.evaluator.Evaluator;
import com.seaofnodes.simple.node.*;
-import com.seaofnodes.simple.type.TypeInteger;
import org.junit.Assert;
import org.junit.Test;
diff --git a/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/src/test/java/com/seaofnodes/simple/Chapter09Test.java
index 2abce3cb..64bbf245 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter09Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter09Test.java
@@ -5,7 +5,6 @@ import com.seaofnodes.simple.node.*;
import com.seaofnodes.simple.type.Type;
import com.seaofnodes.simple.type.TypeInteger;
import org.junit.Assert;
-import org.junit.BeforeClass;
import org.junit.Test;
import org.junit.Ignore;
diff --git a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/src/test/java/com/seaofnodes/simple/Chapter10Test.java
index 7371ff18..4a9521b9 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter10Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter10Test.java
@@ -1,7 +1,12 @@
package com.seaofnodes.simple;
+import com.seaofnodes.simple.node.Node;
import com.seaofnodes.simple.node.StopNode;
+import com.seaofnodes.simple.type.*;
import org.junit.Test;
+
+import java.util.Arrays;
+
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.fail;
@@ -259,7 +264,6 @@ while(arg) {
v0.v0 = arg;
arg = arg-1;
if (arg==5) ret=v0;
-
}
return ret;
""");
diff --git a/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/src/test/java/com/seaofnodes/simple/Chapter11Test.java
index fdf56b56..a8b09226 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter11Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter11Test.java
@@ -292,7 +292,7 @@ else {
}
""");
StopNode stop = parser.parse().iterate();
- assertEquals("Stop[ return 9; return 0; return 0; ]", stop.toString());
+ assertEquals("Stop[ return 9; return 0; return 0; return 0; return 0; ]", stop.toString());
}
@@ -434,7 +434,7 @@ while(1)
arg = arg+ptr.v;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return 0;", stop.toString());
+ assertEquals("Stop[ return 0; return 0; ]", stop.toString());
}
@Test
@@ -496,7 +496,7 @@ return v;
@Test
public void testExample2() {
Parser parser = new Parser(
- """
+ """
struct S { int f; }
S v = new S;
int i = arg;
@@ -507,7 +507,7 @@ while (arg > 0) {
arg = arg - 1;
}
return v;
-""");
+ """);
StopNode stop = parser.parse().iterate();
//assertEquals("return new S;", stop.toString());
}
@@ -528,38 +528,4 @@ return s.f;
assertEquals(1L, Evaluator.evaluate(stop, 1));
assertEquals(0L, Evaluator.evaluate(stop, 2));
}
-
- @Test
- public void testScheduleUse() {
- Parser parser = new Parser(
-"""
-int v0=0;
-while(0>=0) {
- int v1=0;
- v1=v0;
- if(v1*0)
- v0=-v1;
-}
-return 0;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("return 0;", stop.toString());
- }
-
- @Test
- public void testLoopCarriedDep() {
- Parser parser = new Parser(
-"""
-int v0=0;
-{
- int v1=0;
- while(v1) {
- v1=1+(v0!=0);
- v0=v1/0;
- }
-}
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("return 0;", stop.toString());
- }
}
diff --git a/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/src/test/java/com/seaofnodes/simple/Chapter12Test.java
new file mode 100644
index 00000000..af8fdfe9
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/Chapter12Test.java
@@ -0,0 +1,64 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.evaluator.Evaluator;
+import com.seaofnodes.simple.node.StopNode;
+import org.junit.Test;
+
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.fail;
+
+public class Chapter12Test {
+ @Test
+ public void testJig() {
+ Parser parser = new Parser(
+"""
+return 3.14;
+""");
+ StopNode stop = parser.parse(false).iterate(false);
+ 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(false).iterate(false);
+ 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(false).iterate(false);
+ assertEquals("return Phi(Loop9,(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(false).iterate(false);
+ assertEquals("return ((flt)arg==(ToFloat+1.0));", stop.toString());
+ assertEquals(0L, Evaluator.evaluate(stop, 1));
+ }
+
+}
diff --git a/src/test/java/com/seaofnodes/simple/SchedulerTest.java b/src/test/java/com/seaofnodes/simple/SchedulerTest.java
index 32c9c0c5..5def2782 100644
--- a/src/test/java/com/seaofnodes/simple/SchedulerTest.java
+++ b/src/test/java/com/seaofnodes/simple/SchedulerTest.java
@@ -46,7 +46,7 @@ S v0=new S;
if(arg) v0.f=1;
return v0;
""");
- StopNode stop = parser.parse(false).iterate();
+ StopNode stop = parser.parse().iterate();
var eval = new Evaluator(stop);
assertObj(eval.evaluate(0, 10), "S", 0L);
assertObj(eval.evaluate(1, 10), "S", 1L);
@@ -65,7 +65,7 @@ i=v.f;
if (arg) v.f=1;
return i;
""");
- StopNode stop = parser.parse(false).iterate();
+ StopNode stop = parser.parse().iterate();
var eval = new Evaluator(stop);
assertEquals(2L, eval.evaluate(0, 10));
assertEquals(2L, eval.evaluate(1, 10));
diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
index 4a405a3b..3512d2e9 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,24 @@ 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 CastNode cast -> val(cast.in(1));
+ case ToFloatNode cast -> (double)vall(cast.in(1));
case LoadNode load -> load(load);
case StoreNode store -> store(store);
case NewNode alloc -> alloc(alloc);
diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
index 155063ab..b8437b50 100644
--- a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
+++ b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
@@ -22,6 +22,7 @@ public class ScriptGenerator {
private static final int MAX_NAME_LENGTH = 10;
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
@@ -68,7 +69,7 @@ public class ScriptGenerator {
}
private static class TypeStruct extends Type {
- record Field (String name, Type type) {}
+ record Field (String name, Type type, TypeStruct struct) {}
final Field[] fields;
final TypeNullable nullable = new TypeNullable(this);
TypeStruct(String name, Field[] fields) {
@@ -89,7 +90,21 @@ 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() {
+ super("int");
+ }
+
+ @Override
+ boolean isa(Type other) {
+ return super.isa(other) || other == TYPE_FLT;
+ }
+ }
+
+ private static final Type TYPE_INT = new TypeInt();
private static class Variable {
@@ -343,7 +358,9 @@ public class ScriptGenerator {
* @return A random type
*/
private Type getType() {
- if (structs.isEmpty() || random.nextBoolean()) return TYPE_INT;
+ int t = random.nextInt(10);
+ if( t<5 || structs.isEmpty() ) return TYPE_INT;
+ if( t<7 ) return TYPE_FLT;
var idx = random.nextInt(structs.size());
TypeStruct struct = structs.get(idx);
if (random.nextBoolean()) return struct.nullable;
@@ -411,17 +428,18 @@ public class ScriptGenerator {
public int genStruct() {
var name = getStructName();
var fields = new TypeStruct.Field[generateInvalid() ? 0 : random.nextInt(10)];
+ var struct = new TypeStruct(name, fields);
sb.append("struct ").append(name).append(" {\n");
indentation += INDENTATION;
for (int i=0; i<fields.length; i++) {
var fieldName = getRandomName();
- var type = generateInvalid() ? getType() : TYPE_INT;
+ var type = getType();
printIndentation().append(type.name).append(" ").append(fieldName).append(";\n");
- fields[i] = new TypeStruct.Field(fieldName.toString(), type);
+ fields[i] = new TypeStruct.Field(fieldName.toString(), type, struct);
}
indentation -= INDENTATION;
printIndentation().append("}");
- structs.add(new TypeStruct(name, fields));
+ structs.add(struct);
return 0;
}
@@ -515,7 +533,7 @@ public class ScriptGenerator {
*/
public int genIf() {
sb.append("if(");
- genExpression(TYPE_INT);
+ genExpression(TYPE_INT, true);
sb.append(") ");
var stop = genStatementBlock();
if ((stop & FLAG_IF_WITHOUT_ELSE) == 0 && random.nextInt(10) > 3) {
@@ -561,7 +579,7 @@ public class ScriptGenerator {
*/
public int genWhile() {
sb.append("while(");
- genExpression(TYPE_INT);
+ genExpression(TYPE_INT, true);
sb.append(") ");
loopDepth++;
genStatementBlock();
@@ -587,17 +605,17 @@ public class ScriptGenerator {
indentation += INDENTATION;
String name = getVarName();
printIndentation().append("int ").append(name).append("=");
- genExpression(TYPE_INT);
+ genExpression(TYPE_INT, true);
sb.append(";\n");
addVariable(name, TYPE_INT);
printIndentation().append("while(").append(name).append("<");
- genExpression(TYPE_INT);
+ genExpression(TYPE_INT, true);
sb.append(") {\n");
indentation += INDENTATION;
depth--;
loopDepth++;
printIndentation().append(name).append("=").append(name).append("+");
- genExpression(TYPE_INT);
+ genExpression(TYPE_INT, true);
sb.append(";\n");
genStatements();
loopDepth--;
@@ -621,7 +639,7 @@ public class ScriptGenerator {
sb.append(generateInvalid() ? getRandomName() : type.name).append(" ").append(name);
if (!(type instanceof TypeNullable) || random.nextBoolean()) {
sb.append("=");
- genExpression(type);
+ genExpression(type, true);
}
sb.append(";");
addVariable(name, type);
@@ -656,7 +674,7 @@ public class ScriptGenerator {
declared = field.type;
}
sb.append("=");
- genExpression(declared);
+ genExpression(declared, true);
sb.append(";");
return 0;
}
@@ -668,7 +686,7 @@ public class ScriptGenerator {
public int genReturn() {
var type = getType();
sb.append("return ");
- genExpression(type);
+ genExpression(type, true);
sb.append(";");
return FLAG_STOP;
}
@@ -677,70 +695,91 @@ public class ScriptGenerator {
* Generate a binary expression.
* This method does not care about operator precedence.
*/
- public void genExpression(Type type) {
- if (generateInvalid()) type = getType();
- if (type != TYPE_INT) {
- genUnary(type);
+ public void genExpression(Type type, boolean change) {
+ if (change && generateInvalid()) type = getType();
+ if (type != TYPE_INT && type != TYPE_FLT) {
+ genUnary(type, false);
return;
}
var num = randLog(MAX_BINARY_EXPRESSIONS_PER_EXPRESSION);
while(num-->0) {
- genUnary(TYPE_INT);
+ genUnary(type, false);
sb.append(BINARY_OP[random.nextInt(BINARY_OP.length)]);
}
- genUnary(TYPE_INT);
+ genUnary(type, false);
}
/**
* Generate a unary expression.
*/
- public void genUnary(Type type) {
- if (generateInvalid()) type = getType();
- if (type != TYPE_INT) {
- genSuffix(type);
+ public void genUnary(Type type, boolean change) {
+ if (change && generateInvalid()) type = getType();
+ if (type != TYPE_INT && type != TYPE_FLT) {
+ genSuffix(type, false);
return;
}
var num = randLog(MAX_UNARY_EXPRESSIONS_PER_EXPRESSION);
while(num-->0) {
sb.append(UNARY_OP[random.nextInt(UNARY_OP.length)]);
}
- genSuffix(TYPE_INT);
+ genSuffix(type, false);
+ }
+
+ public TypeStruct.Field getField(Type type) {
+ int n=0;
+ for (var s: structs) {
+ for (var f: s.fields) {
+ if (f.type.isa(type)) n++;
+ }
+ }
+ if (n==0) return null;
+ n = random.nextInt(n);
+ for (var s: structs) {
+ for (var f: s.fields) {
+ if (f.type.isa(type)) if (n--==0) return f;
+ }
+ }
+ throw new AssertionError();
}
/**
* Generate
*/
- public void genSuffix(Type type) {
- if (generateInvalid()) type = getType();
- if (type == TYPE_INT && random.nextBoolean()) {
- var t = getType();
+ public void genSuffix(Type type, boolean change) {
+ genSuffixRecursive(type, change, MAX_SUFFIX_RECURSIVE_DEPTH);
+ }
+
+ public void genSuffixRecursive(Type type, boolean change, int depth) {
+ if (change && generateInvalid()) type = getType();
+ if (depth > 0 && random.nextBoolean()) {
if (generateInvalid()) {
var field = getRandomName();
- genPrimary(t);
+ var t = getType();
+ genSuffixRecursive(t, true, depth-1);
sb.append(".").append(field);
return;
- } else if (t instanceof TypeStruct s && s.fields.length > 0) {
- var field = s.fields[random.nextInt(s.fields.length)];
- if (field.type == TYPE_INT) {
- genPrimary(t);
+ } else {
+ var field = getField(type);
+ if (field != null) {
+ genSuffixRecursive(field.struct, true, depth-1);
sb.append(".").append(field.name);
return;
}
}
}
- genPrimary(type);
+ genPrimary(type, false);
}
/**
* Generate a primary expression.
*/
- public void genPrimary(Type type) {
- if (generateInvalid()) type = getType();
+ public void genPrimary(Type type, boolean change) {
+ if (change && generateInvalid()) type = getType();
var rand = random.nextInt(10);
if (rand == 0 && exprDepth != 0) {
sb.append("(");
exprDepth--;
- genExpression(type);
+ genExpression(type, false);
exprDepth++;
sb.append(")");
} else if (rand < 6) {
@@ -755,13 +794,15 @@ public class ScriptGenerator {
*/
public void genConst(Type type) {
if (generateInvalid()) type = getType();
- if (type == TYPE_INT) {
+ if (type == TYPE_INT || (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 (random.nextBoolean()) {
sb.append("null");