diff options
34 files changed, 1694 insertions, 22 deletions
@@ -11,4 +11,5 @@ target/ # Editors .#* +*~ @@ -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 diff --git a/chapter01/README.md b/chapter01/README.md index f3231d8c..57caa801 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -113,7 +113,7 @@ Here is visualization of the program: return 1; ``` - + * Control nodes appear as square boxes * Control edges are in bold red diff --git a/chapter01/docs/01-grammar.md b/chapter01/docs/01-grammar.md index cf947dfc..5d9f3cf7 100644 --- a/chapter01/docs/01-grammar.md +++ b/chapter01/docs/01-grammar.md @@ -21,5 +21,6 @@ primaryExpression INTEGER_LITERAL : [1-9][0-9]* + | [0] ; ```
\ No newline at end of file diff --git a/chapter01/docs/02-graph.gv b/chapter01/docs/01-graph.gv index 40181544..40181544 100644 --- a/chapter01/docs/02-graph.gv +++ b/chapter01/docs/01-graph.gv diff --git a/chapter01/docs/02-graph.svg b/chapter01/docs/01-graph.svg index fbf92d7d..fbf92d7d 100644 --- a/chapter01/docs/02-graph.svg +++ b/chapter01/docs/01-graph.svg diff --git a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java index 8fb1ebaf..cdfff842 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java @@ -80,7 +80,7 @@ public class Parser { * Parse integer literal * * <pre> - * integerLiteral: [1-9][0-9]* + * integerLiteral: [1-9][0-9]* | [0] * </pre> */ private ConstantNode parseIntegerLiteral(Lexer lexer) { @@ -245,7 +245,7 @@ public class Parser { private Token parsePuncuation() { int start = _position-1; - while( isPunctuation(nextChar()) ); + if( isPunctuation(nextChar()) ); return Token.newPunct(new String(_input,start,--_position-start)); } diff --git a/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java b/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java index 887f63b8..14c22437 100644 --- a/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java +++ b/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -4,7 +4,7 @@ import com.seaofnodes.simple.node.*; import org.junit.Test; import static org.junit.Assert.*; -public class ParserTest { +public class Chapter01Test { @Test public void testSimpleProgram() { @@ -54,7 +54,7 @@ public class ParserTest { @Test public void testBad3() { try { new Parser().parse("return --12;"); } - catch( RuntimeException e ) { assertEquals("syntax error, expected integer literal: --",e.getMessage()); } + catch( RuntimeException e ) { assertEquals("syntax error, expected integer literal: -",e.getMessage()); } } @Test 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: + + + +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: + + + +* 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 + +
\ No newline at end of file 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 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 2.43.0 (0) + --> +<!-- Title: Lattice Pages: 1 --> +<svg width="548pt" height="266pt" + viewBox="0.00 0.00 547.59 265.88" xmlns="http://www.w3.org/2000/svg"> + <g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 261.88)"> + <title>Lattice</title> + <polygon fill="white" stroke="transparent" points="-4,4 -4,-261.88 543.59,-261.88 543.59,4 -4,4"/> + <!-- Top --> + <g id="node1" class="node"> + <title>Top</title> + <ellipse fill="lightblue" stroke="black" cx="269.65" cy="-238.39" rx="19.5" ry="19.5"/> + <text text-anchor="middle" x="269.65" y="-234.69" font-family="Times,serif" font-size="14.00">⊤</text> + </g> + <!-- A --> + <g id="node3" class="node"> + <title>A</title> + <ellipse fill="lightblue" stroke="black" cx="52.65" cy="-128.94" rx="52.79" ry="52.79"/> + <text text-anchor="middle" x="52.65" y="-125.24" font-family="Times,serif" font-size="14.00">MIN_INT</text> + </g> + <!-- Top->A --> + <g id="edge1" class="edge"> + <title>Top->A</title> + <path fill="none" stroke="black" + d="M250.55,-233.09C220.3,-225.77 160.13,-209.08 114.65,-182.89 106.3,-178.08 98.02,-172.1 90.35,-165.89"/> + </g> + <!-- B --> + <g id="node4" class="node"> + <title>B</title> + <text text-anchor="middle" x="150.65" y="-125.24" font-family="Times,serif" font-size="14.00">...</text> + </g> + <!-- Top->B --> + <g id="edge2" class="edge"> + <title>Top->B</title> + <path fill="none" stroke="black" + d="M252.34,-228.66C234.5,-219.09 206.55,-202.47 186.65,-182.89 175.87,-172.28 166.38,-158 159.86,-146.95"/> + </g> + <!-- C --> + <g id="node5" class="node"> + <title>C</title> + <ellipse fill="lightblue" stroke="black" cx="214.65" cy="-128.94" rx="19.5" ry="19.5"/> + <text text-anchor="middle" x="214.65" y="-125.24" font-family="Times,serif" font-size="14.00">-1</text> + </g> + <!-- Top->C --> + <g id="edge3" class="edge"> + <title>Top->C</title> + <path fill="none" stroke="black" d="M261.05,-220.6C250.72,-200.41 233.48,-166.74 223.18,-146.61"/> + </g> + <!-- D --> + <g id="node6" class="node"> + <title>D</title> + <ellipse fill="lightblue" stroke="black" cx="269.65" cy="-128.94" rx="18" ry="18"/> + <text text-anchor="middle" x="269.65" y="-125.24" font-family="Times,serif" font-size="14.00">0</text> + </g> + <!-- Top->D --> + <g id="edge4" class="edge"> + <title>Top->D</title> + <path fill="none" stroke="black" d="M269.65,-218.67C269.65,-198.47 269.65,-166.57 269.65,-147.03"/> + </g> + <!-- E --> + <g id="node7" class="node"> + <title>E</title> + <ellipse fill="lightblue" stroke="black" cx="323.65" cy="-128.94" rx="18" ry="18"/> + <text text-anchor="middle" x="323.65" y="-125.24" font-family="Times,serif" font-size="14.00">1</text> + </g> + <!-- Top->E --> + <g id="edge5" class="edge"> + <title>Top->E</title> + <path fill="none" stroke="black" d="M278.08,-220.6C288.46,-199.94 305.94,-165.16 315.97,-145.22"/> + </g> + <!-- F --> + <g id="node8" class="node"> + <title>F</title> + <text text-anchor="middle" x="386.65" y="-125.24" font-family="Times,serif" font-size="14.00">...</text> + </g> + <!-- Top->F --> + <g id="edge6" class="edge"> + <title>Top->F</title> + <path fill="none" stroke="black" + d="M286.52,-228.57C303.92,-218.93 331.18,-202.25 350.65,-182.89 361.2,-172.38 370.57,-158.37 377.1,-147.4"/> + </g> + <!-- G --> + <g id="node9" class="node"> + <title>G</title> + <ellipse fill="lightblue" stroke="black" cx="485.65" cy="-128.94" rx="53.89" ry="53.89"/> + <text text-anchor="middle" x="485.65" y="-125.24" font-family="Times,serif" font-size="14.00">MAX_INT</text> + </g> + <!-- Top->G --> + <g id="edge7" class="edge"> + <title>Top->G</title> + <path fill="none" stroke="black" + d="M288.46,-233C318.29,-225.56 377.63,-208.69 422.65,-182.89 430.83,-178.2 438.98,-172.41 446.57,-166.39"/> + </g> + <!-- Bottom --> + <g id="node2" class="node"> + <title>Bottom</title> + <ellipse fill="lightblue" stroke="black" cx="269.65" cy="-19.5" rx="19.5" ry="19.5"/> + <text text-anchor="middle" x="269.65" y="-15.8" font-family="Times,serif" font-size="14.00">⊥</text> + </g> + <!-- A->Bottom --> + <g id="edge8" class="edge"> + <title>A->Bottom</title> + <path fill="none" stroke="black" + d="M90.35,-91.99C98.02,-85.79 106.3,-79.8 114.65,-75 160.13,-48.81 220.3,-32.11 250.55,-24.79"/> + </g> + <!-- B->Bottom --> + <g id="edge9" class="edge"> + <title>B->Bottom</title> + <path fill="none" stroke="black" + d="M159.86,-110.94C166.38,-99.88 175.87,-85.6 186.65,-75 206.55,-55.41 234.5,-38.79 252.34,-29.22"/> + </g> + <!-- C->Bottom --> + <g id="edge10" class="edge"> + <title>C->Bottom</title> + <path fill="none" stroke="black" d="M223.24,-111.15C233.57,-90.97 250.81,-57.3 261.11,-37.17"/> + </g> + <!-- D->Bottom --> + <g id="edge11" class="edge"> + <title>D->Bottom</title> + <path fill="none" stroke="black" d="M269.65,-110.68C269.65,-91.1 269.65,-59.3 269.65,-39.16"/> + </g> + <!-- E->Bottom --> + <g id="edge12" class="edge"> + <title>E->Bottom</title> + <path fill="none" stroke="black" d="M315.91,-112.55C305.88,-92.59 288.44,-57.9 278.08,-37.28"/> + </g> + <!-- F->Bottom --> + <g id="edge13" class="edge"> + <title>F->Bottom</title> + <path fill="none" stroke="black" + d="M377.1,-110.49C370.57,-99.52 361.2,-85.5 350.65,-75 331.18,-55.63 303.92,-38.95 286.52,-29.31"/> + </g> + <!-- G->Bottom --> + <g id="edge14" class="edge"> + <title>G->Bottom</title> + <path fill="none" stroke="black" + d="M446.57,-91.49C438.98,-85.48 430.83,-79.69 422.65,-75 377.63,-49.19 318.29,-32.33 288.46,-24.88"/> + </g> + </g> +</svg> 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 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 2.43.0 (0) + --> +<!-- Title: chapter02 Pages: 1 --> +<svg width="106pt" height="188pt" + viewBox="0.00 0.00 106.45 188.00" xmlns="http://www.w3.org/2000/svg"> + <g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 184)"> + <title>chapter02</title> + <polygon fill="white" stroke="transparent" points="-4,4 -4,-184 102.45,-184 102.45,4 -4,4"/> + <!-- Start1 --> + <g id="node1" class="node"> + <title>Start1</title> + <polygon fill="none" stroke="black" points="92.45,-180 38.45,-180 38.45,-144 92.45,-144 92.45,-180"/> + <text text-anchor="middle" x="65.45" y="-158.3" font-family="Times,serif" font-size="14.00">Start</text> + </g> + <!-- Con213 --> + <g id="node2" class="node"> + <title>Con213</title> + <ellipse fill="none" stroke="black" cx="34.45" cy="-90" rx="34.39" ry="18"/> + <text text-anchor="middle" x="34.45" y="-86.3" font-family="Times,serif" font-size="14.00">Con2</text> + </g> + <!-- Start1->Con213 --> + <g id="edge1" class="edge"> + <title>Start1->Con213</title> + <path fill="none" stroke="black" stroke-dasharray="1,5" + d="M57.78,-143.7C54.2,-135.61 49.86,-125.81 45.9,-116.87"/> + <polygon fill="black" stroke="black" points="49.06,-115.35 41.81,-107.62 42.66,-118.18 49.06,-115.35"/> + </g> + <!-- Return14 --> + <g id="node3" class="node"> + <title>Return14</title> + <polygon fill="none" stroke="black" points="98.45,-36 32.45,-36 32.45,0 98.45,0 98.45,-36"/> + <text text-anchor="middle" x="65.45" y="-14.3" font-family="Times,serif" font-size="14.00">Return</text> + </g> + <!-- Start1->Return14 --> + <g id="edge3" class="edge"> + <title>Start1->Return14</title> + <path fill="none" stroke="red" + d="M70.32,-143.98C73.01,-133.67 76.08,-120.19 77.45,-108 79.22,-92.1 79.22,-87.9 77.45,-72 76.49,-63.43 74.69,-54.22 72.76,-45.93"/> + <polygon fill="red" stroke="red" points="76.11,-44.89 70.32,-36.02 69.32,-46.57 76.11,-44.89"/> + </g> + <!-- Con213->Return14 --> + <g id="edge2" class="edge"> + <title>Con213->Return14</title> + <path fill="none" stroke="black" d="M41.79,-72.41C45.32,-64.45 49.63,-54.72 53.6,-45.76"/> + <polygon fill="black" stroke="black" points="56.87,-47.01 57.72,-36.45 50.47,-44.17 56.87,-47.01"/> + </g> + </g> +</svg> 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 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 2.43.0 (0) + --> +<!-- Title: chapter02 Pages: 1 --> +<svg width="301pt" height="404pt" + viewBox="0.00 0.00 301.08 404.00" xmlns="http://www.w3.org/2000/svg"> + <g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 400)"> + <title>chapter02</title> + <polygon fill="white" stroke="transparent" points="-4,4 -4,-400 297.08,-400 297.08,4 -4,4"/> + <!-- Start1 --> + <g id="node1" class="node"> + <title>Start1</title> + <polygon fill="none" stroke="black" points="169.34,-396 115.34,-396 115.34,-360 169.34,-360 169.34,-396"/> + <text text-anchor="middle" x="142.34" y="-374.3" font-family="Times,serif" font-size="14.00">Start</text> + </g> + <!-- Con12 --> + <g id="node2" class="node"> + <title>Con12</title> + <ellipse fill="none" stroke="black" cx="46.34" cy="-162" rx="34.39" ry="18"/> + <text text-anchor="middle" x="46.34" y="-158.3" font-family="Times,serif" font-size="14.00">Con1</text> + </g> + <!-- Start1->Con12 --> + <g id="edge1" class="edge"> + <title>Start1->Con12</title> + <path fill="none" stroke="black" stroke-dasharray="1,5" + d="M115.19,-374.6C84.32,-370.26 35.25,-358.08 12.34,-324 -15.78,-282.17 11,-221.54 30.37,-187.88"/> + <polygon fill="black" stroke="black" points="33.47,-189.52 35.59,-179.14 27.46,-185.93 33.47,-189.52"/> + </g> + <!-- Con23 --> + <g id="node3" class="node"> + <title>Con23</title> + <ellipse fill="none" stroke="black" cx="55.34" cy="-306" rx="34.39" ry="18"/> + <text text-anchor="middle" x="55.34" y="-302.3" font-family="Times,serif" font-size="14.00">Con2</text> + </g> + <!-- Start1->Con23 --> + <g id="edge2" class="edge"> + <title>Start1->Con23</title> + <path fill="none" stroke="black" stroke-dasharray="1,5" + d="M120.83,-359.7C108.86,-350.07 93.88,-338.01 81.26,-327.86"/> + <polygon fill="black" stroke="black" points="83.35,-325.05 73.37,-321.51 78.97,-330.5 83.35,-325.05"/> + </g> + <!-- Con34 --> + <g id="node4" class="node"> + <title>Con34</title> + <ellipse fill="none" stroke="black" cx="142.34" cy="-306" rx="34.39" ry="18"/> + <text text-anchor="middle" x="142.34" y="-302.3" font-family="Times,serif" font-size="14.00">Con3</text> + </g> + <!-- Start1->Con34 --> + <g id="edge3" class="edge"> + <title>Start1->Con34</title> + <path fill="none" stroke="black" stroke-dasharray="1,5" + d="M142.34,-359.7C142.34,-351.98 142.34,-342.71 142.34,-334.11"/> + <polygon fill="black" stroke="black" points="145.84,-334.1 142.34,-324.1 138.84,-334.1 145.84,-334.1"/> + </g> + <!-- Con56 --> + <g id="node6" class="node"> + <title>Con56</title> + <ellipse fill="none" stroke="black" cx="229.34" cy="-306" rx="34.39" ry="18"/> + <text text-anchor="middle" x="229.34" y="-302.3" font-family="Times,serif" font-size="14.00">Con5</text> + </g> + <!-- Start1->Con56 --> + <g id="edge6" class="edge"> + <title>Start1->Con56</title> + <path fill="none" stroke="black" stroke-dasharray="1,5" + d="M163.84,-359.7C175.81,-350.07 190.8,-338.01 203.41,-327.86"/> + <polygon fill="black" stroke="black" points="205.71,-330.5 211.31,-321.51 201.32,-325.05 205.71,-330.5"/> + </g> + <!-- Return10 --> + <g id="node10" class="node"> + <title>Return10</title> + <polygon fill="none" stroke="black" points="268.34,-36 202.34,-36 202.34,0 268.34,0 268.34,-36"/> + <text text-anchor="middle" x="235.34" y="-14.3" font-family="Times,serif" font-size="14.00">Return</text> + </g> + <!-- Start1->Return10 --> + <g id="edge13" class="edge"> + <title>Start1->Return10</title> + <path fill="none" stroke="red" + d="M169.34,-373.51C199.13,-368.18 246.29,-355.12 272.34,-324 298.3,-292.99 291.34,-275.45 291.34,-235 291.34,-235 291.34,-235 291.34,-161 291.34,-117.91 268.74,-72.26 252.26,-44.7"/> + <polygon fill="red" stroke="red" points="255.17,-42.75 246.94,-36.07 249.21,-46.42 255.17,-42.75"/> + </g> + <!-- Add9 --> + <g id="node9" class="node"> + <title>Add9</title> + <ellipse fill="none" stroke="black" cx="180.34" cy="-90" rx="28.7" ry="18"/> + <text text-anchor="middle" x="180.34" y="-86.3" font-family="Times,serif" font-size="14.00">Add</text> + </g> + <!-- Con12->Add9 --> + <g id="edge10" class="edge"> + <title>Con12->Add9</title> + <path fill="none" stroke="black" d="M69.99,-148.65C92.27,-137 125.77,-119.5 150.02,-106.84"/> + <polygon fill="black" stroke="black" points="151.89,-109.81 159.13,-102.08 148.65,-103.61 151.89,-109.81"/> + </g> + <!-- Mul5 --> + <g id="node5" class="node"> + <title>Mul5</title> + <ellipse fill="none" stroke="black" cx="137.34" cy="-234" rx="28.7" ry="18"/> + <text text-anchor="middle" x="137.34" y="-230.3" font-family="Times,serif" font-size="14.00">Mul</text> + </g> + <!-- Con23->Mul5 --> + <g id="edge4" class="edge"> + <title>Con23->Mul5</title> + <path fill="none" stroke="black" d="M72.73,-290.15C84.56,-280.05 100.38,-266.55 113.4,-255.43"/> + <polygon fill="black" stroke="black" points="115.76,-258.03 121.09,-248.87 111.21,-252.7 115.76,-258.03"/> + </g> + <!-- Con34->Mul5 --> + <g id="edge5" class="edge"> + <title>Con34->Mul5</title> + <path fill="none" stroke="black" d="M141.1,-287.7C140.55,-279.98 139.89,-270.71 139.27,-262.11"/> + <polygon fill="black" stroke="black" points="142.76,-261.83 138.56,-252.1 135.78,-262.33 142.76,-261.83"/> + </g> + <!-- Add8 --> + <g id="node8" class="node"> + <title>Add8</title> + <ellipse fill="none" stroke="black" cx="180.34" cy="-162" rx="28.7" ry="18"/> + <text text-anchor="middle" x="180.34" y="-158.3" font-family="Times,serif" font-size="14.00">Add</text> + </g> + <!-- Mul5->Add8 --> + <g id="edge8" class="edge"> + <title>Mul5->Add8</title> + <path fill="none" stroke="black" d="M147.31,-216.76C152.58,-208.19 159.15,-197.49 165.04,-187.9"/> + <polygon fill="black" stroke="black" points="168.17,-189.5 170.42,-179.15 162.2,-185.84 168.17,-189.5"/> + </g> + <!-- Minus7 --> + <g id="node7" class="node"> + <title>Minus7</title> + <ellipse fill="none" stroke="black" cx="223.34" cy="-234" rx="39.79" ry="18"/> + <text text-anchor="middle" x="223.34" y="-230.3" font-family="Times,serif" font-size="14.00">Minus</text> + </g> + <!-- Con56->Minus7 --> + <g id="edge7" class="edge"> + <title>Con56->Minus7</title> + <path fill="none" stroke="black" d="M227.85,-287.7C227.19,-279.98 226.4,-270.71 225.66,-262.11"/> + <polygon fill="black" stroke="black" points="229.15,-261.77 224.8,-252.1 222.17,-262.37 229.15,-261.77"/> + </g> + <!-- Minus7->Add8 --> + <g id="edge9" class="edge"> + <title>Minus7->Add8</title> + <path fill="none" stroke="black" d="M213.15,-216.41C207.88,-207.83 201.34,-197.19 195.49,-187.67"/> + <polygon fill="black" stroke="black" points="198.38,-185.68 190.16,-178.99 192.41,-189.34 198.38,-185.68"/> + </g> + <!-- Add8->Add9 --> + <g id="edge11" class="edge"> + <title>Add8->Add9</title> + <path fill="none" stroke="black" d="M180.34,-143.7C180.34,-135.98 180.34,-126.71 180.34,-118.11"/> + <polygon fill="black" stroke="black" points="183.84,-118.1 180.34,-108.1 176.84,-118.1 183.84,-118.1"/> + </g> + <!-- Add9->Return10 --> + <g id="edge12" class="edge"> + <title>Add9->Return10</title> + <path fill="none" stroke="black" d="M192.54,-73.46C199.2,-64.99 207.61,-54.29 215.21,-44.61"/> + <polygon fill="black" stroke="black" points="218.19,-46.49 221.62,-36.46 212.69,-42.16 218.19,-46.49"/> + </g> + </g> +</svg> diff --git a/chapter02/pom.xml b/chapter02/pom.xml new file mode 100644 index 00000000..5ced95c3 --- /dev/null +++ b/chapter02/pom.xml @@ -0,0 +1,14 @@ +<?xml version="1.0" encoding="UTF-8"?> +<project xmlns="http://maven.apache.org/POM/4.0.0" + xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" + xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"> + <modelVersion>4.0.0</modelVersion> + <parent> + <groupId>com.seaofnodes</groupId> + <artifactId>simple</artifactId> + <version>1.0</version> + </parent> + <artifactId>chapter02</artifactId> + <packaging>jar</packaging> + <name>Chapter 2</name> +</project>
\ No newline at end of file diff --git a/chapter02/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter02/src/main/java/com/seaofnodes/simple/GraphVisualizer.java new file mode 100644 index 00000000..d2aa8179 --- /dev/null +++ b/chapter02/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -0,0 +1,102 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.ConstantNode; +import com.seaofnodes.simple.node.Control; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.node.StartNode; + +import java.util.Collection; +import java.util.HashMap; +import java.util.Map; + +/** + * Simple visualizer that outputs GraphViz dot format. + * The dot output must be saved to a file and run manually via dot to generate the SVG output. + * Currently, this is done manually. + */ +public class GraphVisualizer { + + public String generateDotOutput(StartNode start) { + // Since the graph has cycles, we need to create a flat list of all the + // nodes in the graph. + Collection<Node> all = findAll(start); + StringBuilder sb = new StringBuilder(); + sb.append("digraph chapter02\n" + + "{\n"); + for (Node n : all) { + sb.append('\t').append(n.uniqueName()); + // control nodes have box shape + // other nodes are ellipses, i.e. default shape + if (n instanceof Control) + sb.append(" [shape=box, "); + else + sb.append(" ["); + sb.append(" label=\"") + .append(n.label()) + .append("\"];\n"); + // Output the non control edges + walkIns(sb, n, false); + } + // Now output the control edges which must be in red + sb.append("\tedge [color=red];\n"); + for (Node n : all) { + walkIns(sb, n, true); + } + sb.append("}\n"); + return sb.toString(); + } + + /** + * Outputs edges. If doControlEdges is true then + * edges between control nodes are output. Else other edges + * output. + */ + private void walkIns(StringBuilder sb, Node in, boolean doControlEdges) { + for (int i = 0; i < in.nIns(); i++) { + Node out = in.in(i); + if (out == null) + continue; + boolean isControlEdge = (out instanceof Control) && (in instanceof Control); + if (doControlEdges && !isControlEdge) + continue; + if (!doControlEdges && isControlEdge) + continue; + sb.append('\t') + .append(out.uniqueName()) + .append(" -> ") + .append(in.uniqueName()); + // the edge from start node to constants is just for convenience so + // show it differently + if ((out instanceof StartNode) && (in instanceof ConstantNode)) + sb.append(" [style=dotted]"); + sb.append(";\n"); + } + } + + /** + * Walks the whole graph, starting from Start. + * Since Start is the input to all constants - we look at the outputs for + * Start, but for then subsequently we look at the inputs of each node. + */ + private Collection<Node> findAll(StartNode start) { + Map<Integer, Node> all = new HashMap<>(); + for (int i = 0; i < start.nOuts(); i++) { + Node n = start.out(i); + walk(all, n); + } + return all.values(); + } + + /** + * Walk a subgraph and populate distinct nodes in the _all list. + */ + private void walk(Map<Integer, Node> all, Node n) { + if (all.get(n._nid) == null) { + // Not yet seen + all.put(n._nid, n); + for (Node c : n._inputs) + if (c != null) + walk(all, c); + } + } +} diff --git a/chapter02/src/main/java/com/seaofnodes/simple/Parser.java b/chapter02/src/main/java/com/seaofnodes/simple/Parser.java new file mode 100644 index 00000000..27a7cffd --- /dev/null +++ b/chapter02/src/main/java/com/seaofnodes/simple/Parser.java @@ -0,0 +1,269 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; + +/** + * The Parser converts a Simple source program to the Sea of Nodes intermediate + * representation directly in one pass. There is no intermediate Abstract + * Syntax Tree structure. + * <p> + * This is a simple recursive descent parser. All lexical analysis is done here as well. + */ +public class Parser { + + private final Lexer _lexer; + + /** + * A Global Static, unique to each compilation. This is a public, so we + * can make constants everywhere without having to thread the StartNode + * through the entire parser and optimizer. + * <p> + * To make the compiler multithreaded, this field will have to move into a TLS. + */ + public static StartNode START; + + public Parser( String source ) { + _lexer = new Lexer(source); + Node.reset(); + START = new StartNode(); + } + + public ReturnNode parse() { + return parseReturn(); + } + + /** + * Parses return statement. + * + * <pre> + * return expr ; + * </pre> + */ + private ReturnNode parseReturn() { + require("return"); + var returnExpr = parseExpression(); + require(";"); + return new ReturnNode(START, returnExpr); + } + + /** + * Parse an expression of the form: + * + * <pre> + * expr : additiveExpr + * </pre> + */ + private Node parseExpression() { + return parseAddition(); + } + + /** + * Parse an additive expression + * + * <pre> + * additiveExpr : multiplicativeExpr (('+' | '-') multiplicativeExpr)* + * </pre> + */ + private Node parseAddition() { + var lhs = parseMultiplication(); + if( match("+") ) return new AddNode(lhs, parseAddition()).peephole(); + if( match("-") ) return new SubNode(lhs, parseAddition()).peephole(); + return lhs; + } + + + /** + * Parse an multiplicativeExpr expression + * + * <pre> + * multiplicativeExpr : unaryExpr (('*' | '/') unaryExpr)* + * </pre> + */ + private Node parseMultiplication() { + var lhs = parseUnary(); + if( match("*") ) return new MulNode(lhs, parseMultiplication()).peephole(); + if( match("/") ) return new DivNode(lhs, parseMultiplication()).peephole(); + return lhs; + } + + /** + * Parse a unary minus expression. + * + * <pre> + * unaryExpr : ('-') unaryExpr | primaryExpr + * </pre> + */ + private Node parseUnary() { + if( match("-") ) return new MinusNode(parseUnary()).peephole(); + return parsePrimary(); + } + + /** + * Parse a primary expression: + * + * <pre> + * primaryExpr : integerLiteral + * </pre> + */ + private Node parsePrimary() { + if( _lexer.isNumber() ) + return parseIntegerLiteral(); + throw error("syntax error, expected integer literal"); + } + + /** + * Parse integer literal + * + * <pre> + * integerLiteral: [1-9][0-9]* | [0] + * </pre> + */ + private ConstantNode parseIntegerLiteral() { + return (ConstantNode)new ConstantNode(_lexer.parseNumber()).peephole(); + } + + static RuntimeException error(String errorMessage) { + return new RuntimeException(errorMessage); + } + + ////////////////////////////////// + // Utilities for lexical analysis + + // Return true and skip if "syntax" is next in the stream. + private boolean match(String syntax) { + return _lexer.match(syntax); + } + + // Require an exact match + private void require(String syntax) { + if( match(syntax) ) return; + throw error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken()); + } + + //////////////////////////////////// + // Lexer components + + private static class Lexer { + + // Input buffer; an array of text bytes read from a file or a string + private final byte[] _input; + // Tracks current position in input buffer + private int _position = 0; + + /** + * Record the source text for lexing + */ + public Lexer(String source) { + this(source.getBytes()); + } + + /** + * Direct from disk file source + */ + public Lexer(byte[] buf) { + _input = buf; + } + + // True if at EOF + private boolean isEOF() { + return _position >= _input.length; + } + + // Peek next character, or report EOF + private char peek() { + return isEOF() ? Character.MAX_VALUE // Special value that causes parsing to terminate + : (char) _input[_position]; + } + + private char nextChar() { + char ch = peek(); + _position++; + return ch; + } + + // True if a white space + private boolean isWhiteSpace() { + return peek() <= ' '; // Includes all the use space, tab, newline, CR + } + + /** + * Return the next non-white-space character + */ + private void skipWhiteSpace() { + while (isWhiteSpace()) + _position++; + } + + + // Return true, if we find "syntax" after skipping white space; also + // then advance the cursor past syntax. + // Return false otherwise, and do not advance the cursor. + boolean match( String syntax ) { + skipWhiteSpace(); + int len = syntax.length(); + if( _position + len > _input.length ) + return false; + for( int i=0; i<len; i++ ) + if( (char)_input[_position+i] != syntax.charAt(i) ) + return false; + _position += len; + return true; + } + + // Used for errors + String getAnyNextToken() { + if( isEOF() ) return ""; + if( isIdentifierStart(peek()) ) + return parseIdentifier(); + if( isPunctuation(peek()) ) + return parsePunctuation(); + return String.valueOf(peek()); + } + + boolean isNumber() { + return isNumber(peek()); + } + + boolean isNumber(char ch) { + return Character.isDigit(ch); + } + + private Type parseNumber() { + int start = _position; + while (isNumber(nextChar())) ; + String snum = new String(_input, start, --_position - start); + if (snum.length() > 1 && snum.charAt(0) == '0') + throw error("Syntax error: integer values cannot start with '0'"); + return new TypeInteger(Long.parseLong(snum)); + } + + // First letter of an identifier + private boolean isIdentifierStart(char ch) { + return Character.isAlphabetic(ch) || ch == '_'; + } + + // All characters of an identifier, e.g. "_x123" + private boolean isIdentifierLetter(char ch) { + return Character.isLetterOrDigit(ch) || ch == '_'; + } + + private String parseIdentifier() { + int start = _position; + while (isIdentifierLetter(nextChar())) ; + return new String(_input, start, --_position - start); + } + + // + private boolean isPunctuation(char ch) { + return "=;[]<>()+-/*".indexOf(ch) != -1; + } + + private String parsePunctuation() { + int start = _position; + if (isPunctuation(nextChar())) ; + return new String(_input, start, --_position - start); + } + } + +} diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/AddNode.java new file mode 100644 index 00000000..015779dc --- /dev/null +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -0,0 +1,35 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.*; + +public class AddNode extends Node { + public AddNode(Node lhs, Node rhs) { + super(null, lhs, rhs); + } + + @Override + public String label() { return "Add"; } + + @Override + StringBuilder _print(StringBuilder sb) { + in(1)._print(sb.append("(")); + in(2)._print(sb.append("+")); + return sb.append(")"); + } + + + @Override + public Type compute() { + if( in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1 ) + return new TypeInteger(i0._con + i1._con); + return TypeBot.BOTTOM; + } + + @Override + public Node idealize () { + // TODO: add of 0 + return null; + } + +} diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/ConstantNode.java new file mode 100644 index 00000000..99ccf4b5 --- /dev/null +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -0,0 +1,39 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.Type; + +/** + * A Constant node represents a constant value. At present, the only constants + * that we allow are integer literals; therefore Constants contain an integer + * value. As we add other types of constants, we will refactor how we represent + * Constants. + * <p> + * Constants have no semantic inputs. However, we set Start as an input to + * Constants to enable a forward graph walk. This edge carries no semantic + * meaning, and it is present <em>solely</em> to allow visitation. + * <p> + * The Constant's value is the value stored in it. + */ +public class ConstantNode extends Node { + + public ConstantNode( Type type ) { + super(Parser.START); + _type = type; + } + + @Override + public String label() { return "Con" + _type; } + + @Override + StringBuilder _print(StringBuilder sb) { + return _type._print(sb); + } + + @Override + public Type compute() { return _type; } + + @Override + public Node idealize() { return null; } + +} diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/Control.java b/chapter02/src/main/java/com/seaofnodes/simple/node/Control.java new file mode 100644 index 00000000..48cf2b7a --- /dev/null +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/Control.java @@ -0,0 +1,9 @@ +package com.seaofnodes.simple.node; + + +/** + * Control interface is a marker interface to be implemented + * by Control nodes. + */ +public interface Control { +} diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/DivNode.java new file mode 100644 index 00000000..bc129690 --- /dev/null +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -0,0 +1,35 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeBot; +import com.seaofnodes.simple.type.TypeInteger; + +public class DivNode extends Node { + public DivNode(Node lhs, Node rhs) { + super(null, lhs, rhs); + } + + @Override + public String label() { return "Div"; } + + @Override + StringBuilder _print(StringBuilder sb) { + in(1)._print(sb.append("(")); + in(2)._print(sb.append("/")); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1) { + if (i1._con == 0) + throw new IllegalArgumentException("Divide by zero"); + return new TypeInteger(i0._con / i1._con); + } + return TypeBot.BOTTOM; + } + + @Override + public Node idealize() { return null; } +} diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/MinusNode.java new file mode 100644 index 00000000..7fab83b0 --- /dev/null +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -0,0 +1,30 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeBot; +import com.seaofnodes.simple.type.TypeInteger; + +public class MinusNode extends Node { + public MinusNode(Node in) { + super(null, in); + } + + @Override + public String label() { return "Minus"; } + + @Override + StringBuilder _print(StringBuilder sb) { + in(1)._print(sb.append("(-")); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0) + return new TypeInteger(-i0._con); + return TypeBot.BOTTOM; + } + + @Override + public Node idealize() { return null; } +} diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/MulNode.java new file mode 100644 index 00000000..e1a26858 --- /dev/null +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -0,0 +1,32 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeBot; +import com.seaofnodes.simple.type.TypeInteger; + +public class MulNode extends Node { + public MulNode(Node lhs, Node rhs) { + super(null, lhs, rhs); + } + + @Override + public String label() { return "Mul"; } + + @Override + StringBuilder _print(StringBuilder sb) { + in(1)._print(sb.append("(")); + in(2)._print(sb.append("*")); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1) + return new TypeInteger(i0._con * i1._con); + return TypeBot.BOTTOM; + } + + @Override + public Node idealize() { return null; } +} diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter02/src/main/java/com/seaofnodes/simple/node/Node.java new file mode 100644 index 00000000..43dea8e1 --- /dev/null +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/Node.java @@ -0,0 +1,213 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; + +import java.util.ArrayList; +import java.util.Collections; + +/** + * All Nodes in the Sea of Nodes IR inherit from the Node class. + * The Node class provides common functionality used by all subtypes. + * Subtypes of Node specialize by overriding methods. + */ +public abstract class Node { + + /** + * Each node has a unique dense Node ID within a compilation context + * The ID is useful for debugging, for using as an offset in a bitvector, + * as well as for computing equality of nodes (to be implemented later). + */ + public final int _nid; + + /** + * Inputs to the node. These are use-def references to Nodes. + * <p> + * Generally fixed length, ordered, nulls allowed, no unused trailing space. + * Ordering is required because e.g. "a/b" is different from "b/a". + * The first input (offset 0) is often a Control node. + * @see Control + */ + public final ArrayList<Node> _inputs; + + /** + * Outputs reference Nodes that are not null and have this Node as an + * input. These nodes are users of this node, thus these are def-use + * references to Nodes. + * <p> + * Outputs directly match inputs, making a directed graph that can be + * walked in either direction. These outputs are typically used for + * efficient optimizations but otherwise have no semantics meaning. + */ + public final ArrayList<Node> _outputs; + + /** + * A private Global Static mutable counter, for unique node id generation. + * To make the compiler multi-threaded, this field will have to move into a TLS. + * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values. + * */ + private static int UNIQUE_ID = 1; + + protected Node(Node ...inputs) { + _nid = UNIQUE_ID++; // allocate unique dense ID + _inputs = new ArrayList<>(); + Collections.addAll(_inputs,inputs); + _outputs = new ArrayList<>(); + for( Node n : _inputs ) + if( n != null ) + n._outputs.add( this ); + // Do an initial type computation + _type = compute(); + } + + public abstract String label(); + + public String uniqueName() { return label() + _nid; } + + @Override + public final String toString() { + // TODO: This needs a lot of work + return uniqueName(); + } + + // This is a *deep* print. This version will fail on cycles, which we will + // correct later when we can parse programs with loops. + public final String print() { + return _print(new StringBuilder()).toString(); + } + abstract StringBuilder _print(StringBuilder sb); + + + /** + * Gets the ith input node + * @param i Offset of the input node + * @return Input node or null + */ + public Node in(int i) { return _inputs.get(i); } + + public int nIns() { return _inputs.size(); } + + /** + * Gets the ith output node + * @param i Offset of the output node + * @return Output node (not null) + */ + public Node out(int i) { return _outputs.get(i); } + + public int nOuts() { return _outputs.size(); } + + /** + * We allow disabling peephole opt so that we can observe the + * full graph, vs the optimized graph. + */ + public static boolean _disablePeephole = false; + + + /** + * Try to peephole at this node and return a better replacement Node if + * possible. We check and replace: + * <ul> + * <li>if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}</li> + * <li>in a future chapter we will look for a + * <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">Common Subexpression</a> + * to eliminate.</li> + * <li>we ask the Node for a better replacement (again, none enabled in this chapter)</li> + * </ul> + */ + public final Node peephole( ) { + if (_disablePeephole) + return this; // Peephole optimizations turned off + + // Replace constant computations from non-constants with a constant node + Type type = compute(); + if (!(this instanceof ConstantNode) && type.isConstant()) { + kill(); // Kill `this` because replacing with a Constant + return new ConstantNode(type); + } + + // Future chapter: Global Value Numbering goes here + + // Ask each node for a replacement + Node n = idealize(); + if( n != null ) return n; + + return this; // No progress + } + + /** + * Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em> + * to null. This may recursively kill more Nodes and is basically dead + * code elimination. This function is co-recursive with {@link #set_def}. + */ + void kill( ) { + assert nOuts()==0; // Has no uses, so it is dead + for( int i=0; i<nIns(); i++ ) + set_def(i,null); // Set all inputs to null, recursively killing unused Nodes + } + + /** + * Change a <em>def</em> into a Node. Keeps the edges correct, by removing + * the corresponding <em>use->def</em> edge. This may make the original + * <em>def</em> go dead. This function is co-recursive with {@link #kill}. + * + * @param idx which def to set + * @param new_def the new definition + */ + void set_def(int idx, Node new_def ) { + Node old_def = in(idx); + if( old_def != null ) { // If the old def exists, remove a use->def edge + ArrayList<Node> outs = old_def._outputs; + int lidx = outs.size()-1; // Last index + + // This 1-line hack compresses an element out of an ArrayList + // without having to copy the contents. The last element is + // stuffed over the deleted element, and then the size is reduced. + outs.set(outs.indexOf(this),outs.get(lidx)); + outs.remove(lidx); // Reduce ArrayList size without copying anything + if( lidx == 0 ) // If we removed the last use, the old def is now dead + old_def.kill(); // Kill old def + } + // Set the new_def over the old (killed) edge + _inputs.set(idx,new_def); + // If new def is not null, add the corresponding use->def edge + if( new_def != null ) + new_def._outputs.add(this); + } + + + /** + * Current computed type for this Node. This value changes as the graph + * changes and more knowledge is gained about the program. + */ + public Type _type; + + /** + * This function needs to be + * <a href="https://en.wikipedia.org/wiki/Monotonic_function">Monotonic</a> + * as it is part of a Monotone Analysis Framework. + * <a href="https://www.cse.psu.edu/~gxt29/teaching/cse597s21/slides/08monotoneFramework.pdf">See for example this set of slides</a>. + * <p> + * For Chapter 2, all our Types are really integer constants, and so all + * the needed properties are trivially true, and we can ignore the high + * theory. Much later on, this will become important and allow us to do + * many fancy complex optimizations trivially... because theory. + * <p> + * compute() needs to be stand-alone, and cannot recursively call compute + * on its inputs programs are cyclic (have loops!) and this will just + * infinitely recurse until stack overflow. Instead, compute typically + * computes a new type from the {@link #_type} field of its inputs. + */ + public abstract Type compute(); + + public abstract Node idealize(); + + /** + * Used to allow repeating tests in the same JVM. This just resets the + * Node unique id generator, and is done as part of making a new Parser. + */ + public static void reset() { UNIQUE_ID = 1; } + + /* + * hashCode and equals implementation to be added in later chapter. + */ + +} diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/ReturnNode.java new file mode 100644 index 00000000..c188ca79 --- /dev/null +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -0,0 +1,39 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.TypeBot; + +/** + * The Return node has two inputs. The first input is a control node and the + * second is the data node that supplies the return value. + * <p> + * In this presentation, Return functions as a Stop node, since multiple <code>return</code> statements are not possible. + * The Stop node will be introduced in Chapter 6 when we implement <code>if</code> statements. + * <p> + * The Return's output is the value from the data node. + */ +public class ReturnNode extends Node implements Control { + + public ReturnNode(Node ctrl, Node data) { + super(ctrl, data); + } + + public Node ctrl() { return in(0); } + public Node expr() { return in(1); } + + @Override + public String label() { return "Return"; } + + @Override + StringBuilder _print(StringBuilder sb) { + return expr()._print(sb.append("return ")).append(";"); + } + + + @Override + public TypeBot compute() { + return TypeBot.BOTTOM; + } + + @Override + public Node idealize() { return null; } +} diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/StartNode.java new file mode 100644 index 00000000..8d8031bb --- /dev/null +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -0,0 +1,31 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.TypeBot; + +/** + * The Start node represents the start of the function. For now, we do not have any inputs to Start because our function does not + * yet accept parameters. When we add parameters the value of Start will be a tuple, and will require Projections to extract the values. + * We discuss this in detail in Chapter 9: Functions and Calls. + */ +public class StartNode extends Node implements Control { + + public StartNode(/*arguments go here*/) { + super(); + } + + @Override + public String label() { return "Start"; } + + @Override + StringBuilder _print(StringBuilder sb) { + return sb.append(label()); + } + + @Override + public TypeBot compute() { + return TypeBot.BOTTOM; + } + + @Override + public Node idealize() { return null; } +} diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/SubNode.java new file mode 100644 index 00000000..2d7db8d3 --- /dev/null +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -0,0 +1,33 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeBot; +import com.seaofnodes.simple.type.TypeInteger; + +public class SubNode extends Node { + public SubNode(Node lhs, Node rhs) { + super(null, lhs, rhs); + } + + @Override + public String label() { return "Sub"; } + + @Override + StringBuilder _print(StringBuilder sb) { + in(1)._print(sb.append("(")); + in(2)._print(sb.append("-")); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1) + return new TypeInteger(i0._con - i1._con); + return TypeBot.BOTTOM; + } + + @Override + public Node idealize() { return null; } + +} diff --git a/chapter02/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter02/src/main/java/com/seaofnodes/simple/type/Type.java new file mode 100644 index 00000000..872e453d --- /dev/null +++ b/chapter02/src/main/java/com/seaofnodes/simple/type/Type.java @@ -0,0 +1,25 @@ +package com.seaofnodes.simple.type; + + +/** + * These types are part of a Monotone Analysis Framework, + * @see <a href="https://www.cse.psu.edu/~gxt29/teaching/cse597s21/slides/08monotoneFramework.pdf">see for example this set of slides</a>. + * <p> + * The types form a lattice; @see <a href="https://en.wikipedia.org/wiki/Lattice_(order)">a symmetric complete bounded (ranked) lattice.</a> + * <p> + * This wild lattice theory will be needed later to allow us to easily beef up + * the analysis and optimization of the Simple compiler... but we don't need it + * now, just know that it is coming along in a later Chapter. + * <p>g + * One of the fun things here is that while the theory is deep and subtle, the + * actual implementation is darn near trivial and is generally really obvious + * what we're doing with it. Right now, it's just simple integer math to do + * simple constant folding e.g. 1+2 == 3 stuff. + */ + +public abstract class Type { + + public boolean isConstant() { return false; } + + public abstract StringBuilder _print(StringBuilder sb); +} diff --git a/chapter02/src/main/java/com/seaofnodes/simple/type/TypeBot.java b/chapter02/src/main/java/com/seaofnodes/simple/type/TypeBot.java new file mode 100644 index 00000000..5284884a --- /dev/null +++ b/chapter02/src/main/java/com/seaofnodes/simple/type/TypeBot.java @@ -0,0 +1,14 @@ +package com.seaofnodes.simple.type; + +import java.lang.StringBuilder; + +public class TypeBot extends Type { + + public static final TypeBot BOTTOM = new TypeBot(); + + @Override + public String toString() { return "Bottom"; } + + @Override + public StringBuilder _print(StringBuilder sb) { return sb.append(toString()); } +} diff --git a/chapter02/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter02/src/main/java/com/seaofnodes/simple/type/TypeInteger.java new file mode 100644 index 00000000..db3d4c46 --- /dev/null +++ b/chapter02/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -0,0 +1,34 @@ +package com.seaofnodes.simple.type; + +/** + * Integer Type + */ +public class TypeInteger extends Type { + + /** + * The constant value observed for this type + */ + public final long _con; + + public TypeInteger(long con) { _con = con; } + + @Override + public String toString() { + return _print(new StringBuilder()).toString(); + } + + @Override + public StringBuilder _print(StringBuilder sb) { return sb.append(_con); } + + @Override + public boolean isConstant() { return true; } + + public long getConstant() { return _con; } + + @Override + public boolean equals( Object o ) { + if( o==this ) return true; + if( !(o instanceof TypeInteger i) ) return false; + return _con==i._con; + } +} diff --git a/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java new file mode 100644 index 00000000..ba9ae448 --- /dev/null +++ b/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -0,0 +1,125 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.ConstantNode; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.node.ReturnNode; +import com.seaofnodes.simple.node.StartNode; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter02Test { + + @Test + public void testChapter2ParseGrammar() { + Node._disablePeephole = true; // disable peephole so we can observe full graph + Parser parser = new Parser("return 1+2*3+-5;"); + ReturnNode ret = parser.parse(); + assertEquals("return (1+((2*3)+(-5)));", ret.print()); + GraphVisualizer gv = new GraphVisualizer(); + System.out.println(gv.generateDotOutput(Parser.START)); + Node._disablePeephole = false; + } + + @Test + public void testChapter2AddPeephole() { + Parser parser = new Parser("return 1+2;"); + ReturnNode ret = parser.parse(); + assertEquals("return 3;", ret.print()); + } + + @Test + public void testChapter2SubPeephole() { + Parser parser = new Parser("return 1-2;"); + ReturnNode ret = parser.parse(); + assertEquals("return -1;", ret.print()); + } + + @Test + public void testChapter2MulPeephole() { + Parser parser = new Parser("return 2*3;"); + ReturnNode ret = parser.parse(); + assertEquals("return 6;", ret.print()); + } + + @Test + public void testChapter2DivPeephole() { + Parser parser = new Parser("return 6/3;"); + ReturnNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + } + + @Test + public void testChapter2MinusPeephole() { + Parser parser = new Parser("return 6/-3;"); + ReturnNode ret = parser.parse(); + assertEquals("return -2;", ret.print()); + } + + @Test + public void testChapter2Example() { + Parser parser = new Parser("return 1+2*3+-5;"); + ReturnNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + GraphVisualizer gv = new GraphVisualizer(); + System.out.println(gv.generateDotOutput(Parser.START)); + } + + @Test + public void testSimpleProgram() { + Parser parser = new Parser("return 1;"); + ReturnNode ret = parser.parse(); + StartNode start = Parser.START; + + assertEquals(start, ret.ctrl()); + Node expr = ret.expr(); + if( expr instanceof ConstantNode con ) { + assertEquals(start,con.in(0)); + assertEquals(new TypeInteger(1), con._type); + } else { + fail(); + } + } + + @Test + public void testZero() { + Parser parser = new Parser("return 0;"); + parser.parse(); + StartNode start = Parser.START; + for( Node use : start._outputs ) + if( use instanceof ConstantNode con ) + assertEquals(new TypeInteger(0),con._type); + } + + @Test + public void testBad1() { + try { new Parser("ret").parse(); } + catch( RuntimeException e ) { assertEquals("Syntax error, expected return: ret",e.getMessage()); } + } + + @Test + public void testBad2() { + try { new Parser("return 0123;").parse(); } + catch( RuntimeException e ) { assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); } + } + + @Test + public void testBad3() { + try { new Parser("return --12;").parse(); } + catch( RuntimeException e ) { assertEquals("Syntax error, expected integer literal: -",e.getMessage()); } + } + + @Test + public void testBad4() { + try { new Parser("return 100").parse(); } + catch( RuntimeException e ) { assertTrue(e.getMessage().contains("Syntax error, expected ;:")); } + } + + // Negative numbers require unary operator support that is not in scope + @Test + public void testBad5() { + try { new Parser("return -100;").parse(); } + catch( RuntimeException e ) { assertEquals("Syntax error, expected integer literal: -", e.getMessage()); } + } +} @@ -21,6 +21,7 @@ <modules> <module>language</module> <module>chapter01</module> + <module>chapter02</module> </modules> <properties> |
