From 22df891893d30e9906d0b14fc3ae5d8e67d500b2 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 3 Oct 2026 14:03:48 -0700 Subject: Chapter renumber, and split ch 17 Renumber chapters 10a, 10b, 11, 12, 13, 14 -> 10, 11, 13, 12, [11,14]. Split ch 17 into a 17a and 17b; shuffle around im/mutable syntax to be consistent, and present it more slowly. THe new immutable syntax is pushed through all later chapters --- chapter10/docs/10-grammar.md | 125 ++++++ chapter10/docs/Makefile | 1 + chapter10/docs/example1.gv | 16 + chapter10/docs/example1.json | 23 ++ chapter10/docs/example1.svg | 118 ++++++ chapter10/docs/example2a.gv | 17 + chapter10/docs/example2a.json | 26 ++ chapter10/docs/example2a.svg | 130 ++++++ chapter10/docs/example2b.gv | 19 + chapter10/docs/example2b.json | 27 ++ chapter10/docs/example2b.svg | 135 +++++++ chapter10/docs/example2c.gv | 14 + chapter10/docs/example2c.json | 21 + chapter10/docs/example2c.svg | 109 +++++ chapter10/docs/lattice.gv | 127 ++++++ chapter10/docs/lattice.svg | 593 ++++++++++++++++++++++++++++ chapter10/docs/load-after-store-after.json | 19 + chapter10/docs/load-after-store-after.svg | 97 +++++ chapter10/docs/load-after-store-before.json | 20 + chapter10/docs/load-after-store-before.svg | 103 +++++ chapter10/docs/type-control.svg | 5 + chapter10/docs/type-integer.svg | 5 + chapter10/docs/type-memory.svg | 5 + chapter10/docs/type-pointer.svg | 5 + chapter10/docs/type-struct.svg | 5 + chapter10/docs/type-tuple.svg | 5 + 26 files changed, 1770 insertions(+) create mode 100644 chapter10/docs/10-grammar.md create mode 100644 chapter10/docs/Makefile create mode 100644 chapter10/docs/example1.gv create mode 100644 chapter10/docs/example1.json create mode 100644 chapter10/docs/example1.svg create mode 100644 chapter10/docs/example2a.gv create mode 100644 chapter10/docs/example2a.json create mode 100644 chapter10/docs/example2a.svg create mode 100644 chapter10/docs/example2b.gv create mode 100644 chapter10/docs/example2b.json create mode 100644 chapter10/docs/example2b.svg create mode 100644 chapter10/docs/example2c.gv create mode 100644 chapter10/docs/example2c.json create mode 100644 chapter10/docs/example2c.svg create mode 100644 chapter10/docs/lattice.gv create mode 100644 chapter10/docs/lattice.svg create mode 100644 chapter10/docs/load-after-store-after.json create mode 100644 chapter10/docs/load-after-store-after.svg create mode 100644 chapter10/docs/load-after-store-before.json create mode 100644 chapter10/docs/load-after-store-before.svg create mode 100644 chapter10/docs/type-control.svg create mode 100644 chapter10/docs/type-integer.svg create mode 100644 chapter10/docs/type-memory.svg create mode 100644 chapter10/docs/type-pointer.svg create mode 100644 chapter10/docs/type-struct.svg create mode 100644 chapter10/docs/type-tuple.svg (limited to 'chapter10/docs') diff --git a/chapter10/docs/10-grammar.md b/chapter10/docs/10-grammar.md new file mode 100644 index 00000000..b76531d5 --- /dev/null +++ b/chapter10/docs/10-grammar.md @@ -0,0 +1,125 @@ +# Grammar for Chapter 10 + +```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/chapter10/docs/Makefile b/chapter10/docs/Makefile new file mode 100644 index 00000000..6fa0f057 --- /dev/null +++ b/chapter10/docs/Makefile @@ -0,0 +1 @@ +include ../../graph/docs.mk diff --git a/chapter10/docs/example1.gv b/chapter10/docs/example1.gv new file mode 100644 index 00000000..9585b8e4 --- /dev/null +++ b/chapter10/docs/example1.gv @@ -0,0 +1,16 @@ +digraph Memory { + // IR styles match graph/web/render.js; arrows are use -> definition. + graph [bgcolor="#fafbfc" fontname="Helvetica" nodesep=0.35 ranksep=0.55 splines=ortho]; + node [fontname="Helvetica" fontsize=12 color="#758191" fontcolor="#152330" shape=box style="rounded,filled" fillcolor="#edf3f7"]; + edge [fontname="Helvetica" fontsize=9 color="#536477" fontcolor="#364352" arrowsize=0.7 penwidth=1.5]; + + rankdir=RL; + + M0 [label="Initial memory" shape=octagon style="filled" fillcolor="#dcecff"]; + X [label="Store p.x = 3" shape=octagon style="filled" fillcolor="#dcecff"]; + Y [label="Store p.y = arg" shape=octagon style="filled" fillcolor="#dcecff"]; + L [label="Load p.x" shape=box style="rounded,filled" fillcolor="#edf3f7"]; + L -> Y -> X -> M0 [color="#2867b2"]; + Return -> Y [color="#2867b2"]; Return -> L; + Return [shape=box style="filled" fillcolor="#fff1c4"]; +} diff --git a/chapter10/docs/example1.json b/chapter10/docs/example1.json new file mode 100644 index 00000000..a111ae88 --- /dev/null +++ b/chapter10/docs/example1.json @@ -0,0 +1,23 @@ +{ + "ver": 1, + "comp": "chapter10/docs/example1.svg", + "step": 1, + "roots": [13], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"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": 0, "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": 0, "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/chapter10/docs/example1.svg b/chapter10/docs/example1.svg new file mode 100644 index 00000000..d98e0ccd --- /dev/null +++ b/chapter10/docs/example1.svg @@ -0,0 +1,118 @@ +#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[1] → #11 · MEM#13[2] → #12 · DATAStart  #1#1 Start +Type not computed + +$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] → — 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] → — CTRL +[1] → #11 MEM +[2] → #12 DATA012 diff --git a/chapter10/docs/example2a.gv b/chapter10/docs/example2a.gv new file mode 100644 index 00000000..93a8a904 --- /dev/null +++ b/chapter10/docs/example2a.gv @@ -0,0 +1,17 @@ +digraph Memory { + // IR styles match graph/web/render.js; arrows are use -> definition. + graph [bgcolor="#fafbfc" fontname="Helvetica" nodesep=0.35 ranksep=0.55 splines=ortho]; + node [fontname="Helvetica" fontsize=12 color="#758191" fontcolor="#152330" shape=box style="rounded,filled" fillcolor="#edf3f7"]; + edge [fontname="Helvetica" fontsize=9 color="#536477" fontcolor="#364352" arrowsize=0.7 penwidth=1.5]; + + rankdir=RL; + + M [label="Incoming memory" shape=octagon style="filled" fillcolor="#dcecff"]; + A [label="True: Store x" shape=octagon style="filled" fillcolor="#dcecff"]; + B [label="False: Store x" shape=octagon style="filled" fillcolor="#dcecff"]; + P [label="Phi(memory)" shape=hexagon style="filled" fillcolor="#f5e4fa"]; + P -> A -> M [color="#2867b2"]; P -> B -> M [color="#2867b2"]; + P -> Region [style=dashed,color="#9396a3"]; Return -> P [color="#2867b2"]; + Return [shape=box style="filled" fillcolor="#fff1c4"]; + Region [shape=trapezium style="filled" fillcolor="#fff1c4"]; +} diff --git a/chapter10/docs/example2a.json b/chapter10/docs/example2a.json new file mode 100644 index 00000000..660c72e8 --- /dev/null +++ b/chapter10/docs/example2a.json @@ -0,0 +1,26 @@ +{ + "ver": 1, + "comp": "chapter10/docs/example2a.svg", + "step": 1, + "roots": [19], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 1, "role": "MEM", "label": null}], "proj": {"par": 1, "idx": 1}}, + {"id": 5, "label": "new Point", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "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": 10, "label": "True", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 0}}, + {"id": 11, "label": "False", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "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": 10, "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": 11, "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": 17, "label": "Phi $mem", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "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": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 17, "role": "MEM", "label": null}, {"idx": 2, "def": 18, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/chapter10/docs/example2a.svg b/chapter10/docs/example2a.svg new file mode 100644 index 00000000..b7664907 --- /dev/null +++ b/chapter10/docs/example2a.svg @@ -0,0 +1,130 @@ +#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#12[0] → #1 · ASSOC#13[0] → #10 · CTRL#13[1] → #8 · MEM#13[2] → #5 · DATA#13[3] → #12 · DATA#14[0] → #1 · ASSOC#15[0] → #11 · CTRL#15[1] → #8 · MEM#15[2] → #5 · DATA#15[3] → #14 · DATA#17[1] → #13 · MEM#17[2] → #15 · MEM#18[1] → #17 · MEM#18[2] → #5 · DATA#19[1] → #17 · MEM#19[2] → #18 · DATAStart  #1#1 Start +Type not computed + +$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMnew Point  #5#5 new Point +Type not computed + +[0] → — 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 DATA0123True  #10/0#10 True +Projection 0 of #0 +Type not computed + +False  #11/1#11 False +Projection 1 of #0 +Type not computed + +#3  #12#12 #3 +Type not computed + +[0] → #1 ASSOC0Store p.x  #13#13 Store p.x +Type not computed + +[0] → #10 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] → #11 CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → #14 DATA0123Phi $mem  #17#17 Phi $mem +Type not computed + +[0] → — ASSOC +[1] → #13 MEM +[2] → #15 MEM012Load 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] → — CTRL +[1] → #17 MEM +[2] → #18 DATA012 diff --git a/chapter10/docs/example2b.gv b/chapter10/docs/example2b.gv new file mode 100644 index 00000000..c7d64509 --- /dev/null +++ b/chapter10/docs/example2b.gv @@ -0,0 +1,19 @@ +digraph Memory { + // IR styles match graph/web/render.js; arrows are use -> definition. + graph [bgcolor="#fafbfc" fontname="Helvetica" nodesep=0.35 ranksep=0.55 splines=ortho]; + node [fontname="Helvetica" fontsize=12 color="#758191" fontcolor="#152330" shape=box style="rounded,filled" fillcolor="#edf3f7"]; + edge [fontname="Helvetica" fontsize=9 color="#536477" fontcolor="#364352" arrowsize=0.7 penwidth=1.5]; + + rankdir=RL; + + P [label="Phi(memory)" shape=hexagon style="filled" fillcolor="#f5e4fa"]; + S [label="Loop-body Store" shape=octagon style="filled" fillcolor="#dcecff"]; + P -> Entry [color="#2867b2"]; + P -> S [color="#2867b2",constraint=false]; // Backedge must not place Store before Phi. + S -> P [color="#2867b2"]; + P -> Loop [style=dashed,color="#9396a3"]; Return -> P [color="#2867b2"]; + Return -> S [style=invis]; // Layout only: Phi, Store, Return from left to right. + Return [shape=box style="filled" fillcolor="#fff1c4"]; + Entry [shape=octagon style="filled" fillcolor="#dcecff"]; + Loop [shape=box style="rounded,filled" fillcolor="#ffe0ab"]; +} diff --git a/chapter10/docs/example2b.json b/chapter10/docs/example2b.json new file mode 100644 index 00000000..da2fc557 --- /dev/null +++ b/chapter10/docs/example2b.json @@ -0,0 +1,27 @@ +{ + "ver": 1, + "comp": "chapter10/docs/example2b.svg", + "step": 1, + "roots": [19], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"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": 0, "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": 10, "label": "Phi $mem", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "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": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 17, "role": "DATA", "label": null}], "proj": null}, + {"id": 13, "label": "True", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 0}}, + {"id": 14, "label": "False", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 1}}, + {"id": 15, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 13, "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": 14, "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": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 18, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/chapter10/docs/example2b.svg b/chapter10/docs/example2b.svg new file mode 100644 index 00000000..1feb91a3 --- /dev/null +++ b/chapter10/docs/example2b.svg @@ -0,0 +1,135 @@ +#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#10[1] → #8 · MEM#10[2] → #15 · MEM#11[1] → #4 · DATA#11[2] → #17 · DATA#15[0] → #13 · CTRL#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[0] → #14 · CTRL#18[1] → #10 · MEM#18[2] → #5 · DATA#19[1] → #10 · MEM#19[2] → #18 · DATAStart  #1#1 Start +Type not computed + +$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] → — 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 DATA0123Phi $mem  #10#10 Phi $mem +Type not computed + +[0] → — ASSOC +[1] → #8 MEM +[2] → #15 MEM012Phi arg  #11#11 Phi arg +Type not computed + +[0] → — ASSOC +[1] → #4 DATA +[2] → #17 DATA012True  #13/0#13 True +Projection 0 of #0 +Type not computed + +False  #14/1#14 False +Projection 1 of #0 +Type not computed + +Store p.x  #15#15 Store p.x +Type not computed + +[0] → #13 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] → #14 CTRL +[1] → #10 MEM +[2] → #5 DATA +[3] → — DATA0123Return  #19#19 Return +Type not computed + +[0] → — CTRL +[1] → #10 MEM +[2] → #18 DATA012 diff --git a/chapter10/docs/example2c.gv b/chapter10/docs/example2c.gv new file mode 100644 index 00000000..f3a52b4d --- /dev/null +++ b/chapter10/docs/example2c.gv @@ -0,0 +1,14 @@ +digraph Memory { + // IR styles match graph/web/render.js; arrows are use -> definition. + graph [bgcolor="#fafbfc" fontname="Helvetica" nodesep=0.35 ranksep=0.55 splines=ortho]; + node [fontname="Helvetica" fontsize=12 color="#758191" fontcolor="#152330" shape=box style="rounded,filled" fillcolor="#edf3f7"]; + edge [fontname="Helvetica" fontsize=9 color="#536477" fontcolor="#364352" arrowsize=0.7 penwidth=1.5]; + + rankdir=RL; + + M [label="Prior memory" shape=octagon style="filled" fillcolor="#dcecff"]; + L [label="Load p.x" shape=box style="rounded,filled" fillcolor="#edf3f7"]; + S [label="Store p.x" shape=octagon style="filled" fillcolor="#dcecff"]; + L -> M [color="#2867b2"]; S -> M [color="#2867b2"]; + S -> L [style=dashed,xlabel="execute load first"]; +} diff --git a/chapter10/docs/example2c.json b/chapter10/docs/example2c.json new file mode 100644 index 00000000..8623ab8d --- /dev/null +++ b/chapter10/docs/example2c.json @@ -0,0 +1,21 @@ +{ + "ver": 1, + "comp": "chapter10/docs/example2c.svg", + "step": 1, + "roots": [11], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"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": 0, "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": 0, "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/chapter10/docs/example2c.svg b/chapter10/docs/example2c.svg new file mode 100644 index 00000000..f7f7bce3 --- /dev/null +++ b/chapter10/docs/example2c.svg @@ -0,0 +1,109 @@ +#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[1] → #10 · MEM#11[2] → #9 · DATAStart  #1#1 Start +Type not computed + +$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] → — 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] → — CTRL +[1] → #10 MEM +[2] → #9 DATA012 diff --git a/chapter10/docs/lattice.gv b/chapter10/docs/lattice.gv new file mode 100644 index 00000000..b56a3073 --- /dev/null +++ b/chapter10/docs/lattice.gv @@ -0,0 +1,127 @@ +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: int", 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"; fontname="Arial"; color="#cccccc"; + node [fillcolor="#00008b", fontcolor=white]; + MEM_TOP [label="⊤:mem"]; + MEM_BOT [label="⊥:mem"]; + MEM_TOP -> MEM_BOT; + } + + subgraph cluster_tuple { + label="Tuple\ncollection of types"; + fontname="Arial"; color="#cccccc"; + node [fillcolor="#ffc0cb"]; + TUPLE_TOP [label="⊤:tuple"]; + TUPLE_BOT [label="⊥:tuple"]; + // Each black element stands for a recursively nested type lattice. + TUPLE1 [shape=plain, label=< + + + +
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}; + {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/chapter10/docs/lattice.svg b/chapter10/docs/lattice.svg new file mode 100644 index 00000000..006ab762 --- /dev/null +++ b/chapter10/docs/lattice.svg @@ -0,0 +1,593 @@ + + + + + + +Lattice + + +cluster_control + +Control + + +cluster_integer + +Integer + + +cluster_pointer + +Pointer = nullability × struct type + + +cluster_struct + +Struct +named collection of named scalar types + + +cluster_memory + +Memory + + +cluster_tuple + +Tuple +collection of types + + + +TOP + +⊤ + + + +XCTRL + +⊤:ctrl + + + +TOP->XCTRL + + + + + +INT_TOP + +⊤:int + + + +TOP->INT_TOP + + + + + +PTR_TOP + +⊤:ptr +[*⊤:struct] + + + +TOP->PTR_TOP + + + + + +STRUCT_TOP + +⊤:struct +[struct top] + + + +TOP->STRUCT_TOP + + + + + +MEM_TOP + +⊤:mem + + + +TOP->MEM_TOP + + + + + +TUPLE_TOP + +⊤:tuple + + + +TOP->TUPLE_TOP + + + + + +BOT + +⊥ + + + +CTRL + +⊥:ctrl + + + +XCTRL->CTRL + + + + + + +CTRL->BOT + + + + + +INT_NEG + +… −2, −1 + + + +INT_TOP->INT_NEG + + + + + +INT_ZERO + +0 + + + +INT_TOP->INT_ZERO + + + + + +INT_POS + +1, 2, … + + + +INT_TOP->INT_POS + + + + + + +INT_BOT + +⊥:int + + + +INT_BOT->BOT + + + + + +INT_NEG->INT_BOT + + + + + + +INT_ZERO->INT_BOT + + + + + + +INT_POS->INT_BOT + + + + + +PTR_NULL + +null + + + +PTR_TOP->PTR_NULL + + + + + +PTR_PERSON + +*Person + + + +PTR_TOP->PTR_PERSON + + + + + +PTR_S1 + +*s1 + + + +PTR_TOP->PTR_S1 + + + + + +PTR_MORE + +*s2, … + + + +PTR_TOP->PTR_MORE + + + + + + +PTR_BOT + +⊥:ptr +[*⊥:struct?] + + + +PTR_BOT->BOT + + + + + +PTR_PERSON_NIL + +*Person? + + + +PTR_NULL->PTR_PERSON_NIL + + + + + +PTR_S1_NIL + +*s1? + + + +PTR_NULL->PTR_S1_NIL + + + + + +PTR_MORE_NIL + +*s2?, … + + + +PTR_NULL->PTR_MORE_NIL + + + + + +PTR_ANY + +*⊥:struct +[ptr any struct] + + + +PTR_ANY->PTR_BOT + + + + + + +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 + + + + + +PTR_PERSON_NIL->PTR_BOT + + + + + + +PTR_S1_NIL->PTR_BOT + + + + + + +PTR_MORE_NIL->PTR_BOT + + + + + +STRUCT_PERSON + +Person +age: int + + + +STRUCT_TOP->STRUCT_PERSON + + + + + +STRUCT_S1 + +s1 +x: int + + + +STRUCT_TOP->STRUCT_S1 + + + + + +STRUCT_S2 + +s2 +x: int, y: int + + + +STRUCT_TOP->STRUCT_S2 + + + + + +STRUCT_MORE + +… + + + +STRUCT_TOP->STRUCT_MORE + + + + + + +STRUCT_BOT + +⊥:struct +[struct bottom] + + + +STRUCT_BOT->BOT + + + + + +STRUCT_PERSON->STRUCT_BOT + + + + + + +STRUCT_S1->STRUCT_BOT + + + + + + +STRUCT_S2->STRUCT_BOT + + + + + + +STRUCT_MORE->STRUCT_BOT + + + + + +MEM_BOT + +⊥:mem + + + +MEM_TOP->MEM_BOT + + + + + + +MEM_BOT->BOT + + + + + +TUPLE1 + + + +tuple + + +type + + + +TUPLE_TOP->TUPLE1 + + + + + +TUPLE2 + + + +tuple + + +type + + +type + + + +TUPLE_TOP->TUPLE2 + + + + + +TUPLEN + + + +tuple + + +type + + +… + + +type + + + +TUPLE_TOP->TUPLEN + + + + + +TUPLE_BOT + +⊥:tuple + + + +TUPLE_BOT->BOT + + + + + +TUPLE1->TUPLE_BOT + + + + + + +TUPLE2->TUPLE_BOT + + + + + + +TUPLEN->TUPLE_BOT + + + + + diff --git a/chapter10/docs/load-after-store-after.json b/chapter10/docs/load-after-store-after.json new file mode 100644 index 00000000..d27efe5b --- /dev/null +++ b/chapter10/docs/load-after-store-after.json @@ -0,0 +1,19 @@ +{ + "ver": 1, + "comp": "load-after-store-after", + "step": 1, + "roots": [10], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"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 Box", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "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.x", "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": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 4, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/chapter10/docs/load-after-store-after.svg b/chapter10/docs/load-after-store-after.svg new file mode 100644 index 00000000..78867d38 --- /dev/null +++ b/chapter10/docs/load-after-store-after.svg @@ -0,0 +1,97 @@ +#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] → #4 · DATA#10[1] → #8 · MEM#10[2] → #4 · DATAStart  #1#1 Start +Type not computed + +$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 Box  #5#5 new Box +Type not computed + +[0] → — 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.x  #8#8 Store p.x +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #4 DATA0123Return  #10#10 Return +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #4 DATA012 diff --git a/chapter10/docs/load-after-store-before.json b/chapter10/docs/load-after-store-before.json new file mode 100644 index 00000000..ba4e2e0b --- /dev/null +++ b/chapter10/docs/load-after-store-before.json @@ -0,0 +1,20 @@ +{ + "ver": 1, + "comp": "load-after-store-before", + "step": 1, + "roots": [10], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"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 Box", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "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.x", "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": 4, "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": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/chapter10/docs/load-after-store-before.svg b/chapter10/docs/load-after-store-before.svg new file mode 100644 index 00000000..497c915d --- /dev/null +++ b/chapter10/docs/load-after-store-before.svg @@ -0,0 +1,103 @@ +#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] → #4 · DATA#9[1] → #8 · MEM#9[2] → #5 · DATA#10[1] → #8 · MEM#10[2] → #9 · DATAStart  #1#1 Start +Type not computed + +$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 Box  #5#5 new Box +Type not computed + +[0] → — 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.x  #8#8 Store p.x +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #4 DATA0123Load p.x  #9#9 Load p.x +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → — DATA0123Return  #10#10 Return +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #9 DATA012 diff --git a/chapter10/docs/type-control.svg b/chapter10/docs/type-control.svg new file mode 100644 index 00000000..d4b79c53 --- /dev/null +++ b/chapter10/docs/type-control.svg @@ -0,0 +1,5 @@ + + Control + + Control + diff --git a/chapter10/docs/type-integer.svg b/chapter10/docs/type-integer.svg new file mode 100644 index 00000000..97d03372 --- /dev/null +++ b/chapter10/docs/type-integer.svg @@ -0,0 +1,5 @@ + + Integer + + Integer + diff --git a/chapter10/docs/type-memory.svg b/chapter10/docs/type-memory.svg new file mode 100644 index 00000000..16b5121f --- /dev/null +++ b/chapter10/docs/type-memory.svg @@ -0,0 +1,5 @@ + + Memory + + Memory + diff --git a/chapter10/docs/type-pointer.svg b/chapter10/docs/type-pointer.svg new file mode 100644 index 00000000..7604492e --- /dev/null +++ b/chapter10/docs/type-pointer.svg @@ -0,0 +1,5 @@ + + Pointer + + Pointer + diff --git a/chapter10/docs/type-struct.svg b/chapter10/docs/type-struct.svg new file mode 100644 index 00000000..97a16562 --- /dev/null +++ b/chapter10/docs/type-struct.svg @@ -0,0 +1,5 @@ + + Struct + + Struct + diff --git a/chapter10/docs/type-tuple.svg b/chapter10/docs/type-tuple.svg new file mode 100644 index 00000000..691478ac --- /dev/null +++ b/chapter10/docs/type-tuple.svg @@ -0,0 +1,5 @@ + + Tuple + + Tuple + -- cgit v1.2.3