diff options
| author | Cliff Click <cliffc@acm.org> | 2026-08-20 10:56:30 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-08-20 10:56:30 -0700 |
| commit | 3568f3deed586327f885ac98b73d07ae3ade6e57 (patch) | |
| tree | fce7865468dc9e2beabeb68342f23bfea5bdae1a /chapter25/src/main/java | |
| parent | 1cb8279a64f4f79615ac8358927b11237df29bf2 (diff) | |
| download | Simple-3568f3deed586327f885ac98b73d07ae3ade6e57.tar.gz Simple-3568f3deed586327f885ac98b73d07ae3ade6e57.zip | |
Squashed commit of the following:
commit c05d7df4f9c90984d2c04126772be3fee1d81fd1
Author: Cliff Click <cliffc@acm.org>
Date: Thu Aug 20 10:52:58 2026 -0700
Fix local frefs, deferred inlining, and sys FileIO support
- Defer non-trivial inlining out of CallEnd idealization and run it from IterPeeps after normal peepholes reach a fixed point.
- Keep forward refs local to their lexical scope, promote them outward on scope pop, and track created FRefNodes directly for dependency discovery.
- Preserve loop scope shape when frefs are first seen inside loop bodies.
- Treat frefs as final constants from creation and force lazy self lookups before implicit calls.
- Reset imported pointer/struct types conservatively for post-parse Iter.
- Pin Start-owned global machine value chains and clone global constants per function during GCM.
- Improve late ASM printing before encoding and namespace constant-pool symbols.
- Add optional regalloc function-local edge verifier and improve empty-mask splitting for multi-def/fixed-register LRGs.
- Add sys array compare, safer array copy bounds, libc open/creat/close/unlink bindings, aryu8.str0, and higher-level sys.io file operations.
- Add docs/examples/FileIO.smp and a Chapter25 FileIO test.
- Update spill/code-size goldens after the allocator and scheduling changes.
commit ef5316979732ac118612d310b75923c8f59ecdc1
Author: Cliff Click <cliffc@acm.org>
Date: Fri Aug 14 16:29:56 2026 -0700
Dijkstra uses bitset.
TestC.exec for repeated test runs with different stdins.
Support &= and |= op-update forms.
commit 728a527587f19bb49860f02ae5ac5968ab01ae33
Author: Cliff Click <cliffc@acm.org>
Date: Fri Aug 14 12:13:28 2026 -0700
Fix live demo
commit e4c069b9ef2cbfafe28d8edfcbff55396cde085e
Author: Cliff Click <cliffc@acm.org>
Date: Fri Aug 14 09:52:24 2026 -0700
Update Dijkstra.smp
commit b8015739b4056e3f7a715a030e846a441021a9f1
Author: Cliff Click <cliffc@acm.org>
Date: Fri Aug 14 09:41:17 2026 -0700
Better looking Dijkstra
commit 7cce587804c6169b24829e0b5bdc10be94357a31
Author: Cliff Click <cliffc@acm.org>
Date: Fri Aug 14 09:33:33 2026 -0700
Fix CmpMemX86 encoding
Use sys.aryu8 for number printing
commit 310b5d8c9978a3b09622a4b89dac97f0e5e6f3fb
Author: Cliff Click <cliffc@acm.org>
Date: Fri Aug 14 09:04:58 2026 -0700
Progress dijlstra
Fix NotX86 encoding. Allow Not-sinking through Phis; the Nots both take Scalar and might take different types (ptr vs int). Better guard installing during && || opers.
Drop the csv parse flavor in sys lib.
commit 5917d5322521dd5e762c4698d34e5d7ac9b3a37f
Author: Cliff Click <cliffc@acm.org>
Date: Thu Aug 13 14:44:12 2026 -0700
missed
commit da35ad4d8a330559a21c04ae6326536e0fd62c48
Author: Cliff Click <cliffc@acm.org>
Date: Thu Aug 13 14:43:42 2026 -0700
Major cleanup of allocation
All the graph-gen is moved to the <ctor> declaration and not at the alloc site.
commit c4223216099ccbc526d282bb263972532d48c5b2
Author: Cliff Click <cliffc@acm.org>
Date: Thu Aug 13 13:26:01 2026 -0700
Some work from Dykstra (more coming)
commit a03bc567f61dc7e4355e453ee4be16ac2528d1ab
Author: Cliff Click <cliffc@acm.org>
Date: Thu Aug 13 09:32:55 2026 -0700
Spill correctness and improvements
Had the callee-save pick-risky backwards vs cloneables.
commit 2d306e4430225f916cb7fb999f4926e52f6fb70a
Author: Cliff Click <cliffc@acm.org>
Date: Wed Aug 12 19:40:04 2026 -0700
Tighter parser handling of missing fields
Bug fix add libc.errno, read can return -1, sys.ary exists
commit b7eeefda4cafa1e86153170dca6f13d45ef63f69
Author: Cliff Click <cliffc@acm.org>
Date: Wed Aug 12 16:22:48 2026 -0700
Printer improvements
commit 8b9112226f1d2d1c843b080eecefe0d5ddc1f8cf
Author: Cliff Click <cliffc@acm.org>
Date: Wed Aug 12 15:30:46 2026 -0700
Remove GLB
commit ae566f5c610b9c30831906d3f024901d8930a227
Author: Cliff Click <cliffc@acm.org>
Date: Wed Aug 12 14:38:51 2026 -0700
Add Capitalize example
Rename Ary to ary.
Fix bug || carrying state along.
Fix bug load-array removing control.
Add sys.char tolower/upper
Diffstat (limited to 'chapter25/src/main/java')
43 files changed, 1031 insertions, 458 deletions
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java index 9fac7a99..532f5c70 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -50,18 +50,58 @@ import java.util.Random; public class IterPeeps { public final WorkList<Node> _work; + final WorkList<CallEndNode> _workInline; - public IterPeeps( long seed ) { _work = new WorkList<>(seed); } + public IterPeeps( long seed ) { + _work = new WorkList<>(seed); + _workInline = new WorkList<>(seed); + } @SuppressWarnings("unchecked") public <N extends Node> N add( N n ) { return (N)_work.push(n); } public void addAll( Ary<Node> ary ) { _work.addAll(ary); } + public void deferInline( CodeGen code, CallEndNode cend ) { + if( !code._midAssert ) + _workInline.push(cend); + } + /** - * Iterate peepholes to a fixed point + * Iterate peepholes and inlining to a fixed point */ public void iterate( CodeGen code ) { + CallEndNode cend = null; + boolean didInline = false; + Ary<Node> defer = new Ary<>(Node.class); + while( true ) { + // Clean up everything that does not grow the code + iteratePeeps(code); + + // Pick an inline candidate, no real heuristic, first come, first served + while( (cend=_workInline.pop()) != null) { + if( cend.isDead() ) continue; + if( cend.inline() == -1 ) defer.add(cend); + if( cend.inline() > 0 ) break; + } + // Found an inline candidate, so inline + if( cend != null ) { + // Inline, run peeps until clean again + cend.doInline(); + didInline = true; + continue; + } + // No more candidates, check the defer list + if( !didInline ) break; // No more progress, so all the "maybe inline after cleanup" do not progress + // Some inlining happened, retry all the "try again after cleanup" calls + didInline = false; + code.addAll(defer); + defer.clear(); + } + } + + // Run all the code-reduction and type-lifting peeps as possible + private void iteratePeeps( CodeGen code ) { assert progressOnList(code, _work, true); int cnt=0; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/Parser.java b/chapter25/src/main/java/com/seaofnodes/simple/Parser.java index e964fa5b..98093a77 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/Parser.java @@ -100,6 +100,7 @@ public class Parser { ScopeNode _breakScope; // Merge all the while-breaks here ScopeNode _continueScope; // Merge all the while-continues here ScopeNode _returnScope; // Merge all the function exits here + Ary<FRefNode> _frefs; // Forward refs created during this parse TypeStruct _ctorOpenStruct; // Open struct being initialized by an allocation constructor block. // Mapping from a type name to a Type. The string name matches @@ -164,7 +165,9 @@ public class Parser { public Ary<FRefNode> parse( CompUnit ref ) { assert _scope == null && _breakScope == null && _continueScope == null && _returnScope == null; + assert _frefs == null; _lexer = new Lexer(ref._src); + _frefs = new Ary<>(FRefNode.class); // Starting Scope has control, memory, initial arguments _scope = new ScopeNode(); _scope.define(ScopeNode.CTRL, Type.CONTROL , false, null, _lexer); @@ -183,12 +186,12 @@ public class Parser { if( !_lexer.isEOF() ) throw _errorSyntax("unexpected"); - // At the top scope and every new var should be a FRef, and these + // All still-unresolved forward refs // should immediately resolve to a file-based name which is a Simple // class type. Ary<FRefNode> frefs = new Ary<>(FRefNode.class); - for( int i=2; i<_scope._vars._len; i++ ) { - FRefNode fref = (FRefNode)_scope._inputs.at(i); + for( FRefNode fref : _frefs ) { + if( fref.nIns() != 1 && fref._con == FRefNode.FREF_TYPE ) continue; CompUnit cu = ParseAll.findCompUnitOrThrow(_code,_ref,fref._name); fref._con = TypeMemPtr.make((byte)2,TypeStruct.make(addClzPrefix(cu._cname),true),true); frefs.push(fref); @@ -201,6 +204,7 @@ public class Parser { _xScopes.pop(); _scope.kill(); _scope = null; + _frefs = null; return frefs; } @@ -475,7 +479,7 @@ public class Parser { Field[] fs = new Field[self._fields.length]; for( int i=0; i<fs.length; i++ ) { Field fld = self._fields[i]; - fs[i] = fld._t instanceof TypeFunPtr ? fld : fld.makeFrom(fld._t.glb(true)); + fs[i] = fld.makeFrom(fld._t.makeStorage()); } return TypeStruct.make(self._name,self._open,fs); } @@ -680,6 +684,8 @@ public class Parser { // it sets the second input to the corresponding input from the back // edge. If the phi is redundant, it is replaced by its sole input. var exit = _breakScope; + head.balanceLoopFRefs(_scope); + exit.balanceLoopFRefs(_scope); head.endLoop(_scope, exit); head.unkeep().kill(); @@ -812,13 +818,15 @@ public class Parser { Node rhs = switch( fside ) { case "else" -> (doRHS=match(fside)) ? parseStatement() : con(lhs._type.makeZero()); case ":" -> (doRHS=match(fside)) ? parseAsgn() : con(lhs._type.makeZero()); - case "&&" -> rhs = pred; - case "||" -> rhs = parseLogical(); + case "&&" -> con(lhs._type.makeZero()); // pred && expr_is_ignored + case "||" -> parseLogical(); // pred || expr default -> throw TODO(); }; rhs.keep(); _scope.removeGuards(ifF); - if( doRHS ) + // The RHS of `||` is parsed on the false side, so retain its updated + // control, memory and locals just as an explicit else arm does. + if( doRHS || fside.equals("||") ) fScope = _scope; pred.unkeep(); @@ -889,7 +897,7 @@ public class Parser { _returnScope = _scope.dup(); while( lexN+1 < _returnScope.depth() ) _returnScope._pop(); // Pop a nested block scope until we hit the function scope - _returnScope.define("$expr", expr._type.glb(false), true, expr, null); + _returnScope.define("$expr", inferredReturnType(expr._type), true, expr, null); } else { // For <init> and <clinit> - ALL FIELDS IN LAST SCOPE are live @@ -998,6 +1006,34 @@ public class Parser { return peep(new ConvertNode(t,expr)); } + // Inferred `var` declarations describe writable slots, not the exact + // value used to initialize them. Explicitly typed locals retain the + // user's nullability and numeric-width guarantees; `val` retains the + // initializer's precise type. + private static Type mutableInferredType(Type t) { + return switch( t ) { + case TypeInteger ti -> TypeInteger.BOT; + case TypeFloat tf -> TypeFloat.F64; + case TypeMemPtr tmp -> tmp.makeVar(); + case TypeFunPtr tfp -> tfp; + case TypeConAry<?> a -> a; + case TypePtr ptr -> TypePtr.PTR; + case TypeScalar ts -> TypeScalar.BOT; + default -> t; + }; + } + + // Seed an inferred return merge with the declared numeric family instead + // of a transient constant/range. Pointer nullability remains part of the + // inferred function result and is combined by the later Phi. + private static Type inferredReturnType(Type t) { + return switch( t ) { + case TypeInteger ti -> TypeInteger.BOT; + case TypeFloat tf -> TypeFloat.F64; + default -> t; + }; + } + private Node widenInt( Node expr, Type t ) { return (expr._type instanceof TypeInteger || expr._type==Type.NIL) && t instanceof TypeFloat ? peep(new ToFloatNode(expr)) : expr; @@ -1064,7 +1100,7 @@ public class Parser { if( expr._type==Type.NIL ) throw error("a not-null/non-zero expression"); t = expr._type; - if( !xfinal ) t = t.glb(false); // Widen if not final + if( !xfinal ) t = mutableInferredType(t); } // Final is deep on ptrs @@ -1074,7 +1110,8 @@ public class Parser { } // expr is a constant function - if( t instanceof TypeFunPtr && expr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) { + if( t instanceof TypeFunPtr decl && expr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) { + t = decl.makeFrom(tfp.fidx()); FunNode fun = _code.link(tfp); if( fun != null ) fun.setName(name); // Assign debug name to Simple function @@ -1158,6 +1195,8 @@ public class Parser { ts = ctorFld==null ? TypeStruct.make(clzName,false,fld) : TypeStruct.make(clzName,false,fld,ctorFld); + TypeFunPtr alloc = makeAllocator((TypeStruct)TYPES.get(fullName),ret,ctorFld); + ts = ts.add(Field.make("<new>",alloc,_code.alias(_ref._cname),true)); TYPES.put(clzName,ts); // Insert a field in the containing class with the nested class type. @@ -1169,6 +1208,78 @@ public class Parser { return require(_code.ZERO,";"); } + // Build the declaration-side allocation helper. Allocation sites only + // call this function; all layout, initialization and publication choices + // are made here, where the complete struct and constructor are known. + private TypeFunPtr makeAllocator(TypeStruct ts, ReturnNode initRet, Field ctorFld) { + TypeFunPtr ctor = ctorFld==null ? null : (TypeFunPtr)ctorFld._t; + int nargs = ctor==null ? 0 : ctor.nargs()-2; // Hide self and selfMem + Type[] atypes = new Type[nargs]; + for( int i=0; i<nargs; i++ ) atypes[i] = ctor.arg(i+2); + TypeMemPtr ptr = TypeMemPtr.make(ts); + TypeFunPtr sig = TypeFunPtr.make1((byte)2,true,atypes,ptr,_code.fidx(_ref._cname)); + String name = (ts._name+".<new>").intern(); + + int oldUID = _code.UID(); + FunNode fun = (FunNode)new FunNode(loc(),sig,name,_ref,null,_ref._start).peephole(); + _code.link(fun); + Node rpc = new ParmNode("$rpc",0,TypeRPC.BOT,fun,ConstantNode.seed(TypeRPC.BOT).peephole()).peephole(); + Node pub = new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun, + new ProjNode(_ref._start,1,ScopeNode.MEM0).peephole()).peephole(); + Node[] parms = new Node[nargs]; + for( int i=0; i<nargs; i++ ) + parms[i] = new ParmNode("arg"+i,i+2,atypes[i],fun,ConstantNode.seed(atypes[i]).peephole()).peephole(); + + NewNode nnn = new NewNode(ts,fun,off(ts," len")).init(); + Node self = new ProjNode(nnn,0,ts.str()).init(); + Node priv = new ProjNode(nnn,1,"#selfMem").init(); + Node[] initArgs = new Node[]{fun,pub,self,priv, + new FunPtrNode(initRet.fun().sig(),_code._start,initRet).peephole()}; + CallEndNode cend = rawCall(initArgs,initRet.fun()); + Node ctl = new CProjNode(cend,0,ScopeNode.CTRL).peephole(); + pub = new ProjNode(cend,1,ScopeNode.MEM0).peephole(); + priv = new ProjNode(cend,2,"#selfMem").peephole(); + + if( ctor != null ) { + Node[] cargs = new Node[nargs+5]; + cargs[0]=ctl; cargs[1]=pub; cargs[2]=self; cargs[3]=priv; + for( int i=0; i<nargs; i++ ) cargs[i+4]=parms[i]; + FunNode cfun = _code.link(ctor); + cargs[cargs.length-1] = new FunPtrNode(ctor,_code._start,cfun.ret()).peephole(); + cend = rawCall(cargs,cfun); + ctl = new CProjNode(cend,0,ScopeNode.CTRL).peephole(); + pub = new ProjNode(cend,1,ScopeNode.MEM0).peephole(); + priv = new ProjNode(cend,2,"#selfMem").peephole(); + } + + for( Field field : ts._fields ) { + Type storage = field._t.makeStorage(); + Field escaped = field._final ? field : Field.make(field._fname,storage,field._alias,true); + pub.keep(); + Node esc = new EscapeNode(escaped,self,priv,pub).peephole(); + MemMergeNode merge = new MemMergeNode(false,null,pub); + merge.alias(field._alias,esc); + Node next = merge.peephole(); + pub.unkeep(); + pub = next; + } + ReturnNode ret = (ReturnNode)new ReturnNode(ctl,pub,self,rpc,fun).peephole(); + fun.setRet(ret); + fun._approxUIDs = _code.UID() - oldUID; + _ref.addFun(_code,fun); + return sig; + } + + private CallEndNode rawCall(Node[] args, FunNode target) { + // Establish this known declaration-side edge immediately, but do not + // peephole or inline it while the surrounding factory is being built. + // IterPeeps therefore starts with the complete initializer caller set. + CallNode call = new CallNode(loc(),args).init(); + CallEndNode cend = new CallEndNode(call,TypeRPC.constant(_code.rpc(_ref._cname))).init(); + call.link(target); + return cend; + } + // Parse a struct declaration (not an allocation); file-level is a class-init, and scope structs are normal private ReturnNode parseStruct( boolean isClz, String typeName ) { // Record & restore global state set during parsing the <init> code @@ -1816,7 +1927,8 @@ public class Parser { t = TypeMemPtr.make((byte)2,clz,true); } // Define the FRef - var = _scope.defineFRef(id,t,cu!=null,loc()); + var = _scope.defineFRef(id,t,true,loc()); + _frefs.push((FRefNode)_scope.in(var)); } // Load local value @@ -1867,7 +1979,7 @@ public class Parser { int selfx = _scope.kindFcn(var)._lexSize; // Might be a method call from inside a method, so no explicit "self". // Pass the in-scope "self" - return parsePostfixMethod(rvalue,_scope.in(selfx)); + return parsePostfixMethod(rvalue,_scope.in(_scope.update(_scope.var(selfx),null))); } // Assign-update direct into Scope Node op = opAssign(ch,rvalue, var.type() ); @@ -1897,11 +2009,13 @@ public class Parser { case '-' -> new SubNode(lhs,rhs); case '*' -> new MulNode(lhs,rhs); case '/' -> new DivNode(lhs,rhs); + case '|' -> new OrNode(null,lhs,rhs); + case '&' -> new AndNode(null,lhs,rhs); default -> throw TODO(); }; // Convert to float ops, or narrow int types; error if not declared type. // Also, if postfix LHS is still keep() - return convertExpr(peep(op),t.glb(false)); + return convertExpr(peep(op),t); } @@ -1931,59 +2045,38 @@ public class Parser { } private Node allocStruct(TypeStruct ts) { - Ary<Node> ctorArgs = constructorArgs(); // CNC TODO- BAD THREADING SELF-MEM - Node size = off(ts, " len"); - - // Build a NewNode; takes in ctrl and size. - // Produces a ptr and a private mem. - NewNode nnn = new NewNode(ts, ctrl(), size ).init(); - ProjNode self = new ProjNode(nnn,0,ts.str()).init().keep(); - ProjNode smem = new ProjNode(nnn,1,"#selfMem").init(); - - // Find a "class:XXX" struct, with field "XXX" function ptr as the <init> - TypeStruct clz = (TypeStruct)TYPES.get(addClzPrefix(ts._name)); + Ary<Node> ctorArgs = constructorArgs(); + // A field declaration can leave a short forward type name in TYPES. + // Allocation happens in lexical context, so resolve that short name + // to the completed nested type before selecting its class helper. + String typeName = ts._name.indexOf('.') == -1 ? fullTypeName(ts._name) : ts._name; + Type resolved = TYPES.get(typeName); + if( resolved instanceof TypeStruct rts ) ts = rts; + TypeStruct clz = (TypeStruct)TYPES.get(addClzPrefix(typeName)); if( clz==null ) throw error("Unknown struct type '" + ts._name + "'"); - TypeFunPtr init = (TypeFunPtr)clz.field(initFieldName(ts._name))._t; - - // Call construct <init>($ctrl,$mem,NewNode.self,NewNode.#selfMem) and - // encourage inlining - Node initSelf = self._type.isa(init.arg(0)) ? self : peep(new CheckCastNode(init.arg(0),ctrl(),self)); - Ary<Node> args = new Ary<>(Node.class){{add(ctrl()); add(mem()); add(initSelf); add(smem); add(ConstantNode.seed(init)); }}; - Node selfMem = functionCall( args ); - // The returned value is a merge of private *Memory* and NOT some Scalar - - // Optional user constructor; same as the default constructor; private - // memory going in and out. - Field ctor = clz.field("<ctor>"); - if( ctor != null ) - selfMem = constructorCall((TypeFunPtr)ctor._t,self,selfMem,ctorArgs); - else if( !ctorArgs.isEmpty() ) - throw error("Constructor arguments for '" + ts._name + "' but no constructor is defined"); - if( match("{") ) - throw error("Inline constructor blocks are no longer supported; define a constructor in '" + ts._name + "'"); - - // Might be TOP if parsing in dead/unreachable code - if( selfMem._type == Type.TOP ) { - _code.add(selfMem); - return self.unkeep(); - } - - // Escape all new aliases. EscapeNode inputs are the self pointer, the - // merged private memory, then all the named public aliases. The - // output is all the newly merged public aliases - but not actually - // bulk memory. - selfMem.keep(); - for( Field fld : ts._fields ) { - Field fld2 = fld._final ? fld : (Field)fld.glb(true); - Node prior = mem(); - Node esc = peep(new EscapeNode(fld2,self,selfMem,prior)); - mem(mergeAlias(prior,fld._alias,esc)); - } - - if( selfMem.unkeep().isUnused() ) selfMem.kill(); - else _code.add(selfMem); - return self.unkeep(); + Field afld = clz.field("<new>"); + Node alloc; + if( afld != null ) { + TypeFunPtr tfp = (TypeFunPtr)afld._t; + FunNode fun = _code.link(tfp); + alloc = fun==null + ? new FRefNode((addClzPrefix(typeName)+".<new>").intern(),loc()) + : new FunPtrNode(tfp,_code._start,fun.ret()).peephole(); + } else { + if( !ts._fref ) + throw error("Constructor arguments for '" + ts._name + "' but no constructor is defined"); + Type[] sig = new Type[ctorArgs._len]; + for( int i=0; i<ctorArgs._len; i++ ) + sig[i] = ctorArgs.at(i)._type; + alloc = new FRefNode((addClzPrefix(typeName)+".<new>").intern(),loc(), + TypeFunPtr.make(false,sig,TypeMemPtr.make(ts))); + } + Ary<Node> args = new Ary<>(Node.class); + args.add(ctrl()); args.add(mem()); + for( Node arg : ctorArgs ) args.add(arg.unkeep()); + args.add(alloc); + return functionCall(args); } private Ary<Node> constructorArgs() { @@ -2000,29 +2093,6 @@ public class Parser { return args; } - // Constructors are called with two extra arguments: self and selfMem. - private Node constructorCall(TypeFunPtr ctor, Node self, Node selfMem, Ary<Node> ctorArgs) { - Ary<Node> args = new Ary<>(Node.class); - Node ctorSelf = self._type.isa(ctor.arg(0)) - ? self - : peep(new CheckCastNode(ctor.arg(0),ctrl(),self)); - args.add(ctrl()); - args.add(mem()); - args.add(ctorSelf); - args.add(selfMem); - for( Node arg : ctorArgs ) - args.add(arg.unkeep()); - args.add(ConstantNode.seed(ctor)); - - CallNode call = (CallNode)new CallNode(loc(), args.asAry()).peephole(); - CallEndNode cend = (CallEndNode)new CallEndNode(call,TypeRPC.constant(_code.rpc(_ref._cname))).peephole(); - call.peephole(); - cend = (CallEndNode)cend.keep().peephole(); - ctrl(new CProjNode(cend,0,ScopeNode.CTRL).peephole()); - mem (new ProjNode(cend,1,ScopeNode.MEM0).peephole()); - return new ProjNode(cend.unkeep(),2,"#selfMem").peephole(); - } - private Node allocArray(TypeStruct ts, Node len) { Field lenFld = ts.field("#" ); Field bodyFld = ts.field("[]"); @@ -2104,7 +2174,8 @@ public class Parser { } private Node defaultSelf() { - return _scope.in(_scope._kinds.at(_scope.enclosingFuncOrDecl())._lexSize); + int selfx = _scope._kinds.at(_scope.enclosingFuncOrDecl())._lexSize; + return _scope.in(_scope.update(_scope.var(selfx),null)); } /** @@ -2147,8 +2218,18 @@ public class Parser { } Field fld = ts==null ? null : ts.field(name); + if( fld==null && ts!=null && !startsClzPrefix(ts._name) ) { + Type clz0 = TYPES.get(addClzPrefix(ts._name)); + if( clz0 instanceof TypeStruct clz && (fld = latestStruct(clz).field(name)) != null ) { + expr.unkeep(); + ts = latestStruct(clz); + expr = con(TypeMemPtr.make((byte)2,ts,true)).keep(); + } + } if( fld==null && ts!=null ) fld = fieldOrOpen(ts,name,false); + if( fld==null && ts!=null && !latestStruct(ts)._open ) + throw error("Accessing unknown field '"+name+"' from '*"+ts._name+"'"); // With no field, we will update the bulk memory int alias = fld==null ? 1 : fld._alias; Type decl = fld==null ? Type.BOTTOM : fld._t; @@ -2195,7 +2276,7 @@ public class Parser { throw error( "'" + ts._name + "' is not fully initialized, field '" + fld._fname + "' needs to be set in a constructor" ); Node op = opAssign(ch,load, decl ); mem.keep(); - Node st = new StoreNode(loc(), name, alias, decl.glb(true), ctrl(), mem, expr.unkeep(), off.unkeep(), op, false).peephole().keep(); + Node st = new StoreNode(loc(), name, alias, decl, ctrl(), mem, expr.unkeep(), off.unkeep(), op, false).peephole().keep(); storeMem(st,alias,mem); st.unkeep(); mem.unkeep(); @@ -2416,6 +2497,7 @@ public class Parser { private char escapedChar(String kind) { char esc = _lexer.nextChar(); return switch( esc ) { + case '0' -> '\u0000'; case 'n' -> '\n'; case 't' -> '\t'; case 'r' -> '\r'; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 85d8143b..50f5c33b 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -77,6 +77,7 @@ public class CodeGen { // True when fidx is published through a public field of a public class. // TypeStruct.fidxs() already excludes private (underscore) fields. public boolean publicFIDX(int fidx) { + if( fidx < GlobalBits.RESERVED ) return false; // A public class initializer is itself an external root; unlike // constructors and methods, it is not reached through a class field. FunNode fun = _linker.atX(fidx); @@ -128,7 +129,7 @@ public class CodeGen { void freezePublicInterface() { assert _publicFIDXs==null && _publicAliases==null; int[] fidxs = XInt.EMPTY; - for( int fidx=1; fidx<_linker._len; fidx++ ) + for( int fidx=GlobalBits.RESERVED; fidx<_linker._len; fidx++ ) if( publicFIDX(fidx) ) fidxs = XInt.make(fidxs,fidx); int[] aliases = XInt.EMPTY; @@ -268,7 +269,9 @@ public class CodeGen { if( (dump & (1<<30)) != 0 ) System.err.println("After "+_phase+":"); - System.err.println(IRPrinter.prettyPrint(this)); + System.err.println(_phase.ordinal() >= Phase.LocalSched.ordinal() + ? asm(new SB()).toString() + : IRPrinter.prettyPrint(this)); return p2; } @@ -444,11 +447,13 @@ public class CodeGen { // The phase shift closes all parser-in-progress states and freezes // unknown external inputs. Imported nodes carry post-Opto escape - // precision, but Iter is a fresh pessimistic solve: non-singleton - // memory must restart at FULL so newly discovered private escapes can - // only be removed, never added. Seed the complete graph once. + // precision, but Iter is a fresh pessimistic solve: memory escape + // summaries must restart at FULL so newly discovered private escapes + // can only be removed, never added. Seed the complete graph once. + boolean hasImports = _externPaths != null; _start.walk(n -> { - n._type = iterEscapeReset(n._type); + if( !(n instanceof ConstantNode) ) + n._type = hasImports ? iterImportReset(n._type) : iterEscapeReset(n._type); add(n); return null; }); @@ -473,6 +478,26 @@ public class CodeGen { return t; } + private static Type iterImportReset(Type t) { + if( t.isHigh() ) + return t.dual(); + if( t instanceof TypeMem mem ) + return TypeMem.make(mem._alias,iterImportReset(mem._t),mem._one,mem._clz,mem._final,XInt.FULL,XInt.FULL); + if( t instanceof TypeMemPtr ) + return t.makeStorage(); + if( t instanceof TypeStruct ) + return t.makeStorage(); + if( t instanceof TypeTuple tt ) { + TypeTuple rez = tt; + for( int i=0; i<tt._types.length; i++ ) { + Type tx = iterImportReset(tt._types[i]); + if( tx != tt._types[i] ) rez = rez.makeFrom(i,tx); + } + return rez; + } + return t; + } + // Run ideal optimizations public CodeGen opto() { @@ -703,6 +728,7 @@ public class CodeGen { if( n instanceof MachNode ) { for( int i=0; i < n.nIns(); i++ ) n._inputs.set(i, _instSelect(n.in(i),map) ); + pinGlobalValue(n); return n; } @@ -716,6 +742,7 @@ public class CodeGen { // Walk machine op and replace inputs with mapped inputs for( int i=0; i < x.nIns(); i++ ) x._inputs.set(i, _instSelect(x.in(i),map) ); + pinGlobalValue(x); // Post selection action if( x instanceof MachNode mach ) { if( n instanceof ReturnNode ret ) @@ -726,6 +753,28 @@ public class CodeGen { return x; } + + // Some machine values are Start-pinned globals or zero-code wrappers around + // them, e.g. pointer/function constants and PtrToInt/ReadOnly-style adapters. + // Before output edges are rebuilt, make ownership explicit: every global value + // chain member is Start-pinned in slot 0 and data-linked in later slots. + private void pinGlobalValue(Node n) { + if( n instanceof CFGNode || !(n instanceof MachNode mach) || mach.outregmap()==null || n.isPinned() ) + return; + if( n.nIns()==0 ) + return; + if( !(n.in(0)==null || n.in(0)==_start) ) + return; + for( int i=1; i<n.nIns(); i++ ) { + Node def = n.in(i); + if( def==null ) continue; + if( def.isConst() ) continue; + if( def.nIns()==0 ) return; + if( def.in(0) != _start ) return; + } + n._inputs.set(0,_start); + } + // Walk all machine Nodes, and set their output edges private void _instOuts( Node n, BitSet visit ) { if( visit.get(n._nid) ) return; @@ -1020,11 +1069,9 @@ public class CodeGen { // Debugging helper @Override public String toString() { - if( _phase!=null && _phase.ordinal() > Phase.Schedule.ordinal() ) - return IRPrinter.prettyPrint( this ); if( _stop == null ) return "No StopNode"; - return _stop.p(4999); + return IRPrinter.prettyPrint(this); } // Debugging helper diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java index 274be838..7af7e5f1 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java @@ -317,10 +317,11 @@ public class ElfWriter { } // Write relocations for the constant pool + String cpoolPrefix = _code.entryClinitName().replaceAll("[^A-Za-z0-9_$]", "_") + "$CPOOL$"; for( Encoding.Relo relo : enc._bigCons.values() ) { boolean ro = !(relo._t instanceof TypeStruct ts) || ts.isConstant(); DataSection data = ro ? rodata : rwdata; - int symidx = symbols.symbol("CPOOL$"+symbols.gidx(), data._index, SYM_BIND_GLOBAL, SYM_TYPE_FUNC, relo._target, relo._t.size()); + int symidx = symbols.symbol(cpoolPrefix+symbols.gidx(), data._index, SYM_BIND_GLOBAL, SYM_TYPE_FUNC, relo._target, relo._t.size()); relocations.writeReloOffPlus(relo._opStart+relo._off, symidx, relo._elf ); } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index fa187000..f13e8ae3 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -24,7 +24,7 @@ public abstract class GlobalCodeMotion { schedEarly(code); // Break up shared global constants by functions - breakUpGlobalConstants(code._start ); + breakUpGlobalConstants(code._start); code._visit.clear(); schedLate(code); @@ -44,32 +44,31 @@ public abstract class GlobalCodeMotion { } // Break up shared global constants by functions - private static void breakUpGlobalConstants( Node start ) { + private static void breakUpGlobalConstants( StartNode start ) { - // For all global constants + // For all explicitly Start-pinned global values. Instruction + // selection keeps each zero-code/global chain member hooked to Start, + // so no later pass has to infer hidden global chains from data inputs. for( int i=0; i< start.nOuts(); i++ ) { Node con = start.out(i); - // Instruction selection can expand one shared TypeNode constant - // into a constant-valued machine expression. Split either form - // before scheduling, since separate functions have no CFG LCA. - if( !(con instanceof CFGNode) && - ((con._type.isHighOrConst() && con.isConst()) || - con instanceof MachNode mach && mach.isClone() && con._type.isConstant()) ) { - breakUpGlobalConstantSingle( con ); - i--; // Removed a global constant, re-run same index + if( isStartPinnedGlobalValue(con) ) { + breakUpGlobalConstantSingle(con); + if( con.nIns()==0 || con.in(0) != start ) + i--; // Removed a global constant, re-run same index } } } private static void breakUpGlobalConstantSingle( Node con ) { - // If an immediate global-value user still spans functions, it cannot - // yet be assigned to one clone. Keeping the constant at Start is a - // valid schedule; a downstream value with concrete ownership can be - // split independently. + // Split dependent global values first; cloning a later chain member + // will recursively clone its Start-pinned inputs on demand. for( Node use : con.outs() ) - if( use != null && useFun(use)==null ) - return; + if( use != null && useFun(use)==null ) { + if( !isStartPinnedGlobalValue(use) ) + return; + breakUpGlobalConstantSingle(use); + } // While constant has users in different functions while( true ) { // Find a function user, and another function @@ -82,22 +81,16 @@ public abstract class GlobalCodeMotion { if( fun==null || fun==fun2 ) fun=fun2; else { done=false; break; } } + // No direct function users: keep this global value at Start. + if( fun==null ) + return; // Single function user, so this constant is not shared if( done ) { con.setDef(0,fun); return; } // Move function users to a private constant - Node con2 = con.copy(); // Private constant clone - // Node copies made through Node(Node) carry unregistered inputs, - // while some machine copies construct fresh registered edges. - // Detach correctly in either case before pinning to the function. - Node old = con2.in(0); - if( old != null && old._outputs.find(con2) != -1 ) - con2.setDef(0,null); - else - con2._inputs.set(0,null); - con2.setDef(0,fun); + Node con2 = cloneGlobalForFun(con,fun,new IdentityHashMap<>()); // Move function users to this private constant for( int j=0; j<con._outputs._len; j++ ) { Node use = con.out(j); @@ -112,6 +105,44 @@ public abstract class GlobalCodeMotion { } } + private static Node cloneGlobalForFun(Node con, FunNode fun, IdentityHashMap<Node,Node> memo) { + Node memoized = memo.get(con); + if( memoized != null ) return memoized; + Node con2 = con.copy(); // Private constant clone + // Node copies made through Node(Node) carry unregistered inputs, while + // some machine copies construct fresh registered edges. The default + // Node.copy path gives an input-less clone. Normalize all of them to + // the original data inputs, pinned to the owning function. + memo.put(con,con2); + if( con2.nIns()==0 ) { + con2.addDef(fun); + for( int i=1; i<con.nIns(); i++ ) + con2.addDef(cloneInputForFun(con.in(i),fun,memo)); + } else { + Node oldCtrl = con2.in(0); + if( oldCtrl != null && oldCtrl._outputs.find(con2) != -1 ) + con2.setDef(0,null); + else + con2._inputs.set(0,null); + con2.setDef(0,fun); + for( int i=1; i<con2.nIns(); i++ ) + con2.setDef(i,cloneInputForFun(con.in(i),fun,memo)); + } + return con2; + } + + private static Node cloneInputForFun(Node def, FunNode fun, IdentityHashMap<Node,Node> memo) { + return isStartPinnedGlobalValue(def) + ? cloneGlobalForFun(def,fun,memo) + : def; + } + + private static boolean isStartPinnedGlobalValue(Node n) { + return n != null && n._type != null && !(n instanceof CFGNode) && + n.nIns() > 0 && n.in(0) instanceof StartNode && + (n.isConst() || n instanceof MachNode mach && mach.outregmap()!=null); + } + private static FunNode useFun(Node use) { return useFun(use,new BitSet()); } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java index 1d88597c..2b559a38 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -207,18 +207,11 @@ abstract public class IFG { assert tlrg.leader(); // Always, tlrg cannot use kills if( tlrg._mask.overlap(killMask) ) { - // Disallow clone-ables from killing registers. Just fail - // them and re-clone closer to target... so no kill. - // Special case for Intel XOR used to zero. - Node n = (Node)m; - CFGNode effUseBlk = n.out(0) instanceof PhiNode phi ? phi.region().cfg(phi._inputs.find(n)) : n.out(0).cfg0(); - if( m.isClone() && // Must be clonable - (n.nOuts()>1 || // Has many users OR - // Only 1 user but effective use is remote block - effUseBlk != n.cfg0() )) - // Then fail the clonable; it should split or move - alloc.fail(alloc.lrg((Node)m)); - // Else clonable cannot move + Node live = TMP.get(tlrg); + // Disallow clone-ables from living across killed registers. + // Fail them and let splitting re-clone closer to the target use. + if( live instanceof MachNode mach && mach.isClone() ) + alloc.fail(tlrg); else if( !tlrg.sub(killMask) ) alloc.fail(tlrg); } @@ -328,7 +321,7 @@ abstract public class IFG { // Pull all lrgs from IFG, in trivial order if possible while( sptr < color_stack.length ) { // Swap best color up front - pickColor(color_stack,sptr,swork); + pickColor(color_stack,sptr,swork,alloc); // Pick a trivial lrg, and (temporarily) remove from the IFG. LRG lrg = color_stack[sptr++]; @@ -384,10 +377,10 @@ abstract public class IFG { } // Pick LRG from color stack - private static void pickColor(LRG[] color_stack, int sptr, int swork) { + private static void pickColor(LRG[] color_stack, int sptr, int swork, RegAlloc alloc) { // Out of trivial colorable, pick an at-risk to pull if( sptr==swork ) - swap(color_stack,sptr,pickRisky(color_stack,sptr)); + swap(color_stack,sptr,pickRisky(color_stack,sptr,alloc)); // When coloring, we'd like to give more choices; so when coloring we'd // like to see the single-def first (since no choices anyway), then // non-split related (so more live ranges get colored), then @@ -422,12 +415,12 @@ abstract public class IFG { // Pick a live range that hasn't already spilled, or has a single-def- // single-use that are not adjacent. - private static int pickRisky( LRG[] color_stack, int sptr ) { + private static int pickRisky( LRG[] color_stack, int sptr, RegAlloc alloc ) { int best=sptr; - int bestScore = pickRiskyScore(color_stack[best]); + int bestScore = pickRiskyScore(color_stack[best],alloc); for( int i=sptr+1; i<color_stack.length; i++ ) { if( bestScore == 1000000 ) return best; // Already max score - int iScore = pickRiskyScore(color_stack[i]); + int iScore = pickRiskyScore(color_stack[i],alloc); if( iScore > bestScore ) { best = i; bestScore = iScore; } } @@ -442,32 +435,55 @@ abstract public class IFG { // // Picking a live range that is very close to coloring might allow it to // color despite being risky. - private static int pickRiskyScore( LRG lrg ) { + private static int pickRiskyScore( LRG lrg, RegAlloc alloc ) { + // Callee-save live ranges cover the whole function and are cheap to + // split. Rank scheduled area recovered against the loop-scaled cost + // of the def- and use-side moves. + if( lrg._machDef instanceof CalleeSaveNode ) + return areaScore(functionArea(lrg._fun,alloc), + splitCost((Node)lrg._machDef,(Node)lrg._machUse)); + if( lrg._splitDef != null && lrg._splitDef. in(1) instanceof CalleeSaveNode && + lrg._splitUse != null && lrg._splitUse.out(0) instanceof ReturnNode ) + return areaScore(functionArea(lrg._fun,alloc), + splitCost(lrg._splitDef,lrg._splitUse)); + // Pick single-def clonables that are not right next to their single-use. - // Failing to color these will clone them closer to their uses. + // Rank by the area recovered by cloning closer to the use. if( !lrg._multiDef && lrg._machDef.isClone() && lrg._machUse != null ) { Node def = ((Node)lrg._machDef); Node use = ((Node)lrg._machUse); CFGNode cfg = def.cfg0(); - if( cfg != use.cfg0() || // Different blocks OR - // Same block, but not close - cfg._outputs.find(def) < cfg._outputs.find(use)+1 ) - return 1000000; + int area = cfg != use.cfg0() + ? functionArea(lrg._fun,alloc) + : cfg._outputs.find(use)-cfg._outputs.find(def)-1; + if( area > 0 ) + return areaScore(area,loopCost(use)); } - // Always pick callee-save registers as being very large area recovered - // and very cheap to spill. - if( lrg._machDef instanceof CalleeSaveNode ) - return 1000000-2-lrg._mask.firstReg(); - if( lrg._splitDef != null && lrg._splitDef. in(1) instanceof CalleeSaveNode && - lrg._splitUse != null && lrg._splitUse.out(0) instanceof ReturnNode ) - return 1000000-1; - - // TODO: cost/benefit model. Perhaps counting loop-depth (freq) of def/use for cost - // and "area" for benefit + // Default for ranges without a specific area/cost estimate. return 1000 + (lrg._multiUse ? -100 : 0); } + private static int functionArea(FunNode fun, RegAlloc alloc) { + int area=0; + for( CFGNode bb : alloc._code._cfg ) + if( bb.fun()==fun ) + area += bb.nOuts(); + return area; + } + + private static int areaScore(int area, int cost) { + return 1000 + (area<<10)/cost; + } + + private static int splitCost(Node def, Node use) { + return loopCost(def) + (use==null ? 0 : loopCost(use)); + } + + private static int loopCost(Node n) { + return 1 << (n.cfg0().loopDepth()*3); + } + private static short biasColor( RegAlloc alloc, LRG lrg, short reg, RegMask mask ) { if( mask.size1() ) return reg; // Check chain of splits up the def-chain. Take first allocated diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java index b88067c4..5d4c151d 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -127,6 +127,10 @@ abstract public class Opto { private static void linkCG(CodeGen code, TypeFunPtr tfp, CallNode call) { if( tfp.nargs() != call.nargs() ) return; // Error calls hit this int[] fidxs = tfp.fidxs(); + // An unresolved forward call can still carry the infinite, inferred + // function set into Opto. There is no finite call graph to link yet; + // type checking will report the unresolved reference afterwards. + if( XInt.isHigh(fidxs) ) return; for( int fidx = XInt.next(fidxs,0); fidx >=0; fidx = XInt.next(fidxs,fidx) ) { // unlinkStart deliberately leaves uncalled functions in a // temporarily dead limbo. A newly discovered call revives them; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java index 191016be..90309328 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java @@ -114,15 +114,32 @@ public abstract class ParseAll { code._stop.walk( (Node n) -> { n.upgradeType(Parser.TYPES); if( n instanceof FRefNode fref ) { - TypeStruct clz = (TypeStruct)Parser.TYPES.get(fref._name); + boolean alloc = fref._name.endsWith(".<new>"); + String clzName = alloc + ? fref._name.substring(0,fref._name.length()-".<new>".length()).intern() + : fref._name; + TypeStruct clz = (TypeStruct)Parser.TYPES.get(clzName); if( clz == null ) return null; - // Class pointer: - TypeMemPtr clzptr = TypeMemPtr.make((byte)2,clz,true); - // Class pointer constant: - ConstantNode clzCon = code.con(clzptr); + Node con; + if( alloc ) { + Field ctor = clz.field("<new>"); + if( ctor == null || !(ctor._t instanceof TypeFunPtr tfp) ) { + String name = clzName.startsWith(Parser.CLZ) + ? clzName.substring(Parser.CLZ.length()) : clzName; + int dot = name.lastIndexOf('.'); + throw Parser.error("Unknown struct type '"+(dot==-1 ? name : name.substring(dot+1))+"'",fref._loc); + } + FunNode fun = code.link(tfp); + if( fun == null ) return null; + con = new FunPtrNode(tfp,code._start,fun.ret()).peephole(); + } else { + // Class pointer constant: + TypeMemPtr clzptr = TypeMemPtr.make((byte)2,clz,true); + con = code.con(clzptr); + } // Replace and optimize - fref.addDef(clzCon); + fref.addDef(con); code.add(fref); } // Adds sort by NIDs, which just got shuffled diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index 4c00391c..0d5b9e7b 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -61,6 +61,9 @@ public class RegAlloc { // ----------------------- // Live ranges with self-conflicts or no allowed registers private final IdentityHashMap<LRG,String> _failed = new IdentityHashMap<>(); + // Loop Phis get one chance to color after only cold self-conflict splits. + // If the same Phi self-conflicts again, split its hot def/backedge also. + private final IdentityHashMap<PhiNode,String> _deferredLoopSelf = new IdentityHashMap<>(); void fail( LRG lrg ) { assert lrg.leader(); _failed.put(lrg,""); @@ -171,6 +174,8 @@ public class RegAlloc { for( Node n : bb._outputs ) if( n instanceof NewNode nnn ) nnn.cacheRegs(_code); } + // Expensive assert: useful when chasing cross-function allocator edges. + //assert verifyFunctionLocalEdges(); // Top driver: repeated rounds of coloring and splitting. byte round=0; @@ -184,6 +189,63 @@ public class RegAlloc { _done = true; } + private boolean verifyFunctionLocalEdges() { + for( CFGNode bb : _code._cfg ) + for( Node use : bb._outputs ) { + FunNode useFun = funOf(use); + for( int i=1; i<use.nIns(); i++ ) { + Node def = use.in(i); + if( def==null || def.isConst() || allowedCrossFunctionEdge(use,i,def) ) + continue; + FunNode defFun = funOf(def); + if( defFun != null && useFun != null && defFun != useFun ) + throw new AssertionError(crossFunctionMessage(def,defFun,use,useFun,i)); + } + } + return true; + } + + private static String crossFunctionMessage(Node def, FunNode defFun, Node use, FunNode useFun, int idx) { + StringBuilder sb = new StringBuilder("Cross-function value edge: "); + sb.append(def.uniqueName()).append("(").append(defFun.label()).append(") -> ") + .append(use.uniqueName()).append("(").append(useFun.label()).append(") input ").append(idx) + .append(" def=").append(def).append(" use=").append(use).append("\n all uses:"); + for( Node out : def.outs() ) { + FunNode outFun = funOf(out); + sb.append("\n ").append(out.uniqueName()).append("(") + .append(outFun==null ? "?" : outFun.label()).append(")"); + } + return sb.toString(); + } + + private static boolean allowedCrossFunctionEdge(Node use, int idx, Node def) { + // Function metadata/control edges are not value live ranges. + if( use instanceof FunNode || use instanceof StopNode || use instanceof StopCUNode ) + return true; + // Return-linked function pointers carry function identity/lifetime, not + // an allocator value flowing from the callee body into this function. + if( use instanceof FunPtrNode && def instanceof ReturnNode ) + return true; + // Parm defaults and call-linked argument edges are the entry protocol; + // BuildLRG also skips Parm input 1. + if( use instanceof ParmNode ) + return true; + // Linked CallEnd -> Return edges should be gone before RegAlloc, but + // diagnose allocator value edges rather than call graph metadata here. + if( use instanceof CallEndNode && def instanceof ReturnNode ) + return true; + return false; + } + + private static FunNode funOf(Node n) { + if( n instanceof ParmNode parm ) return parm.fun(); + if( n instanceof ReturnNode ret ) return ret.fun(); + if( n instanceof FunNode fun ) return fun; + if( n instanceof CFGNode cfg ) return cfg.fun(); + CFGNode cfg = n.cfg0(); + return cfg==null ? null : cfg.fun(); + } + private boolean graphColor(byte round) { _failed.clear(); _lrgs.clear(); @@ -227,7 +289,7 @@ public class RegAlloc { // Register mask when empty; split around defs and uses with limited // register masks. - if( lrg._mask.isEmpty() && (!lrg._multiDef || lrg._1regUseCnt==1) ) { + if( lrg._mask.isEmpty() ) { if( lrg._1regDefCnt <= 1 && lrg._1regUseCnt <= 1 && (lrg._1regDefCnt + lrg._1regUseCnt) > 0 ) @@ -238,6 +300,10 @@ public class RegAlloc { if( splitEmptyMaskByUse(round,lrg) ) return true; } + if( lrg._mask.isEmpty() && lrg._multiDef && lrg._1regUseCnt > 1 && lrg._1regDefCnt <= 1 ) { + if( splitEmptyMaskSingleUses(round,lrg) ) + return true; + } // Generic split-by-loop depth. return splitByLoop(round,lrg); @@ -322,6 +388,26 @@ public class RegAlloc { return true; } + // Empty-mask live range with several direct single-register uses, often + // through a Phi with multiple defs. Split those uses directly instead of + // doing a loop-depth split, which might keep isolating the wrong edge. + boolean splitEmptyMaskSingleUses( byte round, LRG lrg ) { + findAllLRG(lrg); + if( _ns._len <= 5 ) + return false; + boolean progress = false; + for( Node n : _ns ) { + if( !(n instanceof MachNode mach) ) continue; + for( int i=1; i<n.nIns(); i++ ) { + RegMask use = mach.regmap(i); + if( use != null && use.size1() && lrg(n.in(i))==lrg ) { + insertBefore(n,i,"use/emptyN",round,lrg); + progress = true; + } + } + } + return progress; + } // Put use into a register class, perhaps adding a class or perhaps // narrowing a class (and causing a repeat) @@ -346,6 +432,19 @@ public class RegAlloc { Node[] conflicts = lrg._selfConflicts.keySet().toArray(new Node[0]); Arrays.sort(conflicts, (x,y) -> x._nid - y._nid ); + // First encounter with a loop Phi: try only cold splits this round. + // Remember the Phi across rounds so a persistent self-conflict forces + // the hot def/backedge splits on the next encounter. + IdentityHashMap<PhiNode,String> deferred = new IdentityHashMap<>(); + for( Node def : conflicts ) { + if( def instanceof PhiNode phi && phi.region() instanceof LoopNode ) + deferLoopSelf(phi,deferred); + for( Node use : def._outputs ) + if( use instanceof PhiNode phi && phi.region() instanceof LoopNode && + phi._inputs.find(def)==2 ) + deferLoopSelf(phi,deferred); + } + // For all conflicts for( Node def : conflicts ) { assert lrg(def)==lrg; // Might be conflict use-side @@ -354,6 +453,7 @@ public class RegAlloc { for( int i=0; i<def._outputs._len; i++ ) { Node use = def.out(i); if( (use instanceof PhiNode phi && + !(deferred.containsKey(phi) && phi.region() instanceof LoopNode && phi._inputs.find(def)==2) && !(phi.region() instanceof LoopNode loop && phi.in(2)==def && def.cfg0().idepth() > loop.idepth() ) ) || (use instanceof MachNode mach && mach.twoAddress()!=0 && use.in(mach.twoAddress())==def) ) insertBefore( use, use._inputs.find(def), "use/self/use",round,lrg ); @@ -362,10 +462,12 @@ public class RegAlloc { // Phi slot 1 (and not all inputs), because Phis extend the live range. // TODO: split before all inputs (except the last; at least 1 split here must be extra) if( def instanceof PhiNode phi && !(def instanceof ParmNode) ) { - SplitNode split = makeSplit("def/self",round,lrg); - insertAfterAndReplace(split,def,false); - if( split.nOuts()==0 ) - split.killOrdered(); + if( !deferred.containsKey(phi) ) { + SplitNode split = makeSplit("def/self",round,lrg); + insertAfterAndReplace(split,def,false); + if( split.nOuts()==0 ) + split.killOrdered(); + } insertBefore(phi,1,"use/self/phi",round,lrg); } // Split before two-address ops which extend the live range @@ -375,6 +477,13 @@ public class RegAlloc { return true; } + private void deferLoopSelf(PhiNode phi, IdentityHashMap<PhiNode,String> deferred) { + if( !_deferredLoopSelf.containsKey(phi) ) { + _deferredLoopSelf.put(phi,""); + deferred.put(phi,""); + } + } + // Generic: split around the outermost loop with non-split def/uses. This // covers both self-conflicts (once we split deep enough) and register @@ -401,9 +510,11 @@ public class RegAlloc { int min = (int)ld; int max = (int)(ld>>32); - - // If the minLoopDepth is less than the maxLoopDepth: for-all defs and - // uses, if at minLoopDepth or lower, split after def and before use. + boolean emptyMulti = lrg._mask.isEmpty() && lrg._multiDef && lrg._1regDefCnt <= 1 && + (lrg._1regUseCnt > 1 || _ns._len > 5); + // Multi-def empty-mask conflicts need the hot/deep side isolated from + // fixed register uses. Ordinary pressure splits keep the old shallow + // boundary behavior. for( Node n : _ns ) { if( n instanceof SplitNode && min!=max ) continue; // Ignoring splits; since spilling need to split in a deeper loop if( n.isDead() ) continue; // Some Cloneable went dead by other spill changes @@ -414,7 +525,7 @@ public class RegAlloc { if( lrg(n)==lrg && // This is a LRG def // At loop boundary, or splitting in inner loop - (min==max || n.cfg0().loopDepth() <= min) ) { + (min==max || (emptyMulti ? n.cfg0().loopDepth() >= max : n.cfg0().loopDepth() <= min)) ) { // Cloneable constants will be cloned at uses, not after def if( !(n instanceof MachNode mach && mach.isClone()) && // Single user is already a split adjacent @@ -429,7 +540,7 @@ public class RegAlloc { // No split in front of a split if( !(n.in(i) instanceof SplitNode) && // splitting in inner loop or at loop border - (min==max || phi.region().cfg(i).loopDepth() <= min) && + (min==max || (emptyMulti ? phi.region().cfg(i).loopDepth() >= max : phi.region().cfg(i).loopDepth() <= min)) && // and not around the backedge of a loop (bad place to force a split, hard to remove) !(phi.region() instanceof LoopNode && i==2 && (phi.in(i) instanceof PhiNode pp && pp.region()==phi.region())) ) // Split before phi-use in prior block @@ -441,7 +552,8 @@ public class RegAlloc { // This is a LRG use // splitting in inner loop or at loop border if( lrgSame( n.in( i ), lrg ) && - (min == max || (n.in(i) instanceof MachNode mach && mach.isClone()) || n.cfg0().loopDepth() <= min) ) + (min == max || (n.in(i) instanceof MachNode mach && mach.isClone()) || + (emptyMulti ? n.cfg0().loopDepth() >= max : n.cfg0().loopDepth() <= min)) ) // Split before in this block insertBefore( n, i, "use/loop/use", round,lrg, false ); } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Serialize.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Serialize.java index 8014bb2c..7c230f9c 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Serialize.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Serialize.java @@ -177,7 +177,6 @@ abstract public class Serialize { IdentityHashMap<Node,Integer> anodes = new IdentityHashMap<>(); for( Node n : nodes ) anodes.put(n,anodes.size()+1); // +1 bias, reserve 0 for null - // First cut: 1 byte opcode, optional per-node info, includes variable nIns for( Node n : nodes ) { baos.packed1(n.serialTag().ordinal()); @@ -367,9 +366,11 @@ abstract public class Serialize { // MemMerge precise aliases are encoded by their input slot. // Remap populated file-local slots into this compilation's // local alias numbering; null holes carry no identity. - int local = n instanceof MemMergeNode && i >= GlobalBits.RESERVED && def != null - ? aliases.map(fileAliases,i) - : i; + int local = i; + if( n instanceof MemMergeNode && i >= GlobalBits.RESERVED ) { + if( def == null ) continue; + local = aliases.map(fileAliases,i); + } n.setDefX(local,def); // Call's output[0] is always the CallEnd if( n instanceof CallEndNode cend && i==0 ) { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 8e7f47f3..061232c7 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -16,6 +16,12 @@ public class CallEndNode extends CFGNode implements MultiNode { // When set true, this Call/CallEnd/Fun/Return is being trivially inlined boolean _folding; + // +2 must clone, so await all cleanup but OK + // +1 trivial now, + // 0: take a look, + // -1: somethings wrong, but might improve + // -2: never and stop asking, + private byte _inline; public final TypeRPC _rpc; public CallEndNode(CallNode call, TypeRPC rpc) { @@ -51,6 +57,7 @@ public class CallEndNode extends CFGNode implements MultiNode { public CallNode call() { return (CallNode)in(0); } boolean folding() { return _folding; } + public byte inline() { return _inline; } @Override public CFGNode idom(Node dep) { // Folding the idom is the one inlining Return @@ -101,14 +108,10 @@ public class CallEndNode extends CFGNode implements MultiNode { // appear later - meanwhile, we use a conservative approx of memory // effects. if( (nIns()-1)+externs < tfp.nfcns() ) { - // If before SCCP, we might call extras or also the unknown target. - StartNode start = CodeGen.CODE._start; - addDep(start); - Type tmem = start._type instanceof TypeTuple tt ? tt._types[1] : (start._type.isHigh() ? TypeMem.TOP : TypeMem.BOT); - Type ret = tfp.ret(); // If during Opto, assume call won't be called and thus won't return anything. - if( CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Opto.ordinal() ) - ret = Type.TOP; + boolean opto = CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Opto.ordinal(); + Type tmem = opto ? TypeMem.TOP : TypeMem.BOT; + Type ret = opto ? Type.TOP : tfp.ret(); return TypeTuple.make(Type.CONTROL,tmem,ret); } @@ -118,6 +121,12 @@ public class CallEndNode extends CFGNode implements MultiNode { : TypeTuple.STATE.dual(); for( int i=1; i<nIns(); i++ ) state = (TypeTuple)state.meet(in(i)._type); + // A reachable call whose presently linked exits are all unreachable + // keeps a conservative continuation. In particular, do not let a + // transient no-return result tear down the caller during SCCP. + if( state.ctl()==Type.XCONTROL && + CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Opto.ordinal() ) + return TypeTuple.make(Type.CONTROL,TypeMem.TOP,Type.TOP); // At least as good as the TFP return state.makeFrom(2,state.ret().join(tfp.ret())); } @@ -125,125 +134,112 @@ public class CallEndNode extends CFGNode implements MultiNode { @Override public Node idealize() { - // Worklist-based inlining. Cannot inline if folding, or calling - // multiple targets or no CallNode (malformed because dying). - if( !_folding && nIns()==2 && in(0) instanceof CallNode call ) { - Node fptr = call.fptr(); - if( fptr.isConst() && // We have an immediate call - // Function is being called, and its not-null - fptr._type instanceof TypeFunPtr tfp && tfp.notNull() && !tfp.isHigh() && - // Arguments are correct - call.nargs()==tfp.nargs() && goodArgs(call,tfp) ) { - ReturnNode ret = (ReturnNode)in(1); - FunNode fun = ret.fun(); - int isTrivial = trivialInlining( fptr, fun ); - - // Encouraged inlining because small size and constructor. - int maxSize = fun._name!=null && fun.isInit() && !fun.isClz() ? 200 : 100; - if( isTrivial==1 && fun._approxUIDs < maxSize ) { - assert fun.sig().isa(tfp); - assert !CodeGen.CODE._midAssert; // Triggered inlining - CodeGen.CODE.add(fun); - // Remove the existing function linkage - call.unlink_all(); - // Clone the function body - FunNode fun2 = fun.copyBody(); - // Call uses the unique new function - Node fptr2 = new FunPtrNode(fun2.sig(),CodeGen.CODE._start,fun2.ret()).peephole(); - call.setDef(call.nIns()-1,fptr2); - // Link to the new function - call.link(fun2); - fun = fun2; - assert trivialInlining( fptr2, fun2 )==0; - isTrivial = 0; - } - - // Trivial inlining: call site calls a single function; single function - // is only called by this call site. - if( isTrivial==0 ) - return doTrivialInlining(fun); - - } else { // Function not (yet) a constant function pointer - addDep(fptr); - } + _inline = inlineCandidate(); + if( _inline == 1 ) { + ReturnNode ret = (ReturnNode)in(1); + FunNode fun = ret.fun(); + doTrivialInlining(fun); + return this; } + // Delay for cleanup, before cloning + if( _inline >= 2 ) + CodeGen.CODE._iter.deferInline(CodeGen.CODE,this); return null; } - boolean goodArgs( CallNode call, TypeFunPtr tfp ) { - for( int i=0; i<tfp.nargs(); i++ ) { - Node arg = call.arg(i+2); - // The graph's function-pointer type can still contain open forward - // references here. Compare against its recursively upgraded form, - // so deep mutability requirements participate before inlining. - Type formal = tfp.arg(i).upgradeType(Parser.TYPES); - if( !arg._type.isa(formal) ) - { addDep(arg); return false; } - } - return true; - } + // Check if candidate right now, sets no flags + private byte inlineCandidate() { + if( _inline < -2 ) return -2; // Never + if( _folding ) return -2; // No, and will collapse anyways + if( !(in(0) instanceof CallNode call) ) return -2; // malformed because mid-death + if( nIns()!=2 ) return -1; // Not exactly 1 link, but can change + + // Have exactly 1 linked function + ReturnNode ret = (ReturnNode)in(1); + FunNode fun = ret.fun(); - // Check for trivial inlining: call only calls fun; fun only called by - // call. Returns 0 for trivial, +1 for not-trivial because fptr/fun, and - // -1 for not-trivial because idoms. - public int trivialInlining( Node fptr, FunNode fun ) { // Heuristic forced inlining off via name if( fun._name != null && fun._name.endsWith("_noInline") ) - return -1; - - if( !fun.sig().isa(fptr._type) ) - return -1; // Stall until these align + return -2; // Never, stop asking // Disallow self-recursive inlining (loop unrolling by another name). for( int i=1; i < fun.nIns(); i++ ) if( fun.cfg(i).fun()==fun ) // Check for linked call input inside "fun" - { addDep(fun); return -1; } - - CFGNode idom = call(), prior = this; - while( !(idom instanceof FunNode) ) { - if( idom==null ) { - addDep(prior); - if( prior instanceof RegionNode && !(prior instanceof StartNode) ) - for( int i=1; i<prior.nIns(); i++ ) - addDep(prior.in(i)); - return -1; - } - prior = idom; - idom = idom.idom(); - } - + { addDep(fun); return -1; } // No, but can lose the recursive edge + + // Things that might improve, so not now a candidate + Node fptr = call.fptr(); + // Constant Function is being called, and its not-null + if( !(fptr._type instanceof TypeFunPtr tfp && tfp.notNull() && tfp.isConstant()) ) + { addDep(fptr); return -1; } + + // Arguments are correct + if( call.nargs()!=tfp.nargs() || !goodArgs(call,tfp) ) + { addDep(fptr); return -1; } + + // Encouraged inlining because small size and constructor. + int maxSize = fun._name!=null && fun.isInit() && !fun.isClz() ? 200 : 100; + if( fun._approxUIDs >= maxSize ) + return -2; // Try later (if shrinking helps) + if( fun.body().cardinality() >= maxSize ) + return -1; // Try later (if cleanup makes the real body small enough) + + // Can be cloned but not trivial + if( fun.nIns() > 2 ) { addDep(fun); return 2; } + + // A candidate right now + return 1; + } - // If the *inlined* function is mid-collapse, also do not inline (yet) - idom = fun.ret(); - while( idom != fun ) { - if( idom==null ) return -1; // Forced off, half-folded call - if( idom instanceof FunNode fun2 ) - { addDep(fun2); return -1; } - if( idom instanceof CallEndNode cend && cend._folding ) - { addDep(cend); return -1; } - idom = idom.idom(); + public void doInline() { + assert _inline > 0; // Only called when possible to inline + + ReturnNode ret = (ReturnNode)in(1); + FunNode fun = ret.fun(); + CallNode call = call(); + assert fun.sig().isa(call.fptr()._type); + + // Clone first + if( _inline==2 ) { + assert !CodeGen.CODE._midAssert; // Triggered inlining + // Remove the existing function linkage + call.unlink_all(); + // Clone the function body + FunNode fun2 = fun.copyBody(); + // Call uses the unique new function + Node fptr2 = new FunPtrNode(fun2.sig(),CodeGen.CODE._start,fun2.ret()).peephole(); + call.setDef(call.nIns()-1,fptr2); + // Link to the new function + call.link(fun2); + fun = fun2; } - // Only fun user is this call - if( fun.nIns() > 2 ) { addDep(fun); return 1; } // Trivial inlining: call site calls a single function; single function // is only called by this call site. - assert fun.in(1)==call(); + doTrivialInlining(fun); + } - return 0; + boolean goodArgs( CallNode call, TypeFunPtr tfp ) { + for( int i=0; i<tfp.nargs(); i++ ) { + Node arg = call.arg(i+2); + // The graph's function-pointer type can still contain open forward + // references here. Compare against its recursively upgraded form, + // so deep mutability requirements participate before inlining. + Type formal = tfp.arg(i).upgradeType(Parser.TYPES); + if( !arg._type.isa(formal) ) + { addDep(arg); return false; } + } + return true; } // Do trivial inlining. Inlining does not need to clone code, merely // triggers folding the Call/Fun and Return/CallEnd away. - private Node doTrivialInlining( FunNode fun ) { + private boolean doTrivialInlining( FunNode fun ) { assert !CodeGen.CODE._midAssert; // Triggered inlining - // Add the size heuristic to grow caller, preventing self-recursive - // functions from endlessly inlining. - fun()._approxUIDs += fun._approxUIDs; // Trivial inline: rewrite _folding = true; // Rewrite Fun so the normal RegionNode ideal collapses @@ -260,7 +256,12 @@ public class CallEndNode extends CFGNode implements MultiNode { // Inlining immediately blows all cache idepth fields past the inline point. // Bump the global version number invalidating them en-masse. CodeGen.CODE.invalidateIDepthCaches(); - return this; + // More peeps + CodeGen.CODE.add(fun); + CodeGen.CODE.add(this); + CodeGen.CODE.addAll(_outputs); + CodeGen.CODE.addAll(_inputs); + return true; // Always return true } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java index f2825650..90d7e379 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeFunPtr; import com.seaofnodes.simple.type.TypeMem; +import com.seaofnodes.simple.type.TypeRPC; import com.seaofnodes.simple.type.XInt; import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; @@ -129,8 +130,15 @@ public class CallNode extends CFGNode { assert !linked(fun); fun.addDef(this); for( Node use : fun._outputs ) - if( use instanceof ParmNode parm ) - parm.addDef(parm._idx==0 ? ConstantNode.seed(cend()._rpc).peephole() : arg(parm._idx)); + if( use instanceof ParmNode parm ) { + Node def = parm._idx==0 ? ConstantNode.seed(cend()._rpc).peephole() : arg(parm._idx); + parm.addDef(def); + // Linking can happen during post-SCCP inlining. Keep an RPC + // Parm's cached finite set synchronized with its newly added + // input instead of waiting for the next worklist visit. + if( parm._idx==0 && parm._type instanceof TypeRPC ) + parm._type = parm._type.meet(def._type); + } // Call end points to function return CodeGen.CODE.add(cend()).addDef(fun.ret()); return this; @@ -168,7 +176,7 @@ public class CallNode extends CFGNode { if( fptr()._type == Type.BOTTOM ) return null; // Wrong, but failing earlier if( !(fptr()._type instanceof TypeFunPtr tfp) ) - throw Utils.TODO(); + return Parser.error("Expected a function, but found " + fptr()._type, _loc); if( !tfp.notNull() ) return Parser.error( "Might be null calling "+tfp, _loc); if( nargs() != tfp.nargs() ) diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/EscapeNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/EscapeNode.java index df654291..d1ff3f65 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/EscapeNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/EscapeNode.java @@ -70,7 +70,7 @@ public class EscapeNode extends TypeNode { Type tpub = mpub._t; // t is meet of pub & priv. Pub memory can be very weak (e.g. alias 1) - // and we're no worse than GLB of private + // and we're no worse than the declared field type Type t = tpriv.meet(tpub).join(fld._t); int[] fidxes = XInt.meet(mpriv._escFs, mpub._escFs); int[] aliases = XInt.meet(mpriv._escAs, mpub._escAs); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/FRefNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/FRefNode.java index 723e0007..698ba755 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/FRefNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/FRefNode.java @@ -23,7 +23,12 @@ public class FRefNode extends ConstantNode { public String _name; public final Parser.Lexer _loc; // Source location - public FRefNode( String name, Parser.Lexer loc ) { super(FREF_TYPE); _name = name; _loc = loc; } + public FRefNode( String name, Parser.Lexer loc ) { this(name,loc,FREF_TYPE); } + public FRefNode( String name, Parser.Lexer loc, Type type ) { + super(type); + _name = name; + _loc = loc; + } @Override public String label() { return "FRef"+_name; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java index 5018f5d6..419cf083 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -91,7 +91,7 @@ public class FunNode extends RegionNode { // Signature can improve over time public TypeFunPtr sig() { return _sig; } public void setSig( TypeFunPtr sig ) { - assert sig.isa(_sig); + assert sig.isa(_sig) || resolvesForwardSelf(sig,_sig); if( _sig != sig ) { CODE.add(this); // Changing the signature can allow more inlining @@ -104,6 +104,20 @@ public class FunNode extends RegionNode { } } + // A class initializer starts parsing with an open singleton receiver and + // closes that same receiver after discovering its fields. Function + // arguments are contravariant, so ordinary isa does not describe this + // parser-time forward-reference resolution even though every other part + // of the signature sharpens normally. + private static boolean resolvesForwardSelf(TypeFunPtr sig, TypeFunPtr old) { + if( !(sig.arg(0) instanceof TypeMemPtr now) || + !(old.arg(0) instanceof TypeMemPtr prior) || + now._obj._name != prior._obj._name || + !prior._obj._open || now._obj._open ) + return false; + return sig.makeFrom(old.arg(0),0).isa(old); + } + @Override boolean _upgradeType( HashMap<String,Type> TYPES) { TypeFunPtr sig = (TypeFunPtr)_sig.upgradeType(TYPES); if( sig == _sig ) return false; @@ -323,12 +337,20 @@ public class FunNode extends RegionNode { ReturnNode ret2 = (ReturnNode)map.get(_ret); fun2._ret = ret2; ret2._fun = fun2; + BitSet body2 = new BitSet(); + for( Node n : map.values() ) + body2.set(n._nid); + + // Remove non-body callers. Body-local call edges were cloned along + // with their CallEnds and must stay linked so their cloned types remain + // monotonic during the post-Opto Iter. + for( int i=1; i<fun2.nIns(); i++ ) + if( !(fun2.in(i) instanceof CallNode call) || !body2.get(call._nid) ) + fun2.removeDeadPath(i--); - // Remove all callers - this is a private copy - while( fun2.nIns() > 1 ) - if( fun2.in(1) instanceof CallNode call && body.get(call._nid) ) - call.unlink(fun2,1); // Recursive calls unlink - else fun2.removeDeadPath(1); // Start and external calls can just be removed + for( Node old : map.keySet() ) + if( old instanceof CallNode oldCall ) + relinkClonedCall(oldCall,(CallNode)map.get(oldCall),map); // Flip to a new FIDX to avoid confusion with the old one. // This is a non-monotonic (sideways) type move, only applicable @@ -338,6 +360,23 @@ public class FunNode extends RegionNode { return fun2; } + private static void relinkClonedCall( CallNode oldCall, CallNode call, IdentityHashMap<Node,Node> map ) { + CallEndNode oldCend = oldCall.cend(); + if( oldCend==null || oldCend._folding ) + return; + for( int i=1; i<oldCend.nIns(); i++ ) { + ReturnNode oldRet = (ReturnNode)oldCend.in(i); + FunNode oldFun = oldRet.fun(); + FunNode fun = (FunNode)map.get(oldFun); + if( fun==null ) fun = oldFun; + if( !call.linked(fun) ) + call.link(fun); + } + CallEndNode cend = call.cend(); + if( cend.nIns() > 1 ) + cend._type = cend.compute(); + } + // Clone small function private void bodyCopy( BitSet visit, BitSet body, IdentityHashMap<Node,Node> map, Node n ) { if( n==null ) return; @@ -357,18 +396,20 @@ public class FunNode extends RegionNode { if( visit.get(n._nid) ) return; // Been there, done that visit.set(n._nid); Node m = map.get(n); - // The cloned Call should not clone any linked edges. - if( n instanceof CallEndNode cend && !cend._folding ) { - m.addDef( map.get(cend.call()) ); - } else { - for( Node e : n._inputs ) { - Node x = e; - if( e != null ) { - x = map.get(e); - if( x == null ) x = e; + for( Node e : n._inputs ) { + Node x = e; + if( e != null ) { + if( n instanceof CallEndNode cend && e != cend.call() && + (!(e instanceof ReturnNode ret) || map.get(ret.fun()) == null) ) + continue; + x = map.get(e); + if( x == null ) { + if( n instanceof CallEndNode cend && e != cend.call() ) + continue; + x = e; } - m.addDef(x); } + m.addDef(x); } for( Node x : n._outputs ) bodyEdge(visit,body,map,x); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java index f67f2b97..4ff2bd82 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -102,8 +102,7 @@ public class LoadNode extends MemOpNode { // baked into the type system. Loads into arrays DO need the ctrl // edge, at least until proper range-checking is in place. if( in(0)!=null && ptr()._type instanceof TypeMemPtr tmp && - // Never can be an array - (!tmp._obj._open || (tmp._obj._fields.length > 1 && tmp._obj._fields[0]._fname != "#")) ) { + !tmp._obj.isAry() ) { setDef(0,null); return this; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index a88748b5..e4e7d607 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -113,7 +113,8 @@ public class MemMergeNode extends Node { if( XInt.bit(mem._escAs,i) ) { Node n = in(i); if( n != null && !n._type.isHigh() ) { - TypeMem mem2 = (TypeMem)mem.meet(n._type); + TypeMem nmem2 = ((TypeMem)n._type).makeFrom(mem._escFs, mem._escAs); + TypeMem mem2 = (TypeMem)mem.meet(nmem2); // More escape aliases if( mem2 != mem ) { mem = mem2; progress = true; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index d824bc3a..59f7c304 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -43,15 +43,15 @@ public abstract class MemOpNode extends TypeNode { // Source location for late reported errors public final Parser.Lexer _loc; - public MemOpNode(Parser.Lexer loc, String name, int alias, boolean isLoad, Type glb, Node ctrl, Node mem, Node ptr, Node off) { - super(glb, ctrl, mem, ptr, off); + public MemOpNode(Parser.Lexer loc, String name, int alias, boolean isLoad, Type decl, Node ctrl, Node mem, Node ptr, Node off) { + super(decl, ctrl, mem, ptr, off); _name = name; _alias = alias; _loc = loc; _isLoad = isLoad; } - public MemOpNode(Parser.Lexer loc, String name, int alias, boolean isLoad, Type glb, Node ctrl, Node mem, Node ptr, Node off, Node value) { - this(loc, name, alias, isLoad, glb, ctrl, mem, ptr, off); + public MemOpNode(Parser.Lexer loc, String name, int alias, boolean isLoad, Type decl, Node ctrl, Node mem, Node ptr, Node off, Node value) { + this(loc, name, alias, isLoad, decl, ctrl, mem, ptr, off); addDef(value); } public MemOpNode( Node ideal, MemOpNode mop ) { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/ParmNode.java index 6488b827..51ea28b0 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -73,7 +73,9 @@ public class ParmNode extends PhiNode { @Override public Node idealize() { if( !(region() instanceof FunNode) ) - return in(1); // Input has collapse to e.g. starting control. + // A dead function can lose every caller before the Parm itself is + // removed; there is no replacement input in that transient form. + return nIns()==1 ? null : in(1); // Input has collapse to e.g. starting control. // If function is folding, do all possible peeps if( fun()._folding ) return super.idealize(); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 2c57eb8b..2ae3c752 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -76,7 +76,7 @@ public class PhiNode extends Node { if( !(region() instanceof RegionNode r) ) 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() ) + if( r.inProgress() || in(nIns()-1)==null ) return declaredType(); // Set type to local top of the starting type Type t = Type.TOP; @@ -219,7 +219,7 @@ public class PhiNode extends Node { if( in(i).in(j) != x ) { needsPhi=true; break; } if( needsPhi ) { - x = make(_label,op.in(j)._type.glb(false)); + x = make(_label,op.in(j)._type); x.addDef(region()); for( int i=1; i<nIns(); i++ ) x.addDef(in(i).in(j)); @@ -273,13 +273,12 @@ public class PhiNode extends Node { @Override public Parser.ParseException err() { - if( _type != Type.BOTTOM && _type != TypeScalar.BOT ) return null; + if( _type != Type.BOTTOM ) return null; - // Scalar BOT means we mixed scalar families, e.g. int and ptr. // Global BOTTOM retains the same role for non-scalar families. for( int i=1; i<nIns(); i++ ) // Already an error, but better error messages come from elsewhere - if( in(i)._type == Type.BOTTOM || in(i)._type == TypeScalar.BOT ) + if( in(i)._type == Type.BOTTOM ) return null; SB sb = new SB().p("No common type amongst "); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index b60d27d7..0dc14fd2 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -67,6 +67,9 @@ public class ReturnNode extends CFGNode { if( ctrl()._type == Type.CONTROL && expr()._type == Type.TOP ) return Parser.error("No defined return type",null); + if( ctrl()._type == Type.CONTROL && + expr()._type == TypeScalar.BOT ) + return Parser.error("Cannot return generic scalar",null); // With no user constructor, <init> doubles as the public no-arg // constructor. Required fields remain TOP in its private memory: a // typed parser poison which deliberately emitted no Store or code. diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 58508a1c..dd5fa541 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -240,20 +240,16 @@ public class ScopeNode extends MemMergeNode { return true; } - // Normal lookup was tried and failed. Insert a forward ref outside any - // enclosing Kind.Func scope, skipping any nested Blocks or Allocs and - // return the Var. May insert at the outermost scope, which means this - // must be defined externally, or it's an error. + // Normal lookup was tried and failed. Append a forward ref in the current + // lexical scope. Scope pops promote it outwards "as if" the final constant + // had been declared before the using scope. public Var defineFRef( String id, Type t, boolean xfinal, Parser.Lexer loc ) { - // Kind/Lexical scope index - int kidx = enclosingFunction(); - int idx = _kinds.at(kidx)._lexSize; - Var var = new Var(idx,id,t,xfinal,loc,true); + Var var = new Var(nIns(),id,t,xfinal,loc,true); FRefNode fref = new FRefNode(id,loc).init(); fref._type = fref._con = t; - // Insert in the lex scope just prior to kidx - insert(var,fref,kidx); + _vars.add(var); + addDef(fref); return var; } @@ -406,6 +402,18 @@ public class ScopeNode extends MemMergeNode { } } + public void balanceLoopFRefs( ScopeNode scope ) { + for( int i = nIns(); i < scope.nIns(); i++ ) { + Var n = scope.var(i); + if( n.isFRef() ) { // Loop body has forward refs + Var v = new Var(nIns(),n._name,n.type(),n._final,n._loc,true); + v._uninit = n._uninit; + _vars.add(v); + addDef(scope.in(i)); + } + } + } + // ------------------------------------------------ // peephole the backedge scope into this loop head scope @@ -426,8 +434,10 @@ public class ScopeNode extends MemMergeNode { for( int i=1; i<nIns(); i++ ) { if( var(i)._final ) continue; // Final vars did not get modified in the loop Node n = in(i); - if( var(i).type().isHighOrConst() ) { // Cannot lift higher than a constant, so no Phi - n.subsume(n=ConstantNode.make(var(i).type()).init()); + if( var(i).type().isHighOrConst() && !(n instanceof PhiNode phi && phi.inProgress()) ) { // Cannot lift higher than a constant, so no Phi + Node con = ConstantNode.make(var(i).type()).init(); + n.subsume(con); + n = con; } else if( back.in(i) != scope ) { PhiNode phi = (PhiNode)n; assert phi.region()==scope.ctrl() && phi.in(2)==null; @@ -441,12 +451,48 @@ public class ScopeNode extends MemMergeNode { // ------------------------------------------------ // Up-casting: using the results of an If to improve a value. // E.g. "if( ptr ) ptr.field;" is legal because ptr is known not-null. + // + // This operation is lexical, not semantic, and thus its behavior changes + // the language spec. Optimizations that hide the lexical structure + // (e.g. constant folding control flow) can hide what is guarded or how the + // guard is applied, making it somewhat fragile. Several good use cases + // are covered here, but not everything you might like. + // TODO: Make this more robust for shapes like: + // ``` + // if( !ary || !ary# ) exit(); + // for( ...; ary# ) ...; + // ``` + // Here the guard ends up guarding the whole expression (both ary and ary# + // are not-null), but loses that ary is not-null. A better answer might be + // a dedicated logical expression node, or some sort of gather-of-checked + // values to Guard post-test. + public void addGuards( Node ctrl, Node pred, boolean invert ) { assert ctrl instanceof CFGNode; _guards.add(ctrl); // Marker to distinguish 0,1,2 guards // add pred & its cast to the normal input list, with special Vars if( pred==null || pred.isDead() ) return; // Dead, do not add any guards + _addGuards(ctrl,pred,invert); + } + + private void _addGuards( Node ctrl, Node pred, boolean invert ) { + if( pred==null || pred.isDead() ) + return; + // Short-circuit logic is represented by a Phi. For `a || b` being + // false, or `a && b` being true, both individual operands have the + // same proven value as the whole expression. The "skipped RHS" path + // is the Region input whose Phi value is the controlling If predicate. + if( pred instanceof PhiNode phi && phi.nIns()==3 && phi.region() instanceof RegionNode r && r.nIns()==3 ) + for( int i=1; i<3; i++ ) + if( r.in(i) instanceof CProjNode prj && prj.ctrl() instanceof IfNode iff ) { + Node skip = shortCircuitSkippedPred(phi.in(i),iff.pred(),prj,invert); + if( skip != null ) { + _addGuards(ctrl,skip,invert); + _addGuards(ctrl,phi.in(3-i),invert); + break; + } + } // Invert the If conditional if( invert ) pred = pred instanceof NotNode not ? not.in(1) : CodeGen.CODE.add(new NotNode(pred).peephole()); @@ -460,6 +506,20 @@ public class ScopeNode extends MemMergeNode { _addGuard(false,ctrl,zeroPred); } + private static Node shortCircuitSkippedPred( Node val, Node pred, CProjNode prj, boolean invert ) { + if( val == null ) + return null; + if( val == pred ) + return (prj._idx==0)==invert ? val : null; + if( val instanceof NotNode not && not.in(1)==pred ) + return (prj._idx==1)==invert ? val : null; + if( val._type == TypeInteger.TRUE && invert ) + return prj._idx==0 ? pred : CodeGen.CODE.add(new NotNode(pred).peephole()); + if( val._type == TypeInteger.FALSE && !invert ) + return prj._idx==1 ? pred : CodeGen.CODE.add(new NotNode(pred).peephole()); + return null; + } + private void _addGuard(boolean nonZero, Node ctrl, Node pred) { Node guard = new GuardNode(nonZero,ctrl,pred).peephole(); if( guard != pred ) { @@ -467,7 +527,7 @@ public class ScopeNode extends MemMergeNode { guard.keep(); _guards.add(pred); _guards.add(guard); - replace(pred,guard); + replace(pred,guard,nonZero); } } @@ -512,13 +572,27 @@ public class ScopeNode extends MemMergeNode { } - private void replace( Node old, Node cast ) { + private void replace( Node old, Node cast, boolean nonZero ) { assert old!=null && old!=cast; for( int i=0; i<nIns(); i++ ) - if( in(i)==old ) + if( in(i)==old || nonZero && nullCheckedPhi(in(i),old) ) setDef(i,cast); } + private static boolean nullCheckedPhi( Node n, Node old ) { + if( !(n instanceof PhiNode phi) || phi.nIns()!=3 ) + return false; + if( phi.in(1)==null || phi.in(2)==null ) + return false; + int zero = phi.in(1)._type == phi.in(1)._type.makeZero() ? 1 : + phi.in(2)._type == phi.in(2)._type.makeZero() ? 2 : -1; + if( zero == -1 ) + return false; + Node val = phi.in(3-zero); + return val==old || + val instanceof GuardNode guard && guard._nonZero && guard.in(1)==old; + } + // ------------------------------------------------------------------------ // Insert a top-level public external symbol, "as-if" some #include/import // was executed at the top of tile. diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java index c0006511..bd268af2 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -28,11 +28,11 @@ public class StoreNode extends MemOpNode { * @param off The offset inside the struct base * @param value Value to be stored */ - public StoreNode(Parser.Lexer loc, String name, int alias, Type glb, Node ctrl, Node mem, Node ptr, Node off, Node value, boolean init) { - this(loc,name,alias,glb,ctrl,mem,ptr,off,value,init,(byte)0); + public StoreNode(Parser.Lexer loc, String name, int alias, Type decl, Node ctrl, Node mem, Node ptr, Node off, Node value, boolean init) { + this(loc,name,alias,decl,ctrl,mem,ptr,off,value,init,(byte)0); } - private StoreNode(Parser.Lexer loc, String name, int alias, Type glb, Node ctrl, Node mem, Node ptr, Node off, Node value, boolean init, byte size) { - super(loc, name, alias, false, glb, ctrl, mem, ptr, off, value); + private StoreNode(Parser.Lexer loc, String name, int alias, Type decl, Node ctrl, Node mem, Node ptr, Node off, Node value, boolean init, byte size) { + super(loc, name, alias, false, decl, ctrl, mem, ptr, off, value); _init = init; _size = size; } @@ -235,7 +235,7 @@ public class StoreNode extends MemOpNode { private static byte storeSize(Type decl) { // `decl` is the target field declaration, not the stored value. In // particular a constant zero stored into u32 is still a 4-byte Store; - // taking the constant's GLB here would incorrectly select i64. + // taking the constant's natural width here would incorrectly select i64. byte size = (byte)(1 << decl.log_size()); assert size==1 || size==2 || size==4 || size==8; return size; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java index ebd6a5ae..100bbd2a 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java @@ -27,7 +27,9 @@ public class StoreRISC extends MemOpRISC { if( i==1 ) return null; // mem if( i==2 ) return riscv.RMASK; // ptr // 2 - index - if( i==4 ) return riscv.MEM_MASK; // Wide mask to store GPR and FPR + if( i==4 ) return _bytes >= 4 + ? riscv.MEM_MASK // Word/dword value in GPR or FPR + : riscv.RMASK; // Byte/short stores require a GPR return null; // Anti-dependence } @Override public RegMask outregmap() { return null; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpMemX86.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpMemX86.java index 24812fea..9d131fc6 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpMemX86.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpMemX86.java @@ -38,7 +38,7 @@ public class CmpMemX86 extends MemOpX86 { case 0: enc.add1(_imm); break; case 1: enc.add2(_imm); break; case 2: enc.add4(_imm); break; - case 3: enc.add8(_imm); break; + case 3: enc.add4(_imm); break; } } else { encVal(enc, _con, ptr, idx, src, _off, _scale, _swap); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java index 6069c07b..bfaf7a91 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java @@ -67,7 +67,7 @@ public abstract class MemOpX86 extends MemOpNode implements MachNode { if( i==1 ) return null; // Memory if( i==2 ) return x86_64_v2.RMASK; // base in GPR if( i==3 ) return x86_64_v2.RMASK; // index in GPR - if( i==4 ) return _sz >= 2 + if( i==4 ) return _sz >= '4' ? x86_64_v2.MEM_MASK // value in GPR or XMM : x86_64_v2.RMASK; // Bytes and shorts in GPR only return null; // Anti-dependence diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java index d9056be9..7db80299 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java @@ -17,23 +17,20 @@ public class NotX86 extends MachConcreteNode implements MachNode { short dst = enc.reg(this ); short src = enc.reg(in(1)); - // Pre-zero using XOR dst,dst; since zero'd will not have a - // byte-dependency from the setz. Can skip REX is dst is low 8, makes - // this a 32b xor, which will also zero the high bits. - if( dst >= 8 ) enc.add1(x86_64_v2.rex(dst, dst, 0)); - enc.add1(0x33); // opcode - enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, dst, dst)); - // test rdi,rdi enc.add1(x86_64_v2.rex(src, src, 0)); enc.add1(0x85); enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, src, src)); - // setz (sete dil) - enc.add1(x86_64_v2.rex(dst, 0, 0)); + // setz dstb; then zero-extend the low byte into the full register. + if( dst >= 4 ) enc.add1(x86_64_v2.rex(0, dst, 0, false)); enc.add1(0x0F); enc.add1(0x94); - enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, dst, 0)); + enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, 0, dst)); + if( dst >= 4 ) enc.add1(x86_64_v2.rex(dst, dst, 0, false)); + enc.add1(0x0F); + enc.add1(0xB6); + enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, dst, dst)); } @Override public void asm(CodeGen code, SB sb) { sb.p(code.reg(this)); } } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java index a1ad17dc..4cabefca 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java @@ -511,7 +511,8 @@ public class x86_64_v2 extends Machine { // Operands swap in the encoding directly, no need for Set/Jmp to swap `bop` if( rhs instanceof LoadNode ld && ld.nOuts() == 1 && lhs._type.isa(ld.declaredType()) && - (val!=null || bool.op()=="==" || bool.op()=="!=") ) + (!(lhs instanceof ConstantNode con && con._con instanceof TypeInteger ti && imm32(ti.value())) || + bool.op()=="==" || bool.op()=="!=") ) return new CmpMemX86(bool, address(ld), ld.ptr(), idx, off, scale, imm(lhs), val, true ); // Vs immediate @@ -667,7 +668,7 @@ public class x86_64_v2 extends Machine { private int imm( Node xval ) { assert val == null && imm == 0; - if( xval instanceof ConstantNode con && con._con instanceof TypeInteger ti) { + if( xval instanceof ConstantNode con && con._con instanceof TypeInteger ti && ti.isConstant() && imm32(ti.value()) ) { val = null; imm = (int) ti.value(); assert imm == ti.value(); // In 32-bit range diff --git a/chapter25/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java b/chapter25/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java index 206983a0..e15d7dbe 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java @@ -14,23 +14,26 @@ public abstract class ASMPrinter { public static SB print(SB sb, CodeGen code ) { Encoding enc = code._encoding; - if( enc == null ) return sb.p("No encoding for ").p(code._srcName); + Ary<CFGNode> cfg = enc == null ? code._cfg : enc._cfg; + if( cfg == null || cfg._len == 0 ) return sb.p("No scheduled code for ").p(code._srcName); // instruction address int iadr = 0; // Print all functions in order - for( int i=0; i<enc._cfg._len; i++ ) - if( enc._cfg.at(i) instanceof FunNode fun ) - iadr = print(iadr,sb,code,enc,fun,i); + for( int i=0; i<cfg._len; i++ ) + if( cfg.at(i) instanceof FunNode fun ) + iadr = print(iadr,sb,code,enc,cfg,fun,i); // constant pools - iadr = (iadr+15)&-16; // pad to 16 - if( enc._cpool.size()>0 ) - iadr = printConstantPool(iadr, sb, enc._cpool,enc._bigCons,true ,"Constant Pool"); + if( enc != null ) { + iadr = (iadr+15)&-16; // pad to 16 + if( enc._cpool.size()>0 ) + iadr = printConstantPool(iadr, sb, enc._cpool,enc._bigCons,true ,"Constant Pool"); - iadr = (iadr+15)&-16; // pad to 16 - if( enc._sdata.size()>0 ) - iadr = printConstantPool(iadr, sb,enc._sdata,enc._bigCons,false, "Static Data" ); + iadr = (iadr+15)&-16; // pad to 16 + if( enc._sdata.size()>0 ) + iadr = printConstantPool(iadr, sb,enc._sdata,enc._bigCons,false, "Static Data" ); + } return sb; } @@ -90,7 +93,7 @@ public abstract class ASMPrinter { } - private static int print(int iadr, SB sb, CodeGen code, Encoding enc, FunNode fun, int cfgidx) { + private static int print(int iadr, SB sb, CodeGen code, Encoding enc, Ary<CFGNode> cfg, FunNode fun, int cfgidx) { // Function header sb.nl().p("---"); if( fun._name != null ) sb.p(fun._name).p(" "); @@ -100,8 +103,8 @@ public abstract class ASMPrinter { if( fun._frameAdjust != 0 ) iadr = doInst(iadr,sb,code,enc, cfgidx,fun,true,enc!=null); - while( !(enc._cfg.at(cfgidx) instanceof ReturnNode) ) - iadr = doBlock(iadr,sb,code,enc,fun,cfgidx++); + while( !(cfg.at(cfgidx) instanceof ReturnNode) ) + iadr = doBlock(iadr,sb,code,enc,cfg,fun,cfgidx++); // Function separator sb.p("---"); @@ -112,9 +115,9 @@ public abstract class ASMPrinter { static private final int opWidth = 5; static private final int argWidth = 30; - static int doBlock(int iadr, SB sb, CodeGen code, Encoding enc, FunNode fun, int cfgidx) { + static int doBlock(int iadr, SB sb, CodeGen code, Encoding enc, Ary<CFGNode> cfg, FunNode fun, int cfgidx) { final int encWidth = code._mach==null ? 2 : code._mach.defaultOpSize()*2; - CFGNode bb = enc._cfg.at(cfgidx); + CFGNode bb = cfg.at(cfgidx); if( bb != fun && !(bb instanceof IfNode) && !(bb instanceof CallEndNode) && !(bb instanceof CallNode) && !(bb instanceof CProjNode && bb.in(0) instanceof CallEndNode )) sb.p(label(bb)).p(":").nl(); if( bb instanceof CallNode ) return iadr; @@ -167,8 +170,9 @@ public abstract class ASMPrinter { // need to assume a jump. There's no real hardware op here, yet. if( n instanceof RegionNode cfg && !(n instanceof FunNode) ) { if( postEncode ) return iadr; // All jumps inserted already - while( cfgidx < enc._cfg._len-1 ) { - CFGNode next = enc._cfg.at(++cfgidx); + Ary<CFGNode> blocks = enc == null ? code._cfg : enc._cfg; + while( cfgidx < blocks._len-1 ) { + CFGNode next = blocks.at(++cfgidx); if( next == n ) return iadr; // Fall-through, no branch if( next.nOuts()>1 ) break; // Has code in the block, need to jump around @@ -243,7 +247,7 @@ public abstract class ASMPrinter { sb.nl(); // Printing more op bits than fit - if( isMultiOp != null ) { + if( isMultiOp != null && enc != null ) { // Multiple ops, template style, no RA, no scheduling. Print out // one-line-per-newline, with encoding bits up front. int size = enc != null ? enc.opLen(n) : 0; @@ -267,6 +271,9 @@ public abstract class ASMPrinter { } + } else if( isMultiOp != null ) { + sb.p(isMultiOp).nl(); + } else if( fatEncoding > 0 ) { // Extra bytes past the default encoding width, all put on a line by // themselves. X86 special for super long encodings diff --git a/chapter25/src/main/java/com/seaofnodes/simple/print/IRPrinter.java b/chapter25/src/main/java/com/seaofnodes/simple/print/IRPrinter.java index 7c0f84f3..8b1c1e2f 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/print/IRPrinter.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/print/IRPrinter.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.print; import com.seaofnodes.simple.codegen.CodeGen; -import com.seaofnodes.simple.codegen.Serialize; +import com.seaofnodes.simple.codegen.CompUnit; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.SB; @@ -37,30 +37,133 @@ public abstract class IRPrinter { // Bulk whole program pretty print public static String prettyPrint( CodeGen code ) { - // Loop-tree for nodeOrder - CFGNode.LoopTree old = code._start._ltree; - if( old==null ) - code._start.buildLoopTree( code._linker, code._stop); - Ary<Node> nodes = Serialize.nodeOrder(code); - if( old == null ) - code._start._ltree = null; SB sb = new SB(); - Node prior=null; - for( Node n : nodes ) { - if( n instanceof FunNode fun ) { - sb.nl().p("--- "); - fun.sig().print(sb.p(fun._name==null ? "" : fun._name).p(" ")); - sb.p("----------------------\n"); - } - if( n instanceof MultiNode || n instanceof RegionNode || n instanceof CallNode || + printLine(code._start,sb); + + // Constants are shared program-wide. Print only actual Start children + // here; derived values belong to the functions which use them. + ArrayList<Node> globals = new ArrayList<>(); + for( Node n : code._start._outputs ) + if( n instanceof ConstantNode ) globals.add(n); + globals.sort(Comparator.comparingInt(n -> n._nid)); + for( Node n : globals ) printLine(n,sb); + + ArrayList<CompUnit> cus = new ArrayList<>(code._compunits.values()); + cus.sort(Comparator.comparing(cu -> cu._cname==null ? "" : cu._cname)); + for( CompUnit cu : cus ) { + if( cu._start==null || cu._start._inputs==null ) continue; + sb.nl().p("=== ").p(cu._cname==null ? "" : cu._cname).p(" ===\n"); + printLine(cu._start,sb); + ArrayList<Node> projs = projections(cu._start); + for( Node proj : projs ) printLine(proj,sb); + + ArrayList<FunNode> funs = new ArrayList<>(); + for( FunNode fun : code._linker ) + if( fun!=null && fun._inputs!=null && fun._compunit==cu ) + funs.add(fun); + funs.sort(Comparator.comparingInt(n -> n._nid)); + for( FunNode fun : funs ) printFunction(fun,sb); + + printLine(cu._stop,sb); + } + printLine(code._stop,sb); + return sb.toString(); + } + + /** Print one function without ever traversing a call-graph linkage. */ + private static void printFunction(FunNode fun, SB sb) { + sb.nl().p("--- "); + fun.sig().print(sb.p(fun._name==null ? "" : fun._name).p(" ")); + sb.p("----------------------\n"); + + ArrayList<Node> post = new ArrayList<>(); + IdentityHashMap<Node,Boolean> visit = new IdentityHashMap<>(); + functionPost(fun,fun,visit,post); + Collections.reverse(post); + + Node prior = null; + IdentityHashMap<Node,Boolean> emitted = new IdentityHashMap<>(); + for( Node n : post ) { + if( emitted.containsKey(n) ) continue; + if( n instanceof RegionNode || n instanceof MultiNode || n instanceof CallNode || (isMultiChild(prior) && !isMultiChild(n)) ) sb.nl(); + // A Region/Loop and its Phis are one block header. In particular, + // do not pull loop-carried Phi inputs up between the header and + // the Phi; those values belong down in the loop body/backedge. + if( !isMultiChild(n) ) + emitLocalDefs(n,visit,emitted,sb); printLine(n,sb); - if( n instanceof ReturnNode ret ) - sb.p("--- ").p(ret._fun._name==null ? "" : ret._fun._name).p(" ----------------------\n"); + emitted.put(n,Boolean.TRUE); prior = n; } - return sb.toString(); + sb.p("--- ").p(fun._name==null ? "" : fun._name).p(" ----------------------\n"); + } + + private static void emitLocalDefs(Node n, + IdentityHashMap<Node,Boolean> owned, + IdentityHashMap<Node,Boolean> emitted, + SB sb) { + if( n._inputs==null ) return; + for( Node def : n._inputs ) { + if( def==null || def instanceof CFGNode || def instanceof ConstantNode || + def instanceof PhiNode || isMultiChild(def) || + !owned.containsKey(def) || emitted.containsKey(def) ) + continue; + emitLocalDefs(def,owned,emitted,sb); + printLine(def,sb); + emitted.put(def,Boolean.TRUE); + } + } + + // Printer-private RPO. This deliberately uses raw edge arrays and local + // identity state: no Node visit bits, cached idoms, or loop-tree metadata. + private static void functionPost(Node n, FunNode owner, + IdentityHashMap<Node,Boolean> visit, + ArrayList<Node> post) { + if( n==null || n._inputs==null || visit.put(n,Boolean.TRUE)!=null ) return; + if( n instanceof FunNode fun && fun!=owner ) return; // Linked callee + if( n instanceof ParmNode && + input0(n)!=owner ) return; // Callee parameter + if( n instanceof StopCUNode || n instanceof StopNode || n instanceof StartCUNode ) return; + if( n instanceof CallEndNode && input0(n) instanceof CallNode call && + !visit.containsKey(call) ) return; // Foreign caller + + ArrayList<Node> uses = new ArrayList<>(); + // A Return is terminal inside its function. All of its graph users + // are ownership/linkage hooks (StopCU, CallEnds, FunPtrs), never CFG + // continuation in the function being printed. + if( !(n instanceof ReturnNode) ) for( Node use : n._outputs ) { + if( use==null || use._inputs==null ) continue; + if( n instanceof CallNode && use instanceof FunNode ) continue; + if( use instanceof FunNode fun && fun!=owner ) continue; + if( use instanceof ParmNode && + input0(use)!=owner ) continue; + uses.add(use); + } + // CFG first produces an RPO-like block order. Stable nid ordering + // keeps malformed/multiply-connected graphs deterministic. + uses.sort(Comparator + .comparingInt((Node use) -> use instanceof CFGNode ? 0 : 1) + .thenComparingInt(use -> use._nid)); + for( Node use : uses ) functionPost(use,owner,visit,post); + + // Keep a multi-head and its projections contiguous. + if( isMultiChild(n) ) return; + if( isMultiHead(n) ) { + ArrayList<Node> ps = projections(n); + for( Node p : ps ) visit.put(p,Boolean.TRUE); + for( int i=ps.size()-1; i>=0; i-- ) post.add(ps.get(i)); + } + post.add(n); + } + + private static ArrayList<Node> projections(Node multi) { + ArrayList<Node> ps = new ArrayList<>(); + for( Node use : multi._outputs ) + if( use!=null && use._inputs!=null && isMultiChild(use) ) ps.add(use); + ps.sort(Comparator.comparingInt(IRPrinter::sortOrder)); + return ps; } private static boolean isMultiHead(Node n) { @@ -68,7 +171,19 @@ public abstract class IRPrinter { } private static boolean isMultiChild(Node n) { - return n!=null && n.nIns() > 0 && n.in(0) != null && isMultiHead(n.in(0)); + Node head = input0(n); + // Regions group their Phis, and tuple-producing MultiNodes group their + // projections. Merely being controlled by a Region/Loop does not + // make an ordinary CFG node a grouped child. + return (n instanceof PhiNode && head instanceof RegionNode) || + (n instanceof Proj && head instanceof MultiNode); + } + + // Raw, bounds-safe graph inspection for the debugger. In particular do + // not call an accessor which might assert, sharpen, cache, or lazily kill. + private static Node input0(Node n) { + return n==null || n._inputs==null || n._inputs.isEmpty() + ? null : n._inputs.at(0); } @@ -163,7 +278,7 @@ public abstract class IRPrinter { } static int sortOrder( Node n ) { - if( n instanceof ProjNode proj ) return proj._idx; + if( n instanceof Proj proj ) return proj.idx(); if( n instanceof PhiNode phi ) return phi._nid; if( n == null ) return 0; return n._nid+1000000; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/Field.java b/chapter25/src/main/java/com/seaofnodes/simple/type/Field.java index b6ea5843..ed505b19 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/Field.java @@ -98,8 +98,6 @@ public class Field extends Type { @Override boolean _isConstant() { return _t._isConstant(); } @Override boolean _isFinal() { return _final && _t._isFinal(); } @Override Field _makeRO() { return _final ? this : make(_fname, _t._makeRO(),_alias,true); } - @Override boolean _isGLB(boolean mem) { return _t._isGLB(true); } - @Override public Type _glb(boolean mem) { return make(_fname,_t._glb(true),_alias,true); } @Override Field _close( String name, HashMap<String, Type> TYPES ) { return makeFrom( _t._close(name, TYPES )); } @Override Type _upgradeType(HashMap<String,Type> TYPES) { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter25/src/main/java/com/seaofnodes/simple/type/Type.java index fd3a7c59..509326bb 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/Type.java @@ -480,28 +480,11 @@ public class Type /*implements Cloneable*/ { } Type _makeRO() { return this; } - // Compute greatest lower bound in the lattice. If values are in memory, - // ints and floats cannot widen. - public final boolean isGLB(boolean mem) { return recurClose(recurOpen()._isGLB(mem)); }; - boolean _isGLB(boolean mem) { - return switch(_type) { - case TBOT -> false; - case TSCALAR -> this==TypeScalar.BOT; - case TNIL -> false; - case TCTRL -> true; - case TXCTRL -> false; - case TXNIL -> false; - case TTOP -> false; - default -> throw Utils.TODO(); - }; - } - public final Type glb(boolean mem) { - if( isGLB(mem) ) return this; - Type glb = recurOpen()._glb(mem).recurClose(); - assert this.isa(glb); - return glb; + /** Declared shape used when a value is published into mutable memory. */ + public final Type makeStorage() { + return recurOpen()._makeStorage().recurClose(); } - Type _glb(boolean mem) { assert is_simple(); return Type.BOTTOM; } + Type _makeStorage() { assert is_simple(); return BOTTOM; } // Bulk close-over all recursive types public static TypeStruct[] closeOver(TypeStruct[] ts, HashMap<String,Type> TYPES) { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeConAry.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeConAry.java index 26fa4a67..2a0a817e 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeConAry.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeConAry.java @@ -48,8 +48,7 @@ public abstract class TypeConAry<A> extends TypeScalar { @Override public boolean isHigh() { return this==TOP; } @Override boolean _isConstant() { return true; } - @Override Type _glb(boolean mem) { return this; } - @Override boolean _isGLB(boolean mem) { return true; } + @Override Type _makeStorage() { return this; } // Meet-over-elements type public Type elem() { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeFloat.java index f4968f28..1325b707 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeFloat.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeFloat.java @@ -90,15 +90,13 @@ public class TypeFloat extends TypeScalar { return _isConstant() ? this : new TypeFloat((byte)-_sz,0); // Constants are a self-dual } - @Override boolean _isGLB(boolean mem) { return _glb(mem)==this; } - @Override Type _glb(boolean mem) { - if( !mem ) return F64; + @Override boolean _isConstant() { return _sz==0; } + + @Override Type _makeStorage() { if( _isConstant() ) return isF32() ? F32 : F64; return isHigh() ? dual() : this; } - @Override boolean _isConstant() { return _sz==0; } - @Override public Type makeZero() { return FZERO; } // Reserve tags for F64,F32,constant diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java index e2ec6263..d18ebd9c 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java @@ -68,7 +68,7 @@ public class TypeFunPtr extends TypeNil { @Override TypeFunPtr makeFrom( byte nil ) { return nil ==_nil ? this : make( nil,_open,_sig,_ret, _fidxs); } public TypeFunPtr makeFrom( Type ret ) { return ret ==_ret ? this : make( _nil,_open,_sig, ret, _fidxs); } - public TypeFunPtr makeFrom( int fidx ) { return make1((byte)2,_open,_sig,_ret,fidx); } + public TypeFunPtr makeFrom( int fidx ) { return make1(_nil,_open,_sig,_ret,fidx); } public TypeFunPtr makeFrom( Type arg, int idx ) { // Alter named arg Type[] sig = _sig.clone(); @@ -159,8 +159,7 @@ public class TypeFunPtr extends TypeNil { @Override boolean _isConstant() { return (_nil==2 && XInt.isConstant(_fidxs)) || (_nil==3 && _fidxs== XInt.EMPTY); } @Override boolean _isFinal() { return true; } - @Override boolean _isGLB(boolean mem) { return true; } - @Override TypeFunPtr _glb(boolean mem) { return this; } + @Override TypeFunPtr _makeStorage() { return this; } @Override TypeFunPtr _close( String name, HashMap<String, Type> TYPES ) { Type[] sig = new Type[_sig.length]; @@ -213,7 +212,7 @@ public class TypeFunPtr extends TypeNil { @Override int TAGOFF() { return 8; } @Override public void packed( BAOS baos, HashMap<String,Integer> strs ) { assert _open; // Open: Passing extra args is fine, and extras ignored. - if( _nil==2 && nargs()<6 && nfcns() == 1 ) { + if( _nil==2 && nargs()<6 && nfcns() == 1 && fidx() < 64 ) { baos.write(TAGOFFS[_type] + nargs()); baos.packed2(fidx()); } else { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 25c3fa6f..c981f3d3 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -170,14 +170,10 @@ public class TypeInteger extends TypeScalar { } @Override public Type makeZero() { return ZERO; } @Override boolean _isConstant() { return _min == _max; } - @Override boolean _isGLB(boolean mem) { return _glb(mem)==this; } - @Override Type _glb(boolean mem) { - if( !mem ) return BOT; - // GLB is not well-defined in memory; depends on the size of the memory field + @Override Type _makeStorage() { if( _isConstant() ) return BOT; return isHigh() ? dual() : this; } - // Reserve tags for I64,I32,U32,0,constant,generic @Override int TAGOFF() { return 7; } @Override public void packed( BAOS baos, HashMap<String,Integer> strs ) { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeMem.java index 3bbdf1df..7658e3fd 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -123,10 +123,10 @@ public class TypeMem extends Type { int[] fidxs = XInt.meet( _escFs, that._escFs ); int[] aliases= XInt.meet( _escAs, that._escAs ); // Singleton & class facts are kept only when both sides agree. - + // Final is kept if either side is final, merging a final & non-final // memory can be argued either way here: - + // - Keep it: merging a final & non-final memory means a later Store // update will be flagged as an error. // - Lose it: merging a final & non-final memory means a later Load @@ -152,8 +152,7 @@ public class TypeMem extends Type { @Override boolean _isConstant() { return _one && _clz && _alias!= 1 && _t._isConstant(); } @Override public int log_size() { throw Utils.TODO(); } @Override boolean _isFinal() { return _t._isFinal(); } - @Override boolean _isGLB(boolean mem) { return _t._isGLB(true); } - @Override public Type _glb(boolean mem) { return make(_alias,_t._glb(true),_one,_clz,_final,_escFs,_escAs); } + @Override TypeMem _makeStorage() { return make(_alias,_t._makeStorage(),_one,_clz,_final,_escFs,_escAs); } @Override TypeMem _close( String name, HashMap<String, Type> TYPES ) { return malloc(_alias,_t._close(name, TYPES ),_one,_clz,_final,_escFs,_escAs); } @@ -230,7 +229,7 @@ public class TypeMem extends Type { private static int[] escapeFIDX( int[] xs, Type t ) { return switch(t) { case TypeMemPtr tmp -> escapeFIDX(xs,tmp._obj); - case TypeStruct ts -> ts._open + case TypeStruct ts -> ts._open && !ts.isAry() ? XInt.FULL // Open structs can have any fields : XInt.meet(xs,ts.fidxs()); case TypeFunPtr tfp -> XInt.meet(xs,tfp.fidxs()); @@ -242,7 +241,7 @@ public class TypeMem extends Type { private static int[] escapeAlias( int[] xs, Type t ) { return switch(t) { case TypeMemPtr tmp -> escapeAlias(xs,tmp._obj); - case TypeStruct ts -> ts._open + case TypeStruct ts -> ts._open && !ts.isAry() ? XInt.FULL // Open structs can have any fields : XInt.meet(xs,ts.aliases()); case TypeMem mem -> XInt.meet(xs,mem._escAs); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index 67d80591..5a2693c9 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -68,6 +68,10 @@ public class TypeMemPtr extends TypeNil { public TypeMemPtr makeFrom(TypeStruct obj) { return obj==_obj ? this : make(_nil, obj, _one, _pub); } public TypeMemPtr makeNullable() { return makeFrom((byte)3); } + /** Inferred mutable local: nullable, public and non-singleton. */ + public TypeMemPtr makeVar() { return (TypeMemPtr)makeStorage(); } + /** Public-memory shape: nullable and non-singleton, preserving the referent. */ + @Override TypeMemPtr _makeStorage() { return make((byte)3,_obj._makeStorage(),false,true); } @Override TypeMemPtr makeFrom(byte nil) { return nil==_nil ? this : make(nil, _obj, _one, _pub); } public TypeMemPtr makeHigh(byte nil) { return make(nil,_obj.makeHigh(),false); } @Override public Type nonZero() { return makeFrom((byte)(_nil <= 1 ? 1 : 2)); } @@ -109,8 +113,6 @@ public class TypeMemPtr extends TypeNil { @Override boolean _isConstant() { return _one; } @Override boolean _isFinal() { return _obj._isFinal(); } @Override TypeMemPtr _makeRO() { return makeFrom(_obj._makeRO()); } - @Override boolean _isGLB(boolean mem) { return _obj._isGLB(true); } - @Override TypeMemPtr _glb(boolean mem) { return make((byte)3,_obj.glb2()); } @Override TypeMemPtr _close( String name, HashMap<String, Type> TYPES ) { return malloc(_nil,_obj._close(name, TYPES ),_one,_pub); } @Override Type _upgradeType(HashMap<String,Type> TYPES) { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeNil.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeNil.java index 32505aa2..2c1c1d76 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeNil.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeNil.java @@ -51,7 +51,6 @@ public abstract class TypeNil extends TypeScalar { public boolean nullable() { return _nil==3; } @Override boolean _isConstant() { return false; } - @Override Type _glb(boolean mem) { return Type.NIL; } final String q() { return _nil == 1 || _nil == 2 ? "" : "?"; } final String x() { return isHigh() ? "~" : ""; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypePtr.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypePtr.java index 3ff9765b..7b27ff2b 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypePtr.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypePtr.java @@ -50,8 +50,8 @@ public class TypePtr extends TypeNil { // 0->xscalar, 1->nscalar, 2->nscalar, 3->scalar @Override Type meetX() { return _nil==0 ? XNIL : (_nil==3 ? PTR : NPTR); } - boolean _isGLB(boolean mem) { return this==PTR; } - @Override TypePtr _glb(boolean mem) { return PTR; } + @Override TypePtr _makeStorage() { return PTR; } + // Reserve 2 tags, PTR and NPTR @Override int TAGOFF() { return 2; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeRPC.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeRPC.java index a39ebc04..8a12f50a 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeRPC.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeRPC.java @@ -73,7 +73,7 @@ public class TypeRPC extends Type { } @Override boolean _isConstant() { return XInt.isConstant(_rpcs); } - @Override boolean _isGLB(boolean mem) { return true; } + @Override TypeRPC _makeStorage() { return this; } // Reserve tags for ALL, singleton, generic @Override int TAGOFF() { return 3; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeScalar.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeScalar.java index 7b5d6317..eaba0a1c 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeScalar.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeScalar.java @@ -38,8 +38,7 @@ public class TypeScalar extends Type { @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 Type _makeStorage() { return BOT; } // Reserve tags for both lattice endpoints. Unlike most concrete scalar // families, generic scalar TOP can survive into a serialized graph. diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index f51ab859..2949b015 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -463,18 +463,8 @@ public class TypeStruct extends Type { return recurTransform(_name,_name,_open,_fref,true,Type::_makeRO); } - // Keeps the same struct, but lower-bounds all fields. - public TypeStruct glb2() { - return recurTransform(_uid,_name,_open,false,false,t -> t._glb(true)); - } - - @Override boolean _isGLB(boolean mem) { - if( VISIT.containsKey(_uid) ) return true; // Cycles assume GLB - VISIT.put(_uid,this); - for( Field f : _fields ) - if( !f._t._isGLB(mem) ) - return false; - return true; + @Override TypeStruct _makeStorage() { + return recurTransform(_uid,_name,_open,false,false,Type::_makeStorage); } // log_size for a struct is not defined, unless its exactly some power of @@ -569,7 +559,12 @@ public class TypeStruct extends Type { if( isAry() && field("[]")._t instanceof TypeConAry con ) return sb.p(con.str()); sb.p(_name); - if( html || isAry() ) + if( isAry() ) + // Array names deliberately canonicalize mutable and immutable + // element variants. The verbose debugger print must retain the + // otherwise invisible lattice coordinate. + return sb.p(_fields[1]._final ? "[final]" : "[mutable]"); + if( html ) return sb; sb.p(" {"); for( Field f : _fields ) |