diff options
Diffstat (limited to 'chapter18/src')
20 files changed, 92 insertions, 43 deletions
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java b/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java index 394b6d1c..51a6e78e 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java @@ -66,7 +66,7 @@ public class CodeGen { // Type check String err = _stop.walk( Node::err ); if( err != null ) - throw new RuntimeException(err); + throw new Parser.ParserException(err); return this; } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java index 6267c09d..79d5ce4a 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java @@ -1006,7 +1006,7 @@ public class Parser { String name = _lexer.matchId(); if( name!=null ) { ScopeMinNode.Var n = _scope.lookup(name); - if( n != null ) { + if( n != null && !(n.type() instanceof TypeMemPtr) ) { if( n._final ) throw error("Cannot reassign final '"+n._name+"'"); Node expr = n.type() instanceof TypeFloat @@ -1597,6 +1597,7 @@ public class Parser { if( "+-/*&|^".indexOf(ch0) == -1 ) return 0; char ch1 = (char)_input[_position+1]; if( ch1 == '=' ) { _position += 2; return ch0; } + if( isIdLetter((char)_input[_position+2]) ) return 0; if( ch0 == '+' && ch1 == '+' ) { _position += 2; return (char) 1; } if( ch0 == '-' && ch1 == '-' ) { _position += 2; return (char)-1; } return 0; @@ -1605,7 +1606,11 @@ public class Parser { public RuntimeException error( String errorMessage ) { // file:line:charoff err //String msg = "src:"+_line_number+":"+(_position-_line_start)+" "+errorMessage; - return new RuntimeException(errorMessage); + return new ParserException(errorMessage); } + + } + public static class ParserException extends RuntimeException { + ParserException(String msg) { super(msg); } } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java index bacc1935..78071920 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -109,6 +109,8 @@ public abstract class CFGNode extends Node { for( Node use : _outputs ) { if( !(use instanceof CFGNode usecfg) ) continue; if( usecfg instanceof XCtrlNode ) continue; + if( usecfg._type == Type.XCONTROL ) continue; // Dead, only possible if peeps disabled + if( usecfg._type == TypeTuple.IF_NEITHER ) continue; // Dead again // Child visited but not post-visited? if( !post.get(usecfg._nid) ) { // Must be a backedge to a LoopNode then diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/CastNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CastNode.java index 462d6cba..4adc81ff 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/CastNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CastNode.java @@ -22,6 +22,7 @@ public class CastNode extends Node { public String uniqueName() { return "Cast_" + _nid; } @Override public boolean isPinned() { return true; } + @Override public boolean isConst() { return true; } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { @@ -37,4 +38,13 @@ public class CastNode extends Node { public Node idealize() { return in(1)._type.isa(_t) ? in(1) : null; } + + @Override + boolean eq(Node n) { + CastNode cast = (CastNode)n; // Contract + return _t==cast._t; + } + + @Override + int hash() { return _t.hashCode(); } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 1528f2e9..c69d319e 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -70,7 +70,7 @@ public class LoadNode extends MemOpNode { while( true ) { switch( mem ) { case StoreNode st: - if( ptr == st.ptr() && off() == st.off() ) + if( ptr == st.ptr().addDep(this) && off() == st.off() ) return castRO(st.val()); // Proved equal // Can we prove unequal? Offsets do not overlap? if( !off()._type.join(st.off()._type).isHigh() && // Offsets overlap @@ -79,7 +79,10 @@ public class LoadNode extends MemOpNode { // Pointers cannot overlap mem = st.mem(); // Proved never equal break; - case PhiNode phi: break outer; // Assume related + case PhiNode phi: + // Assume related + phi.addDep(this); + break outer; case ConstantNode top: break outer; // Assume shortly dead case ProjNode mproj: if( mproj.in(0) instanceof NewNode nnn1 ) { diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 001ab8f2..f7f6f80d 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -53,29 +53,38 @@ public class LoopNode extends RegionNode { for( Node use : _outputs ) if( use instanceof PhiNode ) iff.addDef(use); - CProjNode t = new CProjNode(iff,0,"True" ); - CProjNode f = new CProjNode(iff,1,"False"); + CProjNode t = new CProjNode(iff,0,"True" ).init(); + CProjNode f = new CProjNode(iff,1,"False").init(); setDef(2,f); // Now fold control into the exit. Might have 1 valid exit, or an // XCtrl or a bunch of prior NeverNode exits. Node top = new ConstantNode(Type.TOP).peephole(); ReturnNode ret = fun.ret(); - if( ret.ctrl()._type == Type.XCONTROL ) { - ret.setDef(0,t); - ret.setDef(1,top); - ret.setDef(2,top); - } else { - RegionNode ctrl = ret.ctrl() instanceof RegionNode r ? r : new RegionNode(null,ret.ctrl()); - PhiNode mem = ret.mem () instanceof PhiNode phi && phi.in(0)==ctrl ? phi : new PhiNode(ctrl,ret.mem ()); - PhiNode expr = ret.expr() instanceof PhiNode phi && phi.in(0)==ctrl ? phi : new PhiNode(ctrl,ret.expr()); - if( ret.ctrl()!=ctrl ) ret.setDef(0,ctrl); - if( ret.mem ()!=mem ) ret.setDef(1,mem ); - if( ret.expr()!=expr ) ret.setDef(2,expr).peepholeOpt(); + Node ctrl = ret.ctrl(), mem = ret.mem(), expr = ret.expr(); + if( ctrl._type != Type.XCONTROL ) { + // Perfect aligned exit? + if( !(ctrl instanceof RegionNode r && + mem instanceof PhiNode pmem && pmem.region()==r && + expr instanceof PhiNode prez && prez.region()==r ) ) { + // Nope, insert an aligned exit layer + ctrl = new RegionNode(null,ctrl).init(); + mem = new PhiNode((RegionNode)ctrl,mem ).init(); + expr = new PhiNode((RegionNode)ctrl,expr).init(); + } + // Append new Never exit ctrl.addDef(t ); mem .addDef(top); expr.addDef(top); + } else { + ctrl = t; + mem = top; + expr = top; } + ret.setDef(0,ctrl); + ret.setDef(1,mem ); + ret.setDef(2,expr); + return stop; } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 96274789..f0e66952 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -48,6 +48,7 @@ public abstract class MemOpNode extends Node { Type ptr = ptr()._type; // Already an error, but better error messages come from elsewhere if( ptr == Type.BOTTOM ) return null; + if( ptr.isHigh() ) return null; // Assume it will fall to not-null // Better be a not-nil TMP if( ptr instanceof TypeMemPtr tmp && tmp.notNull() ) return null; diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java index 9aa123a5..b0b19311 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java @@ -341,7 +341,7 @@ public abstract class Node { // Replace constant computations from non-constants with a constant // node. If peeps are disabled, still allow high Phis to collapse; - // they typically come from dead Regions and we want the Region to + // they typically come from dead Regions, and we want the Region to // collapse, which requires the Phis to die first. if( _type.isHighOrConst() && !isConst() && (!_disablePeephole || _type.isHigh()) ) return ConstantNode.make(_type).peepholeOpt(); @@ -420,6 +420,7 @@ public abstract class Node { return old; } + public <N extends Node> N init() { _type = compute(); return (N)this; } /** * This function rewrites the current Node into a more "idealized" form. diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java index ccbdd460..35a60cd1 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -55,7 +55,7 @@ public class PhiNode extends Node { // During parsing Phis have to be computed type pessimistically. if( r.inProgress() ) return _declaredType; // Set type to local top of the starting type - Type t = Type.TOP; + Type t = _declaredType.glb().dual();//Type.TOP; for (int i = 1; i < nIns(); i++) // If the region's control input is live, add this as a dependency // to the control because we can be peeped should it become dead. diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java index f29ed20b..ebf650fc 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java @@ -45,7 +45,7 @@ public class ScopeMinNode extends Node { // If being used by a Scope, this is "in progress" from the Parser. - // Otherwise its a memory merge + // Otherwise, it's a memory merge boolean inProgress() { return _inProgress; } @Override public String label() { return "ALLMEM"; } @@ -60,7 +60,7 @@ public class ScopeMinNode extends Node { Node n = in(j); while( n instanceof ScopeNode loop ) { sb.append("Lazy_"); - n = loop.in(j); + n = loop.mem(j); } if( n==null ) sb.append("___ "); else n._print0(sb, visited).append(" "); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index e4a4ddc0..cf993561 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -288,7 +288,7 @@ public class ScopeNode extends ScopeMinNode { assert ctrl instanceof CFGNode; _guards.add(ctrl); // Marker to distinguish 0,1,2 guards // add pred & its cast to the normal input list, with special Vars - if( ctrl._type == Type.XCONTROL || pred==null || pred.isDead() ) + if( pred==null || pred.isDead() ) return; // Dead, do not add any guards // Invert the If conditional if( invert ) @@ -296,7 +296,8 @@ public class ScopeNode extends ScopeMinNode { // This is a zero/null test. // Compute the positive test type. Type tnz = pred._type.nonZero(); - _addGuard(tnz,ctrl,pred); + if( tnz!=null ) + _addGuard(tnz,ctrl,pred); // Compute the negative test type. if( pred instanceof NotNode not ) { @@ -308,7 +309,7 @@ public class ScopeNode extends ScopeMinNode { private void _addGuard(Type guard, Node ctrl, Node pred) { Type tcast = guard.join(pred._type); - if( tcast != pred._type ) { + if( tcast != pred._type && !tcast.isHigh() ) { Node cast = new CastNode(tcast,ctrl,pred.keep()).peephole().keep(); _guards.add(pred); _guards.add(cast); @@ -357,12 +358,11 @@ public class ScopeNode extends ScopeMinNode { } - private Node replace( Node old, Node cast ) { + private void replace( Node old, Node cast ) { assert old!=null && old!=cast; for( int i=0; i<nIns(); i++ ) if( in(i)==old ) setDef(i,cast); - return cast; } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/type/Field.java b/chapter18/src/main/java/com/seaofnodes/simple/type/Field.java index 1ed75fe4..ffa9d2a6 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/type/Field.java @@ -38,7 +38,8 @@ public class Field extends Type { @Override public boolean isFinal() { return _final && _type.isFinal(); } public static final Field TEST = make("test",Type.NIL,-2,false); - public static void gather(ArrayList<Type> ts) { ts.add(TEST); } + public static final Field TEST2= make("test",Type.NIL,-2,true); + public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(TEST2); } @Override Field xmeet( Type that ) { Field fld = (Field)that; // Invariant diff --git a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeFloat.java index df99b630..258cda03 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeFloat.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeFloat.java @@ -79,6 +79,7 @@ public class TypeFloat extends Type { return isConstant() ? this : make(-_sz,0); // Constants are a self-dual } + @Override public Type makeZero() { return FZERO; } @Override public Type glb() { return F64; } @Override @@ -86,7 +87,8 @@ public class TypeFloat extends Type { @Override public boolean eq( Type t ) { TypeFloat i = (TypeFloat)t; // Contract - return _con==i._con && _sz==i._sz; + // Allow NaN to check for equality + return _sz==i._sz && Double.doubleToLongBits(_con)==Double.doubleToLongBits(i._con); } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 77b280f3..cccb85a5 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -113,11 +113,12 @@ public class TypeInteger extends Type { @Override public TypeInteger nonZero() { if( isHigh() ) return this; + if( this==ZERO ) return null; // No sane answer if( _min==0 ) return make(1,Math.max(_max,1)); // specifically good on BOOL if( _max==0 ) return make(_min,-1); return this; } - @Override public Type makeZero() { return TypeInteger.ZERO; } + @Override public Type makeZero() { return ZERO; } @Override public TypeInteger glb() { return BOT; } @Override int hash() { return Utils.fold(_min) * Utils.fold(_max); } @Override public boolean eq( Type t ) { diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter04Test.java index 27d42c43..afed67d1 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -126,4 +126,10 @@ public class Chapter04Test { assertEquals("return (-arg);", code.print()); } + @Test + public void testBug5() { + Parser parser = new Parser("return arg--2;"); + StopNode ret = parser.parse(); + assertEquals("return (arg--2);", ret.print()); + } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter10Test.java index cdb9e923..02029b3f 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -299,8 +299,8 @@ if(0) { while(0) if(arg) continue; int v0=0; while(1) { - int arg=-arg; - v0=arg; + int v2=-arg; + v0=v2; } } """); diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java index c127d1cb..7063ef26 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -11,9 +11,9 @@ public class Chapter18Test { @Test public void testJig() { CodeGen code = new CodeGen(""" -return 0; + return 0; """); - code.parse().opto().typeCheck().GCM(); + code.parse(true).opto().typeCheck().GCM(); assertEquals("return 0;", code._stop.toString()); assertEquals("0", Eval2.eval(code, 0)); } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java b/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java index 580d3b0a..0e5e86a4 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java @@ -32,7 +32,7 @@ public abstract class Eval2 { // Evaluate until we return or timeout. Each outer loop step computes // all data nodes under some new Control. - SB sb = null; //new SB(); // TRACE + SB sb = null; // new SB(); // TRACE IdentityHashMap visit = new IdentityHashMap(); while( true ) { // Compute input path on Phis for this Region, @@ -49,8 +49,17 @@ public abstract class Eval2 { phiCache[i] = isArg(phi) ? arg : val(phi.in(path)); else break; // Parallel assign; might assign before read, so read from cache - for( int j=0; j < i; j++ ) - DATA[C.out(j)._nid] = phiCache[j]; + for( int j=0; j < i; j++ ) { + Node n = C.out(j); + DATA[n._nid] = phiCache[j]; + if( sb!=null ) { + IRPrinter.printLine(n,sb).unchar(); + _print( n._type, DATA[n._nid], sb.p('\t'), visit ); + System.out.println(sb); + sb.clear(); + visit.clear(); + } + } // Now compute the rest of the nodes for( ; i < C.nOuts(); i++ ) step(C.out(i), sb, visit); diff --git a/chapter18/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/chapter18/src/test/java/com/seaofnodes/simple/FuzzerWrap.java index eaeed8e2..d67b2065 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/FuzzerWrap.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/FuzzerWrap.java @@ -28,7 +28,7 @@ public class FuzzerWrap { Random R = new Random(System.currentTimeMillis()); var fuzzer = new Fuzzer(); for (int i=0; i<100; i++) - fuzzer.fuzzPeeps(R.nextLong()); + fuzzer.fuzzPeeps( R.nextLong()); assertTrue(fuzzer.noExceptions()); } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java b/chapter18/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java index 66395a74..a6bef4d3 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java @@ -1,10 +1,10 @@ package com.seaofnodes.simple.fuzzer; import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.Eval2; import com.seaofnodes.simple.CodeGen; import com.seaofnodes.simple.node.Node; -import com.seaofnodes.simple.node.StopNode; import java.util.ArrayList; import java.util.Objects; import java.util.Random; @@ -56,8 +56,7 @@ public class Fuzzer { private static boolean neq(Object a, Object b) { if (Objects.equals(a, b)) return false; - // Deep compare? - throw Utils.TODO(); + return true; } /** @@ -69,7 +68,7 @@ public class Fuzzer { private static void checkGraphs(CodeGen code1, CodeGen code2, long in) { var r1 = Eval2.eval(code1, in, EVAL_TIMEOUT); var r2 = Eval2.eval(code2, in, EVAL_TIMEOUT); - if( r1 == null || r2 == null ) return; + if( r1 == null || r2 == null ) return; // Timeout test invalid if( neq(r1, r2) ) throw new RuntimeException("Different calculations values " + r1 + " vs " + r2); } @@ -90,7 +89,7 @@ public class Fuzzer { FuzzerUtils.parse(script, true); } catch (RuntimeException e2) { if (FuzzerUtils.isExceptionFromSameCause(e1, e2)) { - if (!valid || e1.getClass() == RuntimeException.class) return; + if (!valid || e1.getClass() == Parser.ParserException.class) return; } else { e1.addSuppressed(e2); } |