From 07a87b4461015dd81f1d40cef1e2378882c86479 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Wed, 28 Oct 2026 11:49:32 -0700 Subject: Opto loses 2 whole-graph walks Move changes to worklist actually moves only changes. Numeric modes also moves numerics-only to worklist. Fix monotonicity bug in MinusNode --- .../java/com/seaofnodes/simple/codegen/Opto.java | 90 +++++++++++++--------- .../java/com/seaofnodes/simple/node/MinusNode.java | 24 +++--- .../main/java/com/seaofnodes/simple/node/Node.java | 2 + .../java/com/seaofnodes/simple/MinusNodeTest.java | 65 ++++++++++++++++ 4 files changed, 131 insertions(+), 50 deletions(-) create mode 100644 chapter28b/src/test/java/com/seaofnodes/simple/MinusNodeTest.java (limited to 'chapter28b/src') diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Opto.java index 440ffabb..e288d838 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.IterPeeps.WorkList; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; @@ -25,30 +26,39 @@ abstract public class Opto { // FunNodes. 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); unlinkStart(code); // OPTIMISTIC INTERPROCEDURAL SCCP - sccp(code, oldTypes); + sccp(code, oldTypes, changes, deps); - // SCCP can leave a recursive numeric component at BOTTOM with no - // arithmetic mode selected. Resolve the whole component from all - // available int/float evidence before IterPeeps consumes the types. - resolveNumericModes(code); + // Settle unresolved modes using SCCP's int/float evidence. Some + // computes wait at TOP until a mode is known; others already return + // BOTTOM and stay there. Resume SCCP only on the affected nodes; + // types are not reset, and any further changes must still fall. + resolveNumericModes(code,modes); if( !code._iter._work.isEmpty() ) - sccp(code, oldTypes); + sccp(code, oldTypes, changes, deps); + Node dep; + while( (dep=deps.pop())!=null ) code.add(dep); // After SCCP add everything changed to the worklist and see if // peepholes can make more progress. - moveChangesToWorklist(code, oldTypes); + 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. Gather unresolved modes on this required walk. + 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 return null; @@ -156,7 +166,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; @@ -166,6 +176,9 @@ abstract public class Opto { count++; Type oval = n._type, nval = n.compute(); if( n instanceof CLInitNode init ) init.link(); + // Remember possible peephole work without walking the graph again. + // SCCP can still fall back to the old type, so filter at the end. + if( nval!=oldTypes.atX(n._nid) || n.isUnlocked() ) changes.push(n); if( oval == nval ) continue; assert oval.isa(nval) : "Non-monotonic SCCP: "+n.getClass().getSimpleName()+"#"+n._nid+" "+n+" old="+oval+" new="+nval; // Types start high and always fall Type pesiVal = oldTypes.atX(n._nid); @@ -205,6 +218,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.add(x); - return null; - }); + // Types can stay unchanged while SCCP edits edges or numeric modes. Such + // edits unlock the node from GVN. Revisit both kinds of change and their + // neighbors; distant dependencies consumed by SCCP were saved separately. + 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.addAll(n); + 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; @@ -265,17 +287,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/chapter28b/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index e84eb611..9c99fc6b 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter28b/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.BAOS; import com.seaofnodes.simple.util.Utils; @@ -33,28 +32,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/chapter28b/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/Node.java index 8718f351..0c704a7d 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -643,6 +643,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/chapter28b/src/test/java/com/seaofnodes/simple/MinusNodeTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/MinusNodeTest.java new file mode 100644 index 00000000..f7fbde03 --- /dev/null +++ b/chapter28b/src/test/java/com/seaofnodes/simple/MinusNodeTest.java @@ -0,0 +1,65 @@ +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;"); + ArrayList inputs = new ArrayList<>(Arrays.asList(Type.gather())); + for( long value : new long[]{Long.MIN_VALUE,Long.MIN_VALUE+1,-1,1,Long.MAX_VALUE} ) + inputs.add(TypeInteger.constant(value)); + for( double value : new double[]{-0.0,0.0,-1.0,1.0,Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + Type[][] expected = new Type[3][inputs.size()]; + for( CodeGen.Phase phase : new CodeGen.Phase[]{CodeGen.Phase.Parse,CodeGen.Phase.Iter,CodeGen.Phase.Opto,CodeGen.Phase.IterPostOpto} ) { + code.driver(phase); + for( byte mode=0; mode<3; mode++ ) { + // An isolated analysis input: vary its type without peepholes + // selecting a mode or folding the node under test. + Node input = ConstantNode.seed(Type.BOTTOM); + input.setDef(0,null); + MinusNode minus = new MinusNode(input,mode); + Type[] results = new Type[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 = ConstantNode.seed(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