diff options
Diffstat (limited to 'chapter05/src')
10 files changed, 236 insertions, 15 deletions
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java index 147515f6..331916fb 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java @@ -26,11 +26,21 @@ public class Parser { private final Lexer _lexer; /** - * 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 #_allScopes */ public ScopeNode _scope; + public List<ScopeNode> _allScopes = new ArrayList<>(); + public Parser(String source, TypeInteger arg) { _lexer = new Lexer(source); _scope = new ScopeNode(); @@ -90,10 +100,73 @@ public class Parser { 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("#showGraph")) return showGraph(); else return parseExpressionStatement(); } + private Node parseIf() { + require("("); + // Parse predicate + var pred = require(parseExpression(), ")"); + // IfNode takes current control and predicate + IfNode ifNode = new IfNode(_scope.lookup("$ctrl"), pred); + // Setup projection nodes + ProjNode ifT = new ProjNode(ifNode, 0, "ifT"); + ProjNode ifF = new ProjNode(ifNode, 1, "ifF"); + // 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 visualization we need all scopes + _scope = ifScope; // ifScope is current + _scope.define("$ctrl", ifT); + var thenStmt = parseStatement(); + // restore scope + _scope = savedScope; + // Setup ifF as the ctrl + _scope.define("$ctrl", ifF); + Node elseStmt = null; + if (match("else")) elseStmt = parseStatement(); + // Create region node and merge scopes + // If a var is in both scopes and different then we need to create PhiNode for it + // After merge _scope remains + RegionNode region = mergeScopes(ifT, ifScope, ifF, _scope); + _scope.update("$ctrl", region); + ifScope.clear(); + _allScopes.remove(ifScope); + return region; + } + + private RegionNode mergeScopes(ProjNode ifT, ScopeNode ifScope, ProjNode ifF, ScopeNode scope) { + 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")) // ignore + 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 = scope.lookup(name); + if (ifNdef == null) + // The else scope didn't see this name + scope.define(name, ifTdef); // Is this correct? Do we need same level as in ifScope? + else if (!ifTdef.equals(ifNdef)) { + // Names are mapped to different nodes + PhiNode phiNode = new PhiNode(regionNode, ifTdef, ifNdef); + scope.update(name, phiNode); + } + } + } + return regionNode; + } + + /** * Parses a return statement; "return" already parsed. * The $ctrl edge is killed. diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java new file mode 100644 index 00000000..460054ec --- /dev/null +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -0,0 +1,31 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeBot; + +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) { + return sb; + } + + @Override + public Type compute() { + return TypeBot.BOTTOM; + } + + @Override + public Node idealize() { + return null; + } +} diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java index e517c3d5..28d054a6 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java @@ -7,7 +7,5 @@ public abstract class MultiNode extends Node { public MultiNode(Node... inputs) { super(inputs); } - - // Return the ProjNode with the idx - abstract ProjNode proj(int idx); + } 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 8d698d1b..65ebef5b 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java @@ -4,6 +4,7 @@ import com.seaofnodes.simple.type.Type; import java.util.ArrayList; import java.util.Collections; +import java.util.Objects; /** * All Nodes in the Sea of Nodes IR inherit from the Node class. @@ -339,5 +340,17 @@ public abstract class Node { /* * hashCode and equals implementation to be added in later chapter. */ - + + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (o == null || getClass() != o.getClass()) return false; + Node node = (Node) o; + return _nid == node._nid && Objects.equals(_inputs, node._inputs) && Objects.equals(_type, node._type); + } + + @Override + public int hashCode() { + return Objects.hash(_nid, _inputs, _type); + } } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java new file mode 100644 index 00000000..25308724 --- /dev/null +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -0,0 +1,31 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeBot; + +public class PhiNode extends Node { + + public PhiNode(Node... inputs) { + super(inputs); + } + + @Override + public String label() { + return "Phi"; + } + + @Override + StringBuilder _print1(StringBuilder sb) { + return sb; + } + + @Override + public Type compute() { + return TypeBot.BOTTOM; + } + + @Override + public Node idealize() { + return null; + } +} diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java new file mode 100644 index 00000000..96840ae5 --- /dev/null +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -0,0 +1,30 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeBot; + +public class RegionNode extends Node implements Control { + public RegionNode(Node... inputs) { + super(inputs); + } + + @Override + public String label() { + return "Region"; + } + + @Override + StringBuilder _print1(StringBuilder sb) { + return sb; + } + + @Override + public Type compute() { + return TypeBot.BOTTOM; + } + + @Override + public Node idealize() { + 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 8bd81e82..be5538a3 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -85,4 +85,22 @@ public class ScopeNode extends Node { } + public ScopeNode dup() { + ScopeNode sc = new ScopeNode(); + for (HashMap<String, Integer> tab: _scopes) { + sc.push(); + for (Map.Entry<String, Integer> e: tab.entrySet()) { + String name = e.getKey(); + Integer idx = e.getValue(); + Node n = in(idx); + sc.define(name, n); + } + } + return sc; + } + + public void clear() { + while (!_scopes.empty()) + pop(); + } } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java index b59e3375..583cf054 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -33,14 +33,4 @@ public class StartNode extends MultiNode implements Control { @Override public Node idealize() { return null; } - - - @Override - public ProjNode proj( int idx ) { - for( Node proj : _outputs ) - if( ((ProjNode)proj)._idx==idx ) - return (ProjNode)proj; - return null; - } - } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java new file mode 100644 index 00000000..b710e160 --- /dev/null +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -0,0 +1,30 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeBot; + +public class StopNode extends Node implements Control { + public StopNode(Node... inputs) { + super(inputs); + } + + @Override + public String label() { + return "Stop"; + } + + @Override + StringBuilder _print1(StringBuilder sb) { + return sb; + } + + @Override + public Type compute() { + return TypeBot.BOTTOM; + } + + @Override + public Node idealize() { + return null; + } +} diff --git a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 4106ef3b..858e2470 100644 --- a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -14,6 +14,13 @@ public class Chapter05Test { public ExpectedException exceptionRule = ExpectedException.none(); @Test + public void testChapter5IfStmt() { + Parser parser = new Parser("int a = 1; if (arg == 1) a = arg+2; else a = arg-3; return a;", TypeInteger.BOT); + ReturnNode ret = parser.parse(); + } + + + @Test public void testChapter4Peephole() { Parser parser = new Parser("return 1+arg+2; #showGraph;", TypeInteger.BOT); ReturnNode ret = parser.parse(); |