diff options
24 files changed, 211 insertions, 155 deletions
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java b/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java index 79d817f8..394b6d1c 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java @@ -57,7 +57,10 @@ public class CodeGen { } public CodeGen typeCheck() { - assert _phase == Phase.Opto || _phase == Phase.Parse; + // Demand phase Opto for cleaning up dead control flow at least, + // required for the following GCM. Note that peeps can be disabled, + // but still the dead CFG will get cleaned. + assert _phase == Phase.Opto; _phase = Phase.TypeCheck; // Type check diff --git a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 6b0956ca..f1593a81 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -107,6 +107,8 @@ public abstract class GlobalCodeMotion { if( n instanceof LoadNode ld ) for( Node memuse : ld.mem()._outputs ) if( late[memuse._nid]==null && + // New makes new memory, never crushes load memory + !(memuse instanceof NewNode) && // Load-use directly defines memory (memuse._type instanceof TypeMem || // Load-use indirectly defines memory @@ -188,10 +190,6 @@ public abstract class GlobalCodeMotion { assert late[st._nid]!=null; lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st); break; - case NewNode st: - assert late[st._nid]!=null; - lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st); - break; case PhiNode phi: // Repeat anti-dep for matching Phi inputs. // No anti-dep edges but may raise the LCA. @@ -199,6 +197,7 @@ public abstract class GlobalCodeMotion { if( phi.in(i)==load.mem() ) lca = anti_dep(load,phi.region().cfg(i),load.mem().cfg0(),lca,null); break; + case NewNode st: break; case LoadNode ld: break; // Loads do not cause anti-deps on other loads case ReturnNode ret: break; // Load must already be ahead of Return case ScopeMinNode ret: break; // Mem uses now on ScopeMin diff --git a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java index ac497fe8..235d2414 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java @@ -226,7 +226,7 @@ public class Parser { } // Parse the body - Node last=null; + Node last=ZERO; while (!peek('}') && !_lexer.isEOF()) last = parseStatement(); @@ -562,6 +562,9 @@ public class Parser { RegionNode r = ctrl(tScope.mergeScopes(fScope)); Node ret = peep(new PhiNode("",lhs._type.meet(rhs._type),r,lhs.unkeep(),rhs.unkeep())); + // Immediately fail e.g. `arg ? 7 : ptr` + if( !stmt && ret.err() !=null ) + throw error(ret.err()); r.peephole(); return ret; } @@ -938,6 +941,8 @@ public class Parser { else if( match(">>") ) lhs = new SarNode(lhs,null); else break; lhs.setDef(2,parseAddition()); + if( lhs.err() != null ) + throw error(lhs.err()); lhs = peep(lhs.widen()); } return lhs; @@ -973,7 +978,7 @@ public class Parser { * @return a multiply expression {@link Node}, never {@code null} */ private Node parseMultiplication() { - var lhs = parseUnary(); boolean mul; + var lhs = parseUnary(); while( true ) { if( false ) ; else if( match("*") ) lhs = new MulNode(lhs,null); @@ -1004,7 +1009,9 @@ public class Parser { if( n != null ) { if( n._final ) throw error("Cannot reassign final '"+n._name+"'"); - Node expr = zsMask(peep(new AddNode(_scope.in(n),con(delta))),n.type()); + Node expr = n.type() instanceof TypeFloat + ? peep(new AddFNode(_scope.in(n),con(TypeFloat.constant(-1)))) + : zsMask(peep(new AddNode(_scope.in(n),con(delta))),n.type()); _scope.update(n,expr); return expr; } @@ -1054,7 +1061,7 @@ public class Parser { // Widen RHS int to a RHS float rhs = widenInt(rhs,n.type()); // Complain a RHS float into a LHS int - if( !rhs._type.isa(n.type()) ) + if( !(rhs._type instanceof TypeInteger) && !rhs._type.isa(n.type()) ) throw error("Type " + rhs._type.str() + " is not of declared type " + n.type().str()); Node op = switch(ch) { @@ -1124,7 +1131,7 @@ public class Parser { } // Check that all fields are initialized for( int i=idx; i<init.size(); i++ ) - if( /*init.at(i)._type == Type.TOP ||*/ init.at(i)._type == Type.BOTTOM ) + if( init.at(i)._type == Type.TOP || init.at(i)._type == Type.BOTTOM ) throw error("'"+tmp._obj._name+"' is not fully initialized, field '" + fs[i-idx]._fname + "' needs to be set in a constructor"); Node ptr = newStruct(tmp._obj, con(tmp._obj.offset(fs.length)), idx, init ); if( hasConstructor ) @@ -1196,9 +1203,11 @@ public class Parser { // Happens when parsing known dead code, which often has other typing // issues. Since the code is dead, possibly due to inlining, lets not // spoil the user experience with error messages. - if( ctrl()._type==Type.XCONTROL ) + if( ctrl()._type==Type.XCONTROL ) { + if( expr.isUnused() ) expr.kill(); // Losing last use of expr // Exit out via parsing the trailing expression - return matchOpx('=','=') ? parseAsgn() : parsePostfix(con(Type.TOP)); + return matchOpx( '=', '=' ) ? parseAsgn() : parsePostfix( con( Type.TOP ) ); + } // if( expr._type==Type.NIL ) diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/AndNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/AndNode.java index 68a8079d..7f080ff2 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/AndNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/AndNode.java @@ -5,21 +5,15 @@ import com.seaofnodes.simple.type.TypeInteger; import java.util.BitSet; -public class AndNode extends Node { - public AndNode(Node lhs, Node rhs) { super(null, lhs, rhs); } +public class AndNode extends LogicalNode { + public AndNode(Node lhs, Node rhs) { super(lhs, rhs); } @Override public String label() { return "And"; } + @Override public String op() { return "&"; } @Override public String glabel() { return "&"; } @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - in(1)._print0(sb.append("("), visited); - in(2)._print0(sb.append("&"), visited); - return sb.append(")"); - } - - @Override public Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; if( t1.isHigh() || t2.isHigh() ) @@ -60,9 +54,4 @@ public class AndNode extends Node { return null; } @Override Node copy(Node lhs, Node rhs) { return new AndNode(lhs,rhs); } - @Override public String err() { - if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '&' " + in(1)._type; - if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '&' " + in(2)._type; - return null; - } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/LogicalNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/LogicalNode.java new file mode 100644 index 00000000..7f959ff3 --- /dev/null +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/LogicalNode.java @@ -0,0 +1,25 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; +import java.util.BitSet; + +public abstract class LogicalNode extends Node { + public LogicalNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + abstract String op(); + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append(op()), visited); + return sb.append(")"); + } + + + @Override public String err() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return null; + if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+op()+"' " + in(1)._type; + if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+op()+"' " + in(2)._type; + return null; + } +} 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 3f2ae149..001ab8f2 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -43,7 +43,7 @@ public class LoopNode extends RegionNode { while( x != this ) { if( x instanceof CProjNode exit && exit.in(0) instanceof IfNode iff ) { CFGNode other = iff.cproj(1-exit._idx); - if( other.loopDepth() < loopDepth() ) + if( other!=null && other.loopDepth() < loopDepth() ) return stop; // Found an exit, not an infinite loop } x = x.idom(); @@ -57,18 +57,25 @@ public class LoopNode extends RegionNode { CProjNode f = new CProjNode(iff,1,"False"); setDef(2,f); - // Now fold control into the exit - ReturnNode ret = fun.ret(); - 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); + // 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(); - ctrl.addDef(t ); - mem .addDef(top); - expr.addDef(top); + 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(); + ctrl.addDef(t ); + mem .addDef(top); + expr.addDef(top); + } return stop; } } 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 cc7a1d13..9aa123a5 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java @@ -302,10 +302,6 @@ public abstract class Node { * Always returns some not-null Node (often this). */ public final Node peephole( ) { - if (_disablePeephole) { - _type = compute(); - return this; // Peephole optimizations turned off - } if( _type==null ) // Brand-new node, never peeped before JSViewer.show(); Node n = peepholeOpt(); @@ -337,8 +333,17 @@ public abstract class Node { // Compute initial or improved Type Type old = setType(compute()); - // Replace constant computations from non-constants with a constant node - if( _type.isHighOrConst() && !isConst() ) + // Peepholes can be turned off - except for cleaning up dead CFG paths. + // These need to clean up so the following code motion algorithms don't + // get confused by dead or infinite paths. + if( _disablePeephole && !(this instanceof RegionNode) && !(this instanceof PhiNode) ) + return old==_type ? null : this; // Peephole optimizations turned off + + // 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 + // collapse, which requires the Phis to die first. + if( _type.isHighOrConst() && !isConst() && (!_disablePeephole || _type.isHigh()) ) return ConstantNode.make(_type).peepholeOpt(); // Global Value Numbering diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/OrNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/OrNode.java index bd771198..42bedc46 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/OrNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/OrNode.java @@ -5,21 +5,15 @@ import com.seaofnodes.simple.type.TypeInteger; import java.util.BitSet; -public class OrNode extends Node { - public OrNode(Node lhs, Node rhs) { super(null, lhs, rhs); } +public class OrNode extends LogicalNode { + public OrNode(Node lhs, Node rhs) { super(lhs, rhs); } @Override public String label() { return "Or"; } + @Override public String op() { return "|"; } @Override public String glabel() { return "|"; } @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - in(1)._print0(sb.append("("), visited); - in(2)._print0(sb.append("|"), visited); - return sb.append(")"); - } - - @Override public Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; if( t1.isHigh() || t2.isHigh() ) @@ -57,9 +51,4 @@ public class OrNode extends Node { return null; } @Override Node copy(Node lhs, Node rhs) { return new OrNode(lhs,rhs); } - @Override public String err() { - if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '|' " + in(1)._type; - if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '|' " + in(2)._type; - return null; - } } 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 91334b6c..ccbdd460 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -1,9 +1,9 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Ary; +import com.seaofnodes.simple.SB; import com.seaofnodes.simple.Utils; -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeMem; -import com.seaofnodes.simple.type.TypeNil; +import com.seaofnodes.simple.type.*; import java.util.BitSet; public class PhiNode extends Node { @@ -75,13 +75,21 @@ public class PhiNode extends Node { Node live = singleUniqueInput(); if (live != null) return live; + // No more fancy peeps + if( _disablePeephole ) + return null; + + // No bother if region is going to fold dead paths soon + for( int i=1; i<nIns(); i++ ) + if( r.in(i)._type == Type.XCONTROL ) + return null; // Pull "down" a common data op. One less op in the world. One more // Phi, but Phis do not make code. // Phi(op(A,B),op(Q,R),op(X,Y)) becomes // op(Phi(A,Q,X), Phi(B,R,Y)). Node op = in(1); - if( op.nIns()==3 && op.in(0)==null && same_op() ) { + if( !isMem() && op.nIns()==3 && op.in(0)==null && same_op() ) { assert !(op instanceof CFGNode); Node[] lhss = new Node[nIns()]; Node[] rhss = new Node[nIns()]; @@ -171,4 +179,26 @@ public class PhiNode extends Node { @Override boolean eq( Node n ) { return !inProgress(); } + + @Override + public String err() { + if( _type != Type.BOTTOM ) return null; + + // BOTTOM means we mixed e.g. int and ptr + for( int i=1; i<nIns(); i++ ) + // Already an error, but better error messages come from elsewhere + if( in(i)._type == Type.BOTTOM ) + return null; + + // Gather a minimal set of types that "cover" all the rest + boolean ti=false, tf=false, tp=false, tn=false; + for( int i=1; i<nIns(); i++ ) { + Type t = in(i)._type; + ti |= t instanceof TypeInteger x; + tf |= t instanceof TypeFloat x; + tp |= t instanceof TypeMemPtr x; + tn |= t==Type.NIL; + } + return ReturnNode.mixerr(ti,tf,tp,tn); + } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 0f9fce7a..5b3d90fd 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -65,7 +65,8 @@ public class RegionNode extends CFGNode { return in(1); // Collapse if no Phis; 1-input Phis will collapse on their own // If a CFG diamond with no merging, delete: "if( pred ) {} else {};" - if( !hasPhi() && // No Phi users, just a control user + if( !_disablePeephole && + !hasPhi() && // No Phi users, just a control user in(1) instanceof CProjNode p1 && in(2) instanceof CProjNode p2 && p1.in(0).addDep(this)==p2.in(0).addDep(this) && diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 35563d6e..5232cfbb 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.CodeGen; +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.*; import java.util.BitSet; @@ -16,6 +17,7 @@ import java.util.BitSet; public class ReturnNode extends CFGNode { public final FunNode _fun; + public ReturnNode(Node ctrl, Node mem, Node data, FunNode fun) { super(ctrl, mem, data); _fun = fun; @@ -42,15 +44,40 @@ public class ReturnNode extends CFGNode { return TypeTuple.make(ctrl()._type,mem()._type,expr()._type); } - @Override public Node idealize() { return null; } + @Override public Node idealize() { + if( inProgress() ) return null; + // If dead (cant be reached; infinite loop), kill the exit values + if( ctrl()._type==Type.XCONTROL && + !(mem() instanceof ConstantNode && expr() instanceof ConstantNode) ) { + Node top = new ConstantNode(Type.TOP).peephole(); + setDef(1,top); + setDef(2,top); + return this; + } + return null; + } public boolean inProgress() { return ctrl().getClass() == RegionNode.class && ((RegionNode)ctrl()).inProgress(); } + // Gather parse-time return types for error reporting + private Type mt = Type.TOP; + private boolean ti=false, tf=false, tp=false, tn=false; + // Add a return exit to the current parsing function void addReturn(Node ctrl, Node rmem, Node expr) { assert inProgress(); + + // Gather parse-time return types for error reporting + Type t = expr._type; + mt = mt.meet(t); + ti |= t instanceof TypeInteger x; + tf |= t instanceof TypeFloat x; + tp |= t instanceof TypeMemPtr x; + tn |= t==Type.NIL; + + // Merge path into the One True Return RegionNode r = (RegionNode)ctrl(); // Assert that the Phis are in particular outputs; not reordered or shuffled PhiNode mem = (PhiNode)r.out(0); assert mem._declaredType == TypeMem.BOT; @@ -68,4 +95,17 @@ public class ReturnNode extends CFGNode { mem.addDef(null); rez.addDef(null); } + + @Override public String err() { + return mt==Type.BOTTOM ? mixerr(ti,tf,tp,tn) : null; + } + + static String mixerr( boolean ti, boolean tf, boolean tp, boolean tn ) { + SB sb = new SB().p("No common type amongst "); + if( ti ) sb.p("int and "); + if( tf ) sb.p("f64 and "); + if( tp ) sb.p("reference and "); + if( !tp && tn ) sb.p("nil and "); + return sb.unchar(5).toString(); + } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/SarNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/SarNode.java index a3d1045f..a3e2a562 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/SarNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/SarNode.java @@ -4,21 +4,15 @@ import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import java.util.BitSet; -public class SarNode extends Node { - public SarNode(Node lhs, Node rhs) { super(null, lhs, rhs); } +public class SarNode extends LogicalNode { + public SarNode(Node lhs, Node rhs) { super(lhs, rhs); } @Override public String label() { return "Sar"; } + @Override public String op() { return ">>"; } @Override public String glabel() { return ">>"; } @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - in(1)._print0(sb.append("("), visited); - in(2)._print0(sb.append(">>"), visited); - return sb.append(")"); - } - - @Override public Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; if( t1.isHigh() || t2.isHigh() ) @@ -52,9 +46,4 @@ public class SarNode extends Node { return null; } @Override Node copy(Node lhs, Node rhs) { return new SarNode(lhs,rhs); } - @Override public String err() { - if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '>>' " + in(1)._type; - if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '>>' " + in(2)._type; - return null; - } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ShlNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ShlNode.java index e454362a..24dff5e2 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ShlNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -5,21 +5,15 @@ import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import java.util.BitSet; -public class ShlNode extends Node { - public ShlNode(Node lhs, Node rhs) { super(null, lhs, rhs); } +public class ShlNode extends LogicalNode { + public ShlNode(Node lhs, Node rhs) { super(lhs, rhs); } @Override public String label() { return "Shl"; } + @Override public String op() { return "<<"; } @Override public String glabel() { return "<<"; } @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - in(1)._print0(sb.append("("), visited); - in(2)._print0(sb.append("<<"), visited); - return sb.append(")"); - } - - @Override public Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; if( t1.isHigh() || t2.isHigh() ) @@ -56,9 +50,4 @@ public class ShlNode extends Node { return null; } @Override Node copy(Node lhs, Node rhs) { return new ShlNode(lhs,rhs); } - @Override public String err() { - if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '<<' " + in(1)._type; - if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '<<' " + in(2)._type; - return null; - } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ShrNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ShrNode.java index 6f4a2c6c..52d2971d 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ShrNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -4,21 +4,15 @@ import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import java.util.BitSet; -public class ShrNode extends Node { - public ShrNode(Node lhs, Node rhs) { super(null, lhs, rhs); } +public class ShrNode extends LogicalNode { + public ShrNode(Node lhs, Node rhs) { super(lhs, rhs); } @Override public String label() { return "Shr"; } + @Override public String op() { return ">>>"; } @Override public String glabel() { return ">>>"; } @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - in(1)._print0(sb.append("("), visited); - in(2)._print0(sb.append(">>>"), visited); - return sb.append(")"); - } - - @Override public Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; if( t1.isHigh() || t2.isHigh() ) diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/XorNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/XorNode.java index c140ba83..a23e1304 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/XorNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/XorNode.java @@ -5,21 +5,15 @@ import com.seaofnodes.simple.type.TypeInteger; import java.util.BitSet; -public class XorNode extends Node { - public XorNode(Node lhs, Node rhs) { super(null, lhs, rhs); } +public class XorNode extends LogicalNode { + public XorNode(Node lhs, Node rhs) { super(lhs, rhs); } @Override public String label() { return "Xor"; } + @Override public String op() { return "^"; } @Override public String glabel() { return "^"; } @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - in(1)._print0(sb.append("("), visited); - in(2)._print0(sb.append("^"), visited); - return sb.append(")"); - } - - @Override public Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; if( t1.isHigh() || t2.isHigh() ) @@ -57,9 +51,4 @@ public class XorNode extends Node { return null; } @Override Node copy(Node lhs, Node rhs) { return new XorNode(lhs,rhs); } - @Override public String err() { - if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '^' " + in(1)._type; - if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '^' " + in(2)._type; - return null; - } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeMem.java index 60b3612f..9438abe2 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -44,6 +44,7 @@ public class TypeMem extends Type { return make(_alias,_t.dual()); } + @Override public boolean isHigh() { return _t.isHigh(); } @Override public Type glb() { return make(_alias,_t.glb()); } @Override int hash() { return 9876543 + _alias + _t.hashCode(); } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter02Test.java index 4254f0a6..324ebf41 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter02Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -12,7 +12,7 @@ public class Chapter02Test { public void testParseGrammar() { CodeGen code = new CodeGen("return 1+2*3+-5;"); code.parse(true); // Disable peepholes - assertEquals("return Phi(Region,((1+(2*3))+(-5)));", code.print()); + assertEquals("return ((1+(2*3))+(-5));", code.print()); } @Test diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter03Test.java index 2e45ee2a..a7fc3ae5 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -30,7 +30,7 @@ public class Chapter03Test { public void testVarScopeNoPeephole() { CodeGen code = new CodeGen("int a=1; int b=2; int !c=0; { int b=3; c=a+b; } return c; "); code.parse(true); - assertEquals("return Phi(Region,(1+3));", code.print()); + assertEquals("return (1+3);", code.print()); } @Test diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter09Test.java index 5b764013..b210f7e9 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -194,7 +194,7 @@ int v0=0!=0<-0; return -0+0+0; """); code.parse().opto(); - assertEquals("return 0;", code.print()); + assertEquals("return Top;", code.print()); } @@ -243,7 +243,7 @@ while(1) { return 0!=0; """); code.parse().opto(); - assertEquals("return 0;", code.print()); + assertEquals("return Top;", code.print()); } @Test diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter17Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter17Test.java index 4bcb9daa..5247f122 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter17Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter17Test.java @@ -353,6 +353,17 @@ return f; // missing widening assertEquals("1.2", Eval2.eval(code, 0)); } + + @Test + public void testTrinary6() { + CodeGen code = new CodeGen(""" +struct S{}; +return arg ? 7 : new S; +"""); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("No common type amongst int and reference",e.getMessage()); } + } + // --------------------------------------------------------------- @Test public void testFor0() { diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java b/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java index f7f58f32..77cbf115 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java @@ -115,6 +115,7 @@ public abstract class Eval2 { case MinusNode sub -> - x(sub.in(1)); case MulNode mul -> x(mul.in(1)) * x(mul.in(2)); case NewNode alloc -> alloc(alloc); + case NotNode not -> x(not.in(1)) == 0 ? 1L : 0L; case OrNode or -> x(or .in(1)) | x(or .in(2)); case ProjNode proj -> proj._type instanceof TypeMem ? "$mem" : val(proj.in(0)); case ReadOnlyNode read -> val(read.in(1)); 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 6f5307bc..66395a74 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java @@ -1,7 +1,8 @@ package com.seaofnodes.simple.fuzzer; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.Eval2; import com.seaofnodes.simple.CodeGen; -import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.StopNode; import java.util.ArrayList; @@ -55,18 +56,8 @@ public class Fuzzer { private static boolean neq(Object a, Object b) { if (Objects.equals(a, b)) return false; - if (a instanceof Evaluator.Obj ea && b instanceof Evaluator.Obj eb) { - if (ea.struct() != eb.struct()) return true; - for(int i=0;i<ea.fields().length;i++) { - if (neq(ea.fields()[i], eb.fields()[i])) return true; - } - return false; - } - if( a==null && b == Long.valueOf(0) ) - return false; - if( b==null && a == Long.valueOf(0) ) - return false; - return true; + // Deep compare? + throw Utils.TODO(); } /** @@ -75,11 +66,11 @@ public class Fuzzer { * @param e2 Evaluator for the second graph * @param in The input value to both graphs to test for an equal output */ - private static void checkGraphs(Evaluator e1, Evaluator e2, long in) { - var r1 = e1.evaluate(in, EVAL_TIMEOUT); - var r2 = e2.evaluate(in, EVAL_TIMEOUT); - if (r1 == Evaluator.Status.TIMEOUT || r2 == Evaluator.Status.TIMEOUT) return; - if (neq(r1, r2)) + 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( neq(r1, r2) ) throw new RuntimeException("Different calculations values " + r1 + " vs " + r2); } @@ -91,9 +82,9 @@ public class Fuzzer { * @param valid If the script is definitely valid. If not some exceptions may be suppressed. */ private static void runCheck(String script, boolean valid) { - StopNode stop1; + CodeGen code1; try { - stop1 = FuzzerUtils.parse(script, false); + code1 = FuzzerUtils.parse(script, false); } catch (RuntimeException e1) { try { FuzzerUtils.parse(script, true); @@ -106,12 +97,10 @@ public class Fuzzer { } throw e1; } - var stop2 = FuzzerUtils.parse(script, true); - var e1 = new Evaluator(stop1); - var e2 = new Evaluator(stop2); - checkGraphs(e1, e2, 0); - checkGraphs(e1, e2, 1); - checkGraphs(e1, e2, 10); + CodeGen code2 = FuzzerUtils.parse(script, true); + checkGraphs(code1, code2, 0); + checkGraphs(code1, code2, 1); + checkGraphs(code1, code2, 10); } /** diff --git a/chapter18/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java b/chapter18/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java index 81977522..62a149a8 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java @@ -114,7 +114,7 @@ class FuzzerUtils { /** * Parse script with peepholes enabled or disabled */ - public static StopNode parse(String script, boolean runPeeps) { + public static CodeGen parse(String script, boolean runPeeps) { var err = System.err; var out = System.out; try { @@ -126,12 +126,7 @@ class FuzzerUtils { throw rethrow(e); } var code = new CodeGen(script); - Node._disablePeephole = !runPeeps; - code.parse(); - if( runPeeps ) code.opto(); - code.typeCheck(); - if( runPeeps ) code.GCM(); // Fixup infinite loops - return code._stop; + return code.parse(!runPeeps).opto().typeCheck().GCM().localSched(); } finally { NodeWalkVisit.clear(); System.setErr(err); diff --git a/chapter18/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/chapter18/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java index d3cbb0ee..86dbe66a 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -483,7 +483,7 @@ public class ScriptGenerator { fields[i] = new TypeStruct.Field(fieldName.toString(), type, struct); } indentation -= INDENTATION; - printIndentation().append("}"); + printIndentation().append("};"); struct.fields = fields; forwardStructs.remove(struct); structs.add(struct); @@ -683,7 +683,8 @@ public class ScriptGenerator { public int genDecl() { var type = getType(); var name = getVarName(); - sb.append(generateInvalid() ? getRandomName() : type.name).append(" ").append(name); + // Always make them mutable + sb.append(generateInvalid() ? getRandomName() : type.name).append(" !").append(name); if (!(type instanceof TypeNullable) || random.nextBoolean()) { sb.append("="); genExpression(type, true); |