diff options
| author | Cliff Click <cliffc@acm.org> | 2024-11-26 11:01:47 -0800 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2025-01-14 15:17:03 -0800 |
| commit | eee5b806fabae0b480ff7d41159369c5a457d014 (patch) | |
| tree | 576e6ed318eea76aa9e0de9e95af7616a0b8475a /src/main/java/com/seaofnodes/simple/node | |
| parent | c07510c1d75020d23d688f7f184149c57b13a39a (diff) | |
| download | Simple-linear-chapter18.tar.gz Simple-linear-chapter18.zip | |
Chapter 18: Functionslinear-chapter18
Diffstat (limited to 'src/main/java/com/seaofnodes/simple/node')
45 files changed, 1143 insertions, 411 deletions
diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 0834a381..e6704ea6 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -48,7 +48,7 @@ public class AddNode extends Node { // Add of 0. We do not check for (0+x) because this will already // canonicalize to (x+0) - if( t2 instanceof TypeInteger i && i.isConstant() && i.value()==0 ) + if( t2 == TypeInteger.ZERO ) return lhs; // Add of same to a multiply by 2 diff --git a/src/main/java/com/seaofnodes/simple/node/AndNode.java b/src/main/java/com/seaofnodes/simple/node/AndNode.java index 17a4e0ca..36e3a949 100644 --- a/src/main/java/com/seaofnodes/simple/node/AndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AndNode.java @@ -1,25 +1,20 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; 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(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, 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() ) @@ -59,10 +54,5 @@ public class AndNode extends Node { return null; } - @Override Node copy(Node lhs, Node rhs) { return new AndNode(lhs,rhs); } - @Override 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; - } + @Override Node copy(Node lhs, Node rhs) { return new AndNode(_loc,lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 238be00e..ae968ca1 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -2,10 +2,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.Utils; -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeInteger; -import com.seaofnodes.simple.type.TypeFloat; -import com.seaofnodes.simple.type.TypeMemPtr; +import com.seaofnodes.simple.type.*; import java.util.BitSet; import static com.seaofnodes.simple.type.TypeInteger.*; @@ -35,15 +32,19 @@ abstract public class BoolNode extends Node { public TypeInteger compute() { Type t1 = in(1)._type; Type t2 = in(2)._type; + // Exactly equals? if( t1.isHigh() || t2.isHigh() ) return BOOL.dual(); + if( in(1)==in(2) ) + // LT fails, both EQ and LE succeed + return this instanceof LT ? TypeInteger.FALSE : TypeInteger.TRUE; if( t1 instanceof TypeInteger i1 && t2 instanceof TypeInteger i2 ) return doOp(i1,i2); if( t1 instanceof TypeFloat f1 && t2 instanceof TypeFloat f2 && f1.isConstant() && f2.isConstant() ) - return TypeInteger.constant(doOp(f1.value(), f2.value()) ? 1 : 0); + return doOp(f1.value(), f2.value()) ? TypeInteger.TRUE : TypeInteger.FALSE; return BOOL; } @@ -55,7 +56,7 @@ abstract public class BoolNode extends Node { public Node idealize() { // Compare of same if( in(1)==in(2) ) - return new ConstantNode(doOp(ZERO,ZERO)); + return this instanceof LT ? Parser.ZERO : new ConstantNode(TypeInteger.TRUE); // Equals pushes constant to the right; 5==X becomes X==5. if( this instanceof EQ ) { @@ -66,7 +67,7 @@ abstract public class BoolNode extends Node { return in(1)._type instanceof TypeFloat ? new EQF(in(2),in(1)) : new EQ(in(2),in(1)); } // Equals X==0 becomes a !X - if( (in(2)._type == ZERO || in(2)._type == TypeMemPtr.NULLPTR) ) + if( (in(2)._type == ZERO || in(2)._type == Type.NIL) ) return new NotNode(in(1)); } @@ -93,6 +94,7 @@ abstract public class BoolNode extends Node { public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } + public String glabel() { return "<"; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( i1._max < i2._min ) return TRUE; if( i1._min >= i2._max ) return FALSE; @@ -104,6 +106,7 @@ abstract public class BoolNode extends Node { public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } + public String glabel() { return "<="; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( i1._max <= i2._min ) return TRUE; if( i1._min > i2._max ) return FALSE; diff --git a/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 052ad8fc..b051b3ce 100644 --- a/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -28,6 +28,17 @@ public abstract class CFGNode extends Node { // Block head is Start, Region, CProj, but not e.g. If, Return, Stop public boolean blockHead() { return false; } + // Get the one control following; error to call with more than one e.g. an + // IfNode or other multi-way branch. + public CFGNode uctrl() { + CFGNode c = null; + for( Node n : _outputs ) + if( n instanceof CFGNode cfg ) + { assert c==null; c = cfg; } + return c; + } + + // ------------------------------------------------------------------------ /** * Immediate dominator tree depth, used to approximate a real IDOM during @@ -82,21 +93,25 @@ public abstract class CFGNode extends Node { // Start is a LoopNode which contains all at depth 1. public void buildLoopTree(StopNode stop) { _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this); - _bltWalk(2,stop, new BitSet()); + _bltWalk(2,null,stop, new BitSet()); } - private int _bltWalk(int pre, StopNode stop, BitSet post) { + int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post ) { // Pre-walked? if( _pre!=0 ) return pre; _pre = pre++; // Pre-walk for( Node use : _outputs ) - if( use instanceof CFGNode usecfg ) - pre = usecfg._bltWalk(pre,stop,post); + if( use instanceof CFGNode usecfg && !skip(usecfg) ) + pre = usecfg._bltWalk(pre,use instanceof FunNode fuse ? fuse : fun,stop,post); // Post-order work: find innermost loop LoopTree inner = null, ltree; for( Node use : _outputs ) { if( !(use instanceof CFGNode usecfg) ) continue; + if( skip(usecfg) ) continue; + if( usecfg._type == Type.XCONTROL || // Do not walk dead control + usecfg._type == TypeTuple.IF_NEITHER ) // Nor dead IFs + continue; // Child visited but not post-visited? if( !post.get(usecfg._nid) ) { // Must be a backedge to a LoopNode then @@ -109,7 +124,7 @@ public abstract class CFGNode extends Node { if( ltree._par == null ) // This loop never had an If test choose to take its // exit, i.e. it is a no-exit infinite loop. - ltree._par = ltree._head.forceExit(stop)._ltree; + ltree._par = ltree._head.forceExit(fun,stop)._ltree; ltree = ltree._par; } } @@ -129,4 +144,13 @@ public abstract class CFGNode extends Node { post.set(_nid); return pre; } + + boolean skip(CFGNode usecfg) { + // Only walk control users that are alive. + // Do not walk from a Call to linked Fun's. + return usecfg instanceof XCtrlNode || + (this instanceof CallNode && usecfg instanceof FunNode) || + (this instanceof ReturnNode && usecfg instanceof CallEndNode); + } + } diff --git a/src/main/java/com/seaofnodes/simple/node/CProjNode.java b/src/main/java/com/seaofnodes/simple/node/CProjNode.java index d2f1bbe1..01119310 100644 --- a/src/main/java/com/seaofnodes/simple/node/CProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CProjNode.java @@ -6,7 +6,7 @@ import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.type.TypeTuple; import java.util.BitSet; -public class CProjNode extends CFGNode { +public class CProjNode extends CFGNode implements MultiUse { // Which slice of the incoming multipart value public final int _idx; @@ -21,6 +21,7 @@ public class CProjNode extends CFGNode { } @Override public String label() { return _label; } + @Override public int idx() { return _idx; } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(_label); } @@ -48,7 +49,8 @@ public class CProjNode extends CFGNode { if( ctrl() instanceof IfNode iff && iff.pred().addDep(this) instanceof NotNode not ) return new CProjNode(new IfNode(iff.ctrl(),not.in(1)).peephole(),1-_idx,_idx==0 ? "False" : "True"); - return null; + // Copy of some other input + return ((MultiNode)ctrl()).pcopy(_idx); } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java new file mode 100644 index 00000000..07a2b5a3 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -0,0 +1,92 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.type.*; +import java.util.BitSet; + +/** + * CallEnd + */ +public class CallEndNode extends CFGNode implements MultiNode { + + // When set true, this Call/CallEnd/Fun/Return is being trivially inlined + private boolean _folding; + + public CallEndNode(CallNode call) { super(call); } + + @Override + public String label() { return "CallEnd"; } + @Override public boolean isMultiHead() { return true; } + @Override public boolean blockHead() { return true; } + + CallNode call() { return (CallNode)in(0); } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + sb.append("cend( "); + sb.append( in(0) instanceof CallNode ? "Call, " : "----, "); + for( int i=1; i<nIns()-1; i++ ) + in(i)._print0(sb,visited).append(","); + sb.setLength(sb.length()-1); + return sb.append(")"); + } + + @Override + public Type compute() { + if( !(in(0) instanceof CallNode call) ) + return TypeTuple.RET.dual(); + Type ret = call.fptr().addDep(this)._type instanceof TypeFunPtr tfp ? tfp.ret() : Type.BOTTOM; + return TypeTuple.make(call._type,TypeMem.BOT,ret); + } + + @Override + public Node idealize() { + + // Trivial inlining: call site calls a single function; single function + // is only called by this call site. + if( !_folding && nIns()==2 ) { + CallNode call = call(); + Node fptr = call.fptr(); + if( fptr.nOuts() == 1 && // Only user is this call + fptr instanceof ConstantNode && // We have an immediate call + // Function is being called, and its not-null + fptr._type instanceof TypeFunPtr tfp && tfp.notNull() && + // Arguments are correct + call.err()==null ) { + ReturnNode ret = (ReturnNode)in(1); + FunNode fun = ret.fun(); + // Expecting Start, and the Call + if( fun.nIns()==3 ) { + assert fun.in(1) instanceof StartNode && fun.in(2)==call; + // Disallow self-recursive inlining (loop unrolling by another name) + CFGNode idom = call; + while( !(idom instanceof FunNode fun2) ) + idom = idom.idom(); + if( idom != fun ) { + // Trivial inline: rewrite + _folding = true; + // Rewrite Fun so the normal RegionNode ideal collapses + fun._folding = true; + fun.setDef(1,Parser.XCTRL); // No default/unknown StartNode caller + fun.setDef(2,call.ctrl()); // Bypass the Call; + fun.ret().setDef(3,null); // Return is folding also + IterPeeps.addAll(fun._outputs); + return this; + } + } else { + fun.addDep(this); + } + } else { // Function ptr has multiple users (so maybe multiple call sites) + fptr.addDep(this); + } + } + + return null; + } + + @Override public Node pcopy(int idx) { + return _folding ? in(1).in(idx) : null; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/CallNode.java b/src/main/java/com/seaofnodes/simple/node/CallNode.java new file mode 100644 index 00000000..246398ee --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -0,0 +1,142 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.CodeGen; +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFunPtr; +import java.util.BitSet; + +/** + * Call + */ +public class CallNode extends CFGNode { + + // Source location for late reported errors + public final Parser.Lexer _loc; + + public CallNode(Parser.Lexer loc, Node... nodes) { super(nodes); _loc = loc; } + + @Override + public String label() { return "Call"; } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + String fname = null; + Node fptr = fptr(); + if( fptr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) + fname = tfp._name; + if( fname==null ) fptr._print0(sb,visited); + else sb.append(fname); + sb.append("( "); + for( int i=2; i<nIns()-1; i++ ) + in(i)._print0(sb,visited).append(","); + sb.setLength(sb.length()-1); + return sb.append(")"); + } + + Node ctrl() { return in(0); } + Node mem () { return in(1); } + // Args mapped 1-to-1 on inputs, so conceptually start at 2 + Node arg(int idx) { return in(idx); } + // Same arg accounting as TFPs, although the numbering starts at 2 + int nargs() { return nIns()-3; } // Minus control, memory, fptr + // args from input 2 to last; last is function input + public Node fptr() { return _inputs.last(); } + + // Find the Call End from the Call + public CallEndNode cend() { + // Always in use slot 0 + if( nOuts()>0 && out(0) instanceof CallEndNode cend ) { + assert _cend()==cend; + return cend; + } else { + assert _cend()==null; + return null; + } + } + private CallEndNode _cend() { + CallEndNode cend=null; + for( Node n : _outputs ) + if( n instanceof CallEndNode cend0 ) + { assert cend == null; cend = cend0; } + return cend; + } + + // Get the one control following; error to call with more than one e.g. an + // IfNode or other multi-way branch. + @Override public CFGNode uctrl() { return cend(); } + + + @Override + public Type compute() { + return ctrl()._type; + } + + @Override + public Node idealize() { + CallEndNode cend = cend(); + if( cend==null ) return null; // Still building + + // Link: call calls target function. Linking makes the target FunNode + // point to this Call, and all his Parms point to the call arguments; + // also the CallEnd points to the Return. + if( fptr()._type instanceof TypeFunPtr tfp && tfp.nargs() == nargs() ) { + // If fidxs is negative, then infinite unknown functions + long fidxs = tfp.fidxs(); + if( fidxs > 0 ) { + // Wipe out the return which matching in the linker table + // Walk the (63 max) bits and link + for( ; fidxs!=0; fidxs = TypeFunPtr.nextFIDX(fidxs) ) { + int fidx = Long.numberOfTrailingZeros(fidxs); + TypeFunPtr tfp0 = tfp.makeFrom(fidx); + FunNode fun = CodeGen.CODE.link(tfp0); + if( fun!=null && !fun._folding && !linked(fun) ) + link(fun); + } + } + } + + return null; + } + + // True if Fun is linked to this Call + boolean linked( FunNode fun ) { + for( Node n : fun._inputs ) + if( n == this ) + return true; + return false; + } + + + // Link so this calls fun + private void link( FunNode fun ) { + assert !linked(fun); + fun.addDef(this); + for( Node use : fun._outputs ) + if( use instanceof ParmNode parm ) + parm.addDef(parm._idx==0 ? cend() : arg(parm._idx)); + // Call end points to function return + IterPeeps.add(cend()).addDef(fun.ret()); + assert linked(fun); + } + + @Override + public Parser.ParseException err() { + if( !(fptr()._type instanceof TypeFunPtr tfp) ) + throw Utils.TODO(); + if( !tfp.notNull() ) + return Parser.error( "Might be null calling "+tfp, _loc); + if( nargs() != tfp.nargs() ) + return Parser.error( "Expecting "+tfp.nargs()+" arguments, but found "+nargs(), _loc); + + // Check for args + for( int i=0; i<tfp.nargs(); i++ ) + if( !arg(i+2)._type.isa(tfp.arg(i)) ) + return Parser.error( "Argument #"+i+" isa "+arg(i+2)._type+", but must be a "+tfp.arg(i), _loc); + + return null; + } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/CastNode.java b/src/main/java/com/seaofnodes/simple/node/CastNode.java index 462d6cba..d8a968c1 100644 --- a/src/main/java/com/seaofnodes/simple/node/CastNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CastNode.java @@ -1,9 +1,9 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; -import com.seaofnodes.simple.IterPeeps; - import java.util.BitSet; // Upcast (join) the input to a t. Used after guard test to lift an input. @@ -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,21 @@ 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(); } + + @Override + public Parser.ParseException err() { + // Has a condition to test, so OK + if( in(0) != null ) return null; + // No condition to test, so this must optimize away + throw Utils.TODO(); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 845b9d08..e03bfb0e 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.SB; import com.seaofnodes.simple.type.Type; import java.util.BitSet; @@ -18,24 +19,31 @@ import java.util.BitSet; * The Constant's value is the value stored in it. */ public class ConstantNode extends Node { - Type _con; + public final Type _con; public ConstantNode( Type type ) { super(Parser.START); _con = type; } - @Override - public String label() { return "#"+_con; } + public static Node make( Type type ) { + if( type==Type. CONTROL ) return new CtrlNode(); + if( type==Type.XCONTROL ) return new XCtrlNode(); + return new ConstantNode(type); + } + + @Override public String label() { return "#"+_con; } + @Override public String glabel() { return _con.gprint(new SB().p("#")).toString(); } @Override public String uniqueName() { return "Con_" + _nid; } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { - return _con.print(sb); + return sb.append(_con.print(new SB())); } @Override public boolean isMultiTail() { return true; } + @Override public boolean isConst() { return true; } @Override public Type compute() { return _con; } diff --git a/src/main/java/com/seaofnodes/simple/node/CtrlNode.java b/src/main/java/com/seaofnodes/simple/node/CtrlNode.java new file mode 100644 index 00000000..162417bb --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/CtrlNode.java @@ -0,0 +1,14 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.Type; +import java.util.BitSet; + +public class CtrlNode extends CFGNode { + public CtrlNode() { super(Parser.START); } + @Override public String label() { return "Ctrl"; } + @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append("Cctrl"); } + @Override public boolean isConst() { return true; } + @Override public Type compute() { return Type.CONTROL; } + @Override public Node idealize() { return null; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java index 76e98678..0d5ed297 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -2,7 +2,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; - import java.util.BitSet; public class DivNode extends Node { diff --git a/src/main/java/com/seaofnodes/simple/node/FRefNode.java b/src/main/java/com/seaofnodes/simple/node/FRefNode.java new file mode 100644 index 00000000..f0c4045d --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/FRefNode.java @@ -0,0 +1,35 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Var; +import com.seaofnodes.simple.type.Type; +import java.util.BitSet; + +/** + * A Forward Reference. Its any final constant, including functions. When + * the Def finally appears its plugged into the forward reference, which then + * peepholes to the Def. + */ +public class FRefNode extends ConstantNode { + public static final Type FREF_TYPE = Type.BOTTOM; + public final Var _n; + public FRefNode( Var n ) { super(FREF_TYPE); _n = n; } + + @Override public String label() { return "FRef"+_n; } + + @Override public String uniqueName() { return "FRef_" + _nid; } + + @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { + return sb.append("FRef_").append(_n); + } + + @Override public Node idealize() { + // When FRef finds its definition, idealize to it + return nIns()==1 ? null : in(1); + } + + public Parser.ParseException err() { return Parser.error("Undefined name '"+_n._name+"'",_n._loc); } + + @Override boolean eq(Node n) { return this==n; } + @Override int hash() { return _n._idx; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/FunNode.java b/src/main/java/com/seaofnodes/simple/node/FunNode.java new file mode 100644 index 00000000..1f0c76eb --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -0,0 +1,133 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFunPtr; +import java.util.BitSet; + +public class FunNode extends RegionNode { + + // When set true, this Call/CallEnd/Fun/Return is being trivially inlined + boolean _folding; + + private TypeFunPtr _sig; // Initial signature + private ReturnNode _ret; // Return pointer + + public FunNode( Parser.Lexer loc, StartNode start, TypeFunPtr sig ) { super(loc,null,start); _sig=sig; } + + @Override + public String label() { return _sig._name == null ? "$fun" : _sig._name; } + + // Find the one CFG user from Fun. It's not always the Return, but always + // the Return *is* a CFG user of Fun. + @Override public CFGNode uctrl() { + for( Node n : _outputs ) + if( n instanceof CFGNode cfg && + (cfg instanceof RegionNode || cfg.cfg0()==this) ) + return cfg; + return null; + } + + public ParmNode rpc() { + ParmNode rpc = null; + for( Node n : _outputs ) + if( n instanceof ParmNode parm && parm._idx==0 ) + { assert rpc==null; rpc=parm; } + return rpc; + } + + // Cannot create the Return and Fun at the same time; one has to be first. + // So setting the return requires a second step. + public void setRet(ReturnNode ret) { _ret=ret; } + ReturnNode ret() { assert _ret!=null; return _ret; } + + // Signature can improve over time + public TypeFunPtr sig() { return _sig; } + void setSig( TypeFunPtr sig ) { + assert sig.isa(_sig); + if( _sig != sig ) + IterPeeps.add(this); + _sig = sig; + } + + @Override + public Type compute() { + // Only dead if no callers after SCCP + return Type.CONTROL; + } + + @Override + public Node idealize() { + // When can we assume no callers? Or no other callers (except main)? + // In a partial compilation, we assume Start gets access to any/all + // top-level public structures and recursively what they point to. + // This in turn is valid arguments to every callable function. + // + // In a total compilation, we can start from Start and keep things + // more contained. + + + // If no default/unknown caller, use the normal RegionNode ideal rules + // to collapse + if( unknownCallers() ) return null; + Node progress = super.idealize(); + if( progress!=null ) { + IterPeeps.add( CodeGen.CODE._stop); + IterPeeps.add( _ret ); + } + return progress; + } + + // Bypass Region idom, always assume depth == 1, one more than Start + @Override public int idepth() { return (_idepth=1); } + // Bypass Region idom, always assume idom is Start + @Override public CFGNode idom(Node dep) { return cfg(1); } + + // Always in-progress until we run out of unknown callers + public boolean unknownCallers() { return in(1) instanceof StartNode; } + + @Override public boolean inProgress() { return unknownCallers(); } + + // Add a new function exit point. + public void addReturn(Node ctrl, Node mem, Node rez) { _ret.addReturn(ctrl,mem,rez); } + + // Build the function body + public BitSet body() { + + // Reverse up (stop to start) CFG only, collect bitmap. + BitSet cfgs = new BitSet(); + cfgs.set(_nid); + walkUp(ret(),cfgs ); + + // Top down (start to stop) all flavors. CFG limit to bitmap. + // If data use bottoms out in wrong CFG, returns false - but tries all outputs. + // If any output hits an in-CFG use (e.g. phi), then keep node. + BitSet body = new BitSet(); + walkDown(this, cfgs, body, new BitSet()); + return body; + } + + private static void walkUp(CFGNode n, BitSet cfgs) { + if( cfgs.get(n._nid) ) return; + cfgs.set(n._nid); + if( n instanceof RegionNode r ) + for( int i=1; i<n.nIns(); i++ ) + walkUp(n.cfg(i),cfgs); + else walkUp(n.cfg0(),cfgs); + } + + private static boolean walkDown( Node n, BitSet cfgs, BitSet body, BitSet visit ) { + if( visit.get(n._nid) ) return body.get(n._nid); + visit.set(n._nid); + + if( n instanceof CFGNode && !cfgs.get(n._nid) ) + return false; + if( n.in(0)!=null && !cfgs.get(n.in(0)._nid) ) + return false; + boolean in = n.in(0)!=null || n instanceof CFGNode; + for( Node use : n._outputs ) + in |= walkDown(use,cfgs,body,visit); + if( in ) body.set(n._nid); + return in; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 513b4721..eafcdf5b 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -1,9 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.IterPeeps; -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeInteger; -import com.seaofnodes.simple.type.TypeTuple; +import com.seaofnodes.simple.type.*; import java.util.BitSet; import java.util.HashSet; @@ -28,23 +26,27 @@ public class IfNode extends CFGNode implements MultiNode { public Node ctrl() { return in(0); } public Node pred() { return in(1); } + // No one unique control follows + @Override public CFGNode uctrl() { return null; } + @Override public Type compute() { // If the If node is not reachable then neither is any following Proj if (ctrl()._type != Type.CONTROL && ctrl()._type != Type.BOTTOM ) return TypeTuple.IF_NEITHER; + if( _disablePeephole ) return TypeTuple.IF_BOTH; Node pred = pred(); Type t = pred._type; // High types mean NEITHER side is reachable. // Wait until the type falls to decide which way to go. - if( t == Type.TOP || t == TypeInteger.TOP ) + if( t.isHigh() ) return TypeTuple.IF_NEITHER; // If constant is 0 then false branch is reachable // Else true branch is reachable if( t.isConstant() ) - return t.makeInit()==t ? TypeTuple.IF_FALSE : TypeTuple.IF_TRUE; - // Integers allow non-zero ranges: "1-65535" - if( t.makeZero().meet(t) != t ) + return (t==Type.NIL || t==TypeInteger.ZERO || (t instanceof TypeFunPtr tfp && tfp._fidxs==0) ) ? TypeTuple.IF_FALSE : TypeTuple.IF_TRUE; + // If adding a zero makes a difference, the predicate must not have a zero/null + if( !t.makeZero().isa(t) ) return TypeTuple.IF_TRUE; return TypeTuple.IF_BOTH; @@ -57,7 +59,7 @@ public class IfNode extends CFGNode implements MultiNode { if( !pred()._type.isHighOrConst() ) for( CFGNode dom = idom(), prior=this; dom!=null; prior = dom, dom = dom.idom() ) if( dom.addDep(this) instanceof IfNode iff && iff.pred().addDep(this)==pred() && prior instanceof CProjNode prj ) { - setDef(1,new ConstantNode(TypeInteger.make(true,prj._idx==0?1:0)).peephole()); + setDef(1,new ConstantNode(TypeInteger.constant(prj._idx==0?1:0)).peephole()); return this; } return null; diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 1528f2e9..eee5169d 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.*; import java.util.BitSet; @@ -19,8 +19,8 @@ public class LoadNode extends MemOpNode { * @param ptr The ptr to the struct base from where we load a field * @param off The offset inside the struct base */ - public LoadNode(String name, int alias, Type glb, Node mem, Node ptr, Node off) { - super(name, alias, glb, mem, ptr, off); + public LoadNode(Parser.Lexer loc, String name, int alias, Type glb, Node mem, Node ptr, Node off) { + super(loc, name, alias, glb, mem, ptr, off); } // GraphVis DOT code (must be valid Java identifiers) and debugger labels @@ -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,19 +79,27 @@ 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 ) { + case ProjNode mproj: // Memory projection + switch( mproj.in(0) ) { + case NewNode nnn1: if( ptr instanceof ProjNode pproj && pproj.in(0) == mproj.in(0) ) return castRO(nnn1.in(nnn1.findAlias(_alias))); // Load from New init if( !(ptr instanceof ProjNode pproj && pproj.in(0) instanceof NewNode nnn2) ) break outer; // Cannot tell, ptr not related to New mem = nnn1.in(_alias);// Bypass unrelated New break; - } else if( mproj.in(0) instanceof StartNode ) { - break outer; - } else throw Utils.TODO(); + case StartNode start: break outer; + case CallEndNode cend: break outer; // TODO: Bypass no-alias call + default: throw Utils.TODO(); + } + break; + case MemMergeNode merge: mem = merge.alias(_alias); break; + default: throw Utils.TODO(); } @@ -125,7 +133,7 @@ public class LoadNode extends MemOpNode { private Node ld( int idx ) { Node mem = mem(), ptr = ptr(); - return new LoadNode(_name,_alias,_declaredType,mem.in(idx),ptr instanceof PhiNode && ptr.in(0)==mem.in(0) ? ptr.in(idx) : ptr, off()).peephole(); + return new LoadNode(_loc,_name,_alias,_declaredType,mem.in(idx),ptr instanceof PhiNode && ptr.in(0)==mem.in(0) ? ptr.in(idx) : ptr, off()).peephole(); } private static boolean neverAlias( Node ptr1, Node ptr2 ) { @@ -158,8 +166,9 @@ public class LoadNode extends MemOpNode { private boolean profit(PhiNode phi, int idx) { Node px = phi.in(idx); if( px==null ) return false; - if( px._type instanceof TypeMem mem && mem._t.isHighOrConst() ) { px.addDep(this); return true; } - if( px instanceof StoreNode st1 && ptr()==st1.ptr() && off()==st1.off() ) { px.addDep(this); return true; } + if( px._type instanceof TypeMem mem && mem._t.isHighOrConst() ) return true; + if( px instanceof StoreNode st1 && ptr()==st1.ptr() && off()==st1.off() ) return true; + px.addDep(this); return false; } diff --git a/src/main/java/com/seaofnodes/simple/node/LogicalNode.java b/src/main/java/com/seaofnodes/simple/node/LogicalNode.java new file mode 100644 index 00000000..ccc1f6b5 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/LogicalNode.java @@ -0,0 +1,29 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; +import java.util.BitSet; + +public abstract class LogicalNode extends Node { + // Source location for late reported errors + Parser.Lexer _loc; + + public LogicalNode(Parser.Lexer loc, Node lhs, Node rhs) { super(null, lhs, rhs); _loc = loc; } + 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 Parser.ParseException err() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return null; + if( !(in(1)._type instanceof TypeInteger) ) return Parser.error("Cannot '"+op()+"' " + in(1)._type.glb(),_loc); + if( !(in(2)._type instanceof TypeInteger) ) return Parser.error("Cannot '"+op()+"' " + in(2)._type.glb(), _loc); + return null; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java index ecda9c63..f70a1012 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -3,12 +3,13 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.type.TypeInteger; import java.util.BitSet; import java.util.HashSet; public class LoopNode extends RegionNode { - public LoopNode( Node entry ) { super(null,entry,null); } + public LoopNode( Parser.Lexer loc, Node entry ) { super(loc,null,entry,null); } public CFGNode entry() { return cfg(1); } public CFGNode back () { return cfg(2); } @@ -22,11 +23,6 @@ public class LoopNode extends RegionNode { return entry()._type; } - @Override - public Node idealize() { - return inProgress() ? null : super.idealize(); - } - // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) @Override public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) @@ -34,7 +30,7 @@ public class LoopNode extends RegionNode { // If this is an unreachable loop, it may not have an exit. If it does not // (i.e., infinite loop), force an exit to make it reachable. - public StopNode forceExit( StopNode stop ) { + public StopNode forceExit( FunNode fun, StopNode stop ) { // Walk the backedge, then immediate dominator tree util we hit this // Loop again. If we ever hit a CProj from an If (as opposed to // directly on the If) we found our exit. @@ -42,7 +38,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(); @@ -50,12 +46,40 @@ public class LoopNode extends RegionNode { // Found a no-exit loop. Insert an exit NeverNode iff = new NeverNode(back()); for( Node use : _outputs ) - if( use instanceof PhiNode phi ) + 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); - stop.addDef(new ReturnNode(t,Parser.ZERO,null)); + + // 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(); + 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(_loc,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/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index 9134f9c3..8a08853c 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -2,58 +2,44 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.Var; import com.seaofnodes.simple.type.*; import java.util.*; - import static com.seaofnodes.simple.Utils.TODO; -/* */ -public class ScopeMinNode extends Node { +/** + * Memory Merge - a merge of many aliases into a "fat memory". All aliases + * are here, but most will be lazy - take the default fat memory. + */ +public class MemMergeNode extends Node { - /** The tracked fields are now complex enough to deserve a array-of-structs layout + /* + * In-Progress means this is being used by the Parser to track memory + * aliases. No optimizations are allowed. When no longer "in progress" + * normal peeps work. */ - public static class Var { - public final int _idx; // index in containing scope - public final String _name; // Declared name - private Type _type; // Declared type - public final boolean _final; // Final field - public Var(int idx, String name, Type type, boolean xfinal) { - _idx = idx; - _name = name; - _type = type; - _final = xfinal; - } - public Type type() { - if( !_type.isFRef() ) return _type; - // Update self to no longer use the forward ref type - Type def = Parser.TYPES.get(((TypeMemPtr)_type)._obj._name); - return (_type=_type.meet(def)); - } - public Type lazyGLB() { - Type t = type(); - return t instanceof TypeMemPtr ? t : t.glb(); - } - @Override public String toString() { - return _type.toString()+(_final ? " ": " !")+_name; - } - } + public final boolean _inProgress; + + public MemMergeNode( boolean inProgress) { _type = TypeMem.BOT; _inProgress = inProgress; } - public ScopeMinNode() { _type = TypeMem.BOT; } + // If being used by a Scope, this is "in progress" from the Parser. + // Otherwise, it's a memory merge + boolean inProgress() { return _inProgress; } - @Override public String label() { return "MEM"; } + @Override public String label() { return "ALLMEM"; } + @Override public boolean isMem() { return true; } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { - sb.append("MEM[ "); + sb.append(_inProgress ? "Merge[" : "MEM[ "); for( int j=2; j<nIns(); j++ ) { sb.append(j); sb.append(":"); 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(" "); @@ -62,14 +48,33 @@ public class ScopeMinNode extends Node { return sb.append("]"); } + // Make a memory merge: no longer a Scope really, tracking memory state but + // not related to the parser in any way. + public Node merge() { + // Force default memory to not be lazy + MemMergeNode merge = new MemMergeNode(false); + for( Node n : _inputs ) + merge.addDef(n); + merge._mem(1,null); + return merge.peephole(); + } + @Override public Type compute() { return TypeMem.BOT; } - @Override public Node idealize() { return null; } + @Override public Node idealize() { + if( inProgress() ) return null; + + // If not merging any memory (all memory is just the default) + if( nIns()==2 ) + return in(1); // Become default memory + + return null; + } public Node in( Var v ) { return in(v._idx); } - Node alias( int alias ) { + public Node alias( int alias ) { return in(alias<nIns() && in(alias)!=null ? alias : 1); } @@ -78,7 +83,6 @@ public class ScopeMinNode extends Node { return setDef(alias,st); } - // Read or update from memory. // A shared implementation allows us to create lazy phis both during // lookups and updates; the lazy phi creation is part of chapter 8. @@ -87,7 +91,7 @@ public class ScopeMinNode extends Node { // then it must be START.proj(1) Node old = alias(alias); if( old instanceof ScopeNode loop ) { - ScopeMinNode loopmem = loop.mem(); + MemMergeNode loopmem = loop.mem(); Node memdef = loopmem.alias(alias); // Lazy phi! old = memdef instanceof PhiNode phi && loop.ctrl()==phi.region() @@ -104,28 +108,27 @@ public class ScopeMinNode extends Node { } - void _merge(ScopeMinNode that, RegionNode r) { + void _merge( MemMergeNode that, RegionNode r) { int len = Math.max(nIns(),that.nIns()); for( int i = 2; i < len; i++) if( alias(i) != that.alias(i) ) { // No need for redundant Phis // If we are in lazy phi mode we need to a lookup - // by name as it will trigger a phi creation - //Var v = _vars.at(i); + // by alias as it will trigger a phi creation Node lhs = this._mem(i,null); Node rhs = that._mem(i,null); - alias(i, new PhiNode(Parser.memName(i), TypeMem.BOT, r, lhs, rhs).peephole()); + alias(i, new PhiNode(Parser.memName(i), lhs._type.glb().meet(rhs._type.glb()), r, lhs, rhs).peephole()); } } // Fill in the backedge of any inserted Phis - void _endLoopMem( ScopeNode scope, ScopeMinNode back, ScopeMinNode exit ) { - for( int i=2; i<back.nIns(); i++ ) { - if( back.in(i) != scope ) { - PhiNode phi = (PhiNode)in(i); - assert phi.region()==scope.ctrl() && phi.in(2)==null; - phi.setDef(2,back.in(i)); // Fill backedge + void _endLoopMem( ScopeNode scope, MemMergeNode back, MemMergeNode exit ) { + Node exit_def = exit.alias(1); + for( int i=1; i<nIns(); i++ ) { + if( in(i) instanceof PhiNode phi && phi.region()==scope.ctrl() ) { + assert phi.in(2)==null; + phi.setDef(2,back.in(i)==scope ? phi : back.in(i)); // Fill backedge } - if( exit.alias(i) == scope ) // Replace a lazy-phi on the exit path also + if( exit_def == scope ) // Replace a lazy-phi on the exit path also exit.alias(i,in(i)); } } @@ -147,4 +150,7 @@ public class ScopeMinNode extends Node { } } + @Override boolean eq( Node n ) { + return this==n || !_inProgress; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 82aab8ac..f9df2a40 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMemPtr; @@ -13,15 +15,18 @@ public abstract class MemOpNode extends Node { // Declared type; not final because it might be a forward-reference // which will be lazily improved when the reference is declared. public Type _declaredType; + // Source location for late reported errors + public final Parser.Lexer _loc; - public MemOpNode(String name, int alias, Type glb, Node mem, Node ptr, Node off) { + public MemOpNode(Parser.Lexer loc, String name, int alias, Type glb, Node mem, Node ptr, Node off) { super(null, mem, ptr, off); _name = name; _alias = alias; _declaredType = glb; + _loc = loc; } - public MemOpNode(String name, int alias, Type glb, Node mem, Node ptr, Node off, Node value) { - this(name, alias, glb, mem, ptr, off); + public MemOpNode(Parser.Lexer loc, String name, int alias, Type glb, Node mem, Node ptr, Node off, Node value) { + this(loc,name, alias, glb, mem, ptr, off); addDef(value); } @@ -43,13 +48,14 @@ public abstract class MemOpNode extends Node { int hash() { return _alias; } @Override - String err() { + public Parser.ParseException err() { 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._nil ) + if( ptr instanceof TypeMemPtr tmp && tmp.notNull() ) return null; - return "Might be null accessing '" + _name + "'"; + return Parser.error( "Might be null accessing '" + _name + "'",_loc); } } diff --git a/src/main/java/com/seaofnodes/simple/node/MinusFNode.java b/src/main/java/com/seaofnodes/simple/node/MinusFNode.java index 9727f58b..2b749ba3 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusFNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusFNode.java @@ -22,7 +22,7 @@ public class MinusFNode extends Node { public Type compute() { if (in(1)._type instanceof TypeFloat i0) return i0.isConstant() ? TypeFloat.constant(-i0.value()) : i0; - return TypeFloat.BOT; + return TypeFloat.F64; } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 760a4274..dd2cbd26 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -21,13 +21,11 @@ public class MinusNode extends Node { @Override public Type compute() { - if( in(1)._type instanceof TypeInteger i0 ) { - if( i0.isHigh() ) return TypeInteger.TOP; - if( i0==TypeInteger.BOT || i0._min == Long.MIN_VALUE || i0._max == Long.MIN_VALUE ) - return TypeInteger.BOT; + if( in(1)._type.isHigh() ) return TypeInteger.TOP; + if( in(1)._type instanceof TypeInteger i0 && + !(i0==TypeInteger.BOT || i0._min == Long.MIN_VALUE || i0._max == Long.MIN_VALUE) ) return TypeInteger.make(-i0._max,-i0._min); - } - return TypeInteger.TOP.meet(in(1)._type); + return TypeInteger.BOT; } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/src/main/java/com/seaofnodes/simple/node/MultiNode.java index ac9c0045..17d00881 100644 --- a/src/main/java/com/seaofnodes/simple/node/MultiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MultiNode.java @@ -1,6 +1,11 @@ package com.seaofnodes.simple.node; -public interface MultiNode extends OutNode { +import com.seaofnodes.simple.Ary; + + +public interface MultiNode { + + abstract Ary<Node> outs(); // Find a projection by index default ProjNode proj( int idx ) { @@ -17,4 +22,8 @@ public interface MultiNode extends OutNode { return prj; return null; } + + // Return not-null if this projection index is a ideal copy. + // Called by ProjNode ideal and used to collapse Multis. + default Node pcopy(int idx) { return null; } } diff --git a/src/main/java/com/seaofnodes/simple/node/MultiUse.java b/src/main/java/com/seaofnodes/simple/node/MultiUse.java new file mode 100644 index 00000000..436d3432 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/MultiUse.java @@ -0,0 +1,5 @@ +package com.seaofnodes.simple.node; + +public interface MultiUse { + abstract int idx(); +} diff --git a/src/main/java/com/seaofnodes/simple/node/NewNode.java b/src/main/java/com/seaofnodes/simple/node/NewNode.java index ddb1e09a..34d695f4 100644 --- a/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -17,15 +17,16 @@ public class NewNode extends Node implements MultiNode { public NewNode(TypeMemPtr ptr, Node... nodes) { super(nodes); + assert !ptr.nullable(); _ptr = ptr; _len = ptr._obj._fields.length; // Control in slot 0 assert nodes[0]._type==Type.CONTROL || nodes[0]._type == Type.XCONTROL; // Malloc-length in slot 1 - assert nodes[1]._type instanceof TypeInteger; + assert nodes[1]._type instanceof TypeInteger || nodes[1]._type==Type.NIL; for( int i=0; i<_len; i++ ) { // Memory slices for all fields. - assert nodes[2+ i]._type instanceof TypeMem; + assert nodes[2+ i]._type.isa(TypeMem.BOT); // Value slices for all fields. assert nodes[2 + _len + i]._type != null; } @@ -57,7 +58,8 @@ public class NewNode extends Node implements MultiNode { ts[0] = Type.CONTROL; ts[1] = _ptr; for( int i=0; i<fs.length; i++ ) { - TypeMem mem = (TypeMem)in(i+2)._type; + Type mt = in(i+2)._type; + TypeMem mem = mt==Type.TOP ? TypeMem.TOP : (TypeMem)mt; Type tfld = in(2+_len+i)._type.meet(mem._t); ts[i+2] = TypeMem.make(fs[i]._alias,tfld); } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 3827fdac..4c6cce16 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -1,9 +1,6 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Ary; -import com.seaofnodes.simple.IRPrinter; -import com.seaofnodes.simple.IterPeeps; -import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.*; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeFloat; import java.util.*; @@ -14,7 +11,7 @@ import java.util.function.Function; * The Node class provides common functionality used by all subtypes. * Subtypes of Node specialize by overriding methods. */ -public abstract class Node implements OutNode { +public abstract class Node { /** * Each node has a unique dense Node ID within a compilation context @@ -93,8 +90,9 @@ public abstract class Node implements OutNode { @Override public final String toString() { return print(); } - // This is a *deep* print. We print with a tik-tok style; the common - // _print0 calls the per-Node _print1, which calls back to _print0; + // This is a *deep* print. We print with a mutually recursive tik-tok + // style; the common _print0 calls the per-Node _print1, which calls back + // to _print0; public final String print() { return _print0(new StringBuilder(), new BitSet()).toString(); } @@ -116,6 +114,7 @@ public abstract class Node implements OutNode { public boolean isMultiHead() { return false; } public boolean isMultiTail() { return false; } + public boolean isConst () { return false; } // ------------------------------------------------------------------------ // Graph Node & Edge manipulation @@ -127,7 +126,7 @@ public abstract class Node implements OutNode { */ public Node in(int i) { return _inputs.get(i); } public Node out(int i) { return _outputs.get(i); } - @Override public Ary<Node> outs() { return _outputs; } + public final Ary<Node> outs() { return _outputs; } public int nIns() { return _inputs.size(); } @@ -164,9 +163,11 @@ public abstract class Node implements OutNode { new_def.addUse(this); // Set the new_def over the old (killed) edge _inputs.set(idx,new_def); - if( old_def != null && // If the old def exists, remove a def->use edge - old_def.delUse(this) ) // If we removed the last use, the old def is now dead - old_def.kill(); // Kill old def + if( old_def != null ) { // If the old def exists, remove a def->use edge + if( old_def.delUse(this) ) // If we removed the last use, the old def is now dead + old_def.kill(); // Kill old def + else IterPeeps.add(old_def);// Else old lost a use, so onto worklist + } moveDepsToWorklist(); // Return new_def for easy flow-coding return new_def; @@ -301,12 +302,12 @@ public abstract class Node implements OutNode { * 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(); - return n==null ? this : deadCodeElim(n.peephole()); // Cannot return null for no-progress + if( n!=null ) // Made progress? + JSViewer.show(); // Show again + return n==null ? this : deadCodeElim(n._nid >= _nid ? n.peephole() : n); // Cannot return null for no-progress } /** @@ -332,9 +333,18 @@ public abstract class Node implements OutNode { // Compute initial or improved Type Type old = setType(compute()); - // Replace constant computations from non-constants with a constant node - if( !(this instanceof ConstantNode) && !(this instanceof XCtrlNode) && _type.isHighOrConst() ) - return (_type==Type.XCONTROL ? new XCtrlNode() : new ConstantNode(_type)).peepholeOpt(); + // 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 if( _hash==0 ) { @@ -357,8 +367,9 @@ public abstract class Node implements OutNode { if( n != null ) // Something changed return n; // Report progress - if( old==_type ) ITER_NOP_CNT++; - return old==_type ? null : this; // Report progress + if( old!=_type ) return this; // Report progress; + ITER_NOP_CNT++; + return null; // No progress } public static int ITER_CNT, ITER_NOP_CNT; @@ -409,6 +420,7 @@ public abstract class Node implements OutNode { return old; } + public <N extends Node> N init() { _type = compute(); return (N)this; } /** * This function rewrites the current Node into a more "idealized" form. @@ -577,9 +589,7 @@ public abstract class Node implements OutNode { // Swap inputs without letting either input go dead during the swap. Node swap12() { unlock(); // Hash is order dependent - Node tmp = in(1); - _inputs.set(1,in(2)); - _inputs.set(2,tmp); + _inputs.swap(1,2); return this; } @@ -606,7 +616,7 @@ public abstract class Node implements OutNode { Node copy(Node lhs, Node rhs) { throw Utils.TODO("Binary ops need to implement copy"); } // Report any post-optimize errors - String err() { return null; } + public Parser.ParseException err() { return null; } /** * Used to allow repeating tests in the same JVM. This just resets the diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java index 664d7c7b..b454de66 100644 --- a/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -18,25 +18,13 @@ public class NotNode extends Node { } @Override - public Type compute() { + public TypeInteger compute() { 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.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 - // If input in null then true - // If input is not null ptr then false - if( p0 == TypeMemPtr.NULLPTR ) return TypeInteger.TRUE; - if( !p0._nil ) return TypeInteger.FALSE; - return TypeInteger.BOOL; - case Type t: - if( t0.getClass() != Type.class ) - // Only doing NOT on ints and ptrs - throw Utils.TODO(); - return TypeInteger.BOOL; - } + if( t0.isHigh() ) return TypeInteger.BOOL.dual(); + if( t0 == Type.NIL || t0 == TypeInteger.ZERO ) return TypeInteger.TRUE; + if( t0 instanceof TypeNil tn && tn.notNull() ) return TypeInteger.FALSE; + if( t0 instanceof TypeInteger i && (i._min > 0 || i._max < 0) ) return TypeInteger.FALSE; + return TypeInteger.BOOL; } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/OrNode.java b/src/main/java/com/seaofnodes/simple/node/OrNode.java index b572346f..9b03dc5d 100644 --- a/src/main/java/com/seaofnodes/simple/node/OrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/OrNode.java @@ -1,25 +1,20 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; 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(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, 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() ) @@ -56,10 +51,5 @@ public class OrNode extends Node { return null; } - @Override Node copy(Node lhs, Node rhs) { return new OrNode(lhs,rhs); } - @Override 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; - } + @Override Node copy(Node lhs, Node rhs) { return new OrNode(_loc,lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/node/OutNode.java b/src/main/java/com/seaofnodes/simple/node/OutNode.java deleted file mode 100644 index dbac136b..00000000 --- a/src/main/java/com/seaofnodes/simple/node/OutNode.java +++ /dev/null @@ -1,7 +0,0 @@ -package com.seaofnodes.simple.node; - -import com.seaofnodes.simple.Ary; - -public interface OutNode { - Ary<Node> outs(); -} diff --git a/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/src/main/java/com/seaofnodes/simple/node/ParmNode.java new file mode 100644 index 00000000..784b9146 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -0,0 +1,47 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.type.Type; +import java.util.BitSet; + +public class ParmNode extends PhiNode { + + // Argument indices are mapped one-to-one on CallNode inputs + public final int _idx; // Argument index + + public ParmNode(String label, int idx, Type declaredType, Node... inputs) { + super(label,declaredType,inputs); + _idx = idx; + } + + @Override public String label() { return MemOpNode.mlabel(_label); } + + @Override public String glabel() { return _label; } + + public FunNode fun() { return (FunNode)in(0); } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + if( "main".equals(fun().sig()._name) && _label.equals("arg") ) + return sb.append("arg"); + sb.append("Parm_").append(_label).append("("); + for( Node in : _inputs ) { + if (in == null) sb.append("____"); + else in._print0(sb, visited); + sb.append(","); + } + sb.setLength(sb.length()-1); + sb.append(")"); + return sb; + } + + + @Override + public Node idealize() { + if( inProgress() ) return null; + return super.idealize(); + } + + // Always in-progress until we run out of unknown callers + @Override public boolean inProgress() { return fun().inProgress(); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index cb266ca3..9aed8287 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -1,14 +1,12 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeMem; -import com.seaofnodes.simple.Utils; - +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.type.*; import java.util.BitSet; public class PhiNode extends Node { - final String _label; + public final String _label; // The Phi type we compute must stay within the domain of the Phi. // Example Int stays Int, Ptr stays Ptr, Control stays Control, Mem stays Mem. @@ -16,6 +14,14 @@ public class PhiNode extends Node { public PhiNode(String label, Type declaredType, Node... inputs) { super(inputs); _label = label; assert declaredType!=null; _declaredType = declaredType; } + public PhiNode(RegionNode r, Node sample) { + super(r); + _label = ""; + _declaredType = sample._type; + while( nIns() < r.nIns() ) + addDef(sample); + } + @Override public String label() { return "Phi_"+MemOpNode.mlabel(_label); } @Override public String glabel() { return "φ_"+_label; } @@ -47,7 +53,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 = _declaredType.lub(); + 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. @@ -67,13 +73,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()]; @@ -84,7 +98,11 @@ public class PhiNode extends Node { } Node phi_lhs = new PhiNode(_label, _declaredType,lhss).peephole(); Node phi_rhs = new PhiNode(_label, _declaredType,rhss).peephole(); - return op.copy(phi_lhs,phi_rhs); + Node down = op.copy(phi_lhs,phi_rhs); + // Test not running backwards, which can happen for e.g. And's + if( down.compute().isa(compute()) ) + return down; + down.kill(); } // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. @@ -97,14 +115,16 @@ public class PhiNode extends Node { // then replace with plain val. if( nIns()==3 ) { int nullx = -1; - if( in(1)._type == in(1)._type.makeInit() ) nullx = 1; - if( in(2)._type == in(2)._type.makeInit() ) nullx = 2; + if( in(1)._type == in(1)._type.makeZero() ) nullx = 1; + if( in(2)._type == in(2)._type.makeZero() ) nullx = 2; if( nullx != -1 ) { Node val = in(3-nullx); + if( val instanceof CastNode cast ) + val = cast.in(1); 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(); + while( idom != null && idom.nIns() > 0 && idom.in(0) != iff ) idom = idom.idom(); if( idom instanceof CProjNode proj && proj._idx==1 ) return val; } @@ -149,7 +169,7 @@ public class PhiNode extends Node { } // True if last input is null - public final boolean inProgress() { + public boolean inProgress() { return in(nIns()-1) == null; } @@ -157,4 +177,26 @@ public class PhiNode extends Node { @Override boolean eq( Node n ) { return !inProgress(); } + + @Override + public Parser.ParseException 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, ((RegionNode)region())._loc); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 73c1fa15..ea211dd2 100644 --- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -6,7 +6,7 @@ import com.seaofnodes.simple.type.TypeTuple; import java.util.BitSet; -public class ProjNode extends Node { +public class ProjNode extends Node implements MultiUse { // Which slice of the incoming multipart value public final int _idx; @@ -21,11 +21,19 @@ public class ProjNode extends Node { } @Override public String label() { return _label; } + @Override public int idx() { return _idx; } @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(_label); } + StringBuilder _print1(StringBuilder sb, BitSet visited) { + if( _label != null ) return sb.append(_label); + if( in(0) instanceof CallEndNode cend && cend.call()!=null ) + return cend.call()._print0(sb,visited); + return sb.append("LONELY PROJ"); + } - @Override public CFGNode cfg0() { return in(0).cfg0(); } + @Override public CFGNode cfg0() { + return in(0) instanceof CFGNode cfg ? cfg : in(0).cfg0(); + } @Override public boolean isMultiTail() { return in(0).isMultiHead(); } @Override public boolean isMem() { return _type instanceof TypeMem; } @@ -37,7 +45,7 @@ public class ProjNode extends Node { return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; } - @Override public Node idealize() { return null; } + @Override public Node idealize() { return ((MultiNode)in(0)).pcopy(_idx); } @Override boolean eq( Node n ) { return _idx == ((ProjNode)n)._idx; } diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index fb39af17..ea053c02 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -10,8 +10,11 @@ import java.util.BitSet; import java.util.HashSet; public class RegionNode extends CFGNode { + // Source location for late discovered errors + public Parser.Lexer _loc; - public RegionNode(Node... nodes) { super(nodes); } + public RegionNode(Node... nodes) { this(null,nodes); } + public RegionNode(Parser.Lexer loc, Node... nodes) { super(nodes); _loc = loc; } @Override public String label() { return "Region"; } @@ -65,12 +68,18 @@ 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 && // Optional + !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) && - p1.in(0) instanceof IfNode iff ) - return iff.ctrl(); + p1.in(0) instanceof IfNode iff ) { + // Replace with the iff.ctrl directly + if( nIns()==3 ) return iff.ctrl(); + // Just delete the path for fat Regions + setDef(1,iff.ctrl()); + return delDef(2); + } return null; } @@ -82,7 +91,7 @@ public class RegionNode extends CFGNode { return 0; // All inputs alive } - private boolean hasPhi() { + boolean hasPhi() { for( Node phi : _outputs ) if( phi instanceof PhiNode ) return true; @@ -109,12 +118,9 @@ public class RegionNode extends CFGNode { } // True if last input is null - public final boolean inProgress() { - return nIns()>1 && in(nIns()-1) == null; - } + public boolean inProgress() { return nIns()>1 && in(nIns()-1) == null; } // Never equal if inProgress - @Override boolean eq( Node n ) { - return !inProgress(); - } + @Override boolean eq( Node n ) { return !inProgress(); } + } diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index b586a44f..e543f9ea 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -1,7 +1,9 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.*; - import java.util.BitSet; /** @@ -15,16 +17,18 @@ import java.util.BitSet; */ public class ReturnNode extends CFGNode { - public ReturnNode(Node ctrl, Node data, ScopeNode scope) { - // Add memory slices to Return, so all memory updates are live-on-exit. - super(ctrl, data); - if( scope!=null ) - for( int i=2; i<scope.mem().nIns(); i++ ) - addDef(scope.mem().in(i)); + public final FunNode _fun; + + public ReturnNode(Node ctrl, Node mem, Node data, Node rpc, FunNode fun ) { + super(ctrl, mem, data, rpc); + _fun = fun; } public Node ctrl() { return in(0); } - public Node expr() { return in(1); } + public Node mem () { return in(1); } + public Node expr() { return in(2); } + public Node rpc () { return in(3); } + public FunNode fun() { return _fun; } @Override public String label() { return "Return"; } @@ -36,15 +40,89 @@ public class ReturnNode extends CFGNode { return sb.append(";"); } + // No one unique control follows; can be many call end sites + @Override public CFGNode uctrl() { return null; } + @Override public Type compute() { - return TypeTuple.make(ctrl()._type,expr()._type); + if( inProgress () ) return TypeTuple.RET; // In progress + if( _fun.isDead() ) return TypeTuple.RET.dual(); // Dead another way + return TypeTuple.make(ctrl()._type,mem()._type,expr()._type); } - @Override - public Node idealize() { - if( ctrl()._type==Type.XCONTROL ) - return ctrl(); + @Override public Node idealize() { + if( inProgress () ) return null; + if( _fun.isDead() ) return null; + + // Upgrade signature based on return type + Type ret = expr()._type; + TypeFunPtr fcn = _fun.sig(); + assert ret.isa(fcn.ret()); + if( ret != fcn.ret() ) + _fun.setSig(fcn.makeFrom(ret)); + + // 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; + PhiNode rez = (PhiNode)r.out(1); assert rez._declaredType == Type.BOTTOM; + // Pop "inProgress" null off + r ._inputs.pop(); + mem._inputs.pop(); + rez._inputs.pop(); + // Add new return point + r .addDef(ctrl); + mem.addDef(rmem); + rez.addDef(expr); + // Back to being inProgress + r .addDef(null); + mem.addDef(null); + rez.addDef(null); + } + + @Override public Parser.ParseException err() { + return mt==Type.BOTTOM ? mixerr(ti,tf,tp,tn,_fun._loc) : null; + } + + static Parser.ParseException mixerr( boolean ti, boolean tf, boolean tp, boolean tn, Parser.Lexer loc ) { + if( !ti && !tf && !tp && !tn ) + return Parser.error("No defined return type", loc); + SB sb = new SB().p("No common type amongst "); + if( ti ) sb.p("int and "); + if( tf ) sb.p("f64 and "); + if( tp || tn ) sb.p("reference and "); + return Parser.error(sb.unchar(5).toString(),loc); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/SarNode.java b/src/main/java/com/seaofnodes/simple/node/SarNode.java index 5dc26ad3..4a71ec06 100644 --- a/src/main/java/com/seaofnodes/simple/node/SarNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SarNode.java @@ -1,23 +1,17 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; 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(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, 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 String glabel() { return ">>"; } @Override public Type compute() { @@ -52,10 +46,5 @@ public class SarNode extends Node { return null; } - @Override Node copy(Node lhs, Node rhs) { return new SarNode(lhs,rhs); } - @Override 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; - } + @Override Node copy(Node lhs, Node rhs) { return new SarNode(_loc,lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 86aa7665..d0d86b79 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,17 +1,14 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.IterPeeps; -import com.seaofnodes.simple.Ary; +import com.seaofnodes.simple.*; import com.seaofnodes.simple.type.*; import java.util.*; -import static com.seaofnodes.simple.Utils.TODO; - /** * The Scope node is purely a parser helper - it tracks names to nodes with a - * stack of hashmaps. + * stack of variables. */ -public class ScopeNode extends ScopeMinNode { +public class ScopeNode extends MemMergeNode { /** * The control is a name that binds to the currently active control @@ -24,20 +21,22 @@ public class ScopeNode extends ScopeMinNode { // All active/live variables in all nested scopes, all run together public final Ary<Var> _vars; - // Since of each nested lexical scope + // Size of each nested lexical scope public final Ary<Integer> _lexSize; - // True if parsing inside of a constructor - public final Ary<Boolean> _inCons; + // Lexical scope is one of normal Block, constructor or function + public enum Kind { Block, Constructor, Function }; + public final Ary<Kind> _kinds; // Extra guards; tested predicates and casted results private final Ary<Node> _guards; // A new ScopeNode public ScopeNode() { + super(true); _vars = new Ary<>(Var .class); _lexSize= new Ary<>(Integer.class); - _inCons = new Ary<>(Boolean.class); + _kinds = new Ary<>(Kind .class); _guards = new Ary<>(Node .class); } @@ -50,7 +49,7 @@ public class ScopeNode extends ScopeMinNode { for( int i=0; i<nIns(); i++ ) { if( j < _lexSize._len && i == _lexSize.at(j) ) { sb.append("| "); j++; } Var v = _vars.get(i); - v.type().print(sb); + sb.append(v.type().print(new SB())); sb.append(" "); if( v._final ) sb.append("!"); sb.append(v._name); @@ -70,7 +69,7 @@ public class ScopeNode extends ScopeMinNode { public Node ctrl() { return in(0); } - public ScopeMinNode mem() { return (ScopeMinNode)in(1); } + public MemMergeNode mem() { return (MemMergeNode)in(1); } /** * The ctrl of a ScopeNode is always bound to the currently active @@ -83,29 +82,60 @@ public class ScopeNode extends ScopeMinNode { * @return Node that was bound */ public <N extends Node> N ctrl(N n) { return setDef(0,n); } + public Node mem(Node n) { return setDef(1,n); } - public void push() { push(false); } - public void push(boolean inCon) { - assert _lexSize._len==_inCons._len; + public void push(Kind kind) { + assert _lexSize._len==_kinds._len; _lexSize.push(_vars.size()); - _inCons.push(inCon); + _kinds .push(kind); } + + // Pop a lexical scope public void pop() { - assert _lexSize._len==_inCons._len; + assert _lexSize._len==_kinds._len; + promote(); int n = _lexSize.pop(); - _inCons.pop(); + _kinds.pop(); popUntil(n); _vars.setLen(n); } - public boolean inCon() { return _inCons.last(); } + + // Look for forward references in the last lexical scope and promote to the + // next outer lexical scope. At the last scope declare them an error. + public void promote() { + int n = _lexSize.last(); + for( int i=n; i<nIns(); i++ ) { + Var v = _vars.at(i); + if( !v.isFRef() ) continue; + if( _lexSize._len==1 ) + throw Parser.error("Undefined name '" + v._name + "'",v._loc); + _vars.swap(n,i); + _inputs.swap(n,i); + v._idx = n; + n++; + _lexSize.set(_lexSize._len-1,n); + } + } + + + public boolean inCon() { return _kinds.last() == Kind.Constructor; } + + // Is v outside any current function scope? + public boolean outOfFunction( Var v ) { + for( int i=_lexSize._len-1; i>=0 && v._idx<_lexSize.at(i); i-- ) + if( _kinds.at(i)==Kind.Function ) + return true; + return false; + } + // Find name in reverse, return an index into _vars or -1. Linear scan // instead of hashtable, but probably doesn't matter until the scan // typically hits many dozens of variables. int find( String name ) { for( int i=_vars.size()-1; i>=0; i-- ) - if( _vars.get(i)._name.equals(name) ) + if( _vars.at(i)._name.equals(name) ) return i; return -1; } @@ -113,13 +143,24 @@ public class ScopeNode extends ScopeMinNode { /** * Create a new variable name in the current scope */ - public boolean define( String name, Type declaredType, boolean xfinal, Node init ) { - assert name.charAt(0)!='$' || _lexSize.size()==1; // Later scopes do not define memory - if( _lexSize._len > 1 ) - for( int i=_vars.size()-1; i>=_lexSize.last(); i-- ) - if( _vars.get(i)._name.equals(name) ) - return false; // Double define - _vars.add(new Var(nIns(),name,declaredType,xfinal)); + public boolean define( String name, Type declaredType, boolean xfinal, Node init, Parser.Lexer loc ) { + assert _lexSize.isEmpty() || name.charAt(0)!='$' ; // Later scopes do not define memory + if( _lexSize._len > 0 ) + for( int i=_vars.size()-1; i>=_lexSize.last(); i-- ) { + Var n = _vars.at(i); + if( n._name.equals(name) ) { + if( !n.isFRef() ) return false; // Double define + FRefNode fref = (FRefNode)in(n._idx); // Get forward ref + if( !xfinal || !declaredType.isConstant() ) throw fref.err(); // Must be a final constant + n.defFRef(declaredType,xfinal,loc); // Declare full correct type, final, source location + setDef(n._idx,fref.addDef(init)); // Set FRef to defined; tell parser also + } + } + Var v = new Var(nIns(),name,declaredType,xfinal,loc,init==Parser.XCTRL); + _vars.add(v); + // Creating a forward reference + if( init==Parser.XCTRL ) + init = new FRefNode(v).init(); addDef(init); return true; } @@ -154,7 +195,7 @@ public class ScopeNode extends ScopeMinNode { update(_vars.at(idx),n); } - public Var update( ScopeNode.Var v, Node st ) { + public Var update( Var v, Node st ) { Node old = in(v._idx); if( old instanceof ScopeNode loop ) { // Lazy Phi! @@ -168,6 +209,7 @@ public class ScopeNode extends ScopeMinNode { : loop.setDef(v._idx,new PhiNode(v._name, v.lazyGLB(), loop.ctrl(), loop.in(loop.update(v,null)._idx),null).peephole()); setDef(v._idx,old); } + assert !v._final || st==null; if( st!=null ) setDef(v._idx,st); // Set new value return v; } @@ -194,7 +236,7 @@ public class ScopeNode extends ScopeMinNode { // 3) Ensure that the order of defs is the same to allow easy merging dup._vars .addAll(_vars ); dup._lexSize.addAll(_lexSize); - dup._inCons .addAll(_inCons ); + dup._kinds .addAll(_kinds ); dup._guards .addAll(_guards ); // The dup'd guards all need dup'd keepers, to keep proper accounting // when later removing all guards @@ -204,7 +246,7 @@ public class ScopeNode extends ScopeMinNode { dup.addDef(ctrl()); // Control input is just copied // Memory input is a shallow copy - ScopeMinNode memdup = new ScopeMinNode(), mem = mem(); + MemMergeNode memdup = new MemMergeNode(true), mem = mem(); memdup.addDef(null); memdup.addDef(loop ? this : mem.in(1)); for( int i=2; i<mem.nIns(); i++ ) @@ -217,7 +259,7 @@ public class ScopeNode extends ScopeMinNode { for( int i=2; i<nIns(); i++ ) // For lazy phis on loops we use a sentinel // that will trigger phi creation on update - dup.addDef(loop ? this : in(i)); + dup.addDef(loop && !_vars.at(i)._final ? this : in(i)); return dup; } @@ -229,8 +271,8 @@ public class ScopeNode extends ScopeMinNode { * @param that The ScopeNode to be merged into this * @return A new node representing the merge point */ - public RegionNode mergeScopes(ScopeNode that) { - RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).keep()); + public RegionNode mergeScopes(ScopeNode that, Parser.Lexer loc) { + RegionNode r = ctrl(new RegionNode(loc,null,ctrl(), that.ctrl()).keep()); mem()._merge(that.mem(),r); this ._merge(that ,r); that.kill(); // Kill merged scope @@ -250,6 +292,20 @@ public class ScopeNode extends ScopeMinNode { } } + // Balance arms of an IF. Extra lonely defs are thrown: "if(pred) int x;". + // Forward refs are copied to the other side, "as if" they were there all along. + public void balanceIf( ScopeNode scope ) { + for( int i = nIns(); i < scope.nIns(); i++ ) { + Var n = scope._vars.at(i); + if( n.isFRef() ) { // RHS has forward refs + _vars.add(n); // Copy to LHS + addDef(scope.in(i)); + } else + throw Parser.error("Cannot define a '"+n._name+"' on one arm of an if",n._loc); + } + } + + // peephole the backedge scope into this loop head scope // We set the second input to the phi from the back edge (i.e. loop body) public void endLoop(ScopeNode back, ScopeNode exit ) { @@ -272,6 +328,8 @@ public class ScopeNode extends ScopeMinNode { // Fill in the backedge of any inserted Phis void _endLoop( ScopeNode scope, Node back, Node exit ) { for( int i=2; i<nIns(); i++ ) { + if( _vars.at(i)._final ) continue; // Final vars did not get modified in the loop + if( _vars.at(i).type().isHighOrConst() ) continue; // Cannot lift higher than a constant, so no Phi if( back.in(i) != scope ) { PhiNode phi = (PhiNode)in(i); assert phi.region()==scope.ctrl() && phi.in(2)==null; @@ -289,38 +347,38 @@ 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 ) pred = pred instanceof NotNode not ? not.in(1) : IterPeeps.add(new NotNode(pred).peephole()); // This is a zero/null test. // Compute the positive test type. - Type tnz = pred._type.nonZero(); - Type tcast = tnz.join(pred._type); - if( tcast != pred._type ) { - Node cast = new CastNode(tnz,ctrl,pred.keep()).peephole().keep(); - _guards.add(pred); - _guards.add(cast); - replace(pred,cast); - } + Type tnz = pred._type.nonZero(); + if( tnz!=null ) + _addGuard(tnz,ctrl,pred); // Compute the negative test type. if( pred instanceof NotNode not ) { Node npred = not.in(1); Type tzero = npred._type.makeZero(); - Type tzcast= tzero.join(npred._type); - if( tzcast != npred._type ) { - Node cast = new CastNode(tzero,ctrl,npred.keep()).peephole().keep(); - _guards.add(npred); - _guards.add( cast); - replace(npred,cast); - } + _addGuard(tzero,ctrl,npred); } } + private void _addGuard(Type guard, Node ctrl, Node pred) { + Type tcast = guard.join(pred._type); + if( tcast != pred._type && !tcast.isHigh() ) { + Node cast = new CastNode(tcast,ctrl,pred.keep()).peephole().keep(); + _guards.add(pred); + _guards.add(cast); + replace(pred,cast); + } + } + + // Remove matching pred/cast pairs from this guarded region. - public void removeGuards( Node ctrl ) { + public ScopeNode removeGuards( Node ctrl ) { assert ctrl instanceof CFGNode; // 0,1 or 2 guards while( true ) { @@ -330,6 +388,7 @@ public class ScopeNode extends ScopeMinNode { g .unkill(); // Pop/kill cast _guards.pop().unkill(); // Pop/kill pred } + return this; } // If we find a guarded instance of pred, replace with the upcasted version @@ -353,16 +412,17 @@ public class ScopeNode extends ScopeMinNode { if( !(n instanceof CFGNode) ) n.unkill(); _guards.clear(); - super.kill(); + // Can have lazy uses remaining + if( isUnused() ) + super.kill(); } - 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/src/main/java/com/seaofnodes/simple/node/ShlNode.java b/src/main/java/com/seaofnodes/simple/node/ShlNode.java index 6fd951e4..21dbd503 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShlNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -5,19 +5,13 @@ 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(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, 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 String glabel() { return "<<"; } @Override public Type compute() { @@ -44,10 +38,10 @@ public class ShlNode extends Node { if( (shl.value()&63)==0 ) return lhs; // (x + c) << i => (x << i) + (c << i) - if( lhs instanceof AddNode add && add.addDep(this).in(2)._type instanceof TypeInteger c && c.isConstant() && c!=TypeInteger.ZERO ) { + if( lhs instanceof AddNode add && add.addDep(this).in(2)._type instanceof TypeInteger c && c.isConstant() ) { long sum = c.value() << shl.value(); if( Integer.MIN_VALUE <= sum && sum <= Integer.MAX_VALUE ) - return new AddNode( new ShlNode(add.in(1),rhs).peephole(), Parser.con(sum) ); + return new AddNode(new ShlNode(_loc,add.in(1),rhs).peephole(), Parser.con(sum) ); } } @@ -55,10 +49,5 @@ public class ShlNode extends Node { return null; } - @Override Node copy(Node lhs, Node rhs) { return new ShlNode(lhs,rhs); } - @Override 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; - } + @Override Node copy(Node lhs, Node rhs) { return new ShlNode(_loc,lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/node/ShrNode.java b/src/main/java/com/seaofnodes/simple/node/ShrNode.java index 22eb45a0..789fb8a8 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -1,23 +1,17 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; 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(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, 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 String glabel() { return ">>>"; } @Override public Type compute() { @@ -48,5 +42,5 @@ public class ShrNode extends Node { return null; } - @Override Node copy(Node lhs, Node rhs) { return new ShrNode(lhs,rhs); } + @Override Node copy(Node lhs, Node rhs) { return new ShrNode(_loc,lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index ab6e4931..50cba348 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -18,7 +18,7 @@ public class StartNode extends LoopNode implements MultiNode { final Type _arg; - public StartNode(Type arg) { super(null); _arg = arg; _type = compute(); } + public StartNode(Type arg) { super(null,null); _arg = arg; _type = compute(); } @Override public String label() { return "Start"; } @@ -29,7 +29,19 @@ public class StartNode extends LoopNode implements MultiNode { @Override public boolean isMultiHead() { return true; } @Override public boolean blockHead() { return true; } - @Override public CFGNode cfg0() { return this; } + @Override public CFGNode cfg0() { return null; } + + // Get the one control following; error to call with more than one e.g. an + // IfNode or other multi-way branch. For Start, its "main" + @Override public CFGNode uctrl() { + // Find "main", its the start. + CFGNode C = null; + for( Node use : _outputs ) + if( use instanceof FunNode fun && fun.sig().isa(TypeFunPtr.MAIN) ) + { assert C==null; C = fun; } + return C; + } + @Override public TypeTuple compute() { return TypeTuple.make(Type.CONTROL,TypeMem.TOP,_arg); diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java index 867225cb..feb8347f 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -1,11 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.IterPeeps; -import com.seaofnodes.simple.GlobalCodeMotion; -import com.seaofnodes.simple.GraphVisualizer; - import java.util.BitSet; public class StopNode extends CFGNode { @@ -15,6 +11,7 @@ public class StopNode extends CFGNode { public StopNode(String src) { super(); _src = src; + _type = compute(); } @Override @@ -24,7 +21,8 @@ public class StopNode extends CFGNode { @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { - if( ret()!=null ) return ret()._print0(sb, visited); + // For the sake of many old tests, and single value prints as "return val" + if( ret()!=null ) return ret()._print0(sb,visited); sb.append("Stop[ "); for( Node ret : _inputs ) ret._print0(sb, visited).append(" "); @@ -33,10 +31,11 @@ public class StopNode extends CFGNode { @Override public boolean blockHead() { return true; } + // If a single Return, return it. // Otherwise, null because ambiguous. public ReturnNode ret() { - return nIns()==1 ? (ReturnNode)in(0) : null; + return nIns()==1 && in(0) instanceof ReturnNode ret ? ret : null; } @Override @@ -48,7 +47,7 @@ public class StopNode extends CFGNode { public Node idealize() { int len = nIns(); for( int i=0; i<nIns(); i++ ) - if( in(i)._type==Type.XCONTROL ) + if( ((ReturnNode)in(i)).fun().isDead() ) delDef(i--); if( len != nIns() ) return this; return null; @@ -57,29 +56,8 @@ public class StopNode extends CFGNode { @Override public int idepth() { if( _idepth!=0 ) return _idepth; int d=0; - for( Node n : _inputs ) - if( n!=null ) - d = Math.max(d,((CFGNode)n).idepth()+1); + for( Node ret : _inputs ) + d = Math.max(d,((ReturnNode)ret).idepth()+1); return _idepth=d; } - @Override public CFGNode idom(Node dep) { return null; } - - public Node addReturn(Node node) { - return addDef(node); - } - - public StopNode iterate( ) { return IterPeeps.iterate(this).typeCheck().GCM(false); } - public StopNode iterate(boolean show) { return IterPeeps.iterate(this).typeCheck().GCM(show ); } - StopNode typeCheck() { - String err = walk( Node::err ); - if( err != null ) throw new RuntimeException(err); - return this; - } - StopNode GCM(boolean show) { - Parser.START.buildLoopTree(this); - if( show ) - System.out.println(new GraphVisualizer().generateDotOutput(this,null,null)); - GlobalCodeMotion.buildCFG(this); - return this; - } } diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 62b49a1a..6032de48 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.*; @@ -20,8 +21,8 @@ public class StoreNode extends MemOpNode { * @param off The offset inside the struct base * @param value Value to be stored */ - public StoreNode(String name, int alias, Type glb, Node mem, Node ptr, Node off, Node value, boolean init) { - super(name, alias, glb, mem, ptr, off, value); + public StoreNode(Parser.Lexer loc, String name, int alias, Type glb, Node mem, Node ptr, Node off, Node value, boolean init) { + super(loc, name, alias, glb, mem, ptr, off, value); _init = init; } @@ -42,6 +43,7 @@ public class StoreNode extends MemOpNode { public Type compute() { Type val = val()._type; TypeMem mem = (TypeMem)mem()._type; // Invariant + if( mem == TypeMem.TOP ) return TypeMem.TOP; Type t = Type.BOTTOM; // No idea on field contents // Same alias, lift val to the declared type and then meet into other fields if( mem._alias == _alias ) { @@ -71,7 +73,7 @@ public class StoreNode extends MemOpNode { return this; } - // Simple store-after-new on same address. Should pick up the + // Simple store-after-new on same address. Should pick up // an init-store being stomped by a first user store. if( mem() instanceof ProjNode st && st .in(0) instanceof NewNode nnn && ptr() instanceof ProjNode ptr && ptr.in(0) == nnn && @@ -79,7 +81,7 @@ public class StoreNode extends MemOpNode { // Cannot fold a store of a single element over the array body initializer value !(tmp._obj.isAry() && tmp._obj._fields[1]._alias==_alias) && // Very sad strong cutout: val has to be legal to hoist to a New - // input, which means it cannot depend on the New. Many many + // input, which means it cannot depend on the New. Many, many // things are legal here but difficult to check without doing a // full dominator check. Example failure: // "struct C { C? c; }; C self = new C { c=self; }" @@ -90,10 +92,11 @@ public class StoreNode extends MemOpNode { // Folding away a broken store err()==null ) { nnn.setDef(nnn.findAlias(_alias),val()); - // Must retype the NewNode - nnn ._type = nnn. compute(); + // Must *retype* the NewNode, this is not monotonic in isolation + // but is monotonic counting from this Store to the New. + nnn ._type = nnn .compute(); mem()._type = mem().compute(); - return st; + return mem(); } return null; @@ -111,13 +114,13 @@ public class StoreNode extends MemOpNode { } @Override - String err() { - String err = super.err(); + public Parser.ParseException err() { + Parser.ParseException err = super.err(); if( err != null ) return err; TypeMemPtr tmp = (TypeMemPtr)ptr()._type; - if( tmp._obj.field(_name)._final ) - return "Cannot modify final field '"+_name+"'"; + if( tmp._obj.field(_name)._final && !"[]".equals(_name) ) + return Parser.error("Cannot modify final field '"+_name+"'",_loc); Type t = val()._type; - return _init || t.isa(_declaredType) ? null : "Cannot store "+t+" into field "+_declaredType+" "+_name; + return _init || t.isa(_declaredType) ? null : Parser.error("Cannot store "+t+" into field "+_declaredType+" "+_name,_loc); } } diff --git a/src/main/java/com/seaofnodes/simple/node/StructNode.java b/src/main/java/com/seaofnodes/simple/node/StructNode.java index db170ab1..076b342a 100644 --- a/src/main/java/com/seaofnodes/simple/node/StructNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StructNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.SB; import com.seaofnodes.simple.type.*; import java.util.BitSet; @@ -18,7 +19,7 @@ public class StructNode extends Node { sb.append(_ts._name).append(" {"); for( int i=0; i<nIns(); i++ ) { sb.append(_ts._fields[i]._fname).append(":"); - (in(i)==null ? Type.BOTTOM : in(i)._type).print(sb); + sb.append((in(i)==null ? Type.BOTTOM : in(i)._type).print(new SB())); sb.append("; "); } sb.setLength(sb.length()-2); diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index 5d6c2643..339c65ca 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -3,7 +3,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; - import java.util.BitSet; public class SubNode extends Node { @@ -25,6 +24,9 @@ public class SubNode extends Node { Type t1 = in(1)._type, t2 = in(2)._type; if( t1.isHigh() || t2.isHigh() ) return TypeInteger.TOP; + // Sub of same is 0 + if( in(1)==in(2) ) + return TypeInteger.ZERO; if( t1 instanceof TypeInteger i1 && t2 instanceof TypeInteger i2 ) { if (i1.isConstant() && i2.isConstant()) @@ -35,9 +37,6 @@ public class SubNode extends Node { i2._min != Long.MIN_VALUE ) return TypeInteger.make(i1._min-i2._max,i1._max-i2._min); } - // Sub of same is 0 - if( in(1)==in(2) ) - return TypeInteger.ZERO; return TypeInteger.BOT; } diff --git a/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java b/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java index 1d147cf6..1f4d67e0 100644 --- a/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java @@ -20,9 +20,13 @@ public class ToFloatNode extends Node { @Override public Type compute() { - if (in(1)._type instanceof TypeInteger i0 && i0.isConstant() ) - return TypeFloat.constant(i0.value()); - return TypeFloat.BOT; + if( in(1)._type == Type.NIL ) return TypeFloat.FZERO; + if (in(1)._type instanceof TypeInteger i0 ) { + if( i0.isHigh() ) return TypeFloat.F64.dual(); + if( i0.isConstant() ) + return TypeFloat.constant(i0.value()); + } + return TypeFloat.F64; } @Override public Node idealize() { return null; } diff --git a/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java b/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java index 83779dd2..3c6a5df3 100644 --- a/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java +++ b/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java @@ -5,9 +5,11 @@ import com.seaofnodes.simple.type.Type; import java.util.BitSet; public class XCtrlNode extends CFGNode { - public XCtrlNode( ) { super(Parser.START); } + public XCtrlNode() { super(Parser.START); } @Override public String label() { return "Xctrl"; } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append("Xctrl"); } + @Override public boolean isConst() { return true; } + @Override public boolean isMultiTail() { return true; } @Override public Type compute() { return Type.XCONTROL; } @Override public Node idealize() { return null; } } diff --git a/src/main/java/com/seaofnodes/simple/node/XorNode.java b/src/main/java/com/seaofnodes/simple/node/XorNode.java index 191933f9..37d7147d 100644 --- a/src/main/java/com/seaofnodes/simple/node/XorNode.java +++ b/src/main/java/com/seaofnodes/simple/node/XorNode.java @@ -1,25 +1,19 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; 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(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, 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() ) @@ -56,10 +50,5 @@ public class XorNode extends Node { return null; } - @Override Node copy(Node lhs, Node rhs) { return new XorNode(lhs,rhs); } - @Override 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; - } + @Override Node copy(Node lhs, Node rhs) { return new XorNode(_loc,lhs,rhs); } } |