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 | 41 +++++++++++++++------- .../java/com/seaofnodes/simple/node/FunNode.java | 2 +- .../main/java/com/seaofnodes/simple/node/Node.java | 2 ++ 3 files changed, 32 insertions(+), 13 deletions(-) (limited to 'chapter24b/src/main') diff --git a/chapter24b/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/chapter24b/src/main/java/com/seaofnodes/simple/codegen/Opto.java index 9f07c1d1..e8b7b78d 100644 --- a/chapter24b/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/chapter24b/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; @@ -25,7 +26,9 @@ 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 + Ary oldTypes = new Ary<>(Type.class); + WorkList deps = new WorkList<>(); + WorkList changes = new WorkList<>(); resetToTop(code,oldTypes); // The whole-world assumption: we use it if compiling `main`, and not otherwise. @@ -49,11 +52,13 @@ abstract public class Opto { // OPTIMISTIC INTERPROCEDURAL SCCP - sccp(code, oldTypes); + sccp(code, oldTypes, changes, deps); // 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); } @@ -61,7 +66,7 @@ abstract public class Opto { // Reset Types before running the worklist algorithm private static void resetToTop(CodeGen code, Ary oldTypes ) { code._start.walk( x -> { - oldTypes.setX(x._nid,x._type); // Record original types for asserts + 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. @@ -124,7 +129,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; @@ -133,6 +138,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); // Types start high and always fall Type pesiVal = oldTypes.at(n._nid); @@ -152,6 +159,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(); + } + } } } diff --git a/chapter24b/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter24b/src/main/java/com/seaofnodes/simple/node/FunNode.java index 70e1c200..6a4b6d9e 100644 --- a/chapter24b/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter24b/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -114,7 +114,7 @@ public class FunNode extends RegionNode { } // Upgrade inferred or user-written return type to actual - if( _ret!=null && _ret._type instanceof TypeTuple tt && tt.ret() != _sig.ret() ) { + if( _ret!=null && addDep(_ret)._type instanceof TypeTuple tt && tt.ret() != _sig.ret() ) { setSig(_sig.makeFrom(tt.ret())); return this; } diff --git a/chapter24b/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter24b/src/main/java/com/seaofnodes/simple/node/Node.java index 414530b4..d42b70ed 100644 --- a/chapter24b/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter24b/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() { -- cgit v1.2.3