diff options
Diffstat (limited to 'chapter11/src/main/java')
29 files changed, 140 insertions, 679 deletions
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter11/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java deleted file mode 100644 index 35b34576..00000000 --- a/chapter11/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ /dev/null @@ -1,272 +0,0 @@ - package com.seaofnodes.simple; - -import com.seaofnodes.simple.IterPeeps.WorkList; -import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.type.*; -import java.util.*; - -public abstract class GlobalCodeMotion { - - // Arrange that the existing isCFG() Nodes form a valid CFG. The - // Node.use(0) is always a block tail (either IfNode or head of the - // following block). There are no unreachable infinite loops. - public static void buildCFG( StopNode stop ) { - fixLoops(stop); - schedEarly(); - Parser.SCHEDULED = true; - schedLate(stop); - } - - // ------------------------------------------------------------------------ - // Backwards walk on the CFG only, looking for unreachable code - which has - // to be an infinite loop. Insert a bogus never-taken exit to Stop, so the - // loop becomes reachable. Also, set loop nesting depth - private static void fixLoops(StopNode stop) { - // Backwards walk from Stop, looking for unreachable code - BitSet visit = new BitSet(); - HashSet<CFGNode> unreach = new HashSet<>(); - unreach.add(Parser.START); - for( Node ret : stop._inputs ) - ((ReturnNode)ret).walkUnreach(visit,unreach); - if( unreach.isEmpty() ) return; - - // Forwards walk from unreachable, looking for loops with no exit test. - visit.clear(); - for( CFGNode cfg : unreach ) - walkInfinite(cfg,visit,stop); - // Set loop depth on remaining graph - unreach.clear(); - visit.clear(); - for( Node ret : stop._inputs ) - ((ReturnNode)ret).walkUnreach(visit,unreach); - assert unreach.isEmpty(); - } - - - // Forwards walk over previously unreachable, looking for loops with no - // exit test. - static private void walkInfinite( CFGNode n, BitSet visit, StopNode stop ) { - if( visit.get(n._nid) ) return; // Been there, done that - visit.set(n._nid); - if( n instanceof LoopNode loop ) - loop.forceExit(stop); - for( Node use : n._outputs ) - if( use instanceof CFGNode cfg ) - walkInfinite(cfg,visit,stop); - } - - // ------------------------------------------------------------------------ - private static void schedEarly() { - ArrayList<CFGNode> rpo = new ArrayList<>(); - BitSet visit = new BitSet(); - _rpo_cfg(Parser.START, visit, rpo); - // Reverse Post-Order on CFG - for( int j=rpo.size()-1; j>=0; j-- ) { - CFGNode cfg = rpo.get(j); - cfg.loopDepth(); - for( Node n : cfg._inputs ) - _schedEarly(n,visit); - // In dead infinite loops, entire code blocks may be unreachable - // from below. Reach down from the CFG to their Phis so their - // inputs are scheduled too. - if( cfg instanceof RegionNode ) { - int len = cfg.nOuts(); - for( int i=0; i<len; i++ ) - if( cfg.out(i) instanceof PhiNode phi ) - _schedEarly(phi,visit); - } - } - } - - // Post-Order of CFG - private static void _rpo_cfg(Node n, BitSet visit, ArrayList<CFGNode> rpo) { - if( !(n instanceof CFGNode cfg) || visit.get(cfg._nid) ) - return; // Been there, done that - visit.set(cfg._nid); - for( Node use : cfg._outputs ) - _rpo_cfg(use,visit,rpo); - rpo.add(cfg); - } - - private static void _schedEarly(Node n, BitSet visit) { - if( n==null || visit.get(n._nid) ) return; // Been there, done that - visit.set(n._nid); - // Schedule inputs first, except Phis: following their backedges would - // enter a data cycle before its control has been scheduled. - for( Node def : n._inputs ) - if( def!=null && !(def instanceof PhiNode) ) - _schedEarly(def,visit); - // An existing edge 0 already supplies control (or a Phi/Proj binding). - if( n.in(0)==null ) { - // Schedule at deepest input - CFGNode early = Parser.START; // Maximally early, lowest idepth - for( int i=1; i<n.nIns(); i++ ) - if( n.in(i)!=null && n.in(i).cfg0().idepth() > early.idepth() ) - early = n.in(i).cfg0(); // Latest/deepest input - n.setDef(0,early); // First place this can go - } - } - - // ------------------------------------------------------------------------ - private static void schedLate( StopNode stop) { - CFGNode[] late = new CFGNode[Node.UID()]; - Node[] ns = new Node[Node.UID()]; - // Record Load NIDs at all their CFG block choices, then check against - // Store block choices to force a Load above an anti-dependent Store. - int[] anti = new int[Node.UID()]; - // Breadth-first scheduling - breadth(stop,ns,late,anti); - - // Copy the best placement choice into the control slot - for( int i=0; i<late.length; i++ ) - if( ns[i] != null && !(ns[i] instanceof ProjNode) ) - ns[i].setDef(0,late[i]); - } - - private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) { - // Things on the worklist have some (but perhaps not all) uses done. - WorkList<Node> work = new WorkList<>(); - work.push(stop); - Node n; - outer: - while( (n = work.pop()) != null ) { - assert late[n._nid]==null; // No double visit - // These I know the late schedule of, and need to set early for loops - if( n instanceof CFGNode cfg ) late[n._nid] = cfg.blockHead() ? cfg : cfg.cfg(0); - else if( n instanceof PhiNode phi ) late[n._nid] = phi.region(); - // These nodes have a fixed late placement at their original control. - else if( n instanceof ProjNode || n instanceof NewNode || n==Parser.ZERO ) late[n._nid] = n.cfg0(); - else { - - // All uses done? - for( Node use : n._outputs ) - if( use!=null && late[use._nid]==null ) - continue outer; // Nope, await all uses done - - // Loads need their memory inputs' uses also done - if( n instanceof LoadNode ld ) - for( Node memuse : ld.mem()._outputs ) - if( antiUse(ld,memuse) && late[memuse._nid]==null ) - continue outer; - - // All uses done, schedule - _doSchedLate(n,ns,late,anti); - } - - // A use just finished; reconsider its inputs and waiting loads, - // even when the shared memory input was already scheduled. - for( Node def : n._inputs ) { - if( def==null ) continue; - if( late[def._nid]==null ) work.push(def); - for( Node out : def._outputs ) - if( out instanceof LoadNode ld && late[ld._nid]==null ) - work.push(ld); - } - if( n instanceof LoopNode loop ) - for( Node phi : loop._outputs ) - if( phi instanceof PhiNode && late[phi._nid]==null ) - work.push(phi); - } - } - - private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { - // Walk uses, gathering the LCA (Least Common Ancestor) of uses - CFGNode early = n.in(0) instanceof CFGNode cfg ? cfg : n.in(0).cfg0(); - assert early != null; - CFGNode lca = null; - for( Node use : n._outputs ) - if( use != null ) - lca = use_block(n,use, late).domLCA(lca); - - // Loads may need anti-dependencies, raising their LCA - if( n instanceof LoadNode load ) - lca = find_anti_dep(lca,load,early,late,anti); - - // Walk up from the LCA to the early, looking for best place. This is - // the lowest execution frequency, approximated by least loop depth and - // deepest control flow. - CFGNode best = lca; - lca = lca.idom(); // Already found best for starting LCA - for( ; lca != early.idom(); lca = lca.idom() ) - if( better(lca,best) ) - best = lca; - assert !(best instanceof IfNode); - ns [n._nid] = n; - late[n._nid] = best; - } - - // Block of use. Normally from late[] schedule, except for Phis, which go - // to the matching Region input. - private static CFGNode use_block(Node n, Node use, CFGNode[] late) { - if( !(use instanceof PhiNode phi) ) - return late[use._nid]; - CFGNode found=null; - for( int i=1; i<phi.nIns(); i++ ) - if( phi.in(i)==n ) - found = phi.region().cfg(i).domLCA(found); // Can be more than one matching input. - assert found!=null; - return found; - } - - - // Least loop depth first, then largest idepth - private static boolean better( CFGNode lca, CFGNode best ) { - return lca.loopDepth() < best.loopDepth() || - lca instanceof NeverNode || - lca.idepth() > best.idepth() || - best instanceof IfNode; - } - - // Only a store or memory Phi covering this alias can constrain a load. - // MemMerge packages slices without overwriting them. - private static boolean antiUse(LoadNode load, Node use) { - return switch( use ) { - case StoreNode st -> st._alias==load._alias; - case MemPhiNode phi -> phi._alias==load._alias; - case BulkMemPhiNode phi -> !phi.isSplit(load._alias); - default -> false; - }; - } - - private static CFGNode find_anti_dep(CFGNode lca, LoadNode load, CFGNode early, CFGNode[] late, int[] anti) { - // We could skip final-field loads here. - // Walk LCA->early, flagging Load's block location choices - for( CFGNode cfg=lca; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) - anti[cfg._nid] = load._nid; - // Walk load->mem uses, looking for Stores causing an anti-dep - for( Node mem : load.mem()._outputs ) { - if( !antiUse(load,mem) ) continue; - switch( mem ) { - case StoreNode st: - lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti); - break; - case PhiNode phi: - // Repeat anti-dep for matching Phi inputs. - // No anti-dep edges but may raise the LCA. - for( int i=1; i<phi.nIns(); i++ ) - if( phi.in(i)==load.mem() ) - lca = anti_dep(load,phi.region().cfg(i),load.mem().cfg0(),lca,null,anti); - break; - default: throw Utils.TODO(); - } - } - return lca; - } - - // - private static CFGNode anti_dep( LoadNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st, int[] anti ) { - // Preserve the full store range for the earlier evaluator scheduler. - // It places nodes independently of GCM and may hoist this store. - for( ; stblk != defblk.idom(); stblk = stblk.idom() ) { - // Store and Load overlap, need anti-dependence - if( anti[stblk._nid]==load._nid ) { - lca = stblk.domLCA(lca); // Raise Loads LCA - if( lca == stblk && st != null && Utils.find(st._inputs,load) == -1 ) // And if something moved, - st.addDef(load); // Add anti-dep as well - return lca; // Cap this stores' anti-dep to here - } - } - return lca; - } - -} diff --git a/chapter11/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter11/src/main/java/com/seaofnodes/simple/IRPrinter.java index 7e93e9da..d5ab15fe 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -8,6 +8,7 @@ public final class IRPrinter extends IRAdapter<Node> { private static final com.seaofnodes.print.IRPrinter<Node> PRINT = new com.seaofnodes.print.IRPrinter<>(new IRPrinter()); @Override public String type(Node n) { return n._type==null ? "" : n._type.str(); } + @Override public int inputColumns() { return 3; } @Override public String inputMark(Node n, Node def) { return n instanceof MemMergeNode && def instanceof MemMergeNode ? "^" : " "; } @Override public Kind kind(Node n) { if( n instanceof StartNode ) return Kind.START; @@ -17,15 +18,13 @@ public final class IRPrinter extends IRAdapter<Node> { if( n instanceof PhiNode ) return Kind.PHI; if( n instanceof ReturnNode ) return Kind.RETURN; if( n instanceof ConstantNode ) return Kind.CONSTANT; - if( n instanceof CProjNode ) return Kind.CPROJ; - if( n instanceof ProjNode ) return n instanceof CFGNode ? Kind.CPROJ : Kind.PROJ; - if( n instanceof CFGNode ) return Kind.CTRL; + if( n instanceof ProjNode ) return n.isCFG() ? Kind.CPROJ : Kind.PROJ; + if( n.isCFG() ) return Kind.CTRL; if( n instanceof MultiNode ) return Kind.MULTI; return Kind.DATA; } @Override public int index(Node n) { if( n instanceof ProjNode p ) return p._idx; - if( n instanceof CProjNode p ) return p._idx; return n._nid; } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter11/src/main/java/com/seaofnodes/simple/IterPeeps.java index 9d2b913f..7075d526 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -98,7 +98,6 @@ public abstract class IterPeeps { if( obs != null ) obs.after(n, x, true); } - GlobalCodeMotion.buildCFG(stop); return stop; } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/Parser.java b/chapter11/src/main/java/com/seaofnodes/simple/Parser.java index fb4dfdf8..3b5f2721 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/Parser.java @@ -31,18 +31,12 @@ public class Parser { */ public static StartNode START; - public static ConstantNode ZERO; - public static XCtrlNode XCTRL; - public StopNode STOP; // Field identities are independent of the memory graph and Start's tuple. private final HashMap<String,Integer> _aliases = new HashMap<>(); private int _alias = 2; - // Debugger Printing. - public static boolean SCHEDULED; // True if debug printer can use schedule info - // The Lexer. Thin wrapper over a byte[] buffer with a cursor. private final Lexer _lexer; @@ -96,14 +90,11 @@ public class Parser { Node.reset(); IterPeeps.reset(); OBJS.clear(); - SCHEDULED = false; _lexer = new Lexer(source); _scope = new ScopeNode(); _continueScope = _breakScope = null; START = new StartNode(new Type[]{ Type.CONTROL, TypeMem.BOT, arg }); STOP = new StopNode(source); - ZERO = new ConstantNode(TypeInteger.constant(0)).peephole().keep(); - XCTRL= new XCtrlNode().peephole().keep(); } public Parser(String source) { @@ -126,12 +117,10 @@ public class Parser { _xScopes.push(_scope); // Enter a new scope for the initial control and arguments _scope.push(); - _scope.define(ScopeNode.CTRL, Type.CONTROL , new CProjNode(START, 0, ScopeNode.CTRL).peephole()); - _scope.define(ScopeNode.ARG0, TypeInteger.BOT, new ProjNode(START, 2, ScopeNode.ARG0).peephole()); + _scope.define(ScopeNode.CTRL, Type.CONTROL , new ProjNode(START, 0, ScopeNode.CTRL).peephole()); + _scope.define(ScopeNode.ARG0, TypeInteger.BOT, new ProjNode(START, 2, ScopeNode.ARG0).peephole()); _scope.define("$mem", TypeMem.BOT, new ProjNode(START, 1, "$mem").peephole()); parseBlock(); - if( ctrl()._type==Type.CONTROL ) - STOP.addReturn(new ReturnNode(ctrl(), new ConstantNode(TypeInteger.constant(0)).peephole(), _scope).peephole()); _scope.pop(); _xScopes.pop(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); @@ -215,9 +204,9 @@ public class Parser { require("}"); // Build and install the TypeStruct TypeStruct ts = TypeStruct.make(typeName, fields); - OBJS.put(typeName, ts); // Insert the struct name in the collection of all struct names _aliases.put(typeName,_alias); _alias += ts._fields.length; + OBJS.put(typeName, ts); // Insert the struct name in the collection of all struct names return parseStatement(); } @@ -259,8 +248,8 @@ public class Parser { // IfNode takes current control and predicate Node ifNode = new IfNode(ctrl(), pred).peephole(); // Setup projection nodes - Node ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); - Node ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole(); + Node ifT = new ProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); + Node ifF = new ProjNode(ifNode.unkeep(), 1, "False").peephole(); // Clone the body Scope to create the break/exit Scope which accounts for any // side effects in the predicate. The break/exit Scope will be the final @@ -306,7 +295,7 @@ public class Parser { private ScopeNode jumpTo(ScopeNode toScope) { ScopeNode cur = _scope.dup(); - ctrl(XCTRL); // Kill current scope + ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill current scope // Prune nested lexical scopes that have depth > than the loop head // We use _breakScope as a proxy for the loop head scope to obtain the depth while( cur._scopes.size() > _breakScope._scopes.size() ) @@ -342,8 +331,8 @@ public class Parser { // IfNode takes current control and predicate Node ifNode = new IfNode(ctrl(), pred).peephole(); // Setup projection nodes - Node ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); - Node ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole().keep(); + Node ifT = new ProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); + Node ifF = new ProjNode(ifNode.unkeep(), 1, "False").peephole().keep(); // In if true branch, the ifT proj node becomes the ctrl // But first clone the scope and set it as current int ndefs = _scope.nIns(); @@ -390,7 +379,7 @@ public class Parser { private Node parseReturn() { var expr = require(parseExpression(), ";"); Node ret = STOP.addReturn(new ReturnNode(ctrl(), expr, _scope).peephole()); - ctrl(XCTRL); // Kill control + ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill control return ret; } @@ -585,7 +574,7 @@ public class Parser { if( _lexer.isNumber() ) return parseIntegerLiteral(); if( match("(") ) return require(parseExpression(), ")"); if( matchx("true" ) ) return new ConstantNode(TypeInteger.constant(1)).peephole(); - if( matchx("false") ) return ZERO; + if( matchx("false") ) return new ConstantNode(TypeInteger.constant(0)).peephole(); if( matchx("null" ) ) return new ConstantNode(TypeMemPtr.NULLPTR).peephole(); if( matchx("new") ) { String structName = requireId(); @@ -603,11 +592,12 @@ public class Parser { /** * Return a NewNode but also generate instructions to initialize it. */ - private Node newStruct(TypeStruct obj) { + private Node newStruct( TypeStruct obj ) { Node n = new NewNode(TypeMemPtr.make(obj), ctrl()).peephole().keep(); + Node initValue = new ConstantNode(TypeInteger.constant(0)).peephole(); int alias = _aliases.get(obj._name); for( Field field : obj._fields ) { - store(field._fname,alias,n,ZERO); + store(field._fname,alias,n,initValue); alias++; } return n.unkeep(); @@ -619,7 +609,7 @@ public class Parser { private void store(String name, int alias, Node ptr, Node val) { Node prior = mem().keep(); - Node st = new StoreNode(name,alias,ctrl(),prior,ptr,val).peephole(); + Node st = new StoreNode(name,alias,prior,ptr,val).peephole(); mem(new MemMergeNode(prior,alias,st).peephole()); prior.unkeep(); } @@ -759,16 +749,7 @@ public class Parser { * Return the next non-white-space character */ private void skipWhiteSpace() { - while( true ) { - if( isWhiteSpace() ) _position++; - // Skip // to end of line - else if( _position+2 < _input.length && - _input[_position ] == '/' && - _input[_position+1] == '/') { - _position += 2; - while( !isEOF() && _input[_position] != '\n' ) _position++; - } else break; - } + while (isWhiteSpace()) _position++; } @@ -850,9 +831,8 @@ public class Parser { return new String(_input, start, --_position - start); } - // private boolean isPunctuation(char ch) { - return "=;[]<>()+-/*".indexOf(ch) != -1; + return "=;[]<>(){}+-/*!".indexOf(ch) != -1; } private String parsePunctuation() { diff --git a/chapter11/src/main/java/com/seaofnodes/simple/Utils.java b/chapter11/src/main/java/com/seaofnodes/simple/Utils.java index f3ac25b1..4f2af769 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/Utils.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/Utils.java @@ -55,4 +55,11 @@ public class Utils { // Fold a 64bit hash into 32 bits public static int fold( long x ) { return (int)((x>>32) ^ x); } + + public static boolean eq(String s0, String s1) { + if( s0==s1 ) return true; + assert s0==s0.intern(); + assert s1==s1.intern(); + return false; + } } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/CFGNode.java deleted file mode 100644 index ea67d17d..00000000 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ /dev/null @@ -1,95 +0,0 @@ -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; } - - 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 char _idepth; - public int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(idom().idepth()+1); } - // Zero depth means uncached. Check before narrowing so overflow cannot wrap. - final int cacheIDepth(int depth) { - assert 0 <= depth && depth <= Character.MAX_VALUE : "Dominator depth exceeds 65535"; - return _idepth = (char)depth; - } - - - // 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 domLCA(CFGNode rhs) { - if( rhs==null ) return this; - CFGNode lhs = this; - while( lhs != rhs ) { - if( lhs==null || rhs==null ) return null; - int 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; } - - // ------------------------------------------------------------------------ - // 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/chapter11/src/main/java/com/seaofnodes/simple/node/CProjNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/CProjNode.java deleted file mode 100644 index ff5d1a76..00000000 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/CProjNode.java +++ /dev/null @@ -1,62 +0,0 @@ -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.type.TypeMem; -import com.seaofnodes.simple.type.TypeTuple; - -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 protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p(_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/chapter11/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 9ecd1152..426736ed 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -38,7 +38,6 @@ public class ConstantNode extends Node { } @Override public boolean isMultiTail() { return true; } - // The special forever-zero is pinned, all others can sink @Override public Type compute() { return _con; } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/IfNode.java index 70340f7f..45f695a5 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -5,10 +5,8 @@ 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 { +public class IfNode extends MultiNode { public IfNode(Node ctrl, Node pred) { super(ctrl, pred); @@ -20,6 +18,7 @@ public class IfNode extends CFGNode implements MultiNode { @Override protected String format() { return "if( %1 )"; } + @Override public boolean isCFG() { return true; } @Override public boolean isMultiHead() { return true; } public Node ctrl() { return in(0); } @@ -49,20 +48,11 @@ public class IfNode extends CFGNode implements 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( 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 ) { + 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 ) { 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/chapter11/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 386009b4..9bf36459 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -23,7 +23,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, null, memSlice, memPtr); + super(name, alias, memSlice, memPtr, null); _declaredType = glb; } @@ -67,7 +67,7 @@ public class LoadNode extends MemOpNode { // Simple Load-after-Store on same address. if( mem() instanceof StoreNode st && ptr() == st.ptr() && _alias==st._alias ) { // Must check same object - assert _name.equals(st._name); // Equiv class aliasing is perfect + assert Utils.eq(_name,st._name); // Equiv class aliasing is perfect return st.val(); } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 45549f1d..a0ba973e 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -1,17 +1,15 @@ 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); } - public CFGNode entry() { return cfg(1); } - public CFGNode back () { return cfg(2); } + Node entry() { return in(1); } + Node back () { return in(2); } @Override public String label() { return "Loop"; } @@ -27,51 +25,7 @@ public class LoopNode extends RegionNode { return inProgress() ? null : super.idealize(); } - // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) - @Override public int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(entry().idepth()+1); } - // 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)); - } + // Bypass Region idom, same as the default idom() using use entry in(1) instead of in(0) + @Override int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(entry().idepth()+1); } + @Override Node idom() { return entry(); } } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 5a57a8c8..44304bcb 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/chapter11/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... nodes) { - super(nodes); + public MemOpNode(String name, int alias, Node memSlice, Node memPtr, Node value) { + super(null, memSlice, memPtr, value); _name = name; _alias = alias; } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/MultiNode.java index 379e140d..2743bd19 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/MultiNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/MultiNode.java @@ -1,10 +1,12 @@ package com.seaofnodes.simple.node; -public interface MultiNode extends OutNode { +public abstract class MultiNode extends Node { + + public MultiNode(Node... inputs) { super(inputs); } // Find a projection by index - default ProjNode proj( int idx ) { - for( Node out : outs() ) + ProjNode proj( int idx ) { + for( Node out : _outputs ) if( out instanceof ProjNode prj && prj._idx==idx ) return prj; return null; diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/NeverNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/NeverNode.java deleted file mode 100644 index 6eb7fe63..00000000 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/NeverNode.java +++ /dev/null @@ -1,20 +0,0 @@ -package com.seaofnodes.simple.node; - -import com.seaofnodes.print.ExprPrinter; - -import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.type.TypeInteger; -import com.seaofnodes.simple.type.Type; - -// "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 protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p("Never"); } - - @Override public Type compute() { return TypeInteger.BOT; } - - @Override public Node idealize() { return null; } -} diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/NewNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/NewNode.java index 74ba5184..857920bc 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -22,7 +22,6 @@ public class NewNode extends Node { return p.p("new ").p(_ptr._obj.str()); } - @Override public Type compute() { return _ptr; } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java index 568c23cc..1d8e23f8 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java @@ -2,8 +2,9 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.BaseNode; -import com.seaofnodes.simple.IRPrinter; import com.seaofnodes.simple.Parser; + +import com.seaofnodes.simple.IRPrinter; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; @@ -16,7 +17,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 extends BaseNode<Node> implements OutNode, Cloneable { +public abstract class Node extends BaseNode<Node> implements Cloneable { /** * Inputs to the node. These are use-def references to Nodes. @@ -82,7 +83,6 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable */ 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(); } @@ -90,7 +90,7 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable public boolean isUnused() { return nOuts() == 0; } - public CFGNode cfg0() { return (CFGNode)in(0); } + public boolean isMem() { return false; } /** * Change a <em>def</em> into a Node. Keeps the edges correct, by removing @@ -117,11 +117,11 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable // 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; @@ -149,7 +149,7 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable * @param new_def the new definition, appended to the end of existing definitions * @return new_def for flow coding */ - public Node addDef(Node new_def) { + Node addDef(Node new_def) { unlock(); // Add use->def edge _inputs.add(new_def); @@ -268,8 +268,8 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable Type old = setType(compute()); // Replace constant computations from non-constants with a constant node - if( !(this instanceof ConstantNode) && !(this instanceof XCtrlNode) && _type.isHighOrConst() ) - return (_type==Type.XCONTROL ? new XCtrlNode() : new ConstantNode(_type)).peepholeOpt(); + if( !(this instanceof ConstantNode) && _type.isHighOrConst() ) + return new ConstantNode(_type).peepholeOpt(); // Global Value Numbering if( _hash==0 ) { @@ -484,17 +484,6 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable int hash() { return 0; } // ------------------------------------------------------------------------ - // - - /** Is this Node control-flow-graph related */ - - /** Is this Node Memory related */ - public boolean isMem() { return false; } - - /** Return block start from a isCFG() */ - public Node getBlockStart() { return null; } - - // ------------------------------------------------------------------------ // Peephole utilities // Swap inputs without letting either input go dead during the swap. @@ -522,6 +511,38 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable return true; } + /** + * 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 char _idepth; // IDOM depth approx; Zero is unset; non-zero is cached legit + + // Find the lowest common ancestor in the current dominator tree. + Node domLCA(Node rhs) { + if( rhs==null ) return this; + Node lhs = this; + while( lhs != rhs ) { + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); + if( comp >= 0 ) lhs = lhs.idom(); + if( comp <= 0 ) rhs = rhs.idom(); + } + return lhs; + } + + int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(idom().idepth()+1); } + // Zero depth means uncached. Check before narrowing so overflow cannot wrap. + final int cacheIDepth(int depth) { + assert 0 <= depth && depth <= Character.MAX_VALUE : "Dominator depth exceeds 65535"; + return _idepth = (char)depth; + } + + // 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/chapter11/src/main/java/com/seaofnodes/simple/node/OutNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/OutNode.java deleted file mode 100644 index 7e531145..00000000 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/OutNode.java +++ /dev/null @@ -1,7 +0,0 @@ -package com.seaofnodes.simple.node; - -import java.util.ArrayList; - -public interface OutNode { - ArrayList<Node> outs(); -} diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 8f3cda9e..6995cc2f 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -32,9 +32,10 @@ public class PhiNode extends Node { return p.unchar(',').close(); } - public CFGNode region() { return (CFGNode)in(0); } + Node region() { return 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 Type compute() { @@ -84,9 +85,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. - CFGNode idom = (CFGNode)region().in(nullx); + Node idom = region().in(nullx); while( idom.in(0) != iff ) idom = idom.idom(); - if( idom instanceof CProjNode proj && proj._idx==1 ) + if( idom instanceof ProjNode proj && proj._idx==1 ) return val; } } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/ProjNode.java index e82c69b3..a2632110 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -15,7 +15,7 @@ public class ProjNode extends Node { // Debugging label public final String _label; - public ProjNode(Node ctrl, int idx, String label) { + public ProjNode(MultiNode ctrl, int idx, String label) { super(ctrl); _idx = idx; _label = label; @@ -27,16 +27,30 @@ public class ProjNode extends Node { @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p(_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 Type compute() { Type t = in(0)._type; return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; } - @Override public Node idealize() { return null; } + @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 boolean eq( Node n ) { return _idx == ((ProjNode)n)._idx; } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/RegionNode.java index f0808410..8b52494a 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -3,15 +3,13 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; 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 CFGNode { +public class RegionNode extends Node { public RegionNode(Node... nodes) { super(nodes); } @@ -22,8 +20,8 @@ public class RegionNode extends CFGNode { return p.p(label()).p(_nid); } + @Override public boolean isCFG() { return true; } @Override public boolean isMultiHead() { return true; } - @Override public boolean blockHead() { return true; } @Override public Type compute() { @@ -59,7 +57,7 @@ public class RegionNode extends CFGNode { IterPeeps.addAll(phi._outputs); } } - return isDead() ? Parser.XCTRL : delDef(path); + return isDead() ? new ConstantNode(Type.XCONTROL) : delDef(path); } // If down to a single input, become that input if( nIns()==2 && !hasPhi() ) @@ -91,30 +89,23 @@ public class RegionNode extends CFGNode { } // Immediate dominator of Region is a little more complicated. - @Override public int idepth() { + @Override int idepth() { if( _idepth!=0 ) return _idepth; int depth=0; for( Node n : _inputs ) if( n!=null ) - depth = Math.max(depth,((CFGNode)n).idepth()+1); + depth = Math.max(depth,n.idepth()+1); return cacheIDepth(depth); } - @Override public CFGNode idom() { - CFGNode lca = null; + @Override Node idom() { + Node lca = null; // Recompute from predecessors: CFG edits can change the dominator. for( int i=1; i<nIns(); i++ ) - lca = cfg(i).domLCA(lca); + lca = in(i).domLCA(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; @@ -124,6 +115,4 @@ public class RegionNode extends CFGNode { @Override boolean eq( Node n ) { return !inProgress(); } - - @Override public Node getBlockStart() { return this; } } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 161cc7d6..ef4ddb3a 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -6,11 +6,10 @@ import com.seaofnodes.simple.type.*; /** Keeps all preceding memory effects and the return value alive: {ctrl, $mem, value}. */ -public class ReturnNode extends CFGNode { +public class ReturnNode extends Node { public ReturnNode(Node ctrl, Node data, ScopeNode scope) { - // A synthetic never-taken loop exit has no source scope. - super(ctrl, scope == null ? null : scope.lookup("$mem"), data); + super(ctrl, scope.lookup("$mem"), data); } public Node ctrl() { return in(0); } @@ -27,6 +26,8 @@ public class ReturnNode extends CFGNode { return p.p(";"); } + @Override public boolean isCFG() { return true; } + @Override public Type compute() { // Return exposes the complete memory state. @@ -39,6 +40,4 @@ public class ReturnNode extends CFGNode { return ctrl(); return null; } - - @Override public Node getBlockStart() { return ctrl().getBlockStart(); } } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/StartNode.java index c1b57915..3404f111 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -3,13 +3,10 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.*; -import java.util.BitSet; -import java.util.HashSet; -/** Start supplies control, whole memory, and the argument, in that order. */ -public class StartNode extends CFGNode implements MultiNode { - - private final TypeTuple _args; +/** The entry tuple: control, initial whole-memory state, and argument. */ +public class StartNode extends MultiNode { + final TypeTuple _args; public StartNode(Type[] args) { super(); @@ -23,8 +20,8 @@ public class StartNode extends CFGNode implements MultiNode { return p.p(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; } @@ -33,12 +30,6 @@ public class StartNode extends CFGNode implements MultiNode { public Node idealize() { return null; } // No immediate dominator, and idepth==0 - @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; } + @Override int idepth() { return 0; } + @Override Node idom() { return null; } } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/StopNode.java index 46cf51da..4b4e9615 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -8,7 +8,7 @@ import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.IterPeeps; -public class StopNode extends CFGNode { +public class StopNode extends Node { public final String _src; @@ -31,7 +31,7 @@ public class StopNode extends CFGNode { return p.p("]"); } - @Override public boolean blockHead() { return true; } + @Override public boolean isCFG() { return true; } // If a single Return, return it. // Otherwise, null because ambiguous. @@ -54,17 +54,7 @@ public class StopNode extends CFGNode { 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 cacheIDepth(d); - } - @Override public CFGNode idom() { return null; } - - @Override public int loopDepth() { return (_loopDepth=1); } + @Override public Node idom() { return null; } public Node addReturn(Node node) { return addDef(node); @@ -82,6 +72,4 @@ public class StopNode extends CFGNode { if( obs != null ) obs.phase("TypeCheck"); return this; } - - @Override public Node getBlockStart() { return this; } } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/StoreNode.java index f61afe78..026d5c50 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -19,8 +19,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 ctrl, Node memSlice, Node memPtr, Node value) { - super(name, alias, ctrl, memSlice, memPtr, value); + public StoreNode(String name, int alias, Node memSlice, Node memPtr, Node value) { + super(name, alias, memSlice, memPtr, value); } @Override @@ -53,7 +53,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 _name.equals(st._name); // Equiv class aliasing is perfect + assert Utils.eq(_name,st._name); // Equiv class aliasing is perfect setDef(1,st.mem()); return this; } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/SubNode.java index 7b4cff0b..6fa87a07 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -1,7 +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/chapter11/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java deleted file mode 100644 index 056dfba1..00000000 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java +++ /dev/null @@ -1,14 +0,0 @@ -package com.seaofnodes.simple.node; - -import com.seaofnodes.print.ExprPrinter; - -import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.type.Type; - -public class XCtrlNode extends CFGNode { - public XCtrlNode( ) { super(Parser.START); } - @Override public String label() { return "Xctrl"; } - @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p("Xctrl"); } - @Override public Type compute() { return Type.XCONTROL; } - @Override public Node idealize() { return null; } -} diff --git a/chapter11/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/chapter11/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index 89ef99bd..92d970d8 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -6,13 +6,13 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.type.TypeMem; -/** Chapter 11's view of the IR; browser, transport and layout are shared. */ +/** Chapter 10's view of the IR; browser, transport and layout are shared. */ public class SimpleGraphAdapter extends GraphAdapter<Node> { @Override protected String[] edgeNames(Node n) { return n instanceof ScopeNode scope && n.nIns()!=0 ? scope.reverseNames() : null; } - @Override protected int projectionIndex(Node n) { return n instanceof ProjNode p ? p._idx : n instanceof CProjNode p ? p._idx : -1; } + @Override protected int projectionIndex(Node n) { return n instanceof ProjNode p ? p._idx : -1; } @Override protected Kind kind(Node n) { if( n instanceof StopNode ) return Kind.STOP; @@ -25,9 +25,9 @@ public class SimpleGraphAdapter extends GraphAdapter<Node> { } @Override protected Role role(Node n, int i) { - if( n instanceof ScopeNode || n instanceof ConstantNode || n instanceof XCtrlNode ) return Role.ASSOC; + if( n instanceof ScopeNode || n instanceof ConstantNode ) return Role.ASSOC; if( n instanceof PhiNode ) return i == 0 ? Role.ASSOC : isMem(n) ? Role.MEM : Role.DATA; - if( n instanceof ProjNode || n instanceof CProjNode ) return n.isCFG() ? Role.CTRL : isMem(n) ? Role.MEM : Role.DATA; + if( n instanceof ProjNode ) return n.isCFG() ? Role.CTRL : isMem(n) ? Role.MEM : Role.DATA; if( n instanceof RegionNode && i == 0 ) return Role.ASSOC; if( i == 0 || n instanceof RegionNode || n instanceof StopNode ) return Role.CTRL; if( i == 1 && (n instanceof MemOpNode || n instanceof ReturnNode) ) return Role.MEM; diff --git a/chapter11/src/main/java/com/seaofnodes/simple/type/Field.java b/chapter11/src/main/java/com/seaofnodes/simple/type/Field.java index b50a4fa6..cdc58215 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/type/Field.java @@ -20,7 +20,6 @@ public class Field extends Type { _fname = fname; _type = type; } - // Make with existing alias public static Field make( String fname, Type type ) { return new Field(fname,type).intern(); } @@ -47,7 +46,7 @@ public class Field extends Type { boolean eq(Type t) { Field f = (Field)t; - return _fname.equals(f._fname) && _type==f._type; + return Utils.eq(_fname,f._fname) && _type==f._type; } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter11/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index ec7390ca..0aa019a7 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -58,7 +58,8 @@ public class TypeTuple extends Type { for( Type t : _types ) t.typeName(sb).append(","); sb.setLength(sb.length()-1); - return sb.append("]"); + sb.append("]"); + return sb; } public static final TypeTuple IF_BOTH = make(new Type[]{Type. CONTROL,Type. CONTROL}); |