From 9ed409df4516e0089afbc7d5ccf9b029d431be04 Mon Sep 17 00:00:00 2001 From: Thalia Archibald Date: Sun, 3 Mar 2024 17:55:47 +0000 Subject: Chapter 9: Global Value Numbering and Iterative Peepholes Co-authored-by: Cliff Click Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Robert Obkircher Co-authored-by: Dibyendu Majumdar Co-authored-by: Darrick Wiebe --- src/main/java/com/seaofnodes/simple/Parser.java | 75 ++++++++++++++++--------- 1 file changed, 48 insertions(+), 27 deletions(-) (limited to 'src/main/java/com/seaofnodes/simple/Parser.java') diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 69796828..aabdf63a 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -69,11 +69,12 @@ public class Parser { public Parser(String source, TypeInteger arg) { Node.reset(); + IterPeeps.reset(); _lexer = new Lexer(source); _scope = new ScopeNode(); _continueScope = _breakScope = null; START = new StartNode(new Type[]{ Type.CONTROL, arg }); - STOP = new StopNode(); + STOP = new StopNode(source); } public Parser(String source) { @@ -108,7 +109,6 @@ public class Parser { return STOP; } - /** * Parses a block * @@ -185,11 +185,10 @@ public class Parser { // Parse predicate var pred = require(parseExpression(), ")"); // IfNode takes current control and predicate - IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).keep().peephole(); + Node ifNode = new IfNode(ctrl(), pred).peephole(); // Setup projection nodes - Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); - ifNode.unkeep(); - Node ifF = new ProjNode(ifNode, 1, "False").peephole(); + Node ifT = new ProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); + Node ifF = new ProjNode(ifNode.unkeep(), 1, "False").peephole(); // Clone the body Scope to create the break/exit Scope which accounts for any // side effects in the predicate. The break/exit Scope will be the final @@ -203,7 +202,7 @@ public class Parser { // Parse the true side, which corresponds to loop body // Our current scope is the body Scope - ctrl(ifT); // set ctrl token to ifTrue projection + ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection parseStatement(); // Parse loop body // Merge the loop bottom into other continue statements @@ -247,7 +246,7 @@ public class Parser { return cur; // toScope is either the break scope, or a scope that was created here assert toScope._scopes.size() <= _breakScope._scopes.size(); - toScope.mergeScopes(cur); + toScope.ctrl(toScope.mergeScopes(cur)); return toScope; } @@ -269,11 +268,10 @@ public class Parser { // Parse predicate var pred = require(parseExpression(), ")"); // IfNode takes current control and predicate - IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).keep().peephole(); + Node ifNode = new IfNode(ctrl(), pred).peephole(); // Setup projection nodes - Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); - ifNode.unkeep(); - Node ifF = new ProjNode(ifNode, 1, "False").peephole(); + Node ifT = new ProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); + Node ifF = new ProjNode(ifNode.unkeep(), 1, "False").peephole().keep(); // 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(); @@ -281,13 +279,13 @@ public class Parser { _xScopes.push(fScope); // For graph visualization we need all scopes // Parse the true side - ctrl(ifT); // set ctrl token to ifTrue projection + ctrl(ifT.unkeep()); // 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 - ctrl(ifF); // Ctrl token is now set to ifFalse projection + ctrl(ifF.unkeep()); // Ctrl token is now set to ifFalse projection if (matchx("else")) { parseStatement(); fScope = _scope; @@ -324,8 +322,8 @@ public class Parser { * Dumps out the node graph * @return {@code null} */ - private Node showGraph() { - System.out.println(new GraphVisualizer().generateDotOutput(this)); + Node showGraph() { + System.out.println(new GraphVisualizer().generateDotOutput(STOP,_scope,_xScopes)); return null; } @@ -384,12 +382,23 @@ public class Parser { */ private Node parseComparison() { var lhs = parseAddition(); - if (match("==")) return new BoolNode.EQ(lhs, parseComparison()).peephole(); - if (match("!=")) return new NotNode(new BoolNode.EQ(lhs, parseComparison()).peephole()).peephole(); - if (match("<=")) return new BoolNode.LE(lhs, parseComparison()).peephole(); - if (match("<" )) return new BoolNode.LT(lhs, parseComparison()).peephole(); - if (match(">=")) return new BoolNode.LE(parseComparison(), lhs).peephole(); - if (match(">" )) return new BoolNode.LT(parseComparison(), lhs).peephole(); + while( true ) { + int idx=0; boolean negate=false; + // Test for any local nodes made, and "keep" lhs during peepholes + if( false ) ; + else if( match("==") ) { idx=2; lhs = new BoolNode.EQ(lhs, null); } + else if( match("!=") ) { idx=2; lhs = new BoolNode.EQ(lhs, null); negate=true; } + else if( match("<=") ) { idx=2; lhs = new BoolNode.LE(lhs, null); } + else if( match("<" ) ) { idx=2; lhs = new BoolNode.LT(lhs, null); } + else if( match(">=") ) { idx=1; lhs = new BoolNode.LE(null, lhs); } + else if( match(">" ) ) { idx=1; lhs = new BoolNode.LT(null, lhs); } + else break; + // Peepholes can fire, but lhs is already "hooked", kept alive + lhs.setDef(idx,parseAddition()); + lhs = lhs.peephole(); + if( negate ) // Extra negate for != + lhs = new NotNode(lhs).peephole(); + } return lhs; } @@ -402,9 +411,15 @@ public class Parser { * @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(); + Node lhs = parseMultiplication(); + while( true ) { + if( false ) ; + else if( match("+") ) lhs = new AddNode(lhs,null); + else if( match("-") ) lhs = new SubNode(lhs,null); + else break; + lhs.setDef(2,parseMultiplication()); + lhs = lhs.peephole(); + } return lhs; } @@ -418,8 +433,14 @@ public class Parser { */ private Node parseMultiplication() { var lhs = parseUnary(); - if (match("*")) return new MulNode(lhs, parseMultiplication()).peephole(); - if (match("/")) return new DivNode(lhs, parseMultiplication()).peephole(); + while( true ) { + if( false ) ; + else if( match("*") ) lhs = new MulNode(lhs,null); + else if( match("/") ) lhs = new DivNode(lhs,null); + else break; + lhs.setDef(2,parseUnary()); + lhs = lhs.peephole(); + } return lhs; } -- cgit v1.2.3