From 10249be5b6b13adfeaea77418a4770f0c39485f5 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 27 Oct 2023 20:35:04 +0100 Subject: Chapter 5: If Statement, Phi, and Region MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Dibyendu Majumdar Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Yichen Yan Co-authored-by: Thalia Archibald Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Tamas Hadhazy Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: Claude Opus 5 Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: RobertObkircher Co-authored-by: David Rubin <87927264+Rexicon226@users.noreply.github.com> --- src/main/java/com/seaofnodes/simple/Parser.java | 109 +++++++++-- .../java/com/seaofnodes/simple/node/AddNode.java | 27 ++- .../java/com/seaofnodes/simple/node/BoolNode.java | 6 +- .../java/com/seaofnodes/simple/node/DivNode.java | 2 + .../java/com/seaofnodes/simple/node/IfNode.java | 36 ++++ .../java/com/seaofnodes/simple/node/MulNode.java | 1 + src/main/java/com/seaofnodes/simple/node/Node.java | 16 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 74 ++++++++ .../java/com/seaofnodes/simple/node/ProjNode.java | 2 +- .../com/seaofnodes/simple/node/RegionNode.java | 27 +++ .../java/com/seaofnodes/simple/node/ScopeNode.java | 41 ++++ .../java/com/seaofnodes/simple/node/StopNode.java | 46 +++++ .../java/com/seaofnodes/simple/node/SubNode.java | 1 + .../simple/print/SimpleGraphAdapter.java | 34 +++- .../simple/print/SimpleGraphObserver.java | 12 +- src/main/java/com/seaofnodes/simple/type/Type.java | 2 +- .../java/com/seaofnodes/simple/type/TypeTuple.java | 4 +- .../java/com/seaofnodes/simple/Chapter01Test.java | 3 +- .../java/com/seaofnodes/simple/Chapter02Test.java | 14 +- .../java/com/seaofnodes/simple/Chapter03Test.java | 8 +- .../java/com/seaofnodes/simple/Chapter04Test.java | 43 ++--- .../java/com/seaofnodes/simple/Chapter05Test.java | 210 +++++++++++++++++++++ 22 files changed, 645 insertions(+), 73 deletions(-) create mode 100644 src/main/java/com/seaofnodes/simple/node/IfNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/PhiNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/RegionNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/StopNode.java create mode 100644 src/test/java/com/seaofnodes/simple/Chapter05Test.java (limited to 'src') diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 487afee9..359d0175 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple; import com.seaofnodes.graph.GraphObserver; + import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; @@ -15,6 +16,11 @@ import java.util.*; */ 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; } + /** * A Global Static, unique to each compilation. This is a public, so we @@ -24,17 +30,23 @@ public class Parser { * To make the compiler multithreaded, this field will have to move into a TLS. */ public static StartNode START; - // Current compilation context, like START; the observer belongs to the parser. - public static Parser PARSER; - public GraphObserver _obs; - public int pos() { return _lexer._position; } + + public StopNode STOP; // The Lexer. Thin wrapper over a byte[] buffer with a cursor. private final Lexer _lexer; /** - * A ScopeNode contains a stack of lexical scopes, each scope is a symbol table that binds + * Current ScopeNode - ScopeNodes change as we parse code, but at any point of time + * there is one current ScopeNode. The reason the current ScopeNode can change is to do with how + * we handle branching. See {@link #parseIf()}. + *

+ * Each ScopeNode contains a stack of lexical scopes, each scope is a symbol table that binds * variable names to Nodes. The top of this stack represents current scope. + *

