From b0e1da2a7d0d39347e247d9fbda924b720d4b0a0 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 21 Oct 2024 09:25:15 -0700 Subject: Chapter 17: Syntax Sugar --- .../java/com/seaofnodes/simple/node/AddNode.java | 2 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 90 +++++++++---- .../java/com/seaofnodes/simple/node/CProjNode.java | 4 - .../java/com/seaofnodes/simple/node/IfNode.java | 11 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 53 +++++++- .../java/com/seaofnodes/simple/node/LoopNode.java | 29 +---- .../java/com/seaofnodes/simple/node/MemOpNode.java | 5 +- .../java/com/seaofnodes/simple/node/MinusNode.java | 5 +- src/main/java/com/seaofnodes/simple/node/Node.java | 12 +- .../java/com/seaofnodes/simple/node/NotNode.java | 9 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 4 +- .../com/seaofnodes/simple/node/ReadOnlyNode.java | 29 +++++ .../com/seaofnodes/simple/node/RegionNode.java | 67 +--------- .../com/seaofnodes/simple/node/ReturnNode.java | 2 - .../com/seaofnodes/simple/node/ScopeMinNode.java | 21 ++- .../java/com/seaofnodes/simple/node/ScopeNode.java | 141 +++++++++++++++------ .../java/com/seaofnodes/simple/node/ShlNode.java | 2 +- .../java/com/seaofnodes/simple/node/StartNode.java | 9 +- .../java/com/seaofnodes/simple/node/StopNode.java | 8 +- .../java/com/seaofnodes/simple/node/StoreNode.java | 15 ++- .../java/com/seaofnodes/simple/node/SubNode.java | 5 + 21 files changed, 309 insertions(+), 214 deletions(-) create mode 100644 src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java (limited to 'src/main/java/com/seaofnodes/simple/node') diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index f3b213fb..0834a381 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -36,7 +36,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 } diff --git a/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 9e9d6970..052ad8fc 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 @@ -64,27 +55,78 @@ 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; } - // Anti-dependence field support public int _anti; // Per-CFG field to help find anti-deps // ------------------------------------------------------------------------ - // 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 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 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 3d6fd1fa..d2f1bbe1 100644 --- a/src/main/java/com/seaofnodes/simple/node/CProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CProjNode.java @@ -51,10 +51,6 @@ public class CProjNode extends CFGNode { return null; } - @Override - public Node getBlockStart() { - return ctrl() instanceof IfNode ? this : ctrl().getBlockStart(); - } @Override boolean eq( Node n ) { return _idx == ((CProjNode)n)._idx; } diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 3cce89ab..513b4721 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -43,6 +43,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; } @@ -60,12 +63,4 @@ public class IfNode extends CFGNode implements MultiNode { return null; } - @Override void _walkUnreach( BitSet visit, HashSet 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 d15d4f83..1528f2e9 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -33,10 +33,13 @@ public class LoadNode extends MemOpNode { @Override public Type compute() { - if( mem()._type instanceof TypeMem mem && - // No constant folding if ptr might null-check - _declaredType != mem._t && err()==null ) { - return _declaredType.join(mem._t); + if( mem()._type instanceof TypeMem mem ) { + // Update declared forward ref to the actual + if( _declaredType.isFRef() && mem._t instanceof TypeMemPtr tmp && !tmp.isFRef() ) + _declaredType = tmp; + // No lifting if ptr might null-check + if( err()==null ) + return _declaredType.join(mem._t); } return _declaredType; } @@ -60,13 +63,15 @@ public class LoadNode extends MemOpNode { // 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 ) { switch( mem ) { case StoreNode st: if( 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( !off()._type.join(st.off()._type).isHigh() && // Offsets overlap !neverAlias(ptr,st.ptr()) ) // And might alias @@ -79,11 +84,13 @@ 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.in(_alias);// Bypass unrelated New break; + } else if( mproj.in(0) instanceof StartNode ) { + break outer; } else throw Utils.TODO(); default: throw Utils.TODO(); @@ -98,7 +105,11 @@ public class LoadNode extends MemOpNode { // else ptr.x = e1; : e1; // val = ptr.x; ptr.x = val; if( mem() instanceof PhiNode 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. @@ -111,10 +122,12 @@ public class LoadNode extends MemOpNode { return null; } + private Node ld( int idx ) { Node mem = mem(), ptr = ptr(); return new LoadNode(_name,_alias,_declaredType,mem.in(idx),ptr instanceof PhiNode && ptr.in(0)==mem.in(0) ? ptr.in(idx) : ptr, off()).peephole(); } + private static boolean neverAlias( Node ptr1, Node ptr2 ) { return ptr1.in(0) != ptr2.in(0) && // Unrelated allocations @@ -122,6 +135,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); @@ -130,4 +162,11 @@ public class LoadNode extends MemOpNode { if( px instanceof StoreNode st1 && ptr()==st1.ptr() && off()==st1.off() ) { px.addDep(this); return true; } return false; } + + // Read-Only is a deep property, and cannot be cast-away + private Node castRO(Node rez) { + if( ptr()._type.isFinal() && !rez._type.isFinal() ) + return new ReadOnlyNode(rez).peephole(); + return rez; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 22862cb9..ecda9c63 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 c7a1efec..82aab8ac 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 8a2c9406..760a4274 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.Utils; import java.util.BitSet; @@ -22,7 +23,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 TypeInteger.TOP.meet(in(1)._type); } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 462a403c..3827fdac 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -153,7 +153,7 @@ public abstract class Node implements OutNode { * @param new_def the new definition * @return new_def for flow coding */ - public Node setDef(int idx, Node new_def ) { + public N setDef(int idx, N new_def ) { unlock(); Node old_def = in(idx); if( old_def == new_def ) return new_def; // No change @@ -267,6 +267,10 @@ public abstract class Node implements OutNode { } // 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 @@ -278,6 +282,7 @@ public abstract class Node implements OutNode { int idx = n._inputs.find(this); n._inputs.set(idx,nnn); nnn.addUse(n); + IterPeeps.addAll(n._outputs); } kill(); } @@ -419,7 +424,7 @@ public abstract class Node implements OutNode { * And more folding: * 
   ary + ((idx<<2) + 16)
