From 1ee105dce9c32460feed5c3a20c42abbaa7c1896 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 12 Oct 2024 14:02:06 -0700 Subject: Chapter 16: Constructors and Final fields Co-authored-by: Thalia Archibald --- .../java/com/seaofnodes/simple/node/AndNode.java | 7 +- .../java/com/seaofnodes/simple/node/CastNode.java | 3 +- .../java/com/seaofnodes/simple/node/IfNode.java | 4 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 16 +- .../java/com/seaofnodes/simple/node/MulNode.java | 2 + .../java/com/seaofnodes/simple/node/NewNode.java | 35 ++- src/main/java/com/seaofnodes/simple/node/Node.java | 51 +++-- .../java/com/seaofnodes/simple/node/NotNode.java | 2 +- .../java/com/seaofnodes/simple/node/OrNode.java | 7 +- .../java/com/seaofnodes/simple/node/OutNode.java | 4 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 2 +- .../com/seaofnodes/simple/node/RegionNode.java | 7 +- .../com/seaofnodes/simple/node/ReturnNode.java | 14 +- .../java/com/seaofnodes/simple/node/SarNode.java | 9 +- .../com/seaofnodes/simple/node/ScopeMinNode.java | 137 +++++++++++ .../java/com/seaofnodes/simple/node/ScopeNode.java | 254 +++++++++++---------- .../java/com/seaofnodes/simple/node/ShlNode.java | 11 +- .../java/com/seaofnodes/simple/node/ShrNode.java | 9 +- .../java/com/seaofnodes/simple/node/StartNode.java | 45 +--- .../java/com/seaofnodes/simple/node/StoreNode.java | 41 +++- .../com/seaofnodes/simple/node/StructNode.java | 45 ++++ .../java/com/seaofnodes/simple/node/XorNode.java | 7 +- 22 files changed, 472 insertions(+), 240 deletions(-) create mode 100644 src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/StructNode.java (limited to 'src/main/java/com/seaofnodes/simple/node') diff --git a/src/main/java/com/seaofnodes/simple/node/AndNode.java b/src/main/java/com/seaofnodes/simple/node/AndNode.java index 7e4b898b..17a4e0ca 100644 --- a/src/main/java/com/seaofnodes/simple/node/AndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AndNode.java @@ -21,8 +21,11 @@ public class AndNode extends Node { @Override public Type compute() { - if( in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1 ) { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1.isHigh() || t2.isHigh() ) + return TypeInteger.TOP; + if( t1 instanceof TypeInteger i0 && + t2 instanceof TypeInteger i1 ) { if( i0.isConstant() && i1.isConstant() ) return TypeInteger.constant(i0.value()&i1.value()); // Sharpen allowed bits if either value is narrowed diff --git a/src/main/java/com/seaofnodes/simple/node/CastNode.java b/src/main/java/com/seaofnodes/simple/node/CastNode.java index fbf0e518..462d6cba 100644 --- a/src/main/java/com/seaofnodes/simple/node/CastNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CastNode.java @@ -21,8 +21,7 @@ public class CastNode extends Node { @Override public String uniqueName() { return "Cast_" + _nid; } - @Override - public boolean isPinned() { return true; } + @Override public boolean isPinned() { return true; } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 5457ac6e..3cce89ab 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -41,8 +41,8 @@ public class IfNode extends CFGNode implements MultiNode { return TypeTuple.IF_NEITHER; // If constant is 0 then false branch is reachable // Else true branch is reachable - if (t instanceof TypeInteger ti && ti.isConstant()) - return ti==TypeInteger.ZERO ? TypeTuple.IF_FALSE : TypeTuple.IF_TRUE; + if( t.isConstant() ) + return t.makeInit()==t ? TypeTuple.IF_FALSE : TypeTuple.IF_TRUE; return TypeTuple.IF_BOTH; } diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 0bdf86f0..d15d4f83 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -2,9 +2,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeMem; -import com.seaofnodes.simple.type.TypeStruct; +import com.seaofnodes.simple.type.*; import java.util.BitSet; /** @@ -38,7 +36,6 @@ public class LoadNode extends MemOpNode { if( mem()._type instanceof TypeMem mem && // No constant folding if ptr might null-check _declaredType != mem._t && err()==null ) { - assert mem._alias == _alias; return _declaredType.join(mem._t); } return _declaredType; @@ -57,8 +54,8 @@ public class LoadNode extends MemOpNode { // Simple Load-after-New on same address. if( mem() instanceof ProjNode p && p.in(0) instanceof NewNode nnn && - ptr == nnn.proj(1) ) // Must check same object - return new ConstantNode(_declaredType.makeInit()); + ptr == nnn.proj(1) ) // Must check same object + return nnn.in(nnn.findAlias(_alias)); // Load from New init // Load-after-Store on same address, but bypassing provably unrelated // stores. This is a more complex superset of the above two peeps. @@ -77,12 +74,12 @@ public class LoadNode extends MemOpNode { // Pointers cannot overlap mem = st.mem(); // Proved never equal break; - case PhiNode phi: - break outer; // Assume related + case PhiNode phi: break outer; // Assume related + case ConstantNode top: break outer; // Assume shortly dead case ProjNode mproj: if( mproj.in(0) instanceof NewNode nnn1 ) { if( ptr instanceof ProjNode pproj && pproj.in(0) == mproj.in(0) ) - return new ConstantNode(_declaredType.makeInit()); // Load from a New + return nnn1.in(nnn1.findAlias(_alias)); // Load from New init if( !(ptr instanceof ProjNode pproj && pproj.in(0) instanceof NewNode nnn2) ) break outer; // Cannot tell, ptr not related to New mem = nnn1.in(_alias);// Bypass unrelated New @@ -125,7 +122,6 @@ public class LoadNode extends MemOpNode { ptr2 instanceof ProjNode && ptr2.in(0) instanceof NewNode; } - // Profitable if we find a matching Store on this Phi arm. private boolean profit(PhiNode phi, int idx) { Node px = phi.in(idx); diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index f231a97b..b5ef91e9 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -26,6 +26,8 @@ public class MulNode extends Node { return TypeInteger.TOP; if( t1 instanceof TypeInteger i1 && t2 instanceof TypeInteger i2 ) { + if( i1==TypeInteger.ZERO || i2==TypeInteger.ZERO) + return TypeInteger.ZERO; if (i1.isConstant() && i2.isConstant()) return TypeInteger.constant(i1.value()*i2.value()); } diff --git a/src/main/java/com/seaofnodes/simple/node/NewNode.java b/src/main/java/com/seaofnodes/simple/node/NewNode.java index f06564cd..ddb1e09a 100644 --- a/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.Utils; import java.util.BitSet; /** @@ -11,23 +12,30 @@ import java.util.BitSet; */ public class NewNode extends Node implements MultiNode { - public TypeMemPtr _ptr; + public final TypeMemPtr _ptr; + public final int _len; public NewNode(TypeMemPtr ptr, Node... nodes) { super(nodes); + _ptr = ptr; + _len = ptr._obj._fields.length; // Control in slot 0 assert nodes[0]._type==Type.CONTROL || nodes[0]._type == Type.XCONTROL; // Malloc-length in slot 1 assert nodes[1]._type instanceof TypeInteger; - // Memory slices in remaining slots - for( int i=2; i * Generally fixed length, ordered, nulls allowed, no unused trailing space. * Ordering is required because e.g. "a/b" is different from "b/a". - * The first input (offset 0) is often a {@link #isCFG} node. + * The first input (offset 0) is often a {@link CFGNode} node. */ - public final ArrayList _inputs; + public final Ary _inputs; /** * Outputs reference Nodes that are not null and have this Node as an @@ -41,7 +41,7 @@ public abstract class Node implements OutNode { * walked in either direction. These outputs are typically used for * efficient optimizations but otherwise have no semantics meaning. */ - public final ArrayList _outputs; + public final Ary _outputs; /** @@ -61,9 +61,9 @@ public abstract class Node implements OutNode { protected Node(Node... inputs) { _nid = UNIQUE_ID++; // allocate unique dense ID - _inputs = new ArrayList<>(); + _inputs = new Ary<>(Node.class); Collections.addAll(_inputs,inputs); - _outputs = new ArrayList<>(); + _outputs = new Ary<>(Node.class); for( Node n : _inputs ) if( n != null ) n.addUse( this ); @@ -127,7 +127,7 @@ public abstract class Node implements OutNode { */ public Node in(int i) { return _inputs.get(i); } public Node out(int i) { return _outputs.get(i); } - @Override public ArrayList outs() { return _outputs; } + @Override public Ary outs() { return _outputs; } public int nIns() { return _inputs.size(); } @@ -168,7 +168,7 @@ public abstract class Node implements OutNode { old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def moveDepsToWorklist(); - // Return self for easy flow-coding + // Return new_def for easy flow-coding return new_def; } @@ -179,13 +179,20 @@ public abstract class Node implements OutNode { Node delDef(int idx) { unlock(); Node old_def = in(idx); - Utils.del(_inputs, idx); + _inputs.del(idx); if( old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def old_def.moveDepsToWorklist(); return this; } + // Insert the numbered input, sliding other inputs to the right + Node insertDef(int idx, Node new_def) { + _inputs.add(idx,null); + return setDef(idx,new_def); + } + + /** * Add a new def to an existing Node. Keep the edges correct by * adding the corresponding def->use edge. @@ -210,16 +217,16 @@ public abstract class Node implements OutNode { // Return true if the output list is empty afterward. // Error is 'use' does not exist; ok for 'use' to be null. protected boolean delUse( Node use ) { - Utils.del(_outputs, Utils.find(_outputs, use)); + _outputs.del(_outputs.find(use)); return _outputs.isEmpty(); } - // Shortcut for "popping" n nodes. A "pop" is basically a + // Shortcut for "popping" until n nodes. A "pop" is basically a // setDef(last,null) followed by lowering the nIns() count. - void popN(int n) { + void popUntil(int n) { unlock(); - for( int i=0; i n ) { + Node old_def = _inputs.pop(); if( old_def != null && // If it exists and old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def @@ -259,7 +266,7 @@ public abstract class Node implements OutNode { return (N)this; } // Test "keep" status - public boolean iskeep() { return Utils.find(_outputs,null) != -1; } + public boolean iskeep() { return _outputs.find(null) != -1; } // Replace self with nnn in the graph, making 'this' go dead @@ -268,7 +275,7 @@ public abstract class Node implements OutNode { while( nOuts() > 0 ) { Node n = _outputs.removeLast(); n.unlock(); - int idx = Utils.find(n._inputs, this); + int idx = n._inputs.find(this); n._inputs.set(idx,nnn); nnn.addUse(n); } @@ -294,7 +301,7 @@ public abstract class Node implements OutNode { return this; // Peephole optimizations turned off } Node n = peepholeOpt(); - return n==null ? this : deadCodeElim(n.peephole().keep()).unkeep(); // Cannot return null for no-progress + return n==null ? this : deadCodeElim(n.peephole()); // Cannot return null for no-progress } /** @@ -451,7 +458,7 @@ public abstract class Node implements OutNode { // on a node some distance away, and if that node ever changes we should // retry the peephole. Track a set of Nodes dependent on `this`, and // revisit them if `this` changes. - ArrayList _deps; + Ary _deps; /** * Add a node to the list of dependencies. Only add it if its not an input @@ -462,10 +469,10 @@ public abstract class Node implements OutNode { // Running peepholes during the big assert cannot have side effects // like adding dependencies. if( IterPeeps.midAssert() ) return this; - if( _deps==null ) _deps = new ArrayList<>(); - if( Utils.find(_deps ,dep) != -1 ) return this; // Already on list - if( Utils.find(_inputs,dep) != -1 ) return this; // No need for deps on immediate neighbors - if( Utils.find(_outputs,dep)!= -1 ) return this; + if( _deps==null ) _deps = new Ary<>(Node.class); + if( _deps .find(dep) != -1 ) return this; // Already on list + if( _inputs .find(dep) != -1 ) return this; // No need for deps on immediate neighbors + if( _outputs.find(dep) != -1 ) return this; _deps.add(dep); return this; } diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java index b3c77c45..ffd3e01e 100644 --- a/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -22,7 +22,7 @@ public class NotNode extends Node { Type t0 = in(1)._type; if( t0.isHigh() ) return TypeInteger.BOOL.dual(); switch( t0 ) { - case TypeInteger i0: return i0._max < 0 || i0._min > 0 ? TypeInteger.FALSE : (i0==TypeInteger.ZERO ? TypeInteger.TRUE : TypeInteger.BOT); + case TypeInteger i0: return i0._max < 0 || i0._min > 0 ? TypeInteger.FALSE : (i0==TypeInteger.ZERO ? TypeInteger.TRUE : TypeInteger.BOOL); case TypeFloat i0: return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0; case TypeMemPtr p0: // top->top, bot->bot, null->1, *void->0, not-null ptr->0, ptr/nil->bot diff --git a/src/main/java/com/seaofnodes/simple/node/OrNode.java b/src/main/java/com/seaofnodes/simple/node/OrNode.java index 1b32d4fb..b572346f 100644 --- a/src/main/java/com/seaofnodes/simple/node/OrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/OrNode.java @@ -21,8 +21,11 @@ public class OrNode extends Node { @Override public Type compute() { - if( in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1 ) { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1.isHigh() || t2.isHigh() ) + return TypeInteger.TOP; + if( t1 instanceof TypeInteger i0 && + t2 instanceof TypeInteger i1 ) { if( i0.isConstant() && i1.isConstant() ) return TypeInteger.constant(i0.value()|i1.value()); } diff --git a/src/main/java/com/seaofnodes/simple/node/OutNode.java b/src/main/java/com/seaofnodes/simple/node/OutNode.java index 7e531145..dbac136b 100644 --- a/src/main/java/com/seaofnodes/simple/node/OutNode.java +++ b/src/main/java/com/seaofnodes/simple/node/OutNode.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.node; -import java.util.ArrayList; +import com.seaofnodes.simple.Ary; public interface OutNode { - ArrayList outs(); + Ary outs(); } diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 139e80a3..f0140ce6 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -43,7 +43,7 @@ public class PhiNode extends Node { @Override public Type compute() { if( !(region() instanceof RegionNode r) ) - return region()._type==Type.XCONTROL ? Type.TOP : _type; + return region()._type==Type.XCONTROL ? (_type instanceof TypeMem ? TypeMem.TOP : Type.TOP) : _type; // During parsing Phis have to be computed type pessimistically. if( r.inProgress() ) return _declaredType; // Set type to local top of the starting type diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index bd05ce01..941de76b 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -68,7 +68,7 @@ public class RegionNode extends CFGNode { if( !hasPhi() && // No Phi users, just a control user in(1) instanceof CProjNode p1 && in(2) instanceof CProjNode p2 && - p1.in(0)==p2.in(0) && + p1.in(0).addDep(this)==p2.in(0).addDep(this) && p1.in(0) instanceof IfNode iff ) return iff.ctrl(); @@ -102,7 +102,7 @@ public class RegionNode extends CFGNode { // A walk that can be cutoff early private static final BitSet VISIT = new BitSet(); - private static boolean walk( IfNode iff, CProjNode cproj, Node n ) { + private boolean walk( IfNode iff, CProjNode cproj, Node n ) { if( VISIT.get(n._nid) ) return false; VISIT.set(n._nid); if( n instanceof CFGNode ) return false; @@ -110,6 +110,7 @@ public class RegionNode extends CFGNode { return false; boolean progress = false; Node pred = iff.pred(); + if( pred._type.isHighOrConst() ) return false; // This will collapse the IF already for( int i=1; i= 2 - if( scope != null ) { - String[] names = scope.reverseNames(); - for (String name: names) { - if (!name.equals("$ctrl") && name.startsWith("$")) - addDef(scope.lookup(name)); - } - } + super(ctrl, data); + if( scope!=null ) + for( int i=2; i>i1.value()); if( i1.isConstant() ) { diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java new file mode 100644 index 00000000..e4874e15 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java @@ -0,0 +1,137 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.type.*; +import java.util.*; + +import static com.seaofnodes.simple.Utils.TODO; + +/* */ +public class ScopeMinNode extends Node { + + /** The tracked fields are now complex enough to deserve a array-of-structs layout + */ + public static class Var { + public final int _idx; + public final String _name; + public final Type _type; + public final boolean _final; + public Var(int idx, String name, Type type, boolean xfinal) { + _idx = idx; + _name = name; + _type = type; + _final = xfinal; + } + } + + public ScopeMinNode() { _type = TypeMem.BOT; } + + + @Override public String label() { return "MEM"; } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + sb.append("MEM[ "); + for( int j=2; j= nIns() ) addDef(null); + return setDef(alias,st); + } + + + // Read or update from memory. + // A shared implementation allows us to create lazy phis both during + // lookups and updates; the lazy phi creation is part of chapter 8. + Node _mem( int alias, Node st ) { + // Memory projections are made lazily; if one does not exist + // then it must be START.proj(1) + Node old = alias(alias); + if( old instanceof ScopeNode loop ) { + ScopeMinNode loopmem = loop.mem(); + Node memdef = loopmem.alias(alias); + // Lazy phi! + old = memdef instanceof PhiNode phi && loop.ctrl()==phi.region() + // Loop already has a real Phi, use it + ? memdef + // Set real Phi in the loop head + // The phi takes its one input (no backedge yet) from a recursive + // lookup, which might have insert a Phi in every loop nest. + : loopmem.alias(alias, new PhiNode(Parser.memName(alias), TypeMem.BOT,loop.ctrl(),loopmem._mem(alias,null),null).peephole() ); + alias(alias,old); + } + // Memory projections are made lazily; expand as needed + return st==null ? old : alias(alias,st); // Not lazy, so this is the answer + } + + + void _merge(ScopeMinNode that, RegionNode r) { + int len = Math.max(nIns(),that.nIns()); + for( int i = 2; i < len; i++) + if( alias(i) != that.alias(i) ) { // No need for redundant Phis + // If we are in lazy phi mode we need to a lookup + // by name as it will trigger a phi creation + //Var v = _vars.at(i); + Node lhs = this._mem(i,null); + Node rhs = that._mem(i,null); + alias(i, new PhiNode(Parser.memName(i), TypeMem.BOT, r, lhs, rhs).peephole()); + } + } + + // Fill in the backedge of any inserted Phis + void _endLoopMem( ScopeNode scope, ScopeMinNode back, ScopeMinNode exit ) { + for( int i=2; i> _idxs; + // All active/live variables in all nested scopes, all run together + public final Ary _vars; + + // Since of each nested lexical scope + public final Ary _lexSize; - /** - * Map variable names to declared Type - */ - final Stack> _decls; // A new ScopeNode - public ScopeNode() { - _idxs = new Stack<>(); - _decls= new Stack<>(); - _type = Type.BOTTOM; - } + public ScopeNode() { _vars = new Ary<>(Var.class); _lexSize = new Ary<>(Integer.class); } @Override public String label() { return "Scope"; } + @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { sb.append("Scope[ "); - String[] names = reverseNames(); - for( int j=0; j syms : _idxs ) - for( String name : syms.keySet() ) - names[syms.get(name)] = name; - return names; + public void push() { + _lexSize.push(_vars.size()); + } + public void pop() { + int n = _lexSize.pop(); + popUntil(n); + _vars.setLen(n); } - @Override public Type compute() { return Type.BOTTOM; } - - @Override public Node idealize() { return null; } - - public void push() { _idxs.push(new HashMap<>()); _decls.push(new HashMap<>()); } - public void pop() { popN(_idxs.pop().size()); _decls.pop(); } + // Find name in reverse, return an index into _vars or -1. Linear scan + // instead of hashtable, but probably doesn't matter until the scan + // typically hits many dozens of variables. + int find( String name ) { + for( int i=_vars.size()-1; i>=0; i-- ) + if( _vars.get(i)._name.equals(name) ) + return i; + return -1; + } /** * Create a new variable name in the current scope */ - public Node define( String name, Type declaredType, Node n ) { - HashMap syms = _idxs.lastElement(); - _decls.lastElement().put(name,declaredType); - if( syms.put(name,nIns()) != null ) - return null; // Double define - return addDef(n); + public boolean define( String name, Type declaredType, boolean xfinal, Node init ) { + assert name.charAt(0)!='$' || _lexSize.size()==1; // Later scopes do not define memory + if( _lexSize._len > 1 ) + for( int i=_vars.size()-1; i>=_lexSize.last(); i-- ) + if( _vars.get(i)._name.equals(name) ) + return false; // Double define + _vars.add(new Var(nIns(),name,declaredType,xfinal)); + addDef(init); + return true; } + // Read from memory + public Node mem( int alias ) { return mem()._mem(alias,null); } + // Write to memory + public void mem( int alias, Node st ) { mem()._mem(alias,st); } + + /** * Lookup a name in all scopes starting from most deeply nested. * * @param name Name to be looked up - * @see #update(String, Node, int) + * @return null if not found, or the implementing Node */ - public Node lookup( String name ) { return update(name,null,_idxs.size()-1); } + public Var lookup( String name ) { + int idx = find(name); + // -1 is missed in all scopes, not found + return idx == -1 ? null : _update(_vars.at(idx),null); + } + /** * If the name is present in any scope, then redefine else null * * @param name Name being redefined * @param n The node to bind to the name */ - public Node update( String name, Node n ) { return update(name,n,_idxs.size()-1); } - /** - * Both recursive lookup and update. - *

- * A shared implementation allows us to create lazy phis both during - * lookups and updates; the lazy phi creation is part of chapter 8. - * - * @param name Name whose binding is being updated or looked up - * @param n If null, do a lookup, else update binding - * @param nestingLevel The starting nesting level - * @return node being looked up, or the one that was updated - */ - private Node update( String name, Node n, int nestingLevel ) { - if( nestingLevel<0 ) return null; // Missed in all scopes, not found - var syms = _idxs.get(nestingLevel); // Get the symbol table for nesting level - var idx = syms.get(name); - if( idx == null ) return update(name,n,nestingLevel-1); // Not found in this scope, recursively look in parent scope - Node old = in(idx); + public void update( String name, Node n ) { + int idx = find(name); + assert idx>=0; + _update(_vars.at(idx),n); + } + + Var _update( ScopeNode.Var v, Node st ) { + Node old = in(v._idx); if( old instanceof ScopeNode loop ) { // Lazy Phi! - old = loop.in(idx) instanceof PhiNode phi && loop.ctrl()==phi.region() + Node def = loop.in(v._idx); + old = def instanceof PhiNode phi && loop.ctrl()==phi.region() // Loop already has a real Phi, use it - ? loop.in(idx) + ? def // Set real Phi in the loop head // The phi takes its one input (no backedge yet) from a recursive // lookup, which might have insert a Phi in every loop nest. - : loop.setDef(idx,new PhiNode(name, lookupDeclaredType(name),loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole()); - setDef(idx,old); + : loop.setDef(v._idx,new PhiNode(v._name, v._type instanceof TypeMemPtr ? v._type : v._type.glb(), loop.ctrl(), loop.in(loop._update(v,null)._idx),null).peephole()); + setDef(v._idx,old); } - return n==null ? old : setDef(idx,n); // Not lazy, so this is the answer - } - - // Return declared type for a variable - public Type lookupDeclaredType( String name ) { - for( int i=_decls.size(); i>0; i-- ) { - Type t = _decls.get(i-1).get(name); - if( t != null ) return t; - } - return null; + if( st!=null ) setDef(v._idx,st); // Set new value + return v; } /** @@ -176,13 +178,22 @@ public class ScopeNode extends Node { // 1) duplicate the name bindings of the ScopeNode across all stack levels // 2) Make the new ScopeNode a user of all the nodes bound // 3) Ensure that the order of defs is the same to allow easy merging - for( HashMap syms : _idxs ) - dup._idxs.push(new HashMap<>(syms)); - for( HashMap ts : _decls ) - dup._decls.push(ts); // Types don't change, just keep stacks aligned - + dup._vars.addAll(_vars); + dup._lexSize.addAll(_lexSize); dup.addDef(ctrl()); // Control input is just copied - for( int i=1; i (x << i) + (c << i) - if( lhs instanceof AddNode add && add.in(2)._type instanceof TypeInteger c && c.isConstant() ) { + if( lhs instanceof AddNode add && add.in(2)._type instanceof TypeInteger c && c.isConstant() && c!=TypeInteger.ZERO ) { long sum = c.value() << shl.value(); if( Integer.MIN_VALUE <= sum && sum <= Integer.MAX_VALUE ) return new AddNode( new ShlNode(add.in(1),rhs).peephole(), Parser.con(sum) ); diff --git a/src/main/java/com/seaofnodes/simple/node/ShrNode.java b/src/main/java/com/seaofnodes/simple/node/ShrNode.java index 16d78ebf..22eb45a0 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -21,8 +21,13 @@ public class ShrNode extends Node { @Override public Type compute() { - if (in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1) { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1.isHigh() || t2.isHigh() ) + return TypeInteger.TOP; + if (t1 instanceof TypeInteger i0 && + t2 instanceof TypeInteger i1 ) { + if( i0 == TypeInteger.ZERO ) + return TypeInteger.ZERO; if( i0.isConstant() && i1.isConstant() ) return TypeInteger.constant(i0.value()>>>i1.value()); } diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index 5964e19f..c03a4b06 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.simple.type.*; import java.util.Arrays; import java.util.BitSet; import java.util.HashSet; +import static com.seaofnodes.simple.Utils.TODO; /** * The Start node represents the start of the function. @@ -15,41 +16,9 @@ import java.util.HashSet; */ public class StartNode extends CFGNode implements MultiNode { - // This field is NOT final, because the tuple expands as we add memory aliases - TypeTuple _args; + final Type _arg; - public StartNode(Type[] args) { - super(); - _args = TypeTuple.make(args); - _type = _args; - } - - /** - * Creates a projection for each of the struct's fields, using the field alias - * as the key. - */ - public void addMemProj( TypeStruct ts, ScopeNode scope) { - if( ts._fields.length==0 ) return; - // Expand args type for more memory projections - Type[] args = _args._types; - int max = args.length; - for( Field f : ts._fields ) - max = Math.max(max,f._alias); - args = Arrays.copyOf(args, max+1); - // For each of the fields we now add a mem projection. - for( Field f : ts._fields ) { - TypeMem tm_decl = TypeMem.make(f._alias,f._type.glb()); - args[f._alias] = tm_decl.dual(); - String name = Parser.memName(f._alias); - Node n = new ProjNode(this, f._alias, name); // No 'compute' until ScopeNode gets typed - n._type = args[f._alias]; - scope.define(name, tm_decl, n); - } - for (int i = 0; i < args.length; i++) - if (args[i] == null) - args[i] = Type.TOP; // We parsed a nested struct/array. Avoid nulls until a caller replaces this alias. - _type = _args = TypeTuple.make(args); - } + public StartNode(Type arg) { super(); _arg = arg; _type = compute(); } @Override public String label() { return "Start"; } @@ -62,11 +31,11 @@ public class StartNode extends CFGNode implements MultiNode { @Override public boolean blockHead() { return true; } @Override public CFGNode cfg0() { return this; } - @Override - public TypeTuple compute() { return _args; } + @Override public TypeTuple compute() { + return TypeTuple.make(Type.CONTROL,TypeMem.TOP,_arg); + } - @Override - public Node idealize() { return null; } + @Override public Node idealize() { return null; } // No immediate dominator, and idepth==0 @Override public int idepth() { return 0; } diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index b1c74b94..7b1bddd5 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -55,27 +55,52 @@ public class StoreNode extends MemOpNode { // required init-store being stomped by a first user store. if( mem() instanceof StoreNode st && ptr()==st.ptr() && // Must check same object - off()==st.off() && // And same offset + 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 // Must have exactly one use of "this" or you get weird // non-serializable memory effects in the worse case. - st.checkNoUseBeyond(this) ) { + checkOnlyUse(st) ) { assert _name.equals(st._name); // Equiv class aliasing is perfect setDef(1,st.mem()); return this; } + // Simple store-after-new on same address. Should pick up the + // an init-store being stomped by a first user store. + if( mem() instanceof ProjNode st && st .in(0) instanceof NewNode nnn && + ptr() instanceof ProjNode ptr && ptr.in(0) == nnn && + ptr()._type instanceof TypeMemPtr tmp && // No bother if weird dead pointers + // Cannot fold a store of a single element over the array body initializer value + !(tmp._obj.isAry() && tmp._obj._fields[1]._alias==_alias) && + // Very sad strong cutout: val has to be legal to hoist to a New + // input, which means it cannot depend on the New. Many many + // things are legal here but difficult to check without doing a + // full dominator check. Example failure: + // "struct C { C? c; }; C self = new C { c=self; }" + val()._type.isHighOrConst() && + // Must have exactly one use of "this" or you get weird + // non-serializable memory effects in the worse case. + checkOnlyUse(st) && + // Folding away a broken store + err()==null ) { + nnn.setDef(nnn.findAlias(_alias),val()); + // Must retype the NewNode + nnn ._type = nnn. compute(); + mem()._type = mem().compute(); + return st; + } + return null; } - // Check that `this` has no uses beyond `that` - private boolean checkNoUseBeyond(Node that) { - if( nOuts()==1 ) return true; + // Check that "mem" has no uses except "this" + private boolean checkOnlyUse(Node mem) { + if( mem.nOuts()==1 ) return true; // Add deps on the other uses (can be e.g. ScopeNode mid-parse) so that // when the other uses go away we can retry. - for( Node use : _outputs ) - if( use != that ) - use.addDep(that); + for( Node use : mem._outputs ) + if( use != this ) + use.addDep(this); return false; } diff --git a/src/main/java/com/seaofnodes/simple/node/StructNode.java b/src/main/java/com/seaofnodes/simple/node/StructNode.java new file mode 100644 index 00000000..db170ab1 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/StructNode.java @@ -0,0 +1,45 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.*; +import java.util.BitSet; + +/** + * Build a compound object + */ +public class StructNode extends Node { + + public TypeStruct _ts; + + @Override public String label() { return _ts==null ? "STRUCT?" : _ts.str(); } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + if( _ts==null ) return sb.append("STRUCT?"); + sb.append(_ts._name).append(" {"); + for( int i=0; i