summaryrefslogtreecommitdiff
path: root/chapter25/src
diff options
context:
space:
mode:
authorCliff Click <cliffc@acm.org>2026-09-10 12:39:12 -0700
committerCliff Click <cliffc@acm.org>2026-09-10 12:39:12 -0700
commit6f920fae07f899672b04458b0f80a5119dcdef96 (patch)
tree2c51a2c4614127ea238dbd922222fc3285ea8848 /chapter25/src
parent1f4006e88df54e2b7086bc49e05ffc6d2068e8fd (diff)
downloadSimple-6f920fae07f899672b04458b0f80a5119dcdef96.tar.gz
Simple-6f920fae07f899672b04458b0f80a5119dcdef96.zip
Cleanup coverage issues
A lot of tests become asserts; general cleanup in MemOps and PhiOps
Diffstat (limited to 'chapter25/src')
-rw-r--r--chapter25/src/main/java/com/seaofnodes/simple/Parser.java2
-rw-r--r--chapter25/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java46
-rw-r--r--chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java119
-rw-r--r--chapter25/src/main/java/com/seaofnodes/simple/node/LoopNode.java2
-rw-r--r--chapter25/src/main/java/com/seaofnodes/simple/node/MemOpNode.java2
-rw-r--r--chapter25/src/main/java/com/seaofnodes/simple/node/ParmNode.java25
-rw-r--r--chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java63
-rw-r--r--chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java140
-rw-r--r--chapter25/src/main/java/com/seaofnodes/simple/type/TypeInteger.java4
-rw-r--r--chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java9
10 files changed, 158 insertions, 254 deletions
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/Parser.java b/chapter25/src/main/java/com/seaofnodes/simple/Parser.java
index 7f02080e..b6feb809 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/Parser.java
@@ -1874,7 +1874,7 @@ public class Parser {
*/
private Node parsePrimary() {
if( _lexer.isNumber(_lexer.peek()) ) return parseLiteral();
- if( _lexer.peek('"') ) return newString(parseString());
+ if( _lexer.peek('"') ) return parsePostfix(newString(parseString()));
if( matchx("true" ) ) return con(1);
if( matchx("false") ) return _code.ZERO;
if( matchx("null" ) ) return con(Type.NIL);
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java
index 68f0ecee..d261a2b5 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java
@@ -46,19 +46,6 @@ public class BulkMemPhiNode extends PhiNode {
public boolean isSplit(int alias) { return _aliases.get(alias); }
- /**
- * Record that an alias has been split out. The graph rewrite installing
- * its parallel precise Phi must happen before this semantic change.
- */
- public void splitAlias(int alias) {
- assert alias > 1;
- if( _aliases.get(alias) ) return;
- unlock();
- if( _aliases==EMPTY )
- _aliases = new BitSet();
- _aliases.set(alias);
- }
-
@Override public Tag serialTag() { return Tag.BulkMemPhi; }
@Override
@@ -94,13 +81,8 @@ public class BulkMemPhiNode extends PhiNode {
public Node idealize() {
Node progress = super.idealize();
if( progress != null ) return progress;
-
- if( !(region() instanceof RegionNode r ) )
- return in(1); // Input has collapse to e.g. starting control.
- if( r.inProgress() || r.nIns()<=1 )
+ if( ((RegionNode)region()).inProgress() || region().nIns()<=1 )
return null; // Input is in-progress
- if( nOuts()==0 ) return null;
- if( nIns() <= 2 ) return null;
// "Peek through" a MemMerge that covers this alias set on its default
for( int i=1; i<nIns(); i++ )
@@ -150,8 +132,6 @@ public class BulkMemPhiNode extends PhiNode {
private int inputAlias(Node n) {
return switch(n) {
case ParmNode p -> { assert p._idx==1; yield 0; }
- case ScopeNode scope -> 0;
- case ReturnNode ret -> 0;
case ProjNode proj -> 0;
case ConstantNode con -> {
assert !(con._con instanceof TypeMem tmem && tmem._alias != 1);
@@ -160,7 +140,7 @@ public class BulkMemPhiNode extends PhiNode {
case MemMergeNode mmm -> missingAlias(mmm,false);
case MemOpNode mem -> unsplit(mem._alias);
case BulkMemPhiNode bulk -> missingAlias(bulk);
- default -> throw Utils.TODO();
+ default -> throw Utils.TODO("Should not reach here");
};
}
@@ -174,7 +154,7 @@ public class BulkMemPhiNode extends PhiNode {
return switch(use) {
case ScopeNode scope -> 0;
case ParmNode parm -> 0;
- case MemMergeNode mmm -> mmm.in(1)==this ? missingAlias(mmm,true) : 0;
+ case MemMergeNode mmm -> missingAlias(mmm,true);
case BulkMemPhiNode bulk -> missingAlias(bulk);
case MemOpNode mem -> unsplit(mem._alias);
case MemPhiNode phi -> unsplit(phi._alias);
@@ -190,7 +170,9 @@ public class BulkMemPhiNode extends PhiNode {
// Alias zero/one is bulk, and an already excluded precise alias cannot
// trigger another split of this Phi.
private int unsplit(int alias) {
- return alias <= 1 || _aliases.get(alias) ? 0 : alias;
+ if( alias <= 1 ) return 0;
+ assert !_aliases.get(alias);
+ return alias;
}
// First alias excluded by the neighboring bulk Phi but not by this one.
@@ -207,9 +189,8 @@ public class BulkMemPhiNode extends PhiNode {
for( int alias=2; alias<mmm.nIns(); alias++ )
if( mmm.in(alias)!=null &&
mmm.alias(alias)!=mmm.in(1) &&
- (!user || mmm.in(alias)!=this) &&
!_aliases.get(alias) )
- return alias;
+ { assert (!user || mmm.in(alias)!=this); return alias; }
return 0;
}
@@ -250,17 +231,17 @@ public class BulkMemPhiNode extends PhiNode {
MemMergeNode aggregate(Node bulk, int alias, Node precise) {
MemMergeNode mmm = new MemMergeNode(null,bulk);
for( int old = _aliases.nextSetBit(0); old >= 0; old = _aliases.nextSetBit(old+1) )
- if( old != alias )
- mmm.alias(old,precisePhi(old));
+ { 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.
- if( _type instanceof TypeMem old && mmm._type instanceof TypeMem mem )
- mmm._type = TypeMem.make(mem._alias,mem._t,mem._one,mem._clz,
- mem._final,old._escFs,old._escAs);
+ 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;
}
@@ -304,8 +285,7 @@ public class BulkMemPhiNode extends PhiNode {
private Node preciseInput(Node mem, int alias) {
if( mem instanceof MemMergeNode mmm )
return mmm.alias(alias);
- if( mem instanceof BulkMemPhiNode bulk && bulk.isSplit(alias) )
- return bulk.precisePhi(alias);
+ assert !(mem instanceof BulkMemPhiNode bulk) || !bulk.isSplit(alias);
return mem;
}
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java
index 73c288e6..10adeb3c 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java
@@ -41,17 +41,19 @@ public class LoadNode extends MemOpNode {
@Override
public Type compute() {
- Type mem0 = aliasMem()._type;
+ Type mem0 = mem()._type;
Type ptr0 = ptr()._type;
// Validate argument types
if( ptr0.isHigh() )
return TypeScalar.TOP;
if( !(mem0 instanceof TypeMem mem) )
return mem0.isHigh() ? TypeScalar.TOP : TypeScalar.BOT;
+ if( mem._t == Type.TOP )
+ return TypeScalar.TOP;
if( ptr0 == Type.NIL )
return TypeScalar.TOP;
if( !(ptr0 instanceof TypeMemPtr ptr) )
- return mem0.isHigh() ? TypeScalar.TOP : scalar(mem._t);
+ return scalar(mem._t);
// Load field from object
TypeMemPtr tmp = ptr;
@@ -65,19 +67,8 @@ public class LoadNode extends MemOpNode {
// Load member of constant array
if( t instanceof TypeConAry ary )
t = ary.elem(); // TODO: if offset is known, can peek the constant
-
- // Now, do the same for memory
- if( mem._t instanceof TypeStruct ts ) {
- assert ts._name==tmp._obj._name;
- Field mfld = ts.field(_name);
- // Lift from declared type and memory input
- if( mfld != null )
- t = t.join(mfld._t);
- } else if( mem._alias==_alias ) {
+ if( mem._alias==_alias )
t = t.join(mem._t);
- } else if( mem._t == Type.TOP ) {
- return TypeScalar.TOP;
- }
// A deeply read-only base produces a deeply read-only value. The
// generic declared field type must not cast this information away.
@@ -95,13 +86,13 @@ public class LoadNode extends MemOpNode {
@Override
public Node idealize() {
+ Node mem = mem();
Node ptr = ptr();
- Node mem = aliasMem();
// Loads into structs do not need a ctrl edge, as null-ptr checking is
// baked into the type system. Loads into arrays DO need the ctrl
// edge, at least until proper range-checking is in place.
- if( in(0)!=null && ptr()._type instanceof TypeMemPtr tmp &&
+ if( in(0)!=null && ptr._type instanceof TypeMemPtr tmp &&
!tmp._obj.isAry() ) {
setDef(0,null);
return this;
@@ -109,23 +100,24 @@ public class LoadNode extends MemOpNode {
// Forward-ref loads eventually sharpen to a declared type
Field fld;
- if( ptr()._type instanceof TypeMemPtr tmp &&
+ if( ptr._type instanceof TypeMemPtr tmp &&
(fld=tmp._obj.field(_name)) != null &&
_alias != fld._alias) {
assert _alias==1 || _alias == fld._alias;
+ assert !tmp._obj._open && !tmp._obj._fref;
unlock(); // Alias participates in GVN semantics
_alias = fld._alias;
- // Bulk memory may already have inspected this user. Revisit it
- // once the declaring shape is stable; an open forward reference
- // can still change this Load's semantics.
- if( !tmp._obj._open && !tmp._obj._fref )
- CodeGen.CODE.add(mem());
return this;
}
// Must sharpen alias first
if( _alias == 1 )
return null;
+ if( mem instanceof MemMergeNode merge ) {
+ setDef(1,merge.alias(_alias));
+ return this;
+ }
+
// Simple Load-after-Store on same address.
if( mem instanceof StoreNode st &&
ptr == st.nnptr() &&
@@ -134,21 +126,22 @@ public class LoadNode extends MemOpNode {
return extend(st.val());
}
- // Expose the same effective memory input already observed by compute.
- if( mem != mem() ) {
- for( Node ld : mem._outputs )
- if( ld instanceof LoadNode )
- CodeGen.CODE.add(ld);
- if( mem instanceof BulkMemPhiNode ) CodeGen.CODE.add(mem);
- setDef(1,mem);
- return this;
- }
+ //// Expose the same effective memory input already observed by compute.
+ //if( mem != mem() ) {
+ // for( Node ld : mem._outputs )
+ // if( ld instanceof LoadNode )
+ // CodeGen.CODE.add(ld);
+ // if( mem instanceof BulkMemPhiNode ) CodeGen.CODE.add(mem);
+ // setDef(1,mem);
+ // return this;
+ //}
// Uplift control to a prior dominating load.
for( Node memuse : mem._outputs )
// Find a prior load, has same mem,ptr,off but higher ctrl
if( memuse != this && memuse instanceof LoadNode ld && ptr==ld.ptr() && off()==ld.off() &&
- cfg0()!=null && cfg0()._idom(ld.cfg0(),this) == ld.cfg0() ) // Higher control means load is legal earlier
+ cfg0()!=null && cfg0()._idom(ld.cfg0(),this) == ld.cfg0() && // Higher control means load is legal earlier
+ addDep(ld)._type.isa(_type) ) // and not rolling backwards
return ld;
// Load-after-Store on same address, but bypassing provably unrelated
@@ -176,28 +169,29 @@ public class LoadNode extends MemOpNode {
// Assume related
addDep(phi);
break outer;
- case ConstantNode con:
- // Load from constant memory
- if( con._con instanceof TypeMem tmem )
- return ConstantNode.make(tmem._t);
- break outer; // Assume shortly dead
+ //case ConstantNode con:
+ // // Load from constant memory
+ // if( con._con instanceof TypeMem tmem )
+ // return ConstantNode.make(tmem._t);
+ // break outer; // Assume shortly dead
case ProjNode mproj: // Memory projection
switch( mproj.in(0) ) {
case NewNode nnn1:
// Direct load from e.g. new array elements
assert _name=="[]";
Type decl = declaredType();
- return decl==Type.BOTTOM ? null : ConstantNode.make(decl.makeZero());
- case StartNode start: break outer;
+ assert decl!=Type.BOTTOM;
+ return ConstantNode.make(decl.makeZero());
case CallEndNode cend: addDep(mproj); break outer; // TODO: Bypass no-alias call
- default: throw Utils.TODO();
+ default: throw Utils.TODO("Should not reach here");
}
case MemMergeNode merge: mem = merge.alias(_alias); break;
case EscapeNode esc:
if( esc.self()==ptr ) // Proved equal
{ mem = esc.priv(); break; }
// Two NewNodes are always unequal
- if( esc.self().in(0) instanceof NewNode && ptr.in(0) instanceof NewNode )
+ assert esc.self().in(0) instanceof NewNode;
+ if( ptr.in(0) instanceof NewNode )
{ mem = esc.pub(); break; }
// TODO: Can we prove unequal?
break outer;
@@ -214,7 +208,7 @@ public class LoadNode extends MemOpNode {
// if( pred ) ptr.x = e0; val = pred ? e0
// else ptr.x = e1; : e1;
// val = ptr.x; ptr.x = val;
- if( mem() instanceof PhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 &&
+ if( mem instanceof PhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 &&
// Offset can be hoisted
off() instanceof ConstantNode &&
// Not control dependent
@@ -226,10 +220,6 @@ public class LoadNode extends MemOpNode {
if( profit(memphi,2) ||
// Else must not be a loop to count profit on LHS.
(!(memphi.region() instanceof LoopNode) && profit(memphi,1)) ) {
- // profit() peepholes inputs and can restore a required control
- // edge. Recheck before manufacturing control-free loads.
- if( in(0)!=null )
- return null;
Node ld1 = ld(1);
Node ld2 = ld(2);
PhiNode phi = new PhiNode(_name, memphi.region(),ld1,ld2);
@@ -241,19 +231,11 @@ public class LoadNode extends MemOpNode {
return null;
}
- // Semantic memory input for this Load. Compute defines behavior from
- // this view; ideal merely exposes the same edge in the graph.
- private Node aliasMem() {
- Node mem = mem();
- return _alias != 1 && mem instanceof MemMergeNode merge
- ? merge.alias(_alias)
- : mem;
- }
-
private Node ld( int idx ) {
Node mem = mem(), ptr = ptr();
assert in(0)==null;
- return new LoadNode(_loc,_name,_alias,null,mem.in(idx),ptr instanceof PhiNode && ptr.in(0)==mem.in(0) ? ptr.in(idx) : ptr, off()).peephole();
+ assert !(ptr instanceof PhiNode && ptr.in(0)==mem.in(0)); // If fails, need to use pre-merged ptr at same phi
+ return new LoadNode(_loc,_name,_alias,null,mem.in(idx),ptr, off()).peephole();
}
private static boolean neverAlias( Node ptr1, Node ptr2 ) {
@@ -283,13 +265,13 @@ public class LoadNode extends MemOpNode {
}
// Profitable if we find a matching Store on this Phi arm.
- private boolean profit(PhiNode phi, int idx) {
- Node px = phi.in(idx);
+ private boolean profit(PhiNode memphi, int idx) {
+ Node px = memphi.in(idx);
if( px==null ) return false;
- if( px._type instanceof TypeMem mem && mem._t.isHighOrConst() )
- // To avoid cyclic pushing a Load up then down, getting here means
- // the load *must* replace with the high/constant.
- return true;
+ assert !(px._type instanceof TypeMem mem && mem._t.isHighOrConst() );
+ //// To avoid cyclic pushing a Load up then down, getting here means
+ //// the load *must* replace with the high/constant.
+ //return true;
if( px instanceof StoreNode st1 && ptr()==addDep(st1.nnptr() )&& off()==st1.off() )
// To avoid cyclic pushing a Load up then down, getting here means
// the load *must* match against the Store
@@ -314,19 +296,14 @@ public class LoadNode extends MemOpNode {
// Signed extension
int shift = Long.numberOfLeadingZeros(ti._max)-1;
Node shf = con(shift);
- if( shf._type==TypeInteger.ZERO ) {
- // A freshly exposed Store value can still be globally unknown.
- // Revisit this Load when it settles instead of replacing a typed
- // Load with the weaker transient value.
- if( !val._type.isa(_type) ) {
- addDep(val);
- return null;
- }
+ if( shift==0 ) {
+ if( !val._type.isa(_type) )
+ { addDep(val); return null; }
return val;
}
Node shl = new ShlNode(null,val,shf.keep()).peephole();
return new SarNode(null,shl,shf.unkeep());
}
- @Override public int log_size() { return declaredType().log_size(); }
+ //@Override public int log_size() { return declaredType().log_size(); }
}
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/LoopNode.java
index 90544c00..42c76060 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/LoopNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/LoopNode.java
@@ -75,7 +75,7 @@ public class LoopNode extends RegionNode {
// Nope, insert an aligned exit layer
RegionNode r = new RegionNode(_loc,null,ctrl).init();
ctrl = r; r._ltree = stop._ltree;
- mem = new BulkMemPhiNode(r,mem ).init();
+ mem = new BulkMemPhiNode(r,mem).init();
expr = new PhiNode(r,expr).init();
}
// Append new Never exit
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 59f7c304..083889c5 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
@@ -99,7 +99,7 @@ public abstract class MemOpNode extends TypeNode {
@Override public StringBuilder _print1( StringBuilder sb, BitSet visited ) { return _printMach(sb,visited); }
public StringBuilder _printMach( StringBuilder sb, BitSet visited ) { throw Utils.TODO(); }
- public int log_size() { return _con.log_size(); }
+ //public int log_size() { return _con.log_size(); }
@Override
public boolean eq(Node n) {
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/ParmNode.java
index 51ea28b0..04949a53 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/ParmNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/ParmNode.java
@@ -38,9 +38,6 @@ public class ParmNode extends PhiNode {
@Override public String glabel() { return _label; }
- @Override protected Type declaredType() { return _declaredType; }
- @Override protected Type constrain(Type t) { return t.join(_declaredType); }
-
@Override boolean _upgradeType( HashMap<String,Type> TYPES) {
Type t = _declaredType.upgradeType(TYPES);
if( t == _declaredType ) return false;
@@ -71,6 +68,28 @@ public class ParmNode extends PhiNode {
@Override public boolean inProgress() { return in(0) instanceof FunNode fun && fun.inProgress(); }
@Override
+ public Type compute() {
+ if( !(region() instanceof RegionNode r) )
+ return region()._type==Type.XCONTROL || region()._type==Type.TOP ? (_type instanceof TypeMem ? TypeMem.TOP : Type.TOP) : _type;
+ // During parsing Phis have to be computed type pessimistically.
+ if( r.inProgress() || in(nIns()-1)==null )
+ return _declaredType;
+ // Set type to local top of the starting type
+ Type t = Type.TOP;
+ for( int i = 1; i < nIns(); i++ ) {
+ // If the region's control input is live, add this as a dependency
+ // to the control because we can be peeped should it become dead.
+ Type ctrl = addDep(r.in(i))._type;
+ if( ctrl != Type.XCONTROL && ctrl != Type.TOP ) {
+ if( in(i)._type==Type.BOTTOM )
+ return Type.BOTTOM;
+ t = t.meet(in(i)._type);
+ }
+ }
+ return t.join(_declaredType);
+ }
+
+ @Override
public Node idealize() {
if( !(region() instanceof FunNode) )
// A dead function can lose every caller before the Parm itself is
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 2ae3c752..78a2690a 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -69,15 +69,14 @@ public class PhiNode extends Node {
public CFGNode region() { return (CFGNode)in(0); }
@Override public boolean isMem() { return _type instanceof TypeMem; }
@Override public boolean isPinned() { return true; }
- boolean isRPC() { return false; }
@Override
public Type compute() {
if( !(region() instanceof RegionNode r) )
- return region()._type==Type.XCONTROL || region()._type==Type.TOP ? (_type instanceof TypeMem ? TypeMem.TOP : Type.TOP) : _type;
+ return Type.TOP;
// During parsing Phis have to be computed type pessimistically.
if( r.inProgress() || in(nIns()-1)==null )
- return declaredType();
+ return Type.BOTTOM;
// Set type to local top of the starting type
Type t = Type.TOP;
for( int i = 1; i < nIns(); i++ ) {
@@ -90,31 +89,23 @@ public class PhiNode extends Node {
t = t.meet(in(i)._type);
}
}
- Type declared = declaredType();
- Type newt = constrain(t);
// phi loop widening part
- if( region() instanceof LoopNode && // Only around loops
- newt instanceof TypeInteger newi &&
- // Types changed and are falling (the optimistic case, expected to fall forever)
- newi != _type ) {
- if( !newi.isConstant() && (!(_type instanceof TypeInteger oldi) || newi._widen <= oldi._widen) )
- return newi.same_but_slightly_wider_than(
- declared instanceof TypeInteger ? declared : TypeInteger.BOT);
+ if( r instanceof LoopNode && // Only around loops
+ t != _type && // Types changed and are falling (the optimistic case, expected to fall forever)
+ !t.isConstant() && // No need to widen constants
+ t instanceof TypeInteger newi && // Only widen integers
+ (!(_type instanceof TypeInteger oldi) || newi._widen <= oldi._widen) ) {
+ // Widen, to prevent infinite falling of TypeIntegers
+ return newi.same_but_slightly_wider_than();
}
- return newt;
+ return t;
}
- // Ordinary Phis have no parser-supplied type constraint.
- protected Type declaredType() { return Type.BOTTOM; }
- protected Type constrain(Type t) { return t; }
-
@Override
public Node idealize() {
- if( !(region() instanceof RegionNode r ) )
- return in(1); // Input has collapse to e.g. starting control.
- if( r.inProgress() || r.nIns()<=1 || nOuts()==0 )
+ if( ((RegionNode)region()).inProgress() || nOuts()==0 )
return null; // Input is in-progress
// If we have only a single unique input, become it.
@@ -124,7 +115,7 @@ public class PhiNode extends Node {
// No bother if region is going to fold dead paths soon
for( int i=1; i<nIns(); i++ )
- if( r.in(i)._type == Type.XCONTROL )
+ if( region().in(i)._type == Type.XCONTROL )
return null;
// Generic "pull down op"
@@ -138,28 +129,6 @@ public class PhiNode extends Node {
if( in(2) instanceof GuardNode cast && cast._nonZero && in(1)._type.makeZero()==in(1)._type && cast.in(1)!=this ) return cast.in(1);
}
- // If merging a null-checked null and the checked value, just use the value.
- // if( val ) ..; phi(Region,False=0/null,True=val);
- // then replace with plain val.
- if( nIns()==3 ) {
- int nullx = -1;
- if( in(1)._type == in(1)._type.makeZero() ) nullx = 1;
- if( in(2)._type == in(2)._type.makeZero() ) nullx = 2;
- if( nullx != -1 ) {
- Node val = in(3-nullx);
- if( val instanceof GuardNode cast && cast._nonZero )
- val = cast.in(1);
- Node ridom = r.idom(this);
- if( ridom instanceof IfNode iff && addDep(iff.pred())==val ) {
- // Must walk the idom on the null side to make sure we hit False.
- CFGNode idom = r.cfg(nullx);
- while( idom != null && idom.nIns() > 0 && idom.in(0) != iff ) idom = idom.idom();
- if( idom instanceof CProjNode proj && proj._idx==1 )
- return val;
- } else if( ridom != null ) addDep(ridom);
- }
- }
-
return null;
}
@@ -169,13 +138,10 @@ public class PhiNode extends Node {
Node busy=null;
for( int i=1; i<nIns(); i++ ) {
Node op = in(i);
- if( op.nOuts()==0 )
- { op.kill(); return false; }
if( in(1).getClass() != op.getClass() || op.in(0)!=null || in(1).nIns() != op.nIns() )
return false; // Wrong class or CFG bound or mismatched inputs
if( in(1) instanceof MemOpNode mem ) {
- // Mismatched aliases
- if( mem._alias != ((MemOpNode)op)._alias ) return false;
+ assert mem._alias == ((MemOpNode)op)._alias;
// Load is clobbered somewhere, and can not be pulled forward past the Phi?
if( mem instanceof LoadNode )
for( Node use : op.outs() )
@@ -198,9 +164,6 @@ public class PhiNode extends Node {
return false;
}
}
- for( int j=1; j<in(1).nIns(); j++ )
- if( op.in(j) instanceof ScopeNode || (op.in(j)==null ^ in(1).in(j)==null) )
- return false; // Lazy Phi input
}
return true;
}
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 baf983f3..f140f28f 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java
@@ -55,10 +55,14 @@ public class StoreNode extends MemOpNode {
@Override public String glabel() { return "." +_name+"="; }
@Override public boolean isMem() { return true; }
- public Node nnptr() { return ptr() instanceof GuardNode cast && cast._nonZero ? cast.in(1) : ptr(); }
+ public Node nnptr() {
+ if( !(ptr() instanceof GuardNode cast) ) return ptr();
+ assert cast._nonZero;
+ return cast.in(1);
+ }
public Node val() { return in(4); }
public int storeSize() { assert _size==1 || _size==2 || _size==4 || _size==8; return _size; }
- @Override public int log_size() { return Integer.numberOfTrailingZeros(storeSize()); }
+ public int log_size() { return Integer.numberOfTrailingZeros(storeSize()); };
@Override
public StringBuilder _print1(StringBuilder sb, BitSet visited) {
@@ -68,7 +72,7 @@ public class StoreNode extends MemOpNode {
@Override
public Type compute() {
Type val = val()._type;
- Type mem0 = aliasMem()._type;
+ Type mem0 = mem()._type;
Type ptr0 = ptr()._type;
// Validate argument types
if( ptr0.isHigh() )
@@ -80,10 +84,8 @@ public class StoreNode extends MemOpNode {
// Sharpen memory value; required for narrowing stores where the parser
// inserts zero/sign masking and somebody reads the TypeMem type.
Type decl = declaredType();
- if( decl != Type.BOTTOM && decl != Type.TOP )
- val = val.join(decl);
- //if( err()!=null )
- // val = Type.BOTTOM;
+ if( decl != Type.BOTTOM )
+ { assert decl != Type.TOP; val = val.join(decl); }
// 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.
@@ -114,38 +116,31 @@ public class StoreNode extends MemOpNode {
// canonical field declaration. Waiting until after structural memory
// peeps can lose the declaration to a flow-sensitive constant field
// state. Imported Stores already carry a serialized non-zero width.
- Type storage = storageType();
- if( _size==0 && storage!=Type.BOTTOM && storage!=Type.TOP ) {
+ if( _size==0 && (_size= storageType()) != 0 ) {
unlock(); // Width participates in GVN identity.
- _size = storeSize(storage);
return init();
}
- // A precise Store can confirm its alias from a precise memory input.
- // Do not sharpen an alias-#1 (whole-memory) Store in place: users of
- // that Store already treat it as the complete memory state. The
- // pointer/field path below replaces it with a precise Store wrapped in
- // a MemMerge, preserving any other precise aliases in its input.
- if( mem()._type instanceof TypeMem mem ) {
- assert mem._alias > 0;
- if( _alias != 1 && mem._alias != 1 )
- assert _alias == mem._alias;
+ assert !(mem()._type instanceof TypeMem mem) || _alias == 1 || mem._alias == 1 || _alias == mem._alias;
+
+ // Simple store-after-MemMerge to a known alias can bypass. Happens when inlining.
+ Node mem = mem();
+ if( _alias != 1 && mem instanceof MemMergeNode merge ) {
+ setDef(1,merge.alias(_alias));
+ return this;
}
- // Forward-ref loads eventually sharpen to a declared type
Field fld;
- if( _alias==1 && ptr()._type instanceof TypeMemPtr tmp && (fld=tmp._obj.field(_name)) != null ) {
+ if( _alias==1 && ptr()._type instanceof TypeMemPtr tmp && (fld=tmp._obj.field(_name)) != null && _size != 0 ) {
// Expand Store(bulkMem,alias#1) into MemMerge(bulkMem,#N:Store(bulkMem,alias#N)).
// Normally I'd like to just drop in this xform and move on, but
// users of the bulk Store memory might nontheless depend on the
- // sharp memory type (e.g. I64) from the stores memory. Using the
+ // sharp memory type (e.g. I64) from the store's memory. Using the
// MemMerge means using the bulk memory which e.g. might be BOT.
// Check for store users with the same alias, and use the new store
// directly, preserving the sharper graph.
- Type decl = storageType();
- byte size = _size==0 && decl!=Type.BOTTOM && decl!=Type.TOP ? storeSize(decl) : _size;
- Node st = new StoreNode(_loc,_name,fld._alias,fld._t,in(0),mem(),ptr(),off(),val(),_init,size).peephole();
+ Node st = new StoreNode(_loc,_name,fld._alias,fld._t,in(0),mem,ptr(),off(),val(),_init,_size).peephole();
for( int i=0; i<nOuts(); i++ ) {
Node use = out(i);
if( useAlias(use)==fld._alias ) {
@@ -155,24 +150,17 @@ public class StoreNode extends MemOpNode {
i--; // setDef removed use from this Store's outputs
}
}
- MemMergeNode mmm = mem() instanceof BulkMemPhiNode bulk
- ? bulk.aggregate(mem(),fld._alias,st)
- : new MemMergeNode(null,mem());
- if( !(mem() instanceof BulkMemPhiNode) )
+ MemMergeNode mmm = mem instanceof BulkMemPhiNode bulk
+ ? bulk.aggregate(mem,fld._alias,st)
+ : new MemMergeNode(null,mem);
+ if( !(mem instanceof BulkMemPhiNode) )
mmm.alias(fld._alias,st);
return mmm.init();
}
- // Expose the same effective memory input already observed by compute.
- Node aliasMem = aliasMem();
- if( aliasMem != mem() ) {
- setDef(1,aliasMem);
- CodeGen.CODE.add(aliasMem);
- return this;
- }
// Simple store-after-store on same address. Should pick up the
// required init-store being stomped by a first user store.
- if( mem() instanceof StoreNode st &&
+ if( mem instanceof StoreNode st &&
ptr()==st.ptr() && // Must check same object
off()==st.off() && // And same offset (could be "same alias" but this handles arrays to same index)
ptr()._type instanceof TypeMemPtr && // No bother if weird dead pointers
@@ -184,18 +172,6 @@ public class StoreNode extends MemOpNode {
return this;
}
- // Simple store-after-MemMerge to a known alias can bypass. Happens when inlining.
- if( _alias != 1 && mem() instanceof MemMergeNode mem ) {
- setDef(1,mem.alias(_alias));
- return this;
- }
-
- // Resolve the semantic Store variant exactly once, after structural
- // memory/alias peeps. This avoids publishing a half-sharpened Store
- // while BulkMemPhi is constructing precise slices.
- if( storage != Type.BOTTOM && storage != Type.TOP )
- assert _size==storeSize(storage) : "Store width changed for '"+_name+"': "+_size+" from "+storage;
-
// Value is automatically truncated by narrow store
if( _size!=0 && val() instanceof AndNode and && and.in(2)._type.isConstant() ) {
int log = log_size();
@@ -230,34 +206,33 @@ public class StoreNode extends MemOpNode {
return null;
}
- private static byte storeSize(Type decl) {
- // `decl` is the target field declaration, not the stored value. In
- // particular a constant zero stored into u32 is still a 4-byte Store;
- // taking the constant's natural width here would incorrectly select i64.
- byte size = (byte)(1 << decl.log_size());
- assert size==1 || size==2 || size==4 || size==8;
- return size;
- }
-
// Flow-sensitive pointer types can carry a current field value (e.g. the
// constant zero in a u32 field). Storage width comes from the canonical
// struct declaration. If the pointer/definition is not available yet,
// leave the Store undecided instead of consulting the value or `_con`.
- private Type storageType() {
+ private byte storageType() {
+ if( !(ptr()._type instanceof TypeMemPtr tmp) )
+ return 0;
+ TypeStruct obj = (TypeStruct)Parser.TYPES.get(tmp._obj._name);
+ Field fld = obj.field(_name);
+ if( fld == null || fld._t == null )
+ return 0;
+ if( fld._t == Type.BOTTOM )
+ return 0; // Store into a final field
+ assert fld._t != Type.TOP;
// Freshly parsed field stores retain the declaring structure on their
// symbolic offset even after the pointer's flow type sharpens.
- if( off() instanceof ConFldOffNode coff ) {
- Field fld = coff._ts.field(_name);
- if( fld != null && fld._t != null ) return fld._t;
+ if( fld._t.isConstant() ) {
+ if( !(off() instanceof ConFldOffNode coff) )
+ return 0;
+ fld = coff._ts.field(_name);
+ if( fld == null || fld._t == null )
+ return 0;
}
- if( !(ptr()._type instanceof TypeMemPtr tmp) ) return Type.BOTTOM;
- Type base = Parser.TYPES.get(tmp._obj._name);
- TypeStruct obj = base instanceof TypeStruct ts ? ts : tmp._obj;
- Field fld = obj.field(_name);
- // Imported optimized structs can expose the current constant field
- // value instead of its declaration. A constant has no storage width;
- // an imported Store already carries its serialized, frozen `_size`.
- return fld == null || fld._t == null || fld._t.isConstant() ? Type.BOTTOM : fld._t;
+ // Compute storage size from field type
+ byte size = (byte)(1 << fld._t.log_size());
+ assert size==1 || size==2 || size==4 || size==8;
+ return size;
}
// Alias required by a direct consumer of this Store's memory result.
@@ -266,28 +241,11 @@ public class StoreNode extends MemOpNode {
return switch( use ) {
case MemOpNode mem -> mem._alias;
case MemPhiNode phi -> phi._alias;
- case EscapeNode esc -> esc.pub()==this ? esc.fld()._alias : 0;
+ case EscapeNode esc -> throw Utils.TODO("Untested"); // esc.pub()==this ? esc.fld()._alias : 0;
default -> 0;
};
}
- // Select a precise alias from a whole-memory partition. Alias #1 is the
- // bulk remainder itself.
- private static Node memSlice( Node mem, int alias ) {
- return alias != 1 && mem instanceof MemMergeNode merge
- ? merge.alias(alias)
- : mem;
- }
-
- // Semantic memory input for this Store. Compute defines behavior from
- // this view; ideal exposes the same edge in the graph.
- private Node aliasMem() {
- Node mem = mem();
- if( _alias != 1 && mem instanceof MemMergeNode merge )
- mem = merge.alias(_alias);
- return mem;
- }
-
// Check that "mem" has no uses except "this"
private boolean checkOnlyUse(Node mem) {
if( mem.nOuts()==1 ) return true;
@@ -303,10 +261,8 @@ public class StoreNode extends MemOpNode {
public Parser.ParseException err() {
Parser.ParseException err = super.err();
if( err != null ) return err;
- if( _size==0 && CodeGen.CODE._phase.ordinal() > CodeGen.Phase.Opto.ordinal() )
- throw Utils.TODO("Failed to decide Store size");
- if( ptr()._type == Type.TOP )
- return null; // This means we have an error input, report elsewhere
+ assert _size>0 || CodeGen.CODE._phase.ordinal() <= CodeGen.Phase.Opto.ordinal();
+ assert ptr()._type != Type.TOP;
TypeMemPtr tmp = (TypeMemPtr)ptr()._type;
Field f = tmp._obj.field(_name);
if( f!=null && f._final && !_init )
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
index 28e788fe..405e64d0 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
@@ -56,8 +56,8 @@ public class TypeInteger extends TypeScalar {
return this;
}
- public Type same_but_slightly_wider_than( Type minType ) {
- return _widen < 3 ? make(_min,_max, (byte)(_widen+1)) : minType;
+ public Type same_but_slightly_wider_than( ) {
+ return _widen < 3 ? make(_min,_max, (byte)(_widen+1)) : BOT;
}
// Force max widen
@Override public Type widen() {
diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java
index 68f94f12..96e7fce7 100644
--- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java
+++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java
@@ -231,6 +231,15 @@ return 0;
assertEquals("Hello, World!",arm._stdout.toString());
}
+
+ @Test
+ public void testStrLoad() {
+ CodeGen code = new CodeGen("return \"abc\"[1];");
+ code.parse().opto();
+ assertEquals("return .[];", code.print());
+ }
+
+
@Test
public void testFinalArray() {
String src = """