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 --- README.md | 37 ++++++++++++++++++++----------------- 1 file changed, 20 insertions(+), 17 deletions(-) (limited to 'README.md') diff --git a/README.md b/README.md index bec41b81..ef698c69 100644 --- a/README.md +++ b/README.md @@ -28,20 +28,23 @@ The simple language will be a small subset of C. * [Language](language/README.md): Simple language grammar. * [Chapter 1](chapter01/README.md): Script that returns an integer literal, i.e., an empty function that takes no arguments and returns a single integer value. The `return` statement. -* Chapter 2: Simple binary arithmetic such as addition, subtraction, multiplication, division with constants. Peephole optimization / simple constant folding. -* Chapter 3: Graphical Visualization of Sea of Nodes IR. -* Chapter 4: Local variables, and assignment statements. Read on RHS, SSA, more peephole optimization if local is a constant. -* Chapter 5: Binary and Comparison operators involving constants and variables. Non-zero values will be truthy. -* Chapter 6: `if` statement. CFG construction, peephole optimization around dead control flow. -* Chapter 7: `while` statement. -* Chapter 8: Global Value Numbering. -* Chapter 9: Functions and calls. -* Chapter 10: Boolean operators `&&`, `||` and `!` including short circuit. -* Chapter 11: `float` type. -* Chapter 12: Memory effects: general memory edges in SSA. Peephole optimization around load-after-store/store-after-store. -* Chapter 13: Equivalence class aliasing, fine grained peephole optimizations. Free ptr-to analysis in SoN; but does not handle aliasing in arrays. -* Chapter 14: One dimensional static length array type. Array load/store. -* Chapter 15: Global Code Motion - unwind SoN to CFG. Scheduling. -* Chapter 16: Instruction selection, BURS. -* Chapter 17: Backend register allocation. -* Chapter 18: Garbage Collection. \ No newline at end of file +* [Chapter 2](chapter02/README.md): Simple binary arithmetic such as addition, subtraction, multiplication, division + with constants. Peephole optimization / simple constant folding. +* Chapter 3: Local variables, and assignment statements. Read on RHS, SSA, more peephole optimization if local is a + constant. +* Chapter 4: Binary and Comparison operators involving constants and variables. Non-zero values will be truthy. +* Chapter 5: `if` statement. CFG construction, peephole optimization around dead control flow. +* Chapter 6: `while` statement. +* Chapter 7: Global Value Numbering. +* Chapter 8: Functions and calls. +* Chapter 9: Boolean operators `&&`, `||` and `!` including short circuit. +* Chapter 10: `float` type. +* Chapter 11: Memory effects: general memory edges in SSA. Peephole optimization around + load-after-store/store-after-store. +* Chapter 12: Equivalence class aliasing, fine grained peephole optimizations. Free ptr-to analysis in SoN; but does not + handle aliasing in arrays. +* Chapter 13: One dimensional static length array type. Array load/store. +* Chapter 14: Global Code Motion - unwind SoN to CFG. Scheduling. +* Chapter 15: Instruction selection, BURS. +* Chapter 16: Backend register allocation. +* Chapter 17: Garbage Collection. \ No newline at end of file -- cgit v1.2.3