diff options
Diffstat (limited to 'src/main/java/com')
22 files changed, 421 insertions, 66 deletions
diff --git a/src/main/java/com/seaofnodes/simple/IRPrinter.java b/src/main/java/com/seaofnodes/simple/IRPrinter.java new file mode 100644 index 00000000..2a6dbefd --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -0,0 +1,124 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.LoopNode; +import com.seaofnodes.simple.node.Node; + +import java.util.ArrayList; +import java.util.BitSet; + +public class IRPrinter { + + // Another bulk pretty-printer. Makes more effort at basic-block grouping. + public static String prettyPrint(Node node, int depth) { + // 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 + n._printLine(sb); // Print head + while( --i >= 0 ) { + Node t = rpos.get(i); + if( !t.isMultiTail() ) { i++; break; } + t._printLine(sb); + } + sb.append("\n"); // Blank after multitail + gap = true; + } else { + n._printLine( sb ); + 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.isCFG() && use.nOuts()>=1 && !(use._outputs.get(0) instanceof LoopNode) ) + postOrd(use, rpos,visit,bfs); + for( Node use : n._outputs ) + if( use.isCFG() ) + postOrd(use,rpos,visit,bfs); + } + for( Node use : n._outputs ) + 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; + } + } +} diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index b9fbf26f..2e043538 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -60,6 +60,7 @@ public class Parser { add("int"); add("return"); add("true"); + add("while"); }}; @@ -141,11 +142,80 @@ public class Parser { else if (matchx("int")) return parseDecl(); else if (match ("{" )) return require(parseBlock(),"}"); else if (matchx("if" )) return parseIf(); + else if (matchx("while")) return parseWhile(); else if (matchx(";")) return null; // Empty statement else return parseExpressionStatement(); } /** + * Parses a while statement + * + * <pre> + * while ( expression ) statement + * </pre> + * @return a {@link Node}, never {@code null} + */ + private Node parseWhile() { + require("("); + + // Loop region has two control inputs, the first is the entry + // point, and second is back edge that is set after loop is parsed + // (see end_loop() call below). Note that the absence of back edge is + // used as an indicator to switch off peepholes of the region and + // associated phis; see {@code inProgress()}. + + ctrl(new LoopNode(ctrl()).peephole()); // Note we set back edge to null here + + // At loop head, we clone the current Scope (this includes all + // names in every nesting level within the Scope). + // We create phis eagerly for all the names we find, see dup(). + + // Save the current scope as the loop head + ScopeNode head = _scope.keep(); + // Clone the head Scope to create a new Scope for the body. + // Create phis eagerly as part of cloning + _xScopes.push(_scope = _scope.dup(true)); // The true argument triggers creating phis + + // Parse predicate + var pred = require(parseExpression(), ")"); + // IfNode takes current control and predicate + IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).keep().peephole(); + // Setup projection nodes + Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); + ifNode.unkeep(); + Node ifF = new ProjNode(ifNode, 1, "False").peephole(); + + // Clone the body Scope to create the exit Scope + // which accounts for any side effects in the predicate + // The exit Scope will be the final scope after the loop, + // And its control input is the False branch of the loop predicate + // Note that body Scope is still our current scope + var exit = _scope.dup(); + _xScopes.push(exit); + exit.ctrl(ifF); + + // Parse the true side, which corresponds to loop body + // Our current scope is the body Scope + ctrl(ifT); // set ctrl token to ifTrue projection + parseStatement(); // Parse loop body + + // The true branch loops back, so whatever is current control (_scope.ctrl) gets + // added to head loop as input. endLoop() updates the head scope, + // and goes through all the phis that were created earlier. For each + // phi, it sets the second input to the corresponding input from the back edge. + // If the phi is redundant, it is replaced by its sole input. + head.endLoop(_scope, exit); + head.unkeep().kill(); + + _xScopes.pop(); // Cleanup + _xScopes.pop(); // Cleanup + + // At exit the false control is the current control, and + // the scope is the exit scope after the exit test. + return (_scope = exit); + } + + /** * Parses a statement * * <pre> @@ -368,7 +438,7 @@ public class Parser { // Require an exact match private void require(String syntax) { require(null, syntax); } - private Node require(Node n, String syntax) { + private <N extends Node> N require(N n, String syntax) { if (match(syntax)) return n; throw errorSyntax(syntax); } @@ -377,7 +447,7 @@ public class Parser { return error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken()); } - static RuntimeException error(String errorMessage) { + public static RuntimeException error( String errorMessage ) { return new RuntimeException(errorMessage); } diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 72dc0ffd..84367cc7 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -2,15 +2,17 @@ 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) { - in(1)._print0(sb.append("(")); - in(2)._print0(sb.append("+")); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append("+"), visited); return sb.append(")"); } diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index ab1b474c..f5bbc9ad 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import java.util.BitSet; + abstract public class BoolNode extends Node { public BoolNode(Node lhs, Node rhs) { @@ -15,9 +17,9 @@ abstract public class BoolNode extends Node { public String label() { return getClass().getSimpleName(); } @Override - StringBuilder _print1(StringBuilder sb) { - in(1)._print0(sb.append("(")); - in(2)._print0(sb.append(op())); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append(op()), visited); return sb.append(")"); } diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 85277d82..b7ec8292 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple.node; 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 * that we allow are integer literals; therefore Constants contain an integer @@ -29,10 +31,12 @@ public class ConstantNode extends Node { public String uniqueName() { return "Con_" + _nid; } @Override - StringBuilder _print1(StringBuilder sb) { + StringBuilder _print1(StringBuilder sb, BitSet visited) { return _con.print(sb); } + @Override public boolean isMultiTail() { return true; } + @Override public Type compute() { return _con; } diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java index f80f092d..f71a32db 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -3,15 +3,17 @@ 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) { - in(1)._print0(sb.append("(")); - in(2)._print0(sb.append("/")); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append("/"), visited); return sb.append(")"); } diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 34846e99..0f414c08 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -4,6 +4,8 @@ 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 { public IfNode(Node ctrl, Node pred) { @@ -14,12 +16,13 @@ public class IfNode extends MultiNode { public String label() { return "If"; } @Override - StringBuilder _print1(StringBuilder sb) { + StringBuilder _print1(StringBuilder sb, BitSet visited) { sb.append("if( "); - return in(1)._print0(sb).append(" )"); + return in(1)._print0(sb, visited).append(" )"); } @Override public boolean isCFG() { return true; } + @Override public boolean isMultiHead() { return true; } public Node ctrl() { return in(0); } public Node pred() { return in(1); } @@ -27,7 +30,8 @@ public class IfNode extends MultiNode { @Override public Type compute() { // If the If node is not reachable then neither is any following Proj - if (ctrl()._type != Type.CONTROL) return TypeTuple.IF_NEITHER; + if (ctrl()._type != Type.CONTROL && ctrl()._type != Type.BOTTOM ) + return TypeTuple.IF_NEITHER; // If constant is 0 then false branch is reachable // Else true branch is reachable if (pred()._type instanceof TypeInteger ti && ti.isConstant()) { diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java new file mode 100644 index 00000000..e4ef68a3 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -0,0 +1,30 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; + +import java.util.BitSet; + +public class LoopNode extends RegionNode { + + public LoopNode( Node entry ) { super(null,entry,null); } + + Node entry() { return in(1); } + Node back () { return in(2); } + + @Override + public String label() { return "Loop"; } + + @Override + public Type compute() { + return inProgress() ? Type.CONTROL : super.compute(); + } + + @Override + public Node idealize() { + return inProgress() ? null : super.idealize(); + } + + @Override int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(entry().idepth()+1); } + + @Override Node idom() { return entry(); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index ad6e513a..9d3d3f5d 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -3,14 +3,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) { - in(1)._print0(sb.append("(-")); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("(-"), visited); return sb.append(")"); } diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index 380cb042..4884ee18 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -3,15 +3,17 @@ 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) { - in(1)._print0(sb.append("(")); - in(2)._print0(sb.append("*")); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append("*"), visited); return sb.append(")"); } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 6f9ee258..921292cb 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -96,18 +96,51 @@ public abstract class Node { // tik-tok style; the common _print0 calls the per-Node _print1, which // calls back to _print0; public final String print() { - return _print0(new StringBuilder()).toString(); + return _print0(new StringBuilder(), new BitSet()).toString(); } - // This is the common print: check for DEAD and print "DEAD" else call the - // per-Node print1. - final StringBuilder _print0(StringBuilder sb) { + // 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)) + return sb.append(label()); + visited.set(_nid); return isDead() ? sb.append(uniqueName()).append(":DEAD") - : _print1(sb); + : _print1(sb, visited); + } + // Every Node implements this; a partial-line recursive print + abstract StringBuilder _print1(StringBuilder sb, BitSet visited); + + + // 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 void _printLine(StringBuilder sb ) { + sb.append("%4d %-7.7s ".formatted(_nid,label())); + if( isDead() ) { + sb.append("DEAD\n"); + return; + } + for( Node def : _inputs ) + sb.append(def==null ? "____ " : "%4d ".formatted(def._nid)); + for( int i = _inputs.size(); i<3; i++ ) + sb.append(" "); + sb.append(" [[ "); + for( Node use : _outputs ) + sb.append("%4d ".formatted(use._nid)); + int lim = 5 - Math.max(_inputs.size(),3); + for( int i = _outputs.size(); i<lim; i++ ) + sb.append(" "); + sb.append(" ]] "); + if( _type!= null ) _type.print(sb); + sb.append("\n"); } - // Every Node implements this. - abstract StringBuilder _print1(StringBuilder sb); + public boolean isMultiHead() { return false; } + public boolean isMultiTail() { return false; } + + // ------------------------------------------------------------------------ + // Graph Node & Edge manipulation /** * Gets the ith input node @@ -228,6 +261,20 @@ public abstract class Node { public <N extends Node> N keep() { addUse(null); return (N)this; } // Remove bogus null. public <N extends Node> N unkeep() { delUse(null); return (N)this; } + + + // Replace self with nnn in the graph, making 'this' go dead + void subsume( Node nnn ) { + assert nnn!=this; + while( nOuts() > 0 ) { + Node n = _outputs.removeLast(); + int idx = Utils.find(n._inputs, this); + n._inputs.set(idx,nnn); + nnn.addUse(n); + } + kill(); + } + // ------------------------------------------------------------------------ // Graph-based optimizations diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java index 6a56ff64..4c0be167 100644 --- a/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -3,14 +3,16 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +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) { - in(1)._print0(sb.append("(!")); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("(!"), visited); return sb.append(")"); } diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index f7cf917e..46646773 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -2,6 +2,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; +import java.util.BitSet; + public class PhiNode extends Node { final String _label; @@ -11,19 +13,27 @@ public class PhiNode extends Node { @Override public String label() { return "Phi_"+_label; } @Override - StringBuilder _print1(StringBuilder sb) { + StringBuilder _print1(StringBuilder sb, BitSet visited) { + if( region().inProgress() ) + sb.append("Z"); sb.append("Phi("); - for( Node in : _inputs ) - in._print0(sb).append(","); + 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; } - Node region() { return in(0); } + RegionNode region() { return (RegionNode)in(0); } + @Override public boolean isMultiTail() { return true; } @Override public Type compute() { + if( !(region() instanceof RegionNode r) || r.inProgress() ) + return Type.BOTTOM; Type t = Type.TOP; for (int i = 1; i < nIns(); i++) t = t.meet(in(i)._type); @@ -32,6 +42,9 @@ public class PhiNode extends Node { @Override public Node idealize() { + if( !(region() instanceof RegionNode r ) || r.inProgress() ) + return null; + // If we have only a single unique input, become it. Node live = singleUniqueInput(); if (live != null) @@ -77,5 +90,10 @@ public class PhiNode extends Node { return live; } - + @Override + boolean allCons() { + if( !(region() instanceof RegionNode r) || r.inProgress() ) + return false; + return super.allCons(); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 85f28037..3c3f73b8 100644 --- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeTuple; +import java.util.BitSet; + public class ProjNode extends Node { // Which slice of the incoming multi-part value @@ -21,9 +23,10 @@ public class ProjNode extends Node { public String label() { return _label; } @Override - StringBuilder _print1(StringBuilder sb) { return sb.append(_label); } + StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(_label); } @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; } + @Override public boolean isMultiTail() { return in(0).isMultiHead(); } public MultiNode ctrl() { return (MultiNode)in(0); } diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 9b51a277..e357796b 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -3,21 +3,26 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; +import java.util.BitSet; + public class RegionNode extends Node { - public RegionNode(Node... inputs) { super(inputs); } + + public RegionNode(Node... nodes) { super(nodes); } @Override public String label() { return "Region"; } @Override - StringBuilder _print1(StringBuilder sb) { + StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(label()).append(_nid); } @Override public boolean isCFG() { return true; } + @Override public boolean isMultiHead() { return true; } @Override public Type compute() { + if( inProgress() ) return Type.CONTROL; Type t = Type.XCONTROL; for (int i = 1; i < nIns(); i++) t = t.meet(in(i)._type); @@ -26,6 +31,7 @@ public class RegionNode extends Node { @Override public Node idealize() { + if( inProgress() ) return null; int path = findDeadInput(); if( path != 0 ) { for( Node phi : _outputs ) @@ -71,4 +77,9 @@ public class RegionNode extends Node { lca = in(i).domLCA(lca); return lca; } + + // True if last input is null + public final boolean inProgress() { + return in(nIns()-1) == null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 6130d050..312058b9 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -2,6 +2,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.*; +import java.util.BitSet; + /** * The Return node has two inputs. The first input is a control node and the * second is the data node that supplies the return value. @@ -24,8 +26,8 @@ public class ReturnNode extends Node { public String label() { return "Return"; } @Override - StringBuilder _print1(StringBuilder sb) { - return expr()._print0(sb.append("return ")).append(";"); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + return expr()._print0(sb.append("return "), visited).append(";"); } @Override public boolean isCFG() { return true; } diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index a7a04a42..a4fcbe65 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -33,22 +33,16 @@ public class ScopeNode extends Node { @Override public String label() { return "Scope"; } @Override - StringBuilder _print1(StringBuilder sb) { - sb.append(label()); - for( HashMap<String,Integer> scope : _scopes ) { - sb.append("["); - boolean first=true; - for( String name : scope.keySet() ) { - if( !first ) sb.append(", "); - first=false; - sb.append(name).append(":"); - Node n = in(scope.get(name)); - if( n==null ) sb.append("null"); - else n._print0(sb); - } - sb.append("]"); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + sb.append("Scope[ "); + String[] names = reverseNames(); + for( int j=0; j<nIns(); j++ ) { + sb.append(names[j]).append(":"); + Node n = in(j); + n._print0(sb, visited).append(" "); } - return sb; + sb.setLength(sb.length()-1); + return sb.append("]"); } /** @@ -139,7 +133,8 @@ public class ScopeNode extends Node { * <p> * The new Scope is a full-fledged Node with proper use<->def edges. */ - public ScopeNode dup() { + public ScopeNode dup() { return dup(false); } + public ScopeNode dup(boolean loop) { ScopeNode dup = new ScopeNode(); // Our goals are: // 1) duplicate the name bindings of the ScopeNode across all stack levels @@ -147,9 +142,19 @@ public class ScopeNode extends Node { // 3) Ensure that the order of defs is the same to allow easy merging for( HashMap<String,Integer> syms : _scopes ) dup._scopes.push(new HashMap<>(syms)); + dup.addDef(ctrl()); // Control input is just copied - for( int i=1; i<nIns(); i++ ) - dup.addDef(in(i)); + for( int i=1; i<nIns(); i++ ) { + if ( !loop ) { dup.addDef(in(i)); } + else { + String[] names = reverseNames(); // Get the variable names + // Create a phi node with second input as null - to be filled in + // by endLoop() below + dup.addDef(new PhiNode(names[i], ctrl(), in(i), null).peephole()); + // Ensure our node has the same phi in case we created one + setDef(i, dup.in(i)); + } + } return dup; } @@ -172,4 +177,21 @@ public class ScopeNode extends Node { return r.unkeep().peephole(); } + // Merge the backedge scope into this loop head scope + // We set the second input to the phi from the back edge (i.e. loop body) + public void endLoop(ScopeNode back, ScopeNode exit ) { + Node ctrl = ctrl(); + assert ctrl instanceof LoopNode loop && loop.inProgress(); + ctrl.setDef(2,back.ctrl()); + for( int i=1; i<nIns(); i++ ) { + PhiNode phi = (PhiNode)in(i); + assert phi.region()==ctrl && phi.in(2)==null; + phi.setDef(2,back.in(i)); + // Do an eager useless-phi removal + Node in = phi.peephole(); + if( in != phi ) + phi.subsume(in); + } + back.kill(); // Loop backedge is dead + } } diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index 6b98aed7..bab0f18c 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeTuple; +import java.util.BitSet; + /** * The Start node represents the start of the function. For now, we do not * have any inputs to Start because our function does not yet accept @@ -24,11 +26,12 @@ public class StartNode extends MultiNode { public String label() { return "Start"; } @Override - StringBuilder _print1(StringBuilder sb) { + StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(label()); } @Override public boolean isCFG() { return true; } + @Override public boolean isMultiHead() { return true; } @Override public TypeTuple compute() { return _args; } diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java index 01574dc7..417790d9 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -2,6 +2,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; +import java.util.BitSet; + public class StopNode extends Node { public StopNode(Node... inputs) { super(inputs); @@ -13,11 +15,11 @@ public class StopNode extends Node { } @Override - StringBuilder _print1(StringBuilder sb) { - if( ret()!=null ) return ret()._print0(sb); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + if( ret()!=null ) return ret()._print0(sb, visited); sb.append("Stop[ "); for( Node ret : _inputs ) - ret._print0(sb).append(" "); + ret._print0(sb, visited).append(" "); return sb.append("]"); } diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index bd43bc6c..421e659b 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -3,15 +3,17 @@ 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) { - in(1)._print0(sb.append("(")); - in(2)._print0(sb.append("-")); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append("-"), visited); return sb.append(")"); } diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index 84ef99f2..9f33520e 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.Node; import java.util.ArrayList; -/** Chapter 6's view of the IR; browser, transport and layout are shared. */ +/** Chapter 7'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; } @@ -37,6 +37,7 @@ public class SimpleGraphAdapter extends GraphAdapter<Node> { if( n instanceof StopNode ) return Kind.STOP; if( n instanceof ScopeNode ) return Kind.SCOPE; 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.isCFG() ? Kind.CTRL : Kind.DATA; diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index ea9a705e..1835f53f 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.io.IOException; -/** Chapter 6's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 7's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture<Node> { private Parser _parser; private Node _ret; |