diff options
5 files changed, 110 insertions, 91 deletions
diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter11Test.java index d5b3cc47..fdf56b56 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -528,4 +528,38 @@ return s.f; assertEquals(1L, Evaluator.evaluate(stop, 1)); assertEquals(0L, Evaluator.evaluate(stop, 2)); } + + @Test + public void testScheduleUse() { + Parser parser = new Parser( +""" +int v0=0; +while(0>=0) { + int v1=0; + v1=v0; + if(v1*0) + v0=-v1; +} +return 0; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + } + + @Test + public void testLoopCarriedDep() { + Parser parser = new Parser( +""" +int v0=0; +{ + int v1=0; + while(v1) { + v1=1+(v0!=0); + v0=v1/0; + } +} +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + } } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter16/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index 9e0700d5..de6d65a3 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.node.*; import java.util.*; @@ -82,7 +81,7 @@ public class GraphVisualizer { // Just the Nodes first, in a cluster no edges sb.append(doCtrl ? "\tsubgraph cluster_Controls {\n" : "\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name for (Node n : all) { - if (n instanceof ProjNode || n instanceof CProjNode || n instanceof ScopeNode || n==Parser.XCTRL) + if (n instanceof ProjNode || n instanceof CProjNode || n instanceof ScopeMinNode || n==Parser.XCTRL) continue; // Do not emit, rolled into MultiNode or Scope cluster already if( _separateControlCluster && doCtrl && !(n instanceof CFGNode) ) continue; if( _separateControlCluster && !doCtrl && (n instanceof CFGNode) ) continue; @@ -156,27 +155,34 @@ public class GraphVisualizer { // Build a nested scope display, walking the _prev edge private void scope( StringBuilder sb, ScopeNode scope ) { sb.append("\tnode [shape=plaintext];\n"); - int level=1; - //for( int idx = scope._idxs.size()-1; idx>=0; idx-- ) { - // var syms = scope._idxs.get(idx); - // String scopeName = makeScopeName(scope, 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<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n"); - // // Add the scope level - // int scopeLevel = scope._idxs.size()-level; - // sb.append("\t\t\t<TR><TD BGCOLOR=\"cyan\">").append(scopeLevel).append("</TD>"); - // for(String name: syms.keySet()) - // sb.append("<TD PORT=\"").append(makePortName(scopeName, name)).append("\">").append(name).append("</TD>"); - // sb.append("</TR>\n"); - // sb.append("\t\t\t</TABLE>>];\n"); - // level++; - //} - //// Scope clusters nest, so the graphics shows the nested scopes, so - //// they are not closed as they are printed; so they just keep nesting. - //// We close them all at once here. - //sb.append( "\t}\n".repeat( level-1 ) ); // End all Scope clusters - throw TODO(); + int last = scope.nIns(); + int max = scope._lexSize.size(); + for( int i = 0; i < max; i++ ) { + int level = max-i-1; + String scopeName = makeScopeName(scope, level); + sb.append("\tsubgraph cluster_").append(scopeName).append(" {\n"); // Magic "cluster_" in the subgraph name + // Special for memory ScopeMinNode + if( level==0 ) { + ScopeMinNode n = scope.mem(); + sb.append("\t\t").append(n.uniqueName()).append(" [label=\"").append(n.glabel()).append("\"];\n"); + } + sb.append("\t\t").append(scopeName).append(" [label=<\n"); + sb.append("\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n"); + // Add the scope level + sb.append("\t\t\t<TR><TD BGCOLOR=\"cyan\">").append(level).append("</TD>"); + int lexStart=scope._lexSize.at(level); + for( int j=lexStart; j<last; j++ ) { + var v = scope._vars.at(j); + sb.append("<TD PORT=\"").append(makePortName(scopeName, v._name)).append("\">").append(v._name).append("</TD>"); + } + last = lexStart; + sb.append("</TR>\n"); + sb.append("\t\t\t</TABLE>>];\n"); + } + // Scope clusters nest, so the graphics shows the nested scopes, so + // they are not closed as they are printed; so they just keep nesting. + // We close them all at once here. + sb.append( "\t}\n".repeat( max ) ); // End all Scope clusters } private String makeScopeName(ScopeNode sn, int level) { return sn.uniqueName() + "_" + level; } @@ -232,29 +238,26 @@ public class GraphVisualizer { // Walk the scope edges private void scopeEdges( StringBuilder sb, ScopeNode scope ) { sb.append("\tedge [style=dashed color=cornflowerblue];\n"); - int level=1; - //for( int i = scope._idxs.size()-1; i>=0; i-- ) { - // var syms = scope._idxs.get(i); - // String scopeName = makeScopeName(scope, level); - // for( String name : syms.keySet() ) { - // int idx = syms.get(name); - // Node def = scope.in(idx); - // while( def instanceof ScopeNode lazy ) - // def = lazy.in(idx); - // if( def==null ) continue; - // sb.append("\t") - // .append(scopeName).append(":") - // .append('"').append(makePortName(scopeName, name)).append('"') // wrap port name with quotes because $ctrl is not valid unquoted - // .append(" -> "); - // if( def instanceof CProjNode proj ) { - // String mname = proj.ctrl().uniqueName(); - // sb.append(mname).append(":p").append(proj._idx); - // } else sb.append(def.uniqueName()); - // sb.append(";\n"); - // } - // level++; - //} - throw TODO(); + int level=0; + for( var v : scope._vars ) { + Node def = scope.in(v._idx); + while( def instanceof ScopeNode lazy ) + def = lazy.in(v._idx); + if( def==null ) continue; + while( level < scope._lexSize.size() && v._idx >= scope._lexSize.at(level) ) + level++; + String scopeName = makeScopeName(scope, level-1); + sb.append("\t") + .append(scopeName).append(":") + .append('"').append(makePortName(scopeName, v._name)).append('"') // wrap port name with quotes because $ctrl is not valid unquoted + .append(" -> "); + if( def instanceof CProjNode proj ) { + sb.append(def.in(0).uniqueName()).append(":p").append(proj._idx); + } else if( def instanceof ProjNode proj ) { + sb.append(def.in(0).uniqueName()).append(":p").append(proj._idx); + } else sb.append(def.uniqueName()); + sb.append(";\n"); + } } /** diff --git a/chapter16/src/main/java/com/seaofnodes/simple/Parser.java b/chapter16/src/main/java/com/seaofnodes/simple/Parser.java index b22bcab7..d2a1a9ae 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/Parser.java @@ -96,31 +96,15 @@ public class Parser { // Mapping from a type name to a Type. The string name matches // `type.str()` call. No TypeMemPtrs are in here, because Simple does not // have C-style '*ptr' references. - public static HashMap<String, Type> TYPES = new HashMap<>(); + public final HashMap<String, Type> TYPES; // Mapping from a type name to the constructor for a Type. - public static HashMap<String, StructNode> INITS = new HashMap<>(); + public final HashMap<String, StructNode> INITS; public Parser(String source, TypeInteger arg) { Node.reset(); IterPeeps.reset(); - TYPES.clear(); - TYPES.put("bool",TypeInteger.U1 ); - TYPES.put("byte",TypeInteger.U8 ); - TYPES.put("f32" ,TypeFloat .B32); - TYPES.put("f64" ,TypeFloat .BOT); - TYPES.put("flt" ,TypeFloat .BOT); - TYPES.put("i16" ,TypeInteger.I16); - TYPES.put("i32" ,TypeInteger.I32); - TYPES.put("i64" ,TypeInteger.BOT); - TYPES.put("i8" ,TypeInteger.I8 ); - TYPES.put("int" ,TypeInteger.BOT); - TYPES.put("u1" ,TypeInteger.U1 ); - TYPES.put("u16" ,TypeInteger.U16); - TYPES.put("u32" ,TypeInteger.U32); - TYPES.put("u8" ,TypeInteger.U8 ); - INITS.clear(); SCHEDULED = false; _lexer = new Lexer(source); _scope = new ScopeNode(); @@ -130,6 +114,8 @@ public class Parser { ZERO = con(0).keep(); XCTRL= new XCtrlNode().peephole().keep(); ALIAS = 2; // alias 0 for the control, 1 for memory + TYPES = defaultTypes(); + INITS = new HashMap<>(); } public Parser(String source) { @@ -139,6 +125,25 @@ public class Parser { @Override public String toString() { return _lexer.toString(); } + public static HashMap<String, Type> defaultTypes() { + return new HashMap<>() {{ + put("bool",TypeInteger.U1 ); + put("byte",TypeInteger.U8 ); + put("f32" ,TypeFloat .B32); + put("f64" ,TypeFloat .BOT); + put("flt" ,TypeFloat .BOT); + put("i16" ,TypeInteger.I16); + put("i32" ,TypeInteger.I32); + put("i64" ,TypeInteger.BOT); + put("i8" ,TypeInteger.I8 ); + put("int" ,TypeInteger.BOT); + put("u1" ,TypeInteger.U1 ); + put("u16" ,TypeInteger.U16); + put("u32" ,TypeInteger.U32); + put("u8" ,TypeInteger.U8 ); + }}; + } + // Debugging utility to find a Node by index public static Node find(int nid) { return START.find(nid); } @@ -295,6 +300,8 @@ public class Parser { // At exit the false control is the current control, and // the scope is the exit scope after the exit test. + _xScopes.pop(); + _xScopes.push(exit); return _scope = exit; } @@ -589,7 +596,6 @@ public class Parser { assert ts.str().equals(tname); TypeMemPtr tary = TypeMemPtr.make(ts); TYPES.put(tname,tary); - //START.addMemProj(ts, _scope); // Insert memory alias edges return tary; } @@ -839,10 +845,7 @@ public class Parser { int scale= ary.aryScale(); Node size = new AddNode(con(base),new ShlNode(len,con(scale)).peephole()).peephole(); ALTMP.clear(); ALTMP.add(len); ALTMP.add(con(ary._fields[1]._type.makeInit())); - Node ptr = newStruct(ary,size,0,ALTMP); - //int alias = ary._fields[0]._alias; // Length alias - //memAlias(alias,new StoreNode("#",alias,TypeInteger.BOT,memAlias(alias),ptr,con( ary.offset(0) ), len.unkeep(), true ).peephole()); - return ptr; + return newStruct(ary,size,0,ALTMP); } // We set up memory aliases by inserting special vars in the scope these diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/StructNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/StructNode.java index 4583e1ae..db170ab1 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/StructNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/StructNode.java @@ -25,27 +25,6 @@ public class StructNode extends Node { return sb.append("}"); } - // All fields fully initialized, or a sample not-initialized field - public String uninitField() { - for( int i=0; i<nIns(); i++ ) - if( in(i)==null ) - return _ts._fields[i]._fname; - return null; - } - - // If this is a mem struct, then alias inputs are made lazily. - // If missing, use Start.Mem instead. - Node alias( int alias ) { - return in( alias >= nIns() || in(alias)==null ? 1 : alias ); - } - - Node alias( int alias, Node st ) { - while( alias >= nIns() ) - addDef(null); - return setDef(alias,st); - } - - @Override public TypeStruct compute() { if( _ts==null ) return TypeStruct.BOT; diff --git a/chapter16/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/chapter16/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java index 7cd854bf..d3cbb0ee 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -109,7 +109,7 @@ public class ScriptGenerator { static { new Parser("", TypeInteger.BOT); - for( var e : Parser.TYPES.entrySet() ) { + for( var e : Parser.defaultTypes().entrySet() ) { if( e.getValue() instanceof TypeInteger ) { INTTYPES.add(new TypeInt(e.getKey())); } |