* And during code-gen: - * 
   MOV4 Rary,Ridx,16 // or some such hardware-specific notation
+ * 
   MOV4 Rary,[Ridx<<2 +16] // or some such hardware-specific notation
*

* {@link #idealize} has a very specific calling convention: *

    @@ -542,9 +547,6 @@ public abstract class Node implements OutNode { /** Is this Node Memory related */ public boolean isMem() { return false; } - /** Return block start from a isCFG() */ - public Node getBlockStart() { return null; } - /** Pinned in the schedule; these are data nodes whose input#0 is not allowed to change */ public boolean isPinned() { return false; } diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java index ffd3e01e..664d7c7b 100644 --- a/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -28,15 +28,14 @@ public class NotNode extends Node { // 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 ? Type.TOP : Type.BOTTOM; + 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 f0140ce6..cb266ca3 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -47,7 +47,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. @@ -101,7 +101,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..fddcaa67 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java @@ -0,0 +1,29 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMemPtr; + +import java.util.BitSet; + +/** + * 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 + StringBuilder _print1(StringBuilder sb, BitSet visited) { + return in(1)._print0(sb.append("(const)"),visited); + } + @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 941de76b..fb39af17 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -18,7 +18,7 @@ public class RegionNode extends CFGNode { @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { - return sb.append(label()).append(_nid); + return sb.append(label()); } @Override public boolean isMultiHead() { return true; } @@ -72,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 unreach ) { - for( int i=1; i1 && in(nIns()-1) == null; @@ -180,6 +117,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 de4eba52..b586a44f 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -47,6 +47,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/ScopeMinNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java index e4874e15..9134f9c3 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java @@ -14,16 +14,29 @@ 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 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 ScopeMinNode() { _type = TypeMem.BOT; } diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 11e54d82..86aa7665 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,8 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.IterPeeps; -import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.Ary; import com.seaofnodes.simple.type.*; import java.util.*; @@ -29,13 +27,22 @@ public class ScopeNode extends ScopeMinNode { // Since of each nested lexical scope public final Ary _lexSize; + // True if parsing inside of a constructor + public final Ary _inCons; + + // Extra guards; tested predicates and casted results + private final Ary _guards; // A new ScopeNode - public ScopeNode() { _vars = new Ary<>(Var.class); _lexSize = new Ary<>(Integer.class); } + public ScopeNode() { + _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 StringBuilder _print1(StringBuilder sb, BitSet visited) { sb.append("Scope[ "); @@ -43,7 +50,7 @@ public class ScopeNode extends ScopeMinNode { for( int i=0; i 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); } + 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. @@ -125,7 +139,7 @@ public class ScopeNode extends ScopeMinNode { 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); } /** @@ -137,10 +151,10 @@ public class ScopeNode extends ScopeMinNode { 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! @@ -151,7 +165,7 @@ public class ScopeNode extends ScopeMinNode { // 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,new PhiNode(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,new PhiNode(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 @@ -178,8 +192,15 @@ public class ScopeNode extends ScopeMinNode { // 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 input is a shallow copy @@ -208,13 +229,13 @@ public class ScopeNode extends ScopeMinNode { * @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()); mem()._merge(that.mem(),r); this ._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) { @@ -223,9 +244,9 @@ public class ScopeNode extends ScopeMinNode { // 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, new PhiNode(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, new PhiNode(v._name, v.type(), r, lhs, rhs).peephole()); } } @@ -264,42 +285,78 @@ public class ScopeNode extends ScopeMinNode { // 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. - - // 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 ) { + public void addGuards( Node ctrl, Node pred, boolean invert ) { + assert ctrl instanceof CFGNode; + _guards.add(ctrl); // Marker to distinguish 0,1,2 guards + // 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 // 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. + } + + // Remove matching pred/cast pairs from this guarded region. + public void removeGuards( Node ctrl ) { + assert ctrl instanceof CFGNode; + // 0,1 or 2 guards + 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 + } + } - // No upcast - return null; + // 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 (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/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index c03a4b06..ab6e4931 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -14,11 +14,11 @@ import static com.seaofnodes.simple.Utils.TODO; * In ch10 we also add mem aliases as structs get defined; each field in struct * adds a distinct alias to Start's tuple. */ -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"; } @@ -41,9 +41,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 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 0eacc1f4..867225cb 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.GlobalCodeMotion; import com.seaofnodes.simple.GraphVisualizer; @@ -63,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); } @@ -77,13 +76,10 @@ public class StopNode extends CFGNode { return this; } StopNode GCM(boolean show) { - // Break infinite loops, forcing a Never-branch to exit - GlobalCodeMotion.fixLoops(this); + Parser.START.buildLoopTree(this); if( show ) System.out.println(new GraphVisualizer().generateDotOutput(this,null,null)); 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 7b1bddd5..62b49a1a 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -42,9 +42,15 @@ public class StoreNode extends MemOpNode { public Type compute() { Type val = val()._type; TypeMem mem = (TypeMem)mem()._type; // Invariant - Type t = mem._alias==_alias - ? val.meet(mem._t) // Meet into existing memory - : Type.BOTTOM; + Type t = Type.BOTTOM; // No idea on field contents + // Same alias, lift val to the declared type and then meet into other fields + if( mem._alias == _alias ) { + // Update declared forward ref to the actual + if( _declaredType.isFRef() && val instanceof TypeMemPtr tmp && !tmp.isFRef() ) + _declaredType = tmp; + val = val.join(_declaredType); + t = val.meet(mem._t); + } return TypeMem.make(_alias,t); } @@ -108,6 +114,9 @@ public class StoreNode extends MemOpNode { String err() { String err = super.err(); if( err != null ) return err; + TypeMemPtr tmp = (TypeMemPtr)ptr()._type; + if( 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 009fb30e..5d6c2643 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -29,6 +29,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) ) -- cgit v1.2.3