diff options
| author | Cliff Click <cliffc@acm.org> | 2026-09-10 12:39:12 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-09-10 12:39:12 -0700 |
| commit | 6f920fae07f899672b04458b0f80a5119dcdef96 (patch) | |
| tree | 2c51a2c4614127ea238dbd922222fc3285ea8848 /chapter25 | |
| parent | 1f4006e88df54e2b7086bc49e05ffc6d2068e8fd (diff) | |
| download | Simple-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')
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 = """ |
