diff options
Diffstat (limited to 'chapter03')
19 files changed, 85 insertions, 85 deletions
diff --git a/chapter03/README.md b/chapter03/README.md index 9b4898ff..7b0d22cb 100644 --- a/chapter03/README.md +++ b/chapter03/README.md @@ -3,13 +3,13 @@ In this chapter we extend the language grammar to allow variable declarations. This allows us to write: ``` -int a=1; -int b=2; -int c=0; -{ - int b=3; - c=a+b; -} +int a=1; +int b=2; +int c=0; +{ + int b=3; + c=a+b; +} return c; ``` @@ -45,7 +45,7 @@ We maintain a stack of symbol tables. When a new scope is created, we push a new symbol table to the stack, when scope exits, the topmost symbol table is popped from the stack. -Declaring a name adds it to the current symbol table. +Declaring a name adds it to the current symbol table. If a name is assigned to, then its mapping in the most recent symbol table is updated. If a name is accessed, its mapping is looked up in the symbol tables. The lookup goes up the stack of symbol tables. @@ -53,7 +53,7 @@ If a name is accessed, its mapping is looked up in the symbol tables. The lookup We wrap the stack of symbol tables in a `ScopeNode`. When a name binding is added to a symbol table, we also make the newly added node an input in the `ScopeNode`. This means that the `ScopeNode` is a user of -all nodes that define new names. +all nodes that define new names. From an implementation point of view, the symbol table maps names to offsets in the ScopeNode's inputs. @@ -67,13 +67,13 @@ the box. We show the edge from each variable in the symbol table to the defining We show the output from following code. ``` -01 int a=1; -02 int b=2; -03 int c=0; -04 { -05 int b=3; -07 c=a+b; -08 } +01 int a=1; +02 int b=2; +03 int c=0; +04 { +05 int b=3; +07 c=a+b; +08 } 09 return c; ``` @@ -83,12 +83,12 @@ The variables `a`, `b`, and `c` are registered in this table. * On line 5, a variable `b` is declared. `b` is registered in the symbol table at level 1. This then hides the variable with the same name on line 2. * On line 7, we update the variable `c`. Variable lookup will find it in the symbol table at level 0. -The node graph is shown below (note that peephole opts are switched off here so that we can +The node graph is shown below (note that peephole opts are switched off here so that we can see the graph as its initially constructed).  -The diagram shows the ScopeNode and the symbol tables in the bottom cluster. +The diagram shows the ScopeNode and the symbol tables in the bottom cluster. Each table is annotated by its scope level, and shows the variables defined in that scope. * When we exit the nested scope on line 8, the symbol table at level 1 is popped. @@ -104,10 +104,10 @@ Once we enable peephole optimizations, the parser is able to reduce all the expr constant. This is illustrated nicely below. ``` -01 int x0=1; -02 int y0=2; -03 int x1=3; -04 int y1=4; +01 int x0=1; +02 int y0=2; +03 int x1=3; +04 int y1=4; 05 return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); ``` @@ -115,4 +115,4 @@ The graph for above, is displayed below.  -The return node has the constant `8` as its data value!
\ No newline at end of file +The return node has the constant `8` as its data value! diff --git a/chapter03/docs/03-grammar.md b/chapter03/docs/03-grammar.md index 2a6d4c1b..14a7d5fa 100644 --- a/chapter03/docs/03-grammar.md +++ b/chapter03/docs/03-grammar.md @@ -10,7 +10,7 @@ program statement : returnStatement | declStatement - | blockStatment + | blockStatment | expressionStatement | metaStatement ; @@ -38,11 +38,11 @@ returnStatement expression : additiveExpression ; - + additiveExpression - : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* ; - + multiplicativeExpression : unaryExpression (('*' | '/') unaryExpression)* ; @@ -62,11 +62,11 @@ 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/chapter03/docs/03-graph2.gv b/chapter03/docs/03-graph2.gv index f570b13e..460b63c8 100644 --- a/chapter03/docs/03-graph2.gv +++ b/chapter03/docs/03-graph2.gv @@ -32,4 +32,4 @@ int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph; Scope1_0:"Scope1_0_a" -> Con_3; Scope1_0:"Scope1_0_b" -> Con_4; Scope1_0:"Scope1_0_c" -> Add7; -}
\ No newline at end of file +} diff --git a/chapter03/pom.xml b/chapter03/pom.xml index a484d5bd..2b977285 100644 --- a/chapter03/pom.xml +++ b/chapter03/pom.xml @@ -11,4 +11,4 @@ <artifactId>chapter03</artifactId> <packaging>jar</packaging> <name>Chapter 3</name> -</project>
\ No newline at end of file +</project> diff --git a/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index a85a670e..9dfac52d 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -21,7 +21,7 @@ public class GraphVisualizer { 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 @@ -35,10 +35,10 @@ public class GraphVisualizer { // Merge multiple edges hitting the same node. Makes common shared // nodes much prettier to look at. sb.append("\tconcentrate=\"true\";\n"); - + // Just the Nodes first, in a cluster no edges nodes(sb, all); - + // Now the scopes, in a cluster no edges scopes(sb, parser._scope); @@ -47,7 +47,7 @@ public class GraphVisualizer { // Walk the Scope edges scopeEdges(sb, parser._scope); - + sb.append("}\n"); return sb.toString(); } @@ -124,7 +124,7 @@ public class GraphVisualizer { } } } - + // Walk the scope edges private void scopeEdges( StringBuilder sb, ScopeNode scopenode ) { sb.append("\tedge [style=dashed color=cornflowerblue];\n"); @@ -144,7 +144,7 @@ public class GraphVisualizer { level++; } } - + /** * Finds all nodes in the graph. */ diff --git a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java index 60761f04..9c7ebaca 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java @@ -352,7 +352,7 @@ public class Parser { skipWhiteSpace(); return peek()==ch; } - + // Return an identifier or null String matchId() { skipWhiteSpace(); @@ -379,7 +379,7 @@ public class Parser { return TypeInteger.constant(Long.parseLong(snum)); } - // First letter of an identifier + // First letter of an identifier private boolean isIdStart(char ch) { return Character.isAlphabetic(ch) || ch == '_'; } @@ -395,7 +395,7 @@ public class Parser { return new String(_input, start, --_position - start); } - // + // private boolean isPunctuation(char ch) { return "=;[]<>()+-/*".indexOf(ch) != -1; } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/Utils.java b/chapter03/src/main/java/com/seaofnodes/simple/Utils.java index 4d663c25..45f15327 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/Utils.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/Utils.java @@ -36,4 +36,4 @@ public class Utils { return i; return -1; } -}
\ No newline at end of file +} diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java index a0376dd4..2d58cb75 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -6,7 +6,7 @@ public class AddNode extends Node { public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); } @Override public String label() { return "Add"; } - + @Override public String glabel() { return "+"; } @Override @@ -15,7 +15,7 @@ public class AddNode extends Node { in(2)._print0(sb.append("+")); return sb.append(")"); } - + @Override public Type compute() { @@ -32,5 +32,5 @@ public class AddNode extends Node { // TODO: add of 0 return null; } - + } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index ec85bf1f..e4d7f412 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -21,10 +21,10 @@ public class ConstantNode extends Node { super(Parser.START); _con = type; } - + @Override public String label() { return "#"+_con; } - + @Override public String uniqueName() { return "Con_" + _nid; } @@ -32,11 +32,11 @@ public class ConstantNode extends Node { StringBuilder _print1(StringBuilder sb) { return _con._print(sb); } - + @Override public Type compute() { return _con; } @Override public Node idealize() { return null; } - + } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java index 4f502e5f..e3c3616a 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -16,7 +16,7 @@ public class DivNode extends Node { in(2)._print0(sb.append("/")); return sb.append(")"); } - + @Override public Type compute() { if (in(1)._type instanceof TypeInteger i0 && diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 08924563..0d59ef25 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -7,15 +7,15 @@ public class MinusNode extends Node { public MinusNode(Node in) { super(null, in); } @Override public String label() { return "Minus"; } - + @Override public String glabel() { return "-"; } - + @Override StringBuilder _print1(StringBuilder sb) { in(1)._print0(sb.append("(-")); return sb.append(")"); } - + @Override public Type compute() { if (in(1)._type instanceof TypeInteger i0) diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java index c6718d27..26c28281 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -7,7 +7,7 @@ public class MulNode extends Node { public MulNode(Node lhs, Node rhs) { super(null, lhs, rhs); } @Override public String label() { return "Mul"; } - + @Override public String glabel() { return "*"; } @Override diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java index 91bde29d..504b8e24 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java @@ -74,9 +74,9 @@ public abstract class Node { // ------------------------------------------------------------------------ - + // 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. @@ -103,7 +103,7 @@ public abstract class Node { // Every Node implements this. abstract StringBuilder _print1(StringBuilder sb); - + /** * Gets the ith input node * @param i Offset of the input node @@ -120,21 +120,21 @@ public abstract class Node { public boolean isUnused() { return nOuts() == 0; } public boolean isCFG() { return false; } - - + + /** * 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 new_def for flow coding @@ -193,7 +193,7 @@ public abstract class Node { old_def.kill(); // Kill old def } } - + /** * 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 @@ -228,7 +228,7 @@ public abstract class Node { public final Node peephole( ) { // Compute initial or improved Type Type type = _type = compute(); - + if (_disablePeephole) return this; // Peephole optimizations turned off @@ -239,14 +239,14 @@ public abstract class Node { } // Future chapter: Global Value Numbering goes here - + // Ask each node for a better replacement Node n = idealize(); if( n != null ) return n; - + return this; // No progress } - + /** * This function needs to be * <a href="https://en.wikipedia.org/wiki/Monotonic_function">Monotonic</a> diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index a0f2e931..7fa470f8 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -19,7 +19,7 @@ public class ReturnNode extends Node { public Node ctrl() { return in(0); } public Node expr() { return in(1); } - + @Override public String label() { return "Return"; } @@ -29,7 +29,7 @@ public class ReturnNode extends Node { } @Override public boolean isCFG() { return true; } - + @Override public Type compute() { return Type.BOTTOM; diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 7b42a2d0..e9ff0f44 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -21,8 +21,8 @@ public class ScopeNode extends Node { _scopes = new Stack<>(); _type = Type.BOTTOM; } - - + + @Override public String label() { return "Scope"; } @Override @@ -58,7 +58,7 @@ public class ScopeNode extends Node { names[syms.get(name)] = name; return names; } - + @Override public Type compute() { return Type.BOTTOM; } @Override public Node idealize() { return null; } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java index 6eda4f11..d2e32c61 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -16,7 +16,7 @@ public class SubNode extends Node { in(2)._print0(sb.append("-")); return sb.append(")"); } - + @Override public Type compute() { if (in(1)._type instanceof TypeInteger i0 && diff --git a/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java index 5bd51611..89f6c715 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java @@ -4,7 +4,7 @@ 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> + * <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 @@ -15,7 +15,7 @@ package com.seaofnodes.simple.type; * 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 { diff --git a/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 69fb811c..13f816bf 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -6,16 +6,16 @@ package com.seaofnodes.simple.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 TypeInteger(long con) { + super(TINT); + _con = con; + } public static TypeInteger constant(long con) { return new TypeInteger(con); } @@ -24,7 +24,7 @@ public class TypeInteger extends Type { return _print(new StringBuilder()).toString(); } - @Override + @Override public StringBuilder _print(StringBuilder sb) { return sb.append(_con); } @Override diff --git a/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java index 5847fed4..965a100a 100644 --- a/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -52,7 +52,7 @@ public class Chapter03Test { @Test public void testSelfAssign() { - try { + try { new Parser("int a=a; return a;").parse(); fail(); } catch( RuntimeException e ) { @@ -120,7 +120,7 @@ public class Chapter03Test { Parser parser = new Parser("return 1;"); ReturnNode ret = parser.parse(); StartNode start = Parser.START; - + assertEquals(start, ret.ctrl()); Node expr = ret.expr(); if( expr instanceof ConstantNode con ) { @@ -143,7 +143,7 @@ public class Chapter03Test { @Test public void testBad1() { - try { + try { new Parser("ret").parse(); fail(); } catch( RuntimeException e ) { @@ -153,7 +153,7 @@ public class Chapter03Test { @Test public void testBad2() { - try { + try { new Parser("return 0123;").parse(); fail(); } catch( RuntimeException e ) { @@ -169,7 +169,7 @@ public class Chapter03Test { @Test public void testBad4() { - try { + try { new Parser("return 100").parse(); fail(); } catch( RuntimeException e ) { |