From 3b7d6210011df467e3eb27bd5ba6fef121235138 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 26 Sep 2023 17:43:36 +0100 Subject: Chapter 2: Arithmetic MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Dibyendu Majumdar Co-authored-by: Thalia Archibald Co-authored-by: Yichen Yan Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: hadha Co-authored-by: RobertObkircher --- README.md | 2 +- docs/chapter02/02-demonstration-peephole.svg | 54 ++++ .../02-demonstration-pre-peephole-nokill.svg | 100 ++++++++ docs/chapter02/02-demonstration-pre-peephole.svg | 87 +++++++ docs/chapter02/02-grammar.md | 40 +++ docs/chapter02/02-post-peephole-ex1.gv | 17 ++ docs/chapter02/02-post-peephole-ex1.svg | 56 ++++ docs/chapter02/02-pre-peephole-ex1.gv | 34 +++ docs/chapter02/02-pre-peephole-ex1.svg | 168 ++++++++++++ docs/chapter02/Makefile | 12 + docs/chapter02/README.md | 283 +++++++++++++++++++++ docs/chapter02/lattice.gv | 40 +++ docs/chapter02/lattice.svg | 159 ++++++++++++ src/main/java/com/seaofnodes/simple/Parser.java | 81 +++++- src/main/java/com/seaofnodes/simple/Utils.java | 39 +++ .../java/com/seaofnodes/simple/node/AddNode.java | 34 +++ .../com/seaofnodes/simple/node/ConstantNode.java | 25 +- .../java/com/seaofnodes/simple/node/DivNode.java | 32 +++ .../java/com/seaofnodes/simple/node/MinusNode.java | 26 ++ .../java/com/seaofnodes/simple/node/MulNode.java | 30 +++ src/main/java/com/seaofnodes/simple/node/Node.java | 171 ++++++++++++- .../com/seaofnodes/simple/node/ReturnNode.java | 17 ++ .../java/com/seaofnodes/simple/node/StartNode.java | 23 +- .../java/com/seaofnodes/simple/node/SubNode.java | 31 +++ .../simple/print/SimpleGraphAdapter.java | 10 +- .../simple/print/SimpleGraphObserver.java | 4 +- src/main/java/com/seaofnodes/simple/type/Type.java | 40 +++ .../com/seaofnodes/simple/type/TypeInteger.java | 41 +++ .../java/com/seaofnodes/simple/Chapter01Test.java | 26 +- .../java/com/seaofnodes/simple/Chapter02Test.java | 60 +++++ 30 files changed, 1697 insertions(+), 45 deletions(-) create mode 100644 docs/chapter02/02-demonstration-peephole.svg create mode 100644 docs/chapter02/02-demonstration-pre-peephole-nokill.svg create mode 100644 docs/chapter02/02-demonstration-pre-peephole.svg create mode 100644 docs/chapter02/02-grammar.md create mode 100644 docs/chapter02/02-post-peephole-ex1.gv create mode 100644 docs/chapter02/02-post-peephole-ex1.svg create mode 100644 docs/chapter02/02-pre-peephole-ex1.gv create mode 100644 docs/chapter02/02-pre-peephole-ex1.svg create mode 100644 docs/chapter02/Makefile create mode 100644 docs/chapter02/README.md create mode 100644 docs/chapter02/lattice.gv create mode 100644 docs/chapter02/lattice.svg create mode 100644 src/main/java/com/seaofnodes/simple/Utils.java create mode 100644 src/main/java/com/seaofnodes/simple/node/AddNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/DivNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/MinusNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/MulNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/SubNode.java create mode 100644 src/main/java/com/seaofnodes/simple/type/Type.java create mode 100644 src/main/java/com/seaofnodes/simple/type/TypeInteger.java create mode 100644 src/test/java/com/seaofnodes/simple/Chapter02Test.java diff --git a/README.md b/README.md index ffd3ef9e..9f85aa24 100644 --- a/README.md +++ b/README.md @@ -38,7 +38,7 @@ intermediate representation. The Simple language is styled after a subset of C or Java. * [Chapter 1](docs/chapter01/README.md): Script that returns an integer literal, i.e., an empty function that takes no arguments and returns a single integer value. The `return` statement. -* Chapter 2: Simple binary arithmetic such as addition, subtraction, multiplication, division +* [Chapter 2](docs/chapter02/README.md): Simple binary arithmetic such as addition, subtraction, multiplication, division with constants. Peephole optimization / simple constant folding. * Chapter 3: Local variables, and assignment statements. Read on RHS, SSA, more peephole optimization if local is a constant. diff --git a/docs/chapter02/02-demonstration-peephole.svg b/docs/chapter02/02-demonstration-peephole.svg new file mode 100644 index 00000000..90ab6ca4 --- /dev/null +++ b/docs/chapter02/02-demonstration-peephole.svg @@ -0,0 +1,54 @@ + + + + + + +chapter02 + + +cluster_Nodes + + + + +Start1 + +Start + + + +Con_5 + +#3 + + + +Con_5->Start1 + + +0 + + + +Return6 + +Return + + + +Return6->Start1 + + +0 + + + +Return6->Con_5 + + +1 + + + \ No newline at end of file diff --git a/docs/chapter02/02-demonstration-pre-peephole-nokill.svg b/docs/chapter02/02-demonstration-pre-peephole-nokill.svg new file mode 100644 index 00000000..3d4f53df --- /dev/null +++ b/docs/chapter02/02-demonstration-pre-peephole-nokill.svg @@ -0,0 +1,100 @@ + + + + + + +chapter02 + + +cluster_Nodes + + + + +Start1 + +Start + + + +Con_2 + +#1 + + + +Con_2->Start1 + + +0 + + + +Con_3 + +#2 + + + +Con_3->Start1 + + +0 + + + +Add4 + ++ + + + +Add4->Con_2 + + +1 + + + +Add4->Con_3 + + +2 + + + +Con_5 + +#3 + + + +Con_5->Start1 + + +0 + + + +Return6 + +Return + + + +Return6->Start1 + + +0 + + + +Return6->Con_5 + + +1 + + + \ No newline at end of file diff --git a/docs/chapter02/02-demonstration-pre-peephole.svg b/docs/chapter02/02-demonstration-pre-peephole.svg new file mode 100644 index 00000000..49624652 --- /dev/null +++ b/docs/chapter02/02-demonstration-pre-peephole.svg @@ -0,0 +1,87 @@ + + + + + + +chapter02 + + +cluster_Nodes + + + + +Start1 + +Start + + + +Con_2 + +#1 + + + +Con_2->Start1 + + +0 + + + +Con_3 + +#2 + + + +Con_3->Start1 + + +0 + + + +Add4 + ++ + + + +Add4->Con_2 + + +1 + + + +Add4->Con_3 + + +2 + + + +Return5 + +Return + + + +Return5->Start1 + + +0 + + + +Return5->Add4 + + +1 + + + \ No newline at end of file diff --git a/docs/chapter02/02-grammar.md b/docs/chapter02/02-grammar.md new file mode 100644 index 00000000..ce875eda --- /dev/null +++ b/docs/chapter02/02-grammar.md @@ -0,0 +1,40 @@ +# Grammar for Chapter 1 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement EOF + ; + +statement + : 'return' expression ';' + ; + +expression + : additiveExpression + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | primaryExpression + ; + +primaryExpression + : INTEGER_LITERAL + | '(' expression ')' + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; +``` diff --git a/docs/chapter02/02-post-peephole-ex1.gv b/docs/chapter02/02-post-peephole-ex1.gv new file mode 100644 index 00000000..6c2b23ae --- /dev/null +++ b/docs/chapter02/02-post-peephole-ex1.gv @@ -0,0 +1,17 @@ +digraph chapter02 { +/* +return 1+2*3+-5; +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start1 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con_13 [ label="#2" ]; + Return14 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Con_13 -> Start1[taillabel=0 style=dotted]; + Return14 -> Start1[taillabel=0 color=red]; + Return14 -> Con_13[taillabel=1]; +} diff --git a/docs/chapter02/02-post-peephole-ex1.svg b/docs/chapter02/02-post-peephole-ex1.svg new file mode 100644 index 00000000..db27e30d --- /dev/null +++ b/docs/chapter02/02-post-peephole-ex1.svg @@ -0,0 +1,56 @@ + + + + + + +chapter02 + + +cluster_Nodes + + + + +Start1 + +Start + + + +Con_13 + +#2 + + + +Con_13->Start1 + + +0 + + + +Return14 + +Return + + + +Return14->Start1 + + +0 + + + +Return14->Con_13 + + +1 + + + diff --git a/docs/chapter02/02-pre-peephole-ex1.gv b/docs/chapter02/02-pre-peephole-ex1.gv new file mode 100644 index 00000000..411de5ee --- /dev/null +++ b/docs/chapter02/02-pre-peephole-ex1.gv @@ -0,0 +1,34 @@ +digraph chapter02 { +/* +return 1+2*3+-5; +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start1 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con_2 [ label="#1" ]; + Con_3 [ label="#2" ]; + Con_4 [ label="#3" ]; + Mul5 [ label="*" ]; + Con_6 [ label="#5" ]; + Minus7 [ label="-" ]; + Add8 [ label="+" ]; + Add9 [ label="+" ]; + Return10 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Con_2 -> Start1[taillabel=0 style=dotted]; + Con_3 -> Start1[taillabel=0 style=dotted]; + Con_4 -> Start1[taillabel=0 style=dotted]; + Mul5 -> Con_3[taillabel=1]; + Mul5 -> Con_4[taillabel=2]; + Con_6 -> Start1[taillabel=0 style=dotted]; + Minus7 -> Con_6[taillabel=1]; + Add8 -> Mul5[taillabel=1]; + Add8 -> Minus7[taillabel=2]; + Add9 -> Con_2[taillabel=1]; + Add9 -> Add8[taillabel=2]; + Return10 -> Start1[taillabel=0 color=red]; + Return10 -> Add9[taillabel=1]; +} diff --git a/docs/chapter02/02-pre-peephole-ex1.svg b/docs/chapter02/02-pre-peephole-ex1.svg new file mode 100644 index 00000000..29c76bd8 --- /dev/null +++ b/docs/chapter02/02-pre-peephole-ex1.svg @@ -0,0 +1,168 @@ + + + + + + +chapter02 + + +cluster_Nodes + + + + +Start1 + +Start + + + +Con_2 + +#1 + + + +Con_2->Start1 + + +0 + + + +Con_3 + +#2 + + + +Con_3->Start1 + + +0 + + + +Con_4 + +#3 + + + +Con_4->Start1 + + +0 + + + +Mul5 + +* + + + +Mul5->Con_3 + + +1 + + + +Mul5->Con_4 + + +2 + + + +Con_6 + +#5 + + + +Con_6->Start1 + + +0 + + + +Minus7 + +- + + + +Minus7->Con_6 + + +1 + + + +Add8 + ++ + + + +Add8->Mul5 + + +1 + + + +Add8->Minus7 + + +2 + + + +Add9 + ++ + + + +Add9->Con_2 + + +1 + + + +Add9->Add8 + + +2 + + + +Return10 + +Return + + + +Return10->Start1 + + +0 + + + +Return10->Add9 + + +1 + + + diff --git a/docs/chapter02/Makefile b/docs/chapter02/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter02/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/docs/chapter02/README.md b/docs/chapter02/README.md new file mode 100644 index 00000000..308c75f4 --- /dev/null +++ b/docs/chapter02/README.md @@ -0,0 +1,283 @@ +# Chapter 2: Arithmetic + + +# Table of Contents + +1. [Extensions to Intermediate Representation](#extensions-to-intermediate-representation) +2. [Peephole Optimizations](#peephole-optimizations) +3. [Constant Folding and Constant Propagation](#constant-folding-and-constant-propagation) +4. [Nodes Pre Peephole Optimization](#nodes-pre-peephole-optimization) +5. [Post-peephole](#post-peephole) +6. [Demonstration](#demonstration) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter02) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter01...linear-chapter02) it to the previous chapter. + + +In this chapter we extend the language grammar to include arithmetic operations such as addition, subtraction, +multiplication, division, and unary minus. This allows us to write statements such as: + +``` +return 1 + 2 * 3 + -5; +``` + +Here is the [complete language grammar](02-grammar.md) for this chapter. + +## Extensions to Intermediate Representation + +In [Chapter 1](../chapter01/README.md) we introduced following nodes. + +| Node Name | Type | Description | Inputs | Value | +|-----------|---------|------------------------------------|------------------------------------------------------------------|-------------------------------------------------------| +| Start | Control | Start of function | None | None for now as we do not have function arguments yet | +| Return | Control | End of function | Predecessor control node, Data node value | Return value of the function | +| Constant | Data | Constants such as integer literals | None, however Start node is set as input to enable graph walking | Value of the constant | + +We extend the set of nodes by adding following additional node types. + +| Node Name | Type | Description | Inputs | Value | +|-----------|------|-------------------------------|------------------------------------------------------------|-----------------------------| +| Add | Data | Add two values | Two data nodes, values are added, order not important | Result of the add operation | +| Sub | Data | Subtract a value from another | Two data nodes, values are subtracted, order matters | Result of the subtract | +| Mul | Data | Multiply two values | Two data nodes, values are multiplied, order not important | Result of the multiply | +| Div | Data | Divide a value by another | Two data nodes, values are divided, order matters | Result of the division | +| Minus | Data | Negate a value | One data node, value is negated | Result of the unary minus | + + +## *Value* equality vs *Reference* equality + +In much of Simple, Nodes are looked up (`find()` calls) via *reference* +equality. This is by far the most common case. In [Chapter +9](../chapter09/README.md) we introduce *value* equality for the first time. +In both cases the choice of value-vs-reference equality is intentional: it is +*never* correct to "just pick one or the other kind of equality". When in +doubt check the context: only *Global Value Numbering* uses value equality; +everywhere we mean reference equality. + + +## Peephole Optimizations + +Nodes in the graph can be peephole-optimized. The graph is viewed through a +"peephole", a small chunk of graph, and if a certain pattern is detected we +locally rewrite the graph. + +During parsing, these peephole optimizations are particularly easy to check and +apply: there are no uses (yet) of a just-created Node from a just-parsed piece +of syntax, so there's no effort to the "rewrite" part of the problem. We just +replace in-place before installing Nodes into the graph. + +This replacement might allow us to *kill* the unused inputs from the replaced +Node, basically doing a modest Dead Code Elimination during parsing. + +E.g. Suppose we already parsed out a constant `1`, and a constant `2`; then when we +parse an `Add(1,2)`, the peephole rule for constant math replaces the Add with a +constant `3`. At this point, we also *kill* the unused `Add`, which recursively +may *kill* the unused constants `1` and `2`. + + + +## Constant Folding and Constant Propagation + +In this chapter and next we focus on a particular peephole optimization: +constant folding and constant propagation. Since we do not have non-constant values +until [Chapter 4](../chapter04/README.md), the main feature we demonstrate now is constant folding. +However, we introduce some additional ideas into the compiler at this stage, to +set the scene for Chapter 4. + +It is useful for the compiler to know at various points of the program whether +a node's value is a constant. The compiler can use this knowledge to perform various +optimizations such as: + +* Evaluate expressions at compile time and replace an expression with a + constant. This idea can be extended in a number of ways and is called + [Partial Evaluation](https://en.wikipedia.org/wiki/Partial_evaluation). +* The compiler may be able to identify regions of code that are dead and no + longer needed, such as when a conditional branch always take one of the + branches ([Chapter 6](../chapter06/README.md)). +* Pointers may be known to be not-null, and a null check can be skipped ([Chapter 10a](../chapter10a/README.md)). +* Array indices may be known to be in-range, and a range check can be skipped. +* Many additional optimizations are possible when the compiler learns more + about the possible set of Node values. + +In order to achieve above, we need a way to talk about what kinds of values a Node can take +on at runtime - we call these Types, and we annotate Nodes with Types. + +The Type annotation serves two purposes: + +* it defines the set of operations allowed on the Node +* it defines the set of values the Node takes on + +The Type itself is represented as a Java class; the Java classes are used as +convenient to represent the Type's structure; all types are subtypes of the +class `Type`. For now, we only have the following hierarchy of types: + +``` +Type ++-- TypeInteger +``` + +It turns out that the set of values associated with a Type at a specific Node +can be conveniently represented as a *lattice* +[wiki/Lattice_(order)](https://en.wikipedia.org/wiki/Lattice_(order)). Our lattice has the following structure: + +![Lattice](./lattice.svg) + +Our lattice elements can be one of three types: + +* The highest element is "top", denoted by ⊤; assigning ⊤ means that the Node's + value may or may not be a compile time constant. +* All elements in the middle are constants. +* The lowest is "bottom", denoted by ⊥; assigning ⊥ means that we know that the + Node's value is **not** a compile time constant. + +An invariant of peephole optimizations is that the type of a Node always moves +*up* the lattice (towards "top"); peepholes are *pessmistic* assuming the worst +until they can prove better. A later *optimistic* optimization will start all +Nodes at *top* and move Types *down* the lattice as eager assumptions are +proven wrong. + +In later chapters we will explore extending this lattice, as it frequently +forms the heart of core optimizations we want our compiler to do. + +We add a `_type` field to every Node, to store its current computed best +`Type`. We need a field to keep the optimizer runtime linear, and later when +doing an optimistic version of constant propagation (called [Sparse Conditional +Constant Propagation](https://en.wikipedia.org/wiki/Sparse_conditional_constant_propagation)). + +We add a `_type` field even to `Start` and `Return`, and later to all control +Nodes - because the Sea of Nodes does not distinguish between control and data. +Both nodes are equally peepholed and optimized, and this will be covered +starting in [Chapter 4](../chapter04/README.md) and [Chapter +5](../chapter05/README.md). + + +There are other important properties of the Lattice that we discuss in [Chapter +4](../chapter04/README.md) and [Chapter 10a](../chapter10a/README.md), such as the "meet" and "join" operators and their rules. + + +## Nodes Pre Peephole Optimization + +The following schematic shows the operations before peephole folding. The parser +optimizes each node as it is built; it does not retain this entire intermediate graph: + +![Example Visual](./02-pre-peephole-ex1.svg) + +* Control nodes appear as square boxes with yellow background +* Control edges are in bold red +* The edges from Constants to Start are shown in dotted lines as these are not true control edges +* We label each edge with its position in the node's list of inputs. + + +## Post-peephole + +![Example Visual](./02-post-peephole-ex1.svg) + + +## Demonstration +To demonstrate how the optimisation works, let's consider the following code: +``` +return 1+2; +``` +This is parsed as: +```java + var lhs = parseMultiplication(); + if (match("+")) return new AddNode(lhs, parseAddition()).peephole(); +``` +When the peephole is called on the AddNode node it first calls the compute function: +```java + public final Node peephole( ) { + // Compute initial or improved Type + Type type = _type = compute(); +``` +```java + 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 Type.BOTTOM; + } +``` +In our case both of the operands(`1`, `2`) are constants, and instance of +`TypeInteger`. +Since `compute` returns a type, and we know that both of our operands are constants, we can do +constant propagation/folding where we compute the result of the expression so that instead of having `1+2` we can +have `3`. + +The 'TypeInteger' interface inherits from type but also has a field that stores the value observed for that type. +```java + private final long _con +``` + +AddNode has the layout: + +![Example Visual](./02-demonstration-pre-peephole.svg) + +Since, we already know the value of both of the operands, we can just add them together and replace the +old node with a constant node that just holds the result of the expression. + +To do this - we have to recognize this happens when the type computed for the node is already a constant, but the node +is still not an instance of constant node. + +This can be captured by: +```java +// Replace constant computations from non-constants with a constant node +if (!(this instanceof ConstantNode) && type.isConstant()) { +} +``` +Note how we return a constant type when doing constant folding +```java +return TypeInteger.constant(i0.value()+i1.value()); +``` +We can create a constant node in the following way: +```java +return new ConstantNode(type).peephole(); +``` +This recursively calls the peephole algorithm. +Now, we end up with this: + +![Example Visual](./02-demonstration-pre-peephole-nokill.svg) + +Notice, how we added the constant node holding a constant value of `3`. +The remaining add node is unused and can be killed. + +We can call the kill function before this way: +```java +// Replace constant computations from non-constants with a constant node +if (!(this instanceof ConstantNode) && type.isConstant()) { + kill(); // Kill `this` because replacing with a Constant + return new ConstantNode(type).peephole(); +``` +This is responsible for deleting the dangling add node. + +```java +public void kill( ) { + assert isUnused(); // Has no uses, so it is dead + for( int i=0; i⊤:int>, fillcolor=lightblue, shape=oval]; + INT_BOT [label=<⊥:int>, fillcolor=lightblue, shape=oval]; + + INT_MIN [label="-n" , fillcolor=lightblue]; + INT_MINDOTS [label="...", fillcolor=lightblue shape=oval]; + INT_MINUS [label="-1" , fillcolor=lightblue]; + INT_ZERO [label="0" , fillcolor=lightblue]; + INT_PLUS [label="1" , fillcolor=lightblue]; + INT_MAXDOTS [label="...", fillcolor=lightblue, shape=oval]; + INT_MAX [label="+n" , fillcolor=lightblue]; + + INT_TOP -> INT_MIN; + INT_TOP -> INT_MINDOTS; + INT_TOP -> INT_MINUS; + INT_TOP -> INT_ZERO; + INT_TOP -> INT_PLUS; + INT_TOP -> INT_MAXDOTS; + INT_TOP -> INT_MAX; + INT_MIN -> INT_BOT; + INT_MINDOTS -> INT_BOT; + INT_MINUS -> INT_BOT; + INT_ZERO -> INT_BOT; + INT_PLUS -> INT_BOT; + INT_MAXDOTS -> INT_BOT; + INT_MAX -> INT_BOT; + + INT_MIN -> INT_MINDOTS -> INT_MINUS -> INT_ZERO -> INT_PLUS -> INT_MAXDOTS -> INT_MAX [style=invis]; + + // Additional customization + {rank=same; INT_MIN; INT_MINDOTS; INT_MINUS; INT_ZERO; INT_PLUS; INT_MAXDOTS; INT_MAX; } +} diff --git a/docs/chapter02/lattice.svg b/docs/chapter02/lattice.svg new file mode 100644 index 00000000..b11d57aa --- /dev/null +++ b/docs/chapter02/lattice.svg @@ -0,0 +1,159 @@ + + + + + + +Lattice + + + +INT_TOP + +⊤ +:int + + + +INT_MIN + +-n + + + +INT_TOP->INT_MIN + + + + + +INT_MINDOTS + +... + + + +INT_TOP->INT_MINDOTS + + + + + +INT_MINUS + +-1 + + + +INT_TOP->INT_MINUS + + + + + +INT_ZERO + +0 + + + +INT_TOP->INT_ZERO + + + + + +INT_PLUS + +1 + + + +INT_TOP->INT_PLUS + + + + + +INT_MAXDOTS + +... + + + +INT_TOP->INT_MAXDOTS + + + + + +INT_MAX + ++n + + + +INT_TOP->INT_MAX + + + + + +INT_BOT + +⊥ +:int + + + +INT_MIN->INT_BOT + + + + + + +INT_MINDOTS->INT_BOT + + + + + + +INT_MINUS->INT_BOT + + + + + + +INT_ZERO->INT_BOT + + + + + + +INT_PLUS->INT_BOT + + + + + + +INT_MAXDOTS->INT_BOT + + + + + + +INT_MAX->INT_BOT + + + + + diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index c2ea3734..f59b0f25 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -1,6 +1,9 @@ package com.seaofnodes.simple; +import com.seaofnodes.graph.GraphObserver; + import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; /** * The Parser converts a Simple source program to the Sea of Nodes intermediate @@ -11,6 +14,9 @@ import com.seaofnodes.simple.node.*; */ public class Parser { + // Current compilation context; the observer belongs to the parser. + public static Parser PARSER; + public GraphObserver _obs; public int pos() { return _lexer._position; } @@ -29,10 +35,13 @@ public class Parser { public Parser(String source) { _lexer = new Lexer(source); + PARSER = this; Node.reset(); START = new StartNode(); } + String src() { return new String( _lexer._input ); } + public ReturnNode parse() { var ret = (ReturnNode) parseStatement(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); @@ -60,20 +69,61 @@ public class Parser { * * @return an expression {@link Node}, never {@code null} */ - private ReturnNode parseReturn() { + private Node parseReturn() { var expr = require(parseExpression(), ";"); - return new ReturnNode(START, expr); + return new ReturnNode(START, expr).peephole(); } /** * Parse an expression of the form: * * 
-     *     expr : primaryExpr
+     *     expr : additiveExpr
      *
