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/README.md | 126 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 126 insertions(+) create mode 100644 chapter02/README.md (limited to 'chapter02/README.md') diff --git a/chapter02/README.md b/chapter02/README.md new file mode 100644 index 00000000..5b4c4958 --- /dev/null +++ b/chapter02/README.md @@ -0,0 +1,126 @@ +# Chapter 2 + +In this chapter we extend the language grammar to include arithmetic operations such as addition, subtraction, +multiplication, division, and unary minus. This allows us to write statements such as: + +``` +return 1 + 2 * 3 + -5; +``` + +Here is the [complete language grammar](docs/02-grammar.md) for this chapter. + +## Extensions to Intermediate Representation + +In chapter 1 we introduced following nodes. + +| Node Name | Type | Description | Inputs | Value | +|-----------|---------|------------------------------------|------------------------------------------------------------------|-------------------------------------------------------| +| Start | Control | Start of function | None | None for now as we do not have function arguments yet | +| Return | Control | End of function | Predecessor control node, Data node value | Return value of the function | +| Constant | Data | Constants such as integer literals | None, however Start node is set as input to enable graph walking | Value of the constant | + +We extend the set of nodes by adding following additional node types. + +| Node Name | Type | Description | Inputs | Value | +|------------|------|-------------------------------|------------------------------------------------------------|-----------------------------| +| Add | Data | Add two values | Two data nodes, values are added, order not important | Result of the add operation | +| Sub | Data | Subtract a value from another | Two data nodes, values are subtracted, order matters | Result of the subtract | +| Mul | Data | Multiply two values | Two data nodes, values are multiplied, order not important | Result of the multiply | +| Div | Data | Divide a value by another | Two data nodes, values are divided, order matters | Result of the division | +| UnaryMinus | Data | Negate a value | One data node, value is negated | Result of the unary minus | + +## Peephole Optimizations + +Nodes in the graph can be peephole-optimized. The graph is viewed through a +"peephole", a small chunk of graph, and if a certain pattern is detected we +locally rewrite the graph. + +During parsing, these peephole optimizations are particularly easy to check and +apply: there are no uses (yet) of a just-created Node from a just-parsed piece +of syntax, so there's no effort to the "rewrite" part of the problem. We just +replace in-place before installing Nodes into the graph. + +This replacement might allow us to *kill* the unused inputs from the replaced +Node, basically doing a modest Dead Code Elimination during parsing. + +E.g. Suppose we already parsed out a constant `1`, and a constant `2`; then when we +parse an `Add(1,2)`, the peephole rule for constant math replaces the Add with a +constant `3`. At this point, we also *kill* the unused `Add`, which recursively +may *kill* the unused constants `1` and `2`. + + + +## Constant Folding and Constant Propagation + +In this chapter and next we focus on a particular peephole optimization: +constant folding and constant propagation. Since we do not have variables +until Chapter 3, the main feature we demonstrate now is constant folding. +However, we introduce some additional ideas into the compiler at this stage, to +set the scene for Chapter 3. + +It is useful for the compiler to know at various points of the program whether +a node's value is a constant. The compiler can use this knowledge to perform various +optimizations such as: + +* Evaluate expressions at compile time and replace an expression with a constant +* The compiler may be able to identify regions of code that are dead and no + longer needed, such as when a conditional branch always take one of the + branches +* Pointers may be known to be not-null, and a null check can be skipped. +* Array indices may be known to be in-range, and a range check can be skipped +* Many additional optimizations are possible when the compiler learns more + about the possible set of Node values + +In order to achieve above, we annotate Nodes with Types. + +The Type annotation serves two purposes: + +* it defines the set of operations allowed on the Node +* it defines the set of values the Node takes on + +The type itself is identified by the Java class sub-typing relationship; all +types are subtypes of the class `Type`. For now, we only have the following +hierarchy of types: + +``` +Type ++-- TypeInteger +``` + +It turns out that the set of values associated with a Type at a specific Node +can be conveniently represented as a "lattice". Our lattice has the following +structure: + +![Lattice](./docs/02-lattice.svg) + +Our lattice elements can be one of three types: + +* the highest element is "top", denoted by T. +* The lowest is bottom, denoted by ⊥, +* All elements in the middle are constants. + +Assigning ⊥ means that the Node's value is known to be not a compile time +constant, whereas assigning T means that the Node's value may be some (as yet) +undetermined constant. The transition of the Node's type can occur from T to +some constant to ⊥. + +In later chapters we will explore extending this lattice, as it frequently +forms the heart of core optimizations we want our compiler to do. + +There are other important properties of the Lattice that we discuss in Chapter +3, such as the "meet" operator and its rules. + + +## Nodes Pre Peephole Optimization + +The following visual shows how the graph looks like pre-peephole optimization: + +![Example Visual](./docs/02-pre-peephole-ex1.svg) + +* Control nodes appear as square boxes +* Control edges are in bold red +* The edges from Start to Constants are shown in dotted lines as these are not true def-use edges + +## Post-peephole + +![Example Visual](./docs/02-post-peephole-ex1.svg) \ No newline at end of file -- cgit v1.2.3