diff options
| author | Cliff Click <cliffc@acm.org> | 2025-06-13 15:42:08 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-10-24 15:56:44 -0700 |
| commit | f5f0580331b4e29a0a0dc43d9885dfe0f0aed865 (patch) | |
| tree | a983bd53ce8173b21380f0b3bf06d88d845ae861 /src/main/java/com | |
| parent | b59f51486393b2fae7b0015bc5099c5514c7335a (diff) | |
| download | Simple-f5f0580331b4e29a0a0dc43d9885dfe0f0aed865.tar.gz Simple-f5f0580331b4e29a0a0dc43d9885dfe0f0aed865.zip | |
Chapter 25: SSA Before Types Are Known
Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Symious <14933944+symious@users.noreply.github.com>
Co-authored-by: Jun Kawasaki <jun784@gmail.com>
Co-authored-by: Hadházy Tamás <helsgithub15@gmail.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>
Diffstat (limited to 'src/main/java/com')
67 files changed, 1238 insertions, 359 deletions
diff --git a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java index a3b66e09..2fe4e172 100644 --- a/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -206,7 +206,7 @@ public class IterPeeps { * True if Node is on the WorkList */ public boolean on( E x ) { return _on.get(x._nid); } - boolean isEmpty() { return _len==0; } + public boolean isEmpty() { return _len==0; } /** * Removes a random Node from the WorkList; null if WorkList is empty diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 81c7be32..56233250 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -228,7 +228,7 @@ public class Parser { RegionNode r = new RegionNode( null,null,null).init(); assert r.inProgress(); PhiNode rmem = new BulkMemPhiNode(ScopeNode.MEM0,r,null).init(); - PhiNode rrez = new PhiNode(ScopeNode.ARG0,Type.BOTTOM,r,null).init(); + PhiNode rrez = new PhiNode(ScopeNode.ARG0,r,null).init(); ReturnNode ret = new ReturnNode(r, rmem, rrez, rpc, fun).init(); fun.setRet(ret); assert ret.inProgress(); @@ -617,7 +617,7 @@ public class Parser { // Merge results RegionNode r = ctrl(tScope.mergeScopes(fScope,loc())); - Node ret = peep(new PhiNode("",lhs._type.meet(rhs._type).glb(false),r,lhs.unkeep(),rhs.unkeep())); + Node ret = peep(new PhiNode("",r,lhs.unkeep(),rhs.unkeep())); // Immediately fail e.g. `arg ? 7 : ptr` ParseException err; if( !fside.equals("else") && (err=ret.err()) !=null ) throw err; @@ -664,7 +664,8 @@ public class Parser { // Else safety check for accessing fields out of function scope. if( instance(def) ) { pos(old_pre_equals); // setup for `self.name = expr` - Node self = _scope.in(_scope.lookup("self")); // Insert self reference + Var selfVar = _scope.lookup("self"); + Node self = liftExpr(_scope.in(selfVar),selfVar.type(),true); return parsePostfixName(self,name); } @@ -690,33 +691,16 @@ public class Parser { // Apply declared access permissions; widen floats and narrow integers. // Early error if types do not match variable. - private Node liftExpr( Node expr, Type t, boolean isLoad ) { - if( expr._type instanceof TypeMemPtr tmp && TYPES.get(tmp._obj._name).isFRef() ) - throw error("Must define forward ref "+tmp._obj._name); - // Read-only access is deep; a fixed binding alone does not remove access. - if( t instanceof TypeMemPtr tmp && tmp.isFinal() ) { + private Node liftExpr(Node expr, Type t, boolean isLoad) { + if( t==Type.BOTTOM || t==Type.TOP ) return expr; + // Constructor sentinels record missing initialization, not a value + // needing conversion. Keep them visible to the completion check. + if( expr instanceof ConstantNode && !(expr instanceof FRefNode) && + (expr._type==Type.TOP || expr._type==Type.BOTTOM) ) return expr; + if( t instanceof TypeMemPtr tmp && tmp.isFinal() ) expr = peep(new ReadOnlyNode(expr)); - } - if( !expr._type.accessISA(t) ) - throw error("Type " + expr._type.str() + " is not of declared type " + t.str()); - // Auto-widen array to i64 (cast ptr to raw int bits) - if( t == TypeInteger.BOT && expr._type instanceof TypeMemPtr tmp && tmp._obj.isAry() ) - expr = peep(new AddNode(peep(new CastNode(t,ctrl(),expr)),off(tmp._obj,"[]"))); - // Auto-widen int to float - expr = widenInt( expr, t ); - // Auto-narrow wide ints to narrow ints. For loads, emit code to force - // the loaded value to match the declared sign/zero bits. For stores, - // just force the type, acting "as if" the store silently truncates. - if( expr._type instanceof TypeFloat && t instanceof TypeInteger ) - expr = peep(new ToIntegerNode(expr)); - Type et = expr._type; - if( isLoad ) { expr = zsMask(expr,t); et = expr._type; } - else if( et instanceof TypeInteger && t instanceof TypeInteger ) et=t; - - // Type is sane - if( et!=Type.BOTTOM && (!et.shallowISA(t) || !et.accessISA(t)) ) - expr = peep(new CastNode(t.isConstant() ? t : t.widen(),null,expr)); - return expr; + if( expr instanceof FunPtrNode && t instanceof TypeFunPtr ) return expr; + return peep(new ConvertNode(t,expr)); } private Node widenInt( Node expr, Type t ) { @@ -828,8 +812,6 @@ 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.widen(),null,lift)); // Define a new name if( !_scope.define(name,t,xfinal || fld_final,lift, loc) ) throw error("Redefining name '" + name + "'", loc); @@ -1083,7 +1065,7 @@ public class Parser { else if( !match("!=") ) break; lhs.keep(); Node rhs = parseComparison(); - lhs = peep(new BoolNode.EQ(lhs.unkeep(),rhs).widen()); + lhs = peep(new BoolNode.EQ(lhs.unkeep(),rhs)); if( !eq ) lhs = peep(new NotNode(lhs)); } return lhs; @@ -1149,7 +1131,7 @@ public class Parser { ctrl(ifT.unkeep()); RegionNode r = fail.mergeScopes(_scope, loc()).init(); _scope = fail; - return new PhiNode("",TypeInteger.BOOL,r,con(0),con(1)).peephole(); + return new PhiNode("", r,con(0),con(1)).peephole(); } private int parseCompDir() { @@ -1164,7 +1146,7 @@ public class Parser { if( Math.abs(dir)==2 ) { Node tmp=lhs; lhs=rhs; rhs=tmp; } Node cmp = dir < 0 ? new BoolNode.LE(lhs,rhs) : new BoolNode.LT(lhs,rhs); - return peep(cmp.widen()); + return peep(cmp); } /** @@ -1187,7 +1169,7 @@ public class Parser { ParseException err; if( (err=lhs.err()) != null ) throw err; - lhs = peep(lhs.widen()); + lhs = peep(lhs); } return lhs; } @@ -1208,7 +1190,7 @@ public class Parser { else if( match("-") ) lhs = new SubNode(lhs,null); else break; lhs.setDef(2,parseMultiplication()); - lhs = peep(lhs.widen()); + lhs = peep(lhs); } return lhs; } @@ -1229,7 +1211,7 @@ public class Parser { else if( match("/") ) lhs = new DivNode(lhs,null); else break; lhs.setDef(2,parseUnary()); - lhs = peep(lhs.widen()); + lhs = peep(lhs); } return lhs; } @@ -1253,9 +1235,7 @@ public class Parser { if( n != null && !(n.type() instanceof TypeMemPtr) ) { if( n._final ) throw error("Cannot reassign final '"+n._name+"'"); - Node expr = n.type() instanceof TypeFloat - ? peep(new AddFNode(_scope.in(n),con(TypeFloat.constant(delta)))) - : zsMask(peep(new AddNode(_scope.in(n),con(delta))),n.type()); + Node expr = liftExpr(peep(new AddNode(_scope.in(n),con(delta))),n.type(),true); _scope.update(n,expr); return expr; } @@ -1263,7 +1243,7 @@ public class Parser { // Reset, try again pos(old); } - if (match("-")) return peep(new MinusNode(parseUnary()).widen()); + if (match("-")) return peep(new MinusNode(parseUnary())); if (match("!")) return peep(new NotNode(parseUnary())); // Else be a primary expression return parsePrimary(); @@ -1325,13 +1305,18 @@ public class Parser { // If a method var, allow nested blocks and methods, but not fcns or other structs. // Else safety check for accessing fields out of function scope. if( instance(var) ) { - Node self = _scope.in(_scope.lookup("self")); // Insert self reference + Var selfVar = _scope.lookup("self"); + Node self = liftExpr(_scope.in(selfVar),selfVar.type(),true); return parsePostfixName(self,id); } // Load local value - Node rvalue = _scope.in(var); - if( rvalue._type == Type.BOTTOM ) + Node oldValue = _scope.in(var); + if( oldValue instanceof ConstantNode && !(oldValue instanceof FRefNode) && oldValue._type==Type.BOTTOM ) + throw error("Cannot read uninitialized field '"+id+"'"); + Node rvalue = liftExpr(oldValue,var.type(),true); + if( rvalue!=oldValue ) _scope.update(var,rvalue); + if( rvalue instanceof ConstantNode && rvalue._type == Type.BOTTOM ) if( rvalue instanceof FRefNode ) return parsePostfix(rvalue); else throw error("Cannot read uninitialized field '"+id+"'"); @@ -1407,7 +1392,7 @@ public class Parser { }; // Convert to float ops, or narrow int types; error if not declared type. // Also, if postfix LHS is still keep() - return liftExpr(peep(op.widen()),t,true); + return liftExpr(peep(op),t,true); } @@ -1458,7 +1443,7 @@ public class Parser { } // Check that all fields are initialized for( int i=idx; i<init.size(); i++ ) - if( init.at(i)._type == Type.TOP || init.at(i)._type == Type.BOTTOM ) + if( missingInit(init.at(i),new java.util.BitSet()) ) throw error("'"+tmp._obj._name+"' is not fully initialized, field '" + fs[i-idx]._fname + "' needs to be set in a constructor"); Node ptr = newStruct(tmp._obj, off(tmp._obj, " len"), idx, init ); if( hasConstructor ) @@ -1466,6 +1451,20 @@ public class Parser { return ptr; } + // The old constructor model requires each field on every path. An + // unresolved expression also has BOTTOM now, so inspect the actual + // sentinel and merges instead of mistaking an unknown type for no write. + private boolean missingInit(Node n, java.util.BitSet visit) { + if( n==null || visit.get(n._nid) || n instanceof FRefNode ) return false; + visit.set(n._nid); + if( n instanceof ConstantNode ) return n._type==Type.BOTTOM || n._type==Type.TOP; + if( n instanceof ConvertNode || n instanceof ReadOnlyNode ) return missingInit(n.in(1),visit); + if( n instanceof PhiNode phi ) + for( int i=1; i<n.nIns(); i++ ) + if( phi.region().in(i)!=null && phi.region().in(i)._type!=Type.XCONTROL && missingInit(n.in(i),visit) ) return true; + return false; + } + /** * Return a NewNode initialized memory. @@ -1581,14 +1580,15 @@ public class Parser { // Sanity check expr for being a reference if( !(expr._type instanceof TypeMemPtr ptr) ) - throw error( "Expected "+(name=="#" || name=="[]" ? "array" : "reference")+" but found " + expr._type.str() ); + return parseUnknownField(expr,name); // Find the field from the Type. Lookup in the base object field names. TypeMemPtr ptr2 = (TypeMemPtr)TYPES.get(ptr._obj._name); if( !ptr._obj.isAry() ) - ptr = ptr.makeFrom((TypeStruct)ptr._obj.join(ptr2._obj)); // Resolve the shape, retaining access. + ptr = ptr.makeFrom(ptr2._obj); // The declaration fixes the field shape; retain this view's access. TypeStruct base = ptr._obj; int fidx = base.find(name); + if( fidx==-1 && base._open ) return parseUnknownField(expr,name); if( fidx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); @@ -1620,7 +1620,7 @@ public class Parser { // Load field Node load = f._one && INITS.containsKey( base._name ) ? INITS.get(base._name).in(base.find(name)) - : new LoadNode(loc(),name, f._alias, tf, mem(), expr, off); + : new LoadNode(loc(),name, f._alias, mem(), expr, off); // Arrays include control, as a proxy for a safety range check // Structs don't need this; they only need a NPE check which is // done via the type system. @@ -1641,7 +1641,7 @@ public class Parser { // Method call: Loaded a function from a named field, AND the base // field type is final. if( load._type instanceof TypeFunPtr && name!="[]" && - !(load instanceof ExternNode) && + _code.externFunc((TypeFunPtr)load._type)==null && ((TypeMemPtr)TYPES.get(base._name))._obj.field(name)._final && // And calling a function match("(") ) { @@ -1658,6 +1658,52 @@ public class Parser { } + // Syntax fixes the access even when a forward definition or a loop + // leaves the receiver untyped. Resolve its alias and layout in the graph. + private Node parseUnknownField(Node expr, String name) { + expr.keep(); + Node off = new FldOffNode(expr,name).peephole(); + if( name.equals("[]") ) { + Node index = require(parseAsgn(),"]"); + Node scale = new FldOffNode(expr,"<<").peephole(); + off = peep(new AddNode(off,peep(new ShlNode(loc(),index,scale)))); + } + off.keep(); + if( matchOpx('=','=') ) { + Node value = parseAsgn().keep(); + Node st = new StoreNode(loc(),name,1,Type.BOTTOM,mem(),expr,off,value,false); + st.setDef(0,ctrl()); + mem(st.peephole()); + expr.unkill(); + off.unkill(); + return value.unkeep(); + } + Node load = new LoadNode(loc(),name,1,mem(),expr,off); + load.setDef(0,ctrl()); + load = peep(load); + char ch = _lexer.matchOperAssign(); + if( ch!=0 ) { + Node op = opAssign(ch,load,Type.BOTTOM).keep(); + Node st = new StoreNode(loc(),name,1,Type.BOTTOM,mem(),expr,off,op,false); + st.setDef(0,ctrl()); + mem(st.peephole()); + // The field width is not known yet. A compound assignment returns + // the stored value after conversion; postfix returns the old load. + // Reading our own Store folds once its alias and width are known. + if( postfix(ch) ) load.unkeep(); + else { + load = new LoadNode(loc(),name,1,mem(),expr,off); + load.setDef(0,ctrl()); + load = peep(load); + } + load.keep(); + op.unkill(); + } else load.keep(); + expr.unkill(); + off.unkill(); + return parsePostfix(load.unkeep()); + } + // zero/sign extend. "i" is limited to either classic unsigned (min==0) or // classic signed (min=minus-power-of-2); max=power-of-2-minus-1. private Node zsMask(Node val, Type t ) { @@ -1729,7 +1775,7 @@ public class Parser { private Node functionCall(Node fcn, Node self) { if( fcn._type == Type.NIL ) throw error("Calling a null function pointer"); - if( !(fcn instanceof FRefNode) && !fcn._type.isa(TypeFunPtr.BOT) ) + if( !(fcn instanceof FRefNode) && fcn._type!=Type.BOTTOM && fcn._type!=TypeScalar.BOT && !fcn._type.isa(TypeFunPtr.BOT) ) throw error("Expected a function but got "+fcn._type.glb(false).str()); fcn.keep(); // Keep while parsing args @@ -1915,6 +1961,10 @@ public class Parser { // Tracks current position in input buffer private int _position = 0; + public boolean before(Lexer that) { + return that!=null && _input==that._input && _position<that._position; + } + // private int _line_number = 1; // Start of current line diff --git a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index af670bda..b79eb73d 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -202,6 +202,15 @@ public class CodeGen { public CodeGen parse() { return phase(Phase.Parse, _phase==null, () -> { P.parse(); + // Close the declarations as a group before replacing old forward + // shapes in the graph. A can mention B before B mentions A; both + // must use the same complete cycle, including through functions. + HashMap<String,Type> closed = new HashMap<>(); + for( var entry : Parser.TYPES.entrySet() ) + if( entry.getValue() instanceof TypeMemPtr ptr && !ptr._obj._open ) + closed.put(entry.getKey(),ptr.makeFrom(ptr._obj.close(Parser.TYPES))); + Parser.TYPES.putAll(closed); + _start.walk(n -> { n.upgradeType(Parser.TYPES); return null; }); }); } diff --git a/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java b/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java index e8e87785..5a91cf9f 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java +++ b/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java @@ -65,7 +65,7 @@ class InstSelect { } // Produce a machine node from n; map it to flag as done so stops cycles. - map.put(n, x=_code._mach.instSelect(n) ); + map.put(n, x=select(n) ); // Stop retains the callable body. Its lifetime edge is not a machine operand. if( n instanceof FunPtrNode ) x._inputs.pop(); // Walk machine op and replace inputs with mapped inputs @@ -87,4 +87,25 @@ class InstSelect { } } + + private Node select(Node n) { + if( n instanceof GuardNode guard ) return new GuardMach(guard); + if( n instanceof PtrToIntNode ptr ) return new PtrToIntMach(ptr); + Node op = n; + if( n instanceof ModeNode mode && mode.mode()==2 ) { + // Adapt to the existing CPU selectors. As with machine expansion, + // copy inputs without adding uses to the old graph; _instOuts + // rebuilds reverse edges after selection has finished. + op = switch(n) { + case AddNode add -> new AddFNode(add); + case SubNode sub -> new SubFNode(sub); + case MulNode mul -> new MulFNode(mul); + case DivNode div -> new DivFNode(div); + case MinusNode neg -> new MinusFNode(neg); + default -> n; + }; + op._type = n._type; + } + return _code._mach.instSelect(op); + } } diff --git a/src/main/java/com/seaofnodes/simple/codegen/Machine.java b/src/main/java/com/seaofnodes/simple/codegen/Machine.java index a95faefc..7ca465ba 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Machine.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Machine.java @@ -99,8 +99,9 @@ Pre-alloc Post-Alloc SP+48 RPC // Simple functions already return canonical full-width integer values. protected static TypeInteger cReturn(ProjNode prj) { if( prj._idx==2 && prj.in(0) instanceof CallEndNode cend && - cend.call().fptr() instanceof ExternNode ext && - ((TypeFunPtr)ext._con).ret() instanceof TypeInteger ret && ret.log_size()<3 ) + cend.call().fptr()._type instanceof TypeFunPtr tfp && + CodeGen.CODE.externFunc(tfp)!=null && + tfp.ret() instanceof TypeInteger ret && ret.log_size()<3 ) return ret; return null; } diff --git a/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/src/main/java/com/seaofnodes/simple/codegen/Opto.java index 9f07c1d1..c78e732e 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -4,6 +4,7 @@ import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; +import java.util.BitSet; // Optimistic Algorithm abstract public class Opto { @@ -50,6 +51,8 @@ abstract public class Opto { // OPTIMISTIC INTERPROCEDURAL SCCP sccp(code, oldTypes); + resolveNumericModes(code); + if( !code._iter._work.isEmpty() ) sccp(code, oldTypes); // After SCCP add everything changed to the worklist and see if // peepholes can make more progress. @@ -179,4 +182,63 @@ abstract public class Opto { }); } + // Resolve arithmetic modes which are ambiguous only because they belong to + // a recursive component. Float wins because integer operands can be + // converted to float. + private static void resolveNumericModes(CodeGen code) { + final BitSet visited = new BitSet(); + code._stop.walk(n -> { + if( n instanceof ModeNode modeNode && modeNode.mode()==0 ) { + visited.clear(); + visited.set(n._nid); // Inspect inputs, not Bool's integer result + int mode = 0; + for( int i=1; i<n.nIns(); i++ ) + mode |= numericEvidence(n.in(i),visited); + // A closed recursive numeric component can have no remaining + // concrete evidence after SCCP, e.g. dead all-integer loops. + // With no float evidence, settle to integer. + if( mode == 0 ) + mode = 1; + if( mode != 0 ) { + // If both evidence, FP wins + modeNode.setMode((byte)((mode&2)==2 ? 2 : 1)); + code.add(n); + code.addAll(n.outs()); + } + } + return null; + }); + } + + // Gather numeric evidence through Phi and interprocedural return cycles. + // The visited set makes self- and mutually-recursive calls finite. + private static int numericEvidence(Node n, BitSet visited) { + if( n == null ) return 0; + if( visited.get(n._nid) ) return 0; + visited.set(n._nid); + + Type t = n._type; + if( t instanceof TypeFloat ) return 2; + if( t instanceof TypeInteger ) return 1; + if( t!=Type.BOTTOM && !(t instanceof TypeTuple) ) + return 0; // Something unrelated, like a ptr + + int evidence = 0; + assert !(n instanceof ConvertNode); // No test case + switch( n ) { + case ModeNode modeNode when modeNode.mode() != 0 -> { return modeNode.mode(); } + case ModeNode modeNode -> {} + case PhiNode phi -> {} + case ReturnNode ret -> {} + case ProjNode proj when proj.in(0) instanceof CallEndNode cend -> { + for( int i=1; i<cend.nIns(); i++ ) + evidence |= numericEvidence(cend.in(i),visited); + } + default -> { return 0; } + } + for( int i=1; i<n.nIns(); i++ ) + evidence |= numericEvidence(n.in(i),visited); + + return evidence; + } } diff --git a/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java index 0997fd2f..bc698e19 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java +++ b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java @@ -1,15 +1,39 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.util.Ary; abstract class TypeCheck { static void run(CodeGen code) { - Parser.ParseException err = code._stop.walk(n -> { - Parser.ParseException msg = n.err(); - if( msg != null && code._obs != null ) code._obs.error(n, msg.getMessage()); - return msg; + Ary<Node> errs = new Ary<>(Node.class); + code._stop.walk(n -> { + if( n.err()!=null ) errs.add(n); + return null; }); - if( err != null ) - throw err; + if( errs.isEmpty() ) return; + + // A bad Load now produces BOTTOM. Report the bad access before a + // Convert or arithmetic use that merely received its failed result. + Node first = errs.at(0); + for( Node n : errs ) + if( noBottomInputs(n) ) { first=n; break; } + for( Node n : errs ) + if( noBottomInputs(n) && + ((n instanceof MemOpNode nm && first instanceof MemOpNode fm && + nm._loc!=null && nm._loc.before(fm._loc)) || + (n instanceof CFGNode nc && first instanceof CFGNode fc && nc.idepth()<fc.idepth())) ) + first=n; + Parser.ParseException err = first.err(); + if( code._obs!=null ) code._obs.error(first,err.getMessage()); + throw err; + } + + private static boolean noBottomInputs(Node n) { + for( Node def : n._inputs ) + if( def!=null && !(def instanceof FldOffNode) && def._type==Type.BOTTOM ) + return false; + return true; } } diff --git a/src/main/java/com/seaofnodes/simple/node/AddFNode.java b/src/main/java/com/seaofnodes/simple/node/AddFNode.java index 4ad02dbb..0547e29c 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddFNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddFNode.java @@ -7,6 +7,7 @@ import java.util.BitSet; public class AddFNode extends ArithFNode { public AddFNode(Node lhs, Node rhs) { super(lhs, rhs); } + public AddFNode(ArithNode n) { super(n); } @Override public String label() { return "AddF"; } diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 2bbe1053..aa0ee024 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -1,16 +1,18 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; -import static com.seaofnodes.simple.Parser.con; - public class AddNode extends ArithNode { + @Override boolean allowFloat() { return true; } public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + public AddNode(Node lhs, Node rhs, byte mode) { super(null, lhs, rhs, mode); } @Override public String label() { return "Add"; } @Override public String op() { return "+"; } - @Override long doOp( long x, long y ) { return x + y; } + @Override long doOp( long x, long y ) { return x + y; } + @Override double doOp(double x, double y ) { return x + y; } @Override TypeInteger doOp(TypeInteger x, TypeInteger y) { // Fold ranges like {0-1} + {2-3} into {2-4}. if( !overflow(x._min,y._min) && @@ -21,6 +23,11 @@ public class AddNode extends ArithNode { @Override public Node idealize () { + // Settle the one-shot arithmetic mode before applying family-specific + // algebraic identities. + if( _mode==0 ) + return super.idealize(); + Node lhs = in(1); Node rhs = in(2); if( rhs instanceof AddNode add && add.err()!=null ) @@ -29,12 +36,12 @@ public class AddNode extends ArithNode { // Add of 0. We do not check for (0+x) because this will already // canonicalize to (x+0) - if( t2 == TypeInteger.ZERO && lhs._type instanceof TypeInteger ) + if( t2 == TypeInteger.ZERO && lhs._type.isa(compute()) ) return lhs; // Add of same to a multiply by 2 - if( lhs==rhs ) - return new ShlNode(null,lhs,con(1)); + if( lhs==rhs && _mode==1 ) + return new ShlNode(null,lhs,com.seaofnodes.simple.Parser.con(1)); // Goal: a left-spine set of adds, with constants on the rhs (which then fold). @@ -44,7 +51,7 @@ public class AddNode extends ArithNode { // x+(-y) becomes x-y if( rhs instanceof MinusNode minus ) - return new SubNode(lhs,minus.in(1)); + return new SubNode(lhs,minus.in(1),_mode); // Now we might see (add add non) or (add non non) or (add add add) but never (add non add) @@ -52,18 +59,21 @@ public class AddNode extends ArithNode { // Swap to (x + y) + z // Rotate (add add add) to remove the add on RHS if( rhs instanceof AddNode add ) - return new AddNode(new AddNode(lhs,add.in(1)).peephole(), add.in(2)); + return copy(copy(lhs,add.in(1)).peephole(), add.in(2)); // Now we might see (add add non) or (add non non) but never (add non add) nor (add add add) - if( !(lhs instanceof AddNode) ) + if( !(lhs instanceof AddNode) ) { // Rotate; look for (add (phi cons) con/(phi cons)) - return spine_cmp(lhs,rhs,this) ? swap12() : phiCon(this,true); + if( spine_cmp(lhs,rhs,this) ) return swap12(); + Node n = phiCon(this,true); + return n == null ? super.idealize() : n; + } // Now we only see (add add non) // Dead data cycle; comes about from dead infinite loops. Do nothing, // the loop will peep as dead after a bit. - if( lhs.in(1) == lhs ) + if( lhs.nIns()>=2 && lhs.in(1) == lhs ) return null; // Do we have (x + con1) + con2? @@ -73,7 +83,7 @@ public class AddNode extends ArithNode { // because if it later became a constant then we could make this // transformation. if( addDep(lhs.in(2))._type.isConstant() && rhs._type.isConstant() ) - return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole()); + return copy(lhs.in(1),copy(lhs.in(2),rhs).peephole()); // Do we have ((x + (phi cons)) + con) ? @@ -87,13 +97,13 @@ public class AddNode extends ArithNode { // Do we rotate (x + y) + z // into (x + z) + y ? if( spine_cmp(lhs.in(2),rhs,this) ) - return new AddNode(new AddNode(lhs.in(1),rhs).peephole(),lhs.in(2)); + return copy(copy(lhs.in(1),rhs).peephole(),lhs.in(2)); return super.idealize(); } // Rotation is only valid for associative ops, e.g. Add, Mul, And, Or, Xor. - // Do we have ((phi cons)|(x + (phi cons)) + con|(phi cons)) ? + // Do we have ((phi cons)|(x + (phi cons)) + con|(phi cons)|(op y con)) ? // Push constant up through the phi: x + (phi con0+con0 con1+con1...) static Node phiCon(Node op, boolean rotate) { Node lhs = op.in(1); @@ -126,7 +136,7 @@ public class AddNode extends ArithNode { for( int i=1; i<ns.length; i++ ) ns[i] = op.copy(lphi.in(i), rhs instanceof PhiNode ? rhs.in(i) : rhs).peephole(); String label = lphi._label + (rhs instanceof PhiNode rphi ? rphi._label : ""); - Node phi = new PhiNode(label,lphi._minType.meet(op._type),ns).peephole(); + Node phi = new PhiNode(label,ns).peephole(); // Rotate needs another op, otherwise just the phi return lhs==lphi ? phi : op.copy(lhs.in(1),phi); } @@ -164,6 +174,5 @@ public class AddNode extends ArithNode { return lo._nid > hi._nid; } - @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); } - @Override Node copyF() { return new AddFNode(null,null); } + @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs,_mode); } } diff --git a/src/main/java/com/seaofnodes/simple/node/AndNode.java b/src/main/java/com/seaofnodes/simple/node/AndNode.java index 9957472b..2bb289e9 100644 --- a/src/main/java/com/seaofnodes/simple/node/AndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AndNode.java @@ -5,9 +5,8 @@ import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; public class AndNode extends ArithNode { - public AndNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs); } + public AndNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } - @Override public String label() { return "And"; } @Override public String op() { return "&"; } @Override long doOp( long x, long y ) { return x & y; } @Override TypeInteger doOp(TypeInteger x, TypeInteger y) { @@ -20,6 +19,7 @@ public class AndNode extends ArithNode { public Node idealize() { Node lhs = in(1); Node rhs = in(2); + Type t1 = lhs._type; Type t2 = rhs._type; if( !(t1 instanceof TypeInteger && t2 instanceof TypeInteger t2i) ) @@ -28,7 +28,7 @@ public class AndNode extends ArithNode { // And of -1. We do not check for (-1&x) because this will already // canonicalize to (x&-1). We do not check for zero, because // the compute() call will return a zero already. - if( t2i.isConstant() && t2i.value()==-1 ) + if( t2i.isConstant() && t2i.value()==-1 && forceInt(lhs) ) return lhs; // Move constants to RHS: con*arg becomes arg*con diff --git a/src/main/java/com/seaofnodes/simple/node/ArithFNode.java b/src/main/java/com/seaofnodes/simple/node/ArithFNode.java index dafba626..7d219215 100644 --- a/src/main/java/com/seaofnodes/simple/node/ArithFNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ArithFNode.java @@ -7,6 +7,7 @@ import com.seaofnodes.simple.type.TypeFloat; public abstract class ArithFNode extends Node { public ArithFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + protected ArithFNode(ArithNode n) { super(n); } @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.open().n(in(1)).p(glabel()).n(in(2)).close(); diff --git a/src/main/java/com/seaofnodes/simple/node/ArithNode.java b/src/main/java/com/seaofnodes/simple/node/ArithNode.java index 54290330..5f0862b2 100644 --- a/src/main/java/com/seaofnodes/simple/node/ArithNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ArithNode.java @@ -3,15 +3,22 @@ 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.TypeInteger; +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Utils; +import java.util.HashMap; +import java.util.IdentityHashMap; -public abstract class ArithNode extends Node { +public abstract class ArithNode extends Node implements ModeNode { // Source location for late reported errors Parser.Lexer _loc; + // Mode is 0 for unknown, 1 for int, 2 for flt + byte _mode; public ArithNode( Parser.Lexer loc, Node lhs, Node rhs) { super(null, lhs, rhs); _loc = loc; } + public ArithNode( Parser.Lexer loc, Node lhs, Node rhs, byte mode) { this(loc,lhs,rhs); _mode=mode; } + abstract String op(); @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { @@ -20,20 +27,107 @@ public abstract class ArithNode extends Node { abstract long doOp(long x, long y); abstract TypeInteger doOp(TypeInteger x, TypeInteger y); + double doOp(double x, double y) { throw Utils.TODO(); } + + @Override public byte mode() { return _mode; } + @Override public Node setMode(byte mode) { + assert _mode==0 && (mode==1 || mode==2); + unlock(); // _mode participates in GVN hash and equality + _mode = mode; + return this; + } + static byte mode( Type t1, Type t2 ) { + if( t1 instanceof TypeFloat || t2 instanceof TypeFloat ) return 2; + if( t1 instanceof TypeInteger && t2 instanceof TypeInteger ) return 1; + if( t1 instanceof TypeMemPtr && t2 instanceof TypeMemPtr ) return 1; + if( t1 instanceof TypeFunPtr && t2 instanceof TypeFunPtr ) return 1; + return 0; + } + + // Int-only ops, such as &, | and shifts, can collapse to one input. If + // that input, or the live arms of a Phi input, are still mode-polymorphic + // ops, settle them before returning the value so the replacement remains + // at least as narrow as the int-only op. + static boolean forceInt(Node n) { + if( n instanceof ModeNode mode && mode.mode()==0 ) { + mode.setMode((byte)1); + n.setType(n.compute()); + // Mode changes remove n from GVN even if the caller's remaining + // conditions prevent replacing the int-only operation by n. + CodeGen.CODE.add(n); + } + return true; + } + + // Check that a settled mode agrees with all data inputs. Takes the Node + // instead of a varargs list both to avoid allocation and to keep this ready + // to become shared mode-aware Node behavior later. + static Parser.ParseException nodeErr(Node n, Parser.Lexer loc, String op, byte mode, boolean allowFloat) { + Type bad = null; + for( int i=1; i<n.nIns(); i++ ) { + Type t = n.in(i)._type; + if( t==null ) + return null; + if( t.isHigh() ) + return null; + // A weak input is not evidence of a bad mode while the graph is + // still being built. Loop Phis commonly await their backedge. + if( CodeGen.CODE._phase.ordinal() < CodeGen.Phase.Opto.ordinal() && t == Type.BOTTOM ) + return null; + bad = switch( t ) { + case TypeInteger ti -> mode==1 ? null : t; + case TypeMemPtr ti -> mode==1 ? null : t; + case TypeFunPtr ti -> mode==1 ? null : t; + case TypeFloat tf -> mode==2 ? null : t; + default -> t; + }; + if( bad != null ) break; + } + boolean unsupportedFloat = false; + if( !allowFloat ) + for( int i=1; i<n.nIns(); i++ ) + if( n.in(i)._type instanceof TypeFloat ) { + bad = n.in(i)._type; + unsupportedFloat = true; + break; + } + if( bad == null ) + return null; + if( unsupportedFloat || n instanceof BoolNode ) + return Parser.error("Cannot '"+op+"' "+bad,loc); + return Parser.error("Cannot '"+op+"' "+bad,loc); + } + + // Arithmetic subclasses which have a floating-point interpretation override. + boolean allowFloat() { return false; } - // Generic airthmetic op math: high returns high; low returns low; 2 + // Generic arithmetic op math: high returns high; low returns low; 2 // constants fold; only 2 non-constants call specialized math. @Override public final Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; - if( t1.isHigh() || t2.isHigh() ) - return Type.TOP; - if( t1 instanceof TypeInteger x && - t2 instanceof TypeInteger y ) - return x.isConstant() && y.isConstant() - ? con(x,y) - : doOp(x,y).makeWide( (byte)Math.max(x._widen,y._widen) ); - return TypeInteger.BOT; + if( t1==null || t2==null ) return Type.TOP; + if( t1.isHigh() || t2.isHigh() ) return Type.TOP; + if( t1==Type.BOTTOM || t2==Type.BOTTOM ) return Type.BOTTOM; + byte mode = _mode==0 ? mode(t1,t2) : _mode; + if( mode==0 ) + return CodeGen.CODE._phase.ordinal() < CodeGen.Phase.Opto.ordinal() ? Type.BOTTOM : Type.TOP; + if( mode==1 ) { + if( t1 instanceof TypeInteger x && + t2 instanceof TypeInteger y ) + return x.isConstant() && y.isConstant() + ? con(x,y) + : doOp(x,y).makeWide( (byte)Math.max(x._widen,y._widen) ); + return TypeInteger.BOT; + } + // FP handling + 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); + } + return TypeFloat.F64; } private TypeInteger con( Type t1, Type t2 ) { @@ -46,36 +140,50 @@ public abstract class ArithNode extends Node { // push-down peephole cycle because the constants all fold first. // Returns "Phi(op(con,con),op(x,y))". - // This check is slightly different from the - // Expected to be called after other ideal checks are done. @Override public Node idealize() { + Type t1 = in(1)._type, t2 = in(2)._type; + + // Can we decide int vs flt? + if( _mode==0 ) { + byte mode = mode(t1,t2); + if( mode!=0 ) return setMode(mode).init(); + } + if( _mode==2 ) { + if( t1 instanceof TypeInteger ) return copy(new ToFloatNode(in(1)).peephole(),in(2)); + if( t2 instanceof TypeInteger ) return copy(in(1),new ToFloatNode(in(2)).peephole()); + } + if( in(1) instanceof PhiNode lhs && in(2) instanceof PhiNode rhs && lhs.nIns() >= 2 && !lhs.inProgress() && - 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) ) { - // Profit check: only 1 instance of `this` will remain, all the - // others will fold to constants. - int cnt=0; - for( int i=1; i<lhs.nIns(); i++ ) - if( isCon(lhs,rhs,i) ) - cnt++; - if( lhs.nIns()-1 - cnt <= 1 ) { - // Profit! Push up-phi and fold - Node[] ns = new Node[lhs.nIns()]; - ns[0] = lhs.in(0); - for( int i=1; i<lhs.nIns(); i++ ) { - ns[i] = isCon(lhs,rhs,i) - ? new ConstantNode(con(lhs.in(i)._type, rhs.in(i)._type)).peephole() - : copy(lhs.in(i), rhs.in(i)).peephole(); + (lhs.nIns() > 2 && lhs.in(2)!=lhs && rhs.nIns() > 2 && rhs.in(2)!=rhs) ) { + Node r = lhs.region(); + if( r==rhs.region() && !(r instanceof FunNode) && + // For loops, the backedge *must* fold away, lest we unroll forever + (!(r instanceof LoopNode) || isCon(lhs,rhs,2)) ) { + // Profit check: only 1 instance of `this` will remain, all the + // others will fold to constants. For loops, *all* must fold away + int cnt=0; + for( int i=1; i<lhs.nIns(); i++ ) + if( isCon(lhs,rhs,i) ) + cnt++; + if( lhs.nIns()-1 - cnt <= 1 ) { + // Profit! Push up-phi and fold + Node[] ns = new Node[lhs.nIns()]; + ns[0] = lhs.in(0); + for( int i=1; i<lhs.nIns(); i++ ) { + ns[i] = isCon(lhs,rhs,i) + ? ConstantNode.make(con(lhs.in(i)._type, rhs.in(i)._type)).peephole() + : copy(lhs.in(i), rhs.in(i)).peephole(); + } + String label = lhs._label==rhs._label ? lhs._label : lhs._label + rhs._label; + return new PhiNode(label, ns).peephole(); } - String label = lhs._label==rhs._label ? lhs._label : lhs._label + rhs._label; - return new PhiNode(label,lhs._minType,ns).peephole(); } } + return null; } @@ -85,14 +193,14 @@ public abstract class ArithNode extends Node { static boolean overflow( long x, long y ) { - if( (x ^ y ) < 0 ) return false; // unequal signs, never overflow + if( (x ^ y ) < 0 ) return false; // unequal signs, never overflow return (x ^ (x + y)) < 0; // sum has unequal signs, so overflow } @Override public Parser.ParseException err() { - if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return null; - if( !(in(1)._type instanceof TypeInteger) ) return Parser.error("Cannot '"+op()+"' " + in(1)._type,_loc); - if( !(in(2)._type instanceof TypeInteger) ) return Parser.error("Cannot '"+op()+"' " + in(2)._type,_loc); - return null; + return nodeErr(this,_loc,op(),_mode,allowFloat()); } + + @Override public boolean eq( Node n ) { return _mode==((ArithNode)n)._mode; } + @Override public int hash() { return _mode; } } diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 0d82c5b9..02421e43 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -3,20 +3,23 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Utils; +import java.util.HashMap; +import java.util.IdentityHashMap; import static com.seaofnodes.simple.type.TypeInteger.*; -abstract public class BoolNode extends Node { +abstract public class BoolNode extends Node implements ModeNode { - public BoolNode(Node lhs, Node rhs) { - super(null, lhs, rhs); - } + // Mode is 0 for unknown, 1 for int, 2 for flt + byte _mode; - abstract public String op(); // String opcode name + public BoolNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + public BoolNode(Node lhs, Node rhs, byte mode) { super(null, lhs, rhs); _mode = mode; } - @Override - public String label() { return getClass().getSimpleName(); } + + abstract public String op(); // String opcode name @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.open().n(in(1)).p(op()).n(in(2)).close(); @@ -26,15 +29,25 @@ abstract public class BoolNode extends Node { public TypeInteger compute() { Type t1 = in(1)._type; Type t2 = in(2)._type; + if( t1==null || t2==null ) + return BOOL; // Exactly equals? if( t1.isHigh() || t2.isHigh() ) return (TypeInteger)BOOL.dual(); if( in(1)==in(2) ) // LT fails, both EQ and LE succeed return this instanceof LT ? FALSE : TRUE; - if( t1 instanceof TypeInteger i1 && - t2 instanceof TypeInteger i2 ) - return doOp(i1,i2); + byte mode = _mode==0 ? ArithNode.mode(t1,t2) : _mode; + if( mode==0 ) + return BOOL; + // Handle integer compares + if( mode==1 ) { + if( t1 instanceof TypeInteger i1 && + t2 instanceof TypeInteger i2 ) + return doOp(i1,i2); + return BOOL; + } + // Floating compare. Mixed inputs are converted in idealize(). if( t1 instanceof TypeFloat f1 && t2 instanceof TypeFloat f2 && f1.isConstant() && f2.isConstant() ) @@ -44,22 +57,41 @@ abstract public class BoolNode extends Node { TypeInteger doOp(TypeInteger t1, TypeInteger t2) { throw Utils.TODO(); } boolean doOp(double lhs, double rhs) { throw Utils.TODO(); } - Node copyF(Node lhs, Node rhs) { return null; } - public boolean isFloat() { return false; } + public boolean isFloat() { assert _mode!=0; return _mode==2; } + @Override public byte mode() { return _mode; } + @Override public Node setMode(byte mode) { + assert _mode==0 && (mode==1 || mode==2); + unlock(); // _mode participates in GVN hash and equality + _mode = mode; + return this; + } @Override public Node idealize() { // Compare of same if( in(1)==in(2) ) - return this instanceof LT ? Parser.ZERO : new ConstantNode(TRUE); + return this instanceof LT ? com.seaofnodes.simple.Parser.ZERO : ConstantNode.make(TRUE); + // Can we decide int vs flt? + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1==null || t2==null ) + return null; + if( _mode==0 ) { + byte mode = ArithNode.mode(t1,t2); + if( mode!=0 ) return setMode(mode).init(); + } + if( _mode==2 ) { + if( t1 instanceof TypeInteger ) return copy(new ToFloatNode(in(1)).peephole(),in(2)); + if( t2 instanceof TypeInteger ) return copy(in(1),new ToFloatNode(in(2)).peephole()); + } + // Equals pushes constant to the right; 5==X becomes X==5. if( this instanceof EQ ) { if( !(in(2) instanceof ConstantNode) ) { // con==noncon becomes noncon==con if( in(1) instanceof ConstantNode || in(1)._nid > in(2)._nid ) - // Equals sorts by NID otherwise: non.high == non.low becomes non.low == non.high - return in(1)._type instanceof TypeFloat ? new EQF(in(2),in(1)) : new EQ(in(2),in(1)); + // Equals sorts by NID otherwise: non.high == non.low becomes non.low == non.high + return new EQ(in(2),in(1)); } // Equals X==0 becomes a !X if( (in(2)._type == ZERO || in(2)._type == Type.NIL) ) @@ -75,82 +107,96 @@ abstract public class BoolNode extends Node { return null; } + @Override public boolean eq( Node n ) { return _mode==((BoolNode)n)._mode; } + @Override public int hash() { return _mode; } + @Override public Parser.ParseException err() { + return ArithNode.nodeErr(this,null,op(),_mode,!(this instanceof ULT)); + } + public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } - public String op() { return "=="; } + public EQ(Node lhs, Node rhs, byte mode) { super(lhs,rhs, mode); } + public String op() { return "=="; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( i1==i2 && i1.isConstant() ) return TRUE; if( i1._max < i2._min || i1._min > i2._max ) return FALSE; return BOOL; } - Node copy(Node lhs, Node rhs) { return new EQ(lhs,rhs); } - Node copyF() { return new EQF(null,null); } + @Override boolean doOp(double lhs, double rhs) { return lhs==rhs; } + Node copy(Node lhs, Node rhs) { return new EQ(lhs,rhs,_mode); } } public static class NE extends BoolNode { public NE(Node lhs, Node rhs) { super(lhs,rhs); } - public String op() { return "!="; } + public NE(Node lhs, Node rhs, byte mode) { super(lhs,rhs,mode); } + public String op() { return "!="; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( i1==i2 && i1.isConstant() ) return TRUE; if( i1._max < i2._min || i1._min > i2._max ) return FALSE; return BOOL; } - Node copy(Node lhs, Node rhs) { return new NE(lhs,rhs); } - Node copyF() { throw Utils.TODO(); } + @Override boolean doOp(double lhs, double rhs) { return lhs!=rhs; } + Node copy(Node lhs, Node rhs) { return new NE(lhs,rhs,_mode); } } public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } - public String op() { return "<" ; } + public LT(Node lhs, Node rhs, byte mode) { super(lhs,rhs, mode); } + public String op() { return "<" ; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( i1._max < i2._min ) return TRUE; if( i1._min >= i2._max ) return FALSE; return BOOL; } - Node copy(Node lhs, Node rhs) { return new LT(lhs,rhs); } - Node copyF() { return new LTF(null,null); } + @Override boolean doOp(double lhs, double rhs) { return lhs<rhs; } + Node copy(Node lhs, Node rhs) { return new LT(lhs,rhs,_mode); } } public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } - public String op() { return "<="; } + public LE(Node lhs, Node rhs, byte mode) { super(lhs,rhs,mode); } + public String op() { return "<="; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( i1._max <= i2._min ) return TRUE; if( i1._min > i2._max ) return FALSE; return BOOL; } - Node copy(Node lhs, Node rhs) { return new LE(lhs,rhs); } - Node copyF() { return new LEF(null,null); } + @Override boolean doOp(double lhs, double rhs) { return lhs<=rhs; } + Node copy(Node lhs, Node rhs) { return new LE(lhs,rhs,_mode); } } + // Unsigned less that, for range checks. Not directly user writable. + public static class ULT extends BoolNode { + public ULT(Node lhs, Node rhs) { super(lhs,rhs,(byte)1); } + public ULT(Node lhs, Node rhs, byte mode) { + super(lhs,rhs,(byte)1); + assert mode==1; + } + public String op() { return "u<" ; } + TypeInteger doOp(TypeInteger i1, TypeInteger i2) { + if( Long.compareUnsigned(i1._max,i2._min) < 0 ) return TRUE; + if( Long.compareUnsigned(i1._min,i2._max) >= 0 ) return FALSE; + return BOOL; + } + Node copy(Node lhs, Node rhs) { return new ULT(lhs,rhs); } + } public static class EQF extends EQ { - public EQF(Node lhs, Node rhs) { super(lhs,rhs); } + public EQF(Node lhs, Node rhs) { super(lhs,rhs,(byte)2); } @Override boolean doOp(double lhs, double rhs) { return lhs == rhs; } @Override public boolean isFloat() { return true; } @Override Node copy(Node lhs, Node rhs) { return new EQF(lhs,rhs); } } public static class LTF extends LT { - public LTF(Node lhs, Node rhs) { super(lhs,rhs); } + public LTF(Node lhs, Node rhs) { super(lhs,rhs,(byte)2); } @Override boolean doOp(double lhs, double rhs) { return lhs < rhs; } @Override public boolean isFloat() { return true; } @Override Node copy(Node lhs, Node rhs) { return new LTF(lhs,rhs); } } public static class LEF extends LE { - public LEF(Node lhs, Node rhs) { super(lhs,rhs); } + public LEF(Node lhs, Node rhs) { super(lhs,rhs,(byte)2); } @Override boolean doOp(double lhs, double rhs) { return lhs <= rhs; } @Override public boolean isFloat() { return true; } @Override Node copy(Node lhs, Node rhs) { return new LEF(lhs,rhs); } } - // Unsigned less that, for range checks. Not directly user writable. - public static class ULT extends BoolNode { - public ULT(Node lhs, Node rhs) { super(lhs,rhs); } - public String op() { return "u<" ; } - TypeInteger doOp(TypeInteger i1, TypeInteger i2) { - if( Long.compareUnsigned(i1._max,i2._min) < 0 ) return TRUE; - if( Long.compareUnsigned(i1._min,i2._max) >= 0 ) return FALSE; - return BOOL; - } - Node copy(Node lhs, Node rhs) { return new ULT(lhs,rhs); } - } } diff --git a/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java index 7d4f1fb8..8399ed09 100644 --- a/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java @@ -23,7 +23,7 @@ public class BulkMemPhiNode extends PhiNode { } private BulkMemPhiNode(String label, BitSet aliases, Node... inputs) { - super(label,TypeMem.BOT,inputs); + super(label,inputs); _aliases = aliases; } @@ -31,6 +31,7 @@ public class BulkMemPhiNode extends PhiNode { public BulkMemPhiNode(BulkMemPhiNode phi) { super(phi); _aliases = phi._aliases; } + @Override public boolean isMem() { return true; } @Override public String label() { return "BulkPhi"+_aliases; } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/CallNode.java b/src/main/java/com/seaofnodes/simple/node/CallNode.java index e63b3f62..b2708531 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -35,7 +35,7 @@ public class CallNode extends CFGNode { if( fptr()._type instanceof TypeFunPtr tfp && tfp._isConstant() && tfp.notNull() ) { FunNode fun = CodeGen.CODE._link(tfp); if( fun !=null ) return fun._name; - if( fptr() instanceof ExternNode ex ) return ex._extern; + return CodeGen.CODE.externFunc(tfp); } return null; } diff --git a/src/main/java/com/seaofnodes/simple/node/CastNode.java b/src/main/java/com/seaofnodes/simple/node/CastNode.java index 4e93f3e6..fa7c207d 100644 --- a/src/main/java/com/seaofnodes/simple/node/CastNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CastNode.java @@ -26,6 +26,14 @@ public class CastNode extends Node { @Override public String label() { return "("+_t.str()+")"; } + @Override boolean _upgradeType(java.util.HashMap<String,Type> types) { + Type t = _t.upgradeType(types); + if( t==_t ) return false; + unlock(); + _t = t; + return true; + } + @Override public boolean isConst() { return true; } diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 7c330175..8d783be7 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -18,7 +18,7 @@ import com.seaofnodes.simple.util.SB; */ public class ConstantNode extends Node { - public final Type _con; + public Type _con; public ConstantNode( Type type ) { super(new Node[]{CodeGen.CODE._start}); _con = _type = type; @@ -56,4 +56,12 @@ public class ConstantNode extends Node { @Override public Node idealize() { return null; } @Override public boolean eq(Node n) { return _con==((ConstantNode)n)._con; } @Override int hash() { return _con.hashCode(); } + + @Override boolean _upgradeType(java.util.HashMap<String,Type> types) { + Type next = _con.upgradeType(types); + if( next==_con ) return false; + unlock(); + _con=next; + return true; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/ConvertNode.java b/src/main/java/com/seaofnodes/simple/node/ConvertNode.java new file mode 100644 index 00000000..c5be0123 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ConvertNode.java @@ -0,0 +1,103 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.print.ExprPrinter; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.type.*; + +import java.util.HashMap; + +// Convert a value to an authoritative destination type. The destination is +// known structurally from a declaration; the source family might sharpen later. +public class ConvertNode extends Node { + private Type _dst; + + public ConvertNode(Type dst, Node val) { + super(null,val); + // Folding this conversion would replace the Return-linked FunPtrNode + // with an unhooked ConstantNode. + assert !(dst instanceof TypeFunPtr && val instanceof FunPtrNode); + _dst = dst; + } + + public Type dst() { return _dst; } + public Node val() { return in(1); } + + @Override public String label() { return "Convert_"+_dst.str(); } + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + return p.p(label()).open().n(val()).close(); + } + + // The declaration fixes the result family during pessimistic parsing. + // From SCCP onward, preserve dead inputs and stronger facts in that family. + @Override public Type compute() { + Type src = val()._type; + if( CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Opto.ordinal() ) { + if( src.isHigh() ) return Type.TOP; + if( (src.isa(_dst) && src.accessISA(_dst)) ) return src; + } + return _dst; + } + + @Override public Node idealize() { + Type src = val()._type; + if( src==Type.BOTTOM || src==Type.TOP ) return null; + if( (src.isa(_dst) && src.accessISA(_dst)) ) return val(); + + // Managed arrays are represented by an object pointer, while C wants + // the address of the first element. The representation cast itself is + // zero-code; the Add skips the array header. + if( _dst==TypeInteger.BOT && src instanceof TypeMemPtr tmp && tmp._obj.isAry() ) + return new AddNode(new PtrToIntNode(val()).peephole(),Parser.off(tmp._obj,"[]")); + + // Integer (and nil-as-zero) to floating point. + if( (src instanceof TypeInteger || src==Type.NIL) && _dst instanceof TypeFloat ) + return new ToFloatNode(val()); + + // Convert to i64 first, then apply the destination's integer width. + if( src instanceof TypeFloat && _dst instanceof TypeInteger ) + return new ConvertNode(_dst,new ToIntegerNode(val()).peephole()); + + // Narrow integers produce the declared sign/zero extension. + if( src instanceof TypeInteger && _dst instanceof TypeInteger dst ) { + if( dst._min==0 ) + return new AndNode(null,val(),con(dst._max)); + int shift = Long.numberOfLeadingZeros(dst._max)-1; + Node shf = con(shift); + if( shf._type==TypeInteger.ZERO ) return val(); + return new SarNode(null,new ShlNode(null,val(),shf.keep()).peephole(),shf.unkeep()); + } + + // Narrow f64 to f32. + if( src instanceof TypeFloat && _dst instanceof TypeFloat ) + return new RoundF32Node(val()); + + // Wait for more source information, or report an error after Opto. + return null; + } + + + + @Override public Parser.ParseException err() { + if( val()._type==Type.BOTTOM || + val()._type instanceof TypeNil src && src.nullable() && _dst instanceof TypeNil dst && dst.notNull() ) { + Node out = out(0); + if( out instanceof PhiNode phi ) out = phi.out(0); + if( out instanceof StoreNode st ) + return Parser.error( "'" + ((TypeMemPtr)st.ptr()._type)._obj._name + "' is not fully initialized, field '" + st._name + "' is only partially set in the constructor", null ); + } + return Parser.error("Type "+val()._type.str()+" is not of declared type "+_dst.str(),null); + } + + @Override public boolean eq(Node n) { return _dst==((ConvertNode)n)._dst; } + @Override int hash() { return _dst.hashCode(); } + + @Override boolean _upgradeType(java.util.HashMap<String,Type> types) { + Type next = _dst.upgradeType(types); + if( next==_dst ) return false; + unlock(); + _dst=next; + return true; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/DivFNode.java b/src/main/java/com/seaofnodes/simple/node/DivFNode.java index 0d037a30..df1dae4e 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivFNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivFNode.java @@ -7,6 +7,7 @@ import java.util.BitSet; public class DivFNode extends ArithFNode { public DivFNode(Node lhs, Node rhs) { super(lhs, rhs); } + public DivFNode(ArithNode n) { super(n); } @Override public String label() { return "DivF"; } diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java index 7b5ae16c..d973ffa7 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -2,15 +2,18 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.type.TypeFloat; import java.util.BitSet; public class DivNode extends ArithNode { + @Override boolean allowFloat() { return true; } public DivNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + public DivNode(Node lhs, Node rhs, byte mode) { super(null, lhs, rhs, mode); } - @Override public String label() { return "Div"; } - @Override public String op() { return "//"; } + @Override public String op() { return _mode==1 ? "//" : "/"; } - @Override long doOp( long x, long y ) { return y==0 ? 0 : x / y; } + @Override long doOp( long x, long y ) { return y==0 ? 0 : x / y; } + @Override double doOp(double x, double y ) { return x / y; } @Override TypeInteger doOp(TypeInteger x, TypeInteger y) { return TypeInteger.BOT; } @@ -18,11 +21,19 @@ public class DivNode extends ArithNode { @Override public Node idealize() { // Div of 1. - if( in(2)._type == TypeInteger.TRUE && in(1)._type instanceof TypeInteger ) + if( in(2)._type == TypeInteger.TRUE && in(1)._type.isa(compute()) ) return in(1); + + // Div of constant + if( _mode==2 ) { + if( in(2)._type == TypeFloat.constant(1.) && in(1)._type.isa(compute()) ) + return in(1); + if( in(2)._type instanceof TypeFloat f && f.isConstant() ) + return new MulNode(in(1),ConstantNode.make(TypeFloat.constant(1.0/f.value())).peephole(),_mode); + } + return super.idealize(); } - @Override Node copy(Node lhs, Node rhs) { return new DivNode(lhs,rhs); } - @Override Node copyF() { return new DivFNode(null,null); } + @Override Node copy(Node lhs, Node rhs) { return new DivNode(lhs,rhs,_mode); } } diff --git a/src/main/java/com/seaofnodes/simple/node/FldOffNode.java b/src/main/java/com/seaofnodes/simple/node/FldOffNode.java new file mode 100644 index 00000000..7605d74f --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/FldOffNode.java @@ -0,0 +1,24 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.*; + +/** A field name whose receiver's shape is not known while parsing. */ +public class FldOffNode extends Node { + public final String _name; + public FldOffNode(Node ptr, String name) { super(null,ptr); _name=name; } + @Override public String label() { return "#"+_name; } + @Override public Type compute() { return TypeInteger.BOT; } + @Override public Node idealize() { + if( in(1)._type instanceof TypeMemPtr ptr && !ptr._obj._open ) { + if( _name.equals("<<") && ptr._obj.isAry() ) return con(ptr._obj.aryScale()); + if( ptr._obj.field(_name)!=null ) return new ConFldOffNode(ptr._obj._name,_name); + } + return null; + } + @Override public Parser.ParseException err() { + return Parser.error("Cannot resolve field '"+_name+"'",null); + } + @Override public boolean eq(Node n) { return _name.equals(((FldOffNode)n)._name); } + @Override int hash() { return _name.hashCode(); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/FunNode.java b/src/main/java/com/seaofnodes/simple/node/FunNode.java index 70e1c200..1ba57e85 100644 --- a/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -254,4 +254,12 @@ public class FunNode extends RegionNode { return slotRotate*8; } + + @Override boolean _upgradeType(java.util.HashMap<String,Type> types) { + TypeFunPtr next = (TypeFunPtr)_sig.upgradeType(types); + if( next==_sig ) return false; + unlock(); + _sig=next; + return true; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/GuardMach.java b/src/main/java/com/seaofnodes/simple/node/GuardMach.java new file mode 100644 index 00000000..202b1ab8 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/GuardMach.java @@ -0,0 +1,17 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.Encoding; +import com.seaofnodes.simple.codegen.RegMask; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.util.SB; + +public class GuardMach extends GuardNode implements MachNode { + public GuardMach(GuardNode guard) { super(guard); } + @Override public String op() { return label(); } + @Override public RegMask regmap(int i) { assert i==1; return RegMask.FULL; } + @Override public RegMask outregmap() { return RegMask.FULL; } + @Override public int twoAddress() { return in(1)._type==Type.BOTTOM ? 0 : 1; } + @Override public void encoding(Encoding enc) { } + @Override public void asm(CodeGen code, SB sb) { sb.p(code.reg(in(1))); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/GuardNode.java b/src/main/java/com/seaofnodes/simple/node/GuardNode.java new file mode 100644 index 00000000..f808c276 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/GuardNode.java @@ -0,0 +1,66 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.print.ExprPrinter; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeScalar; +import com.seaofnodes.simple.util.Utils; + +import java.util.HashMap; +import java.util.IdentityHashMap; + +// A branch-proven refinement to zero/null or non-zero/non-null. The value +// family is deliberately taken from the input when it becomes known. +public class GuardNode extends Node { + public final boolean _nonZero; + + public GuardNode(boolean nonZero, Node ctrl, Node val) { + super(ctrl,val); + _nonZero = nonZero; + } + + public GuardNode(GuardNode guard) { + super(guard); + _nonZero = guard._nonZero; + } + + + + @Override public String label() { return _nonZero ? "(!=0)" : "(==0)"; } + + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + return p.p(label()).n(in(1)); + } + + @Override public Type compute() { + // Guard is a pinned, path-local fact. If its control path is not + // executable, the fact is not executable either, regardless of how the + // value input sharpens later. + Type c = in(0)._type; + if( c != Type.CONTROL && c != Type.BOTTOM ) + return Type.TOP; + Type t = in(1)._type; + if( t==Type.BOTTOM || t==Type.TOP ) return t; + // The scalar envelope does not identify a value family. Preserve it + // until SCCP learns whether this is an int, float, pointer, or fptr; + // choosing generic ptr here can be weaker than a later concrete type. + if( t==TypeScalar.BOT || t==TypeScalar.TOP ) return t; + Type t2 = _nonZero ? t.nonZero() : t.makeZero(); + if( t2!=null ) t2 = t.join(t2); + return t2==null ? (_type==null ? Type.TOP : _type) : t2; // No sane answer for e.g. not-zero of a zero + } + + @Override public Node idealize() { + if( in(0)._type != Type.CONTROL && in(0)._type != Type.BOTTOM ) + return null; + if( in(1)._type==Type.BOTTOM || in(1)._type==Type.TOP ) return null; + Type t = in(1)._type; + if( _nonZero ? !t.makeZero().isa(t) : t==t.makeZero() ) return in(1); + if( _type.isHighOrConst() && in(1)._type.isa(_type) ) + return in(1); + return null; + } + + @Override public boolean eq(Node n) { return _nonZero==((GuardNode)n)._nonZero; } + @Override int hash() { return _nonZero ? 1 : 0; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index c96993e5..3f21417e 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -60,7 +60,9 @@ public class IfNode extends CFGNode implements MultiNode { // 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() ) { - if( addDep(dom) instanceof IfNode iff && addDep(iff.pred())==pred() && prior instanceof CProjNode prj ) { + if( addDep(dom) instanceof IfNode iff && prior instanceof CProjNode prj && + (addDep(iff.pred())==pred() || + (pred() instanceof GuardNode guard && guard._nonZero && iff.pred()==guard.in(1))) ) { setDef(1,con( prj._idx==0 ? 1 : 0 )); return this; } diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index e057ef1c..24a2f9b8 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -22,8 +22,10 @@ public class LoadNode extends MemOpNode { * @param ptr The ptr to the struct base from where we load a field * @param off The offset inside the struct base */ - public LoadNode(Parser.Lexer loc, String name, int alias, Type glb, Node mem, Node ptr, Node off) { - super(loc, name, alias, true, glb, mem, ptr, off); + public LoadNode(Parser.Lexer loc, String name, int alias, Node mem, Node ptr, Node off) { + // The field declaration will supply storage width once the receiver + // is known. A parser guess must not bound the value of this Load. + super(loc, name, alias, true, Type.BOTTOM, mem, ptr, off); } @Override boolean canDrop(MemOpNode other, Node dep) { @@ -52,37 +54,40 @@ public class LoadNode extends MemOpNode { @Override public Type compute() { - 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 - 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(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; + Type p = ptr()._type; + Type m = mem()._type; + if( p.isHigh() || m.isHigh() ) return TypeScalar.TOP; + if( p==Type.NIL || p==Type.BOTTOM ) return Type.BOTTOM; + if( !(p instanceof TypeMemPtr ptr) ) return TypeScalar.BOT; + if( ptr.nullable() ) return Type.BOTTOM; + Field field = ptr._obj.field(_name); + if( field==null ) return TypeScalar.BOT; + Type t = field._t; + if( t instanceof TypeConAry ary ) t=ary.elem(); + if( _alias!=1 ) t=t.join(MemMergeNode.contents(mem(),_alias,this)); + if( ptr.isFinal() ) t=t.makeRO(); + return t==Type.TOP ? TypeScalar.TOP : t==Type.BOTTOM ? TypeScalar.BOT : t; } @Override public Node idealize() { + if( ptr()._type instanceof TypeMemPtr ptr && !ptr._obj._open ) { + Field field = ptr._obj.field(_name); + // Storage width comes from the declaration, not from a constant + // or range inferred for this particular object's current value. + Type declared = Parser.TYPES.get(ptr._obj._name); + if( declared instanceof TypeMemPtr shape && shape._obj.field(_name)!=null ) + field=shape._obj.field(_name); + Type storage = field==null ? Type.BOTTOM : field._t instanceof TypeConAry ary ? ary.elem() : field._t; + if( field!=null && (_alias!=field._alias || _declaredType!=storage) ) { + unlock(); + _alias=field._alias; + _declaredType=storage; + return this; + } + } + if( _alias==1 ) return null; + if( mem() instanceof CastNode cast ) { setDef(1,cast.in(1)); return this; @@ -128,7 +133,7 @@ public class LoadNode extends MemOpNode { !(ptr instanceof PhiNode p && p.region()==memphi.region()) ? memphi : null; if( find(memphi.in(2),ptr,stop,new BitSet())!=null || (!(memphi.region() instanceof LoopNode) && find(memphi.in(1),ptr,null,new BitSet())!=null) ) { - PhiNode phi = new PhiNode(_name,_declaredType,memphi.region()).keep(); + PhiNode phi = new PhiNode(_name,memphi.region()).keep(); phi.setType(_type); // Backedge searches may return this value Phi. for( int i=1; i<memphi.nIns(); i++ ) { Node p = ptr instanceof PhiNode pp && pp.region()==memphi.region() ? pp.in(i) : ptr; @@ -153,7 +158,7 @@ public class LoadNode extends MemOpNode { // the unchanged loop memory, or a merge whose every arm folds. Null fails. // Register dependencies so a later pointer/offset rewrite retries the query. private Node find(Node mem, Node ptr, Node stop, BitSet visit) { - if( ptr instanceof ReadOnlyNode ro ) ptr=ro.in(1); + ptr = address(ptr); while( mem!=null ) { addDep(mem); if( mem==stop ) return mem; @@ -161,9 +166,12 @@ public class LoadNode extends MemOpNode { case MemMergeNode merge: mem=merge.alias(_alias); break; case CastNode cast: mem=cast.in(1); break; case StoreNode st: + // A symbolic Store may write this field. Wait for its alias; + // skipping it can make a compound assignment read the old value. + if( st._alias==1 ) return null; addDep(st.ptr()); - if( _alias==st._alias && ptr==st.ptr() && off()==st.off() ) return st; - if( _alias==st._alias && !neverAlias(ptr,st.ptr()) && + if( _alias==st._alias && ptr==address(st.ptr()) && off()==st.off() ) return st; + if( _alias==st._alias && !neverAlias(ptr,address(st.ptr())) && !addDep(off())._type.join(addDep(st.off())._type).isHigh() ) return null; mem=st.mem(); break; @@ -190,6 +198,13 @@ public class LoadNode extends MemOpNode { return null; } + // Guards and read-only views keep the same address. Retain the Load's + // guarded input for its null check, but compare actual addresses here. + private static Node address(Node ptr) { + while( ptr instanceof ReadOnlyNode || ptr instanceof GuardNode ) ptr=ptr.in(1); + return ptr; + } + private Node folded(Node win) { return win instanceof StoreNode st ? extend(castRO(st.val())) : zero((NewNode)win); } @@ -201,13 +216,13 @@ public class LoadNode extends MemOpNode { if( win!=null ) { if( win==stop ) return value; if( win instanceof MemPhiNode mp ) { - PhiNode phi=new PhiNode(_name,_declaredType,mp.region()).keep(); + PhiNode phi=new PhiNode(_name,mp.region()).keep(); for( int i=1; i<mp.nIns(); i++ ) phi.addDef(load(mp.in(i),ptr,stop,value)); return phi.unkeep().peephole(); } return folded(win).peephole(); } - LoadNode ld=new LoadNode(_loc,_name,_alias,_declaredType,mem,ptr,off()); + LoadNode ld=new LoadNode(_loc,_name,_alias,mem,ptr,off()); ld.setDef(0,in(0)); return ld.peephole(); } diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index e7b2c792..1f0fc4d3 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -22,7 +22,7 @@ import java.util.ArrayList; public abstract class MemOpNode extends Node { // The equivalence alias class - public final int _alias; + public int _alias; // True if load-like, false if store-like. // @@ -143,4 +143,12 @@ public abstract class MemOpNode extends Node { } } } + + @Override boolean _upgradeType(java.util.HashMap<String,Type> types) { + Type next = _declaredType.upgradeType(types); + if( next==_declaredType ) return false; + unlock(); + _declaredType=next; + return true; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java b/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java index 787333d9..ba53cfd8 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java @@ -9,20 +9,21 @@ public class MemPhiNode extends PhiNode { public final int _alias; public MemPhiNode(String label, int alias, Node... inputs) { - super(label,TypeMem.make(alias,Type.BOTTOM),inputs); + super(label,inputs); assert alias > 1; _alias = alias; } public MemPhiNode(MemPhiNode phi) { super(phi); _alias = phi._alias; } + @Override public boolean isMem() { return true; } @Override public String label() { return "MemPhi_"+_alias; } @Override public Type compute() { assert BulkMemPhiNode.checkMem(this,_alias); if( !(region() instanceof RegionNode r) ) return (region()._type==Type.XCONTROL || region()._type==Type.TOP) ? TypeMem.TOP : _type; - if( r.inProgress() ) return r instanceof LoopNode ? _minType : TypeMem.BOT; + if( r.inProgress() ) return r instanceof LoopNode ? TypeMem.make(_alias,Type.BOTTOM) : TypeMem.BOT; Type t = Type.TOP; for( int i=1; i<nIns(); i++ ) if( addDep(r.in(i))._type!=Type.XCONTROL && r.in(i)._type!=Type.TOP ) diff --git a/src/main/java/com/seaofnodes/simple/node/MinusFNode.java b/src/main/java/com/seaofnodes/simple/node/MinusFNode.java index 74439b8c..c3c27883 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusFNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusFNode.java @@ -7,6 +7,7 @@ import com.seaofnodes.simple.type.TypeFloat; public class MinusFNode extends Node { public MinusFNode(Node in) { super(null, in); } + public MinusFNode(MinusNode n) { super(n); } @Override public String label() { return "MinusF"; } diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 94c69785..4d7e3ddb 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -1,33 +1,77 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Utils; +import java.util.HashMap; +import java.util.IdentityHashMap; + +public class MinusNode extends Node implements ModeNode { + // Mode is 0 for unknown, 1 for int, 2 for flt + byte _mode; -public class MinusNode extends Node { public MinusNode(Node in) { super(null, in); } + public MinusNode(Node in, byte mode) { super(null, in); _mode = mode; } + - @Override public String label() { return "Minus"; } + @Override public byte mode() { return _mode; } + @Override public Node setMode(byte mode) { + assert _mode==0 && (mode==1 || mode==2); + unlock(); // _mode participates in GVN hash and equality + _mode = mode; + return this; + } @Override protected String format() { return "(-%1)"; } @Override public Type compute() { - 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,i0._widen); - return TypeInteger.BOT; + Type t = in(1)._type; + if( t==null ) + return Type.TOP; + if( t.isHigh() ) + return _mode==0 ? Type.TOP : + _mode==1 ? TypeInteger.TOP : + t instanceof TypeFloat ? t : TypeFloat.F64.dual(); + byte mode = _mode; + if( mode==0 ) { + if( t instanceof TypeFloat ) mode=2; + if( t instanceof TypeInteger ) mode=1; + } + if( mode==0 ) + return CodeGen.CODE._phase.ordinal() < CodeGen.Phase.Opto.ordinal() ? Type.BOTTOM : Type.TOP; + if( mode==1 ) { + if( t instanceof TypeInteger i0 && + i0._min != Long.MIN_VALUE && i0._max != Long.MIN_VALUE ) + return TypeInteger.make(-i0._max,-i0._min,i0._widen); + return TypeInteger.BOT; + } + if( t instanceof TypeFloat f ) + return f.isConstant() ? TypeFloat.constant(-f.value()) : f; + return TypeFloat.F64; } @Override public Node idealize() { // -(-x) is x - if( in(1) instanceof MinusNode minus && addDep(minus.in(1))._type instanceof TypeInteger ) + if( in(1) instanceof MinusNode minus && addDep(minus.in(1))._type.isa(compute()) ) return minus.in(1); + // Can we decide int vs flt? + if( _mode==0 ) { + byte mode = (byte)( + in(1)._type instanceof TypeInteger ? 1 : + in(1)._type instanceof TypeFloat ? 2 : 0); + if( mode!=0 ) return setMode(mode).init(); + } + return null; } - @Override Node copyF() { return new MinusFNode(null); } + @Override public Parser.ParseException err() { + return ArithNode.nodeErr(this,null,"-",_mode,true); + } + @Override public boolean eq( Node n ) { return _mode==((MinusNode)n)._mode; } + @Override public int hash() { return _mode; } } diff --git a/src/main/java/com/seaofnodes/simple/node/ModeNode.java b/src/main/java/com/seaofnodes/simple/node/ModeNode.java new file mode 100644 index 00000000..dc635447 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ModeNode.java @@ -0,0 +1,12 @@ +package com.seaofnodes.simple.node; + +/** + * A node whose numeric input family is selected once: unknown, integer, or + * floating point. Implementors remain ordinary Nodes; this interface only + * centralizes the structural mode contract shared by arithmetic, comparisons, + * and unary minus. + */ +public interface ModeNode { + byte mode(); + Node setMode(byte mode); +} diff --git a/src/main/java/com/seaofnodes/simple/node/MulFNode.java b/src/main/java/com/seaofnodes/simple/node/MulFNode.java index 5c04af43..1126319b 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulFNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulFNode.java @@ -7,6 +7,7 @@ import java.util.BitSet; public class MulFNode extends ArithFNode { public MulFNode(Node lhs, Node rhs) { super(lhs, rhs); } + public MulFNode(ArithNode n) { super(n); } @Override public String label() { return "MulF"; } diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index 6e1dc053..37d6a2bc 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -1,17 +1,19 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import java.util.BitSet; public class MulNode extends ArithNode { + @Override boolean allowFloat() { return true; } public MulNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + public MulNode(Node lhs, Node rhs, byte mode) { super(null, lhs, rhs, mode); } - @Override public String label() { return "Mul"; } @Override public String op() { return "*"; } - @Override long doOp( long x, long y ) { return x * y; } + @Override long doOp( long x, long y ) { return x * y; } + @Override double doOp(double x, double y ) { return x * y; } @Override TypeInteger doOp(TypeInteger x, TypeInteger y) { return TypeInteger.BOT; } @@ -32,8 +34,8 @@ public class MulNode extends ArithNode { // Mul of 1. We do not check for (1*x) because this will already // canonicalize to (x*1) long c = i.value(); - if( c==1 ) return lhs._type instanceof TypeInteger ? lhs : null; - if( c==0 ) return Parser.ZERO; + if( c==1 ) return lhs._type.isa(compute()) ? lhs : super.idealize(); + if( c==0 ) return com.seaofnodes.simple.Parser.ZERO; // Mul by a power of 2, +/-1. Bit patterns more complex than this // are unlikely to win on an X86 vs the normal "imul", and so // become machine-specific. @@ -58,6 +60,5 @@ public class MulNode extends ArithNode { return super.idealize(); } - @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); } - @Override Node copyF() { return new MulFNode(null,null); } + @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs,_mode); } } diff --git a/src/main/java/com/seaofnodes/simple/node/NewNode.java b/src/main/java/com/seaofnodes/simple/node/NewNode.java index 840d2759..bdcdfdfc 100644 --- a/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -14,7 +14,7 @@ import com.seaofnodes.simple.util.Utils; */ public class NewNode extends Node implements MultiNode { - public final TypeMemPtr _ptr; + public TypeMemPtr _ptr; public NewNode(TypeMemPtr ptr, Node... nodes) { super(nodes); @@ -29,6 +29,14 @@ public class NewNode extends Node implements MultiNode { public Node mem() { return in(1); } public Node size() { return in(2); } + @Override boolean _upgradeType(java.util.HashMap<String,Type> types) { + TypeMemPtr ptr = (TypeMemPtr)_ptr.upgradeType(types); + if( ptr==_ptr ) return false; + unlock(); + _ptr = ptr; + return true; + } + public Field field(int alias) { for( Field f : _ptr._obj._fields ) if( !f._one && f._alias==alias ) return f; diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 414530b4..230593a8 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -71,7 +71,7 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { } // Easy reading label for debugger, e.g. "Add" or "Region" or "EQ" - public abstract String label(); + public String label() { return getClass().getSimpleName().replace("Node",""); } public String p(int depth) { return IRPrinter.prettyPrint(this,depth); } @@ -690,4 +690,16 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { for( Node use : _outputs ) if( use != null && (x = use._find(nid,bs)) != null ) return x; return null; } + + boolean _upgradeType(java.util.HashMap<String,Type> types) { return false; } + public final void upgradeType(java.util.HashMap<String,Type> types) { + Type old = _type; + _type = _type.upgradeType(types); + boolean progress = _upgradeType(types); + if( progress || old!=_type ) { + CODE.add(this); + CODE.addAll(_outputs); + moveDepsToWorklist(); + } + } } diff --git a/src/main/java/com/seaofnodes/simple/node/OrNode.java b/src/main/java/com/seaofnodes/simple/node/OrNode.java index d16dd194..618c5340 100644 --- a/src/main/java/com/seaofnodes/simple/node/OrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/OrNode.java @@ -5,7 +5,7 @@ import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; public class OrNode extends ArithNode { - public OrNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs); } + public OrNode( Parser.Lexer loc, Node lhs, Node rhs) { super(loc,lhs, rhs, (byte)1); } @Override public String label() { return "Or"; } @Override public String op() { return "|"; } @@ -18,12 +18,13 @@ public class OrNode extends ArithNode { public Node idealize() { Node lhs = in(1); Node rhs = in(2); + Type t1 = lhs._type; Type t2 = rhs._type; // Or of 0. We do not check for (0|x) because this will already // canonicalize to (x|0) - if( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==0 && lhs._type instanceof TypeInteger ) + if( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==0 && t1.isa(TypeInteger.BOT) && forceInt(lhs) ) return lhs; // Move constants to RHS: con*arg becomes arg*con diff --git a/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/src/main/java/com/seaofnodes/simple/node/ParmNode.java index cc654abb..52fe5704 100644 --- a/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -10,13 +10,15 @@ import com.seaofnodes.simple.type.TypeMemPtr; public class ParmNode extends PhiNode { // Argument indices are mapped one-to-one on CallNode inputs + private Type _declaredType; public final int _idx; // Argument index public ParmNode(String label, int idx, Type declaredType, Node... inputs) { - super(label,declaredType,inputs); + super(label,inputs); _idx = idx; + _declaredType = declaredType; } - public ParmNode(ParmNode parm) { super(parm, parm._label, parm._minType ); _idx = parm._idx; } + public ParmNode(ParmNode parm) { super(parm, parm._label, parm._declaredType ); _idx = parm._idx; _declaredType = parm._declaredType; } @Override public String label() { return MemOpNode.mlabel(_label); } @@ -37,7 +39,7 @@ public class ParmNode extends PhiNode { @Override public Type compute() { - Type t = super.compute(); + Type t = inProgress() ? _declaredType : super.compute().join(_declaredType); // Recursion is a loop in disguise. A Parm merges the first argument // with those from recursive calls, just as a loop Phi merges its entry // and backedge. Use the widening rule in PhiNode.compute here too. @@ -46,7 +48,7 @@ public class ParmNode extends PhiNode { if( t instanceof TypeInteger ti && t != _type && !ti.isHigh() && !ti.isConstant() && (!(_type instanceof TypeInteger oldi) || ti._widen <= oldi._widen) ) - return ti.same_but_slightly_wider_than(_minType); + return ti.same_but_slightly_wider_than(_declaredType); return t; } @@ -58,10 +60,10 @@ public class ParmNode extends PhiNode { if( fun()._folding ) return super.idealize(); // Can upgrade minType even while in-progress - if( _minType instanceof TypeMemPtr tmp && _minType.isFRef() ) { + if( _declaredType instanceof TypeMemPtr tmp && _declaredType.isFRef() ) { TypeMemPtr tmp2 = (TypeMemPtr) Parser.TYPES.get(tmp._obj._name); - if( tmp2!=null && tmp2 != _minType ) { - _minType = tmp2; + if( tmp2!=null && tmp2 != _declaredType ) { + _declaredType = tmp2; return this; } } @@ -72,4 +74,12 @@ public class ParmNode extends PhiNode { @Override public boolean eq( Node n ) { return ((ParmNode)n)._idx==_idx && super.eq(n); } + + @Override boolean _upgradeType(java.util.HashMap<String,Type> types) { + Type next = _declaredType.upgradeType(types); + if( next==_declaredType ) return false; + unlock(); + _declaredType=next; + return true; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 7f2bb1f4..064852e4 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -11,33 +11,27 @@ public class PhiNode extends Node { public final String _label; - // The Phi type we compute must stay within the domain of the Phi. Example - // Int stays Int, Ptr stays Ptr, Control stays Control, Mem stays Mem. - Type _minType; - int lattice_drop; - public PhiNode(String label, Type minType, Node... inputs) { + public PhiNode(String label, Node... inputs) { super(inputs); _label = label; - assert minType!=null; - _minType = minType; } // Used by ParmNode - public PhiNode(PhiNode phi, String label, Type minType) { super(phi); _label = label; _type = _minType = minType; } + public PhiNode(PhiNode phi, String label, Type type) { super(phi); _label = label; _type = type; } // Used by instruction Selection - public PhiNode(PhiNode phi) { this(phi,phi._label,phi._minType ); } + public PhiNode(PhiNode phi) { this(phi,phi._label,phi._type ); } // Used by the infinite-loop exit breaker public PhiNode(RegionNode r, Node sample) { super(new Node[]{r}); _label = ""; - _minType = sample._type; + _type = sample._type; while( nIns() < r.nIns() ) addDef(sample); } public static PhiNode make(String label, Type type, Node... inputs) { - return type instanceof TypeMem ? new BulkMemPhiNode(label,inputs) : new PhiNode(label,type,inputs); + return type instanceof TypeMem ? new BulkMemPhiNode(label,inputs) : new PhiNode(label,inputs); } @Override public String label() { return "Phi_"+MemOpNode.mlabel(_label); } @@ -52,7 +46,7 @@ public class PhiNode extends Node { } public CFGNode region() { return (CFGNode)in(0); } - @Override public boolean isMem() { return _minType instanceof TypeMem; } + @Override public boolean isMem() { return _type instanceof TypeMem; } boolean isRPC() { return false; } @Override @@ -61,11 +55,9 @@ public class PhiNode extends Node { 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() || 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; + // The backedge has not been parsed. Declarations belong on + // Convert/Parm nodes; an unfinished value Phi knows no bound. + return Type.BOTTOM; // Set type to local top of the starting type Type t = Type.TOP; for (int i = 1; i < nIns(); i++) { @@ -78,7 +70,7 @@ public class PhiNode extends Node { t = t.meet(in(i)._type); } } - Type newt = t.join( _minType ); + Type newt = t; // Widen loop Phis so integer ranges cannot grow one step per trip forever. // Recursion is a loop in disguise: ParmNode.compute widens arguments, @@ -91,7 +83,7 @@ public class PhiNode extends Node { // 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 newi.same_but_slightly_wider_than(TypeInteger.BOT); } return newt; @@ -101,27 +93,12 @@ public class PhiNode extends Node { public Node idealize() { if( !(region() instanceof RegionNode r ) ) 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) Parser.TYPES.get(tmp._obj._name); - if( tmp2!=null && tmp2._obj != tmp._obj ) { - _minType = tmp.makeFrom(tmp2._obj); - return this; - } - } - if( r.inProgress() || r.nIns()<=1 ) + if( r.inProgress() || inProgress() || r.nIns()<=1 ) return null; // Input is in-progress // If we have only a single unique input, become it. Node live = singleUniqueInput(); - if( live != null ) { - if( live._type.isa(_type) ) - return live; - // Let the bulk input split this alias before collapsing a precise Phi. - if( live instanceof BulkMemPhiNode ) return null; - // Keep the Phi upcast - return new CastNode(_type,null,live); - } + if( live != null ) return live; // No bother if region is going to fold dead paths soon for( int i=1; i<nIns(); i++ ) @@ -132,6 +109,13 @@ public class PhiNode extends Node { Node down; if( same_op() && (down=drop_same_op())!=null ) return down; + if( nIns()==3 ) { + Node merge = matchingGuardMerge(r,1); + if( merge!=null ) return merge; + merge = matchingGuardMerge(r,2); + if( merge!=null ) return merge; + } + // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. if( nIns()==3 ) { if( in(1) instanceof CastNode cast && addDep(cast.in(1))==in(2) ) return in(2); @@ -162,6 +146,25 @@ public class PhiNode extends Node { return null; } + private Node matchingGuardMerge(RegionNode r, int nzIdx) { + Node zero = in(3-nzIdx); + if( !(in(nzIdx) instanceof GuardNode guard && guard._nonZero) || + zero==null || zero._type.makeZero()!=zero._type || guard.in(1)==this ) + return null; + if( !(r.in(nzIdx) instanceof CProjNode nz && nz._idx==0 && nz.ctrl() instanceof IfNode iff) ) + return null; + if( !(r.in(3-nzIdx) instanceof CProjNode z && z._idx==1 && z.ctrl()==iff) ) + return null; + Node n=guard.in(1), tested=null; + while( true ) { + if( iff.pred()==n ) tested=n; + if( !(n instanceof GuardNode g && g._nonZero) ) break; + n=g.in(1); + } + // The source must exist before the join, not just on its guarded arm. + return tested!=null && ScopeNode.availableAt(n,r,new java.util.BitSet()) ? n : null; + } + // Same op on all Phi paths; all ops have only the Phi as a use. // None have a control input. private boolean same_op() { @@ -274,21 +277,13 @@ public class PhiNode extends Node { // Never equal if inProgress. // Also, joins - @Override public boolean eq( Node n ) { - if( inProgress() ) return false; - Type min = ((PhiNode)n)._minType; - if( _minType==min ) return true; - Type mt = min.meet(_minType); - if( min!=mt && _minType!=mt ) return false; - //// Theory says these 2 Phis CAN be merged/GVNd, but I need to pick the - //// most general minType. - //_minType = ((PhiNode)n)._minType = mt; - //return true; - return false; - } + @Override public boolean eq(Node n) { return !inProgress(); } @Override public Parser.ParseException err() { + if( inProgress() ) return null; + // A scalar union is useful for truth tests, e.g. !(ptr || integer). + // A typed consumer reports an invalid use of that union itself. if( _type != Type.BOTTOM ) return null; // BOTTOM means we mixed e.g. int and ptr diff --git a/src/main/java/com/seaofnodes/simple/node/PtrToIntMach.java b/src/main/java/com/seaofnodes/simple/node/PtrToIntMach.java new file mode 100644 index 00000000..9a9b94fd --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/PtrToIntMach.java @@ -0,0 +1,17 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.Encoding; +import com.seaofnodes.simple.codegen.RegMask; +import com.seaofnodes.simple.util.SB; + +/** Zero-code machine form of {@link PtrToIntNode}. */ +public class PtrToIntMach extends PtrToIntNode implements MachNode { + public PtrToIntMach(PtrToIntNode ptr) { super(ptr); } + @Override public String op() { return label(); } + @Override public RegMask regmap(int i) { assert i==1; return RegMask.FULL; } + @Override public RegMask outregmap() { return RegMask.FULL; } + @Override public int twoAddress() { return 1; } + @Override public void encoding(Encoding enc) { } + @Override public void asm(CodeGen code, SB sb) { sb.p(code.reg(in(1))); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/PtrToIntNode.java b/src/main/java/com/seaofnodes/simple/node/PtrToIntNode.java new file mode 100644 index 00000000..55c0fc02 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/PtrToIntNode.java @@ -0,0 +1,35 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.type.TypeMemPtr; + + +/** + * Reinterpret a non-null managed pointer as its raw integer address. + * + * This node changes representation families but emits no code. No + * control-dependent proof can turn a pointer into an integer; array-to-C-pointer + * conversion adds the array body offset separately. + */ +public class PtrToIntNode extends Node { + public PtrToIntNode(Node ptr) { super(null,ptr); } + public PtrToIntNode(PtrToIntNode ptr) { super(ptr); } + + @Override protected String format() { return "(i64*)%1"; } + + @Override public Type compute() { + return in(1)._type.isHigh() ? TypeInteger.TOP : TypeInteger.BOT; + } + + @Override public Node idealize() { return null; } + + @Override public Parser.ParseException err() { + Type t = in(1)._type; + if( t instanceof TypeMemPtr ptr ) + return ptr.notNull() ? null : Parser.error("Cannot convert a nullable pointer to an integer",null); + return Parser.error("Cannot convert "+t.str()+" to an integer pointer",null); + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 266657be..8fea803d 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -91,8 +91,8 @@ public class ReturnNode extends CFGNode { // Merge path into the One True Return RegionNode r = (RegionNode)ctrl(); // Assert that the Phis are in particular outputs; not reordered or shuffled - PhiNode mem = (PhiNode)r.out(0); assert mem._minType == TypeMem.BOT; - PhiNode rez = (PhiNode)r.out(1); assert rez._minType == Type.BOTTOM; + PhiNode mem = (PhiNode)r.out(0); assert mem.isMem(); + PhiNode rez = (PhiNode)r.out(1); assert !rez.isMem(); // Pop "inProgress" null off r ._inputs.pop(); mem._inputs.pop(); @@ -109,7 +109,26 @@ public class ReturnNode extends CFGNode { @Override public Parser.ParseException err() { 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; + if( expr()._type==TypeScalar.BOT ) { + int kinds = returnKinds(expr(),new java.util.BitSet()); + return mixerr((kinds&1)!=0,(kinds&2)!=0,(kinds&4)!=0,(kinds&8)!=0,_fun._loc); + } + return expr()._type==Type.BOTTOM || expr()._type==Type.TOP || expr()._type==TypeScalar.BOT ? mixerr(ti,tf,tp,tn,_fun._loc) : null; + } + + private static int returnKinds(Node n, java.util.BitSet visit) { + if( n==null || visit.get(n._nid) ) return 0; + visit.set(n._nid); + Type t=n._type; + if( t instanceof TypeInteger ) return 1; + if( t instanceof TypeFloat ) return 2; + if( t instanceof TypeMemPtr || t instanceof TypeFunPtr ) return 4; + if( t==Type.NIL ) return 8; + int kinds=0; + if( n instanceof PhiNode phi ) + for( int i=1; i<n.nIns(); i++ ) + if( phi.region().in(i)._type==Type.CONTROL ) kinds |= returnKinds(n.in(i),visit); + return kinds; } static Parser.ParseException mixerr( boolean ti, boolean tf, boolean tp, boolean tn, Parser.Lexer loc ) { diff --git a/src/main/java/com/seaofnodes/simple/node/SarNode.java b/src/main/java/com/seaofnodes/simple/node/SarNode.java index 429be229..54611b0d 100644 --- a/src/main/java/com/seaofnodes/simple/node/SarNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SarNode.java @@ -5,9 +5,8 @@ import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; public class SarNode extends ArithNode { - public SarNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs); } + public SarNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } - @Override public String label() { return "Sar"; } @Override public String op() { return ">>"; } @Override long doOp( long x, long y ) { return x >> y; } @Override TypeInteger doOp( TypeInteger x, TypeInteger y ) { @@ -22,10 +21,11 @@ public class SarNode extends ArithNode { public Node idealize() { Node lhs = in(1); Node rhs = in(2); + Type t2 = rhs._type; // Sar of 0. - if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 && lhs._type instanceof TypeInteger ) + if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 && forceInt(lhs) && lhs._type instanceof TypeInteger ) return lhs; // TODO: x >> 3 >> (y ? 1 : 2) ==> x >> (y ? 4 : 5) diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 307fc0f9..3c1e9776 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -427,21 +427,14 @@ public class ScopeNode extends Node { pred = pred instanceof NotNode not ? not.in(1) : CodeGen.CODE.add(new NotNode(pred).peephole()); // This is a zero/null test. // Compute the positive test type. - Type tnz = pred._type.nonZero(); - if( tnz!=null ) - _addGuard(tnz,ctrl,pred); - - // Compute the negative test type. - if( pred instanceof NotNode not ) { - Node npred = not.in(1); - Type tzero = npred._type.makeZero(); - _addGuard(tzero,ctrl,npred); - } + _addGuard(true,ctrl,pred); + if( pred instanceof NotNode not ) + _addGuard(false,ctrl,not.in(1)); } // A Phi's value is available at its Region. Other data nodes require all // their inputs, including pinned control, to dominate the proposed guard. - private static boolean availableAt(Node n, CFGNode ctrl, BitSet visit) { + static boolean availableAt(Node n, CFGNode ctrl, BitSet visit) { if( n==null || n instanceof ConstantNode || visit.get(n._nid) ) return true; visit.set(n._nid); if( n instanceof PhiNode phi ) n = phi.region(); @@ -468,17 +461,15 @@ public class ScopeNode extends Node { return null; } - private void _addGuard(Type guard, Node ctrl, Node pred) { - Type tcast = guard.join(pred._type); - if( tcast != pred._type && !tcast.isHigh() ) { - Node cast = new CastNode(tcast,ctrl,pred.keep()).peephole().keep(); - _guards.add(pred); - _guards.add(cast); - replace(pred,cast); - } + private void _addGuard(boolean nonZero, Node ctrl, Node pred) { + Node guard = new GuardNode(nonZero,ctrl,pred.keep()).peephole(); + if( guard==pred ) { pred.unkeep(); return; } + guard.keep(); + _guards.add(pred); + _guards.add(guard); + replace(pred,guard); } - // Remove matching pred/cast pairs from this guarded region. public ScopeNode removeGuards( Node ctrl ) { assert ctrl instanceof CFGNode; diff --git a/src/main/java/com/seaofnodes/simple/node/ShlNode.java b/src/main/java/com/seaofnodes/simple/node/ShlNode.java index e2951784..7d6e8e2e 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShlNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -1,13 +1,13 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; public class ShlNode extends ArithNode { - public ShlNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs); } + public ShlNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } - @Override public String label() { return "Shl"; } @Override public String op() { return "<<"; } @Override long doOp( long x, long y ) { return x << y; } @Override TypeInteger doOp( TypeInteger x, TypeInteger y ) { @@ -30,13 +30,13 @@ public class ShlNode extends ArithNode { if( rhs._type instanceof TypeInteger shl && shl.isConstant() ) { // Shl of 0. - if( (shl.value()&63)==0 && lhs._type instanceof TypeInteger ) + if( (shl.value()&63)==0 && forceInt(lhs) && lhs._type instanceof TypeInteger ) return lhs; // (x + c) << i => (x << i) + (c << i) if( lhs instanceof AddNode add && addDep(add).in(2)._type instanceof TypeInteger c && c.isConstant() ) { long sum = c.value() << shl.value(); if( Integer.MIN_VALUE <= sum && sum <= Integer.MAX_VALUE ) - return new AddNode(new ShlNode(_loc,add.in(1),rhs).peephole(), Parser.con(sum) ); + return new AddNode(new ShlNode(_loc,add.in(1),rhs).peephole(), com.seaofnodes.simple.Parser.con(sum) ); } } diff --git a/src/main/java/com/seaofnodes/simple/node/ShrNode.java b/src/main/java/com/seaofnodes/simple/node/ShrNode.java index 0023431f..4ce5f5b4 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -5,9 +5,8 @@ import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; public class ShrNode extends ArithNode { - public ShrNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs); } + public ShrNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } - @Override public String label() { return "Shr"; } @Override public String op() { return ">>>"; } @Override long doOp( long x, long y ) { return x >>> y; } @Override TypeInteger doOp( TypeInteger x, TypeInteger y ) { @@ -21,7 +20,7 @@ public class ShrNode extends ArithNode { Type t2 = rhs._type; // Shr of 0. - if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 && lhs._type instanceof TypeInteger ) + if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 && forceInt(lhs) && lhs._type instanceof TypeInteger ) return lhs; // TODO: x >>> 3 >>> (y ? 1 : 2) ==> x >>> (y ? 4 : 5) diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 47f12d82..a4abaa1d 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -43,6 +43,7 @@ public class StoreNode extends MemOpNode { @Override public Type compute() { + if( _alias==1 ) return TypeMem.BOT; Type val = val()._type; assert !_declaredType.isFRef(); Type t = val.join(_declaredType).meet(MemMergeNode.contents(mem(),_alias,this)); @@ -51,6 +52,15 @@ public class StoreNode extends MemOpNode { @Override public Node idealize() { + if( _alias==1 ) { + if( !(ptr()._type instanceof TypeMemPtr ptr) || ptr._obj._open ) return null; + Field field = ptr._obj.field(_name); + if( field==null ) return null; + Node value = new ConvertNode(field._t,val()).peephole(); + StoreNode store = new StoreNode(_loc,_name,field._alias,field._t,mem(),ptr(),off(),value,_init); + store.setDef(0,in(0)); + return new MemMergeNode(mem(),field._alias,store.peephole()); + } if( mem() instanceof MemMergeNode merge ) { setDef(1,CodeGen.CODE.add(merge.alias(_alias))); return this; @@ -138,8 +148,8 @@ public class StoreNode extends MemOpNode { if( ctrl==null ) return null; Node mem = phi.in(1); - Node init = new LoadNode(_loc,_name,_alias,_declaredType,mem,ptr(),off()).peephole(); - Node value = CodeGen.CODE.add(new PhiNode(_name,_declaredType,loop,init,val()).peephole()); + Node init = new LoadNode(_loc,_name,_alias,mem,ptr(),off()).peephole(); + Node value = CodeGen.CODE.add(new PhiNode(_name,loop,init,val()).peephole()); Node sink = new StoreNode(_loc,_name,_alias,_declaredType,mem,ptr(),off(),value,_init); // Break the memory cycle, killing the old store. Keep the Phi alive // even if that store was its last use, until our caller replaces it. @@ -164,10 +174,11 @@ 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._ro || tmp._obj.field(_name)._final) && !_init ) + if( !(ptr()._type instanceof TypeMemPtr tmp) ) + return null; // Report the bad or unresolved receiver at its source. + Field field = tmp._obj.field(_name); + if( field==null ) return Parser.error("Cannot resolve field '"+_name+"'",_loc); + if( (tmp._ro || field._final) && !_init ) return Parser.error("Cannot modify final field '"+_name+"'",_loc); return null; } diff --git a/src/main/java/com/seaofnodes/simple/node/StructNode.java b/src/main/java/com/seaofnodes/simple/node/StructNode.java index 78b20e9f..a91ee5de 100644 --- a/src/main/java/com/seaofnodes/simple/node/StructNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StructNode.java @@ -10,9 +10,18 @@ import com.seaofnodes.simple.util.SB; */ public class StructNode extends Node { - public final TypeStruct _ts; + public TypeStruct _ts; public StructNode(TypeStruct ts) { _ts=ts; assert !ts._open; } + @Override boolean _upgradeType(java.util.HashMap<String,Type> types) { + if( _ts==null ) return false; + TypeStruct ts = (TypeStruct)_ts.upgradeType(types); + if( ts==_ts ) return false; + unlock(); + _ts = ts; + return true; + } + @Override public String label() { return _ts==null ? "STRUCT?" : _ts.str(); } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/src/main/java/com/seaofnodes/simple/node/SubFNode.java index 3fc4f7ca..d6a908ca 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubFNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubFNode.java @@ -7,6 +7,7 @@ import java.util.BitSet; public class SubFNode extends ArithFNode { public SubFNode(Node lhs, Node rhs) { super(lhs, rhs); } + public SubFNode(ArithNode n) { super(n); } @Override public String label() { return "SubF"; } diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index 2c4fed39..c47ffb3b 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -6,12 +6,14 @@ import com.seaofnodes.simple.type.TypeInteger; import java.util.BitSet; public class SubNode extends ArithNode { + @Override boolean allowFloat() { return true; } public SubNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + public SubNode(Node lhs, Node rhs, byte mode) { super(null, lhs, rhs,mode); } - @Override public String label() { return "Sub"; } @Override public String op() { return "-"; } - @Override long doOp( long x, long y ) { return x - y; } + @Override long doOp( long x, long y ) { return x - y; } + @Override double doOp(double x, double y ) { return x - y; } @Override TypeInteger doOp(TypeInteger x, TypeInteger y) { // Sub of same is 0 if( in(1)==in(2) ) @@ -32,8 +34,8 @@ public class SubNode extends ArithNode { Type t1 = lhs._type; Type t2 = rhs._type; - // Keep invalid operands for type checking. - if( t1 instanceof TypeInteger x && t2 instanceof TypeInteger y ) { + // Keep invalid operands and unresolved numeric modes for type checking. + if( _mode==1 && t1 instanceof TypeInteger x && t2 instanceof TypeInteger y ) { if( y.isConstant() && y.value()==0 ) return lhs; if( x.isConstant() && x.value()==0 ) return new MinusNode(rhs); } @@ -49,6 +51,5 @@ public class SubNode extends ArithNode { return super.idealize(); } - @Override Node copy(Node lhs, Node rhs) { return new SubNode(lhs,rhs); } - @Override Node copyF() { return new SubFNode(null,null); } + @Override Node copy(Node lhs, Node rhs) { return new SubNode(lhs,rhs,_mode); } } diff --git a/src/main/java/com/seaofnodes/simple/node/XorNode.java b/src/main/java/com/seaofnodes/simple/node/XorNode.java index 75cea98e..e3dac2d0 100644 --- a/src/main/java/com/seaofnodes/simple/node/XorNode.java +++ b/src/main/java/com/seaofnodes/simple/node/XorNode.java @@ -5,9 +5,8 @@ import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; public class XorNode extends ArithNode { - public XorNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs); } + public XorNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } - @Override public String label() { return "Xor"; } @Override public String op() { return "^"; } @Override long doOp( long x, long y ) { return x ^ y; } @Override TypeInteger doOp( TypeInteger x, TypeInteger y ) { @@ -18,12 +17,13 @@ public class XorNode extends ArithNode { public Node idealize() { Node lhs = in(1); Node rhs = in(2); + Type t1 = lhs._type; Type t2 = rhs._type; // Xor of 0. We do not check for (0^x) because this will already // canonicalize to (x^0) - if( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==0 && lhs._type instanceof TypeInteger ) + if( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==0 && forceInt(lhs) && lhs._type instanceof TypeInteger ) return lhs; // Move constants to RHS: con*arg becomes arg*con diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallARM.java b/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallARM.java index e1717cb3..b6d82f09 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallARM.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallARM.java @@ -15,7 +15,7 @@ public class CallARM extends CallNode implements MachNode, RIPRelSize { assert tfp.isConstant(); _tfp = tfp; FunNode fun = CodeGen.CODE.link(tfp); - _name = fun==null ? ((ExternNode)call.fptr())._extern : fun._name; // Can be null for extern calls + _name = fun==null ? CodeGen.CODE.externFunc(tfp) : fun._name; } @Override public String op() { return "call"; } 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 fae98a99..0d5b5440 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 @@ -359,7 +359,7 @@ public class arm extends Machine { String op = "!="; if( iff.in(1) instanceof BoolNode bool ) op = bool.op(); else if( iff.in(1)==null ) op = "=="; // Never-node cutout - else iff.setDef(1, new BoolNode.NE(iff.in(1), new ConstantNode(TypeInteger.ZERO))); + else iff.setDef(1, new BoolNode.NE(iff.in(1), new ConstantNode(TypeInteger.ZERO),(byte)1)); return new BranchARM(iff, op); } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRISC.java b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRISC.java index f0ad8e88..03bedd0d 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRISC.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRISC.java @@ -16,7 +16,7 @@ public class CallRISC extends CallNode implements MachNode, RIPRelSize { _inputs.pop(); // Pop constant target _tfp = tfp; FunNode fun = CodeGen.CODE.link(tfp); - _name = fun==null ? ((ExternNode)call.fptr())._extern : fun._name; // Can be null for extern calls + _name = fun==null ? CodeGen.CODE.externFunc(tfp) : fun._name; } @Override public String op() { return "call"; } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java index d1a43b83..cd4d2452 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java @@ -15,7 +15,7 @@ public class CallX86 extends CallNode implements MachNode, RIPRelSize { assert tfp.isConstant(); _tfp = tfp; FunNode fun = CodeGen.CODE.link(tfp); - _name = fun==null ? ((ExternNode)call.fptr())._extern : fun._name; // Can be null for extern calls + _name = fun==null ? CodeGen.CODE.externFunc(tfp) : fun._name; } @Override public String op() { return "call"; } @Override public String label() { return op(); } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java index fcae17f8..f0598422 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java @@ -441,7 +441,7 @@ public class x86_64_v2 extends Machine { String op = "!="; if( iff.in(1) instanceof BoolNode bool ) op = swap ? IfNode.swap(bool.op()) : bool.op(); else if( iff.in(1)==null ) op = "=="; // Never-node cutout - else iff.setDef(1, new BoolNode.NE(iff.in(1), new ConstantNode(TypeInteger.ZERO))); + else iff.setDef(1, new BoolNode.NE(iff.in(1), new ConstantNode(TypeInteger.ZERO),(byte)1)); return new JmpX86(iff, op); } diff --git a/src/main/java/com/seaofnodes/simple/type/Field.java b/src/main/java/com/seaofnodes/simple/type/Field.java index 1f22cb05..1396f1de 100644 --- a/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/src/main/java/com/seaofnodes/simple/type/Field.java @@ -105,7 +105,7 @@ public class Field extends Type { Type glb = _t._glb(true); return (glb== _t && _final ) ? this : make(_fname,glb,_alias,true,_one); } - @Override Field _close() { return makeFrom( _t._close()); } + @Override Field _close(java.util.HashMap<String,Type> types) { return makeFrom( _t._close(types)); } // Override in subclasses int hash() { return _fname.hashCode() ^ _t.hashCode() ^ _alias ^ (_final ? 1024 : 0) ^ (_one ? 2048 : 0); } diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index b9a6a1f3..9fad2767 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -57,6 +57,7 @@ public class Type /*implements Cloneable*/ { static final byte TNIL = 4; // low null of all flavors static final byte TXNIL = 5; // high or choice null static final byte TSIMPLE = 6; // End of the Simple Types + static final byte TSCALAR = 6; // All register/field values, excluding control and memory static final byte TPTR = 7; // All nil-able scalar values static final byte TINT = 8; // All Integers; see TypeInteger @@ -97,6 +98,7 @@ public class Type /*implements Cloneable*/ { ts.add(BOTTOM); ts.add(CONTROL); ts.add(NIL); + TypeScalar.gather(ts); TypeNil.gather(ts); TypePtr.gather(ts); TypeInteger.gather(ts); @@ -267,6 +269,8 @@ public class Type /*implements Cloneable*/ { // Constant arrays meet their integer element types. if( this instanceof TypeConAry tcon && t instanceof TypeInteger ti ) return tcon.ymeet(ti); if( t instanceof TypeConAry tcon && this instanceof TypeInteger ti ) return tcon.ymeet(ti); + if( this instanceof TypeScalar scalar0 && t instanceof TypeScalar scalar1 ) + return scalar0.smeet(scalar1); return Type.BOTTOM; // Mixing 2 unrelated types } @@ -280,8 +284,14 @@ public class Type /*implements Cloneable*/ { if( _type==TTOP || t._type==TBOT ) return t; // RHS TypeNil vs NIL/XNIL - if( _type== TNIL ) return t instanceof TypeNil ptr ? ptr.meet0() : (t._type==TXNIL ? TypePtr.PTR : BOTTOM); - if( _type== TXNIL ) return t instanceof TypeNil ptr ? ptr.meetX() : (t._type== TNIL ? TypePtr.PTR : BOTTOM); + if( _type==TNIL || _type==TXNIL ) { + if( t instanceof TypeNil ptr ) return _type==TNIL ? ptr.meet0() : ptr.meetX(); + if( t instanceof TypeScalar ) { + if( t._type==TSCALAR ) return t.isHigh() ? this : t; + return TypeScalar.BOT; + } + return t._type==(_type==TNIL ? TXNIL : TNIL) ? TypePtr.PTR : BOTTOM; + } // 'this' is only {TCTRL,TXCTRL} // Other non-simple RHS things bottom out @@ -487,7 +497,7 @@ public class Type /*implements Cloneable*/ { } Type _glb(boolean mem) { assert is_simple(); return Type.BOTTOM; } - Type _close() { return this; } + Type _close(HashMap<String,Type> types) { return this; } public Type widen() { return this; } // ---------------------------------------------------------- @@ -523,4 +533,11 @@ public class Type /*implements Cloneable*/ { // This is used by error messages, and is a shorted print. public String str() { return STRS[_type]; } + + // Closing declarations changes the meaning of forward shapes. Upgrade + // the whole graph together before starting the pessimistic fixed point. + public final Type upgradeType(HashMap<String,Type> types) { + return recurOpen()._upgradeType(types).recurClose(); + } + Type _upgradeType(HashMap<String,Type> types) { 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 0bc264fc..d7ce8503 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeConAry.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeConAry.java @@ -7,7 +7,7 @@ import java.util.ArrayList; /** * Represents a constant array of primitives */ -public abstract class TypeConAry<A> extends Type { +public abstract class TypeConAry<A> extends TypeScalar { boolean _any; byte _widen; // One of byte or int array diff --git a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java index f3de581c..bb00ee91 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java @@ -8,7 +8,7 @@ import java.util.ArrayList; /** * Float Type */ -public class TypeFloat extends Type { +public class TypeFloat extends TypeScalar { // - high -64, high -32, con 0, low +32, low +64 public byte _sz; diff --git a/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java index 50743f69..602aaaae 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java @@ -157,13 +157,13 @@ public class TypeFunPtr extends TypeNil { @Override boolean _isFinal() { return true; } @Override boolean _isGLB(boolean mem) { return true; } @Override TypeFunPtr _glb(boolean mem) { return this; } - @Override TypeFunPtr _close() { + @Override TypeFunPtr _close(java.util.HashMap<String,Type> types) { Type[] sig = new Type[_sig.length]; TypeFunPtr fun = malloc(_nil,false,sig,null,_fidxs); // Now start the recursion - fun._ret = _ret._close(); + fun._ret = _ret._close(types); for( int i=0; i<sig.length; i++ ) - sig[i] = _sig[i]._close(); + sig[i] = _sig[i]._close(types); return fun; } @@ -266,4 +266,15 @@ public class TypeFunPtr extends TypeNil { // 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); } + + @Override Type _upgradeType(java.util.HashMap<String,Type> types) { + TypeFunPtr old = (TypeFunPtr)VISIT.get(_uid); + if( old!=null ) return old; + Type[] sig = new Type[_sig.length]; + TypeFunPtr fun = malloc(_nil,_open,sig,null,_fidxs); + VISIT.put(_uid,fun); + fun._ret = _ret._upgradeType(types); + for( int i=0; i<sig.length; i++ ) sig[i] = _sig[i]._upgradeType(types); + return fun; + } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 74fbfb9f..1b0019d4 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -8,7 +8,7 @@ import java.util.ArrayList; /** * Integer Type */ -public class TypeInteger extends Type { +public class TypeInteger extends TypeScalar { /** * Describes an integer *range* - everything from min to max; both min and * max are inclusive. If min==max, this is a constant. diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/src/main/java/com/seaofnodes/simple/type/TypeMem.java index d5ee8bd8..02cfc57b 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -59,7 +59,10 @@ public class TypeMem extends Type { if( that==TOP ) return this; if( this==BOT ) return BOT; if( that==BOT ) return BOT; - int alias = _alias==that._alias ? _alias : 1; + // Different slices lose their alias and contents together. Their + // scalar meet alone cannot describe the unsplit bulk memory. + if( _alias!=that._alias ) return BOT; + int alias = _alias; Type mt = _t.meet(that._t); return make(alias,mt); } @@ -107,4 +110,8 @@ public class TypeMem extends Type { } @Override public String str() { return toString(); } + + @Override Type _upgradeType(java.util.HashMap<String,Type> types) { + return make(_alias,_t._upgradeType(types)); + } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index 9fc90544..4a28b919 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -126,7 +126,7 @@ public class TypeMemPtr extends TypeNil { @Override TypeMemPtr _makeRO() { return withAccess(true); } @Override boolean _isGLB(boolean mem) { return _ro && _nil==3 && !_one && _obj.isGLB2(); } @Override TypeMemPtr _glb(boolean mem) { return make((byte)3,_obj.glb2(),false,true); } - @Override TypeMemPtr _close() { return makeFrom(_obj._close()); } + @Override TypeMemPtr _close(HashMap<String,Type> types) { return makeFrom(_obj._close(types)); } // True if this "isa" t up to named structures @@ -174,4 +174,8 @@ public class TypeMemPtr extends TypeNil { if( this== NOTBOT) return sb.p("*void"); return _obj.print(sb.p(x()).p("*"),visit,html).p(q()); } + + @Override Type _upgradeType(java.util.HashMap<String,Type> types) { + return makeFrom((TypeStruct)_obj._upgradeType(types)); + } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeNil.java b/src/main/java/com/seaofnodes/simple/type/TypeNil.java index 56d73b00..32505aa2 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeNil.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeNil.java @@ -7,7 +7,7 @@ import java.util.ArrayList; /** * Nil-able Scalar types */ -public abstract class TypeNil extends Type { +public abstract class TypeNil extends TypeScalar { // 0 = high-subclass choice nil // 1 = high-subclass no nil // 2 = low -subclass no nil diff --git a/src/main/java/com/seaofnodes/simple/type/TypeScalar.java b/src/main/java/com/seaofnodes/simple/type/TypeScalar.java new file mode 100644 index 00000000..1b41db13 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/type/TypeScalar.java @@ -0,0 +1,31 @@ +package com.seaofnodes.simple.type; + +import com.seaofnodes.simple.util.SB; +import java.util.ArrayList; +import java.util.BitSet; + +/** + * Values that fit in a register or field: integers, floats and pointers. + * These bounds exclude control and memory. An unresolved load can produce a + * scalar without making the parser guess which kind of value it will hold. + */ +public class TypeScalar extends Type { + protected TypeScalar(byte type) { super(type); } + private TypeScalar() { this(TSCALAR); } + public static final TypeScalar BOT = new TypeScalar().intern(); + public static final TypeScalar TOP = BOT.dual(); + public static void gather(ArrayList<Type> ts) { ts.add(BOT); } + + final Type smeet(TypeScalar scalar) { + if( _type==TSCALAR ) return isHigh() ? scalar : this; + if( scalar._type==TSCALAR ) return scalar.isHigh() ? this : scalar; + return BOT; + } + @Override Type xmeet(Type t) { return isHigh() ? t : this; } + @Override TypeScalar xdual() { return new TypeScalar(); } + @Override public boolean isHigh() { return this==TOP; } + @Override boolean _isGLB(boolean mem) { return this==BOT; } + @Override Type _glb(boolean mem) { return BOT; } + @Override public String str() { return isHigh() ? "~scalar" : "scalar"; } + @Override SB _print(SB sb, BitSet visit, boolean html) { return sb.p(str()); } +} diff --git a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 55942b0e..8eec6dd4 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -90,18 +90,27 @@ public class TypeStruct extends Type { public final TypeStruct close() { - return (TypeStruct)recurOpen()._close().recurClose(); + return close(null); } - @Override TypeStruct _close() { + public final TypeStruct close(HashMap<String,Type> types) { + return (TypeStruct)recurOpen()._close(types).recurClose(); + } + @Override TypeStruct _close(HashMap<String,Type> types) { Object key = isAry() ? _uid : _name; TypeStruct ts = (TypeStruct)VISIT.get(key); if( ts!=null ) return ts; + if( _open && types!=null && types.get(_name) instanceof TypeMemPtr ptr && !ptr._obj._open ) + return ptr._obj._close(types); + // Closing A must not pretend that an undeclared B is an empty + // definition. The root is visited first; self references find it above. + // Keep other empty forward shapes open until their own declaration. + if( _open && _fields.length==0 && VISIT.size()>1 ) return this; ts = recurPre(key,false); Field[] flds = ts._fields; // Now start the recursion for( int i=0; i<flds.length; i++ ) - flds[i].setType(_fields[i]._t._close()); + flds[i].setType(_fields[i]._t._close(types)); return ts; } @@ -490,4 +499,16 @@ public class TypeStruct extends Type { return is; } + + @Override Type _upgradeType(HashMap<String,Type> types) { + Type def = types.get(_name); + if( def instanceof TypeMemPtr ptr && !ptr._obj._open && _open ) + return ptr._obj; + TypeStruct old = (TypeStruct)VISIT.get(_uid); + if( old!=null ) return old; + TypeStruct ts = recurPre(_uid,_open); + for( int i=0; i<_fields.length; i++ ) + ts._fields[i].setType(_fields[i]._t._upgradeType(types)); + return ts; + } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index df9aba31..27a0a9d9 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -18,6 +18,7 @@ public class TypeTuple extends Type { // All fields directly listed public static TypeTuple make(Type... types) { TypeTuple tt = malloc(types); + for( Type t : types ) if( !t._terned ) return tt; TypeTuple t2 = tt.intern(); return t2==tt ? tt : t2.free(tt); } @@ -61,6 +62,18 @@ public class TypeTuple extends Type { return malloc(TypeFunPtr.xdual(_types)); } + @Override int nkids() { return _types==null ? 0 : _types.length; } + @Override Type at(int idx) { return _types[idx]; } + @Override void set(int idx, Type t) { _types[idx]=t; } + @Override TypeTuple rdual() { + if( _dual!=null ) return dual(); + TypeTuple d = malloc(new Type[_types.length]); + (_dual=d)._dual=this; + for( int i=0; i<_types.length; i++ ) + d._types[i] = _types[i]._terned ? _types[i].dual() : _types[i].rdual(); + return d; + } + @Override boolean _isConstant() { for( Type t : _types ) if( !t._isConstant() ) @@ -112,8 +125,10 @@ public class TypeTuple extends Type { return true; } - @Override int nkids() { return _types.length; } - @Override Type at( int idx ) { return _types[idx]; } - @Override void set( int idx, Type t ) { _types[idx] = t; } - + @Override Type _upgradeType(java.util.HashMap<String,Type> types) { + if( _types==null ) return this; + Type[] ts = new Type[_types.length]; + for( int i=0; i<ts.length; i++ ) ts[i] = _types[i]._upgradeType(types); + return make(ts); + } } |