diff options
8 files changed, 63 insertions, 32 deletions
diff --git a/chapter17/README.md b/chapter17/README.md index b9733873..fa268293 100644 --- a/chapter17/README.md +++ b/chapter17/README.md @@ -1,7 +1,7 @@ # Chapter 17: Syntax Sugar -## Post-increment +## Pre/Post-increment Allow `arg++` and `arg--` with the usual meanings; the value is updated and the expression is the pre-update value. Greedy match is used so `arg---arg` parses @@ -9,6 +9,8 @@ as `(arg--)-arg`. Also allows `s.fld++` and `ary[idx]++`, and their `--` variants. +Allow pre-increment for identifiers only, for now: `--pc`. + ## var & val @@ -19,7 +21,7 @@ value), whose type will be inferred from the initalizing expression. The inferred value is the `glb` of the peephole type, which means `var` and `val` will not infer types like `u8` or `f32`, instead inferring `int` and -`flt` respectively. Struct types will always infer as nullable, so e.g. +`flt` respectively. Reference types will always infer as nullable, so e.g. `var s = new S;` @@ -93,12 +95,10 @@ return p.x; ```cpp struct Bar { int x; }; -Bar b = new Bar; /* b = null; *//* b.x++; */ // immutable & deep immutable -Bar !b = new Bar; b = null; /* b.x++; */ // mutable & deep immutable -Bar b! = new Bar; /* b = null; */ b.x++; // immutable & deep mutable -Bar !b! = new Bar; b = null; b.x++; // mutable & deep mutable (ignoring NPE) -val b = new Bar; /* b = null; *//* b.x++; */ // immutable & deep immutable -var b = new Bar; b = null; b.x++; // mutable & inherits deep mutability from RHS +Bar b = new Bar; /* b = new Bar; *//* b.x++; */ // immutable & deep immutable +Bar !b = new Bar; b = new Bar; b.x++; // mutable & deep mutable +val b = new Bar; /* b = new Bar; *//* b.x++; */ // immutable & deep immutable +var b = new Bar; b = new Bar; b.x++; // mutable & inherits deep mutability from RHS ``` @@ -114,6 +114,8 @@ Allow C/C++ style `for` loops: `for( init; test; next ) body` +Example: + ```cpp int sum=0; for( int i=0; i<arg; i++ ) @@ -128,12 +130,14 @@ Any of `init`, `test` and `next` can be empty. int sum=0; for( int i=0; i<arg; i++ ) sum = sum + i; -return sum; +return i; // ERROR: Undefined name 'i' ``` - +pre-dec +finalize final +TODO for-interator switch diff --git a/chapter17/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter17/src/main/java/com/seaofnodes/simple/IterPeeps.java index 81b89513..36f053f9 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -1,25 +1,24 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.type.Type; -import java.util.ArrayList; import java.util.Arrays; import java.util.BitSet; import java.util.Random; /** - * The IterOptim runs after parsing. It iterates the peepholes to a fixed point + * The IterPeeps runs after parsing. It iterates the peepholes to a fixed point * so that no more peepholes apply. This should be linear because peepholes rarely * (never?) increase code size. The graph should monotonically reduce in some * dimension, which is usually size. It might also reduce in e.g. number of * MulNodes or Load/Store nodes, swapping out more "expensive" Nodes for cheaper * ones. - * + * <br> * The theoretical overall worklist is mindless just grabbing the next thing and - * doing it. If the graph changes, put the neighbors on the worklist. Lather, - * Rinse, Repeat until the worklist runs dry. - * + * doing it. If the graph changes, put the neighbors on the worklist. + * <br> + * Lather, Rinse, Repeat until the worklist runs dry. + * <p> * The main issues we have to deal with: * * <ul> @@ -29,7 +28,7 @@ import java.util.Random; * is stable and correct between peepholes. In our case `Node.subsume` does * most of the munging, building on our prior stable Node utilities.</li> * - * <li>Changing a Node also changes the graph "neighborhood". The neigbors need to + * <li>Changing a Node also changes the graph "neighborhood". The neighbors need to * be checked to see if THEY can also peephole, and so on. After any peephole * or graph update we put a Nodes uses and defs on the worklist.</li> * @@ -39,7 +38,7 @@ import java.util.Random; * check is linear at each peephole step... so quadratic overall. Its a useful * assert, but one we can disable once the overall algorithm is stable - and * then turn it back on again when some new set of peepholes is misbehaving. - * The code for this is turned on in `IterOptim.iterate` as `assert + * The code for this is turned on in `IterPeeps.iterate` as `assert * progressOnList(stop);`</li> * </ul> */ @@ -115,7 +114,7 @@ public abstract class IterPeeps { int old_cnt = Node.ITER_CNT, old_nop = Node.ITER_NOP_CNT; Node changed = stop.walk( n -> { Node m = n; - if( n.compute().isa(n._type) ) { // Types must be forwards, even if on worklist + if( n.compute().isa(n._type) && (!n.iskeep() || n._nid<=5) ) { // Types must be forwards, even if on worklist if( WORK.on(n) ) return null; m = n.peepholeOpt(); if( m==null ) return null; diff --git a/chapter17/src/main/java/com/seaofnodes/simple/Parser.java b/chapter17/src/main/java/com/seaofnodes/simple/Parser.java index a4f7462e..e2f8ad32 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/Parser.java @@ -476,7 +476,7 @@ public class Parser { _xScopes.pop(); // Discard pushed from graph display RegionNode r = ctrl(tScope.mergeScopes(fScope)); - Node ret = stmt ? r : peep(new PhiNode("",lhs._type.meet(rhs._type),r,lhs,rhs)); + Node ret = stmt ? r : peep(new PhiNode("",lhs._type.meet(rhs._type),r,lhs.unkeep(),rhs)); r.peephole(); return ret; } @@ -838,11 +838,29 @@ public class Parser { * Parse a unary minus expression. * * <pre> - * unaryExpr : ('-') | '!') unaryExpr | postfixExpr | primaryExpr + * unaryExpr : ('-') unaryExpr | '!') unaryExpr | postfixExpr | primaryExpr | '--' Id | '++' Id * </pre> * @return a unary expression {@link Node}, never {@code null} */ private Node parseUnary() { + // Pre-dec/pre-inc + int old = pos(); + if( match("--") || match("++") ) { + int delta = _lexer.peek(-1)=='+' ? 1 : -1; // Pre vs post + String name = _lexer.matchId(); + if( name!=null ) { + ScopeMinNode.Var n = _scope.lookup(name); + if( n != null ) { + if( n._final ) + throw error("Cannot reassign final '"+n._name+"'"); + Node expr = peep(new AddNode(_scope.in(n),con(delta))); + _scope.update(n,expr); + return expr; + } + } + // Reset, try again + pos(old); + } if (match("-")) return peep(new MinusNode(parseUnary()).widen()); if (match("!")) return peep(new NotNode(parseUnary())); return parsePostfix(parsePrimary()); @@ -892,7 +910,7 @@ public class Parser { if( t==null ) throw error("Expected a type"); // Parse ary[ length_expr ] if( match("[") ) { - Node len = parseExpression().keep(); + Node len = parseExpression(); if( !(len._type instanceof TypeInteger) ) throw error("Cannot allocate an array with length "+len._type); require("]"); @@ -964,8 +982,8 @@ public class Parser { private Node newArray(TypeStruct ary, Node len) { int base = ary.aryBase (); int scale= ary.aryScale(); - Node size = peep(new AddNode(con(base),peep(new ShlNode(len,con(scale))))); - ALTMP.clear(); ALTMP.add(len); ALTMP.add(con(ary._fields[1]._type.makeInit())); + Node size = peep(new AddNode(con(base),peep(new ShlNode(len.keep(),con(scale))))); + ALTMP.clear(); ALTMP.add(len.unkeep()); ALTMP.add(con(ary._fields[1]._type.makeInit())); return newStruct(ary,size,0,ALTMP); } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/PhiNode.java index f0140ce6..58ce6b47 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -101,7 +101,7 @@ public class PhiNode extends Node { if( in(2)._type == in(2)._type.makeInit() ) nullx = 2; if( nullx != -1 ) { Node val = in(3-nullx); - if( r.idom(this) instanceof IfNode iff && iff.pred().addDep(this)==val ) { + if( r.idom(this).addDep(this) instanceof IfNode iff && iff.pred().addDep(this)==val ) { // Must walk the idom on the null side to make sure we hit False. CFGNode idom = (CFGNode)r.in(nullx); while( idom.nIns() > 0 && idom.in(0) != iff ) idom = idom.idom(); diff --git a/chapter17/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/chapter17/src/test/java/com/seaofnodes/simple/BrainFuckTest.java index 28c3477c..0c2509bf 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/BrainFuckTest.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -48,8 +48,7 @@ for( int pc = 0; pc < program#; pc++ ) { } else if (command == 91) { if (data[d] == 0) { for( var d = 1; d > 0; ) { - pc++; - command = program[pc]; + command = program[++pc]; if (command == 91) d++; if (command == 93) d--; } @@ -57,8 +56,7 @@ for( int pc = 0; pc < program#; pc++ ) { } else if (command == 93) { if (data[d]) { for( var d = 1; d > 0; ) { - pc--; - command = program[pc]; + command = program[--pc]; if (command == 93) d++; if (command == 91) d--; } diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter08Test.java index 29fd09dc..bb3bd674 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -138,7 +138,7 @@ return arg; @Test public void testRegress2() { - Parser parser = new Parser("if(1) return 0; else while(arg>--arg) arg=arg+1; return 0;"); + Parser parser = new Parser("if(1) return 0; else while(arg>- -arg) arg=arg+1; return 0;"); StopNode stop = parser.parse().iterate(); assertEquals("return 0;", stop.toString()); } diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 11424720..ddcc9e63 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -292,7 +292,7 @@ else { } """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 9; return 0; return 0; ]", stop.toString()); + assertEquals("Stop[ return 9; return 0; return 0; return 0; return 0; return 0; return 0; return 0; ]", stop.toString()); } diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter17Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter17Test.java index d39cee2d..3773f87f 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter17Test.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter17Test.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.StopNode; import org.junit.Test; +import org.junit.Ignore; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; @@ -88,6 +89,17 @@ return s.x; } @Test + public void testInc6() { + Parser parser = new Parser(""" +return --arg; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return (arg+-1);", stop.toString()); + assertEquals(-1L, Evaluator.evaluate(stop, 0)); + } + + + @Test public void testVar0() { Parser parser = new Parser(""" var d; |