diff options
Diffstat (limited to 'chapter08/src')
7 files changed, 478 insertions, 78 deletions
diff --git a/chapter08/src/main/java/com/seaofnodes/simple/GraphEvaluator.java b/chapter08/src/main/java/com/seaofnodes/simple/GraphEvaluator.java new file mode 100644 index 00000000..cbd6f1f9 --- /dev/null +++ b/chapter08/src/main/java/com/seaofnodes/simple/GraphEvaluator.java @@ -0,0 +1,175 @@ +package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.TypeInteger;
+
+import java.util.Arrays;
+import java.util.BitSet;
+import java.util.HashMap;
+
+public class GraphEvaluator {
+
+ /**
+ * Find the start node from some node in the graph or null if there is no start node
+ */
+ private static StartNode findStart(BitSet visit, Node node) {
+ if (node == null) return null;
+ if (node instanceof StartNode start) return start;
+ if( visit.get(node._nid) ) return null;
+ visit.set(node._nid);
+ for( Node def : node._inputs ) {
+ var res = findStart(visit,def);
+ if( res != null ) return res;
+ }
+ for( Node use : node._outputs ) {
+ var res = findStart(visit,use);
+ if( res != null ) return res;
+ }
+ return null;
+ }
+
+ /**
+ * Find the control output from a control node
+ */
+ private static Node findControl(Node control) {
+ for( Node use : control._outputs ) {
+ if (use.isCFG()) return use;
+ }
+ return null;
+ }
+
+ /**
+ * Find the projection for a node
+ */
+ private static ProjNode findProjection(Node node, int idx) {
+ for( Node use : node._outputs ) {
+ if (use instanceof ProjNode proj && proj._idx == idx) return proj;
+ }
+ return null;
+ }
+
+ private static RuntimeException timeout() {
+ return new RuntimeException("Timeout");
+ }
+
+ /**
+ * Cache values for phi and parameter projection nodes.
+ */
+ private final HashMap<Node, Long> cacheValues = new HashMap<>();
+ /**
+ * Cache for loop phis as they can depend on itself or other loop phis
+ */
+ private long[] loopPhiCache = new long[16];
+
+ private GraphEvaluator() {
+ }
+
+ private long div(DivNode div) {
+ long in2 = getValue(div.in(2));
+ return in2 == 0 ? 0 : getValue(div.in(1)) / in2;
+ }
+
+ /**
+ * Calculate the value of a node
+ */
+ private long getValue(Node node) {
+ var cache = cacheValues.get(node);
+ if (cache != null) return cache;
+ return switch (node) {
+ case ConstantNode cons -> ((TypeInteger)cons.compute()).value();
+ case AddNode add -> getValue(add.in(1)) + getValue(add.in(2));
+ case BoolNode.EQ eq -> getValue(eq.in(1)) == getValue(eq.in(2)) ? 1 : 0;
+ case BoolNode.LE le -> getValue(le.in(1)) <= getValue(le.in(2)) ? 1 : 0;
+ case BoolNode.LT lt -> getValue(lt.in(1)) < getValue(lt.in(2)) ? 1 : 0;
+ case DivNode div -> div(div);
+ case MinusNode minus -> -getValue(minus.in(1));
+ case MulNode mul -> getValue(mul.in(1)) * getValue(mul.in(2));
+ case NotNode not -> getValue(not.in(1)) == 0 ? 1 : 0;
+ case SubNode sub -> getValue(sub.in(1)) - getValue(sub.in(2));
+ default -> throw Utils.TODO("Unexpected node " + node);
+ };
+ }
+
+ /**
+ * Special case of latchPhis when phis can depend on phis of the same region.
+ */
+ private void latchLoopPhis(RegionNode region, Node prev) {
+ int idx = Utils.find(region._inputs, prev);
+ assert idx > 0;
+ int i = 0;
+ for( Node use : region._outputs ) {
+ if (use instanceof PhiNode phi) {
+ var value = getValue(phi.in(idx));
+ if (i == loopPhiCache.length) loopPhiCache = Arrays.copyOf(loopPhiCache, loopPhiCache.length*2);
+ loopPhiCache[i++] = value;
+ }
+ }
+ i = 0;
+ for( Node use : region._outputs ) {
+ if (use instanceof PhiNode phi) cacheValues.put(phi, loopPhiCache[i++]);
+ }
+ }
+
+ /**
+ * Calculate the values of phis of the region and caches the values. The phis are not allowed to depend on other phis of the region.
+ */
+ private void latchPhis(RegionNode region, Node prev) {
+ int idx = Utils.find(region._inputs, prev);
+ assert idx > 0;
+ for( Node use : region._outputs ) {
+ if (use instanceof PhiNode phi) {
+ var value = getValue(phi.in(idx));
+ cacheValues.put(phi, value);
+ }
+ }
+ }
+
+ /**
+ * Run the graph until either a return is found or the number of loop iterations are done.
+ */
+ private long evaluate(StartNode start, long parameter, int loops) {
+ var parameter1 = findProjection(start, 1);
+ if (parameter1 != null) cacheValues.put(parameter1, parameter);
+ Node control = findProjection(start, 0);
+ Node prev = start;
+ while (control != null) {
+ Node next;
+ switch (control) {
+ case RegionNode region -> {
+ if (region instanceof LoopNode && region.in(1) != prev) {
+ if (loops--<=0) throw timeout();
+ latchLoopPhis(region, prev);
+ } else {
+ latchPhis(region, prev);
+ }
+ next = findControl(region);
+ }
+ case IfNode cond -> next = findProjection(cond, getValue(cond.in(1)) != 0 ? 0 : 1);
+ case ReturnNode ret -> {
+ return getValue(ret.in(1));
+ }
+ case ProjNode ignored -> next = findControl(control);
+ default -> throw Utils.TODO("Unexpected control node " + control);
+ }
+ prev = control;
+ control = next;
+ }
+ return 0;
+ }
+
+ public static long evaluate(Node graph) {
+ return evaluate(graph, 0);
+ }
+
+ public static long evaluate(Node graph, long parameter) {
+ return evaluate(graph, parameter, 1000);
+ }
+
+ public static long evaluate(Node graph, long parameter, int loops) {
+ var start = findStart(new BitSet(), graph);
+ if (start == null) throw timeout();
+ var evaluator = new GraphEvaluator();
+ return evaluator.evaluate(start, parameter, loops);
+ }
+
+}
diff --git a/chapter08/src/main/java/com/seaofnodes/simple/Parser.java b/chapter08/src/main/java/com/seaofnodes/simple/Parser.java index 41803f24..45332396 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/Parser.java @@ -13,7 +13,6 @@ import java.util.*; * This is a simple recursive descent parser. All lexical analysis is done here as well. */ public class Parser { - public static boolean LAZY = false; /** * A Global Static, unique to each compilation. This is a public, so we @@ -47,6 +46,8 @@ public class Parser { * List of keywords disallowed as identifiers */ private final HashSet<String> KEYWORDS = new HashSet<>(){{ + add("break"); + add("continue"); add("else"); add("false"); add("if"); @@ -63,10 +64,14 @@ public class Parser { */ public final Stack<ScopeNode> _xScopes = new Stack<>(); + ScopeNode _continueScope; + ScopeNode _breakScope; + public Parser(String source, TypeInteger arg) { Node.reset(); _lexer = new Lexer(source); _scope = new ScopeNode(); + _continueScope = _breakScope = null; START = new StartNode(new Type[]{ Type.CONTROL, arg }); STOP = new StopNode(); } @@ -137,6 +142,8 @@ public class Parser { else if (match ("{" )) return require(parseBlock(),"}"); else if (matchx("if" )) return parseIf(); else if (matchx("while")) return parseWhile(); + else if (matchx("break")) return parseBreak(); + else if (matchx("continue")) return parseContinue(); else if (matchx("#showGraph")) return require(showGraph(),";"); else return parseExpressionStatement(); } @@ -150,65 +157,104 @@ public class Parser { * @return a {@link Node}, never {@code null} */ private Node parseWhile() { + + var savedContinueScope = _continueScope; + var savedBreakScope = _breakScope; + 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. + // associated phis; see {@code inProgress()}. - ctrl(new LoopNode(ctrl(),null).peephole()); // Note we set back edge to null here + 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 = _xScopes.push(_scope).keep(); + ScopeNode head = _scope.keep(); // Clone the head Scope to create a new Scope for the body. // Create phis eagerly as part of cloning - _scope = _scope.dup(true); // The true argument triggers creating phis + _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).<IfNode>keep().peephole(); + 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); + // Clone the body Scope to create the break/exit Scope which accounts for any + // side effects in the predicate. The break/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. + ctrl(ifF); + _xScopes.push(_breakScope = _scope.dup()); + // No continues yet + _continueScope = null; + // 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. + // Merge the loop bottom into other continue statements + if (_continueScope != null) { + _continueScope = jumpTo(_continueScope); + _scope.kill(); + _scope = _continueScope; + } + + // The true branch loops back, so whatever is current _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. + var exit = _breakScope; head.endLoop(_scope, exit); head.unkeep().kill(); _xScopes.pop(); // Cleanup _xScopes.pop(); // Cleanup + _continueScope = savedContinueScope; + _breakScope = savedBreakScope; + // At exit the false control is the current control, and // the scope is the exit scope after the exit test. - return (_scope = exit); + return _scope = exit; } + private ScopeNode jumpTo(ScopeNode toScope) { + ScopeNode cur = _scope.dup(); + ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill current scope + // Prune nested lexical scopes that have depth > than the loop head + // We use _breakScope as a proxy for the loop head scope to obtain the depth + while( cur._scopes.size() > _breakScope._scopes.size() ) + cur.pop(); + // If this is a continue then first time the target is null + // So we just use the pruned current scope as the base for the + // continue + if (toScope == null) + return cur; + // toScope is either the break scope, or a scope that was created here + assert toScope._scopes.size() <= _breakScope._scopes.size(); + toScope.mergeScopes(cur); + return toScope; + } + + private void checkLoopActive() { if (_breakScope == null) throw Parser.error("No active loop for a break or continue"); } + + private Node parseBreak () { checkLoopActive(); return ( _breakScope = require(jumpTo( _breakScope ),";")); } + private Node parseContinue() { checkLoopActive(); return (_continueScope = require(jumpTo( _continueScope ),";")); } + /** * Parses a statement * @@ -339,10 +385,10 @@ public class Parser { var lhs = parseAddition(); if (match("==")) return new BoolNode.EQ(lhs, parseComparison()).peephole(); if (match("!=")) return new NotNode(new BoolNode.EQ(lhs, parseComparison()).peephole()).peephole(); - if (match("<" )) return new BoolNode.LT(lhs, parseComparison()).peephole(); if (match("<=")) return new BoolNode.LE(lhs, parseComparison()).peephole(); - if (match(">" )) return new BoolNode.LT(parseComparison(), lhs).peephole(); + if (match("<" )) return new BoolNode.LT(lhs, parseComparison()).peephole(); if (match(">=")) return new BoolNode.LE(parseComparison(), lhs).peephole(); + if (match(">" )) return new BoolNode.LT(parseComparison(), lhs).peephole(); return lhs; } @@ -439,7 +485,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); } @@ -448,7 +494,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/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java index eaf19199..0ed32464 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -6,7 +6,7 @@ import java.util.BitSet; public class LoopNode extends RegionNode { - public LoopNode( Node entry, Node back) { super(null,entry,back); } + public LoopNode( Node entry ) { super(null,entry,null); } Node entry() { return in(1); } Node back () { return in(2); } @@ -15,21 +15,9 @@ public class LoopNode extends RegionNode { public String label() { return "Loop"; } @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - return sb.append("Loop").append(_nid); - } - - @Override - public Type compute() { - return inProgress() ? Type.CONTROL : super.compute(); - } - - @Override public Node idealize() { return inProgress() ? null : super.idealize(); } - @Override Node idom() { return entry(); } - - @Override public boolean inProgress() { return back()==null; } + @Override Node idom() { return entry(); } } diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java index 4cd1b3d2..52d4c1e4 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java @@ -153,8 +153,6 @@ public abstract class Node { public int nIns() { return _inputs.size(); } - public Node out(int i) { return _outputs.get(i); } - public int nOuts() { return _outputs.size(); } public boolean isUnused() { return nOuts() == 0; } @@ -229,11 +227,11 @@ public abstract class Node { // Error is 'use' does not exist; ok for 'use' to be null. protected boolean delUse( Node use ) { Utils.del(_outputs, Utils.find(_outputs, use)); - return _outputs.size() == 0; + return _outputs.isEmpty(); } // Shortcut for "popping" n nodes. A "pop" is basically a - // set_def(last,null) followed by lowering the nIns() count. + // setDef(last,null) followed by lowering the nIns() count. void popN(int n) { for( int i=0; i<n; i++ ) { Node old_def = _inputs.removeLast(); @@ -443,7 +441,10 @@ public abstract class Node { * Used to allow repeating tests in the same JVM. This just resets the * Node unique id generator, and is done as part of making a new Parser. */ - public static void reset() { UNIQUE_ID = 1; _disablePeephole=false; } + public static void reset() { + UNIQUE_ID = 1; + _disablePeephole=false; + } /** * Debugging utility to find a Node by index diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 3b793758..00c010b2 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -7,8 +7,9 @@ import java.util.Collection; 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"; } @@ -22,6 +23,7 @@ public class RegionNode extends Node { @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); @@ -30,6 +32,7 @@ public class RegionNode extends Node { @Override public Node idealize() { + if( inProgress() ) return null; int path = findDeadInput(); if( path != 0 ) { for( Node phi : _outputs ) @@ -77,5 +80,8 @@ public class RegionNode extends Node { return (_idom=lhs); } - public boolean inProgress() { return false; } + // True if last input is null + public final boolean inProgress() { + return in(nIns()-1) == null; + } } diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 38dfe15d..dfd12253 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -164,25 +164,13 @@ public class ScopeNode extends Node { dup._scopes.push(new HashMap<>(syms)); dup.addDef(ctrl()); // Control input is just copied - for( int i=1; i<nIns(); i++ ) { - if ( !loop ) { dup.addDef(in(i)); } - else if (Parser.LAZY) { - // For lazy phi we need to set a sentinel that will - // trigger phi creation on update - dup.addDef(this); // Add a sentinel which is self - } - 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)); - } - } + for( int i=1; i<nIns(); i++ ) + // For lazy phis on loops we use a sentinel + // that will trigger phi creation on update + dup.addDef(loop ? this : in(i)); return dup; } - + /** * Merges the names whose node bindings differ, by creating Phi node for such names * The names could occur at all stack levels, but a given name can only differ in the @@ -195,18 +183,11 @@ public class ScopeNode extends Node { RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).keep()); String[] ns = reverseNames(); // Note that we skip i==0, which is bound to '$ctrl' - for (int i = 1; i < nIns(); i++) { - if( in(i) != that.in(i) ) { // No need for redundant Phis + for (int i = 1; i < nIns(); i++) + if( in(i) != that.in(i) ) // No need for redundant Phis // If we are in lazy phi mode we need to a lookup - // by name as it will triger a phi creation - Node phi; - if (Parser.LAZY) - phi = new PhiNode(ns[i], r, this.lookup(ns[i]), that.lookup(ns[i])).peephole(); - else - phi = new PhiNode(ns[i], r, in(i), that.in(i)).peephole(); - setDef(i, phi); - } - } + // by name as it will trigger a phi creation + setDef(i, new PhiNode(ns[i], r, this.lookup(ns[i]), that.lookup(ns[i])).peephole()); that.kill(); // Kill merged scope return r.unkeep().peephole(); } diff --git a/chapter08/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/chapter08/src/test/java/com/seaofnodes/simple/Chapter08Test.java index 6baa8215..16f7e324 100644 --- a/chapter08/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/chapter08/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Assert; import org.junit.Test; import static org.junit.Assert.*; @@ -9,6 +10,197 @@ import static org.junit.Assert.*; public class Chapter08Test { @Test + public void testChapter8Ex6() { + Parser parser = new Parser( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + break; + if (arg == 6) + break; +} +return arg; + """); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Region36,Phi(Region25,Phi(Loop6,arg,(Phi_arg+1)),Add),Add);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof RegionNode); + Assert.assertEquals(5, GraphEvaluator.evaluate(stop, 1)); + Assert.assertEquals(10, GraphEvaluator.evaluate(stop, 6)); + } + + + @Test + public void testChapter8Ex5() { + Parser parser = new Parser( + """ +int a = 1; +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 7) + continue; + a = a + 1; +} +return a; + """); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Loop7,1,Phi(Region42,Phi_a,(Phi_a+1)));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + System.out.println(IRPrinter.prettyPrint(stop,99)); + } + + + @Test + public void testChapter8Ex4() { + Parser parser = new Parser( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + break; +} +return arg; + """); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Region34,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof RegionNode); + } + + @Test + public void testChapter8Ex3() { + Parser parser = new Parser( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 6) + break; +} +return arg; + """); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Region25,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof RegionNode); + } + + + @Test + public void testChapter8Ex2() { + Parser parser = new Parser( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + continue; +} +return arg; + """); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + + @Test + public void testChapter8Ex1() { + Parser parser = new Parser( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; +} +return arg; + """); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testChapter8Regress1() { + Parser parser = new Parser( + """ +while( arg < 10 ) { + int a = arg+2; + if( a > 4 ) + break; +} +return arg; + """); + StopNode stop = parser.parse(true); + assertEquals("return arg;", stop.toString()); + System.out.println(IRPrinter.prettyPrint(stop,99)); + } + + @Test + public void testChapter8BreakOutsideLoop() { + try { + new Parser(""" +if(arg <= 10) { + break; + arg = arg + 1; +} +return arg; +""").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("No active loop for a break or continue",e.getMessage()); + } + } + + @Test + public void testChapter8Regress3() { + Parser parser = new Parser(""" +while(arg < 10) { + break; +} +return arg; +"""); + StopNode stop = parser.parse(true); + assertEquals("return arg;", stop.toString()); + } + + @Test + public void testChapter8Regress4() { + Parser parser = new Parser(""" +int a = 1; +while(arg < 10) { + a = a + 1; + if (arg > 2) { + int a = 17; + break; + } +} +return a; +"""); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Region28,Phi(Loop7,1,(Phi_a+1)),Add);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof RegionNode); + } + + @Test + public void testChapter8Regress5() { + Parser parser = new Parser(""" +int a = 1; +while(1) { + a = a + 1; + if (a<10) continue; + break; +} +return a; +"""); + StopNode stop = parser.parse(true); + assertEquals("return (Phi(Loop7,1,Add)+1);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof RegionNode); + } + + @Test public void testChapter7Example() { Parser parser = new Parser( """ @@ -39,7 +231,7 @@ if(arg){}else{ return a; """); StopNode stop = parser.parse(true); - assertEquals("return Phi(Region23,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString()); + assertEquals("return Phi(Region22,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString()); } @Test @@ -60,7 +252,7 @@ while(i < arg) { return sum; """); StopNode stop = parser.parse(true); - assertEquals("return Phi(Loop8,0,Phi(Loop21,Phi_sum,(Phi(Loop,0,(Phi_j+1))+Phi_sum)));", stop.toString()); + assertEquals("return Phi(Loop8,0,Phi(Loop20,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); System.out.println(IRPrinter.prettyPrint(stop,99)); } @@ -78,7 +270,7 @@ return b; """); Node._disablePeephole = true; StopNode stop = parser.parse(true); - assertEquals("return Phi(Loop8,2,Phi(Region27,Phi_b,4));", stop.toString()); + assertEquals("return Phi(Loop8,2,Phi(Region26,Phi_b,4));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); Node._disablePeephole = false; System.out.println(IRPrinter.prettyPrint(stop,99)); @@ -99,7 +291,7 @@ while(a < 10) { return b; """); StopNode stop = parser.parse(true); - assertEquals("return Phi(Loop8,2,(Phi(Region27,Phi_b,4)+1));", stop.toString()); + assertEquals("return Phi(Loop8,2,(Phi(Region26,Phi_b,4)+1));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); System.out.println(IRPrinter.prettyPrint(stop,99)); } @@ -674,7 +866,18 @@ return a;"""); assertEquals("Undefined name 'b'",e.getMessage()); } } + + @Test + public void testChapter5Regress1() { + try { + new Parser("if(arg==2) int a=1; else int b=2; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Cannot define a new name on one arm of an if",e.getMessage()); + } + } + @Test public void testChapter5BadNum() { try { @@ -957,7 +1160,7 @@ return a;"""); parser.parse(); StartNode start = Parser.START; for( Node use : start._outputs ) - if( use instanceof ConstantNode con ) + if( use instanceof ConstantNode con && con._type instanceof TypeInteger ) assertEquals(TypeInteger.constant(0),con._type); } |