diff options
15 files changed, 163 insertions, 35 deletions
diff --git a/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index d2bbdc1e..35dc19ab 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -91,7 +91,7 @@ public abstract class GlobalCodeMotion { // a data-only loop, eventually attempting relying on some pre-visited- // not-post-visited data op with no scheduled control. for( Node def : n._inputs ) - if( def!=null ) + if( def!=null && !def.isPinned() ) _schedEarly(def,visit); // If not-pinned (e.g. constants, projections, phi) and not-CFG if( !n.isPinned() ) { @@ -103,6 +103,10 @@ public abstract class GlobalCodeMotion { early = n.in(i).cfg0(); // Latest/deepest input n.setDef(0,early); // First place this can go } + // Also the pinned inputs we skipped earlier + for( Node def : n._inputs ) + if( def!=null && def.isPinned() ) + _schedEarly(def,visit); } // ------------------------------------------------------------------------ diff --git a/chapter16/src/main/java/com/seaofnodes/simple/Parser.java b/chapter16/src/main/java/com/seaofnodes/simple/Parser.java index c77792de..626f7749 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/Parser.java @@ -524,7 +524,7 @@ public class Parser { } TypeStruct ts = s._ts = TypeStruct.make(typeName, fs); TYPES.put(typeName, TypeMemPtr.make(ts)); - INITS.put(typeName,(StructNode)s.peephole().keep()); + INITS.put(typeName,s.peephole().keep()); // Done with struct/block scope require("}"); require(";"); @@ -786,7 +786,6 @@ public class Parser { boolean hasConstructor = match("{"); Ary<Node> init=s._inputs; int idx=0; if( hasConstructor ) { - init = _scope._inputs; idx = _scope.nIns(); // Push a scope, and pre-assign all struct fields. _scope.push(); @@ -795,6 +794,7 @@ public class Parser { // Parse the constructor body parseBlock(); require("}"); + init = _scope._inputs; } // Check that all fields are initialized for( int i=idx; i<init.size(); i++ ) diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/AndNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/AndNode.java index 7e4b898b..17a4e0ca 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/AndNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/AndNode.java @@ -21,8 +21,11 @@ public class AndNode extends Node { @Override public Type compute() { - if( in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1 ) { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1.isHigh() || t2.isHigh() ) + return TypeInteger.TOP; + if( t1 instanceof TypeInteger i0 && + t2 instanceof TypeInteger i1 ) { if( i0.isConstant() && i1.isConstant() ) return TypeInteger.constant(i0.value()&i1.value()); // Sharpen allowed bits if either value is narrowed diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/CastNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/CastNode.java index fbf0e518..462d6cba 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/CastNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/CastNode.java @@ -21,8 +21,7 @@ public class CastNode extends Node { @Override public String uniqueName() { return "Cast_" + _nid; } - @Override - public boolean isPinned() { return true; } + @Override public boolean isPinned() { return true; } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/NotNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/NotNode.java index b3c77c45..ffd3e01e 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -22,7 +22,7 @@ public class NotNode extends Node { Type t0 = in(1)._type; if( t0.isHigh() ) return TypeInteger.BOOL.dual(); switch( t0 ) { - case TypeInteger i0: return i0._max < 0 || i0._min > 0 ? TypeInteger.FALSE : (i0==TypeInteger.ZERO ? TypeInteger.TRUE : TypeInteger.BOT); + case TypeInteger i0: return i0._max < 0 || i0._min > 0 ? TypeInteger.FALSE : (i0==TypeInteger.ZERO ? TypeInteger.TRUE : TypeInteger.BOOL); case TypeFloat i0: return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0; case TypeMemPtr p0: // top->top, bot->bot, null->1, *void->0, not-null ptr->0, ptr/nil->bot diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/OrNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/OrNode.java index 1b32d4fb..b572346f 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/OrNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/OrNode.java @@ -21,8 +21,11 @@ public class OrNode extends Node { @Override public Type compute() { - if( in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1 ) { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1.isHigh() || t2.isHigh() ) + return TypeInteger.TOP; + if( t1 instanceof TypeInteger i0 && + t2 instanceof TypeInteger i1 ) { if( i0.isConstant() && i1.isConstant() ) return TypeInteger.constant(i0.value()|i1.value()); } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 09a32c95..68f8cbe6 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -110,6 +110,7 @@ public class RegionNode extends CFGNode { return false; boolean progress = false; Node pred = iff.pred(); + if( pred._type.isConstant() ) return false; // This will collapse the IF already for( int i=1; i<n.nIns(); i++ ) { // Using a tested value if( n.in(i) == pred && !(n instanceof CastNode) ) { diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 388a2760..9f6ed6e3 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -151,7 +151,7 @@ public class ScopeNode extends ScopeMinNode { // Set real Phi in the loop head // The phi takes its one input (no backedge yet) from a recursive // lookup, which might have insert a Phi in every loop nest. - : loop.setDef(v._idx,new PhiNode(v._name, v._type, loop.ctrl(), loop.in(loop._update(v,null)._idx),null).peephole()); + : loop.setDef(v._idx,new PhiNode(v._name, v._type instanceof TypeMemPtr ? v._type : v._type.glb(), loop.ctrl(), loop.in(loop._update(v,null)._idx),null).peephole()); setDef(v._idx,old); } if( st!=null ) setDef(v._idx,st); // Set new value diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/XorNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/XorNode.java index 30a88dca..191933f9 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/XorNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/XorNode.java @@ -21,8 +21,11 @@ public class XorNode extends Node { @Override public Type compute() { - if( in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1 ) { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1.isHigh() || t2.isHigh() ) + return TypeInteger.TOP; + if( t1 instanceof TypeInteger i0 && + t2 instanceof TypeInteger i1 ) { if( i0.isConstant() && i1.isConstant() ) return TypeInteger.constant(i0.value()^i1.value()); } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter16/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 042b4ba8..b475055d 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -117,7 +117,7 @@ public class TypeInteger extends Type { @Override public TypeInteger makeInit() { return ZERO; } @Override public TypeInteger nonZero() { if( isHigh() ) return this; - if( _min==0 ) return make(1,_max); // specifically good on BOOL + if( _min==0 ) return make(1,Math.max(_max,1)); // specifically good on BOOL if( _max==0 ) return make(_min,-1); return this; } diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter11Test.java index a064e8e4..d6278b76 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -515,4 +515,22 @@ return v; StopNode stop = parser.parse().iterate(); //assertEquals("return new S;", stop.toString()); } + + @Test + public void testScheduleUse() { + Parser parser = new Parser( +""" +int v0=0; +while(0>=0) { + u1 v1=0; + v1=v0; + if(v1*0) + v0=-v1; +} +return 0; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + } + } diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter14Test.java index ea577c6b..7d7bb25a 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -166,6 +166,39 @@ return arg; } @Test + public void testCloneAnd() { + Parser parser = new Parser(""" +int v0=0; +u32 v1 = 1&(1<<arg)&(1<<arg); +while(arg) v1=-v0; +while(v1) break; +return v1; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return (Phi(Loop18,((1<<arg)&1),0)&Phi(Loop,Shl,4294967295));", stop.toString()); + assertEquals(1L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testAndHigh() { + Parser parser = new Parser(""" +int v0=0; +if(0&0>>>0) { + while(0) { + u8 v1=0; + v0=0>>>0; + v1=arg; + while(v1+0) {} + } +} +return v0; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 0)); + } + + @Test public void testTypes() { Parser parser = new Parser( """ diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 93a9c85c..55486124 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -325,4 +325,45 @@ return is[1]; catch( NegativeArraySizeException e ) { assertEquals("-1",e.getMessage()); } } + @Test + public void testProgress() { + Parser parser = new Parser(""" +i8 v1=0&0; +u8 v2=0; +byte v4=0; +if(0) {} +while(v2<0) { + v4=0-v1; + break; +} +int v5=0&0; +while(v5+(0&0)) { + int v7=0&0; + while(v7) + v4=0>>>v5; + while(v1) + return 0; +} +return v1; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testSharpNot() { + Parser parser = new Parser( +""" +if(0>>0) {} +while(0) {} +u32 v7=0; +int v8=0; +while(0<--1>>>---(v7*0==v8)) {} +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + } + + } diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter16Test.java index 6878a836..7cd1604b 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter16Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter16Test.java @@ -3,31 +3,15 @@ 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 java.awt.*; -import java.nio.charset.StandardCharsets; - import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; -/** - struct S { - int x; // default init of 0 - S? x; // default init of null - int !x; // final init required in constructor - S x; // init required in constructor - int !x=17; // final init done now, not in constructor - S x = ...;// init done now, not in constructor - }; - - */ - public class Chapter16Test { @Test public void testJig() { - Parser parser = new Parser(""" + Parser parser = new Parser( +""" return 3.14; """); StopNode stop = parser.parse().iterate(); @@ -35,6 +19,7 @@ return 3.14; assertEquals(3.14, Evaluator.evaluate(stop, 0)); } + @Test public void testMulti0() { Parser parser = new Parser( @@ -157,5 +142,35 @@ return next.i; assertEquals(2L, Evaluator.evaluate(stop, 3)); } + @Test + public void testLinkedList2() { + Parser parser = new Parser( +""" +struct LLI { LLI? next; int i; }; +LLI? head = null; +while( arg ) { + head = new LLI { + next=head; + // Any old code in the constructor + int tmp=arg; + while( arg > 10 ) { + tmp = tmp + arg; + arg = arg - 1; + } + i=tmp; + }; + arg = arg-1; +} +if( !head ) return 0; +LLI? next = head.next; +if( !next ) return 1; +return next.i; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ return 0; return 1; return .i; ]", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 0)); + assertEquals(1L, Evaluator.evaluate(stop, 1)); + assertEquals(2L, Evaluator.evaluate(stop, 11)); + } } diff --git a/chapter16/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/chapter16/src/test/java/com/seaofnodes/simple/FuzzerWrap.java index 699711fc..eaeed8e2 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/FuzzerWrap.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/FuzzerWrap.java @@ -1,10 +1,9 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.fuzzer.Fuzzer; -import org.junit.Test; +import java.util.Random; import org.junit.Ignore; - - +import org.junit.Test; import static org.junit.Assert.assertTrue; /** @@ -25,6 +24,15 @@ public class FuzzerWrap { @Test + public void fuzzPeepsSmall() { + Random R = new Random(System.currentTimeMillis()); + var fuzzer = new Fuzzer(); + for (int i=0; i<100; i++) + fuzzer.fuzzPeeps(R.nextLong()); + assertTrue(fuzzer.noExceptions()); + } + + @Test @Ignore public void fuzzPeepTiming() { var fuzzer = new Fuzzer(); |