diff options
| author | Cliff Click <cliffc@acm.org> | 2023-10-20 15:21:08 -0700 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2023-10-20 15:21:08 -0700 |
| commit | 30e5fd29536b04faff8d17d8da8729a8f78bf734 (patch) | |
| tree | 25343a359d7c17af575be673a307df8fa71b4a59 | |
| parent | df5294e88cc409d7adf3e10666bfcb40e34472b9 (diff) | |
| download | Simple-30e5fd29536b04faff8d17d8da8729a8f78bf734.tar.gz Simple-30e5fd29536b04faff8d17d8da8729a8f78bf734.zip | |
Chapter4 (#8)
* Initial work on chapter 4.
Updated language grammar for chapter 4
Enhanced Parser to implement comparison operators
Parser now allows setting 'arg' as input parameter to program
The StartNode now has a tuple as result with two values.
We set up two projection nodes as output of Start - the first is bound to scope as '$ctrl' and second as 'arg'.
Return node now obtains the ctrl input by looking up '$ctrl' in scope; thus it gets the projection node.
Added TypeTuple - represents a tuple of values. This is the type of Start.
Added BoolNode - for comparison operators.
Added MultiNode - interface for nodes that generate tuple results. Start implements this interface.
Added ProjNode - projections to extract values from Start node. Each projection takes a MultiNode and an index value.
Initial writeup of chapter 4 in README.
GraphVisualizer now searches node outputs as well to locate all nodes
* Add TypeControl.
The first member of Start's tuple is of TypeControl.
Correct the projType() method
* Quote port names in edges as unquoted $ctrl is not valid.
Revise how we decide an edge is a control edge so that it works correctly for projections.
* We used to compute initial type in Node but this is problematic for new node types such as
ProjNode and BoolNode as the construction is not yet complete when Node calls compute().
So we have to move compute() call down to the sub type's constructor.
Add some tests for comparison ops.
* Describe the $ctrl name binding and how it represents the Ptri net model.
Add a diagram to show why we need algebraic manipulation of expressions.
* Implement a simplification for expressions such as
(con1 + arg) + con2 -> arg + con3
con1 + (arg + con2) -> arg + con3
* Add diagram to show what the graph looks like post peephole
* Explain projection nodes
* Cleanup Chapter 4, add peepholes.
Add like 6 peepholes. Replace the 2 prior ones with 1-liners.
BoolNode: replace the switch with 6 1-line classes.
Giant comment discussion on idealize() calling convention.
TypeInteger shorten isTop and isBot, and use them instead of calling "equals()".
* 2 more peeps, no tests yet
* Cleanup Chapter 4
`peephole()` kills nodes killed by `idealize()` calls... and works recursively. This requires keeping "mid-peephole" nodes alive. The edge-swap code in Add and Mul now keeps their inputs alive mid-swap.
MultiNode is a class, not an interface.
Move the initial 'compute()' to peephole, instead of requiring each constructor to do it. Start and Constant remember their original types, even if the `_type` field changes.
`kill()` flags nodes as DEAD. Print DEAD nodes with "DEAD". Change recursive `_print()` to a tik-tok style, so each individual print does not need to handle DEAD printing. This printing will soon need a "visit" bit to avoid infinite recursion.
Projs pick up a debugging name.
GraphViz: combine Multis and their Projs. Drop Constant inputs from Start. Fix coloring Control edges red.
* minor WS cleanup
* Cleaned up Node.peephole
Use a smart DCE call after peephole. More comments. Tidy interfaces.
* minor comment cleanup
* But the proj nodes inside a table
* No need to set column span on multi node as we put the proj nodes in a table
* Update the dot diagrams
* Rename method to make it more obvious to the reader
* Start to add a description of peephole
* Rename del() to delUse() and make it an instance method as it reads better that way.
Add new method addUse() again to improve readability.
Adjust removeDeadCode() to make the intention clear.
* Update docs explaining how peephole works
Update the diagrams
* Fix errors
* Add diagram to show what the graph looks like post peephole
* 2 more peeps, no tests yet
* Cleanup Chapter 4
`peephole()` kills nodes killed by `idealize()` calls... and works recursively. This requires keeping "mid-peephole" nodes alive. The edge-swap code in Add and Mul now keeps their inputs alive mid-swap.
MultiNode is a class, not an interface.
Move the initial 'compute()' to peephole, instead of requiring each constructor to do it. Start and Constant remember their original types, even if the `_type` field changes.
`kill()` flags nodes as DEAD. Print DEAD nodes with "DEAD". Change recursive `_print()` to a tik-tok style, so each individual print does not need to handle DEAD printing. This printing will soon need a "visit" bit to avoid infinite recursion.
Projs pick up a debugging name.
GraphViz: combine Multis and their Projs. Drop Constant inputs from Start. Fix coloring Control edges red.
* minor WS cleanup
* Cleaned up Node.peephole
Use a smart DCE call after peephole. More comments. Tidy interfaces.
* minor comment cleanup
* But the proj nodes inside a table
* No need to set column span on multi node as we put the proj nodes in a table
* Update the dot diagrams
* Rename method to make it more obvious to the reader
* Start to add a description of peephole
* Rename del() to delUse() and make it an instance method as it reads better that way.
Add new method addUse() again to improve readability.
Adjust removeDeadCode() to make the intention clear.
* Update docs explaining how peephole works
Update the diagrams
* Minor cleanups
Split isUnused from isDead, with comments.
Rename removeDeadCode back to deadCodeElim after discussion; matches the historical compiler wording.
Fixup large javadoc example with a table.
* match doc and code
* Fix name of method
* Fix name of method
---------
Co-authored-by: dibyendumajumdar <mobile@majumdar.org.uk>
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> |
