From eb60c8aa1ffd8602c4ca47fadf4c82154ca04f12 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sat, 28 Oct 2023 11:14:37 +0100 Subject: Update visualization to show all the Scope Nodes that are active. Fix test cases broken due to renaming of ProjNode label. Cleanup the way we update $ctrl token Assign an ID to each ScopeNode so that when we visualize we can assign different names --- .../com/seaofnodes/simple/GraphVisualizer.java | 24 ++++---- .../main/java/com/seaofnodes/simple/Parser.java | 70 ++++++++++++++-------- .../java/com/seaofnodes/simple/node/ScopeNode.java | 33 ++++++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 29 ++++++--- 4 files changed, 104 insertions(+), 52 deletions(-) (limited to 'chapter05/src') diff --git a/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index 3470a49a..d277a980 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -34,13 +34,15 @@ public class GraphVisualizer { nodes(sb, all); // Now the scopes, in a cluster no edges - scopes(sb, parser._scope); + for (ScopeNode sn: parser._allScopes) + scopes(sb, sn); // Walk the Node edges nodeEdges(sb, all); // Walk the Scope edges - scopeEdges(sb, parser._scope); + for (ScopeNode sn: parser._allScopes) + scopeEdges(sb, sn); sb.append("}\n"); return sb.toString(); @@ -51,8 +53,8 @@ public class GraphVisualizer { // Just the Nodes first, in a cluster no edges sb.append("\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name for( Node n : all ) { - if( n instanceof ProjNode ) - continue; // Do not emit, rolled into MultiNode already + if( n instanceof ProjNode || n instanceof ScopeNode ) + continue; // Do not emit, rolled into MultiNode or Scope cluster already sb.append("\t\t").append(n.uniqueName()).append(" [ "); String lab = n.label(); if( n instanceof MultiNode ) { @@ -99,8 +101,8 @@ public class GraphVisualizer { sb.append("\tnode [shape=plaintext];\n"); int level=0; for( HashMap scope : scopenode._scopes ) { - sb.append("\tsubgraph cluster_").append(level).append(" {\n"); // Magic "cluster_" in the subgraph name - String scopeName = makeScopeName(level); + String scopeName = makeScopeName(scopenode, level); + sb.append("\tsubgraph cluster_").append(scopeName).append(" {\n"); // Magic "cluster_" in the subgraph name sb.append("\t\t").append(scopeName).append(" [label=<\n"); sb.append("\t\t\t\n"); // Add the scope level @@ -116,15 +118,15 @@ public class GraphVisualizer { // We close them all at once here. sb.append( "\t}\n".repeat( level ) ); // End all Scope clusters } - - private String makeScopeName(int level) { return "scope" + level; } + + private String makeScopeName(ScopeNode sn, int level) { return sn.label() + "_" + level; } private String makePortName(String scopeName, String varName) { return scopeName + "_" + varName; } // Walk the node edges private void nodeEdges(StringBuilder sb, Collection all) { for( Node n : all ) { - if( n instanceof ConstantNode || n instanceof ProjNode ) - continue; // Do not display the Constant->Start edge; ProjNodes handled by Multi + if( n instanceof ConstantNode || n instanceof ProjNode || n instanceof ScopeNode ) + continue; // Do not display the Constant->Start edge; ProjNodes handled by Multi; ScopeNodes are done separately for( Node def : n._inputs ) if( def != null ) { sb.append('\t').append(n.uniqueName()).append(" -> "); @@ -145,7 +147,7 @@ public class GraphVisualizer { sb.append("\tedge [style=dashed color=cornflowerblue];\n"); int level=0; for( HashMap scope : scopenode._scopes ) { - String scopeName = makeScopeName(level); + String scopeName = makeScopeName(scopenode, level); for( String name : scope.keySet() ) { Node def = scopenode.in(scope.get(name)); if( def==null ) continue; diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java index e5d2901e..2953ec26 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java @@ -14,6 +14,11 @@ import java.util.*; */ public class Parser { + /** + * The control token is a name that binds to the currently active control + * node in the graph + */ + private static final String CTRL_TOKEN = "$ctrl"; /** * A Global Static, unique to each compilation. This is a public, so we * can make constants everywhere without having to thread the StartNode @@ -39,11 +44,16 @@ public class Parser { */ public ScopeNode _scope; - public List _allScopes = new ArrayList<>(); + /** + * 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 _allScopes = new ArrayList<>(); public Parser(String source, TypeInteger arg) { _lexer = new Lexer(source); _scope = new ScopeNode(); + _allScopes.add(_scope); Node.reset(); START = new StartNode(new Type[]{ Type.CONTROL, arg }); START.peephole(); @@ -55,12 +65,18 @@ public class Parser { String src() { return new String( _lexer._input ); } + private Node ctrlToken() { + return _scope.lookup(CTRL_TOKEN); + } + private void updateCtrlToken(Node n) { + _scope.update(CTRL_TOKEN, n); + } public ReturnNode parse() { _scope.push(); try { - _scope.define("$ctrl", new ProjNode(START, 0, "$ctrl").peephole()); + _scope.define(CTRL_TOKEN, new ProjNode(START, 0, CTRL_TOKEN).peephole()); _scope.define("arg" , new ProjNode(START, 1, "arg" ).peephole()); return (ReturnNode) parseBlock(); } @@ -110,56 +126,58 @@ public class Parser { // Parse predicate var pred = require(parseExpression(), ")"); // IfNode takes current control and predicate - IfNode ifNode = new IfNode(_scope.lookup("$ctrl"), pred); + IfNode ifNode = new IfNode(ctrlToken(), pred); // Setup projection nodes ProjNode ifT = new ProjNode(ifNode, 0, "True"); ProjNode ifF = new ProjNode(ifNode, 1, "False"); // 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(); + 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 + updateCtrlToken(ifT); // set ctrl token to ifTrue projection + parseStatement(); // restore scope - _scope = savedScope; + _scope = savedScope; // Restore scope to original, we use this for else block if any // Setup ifF as the ctrl - _scope.define("$ctrl", ifF); - Node elseStmt = null; - if (match("else")) elseStmt = parseStatement(); + updateCtrlToken(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 different then we need to create PhiNode for it - // After merge _scope remains + // 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 RegionNode region = mergeScopes(ifT, ifScope, ifF, _scope); - _scope.update("$ctrl", region); - ifScope.clear(); - _allScopes.remove(ifScope); + updateCtrlToken(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 scope) { + private RegionNode mergeScopes(ProjNode ifT, ScopeNode ifScope, ProjNode ifF, ScopeNode mergeScope) { RegionNode regionNode = new RegionNode(ifT, ifF); Set namesDone = new HashSet<>(); for (int level = ifScope._scopes.size()-1; level >= 0; level--) { var tab = ifScope._scopes.get(level); for (Map.Entry e: tab.entrySet()) { String name = e.getKey(); - if (name.equals("$ctrl")) // ignore + if (name.equals(CTRL_TOKEN)) // ignore ctrl token continue; - if (namesDone.contains(name)) // don't visit a name twice + 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); + Node ifNdef = mergeScope.lookup(name); // Lookup name in merge scope 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)) { + // 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); - scope.update(name, phiNode); + mergeScope.update(name, phiNode); } } } @@ -177,8 +195,8 @@ public class Parser { */ private Node parseReturn() { var expr = require(parseExpression(), ";"); - Node ret = new ReturnNode(_scope.lookup("$ctrl"), expr); - _scope.update("$ctrl",null); + Node ret = new ReturnNode(ctrlToken(), expr); + _scope.update(CTRL_TOKEN,null); return ret; } 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 be5538a3..5ac42c43 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -16,12 +16,24 @@ public class ScopeNode extends Node { * The top of this stack represents current scope. */ public final Stack> _scopes = new Stack<>(); + + /** + * We duplicate ScopeNodes when branches occur, so it is useful to have + * a unique name for each ScopeNode; this helps when we want to visualize the + * graph + */ + private int _id; + + private static int _idCounter = 0; + + public ScopeNode() { _id = _idCounter++; } @Override - public String label() { return "Scope"; } + public String label() { return "Scope" + _id; } @Override StringBuilder _print1(StringBuilder sb) { + sb.append(label()); for( HashMap scope : _scopes ) { sb.append("["); boolean first=true; @@ -84,21 +96,30 @@ public class ScopeNode extends Node { return null; } - + /** + * Duplicate a ScopeNode; including all levels. + * + * We do it in a way that ensures that the new ScopeNode becomes + * additional user of all defined names + */ public ScopeNode dup() { - ScopeNode sc = new ScopeNode(); + ScopeNode dupScope = new ScopeNode(); for (HashMap tab: _scopes) { - sc.push(); + dupScope.push(); // Create same level in the duplicate for (Map.Entry e: tab.entrySet()) { String name = e.getKey(); Integer idx = e.getValue(); Node n = in(idx); - sc.define(name, n); + dupScope.define(name, n); // Ensure that dupScope is a user of n } } - return sc; + return dupScope; } + /** + * Cleanup the scope and all its levels. + * Ensure that the scope is removed as user of all the defs. + */ public void clear() { while (!_scopes.empty()) pop(); diff --git a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 0604e9c6..cc5b5871 100644 --- a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -15,8 +15,19 @@ public class Chapter05Test { @Test public void testChapter5IfStmt() { - Parser parser = new Parser("int a = 1; if (arg == 1) a = arg+2; else a = arg-3; return a; #showGraph;", TypeInteger.BOT); + Parser parser = new Parser(""" + int a = 1;\s + if (arg == 1)\s + a = arg+2;\s + else { + a = arg-3;\s + #showGraph; + } + return a;\s + #showGraph; + """, TypeInteger.BOT); ReturnNode ret = parser.parse(); + assertEquals("return Phi(Region15,(arg3+2),(arg3-3));", ret.toString()); } @@ -24,42 +35,42 @@ public class Chapter05Test { public void testChapter4Peephole() { Parser parser = new Parser("return 1+arg+2; #showGraph;", TypeInteger.BOT); ReturnNode ret = parser.parse(); - assertEquals("return (Proj_3+3);", ret.print()); + assertEquals("return (arg3+3);", ret.print()); } @Test public void testChapter4Peephole2() { Parser parser = new Parser("return (1+arg)+2;", TypeInteger.BOT); ReturnNode ret = parser.parse(); - assertEquals("return (Proj_3+3);", ret.print()); + assertEquals("return (arg3+3);", ret.print()); } @Test public void testChapter4Add0() { Parser parser = new Parser("return 0+arg;", TypeInteger.BOT); ReturnNode ret = parser.parse(); - assertEquals("return Proj_3;", ret.print()); + assertEquals("return arg3;", ret.print()); } @Test public void testChapter4AddAddMul() { Parser parser = new Parser("return arg+0+arg;", TypeInteger.BOT); ReturnNode ret = parser.parse(); - assertEquals("return (Proj_3*2);", ret.print()); + assertEquals("return (arg3*2);", ret.print()); } @Test public void testChapter4Peephole3() { Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;", TypeInteger.BOT); ReturnNode ret = parser.parse(); - assertEquals("return ((Proj_3*2)+6);", ret.print()); + assertEquals("return ((arg3*2)+6);", ret.print()); } @Test public void testChapter4Mul1() { Parser parser = new Parser("return 1*arg;", TypeInteger.BOT); ReturnNode ret = parser.parse(); - assertEquals("return Proj_3;", ret.print()); + assertEquals("return arg3;", ret.print()); } @Test @@ -109,14 +120,14 @@ public class Chapter05Test { public void testChapter4Bug1() { Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;", TypeInteger.BOT); ReturnNode ret = parser.parse(); - assertEquals("return (Proj_3+3);", ret.print()); + assertEquals("return (arg3+3);", ret.print()); } @Test public void testChapter4Bug2() { Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;", TypeInteger.BOT); ReturnNode ret = parser.parse(); - assertEquals("return (Proj_3+1);", ret.print()); + assertEquals("return (arg3+1);", ret.print()); } @Test -- cgit v1.2.3