From 300d2a9c3672acacc8bdd8d5370a424651a00571 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 18 Oct 2026 22:09:58 -0700 Subject: Cleanup & backport The phase rework, made new phases explicit and add them to the CodeGen driver. Fix the flag-spilling on X86 and ARM. Fix the GCM conservative anti-deps and backport. --- .../main/java/com/seaofnodes/simple/Parser.java | 3 +- .../com/seaofnodes/simple/codegen/CodeGen.java | 604 ++++----------------- .../com/seaofnodes/simple/codegen/ElfWriter.java | 2 + .../com/seaofnodes/simple/codegen/FinalizeIR.java | 44 ++ .../simple/codegen/GlobalCodeMotion.java | 60 +- .../com/seaofnodes/simple/codegen/InstSelect.java | 126 +++++ .../java/com/seaofnodes/simple/codegen/Iter.java | 60 ++ .../java/com/seaofnodes/simple/codegen/LRG.java | 2 + .../java/com/seaofnodes/simple/codegen/Opto.java | 6 +- .../com/seaofnodes/simple/codegen/ParseAll.java | 12 + .../com/seaofnodes/simple/codegen/RegAlloc.java | 6 +- .../com/seaofnodes/simple/codegen/Serialize.java | 52 +- .../com/seaofnodes/simple/codegen/StaticData.java | 18 - .../com/seaofnodes/simple/codegen/TypeCheck.java | 57 ++ .../java/com/seaofnodes/simple/codegen/Unlink.java | 112 ++++ .../com/seaofnodes/simple/node/BulkMemPhiNode.java | 14 +- .../com/seaofnodes/simple/node/CLInitNode.java | 60 +- .../com/seaofnodes/simple/node/CallEndNode.java | 6 +- .../java/com/seaofnodes/simple/node/CallNode.java | 3 + .../com/seaofnodes/simple/node/ConstantNode.java | 4 +- .../java/com/seaofnodes/simple/node/FunNode.java | 5 +- .../java/com/seaofnodes/simple/node/MemOpNode.java | 27 +- .../java/com/seaofnodes/simple/node/ParmNode.java | 3 +- .../java/com/seaofnodes/simple/node/SplitNode.java | 2 + .../java/com/seaofnodes/simple/node/StartNode.java | 4 +- .../com/seaofnodes/simple/node/StopCUNode.java | 4 +- .../java/com/seaofnodes/simple/node/StopNode.java | 3 +- .../java/com/seaofnodes/simple/node/StoreNode.java | 11 +- .../simple/node/cpus/arm/SplitFlagsARM.java | 21 + .../simple/node/cpus/arm/SplitGPRARM.java | 11 + .../com/seaofnodes/simple/node/cpus/arm/arm.java | 11 +- .../simple/node/cpus/x86_64_v2/SplitFlagsX86.java | 25 + .../simple/node/cpus/x86_64_v2/SplitX86.java | 6 +- .../simple/node/cpus/x86_64_v2/x86_64_v2.java | 6 +- .../simple/print/SimpleGraphObserver.java | 2 +- 35 files changed, 768 insertions(+), 624 deletions(-) create mode 100644 chapter25/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java create mode 100644 chapter25/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java create mode 100644 chapter25/src/main/java/com/seaofnodes/simple/codegen/Iter.java create mode 100644 chapter25/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java create mode 100644 chapter25/src/main/java/com/seaofnodes/simple/codegen/Unlink.java create mode 100644 chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/SplitFlagsARM.java create mode 100644 chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/SplitGPRARM.java create mode 100644 chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SplitFlagsX86.java (limited to 'chapter25/src/main') diff --git a/chapter25/src/main/java/com/seaofnodes/simple/Parser.java b/chapter25/src/main/java/com/seaofnodes/simple/Parser.java index eca2b9ce..5ceda6a9 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/Parser.java @@ -291,8 +291,7 @@ public class Parser { } // The initializer owns its run-once flag store. Parent initialization - // is a structural requirement, to be executed before this body when - // CLInit runtime lowering is added. + // is a structural requirement, executed before this body by CLInit lowering. if( fun.isClz() ) { Node self = fun.parm(2); Field flag = ((TypeMemPtr)self._type)._obj.field("$init"); 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 3909f881..47ec0112 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -8,9 +8,6 @@ import com.seaofnodes.simple.print.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.*; import java.io.File; -import java.io.IOException; -import java.nio.file.Files; -import java.nio.file.Path; import java.util.*; @@ -32,8 +29,9 @@ public class CodeGen { IterPostOpto, // Peepholes and inlining using SCCP results FinalizeIR, // Field layout, offset cleanup, function/CU roots TypeCheck, // Last check for bad programs + Serialize, // Save ideal IR, including opaque class initialization + Lower, // Expand checked class initialization to ordinary IR LoopTree, // Build a loop tree; break infinite loops - Serialize, // Serialize public IR for future compiles to link Unlink, // Unlink call sites before machine code generation Select, // Convert to target hardware nodes Schedule, // Global schedule (code motion) nodes @@ -185,7 +183,7 @@ public class CodeGen { public final XCtrlNode XCTRL; public Node constant( Type t ) { - assert _phase==null || _phase.ordinal() <= Phase.FinalizeIR.ordinal(); + assert _phase==null || _phase.ordinal() <= Phase.Lower.ordinal(); return ConstantNode.make(t).peephole(); } public ConstantNode con( Type t ) { return (ConstantNode)constant(t); } @@ -239,7 +237,9 @@ public class CodeGen { } - // Run requested phases. + // Run requested phases. File export must request Serialize before Lower; + // requesting Export up front does that automatically. Encoding alone does + // not retain reloadable ideal IR. // No code emission, just IR generation public CodeGen driver( Phase phase ) { return driver(phase,null,null,false,false,0); } @@ -256,25 +256,64 @@ public class CodeGen { // Write an object file for a specific cpu/os pair public CodeGen driver( String cpu, String callingConv, boolean inMemory, boolean emitEntrySymbol ) { return driver(Phase.Export,cpu,callingConv,inMemory,emitEntrySymbol,0); } - // Generic driver - public CodeGen driver( Phase phase, String cpu, String callingConv, boolean inMemory, boolean emitEntrySymbol, int dump ) { - int p1 = phase.ordinal(), p2 = _phase==null ? -1 : _phase.ordinal(); - if( p2 < p1 && p2 < Phase.Parse .ordinal() ) { parse(); p2 = dump(dump); } - if( p2 < p1 && p2 < Phase.Iter .ordinal() ) { iter(); p2 = dump(dump); } - if( p2 < p1 && p2 < Phase.Opto .ordinal() ) { opto(); p2 = dump(dump); } - if( p2 < p1 && p2 < Phase.IterPostOpto.ordinal() ) { iterPostOpto(); p2 = dump(dump); } - if( p2 < p1 && p2 < Phase.FinalizeIR.ordinal() ) { finalizeIR(); p2 = dump(dump); } - if( p2 < p1 && p2 < Phase.TypeCheck .ordinal() ) { typeCheck(); p2 = dump(dump); } - if( p2 < p1 && p2 < Phase.LoopTree .ordinal() ) { loopTree(); p2 = dump(dump); } - if( p2 < p1 && p1 >= Phase.Encoding .ordinal() ) { unlinkImports(); p2 = dump(dump); } - if( p2 < p1 && p1 >= Phase.Encoding .ordinal() ) { serialize(); p2 = dump(dump); } // Include ideal graph in object file - if( p2 < p1 && p2 < Phase.Unlink .ordinal() ) { unlink(); p2 = dump(dump); } - if( p2 < p1 && p2 < Phase.Select .ordinal() && cpu != null ) { instSelect(cpu,callingConv); p2 = dump(dump); } - if( p2 < p1 && p2 < Phase.Schedule .ordinal() ) { GCM(); p2 = dump(dump); } - if( p2 < p1 && p2 < Phase.LocalSched.ordinal() ) { localSched();p2 = dump(dump); } - if( p2 < p1 && p2 < Phase.RegAlloc .ordinal() ) { regAlloc(); p2 = dump(dump); } - if( p2 < p1 && p2 < Phase.Encoding .ordinal() ) { encode(); p2 = dump(dump); } - if( p2 < p1 && p2 < Phase.Export .ordinal() ) { exportELF(inMemory,emitEntrySymbol); p2 = dump(dump); } + + // The Generic driver + public CodeGen driver( Phase target, String cpu, String callingConv, boolean inMemory, boolean emitEntrySymbol, int dump ) { + // Parse a Simple file, and for mentioned external symbols either load + // from .o or recursively parse + step(target, Phase.Parse, this::parse, dump); + // Run peepholes to a fixed point + step(target, Phase.Iter, this::iter, dump); + // Run SCCP (and resolve int/flt expressions) + step(target, Phase.Opto, this::opto, dump); + // Run peepholes to a fixed point again, on the better types. + step(target, Phase.IterPostOpto, this::iterPostOpto, dump); + // Field layouts; field symbols become constant offsets + step(target, Phase.FinalizeIR, this::finalizeIR, dump); + // Final error check - bad programs fail here + step(target, Phase.TypeCheck, this::typeCheck, dump); + // Save reloadable ideal IR for a later seperate compilation + step(target, Phase.Serialize, () -> Serialize.forTarget(this,target,inMemory), dump); + // Replace "fat" nodes with their exploded explicit IR; this can + // introduce CFG diamonds + step(target, Phase.Lower, this::lower, dump); + // Compute the loop-tree, used for approximating exec frequencies for + // scheduling and register allocation + step(target, Phase.LoopTree, this::loopTree, dump); + // Drop imports for machine selection, retain them for ideal evaluation. + step(target, Phase.Unlink, () -> unlink(cpu!=null), dump); + // Instruction selection + step(target, Phase.Select, () -> instSelect(cpu,callingConv), dump); + // Global Code Motion + step(target, Phase.Schedule, this::GCM, dump); + // Local (basic block only) scheduling + step(target, Phase.LocalSched, this::localSched, dump); + // Register allocation + step(target, Phase.RegAlloc, this::regAlloc, dump); + // Encode machine instructions into bits + step(target, Phase.Encoding, this::encode, dump); + // Export bits (and serialized IR) into ELF files + step(target, Phase.Export, () -> exportELF(inMemory,emitEntrySymbol), dump); + return this; + } + + // The driver names the order; optional phases decide locally whether to run. + private void step(Phase target, Phase next, Runnable work, int dump) { + if( next.ordinal() > target.ordinal() || (_phase!=null && _phase.ordinal()>=next.ordinal()) ) return; + Phase prior = _phase; + work.run(); + if( _phase!=prior ) dump(dump); + } + + // All phase entry points share ordering checks, timing, and viewer notification. + // Record elapsed time even on failure, but report completion only on success. + CodeGen phase(Phase next, boolean ordered, Runnable work) { + assert ordered : "Cannot run "+next+" after "+_phase; + _phase = next; + long t0 = System.currentTimeMillis(); + work.run(); // Do The Phase + _times[next.ordinal()] = System.currentTimeMillis() - t0; + if( _obs!=null ) _obs.phase(next.name()); // Record for viewer return this; } @@ -283,17 +322,14 @@ public class CodeGen { } // Verbose printing during compilation - private int dump(int dump) { + private void dump(int dump) { int p2 = _phase.ordinal(); - if( (dump & (1<= Phase.LocalSched.ordinal() ? asm(new SB()).toString() : IRPrinter.prettyPrint(this)); - return p2; } @@ -430,25 +466,7 @@ public class CodeGen { public final Parser P; // Parse ASCII text into Sea-of-Nodes IR - public CodeGen parse() { - assert _phase == null; - _phase = Phase.Parse; - long t0 = System.currentTimeMillis(); - - Parser.TYPES.clear(); - Parser.TYPES.putAll(Parser.INIT_TYPES); - if( _src != null ) { - // No source file, just the source itself. - ParseAll.parseSource(this,_srcName==null ? "Test" : _srcName,_src); - } else { - // Path from module root to source file - ParseAll.parsePath(this,_srcName); - } - - _times[Phase.Parse.ordinal()] = System.currentTimeMillis() - t0; - if( _obs != null ) _obs.phase(_phase.name()); - return this; - } + public CodeGen parse() { return phase(Phase.Parse, _phase==null, () -> ParseAll.parse(this,_src)); } // --------------------------- @@ -464,126 +482,14 @@ public class CodeGen { // Pessimistic peepholes after parsing. This lifts loaded and parsed // types before the optimistic Opto pass resets types and lets them fall. - public CodeGen iter() { - assert _phase == Phase.Parse; - _phase = Phase.Iter; - long t0 = System.currentTimeMillis(); - - // 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: 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 -> { - if( !(n instanceof ConstantNode) ) - n._type = hasImports ? iterImportReset(n._type) : iterEscapeReset(n._type); - add(n); - return null; - }); - _iter.iterate(this); - // Expensive assert. - assert !expensiveAssert() || Opto.fixedPointCheck(this); - - _times[Phase.Iter.ordinal()] = System.currentTimeMillis() - t0; - if( _obs != null ) _obs.phase(_phase.name()); - return this; - } - - private static Type iterEscapeReset(Type t) { - if( t instanceof TypeMem mem ) - return mem._one ? mem : mem.makeFrom(XInt.FULL,XInt.FULL); - if( t instanceof TypeTuple tt ) { - TypeTuple rez = tt; - for( int i=0; i Iter.run(this)); } // SCCP and numeric-mode resolution; leave cleanup work queued for Iter. - public CodeGen opto() { - assert _phase == Phase.Iter; - _phase = Phase.Opto; - long t0 = System.currentTimeMillis(); + public CodeGen opto() { return phase(Phase.Opto, _phase==Phase.Iter, () -> Opto.opto(this)); } - Opto.opto(this); - - _times[Phase.Opto.ordinal()] = System.currentTimeMillis() - t0; - if( _obs != null ) _obs.phase(_phase.name()); - return this; - } + public CodeGen iterPostOpto() { return phase(Phase.IterPostOpto, _phase==Phase.Opto, () -> _iter.iterate(this)); } - public CodeGen iterPostOpto() { - assert _phase == Phase.Opto; - _phase = Phase.IterPostOpto; - long t0 = System.currentTimeMillis(); - // Use SCCP types and the sharp call graph for peepholes and inlining. - _iter.iterate(this); - _times[Phase.IterPostOpto.ordinal()] = System.currentTimeMillis() - t0; - if( _obs != null ) _obs.phase(_phase.name()); - return this; - } - - public CodeGen finalizeIR() { - assert _phase == Phase.IterPostOpto; - _phase = Phase.FinalizeIR; - long t0 = System.currentTimeMillis(); - - // Freeze field sizes and replace symbolic field offsets by constants. - for( int i=0; i<_start.nOuts(); i++ ) { - Node use = _start.out(i); - if( use instanceof ConFldOffNode off ) { - Node con = off.asOffset(); - assert con != null : off._ts._name+"."+off._fname; - off.subsume(con); - i--; - } - } - _iter.iterate(this); // Propagate field offsets and clean up. - - // Retain surviving functions for emission without adding unknown callers. - for( FunNode fun : _linker ) - if( fun != null && !fun.isDead() && !fun._type.isHigh() ) - keepInCompUnit(fun); - for( CompUnit cu : _compunits.values() ) { - ProjNode mem = cu._start.proj(1); - if( mem != null ) mem.unkeep(); - } - // Stable print order: initializers first, then other Returns by NID. - for( Node stop : _stop._inputs ) - Arrays.sort(stop._inputs._es,0,stop.nIns(), - (x,y) -> ((((ReturnNode)x).fun().isClz() ? -1 : x._nid) - - (((ReturnNode)y).fun().isClz() ? -1 : y._nid) )); - - _times[Phase.FinalizeIR.ordinal()] = System.currentTimeMillis() - t0; - if( _obs != null ) _obs.phase(_phase.name()); - return this; - } + public CodeGen finalizeIR() { return phase(Phase.FinalizeIR, _phase==Phase.IterPostOpto, () -> FinalizeIR.run(this)); } // Root a surviving function without claiming that it has unknown callers. void keepInCompUnit(FunNode fun) { @@ -597,58 +503,7 @@ public class CodeGen { // --------------------------- // Last check for bad programs - public CodeGen typeCheck() { - assert _phase == Phase.FinalizeIR; - _phase = Phase.TypeCheck; - long t0 = System.currentTimeMillis(); - - // Check for class-init cycles first; such a cycle can prevent other - // things from resolving types. The dependency graph is temporary. - String clzInitCycle = new ClassInitDependencies(this).check(); - if( clzInitCycle != null ) - throw Parser.error(clzInitCycle,null); - - Ary errs = new Ary<>(Node.class); - _stop.walk( n -> { - if( n.err() != null ) - errs.add(n); - return null; - }); - _times[Phase.TypeCheck.ordinal()] = System.currentTimeMillis() - t0; - - if( !errs.isEmpty() ) { - // Prefer an originating error over a secondary error caused by a - // BOTTOM input. If all errors are downstream-poisoned, retain - // the old first-error behavior. - Node min = null; - for( Node n : errs ) - if( noBottomInputs(n) ) - { min = n; break; } - if( min==null ) - min = errs.at(0); - for( Node n : errs ) - if( n!=min && - noBottomInputs(n) && - ((n instanceof MemOpNode nmop && - min instanceof MemOpNode mmop && - nmop._loc.before(mmop._loc)) || - (n instanceof CFGNode ncfg && - min instanceof CFGNode mincfg && - ncfg.idepth() < mincfg.idepth())) ) - min = n; - if( _obs != null ) _obs.error(min, min.err().getMessage()); - throw min.err(); - } - if( _obs != null ) _obs.phase("TypeCheck"); - return this; - } - - private static boolean noBottomInputs(Node n) { - for( Node def : n._inputs ) - if( def!=null && !(def instanceof FldOffNode) && def._type==Type.BOTTOM ) - return false; - return true; - } + public CodeGen typeCheck() { return phase(Phase.TypeCheck, _phase==Phase.FinalizeIR, () -> TypeCheck.run(this)); } public static TypeStruct requiredStruct(Node n) { // CNC: remove? cleanup? @@ -658,63 +513,22 @@ public class CodeGen { return null; } + // --------------------------- + // TypeCheck queued surviving CLInits during its existing error walk. + public CodeGen lower() { + return phase(Phase.Lower, (_phase==Phase.TypeCheck || _phase==Phase.Serialize), () -> _iter.iterate(this)); + } + // --------------------------- // Build the loop tree; break never-exit loops public CodeGen loopTree() { - assert _phase.ordinal() <= Phase.Serialize.ordinal(); - _phase = Phase.LoopTree; - long t0 = System.currentTimeMillis(); - // Build the loop tree, fix never-exit loops - _start.buildLoopTree( _linker, _stop); - // Invariant theory: No more type or code changes after Opto. The - // LoopTree stuff is used to do layouts now, but not core opts. TODO: - // at some future date we'll do loop opts (e.g. peeling, unrolling) - // that will totally impact code shape, types and core opts - but this - // will be done in tandem with Opto changes. - //_iter.iterate(this); - _times[Phase.LoopTree.ordinal()] = System.currentTimeMillis() - t0; - return this; + return phase(Phase.LoopTree, _phase==Phase.Lower, () -> _start.buildLoopTree(_linker,_stop)); } // --------------------------- public BAOS _serial; public void serialize() { - assert _phase.ordinal() <= Phase.Serialize.ordinal(); - _phase = Phase.Serialize; - long t0 = System.currentTimeMillis(); - // Does not change compiler phase; just records IR - Serialize.serialize(this); - _times[Phase.Serialize.ordinal()] = System.currentTimeMillis() - t0; - } - - // Unlink imported function bodies before serialization. Calls to them - // remain as normal calls through their function pointer, and codegen later - // turns them into external relocations. - private void unlinkImports() { - assert _phase.ordinal() <= Phase.Serialize.ordinal(); - // Imported function constants keep their symbolic identity, not an - // embedded copy of the other object's Return and body. - for( Node n : _start._outputs.asAry() ) - if( n instanceof FunPtrNode ptr && ptr.ret()!=null && !owns(ptr.fun()) ) { - ptr.liftType(ptr._type); - ptr.setDef(1,null); - } - for( FunNode fun : _linker ) { - if( fun==null || fun.isDead() || owns(fun) ) - continue; - for( int i=1; i Serialize.serialize(this)); } // --------------------------- @@ -740,208 +554,15 @@ public class CodeGen { // Convert to target hardware nodes public CodeGen instSelect( String cpu, String callingConv ) { return instSelect(cpu,callingConv,PORTS); } public CodeGen instSelect( String cpu, String callingConv, String base ) { - assert _phase.ordinal() <= Phase.Unlink.ordinal(); - _phase = Phase.Select; - - _callingConv = callingConv; - - // Not timing the class load... - // Look for CPU in fixed named place: - // com.seaofnodes.simple.node.cpus."cpu"."cpu.class" - String clzFile = base+"."+cpu+"."+cpu; - try { _mach = ((Class) Class.forName( clzFile )).getDeclaredConstructor(new Class[]{CodeGen.class}).newInstance(this); } - catch( Exception e ) { throw new RuntimeException(e); } - - _cCallingConv = _mach.cCallingConv(callingConv); - - // Build global copies of common register masks. - long callerSave = _mach.callerSave(); - long cCallerSave= _mach.callerSave(_cCallingConv); - long neverSave = _mach. neverSave(); - int maxReg = Math.min(64,_mach.regs().length); - assert maxReg>=64 || (-1L << maxReg & callerSave)==0; // No stack slots in callerSave - assert maxReg>=64 || (-1L << maxReg & cCallerSave)==0; // No stack slots in cCallerSave - _callerSave = new RegMask(callerSave); - _cCallerSave= new RegMask(cCallerSave); - - // Build a Return RegMask array. All returns have the following inputs: - // 0 - ctrl - // 1 - memory - // 2 - varies with returning GPR,FPR - // 3 - RPC - // 4+- Caller save registers - _retMasks = new RegMask[(maxReg-_callerSave.size()-Long.bitCount( neverSave ))+4]; - for( int reg=0, i=4; reg(); - _instSelect( _stop, map ); - _stop = (StopNode)map.get(_stop ); - StartNode start = (StartNode)map.get(_start); - _start = start==null ? new StartNode(_start) : start; - _instOuts(_stop,visit()); - _visit.clear(); - - // Replace the CompUnit stop (and list of functions) - // with hardware-specific ones - for( CompUnit cu : _compunits.values() ) { - cu._start= (StartCUNode)map.get(cu._start); - cu._stop = (StopCUNode )map.get(cu._stop ); - } - - _times[Phase.Select.ordinal()] = System.currentTimeMillis() - t0; - return this; - } - - // Walk all ideal nodes, recursively mapping ideal to machine nodes, then - // make a machine node for "this". - private Node _instSelect( Node n, IdentityHashMap map ) { - if( n==null ) return null; - if( n instanceof StoreNode st && StaticData.preinitialized(this,st) ) - return _instSelect(st.mem(),map); - Node x = map.get(n); - if( x !=null ) return x; // Been there, done that - - // If n is a MachNode already, then its part of a multi-node expansion. - // It does not need instruction selection (already selected!) - // but it does need its inputs walked. - if( n instanceof MachNode ) { - for( int i=0; i < n.nIns(); i++ ) - n._inputs.set(i, _instSelect(n.in(i),map) ); - return n; - } - - // Produce a machine node from n; map it to flag as done so stops cycles. - if( n instanceof MemOpNode mem && mem.off() instanceof ExternOffsetNode off ) { - // External fields replace base+offset with symbol+0. Keep the ideal - // declaring type on the address for machine load/store width selection. - TypeMemPtr ptr = (TypeMemPtr)mem.ptr()._type; - n._inputs.set(2,new ExternNode(TypeMemPtr.make((byte)2,ptr._obj,true),off._extern)); - n._inputs.set(3,ConstantNode.raw(TypeInteger.ZERO)); - } - map.put(n, x=_mach.instSelect(n) ); - // Carry loop-tree and pre-order info across the ideal->mach transition - if( n instanceof CFGNode ncfg && x instanceof CFGNode xcfg ) { - xcfg._ltree = ncfg._ltree; - xcfg._pre = ncfg._pre; - } - // 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) ); - // Post selection action - if( x instanceof MachNode mach ) { - if( n instanceof ReturnNode ret ) - ((ReturnNode)mach)._fun = (FunNode)map.get(ret._fun); - mach.postSelect(this); // Post selection action - } - - return x; - } - - - // Walk all machine Nodes, and set their output edges - private void _instOuts( Node n, BitSet visit ) { - if( visit.get(n._nid) ) return; - visit.set(n._nid); - for( Node in : n._inputs ) - if( in!=null ) { - in._outputs.push(n); - // CallNode special: outputs are partially ordered; CallEnd in slot 0 - if( in instanceof CallNode call && n instanceof CallEndNode cend && call.out(0) != cend ) - call._outputs.swap(0,call.nOuts()-1); - _instOuts(in,visit); - } + return InstSelect.select(this,cpu,callingConv,base); } // --------------------------- public void unlink() { - assert _phase.ordinal() <= Phase.Select.ordinal(); - _phase = Phase.Unlink; - long t0 = System.currentTimeMillis(); - - // The remaining passes assume all calls are unlinked; i.e. we are throwing - // away the Call Graph here. Functions only reachable from internal calls - // need to be re-hooked to stop/start less they go dead. - for( FunNode fun : _linker ) { - // Already linked to start, not going dead - if( fun==null || fun.isDead() ) - continue; - - // Imported functions are not emitted by this object. Unlink any - // concrete calls so they become normal external relocations. - if( !owns(fun) ) { - while( fun.nIns() > 1 ) { - if( fun.in(1) instanceof CallNode call ) - call.unlink(fun,1); - else - fun.removeDeadPath(1); - } - StartCUNode start = fun._compunit._start; - StopCUNode stop = fun._compunit._stop; - // Unhook the Stop->Return edge also - ReturnNode ret = fun.ret(); - int idx = stop._inputs.find(ret); - if( idx != -1 ) { - stop._inputs.del(idx); - ret.delUse(stop); - } - // - if( stop.nIns()==0 ) { - idx = _stop._inputs.find(stop); - if( idx != -1 ) - _stop.delDef(idx); - if( start.nIns() > 0 && start.in(0) != null ) - start.setDef(0,null); - if( start.nIns() > 1 && start.in(1) != null ) - start.setDef(1,null); - } - continue; - } - - // Insert the post-Opto code-generation hook. Unlike an Opto-time - // Start input, this no longer carries unknown-caller semantics. - ReturnNode ret = fun.ret(); - StartNode start = fun._compunit._start; - assert start!=null; - if( fun.nIns() <= 1 || fun.in(1) != start ) { - fun.insertDef(1,start); - for( Node use : fun._outputs ) - if( use instanceof ParmNode parm ) - parm.insertDef(1,ConstantNode.raw(parm._type)); - if( fun._compunit._stop._inputs.find(ret) == -1 ) - fun._compunit._stop.addDef(ret); - } - // Unlink from Call - for( int i=2; i { - if( n instanceof CallEndNode cend ) - for( int i=1; i Unlink.run(this,removeImports)); } // --------------------------- @@ -950,39 +571,22 @@ public class CodeGen { // Global schedule (code motion) nodes public CodeGen GCM() { - assert _phase.ordinal() <= Phase.Select.ordinal(); - _phase = Phase.Schedule; - long t0 = System.currentTimeMillis(); - - GlobalCodeMotion.buildCFG(this); - _times[Phase.Schedule.ordinal()] = System.currentTimeMillis() - t0; - - return this; + return phase(Phase.Schedule, (_phase==Phase.Unlink || _phase==Phase.Select), () -> GlobalCodeMotion.buildCFG(this)); } // --------------------------- // Local (basic block) scheduler phase, a classic list scheduler - public CodeGen localSched() { - assert _phase == Phase.Schedule; - _phase = Phase.LocalSched; - long t0 = System.currentTimeMillis(); - ListScheduler.sched(this); - _times[Phase.LocalSched.ordinal()] = System.currentTimeMillis() - t0; - return this; - } + public CodeGen localSched() { return phase(Phase.LocalSched, _phase==Phase.Schedule, () -> ListScheduler.sched(this)); } // --------------------------- // Register Allocation public RegAlloc _regAlloc; public CodeGen regAlloc() { - assert _phase == Phase.LocalSched; - _phase = Phase.RegAlloc; - long t0 = System.currentTimeMillis(); - _regAlloc = new RegAlloc(this); - _regAlloc.regAlloc(); - _times[Phase.RegAlloc.ordinal()] = System.currentTimeMillis() - t0; - return this; + return phase(Phase.RegAlloc, _phase==Phase.LocalSched, () -> { + _regAlloc = new RegAlloc(this); + _regAlloc.regAlloc(); + }); } // Human-readable register name @@ -998,32 +602,16 @@ public class CodeGen { // --------------------------- // Encoding public Encoding _encoding; - public CodeGen encode() { - assert _phase == Phase.RegAlloc; - _phase = Phase.Encoding; - long t0 = System.currentTimeMillis(); - - _encoding = new Encoding(this).encode(); - - _times[Phase.Encoding.ordinal()] = System.currentTimeMillis() - t0; - return this; - } + public CodeGen encode() { return phase(Phase.Encoding, _phase==Phase.RegAlloc, () -> _encoding = new Encoding(this).encode()); } // --------------------------- // Exporting to external formats ElfWriter _elf; public CodeGen exportELF( boolean inMemory, boolean emitEntrySymbol ) { - assert _phase == Phase.Encoding; - _phase = Phase.Export; - long t0 = System.currentTimeMillis(); - if( _encoding!=null ) { - if( inMemory ) - new LinkMem(this).link(_encoding); // In memory patching - else - _elf = new ElfWriter(this).export(emitEntrySymbol); - } - _times[Phase.Export.ordinal()] = System.currentTimeMillis() - t0; - return this; + return phase(Phase.Export, _phase==Phase.Encoding, () -> { + if( inMemory ) new LinkMem(this).link(_encoding); + else _elf = new ElfWriter(this).export(emitEntrySymbol); + }); } 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 1b6281b8..b3eac583 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java @@ -282,6 +282,8 @@ public class ElfWriter { // ------------------------------------------------------------------------ public ElfWriter export(boolean emitEntrySymbol) { + if( _code._serial==null ) + throw new IllegalStateException("ELF export needs ideal IR: request Export from the driver, or Serialize before Lower"); // Sections are created in the order they are emitted. _sections = new Ary<>(Section.class); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java new file mode 100644 index 00000000..923486c6 --- /dev/null +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java @@ -0,0 +1,44 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.node.*; +import java.util.Arrays; + +// Comnpute field layouts only after SCCP and its peepholes converge. +// Keep surviving functions rooted without introducing unknown callers. +abstract class FinalizeIR { + static void run(CodeGen code) { + // Compute field layouts and replace symbolic field offsets by constants. + for( int i=0; i ((((ReturnNode)x).fun().isClz() ? -1 : x._nid) - + (((ReturnNode)y).fun().isClz() ? -1 : y._nid) )); + } +} 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 33d971e9..09eb8d33 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -60,7 +60,7 @@ public abstract class GlobalCodeMotion { if( use==null || globals.containsKey(use) ) continue; FunNode fun = useFun(use); if( fun==null ) continue; // Global metadata has no function owner. - assert CodeGen.CODE.owns(fun); + assert CodeGen.CODE._mach==null || CodeGen.CODE.owns(fun); // Ideal evaluation includes imported bodies. var local = copies.computeIfAbsent(fun,f -> new IdentityHashMap<>()); Node copy = cloneGlobal(con,fun,globals,local); for( int i=0; i antideps = new Ary<>(Node.class); // Breadth-first scheduling - breadth(code._stop,ns,late,anti); + breadth(code._stop,ns,late,anti, antideps); // Copy the best placement choice into the control slot for( int i=0; i antideps) { // Things on the worklist have some (but perhaps not all) uses done. WorkList work = new WorkList<>(); work.push(stop); @@ -172,12 +173,12 @@ public abstract class GlobalCodeMotion { // Loads need their memory inputs' uses also done if( n instanceof MemOpNode ld && ld._isLoad ) - for( Node memuse : ld.antiDeps() ) + for( Node memuse : ld.antiDeps(antideps) ) if( late[memuse._nid]==null ) continue outer; // All uses done, schedule - _doSchedLate(n,ns,late,anti); + _doSchedLate(n,ns,late,anti,antideps); } // A use just finished; reconsider its inputs and waiting loads, @@ -194,7 +195,7 @@ public abstract class GlobalCodeMotion { } } - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { + private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti, Ary antideps) { // Walk uses, gathering the LCA (Least Common Ancestor) of uses CFGNode early = n.in(0) instanceof CFGNode cfg ? cfg : n.in(0).cfg0(); assert early != null; @@ -205,7 +206,7 @@ public abstract class GlobalCodeMotion { // Loads may need anti-dependencies, raising their LCA if( n instanceof MemOpNode load && load._isLoad ) - lca = find_anti_dep(lca,load,early,late,anti); + lca = find_anti_dep(lca,load,early,late,anti, antideps); // Walk up from the LCA to the early, looking for best place. This is // the lowest execution frequency, approximated by least loop depth and @@ -256,38 +257,26 @@ public abstract class GlobalCodeMotion { if( def.in(i)!=null ) wakeLoads(def.in(i),late,work,visit); } - private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late, int[] anti) { + private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late, int[] anti, Ary antideps) { // We could skip final-field loads here. // Walk LCA->early, flagging Load's block location choices for( CFGNode cfg=lca; cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep - for( Node mem : load.antiDeps() ) { - switch( mem ) { - case MemOpNode st: - assert late[st._nid]!=null; - lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti); - break; - case EscapeNode st: - assert late[st._nid]!=null; - lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti); - break; - case CallNode call: - assert late[call._nid]!=null; - lca = anti_dep(load,late[call._nid],call.cfg0(),lca,call,anti); - break; - case CLInitNode init: - assert late[init._nid]!=null; - lca = anti_dep(load,late[init._nid],init.cfg0(),lca,init,anti); - break; - case PhiNode phi: - // Repeat anti-dep for matching Phi inputs. - // No anti-dep edges but may raise the LCA. + for( Node mem : load.antiDeps(antideps) ) { + if( mem instanceof PhiNode phi ) { + // Inputs carrying different memory might overwrite this alias. + // Raise the LCA for those paths; the unchanged-memory paths + // do not clobber the load. No scheduling edge to the Phi. for( int i=1; i= defblk.idepth(); stblk = stblk.idom() ) { // Store and Load overlap, need anti-dependence if( anti[stblk._nid]==load._nid ) { lca = stblk.domLCA(lca,null); // Raise Loads LCA if( lca == stblk && st != null && !(st instanceof CallNode) && st._inputs.find(load) == -1 ) // And if something moved, - st.addDef(load); // Add anti-dep as well; Calls already end their block. + st.addDef(load); // Add anti-dep as well (calls already end their block) return lca; // Cap this stores' anti-dep to here } } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java new file mode 100644 index 00000000..5fc002a1 --- /dev/null +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java @@ -0,0 +1,126 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import java.util.BitSet; +import java.util.IdentityHashMap; + +// Replace ideal nodes with machine nodes while preserving CFG/loop metadata. +// Selection also owns target ABI masks and rebuilding the copied graph's uses. +class InstSelect { + private final CodeGen _code; + private InstSelect(CodeGen code) { _code=code; } + + static CodeGen select(CodeGen code, String cpu, String callingConv, String base) { + // Ideal evaluation schedules the ideal graph without a CPU port. + if( cpu==null ) return code; + return code.phase(CodeGen.Phase.Select, code._phase==CodeGen.Phase.Unlink, + () -> new InstSelect(code).run(cpu,callingConv,base)); + } + + private void run(String cpu, String callingConv, String base) { + _code._callingConv = callingConv; + + // Look for CPU in fixed named place: + // com.seaofnodes.simple.node.cpus."cpu"."cpu.class" + String clzFile = base+"."+cpu+"."+cpu; + try { _code._mach = Class.forName(clzFile).asSubclass(Machine.class).getDeclaredConstructor(CodeGen.class).newInstance(_code); } + catch( Exception e ) { throw new RuntimeException(e); } + + _code._cCallingConv = _code._mach.cCallingConv(callingConv); + + // Build global copies of common register masks. + long callerSave = _code._mach.callerSave(); + long cCallerSave= _code._mach.callerSave(_code._cCallingConv); + long neverSave = _code._mach. neverSave(); + int maxReg = Math.min(64,_code._mach.regs().length); + assert maxReg>=64 || (-1L << maxReg & callerSave)==0; // No stack slots in callerSave + assert maxReg>=64 || (-1L << maxReg & cCallerSave)==0; // No stack slots in cCallerSave + _code._callerSave = new RegMask(callerSave); + _code._cCallerSave= new RegMask(cCallerSave); + + // Build a Return RegMask array. All returns have the following inputs: + // 0 - ctrl + // 1 - memory + // 2 - varies with returning GPR,FPR + // 3 - RPC + // 4+- Caller save registers + _code._retMasks = new RegMask[(maxReg-_code._callerSave.size()-Long.bitCount( neverSave ))+4]; + for( int reg=0, i=4; reg(); + _instSelect( _code._stop, map ); + _code._stop = (StopNode)map.get(_code._stop ); + StartNode start = (StartNode)map.get(_code._start); + _code._start = start==null ? new StartNode(_code._start) : start; + _instOuts(_code._stop,_code.visit()); + _code._visit.clear(); + + // Replace the CompUnit stop (and list of functions) + // with hardware-specific ones + for( CompUnit cu : _code._compunits.values() ) { + cu._start= (StartCUNode)map.get(cu._start); + cu._stop = (StopCUNode )map.get(cu._stop ); + } + } + + private Node _instSelect( Node n, IdentityHashMap map ) { + if( n==null ) return null; + Node x = map.get(n); + if( x !=null ) return x; // Been there, done that + + // If n is a MachNode already, then its part of a multi-node expansion. + // It does not need instruction selection (already selected!) + // but it does need its inputs walked. + if( n instanceof MachNode ) { + for( int i=0; i < n.nIns(); i++ ) + n._inputs.set(i, _instSelect(n.in(i),map) ); + return n; + } + + // Produce a machine node from n; map it to flag as done so stops cycles. + if( n instanceof MemOpNode mem && mem.off() instanceof ExternOffsetNode off ) { + // External fields replace base+offset with symbol+0. Keep the ideal + // declaring type on the address for machine load/store width selection. + TypeMemPtr ptr = (TypeMemPtr)mem.ptr()._type; + n._inputs.set(2,new ExternNode(TypeMemPtr.make((byte)2,ptr._obj,true),off._extern)); + n._inputs.set(3,ConstantNode.raw(TypeInteger.ZERO)); + } + map.put(n, x=_code._mach.instSelect(n) ); + // Carry loop-tree and pre-order info across the ideal->mach transition + if( n instanceof CFGNode ncfg && x instanceof CFGNode xcfg ) { + xcfg._ltree = ncfg._ltree; + xcfg._pre = ncfg._pre; + } + // 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) ); + // Post selection action + if( x instanceof MachNode mach ) { + if( n instanceof ReturnNode ret ) + ((ReturnNode)mach)._fun = (FunNode)map.get(ret._fun); + mach.postSelect(_code); // Post selection action + } + + return x; + } + + private void _instOuts( Node n, BitSet visit ) { + if( visit.get(n._nid) ) return; + visit.set(n._nid); + for( Node in : n._inputs ) + if( in!=null ) { + in._outputs.push(n); + // CallNode special: outputs are partially ordered; CallEnd in slot 0 + if( in instanceof CallNode call && n instanceof CallEndNode cend && call.out(0) != cend ) + call._outputs.swap(0,call.nOuts()-1); + _instOuts(in,visit); + } + } +} diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Iter.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Iter.java new file mode 100644 index 00000000..c5120370 --- /dev/null +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Iter.java @@ -0,0 +1,60 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; + +// Establish a pessimistic fixed point after parsing/loading. Later Iter runs +// reuse the worklist and types produced by the preceding phase. +abstract class Iter { + static void run(CodeGen code) { + // 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: 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 = code._externPaths != null; + code._start.walk(n -> { + if( !(n instanceof ConstantNode) ) + n._type = hasImports ? iterImportReset(n._type) : iterEscapeReset(n._type); + code.add(n); + return null; + }); + code._iter.iterate(code); + // Expensive assert. + assert !CodeGen.expensiveAssert() || Opto.fixedPointCheck(code); + } + + private static Type iterEscapeReset(Type t) { + if( t instanceof TypeMem mem ) + return mem._one ? mem : mem.makeFrom(XInt.FULL,XInt.FULL); + if( t instanceof TypeTuple tt ) { + TypeTuple rez = tt; + for( int i=0; i(LRG.class); _adj.push(lrg); 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 c41a29ac..ef222f60 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -73,8 +73,10 @@ abstract public class Opto { FunNode fun = ret.fun(); // Start is a semantic unknown-caller edge. Public functions // keep it; closed-world functions must be reached by a - // concrete Call edge discovered during SCCP. - if( !(code.owns(fun) && fun.isClz()) && + // concrete Call edge discovered during SCCP. Initializers, + // including private/imported ones, are called by opaque CLInit + // obligations whose Call edges are introduced only in Lower. + if( !fun.isClz() && !code.publicFIDX(fun.sig().fidx()) && fun.in(1) instanceof StartNode ) { fun.removeDeadPath(1); 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 bb123634..7ce727fd 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java @@ -13,6 +13,18 @@ import java.util.*; // Parse a given file, and all its dependencies public abstract class ParseAll { + static void parse(CodeGen code, String src) { + Parser.TYPES.clear(); + Parser.TYPES.putAll(Parser.INIT_TYPES); + if( src != null ) { + // No source file, just the source itself. + parseSource(code,code._srcName==null ? "Test" : code._srcName,src); + } else { + // Path from module root to source file + parsePath(code,code._srcName); + } + } + // Worklist of symbols to search and files to parse private static final Ary WORK = new Ary<>(CompUnit.class); 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 1ce68080..ac792988 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -518,7 +518,7 @@ public class RegAlloc { // 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 instanceof SplitNode split && !split.isNonStackSplit() && min!=max ) continue; // Ordinary splits already reach stack storage. if( n.isDead() ) continue; // Some Cloneable went dead by other spill changes // If this is a 2-address commutable op (e.g. AddX86, MulX86) and the rhs has only a single user, // commute the inputs... which chops the LHS live ranges' upper bound to just the RHS. @@ -572,8 +572,8 @@ public class RegAlloc { } private static long ldepth( long ld, Node n, CFGNode cfg ) { - // Do not count splits - if( n instanceof SplitNode ) return ld; + // Ordinary splits already reach stack storage; register-only transfers do not. + if( n instanceof SplitNode split && !split.isNonStackSplit() ) return ld; // Collect min/max loop depth int min = (int)ld; int max = (int)(ld>>32); 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 1806be24..6a23252d 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Serialize.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Serialize.java @@ -8,6 +8,13 @@ import java.util.*; abstract public class Serialize { + // Encoding/emulation need only machine code. File export also needs ideal + // IR for a later compiler to import; an explicit Serialize request stops here. + static void forTarget(CodeGen code, CodeGen.Phase target, boolean inMemory) { + if( target==CodeGen.Phase.Serialize || (target.ordinal()>=CodeGen.Phase.Export.ordinal() && !inMemory) ) + code.serialize(); + } + static void serialize( CodeGen code ) { // Get all Nodes in a sane order @@ -68,6 +75,15 @@ abstract public class Serialize { // Initialize the mapping from bits/tags to types Type.TAGOFFS(); + IdentityHashMap anodes = new IdentityHashMap<>(); + for( Node n : nodes ) anodes.put(n,anodes.size()+1); // 0 is null. + // The saved wrappers summarize this object's units only. Keep the + // live whole-program graph intact for subsequent lowering. + TypeTuple stopType = TypeTuple.STOP_HIGH; + for( Node n : nodes.last()._inputs ) + if( anodes.containsKey(n) ) stopType = (TypeTuple)stopType.meet(n._type); + Type startType = TypeTuple.make(Type.CONTROL,stopType.mem(),((StartNode)nodes.at(0)).arg()); + BAOS baos = new BAOS(); // A - Print the C0DE header. The format is not versioned yet. baos.write('C').write('0').write('D').write('E'); @@ -91,6 +107,8 @@ abstract public class Serialize { if( n instanceof ParmNode parm ) parm._declaredType.gather(types); if( n instanceof TypeNode con ) con._con .gather(types); } + stopType.gather(types); + startType.gather(types); // A defined class remains importable even when its initializer body dies. for( TypeStruct ts : pubTypes ) if( Parser.startsClzPrefix(ts._name) && @@ -190,21 +208,20 @@ abstract public class Serialize { // How many nodes? baos.packed4(nodes._len); - // Radix sort by Node ID#, new compressed NIDs - IdentityHashMap 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()); - baos.packed2(types.get(n._type)); + baos.packed2(types.get(n==nodes.at(0) ? startType : n==nodes.last() ? stopType : n._type)); n.packed(baos,strs,types,anodes); } // Write out the input indices packed. for( Node n : nodes ) { for( int j=0; j nodes) { + if( n instanceof ParmNode parm ) n=parm.fun(); + if( (n instanceof FunNode || n instanceof CallEndNode) && i>0 ) + return nodes.containsKey(n.in(i)); + if( n instanceof StopNode ) return nodes.containsKey(n.in(i)); + return true; + } + + public static int nIns(Node n, IdentityHashMap nodes) { + int len=0; + for( int i=0; i void gather( HashMap strs, T s) { if( s!=null && !strs.containsKey(s) ) strs.put(s,strs.size()); @@ -450,7 +483,6 @@ abstract public class Serialize { // -------------------------------------------------- public static Ary nodeOrder( CodeGen code, CompUnit cu ) { - assert code._start._ltree != null; // Uses loop tree BitSet visit = code.visit(); Ary nodes = new Ary<>(Node.class); visit.set(code._stop._nid); @@ -501,7 +533,6 @@ abstract public class Serialize { // -------------------------------------------------- public static Ary nodeOrder( CodeGen code ) { - assert code._start._ltree != null; // Uses loop tree Ary nodes = new Ary<>(Node.class); BitSet visit = code.visit(); nodes.add(code._start); @@ -555,6 +586,9 @@ abstract public class Serialize { private static void _funWalk( FunNode fun, Ary rpo, BitSet visit ) { int start = rpo._len; _funRPO(fun,rpo,visit); + // A nonreturning function still owns a Return, even before LoopTree + // inserts synthetic exits. No loop-depth ordering is needed on disk. + _funRPO(fun.ret(),rpo,visit); int len = rpo._len - start; for( int i=0; i< len>>1; i++ ) rpo.swap(start+i,start+len-1-i); @@ -566,13 +600,9 @@ abstract public class Serialize { visit.set(n._nid); // Stop recursion // Walk outputs ordered if( n instanceof CFGNode ncfg ) { - // If nodes walk outer loops before inner, so they hit the - // Return first, so Return is at the bottom of the RPO. if( n instanceof IfNode iff ) { CProjNode c0 = iff.cproj(0); CProjNode c1 = iff.cproj(1); - if( c0._ltree.depth() > c1._ltree.depth() ) - { c0 = c1; c1 = iff.cproj(0); } _funRPO(c0,rpo,visit); _funRPO(c1,rpo,visit); } else if( n instanceof StopNode ) { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/StaticData.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/StaticData.java index f9f16008..616753d4 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/StaticData.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/StaticData.java @@ -56,24 +56,6 @@ public final class StaticData { return owner; } - // A final field whose declaration already denotes this exact constant is - // available as that value to every ideal Load. Materialize it in the object - // image instead of emitting the redundant initializer Store. This lowering - // leaves serialized ideal IR intact, so imports retain their memory edges. - static boolean preinitialized(CodeGen code,StoreNode st) { - if( !(st.ptr()._type instanceof TypeMemPtr ptr) || !ptr._one || !isClass(ptr._obj) ) return false; - CompUnit owner=owner(code,ptr._obj); - if( owner==null || owner._src==null ) return false; - if( !(Parser.TYPES.get(ptr._obj._name) instanceof TypeStruct ts) ) return false; - Field fld=ts.field(st._name); - if( fld==null || !fld._final || !fld._t.isConstant() || !st.val()._type.isConstant() ) return false; - Type value=st.val()._type, declared=fld._t; - if( declared instanceof TypeFunPtr fp && value instanceof TypeFunPtr vp ) return fp.fidx()==vp.fidx(); - if( declared instanceof TypeMemPtr ptr0 && value instanceof TypeMemPtr ptr1 ) - return pointerConstant(ptr0) && ptr0._obj==ptr1._obj; - return declared==value; - } - ObjectData object(Type t) { Object key=isClass(t) ? ((TypeStruct)t)._name : t instanceof TypeFunPtr fp ? functionSymbol(fp) : t; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java new file mode 100644 index 00000000..9b4b0995 --- /dev/null +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java @@ -0,0 +1,57 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.util.Ary; + +// Reject invalid optimized programs before lowering erases their source-level +// obligations. Queue surviving CLInits during the same walk for Lower's Iter. +abstract class TypeCheck { + static void run(CodeGen code) { + // Check for class-init cycles first; such a cycle can prevent other + // things from resolving types. The dependency graph is temporary. + String clzInitCycle = new ClassInitDependencies(code).check(); + if( clzInitCycle != null ) + throw Parser.error(clzInitCycle,null); + + Ary errs = new Ary<>(Node.class); + code._stop.walk( n -> { + if( n.err() != null ) + errs.add(n); + if( n instanceof CLInitNode ) code.add(n); + return null; + }); + + if( !errs.isEmpty() ) { + // Prefer an originating error over a secondary error caused by a + // BOTTOM input. If all errors are downstream-poisoned, retain + // the old first-error behavior. + Node min = null; + for( Node n : errs ) + if( noBottomInputs(n) ) + { min = n; break; } + if( min==null ) + min = errs.at(0); + for( Node n : errs ) + if( n!=min && + noBottomInputs(n) && + ((n instanceof MemOpNode nmop && + min instanceof MemOpNode mmop && + nmop._loc.before(mmop._loc)) || + (n instanceof CFGNode ncfg && + min instanceof CFGNode mincfg && + ncfg.idepth() < mincfg.idepth())) ) + min = n; + if( code._obs != null ) code._obs.error(min, min.err().getMessage()); + throw min.err(); + } + } + + private static boolean noBottomInputs(Node n) { + for( Node def : n._inputs ) + if( def!=null && !(def instanceof FldOffNode) && def._type==Type.BOTTOM ) + return false; + return true; + } +} diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Unlink.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Unlink.java new file mode 100644 index 00000000..fb1c4a6f --- /dev/null +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Unlink.java @@ -0,0 +1,112 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.node.*; + +// Discard call-graph edges after LoopTree. Machine selection keeps only this +// object's bodies; ideal evaluation keeps imports so their calls can execute. +abstract class Unlink { + private static void unlinkImports(CodeGen code) { + // Imported function constants keep their symbolic identity, not an + // embedded copy of the other object's Return and body. + for( Node n : code._start._outputs.asAry() ) + if( n instanceof FunPtrNode ptr && ptr.ret()!=null && !code.owns(ptr.fun()) ) { + ptr.liftType(ptr._type); + ptr.setDef(1,null); + } + for( FunNode fun : code._linker ) { + if( fun==null || fun.isDead() || code.owns(fun) ) + continue; + for( int i=1; i 1 ) { + if( fun.in(1) instanceof CallNode call ) + call.unlink(fun,1); + else + fun.removeDeadPath(1); + } + StartCUNode start = fun._compunit._start; + StopCUNode stop = fun._compunit._stop; + // Unhook the Stop->Return edge also + ReturnNode ret = fun.ret(); + int idx = stop._inputs.find(ret); + if( idx != -1 ) { + stop._inputs.del(idx); + ret.delUse(stop); + } + // + if( stop.nIns()==0 ) { + idx = code._stop._inputs.find(stop); + if( idx != -1 ) + code._stop.delDef(idx); + if( start.nIns() > 0 && start.in(0) != null ) + start.setDef(0,null); + if( start.nIns() > 1 && start.in(1) != null ) + start.setDef(1,null); + } + continue; + } + + // Insert the post-Opto code-generation hook. Unlike an Opto-time + // Start input, this no longer carries unknown-caller semantics. + ReturnNode ret = fun.ret(); + StartNode start = fun._compunit._start; + assert start!=null; + if( fun.nIns() <= 1 || fun.in(1) != start ) { + fun.insertDef(1,start); + for( Node use : fun._outputs ) + if( use instanceof ParmNode parm ) + parm.insertDef(1,ConstantNode.raw(parm._type)); + if( fun._compunit._stop._inputs.find(ret) == -1 ) + fun._compunit._stop.addDef(ret); + } + // Unlink from Call + for( int i=2; i { + if( n instanceof CallEndNode cend ) + for( int i=1; i missingAlias(mmm,false); + case MemMergeNode mmm -> missingAlias(mmm); case MemOpNode mem -> unsplit(mem._alias); case BulkMemPhiNode bulk -> missingAlias(bulk); default -> throw Utils.TODO("Should not reach here"); @@ -154,7 +154,7 @@ public class BulkMemPhiNode extends PhiNode { return switch(use) { case ScopeNode scope -> 0; case ParmNode parm -> 0; - case MemMergeNode mmm -> missingAlias(mmm,true); + case MemMergeNode mmm -> missingAlias(mmm); case BulkMemPhiNode bulk -> missingAlias(bulk); case MemOpNode mem -> unsplit(mem._alias); case MemPhiNode phi -> unsplit(phi._alias); @@ -183,14 +183,14 @@ public class BulkMemPhiNode extends PhiNode { return 0; } - // First precise MemMerge slice still covered by this Phi. When inspecting - // a user, ignore slots which point back to this Phi. - private int missingAlias(MemMergeNode mmm, boolean user) { + // First explicit MemMerge slice still covered by this Phi. A user's slice + // may point to this Phi after a precise Phi folds; splitting is still valid. + private int missingAlias( MemMergeNode mmm ) { for( int alias=2; alias strs, HashMap types, IdentityHashMap anodes ) { - baos.packed1(nIns()); + baos.packed1(Serialize.nIns(this,anodes)); // Linked CallEnds depend on Return types which depend on CallEnds; // break the cycle baos.packed2(types.get(_type)); @@ -108,7 +108,9 @@ public class CallEndNode extends CFGNode implements MultiNode { // effects. if( (nIns()-1)+externs < tfp.nfcns() ) { // If during Opto, assume call won't be called and thus won't return anything. - boolean opto = CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Opto.ordinal(); + // Lowered calls deliberately have no links into optimized bodies. + boolean opto = CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Opto.ordinal() && + CodeGen.CODE._phase.ordinal() < CodeGen.Phase.Lower.ordinal(); Type tmem = opto ? TypeMem.TOP : TypeMem.BOT; Type ret = opto ? Type.TOP : tfp.ret(); return TypeTuple.make(Type.CONTROL,tmem,ret); 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 b4bb5e72..71f6d146 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -101,6 +101,9 @@ public class CallNode extends CFGNode { @Override public Node idealize() { + // Lowering may introduce calls after the call graph has been analyzed. + // These use the callee interface without reopening its parameter flow. + if( CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Lower.ordinal() ) return null; CallEndNode cend = cend(); if( cend==null ) return null; // Still building diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 4357570e..0569f352 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -37,13 +37,13 @@ public class ConstantNode extends TypeNode { } static Node make( BAOS bais, Type[] types) { return raw(types[bais.packed2()]); } - // Semantic constant construction through FinalizeIR. A unique internal + // Semantic constant construction through Lower. A unique internal // function identity carries a lifetime edge to the function's Return. public static Node make( Type type ) { if( type==Type. CONTROL ) return new CtrlNode(); if( type==Type.XCONTROL ) return new XCtrlNode(); if( CodeGen.CODE._phase != null && - CodeGen.CODE._phase.ordinal() > CodeGen.Phase.FinalizeIR.ordinal() ) + CodeGen.CODE._phase.ordinal() > CodeGen.Phase.Lower.ordinal() ) return raw(type); if( type instanceof TypeFunPtr tfp && tfp.isConstant() ) { FunNode fun = CodeGen.CODE._link(tfp); 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 7f9a2819..edde247a 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -45,7 +45,7 @@ public class FunNode extends RegionNode { @Override public Tag serialTag() { return Tag.Fun; } @Override public void packed(BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { assert !_folding; - baos.packed1(nIns()); // Number of linked calls + baos.packed1(Serialize.nIns(this,anodes)); // Object-local linked calls baos.packed2(types.get(_sig)); // NPE if fails lookup baos.packed2(_name==null ? 0 : strs.get(_name)); baos.packed2(_approxUIDs); @@ -171,7 +171,8 @@ public class FunNode extends RegionNode { // through class-field loads and other initially imprecise values. // - FIDX is not in the escape set // - Not called anywhere else; post Opto called-not-escaped functions need to still be hooked to start - if( in(1) instanceof StartCUNode start ) { + // Opaque CLInit obligations need their bodies even without Call edges. + if( !isClz() && in(1) instanceof StartCUNode start ) { boolean preOpto = CodeGen.CODE._phase == null || CodeGen.CODE._phase.ordinal() < CodeGen.Phase.Opto.ordinal(); if( !preOpto && !start.escapedFIDX(_sig.fidx()) && nIns()<=2 && _ret!=null ) { 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 b31e14d5..bfbd46c3 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -6,13 +6,9 @@ import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.codegen.GlobalBits; import com.seaofnodes.simple.type.*; -import com.seaofnodes.simple.util.BAOS; -import com.seaofnodes.simple.util.Utils; +import com.seaofnodes.simple.util.*; import java.lang.StringBuilder; -import java.util.BitSet; -import java.util.ArrayList; -import java.util.HashMap; -import java.util.IdentityHashMap; +import java.util.*; /** * Convenience common base for Load and Store. @@ -140,27 +136,24 @@ public abstract class MemOpNode extends TypeNode { // Memory writers which must follow this read. A packaging node is not a // write; follow this alias through aggregates to its writers. - public ArrayList antiDeps() { - ArrayList deps = new ArrayList<>(); - antiDeps(mem(),deps,new BitSet()); - return deps; + public Ary antiDeps( Ary antideps ) { + antideps.clear(); + return antiDeps(mem(),antideps); } - private void antiDeps(Node mem, ArrayList deps, BitSet visit) { - if( visit.get(mem._nid) ) return; - visit.set(mem._nid); + private Ary antiDeps( Node mem, Ary antideps ) { for( Node use : mem._outputs ) { if( use instanceof MemMergeNode merge ) { - Node slice = _alias strs, HashMap types, IdentityHashMap anodes ) { - baos.packed1(nIns()); // Number of linked calls + baos.packed1(Serialize.nIns(this,anodes)); // Object-local linked calls baos.packed2(_label==null ? 0 : strs.get(_label)); baos.packed2(types.get(_declaredType)); // NPE if fails lookup baos.packed1(_idx); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/SplitNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/SplitNode.java index 0e104c15..3042f857 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/SplitNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/SplitNode.java @@ -13,6 +13,8 @@ public abstract class SplitNode extends MachConcreteNode { public final String _kind; // Kind of split public final byte _round; // Debugging info for which RegAlloc round public SplitNode(LRG lrg,String kind, byte round, Node[] nodes) { super(nodes); _lrg=lrg; _kind = kind; _round = round; } + // A register-only transfer may need another split to reach stack storage. + public boolean isNonStackSplit() { return false; } @Override public String op() { return "mov"; } @Override protected ExprPrinter _print1(ExprPrinter p) { p.p("mov("); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/StartNode.java index 84c8a3a7..495be0a2 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -45,11 +45,11 @@ public class StartNode extends LoopNode implements MultiNode { // Find module., it's the start. CFGNode C = null; for( Node use : _outputs ) - if( use instanceof FunNode fun && fun.isModInit() ) + if( use instanceof FunNode fun && CodeGen.CODE.entryClinitName().equals(fun._name) ) { assert C==null; C = fun; } if( C==null ) for( FunNode fun : CodeGen.CODE._linker ) - if( fun!=null && !fun.isDead() && fun.isModInit() ) + if( fun!=null && !fun.isDead() && CodeGen.CODE.entryClinitName().equals(fun._name) ) { assert C==null; C = fun; } return C; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/StopCUNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/StopCUNode.java index f2bd5841..d3a356ed 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/StopCUNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/StopCUNode.java @@ -41,7 +41,7 @@ public class StopCUNode extends StopNode { // below must not forget private bits already discovered precisely from // that Return on an earlier SCCP step. if( CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Opto.ordinal() && - CodeGen.CODE._phase.ordinal() <= CodeGen.Phase.FinalizeIR.ordinal() && + CodeGen.CODE._phase.ordinal() <= CodeGen.Phase.Lower.ordinal() && _type instanceof TypeTuple old && old.mem() instanceof TypeMem omem ) xmem = xmem.makeFrom(XInt.meet(xmem._escFs,omem._escFs), XInt.meet(xmem._escAs,omem._escAs)); @@ -102,7 +102,7 @@ public class StopCUNode extends StopNode { // input refinement add bits, reversing Iter's monotonic direction. // This normalization is needed only for Opto's optimistic grand cycle. if( CodeGen.CODE._phase.ordinal() < CodeGen.Phase.Opto.ordinal() || - CodeGen.CODE._phase.ordinal() > CodeGen.Phase.FinalizeIR.ordinal() ) return mem; + CodeGen.CODE._phase.ordinal() > CodeGen.Phase.Lower.ordinal() ) return mem; int[] escFs = XInt.isHigh(mem._escFs) ? XInt.meet(prior._escFs,CodeGen.CODE.publicFIDXs()) : mem._escFs; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/StopNode.java index e52a49a2..a7e52563 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.Serialize; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.BAOS; @@ -18,7 +19,7 @@ public class StopNode extends CFGNode { } public StopNode(StopNode stop) { super(stop); } @Override public Tag serialTag() { return Tag.Stop; } - @Override public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { baos.packed1(nIns()); } + @Override public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { baos.packed1(Serialize.nIns(this,anodes)); } static Node make( BAOS bais ) { StopNode stop = new StopNode(); stop.setDefX(bais.packed1()-1,null); 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 418b1e92..8a0bf8d4 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -89,6 +89,16 @@ public class StoreNode extends MemOpNode { Type decl = declaredType(); if( decl != Type.BOTTOM ) { assert decl != Type.TOP; val = val.join(decl); } + // A singleton class's final constant field lives in the static image. + // Its precise memory slice is a constant too; ordinary peepholes can + // replace this Store before scheduling or instruction selection. + // A constant runtime value alone is not enough: mutable fields (notably + // $init) still need their writes, and instance fields need allocation. + Field fld = ptr._obj.field(_name); + if( _alias!=1 && ptr._one && Parser.startsClzPrefix(ptr._obj._name) && + fld!=null && fld._final && decl.isConstant() ) + return TypeMem.make(_alias,val,true,true,true,mem._escFs,mem._escAs).escapesFrom(val); + // Allocation uses a private TypeMem and nothing else does. This // memory is truly private; a temporary singleton until it escapes - // which is never does in a constructor. @@ -108,7 +118,6 @@ public class StoreNode extends MemOpNode { Type t = val.meet(tfld); // Bulk memory's final bit describes its conservative remainder, not // this newly precise slice. Slice finality comes from the field. - Field fld = ptr._obj.field(_name); boolean xfinal = fld != null && fld._final; return TypeMem.make(_alias,t,mem._one,mem._clz,xfinal,mem._escFs,mem._escAs).escapesFrom(val); } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/SplitFlagsARM.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/SplitFlagsARM.java new file mode 100644 index 00000000..25e5d501 --- /dev/null +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/SplitFlagsARM.java @@ -0,0 +1,21 @@ +package com.seaofnodes.simple.node.cpus.arm; + +import com.seaofnodes.isa.Arm64; +import com.seaofnodes.simple.codegen.*; + +// NZCV transfers require a GPR. Further splits can spill that GPR to the stack. +public class SplitFlagsARM extends SplitARM { + private static final RegMask MASK = new RegMask(arm.WR_BITS,1L); + SplitFlagsARM(LRG lrg,String kind,byte round) { super(lrg,kind,round); } + @Override public boolean isNonStackSplit() { return true; } + @Override public RegMask regmap(int i) { return MASK; } + @Override public RegMask outregmap() { return MASK; } + + @Override public void encoding(Encoding enc) { + short dst=enc.reg(this), src=enc.reg(in(1)); + if( dst==src ) return; + if( src==arm.FLAGS ) enc.add4(Arm64.flags(dst,false)); + else if( dst==arm.FLAGS ) enc.add4(Arm64.flags(src,true)); + else super.encoding(enc); + } +} diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/SplitGPRARM.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/SplitGPRARM.java new file mode 100644 index 00000000..c9b2127a --- /dev/null +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/SplitGPRARM.java @@ -0,0 +1,11 @@ +package com.seaofnodes.simple.node.cpus.arm; + +import com.seaofnodes.simple.codegen.*; + +// Keep a saved NZCV value in GPRs and stack slots through subsequent spills. +public class SplitGPRARM extends SplitARM { + private static final RegMask MASK = new RegMask(arm.WR_BITS,-2L); + SplitGPRARM(LRG lrg,String kind,byte round) { super(lrg,kind,round); } + @Override public RegMask regmap(int i) { return MASK; } + @Override public RegMask outregmap() { return MASK; } +} diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java index 8c9bed95..3c965da5 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java @@ -288,7 +288,16 @@ public class arm extends Machine { @Override public int rpc() { return X30; } // Create a split op; any register to any register, including stack slots - @Override public SplitNode split(LRG lrg, String kind, byte round) { return new SplitARM(lrg,kind,round); } + @Override public SplitNode split(LRG lrg, String kind, byte round) { + RegMask def = lrg._machDef==null ? null : lrg._machDef.outregmap(), use = lrg.useMask(); + if( (def!=null && def.size1() && def.test(FLAGS)) || + (use!=null && use.size1() && use.test(FLAGS)) ) + return new SplitFlagsARM(lrg,kind,round); + // Spilling the saved flags requires a GPR between NZCV and the stack. + if( lrg._machDef instanceof SplitFlagsARM || lrg._machDef instanceof SplitGPRARM ) + return new SplitGPRARM(lrg,kind,round); + return new SplitARM(lrg,kind,round); + } // Return a MachNode unconditional branch @Override public CFGNode jump() { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SplitFlagsX86.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SplitFlagsX86.java new file mode 100644 index 00000000..cb7694f9 --- /dev/null +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SplitFlagsX86.java @@ -0,0 +1,25 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.isa.X86; +import com.seaofnodes.simple.codegen.*; + +// Flag snapshots can use GPRs or stack slots, but never XMM registers. +public class SplitFlagsX86 extends SplitX86 { + private static final RegMask MASK = new RegMask(x86_64_v2.WR_BITS | (1L<=x86_64_v2.MAX_REG ) + X86.flagsStack(enc,fun(enc).computeStackOffset(enc._code,reg),toFlags); + else + X86.flags(enc,reg,toFlags); + } else super.encoding(enc); + } +} diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SplitX86.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SplitX86.java index b2b643d3..46f2cb16 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SplitX86.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SplitX86.java @@ -16,12 +16,10 @@ public class SplitX86 extends SplitNode { @Override public RegMask regmap(int i) { return x86_64_v2.SPLIT_MASK; } @Override public RegMask outregmap() { return x86_64_v2.SPLIT_MASK; } - // Need to handle 8 cases: . reg->reg, reg->xmm, reg->flags, xmm->reg, xmm->xmm, xmm->flags, flags->reg, flags->xmm, - // flags->flags. + // Moves among GPRs, XMM registers, and stack slots. @Override public void encoding( Encoding enc ) { short dst=enc.reg(this), src=enc.reg(in(1)); - if( dst==x86_64_v2.FLAGS ) { X86.flags(enc,src,true); return; } - if( src==x86_64_v2.FLAGS ) { X86.flags(enc,dst,false); return; } + assert dst!=x86_64_v2.FLAGS && src!=x86_64_v2.FLAGS; boolean dstX=dst>=x86_64_v2.XMM_OFFSET, srcX=src>=x86_64_v2.XMM_OFFSET; // Stack spills if( dst >= x86_64_v2.MAX_REG ) { 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 7b351533..3dc93bf6 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 @@ -47,7 +47,7 @@ public class x86_64_v2 extends Machine { static RegMask DIV_MASK = new RegMask(RD_BITS & ~(1L< { @Override protected void compile(String src) { _code = new CodeGen(src); _code._obs = this; - _code.parse().iter().opto().iterPostOpto().finalizeIR().typeCheck(); + _code.driver(CodeGen.Phase.TypeCheck); } @Override protected String phase() { return _code._phase.name(); } @Override protected int pos() { return _code._phase == CodeGen.Phase.Parse ? _code.P.pos() : -1; } -- cgit v1.2.3