diff options
| author | Cliff Click <cliffc@acm.org> | 2024-06-30 01:58:08 +0100 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2024-10-23 17:51:09 -0700 |
| commit | dc77490c735104497851ed8c12ae5c713ab05b04 (patch) | |
| tree | 251544a95f158f4bcccc4a8d393933e638037265 /src | |
| parent | b933257d6b26343f3ad517f5876bb5a0093ab403 (diff) | |
| download | Simple-dc77490c735104497851ed8c12ae5c713ab05b04.tar.gz Simple-dc77490c735104497851ed8c12ae5c713ab05b04.zip | |
Chapter 11: Global Code Motionlinear-chapter11
Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>
Diffstat (limited to 'src')
42 files changed, 1401 insertions, 233 deletions
diff --git a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java new file mode 100644 index 00000000..14540d46 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -0,0 +1,238 @@ + package com.seaofnodes.simple; + +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(Parser.START); + } + + // ------------------------------------------------------------------------ + // 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); + // Strictly for dead infinite loops, we can have entire code blocks + // not reachable from below - so we reach down, from above, one + // step. Since _schedEarly modifies the output arrays, the normal + // region._outputs ArrayList iterator throws CME. The extra edges + // are always *added* after any Phis, so just walk the Phi prefix. + if( cfg instanceof RegionNode region ) { + int len = region.nOuts(); + for( int i=0; i<len; i++ ) + if( region.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 not-pinned not-CFG inputs before self. Since skipping + // Pinned, this never walks the backedge of Phis (and thus spins around + // a data-only loop, eventually attempting relying on some pre-visited- + // not-post-visited data op with no scheduled control. + for( Node def : n._inputs ) + if( def!=null && !def.isPinned() ) + _schedEarly(def,visit); + // If not-pinned (e.g. constants, projections, phi) and not-CFG + if( !n.isPinned() ) { + // Schedule at deepest input + CFGNode early = Parser.START; // Maximally early, lowest idepth + for( int i=1; i<n.nIns(); i++ ) + if( 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(StartNode start) { + CFGNode[] late = new CFGNode[Node.UID()]; + Node[] ns = new Node[Node.UID()]; + _schedLate(start,ns,late); + for( int i=0; i<late.length; i++ ) + if( ns[i] != null ) + ns[i].setDef(0,late[i]); + } + + // Forwards post-order pass. Schedule all outputs first, then draw an + // idom-tree line from the LCA of uses to the early schedule. Schedule is + // legal anywhere on this line; pick the most control-dependent (largest + // idepth) in the shallowest loop nest. + private static void _schedLate(Node n, Node[] ns, CFGNode[] late) { + if( late[n._nid]!=null ) return; // Been there, done that + // 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); + if( n instanceof PhiNode phi ) late[n._nid] = phi.region(); + + // Walk Stores before Loads, so we can get the anti-deps right + for( Node use : n._outputs ) + if( isForwardsEdge(use,n) && + use._type instanceof TypeMem ) + _schedLate(use,ns,late); + // Walk everybody now + for( Node use : n._outputs ) + if( isForwardsEdge(use,n) ) + _schedLate(use,ns,late); + // Already implicitly scheduled + if( n.isPinned() ) return; + // Need to schedule n + + // Walk uses, gathering the LCA (Least Common Ancestor) of uses + CFGNode early = (CFGNode)n.in(0); + assert early != null; + CFGNode lca = null; + for( Node use : n._outputs ) + lca = use_block(n,use, late).idom(lca); + + // Loads may need anti-dependencies, raising their LCA + if( n instanceof LoadNode load ) + lca = find_anti_dep(lca,load,early,late); + + // 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 ) + if( found==null ) found = phi.region().cfg(i); + else Utils.TODO(); // Can be more than once + 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.idepth() > best.idepth() || best instanceof IfNode); + } + + // Skip iteration if a backedge + private static boolean isForwardsEdge(Node use, Node def) { + return use != null && def != null && + !(use.nIns()>2 && use.in(2)==def && (use instanceof LoopNode || (use instanceof PhiNode phi && phi.region() instanceof LoopNode))); + } + + private static CFGNode find_anti_dep(CFGNode lca, LoadNode load, CFGNode early, CFGNode[] late) { + // 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() ) + cfg._anti = load._nid; + // Walk load->mem uses, looking for Stores causing an anti-dep + for( Node mem : load.mem()._outputs ) { + switch( mem ) { + case StoreNode st: + lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st); + 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); + break; + case LoadNode ld: break; // Loads do not cause anti-deps on other loads + case ReturnNode ret: break; // Load must already be ahead of Return + default: throw Utils.TODO(); + } + } + return lca; + } + + // + private static CFGNode anti_dep( LoadNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st ) { + // Walk store blocks "reach" from its scheduled location to its earliest + for( ; stblk != defblk.idom(); stblk = stblk.idom() ) { + // Store and Load overlap, need anti-dependence + if( stblk._anti==load._nid ) { + lca = stblk.idom(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/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index cfe6d5cc..604770a4 100644 --- a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.node.*; import java.util.*; @@ -27,7 +28,7 @@ public class GraphVisualizer { // nodes in the graph. Collection<Node> all = findAll(stop, scope); StringBuilder sb = new StringBuilder(); - sb.append("digraph chapter10 {\n"); + sb.append("digraph chapter11 {\n"); sb.append("/*\n"); sb.append(stop._src); sb.append("\n*/\n"); @@ -79,7 +80,7 @@ public class GraphVisualizer { // Just the Nodes first, in a cluster no edges sb.append(doCtrl ? "\tsubgraph cluster_Controls {\n" : "\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name for (Node n : all) { - if (n instanceof ProjNode || n instanceof ScopeNode) + if (n instanceof ProjNode || n instanceof CProjNode || n instanceof ScopeNode || n==Parser.XCTRL) continue; // Do not emit, rolled into MultiNode or Scope cluster already if (_separateControlCluster && doCtrl && !n.isCFG()) continue; if (_separateControlCluster && !doCtrl && n.isCFG()) continue; @@ -100,9 +101,16 @@ public class GraphVisualizer { sb.append("\t\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">").append("\n"); sb.append("\t\t\t\t<TR>"); } - sb.append("<TD PORT=\"p").append(proj._idx).append("\""); - if (proj.isCFG()) sb.append(" BGCOLOR=\"yellow\""); - sb.append(">").append(proj.glabel()).append("</TD>"); + sb.append("<TD PORT=\"p").append(proj._idx).append("\">").append(proj.glabel()).append("</TD>"); + } + if (use instanceof CProjNode proj) { + if (!doProjTable) { + doProjTable = true; + sb.append("<TD>").append("\n"); + sb.append("\t\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">").append("\n"); + sb.append("\t\t\t\t<TR>"); + } + sb.append("<TD PORT=\"p").append(proj._idx).append("\" BGCOLOR=\"yellow\">").append(proj.glabel()).append("</TD>"); } } if (doProjTable) { @@ -178,7 +186,7 @@ public class GraphVisualizer { // Do not display the Constant->Start edge; // ProjNodes handled by Multi; // ScopeNodes are done separately - if( n instanceof ConstantNode || n instanceof ProjNode || n instanceof ScopeNode ) + if( n instanceof ConstantNode || n instanceof ProjNode || n instanceof CProjNode || n instanceof ScopeNode || n==Parser.XCTRL ) continue; for( int i=0; i<n.nIns(); i++ ) { Node def = n.in(i); @@ -191,9 +199,12 @@ public class GraphVisualizer { } else if( def != null ) { // Most edges land here use->def sb.append('\t').append(n.uniqueName()).append(" -> "); - if( def instanceof ProjNode proj ) { + if( def instanceof CProjNode proj ) { String mname = proj.ctrl().uniqueName(); sb.append(mname).append(":p").append(proj._idx); + } else if( def instanceof ProjNode proj ) { + String mname = proj.in(0).uniqueName(); + sb.append(mname).append(":p").append(proj._idx); } else sb.append(def.uniqueName()); // Number edges, so we can see how they track sb.append("[taillabel=").append(i); @@ -231,7 +242,7 @@ public class GraphVisualizer { .append(scopeName).append(":") .append('"').append(makePortName(scopeName, name)).append('"') // wrap port name with quotes because $ctrl is not valid unquoted .append(" -> "); - if( def instanceof ProjNode proj ) { + if( def instanceof CProjNode proj ) { String mname = proj.ctrl().uniqueName(); sb.append(mname).append(":p").append(proj._idx); } else sb.append(def.uniqueName()); diff --git a/src/main/java/com/seaofnodes/simple/IRPrinter.java b/src/main/java/com/seaofnodes/simple/IRPrinter.java index f08f3208..43c6c9f7 100644 --- a/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -1,11 +1,10 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.node.LoopNode; -import com.seaofnodes.simple.node.Node; -import com.seaofnodes.simple.node.ProjNode; - +import com.seaofnodes.simple.node.*; +import java.lang.StringBuilder; import java.util.ArrayList; import java.util.BitSet; +import java.util.HashMap; public class IRPrinter { @@ -20,12 +19,12 @@ public class IRPrinter { } for( Node def : n._inputs ) sb.append(def==null ? "____ " : "%4d ".formatted(def._nid)); - for( int i = n._inputs.size(); i<3; i++ ) + for( int i = n._inputs.size(); i<4; i++ ) sb.append(" "); sb.append(" [[ "); for( Node use : n._outputs ) sb.append(use==null ? "____ " : "%4d ".formatted(use._nid)); - int lim = 5 - Math.max(n._inputs.size(),3); + int lim = 6 - Math.max(n._inputs.size(),4); for( int i = n._outputs.size(); i<lim; i++ ) sb.append(" "); sb.append(" ]] "); @@ -68,7 +67,9 @@ public class IRPrinter { } public static String prettyPrint(Node node, int depth) { - return prettyPrint( node, depth, false ); + return Parser.SCHEDULED + ? prettyPrintScheduled( node, depth, false ) + : prettyPrint( node, depth, false ); } // Another bulk pretty-printer. Makes more effort at basic-block grouping. @@ -185,4 +186,81 @@ public class IRPrinter { return false; } } + + // Bulk pretty printer, knowing scheduling information is available + public static String prettyPrintScheduled( Node node, int depth, boolean llvmFormat ) { + // Backwards DFS walk to depth. + HashMap<Node,Integer> ds = new HashMap<>(); + _walk(ds,node,depth); + // Print by block with least idepth + StringBuilder sb = new StringBuilder(); + ArrayList<Node> bns = new ArrayList<>(); + while( !ds.isEmpty() ) { + CFGNode blk = null; + for( Node n : ds.keySet() ) { + CFGNode cfg = n instanceof CFGNode cfg0 && cfg0.blockHead() ? cfg0 : (CFGNode)n.in(0); + if( blk==null || cfg.idepth() < blk.idepth() ) + blk = cfg; + } + ds.remove(blk); + + // Print block header + sb.append("%-13.13s".formatted(label(blk)+":")); + sb.append( " ".repeat(4) ).append(" [[ "); + if( blk instanceof RegionNode || blk instanceof StopNode ) + for( int i=(blk instanceof StopNode ? 0 : 1); i<blk.nIns(); i++ ) + label(sb,blk.cfg(i)); + else if( !(blk instanceof StartNode) ) + label(sb,blk.cfg(0)); + sb.append(" ]] \n"); + + // Collect block contents that are in the depth limit + bns.clear(); + int xd = Integer.MAX_VALUE; + for( Node use : blk._outputs ) { + Integer i = ds.get(use); + if( i!=null && !(use instanceof CFGNode cfg && cfg.blockHead()) ) { + bns.add(use); + xd = Math.min(xd,i); + } + } + // Print Phis up front, if any + for( int i=0; i<bns.size(); i++ ) + if( bns.get(i) instanceof PhiNode phi ) + printLine( phi, sb, llvmFormat,bns,i--,ds); + + // Print block contents in depth order, bumping depth until whole block printed + for( ; !bns.isEmpty(); xd++ ) + for( int i=0; i<bns.size(); i++ ) + if( ds.get(bns.get(i))==xd ) + printLine( bns.get(i), sb, llvmFormat, bns, i--, ds ); + sb.append("\n"); + } + return sb.toString(); + } + + private static void _walk( HashMap<Node,Integer> ds, Node node, int d ) { + Integer nd = ds.get(node); + if( nd!=null && d <= nd ) return; // Been there, done that + ds.put(node,d); + if( d == 0 ) return; // Depth cutoff + for( Node def : node._inputs ) + if( def != null ) + _walk(ds,def,d-1); + } + + static String label( CFGNode blk ) { + if( blk instanceof StartNode ) return "START"; + return (blk instanceof LoopNode ? "LOOP" : "L")+blk._nid; + } + static void label( StringBuilder sb, CFGNode blk ) { + if( !blk.blockHead() ) blk = blk.cfg(0); + sb.append( "%-9.9s ".formatted( label( blk ) ) ); + } + static void printLine( Node n, StringBuilder sb, boolean llvmFormat, ArrayList<Node> bns, int i, HashMap<Node,Integer> ds ) { + printLine( n, sb, llvmFormat ); + Utils.del(bns,i); + ds.remove(n); + } + } diff --git a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java index 1cee1ccb..b2b76777 100644 --- a/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -94,6 +94,7 @@ public abstract class IterPeeps { if( show ) System.out.println(new GraphVisualizer().generateDotOutput(stop,null,null)); + GlobalCodeMotion.buildCFG(stop); return stop; } diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index fc84c9d9..e367f499 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -23,8 +23,14 @@ public class Parser { */ public static StartNode START; + public static ConstantNode ZERO; + public static XCtrlNode XCTRL; + public StopNode STOP; + // 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; @@ -77,11 +83,14 @@ 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, arg }); STOP = new StopNode(source); + ZERO = new ConstantNode(TypeInteger.constant(0)).peephole().keep(); + XCTRL= new XCtrlNode().peephole().keep(); } public Parser(String source) { @@ -105,9 +114,11 @@ 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 ProjNode(START, 0, ScopeNode.CTRL).peephole()); - _scope.define(ScopeNode.ARG0, TypeInteger.BOT, new ProjNode(START, 1, ScopeNode.ARG0).peephole()); + _scope.define(ScopeNode.CTRL, Type.CONTROL , new CProjNode(START, 0, ScopeNode.CTRL).peephole()); + _scope.define(ScopeNode.ARG0, TypeInteger.BOT, new ProjNode(START, 1, ScopeNode.ARG0).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()); @@ -236,8 +247,8 @@ public class Parser { // IfNode takes current control and predicate Node ifNode = new IfNode(ctrl(), pred).peephole(); // Setup projection nodes - Node ifT = new ProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); - Node ifF = new ProjNode(ifNode.unkeep(), 1, "False").peephole(); + Node ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); + Node ifF = new CProjNode(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 @@ -283,7 +294,7 @@ public class Parser { private ScopeNode jumpTo(ScopeNode toScope) { ScopeNode cur = _scope.dup(); - ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill current scope + ctrl(XCTRL); // 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() ) @@ -319,8 +330,8 @@ public class Parser { // IfNode takes current control and predicate Node ifNode = new IfNode(ctrl(), pred).peephole(); // Setup projection nodes - Node ifT = new ProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); - Node ifF = new ProjNode(ifNode.unkeep(), 1, "False").peephole().keep(); + Node ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); + Node ifF = new CProjNode(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(); @@ -366,7 +377,7 @@ public class Parser { private Node parseReturn() { var expr = require(parseExpression(), ";"); Node ret = STOP.addReturn(new ReturnNode(ctrl(), expr, _scope).peephole()); - ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill control + ctrl(XCTRL); // Kill control return ret; } @@ -568,7 +579,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 new ConstantNode(TypeInteger.constant(0)).peephole(); + if( matchx("false") ) return ZERO; if( matchx("null" ) ) return new ConstantNode(TypeMemPtr.NULLPTR).peephole(); if( matchx("new") ) { String structName = requireId(); @@ -586,12 +597,11 @@ 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 = START._aliasStarts.get(obj._name); for( Field field : obj._fields ) { - memAlias(alias, new StoreNode(field._fname, alias, memAlias(alias), n, initValue).peephole()); + memAlias(alias, new StoreNode(field._fname, alias, ctrl(), memAlias(alias), n, ZERO).peephole()); alias++; } return n.unkeep(); @@ -629,7 +639,7 @@ public class Parser { if( peek('=') ) _lexer._position--; else { Node val = parseExpression(); - memAlias(alias, new StoreNode(name, alias, memAlias(alias), expr, val).peephole()); + memAlias(alias, new StoreNode(name, alias, ctrl(), memAlias(alias), expr, val).peephole()); return expr; // "obj.a = expr" returns the expression while updating memory } } @@ -740,7 +750,16 @@ public class Parser { * Return the next non-white-space character */ private void skipWhiteSpace() { - while (isWhiteSpace()) _position++; + 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; + } } @@ -822,8 +841,9 @@ 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/src/main/java/com/seaofnodes/simple/Utils.java b/src/main/java/com/seaofnodes/simple/Utils.java index 4f2af769..f3ac25b1 100644 --- a/src/main/java/com/seaofnodes/simple/Utils.java +++ b/src/main/java/com/seaofnodes/simple/Utils.java @@ -55,11 +55,4 @@ 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/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/src/main/java/com/seaofnodes/simple/node/CFGNode.java new file mode 100644 index 00000000..b605071b --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -0,0 +1,92 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.Utils; + +import java.util.BitSet; +import java.util.HashSet; +import java.util.HashMap; + +/** Control Flow Graph Nodes + * <p> + * CFG nodes have a immediate dominator depth (idepth) and a loop nesting + * depth(loop_depth). + * <p> + * idepth is computed lazily upon first request, and is valid even in the + * Parser, and is used by peepholes during parsing and afterward. + * <p> + * loop_depth is computed after optimization as part of scheduling. + * + */ +public abstract class CFGNode extends Node { + + public CFGNode(Node... nodes) { super(nodes); } + + @Override public boolean isCFG() { return true; } + @Override public boolean isPinned() { return true; } + + public CFGNode cfg(int idx) { return (CFGNode)in(idx); } + + // Block head is Start, Region, CProj, but not e.g. If, Return, Stop + public boolean blockHead() { return false; } + + // Should be exactly 1 tail from a block head + public CFGNode blockTail() { + assert blockHead(); + for( Node n : _outputs ) + if( n instanceof CFGNode cfg ) + return cfg; + return null; + } + + // ------------------------------------------------------------------------ + /** + * Immediate dominator tree depth, used to approximate a real IDOM during + * parsing where we do not have the whole program, and also peepholes + * change the CFG incrementally. + * <p> + * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} + */ + public int _idepth; + public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + + // Return the immediate dominator of this Node and compute dom tree depth. + public CFGNode idom() { return cfg(0); } + + // Return the LCA of two idoms + public CFGNode idom(CFGNode rhs) { + if( rhs==null ) return this; + CFGNode lhs = this; + while( lhs != rhs ) { + var comp = lhs.idepth() - rhs.idepth(); + if( comp >= 0 ) lhs = lhs.idom(); + if( comp <= 0 ) rhs = rhs.idom(); + } + return lhs; + } + + // Loop nesting depth + public int _loopDepth; + public int loopDepth() { return _loopDepth==0 ? (_loopDepth = cfg(0).loopDepth()) : _loopDepth; } + + // Anti-dependence field support + public int _anti; // Per-CFG field to help find anti-deps + + // ------------------------------------------------------------------------ + // Support routines for Global Code Motion + + // Tik-tok recursion pattern. This method is final, and every caller does + // this work. + public final void walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { + if( visit.get(_nid) ) return; + visit.set(_nid); + _walkUnreach(visit,unreach); + unreach.remove(this); // Since we reached here... Node was not unreachable + } + + // Tik-tok recursion pattern; not-final; callers override this. + void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { + cfg(0).walkUnreach(visit,unreach); + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/CProjNode.java b/src/main/java/com/seaofnodes/simple/node/CProjNode.java new file mode 100644 index 00000000..fb0ff879 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/CProjNode.java @@ -0,0 +1,61 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; +import com.seaofnodes.simple.type.TypeTuple; +import java.util.BitSet; + +public class CProjNode extends CFGNode { + + // Which slice of the incoming multipart value + public final int _idx; + + // Debugging label + public final String _label; + + public CProjNode(Node ctrl, int idx, String label) { + super(ctrl); + _idx = idx; + _label = label; + } + + @Override public String label() { return _label; } + + @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(_label); } + + @Override public boolean isMultiTail() { return in(0).isMultiHead(); } + @Override public boolean blockHead() { return true; } + + public CFGNode ctrl() { return cfg(0); } + + @Override + public Type compute() { + Type t = ctrl()._type; + return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; + } + + @Override + public Node idealize() { + if ( ctrl() instanceof IfNode iff ) { + if ( iff._type instanceof TypeTuple tt && tt._types[1 - _idx] == Type.XCONTROL ) + return iff.in(0); // We become our input control + + // Flip a negating if-test, to remove the not + if( iff.pred().addDep(this) instanceof NotNode not ) + return new CProjNode(new IfNode(iff.ctrl(),not.in(1)).peephole(),1-_idx,_idx==0 ? "False" : "True"); + } + return null; + } + + @Override + public Node getBlockStart() { + return ctrl() instanceof IfNode ? this : ctrl().getBlockStart(); + } + @Override + boolean eq( Node n ) { return _idx == ((CProjNode)n)._idx; } + + @Override + int hash() { return _idx; } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index ca42c2dc..cf1a76b0 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -36,6 +36,8 @@ public class ConstantNode extends Node { } @Override public boolean isMultiTail() { return true; } + // The special forever-zero is pinned, all others can sink + @Override public boolean isPinned() { return this==Parser.ZERO; } @Override public Type compute() { return _con; } diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 1cf4ddaf..5457ac6e 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -5,8 +5,9 @@ import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeTuple; import java.util.BitSet; +import java.util.HashSet; -public class IfNode extends MultiNode { +public class IfNode extends CFGNode implements MultiNode { public IfNode(Node ctrl, Node pred) { super(ctrl, pred); @@ -22,7 +23,6 @@ public class IfNode extends MultiNode { return in(1)._print0(sb, visited).append(" )"); } - @Override public boolean isCFG() { return true; } @Override public boolean isMultiHead() { return true; } public Node ctrl() { return in(0); } @@ -52,11 +52,20 @@ public class IfNode extends MultiNode { // Hunt up the immediate dominator tree. If we find an identical if // test on either the true or false branch, that side wins. if( !pred()._type.isHighOrConst() ) - for( Node dom = idom(), prior=this; dom!=null; prior = dom, dom = dom.idom() ) - if( dom.addDep(this) instanceof IfNode iff && iff.pred().addDep(this)==pred() && prior instanceof ProjNode prj ) { + for( CFGNode dom = idom(), prior=this; dom!=null; prior = dom, dom = dom.idom() ) + if( dom.addDep(this) instanceof IfNode iff && iff.pred().addDep(this)==pred() && prior instanceof CProjNode prj ) { setDef(1,new ConstantNode(TypeInteger.make(true,prj._idx==0?1:0)).peephole()); return this; } return null; } + + @Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { + for( Node proj : _outputs ) + if( ((CProjNode)proj)._loopDepth == 0 ) + unreach.add((CProjNode)proj); + super._walkUnreach(visit,unreach); + } + + @Override public Node getBlockStart() { return ctrl().getBlockStart(); } } diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 53ae1096..296237f4 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -21,7 +21,7 @@ public class LoadNode extends MemOpNode { * @param memPtr The ptr to the struct from where we load a field */ public LoadNode(String name, int alias, Type glb, Node memSlice, Node memPtr) { - super(name, alias, memSlice, memPtr, null); + super(name, alias, null, memSlice, memPtr); _declaredType = glb; } @@ -45,7 +45,7 @@ public class LoadNode extends MemOpNode { // Simple Load-after-Store on same address. if( mem() instanceof StoreNode st && ptr() == st.ptr() ) { // Must check same object - assert Utils.eq(_name,st._name); // Equiv class aliasing is perfect + assert _name.equals(st._name); // Equiv class aliasing is perfect return st.val(); } diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java index ea1489c4..c662dee6 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -1,15 +1,17 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; - +import com.seaofnodes.simple.type.TypeInteger; import java.util.BitSet; +import java.util.HashSet; public class LoopNode extends RegionNode { - public LoopNode( Node entry ) { super(null,entry,null); } - Node entry() { return in(1); } - Node back () { return in(2); } + public CFGNode entry() { return cfg(1); } + public CFGNode back () { return cfg(2); } @Override public String label() { return "Loop"; } @@ -25,7 +27,51 @@ public class LoopNode extends RegionNode { return inProgress() ? null : super.idealize(); } - // Bypass Region idom, same as the default idom() using use entry in(1) instead of in(0) - @Override int idepth() { return _idepth(1); } - @Override Node idom() { return entry(); } + // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) + @Override public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) + @Override public CFGNode idom() { return entry(); } + + @Override public int loopDepth() { + if( _loopDepth!=0 ) return _loopDepth; // Was already set + _loopDepth = entry()._loopDepth+1; // Entry depth plus one + // One-time tag loop exits + for( CFGNode idom = back(); idom!=this; idom = idom.idom() ) { + // Walk idom in loop, setting depth + idom._loopDepth = _loopDepth; + // Loop exit hits the CProj before the If, instead of jumping from + // Region directly to If. + if( idom instanceof CProjNode proj ) { + assert proj.in(0) instanceof IfNode; // Loop exit test + // Find the loop exit CProj, and set loop_depth + for( Node use : proj.in(0)._outputs ) + if( use instanceof CProjNode proj2 && proj2 != idom ) + proj2._loopDepth = _loopDepth-1; + } + } + return _loopDepth; + } + + // If this is an unreachable loop, it may not have an exit. If it does not + // (i.e., infinite loop), force an exit to make it reachable. + public void forceExit( StopNode stop ) { + // Walk the backedge, then immediate dominator tree util we hit this + // Loop again. If we ever hit a CProj from an If (as opposed to + // directly on the If) we found our exit. + CFGNode x = back(); + while( x != this ) { + if( x instanceof CProjNode exit ) + return; // Found an exit, not an infinite loop + x = x.idom(); + } + // Found a no-exit loop. Insert an exit + NeverNode iff = new NeverNode(back()); + for( Node use : _outputs ) + if( use instanceof PhiNode phi ) + iff.addDef(use); + CProjNode t = new CProjNode(iff,0,"True" ); + CProjNode f = new CProjNode(iff,1,"False"); + setDef(2,f); + stop.addDef(new ReturnNode(t,Parser.ZERO,null)); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 08e08bbf..551d2aa9 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -12,8 +12,8 @@ public abstract class MemOpNode extends Node { public final String _name; public final int _alias; - public MemOpNode(String name, int alias, Node memSlice, Node memPtr, Node value) { - super(null, memSlice, memPtr, value); + public MemOpNode(String name, int alias, Node... nodes) { + super(nodes); _name = name; _alias = alias; } diff --git a/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/src/main/java/com/seaofnodes/simple/node/MultiNode.java index 2743bd19..379e140d 100644 --- a/src/main/java/com/seaofnodes/simple/node/MultiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MultiNode.java @@ -1,12 +1,10 @@ package com.seaofnodes.simple.node; -public abstract class MultiNode extends Node { - - public MultiNode(Node... inputs) { super(inputs); } +public interface MultiNode extends OutNode { // Find a projection by index - ProjNode proj( int idx ) { - for( Node out : _outputs ) + default ProjNode proj( int idx ) { + for( Node out : outs() ) if( out instanceof ProjNode prj && prj._idx==idx ) return prj; return null; diff --git a/src/main/java/com/seaofnodes/simple/node/NeverNode.java b/src/main/java/com/seaofnodes/simple/node/NeverNode.java new file mode 100644 index 00000000..f50d3503 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/NeverNode.java @@ -0,0 +1,19 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.type.Type; +import java.util.BitSet; + +// "Never true" for infinite loop exits +public class NeverNode extends IfNode { + public NeverNode(Node ctrl) { super(ctrl,Parser.ZERO); } + + @Override public String label() { return "Never"; } + + @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append("Never"); } + + @Override public Type compute() { return TypeInteger.BOT; } + + @Override public Node idealize() { return null; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/NewNode.java b/src/main/java/com/seaofnodes/simple/node/NewNode.java index 352689b5..0724ec56 100644 --- a/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -26,6 +26,8 @@ public class NewNode extends Node { return sb.append(_ptr._obj.str()); } + @Override public boolean isPinned() { return true; } + @Override public Type compute() { return _ptr; } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index bb698860..fc49ad6a 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.IRPrinter; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; @@ -13,7 +14,7 @@ import java.util.function.Function; * The Node class provides common functionality used by all subtypes. * Subtypes of Node specialize by overriding methods. */ -public abstract class Node { +public abstract class Node implements OutNode { /** * Each node has a unique dense Node ID within a compilation context @@ -128,6 +129,7 @@ public abstract class Node { */ public Node in(int i) { return _inputs.get(i); } public Node out(int i) { return _outputs.get(i); } + @Override public ArrayList<Node> outs() { return _outputs; } public int nIns() { return _inputs.size(); } @@ -135,9 +137,7 @@ public abstract class Node { public boolean isUnused() { return nOuts() == 0; } - public boolean isCFG() { return false; } - - public boolean isMem() { return false; } + public CFGNode cfg0() { return (CFGNode)in(0); } /** * Change a <em>def</em> into a Node. Keeps the edges correct, by removing @@ -164,11 +164,11 @@ public abstract class Node { // the new_def might get killed if the old node kills it recursively. if( new_def != null ) new_def.addUse(this); + // Set the new_def over the old (killed) edge + _inputs.set(idx,new_def); if( old_def != null && // If the old def exists, remove a def->use edge old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def - // Set the new_def over the old (killed) edge - _inputs.set(idx,new_def); moveDepsToWorklist(); // Return self for easy flow-coding return new_def; @@ -196,7 +196,7 @@ public abstract class Node { * @param new_def the new definition, appended to the end of existing definitions * @return new_def for flow coding */ - Node addDef(Node new_def) { + public Node addDef(Node new_def) { unlock(); // Add use->def edge _inputs.add(new_def); @@ -323,8 +323,8 @@ public abstract class Node { Type old = setType(compute()); // Replace constant computations from non-constants with a constant node - if( !(this instanceof ConstantNode) && _type.isHighOrConst() ) - return new ConstantNode(_type).peepholeOpt(); + if( !(this instanceof ConstantNode) && !(this instanceof XCtrlNode) && _type.isHighOrConst() ) + return (_type==Type.XCONTROL ? new XCtrlNode() : new ConstantNode(_type)).peepholeOpt(); // Global Value Numbering if( _hash==0 ) { @@ -531,6 +531,20 @@ public abstract class Node { // Subclasses add extra hash info (such as ConstantNodes constant) int hash() { return 0; } + // ------------------------------------------------------------------------ + // + + /** Is this Node control-flow-graph related */ + public boolean isCFG() { return false; } + + /** Is this Node Memory related */ + public boolean isMem() { return false; } + + /** Return block start from a isCFG() */ + public Node getBlockStart() { return null; } + + /** Pinned in the schedule */ + public boolean isPinned() { return false; } // ------------------------------------------------------------------------ // Peephole utilities @@ -561,20 +575,6 @@ public abstract class Node { } - /** - * Immediate dominator tree depth, used to approximate a real IDOM depth - * during parsing where we do not have the whole program, and also - * peepholes change the CFG incrementally. - * <p> - * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} - */ - public int _idepth; // IDOM depth approx; Zero is unset; non-zero is cached legit - final int _idepth(int idx) { return _idepth==0 ? (_idepth=in(idx).idepth()+1) : _idepth; } - int idepth() { return _idepth(0); } - - // Return the immediate dominator of this Node. - Node idom() { return in(0); } - // Make a shallow copy (same class) of this Node, with given inputs and // empty outputs and a new Node ID. The original inputs are ignored. // Does not need to be implemented in isCFG() nodes. diff --git a/src/main/java/com/seaofnodes/simple/node/OutNode.java b/src/main/java/com/seaofnodes/simple/node/OutNode.java new file mode 100644 index 00000000..7e531145 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/OutNode.java @@ -0,0 +1,7 @@ +package com.seaofnodes.simple.node; + +import java.util.ArrayList; + +public interface OutNode { + ArrayList<Node> outs(); +} diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index dd67bd06..a07dc140 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -35,10 +35,10 @@ public class PhiNode extends Node { return sb; } - Node region() { return in(0); } + public CFGNode region() { return (CFGNode)in(0); } @Override public boolean isMultiTail() { return true; } - @Override - public boolean isMem() { return _declaredType instanceof TypeMem; } + @Override public boolean isMem() { return _declaredType instanceof TypeMem; } + @Override public boolean isPinned() { return true; } @Override public Type compute() { @@ -102,9 +102,9 @@ public class PhiNode extends Node { Node val = in(3-nullx); if( region().idom() instanceof IfNode iff && iff.pred().addDep(this)==val ) { // Must walk the idom on the null side to make sure we hit False. - Node idom = region().in(nullx); + CFGNode idom = (CFGNode)region().in(nullx); while( idom.in(0) != iff ) idom = idom.idom(); - if( idom instanceof ProjNode proj && proj._idx==1 ) + if( idom instanceof CProjNode proj && proj._idx==1 ) return val; } } diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 735fcdf3..f94e98a7 100644 --- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -14,7 +14,7 @@ public class ProjNode extends Node { // Debugging label public final String _label; - public ProjNode(MultiNode ctrl, int idx, String label) { + public ProjNode(Node ctrl, int idx, String label) { super(ctrl); _idx = idx; _label = label; @@ -26,11 +26,9 @@ public class ProjNode extends Node { @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(_label); } - @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; } @Override public boolean isMultiTail() { return in(0).isMultiHead(); } @Override public boolean isMem() { return _type instanceof TypeMem; } - - public MultiNode ctrl() { return (MultiNode)in(0); } + @Override public boolean isPinned() { return true; } @Override public Type compute() { @@ -38,18 +36,7 @@ public class ProjNode extends Node { return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; } - @Override - public Node idealize() { - if ( ctrl() instanceof IfNode iff ) { - if ( iff._type instanceof TypeTuple tt && tt._types[1 - _idx] == Type.XCONTROL ) - return iff.in(0); // We become our input control - - // Flip a negating if-test, to remove the not - if( iff.pred().addDep(this) instanceof NotNode not ) - return new ProjNode((MultiNode)new IfNode(iff.ctrl(),not.in(1)).peephole(),1-_idx,_idx==0 ? "False" : "True"); - } - return null; - } + @Override public Node idealize() { return null; } @Override boolean eq( Node n ) { return _idx == ((ProjNode)n)._idx; } diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 42501118..dcc7ccef 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -1,14 +1,15 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; - import java.util.ArrayList; import java.util.Arrays; import java.util.BitSet; +import java.util.HashSet; -public class RegionNode extends Node { +public class RegionNode extends CFGNode { public RegionNode(Node... nodes) { super(nodes); } @@ -20,8 +21,8 @@ public class RegionNode extends Node { return sb.append(label()).append(_nid); } - @Override public boolean isCFG() { return true; } @Override public boolean isMultiHead() { return true; } + @Override public boolean blockHead() { return true; } @Override public Type compute() { @@ -57,7 +58,7 @@ public class RegionNode extends Node { IterPeeps.addAll(phi._outputs); } } - return isDead() ? new ConstantNode(Type.XCONTROL) : delDef(path); + return isDead() ? Parser.XCTRL : delDef(path); } // If down to a single input, become that input if( nIns()==2 && !hasPhi() ) @@ -89,31 +90,31 @@ public class RegionNode extends Node { } // Immediate dominator of Region is a little more complicated. - @Override int idepth() { + @Override public int idepth() { if( _idepth!=0 ) return _idepth; int d=0; for( Node n : _inputs ) if( n!=null ) - d = Math.max(d,n.idepth()); + d = Math.max(d,((CFGNode)n).idepth()+1); return _idepth=d; } - @Override Node idom() { - if( nIns()==2 ) return in(1); // 1-input is that one input - if( nIns()!=3 ) return null; // Fails for anything other than 2-inputs + @Override public CFGNode idom() { + CFGNode lca = null; // Walk the LHS & RHS idom trees in parallel until they match, or either fails. // Because this does not cache, it can be linear in the size of the program. - Node lhs = in(1); - Node rhs = in(2); - while( lhs != rhs ) { - if( lhs==null || rhs==null ) return null; - var comp = lhs.idepth() - rhs.idepth(); - if( comp >= 0 ) lhs = lhs.idom(); - if( comp <= 0 ) rhs = rhs.idom(); - } - return lhs; + for( int i=1; i<nIns(); i++ ) + lca = cfg(i).idom(lca); + return lca; + } + + @Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { + for( int i=1; i<nIns(); i++ ) + cfg(i).walkUnreach(visit,unreach); } + @Override public int loopDepth() { return _loopDepth==0 ? (_loopDepth = cfg(1).loopDepth()) : _loopDepth; } + // True if last input is null public final boolean inProgress() { return nIns()>1 && in(nIns()-1) == null; @@ -123,4 +124,6 @@ public class RegionNode extends Node { @Override boolean eq( Node n ) { return !inProgress(); } + + @Override public Node getBlockStart() { return this; } } diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 92bda5bf..444b76a8 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -13,16 +13,18 @@ import java.util.BitSet; * <p> * The Return's output is the value from the data node. */ -public class ReturnNode extends Node { +public class ReturnNode extends CFGNode { public ReturnNode(Node ctrl, Node data, ScopeNode scope) { super(ctrl, data); // We lookup memory slices by the naming convention that they start with $ // We could also use implicit knowledge that all memory projects are at offset >= 2 - String[] names = scope.reverseNames(); - for (String name: names) { - if (!name.equals("$ctrl") && name.startsWith("$")) - addDef(scope.lookup(name)); + if( scope != null ) { + String[] names = scope.reverseNames(); + for (String name: names) { + if (!name.equals("$ctrl") && name.startsWith("$")) + addDef(scope.lookup(name)); + } } } @@ -39,8 +41,6 @@ public class ReturnNode extends Node { return sb.append(";"); } - @Override public boolean isCFG() { return true; } - @Override public Type compute() { return TypeTuple.make(ctrl()._type,expr()._type); @@ -52,4 +52,6 @@ public class ReturnNode extends Node { return ctrl(); return null; } + + @Override public Node getBlockStart() { return ctrl().getBlockStart(); } } diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index 4b7e02a8..62fc8a6b 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.simple.type.*; import java.util.Arrays; import java.util.BitSet; import java.util.HashMap; +import java.util.HashSet; /** * The Start node represents the start of the function. @@ -13,7 +14,7 @@ import java.util.HashMap; * In ch10 we also add mem aliases as structs get defined; each field in struct * adds a distinct alias to Start's tuple. */ -public class StartNode extends MultiNode { +public class StartNode extends CFGNode implements MultiNode { // This field is NOT final, because the tuple expands as we add memory aliases TypeTuple _args; @@ -63,8 +64,8 @@ public class StartNode extends MultiNode { return sb.append(label()); } - @Override public boolean isCFG() { return true; } @Override public boolean isMultiHead() { return true; } + @Override public boolean blockHead() { return true; } @Override public TypeTuple compute() { return _args; } @@ -73,6 +74,12 @@ public class StartNode extends MultiNode { public Node idealize() { return null; } // No immediate dominator, and idepth==0 - @Override int idepth() { return 0; } - @Override Node idom() { return null; } + @Override public int idepth() { return 0; } + @Override public CFGNode idom() { return null; } + + @Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { } + + @Override public int loopDepth() { return (_loopDepth=1); } + + @Override public Node getBlockStart() { return this; } } diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java index 3b5a7ce3..94b2ad6d 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -5,7 +5,7 @@ import com.seaofnodes.simple.IterPeeps; import java.util.BitSet; -public class StopNode extends Node { +public class StopNode extends CFGNode { public final String _src; @@ -28,7 +28,7 @@ public class StopNode extends Node { return sb.append("]"); } - @Override public boolean isCFG() { return true; } + @Override public boolean blockHead() { return true; } // If a single Return, return it. // Otherwise, null because ambiguous. @@ -51,7 +51,17 @@ public class StopNode extends Node { return null; } - @Override public Node idom() { return null; } + @Override public int idepth() { + if( _idepth!=0 ) return _idepth; + int d=0; + for( Node n : _inputs ) + if( n!=null ) + d = Math.max(d,((CFGNode)n).idepth()+1); + return _idepth=d; + } + @Override public CFGNode idom() { return null; } + + @Override public int loopDepth() { return (_loopDepth=1); } public Node addReturn(Node node) { return addDef(node); @@ -64,4 +74,6 @@ public class StopNode extends Node { if( err != null ) throw new RuntimeException(err); return this; } + + @Override public Node getBlockStart() { return this; } } diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 8d264601..db8e2ce6 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -17,8 +17,8 @@ public class StoreNode extends MemOpNode { * @param memPtr The ptr to the struct where we will store a value * @param value Value to be stored */ - public StoreNode(String name, int alias, Node memSlice, Node memPtr, Node value) { - super(name, alias, memSlice, memPtr, value); + public StoreNode(String name, int alias, Node ctrl, Node memSlice, Node memPtr, Node value) { + super(name, alias, ctrl, memSlice, memPtr, value); } @Override @@ -48,7 +48,7 @@ public class StoreNode extends MemOpNode { // Must have exactly one use of "this" or you get weird // non-serializable memory effects in the worse case. st.checkNoUseBeyond(this) ) { - assert Utils.eq(_name,st._name); // Equiv class aliasing is perfect + assert _name.equals(st._name); // Equiv class aliasing is perfect setDef(1,st.mem()); return this; } diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index b87115cd..5ddcdb68 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; diff --git a/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java b/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java new file mode 100644 index 00000000..83779dd2 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java @@ -0,0 +1,13 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.Type; +import java.util.BitSet; + +public class XCtrlNode extends CFGNode { + public XCtrlNode( ) { super(Parser.START); } + @Override public String label() { return "Xctrl"; } + @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append("Xctrl"); } + @Override public Type compute() { return Type.XCONTROL; } + @Override public Node idealize() { return null; } +} diff --git a/src/main/java/com/seaofnodes/simple/type/Field.java b/src/main/java/com/seaofnodes/simple/type/Field.java index 56626482..e1c337d4 100644 --- a/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/src/main/java/com/seaofnodes/simple/type/Field.java @@ -47,7 +47,7 @@ public class Field extends Type { boolean eq(Type t) { Field f = (Field)t; - return Utils.eq(_fname,f._fname) && _type==f._type; + return _fname.equals(f._fname) && _type==f._type; } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index d57f6c98..01bcbe9f 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -58,8 +58,7 @@ public class TypeTuple extends Type { for( Type t : _types ) t.typeName(sb).append(","); sb.setLength(sb.length()-1); - sb.append("]"); - return sb; + return sb.append("]"); } public static final TypeTuple IF_BOTH = make(new Type[]{Type. CONTROL,Type. CONTROL}); diff --git a/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/src/test/java/com/seaofnodes/simple/Chapter01Test.java index 89882b2f..c10dc510 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/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 ProjNode); + assertTrue(ret.ctrl() instanceof CProjNode); Node expr = ret.expr(); if( expr instanceof ConstantNode con ) { assertEquals(start,con.in(0)); diff --git a/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/src/test/java/com/seaofnodes/simple/Chapter04Test.java index e23a10b1..70f38dd6 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -55,8 +55,8 @@ public class Chapter04Test { Parser parser = new Parser("return arg; "); StopNode stop = parser.parse(); ReturnNode ret = stop.ret(); - assertTrue(ret.in(0) instanceof ProjNode); - assertTrue(ret.in(1) instanceof ProjNode); + assertTrue(ret.in(0) instanceof CProjNode); + assertTrue(ret.in(1) instanceof ProjNode); } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 35e54fa9..8d15493f 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -22,7 +22,7 @@ else { return a;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region18,(arg+2),(arg-3));", ret.toString()); + assertEquals("return Phi(Region20,(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(Region16,4,3);", ret.toString()); + assertEquals("return Phi(Region18,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(Region21,2,3));", ret.toString()); + assertEquals("return ((arg*2)+Phi(Region23,2,3));", ret.toString()); } @Test @@ -80,7 +80,7 @@ else a=b+1; return a+b;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return ((Phi(Region32,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString()); + assertEquals("return ((Phi(Region34,(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(Region36,Phi(Region22,2,3),Phi(Region34,4,5));", stop.toString()); + assertEquals("return Phi(Region38,Phi(Region24,2,3),Phi(Region36,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(Region13,1,0))+Phi(Region28,2,0));", stop.toString()); + assertEquals("return ((arg+Phi(Region15,1,0))+Phi(Region30,2,0));", stop.toString()); } @Test @@ -130,7 +130,7 @@ if( arg==1 ) } return a;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return (arg==Phi(Region16,3,2));", ret.toString()); + assertEquals("return (arg==Phi(Region18,3,2));", ret.toString()); } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java index 097c2617..7b11bc35 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/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 ProjNode); + assertTrue(stop.ret().ctrl() instanceof CProjNode); } @Test @@ -30,7 +30,7 @@ if (arg) return (arg < a) < 3; """); StopNode stop = parser.parse().iterate(); - assertEquals("return ((arg<Phi(Region12,2,1))<3);", stop.toString()); + assertEquals("return ((arg<Phi(Region14,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 ProjNode); + assertTrue(stop.ret().ctrl() instanceof CProjNode); } @Test @@ -65,7 +65,7 @@ else b=5; return b;""", TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region37,42,5);", stop.toString()); + assertEquals("return Phi(Region39,42,5);", stop.toString()); } @Test @@ -84,7 +84,7 @@ else b=5; return b;""", TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region30,2,5);", stop.toString()); + assertEquals("return Phi(Region32,2,5);", stop.toString()); } @Test @@ -144,7 +144,7 @@ else return a; """, TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region41,3,Phi(Region39,4,5));", stop.toString()); + assertEquals("return Phi(Region43,3,Phi(Region41,4,5));", stop.toString()); } @Test @@ -200,7 +200,7 @@ if( arg ) { return a+b; """); StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region24,4,1);", ret.toString()); + assertEquals("return Phi(Region26,4,1);", ret.toString()); } @@ -251,7 +251,7 @@ if( arg ) { return a+b+c; """); StopNode ret = parser.parse().iterate(); - assertEquals("return (Phi(Region36,Phi(Region23,2,3),0)+Phi(Region,3,1));", ret.toString()); + assertEquals("return (Phi(Region38,Phi(Region25,2,3),0)+Phi(Region,3,1));", ret.toString()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/src/test/java/com/seaofnodes/simple/Chapter07Test.java index de9d16f2..e604937c 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter07Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -19,8 +19,8 @@ public class Chapter07Test { """); Node._disablePeephole = true; StopNode stop = parser.parse(); - assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); + assertEquals("return Phi(Loop8,arg,(Phi_arg+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof CProjNode); Node._disablePeephole = false; } @@ -37,7 +37,7 @@ if(arg){}else{ return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region24,1,Phi(Loop13,1,(Phi_a+1)));", stop.toString()); + assertEquals("return Phi(Region26,1,Phi(Loop15,1,(Phi_a+1)));", stop.toString()); } @Test @@ -57,7 +57,7 @@ while(i < arg) { return sum; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop8,0,Phi(Loop20,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); + assertEquals("return Phi(Loop10,0,Phi(Loop22,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); } @Test @@ -74,8 +74,8 @@ return b; """); Node._disablePeephole = true; StopNode stop = parser.parse(); - assertEquals("return Phi(Loop8,2,Phi(Region27,Phi_b,4));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); + assertEquals("return Phi(Loop10,2,Phi(Region29,Phi_b,4));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof CProjNode); Node._disablePeephole = false; } @@ -94,8 +94,8 @@ while(a < 10) { return b; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop8,2,(Phi(Region27,Phi_b,4)+1));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); + assertEquals("return Phi(Loop10,2,(Phi(Region29,Phi_b,4)+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -112,8 +112,8 @@ return a; """); Node._disablePeephole = true; StopNode stop = parser.parse(); - assertEquals("return Phi(Loop7,1,((Phi_a+1)+2));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); + assertEquals("return Phi(Loop9,1,((Phi_a+1)+2));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof CProjNode); Node._disablePeephole = false; } @@ -129,8 +129,8 @@ while(a < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop7,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); + assertEquals("return Phi(Loop9,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof CProjNode); } @Test @@ -143,8 +143,8 @@ return a; """); Node._disablePeephole = true; StopNode stop = parser.parse(); - assertEquals("return Phi(Loop7,1,2);", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); + assertEquals("return Phi(Loop9,1,2);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof CProjNode); Node._disablePeephole = false; } @@ -157,8 +157,8 @@ while(arg) a = 2; return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop7,1,2);", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); + assertEquals("return Phi(Loop9,1,2);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof CProjNode); } @Test @@ -174,8 +174,8 @@ return a; """); Node._disablePeephole = true; StopNode stop = parser.parse(); - assertEquals("return Phi(Loop7,1,((Phi_a+1)+2));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); + assertEquals("return Phi(Loop9,1,((Phi_a+1)+2));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof CProjNode); Node._disablePeephole = false; } @@ -191,8 +191,8 @@ while(a < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop7,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); + assertEquals("return Phi(Loop9,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof CProjNode); } @Test @@ -209,8 +209,8 @@ return a; """); Node._disablePeephole = true; StopNode stop = parser.parse(); - assertEquals("return Phi(Loop8,1,((Phi_a+1)+2));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); + assertEquals("return Phi(Loop10,1,((Phi_a+1)+2));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof CProjNode); Node._disablePeephole = false; } @@ -227,8 +227,8 @@ while(a < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); + assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof CProjNode); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/src/test/java/com/seaofnodes/simple/Chapter08Test.java index 6688d598..98fd181b 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/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(Region36,Phi(Region25,Phi(Loop6,arg,(Phi_arg+1)),Add),Add);", stop.toString()); + assertEquals("return Phi(Region36,Phi(Region26,Phi(Loop8,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(Loop7,1,Phi(Region42,Phi_a,(Phi_a+1)));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); + assertEquals("return Phi(Loop9,1,Phi(Region41,Phi_a,(Phi_a+1)));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -66,7 +66,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region34,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString()); + assertEquals("return Phi(Region34,Phi(Loop8,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(Region25,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString()); + assertEquals("return Phi(Region26,Phi(Loop8,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(Loop6,arg,(Phi_arg+1));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); + assertEquals("return Phi(Loop8,arg,(Phi_arg+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -118,8 +118,8 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode); + assertEquals("return Phi(Loop8,arg,(Phi_arg+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof CProjNode); } @Test @@ -186,7 +186,7 @@ while(arg < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region28,Phi(Loop7,1,(Phi_a+1)),Add);", stop.toString()); + assertEquals("return Phi(Region29,Phi(Loop9,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(Loop7,1,Add)+1);", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof ProjNode prj && prj._idx==1 ); + assertEquals("return (Phi(Loop9,1,Add)+1);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof CProjNode prj && prj._idx==1 ); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/src/test/java/com/seaofnodes/simple/Chapter09Test.java index 048a58c7..2abce3cb 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/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(Loop7,arg,(Phi_arg+2));", stop.toString()); + assertEquals("return Phi(Loop9,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(Loop8,arg,(Phi_arg+4));", stop.toString()); + assertEquals("return Phi(Loop10,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(Loop14,arg,(Phi_arg+1));", stop.toString()); + assertEquals("return Phi(Loop16,arg,(Phi_arg+1));", stop.toString()); } @Test @@ -134,14 +134,14 @@ while(v1+arg) { } """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ ]", stop.toString()); + assertEquals("Stop[ return 0; return 0; ]", stop.toString()); } @Test public void testWhile0() { Parser parser = new Parser("while(0) continue; if(0) arg=0;"); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ ]", stop.toString()); + assertEquals("return 0;", stop.toString()); } @Test @@ -153,7 +153,7 @@ if(0) while(0) { } """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ ]", stop.toString()); + assertEquals("return 0;", stop.toString()); } @@ -186,7 +186,7 @@ while(arg) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop9,0,(-(Phi_a+3)));", stop.toString()); + assertEquals("return Phi(Loop11,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("Stop[ ]", stop.toString()); + assertEquals("return 0;", 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("Stop[ ]", stop.toString()); + assertEquals("return 0;", stop.toString()); } @Test @@ -227,7 +227,7 @@ while(1) { } """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ ]", stop.toString()); + assertEquals("return 0;", stop.toString()); } @Test @@ -249,18 +249,19 @@ while(1) { return 0!=0; """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ ]", stop.toString()); + assertEquals("return 0;", 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("Stop[ ]", stop.toString()); + assertEquals("return 0;", stop.toString()); } @Test @@ -276,14 +277,14 @@ while(1) return v1+v0; """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ ]", stop.toString()); + assertEquals("return 0;", 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(Loop6,arg,(Phi_arg-1));", stop.toString()); + assertEquals("return Phi(Loop8,arg,(Phi_arg-1));", stop.toString()); } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/src/test/java/com/seaofnodes/simple/Chapter10Test.java index f2e7ca2c..7371ff18 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -1,12 +1,7 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.StopNode; -import com.seaofnodes.simple.type.*; import org.junit.Test; - -import java.util.Arrays; - import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; @@ -108,7 +103,7 @@ while (arg) { return bar.a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,0,(Phi_a+2));", stop.toString()); + assertEquals("return Phi(Loop11,0,(Phi_a+2));", stop.toString()); } @Test @@ -160,7 +155,7 @@ if( bar ) bar.a = 1; return bar; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region15,null,new Bar);", stop.toString()); + assertEquals("return Phi(Region16,null,new Bar);", stop.toString()); } @Test @@ -176,7 +171,7 @@ else bar.a = 1; return rez; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region32,4,3);", stop.toString()); + assertEquals("return Phi(Region33,4,3);", stop.toString()); } @Test @@ -193,7 +188,8 @@ 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 @@ -229,7 +225,7 @@ while( i.x < i.len ) { return sum; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop14,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); + assertEquals("return Phi(Loop15,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); } @@ -245,11 +241,12 @@ while(arg) { v0.v0 = arg; arg = arg-1; if (arg==5) ret=v0; + } return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,new s0,Phi(Region31,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop11,new s0,Phi(Region31,new s0,Phi_ret));", stop.toString()); } @Test @@ -262,6 +259,7 @@ while(arg) { v0.v0 = arg; arg = arg-1; if (arg==5) ret=v0; + } return ret; """); @@ -283,7 +281,7 @@ while(arg < 10) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,new s0,Phi(Region30,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop11,new s0,Phi(Region30,new s0,Phi_ret));", stop.toString()); } @Test @@ -313,7 +311,7 @@ if(0) { } """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ ]", stop.toString()); + assertEquals("return 0;", stop.toString()); } @Test @@ -387,7 +385,7 @@ while(0) {} } """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ ]", stop.toString()); + assertEquals("return 0;", stop.toString()); } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/src/test/java/com/seaofnodes/simple/Chapter11Test.java new file mode 100644 index 00000000..fdf56b56 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -0,0 +1,565 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.StopNode; +import org.junit.Test; + + +import static org.junit.Assert.assertEquals; + +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; + } +} +"""); + 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(Loop19,1,Phi(Region81,Phi_primeCount,Phi(Region76,(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(Region31,.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(Loop13,arg,Phi(Region35,.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(Region35,1,Phi(Region33,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/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/src/test/java/com/seaofnodes/simple/FuzzerWrap.java index bb3bec1c..699711fc 100644 --- a/src/test/java/com/seaofnodes/simple/FuzzerWrap.java +++ b/src/test/java/com/seaofnodes/simple/FuzzerWrap.java @@ -10,12 +10,12 @@ import static org.junit.Assert.assertTrue; /** * To use the fuzzer run the <code>fuzzPeeps</code> methods. * This can be done from IntelliJ Gui or remove the `@Ignore` annotation and start the test case from the command line - * via <code>mvn clean test -Dtest=com.seaofnodes.simple.FuzzerWrap#fuzzPeeps</code> + * via <code>mvn clean test -Dtest=com.seaofnodes.simple.Fuzzer08Test#fuzzPeeps</code> */ public class FuzzerWrap { - @Test @Ignore + @Test public void fuzzPeeps() { var fuzzer = new Fuzzer(); for (int i=0; i<1000000; i++) diff --git a/src/test/java/com/seaofnodes/simple/SchedulerTest.java b/src/test/java/com/seaofnodes/simple/SchedulerTest.java index 5def2782..32c9c0c5 100644 --- a/src/test/java/com/seaofnodes/simple/SchedulerTest.java +++ b/src/test/java/com/seaofnodes/simple/SchedulerTest.java @@ -46,7 +46,7 @@ S v0=new S; if(arg) v0.f=1; return v0; """); - StopNode stop = parser.parse().iterate(); + StopNode stop = parser.parse(false).iterate(); var eval = new Evaluator(stop); assertObj(eval.evaluate(0, 10), "S", 0L); assertObj(eval.evaluate(1, 10), "S", 1L); @@ -65,7 +65,7 @@ i=v.f; if (arg) v.f=1; return i; """); - StopNode stop = parser.parse().iterate(); + StopNode stop = parser.parse(false).iterate(); var eval = new Evaluator(stop); assertEquals(2L, eval.evaluate(0, 10)); assertEquals(2L, eval.evaluate(1, 10)); diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index 3cf5c57b..4a405a3b 100644 --- a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -139,7 +139,8 @@ public class Evaluator { case LoadNode load -> load(load); case StoreNode store -> store(store); case NewNode alloc -> alloc(alloc); - case ProjNode proj -> ((Object[])val(proj.ctrl()))[proj._idx]; + case CProjNode cproj -> ((Object[])val(cproj.ctrl()))[cproj._idx]; + case ProjNode proj -> ((Object[])val( proj.in(0) ))[ proj._idx]; default -> throw new AssertionError("Unexpected node " + node); }; } diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java b/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java index 674d12f5..8b86d67a 100644 --- a/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java +++ b/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); + return !(node instanceof ConstantNode c && c.compute() == Type.XCONTROL) && !(node instanceof XCtrlNode); } /** @@ -322,6 +322,8 @@ 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; } @@ -397,7 +399,7 @@ public class Scheduler { } } if (!(node instanceof ReturnNode)) - for (Node n:node._outputs) if (n.isCFG() && isCFGNodeReady(n) && d(n).block == null) queue.push(d(n)); + for (Node n:node._outputs) if (n!=null && 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)); } @@ -443,7 +445,7 @@ public class Scheduler { node = data.node; assert node.isCFG(); if (!(node instanceof ReturnNode)) { - for (var out : node._outputs) if (out.isCFG() && isNotXCtrl(out)) markAlive(cfgQueue, out, true); + for (var out : node._outputs) if (out!=null && out.isCFG() && isNotXCtrl(out)) markAlive(cfgQueue, out, true); } for (var in : node._inputs) if(in!=null && !in.isCFG() && isNotXCtrl(in)) markAlive(dataQueue, in, false); } @@ -496,7 +498,7 @@ public class Scheduler { */ private static Node findSingleCFGOut(Node node) { if (node instanceof StartNode) { - for(var n:node._outputs) if (n instanceof ProjNode p && p._idx==0) return p; + for(var n:node._outputs) if (n instanceof CProjNode p && p._idx==0) return p; return null; } assert node._outputs.stream().filter(Node::isCFG).limit(2).count()<=1; @@ -563,7 +565,7 @@ public class Scheduler { switch(block.exit) { case null: break; case IfNode i: - for(var out:i._outputs) if (out instanceof ProjNode p) block.next[p._idx] = blocks.get(p); + for(var out:i._outputs) if (out instanceof CProjNode p) block.next[p._idx] = blocks.get(p); break; case RegionNode r: block.next[0] = blocks.get(r); |