diff options
31 files changed, 2461 insertions, 1 deletions
@@ -8,6 +8,7 @@ # Idea .idea/ target/ +*.iml # Editors .#* @@ -32,7 +32,7 @@ The simple language will be a small subset of C. with constants. Peephole optimization / simple constant folding. * [Chapter 3](chapter03/README.md): 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 4](chapter04/README.md): 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. diff --git a/chapter04/README.md b/chapter04/README.md new file mode 100644 index 00000000..14332d8e --- /dev/null +++ b/chapter04/README.md @@ -0,0 +1,229 @@ +# Chapter 4 + +In this chapter we extend the language grammar with following features: + +* The program receives a single argument named `arg` of integer type from external environment. +* Expressions support comparison operators. +* We introduce a scope sensitive name binding `$ctrl` for the current incoming + control node. Thus, our Return is no longer hard-wired to Start, instead it + tracks the in scope `$ctrl` binding. + +Here is the [complete language grammar](docs/04-grammar.md) for this chapter. + +## Extensions to Intermediate Representation + +In this chapter we add some new nodes and revise some existing nodes. +Following are revised or new nodes + +| Node Name | Type | Description | Inputs | Value | +|-----------|------------------|------------------------------------------------|--------------------------------|-------------------------------------------------------------------------| +| MultiNode | Abstract class | A node that has a tuple result | | A tuple | +| Start | Control | Start of function, now a MultiNode | An input argument named `arg`. | A tuple with a ctrl token and an `arg` data node | +| Proj | ? | Projection nodes extract values from MultiNode | A MultiNode and index | Result is the extracted value from the input MultiNode at offset index | +| Bool | Data | Represents results of a comparison operator | Two data nodes | Result a comparison, represented as integer value where 1=true, 0=false | + +Below is our list of Nodes from chapter 3: + +| Node Name | Type | Description | Inputs | Value | +|------------|---------|------------------------------------|------------------------------------------------------------------|------------------------------| +| 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 | +| 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 | + +## Changes to Type System + +In Chapter 2 we introduced the Type System. Here is a summary of key points: + +We annotate Nodes with Types. + +The Type annotation serves two purposes: + +* it defines the set of operations allowed on the Node, and +* 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`. + +In this chapter we extend the Type hierarchy as follows: + +``` +Type ++-- TypeControl (New - represents control token) ++-- TypeInteger (Enhanced - now has Top and Bottom types) ++-- TypeBot ++-- TypeTuple (New - represents multi-valued result) +``` + +We mentioned in Chapter 2 that the set of values associated with a Type at a specific Node +can be conveniently represented as a "lattice". + +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 this chapter we introduce the possibility of a program input variable named +`arg`; this variable is usually unknown so ⊥ . + +To support the requirements for non-constant integer values, we enhance `TypeInteger` to +allow it to represent `Top` and `Bot` integer types in addition to the earlier constant value. + +Now that integer values may be constants or non-constants, we need to introduce the meet operator +in our lattice. The meet operator describes rules that define the resulting type when we combine +integer values. + +| | ⊥ | Con1 | Con2 | T | +|------|---|------|------|------| +| ⊥ | ⊥ | ⊥ | ⊥ | ⊥ | +| Con1 | ⊥ | Con1 | ⊥ | Con1 | +| T | ⊥ | Con1 | Con2 | T | + + +The `meet` of `Top` with anything is that thing. +The `meet` of `Bot` with anything is `Bot`. +The `meet` of anything with itself is that thing. +The `meet` of two unrelated constants is `Bot`. +Currently, all our integer valued nodes are either a constant or a Bottom integer type. +When we start optimizing loops, we will start seeing Top values. + +## `$ctrl` name binding + +In previous chapters, we had a hard coded control input edge from Start to +Return. In this chapter we no longer have such a hard-wired edge. Instead, we +track the current in-scope control node via the name `$ctrl`. This means that +when we need to create an edge to the predecessor control node, we simply +lookup this name in the current scope. + +This introduces the idea that the control flow subgraph is a Petri net model. +The control token moves virtually from node to node as execution proceeds. The +initial control token is in Start, it then moves via the Proj node to Return. +In later chapters we will see how the token moves across branches. + +## More Peephole Optimizations + +Now that we have non-constant integer values, we do additional optimizations, rearranging algebraic +expressions to enable constant folding. For example: + +``` +return 1 + arg + 2; +``` + +We would expect the compiler to output `arg+3` here, but as it stands what we get is: + + + +We need to perform some algebraic simplifications to enable better outcome. For example, we need to rearrange the +expression as follows: + +``` +arg + (1 + 2) +``` + +Here is a (partial) list of peepholes introduced in this Chapter: + +| Before | After | Description | +|-----------------------|-----------------------|------------------------------------------------| +| (arg + 0 ) | arg | Add of zero identity | +| (arg * 1 ) | arg | Multiple of one identity | +| (con + arg) | (arg + con) | Move constants to right, to encourage folding | +| (con * arg) | (arg * con) | Move constants to right, to encourage folding | +| (con1 + (arg + con2)) | (arg + (con1 + con2)) | Move constants to right, to encourage folding | +| ((arg1 + con) + arg2) | ((arg1 + arg2) + con) | Move constants to right, to encourage folding | +| (arg + arg) | (arg * 2) | Sum-of-products form | + +## Code Walkthrough + +The peephole optimizations introduced in this chapter are local. They are triggered during parsing +as new nodes are created, before the newly created node has any uses. + +For example, when we parse a unary expression, and create a Node for the parsed expression, +`peephole()` is invoked on the newky created `MinusNode`: + +```java +private Node parseUnary() { + if (match("-")) return new MinusNode(parseUnary()).peephole(); + return parsePrimary(); +} +``` + +As another example, here is the parsing of comparison operators, also introduced in this chapter: + +```java +private Node parseComparison() { + var lhs = parseAddition(); + if (match("==")) return new BoolNode.EQNode(lhs, parseComparison()).peephole(); + if (match("!=")) return new BoolNode.NENode(lhs, parseComparison()).peephole(); + if (match("<" )) return new BoolNode.LTNode(lhs, parseComparison()).peephole(); + if (match("<=")) return new BoolNode.LENode(lhs, parseComparison()).peephole(); + if (match(">" )) return new BoolNode.GTNode(lhs, parseComparison()).peephole(); + if (match(">=")) return new BoolNode.GENode(lhs, parseComparison()).peephole(); + return lhs; +} +``` + +The implementation of `peephole()` is in the main `Node` class, and is thus shared +by all subclasses of `Node`. + +```java +public final Node peephole( ) { + // Compute initial or improved Type + Type type = _type = compute(); + + // Replace constant computations from non-constants with a constant node + if (!(this instanceof ConstantNode) && type.isConstant()) + return deadCodeElim(new ConstantNode(type).peephole()); + + // Ask each node for a better replacement + Node n = idealize(); + if( n != null ) // Something changed + // Recursively optimize + return deadCodeElim(n.peephole()); + + return this; // No progress +} +``` + +The peephole method does following: + +* Compute a Type for the node +* If the Type is a Constant, replace with a ConstantNode, recursively invoking peephole on the new node +* Otherwise, ask the Node for a better replacement via a call to `idealize()`. The "better replacement" is things like `(1+2)` becomes `3` and `1+(x+2))` becomes + `(x+(1+2))`. By canonicalizing expressions we fold common addressing math constants, remove algebraic identities and generally simplify the code. + * Each Node subtype is responsible for deciding what the `idealize()` step should do. If there is a better replacement then the node returns a non `null` value. + * If we see a non `null` value, something changed, so we invoke `peephole()` again and then also run dead code elimination. + +`peephole()` calls `deadCodeElim()` which is shown below. + +```java +// m is the new Node, self is the old. +// Return 'm', which may have zero uses but is alive nonetheless. +// If self has zero uses (and is not 'm'), {@link #kill} self. +private Node deadCodeElim(Node m) { + // If self is going dead and not being returned here (Nodes returned + // from peephole commonly have no uses (yet)), then kill self. + if( m != this && isDead() ) { + // Killing self - and since self recursively kills self's inputs we + // might end up killing 'm', which we are returning as a live Node. + // So we add a bogus extra null output edge to stop kill(). + m.addUse(null); // Add bogus null use to keep m alive + kill(); // Kill self because replacing with 'm' + m.delUse(null); // Remove bogus null. + } + return m; +} +``` + +Note the temporary add of a bogus user to the Node `m`. +The reason this is done is that we know `m` is the new replacement and is alive, +but since it is not yet part of the graph up the tree, it has no users yet. +By adding a bogus user we prevent it being mistaken for dead and being killed. diff --git a/chapter04/docs/04-grammar.md b/chapter04/docs/04-grammar.md new file mode 100644 index 00000000..eca2e649 --- /dev/null +++ b/chapter04/docs/04-grammar.md @@ -0,0 +1,78 @@ +# Grammar for Chapter 1 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + | metaStatement + ; + +metaStatement + : '#showGraph' ';' + ; + +expressionStatement + : IDENTIFIER '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +declStatement + : 'int' IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : comparisonExpression + ; + +comparisonExpression + : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | primaryExpression + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | 'true' + | 'false' + | '(' expression ')' + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +```
\ No newline at end of file diff --git a/chapter04/docs/04-post-peephole.gv b/chapter04/docs/04-post-peephole.gv new file mode 100644 index 00000000..22f55468 --- /dev/null +++ b/chapter04/docs/04-post-peephole.gv @@ -0,0 +1,41 @@ +digraph chapter04 { +/* +return 1+arg+2; #showGraph; +*/ + rankdir=BT; + subgraph cluster_Nodes { + Start1 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">Start</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">$ctrl</TD><TD PORT="p1">arg</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Con_9 [ label="#3" ]; + Add10 [ label="Add" ]; + Return11 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + node [shape=plaintext]; + subgraph cluster_0 { + scope0 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="scope0_$ctrl">$ctrl</TD><TD PORT="scope0_arg">arg</TD></TR> + </TABLE>>]; + subgraph cluster_1 { + scope1 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">1</TD></TR> + </TABLE>>]; + } + } + Add10 -> Start1:p1; + Add10 -> Con_9; + Return11 -> Start1:p0 [color=red]; + Return11 -> Add10; + edge [style=dashed color=cornflowerblue]; + scope0:"scope0_$ctrl" -> Start1:p0; + scope0:"scope0_arg" -> Start1:p1; +}
\ No newline at end of file diff --git a/chapter04/docs/04-post-peephole.svg b/chapter04/docs/04-post-peephole.svg new file mode 100644 index 00000000..5a45722c --- /dev/null +++ b/chapter04/docs/04-post-peephole.svg @@ -0,0 +1,110 @@ +<?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: chapter04 Pages: 1 --> +<svg width="417pt" height="248pt" + viewBox="0.00 0.00 417.00 248.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 244)"> +<title>chapter04</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-244 413,-244 413,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-232 193,-232 193,-8 8,-8"/> +</g> +<g id="clust2" class="cluster"> +<title>cluster_0</title> +<polygon fill="none" stroke="black" points="201,-72 201,-140 401,-140 401,-72 201,-72"/> +</g> +<g id="clust3" class="cluster"> +<title>cluster_1</title> +<polygon fill="none" stroke="black" points="323,-80 323,-132 393,-132 393,-80 323,-80"/> +</g> +<!-- Start1 --> +<g id="node1" class="node"> +<title>Start1</title> +<polygon fill="yellow" stroke="transparent" points="97,-195 97,-220 178,-220 178,-195 97,-195"/> +<polygon fill="none" stroke="black" points="97,-195 97,-220 178,-220 178,-195 97,-195"/> +<text text-anchor="start" x="119" y="-203.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="97,-164 97,-195 178,-195 178,-164 97,-164"/> +<polygon fill="yellow" stroke="transparent" points="102,-169 102,-190 142,-190 142,-169 102,-169"/> +<polygon fill="none" stroke="black" points="102,-169 102,-190 142,-190 142,-169 102,-169"/> +<text text-anchor="start" x="105" y="-175.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="142,-169 142,-190 173,-190 173,-169 142,-169"/> +<text text-anchor="start" x="145" y="-175.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- Con_9 --> +<g id="node2" class="node"> +<title>Con_9</title> +<ellipse fill="none" stroke="black" cx="43" cy="-192" rx="27" ry="18"/> +<text text-anchor="middle" x="43" y="-188.3" font-family="Times,serif" font-size="14.00">#3</text> +</g> +<!-- Add10 --> +<g id="node3" class="node"> +<title>Add10</title> +<ellipse fill="none" stroke="black" cx="156" cy="-106" rx="28.7" ry="18"/> +<text text-anchor="middle" x="156" y="-102.3" font-family="Times,serif" font-size="14.00">Add</text> +</g> +<!-- Add10->Start1 --> +<g id="edge1" class="edge"> +<title>Add10->Start1:p1</title> +<path fill="none" stroke="black" d="M156.86,-124.09C157.28,-133.54 157.73,-145.77 157.92,-157.68"/> +<polygon fill="black" stroke="black" points="154.42,-158.03 158,-168 161.42,-157.97 154.42,-158.03"/> +</g> +<!-- Add10->Con_9 --> +<g id="edge2" class="edge"> +<title>Add10->Con_9</title> +<path fill="none" stroke="black" d="M136.93,-119.61C121.35,-130.08 98.91,-145.53 80,-160 75.7,-163.29 71.22,-166.89 66.91,-170.44"/> +<polygon fill="black" stroke="black" points="64.38,-168 58.96,-177.1 68.87,-173.37 64.38,-168"/> +</g> +<!-- Return11 --> +<g id="node4" class="node"> +<title>Return11</title> +<polygon fill="yellow" stroke="black" points="163,-52 97,-52 97,-16 163,-16 163,-52"/> +<text text-anchor="middle" x="130" y="-30.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Return11->Start1 --> +<g id="edge3" class="edge"> +<title>Return11->Start1:p0</title> +<path fill="none" stroke="red" d="M123.24,-52.04C121.12,-58.23 119.05,-65.33 118,-72 113.28,-101.85 115.86,-109.85 118,-140 118.58,-148.23 120.12,-152.3 121.11,-157.68"/> +<polygon fill="red" stroke="red" points="117.66,-158.34 122,-168 124.63,-157.74 117.66,-158.34"/> +</g> +<!-- Return11->Add10 --> +<g id="edge4" class="edge"> +<title>Return11->Add10</title> +<path fill="none" stroke="black" d="M136.43,-52.3C139.4,-60.3 142.99,-69.98 146.29,-78.85"/> +<polygon fill="black" stroke="black" points="143.06,-80.22 149.83,-88.38 149.63,-77.78 143.06,-80.22"/> +</g> +<!-- scope0 --> +<g id="node5" class="node"> +<title>scope0</title> +<polygon fill="cyan" stroke="transparent" points="218,-95 218,-116 234,-116 234,-95 218,-95"/> +<polygon fill="none" stroke="black" points="218,-95 218,-116 234,-116 234,-95 218,-95"/> +<text text-anchor="start" x="221" y="-101.8" font-family="Times,serif" font-size="14.00">0</text> +<polygon fill="none" stroke="black" points="234,-95 234,-116 274,-116 274,-95 234,-95"/> +<text text-anchor="start" x="237" y="-101.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="274,-95 274,-116 305,-116 305,-95 274,-95"/> +<text text-anchor="start" x="277" y="-101.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- scope0->Start1 --> +<g id="edge5" class="edge"> +<title>scope0:scope0_$ctrl->Start1:p0</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M254,-117C254,-176.09 137.5,-113.66 123.39,-158.03"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="119.92,-157.61 122,-168 126.85,-158.58 119.92,-157.61"/> +</g> +<!-- scope0->Start1 --> +<g id="edge6" class="edge"> +<title>scope0:scope0_arg->Start1:p1</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M290,-117C290,-172.03 239,-178.4 184.25,-178.95"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="183.98,-175.45 174,-179 184.02,-182.45 183.98,-175.45"/> +</g> +<!-- scope1 --> +<g id="node6" class="node"> +<title>scope1</title> +<polygon fill="cyan" stroke="transparent" points="350,-95 350,-116 366,-116 366,-95 350,-95"/> +<polygon fill="none" stroke="black" points="350,-95 350,-116 366,-116 366,-95 350,-95"/> +<text text-anchor="start" x="353" y="-101.8" font-family="Times,serif" font-size="14.00">1</text> +</g> +</g> +</svg> diff --git a/chapter04/docs/04-pre-peephole.gv b/chapter04/docs/04-pre-peephole.gv new file mode 100644 index 00000000..e8016c87 --- /dev/null +++ b/chapter04/docs/04-pre-peephole.gv @@ -0,0 +1,45 @@ +digraph chapter04 { +/* +return 1+arg+2; #showGraph; +*/ + rankdir=BT; + subgraph cluster_Nodes { + Start1 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">Start</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">$ctrl</TD><TD PORT="p1">arg</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Con_4 [ label="#1" ]; + Con_5 [ label="#2" ]; + Add6 [ label="Add" ]; + Add7 [ label="Add" ]; + Return8 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + node [shape=plaintext]; + subgraph cluster_0 { + scope0 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="scope0_$ctrl">$ctrl</TD><TD PORT="scope0_arg">arg</TD></TR> + </TABLE>>]; + subgraph cluster_1 { + scope1 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">1</TD></TR> + </TABLE>>]; + } + } + Add6 -> Start1:p1; + Add6 -> Con_5; + Add7 -> Con_4; + Add7 -> Add6; + Return8 -> Start1:p0 [color=red]; + Return8 -> Add7; + edge [style=dashed color=cornflowerblue]; + scope0:"scope0_$ctrl" -> Start1:p0; + scope0:"scope0_arg" -> Start1:p1; +} diff --git a/chapter04/docs/04-pre-peephole.svg b/chapter04/docs/04-pre-peephole.svg new file mode 100644 index 00000000..b1ab4eee --- /dev/null +++ b/chapter04/docs/04-pre-peephole.svg @@ -0,0 +1,134 @@ +<?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: chapter04 Pages: 1 --> +<svg width="417pt" height="320pt" + viewBox="0.00 0.00 417.00 320.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 316)"> +<title>chapter04</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-316 413,-316 413,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-304 193,-304 193,-8 8,-8"/> +</g> +<g id="clust2" class="cluster"> +<title>cluster_0</title> +<polygon fill="none" stroke="black" points="201,-144 201,-212 401,-212 401,-144 201,-144"/> +</g> +<g id="clust3" class="cluster"> +<title>cluster_1</title> +<polygon fill="none" stroke="black" points="323,-152 323,-204 393,-204 393,-152 323,-152"/> +</g> +<!-- Start1 --> +<g id="node1" class="node"> +<title>Start1</title> +<polygon fill="yellow" stroke="transparent" points="97,-267 97,-292 178,-292 178,-267 97,-267"/> +<polygon fill="none" stroke="black" points="97,-267 97,-292 178,-292 178,-267 97,-267"/> +<text text-anchor="start" x="119" y="-275.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="97,-236 97,-267 178,-267 178,-236 97,-236"/> +<polygon fill="yellow" stroke="transparent" points="102,-241 102,-262 142,-262 142,-241 102,-241"/> +<polygon fill="none" stroke="black" points="102,-241 102,-262 142,-262 142,-241 102,-241"/> +<text text-anchor="start" x="105" y="-247.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="142,-241 142,-262 173,-262 173,-241 142,-241"/> +<text text-anchor="start" x="145" y="-247.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- Con_4 --> +<g id="node2" class="node"> +<title>Con_4</title> +<ellipse fill="none" stroke="black" cx="119" cy="-178" rx="27" ry="18"/> +<text text-anchor="middle" x="119" y="-174.3" font-family="Times,serif" font-size="14.00">#1</text> +</g> +<!-- Con_5 --> +<g id="node3" class="node"> +<title>Con_5</title> +<ellipse fill="none" stroke="black" cx="43" cy="-264" rx="27" ry="18"/> +<text text-anchor="middle" x="43" y="-260.3" font-family="Times,serif" font-size="14.00">#2</text> +</g> +<!-- Add6 --> +<g id="node4" class="node"> +<title>Add6</title> +<ellipse fill="none" stroke="black" cx="45" cy="-178" rx="28.7" ry="18"/> +<text text-anchor="middle" x="45" y="-174.3" font-family="Times,serif" font-size="14.00">Add</text> +</g> +<!-- Add6->Start1 --> +<g id="edge1" class="edge"> +<title>Add6->Start1:p1</title> +<path fill="none" stroke="black" d="M59.56,-193.83C66.26,-200.06 74.59,-207 83,-212 110.12,-228.12 148.12,-209.69 156.37,-230.12"/> +<polygon fill="black" stroke="black" points="152.92,-230.7 158,-240 159.83,-229.56 152.92,-230.7"/> +</g> +<!-- Add6->Con_5 --> +<g id="edge2" class="edge"> +<title>Add6->Con_5</title> +<path fill="none" stroke="black" d="M44.6,-196C44.33,-207.31 43.97,-222.42 43.66,-235.43"/> +<polygon fill="black" stroke="black" points="40.15,-235.66 43.41,-245.74 47.15,-235.82 40.15,-235.66"/> +</g> +<!-- Add7 --> +<g id="node5" class="node"> +<title>Add7</title> +<ellipse fill="none" stroke="black" cx="117" cy="-106" rx="28.7" ry="18"/> +<text text-anchor="middle" x="117" y="-102.3" font-family="Times,serif" font-size="14.00">Add</text> +</g> +<!-- Add7->Con_4 --> +<g id="edge3" class="edge"> +<title>Add7->Con_4</title> +<path fill="none" stroke="black" d="M117.49,-124.3C117.71,-132.02 117.98,-141.29 118.23,-149.89"/> +<polygon fill="black" stroke="black" points="114.73,-150 118.51,-159.9 121.72,-149.8 114.73,-150"/> +</g> +<!-- Add7->Add6 --> +<g id="edge4" class="edge"> +<title>Add7->Add6</title> +<path fill="none" stroke="black" d="M102.08,-121.5C92.04,-131.27 78.62,-144.31 67.32,-155.3"/> +<polygon fill="black" stroke="black" points="64.63,-153.03 59.9,-162.51 69.51,-158.05 64.63,-153.03"/> +</g> +<!-- Return8 --> +<g id="node6" class="node"> +<title>Return8</title> +<polygon fill="yellow" stroke="black" points="167,-52 101,-52 101,-16 167,-16 167,-52"/> +<text text-anchor="middle" x="134" y="-30.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Return8->Start1 --> +<g id="edge5" class="edge"> +<title>Return8->Start1:p0</title> +<path fill="none" stroke="red" d="M142.72,-52.17C147.37,-62.31 152.62,-75.56 155,-88 165.33,-142.13 178.15,-161.99 155,-212 148.81,-225.36 132.76,-223.4 125.57,-230.38"/> +<polygon fill="red" stroke="red" points="122.2,-229.41 122,-240 128.76,-231.84 122.2,-229.41"/> +</g> +<!-- Return8->Add7 --> +<g id="edge6" class="edge"> +<title>Return8->Add7</title> +<path fill="none" stroke="black" d="M129.8,-52.3C127.9,-60.1 125.62,-69.49 123.52,-78.17"/> +<polygon fill="black" stroke="black" points="120.11,-77.35 121.15,-87.9 126.92,-79 120.11,-77.35"/> +</g> +<!-- scope0 --> +<g id="node7" class="node"> +<title>scope0</title> +<polygon fill="cyan" stroke="transparent" points="218,-167 218,-188 234,-188 234,-167 218,-167"/> +<polygon fill="none" stroke="black" points="218,-167 218,-188 234,-188 234,-167 218,-167"/> +<text text-anchor="start" x="221" y="-173.8" font-family="Times,serif" font-size="14.00">0</text> +<polygon fill="none" stroke="black" points="234,-167 234,-188 274,-188 274,-167 234,-167"/> +<text text-anchor="start" x="237" y="-173.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="274,-167 274,-188 305,-188 305,-167 274,-167"/> +<text text-anchor="start" x="277" y="-173.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- scope0->Start1 --> +<g id="edge7" class="edge"> +<title>scope0:scope0_$ctrl->Start1:p0</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M254,-189C254,-248.09 137.5,-185.66 123.39,-230.03"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="119.92,-229.61 122,-240 126.85,-230.58 119.92,-229.61"/> +</g> +<!-- scope0->Start1 --> +<g id="edge8" class="edge"> +<title>scope0:scope0_arg->Start1:p1</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M290,-189C290,-244.03 239,-250.4 184.25,-250.95"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="183.98,-247.45 174,-251 184.02,-254.45 183.98,-247.45"/> +</g> +<!-- scope1 --> +<g id="node8" class="node"> +<title>scope1</title> +<polygon fill="cyan" stroke="transparent" points="350,-167 350,-188 366,-188 366,-167 350,-167"/> +<polygon fill="none" stroke="black" points="350,-167 350,-188 366,-188 366,-167 350,-167"/> +<text text-anchor="start" x="353" y="-173.8" font-family="Times,serif" font-size="14.00">1</text> +</g> +</g> +</svg> diff --git a/chapter04/pom.xml b/chapter04/pom.xml new file mode 100644 index 00000000..a69df6d0 --- /dev/null +++ b/chapter04/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>chapter04</artifactId> + <packaging>jar</packaging> + <name>Chapter 4</name> +</project>
\ No newline at end of file diff --git a/chapter04/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter04/src/main/java/com/seaofnodes/simple/GraphVisualizer.java new file mode 100644 index 00000000..38bc1356 --- /dev/null +++ b/chapter04/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -0,0 +1,197 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeControl; + +import java.util.*; + +/** + * 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(Parser parser) { + + // Since the graph has cycles, we need to create a flat list of all the + // nodes in the graph. + Collection<Node> all = findAll(parser); + StringBuilder sb = new StringBuilder(); + sb.append("digraph chapter04 {\n"); + sb.append("/*\n"); + sb.append(parser.src()); + sb.append("\n*/\n"); + + // To keep the Scopes below the graph and pointing up into the graph we + // need to group the Nodes in a subgraph cluster, and the scopes into a + // different subgraph cluster. THEN we can draw edges between the + // scopes and nodes. If we try to cross subgraph cluster borders while + // still making the subgraphs DOT gets confused. + sb.append("\trankdir=BT;\n"); // Force Nodes before Scopes + + // Just the Nodes first, in a cluster no edges + nodes(sb, all); + + // Now the scopes, in a cluster no edges + scopes(sb, parser._scopes); + + // Walk the Node edges + nodeEdges(sb, all); + + // Walk the Scope edges + scopeEdges(sb, parser._scopes); + + sb.append("}\n"); + return sb.toString(); + } + + + private void nodes(StringBuilder sb, Collection<Node> all) { + // Just the Nodes first, in a cluster no edges + sb.append("\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name + for( Node n : all ) { + if( n instanceof ProjNode ) + continue; // Do not emit, rolled into MultiNode already + sb.append("\t\t").append(n.uniqueName()).append(" [ "); + String lab = n.label(); + if( n instanceof MultiNode ) { + // Make a box with the MultiNode on top, and all the projections on the bottom + sb.append("shape=plaintext label=<\n"); + sb.append("\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\" CELLPADDING=\"4\">\n"); + sb.append("\t\t\t<TR><TD BGCOLOR=\"yellow\">").append(lab).append("</TD></TR>\n"); + sb.append("\t\t\t<TR>"); + boolean doProjTable = false; + for( Node use : n._outputs ) { + if( use instanceof ProjNode proj ) { + if (!doProjTable) { + doProjTable = true; + sb.append("<TD>").append("\n"); + sb.append("\t\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">").append("\n"); + sb.append("\t\t\t\t<TR>"); + } + sb.append("<TD PORT=\"p").append(proj._idx).append("\""); + if( proj._idx==0 ) sb.append(" BGCOLOR=\"yellow\""); + sb.append(">").append(proj.label()).append("</TD>"); + } + } + if (doProjTable) { + sb.append("</TR>").append("\n"); + sb.append("\t\t\t\t</TABLE>").append("\n"); + sb.append("\t\t\t</TD>"); + } + sb.append("</TR>\n"); + sb.append("\t\t\t</TABLE>>\n\t\t"); + + } else { + // control nodes have box shape + // other nodes are ellipses, i.e. default shape + if( n instanceof Control ) + sb.append("shape=box style=filled fillcolor=yellow "); + sb.append("label=\"").append(lab).append("\" "); + } + sb.append("];\n"); + } + sb.append("\t}\n"); // End Node cluster + } + + private void scopes( StringBuilder sb, Stack<HashMap<String,Node>> scopes) { + sb.append("\tnode [shape=plaintext];\n"); + int level=0; + for( HashMap<String,Node> scope : scopes ) { + sb.append("\tsubgraph cluster_").append(level).append(" {\n"); // Magic "cluster_" in the subgraph name + String scopeName = makeScopeName(level); + sb.append("\t\t").append(scopeName).append(" [label=<\n"); + sb.append("\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n"); + // Add the scope level + sb.append("\t\t\t<TR><TD BGCOLOR=\"cyan\">").append(level).append("</TD>"); + for( String name : scope.keySet() ) + sb.append("<TD PORT=\"").append(makePortName(scopeName, name)).append("\">").append(name).append("</TD>"); + sb.append("</TR>\n"); + sb.append("\t\t\t</TABLE>>];\n"); + level++; + } + // Scope clusters nest, so the graphics shows the nested scopes, so + // they are not closed as they are printed; so they just keep nesting. + // We close them all at once here. + sb.append( "\t}\n".repeat( level ) ); // End all Scope clusters + } + + private String makeScopeName(int level) { return "scope" + level; } + private String makePortName(String scopeName, String varName) { return scopeName + "_" + varName; } + + private boolean isControlEdge(Node def) { + return def._type instanceof TypeControl; + } + + // Walk the node edges + private void nodeEdges(StringBuilder sb, Collection<Node> all) { + for( Node n : all ) { + if( n instanceof ConstantNode || n instanceof ProjNode ) + continue; // Do not display the Constant->Start edge; ProjNodes handled by Multi + for( Node def : n._inputs ) + if( def != null ) { + sb.append('\t').append(n.uniqueName()).append(" -> "); + if( def instanceof ProjNode proj ) { + String mname = proj.ctrl().uniqueName(); + sb.append(mname).append(":p").append(proj._idx); + } else sb.append(def.uniqueName()); + // Control edges are colored red + if( isControlEdge(def) ) + sb.append(" [color=red]"); + sb.append(";\n"); + } + } + } + + // Walk the scope edges + private void scopeEdges( StringBuilder sb, Stack<HashMap<String,Node>> scopes) { + sb.append("\tedge [style=dashed color=cornflowerblue];\n"); + int level=0; + for( HashMap<String,Node> scope : scopes ) { + String scopeName = makeScopeName(level); + for( String name : scope.keySet() ) { + sb.append("\t") + .append(scopeName).append(":") + .append('"').append(makePortName(scopeName, name)).append('"') // wrap port name with quotes because $ctrl is not valid unquoted + .append(" -> "); + Node def = scope.get(name); + if( def instanceof ProjNode proj ) { + String mname = proj.ctrl().uniqueName(); + sb.append(mname).append(":p").append(proj._idx); + } else sb.append(def.uniqueName()); + sb.append(";\n"); + } + level++; + } + } + + /** + * Finds all nodes in the graph. + */ + private Collection<Node> findAll(Parser parser) { + final StartNode start = Parser.START; + final HashMap<Integer, Node> all = new HashMap<>(); + for( Node n : start._outputs ) + walk(all, n); + // Scan symbol tables + for( HashMap<String,Node> scope : parser._scopes ) + for (Node n : scope.values()) + walk(all, n); + return all.values(); + } + + /** + * Walk a subgraph and populate distinct nodes in the all list. + */ + private void walk(HashMap<Integer, Node> all, Node n) { + if (all.get(n._nid) != null) return; // Been there, done that + all.put(n._nid, n); + for (Node c : n._inputs) + if (c != null) + walk(all, c); + for (Node c : n._outputs) + if (c != null) + walk(all, c); + } +} diff --git a/chapter04/src/main/java/com/seaofnodes/simple/Parser.java b/chapter04/src/main/java/com/seaofnodes/simple/Parser.java new file mode 100644 index 00000000..36fec5d5 --- /dev/null +++ b/chapter04/src/main/java/com/seaofnodes/simple/Parser.java @@ -0,0 +1,414 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; + +import java.util.*; + +/** + * 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 { + + /** + * 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; + + private final Lexer _lexer; + + /** + * Stack of lexical scopes, each scope is a symbol table + * that binds variable names to Nodes. + * The top of this stack represents current scope. + */ + public Stack<HashMap<String, Node>> _scopes; + + public Parser(String source, TypeInteger arg) { + _lexer = new Lexer(source); + _scopes = new Stack<>(); + Node.reset(); + START = new StartNode(new Type[]{ Type.CONTROL, arg }); + START.peephole(); + } + + public Parser(String source) { + this(source, TypeInteger.BOT); + } + + String src() { return new String( _lexer._input ); } + + public ReturnNode parse() { + _scopes.push(new HashMap<>()); + try { + define("$ctrl", new ProjNode(START, 0, "$ctrl").peephole()); + define("arg" , new ProjNode(START, 1, "arg" ).peephole()); + return (ReturnNode) parseBlock(); + } + finally { + _scopes.pop(); + } + } + + // Create a new name in current scope + private Node define(String name, Node n) { + _scopes.lastElement().put(name, n); + return n; + } + + // If the name is present in any scope, then redefine + private Node update(String name, Node n) { + for (int i = _scopes.size() - 1; i >= 0; i--) { + HashMap<String, Node> scope = _scopes.get(i); + Node old = scope.get(name); + if (old != null) { // Found prior def + if (old.nOuts() == 0) old.kill(); // Delete old ref + scope.put(name, n); // Update existing ref + return n; + } + } + throw error("Undefined name '" + name + "'"); + } + + // Lookup a name in all scopes + private Node lookup(String name) { + for (int i = _scopes.size() - 1; i >= 0; i--) { + var n = _scopes.get(i).get(name); + if (n != null) return n; + } + throw error("Undefined name '" + name + "'"); + } + + /** + * Parses a block + * + * <pre> + * '{' statements '}' + * </pre> + */ + private Node parseBlock() { + // Enter a new scope + _scopes.push(new HashMap<>()); + Node n = null; + while (!match("}") && !_lexer.isEOF()) { + Node n0 = parseStatement(); + if (n0 != null) n = n0; // Allow null returns from eg showGraph + } + // Exit scope + _scopes.pop(); + return n; + } + + /** + * Parses a statement + * + * <pre> + * returnStatement | declStatement | blockStatement | expressionStatement + * </pre> + */ + private Node parseStatement() { + if (match("return")) return parseReturn(); + else if (match("int")) return parseDecl(); + else if (match("{")) return parseBlock(); + else if (match("#showGraph")) return showGraph(); + else return parseExpressionStatement(); + } + + /** + * Parses returnStatement; "return" already parsed + * + * <pre> + * 'return' expr ; + * </pre> + */ + private Node parseReturn() { + var expr = require(parseExpression(), ";"); + return new ReturnNode(lookup("$ctrl"), expr); + } + + /** + * Dumps out the node graph + */ + private Node showGraph() { + require(";"); + System.out.println(new GraphVisualizer().generateDotOutput(this)); + return null; + } + + /** + * Parses an expression statement + * + * <pre> + * name '=' expression ';' + * </pre> + */ + private Node parseExpressionStatement() { + var name = requireId(); + require("="); + var expr = require(parseExpression(), ";"); + return update(name, expr); + } + + /** + * Parses a declStatement + * + * <pre> + * 'int' name = expression ';' + * </pre> + */ + private Node parseDecl() { + // Type is 'int' for now + var name = requireId(); + require("="); + var expr = require(parseExpression(), ";"); + return define(name, expr); + } + + /** + * Parse an expression of the form: + * + * <pre> + * expr : additiveExpr + * </pre> + */ + private Node parseExpression() { return parseComparison(); } + + private Node parseComparison() { + var lhs = parseAddition(); + if (match("==")) return new BoolNode.EQNode(lhs, parseComparison()).peephole(); + if (match("!=")) return new BoolNode.NENode(lhs, parseComparison()).peephole(); + if (match("<" )) return new BoolNode.LTNode(lhs, parseComparison()).peephole(); + if (match("<=")) return new BoolNode.LENode(lhs, parseComparison()).peephole(); + if (match(">" )) return new BoolNode.GTNode(lhs, parseComparison()).peephole(); + if (match(">=")) return new BoolNode.GENode(lhs, parseComparison()).peephole(); + return lhs; + } + + /** + * 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 | Identifier | '(' expression ')' + * </pre> + */ + private Node parsePrimary() { + if (_lexer.isNumber()) return parseIntegerLiteral(); + if (match("(")) return require(parseExpression(), ")"); + return lookup(requireId()).peephole(); + } + + /** + * Parse integer literal + * + * <pre> + * integerLiteral: [1-9][0-9]* | [0] + * </pre> + */ + private ConstantNode parseIntegerLiteral() { + return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole(); + } + + ////////////////////////////////// + // 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 and return an identifier + private String requireId() { + String id = _lexer.matchId(); + if (id != null) return id; + throw error("identifier"); + } + + // Require an exact match + private void require(String syntax) { require(null, syntax); } + private Node require(Node n, String syntax) { + if (match(syntax)) return n; + throw errorSyntax(syntax); + } + + RuntimeException errorSyntax(String syntax) { + return error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken()); + } + + static RuntimeException error(String errorMessage) { + return new RuntimeException(errorMessage); + } + + //////////////////////////////////// + // 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; + } + + // Very handy in the debugger, shows the unparsed program + @Override + public String toString() { + return new String(_input, _position, _input.length - _position); + } + + // 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; + } + + // Return an identifier or null + String matchId() { + skipWhiteSpace(); + return isIdStart(peek()) ? parseId() : null; + } + + // Used for errors + String getAnyNextToken() { + if (isEOF()) return ""; + if (isIdStart(peek())) return parseId(); + 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 TypeInteger.constant(Long.parseLong(snum)); + } + + // First letter of an identifier + private boolean isIdStart(char ch) { + return Character.isAlphabetic(ch) || ch == '_'; + } + + // All characters of an identifier, e.g. "_x123" + private boolean isIdLetter(char ch) { + return Character.isLetterOrDigit(ch) || ch == '_'; + } + + private String parseId() { + int start = _position; + while (isIdLetter(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/chapter04/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/AddNode.java new file mode 100644 index 00000000..8b157a9c --- /dev/null +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -0,0 +1,72 @@ +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 _print1(StringBuilder sb) { + in(1)._print0(sb.append("(")); + in(2)._print0(sb.append("+")); + return sb.append(")"); + } + + + @Override + public Type compute() { + if( in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1 ) { + if (i0.isConstant() && i1.isConstant()) + return TypeInteger.constant(i0.value()+i1.value()); + return i0.meet(i1); + } + return TypeBot.BOTTOM; + } + + @Override + public Node idealize () { + Node lhs = in(1); + Node rhs = in(2); + Type t1 = lhs._type; + Type t2 = rhs._type; + + // Add of 0. We do not check for (0+x) because this will already + // canonicalize to (x+0) + if ( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==0 ) + return lhs; + + // Move constants to RHS: con+arg becomes arg+con + if ( t1.isConstant() && !t2.isConstant() ) { + Node tmp = in(1); // Swap inputs without letting either input go dead during the swap + _inputs.set(1,in(2)); + _inputs.set(2,tmp); + return this; + } + + // Goal: a left-spine set of adds, with constants on the rhs (which then fold). + + // Do we have (x + con1) + con2 ? + // Rotate to x +(con1 + con2) + // The constants will fold on the next peephole. + if (t2.isConstant() && lhs instanceof AddNode && lhs.in(2)._type.isConstant() ) + return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole()); + + // Do we have x + (y + con) ? + // Swap to (x + y) + con + if (rhs instanceof AddNode add && add.in(2)._type.isConstant() ) + return new AddNode(new AddNode(lhs,add.in(1)).peephole(), add.in(2)); + + // Add of same to a multiply by 2 + if( lhs==rhs ) + return new MulNode(lhs,new ConstantNode(TypeInteger.constant(2)).peephole()); + + return null; + } + +} diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java new file mode 100644 index 00000000..b0e0bf42 --- /dev/null +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -0,0 +1,53 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeBot; +import com.seaofnodes.simple.type.TypeInteger; + +abstract public class BoolNode extends Node { + + public BoolNode(Node lhs, Node rhs) { + super(null, lhs, rhs); + } + + abstract String op(); // String opcode name + + @Override + public String label() { return op(); } + + @Override + StringBuilder _print1(StringBuilder sb) { + in(1)._print0(sb.append("(")); + in(2)._print0(sb.append(op())); + return sb.append(")"); + } + + @Override + public Type compute() { + if( in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1 ) { + if (i0.isConstant() && i1.isConstant()) + return TypeInteger.constant(doOp(i0.value(), i1.value()) ? 1 : 0); + return i0.meet(i1); + } + return TypeBot.BOTTOM; + } + + abstract boolean doOp(long lhs, long rhs); + + @Override + public Node idealize() { + // Compare of same + if( in(1)==in(2) ) + return new ConstantNode(TypeInteger.constant(doOp(3,3)?1:0)); + + return null; + } + + public static class EQNode extends BoolNode { public EQNode(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } } + public static class NENode extends BoolNode { public NENode(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "!="; } boolean doOp(long lhs, long rhs) { return lhs != rhs; } } + public static class LTNode extends BoolNode { public LTNode(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs < rhs; } } + public static class LENode extends BoolNode { public LENode(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } } + public static class GTNode extends BoolNode { public GTNode(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return ">" ; } boolean doOp(long lhs, long rhs) { return lhs > rhs; } } + public static class GENode extends BoolNode { public GENode(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return ">="; } boolean doOp(long lhs, long rhs) { return lhs >= rhs; } } +} diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ConstantNode.java new file mode 100644 index 00000000..5b4f8af9 --- /dev/null +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -0,0 +1,42 @@ +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 { + Type _con; + public ConstantNode( Type type ) { + super(Parser.START); + _con = type; + } + + @Override + public String label() { return "#"+_con; } + + @Override + public String uniqueName() { return "Con_" + _nid; } + + @Override + StringBuilder _print1(StringBuilder sb) { + return _type._print(sb); + } + + @Override + public Type compute() { return _con; } + + @Override + public Node idealize() { return null; } + +} diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/Control.java b/chapter04/src/main/java/com/seaofnodes/simple/node/Control.java new file mode 100644 index 00000000..48cf2b7a --- /dev/null +++ b/chapter04/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/chapter04/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/DivNode.java new file mode 100644 index 00000000..22167a87 --- /dev/null +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -0,0 +1,38 @@ +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 _print1(StringBuilder sb) { + in(1)._print0(sb.append("(")); + in(2)._print0(sb.append("/")); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1) { + if (i0.isConstant() && i1.isConstant()) { + if (i1.value() == 0) + throw new IllegalArgumentException("Divide by zero"); + return TypeInteger.constant(i0.value()/i1.value()); + } + return i0.meet(i1); + } + return TypeBot.BOTTOM; + } + + @Override + public Node idealize() { return null; } +} diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/MinusNode.java new file mode 100644 index 00000000..04084d0f --- /dev/null +++ b/chapter04/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 _print1(StringBuilder sb) { + in(1)._print0(sb.append("(-")); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0) + return TypeInteger.constant(-i0.value()); + return TypeBot.BOTTOM; + } + + @Override + public Node idealize() { return null; } +} diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/MulNode.java new file mode 100644 index 00000000..e3e83b38 --- /dev/null +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -0,0 +1,55 @@ +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 _print1(StringBuilder sb) { + in(1)._print0(sb.append("(")); + in(2)._print0(sb.append("*")); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1) { + if (i0.isConstant() && i1.isConstant()) + return TypeInteger.constant(i0.value()*i1.value()); + return i0.meet(i1); + } + return TypeBot.BOTTOM; + } + + @Override + public Node idealize() { + Node lhs = in(1); + Node rhs = in(2); + Type t1 = lhs._type; + Type t2 = rhs._type; + + // Mul of 1. We do not check for (1*x) because this will already + // canonicalize to (x*1) + if ( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==1 ) + return lhs; + + // Move constants to RHS: con*arg becomes arg*con + if ( t1.isConstant() && !t2.isConstant() ) { + Node tmp = in(1); // Swap inputs without letting either input go dead during the swap + _inputs.set(1,in(2)); + _inputs.set(2,tmp); + return this; + } + + return null; + } +} diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/MultiNode.java new file mode 100644 index 00000000..e517c3d5 --- /dev/null +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/MultiNode.java @@ -0,0 +1,13 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; + +public abstract class MultiNode extends Node { + + public MultiNode(Node... inputs) { + super(inputs); + } + + // Return the ProjNode with the idx + abstract ProjNode proj(int idx); +} diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java new file mode 100644 index 00000000..45c4e11a --- /dev/null +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java @@ -0,0 +1,317 @@ +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; + + + /** + * Current computed type for this Node. This value changes as the graph + * changes and more knowledge is gained about the program. + */ + public Type _type; + + /** + * 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 ); + } + + public abstract String label(); + + public String uniqueName() { return label() + _nid; } + + @Override + public final String toString() { + // TODO: This needs a lot of work + return print(); + } + + // This is a *deep* print. This version will fail on cycles, which we will + // correct later when we can parse programs with loops. We print with a + // tik-tok style; the common _print0 calls the per-Node _print1, which + // calls back to _print0; + public final String print() { + return _print0(new StringBuilder()).toString(); + } + // This is the common print: check for DEAD and print "DEAD" else call the + // per-Node print1. + final StringBuilder _print0(StringBuilder sb) { + return isDead() + ? sb.append(uniqueName()).append(":DEAD") + : _print1(sb); + } + // Every Node implements this. + abstract StringBuilder _print1(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(); } + + public boolean isUnused() { return nOuts() == 0; } + + /** + * 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 compute a {@link Type} and then 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. The "better replacement" + * is things like {@code (1+2)} becomes {@code 3} and {@code (1+(x+2))} becomes + * {@code (x+(1+2))}. By canonicalizing expressions we fold common addressing + * math constants, remove algebraic identities and generally simplify the + * code. </li> + * </ul> + */ + public final Node peephole( ) { + // Compute initial or improved Type + Type type = _type = compute(); + + if (_disablePeephole) + return this; // Peephole optimizations turned off + + // Replace constant computations from non-constants with a constant node + if (!(this instanceof ConstantNode) && type.isConstant()) + return deadCodeElim(new ConstantNode(type).peephole()); + + // Future chapter: Global Value Numbering goes here + + // Ask each node for a better replacement + Node n = idealize(); + if( n != null ) // Something changed + // Recursively optimize + return deadCodeElim(n.peephole()); + + return this; // No progress + } + + // m is the new Node, self is the old. + // Return 'm', which may have zero uses but is alive nonetheless. + // If self has zero uses (and is not 'm'), {@link #kill} self. + private Node deadCodeElim(Node m) { + // If self is going dead and not being returned here (Nodes returned + // from peephole commonly have no uses (yet)), then kill self. + if( m != this && isDead() ) { + // Killing self - and since self recursively kills self's inputs we + // might end up killing 'm', which we are returning as a live Node. + // So we add a bogus extra null output edge to stop kill(). + m.addUse(null); // Add bogus null use to keep m alive + kill(); // Kill self because replacing with 'm' + m.delUse(null); // Remove bogus null. + } + return m; + } + + + /** + * 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}. + * <p> + + * This method is the normal path for altering a Node, because it does the + * proper default edge maintenance. It also <em>immediately</em> kills + * Nodes that lose their last use; at times care must be taken to avoid + * killing Nodes that are being used without having an output Node. This + * definitely happens in the middle of recursive {@link #peephole} calls. + * + * @param idx which def to set + * @param new_def the new definition + * @return this for flow coding + */ + Node 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 + old_def.delUse(this) ) // 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); + // Return self for easy flow-coding + return this; + } + + // Breaks the edge invariants, used temporarily + private void addUse(Node n) { _outputs.add(n); } + + // Remove node 'use' from 'def's (i.e. our) output list, by compressing the list in-place. + // Return true if the output list is empty afterward. + // Error is 'use' does not exist; ok for 'use' to be null. + private boolean delUse( Node use ) { + ArrayList<Node> outs = _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(use),outs.get(lidx)); + outs.remove(lidx); // Reduce ArrayList size without copying anything + return lidx==0; + } + + /** + * 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}. + */ + public void kill( ) { + assert isUnused(); // 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 + _inputs.clear(); // Flag as dead + _outputs.clear(); // Flag as dead + _type=null; // Flag as dead + assert isDead(); // Really dead now + } + + // Mostly used for asserts and printing. + boolean isDead() { return isUnused() && nIns()==0 && _type==null; } + + /** + * 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(); + + /** + * This function rewrites the current Node into a more "idealized" form. + * This is the bulk of our peephole rewrite rules, and we use this to + * e.g. turn arbitrary collections of adds and multiplies with mixed + * constants into a normal form that's easy for hardware to implement. + * Example: An array addressing expression: + * <pre> ary[idx+1]</pre> + * might turn into Sea-of-Nodes IR: + * <pre> (ary+12)+((idx+1) * 4)</pre> + * This expression can then be idealized into: + * <pre> ary + ((idx*4) + (12 + (1*4)))</pre> + * And more folding: + * <pre> ary + ((idx<<2) + 16)</pre> + * And during code-gen: + * <pre> MOV4 Rary,Ridx,16 // or some such hardware-specific notation </pre> + * <p> + * {@link #idealize} has a very specific calling convention: + * <ul> + * <li>If NO change is made, return {@code null} + * <li>If ANY change is made, return not-null; this can be {@code this} + * <li>The returned Node does NOT call {@link #peephole} on itself; the {@link #peephole} call will recursively peephole it. + * <li>Any NEW nodes that are not directly returned DO call {@link #peephole}. + * </ul> + * <p> + * Examples: + * <table border="3"> + * <tr><th> before </th><th> after </th><th>return </th><th>comment </th></tr> + * <tr><td>{@code (x+5) }</td><td>{@code (x+5) }</td><td>{@code null }</td><td>No change</td></tr> + * <tr><td>{@code (5+x) }</td><td>{@code (x+5) }</td><td>{@code this }</td><td>Swapped arguments</td></tr> + * <tr><td>{@code ((x+1)+2)}</td><td>{@code (x+(1+2))}</td><td>{@code (x+_) }</td><td>Returns 2 new Nodes</td></tr> + * </table> + * + * The last entry deserves more discussion. The new Node {@code (1+2)} + * created in {@link #idealize} calls {@link #peephole} (which then folds + * into a constant). The other new Node {@code (x+3)} does not call + * peephole, because it is returned and peephole itself will recursively + * call peephole. + * <p> + * Since idealize calls peephole and peephole calls idealize, you must be + * careful that all idealizations are <em>monotonic</em>: all transforms remove + * some feature, so that the set of available transforms always shrinks. + * If you don't, you risk an infinite peephole loop! + * + * @return Either a new or changed node, or null for no changes. + */ + 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/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java new file mode 100644 index 00000000..be37c514 --- /dev/null +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -0,0 +1,39 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeBot; +import com.seaofnodes.simple.type.TypeTuple; + +public class ProjNode extends Node { + + // Which slice of the incoming multi-part value + public final int _idx; + + // Debugging label + public final String _label; + + public ProjNode(MultiNode ctrl, int idx, String label) { + super(ctrl); + _idx = idx; + _label = label; + } + + @Override + public String label() { return _label; } + + @Override + StringBuilder _print1(StringBuilder sb) { return sb.append("Proj_" +_nid); } + + public MultiNode ctrl() { return (MultiNode)in(0); } + + @Override + public Type compute() { + Type t = ctrl()._type; + return t instanceof TypeTuple tt ? tt._types[_idx] : TypeBot.BOTTOM; + } + + @Override + public Node idealize() { + return null; + } +} diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java new file mode 100644 index 00000000..c94115bb --- /dev/null +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -0,0 +1,40 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +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 _print1(StringBuilder sb) { + return expr()._print0(sb.append("return ")).append(";"); + } + + + @Override + public Type compute() { + return expr().compute(); + } + + @Override + public Node idealize() { return null; } +} diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java new file mode 100644 index 00000000..0618a42f --- /dev/null +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -0,0 +1,46 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeBot; +import com.seaofnodes.simple.type.TypeTuple; + +/** + * 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 MultiNode implements Control { + + final TypeTuple _args; + + public StartNode(Type[] args) { + super(); + _args = new TypeTuple(args); + } + + @Override + public String label() { return "Start"; } + + @Override + StringBuilder _print1(StringBuilder sb) { + return sb.append(label()); + } + + @Override + public TypeTuple compute() { + return _args; + } + + @Override + public Node idealize() { return null; } + + + @Override + public ProjNode proj( int idx ) { + for( Node proj : _outputs ) + if( ((ProjNode)proj)._idx==idx ) + return (ProjNode)proj; + return null; + } + +} diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/SubNode.java new file mode 100644 index 00000000..e5939e1b --- /dev/null +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -0,0 +1,42 @@ +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 _print1(StringBuilder sb) { + in(1)._print0(sb.append("(")); + in(2)._print0(sb.append("-")); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1) { + if (i0.isConstant() && i1.isConstant()) + return TypeInteger.constant(i0.value()-i1.value()); + return i0.meet(i1); + } + return TypeBot.BOTTOM; + } + + @Override + public Node idealize() { + // Sub of same is 0 + if( in(1)==in(2) ) + return new ConstantNode(TypeInteger.constant(0)); + + return null; + } + +} diff --git a/chapter04/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter04/src/main/java/com/seaofnodes/simple/type/Type.java new file mode 100644 index 00000000..d9567dc8 --- /dev/null +++ b/chapter04/src/main/java/com/seaofnodes/simple/type/Type.java @@ -0,0 +1,30 @@ +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 static final TypeControl CONTROL = new TypeControl(); + + public boolean isConstant() { return false; } + + public abstract StringBuilder _print(StringBuilder sb); + + public Type meet(Type other) { return TypeBot.BOTTOM; } + +} diff --git a/chapter04/src/main/java/com/seaofnodes/simple/type/TypeBot.java b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeBot.java new file mode 100644 index 00000000..a5709448 --- /dev/null +++ b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeBot.java @@ -0,0 +1,19 @@ +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 Type meet(Type other) { + return BOTTOM; + } + + @Override + public StringBuilder _print(StringBuilder sb) { return sb.append(toString()); } +} diff --git a/chapter04/src/main/java/com/seaofnodes/simple/type/TypeControl.java b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeControl.java new file mode 100644 index 00000000..0130ffd0 --- /dev/null +++ b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeControl.java @@ -0,0 +1,16 @@ +package com.seaofnodes.simple.type; + +public class TypeControl extends Type { + + public static final TypeControl CONTROL = new TypeControl(); + + @Override + public StringBuilder _print(StringBuilder sb) { + return sb.append(toString()); + } + + @Override + public String toString() { + return "Control"; + } +} diff --git a/chapter04/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeInteger.java new file mode 100644 index 00000000..e23840e0 --- /dev/null +++ b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -0,0 +1,63 @@ +package com.seaofnodes.simple.type; + +/** + * Integer Type + */ +public class TypeInteger extends Type { + + public final static TypeInteger TOP = new TypeInteger(false, 0); + public final static TypeInteger BOT = new TypeInteger(false, 1); + + private final boolean _is_con; + + /** + * The constant value or + * if not constant then 0=bottom, 1=top. + */ + private final long _con; + + public TypeInteger(boolean is_con, long con) { _is_con = is_con; _con = con; } + + public static TypeInteger constant(long con) { return new TypeInteger(true, con); } + + public boolean isTop() { return !_is_con && _con==0; } + public boolean isBot() { return !_is_con && _con==1; } + + @Override + public String toString() { + return _print(new StringBuilder()).toString(); + } + + @Override + public StringBuilder _print(StringBuilder sb) { + if (isTop()) return sb.append("IntTop"); + if (isBot()) return sb.append("IntBot"); + return sb.append(_con); + } + + @Override + public boolean isConstant() { return _is_con; } + + public long value() { return _con; } + + @Override + public Type meet(Type other) { + if( this==other ) return this; + if (!(other instanceof TypeInteger i)) return super.meet(other); + // BOT wins + if ( isBot() ) return this; + if ( i.isBot() ) return i ; + // TOP loses + if ( i.isTop() ) return this; + if ( isTop() ) return i ; + assert isConstant() && i.isConstant(); + return _con==i._con ? this : TypeInteger.BOT; + } + + @Override + public boolean equals( Object o ) { + if( o==this ) return true; + if( !(o instanceof TypeInteger i) ) return false; + return _con==i._con && _is_con==i._is_con; + } +} diff --git a/chapter04/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeTuple.java new file mode 100644 index 00000000..ef87a415 --- /dev/null +++ b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -0,0 +1,20 @@ +package com.seaofnodes.simple.type; + +public class TypeTuple extends Type { + + public final Type[] _types; + + public TypeTuple(Type[] _types) { + this._types = _types; + } + + @Override + public Type meet(Type other) { + throw new UnsupportedOperationException("Meet on Tuple Type not yet implemented"); + } + + @Override + public StringBuilder _print(StringBuilder sb) { + return sb; + } +} diff --git a/chapter04/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter04/src/test/java/com/seaofnodes/simple/Chapter04Test.java new file mode 100644 index 00000000..988e3608 --- /dev/null +++ b/chapter04/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -0,0 +1,252 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Rule; +import org.junit.Test; +import org.junit.rules.ExpectedException; + +import static org.junit.Assert.*; + +public class Chapter04Test { + + @Rule + public ExpectedException exceptionRule = ExpectedException.none(); + + @Test + public void testChapter4Peephole() { + Parser parser = new Parser("return 1+arg+2; #showGraph;", TypeInteger.BOT); + ReturnNode ret = parser.parse(); + assertEquals("return (Proj_3+3);", ret.print()); + } + + @Test + public void testChapter4Peephole2() { + Parser parser = new Parser("return (1+arg)+2;", TypeInteger.BOT); + ReturnNode ret = parser.parse(); + assertEquals("return (Proj_3+3);", ret.print()); + } + + @Test + public void testChapter4Add0() { + Parser parser = new Parser("return 0+arg;", TypeInteger.BOT); + ReturnNode ret = parser.parse(); + assertEquals("return Proj_3;", ret.print()); + } + + @Test + public void testChapter4AddAddMul() { + Parser parser = new Parser("return arg+0+arg;", TypeInteger.BOT); + ReturnNode ret = parser.parse(); + assertEquals("return (Proj_3*2);", ret.print()); + } + + @Test + public void testChapter4Peephole3() { + Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;", TypeInteger.BOT); + ReturnNode ret = parser.parse(); + assertEquals("return ((Proj_3*2)+6);", ret.print()); + } + + @Test + public void testChapter4Mul1() { + Parser parser = new Parser("return 1*arg;", TypeInteger.BOT); + ReturnNode ret = parser.parse(); + assertEquals("return Proj_3;", ret.print()); + } + + @Test + public void testChapter4VarArg() { + Parser parser = new Parser("return arg; #showGraph;", TypeInteger.BOT); + ReturnNode ret = parser.parse(); + assertTrue(ret.in(0) instanceof ProjNode); + assertTrue(ret.in(1) instanceof ProjNode); + } + + @Test + public void testChapter4ConstantArg() { + Parser parser = new Parser("return arg; #showGraph;", TypeInteger.constant(2)); + ReturnNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + } + + @Test + public void testChapter4CompEq() { + Parser parser = new Parser("return 3==3; #showGraph;", TypeInteger.BOT); + ReturnNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testChapter4CompEq2() { + Parser parser = new Parser("return 3==4; #showGraph;", TypeInteger.BOT); + ReturnNode ret = parser.parse(); + assertEquals("return 0;", ret.print()); + } + + @Test + public void testChapter4CompNEq() { + Parser parser = new Parser("return 3!=3; #showGraph;", TypeInteger.BOT); + ReturnNode ret = parser.parse(); + assertEquals("return 0;", ret.print()); + } + + @Test + public void testChapter4CompNEq2() { + Parser parser = new Parser("return 3!=4; #showGraph;", TypeInteger.BOT); + ReturnNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testVarDecl() { + Parser parser = new Parser("int a=1; return a;"); + ReturnNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testVarAdd() { + Parser parser = new Parser("int a=1; int b=2; return a+b;"); + ReturnNode ret = parser.parse(); + assertEquals("return 3;", ret.print()); + } + + @Test + public void testVarScope() { + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;"); + ReturnNode ret = parser.parse(); + assertEquals("return 4;", ret.print()); + } + + @Test + public void testVarScopeNoPeephole() { + Node._disablePeephole = true; + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;"); + ReturnNode ret = parser.parse(); + Node._disablePeephole = false; + assertEquals("return (1+3);", ret.print()); + } + + @Test + public void testVarDist() { + Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph;"); + ReturnNode ret = parser.parse(); + assertEquals("return 8;", ret.print()); + } + + + @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)); + 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)); + } + + @Test + public void testSimpleProgram() { + Parser parser = new Parser("return 1;"); + ReturnNode ret = parser.parse(); + StartNode start = Parser.START; + + assertTrue(ret.ctrl() instanceof ProjNode); + Node expr = ret.expr(); + if( expr instanceof ConstantNode con ) { + assertEquals(start,con.in(0)); + assertEquals(TypeInteger.constant(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(TypeInteger.constant(0),con._type); + } + + @Test + public void testBad1() { + exceptionRule.expect(RuntimeException.class); + exceptionRule.expectMessage("Syntax error, expected =: "); + new Parser("ret").parse(); + } + + @Test + public void testBad2() { + exceptionRule.expect(RuntimeException.class); + exceptionRule.expectMessage("Syntax error: integer values cannot start with '0'"); + new Parser("return 0123;").parse(); + } + + @Test + public void testNotBad3() { + // this test used to fail in chapter 1 + assertEquals("return 12;", new Parser("return --12;").parse().print()); + } + + @Test + public void testBad4() { + exceptionRule.expect(RuntimeException.class); + exceptionRule.expectMessage("Syntax error, expected ;:"); + new Parser("return 100").parse(); + } + + @Test + public void testNotBad5() { + // this test used to fail in chapter 1 + assertEquals("return -100;", new Parser("return -100;").parse().print()); + } +} @@ -23,6 +23,7 @@ <module>chapter01</module> <module>chapter02</module> <module>chapter03</module> + <module>chapter04</module> </modules> <properties> |
