diff options
Diffstat (limited to 'chapter05/src/main/java/com')
5 files changed, 83 insertions, 97 deletions
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java index fc105523..4225e67b 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java @@ -15,10 +15,11 @@ import java.util.*; public class Parser { /** - * The control token is a name that binds to the currently active control + * The control is a name that binds to the currently active control * node in the graph */ - private static final String CTRL_TOKEN = "$ctrl"; + public static final String CTRL = "$ctrl"; + /** * A Global Static, unique to each compilation. This is a public, so we * can make constants everywhere without having to thread the StartNode @@ -34,10 +35,10 @@ public class Parser { * 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()}. - * + * <p> * 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. - * + * <p> * We keep a list of all ScopeNodes so that we can show them in graphs. * @see #parseIf() * @see #_allScopes @@ -48,13 +49,12 @@ public class Parser { * 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 List<ScopeNode> _allScopes = new ArrayList<>(); + public final Stack<ScopeNode> _allScopes = new Stack<>(); public Parser(String source, TypeInteger arg) { _lexer = new Lexer(source); - _scope = new ScopeNode(); - _allScopes.add(_scope); Node.reset(); + _scope = new ScopeNode(); START = new StartNode(new Type[]{ Type.CONTROL, arg }); START.peephole(); } @@ -65,23 +65,21 @@ public class Parser { String src() { return new String( _lexer._input ); } - private Node ctrlToken() { - return _scope.lookup(CTRL_TOKEN); - } + private Node ctrl() { return _scope.ctrl(); } - private void setCtrlToken(Node n) { - _scope.update(CTRL_TOKEN, n); - } + private Node ctrl(Node n) { return _scope.ctrl(n); } public ReturnNode parse() { + _allScopes.push(_scope); _scope.push(); try { - _scope.define(CTRL_TOKEN, new ProjNode(START, 0, CTRL_TOKEN).peephole()); - _scope.define("arg" , new ProjNode(START, 1, "arg" ).peephole()); + _scope.define(CTRL , new ProjNode(START, 0, CTRL ).peephole()); + _scope.define("arg", new ProjNode(START, 1, "arg").peephole()); return (ReturnNode) parseBlock(); } finally { _scope.pop(); + _allScopes.pop(); } } @@ -113,10 +111,10 @@ public class Parser { * </pre> */ private Node parseStatement() { - if (match("return")) return parseReturn(); + if (match("return") ) return parseReturn(); else if (match("int")) return parseDecl(); - else if (match("{")) return parseBlock(); - else if (match("if")) return parseIf(); + else if (match("{" )) return parseBlock(); + else if (match("if" )) return parseIf(); else if (match("#showGraph")) return showGraph(); else return parseExpressionStatement(); } @@ -126,61 +124,33 @@ public class Parser { // Parse predicate var pred = require(parseExpression(), ")"); // IfNode takes current control and predicate - IfNode ifNode = new IfNode(ctrlToken(), pred); + IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).peephole(); // Setup projection nodes - ProjNode ifT = new ProjNode(ifNode, 0, "True"); - ProjNode ifF = new ProjNode(ifNode, 1, "False"); + 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 - ScopeNode savedScope = _scope; - ScopeNode ifScope = _scope.dup(); // Duplicate current scope - _allScopes.add(ifScope); // For graph visualization we need all scopes - _scope = ifScope; // ifScope is now the current scope - setCtrlToken(ifT); // set ctrl token to ifTrue projection - parseStatement(); - _scope = savedScope; // Restore scope to original, we use this for else block if any - setCtrlToken(ifF); // Ctrl token is now set to ifFalse projection + int ndefs = _scope.nIns(); + ScopeNode fScope = _scope.dup(); // Duplicate current scope + _allScopes.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 + ctrl(ifF); // Ctrl token is now set to ifFalse projection if (match("else")) parseStatement(); - // Create region node and merge scopes - // If a var is in both scopes and has different binding then we need to create PhiNode for it - // After merge _scope remains, and ifScope is discarded - //System.out.println(new GraphVisualizer().generateDotOutput(this)); - RegionNode region = mergeScopes(ifT, ifScope, ifF, _scope); - setCtrlToken(region); // Now region becomes the ctrl token - ifScope.clear(); // Clean up ifScope - _allScopes.remove(ifScope); // Discard ifScope - return region; - } - private RegionNode mergeScopes(ProjNode ifT, ScopeNode ifScope, ProjNode ifF, ScopeNode mergeScope) { - RegionNode regionNode = new RegionNode(ifT, ifF); - Set<String> namesDone = new HashSet<>(); - for (int level = ifScope._scopes.size()-1; level >= 0; level--) { - var tab = ifScope._scopes.get(level); - for (Map.Entry<String, Integer> e: tab.entrySet()) { - String name = e.getKey(); - if (name.equals(CTRL_TOKEN)) // ignore ctrl token - continue; - if (namesDone.contains(name)) // don't visit a name twice - continue; - namesDone.add(name); - Integer idx = e.getValue(); - Node ifTdef = ifScope.in(idx); - Node ifNdef = mergeScope.lookup(name); // Lookup name in merge scope - if (ifNdef == null) - // The else scope didn't see this name - // Is this correct? Do we need same level as in ifScope? - // FIXME can this even happen, as all nested scopes should be gone - // so we cannot have a new var in same level anyway - mergeScope.define(name, ifTdef); - else if (!ifTdef.equals(ifNdef)) { // FIXME do we need equals or just ID comparison? - // Names are mapped to different nodes - PhiNode phiNode = new PhiNode(regionNode, ifTdef, ifNdef); - mergeScope.update(name, phiNode); - } - } - } - return regionNode; + if( tScope.nIns() != ndefs || fScope.nIns() != ndefs ) + throw error("Cannot define a new name on one arm of an if"); + + // Merge results + _scope = tScope; + _allScopes.pop(); // Discard pushed from graph display + return ctrl(tScope.mergeScopes(fScope)); } @@ -194,8 +164,8 @@ public class Parser { */ private Node parseReturn() { var expr = require(parseExpression(), ";"); - Node ret = new ReturnNode(ctrlToken(), expr); - _scope.update(CTRL_TOKEN,null); + Node ret = new ReturnNode(ctrl(), expr); + ctrl(null); // Kill control return ret; } @@ -479,8 +449,7 @@ public class Parser { private String parsePunctuation() { int start = _position; - if (isPunctuation(nextChar())) ; - return new String(_input, start, --_position - start); + return new String(_input, start, start+1); } } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java index 8b157a9c..a726a22d 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -57,11 +57,16 @@ public class AddNode extends Node { if (t2.isConstant() && lhs instanceof AddNode && lhs.in(2)._type.isConstant() ) return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole()); - // Do we have x + (y + con) ? - // Swap to (x + y) + con - if (rhs instanceof AddNode add && add.in(2)._type.isConstant() ) + // Do we have x + (y + non_add) ? + // Swap to (x + y) + non_add + if (rhs instanceof AddNode add && !(add.in(2) instanceof AddNode) ) return new AddNode(new AddNode(lhs,add.in(1)).peephole(), add.in(2)); + // Do we have (x + y) + x + // Swap to (x + x) + y + if (lhs instanceof AddNode add && add.in(1)==rhs ) + return new AddNode(new AddNode(rhs,rhs).peephole(), add.in(2)); + // Add of same to a multiply by 2 if( lhs==rhs ) return new MulNode(lhs,new ConstantNode(TypeInteger.constant(2)).peephole()); 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 2cafb1fa..f2fddd1c 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java @@ -25,8 +25,7 @@ public abstract class Node { * <p> * Generally fixed length, ordered, nulls allowed, no unused trailing space. * Ordering is required because e.g. "a/b" is different from "b/a". - * The first input (offset 0) is often a Control node. - * @see Control + * The first input (offset 0) is often a {@link #isCFG} node. */ public final ArrayList<Node> _inputs; @@ -102,13 +101,6 @@ public abstract class Node { public int nIns() { return _inputs.size(); } - /** - * Gets the ith output node - * @param i Offset of the output node - * @return Output node (not null) - */ - public Node out(int i) { return _outputs.get(i); } - public int nOuts() { return _outputs.size(); } public boolean isUnused() { return nOuts() == 0; } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 5e979cfd..6fef99f3 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -31,6 +31,10 @@ public class PhiNode extends Node { @Override public Node idealize() { + // Remove a "junk" Phi: Phi(x,x) is just x + if( in(1)==in(2) ) + return in(1); + return null; } } 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 517ada00..60d2bd43 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.TypeBot; import java.util.*; @@ -73,7 +74,15 @@ public class ScopeNode extends Node { return null; } + public Node ctrl() { assert lookup(Parser.CTRL)==in(0); return in(0); } + + public Node ctrl(Node n) { + assert lookup(Parser.CTRL)==in(0); + set_def(0,n); + return n; + } + // If the name is present in any scope, then redefine public Node update(String name, Node n) { for (int i = _scopes.size() - 1; i >= 0; i--) { @@ -86,23 +95,30 @@ public class ScopeNode extends Node { } /** - * Duplicate a ScopeNode; including all levels. + * Duplicate a ScopeNode; including all levels, up to Nodes. So this is + * neither shallow (would dup the Scope but not the internal HashMap + * tables), nor deep (would dup the Scope, the HashMap tables, but then the + * also program Nodes). * - * We do it in a way that ensures that the new ScopeNode becomes - * additional user of all defined names + * The new Scope is a full-fledged Node with proper use<->def edges. */ public ScopeNode dup() { - ScopeNode dupScope = new ScopeNode(); - for (HashMap<String, Integer> tab: _scopes) { - dupScope.push(); // Create same level in the duplicate - for (Map.Entry<String, Integer> e: tab.entrySet()) { - String name = e.getKey(); - Integer idx = e.getValue(); - Node n = in(idx); - dupScope.define(name, n); // Ensure that dupScope is a user of n - } + ScopeNode dup = new ScopeNode(); + for( HashMap<String, Integer> tab : _scopes ) { + dup.push(); // Create same level in the duplicate + for( String name : tab.keySet() ) + // Ensure that dup is a user of n + dup.define(name, in(tab.get(name))); } - return dupScope; + return dup; + } + + public RegionNode mergeScopes(ScopeNode that) { + RegionNode r = (RegionNode)ctrl(new RegionNode(ctrl(), that.ctrl()).peephole()); + for( int i=1; i<nIns(); i++ ) + set_def(i,new PhiNode(r, in(i), that.in(i)).peephole()); + that.kill(); // Kill merged scope + return r; } /** |