diff options
Diffstat (limited to 'src/main/java/com/seaofnodes/simple/node')
32 files changed, 290 insertions, 149 deletions
diff --git a/src/main/java/com/seaofnodes/simple/node/AddFNode.java b/src/main/java/com/seaofnodes/simple/node/AddFNode.java index fd713156..4ad02dbb 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddFNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddFNode.java @@ -1,35 +1,29 @@ package com.seaofnodes.simple.node; - import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeFloat; +import java.util.BitSet; -public class AddFNode extends Node { - public AddFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } +public class AddFNode extends ArithFNode { + public AddFNode(Node lhs, Node rhs) { super(lhs, rhs); } @Override public String label() { return "AddF"; } - @Override protected String format() { return "(%1+%2)"; } + @Override public String glabel() { return "+"; } - @Override - public Type compute() { - if (in(1)._type instanceof TypeFloat i0 && - in(2)._type instanceof TypeFloat i1) { - if (i0.isConstant() && i1.isConstant()) - return TypeFloat.constant(i0.value()+i1.value()); - } - return in(1)._type.meet(in(2)._type); - } + @Override double doOp( double x, double y ) { return x+y; } @Override public Node idealize() { - Node lhs = in(1); - Type t2 = in(2)._type; - // Add of 0. + Type t2 = in(2)._type; if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==0 ) - return lhs; + return in(1); + + // Move constants to RHS: con+arg becomes arg+con + if ( in(1)._type.isConstant() && !t2.isConstant() ) + return swap12(); return null; } diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index dfc7d7b3..2bbe1053 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -139,7 +139,7 @@ public class AddNode extends ArithNode { * dep can make progress. */ static PhiNode pcon(Node op, Node dep) { - return op instanceof PhiNode phi && phi.allCons(dep) ? phi : null; + return op instanceof PhiNode phi && !(phi instanceof ParmNode) && phi.allCons(dep) ? phi : null; } // Compare two off-spine nodes and decide what order they should be in. diff --git a/src/main/java/com/seaofnodes/simple/node/ArithFNode.java b/src/main/java/com/seaofnodes/simple/node/ArithFNode.java new file mode 100644 index 00000000..dafba626 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ArithFNode.java @@ -0,0 +1,30 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.print.ExprPrinter; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; + +public abstract class ArithFNode extends Node { + public ArithFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + return p.open().n(in(1)).p(glabel()).n(in(2)).close(); + } + + abstract double doOp(double x, double y); + + @Override + public Type compute() { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1.isHigh() || t2.isHigh() ) + return Type.TOP; + if( t1 instanceof TypeFloat f1 && + t2 instanceof TypeFloat f2 ) { + if( f1.isConstant() && f2.isConstant() ) + return TypeFloat.constant(doOp(f1.value(),f2.value())); + } + return t1.meet(t2); + } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/ArithNode.java b/src/main/java/com/seaofnodes/simple/node/ArithNode.java index 124acbd7..54290330 100644 --- a/src/main/java/com/seaofnodes/simple/node/ArithNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ArithNode.java @@ -24,15 +24,15 @@ public abstract class ArithNode extends Node { // Generic airthmetic op math: high returns high; low returns low; 2 // constants fold; only 2 non-constants call specialized math. @Override - public final TypeInteger compute() { + public final Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; if( t1.isHigh() || t2.isHigh() ) - return TypeInteger.TOP; + return Type.TOP; if( t1 instanceof TypeInteger x && t2 instanceof TypeInteger y ) return x.isConstant() && y.isConstant() ? con(x,y) - : doOp(x,y); + : doOp(x,y).makeWide( (byte)Math.max(x._widen,y._widen) ); return TypeInteger.BOT; } @@ -53,7 +53,7 @@ public abstract class ArithNode extends Node { if( in(1) instanceof PhiNode lhs && in(2) instanceof PhiNode rhs && lhs.nIns() >= 2 && !lhs.inProgress() && - lhs.region()==rhs.region() && + lhs.region()==rhs.region() && !(lhs.region() instanceof FunNode) && lhs.nIns()>2 && // A 1-input Phi will collapse already // Disallow with self-looping phi; these will collapse (lhs.in(2)!=lhs && rhs.in(2)!=rhs) ) { diff --git a/src/main/java/com/seaofnodes/simple/node/CProjNode.java b/src/main/java/com/seaofnodes/simple/node/CProjNode.java index 1225de31..c62de840 100644 --- a/src/main/java/com/seaofnodes/simple/node/CProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CProjNode.java @@ -34,7 +34,7 @@ public class CProjNode extends CFGNode { @Override public Type compute() { Type t = ctrl()._type; - return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; + return t instanceof TypeTuple tt ? tt._types[_idx] : (t.isHigh() ? Type.TOP : Type.BOTTOM); } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index e83e5cba..3321301b 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -15,9 +15,22 @@ public class CallEndNode extends CFGNode implements MultiNode { private boolean _folding; public boolean folding() { return _folding; } public final TypeRPC _rpc; + // Pessimistic analysis may know more than the written signature. Preserve + // that summary when local SCCP disconnects the callee's return edges. + private Type _retType = Type.BOTTOM; public CallEndNode(CallNode call) { super(new Node[]{call}); _rpc = TypeRPC.constant(_nid); } - public CallEndNode(CallEndNode cend) { super(cend); _rpc = cend._rpc; } + public CallEndNode(CallEndNode cend) { super(cend); _rpc = cend._rpc; _retType = cend._retType; } + + public void freezeResult() { + if( _type instanceof TypeTuple tt ) { + unlock(); + _retType = tt.ret(); + } + } + + @Override public boolean eq(Node n) { return _retType==((CallEndNode)n)._retType; } + @Override int hash() { return _retType.hashCode(); } @Override public String label() { return "CallEnd"; } @Override public boolean blockHead() { return true; } @@ -40,16 +53,23 @@ public class CallEndNode extends CFGNode implements MultiNode { @Override public Type compute() { - if( !(in(0) instanceof CallNode call) ) + if( !(in(0) instanceof CallNode call) || call._type != Type.CONTROL ) return TypeTuple.RET.dual(); - Type ret = Type.BOTTOM; - if( addDep(call.fptr())._type instanceof TypeFunPtr tfp ) { - ret = tfp.ret(); + // Mid-fold, just take the one single callers' return type + if( _folding ) return in(1)._type; + // Grab the TFP and use the functions declared return type. + Type ftype = addDep(call.fptr())._type; + Type ret = ftype.isHigh() ? Type.TOP : Type.BOTTOM; + if( ftype instanceof TypeFunPtr tfp ) { + ret = tfp.ret().join(_retType); // Here, if I can figure out I've found *all* callers, then I can meet // across the linked returns and join with the function return type. - if( tfp.isConstant() && nIns()>1 ) { - assert nIns()==2; // Linked exactly once for a constant - ret = ((TypeTuple)in(1)._type).ret(); // Return type + if( 1+tfp.nfcns() == nIns() ) { // A linked function for every concrete function + ret = Type.TOP; + for( int i=1; i<nIns(); i++ ) { + Type tret = in(i)._type instanceof TypeTuple rtt ? rtt.ret() : in(i)._type; + ret = ret.meet(tret); + } } } return TypeTuple.make(call._type,TypeMem.BOT,ret); @@ -73,12 +93,18 @@ public class CallEndNode extends CFGNode implements MultiNode { // 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) + // Disallow self-recursive inlining (loop unrolling by another name). + // Disallow if still folding other things, as it makes other + // dependency checks carry long chains of half-folded calls. + // Dead control may end the walk before an enclosing function. CFGNode idom = call; - while( !(idom instanceof FunNode) && idom!=null ) + while( idom!=null ) { idom = idom.idom(); + if( idom instanceof FunNode ) break; + if( idom instanceof CallEndNode cend && cend._folding ) break; + } // Inline? - if( idom != fun && idom != null ) { + if( idom instanceof FunNode fun2 && fun2 != fun && !fun2._folding ) { // Trivial inline: rewrite _folding = true; // Rewrite Fun so the normal RegionNode ideal collapses @@ -96,6 +122,8 @@ public class CallEndNode extends CFGNode implements MultiNode { // Bump the global version number invalidating them en-masse. CodeGen.CODE.invalidateIDepthCaches(); return this; + } else if( idom!=null ) { + addDep(idom); } } else { addDep(fun); diff --git a/src/main/java/com/seaofnodes/simple/node/CallNode.java b/src/main/java/com/seaofnodes/simple/node/CallNode.java index f66d1f71..e63b3f62 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -33,7 +33,7 @@ public class CallNode extends CFGNode { } public String name() { if( fptr()._type instanceof TypeFunPtr tfp && tfp._isConstant() && tfp.notNull() ) { - FunNode fun = CodeGen.CODE.link(tfp); + FunNode fun = CodeGen.CODE._link(tfp); if( fun !=null ) return fun._name; if( fptr() instanceof ExternNode ex ) return ex._extern; } @@ -115,16 +115,15 @@ public class CallNode extends CFGNode { } // True if Fun is linked to this Call - boolean linked( FunNode fun ) { + public boolean linked( FunNode fun ) { for( Node n : fun._inputs ) if( n == this ) return true; return false; } - // Link so this calls fun - private Node link( FunNode fun ) { + public Node link( FunNode fun ) { assert !linked(fun); fun.addDef(this); for( Node use : fun._outputs ) diff --git a/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java b/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java index 04b88b87..afdd29be 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java @@ -15,8 +15,8 @@ import com.seaofnodes.simple.util.SB; */ public class ConFldOffNode extends ConstantNode { - public final String _name; // Struct name - public final String _fname; // Field name + public final String _name; // Struct name + public final String _fname; // Field name public ConFldOffNode( String name, String fname ) { super(TypeInteger.BOT); _name = name; _fname = fname; } @Override public String label() { @@ -35,7 +35,7 @@ public class ConFldOffNode extends ConstantNode { @Override public boolean eq(Node n) { ConFldOffNode off = (ConFldOffNode)n; // Invariant - return _name==off._name && _fname==off._fname && super.eq(n); + return _name.equals(off._name) && _fname.equals(off._fname) && super.eq(n); } @Override int hash() { return super.hash() * _name.hashCode() * _fname.hashCode(); } } diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 6384228e..7c330175 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -44,7 +44,7 @@ public class ConstantNode extends Node { @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { if( _con instanceof TypeFunPtr tfp && tfp._isConstant() && tfp.notNull() ) { - FunNode fun = CodeGen.CODE.link(tfp); + FunNode fun = CodeGen.CODE._link(tfp); if( fun!=null && fun._name != null ) return p.p("{ ").p(fun._name).p("}"); } diff --git a/src/main/java/com/seaofnodes/simple/node/DivFNode.java b/src/main/java/com/seaofnodes/simple/node/DivFNode.java index 149499f9..0d037a30 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivFNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivFNode.java @@ -1,26 +1,18 @@ package com.seaofnodes.simple.node; - import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeFloat; +import java.util.BitSet; -public class DivFNode extends Node { - public DivFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } +public class DivFNode extends ArithFNode { + public DivFNode(Node lhs, Node rhs) { super(lhs, rhs); } @Override public String label() { return "DivF"; } - @Override protected String format() { return "(%1/%2)"; } + @Override public String glabel() { return "/"; } - @Override - public Type compute() { - if (in(1)._type instanceof TypeFloat i0 && - in(2)._type instanceof TypeFloat i1) { - if (i0.isConstant() && i1.isConstant()) - return TypeFloat.constant(i0.value()/i1.value()); - } - return in(1)._type.meet(in(2)._type); - } + @Override double doOp( double x, double y ) { return x/y; } @Override public Node idealize() { diff --git a/src/main/java/com/seaofnodes/simple/node/FunNode.java b/src/main/java/com/seaofnodes/simple/node/FunNode.java index e7d6c3a6..70e1c200 100644 --- a/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -91,14 +91,22 @@ public class FunNode extends RegionNode { // Only dead if no callers after SCCP if( unknownCallers() ) return Type.CONTROL; - return super.compute(); + Type t = Type.XCONTROL; + for (int i = 1; i < nIns(); i++) { + // Since no unknown callers, we are not main and the Start input + // will be a Tuple with XControl, so ignore it. Need to be called + // from someplace other than Start + if( !(in(i) instanceof StartNode) ) + t = t.meet(in(i)._type); + } + return t; } @Override public Node idealize() { - // Some linked path dies - Node progress = deadPath(); + // Some linked path dies, except main never kills Start + Node progress = deadPath(unknownCallers()); if( progress!=null ) { if( nIns()==3 && in(2) instanceof CallNode call ) CODE.add(call.cend()); // If Start and one call, check for inline @@ -106,8 +114,11 @@ public class FunNode extends RegionNode { } // Upgrade inferred or user-written return type to actual - if( _ret!=null && _ret._type instanceof TypeTuple tt && tt.ret() != _sig.ret() ) - throw Utils.TODO(); + if( _ret!=null && _ret._type instanceof TypeTuple tt && tt.ret() != _sig.ret() ) { + setSig(_sig.makeFrom(tt.ret())); + return this; + } + // When can we assume no callers? Or no other callers (except main)? // In a partial compilation, we assume Start gets access to any/all @@ -121,8 +132,10 @@ public class FunNode extends RegionNode { // to collapse if( unknownCallers() ) return null; - // If down to a single input, become that input - if( nIns()==2 && !hasPhi() ) { + // If folding (already inlined) down to a single input, become that input. + // Cannot collapse if not-inlining, and might not inline if call site + // calls multiple targets. + if( _folding && nIns()==2 && !hasPhi() ) { CODE.add( CODE._stop ); // Stop will remove dead path CODE.add( _ret ); // Return will compute to TOP control return in(1); // Collapse if no Phis; 1-input Phis will collapse on their own @@ -185,6 +198,14 @@ public class FunNode extends RegionNode { return in; } + // FunNodes must match signature (equivalent: no 2 FunNodes are ever GVN'able) + @Override public boolean eq( Node n ) { + return _sig == ((FunNode)n)._sig; + } + + @Override public int hash() { + return _sig.hashCode(); + } // ------------ // MachNode specifics, shared across all CPUs diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index da6a0cde..c96993e5 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -34,6 +34,7 @@ public class IfNode extends CFGNode implements MultiNode { @Override public Type compute() { // If the If node is not reachable then neither is any following Proj + assert !_inputs.isEmpty(); if (ctrl()._type != Type.CONTROL && ctrl()._type != Type.BOTTOM ) return TypeTuple.IF_NEITHER; Node pred = pred(); @@ -58,11 +59,15 @@ public class IfNode extends CFGNode implements MultiNode { // Hunt up the immediate dominator tree. If we find an identical if // test on either the true or false branch, that side wins. if( !pred()._type.isHighOrConst() ) - for( CFGNode dom = idom(), prior=this; dom!=null; prior = dom, dom = dom.idom() ) + for( CFGNode dom = idom(), prior=this; dom!=null; prior = dom, dom = dom.idom() ) { if( addDep(dom) instanceof IfNode iff && addDep(iff.pred())==pred() && prior instanceof CProjNode prj ) { setDef(1,con( prj._idx==0 ? 1 : 0 )); return this; } + if( dom instanceof RegionNode r ) + for( Node c : r._inputs ) + if( c!= null ) addDep(c); // If region loses input, idom changes + } 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 ad478d55..e057ef1c 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -52,21 +52,32 @@ public class LoadNode extends MemOpNode { @Override public Type compute() { - if( ptr()._type==Type.TOP ) return Type.TOP; // Dead pointer, not a type error. - if( !(mem()._type instanceof TypeMem mem) ) - return _declaredType; // No memory yet? Declared type + Type tmem = mem()._type; + if( !(tmem instanceof TypeMem mem) ) + return tmem; // No memory yet? Assume TOP/BOT assert !_declaredType.isFRef(); // No lifting if ptr might null-check - if( err()!=null || !(ptr()._type instanceof TypeMemPtr tmp) ) - return _declaredType; // No pointer yet? Declared type - Type t = tmp._obj.field(_name)._t; - if( t instanceof TypeConAry ary ) { + Type tptr = ptr()._type; + if( err() != null ) + return _declaredType; + if( !(tptr instanceof TypeMemPtr tmp) ) + return tptr; // No pointer yet? Assume TOP/BOT + // Load field from object + Field f = tmp._obj.field(_name); + // No field? Open objects might yet get the field when falling; + // closed objects with missing field are an error. + if( f == null ) + return tmp.isHigh() ? Type.TOP : _declaredType; + Type t = f._t; + // Load member of constant array + if( t instanceof TypeConAry ary ) t = ary.elem(); // TODO: if offset is known, can peek the constant - } // Lift from declared type and memory input - t = t.join(_declaredType).join(MemMergeNode.contents(mem(),_alias,this)); + t = t.join(MemMergeNode.contents(mem(),_alias,this)); if( ptr()._type.isFinal() || _declaredType.isFinal() ) t = t.makeRO(); // Deep final applied + // Pinch between declared type + t = t.join(_declaredType); return t; } diff --git a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index 8d924b96..7a329117 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -45,6 +45,7 @@ public class MemMergeNode extends Node { if( mem instanceof ProjNode proj && proj.in(0) instanceof NewNode nnn ) { assert proj._idx==1 && nnn.field(alias)!=null; dep.addDep(nnn); + if( dep.addDep(nnn.in(0))._type.isHigh() ) return Type.TOP; return contents(nnn.mem(),alias,dep).meet(nnn.field(alias)._t.makeZero()); } // Function parameters and call results may contain arbitrary heap values. @@ -56,7 +57,6 @@ public class MemMergeNode extends Node { @Override public String label() { return "MemMerge"; } @Override public boolean isMem() { return true; } - @Override public Type compute() { return TypeMem.BOT; } @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { p.p("MEM["); for( int i=1; i<nIns(); i++ ) @@ -67,6 +67,14 @@ public class MemMergeNode extends Node { return p.p("]"); } + + @Override public Type compute() { + for( Node n : _inputs ) + if( n != null && !n._type.isHigh() ) + return TypeMem.BOT; + return TypeMem.TOP; + } + @Override public Node idealize() { boolean progress=false, allDefault=true; for( int i=2; i<nIns(); i++ ) { diff --git a/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java b/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java index bada20ac..787333d9 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java @@ -21,11 +21,11 @@ public class MemPhiNode extends PhiNode { @Override public Type compute() { assert BulkMemPhiNode.checkMem(this,_alias); if( !(region() instanceof RegionNode r) ) - return region()._type==Type.XCONTROL ? TypeMem.TOP : _type; - if( r.inProgress() ) return _minType; + return (region()._type==Type.XCONTROL || region()._type==Type.TOP) ? TypeMem.TOP : _type; + if( r.inProgress() ) return r instanceof LoopNode ? _minType : TypeMem.BOT; Type t = Type.TOP; for( int i=1; i<nIns(); i++ ) - if( addDep(r.in(i))._type!=Type.XCONTROL ) + if( addDep(r.in(i))._type!=Type.XCONTROL && r.in(i)._type!=Type.TOP ) t = t.meet(MemMergeNode.contents(in(i),_alias,this)); return TypeMem.make(_alias,t); } diff --git a/src/main/java/com/seaofnodes/simple/node/MinusFNode.java b/src/main/java/com/seaofnodes/simple/node/MinusFNode.java index 852e646d..74439b8c 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusFNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusFNode.java @@ -14,7 +14,8 @@ public class MinusFNode extends Node { @Override public Type compute() { - if (in(1)._type instanceof TypeFloat i0) + if( in(1)._type.isHigh() ) return TypeFloat.TOP; + if( in(1)._type instanceof TypeFloat i0) return i0.isConstant() ? TypeFloat.constant(-i0.value()) : i0; return TypeFloat.F64; } diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 921e6066..94c69785 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -17,7 +17,7 @@ public class MinusNode extends Node { if( in(1)._type.isHigh() ) return TypeInteger.TOP; if( in(1)._type instanceof TypeInteger i0 && i0._min != Long.MIN_VALUE && i0._max != Long.MIN_VALUE ) - return TypeInteger.make(-i0._max,-i0._min); + return TypeInteger.make(-i0._max,-i0._min,i0._widen); return TypeInteger.BOT; } diff --git a/src/main/java/com/seaofnodes/simple/node/MulFNode.java b/src/main/java/com/seaofnodes/simple/node/MulFNode.java index 6a57f3c5..5c04af43 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulFNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulFNode.java @@ -1,26 +1,18 @@ package com.seaofnodes.simple.node; - import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeFloat; +import java.util.BitSet; -public class MulFNode extends Node { - public MulFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } +public class MulFNode extends ArithFNode { + public MulFNode(Node lhs, Node rhs) { super(lhs, rhs); } @Override public String label() { return "MulF"; } - @Override protected String format() { return "(%1*%2)"; } + @Override public String glabel() { return "*"; } - @Override - public Type compute() { - if (in(1)._type instanceof TypeFloat i0 && - in(2)._type instanceof TypeFloat i1) { - if (i0.isConstant() && i1.isConstant()) - return TypeFloat.constant(i0.value()*i1.value()); - } - return in(1)._type.meet(in(2)._type); - } + @Override double doOp( double x, double y ) { return x*y; } @Override public Node idealize() { diff --git a/src/main/java/com/seaofnodes/simple/node/NewNode.java b/src/main/java/com/seaofnodes/simple/node/NewNode.java index 3c2a8de3..840d2759 100644 --- a/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.util.Utils; /** Allocate a zeroed object. Inputs {ctrl, $mem, size}; @@ -45,7 +46,9 @@ public class NewNode extends Node implements MultiNode { @Override public TypeTuple compute() { - return TypeTuple.make(_ptr,TypeMem.BOT); + return in(0)._type.isHigh() + ? TypeTuple.make(_ptr.makeHigh(),TypeMem.TOP) + : TypeTuple.make(_ptr,TypeMem.BOT); } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 3eacbb16..414530b4 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.BaseNode; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.Utils; @@ -154,9 +155,9 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { } // Insert the numbered input, sliding other inputs to the right - Node insertDef(int idx, Node new_def) { - _inputs.add(idx,null); - return setDef(idx,new_def); + public void insertDef(int idx, Node new_def) { + _inputs.insert(null,idx); + setDef(idx,new_def); } /** @@ -182,7 +183,7 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { // Remove node 'use' from 'def's (i.e. our) output list, by compressing the list in-place. // Return true if the output list is empty afterward. // Error is 'use' does not exist; ok for 'use' to be null. - protected boolean delUse( Node use ) { + public boolean delUse( Node use ) { _outputs.del(_outputs.find(use)); moveDepsToWorklist(); // User-count and anti-dependence queries can now change. return _outputs.isEmpty(); @@ -213,8 +214,11 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { while( nIns()>0 ) { // Set all inputs to null, recursively killing unused Nodes Node old_def = _inputs.removeLast(); // Revisit neighbor because removed use - if( old_def != null && CODE.add(old_def).delUse(this) ) - old_def.kill(); // If we removed the last use, the old def is now dead + if( old_def != null ) { + if( CODE.add(old_def).delUse(this) ) + old_def.kill(); // If we removed the last use, the old def is now dead + old_def.moveDepsToWorklist(); // Use-count changes can enable distant rewrites. + } } assert isDead(); // Really dead now } @@ -431,7 +435,7 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { // If changing, add users to worklist. public Type setType(Type type) { Type old = _type; - assert old==null || type.isa(old); // Since _type not set, can just re-run this in assert in the debugger + assert old == null || type.isa(old) : "Monotonicity test failed"; if( old == type ) return old; _type = type; // Set _type late for easier assert debugging CODE.addAll(_outputs); @@ -499,7 +503,7 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { public Node dep(int idx) { return _deps.get(idx); } /** - * Add a node to the list of dependencies. Only add it if its not an input + * Add a node to the list of dependencies. Only add it if it's not an input * or output of this node, that is, it is at least one step away. The node * being added must benefit from this node being peepholed. */ @@ -523,9 +527,10 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { } // Move the dependents onto a worklist, and clear for future dependents. - public void moveDepsToWorklist( ) { - if( _deps==null ) return; - CODE.addAll(_deps); + public void moveDepsToWorklist( ) { moveDepsToWorklist(CODE._iter); } + public void moveDepsToWorklist( IterPeeps iter ) { + if( _deps == null ) return; + iter.addAll(_deps); _deps.clear(); } diff --git a/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/src/main/java/com/seaofnodes/simple/node/ParmNode.java index 8b614624..95934e4b 100644 --- a/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -2,7 +2,9 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMemPtr; public class ParmNode extends PhiNode { @@ -32,6 +34,25 @@ public class ParmNode extends PhiNode { // Always in-progress until we run out of unknown callers @Override public boolean inProgress() { return in(0) instanceof FunNode fun && fun.inProgress(); } + @Override + public Node idealize() { + if( !(region() instanceof FunNode) ) + return in(1); // Input has collapse to e.g. starting control. + // If function is folding, do all possible peeps + if( fun()._folding ) return super.idealize(); + + // Can upgrade minType even while in-progress + if( _minType instanceof TypeMemPtr tmp && _minType.isFRef() ) { + TypeMemPtr tmp2 = (TypeMemPtr) Parser.TYPES.get(tmp._obj._name); + if( tmp2!=null && tmp2 != _minType ) { + _minType = tmp2; + return this; + } + } + // Skip most phi optimizations on parms + return null; + } + @Override public boolean eq( Node n ) { return ((ParmNode)n)._idx==_idx && super.eq(n); } diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index af5d900b..953e009e 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -15,6 +15,8 @@ public class PhiNode extends Node { // Int stays Int, Ptr stays Ptr, Control stays Control, Mem stays Mem. Type _minType; + int lattice_drop; + public PhiNode(String label, Type minType, Node... inputs) { super(inputs); _label = label; @@ -51,26 +53,47 @@ public class PhiNode extends Node { public CFGNode region() { return (CFGNode)in(0); } @Override public boolean isMem() { return _minType instanceof TypeMem; } + boolean isRPC() { return false; } @Override public Type compute() { if( !(region() instanceof RegionNode r) ) - return region()._type==Type.XCONTROL ? (_type instanceof TypeMem ? TypeMem.TOP : Type.TOP) : _type; + return region()._type==Type.XCONTROL || region()._type==Type.TOP ? (_type instanceof TypeMem ? TypeMem.TOP : Type.TOP) : _type; // During parsing Phis have to be computed type pessimistically. - if( r.inProgress() ) return _minType; + if( r.inProgress() || in(nIns()-1)==null ) + // Loop-Phis must lift to the declared type, because that is how + // the Parser keeps precise types until the loop finishes parsing. + // Similar, ParmNodes use precise minType until all calls are + // linked (post opto). + return r instanceof LoopNode || (this instanceof ParmNode) ? _minType : Type.BOTTOM; // Set type to local top of the starting type - //Type t = _minType.dual(); Type t = Type.TOP; - for (int i = 1; i < nIns(); i++) + 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. - if( addDep(r.in(i))._type != Type.XCONTROL ) { + Type ctrl = addDep(r.in(i))._type; + if( ctrl != Type.XCONTROL && ctrl != Type.TOP ) { if( in(i)._type==Type.BOTTOM ) return Type.BOTTOM; t = t.meet(in(i)._type); } - t = t.join( _minType ); - return t; + } + Type newt = t.join( _minType ); + + // Widen loop Phis so integer ranges cannot grow one step per trip forever. + // Calls are opaque during SCCP here. The next chapter also widens at + // ParmNode and CallEndNode when solving through recursive calls. + // Above-center ranges may still fall to unwidened constants. + // Widen only below-center ranges to preserve monotonicity. + if( region() instanceof LoopNode && // Only around loops + newt instanceof TypeInteger newi && + // Types changed and are falling (the optimistic case, expected to fall forever) + newi != _type ) { + if( !newi.isHigh() && !newi.isConstant() && (!(_type instanceof TypeInteger oldi) || newi._widen <= oldi._widen) ) + return newi.same_but_slightly_wider_than(_minType); + } + + return newt; } @Override @@ -79,7 +102,7 @@ public class PhiNode extends Node { return in(1); // Input has collapse to e.g. starting control. // Can upgrade minType even while in-progress if( _minType instanceof TypeMemPtr tmp && _minType.isFRef() ) { - TypeMemPtr tmp2 = (TypeMemPtr)CodeGen.CODE.P.TYPES.get(tmp._obj._name); + TypeMemPtr tmp2 = (TypeMemPtr) Parser.TYPES.get(tmp._obj._name); if( tmp2!=null && tmp2._obj != tmp._obj ) { _minType = tmp.makeFrom(tmp2._obj); return this; @@ -124,13 +147,14 @@ public class PhiNode extends Node { Node val = in(3-nullx); if( val instanceof CastNode cast ) val = cast.in(1); - if( addDep(r.idom(this)) instanceof IfNode iff && addDep(iff.pred())==val ) { + Node ridom = r.idom(this); + if( ridom instanceof IfNode iff && addDep(iff.pred())==val ) { // Must walk the idom on the null side to make sure we hit False. CFGNode idom = (CFGNode)r.in(nullx); while( idom != null && idom.nIns() > 0 && idom.in(0) != iff ) idom = idom.idom(); if( idom instanceof CProjNode proj && proj._idx==1 ) return val; - } + } else if( ridom != null ) addDep(ridom); } } diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 26b3a522..92c6c2be 100644 --- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -41,7 +41,7 @@ public class ProjNode extends Node { @Override public Type compute() { Type t = in(0)._type; - return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; + return t instanceof TypeTuple tt ? tt._types[_idx] : t.oob(); } @Override public Node idealize() { return ((MultiNode)in(0)).pcopy(_idx); } diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 72f0df7e..59030dee 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -38,7 +38,7 @@ public class RegionNode extends CFGNode { public Node idealize() { if( inProgress() ) return null; - Node progress = deadPath(); + Node progress = deadPath(false); if( progress!=null ) return progress; // If down to a single input, become that input @@ -84,16 +84,21 @@ public class RegionNode extends CFGNode { return null; } - Node deadPath() { + Node deadPath(boolean skipStart) { // Delete dead paths into a Region - int path = findDeadInput(); + int path = findDeadInput(skipStart ? 2 :1); if( path==0 ) return null; + // Do not delete the entry path of a loop (ok to remove the back edge // and make the loop a single-entry Region which folds away the Loop). // Folding the entry path confused the loop structure, moving the // backedge to the entry point. if( this instanceof LoopNode loop && loop.entry()==in(path) ) return null; + return removeDeadPath(path); + } + + public Node removeDeadPath(int path) { // Cannot use the obvious output iterator here, because a Phi deleting // an input might recursively delete *itself*. This shuffles the // output array, and we might miss iterating an unrelated Phi. So on @@ -102,15 +107,16 @@ public class RegionNode extends CFGNode { while( nouts != nOuts() ) { nouts = nOuts(); for( int i=0; i<nOuts(); i++ ) - if( out(i) instanceof PhiNode phi && phi.nIns()==nIns() ) + if( out(i) instanceof PhiNode phi && phi.nIns()==nIns() ) { + CodeGen.CODE.addAll(phi.in(path)._outputs); CodeGen.CODE.addAll(phi.delDef(path)._outputs); + } } return isDead() ? Parser.XCTRL : delDef(path); } - - private int findDeadInput() { - for( int i=1; i<nIns(); i++ ) + private int findDeadInput(int startIdx) { + for( int i=startIdx; i<nIns(); i++ ) if( in(i)._type==Type.XCONTROL ) return i; return 0; // All inputs alive @@ -131,10 +137,10 @@ public class RegionNode extends CFGNode { if( use instanceof PhiNode ) { for( Node data : use._outputs ) { if( !(data instanceof PhiNode phi2) || phi2.region()!=this ) - { addDep(use); if( data!=null ) addDep(data); return true; } + { addDep(use); if( data!=null ) addDep(data); return true; } } } else - { addDep(use); return true; } // Control user + { addDep(use); return true; } // Control user } return false; } @@ -154,7 +160,8 @@ public class RegionNode extends CFGNode { CFGNode lca = null; // Recompute from predecessors: CFG edits can change the dominator. for( int i=1; i<nIns(); i++ ) - lca = cfg(i).domLCA(lca,dep); + if( !cfg(i)._type.isHigh() ) + lca = cfg(i).domLCA(lca,dep); return lca; } diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 6d268994..266657be 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -108,12 +108,17 @@ public class ReturnNode extends CFGNode { } @Override public Parser.ParseException err() { - return expr()._type==Type.BOTTOM ? mixerr(ti,tf,tp,tn,_fun._loc) : null; + if( ctrl()._type != Type.CONTROL ) return null; // Exit path is dead + return expr()._type==Type.BOTTOM || expr()._type==Type.TOP ? 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 ) + // Hit when the function never returns. e.g. `f = { -> return f() };` return Parser.error("No defined return type", loc); + // Rather ugly way to print conflicting return types + int cnt = (ti?1:0) + (tf?1:0) + (tp||tn?1:0); + if( cnt==1 ) return null; // Uniform return type, something else errored and will report SB sb = new SB().p("No common type amongst "); if( ti ) sb.p("int and "); if( tf ) sb.p("f64 and "); diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 262f6bf3..47f12d82 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -165,7 +165,7 @@ public class StoreNode extends MemOpNode { Parser.ParseException err = super.err(); if( err != null ) return err; if( ptr()._type == Type.TOP ) - return null; // Dead store + return null; // This means we have an error input, report elsewhere TypeMemPtr tmp = (TypeMemPtr)ptr()._type; if( (tmp._ro || tmp._obj.field(_name)._final) && !_init ) return Parser.error("Cannot modify final field '"+_name+"'",_loc); diff --git a/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/src/main/java/com/seaofnodes/simple/node/SubFNode.java index 2d218a03..3fc4f7ca 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubFNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubFNode.java @@ -1,35 +1,25 @@ package com.seaofnodes.simple.node; - import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeFloat; +import java.util.BitSet; -public class SubFNode extends Node { - public SubFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } +public class SubFNode extends ArithFNode { + public SubFNode(Node lhs, Node rhs) { super(lhs, rhs); } @Override public String label() { return "SubF"; } - @Override protected String format() { return "(%1-%2)"; } + @Override public String glabel() { return "-"; } - @Override - public Type compute() { - if (in(1)._type instanceof TypeFloat i0 && - in(2)._type instanceof TypeFloat i1) { - if (i0.isConstant() && i1.isConstant()) - return TypeFloat.constant(i0.value()-i1.value()); - } - return in(1)._type.meet(in(2)._type); - } + @Override double doOp( double x, double y ) { return x-y; } @Override public Node idealize() { - Node lhs = in(1); - Type t2 = in(2)._type; - // Sub of 0. + Type t2 = in(2)._type; if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==0 ) - return lhs; + return in(1); return null; } diff --git a/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java b/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java index 7b0122ce..840a95ec 100644 --- a/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java @@ -15,12 +15,10 @@ public class ToFloatNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() ) return TypeFloat.F64.dual(); 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()); - } + if( in(1)._type instanceof TypeInteger i0 && i0.isConstant() ) + return TypeFloat.constant(i0.value()); return TypeFloat.F64; } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/arm/SetARM.java b/src/main/java/com/seaofnodes/simple/node/cpus/arm/SetARM.java index 1cda4787..afbbd3bf 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/arm/SetARM.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/arm/SetARM.java @@ -21,6 +21,7 @@ public class SetARM extends MachConcreteNode implements MachNode { @Override public RegMask outregmap() { return arm.WMASK; } @Override public void encoding( Encoding enc ) { + // Using RM==RN==31 implies a *zero* value, not R31. int body = Arm64.cset(Arm64.OP_CSET,0b11111, Arm64.make_condition(_bop), 0b011111, enc.reg(this)); enc.add4(body); } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java b/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java index b4609419..fae98a99 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java @@ -239,7 +239,9 @@ public class arm extends Machine { if( idx-2-fcnt < cargs.length ) return cargs[idx-2-fcnt]; } - throw Utils.TODO(); // Pass on stack slot + // Pass on stack slot (8 and higher) + if( maxArgSlot>0 ) throw Utils.TODO(); + return new RegMask(MAX_REG + 1 + (idx - 2)); } // Return the max stack slot used by this signature, or 0 diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/MemOpRISC.java b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/MemOpRISC.java index 22dba099..adf21848 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/MemOpRISC.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/MemOpRISC.java @@ -50,6 +50,9 @@ public abstract class MemOpRISC extends MemOpNode implements MachNode { if( _declaredType == TypeInteger.BOOL) func3=4; // LBU if( _declaredType == TypeInteger.U16 ) func3=5; // LHU if( _declaredType == TypeInteger.U32 ) func3=6; // LWU + if( _declaredType instanceof TypeInteger ti ) { + if( -128 <= ti._min && ti._max < 128 ) func3 = 0; // LB + } // float if( _declaredType == TypeFloat.F32) func3 = 2; // fLW fSW diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SetX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SetX86.java index 533d5652..864c1b55 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SetX86.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SetX86.java @@ -30,6 +30,7 @@ public class SetX86 extends MachConcreteNode implements MachNode { case "<" -> _unsigned ? 0x92 : 0x9C; // SETB /SETL case "<=" -> _unsigned ? 0x96 : 0x9E; // SETBE/SETLE case ">=" -> _unsigned ? 0x93 : 0x9D; // SETAE/SETGE + case ">" -> _unsigned ? 0x97 : 0x9F; // SETA /SETG default -> throw Utils.TODO(); }; X86.set(enc,op&15,enc.reg(this)); |