From f13a809597991b705db6f185bd356c34eca967be Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 11 Nov 2024 11:39:32 -0800 Subject: Allow pre-inc/dec on variables --- .../main/java/com/seaofnodes/simple/IterPeeps.java | 19 +++++++-------- .../main/java/com/seaofnodes/simple/Parser.java | 28 ++++++++++++++++++---- .../java/com/seaofnodes/simple/node/PhiNode.java | 2 +- .../java/com/seaofnodes/simple/BrainFuckTest.java | 6 ++--- .../java/com/seaofnodes/simple/Chapter08Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter11Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter17Test.java | 12 ++++++++++ 7 files changed, 49 insertions(+), 22 deletions(-) (limited to 'chapter17/src') 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. - * + *
* 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. + *
+ * Lather, Rinse, Repeat until the worklist runs dry. + *

* The main issues we have to deal with: * *

*/ @@ -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. * * 
-     *     unaryExpr : ('-') | '!') unaryExpr | postfixExpr | primaryExpr
+     *     unaryExpr : ('-') unaryExpr | '!') unaryExpr | postfixExpr | primaryExpr | '--' Id | '++' Id
      *
* @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; @@ -87,6 +88,17 @@ return s.x; assertEquals(65535L, Evaluator.evaluate(stop, 2)); } + @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(""" -- cgit v1.2.3