+ * We keep a list of all ScopeNodes so that we can show them in graphs. + * @see #parseIf() + * @see #_xScopes */ public ScopeNode _scope; @@ -42,18 +54,28 @@ public class Parser { * List of keywords disallowed as identifiers */ private final HashSet KEYWORDS = new HashSet<>(){{ + add("else"); + add("false"); + add("if"); add("int"); add("return"); + add("true"); }}; + /** + * We clone ScopeNodes when control flows branch; it is useful to have + * a list of all active ScopeNodes for purposes of visualization of the SoN graph + */ + public final Stack _xScopes = new Stack<>(); + public Parser(String source, TypeInteger arg) { PARSER = this; Node.reset(); _lexer = new Lexer(source); _scope = new ScopeNode(); START = new StartNode(new Type[]{ Type.CONTROL, arg }); - START.peephole(); + STOP = new StopNode(); } public Parser(String source) { @@ -72,17 +94,21 @@ public class Parser { private Node ctrl(Node n) { return _scope.ctrl(n); } - public ReturnNode parse() { + public StopNode parse() { + _xScopes.push(_scope); // Enter a new scope for the initial control and arguments _scope.push(); _scope.define(ScopeNode.CTRL, new ProjNode(START, 0, ScopeNode.CTRL).peephole()); _scope.define(ScopeNode.ARG0, new ProjNode(START, 1, ScopeNode.ARG0).peephole()); - var ret = (ReturnNode) parseBlock(); + parseBlock(); _scope.pop(); + _xScopes.pop(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); - return ret; + STOP.peephole(); + return STOP; } + /** * Parses a block * @@ -95,21 +121,18 @@ public class Parser { private Node parseBlock() { // Enter a new scope _scope.push(); - Node n = null; - while (!peek('}') && !_lexer.isEOF()) { - Node n0 = parseStatement(); - if (n0 != null) n = n0; // Empty statements can return null - }; + while (!peek('}') && !_lexer.isEOF()) + parseStatement(); // Exit scope _scope.pop(); - return n; + return null; } /** * Parses a statement * * 

-     *     returnStatement | declStatement | blockStatement | expressionStatement
+     *     returnStatement | declStatement | blockStatement | ifStatement | expressionStatement
      *
