From 29def92f2ddbfca64ba827f116172fe98b2df491 Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Tue, 26 Sep 2023 17:43:36 +0100 Subject: Chapter 2 (#4) * Start on Chapter 2. * Start on Chapter 2. * Refactor * Refactor * Initial attempt at peephole opt for add operation * cleanup unused import * Start on graph visualizer * Start on graph visualizer * Rework chapter 2 Add a short discourse on the Types, and provide a Bottom type. Make a final toString; require each Node to specify its special printing via label(). Add a recursing printer called print(); toString is used by default in the debugger and so cannot be recursive. Make the peephole rules based on a proper Type and idealize calls. Big comments about the Type computations. Every node picks up a _print, compute and idealize() call. Rename long arith ops Divide, UnaryMinus, Multiply, Subtract into shorter uniform-length names. Cleans up the parser where he does the precedence op parsing. Rework Parser: - Drop Token class, its all Strings except in the one place we know a number is coming - Embed the Lexer as a field in the Parser, instead of trying to pass it around everywhere in the Parser - StartNode becomes a read-only global, so we don't have to pass it around everywhere in the Parser AND optimizer. - Lexer matches on strings and returns strings. Match and consume *at the moment* instead of carrying around a current token/string and forcing the next-token after consuming the current one. - All parse subexpressions shrink by 1/2 after these changes. * Initial writeup of Chapter 2 * Initial writeup of Chapter 2 * Initial writeup of Chapter 2 * Initial writeup of Chapter 2 * Remove range * progress Chapter 2 Drop integer ranges. Broader lattice pic. Lots of prose changes in the readme. Fixed title in gviz dot generation. Fixed bug with peephole making redundant constants. * Implement compute for all the arithmetic node types Add a flag to switch off peephole so we can see the full graph Add post peephole graph to writeup * Implement compute for all the arithmetic node types Add a flag to switch off peephole so we can see the full graph Add post peephole graph to writeup * Fix bad path to the svg * Update pre-peephole diagram * Add dead code elimination ...and a set_def to proper update graph edges. * Update README.md * Cleanup the GraphVisualizer a bit. Update the graphs. Update the chapter list as chapter 3 deleted, and chapter 4 is now chapter 3. --------- Co-authored-by: Cliff Click --- chapter02/docs/02-grammar.md | 39 ++++++++ chapter02/docs/02-lattice.gv | 35 +++++++ chapter02/docs/02-lattice.svg | 143 +++++++++++++++++++++++++++++ chapter02/docs/02-post-peephole-ex1.gv | 10 ++ chapter02/docs/02-post-peephole-ex1.svg | 51 +++++++++++ chapter02/docs/02-pre-peephole-ex1.gv | 27 ++++++ chapter02/docs/02-pre-peephole-ex1.svg | 156 ++++++++++++++++++++++++++++++++ 7 files changed, 461 insertions(+) create mode 100644 chapter02/docs/02-grammar.md create mode 100644 chapter02/docs/02-lattice.gv create mode 100644 chapter02/docs/02-lattice.svg create mode 100644 chapter02/docs/02-post-peephole-ex1.gv create mode 100644 chapter02/docs/02-post-peephole-ex1.svg create mode 100644 chapter02/docs/02-pre-peephole-ex1.gv create mode 100644 chapter02/docs/02-pre-peephole-ex1.svg (limited to 'chapter02/docs') diff --git a/chapter02/docs/02-grammar.md b/chapter02/docs/02-grammar.md new file mode 100644 index 00000000..a4a79cea --- /dev/null +++ b/chapter02/docs/02-grammar.md @@ -0,0 +1,39 @@ +# Grammar for Chapter 1 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement EOF + ; + +statement + : 'return' expression ';' + ; + +expression + : additiveExpression + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | primaryExpression + ; + +primaryExpression + : INTEGER_LITERAL + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; +``` \ No newline at end of file diff --git a/chapter02/docs/02-lattice.gv b/chapter02/docs/02-lattice.gv new file mode 100644 index 00000000..57f14d77 --- /dev/null +++ b/chapter02/docs/02-lattice.gv @@ -0,0 +1,35 @@ +digraph Lattice { + // Define nodes + node [shape=circle, style=filled, fillcolor=lightblue]; + Top [label="⊤"]; + Bottom [label="⊥"]; + + A [label="MIN_INT"]; + B [label="..." shape=none style=none]; + C [label="-1"]; + D [label="0"]; + E [label="1"]; + F [label="..." shape=none style=none]; + G [label="MAX_INT"]; + + + // Define edges + Top -> A [arrowhead=none]; + Top -> B [arrowhead=none]; + Top -> C [arrowhead=none]; + Top -> D [arrowhead=none]; + Top -> E [arrowhead=none]; + Top -> F [arrowhead=none]; + Top -> G [arrowhead=none]; + A -> Bottom [arrowhead=none]; + B -> Bottom [arrowhead=none]; + C -> Bottom [arrowhead=none]; + D -> Bottom [arrowhead=none]; + E -> Bottom [arrowhead=none]; + F -> Bottom [arrowhead=none]; + G -> Bottom [arrowhead=none]; + + // Additional customization + {rank=same; A; B; C; D; E; F; G; } + {rank=same; Bottom;} +} diff --git a/chapter02/docs/02-lattice.svg b/chapter02/docs/02-lattice.svg new file mode 100644 index 00000000..218acc6a --- /dev/null +++ b/chapter02/docs/02-lattice.svg @@ -0,0 +1,143 @@ + + + + + + + Lattice + + + + Top + + ⊤ + + + + A + + MIN_INT + + + + Top->A + + + + + B + ... + + + + Top->B + + + + + C + + -1 + + + + Top->C + + + + + D + + 0 + + + + Top->D + + + + + E + + 1 + + + + Top->E + + + + + F + ... + + + + Top->F + + + + + G + + MAX_INT + + + + Top->G + + + + + Bottom + + ⊥ + + + + A->Bottom + + + + + B->Bottom + + + + + C->Bottom + + + + + D->Bottom + + + + + E->Bottom + + + + + F->Bottom + + + + + G->Bottom + + + + diff --git a/chapter02/docs/02-post-peephole-ex1.gv b/chapter02/docs/02-post-peephole-ex1.gv new file mode 100644 index 00000000..a39d602b --- /dev/null +++ b/chapter02/docs/02-post-peephole-ex1.gv @@ -0,0 +1,10 @@ +digraph chapter02 +{ + Start1 [shape=box, label="Start"]; + Con213 [ label="Con2"]; + Start1 -> Con213 [style=dotted]; + Return14 [shape=box, label="Return"]; + Con213 -> Return14; + edge [color=red]; + Start1 -> Return14; +} \ No newline at end of file diff --git a/chapter02/docs/02-post-peephole-ex1.svg b/chapter02/docs/02-post-peephole-ex1.svg new file mode 100644 index 00000000..33aa5a95 --- /dev/null +++ b/chapter02/docs/02-post-peephole-ex1.svg @@ -0,0 +1,51 @@ + + + + + + + chapter02 + + + + Start1 + + Start + + + + Con213 + + Con2 + + + + Start1->Con213 + + + + + + Return14 + + Return + + + + Start1->Return14 + + + + + + Con213->Return14 + + + + + diff --git a/chapter02/docs/02-pre-peephole-ex1.gv b/chapter02/docs/02-pre-peephole-ex1.gv new file mode 100644 index 00000000..d5a16616 --- /dev/null +++ b/chapter02/docs/02-pre-peephole-ex1.gv @@ -0,0 +1,27 @@ +digraph chapter02 +{ + Start1 [shape=box, label="Start"]; + Con12 [ label="Con1"]; + Start1 -> Con12 [style=dotted]; + Con23 [ label="Con2"]; + Start1 -> Con23 [style=dotted]; + Con34 [ label="Con3"]; + Start1 -> Con34 [style=dotted]; + Mul5 [ label="Mul"]; + Con23 -> Mul5; + Con34 -> Mul5; + Con56 [ label="Con5"]; + Start1 -> Con56 [style=dotted]; + Minus7 [ label="Minus"]; + Con56 -> Minus7; + Add8 [ label="Add"]; + Mul5 -> Add8; + Minus7 -> Add8; + Add9 [ label="Add"]; + Con12 -> Add9; + Add8 -> Add9; + Return10 [shape=box, label="Return"]; + Add9 -> Return10; + edge [color=red]; + Start1 -> Return10; +} \ No newline at end of file diff --git a/chapter02/docs/02-pre-peephole-ex1.svg b/chapter02/docs/02-pre-peephole-ex1.svg new file mode 100644 index 00000000..dc33c7f5 --- /dev/null +++ b/chapter02/docs/02-pre-peephole-ex1.svg @@ -0,0 +1,156 @@ + + + + + + + chapter02 + + + + Start1 + + Start + + + + Con12 + + Con1 + + + + Start1->Con12 + + + + + + Con23 + + Con2 + + + + Start1->Con23 + + + + + + Con34 + + Con3 + + + + Start1->Con34 + + + + + + Con56 + + Con5 + + + + Start1->Con56 + + + + + + Return10 + + Return + + + + Start1->Return10 + + + + + + Add9 + + Add + + + + Con12->Add9 + + + + + + Mul5 + + Mul + + + + Con23->Mul5 + + + + + + Con34->Mul5 + + + + + + Add8 + + Add + + + + Mul5->Add8 + + + + + + Minus7 + + Minus + + + + Con56->Minus7 + + + + + + Minus7->Add8 + + + + + + Add8->Add9 + + + + + + Add9->Return10 + + + + + -- cgit v1.2.3