From 41ae6269689e2b3cde9f7ac4227923d4085dceda Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 2 Oct 2026 16:21:02 -0700 Subject: More better layout ch10a,b,11 --- chapter10a/README.md | 5 + chapter10a/docs/example1.json | 5 +- chapter10a/docs/example1.svg | 34 +- chapter10a/docs/example2a.json | 19 +- chapter10a/docs/example2a.svg | 61 ++-- chapter10a/docs/example2b.json | 20 +- chapter10a/docs/example2b.svg | 61 ++-- chapter10a/docs/example2c.json | 5 +- chapter10a/docs/example2c.svg | 30 +- chapter10a/docs/load-after-store-after.json | 5 +- chapter10a/docs/load-after-store-after.svg | 26 +- chapter10a/docs/load-after-store-before.json | 5 +- chapter10a/docs/load-after-store-before.svg | 28 +- chapter10b/#README.md# | 174 ---------- chapter10b/.#README.md | 1 - chapter10b/README.md | 119 ++++--- chapter10b/docs/Makefile | 15 +- chapter10b/docs/example1.json | 31 ++ chapter10b/docs/example1.svg | 248 +++++++++----- chapter10b/docs/example2a.json | 20 ++ chapter10b/docs/example2a.svg | 185 +++++----- chapter10b/docs/example2b.json | 30 ++ chapter10b/docs/example2b.svg | 251 ++++++++------ chapter10b/docs/example2c.json | 23 ++ chapter10b/docs/example2c.svg | 177 +++++++--- chapter10b/docs/lattice.gv | 25 +- chapter10b/docs/lattice.svg | 296 ++++++++-------- chapter11/README.md | 493 ++++++--------------------- chapter11/docs/graph1.json | 18 +- chapter11/docs/graph1.svg | 64 +--- chapter11/docs/graph2.json | 28 +- chapter11/docs/graph2.svg | 74 ++-- chapter11/docs/graph3-snip.json | 13 +- chapter11/docs/graph3-snip.svg | 31 +- chapter11/docs/graph3.json | 27 +- chapter11/docs/graph3.svg | 72 ++-- chapter11/docs/graph4.json | 28 +- chapter11/docs/graph4.svg | 103 +----- chapter11/docs/graph5.json | 36 +- chapter11/docs/graph5.svg | 111 ++---- chapter11/docs/graph6.json | 35 +- chapter11/docs/graph6.svg | 109 ++---- chapter11/docs/graph7.svg | 2 +- chapter11/docs/graph8.svg | 2 +- chapter12/docs/lattice.gv | 25 +- chapter12/docs/lattice.svg | 322 +++++++++-------- chapter14/docs/lattice.gv | 25 +- chapter14/docs/lattice.svg | 430 ++++++++++++----------- graph/README.md | 20 +- graph/web/layout.js | 34 +- 50 files changed, 1795 insertions(+), 2206 deletions(-) delete mode 100644 chapter10b/#README.md# delete mode 100644 chapter10b/.#README.md create mode 100644 chapter10b/docs/example1.json create mode 100644 chapter10b/docs/example2a.json create mode 100644 chapter10b/docs/example2b.json create mode 100644 chapter10b/docs/example2c.json diff --git a/chapter10a/README.md b/chapter10a/README.md index 968180b5..d6945f03 100644 --- a/chapter10a/README.md +++ b/chapter10a/README.md @@ -33,6 +33,11 @@ different fields are independent. Chapter 10b will remove it. The graphs show dependencies before local folding. Definitions appear above their uses, except for loop backedges; arrows point from use to definition. +To focus on memory, these illustrations show only small, detached True/False +control projections gating Loads and Stores. These schematic gates indicate +the source branches; Chapter 11 chooses the actual scheduling inputs. Other +control-flow context, including the Regions that bind Phis, is omitted. +The layout shows dependencies, not an execution schedule. | Node | Inputs | Result | |----------|---|---| diff --git a/chapter10a/docs/example1.json b/chapter10a/docs/example1.json index 1b556c04..07e1dfef 100644 --- a/chapter10a/docs/example1.json +++ b/chapter10a/docs/example1.json @@ -6,10 +6,9 @@ "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": 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}, @@ -17,7 +16,7 @@ {"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} + {"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/chapter10a/docs/example1.svg b/chapter10a/docs/example1.svg index b50701b0..d98e0ccd 100644 --- a/chapter10a/docs/example1.svg +++ b/chapter10a/docs/example1.svg @@ -1,4 +1,4 @@ -#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 -$ctrl  #2/0#2 $ctrl -Projection 0 of #1 -Type not computed - -[0] → #1 CTRL$mem  #3/1#3 $mem +$mem  #3/1#3 $mem Projection 1 of #1 Type not computed -[0] → #1 MEMarg  #4/2#4 arg +[0] → #1 MEMarg  #4/2#4 arg Projection 2 of #1 Type not computed -[0] → #1 DATAnew Point  #5#5 new Point +[0] → #1 DATAnew Point  #5#5 new Point Type not computed -[0] → #2 CTRL0#0  #6#6 #0 +[0] → — CTRL0#0  #6#6 #0 Type not computed -[0] → #1 ASSOC0Store p.x  #7#7 Store p.x +[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 +[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 +[3] → #6 DATA0123#3  #9#9 #3 Type not computed -[0] → #1 ASSOC0Store p.x  #10#10 Store p.x +[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 +[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 +[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 +[3] → — DATA0123Return  #13#13 Return Type not computed -[0] → #2 CTRL +[0] → — CTRL [1] → #11 MEM -[2] → #12 DATA012 +[2] → #12 DATA012 diff --git a/chapter10a/docs/example2a.json b/chapter10a/docs/example2a.json index 2fa04643..7c22da0a 100644 --- a/chapter10a/docs/example2a.json +++ b/chapter10a/docs/example2a.json @@ -6,26 +6,21 @@ "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": 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": "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": 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": 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": 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": 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": 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": 16, "role": "CTRL", "label": null}, {"idx": 1, "def": 17, "role": "MEM", "label": null}, {"idx": 2, "def": 18, "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": [ - {"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 eb43548f..b7664907 100644 --- a/chapter10a/docs/example2a.svg +++ b/chapter10a/docs/example2a.svg @@ -1,4 +1,4 @@ -#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 -$ctrl  #2/0#2 $ctrl -Projection 0 of #1 -Type not computed - -[0] → #1 CTRL$mem  #3/1#3 $mem +$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 +[0] → #1 MEMnew Point  #5#5 new Point Type not computed -[0] → #2 CTRL0#0  #6#6 #0 +[0] → — CTRL0#0  #6#6 #0 Type not computed -[0] → #1 ASSOC0Store p.x  #7#7 Store p.x +[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 +[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 +[3] → #6 DATA0123True  #10/0#10 True +Projection 0 of #0 Type not computed -[0] → #9 CTRLFalse  #11/1#11 False -Projection 1 of #9 +False  #11/1#11 False +Projection 1 of #0 Type not computed -[0] → #9 CTRL#3  #12#12 #3 +#3  #12#12 #3 Type not computed -[0] → #1 ASSOC0Store p.x  #13#13 Store p.x +[0] → #1 ASSOC0Store p.x  #13#13 Store p.x Type not computed -[0] → — CTRL +[0] → #10 CTRL [1] → #8 MEM [2] → #5 DATA -[3] → #12 DATA0123#4  #14#14 #4 +[3] → #12 DATA0123#4  #14#14 #4 Type not computed -[0] → #1 ASSOC0Store p.x  #15#15 Store p.x +[0] → #1 ASSOC0Store p.x  #15#15 Store p.x Type not computed -[0] → — CTRL +[0] → #11 CTRL [1] → #8 MEM [2] → #5 DATA -[3] → #14 DATA0123Region  #16#16 Region +[3] → #14 DATA0123Phi $mem  #17#17 Phi $mem 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 +[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 +[3] → — DATA0123Return  #19#19 Return Type not computed -[0] → #16 CTRL +[0] → — CTRL [1] → #17 MEM -[2] → #18 DATA012If  #9If · 9 nodes−Fold region +[2] → #18 DATA012 diff --git a/chapter10a/docs/example2b.json b/chapter10a/docs/example2b.json index 50fbfc74..0b778aea 100644 --- a/chapter10a/docs/example2b.json +++ b/chapter10a/docs/example2b.json @@ -6,26 +6,22 @@ "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": 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": "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": 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": 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} + {"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": [ - {"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 e5322a61..1feb91a3 100644 --- a/chapter10a/docs/example2b.svg +++ b/chapter10a/docs/example2b.svg @@ -1,4 +1,4 @@ -#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 -$ctrl  #2/0#2 $ctrl -Projection 0 of #1 -Type not computed - -[0] → #1 CTRL$mem  #3/1#3 $mem +$mem  #3/1#3 $mem Projection 1 of #1 Type not computed -[0] → #1 MEMarg  #4/2#4 arg +[0] → #1 MEMarg  #4/2#4 arg Projection 2 of #1 Type not computed -[0] → #1 DATAnew Point  #5#5 new Point +[0] → #1 DATAnew Point  #5#5 new Point Type not computed -[0] → #2 CTRL0#0  #6#6 #0 +[0] → — CTRL0#0  #6#6 #0 Type not computed -[0] → #1 ASSOC0Store p.x  #7#7 Store p.x +[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 +[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 +[3] → #6 DATA0123Phi $mem  #10#10 Phi $mem 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 +[2] → #15 MEM012Phi arg  #11#11 Phi arg Type not computed -[0] → #9 ASSOC +[0] → — 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 +[2] → #17 DATA012True  #13/0#13 True +Projection 0 of #0 Type not computed -[0] → #12 CTRLFalse  #14/1#14 False -Projection 1 of #12 +False  #14/1#14 False +Projection 1 of #0 Type not computed -[0] → #12 CTRLStore p.x  #15#15 Store p.x +Store p.x  #15#15 Store p.x Type not computed -[0] → — CTRL +[0] → #13 CTRL [1] → #10 MEM [2] → #5 DATA -[3] → #11 DATA0123#1  #16#16 #1 +[3] → #11 DATA0123#1  #16#16 #1 Type not computed -[0] → #1 ASSOC0-  #17#17 - +[0] → #1 ASSOC0-  #17#17 - Type not computed [0] → — CTRL [1] → #11 DATA -[2] → #16 DATA012Load p.x  #18#18 Load p.x +[2] → #16 DATA012Load p.x  #18#18 Load p.x Type not computed -[0] → — CTRL +[0] → #14 CTRL [1] → #10 MEM [2] → #5 DATA -[3] → — DATA0123Return  #19#19 Return +[3] → — DATA0123Return  #19#19 Return Type not computed -[0] → #14 CTRL +[0] → — CTRL [1] → #10 MEM -[2] → #18 DATA012Loop  #9Loop · 10 nodes−Fold region +[2] → #18 DATA012 diff --git a/chapter10a/docs/example2c.json b/chapter10a/docs/example2c.json index 4e7e096b..84c3d2b6 100644 --- a/chapter10a/docs/example2c.json +++ b/chapter10a/docs/example2c.json @@ -6,16 +6,15 @@ "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": 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": 2, "role": "CTRL", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "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/chapter10a/docs/example2c.svg b/chapter10a/docs/example2c.svg index eb8fad03..f7f7bce3 100644 --- a/chapter10a/docs/example2c.svg +++ b/chapter10a/docs/example2c.svg @@ -1,4 +1,4 @@ -#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 -$ctrl  #2/0#2 $ctrl -Projection 0 of #1 -Type not computed - -[0] → #1 CTRL$mem  #3/1#3 $mem +$mem  #3/1#3 $mem Projection 1 of #1 Type not computed -[0] → #1 MEMarg  #4/2#4 arg +[0] → #1 MEMarg  #4/2#4 arg Projection 2 of #1 Type not computed -[0] → #1 DATAnew Point  #5#5 new Point +[0] → #1 DATAnew Point  #5#5 new Point Type not computed -[0] → #2 CTRL0#0  #6#6 #0 +[0] → — CTRL0#0  #6#6 #0 Type not computed -[0] → #1 ASSOC0Store p.x  #7#7 Store p.x +[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 +[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 +[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 +[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 +[3] → #4 DATA0123Return  #11#11 Return Type not computed -[0] → #2 CTRL +[0] → — CTRL [1] → #10 MEM -[2] → #9 DATA012 +[2] → #9 DATA012 diff --git a/chapter10a/docs/load-after-store-after.json b/chapter10a/docs/load-after-store-after.json index 0f0d3a93..d27efe5b 100644 --- a/chapter10a/docs/load-after-store-after.json +++ b/chapter10a/docs/load-after-store-after.json @@ -6,14 +6,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 Box", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": null}, + {"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": 2, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "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/chapter10a/docs/load-after-store-after.svg b/chapter10a/docs/load-after-store-after.svg index ee6d8189..78867d38 100644 --- a/chapter10a/docs/load-after-store-after.svg +++ b/chapter10a/docs/load-after-store-after.svg @@ -1,4 +1,4 @@ -#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 -$ctrl  #2/0#2 $ctrl -Projection 0 of #1 -Type not computed - -[0] → #1 CTRL$mem  #3/1#3 $mem +$mem  #3/1#3 $mem Projection 1 of #1 Type not computed -[0] → #1 MEMarg  #4/2#4 arg +[0] → #1 MEMarg  #4/2#4 arg Projection 2 of #1 Type not computed -[0] → #1 DATAnew Box  #5#5 new Box +[0] → #1 DATAnew Box  #5#5 new Box Type not computed -[0] → #2 CTRL0#0  #6#6 #0 +[0] → — CTRL0#0  #6#6 #0 Type not computed -[0] → #1 ASSOC0Store p.x  #7#7 Store p.x +[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 +[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 +[3] → #4 DATA0123Return  #10#10 Return Type not computed -[0] → #2 CTRL +[0] → — CTRL [1] → #8 MEM -[2] → #4 DATA012 +[2] → #4 DATA012 diff --git a/chapter10a/docs/load-after-store-before.json b/chapter10a/docs/load-after-store-before.json index 5a15a4e4..ba4e2e0b 100644 --- a/chapter10a/docs/load-after-store-before.json +++ b/chapter10a/docs/load-after-store-before.json @@ -6,15 +6,14 @@ "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 Box", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": null}, + {"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": 2, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "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/chapter10a/docs/load-after-store-before.svg b/chapter10a/docs/load-after-store-before.svg index cdb152e3..497c915d 100644 --- a/chapter10a/docs/load-after-store-before.svg +++ b/chapter10a/docs/load-after-store-before.svg @@ -1,4 +1,4 @@ -#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 -$ctrl  #2/0#2 $ctrl -Projection 0 of #1 -Type not computed - -[0] → #1 CTRL$mem  #3/1#3 $mem +$mem  #3/1#3 $mem Projection 1 of #1 Type not computed -[0] → #1 MEMarg  #4/2#4 arg +[0] → #1 MEMarg  #4/2#4 arg Projection 2 of #1 Type not computed -[0] → #1 DATAnew Box  #5#5 new Box +[0] → #1 DATAnew Box  #5#5 new Box Type not computed -[0] → #2 CTRL0#0  #6#6 #0 +[0] → — CTRL0#0  #6#6 #0 Type not computed -[0] → #1 ASSOC0Store p.x  #7#7 Store p.x +[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 +[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 +[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 +[3] → — DATA0123Return  #10#10 Return Type not computed -[0] → #2 CTRL +[0] → — CTRL [1] → #8 MEM -[2] → #9 DATA012 +[2] → #9 DATA012 diff --git a/chapter10b/#README.md# b/chapter10b/#README.md# deleted file mode 100644 index 6380b79e..00000000 --- a/chapter10b/#README.md# +++ /dev/null @@ -1,174 +0,0 @@ -# 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. - -![Independent field dependencies](docs/example1.svg) - -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. - -![An aggregate preserves both updates](docs/example2a.svg) - -## 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. - -![Precise and bulk Phis share a control merge](docs/example2b.svg) - -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. - -![The type domains, including precise memory aliases](docs/lattice.svg) - -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. - -![Ordering applies within the affected alias](docs/example2c.svg) - -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/chapter10b/.#README.md b/chapter10b/.#README.md deleted file mode 100644 index c657b199..00000000 --- a/chapter10b/.#README.md +++ /dev/null @@ -1 +0,0 @@ -cliffc@DESKTOP-DAD.21980:1790387027 \ No newline at end of file diff --git a/chapter10b/README.md b/chapter10b/README.md index 671d53c3..7cb4cc75 100644 --- a/chapter10b/README.md +++ b/chapter10b/README.md @@ -5,7 +5,7 @@ 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 +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? @@ -27,6 +27,15 @@ load-after-store forwarding turn the return value into 42. ![Independent field dependencies](docs/example1.svg) +The graph shows the split chains before the final Load folds. Its memory input +goes straight to the Store of 42, bypassing the loop's `y` chain. As in 10a, +definitions appear above uses, apart from loop backedges, and arrows point +from use to definition. As in 10a, small, detached True/False projections +show the source branches gating Loads and Stores. Other control-flow context, +including Regions and their Phi bindings, is omitted. Chapter 11 chooses +the actual scheduling inputs; the vertical placement of independent chains +does not specify their execution order. + ## Equivalence-class aliasing Each struct field has an integer alias identity. Two different fields receive @@ -71,14 +80,21 @@ 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. +The graph below shows `p.x = arg; p.y = 42; return p;` after redundant +initialization stores have been removed. MemMerge takes the default memory +in slot 1 and the `x` and `y` overrides in slots 2 and 3. + ![An aggregate preserves both updates](docs/example2a.svg) + ## 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: +to merge memory. It starts by covering all aliases and an empty exclusion set +while the merge point is finalized. Later, peeps will split out precise memory +slices from the bulk memory, lazily on demand. + +Precise single aliases can be split out from the bulk by this transformation: ```text BulkPhi(R, left, right) @@ -88,19 +104,47 @@ MemMerge( 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. +The new precise Phi and the remaining bulk Phi share a Region (omitted from +the illustrations) 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 (and peephole optimizations tidy up the stacked splits). + +Here the two branches store 3 or 4 into `p.x`, then return `p`. The graph shows +the partition immediately after extracting `x`, before further simplification +of the bulk Phi and its incoming aggregates. ![Precise and bulk Phis share a control merge](docs/example2b.svg) -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. +This transform is invasive, and is disallowed from being called recursively; +you can end up splitting around a loop (which is good) but then visiting a +1/2-split loop head (which is bad). The new nodes from the split are put +on the worklist and visited after the current split completes. + +Since bulk Phis merge a bunch of aliases, they have to take care when +peepholing vs MemMerges: there cannot be any overlap between the MemMerge +precise merges and the bulk Phi. -## Types and the worklist +Phi refactoring can combine matching Loads or Stores as in Chapter 10a (pushing +up or pulling down). The Phi new memory operands can use precise MemPhis for +the alias. This peep requires precise aliases, and is otherwise blocked by +BulkMems - and thus is a trigger for splitting a BulkMem. + +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 - job for +`addDep()`. Selecting a slice from an aggregate can expose a new bulk-Phi +user; that selected definition must be queued too. In short, any time we're +working with MemMerge, MemPhi or BulkMemPhi we can expect some non-local +dependencies. + +Memory splitting can increase node count - but Phis (Mem, Bulk or otherwise) +make no code. Progress comes from extracting an alias from a bulk Phi and +removing some Loads & Stores, rather than from requiring every rewrite +to shrink the graph. In other words, the total Load/Store count is going down +even if the MemPhi count is going up. + + + +## Types 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 @@ -110,45 +154,18 @@ alias between memory top (`TypeMem.TOP`) and memory bottom (`TypeMem.BOT`). ![The type domains, including precise memory aliases](docs/lattice.svg) 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 +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. (And 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 +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. Phi -factoring can combine matching Loads or Stores as in Chapter 10a, but cannot -factor MemMerge or BulkMemPhi. Its new memory operands use precise MemPhis for -the operation's alias. Load safety checks only immediate memory users, rejecting -Stores, Phis, and MemMerges. A Phi or aggregate might lead to a later write; -we conservatively skip the rewrite instead of searching farther to save one Load. - -Factoring waits while a BulkMemPhi remains at the same Region. Bulk splitting -identifies parallel slices by Region and alias, whereas factoring a Store can -introduce a memory Phi *before* the Store at that same Region. Waiting avoids -mistaking that earlier memory for the aggregate's completed slice. - -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. Factoring also depends on user counts: -removing a use wakes recorded dependents even when the definition's type stays -unchanged. ## Evaluation and ordering @@ -157,6 +174,10 @@ 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. +In `int old = p.x; p.x = arg; p.y = arg; return old;`, the Load must precede +the later `x` Store; the `y` Store has an independent memory chain. The graph +retains the Load to show this scheduling requirement before local folding. + ![Ordering applies within the affected alias](docs/example2c.svg) Tests cover independent-field folding, parallel memory Phis, multiple field diff --git a/chapter10b/docs/Makefile b/chapter10b/docs/Makefile index 055882b2..6fa0f057 100644 --- a/chapter10b/docs/Makefile +++ b/chapter10b/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/chapter10b/docs/example1.json b/chapter10b/docs/example1.json new file mode 100644 index 00000000..67c277e1 --- /dev/null +++ b/chapter10b/docs/example1.json @@ -0,0 +1,31 @@ +{ + "ver": 1, + "comp": "chapter10b/docs/example1.svg", + "step": 1, + "roots": [24], + "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": "#42", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 8, "label": "Store p.x", "type": "MEM#2", "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": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "Store p.y", "type": "MEM#3", "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": 11, "label": "MemPhi y", "type": "MEM#3", "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 9, "role": "MEM", "label": null}, {"idx": 2, "def": 19, "role": "MEM", "label": null}], "proj": null}, + {"id": 12, "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": 21, "role": "DATA", "label": null}], "proj": null}, + {"id": 15, "label": "True", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 0}}, + {"id": 16, "label": "False", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 1}}, + {"id": 17, "label": "Load p.y", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 15, "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": 18, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 17, "role": "DATA", "label": null}, {"idx": 2, "def": 12, "role": "DATA", "label": null}], "proj": null}, + {"id": 19, "label": "Store p.y", "type": "MEM#3", "kind": "MEM", "edges": [{"idx": 0, "def": 15, "role": "CTRL", "label": null}, {"idx": 1, "def": 11, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 18, "role": "DATA", "label": null}], "proj": null}, + {"id": 20, "label": "#1", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 21, "label": "-", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 12, "role": "DATA", "label": null}, {"idx": 2, "def": 20, "role": "DATA", "label": null}], "proj": null}, + {"id": 22, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 8, "role": "MEM", "label": null}, {"idx": 3, "def": 11, "role": "MEM", "label": null}], "proj": null}, + {"id": 23, "label": "Load p.x", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 16, "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": 24, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 22, "role": "MEM", "label": null}, {"idx": 2, "def": 23, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/chapter10b/docs/example1.svg b/chapter10b/docs/example1.svg index f0b57612..46faf818 100644 --- a/chapter10b/docs/example1.svg +++ b/chapter10b/docs/example1.svg @@ -1,93 +1,155 @@ - - - - - - -Memory - - - -M - -Initial memory - - - -X - -Store x = 42 - - - -X->M - - - - - -Y - -Loop: Store y - - - -Y->M - - - - - - -L - -Load x (42) - - - -L->X - - - - - -MemMerge - -MemMerge - - - -MemMerge->X - - - - - -MemMerge->Y - - - - - - -Return - -Return - - - -Return->L - - - - - -Return->MemMerge - - - - - +#6[0] → #1 · ASSOC#7[0] → #1 · ASSOC#8[1] → #3 · MEM#8[2] → #5 · DATA#8[3] → #7 · DATA#9[1] → #3 · MEM#9[2] → #5 · DATA#9[3] → #6 · DATA#11[1] → #9 · MEM#11[2] → #19 · MEM#12[1] → #4 · DATA#12[2] → #21 · DATA#17[0] → #15 · CTRL#17[1] → #11 · MEM#17[2] → #5 · DATA#18[1] → #17 · DATA#18[2] → #12 · DATA#19[0] → #15 · CTRL#19[1] → #11 · MEM#19[2] → #5 · DATA#19[3] → #18 · DATA#20[0] → #1 · ASSOC#21[1] → #12 · DATA#21[2] → #20 · DATA#22[1] → #3 · MEM#22[2] → #8 · MEM#22[3] → #11 · MEM#23[0] → #16 · CTRL#23[1] → #8 · MEM#23[2] → #5 · DATA#24[1] → #22 · MEM#24[2] → #23 · 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 ASSOC0#42  #7#7 #42 +Type not computed + +[0] → #1 ASSOC0Store p.x  #8MEM#2#8 Store p.x +MEM#2 + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #7 DATA0123Store p.y  #9MEM#3#9 Store p.y +MEM#3 + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123MemPhi y  #11MEM#3#11 MemPhi y +MEM#3 + +[0] → — ASSOC +[1] → #9 MEM +[2] → #19 MEM012Phi arg  #12#12 Phi arg +Type not computed + +[0] → — ASSOC +[1] → #4 DATA +[2] → #21 DATA012True  #15/0#15 True +Projection 0 of #0 +Type not computed + +False  #16/1#16 False +Projection 1 of #0 +Type not computed + +Load p.y  #17#17 Load p.y +Type not computed + +[0] → #15 CTRL +[1] → #11 MEM +[2] → #5 DATA +[3] → — DATA0123+  #18#18 + +Type not computed + +[0] → — CTRL +[1] → #17 DATA +[2] → #12 DATA012Store p.y  #19MEM#3#19 Store p.y +MEM#3 + +[0] → #15 CTRL +[1] → #11 MEM +[2] → #5 DATA +[3] → #18 DATA0123#1  #20#20 #1 +Type not computed + +[0] → #1 ASSOC0-  #21#21 - +Type not computed + +[0] → — CTRL +[1] → #12 DATA +[2] → #20 DATA012MemMerge  #22#22 MemMerge +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #8 MEM +[3] → #11 MEM0123Load p.x  #23#23 Load p.x +Type not computed + +[0] → #16 CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → — DATA0123Return  #24#24 Return +Type not computed + +[0] → — CTRL +[1] → #22 MEM +[2] → #23 DATA012 diff --git a/chapter10b/docs/example2a.json b/chapter10b/docs/example2a.json new file mode 100644 index 00000000..2a9461b6 --- /dev/null +++ b/chapter10b/docs/example2a.json @@ -0,0 +1,20 @@ +{ + "ver": 1, + "comp": "chapter10b/docs/example2a.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": 7, "label": "Store p.x", "type": "MEM#2", "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": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "#42", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 9, "label": "Store p.y", "type": "MEM#3", "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": 8, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 7, "role": "MEM", "label": null}, {"idx": 3, "def": 9, "role": "MEM", "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": 5, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/chapter10b/docs/example2a.svg b/chapter10b/docs/example2a.svg index 47bc3a8f..b43a55b4 100644 --- a/chapter10b/docs/example2a.svg +++ b/chapter10b/docs/example2a.svg @@ -1,82 +1,103 @@ - - - - - - -Memory - - - -M - -Default memory - - - -X - -Store x - - - -X->M - - - - - -Y - -Store y - - - -Y->M - - - - - -MemMerge - -MemMerge - - - -MemMerge->M - - -default - - - -MemMerge->X - - -x - - - -MemMerge->Y - - -y - - - -Return - -Return - - - -Return->MemMerge - - - - - +#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #4 · DATA#8[0] → #1 · ASSOC#9[1] → #3 · MEM#9[2] → #5 · DATA#9[3] → #8 · DATA#10[1] → #3 · MEM#10[2] → #7 · MEM#10[3] → #9 · MEM#11[1] → #10 · MEM#11[2] → #5 · 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] → — CTRL0Store p.x  #7MEM#2#7 Store p.x +MEM#2 + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #4 DATA0123#42  #8#8 #42 +Type not computed + +[0] → #1 ASSOC0Store p.y  #9MEM#3#9 Store p.y +MEM#3 + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #8 DATA0123MemMerge  #10#10 MemMerge +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #7 MEM +[3] → #9 MEM0123Return  #11#11 Return +Type not computed + +[0] → — CTRL +[1] → #10 MEM +[2] → #5 DATA012 diff --git a/chapter10b/docs/example2b.json b/chapter10b/docs/example2b.json new file mode 100644 index 00000000..3d919618 --- /dev/null +++ b/chapter10b/docs/example2b.json @@ -0,0 +1,30 @@ +{ + "ver": 1, + "comp": "chapter10b/docs/example2b.svg", + "step": 1, + "roots": [23], + "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": "MEM#2", "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": "MEM#3", "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": 9, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 7, "role": "MEM", "label": null}, {"idx": 3, "def": 8, "role": "MEM", "label": null}], "proj": null}, + {"id": 11, "label": "True", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 0}}, + {"id": 12, "label": "False", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 1}}, + {"id": 13, "label": "#3", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 14, "label": "Store p.x", "type": "MEM#2", "kind": "MEM", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 13, "role": "DATA", "label": null}], "proj": null}, + {"id": 15, "label": "#4", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 16, "label": "Store p.x", "type": "MEM#2", "kind": "MEM", "edges": [{"idx": 0, "def": 12, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 15, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 9, "role": "MEM", "label": null}, {"idx": 2, "def": 14, "role": "MEM", "label": null}], "proj": null}, + {"id": 18, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 9, "role": "MEM", "label": null}, {"idx": 2, "def": 16, "role": "MEM", "label": null}], "proj": null}, + {"id": 20, "label": "MemPhi x", "type": "MEM#2", "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 16, "role": "MEM", "label": null}], "proj": null}, + {"id": 21, "label": "BulkMemPhi except x", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 17, "role": "MEM", "label": null}, {"idx": 2, "def": 18, "role": "MEM", "label": null}], "proj": null}, + {"id": 22, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 21, "role": "MEM", "label": null}, {"idx": 2, "def": 20, "role": "MEM", "label": null}], "proj": null}, + {"id": 23, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 22, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/chapter10b/docs/example2b.svg b/chapter10b/docs/example2b.svg index cb10b90b..54ddad9d 100644 --- a/chapter10b/docs/example2b.svg +++ b/chapter10b/docs/example2b.svg @@ -1,101 +1,150 @@ - - - - - - -Memory - - - -P - -MemPhi(x) - - - -Left - -Left - - - -P->Left - - -slice x - - - -Right - -Right - - - -P->Right - - -slice x - - - -Region - -Region - - - -P->Region - - - - - -B - -BulkMemPhi(All except x) - - - -B->Left - - - - - -B->Right - - - - - -B->Region - - - - - -MemMerge - -MemMerge - - - -MemMerge->P - - -x - - - -MemMerge->B - - -default - - - +#6[0] → #1 · ASSOC#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #6 · DATA#8[1] → #3 · MEM#8[2] → #5 · DATA#8[3] → #6 · DATA#9[1] → #3 · MEM#9[2] → #7 · MEM#9[3] → #8 · MEM#13[0] → #1 · ASSOC#14[0] → #11 · CTRL#14[1] → #7 · MEM#14[2] → #5 · DATA#14[3] → #13 · DATA#15[0] → #1 · ASSOC#16[0] → #12 · CTRL#16[1] → #7 · MEM#16[2] → #5 · DATA#16[3] → #15 · DATA#17[1] → #9 · MEM#17[2] → #14 · MEM#18[1] → #9 · MEM#18[2] → #16 · MEM#20[1] → #14 · MEM#20[2] → #16 · MEM#21[1] → #17 · MEM#21[2] → #18 · MEM#22[1] → #21 · MEM#22[2] → #20 · MEM#23[1] → #22 · MEM#23[2] → #5 · 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  #7MEM#2#7 Store p.x +MEM#2 + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Store p.y  #8MEM#3#8 Store p.y +MEM#3 + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123MemMerge  #9#9 MemMerge +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #7 MEM +[3] → #8 MEM0123True  #11/0#11 True +Projection 0 of #0 +Type not computed + +False  #12/1#12 False +Projection 1 of #0 +Type not computed + +#3  #13#13 #3 +Type not computed + +[0] → #1 ASSOC0Store p.x  #14MEM#2#14 Store p.x +MEM#2 + +[0] → #11 CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #13 DATA0123#4  #15#15 #4 +Type not computed + +[0] → #1 ASSOC0Store p.x  #16MEM#2#16 Store p.x +MEM#2 + +[0] → #12 CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #15 DATA0123MemMerge  #17#17 MemMerge +Type not computed + +[0] → — CTRL +[1] → #9 MEM +[2] → #14 MEM012MemMerge  #18#18 MemMerge +Type not computed + +[0] → — CTRL +[1] → #9 MEM +[2] → #16 MEM012MemPhi x  #20MEM#2#20 MemPhi x +MEM#2 + +[0] → — ASSOC +[1] → #14 MEM +[2] → #16 MEM012BulkMemPhi except x  #21#21 BulkMemPhi except x +Type not computed + +[0] → — ASSOC +[1] → #17 MEM +[2] → #18 MEM012MemMerge  #22#22 MemMerge +Type not computed + +[0] → — CTRL +[1] → #21 MEM +[2] → #20 MEM012Return  #23#23 Return +Type not computed + +[0] → — CTRL +[1] → #22 MEM +[2] → #5 DATA012 diff --git a/chapter10b/docs/example2c.json b/chapter10b/docs/example2c.json new file mode 100644 index 00000000..380815a2 --- /dev/null +++ b/chapter10b/docs/example2c.json @@ -0,0 +1,23 @@ +{ + "ver": 1, + "comp": "chapter10b/docs/example2c.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": "MEM#2", "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": "MEM#3", "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": 9, "label": "Load p.x", "type": null, "kind": "DATA", "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": 0, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "Store p.x", "type": "MEM#2", "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": 11, "label": "Store p.y", "type": "MEM#3", "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": 12, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 10, "role": "MEM", "label": null}, {"idx": 3, "def": 11, "role": "MEM", "label": null}], "proj": null}, + {"id": 13, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 12, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/chapter10b/docs/example2c.svg b/chapter10b/docs/example2c.svg index 531fabfe..01bbe10a 100644 --- a/chapter10b/docs/example2c.svg +++ b/chapter10b/docs/example2c.svg @@ -1,56 +1,121 @@ - - - - - - -Memory - - - -M - -Prior x memory - - - -L - -Load p.x - - - -L->M - - - - - -S - -Store p.x - - - -S->M - - - - - -S->L - - -execute load first - - - -Y - -Store p.y: independent - - - +#6[0] → #1 · ASSOC#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #6 · DATA#8[1] → #3 · MEM#8[2] → #5 · DATA#8[3] → #6 · DATA#9[1] → #7 · MEM#9[2] → #5 · DATA#10[1] → #7 · MEM#10[2] → #5 · DATA#10[3] → #4 · DATA#11[1] → #8 · MEM#11[2] → #5 · DATA#11[3] → #4 · DATA#12[1] → #3 · MEM#12[2] → #10 · MEM#12[3] → #11 · MEM#13[1] → #12 · MEM#13[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  #7MEM#2#7 Store p.x +MEM#2 + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Store p.y  #8MEM#3#8 Store p.y +MEM#3 + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Load p.x  #9#9 Load p.x +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → — DATA0123Store p.x  #10MEM#2#10 Store p.x +MEM#2 + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #4 DATA0123Store p.y  #11MEM#3#11 Store p.y +MEM#3 + +[0] → — CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → #4 DATA0123MemMerge  #12#12 MemMerge +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #10 MEM +[3] → #11 MEM0123Return  #13#13 Return +Type not computed + +[0] → — CTRL +[1] → #12 MEM +[2] → #9 DATA012 diff --git a/chapter10b/docs/lattice.gv b/chapter10b/docs/lattice.gv index a37a1738..93d99dd8 100644 --- a/chapter10b/docs/lattice.gv +++ b/chapter10b/docs/lattice.gv @@ -97,9 +97,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/chapter10b/docs/lattice.svg b/chapter10b/docs/lattice.svg index ff554601..8d2e2875 100644 --- a/chapter10b/docs/lattice.svg +++ b/chapter10b/docs/lattice.svg @@ -4,123 +4,123 @@ - - + + 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 -precise alias slices + +Memory +precise alias slices 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 - - + + @@ -137,7 +137,7 @@ XCTRL->CTRL - + @@ -150,38 +150,38 @@ INT_NEG - -… −2, −1 + +… −2, −1 INT_TOP->INT_NEG - - + + INT_ZERO - -0 + +0 INT_TOP->INT_ZERO - - + + INT_POS - -1, 2, … + +1, 2, … INT_TOP->INT_POS - - + + @@ -199,70 +199,70 @@ INT_NEG->INT_BOT - - + + INT_ZERO->INT_BOT - - + + INT_POS->INT_BOT - - + + 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 - - + + @@ -287,8 +287,8 @@ PTR_NULL->PTR_PERSON_NIL - - + + @@ -299,8 +299,8 @@ PTR_NULL->PTR_S1_NIL - - + + @@ -311,8 +311,8 @@ PTR_NULL->PTR_MORE_NIL - - + + @@ -331,41 +331,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 - - + + @@ -397,8 +397,8 @@ STRUCT_TOP->STRUCT_PERSON - - + + @@ -410,8 +410,8 @@ STRUCT_TOP->STRUCT_S1 - - + + @@ -423,8 +423,8 @@ STRUCT_TOP->STRUCT_S2 - - + + @@ -435,8 +435,8 @@ STRUCT_TOP->STRUCT_MORE - - + + @@ -488,8 +488,8 @@ MEM_TOP->MEM_ALIAS2 - - + + @@ -500,8 +500,8 @@ MEM_TOP->MEM_ALIAS3 - - + + @@ -512,8 +512,8 @@ MEM_TOP->MEM_MORE - - + + @@ -551,70 +551,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 - - + + diff --git a/chapter11/README.md b/chapter11/README.md index 58adbbfb..cd44f811 100644 --- a/chapter11/README.md +++ b/chapter11/README.md @@ -3,20 +3,11 @@ [Previous: Chapter 10b](../chapter10b/README.md) | [Next: Chapter 12](../chapter12/README.md) -This chapter schedules the memory representation introduced in -[10b](../chapter10b/README.md): one parser-visible `$mem`, with `MemMerge`, -`MemPhi`, and `BulkMemPhi` recovering independent field chains. Start supplies -`{ctrl, $mem, arg}`. Return consumes `{ctrl, $mem, result}`, with the complete -memory aggregate in slot 1. Nodes consuming or producing both control and -memory consistently use slot 0 for control and slot 1 for memory. - -The new scheduling rule is to distinguish a memory aggregate from a memory -write. `MemMerge` gets a placement from its inputs and uses, but emits no heap -operation and creates no load/store anti-dependency. A Store or MemPhi can -constrain a Load only for the same alias; a BulkMemPhi can constrain it only -while it still covers that alias. Both kinds of memory Phi remain attached to -their Region, just like scalar Phis. +This chapter schedules the programs from [10b](../chapter10b/README.md), +picking a slot#0 CFG input for all nodes lacking one. +Also in this chapter, we'll be presenting several fairly detailed graph +algorithms. You might want to brush up on your graph theory! # Table of Contents @@ -36,9 +27,11 @@ their Region, just like scalar Phis. You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter11) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter10b...linear-chapter11) it to the previous chapter. -The original input source program defines a sequence in which things happen. As we parse the program into Sea of Nodes representation -and perform various optimizations, this sequence is not fully maintained. The optimized Sea of Nodes graph is driven more -by dependencies between nodes rather than the sequence of instructions in the original source program. +The original input source program defines a sequence in which things happen. As +we parse the program into Sea of Nodes representation and perform various +optimizations, this sequence is not fully maintained. The optimized Sea of +Nodes graph is driven by the dependencies between nodes rather than the +sequence of instructions in the original source program. Our goal in this chapter is to look at how we can recover a schedule for executing instructions from an optimized Sea of Nodes graph. This schedule needs to preserve the semantics of the original source program, @@ -91,26 +84,35 @@ First let's look at the graph before scheduling. These walkthrough diagrams show the precise `S.f` chain and the final MemMerge consumed by Return. The unchanged default memory comes from Start; -any redundant bulk Phis have folded away. Arrows point from uses to definitions. +any redundant bulk Phis have folded away. As in 10a and 10b, the diagrams omit +control-flow context, including Regions and their Phi bindings. Small, +detached True/False projections remain where they gate a Load or Store. +Unlike Chapter 10's schematic source gates, these figures show the actual +scheduling inputs at each stage. Entry-block and Loop bindings are omitted. ![Graph1](./docs/graph1.svg) Observe that -* Control nodes are colored in yellow; these are immovable. -* New nodes have control input and therefore these are already scheduled. -* Ditto for Phi nodes which are attached to the Region nodes. -* So what remains are the "floating" Data nodes that do not have a control input at this stage. In this example, these are the load `.f` and store `.f=` nodes. +* Control nodes are immovable. Most are omitted here. +* New nodes already have control inputs, and Phis are bound to Regions; + these bindings remain fixed even though they are not drawn. +* The load `.f` and store `.f=` nodes are still "floating": they have no + control input at this stage, so scheduling must choose their blocks. Now, let's look at the graph after we run the early schedule. ![Graph2](./docs/graph2.svg) -* Observe that the load `.f` and the stores `.f=` now have control edges to the `$ctrl` projection from Start. Thus, the early schedule has put the Data nodes in the first basic block. -* This is because the inputs to these nodes have the `$ctrl` projection as the immediate dominator. +The early schedule puts the load `.f` and stores `.f=` in the first basic +block, since their inputs are available there. These entry-block control +bindings are omitted, so the memory view looks unchanged. -The graph below shows the schedule post late scheduling. +The graph below focuses on memory and data dependencies after late scheduling. +The control-flow scaffold, including the Region, is omitted. Store #22's +control input remains visible as the red edge to the standalone True +projection #8; the Store-to-Load anti-dependency and memory Phis are retained. ![Graph3](./docs/graph3.svg) @@ -146,8 +148,9 @@ Following early schedule generation, we get: ![Graph5](./docs/graph5.svg) -Note that the `arg == 5` comparison at this stage is not in the correct place. -This is rectified after we complete late scheduling. +The early schedule places Store #31 at the loop header (its control binding +is omitted). Late scheduling moves it to the True branch #15 of +`if (arg == 5)`, shown by the red control edge: ![Graph6](./docs/graph6.svg) @@ -214,32 +217,11 @@ Now, look at the modified graph after we insert an edge from the infinite loop t ![Graph8](./docs/graph8.svg) -The implementation is in the Loop node: - -```java - // If this is an unreachable loop, it may not have an exit. If it does not - // (i.e., infinite loop), force an exit to make it reachable. - public void forceExit( StopNode stop ) { - // Walk the backedge, then immediate dominator tree until we hit this - // Loop again. If we ever hit a CProj from an If (as opposed to - // directly on the If) we found our exit. - CFGNode x = back(); - while( x != this ) { - if( x instanceof CProjNode exit ) - return; // Found an exit, not an infinite loop - x = x.idom(); - } - // Found a no-exit loop. Insert an exit - NeverNode iff = new NeverNode(back()); - for( Node use : _outputs ) - if( use instanceof PhiNode phi ) - iff.addDef(use); - CProjNode t = new CProjNode(iff,0,"True" ); - CProjNode f = new CProjNode(iff,1,"False"); - setDef(2,f); - stop.addDef(new ReturnNode(t,Parser.ZERO,null)); - } -``` +The implementation is in +[`LoopNode.forceExit()`](src/main/java/com/seaofnodes/simple/node/LoopNode.java#L57). +It walks the backedge's dominator chain to look for an exit. If none exists, +it inserts a Never node and a never-taken return path, making the loop +reachable to the scheduler's backward walk. ## Dominators @@ -247,87 +229,28 @@ In Simple, we compute Dominators incrementally. Our approach relies on the fact but we never introduce new control structure via peepholes. This allows us to use a simple approach described below. The CFG node is the base class for all control nodes. It maintains a conservative approximation of dominator depth via `_idepth`. This field is a cached value representing -the immediate dominator depth. Its initial value is `0`, which signifies that it has not yet been computed. On request, we compute this as shown below. +the immediate dominator depth. Its initial value is `0`, which signifies that it has not yet been computed. The depth is computed on request. + +See [`CFGNode.idepth()`](src/main/java/com/seaofnodes/simple/node/CFGNode.java#L51) +for the default computation and cache. The overrides in +[`RegionNode`](src/main/java/com/seaofnodes/simple/node/RegionNode.java#L94), +[`LoopNode`](src/main/java/com/seaofnodes/simple/node/LoopNode.java#L31), +[`StartNode`](src/main/java/com/seaofnodes/simple/node/StartNode.java#L36), and +[`StopNode`](src/main/java/com/seaofnodes/simple/node/StopNode.java#L57) +handle merges, loop entries, and the graph's endpoints. -```java -class CFGNode { - public int _idepth; - public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } -} -class RegionNode extends CFGNode { - // Immediate dominator of Region is a little more complicated. - @Override public int idepth() { - if( _idepth!=0 ) return _idepth; - int d=0; - for( Node n : _inputs ) - if( n!=null ) - d = Math.max(d,((CFGNode)n).idepth()+1); - return _idepth=d; - } -} -class LoopNode extends RegionNode { - // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) - @Override public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } -} -class StartNode extends CFGNode { - @Override public int idepth() { return 0; } -} -class StopNode extends CFGNode { - @Override public int idepth() { - if( _idepth!=0 ) return _idepth; - int d=0; - for( Node n : _inputs ) - if( n!=null ) - d = Math.max(d,((CFGNode)n).idepth()+1); - return _idepth=d; - } -} -``` If portions of the control flow graph are deleted, then there will be gaps in the `_idepth`, but it still correctly reflects the invariant that the value of `_idepth` increases as we go down the dominator tree. Alongside the dominator depth, which is cached on first compute, a method is provided to get the immediate Dominator node. This value is not cached as it is only valid at a point in time, and is invalidated as the graph changes. -We show the code that computes this value: - -```java -class CFGNode { - // Return the immediate dominator of this Node and compute dom tree depth. - public CFGNode idom() { return cfg(0); } - // Return the LCA of two idoms - public CFGNode idom(CFGNode rhs) { - if( rhs==null ) return this; - CFGNode lhs = this; - while( lhs != rhs ) { - var comp = lhs.idepth() - rhs.idepth(); - if( comp >= 0 ) lhs = lhs.idom(); - if( comp <= 0 ) rhs = rhs.idom(); - } - return lhs; - } -} -class RegionNode extends CFGNode { - @Override public CFGNode idom() { - CFGNode lca = null; - // Walk the LHS & RHS idom trees in parallel until they match, or either fails. - // Because this does not cache, it can be linear in the size of the program. - for( int i=1; i rpo = new ArrayList<>(); - BitSet visit = new BitSet(); - _rpo_cfg(Parser.START, visit, rpo); - // Reverse Post-Order on CFG - for( int j=rpo.size()-1; j>=0; j-- ) { - CFGNode cfg = rpo.get(j); - cfg.loopDepth(); - for( Node n : cfg._inputs ) - _schedEarly(n,visit); - // In dead infinite loops, entire code blocks may be unreachable - // from below. Reach down from the CFG to their Phis so their - // inputs are scheduled too. - if( cfg instanceof RegionNode ) { - int len = cfg.nOuts(); - for( int i=0; i rpo) { - if( !(n instanceof CFGNode cfg) || visit.get(cfg._nid) ) - return; // Been there, done that - visit.set(cfg._nid); - for( Node use : cfg._outputs ) - _rpo_cfg(use,visit,rpo); - rpo.add(cfg); - } - - private static void _schedEarly(Node n, BitSet visit) { - if( n==null || visit.get(n._nid) ) return; // Been there, done that - visit.set(n._nid); - // Schedule inputs first, except Phis: following their backedges would - // enter a data cycle before its control has been scheduled. - for( Node def : n._inputs ) - if( def!=null && !(def instanceof PhiNode) ) - _schedEarly(def,visit); - // An existing edge 0 already supplies control (or a Phi/Proj binding). - if( n.in(0)==null ) { - // Schedule at deepest input - CFGNode early = Parser.START; // Maximally early, lowest idepth - for( int i=1; i early.idepth() ) - early = n.in(i).cfg0(); // Latest/deepest input - n.setDef(0,early); // First place this can go - } - } -``` +The implementation starts in +[`GlobalCodeMotion.schedEarly()`](src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L59). +[`_rpo_cfg()`](src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L82) +builds the CFG traversal order, and +[`_schedEarly()`](src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L91) +recursively schedules data inputs. It skips recursion through Phi inputs to +avoid entering a data cycle before its control has been scheduled. Existing control and Phi/Proj bindings are preserved. Floating nodes receive the deepest input block as their earliest placement. MemMerge follows this @@ -449,121 +297,28 @@ waits for memory users that can overwrite or merge its alias. The chosen block lies between the early placement and the common dominator of all uses, favoring shallower loops and then deeper control flow. -```java - private static void schedLate( StopNode stop) { - CFGNode[] late = new CFGNode[Node.UID()]; - Node[] ns = new Node[Node.UID()]; - // Record Load NIDs at all their CFG block choices, then check against - // Store block choices to force a Load above an anti-dependent Store. - int[] anti = new int[Node.UID()]; - // Breadth-first scheduling - breadth(stop,ns,late,anti); - - // Copy the best placement choice into the control slot - for( int i=0; i work = new WorkList<>(); - work.push(stop); - Node n; - outer: - while( (n = work.pop()) != null ) { - assert late[n._nid]==null; // No double visit - // These I know the late schedule of, and need to set early for loops - if( n instanceof CFGNode cfg ) late[n._nid] = cfg.blockHead() ? cfg : cfg.cfg(0); - else if( n instanceof PhiNode phi ) late[n._nid] = phi.region(); - // These nodes have a fixed late placement at their original control. - else if( n instanceof ProjNode || n instanceof NewNode || n==Parser.ZERO ) late[n._nid] = n.cfg0(); - else { - - // All uses done? - for( Node use : n._outputs ) - if( use!=null && late[use._nid]==null ) - continue outer; // Nope, await all uses done - - // Loads need their memory inputs' uses also done - if( n instanceof LoadNode ld ) - for( Node memuse : ld.mem()._outputs ) - if( antiUse(ld,memuse) && late[memuse._nid]==null ) - continue outer; - - // All uses done, schedule - _doSchedLate(n,ns,late,anti); - } - - // A use just finished; reconsider its inputs and waiting loads, - // even when the shared memory input was already scheduled. - for( Node def : n._inputs ) { - if( def==null ) continue; - if( late[def._nid]==null ) work.push(def); - for( Node out : def._outputs ) - if( out instanceof LoadNode ld && late[ld._nid]==null ) - work.push(ld); - } - if( n instanceof LoopNode loop ) - for( Node phi : loop._outputs ) - if( phi instanceof PhiNode && late[phi._nid]==null ) - work.push(phi); - } - } - - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { - // Walk uses, gathering the LCA (Least Common Ancestor) of uses - CFGNode early = n.in(0) instanceof CFGNode cfg ? cfg : n.in(0).cfg0(); - assert early != null; - CFGNode lca = null; - for( Node use : n._outputs ) - if( use != null ) - lca = use_block(n,use, late).domLCA(lca); - - // Loads may need anti-dependencies, raising their LCA - if( n instanceof LoadNode load ) - lca = find_anti_dep(lca,load,early,late,anti); - - // Walk up from the LCA to the early, looking for best place. This is - // the lowest execution frequency, approximated by least loop depth and - // deepest control flow. - CFGNode best = lca; - lca = lca.idom(); // Already found best for starting LCA - for( ; lca != early.idom(); lca = lca.idom() ) - if( better(lca,best) ) - best = lca; - assert !(best instanceof IfNode); - ns [n._nid] = n; - late[n._nid] = best; - } - - // Block of use. Normally from late[] schedule, except for Phis, which go - // to the matching Region input. - private static CFGNode use_block(Node n, Node use, CFGNode[] late) { - if( !(use instanceof PhiNode phi) ) - return late[use._nid]; - CFGNode found=null; - for( int i=1; i best.idepth() || - best instanceof IfNode; - } -``` +The implementation is divided into these steps: + +* [`schedLate()`](src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L111) + manages the placement tables and installs the final control inputs; + [`breadth()`](src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L126) + drives the worklist and wakes definitions and waiting loads as uses finish. +* [`_doSchedLate()`](src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L172) + finds the common dominator of uses, accounts for load anti-dependencies, and + walks toward the early placement. It calls + [`better()`](src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L213) + to compare candidate blocks. +* [`use_block()`](src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L200) + handles Phi uses at their matching incoming control paths, rather than at + the merge itself. ## Inserting Anti Dependencies -To ensure that Loads and Stores to the same memory location are correctly ordered, we insert an edge from the Store to the Load as described below: the Store must wait for the earlier Load. -We call these edges anti-dependencies because they do not represent the Def-Use dependency that we normally capture in SoN, and are purely present as scheduling constraints. +To ensure that Loads and Stores to the same memory location are correctly +ordered, we insert an edge from the Store to the Load as described below: the +Store must wait for the earlier Load. We call these edges anti-dependencies +because they do not represent the Def-Use dependency that we normally capture +in SoN, and are purely present as scheduling constraints. We compute anti-dependencies DURING running schedule late. This is because we rely on the early-schedule, and the late-schedule of the Load's uses (before scheduling the Load). @@ -581,66 +336,24 @@ is ready to schedule and when computing its anti-dependencies. A completed memory user wakes waiting loads even if their shared memory definition has already been scheduled. -Since we're in the middle of "schedule late", we have already computed all the late schedules of a Load's users, and we have the Loads "Least Common Ancestor" of uses, the LCA or late position. -We inspect the set of mem-defs that might impact the Load, and either add an anti-dependency from Store to Load, or raise the Loads effective LCA. -For Phi mem-defs, we look at the Phi inputs and place an effective use on that block; this will be used to raise the Load's LCA. -For stores, we do the same - until/unless we find stores with the SAME block as the Load's LCA. Then we add the anti-dependency edge to force ordering within the same block. - -The implementation is shown below. - -```java - // Only a store or memory Phi covering this alias can constrain a load. - // MemMerge packages slices without overwriting them. - private static boolean antiUse(LoadNode load, Node use) { - return switch( use ) { - case StoreNode st -> st._alias==load._alias; - case MemPhiNode phi -> phi._alias==load._alias; - case BulkMemPhiNode phi -> !phi.isSplit(load._alias); - default -> false; - }; - } - - private static CFGNode find_anti_dep(CFGNode lca, LoadNode load, CFGNode early, CFGNode[] late, int[] anti) { - // We could skip final-field loads here. - // Walk LCA->early, flagging Load's block location choices - for( CFGNode cfg=lca; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) - anti[cfg._nid] = load._nid; - // Walk load->mem uses, looking for Stores causing an anti-dep - for( Node mem : load.mem()._outputs ) { - if( !antiUse(load,mem) ) continue; - switch( mem ) { - case StoreNode st: - lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti); - break; - case PhiNode phi: - // Repeat anti-dep for matching Phi inputs. - // No anti-dep edges but may raise the LCA. - for( int i=1; i#1[1] → #6 · MEM#1[2] → #224 · MEM#12[1] → #6 · MEM#12[2] → #9 · DATA#12[3] → #11 · DATA#14[1] → #12 · MEM#14[2] → #13 · DATA#14[3] → #4 · DATA#16[1] → #14 · MEM#16[2] → #9 · DATA#22[1] → #14 · MEM#22[2] → #9 · DATA#22[3] → #21 · DATA#25[1] → #1 · MEM#25[2] → #16 · DATA#224[1] → #22 · MEM#224[2] → #14 · MEMMemMerge  #1#1 MemMerge Type not computed [0] → — DATA [1] → #6 MEM -[2] → #224 MEM012Start  #2#2 Start +[2] → #224 MEM012Start  #2#2 Start Type not computed -Stop  #3#3 Stop +#0  #4#4 #0 Type not computed -[0] → #25 CTRL0#0  #4#4 #0 -Type not computed - -$ctrl  #5/0#5 $ctrl -Projection 0 of #2 -Type not computed - -[0] → #2 CTRL$mem  #6/1#6 $mem +$mem  #6/1#6 $mem Projection 1 of #2 Type not computed -[0] → #2 MEMarg  #7/2#7 arg -Projection 2 of #2 -Type not computed - -[0] → #2 DATATrue  #8/0#8 True -Projection 0 of #17 -Type not computed - -[0] → #17 CTRLnew S  #9#9 new S +[0] → #2 MEMnew S  #9#9 new S Type not computed -[0] → #5 CTRL0False  #10/1#10 False -Projection 1 of #17 +[0] → — CTRL0#2  #11#11 #2 Type not computed -[0] → #17 CTRL#2  #11#11 #2 -Type not computed - -.f =  #12#12 .f = +.f =  #12#12 .f = Type not computed [0] → — DATA [1] → #6 MEM [2] → #9 DATA -[3] → #11 DATA0123new S  #13#13 new S +[3] → #11 DATA0123new S  #13#13 new S Type not computed -[0] → #5 CTRL0.f =  #14#14 .f = +[0] → — CTRL0.f =  #14#14 .f = Type not computed [0] → — DATA [1] → #12 MEM [2] → #13 DATA -[3] → #4 DATA0123.f  #16#16 .f +[3] → #4 DATA0123.f  #16#16 .f Type not computed [0] → — DATA [1] → #14 MEM -[2] → #9 DATA012If  #17#17 If -Type not computed - -[0] → #5 CTRL -[1] → #7 DATA01#1  #21#21 #1 +[2] → #9 DATA012#1  #21#21 #1 Type not computed -.f =  #22#22 .f = +.f =  #22#22 .f = Type not computed [0] → — DATA [1] → #14 MEM [2] → #9 DATA -[3] → #21 DATA0123Region  #23#23 Region -Type not computed - -[0] → — DATA -[1] → #8 CTRL -[2] → #10 CTRL012Return  #25#25 Return +[3] → #21 DATA0123Return  #25#25 Return Type not computed -[0] → #23 CTRL +[0] → — CTRL [1] → #1 MEM -[2] → #16 DATA012MemPhi_2  #224#224 MemPhi_2 +[2] → #16 DATA012MemPhi_2  #224#224 MemPhi_2 Type not computed -[0] → #23 ASSOC +[0] → — ASSOC [1] → #22 MEM -[2] → #14 MEM[0] → #23012If  #17If · 6 nodes−Fold region +[2] → #14 MEM012 diff --git a/chapter11/docs/graph2.json b/chapter11/docs/graph2.json index 7c50307d..602c1584 100644 --- a/chapter11/docs/graph2.json +++ b/chapter11/docs/graph2.json @@ -2,32 +2,24 @@ "ver": 1, "comp": "chapter11/docs/graph2.svg", "step": 1, - "roots": [], + "roots": [25], "scope": 0, "nodes": [ - {"id": 1, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 23, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 224, "role": "MEM", "label": null}], "proj": null}, + {"id": 1, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 224, "role": "MEM", "label": null}], "proj": null}, {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, - {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": null}, {"id": 4, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, - {"id": 5, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, {"id": 6, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 2, "role": "MEM", "label": null}], "proj": {"par": 2, "idx": 1}}, - {"id": 7, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 2}}, - {"id": 8, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 17, "role": "CTRL", "label": null}], "proj": {"par": 17, "idx": 0}}, - {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}], "proj": null}, - {"id": 10, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 17, "role": "CTRL", "label": null}], "proj": {"par": 17, "idx": 1}}, + {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, {"id": 11, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, - {"id": 12, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 11, "role": "DATA", "label": null}], "proj": null}, - {"id": 13, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}], "proj": null}, - {"id": 14, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 12, "role": "MEM", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, - {"id": 16, "label": ".f", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, - {"id": 17, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 12, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 11, "role": "DATA", "label": null}], "proj": null}, + {"id": 13, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, + {"id": 14, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 12, "role": "MEM", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 16, "label": ".f", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, {"id": 21, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, - {"id": 22, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 21, "role": "DATA", "label": null}], "proj": null}, - {"id": 23, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 8, "role": "CTRL", "label": null}, {"idx": 2, "def": 10, "role": "CTRL", "label": null}], "proj": null}, - {"id": 25, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 23, "role": "CTRL", "label": null}, {"idx": 1, "def": 1, "role": "MEM", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, - {"id": 224, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 23, "role": "ASSOC", "label": null}, {"idx": 1, "def": 22, "role": "MEM", "label": null}, {"idx": 2, "def": 14, "role": "MEM", "label": null}], "proj": null} + {"id": 22, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 21, "role": "DATA", "label": null}], "proj": null}, + {"id": 25, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 1, "role": "MEM", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 224, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 22, "role": "MEM", "label": null}, {"idx": 2, "def": 14, "role": "MEM", "label": null}], "proj": null} ], "groups": [ - {"id": 17, "par": 0, "nodes": [1, 8, 10, 17, 23, 224]} ] } diff --git a/chapter11/docs/graph2.svg b/chapter11/docs/graph2.svg index a3afd14f..05210749 100644 --- a/chapter11/docs/graph2.svg +++ b/chapter11/docs/graph2.svg @@ -1,4 +1,4 @@ -#1[1] → #6 · MEM#1[2] → #224 · MEM#12[1] → #6 · MEM#12[2] → #9 · DATA#12[3] → #11 · DATA#14[1] → #12 · MEM#14[2] → #13 · DATA#14[3] → #4 · DATA#16[1] → #14 · MEM#16[2] → #9 · DATA#22[1] → #14 · MEM#22[2] → #9 · DATA#22[3] → #21 · DATA#25[1] → #1 · MEM#25[2] → #16 · DATA#224[1] → #22 · MEM#224[2] → #14 · MEMMemMerge  #1#1 MemMerge Type not computed -[0] → #23 CTRL +[0] → — CTRL [1] → #6 MEM -[2] → #224 MEM012Start  #2#2 Start +[2] → #224 MEM012Start  #2#2 Start Type not computed -Stop  #3#3 Stop +#0  #4#4 #0 Type not computed -[0] → #25 CTRL0#0  #4#4 #0 -Type not computed - -$ctrl  #5/0#5 $ctrl -Projection 0 of #2 -Type not computed - -[0] → #2 CTRL$mem  #6/1#6 $mem +$mem  #6/1#6 $mem Projection 1 of #2 Type not computed -[0] → #2 MEMarg  #7/2#7 arg -Projection 2 of #2 -Type not computed - -[0] → #2 DATATrue  #8/0#8 True -Projection 0 of #17 -Type not computed - -[0] → #17 CTRLnew S  #9#9 new S -Type not computed - -[0] → #5 CTRL0False  #10/1#10 False -Projection 1 of #17 +[0] → #2 MEMnew S  #9#9 new S Type not computed -[0] → #17 CTRL#2  #11#11 #2 +[0] → — CTRL0#2  #11#11 #2 Type not computed -.f =  #12#12 .f = +.f =  #12#12 .f = Type not computed -[0] → #5 CTRL +[0] → — CTRL [1] → #6 MEM [2] → #9 DATA -[3] → #11 DATA0123new S  #13#13 new S +[3] → #11 DATA0123new S  #13#13 new S Type not computed -[0] → #5 CTRL0.f =  #14#14 .f = +[0] → — CTRL0.f =  #14#14 .f = Type not computed -[0] → #5 CTRL +[0] → — CTRL [1] → #12 MEM [2] → #13 DATA -[3] → #4 DATA0123.f  #16#16 .f +[3] → #4 DATA0123.f  #16#16 .f Type not computed -[0] → #5 CTRL +[0] → — CTRL [1] → #14 MEM -[2] → #9 DATA012If  #17#17 If +[2] → #9 DATA012#1  #21#21 #1 Type not computed -[0] → #5 CTRL -[1] → #7 DATA01#1  #21#21 #1 +.f =  #22#22 .f = Type not computed -.f =  #22#22 .f = -Type not computed - -[0] → #5 CTRL +[0] → — CTRL [1] → #14 MEM [2] → #9 DATA -[3] → #21 DATA0123Region  #23#23 Region -Type not computed - -[0] → — DATA -[1] → #8 CTRL -[2] → #10 CTRL012Return  #25#25 Return +[3] → #21 DATA0123Return  #25#25 Return Type not computed -[0] → #23 CTRL +[0] → — CTRL [1] → #1 MEM -[2] → #16 DATA012MemPhi_2  #224#224 MemPhi_2 +[2] → #16 DATA012MemPhi_2  #224#224 MemPhi_2 Type not computed -[0] → #23 ASSOC +[0] → — ASSOC [1] → #22 MEM -[2] → #14 MEM[0] → #23012If  #17If · 6 nodes−Fold region +[2] → #14 MEM012 diff --git a/chapter11/docs/graph3-snip.json b/chapter11/docs/graph3-snip.json index 00b3e744..7dade538 100644 --- a/chapter11/docs/graph3-snip.json +++ b/chapter11/docs/graph3-snip.json @@ -2,16 +2,13 @@ "ver": 1, "comp": "chapter11/docs/graph3-snip.svg", "step": 1, - "roots": [], + "roots": [22], "scope": 0, "nodes": [ - {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, - {"id": 5, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, - {"id": 8, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 17, "role": "CTRL", "label": null}], "proj": {"par": 17, "idx": 0}}, - {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}], "proj": null}, - {"id": 14, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 0, "role": "MEM", "label": null}, {"idx": 2, "def": 0, "role": "DATA", "label": null}, {"idx": 3, "def": 0, "role": "DATA", "label": null}], "proj": null}, - {"id": 16, "label": ".f", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, - {"id": 17, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 0, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "True", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 0}}, + {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, + {"id": 14, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 0, "role": "MEM", "label": null}, {"idx": 2, "def": 0, "role": "DATA", "label": null}, {"idx": 3, "def": 0, "role": "DATA", "label": null}], "proj": null}, + {"id": 16, "label": ".f", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, {"id": 21, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, {"id": 22, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 21, "role": "DATA", "label": null}, {"idx": 4, "def": 16, "role": "DATA", "label": null}], "proj": null} ], diff --git a/chapter11/docs/graph3-snip.svg b/chapter11/docs/graph3-snip.svg index cf6420c5..9f5218af 100644 --- a/chapter11/docs/graph3-snip.svg +++ b/chapter11/docs/graph3-snip.svg @@ -1,4 +1,4 @@ -#16[1] → #14 · MEM#16[2] → #9 · DATA#22[0] → #8 · CTRL#22[1] → #14 · MEM#22[2] → #9 · DATA#22[3] → #21 · DATA#22[4] → #16 · DATATrue  #8/0#8 True +Projection 0 of #0 Type not computed -$ctrl  #5/0#5 $ctrl -Projection 0 of #2 +new S  #9#9 new S Type not computed -[0] → #2 CTRLTrue  #8/0#8 True -Projection 0 of #17 +[0] → — CTRL0.f =  #14#14 .f = Type not computed -[0] → #17 CTRLnew S  #9#9 new S -Type not computed - -[0] → #5 CTRL0.f =  #14#14 .f = -Type not computed - -[0] → #5 CTRL +[0] → — CTRL [1] → — MEM [2] → — DATA -[3] → — DATA0123.f  #16#16 .f +[3] → — DATA0123.f  #16#16 .f Type not computed -[0] → #5 CTRL +[0] → — CTRL [1] → #14 MEM -[2] → #9 DATA012If  #17#17 If -Type not computed - -[0] → #5 CTRL -[1] → — DATA01#1  #21#21 #1 +[2] → #9 DATA012#1  #21#21 #1 Type not computed -.f =  #22#22 .f = +.f =  #22#22 .f = Type not computed [0] → #8 CTRL diff --git a/chapter11/docs/graph3.json b/chapter11/docs/graph3.json index 998c6f87..577d7c3b 100644 --- a/chapter11/docs/graph3.json +++ b/chapter11/docs/graph3.json @@ -2,32 +2,25 @@ "ver": 1, "comp": "chapter11/docs/graph3.svg", "step": 1, - "roots": [], + "roots": [25], "scope": 0, "nodes": [ - {"id": 1, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 23, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 224, "role": "MEM", "label": null}], "proj": null}, + {"id": 1, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 224, "role": "MEM", "label": null}], "proj": null}, {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, - {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": null}, {"id": 4, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, - {"id": 5, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, {"id": 6, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 2, "role": "MEM", "label": null}], "proj": {"par": 2, "idx": 1}}, - {"id": 7, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 2}}, - {"id": 8, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 17, "role": "CTRL", "label": null}], "proj": {"par": 17, "idx": 0}}, - {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}], "proj": null}, - {"id": 10, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 17, "role": "CTRL", "label": null}], "proj": {"par": 17, "idx": 1}}, + {"id": 8, "label": "True", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 0}}, + {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, {"id": 11, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, - {"id": 12, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 11, "role": "DATA", "label": null}], "proj": null}, - {"id": 13, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}], "proj": null}, - {"id": 14, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 12, "role": "MEM", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, - {"id": 16, "label": ".f", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, - {"id": 17, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 12, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 11, "role": "DATA", "label": null}], "proj": null}, + {"id": 13, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, + {"id": 14, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 12, "role": "MEM", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 16, "label": ".f", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, {"id": 21, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, {"id": 22, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 21, "role": "DATA", "label": null}, {"idx": 4, "def": 16, "role": "DATA", "label": null}], "proj": null}, - {"id": 23, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 8, "role": "CTRL", "label": null}, {"idx": 2, "def": 10, "role": "CTRL", "label": null}], "proj": null}, - {"id": 25, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 23, "role": "CTRL", "label": null}, {"idx": 1, "def": 1, "role": "MEM", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, - {"id": 224, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 23, "role": "ASSOC", "label": null}, {"idx": 1, "def": 22, "role": "MEM", "label": null}, {"idx": 2, "def": 14, "role": "MEM", "label": null}], "proj": null} + {"id": 25, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 1, "role": "MEM", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 224, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 22, "role": "MEM", "label": null}, {"idx": 2, "def": 14, "role": "MEM", "label": null}], "proj": null} ], "groups": [ - {"id": 17, "par": 0, "nodes": [1, 8, 10, 17, 22, 23, 224]} ] } diff --git a/chapter11/docs/graph3.svg b/chapter11/docs/graph3.svg index 6fe5fe73..0247b5c6 100644 --- a/chapter11/docs/graph3.svg +++ b/chapter11/docs/graph3.svg @@ -1,4 +1,4 @@ -#1[1] → #6 · MEM#1[2] → #224 · MEM#12[1] → #6 · MEM#12[2] → #9 · DATA#12[3] → #11 · DATA#14[1] → #12 · MEM#14[2] → #13 · DATA#14[3] → #4 · DATA#16[1] → #14 · MEM#16[2] → #9 · DATA#22[0] → #8 · CTRL#22[1] → #14 · MEM#22[2] → #9 · DATA#22[3] → #21 · DATA#22[4] → #16 · DATA#25[1] → #1 · MEM#25[2] → #16 · DATA#224[1] → #22 · MEM#224[2] → #14 · MEMMemMerge  #1#1 MemMerge Type not computed -[0] → #23 CTRL +[0] → — CTRL [1] → #6 MEM -[2] → #224 MEM012Start  #2#2 Start +[2] → #224 MEM012Start  #2#2 Start Type not computed -Stop  #3#3 Stop +#0  #4#4 #0 Type not computed -[0] → #25 CTRL0#0  #4#4 #0 -Type not computed - -$ctrl  #5/0#5 $ctrl -Projection 0 of #2 -Type not computed - -[0] → #2 CTRL$mem  #6/1#6 $mem +$mem  #6/1#6 $mem Projection 1 of #2 Type not computed -[0] → #2 MEMarg  #7/2#7 arg -Projection 2 of #2 -Type not computed - -[0] → #2 DATATrue  #8/0#8 True -Projection 0 of #17 +[0] → #2 MEMTrue  #8/0#8 True +Projection 0 of #0 Type not computed -[0] → #17 CTRLnew S  #9#9 new S +new S  #9#9 new S Type not computed -[0] → #5 CTRL0False  #10/1#10 False -Projection 1 of #17 +[0] → — CTRL0#2  #11#11 #2 Type not computed -[0] → #17 CTRL#2  #11#11 #2 +.f =  #12#12 .f = Type not computed -.f =  #12#12 .f = -Type not computed - -[0] → #5 CTRL +[0] → — CTRL [1] → #6 MEM [2] → #9 DATA -[3] → #11 DATA0123new S  #13#13 new S +[3] → #11 DATA0123new S  #13#13 new S Type not computed -[0] → #5 CTRL0.f =  #14#14 .f = +[0] → — CTRL0.f =  #14#14 .f = Type not computed -[0] → #5 CTRL +[0] → — CTRL [1] → #12 MEM [2] → #13 DATA -[3] → #4 DATA0123.f  #16#16 .f +[3] → #4 DATA0123.f  #16#16 .f Type not computed -[0] → #5 CTRL +[0] → — CTRL [1] → #14 MEM -[2] → #9 DATA012If  #17#17 If -Type not computed - -[0] → #5 CTRL -[1] → #7 DATA01#1  #21#21 #1 +[2] → #9 DATA012#1  #21#21 #1 Type not computed -.f =  #22#22 .f = +.f =  #22#22 .f = Type not computed [0] → #8 CTRL [1] → #14 MEM [2] → #9 DATA [3] → #21 DATA -[4] → #16 DATA01234Region  #23#23 Region -Type not computed - -[0] → — DATA -[1] → #8 CTRL -[2] → #10 CTRL012Return  #25#25 Return +[4] → #16 DATA01234Return  #25#25 Return Type not computed -[0] → #23 CTRL +[0] → — CTRL [1] → #1 MEM -[2] → #16 DATA012MemPhi_2  #224#224 MemPhi_2 +[2] → #16 DATA012MemPhi_2  #224#224 MemPhi_2 Type not computed -[0] → #23 ASSOC +[0] → — ASSOC [1] → #22 MEM -[2] → #14 MEM[0] → #23012If  #17If · 7 nodes−Fold region +[2] → #14 MEM012 diff --git a/chapter11/docs/graph4.json b/chapter11/docs/graph4.json index b021c03f..44c1c055 100644 --- a/chapter11/docs/graph4.json +++ b/chapter11/docs/graph4.json @@ -2,41 +2,23 @@ "ver": 1, "comp": "chapter11/docs/graph4.svg", "step": 1, - "roots": [], + "roots": [37], "scope": 0, "nodes": [ {"id": 1, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 230, "role": "MEM", "label": null}], "proj": null}, {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, - {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 37, "role": "CTRL", "label": null}], "proj": null}, {"id": 4, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, - {"id": 5, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, {"id": 6, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 2, "role": "MEM", "label": null}], "proj": {"par": 2, "idx": 1}}, {"id": 7, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 2}}, - {"id": 8, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 16, "role": "CTRL", "label": null}], "proj": {"par": 16, "idx": 0}}, - {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}], "proj": null}, + {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, {"id": 10, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, - {"id": 11, "label": "Loop", "type": null, "kind": "LOOP", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 5, "role": "CTRL", "label": null}, {"idx": 2, "def": 32, "role": "CTRL", "label": null}], "proj": null}, - {"id": 12, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 16, "role": "CTRL", "label": null}], "proj": {"par": 16, "idx": 1}}, - {"id": 13, "label": "φ_arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 11, "role": "ASSOC", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}, {"idx": 2, "def": 35, "role": "DATA", "label": null}], "proj": null}, - {"id": 14, "label": "<", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}], "proj": null}, - {"id": 15, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": {"par": 25, "idx": 0}}, - {"id": 16, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "DATA", "label": null}], "proj": null}, - {"id": 17, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": {"par": 25, "idx": 1}}, {"id": 21, "label": "//", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}, {"idx": 2, "def": 22, "role": "DATA", "label": null}], "proj": null}, {"id": 22, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, - {"id": 23, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 13, "role": "DATA", "label": null}, {"idx": 2, "def": 24, "role": "DATA", "label": null}], "proj": null}, - {"id": 24, "label": "#5", "type": null, "kind": "DATA", "edges": [], "proj": null}, - {"id": 25, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}, {"idx": 1, "def": 23, "role": "DATA", "label": null}], "proj": null}, {"id": 31, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 230, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 21, "role": "DATA", "label": null}], "proj": null}, - {"id": 32, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 15, "role": "CTRL", "label": null}, {"idx": 2, "def": 17, "role": "CTRL", "label": null}], "proj": null}, - {"id": 35, "label": "-", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 13, "role": "DATA", "label": null}, {"idx": 2, "def": 36, "role": "DATA", "label": null}], "proj": null}, - {"id": 36, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, - {"id": 37, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 12, "role": "CTRL", "label": null}, {"idx": 1, "def": 1, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, - {"id": 230, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 11, "role": "ASSOC", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 233, "role": "MEM", "label": null}], "proj": null}, - {"id": 233, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 32, "role": "ASSOC", "label": null}, {"idx": 1, "def": 31, "role": "MEM", "label": null}, {"idx": 2, "def": 230, "role": "MEM", "label": null}], "proj": null} + {"id": 37, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 1, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 230, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 233, "role": "MEM", "label": null}], "proj": null}, + {"id": 233, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 31, "role": "MEM", "label": null}, {"idx": 2, "def": 230, "role": "MEM", "label": null}], "proj": null} ], "groups": [ - {"id": 11, "par": 0, "nodes": [8, 10, 11, 12, 13, 14, 16, 35, 230]}, - {"id": 25, "par": 11, "nodes": [15, 17, 21, 23, 25, 31, 32, 233]} ] } diff --git a/chapter11/docs/graph4.svg b/chapter11/docs/graph4.svg index c268b4e9..9ca92879 100644 --- a/chapter11/docs/graph4.svg +++ b/chapter11/docs/graph4.svg @@ -1,4 +1,4 @@ -#1[1] → #6 · MEM#1[2] → #230 · MEM#10[1] → #6 · MEM#10[2] → #9 · DATA#10[3] → #4 · DATA#21[1] → #7 · DATA#21[2] → #22 · DATA#31[1] → #230 · MEM#31[2] → #9 · DATA#31[3] → #21 · DATA#37[1] → #1 · MEM#37[2] → #9 · DATA#230[1] → #10 · MEM#230[2] → #233 · MEM#233[1] → #31 · MEM#233[2] → #230 · MEMMemMerge  #1#1 MemMerge Type not computed [0] → — DATA [1] → #6 MEM -[2] → #230 MEM012Start  #2#2 Start +[2] → #230 MEM012Start  #2#2 Start Type not computed -Stop  #3#3 Stop +#0  #4#4 #0 Type not computed -[0] → #37 CTRL0#0  #4#4 #0 -Type not computed - -$ctrl  #5/0#5 $ctrl -Projection 0 of #2 -Type not computed - -[0] → #2 CTRL$mem  #6/1#6 $mem +$mem  #6/1#6 $mem Projection 1 of #2 Type not computed -[0] → #2 MEMarg  #7/2#7 arg +[0] → #2 MEMarg  #7/2#7 arg Projection 2 of #2 Type not computed -[0] → #2 DATATrue  #8/0#8 True -Projection 0 of #16 -Type not computed - -[0] → #16 CTRLnew S  #9#9 new S +[0] → #2 DATAnew S  #9#9 new S Type not computed -[0] → #5 CTRL0.f =  #10#10 .f = +[0] → — CTRL0.f =  #10#10 .f = Type not computed [0] → — DATA [1] → #6 MEM [2] → #9 DATA -[3] → #4 DATA0123Loop  #11#11 Loop -Type not computed - -[0] → — DATA -[1] → #5 CTRL -[2] → #32 CTRL012False  #12/1#12 False -Projection 1 of #16 -Type not computed - -[0] → #16 CTRLφ_arg  #13#13 φ_arg -Type not computed - -[0] → #11 ASSOC -[1] → #7 DATA -[2] → #35 DATA[0] → #11012<  #14#14 < -Type not computed - -[0] → — DATA -[1] → #4 DATA -[2] → #13 DATA012True  #15/0#15 True -Projection 0 of #25 -Type not computed - -[0] → #25 CTRLIf  #16#16 If -Type not computed - -[0] → #11 CTRL -[1] → #14 DATA01False  #17/1#17 False -Projection 1 of #25 -Type not computed - -[0] → #25 CTRL//  #21#21 // +[3] → #4 DATA0123//  #21#21 // Type not computed [0] → — DATA [1] → #7 DATA -[2] → #22 DATA012#3  #22#22 #3 +[2] → #22 DATA012#3  #22#22 #3 Type not computed -==  #23#23 == -Type not computed - -[0] → — DATA -[1] → #13 DATA -[2] → #24 DATA012#5  #24#24 #5 -Type not computed - -If  #25#25 If -Type not computed - -[0] → #8 CTRL -[1] → #23 DATA01.f =  #31#31 .f = +.f =  #31#31 .f = Type not computed [0] → — DATA [1] → #230 MEM [2] → #9 DATA -[3] → #21 DATA0123Region  #32#32 Region -Type not computed - -[0] → — DATA -[1] → #15 CTRL -[2] → #17 CTRL012-  #35#35 - -Type not computed - -[0] → — DATA -[1] → #13 DATA -[2] → #36 DATA012#1  #36#36 #1 -Type not computed - -Return  #37#37 Return +[3] → #21 DATA0123Return  #37#37 Return Type not computed -[0] → #12 CTRL +[0] → — CTRL [1] → #1 MEM -[2] → #9 DATA012MemPhi_2  #230#230 MemPhi_2 +[2] → #9 DATA012MemPhi_2  #230#230 MemPhi_2 Type not computed -[0] → #11 ASSOC +[0] → — ASSOC [1] → #10 MEM -[2] → #233 MEM[0] → #11012MemPhi_2  #233#233 MemPhi_2 +[2] → #233 MEM012MemPhi_2  #233#233 MemPhi_2 Type not computed -[0] → #32 ASSOC +[0] → — ASSOC [1] → #31 MEM -[2] → #230 MEM[0] → #32012Loop  #11Loop · 17 nodes−Fold regionIf  #25If · 8 nodes−Fold region +[2] → #230 MEM012 diff --git a/chapter11/docs/graph5.json b/chapter11/docs/graph5.json index 2211cb19..659384e0 100644 --- a/chapter11/docs/graph5.json +++ b/chapter11/docs/graph5.json @@ -2,41 +2,23 @@ "ver": 1, "comp": "chapter11/docs/graph5.svg", "step": 1, - "roots": [], + "roots": [37], "scope": 0, "nodes": [ - {"id": 1, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 230, "role": "MEM", "label": null}], "proj": null}, + {"id": 1, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 230, "role": "MEM", "label": null}], "proj": null}, {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, - {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 37, "role": "CTRL", "label": null}], "proj": null}, {"id": 4, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, - {"id": 5, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, {"id": 6, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 2, "role": "MEM", "label": null}], "proj": {"par": 2, "idx": 1}}, {"id": 7, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 2}}, - {"id": 8, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 16, "role": "CTRL", "label": null}], "proj": {"par": 16, "idx": 0}}, - {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}], "proj": null}, - {"id": 10, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, - {"id": 11, "label": "Loop", "type": null, "kind": "LOOP", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 5, "role": "CTRL", "label": null}, {"idx": 2, "def": 32, "role": "CTRL", "label": null}], "proj": null}, - {"id": 12, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 16, "role": "CTRL", "label": null}], "proj": {"par": 16, "idx": 1}}, - {"id": 13, "label": "φ_arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 11, "role": "ASSOC", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}, {"idx": 2, "def": 35, "role": "DATA", "label": null}], "proj": null}, - {"id": 14, "label": "<", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}], "proj": null}, - {"id": 15, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": {"par": 25, "idx": 0}}, - {"id": 16, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "DATA", "label": null}], "proj": null}, - {"id": 17, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": {"par": 25, "idx": 1}}, - {"id": 21, "label": "//", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}, {"idx": 2, "def": 22, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, + {"id": 10, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 21, "label": "//", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}, {"idx": 2, "def": 22, "role": "DATA", "label": null}], "proj": null}, {"id": 22, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, - {"id": 23, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}, {"idx": 1, "def": 13, "role": "DATA", "label": null}, {"idx": 2, "def": 24, "role": "DATA", "label": null}], "proj": null}, - {"id": 24, "label": "#5", "type": null, "kind": "DATA", "edges": [], "proj": null}, - {"id": 25, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}, {"idx": 1, "def": 23, "role": "DATA", "label": null}], "proj": null}, - {"id": 31, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}, {"idx": 1, "def": 230, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 21, "role": "DATA", "label": null}], "proj": null}, - {"id": 32, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 15, "role": "CTRL", "label": null}, {"idx": 2, "def": 17, "role": "CTRL", "label": null}], "proj": null}, - {"id": 35, "label": "-", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}, {"idx": 1, "def": 13, "role": "DATA", "label": null}, {"idx": 2, "def": 36, "role": "DATA", "label": null}], "proj": null}, - {"id": 36, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, - {"id": 37, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 12, "role": "CTRL", "label": null}, {"idx": 1, "def": 1, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, - {"id": 230, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 11, "role": "ASSOC", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 233, "role": "MEM", "label": null}], "proj": null}, - {"id": 233, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 32, "role": "ASSOC", "label": null}, {"idx": 1, "def": 31, "role": "MEM", "label": null}, {"idx": 2, "def": 230, "role": "MEM", "label": null}], "proj": null} + {"id": 31, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 230, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 21, "role": "DATA", "label": null}], "proj": null}, + {"id": 37, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 1, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 230, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 233, "role": "MEM", "label": null}], "proj": null}, + {"id": 233, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 31, "role": "MEM", "label": null}, {"idx": 2, "def": 230, "role": "MEM", "label": null}], "proj": null} ], "groups": [ - {"id": 11, "par": 0, "nodes": [1, 8, 11, 12, 13, 14, 16, 23, 31, 35, 230]}, - {"id": 25, "par": 11, "nodes": [15, 17, 25, 32, 233]} ] } diff --git a/chapter11/docs/graph5.svg b/chapter11/docs/graph5.svg index 1669e008..c120550f 100644 --- a/chapter11/docs/graph5.svg +++ b/chapter11/docs/graph5.svg @@ -1,4 +1,4 @@ -#1[1] → #6 · MEM#1[2] → #230 · MEM#10[1] → #6 · MEM#10[2] → #9 · DATA#10[3] → #4 · DATA#21[1] → #7 · DATA#21[2] → #22 · DATA#31[1] → #230 · MEM#31[2] → #9 · DATA#31[3] → #21 · DATA#37[1] → #1 · MEM#37[2] → #9 · DATA#230[1] → #10 · MEM#230[2] → #233 · MEM#233[1] → #31 · MEM#233[2] → #230 · MEMMemMerge  #1#1 MemMerge Type not computed -[0] → #11 CTRL +[0] → — CTRL [1] → #6 MEM -[2] → #230 MEM012Start  #2#2 Start +[2] → #230 MEM012Start  #2#2 Start Type not computed -Stop  #3#3 Stop +#0  #4#4 #0 Type not computed -[0] → #37 CTRL0#0  #4#4 #0 -Type not computed - -$ctrl  #5/0#5 $ctrl -Projection 0 of #2 -Type not computed - -[0] → #2 CTRL$mem  #6/1#6 $mem +$mem  #6/1#6 $mem Projection 1 of #2 Type not computed -[0] → #2 MEMarg  #7/2#7 arg +[0] → #2 MEMarg  #7/2#7 arg Projection 2 of #2 Type not computed -[0] → #2 DATATrue  #8/0#8 True -Projection 0 of #16 +[0] → #2 DATAnew S  #9#9 new S Type not computed -[0] → #16 CTRLnew S  #9#9 new S +[0] → — CTRL0.f =  #10#10 .f = Type not computed -[0] → #5 CTRL0.f =  #10#10 .f = -Type not computed - -[0] → #5 CTRL +[0] → — CTRL [1] → #6 MEM [2] → #9 DATA -[3] → #4 DATA0123Loop  #11#11 Loop -Type not computed - -[0] → — DATA -[1] → #5 CTRL -[2] → #32 CTRL012False  #12/1#12 False -Projection 1 of #16 +[3] → #4 DATA0123//  #21#21 // Type not computed -[0] → #16 CTRLφ_arg  #13#13 φ_arg -Type not computed - -[0] → #11 ASSOC +[0] → — CTRL [1] → #7 DATA -[2] → #35 DATA[0] → #11012<  #14#14 < -Type not computed - -[0] → #11 CTRL -[1] → #4 DATA -[2] → #13 DATA012True  #15/0#15 True -Projection 0 of #25 -Type not computed - -[0] → #25 CTRLIf  #16#16 If -Type not computed - -[0] → #11 CTRL -[1] → #14 DATA01False  #17/1#17 False -Projection 1 of #25 +[2] → #22 DATA012#3  #22#22 #3 Type not computed -[0] → #25 CTRL//  #21#21 // +.f =  #31#31 .f = Type not computed -[0] → #2 CTRL -[1] → #7 DATA -[2] → #22 DATA012#3  #22#22 #3 -Type not computed - -==  #23#23 == -Type not computed - -[0] → #11 CTRL -[1] → #13 DATA -[2] → #24 DATA012#5  #24#24 #5 -Type not computed - -If  #25#25 If -Type not computed - -[0] → #8 CTRL -[1] → #23 DATA01.f =  #31#31 .f = -Type not computed - -[0] → #11 CTRL +[0] → — CTRL [1] → #230 MEM [2] → #9 DATA -[3] → #21 DATA0123Region  #32#32 Region -Type not computed - -[0] → — DATA -[1] → #15 CTRL -[2] → #17 CTRL012-  #35#35 - -Type not computed - -[0] → #11 CTRL -[1] → #13 DATA -[2] → #36 DATA012#1  #36#36 #1 -Type not computed - -Return  #37#37 Return +[3] → #21 DATA0123Return  #37#37 Return Type not computed -[0] → #12 CTRL +[0] → — CTRL [1] → #1 MEM -[2] → #9 DATA012MemPhi_2  #230#230 MemPhi_2 +[2] → #9 DATA012MemPhi_2  #230#230 MemPhi_2 Type not computed -[0] → #11 ASSOC +[0] → — ASSOC [1] → #10 MEM -[2] → #233 MEM[0] → #11012MemPhi_2  #233#233 MemPhi_2 +[2] → #233 MEM012MemPhi_2  #233#233 MemPhi_2 Type not computed -[0] → #32 ASSOC +[0] → — ASSOC [1] → #31 MEM -[2] → #230 MEM[0] → #32012Loop  #11Loop · 16 nodes−Fold regionIf  #25If · 5 nodes−Fold region +[2] → #230 MEM012 diff --git a/chapter11/docs/graph6.json b/chapter11/docs/graph6.json index 1c08947a..512c308d 100644 --- a/chapter11/docs/graph6.json +++ b/chapter11/docs/graph6.json @@ -2,41 +2,24 @@ "ver": 1, "comp": "chapter11/docs/graph6.svg", "step": 1, - "roots": [], + "roots": [37], "scope": 0, "nodes": [ - {"id": 1, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 12, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 230, "role": "MEM", "label": null}], "proj": null}, + {"id": 1, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 230, "role": "MEM", "label": null}], "proj": null}, {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, - {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 37, "role": "CTRL", "label": null}], "proj": null}, {"id": 4, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, - {"id": 5, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, {"id": 6, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 2, "role": "MEM", "label": null}], "proj": {"par": 2, "idx": 1}}, {"id": 7, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 2}}, - {"id": 8, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 16, "role": "CTRL", "label": null}], "proj": {"par": 16, "idx": 0}}, - {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}], "proj": null}, - {"id": 10, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, - {"id": 11, "label": "Loop", "type": null, "kind": "LOOP", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 5, "role": "CTRL", "label": null}, {"idx": 2, "def": 32, "role": "CTRL", "label": null}], "proj": null}, - {"id": 12, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 16, "role": "CTRL", "label": null}], "proj": {"par": 16, "idx": 1}}, - {"id": 13, "label": "φ_arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 11, "role": "ASSOC", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}, {"idx": 2, "def": 35, "role": "DATA", "label": null}], "proj": null}, - {"id": 14, "label": "<", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}], "proj": null}, - {"id": 15, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": {"par": 25, "idx": 0}}, - {"id": 16, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "DATA", "label": null}], "proj": null}, - {"id": 17, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": {"par": 25, "idx": 1}}, - {"id": 21, "label": "//", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}, {"idx": 2, "def": 22, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, + {"id": 10, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 15, "label": "True", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 0}}, + {"id": 21, "label": "//", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}, {"idx": 2, "def": 22, "role": "DATA", "label": null}], "proj": null}, {"id": 22, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, - {"id": 23, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}, {"idx": 1, "def": 13, "role": "DATA", "label": null}, {"idx": 2, "def": 24, "role": "DATA", "label": null}], "proj": null}, - {"id": 24, "label": "#5", "type": null, "kind": "DATA", "edges": [], "proj": null}, - {"id": 25, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}, {"idx": 1, "def": 23, "role": "DATA", "label": null}], "proj": null}, {"id": 31, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 15, "role": "CTRL", "label": null}, {"idx": 1, "def": 230, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 21, "role": "DATA", "label": null}], "proj": null}, - {"id": 32, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 15, "role": "CTRL", "label": null}, {"idx": 2, "def": 17, "role": "CTRL", "label": null}], "proj": null}, - {"id": 35, "label": "-", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 32, "role": "CTRL", "label": null}, {"idx": 1, "def": 13, "role": "DATA", "label": null}, {"idx": 2, "def": 36, "role": "DATA", "label": null}], "proj": null}, - {"id": 36, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, - {"id": 37, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 12, "role": "CTRL", "label": null}, {"idx": 1, "def": 1, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, - {"id": 230, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 11, "role": "ASSOC", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 233, "role": "MEM", "label": null}], "proj": null}, - {"id": 233, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 32, "role": "ASSOC", "label": null}, {"idx": 1, "def": 31, "role": "MEM", "label": null}, {"idx": 2, "def": 230, "role": "MEM", "label": null}], "proj": null} + {"id": 37, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 1, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 230, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 233, "role": "MEM", "label": null}], "proj": null}, + {"id": 233, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 31, "role": "MEM", "label": null}, {"idx": 2, "def": 230, "role": "MEM", "label": null}], "proj": null} ], "groups": [ - {"id": 11, "par": 0, "nodes": [8, 11, 12, 13, 14, 16, 23, 230]}, - {"id": 25, "par": 11, "nodes": [15, 17, 25, 31, 32, 35, 233]} ] } diff --git a/chapter11/docs/graph6.svg b/chapter11/docs/graph6.svg index 8862f25c..d6dec88f 100644 --- a/chapter11/docs/graph6.svg +++ b/chapter11/docs/graph6.svg @@ -1,4 +1,4 @@ -#1[1] → #6 · MEM#1[2] → #230 · MEM#10[1] → #6 · MEM#10[2] → #9 · DATA#10[3] → #4 · DATA#21[1] → #7 · DATA#21[2] → #22 · DATA#31[0] → #15 · CTRL#31[1] → #230 · MEM#31[2] → #9 · DATA#31[3] → #21 · DATA#37[1] → #1 · MEM#37[2] → #9 · DATA#230[1] → #10 · MEM#230[2] → #233 · MEM#233[1] → #31 · MEM#233[2] → #230 · MEMMemMerge  #1#1 MemMerge Type not computed -[0] → #12 CTRL +[0] → — CTRL [1] → #6 MEM -[2] → #230 MEM012Start  #2#2 Start +[2] → #230 MEM012Start  #2#2 Start Type not computed -Stop  #3#3 Stop +#0  #4#4 #0 Type not computed -[0] → #37 CTRL0#0  #4#4 #0 -Type not computed - -$ctrl  #5/0#5 $ctrl -Projection 0 of #2 -Type not computed - -[0] → #2 CTRL$mem  #6/1#6 $mem +$mem  #6/1#6 $mem Projection 1 of #2 Type not computed -[0] → #2 MEMarg  #7/2#7 arg +[0] → #2 MEMarg  #7/2#7 arg Projection 2 of #2 Type not computed -[0] → #2 DATATrue  #8/0#8 True -Projection 0 of #16 +[0] → #2 DATAnew S  #9#9 new S Type not computed -[0] → #16 CTRLnew S  #9#9 new S +[0] → — CTRL0.f =  #10#10 .f = Type not computed -[0] → #5 CTRL0.f =  #10#10 .f = -Type not computed - -[0] → #5 CTRL +[0] → — CTRL [1] → #6 MEM [2] → #9 DATA -[3] → #4 DATA0123Loop  #11#11 Loop -Type not computed - -[0] → — DATA -[1] → #5 CTRL -[2] → #32 CTRL012False  #12/1#12 False -Projection 1 of #16 +[3] → #4 DATA0123True  #15/0#15 True +Projection 0 of #0 Type not computed -[0] → #16 CTRLφ_arg  #13#13 φ_arg +//  #21#21 // Type not computed -[0] → #11 ASSOC +[0] → — CTRL [1] → #7 DATA -[2] → #35 DATA[0] → #11012<  #14#14 < +[2] → #22 DATA012#3  #22#22 #3 Type not computed -[0] → #11 CTRL -[1] → #4 DATA -[2] → #13 DATA012True  #15/0#15 True -Projection 0 of #25 -Type not computed - -[0] → #25 CTRLIf  #16#16 If -Type not computed - -[0] → #11 CTRL -[1] → #14 DATA01False  #17/1#17 False -Projection 1 of #25 -Type not computed - -[0] → #25 CTRL//  #21#21 // -Type not computed - -[0] → #5 CTRL -[1] → #7 DATA -[2] → #22 DATA012#3  #22#22 #3 -Type not computed - -==  #23#23 == -Type not computed - -[0] → #8 CTRL -[1] → #13 DATA -[2] → #24 DATA012#5  #24#24 #5 -Type not computed - -If  #25#25 If -Type not computed - -[0] → #8 CTRL -[1] → #23 DATA01.f =  #31#31 .f = +.f =  #31#31 .f = Type not computed [0] → #15 CTRL [1] → #230 MEM [2] → #9 DATA -[3] → #21 DATA0123Region  #32#32 Region -Type not computed - -[0] → — DATA -[1] → #15 CTRL -[2] → #17 CTRL012-  #35#35 - -Type not computed - -[0] → #32 CTRL -[1] → #13 DATA -[2] → #36 DATA012#1  #36#36 #1 -Type not computed - -Return  #37#37 Return +[3] → #21 DATA0123Return  #37#37 Return Type not computed -[0] → #12 CTRL +[0] → — CTRL [1] → #1 MEM -[2] → #9 DATA012MemPhi_2  #230#230 MemPhi_2 +[2] → #9 DATA012MemPhi_2  #230#230 MemPhi_2 Type not computed -[0] → #11 ASSOC +[0] → — ASSOC [1] → #10 MEM -[2] → #233 MEM[0] → #11012MemPhi_2  #233#233 MemPhi_2 +[2] → #233 MEM012MemPhi_2  #233#233 MemPhi_2 Type not computed -[0] → #32 ASSOC +[0] → — ASSOC [1] → #31 MEM -[2] → #230 MEM[0] → #32012Loop  #11Loop · 15 nodes−Fold regionIf  #25If · 7 nodes−Fold region +[2] → #230 MEM012 diff --git a/chapter11/docs/graph7.svg b/chapter11/docs/graph7.svg index e83b8d54..15d886dc 100644 --- a/chapter11/docs/graph7.svg +++ b/chapter11/docs/graph7.svg @@ -60,7 +60,7 @@ .count { font-size:20px; min-width:35px; text-align:center; } #N { width:6ch; } #scrub { width:clamp(120px,35vw,600px); } - #8[1] → #1 · CTRL#8[2] → #8 · CTRL$ctrl  #1/0#1 $ctrl + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"><g class="region" transform="translate(164,171)"><rect class="region-box" rx="8" width="176" height="130" fill="#f1f6fc"/></g></g><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge CTRL" id="e8i1" d="M236,118 L236,223" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#8[1] → #1 · CTRL#8[2] → #8 · CTRL$ctrl  #1/0#1 $ctrl Projection 0 of #2 Type not computed diff --git a/chapter11/docs/graph8.svg b/chapter11/docs/graph8.svg index 4db46240..d96a9a7d 100644 --- a/chapter11/docs/graph8.svg +++ b/chapter11/docs/graph8.svg @@ -60,7 +60,7 @@ .count { font-size:20px; min-width:35px; text-align:center; } #N { width:6ch; } #scrub { width:clamp(120px,35vw,600px); } - </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"><g class="region" transform="translate(24,171)"><rect class="region-box" rx="8" width="313" height="298" fill="#f1f6fc"/></g></g><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge CTRL" id="e3i0" d="M126,575 C126,599 215.5,602 215.5,626" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#3[0] → #21 · CTRL#8[1] → #6 · CTRL#8[2] → #5 · CTRL#18[0] → #8 · CTRL#18[1] → #4 · DATA#21[0] → #1 · CTRL#21[2] → #4 · DATATrue  #1/0#1 True + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"><g class="region" transform="translate(24,171)"><rect class="region-box" rx="8" width="313" height="298" fill="#f1f6fc"/></g></g><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge CTRL" id="e3i0" d="M126,575 C126,599 215.5,602 215.5,626" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#3[0] → #21 · CTRL#8[1] → #6 · CTRL#8[2] → #5 · CTRL#18[0] → #8 · CTRL#18[1] → #4 · DATA#21[0] → #1 · CTRL#21[2] → #4 · DATATrue  #1/0#1 True Projection 0 of #18 Type not computed diff --git a/chapter12/docs/lattice.gv b/chapter12/docs/lattice.gv index f3b5051c..e8631cd5 100644 --- a/chapter12/docs/lattice.gv +++ b/chapter12/docs/lattice.gv @@ -118,9 +118,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=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="#ffc0cb">tuple</TD></TR> + <TR><TD BGCOLOR="black"><FONT COLOR="white">type</FONT></TD></TR> + </TABLE> + >]; + TUPLE2 [shape=plain, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="#ffc0cb">tuple</TD></TR> + <TR><TD BGCOLOR="black"><FONT COLOR="white">type</FONT></TD></TR> + <TR><TD BGCOLOR="black"><FONT COLOR="white">type</FONT></TD></TR> + </TABLE> + >]; + TUPLEN [shape=plain, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="#ffc0cb">tuple</TD></TR> + <TR><TD BGCOLOR="black"><FONT COLOR="white">type</FONT></TD></TR> + <TR><TD BGCOLOR="black"><FONT COLOR="white">…</FONT></TD></TR> + <TR><TD BGCOLOR="black"><FONT COLOR="white">type</FONT></TD></TR> + </TABLE> + >]; {rank=same; TUPLE1; TUPLE2; TUPLEN;} TUPLE1 -> TUPLE2 -> TUPLEN [style=invis]; TUPLE_TOP -> {TUPLE1 TUPLE2 TUPLEN}; diff --git a/chapter12/docs/lattice.svg b/chapter12/docs/lattice.svg index bc64abb6..41804d92 100644 --- a/chapter12/docs/lattice.svg +++ b/chapter12/docs/lattice.svg @@ -4,141 +4,141 @@ <!-- Generated by graphviz version 12.2.0 (20241103.1931) --> <!-- Title: Lattice Pages: 1 --> -<svg width="2357pt" height="533pt" - viewBox="0.00 0.00 2357.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)"> +<svg width="2261pt" height="603pt" + viewBox="0.00 0.00 2261.00 603.45" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 599.45)"> <title>Lattice - + cluster_control - -Control + +Control cluster_integer - -Integer + +Integer cluster_float - -Float + +Float 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 -precise alias slices + +Memory +precise alias slices cluster_tuple - -Tuple -collection of types + +Tuple +collection of types TOP - -⊤ + +⊤ XCTRL - -⊤:ctrl + +⊤:ctrl TOP->XCTRL - - + + INT_TOP - -⊤:int + +⊤:int TOP->INT_TOP - - + + FLT_TOP - -⊤ -:flt + +⊤ +:flt TOP->FLT_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 - - + + @@ -155,7 +155,7 @@ XCTRL->CTRL - + @@ -174,8 +174,8 @@ INT_TOP->INT_NEG - - + + @@ -186,8 +186,8 @@ INT_TOP->INT_ZERO - - + + @@ -198,8 +198,8 @@ INT_TOP->INT_POS - - + + @@ -237,38 +237,38 @@ FLT_MINDOTS - -… negative constants + +… negative constants FLT_TOP->FLT_MINDOTS - - + + FLT_ZERO - -0.0 + +0.0 FLT_TOP->FLT_ZERO - - + + FLT_MAXDOTS - -positive constants … + +positive constants … FLT_TOP->FLT_MAXDOTS - - + + @@ -287,70 +287,70 @@ FLT_MINDOTS->FLT_BOT - - + + FLT_ZERO->FLT_BOT - - + + FLT_MAXDOTS->FLT_BOT - - + + 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 - - + + @@ -375,8 +375,8 @@ PTR_NULL->PTR_PERSON_NIL - - + + @@ -387,8 +387,8 @@ PTR_NULL->PTR_S1_NIL - - + + @@ -399,8 +399,8 @@ PTR_NULL->PTR_MORE_NIL - - + + @@ -419,41 +419,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 - - + + @@ -485,8 +485,8 @@ STRUCT_TOP->STRUCT_PERSON - - + + @@ -498,8 +498,8 @@ STRUCT_TOP->STRUCT_S1 - - + + @@ -511,8 +511,8 @@ STRUCT_TOP->STRUCT_S2 - - + + @@ -523,8 +523,8 @@ STRUCT_TOP->STRUCT_MORE - - + + @@ -576,8 +576,8 @@ MEM_TOP->MEM_ALIAS2 - - + + @@ -588,8 +588,8 @@ MEM_TOP->MEM_ALIAS3 - - + + @@ -600,8 +600,8 @@ MEM_TOP->MEM_MORE - - + + @@ -639,70 +639,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 - - + + diff --git a/chapter14/docs/lattice.gv b/chapter14/docs/lattice.gv index ac2f1f2e..5fd97a52 100644 --- a/chapter14/docs/lattice.gv +++ b/chapter14/docs/lattice.gv @@ -142,9 +142,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/chapter14/docs/lattice.svg b/chapter14/docs/lattice.svg index 131b5601..9db77f7a 100644 --- a/chapter14/docs/lattice.svg +++ b/chapter14/docs/lattice.svg @@ -4,142 +4,142 @@ - - + + Lattice - + cluster_control - -Control + +Control cluster_integer - -Integer ranges (schematic) + +Integer ranges (schematic) cluster_float - -Float + +Float 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 -precise alias slices + +Memory +precise alias slices cluster_tuple - -Tuple -collection of types + +Tuple +collection of types TOP - -⊤ + +⊤ XCTRL - -⊤:ctrl + +⊤:ctrl TOP->XCTRL - - + + INT_TOP - -⊤ -:int + +⊤ +:int TOP->INT_TOP - - + + FLT_TOP - -⊤ -:flt + +⊤ +:flt TOP->FLT_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 - - + + @@ -156,7 +156,7 @@ XCTRL->CTRL - + @@ -169,14 +169,14 @@ INT_HI - -max < min + +max < min INT_TOP->INT_HI - - + + @@ -195,50 +195,50 @@ INT_XBOOL - -1...0 + +1...0 INT_HI->INT_XBOOL - - + + INT_CON - -constants + +constants INT_HI->INT_CON - - + + INT_CON0 - -0 + +0 INT_XBOOL->INT_CON0 - - + + INT_CON1 - -1 + +1 INT_XBOOL->INT_CON1 - - + + @@ -249,8 +249,8 @@ INT_CON->INT_LO - - + + @@ -262,15 +262,15 @@ INT_CON0->INT_BOOL - - + + INT_CON1->INT_BOOL - - + + @@ -287,40 +287,40 @@ FLT_CON64 - -64b consts -[excludes -32b consts] + +64b consts +[excludes +32b consts] FLT_TOP->FLT_CON64 - - + + FLT_CONPI - -3.14159... + +3.14159... FLT_TOP->FLT_CONPI - - + + FLT_X32 - -~f32 + +~f32 FLT_TOP->FLT_X32 - - + + @@ -339,113 +339,113 @@ FLT_CON64->FLT_BOT - - + + FLT_CON32 - -32b consts + +32b consts FLT_32 - -f32 + +f32 FLT_CON32->FLT_32 - - + + FLT_CONPI->FLT_BOT - - + + FLT_X32->FLT_CON32 - - + + FLT_CON0 - -0. + +0. FLT_X32->FLT_CON0 - - + + FLT_CON0->FLT_32 - - + + FLT_32->FLT_BOT - - + + 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 - - + + @@ -464,111 +464,111 @@ PTR_PERSON_NIL - -*Person? + +*Person? PTR_NULL->PTR_PERSON_NIL - - + + PTR_S1_NIL - -*s1? + +*s1? PTR_NULL->PTR_S1_NIL - - + + PTR_MORE_NIL - -*s2?, … + +*s2?, … PTR_NULL->PTR_MORE_NIL - - + + PTR_ANY - -*⊥:struct -[ptr any struct] + +*⊥: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 - - + + @@ -580,8 +580,8 @@ STRUCT_TOP->STRUCT_PERSON - - + + @@ -593,8 +593,8 @@ STRUCT_TOP->STRUCT_S1 - - + + @@ -606,8 +606,8 @@ STRUCT_TOP->STRUCT_S2 - - + + @@ -618,8 +618,8 @@ STRUCT_TOP->STRUCT_MORE - - + + @@ -671,8 +671,8 @@ MEM_TOP->MEM_ALIAS2 - - + + @@ -683,8 +683,8 @@ MEM_TOP->MEM_ALIAS3 - - + + @@ -695,8 +695,8 @@ MEM_TOP->MEM_MORE - - + + @@ -734,70 +734,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 - - + + diff --git a/graph/README.md b/graph/README.md index f0e32d9d..f7037548 100644 --- a/graph/README.md +++ b/graph/README.md @@ -156,11 +156,21 @@ This keeps both graphs side by side in the chapter README. Chapter 10a's [load-after-store example](../chapter10a/README.md#local-memory-optimizations) uses this format to isolate a single rewrite. -The compact memory-dependency schematics in 10b retain `.gv` sources to -preserve their deliberate horizontal layouts. They use the viewer palette and -node shapes; definitions are left of uses horizontally and above uses vertically, -with arrows from use to definition. Type lattices use their own domain colors -and top-to-bottom lattice order, rather than IR edge conventions. +The memory diagrams in 10a, 10b, and 11 also use viewer snapshots, with definitions +above uses (apart from loop backedges) and arrows from use to definition. +They omit control-flow context, including Regions and their Phi bindings, +while retaining data and memory dependencies. Small, detached True/False +projections show branch gates for Loads and Stores. Chapter 10 shows schematic +source gates; Chapter 11 shows actual bindings at each scheduling stage, with +entry-block and Loop bindings omitted. Its infinite-loop figures retain the +CFG because that is their subject. Empty control slots in focused snapshots +can denote omitted context rather than null inputs in the compiler. +Type lattices retain DOT sources, their own +domain colors, and top-to-bottom lattice order, rather than IR edge conventions. + +Routed edges keep their horizontal and vertical segments, with rounded corners +in both the live viewer and SVG exports. The bend radius shrinks on short +segments so adjacent corners do not overlap. The launcher prints the viewer URL before opening the browser. If the desktop only raises an existing browser window, paste that URL into a new tab. Use diff --git a/graph/web/layout.js b/graph/web/layout.js index 880e7662..04d6f338 100644 --- a/graph/web/layout.js +++ b/graph/web/layout.js @@ -24,7 +24,9 @@ class GraphLayout { const hidden = (n, e) => ["START", "UNIT"].includes(n.kind) && raw.get(e.def)?.kind === "STOP"; const nodes = snap.nodes.map(n => { const label = `${this.clip(n.label)} #${n.id}${n.proj ? "/" + n.proj.idx : ""}`, type = this.clip(n.type); - const compact = ["START", "UNIT", "STOP"].includes(n.kind); + // Detached control projections need only a small, single-line anchor. + const compact = ["START", "UNIT", "STOP"].includes(n.kind) || + (n.kind === "CTRL" && n.proj && !raw.has(n.proj.par) && !n.type); let w = Math.ceil(Math.max(120, this.ctx.measureText(label).width + 24 + (n.folding ? 60 : 0), this.ctx.measureText(type).width + 24, (n.edges.length + 1) * 18)); const scope = n.kind === "SCOPE"; @@ -335,9 +337,9 @@ class GraphLayout { e.path = `M${x},${y} C${x},${y + 24} ${u},${v - 24} ${u},${v}`; } else { const route = routes.get(e.id), origin = boxes.get(route.e.container) || route.box; - e.path = route.e.sections.map(s => + e.path = route.e.sections.map(s => this.roundedPath( [s.startPoint, ...(s.bendPoints || []), s.endPoint] - .map((p, i) => `${i ? "L" : "M"}${p.x + origin.x},${p.y + origin.y}`).join(" ")).join(" "); + .map(p => ({x: p.x + origin.x, y: p.y + origin.y})))).join(" "); } if (e.wrap) { const box = boxes.get("g" + e.wrap), i = lanes.get(e.wrap) || 0; @@ -352,7 +354,7 @@ class GraphLayout { const right = box.x + box.width - 12 - i * 10; const head = this.toRight(from, right, obstacles), tail = this.toRight(to, right, obstacles); const pts = [start, ...head, ...tail.reverse(), end]; - e.path = pts.map((p, i) => `${i ? "L" : "M"}${p.x},${p.y}`).join(" "); + e.path = this.roundedPath(pts); e.lane = right; } } @@ -361,7 +363,9 @@ class GraphLayout { j.x += box.x; j.y += box.y; const p = use.ports.find(p => p.id === use.id + "i" + j.slot); const x = use.x + p.x + 3, y = use.y + p.y + 3; - j.path = `M${j.x},${j.y + j.height / 2}H${j.x - 12}V${box.y - 18}H${x}V${y}`; + j.path = this.roundedPath([{x: j.x, y: j.y + j.height / 2}, + {x: j.x - 12, y: j.y + j.height / 2}, {x: j.x - 12, y: box.y - 18}, + {x, y: box.y - 18}, {x, y}]); } return {width: graph.width, height: graph.height, nodes, edges, jumps, raw: view.raw, cover: view.cover, groups: view.open.map(g => ({...g, ...boxes.get("g" + g.id), gid: g.id, n: view.raw.get(g.id)})), @@ -369,6 +373,26 @@ class GraphLayout { held: new Set(held.map(n => n.n.id))}; } + // Keep the orthogonal route, easing each bend without moving its endpoints. + // Half-segment limits prevent neighboring corners from overlapping on short + // routes. The radius fits inside the routing gutters' eight-pixel clearance. + roundedPath(points, radius = 8) { + const ps = points.filter((p, i) => !i || p.x !== points[i-1].x || p.y !== points[i-1].y); + if (!ps.length) return ""; + let path = `M${ps[0].x},${ps[0].y}`; + for (let i = 1; i < ps.length - 1; i++) { + const a = ps[i-1], b = ps[i], c = ps[i+1]; + const ux = b.x-a.x, uy = b.y-a.y, vx = c.x-b.x, vy = c.y-b.y; + if (ux*vy === uy*vx) { path += ` L${b.x},${b.y}`; continue; } + const before = Math.hypot(ux,uy), after = Math.hypot(vx,vy); + const r = Math.min(radius, before/2, after/2); + path += ` L${b.x-ux*r/before},${b.y-uy*r/before}` + + ` Q${b.x},${b.y} ${b.x+vx*r/after},${b.y+vy*r/after}`; + } + if (ps.length > 1) path += ` L${ps.at(-1).x},${ps.at(-1).y}`; + return path; + } + // An orthogonal lead to a right-side gutter. Search only the channels // between boxes; this is routing geometry, not a second node layout. toRight(start, right, boxes) { -- cgit v1.2.3