From 1e2ebb397cbbca1a7d2fd35052c3b90a47bb5733 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 2 Oct 2026 14:27:49 -0700 Subject: README updates thru ch10a --- chapter10a/README.md | 101 ++++++++++------ chapter10a/docs/Makefile | 15 +-- chapter10a/docs/example1.json | 24 ++++ chapter10a/docs/example1.svg | 195 +++++++++++++++++++------------ chapter10a/docs/example2a.json | 31 +++++ chapter10a/docs/example2a.svg | 232 ++++++++++++++++++++++-------------- chapter10a/docs/example2b.json | 31 +++++ chapter10a/docs/example2b.svg | 222 +++++++++++++++++++++++------------ chapter10a/docs/example2c.json | 22 ++++ chapter10a/docs/example2c.svg | 163 ++++++++++++++++++-------- chapter10a/docs/lattice.gv | 25 +++- chapter10a/docs/lattice.svg | 260 ++++++++++++++++++++++------------------- 12 files changed, 867 insertions(+), 454 deletions(-) create mode 100644 chapter10a/docs/example1.json create mode 100644 chapter10a/docs/example2a.json create mode 100644 chapter10a/docs/example2b.json create mode 100644 chapter10a/docs/example2c.json (limited to 'chapter10a') diff --git a/chapter10a/README.md b/chapter10a/README.md index b9ea258a..6f51df28 100644 --- a/chapter10a/README.md +++ b/chapter10a/README.md @@ -31,6 +31,9 @@ different fields are independent. Chapter 10b will remove it. ![One chain orders stores and loads](docs/example1.svg) +The graphs show dependencies before local folding. Definitions appear above +their uses, except for loop backedges; arrows point from use to definition. + | Node | Inputs | Result | |----------|---|---| | `New` | Control and a struct type | A fresh, non-null object pointer | @@ -86,41 +89,6 @@ Every Return consumes the current whole-memory value. This keeps stores alive even when the returned scalar does not depend on them, or when the program returns the modified object itself. -## Local memory optimizations - -A load immediately following a store to the **same pointer and field** can use -the stored value. A store immediately following another store to the same -address can discard the earlier store when no other user needs it. Both the -pointer and field checks matter: two different fields of one object are -different addresses, as are the same fields of two different objects. - -A load can also move through a memory Phi when doing so exposes a useful -load-after-store fold. On a loop, the backedge must fold, preventing this rewrite -from repeatedly moving the load around the cycle. - -The reverse direction can save an operation: a Phi of matching Loads or Stores -can become one operation after the join. For example, these two writes: - -```java -if (arg) s.x = arg+1; -else s.x = arg+2; -``` - -can become `s.x = Phi(arg+1,arg+2)`. The general rewrite creates a separate, -correctly typed Phi for each differing operand, including memory and pointers; -identical operands need no Phi. An exact-class copy preserves the operation's -attributes. The proposed result must not widen the original Phi's type. - -Every arm must match the operation and field and have no control input. A Store -must have no other users, so moving it removes the original effect. A Load must -have no possible conflicting write or memory merge among its memory's users; -otherwise delaying the read could change its value. The check happens during -optimization, before any scheduler can supply explicit anti-dependency edges. - -The single chain is conservative. A store to `y` can prevent forwarding an -earlier store to `x`, even when the objects are identical. This is a missed -optimization, not a correctness problem; it motivates the next chapter. - ## Enhanced Type Lattice The Type Lattice for Simple has a major revision in this chapter. @@ -182,8 +150,9 @@ Within the type lattice, we now have the following domains: Memory top and memory bottom are `TypeMem.TOP` and `TypeMem.BOT`. Neither records the values stored in individual fields. * ![Tuple](docs/type-tuple.svg) represents a collection of results from one node, - such as Start's control, memory, and argument. The displayed shapes abbreviate - tuples of different lengths and their element-type lattices. + such as Start's control, memory, and argument. The pink headers identify tuples + of different lengths; each vertically stacked black `type` cell stands for + the full type lattice again, including the possibility of another tuple. We use the following operations on the lattice: @@ -299,6 +268,59 @@ To enable this behaviour, we make the following enhancements. ptr value, we convert to `0`. See `NotNode.compute()`. +## Local memory optimizations + +A load immediately following a store to the **same pointer and field** can use +the stored value. A store immediately following another store to the same +address can discard the earlier store when no other user needs it. Both the +pointer and field checks matter: two different fields of one object are +different addresses, as are the same fields of two different objects. + +A load can also move up through a memory Phi. This extends +[Chapter 5's push-through-Phi optimization](../chapter05/README.md#pushing-addition-up-through-a-phi): +there, arithmetic folds on the incoming paths; here, a load can fold against +a matching store. In graph notation, keeping the same pointer and field: + +```text +Load(Phi(r, m0, m1), p.x) + -> Phi(r, Load(m0, p.x), Load(m1, p.x)) +``` + +The Phi of memory becomes a Phi of loaded values. This chapter handles two +incoming paths and requires a load-after-store fold on at least one of them. +On a loop, that path must be the **backedge**: folding only on entry would +leave a load that could be pushed around the cycle indefinitely. As with the +arithmetic rewrite, exposing a fold is part of deciding to transform the +graph, not just a hoped-for cleanup afterward. See +[`LoadNode.idealize()`](src/main/java/com/seaofnodes/simple/node/LoadNode.java). + +The reverse direction extends +[Chapter 5's common-operation pull-down](../chapter05/README.md#example-3): +a Phi of matching Loads or Stores can become one operation after the join. +For example, these two writes: + +```java +if (arg) s.x = arg+1; +else s.x = arg+2; +``` + +can become `s.x = Phi(arg+1,arg+2)`. The general rewrite creates a separate, +correctly typed Phi for each differing operand, including memory and pointers. +We must be more careful here with memory ops; it is possible to lose some +type precision, so we check for that as part of the profitability. + +Also, a Store must have no other users, so moving it removes the original +effect. A Load must have no possible conflicting writes or memory merges among +its memory's users; otherwise delaying the read could change its value. Much +later, we will be adding anti-dependences, but for now we do a conservative +check. + +### Missing an easy one + +The single memory chain is correct but conservative. A store to `y` can +prevent forwarding an earlier store to `x`, even when the objects are +identical. This is a missed optimization and it motivates the next chapter. + ## Executing the graph The evaluator includes a small late scheduler. A load must execute before a @@ -306,6 +328,11 @@ later store that consumes the same memory definition, even though there is no ordinary data edge from the load to that store. These load/store anti-dependencies supplement the explicit graph edges. +For example, after allocating `p`, `int old = p.x; p.x = arg; return old;` +reads the value before the final store. In the graph below, Load and Store +consume the same memory state. The scheduler must execute the Load first; +there is no ordinary data edge between them. + ![A load must precede a clobbering store](docs/example2c.svg) The scheduler is sufficient to execute this chapter. Chapter 11 develops diff --git a/chapter10a/docs/Makefile b/chapter10a/docs/Makefile index 055882b2..6fa0f057 100644 --- a/chapter10a/docs/Makefile +++ b/chapter10a/docs/Makefile @@ -1,14 +1 @@ -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) +include ../../graph/docs.mk diff --git a/chapter10a/docs/example1.json b/chapter10a/docs/example1.json new file mode 100644 index 00000000..1b556c04 --- /dev/null +++ b/chapter10a/docs/example1.json @@ -0,0 +1,24 @@ +{ + "ver": 1, + "comp": "chapter10a/docs/example1.svg", + "step": 1, + "roots": [13], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 2, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}], "proj": {"par": 1, "idx": 0}}, + {"id": 3, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 1, "role": "MEM", "label": null}], "proj": {"par": 1, "idx": 1}}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "DATA", "label": null}], "proj": {"par": 1, "idx": 2}}, + {"id": 5, "label": "new Point", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": null}, + {"id": 6, "label": "#0", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 7, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "Store p.y", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "#3", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 10, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 11, "label": "Store p.y", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 12, "label": "Load p.x", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 11, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 0, "role": "DATA", "label": null}], "proj": null}, + {"id": 13, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}, {"idx": 1, "def": 11, "role": "MEM", "label": null}, {"idx": 2, "def": 12, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/chapter10a/docs/example1.svg b/chapter10a/docs/example1.svg index fdb4864c..b50701b0 100644 --- a/chapter10a/docs/example1.svg +++ b/chapter10a/docs/example1.svg @@ -1,73 +1,122 @@ - - - - - - -Memory - - - -M0 - -Initial memory - - - -X - -Store p.x = 3 - - - -X->M0 - - - - - -Y - -Store p.y = arg - - - -Y->X - - - - - -L - -Load p.x - - - -L->Y - - - - - -Return - -Return - - - -Return->Y - - - - - -Return->L - - - - - +#5[0] → #2 · CTRL#6[0] → #1 · ASSOC#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #6 · DATA#8[1] → #7 · MEM#8[2] → #5 · DATA#8[3] → #6 · DATA#9[0] → #1 · ASSOC#10[1] → #8 · MEM#10[2] → #5 · DATA#10[3] → #9 · DATA#11[1] → #10 · MEM#11[2] → #5 · DATA#11[3] → #4 · DATA#12[1] → #11 · MEM#12[2] → #5 · DATA#13[0] → #2 · CTRL#13[1] → #11 · MEM#13[2] → #12 · DATAStart  #1#1 Start +Type not computed + +$ctrl  #2/0#2 $ctrl +Projection 0 of #1 +Type not computed + +[0] → #1 CTRL$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMarg  #4/2#4 arg +Projection 2 of #1 +Type not computed + +[0] → #1 DATAnew Point  #5#5 new Point +Type not computed + +[0] → #2 CTRL0#0  #6#6 #0 +Type not computed + +[0] → #1 ASSOC0Store p.x  #7#7 Store p.x +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Store p.y  #8#8 Store p.y +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #6 DATA0123#3  #9#9 #3 +Type not computed + +[0] → #1 ASSOC0Store p.x  #10#10 Store p.x +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → #9 DATA0123Store p.y  #11#11 Store p.y +Type not computed + +[0] → — CTRL +[1] → #10 MEM +[2] → #5 DATA +[3] → #4 DATA0123Load p.x  #12#12 Load p.x +Type not computed + +[0] → — CTRL +[1] → #11 MEM +[2] → #5 DATA +[3] → — DATA0123Return  #13#13 Return +Type not computed + +[0] → #2 CTRL +[1] → #11 MEM +[2] → #12 DATA012 diff --git a/chapter10a/docs/example2a.json b/chapter10a/docs/example2a.json new file mode 100644 index 00000000..2fa04643 --- /dev/null +++ b/chapter10a/docs/example2a.json @@ -0,0 +1,31 @@ +{ + "ver": 1, + "comp": "chapter10a/docs/example2a.svg", + "step": 1, + "roots": [19], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 2, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}], "proj": {"par": 1, "idx": 0}}, + {"id": 3, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 1, "role": "MEM", "label": null}], "proj": {"par": 1, "idx": 1}}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "DATA", "label": null}], "proj": {"par": 1, "idx": 2}}, + {"id": 5, "label": "new Point", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": null}, + {"id": 6, "label": "#0", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 7, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "Store p.y", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 9, "role": "CTRL", "label": null}], "proj": {"par": 9, "idx": 0}}, + {"id": 11, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 9, "role": "CTRL", "label": null}], "proj": {"par": 9, "idx": 1}}, + {"id": 12, "label": "#3", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 13, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 12, "role": "DATA", "label": null}], "proj": null}, + {"id": 14, "label": "#4", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 15, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 14, "role": "DATA", "label": null}], "proj": null}, + {"id": 16, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 10, "role": "CTRL", "label": null}, {"idx": 2, "def": 11, "role": "CTRL", "label": null}], "proj": null}, + {"id": 17, "label": "Phi $mem", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 16, "role": "ASSOC", "label": null}, {"idx": 1, "def": 13, "role": "MEM", "label": null}, {"idx": 2, "def": 15, "role": "MEM", "label": null}], "proj": null}, + {"id": 18, "label": "Load p.x", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 17, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 0, "role": "DATA", "label": null}], "proj": null}, + {"id": 19, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 16, "role": "CTRL", "label": null}, {"idx": 1, "def": 17, "role": "MEM", "label": null}, {"idx": 2, "def": 18, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 9, "par": 0, "nodes": [7, 8, 9, 10, 11, 13, 15, 16, 17]} + ] +} diff --git a/chapter10a/docs/example2a.svg b/chapter10a/docs/example2a.svg index f0bbf531..eb43548f 100644 --- a/chapter10a/docs/example2a.svg +++ b/chapter10a/docs/example2a.svg @@ -1,85 +1,147 @@ - - - - - - -Memory - - - -M - -Incoming memory - - - -A - -True: Store x - - - -A->M - - - - - -B - -False: Store x - - - -B->M - - - - - -P - -Phi(memory) - - - -P->A - - - - - -P->B - - - - - -Region - -Region - - - -P->Region - - - - - -Return - -Return - - - -Return->P - - - - - +#5[0] → #2 · CTRL#6[0] → #1 · ASSOC#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #6 · DATA#8[1] → #7 · MEM#8[2] → #5 · DATA#8[3] → #6 · DATA#9[0] → #2 · CTRL#9[1] → #4 · DATA#12[0] → #1 · ASSOC#13[1] → #8 · MEM#13[2] → #5 · DATA#13[3] → #12 · DATA#14[0] → #1 · ASSOC#15[1] → #8 · MEM#15[2] → #5 · DATA#15[3] → #14 · DATA#16[1] → #10 · CTRL#16[2] → #11 · CTRL#17[1] → #13 · MEM#17[2] → #15 · MEM#18[1] → #17 · MEM#18[2] → #5 · DATA#19[0] → #16 · CTRL#19[1] → #17 · MEM#19[2] → #18 · DATAStart  #1#1 Start +Type not computed + +$ctrl  #2/0#2 $ctrl +Projection 0 of #1 +Type not computed + +[0] → #1 CTRL$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMarg  #4/2#4 arg +Projection 2 of #1 +Type not computed + +[0] → #1 DATAnew Point  #5#5 new Point +Type not computed + +[0] → #2 CTRL0#0  #6#6 #0 +Type not computed + +[0] → #1 ASSOC0Store p.x  #7#7 Store p.x +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Store p.y  #8#8 Store p.y +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #6 DATA0123If  #9#9 If +Type not computed + +[0] → #2 CTRL +[1] → #4 DATA01True  #10/0#10 True +Projection 0 of #9 +Type not computed + +[0] → #9 CTRLFalse  #11/1#11 False +Projection 1 of #9 +Type not computed + +[0] → #9 CTRL#3  #12#12 #3 +Type not computed + +[0] → #1 ASSOC0Store p.x  #13#13 Store p.x +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → #12 DATA0123#4  #14#14 #4 +Type not computed + +[0] → #1 ASSOC0Store p.x  #15#15 Store p.x +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → #14 DATA0123Region  #16#16 Region +Type not computed + +[0] → — ASSOC +[1] → #10 CTRL +[2] → #11 CTRL012Phi $mem  #17#17 Phi $mem +Type not computed + +[0] → #16 ASSOC +[1] → #13 MEM +[2] → #15 MEM[0] → #16012Load p.x  #18#18 Load p.x +Type not computed + +[0] → — CTRL +[1] → #17 MEM +[2] → #5 DATA +[3] → — DATA0123Return  #19#19 Return +Type not computed + +[0] → #16 CTRL +[1] → #17 MEM +[2] → #18 DATA012If  #9If · 9 nodes−Fold region diff --git a/chapter10a/docs/example2b.json b/chapter10a/docs/example2b.json new file mode 100644 index 00000000..50fbfc74 --- /dev/null +++ b/chapter10a/docs/example2b.json @@ -0,0 +1,31 @@ +{ + "ver": 1, + "comp": "chapter10a/docs/example2b.svg", + "step": 1, + "roots": [19], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 2, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}], "proj": {"par": 1, "idx": 0}}, + {"id": 3, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 1, "role": "MEM", "label": null}], "proj": {"par": 1, "idx": 1}}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "DATA", "label": null}], "proj": {"par": 1, "idx": 2}}, + {"id": 5, "label": "new Point", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": null}, + {"id": 6, "label": "#0", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 7, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "Store p.y", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "Loop", "type": null, "kind": "LOOP", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 2, "role": "CTRL", "label": null}, {"idx": 2, "def": 13, "role": "CTRL", "label": null}], "proj": null}, + {"id": 10, "label": "Phi $mem", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 9, "role": "ASSOC", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 15, "role": "MEM", "label": null}], "proj": null}, + {"id": 11, "label": "Phi arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 9, "role": "ASSOC", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 17, "role": "DATA", "label": null}], "proj": null}, + {"id": 12, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 9, "role": "CTRL", "label": null}, {"idx": 1, "def": 11, "role": "DATA", "label": null}], "proj": null}, + {"id": 13, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 12, "role": "CTRL", "label": null}], "proj": {"par": 12, "idx": 0}}, + {"id": 14, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 12, "role": "CTRL", "label": null}], "proj": {"par": 12, "idx": 1}}, + {"id": 15, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 11, "role": "DATA", "label": null}], "proj": null}, + {"id": 16, "label": "#1", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 17, "label": "-", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 11, "role": "DATA", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 18, "label": "Load p.x", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 0, "role": "DATA", "label": null}], "proj": null}, + {"id": 19, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 14, "role": "CTRL", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 18, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 9, "par": 0, "nodes": [7, 8, 9, 10, 11, 12, 13, 14, 15, 17]} + ] +} diff --git a/chapter10a/docs/example2b.svg b/chapter10a/docs/example2b.svg index 77ebec85..e5322a61 100644 --- a/chapter10a/docs/example2b.svg +++ b/chapter10a/docs/example2b.svg @@ -1,74 +1,148 @@ - - - - - - -Memory - - - -P - -Phi(memory) - - - -S - -Loop-body Store - - - -P->S - - - - - -Entry - -Entry - - - -P->Entry - - - - - -Loop - -Loop - - - -P->Loop - - - - - -S->P - - - - - -Return - -Return - - - -Return->P - - - - - - +#5[0] → #2 · CTRL#6[0] → #1 · ASSOC#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #6 · DATA#8[1] → #7 · MEM#8[2] → #5 · DATA#8[3] → #6 · DATA#9[1] → #2 · CTRL#9[2] → #13 · CTRL#10[1] → #8 · MEM#10[2] → #15 · MEM#11[1] → #4 · DATA#11[2] → #17 · DATA#12[0] → #9 · CTRL#12[1] → #11 · DATA#15[1] → #10 · MEM#15[2] → #5 · DATA#15[3] → #11 · DATA#16[0] → #1 · ASSOC#17[1] → #11 · DATA#17[2] → #16 · DATA#18[1] → #10 · MEM#18[2] → #5 · DATA#19[0] → #14 · CTRL#19[1] → #10 · MEM#19[2] → #18 · DATAStart  #1#1 Start +Type not computed + +$ctrl  #2/0#2 $ctrl +Projection 0 of #1 +Type not computed + +[0] → #1 CTRL$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMarg  #4/2#4 arg +Projection 2 of #1 +Type not computed + +[0] → #1 DATAnew Point  #5#5 new Point +Type not computed + +[0] → #2 CTRL0#0  #6#6 #0 +Type not computed + +[0] → #1 ASSOC0Store p.x  #7#7 Store p.x +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Store p.y  #8#8 Store p.y +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #6 DATA0123Loop  #9#9 Loop +Type not computed + +[0] → — ASSOC +[1] → #2 CTRL +[2] → #13 CTRL012Phi $mem  #10#10 Phi $mem +Type not computed + +[0] → #9 ASSOC +[1] → #8 MEM +[2] → #15 MEM[0] → #9012Phi arg  #11#11 Phi arg +Type not computed + +[0] → #9 ASSOC +[1] → #4 DATA +[2] → #17 DATA[0] → #9012If  #12#12 If +Type not computed + +[0] → #9 CTRL +[1] → #11 DATA01True  #13/0#13 True +Projection 0 of #12 +Type not computed + +[0] → #12 CTRLFalse  #14/1#14 False +Projection 1 of #12 +Type not computed + +[0] → #12 CTRLStore p.x  #15#15 Store p.x +Type not computed + +[0] → — CTRL +[1] → #10 MEM +[2] → #5 DATA +[3] → #11 DATA0123#1  #16#16 #1 +Type not computed + +[0] → #1 ASSOC0-  #17#17 - +Type not computed + +[0] → — CTRL +[1] → #11 DATA +[2] → #16 DATA012Load p.x  #18#18 Load p.x +Type not computed + +[0] → — CTRL +[1] → #10 MEM +[2] → #5 DATA +[3] → — DATA0123Return  #19#19 Return +Type not computed + +[0] → #14 CTRL +[1] → #10 MEM +[2] → #18 DATA012Loop  #9Loop · 10 nodes−Fold region diff --git a/chapter10a/docs/example2c.json b/chapter10a/docs/example2c.json new file mode 100644 index 00000000..4e7e096b --- /dev/null +++ b/chapter10a/docs/example2c.json @@ -0,0 +1,22 @@ +{ + "ver": 1, + "comp": "chapter10a/docs/example2c.svg", + "step": 1, + "roots": [11], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 2, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}], "proj": {"par": 1, "idx": 0}}, + {"id": 3, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 1, "role": "MEM", "label": null}], "proj": {"par": 1, "idx": 1}}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "DATA", "label": null}], "proj": {"par": 1, "idx": 2}}, + {"id": 5, "label": "new Point", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": null}, + {"id": 6, "label": "#0", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 7, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "Store p.y", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "Load p.x", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 0, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 11, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/chapter10a/docs/example2c.svg b/chapter10a/docs/example2c.svg index 2aa8fa2d..eb8fad03 100644 --- a/chapter10a/docs/example2c.svg +++ b/chapter10a/docs/example2c.svg @@ -1,50 +1,113 @@ - - - - - - -Memory - - - -M - -Prior memory - - - -L - -Load p.x - - - -L->M - - - - - -S - -Store p.x - - - -S->M - - - - - -S->L - - -execute load first - - - +#5[0] → #2 · CTRL#6[0] → #1 · ASSOC#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #6 · DATA#8[1] → #7 · MEM#8[2] → #5 · DATA#8[3] → #6 · DATA#9[1] → #8 · MEM#9[2] → #5 · DATA#10[1] → #8 · MEM#10[2] → #5 · DATA#10[3] → #4 · DATA#11[0] → #2 · CTRL#11[1] → #10 · MEM#11[2] → #9 · DATAStart  #1#1 Start +Type not computed + +$ctrl  #2/0#2 $ctrl +Projection 0 of #1 +Type not computed + +[0] → #1 CTRL$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMarg  #4/2#4 arg +Projection 2 of #1 +Type not computed + +[0] → #1 DATAnew Point  #5#5 new Point +Type not computed + +[0] → #2 CTRL0#0  #6#6 #0 +Type not computed + +[0] → #1 ASSOC0Store p.x  #7#7 Store p.x +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Store p.y  #8#8 Store p.y +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #6 DATA0123Load p.x  #9#9 Load p.x +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → — DATA0123Store p.x  #10#10 Store p.x +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → #4 DATA0123Return  #11#11 Return +Type not computed + +[0] → #2 CTRL +[1] → #10 MEM +[2] → #9 DATA012 diff --git a/chapter10a/docs/lattice.gv b/chapter10a/docs/lattice.gv index eb4d7fb1..b56a3073 100644 --- a/chapter10a/docs/lattice.gv +++ b/chapter10a/docs/lattice.gv @@ -91,9 +91,28 @@ digraph Lattice { 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]; + // Each black element stands for a recursively nested type lattice. + TUPLE1 [shape=plain, label=< + + + +
tuple
type
+ >]; + TUPLE2 [shape=plain, label=< + + + + +
tuple
type
type
+ >]; + TUPLEN [shape=plain, label=< + + + + + +
tuple
type
…
type
+ >]; {rank=same; TUPLE1; TUPLE2; TUPLEN;} TUPLE1 -> TUPLE2 -> TUPLEN [style=invis]; TUPLE_TOP -> {TUPLE1 TUPLE2 TUPLEN}; diff --git a/chapter10a/docs/lattice.svg b/chapter10a/docs/lattice.svg index c8bed535..006ab762 100644 --- a/chapter10a/docs/lattice.svg +++ b/chapter10a/docs/lattice.svg @@ -4,122 +4,122 @@ - - + + Lattice - + cluster_control - -Control + +Control cluster_integer - -Integer + +Integer cluster_pointer - -Pointer = nullability × struct type + +Pointer = nullability × struct type cluster_struct - -Struct -named collection of named scalar types + +Struct +named collection of named scalar types cluster_memory - -Memory + +Memory cluster_tuple - -Tuple -collection of types + +Tuple +collection of types TOP - -⊤ + +⊤ XCTRL - -⊤:ctrl + +⊤:ctrl TOP->XCTRL - - + + INT_TOP - -⊤:int + +⊤:int TOP->INT_TOP - - + + PTR_TOP - -⊤:ptr -[*⊤:struct] + +⊤:ptr +[*⊤:struct] TOP->PTR_TOP - - + + STRUCT_TOP - -⊤:struct -[struct top] + +⊤:struct +[struct top] TOP->STRUCT_TOP - - + + MEM_TOP - -⊤:mem + +⊤:mem TOP->MEM_TOP - - + + TUPLE_TOP - -⊤:tuple + +⊤:tuple TOP->TUPLE_TOP - - + + @@ -136,7 +136,7 @@ XCTRL->CTRL - + @@ -155,8 +155,8 @@ INT_TOP->INT_NEG - - + + @@ -167,8 +167,8 @@ INT_TOP->INT_ZERO - - + + @@ -179,8 +179,8 @@ INT_TOP->INT_POS - - + + @@ -218,50 +218,50 @@ PTR_NULL - -null + +null PTR_TOP->PTR_NULL - - + + PTR_PERSON - -*Person + +*Person PTR_TOP->PTR_PERSON - - + + PTR_S1 - -*s1 + +*s1 PTR_TOP->PTR_S1 - - + + PTR_MORE - -*s2, … + +*s2, … PTR_TOP->PTR_MORE - - + + @@ -286,8 +286,8 @@ PTR_NULL->PTR_PERSON_NIL - - + + @@ -298,8 +298,8 @@ PTR_NULL->PTR_S1_NIL - - + + @@ -310,8 +310,8 @@ PTR_NULL->PTR_MORE_NIL - - + + @@ -330,41 +330,41 @@ PTR_PERSON->PTR_ANY - - + + PTR_PERSON->PTR_PERSON_NIL - - + + PTR_S1->PTR_ANY - - + + PTR_S1->PTR_S1_NIL - - + + PTR_MORE->PTR_ANY - - + + PTR_MORE->PTR_MORE_NIL - - + + @@ -396,8 +396,8 @@ STRUCT_TOP->STRUCT_PERSON - - + + @@ -409,8 +409,8 @@ STRUCT_TOP->STRUCT_S1 - - + + @@ -422,8 +422,8 @@ STRUCT_TOP->STRUCT_S2 - - + + @@ -434,8 +434,8 @@ STRUCT_TOP->STRUCT_MORE - - + + @@ -487,7 +487,7 @@ MEM_TOP->MEM_BOT - + @@ -500,70 +500,94 @@ TUPLE1 - -(type) + + + +tuple + + +type TUPLE_TOP->TUPLE1 - - + + TUPLE2 - -(type, type) + + + +tuple + + +type + + +type TUPLE_TOP->TUPLE2 - - + + TUPLEN - -(type, …) + + + +tuple + + +type + + +… + + +type TUPLE_TOP->TUPLEN - - + + TUPLE_BOT - -⊥:tuple + +⊥:tuple TUPLE_BOT->BOT - - + + TUPLE1->TUPLE_BOT - - + + TUPLE2->TUPLE_BOT - - + + TUPLEN->TUPLE_BOT - - + + -- cgit v1.2.3