From 3ba6686fc991998a0a420709dfb0012bbddf77ab Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 29 Sep 2026 12:21:46 -0700 Subject: Backport lazy memory splits to ch10, split into ch10a and b --- chapter10b/docs/example1.gv | 6 +- chapter10b/docs/example1.svg | 62 ++-- chapter10b/docs/example2a.gv | 2 +- chapter10b/docs/example2a.svg | 50 +-- chapter10b/docs/example2b.gv | 2 +- chapter10b/docs/example2b.svg | 64 ++-- chapter10b/docs/example2c.gv | 2 +- chapter10b/docs/example2c.svg | 30 +- chapter10b/docs/lattice.gv | 271 ++++++-------- chapter10b/docs/lattice.svg | 830 ++++++++++++++++++++++++------------------ 10 files changed, 690 insertions(+), 629 deletions(-) (limited to 'chapter10b/docs') diff --git a/chapter10b/docs/example1.gv b/chapter10b/docs/example1.gv index 2194ae8f..0b0a5feb 100644 --- a/chapter10b/docs/example1.gv +++ b/chapter10b/docs/example1.gv @@ -1,11 +1,13 @@ digraph Memory { - rankdir=LR; + rankdir=BT; node [shape=box]; M [label="Initial memory"]; X [label="Store x = 42"]; Y [label="Loop: Store y"]; - L [label="Load x -> 42"]; + L [label="Load x (42)"]; L -> X -> M [color=blue]; Y -> M [color=green]; MemMerge -> X [color=blue]; MemMerge -> Y [color=green]; Return -> MemMerge; Return -> L; + { rank=same; MemMerge -> L [style=invis]; } + Y -> X [style=invis]; // Layout only: keep the stores in code order. } diff --git a/chapter10b/docs/example1.svg b/chapter10b/docs/example1.svg index c441bc7b..384b6e12 100644 --- a/chapter10b/docs/example1.svg +++ b/chapter10b/docs/example1.svg @@ -4,88 +4,90 @@ - - + + Memory - + M - -Initial memory + +Initial memory X - -Store x = 42 + +Store x = 42 X->M - - + + Y - -Loop: Store y + +Loop: Store y Y->M - - + + + L - -Load x -> 42 + +Load x (42) L->X - - + + MemMerge - -MemMerge + +MemMerge MemMerge->X - - + + MemMerge->Y - - + + + Return - -Return + +Return Return->L - - + + Return->MemMerge - - + + diff --git a/chapter10b/docs/example2a.gv b/chapter10b/docs/example2a.gv index c2db6771..d92eea41 100644 --- a/chapter10b/docs/example2a.gv +++ b/chapter10b/docs/example2a.gv @@ -1,5 +1,5 @@ digraph Memory { - rankdir=LR; + rankdir=RL; node [shape=box]; M [label="Default memory"]; X [label="Store x"]; diff --git a/chapter10b/docs/example2a.svg b/chapter10b/docs/example2a.svg index fc95e08c..97fb144e 100644 --- a/chapter10b/docs/example2a.svg +++ b/chapter10b/docs/example2a.svg @@ -12,71 +12,71 @@ M - -Default memory + +Default memory X - -Store x + +Store x X->M - - + + Y - -Store y + +Store y Y->M - - + + MemMerge - -MemMerge + +MemMerge MemMerge->M - - -default + + +default MemMerge->X - - -x + + +x MemMerge->Y - - -y + + +y Return - -Return + +Return Return->MemMerge - - + + diff --git a/chapter10b/docs/example2b.gv b/chapter10b/docs/example2b.gv index 17b35910..4ddd36b5 100644 --- a/chapter10b/docs/example2b.gv +++ b/chapter10b/docs/example2b.gv @@ -1,5 +1,5 @@ digraph Memory { - rankdir=LR; + rankdir=RL; node [shape=box]; P [label="MemPhi(x)"]; B [label="BulkMemPhi(All except x)"]; diff --git a/chapter10b/docs/example2b.svg b/chapter10b/docs/example2b.svg index 67d74ea8..4e0616f1 100644 --- a/chapter10b/docs/example2b.svg +++ b/chapter10b/docs/example2b.svg @@ -12,90 +12,90 @@ P - -MemPhi(x) + +MemPhi(x) Left - -Left + +Left P->Left - - -slice x + + +slice x Right - -Right + +Right P->Right - - -slice x + + +slice x Region - -Region + +Region P->Region - - + + B - -BulkMemPhi(All except x) + +BulkMemPhi(All except x) B->Left - - + + B->Right - - + + B->Region - - + + MemMerge - -MemMerge + +MemMerge MemMerge->P - - -x + + +x MemMerge->B - - -default + + +default diff --git a/chapter10b/docs/example2c.gv b/chapter10b/docs/example2c.gv index 7a0562ee..4fae3bba 100644 --- a/chapter10b/docs/example2c.gv +++ b/chapter10b/docs/example2c.gv @@ -1,5 +1,5 @@ digraph Memory { - rankdir=LR; + rankdir=RL; node [shape=box]; M [label="Prior x memory"]; L [label="Load p.x"]; diff --git a/chapter10b/docs/example2c.svg b/chapter10b/docs/example2c.svg index 1d51ccca..8249d677 100644 --- a/chapter10b/docs/example2c.svg +++ b/chapter10b/docs/example2c.svg @@ -12,45 +12,45 @@ M - -Prior x memory + +Prior x memory L - -Load p.x + +Load p.x L->M - - + + S - -Store p.x + +Store p.x S->M - - + + S->L - - -execute load first + + +execute load first Y - -Store p.y: independent + +Store p.y: independent diff --git a/chapter10b/docs/lattice.gv b/chapter10b/docs/lattice.gv index f87acfed..f9fb2b09 100644 --- a/chapter10b/docs/lattice.gv +++ b/chapter10b/docs/lattice.gv @@ -1,161 +1,114 @@ digraph Lattice { - compound = true; - // Define nodes - splines=false; - node [shape=circle, style=filled]; - nodesep=0.6; - - TOP [label=<⊤>, fillcolor=black, fontcolor=white]; - BOT [label=<⊥>, fillcolor=black, fontcolor=white]; - - // ---------------------- - // Control - XCTRL [label=<⊤:ctrl>, fillcolor=yellow, shape=oval]; - CTRL [label=<⊥:ctrl>, fillcolor=yellow, shape=oval]; - - TOP -> XCTRL; - XCTRL -> CTRL; - CTRL -> BOT; - - // ---------------------- - // Integers - INT_TOP [label=<⊤:int>, fillcolor=lightblue, shape=oval]; - INT_BOT [label=<⊥:int>, fillcolor=lightblue, shape=oval]; - - INT_MINDOTS [label="...", fillcolor=lightblue, shape=oval]; - INT_ZERO [label="0" , fillcolor=lightblue]; - INT_MAXDOTS [label="...", fillcolor=lightblue, shape=oval]; - - TOP -> INT_TOP; - INT_TOP -> INT_MINDOTS; - INT_TOP -> INT_ZERO; - INT_TOP -> INT_MAXDOTS; - INT_MINDOTS -> INT_BOT; - INT_ZERO -> INT_BOT; - INT_MAXDOTS -> INT_BOT; - INT_BOT -> BOT; - - INT_MINDOTS -> INT_ZERO -> INT_MAXDOTS [style=invis]; - - // ---------------------- - // Pointers, just a boolean nil/not and a struct - PTR [shape=none, fillcolor=none, label=< - - - -
*ptr
struct
- >]; - PTR0 [shape=none, fillcolor=none, label=< - - - -
*ptr?
struct
- >]; - - TOP -> PTR; - PTR -> PTR0; - PTR0 -> BOT; - - // ---------------------- - // Structs - STRUCT_TOP [label=<⊤:struct>, fillcolor=lightgreen, shape=oval]; - STRUCT_BOT [label=<⊥:struct>, fillcolor=lightgreen, shape=oval]; - - STRUCT_S1 [shape=none, fillcolor=none, label=< - - -
fieldint/ptr
- >]; - STRUCT_S2 [shape=none, fillcolor=none, label=< - - - -
fieldint/ptr
fieldint/ptr
- >]; - STRUCT_SN [shape=none, fillcolor=none, label=< - - - - -
fieldint/ptr
... int/ptr
fieldint/ptr
- >]; - - - TOP -> STRUCT_TOP; - STRUCT_TOP -> STRUCT_S1; - STRUCT_TOP -> STRUCT_S2; - STRUCT_TOP -> STRUCT_SN; - STRUCT_S1 -> STRUCT_BOT; - STRUCT_S2 -> STRUCT_BOT; - STRUCT_SN -> STRUCT_BOT; - STRUCT_BOT -> BOT; - - STRUCT_S1 -> STRUCT_S2 -> STRUCT_SN [style=invis]; - - // ---------------------- - // Memory - MEM_TOP [label=<⊤:mem>, fillcolor=blue, fontcolor=white, shape=oval]; - MEM_BOT [label=<⊥:mem>, fillcolor=blue, fontcolor=white, shape=oval]; - MEM_ALIAS1 [label="#2" , fillcolor=blue, fontcolor=white]; - MEM_ALIASDOTS [label="..." , fillcolor=blue, fontcolor=white, shape=oval]; - MEM_ALIASN [label="#n" , fillcolor=blue, fontcolor=white]; - - TOP -> MEM_TOP; - MEM_TOP -> MEM_ALIAS1; - MEM_TOP -> MEM_ALIASDOTS; - MEM_TOP -> MEM_ALIASN; - MEM_ALIAS1 -> MEM_BOT; - MEM_ALIASDOTS -> MEM_BOT; - MEM_ALIASN -> MEM_BOT; - MEM_BOT -> BOT; - - MEM_ALIAS1 -> MEM_ALIASDOTS -> MEM_ALIASN [style=invis]; - - // ---------------------- - // Tuples - - TUPLE_TOP [label=<⊤:tuple>, fillcolor=pink, shape=oval]; - TUPLE_BOT [label=<⊥:tuple>, fillcolor=pink, shape=oval]; - - TUPLE1 [shape=none, fillcolor=none, label=< - - - -
Tuple
type
- >]; - TUPLE2 [shape=none, fillcolor=none, label=< - - - - -
Tuple
type
type
- >]; - TUPLEN [shape=none, fillcolor=none, label=< - - - - - -
Tuple
type
...
type
- >]; - - - TOP -> TUPLE_TOP; - TUPLE_TOP -> TUPLE1; - TUPLE_TOP -> TUPLE2; - TUPLE_TOP -> TUPLEN; - TUPLE1 -> TUPLE_BOT; - TUPLE2 -> TUPLE_BOT; - TUPLEN -> TUPLE_BOT; - TUPLE_BOT -> BOT; - - // ---------------------- - // Additional customization - {rank=same; TOP;} - {rank=same; INT_TOP; XCTRL; STRUCT_TOP; MEM_TOP; TUPLE_TOP} - {rank=same; INT_MINDOTS; INT_ZERO; INT_MAXDOTS; - STRUCT_S1; STRUCT_S2; STRUCT_SN; - MEM_ALIAS1; MEM_ALIASDOTS; MEM_ALIASN;} - {rank=same; INT_BOT; CTRL; STRUCT_BOT; MEM_BOT; TUPLE_BOT} - {rank=same; BOT;} + rankdir=TB; + newrank=true; + // Preserve the same-rank ordering edges through cluster layout. + remincross=false; + nodesep=0.22; + ranksep=0.65; + node [shape=ellipse, style=filled, fontname="DejaVu Sans", fontsize=13]; + edge [color="#555555", arrowsize=0.6]; + + // These arrows are lattice-order edges, not use/definition edges. + TOP [label="⊤", fillcolor=black, fontcolor=white]; + BOT [label="⊥", fillcolor=black, fontcolor=white]; + + subgraph cluster_control { + label="Control"; fontname="Arial"; color="#cccccc"; + node [fillcolor="#ffff00"]; + XCTRL [label="⊤:ctrl"]; + CTRL [label="⊥:ctrl"]; + XCTRL -> CTRL; + } + + subgraph cluster_integer { + label="Integer"; fontname="Arial"; color="#cccccc"; + node [fillcolor="#add8e6"]; + INT_TOP [label="⊤:int"]; + INT_BOT [label="⊥:int"]; + INT_NEG [label="… −2, −1"]; + INT_ZERO [label="0"]; + INT_POS [label="1, 2, …"]; + {rank=same; INT_NEG; INT_ZERO; INT_POS;} + INT_NEG -> INT_ZERO -> INT_POS [style=invis]; + INT_TOP -> {INT_NEG INT_ZERO INT_POS}; + {INT_NEG INT_ZERO INT_POS} -> INT_BOT; + } + + subgraph cluster_pointer { + label="Pointer = nullability × struct type"; + fontname="Arial"; color="#cccccc"; + node [fillcolor="#008000", fontcolor=white]; + PTR_TOP [label="⊤:ptr\n[*⊤:struct]"]; + PTR_BOT [label="⊥:ptr\n[*⊥:struct?]"]; + PTR_NULL [label="null"]; + PTR_ANY [label="*⊥:struct\n[ptr any struct]"]; + PTR_PERSON [label="*Person"]; + PTR_S1 [label="*s1"]; + PTR_MORE [label="*s2, …"]; + PTR_PERSON_NIL [label="*Person?"]; + PTR_S1_NIL [label="*s1?"]; + PTR_MORE_NIL [label="*s2?, …"]; + {rank=same; PTR_PERSON; PTR_S1; PTR_MORE; PTR_NULL;} + {rank=same; PTR_ANY; PTR_PERSON_NIL; PTR_S1_NIL; PTR_MORE_NIL;} + PTR_PERSON -> PTR_S1 -> PTR_MORE -> PTR_NULL [style=invis]; + PTR_ANY -> PTR_PERSON_NIL -> PTR_S1_NIL -> PTR_MORE_NIL [style=invis]; + PTR_TOP -> {PTR_PERSON PTR_S1 PTR_MORE PTR_NULL}; + {PTR_PERSON PTR_S1 PTR_MORE} -> PTR_ANY; + PTR_PERSON -> PTR_PERSON_NIL; + PTR_S1 -> PTR_S1_NIL; + PTR_MORE -> PTR_MORE_NIL; + PTR_NULL -> {PTR_PERSON_NIL PTR_S1_NIL PTR_MORE_NIL}; + {PTR_ANY PTR_PERSON_NIL PTR_S1_NIL PTR_MORE_NIL} -> PTR_BOT; + } + + subgraph cluster_struct { + label="Struct\nnamed collection of named scalar types"; + fontname="Arial"; color="#cccccc"; + node [fillcolor="#90ee90"]; + STRUCT_TOP [label="⊤:struct\n[struct top]"]; + STRUCT_BOT [label="⊥:struct\n[struct bottom]"]; + STRUCT_PERSON [label="Person\nage: int", shape=box]; + STRUCT_S1 [label="s1\nx: int", shape=box]; + STRUCT_S2 [label="s2\nx: int, y: *s1", shape=box]; + STRUCT_MORE [label="…", shape=box]; + {rank=same; STRUCT_PERSON; STRUCT_S1; STRUCT_S2; STRUCT_MORE;} + STRUCT_PERSON -> STRUCT_S1 -> STRUCT_S2 -> STRUCT_MORE [style=invis]; + STRUCT_TOP -> {STRUCT_PERSON STRUCT_S1 STRUCT_S2 STRUCT_MORE}; + {STRUCT_PERSON STRUCT_S1 STRUCT_S2 STRUCT_MORE} -> STRUCT_BOT; + } + + subgraph cluster_memory { + label="Memory\nprecise alias slices"; fontname="Arial"; color="#cccccc"; + node [fillcolor="#00008b", fontcolor=white]; + MEM_TOP [label="⊤:mem"]; + MEM_BOT [label="⊥:mem"]; + MEM_ALIAS2 [label="MEM#2"]; + MEM_ALIAS3 [label="MEM#3"]; + MEM_MORE [label="…"]; + {rank=same; MEM_ALIAS2; MEM_ALIAS3; MEM_MORE;} + MEM_ALIAS2 -> MEM_ALIAS3 -> MEM_MORE [style=invis]; + MEM_TOP -> {MEM_ALIAS2 MEM_ALIAS3 MEM_MORE}; + {MEM_ALIAS2 MEM_ALIAS3 MEM_MORE} -> MEM_BOT; + } + + subgraph cluster_tuple { + label="Tuple\ncollection of types"; + fontname="Arial"; color="#cccccc"; + node [fillcolor="#ffc0cb"]; + TUPLE_TOP [label="⊤:tuple"]; + TUPLE_BOT [label="⊥:tuple"]; + TUPLE1 [label="(type)", shape=box]; + TUPLE2 [label="(type, type)", shape=box]; + TUPLEN [label="(type, …)", shape=box]; + {rank=same; TUPLE1; TUPLE2; TUPLEN;} + TUPLE1 -> TUPLE2 -> TUPLEN [style=invis]; + TUPLE_TOP -> {TUPLE1 TUPLE2 TUPLEN}; + {TUPLE1 TUPLE2 TUPLEN} -> TUPLE_BOT; + } + + TOP -> {XCTRL INT_TOP PTR_TOP STRUCT_TOP MEM_TOP TUPLE_TOP}; + {CTRL INT_BOT PTR_BOT STRUCT_BOT MEM_BOT TUPLE_BOT} -> BOT; + {rank=same; XCTRL; INT_TOP; PTR_TOP; STRUCT_TOP; MEM_TOP; TUPLE_TOP;} + {rank=same; CTRL; INT_BOT; PTR_BOT; STRUCT_BOT; MEM_BOT; TUPLE_BOT;} + XCTRL -> INT_TOP -> PTR_TOP -> STRUCT_TOP -> MEM_TOP -> TUPLE_TOP [style=invis]; } diff --git a/chapter10b/docs/lattice.svg b/chapter10b/docs/lattice.svg index 4023b68c..a11452b9 100644 --- a/chapter10b/docs/lattice.svg +++ b/chapter10b/docs/lattice.svg @@ -4,513 +4,617 @@ - - + + Lattice - + + +cluster_control + +Control + + +cluster_integer + +Integer + + +cluster_pointer + +Pointer = nullability × struct type + + +cluster_struct + +Struct +named collection of named scalar types + + +cluster_memory + +Memory +precise alias slices + + +cluster_tuple + +Tuple +collection of types + TOP - -⊤ + +⊤ XCTRL - -⊤ -:ctrl + +⊤:ctrl - + TOP->XCTRL - - + + INT_TOP - -⊤ -:int + +⊤:int - + TOP->INT_TOP - - + + - + -PTR - - - -*ptr - - -struct - - - -TOP->PTR - - +PTR_TOP + +⊤:ptr +[*⊤:struct] + + + +TOP->PTR_TOP + + - + STRUCT_TOP - -⊤ -:struct + +⊤:struct +[struct top] - + TOP->STRUCT_TOP - - + + - + MEM_TOP - -⊤ -:mem + +⊤:mem - + TOP->MEM_TOP - - + + - + TUPLE_TOP - -⊤ -:tuple + +⊤:tuple - + TOP->TUPLE_TOP - - + + BOT - -⊥ + +⊥ CTRL - -⊥ -:ctrl + +⊥:ctrl - + XCTRL->CTRL - - + + + - + CTRL->BOT - - + + - + -INT_MINDOTS - -... +INT_NEG + +… −2, −1 - - -INT_TOP->INT_MINDOTS - - + + +INT_TOP->INT_NEG + + INT_ZERO - -0 + +0 - + INT_TOP->INT_ZERO - - + + - + -INT_MAXDOTS - -... +INT_POS + +1, 2, … - - -INT_TOP->INT_MAXDOTS - - + + +INT_TOP->INT_POS + + + INT_BOT - -⊥ -:int + +⊥:int - + INT_BOT->BOT - - + + - - -INT_MINDOTS->INT_BOT - - + + +INT_NEG->INT_BOT + + - + - + INT_ZERO->INT_BOT - - + + + + + + +INT_POS->INT_BOT + + - - - -INT_MAXDOTS->INT_BOT - - + + +PTR_NULL + +null - - -PTR0 - - - -*ptr? - - -struct - - - -PTR->PTR0 - - - - + -PTR0->BOT - - +PTR_TOP->PTR_NULL + + - + +PTR_PERSON + +*Person + + + +PTR_TOP->PTR_PERSON + + + + + +PTR_S1 + +*s1 + + + +PTR_TOP->PTR_S1 + + + + + +PTR_MORE + +*s2, … + + + +PTR_TOP->PTR_MORE + + + + + + +PTR_BOT + +⊥:ptr +[*⊥:struct?] + + + +PTR_BOT->BOT + + + + + +PTR_PERSON_NIL + +*Person? + + + +PTR_NULL->PTR_PERSON_NIL + + + + + +PTR_S1_NIL + +*s1? + + + +PTR_NULL->PTR_S1_NIL + + + + + +PTR_MORE_NIL + +*s2?, … + + + +PTR_NULL->PTR_MORE_NIL + + + + + +PTR_ANY + +*⊥:struct +[ptr any struct] + + + +PTR_ANY->PTR_BOT + + + + + + +PTR_PERSON->PTR_ANY + + + + + + +PTR_PERSON->PTR_PERSON_NIL + + + + + +PTR_S1->PTR_ANY + + + + + + +PTR_S1->PTR_S1_NIL + + + + + + +PTR_MORE->PTR_ANY + + + + + +PTR_MORE->PTR_MORE_NIL + + + + + +PTR_PERSON_NIL->PTR_BOT + + + + + + +PTR_S1_NIL->PTR_BOT + + + + + + +PTR_MORE_NIL->PTR_BOT + + + + + +STRUCT_PERSON + +Person +age: int + + + +STRUCT_TOP->STRUCT_PERSON + + + + + STRUCT_S1 - - - -field - - - - - - - - -int/ptr + +s1 +x: int - + STRUCT_TOP->STRUCT_S1 - - + + - + STRUCT_S2 - - - -field - - - - - - - - -int/ptr - - -field - - - - - - - - -int/ptr + +s2 +x: int, y: *s1 - + STRUCT_TOP->STRUCT_S2 - - + + - - -STRUCT_SN - - - -field - - - - - - - - -int/ptr - - -...   - - - - - - - - -int/ptr - - -field - - - - - - - - -int/ptr - - - -STRUCT_TOP->STRUCT_SN - - + + +STRUCT_MORE + +… + + + +STRUCT_TOP->STRUCT_MORE + + + - + STRUCT_BOT - -⊥ -:struct + +⊥:struct +[struct bottom] - + STRUCT_BOT->BOT - - + + + + + +STRUCT_PERSON->STRUCT_BOT + + + - + STRUCT_S1->STRUCT_BOT - - + + - + STRUCT_S2->STRUCT_BOT - - - - - - -STRUCT_SN->STRUCT_BOT - - - - - -MEM_ALIAS1 - -#2 - - - -MEM_TOP->MEM_ALIAS1 - - - - - -MEM_ALIASDOTS - -... - - - -MEM_TOP->MEM_ALIASDOTS - - - - - -MEM_ALIASN - -#n - - - -MEM_TOP->MEM_ALIASN - - + + + + + +STRUCT_MORE->STRUCT_BOT + + + + + +MEM_ALIAS2 + +MEM#2 + + + +MEM_TOP->MEM_ALIAS2 + + + + + +MEM_ALIAS3 + +MEM#3 + + + +MEM_TOP->MEM_ALIAS3 + + + + + +MEM_MORE + +… + + + +MEM_TOP->MEM_MORE + + + + - + MEM_BOT - -⊥ -:mem + +⊥:mem - + MEM_BOT->BOT - - - - - -MEM_ALIAS1->MEM_BOT - - - - - - -MEM_ALIASDOTS->MEM_BOT - - - - - - -MEM_ALIASN->MEM_BOT - - + + + + + +MEM_ALIAS2->MEM_BOT + + + + + + +MEM_ALIAS3->MEM_BOT + + + + + + +MEM_MORE->MEM_BOT + + - + TUPLE1 - - - -Tuple - - -type + +(type) - + TUPLE_TOP->TUPLE1 - - + + - + TUPLE2 - - - -Tuple - - -type - - -type + +(type, type) - + TUPLE_TOP->TUPLE2 - - + + - + TUPLEN - - - -Tuple - - -type - - -... - - -type + +(type, …) - + TUPLE_TOP->TUPLEN - - + + - + TUPLE_BOT - -⊥ -:tuple + +⊥:tuple - + TUPLE_BOT->BOT - - + + - + TUPLE1->TUPLE_BOT - - + + + - + TUPLE2->TUPLE_BOT - - + + + - + TUPLEN->TUPLE_BOT - - + + -- cgit v1.2.3