diff options
Diffstat (limited to 'src/main/java/com/seaofnodes/simple/node')
22 files changed, 327 insertions, 222 deletions
diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index b08f749a..5eb0b0a3 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -29,7 +29,7 @@ public class AddNode extends Node { return TypeInteger.BOT; } - private static boolean overflow( long x, long y ) { + static boolean overflow( long x, long y ) { if( (x ^ y ) < 0 ) return false; // unequal signs, never overflow return (x ^ (x + y)) < 0; // sum has unequal signs, so overflow } @@ -37,6 +37,7 @@ public class AddNode extends Node { public Node idealize () { Node lhs = in(1); Node rhs = in(2); + if( rhs.err() != null ) return null; Type t2 = rhs._type; // Add of 0. We do not check for (0+x) because this will already diff --git a/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 06596ce0..e85fc6ae 100644 --- a/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -28,15 +28,6 @@ public abstract class CFGNode extends Node { // Block head is Start, Region, CProj, but not e.g. If, Return, Stop public boolean blockHead() { return false; } - // Should be exactly 1 tail from a block head - public CFGNode blockTail() { - assert blockHead(); - for( Node n : _outputs ) - if( n instanceof CFGNode cfg ) - return cfg; - return null; - } - // ------------------------------------------------------------------------ /** * Immediate dominator tree depth, used to approximate a real IDOM during @@ -71,24 +62,75 @@ public abstract class CFGNode extends Node { return lhs; } - // Loop nesting depth - public int _loopDepth; - public int loopDepth() { return _loopDepth==0 ? (_loopDepth = cfg(0).loopDepth()) : _loopDepth; } - // ------------------------------------------------------------------------ - // Support routines for Global Code Motion + // Loop nesting + public LoopNode loop() { return _ltree._head; } + public int loopDepth() { return _ltree==null ? 0 : _ltree.depth(); } + + LoopTree _ltree; + int _pre; // Pre-order numbers for loop tree finding + private static class LoopTree { + LoopTree _par; + final LoopNode _head; + int _depth; + LoopTree(LoopNode head) { _head = head; } + @Override public String toString() { return "LOOP"+_head._nid; } + int depth() { + return _depth==0 ? (_par==null ? 0 : (_depth = _par.depth()+1)) : _depth; + } + } - // Tik-tok recursion pattern. This method is final, and every caller does - // this work. - public final void walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { - if( visit.get(_nid) ) return; - visit.set(_nid); - _walkUnreach(visit,unreach); - unreach.remove(this); // Since we reached here... Node was not unreachable + // ------------------------------------------------------------------------ + // Tag all CFG Nodes with their containing LoopNode; LoopNodes themselves + // also refer to *their* containing LoopNode, as well as have their depth. + // Start is a LoopNode which contains all at depth 1. + public void buildLoopTree(StopNode stop) { + _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this); + _bltWalk(2,stop, new BitSet()); } + private int _bltWalk(int pre, StopNode stop, BitSet post) { + // Pre-walked? + if( _pre!=0 ) return pre; + _pre = pre++; + // Pre-walk + for( Node use : _outputs ) + if( use instanceof CFGNode usecfg ) + pre = usecfg._bltWalk(pre,stop,post); - // Tik-tok recursion pattern; not-final; callers override this. - void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { - cfg(0).walkUnreach(visit,unreach); + // Post-order work: find innermost loop + LoopTree inner = null, ltree; + for( Node use : _outputs ) { + if( !(use instanceof CFGNode usecfg) ) continue; + // Child visited but not post-visited? + if( !post.get(usecfg._nid) ) { + // Must be a backedge to a LoopNode then + ltree = usecfg._ltree = new LoopTree((LoopNode)usecfg); + } else { + // Take child's loop choice, which must exist + ltree = usecfg._ltree; + // If falling into a loop, use the target loop's parent instead + if( ltree._head == usecfg ) { + if( ltree._par == null ) + // This loop never had an If test choose to take its + // exit, i.e. it is a no-exit infinite loop. + ltree._par = ltree._head.forceExit(stop)._ltree; + ltree = ltree._par; + } + } + // Sort inner loops. The decision point is some branch far removed + // from either loop head OR either backedge so requires pre-order + // numbers to figure out innermost. + if( inner == null ) { inner = ltree; continue; } + if( inner == ltree ) continue; // No change + LoopTree outer = ltree._head._pre > inner._head._pre ? inner : ltree; + inner = ltree._head._pre > inner._head._pre ? ltree : inner; + inner._par = outer; + } + // Set selected loop + if( inner!=null ) + _ltree = inner; + // Tag as post-walked + post.set(_nid); + return pre; } } diff --git a/src/main/java/com/seaofnodes/simple/node/CProjNode.java b/src/main/java/com/seaofnodes/simple/node/CProjNode.java index cba63db8..53348b5a 100644 --- a/src/main/java/com/seaofnodes/simple/node/CProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CProjNode.java @@ -53,10 +53,6 @@ public class CProjNode extends CFGNode { } @Override - public Node getBlockStart() { - return ctrl() instanceof IfNode ? this : ctrl().getBlockStart(); - } - @Override boolean eq( Node n ) { return _idx == ((CProjNode)n)._idx; } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/DivFNode.java b/src/main/java/com/seaofnodes/simple/node/DivFNode.java index a3f4318d..c678ac3e 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivFNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivFNode.java @@ -29,7 +29,7 @@ public class DivFNode extends Node { Type t1 = lhs._type; Type t2 = rhs._type; - // Div of 1. + // Div of 1. if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==1 ) return lhs; diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index f21894dc..2b53b3a3 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -5,7 +5,6 @@ import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeTuple; -import java.util.BitSet; import java.util.HashSet; public class IfNode extends CFGNode implements MultiNode { @@ -40,6 +39,9 @@ public class IfNode extends CFGNode implements MultiNode { // Else true branch is reachable if( t.isConstant() ) return t.makeInit()==t ? TypeTuple.IF_FALSE : TypeTuple.IF_TRUE; + // Integers allow non-zero ranges: "1-65535" + if( t.makeZero().meet(t) != t ) + return TypeTuple.IF_TRUE; return TypeTuple.IF_BOTH; } @@ -57,12 +59,4 @@ public class IfNode extends CFGNode implements MultiNode { return null; } - @Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { - for( Node proj : _outputs ) - if( ((CProjNode)proj)._loopDepth == 0 ) - unreach.add((CProjNode)proj); - super._walkUnreach(visit,unreach); - } - - @Override public Node getBlockStart() { return ctrl().getBlockStart(); } } diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 8d604b28..85ad243b 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -53,8 +53,11 @@ public class LoadNode extends MemOpNode { @Override public Type compute() { Type t = MemMergeNode.contents(mem(),_alias,this); - // No constant folding if the pointer still needs a null check. - return err()==null ? _declaredType.join(t) : _declaredType; + // Update declared forward ref to the actual. + if( _declaredType.isFRef() && t instanceof TypeMemPtr tmp && !tmp.isFRef() ) + _declaredType = tmp.withAccess(((TypeMemPtr)_declaredType)._ro); + Type rez = err()==null ? _declaredType.join(t) : _declaredType; + return ptr()._type.isFinal() || _declaredType.isFinal() ? rez.makeRO() : rez; } @Override @@ -69,17 +72,19 @@ public class LoadNode extends MemOpNode { if( mem() instanceof StoreNode st && _alias==st._alias && ptr == st.ptr() && off() == st.off() ) { // Must check same object assert _name.equals(st._name); // Equiv class aliasing is perfect - return st.val(); + return castRO(st.val()); } // Simple Load-after-New on same address. if( mem() instanceof ProjNode p && p.in(0) instanceof NewNode nnn && ptr == nnn.proj(0) ) // Must check same object - return nnn.in(nnn.findAlias(_alias)); // Load from New init + return castRO(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. // "Provably unrelated" is really weak. + if( ptr instanceof ReadOnlyNode ro ) + ptr = ro.in(1); Node mem = mem(); outer: while( true ) { @@ -90,7 +95,7 @@ public class LoadNode extends MemOpNode { break; case StoreNode st: if( _alias==st._alias && ptr == st.ptr() && off() == st.off() ) - return st.val(); // Proved equal + return castRO(st.val()); // Proved equal // Can we prove unequal? Offsets do not overlap? if( _alias==st._alias && !off()._type.join(st.off()._type).isHigh() && // Offsets overlap !neverAlias(ptr,st.ptr()) ) // And might alias @@ -103,7 +108,7 @@ public class LoadNode extends MemOpNode { case ProjNode mproj: if( mproj.in(0) instanceof NewNode nnn1 ) { if( ptr instanceof ProjNode pproj && pproj.in(0) == mproj.in(0) ) - return nnn1.in(nnn1.findAlias(_alias)); // Load from New init + return castRO(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.mem();// Bypass unrelated New @@ -122,7 +127,11 @@ public class LoadNode extends MemOpNode { // else ptr.x = e1; : e1; // val = ptr.x; ptr.x = val; if( mem() instanceof MemPhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 && - off() instanceof ConstantNode ) { + // Offset can be hoisted + off() instanceof ConstantNode && + // Pointer can be hoisted + hoistPtr(ptr,memphi) ) { + // Profit on RHS/Loop backedge if( profit(memphi,2) || // Else must not be a loop to count profit on LHS. @@ -135,12 +144,14 @@ public class LoadNode extends MemOpNode { return null; } + private Node ld( int idx ) { Node mem = mem(), ptr = ptr(); LoadNode ld = new LoadNode(_name,_alias,_declaredType,mem.in(idx),ptr instanceof PhiNode && ptr.in(0)==mem.in(0) ? ptr.in(idx) : ptr,off()); ld.setDef(0,in(0)); return ld.peephole(); } + private static boolean neverAlias( Node ptr1, Node ptr2 ) { return ptr1.in(0) != ptr2.in(0) && // Unrelated allocations @@ -148,6 +159,25 @@ public class LoadNode extends MemOpNode { ptr2 instanceof ProjNode && ptr2.in(0) instanceof NewNode; } + private static boolean hoistPtr(Node ptr, PhiNode memphi ) { + // Can I hoist ptr above the Region? + if( !(memphi.region() instanceof RegionNode r) ) + return false; // Dead or dying Region/Phi + // If ptr from same Region, then yes, just use hoisted split pointers + if( ptr instanceof PhiNode pphi && pphi.region() == r ) + return true; + + // No, so can we lift this ptr? + CFGNode cptr = ptr.cfg0(); + if( cptr != null ) + // Pointer is controlled high + // TODO: Really needs to be the LCA of all inputs is high + return cptr.idepth() <= r.idepth(); + + // Dunno without a longer walk + return false; + } + // Profitable if we find a matching Store on this Phi arm. private boolean profit(PhiNode phi, int idx) { Node px = phi.in(idx); @@ -158,6 +188,13 @@ public class LoadNode extends MemOpNode { return false; } + // Read-Only is a deep property, and cannot be cast-away + private Node castRO(Node rez) { + if( (ptr()._type.isFinal() || _declaredType.isFinal()) && !rez._type.isFinal() ) + return new ReadOnlyNode(rez).peephole(); + return rez; + } + // Memory writers which must follow this read. A packaging node is not a // write, but can hide New's input, so follow this alias through aggregates. public ArrayList<Node> antiDeps() { diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java index a0e988dd..8fb6a4ce 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -32,38 +32,18 @@ public class LoopNode extends RegionNode { // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) @Override public CFGNode idom(Node dep) { return entry(); } - @Override public int loopDepth() { - if( _loopDepth!=0 ) return _loopDepth; // Was already set - _loopDepth = entry()._loopDepth+1; // Entry depth plus one - // One-time tag loop exits - for( CFGNode idom = back(); idom!=this; idom = idom.idom() ) { - // Walk idom in loop, setting depth - idom._loopDepth = _loopDepth; - // Loop exit hits the CProj before the If, instead of jumping from - // Region directly to If. - if( idom instanceof CProjNode proj ) { - assert proj.in(0) instanceof IfNode; // Loop exit test - // Find the loop exit CProj, and set loop_depth - for( Node use : proj.in(0)._outputs ) - if( use instanceof CProjNode proj2 && proj2 != idom ) - proj2._loopDepth = _loopDepth-1; - } - } - return _loopDepth; - } - // If this is an unreachable loop, it may not have an exit. If it does not // (i.e., infinite loop), force an exit to make it reachable. - public void forceExit( StopNode stop ) { + public StopNode forceExit( StopNode stop ) { // Walk the backedge, then immediate dominator tree util we hit this // Loop again. If we ever hit a CProj from an If (as opposed to // directly on the If) we found our exit. CFGNode x = back(); while( x != this ) { if( x instanceof CProjNode exit && exit.in(0) instanceof IfNode iff ) { - Node other = iff.cproj(1-exit._idx); - if( !(other.out(0) instanceof LoopNode loop) || loop.entry()==exit ) - return; // Found an exit, not an infinite loop + CFGNode other = iff.cproj(1-exit._idx); + if( other.loopDepth() < loopDepth() ) + return stop; // Found an exit, not an infinite loop } x = x.idom(); } @@ -76,5 +56,6 @@ public class LoopNode extends RegionNode { CProjNode f = new CProjNode(iff,1,"False"); setDef(2,f); stop.addDef(new ReturnNode(t,Parser.ZERO,null)); + return stop; } } diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 9c222ad2..0bf9b6ac 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.type.Field; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMemPtr; @@ -11,7 +10,9 @@ public abstract class MemOpNode extends Node { public final String _name; public final int _alias; - public final Type _declaredType; + // Declared type; not final because it might be a forward-reference + // which will be lazily improved when the reference is declared. + public Type _declaredType; public MemOpNode(String name, int alias, Type glb, Node mem, Node ptr, Node off) { super(null, mem, ptr, off); diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index bd8f71ad..b85af74e 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.Utils; public class MinusNode extends Node { @@ -16,7 +17,9 @@ public class MinusNode extends Node { public Type compute() { if( in(1)._type instanceof TypeInteger i0 ) { if( i0.isHigh() ) return TypeInteger.TOP; - return i0==TypeInteger.BOT ? TypeInteger.BOT : TypeInteger.make(-i0._max,-i0._min); + if( i0==TypeInteger.BOT || i0._min == Long.MIN_VALUE || i0._max == Long.MIN_VALUE ) + return TypeInteger.BOT; + return TypeInteger.make(-i0._max,-i0._min); } return in(1)._type.isHigh() ? TypeInteger.TOP : TypeInteger.BOT; } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index fa25b58a..e70fe495 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -110,7 +110,7 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable * @param new_def the new definition * @return new_def for flow coding */ - public Node setDef(int idx, Node new_def ) { + public <N extends Node> N setDef(int idx, N new_def ) { unlock(); Node old_def = in(idx); if( old_def == new_def ) return new_def; // No change @@ -221,6 +221,10 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable public <N extends Node> N unkeep() { delUse(null); return (N)this; } // Test "keep" status public boolean iskeep() { return _outputs.find(null) != -1; } + public void unkill() { + if( unkeep().isUnused() ) + kill(); + } // Replace self with nnn in the graph, making 'this' go dead public void subsume( Node nnn ) { @@ -232,6 +236,7 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable n._inputs.set(idx,nnn); n.moveDepsToWorklist(); // Rewiring can change a dependent query without changing type. nnn.addUse(n); + IterPeeps.addAll(n._outputs); } kill(); } @@ -366,7 +371,7 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable * And more folding: * <pre> ary + ((idx<<2) + 16)</pre> * And during code-gen: - * <pre> MOV4 Rary,Ridx,16 // or some such hardware-specific notation </pre> + * <pre> MOV4 Rary,[Ridx<<2 +16] // or some such hardware-specific notation </pre> * <p> * {@link #idealize} has a very specific calling convention: * <ul> @@ -497,9 +502,6 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable /** Is this Node Memory related */ public boolean isMem() { return false; } - /** Return block start from a isCFG() */ - public Node getBlockStart() { return null; } - // Semantic change to the graph (so NOT a peephole), used by the Parser. // If any input is a float, flip to a float-flavored opcode and widen any // non-float input. @@ -585,9 +587,8 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable private static final BitSet WVISIT = new BitSet(); final public <E> E walk( Function<Node,E> pred ) { assert WVISIT.isEmpty(); - E rez = _walk(pred); - WVISIT.clear(); - return rez; + try { return _walk(pred); } + finally { WVISIT.clear(); } } private <E> E _walk( Function<Node,E> pred ) { diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java index e388f4a3..b9cf4904 100644 --- a/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -18,20 +18,19 @@ public class NotNode extends Node { switch( t0 ) { 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) : TypeInteger.BOT; + return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : TypeInteger.BOOL; case TypeMemPtr p0: // top->top, bot->bot, null->1, *void->0, not-null ptr->0, ptr/nil->bot // If input in null then true // If input is not null ptr then false - if( p0 == TypeMemPtr.TOP ) return TypeInteger.TOP; - if( p0 == TypeMemPtr.NULLPTR ) return TypeInteger.constant(1); - if( !p0._nil ) return TypeInteger.constant(0); - return TypeInteger.BOT; + if( p0 == TypeMemPtr.NULLPTR ) return TypeInteger.TRUE; + if( !p0._nil ) return TypeInteger.FALSE; + return TypeInteger.BOOL; case Type t: if( t0.getClass() != Type.class ) // Only doing NOT on ints and ptrs throw Utils.TODO(); - return t0==Type.TOP ? TypeInteger.TOP : TypeInteger.BOT; + return TypeInteger.BOOL; } } diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 8479b4dc..942748e7 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 { // During parsing Phis have to be computed type pessimistically. if( r.inProgress() ) return _declaredType; // Set type to local top of the starting type - Type t = _declaredType.glb().dual(); + Type t = _declaredType.lub(); 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. @@ -82,7 +82,7 @@ public class PhiNode extends Node { if( in(2)._type == in(2)._type.makeInit() ) nullx = 2; if( nullx != -1 ) { Node val = in(3-nullx); - if( r.idom(this) instanceof IfNode iff && iff.pred().addDep(this)==val ) { + if( r.idom(this).addDep(this) instanceof IfNode iff && iff.pred().addDep(this)==val ) { // Must walk the idom on the null side to make sure we hit False. CFGNode idom = (CFGNode)r.in(nullx); while( idom.nIns() > 0 && idom.in(0) != iff ) idom = idom.idom(); diff --git a/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java b/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java new file mode 100644 index 00000000..fa4e0242 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java @@ -0,0 +1,26 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMemPtr; + + +/** + * Cast a pointer to read-only + */ +public class ReadOnlyNode extends Node { + public ReadOnlyNode( Node n ) { super(null,n); } + @Override public String label() { return "ReadOnly"; } + + @Override protected String format() { return "(const)%1"; } + @Override public Type compute() { + Type t = in(1)._type; + return t instanceof TypeMemPtr tmp ? tmp.makeRO() : t; + } + + @Override public Node idealize() { + if( in(1)._type instanceof TypeMemPtr tmp && tmp.isFinal() ) + return in(1); + return null; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 08f48a08..27866139 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -8,7 +8,6 @@ import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import java.util.ArrayList; import java.util.Arrays; -import java.util.BitSet; import java.util.HashSet; public class RegionNode extends CFGNode { @@ -19,7 +18,7 @@ public class RegionNode extends CFGNode { public String label() { return "Region"; } @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { - return p.p(label()).p(_nid); + return p.p(label()); } @Override public boolean isMultiHead() { return true; } @@ -73,65 +72,9 @@ public class RegionNode extends CFGNode { p1.in(0) instanceof IfNode iff ) return iff.ctrl(); - - // Look for direct uses of a guarded expression, and replace with the guard result. - if( !(idom() instanceof StartNode) && // Dead or dying - !(this instanceof LoopNode) ) { - VISIT.clear(); - boolean progress = false; - outer: - for( int i=1; i<nIns(); i++ ) { - CFGNode idom = cfg(i); - while( !(idom instanceof CProjNode cproj) ) { - idom = idom.idom(); - if( idom==null || idom.idepth() < idom().idepth() ) - continue outer; - } - if( cproj.cfg0() instanceof IfNode iff && cproj.compute()==Type.CONTROL ) { - VISIT.set(iff.pred()._nid); - for( Node out : _outputs ) - if( out instanceof PhiNode phi ) - progress |= walk(iff,cproj,phi.in(i)); - } - } - if( progress ) - return this; - } - return null; } - // A walk that can be cutoff early - private static final BitSet VISIT = new BitSet(); - 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; - if( n.in(0)!=null && n.cfg0().idepth() < iff.idepth() ) - 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<n.nIns(); i++ ) { - // Using a tested value - if( n.in(i) == pred && !(n instanceof CastNode) ) { - // Checking pred for T/F - Type t = pred._type; - Type tcast = cproj._idx==0 ? t.nonZero() : t.makeInit(); - if( t!=tcast ) { // Progress to cast - Node cast = new CastNode( tcast, cproj, pred ).peephole(); - n.setDef( i, cast ); - IterPeeps.add(n); - progress = true; - } else pred.addDep( this ); - } - if( n.in(i)!=null ) - progress |= walk(iff,cproj,n.in(i)); - } - return progress; - } - - private int findDeadInput() { for( int i=1; i<nIns(); i++ ) if( in(i)._type==Type.XCONTROL ) @@ -164,13 +107,6 @@ public class RegionNode extends CFGNode { return lca; } - @Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { - for( int i=1; i<nIns(); i++ ) - cfg(i).walkUnreach(visit,unreach); - } - - @Override public int loopDepth() { return _loopDepth==0 ? (_loopDepth = cfg(1).loopDepth()) : _loopDepth; } - // True if last input is null public final boolean inProgress() { return nIns()>1 && in(nIns()-1) == null; @@ -180,6 +116,4 @@ public class RegionNode extends CFGNode { @Override boolean eq( Node n ) { return !inProgress(); } - - @Override public Node getBlockStart() { return this; } } diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index eff33954..6c773c42 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -39,6 +39,4 @@ public class ReturnNode extends CFGNode { return ctrl(); return null; } - - @Override public Node getBlockStart() { return ctrl().getBlockStart(); } } diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 84937ad7..753abe90 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.Ary; import com.seaofnodes.simple.type.*; import java.util.*; @@ -21,19 +22,32 @@ public class ScopeNode extends Node { public static final String ARG0 = "arg"; public static final String MEM0 = "$mem"; - /** The tracked fields are now complex enough to deserve an array-of-structs layout + /** 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 final int _idx; // index in containing scope + public final String _name; // Declared name + private Type _type; // Declared type + public final boolean _final; // Final field public Var(int idx, String name, Type type, boolean xfinal) { _idx = idx; _name = name; _type = type; _final = xfinal; } + public Type type() { + if( !_type.isFRef() ) return _type; + // Update self to no longer use the forward ref type + Type def = Parser.TYPES.get(((TypeMemPtr)_type)._obj._name); + return (_type=_type.meet(def)); + } + public Type lazyGLB() { + Type t = type(); + return t instanceof TypeMemPtr ? t : t.glb(); + } + @Override public String toString() { + return _type.toString()+(_final ? " ": " !")+_name; + } } public Node in(Var v) { return in(v._idx); } @@ -47,13 +61,23 @@ public class ScopeNode extends Node { // Size of each nested lexical scope public final Ary<Integer> _lexSize; + // True if parsing inside of a constructor + public final Ary<Boolean> _inCons; + + // Extra guards; tested predicates and casted results + private final Ary<Node> _guards; // A new ScopeNode - public ScopeNode() { _type = Type.BOTTOM; _vars = new Ary<>(Var.class); _lexSize = new Ary<>(Integer.class); } + public ScopeNode() { + _type = Type.BOTTOM; + _vars = new Ary<>(Var .class); + _lexSize= new Ary<>(Integer.class); + _inCons = new Ary<>(Boolean.class); + _guards = new Ary<>(Node .class); + } @Override public String label() { return "Scope"; } - @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { p.p("Scope[ "); @@ -61,7 +85,7 @@ public class ScopeNode extends Node { for( int i=0; i<nIns(); i++ ) { if( j < _lexSize._len && i == _lexSize.at(j) ) { p.p("| "); j++; } Var v = _vars.get(i); - p.p(v._type); + p.p(v.type()); p.p(" "); if( v._final ) p.p("!"); p.p(v._name); @@ -92,17 +116,33 @@ public class ScopeNode extends Node { * * @return Node that was bound */ - public Node ctrl(Node n) { return setDef(0,n); } + public <N extends Node> N ctrl(N n) { return setDef(0,n); } - public void push() { + public void push() { push(false); } + public void push(boolean inCon) { + assert _lexSize._len==_inCons._len; _lexSize.push(_vars.size()); + _inCons.push(inCon); } public void pop() { + assert _lexSize._len==_inCons._len; int n = _lexSize.pop(); + _inCons.pop(); popUntil(n); _vars.setLen(n); } + // Allocation fields live in the scope immediately outside the constructor + // block. Nested blocks retain that permission; surrounding bindings do not. + public boolean canInit(Var v) { + for( int i=_inCons._len-1; i>0; i-- ) + if( _inCons.at(i) ) + return v._idx >= _lexSize.at(i-1) && v._idx < _lexSize.at(i); + return false; + } + + public boolean inCon() { return _inCons.last(); } + // 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. @@ -136,7 +176,7 @@ public class ScopeNode extends Node { 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); + return idx == -1 ? null : update(_vars.at(idx),null); } /** @@ -148,10 +188,10 @@ public class ScopeNode extends Node { public void update( String name, Node n ) { int idx = find(name); assert idx>=0; - _update(_vars.at(idx),n); + update(_vars.at(idx),n); } - Var _update( ScopeNode.Var v, Node st ) { + public Var update( ScopeNode.Var v, Node st ) { Node old = in(v._idx); if( old instanceof ScopeNode loop ) { // Lazy Phi! @@ -162,7 +202,7 @@ public class ScopeNode extends Node { // 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(v._idx,PhiNode.make(v._name, v._type instanceof TypeMemPtr ? v._type : v._type.glb(), loop.ctrl(), loop.in(loop._update(v,null)._idx),null).peephole()); + : loop.setDef(v._idx,PhiNode.make(v._name, v.lazyGLB(), loop.ctrl(), loop.in(loop.update(v,null)._idx),null).peephole()); setDef(v._idx,old); } if( st!=null ) setDef(v._idx,st); // Set new value @@ -189,8 +229,15 @@ 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 - dup._vars.addAll(_vars); + dup._vars .addAll(_vars ); dup._lexSize.addAll(_lexSize); + dup._inCons .addAll(_inCons ); + dup._guards .addAll(_guards ); + // The dup'd guards all need dup'd keepers, to keep proper accounting + // when later removing all guards + for( Node n : _guards ) + if( !(n instanceof CFGNode) ) + n.keep(); dup.addDef(ctrl()); // Control input is just copied // Memory is one binding, with the same lazy loop Phi as scalar names. @@ -207,12 +254,12 @@ public class ScopeNode extends Node { * @param that The ScopeNode to be merged into this * @return A new node representing the merge point */ - public Node mergeScopes(ScopeNode that) { + public RegionNode mergeScopes(ScopeNode that) { RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).keep()); _merge(that,r); that.kill(); // Kill merged scope IterPeeps.add(r); - return r.unkeep().peephole(); + return r.unkeep(); } private void _merge(ScopeNode that, RegionNode r) { @@ -221,9 +268,9 @@ public class ScopeNode extends Node { // 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.in(this._update(v,null)); - Node rhs = that.in(that._update(v,null)); - setDef(i, PhiNode.make(v._name, v._type, r, lhs, rhs).peephole()); + Node lhs = this.in(this.update(v,null)); + Node rhs = that.in(that.update(v,null)); + setDef(i, PhiNode.make(v._name, v.type(), r, lhs, rhs).peephole()); } } @@ -273,50 +320,91 @@ public class ScopeNode extends Node { // Up-casting: using the results of an If to improve a value. // E.g. "if( ptr ) ptr.field;" is legal because ptr is known not-null. + public void addGuards( Node ctrl, Node pred, boolean invert ) { + assert ctrl instanceof CFGNode; + _guards.add(ctrl); // Marker between guard sets + // add pred & its cast to the normal input list, with special Vars + if( ctrl._type == Type.XCONTROL || pred==null || pred.isDead() ) + return; // Dead, do not add any guards + _addGuards(ctrl,pred,invert); + } - // This Scope looks for direct variable uses, or certain simple - // combinations, and replaces the variable with the upcast variant. - public Node upcast( Node ctrl, Node pred, boolean invert ) { - if( ctrl._type==Type.XCONTROL ) return null; + private void _addGuards( Node ctrl, Node pred, boolean invert ) { + if( pred==null || pred.isDead() ) + return; // A single negation is handled below. For !!p (including p != null), // also refine the underlying p without changing the Boolean result. if( pred instanceof NotNode not && not.in(1) instanceof NotNode ) { pred.keep(); // Recursive peepholes may rediscover this Not. - upcast(ctrl,not.in(1),!invert); + _addGuards(ctrl,not.in(1),!invert); pred.unkeep(); } // Invert the If conditional if( invert ) pred = pred instanceof NotNode not ? not.in(1) : IterPeeps.add(new NotNode(pred).peephole()); - - // Direct use of a value as predicate. This is a zero/null test. - if( _inputs.find(pred) != -1 ) { - if( !(pred._type instanceof TypeMemPtr tmp) ) - // Must be an `int`, since int and ptr are the only two value types - // being tested. No representation for a generic not-null int, so no upcast. - return null; - if( tmp.isa(TypeMemPtr.VOIDPTR) ) - return null; // Already not-null, no reason to upcast - // Upcast the ptr to not-null ptr, and replace in scope - return replace(pred,new CastNode(TypeMemPtr.VOIDPTR,ctrl,pred).peephole()); + // This is a zero/null test. + // Compute the positive test type. + Type tnz = pred._type.nonZero(); + Type tcast = tnz.join(pred._type); + if( tcast != pred._type ) { + Node cast = new CastNode(tnz,ctrl,pred.keep()).peephole().keep(); + _guards.add(pred); + _guards.add(cast); + replace(pred,cast); } + // Compute the negative test type. if( pred instanceof NotNode not ) { - // Direct use of a !value as predicate. This is a zero/null test. - if( _inputs.find(not.in(1)) != -1 ) { - Type tinit = not.in(1)._type.makeInit(); - if( not.in(1)._type.isa(tinit) ) return null; // Already zero/null, no reason to upcast - return replace(not.in(1), new ConstantNode(tinit).peephole()); + Node npred = not.in(1); + Type tzero = npred._type.makeZero(); + Type tzcast= tzero.join(npred._type); + if( tzcast != npred._type ) { + Node cast = new CastNode(tzero,ctrl,npred.keep()).peephole().keep(); + _guards.add(npred); + _guards.add( cast); + replace(npred,cast); } } - // Apr/9/2024: Attempted to replace X with Y if guarded by a test of - // X==Y. This didn't seem to help very much, or at least in the test - // cases seen so far was a very minor help. + } - // No upcast - return null; + // Remove matching pred/cast pairs from this guarded region. + public void removeGuards( Node ctrl ) { + assert ctrl instanceof CFGNode; + // Pop the guards up to this region's marker. + while( true ) { + Node g = _guards.pop(); + if( g == ctrl ) break; + if( g instanceof CFGNode ) continue; + g .unkill(); // Pop/kill cast + _guards.pop().unkill(); // Pop/kill pred + } } + // If we find a guarded instance of pred, replace with the upcasted version + public Node upcastGuard( Node pred ) { + // If finding an instanceof pred, replace with cast. + // Otherwise, just pred itself. + int i = _guards._len; + while( i > 0 ) { + Node cast = _guards.at(--i); + if( cast instanceof CFGNode ) continue; // Marker between guard sets + Node xpred = _guards.at(--i); + if( xpred == pred ) + return cast; + } + return pred; + } + + // Kill guards also + @Override public void kill() { + for( Node n : _guards ) + if( !(n instanceof CFGNode) ) + n.unkill(); + _guards.clear(); + super.kill(); + } + + private Node replace( Node old, Node cast ) { assert old!=null && old!=cast; for( int i=0; i<nIns(); i++ ) diff --git a/src/main/java/com/seaofnodes/simple/node/ShlNode.java b/src/main/java/com/seaofnodes/simple/node/ShlNode.java index 4d673056..65dfe684 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShlNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -37,7 +37,7 @@ public class ShlNode extends Node { if( (shl.value()&63)==0 ) return lhs; // (x + c) << i => (x << i) + (c << i) - if( lhs instanceof AddNode add && add.in(2)._type instanceof TypeInteger c && c.isConstant() && c!=TypeInteger.ZERO ) { + if( lhs instanceof AddNode add && add.addDep(this).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 bc6881f1..757fd69e 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -42,4 +42,9 @@ public class ShrNode extends Node { return null; } @Override Node copy(Node lhs, Node rhs) { return new ShrNode(lhs,rhs); } + @Override String err() { + if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '>>>' " + in(1)._type; + if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '>>>' " + in(2)._type; + return null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index 23830a18..cefa2d72 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -3,16 +3,15 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.*; -import java.util.BitSet; import java.util.HashSet; import static com.seaofnodes.simple.Utils.TODO; /** Start supplies control, whole memory, and the argument, in that order. */ -public class StartNode extends CFGNode implements MultiNode { +public class StartNode extends LoopNode implements MultiNode { final Type _arg; - public StartNode(Type arg) { super(); _arg = arg; _type = compute(); } + public StartNode(Type arg) { super(null); _arg = arg; _type = compute(); } @Override public String label() { return "Start"; } @@ -34,9 +33,4 @@ public class StartNode extends CFGNode implements MultiNode { @Override public int idepth() { return 0; } @Override public CFGNode idom(Node dep) { return null; } - @Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { } - - @Override public int loopDepth() { return (_loopDepth=1); } - - @Override public Node getBlockStart() { return this; } } diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java index 202afbd2..d0eb5750 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -2,9 +2,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; -import com.seaofnodes.simple.Parser; - import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.GlobalCodeMotion; @@ -65,8 +64,6 @@ public class StopNode extends CFGNode { } @Override public CFGNode idom(Node dep) { return null; } - @Override public int loopDepth() { return (_loopDepth=1); } - public Node addReturn(Node node) { return addDef(node); } @@ -84,12 +81,9 @@ public class StopNode extends CFGNode { return this; } StopNode GCM() { - // Break infinite loops, forcing a Never-branch to exit - GlobalCodeMotion.fixLoops(this); + Parser.START.buildLoopTree(this); GlobalCodeMotion.buildCFG(this); return this; } - - @Override public Node getBlockStart() { return this; } } diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 8eb104a7..a5f04dd2 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -44,7 +44,10 @@ public class StoreNode extends MemOpNode { @Override public Type compute() { - Type t = val()._type.meet(MemMergeNode.contents(mem(),_alias,this)); + Type val = val()._type; + if( _declaredType.isFRef() && val instanceof TypeMemPtr tmp && !tmp.isFRef() ) + _declaredType = tmp; + Type t = val.join(_declaredType).meet(MemMergeNode.contents(mem(),_alias,this)); return TypeMem.make(_alias,t); } @@ -113,6 +116,9 @@ public class StoreNode extends MemOpNode { String err() { String err = super.err(); if( err != null ) return err; + TypeMemPtr tmp = (TypeMemPtr)ptr()._type; + if( tmp._ro || tmp._obj.field(_name)._final ) + return "Cannot modify final field '"+_name+"'"; Type t = val()._type; return _init || t.isa(_declaredType) ? null : "Cannot store "+t+" into field "+_declaredType+" "+_name; } diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index 134f7cd6..768cb2bf 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -22,6 +22,11 @@ public class SubNode extends Node { t2 instanceof TypeInteger i2 ) { if (i1.isConstant() && i2.isConstant()) return TypeInteger.constant(i1.value()-i2.value()); + // Fold ranges like {2-3} - {0-1} into {1-3}. + if( !AddNode.overflow(i1._min,-i2._max) && + !AddNode.overflow(i1._max,-i2._min) && + i2._min != Long.MIN_VALUE ) + return TypeInteger.make(i1._min-i2._max,i1._max-i2._min); } // Sub of same is 0 if( in(1)==in(2) ) |