diff options
Diffstat (limited to 'src/main/java/com/seaofnodes/simple/node')
21 files changed, 360 insertions, 99 deletions
diff --git a/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/src/main/java/com/seaofnodes/simple/node/CFGNode.java new file mode 100644 index 00000000..b605071b --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -0,0 +1,92 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.Utils; + +import java.util.BitSet; +import java.util.HashSet; +import java.util.HashMap; + +/** Control Flow Graph Nodes + * <p> + * CFG nodes have a immediate dominator depth (idepth) and a loop nesting + * depth(loop_depth). + * <p> + * idepth is computed lazily upon first request, and is valid even in the + * Parser, and is used by peepholes during parsing and afterward. + * <p> + * loop_depth is computed after optimization as part of scheduling. + * + */ +public abstract class CFGNode extends Node { + + public CFGNode(Node... nodes) { super(nodes); } + + @Override public boolean isCFG() { return true; } + @Override public boolean isPinned() { return true; } + + public CFGNode cfg(int idx) { return (CFGNode)in(idx); } + + // 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 + * parsing where we do not have the whole program, and also peepholes + * change the CFG incrementally. + * <p> + * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} + */ + public int _idepth; + public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + + // Return the immediate dominator of this Node and compute dom tree depth. + public CFGNode idom() { return cfg(0); } + + // Return the LCA of two idoms + public CFGNode idom(CFGNode rhs) { + if( rhs==null ) return this; + CFGNode lhs = this; + while( lhs != rhs ) { + var comp = lhs.idepth() - rhs.idepth(); + if( comp >= 0 ) lhs = lhs.idom(); + if( comp <= 0 ) rhs = rhs.idom(); + } + 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 + + // 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 + } + + // Tik-tok recursion pattern; not-final; callers override this. + void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { + cfg(0).walkUnreach(visit,unreach); + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/CProjNode.java b/src/main/java/com/seaofnodes/simple/node/CProjNode.java new file mode 100644 index 00000000..fb0ff879 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/CProjNode.java @@ -0,0 +1,61 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; +import com.seaofnodes.simple.type.TypeTuple; +import java.util.BitSet; + +public class CProjNode extends CFGNode { + + // Which slice of the incoming multipart value + public final int _idx; + + // Debugging label + public final String _label; + + public CProjNode(Node ctrl, int idx, String label) { + super(ctrl); + _idx = idx; + _label = label; + } + + @Override public String label() { return _label; } + + @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(_label); } + + @Override public boolean isMultiTail() { return in(0).isMultiHead(); } + @Override public boolean blockHead() { return true; } + + public CFGNode ctrl() { return cfg(0); } + + @Override + public Type compute() { + Type t = ctrl()._type; + return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; + } + + @Override + public Node idealize() { + if ( ctrl() instanceof IfNode iff ) { + if ( iff._type instanceof TypeTuple tt && tt._types[1 - _idx] == Type.XCONTROL ) + return iff.in(0); // We become our input control + + // Flip a negating if-test, to remove the not + if( iff.pred().addDep(this) instanceof NotNode not ) + return new CProjNode(new IfNode(iff.ctrl(),not.in(1)).peephole(),1-_idx,_idx==0 ? "False" : "True"); + } + return null; + } + + @Override + public Node getBlockStart() { + return ctrl() instanceof IfNode ? this : ctrl().getBlockStart(); + } + @Override + boolean eq( Node n ) { return _idx == ((CProjNode)n)._idx; } + + @Override + int hash() { return _idx; } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index ca42c2dc..cf1a76b0 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -36,6 +36,8 @@ public class ConstantNode extends Node { } @Override public boolean isMultiTail() { return true; } + // The special forever-zero is pinned, all others can sink + @Override public boolean isPinned() { return this==Parser.ZERO; } @Override public Type compute() { return _con; } diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 1cf4ddaf..5457ac6e 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -5,8 +5,9 @@ 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 MultiNode { +public class IfNode extends CFGNode implements MultiNode { public IfNode(Node ctrl, Node pred) { super(ctrl, pred); @@ -22,7 +23,6 @@ public class IfNode extends MultiNode { return in(1)._print0(sb, visited).append(" )"); } - @Override public boolean isCFG() { return true; } @Override public boolean isMultiHead() { return true; } public Node ctrl() { return in(0); } @@ -52,11 +52,20 @@ public class IfNode extends MultiNode { // Hunt up the immediate dominator tree. If we find an identical if // test on either the true or false branch, that side wins. if( !pred()._type.isHighOrConst() ) - for( Node dom = idom(), prior=this; dom!=null; prior = dom, dom = dom.idom() ) - if( dom.addDep(this) instanceof IfNode iff && iff.pred().addDep(this)==pred() && prior instanceof ProjNode prj ) { + for( CFGNode dom = idom(), prior=this; dom!=null; prior = dom, dom = dom.idom() ) + if( dom.addDep(this) instanceof IfNode iff && iff.pred().addDep(this)==pred() && prior instanceof CProjNode prj ) { setDef(1,new ConstantNode(TypeInteger.make(true,prj._idx==0?1:0)).peephole()); return this; } 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 53ae1096..296237f4 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -21,7 +21,7 @@ public class LoadNode extends MemOpNode { * @param memPtr The ptr to the struct from where we load a field */ public LoadNode(String name, int alias, Type glb, Node memSlice, Node memPtr) { - super(name, alias, memSlice, memPtr, null); + super(name, alias, null, memSlice, memPtr); _declaredType = glb; } @@ -45,7 +45,7 @@ public class LoadNode extends MemOpNode { // Simple Load-after-Store on same address. if( mem() instanceof StoreNode st && ptr() == st.ptr() ) { // Must check same object - assert Utils.eq(_name,st._name); // Equiv class aliasing is perfect + assert _name.equals(st._name); // Equiv class aliasing is perfect return st.val(); } diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java index ea1489c4..c662dee6 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -1,15 +1,17 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; - +import com.seaofnodes.simple.type.TypeInteger; import java.util.BitSet; +import java.util.HashSet; public class LoopNode extends RegionNode { - public LoopNode( Node entry ) { super(null,entry,null); } - Node entry() { return in(1); } - Node back () { return in(2); } + public CFGNode entry() { return cfg(1); } + public CFGNode back () { return cfg(2); } @Override public String label() { return "Loop"; } @@ -25,7 +27,51 @@ public class LoopNode extends RegionNode { return inProgress() ? null : super.idealize(); } - // Bypass Region idom, same as the default idom() using use entry in(1) instead of in(0) - @Override int idepth() { return _idepth(1); } - @Override Node idom() { return entry(); } + // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) + @Override public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) + @Override public CFGNode idom() { 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 ) { + // 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 ) + return; // Found an exit, not an infinite loop + x = x.idom(); + } + // Found a no-exit loop. Insert an exit + NeverNode iff = new NeverNode(back()); + for( Node use : _outputs ) + if( use instanceof PhiNode phi ) + iff.addDef(use); + CProjNode t = new CProjNode(iff,0,"True" ); + CProjNode f = new CProjNode(iff,1,"False"); + setDef(2,f); + stop.addDef(new ReturnNode(t,Parser.ZERO,null)); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 08e08bbf..551d2aa9 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -12,8 +12,8 @@ public abstract class MemOpNode extends Node { public final String _name; public final int _alias; - public MemOpNode(String name, int alias, Node memSlice, Node memPtr, Node value) { - super(null, memSlice, memPtr, value); + public MemOpNode(String name, int alias, Node... nodes) { + super(nodes); _name = name; _alias = alias; } diff --git a/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/src/main/java/com/seaofnodes/simple/node/MultiNode.java index 2743bd19..379e140d 100644 --- a/src/main/java/com/seaofnodes/simple/node/MultiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MultiNode.java @@ -1,12 +1,10 @@ package com.seaofnodes.simple.node; -public abstract class MultiNode extends Node { - - public MultiNode(Node... inputs) { super(inputs); } +public interface MultiNode extends OutNode { // Find a projection by index - ProjNode proj( int idx ) { - for( Node out : _outputs ) + default ProjNode proj( int idx ) { + for( Node out : outs() ) if( out instanceof ProjNode prj && prj._idx==idx ) return prj; return null; diff --git a/src/main/java/com/seaofnodes/simple/node/NeverNode.java b/src/main/java/com/seaofnodes/simple/node/NeverNode.java new file mode 100644 index 00000000..f50d3503 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/NeverNode.java @@ -0,0 +1,19 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.type.Type; +import java.util.BitSet; + +// "Never true" for infinite loop exits +public class NeverNode extends IfNode { + public NeverNode(Node ctrl) { super(ctrl,Parser.ZERO); } + + @Override public String label() { return "Never"; } + + @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append("Never"); } + + @Override public Type compute() { return TypeInteger.BOT; } + + @Override public Node idealize() { return null; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/NewNode.java b/src/main/java/com/seaofnodes/simple/node/NewNode.java index 352689b5..0724ec56 100644 --- a/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -26,6 +26,8 @@ public class NewNode extends Node { return sb.append(_ptr._obj.str()); } + @Override public boolean isPinned() { return true; } + @Override public Type compute() { return _ptr; } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index bb698860..fc49ad6a 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.IRPrinter; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; @@ -13,7 +14,7 @@ import java.util.function.Function; * The Node class provides common functionality used by all subtypes. * Subtypes of Node specialize by overriding methods. */ -public abstract class Node { +public abstract class Node implements OutNode { /** * Each node has a unique dense Node ID within a compilation context @@ -128,6 +129,7 @@ public abstract class Node { */ public Node in(int i) { return _inputs.get(i); } public Node out(int i) { return _outputs.get(i); } + @Override public ArrayList<Node> outs() { return _outputs; } public int nIns() { return _inputs.size(); } @@ -135,9 +137,7 @@ public abstract class Node { public boolean isUnused() { return nOuts() == 0; } - public boolean isCFG() { return false; } - - public boolean isMem() { return false; } + public CFGNode cfg0() { return (CFGNode)in(0); } /** * Change a <em>def</em> into a Node. Keeps the edges correct, by removing @@ -164,11 +164,11 @@ public abstract class Node { // the new_def might get killed if the old node kills it recursively. if( new_def != null ) new_def.addUse(this); + // Set the new_def over the old (killed) edge + _inputs.set(idx,new_def); if( old_def != null && // If the old def exists, remove a def->use edge old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def - // Set the new_def over the old (killed) edge - _inputs.set(idx,new_def); moveDepsToWorklist(); // Return self for easy flow-coding return new_def; @@ -196,7 +196,7 @@ public abstract class Node { * @param new_def the new definition, appended to the end of existing definitions * @return new_def for flow coding */ - Node addDef(Node new_def) { + public Node addDef(Node new_def) { unlock(); // Add use->def edge _inputs.add(new_def); @@ -323,8 +323,8 @@ public abstract class Node { Type old = setType(compute()); // Replace constant computations from non-constants with a constant node - if( !(this instanceof ConstantNode) && _type.isHighOrConst() ) - return new ConstantNode(_type).peepholeOpt(); + if( !(this instanceof ConstantNode) && !(this instanceof XCtrlNode) && _type.isHighOrConst() ) + return (_type==Type.XCONTROL ? new XCtrlNode() : new ConstantNode(_type)).peepholeOpt(); // Global Value Numbering if( _hash==0 ) { @@ -531,6 +531,20 @@ public abstract class Node { // Subclasses add extra hash info (such as ConstantNodes constant) int hash() { return 0; } + // ------------------------------------------------------------------------ + // + + /** Is this Node control-flow-graph related */ + public boolean isCFG() { return false; } + + /** 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 */ + public boolean isPinned() { return false; } // ------------------------------------------------------------------------ // Peephole utilities @@ -561,20 +575,6 @@ public abstract class Node { } - /** - * Immediate dominator tree depth, used to approximate a real IDOM depth - * during parsing where we do not have the whole program, and also - * peepholes change the CFG incrementally. - * <p> - * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} - */ - public int _idepth; // IDOM depth approx; Zero is unset; non-zero is cached legit - final int _idepth(int idx) { return _idepth==0 ? (_idepth=in(idx).idepth()+1) : _idepth; } - int idepth() { return _idepth(0); } - - // Return the immediate dominator of this Node. - Node idom() { return in(0); } - // Make a shallow copy (same class) of this Node, with given inputs and // empty outputs and a new Node ID. The original inputs are ignored. // Does not need to be implemented in isCFG() nodes. diff --git a/src/main/java/com/seaofnodes/simple/node/OutNode.java b/src/main/java/com/seaofnodes/simple/node/OutNode.java new file mode 100644 index 00000000..7e531145 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/OutNode.java @@ -0,0 +1,7 @@ +package com.seaofnodes.simple.node; + +import java.util.ArrayList; + +public interface OutNode { + ArrayList<Node> outs(); +} diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index dd67bd06..a07dc140 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -35,10 +35,10 @@ public class PhiNode extends Node { return sb; } - Node region() { return in(0); } + public CFGNode region() { return (CFGNode)in(0); } @Override public boolean isMultiTail() { return true; } - @Override - public boolean isMem() { return _declaredType instanceof TypeMem; } + @Override public boolean isMem() { return _declaredType instanceof TypeMem; } + @Override public boolean isPinned() { return true; } @Override public Type compute() { @@ -102,9 +102,9 @@ public class PhiNode extends Node { Node val = in(3-nullx); if( region().idom() instanceof IfNode iff && iff.pred().addDep(this)==val ) { // Must walk the idom on the null side to make sure we hit False. - Node idom = region().in(nullx); + CFGNode idom = (CFGNode)region().in(nullx); while( idom.in(0) != iff ) idom = idom.idom(); - if( idom instanceof ProjNode proj && proj._idx==1 ) + if( idom instanceof CProjNode proj && proj._idx==1 ) return val; } } diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 735fcdf3..f94e98a7 100644 --- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -14,7 +14,7 @@ public class ProjNode extends Node { // Debugging label public final String _label; - public ProjNode(MultiNode ctrl, int idx, String label) { + public ProjNode(Node ctrl, int idx, String label) { super(ctrl); _idx = idx; _label = label; @@ -26,11 +26,9 @@ public class ProjNode extends Node { @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(_label); } - @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; } @Override public boolean isMultiTail() { return in(0).isMultiHead(); } @Override public boolean isMem() { return _type instanceof TypeMem; } - - public MultiNode ctrl() { return (MultiNode)in(0); } + @Override public boolean isPinned() { return true; } @Override public Type compute() { @@ -38,18 +36,7 @@ public class ProjNode extends Node { return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; } - @Override - public Node idealize() { - if ( ctrl() instanceof IfNode iff ) { - if ( iff._type instanceof TypeTuple tt && tt._types[1 - _idx] == Type.XCONTROL ) - return iff.in(0); // We become our input control - - // Flip a negating if-test, to remove the not - if( iff.pred().addDep(this) instanceof NotNode not ) - return new ProjNode((MultiNode)new IfNode(iff.ctrl(),not.in(1)).peephole(),1-_idx,_idx==0 ? "False" : "True"); - } - return null; - } + @Override public Node idealize() { return null; } @Override boolean eq( Node n ) { return _idx == ((ProjNode)n)._idx; } diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 42501118..dcc7ccef 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -1,14 +1,15 @@ 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.Type; - import java.util.ArrayList; import java.util.Arrays; import java.util.BitSet; +import java.util.HashSet; -public class RegionNode extends Node { +public class RegionNode extends CFGNode { public RegionNode(Node... nodes) { super(nodes); } @@ -20,8 +21,8 @@ public class RegionNode extends Node { return sb.append(label()).append(_nid); } - @Override public boolean isCFG() { return true; } @Override public boolean isMultiHead() { return true; } + @Override public boolean blockHead() { return true; } @Override public Type compute() { @@ -57,7 +58,7 @@ public class RegionNode extends Node { IterPeeps.addAll(phi._outputs); } } - return isDead() ? new ConstantNode(Type.XCONTROL) : delDef(path); + return isDead() ? Parser.XCTRL : delDef(path); } // If down to a single input, become that input if( nIns()==2 && !hasPhi() ) @@ -89,31 +90,31 @@ public class RegionNode extends Node { } // Immediate dominator of Region is a little more complicated. - @Override int idepth() { + @Override public int idepth() { if( _idepth!=0 ) return _idepth; int d=0; for( Node n : _inputs ) if( n!=null ) - d = Math.max(d,n.idepth()); + d = Math.max(d,((CFGNode)n).idepth()+1); return _idepth=d; } - @Override Node idom() { - if( nIns()==2 ) return in(1); // 1-input is that one input - if( nIns()!=3 ) return null; // Fails for anything other than 2-inputs + @Override public CFGNode idom() { + CFGNode lca = null; // Walk the LHS & RHS idom trees in parallel until they match, or either fails. // Because this does not cache, it can be linear in the size of the program. - Node lhs = in(1); - Node rhs = in(2); - while( lhs != rhs ) { - if( lhs==null || rhs==null ) return null; - var comp = lhs.idepth() - rhs.idepth(); - if( comp >= 0 ) lhs = lhs.idom(); - if( comp <= 0 ) rhs = rhs.idom(); - } - return lhs; + for( int i=1; i<nIns(); i++ ) + lca = cfg(i).idom(lca); + 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; @@ -123,4 +124,6 @@ public class RegionNode extends Node { @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 92bda5bf..444b76a8 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -13,16 +13,18 @@ import java.util.BitSet; * <p> * The Return's output is the value from the data node. */ -public class ReturnNode extends Node { +public class ReturnNode extends CFGNode { public ReturnNode(Node ctrl, Node data, ScopeNode scope) { super(ctrl, data); // We lookup memory slices by the naming convention that they start with $ // We could also use implicit knowledge that all memory projects are at offset >= 2 - String[] names = scope.reverseNames(); - for (String name: names) { - if (!name.equals("$ctrl") && name.startsWith("$")) - addDef(scope.lookup(name)); + if( scope != null ) { + String[] names = scope.reverseNames(); + for (String name: names) { + if (!name.equals("$ctrl") && name.startsWith("$")) + addDef(scope.lookup(name)); + } } } @@ -39,8 +41,6 @@ public class ReturnNode extends Node { return sb.append(";"); } - @Override public boolean isCFG() { return true; } - @Override public Type compute() { return TypeTuple.make(ctrl()._type,expr()._type); @@ -52,4 +52,6 @@ public class ReturnNode extends Node { return ctrl(); return null; } + + @Override public Node getBlockStart() { return ctrl().getBlockStart(); } } diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index 4b7e02a8..62fc8a6b 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.HashMap; +import java.util.HashSet; /** * The Start node represents the start of the function. @@ -13,7 +14,7 @@ import java.util.HashMap; * 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 MultiNode { +public class StartNode extends CFGNode implements MultiNode { // This field is NOT final, because the tuple expands as we add memory aliases TypeTuple _args; @@ -63,8 +64,8 @@ public class StartNode extends MultiNode { return sb.append(label()); } - @Override public boolean isCFG() { return true; } @Override public boolean isMultiHead() { return true; } + @Override public boolean blockHead() { return true; } @Override public TypeTuple compute() { return _args; } @@ -73,6 +74,12 @@ public class StartNode extends MultiNode { public Node idealize() { return null; } // No immediate dominator, and idepth==0 - @Override int idepth() { return 0; } - @Override Node idom() { return null; } + @Override public int idepth() { return 0; } + @Override public CFGNode idom() { 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 3b5a7ce3..94b2ad6d 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -5,7 +5,7 @@ import com.seaofnodes.simple.IterPeeps; import java.util.BitSet; -public class StopNode extends Node { +public class StopNode extends CFGNode { public final String _src; @@ -28,7 +28,7 @@ public class StopNode extends Node { return sb.append("]"); } - @Override public boolean isCFG() { return true; } + @Override public boolean blockHead() { return true; } // If a single Return, return it. // Otherwise, null because ambiguous. @@ -51,7 +51,17 @@ public class StopNode extends Node { return null; } - @Override public Node idom() { return null; } + @Override public int idepth() { + if( _idepth!=0 ) return _idepth; + int d=0; + for( Node n : _inputs ) + if( n!=null ) + d = Math.max(d,((CFGNode)n).idepth()+1); + return _idepth=d; + } + @Override public CFGNode idom() { return null; } + + @Override public int loopDepth() { return (_loopDepth=1); } public Node addReturn(Node node) { return addDef(node); @@ -64,4 +74,6 @@ public class StopNode extends Node { if( err != null ) throw new RuntimeException(err); 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 8d264601..db8e2ce6 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -17,8 +17,8 @@ public class StoreNode extends MemOpNode { * @param memPtr The ptr to the struct where we will store a value * @param value Value to be stored */ - public StoreNode(String name, int alias, Node memSlice, Node memPtr, Node value) { - super(name, alias, memSlice, memPtr, value); + public StoreNode(String name, int alias, Node ctrl, Node memSlice, Node memPtr, Node value) { + super(name, alias, ctrl, memSlice, memPtr, value); } @Override @@ -48,7 +48,7 @@ public class StoreNode extends MemOpNode { // Must have exactly one use of "this" or you get weird // non-serializable memory effects in the worse case. st.checkNoUseBeyond(this) ) { - assert Utils.eq(_name,st._name); // Equiv class aliasing is perfect + assert _name.equals(st._name); // Equiv class aliasing is perfect setDef(1,st.mem()); return this; } diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index b87115cd..5ddcdb68 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; diff --git a/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java b/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java new file mode 100644 index 00000000..83779dd2 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java @@ -0,0 +1,13 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.Type; +import java.util.BitSet; + +public class XCtrlNode extends CFGNode { + public XCtrlNode( ) { super(Parser.START); } + @Override public String label() { return "Xctrl"; } + @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append("Xctrl"); } + @Override public Type compute() { return Type.XCONTROL; } + @Override public Node idealize() { return null; } +} |