diff options
| author | Cliff Click <cliffc@acm.org> | 2026-09-29 12:34:58 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-09-29 12:34:58 -0700 |
| commit | f05ad3837117b3b8cb830981aae619c583d7e694 (patch) | |
| tree | ceed1399ae4c062adaedfc98625ac5fe632731fe | |
| parent | 502e7e752f3efdb069a36b23ab51ac22f9d74e9e (diff) | |
| download | Simple-linear-chapter10b.tar.gz Simple-linear-chapter10b.zip | |
Chapter 10b: Splitting Memorylinear-chapter10b
34 files changed, 2185 insertions, 60 deletions
diff --git a/#README.md# b/#README.md# new file mode 100644 index 00000000..6380b79e --- /dev/null +++ b/#README.md# @@ -0,0 +1,174 @@ +# Chapter 10b: Splitting Memory + +[Previous: Chapter 10a](../chapter10a/README.md) | +[Next: Chapter 11](../chapter11/README.md) + +Chapter 10a made memory effects explicit with one SSA memory value. This +chapter keeps exactly that parser model and recovers independent memory chains +through graph rewrites. There is no new language syntax; the +[grammar](docs/10-grammar.md), pointer types, and null checks are unchanged. + +## Why split memory? + +```java +struct Point { int x; int y; } +Point p = new Point; +p.x = 42; +while (arg > 0) { + p.y = p.y + arg; + arg = arg - 1; +} +return p.x; +``` + +The loop changes `y`, so it cannot affect `x`. With one memory chain the load +of `x` follows the loop's stores. Splitting the fields lets ordinary +load-after-store forwarding turn the return value into 42. + + + +Control, pointer, and value edges are omitted when they do not explain memory. + +## Equivalence-class aliasing + +Each struct field has an integer alias identity. Two different fields receive +different identities, even if they have the same spelling in different structs. +Two instances of the same struct share their field aliases. Thus different +classes never alias; accesses in the same class **may alias**. Same-class does +not mean same-address: forwarding still checks pointer identity. + +The parser assigns field identities at struct declarations, beginning at 2. +These identities are independent of Start's output indices. The default slot +of a memory aggregate is 1; precise slots are greater than 1. + +We do not allocate a Start projection, scope binding, or loop Phi for every +declared field. Start supplies one memory value, Scope holds one `$mem` binding, +and Return consumes one complete memory value. The optimizer introduces slices +only where graph operations require them. + +## Three memory nodes + +| Node | Meaning | +|---|---| +| `MemMerge` | A complete memory state: a default plus precise alias overrides | +| `MemPhi` | One alias selected according to the incoming control path | +| `BulkMemPhi` | All aliases except an explicit exclusion set, selected by control | + +`MemMerge` combines independent pieces of memory at one program point. It is +not a control-flow merge. For example, after storing to alias `x`: + +```text +prior = current memory +store = Store_x(prior, pointer, value) +current memory = MemMerge(default=prior, x=store) +``` + +The Store selects its precise input from any incoming MemMerge. Loads and +precise memory Phis do the same. A missing precise entry falls back to the +default, provided that default still covers the requested alias. + +The explicit entries override the default: the semantic slices are disjoint, +and their union covers all memory. Flattening stacked aggregates preserves +entries that the outer aggregate has not replaced. This allows an `x` store +and a later `y` store to remain visible together at Return. + + + +## Splitting a memory Phi + +Scope initially creates a BulkMemPhi wherever the ordinary SSA algorithm needs +to merge memory. Its empty exclusion set means that it covers every alias. +After the Region is complete, the Phi inspects its memory inputs and users. +When they require a precise alias, it splits out that alias: + +```text +BulkPhi(R, left, right) + becomes +MemMerge( + default = BulkPhi_except{x}(R, left, right), + x = MemPhi_x(R, slice(left,x), slice(right,x))) +``` + +The new precise Phi and the remaining bulk Phi share a Region and matching +control-path indices. A loop uses the same transformation, with the backedge +among those inputs. Each further split preserves all previously extracted +slices; replacing a bulk Phi must never drop their parallel precise Phis. + + + +A bulk Phi can bypass an incoming aggregate only when all of that aggregate's +explicit slices are already excluded from the Phi. A precise consumer can +select one entry. A whole-memory consumer cannot just select the default: +that would lose the explicit updates. + +## Types and the worklist + +The memory type lattice adds a flat element `MEM#N` for each precise alias. +Meeting different aliases gives `TypeMem.BOT`. It does not track field values, +private objects, or escape information. Bulk exclusion sets belong to the +graph nodes, not to an expanded type lattice. + + + +Scalar Phis remain ordinary PhiNodes. The scope's Phi factory chooses a +BulkMemPhi for whole memory; splitting constructs MemPhis explicitly. Generic +arithmetic factoring through Phis must not factor a memory aggregate. + +Memory splitting can increase node count. Progress comes from extracting an +alias from a bulk Phi and simplifying its precise chain, rather than from +requiring every rewrite to shrink the graph. Nodes must have conservative +initial types before introducing cyclic inputs. New bulk and precise Phis are +queued, so a recursive peephole cannot start another split halfway through the +first one. + +This also extends the worklist lesson from Chapter 9. A bulk Phi inspects its +users, so changes to a user's partition must wake the producer. Selecting a +slice from an aggregate can expose a new bulk-Phi user; that selected definition +must be queued too. The optimizer's worklist completeness assertion remains +enabled and checks these dependencies. + +## Evaluation and ordering + +MemMerge is a dependency node; it emits no heap operation. Its evaluator result +is a memory token, while Store mutates the object's fields. The scheduler must +distinguish aggregation from overwriting memory. A MemMerge is not a clobber, +and stores in different alias classes do not impose load/store anti-dependencies. + + + +Tests cover independent-field folding, parallel memory Phis, multiple field +updates surviving at Return, early returns, nested loops with break/continue, +and reads before subsequent stores through potentially aliased pointers. + +## What remains for later chapters? + +Chapter 10b knows every access's alias while parsing. What is lazy here is the +construction of memory partitions. Chapter 25 also allows an existing access's +alias to become known later, using the same representation. Its private +constructor memory, escape tracking, incomplete types, and module alias +remapping are separate extensions and are not needed here. + +Chapters 11-24 currently retain their older parser-managed memory chains. +Forwarding this representation through those snapshots is tracked in the +[backport queue](../docs/chapter-backports.md). Chapter 11's scheduling lesson +therefore still shows the older graph construction, with the same language. + +## Build and test + +With JDK 21 or newer, from this directory: + +```sh +make lib +make tests +make release +make view +``` + +Make builds this complete snapshot without Maven. `make release` writes +`build/release/simple.jar`; `make view` launches the shared graph viewer. +Both the root Maven reactor and the supplied IDEA module descriptor include +the chapter. From the repository root, test both halves with: + +```sh +make tests CHAPTERS="chapter10a chapter10b" +``` diff --git a/.#README.md b/.#README.md new file mode 100644 index 00000000..c657b199 --- /dev/null +++ b/.#README.md @@ -0,0 +1 @@ +cliffc@DESKTOP-DAD.21980:1790387027
\ No newline at end of file @@ -53,7 +53,7 @@ The Simple language is styled after a subset of C or Java. * [Chapter 9](docs/chapter09/README.md): Global Value Numbering. Iterative peepholes to fixpoint. Worklists. * [Chapter 10a](docs/chapter10a/README.md): User defined structs, pointers and null analysis. One memory value in SSA. Loads, stores, and an executable evaluator. -* Chapter 10b: Equivalence class aliasing. Lazy memory +* [Chapter 10b](docs/chapter10b/README.md): Equivalence class aliasing. Lazy memory partitioning with `MemMerge`, `MemPhi`, and `BulkMemPhi`. * Chapter 11: Global Code Motion - Scheduling. * Chapter 12: Float type. diff --git a/chapter10a.iml b/chapter10b.iml index 3f930463..9d1eeeb2 100644 --- a/chapter10a.iml +++ b/chapter10b.iml @@ -1,8 +1,8 @@ <?xml version="1.0" encoding="UTF-8"?> <module type="JAVA_MODULE" version="4"> <component name="NewModuleRootManager" inherit-compiler-output="false"> - <output url="file://$MODULE_DIR$/../build/idea/production/chapter10a" /> - <output-test url="file://$MODULE_DIR$/../build/idea/test/chapter10a" /> + <output url="file://$MODULE_DIR$/../build/idea/production/chapter10b" /> + <output-test url="file://$MODULE_DIR$/../build/idea/test/chapter10b" /> <exclude-output /> <content url="file://$MODULE_DIR$"> <sourceFolder url="file://$MODULE_DIR$/src/main/java" isTestSource="false" /> diff --git a/docs/chapter10b/10-grammar.md b/docs/chapter10b/10-grammar.md new file mode 100644 index 00000000..9a80d6ea --- /dev/null +++ b/docs/chapter10b/10-grammar.md @@ -0,0 +1,125 @@ +# Grammar for Chapter 10b + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | structDeclaration + | declStatement + | blockStatment + | expressionStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatment + ; + +field + : 'int' IDENTIFIER ';' + ; + +fields + : field+ + ; + +structDeclaration + : 'struct' IDENTIFIER '{' fields '}' + ; + +whileStatement + : 'while' '(' expression ')' statement + ; + +breakStatement + : 'break' ';' + ; + +continueStatement + : 'continue' ';' + ; + +ifStatement + : 'if' '(' expression ')' statement ('else' statement)? + ; + + +expressionStatement + : IDENTIFIER '=' expression ';' + | fieldExpression '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +structName + : IDENTIFIER + ; + +declStatement + : 'int' IDENTIFIER '=' expression ';' + | structName ('?')? IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : comparisonExpression + ; + +comparisonExpression + : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | '!' unaryExpression + | primaryExpression + ; + +newExpression + : 'new' IDENTIFIER + ; + +fieldExpression + : primaryExpresson '.' IDENTIFIER + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | 'true' + | 'false' + | 'null' + | newExpression + | '(' expression ')' + | fieldExpression + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +``` diff --git a/docs/chapter10b/Makefile b/docs/chapter10b/Makefile new file mode 100644 index 00000000..055882b2 --- /dev/null +++ b/docs/chapter10b/Makefile @@ -0,0 +1,14 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) +.DELETE_ON_ERROR: + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + @sed -i 's/\r$$//' $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/docs/chapter10b/README.md b/docs/chapter10b/README.md new file mode 100644 index 00000000..69f13335 --- /dev/null +++ b/docs/chapter10b/README.md @@ -0,0 +1,190 @@ +# Chapter 10b: Splitting Memory + +[Previous: Chapter 10a](../chapter10a/README.md) | +[Next: Chapter 11](../chapter11/README.md) + +Chapter 10a made memory effects explicit with one SSA memory value. This +chapter keeps exactly that parser model and recovers independent memory chains +through graph rewrites. There is no new language syntax; the +[grammar](10-grammar.md), pointer types, and null checks are unchanged. + +## Why split memory? + +```java +struct Point { int x; int y; } +Point p = new Point; +p.x = 42; +while (arg > 0) { + p.y = p.y + arg; + arg = arg - 1; +} +return p.x; +``` + +The loop changes `y`, so it cannot affect `x`. With one memory chain the load +of `x` follows the loop's stores. Splitting the fields lets ordinary +load-after-store forwarding turn the return value into 42. + + + +These are schematic dependency graphs, with arrows from uses to their definitions. +In horizontal diagrams, definitions appear on the left and uses on the right; +in vertical diagrams, definitions appear above uses. +Control, pointer, and value edges are omitted when they do not explain memory. + +## Equivalence-class aliasing + +Each struct field has an integer alias identity. Two different fields receive +different identities, even if they have the same spelling in different structs. +Two instances of the same struct share their field aliases. Thus different +classes never alias; accesses in the same class **may alias**. Same-class does +not mean same-address: forwarding still checks pointer identity. + +The parser assigns field identities at struct declarations, beginning at 2. +These identities are independent of Start's output indices. The default slot +of a memory aggregate is 1; precise slots are greater than 1. + +We do not allocate a Start projection, scope binding, or loop Phi for every +declared field. Start supplies one memory value, Scope holds one `$mem` binding, +and Return consumes one complete memory value. The optimizer introduces slices +only where graph operations require them. + +## Three memory nodes + +| Node | Meaning | +|---|---| +| `MemMerge` | A complete memory state: a default plus precise alias overrides | +| `MemPhi` | One alias selected according to the incoming control path | +| `BulkMemPhi` | All aliases except an explicit exclusion set, selected by control | + +`MemMerge` combines independent pieces of memory at one program point. It is +not a control-flow merge. For example, after storing to alias `x`: + +```text +prior = current memory +store = Store_x(prior, pointer, value) +current memory = MemMerge(default=prior, x=store) +``` + +The Store selects its precise input from any incoming MemMerge. Loads and +precise memory Phis do the same. A missing precise entry falls back to the +default, provided that default still covers the requested alias. + +The explicit entries override the default: the semantic slices are disjoint, +and their union covers all memory. Flattening stacked aggregates preserves +entries that the outer aggregate has not replaced. This allows an `x` store +and a later `y` store to remain visible together at Return. + + + +## Splitting a memory Phi + +Scope initially creates a BulkMemPhi wherever the ordinary SSA algorithm needs +to merge memory. Its empty exclusion set means that it covers every alias. +After the Region is complete, the Phi inspects its memory inputs and users. +When they require a precise alias, it splits out that alias: + +```text +BulkPhi(R, left, right) + becomes +MemMerge( + default = BulkPhi_except{x}(R, left, right), + x = MemPhi_x(R, slice(left,x), slice(right,x))) +``` + +The new precise Phi and the remaining bulk Phi share a Region and matching +control-path indices. A loop uses the same transformation, with the backedge +among those inputs. Each further split preserves all previously extracted +slices; replacing a bulk Phi must never drop their parallel precise Phis. + + + +A bulk Phi can bypass an incoming aggregate only when all of that aggregate's +explicit slices are already excluded from the Phi. A precise consumer can +select one entry. A whole-memory consumer cannot just select the default: +that would lose the explicit updates. + +## Types and the worklist + +The type lattice retains Chapter 10a's six domains, colors, and notation: +`⊤` means top, `⊥` means bottom, and a suffix names the domain. The other five +domains are unchanged; memory now adds a flat element `MEM#N` for each precise +alias between memory top (`TypeMem.TOP`) and memory bottom (`TypeMem.BOT`). + + + +The parallel `MEM#2`, `MEM#3`, and further alias elements describe independent +field slices. For the first `Point` declaration above, these two aliases identify +`Point.x` and `Point.y`. Meeting different aliases gives memory bottom; joining +them gives memory top. Each precise alias is its own dual. The ellipsis stands +for more parallel aliases, not a type representing a set of aliases. + +Memory bottom covers all memory. The default aggregate slot numbered 1 is a +graph input position, not a precise field alias in this diagram. Types do not +track field values, private objects, or escape information. Bulk exclusion sets +and the default-plus-overrides structure of MemMerge belong to graph nodes, +not to an expanded type lattice. As in Chapter 10a, diagram edges show lattice +order, with top above bottom; field and tuple-element type lattices are elided. + +Scalar Phis remain ordinary PhiNodes. The scope's Phi factory chooses a +BulkMemPhi for whole memory; splitting constructs MemPhis explicitly. Generic +arithmetic factoring through Phis must not factor a memory aggregate. + +Memory splitting can increase node count. Progress comes from extracting an +alias from a bulk Phi and simplifying its precise chain, rather than from +requiring every rewrite to shrink the graph. Nodes must have conservative +initial types before introducing cyclic inputs. New bulk and precise Phis are +queued, so a recursive peephole cannot start another split halfway through the +first one. + +This also extends the worklist lesson from Chapter 9. A bulk Phi inspects its +users, so changes to a user's partition must wake the producer. Selecting a +slice from an aggregate can expose a new bulk-Phi user; that selected definition +must be queued too. The optimizer's worklist completeness assertion remains +enabled and checks these dependencies. + +## Evaluation and ordering + +MemMerge is a dependency node; it emits no heap operation. Its evaluator result +is a memory token, while Store mutates the object's fields. The scheduler must +distinguish aggregation from overwriting memory. A MemMerge is not a clobber, +and stores in different alias classes do not impose load/store anti-dependencies. + + + +Tests cover independent-field folding, parallel memory Phis, multiple field +updates surviving at Return, early returns, nested loops with break/continue, +and reads before subsequent stores through potentially aliased pointers. + +## What remains for later chapters? + +Chapter 10b knows every access's alias while parsing. What is lazy here is the +construction of memory partitions. Chapter 25 also allows an existing access's +alias to become known later, using the same representation. Its private +constructor memory, escape tracking, incomplete types, and module alias +remapping are separate extensions and are not needed here. + +Chapters 11-24 currently retain their older parser-managed memory chains. +Forwarding this representation through those snapshots is tracked in the +[backport queue](../chapter-backports.md). Chapter 11's scheduling lesson +therefore still shows the older graph construction, with the same language. + +## Build and test + +With JDK 21 or newer, from this directory: + +```sh +make lib +make tests +make release +make view +``` + +Make builds this complete snapshot without Maven. `make release` writes +`build/release/simple.jar`; `make view` launches the shared graph viewer. +Both the root Maven reactor and the supplied IDEA module descriptor include +the chapter. From the repository root, test both halves with: + +```sh +make tests CHAPTERS="chapter10a chapter10b" +``` diff --git a/docs/chapter10b/example1.gv b/docs/chapter10b/example1.gv new file mode 100644 index 00000000..0b0a5feb --- /dev/null +++ b/docs/chapter10b/example1.gv @@ -0,0 +1,13 @@ +digraph Memory { + rankdir=BT; + node [shape=box]; + M [label="Initial memory"]; + X [label="Store x = 42"]; + Y [label="Loop: Store y"]; + L [label="Load x (42)"]; + L -> X -> M [color=blue]; Y -> M [color=green]; + MemMerge -> X [color=blue]; MemMerge -> Y [color=green]; + Return -> MemMerge; Return -> L; + { rank=same; MemMerge -> L [style=invis]; } + Y -> X [style=invis]; // Layout only: keep the stores in code order. +} diff --git a/docs/chapter10b/example1.svg b/docs/chapter10b/example1.svg new file mode 100644 index 00000000..384b6e12 --- /dev/null +++ b/docs/chapter10b/example1.svg @@ -0,0 +1,93 @@ +<?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: Memory Pages: 1 --> +<svg width="206pt" height="332pt" + viewBox="0.00 0.00 205.75 332.00" 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 328)"> +<title>Memory</title> +<polygon fill="white" stroke="none" points="-4,4 -4,-328 201.75,-328 201.75,4 -4,4"/> +<!-- M --> +<g id="node1" class="node"> +<title>M</title> +<polygon fill="none" stroke="black" points="131.75,-324 33.25,-324 33.25,-288 131.75,-288 131.75,-324"/> +<text text-anchor="middle" x="82.5" y="-300.95" font-family="Times New Roman,serif" font-size="14.00">Initial memory</text> +</g> +<!-- X --> +<g id="node2" class="node"> +<title>X</title> +<polygon fill="none" stroke="black" points="160.62,-252 76.38,-252 76.38,-216 160.62,-216 160.62,-252"/> +<text text-anchor="middle" x="118.5" y="-228.95" font-family="Times New Roman,serif" font-size="14.00">Store x = 42</text> +</g> +<!-- X->M --> +<g id="edge2" class="edge"> +<title>X->M</title> +<path fill="none" stroke="blue" d="M109.6,-252.3C105.63,-260.02 100.87,-269.29 96.44,-277.89"/> +<polygon fill="blue" stroke="blue" points="93.45,-276.06 91.99,-286.55 99.67,-279.26 93.45,-276.06"/> +</g> +<!-- Y --> +<g id="node3" class="node"> +<title>Y</title> +<polygon fill="none" stroke="black" points="91,-180 0,-180 0,-144 91,-144 91,-180"/> +<text text-anchor="middle" x="45.5" y="-156.95" font-family="Times New Roman,serif" font-size="14.00">Loop: Store y</text> +</g> +<!-- Y->M --> +<g id="edge3" class="edge"> +<title>Y->M</title> +<path fill="none" stroke="green" d="M49.63,-180.44C53.93,-198.41 60.94,-227.23 67.5,-252 69.64,-260.07 72.07,-268.81 74.33,-276.81"/> +<polygon fill="green" stroke="green" points="70.96,-277.75 77.07,-286.4 77.69,-275.82 70.96,-277.75"/> +</g> +<!-- Y->X --> +<!-- L --> +<g id="node4" class="node"> +<title>L</title> +<polygon fill="none" stroke="black" points="197.75,-108 117.25,-108 117.25,-72 197.75,-72 197.75,-108"/> +<text text-anchor="middle" x="157.5" y="-84.95" font-family="Times New Roman,serif" font-size="14.00">Load x (42)</text> +</g> +<!-- L->X --> +<g id="edge1" class="edge"> +<title>L->X</title> +<path fill="none" stroke="blue" d="M152.87,-108.41C148.09,-126.37 140.36,-155.17 133.5,-180 131.28,-188.05 128.82,-196.78 126.56,-204.78"/> +<polygon fill="blue" stroke="blue" points="123.2,-203.8 123.83,-214.37 129.93,-205.71 123.2,-203.8"/> +</g> +<!-- MemMerge --> +<g id="node5" class="node"> +<title>MemMerge</title> +<polygon fill="none" stroke="black" points="99.5,-108 17.5,-108 17.5,-72 99.5,-72 99.5,-108"/> +<text text-anchor="middle" x="58.5" y="-84.95" font-family="Times New Roman,serif" font-size="14.00">MemMerge</text> +</g> +<!-- MemMerge->X --> +<g id="edge4" class="edge"> +<title>MemMerge->X</title> +<path fill="none" stroke="blue" d="M75.59,-108.21C84.32,-117.95 94.37,-130.8 100.5,-144 109.34,-163.03 113.85,-186.32 116.15,-204.31"/> +<polygon fill="blue" stroke="blue" points="112.64,-204.46 117.22,-214.02 119.6,-203.7 112.64,-204.46"/> +</g> +<!-- MemMerge->Y --> +<g id="edge5" class="edge"> +<title>MemMerge->Y</title> +<path fill="none" stroke="green" d="M55.29,-108.3C53.92,-115.68 52.28,-124.48 50.75,-132.75"/> +<polygon fill="green" stroke="green" points="47.34,-131.94 48.95,-142.41 54.22,-133.21 47.34,-131.94"/> +</g> +<!-- MemMerge->L --> +<!-- Return --> +<g id="node6" class="node"> +<title>Return</title> +<polygon fill="none" stroke="black" points="134.5,-36 80.5,-36 80.5,0 134.5,0 134.5,-36"/> +<text text-anchor="middle" x="107.5" y="-12.95" font-family="Times New Roman,serif" font-size="14.00">Return</text> +</g> +<!-- Return->L --> +<g id="edge7" class="edge"> +<title>Return->L</title> +<path fill="none" stroke="black" d="M119.86,-36.3C125.55,-44.27 132.43,-53.9 138.74,-62.74"/> +<polygon fill="black" stroke="black" points="135.74,-64.56 144.4,-70.66 141.44,-60.49 135.74,-64.56"/> +</g> +<!-- Return->MemMerge --> +<g id="edge6" class="edge"> +<title>Return->MemMerge</title> +<path fill="none" stroke="black" d="M95.39,-36.3C89.81,-44.27 83.07,-53.9 76.88,-62.74"/> +<polygon fill="black" stroke="black" points="74.21,-60.46 71.34,-70.66 79.94,-64.47 74.21,-60.46"/> +</g> +</g> +</svg> diff --git a/docs/chapter10b/example2a.gv b/docs/chapter10b/example2a.gv new file mode 100644 index 00000000..d92eea41 --- /dev/null +++ b/docs/chapter10b/example2a.gv @@ -0,0 +1,10 @@ +digraph Memory { + rankdir=RL; + node [shape=box]; + M [label="Default memory"]; + X [label="Store x"]; + Y [label="Store y"]; + X -> M [color=blue]; Y -> M [color=green]; + MemMerge -> M [label="default"]; MemMerge -> X [label="x",color=blue]; + MemMerge -> Y [label="y",color=green]; Return -> MemMerge; +} diff --git a/docs/chapter10b/example2a.svg b/docs/chapter10b/example2a.svg new file mode 100644 index 00000000..97fb144e --- /dev/null +++ b/docs/chapter10b/example2a.svg @@ -0,0 +1,82 @@ +<?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: Memory Pages: 1 --> +<svg width="423pt" height="126pt" + viewBox="0.00 0.00 422.50 125.93" 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 121.93)"> +<title>Memory</title> +<polygon fill="white" stroke="none" points="-4,4 -4,-121.93 418.5,-121.93 418.5,4 -4,4"/> +<!-- M --> +<g id="node1" class="node"> +<title>M</title> +<polygon fill="none" stroke="black" points="106.75,-90 0,-90 0,-54 106.75,-54 106.75,-90"/> +<text text-anchor="middle" x="53.38" y="-66.95" font-family="Times New Roman,serif" font-size="14.00">Default memory</text> +</g> +<!-- X --> +<g id="node2" class="node"> +<title>X</title> +<polygon fill="none" stroke="black" points="198.75,-90 143.75,-90 143.75,-54 198.75,-54 198.75,-90"/> +<text text-anchor="middle" x="171.25" y="-66.95" font-family="Times New Roman,serif" font-size="14.00">Store x</text> +</g> +<!-- X->M --> +<g id="edge1" class="edge"> +<title>X->M</title> +<path fill="none" stroke="blue" d="M143.37,-72C135.84,-72 127.32,-72 118.6,-72"/> +<polygon fill="blue" stroke="blue" points="118.61,-68.5 108.61,-72 118.61,-75.5 118.61,-68.5"/> +</g> +<!-- Y --> +<g id="node3" class="node"> +<title>Y</title> +<polygon fill="none" stroke="black" points="198.75,-36 143.75,-36 143.75,0 198.75,0 198.75,-36"/> +<text text-anchor="middle" x="171.25" y="-12.95" font-family="Times New Roman,serif" font-size="14.00">Store y</text> +</g> +<!-- Y->M --> +<g id="edge2" class="edge"> +<title>Y->M</title> +<path fill="none" stroke="green" d="M143.37,-30.52C131.65,-35.99 117.53,-42.57 104.01,-48.87"/> +<polygon fill="green" stroke="green" points="102.81,-45.57 95.22,-52.97 105.76,-51.91 102.81,-45.57"/> +</g> +<!-- MemMerge --> +<g id="node4" class="node"> +<title>MemMerge</title> +<polygon fill="none" stroke="black" points="323.5,-90 241.5,-90 241.5,-54 323.5,-54 323.5,-90"/> +<text text-anchor="middle" x="282.5" y="-66.95" font-family="Times New Roman,serif" font-size="14.00">MemMerge</text> +</g> +<!-- MemMerge->M --> +<g id="edge3" class="edge"> +<title>MemMerge->M</title> +<path fill="none" stroke="black" d="M241.39,-88.58C228.08,-93.14 213,-97.3 198.75,-99 174.48,-101.9 167.93,-102.57 143.75,-99 135.07,-97.72 126.06,-95.77 117.26,-93.5"/> +<polygon fill="black" stroke="black" points="118.28,-90.15 107.71,-90.87 116.42,-96.9 118.28,-90.15"/> +<text text-anchor="middle" x="171.25" y="-104.63" font-family="Times New Roman,serif" font-size="14.00">default</text> +</g> +<!-- MemMerge->X --> +<g id="edge4" class="edge"> +<title>MemMerge->X</title> +<path fill="none" stroke="blue" d="M241.13,-72C231.08,-72 220.34,-72 210.4,-72"/> +<polygon fill="blue" stroke="blue" points="210.71,-68.5 200.71,-72 210.71,-75.5 210.71,-68.5"/> +<text text-anchor="middle" x="220.12" y="-75.2" font-family="Times New Roman,serif" font-size="14.00">x</text> +</g> +<!-- MemMerge->Y --> +<g id="edge5" class="edge"> +<title>MemMerge->Y</title> +<path fill="none" stroke="green" d="M244.21,-53.57C232.85,-47.95 220.38,-41.79 209.05,-36.19"/> +<polygon fill="green" stroke="green" points="210.91,-33.2 200.39,-31.91 207.81,-39.48 210.91,-33.2"/> +<text text-anchor="middle" x="220.12" y="-44.97" font-family="Times New Roman,serif" font-size="14.00">y</text> +</g> +<!-- Return --> +<g id="node5" class="node"> +<title>Return</title> +<polygon fill="none" stroke="black" points="414.5,-90 360.5,-90 360.5,-54 414.5,-54 414.5,-90"/> +<text text-anchor="middle" x="387.5" y="-66.95" font-family="Times New Roman,serif" font-size="14.00">Return</text> +</g> +<!-- Return->MemMerge --> +<g id="edge6" class="edge"> +<title>Return->MemMerge</title> +<path fill="none" stroke="black" d="M360.24,-72C352.53,-72 343.82,-72 335.11,-72"/> +<polygon fill="black" stroke="black" points="335.25,-68.5 325.25,-72 335.25,-75.5 335.25,-68.5"/> +</g> +</g> +</svg> diff --git a/docs/chapter10b/example2b.gv b/docs/chapter10b/example2b.gv new file mode 100644 index 00000000..4ddd36b5 --- /dev/null +++ b/docs/chapter10b/example2b.gv @@ -0,0 +1,10 @@ +digraph Memory { + rankdir=RL; + node [shape=box]; + P [label="MemPhi(x)"]; + B [label="BulkMemPhi(All except x)"]; + P -> Left [label="slice x",color=blue]; P -> Right [label="slice x",color=blue]; + B -> Left; B -> Right; + P -> Region [style=dashed]; B -> Region [style=dashed]; + MemMerge -> P [label="x",color=blue]; MemMerge -> B [label="default"]; +} diff --git a/docs/chapter10b/example2b.svg b/docs/chapter10b/example2b.svg new file mode 100644 index 00000000..4e0616f1 --- /dev/null +++ b/docs/chapter10b/example2b.svg @@ -0,0 +1,101 @@ +<?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: Memory Pages: 1 --> +<svg width="456pt" height="170pt" + viewBox="0.00 0.00 455.75 170.00" 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 166)"> +<title>Memory</title> +<polygon fill="white" stroke="none" points="-4,4 -4,-166 451.75,-166 451.75,4 -4,4"/> +<!-- P --> +<g id="node1" class="node"> +<title>P</title> +<polygon fill="none" stroke="black" points="249.12,-67 169.38,-67 169.38,-31 249.12,-31 249.12,-67"/> +<text text-anchor="middle" x="209.25" y="-43.95" font-family="Times New Roman,serif" font-size="14.00">MemPhi(x)</text> +</g> +<!-- Left --> +<g id="node3" class="node"> +<title>Left</title> +<polygon fill="none" stroke="black" points="54.5,-102 0.5,-102 0.5,-66 54.5,-66 54.5,-102"/> +<text text-anchor="middle" x="27.5" y="-78.95" font-family="Times New Roman,serif" font-size="14.00">Left</text> +</g> +<!-- P->Left --> +<g id="edge1" class="edge"> +<title>P->Left</title> +<path fill="none" stroke="blue" d="M169.09,-45.11C141.55,-43.68 104.19,-44.4 73,-54.5 68.76,-55.87 64.54,-57.77 60.48,-59.95"/> +<polygon fill="blue" stroke="blue" points="58.85,-56.85 52.11,-65.02 62.48,-62.84 58.85,-56.85"/> +<text text-anchor="middle" x="90.62" y="-57.7" font-family="Times New Roman,serif" font-size="14.00">slice x</text> +</g> +<!-- Right --> +<g id="node4" class="node"> +<title>Right</title> +<polygon fill="none" stroke="black" points="54.5,-162 0.5,-162 0.5,-126 54.5,-126 54.5,-162"/> +<text text-anchor="middle" x="27.5" y="-138.95" font-family="Times New Roman,serif" font-size="14.00">Right</text> +</g> +<!-- P->Right --> +<g id="edge2" class="edge"> +<title>P->Right</title> +<path fill="none" stroke="blue" d="M168.93,-64.2C141.32,-75.51 103.94,-92.12 73,-110.5 68.67,-113.07 64.27,-115.98 59.99,-118.98"/> +<polygon fill="blue" stroke="blue" points="58.15,-115.99 52.15,-124.72 62.29,-121.64 58.15,-115.99"/> +<text text-anchor="middle" x="90.62" y="-113.7" font-family="Times New Roman,serif" font-size="14.00">slice x</text> +</g> +<!-- Region --> +<g id="node5" class="node"> +<title>Region</title> +<polygon fill="none" stroke="black" points="55,-36 0,-36 0,0 55,0 55,-36"/> +<text text-anchor="middle" x="27.5" y="-12.95" font-family="Times New Roman,serif" font-size="14.00">Region</text> +</g> +<!-- P->Region --> +<g id="edge5" class="edge"> +<title>P->Region</title> +<path fill="none" stroke="black" stroke-dasharray="5,2" d="M171.76,-30.51C153.24,-22.15 130.1,-13.21 108.25,-9 94.7,-6.39 79.71,-7.15 66.41,-9.05"/> +<polygon fill="black" stroke="black" points="66,-5.57 56.73,-10.71 67.18,-12.47 66,-5.57"/> +</g> +<!-- B --> +<g id="node2" class="node"> +<title>B</title> +<polygon fill="none" stroke="black" points="292.25,-132 126.25,-132 126.25,-96 292.25,-96 292.25,-132"/> +<text text-anchor="middle" x="209.25" y="-108.95" font-family="Times New Roman,serif" font-size="14.00">BulkMemPhi(All except x)</text> +</g> +<!-- B->Left --> +<g id="edge3" class="edge"> +<title>B->Left</title> +<path fill="none" stroke="black" d="M126.03,-119C108.27,-118.2 89.8,-115.9 73,-111 69.91,-110.1 66.82,-108.93 63.78,-107.57"/> +<polygon fill="black" stroke="black" points="65.62,-104.58 55.13,-103.12 62.42,-110.81 65.62,-104.58"/> +</g> +<!-- B->Right --> +<g id="edge4" class="edge"> +<title>B->Right</title> +<path fill="none" stroke="black" d="M126,-127.73C104.92,-131.25 83.28,-134.86 65.75,-137.78"/> +<polygon fill="black" stroke="black" points="65.66,-134.25 56.37,-139.35 66.81,-141.15 65.66,-134.25"/> +</g> +<!-- B->Region --> +<g id="edge6" class="edge"> +<title>B->Region</title> +<path fill="none" stroke="black" stroke-dasharray="5,2" d="M167.07,-95.69C153.92,-89.64 139.38,-82.73 126.25,-76 102.07,-63.61 96.34,-59.9 73,-46 70.37,-44.43 67.67,-42.8 64.95,-41.14"/> +<polygon fill="black" stroke="black" points="66.83,-38.18 56.48,-35.89 63.14,-44.13 66.83,-38.18"/> +</g> +<!-- MemMerge --> +<g id="node6" class="node"> +<title>MemMerge</title> +<polygon fill="none" stroke="black" points="447.75,-94 365.75,-94 365.75,-58 447.75,-58 447.75,-94"/> +<text text-anchor="middle" x="406.75" y="-70.95" font-family="Times New Roman,serif" font-size="14.00">MemMerge</text> +</g> +<!-- MemMerge->P --> +<g id="edge7" class="edge"> +<title>MemMerge->P</title> +<path fill="none" stroke="blue" d="M365.39,-64.23C359.51,-62.81 353.5,-61.5 347.75,-60.5 319.17,-55.53 286.87,-52.69 260.76,-51.07"/> +<polygon fill="blue" stroke="blue" points="261.3,-47.6 251.11,-50.52 260.9,-54.59 261.3,-47.6"/> +<text text-anchor="middle" x="329" y="-63.7" font-family="Times New Roman,serif" font-size="14.00">x</text> +</g> +<!-- MemMerge->B --> +<g id="edge8" class="edge"> +<title>MemMerge->B</title> +<path fill="none" stroke="black" d="M365.72,-83.78C347.65,-87.29 325.5,-91.6 303.63,-95.85"/> +<polygon fill="black" stroke="black" points="303.23,-92.36 294.08,-97.71 304.56,-99.23 303.23,-92.36"/> +<text text-anchor="middle" x="329" y="-97.06" font-family="Times New Roman,serif" font-size="14.00">default</text> +</g> +</g> +</svg> diff --git a/docs/chapter10b/example2c.gv b/docs/chapter10b/example2c.gv new file mode 100644 index 00000000..4fae3bba --- /dev/null +++ b/docs/chapter10b/example2c.gv @@ -0,0 +1,10 @@ +digraph Memory { + rankdir=RL; + node [shape=box]; + M [label="Prior x memory"]; + L [label="Load p.x"]; + S [label="Store p.x"]; + L -> M [color=blue]; S -> M [color=blue]; + S -> L [style=dashed,label="execute load first"]; + Y [label="Store p.y: independent"]; +} diff --git a/docs/chapter10b/example2c.svg b/docs/chapter10b/example2c.svg new file mode 100644 index 00000000..8249d677 --- /dev/null +++ b/docs/chapter10b/example2c.svg @@ -0,0 +1,56 @@ +<?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: Memory Pages: 1 --> +<svg width="482pt" height="121pt" + viewBox="0.00 0.00 482.25 121.00" 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 117)"> +<title>Memory</title> +<polygon fill="white" stroke="none" points="-4,4 -4,-117 478.25,-117 478.25,4 -4,4"/> +<!-- M --> +<g id="node1" class="node"> +<title>M</title> +<polygon fill="none" stroke="black" points="103.75,-59 0,-59 0,-23 103.75,-23 103.75,-59"/> +<text text-anchor="middle" x="51.88" y="-35.95" font-family="Times New Roman,serif" font-size="14.00">Prior x memory</text> +</g> +<!-- L --> +<g id="node2" class="node"> +<title>L</title> +<polygon fill="none" stroke="black" points="205.5,-36 140.75,-36 140.75,0 205.5,0 205.5,-36"/> +<text text-anchor="middle" x="173.12" y="-12.95" font-family="Times New Roman,serif" font-size="14.00">Load p.x</text> +</g> +<!-- L->M --> +<g id="edge1" class="edge"> +<title>L->M</title> +<path fill="none" stroke="blue" d="M140.48,-24.1C132.62,-25.62 123.92,-27.3 115.15,-28.99"/> +<polygon fill="blue" stroke="blue" points="114.69,-25.51 105.54,-30.84 116.02,-32.39 114.69,-25.51"/> +</g> +<!-- S --> +<g id="node3" class="node"> +<title>S</title> +<polygon fill="none" stroke="black" points="437.5,-59 372,-59 372,-23 437.5,-23 437.5,-59"/> +<text text-anchor="middle" x="404.75" y="-35.95" font-family="Times New Roman,serif" font-size="14.00">Store p.x</text> +</g> +<!-- S->M --> +<g id="edge2" class="edge"> +<title>S->M</title> +<path fill="none" stroke="blue" d="M371.77,-45.13C355.48,-47.03 335.34,-49.06 317.25,-50 248.24,-53.58 169.03,-49.84 115.44,-46.15"/> +<polygon fill="blue" stroke="blue" points="115.81,-42.67 105.58,-45.45 115.31,-49.65 115.81,-42.67"/> +</g> +<!-- S->L --> +<g id="edge3" class="edge"> +<title>S->L</title> +<path fill="none" stroke="black" stroke-dasharray="5,2" d="M371.82,-37.8C331.55,-33.77 262.15,-26.82 217.21,-22.32"/> +<polygon fill="black" stroke="black" points="217.59,-18.84 207.29,-21.32 216.89,-25.8 217.59,-18.84"/> +<text text-anchor="middle" x="270.38" y="-35.44" font-family="Times New Roman,serif" font-size="14.00">execute load first</text> +</g> +<!-- Y --> +<g id="node4" class="node"> +<title>Y</title> +<polygon fill="none" stroke="black" points="474.25,-113 335.25,-113 335.25,-77 474.25,-77 474.25,-113"/> +<text text-anchor="middle" x="404.75" y="-89.95" font-family="Times New Roman,serif" font-size="14.00">Store p.y: independent</text> +</g> +</g> +</svg> diff --git a/docs/chapter10b/lattice.gv b/docs/chapter10b/lattice.gv new file mode 100644 index 00000000..f9fb2b09 --- /dev/null +++ b/docs/chapter10b/lattice.gv @@ -0,0 +1,114 @@ +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_pointer { + label="Pointer = nullability × struct type"; + fontname="Arial"; color="#cccccc"; + node [fillcolor="#008000", fontcolor=white]; + PTR_TOP [label="⊤:ptr\n[*⊤:struct]"]; + PTR_BOT [label="⊥:ptr\n[*⊥:struct?]"]; + PTR_NULL [label="null"]; + PTR_ANY [label="*⊥:struct\n[ptr any struct]"]; + PTR_PERSON [label="*Person"]; + PTR_S1 [label="*s1"]; + PTR_MORE [label="*s2, …"]; + PTR_PERSON_NIL [label="*Person?"]; + PTR_S1_NIL [label="*s1?"]; + PTR_MORE_NIL [label="*s2?, …"]; + {rank=same; PTR_PERSON; PTR_S1; PTR_MORE; PTR_NULL;} + {rank=same; PTR_ANY; PTR_PERSON_NIL; PTR_S1_NIL; PTR_MORE_NIL;} + PTR_PERSON -> PTR_S1 -> PTR_MORE -> PTR_NULL [style=invis]; + PTR_ANY -> PTR_PERSON_NIL -> PTR_S1_NIL -> PTR_MORE_NIL [style=invis]; + PTR_TOP -> {PTR_PERSON PTR_S1 PTR_MORE PTR_NULL}; + {PTR_PERSON PTR_S1 PTR_MORE} -> PTR_ANY; + PTR_PERSON -> PTR_PERSON_NIL; + PTR_S1 -> PTR_S1_NIL; + PTR_MORE -> PTR_MORE_NIL; + PTR_NULL -> {PTR_PERSON_NIL PTR_S1_NIL PTR_MORE_NIL}; + {PTR_ANY PTR_PERSON_NIL PTR_S1_NIL PTR_MORE_NIL} -> PTR_BOT; + } + + subgraph cluster_struct { + label="Struct\nnamed collection of named scalar types"; + fontname="Arial"; color="#cccccc"; + node [fillcolor="#90ee90"]; + STRUCT_TOP [label="⊤:struct\n[struct top]"]; + STRUCT_BOT [label="⊥:struct\n[struct bottom]"]; + STRUCT_PERSON [label="Person\nage: int", shape=box]; + STRUCT_S1 [label="s1\nx: int", shape=box]; + STRUCT_S2 [label="s2\nx: int, y: *s1", shape=box]; + STRUCT_MORE [label="…", shape=box]; + {rank=same; STRUCT_PERSON; STRUCT_S1; STRUCT_S2; STRUCT_MORE;} + STRUCT_PERSON -> STRUCT_S1 -> STRUCT_S2 -> STRUCT_MORE [style=invis]; + STRUCT_TOP -> {STRUCT_PERSON STRUCT_S1 STRUCT_S2 STRUCT_MORE}; + {STRUCT_PERSON STRUCT_S1 STRUCT_S2 STRUCT_MORE} -> STRUCT_BOT; + } + + subgraph cluster_memory { + label="Memory\nprecise alias slices"; fontname="Arial"; color="#cccccc"; + node [fillcolor="#00008b", fontcolor=white]; + MEM_TOP [label="⊤:mem"]; + MEM_BOT [label="⊥:mem"]; + MEM_ALIAS2 [label="MEM#2"]; + MEM_ALIAS3 [label="MEM#3"]; + MEM_MORE [label="…"]; + {rank=same; MEM_ALIAS2; MEM_ALIAS3; MEM_MORE;} + MEM_ALIAS2 -> MEM_ALIAS3 -> MEM_MORE [style=invis]; + MEM_TOP -> {MEM_ALIAS2 MEM_ALIAS3 MEM_MORE}; + {MEM_ALIAS2 MEM_ALIAS3 MEM_MORE} -> MEM_BOT; + } + + subgraph cluster_tuple { + label="Tuple\ncollection of types"; + fontname="Arial"; color="#cccccc"; + node [fillcolor="#ffc0cb"]; + TUPLE_TOP [label="⊤:tuple"]; + TUPLE_BOT [label="⊥:tuple"]; + TUPLE1 [label="(type)", shape=box]; + TUPLE2 [label="(type, type)", shape=box]; + TUPLEN [label="(type, …)", shape=box]; + {rank=same; TUPLE1; TUPLE2; TUPLEN;} + TUPLE1 -> TUPLE2 -> TUPLEN [style=invis]; + TUPLE_TOP -> {TUPLE1 TUPLE2 TUPLEN}; + {TUPLE1 TUPLE2 TUPLEN} -> TUPLE_BOT; + } + + TOP -> {XCTRL INT_TOP PTR_TOP STRUCT_TOP MEM_TOP TUPLE_TOP}; + {CTRL INT_BOT PTR_BOT STRUCT_BOT MEM_BOT TUPLE_BOT} -> BOT; + {rank=same; XCTRL; INT_TOP; PTR_TOP; STRUCT_TOP; MEM_TOP; TUPLE_TOP;} + {rank=same; CTRL; INT_BOT; PTR_BOT; STRUCT_BOT; MEM_BOT; TUPLE_BOT;} + XCTRL -> INT_TOP -> PTR_TOP -> STRUCT_TOP -> MEM_TOP -> TUPLE_TOP [style=invis]; +} diff --git a/docs/chapter10b/lattice.svg b/docs/chapter10b/lattice.svg new file mode 100644 index 00000000..a11452b9 --- /dev/null +++ b/docs/chapter10b/lattice.svg @@ -0,0 +1,620 @@ +<?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="1827pt" height="533pt" + viewBox="0.00 0.00 1827.00 533.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 529.45)"> +<title>Lattice</title> +<polygon fill="white" stroke="none" points="-4,4 -4,-529.45 1823,-529.45 1823,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_control</title> +<polygon fill="none" stroke="#cccccc" points="8,-85.99 8,-454.71 98,-454.71 98,-85.99 8,-85.99"/> +<text text-anchor="middle" x="53" y="-437.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,-454.71 404,-454.71 404,-85.99 106,-85.99"/> +<text text-anchor="middle" x="255" y="-437.41" font-family="Arial" font-size="14.00">Integer</text> +</g> +<g id="clust6" class="cluster"> +<title>cluster_pointer</title> +<polygon fill="none" stroke="#cccccc" points="412,-75 412,-465.7 893,-465.7 893,-75 412,-75"/> +<text text-anchor="middle" x="652.5" y="-448.4" font-family="Arial" font-size="14.00">Pointer = nullability × struct type</text> +</g> +<g id="clust13" class="cluster"> +<title>cluster_struct</title> +<polygon fill="none" stroke="#cccccc" points="901,-75 901,-481.45 1237,-481.45 1237,-75 901,-75"/> +<text text-anchor="middle" x="1069" y="-464.15" font-family="Arial" font-size="14.00">Struct</text> +<text text-anchor="middle" x="1069" y="-448.4" font-family="Arial" font-size="14.00">named collection of named scalar types</text> +</g> +<g id="clust17" class="cluster"> +<title>cluster_memory</title> +<polygon fill="none" stroke="#cccccc" points="1245,-85.99 1245,-470.46 1527,-470.46 1527,-85.99 1245,-85.99"/> +<text text-anchor="middle" x="1386" y="-453.16" font-family="Arial" font-size="14.00">Memory</text> +<text text-anchor="middle" x="1386" y="-437.41" font-family="Arial" font-size="14.00">precise alias slices</text> +</g> +<g id="clust21" class="cluster"> +<title>cluster_tuple</title> +<polygon fill="none" stroke="#cccccc" points="1535,-85.99 1535,-470.46 1811,-470.46 1811,-85.99 1535,-85.99"/> +<text text-anchor="middle" x="1673" y="-453.16" font-family="Arial" font-size="14.00">Tuple</text> +<text text-anchor="middle" x="1673" y="-437.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="887" cy="-507.45" rx="27" ry="18"/> +<text text-anchor="middle" x="887" y="-503.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="-404.96" rx="36.51" ry="18"/> +<text text-anchor="middle" x="53" y="-400.86" font-family="DejaVu Sans" font-size="13.00">⊤:ctrl</text> +</g> +<!-- TOP->XCTRL --> +<g id="edge60" class="edge"> +<title>TOP->XCTRL</title> +<path fill="none" stroke="#555555" d="M859.92,-506.29C725.56,-505.4 135.66,-500.43 102,-481.45 82.17,-470.27 69.05,-447.37 61.41,-429.71"/> +<polygon fill="#555555" stroke="#555555" points="63.45,-429.15 59.23,-424.39 59.57,-430.74 63.45,-429.15"/> +</g> +<!-- INT_TOP --> +<g id="node5" class="node"> +<title>INT_TOP</title> +<ellipse fill="#add8e6" stroke="black" cx="353" cy="-404.96" rx="33.44" ry="18"/> +<text text-anchor="middle" x="353" y="-400.86" font-family="DejaVu Sans" font-size="13.00">⊤:int</text> +</g> +<!-- TOP->INT_TOP --> +<g id="edge61" class="edge"> +<title>TOP->INT_TOP</title> +<path fill="none" stroke="#555555" d="M859.8,-506.38C764.27,-505.97 447.72,-502.97 408,-481.45 387.23,-470.19 372.29,-447.31 363.27,-429.67"/> +<polygon fill="#555555" stroke="#555555" points="365.18,-428.79 360.66,-424.32 361.41,-430.63 365.18,-428.79"/> +</g> +<!-- PTR_TOP --> +<g id="node10" class="node"> +<title>PTR_TOP</title> +<ellipse fill="#008000" stroke="black" cx="715" cy="-404.96" rx="61.7" ry="28.99"/> +<text text-anchor="middle" x="715" y="-409.11" font-family="DejaVu Sans" font-size="13.00" fill="white">⊤:ptr</text> +<text text-anchor="middle" x="715" y="-392.61" font-family="DejaVu Sans" font-size="13.00" fill="white">[*⊤:struct]</text> +</g> +<!-- TOP->PTR_TOP --> +<g id="edge62" class="edge"> +<title>TOP->PTR_TOP</title> +<path fill="none" stroke="#555555" d="M867.27,-494.92C841.1,-479.63 794.17,-452.21 759.3,-431.84"/> +<polygon fill="#555555" stroke="#555555" points="760.48,-430.1 754.24,-428.88 758.36,-433.72 760.48,-430.1"/> +</g> +<!-- STRUCT_TOP --> +<g id="node20" class="node"> +<title>STRUCT_TOP</title> +<ellipse fill="#90ee90" stroke="black" cx="1020" cy="-404.96" rx="64.35" ry="28.99"/> +<text text-anchor="middle" x="1020" y="-409.11" font-family="DejaVu Sans" font-size="13.00">⊤:struct</text> +<text text-anchor="middle" x="1020" y="-392.61" font-family="DejaVu Sans" font-size="13.00">[struct top]</text> +</g> +<!-- TOP->STRUCT_TOP --> +<g id="edge63" class="edge"> +<title>TOP->STRUCT_TOP</title> +<path fill="none" stroke="#555555" d="M904.39,-493.31C923.88,-478.58 956.09,-454.25 981.56,-435"/> +<polygon fill="#555555" stroke="#555555" points="982.82,-436.68 986.34,-431.39 980.29,-433.33 982.82,-436.68"/> +</g> +<!-- MEM_TOP --> +<g id="node26" class="node"> +<title>MEM_TOP</title> +<ellipse fill="#00008b" stroke="black" cx="1351" cy="-404.96" rx="44.7" ry="18"/> +<text text-anchor="middle" x="1351" y="-400.86" font-family="DejaVu Sans" font-size="13.00" fill="white">⊤:mem</text> +</g> +<!-- TOP->MEM_TOP --> +<g id="edge64" class="edge"> +<title>TOP->MEM_TOP</title> +<path fill="none" stroke="#555555" d="M914.33,-506.36C986.5,-505.84 1180.8,-502.47 1241,-481.45 1274.58,-469.72 1307.45,-444.9 1328.39,-426.91"/> +<polygon fill="#555555" stroke="#555555" points="1329.69,-428.56 1332.83,-423.03 1326.93,-425.4 1329.69,-428.56"/> +</g> +<!-- TUPLE_TOP --> +<g id="node31" class="node"> +<title>TUPLE_TOP</title> +<ellipse fill="#ffc0cb" stroke="black" cx="1588" cy="-404.96" rx="44.7" ry="18"/> +<text text-anchor="middle" x="1588" y="-400.86" font-family="DejaVu Sans" font-size="13.00">⊤:tuple</text> +</g> +<!-- TOP->TUPLE_TOP --> +<g id="edge65" class="edge"> +<title>TOP->TUPLE_TOP</title> +<path fill="none" stroke="#555555" d="M914.36,-506.76C1030.08,-507.88 1475.84,-510.27 1531,-481.45 1552.39,-470.27 1568.01,-447.05 1577.43,-429.3"/> +<polygon fill="#555555" stroke="#555555" points="1579.08,-430.68 1579.93,-424.38 1575.34,-428.78 1579.08,-430.68"/> +</g> +<!-- BOT --> +<g id="node2" class="node"> +<title>BOT</title> +<ellipse fill="black" stroke="black" cx="884" cy="-18" rx="27" ry="18"/> +<text text-anchor="middle" x="884" 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,-386.63C53,-337.1 53,-194.83 53,-137.43"/> +<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="edge66" class="edge"> +<title>CTRL->BOT</title> +<path fill="none" stroke="#555555" d="M69.29,-95.39C78.22,-87.83 89.91,-79.45 102,-75 242.26,-23.4 717.31,-19.12 849.57,-18.95"/> +<polygon fill="#555555" stroke="#555555" points="849.19,-21.05 855.19,-18.94 849.18,-16.85 849.19,-21.05"/> +</g> +<!-- INT_NEG --> +<g id="node7" class="node"> +<title>INT_NEG</title> +<ellipse fill="#add8e6" stroke="black" cx="169" cy="-310.97" rx="55.45" ry="18"/> +<text text-anchor="middle" x="169" y="-306.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="M328.95,-391.93C297.31,-376.11 241.45,-348.19 204.83,-329.88"/> +<polygon fill="#555555" stroke="#555555" points="205.88,-328.06 199.58,-327.25 204,-331.81 205.88,-328.06"/> +</g> +<!-- INT_ZERO --> +<g id="node8" class="node"> +<title>INT_ZERO</title> +<ellipse fill="#add8e6" stroke="black" cx="267" cy="-310.97" rx="27" ry="18"/> +<text text-anchor="middle" x="267" y="-306.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="M338.41,-388.35C323.94,-372.88 301.71,-349.1 285.9,-332.18"/> +<polygon fill="#555555" stroke="#555555" points="287.47,-330.79 281.84,-327.84 284.4,-333.66 287.47,-330.79"/> +</g> +<!-- INT_POS --> +<g id="node9" class="node"> +<title>INT_POS</title> +<ellipse fill="#add8e6" stroke="black" cx="353" cy="-310.97" rx="43.16" ry="18"/> +<text text-anchor="middle" x="353" y="-306.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,-386.65C353,-372.52 353,-352.37 353,-336.56"/> +<polygon fill="#555555" stroke="#555555" points="355.1,-336.7 353,-330.7 350.9,-336.7 355.1,-336.7"/> +</g> +<!-- INT_TOP->PTR_TOP --> +<!-- INT_BOT --> +<g id="node6" class="node"> +<title>INT_BOT</title> +<ellipse fill="#add8e6" stroke="black" cx="289" cy="-111.99" rx="33.44" ry="18"/> +<text text-anchor="middle" x="289" y="-107.89" font-family="DejaVu Sans" font-size="13.00">⊥:int</text> +</g> +<!-- INT_BOT->BOT --> +<g id="edge67" class="edge"> +<title>INT_BOT->BOT</title> +<path fill="none" stroke="#555555" d="M316.06,-101.31C339.95,-93.13 375.88,-81.69 408,-75 571.35,-40.97 770.86,-25.89 849.65,-20.95"/> +<polygon fill="#555555" stroke="#555555" points="849.52,-23.07 855.38,-20.6 849.26,-18.87 849.52,-23.07"/> +</g> +<!-- INT_NEG->INT_BOT --> +<g id="edge7" class="edge"> +<title>INT_NEG->INT_BOT</title> +<path fill="none" stroke="#555555" d="M179.44,-292.83C201.14,-257.2 251.13,-175.15 275.35,-135.4"/> +<polygon fill="#555555" stroke="#555555" points="276.89,-136.9 278.22,-130.68 273.31,-134.72 276.89,-136.9"/> +</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="M268.91,-292.83C272.82,-257.83 281.73,-178.04 286.26,-137.55"/> +<polygon fill="#555555" stroke="#555555" points="288.33,-137.93 286.91,-131.73 284.15,-137.46 288.33,-137.93"/> +</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="M347.43,-292.83C336.04,-257.76 310.03,-177.71 296.9,-137.29"/> +<polygon fill="#555555" stroke="#555555" points="298.92,-136.72 295.07,-131.67 294.92,-138.02 298.92,-136.72"/> +</g> +<!-- PTR_NULL --> +<g id="node12" class="node"> +<title>PTR_NULL</title> +<ellipse fill="#008000" stroke="black" cx="799" cy="-310.97" rx="27.3" ry="18"/> +<text text-anchor="middle" x="799" y="-306.87" font-family="DejaVu Sans" font-size="13.00" fill="white">null</text> +</g> +<!-- PTR_TOP->PTR_NULL --> +<g id="edge16" class="edge"> +<title>PTR_TOP->PTR_NULL</title> +<path fill="none" stroke="#555555" d="M738.85,-377.84C752,-363.43 768.1,-345.8 780.33,-332.41"/> +<polygon fill="#555555" stroke="#555555" points="781.8,-333.91 784.3,-328.06 778.7,-331.08 781.8,-333.91"/> +</g> +<!-- PTR_PERSON --> +<g id="node14" class="node"> +<title>PTR_PERSON</title> +<ellipse fill="#008000" stroke="black" cx="542" cy="-310.97" rx="45.72" ry="18"/> +<text text-anchor="middle" x="542" y="-306.87" font-family="DejaVu Sans" font-size="13.00" fill="white">*Person</text> +</g> +<!-- PTR_TOP->PTR_PERSON --> +<g id="edge17" class="edge"> +<title>PTR_TOP->PTR_PERSON</title> +<path fill="none" stroke="#555555" d="M674.88,-382.62C644.57,-366.5 603.47,-344.65 575.04,-329.54"/> +<polygon fill="#555555" stroke="#555555" points="576.08,-327.71 569.8,-326.75 574.11,-331.42 576.08,-327.71"/> +</g> +<!-- PTR_S1 --> +<g id="node15" class="node"> +<title>PTR_S1</title> +<ellipse fill="#008000" stroke="black" cx="631" cy="-310.97" rx="27" ry="18"/> +<text text-anchor="middle" x="631" y="-306.87" font-family="DejaVu Sans" font-size="13.00" fill="white">*s1</text> +</g> +<!-- PTR_TOP->PTR_S1 --> +<g id="edge18" class="edge"> +<title>PTR_TOP->PTR_S1</title> +<path fill="none" stroke="#555555" d="M691.15,-377.84C678,-363.43 661.9,-345.8 649.67,-332.41"/> +<polygon fill="#555555" stroke="#555555" points="651.3,-331.08 645.7,-328.06 648.2,-333.91 651.3,-331.08"/> +</g> +<!-- PTR_MORE --> +<g id="node16" class="node"> +<title>PTR_MORE</title> +<ellipse fill="#008000" stroke="black" cx="715" cy="-310.97" rx="40.6" ry="18"/> +<text text-anchor="middle" x="715" y="-306.87" font-family="DejaVu Sans" font-size="13.00" fill="white">*s2, …</text> +</g> +<!-- PTR_TOP->PTR_MORE --> +<g id="edge19" class="edge"> +<title>PTR_TOP->PTR_MORE</title> +<path fill="none" stroke="#555555" d="M715,-375.61C715,-363.22 715,-348.82 715,-336.86"/> +<polygon fill="#555555" stroke="#555555" points="717.1,-336.91 715,-330.91 712.9,-336.91 717.1,-336.91"/> +</g> +<!-- PTR_TOP->STRUCT_TOP --> +<!-- PTR_BOT --> +<g id="node11" class="node"> +<title>PTR_BOT</title> +<ellipse fill="#008000" stroke="black" cx="748" cy="-111.99" rx="66.47" ry="28.99"/> +<text text-anchor="middle" x="748" y="-116.14" font-family="DejaVu Sans" font-size="13.00" fill="white">⊥:ptr</text> +<text text-anchor="middle" x="748" y="-99.64" font-family="DejaVu Sans" font-size="13.00" fill="white">[*⊥:struct?]</text> +</g> +<!-- PTR_BOT->BOT --> +<g id="edge68" class="edge"> +<title>PTR_BOT->BOT</title> +<path fill="none" stroke="#555555" d="M783.38,-87.06C807.3,-70.88 838.29,-49.92 859.52,-35.56"/> +<polygon fill="#555555" stroke="#555555" points="860.46,-37.46 864.25,-32.36 858.1,-33.98 860.46,-37.46"/> +</g> +<!-- PTR_PERSON_NIL --> +<g id="node17" class="node"> +<title>PTR_PERSON_NIL</title> +<ellipse fill="#008000" stroke="black" cx="651" cy="-216.97" rx="50.33" ry="18"/> +<text text-anchor="middle" x="651" y="-212.87" font-family="DejaVu Sans" font-size="13.00" fill="white">*Person?</text> +</g> +<!-- PTR_NULL->PTR_PERSON_NIL --> +<g id="edge26" class="edge"> +<title>PTR_NULL->PTR_PERSON_NIL</title> +<path fill="none" stroke="#555555" d="M779.65,-297.94C754.63,-282.39 710.79,-255.14 681.32,-236.82"/> +<polygon fill="#555555" stroke="#555555" points="682.76,-235.24 676.55,-233.86 680.54,-238.81 682.76,-235.24"/> +</g> +<!-- PTR_S1_NIL --> +<g id="node18" class="node"> +<title>PTR_S1_NIL</title> +<ellipse fill="#008000" stroke="black" cx="748" cy="-216.97" rx="30.37" ry="18"/> +<text text-anchor="middle" x="748" y="-212.87" font-family="DejaVu Sans" font-size="13.00" fill="white">*s1?</text> +</g> +<!-- PTR_NULL->PTR_S1_NIL --> +<g id="edge27" class="edge"> +<title>PTR_NULL->PTR_S1_NIL</title> +<path fill="none" stroke="#555555" d="M789.88,-293.52C781.74,-278.83 769.73,-257.16 760.65,-240.8"/> +<polygon fill="#555555" stroke="#555555" points="762.69,-240.14 757.94,-235.91 759.02,-242.18 762.69,-240.14"/> +</g> +<!-- PTR_MORE_NIL --> +<g id="node19" class="node"> +<title>PTR_MORE_NIL</title> +<ellipse fill="#008000" stroke="black" cx="840" cy="-216.97" rx="45.21" ry="18"/> +<text text-anchor="middle" x="840" y="-212.87" font-family="DejaVu Sans" font-size="13.00" fill="white">*s2?, …</text> +</g> +<!-- PTR_NULL->PTR_MORE_NIL --> +<g id="edge28" class="edge"> +<title>PTR_NULL->PTR_MORE_NIL</title> +<path fill="none" stroke="#555555" d="M806.33,-293.52C812.78,-279.05 822.24,-257.81 829.5,-241.54"/> +<polygon fill="#555555" stroke="#555555" points="831.32,-242.62 831.84,-236.28 827.48,-240.91 831.32,-242.62"/> +</g> +<!-- PTR_ANY --> +<g id="node13" class="node"> +<title>PTR_ANY</title> +<ellipse fill="#008000" stroke="black" cx="502" cy="-216.97" rx="82.38" ry="28.99"/> +<text text-anchor="middle" x="502" y="-221.12" font-family="DejaVu Sans" font-size="13.00" fill="white">*⊥:struct</text> +<text text-anchor="middle" x="502" y="-204.62" font-family="DejaVu Sans" font-size="13.00" fill="white">[ptr any struct]</text> +</g> +<!-- PTR_ANY->PTR_BOT --> +<g id="edge29" class="edge"> +<title>PTR_ANY->PTR_BOT</title> +<path fill="none" stroke="#555555" d="M554.17,-194.13C595.32,-176.91 652.51,-152.97 694.1,-135.56"/> +<polygon fill="#555555" stroke="#555555" points="694.78,-137.55 699.5,-133.29 693.15,-133.67 694.78,-137.55"/> +</g> +<!-- PTR_ANY->PTR_PERSON_NIL --> +<!-- PTR_PERSON->PTR_ANY --> +<g id="edge20" class="edge"> +<title>PTR_PERSON->PTR_ANY</title> +<path fill="none" stroke="#555555" d="M534.66,-293.09C529.74,-281.77 523.08,-266.45 517.05,-252.6"/> +<polygon fill="#555555" stroke="#555555" points="519.08,-251.99 514.76,-247.33 515.23,-253.67 519.08,-251.99"/> +</g> +<!-- PTR_PERSON->PTR_S1 --> +<!-- PTR_PERSON->PTR_PERSON_NIL --> +<g id="edge23" class="edge"> +<title>PTR_PERSON->PTR_PERSON_NIL</title> +<path fill="none" stroke="#555555" d="M560.49,-294.36C578.62,-279.06 606.38,-255.63 626.38,-238.76"/> +<polygon fill="#555555" stroke="#555555" points="627.67,-240.42 630.9,-234.94 624.96,-237.21 627.67,-240.42"/> +</g> +<!-- PTR_S1->PTR_ANY --> +<g id="edge21" class="edge"> +<title>PTR_S1->PTR_ANY</title> +<path fill="none" stroke="#555555" d="M613.06,-297.17C595.19,-284.43 567.11,-264.41 543.66,-247.68"/> +<polygon fill="#555555" stroke="#555555" points="545.14,-246.16 539.04,-244.39 542.7,-249.58 545.14,-246.16"/> +</g> +<!-- PTR_S1->PTR_MORE --> +<!-- PTR_S1->PTR_S1_NIL --> +<g id="edge24" class="edge"> +<title>PTR_S1->PTR_S1_NIL</title> +<path fill="none" stroke="#555555" d="M648.01,-296.59C668.14,-280.76 701.78,-254.32 724.41,-236.52"/> +<polygon fill="#555555" stroke="#555555" points="725.59,-238.26 729.01,-232.91 722.99,-234.96 725.59,-238.26"/> +</g> +<!-- PTR_MORE->PTR_NULL --> +<!-- PTR_MORE->PTR_ANY --> +<g id="edge22" class="edge"> +<title>PTR_MORE->PTR_ANY</title> +<path fill="none" stroke="#555555" d="M686.72,-297.75C654.45,-283.81 600.84,-260.66 559.66,-242.88"/> +<polygon fill="#555555" stroke="#555555" points="560.63,-241.01 554.29,-240.56 558.97,-244.86 560.63,-241.01"/> +</g> +<!-- PTR_MORE->PTR_MORE_NIL --> +<g id="edge25" class="edge"> +<title>PTR_MORE->PTR_MORE_NIL</title> +<path fill="none" stroke="#555555" d="M735.36,-294.98C756.57,-279.37 789.9,-254.84 813.23,-237.67"/> +<polygon fill="#555555" stroke="#555555" points="814.42,-239.4 818.01,-234.16 811.93,-236.02 814.42,-239.4"/> +</g> +<!-- PTR_PERSON_NIL->PTR_BOT --> +<g id="edge30" class="edge"> +<title>PTR_PERSON_NIL->PTR_BOT</title> +<path fill="none" stroke="#555555" d="M666.58,-199.43C680.58,-184.56 701.51,-162.35 718.65,-144.16"/> +<polygon fill="#555555" stroke="#555555" points="719.75,-146.05 722.33,-140.24 716.69,-143.17 719.75,-146.05"/> +</g> +<!-- PTR_PERSON_NIL->PTR_S1_NIL --> +<!-- PTR_S1_NIL->PTR_BOT --> +<g id="edge31" class="edge"> +<title>PTR_S1_NIL->PTR_BOT</title> +<path fill="none" stroke="#555555" d="M748,-198.5C748,-184.97 748,-165.76 748,-148.97"/> +<polygon fill="#555555" stroke="#555555" points="750.1,-148.97 748,-142.97 745.9,-148.97 750.1,-148.97"/> +</g> +<!-- PTR_S1_NIL->PTR_MORE_NIL --> +<!-- PTR_MORE_NIL->PTR_BOT --> +<g id="edge32" class="edge"> +<title>PTR_MORE_NIL->PTR_BOT</title> +<path fill="none" stroke="#555555" d="M825.62,-199.88C812.53,-185.22 792.8,-163.14 776.51,-144.9"/> +<polygon fill="#555555" stroke="#555555" points="778.14,-143.58 772.58,-140.51 775.01,-146.38 778.14,-143.58"/> +</g> +<!-- STRUCT_PERSON --> +<g id="node22" class="node"> +<title>STRUCT_PERSON</title> +<polygon fill="#90ee90" stroke="black" points="976.5,-237.47 909.5,-237.47 909.5,-196.47 976.5,-196.47 976.5,-237.47"/> +<text text-anchor="middle" x="943" y="-221.12" font-family="DejaVu Sans" font-size="13.00">Person</text> +<text text-anchor="middle" x="943" y="-204.62" font-family="DejaVu Sans" font-size="13.00">age: int</text> +</g> +<!-- STRUCT_TOP->STRUCT_PERSON --> +<g id="edge36" class="edge"> +<title>STRUCT_TOP->STRUCT_PERSON</title> +<path fill="none" stroke="#555555" d="M1008.47,-376.11C993.72,-340.49 968.36,-279.23 953.91,-244.33"/> +<polygon fill="#555555" stroke="#555555" points="955.99,-243.86 951.75,-239.12 952.11,-245.47 955.99,-243.86"/> +</g> +<!-- STRUCT_S1 --> +<g id="node23" class="node"> +<title>STRUCT_S1</title> +<polygon fill="#90ee90" stroke="black" points="1047,-237.47 993,-237.47 993,-196.47 1047,-196.47 1047,-237.47"/> +<text text-anchor="middle" x="1020" y="-221.12" font-family="DejaVu Sans" font-size="13.00">s1</text> +<text text-anchor="middle" x="1020" y="-204.62" font-family="DejaVu Sans" font-size="13.00">x: int</text> +</g> +<!-- STRUCT_TOP->STRUCT_S1 --> +<g id="edge37" class="edge"> +<title>STRUCT_TOP->STRUCT_S1</title> +<path fill="none" stroke="#555555" d="M1020,-375.71C1020,-340.38 1020,-280.29 1020,-245.36"/> +<polygon fill="#555555" stroke="#555555" points="1022.1,-245.4 1020,-239.4 1017.9,-245.4 1022.1,-245.4"/> +</g> +<!-- STRUCT_S2 --> +<g id="node24" class="node"> +<title>STRUCT_S2</title> +<polygon fill="#90ee90" stroke="black" points="1159.12,-237.47 1062.88,-237.47 1062.88,-196.47 1159.12,-196.47 1159.12,-237.47"/> +<text text-anchor="middle" x="1111" y="-221.12" font-family="DejaVu Sans" font-size="13.00">s2</text> +<text text-anchor="middle" x="1111" y="-204.62" font-family="DejaVu Sans" font-size="13.00">x: int, y: *s1</text> +</g> +<!-- STRUCT_TOP->STRUCT_S2 --> +<g id="edge38" class="edge"> +<title>STRUCT_TOP->STRUCT_S2</title> +<path fill="none" stroke="#555555" d="M1033.43,-376.51C1050.81,-340.99 1080.89,-279.5 1098.04,-244.46"/> +<polygon fill="#555555" stroke="#555555" points="1099.88,-245.49 1100.63,-239.17 1096.1,-243.64 1099.88,-245.49"/> +</g> +<!-- STRUCT_MORE --> +<g id="node25" class="node"> +<title>STRUCT_MORE</title> +<polygon fill="#90ee90" stroke="black" points="1229,-234.97 1175,-234.97 1175,-198.97 1229,-198.97 1229,-234.97"/> +<text text-anchor="middle" x="1202" y="-212.87" font-family="DejaVu Sans" font-size="13.00">…</text> +</g> +<!-- STRUCT_TOP->STRUCT_MORE --> +<g id="edge39" class="edge"> +<title>STRUCT_TOP->STRUCT_MORE</title> +<path fill="none" stroke="#555555" d="M1045.31,-378.1C1081.09,-341.53 1145.91,-275.3 1179.87,-240.58"/> +<polygon fill="#555555" stroke="#555555" points="1181.3,-242.13 1183.99,-236.38 1178.3,-239.19 1181.3,-242.13"/> +</g> +<!-- STRUCT_TOP->MEM_TOP --> +<!-- STRUCT_BOT --> +<g id="node21" class="node"> +<title>STRUCT_BOT</title> +<ellipse fill="#90ee90" stroke="black" cx="1020" cy="-111.99" rx="82.91" ry="28.99"/> +<text text-anchor="middle" x="1020" y="-116.14" font-family="DejaVu Sans" font-size="13.00">⊥:struct</text> +<text text-anchor="middle" x="1020" y="-99.64" font-family="DejaVu Sans" font-size="13.00">[struct bottom]</text> +</g> +<!-- STRUCT_BOT->BOT --> +<g id="edge69" class="edge"> +<title>STRUCT_BOT->BOT</title> +<path fill="none" stroke="#555555" d="M982.84,-85.85C959.17,-69.85 929.19,-49.57 908.49,-35.56"/> +<polygon fill="#555555" stroke="#555555" points="909.78,-33.9 903.63,-32.28 907.42,-37.38 909.78,-33.9"/> +</g> +<!-- STRUCT_PERSON->STRUCT_BOT --> +<g id="edge40" class="edge"> +<title>STRUCT_PERSON->STRUCT_BOT</title> +<path fill="none" stroke="#555555" d="M957.85,-196.12C968.43,-181.96 982.92,-162.59 995.24,-146.11"/> +<polygon fill="#555555" stroke="#555555" points="996.85,-147.46 998.76,-141.4 993.49,-144.94 996.85,-147.46"/> +</g> +<!-- STRUCT_PERSON->STRUCT_S1 --> +<!-- STRUCT_S1->STRUCT_BOT --> +<g id="edge41" class="edge"> +<title>STRUCT_S1->STRUCT_BOT</title> +<path fill="none" stroke="#555555" d="M1020,-196.12C1020,-182.64 1020,-164.43 1020,-148.49"/> +<polygon fill="#555555" stroke="#555555" points="1022.1,-148.87 1020,-142.87 1017.9,-148.87 1022.1,-148.87"/> +</g> +<!-- STRUCT_S1->STRUCT_S2 --> +<!-- STRUCT_S2->STRUCT_BOT --> +<g id="edge42" class="edge"> +<title>STRUCT_S2->STRUCT_BOT</title> +<path fill="none" stroke="#555555" d="M1093.45,-196.12C1080.83,-181.83 1063.53,-162.25 1048.88,-145.68"/> +<polygon fill="#555555" stroke="#555555" points="1050.58,-144.42 1045.03,-141.32 1047.43,-147.2 1050.58,-144.42"/> +</g> +<!-- STRUCT_S2->STRUCT_MORE --> +<!-- STRUCT_MORE->STRUCT_BOT --> +<g id="edge43" class="edge"> +<title>STRUCT_MORE->STRUCT_BOT</title> +<path fill="none" stroke="#555555" d="M1181.79,-198.68C1177.07,-194.96 1171.97,-191.19 1167,-187.98 1138.36,-169.5 1104.6,-152 1076.65,-138.56"/> +<polygon fill="#555555" stroke="#555555" points="1077.74,-136.75 1071.42,-136.06 1075.93,-140.54 1077.74,-136.75"/> +</g> +<!-- MEM_ALIAS2 --> +<g id="node28" class="node"> +<title>MEM_ALIAS2</title> +<ellipse fill="#00008b" stroke="black" cx="1298" cy="-216.97" rx="45.21" ry="18"/> +<text text-anchor="middle" x="1298" y="-212.87" font-family="DejaVu Sans" font-size="13.00" fill="white">MEM#2</text> +</g> +<!-- MEM_TOP->MEM_ALIAS2 --> +<g id="edge46" class="edge"> +<title>MEM_TOP->MEM_ALIAS2</title> +<path fill="none" stroke="#555555" d="M1346.11,-386.79C1336.64,-353.58 1315.8,-280.42 1304.92,-242.24"/> +<polygon fill="#555555" stroke="#555555" points="1306.96,-241.75 1303.29,-236.55 1302.92,-242.9 1306.96,-241.75"/> +</g> +<!-- MEM_ALIAS3 --> +<g id="node29" class="node"> +<title>MEM_ALIAS3</title> +<ellipse fill="#00008b" stroke="black" cx="1404" cy="-216.97" rx="45.21" ry="18"/> +<text text-anchor="middle" x="1404" y="-212.87" font-family="DejaVu Sans" font-size="13.00" fill="white">MEM#3</text> +</g> +<!-- MEM_TOP->MEM_ALIAS3 --> +<g id="edge47" class="edge"> +<title>MEM_TOP->MEM_ALIAS3</title> +<path fill="none" stroke="#555555" d="M1355.89,-386.79C1365.36,-353.58 1386.2,-280.42 1397.08,-242.24"/> +<polygon fill="#555555" stroke="#555555" points="1399.08,-242.9 1398.71,-236.55 1395.04,-241.75 1399.08,-242.9"/> +</g> +<!-- MEM_MORE --> +<g id="node30" class="node"> +<title>MEM_MORE</title> +<ellipse fill="#00008b" stroke="black" cx="1492" cy="-216.97" rx="27" ry="18"/> +<text text-anchor="middle" x="1492" y="-212.87" font-family="DejaVu Sans" font-size="13.00" fill="white">…</text> +</g> +<!-- MEM_TOP->MEM_MORE --> +<g id="edge48" class="edge"> +<title>MEM_TOP->MEM_MORE</title> +<path fill="none" stroke="#555555" d="M1363.51,-387.45C1389.1,-353.7 1447.4,-276.8 1475.82,-239.32"/> +<polygon fill="#555555" stroke="#555555" points="1477.25,-240.91 1479.2,-234.86 1473.9,-238.37 1477.25,-240.91"/> +</g> +<!-- MEM_TOP->TUPLE_TOP --> +<!-- MEM_BOT --> +<g id="node27" class="node"> +<title>MEM_BOT</title> +<ellipse fill="#00008b" stroke="black" cx="1351" cy="-111.99" rx="44.7" ry="18"/> +<text text-anchor="middle" x="1351" y="-107.89" font-family="DejaVu Sans" font-size="13.00" fill="white">⊥:mem</text> +</g> +<!-- MEM_BOT->BOT --> +<g id="edge70" class="edge"> +<title>MEM_BOT->BOT</title> +<path fill="none" stroke="#555555" d="M1319.14,-99.06C1297.39,-91.29 1267.77,-81.43 1241,-75 1124.06,-46.89 982.06,-29.48 918.11,-22.5"/> +<polygon fill="#555555" stroke="#555555" points="918.4,-20.42 912.21,-21.87 917.95,-24.6 918.4,-20.42"/> +</g> +<!-- MEM_ALIAS2->MEM_BOT --> +<g id="edge49" class="edge"> +<title>MEM_ALIAS2->MEM_BOT</title> +<path fill="none" stroke="#555555" d="M1306.75,-198.97C1315.5,-181.97 1329.02,-155.71 1338.81,-136.68"/> +<polygon fill="#555555" stroke="#555555" points="1340.66,-137.66 1341.54,-131.37 1336.93,-135.74 1340.66,-137.66"/> +</g> +<!-- MEM_ALIAS2->MEM_ALIAS3 --> +<!-- MEM_ALIAS3->MEM_BOT --> +<g id="edge50" class="edge"> +<title>MEM_ALIAS3->MEM_BOT</title> +<path fill="none" stroke="#555555" d="M1395.25,-198.97C1386.5,-181.97 1372.98,-155.71 1363.19,-136.68"/> +<polygon fill="#555555" stroke="#555555" points="1365.07,-135.74 1360.46,-131.37 1361.34,-137.66 1365.07,-135.74"/> +</g> +<!-- MEM_ALIAS3->MEM_MORE --> +<!-- MEM_MORE->MEM_BOT --> +<g id="edge51" class="edge"> +<title>MEM_MORE->MEM_BOT</title> +<path fill="none" stroke="#555555" d="M1475.42,-202.39C1469.65,-197.74 1463.09,-192.57 1457,-187.98 1430.93,-168.37 1400.47,-146.96 1378.9,-132.06"/> +<polygon fill="#555555" stroke="#555555" points="1380.17,-130.38 1374.03,-128.71 1377.78,-133.84 1380.17,-130.38"/> +</g> +<!-- TUPLE1 --> +<g id="node33" class="node"> +<title>TUPLE1</title> +<polygon fill="#ffc0cb" stroke="black" points="1598.88,-328.97 1543.12,-328.97 1543.12,-292.97 1598.88,-292.97 1598.88,-328.97"/> +<text text-anchor="middle" x="1571" y="-306.87" font-family="DejaVu Sans" font-size="13.00">(type)</text> +</g> +<!-- TUPLE_TOP->TUPLE1 --> +<g id="edge54" class="edge"> +<title>TUPLE_TOP->TUPLE1</title> +<path fill="none" stroke="#555555" d="M1584.8,-386.65C1582.19,-372.52 1578.47,-352.37 1575.54,-336.56"/> +<polygon fill="#555555" stroke="#555555" points="1577.61,-336.2 1574.46,-330.68 1573.48,-336.96 1577.61,-336.2"/> +</g> +<!-- TUPLE2 --> +<g id="node34" class="node"> +<title>TUPLE2</title> +<polygon fill="#ffc0cb" stroke="black" points="1709,-328.97 1615,-328.97 1615,-292.97 1709,-292.97 1709,-328.97"/> +<text text-anchor="middle" x="1662" y="-306.87" font-family="DejaVu Sans" font-size="13.00">(type, type)</text> +</g> +<!-- TUPLE_TOP->TUPLE2 --> +<g id="edge55" class="edge"> +<title>TUPLE_TOP->TUPLE2</title> +<path fill="none" stroke="#555555" d="M1601.23,-387.51C1613,-372.87 1630.35,-351.31 1643.5,-334.97"/> +<polygon fill="#555555" stroke="#555555" points="1645.06,-336.38 1647.18,-330.39 1641.79,-333.74 1645.06,-336.38"/> +</g> +<!-- TUPLEN --> +<g id="node35" class="node"> +<title>TUPLEN</title> +<polygon fill="#ffc0cb" stroke="black" points="1802.75,-328.97 1725.25,-328.97 1725.25,-292.97 1802.75,-292.97 1802.75,-328.97"/> +<text text-anchor="middle" x="1764" y="-306.87" font-family="DejaVu Sans" font-size="13.00">(type, …)</text> +</g> +<!-- TUPLE_TOP->TUPLEN --> +<g id="edge56" class="edge"> +<title>TUPLE_TOP->TUPLEN</title> +<path fill="none" stroke="#555555" d="M1614.35,-390.18C1643.39,-375.01 1690.42,-350.42 1724.01,-332.87"/> +<polygon fill="#555555" stroke="#555555" points="1724.85,-334.8 1729.2,-330.16 1722.91,-331.07 1724.85,-334.8"/> +</g> +<!-- TUPLE_BOT --> +<g id="node32" class="node"> +<title>TUPLE_BOT</title> +<ellipse fill="#ffc0cb" stroke="black" cx="1625" cy="-111.99" rx="44.7" ry="18"/> +<text text-anchor="middle" x="1625" y="-107.89" font-family="DejaVu Sans" font-size="13.00">⊥:tuple</text> +</g> +<!-- TUPLE_BOT->BOT --> +<g id="edge71" class="edge"> +<title>TUPLE_BOT->BOT</title> +<path fill="none" stroke="#555555" d="M1596.44,-97.66C1578.14,-89.72 1553.65,-80.21 1531,-75 1301.56,-22.24 1015.96,-18.29 918.46,-18.63"/> +<polygon fill="#555555" stroke="#555555" points="918.73,-16.53 912.74,-18.66 918.75,-20.73 918.73,-16.53"/> +</g> +<!-- TUPLE1->TUPLE_BOT --> +<g id="edge57" class="edge"> +<title>TUPLE1->TUPLE_BOT</title> +<path fill="none" stroke="#555555" d="M1575.79,-292.49C1585.46,-257.21 1607.33,-177.44 1618.37,-137.19"/> +<polygon fill="#555555" stroke="#555555" points="1620.33,-137.95 1619.9,-131.61 1616.28,-136.84 1620.33,-137.95"/> +</g> +<!-- TUPLE1->TUPLE2 --> +<!-- TUPLE2->TUPLE_BOT --> +<g id="edge58" class="edge"> +<title>TUPLE2->TUPLE_BOT</title> +<path fill="none" stroke="#555555" d="M1658.72,-292.49C1652.12,-257.37 1637.24,-178.17 1629.65,-137.74"/> +<polygon fill="#555555" stroke="#555555" points="1631.73,-137.43 1628.56,-131.92 1627.6,-138.2 1631.73,-137.43"/> +</g> +<!-- TUPLE2->TUPLEN --> +<!-- TUPLEN->TUPLE_BOT --> +<g id="edge59" class="edge"> +<title>TUPLEN->TUPLE_BOT</title> +<path fill="none" stroke="#555555" d="M1751.66,-292.49C1726.44,-256.74 1668.97,-175.3 1640.95,-135.59"/> +<polygon fill="#555555" stroke="#555555" points="1642.76,-134.52 1637.59,-130.83 1639.33,-136.94 1642.76,-134.52"/> +</g> +</g> +</svg> diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 7734f4df..3b5f2721 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -33,6 +33,10 @@ public class Parser { 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; + // The Lexer. Thin wrapper over a byte[] buffer with a cursor. private final Lexer _lexer; @@ -200,6 +204,8 @@ public class Parser { require("}"); // Build and install the TypeStruct TypeStruct ts = TypeStruct.make(typeName, fields); + _aliases.put(typeName,_alias); + _alias += ts._fields.length; OBJS.put(typeName, ts); // Insert the struct name in the collection of all struct names return parseStatement(); } @@ -589,8 +595,10 @@ public class Parser { private Node newStruct( TypeStruct obj ) { Node n = new NewNode(TypeMemPtr.make(obj), ctrl()).peephole().keep(); Node initValue = new ConstantNode(TypeInteger.constant(0)).peephole(); + int alias = _aliases.get(obj._name); for( Field field : obj._fields ) { - mem(new StoreNode(field._fname, mem(), n, initValue).peephole()); + store(field._fname,alias,n,initValue); + alias++; } return n.unkeep(); } @@ -599,6 +607,13 @@ 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) { + Node prior = mem().keep(); + Node st = new StoreNode(name,alias,prior,ptr,val).peephole(); + mem(new MemMergeNode(prior,alias,st).peephole()); + prior.unkeep(); + } + /** * Parse postfix expression. For now this is just a field * expression, but in future could be array index too. @@ -616,19 +631,20 @@ public class Parser { String name = requireId().intern(); int idx = ptr._obj==null ? -1 : ptr._obj.find(name); if( idx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); + int alias = _aliases.get(ptr._obj._name)+idx; if( match("=") ) { // Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment if( peek('=') ) _lexer._position--; else { Node val = parseExpression(); - mem(new StoreNode(name, mem(), expr, val).peephole()); + store(name,alias,expr,val); return expr; // "obj.a = expr" returns the expression while updating memory } } Type declaredType = ptr._obj._fields[idx]._type; - return parsePostfix(new LoadNode(name, declaredType, mem(), expr).peephole()); + return parsePostfix(new LoadNode(name, alias, declaredType, mem(), expr).peephole()); } /** diff --git a/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java new file mode 100644 index 00000000..8d512f21 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java @@ -0,0 +1,237 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; +import java.util.BitSet; + +/** + * A Phi for bulk memory. It covers all aliases except {@link #_aliases}; + * those aliases must be represented by parallel precise MemPhis at the same + * program slice. + */ +public class BulkMemPhiNode extends PhiNode { + + private static final BitSet EMPTY = new BitSet(); + + // Excluded Aliases; empty means NO exclusions. + // Each split clones the exclusions; published sets are never mutated. + public final BitSet _aliases; + + public BulkMemPhiNode(String label, Node... inputs) { + this(label,EMPTY,inputs); + } + + private BulkMemPhiNode(String label, BitSet aliases, Node... inputs) { + super(label,TypeMem.BOT,inputs); + _aliases = aliases; + } + + public boolean isSplit(int alias) { return _aliases.get(alias); } + + @Override public String label() { return "BulkPhi"+_aliases; } + + @Override + public Type compute() { + Type t = super.compute(); + return t instanceof TypeMem mem ? mem : + t==Type.BOTTOM ? TypeMem.BOT : + TypeMem.TOP; + } + + @Override + public Node idealize() { + Node progress = super.idealize(); + if( progress != null ) return progress; + if( ((RegionNode)region()).inProgress() || region().nIns()<=1 ) + return null; // Input is in-progress + + // "Peek through" a MemMerge that covers this alias set on its default + for( int i=1; i<nIns(); i++ ) + if( in(i) instanceof MemMergeNode mmm && canPeek(mmm) ) { + setDef(i,IterPeeps.add(mmm.in(1))); + return this; + } + + // If any input or output uses or defines a specific alias we cover, + // make a private MemPhi for it, and add it to the excluded list. + for( int i=1; i<nIns(); i++ ) { + int alias = inputAlias(in(i)); + if( alias!=0 ) + return slice(alias); + } + + for( int i=0; i<_outputs.size(); i++ ) { + int alias = outputAlias(_outputs.get(i)); + if( alias!=0 ) + return slice(alias); + } + + return null; + } + + static public boolean checkMem(Node n, int alias) { + for( Node m : n._inputs ) + // Bulk memory supplies this alias + if( m instanceof BulkMemPhiNode bulk ) { + if( bulk._aliases.get(alias) ) + return false; + } else if( m instanceof MemMergeNode mmm && + mmm.in(1) instanceof BulkMemPhiNode bulk && + bulk._aliases.get(alias) && + (alias >= mmm.nIns() || mmm.in(alias)==null) ) + return false; + return true; + } + + + // True if the MemMerge has no precise slice still covered by this Phi. + private boolean canPeek(MemMergeNode mmm) { + return missingAlias(mmm,false)==0; + } + + // Return an alias required by an input but still covered by this Phi, or 0. + private int inputAlias(Node n) { + return switch(n) { + case ProjNode proj -> 0; + case ConstantNode con -> 0; + case MemMergeNode mmm -> missingAlias(mmm,false); + case MemOpNode mem -> unsplit(mem._alias); + case BulkMemPhiNode bulk -> missingAlias(bulk); + default -> throw new AssertionError("Unexpected memory input "+n); + }; + } + + // Return an alias required by a user but still covered by this Phi, or 0. + private int outputAlias(Node use) { + // This decision depends backwards on an immediate user's alias/set. + // Normal graph-neighbor enqueueing flows from defs to uses, so retain + // an explicit forward dependency to revisit this Phi when the user + // sharpens. + use.addDepForwards(this); + return switch(use) { + case ScopeNode scope -> 0; + case MemMergeNode mmm -> missingAlias(mmm,true); + case BulkMemPhiNode bulk -> missingAlias(bulk); + case MemOpNode mem -> unsplit(mem._alias); + case MemPhiNode phi -> unsplit(phi._alias); + default -> { + assert use instanceof ReturnNode + : "Unexpected bulk-memory user "+use; + yield 0; + } + }; + } + + // Alias zero/one is bulk, and an already excluded precise alias cannot + // trigger another split of this Phi. + private int unsplit(int alias) { + if( alias <= 1 ) return 0; + assert !_aliases.get(alias); + return alias; + } + + // First alias excluded by the neighboring bulk Phi but not by this one. + private int missingAlias(BulkMemPhiNode bulk) { + for( int alias = bulk._aliases.nextSetBit(0); alias >= 0; alias = bulk._aliases.nextSetBit(alias+1) ) + if( !_aliases.get(alias) ) + return alias; + return 0; + } + + // First precise MemMerge slice still covered by this Phi. When inspecting + // a user, ignore slots which point back to this Phi. + private int missingAlias(MemMergeNode mmm, boolean user) { + for( int alias=2; alias<mmm.nIns(); alias++ ) + if( mmm.in(alias)!=null && + mmm.alias(alias)!=mmm.in(1) && + !_aliases.get(alias) ) + { assert (!user || mmm.in(alias)!=this); return alias; } + return 0; + } + + // Slice out given alias + private MemMergeNode slice( int alias ) { + assert !_aliases.get(alias); + // Inputs are the same; MemPhi will sharpen his own inputs. If a + // parallel precise Phi already exists, reuse it instead of building a + // duplicate for the same Region/alias pair. + Node mem = precisePhi(alias); + + BitSet aliases = ((BitSet)_aliases.clone()); + aliases.set(alias); + BulkMemPhiNode bphi = new BulkMemPhiNode(_label,aliases); + for( int i=0; i<nIns(); i++ ) + bphi.addDef(in(i)); + // Installing bphi creates a new bulk user with a different exclusion + // set. Queue the original memory inputs before bphi itself can peep + // away and hide those neighbor relationships. + for( int i=1; i<bphi.nIns(); i++ ) + IterPeeps.add(bphi.in(i)); + // Do not peephole bphi here, as BulkMemPhi can recursively start a + // second bulk rewrite before this one has finished. Let the worklist + // discover any further splits + bphi.setType(TypeMem.BOT); + Node bulk = bphi; + IterPeeps.add(bulk); + IterPeeps.add(mem); + return aggregate(bulk,alias,mem); + } + + // Build aggregate memory over a bulk Phi, preserving every precise slice + // which the bulk has already excluded. The named alias is newly supplied + // (or replaces its old slice). + MemMergeNode aggregate(Node bulk, int alias, Node precise) { + MemMergeNode mmm = new MemMergeNode(bulk); + for( int old = _aliases.nextSetBit(0); old >= 0; old = _aliases.nextSetBit(old+1) ) + { assert old != alias; mmm.alias(old,precisePhi(old));} + mmm.alias(alias,precise); + assert checkMerge(mmm); + return mmm; + } + + // Find or make the precise Phi parallel to this bulk Phi at the same merge. + private Node precisePhi(int alias) { + MemPhiNode mphi = _findPhi(alias); + if( mphi!=null ) return mphi; + + mphi = new MemPhiNode("$"+alias,alias); + mphi.addDef(region()); + // Due to cycles, must set before calling peephole + mphi.setType(TypeMem.make(alias)); + for( int i=1; i<nIns(); i++ ) + mphi.addDef(IterPeeps.add(preciseInput(in(i),alias))); + return IterPeeps.add(mphi); + } + + MemPhiNode _findPhi(int alias) { + for( Node use : region()._outputs ) + if( use instanceof MemPhiNode mphi && mphi._alias==alias ) + return mphi; + return null; + } + + // Select an alias already split out of a predecessor's bulk memory. + private Node preciseInput(Node mem, int alias) { + if( mem instanceof MemMergeNode mmm ) + return mmm.alias(alias); + if( mem instanceof BulkMemPhiNode bulk && bulk.isSplit(alias) ) + return bulk.precisePhi(alias); + return mem; + } + + // Every alias excluded by a bulk default must be supplied explicitly. + static boolean checkMerge(MemMergeNode mmm) { + if( !(mmm.in(1) instanceof BulkMemPhiNode bulk) ) return true; + for( int alias = bulk._aliases.nextSetBit(0); alias >= 0; alias = bulk._aliases.nextSetBit(alias+1) ) + if( alias >= mmm.nIns() || mmm.in(alias)==null ) + return false; + return true; + } + + @Override public boolean eq(Node n) { + return _aliases.equals(((BulkMemPhiNode)n)._aliases) && super.eq(n); + } + + @Override int hash() { return _aliases.hashCode(); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 54689283..55822722 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -1,6 +1,9 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.Field; import java.util.BitSet; @@ -15,11 +18,11 @@ public class LoadNode extends MemOpNode { * Load a value from a ptr.field. * * @param name The field we are loading - * @param memSlice The whole-memory node - this is updated after a Store + * @param memSlice The memory alias node - this is updated after a Store * @param memPtr The ptr to the struct from where we load a field */ - public LoadNode(String name, Type glb, Node memSlice, Node memPtr) { - super(name, memSlice, memPtr, null); + public LoadNode(String name, int alias, Type glb, Node memSlice, Node memPtr) { + super(name, alias, memSlice, memPtr, null); _declaredType = glb; } @@ -36,10 +39,16 @@ public class LoadNode extends MemOpNode { @Override public Node idealize() { + if( mem() instanceof MemMergeNode merge ) { + setDef(1,IterPeeps.add(merge.alias(_alias))); + return this; + } + // Simple Load-after-Store on same address. if( mem() instanceof StoreNode st && - ptr() == st.ptr() && _name.equals(st._name) ) { // Must check same object + ptr() == st.ptr() && _alias==st._alias ) { // Must check same object + assert Utils.eq(_name,st._name); // Equiv class aliasing is perfect return st.val(); } @@ -50,13 +59,13 @@ public class LoadNode extends MemOpNode { // if( pred ) ptr.x = e0; val = pred ? e0 // else ptr.x = e1; : e1; // val = ptr.x; ptr.x = val; - if( mem() instanceof PhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 ) { + if( mem() instanceof MemPhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 ) { // Profit on RHS/Loop backedge if( profit(memphi,2) || // Else must not be a loop to count profit on LHS. (!(memphi.region() instanceof LoopNode) && profit(memphi,1)) ) { - Node ld1 = new LoadNode(_name,_declaredType,memphi.in(1),ptr()).peephole(); - Node ld2 = new LoadNode(_name,_declaredType,memphi.in(2),ptr()).peephole(); + 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); } } @@ -67,6 +76,6 @@ public class LoadNode extends MemOpNode { // Profitable if we find a matching Store on this Phi arm. private boolean profit(PhiNode phi, int idx) { Node px = phi.in(idx); - return px!=null && px.addDep(this) instanceof StoreNode st1 && ptr()==st1.ptr() && _name.equals(st1._name); + return px!=null && px.addDep(this) instanceof StoreNode st1 && ptr()==st1.ptr() && _alias==st1._alias; } } diff --git a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java new file mode 100644 index 00000000..d7fed402 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -0,0 +1,60 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; +import java.util.BitSet; + +/** All memory: a default slice and explicit overrides for individual aliases. */ +public class MemMergeNode extends Node { + public MemMergeNode(Node bulk) { super(null,bulk); _type = TypeMem.BOT; } + public MemMergeNode(Node bulk, int alias, Node precise) { + this(bulk); + alias(alias,precise); + } + + public Node alias(int alias) { + Node n = alias < nIns() ? in(alias) : null; + assert n!=null || !(in(1) instanceof BulkMemPhiNode bulk) || !bulk.isSplit(alias); + return n==null ? in(1) : n; + } + + public void alias(int alias, Node mem) { + assert alias > 1; + while( nIns()<=alias ) addDef(null); + setDef(alias,mem); + } + + @Override public String label() { return "MemMerge"; } + @Override public boolean isMem() { return true; } + @Override public Type compute() { return TypeMem.BOT; } + @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { + sb.append("MEM["); + for( int i=1; i<nIns(); i++ ) + if( in(i)!=null ) { + sb.append(i==1 ? "default:" : i+":"); + in(i)._print0(sb,visited).append(" "); + } + return sb.append("]"); + } + + @Override public Node idealize() { + boolean progress=false, allDefault=true; + for( int i=2; i<nIns(); i++ ) { + if( in(i)==in(1) ) { setDef(i,null); progress=true; } + if( in(i)!=null ) allDefault=false; + } + if( allDefault ) return in(1); + + if( in(1) instanceof MemMergeNode mem ) { + for( int i=2; i<mem.nIns(); i++ ) + if( mem.in(i)!=null && (i>=nIns() || in(i)==null) ) + alias(i,mem.in(i)); + IterPeeps.add(mem.in(1)); + setDef(1,mem.in(1)); + return this; + } + assert BulkMemPhiNode.checkMerge(this); + return progress ? this : null; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index d811e71a..08e08bbf 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.type.Field; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMemPtr; @@ -9,10 +10,12 @@ import com.seaofnodes.simple.type.TypeMemPtr; public abstract class MemOpNode extends Node { public final String _name; + public final int _alias; - public MemOpNode(String name, Node memSlice, Node memPtr, Node value) { + public MemOpNode(String name, int alias, Node memSlice, Node memPtr, Node value) { super(null, memSlice, memPtr, value); _name = name; + _alias = alias; } public Node mem() { return in(1); } @@ -21,11 +24,11 @@ public abstract class MemOpNode extends Node { @Override boolean eq(Node n) { MemOpNode mem = (MemOpNode)n; // Invariant - return _name.equals(mem._name); + return _alias==mem._alias; // When comparing types error to use "equals"; always use "==" } @Override - int hash() { return _name.hashCode(); } + int hash() { return _alias; } @Override String err() { diff --git a/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java b/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java new file mode 100644 index 00000000..c806bede --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java @@ -0,0 +1,36 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; + +/** A Phi for one field alias, parallel to a bulk Phi at the same Region. */ +public class MemPhiNode extends PhiNode { + public final int _alias; + + public MemPhiNode(String label, int alias, Node... inputs) { + super(label,TypeMem.make(alias),inputs); + assert alias > 1; + _alias = alias; + } + + @Override public String label() { return "MemPhi_"+_alias; } + + @Override public Type compute() { + assert BulkMemPhiNode.checkMem(this,_alias); + Type t = super.compute(); + return t==Type.TOP || t==TypeMem.TOP ? TypeMem.TOP : TypeMem.make(_alias); + } + + @Override public Node idealize() { + for( int i=1; i<nIns(); i++ ) + if( in(i) instanceof MemMergeNode mem ) { + setDef(i,IterPeeps.add(mem.alias(_alias))); + return this; + } + return super.idealize(); + } + + @Override boolean eq(Node n) { return _alias==((MemPhiNode)n)._alias && super.eq(n); } + @Override int hash() { return _alias; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index eb6c1697..f4972f96 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -450,6 +450,14 @@ public abstract class Node { * being added must benefit from this node being peepholed. */ Node addDep( Node dep ) { + return addDep(dep,false); + } + + // A bulk Phi inspects its users' partitions. Def-to-use propagation does + // not revisit that producer when an immediate user's partition changes. + Node addDepForwards(Node dep) { return addDep(dep,true); } + + private Node addDep(Node dep, boolean forwards) { // Running peepholes during the big assert cannot have side effects // like adding dependencies. if( IterPeeps.midAssert() ) return this; @@ -457,8 +465,8 @@ public abstract class Node { if( obs != null ) obs.dep(this, dep); if( _deps==null ) _deps = new ArrayList<>(); if( Utils.find(_deps ,dep) != -1 ) return this; // Already on list - if( Utils.find(_inputs,dep) != -1 ) return this; // No need for deps on immediate neighbors - if( Utils.find(_outputs,dep)!= -1 ) return this; + if( !forwards && Utils.find(_inputs,dep) != -1 ) return this; + if( !forwards && Utils.find(_outputs,dep)!= -1 ) return this; _deps.add(dep); return this; } diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index bdf50847..650edd6b 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -16,6 +16,10 @@ public class PhiNode extends Node { public PhiNode(String label, Type declaredType, Node... inputs) { super(inputs); _label = label; assert declaredType!=null; _declaredType = declaredType; } + public static PhiNode make(String label, Type type, Node... inputs) { + return type instanceof TypeMem ? new BulkMemPhiNode(label,inputs) : new PhiNode(label,type,inputs); + } + @Override public String label() { return "Phi_"+_label; } @Override @@ -71,7 +75,7 @@ public class PhiNode extends Node { // Phi(op(A,B),op(Q,R),op(X,Y)) becomes // op(Phi(A,Q,X), Phi(B,R,Y)). Node op = in(1); - if( op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op() ) { + if( !isMem() && op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op() ) { Node[] lhss = new Node[nIns()]; Node[] rhss = new Node[nIns()]; lhss[0] = rhss[0] = in(0); // Set Region diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 455f4b3a..b931e862 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -129,7 +129,7 @@ public class ScopeNode extends Node { // Set real Phi in the loop head // The phi takes its one input (no backedge yet) from a recursive // lookup, which might have insert a Phi in every loop nest. - : loop.setDef(idx,new PhiNode(name, lookupDeclaredType(name),loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole()); + : loop.setDef(idx,PhiNode.make(name, lookupDeclaredType(name),loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole()); setDef(idx,old); } return n==null ? old : setDef(idx,n); // Not lazy, so this is the answer @@ -207,7 +207,7 @@ public class ScopeNode extends Node { if( in(i) != that.in(i) ) // No need for redundant Phis // If we are in lazy phi mode we need to a lookup // by name as it will trigger a phi creation - setDef(i, new PhiNode(ns[i], this.lookupDeclaredType(ns[i]), r, this.lookup(ns[i]), that.lookup(ns[i])).peephole()); + setDef(i, PhiNode.make(ns[i], this.lookupDeclaredType(ns[i]), r, this.lookup(ns[i]), that.lookup(ns[i])).peephole()); that.kill(); // Kill merged scope IterPeeps.add(r); return r.unkeep().peephole(); diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 4bc67c3c..b752aad5 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.*; import java.util.BitSet; @@ -12,12 +14,12 @@ public class StoreNode extends MemOpNode { /** * @param name The struct field we are assigning to - * @param memSlice The whole-memory node - this is updated after a Store + * @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, Node memSlice, Node memPtr, Node value) { - super(name, memSlice, memPtr, value); + public StoreNode(String name, int alias, Node memSlice, Node memPtr, Node value) { + super(name, alias, memSlice, memPtr, value); } @Override @@ -32,19 +34,25 @@ public class StoreNode extends MemOpNode { } @Override - public Type compute() { return TypeMem.BOT; } + public Type compute() { return TypeMem.make(_alias); } @Override public Node idealize() { + if( mem() instanceof MemMergeNode merge ) { + setDef(1,IterPeeps.add(merge.alias(_alias))); + return this; + } + // Simple store-after-store on same address. Should pick up the // required init-store being stomped by a first user store. if( mem() instanceof StoreNode st && - ptr()==st.ptr() && _name.equals(st._name) && // Must check same object + ptr()==st.ptr() && _alias==st._alias && // Must check same object ptr()._type instanceof TypeMemPtr && // No bother if weird dead pointers // Must have exactly one use of "this" or you get weird // non-serializable memory effects in the worse case. st.checkNoUseBeyond(this) ) { + assert Utils.eq(_name,st._name); // Equiv class aliasing is perfect setDef(1,st.mem()); return this; } diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index bd9cf458..93e27c76 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -34,7 +34,7 @@ public class Type { static final byte TSIMPLE = 4; // End of the Simple Types static final byte TINT = 5; // All Integers; see TypeInteger static final byte TTUPLE = 6; // Tuples; finite collections of unrelated Types, kept in parallel - static final byte TMEM = 7; // Whole-memory token + 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 diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/src/main/java/com/seaofnodes/simple/type/TypeMem.java index d921bac3..b6fc8824 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -1,20 +1,66 @@ package com.seaofnodes.simple.type; +import com.seaofnodes.simple.Utils; +import java.lang.Long; +import java.util.BitSet; import java.util.ArrayList; -/** A token for all memory; field values are not tracked in its type. */ + +/** + * Represents a slice of memory corresponding to a set of aliases + */ public class TypeMem extends Type { - private final boolean _high; - private TypeMem(boolean high) { super(TMEM); _high = high; } - public static final TypeMem TOP = new TypeMem(true ).intern(); - public static final TypeMem BOT = new TypeMem(false).intern(); - - public static void gather(ArrayList<Type> ts) { ts.add(BOT); } - @Override TypeMem xmeet(Type t) { return BOT; } - @Override public Type dual() { return _high ? BOT : TOP; } - @Override public Type glb() { return BOT; } - @Override int hash() { return _high ? 1 : 2; } - @Override boolean eq(Type t) { return _high==((TypeMem)t)._high; } - @Override public StringBuilder print(StringBuilder sb) { return sb.append(_high ? "MemTop" : "MemBot"); } + + // Which slice of memory? + // 0 means TOP, no slice. + // -1 means BOT, all memory. + // N means slice#N. + private final int _alias; + + private TypeMem(int alias) { super(TMEM); _alias = alias; } + + public static TypeMem make(int alias) { return new TypeMem(alias).intern(); } + 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 + TypeMem xmeet(Type t) { + TypeMem that = (TypeMem) t; // Invariant: TypeMem and unequal + return _alias==0 ? that : (that._alias==0 ? this : BOT); + } + + @Override + public Type dual() { + if( _alias== 0 ) return BOT; + if( _alias==-1 ) return TOP; + return this; + } + + @Override + public Type glb() { return TypeMem.BOT; } + + @Override + int hash() { return 9876543 + _alias; } + + @Override + boolean eq(Type t) { + TypeMem that = (TypeMem) t; // Invariant + return _alias == that._alias; + } + + @Override + public StringBuilder print(StringBuilder sb) { + if( this==BOT ) return sb.append("MemBot"); + if( this==TOP ) return sb.append("MemTop"); + return sb.append("MEM#").append( switch(_alias) { + case 0 -> "TOP"; + case -1 -> "BOT"; + default -> ""+_alias; + }); + } + @Override public String str() { return print(new StringBuilder()).toString(); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 26bbb62a..b59eee93 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -165,7 +165,7 @@ while (arg) { return bar.a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,0,(Phi_a+2));", stop.toString()); + assertEquals("return Phi(Loop11,0,(Phi_a+2));", stop.toString()); } @Test @@ -217,7 +217,7 @@ if( bar ) bar.a = 1; return bar; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region15,null,new Bar);", stop.toString()); + assertEquals("return Phi(Region16,null,new Bar);", stop.toString()); } @Test @@ -233,7 +233,7 @@ else bar.a = 1; return rez; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region32,4,3);", stop.toString()); + assertEquals("return Phi(Region34,4,3);", stop.toString()); } @Test @@ -286,9 +286,7 @@ while( i.x < i.len ) { return sum; """); StopNode stop = parser.parse().iterate(); - // The preceding len store keeps the initial x load on the bulk chain. - assertEquals("return Phi(Loop13,0,(Phi(Loop,.x,(Phi_x+1))+Phi_sum));", stop.toString()); - assertEquals(10L, com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,5)); + assertEquals("return Phi(Loop16,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); } @@ -308,7 +306,7 @@ while(arg) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,new s0,Phi(Region31,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop11,new s0,Phi(Region34,new s0,Phi_ret));", stop.toString()); } @Test @@ -325,7 +323,7 @@ while(arg) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop13,new s0,Phi(Region32,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop15,new s0,Phi(Region35,new s0,Phi_ret));", stop.toString()); } @@ -342,7 +340,7 @@ while(arg < 10) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,new s0,Phi(Region30,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop11,new s0,Phi(Region32,new s0,Phi_ret));", stop.toString()); } @Test @@ -476,8 +474,7 @@ return 0; assertEquals(2244L, com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,1)); } - @Test public void testMemoryAcrossNestedLoops() { - var stop = new Parser(""" + static final String NESTED_MEMORY = """ struct S { int x; int y; int z; } S s = new S; s.x = 5; s.y = 7; s.z = 11; @@ -494,7 +491,10 @@ return 0; arg = arg - 1; } return s; - """).parse().iterate(); + """; + + @Test public void testMemoryAcrossNestedLoops() { + var stop = new Parser(NESTED_MEMORY).parse().iterate(); for (int arg=0; arg<7; arg++) { var obj = (com.seaofnodes.simple.evaluator.Evaluator.Obj) com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,arg); diff --git a/src/test/java/com/seaofnodes/simple/Chapter10bTest.java b/src/test/java/com/seaofnodes/simple/Chapter10bTest.java new file mode 100644 index 00000000..6f094cfb --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter10bTest.java @@ -0,0 +1,64 @@ +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/src/test/java/com/seaofnodes/simple/TypeTest.java b/src/test/java/com/seaofnodes/simple/TypeTest.java index c9eb2747..f9c580cc 100644 --- a/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -22,10 +22,23 @@ public class TypeTest { Assert.assertNotEquals(s1, s1.dual()); Assert.assertEquals(s1, s1.dual().glb()); - assertEquals(TypeStruct.BOT, s1.meet(s2)); - assertEquals(TypeMem.BOT, TypeMem.TOP.meet(TypeMem.BOT)); - assertEquals(TypeMem.TOP, TypeMem.BOT.dual()); - assertEquals(TypeMem.BOT, TypeMem.TOP.dual()); + TypeMem m1 = TypeMem.make(1); + TypeMem m2 = TypeMem.make(2); + TypeMem m3 = TypeMem.make(3); + TypeMem m4 = TypeMem.make(4); + + Assert.assertNotEquals(m1, m2); + Assert.assertNotEquals(m2, m3); + Assert.assertNotEquals(m3, m4); + + Assert.assertEquals(TypeStruct.BOT, s1.meet(s2)); + Assert.assertEquals(TypeMem .BOT, m1.meet(m2)); + Assert.assertEquals(TypeMem .BOT, m2.meet(m3)); + Assert.assertEquals(TypeMem .BOT, m3.meet(m4)); + + Assert.assertEquals(TypeMem.BOT, m1.glb()); + Assert.assertEquals(m1, m1.dual()); + Assert.assertEquals(TypeMem.TOP, m1.glb().dual()); TypeMemPtr ptr1 = TypeMemPtr.make(s1); Assert.assertEquals(s1, ptr1._obj); diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index eaeb061b..e49e0303 100644 --- a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -138,6 +138,7 @@ public class Evaluator { case CastNode cast -> val(cast.in(1)); case LoadNode load -> load(load); case StoreNode store -> store(store); + case MemMergeNode merge -> MEMORY; case NewNode alloc -> alloc(alloc); case ProjNode proj -> ((Object[])val(proj.ctrl()))[proj._idx]; default -> throw new AssertionError("Unexpected node " + node); diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java b/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java index 674d12f5..48ac0562 100644 --- a/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java +++ b/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java @@ -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(); } /** @@ -250,6 +250,12 @@ public class Scheduler { // so do that now. var mem = l.in(1); for(var out : mem._outputs) { + // Aggregates describe partitions; they do not overwrite + // memory. Only users of this alias constrain the load. + if (out instanceof MemMergeNode || out instanceof ReturnNode) continue; + if (out instanceof StoreNode s && s._alias != l._alias) continue; + if (out instanceof MemPhiNode p && p._alias != l._alias) continue; + if (out instanceof BulkMemPhiNode p && p.isSplit(l._alias)) continue; if (out instanceof PhiNode p) { var r = p.in(0); for (int i = 1; i < p.nIns(); i++) { @@ -271,7 +277,7 @@ public class Scheduler { // Store nodes have anti-deps to load nodes. // So decrease the uses of these loads when the store is placed. for (var out: s.in(1)._outputs) { - if (out instanceof LoadNode) od(out).ifPresent(this::decUsers); + if (out instanceof LoadNode l && l._alias==s._alias) od(out).ifPresent(this::decUsers); } } } @@ -467,7 +473,8 @@ public class Scheduler { var data = mem.pop(); node = data.node; for(var out:node.in(1)._outputs) { - if (out instanceof LoadNode) od(out).ifPresent(d->d.users++); + if (out instanceof LoadNode l && l._alias==((StoreNode)node)._alias) + od(out).ifPresent(d->d.users++); } } } |