* @return an expression {@link Node}, never {@code null} */ - private Node parseExpression() { + private Node parseExpression() { return parseAddition(); } + + /** + * Parse an additive expression + * + * 
+     *     additiveExpr : multiplicativeExpr (('+' | '-') multiplicativeExpr)*
+     *
+ * @return an add expression {@link Node}, never {@code null} + */ + 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 + * + * 
+     *     multiplicativeExpr : unaryExpr (('*' | '/') unaryExpr)*
+     *
+ * @return a multiply expression {@link Node}, never {@code null} + */ + 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. + * + * 
+     *     unaryExpr : ('-') unaryExpr | primaryExpr
+     *
+ * @return a unary expression {@link Node}, never {@code null} + */ + private Node parseUnary() { + if (match("-")) return new MinusNode(parseUnary()).peephole(); return parsePrimary(); } @@ -81,14 +131,14 @@ public class Parser { * Parse a primary expression: * * 
-     *     primaryExpr : integerLiteral
+     *     primaryExpr : integerLiteral | Identifier | '(' expression ')'
      *
+ * @return a primary {@link Node}, never {@code null} */ private Node parsePrimary() { - _lexer.skipWhiteSpace(); - if (_lexer.isNumber()) - return parseIntegerLiteral(); - throw error("Syntax error, expected integer literal"); + if( _lexer.isNumber() ) return parseIntegerLiteral(); + if( match("(") ) return require(parseExpression(), ")"); + throw errorSyntax("integer literal"); } /** @@ -99,7 +149,7 @@ public class Parser { * */ private ConstantNode parseIntegerLiteral() { - return new ConstantNode(_lexer.parseNumber()); + return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole(); } ////////////////////////////////// @@ -149,6 +199,12 @@ public class Parser { _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; @@ -212,11 +268,11 @@ public class Parser { boolean isNumber() {return isNumber(peek());} boolean isNumber(char ch) {return Character.isDigit(ch);} - private long parseNumber() { + private Type parseNumber() { String snum = parseNumberString(); if (snum.length() > 1 && snum.charAt(0) == '0') throw error("Syntax error: integer values cannot start with '0'"); - return Long.parseLong(snum); + return TypeInteger.constant(Long.parseLong(snum)); } private String parseNumberString() { int start = _position; @@ -249,5 +305,4 @@ public class Parser { return new String(_input, start, 1); } } - } diff --git a/src/main/java/com/seaofnodes/simple/Utils.java b/src/main/java/com/seaofnodes/simple/Utils.java new file mode 100644 index 00000000..45f15327 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/Utils.java @@ -0,0 +1,39 @@ +package com.seaofnodes.simple; + +import java.util.ArrayList; + +public class Utils { + public static RuntimeException TODO() { return TODO("Not yet implemented"); } + public static RuntimeException TODO(String msg) { return new RuntimeException(msg); } + + /** + * Fast, constant-time, element removal. Does not preserve order + * + * @param array ArrayList to modify + * @param i element to be removed + * @return element removed + */ + public static E del(ArrayList array, int i) { + if ( i >= 0 && i < array.size() ) { + E tmp = array.get(i); + E last = array.removeLast(); + if (i < array.size()) array.set(i, last); + return tmp; + } + return null; + } + + /** + * Search a list for an element by reference + * + * @param ary List to search in + * @param x Object to be searched + * @return >= 0 on success, -1 on failure + */ + public static int find( ArrayList ary, E x ) { + for( int i=0; i _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. @@ -50,8 +62,49 @@ public abstract class Node { _outputs = new ArrayList<>(); for( Node n : _inputs ) if( n != null ) - n._outputs.add( this ); + n.addUse( this ); + } + + // Easy reading label for debugger, e.g. "Add" or "Region" or "EQ" + public abstract String label(); + + // Unique label for debugging, e.g. "Add12" or "Region30" or "EQ99" + public String uniqueName() { return label() + _nid; } + + // ------------------------------------------------------------------------ + + // Debugger Printing. + + // {@code toString} is what you get in the debugger. It has to print 1 + // line (because this is what a debugger typically displays by default) and + // has to be robust with broken graph/nodes. + @Override + public final String toString() { + // TODO: The print evolves in later chapters. For now, a simple + // recursive print does well. Later with control flow and later still + // with loops, we need some serious algorithm work to get a decent + // print. So you should consider the "print" to always be a work-in- + // progress as we march through the chapters. + 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 @@ -62,6 +115,8 @@ public abstract class Node { public int nIns() { return _inputs.size(); } + public Node out(int i) { return _outputs.get(i); } + public int nOuts() { return _outputs.size(); } public boolean isUnused() { return nOuts() == 0; } @@ -69,6 +124,120 @@ public abstract class Node { public boolean isCFG() { return false; } + /** + * Change a def into a Node. Keeps the edges correct, by removing + * the corresponding use->def edge. This may make the original + * def go dead. This function is co-recursive with {@link #kill}. + * + * @param idx which def to set + * @param new_def the new definition + * @return new_def for flow coding + */ + Node setDef(int idx, Node new_def ) { + Node old_def = in(idx); + if( old_def == new_def ) return this; // No change + // If new def is not null, add the corresponding def->use edge + // This needs to happen before removing the old node's def->use edge as + // the new_def might get killed if the old node kills it recursively. + if( new_def != null ) + new_def.addUse(this); + if( old_def != null && // If the old def exists, remove a def->use 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); + // Return self for easy flow-coding + return new_def; + } + + // Breaks the edge invariants, used temporarily + protected void addUse(N 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. + protected boolean delUse( Node use ) { + Utils.del(_outputs, Utils.find(_outputs, use)); + return _outputs.size() == 0; + } + + /** + * Kill a Node with no uses, by setting all of its defs + * to null. This may recursively kill more Nodes and is basically dead + * code elimination. This function is co-recursive with {@link #setDef}. + */ + public void kill( ) { + assert isUnused(); // Has no uses, so it is dead + for( int i=0; i + *
  • if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}
    • + *
  • in a future chapter we will look for a + * Common Subexpression + * to eliminate.
    • + *
  • we ask the Node for a better replacement (again, none enabled in this chapter)
    • + * + */ + public final Node peephole() { + var obs = Parser.PARSER == null ? null : Parser.PARSER._obs; + if( obs != null ) obs.before(this); + Type old = _type; + Node n = peepholeOpt(); + Node rez = n == null ? this : n; + if( obs != null ) obs.after(this, n == null && old == _type ? null : rez, false); + return rez; + } + + private Node peepholeOpt() { + // 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()) { + kill(); // Kill `this` because replacing with a Constant + return new ConstantNode(type).peephole(); + } + + // Future chapter: Global Value Numbering goes here + + // Ask each node for a better replacement + Node n = idealize(); + if( n != null ) return n; + + return null; // No progress + } + + + /** + * This function needs to be + * Monotonic + * as it is part of a Monotone Analysis Framework. + * See for example this set of slides. + *

    + * 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. + *

    + * compute() needs to be stand-alone, and cannot recursively call compute + * on its inputs programs are cyclic (have loops!) and this will just + * infinitely recurse until stack overflow. Instead, compute typically + * computes a new type from the {@link #_type} field of its inputs. + */ + public abstract Type compute(); + + public abstract Node idealize(); + /** * Used to allow repeating tests in the same JVM. This just resets the * Node unique id generator, and is done as part of making a new Parser. diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 85bbc83f..7fa470f8 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.type.*; + /** * 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. @@ -18,6 +20,21 @@ public class ReturnNode extends Node { 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 boolean isCFG() { return true; } + @Override + public Type compute() { + return Type.BOTTOM; + } + + @Override + public Node idealize() { return null; } } diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index 04bd6bb4..99e240ad 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -1,9 +1,13 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.type.Type; + /** - * 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. + * The Start node represents the start of the function. For now, we do not + * have any inputs to Start because our function does not yet accept + * parameters. When we add parameters the value of Start will be a tuple, and + * will require Projections to extract the values. We discuss this in detail + * in Chapter 9: Functions and Calls. */ public class StartNode extends Node { @@ -11,6 +15,19 @@ public class StartNode extends Node { super(); } + @Override + public String label() { return "Start"; } + + @Override + StringBuilder _print1(StringBuilder sb) { + return sb.append(label()); + } + @Override public boolean isCFG() { return true; } + @Override + public Type compute() { return Type.BOTTOM; } + + @Override + public Node idealize() { return null; } } diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java new file mode 100644 index 00000000..1d2ddaa0 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -0,0 +1,31 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +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 Type.BOTTOM; + } + + @Override + public Node idealize() { return null; } + +} diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index 59275832..502a2a8e 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -7,14 +7,14 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.Node; import java.util.ArrayList; -/** Chapter 1's view of the IR; browser, transport and layout are shared. */ +/** Chapter 2's view of the IR; browser, transport and layout are shared. */ public class SimpleGraphAdapter extends GraphAdapter { - @Override protected boolean dead(Node n) { return false; } + @Override protected boolean dead(Node n) { return n.isDead(); } @Override protected int id(Node n) { return n._nid; } @Override protected int nIns(Node n) { return n.nIns(); } @Override protected Node in(Node n, int idx) { return n.in(idx); } @Override protected int nOuts(Node n) { return n.nOuts(); } - @Override protected Node out(Node n, int idx) { return n._outputs.get(idx); } + @Override protected Node out(Node n, int idx) { return n.out(idx); } private ArrayList edges(Node n) { var edges = new ArrayList(); @@ -27,9 +27,9 @@ public class SimpleGraphAdapter extends GraphAdapter { @Override protected GraphSnapshot.Node desc(Node n) { Projection proj = null; - String label = n instanceof ConstantNode c ? Long.toString(c._value) : n.getClass().getSimpleName(); + String label = n.label(); return new GraphSnapshot.Node(n._nid, label == null ? n.getClass().getSimpleName() : label, - null, kind(n), edges(n), proj); + n._type == null ? null : n._type.toString(), kind(n), edges(n), proj); } private Kind kind(Node n) { diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index 1c78e4dd..a17bf796 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.io.IOException; -/** Chapter 1's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 2's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture { private Parser _parser; private Node _ret; @@ -18,6 +18,7 @@ public class SimpleGraphObserver extends GraphCapture { } @Override protected void compile(String src) { _parser = new Parser(src); + _parser._obs = this; _phase = "Parse"; _ret = _parser.parse(); phase(_phase); @@ -25,6 +26,7 @@ public class SimpleGraphObserver extends GraphCapture { @Override protected String phase() { return _phase; } @Override protected int pos() { return "Parse".equals(_phase) ? _parser.pos() : -1; } @Override protected void detach() { + if( _parser != null ) _parser._obs = null; _parser = null; _ret = null; } diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java new file mode 100644 index 00000000..7ea17bfb --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -0,0 +1,40 @@ +package com.seaofnodes.simple.type; + + +/** + * These types are part of a Monotone Analysis Framework, + * @see see for example this set of slides. + *

    + * The types form a lattice; @see a symmetric complete bounded (ranked) lattice. + *

    + * 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. + *

    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 class Type { + + // ---------------------------------------------------------- + // Simple types are implemented fully here. "Simple" means: the code and + // type hierarchy are simple, not that the Type is conceptually simple. + static final byte TBOT = 0; // Bottom (ALL) + static final byte TTOP = 1; // Top (ANY) + static final byte TSIMPLE = 2; // End of the Simple Types + static final byte TINT = 3; // All Integers; see TypeInteger + public final byte _type; + + public boolean is_simple() { return _type < TSIMPLE; } + private static final String[] STRS = new String[]{"Bot","Top"}; + protected Type(byte type) { _type = type; } + + public static final Type BOTTOM = new Type( TBOT ); // ALL + + public boolean isConstant() { return _type == TTOP; } + + public StringBuilder print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;} +} diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java new file mode 100644 index 00000000..e0324da5 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -0,0 +1,41 @@ +package com.seaofnodes.simple.type; + +/** + * Integer Type + */ +public class TypeInteger extends Type { + + public final static TypeInteger ZERO= new TypeInteger(0); + + /** + * The constant value observed for this type + */ + private final long _con; + + public TypeInteger(long con) { + super(TINT); + _con = con; + } + + public static TypeInteger constant(long con) { return new TypeInteger(con); } + + @Override + public String toString() { + return print(new StringBuilder()).toString(); + } + + @Override + public StringBuilder print(StringBuilder sb) { return sb.append(_con); } + + @Override + public boolean isConstant() { return true; } + + public long value() { return _con; } + + @Override + public boolean equals( Object o ) { + if( o==this ) return true; + if( !(o instanceof TypeInteger i) ) return false; + return _con==i._con; + } +} diff --git a/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/src/test/java/com/seaofnodes/simple/Chapter01Test.java index a91aabb1..49edfb5b 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; import org.junit.Test; import static org.junit.Assert.*; @@ -17,7 +18,7 @@ public class Chapter01Test { Node expr = ret.expr(); if( expr instanceof ConstantNode con ) { assertEquals(start,con.in(0)); - assertEquals(1, con._value); + assertEquals(TypeInteger.constant(1), con._type); } else { fail(); } @@ -30,7 +31,7 @@ public class Chapter01Test { StartNode start = Parser.START; for( Node use : start._outputs ) if( use instanceof ConstantNode con ) - assertEquals(0,con._value); + assertEquals(TypeInteger.constant(0),con._type); } @Test @@ -54,13 +55,9 @@ public class Chapter01Test { } @Test - public void testBad3() { - try { - new Parser("return --12;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected integer literal",e.getMessage()); - } + public void testNotBad3() { + // this test used to fail in chapter 1 + assertEquals("return 12;", new Parser("return --12;").parse().print()); } @Test @@ -73,15 +70,10 @@ public class Chapter01Test { } } - // Negative numbers require unary operator support that is not in scope @Test - public void testBad5() { - try { - new Parser("return -100;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected integer literal",e.getMessage()); - } + public void testNotBad5() { + // this test used to fail in chapter 1 + assertEquals("return -100;", new Parser("return -100;").parse().print()); } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/src/test/java/com/seaofnodes/simple/Chapter02Test.java new file mode 100644 index 00000000..6c816a23 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -0,0 +1,60 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter02Test { + + @Test + public void testParseGrammar() { + Parser parser = new Parser("return 1+2*3+-5;"); + ReturnNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + } + + @Test + public void testAddPeephole() { + Parser parser = new Parser("return 1+2;"); + ReturnNode ret = parser.parse(); + assertEquals("return 3;", ret.print()); + } + + @Test + public void testSubPeephole() { + Parser parser = new Parser("return 1-2;"); + ReturnNode ret = parser.parse(); + assertEquals("return -1;", ret.print()); + } + + @Test + public void testMulPeephole() { + Parser parser = new Parser("return 2*3;"); + ReturnNode ret = parser.parse(); + assertEquals("return 6;", ret.print()); + } + + @Test + public void testDivPeephole() { + Parser parser = new Parser("return 6/3;"); + ReturnNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + } + + @Test + public void testMinusPeephole() { + Parser parser = new Parser("return 6/-3;"); + ReturnNode ret = parser.parse(); + assertEquals("return -2;", ret.print()); + } + + @Test + public void testExample() { + Parser parser = new Parser("return 1+2*3+-5;"); + ReturnNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + } + +} -- cgit v1.2.3