diff options
Diffstat (limited to 'chapter12')
68 files changed, 805 insertions, 2971 deletions
diff --git a/chapter12/Makefile b/chapter12/Makefile index 3f1e53ff..5ed21084 100644 --- a/chapter12/Makefile +++ b/chapter12/Makefile @@ -1,106 +1,7 @@ -SHELL := /bin/bash -# Shared packaging target; included after chapter source variables below. -.DELETE_ON_ERROR: +# Standalone compiler snapshot; shared rules also work in linearized checkouts. +include $(firstword $(wildcard ../build-support/early-chapter.mk build-support/early-chapter.mk)) +test_cp += com.seaofnodes.simple.FuzzerWrap -# for printing variable values -# usage: make print-VARIABLE -# > VARIABLE = value_of_variable -print-% : ; @echo $* = $($*) - -# literal space -space := $() $() - -# Decide OS-specific questions -# jar-file seperator -ifeq ($(OS),Windows_NT) - SEP = ; -else - SEP = : -endif -# Find a reasonable ctags. -CTAGS = $(shell which ctags) -# Hack for MacOS: /usr/bin/ctags is unfriendly, so look for ctags from brew -ifeq ($(UNAME),Darwin) - CTAGS = $(shell brew list ctags 2> /dev/null | grep bin/ctags) -endif - -# Fun Args to javac. Mostly limit to java8 source definitions, and fairly -# aggressive lint warnings. -JAVAC_ARGS = -g - -# Source code -SIMPLE := com/seaofnodes/simple -SRC := src/main/java -TST := src/test/java -CLZDIR:= build/classes -main_javas := $(wildcard $(SRC)/$(SIMPLE)/*java $(SRC)/$(SIMPLE)/*/*java) -test_javas := $(wildcard $(TST)/$(SIMPLE)/*java $(TST)/$(SIMPLE)/*/*java) -main_classes := $(patsubst $(SRC)/%java,$(CLZDIR)/main/%class,$(main_javas)) -include $(firstword $(wildcard ../graph/graph.mk graph/graph.mk)) -include $(firstword $(wildcard ../print/print.mk print/print.mk)) -test_classes := $(patsubst $(TST)/%java,$(CLZDIR)/test/%class,$(test_javas)) -test_cp := $(patsubst $(TST)/$(SIMPLE)/%.java,com.seaofnodes.simple.%,$(wildcard $(TST)/$(SIMPLE)/*Test.java)) -classes = $(main_classes) $(test_classes) -# All the libraries -libs = $(wildcard lib/*jar) -jars = $(subst $(space),$(SEP),$(libs)) - - -default_targets := $(main_classes) $(test_classes) -# Optionally add ctags to the default target if a reasonable one was found. -ifneq ($(CTAGS),) -default_targets += tags -endif - -default: $(default_targets) - -# Compile just the out-of-date files -$(main_classes): build/classes/main/%class: $(SRC)/%java $(graph_javas) $(print_javas) - @echo "compiling " $@ " because " $? - @[ -d $(CLZDIR)/main ] || mkdir -p $(CLZDIR)/main - @javac $(JAVAC_ARGS) -cp "$(CLZDIR)/main$(SEP)$(jars)" -sourcepath $(SRC) -d $(CLZDIR)/main $(main_javas) - -$(test_classes): $(CLZDIR)/test/%class: $(TST)/%java $(main_classes) - @echo "compiling " $@ " because " $? - @[ -d $(CLZDIR)/test ] || mkdir -p $(CLZDIR)/test - @javac $(JAVAC_ARGS) -cp "$(CLZDIR)/test$(SEP)$(CLZDIR)/main$(SEP)$(jars)" -sourcepath $(TST) -d $(CLZDIR)/test $(test_javas) - -# Base launch line for JVM tests -JVM=nice java -ea -cp "build/classes/main${SEP}${jars}${SEP}$(CLZDIR)/test" - -tests: $(default_targets) - @echo "testing " $(test_cp) - @$(JVM) org.junit.runner.JUnitCore $(test_cp) com.seaofnodes.simple.FuzzerWrap - -fuzzer: $(default_targets) - @echo "fuzzing " $(test_cp) - @$(JVM) org.junit.runner.JUnitCore com.seaofnodes.simple.FuzzerWrap - - -.PHONY: clean -clean: - rm -rf build - rm -f TAGS - (find . -name "*~" -exec rm {} \; 2>/dev/null; exit 0) - -# Download libs from maven -lib: lib/junit-4.12.jar lib/hamcrest-core-1.3.jar - -# Jars -lib/junit-4.12.jar: - @[ -d lib ] || mkdir -p lib - @(cd lib; wget https://repo1.maven.org/maven2/junit/junit/4.12/junit-4.12.jar) - -lib/hamcrest-core-1.3.jar: - @[ -d lib ] || mkdir -p lib - @(cd lib; wget https://repo1.maven.org/maven2/org/hamcrest/hamcrest-core/1.3/hamcrest-core-1.3.jar) - -# Build emacs tags (part of a tasty emacs ide experience) -tags: $(main_javas) $(test_javas) - @rm -f TAGS - @$(CTAGS) -e --recurse=yes --extra=+q --fields=+fksaiS $(SRC) $(TST) - -include $(firstword $(wildcard ../build-support/chapter-release.mk build-support/chapter-release.mk)) - -.PHONY: build -build: $(main_classes) +.PHONY: fuzzer +fuzzer: $(test_classes) + java -ea -cp "$(CLZDIR)/main$(SEP)$(CLZDIR)/test$(SEP)$(jars)" org.junit.runner.JUnitCore com.seaofnodes.simple.FuzzerWrap diff --git a/chapter12/README.md b/chapter12/README.md index 36922373..3110d735 100644 --- a/chapter12/README.md +++ b/chapter12/README.md @@ -1,61 +1,148 @@ -# Chapter 12: Floats +# Chapter 12: References [Previous: Chapter 11](../chapter11/README.md) | [Next: Chapter 13](../chapter13/README.md) -# Table of Contents +Chapters 10 and 11 gave structs integer fields and represented their memory +effects in SSA. This chapter lets fields contain references to other structs, +including structs whose definitions have not yet appeared. Linked lists and +mutually referring objects become possible without changing the memory graph. -1. [Float](#floats) +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter12) +in the linear Git history and [compare it with Chapter 11](https://github.com/SeaOfNodes/Simple/compare/linear-chapter11...linear-chapter12). -In this chapter, we add a floating point type and values. +## Typed fields and forward references -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. +```java +struct Person { + int age; + FamilyTree? tree; +} +struct FamilyTree { + Person? father; + Person? mother; +} +``` + +The parser's `TYPES` table maps names to types. It initially contains `int` +(and any other primitive types, more are showing up in later chapters). When +`type()` recognizes a declaration using an unknown name, it installs a +name-only `TypeStruct`, with `_fields == null` - this a struct where we only +know the struct name, and no other information. A pointer to that struct is +enough to describe a reference field,`?` allows the pointer to be null. -## Floats +`parseStruct()` collects all fields before installing the complete struct in +`TYPES`. It replaces the table entry; it does not mutate the old type or +publish successive prefixes of the field list. Field aliases are allocated +with the completed declaration, as before. -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. +See [the parser](src/main/java/com/seaofnodes/simple/Parser.java), particularly +`type()`, `parseField()`, and `parseStruct()`, and the +[grammar](docs/12-grammar.md). + +## Recursive structs: `L0` and `L1` ```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 +struct LLI { LLI? next; int i; } ``` -There is no corresponding way right now to round a `flt` back to an `int`: -```java -int x = 3.14; // error +Two descriptions are useful for remembering what the compiler actually builds: + +```text +L0 = TypeStruct("LLI", fields = null) +L1 = TypeStruct("LLI", fields = { next: pointer-to-L0?, i: int }) +TYPES["LLI"] = L1 ``` -Here is Newton's method for computing a square root: +`L0` is created when parsing the `LLI? next` field. After the closing brace, +`L1` replaces it in the name table. The `next` field inside `L1` still points +to `L0`; it is not patched to point back to `L1`. + +The design is **immutable shallow references, resolved by name when needed**. +The runtime objects may form a cycle; their compiler type descriptions remain +finite and acyclic. This is an intentional decision to **stop recursive type +expansion**. Recursively substituting the completed definition into every +reference would either expand forever or require cyclic type interning, +equality, hashing, and lattice operations (which indeed show up in a lattice +chapter). + +[`TypeStruct`](src/main/java/com/seaofnodes/simple/type/TypeStruct.java) +instead stops at the name-only description. Its `dual()` and `glb()` leave that +description alone. Meeting a complete description with a name-only description +of the same struct yields the name-only description. That loses field detail +without losing the struct's identity. There is no pass trying to expand `L0` +into an ever deeper sequence of `L1`, `L2`, and so on. + +## Resolving a shallow reference + +When parsing `head.next`, `parsePostfix()` takes the pointer's struct name and +looks up the current declaration in `TYPES`. It gets the field layout and alias +from that declaration, even if the pointer's own type still contains `L0`. +Doing the lookup again for the next field access is sufficient for a chain +such as `head.next.next.i`. + +For a local declaration or assignment, `parseExpressionStatement()` also +resolves a name-only pointer before checking assignment compatibility. This +"deepening" changes the temporary type used for the check; it does not rewrite +the expression node's type or replace all old references in the graph. + ```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; +struct LLI { LLI? next; int i; } +LLI? head = null; +while (arg) { + LLI x = new LLI; + x.next = head; + x.i = arg; + head = x; + arg = arg - 1; } -return guess; +if (!head) return 0; +LLI? next = head.next; +if (next == null) return 1; +return next.i; ``` -When run with argument 2.0, produces 1.414213562373095. -Floating point operations have their own Nodes: +The null checks refine the pointer on the surviving control path. In +particular, the false path of an `if` must record its refinement even when +there is no explicit `else`. Resolving a name supplies the field definition; +it does not prove that the pointer is non-null. -| Node | Op | -|------------------------|----------------------| -| AddF, SubF, MulF, DivF | Basic binary FP ops | -| MinusF | Unary negate | -| EQF, LTF, LEF | FP compare operators | +## Initialization and incomplete definitions -Within the Type lattice, we add the following domain: +`newStruct()` initializes each field using its type's `makeInit()`: zero for +integers and null for references. Loads and Stores use the same aliases and +memory optimizations as Chapter 11. A Load from an initializing Store can +therefore fold to null. -*  - Float values. The same shape as the Integer values, but floats - with a top (`TOP`, ⊤), bottom (`BOT`, ⊥), and constants. +An unused forward reference need not ever be defined: + +```java +struct Holder { Missing? ref; } +Holder h = new Holder; +return h.ref; // null; no definition of Missing is needed +``` + +There is no way here to construct a non-null `Missing` without its complete +definition: `new Missing` is rejected. Accessing one of its fields also needs +a definition, as well as a non-null pointer. Simply mentioning a nullable +reference type does not impose a requirement to define it before the end of +the program. + +There is one temporary initialization allowance in this chapter: + +```java +struct N { N next; int i; } +N n = new N; +return n.next; // null, despite the non-null field declaration +``` -The other domains retain Chapter 10b's named structs, nullable pointers, and -precise memory aliases. +The initializing Store may write null even into a non-null reference field. +An ordinary `n.next = null` is rejected. Chapter 16 adds constructors and +checks initialization; this chapter keeps the distinction explicit in +[`StoreNode`](src/main/java/com/seaofnodes/simple/node/StoreNode.java). - +The [reference tests](src/test/java/com/seaofnodes/simple/Chapter12Test.java) +exercise linked lists, mutual references, null checks, and incomplete types. +Run them with `make tests`; `make view` displays the same unscheduled graph. +Chapter 13 now has the memory and reference semantics it needs to introduce +global code motion, including load/store anti-dependencies. diff --git a/chapter12/chapter12.iml b/chapter12/chapter12.iml new file mode 100644 index 00000000..28f6886a --- /dev/null +++ b/chapter12/chapter12.iml @@ -0,0 +1,28 @@ +<?xml version="1.0" encoding="UTF-8"?> +<module type="JAVA_MODULE" version="4"> + <component name="NewModuleRootManager" inherit-compiler-output="false"> + <output url="file://$MODULE_DIR$/../build/idea/production/chapter12" /> + <output-test url="file://$MODULE_DIR$/../build/idea/test/chapter12" /> + <exclude-output /> + <content url="file://$MODULE_DIR$"> + <sourceFolder url="file://$MODULE_DIR$/src/main/java" isTestSource="false" /> + <sourceFolder url="file://$MODULE_DIR$/src/test/java" isTestSource="true" /> + <excludeFolder url="file://$MODULE_DIR$/build" /> + <excludeFolder url="file://$MODULE_DIR$/target" /> + </content> + <orderEntry type="inheritedJdk" /> + <orderEntry type="sourceFolder" forTests="false" /> + <orderEntry type="module" module-name="graph" /> + <orderEntry type="module" module-name="print" /> + <orderEntry type="module-library" scope="TEST"> + <library name="JUnit4"> + <CLASSES> + <root url="jar://$MODULE_DIR$/lib/junit-4.12.jar!/" /> + <root url="jar://$MODULE_DIR$/lib/hamcrest-core-1.3.jar!/" /> + </CLASSES> + <JAVADOC /> + <SOURCES /> + </library> + </orderEntry> + </component> +</module> diff --git a/chapter12/docs/12-grammar.md b/chapter12/docs/12-grammar.md index 4c071a98..24199ede 100644 --- a/chapter12/docs/12-grammar.md +++ b/chapter12/docs/12-grammar.md @@ -11,21 +11,21 @@ statement : returnStatement | structDeclaration | declStatement - | blockStatment + | blockStatement | expressionStatement | ifStatement | whileStatement | breakStatement - | continueStatment + | continueStatement ; PRIMTYPE : 'int' - | 'flt' ; field : PRIMTYPE IDENTIFIER ';' + | structName ('?')? IDENTIFIER ';' ; fields @@ -102,7 +102,7 @@ newExpression ; fieldExpression - : primaryExpresson '.' IDENTIFIER + : primaryExpression '.' IDENTIFIER ; primaryExpression @@ -122,7 +122,7 @@ INTEGER_LITERAL ; IDENTIFIER - : NON_DIGIT (NON_DIGIT | DIGIT)* + : NON_DIGIT (NON_DIGIT | DEC_DIGIT)* ; NON_DIGIT: [a-zA-Z_]; diff --git a/chapter12/docs/lattice.gv b/chapter12/docs/lattice.gv deleted file mode 100644 index e8631cd5..00000000 --- a/chapter12/docs/lattice.gv +++ /dev/null @@ -1,154 +0,0 @@ -digraph Lattice { - rankdir=TB; - newrank=true; - // Preserve the same-rank ordering edges through cluster layout. - remincross=false; - nodesep=0.22; - ranksep=0.65; - node [shape=ellipse, style=filled, fontname="DejaVu Sans", fontsize=13]; - edge [color="#555555", arrowsize=0.6]; - - // These arrows are lattice-order edges, not use/definition edges. - TOP [label="⊤", fillcolor=black, fontcolor=white]; - BOT [label="⊥", fillcolor=black, fontcolor=white]; - - subgraph cluster_control { - label="Control"; fontname="Arial"; color="#cccccc"; - node [fillcolor="#ffff00"]; - XCTRL [label="⊤:ctrl"]; - CTRL [label="⊥:ctrl"]; - XCTRL -> CTRL; - } - - subgraph cluster_integer { - label="Integer"; fontname="Arial"; color="#cccccc"; - node [fillcolor="#add8e6"]; - INT_TOP [label="⊤:int"]; - INT_BOT [label="⊥:int"]; - INT_NEG [label="… −2, −1"]; - INT_ZERO [label="0"]; - INT_POS [label="1, 2, …"]; - {rank=same; INT_NEG; INT_ZERO; INT_POS;} - INT_NEG -> INT_ZERO -> INT_POS [style=invis]; - INT_TOP -> {INT_NEG INT_ZERO INT_POS}; - {INT_NEG INT_ZERO INT_POS} -> INT_BOT; - } - - subgraph cluster_float { - label="Float"; fontname="Arial"; color="#cccccc"; - FLT_TOP [label=<<B>⊤</B >:flt>, fillcolor=aqua, shape=oval]; - FLT_BOT [label=<<B>⊥</B>:flt>, fillcolor=aqua, shape=oval]; - - FLT_MINDOTS [label="… negative constants", fillcolor=aqua, shape=oval]; - FLT_ZERO [label="0.0" , fillcolor=aqua]; - FLT_MAXDOTS [label="positive constants …", fillcolor=aqua, shape=oval]; - - 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_MINDOTS -> FLT_ZERO -> FLT_MAXDOTS [style=invis]; - - {rank=same; FLT_MINDOTS; FLT_ZERO; FLT_MAXDOTS;} - } - - subgraph cluster_pointer { - label="Pointer = nullability × struct type"; - fontname="Arial"; color="#cccccc"; - node [fillcolor="#008000", fontcolor=white]; - PTR_TOP [label="⊤:ptr\n[*⊤:struct]"]; - PTR_BOT [label="⊥:ptr\n[*⊥:struct?]"]; - PTR_NULL [label="null"]; - PTR_ANY [label="*⊥:struct\n[ptr any struct]"]; - PTR_PERSON [label="*Person"]; - PTR_S1 [label="*s1"]; - PTR_MORE [label="*s2, …"]; - PTR_PERSON_NIL [label="*Person?"]; - PTR_S1_NIL [label="*s1?"]; - PTR_MORE_NIL [label="*s2?, …"]; - {rank=same; PTR_PERSON; PTR_S1; PTR_MORE; PTR_NULL;} - {rank=same; PTR_ANY; PTR_PERSON_NIL; PTR_S1_NIL; PTR_MORE_NIL;} - PTR_PERSON -> PTR_S1 -> PTR_MORE -> PTR_NULL [style=invis]; - PTR_ANY -> PTR_PERSON_NIL -> PTR_S1_NIL -> PTR_MORE_NIL [style=invis]; - PTR_TOP -> {PTR_PERSON PTR_S1 PTR_MORE PTR_NULL}; - {PTR_PERSON PTR_S1 PTR_MORE} -> PTR_ANY; - PTR_PERSON -> PTR_PERSON_NIL; - PTR_S1 -> PTR_S1_NIL; - PTR_MORE -> PTR_MORE_NIL; - PTR_NULL -> {PTR_PERSON_NIL PTR_S1_NIL PTR_MORE_NIL}; - {PTR_ANY PTR_PERSON_NIL PTR_S1_NIL PTR_MORE_NIL} -> PTR_BOT; - } - - subgraph cluster_struct { - label="Struct\nnamed collection of named scalar types"; - fontname="Arial"; color="#cccccc"; - node [fillcolor="#90ee90"]; - STRUCT_TOP [label="⊤:struct\n[struct top]"]; - STRUCT_BOT [label="⊥:struct\n[struct bottom]"]; - STRUCT_PERSON [label="Person\nage: int", shape=box]; - STRUCT_S1 [label="s1\nx: int", shape=box]; - STRUCT_S2 [label="s2\nx: int, y: flt", shape=box]; - STRUCT_MORE [label="…", shape=box]; - {rank=same; STRUCT_PERSON; STRUCT_S1; STRUCT_S2; STRUCT_MORE;} - STRUCT_PERSON -> STRUCT_S1 -> STRUCT_S2 -> STRUCT_MORE [style=invis]; - STRUCT_TOP -> {STRUCT_PERSON STRUCT_S1 STRUCT_S2 STRUCT_MORE}; - {STRUCT_PERSON STRUCT_S1 STRUCT_S2 STRUCT_MORE} -> STRUCT_BOT; - } - - subgraph cluster_memory { - label="Memory\nprecise alias slices"; fontname="Arial"; color="#cccccc"; - node [fillcolor="#00008b", fontcolor=white]; - MEM_TOP [label="⊤:mem"]; - MEM_BOT [label="⊥:mem"]; - MEM_ALIAS2 [label="MEM#2"]; - MEM_ALIAS3 [label="MEM#3"]; - MEM_MORE [label="…"]; - {rank=same; MEM_ALIAS2; MEM_ALIAS3; MEM_MORE;} - MEM_ALIAS2 -> MEM_ALIAS3 -> MEM_MORE [style=invis]; - MEM_TOP -> {MEM_ALIAS2 MEM_ALIAS3 MEM_MORE}; - {MEM_ALIAS2 MEM_ALIAS3 MEM_MORE} -> MEM_BOT; - } - - subgraph cluster_tuple { - label="Tuple\ncollection of types"; - fontname="Arial"; color="#cccccc"; - node [fillcolor="#ffc0cb"]; - TUPLE_TOP [label="⊤:tuple"]; - TUPLE_BOT [label="⊥:tuple"]; - // Each black element stands for a recursively nested type lattice. - TUPLE1 [shape=plain, label=< - <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> - <TR><TD BGCOLOR="#ffc0cb">tuple</TD></TR> - <TR><TD BGCOLOR="black"><FONT COLOR="white">type</FONT></TD></TR> - </TABLE> - >]; - TUPLE2 [shape=plain, label=< - <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> - <TR><TD BGCOLOR="#ffc0cb">tuple</TD></TR> - <TR><TD BGCOLOR="black"><FONT COLOR="white">type</FONT></TD></TR> - <TR><TD BGCOLOR="black"><FONT COLOR="white">type</FONT></TD></TR> - </TABLE> - >]; - TUPLEN [shape=plain, label=< - <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> - <TR><TD BGCOLOR="#ffc0cb">tuple</TD></TR> - <TR><TD BGCOLOR="black"><FONT COLOR="white">type</FONT></TD></TR> - <TR><TD BGCOLOR="black"><FONT COLOR="white">…</FONT></TD></TR> - <TR><TD BGCOLOR="black"><FONT COLOR="white">type</FONT></TD></TR> - </TABLE> - >]; - {rank=same; TUPLE1; TUPLE2; TUPLEN;} - TUPLE1 -> TUPLE2 -> TUPLEN [style=invis]; - TUPLE_TOP -> {TUPLE1 TUPLE2 TUPLEN}; - {TUPLE1 TUPLE2 TUPLEN} -> TUPLE_BOT; - } - - TOP -> {XCTRL INT_TOP FLT_TOP PTR_TOP STRUCT_TOP MEM_TOP TUPLE_TOP}; - {CTRL INT_BOT FLT_BOT PTR_BOT STRUCT_BOT MEM_BOT TUPLE_BOT} -> BOT; - {rank=same; XCTRL; INT_TOP; FLT_TOP; PTR_TOP; STRUCT_TOP; MEM_TOP; TUPLE_TOP;} - {rank=same; CTRL; INT_BOT; FLT_BOT; PTR_BOT; STRUCT_BOT; MEM_BOT; TUPLE_BOT;} - XCTRL -> INT_TOP -> FLT_TOP -> PTR_TOP -> STRUCT_TOP -> MEM_TOP -> TUPLE_TOP [style=invis]; -} diff --git a/chapter12/docs/lattice.svg b/chapter12/docs/lattice.svg deleted file mode 100644 index 41804d92..00000000 --- a/chapter12/docs/lattice.svg +++ /dev/null @@ -1,732 +0,0 @@ -<?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="2261pt" height="603pt" - viewBox="0.00 0.00 2261.00 603.45" 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 599.45)"> -<title>Lattice</title> -<polygon fill="white" stroke="none" points="-4,4 -4,-599.45 2257,-599.45 2257,4 -4,4"/> -<g id="clust1" class="cluster"> -<title>cluster_control</title> -<polygon fill="none" stroke="#cccccc" points="8,-85.99 8,-524.71 98,-524.71 98,-85.99 8,-85.99"/> -<text text-anchor="middle" x="53" y="-507.41" font-family="Arial" font-size="14.00">Control</text> -</g> -<g id="clust2" class="cluster"> -<title>cluster_integer</title> -<polygon fill="none" stroke="#cccccc" points="106,-85.99 106,-524.71 404,-524.71 404,-85.99 106,-85.99"/> -<text text-anchor="middle" x="255" y="-507.41" font-family="Arial" font-size="14.00">Integer</text> -</g> -<g id="clust6" class="cluster"> -<title>cluster_float</title> -<polygon fill="none" stroke="#cccccc" points="412,-85.99 412,-524.71 942,-524.71 942,-85.99 412,-85.99"/> -<text text-anchor="middle" x="677" y="-507.41" font-family="Arial" font-size="14.00">Float</text> -</g> -<g id="clust8" class="cluster"> -<title>cluster_pointer</title> -<polygon fill="none" stroke="#cccccc" points="950,-75 950,-535.7 1431,-535.7 1431,-75 950,-75"/> -<text text-anchor="middle" x="1190.5" y="-518.4" font-family="Arial" font-size="14.00">Pointer = nullability × struct type</text> -</g> -<g id="clust15" class="cluster"> -<title>cluster_struct</title> -<polygon fill="none" stroke="#cccccc" points="1439,-75 1439,-551.45 1767,-551.45 1767,-75 1439,-75"/> -<text text-anchor="middle" x="1603" y="-534.15" font-family="Arial" font-size="14.00">Struct</text> -<text text-anchor="middle" x="1603" y="-518.4" font-family="Arial" font-size="14.00">named collection of named scalar types</text> -</g> -<g id="clust19" class="cluster"> -<title>cluster_memory</title> -<polygon fill="none" stroke="#cccccc" points="1775,-85.99 1775,-540.46 2057,-540.46 2057,-85.99 1775,-85.99"/> -<text text-anchor="middle" x="1916" y="-523.16" font-family="Arial" font-size="14.00">Memory</text> -<text text-anchor="middle" x="1916" y="-507.41" font-family="Arial" font-size="14.00">precise alias slices</text> -</g> -<g id="clust23" class="cluster"> -<title>cluster_tuple</title> -<polygon fill="none" stroke="#cccccc" points="2065,-85.99 2065,-540.46 2245,-540.46 2245,-85.99 2065,-85.99"/> -<text text-anchor="middle" x="2155" y="-523.16" font-family="Arial" font-size="14.00">Tuple</text> -<text text-anchor="middle" x="2155" y="-507.41" font-family="Arial" font-size="14.00">collection of types</text> -</g> -<!-- TOP --> -<g id="node1" class="node"> -<title>TOP</title> -<ellipse fill="black" stroke="black" cx="1171" cy="-577.45" rx="27" ry="18"/> -<text text-anchor="middle" x="1171" y="-573.35" font-family="DejaVu Sans" font-size="13.00" fill="white">⊤</text> -</g> -<!-- XCTRL --> -<g id="node3" class="node"> -<title>XCTRL</title> -<ellipse fill="#ffff00" stroke="black" cx="53" cy="-474.96" rx="36.51" ry="18"/> -<text text-anchor="middle" x="53" y="-470.86" font-family="DejaVu Sans" font-size="13.00">⊤:ctrl</text> -</g> -<!-- TOP->XCTRL --> -<g id="edge68" class="edge"> -<title>TOP->XCTRL</title> -<path fill="none" stroke="#555555" d="M1143.75,-576.53C981.55,-576.91 148.8,-577.58 102,-551.45 82.13,-540.35 69.01,-517.44 61.39,-499.76"/> -<polygon fill="#555555" stroke="#555555" points="63.42,-499.19 59.21,-494.43 59.54,-500.78 63.42,-499.19"/> -</g> -<!-- INT_TOP --> -<g id="node5" class="node"> -<title>INT_TOP</title> -<ellipse fill="#add8e6" stroke="black" cx="353" cy="-474.96" rx="33.44" ry="18"/> -<text text-anchor="middle" x="353" y="-470.86" font-family="DejaVu Sans" font-size="13.00">⊤:int</text> -</g> -<!-- TOP->INT_TOP --> -<g id="edge69" class="edge"> -<title>TOP->INT_TOP</title> -<path fill="none" stroke="#555555" d="M1143.82,-576.22C1011.67,-575.05 441.13,-568.99 408,-551.45 387.13,-540.4 372.2,-517.48 363.21,-499.78"/> -<polygon fill="#555555" stroke="#555555" points="365.11,-498.89 360.61,-494.41 361.33,-500.72 365.11,-498.89"/> -</g> -<!-- FLT_TOP --> -<g id="node10" class="node"> -<title>FLT_TOP</title> -<ellipse fill="aqua" stroke="black" cx="755" cy="-474.96" rx="31.39" ry="18"/> -<text text-anchor="start" x="740" y="-471.86" font-family="DejaVu Sans" font-weight="bold" font-size="13.00">⊤</text> -<text text-anchor="start" x="752" y="-471.86" font-family="DejaVu Sans" font-size="13.00">:flt</text> -</g> -<!-- TOP->FLT_TOP --> -<g id="edge70" class="edge"> -<title>TOP->FLT_TOP</title> -<path fill="none" stroke="#555555" d="M1143.92,-575.75C1101.25,-574.14 1015.99,-568.84 946,-551.45 886.87,-536.76 821.59,-508.05 784.7,-490.58"/> -<polygon fill="#555555" stroke="#555555" points="785.84,-488.79 779.52,-488.1 784.03,-492.58 785.84,-488.79"/> -</g> -<!-- PTR_TOP --> -<g id="node15" class="node"> -<title>PTR_TOP</title> -<ellipse fill="#008000" stroke="black" cx="1171" cy="-474.96" rx="61.7" ry="28.99"/> -<text text-anchor="middle" x="1171" y="-479.11" font-family="DejaVu Sans" font-size="13.00" fill="white">⊤:ptr</text> -<text text-anchor="middle" x="1171" y="-462.61" font-family="DejaVu Sans" font-size="13.00" fill="white">[*⊤:struct]</text> -</g> -<!-- TOP->PTR_TOP --> -<g id="edge71" class="edge"> -<title>TOP->PTR_TOP</title> -<path fill="none" stroke="#555555" d="M1171,-559.4C1171,-546.29 1171,-527.72 1171,-511.43"/> -<polygon fill="#555555" stroke="#555555" points="1173.1,-511.64 1171,-505.64 1168.9,-511.64 1173.1,-511.64"/> -</g> -<!-- STRUCT_TOP --> -<g id="node25" class="node"> -<title>STRUCT_TOP</title> -<ellipse fill="#90ee90" stroke="black" cx="1558" cy="-474.96" rx="64.35" ry="28.99"/> -<text text-anchor="middle" x="1558" y="-479.11" font-family="DejaVu Sans" font-size="13.00">⊤:struct</text> -<text text-anchor="middle" x="1558" y="-462.61" font-family="DejaVu Sans" font-size="13.00">[struct top]</text> -</g> -<!-- TOP->STRUCT_TOP --> -<g id="edge72" class="edge"> -<title>TOP->STRUCT_TOP</title> -<path fill="none" stroke="#555555" d="M1197.97,-575.44C1256.13,-573.02 1391.55,-565.96 1435,-551.45 1466.2,-541.03 1497.74,-521.44 1521.07,-504.83"/> -<polygon fill="#555555" stroke="#555555" points="1522.26,-506.56 1525.9,-501.35 1519.8,-503.16 1522.26,-506.56"/> -</g> -<!-- MEM_TOP --> -<g id="node31" class="node"> -<title>MEM_TOP</title> -<ellipse fill="#00008b" stroke="black" cx="1881" cy="-474.96" rx="44.7" ry="18"/> -<text text-anchor="middle" x="1881" y="-470.86" font-family="DejaVu Sans" font-size="13.00" fill="white">⊤:mem</text> -</g> -<!-- TOP->MEM_TOP --> -<g id="edge73" class="edge"> -<title>TOP->MEM_TOP</title> -<path fill="none" stroke="#555555" d="M1198.14,-576.2C1307.98,-575.07 1716.29,-569.67 1771,-551.45 1804.95,-540.14 1837.98,-514.99 1858.84,-496.82"/> -<polygon fill="#555555" stroke="#555555" points="1860.16,-498.46 1863.26,-492.9 1857.37,-495.31 1860.16,-498.46"/> -</g> -<!-- TUPLE_TOP --> -<g id="node36" class="node"> -<title>TUPLE_TOP</title> -<ellipse fill="#ffc0cb" stroke="black" cx="2118" cy="-474.96" rx="44.7" ry="18"/> -<text text-anchor="middle" x="2118" y="-470.86" font-family="DejaVu Sans" font-size="13.00">⊤:tuple</text> -</g> -<!-- TOP->TUPLE_TOP --> -<g id="edge74" class="edge"> -<title>TOP->TUPLE_TOP</title> -<path fill="none" stroke="#555555" d="M1198.25,-576.35C1343.51,-575.71 2021.76,-571.68 2061,-551.45 2082.45,-540.39 2098.06,-517.15 2107.46,-499.36"/> -<polygon fill="#555555" stroke="#555555" points="2109.12,-500.74 2109.96,-494.43 2105.37,-498.84 2109.12,-500.74"/> -</g> -<!-- BOT --> -<g id="node2" class="node"> -<title>BOT</title> -<ellipse fill="black" stroke="black" cx="1237" cy="-18" rx="27" ry="18"/> -<text text-anchor="middle" x="1237" y="-13.9" font-family="DejaVu Sans" font-size="13.00" fill="white">⊥</text> -</g> -<!-- CTRL --> -<g id="node4" class="node"> -<title>CTRL</title> -<ellipse fill="#ffff00" stroke="black" cx="53" cy="-111.99" rx="36.51" ry="18"/> -<text text-anchor="middle" x="53" y="-107.89" font-family="DejaVu Sans" font-size="13.00">⊥:ctrl</text> -</g> -<!-- XCTRL->CTRL --> -<g id="edge1" class="edge"> -<title>XCTRL->CTRL</title> -<path fill="none" stroke="#555555" d="M53,-456.55C53,-397.7 53,-206.04 53,-137.58"/> -<polygon fill="#555555" stroke="#555555" points="55.1,-137.74 53,-131.74 50.9,-137.74 55.1,-137.74"/> -</g> -<!-- XCTRL->INT_TOP --> -<!-- CTRL->BOT --> -<g id="edge75" class="edge"> -<title>CTRL->BOT</title> -<path fill="none" stroke="#555555" d="M68.81,-95.65C77.79,-87.96 89.67,-79.38 102,-75 207.84,-37.39 1023.53,-22.38 1202.4,-19.52"/> -<polygon fill="#555555" stroke="#555555" points="1202.23,-21.63 1208.2,-19.43 1202.17,-17.43 1202.23,-21.63"/> -</g> -<!-- INT_NEG --> -<g id="node7" class="node"> -<title>INT_NEG</title> -<ellipse fill="#add8e6" stroke="black" cx="169" cy="-216.97" rx="55.45" ry="18"/> -<text text-anchor="middle" x="169" y="-212.87" font-family="DejaVu Sans" font-size="13.00">… −2, −1</text> -</g> -<!-- INT_TOP->INT_NEG --> -<g id="edge4" class="edge"> -<title>INT_TOP->INT_NEG</title> -<path fill="none" stroke="#555555" d="M338.42,-458.38C324.81,-443.56 304.22,-420.4 288,-398.97 246.77,-344.48 204.12,-276.17 182.84,-241.1"/> -<polygon fill="#555555" stroke="#555555" points="184.8,-240.29 179.9,-236.24 181.21,-242.46 184.8,-240.29"/> -</g> -<!-- INT_ZERO --> -<g id="node8" class="node"> -<title>INT_ZERO</title> -<ellipse fill="#add8e6" stroke="black" cx="267" cy="-216.97" rx="27" ry="18"/> -<text text-anchor="middle" x="267" y="-212.87" font-family="DejaVu Sans" font-size="13.00">0</text> -</g> -<!-- INT_TOP->INT_ZERO --> -<g id="edge5" class="edge"> -<title>INT_TOP->INT_ZERO</title> -<path fill="none" stroke="#555555" d="M347.22,-456.76C332.26,-412.21 292.18,-292.93 275,-241.79"/> -<polygon fill="#555555" stroke="#555555" points="277.02,-241.21 273.12,-236.19 273.04,-242.55 277.02,-241.21"/> -</g> -<!-- INT_POS --> -<g id="node9" class="node"> -<title>INT_POS</title> -<ellipse fill="#add8e6" stroke="black" cx="353" cy="-216.97" rx="43.16" ry="18"/> -<text text-anchor="middle" x="353" y="-212.87" font-family="DejaVu Sans" font-size="13.00">1, 2, …</text> -</g> -<!-- INT_TOP->INT_POS --> -<g id="edge6" class="edge"> -<title>INT_TOP->INT_POS</title> -<path fill="none" stroke="#555555" d="M353,-456.76C353,-412.51 353,-294.56 353,-242.85"/> -<polygon fill="#555555" stroke="#555555" points="355.1,-242.94 353,-236.94 350.9,-242.94 355.1,-242.94"/> -</g> -<!-- INT_TOP->FLT_TOP --> -<!-- INT_BOT --> -<g id="node6" class="node"> -<title>INT_BOT</title> -<ellipse fill="#add8e6" stroke="black" cx="310" cy="-111.99" rx="33.44" ry="18"/> -<text text-anchor="middle" x="310" y="-107.89" font-family="DejaVu Sans" font-size="13.00">⊥:int</text> -</g> -<!-- INT_BOT->BOT --> -<g id="edge76" class="edge"> -<title>INT_BOT->BOT</title> -<path fill="none" stroke="#555555" d="M334.8,-99.65C354.27,-91.29 382.29,-80.47 408,-75 563.61,-41.88 1066.53,-24.26 1202.72,-20.02"/> -<polygon fill="#555555" stroke="#555555" points="1202.6,-22.12 1208.53,-19.84 1202.47,-17.92 1202.6,-22.12"/> -</g> -<!-- INT_NEG->INT_BOT --> -<g id="edge7" class="edge"> -<title>INT_NEG->INT_BOT</title> -<path fill="none" stroke="#555555" d="M190.72,-200.11C216.15,-181.54 258.17,-150.85 284.95,-131.29"/> -<polygon fill="#555555" stroke="#555555" points="285.92,-133.18 289.52,-127.95 283.44,-129.79 285.92,-133.18"/> -</g> -<!-- INT_NEG->INT_ZERO --> -<!-- INT_ZERO->INT_BOT --> -<g id="edge8" class="edge"> -<title>INT_ZERO->INT_BOT</title> -<path fill="none" stroke="#555555" d="M273.91,-199.43C281.01,-182.41 292.14,-155.76 300.16,-136.55"/> -<polygon fill="#555555" stroke="#555555" points="302.01,-137.58 302.38,-131.24 298.13,-135.96 302.01,-137.58"/> -</g> -<!-- INT_ZERO->INT_POS --> -<!-- INT_POS->INT_BOT --> -<g id="edge9" class="edge"> -<title>INT_POS->INT_BOT</title> -<path fill="none" stroke="#555555" d="M345.9,-198.97C338.83,-182.05 327.93,-155.94 319.99,-136.93"/> -<polygon fill="#555555" stroke="#555555" points="321.94,-136.15 317.69,-131.42 318.07,-137.76 321.94,-136.15"/> -</g> -<!-- FLT_MINDOTS --> -<g id="node12" class="node"> -<title>FLT_MINDOTS</title> -<ellipse fill="aqua" stroke="black" cx="529" cy="-345.97" rx="109.19" ry="18"/> -<text text-anchor="middle" x="529" y="-341.87" font-family="DejaVu Sans" font-size="13.00">… negative constants</text> -</g> -<!-- FLT_TOP->FLT_MINDOTS --> -<g id="edge10" class="edge"> -<title>FLT_TOP->FLT_MINDOTS</title> -<path fill="none" stroke="#555555" d="M733.33,-461.78C694.5,-439.96 612.69,-393.99 565.21,-367.31"/> -<polygon fill="#555555" stroke="#555555" points="566.33,-365.53 560.07,-364.42 564.27,-369.19 566.33,-365.53"/> -</g> -<!-- FLT_ZERO --> -<g id="node13" class="node"> -<title>FLT_ZERO</title> -<ellipse fill="aqua" stroke="black" cx="681" cy="-345.97" rx="27" ry="18"/> -<text text-anchor="middle" x="681" y="-341.87" font-family="DejaVu Sans" font-size="13.00">0.0</text> -</g> -<!-- FLT_TOP->FLT_ZERO --> -<g id="edge11" class="edge"> -<title>FLT_TOP->FLT_ZERO</title> -<path fill="none" stroke="#555555" d="M745.33,-457.35C732.24,-434.89 708.83,-394.73 694.16,-369.54"/> -<polygon fill="#555555" stroke="#555555" points="696.04,-368.6 691.2,-364.48 692.41,-370.72 696.04,-368.6"/> -</g> -<!-- FLT_MAXDOTS --> -<g id="node14" class="node"> -<title>FLT_MAXDOTS</title> -<ellipse fill="aqua" stroke="black" cx="829" cy="-345.97" rx="105.09" ry="18"/> -<text text-anchor="middle" x="829" y="-341.87" font-family="DejaVu Sans" font-size="13.00">positive constants …</text> -</g> -<!-- FLT_TOP->FLT_MAXDOTS --> -<g id="edge12" class="edge"> -<title>FLT_TOP->FLT_MAXDOTS</title> -<path fill="none" stroke="#555555" d="M764.67,-457.35C777.62,-435.14 800.65,-395.61 815.36,-370.38"/> -<polygon fill="#555555" stroke="#555555" points="817.12,-371.53 818.33,-365.28 813.49,-369.41 817.12,-371.53"/> -</g> -<!-- FLT_TOP->PTR_TOP --> -<!-- FLT_BOT --> -<g id="node11" class="node"> -<title>FLT_BOT</title> -<ellipse fill="aqua" stroke="black" cx="718" cy="-111.99" rx="31.39" ry="18"/> -<text text-anchor="start" x="703" y="-108.89" font-family="DejaVu Sans" font-weight="bold" font-size="13.00">⊥</text> -<text text-anchor="start" x="715" y="-108.89" font-family="DejaVu Sans" font-size="13.00">:flt</text> -</g> -<!-- FLT_BOT->BOT --> -<g id="edge77" class="edge"> -<title>FLT_BOT->BOT</title> -<path fill="none" stroke="#555555" d="M747.77,-105.72C838.15,-89.69 1109.02,-41.68 1203.8,-24.88"/> -<polygon fill="#555555" stroke="#555555" points="1204.08,-26.97 1209.62,-23.85 1203.35,-22.83 1204.08,-26.97"/> -</g> -<!-- FLT_MINDOTS->FLT_BOT --> -<g id="edge13" class="edge"> -<title>FLT_MINDOTS->FLT_BOT</title> -<path fill="none" stroke="#555555" d="M542.9,-327.91C576.67,-286.45 663.03,-180.46 700.37,-134.63"/> -<polygon fill="#555555" stroke="#555555" points="701.97,-135.99 704.13,-130.01 698.72,-133.34 701.97,-135.99"/> -</g> -<!-- FLT_MINDOTS->FLT_ZERO --> -<!-- FLT_ZERO->FLT_BOT --> -<g id="edge14" class="edge"> -<title>FLT_ZERO->FLT_BOT</title> -<path fill="none" stroke="#555555" d="M683.72,-327.91C690.19,-287.37 706.5,-185.12 714.05,-137.77"/> -<polygon fill="#555555" stroke="#555555" points="716.12,-138.14 714.99,-131.88 711.97,-137.48 716.12,-138.14"/> -</g> -<!-- FLT_ZERO->FLT_MAXDOTS --> -<!-- FLT_MAXDOTS->FLT_BOT --> -<g id="edge15" class="edge"> -<title>FLT_MAXDOTS->FLT_BOT</title> -<path fill="none" stroke="#555555" d="M820.66,-327.53C800.95,-286.34 751.49,-182.98 729.2,-136.4"/> -<polygon fill="#555555" stroke="#555555" points="731.13,-135.56 726.64,-131.05 727.34,-137.37 731.13,-135.56"/> -</g> -<!-- PTR_NULL --> -<g id="node17" class="node"> -<title>PTR_NULL</title> -<ellipse fill="#008000" stroke="black" cx="1297" cy="-345.97" rx="27.3" ry="18"/> -<text text-anchor="middle" x="1297" y="-341.87" font-family="DejaVu Sans" font-size="13.00" fill="white">null</text> -</g> -<!-- PTR_TOP->PTR_NULL --> -<g id="edge24" class="edge"> -<title>PTR_TOP->PTR_NULL</title> -<path fill="none" stroke="#555555" d="M1204.16,-450.36C1222.35,-436.53 1244.66,-418.07 1262,-398.97 1270.08,-390.06 1277.71,-379.16 1283.77,-369.64"/> -<polygon fill="#555555" stroke="#555555" points="1285.52,-370.8 1286.9,-364.59 1281.95,-368.58 1285.52,-370.8"/> -</g> -<!-- PTR_PERSON --> -<g id="node19" class="node"> -<title>PTR_PERSON</title> -<ellipse fill="#008000" stroke="black" cx="1040" cy="-345.97" rx="45.72" ry="18"/> -<text text-anchor="middle" x="1040" y="-341.87" font-family="DejaVu Sans" font-size="13.00" fill="white">*Person</text> -</g> -<!-- PTR_TOP->PTR_PERSON --> -<g id="edge25" class="edge"> -<title>PTR_TOP->PTR_PERSON</title> -<path fill="none" stroke="#555555" d="M1144.81,-448.56C1120.47,-424.98 1084.66,-390.26 1061.83,-368.13"/> -<polygon fill="#555555" stroke="#555555" points="1063.46,-366.79 1057.69,-364.12 1060.54,-369.8 1063.46,-366.79"/> -</g> -<!-- PTR_S1 --> -<g id="node20" class="node"> -<title>PTR_S1</title> -<ellipse fill="#008000" stroke="black" cx="1129" cy="-345.97" rx="27" ry="18"/> -<text text-anchor="middle" x="1129" y="-341.87" font-family="DejaVu Sans" font-size="13.00" fill="white">*s1</text> -</g> -<!-- PTR_TOP->PTR_S1 --> -<g id="edge26" class="edge"> -<title>PTR_TOP->PTR_S1</title> -<path fill="none" stroke="#555555" d="M1161.78,-446.09C1154.35,-423.62 1144.01,-392.36 1136.94,-370.98"/> -<polygon fill="#555555" stroke="#555555" points="1138.94,-370.34 1135.06,-365.3 1134.96,-371.66 1138.94,-370.34"/> -</g> -<!-- PTR_MORE --> -<g id="node21" class="node"> -<title>PTR_MORE</title> -<ellipse fill="#008000" stroke="black" cx="1213" cy="-345.97" rx="40.6" ry="18"/> -<text text-anchor="middle" x="1213" y="-341.87" font-family="DejaVu Sans" font-size="13.00" fill="white">*s2, …</text> -</g> -<!-- PTR_TOP->PTR_MORE --> -<g id="edge27" class="edge"> -<title>PTR_TOP->PTR_MORE</title> -<path fill="none" stroke="#555555" d="M1180.22,-446.09C1187.6,-423.75 1197.87,-392.72 1204.93,-371.36"/> -<polygon fill="#555555" stroke="#555555" points="1206.92,-372.03 1206.81,-365.67 1202.94,-370.71 1206.92,-372.03"/> -</g> -<!-- PTR_TOP->STRUCT_TOP --> -<!-- PTR_BOT --> -<g id="node16" class="node"> -<title>PTR_BOT</title> -<ellipse fill="#008000" stroke="black" cx="1237" cy="-111.99" rx="66.47" ry="28.99"/> -<text text-anchor="middle" x="1237" y="-116.14" font-family="DejaVu Sans" font-size="13.00" fill="white">⊥:ptr</text> -<text text-anchor="middle" x="1237" y="-99.64" font-family="DejaVu Sans" font-size="13.00" fill="white">[*⊥:struct?]</text> -</g> -<!-- PTR_BOT->BOT --> -<g id="edge78" class="edge"> -<title>PTR_BOT->BOT</title> -<path fill="none" stroke="#555555" d="M1237,-82.64C1237,-70.25 1237,-55.86 1237,-43.89"/> -<polygon fill="#555555" stroke="#555555" points="1239.1,-43.94 1237,-37.94 1234.9,-43.94 1239.1,-43.94"/> -</g> -<!-- PTR_PERSON_NIL --> -<g id="node22" class="node"> -<title>PTR_PERSON_NIL</title> -<ellipse fill="#008000" stroke="black" cx="1189" cy="-216.97" rx="50.33" ry="18"/> -<text text-anchor="middle" x="1189" y="-212.87" font-family="DejaVu Sans" font-size="13.00" fill="white">*Person?</text> -</g> -<!-- PTR_NULL->PTR_PERSON_NIL --> -<g id="edge34" class="edge"> -<title>PTR_NULL->PTR_PERSON_NIL</title> -<path fill="none" stroke="#555555" d="M1287.29,-328.97C1280.63,-318.41 1271.33,-304.45 1262,-292.97 1246.39,-273.75 1226.71,-253.74 1211.73,-239.23"/> -<polygon fill="#555555" stroke="#555555" points="1213.3,-237.84 1207.52,-235.19 1210.39,-240.87 1213.3,-237.84"/> -</g> -<!-- PTR_S1_NIL --> -<g id="node23" class="node"> -<title>PTR_S1_NIL</title> -<ellipse fill="#008000" stroke="black" cx="1286" cy="-216.97" rx="30.37" ry="18"/> -<text text-anchor="middle" x="1286" y="-212.87" font-family="DejaVu Sans" font-size="13.00" fill="white">*s1?</text> -</g> -<!-- PTR_NULL->PTR_S1_NIL --> -<g id="edge35" class="edge"> -<title>PTR_NULL->PTR_S1_NIL</title> -<path fill="none" stroke="#555555" d="M1295.49,-327.57C1293.58,-305.54 1290.28,-267.42 1288.12,-242.45"/> -<polygon fill="#555555" stroke="#555555" points="1290.23,-242.46 1287.62,-236.66 1286.04,-242.82 1290.23,-242.46"/> -</g> -<!-- PTR_MORE_NIL --> -<g id="node24" class="node"> -<title>PTR_MORE_NIL</title> -<ellipse fill="#008000" stroke="black" cx="1378" cy="-216.97" rx="45.21" ry="18"/> -<text text-anchor="middle" x="1378" y="-212.87" font-family="DejaVu Sans" font-size="13.00" fill="white">*s2?, …</text> -</g> -<!-- PTR_NULL->PTR_MORE_NIL --> -<g id="edge36" class="edge"> -<title>PTR_NULL->PTR_MORE_NIL</title> -<path fill="none" stroke="#555555" d="M1307.26,-328.88C1321.47,-306.61 1347.21,-266.25 1363.41,-240.85"/> -<polygon fill="#555555" stroke="#555555" points="1365.04,-242.2 1366.5,-236.01 1361.5,-239.94 1365.04,-242.2"/> -</g> -<!-- PTR_ANY --> -<g id="node18" class="node"> -<title>PTR_ANY</title> -<ellipse fill="#008000" stroke="black" cx="1040" cy="-216.97" rx="82.38" ry="28.99"/> -<text text-anchor="middle" x="1040" y="-221.12" font-family="DejaVu Sans" font-size="13.00" fill="white">*⊥:struct</text> -<text text-anchor="middle" x="1040" y="-204.62" font-family="DejaVu Sans" font-size="13.00" fill="white">[ptr any struct]</text> -</g> -<!-- PTR_ANY->PTR_BOT --> -<g id="edge37" class="edge"> -<title>PTR_ANY->PTR_BOT</title> -<path fill="none" stroke="#555555" d="M1085.2,-192.35C1116.06,-176.21 1156.91,-154.86 1188.46,-138.37"/> -<polygon fill="#555555" stroke="#555555" points="1189.36,-140.27 1193.7,-135.63 1187.41,-136.54 1189.36,-140.27"/> -</g> -<!-- PTR_ANY->PTR_PERSON_NIL --> -<!-- PTR_PERSON->PTR_ANY --> -<g id="edge28" class="edge"> -<title>PTR_PERSON->PTR_ANY</title> -<path fill="none" stroke="#555555" d="M1040,-327.57C1040,-308.61 1040,-277.75 1040,-253.6"/> -<polygon fill="#555555" stroke="#555555" points="1042.1,-253.86 1040,-247.86 1037.9,-253.86 1042.1,-253.86"/> -</g> -<!-- PTR_PERSON->PTR_S1 --> -<!-- PTR_PERSON->PTR_PERSON_NIL --> -<g id="edge31" class="edge"> -<title>PTR_PERSON->PTR_PERSON_NIL</title> -<path fill="none" stroke="#555555" d="M1055.68,-329.07C1066.26,-318.55 1080.66,-304.6 1094,-292.97 1116.38,-273.44 1143.02,-252.61 1162.38,-237.87"/> -<polygon fill="#555555" stroke="#555555" points="1163.43,-239.71 1166.94,-234.41 1160.89,-236.36 1163.43,-239.71"/> -</g> -<!-- PTR_S1->PTR_ANY --> -<g id="edge29" class="edge"> -<title>PTR_S1->PTR_ANY</title> -<path fill="none" stroke="#555555" d="M1118.41,-328.95C1111.53,-318.62 1102.33,-304.93 1094,-292.97 1084.38,-279.15 1073.57,-264.06 1064.17,-251.06"/> -<polygon fill="#555555" stroke="#555555" points="1066.07,-250.1 1060.85,-246.48 1062.67,-252.57 1066.07,-250.1"/> -</g> -<!-- PTR_S1->PTR_MORE --> -<!-- PTR_S1->PTR_S1_NIL --> -<g id="edge32" class="edge"> -<title>PTR_S1->PTR_S1_NIL</title> -<path fill="none" stroke="#555555" d="M1137.43,-328.51C1143.67,-317.48 1152.98,-303.17 1164,-292.97 1195.11,-264.17 1211.28,-268.8 1247,-245.97 1251.84,-242.87 1256.9,-239.42 1261.71,-236.02"/> -<polygon fill="#555555" stroke="#555555" points="1262.75,-237.85 1266.4,-232.65 1260.3,-234.44 1262.75,-237.85"/> -</g> -<!-- PTR_MORE->PTR_NULL --> -<!-- PTR_MORE->PTR_ANY --> -<g id="edge30" class="edge"> -<title>PTR_MORE->PTR_ANY</title> -<path fill="none" stroke="#555555" d="M1199.85,-328.86C1190.51,-317.99 1177.32,-303.72 1164,-292.97 1141.82,-275.05 1114.97,-258.29 1091.94,-245.19"/> -<polygon fill="#555555" stroke="#555555" points="1093.13,-243.45 1086.87,-242.33 1091.07,-247.11 1093.13,-243.45"/> -</g> -<!-- PTR_MORE->PTR_MORE_NIL --> -<g id="edge33" class="edge"> -<title>PTR_MORE->PTR_MORE_NIL</title> -<path fill="none" stroke="#555555" d="M1226.25,-328.99C1235.64,-318.18 1248.85,-303.92 1262,-292.97 1288.56,-270.85 1321.98,-249.86 1346.12,-235.75"/> -<polygon fill="#555555" stroke="#555555" points="1346.91,-237.72 1351.04,-232.89 1344.8,-234.09 1346.91,-237.72"/> -</g> -<!-- PTR_PERSON_NIL->PTR_BOT --> -<g id="edge38" class="edge"> -<title>PTR_PERSON_NIL->PTR_BOT</title> -<path fill="none" stroke="#555555" d="M1196.93,-198.97C1203.41,-185.05 1212.8,-164.91 1220.86,-147.62"/> -<polygon fill="#555555" stroke="#555555" points="1222.72,-148.6 1223.35,-142.27 1218.91,-146.83 1222.72,-148.6"/> -</g> -<!-- PTR_PERSON_NIL->PTR_S1_NIL --> -<!-- PTR_S1_NIL->PTR_BOT --> -<g id="edge39" class="edge"> -<title>PTR_S1_NIL->PTR_BOT</title> -<path fill="none" stroke="#555555" d="M1278.13,-199.43C1271.43,-185.35 1261.59,-164.68 1253.22,-147.07"/> -<polygon fill="#555555" stroke="#555555" points="1255.33,-146.63 1250.86,-142.11 1251.54,-148.43 1255.33,-146.63"/> -</g> -<!-- PTR_S1_NIL->PTR_MORE_NIL --> -<!-- PTR_MORE_NIL->PTR_BOT --> -<g id="edge40" class="edge"> -<title>PTR_MORE_NIL->PTR_BOT</title> -<path fill="none" stroke="#555555" d="M1357.19,-200.78C1335.97,-185.28 1302.52,-160.85 1276.3,-141.69"/> -<polygon fill="#555555" stroke="#555555" points="1277.78,-140.18 1271.7,-138.33 1275.31,-143.57 1277.78,-140.18"/> -</g> -<!-- STRUCT_PERSON --> -<g id="node27" class="node"> -<title>STRUCT_PERSON</title> -<polygon fill="#90ee90" stroke="black" points="1514.5,-237.47 1447.5,-237.47 1447.5,-196.47 1514.5,-196.47 1514.5,-237.47"/> -<text text-anchor="middle" x="1481" y="-221.12" font-family="DejaVu Sans" font-size="13.00">Person</text> -<text text-anchor="middle" x="1481" y="-204.62" font-family="DejaVu Sans" font-size="13.00">age: int</text> -</g> -<!-- STRUCT_TOP->STRUCT_PERSON --> -<g id="edge44" class="edge"> -<title>STRUCT_TOP->STRUCT_PERSON</title> -<path fill="none" stroke="#555555" d="M1549.61,-446.07C1534.71,-396.53 1503.8,-293.77 1489.1,-244.91"/> -<polygon fill="#555555" stroke="#555555" points="1491.15,-244.41 1487.41,-239.27 1487.12,-245.62 1491.15,-244.41"/> -</g> -<!-- STRUCT_S1 --> -<g id="node28" class="node"> -<title>STRUCT_S1</title> -<polygon fill="#90ee90" stroke="black" points="1585,-237.47 1531,-237.47 1531,-196.47 1585,-196.47 1585,-237.47"/> -<text text-anchor="middle" x="1558" y="-221.12" font-family="DejaVu Sans" font-size="13.00">s1</text> -<text text-anchor="middle" x="1558" y="-204.62" font-family="DejaVu Sans" font-size="13.00">x: int</text> -</g> -<!-- STRUCT_TOP->STRUCT_S1 --> -<g id="edge45" class="edge"> -<title>STRUCT_TOP->STRUCT_S1</title> -<path fill="none" stroke="#555555" d="M1558,-445.58C1558,-395.91 1558,-293.85 1558,-245.08"/> -<polygon fill="#555555" stroke="#555555" points="1560.1,-245.25 1558,-239.25 1555.9,-245.25 1560.1,-245.25"/> -</g> -<!-- STRUCT_S2 --> -<g id="node29" class="node"> -<title>STRUCT_S2</title> -<polygon fill="#90ee90" stroke="black" points="1689,-237.47 1601,-237.47 1601,-196.47 1689,-196.47 1689,-237.47"/> -<text text-anchor="middle" x="1645" y="-221.12" font-family="DejaVu Sans" font-size="13.00">s2</text> -<text text-anchor="middle" x="1645" y="-204.62" font-family="DejaVu Sans" font-size="13.00">x: int, y: flt</text> -</g> -<!-- STRUCT_TOP->STRUCT_S2 --> -<g id="edge46" class="edge"> -<title>STRUCT_TOP->STRUCT_S2</title> -<path fill="none" stroke="#555555" d="M1567.48,-446.07C1584.32,-396.53 1619.24,-293.77 1635.85,-244.91"/> -<polygon fill="#555555" stroke="#555555" points="1637.82,-245.61 1637.77,-239.26 1633.85,-244.26 1637.82,-245.61"/> -</g> -<!-- STRUCT_MORE --> -<g id="node30" class="node"> -<title>STRUCT_MORE</title> -<polygon fill="#90ee90" stroke="black" points="1759,-234.97 1705,-234.97 1705,-198.97 1759,-198.97 1759,-234.97"/> -<text text-anchor="middle" x="1732" y="-212.87" font-family="DejaVu Sans" font-size="13.00">…</text> -</g> -<!-- STRUCT_TOP->STRUCT_MORE --> -<g id="edge47" class="edge"> -<title>STRUCT_TOP->STRUCT_MORE</title> -<path fill="none" stroke="#555555" d="M1576.29,-447.05C1610.53,-396.68 1683.74,-288.97 1716.08,-241.39"/> -<polygon fill="#555555" stroke="#555555" points="1717.7,-242.75 1719.33,-236.61 1714.22,-240.39 1717.7,-242.75"/> -</g> -<!-- STRUCT_TOP->MEM_TOP --> -<!-- STRUCT_BOT --> -<g id="node26" class="node"> -<title>STRUCT_BOT</title> -<ellipse fill="#90ee90" stroke="black" cx="1558" cy="-111.99" rx="82.91" ry="28.99"/> -<text text-anchor="middle" x="1558" y="-116.14" font-family="DejaVu Sans" font-size="13.00">⊥:struct</text> -<text text-anchor="middle" x="1558" y="-99.64" font-family="DejaVu Sans" font-size="13.00">[struct bottom]</text> -</g> -<!-- STRUCT_BOT->BOT --> -<g id="edge79" class="edge"> -<title>STRUCT_BOT->BOT</title> -<path fill="none" stroke="#555555" d="M1495.46,-92.57C1476.09,-86.9 1454.67,-80.66 1435,-75 1376.34,-58.12 1307.78,-38.83 1268.67,-27.86"/> -<polygon fill="#555555" stroke="#555555" points="1269.52,-25.92 1263.17,-26.32 1268.38,-29.96 1269.52,-25.92"/> -</g> -<!-- STRUCT_PERSON->STRUCT_BOT --> -<g id="edge48" class="edge"> -<title>STRUCT_PERSON->STRUCT_BOT</title> -<path fill="none" stroke="#555555" d="M1495.85,-196.12C1506.43,-181.96 1520.92,-162.59 1533.24,-146.11"/> -<polygon fill="#555555" stroke="#555555" points="1534.85,-147.46 1536.76,-141.4 1531.49,-144.94 1534.85,-147.46"/> -</g> -<!-- STRUCT_PERSON->STRUCT_S1 --> -<!-- STRUCT_S1->STRUCT_BOT --> -<g id="edge49" class="edge"> -<title>STRUCT_S1->STRUCT_BOT</title> -<path fill="none" stroke="#555555" d="M1558,-196.12C1558,-182.64 1558,-164.43 1558,-148.49"/> -<polygon fill="#555555" stroke="#555555" points="1560.1,-148.87 1558,-142.87 1555.9,-148.87 1560.1,-148.87"/> -</g> -<!-- STRUCT_S1->STRUCT_S2 --> -<!-- STRUCT_S2->STRUCT_BOT --> -<g id="edge50" class="edge"> -<title>STRUCT_S2->STRUCT_BOT</title> -<path fill="none" stroke="#555555" d="M1628.23,-196.12C1616.16,-181.83 1599.61,-162.25 1585.61,-145.68"/> -<polygon fill="#555555" stroke="#555555" points="1587.43,-144.57 1581.95,-141.34 1584.22,-147.28 1587.43,-144.57"/> -</g> -<!-- STRUCT_S2->STRUCT_MORE --> -<!-- STRUCT_MORE->STRUCT_BOT --> -<g id="edge51" class="edge"> -<title>STRUCT_MORE->STRUCT_BOT</title> -<path fill="none" stroke="#555555" d="M1711.74,-198.76C1707.02,-195.04 1701.93,-191.25 1697,-187.98 1670.12,-170.19 1638.63,-152.93 1612.41,-139.46"/> -<polygon fill="#555555" stroke="#555555" points="1613.52,-137.67 1607.22,-136.81 1611.61,-141.41 1613.52,-137.67"/> -</g> -<!-- MEM_ALIAS2 --> -<g id="node33" class="node"> -<title>MEM_ALIAS2</title> -<ellipse fill="#00008b" stroke="black" cx="1828" cy="-216.97" rx="45.21" ry="18"/> -<text text-anchor="middle" x="1828" y="-212.87" font-family="DejaVu Sans" font-size="13.00" fill="white">MEM#2</text> -</g> -<!-- MEM_TOP->MEM_ALIAS2 --> -<g id="edge54" class="edge"> -<title>MEM_TOP->MEM_ALIAS2</title> -<path fill="none" stroke="#555555" d="M1877.44,-456.76C1868.24,-412.32 1843.64,-293.5 1833.01,-242.16"/> -<polygon fill="#555555" stroke="#555555" points="1835.12,-242.02 1831.85,-236.57 1831.01,-242.88 1835.12,-242.02"/> -</g> -<!-- MEM_ALIAS3 --> -<g id="node34" class="node"> -<title>MEM_ALIAS3</title> -<ellipse fill="#00008b" stroke="black" cx="1934" cy="-216.97" rx="45.21" ry="18"/> -<text text-anchor="middle" x="1934" y="-212.87" font-family="DejaVu Sans" font-size="13.00" fill="white">MEM#3</text> -</g> -<!-- MEM_TOP->MEM_ALIAS3 --> -<g id="edge55" class="edge"> -<title>MEM_TOP->MEM_ALIAS3</title> -<path fill="none" stroke="#555555" d="M1884.56,-456.76C1893.76,-412.32 1918.36,-293.5 1928.99,-242.16"/> -<polygon fill="#555555" stroke="#555555" points="1930.99,-242.88 1930.15,-236.57 1926.88,-242.02 1930.99,-242.88"/> -</g> -<!-- MEM_MORE --> -<g id="node35" class="node"> -<title>MEM_MORE</title> -<ellipse fill="#00008b" stroke="black" cx="2022" cy="-216.97" rx="27" ry="18"/> -<text text-anchor="middle" x="2022" y="-212.87" font-family="DejaVu Sans" font-size="13.00" fill="white">…</text> -</g> -<!-- MEM_TOP->MEM_MORE --> -<g id="edge56" class="edge"> -<title>MEM_TOP->MEM_MORE</title> -<path fill="none" stroke="#555555" d="M1890.25,-457.16C1914.82,-412.56 1981.72,-291.1 2009.57,-240.54"/> -<polygon fill="#555555" stroke="#555555" points="2011.29,-241.76 2012.35,-235.49 2007.62,-239.74 2011.29,-241.76"/> -</g> -<!-- MEM_TOP->TUPLE_TOP --> -<!-- MEM_BOT --> -<g id="node32" class="node"> -<title>MEM_BOT</title> -<ellipse fill="#00008b" stroke="black" cx="1881" cy="-111.99" rx="44.7" ry="18"/> -<text text-anchor="middle" x="1881" y="-107.89" font-family="DejaVu Sans" font-size="13.00" fill="white">⊥:mem</text> -</g> -<!-- MEM_BOT->BOT --> -<g id="edge80" class="edge"> -<title>MEM_BOT->BOT</title> -<path fill="none" stroke="#555555" d="M1849.72,-98.79C1827.96,-90.8 1798.12,-80.79 1771,-75 1585.39,-35.37 1357.24,-23.36 1271.62,-20.1"/> -<polygon fill="#555555" stroke="#555555" points="1271.85,-18 1265.78,-19.88 1271.7,-22.2 1271.85,-18"/> -</g> -<!-- MEM_ALIAS2->MEM_BOT --> -<g id="edge57" class="edge"> -<title>MEM_ALIAS2->MEM_BOT</title> -<path fill="none" stroke="#555555" d="M1836.75,-198.97C1845.5,-181.97 1859.02,-155.71 1868.81,-136.68"/> -<polygon fill="#555555" stroke="#555555" points="1870.66,-137.66 1871.54,-131.37 1866.93,-135.74 1870.66,-137.66"/> -</g> -<!-- MEM_ALIAS2->MEM_ALIAS3 --> -<!-- MEM_ALIAS3->MEM_BOT --> -<g id="edge58" class="edge"> -<title>MEM_ALIAS3->MEM_BOT</title> -<path fill="none" stroke="#555555" d="M1925.25,-198.97C1916.5,-181.97 1902.98,-155.71 1893.19,-136.68"/> -<polygon fill="#555555" stroke="#555555" points="1895.07,-135.74 1890.46,-131.37 1891.34,-137.66 1895.07,-135.74"/> -</g> -<!-- MEM_ALIAS3->MEM_MORE --> -<!-- MEM_MORE->MEM_BOT --> -<g id="edge59" class="edge"> -<title>MEM_MORE->MEM_BOT</title> -<path fill="none" stroke="#555555" d="M2005.42,-202.39C1999.65,-197.74 1993.09,-192.57 1987,-187.98 1960.93,-168.37 1930.47,-146.96 1908.9,-132.06"/> -<polygon fill="#555555" stroke="#555555" points="1910.17,-130.38 1904.03,-128.71 1907.78,-133.84 1910.17,-130.38"/> -</g> -<!-- TUPLE1 --> -<g id="node38" class="node"> -<title>TUPLE1</title> -<polygon fill="#ffc0cb" stroke="none" points="2116.88,-372.47 2073.12,-372.47 2073.12,-319.47 2116.88,-319.47 2116.88,-372.47"/> -<polygon fill="#ffc0cb" stroke="none" points="2073.12,-345.97 2073.12,-372.47 2116.88,-372.47 2116.88,-345.97 2073.12,-345.97"/> -<polygon fill="none" stroke="black" points="2073.12,-345.97 2073.12,-372.47 2116.88,-372.47 2116.88,-345.97 2073.12,-345.97"/> -<text text-anchor="start" x="2078.12" y="-355.12" font-family="DejaVu Sans" font-size="13.00">tuple</text> -<polygon fill="black" stroke="none" points="2073.12,-319.47 2073.12,-345.97 2116.88,-345.97 2116.88,-319.47 2073.12,-319.47"/> -<polygon fill="none" stroke="black" points="2073.12,-319.47 2073.12,-345.97 2116.88,-345.97 2116.88,-319.47 2073.12,-319.47"/> -<text text-anchor="start" x="2080.38" y="-328.62" font-family="DejaVu Sans" font-size="13.00" fill="white">type</text> -</g> -<!-- TUPLE_TOP->TUPLE1 --> -<g id="edge62" class="edge"> -<title>TUPLE_TOP->TUPLE1</title> -<path fill="none" stroke="#555555" d="M2114.85,-456.57C2111.26,-436.74 2105.31,-403.91 2100.86,-379.34"/> -<polygon fill="#555555" stroke="#555555" points="2102.94,-379.03 2099.81,-373.5 2098.81,-379.77 2102.94,-379.03"/> -</g> -<!-- TUPLE2 --> -<g id="node39" class="node"> -<title>TUPLE2</title> -<polygon fill="#ffc0cb" stroke="none" points="2176.88,-385.72 2133.12,-385.72 2133.12,-306.22 2176.88,-306.22 2176.88,-385.72"/> -<polygon fill="#ffc0cb" stroke="none" points="2133.12,-359.22 2133.12,-385.72 2176.88,-385.72 2176.88,-359.22 2133.12,-359.22"/> -<polygon fill="none" stroke="black" points="2133.12,-359.22 2133.12,-385.72 2176.88,-385.72 2176.88,-359.22 2133.12,-359.22"/> -<text text-anchor="start" x="2138.12" y="-368.37" font-family="DejaVu Sans" font-size="13.00">tuple</text> -<polygon fill="black" stroke="none" points="2133.12,-332.72 2133.12,-359.22 2176.88,-359.22 2176.88,-332.72 2133.12,-332.72"/> -<polygon fill="none" stroke="black" points="2133.12,-332.72 2133.12,-359.22 2176.88,-359.22 2176.88,-332.72 2133.12,-332.72"/> -<text text-anchor="start" x="2140.38" y="-341.87" font-family="DejaVu Sans" font-size="13.00" fill="white">type</text> -<polygon fill="black" stroke="none" points="2133.12,-306.22 2133.12,-332.72 2176.88,-332.72 2176.88,-306.22 2133.12,-306.22"/> -<polygon fill="none" stroke="black" points="2133.12,-306.22 2133.12,-332.72 2176.88,-332.72 2176.88,-306.22 2133.12,-306.22"/> -<text text-anchor="start" x="2140.38" y="-315.37" font-family="DejaVu Sans" font-size="13.00" fill="white">type</text> -</g> -<!-- TUPLE_TOP->TUPLE2 --> -<g id="edge63" class="edge"> -<title>TUPLE_TOP->TUPLE2</title> -<path fill="none" stroke="#555555" d="M2122.99,-456.83C2127.76,-440.46 2135.17,-415.04 2141.65,-392.78"/> -<polygon fill="#555555" stroke="#555555" points="2143.64,-393.48 2143.3,-387.13 2139.6,-392.3 2143.64,-393.48"/> -</g> -<!-- TUPLEN --> -<g id="node40" class="node"> -<title>TUPLEN</title> -<polygon fill="#ffc0cb" stroke="none" points="2236.88,-398.97 2193.12,-398.97 2193.12,-292.97 2236.88,-292.97 2236.88,-398.97"/> -<polygon fill="#ffc0cb" stroke="none" points="2193.12,-372.47 2193.12,-398.97 2236.88,-398.97 2236.88,-372.47 2193.12,-372.47"/> -<polygon fill="none" stroke="black" points="2193.12,-372.47 2193.12,-398.97 2236.88,-398.97 2236.88,-372.47 2193.12,-372.47"/> -<text text-anchor="start" x="2198.12" y="-381.62" font-family="DejaVu Sans" font-size="13.00">tuple</text> -<polygon fill="black" stroke="none" points="2193.12,-345.97 2193.12,-372.47 2236.88,-372.47 2236.88,-345.97 2193.12,-345.97"/> -<polygon fill="none" stroke="black" points="2193.12,-345.97 2193.12,-372.47 2236.88,-372.47 2236.88,-345.97 2193.12,-345.97"/> -<text text-anchor="start" x="2200.38" y="-355.12" font-family="DejaVu Sans" font-size="13.00" fill="white">type</text> -<polygon fill="black" stroke="none" points="2193.12,-319.47 2193.12,-345.97 2236.88,-345.97 2236.88,-319.47 2193.12,-319.47"/> -<polygon fill="none" stroke="black" points="2193.12,-319.47 2193.12,-345.97 2236.88,-345.97 2236.88,-319.47 2193.12,-319.47"/> -<text text-anchor="start" x="2208.62" y="-328.62" font-family="DejaVu Sans" font-size="13.00" fill="white">…</text> -<polygon fill="black" stroke="none" points="2193.12,-292.97 2193.12,-319.47 2236.88,-319.47 2236.88,-292.97 2193.12,-292.97"/> -<polygon fill="none" stroke="black" points="2193.12,-292.97 2193.12,-319.47 2236.88,-319.47 2236.88,-292.97 2193.12,-292.97"/> -<text text-anchor="start" x="2200.38" y="-302.12" font-family="DejaVu Sans" font-size="13.00" fill="white">type</text> -</g> -<!-- TUPLE_TOP->TUPLEN --> -<g id="edge64" class="edge"> -<title>TUPLE_TOP->TUPLEN</title> -<path fill="none" stroke="#555555" d="M2134.21,-457.82C2148.47,-443.17 2169.34,-420.61 2185,-398.97 2186.4,-397.02 2187.8,-395.01 2189.17,-392.95"/> -<polygon fill="#555555" stroke="#555555" points="2190.91,-394.14 2192.41,-387.96 2187.38,-391.86 2190.91,-394.14"/> -</g> -<!-- TUPLE_BOT --> -<g id="node37" class="node"> -<title>TUPLE_BOT</title> -<ellipse fill="#ffc0cb" stroke="black" cx="2136" cy="-111.99" rx="44.7" ry="18"/> -<text text-anchor="middle" x="2136" y="-107.89" font-family="DejaVu Sans" font-size="13.00">⊥:tuple</text> -</g> -<!-- TUPLE_BOT->BOT --> -<g id="edge81" class="edge"> -<title>TUPLE_BOT->BOT</title> -<path fill="none" stroke="#555555" d="M2111.91,-96.53C2097.63,-88.71 2078.88,-79.71 2061,-75 1908.25,-34.75 1408.04,-22.3 1271.63,-19.61"/> -<polygon fill="#555555" stroke="#555555" points="1271.84,-17.52 1265.8,-19.5 1271.76,-21.72 1271.84,-17.52"/> -</g> -<!-- TUPLE1->TUPLE_BOT --> -<g id="edge65" class="edge"> -<title>TUPLE1->TUPLE_BOT</title> -<path fill="none" stroke="#555555" d="M2099.47,-319.7C2107.39,-274.85 2123.82,-181.9 2131.66,-137.56"/> -<polygon fill="#555555" stroke="#555555" points="2133.69,-138.14 2132.66,-131.86 2129.55,-137.4 2133.69,-138.14"/> -</g> -<!-- TUPLE1->TUPLE2 --> -<!-- TUPLE2->TUPLE_BOT --> -<g id="edge66" class="edge"> -<title>TUPLE2->TUPLE_BOT</title> -<path fill="none" stroke="#555555" d="M2151.84,-306.4C2147.91,-258.37 2141.3,-177.75 2138,-137.46"/> -<polygon fill="#555555" stroke="#555555" points="2140.13,-137.74 2137.55,-131.93 2135.95,-138.08 2140.13,-137.74"/> -</g> -<!-- TUPLE2->TUPLEN --> -<!-- TUPLEN->TUPLE_BOT --> -<g id="edge67" class="edge"> -<title>TUPLEN->TUPLE_BOT</title> -<path fill="none" stroke="#555555" d="M2197.37,-293.19C2180.79,-244.5 2156.69,-173.75 2144.2,-137.07"/> -<polygon fill="#555555" stroke="#555555" points="2146.27,-136.64 2142.35,-131.63 2142.3,-137.99 2146.27,-136.64"/> -</g> -</g> -</svg> diff --git a/chapter12/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter12/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java deleted file mode 100644 index 74b58e6b..00000000 --- a/chapter12/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ /dev/null @@ -1,271 +0,0 @@ - package com.seaofnodes.simple; - -import com.seaofnodes.simple.IterPeeps.WorkList; -import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.type.*; -import java.util.*; - -public abstract class GlobalCodeMotion { - - // Arrange that the existing isCFG() Nodes form a valid CFG. The - // 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 ) { - schedEarly(); - Parser.SCHEDULED = true; - schedLate(stop); - } - - // ------------------------------------------------------------------------ - // 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 - static void fixLoops(StopNode stop) { - // Backwards walk from Stop, looking for unreachable code - BitSet visit = new BitSet(); - HashSet<CFGNode> unreach = new HashSet<>(); - unreach.add(Parser.START); - for( Node ret : stop._inputs ) - ((ReturnNode)ret).walkUnreach(visit,unreach); - if( unreach.isEmpty() ) return; - - // Forwards walk from unreachable, looking for loops with no exit test. - visit.clear(); - for( CFGNode cfg : unreach ) - walkInfinite(cfg,visit,stop); - // Set loop depth on remaining graph - unreach.clear(); - visit.clear(); - for( Node ret : stop._inputs ) - ((ReturnNode)ret).walkUnreach(visit,unreach); - assert unreach.isEmpty(); - } - - - // Forwards walk over previously unreachable, looking for loops with no - // exit test. - static private void walkInfinite( CFGNode n, BitSet visit, StopNode stop ) { - if( visit.get(n._nid) ) return; // Been there, done that - visit.set(n._nid); - if( n instanceof LoopNode loop ) - loop.forceExit(stop); - for( Node use : n._outputs ) - if( use instanceof CFGNode cfg ) - walkInfinite(cfg,visit,stop); - } - - // ------------------------------------------------------------------------ - private static void schedEarly() { - ArrayList<CFGNode> rpo = new ArrayList<>(); - BitSet visit = new BitSet(); - _rpo_cfg(Parser.START, visit, rpo); - // Reverse Post-Order on CFG - for( int j=rpo.size()-1; j>=0; j-- ) { - CFGNode cfg = rpo.get(j); - cfg.loopDepth(); - for( Node n : cfg._inputs ) - _schedEarly(n,visit); - // In dead infinite loops, entire code blocks may be unreachable - // from below. Reach down from the CFG to their Phis so their - // inputs are scheduled too. - if( cfg instanceof RegionNode ) { - int len = cfg.nOuts(); - for( int i=0; i<len; i++ ) - if( cfg.out(i) instanceof PhiNode phi ) - _schedEarly(phi,visit); - } - } - } - - // Post-Order of CFG - private static void _rpo_cfg(Node n, BitSet visit, ArrayList<CFGNode> rpo) { - if( !(n instanceof CFGNode cfg) || visit.get(cfg._nid) ) - return; // Been there, done that - visit.set(cfg._nid); - for( Node use : cfg._outputs ) - _rpo_cfg(use,visit,rpo); - rpo.add(cfg); - } - - private static void _schedEarly(Node n, BitSet visit) { - if( n==null || visit.get(n._nid) ) return; // Been there, done that - visit.set(n._nid); - // Schedule inputs first, except Phis: following their backedges would - // enter a data cycle before its control has been scheduled. - for( Node def : n._inputs ) - if( def!=null && !(def instanceof PhiNode) ) - _schedEarly(def,visit); - // An existing edge 0 already supplies control (or a Phi/Proj binding). - if( n.in(0)==null ) { - // Schedule at deepest input - CFGNode early = Parser.START; // Maximally early, lowest idepth - for( int i=1; i<n.nIns(); i++ ) - if( n.in(i)!=null && n.in(i).cfg0().idepth() > early.idepth() ) - early = n.in(i).cfg0(); // Latest/deepest input - n.setDef(0,early); // First place this can go - } - } - - // ------------------------------------------------------------------------ - private static void schedLate( StopNode stop) { - CFGNode[] late = new CFGNode[Node.UID()]; - Node[] ns = new Node[Node.UID()]; - // Record Load NIDs at all their CFG block choices, then check against - // Store block choices to force a Load above an anti-dependent Store. - int[] anti = new int[Node.UID()]; - // Breadth-first scheduling - breadth(stop,ns,late,anti); - - // Copy the best placement choice into the control slot - for( int i=0; i<late.length; i++ ) - if( ns[i] != null && !(ns[i] instanceof ProjNode) ) - ns[i].setDef(0,late[i]); - } - - private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) { - // Things on the worklist have some (but perhaps not all) uses done. - WorkList<Node> work = new WorkList<>(); - work.push(stop); - Node n; - outer: - while( (n = work.pop()) != null ) { - assert late[n._nid]==null; // No double visit - // These I know the late schedule of, and need to set early for loops - if( n instanceof CFGNode cfg ) late[n._nid] = cfg.blockHead() ? cfg : cfg.cfg(0); - else if( n instanceof PhiNode phi ) late[n._nid] = phi.region(); - // These nodes have a fixed late placement at their original control. - else if( n instanceof ProjNode || n instanceof NewNode || n==Parser.ZERO ) late[n._nid] = n.cfg0(); - else { - - // All uses done? - for( Node use : n._outputs ) - if( use!=null && late[use._nid]==null ) - continue outer; // Nope, await all uses done - - // Loads need their memory inputs' uses also done - if( n instanceof LoadNode ld ) - for( Node memuse : ld.mem()._outputs ) - if( antiUse(ld,memuse) && late[memuse._nid]==null ) - continue outer; - - // All uses done, schedule - _doSchedLate(n,ns,late,anti); - } - - // A use just finished; reconsider its inputs and waiting loads, - // even when the shared memory input was already scheduled. - for( Node def : n._inputs ) { - if( def==null ) continue; - if( late[def._nid]==null ) work.push(def); - for( Node out : def._outputs ) - if( out instanceof LoadNode ld && late[ld._nid]==null ) - work.push(ld); - } - if( n instanceof LoopNode loop ) - for( Node phi : loop._outputs ) - if( phi instanceof PhiNode && late[phi._nid]==null ) - work.push(phi); - } - } - - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { - // Walk uses, gathering the LCA (Least Common Ancestor) of uses - CFGNode early = n.in(0) instanceof CFGNode cfg ? cfg : n.in(0).cfg0(); - assert early != null; - CFGNode lca = null; - for( Node use : n._outputs ) - if( use != null ) - lca = use_block(n,use, late).domLCA(lca,null); - - // Loads may need anti-dependencies, raising their LCA - if( n instanceof LoadNode load ) - lca = find_anti_dep(lca,load,early,late,anti); - - // Walk up from the LCA to the early, looking for best place. This is - // the lowest execution frequency, approximated by least loop depth and - // deepest control flow. - CFGNode best = lca; - lca = lca.idom(); // Already found best for starting LCA - for( ; lca != early.idom(); lca = lca.idom() ) - if( better(lca,best) ) - best = lca; - assert !(best instanceof IfNode); - ns [n._nid] = n; - late[n._nid] = best; - } - - // Block of use. Normally from late[] schedule, except for Phis, which go - // to the matching Region input. - private static CFGNode use_block(Node n, Node use, CFGNode[] late) { - if( !(use instanceof PhiNode phi) ) - return late[use._nid]; - CFGNode found=null; - for( int i=1; i<phi.nIns(); i++ ) - if( phi.in(i)==n ) - found = phi.region().cfg(i).domLCA(found,null); // Can be more than one matching input. - assert found!=null; - return found; - } - - - // Least loop depth first, then largest idepth - private static boolean better( CFGNode lca, CFGNode best ) { - return lca.loopDepth() < best.loopDepth() || - lca instanceof NeverNode || - lca.idepth() > best.idepth() || - best instanceof IfNode; - } - - // Only a store or memory Phi covering this alias can constrain a load. - // MemMerge packages slices without overwriting them. - private static boolean antiUse(LoadNode load, Node use) { - return switch( use ) { - case StoreNode st -> st._alias==load._alias; - case MemPhiNode phi -> phi._alias==load._alias; - case BulkMemPhiNode phi -> !phi.isSplit(load._alias); - default -> false; - }; - } - - private static CFGNode find_anti_dep(CFGNode lca, LoadNode load, CFGNode early, CFGNode[] late, int[] anti) { - // We could skip final-field loads here. - // Walk LCA->early, flagging Load's block location choices - for( CFGNode cfg=lca; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) - anti[cfg._nid] = load._nid; - // Walk load->mem uses, looking for Stores causing an anti-dep - for( Node mem : load.mem()._outputs ) { - if( !antiUse(load,mem) ) continue; - switch( mem ) { - case StoreNode st: - lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti); - break; - case PhiNode phi: - // Repeat anti-dep for matching Phi inputs. - // No anti-dep edges but may raise the LCA. - for( int i=1; i<phi.nIns(); i++ ) - if( phi.in(i)==load.mem() ) - lca = anti_dep(load,phi.region().cfg(i),load.mem().cfg0(),lca,null,anti); - break; - default: throw Utils.TODO(); - } - } - return lca; - } - - // - private static CFGNode anti_dep( LoadNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st, int[] anti ) { - // Preserve the full store range for the earlier evaluator scheduler. - // It places nodes independently of GCM and may hoist this store. - for( ; stblk != defblk.idom(); stblk = stblk.idom() ) { - // Store and Load overlap, need anti-dependence - if( anti[stblk._nid]==load._nid ) { - lca = stblk.domLCA(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 - } - } - return lca; - } - -} diff --git a/chapter12/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter12/src/main/java/com/seaofnodes/simple/IRPrinter.java index 7e93e9da..d5ab15fe 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -8,6 +8,7 @@ public final class IRPrinter extends IRAdapter<Node> { private static final com.seaofnodes.print.IRPrinter<Node> PRINT = new com.seaofnodes.print.IRPrinter<>(new IRPrinter()); @Override public String type(Node n) { return n._type==null ? "" : n._type.str(); } + @Override public int inputColumns() { return 3; } @Override public String inputMark(Node n, Node def) { return n instanceof MemMergeNode && def instanceof MemMergeNode ? "^" : " "; } @Override public Kind kind(Node n) { if( n instanceof StartNode ) return Kind.START; @@ -17,15 +18,13 @@ public final class IRPrinter extends IRAdapter<Node> { if( n instanceof PhiNode ) return Kind.PHI; if( n instanceof ReturnNode ) return Kind.RETURN; if( n instanceof ConstantNode ) return Kind.CONSTANT; - if( n instanceof CProjNode ) return Kind.CPROJ; - if( n instanceof ProjNode ) return n instanceof CFGNode ? Kind.CPROJ : Kind.PROJ; - if( n instanceof CFGNode ) return Kind.CTRL; + if( n instanceof ProjNode ) return n.isCFG() ? Kind.CPROJ : Kind.PROJ; + if( n.isCFG() ) return Kind.CTRL; if( n instanceof MultiNode ) return Kind.MULTI; return Kind.DATA; } @Override public int index(Node n) { if( n instanceof ProjNode p ) return p._idx; - if( n instanceof CProjNode p ) return p._idx; return n._nid; } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter12/src/main/java/com/seaofnodes/simple/IterPeeps.java index 65a5e64f..7075d526 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -98,10 +98,6 @@ public abstract class IterPeeps { if( obs != null ) obs.after(n, x, true); } - // Break infinite loops, forcing a Never-branch to exit - GlobalCodeMotion.fixLoops(stop); - - GlobalCodeMotion.buildCFG(stop); return stop; } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/Parser.java b/chapter12/src/main/java/com/seaofnodes/simple/Parser.java index 9c213165..0fa7ee0a 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/Parser.java @@ -31,18 +31,12 @@ public class Parser { */ public static StartNode START; - public static ConstantNode ZERO; - public static XCtrlNode XCTRL; - public StopNode STOP; // Field identities are independent of the memory graph and Start's tuple. private final HashMap<String,Integer> _aliases = new HashMap<>(); private int _alias = 2; - // Debugger Printing. - public static boolean SCHEDULED; // True if debug printer can use schedule info - // The Lexer. Thin wrapper over a byte[] buffer with a cursor. private final Lexer _lexer; @@ -68,7 +62,6 @@ public class Parser { add("continue"); add("else"); add("false"); - add("flt"); add("if"); add("int"); add("new"); @@ -89,7 +82,7 @@ public class Parser { ScopeNode _continueScope; ScopeNode _breakScope; - // Mapping from a type name to a Type. + // Authoritative declarations, indexed by type name. public static HashMap<String, Type> TYPES = new HashMap<>(); public Parser(String source, TypeInteger arg) { @@ -98,15 +91,11 @@ public class Parser { IterPeeps.reset(); TYPES.clear(); TYPES.put("int",TypeInteger.BOT); - TYPES.put("flt",TypeFloat .BOT); - SCHEDULED = false; _lexer = new Lexer(source); _scope = new ScopeNode(); _continueScope = _breakScope = null; START = new StartNode(new Type[]{ Type.CONTROL, TypeMem.BOT, arg }); STOP = new StopNode(source); - ZERO = new ConstantNode(TypeInteger.constant(0)).peephole().keep(); - XCTRL= new XCtrlNode().peephole().keep(); } public Parser(String source) { @@ -129,8 +118,8 @@ public class Parser { _xScopes.push(_scope); // Enter a new scope for the initial control and arguments _scope.push(); - _scope.define(ScopeNode.CTRL, Type.CONTROL , new CProjNode(START, 0, ScopeNode.CTRL).peephole()); - _scope.define(ScopeNode.ARG0, TypeInteger.BOT, new ProjNode(START, 2, ScopeNode.ARG0).peephole()); + _scope.define(ScopeNode.CTRL, Type.CONTROL , new ProjNode(START, 0, ScopeNode.CTRL).peephole()); + _scope.define(ScopeNode.ARG0, TypeInteger.BOT, new ProjNode(START, 2, ScopeNode.ARG0).peephole()); _scope.define("$mem", TypeMem.BOT, new ProjNode(START, 1, "$mem").peephole()); parseBlock(); if( ctrl()._type==Type.CONTROL ) @@ -190,7 +179,7 @@ public class Parser { * type IDENTIFIER ; * </pre> */ - private Field parseField(String sname) { + private Field parseField() { Type t = type(); if( t==null ) throw errorSyntax("Requires a field type, found '"+_lexer.getAnyNextToken()+"'"); @@ -198,20 +187,21 @@ public class Parser { } /** - * Parse a struct declaration, and return the following statement. + * Parse a complete struct declaration. * Only allowed in top level scope. * Structs cannot be redefined. * - * @return The statement following the struct + * @return null */ private Node parseStruct() { if (_xScopes.size() > 1) throw errorSyntax("struct declarations can only appear in top level scope"); String typeName = requireId(); - if ( TYPES.containsKey(typeName)) throw errorSyntax("struct '" + typeName + "' cannot be redefined"); + Type t = TYPES.get(typeName); + if( t!=null && !(t instanceof TypeStruct ts && ts._fields==null) ) throw errorSyntax("struct '" + typeName + "' cannot be redefined"); ArrayList<Field> fields = new ArrayList<>(); require("{"); while (!peek('}') && !_lexer.isEOF()) { - Field field = parseField(typeName); + Field field = parseField(); if (fields.contains(field)) throw errorSyntax("Field '" + field + "' already defined in struct '" + typeName + "'"); fields.add(field); } @@ -221,7 +211,7 @@ public class Parser { TYPES.put(typeName, ts); // Insert the struct name in the collection of all struct names _aliases.put(typeName,_alias); _alias += ts._fields.length; - return parseStatement(); + return null; } /** @@ -262,8 +252,8 @@ public class Parser { // IfNode takes current control and predicate Node ifNode = new IfNode(ctrl(), pred).peephole(); // Setup projection nodes - Node ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); - Node ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole(); + Node ifT = new ProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); + Node ifF = new ProjNode(ifNode.unkeep(), 1, "False").peephole(); // Clone the body Scope to create the break/exit Scope which accounts for any // side effects in the predicate. The break/exit Scope will be the final @@ -309,7 +299,7 @@ public class Parser { private ScopeNode jumpTo(ScopeNode toScope) { ScopeNode cur = _scope.dup(); - ctrl(XCTRL); // Kill current scope + ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill current scope // Prune nested lexical scopes that have depth > than the loop head // We use _breakScope as a proxy for the loop head scope to obtain the depth while( cur._scopes.size() > _breakScope._scopes.size() ) @@ -345,8 +335,8 @@ public class Parser { // IfNode takes current control and predicate Node ifNode = new IfNode(ctrl(), pred).peephole(); // Setup projection nodes - Node ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); - Node ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole().keep(); + Node ifT = new ProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); + Node ifF = new ProjNode(ifNode.unkeep(), 1, "False").peephole().keep(); // In if true branch, the ifT proj node becomes the ctrl // But first clone the scope and set it as current int ndefs = _scope.nIns(); @@ -363,8 +353,8 @@ public class Parser { // Parse the false side _scope = fScope; // Restore scope, then parse else block if any ifF.unkeep(); // fScope already owns the false control + _scope.upcast(ifF,pred,true); // Up-cast predicate, also without an else if (matchx("else")) { - _scope.upcast(ifF,pred,true); // Up-cast predicate parseStatement(); fScope = _scope; } @@ -393,7 +383,7 @@ public class Parser { private Node parseReturn() { var expr = require(parseExpression(), ";"); Node ret = STOP.addReturn(new ReturnNode(ctrl(), expr, _scope).peephole()); - ctrl(XCTRL); // Kill control + ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill control return ret; } @@ -436,12 +426,13 @@ public class Parser { throw error("Undefined name '" + name + "'"); t = _scope.lookupDeclaredType(name); } - // Auto-widen int to float - if( expr._type instanceof TypeInteger && t instanceof TypeFloat ) - expr = new ToFloatNode(expr).peephole(); + // Auto-deepen forward ref types + Type e = expr._type; + if( e instanceof TypeMemPtr tmp && tmp._obj._fields==null ) + e = tmp.make_from((TypeStruct)TYPES.get(tmp._obj._name)); // Type is sane - if( !expr._type.isa(t) ) - throw error("Type " + expr._type.str() + " is not of declared type " + t.str()); + if( !e.isa(t) ) + throw error("Type " + e.str() + " is not of declared type " + t.str()); return _scope.update(name,expr); } @@ -450,16 +441,22 @@ public class Parser { int old = _lexer._position; String tname = _lexer.matchId(); if( tname==null ) return null; + boolean nullable = match("?"); Type t = TYPES.get(tname); + // Assume a forward-reference type if( t == null ) { - // Not a type; unwind the parse - _lexer._position = old; - return null; + int old2 = _lexer._position; + String id = _lexer.matchId(); + if( id==null ) { + _lexer._position = old; + return null; + } + TYPES.put(tname,t = TypeStruct.make(tname)); + _lexer._position = old2; // Reparse ID in caller } - return t instanceof TypeStruct obj ? TypeMemPtr.make(obj,match("?")) : t; + return t instanceof TypeStruct obj ? TypeMemPtr.make(obj,nullable) : t; } - /** * Parse an expression of the form: * @@ -493,7 +490,7 @@ public class Parser { else break; // Peepholes can fire, but lhs is already "hooked", kept alive lhs.setDef(idx,parseAddition()); - lhs = lhs.widen().peephole(); + lhs = lhs.peephole(); if( negate ) // Extra negate for != lhs = new NotNode(lhs).peephole(); } @@ -516,7 +513,7 @@ public class Parser { else if( match("-") ) lhs = new SubNode(lhs,null); else break; lhs.setDef(2,parseMultiplication()); - lhs = lhs.widen().peephole(); + lhs = lhs.peephole(); } return lhs; } @@ -530,14 +527,14 @@ public class Parser { * @return a multiply expression {@link Node}, never {@code null} */ private Node parseMultiplication() { - var lhs = parseUnary(); boolean mul; + var lhs = parseUnary(); 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.widen().peephole(); + lhs = lhs.peephole(); } return lhs; } @@ -551,7 +548,7 @@ public class Parser { * @return a unary expression {@link Node}, never {@code null} */ private Node parseUnary() { - if (match("-")) return new MinusNode(parseUnary()).widen().peephole(); + if (match("-")) return new MinusNode(parseUnary()).peephole(); if (match("!")) return new NotNode(parseUnary()).peephole(); return parsePostfix(parsePrimary()); } @@ -565,15 +562,16 @@ public class Parser { * @return a primary {@link Node}, never {@code null} */ private Node parsePrimary() { - if( _lexer.isNumber(_lexer.peek()) ) return parseLiteral(); + if( _lexer.isNumber(_lexer.peek()) ) return parseIntegerLiteral(); if( match("(") ) return require(parseExpression(), ")"); if( matchx("true" ) ) return new ConstantNode(TypeInteger.constant(1)).peephole(); - if( matchx("false") ) return ZERO; + if( matchx("false") ) return new ConstantNode(TypeInteger.ZERO).peephole(); if( matchx("null" ) ) return new ConstantNode(TypeMemPtr.NULLPTR).peephole(); if( matchx("new") ) { String structName = requireId(); Type t = TYPES.get(structName); - if( t == null || !(t instanceof TypeStruct obj) ) throw errorSyntax("Unknown struct type '" + structName + "'"); + if( !(t instanceof TypeStruct obj) || obj._fields==null ) + throw error("Unknown struct type '" + structName + "'"); return newStruct(obj); } String name = _lexer.matchId(); @@ -590,7 +588,7 @@ public class Parser { Node n = new NewNode(TypeMemPtr.make(obj), ctrl()).peephole().keep(); int alias = _aliases.get(obj._name); for( Field field : obj._fields ) { - store(field._fname,alias,n,ZERO); + store(field._fname,alias,field._type,n,new ConstantNode(field._type.makeInit()).peephole(),true); alias++; } return n.unkeep(); @@ -600,9 +598,9 @@ public class Parser { private Node mem() { return _scope.lookup("$mem"); } private Node mem(Node n) { return _scope.update("$mem",n); } - private void store(String name, int alias, Node ptr, Node val) { + private void store(String name, int alias, Type glb, Node ptr, Node val, boolean init) { Node prior = mem().keep(); - Node st = new StoreNode(name,alias,ctrl(),prior,ptr,val).peephole(); + Node st = new StoreNode(name,alias,glb,null,prior,ptr,val,init).peephole(); mem(new MemMergeNode(prior,alias,st).peephole()); prior.unkeep(); } @@ -623,7 +621,9 @@ public class Parser { 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( ptr._obj == null ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); + TypeStruct base = (TypeStruct)TYPES.get(ptr._obj._name); + int idx = base==null ? -1 : base.find(name); if( idx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); int alias = _aliases.get(ptr._obj._name)+idx; @@ -632,13 +632,14 @@ public class Parser { if( peek('=') ) _lexer._position--; else { Node val = parseExpression(); - store(name,alias,expr,val); + Type glb = base._fields[idx]._type; + store(name,alias,glb,expr,val,false); return expr; // "obj.a = expr" returns the expression while updating memory } } - Type declaredType = ptr._obj._fields[idx]._type; - return parsePostfix(new LoadNode(name, alias, declaredType, mem(), expr).peephole()); + Type declaredType = base._fields[idx]._type; + return parsePostfix(new LoadNode(name, alias, declaredType.glb(), mem(), expr).peephole()); } /** @@ -646,10 +647,9 @@ public class Parser { * * <pre> * integerLiteral: [1-9][0-9]* | [0] - * floatLiteral: [1-9][0-9]* | [0] * </pre> */ - private ConstantNode parseLiteral() { + private ConstantNode parseIntegerLiteral() { return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole(); } @@ -744,16 +744,7 @@ public class Parser { * Return the next non-white-space character */ private void skipWhiteSpace() { - while( true ) { - if( isWhiteSpace() ) _position++; - // Skip // to end of line - else if( _position+2 < _input.length && - _input[_position ] == '/' && - _input[_position+1] == '/') { - _position += 2; - while( !isEOF() && _input[_position] != '\n' ) _position++; - } else break; - } + while (isWhiteSpace()) _position++; } @@ -804,37 +795,19 @@ 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() { - 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))); + 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)); } private String parseNumberString() { - 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); + int start = _position; + while (isNumber(nextChar())) ; + return new String(_input, start, --_position - start); } // First letter of an identifier @@ -853,9 +826,8 @@ public class Parser { return new String(_input, start, --_position - start); } - // private boolean isPunctuation(char ch) { - return "=;[]<>()+-/*".indexOf(ch) != -1; + return "=;[]<>(){}+-/*!".indexOf(ch) != -1; } private String parsePunctuation() { diff --git a/chapter12/src/main/java/com/seaofnodes/simple/Utils.java b/chapter12/src/main/java/com/seaofnodes/simple/Utils.java index f3ac25b1..4f2af769 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/Utils.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/Utils.java @@ -55,4 +55,11 @@ public class Utils { // Fold a 64bit hash into 32 bits public static int fold( long x ) { return (int)((x>>32) ^ x); } + + public static boolean eq(String s0, String s1) { + if( s0==s1 ) return true; + assert s0==s0.intern(); + assert s1==s1.intern(); + return false; + } } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/AddFNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/AddFNode.java deleted file mode 100644 index fd713156..00000000 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/AddFNode.java +++ /dev/null @@ -1,37 +0,0 @@ -package com.seaofnodes.simple.node; - - -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeFloat; - - -public class AddFNode extends Node { - public AddFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } - - @Override public String label() { return "AddF"; } - - @Override protected String format() { return "(%1+%2)"; } - - @Override - public Type compute() { - if (in(1)._type instanceof TypeFloat i0 && - in(2)._type instanceof TypeFloat i1) { - if (i0.isConstant() && i1.isConstant()) - return TypeFloat.constant(i0.value()+i1.value()); - } - return in(1)._type.meet(in(2)._type); - } - - @Override - public Node idealize() { - Node lhs = in(1); - Type t2 = in(2)._type; - - // Add of 0. - if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==0 ) - return lhs; - - return null; - } - @Override Node copy(Node lhs, Node rhs) { return new AddFNode(lhs,rhs); } -} diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/AddNode.java index 01aa209f..e993a20e 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -103,7 +103,6 @@ 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 ) { @@ -169,5 +168,9 @@ public class AddNode extends Node { } @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); } - @Override Node copyF() { return new AddFNode(null,null); } + @Override public String err() { + if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type; + if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type; + return null; + } } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/BoolNode.java index e515a5f1..63452dba 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -2,11 +2,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; -import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; -import com.seaofnodes.simple.type.TypeFloat; import com.seaofnodes.simple.type.TypeMemPtr; @@ -27,21 +24,19 @@ abstract public class BoolNode extends Node { @Override public Type compute() { - if( in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1 ) { - if (i0.isConstant() && i1.isConstant()) - return TypeInteger.constant(doOp(i0.value(), i1.value()) ? 1 : 0); - } - if( in(1)._type instanceof TypeFloat i0 && - in(2)._type instanceof TypeFloat i1 ) { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1==Type.TOP || t1==TypeInteger.TOP || + t2==Type.TOP || t2==TypeInteger.TOP ) + return TypeInteger.TOP; + if( t1 instanceof TypeInteger i0 && + t2 instanceof TypeInteger i1 ) { if (i0.isConstant() && i1.isConstant()) return TypeInteger.constant(doOp(i0.value(), i1.value()) ? 1 : 0); } return TypeInteger.BOT; } - boolean doOp(long lhs, long rhs) { throw Utils.TODO(); } - boolean doOp(double lhs, double rhs) { throw Utils.TODO(); } + abstract boolean doOp(long lhs, long rhs); @Override public Node idealize() { @@ -53,9 +48,11 @@ 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 || in(1)._nid > in(2)._nid ) + if( in(1) instanceof ConstantNode ) + return new EQ(in(2),in(1)); // Equals sorts by NID otherwise: non.high == non.low becomes non.low == non.high - return in(1)._type instanceof TypeFloat ? new EQF(in(2),in(1)) : new EQ(in(2),in(1)); + else if( in(1)._nid > in(2)._nid ) + return new EQ(in(2),in(1)); } // Equals X==0 becomes a !X if( (in(2)._type == TypeInteger.ZERO || in(2)._type == TypeMemPtr.NULLPTR) ) @@ -71,12 +68,7 @@ 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); } 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; } } - + 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); } } } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/CFGNode.java deleted file mode 100644 index c690a83c..00000000 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ /dev/null @@ -1,96 +0,0 @@ -package com.seaofnodes.simple.node; - -import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.type.*; -import com.seaofnodes.simple.Utils; - -import java.util.BitSet; -import java.util.HashSet; -import java.util.HashMap; - -/** Control Flow Graph Nodes - * <p> - * CFG nodes have a immediate dominator depth (idepth) and a loop nesting - * depth(loop_depth). - * <p> - * idepth is computed lazily upon first request, and is valid even in the - * Parser, and is used by peepholes during parsing and afterward. - * <p> - * loop_depth is computed after optimization as part of scheduling. - * - */ -public abstract class CFGNode extends Node { - - public CFGNode(Node... nodes) { super(nodes); } - - @Override public boolean isCFG() { return true; } - - public CFGNode cfg(int idx) { return (CFGNode)in(idx); } - - // Block head is Start, Region, CProj, but not e.g. If, Return, Stop - public boolean blockHead() { return false; } - - // Should be exactly 1 tail from a block head - public CFGNode blockTail() { - assert blockHead(); - for( Node n : _outputs ) - if( n instanceof CFGNode cfg ) - return cfg; - return null; - } - - // ------------------------------------------------------------------------ - /** - * Immediate dominator tree depth, used to approximate a real IDOM during - * parsing where we do not have the whole program, and also peepholes - * change the CFG incrementally. - * <p> - * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} - */ - public char _idepth; - public int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(idom().idepth()+1); } - // Zero depth means uncached. Check before narrowing so overflow cannot wrap. - final int cacheIDepth(int depth) { - assert 0 <= depth && depth <= Character.MAX_VALUE : "Dominator depth exceeds 65535"; - return _idepth = (char)depth; - } - - - // Return the immediate dominator of this Node and compute dom tree depth. - public CFGNode idom(Node dep) { return cfg(0); } - public final CFGNode idom() { return idom(null); } - - // Return the LCA of two idoms - public CFGNode domLCA(CFGNode rhs, Node dep) { - if( rhs==null ) return this; - CFGNode lhs = this; - while( lhs != rhs ) { - if( lhs==null || rhs==null ) return null; - int comp = lhs.idepth() - rhs.idepth(); - if( comp >= 0 ) lhs = (dep==null ? lhs : (CFGNode)lhs.addDep(dep)).idom(); - if( comp <= 0 ) rhs = (dep==null ? rhs : (CFGNode)rhs.addDep(dep)).idom(); - } - return lhs; - } - - // Loop nesting depth - public int _loopDepth; - public int loopDepth() { return _loopDepth==0 ? (_loopDepth = cfg(0).loopDepth()) : _loopDepth; } - - // ------------------------------------------------------------------------ - // Support routines for Global Code Motion - - // Tik-tok recursion pattern. This method is final, and every caller does - // this work. - public final void walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { - if( visit.get(_nid) ) return; - visit.set(_nid); - _walkUnreach(visit,unreach); - unreach.remove(this); // Since we reached here... Node was not unreachable - } - - // Tik-tok recursion pattern; not-final; callers override this. - void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { - cfg(0).walkUnreach(visit,unreach); - } -} diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/CProjNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/CProjNode.java deleted file mode 100644 index ff5d1a76..00000000 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/CProjNode.java +++ /dev/null @@ -1,62 +0,0 @@ -package com.seaofnodes.simple.node; - -import com.seaofnodes.print.ExprPrinter; - -import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeMem; -import com.seaofnodes.simple.type.TypeTuple; - -public class CProjNode extends CFGNode { - - // Which slice of the incoming multipart value - public final int _idx; - - // Debugging label - public final String _label; - - public CProjNode(Node ctrl, int idx, String label) { - super(ctrl); - _idx = idx; - _label = label; - } - - @Override public String label() { return _label; } - - @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p(_label); } - - @Override public boolean isMultiTail() { return in(0).isMultiHead(); } - @Override public boolean blockHead() { return true; } - - public CFGNode ctrl() { return cfg(0); } - - @Override - public Type compute() { - Type t = ctrl()._type; - return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; - } - - @Override - public Node idealize() { - if ( ctrl() instanceof IfNode iff ) { - if ( iff._type instanceof TypeTuple tt && tt._types[1 - _idx] == Type.XCONTROL ) - return iff.in(0); // We become our input control - - // Flip a negating if-test, to remove the not - if( iff.pred().addDep(this) instanceof NotNode not ) - return new CProjNode(new IfNode(iff.ctrl(),not.in(1)).peephole(),1-_idx,_idx==0 ? "False" : "True"); - } - return null; - } - - @Override - public Node getBlockStart() { - return ctrl() instanceof IfNode ? this : ctrl().getBlockStart(); - } - @Override - boolean eq( Node n ) { return _idx == ((CProjNode)n)._idx; } - - @Override - int hash() { return _idx; } - -} diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 9ecd1152..426736ed 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -38,7 +38,6 @@ public class ConstantNode extends Node { } @Override public boolean isMultiTail() { return true; } - // The special forever-zero is pinned, all others can sink @Override public Type compute() { return _con; } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/DivFNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/DivFNode.java deleted file mode 100644 index a3f4318d..00000000 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/DivFNode.java +++ /dev/null @@ -1,39 +0,0 @@ -package com.seaofnodes.simple.node; - - -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeFloat; - - -public class DivFNode extends Node { - public DivFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } - - @Override public String label() { return "DivF"; } - - @Override protected String format() { return "(%1/%2)"; } - - @Override - public Type compute() { - if (in(1)._type instanceof TypeFloat i0 && - in(2)._type instanceof TypeFloat i1) { - if (i0.isConstant() && i1.isConstant()) - return TypeFloat.constant(i0.value()/i1.value()); - } - return in(1)._type.meet(in(2)._type); - } - - @Override - public Node idealize() { - Node lhs = in(1); - Node rhs = in(2); - Type t1 = lhs._type; - Type t2 = rhs._type; - - // Div of 1. - if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==1 ) - return lhs; - - return null; - } - @Override Node copy(Node lhs, Node rhs) { return new DivFNode(lhs,rhs); } -} diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/DivNode.java index cd52d117..d7244ace 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -37,5 +37,4 @@ 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/chapter12/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/IfNode.java index 70340f7f..45f695a5 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -5,10 +5,8 @@ import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeTuple; -import java.util.BitSet; -import java.util.HashSet; -public class IfNode extends CFGNode implements MultiNode { +public class IfNode extends MultiNode { public IfNode(Node ctrl, Node pred) { super(ctrl, pred); @@ -20,6 +18,7 @@ public class IfNode extends CFGNode implements MultiNode { @Override protected String format() { return "if( %1 )"; } + @Override public boolean isCFG() { return true; } @Override public boolean isMultiHead() { return true; } public Node ctrl() { return in(0); } @@ -49,20 +48,11 @@ public class IfNode extends CFGNode implements MultiNode { // Hunt up the immediate dominator tree. If we find an identical if // test on either the true or false branch, that side wins. if( !pred()._type.isHighOrConst() ) - for( CFGNode dom = idom(), prior=this; dom!=null; prior = dom, dom = dom.idom() ) - if( dom.addDep(this) instanceof IfNode iff && iff.pred().addDep(this)==pred() && prior instanceof CProjNode prj ) { + for( Node dom = idom(), prior=this; dom!=null; prior = dom, dom = dom.idom() ) + if( dom.addDep(this) instanceof IfNode iff && iff.pred().addDep(this)==pred() && prior instanceof ProjNode prj ) { setDef(1,new ConstantNode(TypeInteger.make(true,prj._idx==0?1:0)).peephole()); return this; } return null; } - - @Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { - for( Node proj : _outputs ) - if( ((CProjNode)proj)._loopDepth == 0 ) - unreach.add((CProjNode)proj); - super._walkUnreach(visit,unreach); - } - - @Override public Node getBlockStart() { return ctrl().getBlockStart(); } } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 01a82a79..b2ee6939 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -14,7 +14,6 @@ import com.seaofnodes.simple.type.Field; */ public class LoadNode extends MemOpNode { - Type _declaredType; /** * Load a value from a ptr.field. * @@ -23,12 +22,11 @@ public class LoadNode extends MemOpNode { * @param memPtr The ptr to the struct from where we load a field */ public LoadNode(String name, int alias, Type glb, Node memSlice, Node memPtr) { - super(name, alias, null, memSlice, memPtr); - _declaredType = glb; + super(name, alias, glb, null, memSlice, memPtr); } @Override boolean canDrop(MemOpNode other, Node dep) { - return super.canDrop(other,dep) && _declaredType==((LoadNode)other)._declaredType && !clobbered(dep); + return super.canDrop(other,dep) && !clobbered(dep); } // Check only immediate memory users. Stores clobber memory; Phis and @@ -67,7 +65,7 @@ public class LoadNode extends MemOpNode { // Simple Load-after-Store on same address. if( mem() instanceof StoreNode st && ptr() == st.ptr() && _alias==st._alias ) { // Must check same object - assert _name.equals(st._name); // Equiv class aliasing is perfect + assert Utils.eq(_name,st._name); // Equiv class aliasing is perfect return st.val(); } @@ -83,13 +81,9 @@ 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)) ) { - 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); - } + 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/chapter12/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/LoopNode.java index a0e988dd..a0ba973e 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -1,17 +1,15 @@ 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 java.util.BitSet; -import java.util.HashSet; public class LoopNode extends RegionNode { + public LoopNode( Node entry ) { super(null,entry,null); } - public CFGNode entry() { return cfg(1); } - public CFGNode back () { return cfg(2); } + Node entry() { return in(1); } + Node back () { return in(2); } @Override public String label() { return "Loop"; } @@ -27,54 +25,7 @@ public class LoopNode extends RegionNode { return inProgress() ? null : super.idealize(); } - // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) - @Override public int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(entry().idepth()+1); } - // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) - @Override public CFGNode idom(Node dep) { return entry(); } - - @Override public int loopDepth() { - if( _loopDepth!=0 ) return _loopDepth; // Was already set - _loopDepth = entry()._loopDepth+1; // Entry depth plus one - // One-time tag loop exits - for( CFGNode idom = back(); idom!=this; idom = idom.idom() ) { - // Walk idom in loop, setting depth - idom._loopDepth = _loopDepth; - // Loop exit hits the CProj before the If, instead of jumping from - // Region directly to If. - if( idom instanceof CProjNode proj ) { - assert proj.in(0) instanceof IfNode; // Loop exit test - // Find the loop exit CProj, and set loop_depth - for( Node use : proj.in(0)._outputs ) - if( use instanceof CProjNode proj2 && proj2 != idom ) - proj2._loopDepth = _loopDepth-1; - } - } - return _loopDepth; - } - - // If this is an unreachable loop, it may not have an exit. If it does not - // (i.e., infinite loop), force an exit to make it reachable. - public void forceExit( StopNode stop ) { - // Walk the backedge, then immediate dominator tree util we hit this - // Loop again. If we ever hit a CProj from an If (as opposed to - // directly on the If) we found our exit. - CFGNode x = back(); - while( x != this ) { - 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 - NeverNode iff = new NeverNode(back()); - for( Node use : _outputs ) - if( use instanceof PhiNode phi ) - iff.addDef(use); - CProjNode t = new CProjNode(iff,0,"True" ); - CProjNode f = new CProjNode(iff,1,"False"); - setDef(2,f); - stop.addDef(new ReturnNode(t,Parser.ZERO,null)); - } + // Bypass Region idom, same as the default idom() using use entry in(1) instead of in(0) + @Override int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(entry().idepth()+1); } + @Override Node idom() { return entry(); } } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 5a57a8c8..7c6afb0c 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -11,11 +11,14 @@ public abstract class MemOpNode extends Node { public final String _name; public final int _alias; + public final Type _declaredType; - public MemOpNode(String name, int alias, Node... nodes) { + + public MemOpNode(String name, int alias, Type glb, Node... nodes ) { super(nodes); _name = name; _alias = alias; + _declaredType = glb; } public Node mem() { return in(1); } @@ -25,7 +28,7 @@ public abstract class MemOpNode extends Node { // The caller has already checked the opcode, input shape and control. boolean canDrop(MemOpNode other, Node dep) { ptr().addDep(dep); - return _alias==other._alias && err()==null; + return _alias==other._alias && _declaredType==other._declaredType && err()==null; } @Override diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/MinusFNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/MinusFNode.java deleted file mode 100644 index 1b45c7c5..00000000 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/MinusFNode.java +++ /dev/null @@ -1,30 +0,0 @@ -package com.seaofnodes.simple.node; - - -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeFloat; - - -public class MinusFNode extends Node { - public MinusFNode(Node in) { super(null, in); } - - @Override public String label() { return "MinusF"; } - - @Override protected String format() { return "(-%1)"; } - - @Override - public Type compute() { - if (in(1)._type instanceof TypeFloat i0) - return i0.isConstant() ? TypeFloat.constant(-i0.value()) : i0; - return TypeFloat.BOT; - } - - @Override - public Node idealize() { - // -(-x) is x - if( in(1) instanceof MinusFNode minus ) - return minus.in(1); - - return null; - } -} diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/MinusNode.java index ae450b22..5b65b3fb 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -27,5 +27,4 @@ public class MinusNode extends Node { return null; } - @Override Node copyF() { return new MinusFNode(null); } } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/MulFNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/MulFNode.java deleted file mode 100644 index 6a57f3c5..00000000 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/MulFNode.java +++ /dev/null @@ -1,44 +0,0 @@ -package com.seaofnodes.simple.node; - - -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeFloat; - - -public class MulFNode extends Node { - public MulFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } - - @Override public String label() { return "MulF"; } - - @Override protected String format() { return "(%1*%2)"; } - - @Override - public Type compute() { - if (in(1)._type instanceof TypeFloat i0 && - in(2)._type instanceof TypeFloat i1) { - if (i0.isConstant() && i1.isConstant()) - return TypeFloat.constant(i0.value()*i1.value()); - } - return in(1)._type.meet(in(2)._type); - } - - @Override - public Node idealize() { - Node lhs = in(1); - Node rhs = in(2); - Type t1 = lhs._type; - Type t2 = rhs._type; - - // Mul of 1. We do not check for (1*x) because this will already - // canonicalize to (x*1) - if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==1 ) - return lhs; - - // Move constants to RHS: con*arg becomes arg*con - if ( t1.isConstant() && !t2.isConstant() ) - return swap12(); - - return null; - } - @Override Node copy(Node lhs, Node rhs) { return new MulFNode(lhs,rhs); } -} diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/MulNode.java index 2c13fd0f..b0359a52 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -51,5 +51,9 @@ public class MulNode extends Node { return null; } @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); } - @Override Node copyF() { return new MulFNode(null,null); } + @Override public String err() { + if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type; + if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type; + return null; + } } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/MultiNode.java index ac9c0045..2743bd19 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/MultiNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/MultiNode.java @@ -1,19 +1,13 @@ package com.seaofnodes.simple.node; -public interface MultiNode extends OutNode { +public abstract class MultiNode extends Node { - // Find a projection by index - default ProjNode proj( int idx ) { - for( Node out : outs() ) - if( out instanceof ProjNode prj && prj._idx==idx ) - return prj; - return null; - } + public MultiNode(Node... inputs) { super(inputs); } // Find a projection by index - default CProjNode cproj( int idx ) { - for( Node out : outs() ) - if( out instanceof CProjNode prj && prj._idx==idx ) + ProjNode proj( int idx ) { + for( Node out : _outputs ) + if( out instanceof ProjNode prj && prj._idx==idx ) return prj; return null; } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/NeverNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/NeverNode.java deleted file mode 100644 index 7e42ccf9..00000000 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/NeverNode.java +++ /dev/null @@ -1,22 +0,0 @@ -package com.seaofnodes.simple.node; - -import com.seaofnodes.print.ExprPrinter; - -import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.type.TypeInteger; -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeTuple; - - -// "Never true" for infinite loop exits -public class NeverNode extends IfNode { - public NeverNode(Node ctrl) { super(ctrl,Parser.ZERO); } - - @Override public String label() { return "Never"; } - - @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p("Never"); } - - @Override public Type compute() { return TypeTuple.IF_BOTH; } - - @Override public Node idealize() { return null; } -} diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/NewNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/NewNode.java index 74ba5184..857920bc 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -22,7 +22,6 @@ public class NewNode extends Node { return p.p("new ").p(_ptr._obj.str()); } - @Override public Type compute() { return _ptr; } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter12/src/main/java/com/seaofnodes/simple/node/Node.java index e3503a7c..999e38fd 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/Node.java @@ -8,7 +8,6 @@ import com.seaofnodes.simple.IRPrinter; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeFloat; import java.util.*; import java.util.function.Function; @@ -18,7 +17,7 @@ import java.util.function.Function; * The Node class provides common functionality used by all subtypes. * Subtypes of Node specialize by overriding methods. */ -public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable { +public abstract class Node extends BaseNode<Node> implements Cloneable { /** * Inputs to the node. These are use-def references to Nodes. @@ -84,7 +83,6 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable */ public Node in(int i) { return _inputs.get(i); } public Node out(int i) { return _outputs.get(i); } - @Override public ArrayList<Node> outs() { return _outputs; } public int nIns() { return _inputs.size(); } @@ -92,7 +90,7 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable public boolean isUnused() { return nOuts() == 0; } - public CFGNode cfg0() { return (CFGNode)in(0); } + public boolean isMem() { return false; } /** * Change a <em>def</em> into a Node. Keeps the edges correct, by removing @@ -119,11 +117,11 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable // the new_def might get killed if the old node kills it recursively. if( new_def != null ) new_def.addUse(this); - // Set the new_def over the old (killed) edge - _inputs.set(idx,new_def); if( old_def != null && // If the old def exists, remove a def->use edge old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def + // Set the new_def over the old (killed) edge + _inputs.set(idx,new_def); moveDepsToWorklist(); // Return self for easy flow-coding return new_def; @@ -151,7 +149,7 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable * @param new_def the new definition, appended to the end of existing definitions * @return new_def for flow coding */ - public Node addDef(Node new_def) { + Node addDef(Node new_def) { unlock(); // Add use->def edge _inputs.add(new_def); @@ -271,8 +269,8 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable Type old = setType(compute()); // Replace constant computations from non-constants with a constant node - if( !(this instanceof ConstantNode) && !(this instanceof XCtrlNode) && _type.isHighOrConst() ) - return (_type==Type.XCONTROL ? new XCtrlNode() : new ConstantNode(_type)).peepholeOpt(); + if( !(this instanceof ConstantNode) && _type.isHighOrConst() ) + return new ConstantNode(_type).peepholeOpt(); // Global Value Numbering if( _hash==0 ) { @@ -487,37 +485,6 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable int hash() { return 0; } // ------------------------------------------------------------------------ - // - - /** Is this Node control-flow-graph related */ - - /** Is this Node Memory related */ - public boolean isMem() { return false; } - - /** Return block start from a isCFG() */ - public Node getBlockStart() { return null; } - - // Semantic change to the graph (so NOT a peephole), used by the Parser. - // If any input is a float, flip to a float-flavored opcode and widen any - // non-float input. - public final Node widen() { - if( !hasFloatInput() ) return this; - Node flt = copyF(); - if( flt==null ) return this; - for( int i=1; i<nIns(); i++ ) - flt.setDef(i, in(i)._type instanceof TypeFloat ? in(i) : new ToFloatNode(in(i)).peephole()); - kill(); - return flt; - } - private boolean hasFloatInput() { - for( int i=1; i<nIns(); i++ ) - if( in(i)._type instanceof TypeFloat ) - return true; - return false; - } - Node copyF() { return null; } - - // ------------------------------------------------------------------------ // Peephole utilities // Swap inputs without letting either input go dead during the swap. @@ -545,6 +512,38 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable return true; } + /** + * Immediate dominator tree depth, used to approximate a real IDOM depth + * during parsing where we do not have the whole program, and also + * peepholes change the CFG incrementally. + * <p> + * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} + */ + public char _idepth; // IDOM depth approx; Zero is unset; non-zero is cached legit + + // Find the lowest common ancestor in the current dominator tree. + Node domLCA(Node rhs) { + if( rhs==null ) return this; + Node lhs = this; + while( lhs != rhs ) { + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); + if( comp >= 0 ) lhs = lhs.idom(); + if( comp <= 0 ) rhs = rhs.idom(); + } + return lhs; + } + + int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(idom().idepth()+1); } + // Zero depth means uncached. Check before narrowing so overflow cannot wrap. + final int cacheIDepth(int depth) { + assert 0 <= depth && depth <= Character.MAX_VALUE : "Dominator depth exceeds 65535"; + return _idepth = (char)depth; + } + + // Return the immediate dominator of this Node. + Node idom() { return in(0); } + // Make a shallow copy (same class) of this Node, with given inputs and // empty outputs and a new Node ID. The original inputs are ignored. // Does not need to be implemented in isCFG() nodes. diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/NotNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/NotNode.java index 4539f982..5e556390 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -15,10 +15,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 TypeFloat i0: - if( i0==TypeFloat.TOP ) return TypeInteger.TOP; - return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : TypeInteger.BOT; + case TypeInteger 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/chapter12/src/main/java/com/seaofnodes/simple/node/OutNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/OutNode.java deleted file mode 100644 index 7e531145..00000000 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/OutNode.java +++ /dev/null @@ -1,7 +0,0 @@ -package com.seaofnodes.simple.node; - -import java.util.ArrayList; - -public interface OutNode { - ArrayList<Node> outs(); -} diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 8dfa04cf..6995cc2f 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -32,9 +32,10 @@ public class PhiNode extends Node { return p.unchar(',').close(); } - public CFGNode region() { return (CFGNode)in(0); } + Node region() { return in(0); } @Override public boolean isMultiTail() { return true; } - @Override public boolean isMem() { return _declaredType instanceof TypeMem; } + @Override + public boolean isMem() { return _declaredType instanceof TypeMem; } @Override public Type compute() { @@ -82,11 +83,11 @@ 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(this) instanceof IfNode iff && iff.pred().addDep(this)==val ) { + if( region().idom() 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.nIns() > 0 && idom.in(0) != iff ) idom = idom.idom(); - if( idom instanceof CProjNode proj && proj._idx==1 ) + Node idom = region().in(nullx); + while( idom.in(0) != iff ) idom = idom.idom(); + if( idom instanceof ProjNode proj && proj._idx==1 ) return val; } } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/ProjNode.java index e82c69b3..a2632110 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -15,7 +15,7 @@ public class ProjNode extends Node { // Debugging label public final String _label; - public ProjNode(Node ctrl, int idx, String label) { + public ProjNode(MultiNode ctrl, int idx, String label) { super(ctrl); _idx = idx; _label = label; @@ -27,16 +27,30 @@ public class ProjNode extends Node { @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p(_label); } + @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; } @Override public boolean isMultiTail() { return in(0).isMultiHead(); } @Override public boolean isMem() { return _type instanceof TypeMem; } + public MultiNode ctrl() { return (MultiNode)in(0); } + @Override public Type compute() { Type t = in(0)._type; return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; } - @Override public Node idealize() { return null; } + @Override + public Node idealize() { + if ( ctrl() instanceof IfNode iff ) { + if ( iff._type instanceof TypeTuple tt && tt._types[1 - _idx] == Type.XCONTROL ) + return iff.in(0); // We become our input control + + // Flip a negating if-test, to remove the not + if( iff.pred().addDep(this) instanceof NotNode not ) + return new ProjNode((MultiNode)new IfNode(iff.ctrl(),not.in(1)).peephole(),1-_idx,_idx==0 ? "False" : "True"); + } + return null; + } @Override boolean eq( Node n ) { return _idx == ((ProjNode)n)._idx; } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/RegionNode.java index cdfd10ad..8b52494a 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -3,15 +3,13 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.IterPeeps; -import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; + import java.util.ArrayList; import java.util.Arrays; -import java.util.BitSet; -import java.util.HashSet; -public class RegionNode extends CFGNode { +public class RegionNode extends Node { public RegionNode(Node... nodes) { super(nodes); } @@ -22,8 +20,8 @@ public class RegionNode extends CFGNode { return p.p(label()).p(_nid); } + @Override public boolean isCFG() { return true; } @Override public boolean isMultiHead() { return true; } - @Override public boolean blockHead() { return true; } @Override public Type compute() { @@ -59,7 +57,7 @@ public class RegionNode extends CFGNode { IterPeeps.addAll(phi._outputs); } } - return isDead() ? Parser.XCTRL : delDef(path); + return isDead() ? new ConstantNode(Type.XCONTROL) : delDef(path); } // If down to a single input, become that input if( nIns()==2 && !hasPhi() ) @@ -91,30 +89,23 @@ public class RegionNode extends CFGNode { } // Immediate dominator of Region is a little more complicated. - @Override public int idepth() { + @Override int idepth() { if( _idepth!=0 ) return _idepth; int depth=0; for( Node n : _inputs ) if( n!=null ) - depth = Math.max(depth,((CFGNode)n).idepth()+1); + depth = Math.max(depth,n.idepth()+1); return cacheIDepth(depth); } - @Override public CFGNode idom(Node dep) { - CFGNode lca = null; + @Override Node idom() { + Node lca = null; // Recompute from predecessors: CFG edits can change the dominator. for( int i=1; i<nIns(); i++ ) - lca = cfg(i).domLCA(lca,dep); + lca = in(i).domLCA(lca); return lca; } - @Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { - for( int i=1; i<nIns(); i++ ) - cfg(i).walkUnreach(visit,unreach); - } - - @Override public int loopDepth() { return _loopDepth==0 ? (_loopDepth = cfg(1).loopDepth()) : _loopDepth; } - // True if last input is null public final boolean inProgress() { return nIns()>1 && in(nIns()-1) == null; @@ -124,6 +115,4 @@ public class RegionNode extends CFGNode { @Override boolean eq( Node n ) { return !inProgress(); } - - @Override public Node getBlockStart() { return this; } } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 161cc7d6..ef4ddb3a 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -6,11 +6,10 @@ import com.seaofnodes.simple.type.*; /** Keeps all preceding memory effects and the return value alive: {ctrl, $mem, value}. */ -public class ReturnNode extends CFGNode { +public class ReturnNode extends Node { public ReturnNode(Node ctrl, Node data, ScopeNode scope) { - // A synthetic never-taken loop exit has no source scope. - super(ctrl, scope == null ? null : scope.lookup("$mem"), data); + super(ctrl, scope.lookup("$mem"), data); } public Node ctrl() { return in(0); } @@ -27,6 +26,8 @@ public class ReturnNode extends CFGNode { return p.p(";"); } + @Override public boolean isCFG() { return true; } + @Override public Type compute() { // Return exposes the complete memory state. @@ -39,6 +40,4 @@ public class ReturnNode extends CFGNode { return ctrl(); return null; } - - @Override public Node getBlockStart() { return ctrl().getBlockStart(); } } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/StartNode.java index a5d4923f..3404f111 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -3,13 +3,10 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.*; -import java.util.BitSet; -import java.util.HashSet; -/** Start supplies control, whole memory, and the argument, in that order. */ -public class StartNode extends CFGNode implements MultiNode { - - private final TypeTuple _args; +/** The entry tuple: control, initial whole-memory state, and argument. */ +public class StartNode extends MultiNode { + final TypeTuple _args; public StartNode(Type[] args) { super(); @@ -23,8 +20,8 @@ public class StartNode extends CFGNode implements MultiNode { return p.p(label()); } + @Override public boolean isCFG() { return true; } @Override public boolean isMultiHead() { return true; } - @Override public boolean blockHead() { return true; } @Override public TypeTuple compute() { return _args; } @@ -33,12 +30,6 @@ public class StartNode extends CFGNode implements MultiNode { public Node idealize() { return null; } // No immediate dominator, and idepth==0 - @Override public int idepth() { return 0; } - @Override public CFGNode idom(Node dep) { return null; } - - @Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { } - - @Override public int loopDepth() { return (_loopDepth=1); } - - @Override public Node getBlockStart() { return this; } + @Override int idepth() { return 0; } + @Override Node idom() { return null; } } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/StopNode.java index b5d2d716..4b4e9615 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -8,7 +8,7 @@ import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.IterPeeps; -public class StopNode extends CFGNode { +public class StopNode extends Node { public final String _src; @@ -31,7 +31,7 @@ public class StopNode extends CFGNode { return p.p("]"); } - @Override public boolean blockHead() { return true; } + @Override public boolean isCFG() { return true; } // If a single Return, return it. // Otherwise, null because ambiguous. @@ -54,17 +54,7 @@ public class StopNode extends CFGNode { return null; } - @Override public int idepth() { - if( _idepth!=0 ) return _idepth; - int d=0; - for( Node n : _inputs ) - if( n!=null ) - d = Math.max(d,((CFGNode)n).idepth()+1); - return cacheIDepth(d); - } - @Override public CFGNode idom(Node dep) { return null; } - - @Override public int loopDepth() { return (_loopDepth=1); } + @Override public Node idom() { return null; } public Node addReturn(Node node) { return addDef(node); @@ -82,6 +72,4 @@ public class StopNode extends CFGNode { if( obs != null ) obs.phase("TypeCheck"); return this; } - - @Override public Node getBlockStart() { return this; } } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/StoreNode.java index f61afe78..e9eaaf2e 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -13,20 +13,26 @@ import com.seaofnodes.simple.type.*; */ public class StoreNode extends MemOpNode { + private final boolean _init; // Initializing writes are allowed to write null + /** * @param name The struct field we are assigning to * @param memSlice The memory alias node - this is updated after a Store * @param memPtr The ptr to the struct where we will store a value * @param value Value to be stored */ - public StoreNode(String name, int alias, Node ctrl, Node memSlice, Node memPtr, Node value) { - super(name, alias, ctrl, memSlice, memPtr, value); + public StoreNode(String name, int alias, Type glb, Node ctrl, Node memSlice, Node memPtr, Node value, boolean init) { + super(name, alias, glb, ctrl, memSlice, memPtr, value); + _init = init; } - @Override - public String label() { return "Store"; } - @Override - public boolean isMem() { return true; } + @Override boolean canDrop(MemOpNode other, Node dep) { + return super.canDrop(other,dep) && _init==((StoreNode)other)._init; + } + + @Override public String label() { return "." +_name+"="; } + @Override public boolean isMem() { return true; } + public Node val() { return in(3); } @Override @@ -72,4 +78,11 @@ public class StoreNode extends MemOpNode { return false; } + @Override + String err() { + String err = super.err(); + if( err != null ) return err; + Type ptr = val()._type; + return _init || ptr.isa(_declaredType) ? null : "Cannot store "+ptr+" into field "+_declaredType+" "+_name; + } } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/SubFNode.java deleted file mode 100644 index 2d218a03..00000000 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/SubFNode.java +++ /dev/null @@ -1,37 +0,0 @@ -package com.seaofnodes.simple.node; - - -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeFloat; - - -public class SubFNode extends Node { - public SubFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } - - @Override public String label() { return "SubF"; } - - @Override protected String format() { return "(%1-%2)"; } - - @Override - public Type compute() { - if (in(1)._type instanceof TypeFloat i0 && - in(2)._type instanceof TypeFloat i1) { - if (i0.isConstant() && i1.isConstant()) - return TypeFloat.constant(i0.value()-i1.value()); - } - return in(1)._type.meet(in(2)._type); - } - - @Override - public Node idealize() { - Node lhs = in(1); - Type t2 = in(2)._type; - - // Sub of 0. - if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==0 ) - return lhs; - - return null; - } - @Override Node copy(Node lhs, Node rhs) { return new SubFNode(lhs,rhs); } -} diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/SubNode.java index f36f2af5..6fa87a07 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; @@ -28,7 +27,6 @@ public class SubNode extends Node { if (i0.isConstant() && i1.isConstant()) return TypeInteger.constant(i0.value()-i1.value()); } - return TypeInteger.BOT; } @@ -57,5 +55,4 @@ 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/chapter12/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java deleted file mode 100644 index 26cf50e1..00000000 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java +++ /dev/null @@ -1,25 +0,0 @@ -package com.seaofnodes.simple.node; - - -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeFloat; -import com.seaofnodes.simple.type.TypeInteger; - - -public class ToFloatNode extends Node { - public ToFloatNode(Node lhs) { super(null, lhs); } - - @Override public String label() { return "ToFloat"; } - - @Override protected String format() { return "(flt)%1"; } - - @Override - public Type compute() { - if (in(1)._type instanceof TypeInteger i0 && i0.isConstant() ) - return TypeFloat.constant(i0.value()); - return TypeFloat.BOT; - } - - @Override public Node idealize() { return null; } - @Override Node copy(Node lhs, Node rhs) { return new ToFloatNode(lhs); } -} diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java deleted file mode 100644 index 056dfba1..00000000 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java +++ /dev/null @@ -1,14 +0,0 @@ -package com.seaofnodes.simple.node; - -import com.seaofnodes.print.ExprPrinter; - -import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.type.Type; - -public class XCtrlNode extends CFGNode { - public XCtrlNode( ) { super(Parser.START); } - @Override public String label() { return "Xctrl"; } - @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p("Xctrl"); } - @Override public Type compute() { return Type.XCONTROL; } - @Override public Node idealize() { return null; } -} diff --git a/chapter12/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/chapter12/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index e65963db..92d970d8 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -6,13 +6,13 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.type.TypeMem; -/** Chapter 12's view of the IR; browser, transport and layout are shared. */ +/** Chapter 10's view of the IR; browser, transport and layout are shared. */ public class SimpleGraphAdapter extends GraphAdapter<Node> { @Override protected String[] edgeNames(Node n) { return n instanceof ScopeNode scope && n.nIns()!=0 ? scope.reverseNames() : null; } - @Override protected int projectionIndex(Node n) { return n instanceof ProjNode p ? p._idx : n instanceof CProjNode p ? p._idx : -1; } + @Override protected int projectionIndex(Node n) { return n instanceof ProjNode p ? p._idx : -1; } @Override protected Kind kind(Node n) { if( n instanceof StopNode ) return Kind.STOP; @@ -25,9 +25,9 @@ public class SimpleGraphAdapter extends GraphAdapter<Node> { } @Override protected Role role(Node n, int i) { - if( n instanceof ScopeNode || n instanceof ConstantNode || n instanceof XCtrlNode ) return Role.ASSOC; + if( n instanceof ScopeNode || n instanceof ConstantNode ) return Role.ASSOC; if( n instanceof PhiNode ) return i == 0 ? Role.ASSOC : isMem(n) ? Role.MEM : Role.DATA; - if( n instanceof ProjNode || n instanceof CProjNode ) return n.isCFG() ? Role.CTRL : isMem(n) ? Role.MEM : Role.DATA; + if( n instanceof ProjNode ) return n.isCFG() ? Role.CTRL : isMem(n) ? Role.MEM : Role.DATA; if( n instanceof RegionNode && i == 0 ) return Role.ASSOC; if( i == 0 || n instanceof RegionNode || n instanceof StopNode ) return Role.CTRL; if( i == 1 && (n instanceof MemOpNode || n instanceof ReturnNode) ) return Role.MEM; diff --git a/chapter12/src/main/java/com/seaofnodes/simple/type/Field.java b/chapter12/src/main/java/com/seaofnodes/simple/type/Field.java index b50a4fa6..b2c006dd 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/type/Field.java @@ -53,7 +53,7 @@ public class Field extends Type { @Override public StringBuilder print( StringBuilder sb ) { - return _type.print(sb.append(_fname).append(":")); + return _type.print(sb.append(_fname).append(" :")); } @Override public String str() { return _fname; } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter12/src/main/java/com/seaofnodes/simple/type/Type.java index 45d66be4..93e27c76 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/type/Type.java @@ -33,12 +33,11 @@ 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 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 + 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 public final byte _type; diff --git a/chapter12/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/chapter12/src/main/java/com/seaofnodes/simple/type/TypeFloat.java deleted file mode 100644 index 738aebc9..00000000 --- a/chapter12/src/main/java/com/seaofnodes/simple/type/TypeFloat.java +++ /dev/null @@ -1,101 +0,0 @@ -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/chapter12/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/chapter12/src/main/java/com/seaofnodes/simple/type/TypeMem.java index b6fc8824..38b3635a 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -15,7 +15,7 @@ public class TypeMem extends Type { // 0 means TOP, no slice. // -1 means BOT, all memory. // N means slice#N. - private final int _alias; + public final int _alias; private TypeMem(int alias) { super(TMEM); _alias = alias; } @@ -23,7 +23,6 @@ public class TypeMem extends Type { public static final TypeMem TOP = make( 0); public static final TypeMem BOT = make(-1); - public static void gather(ArrayList<Type> ts) { ts.add(make(1)); ts.add(BOT); } @Override @@ -40,7 +39,7 @@ public class TypeMem extends Type { } @Override - public Type glb() { return TypeMem.BOT; } + public Type glb() { return make(_alias); } @Override int hash() { return 9876543 + _alias; } @@ -62,5 +61,5 @@ public class TypeMem extends Type { }); } - @Override public String str() { return print(new StringBuilder()).toString(); } + @Override public String str() { return toString(); } } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/chapter12/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index 6c874a93..5caa816d 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -13,21 +13,27 @@ import java.util.ArrayList; */ public class TypeMemPtr extends Type { // A TypeMemPtr is pair (obj,nil) - // where obj is one of - // (null,TypeStruct). - // where nil is one of - // (true,false) meaning an explicit null is allowed or not + // where obj is a TypeStruct, possibly TypeStruct.BOT + // where nil is an explicit null is allowed or not - public final TypeStruct _obj; // null, a TypeStruct, or sentinel TypeStruct.MANY + // Examples: + // (Person,false) - a not-nil Person + // (Person,true ) - a Person or a nil + // (BOT ,false) - a not-nil void* (unspecified struct) + // (TOP ,true ) - a nil + + public final TypeStruct _obj; public final boolean _nil; private TypeMemPtr(TypeStruct obj, boolean nil) { super(TMEMPTR); + assert obj!=null; _obj = obj; _nil = nil; } public static TypeMemPtr make(TypeStruct obj, boolean nil) { return new TypeMemPtr(obj, nil).intern(); } - public static TypeMemPtr make(TypeStruct obj) { return TypeMemPtr.make(obj, false); } + public static TypeMemPtr make(TypeStruct obj) { return make(obj, false); } + public TypeMemPtr make_from(TypeStruct obj) { return make(obj, _nil); } public static final TypeMemPtr BOT = make(TypeStruct.BOT,true); public static final TypeMemPtr TOP = BOT.dual(); @@ -43,17 +49,14 @@ public class TypeMemPtr extends Type { } @Override - public TypeMemPtr dual() { return TypeMemPtr.make(_obj==null ? null : _obj.dual(), !_nil); } + public TypeMemPtr dual() { return TypeMemPtr.make(_obj.dual(), !_nil); } @Override - public Type glb() { - if( _obj==null ) return BOT; - return make(_obj.glb(),true); - } + public Type glb() { return make(_obj.glb(),true); } @Override public TypeMemPtr makeInit() { return NULLPTR; } @Override - int hash() { return (_obj==null ? 0xDEADBEEF : _obj.hashCode()) ^ (_nil ? 1024 : 0); } + int hash() { return _obj.hashCode() ^ (_nil ? 1024 : 0); } @Override boolean eq(Type t) { diff --git a/chapter12/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/chapter12/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 44741def..02de7cc8 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -8,9 +8,12 @@ import java.util.ArrayList; */ public class TypeStruct extends Type { - // For now in terms of the lattice - // a struct type just stays as is - + // Immutable shallow references, resolved by name in Parser.TYPES when needed. + // A name-only struct has _fields == null, even after its definition is known. + // For LLI { LLI? next; int i; }, L0 is name-only and L1.next points to L0; + // TYPES["LLI"] holds L1. We deliberately stop recursive type expansion here, + // keeping interning and lattice operations finite and acyclic. Never patch + // L0 into L1: field access looks up the complete declaration by name instead. public final String _name; public final Field[] _fields; @@ -20,13 +23,23 @@ public class TypeStruct extends Type { _fields = fields; } + // Forward-ref version + public static TypeStruct make(String name) { return new TypeStruct(name, null).intern(); } + // All fields directly listed public static TypeStruct make(String name, Field[] fields) { return new TypeStruct(name, fields).intern(); } + // Parser uses an ArrayList to gather the fields public static TypeStruct make(String name, ArrayList<Field> fields) { return make(name,fields.toArray(new Field[fields.size()])); } public static final TypeStruct TOP = make("$TOP",new Field [0]); public static final TypeStruct BOT = make("$BOT",new Field [0]); public static final TypeStruct TEST = make("test",new Field[]{Field.TEST}); - public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(BOT); } + + // A pair of self-cyclic types + private static final TypeStruct S1F = make("S1"); + private static final TypeStruct S2F = make("S2"); + public static final TypeStruct S1 = make("S1", new Field[]{ Field.make("a", TypeInteger.BOT), Field.make("s2",TypeMemPtr.make(S2F,false)) }); + private static final TypeStruct S2 = make("S2", new Field[]{ Field.make("b", TypeInteger.BOT), Field.make("s1",TypeMemPtr.make(S1F,false)) }); + public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(BOT); ts.add(S1); ts.add(S2); } public int find(String fname) { for( int i=0; i<_fields.length; i++ ) @@ -51,6 +64,8 @@ public class TypeStruct extends Type { // And the answer is: "don't ask". if( !_name.equals(that._name) ) return BOT; // It's a struct; that's about all we know + if( this._fields==null ) return this; + if( that._fields==null ) return that; // Now all fields should be the same, so just do field meets assert _fields.length == that._fields.length; Field[] flds = new Field[_fields.length]; @@ -63,6 +78,7 @@ public class TypeStruct extends Type { public TypeStruct dual() { if( this==TOP ) return BOT; if( this==BOT ) return TOP; + if( _fields == null ) return this; Field[] flds = new Field[_fields.length]; for( int i=0; i<_fields.length; i++ ) flds[i] = _fields[i].dual(); @@ -80,9 +96,10 @@ public class TypeStruct extends Type { return make(_name,flds); } private boolean _glb() { - for( Field f : _fields ) - if( f.glb() != f ) - return false; + if( _fields!=null ) + for( Field f : _fields ) + if( f.glb() != f ) + return false; return true; } @@ -91,6 +108,7 @@ public class TypeStruct extends Type { TypeStruct ts = (TypeStruct)t; // Invariant if( !_name.equals(ts._name) ) return false; + if( _fields == ts._fields ) return true; if( _fields.length!=ts._fields.length ) return false; for( int i = 0; i < _fields.length; i++ ) @@ -102,7 +120,9 @@ public class TypeStruct extends Type { @Override int hash() { long hash = _name.hashCode(); - for( Field f : _fields ) hash = Utils.rot(hash,13) ^ f.hashCode(); + if( _fields != null ) + for( Field f : _fields ) + hash = Utils.rot(hash,13) ^ f.hashCode(); return Utils.fold(hash); } @@ -110,11 +130,12 @@ public class TypeStruct extends Type { public StringBuilder print(StringBuilder sb) { if( this==BOT ) return sb.append("StructBot"); if( this==TOP ) return sb.append("StructTop"); - sb.append(_name).append(" {\n"); + sb.append(_name); + if( _fields == null ) return sb; // Forward reference struct, just print the name + sb.append(" {\n"); for( Field f : _fields ) { - sb.append(" ").append(f._fname).append(":"); - f._type.print(sb); - sb.append(";\n"); + sb.append(" ").append(f._fname).append(" :"); + f._type.print(sb).append(";\n"); } return sb.append("}"); } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter12/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index ec7390ca..0aa019a7 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -58,7 +58,8 @@ public class TypeTuple extends Type { for( Type t : _types ) t.typeName(sb).append(","); sb.setLength(sb.length()-1); - return sb.append("]"); + sb.append("]"); + return sb; } public static final TypeTuple IF_BOTH = make(new Type[]{Type. CONTROL,Type. CONTROL}); diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter01Test.java index c10dc510..89882b2f 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -15,7 +15,7 @@ public class Chapter01Test { StartNode start = Parser.START; ReturnNode ret = (ReturnNode)stop.in(0); - assertTrue(ret.ctrl() instanceof CProjNode); + assertTrue(ret.ctrl() instanceof ProjNode); Node expr = ret.expr(); if( expr instanceof ConstantNode con ) { assertEquals(start,con.in(0)); diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter04Test.java index 14d31245..edc62f50 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -83,7 +83,7 @@ public class Chapter04Test { Parser parser = new Parser("return arg; "); StopNode stop = parser.parse(); ReturnNode ret = stop.ret(); - assertTrue(ret.in(0) instanceof CProjNode); + assertTrue(ret.in(0) instanceof ProjNode); assertTrue(ret.in(1) instanceof ProjNode); assertEquals(1, ((ProjNode)ret.in(1))._idx); assertTrue(ret.in(2) instanceof ProjNode); diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 7beeb4d9..97cd9940 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -22,7 +22,7 @@ else { return a;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region21,(arg+2),(arg-3));", ret.toString()); + assertEquals("return Phi(Region19,(arg+2),(arg-3));", ret.toString()); } @Test @@ -37,7 +37,7 @@ if (arg == 1) { } return c;""", TypeInteger.BOT); StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region19,4,3);", ret.toString()); + assertEquals("return Phi(Region18,4,3);", ret.toString()); } @Test @@ -65,7 +65,7 @@ else b=a+1; return a+b;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return ((arg*2)+Phi(Region24,2,3));", ret.toString()); + assertEquals("return ((arg*2)+Phi(Region22,2,3));", ret.toString()); } @Test @@ -80,7 +80,7 @@ else a=b+1; return a+b;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return ((Phi(Region35,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString()); + assertEquals("return ((Phi(Region33,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString()); } @Test @@ -100,7 +100,7 @@ else return a; """, TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region39,Phi(Region25,2,3),Phi(Region37,4,5));", stop.toString()); + assertEquals("return Phi(Region37,Phi(Region23,2,3),Phi(Region35,4,5));", stop.toString()); } @Test @@ -116,7 +116,7 @@ if( arg==0 ) return arg+a+b; """, TypeInteger.BOT); StopNode stop = parser.parse(); - assertEquals("return ((arg+Phi(Region16,1,0))+Phi(Region31,2,0));", stop.toString()); + assertEquals("return ((arg+Phi(Region16,1,0))+Phi(Region32,2,0));", stop.toString()); } @Test @@ -130,7 +130,7 @@ if( arg==1 ) } return a;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return (arg==Phi(Region19,3,2));", ret.toString()); + assertEquals("return (arg==Phi(Region18,3,2));", ret.toString()); } @Test diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter06Test.java index df0f2848..9af11b68 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -17,7 +17,7 @@ return 1; """); StopNode stop = parser.parse().iterate(); assertEquals("return 2;", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -46,7 +46,7 @@ return a; """); StopNode stop = parser.parse().iterate(); assertEquals("return 2;", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -65,7 +65,7 @@ else b=5; return b;""", TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region40,42,5);", stop.toString()); + assertEquals("return Phi(Region38,42,5);", stop.toString()); } @Test @@ -84,7 +84,7 @@ else b=5; return b;""", TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region33,2,5);", stop.toString()); + assertEquals("return Phi(Region31,2,5);", stop.toString()); } @Test @@ -144,7 +144,7 @@ else return a; """, TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region44,3,Phi(Region42,4,5));", stop.toString()); + assertEquals("return Phi(Region42,3,Phi(Region40,4,5));", stop.toString()); } @Test @@ -251,7 +251,7 @@ if( arg ) { return a+b+c; """); StopNode ret = parser.parse().iterate(); - assertEquals("return (Phi(Region39,Phi(Region26,2,3),0)+Phi(Region,3,1));", ret.toString()); + assertEquals("return (Phi(Region39,Phi(Region24,2,3),0)+Phi(Region,3,1));", ret.toString()); } diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter07Test.java index 222982e7..ff0ca599 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter07Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -18,8 +18,8 @@ public class Chapter07Test { return arg; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop9,arg,(Phi_arg+1));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop7,arg,(Phi_arg+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -35,7 +35,7 @@ if(arg){}else{ return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region27,1,Phi(Loop16,1,(Phi_a+1)));", stop.toString()); + assertEquals("return Phi(Region25,1,Phi(Loop14,1,(Phi_a+1)));", stop.toString()); } @Test @@ -55,7 +55,7 @@ while(i < arg) { return sum; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,0,Phi(Loop23,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); + assertEquals("return Phi(Loop9,0,Phi(Loop21,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); } @Test @@ -71,8 +71,8 @@ while(a < 10) { return b; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop11,2,Phi(Region30,Phi_b,4));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop9,2,Phi(Region28,Phi_b,4));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -90,8 +90,8 @@ while(a < 10) { return b; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,2,(Phi(Region30,Phi_b,4)+1));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop9,2,(Phi(Region28,Phi_b,4)+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -107,8 +107,8 @@ while(a < 10) { return a; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -123,8 +123,8 @@ while(a < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -136,8 +136,8 @@ while(arg) a = 2; return a; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop10,1,2);", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop8,1,2);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -149,8 +149,8 @@ while(arg) a = 2; return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,1,2);", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop8,1,2);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -165,8 +165,8 @@ while(a < 10) { return a; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -181,8 +181,8 @@ while(a < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -198,8 +198,8 @@ while(a < 10) { return a; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop11,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop9,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -215,8 +215,8 @@ while(a < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop9,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } } diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter08Test.java index 8c644977..02c3a301 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -2,6 +2,7 @@ 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; @@ -23,7 +24,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region37,Phi(Region27,Phi(Loop9,arg,(Phi_arg+1)),Add),Add);", stop.toString()); + assertEquals("return Phi(Region38,Phi(Region26,Phi(Loop7,arg,(Phi_arg+1)),Add),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); Assert.assertEquals(5L, Evaluator.evaluate(stop, 1)); Assert.assertEquals(10L, Evaluator.evaluate(stop, 6)); @@ -46,8 +47,8 @@ while(arg < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,1,Phi(Region42,Phi_a,(Phi_a+1)));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop8,1,Phi(Region45,Phi_a,(Phi_a+1)));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -65,7 +66,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region35,Phi(Loop9,arg,(Phi_arg+1)),Add);", stop.toString()); + assertEquals("return Phi(Region36,Phi(Loop7,arg,(Phi_arg+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -81,7 +82,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region27,Phi(Loop9,arg,(Phi_arg+1)),Add);", stop.toString()); + assertEquals("return Phi(Region26,Phi(Loop7,arg,(Phi_arg+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -100,8 +101,8 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop9,arg,(Phi_arg+1));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop7,arg,(Phi_arg+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -117,8 +118,8 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop9,arg,(Phi_arg+1));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop7,arg,(Phi_arg+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -185,7 +186,7 @@ while(arg < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region30,Phi(Loop10,1,(Phi_a+1)),Add);", stop.toString()); + assertEquals("return Phi(Region29,Phi(Loop8,1,(Phi_a+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -201,8 +202,8 @@ while(1) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return (Phi(Loop10,1,Add)+1);", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode prj && prj._idx==1 ); + assertEquals("return (Phi(Loop8,1,Add)+1);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode prj && prj._idx==1 ); } } diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter09Test.java index 49ee75a2..b1fdc459 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -5,6 +5,7 @@ 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; @@ -69,7 +70,7 @@ while (arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,arg,(Phi_arg+2));", stop.toString()); + assertEquals("return Phi(Loop8,arg,(Phi_arg+2));", stop.toString()); Assert.assertEquals(11L, Evaluator.evaluate(stop, 1)); } @@ -86,7 +87,7 @@ while (arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,arg,(Phi_arg+4));", stop.toString()); + assertEquals("return Phi(Loop9,arg,(Phi_arg+4));", stop.toString()); Assert.assertEquals(13L, Evaluator.evaluate(stop, 1)); } @@ -115,7 +116,7 @@ while (arg) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop17,arg,(Phi_arg+1));", stop.toString()); + assertEquals("return Phi(Loop15,arg,(Phi_arg+1));", stop.toString()); } @Test @@ -133,7 +134,7 @@ while(v1+arg) { } """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 0; return 0; ]", stop.toString()); + assertEquals("return 0;", stop.toString()); } @Test @@ -185,7 +186,7 @@ while(arg) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop12,0,(-(Phi_a+3)));", stop.toString()); + assertEquals("return Phi(Loop10,0,(-(Phi_a+3)));", stop.toString()); } @Test @@ -199,7 +200,7 @@ int v0=0!=0<-0; return -0+0+0; """); StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + assertEquals("Stop[ ]", stop.toString()); } @@ -226,7 +227,7 @@ while(1) { } """); StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + assertEquals("Stop[ ]", stop.toString()); } @Test @@ -248,17 +249,16 @@ while(1) { return 0!=0; """); StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + assertEquals("Stop[ ]", stop.toString()); } @Test public void testFuzz6() { - Parser parser = new Parser( -""" + Parser parser = new Parser(""" int v0=0; while(0==1) while(v0) v0=1+v0; -"""); + """); StopNode stop = parser.parse().iterate(); assertEquals("return 0;", stop.toString()); } @@ -276,14 +276,14 @@ while(1) return v1+v0; """); StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + assertEquals("Stop[ ]", stop.toString()); } @Test public void testFuzz8() { Parser parser = new Parser("while(arg) arg = arg - 1; return arg;"); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop9,arg,(Phi_arg-1));", stop.toString()); + assertEquals("return Phi(Loop7,arg,(Phi_arg-1));", stop.toString()); } @Test diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 38aceb84..55574c13 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -169,7 +169,7 @@ while (arg) { return bar.a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop12,0,(Phi_a+2));", stop.toString()); + assertEquals("return Phi(Loop11,0,(Phi_a+2));", stop.toString()); } @Test @@ -221,7 +221,7 @@ if( bar ) bar.a = 1; return bar; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region17,null,new Bar);", stop.toString()); + assertEquals("return Phi(Region31,(*void)Phi(Region18,null,new Bar),null);", stop.toString()); } @Test @@ -237,7 +237,7 @@ else bar.a = 1; return rez; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region35,4,3);", stop.toString()); + assertEquals("return Phi(Region37,4,3);", stop.toString()); } @Test @@ -254,8 +254,7 @@ while(arg) { return ret; """); try { parser.parse().iterate(); fail(); } - catch( Exception e ) { - assertEquals("Might be null accessing 'v0'", e.getMessage()); } + catch( Exception e ) { assertEquals("Might be null accessing 'v0'", e.getMessage()); } } @Test @@ -307,12 +306,11 @@ while(arg) { v0.v0 = arg; arg = arg-1; if (arg==5) ret=v0; - } return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop12,new s0,Phi(Region34,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop11,new s0,Phi(Region35,new s0,Phi_ret));", stop.toString()); } @Test @@ -329,7 +327,7 @@ while(arg) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop15,new s0,Phi(Region35,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop15,new s0,Phi(Region36,new s0,Phi_ret));", stop.toString()); } @@ -346,7 +344,7 @@ while(arg < 10) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop12,new s0,Phi(Region32,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop11,new s0,Phi(Region33,new s0,Phi_ret));", stop.toString()); } @Test @@ -464,6 +462,7 @@ return 0; assertEquals("return 0;", stop.toString()); } + @Test public void testReadBeforeStores() { var stop = new Parser(""" struct S { int x; int y; } @@ -550,8 +549,8 @@ return 0; if (arg) s.x=arg+1; else s.x=arg+2; return s; """).parse().iterate(); - // These chapters still bind struct Stores to branch control. - assertEquals(3,countMemoryNodes(stop,StoreNode.class,new BitSet())); + // The initializing slice also remains live as the aggregate default. + assertEquals(2,countMemoryNodes(stop,StoreNode.class,new BitSet())); assertEquals(2L,((Evaluator.Obj)Evaluator.evaluate(stop,0)).fields()[0]); assertEquals(4L,((Evaluator.Obj)Evaluator.evaluate(stop,3)).fields()[0]); } diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter10bTest.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter10bTest.java deleted file mode 100644 index 6f094cfb..00000000 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter10bTest.java +++ /dev/null @@ -1,64 +0,0 @@ -package com.seaofnodes.simple; - -import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.evaluator.Evaluator; -import org.junit.Test; -import static org.junit.Assert.*; - -public class Chapter10bTest { - @Test public void testIndependentField() { - var stop = new Parser(""" - struct S { int x; int y; } - S s = new S; - s.x = 42; - while (arg > 0) { s.y = s.y + arg; arg = arg - 1; } - return s.x; - """).parse().iterate(); - assertEquals("return 42;",stop.toString()); - assertEquals(42L,Evaluator.evaluate(stop,5)); - assertNull(stop.walk(n -> n instanceof LoadNode ? n : null)); - } - - @Test public void testParallelMemoryPhis() { - var stop = new Parser(""" - struct S { int x; int y; int z; } - S a = new S; S b = new S; - S p = a; if (arg) p = b; - while (arg > 0) { - a.x = p.x + arg; - a.y = p.y + 2; - a.z = p.z + 3; - arg = arg - 1; - } - return a; - """).parse().iterate(); - int[] phis = {0}; - stop.walk(n -> { - if (n instanceof MemPhiNode) phis[0]++; - if (n instanceof MemMergeNode m && m.in(1) instanceof BulkMemPhiNode b) - for(int a=b._aliases.nextSetBit(0); a>=0; a=b._aliases.nextSetBit(a+1)) - assertTrue(a<m.nIns() && m.in(a)!=null); - assertFalse(n instanceof PhiNode && n.isMem() && - !(n instanceof MemPhiNode) && !(n instanceof BulkMemPhiNode)); - return null; - }); - assertTrue(phis[0]>=3); - assertArrayEquals(new Object[]{1L,2L,3L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields()); - } - - @Test public void testLateSliceWorklist() throws ReflectiveOperationException { - // Seed 97 exposed a store selecting a bulk predecessor without queuing - // it. Keep both the worklist assertion and the final heap check. - for (int seed : new int[]{0,97,123,456}) { - var parser = new Parser(Chapter10Test.NESTED_MEMORY); - var field = IterPeeps.class.getDeclaredField("WORK"); - field.setAccessible(true); - Object work = field.get(null); - field = work.getClass().getDeclaredField("_R"); - field.setAccessible(true); - ((java.util.Random)field.get(work)).setSeed(seed); - var stop = parser.parse().iterate(); - assertArrayEquals(new Object[]{9L,25L,17L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields()); - } - } -} diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 0e492591..5f92c9c1 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,532 +1,64 @@ package com.seaofnodes.simple; - +import com.seaofnodes.simple.node.*; 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.*; public class Chapter11Test { - - // A placeholder test used to rapidly rotate through fuzzer produced issues - @Test - public void testFuzzer() { - Parser parser = new Parser( -""" -while(-----arg) { - while(-arg) { - while(-----arg*---0) { - int N=--false==false<--arg; - while(N<-4==N) { - N=N+N; - } - } - { - int kzEl_r7EYz=3*----0!=-arg<(37*--97!=0/arg==arg)<=-(--arg!=0); - while(kzEl_r7EYz<---1) { - kzEl_r7EYz=kzEl_r7EYz+kzEl_r7EYz*arg>=24; - if(7) continue; - kzEl_r7EYz=false; - if(-kzEl_r7EYz+arg<-3) continue; - else { - while(kzEl_r7EYz) continue; - arg=----3; - kzEl_r7EYz=-(-----arg*1>-kzEl_r7EYz); - int v2uF_4ba=9; - } - } - } - int pjcp7rv=arg; - { - int m2ya3=--arg-pjcp7rv; - while(m2ya3<-----pjcp7rv>=pjcp7rv+--pjcp7rv!=---pjcp7rv!=-arg<---(-m2ya3)>m2ya3<=-----true>14!=--m2ya3) { - m2ya3=m2ya3+-(--0<=false<pjcp7rv/arg<=-true); - while((--m2ya3)<--arg<-----arg*false!=arg<pjcp7rv*arg) { - pjcp7rv=-3+-arg; - break; - } - while(-3) { - while(67+0-61) m2ya3=m2ya3; - if(----pjcp7rv==---(---arg)) pjcp7rv=0!=-23; - else pjcp7rv=----89; - while(m2ya3!=m2ya3<pjcp7rv) m2ya3=1; - while(--arg<=pjcp7rv) pjcp7rv=-32<=-m2ya3+62; - } - break; - } - } - { - int arg=-1<-9!=(-arg>=-pjcp7rv>=arg<=arg); - while(arg<-arg) { - arg=arg+--arg; - { - while((--93)--pjcp7rv*-pjcp7rv+arg) arg=0-(6>=(--(---41/(0))!=--pjcp7rv)>=---2*33); - pjcp7rv=11; - int c=pjcp7rv; - if(--107) break; - else break; - } - } - } - pjcp7rv=pjcp7rv; - int aR0Wkua=-pjcp7rv==pjcp7rv; - { - if(-0!=-0) while(-true) break; - else { - while(aR0Wkua) pjcp7rv=-0/pjcp7rv; - pjcp7rv=pjcp7rv; - } - } - } - if(-arg) { - { - int Isdlt0fr91=0!=arg; - while(Isdlt0fr91<-Isdlt0fr91==-Isdlt0fr91+true) { - Isdlt0fr91=Isdlt0fr91+-1!=true; - if(-arg) if(--arg<=Isdlt0fr91) Isdlt0fr91=-Isdlt0fr91; - int i=---arg<---arg!=--40; - { - int jVX43Ln4Dm=-(6)==-Isdlt0fr91/----0; - while(jVX43Ln4Dm<--(3-3)) { - jVX43Ln4Dm=jVX43Ln4Dm+-0<25; - i=24<--(jVX43Ln4Dm); - } - } - i=(arg!=----false>=7); - int Te=5>-arg; - break; - } - } - arg=arg!=--true/arg; - { - int UX=arg; - while(UX<-3*arg) { - UX=UX+arg/-1; - arg=-3--(-UX--47<arg==--arg==arg)/arg--UX>=-arg; - if(---12) while(-UX) break; - break; - } - } - continue; - } - if(arg) arg=--0; - else if(1) continue; - int DtTlhjYq=19==arg; - { - arg=--DtTlhjYq<=(DtTlhjYq/---DtTlhjYq<=-DtTlhjYq); - if(---arg) continue; - else { - int Zsl=40; - while(Zsl<--Zsl--false>((Zsl))==Zsl!=--DtTlhjYq-DtTlhjYq-DtTlhjYq) { - Zsl=Zsl+arg; - } - } - if((arg)) if(-DtTlhjYq) { - } - else while(((2)==3*arg/DtTlhjYq)<=0==---arg) return false; - else { - int lwbF=arg>=0; - while(lwbF<57) { - lwbF=lwbF+--(-arg+lwbF)>=-2>=arg!=arg; - arg=----0+0; - while(49) break; - if(true) DtTlhjYq=-----arg; - DtTlhjYq=0!=-----(0); - } - } - arg=---arg!=DtTlhjYq/--0; - DtTlhjYq=-DtTlhjYq/(--arg<arg); - if(32) { - int q=-DtTlhjYq; - while(q<arg*(0*q)/0) { - q=q+DtTlhjYq; - DtTlhjYq=arg; - } - } - else if(--arg) if(15) break; - else arg=0==arg<=-55>DtTlhjYq; - else { - } - DtTlhjYq=-0; - { - while((0)<-arg) DtTlhjYq=-DtTlhjYq; - } - if(30/--(arg)>=0) DtTlhjYq=-0>=arg; - else { - int Y2wcIQJ=--DtTlhjYq*---11; - if(arg==arg) { - Y2wcIQJ=-----Y2wcIQJ; - Y2wcIQJ=Y2wcIQJ<7; - if(DtTlhjYq) arg=arg; - else break; - while(-arg!=-31==(false<=-15>=-DtTlhjYq+--6*-----Y2wcIQJ<=---arg!=-Y2wcIQJ<=---0<-arg*--Y2wcIQJ)) DtTlhjYq=arg!=3; - } - continue; - } - arg=DtTlhjYq; - arg=--3/(---arg)>=80>=-DtTlhjYq<=DtTlhjYq; - arg=51+---(-true)!=arg!=----1==-DtTlhjYq; - if(11<=arg) if((arg)+79<32+(-arg)) continue; - else if(true==DtTlhjYq) break; - break; - } -} -if(arg!=62==arg) { - while(---arg) { - { - int bhmDacPM=arg/arg; - while(bhmDacPM<arg) { - bhmDacPM=bhmDacPM+80*((-bhmDacPM)/---bhmDacPM>1)<bhmDacPM-2!=7; - arg=-0; - arg=bhmDacPM>=-arg+-arg; - break; - } - } - int arg=true; - arg=arg<=arg; - { - int KlC=30; - while(KlC<-2) { - KlC=KlC+-1!=25<=-KlC>KlC>----0; - int Ij=arg>=-arg<=---10; - { - int LAbgurVa2R=-arg!=Ij; - while(LAbgurVa2R<-true) { - LAbgurVa2R=LAbgurVa2R+Ij; - KlC=-LAbgurVa2R; - Ij=42*(-Ij>true); - while(Ij) arg=KlC; - KlC=-----7>-(--KlC<--7)==-LAbgurVa2R; - } - } - int a=Ij<=-KlC; - if(Ij) { - int r1W=a!=-false; - } - else { - arg=56>=Ij; - while(54) break; - arg=8>=-(a<--Ij)/a>=-a-KlC; - } - int Yt_T=KlC; - arg=KlC; - } + @Test public void testIndependentField() { + var stop = new Parser(""" + struct S { int x; int y; } + S s = new S; + s.x = 42; + while (arg > 0) { s.y = s.y + arg; arg = arg - 1; } + return s.x; + """).parse().iterate(); + assertEquals("return 42;",stop.toString()); + assertEquals(42L,Evaluator.evaluate(stop,5)); + assertNull(stop.walk(n -> n instanceof LoadNode ? n : null)); + } + + @Test public void testParallelMemoryPhis() { + var stop = new Parser(""" + struct S { int x; int y; int z; } + S a = new S; S b = new S; + S p = a; if (arg) p = b; + while (arg > 0) { + a.x = p.x + arg; + a.y = p.y + 2; + a.z = p.z + 3; + arg = arg - 1; + } + return a; + """).parse().iterate(); + int[] phis = {0}; + stop.walk(n -> { + if (n instanceof MemPhiNode) phis[0]++; + if (n instanceof MemMergeNode m && m.in(1) instanceof BulkMemPhiNode b) + for(int a=b._aliases.nextSetBit(0); a>=0; a=b._aliases.nextSetBit(a+1)) + assertTrue(a<m.nIns() && m.in(a)!=null); + assertFalse(n instanceof PhiNode && n.isMem() && + !(n instanceof MemPhiNode) && !(n instanceof BulkMemPhiNode)); + return null; + }); + assertTrue(phis[0]>=3); + assertArrayEquals(new Object[]{1L,2L,3L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields()); + } + + @Test public void testLateSliceWorklist() throws ReflectiveOperationException { + // Seed 97 exposed a store selecting a bulk predecessor without queuing + // it. Keep both the worklist assertion and the final heap check. + for (int seed : new int[]{0,97,123,456}) { + var parser = new Parser(Chapter10Test.NESTED_MEMORY); + var field = IterPeeps.class.getDeclaredField("WORK"); + field.setAccessible(true); + Object work = field.get(null); + field = work.getClass().getDeclaredField("_R"); + field.setAccessible(true); + ((java.util.Random)field.get(work)).setSeed(seed); + var stop = parser.parse().iterate(); + assertArrayEquals(new Object[]{9L,25L,17L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields()); } - if(----false/--arg/12+-----0) if(-9+-arg) while(arg!=(arg)) arg=--1>=-71-arg!=---(--arg*11+102)/--arg; - else if(----arg) continue; - if(-arg-arg) { - arg=-(-arg)*--(-3)<(-7==-arg----arg); - { - int arg=arg; - while(arg<-0>arg==-arg-(-arg>1+11)) { - arg=arg+6-arg!=--0>---30>=---arg<=arg/(3)+---arg; - } - } - arg=-arg+arg; - arg=--47+-arg<1>arg*(-arg==-arg--0>3); - arg=(----arg)!=arg+--59; - arg=--4+arg==-(arg)-arg; - } - else { - while(--true-----true*-25+-18>arg>=-----(-arg)---13) { - arg=-0+--true<false; - continue; - } - arg=true<=arg; - break; - } - arg=arg*22<--(0+-arg); - { - continue; - } - } - arg=1*---((3<=true)==---2); - arg=7+-(-1); - return arg+--true; -} -else { - int o3ypEsewxM=-(---arg); - int vzXB=(-(---11<=--o3ypEsewxM>=--0))<=-0/-arg; - int L=-arg; - int B4mHcrf=---vzXB; - int oZWGdzZl=-o3ypEsewxM; - int K6tQqa1=11; - while(0!=--L) { - int sdZfTM=vzXB*true+K6tQqa1; - while(sdZfTM<false) { - sdZfTM=sdZfTM+arg; - sdZfTM=oZWGdzZl; - K6tQqa1=-K6tQqa1; - arg=---K6tQqa1; - while((3+-K6tQqa1)<oZWGdzZl) { - if(-----(-1)) sdZfTM=-false; - {} - } - K6tQqa1=vzXB!=-(B4mHcrf+-7>false); - sdZfTM=vzXB; - } - } - L=false; - while(31) B4mHcrf=arg; - oZWGdzZl=-0<--oZWGdzZl<=--2; - if(K6tQqa1>=20<=46) { - if(-1+-L) if(oZWGdzZl) { - int wmhv=-----0; - } - int arg=0; - o3ypEsewxM=---(oZWGdzZl); - return -oZWGdzZl/0; - } - else if(arg) { - int yKk5=B4mHcrf>=4>K6tQqa1<-B4mHcrf/o3ypEsewxM; - return -K6tQqa1; - } - else { - if(---0) { - {} - {} - } - return o3ypEsewxM; - } -} -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 9; return 0; return 0; return 0; return 0; ]", stop.toString()); - } - - - @Test - public void testPrimes() { - Parser parser = new Parser( -""" -if( arg < 2 ) return 0; -int primeCount = 1; -int prime = 3; -while( prime <= arg ) { - int isPrime = 1; - // Check for even case, so the next loop need only check odds - if( (prime/2)*2 == prime ) - continue; - // Check odds up to sqrt of prime - int j = 3; - while( j*j <= prime ) { - if( (prime/j)*j == prime ) { - isPrime = 0; - break; - } - j = j + 2; - } - if( isPrime ) - primeCount = primeCount + 1; - prime = prime + 2; -} -return primeCount; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 0; return Phi(Loop20,1,Phi(Region82,Phi_primeCount,Phi(Region77,(Phi_primeCount+1),Phi_primeCount))); ]", stop.toString()); - assertEquals(0L, Evaluator.evaluate(stop, 1)); // No primes 1 or below - assertEquals(1L, Evaluator.evaluate(stop, 2)); // 2 - assertEquals(2L, Evaluator.evaluate(stop, 3)); // 2, 3 - assertEquals(2L, Evaluator.evaluate(stop, 4)); // 2, 3 - assertEquals(3L, Evaluator.evaluate(stop, 5)); // 2, 3, 5 - assertEquals(4L, Evaluator.evaluate(stop, 10)); // 2, 3, 5, 7 - } - - @Test - public void testAntiDeps1() { - Parser parser = new Parser( -""" -struct S { int f; } -S v=new S; -v.f = 2; -int i=new S.f; -i=v.f; -if (arg) v.f=1; -return i; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return .f;", stop.toString()); - } - - @Test - public void testAntiDeps2() { - Parser parser = new Parser( -""" -struct S { int f; } -S v = new S; -S t = new S; -int i = 0; -if (arg) { - if (arg+1) v = t; - i = v.f; -} else { - v.f = 2; -} -return i; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region34,.f,0);", stop.toString()); - } - - @Test - public void testAntiDeps3() { - Parser parser = new Parser( -""" -struct S { int f; } -S v0 = new S; -S? v1; -if (arg) v1 = new S; -if (v1) { - v0.f = v1.f; -} else { - v0.f = 2; -} -return v0; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return new S;", stop.toString()); - } - - - @Test - public void testAntiDeps4() { - Parser parser = new Parser( -""" -struct S { int f; } -S v = new S; -S t = new S; -int i = v.f; -if (arg+1) arg= 0; -while (arg) v.f = 2; -return i; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return .f;", stop.toString()); - } - - @Test - public void testAntiDeps5() { - Parser parser = new Parser( -""" -struct S { int f; } -S v = new S; -while(1) { - while(arg+1) { arg=arg-1; } - if (arg) break; - v.f = 2; -} -return v; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return new S;", stop.toString()); - } - - @Test - public void testAntiDeps6() { - Parser parser = new Parser( -""" -struct s { int v; } -s ptr=new s; -while( -arg ) - ptr = new s; -while(1) - arg = arg+ptr.v; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 0; return 0; ]", stop.toString()); - } - - @Test - public void testAntiDeps7() { - Parser parser = new Parser( -""" -struct S { int f; } -S v = new S; -S t = new S; -int i = v.f; -while (arg) { - v.f = arg; - arg = arg-1; -} -return i; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return .f;", stop.toString()); - } - - @Test - public void testAntiDeps8() { - Parser parser = new Parser( -""" -struct S { int f; } -S v = new S; -S t = new S; -while(arg) { - arg=arg-1; - int f = v.f; - v.f = 2; - if (arg) arg = f; - else v.f = 3; -} -return arg; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop15,arg,Phi(Region39,.f,0));", stop.toString()); - } - - @Test - public void testAntiDeps9() { - Parser parser = new Parser( -""" -struct S { int f; } -S v = new S; -S t = new S; -if (arg) { - v.f=2; - int i=t.f; - v.f=i; -} -return v; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return new S;", stop.toString()); - } - - @Test - public void testExample2() { - Parser parser = new Parser( - """ -struct S { int f; } -S v = new S; -int i = arg; -while (arg > 0) { - int j = i/3; - if (arg == 5) - v.f = j; - arg = arg - 1; -} -return v; - """); - StopNode stop = parser.parse().iterate(); - //assertEquals("return new S;", stop.toString()); - } - - @Test - public void testSplit() { - Parser parser = new Parser( - """ -struct S { int f; } -S s = new S; -if( arg==0 ) s.f = 1; -else if (arg == 1) s.f = 1; -return s.f; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region41,1,Phi(Region36,1,0));", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 0)); - assertEquals(1L, Evaluator.evaluate(stop, 1)); - assertEquals(0L, Evaluator.evaluate(stop, 2)); } } diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter12Test.java index e577c8c3..0d4f3c97 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -2,84 +2,199 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.StopNode; +import com.seaofnodes.simple.type.TypeStruct; +import com.seaofnodes.simple.type.TypeMemPtr; +import org.junit.Ignore; import org.junit.Test; - - import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; +import static org.junit.Assert.assertNull; +import static org.junit.Assert.assertSame; public class Chapter12Test { - @Test public void testSubZeroFloat() { - var stop = new Parser("flt x = arg; return 0-x;").parse().iterate(); - // Compare strings so +0.0 and -0.0 remain distinct. - assertEquals("0.0", Evaluator.evaluate(stop,0).toString()); - assertEquals("-1.0", Evaluator.evaluate(stop,1).toString()); + + @Test + public void testLinkedList0() { + Parser parser = new Parser( +""" +struct LLI { LLI? next; int i; } +LLI? head = null; +while( arg ) { + LLI x = new LLI; + x.next = head; + x.i = arg; + head = x; + arg = arg-1; +} +return head.next.i; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Might be null accessing 'next'",e.getMessage()); } } - @Test public void testDeadNumericReturns() { - for( String[] test : new String[][] { - {"if(1) return 7; else return 2.5;", "7"}, - {"if(0) return 7; else return 2.5;", "2.5"}, - {"return 7; return 2.5;", "7"}, - {"return 2.5; return 7;", "2.5"} - } ) { - String src = test[0]; - var stop = new Parser(src).parse().iterate(); - assertEquals(src,test[1],com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,0).toString()); - } + @Test + public void testLinkedList1() { + Parser parser = new Parser( +""" +struct LLI { LLI? next; int i; } +LLI? head = null; +while( arg ) { + LLI x = new LLI; + x.next = head; + x.i = arg; + head = x; + arg = arg-1; +} +if( !head ) return 0; +LLI? next = head.next; +if( next==null ) return 1; +return next.i; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ return 0; return 1; return .i; ]", stop.toString()); + assertEquals(2L, Evaluator.evaluate(stop, 3)); } + @Test + public void testCoRecur() { + Parser parser = new Parser( +""" +struct Left { int i; Right? f; } +struct Right { int f; Left? i; } +Left left = new Left; +left.i = 17; +Right right = new Right; +right.f = 314; +left.f = right; +right.i = left; +return right.i.f.i.i; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 17;", stop.toString()); + } @Test - public void testJig() { + public void testNullReright() { Parser parser = new Parser( """ -return 3.14; +struct N { N next; int i; } +N n = new N; +return n.next; """); StopNode stop = parser.parse().iterate(); - assertEquals("return 3.14;", stop.toString()); - assertEquals(3.14, Evaluator.evaluate(stop, 0)); + assertEquals("return null;", stop.toString()); } @Test - public void testFloat() { + public void testNullRef1() { Parser parser = new Parser( """ -return 3.14; +struct N { N next; int i; } +N n = new N; +n.next = new N; +return n.next; """); StopNode stop = parser.parse().iterate(); - assertEquals("return 3.14;", stop.toString()); - assertEquals(3.14, Evaluator.evaluate(stop, 0)); + assertEquals("return new N;", stop.toString()); } @Test - public void testSquareRoot() { + public void testNullRef2() { Parser parser = new Parser( """ -flt guess = arg; -while( 1 ) { - flt next = (arg/guess + guess)/2; - if( next == guess ) break; - guess = next; -} -return guess; +struct N { N next; int i; } +N n = new N; +n.next = null; +return n.next; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Cannot store null into field *N next",e.getMessage()); } + } + + + @Test + public void testNullRef4() { + Parser parser = new Parser("-null-5/null-5"); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Expected an identifier, found 'null'",e.getMessage()); } + } + + @Test public void testNullRef5() { + Parser parser = new Parser("return null+42;"); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Cannot 'Add' null",e.getMessage()); } + } + + @Test + public void testEmpty() { + Parser parser = new Parser( +""" +struct S{}; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)/2.0));", stop.toString()); - assertEquals(3.0, Evaluator.evaluate(stop, 9)); - assertEquals(1.414213562373095, Evaluator.evaluate(stop, 2)); + assertEquals("return 0;", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testForwardReright() { + Parser parser = new Parser( +""" +struct S1 { S2 s; } +return new S2; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Unknown struct type 'S2'",e.getMessage()); } } @Test - public void testFPOps() { + public void testForwardRef1() { Parser parser = new Parser( """ -flt x = arg; -return x+1==x; +struct S1 { S2? s; } +struct S2 { int x; } +return new S1.s=new S2; """); StopNode stop = parser.parse().iterate(); - assertEquals("return ((flt)arg==(ToFloat+1.0));", stop.toString()); - assertEquals(0L, Evaluator.evaluate(stop, 1)); + assertEquals("return new S1;", stop.toString()); } + @Test + public void testcheckNull() { + Parser parser = new Parser( +""" +struct I {int i;} +struct P {I pi;} +P p1 = new P; +P p2 = new P; +p2.pi = new I; +p2.pi.i = 2; +if (arg) p1 = new P; +return p1.pi.i + 1; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Might be null accessing 'i'",e.getMessage()); } + } + + + @Test + public void testShallowRecursiveType() { + new Parser("struct LLI { LLI? next; int i; } return 0;").parse().iterate(); + TypeStruct l1 = (TypeStruct)Parser.TYPES.get("LLI"); + TypeStruct l0 = ((TypeMemPtr)l1._fields[0]._type)._obj; + assertEquals("LLI", l0._name); + assertNull(l0._fields); + assertEquals(2, l1._fields.length); + assertSame(l0, l1.meet(l0)); + assertSame(l0, l0.dual()); + assertSame(l0, l0.glb()); + } + + @Test + public void testUnusedForwardReference() { + StopNode stop = new Parser("struct Holder { Missing? ref; } Holder h = new Holder; return h.ref;") + .parse().iterate(); + assertEquals("return null;", stop.toString()); + assertNull(((TypeStruct)Parser.TYPES.get("Missing"))._fields); + } } diff --git a/chapter12/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/chapter12/src/test/java/com/seaofnodes/simple/FuzzerWrap.java index 52c2a014..019140ad 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/FuzzerWrap.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/FuzzerWrap.java @@ -29,8 +29,8 @@ public class FuzzerWrap { fuzzer.fuzzPeepsRegression(seed); } - @Ignore @Test + @Ignore public void fuzzPeepsLarge() { var fuzzer = new Fuzzer(); for (int i=0; i<1000000; i++) diff --git a/chapter12/src/test/java/com/seaofnodes/simple/TypeTest.java b/chapter12/src/test/java/com/seaofnodes/simple/TypeTest.java index f9c580cc..298fc6f8 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -36,9 +36,9 @@ public class TypeTest { Assert.assertEquals(TypeMem .BOT, m2.meet(m3)); Assert.assertEquals(TypeMem .BOT, m3.meet(m4)); - Assert.assertEquals(TypeMem.BOT, m1.glb()); + Assert.assertEquals(m1, m1.glb()); Assert.assertEquals(m1, m1.dual()); - Assert.assertEquals(TypeMem.TOP, m1.glb().dual()); + Assert.assertEquals(m1, m1.glb().dual()); TypeMemPtr ptr1 = TypeMemPtr.make(s1); Assert.assertEquals(s1, ptr1._obj); diff --git a/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index 40a2f78d..ac7c5e09 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -2,7 +2,10 @@ package com.seaofnodes.simple.evaluator; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.type.*; +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 java.lang.invoke.MethodHandle; import java.lang.invoke.MethodHandles; @@ -77,10 +80,6 @@ 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; @@ -116,16 +115,10 @@ 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; } @@ -134,30 +127,20 @@ 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 MemMergeNode merge -> MEMORY; case NewNode alloc -> alloc(alloc); - case CProjNode cproj -> ((Object[])val(cproj.ctrl()))[cproj._idx]; - case ProjNode proj -> ((Object[])val( proj.in(0) ))[ proj._idx]; + case ProjNode proj -> ((Object[])val(proj.ctrl()))[proj._idx]; default -> throw new AssertionError("Unexpected node " + node); }; } diff --git a/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java b/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java index d16f4300..48ac0562 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java @@ -164,7 +164,7 @@ public class Scheduler { * @return true if the node is not XCtrl. */ private static boolean isNotXCtrl(Node node) { - return !(node instanceof ConstantNode c && c.compute() == Type.XCONTROL) && !(node instanceof XCtrlNode); + return !(node instanceof ConstantNode c && c.compute() == Type.XCONTROL); } /** @@ -215,7 +215,7 @@ public class Scheduler { private void refinePlacement(NodeData data, BasicBlock block) { assert !isPinnedNode(data); data.block = data.block == null ? block : dom(data.block, block); - assert isValid(data); + assert isValid(data) : data.node.uniqueName()+" at "+data.block.entry.uniqueName(); } /** @@ -328,8 +328,6 @@ public class Scheduler { for(int i=1; i<r.nIns(); i++) { if (od(r.in(i)).map(d->d.block==null).orElse(false)) return false; } - } else if (node instanceof XCtrlNode) { - return false; } else { assert d(node.in(0)).block != null; } @@ -405,7 +403,7 @@ public class Scheduler { } } if (!(node instanceof ReturnNode)) - for (Node n:node._outputs) if (n!=null && n.isCFG() && isCFGNodeReady(n) && d(n).block == null) queue.push(d(n)); + for (Node n:node._outputs) if (n.isCFG() && isCFGNodeReady(n) && d(n).block == null) queue.push(d(n)); var b = block; for(var in:data.node._inputs) od(in).ifPresent(d->update(d, b)); } @@ -451,7 +449,7 @@ public class Scheduler { node = data.node; assert node.isCFG(); if (!(node instanceof ReturnNode)) { - for (var out : node._outputs) if (out!=null && out.isCFG() && isNotXCtrl(out)) markAlive(cfgQueue, out, true); + for (var out : node._outputs) if (out.isCFG() && isNotXCtrl(out)) markAlive(cfgQueue, out, true); } for (var in : node._inputs) if(in!=null && !in.isCFG() && isNotXCtrl(in)) markAlive(dataQueue, in, false); } @@ -505,7 +503,7 @@ public class Scheduler { */ private static Node findSingleCFGOut(Node node) { if (node instanceof StartNode) { - for(var n:node._outputs) if (n instanceof CProjNode p && p._idx==0) return p; + for(var n:node._outputs) if (n instanceof ProjNode p && p._idx==0) return p; return null; } assert node._outputs.stream().filter(Node::isCFG).limit(2).count()<=1; @@ -572,7 +570,7 @@ public class Scheduler { switch(block.exit) { case null: break; case IfNode i: - for(var out:i._outputs) if (out instanceof CProjNode p) block.next[p._idx] = blocks.get(p); + for(var out:i._outputs) if (out instanceof ProjNode p) block.next[p._idx] = blocks.get(p); break; case RegionNode r: block.next[0] = blocks.get(r); diff --git a/chapter12/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/chapter12/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java index b8437b50..14baadba 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -3,9 +3,7 @@ package com.seaofnodes.simple.fuzzer; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.node.ScopeNode; -import java.util.ArrayList; -import java.util.HashSet; -import java.util.Random; +import java.util.*; import java.util.function.Predicate; /** @@ -70,11 +68,10 @@ public class ScriptGenerator { private static class TypeStruct extends Type { record Field (String name, Type type, TypeStruct struct) {} - final Field[] fields; + Field[] fields; final TypeNullable nullable = new TypeNullable(this); - TypeStruct(String name, Field[] fields) { + TypeStruct(String name) { super(name); - this.fields = fields; } boolean isa(Type other) { return this == other || other == nullable; } } @@ -90,21 +87,7 @@ public class ScriptGenerator { } - 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 final Type TYPE_INT = new Type("int"); private static class Variable { @@ -159,6 +142,10 @@ public class ScriptGenerator { */ private final ArrayList<TypeStruct> structs = new ArrayList<>(); /** + * All forward declared structs + */ + private final ArrayList<TypeStruct> forwardStructs = new ArrayList<>(); + /** * Allow to declare structs. */ private boolean allowStructs = true; @@ -301,6 +288,7 @@ public class ScriptGenerator { for (var s:structs) { if (s.name.equals(name)) return s; } + for (var s:forwardStructs) if (s.name.equals(name)) return s; return null; } @@ -333,12 +321,18 @@ public class ScriptGenerator { return v; } + private <T> T randFromList(List<T> list) { + return list.get(random.nextInt(list.size())); + } + /** * Get a random structure name * @return A random structure name */ private String getStructName() { - if (!structs.isEmpty() && generateInvalid()) return structs.get(random.nextInt(structs.size())).name; + if (!structs.isEmpty() && generateInvalid()) return randFromList(structs).name; + if (!forwardStructs.isEmpty() && generateInvalid()) return randFromList(forwardStructs).name; + // Generate a new random struct name StringBuilder sb = getRandomName(); var v = sb.toString(); @@ -357,16 +351,26 @@ public class ScriptGenerator { * Get a random type * @return A random type */ - private Type getType() { + private Type getType(boolean allowForward) { 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 (allowForward && random.nextInt(10)==0) { + int i=random.nextInt(forwardStructs.size()+1); + if (i>0) return forwardStructs.get(i-1).nullable; + var name = getStructName(); + var struct = new TypeStruct(name); + forwardStructs.add(struct); + return struct.nullable; + } + TypeStruct struct = randFromList(structs); if (random.nextBoolean()) return struct.nullable; return struct; } + private Type getType() { + return getType(false); + } + /** * Generates a program and writes it into the string builder supplied in the constructor. * @return If the program is allowed to be invalid returns if something potentially invalid was generated. @@ -426,19 +430,28 @@ public class ScriptGenerator { * @return 0 */ public int genStruct() { - var name = getStructName(); + int idx = random.nextInt(forwardStructs.size()+10); + TypeStruct struct; + if (idx < 10) { + var name = getStructName(); + struct = new TypeStruct(name); + forwardStructs.add(struct); + } else { + struct = forwardStructs.get(idx-10); + } var fields = new TypeStruct.Field[generateInvalid() ? 0 : random.nextInt(10)]; - var struct = new TypeStruct(name, fields); - sb.append("struct ").append(name).append(" {\n"); + sb.append("struct ").append(struct.name).append(" {\n"); indentation += INDENTATION; for (int i=0; i<fields.length; i++) { var fieldName = getRandomName(); - var type = getType(); + var type = getType(true); printIndentation().append(type.name).append(" ").append(fieldName).append(";\n"); fields[i] = new TypeStruct.Field(fieldName.toString(), type, struct); } indentation -= INDENTATION; printIndentation().append("}"); + struct.fields = fields; + forwardStructs.remove(struct); structs.add(struct); return 0; } @@ -697,7 +710,7 @@ public class ScriptGenerator { */ public void genExpression(Type type, boolean change) { if (change && generateInvalid()) type = getType(); - if (type != TYPE_INT && type != TYPE_FLT) { + if (type != TYPE_INT) { genUnary(type, false); return; } @@ -714,7 +727,7 @@ public class ScriptGenerator { */ public void genUnary(Type type, boolean change) { if (change && generateInvalid()) type = getType(); - if (type != TYPE_INT && type != TYPE_FLT) { + if (type != TYPE_INT) { genSuffix(type, false); return; } @@ -794,17 +807,16 @@ public class ScriptGenerator { */ public void genConst(Type type) { if (generateInvalid()) type = getType(); - if (type == TYPE_INT || (type == TYPE_FLT && random.nextBoolean())) { + if (type == TYPE_INT) { 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()) { + if ((n.base instanceof TypeStruct s && s.fields == null) || random.nextBoolean()) { sb.append("null"); } else { sb.append("new ").append(generateInvalid() ? getRandomName() : n.base.name); |
