diff options
Diffstat (limited to 'src/main/java')
21 files changed, 210 insertions, 27 deletions
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 22c36746..5ee742f7 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.*; + public class AddNode extends Node { public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); } diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 3a5e1a8f..e363bf75 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; + abstract public class BoolNode extends Node { public BoolNode(Node lhs, Node rhs) { diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 5efe29b7..19166ec6 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; + /** * A Constant node represents a constant value. At present, the only constants * that we allow are integer literals; therefore Constants contain an integer @@ -36,6 +37,8 @@ public class ConstantNode extends Node { return p.p(_con); } + @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 f6b4e03e..4c3c2feb 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -4,6 +4,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; + public class DivNode extends Node { public DivNode(Node lhs, Node rhs) { super(null, lhs, rhs); } diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 05c1c844..52d7e31e 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeTuple; + public class IfNode extends MultiNode { public IfNode(Node ctrl, Node pred) { @@ -17,6 +18,7 @@ public class IfNode extends MultiNode { @Override protected String format() { return "if( %1 )"; } @Override public boolean isCFG() { return true; } + @Override public boolean isMultiHead() { return true; } public Node ctrl() { return in(0); } public Node pred() { return in(1); } @@ -24,7 +26,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 bb5f155d..fb51777e 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -4,6 +4,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; + public class MinusNode extends Node { public MinusNode(Node in) { super(null, in); } diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index d7c65b26..2d0fa95b 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -4,6 +4,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; + public class MulNode extends Node { public MulNode(Node lhs, Node rhs) { super(null, lhs, rhs); } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 23f15ebe..1430cdac 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -71,6 +71,12 @@ public abstract class Node extends BaseNode<Node> { // Easy reading label for debugger, e.g. "Add" or "Region" or "EQ" public abstract String label(); + public boolean isMultiHead() { return false; } + public boolean isMultiTail() { return false; } + + // ------------------------------------------------------------------------ + // Graph Node & Edge manipulation + @Override public String typeName() { return _type==null ? null : _type.toString(); } /** @@ -190,6 +196,19 @@ public abstract class Node extends BaseNode<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 a9781ce1..538016bd 100644 --- a/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -4,6 +4,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; + public class NotNode extends Node { public NotNode(Node in) { super(null, in); } diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 6acb5535..64cd3dd7 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -4,6 +4,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; + public class PhiNode extends Node { final String _label; @@ -14,16 +15,20 @@ public class PhiNode extends Node { @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + if( region().inProgress() ) + p.p("Z"); p.p("Phi("); - for( Node in : _inputs ) - p.n(in).p(","); + for( Node in : _inputs ) p.n(in).p(","); return p.unchar(',').close(); } - 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 +37,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 +85,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 e313d31b..605c73bd 100644 --- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeTuple; + public class ProjNode extends Node { // Which slice of the incoming multi-part value @@ -26,6 +27,7 @@ public class ProjNode extends Node { 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(); } 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 cbd51743..e0dd45d7 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -5,8 +5,10 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; + public class RegionNode extends Node { - public RegionNode(Node... inputs) { super(inputs); } + + public RegionNode(Node... nodes) { super(nodes); } @Override public String label() { return "Region"; } @@ -16,9 +18,11 @@ public class RegionNode extends Node { } @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); @@ -27,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 ) @@ -72,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 b8bc8859..9f4cad7a 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -4,6 +4,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.*; + /** * 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. diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 86f4778e..bd6b0d8c 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -36,21 +36,14 @@ public class ScopeNode extends Node { @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { - p.p(label()); - for( HashMap<String,Integer> scope : _scopes ) { - p.p("["); - boolean first=true; - for( String name : scope.keySet() ) { - if( !first ) p.p(", "); - first=false; - p.p(name).p(":"); - Node n = in(scope.get(name)); - if( n==null ) p.p("null"); - else p.n(n); - } - p.p("]"); + p.p("Scope[ "); + String[] names = reverseNames(); + for( int j=0; j<nIns(); j++ ) { + p.p(names[j]).p(":"); + Node n = in(j); + p.n(n).p(" "); } - return p; + return p.unchar(' ').p("]"); } /** @@ -141,7 +134,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 @@ -149,9 +143,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; } @@ -174,4 +178,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 199845fe..56689503 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeTuple; + /** * 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 @@ -30,6 +31,7 @@ public class StartNode extends MultiNode { } @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 fe10b1ce..aa655f63 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -4,6 +4,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; + public class StopNode extends Node { public StopNode(Node... inputs) { super(inputs); diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index 7a6e1a4b..bf938504 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -4,6 +4,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; + public class SubNode extends Node { public SubNode(Node lhs, Node rhs) { super(null, lhs, rhs); } diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index 24614ad4..c5ab1c60 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -5,7 +5,7 @@ import com.seaofnodes.graph.GraphSnapshot.*; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.Node; -/** 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 String[] edgeNames(Node n) { @@ -17,6 +17,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; |