From fc06aa2bebec45aa93df5450ebf4c327f9f51496 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 5 Aug 2024 16:15:27 -0700 Subject: Chapter 13: Global Code Motion MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Thalia Archibald Co-authored-by: Dibyendu Majumdar Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: RobertObkircher Co-authored-by: Robert Obkircher Co-authored-by: Jun Kawasaki Co-authored-by: Claude Opus 5 --- .../com/seaofnodes/simple/GlobalCodeMotion.java | 275 +++++++++++++++++++++ src/main/java/com/seaofnodes/simple/IRPrinter.java | 7 +- src/main/java/com/seaofnodes/simple/Parser.java | 59 +++-- src/main/java/com/seaofnodes/simple/Utils.java | 7 - .../java/com/seaofnodes/simple/node/AddNode.java | 1 + .../java/com/seaofnodes/simple/node/CFGNode.java | 96 +++++++ .../java/com/seaofnodes/simple/node/CProjNode.java | 62 +++++ .../java/com/seaofnodes/simple/node/CastNode.java | 1 + .../com/seaofnodes/simple/node/ConstantNode.java | 1 + .../java/com/seaofnodes/simple/node/IfNode.java | 18 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 17 +- .../java/com/seaofnodes/simple/node/LoopNode.java | 63 ++++- .../java/com/seaofnodes/simple/node/MultiNode.java | 16 +- .../java/com/seaofnodes/simple/node/NeverNode.java | 22 ++ .../java/com/seaofnodes/simple/node/NewNode.java | 1 + src/main/java/com/seaofnodes/simple/node/Node.java | 58 ++--- .../java/com/seaofnodes/simple/node/OutNode.java | 7 + .../java/com/seaofnodes/simple/node/PhiNode.java | 13 +- .../java/com/seaofnodes/simple/node/ProjNode.java | 18 +- .../com/seaofnodes/simple/node/RegionNode.java | 29 ++- .../com/seaofnodes/simple/node/ReturnNode.java | 9 +- .../java/com/seaofnodes/simple/node/StartNode.java | 21 +- .../java/com/seaofnodes/simple/node/StopNode.java | 28 ++- .../java/com/seaofnodes/simple/node/SubNode.java | 2 + .../java/com/seaofnodes/simple/node/XCtrlNode.java | 14 ++ .../simple/print/SimpleGraphAdapter.java | 8 +- .../simple/print/SimpleGraphObserver.java | 2 +- .../java/com/seaofnodes/simple/type/TypeTuple.java | 12 +- 28 files changed, 717 insertions(+), 150 deletions(-) create mode 100644 src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java create mode 100644 src/main/java/com/seaofnodes/simple/node/CFGNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/CProjNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/NeverNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/OutNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/XCtrlNode.java (limited to 'src/main/java/com/seaofnodes') 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..78a0dcde --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -0,0 +1,275 @@ + package com.seaofnodes.simple; + +import com.seaofnodes.simple.IterPeeps.WorkList; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import java.util.*; + +public abstract class GlobalCodeMotion { + + // Arrange that the existing isCFG() Nodes form a valid CFG. The + // Node.use(0) is always a block tail (either IfNode or head of the + // following block). There are no unreachable infinite loops. + public static void buildCFG( StopNode stop ) { + schedEarly(); + Parser.SCHEDULED = true; + schedLate( stop); + } + + // ------------------------------------------------------------------------ + // Backwards walk on the CFG only, looking for unreachable code - which has + // to be an infinite loop. Insert a bogus never-taken exit to Stop, so the + // loop becomes reachable. Also, set loop nesting depth + public static void fixLoops(StopNode stop) { + // Backwards walk from Stop, looking for unreachable code + BitSet visit = new BitSet(); + HashSet 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); + } + + // ------------------------------------------------------------------------ + // Visit all nodes in CFG Reverse Post-Order, essentially defs before uses + // (except at loops). Since defs are visited first - and hoisted as early + // as possible, when we come to a use we place it just after its deepest + // input. + private static void schedEarly() { + ArrayList rpo = new ArrayList<>(); + BitSet visit = new BitSet(); + _rpo_cfg(Parser.START, visit, rpo); + // Reverse Post-Order on CFG + for( int j=rpo.size()-1; j>=0; j-- ) { + CFGNode cfg = rpo.get(j); + cfg.loopDepth(); + for( Node n : cfg._inputs ) + _schedEarly(n,visit); + // In dead infinite loops, entire code blocks may be unreachable + // from below. Reach down from the CFG to their Phis so their + // inputs are scheduled too. + if( cfg instanceof RegionNode ) { + int len = cfg.nOuts(); + for( int i=0; i rpo) { + if( !(n instanceof CFGNode cfg) || visit.get(cfg._nid) ) + return; // Been there, done that + visit.set(cfg._nid); + for( Node use : cfg._outputs ) + _rpo_cfg(use,visit,rpo); + rpo.add(cfg); + } + + private static void _schedEarly(Node n, BitSet visit) { + if( n==null || visit.get(n._nid) ) return; // Been there, done that + visit.set(n._nid); + // Schedule inputs first, except Phis: following their backedges would + // enter a data cycle before its control has been scheduled. + for( Node def : n._inputs ) + if( def!=null && !(def instanceof PhiNode) ) + _schedEarly(def,visit); + // An existing edge 0 already supplies control (or a Phi/Proj binding). + if( n.in(0)==null ) { + // Schedule at deepest input + CFGNode early = Parser.START; // Maximally early, lowest idepth + for( int i=1; i early.idepth() ) + early = n.in(i).cfg0(); // Latest/deepest input + n.setDef(0,early); // First place this can go + } + } + + // ------------------------------------------------------------------------ + private static void schedLate( StopNode stop) { + CFGNode[] late = new CFGNode[Node.UID()]; + Node[] ns = new Node[Node.UID()]; + // Record Load NIDs at all their CFG block choices, then check against + // Store block choices to force a Load above an anti-dependent Store. + int[] anti = new int[Node.UID()]; + // Breadth-first scheduling + breadth(stop,ns,late,anti); + + // Copy the best placement choice into the control slot + for( int i=0; i work = new WorkList<>(); + work.push(stop); + Node n; + outer: + while( (n = work.pop()) != null ) { + assert late[n._nid]==null; // No double visit + // These I know the late schedule of, and need to set early for loops + if( n instanceof CFGNode cfg ) late[n._nid] = cfg.blockHead() ? cfg : cfg.cfg(0); + else if( n instanceof PhiNode phi ) late[n._nid] = phi.region(); + // These nodes have a fixed late placement at their original control. + else if( n instanceof ProjNode || n instanceof NewNode || n==Parser.ZERO || n instanceof CastNode ) late[n._nid] = n.cfg0(); + else { + + // All uses done? + for( Node use : n._outputs ) + if( use!=null && late[use._nid]==null ) + continue outer; // Nope, await all uses done + + // Loads need their memory inputs' uses also done + if( n instanceof LoadNode ld ) + for( Node memuse : ld.mem()._outputs ) + if( antiUse(ld,memuse) && late[memuse._nid]==null ) + continue outer; + + // All uses done, schedule + _doSchedLate(n,ns,late,anti); + } + + // A use just finished; reconsider its inputs and waiting loads, + // even when the shared memory input was already scheduled. + for( Node def : n._inputs ) { + if( def==null ) continue; + if( late[def._nid]==null ) work.push(def); + for( Node out : def._outputs ) + if( out instanceof LoadNode ld && late[ld._nid]==null ) + work.push(ld); + } + if( n instanceof LoopNode loop ) + for( Node phi : loop._outputs ) + if( phi instanceof PhiNode && late[phi._nid]==null ) + work.push(phi); + } + } + + private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { + // Walk uses, gathering the LCA (Least Common Ancestor) of uses + CFGNode early = (CFGNode)n.in(0); + assert early != null; + CFGNode lca = null; + for( Node use : n._outputs ) + lca = use_block(n,use, late).domLCA(lca,null); + + // Loads may need anti-dependencies, raising their LCA + if( n instanceof LoadNode load ) + lca = find_anti_dep(lca,load,early,late,anti); + + // Walk up from the LCA to the early, looking for best place. This is + // the lowest execution frequency, approximated by least loop depth and + // deepest control flow. + CFGNode best = lca; + lca = lca.idom(); // Already found best for starting LCA + for( ; lca != early.idom(); lca = lca.idom() ) + if( better(lca,best) ) + best = lca; + assert !(best instanceof IfNode); + ns [n._nid] = n; + late[n._nid] = best; + } + + // Block of use. Normally from late[] schedule, except for Phis, which go + // to the matching Region input. + private static CFGNode use_block(Node n, Node use, CFGNode[] late) { + if( !(use instanceof PhiNode phi) ) + return late[use._nid]; + CFGNode found=null; + for( int i=1; i best.idepth() || + best instanceof IfNode; + } + + // Only a store or memory Phi covering this alias can constrain a load. + // MemMerge packages slices without overwriting them. + private static boolean antiUse(LoadNode load, Node use) { + return switch( use ) { + case StoreNode st -> st._alias==load._alias; + case MemPhiNode phi -> phi._alias==load._alias; + case BulkMemPhiNode phi -> !phi.isSplit(load._alias); + default -> false; + }; + } + + private static CFGNode find_anti_dep(CFGNode lca, LoadNode load, CFGNode early, CFGNode[] late, int[] anti) { + // We could skip final-field loads here. + // Walk LCA->early, flagging Load's block location choices + for( CFGNode cfg=lca; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + anti[cfg._nid] = load._nid; + // Walk load->mem uses, looking for Stores causing an anti-dep + for( Node mem : load.mem()._outputs ) { + if( !antiUse(load,mem) ) continue; + switch( mem ) { + case StoreNode st: + assert late[st._nid]!=null; + lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti); + break; + case PhiNode phi: + // Repeat anti-dep for matching Phi inputs. + // No anti-dep edges but may raise the LCA. + for( int i=1; i { private static final com.seaofnodes.print.IRPrinter PRINT = new com.seaofnodes.print.IRPrinter<>(new IRPrinter()); @Override public String type(Node n) { return n._type==null ? "" : n._type.str(); } - @Override public int inputColumns() { return 3; } @Override public String inputMark(Node n, Node def) { return n instanceof MemMergeNode && def instanceof MemMergeNode ? "^" : " "; } @Override public Kind kind(Node n) { if( n instanceof StartNode ) return Kind.START; @@ -18,13 +17,15 @@ public final class IRPrinter extends IRAdapter { if( n instanceof PhiNode ) return Kind.PHI; if( n instanceof ReturnNode ) return Kind.RETURN; if( n instanceof ConstantNode ) return Kind.CONSTANT; - if( n instanceof ProjNode ) return n.isCFG() ? Kind.CPROJ : Kind.PROJ; - if( n.isCFG() ) return Kind.CTRL; + if( n instanceof CProjNode ) return Kind.CPROJ; + if( n instanceof ProjNode ) return n instanceof CFGNode ? Kind.CPROJ : Kind.PROJ; + if( n instanceof CFGNode ) return Kind.CTRL; if( n instanceof MultiNode ) return Kind.MULTI; return Kind.DATA; } @Override public int index(Node n) { if( n instanceof ProjNode p ) return p._idx; + if( n instanceof CProjNode p ) return p._idx; return n._nid; } diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index a25edeb1..3c8d8f40 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -31,12 +31,18 @@ public class Parser { */ public static StartNode START; + public static ConstantNode ZERO; + public static XCtrlNode XCTRL; + public StopNode STOP; // Field identities are independent of the memory graph and Start's tuple. private final HashMap _aliases = new HashMap<>(); private int _alias = 2; + // Debugger Printing. + public static boolean SCHEDULED; // True if debug printer can use schedule info + // The Lexer. Thin wrapper over a byte[] buffer with a cursor. private final Lexer _lexer; @@ -82,7 +88,7 @@ public class Parser { ScopeNode _continueScope; ScopeNode _breakScope; - // Authoritative declarations, indexed by type name. + // Mapping from a type name to a Type. public static HashMap TYPES = new HashMap<>(); public Parser(String source, TypeInteger arg) { @@ -91,11 +97,14 @@ public class Parser { IterPeeps.reset(); TYPES.clear(); TYPES.put("int",TypeInteger.BOT); + SCHEDULED = false; _lexer = new Lexer(source); _scope = new ScopeNode(); _continueScope = _breakScope = null; START = new StartNode(new Type[]{ Type.CONTROL, TypeMem.BOT, arg }); STOP = new StopNode(source); + ZERO = new ConstantNode(TypeInteger.constant(0)).peephole().keep(); + XCTRL= new XCtrlNode().peephole().keep(); } public Parser(String source) { @@ -118,8 +127,8 @@ 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, 2, 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, 2, ScopeNode.ARG0).peephole()); _scope.define("$mem", TypeMem.BOT, new ProjNode(START, 1, "$mem").peephole()); parseBlock(); if( ctrl()._type==Type.CONTROL ) @@ -187,7 +196,7 @@ public class Parser { } /** - * Parse a complete struct declaration. + * Parse a struct declaration, and return the following statement. * Only allowed in top level scope. * Structs cannot be redefined. * @@ -252,8 +261,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 @@ -299,7 +308,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() ) @@ -335,8 +344,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(); @@ -353,7 +362,7 @@ public class Parser { // Parse the false side _scope = fScope; // Restore scope, then parse else block if any ifF.unkeep(); // fScope already owns the false control - _scope.upcast(ifF,pred,true); // Up-cast predicate, also without an else + _scope.upcast(ifF,pred,true); // Up-cast predicate if (matchx("else")) { parseStatement(); fScope = _scope; @@ -383,7 +392,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; } @@ -436,7 +445,8 @@ public class Parser { return _scope.update(name,expr); } - // Parse a type-or-null + // Parse a "type id" and return "type" (and re-parse "id" in caller) or + // return null. private Type type() { int old = _lexer._position; String tname = _lexer.matchId(); @@ -457,6 +467,7 @@ public class Parser { return t instanceof TypeStruct obj ? TypeMemPtr.make(obj,nullable) : t; } + /** * Parse an expression of the form: * @@ -527,7 +538,7 @@ public class Parser { * @return a multiply expression {@link Node}, never {@code null} */ private Node parseMultiplication() { - var lhs = parseUnary(); + var lhs = parseUnary(); boolean mul; while( true ) { if( false ) ; else if( match("*") ) lhs = new MulNode(lhs,null); @@ -562,10 +573,10 @@ public class Parser { * @return a primary {@link Node}, never {@code null} */ private Node parsePrimary() { - if( _lexer.isNumber(_lexer.peek()) ) return parseIntegerLiteral(); + if( _lexer.isNumber(_lexer.peek()) ) return parseLiteral(); if( match("(") ) return require(parseExpression(), ")"); if( matchx("true" ) ) return new ConstantNode(TypeInteger.constant(1)).peephole(); - if( matchx("false") ) return new ConstantNode(TypeInteger.ZERO).peephole(); + if( matchx("false") ) return ZERO; if( matchx("null" ) ) return new ConstantNode(TypeMemPtr.NULLPTR).peephole(); if( matchx("new") ) { String structName = requireId(); @@ -600,7 +611,7 @@ public class Parser { private void store(String name, int alias, Type glb, Node ptr, Node val, boolean init) { Node prior = mem().keep(); - Node st = new StoreNode(name,alias,glb,null,prior,ptr,val,init).peephole(); + Node st = new StoreNode(name,alias,glb,ctrl(),prior,ptr,val,init).peephole(); mem(new MemMergeNode(prior,alias,st).peephole()); if( prior.unkeep().isUnused() ) prior.kill(); } @@ -649,7 +660,7 @@ public class Parser { * integerLiteral: [1-9][0-9]* | [0] * */ - private ConstantNode parseIntegerLiteral() { + private ConstantNode parseLiteral() { return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole(); } @@ -744,7 +755,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; + } } @@ -826,8 +846,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/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index e993a20e..eb7e2793 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -103,6 +103,7 @@ public class AddNode extends Node { static Node phiCon(Node op, boolean rotate) { Node lhs = op.in(1); Node rhs = op.in(2); + if( rhs._type==TypeInteger.TOP ) return null; // LHS is either a Phi of constants, or another op with Phi of constants PhiNode lphi = pcon(lhs,op); if( rotate && lphi==null && lhs.nIns() > 2 ) { 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..c690a83c --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -0,0 +1,96 @@ +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 + *

+ * CFG nodes have a immediate dominator depth (idepth) and a loop nesting + * depth(loop_depth). + *

+ * idepth is computed lazily upon first request, and is valid even in the + * Parser, and is used by peepholes during parsing and afterward. + *

+ * loop_depth is computed after optimization as part of scheduling. + * + */ +public abstract class CFGNode extends Node { + + public CFGNode(Node... nodes) { super(nodes); } + + @Override public boolean isCFG() { return true; } + + public CFGNode cfg(int idx) { return (CFGNode)in(idx); } + + // Block head is Start, Region, CProj, but not e.g. If, Return, Stop + public boolean blockHead() { return false; } + + // Should be exactly 1 tail from a block head + public CFGNode blockTail() { + assert blockHead(); + for( Node n : _outputs ) + if( n instanceof CFGNode cfg ) + return cfg; + return null; + } + + // ------------------------------------------------------------------------ + /** + * Immediate dominator tree depth, used to approximate a real IDOM during + * parsing where we do not have the whole program, and also peepholes + * change the CFG incrementally. + *

+ * See {@link ...} + */ + public char _idepth; + public int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(idom().idepth()+1); } + // Zero depth means uncached. Check before narrowing so overflow cannot wrap. + final int cacheIDepth(int depth) { + assert 0 <= depth && depth <= Character.MAX_VALUE : "Dominator depth exceeds 65535"; + return _idepth = (char)depth; + } + + + // Return the immediate dominator of this Node and compute dom tree depth. + public CFGNode idom(Node dep) { return cfg(0); } + public final CFGNode idom() { return idom(null); } + + // Return the LCA of two idoms + public CFGNode domLCA(CFGNode rhs, Node dep) { + if( rhs==null ) return this; + CFGNode lhs = this; + while( lhs != rhs ) { + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); + if( comp >= 0 ) lhs = (dep==null ? lhs : (CFGNode)lhs.addDep(dep)).idom(); + if( comp <= 0 ) rhs = (dep==null ? rhs : (CFGNode)rhs.addDep(dep)).idom(); + } + return lhs; + } + + // Loop nesting depth + public int _loopDepth; + public int loopDepth() { return _loopDepth==0 ? (_loopDepth = cfg(0).loopDepth()) : _loopDepth; } + + // ------------------------------------------------------------------------ + // Support routines for Global Code Motion + + // Tik-tok recursion pattern. This method is final, and every caller does + // this work. + public final void walkUnreach( BitSet visit, HashSet 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 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..ff5d1a76 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/CProjNode.java @@ -0,0 +1,62 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.print.ExprPrinter; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; +import com.seaofnodes.simple.type.TypeTuple; + +public class CProjNode extends CFGNode { + + // Which slice of the incoming multipart value + public final int _idx; + + // Debugging label + public final String _label; + + public CProjNode(Node ctrl, int idx, String label) { + super(ctrl); + _idx = idx; + _label = label; + } + + @Override public String label() { return _label; } + + @Override protected ExprPrinter _print1(ExprPrinter p) { return p.p(_label); } + + @Override public boolean isMultiTail() { return in(0).isMultiHead(); } + @Override public boolean blockHead() { return true; } + + public CFGNode ctrl() { return cfg(0); } + + @Override + public Type compute() { + Type t = ctrl()._type; + return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; + } + + @Override + public Node idealize() { + if ( ctrl() instanceof IfNode iff ) { + if ( iff._type instanceof TypeTuple tt && tt._types[1 - _idx] == Type.XCONTROL ) + return iff.in(0); // We become our input control + + // Flip a negating if-test, to remove the not + if( iff.pred().addDep(this) instanceof NotNode not ) + return new CProjNode(new IfNode(iff.ctrl(),not.in(1)).peephole(),1-_idx,_idx==0 ? "False" : "True"); + } + return null; + } + + @Override + public Node getBlockStart() { + return ctrl() instanceof IfNode ? this : ctrl().getBlockStart(); + } + @Override + boolean eq( Node n ) { return _idx == ((CProjNode)n)._idx; } + + @Override + int hash() { return _idx; } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/CastNode.java b/src/main/java/com/seaofnodes/simple/node/CastNode.java index c1faf210..9ade5a50 100644 --- a/src/main/java/com/seaofnodes/simple/node/CastNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CastNode.java @@ -20,6 +20,7 @@ public class CastNode extends Node { @Override public String label() { return "("+_t.str()+")"; } + @Override protected ExprPrinter _print1(ExprPrinter p) { return p.p(label()).n(in(1)); } diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 426736ed..9ecd1152 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -38,6 +38,7 @@ public class ConstantNode extends Node { } @Override public boolean isMultiTail() { return true; } + // The special forever-zero is pinned, all others can sink @Override public Type compute() { return _con; } diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 45f695a5..70340f7f 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -5,8 +5,10 @@ import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeTuple; +import java.util.BitSet; +import java.util.HashSet; -public class IfNode extends MultiNode { +public class IfNode extends CFGNode implements MultiNode { public IfNode(Node ctrl, Node pred) { super(ctrl, pred); @@ -18,7 +20,6 @@ public class IfNode extends MultiNode { @Override protected String format() { return "if( %1 )"; } - @Override public boolean isCFG() { return true; } @Override public boolean isMultiHead() { return true; } public Node ctrl() { return in(0); } @@ -48,11 +49,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 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 b2ee6939..277644f5 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -5,7 +5,6 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.Field; /** @@ -43,9 +42,7 @@ public class LoadNode extends MemOpNode { return false; } - @Override - public String label() { return "Load"; } - + @Override public String label() { return _name; } @Override protected ExprPrinter _print1(ExprPrinter p) { return p.p(".").p(_name); } @@ -65,7 +62,7 @@ public class LoadNode extends MemOpNode { // Simple Load-after-Store on same address. if( mem() instanceof StoreNode st && ptr() == st.ptr() && _alias==st._alias ) { // Must check same object - assert Utils.eq(_name,st._name); // Equiv class aliasing is perfect + assert _name.equals(st._name); // Equiv class aliasing is perfect return st.val(); } @@ -81,9 +78,13 @@ public class LoadNode extends MemOpNode { if( profit(memphi,2) || // Else must not be a loop to count profit on LHS. (!(memphi.region() instanceof LoopNode) && profit(memphi,1)) ) { - Node ld1 = new LoadNode(_name,_alias,_declaredType,memphi.in(1),ptr()).peephole(); - Node ld2 = new LoadNode(_name,_alias,_declaredType,memphi.in(2),ptr()).peephole(); - return new PhiNode(_name,_type,memphi.region(),ld1,ld2); + if( ptr() instanceof NewNode || !(ptr() instanceof CastNode) ) { + if( !(ptr() instanceof NewNode) ) throw Utils.TODO(); // Validate + + Node ld1 = new LoadNode(_name,_alias,_declaredType,memphi.in(1),ptr()).peephole(); + Node ld2 = new LoadNode(_name,_alias,_declaredType,memphi.in(2),ptr()).peephole(); + return new PhiNode(_name,_type,memphi.region(),ld1,ld2); + } } } diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java index a0ba973e..a0e988dd 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,54 @@ 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!=0 ? _idepth : cacheIDepth(entry().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 : cacheIDepth(entry().idepth()+1); } + // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) + @Override public CFGNode idom(Node dep) { return entry(); } + + @Override public int loopDepth() { + if( _loopDepth!=0 ) return _loopDepth; // Was already set + _loopDepth = entry()._loopDepth+1; // Entry depth plus one + // One-time tag loop exits + for( CFGNode idom = back(); idom!=this; idom = idom.idom() ) { + // Walk idom in loop, setting depth + idom._loopDepth = _loopDepth; + // Loop exit hits the CProj before the If, instead of jumping from + // Region directly to If. + if( idom instanceof CProjNode proj ) { + assert proj.in(0) instanceof IfNode; // Loop exit test + // Find the loop exit CProj, and set loop_depth + for( Node use : proj.in(0)._outputs ) + if( use instanceof CProjNode proj2 && proj2 != idom ) + proj2._loopDepth = _loopDepth-1; + } + } + return _loopDepth; + } + + // If this is an unreachable loop, it may not have an exit. If it does not + // (i.e., infinite loop), force an exit to make it reachable. + public void forceExit( StopNode stop ) { + // Walk the backedge, then immediate dominator tree util we hit this + // Loop again. If we ever hit a CProj from an If (as opposed to + // directly on the If) we found our exit. + CFGNode x = back(); + while( x != this ) { + if( x instanceof CProjNode exit && exit.in(0) instanceof IfNode iff ) { + Node other = iff.cproj(1-exit._idx); + if( !(other.out(0) instanceof LoopNode loop) || loop.entry()==exit ) + return; // Found an exit, not an infinite loop + } + 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/MultiNode.java b/src/main/java/com/seaofnodes/simple/node/MultiNode.java index 2743bd19..ac9c0045 100644 --- a/src/main/java/com/seaofnodes/simple/node/MultiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MultiNode.java @@ -1,14 +1,20 @@ 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; } + + // Find a projection by index + default CProjNode cproj( int idx ) { + for( Node out : outs() ) + if( out instanceof CProjNode 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..7e42ccf9 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/NeverNode.java @@ -0,0 +1,22 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.print.ExprPrinter; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeTuple; + + +// "Never true" for infinite loop exits +public class NeverNode extends IfNode { + public NeverNode(Node ctrl) { super(ctrl,Parser.ZERO); } + + @Override public String label() { return "Never"; } + + @Override protected ExprPrinter _print1(ExprPrinter p) { return p.p("Never"); } + + @Override public Type compute() { return TypeTuple.IF_BOTH; } + + @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 857920bc..74ba5184 100644 --- a/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -22,6 +22,7 @@ public class NewNode extends Node { return p.p("new ").p(_ptr._obj.str()); } + @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 999e38fd..2c8596fa 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -17,7 +17,7 @@ import java.util.function.Function; * The Node class provides common functionality used by all subtypes. * Subtypes of Node specialize by overriding methods. */ -public abstract class Node extends BaseNode implements Cloneable { +public abstract class Node extends BaseNode implements OutNode, Cloneable { /** * Inputs to the node. These are use-def references to Nodes. @@ -83,6 +83,7 @@ public abstract class Node extends BaseNode implements Cloneable { */ public Node in(int i) { return _inputs.get(i); } public Node out(int i) { return _outputs.get(i); } + @Override public ArrayList outs() { return _outputs; } public int nIns() { return _inputs.size(); } @@ -90,7 +91,7 @@ public abstract class Node extends BaseNode implements Cloneable { public boolean isUnused() { return nOuts() == 0; } - public boolean isMem() { return false; } + public CFGNode cfg0() { return (CFGNode)in(0); } /** * Change a def into a Node. Keeps the edges correct, by removing @@ -117,11 +118,11 @@ public abstract class Node extends BaseNode implements Cloneable { // the new_def might get killed if the old node kills it recursively. if( new_def != null ) new_def.addUse(this); + // Set the new_def over the old (killed) edge + _inputs.set(idx,new_def); if( old_def != null && // If the old def exists, remove a def->use edge old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def - // Set the new_def over the old (killed) edge - _inputs.set(idx,new_def); moveDepsToWorklist(); // Return self for easy flow-coding return new_def; @@ -149,7 +150,7 @@ public abstract class Node extends BaseNode implements Cloneable { * @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); @@ -269,8 +270,8 @@ public abstract class Node extends BaseNode implements Cloneable { 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 ) { @@ -484,6 +485,17 @@ public abstract class Node extends BaseNode implements Cloneable { // Subclasses add extra hash info (such as ConstantNodes constant) int hash() { return 0; } + // ------------------------------------------------------------------------ + // + + /** Is this Node control-flow-graph related */ + + /** Is this Node Memory related */ + public boolean isMem() { return false; } + + /** Return block start from a isCFG() */ + public Node getBlockStart() { return null; } + // ------------------------------------------------------------------------ // Peephole utilities @@ -512,38 +524,6 @@ public abstract class Node extends BaseNode implements Cloneable { return true; } - /** - * Immediate dominator tree depth, used to approximate a real IDOM depth - * during parsing where we do not have the whole program, and also - * peepholes change the CFG incrementally. - *

- * See {@link ...} - */ - public char _idepth; // IDOM depth approx; Zero is unset; non-zero is cached legit - - // Find the lowest common ancestor in the current dominator tree. - Node domLCA(Node rhs) { - if( rhs==null ) return this; - Node lhs = this; - while( lhs != rhs ) { - if( lhs==null || rhs==null ) return null; - int comp = lhs.idepth() - rhs.idepth(); - if( comp >= 0 ) lhs = lhs.idom(); - if( comp <= 0 ) rhs = rhs.idom(); - } - return lhs; - } - - int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(idom().idepth()+1); } - // Zero depth means uncached. Check before narrowing so overflow cannot wrap. - final int cacheIDepth(int depth) { - assert 0 <= depth && depth <= Character.MAX_VALUE : "Dominator depth exceeds 65535"; - return _idepth = (char)depth; - } - - // Return the immediate dominator of this Node. - Node idom() { return in(0); } - // Make a shallow copy (same class) of this Node, with given inputs and // empty outputs and a new Node ID. The original inputs are ignored. // Does not need to be implemented in isCFG() nodes. diff --git a/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 outs(); +} diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 6995cc2f..8dfa04cf 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -32,10 +32,9 @@ public class PhiNode extends Node { return p.unchar(',').close(); } - 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 Type compute() { @@ -83,11 +82,11 @@ public class PhiNode extends Node { if( in(2)._type == in(2)._type.makeInit() ) nullx = 2; if( nullx != -1 ) { Node val = in(3-nullx); - if( region().idom() instanceof IfNode iff && iff.pred().addDep(this)==val ) { + if( region().idom(this) 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); - while( idom.in(0) != iff ) idom = idom.idom(); - if( idom instanceof ProjNode proj && proj._idx==1 ) + CFGNode idom = (CFGNode)region().in(nullx); + while( idom.nIns() > 0 && idom.in(0) != iff ) idom = idom.idom(); + 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 a2632110..e82c69b3 100644 --- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -15,7 +15,7 @@ public class ProjNode extends Node { // Debugging label public final String _label; - public ProjNode(MultiNode ctrl, int idx, String label) { + public ProjNode(Node ctrl, int idx, String label) { super(ctrl); _idx = idx; _label = label; @@ -27,30 +27,16 @@ public class ProjNode extends Node { @Override protected ExprPrinter _print1(ExprPrinter p) { return p.p(_label); } - @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; } @Override public boolean isMultiTail() { return in(0).isMultiHead(); } @Override public boolean isMem() { return _type instanceof TypeMem; } - public MultiNode ctrl() { return (MultiNode)in(0); } - @Override public Type compute() { Type t = in(0)._type; return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; } - @Override - public Node idealize() { - 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 8b52494a..cdfd10ad 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -3,13 +3,15 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; - import java.util.ArrayList; import java.util.Arrays; +import java.util.BitSet; +import java.util.HashSet; -public class RegionNode extends Node { +public class RegionNode extends CFGNode { public RegionNode(Node... nodes) { super(nodes); } @@ -20,8 +22,8 @@ public class RegionNode extends Node { return p.p(label()).p(_nid); } - @Override public boolean isCFG() { return true; } @Override public boolean isMultiHead() { return true; } + @Override public boolean blockHead() { return true; } @Override public Type compute() { @@ -57,7 +59,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,23 +91,30 @@ 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 depth=0; for( Node n : _inputs ) if( n!=null ) - depth = Math.max(depth,n.idepth()+1); + depth = Math.max(depth,((CFGNode)n).idepth()+1); return cacheIDepth(depth); } - @Override Node idom() { - Node lca = null; + @Override public CFGNode idom(Node dep) { + CFGNode lca = null; // Recompute from predecessors: CFG edits can change the dominator. for( int i=1; i unreach ) { + for( int i=1; i1 && in(nIns()-1) == null; @@ -115,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 ef4ddb3a..161cc7d6 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -6,10 +6,11 @@ import com.seaofnodes.simple.type.*; /** Keeps all preceding memory effects and the return value alive: {ctrl, $mem, value}. */ -public class ReturnNode extends Node { +public class ReturnNode extends CFGNode { public ReturnNode(Node ctrl, Node data, ScopeNode scope) { - super(ctrl, scope.lookup("$mem"), data); + // A synthetic never-taken loop exit has no source scope. + super(ctrl, scope == null ? null : scope.lookup("$mem"), data); } public Node ctrl() { return in(0); } @@ -26,8 +27,6 @@ public class ReturnNode extends Node { return p.p(";"); } - @Override public boolean isCFG() { return true; } - @Override public Type compute() { // Return exposes the complete memory state. @@ -40,4 +39,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 3404f111..a5d4923f 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -3,10 +3,13 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.*; +import java.util.BitSet; +import java.util.HashSet; -/** The entry tuple: control, initial whole-memory state, and argument. */ -public class StartNode extends MultiNode { - final TypeTuple _args; +/** Start supplies control, whole memory, and the argument, in that order. */ +public class StartNode extends CFGNode implements MultiNode { + + private final TypeTuple _args; public StartNode(Type[] args) { super(); @@ -20,8 +23,8 @@ public class StartNode extends MultiNode { return p.p(label()); } - @Override public boolean isCFG() { return true; } @Override public boolean isMultiHead() { return true; } + @Override public boolean blockHead() { return true; } @Override public TypeTuple compute() { return _args; } @@ -30,6 +33,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(Node dep) { return null; } + + @Override void _walkUnreach( BitSet visit, HashSet unreach ) { } + + @Override public int loopDepth() { return (_loopDepth=1); } + + @Override public Node getBlockStart() { return this; } } diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java index 4b4e9615..202afbd2 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -6,9 +6,10 @@ import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.GlobalCodeMotion; -public class StopNode extends Node { +public class StopNode extends CFGNode { public final String _src; @@ -31,7 +32,7 @@ public class StopNode extends Node { return p.p("]"); } - @Override public boolean isCFG() { return true; } + @Override public boolean blockHead() { return true; } // If a single Return, return it. // Otherwise, null because ambiguous. @@ -54,13 +55,23 @@ 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 cacheIDepth(d); + } + @Override public CFGNode idom(Node dep) { return null; } + + @Override public int loopDepth() { return (_loopDepth=1); } public Node addReturn(Node node) { return addDef(node); } - public StopNode iterate() { return IterPeeps.iterate(this).typeCheck(); } + public StopNode iterate() { return IterPeeps.iterate(this).typeCheck().GCM(); } public StopNode typeCheck() { var obs = Parser.PARSER == null ? null : Parser.PARSER._obs; String err = walk(n -> { @@ -72,4 +83,13 @@ public class StopNode extends Node { if( obs != null ) obs.phase("TypeCheck"); return this; } + StopNode GCM() { + // Break infinite loops, forcing a Never-branch to exit + GlobalCodeMotion.fixLoops(this); + + GlobalCodeMotion.buildCFG(this); + return this; + } + + @Override public Node getBlockStart() { 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 6fa87a07..1589abe7 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; @@ -27,6 +28,7 @@ public class SubNode extends Node { if (i0.isConstant() && i1.isConstant()) return TypeInteger.constant(i0.value()-i1.value()); } + return TypeInteger.BOT; } 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..056dfba1 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java @@ -0,0 +1,14 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.print.ExprPrinter; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.Type; + +public class XCtrlNode extends CFGNode { + public XCtrlNode( ) { super(Parser.START); } + @Override public String label() { return "Xctrl"; } + @Override protected ExprPrinter _print1(ExprPrinter p) { return p.p("Xctrl"); } + @Override public Type compute() { return Type.XCONTROL; } + @Override public Node idealize() { return null; } +} diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index 92d970d8..e65963db 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -6,13 +6,13 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.type.TypeMem; -/** Chapter 10's view of the IR; browser, transport and layout are shared. */ +/** Chapter 12's view of the IR; browser, transport and layout are shared. */ public class SimpleGraphAdapter extends GraphAdapter { @Override protected String[] edgeNames(Node n) { return n instanceof ScopeNode scope && n.nIns()!=0 ? scope.reverseNames() : null; } - @Override protected int projectionIndex(Node n) { return n instanceof ProjNode p ? p._idx : -1; } + @Override protected int projectionIndex(Node n) { return n instanceof ProjNode p ? p._idx : n instanceof CProjNode p ? p._idx : -1; } @Override protected Kind kind(Node n) { if( n instanceof StopNode ) return Kind.STOP; @@ -25,9 +25,9 @@ public class SimpleGraphAdapter extends GraphAdapter { } @Override protected Role role(Node n, int i) { - if( n instanceof ScopeNode || n instanceof ConstantNode ) return Role.ASSOC; + if( n instanceof ScopeNode || n instanceof ConstantNode || n instanceof XCtrlNode ) return Role.ASSOC; if( n instanceof PhiNode ) return i == 0 ? Role.ASSOC : isMem(n) ? Role.MEM : Role.DATA; - if( n instanceof ProjNode ) return n.isCFG() ? Role.CTRL : isMem(n) ? Role.MEM : Role.DATA; + if( n instanceof ProjNode || n instanceof CProjNode ) return n.isCFG() ? Role.CTRL : isMem(n) ? Role.MEM : Role.DATA; if( n instanceof RegionNode && i == 0 ) return Role.ASSOC; if( i == 0 || n instanceof RegionNode || n instanceof StopNode ) return Role.CTRL; if( i == 1 && (n instanceof MemOpNode || n instanceof ReturnNode) ) return Role.MEM; diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index 5c852f94..3aabd79f 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.io.IOException; -/** Chapter 12's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 13's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture { private Parser _parser; private Node _ret; diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index 0aa019a7..783f3f60 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -37,12 +37,11 @@ public class TypeTuple extends Type { return make(ts); } - @Override - public StringBuilder print(StringBuilder sb) { - sb.append("["); + @Override public StringBuilder print(StringBuilder sb) { + sb.append("[ "); for( Type t : _types ) - t.print(sb).append(","); - sb.setLength(sb.length()-1); + t.print(sb).append(", "); + sb.setLength(sb.length()-2); sb.append("]"); return sb; } @@ -58,8 +57,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}); -- cgit v1.2.3