* @return a {@link Node} or {@code null} */ @@ -117,10 +140,58 @@ public class Parser { if (matchx("return") ) return parseReturn(); else if (matchx("int")) return parseDecl(); else if (match ("{" )) return require(parseBlock(),"}"); + else if (matchx("if" )) return parseIf(); else if (matchx(";")) return null; // Empty statement else return parseExpressionStatement(); } + /** + * Parses a statement + * + * 
+     *     if ( expression ) statement [else statement]
+     *
+ * @return a {@link Node}, never {@code null} + */ + private Node parseIf() { + require("("); + // Parse predicate + var pred = require(parseExpression(), ")"); + // IfNode takes current control and predicate + IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).keep().peephole(); + // Setup projection nodes + Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); + Node ifF = new ProjNode(ifNode, 1, "False").peephole(); + // In if true branch, the ifT proj node becomes the ctrl + // But first clone the scope and set it as current + int ndefs = _scope.nIns(); + ScopeNode fScope = _scope.dup(); // Duplicate current scope + fScope.ctrl(ifF); // The pending arm already starts at False + _xScopes.push(fScope); // For graph visualization we need all scopes + + // Parse the true side + ctrl(ifT); // set ctrl token to ifTrue projection + parseStatement(); // Parse true-side + ScopeNode tScope = _scope; + + // Parse the false side + _scope = fScope; // Restore scope, then parse else block if any + if (matchx("else")) { + parseStatement(); + fScope = _scope; + } + + if( tScope.nIns() != ndefs || fScope.nIns() != ndefs ) + throw error("Cannot define a new name on one arm of an if"); + + // Merge results + _scope = tScope; + _xScopes.pop(); // Discard pushed from graph display + + return ctrl(tScope.mergeScopes(fScope)); + } + + /** * Parses a return statement; "return" already parsed. * The $ctrl edge is killed. @@ -132,7 +203,7 @@ public class Parser { */ private Node parseReturn() { var expr = require(parseExpression(), ";"); - Node ret = new ReturnNode(ctrl(), expr).peephole(); + Node ret = STOP.addReturn(new ReturnNode(ctrl(), expr).peephole()); ctrl(null); // Kill control return ret; } @@ -250,13 +321,15 @@ public class Parser { * Parse a primary expression: * * 
-     *     primaryExpr : integerLiteral | Identifier | '(' expression ')'
+     *     primaryExpr : integerLiteral | Identifier | true | false | '(' expression ')'
      *
* @return a primary {@link Node}, never {@code null} */ private Node parsePrimary() { if( _lexer.isNumber() ) return parseIntegerLiteral(); if( match("(") ) return require(parseExpression(), ")"); + if( matchx("true" ) ) return new ConstantNode(TypeInteger.constant(1)).peephole(); + if( matchx("false") ) return new ConstantNode(TypeInteger.constant(0)).peephole(); String name = _lexer.matchId(); if( name == null) throw errorSyntax("an identifier or expression"); Node n = _scope.lookup(name); diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 0291a900..2772c4c5 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -70,6 +70,24 @@ public class AddNode extends Node { if( lhs.in(2)._type.isConstant() && t2.isConstant() ) return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole()); + if( lhs.in(2) instanceof PhiNode phi && phi.allCons() && + // Do we have ((x + (phi cons)) + con) ? + // Do we have ((x + (phi cons)) + (phi cons)) ? + // Push constant up through the phi: x + (phi con0+con0 con1+con1...) + + // Note that this is the exact reverse of Phi pulling a common op + // down to reduce total op-count. We don't get in an endless push- + // up push-down peephole cycle because the constants all fold first. + (t2.isConstant() || (rhs instanceof PhiNode && phi.in(0) == rhs.in(0) && rhs.allCons()) ) ) { + Node[] ns = new Node[phi.nIns()]; + ns[0] = phi.in(0); + // Push constant up through the phi: x + (phi con0+con0 con1+con1...) + for( int i=1; i hi._nid; } + @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 143a6fde..87acc6cc 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -43,7 +43,7 @@ abstract public class BoolNode extends Node { return null; } - public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } } - public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs < rhs; } } - public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } } + public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } Node copy(Node lhs, Node rhs) { return new EQ(lhs,rhs); } } + public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs < rhs; } Node copy(Node lhs, Node rhs) { return new LT(lhs,rhs); } } + public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } Node copy(Node lhs, Node rhs) { return new LE(lhs,rhs); } } } diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java index bffa4b44..f80f092d 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -35,4 +35,6 @@ public class DivNode extends Node { return in(1); return null; } + + @Override Node copy(Node lhs, Node rhs) { return new DivNode(lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java new file mode 100644 index 00000000..6124b893 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -0,0 +1,36 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.type.TypeTuple; + +public class IfNode extends MultiNode { + + public IfNode(Node ctrl, Node pred) { + super(ctrl, pred); + } + + @Override + public String label() { return "If"; } + + @Override + StringBuilder _print1(StringBuilder sb) { + sb.append("if( "); + return in(1)._print0(sb).append(" )"); + } + + @Override public boolean isCFG() { return true; } + + public Node ctrl() { return in(0); } + public Node pred() { return in(1); } + + @Override + public Type compute() { + return TypeTuple.IF; + } + + @Override + public Node idealize() { + return null; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index 60103b8b..b1d9e44a 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -44,4 +44,5 @@ public class MulNode extends Node { return null; } + @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index fdde869b..e17d7b9a 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -250,7 +250,7 @@ public abstract class Node { return deadCodeElim(n.peephole()); return null; // No progress - } + } // m is the new Node, self is the old. // Return 'm', which may have zero uses but is alive nonetheless. @@ -346,6 +346,20 @@ public abstract class Node { return this; } + // does this node contain all constants? + // Ignores in(0), as is usually control. + boolean allCons() { + for( int i=1; i + * The new Scope is a full-fledged Node with proper use<->def edges. + */ + public ScopeNode dup() { + ScopeNode dup = new ScopeNode(); + // Our goals are: + // 1) duplicate the name bindings of the ScopeNode across all stack levels + // 2) Make the new ScopeNode a user of all the nodes bound + // 3) Ensure that the order of defs is the same to allow easy merging + for( HashMap syms : _scopes ) + dup._scopes.push(new HashMap<>(syms)); + dup.addDef(ctrl()); // Control input is just copied + for( int i=1; i { @Override protected boolean dead(Node n) { return n.isDead(); } @Override protected int id(Node n) { return n._nid; } @@ -17,23 +17,37 @@ public class SimpleGraphAdapter extends GraphAdapter { @Override protected Node out(Node n, int idx) { return n.out(idx); } private ArrayList edges(Node n) { - String[] names = n instanceof ScopeNode scope && n.nIns() != 0 ? scope.reverseNames() : null; var edges = new ArrayList(); + String[] names = n instanceof ScopeNode scope && n.nIns() != 0 ? scope.reverseNames() : null; for( int i = 0; i < n.nIns(); i++ ) { - Role role = n instanceof ScopeNode || n instanceof ConstantNode ? Role.ASSOC - : n instanceof ProjNode ? (n.isCFG() ? Role.CTRL : Role.DATA) - : i == 0 ? Role.CTRL : Role.DATA; - edges.add(new Edge(i, ref(n.in(i)), role, names == null ? null : names[i])); + String name = names == null || i >= names.length ? null : names[i]; + edges.add(new Edge(i, ref(n.in(i)), role(n, i), name)); } return edges; } @Override protected GraphSnapshot.Node desc(Node n) { - Projection proj = n instanceof ProjNode p - ? new Projection(n.nIns() == 0 ? 0 : ref(n.in(0)), p._idx) : null; - Kind kind = n instanceof ScopeNode ? Kind.SCOPE : n.isCFG() ? Kind.CTRL : Kind.DATA; + Projection proj = n instanceof ProjNode p ? new Projection(ref(n.in(0)), p._idx) : null; String label = n.label(); return new GraphSnapshot.Node(n._nid, label == null ? n.getClass().getSimpleName() : label, - n._type == null ? null : n._type.toString(), kind, edges(n), proj); + n._type == null ? null : n._type.toString(), kind(n), edges(n), proj); + } + + private Kind kind(Node n) { + if( n instanceof StopNode ) return Kind.STOP; + if( n instanceof ScopeNode ) return Kind.SCOPE; + if( n instanceof StartNode ) return Kind.CTRL; + if( n instanceof RegionNode ) return Kind.REGION; + if( n instanceof PhiNode ) return Kind.PHI; + return n.isCFG() ? Kind.CTRL : Kind.DATA; + } + + private Role role(Node n, int i) { + if( n instanceof ScopeNode || n instanceof ConstantNode ) return Role.ASSOC; + if( n instanceof PhiNode ) return i == 0 ? Role.ASSOC : Role.DATA; + if( n instanceof ProjNode ) return n.isCFG() ? Role.CTRL : Role.DATA; + if( n instanceof RegionNode && i == 0 ) return Role.ASSOC; + if( i == 0 || n instanceof RegionNode || n instanceof StopNode ) return Role.CTRL; + return Role.DATA; } } diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index d655ed4a..a7604165 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -7,10 +7,11 @@ import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.io.IOException; -/** Chapter 4 needs only a parser; it has no worklist or distant dependencies. */ +/** Chapter 5's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture { private Parser _parser; private Node _ret; + private String _phase; public SimpleGraphObserver() { super(new SimpleGraphAdapter()); } public static void main(String[] args) throws IOException { GraphViewer.run(new SimpleGraphObserver()); @@ -18,11 +19,12 @@ public class SimpleGraphObserver extends GraphCapture { @Override protected void compile(String src) { _parser = new Parser(src); _parser._obs = this; + _phase = "Parse"; _ret = _parser.parse(); - phase("Parse"); + phase(_phase); } - @Override protected String phase() { return "Parse"; } - @Override protected int pos() { return _parser.pos(); } + @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; @@ -31,6 +33,8 @@ public class SimpleGraphObserver extends GraphCapture { @Override protected Node scope() { return _parser._scope; } @Override protected void roots(ArrayList roots) { roots.add(Parser.START); + roots.add(_parser.STOP); + roots.addAll(_parser._xScopes); roots.add(_ret); } } diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index 1e50bdda..6b9130ba 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -43,7 +43,7 @@ public class Type { public StringBuilder print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;} - public Type meet(Type other) { return Type.BOTTOM; } + public Type meet(Type other) { return BOTTOM; } @Override public final String toString() { diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index 52befa38..da701865 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -16,11 +16,13 @@ public class TypeTuple extends Type { @Override public StringBuilder print(StringBuilder sb) { - sb.append("[ "); + sb.append("["); for( Type t : _types ) t.print(sb).append(","); sb.setLength(sb.length()-1); sb.append("]"); return sb; } + + public static final TypeTuple IF = new TypeTuple(new Type[]{Type.CONTROL,Type.CONTROL}); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/src/test/java/com/seaofnodes/simple/Chapter01Test.java index 3d568337..547c36f8 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -11,8 +11,9 @@ public class Chapter01Test { @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(); diff --git a/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/src/test/java/com/seaofnodes/simple/Chapter02Test.java index 6c816a23..a6075b75 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter02Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -11,49 +11,49 @@ public class Chapter02Test { @Test public void testParseGrammar() { Parser parser = new Parser("return 1+2*3+-5;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 2;", ret.print()); } @Test public void testAddPeephole() { Parser parser = new Parser("return 1+2;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 3;", ret.print()); } @Test public void testSubPeephole() { Parser parser = new Parser("return 1-2;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return -1;", ret.print()); } @Test public void testMulPeephole() { Parser parser = new Parser("return 2*3;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 6;", ret.print()); } @Test public void testDivPeephole() { Parser parser = new Parser("return 6/3;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 2;", ret.print()); } @Test public void testMinusPeephole() { Parser parser = new Parser("return 6/-3;"); - ReturnNode ret = parser.parse(); + StopNode 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(); + StopNode ret = parser.parse(); assertEquals("return 2;", ret.print()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java index 46b1ca33..c3cd43c3 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -11,28 +11,28 @@ public class Chapter03Test { @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()); } @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);"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 8;", ret.print()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/src/test/java/com/seaofnodes/simple/Chapter04Test.java index 195afbb7..e5840622 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -11,77 +11,78 @@ public class Chapter04Test { @Test public void testPeephole() { Parser parser = new Parser("return 1+arg+2;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (arg+3);", ret.print()); } @Test public void testPeephole2() { Parser parser = new Parser("return (1+arg)+2;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (arg+3);", ret.print()); } @Test public void testAdd0() { Parser parser = new Parser("return 0+arg;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return arg;", ret.print()); } @Test public void testAddAddMul() { Parser parser = new Parser("return arg+0+arg;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (arg*2);", ret.print()); } @Test public void testPeephole3() { Parser parser = new Parser("return 1+arg+2+arg+3;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return ((arg*2)+6);", ret.print()); } @Test public void testMul1() { Parser parser = new Parser("return 1*arg;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return arg;", ret.print()); } @Test public void testSub0() { Parser parser = new Parser("return arg-0;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return arg;", ret.print()); } @Test public void test0Sub() { Parser parser = new Parser("return 0-arg;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (-arg);", ret.print()); } @Test public void testSubNeg() { Parser parser = new Parser("return 3--arg;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (arg+3);", ret.print()); } @Test public void testNegSub() { Parser parser = new Parser("return -arg-3;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (-(arg+3));", ret.print()); } @Test public void testVarArg() { - Parser parser = new Parser("return arg;", TypeInteger.BOT); - ReturnNode ret = parser.parse(); + Parser parser = new Parser("return arg;"); + StopNode stop = parser.parse(); + ReturnNode ret = stop.ret(); assertTrue(ret.in(0) instanceof ProjNode); assertTrue(ret.in(1) instanceof ProjNode); } @@ -89,49 +90,49 @@ public class Chapter04Test { @Test public void testConstantArg() { Parser parser = new Parser("return arg;", TypeInteger.constant(2)); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 2;", ret.print()); } @Test public void testCompEq() { Parser parser = new Parser("return 3==3;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 1;", ret.print()); } @Test public void testCompEq2() { Parser parser = new Parser("return 3==4;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 0;", ret.print()); } @Test public void testCompNEq() { Parser parser = new Parser("return 3!=3;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 0;", ret.print()); } @Test public void testCompNEq2() { Parser parser = new Parser("return 3!=4;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 1;", ret.print()); } @Test public void testBug1() { Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (arg+3);", ret.print()); } @Test public void testBug2() { Parser parser = new Parser("int a=arg+1; a=a; return a;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (arg+1);", ret.print()); } @@ -148,14 +149,14 @@ public class Chapter04Test { @Test public void testBug4() { Parser parser = new Parser("return -arg;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (-arg);", ret.print()); } @Test public void testBug5() { Parser parser = new Parser("return arg--2;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (arg--2);", ret.print()); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java new file mode 100644 index 00000000..31ca56a0 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -0,0 +1,210 @@ +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 Chapter05Test { + + @Test + public void testIfStmt() { + Parser parser = new Parser( +""" +int a = 1; +if (arg == 1) + a = arg+2; +else { + a = arg-3; +} +return a;"""); + StopNode ret = parser.parse(); + assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString()); + } + + @Test + public void testTest() { + Parser parser = new Parser( +""" +int c = 3; +int b = 2; +if (arg == 1) { + b = 3; + c = 4; +} +return c;""", TypeInteger.BOT); + StopNode ret = parser.parse(); + assertEquals("return Phi(Region16,4,3);", ret.toString()); + } + + @Test + public void testReturn2() { + Parser parser = new Parser( +""" +if( arg==1 ) + return 3; +else + return 4; +""", TypeInteger.BOT); + StopNode stop = parser.parse(); + assertEquals("Stop[ return 3; return 4; ]", stop.toString()); + } + + @Test + public void testIfMergeB() { + Parser parser = new Parser( +""" +int a=arg+1; +int b=0; +if( arg==1 ) + b=a; +else + b=a+1; +return a+b;"""); + StopNode ret = parser.parse(); + assertEquals("return ((arg*2)+Phi(Region20,2,3));", ret.toString()); + } + + @Test + public void testIfMerge2() { + 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;"""); + StopNode ret = parser.parse(); + assertEquals("return ((Phi(Region31,(arg*2),arg)+arg)+Phi(Region31,4,5));", ret.toString()); + } + + @Test + public void testMerge3() { + Parser parser = new Parser( +""" +int a=1; +if( arg==1 ) + if( arg==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +""", TypeInteger.BOT); + StopNode stop = parser.parse(); + assertEquals("return Phi(Region33,Phi(Region21,2,3),Phi(Region31,4,5));", stop.toString()); + } + + @Test + public void testMerge4() { + Parser parser = new Parser( +""" +int a=0; +int b=0; +if( arg ) + a=1; +if( arg==0 ) + b=2; +return arg+a+b; +""", TypeInteger.BOT); + StopNode stop = parser.parse(); + assertEquals("return ((arg+Phi(Region13,1,0))+Phi(Region22,2,0));", stop.toString()); + } + + @Test + public void testMerge5() { + Parser parser = new Parser( +""" +int a=arg==2; +if( arg==1 ) +{ + a=arg==3; +} +return a;"""); + StopNode ret = parser.parse(); + assertEquals("return (arg==Phi(Region16,3,2));", ret.toString()); + } + + @Test + public void testTrue() { + StopNode stop = new Parser("return true;").parse(); + assertEquals("return 1;",stop.toString()); + } + + @Test + public void testHalfDef() { + try { + new Parser("if( arg==1 ) int b=2; return b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Cannot define a new name on one arm of an if",e.getMessage()); + } + } + + @Test + public void testHalfDef2() { + try { + new Parser("if( arg==1 ) { int b=2; } else { int b=3; } return b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'b'",e.getMessage()); + } + } + + @Test + public void testRegress1() { + try { + new Parser("if(arg==2) int a=1; else int b=2; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Cannot define a new name on one arm of an if",e.getMessage()); + } + } + + @Test + public void testBadNum() { + try { + new Parser("return 1-;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected an identifier or expression: ;",e.getMessage()); + } + } + + @Test + public void testKeyword1() { + try { + new Parser("int true=0; return true;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Expected an identifier, found 'true'",e.getMessage()); + } + } + + @Test + public void testKeyword2() { + try { + new Parser("int else=arg; if(else) else=2; else else=1; return else;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Expected an identifier, found 'else'",e.getMessage()); + } + } + + @Test + public void testKeyword3() { + try { + new Parser("int a=1; ififif(arg)inta=2;return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected =: (",e.getMessage()); + } + } + +} -- cgit v1.2.3