diff options
| author | Cliff Click <cliffc@acm.org> | 2025-06-13 15:42:08 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-08-10 11:11:18 -0700 |
| commit | e57bdd315a7918a0d130e1c95648ca4a1b4f08ed (patch) | |
| tree | ea659c39bce731b506347a80f424e3c325ff5326 /src/main/java | |
| parent | 08d33f808db30936b273582bcfaddcbc5a57c112 (diff) | |
| download | Simple-e57bdd315a7918a0d130e1c95648ca4a1b4f08ed.tar.gz Simple-e57bdd315a7918a0d130e1c95648ca4a1b4f08ed.zip | |
Chapter 24: Chaining Relationals and Sparse Conditional Constant Propagation
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Hadházy Tamás <helsgithub15@gmail.com>
Diffstat (limited to 'src/main/java')
45 files changed, 788 insertions, 328 deletions
diff --git a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java index 9ae4231e..18ff470a 100644 --- a/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -1,6 +1,8 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.print.JSViewer; @@ -46,7 +48,7 @@ import java.util.Random; */ public class IterPeeps { - private final WorkList<Node> _work; + public final WorkList<Node> _work; public IterPeeps( long seed ) { _work = new WorkList<>(seed); } @@ -59,7 +61,7 @@ public class IterPeeps { * Iterate peepholes to a fixed point */ public void iterate( CodeGen code ) { - assert progressOnList(code); + assert progressOnList(code, _work, true); int cnt=0; Node n; @@ -89,7 +91,7 @@ public class IterPeeps { // If there are distant neighbors, move to worklist n.moveDepsToWorklist(); JSViewer.show(); // Show again - assert progressOnList(code); // Very expensive assert + assert progressOnList(code, _work, true); // Very expensive assert } if( n.isUnused() && !(n instanceof StopNode) ) n.kill(); // Just plain dead @@ -109,18 +111,24 @@ public class IterPeeps { // neighbors and these should fail, but will then try to add dependencies // {@link #Node.addDep} which is a side effect in an assert. The {@link // #midAssert} is used to stop this side effect. - private boolean progressOnList(CodeGen code) { + // Pessimistic solver assert + public static boolean progressOnList(CodeGen code, WorkList<Node> list, boolean dir ) { code._midAssert = true; Node changed = code._stop.walk( n -> { - Node m = n; - if( n.compute().isa(n._type) && (!n.iskeep() || n._nid<=6) ) { // Types must be forwards, even if on worklist - if( _work.on(n) ) return null; - m = n.peepholeOpt(); - if( m==null ) return null; - } - System.err.println("BREAK HERE FOR BUG"); - return m; - }); + Node m = n; + Type nval = n.compute(); + if( (!n.iskeep() || n._nid<=8) && // Types must be forwards, even if on worklist + ( dir + ? nval.isa(n._type) // Pesi: new value lifts over old + : n._type.isa(nval) // Opto: new value falls over old + ) ) { + if( list.on(n) ) return null; + m = n.peepholeOpt(); + if( m==null ) return null; + } + System.err.println("BREAK HERE FOR BUG"); + return m; + }); code._midAssert = false; return changed==null; } @@ -176,7 +184,7 @@ public class IterPeeps { /** * True if Node is on the WorkList */ - boolean on( E x ) { return _on.get(x._nid); } + public boolean on( E x ) { return _on.get(x._nid); } boolean isEmpty() { return _len==0; } /** diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 8a6b1967..f80e8f2c 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -142,7 +142,7 @@ public class Parser { _scope.mem(new MemMergeNode(false)); // Parse the sys import - _lexer = new Lexer(com.seaofnodes.simple.sys.SYS); + _lexer = new Lexer(sys.SYS); while( !_lexer.isEOF() ) { parseStatement(); _lexer.skipWhiteSpace(); @@ -160,18 +160,26 @@ public class Parser { // default main). FunNode main = _code.link(_code._main); StopNode stop = _code._stop; + // Gather an explicit main + FunNode xmain = null; + for( Node n : stop._inputs ) + if( n instanceof ReturnNode ret && "main".equals(ret.fun()._name) ) + if( xmain != null ) throw Utils.TODO(); + else xmain = ret.fun(); + if( main.ret().expr()._type==Type.TOP && main.uctrl()==null ) { // Kill an empty default main; so it does not attempt to put a // "main" in any final ELF file main.setDef(1,XCTRL); // Delete default start input stop.delDef(stop._inputs.find(main.ret())); + if( xmain != null ) + _code.setMain(xmain); + } else { // We have a non-empty default main. - // Check for an explicit main - for( Node n : stop._inputs ) - if( n instanceof FunNode fun && fun._name.equals("main") ) - // Found an explicit "main" AND we have a default "main" - throw error("Cannot define both an explicit main and a default main"); + if( xmain != null ) + // Found an explicit "main" AND we have a default "main" + throw error("Cannot define both an explicit main and a default main"); main._name = "main"; } @@ -540,9 +548,8 @@ public class Parser { // Parse a conditional expression, merging results. private Node parseTrinary( Node pred, String fside ) { - pred.keep(); - // IfNode takes current control and predicate + pred.keep(); Node ifNode = new IfNode(ctrl(), pred).peephole(); // Setup projection nodes Node ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); @@ -712,7 +719,7 @@ public class Parser { // Type is sane if( et!=Type.BOTTOM && !et.shallowISA(t) ) - expr = peep(new CastNode(t,null,expr)); + expr = peep(new CastNode(t.isConstant() ? t : t.widen(),null,expr)); return expr; } @@ -818,7 +825,7 @@ public class Parser { // Lift type to the declaration. This will report as an error later if // we cannot lift the type. if( !lift._type.isa(t) ) - lift = peep(new CastNode(t,null,lift)); + lift = peep(new CastNode(t.widen(),null,lift)); // Define a new name if( !_scope.define(name,t,xfinal || fld_final,lift, loc) ) throw error("Redefining name '" + name + "'", loc); @@ -1037,49 +1044,100 @@ public class Parser { } private Node parseBitwise() { - Node lhs = parseComparison(); + Node lhs = parseEquality(); while( true ) { if( false ) ; else if( matchOp('&') ) lhs = new AndNode(loc(),lhs,null); else if( matchOp('|') ) lhs = new OrNode(loc(),lhs,null); else if( match ("^") ) lhs = new XorNode(loc(),lhs,null); else break; - lhs.setDef(2,parseComparison()); + lhs.setDef(2,parseEquality()); lhs = peep(lhs); } return lhs; } + + + /** + * Parse an eq/ne expression + */ + private Node parseEquality() { + Node lhs = parseComparison(); + while( true ) { + boolean eq = false; + if( match("==") ) eq = true; + else if( !match("!=") ) break; + lhs.keep(); + Node rhs = parseComparison(); + lhs = peep(new BoolNode.EQ(lhs.unkeep(),rhs).widen()); + if( !eq ) lhs = peep(new NotNode(lhs)); + } + return lhs; + } + /** * Parse an expression of the form: * * <pre> - * expr : additiveExpr op additiveExpr + * expr : shiftExpr < shiftExpr <= shiftExpr... + * expr : shiftExpr > shiftExpr >= shiftExpr... * </pre> * @return an comparator expression {@link Node}, never {@code null} */ private Node parseComparison() { - var lhs = parseShift(); + Node lhs = parseShift(); + int dir = 0; + while( true ) { - int idx=0; boolean negate=false; - // Test for any local nodes made, and "keep" lhs during peepholes + int dir0; if( false ) ; - else if( match("==") ) { idx=2; lhs = new BoolNode.EQ(lhs, null); } - else if( match("!=") ) { idx=2; lhs = new BoolNode.EQ(lhs, null); negate=true; } - else if( match("<=") ) { idx=2; lhs = new BoolNode.LE(lhs, null); } - else if( match("<" ) ) { idx=2; lhs = new BoolNode.LT(lhs, null); } - else if( match(">=") ) { idx=1; lhs = new BoolNode.LE(null, lhs); } - else if( match(">" ) ) { idx=1; lhs = new BoolNode.LT(null, lhs); } + else if( match("<=" ) ) dir0 = -1; + else if( match(">=" ) ) dir0 = -2; + else if( match("<" ) ) dir0 = 1; + else if( match(">" ) ) dir0 = 2; else break; - // Peepholes can fire, but lhs is already "hooked", kept alive - lhs.setDef(idx,parseShift()); - lhs = peep(lhs.widen()); - if( negate ) // Extra negate for != - lhs = peep(new NotNode(lhs)); + lhs.keep(); + // Check and record direction + if( dir==0 ) { + dir = Math.abs(dir0); + Node rhs = parseShift(); + lhs = makeCompBool(dir0,lhs.unkeep(),rhs); // Convert to a bool + } else if( dir == Math.abs(dir0) ) { + // e0 < lhs < ??? + Node ifNode = new IfNode(ctrl(), lhs).peephole(); + Node ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole(); + Node ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole(); + // False side does nothing + ScopeNode fScope = _scope.dup(); + fScope.ctrl(ifF); + // True side executes next part of range + ctrl(ifT); + _scope.addGuards(ifT,lhs,false); + Node rhs = parseShift(); + _scope.removeGuards(ifT); // TODO: I think should remain true as long as possible + Node next = makeCompBool(dir0, lhs, rhs).keep(); + // Merge result + RegionNode r = ctrl(_scope.mergeScopes(fScope, loc())); + assert next._type.meet(lhs._type).isa( TypeInteger.BOOL ); + lhs = peep(new PhiNode("",TypeInteger.BOOL,r,next.unkeep(),lhs.unkeep())); + r.peephole(); + } else { + throw error("Mixing relational directions in a chained relational test"); + } } return lhs; } + private Node makeCompBool( int dir0, Node lhs, Node rhs ) { + // Convert to a bool + if( Math.abs(dir0)==2 ) // Swap direction + { Node tmp = lhs; lhs = rhs; rhs = tmp; } + lhs = peep(dir0 < 0 ? new BoolNode.LE(lhs,rhs) : new BoolNode.LT(lhs,rhs)); + return peep(lhs.widen()); + } + + /** * Parse an additive expression * @@ -1493,6 +1551,8 @@ public class Parser { Type tf = f._t; if( tf instanceof TypeMemPtr ftmp && ftmp.isFRef() ) tf = ftmp.makeFrom(((TypeMemPtr)(TYPES.get(ftmp._obj._name)))._obj); + if( base.isAry() && tf instanceof TypeConAry con ) + tf = con.elem(); // Field offset; fixed for structs, computed for arrays Node off = (name.equals("[]") // If field is an array body @@ -1662,7 +1722,6 @@ public class Parser { // Into the call CallNode call = (CallNode)new CallNode(loc(), args.asAry()).peephole(); - // Post-call setup CallEndNode cend = (CallEndNode)new CallEndNode(call).peephole(); call.peephole(); // Rerun peeps after CallEnd, allows early inlining diff --git a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 6c958f32..3715d015 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -7,6 +7,7 @@ import com.seaofnodes.simple.print.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.util.Utils; import java.io.IOException; import java.util.*; @@ -30,7 +31,6 @@ public class CodeGen { Export, // Export } public Phase _phase; - // --------------------------- // Compilation source code public final String _src; @@ -124,7 +124,7 @@ public class CodeGen { // are structurally equal. public final HashMap<Node,Node> _gvn = new HashMap<>(); - // + // Source of unique function indices private int _fidx =0; public TypeFunPtr makeFun( TypeFunPtr fun ) { int fidx = _fidx++; @@ -132,23 +132,33 @@ public class CodeGen { return fun.makeFrom(fidx); } // Signature for MAIN - public final TypeFunPtr _main; - // Reverse from a constant function pointer to the IR function being called - public FunNode link( TypeFunPtr tfp ) { - assert tfp.isConstant(); - return _linker.get(tfp.makeFrom(Type.BOTTOM)); + public TypeFunPtr _main; + public void setMain(FunNode main) { + _main = main.sig(); + link(main); + } + // Reverse from a constant function pointer to the IR function being called. + // Error to call with a non-constant TFP + public FunNode link( TypeFunPtr tfp ) { return link(tfp.fidx()); } + // Return the FunNode from a fidx + public FunNode link( int fidx ) { + FunNode fun =_linker.atX(fidx); + if( fun!=null && fun.isDead() ) { + _linker.setX(fidx,null); fun = null; } + return fun; } // Insert linker mapping from constant function signature to the function // being called. public void link(FunNode fun) { - _linker.put(fun.sig().makeFrom(Type.BOTTOM),fun); + int fidx = fun.sig().fidx(); + _linker.setX(fidx,fun); } // "Linker" mapping from constant TypeFunPtrs to heads of function. These // TFPs all have exact single fidxs and their return is wiped to BOTTOM (so // the return is not part of the match). - private final HashMap<TypeFunPtr,FunNode> _linker = new HashMap<>(); + final Ary<FunNode> _linker = new Ary<>(FunNode.class); // Parser object public final Parser P; @@ -185,59 +195,14 @@ public class CodeGen { _phase = Phase.Opto; long t0 = System.currentTimeMillis(); - // Pessimistic peephole optimization on a worklist - _iter.iterate(this); - - // OPTIMISTIC PASS GOES HERE - - // Not really a true optimistic pass, but look for unlinked functions. - // This can be removed, which may trigger another round of pessimistic. - // This is the point where we flip from a virtual Call Graph (any call - // can call any function) to having a correct (but conservative) CG. - int progress = 0; - while( progress != _start.nOuts() ) { - progress = _start.nOuts(); - FunNode main = link(_main); - for( int i=0; i<_start.nOuts(); i++ ) { - Node use = _start.out(i); - if( use instanceof FunNode fun && - fun.nIns()==2 && fun.in(1)==_start && fun != main && - (fun._name==null || fun._name.startsWith("sys.")) ) { - add(fun).setDef(1,Parser.XCTRL); - addAll(fun._outputs); - i--; - } - } - _iter.iterate(this); - } - - // Freeze field sizes; do struct layouts; convert field offsets into - // constants. - for( int i=0; i<_start.nOuts(); i++ ) { - Node use = _start.out(i); - if( use instanceof ConFldOffNode off ) { - TypeMemPtr tmp = (TypeMemPtr) Parser.TYPES.get(off._name); - off.subsume( off.asOffset(tmp._obj) ); - i--; - } - } - _iter.iterate(this); - - // To help with testing, sort StopNode returns by NID - Arrays.sort(_stop._inputs._es,0,_stop.nIns(),(x,y) -> x._nid - y._nid ); + Opto.opto(this); _tOpto = (int)(System.currentTimeMillis() - t0); - - // TODO: - // Optimistic - // TODO: - // loop unroll, peel, RCE, etc return this; } public <N extends Node> N add( N n ) { return _iter.add(n); } public void addAll( Ary<Node> ary ) { _iter.addAll(ary); } - // --------------------------- // Last check for bad programs public int _tTypeCheck; diff --git a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index 1065cd9f..e3684445 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -189,12 +189,16 @@ public class Encoding { rpos.put(_code._start.loop(),rpo); BitSet visit = _code.visit(); rpo.add(_code._stop); + FunNode main = _code.link(_code._main); for( Node n : _code._start._outputs ) - if( n instanceof FunNode fun ) { + if( n instanceof FunNode fun && fun != main ) { int x = rpo._len; _rpo_cfg(fun, visit, rpos ); assert rpo.at(x) instanceof ReturnNode; } + // Do any main function last... so it lands at offset 0 in the RPO + if( main!=null ) + _rpo_cfg(main, visit, rpos ); rpo.add(_code._start); // Reverse in-place diff --git a/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/src/main/java/com/seaofnodes/simple/codegen/Opto.java new file mode 100644 index 00000000..f8ce1e54 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -0,0 +1,264 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; +import java.util.Arrays; + +// Optimistic Algorithm +abstract public class Opto { + + // Optimistic analysis - extended SCCP + + // Start all Types at TOP, and propagate changes until stable. Unlike a + // normal Sparse Conditional Constant Propagation, this version is + // interprocedural, computing effectively CFA0 in linear time using the + // normal SCCP algorithm. + + // This algo also builds a Call Graph; as Calls become reachable (CONTROL + // not TOP nor XCONTROL), they "link" against the reaching function + // pointers - adding edges from the Call to the Fun, and from the Return to + // the CallEnd. This allows the normal algorithm to use the normal edge + // propagation rules as function argument types stabilize. In the end, we + // get a fairly precise set of Call Graph edges between CallNodes and + // FunNodes. + public static void opto(CodeGen code) { + + // Pessimistic peephole optimization on a worklist - this completes + // whatever peepholes can run after parsing. + code._iter.iterate(code); + + // Reset Types before running the worklist algorithm + Ary<Type> oldTypes = new Ary<>(Type.class); // Used for asserts only + resetToTop(code,oldTypes); + + // The whole-world assumption: we use it if compiling `main`, and not otherwise. + // The assumption is no unknown callers into functions: + // - during or past an Opto phase (but not before, since parse through + // pessimistic must assume somebody calls an unknown function which + // calls everybody). + // - Have a `main` to start tracing the Call Graph from + // - - True for most test cases + // - - False for lacking a main; we assume the linker will call all public functions + + // True if we can make the "whole world" assumption, which means we are + // compiling the program entry: `main`. + boolean wholeWorld = code.link(code._main) != null; + + + // If wholeWorld, remove the Start inputs to functions - they are not + // called unless they get linked (hence go dead and can be removed). + // If not wholeWorld, keep only public methods (and not the std lib). + unlinkStart(wholeWorld,code); + + + // OPTIMISTIC INTERPROCEDURAL SCCP + sccp(code, oldTypes); + + // After SCCP add everything changed to the worklist and see if + // peepholes can make more progress. + moveChangesToWorklist(code, oldTypes); + + // Progress with improved types. E.g. since we have a full Call Graph + // here, we might do better inlining. + code._iter.iterate(code); + + // TODO: + // loop unroll, peel, RCE, etc + + // Freeze field sizes; do struct layouts; convert field offsets into + // constants. + fieldSizes(code); + // Propagate field size constants + code._iter.iterate(code); + + // Throw away the Call Graph + + // The remaining passes assume all calls are unlinked; i.e. we are + // throwing away the Call Graph here. Functions only reachable from + // internal calls need to be re-hooked to stop/start less they go dead. + removeCallGraph(code); + + // To help with testing, sort StopNode Returns by NID + Arrays.sort(code._stop._inputs._es,0,code._stop.nIns(),(x,y) -> x._nid - y._nid ); + } + + // Reset Types before running the worklist algorithm + private static void resetToTop(CodeGen code, Ary<Type> oldTypes ) { + code._start.walk( x -> { + oldTypes.setX(x._nid,x._type); // Record original types for asserts + x._type = Type.TOP; // Reset all Nodes to TOP + code._iter.add(x); // Visit everybody at least once; most Nodes produce better than TOP + // Unlink all existing (conservative) linkages. + if( x instanceof CallNode call ) + call.unlink_all(); + return null; + } ); + } + + + // If wholeWorld, remove the Start inputs to functions - they are not + // called unless they get linked (hence go dead and can be removed). If + // not wholeWorld, keep only public methods (and not the std lib). + private static void unlinkStart(boolean wholeWorld, CodeGen code) { + for( FunNode fun : code._linker ) { + if( fun != null && !fun.isDead() && !funIsPublic(code,wholeWorld,fun) ) { + assert fun.in(1)==code._start; // Start always in slot 1 + fun.removeDeadPath(1); + // By same logic, remove stop->return linkage, without + // remove the (now dead) ReturnNode; it awaits in limbo + // for the opto phase to link to some valid call + code._stop._inputs.del(code._stop._inputs.find(fun.ret())); + fun.ret().delUse(code._stop); + } + } + } + + // Function is public (callable from Start directly). + // - Always true for main + // - Never true for stdlib, or anonymous functions + // - Named functions use `!wholeWorld` + private static boolean funIsPublic( CodeGen code, boolean wholeWorld, FunNode fun ) { + // Always true for main + if( fun.sig().fidx() == code._main.fidx() ) return true; + // Never true for stdlib or anonymous functions + if( fun._name == null || fun._name.startsWith("sys.") ) + return false; + // Named functions (and not stdlib) are callable if not whole-world. + return !wholeWorld; + } + + // As part of building a CallGraph, when opto finds a function ptr flowing + // into a Call, link the Call and Fun. + private static void linkCG(CodeGen code, TypeFunPtr tfp, CallNode call) { + if( tfp.nargs() != call.nargs() ) return; // Error calls hit this + for( long fidxs=tfp.fidxs(); fidxs!=0; fidxs=TypeFunPtr.nextFIDX(fidxs) ) { + int fidx = Long.numberOfTrailingZeros(fidxs); + FunNode fun = code.link(fidx); + // null here means an external function; i.e. this Call + // calls to an outside library and all its arguments escape. + if( fun != null && !call.linked(fun) ) { + call.link( fun ); + code._iter.add(fun); + code._iter.addAll(fun._outputs); + } + } + } + + // The core SCCP algorithm + private static void sccp( CodeGen code, Ary<Type> oldTypes ) { + // Iter workList is empty at this point + // OPTIMISTIC PASS + Node n; + int count = 0; // Debug counter + while( (n = code._iter._work.pop()) != null ) { + if( n.isDead() ) continue; + count++; + Type oval = n._type, nval = n.compute(); + if( oval == nval ) continue; + assert oval.isa(nval); // Types start high and always fall + Type pesiVal = oldTypes.at(n._nid); + assert nval.isa(pesiVal); // Never fall worse than the pessimistic pass + n._type = nval; + + // If a TFP adds a new function input to a call, link to the new Fun + if( nval instanceof TypeFunPtr tfp ) { + for( Node use : n._outputs ) + if( !use._type.isHigh() && use instanceof CallNode call && call.fptr() == n ) + linkCG(code,tfp,call); + } + + // Link a Call which becomes alive + if( n instanceof CallNode call && oval.isHigh() && !nval.isHigh() && call.fptr()._type instanceof TypeFunPtr ) + linkCG(code,call.tfp(),call); + + // Since n._type changed, visit all output neighbors + code._iter.addAll(n._outputs); + n.moveDepsToWorklist(code._iter); + // Quadratic (expensive) small-step assert + assert check(code); + } + } + + // Quadratic (expensive) small-step assert + private static boolean check(CodeGen code) { + code._start.walk( x -> { + Type xval = x.compute(); + assert xval == x._type || (x._type.isa( xval ) && code._iter._work.on( x )); + return null; + }); + return true; + } + + // After SCCP add everything changed to the worklist and see if peepholes + // can make more progress. + private static void moveChangesToWorklist(CodeGen code, Ary<Type> oldTypes) { + code._start.walk( x -> { + assert x.compute() == x._type; // Hit the fixed point + assert x._nid >= oldTypes._len || x._type.isa(oldTypes.at(x._nid)); // Hit at least the bottom-up type + code._iter.add(x); + return null; + }); + } + + // Freeze field sizes; do struct layouts; convert field offsets into + // constants. + private static void fieldSizes( CodeGen code ) { + for( int i=0; i<code._start.nOuts(); i++ ) { + Node use = code._start.out(i); + if( use instanceof ConFldOffNode off ) { + TypeMemPtr tmp = (TypeMemPtr) Parser.TYPES.get(off._name); + off.subsume( off.asOffset(tmp._obj) ); + i--; + } + } + } + + // The remaining passes assume all calls are unlinked; i.e. we are throwing + // away the Call Graph here. Functions only reachable from internal calls + // need to be re-hooked to stop/start less they go dead. + private static void removeCallGraph(CodeGen code) { + code._start.walk( x -> { + // Unlink all existing (conservative) linkages. + if( x instanceof CallNode call ) { + for( Node y : call._outputs ) { + // Keep function alive and hooked to Start so it gets + // codegen'd. Function is callable by this call via + // TFP, although perhaps not by any other means. + if( y instanceof FunNode fun && !(fun.in(1) instanceof StartNode) ) { + ParmNode rpc = fun.rpc(); + if( rpc==null ) // Ensure valid RPC + rpc = makeRPC(fun); + // Insert a hook to Start and Stop + fun.insertDef(1,code._start); + for( Node use : fun._outputs ) + if( use instanceof ParmNode parm ) + parm.insertDef(1,ConstantNode.make(parm._type).peephole()); + code._stop.addDef(fun.ret()); + } + } + call.unlink_all(); + } + return null; + } ); + + } + + // Make a valid Parm RPC. + // First make sure a valid RPC; single-call into multi-fun will have each + // function having a single call site, so the RPC becomes a constant and + // folds - but since multiple targets, the Call never inlines. Recreate a + // valid RPC so codegen (and Eval2) understands the calling convention. + private static ParmNode makeRPC( FunNode fun ) { + ParmNode rpc = new ParmNode("$rpc",0,fun.ret().rpc()._type,fun); + for( int i=1; i<fun.nIns(); i++ ) { + CallEndNode cend = ((CallNode)fun.in(i)).cend(); + rpc.addDef(ConstantNode.make(cend._rpc).peephole()); + } + fun.ret().setDef(3,rpc.init()); + return rpc; + } + + +} diff --git a/src/main/java/com/seaofnodes/simple/node/AddFNode.java b/src/main/java/com/seaofnodes/simple/node/AddFNode.java index 792da62e..4ad02dbb 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddFNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddFNode.java @@ -5,38 +5,25 @@ 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 public String glabel() { return "+"; } - @Override - public 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() { - 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 c5ba14de..c7fd4daa 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..7fa428c6 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ArithFNode.java @@ -0,0 +1,32 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; +import java.util.BitSet; + +public abstract class ArithFNode extends Node { + public ArithFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override + public StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append(glabel()), visited); + return sb.append(")"); + } + + 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 TypeFloat.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 96067c8e..f2beaacb 100644 --- a/src/main/java/com/seaofnodes/simple/node/ArithNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ArithNode.java @@ -35,7 +35,7 @@ public abstract class ArithNode extends Node { 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; } @@ -56,7 +56,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 a6e21ea0..d18f779b 100644 --- a/src/main/java/com/seaofnodes/simple/node/CProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CProjNode.java @@ -33,7 +33,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 d95af697..a7e50c39 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -39,16 +39,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 ) { + // 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(); // 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); @@ -72,12 +79,17 @@ 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. CFGNode idom = call; - while( !(idom instanceof FunNode) && idom!=null ) + while( true ) { 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 @@ -95,6 +107,8 @@ public class CallEndNode extends CFGNode implements MultiNode { // Bump the global version number invalidating them en-masse. CodeGen.CODE.invalidateIDepthCaches(); return this; + } else { + 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 ba08c87a..47dfdf19 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -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 3e1d3c69..c54da2c4 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java @@ -14,8 +14,8 @@ import java.util.BitSet; */ 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() { @@ -37,7 +37,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/DivFNode.java b/src/main/java/com/seaofnodes/simple/node/DivFNode.java index 633f3224..0d037a30 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivFNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivFNode.java @@ -5,29 +5,14 @@ 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 public String glabel() { return "/"; } - @Override - public 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() { - 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 4bd0fd97..2931b9ea 100644 --- a/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -80,14 +80,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 @@ -95,8 +103,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 @@ -110,8 +121,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 @@ -176,6 +189,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 c5d687e5..5d751602 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -33,6 +33,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(); @@ -57,11 +58,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 b58ea498..58dbfc81 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -34,20 +34,32 @@ public class LoadNode extends MemOpNode { @Override public Type compute() { - 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(mem._t); + t = t.join(mem._t); if( _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 19acc5b9..9ab57714 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -60,7 +60,12 @@ public class MemMergeNode extends Node { } - @Override public Type compute() { return TypeMem.BOT; } + @Override public Type compute() { + for( Node n : _inputs ) + if( n != null && !n._type.isHigh() ) + return TypeMem.BOT; + return TypeMem.TOP; + } @Override public Node idealize() { if( inProgress() ) return null; diff --git a/src/main/java/com/seaofnodes/simple/node/MinusFNode.java b/src/main/java/com/seaofnodes/simple/node/MinusFNode.java index 99fc3144..5bb0889f 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusFNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusFNode.java @@ -20,7 +20,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 f26ce37e..3ab74625 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -23,7 +23,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 6fbf4bbb..5c04af43 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulFNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulFNode.java @@ -5,29 +5,14 @@ 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 public String glabel() { return "*"; } - @Override - public 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() { - 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 1785af4e..9310aa38 100644 --- a/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.util.Utils; import java.util.BitSet; @@ -61,19 +62,27 @@ public class NewNode extends Node implements MultiNode { public TypeTuple compute() { Field[] fs = _ptr._obj._fields; Type[] ts = new Type[fs.length+2]; - ts[0] = Type.CONTROL; - ts[1] = _ptr; - for( int i=0; i<fs.length; i++ ) { - if( _ptr._obj._fields[i]._one ) { - // Once-only fields use the declared type - ts[i+2] = _ptr._obj._fields[i]._t; - } else { - // Others take from the inputs - Type mt = in(i+2)._type; - TypeMem mem = mt==Type.TOP ? TypeMem.TOP : (TypeMem)mt; - Type tfld = mem._t.meet(mem._t.makeZero()); - Type tfld2 = tfld.join(fs[i]._t ); - ts[i+2] = TypeMem.make(fs[i]._alias,tfld2); + if( in(0)._type.isHigh() ) { + ts[0] = Type.XCONTROL; + ts[1] = _ptr.makeHigh(); + for( int i=0; i<fs.length; i++ ) + ts[i+2] = Type.TOP; + } else { + ts[0] = Type.CONTROL; + ts[1] = _ptr; + for( int i=0; i<fs.length; i++ ) { + if( _ptr._obj._fields[i]._one ) { + // Once-only fields use the declared type + ts[i+2] = _ptr._obj._fields[i]._t; + } else { + // Others take from the inputs + Type mt = in(i+2)._type; + TypeMem mem = mt==Type.TOP ? TypeMem.TOP : (TypeMem)mt; + //Type tfld = mem._t.meet(mem._t.makeZero()); + Type tfld = mem._t; + Type tfld2 = tfld.join(fs[i]._t ); + ts[i+2] = TypeMem.make(fs[i]._alias,tfld2); + } } } return TypeTuple.make(ts); diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 8981ab0d..458a3407 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.Utils; @@ -204,9 +205,9 @@ public abstract class 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); } @@ -233,7 +234,7 @@ public abstract class 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)); return _outputs.isEmpty(); } @@ -482,7 +483,7 @@ public abstract class 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); @@ -549,7 +550,7 @@ public abstract class Node implements Cloneable { Ary<Node> _deps; /** - * 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. */ @@ -566,13 +567,13 @@ public abstract class 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(); } - // Two nodes are equal if they have the same inputs and the same "opcode" // which means the same Java class, plus same internal parts. @Override public final boolean equals( Object o ) { diff --git a/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/src/main/java/com/seaofnodes/simple/node/ParmNode.java index a14a4fb9..880f936c 100644 --- a/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -1,6 +1,8 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMemPtr; import java.util.BitSet; public class ParmNode extends PhiNode { @@ -39,6 +41,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 fcbacbc9..bdc0d0fa 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -14,6 +14,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; @@ -55,26 +57,43 @@ public class PhiNode extends Node { public CFGNode region() { return (CFGNode)in(0); } @Override public boolean isMem() { return _minType instanceof TypeMem; } @Override public boolean isPinned() { return true; } + 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() ) + // 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 ); + + // phi loop widening part + 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.isConstant() && (!(_type instanceof TypeInteger oldi) || newi._widen <= oldi._widen) ) + return newi.same_but_slightly_wider_than(_minType); + } + + return newt; } @Override @@ -83,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 != _minType ) { _minType = tmp2; return this; @@ -136,13 +155,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 a0394e5b..586527c8 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 2b467a8c..b115a260 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -37,7 +37,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 @@ -46,10 +46,10 @@ public class RegionNode extends CFGNode { // If a CFG diamond with no merging, delete: "if( pred ) {} else {};" if( !hasPhi() && nIns()>3 && // No Phi users, just a control user - in(1) instanceof CProjNode p1 && - in(2) instanceof CProjNode p2 && - addDep(p1.in(0))==addDep(p2.in(0)) && - p1.in(0) instanceof IfNode iff ) { + in(1) instanceof CProjNode p1 && + in(2) instanceof CProjNode p2 && + addDep(p1.in(0))==addDep(p2.in(0)) && + 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 @@ -83,16 +83,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 @@ -101,15 +106,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 @@ -130,10 +136,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; } @@ -155,7 +161,8 @@ public class RegionNode extends CFGNode { // Walk the LHS & RHS idom trees in parallel until they match, or either fails. // Because this does not cache, it can be linear in the size of the program. for( int i=1; i<nIns(); i++ ) - lca = cfg(i)._idom(lca,dep); + if( !cfg(i)._type.isHigh() ) + lca = cfg(i)._idom(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 7971733a..0aa70214 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -116,12 +116,17 @@ public class ReturnNode extends CFGNode { } @Override public Parser.ParseException err() { - return expr()._type/*mt*/==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 5fb274db..8e33512a 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -132,6 +132,8 @@ public class StoreNode extends MemOpNode { public Parser.ParseException err() { Parser.ParseException err = super.err(); if( err != null ) return err; + if( ptr()._type == Type.TOP ) + return null; // This means we have an error input, report elsewhere TypeMemPtr tmp = (TypeMemPtr)ptr()._type; if( 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 5c7e969f..3fc4f7ca 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubFNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubFNode.java @@ -5,38 +5,21 @@ 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 public String glabel() { return "-"; } - @Override - public 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() { - 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 c098ad99..e02183a0 100644 --- a/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java @@ -20,12 +20,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/NotARM.java b/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java index 027a8128..d78421ca 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/arm/NotARM.java @@ -19,7 +19,7 @@ public class NotARM extends MachConcreteNode implements MachNode{ short reg1 = enc.reg(in(1)); int subs = arm.imm_inst(arm.OP_SUBS, 0, reg1, self); enc.add4(subs); - int cset = arm.cond_set(arm.OP_CSET, 31, arm.COND.EQ, 63, reg1); + int cset = arm.cond_set(arm.OP_CSET, 31, arm.COND.EQ, 31, reg1); enc.add4(cset); } 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 01b46b8d..e1b3b3b6 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 @@ -20,6 +20,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 = arm.cset(arm.OP_CSET,0b11111, arm.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 9dbf724d..a5dac751 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 @@ -216,7 +216,9 @@ public class arm extends Machine { assert 0 <= rm && rm < 32; assert 0 <= rn && rn < 32; assert 0 <= rd && rd < 32; - return (opcode << 21) | (rm << 15) | (cond.ordinal() << 12) | (rn << 5) | rd; + // Is one of the standard conditions, excluding AL and NV, encoded in the "cond" field with its least significant bit inverted. + int actualCond = cond.ordinal() ^ 1; + return (opcode << 21) | (rm << 16) | (actualCond << 12) | (0b01 << 10) | (rn << 5) | rd; } static public int cset(int opcode, COND cond, int rn, int rd) { @@ -563,29 +565,6 @@ public class arm extends Machine { return (opcode << 26) | delta; } - @Override public RegMask callArgMask(TypeFunPtr tfp, int idx, int maxArgSlot ) { return callInMask(tfp,idx,maxArgSlot); } - static RegMask callInMask(TypeFunPtr tfp, int idx, int maxArgSlot ) { - if( idx==0 ) return CodeGen.CODE._rpcMask; - if( idx==1 ) return null; - // Count floats in signature up to index - if( idx-2 >= tfp.nargs() ) return null; // Anti-dependence - // Count floats in signature up to index - int fcnt=0; - for( int i=2; i<idx; i++ ) - if( tfp.arg(i-2) instanceof TypeFloat) - fcnt++; - // Floats up to XMMS in XMM registers - if( tfp.arg(idx-2) instanceof TypeFloat ) { - if( fcnt < XMMS.length ) - return XMMS[fcnt]; - } else { - RegMask[] cargs = CALLINMASK; - if( idx-2-fcnt < cargs.length ) - return cargs[idx-2-fcnt]; - } - throw Utils.TODO(); // Pass on stack slot - } - public static long decodeImm12(int imm12) { int immr = (imm12 >> 6) & 0x3F; int imms = imm12 & 0x3F; @@ -609,6 +588,31 @@ public class arm extends Machine { return val; } + @Override public RegMask callArgMask(TypeFunPtr tfp, int idx, int maxArgSlot ) { return callInMask(tfp,idx,maxArgSlot); } + static RegMask callInMask(TypeFunPtr tfp, int idx, int maxArgSlot ) { + if( idx==0 ) return CodeGen.CODE._rpcMask; + if( idx==1 ) return null; + // Count floats in signature up to index + if( idx-2 >= tfp.nargs() ) return null; // Anti-dependence + // Count floats in signature up to index + int fcnt=0; + for( int i=2; i<idx; i++ ) + if( tfp.arg(i-2) instanceof TypeFloat) + fcnt++; + // Floats up to XMMS in XMM registers + if( tfp.arg(idx-2) instanceof TypeFloat ) { + if( fcnt < XMMS.length ) + return XMMS[fcnt]; + } else { + RegMask[] cargs = CALLINMASK; + if( idx-2-fcnt < cargs.length ) + return cargs[idx-2-fcnt]; + } + // 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 @Override public short maxArgSlot( TypeFunPtr tfp ) { int icnt=0, fcnt=0; // Count of ints, floats @@ -691,7 +695,7 @@ public class arm extends Machine { private Node cmp(BoolNode bool){ Node cmp = _cmp(bool); - return new SetARM(cmp, IfNode.negate(bool.op())); + return new SetARM(cmp, bool.op()); } private Node _cmp(BoolNode bool) { if( bool.isFloat() ) 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 93c90052..b9e6e5ba 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 @@ -49,6 +49,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 0eff2afe..177e35ab 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 @@ -35,6 +35,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(); }); enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, 0, dst)); diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index b7a8408e..2d5a6d04 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -316,7 +316,8 @@ public class Type /*implements Cloneable*/ { } // True if this "isa" t; e.g. 17 isa TypeInteger.BOT - public boolean isa( Type t ) { return meet(t)==t; } + // Applies for pessimistic case + public boolean isa( Type t ) { return meet(t)==t; } // True if this "isa" t up to named structures public boolean shallowISA( Type t ) { return isa(t); } @@ -329,6 +330,9 @@ public class Type /*implements Cloneable*/ { // Is forward-reference public boolean isFRef() { return false; } + // Cap at limits + public Type oob() { return isHigh() ? TOP : BOTTOM; } + // ---------------------------------------------------------- // Cyclic types! Flag the start of a cyclic type by putting a sentinel in @@ -477,6 +481,7 @@ public class Type /*implements Cloneable*/ { Type _glb(boolean mem) { assert is_simple(); return Type.BOTTOM; } Type _close() { return this; } + public Type widen() { return this; } // ---------------------------------------------------------- diff --git a/src/main/java/com/seaofnodes/simple/type/TypeConAry.java b/src/main/java/com/seaofnodes/simple/type/TypeConAry.java index d4003f87..c5543030 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeConAry.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeConAry.java @@ -51,6 +51,8 @@ public class TypeConAry<A> extends Type { @Override public boolean isHigh() { return this==TOP; } @Override boolean _isConstant() { return true; } + @Override Type _glb(boolean mem) { return this; } + @Override boolean _isGLB(boolean mem) { return true; } // Meet-over-elements type public Type elem() { diff --git a/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java b/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java index fd2b2635..9e5f0a2d 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java @@ -15,7 +15,7 @@ public class TypeConAryB extends TypeConAry<byte[]> { @Override public int len() { return _ary.length; } @Override public int log_size() { return 0; } @Override public String str() { return "[\""+new String(_ary)+"\"]"; } - @Override boolean eq(Type t) { return Arrays.equals(_ary,((TypeConAryB)t)._ary); } + @Override boolean eq(Type t) { return t instanceof TypeConAryB ary && Arrays.equals(_ary,ary._ary); } @Override int hash() { return Arrays.hashCode(_ary); } @Override public void write( ByteArrayOutputStream baos ) { baos.write(_ary,0,_ary.length); } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java b/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java index 924e3d73..8228887e 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java @@ -12,6 +12,6 @@ public class TypeConAryI extends TypeConAry<int[]> { @Override public int len() { return _ary.length; } @Override public int log_size() { return 2; } @Override public String str() { return "[i32]"; } - @Override boolean eq(Type t) { return Arrays.equals(_ary,((TypeConAryI)t)._ary); } + @Override boolean eq(Type t) { return t instanceof TypeConAryI ary && Arrays.equals(_ary,ary._ary); } @Override int hash() { return Arrays.hashCode(_ary); } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java index b21dd451..ddef9651 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java @@ -158,8 +158,13 @@ public class TypeFunPtr extends TypeNil { public Type ret() { return _ret; } public int nargs() { return _sig.length; } public int fidx() { assert Long.bitCount(_fidxs)==1; return Long.numberOfTrailingZeros(_fidxs); } + public int nfcns() { + if( _fidxs < 0 ) return Integer.MAX_VALUE; // Infinite choices + return Long.bitCount(_fidxs); + } + // Used to walk over type structures @Override int nkids() { return _sig.length+1; } @Override Type at( int idx ) { return idx == _sig.length ? _ret : _sig[idx]; @@ -235,7 +240,7 @@ public class TypeFunPtr extends TypeNil { return tilde+fidx; } - // Usage: for( long fidxs=fidxs(); fidxs!=0; fidxs=nextFIDX(fidxs) { int fidxs = Long.numberOfTrailingZeros(fidxs); ... } + // Usage: for( long fidxs=fidxs(); fidxs!=0; fidxs=nextFIDX(fidxs) ) { int fidx = Long.numberOfTrailingZeros(fidxs); ... } public static long nextFIDX(long fidxs) { return fidxs & (fidxs-1); } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 99f237a9..97c17a34 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -18,24 +18,49 @@ public class TypeInteger extends Type { */ public long _min, _max; + public byte _widen; + private static final Ary<TypeInteger> FREE = new Ary<>(TypeInteger.class); - private TypeInteger(long min, long max) { super(TINT); init(min,max); } - private TypeInteger init(long min, long max) { _min = min; _max = max; return this; } - public static TypeInteger malloc(long lo, long hi) { return FREE.isEmpty() ? new TypeInteger(lo,hi) : FREE.pop().init(lo,hi); } - public static TypeInteger make(long lo, long hi) { - TypeInteger i = malloc(lo,hi); + private TypeInteger(long min, long max, byte widen) { super(TINT); init(min,max,widen); } + private TypeInteger init(long min, long max, byte widen) { + // Constants must always have a widen value of zero. Widening is only + // meaningful for ranges of values - which otherwide can increase in + // range size indefinitely. + assert min!=max || widen==0; // Constants always zero widen + _min = min; _max = max; _widen=widen; + return this; + } + public static TypeInteger malloc(long lo, long hi, byte widen) { return FREE.isEmpty() ? new TypeInteger(lo,hi,widen) : FREE.pop().init(lo,hi,widen); } + public static TypeInteger make(long lo, long hi) { return make(lo,hi,(byte)0); } + public static TypeInteger make(long lo, long hi, byte widen) { + TypeInteger i = malloc(lo,hi,lo==hi ? 0 : widen); TypeInteger t2 = i.intern(); return t2==i ? i : t2.free(i); } + public TypeInteger makeWide(byte widen) { + if( widen == _widen ) return this; + if( _min == Long.MIN_VALUE && _max == Long.MAX_VALUE ) + return TypeInteger.BOT; + if( _min==_max ) return this; // Leave constants always narrow + return make(_min,_max,widen); + } @Override TypeInteger free(Type t) { TypeInteger i = (TypeInteger)t; i._min = i._max = 0; + i._widen = 0; i._hash = 0; i._dual = null; FREE.push(i); return this; } + public Type same_but_slightly_wider_than( Type minType ) { + return _widen < 3 ? make(_min,_max, (byte)(_widen+1)) : minType; + } + // Force max widen + @Override public Type widen() { + return _widen==3 ? this : make(_min,_max,(byte)3); + } public static TypeInteger constant(long con) { return make(con, con); } public final static TypeInteger ZERO= make(0,0); @@ -43,20 +68,22 @@ public class TypeInteger extends Type { public final static TypeInteger TRUE= make(1,1); public final static TypeInteger TWO = make(2,2); // Shows up in some Simple tests as the starting argument - public final static TypeInteger I1 = make(-1,0); - public final static TypeInteger I8 = make(-128,127); - public final static TypeInteger I16 = make(-32768,32767); - public final static TypeInteger I32 = make(-1L<<31,(1L<<31)-1); - public final static TypeInteger BOT = make(Long.MIN_VALUE,Long.MAX_VALUE); + public final static TypeInteger I1 = make(-1,0,(byte)3); + public final static TypeInteger I8 = make(-128,127,(byte)3); + public final static TypeInteger I16 = make(-32768,32767,(byte)3); + public final static TypeInteger I32 = make(-1L<<31,(1L<<31)-1,(byte)3); + public final static TypeInteger BOT = make(Long.MIN_VALUE,Long.MAX_VALUE,(byte)3); public final static TypeInteger TOP = (TypeInteger)BOT.dual(); - public final static TypeInteger U1 = make(0,1); + public final static TypeInteger U1 = make(0,1,(byte)3); public final static TypeInteger BOOL= U1; - public final static TypeInteger U8 = make(0,255); - public final static TypeInteger U16 = make(0,65535); - public final static TypeInteger U32 = make(0,(1L<<32)-1); + public final static TypeInteger U8 = make(0,255,(byte)3); + public final static TypeInteger U16 = make(0,65535,(byte)3); + public final static TypeInteger U32 = make(0,(1L<<32)-1,(byte)3); + + public final static TypeInteger FATBOOL = make(0,1,(byte)2); - public static void gather(ArrayList<Type> ts) { ts.add(I32); ts.add(BOT); ts.add(U1); ts.add(I1); ts.add(U8); } + public static void gather(ArrayList<Type> ts) { ts.add(I32); ts.add(BOT); ts.add(U1); ts.add(I1); ts.add(U8); ts.add(ZERO); ts.add(FATBOOL); } @Override public String str() { if( _isConstant() ) return ""+_min; @@ -95,6 +122,7 @@ public class TypeInteger extends Type { else if (-0xFFFFFFFFL <= _min && _min <= 0xFFFFFFFFL) return 2; else return 3; } + if( -128 <= _min && _max < 128 ) return 0; // 1 byte throw Utils.TODO(); } @@ -122,11 +150,11 @@ public class TypeInteger extends Type { if( other instanceof TypeConAry ary ) return ary.imeet(this); // Invariant from caller: 'this' != 'other' and same class (TypeInteger) TypeInteger i = (TypeInteger)other; // Contract - return make(Math.min(_min,i._min), Math.max(_max,i._max)); + return make(Math.min(_min,i._min), Math.max(_max,i._max), (byte)Math.max(_widen,i._widen)); } @Override TypeInteger xdual() { - return _min==_max ? this : malloc(_max,_min); + return _min==_max ? this : malloc(_max,_min,(byte)(-_widen)); } @Override public TypeInteger nonZero() { @@ -146,8 +174,8 @@ public class TypeInteger extends Type { return isHigh() ? dual() : this; } - @Override int hash() { return Utils.fold(_min) * Utils.fold(_max); } + @Override int hash() { return Utils.fold(_min) * Utils.fold(_max) + _widen; } @Override public boolean eq( Type t ) { - return t instanceof TypeInteger i && _min==i._min && _max==i._max; + return t instanceof TypeInteger i && _min==i._min && _max==i._max && _widen==i._widen; } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index 6041155d..689b73ce 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -61,6 +61,7 @@ public class TypeMemPtr extends TypeNil { public TypeMemPtr makeFrom(TypeStruct obj) { return obj==_obj ? this : make(_nil, obj, _one); } public TypeMemPtr makeNullable() { return makeFrom((byte)3); } @Override TypeMemPtr makeFrom(byte nil) { return nil==_nil ? this : make(nil, _obj, _one); } + public TypeMemPtr makeHigh() { return make((byte)0,_obj.makeHigh(),false); } // An abstract pointer, pointing to either a Struct or an Array. // Can also be null or not, so 4 choices {TOP,BOT} x {nil,not} diff --git a/src/main/java/com/seaofnodes/simple/type/TypeRPC.java b/src/main/java/com/seaofnodes/simple/type/TypeRPC.java index bd5e2923..a1389540 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeRPC.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeRPC.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.type; +import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.SB; import com.seaofnodes.simple.util.Utils; import java.util.ArrayList; @@ -13,19 +14,31 @@ public class TypeRPC extends Type { // A set of CallEndNode IDs (or StopNode); commonly just one. // Basically a sparse bit set - final HashSet<Integer> _rpcs; + HashSet<Integer> _rpcs; // If true, invert the meaning of the bits - final boolean _any; + boolean _any; - private TypeRPC(boolean any, HashSet<Integer> rpcs) { - super(TRPC); - _any = any; - _rpcs = rpcs; + private static final Ary<TypeRPC> FREE = new Ary<>(TypeRPC.class); + private TypeRPC init(boolean any, HashSet<Integer> rpcs) { _any=any; _rpcs=rpcs; return this; } + private TypeRPC() { super(TRPC); } + private static TypeRPC malloc(boolean any, HashSet<Integer> rpcs) { + return (FREE.isEmpty() ? new TypeRPC() : FREE.pop()).init(any,rpcs); } private static TypeRPC make(boolean any, HashSet<Integer> rpcs) { - return new TypeRPC(any,rpcs).intern(); + TypeRPC rpc = (FREE.isEmpty() ? new TypeRPC() : FREE.pop()).init(any,rpcs); + TypeRPC t2 = rpc.intern(); + return t2==rpc ? rpc : t2.free(rpc); } + @Override TypeRPC free(Type t) { + TypeRPC rpc = (TypeRPC)t; + rpc._rpcs = null; + rpc._dual = null; + rpc._hash = 0; + FREE.push(rpc); + return this; + } + @Override boolean isFree() { return _rpcs==null; } public static TypeRPC constant(int cend) { HashSet<Integer> rpcs = new HashSet<>(); @@ -82,8 +95,7 @@ public class TypeRPC extends Type { return make(any,rpcs); } - @Override - Type xdual() { return new TypeRPC(!_any,_rpcs); } + @Override Type xdual() { return malloc(!_any,_rpcs); } @Override boolean _isConstant() { return !_any && _rpcs.size()==1; } @Override boolean _isGLB(boolean mem) { return true; } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 73fecdab..1cabbe32 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -68,6 +68,12 @@ public class TypeStruct extends Type { Field.make("#" ,len , lenAlias,true ,false), Field.make("[]",body,bodyAlias,efinal,false)); } + public TypeStruct makeHigh() { + Field[] fs = new Field[_fields.length]; + for( int i=0; i<_fields.length; i++ ) + fs[i] = _fields[i].makeFrom(Type.TOP); + return make(_name,false,fs); + } public TypeStruct add( Field f ) { assert _open && find(f._fname)==-1; // No double field names |