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. --- chapter10a/docs/10-grammar.md | 125 +++++++++++ chapter10a/docs/Makefile | 14 ++ chapter10a/docs/example1.gv | 10 + chapter10a/docs/example1.svg | 73 +++++++ chapter10a/docs/example2a.gv | 10 + chapter10a/docs/example2a.svg | 85 ++++++++ chapter10a/docs/example2b.gv | 8 + chapter10a/docs/example2b.svg | 73 +++++++ chapter10a/docs/example2c.gv | 9 + chapter10a/docs/example2c.svg | 50 +++++ chapter10a/docs/lattice.gv | 151 ++++++++++++++ chapter10a/docs/lattice.svg | 466 ++++++++++++++++++++++++++++++++++++++++++ 12 files changed, 1074 insertions(+) create mode 100644 chapter10a/docs/10-grammar.md create mode 100644 chapter10a/docs/Makefile create mode 100644 chapter10a/docs/example1.gv create mode 100644 chapter10a/docs/example1.svg create mode 100644 chapter10a/docs/example2a.gv create mode 100644 chapter10a/docs/example2a.svg create mode 100644 chapter10a/docs/example2b.gv create mode 100644 chapter10a/docs/example2b.svg create mode 100644 chapter10a/docs/example2c.gv create mode 100644 chapter10a/docs/example2c.svg create mode 100644 chapter10a/docs/lattice.gv create mode 100644 chapter10a/docs/lattice.svg (limited to 'chapter10a/docs') diff --git a/chapter10a/docs/10-grammar.md b/chapter10a/docs/10-grammar.md new file mode 100644 index 00000000..5b9b680e --- /dev/null +++ b/chapter10a/docs/10-grammar.md @@ -0,0 +1,125 @@ +# Grammar for Chapter 10a + +```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/chapter10a/docs/Makefile b/chapter10a/docs/Makefile new file mode 100644 index 00000000..055882b2 --- /dev/null +++ b/chapter10a/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/chapter10a/docs/example1.gv b/chapter10a/docs/example1.gv new file mode 100644 index 00000000..38214174 --- /dev/null +++ b/chapter10a/docs/example1.gv @@ -0,0 +1,10 @@ +digraph Memory { + rankdir=LR; + node [shape=box]; + M0 [label="Initial memory"]; + X [label="Store p.x = 3"]; + Y [label="Store p.y = arg"]; + L [label="Load p.x"]; + M0 -> X -> Y -> L [color=blue]; + Y -> Return [color=blue]; L -> Return; +} diff --git a/chapter10a/docs/example1.svg b/chapter10a/docs/example1.svg new file mode 100644 index 00000000..7ae4b560 --- /dev/null +++ b/chapter10a/docs/example1.svg @@ -0,0 +1,73 @@ + + + + + + +Memory + + + +M0 + +Initial memory + + + +X + +Store p.x = 3 + + + +M0->X + + + + + +Y + +Store p.y = arg + + + +X->Y + + + + + +L + +Load p.x + + + +Y->L + + + + + +Return + +Return + + + +Y->Return + + + + + +L->Return + + + + + diff --git a/chapter10a/docs/example2a.gv b/chapter10a/docs/example2a.gv new file mode 100644 index 00000000..13fd75e0 --- /dev/null +++ b/chapter10a/docs/example2a.gv @@ -0,0 +1,10 @@ +digraph Memory { + rankdir=LR; + node [shape=box]; + M [label="Incoming memory"]; + A [label="True: Store x"]; + B [label="False: Store y"]; + P [label="Phi(memory)"]; + M -> A -> P [color=blue]; M -> B -> P [color=blue]; + Region -> P [style=dashed]; P -> Return [color=blue]; +} diff --git a/chapter10a/docs/example2a.svg b/chapter10a/docs/example2a.svg new file mode 100644 index 00000000..1752659e --- /dev/null +++ b/chapter10a/docs/example2a.svg @@ -0,0 +1,85 @@ + + + + + + +Memory + + + +M + +Incoming memory + + + +A + +True: Store x + + + +M->A + + + + + +B + +False: Store y + + + +M->B + + + + + +P + +Phi(memory) + + + +A->P + + + + + +B->P + + + + + +Return + +Return + + + +P->Return + + + + + +Region + +Region + + + +Region->P + + + + + diff --git a/chapter10a/docs/example2b.gv b/chapter10a/docs/example2b.gv new file mode 100644 index 00000000..9db0f5fb --- /dev/null +++ b/chapter10a/docs/example2b.gv @@ -0,0 +1,8 @@ +digraph Memory { + rankdir=LR; + node [shape=box]; + P [label="Phi(memory)"]; + S [label="Loop-body Store"]; + Entry -> P [color=blue]; P -> S -> P [color=blue]; + Loop -> P [style=dashed]; P -> Return [color=blue]; +} diff --git a/chapter10a/docs/example2b.svg b/chapter10a/docs/example2b.svg new file mode 100644 index 00000000..1f106d63 --- /dev/null +++ b/chapter10a/docs/example2b.svg @@ -0,0 +1,73 @@ + + + + + + +Memory + + + +P + +Phi(memory) + + + +S + +Loop-body Store + + + +P->S + + + + + +Return + +Return + + + +P->Return + + + + + +S->P + + + + + +Entry + +Entry + + + +Entry->P + + + + + +Loop + +Loop + + + +Loop->P + + + + + diff --git a/chapter10a/docs/example2c.gv b/chapter10a/docs/example2c.gv new file mode 100644 index 00000000..0a9f0462 --- /dev/null +++ b/chapter10a/docs/example2c.gv @@ -0,0 +1,9 @@ +digraph Memory { + rankdir=LR; + node [shape=box]; + M [label="Prior 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"]; +} diff --git a/chapter10a/docs/example2c.svg b/chapter10a/docs/example2c.svg new file mode 100644 index 00000000..90f90920 --- /dev/null +++ b/chapter10a/docs/example2c.svg @@ -0,0 +1,50 @@ + + + + + + +Memory + + + +M + +Prior memory + + + +L + +Load p.x + + + +M->L + + + + + +S + +Store p.x + + + +M->S + + + + + +L->S + + +execute load first + + + diff --git a/chapter10a/docs/lattice.gv b/chapter10a/docs/lattice.gv new file mode 100644 index 00000000..b2d8255e --- /dev/null +++ b/chapter10a/docs/lattice.gv @@ -0,0 +1,151 @@ +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]; + + TOP -> MEM_TOP; + MEM_TOP -> MEM_BOT; + MEM_BOT -> BOT; + + + // ---------------------- + // 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;} + {rank=same; INT_BOT; CTRL; STRUCT_BOT; MEM_BOT; TUPLE_BOT} + {rank=same; BOT;} +} diff --git a/chapter10a/docs/lattice.svg b/chapter10a/docs/lattice.svg new file mode 100644 index 00000000..aa296366 --- /dev/null +++ b/chapter10a/docs/lattice.svg @@ -0,0 +1,466 @@ + + + + + + +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_BOT + +⊥ +:mem + + + +MEM_TOP->MEM_BOT + + + + + +MEM_BOT->BOT + + + + + +TUPLE1 + + + +Tuple + + +type + + + +TUPLE_TOP->TUPLE1 + + + + + +TUPLE2 + + + +Tuple + + +type + + +type + + + +TUPLE_TOP->TUPLE2 + + + + + +TUPLEN + + + +Tuple + + +type + + +... + + +type + + + +TUPLE_TOP->TUPLEN + + + + + +TUPLE_BOT + +⊥ +:tuple + + + +TUPLE_BOT->BOT + + + + + +TUPLE1->TUPLE_BOT + + + + + +TUPLE2->TUPLE_BOT + + + + + +TUPLEN->TUPLE_BOT + + + + + -- cgit v1.2.3