diff options
Diffstat (limited to 'chapter21/src')
36 files changed, 147 insertions, 1039 deletions
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter21/src/main/java/com/seaofnodes/simple/IterPeeps.java index 66e8a4a8..ded3da7e 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -2,7 +2,6 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.print.JSViewer; import java.util.Arrays; import java.util.BitSet; import java.util.Random; @@ -65,9 +64,14 @@ public class IterPeeps { while( (n=_work.pop()) != null ) { if( n.isDead() ) continue; cnt++; // Useful for debugging, searching which peephole broke things + var obs = CodeGen.CODE._obs; + if( obs != null ) obs.before(n); Node x = n.peepholeOpt(); if( x != null ) { - if( x.isDead() ) continue; + if( x.isDead() ) { + if( obs != null ) obs.after(n, x, true); + continue; + } // peepholeOpt can return brand-new nodes, needing an initial type set if( x._type==null ) x.setType(x.compute()); // Changes require neighbors onto the worklist @@ -86,11 +90,11 @@ public class IterPeeps { } // If there are distant neighbors, move to worklist n.moveDepsToWorklist(); - JSViewer.show(); // Show again assert progressOnList(code); // Very expensive assert } if( n.isUnused() && !(n instanceof StopNode) ) n.kill(); // Just plain dead + if( obs != null ) obs.after(n, x, true); } } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/Parser.java b/chapter21/src/main/java/com/seaofnodes/simple/Parser.java index 8e67ed10..adddbaa6 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/Parser.java @@ -2,7 +2,6 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.print.GraphVisualizer; import com.seaofnodes.simple.type.*; import java.text.ParseException; import java.util.*; @@ -132,8 +131,7 @@ public class Parser { private Node ctrl() { return _scope.ctrl(); } private <N extends Node> N ctrl(N n) { return _scope.ctrl(n); } - public void parse() { parse(false); } - public void parse(boolean show) { + public void parse() { _xScopes.push(_scope); _scope.define(ScopeNode.CTRL, Type.CONTROL , false, null, _lexer); _scope.define(ScopeNode.MEM0, TypeMem.BOT , false, null, _lexer); @@ -173,7 +171,6 @@ public class Parser { init.unkeep().kill(); INITS.clear(); stop.peephole(); - if( show ) showGraph(); } /** @@ -295,7 +292,6 @@ public class Parser { else if (matchx("break") ) return parseBreak(); else if (matchx("continue")) return parseContinue(); else if (matchx("struct") ) return parseStruct(); - else if (matchx("#showGraph")) return require(showGraph(),";"); else if (matchx(";") ) return null; // Empty statement // Break ambiguity around leading function types and starting a block else if (peek('{') && !isTypeFun() ) { @@ -596,14 +592,7 @@ public class Parser { return expr; } - /** - * Dumps out the node graph - * @return {@code null} - */ - Node showGraph() { - System.out.println(new GraphVisualizer().generateDotOutput(_code._stop,_scope,_xScopes)); - return null; - } + /** Parse: [name '='] expr */ diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 029e149b..4bfd3c5d 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple.codegen; +import com.seaofnodes.graph.GraphObserver; + import com.seaofnodes.simple.*; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.print.*; @@ -11,6 +13,7 @@ import java.util.IdentityHashMap; @SuppressWarnings("unchecked") public class CodeGen { + public GraphObserver<Node> _obs; public static final String PORTS = "com.seaofnodes.simple.node.cpus"; // Last created CodeGen as a global; used all over to avoid passing about a // "context". @@ -148,7 +151,7 @@ public class CodeGen { P.parse(); _tParse = (int)(System.currentTimeMillis() - t0); - JSViewer.show(); + if( _obs != null ) _obs.phase("Parse"); return this; } @@ -179,6 +182,7 @@ public class CodeGen { // Optimistic // TODO: // loop unroll, peel, RCE, etc + if( _obs != null ) _obs.phase("Opto"); return this; } public <N extends Node> N add( N n ) { return (N)_iter.add(n); } @@ -330,16 +334,14 @@ public class CodeGen { public Ary<CFGNode> _cfg = new Ary<>(CFGNode.class); // Global schedule (code motion) nodes - public CodeGen GCM() { return GCM(false); } - public CodeGen GCM( boolean show) { + public CodeGen GCM() { assert _phase.ordinal() <= Phase.InstSelect.ordinal(); _phase = Phase.Schedule; long t0 = System.currentTimeMillis(); GlobalCodeMotion.buildCFG(this); _tGCM = (int)(System.currentTimeMillis() - t0); - if( show ) - System.out.println(new GraphVisualizer().generateDotOutput(_stop,null,null)); + return this; } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/AddFNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/AddFNode.java index 792da62e..ba5815da 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/AddFNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/AddFNode.java @@ -10,8 +10,6 @@ public class AddFNode extends Node { @Override public String label() { return "AddF"; } - @Override public String glabel() { return "+"; } - @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/AddNode.java index dd128e76..c8701b5d 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -12,8 +12,6 @@ public class AddNode extends Node { @Override public String label() { return "Add"; } - @Override public String glabel() { return "+"; } - @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/AndNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/AndNode.java index 3cfcbda3..b425a6ce 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/AndNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/AndNode.java @@ -12,8 +12,6 @@ public class AndNode extends LogicalNode { @Override public String label() { return "And"; } @Override public String op() { return "&"; } - @Override public String glabel() { return "&"; } - @Override public Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 5f96c591..b2753fb1 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -18,9 +18,6 @@ abstract public class BoolNode extends Node { public String label() { return getClass().getSimpleName(); } @Override - public String glabel() { return op(); } - - @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); in(2)._print0(sb.append(op()), visited); @@ -107,7 +104,6 @@ abstract public class BoolNode extends Node { public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } public String op() { return "<" ; } - public String glabel() { return "<"; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( i1._max < i2._min ) return TRUE; if( i1._min >= i2._max ) return FALSE; @@ -120,7 +116,6 @@ abstract public class BoolNode extends Node { public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } public String op() { return "<="; } - public String glabel() { return "<="; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( i1._max <= i2._min ) return TRUE; if( i1._min > i2._max ) return FALSE; @@ -138,7 +133,6 @@ abstract public class BoolNode extends Node { public static class ULT extends BoolNode { public ULT(Node lhs, Node rhs) { super(lhs,rhs); } public String op() { return "u<" ; } - public String glabel() { return "u<"; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( Long.compareUnsigned(i1._max,i2._min) < 0 ) return TRUE; if( Long.compareUnsigned(i1._min,i2._max) >= 0 ) return FALSE; diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 3ffd430b..9785855b 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -36,8 +36,6 @@ public class ConstantNode extends Node { } @Override public String label() { return "#"+_con; } - @Override public String glabel() { return _con.gprint(new SB().p("#")).toString(); } - @Override public String uniqueName() { return "Con_" + _nid; } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/DivFNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/DivFNode.java index 633f3224..2180ab46 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/DivFNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/DivFNode.java @@ -10,8 +10,6 @@ public class DivFNode extends Node { @Override public String label() { return "DivF"; } - @Override public String glabel() { return "/"; } - @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/DivNode.java index 41518311..7aa98bf2 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -9,8 +9,6 @@ public class DivNode extends Node { @Override public String label() { return "Div"; } - @Override public String glabel() { return "//"; } - @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 785ba62c..80bf989c 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -23,11 +23,8 @@ public class LoadNode extends MemOpNode { super(loc, name, alias, true, glb, mem, ptr, off); } - // GraphVis DOT code (must be valid Java identifiers) and debugger labels + // Debugger label @Override public String label() { return "ld_"+mlabel(); } - // GraphVis node-internal labels - @Override public String glabel() { return "." +_name; } - @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(".").append(_name); } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/MinusFNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/MinusFNode.java index 99fc3144..bfdb41cc 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/MinusFNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/MinusFNode.java @@ -10,8 +10,6 @@ public class MinusFNode extends Node { @Override public String label() { return "MinusF"; } - @Override public String glabel() { return "-"; } - @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("(-"), visited); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/MinusNode.java index e06e0c69..64f471a8 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -11,8 +11,6 @@ public class MinusNode extends Node { @Override public String label() { return "Minus"; } - @Override public String glabel() { return "-"; } - @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("(-"), visited); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/MulFNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/MulFNode.java index 6fbf4bbb..0fc062cd 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/MulFNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/MulFNode.java @@ -10,8 +10,6 @@ public class MulFNode extends Node { @Override public String label() { return "MulF"; } - @Override public String glabel() { return "*"; } - @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/MulNode.java index 384dbace..7609f1d4 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -10,8 +10,6 @@ public class MulNode extends Node { @Override public String label() { return "Mul"; } - @Override public String glabel() { return "*"; } - @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/NewNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/NewNode.java index 5a8c1b6b..27f7d634 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -35,11 +35,7 @@ public class NewNode extends Node implements MultiNode { public Node mem (int idx) { return in(idx+2); } - @Override public String label() { return "new_"+glabel(); } - @Override public String glabel() { - return _ptr._obj.isAry() ? "ary_"+_ptr._obj._fields[1]._type.str() : _ptr._obj.str(); - } - + @Override public String label() { return "new_"+(_ptr._obj.isAry() ? "ary_"+_ptr._obj._fields[1]._type.str() : _ptr._obj.str()); } @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { sb.append("new "); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter21/src/main/java/com/seaofnodes/simple/node/Node.java index a83ca6c1..1b543c69 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/Node.java @@ -3,7 +3,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.*; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.print.IRPrinter; -import com.seaofnodes.simple.print.JSViewer; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeFloat; import com.seaofnodes.simple.type.TypeInteger; @@ -78,14 +77,12 @@ public abstract class Node implements Cloneable { // Easy reading label for debugger, e.g. "Add" or "Region" or "EQ" public abstract String label(); - // Unique label for graph visualization, e.g. "Add12" or "Region30" or "EQ99" + // Unique label for debugging, e.g. "Add12" or "Region30" or "EQ99" public String uniqueName() { - // Get rid of $ as graphviz doesn't like it - String label = label().replaceAll("\\$", ""); - return label + _nid; + return label() + _nid; } - // Graphical label, e.g. "+" or "Region" or "==" + // Operator symbol used by assembly/debug printing. public String glabel() { return label(); } // Extra fun stuff, for assembly printing. Jump labels, parser locations, @@ -371,13 +368,13 @@ public abstract class Node implements Cloneable { * Try to peephole at this node and return a better replacement Node. * Always returns some not-null Node (often this). */ - public final Node peephole( ) { - if( _type==null ) // Brand-new node, never peeped before - JSViewer.show(); + public final Node peephole() { + var obs = CodeGen.CODE._midAssert ? null : CodeGen.CODE._obs; + if( obs != null ) obs.before(this); Node n = peepholeOpt(); - if( n!=null ) // Made progress? - JSViewer.show(); // Show again - return n==null ? this : deadCodeElim(n._nid >= _nid ? n.peephole() : n); // Cannot return null for no-progress + Node rez = n == null ? this : deadCodeElim(n._nid >= _nid ? n.peephole() : n); + if( obs != null ) obs.after(this, n == null ? null : rez, false); + return rez; } /** @@ -540,6 +537,8 @@ public abstract class Node implements Cloneable { // retry the peephole. Track a set of Nodes dependent on `this`, and // revisit them if `this` changes. Ary<Node> _deps; + public int nDeps() { return _deps == null ? 0 : _deps.size(); } + public Node dep(int idx) { return _deps.get(idx); } /** * Add a node to the list of dependencies. Only add it if its not an input @@ -550,6 +549,8 @@ public abstract class Node implements Cloneable { // Running peepholes during the big assert cannot have side effects // like adding dependencies. if( CODE._midAssert ) return dep; + var obs = CodeGen.CODE._midAssert ? null : CodeGen.CODE._obs; + if( obs != null ) obs.dep(this, dep); if( dep._deps==null ) dep._deps = new Ary<>(Node.class); if( dep._deps .find(this) != -1 ) return dep; // Already on list if( dep._inputs .find(this) != -1 ) return dep; // No need for deps on immediate neighbors diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/NotNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/NotNode.java index 0314841d..118ef5c8 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -9,8 +9,6 @@ public class NotNode extends Node { @Override public String label() { return "Not"; } - @Override public String glabel() { return "!"; } - @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("(!"), visited); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/OrNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/OrNode.java index 9b03dc5d..5a87ce09 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/OrNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/OrNode.java @@ -12,8 +12,6 @@ public class OrNode extends LogicalNode { @Override public String label() { return "Or"; } @Override public String op() { return "|"; } - @Override public String glabel() { return "|"; } - @Override public Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/ParmNode.java index 9e11a129..0eb2e5f0 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -17,8 +17,6 @@ public class ParmNode extends PhiNode { @Override public String label() { return MemOpNode.mlabel(_label); } - @Override public String glabel() { return _label; } - public FunNode fun() { return (FunNode)in(0); } @Override diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 24a766d6..8ab40af6 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -26,8 +26,6 @@ public class PhiNode extends Node { @Override public String label() { return "Phi_"+MemOpNode.mlabel(_label); } - @Override public String glabel() { return "φ_"+_label; } - @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { if( !(region() instanceof RegionNode r) || r.inProgress() ) diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java b/chapter21/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java index 7936086d..2ad034d6 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java @@ -10,8 +10,6 @@ public class RoundF32Node extends Node { @Override public String label() { return "RoundF32"; } - @Override public String glabel() { return "(f32)"; } - @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { return in(1)._print0(sb.append("((f32)"), visited).append(")"); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/SarNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/SarNode.java index 4a71ec06..47091fed 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/SarNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/SarNode.java @@ -11,8 +11,6 @@ public class SarNode extends LogicalNode { @Override public String label() { return "Sar"; } @Override public String op() { return ">>"; } - @Override public String glabel() { return ">>"; } - @Override public Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/ShlNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/ShlNode.java index 82e01841..ad7d9978 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/ShlNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -11,8 +11,6 @@ public class ShlNode extends LogicalNode { @Override public String label() { return "Shl"; } @Override public String op() { return "<<"; } - @Override public String glabel() { return "<<"; } - @Override public Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/ShrNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/ShrNode.java index 789fb8a8..926bc993 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/ShrNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -11,8 +11,6 @@ public class ShrNode extends LogicalNode { @Override public String label() { return "Shr"; } @Override public String op() { return ">>>"; } - @Override public String glabel() { return ">>>"; } - @Override public Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/StoreNode.java index a6992f04..8878193c 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -24,10 +24,8 @@ public class StoreNode extends MemOpNode { _init = init; } - // GraphVis DOT code and debugger labels + // Debugger label @Override public String label() { return "st_"+mlabel(); } - // GraphVis node-internal labels - @Override public String glabel() { return "." +_name+"="; } @Override public boolean isMem() { return true; } public Node val() { return in(4); } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/SubFNode.java index 5c7e969f..73cf9de5 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/SubFNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/SubFNode.java @@ -10,8 +10,6 @@ public class SubFNode extends Node { @Override public String label() { return "SubF"; } - @Override public String glabel() { return "-"; } - @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/SubNode.java index 4290ff9b..51164dcc 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -10,8 +10,6 @@ public class SubNode extends Node { @Override public String label() { return "Sub"; } - @Override public String glabel() { return "-"; } - @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java index c098ad99..8ef5e40a 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java @@ -11,8 +11,6 @@ public class ToFloatNode extends Node { @Override public String label() { return "ToFloat"; } - @Override public String glabel() { return "(flt)"; } - @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { return in(1)._print0(sb.append("(flt)"), visited); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/XorNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/XorNode.java index 37d7147d..ef022a2c 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/XorNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/XorNode.java @@ -11,8 +11,6 @@ public class XorNode extends LogicalNode { @Override public String label() { return "Xor"; } @Override public String op() { return "^"; } - @Override public String glabel() { return "^"; } - @Override public Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; diff --git a/chapter21/src/main/java/com/seaofnodes/simple/print/GraphVisualizer.java b/chapter21/src/main/java/com/seaofnodes/simple/print/GraphVisualizer.java deleted file mode 100644 index e4cf2c31..00000000 --- a/chapter21/src/main/java/com/seaofnodes/simple/print/GraphVisualizer.java +++ /dev/null @@ -1,287 +0,0 @@ -package com.seaofnodes.simple.print; - -import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.node.*; -import java.util.*; -import static com.seaofnodes.simple.Utils.TODO; - -/** - * Simple visualizer that outputs GraphViz dot format. - * The dot output must be saved to a file and run manually via dot to generate the SVG output. - * Currently, this is done manually. - */ -public class GraphVisualizer { - - /** - * If set to true we put the control nodes in a separate cluster from - * data nodes. - */ - boolean _separateControlCluster = false; - - public GraphVisualizer(boolean separateControlCluster) { this._separateControlCluster = separateControlCluster; } - public GraphVisualizer() { this(false); } - - public String generateDotOutput(Parser parse) { return generateDotOutput(parse._code._stop,parse._scope,parse._xScopes); } - public String generateDotOutput(StopNode stop, Node scope, Stack<ScopeNode> xScopes) { - - // Since the graph has cycles, we need to create a flat list of all the - // nodes in the graph. - Collection<Node> all = findAll(xScopes, stop, scope); - StringBuilder sb = new StringBuilder(); - sb.append("digraph chapter18 {\n"); - sb.append("/*\n"); - sb.append(stop._src); - sb.append("\n*/\n"); - - // To keep the Scopes below the graph and pointing up into the graph we - // need to group the Nodes in a subgraph cluster, and the scopes into a - // different subgraph cluster. THEN we can draw edges between the - // scopes and nodes. If we try to cross subgraph cluster borders while - // still making the subgraphs DOT gets confused. - sb.append("\trankdir=BT;\n"); // Force Nodes before Scopes - - // CNC - turned off Apr/8/2024, gives more flex in the layout and - // removes some of the more ludicrous layout choices. - // Preserve node input order - //sb.append("\tordering=\"in\";\n"); - - // Merge multiple edges hitting the same node. Makes common shared - // nodes much prettier to look at. - sb.append("\tconcentrate=\"true\";\n"); - - // Force nested scopes to order - sb.append("\tcompound=\"true\";\n"); - - // Just the Nodes first, in a cluster no edges - nodes(sb, all); - - // Now the scopes, in a cluster no edges - if( xScopes != null ) - for( ScopeNode xscope : xScopes ) - if( !xscope.isDead() ) - scope( sb, xscope ); - - // Walk the Node edges - nodeEdges(sb, all); - - // Walk the active Scope edges - if( xScopes != null ) - for( ScopeNode xscope : xScopes ) - if( !xscope.isDead() ) - scopeEdges( sb, xscope ); - - sb.append("}\n"); - return sb.toString(); - } - - private void nodesByCluster(StringBuilder sb, boolean doCtrl, Collection<Node> all) { - if (!_separateControlCluster && doCtrl) // all nodes in 1 cluster - return; - // 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 MemMergeNode || 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; - sb.append("\t\t").append(n.uniqueName()).append(" [ "); - String lab = n.glabel(); - if (n instanceof MultiNode) { - // Make a box with the MultiNode on top, and all the projections on the bottom - sb.append("shape=plaintext label=<\n"); - sb.append("\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\" CELLPADDING=\"4\">\n"); - sb.append("\t\t\t<TR><TD BGCOLOR=\"yellow\">").append(lab).append("</TD></TR>\n"); - sb.append("\t\t\t<TR>"); - boolean doProjTable = false; - n._outputs.sort((x,y) -> x instanceof ProjNode xp && y instanceof ProjNode yp ? (xp._idx - yp._idx) : (x._nid - y._nid)); - for (Node use : n._outputs) { - if (use instanceof ProjNode proj) { - if (!doProjTable) { - doProjTable = true; - sb.append("<TD>").append("\n"); - sb.append("\t\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">").append("\n"); - sb.append("\t\t\t\t<TR>"); - } - sb.append("<TD PORT=\"p").append(proj._idx).append("\">").append(proj.glabel()).append("</TD>"); - } - if (use instanceof CProjNode proj) { - if (!doProjTable) { - doProjTable = true; - sb.append("<TD>").append("\n"); - sb.append("\t\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">").append("\n"); - sb.append("\t\t\t\t<TR>"); - } - sb.append("<TD PORT=\"p").append(proj._idx).append("\" BGCOLOR=\"yellow\">").append(proj.glabel()).append("</TD>"); - } - } - if (doProjTable) { - sb.append("</TR>").append("\n"); - sb.append("\t\t\t\t</TABLE>").append("\n"); - sb.append("\t\t\t</TD>"); - } - sb.append("</TR>\n"); - sb.append("\t\t\t</TABLE>>\n\t\t"); - - } else { - // control nodes have box shape - // other nodes are ellipses, i.e. default shape - if( n instanceof CFGNode ) sb.append("shape=box style=filled fillcolor=yellow "); - else if (n instanceof PhiNode) sb.append("style=filled fillcolor=lightyellow "); - sb.append("label=\"").append(lab).append("\" "); - } - sb.append("];\n"); - } - if (!_separateControlCluster) { - // Force Region & Phis to line up - for (Node n : all) { - if (n instanceof RegionNode region) { - sb.append("\t\t{ rank=same; "); - sb.append(region.uniqueName()).append(";"); - for (Node phi : region._outputs) - if (phi instanceof PhiNode) sb.append(phi.uniqueName()).append(";"); - sb.append("}\n"); - } - } - } - sb.append("\t}\n"); // End Node cluster - } - - private void nodes(StringBuilder sb, Collection<Node> all) { - nodesByCluster(sb, true, all); - nodesByCluster(sb, false, all); - } - - // Build a nested scope display, walking the _prev edge - private void scope( StringBuilder sb, ScopeNode scope ) { - sb.append("\tnode [shape=plaintext];\n"); - 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 ) { - MemMergeNode 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; } - private String makePortName(String scopeName, String varName) { return scopeName + "_" + varName; } - - // Walk the node edges - private void nodeEdges(StringBuilder sb, Collection<Node> all) { - // All them edge labels - sb.append("\tedge [ fontname=Helvetica, fontsize=8 ];\n"); - for( Node n : all ) { - // Do not display the Constant->Start edge; - // ProjNodes handled by Multi; - // ScopeNodes are done separately - if( n instanceof ConstantNode || n instanceof ProjNode || n instanceof CProjNode || n instanceof ScopeNode || n==Parser.XCTRL ) - continue; - for( int i=0; i<n.nIns(); i++ ) { - Node def = n.in(i); - if( n instanceof PhiNode && def instanceof RegionNode ) { - // Draw a dotted use->def edge from Phi to Region. - sb.append('\t').append(n.uniqueName()); - sb.append(" -> "); - sb.append(def.uniqueName()); - sb.append(" [style=dotted taillabel=").append(i).append("];\n"); - } else if( def != null ) { - // Most edges land here use->def - sb.append('\t').append(n.uniqueName()).append(" -> "); - if( def instanceof CProjNode proj ) { - String mname = proj.ctrl().uniqueName(); - sb.append(mname).append(":p").append(proj._idx); - } else if( def instanceof ProjNode proj ) { - String mname = proj.in(0).uniqueName(); - sb.append(mname).append(":p").append(proj._idx); - } else sb.append(def.uniqueName()); - // Number edges, so we can see how they track - sb.append("[taillabel=").append(i); - // The edge from New to ctrl is just for anchoring the New - if ( n instanceof NewNode ) - sb.append(" color=green"); - // control edges are colored red - else if( def instanceof CFGNode ) - sb.append(" color=red"); - else if( def.isMem() ) - sb.append(" color=blue"); - // Backedges do not add a ranking constraint - if( i==2 && (n instanceof PhiNode || n instanceof LoopNode) ) - sb.append(" constraint=false"); - sb.append("];\n"); - } - } - } - } - - // Walk the scope edges - private void scopeEdges( StringBuilder sb, ScopeNode scope ) { - sb.append("\tedge [style=dashed color=cornflowerblue];\n"); - 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"); - } - } - - /** - * Finds all nodes in the graph. - */ - public static Collection<Node> findAll(Stack<ScopeNode> ss, Node... ns) { - final HashMap<Integer, Node> all = new HashMap<>(); - for( Node n : ns ) - walk(all, n); - if( ss != null ) - for( Node n : ss ) - walk(all, n); - return all.values(); - } - - /** - * Walk a subgraph and populate distinct nodes in the all list. - */ - private static void walk(HashMap<Integer,Node> all, Node n) { - if(n == null ) return; - if (all.get(n._nid) != null) return; // Been there, done that - all.put(n._nid, n); - for (Node c : n._inputs) - walk(all, c); - for( Node c : n._outputs ) - walk(all, c); - } -} diff --git a/chapter21/src/main/java/com/seaofnodes/simple/print/JSViewer.java b/chapter21/src/main/java/com/seaofnodes/simple/print/JSViewer.java deleted file mode 100644 index c1a1d7e2..00000000 --- a/chapter21/src/main/java/com/seaofnodes/simple/print/JSViewer.java +++ /dev/null @@ -1,421 +0,0 @@ -package com.seaofnodes.simple.print; - -import com.seaofnodes.simple.SB; -import com.seaofnodes.simple.Utils; -import com.seaofnodes.simple.codegen.CodeGen; -import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.type.*; -import java.io.IOException; -import java.nio.file.Paths; -import java.nio.file.Files; -import java.nio.file.Path; -import java.net.URI; -import java.util.Collection; -import java.util.Stack; -import static com.seaofnodes.simple.codegen.CodeGen.CODE; - -public class JSViewer implements AutoCloseable { - // Display programs in an endless loop - public static void main( String[] args ) throws Exception { - try(var js = new JSViewer()) { - js.run(); - } - } - - static boolean SHOW; - - // WebSocket to the browser for display - static SimpleWebSocket SERVER; - - static int N; // Dot frames - - JSViewer() throws Exception { - // Launch server; handshake - SERVER = new SimpleWebSocket(viewerURI(),12345); - } - - // The browser application is shared by all chapters. Search upwards so - // chapter, repository-root, and linearized checkouts use the same assets. - static URI viewerURI() throws IOException { - String url = System.getProperty("simple.graph.url"); - if( url != null ) return URI.create(url); - for( Path dir = Paths.get("").toAbsolutePath(); dir != null; dir = dir.getParent() ) { - Path page = dir.resolve("graph/web/index.html"); - if( Files.isRegularFile(page) ) return page.toUri(); - } - throw new IOException("Cannot find graph/web/index.html; run inside the Simple checkout " - + "or set -Dsimple.graph.url=<viewer URL>"); - } - - void run( ) throws Exception { - SERVER.put("!"); - while( true ) { - String src = SERVER.get(); - switch( src ) { - case null: return; - case "null": return; - case "+": break; // Client requests more frames, but we send them all anyway - default: - System.out.println(src); - try { - N=0; - // Use parser scope, xscope when building views - CodeGen code = new CodeGen(src); - SHOW = true; - show(); - // Parse program, generating views at every parse point - code.parse(); - // No longer user parse internal state when building views - code.opto(); - - // Catch and ignore Parser errors - } catch(RuntimeException re) { - System.err.println(re); - } finally { - SHOW = false; - SERVER.put("#"); // Final frame - } - break; - } - } - } - - @Override public void close() throws IOException { - SERVER.close(); - SERVER=null; - } - - public static void show() { if( SERVER!=null && SHOW ) _show(); } - private static void _show() { - // Skip util we at least get the Parse object made - if( CODE._phase==null || CODE._phase.ordinal() < CodeGen.Phase.Parse.ordinal() ) - return; - boolean midParse = CODE._phase == CodeGen.Phase.Parse; - Stack<ScopeNode> xScopes = midParse ? CODE.P._xScopes : null; - - Collection<Node> all = GraphVisualizer.findAll(xScopes, CODE._stop, midParse ? CODE.P._scope: null); - SB sb = new SB(); - sb.p("digraph view_").p(N++).p(" {\n").ii(); - if( midParse ) - sb.i().p("// POS: ").p(CODE.P.pos()).nl(); - - // To keep the Scopes below the graph and pointing up into the graph we - // need to group the Nodes in a subgraph cluster, and the scopes into a - // different subgraph cluster. THEN we can draw edges between the - // scopes and nodes. If we try to cross subgraph cluster borders while - // still making the subgraphs DOT gets confused. - sb.i().p("rankdir=BT;\n"); // Force Nodes before Scopes - - // CNC - turned off Apr/8/2024, gives more flex in the layout and - // removes some of the more ludicrous layout choices. - // Preserve node input order - //sb.append("ordering=\"in\";\n"); - - // Merge multiple edges hitting the same node. Makes common shared - // nodes much prettier to look at. - sb.i().p("concentrate=\"true\";\n"); - - // Force nested scopes to order - sb.i().p("compound=\"true\";\n"); - - // Just the Nodes first, in a cluster no edges - nodes(sb, all); - - // Now the scopes, in a cluster no edges - if( midParse ) - for( ScopeNode xscope : xScopes ) - if( !xscope.isDead() ) - scope( sb, xscope ); - - // Walk the Node edges - nodeEdges(sb, midParse && !xScopes.empty() ? xScopes.peek() : null, all); - - // Walk the active Scope edges - if( midParse ) - for( ScopeNode xscope : xScopes ) - if( !xscope.isDead() ) - scopeEdges( sb, xscope ); - - - sb.p("}\n").di(); - // Tell client another DOT frame - String dot = sb.toString(); - System.out.println(dot); - try { - SERVER.put(dot); - } catch( IOException ioe ) { - try { SERVER.close();} catch( IOException ignored ){} - } - } - - - private static void nodes(SB sb, Collection<Node> all) { - // Just the Nodes first, in a cluster no edges - sb.i().p("subgraph cluster_Nodes {\n").ii(); // Magic "cluster_" in the subgraph name - for( Node n : all ) { - if( n instanceof ProjNode || n instanceof CProjNode || n instanceof MemMergeNode ) - continue; // Do not emit, rolled into MultiNode or Scope cluster already - sb.i().p(n.uniqueName()).p(" [ "); - if( n instanceof MultiNode && !(n instanceof StartNode) ) { - // Make a box with the MultiNode on top, and all the projections on the bottom - sb. p("shape=plaintext label=<\n").ii(); - sb.i().p("<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\" CELLPADDING=\"4\">\n"); - // Row over single cell for node label - cell(sb.i().p("<TR>"), n.glabel(), n, null).p("</TR>\n"); - // Row over single cell, for nested table - sb.i().p("<TR><TD>\n").ii(); - sb.i().p("<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">").p("\n"); - sb.i().p("<TR>"); - n._outputs.sort((x,y) -> x instanceof ProjNode xp && y instanceof ProjNode yp ? (xp._idx - yp._idx) : ((x==null ? 99999 : x._nid) - (y==null ? 99999 : y._nid))); - boolean empty_row=true; - for( Node use : n._outputs ) { - int idx = idx(n); - if( idx != -1 ) { - cell(sb,use.glabel(),use,"p"+idx); - empty_row=false; - } - } - // At least one cell on row - if( empty_row ) sb.p("<TD></TD>"); - sb. p("</TR>").p("\n"); - sb.i().p("</TABLE>").p("\n").di(); - sb.i().p("</TD></TR>\n"); - sb.i().p("</TABLE>>\n").di(); - sb.i().p("];\n"); - - } else { - // control nodes have box shape - // other nodes are ellipses, i.e. default shape - //else if (n instanceof PhiNode) sb.p("style=filled fillcolor=lightyellow "); - node(sb,n.glabel(),n); - sb.p("];\n"); - } - } - // Force Region & Phis to line up - for (Node n : all) { - if (n instanceof RegionNode region) { - sb.i().p("{ rank=same; "); - sb.p(region.uniqueName()).p(";"); - for (Node phi : region._outputs) - if (phi instanceof PhiNode) sb.p(phi.uniqueName()).p(";"); - sb.p("}\n"); - } - } - sb.di().i().p("}").nl(); // End Node cluster - } - - // Build a nested scope display, walking the _prev edge - private static void scope( SB sb, ScopeNode scope ) { - sb.i().p("node [shape=plaintext];\n"); - int last = scope.nIns(); - int max = scope._lexSize.size()+1; // One more than lexsize - for( int i = 0; i < max; i++ ) { - int level = max-i-1; - String scopeName = makeScopeName(scope, level); - sb.i().p("subgraph cluster_").p(scopeName).p(" {\n").ii(); // Magic "cluster_" in the subgraph name - sb.i().p(scopeName).p(" [label=<\n").ii(); - sb.i().p("<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n"); - int lexStart = level==0 ? 0 : scope._lexSize.at(level-1); - - // Special for memory ScopeMinNode - MemMergeNode n = scope.nIns()>1 ? scope.mem() : null; - if( level==0 && n!=null && n.nIns()>2 ) { - sb.i().p("<TR>"); - for( int m=2; m<n.nIns(); m++ ) - cell(sb,"#"+m,n.alias(m),"m"+m); - sb.p("</TR>\n"); // End scope level - } - - // Scope variables, empty if none - if( lexStart<last ) { - sb.i().p("<TR>\n"); - for( int j=lexStart; j<last; j++ ) { - if( scope.in(j)==null ) continue; - var v = scope._vars.at(j); - cell(sb.i(),v._name,scope.in(j),makePortName(scopeName, v._name)).nl(); - } - last = lexStart; - sb.i().p("</TR>\n"); - } - sb.i().p("</TABLE>>];\n").di(); - // Scope label - sb.i().p(scopeName).p("A [label=\"").p(level).p("\" shape=doublecircle style=filled fillcolor=aqua fontsize=10 margin=0 width=0.2 ];\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. - for( int i=0; i<max; i++ ) - sb.di().i().p("}\n"); - } - - // Append a cell, with color - private static SB cell(SB sb, String text, Node n, String port) { - sb.p("<TD"); - String color = color(n); - sb.p(" BGCOLOR=\"").p(color).p("\""); - if( port!=null ) sb.p(" PORT=\"").p(port).p("\""); - return colorcell(sb.p(">"),text,n,dark(color)).p("</TD>"); - } - private static SB node(SB sb, String text, Node n) { - String color = color(n); - sb.p("style=filled fillcolor=").p(color).p(" "); - String shape = switch( n ) { - case FunNode fun -> "shape=box peripheries=2"; - case CFGNode cfg -> "shape=box"; - default -> ""; - }; - sb.p(shape).p(" "); - return colorcell(sb.p("label=<"),text,n,dark(color)).p(">"); - } - - private static String color(Node n) { - return switch( n ) { - case CFGNode cfg -> "yellow"; - case NewNode nnn -> "lightgreen"; - case StructNode s -> "lightgreen"; - default -> typeColor(n._type); - }; - } - private static String typeColor(Type t) { - return t==null ? "white" : switch( t ) { - case TypeMem mem -> "blue"; - case TypeMemPtr tmp -> "green"; - case TypeFunPtr tfp -> "orange"; - case TypeRPC rpc -> "antiquewhite"; - case TypeInteger ti -> "lightblue"; - case TypeFloat tf -> "aqua"; - case Type tn -> tn==Type.NIL ? "lightgray" : "red"; - }; - } - private static final String[] DARKS = new String[]{"blue","green","black"}; - private static boolean dark(String color) { return Utils.find(DARKS,color) != -1; } - - - - // Called with an open div - private static SB colorcell(SB sb, String text, Node n, boolean dark) { - if( dark ) sb.p("<font color=\"white\">"); - sb.p(text); - if( n._type!=null ) { - sb.p("<br /><font point-size=\"10\">"); - n._type.gprint(sb); - sb.p("</font>"); - } - if( dark ) sb.p("</font>"); - return sb; - } - - - private static String makeScopeName(ScopeNode sn, int level) { return sn.uniqueName() + "_" + level; } - private static String makePortName(String scopeName, String varName) { return scopeName + "_" + varName; } - - // Walk the node edges - private static void nodeEdges(SB sb, ScopeNode scope, Collection<Node> all) { - // All them edge labels - String scopeName = scope!=null ? makeScopeName(scope, 0) : null; - sb.i().p("edge [ fontname=Helvetica, fontsize=8 ];\n"); - for( Node n : all ) { - // Do not display the Constant->Start edge; - if( n instanceof ConstantNode || - n instanceof XCtrlNode || - // ProjNodes handled by Multi; - n instanceof ProjNode || - n instanceof CProjNode || - // ScopeNodes are done separately - n instanceof ScopeNode || - n instanceof MemMergeNode - ) - continue; - if( n.isDead() ) - throw Utils.TODO(); - // Normal edges - for( int i=0; i<n.nIns(); i++ ) { - Node def = n.in(i); - if( def==null ) continue; - sb.i().p(n.uniqueName()).p(" -> "); - if( n instanceof PhiNode && def instanceof RegionNode ) { - // Draw a dotted use->def edge from Phi to Region. - sb.p(def.uniqueName()); - sb.p(" [style=dotted taillabel=").p(i).p("];\n"); - } else { - // Most edges land here use->def - if( def instanceof CProjNode proj ) { - String mname = proj.ctrl().uniqueName(); - sb.p(mname).p(":p").p(proj._idx); - } else if( def instanceof ProjNode proj ) { - String mname = proj.in(0).uniqueName(); - sb.p(mname).p(":p").p(proj._idx); - } else sb.p(def.uniqueName()); - // Number edges, so we can see how they track - sb.p("[taillabel=").p(i); - // Color the edge - nodeEdgeColor(sb,def._type); - // Backedges do not add a ranking constraint - if( i==2 && (n instanceof PhiNode || n instanceof LoopNode) ) - sb.p(" constraint=false"); - sb.p("];\n"); - } - } - - // Bonus edge if hooked by parser - if( (n.iskeep() || n.isUnused()) && scopeName != null ) { - sb.i().p(scopeName).p(" -> ").p(n.uniqueName()).p(" [ style=dashed color=grey];\n"); - } - // Force functions above return - if( n instanceof ReturnNode ret && ret.inProgress() && !ret.fun().isDead() ) - sb.i().p(ret.ctrl().uniqueName()).p(" -> ").p(ret.fun().uniqueName()).p("[style=invis]\n"); - } - } - - private static void nodeEdgeColor(SB sb, Type t) { - sb.p(" color=").p(typeColor(t)); - } - - // Walk the scope edges - private static void scopeEdges( SB sb, ScopeNode scope ) { - sb.i().p("edge [style=dashed color=cornflowerblue];\n"); - int level=0; - for( var v : scope._vars ) { - if( v._idx==1 ) continue; // Memory done separately - 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); - sb.i() - .p(scopeName).p(":") - .p('"').p(makePortName(scopeName, v._name)).p('"') // wrap port name with quotes because $ctrl is not valid unquoted - .p(" -> "); - defPort(sb,def).p(";\n"); - } - - // Memory - if( scope.nIns()>1 ) { - MemMergeNode n = scope.mem(); - for( int i=2; i<n.nIns(); i++ ) { - Node def = n.in(i); - while( def instanceof ScopeNode lazy ) - def = lazy.in(i); - if( def==null ) continue; - String scopeName = makeScopeName(scope, 0); - sb.i().p(scopeName).p(":m").p(i).p(" -> "); - defPort(sb,def).p(";\n"); - } - } - - } - - // (C)Projection index or -1 - private static int idx(Node n) { - return n instanceof ProjNode p ? p._idx : (n instanceof CProjNode cp ? cp._idx : -1); - } - - private static SB defPort(SB sb, Node def) { - int idx = idx(def); - return idx != -1 - ? sb.p(def.in(0).uniqueName()).p(":p").p(idx) - : sb.p(def.uniqueName()); - } -} diff --git a/chapter21/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/chapter21/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java new file mode 100644 index 00000000..73967e05 --- /dev/null +++ b/chapter21/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -0,0 +1,64 @@ +package com.seaofnodes.simple.print; + +import com.seaofnodes.graph.GraphAdapter; +import com.seaofnodes.graph.GraphSnapshot; +import com.seaofnodes.graph.GraphSnapshot.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.type.TypeMem; +import java.util.ArrayList; + +/** Chapter 21's view of the IR; browser, transport and layout are shared. */ +public class SimpleGraphAdapter extends GraphAdapter<Node> { + @Override protected boolean dead(Node n) { return n.isDead(); } + @Override protected int id(Node n) { return n._nid; } + @Override protected int nIns(Node n) { return n.nIns(); } + @Override protected Node in(Node n, int idx) { return n.in(idx); } + @Override protected int nOuts(Node n) { return n.nOuts(); } + @Override protected Node out(Node n, int idx) { return n.out(idx); } + @Override protected int nDeps(Node n) { return n.nDeps(); } + @Override protected Node dep(Node n, int idx) { return n.dep(idx); } + + private ArrayList<Edge> edges(Node n) { + var edges = new ArrayList<Edge>(); + for( int i = 0; i < n.nIns(); i++ ) { + String name = n instanceof ScopeNode scope && i < scope._vars.size() + ? scope._vars.get(i)._name : null; + edges.add(new Edge(i, ref(n.in(i)), role(n, i), name)); + } + return edges; + } + + @Override protected GraphSnapshot.Node desc(Node n) { + Projection proj = n instanceof ProjNode p ? new Projection(ref(n.in(0)), p._idx) + : n instanceof CProjNode p ? new Projection(ref(n.in(0)), p._idx) : null; + String label = n.label(); + return new GraphSnapshot.Node(n._nid, label == null ? n.getClass().getSimpleName() : label, + n._type == null ? null : n._type.toString(), kind(n), edges(n), proj); + } + + private Kind kind(Node n) { + if( n instanceof ScopeNode ) return Kind.SCOPE; + if( n instanceof FunNode ) return Kind.FUN; + if( n instanceof StartNode ) return Kind.CTRL; + if( n instanceof LoopNode ) return Kind.LOOP; + if( n instanceof RegionNode ) return Kind.REGION; + if( n instanceof PhiNode ) return Kind.PHI; + return n instanceof CFGNode ? Kind.CTRL : isMem(n) ? Kind.MEM : Kind.DATA; + } + + private Role role(Node n, int i) { + if( n instanceof ScopeNode || n instanceof ConstantNode || n instanceof CtrlNode || n instanceof XCtrlNode ) return Role.ASSOC; + if( n instanceof PhiNode ) return i == 0 ? Role.ASSOC : isMem(n) ? Role.MEM : Role.DATA; + if( n instanceof ProjNode || n instanceof CProjNode ) + return n instanceof CFGNode ? Role.CTRL : isMem(n) ? Role.MEM : Role.DATA; + if( n instanceof RegionNode && i == 0 ) return Role.ASSOC; + if( i == 0 || n instanceof RegionNode || n instanceof StopNode ) return Role.CTRL; + if( n instanceof MemMergeNode || i == 1 && (n instanceof MemOpNode || n instanceof ReturnNode || n instanceof CallNode) ) return Role.MEM; + Node def = n.in(i); + if( def != null && isMem(def) ) return Role.MEM; + return Role.DATA; + } + + private boolean isMem(Node n) { return n.isMem() || n._type instanceof TypeMem; } +} diff --git a/chapter21/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/chapter21/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java new file mode 100644 index 00000000..b04c58a2 --- /dev/null +++ b/chapter21/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -0,0 +1,35 @@ +package com.seaofnodes.simple.print; + +import com.seaofnodes.graph.GraphCapture; +import com.seaofnodes.graph.GraphViewer; +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.Node; +import java.util.ArrayList; +import java.io.IOException; + +/** Chapter 21's compilation context; capture and event bookkeeping are shared. */ +public class SimpleGraphObserver extends GraphCapture<Node> { + private CodeGen _code; + public SimpleGraphObserver() { super(new SimpleGraphAdapter()); } + public static void main(String[] args) throws IOException { + GraphViewer.run(new SimpleGraphObserver()); + } + @Override protected void compile(String src) { + _code = new CodeGen(src); + _code._obs = this; + _code.parse().opto(); + } + @Override protected String phase() { return _code._phase.name(); } + @Override protected int pos() { return _code._phase == CodeGen.Phase.Parse ? _code.P.pos() : -1; } + @Override protected void detach() { + if( _code != null ) _code._obs = null; + _code = null; + } + @Override protected void roots(ArrayList<Node> roots) { + roots.add(_code._stop); + if( _code._phase == CodeGen.Phase.Parse ) { + roots.add(_code.P._scope); + roots.addAll(_code.P._xScopes); + } + } +} diff --git a/chapter21/src/main/java/com/seaofnodes/simple/print/SimpleWebSocket.java b/chapter21/src/main/java/com/seaofnodes/simple/print/SimpleWebSocket.java deleted file mode 100644 index e1b893f1..00000000 --- a/chapter21/src/main/java/com/seaofnodes/simple/print/SimpleWebSocket.java +++ /dev/null @@ -1,193 +0,0 @@ -package com.seaofnodes.simple.print; - -import com.seaofnodes.simple.Utils; -import java.io.*; -import java.net.ServerSocket; -import java.net.Socket; -import java.net.URI; -import java.nio.charset.StandardCharsets; -import java.security.MessageDigest; -import java.security.NoSuchAlgorithmException; -import java.util.Base64; -import java.net.InetSocketAddress; -import java.nio.file.Path; -import com.sun.net.httpserver.HttpServer; -import com.sun.net.httpserver.SimpleFileServer; - -// Why-Oh-Why is this needed? - -// Pass in a URI and a port. -// Opens the client; client has to open a websocket at the given port. -// Connects, handshakes. -// Thereafter you can call get/put to swap frames with client. - -class SimpleWebSocket extends ServerSocket { - final InputStream _in; - final OutputStream _out; - private HttpServer _http; - private Socket _client; - - SimpleWebSocket(URI uri, int port) throws IOException, NoSuchAlgorithmException { - super(port); - try { - // Use an ordinary web URL; desktop dispatch of file: URLs can silently - // raise the browser without opening the page. - if( "file".equals(uri.getScheme()) ) { - Path page = Path.of(uri); - _http = SimpleFileServer.createFileServer( - new InetSocketAddress("127.0.0.1",0), page.getParent(), - SimpleFileServer.OutputLevel.NONE); - _http.start(); - uri = URI.create("http://127.0.0.1:" + _http.getAddress().getPort() - + "/" + page.getFileName()); - } - // Print the address even if the desktop silently fails to open a tab. - System.out.println("Graph viewer: " + uri); - if( Boolean.parseBoolean(System.getProperty("simple.graph.open", "true")) ) - java.awt.Desktop.getDesktop().browse(uri); - // Look for client; get in/out streams - Socket sock = accept(); - _client = sock; - _in = sock. getInputStream(); - _out = sock.getOutputStream(); - - - // Establish web socket with handshake; easier with a buffered reader - BufferedReader br = new BufferedReader(new InputStreamReader(_in, StandardCharsets.US_ASCII)); - String key = null; - // TCP can deliver the request in several chunks. ready() is not an - // end-of-headers test; wait for the terminating empty line. - String line; - while( (line = br.readLine()) != null && !line.isEmpty() ) { - if( line.startsWith("Sec-WebSocket-Key: ") ) - key = line.substring(19); - } - if( key==null || line==null ) { - sock.close(); - super.close(); - throw new IOException("Incomplete WebSocket upgrade request"); - } - // Magic handshake - byte[] response = ("HTTP/1.1 101 Switching Protocols\r\n" - + "Connection: Upgrade\r\n" - + "Upgrade: websocket\r\n" - + "Sec-WebSocket-Accept: " - + Base64.getEncoder().encodeToString(MessageDigest.getInstance("SHA-1").digest((key + "258EAFA5-E914-47DA-95CA-C5AB0DC85B11").getBytes( StandardCharsets.UTF_8 ))) - + "\r\n\r\n").getBytes( StandardCharsets.UTF_8 ); - _out.write(response,0,response.length); - _out.flush(); - } catch( IOException | NoSuchAlgorithmException | RuntimeException | Error failure ) { - if( _http != null ) _http.stop(0); - if( _client != null ) { - try { _client.close(); } catch( IOException ignored ) {} - } - try { super.close(); } catch( IOException ignored ) {} - throw failure; - } - } - - final byte[] _ins = new byte[1024]; - final byte[] _str = new byte[1024]; - final byte[] _key = new byte[4]; - int _x, _len; - private int rawget() { assert _x<_len; return _ins[_x++]&0xFF; } - - // TODO: Flip to Direct Byte Buffer, this is just a poor-mans version - private void flipRead() throws IOException { - // Move _x to _len to offset 0 - System.arraycopy(_ins,_x,_ins,0,(_len-_x)); - _len = _len-_x; - _x=0; - // Read more - int len = _in.read(_ins,_len,_ins.length-_len); - if( len == -1 ) - throw Utils.TODO(); // EOF - _len += len; - } - // Block until you read at least len - private void atLeast(int len) throws IOException { - if( _x+len <= _len ) return; - flipRead(); - } - - - // Classic read from browser client. Encoded, so decoded here - public String get() throws IOException { - atLeast(1); // Need 1 byte for opcode - int op = rawget(); - if( (op&0x80)!=0x80 ) // FIN bit not set? - throw Utils.TODO( "Multi-part from client: " + op ); // Multipart message - op &= 0x7F; // Strip FIN bit - switch( op&15) { - case 1: { - atLeast(5); // Min message length - // Message length - int len = rawget()-128; - if( len > 125 ) { - if( len > 126 ) - throw Utils.TODO(); // Multi-byte length - len = (rawget()<<8) | rawget(); - } - atLeast(len+4); // Rest of message - // Encoding key - _key[0] = (byte)rawget(); - _key[1] = (byte)rawget(); - _key[2] = (byte)rawget(); - _key[3] = (byte)rawget(); - - // Decode bytes - for( int i=0; i<len; i++ ) - _str[i] = (byte)(rawget() ^ _key[i & 3]); - - return new String(_str,0,len); - } - // Client closes - case 8: return null; - // Ping - case 9: - // Send a PONG back. TODO: echo PING data in the PONG - _out.write(0x8A); // FIN + PONG - _out.write(0x00); // LENGTH==0 - return get(); - // Not (yet) implemented: continuation frames, ping/pong - default: - throw Utils.TODO("Unexpected op from client: "+op); // Multi-part message - } - } - - // Classic put to browser client. No encoding. - public void put(String msg) throws IOException { - int len = msg.length(); - if( len <= 125 ) { - _out.write(129); // FIN, opcode 1 - whole text message - _out.write(len); - for( int i=0; i<msg.length(); i++ ) - _out.write(msg.charAt(i)); - return; - } - if( len > 65535 ) - throw Utils.TODO("MOAR LENGTH"); - _out.write(129); // FIN, opcode 1 - whole text message - _out.write(126); // Length is 16b - _out.write(len>>>8); - _out.write(len&255); - for( int i=0; i<msg.length(); i++ ) - _out.write(msg.charAt(i)); - } - - @Override public void close() throws IOException { - try { - if( _out != null ) { - _out.write(new byte[]{(byte)0x88, 0}); // Complete, empty close frame - _out.flush(); - } - } finally { - if( _http != null ) _http.stop(0); - try { - if( _client != null ) _client.close(); - } finally { - super.close(); - } - } - } -} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Simple.java b/chapter21/src/test/java/com/seaofnodes/simple/Simple.java index 509ec100..705b086a 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Simple.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Simple.java @@ -25,10 +25,8 @@ public class Simple { static final int DUMP_FINAL = 1<<16; - static final int DUMP_DOT = 1<<29; static final int DUMP_PASS_NAME = 1<<30; static final int DUMP_AFTER_ALL = 0xff | DUMP_PASS_NAME; - static final int DUMP_DOT_AFTER_ALL = 0xff | DUMP_DOT; static final int DUMP_DISASSEMBLE = 1<<31; @@ -50,7 +48,6 @@ Options: --dump-after-reg-alloc - dump intermediate representation after register allocation pass --dump-after-encode - dump intermediate representation after encoding pass --dump-after-all - dump intermediate representation after all passes - --dot - dump grapical representation of intermediate code into *.dot file(s) -S - dump generated assembler code --eval ... - evaluate the compiled code in emulator --run ... - run the compiled code natively @@ -84,47 +81,24 @@ Options: static void dump(CodeGen code, int dump, int pass) { if ((dump & pass) != 0) { - if ((dump & DUMP_DOT) != 0) { - String fn = switch (pass) { - case DUMP_AFTER_PARSE -> "01-parse.dot"; - case DUMP_AFTER_OPTO -> "02-opto.dot"; - case DUMP_AFTER_TYPE_CHECK -> "03-type_check.dot"; - case DUMP_AFTER_LOOP_TREE -> "04-loop_tree.dot"; - case DUMP_AFTER_INSTR_SELECT -> "05-instr_select.dot"; - case DUMP_AFTER_GCM -> "06-gcm.dot"; - case DUMP_AFTER_LOCAL_SCHED -> "07-local_sched.dot"; - case DUMP_AFTER_REG_ALLOC -> "08-reg_allos.dot"; - case DUMP_AFTER_ENCODE -> "09-local_sched.dot"; - case DUMP_FINAL -> "10-final.dot"; + if ((dump & DUMP_PASS_NAME) != 0) { + System.err.println(switch (pass) { + case DUMP_AFTER_PARSE -> "After Parse:"; + case DUMP_AFTER_OPTO -> "After OPTO:"; + case DUMP_AFTER_TYPE_CHECK -> "After Type Check:"; + case DUMP_AFTER_LOOP_TREE -> "After Loop Tree:"; + case DUMP_AFTER_INSTR_SELECT -> "After Instruction Selection:"; + case DUMP_AFTER_GCM -> "After GCM:"; + case DUMP_AFTER_LOCAL_SCHED -> "After Local Scheduling:"; + case DUMP_AFTER_REG_ALLOC -> "After Register Allocation:"; + case DUMP_AFTER_ENCODE -> "After Instruction Encoding:"; + case DUMP_FINAL -> "Final:"; default -> throw Utils.TODO(); - }; - - try { - Files.writeString(Path.of(fn), - new GraphVisualizer().generateDotOutput(code._stop, null, null)); - } catch(IOException e) { - System.err.println("ERROR: Cannot write DOT file"); - System.exit(1); - } - } else { - if ((dump & DUMP_PASS_NAME) != 0) { - System.err.println(switch (pass) { - case DUMP_AFTER_PARSE -> "After Parse:"; - case DUMP_AFTER_OPTO -> "After OPTO:"; - case DUMP_AFTER_TYPE_CHECK -> "After Type Check:"; - case DUMP_AFTER_LOOP_TREE -> "After Loop Tree:"; - case DUMP_AFTER_INSTR_SELECT -> "After Instruction Selection:"; - case DUMP_AFTER_GCM -> "After GCM:"; - case DUMP_AFTER_LOCAL_SCHED -> "After Local Scheduling:"; - case DUMP_AFTER_REG_ALLOC -> "After Register Allocation:"; - case DUMP_AFTER_ENCODE -> "After Instruction Encoding:"; - case DUMP_FINAL -> "Final:"; - default -> throw Utils.TODO(); - }); - } - - System.err.println(IRPrinter.prettyPrint(code._stop, 9999)); + }); } + + System.err.println(IRPrinter.prettyPrint(code._stop, 9999)); + } } @@ -193,7 +167,6 @@ loop: for (int i = 0; i < args.length; i++) { case "--dump-after-reg-alloc": dump |= DUMP_AFTER_REG_ALLOC; break; case "--dump-after-encode": dump |= DUMP_AFTER_ENCODE; break; case "--dump-after-all": dump |= DUMP_AFTER_ALL; break; - case "--dot": dump |= DUMP_DOT; break; case "-S": dump |= DUMP_DISASSEMBLE; break; case "--eval": do_eval = true; first_arg = i + 1; break loop; case "--run": do_run = true; first_arg = i + 1; break loop; |