diff options
Diffstat (limited to 'chapter05')
9 files changed, 78 insertions, 55 deletions
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index b7e561e1..79d98792 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -122,7 +122,7 @@ public class GraphVisualizer { sb.append( "\t}\n".repeat( level ) ); // End all Scope clusters } - private String makeScopeName(ScopeNode sn, int level) { return sn.label() + "_" + level; } + private String makeScopeName(ScopeNode sn, int level) { return sn.uniqueName() + "_" + level; } private String makePortName(String scopeName, String varName) { return scopeName + "_" + varName; } // Walk the node edges diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java index 4225e67b..3e832610 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java @@ -29,6 +29,9 @@ public class Parser { */ public static StartNode START; + public StopNode STOP; + + // The Lexer. Thin wrapper over a byte[] buffer with a cursor. private final Lexer _lexer; /** @@ -57,6 +60,7 @@ public class Parser { _scope = new ScopeNode(); START = new StartNode(new Type[]{ Type.CONTROL, arg }); START.peephole(); + STOP = new StopNode(); } public Parser(String source) { @@ -69,13 +73,14 @@ public class Parser { private Node ctrl(Node n) { return _scope.ctrl(n); } - public ReturnNode parse() { + public StopNode parse() { _allScopes.push(_scope); _scope.push(); try { _scope.define(CTRL , new ProjNode(START, 0, CTRL ).peephole()); _scope.define("arg", new ProjNode(START, 1, "arg").peephole()); - return (ReturnNode) parseBlock(); + parseBlock(); + return STOP; } finally { _scope.pop(); @@ -164,7 +169,7 @@ public class Parser { */ private Node parseReturn() { var expr = require(parseExpression(), ";"); - Node ret = new ReturnNode(ctrl(), expr); + Node ret = STOP.add_def(new ReturnNode(ctrl(), expr).peephole()); ctrl(null); // Kill control return ret; } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java index 382d41ae..49426c26 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java @@ -206,7 +206,7 @@ public abstract class Node { * @param new_def the new definition, appended to the end of existing definitions * @return new_def for flow coding */ - Node add_def(Node new_def) { + public Node add_def(Node new_def) { // Add use->def edge _inputs.add(new_def); // If new def is not null, add the corresponding def->use edge diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java index c9b1ec07..8e223e93 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -22,7 +22,7 @@ public class ProjNode extends Node { public String label() { return _label; } @Override - StringBuilder _print1(StringBuilder sb) { return sb.append(_label).append(_nid); } + StringBuilder _print1(StringBuilder sb) { return sb.append(_label); } @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 681bd175..e20d01e5 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeBot; +import com.seaofnodes.simple.type.*; /** * The Return node has two inputs. The first input is a control node and the @@ -33,7 +32,7 @@ public class ReturnNode extends Node { @Override public Type compute() { - return expr().compute(); + return new TypeTuple(TypeControl.CONTROL,expr()._type); } @Override diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index f09eeef5..b3cca3da 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -105,7 +105,7 @@ public class ScopeNode extends Node { public ScopeNode dup() { ScopeNode dup = new ScopeNode(); for( HashMap<String, Integer> tab : _scopes ) - dup._scopes.push((HashMap<String, Integer>) tab.clone()); + dup._scopes.push(new HashMap<String, Integer>(tab)); for( int i=0; i<nIns(); i++ ) dup.add_def(in(i)); return dup; diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java index b0c851a2..df5e09ef 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -15,10 +15,20 @@ public class StopNode extends Node { @Override StringBuilder _print1(StringBuilder sb) { - return sb; + if( ret()!=null ) return ret()._print0(sb); + sb.append("Stop[ "); + for( Node ret : _inputs ) + ret._print0(sb).append(" "); + return sb.append("]"); } @Override public boolean isCFG() { return true; } + + // If a single Return, return it. + // Otherwise, null because ambiguous. + public ReturnNode ret() { + return nIns()==1 ? (ReturnNode)in(0) : null; + } @Override public Type compute() { diff --git a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index 4d7a79bc..80d09884 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -4,7 +4,7 @@ public class TypeTuple extends Type { public final Type[] _types; - public TypeTuple(Type[] _types) { + public TypeTuple(Type... _types) { this._types = _types; } diff --git a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 496b3ff5..e59d1dbd 100644 --- a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -23,8 +23,8 @@ else { return a; #showGraph; """); - ReturnNode ret = parser.parse(); - assertEquals("return Phi(Region16,(arg4+2),(arg4-3));", ret.toString()); + StopNode ret = parser.parse(); + assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString()); } @Test @@ -38,22 +38,29 @@ if (arg == 1) { } return c; """, TypeInteger.BOT); - ReturnNode ret = parser.parse(); - assertEquals("return Phi(Region15,4,3);", ret.toString()); + StopNode ret = parser.parse(); + assertEquals("return Phi(Region16,4,3);", ret.toString()); + } + + @Test + public void testChapter5Return2() { + Parser parser = new Parser("if( arg==1 ) return 3; else return 4; #showGraph;", TypeInteger.BOT); + StopNode stop = parser.parse(); + assertEquals("Stop[ return 3; return 4; ]", stop.toString()); } @Test public void testChapter5IfMergeB() { Parser parser = new Parser("int a=arg+1; int b=0; if( arg==1 ) b=a; else b=a+1; return a+b; #showGraph;"); - ReturnNode ret = parser.parse(); - assertEquals("return ((arg4+1)+Phi(Region19,(arg4+1),(arg4+2)));", ret.toString()); + StopNode ret = parser.parse(); + assertEquals("return ((arg+1)+Phi(Region20,(arg+1),(arg+2)));", ret.toString()); } @Test public void testChapter5IfMerge2() { Parser parser = new Parser("int a=arg+1; int b=arg+2; if( arg==1 ) b=b+a; else a=b+1; return a+b; #showGraph;"); - ReturnNode ret = parser.parse(); - assertEquals("return (Phi(Region30,(arg4+1),(arg4+3))+Phi(Region30,((arg4*2)+3),(arg4+2)));", ret.toString()); + StopNode ret = parser.parse(); + assertEquals("return (Phi(Region31,(arg+1),(arg+3))+Phi(Region31,((arg*2)+3),(arg+2)));", ret.toString()); } @Test @@ -79,49 +86,50 @@ return c; @Test public void testChapter4Peephole() { Parser parser = new Parser("return 1+arg+2; #showGraph;"); - ReturnNode ret = parser.parse(); - assertEquals("return (arg4+3);", ret.print()); + StopNode ret = parser.parse(); + assertEquals("return (arg+3);", ret.print()); } @Test public void testChapter4Peephole2() { Parser parser = new Parser("return (1+arg)+2;"); - ReturnNode ret = parser.parse(); - assertEquals("return (arg4+3);", ret.print()); + StopNode ret = parser.parse(); + assertEquals("return (arg+3);", ret.print()); } @Test public void testChapter4Add0() { Parser parser = new Parser("return 0+arg;"); - ReturnNode ret = parser.parse(); - assertEquals("return arg4;", ret.print()); + StopNode ret = parser.parse(); + assertEquals("return arg;", ret.print()); } @Test public void testChapter4AddAddMul() { Parser parser = new Parser("return arg+0+arg;"); - ReturnNode ret = parser.parse(); - assertEquals("return (arg4*2);", ret.print()); + StopNode ret = parser.parse(); + assertEquals("return (arg*2);", ret.print()); } @Test public void testChapter4Peephole3() { Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;"); - ReturnNode ret = parser.parse(); - assertEquals("return ((arg4*2)+6);", ret.print()); + StopNode ret = parser.parse(); + assertEquals("return ((arg*2)+6);", ret.print()); } @Test public void testChapter4Mul1() { Parser parser = new Parser("return 1*arg;"); - ReturnNode ret = parser.parse(); - assertEquals("return arg4;", ret.print()); + StopNode ret = parser.parse(); + assertEquals("return arg;", ret.print()); } @Test public void testChapter4VarArg() { Parser parser = new Parser("return arg; #showGraph;"); - ReturnNode ret = parser.parse(); + StopNode stop = parser.parse(); + ReturnNode ret = stop.ret(); assertTrue(ret.in(0) instanceof ProjNode); assertTrue(ret.in(1) instanceof ProjNode); } @@ -129,70 +137,70 @@ return c; @Test public void testChapter4ConstantArg() { Parser parser = new Parser("return arg; #showGraph;", TypeInteger.constant(2)); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 2;", ret.print()); } @Test public void testChapter4CompEq() { Parser parser = new Parser("return 3==3; #showGraph;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 1;", ret.print()); } @Test public void testChapter4CompEq2() { Parser parser = new Parser("return 3==4; #showGraph;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 0;", ret.print()); } @Test public void testChapter4CompNEq() { Parser parser = new Parser("return 3!=3; #showGraph;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 0;", ret.print()); } @Test public void testChapter4CompNEq2() { Parser parser = new Parser("return 3!=4; #showGraph;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 1;", ret.print()); } @Test public void testChapter4Bug1() { Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;"); - ReturnNode ret = parser.parse(); - assertEquals("return (arg4+3);", ret.print()); + StopNode ret = parser.parse(); + assertEquals("return (arg+3);", ret.print()); } @Test public void testChapter4Bug2() { Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;"); - ReturnNode ret = parser.parse(); - assertEquals("return (arg4+1);", ret.print()); + StopNode ret = parser.parse(); + assertEquals("return (arg+1);", ret.print()); } @Test public void testVarDecl() { Parser parser = new Parser("int a=1; return a;"); - ReturnNode ret = parser.parse(); + StopNode 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(); + StopNode 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(); + StopNode ret = parser.parse(); assertEquals("return 4;", ret.print()); } @@ -200,7 +208,7 @@ return c; 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(); + StopNode ret = parser.parse(); Node._disablePeephole = false; assertEquals("return (1+3);", ret.print()); } @@ -208,7 +216,7 @@ return c; @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(); + StopNode ret = parser.parse(); assertEquals("return 8;", ret.print()); } @@ -226,7 +234,7 @@ return c; 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(); + StopNode ret = parser.parse(); assertEquals("return (1+((2*3)+(-5)));", ret.print()); GraphVisualizer gv = new GraphVisualizer(); System.out.println(gv.generateDotOutput(parser)); @@ -236,42 +244,42 @@ return c; @Test public void testChapter2AddPeephole() { Parser parser = new Parser("return 1+2;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 3;", ret.print()); } @Test public void testChapter2SubPeephole() { Parser parser = new Parser("return 1-2;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return -1;", ret.print()); } @Test public void testChapter2MulPeephole() { Parser parser = new Parser("return 2*3;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 6;", ret.print()); } @Test public void testChapter2DivPeephole() { Parser parser = new Parser("return 6/3;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 2;", ret.print()); } @Test public void testChapter2MinusPeephole() { Parser parser = new Parser("return 6/-3;"); - ReturnNode ret = parser.parse(); + StopNode 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(); + StopNode ret = parser.parse(); assertEquals("return 2;", ret.print()); GraphVisualizer gv = new GraphVisualizer(); System.out.println(gv.generateDotOutput(parser)); @@ -280,8 +288,9 @@ return c; @Test public void testSimpleProgram() { Parser parser = new Parser("return 1;"); - ReturnNode ret = parser.parse(); + StopNode stop = parser.parse(); StartNode start = Parser.START; + ReturnNode ret = (ReturnNode)stop.in(0); assertTrue(ret.ctrl() instanceof ProjNode); Node expr = ret.expr(); |