diff options
Diffstat (limited to 'chapter10b/src/main/java/com')
24 files changed, 128 insertions, 392 deletions
diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter10b/src/main/java/com/seaofnodes/simple/IRPrinter.java index 1ac32b1a..d5ab15fe 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -1,188 +1,32 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.node.LoopNode; -import com.seaofnodes.simple.node.Node; -import com.seaofnodes.simple.node.ProjNode; - -import java.util.ArrayList; -import java.util.BitSet; - -public class IRPrinter { - - // Print a node on 1 line, columnar aligned, as: - // NNID NNAME DDEF DDEF [[ UUSE UUSE ]] TYPE - // 1234 sssss 1234 1234 1234 1234 1234 1234 tttttt - public static void _printLine( Node n, StringBuilder sb ) { - sb.append("%4d %-7.7s ".formatted(n._nid,n.label())); - if( n.isDead() ) { - sb.append("DEAD\n"); - return; - } - for( Node def : n._inputs ) - sb.append(def==null ? "____ " : "%4d ".formatted(def._nid)); - for( int i = n._inputs.size(); i<3; i++ ) - sb.append(" "); - sb.append(" [[ "); - for( Node use : n._outputs ) - sb.append(use==null ? "____ " : "%4d ".formatted(use._nid)); - int lim = 5 - Math.max(n._inputs.size(),3); - for( int i = n._outputs.size(); i<lim; i++ ) - sb.append(" "); - sb.append(" ]] "); - if( n._type!= null ) sb.append(n._type.str()); - sb.append("\n"); - } - - private static StringBuilder nodeId(StringBuilder sb, Node n) { - sb.append("%%%d".formatted(n._nid)); - if (n instanceof ProjNode proj) { - sb.append(".").append(proj._idx); - } - return sb; - } - - // Print a node on 1 line, format is inspired by LLVM - // %id: TYPE = NODE(inputs ....) - // Nodes as referred to as %id - public static void _printLineLlvmFormat( Node n, StringBuilder sb ) { - nodeId(sb, n).append(": "); - if( n.isDead() ) { - sb.append("DEAD\n"); - return; - } - if( n._type!= null ) n._type.typeName(sb); - sb.append(" = ").append( n.label() ).append( "(" ); - for( int i = 0; i < n._inputs.size(); i++ ) { - Node def = n.in(i); - if (i > 0) - sb.append(", "); - if (def == null) sb.append("_"); - else nodeId(sb, def); - } - sb.append(")").append("\n"); - } - - public static void printLine( Node n, StringBuilder sb, boolean llvmFormat ) { - if (llvmFormat) _printLineLlvmFormat( n, sb ); - else _printLine ( n, sb ); - } - - public static String prettyPrint(Node node, int depth) { - return prettyPrint( node, depth, false ); - } - - // Another bulk pretty-printer. Makes more effort at basic-block grouping. - public static String prettyPrint( Node node, int depth, boolean llvmFormat ) { - // First, a Breadth First Search at a fixed depth. - BFS bfs = new BFS(node,depth); - // Convert just that set to a post-order - ArrayList<Node> rpos = new ArrayList<>(); - BitSet visit = new BitSet(); - for( int i=bfs._lim; i< bfs._bfs.size(); i++ ) - postOrd( bfs._bfs.get(i), rpos, visit, bfs._bs); - // Reverse the post-order walk - StringBuilder sb = new StringBuilder(); - boolean gap=false; - for( int i=rpos.size()-1; i>=0; i-- ) { - Node n = rpos.get(i); - if( n.isCFG() || n.isMultiHead() ) { - if( !gap ) sb.append("\n"); // Blank before multihead - printLine( n, sb, llvmFormat ); // Print head - while( --i >= 0 ) { - Node t = rpos.get(i); - if( !t.isMultiTail() ) { i++; break; } - printLine( t, sb, llvmFormat ); - } - sb.append("\n"); // Blank after multitail - gap = true; - } else { - printLine( n, sb, llvmFormat ); - gap = false; - } - } - return sb.toString(); - } - - private static void postOrd(Node n, ArrayList<Node> rpos, BitSet visit, BitSet bfs) { - if( !bfs.get(n._nid) ) - return; // Not in the BFS visit - if( visit.get(n._nid) ) return; // Already post-order walked - visit.set(n._nid); - // First walk the CFG, then everything - if( n.isCFG() ) { - for( Node use : n._outputs ) - if( use!=null && use.isCFG() && use.nOuts()>=1 && !(use._outputs.get(0) instanceof LoopNode) ) - postOrd(use, rpos,visit,bfs); - for( Node use : n._outputs ) - if( use!=null && use.isCFG() ) - postOrd(use,rpos,visit,bfs); - } - for( Node use : n._outputs ) - if( use != null ) - postOrd(use, rpos,visit,bfs); - // Post-order - rpos.add(n); - } - - // Breadth-first search, broken out in a class to keep in more independent. - // Maintains a root-set of Nodes at the limit (or past by 1 if MultiHead). - public static class BFS { - // A breadth first search, plus MultiHeads for any MultiTails - public final ArrayList<Node> _bfs; - public final BitSet _bs; // Visited members by node id - public final int _depth; // Depth limit - public final int _lim; // From here to _bfs._len can be roots for a reverse search - public BFS( Node base, int d ) { - _depth = d; - _bfs = new ArrayList<>(); - _bs = new BitSet(); - - add(base); // Prime the pump - int idx=0, lim=1; // Limit is where depth counter changes - while( idx < _bfs.size() ) { // Ran out of nodes below depth - Node n = _bfs.get(idx++); - for( Node def : n._inputs ) - if( def!=null && !_bs.get(def._nid) ) - add(def); - if( idx==lim ) { // Depth counter changes at limit - if( --d < 0 ) - break; // Ran out of depth - lim = _bfs.size(); // New depth limit - } - } - // Toss things past the limit except multi-heads - while( idx < _bfs.size() ) { - Node n = _bfs.get(idx); - if( n.isMultiHead() ) idx++; - else del(idx); - } - // Root set is any node with no inputs in the visited set - lim = _bfs.size(); - for( int i=_bfs.size()-1; i>=0; i-- ) - if( !any_visited(_bfs.get(i)) ) - swap( i,--lim); - _lim = lim; - } - void swap( int x, int y ) { - if( x==y ) return; - Node tx = _bfs.get(x); - Node ty = _bfs.get(y); - _bfs.set(x,ty); - _bfs.set(y,tx); - } - void add(Node n) { - _bfs.add(n); - _bs.set(n._nid); - } - void del(int idx) { - Node n = Utils.del(_bfs, idx); - _bs.clear(n._nid); - } - boolean any_visited( Node n ) { - for( Node def : n._inputs ) - if( def!=null && _bs.get(def._nid) ) - return true; - return false; - } - } +import com.seaofnodes.print.IRAdapter; +import com.seaofnodes.simple.node.*; + +/** This chapter's read-only IR facts and the familiar debugger entry points. */ +public final class IRPrinter extends IRAdapter<Node> { + private static final com.seaofnodes.print.IRPrinter<Node> PRINT = + new com.seaofnodes.print.IRPrinter<>(new IRPrinter()); + @Override public String type(Node n) { return n._type==null ? "" : n._type.str(); } + @Override public int inputColumns() { return 3; } + @Override public String inputMark(Node n, Node def) { return n instanceof MemMergeNode && def instanceof MemMergeNode ? "^" : " "; } + @Override public Kind kind(Node n) { + if( n instanceof StartNode ) return Kind.START; + if( n instanceof StopNode ) return Kind.STOP; + if( n instanceof LoopNode ) return Kind.LOOP; + if( n instanceof RegionNode ) return Kind.REGION; + if( n instanceof PhiNode ) return Kind.PHI; + if( n instanceof ReturnNode ) return Kind.RETURN; + if( n instanceof ConstantNode ) return Kind.CONSTANT; + if( n instanceof ProjNode ) return n.isCFG() ? Kind.CPROJ : Kind.PROJ; + if( n.isCFG() ) return Kind.CTRL; + if( n instanceof MultiNode ) return Kind.MULTI; + return Kind.DATA; + } + @Override public int index(Node n) { + if( n instanceof ProjNode p ) return p._idx; + return n._nid; + } + + public static String prettyPrint(Node n, int depth) { return PRINT.prettyPrint(n,depth); } } diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/AddNode.java index de5044d7..e235d288 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -1,20 +1,15 @@ package com.seaofnodes.simple.node; + import com.seaofnodes.simple.type.*; -import java.util.BitSet; public class AddNode extends Node { public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); } @Override public String label() { return "Add"; } - @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - in(1)._print0(sb.append("("), visited); - in(2)._print0(sb.append("+"), visited); - return sb.append(")"); - } + @Override protected String format() { return "(%1+%2)"; } @Override diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index bf0d3a84..63452dba 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -1,10 +1,11 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeMemPtr; -import java.util.BitSet; abstract public class BoolNode extends Node { @@ -17,11 +18,8 @@ abstract public class BoolNode extends Node { @Override public String label() { return getClass().getSimpleName(); } - @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - in(1)._print0(sb.append("("), visited); - in(2)._print0(sb.append(op()), visited); - return sb.append(")"); + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + return p.open().n(in(1)).p(op()).n(in(2)).close(); } @Override diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/CastNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/CastNode.java index fec540f7..c1faf210 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/CastNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/CastNode.java @@ -1,10 +1,11 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.IterPeeps; -import java.util.BitSet; // Upcast (join) the input to a t. Used after guard test to lift an input. // Can also be used to make a type-assertion if ctrl is null. @@ -18,12 +19,9 @@ public class CastNode extends Node { @Override public String label() { return "("+_t.str()+")"; } - @Override - public String uniqueName() { return "Cast_" + _nid; } - @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - return in(1)._print0(sb.append(label()), visited); + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + return p.p(label()).n(in(1)); } @Override diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index d760c0df..426736ed 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -1,9 +1,10 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; -import java.util.BitSet; /** * A Constant node represents a constant value. At present, the only constants @@ -24,15 +25,16 @@ public class ConstantNode extends Node { _con = type; } - @Override - public String label() { return "#"+_con; } + @Override protected String repeatName() { + return _con==null || _con.toString().length()<=32 ? null : uniqueName(); + } @Override - public String uniqueName() { return "Con_" + _nid; } + public String label() { return "Con"; } - @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - return _con.print(sb); + + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + return p.p(_con); } @Override public boolean isMultiTail() { return true; } diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/DivNode.java index 6cee90ad..d7244ace 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -1,21 +1,16 @@ package com.seaofnodes.simple.node; + import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; -import java.util.BitSet; public class DivNode extends Node { public DivNode(Node lhs, Node rhs) { super(null, lhs, rhs); } @Override public String label() { return "Div"; } - @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - in(1)._print0(sb.append("("), visited); - in(2)._print0(sb.append("/"), visited); - return sb.append(")"); - } + @Override protected String format() { return "(%1/%2)"; } @Override public Type compute() { diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 1cf4ddaf..45f695a5 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -1,10 +1,10 @@ package com.seaofnodes.simple.node; + import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeTuple; -import java.util.BitSet; public class IfNode extends MultiNode { @@ -16,11 +16,7 @@ public class IfNode extends MultiNode { @Override public String label() { return "If"; } - @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - sb.append("if( "); - return in(1)._print0(sb, visited).append(" )"); - } + @Override protected String format() { return "if( %1 )"; } @Override public boolean isCFG() { return true; } @Override public boolean isMultiHead() { return true; } diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 5f096ef7..9bf36459 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -1,11 +1,12 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.Field; -import java.util.BitSet; /** * Load represents extracting a value from inside a memory object, @@ -48,7 +49,7 @@ public class LoadNode extends MemOpNode { public String label() { return "Load"; } @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(".").append(_name); } + protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p(".").p(_name); } @Override public Type compute() { diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index d7fed402..f3d5b01e 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -1,9 +1,10 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMem; -import java.util.BitSet; /** All memory: a default slice and explicit overrides for individual aliases. */ public class MemMergeNode extends Node { @@ -28,14 +29,14 @@ public class MemMergeNode extends Node { @Override public String label() { return "MemMerge"; } @Override public boolean isMem() { return true; } @Override public Type compute() { return TypeMem.BOT; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { - sb.append("MEM["); + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + p.p("MEM["); for( int i=1; i<nIns(); i++ ) if( in(i)!=null ) { - sb.append(i==1 ? "default:" : i+":"); - in(i)._print0(sb,visited).append(" "); + p.p(i==1 ? "default:" : i+":"); + p.n(in(i)).p(" "); } - return sb.append("]"); + return p.p("]"); } @Override public Node idealize() { diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 8b1b73bf..5b65b3fb 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -1,20 +1,16 @@ package com.seaofnodes.simple.node; + import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; -import java.util.BitSet; public class MinusNode extends Node { public MinusNode(Node in) { super(null, in); } @Override public String label() { return "Minus"; } - @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - in(1)._print0(sb.append("(-"), visited); - return sb.append(")"); - } + @Override protected String format() { return "(-%1)"; } @Override public Type compute() { diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/MulNode.java index 97721ce3..5592c52d 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -1,21 +1,16 @@ package com.seaofnodes.simple.node; + import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; -import java.util.BitSet; public class MulNode extends Node { public MulNode(Node lhs, Node rhs) { super(null, lhs, rhs); } @Override public String label() { return "Mul"; } - @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - in(1)._print0(sb.append("("), visited); - in(2)._print0(sb.append("*"), visited); - return sb.append(")"); - } + @Override protected String format() { return "(%1*%2)"; } @Override public Type compute() { diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/NewNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/NewNode.java index b13462f5..857920bc 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -1,9 +1,10 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMemPtr; -import java.util.BitSet; public class NewNode extends Node { @@ -17,10 +18,8 @@ public class NewNode extends Node { @Override public String label() { return "new"; } - @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - sb.append("new "); - return sb.append(_ptr._obj.str()); + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + return p.p("new ").p(_ptr._obj.str()); } @Override diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/Node.java index 9a48c515..1d8e23f8 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.BaseNode; + import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.IRPrinter; @@ -15,14 +17,7 @@ import java.util.function.Function; * The Node class provides common functionality used by all subtypes. * Subtypes of Node specialize by overriding methods. */ -public abstract class Node implements Cloneable { - - /** - * Each node has a unique dense Node ID within a compilation context - * The ID is useful for debugging, for using as an offset in a bitvector, - * as well as for computing equality of nodes (to be implemented later). - */ - public int _nid; +public abstract class Node extends BaseNode<Node> implements Cloneable { /** * Inputs to the node. These are use-def references to Nodes. @@ -44,14 +39,12 @@ public abstract class Node implements Cloneable { */ public ArrayList<Node> _outputs; - /** * Current computed type for this Node. This value changes as the graph * changes and more knowledge is gained about the program. */ public Type _type; - /** * A private Global Static mutable counter, for unique node id generation. * To make the compiler multithreaded, this field will have to move into a TLS. @@ -61,7 +54,7 @@ public abstract class Node implements Cloneable { public static int UID() { return UNIQUE_ID; } protected Node(Node... inputs) { - _nid = UNIQUE_ID++; // allocate unique dense ID + super(UNIQUE_ID++); // allocate unique dense ID _inputs = new ArrayList<>(); Collections.addAll(_inputs,inputs); _outputs = new ArrayList<>(); @@ -73,42 +66,6 @@ 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 debugging, e.g. "Add12" or "Region30" or "EQ99" - public String uniqueName() { - return label() + _nid; - } - - // ------------------------------------------------------------------------ - - // Debugger Printing. - - // {@code toString} is what you get in the debugger. It has to print 1 - // line (because this is what a debugger typically displays by default) and - // has to be robust with broken graph/nodes. - @Override - public final String toString() { return print(); } - - // This is a *deep* print. This version will fail on cycles, which we will - // correct later when we can parse programs with loops. We print with a - // tik-tok style; the common _print0 calls the per-Node _print1, which - // calls back to _print0; - public final String print() { - return _print0(new StringBuilder(), new BitSet()).toString(); - } - - // This is the common print: check for repeats, check for DEAD and print - // "DEAD" else call the per-Node print1. - final StringBuilder _print0(StringBuilder sb, BitSet visited) { - if (visited.get(_nid) && !(this instanceof ConstantNode) ) - return sb.append(label()); - visited.set(_nid); - return isDead() - ? sb.append(uniqueName()).append(":DEAD") - : _print1(sb, visited); - } - // Every Node implements this; a partial-line recursive print - abstract StringBuilder _print1(StringBuilder sb, BitSet visited); - public String p(int depth) { return IRPrinter.prettyPrint(this,depth); } public boolean isMultiHead() { return false; } @@ -117,6 +74,8 @@ public abstract class Node implements Cloneable { // ------------------------------------------------------------------------ // Graph Node & Edge manipulation + @Override public String typeName() { return _type==null ? null : _type.toString(); } + /** * Gets the ith input node * @param i Offset of the input node @@ -131,8 +90,6 @@ public abstract class Node implements Cloneable { public boolean isUnused() { return nOuts() == 0; } - public boolean isCFG() { return false; } - public boolean isMem() { return false; } /** @@ -257,7 +214,6 @@ public abstract class Node implements Cloneable { // Test "keep" status public boolean iskeep() { return Utils.find(_outputs,null) != -1; } - // Replace self with nnn in the graph, making 'this' go dead public void subsume( Node nnn ) { assert nnn!=this; @@ -388,7 +344,6 @@ public abstract class Node implements Cloneable { return old; } - /** * This function rewrites the current Node into a more "idealized" form. * This is the bulk of our peephole rewrite rules, and we use this to @@ -436,7 +391,6 @@ public abstract class Node implements Cloneable { */ public abstract Node idealize(); - // Some of the peephole rules get complex, and search further afield than // just the nearest neighbor. These peepholes can fail the pattern match // on a node some distance away, and if that node ever changes we should @@ -480,7 +434,6 @@ public abstract class Node implements Cloneable { _deps.clear(); } - // Global Value Numbering. Hash over opcode and inputs; hits in this table // are structurally equal. public static final HashMap<Node,Node> GVN = new HashMap<>(); @@ -502,7 +455,6 @@ public abstract class Node implements Cloneable { // and can assume "this!=n" and has the same Java class. boolean eq( Node n ) { return true; } - // Cached hash. If zero, then not computed AND this Node is NOT in the GVN // table - and can have its edges hacked (which will change his hash // anyway). If Non-Zero then this Node is IN the GVN table, or is being @@ -518,7 +470,6 @@ public abstract class Node implements Cloneable { _hash=0; // Out of table now } - // Hash of opcode and inputs @Override public final int hashCode() { if( _hash != 0 ) return _hash; @@ -532,7 +483,6 @@ public abstract class Node implements Cloneable { // Subclasses add extra hash info (such as ConstantNodes constant) int hash() { return 0; } - // ------------------------------------------------------------------------ // Peephole utilities @@ -561,7 +511,6 @@ public abstract class Node implements Cloneable { return true; } - /** * Immediate dominator tree depth, used to approximate a real IDOM depth * during parsing where we do not have the whole program, and also @@ -591,7 +540,6 @@ public abstract class Node implements Cloneable { return _idepth = (char)depth; } - // Return the immediate dominator of this Node. Node idom() { return in(0); } @@ -627,7 +575,6 @@ public abstract class Node implements Cloneable { ITER_CNT = ITER_NOP_CNT = 0; } - // Utility to walk the entire graph applying a function; return the first // not-null result. private static final BitSet WVISIT = new BitSet(); diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/NotNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/NotNode.java index 83141836..5e556390 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -1,19 +1,15 @@ package com.seaofnodes.simple.node; + import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.*; -import java.util.BitSet; public class NotNode extends Node { public NotNode(Node in) { super(null, in); } @Override public String label() { return "Not"; } - @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - in(1)._print0(sb.append("(!"), visited); - return sb.append(")"); - } + @Override protected String format() { return "(!%1)"; } @Override public Type compute() { diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index cdb4b7cc..6995cc2f 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -1,10 +1,11 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.Utils; -import java.util.BitSet; public class PhiNode extends Node { @@ -23,18 +24,12 @@ public class PhiNode extends Node { @Override public String label() { return "Phi_"+_label; } @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { + protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { if( !(region() instanceof RegionNode r) || r.inProgress() ) - sb.append("Z"); - sb.append("Phi("); - for( Node in : _inputs ) { - if (in == null) sb.append("____"); - else in._print0(sb, visited); - sb.append(","); - } - sb.setLength(sb.length()-1); - sb.append(")"); - return sb; + p.p("Z"); + p.p("Phi("); + for( Node in : _inputs ) p.n(in).p(","); + return p.unchar(',').close(); } Node region() { return in(0); } diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 735fcdf3..a2632110 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -1,10 +1,11 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.type.TypeTuple; -import java.util.BitSet; public class ProjNode extends Node { @@ -24,7 +25,7 @@ public class ProjNode extends Node { public String label() { return _label; } @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(_label); } + protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p(_label); } @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; } @Override public boolean isMultiTail() { return in(0).isMultiHead(); } diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index a6b8d834..8b52494a 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -1,12 +1,13 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import java.util.ArrayList; import java.util.Arrays; -import java.util.BitSet; public class RegionNode extends Node { @@ -15,9 +16,8 @@ public class RegionNode extends Node { @Override public String label() { return "Region"; } - @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - return sb.append(label()).append(_nid); + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + return p.p(label()).p(_nid); } @Override public boolean isCFG() { return true; } diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 96d58599..ef4ddb3a 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -1,8 +1,9 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.type.*; -import java.util.BitSet; /** Keeps all preceding memory effects and the return value alive: {ctrl, $mem, value}. */ public class ReturnNode extends Node { @@ -19,10 +20,10 @@ public class ReturnNode extends Node { public String label() { return "Return"; } @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - sb.append("return "); - expr()._print0(sb, visited); - return sb.append(";"); + protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + p.p("return "); + p.n(expr()); + return p.p(";"); } @Override public boolean isCFG() { return true; } diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index b931e862..b408eb2f 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.Utils; @@ -42,20 +44,19 @@ public class ScopeNode extends Node { @Override public String label() { return "Scope"; } @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - sb.append("Scope[ "); + protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + p.p("Scope[ "); String[] names = reverseNames(); for( int j=0; j<nIns(); j++ ) { - sb.append(names[j]).append(":"); + p.p(names[j]).p(":"); Node n = in(j); while( n instanceof ScopeNode loop ) { - sb.append("Lazy_"); + p.p("Lazy_"); n = loop.in(j); } - n._print0(sb, visited).append(" "); + p.n(n).p(" "); } - sb.setLength(sb.length()-1); - return sb.append("]"); + return p.unchar(' ').p("]"); } /** diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/StartNode.java index 1ca52af0..3404f111 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -1,7 +1,8 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.type.*; -import java.util.BitSet; /** The entry tuple: control, initial whole-memory state, and argument. */ public class StartNode extends MultiNode { @@ -15,9 +16,8 @@ public class StartNode extends MultiNode { @Override public String label() { return "Start"; } - @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - return sb.append(label()); + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + return p.p(label()); } @Override public boolean isCFG() { return true; } diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/StopNode.java index cb4126f5..4b4e9615 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -1,11 +1,12 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.IterPeeps; -import java.util.BitSet; public class StopNode extends Node { @@ -22,12 +23,12 @@ public class StopNode extends Node { } @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - if( ret()!=null ) return ret()._print0(sb, visited); - sb.append("Stop[ "); + protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + if( ret()!=null ) return p.n(ret()); + p.p("Stop[ "); for( Node ret : _inputs ) - ret._print0(sb, visited).append(" "); - return sb.append("]"); + p.n(ret).p(" "); + return p.p("]"); } @Override public boolean isCFG() { return true; } diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index b752aad5..026d5c50 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -1,10 +1,11 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.*; -import java.util.BitSet; /** * Store represents setting a value to a memory based object, in chapter 10 @@ -29,8 +30,8 @@ public class StoreNode extends MemOpNode { public Node val() { return in(3); } @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - return sb.append(".").append(_name).append("=").append( val()).append(";"); + protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + return p.p(".").p(_name).p("=").p( val()).p(";"); } @Override diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/SubNode.java index eeec5e1d..6fa87a07 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -1,21 +1,16 @@ package com.seaofnodes.simple.node; + import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; -import java.util.BitSet; public class SubNode extends Node { public SubNode(Node lhs, Node rhs) { super(null, lhs, rhs); } @Override public String label() { return "Sub"; } - @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - in(1)._print0(sb.append("("), visited); - in(2)._print0(sb.append("-"), visited); - return sb.append(")"); - } + @Override protected String format() { return "(%1-%2)"; } @Override public Type compute() { diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/chapter10b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index 600e9c73..92d970d8 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -1,42 +1,20 @@ 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 10'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>(); - String[] names = n instanceof ScopeNode scope && n.nIns() != 0 ? scope.reverseNames() : null; - for( int i = 0; i < n.nIns(); i++ ) { - String name = names == null || i >= names.length ? null : names[i]; - edges.add(new Edge(i, ref(n.in(i)), role(n, i), name)); - } - return edges; + @Override protected String[] edgeNames(Node n) { + return n instanceof ScopeNode scope && n.nIns()!=0 ? scope.reverseNames() : null; } + @Override protected int projectionIndex(Node n) { return n instanceof ProjNode p ? p._idx : -1; } - @Override protected GraphSnapshot.Node desc(Node n) { - Projection proj = n instanceof ProjNode 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) { + @Override protected Kind kind(Node n) { if( n instanceof StopNode ) return Kind.STOP; if( n instanceof ScopeNode ) return Kind.SCOPE; if( n instanceof StartNode ) return Kind.CTRL; @@ -46,7 +24,7 @@ public class SimpleGraphAdapter extends GraphAdapter<Node> { return n.isCFG() ? Kind.CTRL : isMem(n) ? Kind.MEM : Kind.DATA; } - private Role role(Node n, int i) { + @Override protected Role role(Node n, int i) { if( n instanceof ScopeNode || n instanceof ConstantNode ) return Role.ASSOC; if( n instanceof PhiNode ) return i == 0 ? Role.ASSOC : isMem(n) ? Role.MEM : Role.DATA; if( n instanceof ProjNode ) return n.isCFG() ? Role.CTRL : isMem(n) ? Role.MEM : Role.DATA; |