diff options
Diffstat (limited to 'chapter24/src')
31 files changed, 147 insertions, 1021 deletions
diff --git a/chapter24/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter24/src/main/java/com/seaofnodes/simple/IterPeeps.java index 18ff470a..c924ccea 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -5,7 +5,6 @@ import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.print.JSViewer; import java.util.Arrays; import java.util.BitSet; import java.util.Random; @@ -68,9 +67,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 @@ -90,11 +94,11 @@ public class IterPeeps { } // If there are distant neighbors, move to worklist n.moveDepsToWorklist(); - JSViewer.show(); // Show again assert progressOnList(code, _work, true); // 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/chapter24/src/main/java/com/seaofnodes/simple/Parser.java b/chapter24/src/main/java/com/seaofnodes/simple/Parser.java index 1932772c..c9e53b4b 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter24/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 com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.Utils; @@ -325,7 +324,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() ) { @@ -642,14 +640,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/chapter24/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 3c6e825d..d4af3a10 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter24/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.IterPeeps; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.node.*; @@ -13,6 +15,7 @@ import java.util.*; @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". @@ -165,7 +168,7 @@ public class CodeGen { P.parse(); _tParse = (int)(System.currentTimeMillis() - t0); - JSViewer.show(); + if( _obs != null ) _obs.phase("Parse"); return this; } @@ -191,6 +194,7 @@ public class CodeGen { Opto.opto(this); _tOpto = (int)(System.currentTimeMillis() - t0); + if( _obs != null ) _obs.phase("Opto"); return this; } public <N extends Node> N add( N n ) { return _iter.add(n); } @@ -339,16 +343,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.Select.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/chapter24/src/main/java/com/seaofnodes/simple/node/AndNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/AndNode.java index 70b57d6d..9957472b 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/AndNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/AndNode.java @@ -9,8 +9,6 @@ public class AndNode extends ArithNode { @Override public String label() { return "And"; } @Override public String op() { return "&"; } - @Override public String glabel() { return "&"; } - @Override long doOp( long x, long y ) { return x & y; } @Override TypeInteger doOp(TypeInteger x, TypeInteger y) { // Sharpen allowed bits if either value is narrowed diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/ArithNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/ArithNode.java index f2beaacb..6c147fe8 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/ArithNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/ArithNode.java @@ -11,7 +11,6 @@ public abstract class ArithNode extends Node { Parser.Lexer _loc; public ArithNode( Parser.Lexer loc, Node lhs, Node rhs) { super(null, lhs, rhs); _loc = loc; } - @Override public String glabel() { return op(); } abstract String op(); @Override diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 513f8d31..1a837435 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter24/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; @@ -153,7 +148,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/chapter24/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java index c54da2c4..56c125e2 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java @@ -21,7 +21,6 @@ public class ConFldOffNode extends ConstantNode { @Override public String label() { return _fname == " len" ? "sizeof("+_name+")" : "#"+_fname; } - @Override public String glabel() { return label(); } @Override public String uniqueName() { return "Off_" + _nid; } @Override diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index d5d70a0f..89289cfc 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -31,7 +31,6 @@ public class ConstantNode extends Node { } @Override public String label() { return "#"+_con; } - @Override public String glabel() { return "#"+_con.gprint(); } @Override public String uniqueName() { return "Con_" + _nid; } @Override diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/ExternNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/ExternNode.java index a10bb84a..21ef8eff 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/ExternNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/ExternNode.java @@ -16,7 +16,6 @@ public class ExternNode extends ConstantNode { public ExternNode(Type t, String ex) { super(t); _extern = ex; } @Override public String label() { return "#"+_con+":"+_extern; } - @Override public String glabel() { return _con.print(new SB().p("#"), new BitSet(), true).p(":").p(_extern).toString(); } @Override public String uniqueName() { return "Extern_" + _nid; } @Override public boolean eq(Node n) { return this==n; } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 10fa9d43..b32484c2 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -24,11 +24,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/chapter24/src/main/java/com/seaofnodes/simple/node/MinusFNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/MinusFNode.java index 5bb0889f..aa66a7f0 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/MinusFNode.java +++ b/chapter24/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/chapter24/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 3ab74625..e87d8dd4 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -10,8 +10,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/chapter24/src/main/java/com/seaofnodes/simple/node/NewNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/NewNode.java index 9310aa38..1a15439e 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/chapter24/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]._t.str() : _ptr._obj.str(); - } - + @Override public String label() { return "new_"+(_ptr._obj.isAry() ? "ary_"+_ptr._obj._fields[1]._t.str() : _ptr._obj.str()); } @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { sb.append("new "); diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter24/src/main/java/com/seaofnodes/simple/node/Node.java index f45a1aa8..5583d3d6 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/Node.java @@ -6,7 +6,6 @@ import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.Utils; 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; @@ -81,14 +80,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, @@ -379,13 +376,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; } /** @@ -548,6 +545,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 it's not an input @@ -558,6 +557,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/chapter24/src/main/java/com/seaofnodes/simple/node/NotNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/NotNode.java index 4b80e61c..1cbd2402 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/chapter24/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/chapter24/src/main/java/com/seaofnodes/simple/node/OrNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/OrNode.java index ac0d8454..6b48815d 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/OrNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/OrNode.java @@ -9,9 +9,6 @@ public class OrNode extends ArithNode { @Override public String label() { return "Or"; } @Override public String op() { return "|"; } - @Override public String glabel() { return "|"; } - - @Override long doOp( long x, long y ) { return x | y; } @Override TypeInteger doOp(TypeInteger x, TypeInteger y) { return TypeInteger.BOT; diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/ParmNode.java index 880f936c..48d05e6b 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -18,8 +18,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/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java index b2483218..81af208c 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -37,8 +37,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/chapter24/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java b/chapter24/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java index 7936086d..2ad034d6 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java +++ b/chapter24/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/chapter24/src/main/java/com/seaofnodes/simple/node/SarNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/SarNode.java index ee15fa65..6b8969e3 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/SarNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/SarNode.java @@ -9,8 +9,6 @@ public class SarNode extends ArithNode { @Override public String label() { return "Sar"; } @Override public String op() { return ">>"; } - @Override public String glabel() { return ">>"; } - @Override long doOp( long x, long y ) { return x >> y; } @Override TypeInteger doOp( TypeInteger x, TypeInteger y ) { if( y.isConstant() ) { diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/ShlNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/ShlNode.java index 2557bf6b..60c91fc9 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/ShlNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -9,8 +9,6 @@ public class ShlNode extends ArithNode { @Override public String label() { return "Shl"; } @Override public String op() { return "<<"; } - @Override public String glabel() { return "<<"; } - @Override long doOp( long x, long y ) { return x << y; } @Override TypeInteger doOp( TypeInteger x, TypeInteger y ) { if( x == TypeInteger.ZERO ) diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/ShrNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/ShrNode.java index 269f6b7f..81dae615 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/ShrNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -9,8 +9,6 @@ public class ShrNode extends ArithNode { @Override public String label() { return "Shr"; } @Override public String op() { return ">>>"; } - @Override public String glabel() { return ">>>"; } - @Override long doOp( long x, long y ) { return x >>> y; } @Override TypeInteger doOp( TypeInteger x, TypeInteger y ) { return x == TypeInteger.ZERO ? x : TypeInteger.BOT; diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 8e33512a..09257730 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter24/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/chapter24/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java index e02183a0..5734bcbc 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java +++ b/chapter24/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/chapter24/src/main/java/com/seaofnodes/simple/node/XorNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/XorNode.java index fdb4863e..cff1706a 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/XorNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/XorNode.java @@ -9,8 +9,6 @@ public class XorNode extends ArithNode { @Override public String label() { return "Xor"; } @Override public String op() { return "^"; } - @Override public String glabel() { return "^"; } - @Override long doOp( long x, long y ) { return x ^ y; } @Override TypeInteger doOp( TypeInteger x, TypeInteger y ) { return TypeInteger.BOT; diff --git a/chapter24/src/main/java/com/seaofnodes/simple/print/GraphVisualizer.java b/chapter24/src/main/java/com/seaofnodes/simple/print/GraphVisualizer.java deleted file mode 100644 index 20c8439a..00000000 --- a/chapter24/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.util.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.depth(); - 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._kinds.at(level)._lexSize; - 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.depth() && v._idx >= scope._kinds.at(level)._lexSize ) - 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/chapter24/src/main/java/com/seaofnodes/simple/print/JSViewer.java b/chapter24/src/main/java/com/seaofnodes/simple/print/JSViewer.java deleted file mode 100644 index f4f72a3b..00000000 --- a/chapter24/src/main/java/com/seaofnodes/simple/print/JSViewer.java +++ /dev/null @@ -1,421 +0,0 @@ -package com.seaofnodes.simple.print; - -import com.seaofnodes.simple.codegen.CodeGen; -import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.type.*; -import com.seaofnodes.simple.util.SB; -import com.seaofnodes.simple.util.Utils; -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.depth()+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._kinds.at(level-1)._lexSize; - - // 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.depth() && v._idx >= scope._kinds.at(level)._lexSize ) - 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/chapter24/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/chapter24/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java new file mode 100644 index 00000000..bf8f4181 --- /dev/null +++ b/chapter24/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 24'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/chapter24/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/chapter24/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java new file mode 100644 index 00000000..ee540508 --- /dev/null +++ b/chapter24/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 24'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/chapter24/src/main/java/com/seaofnodes/simple/print/SimpleWebSocket.java b/chapter24/src/main/java/com/seaofnodes/simple/print/SimpleWebSocket.java deleted file mode 100644 index d7fa8bf2..00000000 --- a/chapter24/src/main/java/com/seaofnodes/simple/print/SimpleWebSocket.java +++ /dev/null @@ -1,193 +0,0 @@ -package com.seaofnodes.simple.print; - -import com.seaofnodes.simple.util.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/chapter24/src/test/java/com/seaofnodes/simple/Simple.java b/chapter24/src/test/java/com/seaofnodes/simple/Simple.java index be582a64..18804ebd 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Simple.java +++ b/chapter24/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; @@ -47,7 +45,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; this is the default @@ -78,44 +75,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_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"; - default -> throw Utils.TODO(); - }; - - try { - Files.writeString(Path.of(fn), - new GraphVisualizer().generateDotOutput(code._stop, null, null)); - } catch(IOException e) { throw bad("Cannot write DOT file"); } - } 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_SELECT -> "After Code 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 Encoding:"; - case DUMP_FINAL -> "Final:"; - default -> throw Utils.TODO(); - }); - } - - System.err.println(IRPrinter.prettyPrint(code._stop, 9999)); + 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_SELECT -> "After Code 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 Encoding:"; + case DUMP_FINAL -> "Final:"; + default -> throw Utils.TODO(); + }); } + + System.err.println(IRPrinter.prettyPrint(code._stop, 9999)); + } } @@ -183,7 +160,6 @@ Options: 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 ; do_run = false; break; case "--run": do_run = true ; break; |