diff options
| author | Cliff Click <cliffc@acm.org> | 2026-10-03 14:03:48 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-10-03 14:03:48 -0700 |
| commit | 22df891893d30e9906d0b14fc3ae5d8e67d500b2 (patch) | |
| tree | 2bda142f92febc8b26f1cabd4bb0c46d1864f34b /chapter11/src | |
| parent | c3958e34c0de21df52e57e47e4f47ffe6464f138 (diff) | |
| download | Simple-22df891893d30e9906d0b14fc3ae5d8e67d500b2.tar.gz Simple-22df891893d30e9906d0b14fc3ae5d8e67d500b2.zip | |
Chapter renumber, and split ch 17
Renumber chapters 10a, 10b, 11, 12, 13, 14 -> 10, 11, 13, 12, [11,14].
Split ch 17 into a 17a and 17b; shuffle around im/mutable syntax to be consistent, and present it more slowly.
THe new immutable syntax is pushed through all later chapters
Diffstat (limited to 'chapter11/src')
42 files changed, 288 insertions, 1396 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}); diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter01Test.java index c10dc510..89882b2f 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -15,7 +15,7 @@ public class Chapter01Test { StartNode start = Parser.START; ReturnNode ret = (ReturnNode)stop.in(0); - assertTrue(ret.ctrl() instanceof CProjNode); + assertTrue(ret.ctrl() instanceof ProjNode); Node expr = ret.expr(); if( expr instanceof ConstantNode con ) { assertEquals(start,con.in(0)); diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter04Test.java index 14d31245..edc62f50 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -83,7 +83,7 @@ public class Chapter04Test { Parser parser = new Parser("return arg; "); StopNode stop = parser.parse(); ReturnNode ret = stop.ret(); - assertTrue(ret.in(0) instanceof CProjNode); + assertTrue(ret.in(0) instanceof ProjNode); assertTrue(ret.in(1) instanceof ProjNode); assertEquals(1, ((ProjNode)ret.in(1))._idx); assertTrue(ret.in(2) instanceof ProjNode); diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 7beeb4d9..cf7bd6cf 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -22,7 +22,7 @@ else { return a;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region21,(arg+2),(arg-3));", ret.toString()); + assertEquals("return Phi(Region19,(arg+2),(arg-3));", ret.toString()); } @Test @@ -37,7 +37,7 @@ if (arg == 1) { } return c;""", TypeInteger.BOT); StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region19,4,3);", ret.toString()); + assertEquals("return Phi(Region17,4,3);", ret.toString()); } @Test @@ -65,7 +65,7 @@ else b=a+1; return a+b;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return ((arg*2)+Phi(Region24,2,3));", ret.toString()); + assertEquals("return ((arg*2)+Phi(Region22,2,3));", ret.toString()); } @Test @@ -80,7 +80,7 @@ else a=b+1; return a+b;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return ((Phi(Region35,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString()); + assertEquals("return ((Phi(Region33,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString()); } @Test @@ -100,7 +100,7 @@ else return a; """, TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region39,Phi(Region25,2,3),Phi(Region37,4,5));", stop.toString()); + assertEquals("return Phi(Region37,Phi(Region23,2,3),Phi(Region35,4,5));", stop.toString()); } @Test @@ -116,7 +116,7 @@ if( arg==0 ) return arg+a+b; """, TypeInteger.BOT); StopNode stop = parser.parse(); - assertEquals("return ((arg+Phi(Region16,1,0))+Phi(Region31,2,0));", stop.toString()); + assertEquals("return ((arg+Phi(Region14,1,0))+Phi(Region29,2,0));", stop.toString()); } @Test @@ -130,7 +130,7 @@ if( arg==1 ) } return a;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return (arg==Phi(Region19,3,2));", ret.toString()); + assertEquals("return (arg==Phi(Region17,3,2));", ret.toString()); } @Test diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter06Test.java index df0f2848..920e26e3 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -17,7 +17,7 @@ return 1; """); StopNode stop = parser.parse().iterate(); assertEquals("return 2;", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -30,7 +30,7 @@ if (arg) return (arg < a) < 3; """); StopNode stop = parser.parse().iterate(); - assertEquals("return ((arg<Phi(Region15,2,1))<3);", stop.toString()); + assertEquals("return ((arg<Phi(Region13,2,1))<3);", stop.toString()); } @Test @@ -46,7 +46,7 @@ return a; """); StopNode stop = parser.parse().iterate(); assertEquals("return 2;", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -65,7 +65,7 @@ else b=5; return b;""", TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region40,42,5);", stop.toString()); + assertEquals("return Phi(Region38,42,5);", stop.toString()); } @Test @@ -84,7 +84,7 @@ else b=5; return b;""", TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region33,2,5);", stop.toString()); + assertEquals("return Phi(Region31,2,5);", stop.toString()); } @Test @@ -144,7 +144,7 @@ else return a; """, TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region44,3,Phi(Region42,4,5));", stop.toString()); + assertEquals("return Phi(Region42,3,Phi(Region40,4,5));", stop.toString()); } @Test @@ -200,7 +200,7 @@ if( arg ) { return a+b; """); StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region27,4,1);", ret.toString()); + assertEquals("return Phi(Region25,4,1);", ret.toString()); } @@ -251,7 +251,7 @@ if( arg ) { return a+b+c; """); StopNode ret = parser.parse().iterate(); - assertEquals("return (Phi(Region39,Phi(Region26,2,3),0)+Phi(Region,3,1));", ret.toString()); + assertEquals("return (Phi(Region37,Phi(Region24,2,3),0)+Phi(Region,3,1));", ret.toString()); } diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter07Test.java index 222982e7..ff0ca599 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter07Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -18,8 +18,8 @@ public class Chapter07Test { return arg; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop9,arg,(Phi_arg+1));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop7,arg,(Phi_arg+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -35,7 +35,7 @@ if(arg){}else{ return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region27,1,Phi(Loop16,1,(Phi_a+1)));", stop.toString()); + assertEquals("return Phi(Region25,1,Phi(Loop14,1,(Phi_a+1)));", stop.toString()); } @Test @@ -55,7 +55,7 @@ while(i < arg) { return sum; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,0,Phi(Loop23,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); + assertEquals("return Phi(Loop9,0,Phi(Loop21,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); } @Test @@ -71,8 +71,8 @@ while(a < 10) { return b; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop11,2,Phi(Region30,Phi_b,4));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop9,2,Phi(Region28,Phi_b,4));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -90,8 +90,8 @@ while(a < 10) { return b; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,2,(Phi(Region30,Phi_b,4)+1));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop9,2,(Phi(Region28,Phi_b,4)+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -107,8 +107,8 @@ while(a < 10) { return a; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -123,8 +123,8 @@ while(a < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -136,8 +136,8 @@ while(arg) a = 2; return a; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop10,1,2);", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop8,1,2);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -149,8 +149,8 @@ while(arg) a = 2; return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,1,2);", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop8,1,2);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -165,8 +165,8 @@ while(a < 10) { return a; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -181,8 +181,8 @@ while(a < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -198,8 +198,8 @@ while(a < 10) { return a; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop11,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop9,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -215,8 +215,8 @@ while(a < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop9,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } } diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter08Test.java index 8fcb29a0..4fa08bd9 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -24,7 +24,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region37,Phi(Region27,Phi(Loop9,arg,(Phi_arg+1)),Add),Add);", stop.toString()); + assertEquals("return Phi(Region37,Phi(Region26,Phi(Loop7,arg,(Phi_arg+1)),Add),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); Assert.assertEquals(5L, Evaluator.evaluate(stop, 1)); Assert.assertEquals(10L, Evaluator.evaluate(stop, 6)); @@ -47,8 +47,8 @@ while(arg < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,1,Phi(Region42,Phi_a,(Phi_a+1)));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop8,1,Phi(Region43,Phi_a,(Phi_a+1)));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -66,7 +66,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region35,Phi(Loop9,arg,(Phi_arg+1)),Add);", stop.toString()); + assertEquals("return Phi(Region35,Phi(Loop7,arg,(Phi_arg+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -82,7 +82,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region27,Phi(Loop9,arg,(Phi_arg+1)),Add);", stop.toString()); + assertEquals("return Phi(Region26,Phi(Loop7,arg,(Phi_arg+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -101,8 +101,8 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop9,arg,(Phi_arg+1));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop7,arg,(Phi_arg+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -118,8 +118,8 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop9,arg,(Phi_arg+1));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop7,arg,(Phi_arg+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -186,7 +186,7 @@ while(arg < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region30,Phi(Loop10,1,(Phi_a+1)),Add);", stop.toString()); + assertEquals("return Phi(Region29,Phi(Loop8,1,(Phi_a+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -202,8 +202,8 @@ while(1) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return (Phi(Loop10,1,Add)+1);", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode prj && prj._idx==1 ); + assertEquals("return (Phi(Loop8,1,Add)+1);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode prj && prj._idx==1 ); } } diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter09Test.java index 7af2fa3d..1b1920e8 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -70,7 +70,7 @@ while (arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,arg,(Phi_arg+2));", stop.toString()); + assertEquals("return Phi(Loop8,arg,(Phi_arg+2));", stop.toString()); Assert.assertEquals(11L, Evaluator.evaluate(stop, 1)); } @@ -87,7 +87,7 @@ while (arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,arg,(Phi_arg+4));", stop.toString()); + assertEquals("return Phi(Loop9,arg,(Phi_arg+4));", stop.toString()); Assert.assertEquals(13L, Evaluator.evaluate(stop, 1)); } @@ -116,7 +116,7 @@ while (arg) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop17,arg,(Phi_arg+1));", stop.toString()); + assertEquals("return Phi(Loop15,arg,(Phi_arg+1));", stop.toString()); } @Test @@ -134,14 +134,14 @@ while(v1+arg) { } """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 0; return 0; ]", stop.toString()); + assertEquals("Stop[ ]", stop.toString()); } @Test public void testWhile0() { Parser parser = new Parser("while(0) continue; if(0) arg=0;"); StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + assertEquals("Stop[ ]", stop.toString()); } @Test @@ -153,7 +153,7 @@ if(0) while(0) { } """); StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + assertEquals("Stop[ ]", stop.toString()); } @@ -186,7 +186,7 @@ while(arg) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop12,0,(-(Phi_a+3)));", stop.toString()); + assertEquals("return Phi(Loop10,0,(-(Phi_a+3)));", stop.toString()); } @Test @@ -200,7 +200,7 @@ int v0=0!=0<-0; return -0+0+0; """); StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + assertEquals("Stop[ ]", stop.toString()); } @@ -215,7 +215,7 @@ return -0+0+0; public void testFuzz3() { Parser parser = new Parser("int v0=0; while(0==69) while(v0) return 0;"); StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + assertEquals("Stop[ ]", stop.toString()); } @Test @@ -227,7 +227,7 @@ while(1) { } """); StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + assertEquals("Stop[ ]", stop.toString()); } @Test @@ -249,19 +249,18 @@ while(1) { return 0!=0; """); StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + assertEquals("Stop[ ]", stop.toString()); } @Test public void testFuzz6() { - Parser parser = new Parser( -""" + Parser parser = new Parser(""" int v0=0; while(0==1) while(v0) v0=1+v0; -"""); + """); StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + assertEquals("Stop[ ]", stop.toString()); } @Test @@ -277,14 +276,14 @@ while(1) return v1+v0; """); StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + assertEquals("Stop[ ]", stop.toString()); } @Test public void testFuzz8() { Parser parser = new Parser("while(arg) arg = arg - 1; return arg;"); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop9,arg,(Phi_arg-1));", stop.toString()); + assertEquals("return Phi(Loop7,arg,(Phi_arg-1));", stop.toString()); } @Test diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 0da695a0..8bf1debe 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -2,11 +2,15 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.StopNode; +import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.node.LoadNode; import com.seaofnodes.simple.node.StoreNode; import com.seaofnodes.simple.evaluator.Evaluator; import java.util.BitSet; import org.junit.Test; + +import java.util.Arrays; + import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; @@ -165,7 +169,7 @@ while (arg) { return bar.a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop12,0,(Phi_a+2));", stop.toString()); + assertEquals("return Phi(Loop11,0,(Phi_a+2));", stop.toString()); } @Test @@ -217,7 +221,7 @@ if( bar ) bar.a = 1; return bar; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region17,null,new Bar);", stop.toString()); + assertEquals("return Phi(Region16,null,new Bar);", stop.toString()); } @Test @@ -233,7 +237,7 @@ else bar.a = 1; return rez; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region35,4,3);", stop.toString()); + assertEquals("return Phi(Region34,4,3);", stop.toString()); } @Test @@ -250,8 +254,7 @@ while(arg) { return ret; """); try { parser.parse().iterate(); fail(); } - catch( Exception e ) { - assertEquals("Might be null accessing 'v0'", e.getMessage()); } + catch( Exception e ) { assertEquals("Might be null accessing 'v0'", e.getMessage()); } } @Test @@ -287,7 +290,7 @@ while( i.x < i.len ) { return sum; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop17,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); + assertEquals("return Phi(Loop16,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); } @@ -303,12 +306,11 @@ while(arg) { v0.v0 = arg; arg = arg-1; if (arg==5) ret=v0; - } return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop12,new s0,Phi(Region34,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop11,new s0,Phi(Region34,new s0,Phi_ret));", stop.toString()); } @Test @@ -321,7 +323,6 @@ while(arg) { v0.v0 = arg; arg = arg-1; if (arg==5) ret=v0; - } return ret; """); @@ -343,7 +344,7 @@ while(arg < 10) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop12,new s0,Phi(Region32,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop11,new s0,Phi(Region32,new s0,Phi_ret));", stop.toString()); } @Test @@ -373,7 +374,7 @@ if(0) { } """); StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + assertEquals("Stop[ ]", stop.toString()); } @Test @@ -447,7 +448,7 @@ while(0) {} } """); StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + assertEquals("Stop[ ]", stop.toString()); } @Test @@ -461,6 +462,7 @@ return 0; assertEquals("return 0;", stop.toString()); } + @Test public void testReadBeforeStores() { var stop = new Parser(""" struct S { int x; int y; } @@ -547,8 +549,8 @@ return 0; if (arg) s.x=arg+1; else s.x=arg+2; return s; """).parse().iterate(); - // These chapters still bind struct Stores to branch control. - assertEquals(3,countMemoryNodes(stop,StoreNode.class,new BitSet())); + // The initializing slice also remains live as the aggregate default. + assertEquals(2,countMemoryNodes(stop,StoreNode.class,new BitSet())); assertEquals(2L,((Evaluator.Obj)Evaluator.evaluate(stop,0)).fields()[0]); assertEquals(4L,((Evaluator.Obj)Evaluator.evaluate(stop,3)).fields()[0]); } diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter10bTest.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter10bTest.java deleted file mode 100644 index 6f094cfb..00000000 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter10bTest.java +++ /dev/null @@ -1,64 +0,0 @@ -package com.seaofnodes.simple; - -import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.evaluator.Evaluator; -import org.junit.Test; -import static org.junit.Assert.*; - -public class Chapter10bTest { - @Test public void testIndependentField() { - var stop = new Parser(""" - struct S { int x; int y; } - S s = new S; - s.x = 42; - while (arg > 0) { s.y = s.y + arg; arg = arg - 1; } - return s.x; - """).parse().iterate(); - assertEquals("return 42;",stop.toString()); - assertEquals(42L,Evaluator.evaluate(stop,5)); - assertNull(stop.walk(n -> n instanceof LoadNode ? n : null)); - } - - @Test public void testParallelMemoryPhis() { - var stop = new Parser(""" - struct S { int x; int y; int z; } - S a = new S; S b = new S; - S p = a; if (arg) p = b; - while (arg > 0) { - a.x = p.x + arg; - a.y = p.y + 2; - a.z = p.z + 3; - arg = arg - 1; - } - return a; - """).parse().iterate(); - int[] phis = {0}; - stop.walk(n -> { - if (n instanceof MemPhiNode) phis[0]++; - if (n instanceof MemMergeNode m && m.in(1) instanceof BulkMemPhiNode b) - for(int a=b._aliases.nextSetBit(0); a>=0; a=b._aliases.nextSetBit(a+1)) - assertTrue(a<m.nIns() && m.in(a)!=null); - assertFalse(n instanceof PhiNode && n.isMem() && - !(n instanceof MemPhiNode) && !(n instanceof BulkMemPhiNode)); - return null; - }); - assertTrue(phis[0]>=3); - assertArrayEquals(new Object[]{1L,2L,3L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields()); - } - - @Test public void testLateSliceWorklist() throws ReflectiveOperationException { - // Seed 97 exposed a store selecting a bulk predecessor without queuing - // it. Keep both the worklist assertion and the final heap check. - for (int seed : new int[]{0,97,123,456}) { - var parser = new Parser(Chapter10Test.NESTED_MEMORY); - var field = IterPeeps.class.getDeclaredField("WORK"); - field.setAccessible(true); - Object work = field.get(null); - field = work.getClass().getDeclaredField("_R"); - field.setAccessible(true); - ((java.util.Random)field.get(work)).setSeed(seed); - var stop = parser.parse().iterate(); - assertArrayEquals(new Object[]{9L,25L,17L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields()); - } - } -} diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 4c2b42f1..5f92c9c1 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,567 +1,64 @@ package com.seaofnodes.simple; - +import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.evaluator.Evaluator; -import com.seaofnodes.simple.node.StopNode; import org.junit.Test; - - -import static org.junit.Assert.assertEquals; +import static org.junit.Assert.*; public class Chapter11Test { - - // A placeholder test used to rapidly rotate through fuzzer produced issues - @Test - public void testFuzzer() { - Parser parser = new Parser( -""" -while(-----arg) { - while(-arg) { - while(-----arg*---0) { - int N=--false==false<--arg; - while(N<-4==N) { - N=N+N; - } - } - { - int kzEl_r7EYz=3*----0!=-arg<(37*--97!=0/arg==arg)<=-(--arg!=0); - while(kzEl_r7EYz<---1) { - kzEl_r7EYz=kzEl_r7EYz+kzEl_r7EYz*arg>=24; - if(7) continue; - kzEl_r7EYz=false; - if(-kzEl_r7EYz+arg<-3) continue; - else { - while(kzEl_r7EYz) continue; - arg=----3; - kzEl_r7EYz=-(-----arg*1>-kzEl_r7EYz); - int v2uF_4ba=9; - } - } - } - int pjcp7rv=arg; - { - int m2ya3=--arg-pjcp7rv; - while(m2ya3<-----pjcp7rv>=pjcp7rv+--pjcp7rv!=---pjcp7rv!=-arg<---(-m2ya3)>m2ya3<=-----true>14!=--m2ya3) { - m2ya3=m2ya3+-(--0<=false<pjcp7rv/arg<=-true); - while((--m2ya3)<--arg<-----arg*false!=arg<pjcp7rv*arg) { - pjcp7rv=-3+-arg; - break; - } - while(-3) { - while(67+0-61) m2ya3=m2ya3; - if(----pjcp7rv==---(---arg)) pjcp7rv=0!=-23; - else pjcp7rv=----89; - while(m2ya3!=m2ya3<pjcp7rv) m2ya3=1; - while(--arg<=pjcp7rv) pjcp7rv=-32<=-m2ya3+62; - } - break; - } - } - { - int arg=-1<-9!=(-arg>=-pjcp7rv>=arg<=arg); - while(arg<-arg) { - arg=arg+--arg; - { - while((--93)--pjcp7rv*-pjcp7rv+arg) arg=0-(6>=(--(---41/(0))!=--pjcp7rv)>=---2*33); - pjcp7rv=11; - int c=pjcp7rv; - if(--107) break; - else break; - } - } - } - pjcp7rv=pjcp7rv; - int aR0Wkua=-pjcp7rv==pjcp7rv; - { - if(-0!=-0) while(-true) break; - else { - while(aR0Wkua) pjcp7rv=-0/pjcp7rv; - pjcp7rv=pjcp7rv; - } - } - } - if(-arg) { - { - int Isdlt0fr91=0!=arg; - while(Isdlt0fr91<-Isdlt0fr91==-Isdlt0fr91+true) { - Isdlt0fr91=Isdlt0fr91+-1!=true; - if(-arg) if(--arg<=Isdlt0fr91) Isdlt0fr91=-Isdlt0fr91; - int i=---arg<---arg!=--40; - { - int jVX43Ln4Dm=-(6)==-Isdlt0fr91/----0; - while(jVX43Ln4Dm<--(3-3)) { - jVX43Ln4Dm=jVX43Ln4Dm+-0<25; - i=24<--(jVX43Ln4Dm); - } - } - i=(arg!=----false>=7); - int Te=5>-arg; - break; - } - } - arg=arg!=--true/arg; - { - int UX=arg; - while(UX<-3*arg) { - UX=UX+arg/-1; - arg=-3--(-UX--47<arg==--arg==arg)/arg--UX>=-arg; - if(---12) while(-UX) break; - break; - } - } - continue; - } - if(arg) arg=--0; - else if(1) continue; - int DtTlhjYq=19==arg; - { - arg=--DtTlhjYq<=(DtTlhjYq/---DtTlhjYq<=-DtTlhjYq); - if(---arg) continue; - else { - int Zsl=40; - while(Zsl<--Zsl--false>((Zsl))==Zsl!=--DtTlhjYq-DtTlhjYq-DtTlhjYq) { - Zsl=Zsl+arg; - } - } - if((arg)) if(-DtTlhjYq) { - } - else while(((2)==3*arg/DtTlhjYq)<=0==---arg) return false; - else { - int lwbF=arg>=0; - while(lwbF<57) { - lwbF=lwbF+--(-arg+lwbF)>=-2>=arg!=arg; - arg=----0+0; - while(49) break; - if(true) DtTlhjYq=-----arg; - DtTlhjYq=0!=-----(0); - } - } - arg=---arg!=DtTlhjYq/--0; - DtTlhjYq=-DtTlhjYq/(--arg<arg); - if(32) { - int q=-DtTlhjYq; - while(q<arg*(0*q)/0) { - q=q+DtTlhjYq; - DtTlhjYq=arg; - } - } - else if(--arg) if(15) break; - else arg=0==arg<=-55>DtTlhjYq; - else { - } - DtTlhjYq=-0; - { - while((0)<-arg) DtTlhjYq=-DtTlhjYq; - } - if(30/--(arg)>=0) DtTlhjYq=-0>=arg; - else { - int Y2wcIQJ=--DtTlhjYq*---11; - if(arg==arg) { - Y2wcIQJ=-----Y2wcIQJ; - Y2wcIQJ=Y2wcIQJ<7; - if(DtTlhjYq) arg=arg; - else break; - while(-arg!=-31==(false<=-15>=-DtTlhjYq+--6*-----Y2wcIQJ<=---arg!=-Y2wcIQJ<=---0<-arg*--Y2wcIQJ)) DtTlhjYq=arg!=3; - } - continue; - } - arg=DtTlhjYq; - arg=--3/(---arg)>=80>=-DtTlhjYq<=DtTlhjYq; - arg=51+---(-true)!=arg!=----1==-DtTlhjYq; - if(11<=arg) if((arg)+79<32+(-arg)) continue; - else if(true==DtTlhjYq) break; - break; - } -} -if(arg!=62==arg) { - while(---arg) { - { - int bhmDacPM=arg/arg; - while(bhmDacPM<arg) { - bhmDacPM=bhmDacPM+80*((-bhmDacPM)/---bhmDacPM>1)<bhmDacPM-2!=7; - arg=-0; - arg=bhmDacPM>=-arg+-arg; - break; - } - } - int arg=true; - arg=arg<=arg; - { - int KlC=30; - while(KlC<-2) { - KlC=KlC+-1!=25<=-KlC>KlC>----0; - int Ij=arg>=-arg<=---10; - { - int LAbgurVa2R=-arg!=Ij; - while(LAbgurVa2R<-true) { - LAbgurVa2R=LAbgurVa2R+Ij; - KlC=-LAbgurVa2R; - Ij=42*(-Ij>true); - while(Ij) arg=KlC; - KlC=-----7>-(--KlC<--7)==-LAbgurVa2R; - } - } - int a=Ij<=-KlC; - if(Ij) { - int r1W=a!=-false; - } - else { - arg=56>=Ij; - while(54) break; - arg=8>=-(a<--Ij)/a>=-a-KlC; - } - int Yt_T=KlC; - arg=KlC; - } - } - if(----false/--arg/12+-----0) if(-9+-arg) while(arg!=(arg)) arg=--1>=-71-arg!=---(--arg*11+102)/--arg; - else if(----arg) continue; - if(-arg-arg) { - arg=-(-arg)*--(-3)<(-7==-arg----arg); - { - int arg=arg; - while(arg<-0>arg==-arg-(-arg>1+11)) { - arg=arg+6-arg!=--0>---30>=---arg<=arg/(3)+---arg; - } - } - arg=-arg+arg; - arg=--47+-arg<1>arg*(-arg==-arg--0>3); - arg=(----arg)!=arg+--59; - arg=--4+arg==-(arg)-arg; - } - else { - while(--true-----true*-25+-18>arg>=-----(-arg)---13) { - arg=-0+--true<false; - continue; - } - arg=true<=arg; - break; - } - arg=arg*22<--(0+-arg); - { - continue; - } - } - arg=1*---((3<=true)==---2); - arg=7+-(-1); - return arg+--true; -} -else { - int o3ypEsewxM=-(---arg); - int vzXB=(-(---11<=--o3ypEsewxM>=--0))<=-0/-arg; - int L=-arg; - int B4mHcrf=---vzXB; - int oZWGdzZl=-o3ypEsewxM; - int K6tQqa1=11; - while(0!=--L) { - int sdZfTM=vzXB*true+K6tQqa1; - while(sdZfTM<false) { - sdZfTM=sdZfTM+arg; - sdZfTM=oZWGdzZl; - K6tQqa1=-K6tQqa1; - arg=---K6tQqa1; - while((3+-K6tQqa1)<oZWGdzZl) { - if(-----(-1)) sdZfTM=-false; - {} - } - K6tQqa1=vzXB!=-(B4mHcrf+-7>false); - sdZfTM=vzXB; - } - } - L=false; - while(31) B4mHcrf=arg; - oZWGdzZl=-0<--oZWGdzZl<=--2; - if(K6tQqa1>=20<=46) { - if(-1+-L) if(oZWGdzZl) { - int wmhv=-----0; - } - int arg=0; - o3ypEsewxM=---(oZWGdzZl); - return -oZWGdzZl/0; - } - else if(arg) { - int yKk5=B4mHcrf>=4>K6tQqa1<-B4mHcrf/o3ypEsewxM; - return -K6tQqa1; - } - else { - if(---0) { - {} - {} - } - return o3ypEsewxM; + @Test public void testIndependentField() { + var stop = new Parser(""" + struct S { int x; int y; } + S s = new S; + s.x = 42; + while (arg > 0) { s.y = s.y + arg; arg = arg - 1; } + return s.x; + """).parse().iterate(); + assertEquals("return 42;",stop.toString()); + assertEquals(42L,Evaluator.evaluate(stop,5)); + assertNull(stop.walk(n -> n instanceof LoadNode ? n : null)); + } + + @Test public void testParallelMemoryPhis() { + var stop = new Parser(""" + struct S { int x; int y; int z; } + S a = new S; S b = new S; + S p = a; if (arg) p = b; + while (arg > 0) { + a.x = p.x + arg; + a.y = p.y + 2; + a.z = p.z + 3; + arg = arg - 1; + } + return a; + """).parse().iterate(); + int[] phis = {0}; + stop.walk(n -> { + if (n instanceof MemPhiNode) phis[0]++; + if (n instanceof MemMergeNode m && m.in(1) instanceof BulkMemPhiNode b) + for(int a=b._aliases.nextSetBit(0); a>=0; a=b._aliases.nextSetBit(a+1)) + assertTrue(a<m.nIns() && m.in(a)!=null); + assertFalse(n instanceof PhiNode && n.isMem() && + !(n instanceof MemPhiNode) && !(n instanceof BulkMemPhiNode)); + return null; + }); + assertTrue(phis[0]>=3); + assertArrayEquals(new Object[]{1L,2L,3L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields()); + } + + @Test public void testLateSliceWorklist() throws ReflectiveOperationException { + // Seed 97 exposed a store selecting a bulk predecessor without queuing + // it. Keep both the worklist assertion and the final heap check. + for (int seed : new int[]{0,97,123,456}) { + var parser = new Parser(Chapter10Test.NESTED_MEMORY); + var field = IterPeeps.class.getDeclaredField("WORK"); + field.setAccessible(true); + Object work = field.get(null); + field = work.getClass().getDeclaredField("_R"); + field.setAccessible(true); + ((java.util.Random)field.get(work)).setSeed(seed); + var stop = parser.parse().iterate(); + assertArrayEquals(new Object[]{9L,25L,17L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields()); } -} -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 9; return 0; return 0; ]", stop.toString()); - } - - - - @Test - public void testPrimes() { - Parser parser = new Parser( -""" -if( arg < 2 ) return 0; -int primeCount = 1; -int prime = 3; -while( prime <= arg ) { - int isPrime = 1; - // Check for even case, so the next loop need only check odds - if( (prime/2)*2 == prime ) - continue; - // Check odds up to sqrt of prime - int j = 3; - while( j*j <= prime ) { - if( (prime/j)*j == prime ) { - isPrime = 0; - break; - } - j = j + 2; - } - if( isPrime ) - primeCount = primeCount + 1; - prime = prime + 2; -} -return primeCount; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 0; return Phi(Loop20,1,Phi(Region82,Phi_primeCount,Phi(Region77,(Phi_primeCount+1),Phi_primeCount))); ]", stop.toString()); - assertEquals(0L, Evaluator.evaluate(stop, 1)); // No primes 1 or below - assertEquals(1L, Evaluator.evaluate(stop, 2)); // 2 - assertEquals(2L, Evaluator.evaluate(stop, 3)); // 2, 3 - assertEquals(2L, Evaluator.evaluate(stop, 4)); // 2, 3 - assertEquals(3L, Evaluator.evaluate(stop, 5)); // 2, 3, 5 - assertEquals(4L, Evaluator.evaluate(stop, 10)); // 2, 3, 5, 7 - } - - @Test - public void testAntiDeps1() { - Parser parser = new Parser( -""" -struct S { int f; } -S v=new S; -v.f = 2; -int i=new S.f; -i=v.f; -if (arg) v.f=1; -return i; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return .f;", stop.toString()); - } - - @Test - public void testAntiDeps2() { - Parser parser = new Parser( -""" -struct S { int f; } -S v = new S; -S t = new S; -int i = 0; -if (arg) { - if (arg+1) v = t; - i = v.f; -} else { - v.f = 2; -} -return i; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region34,.f,0);", stop.toString()); - } - - @Test - public void testAntiDeps3() { - Parser parser = new Parser( -""" -struct S { int f; } -S v0 = new S; -S? v1; -if (arg) v1 = new S; -if (v1) { - v0.f = v1.f; -} else { - v0.f = 2; -} -return v0; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return new S;", stop.toString()); - } - - - @Test - public void testAntiDeps4() { - Parser parser = new Parser( -""" -struct S { int f; } -S v = new S; -S t = new S; -int i = v.f; -if (arg+1) arg= 0; -while (arg) v.f = 2; -return i; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return .f;", stop.toString()); - } - - @Test - public void testAntiDeps5() { - Parser parser = new Parser( -""" -struct S { int f; } -S v = new S; -while(1) { - while(arg+1) { arg=arg-1; } - if (arg) break; - v.f = 2; -} -return v; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return new S;", stop.toString()); - } - - @Test - public void testAntiDeps6() { - Parser parser = new Parser( -""" -struct s { int v; } -s ptr=new s; -while( -arg ) - ptr = new s; -while(1) - arg = arg+ptr.v; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); - } - - @Test - public void testAntiDeps7() { - Parser parser = new Parser( -""" -struct S { int f; } -S v = new S; -S t = new S; -int i = v.f; -while (arg) { - v.f = arg; - arg = arg-1; -} -return i; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return .f;", stop.toString()); - } - - @Test - public void testAntiDeps8() { - Parser parser = new Parser( -""" -struct S { int f; } -S v = new S; -S t = new S; -while(arg) { - arg=arg-1; - int f = v.f; - v.f = 2; - if (arg) arg = f; - else v.f = 3; -} -return arg; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop15,arg,Phi(Region39,.f,0));", stop.toString()); - } - - @Test - public void testAntiDeps9() { - Parser parser = new Parser( -""" -struct S { int f; } -S v = new S; -S t = new S; -if (arg) { - v.f=2; - int i=t.f; - v.f=i; -} -return v; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return new S;", stop.toString()); - } - - @Test - public void testExample2() { - Parser parser = new Parser( - """ -struct S { int f; } -S v = new S; -int i = arg; -while (arg > 0) { - int j = i/3; - if (arg == 5) - v.f = j; - arg = arg - 1; -} -return v; -"""); - StopNode stop = parser.parse().iterate(); - //assertEquals("return new S;", stop.toString()); - } - - @Test - public void testSplit() { - Parser parser = new Parser( - """ -struct S { int f; } -S s = new S; -if( arg==0 ) s.f = 1; -else if (arg == 1) s.f = 1; -return s.f; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region41,1,Phi(Region36,1,0));", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 0)); - assertEquals(1L, Evaluator.evaluate(stop, 1)); - assertEquals(0L, Evaluator.evaluate(stop, 2)); - } - - @Test - public void testScheduleUse() { - Parser parser = new Parser( -""" -int v0=0; -while(0>=0) { - int v1=0; - v1=v0; - if(v1*0) - v0=-v1; -} -return 0; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); - } - - @Test - public void testLoopCarriedDep() { - Parser parser = new Parser( -""" -int v0=0; -{ - int v1=0; - while(v1) { - v1=1+(v0!=0); - v0=v1/0; - } -} -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); } } diff --git a/chapter11/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/chapter11/src/test/java/com/seaofnodes/simple/FuzzerWrap.java index 52c2a014..019140ad 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/FuzzerWrap.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/FuzzerWrap.java @@ -29,8 +29,8 @@ public class FuzzerWrap { fuzzer.fuzzPeepsRegression(seed); } - @Ignore @Test + @Ignore public void fuzzPeepsLarge() { var fuzzer = new Fuzzer(); for (int i=0; i<1000000; i++) diff --git a/chapter11/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter11/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index 355d906b..ac7c5e09 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -140,8 +140,7 @@ public class Evaluator { case StoreNode store -> store(store); case MemMergeNode merge -> MEMORY; case NewNode alloc -> alloc(alloc); - case CProjNode cproj -> ((Object[])val(cproj.ctrl()))[cproj._idx]; - case ProjNode proj -> ((Object[])val( proj.in(0) ))[ proj._idx]; + case ProjNode proj -> ((Object[])val(proj.ctrl()))[proj._idx]; default -> throw new AssertionError("Unexpected node " + node); }; } diff --git a/chapter11/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java b/chapter11/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java index d16f4300..48ac0562 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java @@ -164,7 +164,7 @@ public class Scheduler { * @return true if the node is not XCtrl. */ private static boolean isNotXCtrl(Node node) { - return !(node instanceof ConstantNode c && c.compute() == Type.XCONTROL) && !(node instanceof XCtrlNode); + return !(node instanceof ConstantNode c && c.compute() == Type.XCONTROL); } /** @@ -215,7 +215,7 @@ public class Scheduler { private void refinePlacement(NodeData data, BasicBlock block) { assert !isPinnedNode(data); data.block = data.block == null ? block : dom(data.block, block); - assert isValid(data); + assert isValid(data) : data.node.uniqueName()+" at "+data.block.entry.uniqueName(); } /** @@ -328,8 +328,6 @@ public class Scheduler { for(int i=1; i<r.nIns(); i++) { if (od(r.in(i)).map(d->d.block==null).orElse(false)) return false; } - } else if (node instanceof XCtrlNode) { - return false; } else { assert d(node.in(0)).block != null; } @@ -405,7 +403,7 @@ public class Scheduler { } } if (!(node instanceof ReturnNode)) - for (Node n:node._outputs) if (n!=null && n.isCFG() && isCFGNodeReady(n) && d(n).block == null) queue.push(d(n)); + for (Node n:node._outputs) if (n.isCFG() && isCFGNodeReady(n) && d(n).block == null) queue.push(d(n)); var b = block; for(var in:data.node._inputs) od(in).ifPresent(d->update(d, b)); } @@ -451,7 +449,7 @@ public class Scheduler { node = data.node; assert node.isCFG(); if (!(node instanceof ReturnNode)) { - for (var out : node._outputs) if (out!=null && out.isCFG() && isNotXCtrl(out)) markAlive(cfgQueue, out, true); + for (var out : node._outputs) if (out.isCFG() && isNotXCtrl(out)) markAlive(cfgQueue, out, true); } for (var in : node._inputs) if(in!=null && !in.isCFG() && isNotXCtrl(in)) markAlive(dataQueue, in, false); } @@ -505,7 +503,7 @@ public class Scheduler { */ private static Node findSingleCFGOut(Node node) { if (node instanceof StartNode) { - for(var n:node._outputs) if (n instanceof CProjNode p && p._idx==0) return p; + for(var n:node._outputs) if (n instanceof ProjNode p && p._idx==0) return p; return null; } assert node._outputs.stream().filter(Node::isCFG).limit(2).count()<=1; @@ -572,7 +570,7 @@ public class Scheduler { switch(block.exit) { case null: break; case IfNode i: - for(var out:i._outputs) if (out instanceof CProjNode p) block.next[p._idx] = blocks.get(p); + for(var out:i._outputs) if (out instanceof ProjNode p) block.next[p._idx] = blocks.get(p); break; case RegionNode r: block.next[0] = blocks.get(r); |
