From e481e3d215882faa82b19f29cfde5746d4e51863 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Wed, 28 Oct 2026 12:26:28 -0700 Subject: Backport Opto speedups and Minus fix --- .../java/com/seaofnodes/simple/codegen/Opto.java | 79 +++++++++++++--------- .../java/com/seaofnodes/simple/node/FunNode.java | 2 +- .../java/com/seaofnodes/simple/node/MinusNode.java | 24 +++---- .../main/java/com/seaofnodes/simple/node/Node.java | 2 + .../java/com/seaofnodes/simple/Chapter20Test.java | 2 +- .../java/com/seaofnodes/simple/MinusNodeTest.java | 73 ++++++++++++++++++++ 6 files changed, 135 insertions(+), 47 deletions(-) create mode 100644 chapter27/src/test/java/com/seaofnodes/simple/MinusNodeTest.java (limited to 'chapter27/src') diff --git a/chapter27/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/chapter27/src/main/java/com/seaofnodes/simple/codegen/Opto.java index 3c34b44c..d8cef195 100644 --- a/chapter27/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/chapter27/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.IterPeeps.WorkList; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; import java.util.BitSet; @@ -26,8 +27,11 @@ abstract public class Opto { public static void opto(CodeGen code) { // Reset Types before running the worklist algorithm - Ary oldTypes = new Ary<>(Type.class); // Used for asserts only - resetToTop(code,oldTypes); + Ary oldTypes = new Ary<>(Type.class); + WorkList deps = new WorkList<>(); + WorkList changes = new WorkList<>(); + Ary modes = new Ary<>(Node.class); + resetToTop(code,oldTypes,modes); // Main seeds a whole program. Without main, named exported functions // seed discovery. Either way, escaping addresses can add more unknown @@ -42,24 +46,30 @@ abstract public class Opto { // OPTIMISTIC INTERPROCEDURAL SCCP - sccp(code, oldTypes); - resolveNumericModes(code); - if( !code._iter._work.isEmpty() ) sccp(code, oldTypes); + sccp(code, oldTypes, changes, deps); + // Settle modes, then resume SCCP on affected nodes without resetting types. + // Any further type changes must still fall; BOTTOM results stay BOTTOM. + resolveNumericModes(code,modes); + if( !code._iter._work.isEmpty() ) sccp(code, oldTypes, changes, deps); ProjNode startMem=code._start.proj(1); if( startMem!=null ) { startMem.unkeep(); code.add(startMem); } // After SCCP add everything changed to the worklist and see if // peepholes can make more progress. - moveChangesToWorklist(code, oldTypes); + Node dep; + while( (dep=deps.pop())!=null ) code.add(dep); + moveChangesToWorklist(code, oldTypes, changes); } // Reset Types before running the worklist algorithm - private static void resetToTop(CodeGen code, Ary oldTypes ) { + private static void resetToTop(CodeGen code, Ary oldTypes, Ary modes ) { code._start.walk( x -> { - oldTypes.setX(x._nid,x._type); // Record original types for asserts + // SCCP adds call edges and default arguments, not numeric operations. + if( x instanceof ModeNode mode && mode.mode()==0 ) modes.push(x); + oldTypes.setX(x._nid,x._type); // Compare the final SCCP type with Iter's type x._type = Type.TOP; // Reset all Nodes to TOP code._iter.add(x); // Visit everybody at least once; most Nodes produce better than TOP // Unlink all existing (conservative) linkages. @@ -145,7 +155,7 @@ abstract public class Opto { } // The core SCCP algorithm - private static void sccp( CodeGen code, Ary oldTypes ) { + private static void sccp( CodeGen code, Ary oldTypes, WorkList changes, WorkList deps ) { // Iter workList is empty at this point // OPTIMISTIC PASS Node n; @@ -154,6 +164,8 @@ abstract public class Opto { if( n.isDead() ) continue; count++; Type oval = n._type, nval = n.compute(); + // Filter candidates against the final SCCP type after convergence. + if( nval!=oldTypes.atX(n._nid) || n.isUnlocked() ) changes.push(n); if( oval == nval ) continue; assert oval.isa(nval) : n.label()+"#"+n._nid+" old="+oval+" new="+nval; // Types start high and always fall Type pesiVal = oldTypes.atX(n._nid); @@ -175,6 +187,9 @@ abstract public class Opto { // Since n._type changed, visit all output neighbors code._iter.addAll(n._outputs); + // SCCP consumes these without running peepholes. Save them for + // the following Iter pass before moving clears the dependency list. + for( int i=0; i oldTypes) { - code._start.walk( x -> { - assert x.compute() == x._type; // Hit the fixed point - assert x._nid >= oldTypes._len || x._type.isa(oldTypes.at(x._nid)); // Hit at least the bottom-up type - code._iter.add(x); - return null; - }); + private static void moveChangesToWorklist(CodeGen code, Ary oldTypes, WorkList changes) { + Node n; + while( (n=changes.pop())!=null ) { + if( n.isDead() ) continue; + assert n.compute() == n._type; // Hit the fixed point. + Type old = oldTypes.atX(n._nid); + assert old==null || n._type.isa(old); + if( n._type!=old || n.isUnlocked() ) { + code.add(n); + code.addAll(n._inputs); + code.addAll(n._outputs); + n.moveDepsToWorklist(); + } + } } - // Resolve arithmetic modes which are ambiguous only because they belong to - // a recursive component. Float wins because integer operands can be - // converted to float. - private static void resolveNumericModes(CodeGen code) { + // Resolve modes left undecided by SCCP, following recursive inputs for + // evidence. Float wins because integer operands can be converted to float. + private static void resolveNumericModes(CodeGen code, Ary modes) { final BitSet visited = new BitSet(); - code._stop.walk(n -> { - if( n instanceof ModeNode modeNode && modeNode.mode()==0 ) { + for( Node n : modes ) { + if( !n.isDead() && n instanceof ModeNode modeNode && modeNode.mode()==0 ) { visited.clear(); visited.set(n._nid); // Inspect inputs, not Bool's integer result int mode = 0; @@ -218,17 +239,11 @@ abstract public class Opto { // A closed recursive numeric component can have no remaining // concrete evidence after SCCP, e.g. dead all-integer loops. // With no float evidence, settle to integer. - if( mode == 0 ) - mode = 1; - if( mode != 0 ) { - // If both evidence, FP wins - modeNode.setMode((byte)((mode&2)==2 ? 2 : 1)); - code.add(n); - code.addAll(n.outs()); - } + modeNode.setMode((byte)((mode&2)==2 ? 2 : 1)); + code.add(n); + code.addAll(n.outs()); } - return null; - }); + } } // Gather numeric evidence through Phi and interprocedural return cycles. diff --git a/chapter27/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter27/src/main/java/com/seaofnodes/simple/node/FunNode.java index 2850ba92..7fd60d60 100644 --- a/chapter27/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter27/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -126,7 +126,7 @@ public class FunNode extends RegionNode { } // Upgrade inferred or user-written return type to actual - if( _ret!=null && _ret._type instanceof TypeTuple tt && + if( _ret!=null && addDep(_ret)._type instanceof TypeTuple tt && !(tt.ret() instanceof TypeMem) && tt.ret() != _sig.ret() ) { setSig(_sig.makeFrom(tt.ret())); return this; diff --git a/chapter27/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter27/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 4d7e3ddb..6409ad21 100644 --- a/chapter27/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter27/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -2,7 +2,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Utils; import java.util.HashMap; @@ -29,28 +28,27 @@ public class MinusNode extends Node implements ModeNode { @Override public Type compute() { Type t = in(1)._type; + // Constant array payloads lie below their element ranges in the lattice. + if( t instanceof TypeConAry ary ) t = ary.elem(); if( t==null ) return Type.TOP; if( t.isHigh() ) return _mode==0 ? Type.TOP : _mode==1 ? TypeInteger.TOP : t instanceof TypeFloat ? t : TypeFloat.F64.dual(); - byte mode = _mode; - if( mode==0 ) { - if( t instanceof TypeFloat ) mode=2; - if( t instanceof TypeInteger ) mode=1; - } - if( mode==0 ) - return CodeGen.CODE._phase.ordinal() < CodeGen.Phase.Opto.ordinal() ? Type.BOTTOM : Type.TOP; - if( mode==1 ) { - if( t instanceof TypeInteger i0 && - i0._min != Long.MIN_VALUE && i0._max != Long.MIN_VALUE ) + if( t instanceof TypeInteger i0 ) { + if( _mode==2 ) return TypeFloat.F64; + if( i0._min != Long.MIN_VALUE && i0._max != Long.MIN_VALUE ) return TypeInteger.make(-i0._max,-i0._min,i0._widen); return TypeInteger.BOT; } - if( t instanceof TypeFloat f ) + if( t instanceof TypeFloat f ) { + if( _mode==1 ) return TypeInteger.BOT; return f.isConstant() ? TypeFloat.constant(-f.value()) : f; - return TypeFloat.F64; + } + // No numeric family is known. This must be below both integer and + // float results, in either analysis direction and with any mode. + return Type.BOTTOM; } @Override diff --git a/chapter27/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter27/src/main/java/com/seaofnodes/simple/node/Node.java index 230593a8..77b1dd35 100644 --- a/chapter27/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter27/src/main/java/com/seaofnodes/simple/node/Node.java @@ -557,6 +557,8 @@ public abstract class Node extends BaseNode implements Cloneable { // probed to see if it can be inserted. His edges are "locked", because // hacking his edges will change his hash. int _hash; + // Edge and mode edits remove the node from GVN, even if its type is unchanged. + public boolean isUnlocked() { return _hash==0; } // If the _hash is set, then the Node is in the GVN table; remove it. void unlock() { diff --git a/chapter27/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter27/src/test/java/com/seaofnodes/simple/Chapter20Test.java index c5e4c583..2db10f8f 100644 --- a/chapter27/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter27/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -243,7 +243,7 @@ s.cs[0] = 67; // C s.cs[1] = 108; // l hashCode(s); """; - testTarget(src,"x86_64_v2", "SystemV",9,null); + testTarget(src,"x86_64_v2", "SystemV",0,null); testTarget(src,"riscv" , "SystemV",1,null); testTarget(src,"arm" , "SystemV",1,null); } diff --git a/chapter27/src/test/java/com/seaofnodes/simple/MinusNodeTest.java b/chapter27/src/test/java/com/seaofnodes/simple/MinusNodeTest.java new file mode 100644 index 00000000..497546df --- /dev/null +++ b/chapter27/src/test/java/com/seaofnodes/simple/MinusNodeTest.java @@ -0,0 +1,73 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.ConstantNode; +import com.seaofnodes.simple.node.MinusNode; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.type.*; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class MinusNodeTest { + @Test public void testMonotoneCompute() { + CodeGen code = new CodeGen("return 0;"); + // Type.gather also loads cached fixtures which do not survive later compiler resets. + ArrayList inputs = new ArrayList<>(Arrays.asList( + Type.BOTTOM,Type.CONTROL,Type.NIL,TypeScalar.BOT,TypePtr.PTR, + TypeMemPtr.BOT,TypeFunPtr.BOT,TypeMem.BOT, + TypeConAryB.make(new byte[]{1,2,3}))); + TypeInteger.gather(inputs); + TypeFloat.gather(inputs); + int size = inputs.size(); + for( int i=0; i "+inputs.get(j)+ + " gave "+results[i]+" -> "+results[j],results[i].isa(results[j])); + } + } + } + + @Test public void testUnresolvedInput() { + new CodeGen("return 0;").driver(CodeGen.Phase.Opto); + Node input = new ConstantNode(TypeInteger.TRUE); + MinusNode minus = new MinusNode(input); + assertSame(TypeInteger.constant(-1),minus.compute()); + input._type = Type.BOTTOM; + assertSame(Type.BOTTOM,minus.compute()); + minus.setMode((byte)1); + assertSame(Type.BOTTOM,minus.compute()); + } + + @Test public void testRecursiveFloat() { + CodeGen code = new CodeGen("val _neg = { int x -> x ? -_neg(x-1) : 1.0; }; return _neg(arg);") + .driver(CodeGen.Phase.TypeCheck); + for( int i=0; i<4; i++ ) + assertEquals((i&1)==0 ? "1.0" : "-1.0",Eval2.eval(code,i)); + } +} -- cgit v1.2.3