From 741d78b6e840c88b7b183010c812ad982b342da1 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 10 Aug 2026 11:11:18 -0700 Subject: Chapter 28a: Modules and Lazy Class Initialization Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: Jun Kawasaki Co-authored-by: Claude Opus 5 --- .../java/com/seaofnodes/simple/node/AddFNode.java | 32 -- .../java/com/seaofnodes/simple/node/AddNode.java | 3 +- .../java/com/seaofnodes/simple/node/AndNode.java | 1 + .../com/seaofnodes/simple/node/ArithFNode.java | 31 -- .../java/com/seaofnodes/simple/node/ArithNode.java | 2 + .../java/com/seaofnodes/simple/node/BoolNode.java | 36 +- .../com/seaofnodes/simple/node/BulkMemPhiNode.java | 76 ++-- .../java/com/seaofnodes/simple/node/CFGNode.java | 143 ++++-- .../com/seaofnodes/simple/node/CLInitNode.java | 165 +++++++ .../java/com/seaofnodes/simple/node/CProjNode.java | 18 +- .../com/seaofnodes/simple/node/CallEndMach.java | 6 +- .../com/seaofnodes/simple/node/CallEndNode.java | 421 ++++++++++-------- .../java/com/seaofnodes/simple/node/CallNode.java | 100 +++-- .../java/com/seaofnodes/simple/node/CastMach.java | 19 - .../java/com/seaofnodes/simple/node/CastNode.java | 79 ---- .../com/seaofnodes/simple/node/ConFldOffNode.java | 51 ++- .../com/seaofnodes/simple/node/ConstantNode.java | 57 ++- .../com/seaofnodes/simple/node/ConvertNode.java | 16 +- .../java/com/seaofnodes/simple/node/CtrlNode.java | 1 + .../java/com/seaofnodes/simple/node/DivFNode.java | 27 -- .../java/com/seaofnodes/simple/node/DivNode.java | 1 + .../com/seaofnodes/simple/node/EscapeMach.java | 12 - .../com/seaofnodes/simple/node/EscapeNode.java | 131 ++++-- .../com/seaofnodes/simple/node/ExternNode.java | 20 +- .../seaofnodes/simple/node/ExternOffsetNode.java | 16 + .../java/com/seaofnodes/simple/node/FRefNode.java | 27 +- .../com/seaofnodes/simple/node/FldOffNode.java | 56 ++- .../java/com/seaofnodes/simple/node/FunNode.java | 367 ++++++++++++---- .../com/seaofnodes/simple/node/FunPtrNode.java | 62 ++- .../java/com/seaofnodes/simple/node/GuardNode.java | 4 - .../java/com/seaofnodes/simple/node/IfNode.java | 15 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 243 ++++++----- .../java/com/seaofnodes/simple/node/LoopNode.java | 36 +- .../seaofnodes/simple/node/MachConcreteNode.java | 5 +- .../java/com/seaofnodes/simple/node/MachNode.java | 2 +- .../com/seaofnodes/simple/node/MemMergeNode.java | 199 +++++---- .../java/com/seaofnodes/simple/node/MemOpNode.java | 124 +++--- .../com/seaofnodes/simple/node/MemPhiNode.java | 53 ++- .../com/seaofnodes/simple/node/MinusFNode.java | 32 -- .../java/com/seaofnodes/simple/node/MulFNode.java | 37 -- .../java/com/seaofnodes/simple/node/MulNode.java | 3 +- .../java/com/seaofnodes/simple/node/MultiNode.java | 2 +- .../java/com/seaofnodes/simple/node/NeverNode.java | 3 +- .../java/com/seaofnodes/simple/node/NewNode.java | 108 ++--- src/main/java/com/seaofnodes/simple/node/Node.java | 129 +++--- .../java/com/seaofnodes/simple/node/NotNode.java | 1 - .../java/com/seaofnodes/simple/node/OrNode.java | 1 + .../java/com/seaofnodes/simple/node/ParmNode.java | 80 ++-- .../java/com/seaofnodes/simple/node/PhiNode.java | 149 +++---- src/main/java/com/seaofnodes/simple/node/Proj.java | 2 + .../java/com/seaofnodes/simple/node/ProjNode.java | 11 +- .../com/seaofnodes/simple/node/PtrToIntNode.java | 1 + .../com/seaofnodes/simple/node/ReadOnlyNode.java | 2 +- .../com/seaofnodes/simple/node/RegionNode.java | 16 +- .../com/seaofnodes/simple/node/ReturnNode.java | 139 ++---- .../com/seaofnodes/simple/node/RoundF32Node.java | 1 - .../java/com/seaofnodes/simple/node/SarNode.java | 1 + .../java/com/seaofnodes/simple/node/ScopeNode.java | 481 ++++++++++++++------- .../java/com/seaofnodes/simple/node/ShlNode.java | 3 +- .../java/com/seaofnodes/simple/node/ShrNode.java | 1 + .../java/com/seaofnodes/simple/node/SplitNode.java | 8 +- .../com/seaofnodes/simple/node/StartCUNode.java | 22 + .../java/com/seaofnodes/simple/node/StartNode.java | 82 ++-- .../com/seaofnodes/simple/node/StopCUNode.java | 126 ++++++ .../java/com/seaofnodes/simple/node/StopNode.java | 90 ++-- .../java/com/seaofnodes/simple/node/StoreNode.java | 219 +++++++--- .../com/seaofnodes/simple/node/StructNode.java | 56 --- .../java/com/seaofnodes/simple/node/SubFNode.java | 28 -- .../java/com/seaofnodes/simple/node/SubNode.java | 1 + .../com/seaofnodes/simple/node/ToFloatNode.java | 1 - .../com/seaofnodes/simple/node/ToIntegerNode.java | 1 + .../java/com/seaofnodes/simple/node/TypeNode.java | 32 ++ .../java/com/seaofnodes/simple/node/XCtrlNode.java | 2 +- .../java/com/seaofnodes/simple/node/XorNode.java | 1 + .../seaofnodes/simple/node/cpus/arm/BranchARM.java | 8 +- .../seaofnodes/simple/node/cpus/arm/CallARM.java | 3 +- .../seaofnodes/simple/node/cpus/arm/FloatARM.java | 44 -- .../seaofnodes/simple/node/cpus/arm/FltARM.java | 45 ++ .../seaofnodes/simple/node/cpus/arm/IntARM.java | 7 +- .../seaofnodes/simple/node/cpus/arm/LoadARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/MemOpARM.java | 12 +- .../seaofnodes/simple/node/cpus/arm/NewARM.java | 3 +- .../seaofnodes/simple/node/cpus/arm/SetARM.java | 6 +- .../seaofnodes/simple/node/cpus/arm/SplitARM.java | 12 +- .../simple/node/cpus/arm/SplitFlagsARM.java | 2 +- .../simple/node/cpus/arm/SplitGPRARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/StoreARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/TFPARM.java | 37 +- .../seaofnodes/simple/node/cpus/arm/TMPARM.java | 18 +- .../com/seaofnodes/simple/node/cpus/arm/arm.java | 116 +++-- .../seaofnodes/simple/node/cpus/riscv/AUIPC.java | 11 +- .../simple/node/cpus/riscv/CallRISC.java | 3 +- .../simple/node/cpus/riscv/CallRRISC.java | 2 +- .../seaofnodes/simple/node/cpus/riscv/FltRISC.java | 5 +- .../simple/node/cpus/riscv/Int8RISC.java | 8 +- .../seaofnodes/simple/node/cpus/riscv/IntRISC.java | 2 +- .../simple/node/cpus/riscv/LoadRISC.java | 35 ++ .../simple/node/cpus/riscv/MemOpRISC.java | 41 +- .../seaofnodes/simple/node/cpus/riscv/NewRISC.java | 5 +- .../simple/node/cpus/riscv/SplitRISC.java | 12 +- .../simple/node/cpus/riscv/StoreRISC.java | 8 +- .../seaofnodes/simple/node/cpus/riscv/TFPRISC.java | 31 +- .../seaofnodes/simple/node/cpus/riscv/TMPRISC.java | 12 +- .../seaofnodes/simple/node/cpus/riscv/riscv.java | 119 ++--- .../simple/node/cpus/x86_64_v2/AddFMemX86.java | 2 +- .../simple/node/cpus/x86_64_v2/CallX86.java | 12 +- .../simple/node/cpus/x86_64_v2/CmpMemX86.java | 4 +- .../simple/node/cpus/x86_64_v2/FltX86.java | 7 +- .../simple/node/cpus/x86_64_v2/FunX86.java | 1 + .../simple/node/cpus/x86_64_v2/IntX86.java | 7 +- .../simple/node/cpus/x86_64_v2/LoadX86.java | 4 +- .../simple/node/cpus/x86_64_v2/MemOpX86.java | 8 +- .../simple/node/cpus/x86_64_v2/NewX86.java | 3 +- .../simple/node/cpus/x86_64_v2/SplitFlagsX86.java | 4 +- .../simple/node/cpus/x86_64_v2/SplitX86.java | 17 +- .../simple/node/cpus/x86_64_v2/StoreX86.java | 4 +- .../simple/node/cpus/x86_64_v2/TFPX86.java | 48 +- .../simple/node/cpus/x86_64_v2/TMPX86.java | 21 +- .../simple/node/cpus/x86_64_v2/x86_64_v2.java | 155 ++++--- 119 files changed, 3184 insertions(+), 2255 deletions(-) delete mode 100644 src/main/java/com/seaofnodes/simple/node/AddFNode.java delete mode 100644 src/main/java/com/seaofnodes/simple/node/ArithFNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/CLInitNode.java delete mode 100644 src/main/java/com/seaofnodes/simple/node/CastMach.java delete mode 100644 src/main/java/com/seaofnodes/simple/node/CastNode.java delete mode 100644 src/main/java/com/seaofnodes/simple/node/DivFNode.java delete mode 100644 src/main/java/com/seaofnodes/simple/node/EscapeMach.java create mode 100644 src/main/java/com/seaofnodes/simple/node/ExternOffsetNode.java delete mode 100644 src/main/java/com/seaofnodes/simple/node/MinusFNode.java delete mode 100644 src/main/java/com/seaofnodes/simple/node/MulFNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/Proj.java create mode 100644 src/main/java/com/seaofnodes/simple/node/StartCUNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/StopCUNode.java delete mode 100644 src/main/java/com/seaofnodes/simple/node/StructNode.java delete mode 100644 src/main/java/com/seaofnodes/simple/node/SubFNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/TypeNode.java delete mode 100644 src/main/java/com/seaofnodes/simple/node/cpus/arm/FloatARM.java create mode 100644 src/main/java/com/seaofnodes/simple/node/cpus/arm/FltARM.java (limited to 'src/main/java/com/seaofnodes/simple/node') diff --git a/src/main/java/com/seaofnodes/simple/node/AddFNode.java b/src/main/java/com/seaofnodes/simple/node/AddFNode.java deleted file mode 100644 index 0547e29c..00000000 --- a/src/main/java/com/seaofnodes/simple/node/AddFNode.java +++ /dev/null @@ -1,32 +0,0 @@ -package com.seaofnodes.simple.node; - -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeFloat; - -import java.util.BitSet; - -public class AddFNode extends ArithFNode { - public AddFNode(Node lhs, Node rhs) { super(lhs, rhs); } - public AddFNode(ArithNode n) { super(n); } - - @Override public String label() { return "AddF"; } - - @Override public String glabel() { return "+"; } - - @Override double doOp( double x, double y ) { return x+y; } - - @Override - public Node idealize() { - // Add of 0. - Type t2 = in(2)._type; - if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==0 ) - return in(1); - - // Move constants to RHS: con+arg becomes arg+con - if ( in(1)._type.isConstant() && !t2.isConstant() ) - return swap12(); - - return null; - } - @Override Node copy(Node lhs, Node rhs) { return new AddFNode(lhs,rhs); } -} diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index aa0ee024..8835208b 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -8,6 +8,7 @@ public class AddNode extends ArithNode { public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); } public AddNode(Node lhs, Node rhs, byte mode) { super(null, lhs, rhs, mode); } + @Override public String label() { return "Add"; } @Override public String op() { return "+"; } @@ -41,7 +42,7 @@ public class AddNode extends ArithNode { // Add of same to a multiply by 2 if( lhs==rhs && _mode==1 ) - return new ShlNode(null,lhs,com.seaofnodes.simple.Parser.con(1)); + return new ShlNode(null,lhs,CodeGen.CODE.con(1)); // Goal: a left-spine set of adds, with constants on the rhs (which then fold). diff --git a/src/main/java/com/seaofnodes/simple/node/AndNode.java b/src/main/java/com/seaofnodes/simple/node/AndNode.java index 2bb289e9..a737b703 100644 --- a/src/main/java/com/seaofnodes/simple/node/AndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AndNode.java @@ -7,6 +7,7 @@ import com.seaofnodes.simple.type.TypeInteger; public class AndNode extends ArithNode { public AndNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } + @Override public String op() { return "&"; } @Override long doOp( long x, long y ) { return x & y; } @Override TypeInteger doOp(TypeInteger x, TypeInteger y) { diff --git a/src/main/java/com/seaofnodes/simple/node/ArithFNode.java b/src/main/java/com/seaofnodes/simple/node/ArithFNode.java deleted file mode 100644 index 7d219215..00000000 --- a/src/main/java/com/seaofnodes/simple/node/ArithFNode.java +++ /dev/null @@ -1,31 +0,0 @@ -package com.seaofnodes.simple.node; - -import com.seaofnodes.print.ExprPrinter; - -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeFloat; - -public abstract class ArithFNode extends Node { - public ArithFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } - protected ArithFNode(ArithNode n) { super(n); } - - @Override protected ExprPrinter _print1(ExprPrinter p) { - return p.open().n(in(1)).p(glabel()).n(in(2)).close(); - } - - abstract double doOp(double x, double y); - - @Override - public Type compute() { - Type t1 = in(1)._type, t2 = in(2)._type; - if( t1.isHigh() || t2.isHigh() ) - return Type.TOP; - if( t1 instanceof TypeFloat f1 && - t2 instanceof TypeFloat f2 ) { - if( f1.isConstant() && f2.isConstant() ) - return TypeFloat.constant(doOp(f1.value(),f2.value())); - } - return t1.meet(t2); - } - -} diff --git a/src/main/java/com/seaofnodes/simple/node/ArithNode.java b/src/main/java/com/seaofnodes/simple/node/ArithNode.java index 5f0862b2..094b927f 100644 --- a/src/main/java/com/seaofnodes/simple/node/ArithNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ArithNode.java @@ -95,6 +95,8 @@ public abstract class ArithNode extends Node implements ModeNode { return null; if( unsupportedFloat || n instanceof BoolNode ) return Parser.error("Cannot '"+op+"' "+bad,loc); + if( n.nIns()==3 ) + return Parser.error("Cannot "+n.in(1)._type+" "+op+" "+n.in(2)._type,loc); return Parser.error("Cannot '"+op+"' "+bad,loc); } diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 02421e43..dd0bc996 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -70,7 +70,7 @@ abstract public class BoolNode extends Node implements ModeNode { public Node idealize() { // Compare of same if( in(1)==in(2) ) - return this instanceof LT ? com.seaofnodes.simple.Parser.ZERO : ConstantNode.make(TRUE); + return this instanceof LT ? CodeGen.CODE.ZERO : ConstantNode.make(TRUE); // Can we decide int vs flt? Type t1 = in(1)._type, t2 = in(2)._type; if( t1==null || t2==null ) @@ -116,7 +116,8 @@ abstract public class BoolNode extends Node implements ModeNode { public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } public EQ(Node lhs, Node rhs, byte mode) { super(lhs,rhs, mode); } - public String op() { return "=="; } + + public String op() { return "=="; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( i1==i2 && i1.isConstant() ) return TRUE; if( i1._max < i2._min || i1._min > i2._max ) return FALSE; @@ -129,7 +130,8 @@ abstract public class BoolNode extends Node implements ModeNode { public static class NE extends BoolNode { public NE(Node lhs, Node rhs) { super(lhs,rhs); } public NE(Node lhs, Node rhs, byte mode) { super(lhs,rhs,mode); } - public String op() { return "!="; } + + public String op() { return "!="; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( i1==i2 && i1.isConstant() ) return TRUE; if( i1._max < i2._min || i1._min > i2._max ) return FALSE; @@ -142,7 +144,8 @@ abstract public class BoolNode extends Node implements ModeNode { public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } public LT(Node lhs, Node rhs, byte mode) { super(lhs,rhs, mode); } - public String op() { return "<" ; } + + public String op() { return "<" ; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( i1._max < i2._min ) return TRUE; if( i1._min >= i2._max ) return FALSE; @@ -155,7 +158,8 @@ abstract public class BoolNode extends Node implements ModeNode { public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } public LE(Node lhs, Node rhs, byte mode) { super(lhs,rhs,mode); } - public String op() { return "<="; } + + public String op() { return "<="; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( i1._max <= i2._min ) return TRUE; if( i1._min > i2._max ) return FALSE; @@ -172,7 +176,8 @@ abstract public class BoolNode extends Node implements ModeNode { super(lhs,rhs,(byte)1); assert mode==1; } - public String op() { return "u<" ; } + + public String op() { return "u<" ; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( Long.compareUnsigned(i1._max,i2._min) < 0 ) return TRUE; if( Long.compareUnsigned(i1._min,i2._max) >= 0 ) return FALSE; @@ -180,23 +185,4 @@ abstract public class BoolNode extends Node implements ModeNode { } Node copy(Node lhs, Node rhs) { return new ULT(lhs,rhs); } } - public static class EQF extends EQ { - public EQF(Node lhs, Node rhs) { super(lhs,rhs,(byte)2); } - @Override boolean doOp(double lhs, double rhs) { return lhs == rhs; } - @Override public boolean isFloat() { return true; } - @Override Node copy(Node lhs, Node rhs) { return new EQF(lhs,rhs); } - } - public static class LTF extends LT { - public LTF(Node lhs, Node rhs) { super(lhs,rhs,(byte)2); } - @Override boolean doOp(double lhs, double rhs) { return lhs < rhs; } - @Override public boolean isFloat() { return true; } - @Override Node copy(Node lhs, Node rhs) { return new LTF(lhs,rhs); } - } - public static class LEF extends LE { - public LEF(Node lhs, Node rhs) { super(lhs,rhs,(byte)2); } - @Override boolean doOp(double lhs, double rhs) { return lhs <= rhs; } - @Override public boolean isFloat() { return true; } - @Override Node copy(Node lhs, Node rhs) { return new LEF(lhs,rhs); } - } - } diff --git a/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java index e6f70c64..df9e4fff 100644 --- a/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java @@ -3,7 +3,11 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMem; +import com.seaofnodes.simple.util.Utils; + import java.util.BitSet; +import java.util.HashMap; +import java.util.IdentityHashMap; /** * A Phi for bulk memory. It covers all aliases except {@link #_aliases}; @@ -15,24 +19,31 @@ public class BulkMemPhiNode extends PhiNode { private static final BitSet EMPTY = new BitSet(); // Excluded Aliases; empty means NO exclusions. - // Each split clones the exclusions; published sets are never mutated. - public final BitSet _aliases; + // Directly visible by design. Empty sets share EMPTY; splitAlias performs + // copy-on-first-write and removes the node from GVN before mutation. + public BitSet _aliases; public BulkMemPhiNode(String label, Node... inputs) { this(label,EMPTY,inputs); } private BulkMemPhiNode(String label, BitSet aliases, Node... inputs) { - super(label,inputs); + super(label, inputs); _aliases = aliases; } - public boolean isSplit(int alias) { return _aliases.get(alias); } + public BulkMemPhiNode(BulkMemPhiNode phi) { + super(phi,phi._label); + _aliases = phi._aliases.isEmpty() ? EMPTY : (BitSet)phi._aliases.clone(); + } + + public BulkMemPhiNode(RegionNode r, Node sample) { + super(r,sample); + _aliases = EMPTY; + } - public BulkMemPhiNode(BulkMemPhiNode phi) { super(phi); _aliases = phi._aliases; } + public boolean isSplit(int alias) { return _aliases.get(alias); } - @Override public boolean isMem() { return true; } - @Override public String label() { return "BulkPhi"+_aliases; } @Override public Type compute() { @@ -52,7 +63,7 @@ public class BulkMemPhiNode extends PhiNode { // "Peek through" a MemMerge that covers this alias set on its default for( int i=1; i { assert p._idx==1; yield 0; } case ProjNode proj -> 0; - case ParmNode parm -> 0; - case ConstantNode con -> 0; + case ConstantNode con -> { + assert !(con._con instanceof TypeMem tmem && tmem._alias != 1); + yield 0; + } case MemMergeNode mmm -> missingAlias(mmm); case MemOpNode mem -> unsplit(mem._alias); - case EscapeNode esc -> unsplit(esc._field._alias); case BulkMemPhiNode bulk -> missingAlias(bulk); - default -> throw new AssertionError("Unexpected memory input "+n); + default -> throw Utils.TODO("Should not reach here"); }; } @@ -113,17 +126,18 @@ public class BulkMemPhiNode extends PhiNode { // Normal graph-neighbor enqueueing flows from defs to uses, so retain // an explicit forward dependency to revisit this Phi when the user // sharpens. - addDepForwards(use); + use = addDepForwards(use); return switch(use) { case ScopeNode scope -> 0; + case ParmNode parm -> 0; case MemMergeNode mmm -> missingAlias(mmm); case BulkMemPhiNode bulk -> missingAlias(bulk); case MemOpNode mem -> unsplit(mem._alias); - case EscapeNode esc -> unsplit(esc._field._alias); case MemPhiNode phi -> unsplit(phi._alias); + case EscapeNode esc -> esc.pub()==this ? unsplit(esc.fld()._alias) : 0; default -> { - assert use instanceof ReturnNode || use instanceof CallNode || use instanceof ParmNode - : "Unexpected bulk-memory user "+use; + assert use instanceof ReturnNode || use instanceof CallNode || use instanceof CLInitNode + : "Unexpected bulk-memory user "+use.getClass().getSimpleName()+"#"+use._nid+": "+use; yield 0; } }; @@ -145,9 +159,9 @@ public class BulkMemPhiNode extends PhiNode { return 0; } - // Every explicit slot requests that alias, including a partial allocation - // input whose slot still points to this bulk Phi. - private int missingAlias(MemMergeNode mmm) { + // 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= 0; old = _aliases.nextSetBit(old+1) ) { assert old != alias; mmm.alias(old,precisePhi(old));} mmm.alias(alias,precise); assert checkMerge(mmm); + mmm.init(); + // Slicing changes representation, not the set of values in memory. + // Newly exposed precise inputs can carry conservative bulk escape + // summaries; do not let those invent escapes absent from this Phi. + TypeMem old = (TypeMem)_type; + TypeMem mem = (TypeMem) mmm._type; + mmm._type = TypeMem.make(mem._alias,mem._t,mem._one,mem._clz, + mem._final,old._escFs,old._escAs); return mmm; } @@ -204,14 +226,14 @@ public class BulkMemPhiNode extends PhiNode { mphi = new MemPhiNode("$"+alias,alias); mphi.addDef(region()); // Due to cycles, must set before calling peephole - mphi.setType(TypeMem.make(alias,Type.BOTTOM)); + mphi.setType(TypeMem.BOT.makeFrom(alias)); for( int i=1; i @@ -103,11 +101,79 @@ public abstract class CFGNode extends Node { return lhs; } + // Safe read of the control input of a data node. + public static CFGNode safeCFG(Node n) { + if( n==null ) return null; + if( !(n.in(0) instanceof CFGNode cfg) ) return null; + return cfg._safeCFG(); + } + private CFGNode _safeCFG() { + return switch(this) { + case CLInitNode init when init.bypass() -> init.cfg0()._safeCFG(); + case CallNode call when call.cend()._folding -> call.cfg0()._safeCFG(); + case CallEndNode cend when cend._folding -> cend.cfg(1)._safeCFG(); + case FunNode fun when fun._folding -> fun.cfg(1)._safeCFG(); + case ReturnNode ret when ret.fun()._folding -> ret.cfg0()._safeCFG(); + default -> this; + }; + } + + // True when this node dominates `sub` in the current idom tree. + public boolean dominates(CFGNode sub, Node dep) { + for( CFGNode cfg=sub; cfg!=null; cfg=cfg.idom() ) + if( cfg == this ) + return true; + else if( dep != null ) dep.addDep(cfg); + return false; + } + + public static CFGNode deepest(CFGNode a, CFGNode b) { + if( a == null ) return b; + if( b == null ) return a; + return b.idepth() > a.idepth() ? b : a; + } + + public static CFGNode earlyCFG(Node n) { + return earlyCFG(n,new IdentityHashMap<>(),new BitSet()); + } + + public static CFGNode earlyCFG(Node n, IdentityHashMap cache, BitSet active) { + if( n == null ) return null; + CFGNode cached = cache.get(n); + if( cached != null ) return cached; + if( active.get(n._nid) ) + return safeCFG(n); + active.set(n._nid); + CFGNode early = null; + for( Node x : n._inputs ) + early = deepest(early,defCFG(x,cache,active)); + active.clear(n._nid); + cache.put(n,early); + return early; + } + + private static CFGNode defCFG(Node n, IdentityHashMap cache, BitSet active) { + if( n == null || n.isConst() ) return null; // no impact on early cfg + return switch( n ) { + case PhiNode phi -> phi.region(); + case CFGNode cfg -> cfg; + case ProjNode projNode -> safeCFG( n ); + default -> earlyCFG( n, cache, active ); + }; + } + + public boolean sameFun(CFGNode that) { + FunNode fun = fun(); + return fun != null && fun == that.fun(); + } + // Find nearest enclosing FunNode public FunNode fun() { CFGNode cfg = this; - while( !(cfg instanceof FunNode fun) ) + while( !(cfg instanceof FunNode fun) ) { + if( cfg==null ) return null; cfg = cfg.idom(); + } return fun; } @@ -118,13 +184,13 @@ public abstract class CFGNode extends Node { public LoopTree _ltree; public int _pre; // Pre-order numbers for loop tree finding - static class LoopTree { - LoopTree _par; - final LoopNode _head; - int _depth; + public static class LoopTree { + public LoopTree _par; + public final LoopNode _head; + public int _depth; LoopTree(LoopNode head) { _head = head; } - @Override public String toString() { return "LOOP"+_head._nid; } - int depth() { + @Override public String toString() { return label(_head); } + public int depth() { return _depth==0 ? (_par==null ? 0 : (_depth = _par.depth()+1)) : _depth; } } @@ -133,23 +199,29 @@ public abstract class CFGNode extends Node { // Tag all CFG Nodes with their containing LoopNode; LoopNodes themselves // also refer to *their* containing LoopNode, as well as have their depth. // Start contains the function bodies at depth 0; real loops add depth. - public void buildLoopTree(StartNode start, StopNode stop) { - // Unlink all linked calls. This can remove RPC constants which - // shuffled the StartNode outputs so requires a while loop. - boolean done=false; - while(!done) { - done = true; - for( Node use : start._outputs ) - if( use instanceof FunNode fun ) - for( Node c : fun._inputs ) - if( c instanceof CallNode call ) - { call.unlink_all(); done=false; } + public void buildLoopTree( Ary funs, StopNode stop) { + _ltree = stop._ltree = CodeGen.CODE.XCTRL._ltree = new LoopTree((StartNode)this); + Ary work = new Ary<>(FunNode.class); + + BitSet post = new BitSet(); + int pre = 1; + _pre = pre++; + for( FunNode fun : funs ) { + if( fun!=null && !fun.isDead() && !fun._type.isHigh() ) { + work.push(fun); + if(fun.in(1) instanceof StartCUNode start && start._pre==0 ) { + start._pre = pre++; + start._ltree = start.cfg(1)._ltree = _ltree; + post.set(start._nid); + } + }; } - _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this); - _bltWalk(2,null,stop, new BitSet()); + for( int i=0; i work ) { // Pre-walked? if( _pre!=0 ) return pre; _pre = pre++; @@ -163,8 +235,12 @@ public abstract class CFGNode extends Node { } // Pre-walk for( Node use : _outputs ) - if( use instanceof CFGNode usecfg && !skip( usecfg ) ) - pre = usecfg._bltWalk( pre, use instanceof FunNode fuse ? fuse : fun, stop, post ); + if( use instanceof CFGNode usecfg ) { + if( skip( usecfg ) ) { + if( usecfg._pre==0 && usecfg instanceof FunNode fun2 ) work.add( fun2 ); + } else + pre = usecfg._bltWalk( pre, use instanceof FunNode fuse ? fuse : fun, stop, post, work ); + } // Post-order work: find innermost loop LoopTree inner = null, ltree; @@ -207,7 +283,7 @@ public abstract class CFGNode extends Node { return pre; } - private boolean skip(CFGNode usecfg) { + public boolean skip(CFGNode usecfg) { // Only walk control users that are alive. // Do not walk from a Call to linked Fun's. return usecfg instanceof XCtrlNode || @@ -215,8 +291,13 @@ public abstract class CFGNode extends Node { (this instanceof ReturnNode && usecfg instanceof CallEndNode); } - - public String label( CFGNode target ) { - return (target instanceof LoopNode ? "LOOP" : "L")+target._nid; + public static String label( CFGNode target ) { + return switch(target) { + case StartNode start -> start.label(); + case FunNode fun -> fun.label(); + case LoopNode loop -> "LOOP"+target._nid; + default -> "L"+target._nid; + }; } + } diff --git a/src/main/java/com/seaofnodes/simple/node/CLInitNode.java b/src/main/java/com/seaofnodes/simple/node/CLInitNode.java new file mode 100644 index 00000000..0a0de3cf --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/CLInitNode.java @@ -0,0 +1,165 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.print.ExprPrinter; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.CompUnit; +import com.seaofnodes.simple.type.*; +import java.util.*; + +// Track class initializers - the code just after this point expects the named +// class to be initialized. If this code path dies, then the dependency dies +// also - dead code does not force class init. +// +public class CLInitNode extends CFGNode implements MultiNode { + public Parser.Lexer _loc; // For error reporting + + // Inputs: control, whole memory, class pointer, loaded $init flag + // Results: control, whole memory, known-true flag alias memory. + // For field references, the ptr might be the dst clz ptr or not. + public CLInitNode(Parser.Lexer loc, Node ctrl, Node mem, Node ptr, Node ready) { + super(ctrl,mem,ptr,ready); + _loc = loc; + } + + + public CLInitNode(CLInitNode init) { + super(init); + _loc = init._loc; + } + + public Node mem() { return in(1); } + public Node ptr() { return in(2); } + public Node ready() { return in(3); } + + // The field/alias can be unresolved until forward references are loaded. + public Field flag() { + return ptr()._type instanceof TypeMemPtr tmp && Parser.startsClzPrefix(tmp._obj._name) + ? tmp._obj.field("$init") : null; + } + @Override public String label() { return "CLInit"; } + + // Best effort dst compunit, based on ptr - or null + public CompUnit cu() { + if( !(ptr()._type instanceof TypeMemPtr ptr && Parser.startsClzPrefix(ptr._obj._name)) ) + return null; + // Convert "class:sys.ary" into "sys/ary" and lookup CompUnit + String fname = ptr._obj._name.substring(6).replace(".","/"); + return CodeGen.CODE._compunits.get(fname); + } + + @Override protected ExprPrinter _print1(ExprPrinter p) { + FunNode fun = fun(); + CompUnit cu = cu(); + return p.p("CLInit ").p(fun._name).p(" -> ").p(cu==null ? "---" : cu._cname); + } + + // Block head is Start, Region, CProj, but not e.g. If, Return, Stop + public boolean blockHead() { return true; } + + private boolean instance() { + return ptr()._type==Type.NIL || + (ptr()._type instanceof TypeMemPtr tmp && tmp._obj!=TypeStruct.BOT && + !tmp._obj.isHigh() && !tmp._obj._open && !tmp._obj._fref && + !Parser.startsClzPrefix(tmp._obj._name)); + } + + public boolean bypass() { return instance() || ready()._type==TypeInteger.TRUE; } + + @Override public Type compute() { + if( in(0)._type.isHigh() || ptr()._type.isHigh() ) + return TypeTuple.make(Type.XCONTROL,TypeMem.TOP,TypeMem.TOP); + if( instance() ) + return TypeTuple.make(in(0)._type,mem()._type,mem()._type); + Field flag = flag(); + Type slice = flag==null ? TypeMem.BOT : TypeMem.make(flag._alias,TypeInteger.TRUE); + // The initializer may write arbitrary public memory. Only its flag + // has a guaranteed value on the normal continuation. + Type bulk = ready()._type.isHigh() ? TypeMem.TOP : + ready()._type==TypeInteger.TRUE ? mem()._type : TypeMem.BOT; + return TypeTuple.make(in(0)._type,bulk,slice); + } + + @Override public Node pcopy(int idx, Node dep) { + dep.addDep(ptr()); + dep.addDep(ready()); + if( instance() ) return idx==0 ? in(0) : mem(); + if( ready()._type!=TypeInteger.TRUE ) return null; + if( idx==0 ) return in(0); + if( idx==1 ) return mem(); + // Already established on the incoming path; this is a memory fact, + // not a new store to the class object. + return CodeGen.CODE.con(((TypeTuple)_type)._types[2]); + } + + @Override public Node idealize() { + if( CodeGen.CODE._phase!=CodeGen.Phase.Lower || bypass() || in(0)._type.isHigh() ) return null; + if( CodeGen.CODE._midAssert ) return this; + // Until entry arguments become arrays, ordinary initializers receive zero. + return expand(CodeGen.CODE.con(TypeInteger.ZERO)); + } + + // Called only after cycle/type checking. The initialized arm skips the + // call; both arms rejoin with whole memory and a known-true flag slice. + private Node expand(Node arg) { + FunNode target = CodeGen.CODE.link(cu()); + assert target!=null && !target.isDead(); + keep(); + Node ctrl = in(0); + Node memory = mem(); + + // A child body may assume its parent has finished. Establish that + // requirement first, then test the child's flag in the resulting memory. + CompUnit parent = cu()._par; + if( parent!=null ) { + Node ptr = CodeGen.CODE.con(TypeMemPtr.make((byte)2,parent._clz,true)); + Field flag = parent._clz.field("$init"); + Node off = CodeGen.CODE.con(parent._clz.offset(parent._clz.find("$init"))); + Node parentReady = CodeGen.CODE.add(new LoadNode(_loc,"$init",flag._alias,ctrl,memory,ptr,off).init()); + CLInitNode init = CodeGen.CODE.add(new CLInitNode(_loc,ctrl,memory,ptr,parentReady).init()); + ctrl = CodeGen.CODE.add(new CProjNode(init,0,ScopeNode.CTRL).init()); + memory = CodeGen.CODE.add(new ProjNode(init,1,ScopeNode.MEM0).init()); + } + + Node childOff = CodeGen.CODE.con(cu()._clz.offset(cu()._clz.find("$init"))); + // Read the child's flag after establishing its parent's memory effects. + Node ready = CodeGen.CODE.add(new LoadNode(_loc,"$init",flag()._alias,ctrl,memory,ptr(),childOff).init()); + + IfNode iff = CodeGen.CODE.add(new IfNode(ctrl,ready).init()); + Node done = CodeGen.CODE.add(new CProjNode(iff,0,"True").init()); + Node cold = CodeGen.CODE.add(new CProjNode(iff,1,"False").init()); + + Node fptr = new FunPtrNode(target.sig(),CodeGen.CODE._start,target.ret()).peephole(); + CallNode call = CodeGen.CODE.add(new CallNode(_loc,cold,memory,ptr(),arg,fptr).init()); + CallEndNode end = new CallEndNode(call,TypeRPC.constant(CodeGen.CODE.rpc(_loc._cu._cname))); + // This is a lowered call, after interprocedural analysis. Do not add + // new parameter flows to a body already optimized by SCCP. + CodeGen.CODE.add(end.init()); + Node called = CodeGen.CODE.add(new CProjNode(end,0,ScopeNode.CTRL).init()); + Node after = CodeGen.CODE.add(new ProjNode(end,1,ScopeNode.MEM0).init()); + RegionNode region = CodeGen.CODE.add(new RegionNode(_loc,null,done,called).init()); + Node merged = CodeGen.CODE.add(new BulkMemPhiNode(ScopeNode.MEM0,region,memory,after).init()); + + // Replace the individual outputs; no tuple-pack node or second + // representation of CLInit is needed while the projections collapse. + for( Node use : _outputs.asAry() ) { + if( use==null ) continue; // Our temporary keep. + assert use instanceof Proj; + int idx = ((Proj)use).idx(); + use.subsume(idx==0 ? region : idx==1 ? merged : CodeGen.CODE.con(((TypeTuple)_type)._types[2])); + } + CodeGen.CODE.invalidateIDepthCaches(); + return unkeep(); // Iter removes this now-unused node. + } + + // Resolve a precise flag slice even when the parser did not yet know the + // class/alias and could only install the whole-memory projection. + static Node slice(Node mem, int alias, Node dep) { + if( !(mem instanceof ProjNode proj && proj._idx==1 && proj.in(0) instanceof CLInitNode init) ) + return mem; + dep.addDep(init.ptr()); + Field flag = init.flag(); + if( flag==null || flag._alias!=alias ) return mem; + return new ProjNode(init,2,Parser.memName(alias)).peephole(); + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/CProjNode.java b/src/main/java/com/seaofnodes/simple/node/CProjNode.java index c62de840..2bd48d92 100644 --- a/src/main/java/com/seaofnodes/simple/node/CProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CProjNode.java @@ -2,13 +2,14 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.type.TypeTuple; -import com.seaofnodes.simple.util.Utils; -public class CProjNode extends CFGNode { +import java.util.HashMap; +import java.util.IdentityHashMap; + +public class CProjNode extends CFGNode implements Proj { // Which slice of the incoming multipart value public int _idx; @@ -23,6 +24,7 @@ public class CProjNode extends CFGNode { } public CProjNode(CProjNode c) { super(c); _idx = c._idx; _label = c._label; } + @Override public String label() { return _label; } @Override protected ExprPrinter _print1(ExprPrinter p) { return p.p(_label); } @@ -41,17 +43,17 @@ public class CProjNode extends CFGNode { public Node idealize() { if( ctrl()._type instanceof TypeTuple tt ) { if( tt._types[_idx]==Type.XCONTROL ) - return Parser.XCTRL; // We are dead + return CodeGen.CODE.XCTRL; // We are dead if( ctrl() instanceof IfNode && tt._types[1-_idx]==Type.XCONTROL ) // Only true for IfNodes return ctrl().in(0); // We become our input control } // Flip a negating if-test, to remove the not - if( ctrl() instanceof IfNode iff && addDep(iff.pred()) instanceof NotNode not ) + if( ctrl() instanceof IfNode iff && iff.pred() != null && addDep(iff.pred()) instanceof NotNode not ) return new CProjNode(new IfNode(iff.ctrl(),not.in(1)).peephole(),1-_idx,_idx==0 ? "False" : "True"); // Copy of some other input - return ((MultiNode)ctrl()).pcopy(_idx); + return ((MultiNode)ctrl()).pcopy(_idx,this); } // Only called during basic-block layout, inverts a T/F CProj @@ -66,4 +68,6 @@ public class CProjNode extends CFGNode { @Override int hash() { return _idx; } + @Override public int idx() { return _idx; } + } diff --git a/src/main/java/com/seaofnodes/simple/node/CallEndMach.java b/src/main/java/com/seaofnodes/simple/node/CallEndMach.java index d26ea33b..05707132 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallEndMach.java +++ b/src/main/java/com/seaofnodes/simple/node/CallEndMach.java @@ -14,13 +14,15 @@ public class CallEndMach extends CallEndNode implements MachNode { _retMask = code._mach.retMask(call().tfp()); // Kill mask is all caller-saves, and any mirror stack slots for args // in registers. - RegMaskRW kills = code._callerSave.copy(); + RegMaskRW kills = (call().external() ? code._cCallerSave : code._callerSave).copy(); // Start of stack slots int maxReg = code._mach.regs().length; // Incoming function arg slots, all low numbered in the RA int fslot = fun()._maxArgSlot; // Killed slots for this calls outgoing args - int xslot = code._mach.maxArgSlot(call().tfp()); + int xslot = call().external() + ? code._mach.maxArgSlot(call().tfp(),code._cCallingConv) + : code._mach.maxArgSlot(call().tfp()); _xslot = (maxReg+fslot)+xslot; for( int i=0; i CallEnd -> Add -> Phi -> Return, without - // crossing ParmNode.compute's widening point. Widen here too, - // using the loop rule in PhiNode.compute. Keep constants and - // above-center ranges narrow, and stay within the return type. - Type oldret = _type instanceof TypeTuple tt ? tt.ret() : Type.TOP; - if( ret instanceof TypeInteger ti && ret != oldret && - !ti.isHigh() && !ti.isConstant() && - (!(oldret instanceof TypeInteger oldi) || ti._widen <= oldi._widen) ) - ret = ti.same_but_slightly_wider_than(TypeInteger.BOT).join(tfp.ret()); - } - } - TypeMem mem=TypeMem.TOP; - for( int i=1; i=0; fidx=XInt.next(tfp.fidxs(),fidx) ) { - if( CodeGen.CODE.externFunc(tfp.makeFrom(fidx))!=null ) external=true; - else locals++; + + // Here, if I can figure out I've linked *all* callers, then I can meet + // across the linked returns and join with the function return type. + + // External functions have an exact FIDX but deliberately no local + // FunNode/Return edge. They conservatively crush public memory and + // produce their declared return type. A missing non-external target + // is still an unresolved/error call. + int externs = 0; + // The signature bounds widening (e.g. an i32 result stays i32). + // Use the callee signature, not FunPtrNode's live recursive range. + Type bound = tfp.ret(); + if( !XInt.isHigh(tfp.fidxs()) ) { + bound = Type.TOP; + for( int fidx = XInt.next(tfp.fidxs(),0); fidx >= 0; fidx = XInt.next(tfp.fidxs(),fidx) ) { + if( CodeGen.CODE.externFunc(fidx)!=null ) + externs++; + FunNode fun = CodeGen.CODE._link(fidx); + bound = bound.meet(fun==null ? tfp.ret() : addDep(fun).sig().ret()); } - known=locals==nIns()-1; } - if( external || (ftype instanceof TypeFunPtr tfp && XInt.isHigh(tfp.fidxs())) ) { - // Unknown code may retain arguments and all addresses already - // exposed to it. Heap values are arbitrary after this call; - // exposure itself still has a useful finite summary. - mem=(TypeMem)mem.meet(call.exposed(this)); - } else if( !known && (CodeGen.CODE._phase.ordinal()CodeGen.Phase.FinalizeIR.ordinal()) ) mem=TypeMem.BOT; - return TypeTuple.make(call._type,mem,ret); + boolean hasExtern = externs != 0; + + // If we have an error-call, e.g. wrong args, then we never link. + // Pre-Opto this looks like a missing target fcn, and we assume it will + // appear later - meanwhile, we use a conservative approx of memory + // effects. + if( (nIns()-1)+externs < tfp.nfcns() ) { + // If during Opto, assume call won't be called and thus won't return anything. + // 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(); + // Use the same widening before and after linking a callee. + return TypeTuple.make(Type.CONTROL,tmem,widenResult(ret,bound)); + } + + // A linked function for every concrete function + TypeTuple state = hasExtern + ? TypeTuple.make(Type.CONTROL,call.exposed(this),tfp.ret()) + : TypeTuple.STATE.dual(); + for( int i=1; i CallEnd -> Add -> Phi -> Return, without + // crossing ParmNode.compute's widening point. Widen here too, + // using the loop rule in PhiNode.compute. Keep constants and + // above-center ranges narrow. + if( ret instanceof TypeInteger ti && !ti.isHigh() && !ti.isConstant() ) + ret = ti.same_but_slightly_wider_than().join(bound); + return ret; } @Override public Node idealize() { + return null; + } - // Trivial inlining: call site calls a single function; single function - // is only called by this call site. - if( !_folding && nIns()==2 && in(0) instanceof CallNode call ) { - Node fptr = call.fptr(); - if( fptr.nOuts() == 1 && // Only user is this call - fptr instanceof ConstantNode && // We have an immediate call - // Function is being called, and its not-null - fptr._type instanceof TypeFunPtr tfp && tfp.notNull() && - // Arguments are correct - call.err()==null ) { - ReturnNode ret = (ReturnNode)in(1); - FunNode fun = ret.fun(); - // Expecting Start, and the Call - if( fun.nIns()==3 ) { - assert fun.in(1) instanceof StartNode && fun.in(2)==call; - // Disallow self-recursive inlining (loop unrolling by another name). - // Disallow if still folding other things, as it makes other - // dependency checks carry long chains of half-folded calls. - // Dead control may end the walk before an enclosing function. - CFGNode idom = call; - while( idom!=null ) { - idom = idom.idom(); - if( idom instanceof FunNode ) break; - if( idom instanceof CallEndNode cend && cend._folding ) break; - } - // Inline? - if( idom instanceof FunNode fun2 && fun2 != fun && !fun2._folding ) { - // Trivial inline: rewrite - _folding = true; - // Rewrite Fun so the normal RegionNode ideal collapses - fun._folding = true; - fun.setDef(1,Parser.XCTRL); // No default/unknown StartNode caller - fun.setDef(2,call.ctrl()); // Bypass the Call; - fun.ret().setDef(3,null); // Return is folding also - CodeGen.CODE.addAll(fun._outputs); - // Repeat defs 1 layer down, for users of Parm (Phis) - for( Node parm : fun._outputs ) - if( parm instanceof ParmNode ) - CodeGen.CODE.addAll(parm._outputs); - - // Inlining immediately blows all cache idepth fields past the inline point. - // Bump the global version number invalidating them en-masse. - CodeGen.CODE.invalidateIDepthCaches(); - return this; - } else if( idom!=null ) { - addDep(idom); - } - } else { - addDep(fun); - } - } else { // Function ptr has multiple users (so maybe multiple call sites) - addDep(fptr); - } - } + public byte maybeInline() { + byte inline = inlineCandidate(); + if( CodeGen.CODE._midAssert ) + return inline; + _inline = inline; + if( _inline > 0 ) + doInline(); - return null; + return _inline; } - // Clone only tiny, straight-line boilerplate, after ordinary peeps settle. - // Larger bodies still use the existing single-caller, non-cloning inline. - public boolean inlineSmall() { - if( isDead() || _folding || nIns()!=2 || !(in(0) instanceof CallNode call) ) return false; - Node fptr = call.fptr(); - if( !(fptr instanceof ConstantNode) || - !(fptr._type instanceof TypeFunPtr tfp && tfp.notNull() && tfp.isConstant()) ) - { addDep(fptr); return false; } - if( call.err()!=null ) return false; + // Check if candidate right now, sets no flags + private byte inlineCandidate() { + if( _inline < -2 ) return -2; // Never + if( _folding ) return -2; // No, and will collapse anyways + if( !(in(0) instanceof CallNode call) ) return -2; // malformed because mid-death + + if( nIns()!=2 ) return -1; // Not exactly 1 link, but can change + + // Have exactly 1 linked function ReturnNode ret = (ReturnNode)in(1); FunNode fun = ret.fun(); - if( fun._folding ) return false; - int len = smallBody(fun); - if( len==0 ) return false; - // All callers consume the three normal return projections. - for( Node use : _outputs ) - if( !((use instanceof ProjNode p && p._idx>=0 && p._idx<3) || - (use instanceof CProjNode cp && cp._idx==0)) ) return false; - - // Substitute control and arguments directly; no new function identity, - // parameter Phis, or return address is needed for this straight line. - Node[] copy = new Node[len]; - for( int i=0; i1 ) { - Node use = out(0)==null ? out(1) : out(0); - int idx = use instanceof ProjNode p ? p._idx : ((CProjNode)use)._idx; - CodeGen.CODE.addAll(use._outputs); - use.subsume(result[idx]); - } - unkill(); - for( Node n : result ) n.unkill(); - CodeGen.CODE.invalidateIDepthCaches(); - return true; - } - private static Node mapped(Node n, Node[] copy) { - for( int i=0; i= maxSize ) { + if( !smallBody(fun) ) return -1; + } else if( fun.body().cardinality() >= maxSize ) // Expensive size check + return -1; // Try later (if cleanup makes the real body small enough) + + // Can be cloned but not trivial + if( fun.nIns() > 2 ) { addDep(fun); return 2; } + + // A trivial candidate right now + return 1; } - // Bounded recognition of initializer boilerplate. Walk uses from the entry - // and stop at Return, never following callers or constant inputs. This also - // avoids scanning sparse MemMerge input arrays while a large body shrinks. - // Watch this small prefix, including an unsupported node that may fold. + // Bounded, conservative recognition of straight-line initializer boilerplate. + // Walk uses from the entry and stop at Return, never following callers or + // constant inputs. This also avoids scanning sparse MemMerge input arrays. + // Watch only this small prefix, including an unsupported node that may fold. private static final Node[] TINYBODY = new Node[15]; // Tiny worklist - private int smallBody(FunNode fun) { + private boolean smallBody(FunNode fun) { ReturnNode ret = fun.ret(); for( Node in : ret._inputs ) if( in!=null ) addDep(in); - if( ret.ctrl()!=fun ) return 0; + if( ret.ctrl()!=fun ) return false; TINYBODY[0] = fun; int len=1; for( int i=0; iTINYBODY.length ) return 0; + !(n instanceof StoreNode) && !(n instanceof MemMergeNode) ) + return false; // Something unexpected + if( n.nOuts()>TINYBODY.length ) return false; // Too big for( Node use : n._outputs ) { if( use==null ) continue; int j=0; while( j 0; // Only called when possible to inline + + ReturnNode ret = (ReturnNode)in(1); + FunNode fun = ret.fun(); + CallNode call = call(); + assert fun.sig().isa(call.fptr()._type); + + // Clone first + if( _inline==2 ) { + assert !CodeGen.CODE._midAssert; // Triggered inlining + // Remove the existing function linkage + call.unlink_all(); + // Clone the function body + FunNode fun2 = fun.copyBody(); + // Call uses the unique new function + Node fptr2 = new FunPtrNode(fun2.sig(),CodeGen.CODE._start,fun2.ret()).peephole(); + call.setDef(call.nIns()-1,fptr2); + // Link to the new function + call.link(fun2); + fun = fun2; + } + + // Trivial inlining: call site calls a single function; single function + // is only called by this call site. + doTrivialInlining(fun); + } + + boolean goodArgs( CallNode call, TypeFunPtr tfp ) { + for( int i=0; i _print1(ExprPrinter p) { String fname = name(); @@ -40,13 +38,12 @@ public class CallNode extends CFGNode { if( fptr()._type instanceof TypeFunPtr tfp && tfp._isConstant() && tfp.notNull() ) { FunNode fun = CodeGen.CODE._link(tfp); if( fun !=null ) return fun._name; - return CodeGen.CODE.externFunc(tfp); + if( fptr() instanceof ExternNode ex ) return ex._extern; } return null; } - Node ctrl() { return in(0); } Node mem () { return in(1); } // Args mapped 1-to-1 on inputs, so conceptually start at 2 @@ -63,12 +60,12 @@ public class CallNode extends CFGNode { if( !(fptr()._type instanceof TypeFunPtr tfp) ) return false; if( XInt.isHigh(tfp.fidxs()) ) return true; for( int fidx=XInt.next(tfp.fidxs(),-1); fidx>=0; fidx=XInt.next(tfp.fidxs(),fidx) ) - if( CodeGen.CODE.externFunc(tfp.makeFrom(fidx))!=null ) return true; + if( CodeGen.CODE.externFunc(fidx)!=null ) return true; return false; } - // Unknown code can retain arguments without ever returning. Stop uses - // this summary directly as well as through the call's memory result. + // As in the escape chapter, native code may retain an argument even if + // this path never returns. StopCU reads this independently of CallEnd. TypeMem exposed(Node dep) { dep.addDepForwards(this); dep.addDepForwards(fptr()); @@ -76,7 +73,7 @@ public class CallNode extends CFGNode { Type input=dep.addDepForwards(mem())._type; TypeMem escaped=input instanceof TypeMem m ? m : input.isHigh() ? TypeMem.TOP : TypeMem.BOT; for( int i=2; i= CodeGen.Phase.Lower.ordinal() ) return null; CallEndNode cend = cend(); if( cend==null ) return null; // Still building - if( _method!=null ) { - if( !(arg(2)._type instanceof com.seaofnodes.simple.type.TypeMemPtr ptr) ) return null; - var field=ptr._obj.field(_method); - if( field==null ) return null; - if( !(fptr()._type instanceof TypeFunPtr sig) ) return null; - if( !field._final || CodeGen.CODE.externFunc(sig)!=null ) delDef(2); - _method=null; - return this; - } // Link: call calls target function. Linking makes the target FunNode // point to this Call, and all his Parms point to the call arguments; @@ -131,11 +122,9 @@ public class CallNode extends CFGNode { // If fidxs is negative, then infinite unknown functions int[] fidxs = tfp.fidxs(); if( !XInt.isHigh(fidxs) ) { - // Wipe out the return which matching in the linker table - // Walk the function identities and link each possible callee. - for( int fidx=XInt.next(fidxs,-1); fidx>=0; fidx=XInt.next(fidxs,fidx) ) { - TypeFunPtr tfp0 = tfp.makeFrom(fidx); - FunNode fun = CodeGen.CODE.link(tfp0); + // Walk the bits and link + for( int fidx = XInt.next(fidxs,0); fidx > 0; fidx = XInt.next(fidxs,fidx) ) { + FunNode fun = CodeGen.CODE.link(fidx); if( fun!=null && !fun._folding && !linked(fun) ) progress = link(fun); } @@ -156,35 +145,58 @@ public class CallNode extends CFGNode { // Link so this calls fun public Node link( FunNode fun ) { assert !linked(fun); - fun.addDef(this); + CodeGen.CODE.add(fun).addDef(this); for( Node use : fun._outputs ) - if( use instanceof ParmNode parm ) - parm.addDef(parm._idx==0 ? new ConstantNode(cend()._rpc).peephole() : arg(parm._idx)); + if( use instanceof ParmNode parm ) { + Node def = parm._idx==0 ? ConstantNode.seed(cend()._rpc).peephole() : arg(parm._idx); + CodeGen.CODE.add(parm).addDef(def); + // Linking can happen during post-SCCP inlining. Keep an RPC + // Parm's cached finite set synchronized with its newly added + // input instead of waiting for the next worklist visit. + if( parm._idx==0 && parm._type instanceof TypeRPC ) + parm._type = parm._type.meet(def._type); + } // Call end points to function return CodeGen.CODE.add(cend()).addDef(fun.ret()); return this; } + // Unlink a single function + public void unlink( FunNode fun, int path ) { + assert linked(fun); + for( Node use : fun._outputs ) + if( use instanceof ParmNode ) + use.delDef(path); + fun.delDef(path); + CodeGen.CODE.add(fun); + CallEndNode cend = cend(); + ReturnNode ret = fun.ret(); + if( cend != null ) { + ret.keep(); + cend.delDef(cend._inputs.find(ret)); + CodeGen.CODE.add(cend); + ret.unkeep(); + } + assert !linked(fun); + } + + // Unlink all linked functions public void unlink_all() { for( int i=0; i<_outputs._len; i++ ) if( out(i) instanceof FunNode fun ) { - assert linked(fun); - int idx = fun._inputs.find(this); - for( Node use : fun._outputs ) - if( use instanceof ParmNode ) - use.delDef(idx); - fun.delDef(idx); - cend().delDef(cend()._inputs.find(fun.ret())); - assert !linked(fun); + int path = fun._inputs.find(this); + unlink(fun,path); i--; } } @Override public Parser.ParseException err() { + if( fptr()._type == Type.BOTTOM ) + return null; // Wrong, but failing earlier if( !(fptr()._type instanceof TypeFunPtr tfp) ) - throw Utils.TODO(); + return Parser.error("Expected a function, but found " + fptr()._type, _loc); if( !tfp.notNull() ) return Parser.error( "Might be null calling "+tfp, _loc); if( nargs() != tfp.nargs() ) @@ -193,11 +205,13 @@ public class CallNode extends CFGNode { // Check for args for( int i=0; i