From e1bba17ff54400a34ede0eaacad863420d021119 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 29 Sep 2026 09:44:41 -0700 Subject: Split ch10 Basic memory introduction in 10a, then precise aliases in 10b. --- chapter10b/docs/10-grammar.md | 125 ++++++++++ chapter10b/docs/Makefile | 14 ++ chapter10b/docs/example1.gv | 11 + chapter10b/docs/example1.svg | 91 ++++++++ chapter10b/docs/example2a.gv | 10 + chapter10b/docs/example2a.svg | 82 +++++++ chapter10b/docs/example2b.gv | 10 + chapter10b/docs/example2b.svg | 101 +++++++++ chapter10b/docs/example2c.gv | 10 + chapter10b/docs/example2c.svg | 56 +++++ chapter10b/docs/lattice.gv | 161 +++++++++++++ chapter10b/docs/lattice.svg | 516 ++++++++++++++++++++++++++++++++++++++++++ 12 files changed, 1187 insertions(+) create mode 100644 chapter10b/docs/10-grammar.md create mode 100644 chapter10b/docs/Makefile create mode 100644 chapter10b/docs/example1.gv create mode 100644 chapter10b/docs/example1.svg create mode 100644 chapter10b/docs/example2a.gv create mode 100644 chapter10b/docs/example2a.svg create mode 100644 chapter10b/docs/example2b.gv create mode 100644 chapter10b/docs/example2b.svg create mode 100644 chapter10b/docs/example2c.gv create mode 100644 chapter10b/docs/example2c.svg create mode 100644 chapter10b/docs/lattice.gv create mode 100644 chapter10b/docs/lattice.svg (limited to 'chapter10b/docs') diff --git a/chapter10b/docs/10-grammar.md b/chapter10b/docs/10-grammar.md new file mode 100644 index 00000000..9a80d6ea --- /dev/null +++ b/chapter10b/docs/10-grammar.md @@ -0,0 +1,125 @@ +# Grammar for Chapter 10b + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | structDeclaration + | declStatement + | blockStatment + | expressionStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatment + ; + +field + : 'int' IDENTIFIER ';' + ; + +fields + : field+ + ; + +structDeclaration + : 'struct' IDENTIFIER '{' fields '}' + ; + +whileStatement + : 'while' '(' expression ')' statement + ; + +breakStatement + : 'break' ';' + ; + +continueStatement + : 'continue' ';' + ; + +ifStatement + : 'if' '(' expression ')' statement ('else' statement)? + ; + + +expressionStatement + : IDENTIFIER '=' expression ';' + | fieldExpression '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +structName + : IDENTIFIER + ; + +declStatement + : 'int' IDENTIFIER '=' expression ';' + | structName ('?')? IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : comparisonExpression + ; + +comparisonExpression + : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | '!' unaryExpression + | primaryExpression + ; + +newExpression + : 'new' IDENTIFIER + ; + +fieldExpression + : primaryExpresson '.' IDENTIFIER + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | 'true' + | 'false' + | 'null' + | newExpression + | '(' expression ')' + | fieldExpression + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +``` diff --git a/chapter10b/docs/Makefile b/chapter10b/docs/Makefile new file mode 100644 index 00000000..055882b2 --- /dev/null +++ b/chapter10b/docs/Makefile @@ -0,0 +1,14 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) +.DELETE_ON_ERROR: + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + @sed -i 's/\r$$//' $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/chapter10b/docs/example1.gv b/chapter10b/docs/example1.gv new file mode 100644 index 00000000..d1b2d456 --- /dev/null +++ b/chapter10b/docs/example1.gv @@ -0,0 +1,11 @@ +digraph Memory { + rankdir=LR; + node [shape=box]; + M [label="Initial memory"]; + X [label="Store x = 42"]; + Y [label="Loop: Store y"]; + L [label="Load x -> 42"]; + M -> X -> L [color=blue]; M -> Y [color=green]; + X -> MemMerge [color=blue]; Y -> MemMerge [color=green]; + MemMerge -> Return; L -> Return; +} diff --git a/chapter10b/docs/example1.svg b/chapter10b/docs/example1.svg new file mode 100644 index 00000000..bcd2a221 --- /dev/null +++ b/chapter10b/docs/example1.svg @@ -0,0 +1,91 @@ + + + + + + +Memory + + + +M + +Initial memory + + + +X + +Store x = 42 + + + +M->X + + + + + +Y + +Loop: Store y + + + +M->Y + + + + + +L + +Load x -> 42 + + + +X->L + + + + + +MemMerge + +MemMerge + + + +X->MemMerge + + + + + +Y->MemMerge + + + + + +Return + +Return + + + +L->Return + + + + + +MemMerge->Return + + + + + diff --git a/chapter10b/docs/example2a.gv b/chapter10b/docs/example2a.gv new file mode 100644 index 00000000..50f7ec80 --- /dev/null +++ b/chapter10b/docs/example2a.gv @@ -0,0 +1,10 @@ +digraph Memory { + rankdir=LR; + node [shape=box]; + M [label="Default memory"]; + X [label="Store x"]; + Y [label="Store y"]; + M -> X [color=blue]; M -> Y [color=green]; + M -> MemMerge [label="default"]; X -> MemMerge [label="x",color=blue]; + Y -> MemMerge [label="y",color=green]; MemMerge -> Return; +} diff --git a/chapter10b/docs/example2a.svg b/chapter10b/docs/example2a.svg new file mode 100644 index 00000000..74cb48e0 --- /dev/null +++ b/chapter10b/docs/example2a.svg @@ -0,0 +1,82 @@ + + + + + + +Memory + + + +M + +Default memory + + + +X + +Store x + + + +M->X + + + + + +Y + +Store y + + + +M->Y + + + + + +MemMerge + +MemMerge + + + +M->MemMerge + + +default + + + +X->MemMerge + + +x + + + +Y->MemMerge + + +y + + + +Return + +Return + + + +MemMerge->Return + + + + + diff --git a/chapter10b/docs/example2b.gv b/chapter10b/docs/example2b.gv new file mode 100644 index 00000000..7ef10ec8 --- /dev/null +++ b/chapter10b/docs/example2b.gv @@ -0,0 +1,10 @@ +digraph Memory { + rankdir=LR; + node [shape=box]; + P [label="MemPhi(x)"]; + B [label="BulkMemPhi(All except x)"]; + Left -> P [label="slice x",color=blue]; Right -> P [label="slice x",color=blue]; + Left -> B; Right -> B; + Region -> P [style=dashed]; Region -> B [style=dashed]; + P -> MemMerge [label="x",color=blue]; B -> MemMerge [label="default"]; +} diff --git a/chapter10b/docs/example2b.svg b/chapter10b/docs/example2b.svg new file mode 100644 index 00000000..fae583e6 --- /dev/null +++ b/chapter10b/docs/example2b.svg @@ -0,0 +1,101 @@ + + + + + + +Memory + + + +P + +MemPhi(x) + + + +MemMerge + +MemMerge + + + +P->MemMerge + + +x + + + +B + +BulkMemPhi(All except x) + + + +B->MemMerge + + +default + + + +Left + +Left + + + +Left->P + + +slice x + + + +Left->B + + + + + +Right + +Right + + + +Right->P + + +slice x + + + +Right->B + + + + + +Region + +Region + + + +Region->P + + + + + +Region->B + + + + + diff --git a/chapter10b/docs/example2c.gv b/chapter10b/docs/example2c.gv new file mode 100644 index 00000000..fb827b3e --- /dev/null +++ b/chapter10b/docs/example2c.gv @@ -0,0 +1,10 @@ +digraph Memory { + rankdir=LR; + node [shape=box]; + M [label="Prior x memory"]; + L [label="Load p.x"]; + S [label="Store p.x"]; + M -> L [color=blue]; M -> S [color=blue]; + L -> S [style=dashed,label="execute load first"]; + Y [label="Store p.y: independent"]; +} diff --git a/chapter10b/docs/example2c.svg b/chapter10b/docs/example2c.svg new file mode 100644 index 00000000..d8e5cf96 --- /dev/null +++ b/chapter10b/docs/example2c.svg @@ -0,0 +1,56 @@ + + + + + + +Memory + + + +M + +Prior x memory + + + +L + +Load p.x + + + +M->L + + + + + +S + +Store p.x + + + +M->S + + + + + +L->S + + +execute load first + + + +Y + +Store p.y: independent + + + diff --git a/chapter10b/docs/lattice.gv b/chapter10b/docs/lattice.gv new file mode 100644 index 00000000..f87acfed --- /dev/null +++ b/chapter10b/docs/lattice.gv @@ -0,0 +1,161 @@ +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;} +} diff --git a/chapter10b/docs/lattice.svg b/chapter10b/docs/lattice.svg new file mode 100644 index 00000000..4023b68c --- /dev/null +++ b/chapter10b/docs/lattice.svg @@ -0,0 +1,516 @@ + + + + + + +Lattice + + + +TOP + +⊤ + + + +XCTRL + +⊤ +:ctrl + + + +TOP->XCTRL + + + + + +INT_TOP + +⊤ +:int + + + +TOP->INT_TOP + + + + + +PTR + + + +*ptr + + +struct + + + +TOP->PTR + + + + + +STRUCT_TOP + +⊤ +:struct + + + +TOP->STRUCT_TOP + + + + + +MEM_TOP + +⊤ +:mem + + + +TOP->MEM_TOP + + + + + +TUPLE_TOP + +⊤ +:tuple + + + +TOP->TUPLE_TOP + + + + + +BOT + +⊥ + + + +CTRL + +⊥ +:ctrl + + + +XCTRL->CTRL + + + + + +CTRL->BOT + + + + + +INT_MINDOTS + +... + + + +INT_TOP->INT_MINDOTS + + + + + +INT_ZERO + +0 + + + +INT_TOP->INT_ZERO + + + + + +INT_MAXDOTS + +... + + + +INT_TOP->INT_MAXDOTS + + + + + +INT_BOT + +⊥ +:int + + + +INT_BOT->BOT + + + + + +INT_MINDOTS->INT_BOT + + + + + + +INT_ZERO->INT_BOT + + + + + + +INT_MAXDOTS->INT_BOT + + + + + +PTR0 + + + +*ptr? + + +struct + + + +PTR->PTR0 + + + + + +PTR0->BOT + + + + + +STRUCT_S1 + + + +field + + + + + + + + +int/ptr + + + +STRUCT_TOP->STRUCT_S1 + + + + + +STRUCT_S2 + + + +field + + + + + + + + +int/ptr + + +field + + + + + + + + +int/ptr + + + +STRUCT_TOP->STRUCT_S2 + + + + + +STRUCT_SN + + + +field + + + + + + + + +int/ptr + + +...   + + + + + + + + +int/ptr + + +field + + + + + + + + +int/ptr + + + +STRUCT_TOP->STRUCT_SN + + + + + +STRUCT_BOT + +⊥ +:struct + + + +STRUCT_BOT->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 + + + + + +MEM_BOT + +⊥ +:mem + + + +MEM_BOT->BOT + + + + + +MEM_ALIAS1->MEM_BOT + + + + + + +MEM_ALIASDOTS->MEM_BOT + + + + + + +MEM_ALIASN->MEM_BOT + + + + + +TUPLE1 + + + +Tuple + + +type + + + +TUPLE_TOP->TUPLE1 + + + + + +TUPLE2 + + + +Tuple + + +type + + +type + + + +TUPLE_TOP->TUPLE2 + + + + + +TUPLEN + + + +Tuple + + +type + + +... + + +type + + + +TUPLE_TOP->TUPLEN + + + + + +TUPLE_BOT + +⊥ +:tuple + + + +TUPLE_BOT->BOT + + + + + +TUPLE1->TUPLE_BOT + + + + + +TUPLE2->TUPLE_BOT + + + + + +TUPLEN->TUPLE_BOT + + + + + -- cgit v1.2.3