summaryrefslogtreecommitdiff
path: root/chapter18/src/main
diff options
context:
space:
mode:
authorCliff Click <cliffc@acm.org>2024-12-28 16:39:00 -0800
committerCliff Click <cliffc@acm.org>2025-01-15 15:07:30 -0800
commitc2cec7cb7fef6df603dd10180de4d0bb715ad47e (patch)
tree67dc5c1751034ddb2b15f338ffd75fd9dac74042 /chapter18/src/main
parentb80abea4fda5580d5070a4ac6d7763552634c32f (diff)
downloadSimple-c2cec7cb7fef6df603dd10180de4d0bb715ad47e.tar.gz
Simple-c2cec7cb7fef6df603dd10180de4d0bb715ad47e.zip
New evaluator, more Compiler Driver cleanup
More compiler driver cleanup: Stop only has Return inputs, never an expr. Drop extra lexical scope. Linker table moves to CodeGen. Replace evaluator with a simpler design; I was unable to get the current design to work with the other changes. Updates to old eval; proper idoms; forced type checks; extensions for Fun, Return, Call, CallEnd. Accessor find next control to execute. Accessor for deciding when its ok to optimize a Function/Return, Call/CallEnd, Stop, ScopeMin (merge) Add local scheduling pass. IRPrinter uses SB instead of StringBuilder Spelling SubF comment
Diffstat (limited to 'chapter18/src/main')
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java35
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java4
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java62
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java1
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/ListScheduler.java110
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/Parser.java104
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java14
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java6
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/node/ConstantNode.java9
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/node/CtrlNode.java14
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java36
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/node/IfNode.java3
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java18
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/node/Node.java5
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/node/ParmNode.java4
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java10
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java12
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java42
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java8
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/node/StartNode.java14
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/node/StopNode.java14
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/node/SubFNode.java2
-rw-r--r--chapter18/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java4
23 files changed, 366 insertions, 165 deletions
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java b/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java
index 184b6f9c..79d817f8 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java
@@ -1,14 +1,13 @@
package com.seaofnodes.simple;
-import com.seaofnodes.simple.Parser;
import com.seaofnodes.simple.node.*;
import com.seaofnodes.simple.type.*;
-import java.util.*;
+import java.util.HashMap;
public class CodeGen {
public enum Phase {
- Parse, Opto, TypeCheck, Schedule, RegAlloc;
+ Parse, Opto, TypeCheck, Schedule, LocalSched, RegAlloc;
}
public Phase _phase;
@@ -20,6 +19,11 @@ public class CodeGen {
public StartNode _start;
public StopNode _stop ;
+
+ // "Linker" mapping from constant TypeFunPtrs to heads of function
+ public final HashMap<TypeFunPtr,FunNode> _linker = new HashMap<>();
+
+
// Last created CodeGen as a global, for easier debugging prints
public static CodeGen CODE;
@@ -30,6 +34,8 @@ public class CodeGen {
public CodeGen parse(boolean disable) {
assert _phase == null;
_phase = Phase.Parse;
+ _linker.clear();
+
P = new Parser(_src,_arg);
Node._disablePeephole = disable;
_stop = P.parse();
@@ -51,7 +57,7 @@ public class CodeGen {
}
public CodeGen typeCheck() {
- assert _phase == Phase.Opto;
+ assert _phase == Phase.Opto || _phase == Phase.Parse;
_phase = Phase.TypeCheck;
// Type check
@@ -62,8 +68,8 @@ public class CodeGen {
}
- public CodeGen codegen() { return codegen(false); }
- public CodeGen codegen(boolean show) {
+ public CodeGen GCM() { return GCM(false); }
+ public CodeGen GCM( boolean show) {
assert _phase == Phase.TypeCheck;
_phase = Phase.Schedule;
@@ -74,14 +80,23 @@ public class CodeGen {
// TODO:
// loop unroll, peel, RCE, etc
-
GlobalCodeMotion.buildCFG(_start,_stop);
-
- _phase = Phase.RegAlloc;
-
return this;
}
+ public CodeGen localSched() {
+ assert _phase == Phase.Schedule;
+ _phase = Phase.LocalSched;
+ ListScheduler.sched(this);
+ return this;
+ }
+
+
+ // Testing shortcuts
+ Node ctrl() { return _stop.ret().ctrl(); }
+ Node expr() { return _stop.ret().expr(); }
+ String print() { return _stop.print(); }
+
// Debugging helper
@Override public String toString() {
return _stop.p(9999);
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
index 7ce12091..6b0956ca 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
@@ -54,7 +54,7 @@ public abstract class GlobalCodeMotion {
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-
+ // 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 instanceof PhiNode) )
@@ -65,7 +65,7 @@ public abstract class GlobalCodeMotion {
CFGNode early = Parser.START; // Maximally early, lowest idepth
if( n.in(0) instanceof CFGNode cfg ) early = cfg;
for( int i=1; i<n.nIns(); i++ )
- if( n.in(i).cfg0().idepth() > early.idepth() )
+ if( n.in(i)!=null && n.in(i).cfg0().idepth() > early.idepth() )
early = n.in(i).cfg0(); // Latest/deepest input
n.setDef(0,early); // First place this can go
}
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java
index 4f422a25..adf67d8b 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java
@@ -1,7 +1,6 @@
package com.seaofnodes.simple;
import com.seaofnodes.simple.node.*;
-import java.lang.StringBuilder;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;
@@ -11,33 +10,31 @@ public class IRPrinter {
// Print a node on 1 line, columnar aligned, as:
// NNID NNAME DDEF DDEF [[ UUSE UUSE ]] TYPE
// 1234 sssss 1234 1234 1234 1234 1234 1234 tttttt
- public static void printLine( Node n, StringBuilder sb ) {
- sb.append("%4d %-7.7s ".formatted(n._nid,n.label()));
- if( n._inputs==null ) {
- sb.append("DEAD\n");
- return;
- }
+ public static SB printLine( Node n, SB sb ) {
+ sb.p("%4d %-7.7s ".formatted(n._nid,n.label()));
+ if( n._inputs==null )
+ return sb.p("DEAD\n");
for( Node def : n._inputs )
- sb.append(def==null ? "____" : "%4d".formatted(def._nid))
+ sb.p(def==null ? "____" : "%4d".formatted(def._nid))
// Lazy Phi indicator
- .append(n instanceof ScopeMinNode && def instanceof ScopeMinNode ? "^" : " ");
+ .p(n instanceof ScopeMinNode && def instanceof ScopeMinNode ? "^" : " ");
for( int i = n._inputs.size(); i<4; i++ )
- sb.append(" ");
- sb.append(" [[ ");
+ sb.p(" ");
+ sb.p(" [[ ");
for( Node use : n._outputs )
- sb.append(use==null ? "____ " : "%4d ".formatted(use._nid));
+ sb.p(use==null ? "____ " : "%4d ".formatted(use._nid));
int lim = 6 - Math.max(n._inputs.size(),4);
for( int i = n._outputs.size(); i<lim; i++ )
- sb.append(" ");
- sb.append(" ]] ");
- if( n._type!= null ) sb.append(n._type.str());
- sb.append("\n");
+ sb.p(" ");
+ sb.p(" ]] ");
+ if( n._type!= null ) sb.p(n._type.str());
+ return sb.p("\n");
}
- private static StringBuilder nodeId(StringBuilder sb, Node n) {
- sb.append("%%%d".formatted(n._nid));
+ private static SB nodeId(SB sb, Node n) {
+ sb.p("%%%d".formatted(n._nid));
if (n instanceof ProjNode proj) {
- sb.append(".").append(proj._idx);
+ sb.p(".").p(proj._idx);
}
return sb;
}
@@ -58,19 +55,19 @@ public class IRPrinter {
for( int i=bfs._lim; i< bfs._bfs.size(); i++ )
postOrd( bfs._bfs.get(i), null, rpos, visit, bfs._bs);
// Reverse the post-order walk
- StringBuilder sb = new StringBuilder();
+ SB sb = new SB();
boolean gap=false;
for( int i=rpos.size()-1; i>=0; i-- ) {
Node n = rpos.get(i);
if( n instanceof CFGNode || n.isMultiHead() ) {
- if( !gap ) sb.append("\n"); // Blank before multihead
+ if( !gap ) sb.p("\n"); // Blank before multihead
printLine( n, sb ); // Print head
while( --i >= 0 ) {
Node t = rpos.get(i);
if( !t.isMultiTail() ) { i++; break; }
printLine( t, sb );
}
- sb.append("\n"); // Blank after multitail
+ sb.p("\n"); // Blank after multitail
gap = true;
} else {
printLine( n, sb );
@@ -180,7 +177,7 @@ public class IRPrinter {
}
}
// Print by block with least idepth
- StringBuilder sb = new StringBuilder();
+ SB sb = new SB();
Ary<Node> bns = new Ary<>(Node.class);
while( !ds.isEmpty() ) {
CFGNode blk = null;
@@ -193,16 +190,15 @@ public class IRPrinter {
ns.remove(blk);
// Print block header
- sb.append("%-13.13s".formatted(label(blk)+":"));
- sb.append( " ".repeat(4) ).append(" [[ ");
+ sb.p("%-13.13s".formatted(label(blk)+":"));
+ sb.p( " ".repeat(4) ).p(" [[ ");
if( blk instanceof StartNode ) ;
else if( blk instanceof RegionNode || blk instanceof StopNode )
for( int i=(blk instanceof StopNode ? 3 : 1); i<blk.nIns(); i++ )
label(sb,blk.cfg(i));
else
label(sb,blk.cfg(0));
- sb.append(" ]] \n");
- sb.append(d);
+ sb.p(" ]] \n");
printLine(blk,sb);
// Collect block contents that are in the depth limit
@@ -234,20 +230,21 @@ public class IRPrinter {
}
}
}
- sb.append("\n");
+ sb.p("\n");
}
return sb.toString();
}
private static void _walk( HashMap<Integer,Integer> ds, ArrayList<Node> ns, Node node, int d ) {
Integer nd = ds.get(node._nid);
- if( nd!=null && d >= nd ) return; // Been there, done that
+ if( nd!=null && d <= nd ) return; // Been there, done that
Integer old = ds.put(node._nid,d) ;
if( old == null )
ns.add(node);
if( d == 0 ) return; // Depth cutoff
for( Node def : node._inputs )
if( def != null &&
+ !(node instanceof LoopNode loop && loop.back()==def) &&
// Don't walk into or out of functions
!(node instanceof CallEndNode && def instanceof ReturnNode) &&
!(node instanceof FunNode && def instanceof CallNode) )
@@ -258,12 +255,11 @@ public class IRPrinter {
if( blk instanceof StartNode ) return "START";
return (blk instanceof LoopNode ? "LOOP" : "L")+blk._nid;
}
- static void label( StringBuilder sb, CFGNode blk ) {
+ static void label( SB sb, CFGNode blk ) {
if( !blk.blockHead() ) blk = blk.cfg(0);
- sb.append( "%-9.9s ".formatted( label( blk ) ) );
+ sb.p( "%-9.9s ".formatted( label( blk ) ) );
}
- static void printLine( Node n, StringBuilder sb, Ary<Node> bns, int i, HashMap<Integer,Integer> ds, ArrayList<Node> ns ) {
- sb.append(ds.get(n._nid));
+ static void printLine( Node n, SB sb, Ary<Node> bns, int i, HashMap<Integer,Integer> ds, ArrayList<Node> ns ) {
printLine( n, sb );
if( i != -1 ) bns.del(i);
ds.remove(n._nid);
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java
index a321b13e..998bd4f0 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java
@@ -182,6 +182,7 @@ public abstract class IterPeeps {
* True if Node is on the WorkList
*/
boolean on( E x ) { return _on.get(x._nid); }
+ boolean isEmpty() { return _len==0; }
/**
* Removes a random Node from the WorkList; null if WorkList is empty
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/ListScheduler.java b/chapter18/src/main/java/com/seaofnodes/simple/ListScheduler.java
new file mode 100644
index 00000000..252a8f8e
--- /dev/null
+++ b/chapter18/src/main/java/com/seaofnodes/simple/ListScheduler.java
@@ -0,0 +1,110 @@
+ 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 ListScheduler {
+
+ private static final BitSet VISIT = new BitSet();
+ private static int[] BCNTS;
+ public static void sched( CodeGen code ) {
+ assert VISIT.isEmpty();
+ BCNTS = new int[Node.UID()];
+ walk(code._start,VISIT);
+ VISIT.clear();
+ }
+
+ // Visit all CFG nodes
+ static void walk( CFGNode cfg, BitSet visit ) {
+ if( visit.get(cfg._nid) ) return;
+ visit.set(cfg._nid);
+ local(cfg);
+ for( Node n : cfg._outputs )
+ if( n instanceof CFGNode c )
+ walk(c,visit);
+ }
+
+ // Local schedule this one CFG
+ static void local( CFGNode bb ) {
+ if( !bb.blockHead() || bb instanceof StopNode ) return;
+ Node[] uses = bb._outputs._es;
+ int ulen = bb._outputs._len;
+
+ // Count block-locals
+ for( int i=0; i<ulen; i++ ) {
+ Node use = uses[i];
+ if( use.in(0)==bb && !(use instanceof PhiNode) ) {
+ // Normal basic block member: in(0)==bb and not a Phi
+ for( Node def : use._inputs )
+ // Has defs from same block? Then block-local inputs
+ if( def != null && def.cfg0()==bb ) // Same block?
+ BCNTS[use._nid]++; // Raise block-local input count
+ }
+ }
+
+ // Nodes are ready if they are not used by other nodes in this block.
+ // Move ready up front. We will never look at remaining nodes, later
+ // nodes are found by looking at users of ready nodes.
+ int ready = 0;
+ for( int i=0; i<ulen; i++ )
+ if( BCNTS[uses[i]._nid]==0 ) // No block-local inputs?
+ uses[ready++] = uses[i]; // Move into ready set
+ assert ready > 0;
+
+ // Classic list scheduler. Behind sched is scheduled. Between sched
+ // and ready have zero counts and are ready to schedule. Ahead of
+ // ready is undefined.
+ //
+ // As nodes are scheduled, the nodes they use decrement their _bcnt. Once
+ // that gets to 0, all the nodes using it are scheduled, so it's ready.
+ int sched = 0;
+ while( sched < ulen ) {
+ assert sched < ready : "Scheduling nodes that are not ready. Probably due to duplicate nodes in the user list.";
+ int pick = best(uses, sched,ready); // Pick best
+ Node best = uses[pick]; // Swap best to head of ready
+ uses[pick] = uses[sched];
+ uses[sched++] = best; // And move it into the scheduled set
+ // Lower ready count of users
+ for( Node use : best._outputs )
+ if( use instanceof ProjNode ) {
+ for( Node useuse : use._outputs )
+ ready = ready(bb,useuse,ready);
+ } else
+ ready = ready(bb, use,ready);
+ }
+ }
+
+ private static int ready(CFGNode bb, Node use, int ready) {
+ if( use != null && use.in(0)==bb && !(use instanceof PhiNode) ) {
+ assert BCNTS[use._nid] >= 1;
+ if( --BCNTS[use._nid] == 0 )
+ bb._outputs._es[ready++] = use; // Became ready, move into ready set
+ }
+ return ready;
+ }
+
+
+ // Pick best between sched and ready.
+ private static int best( Node[] uses, int sched, int ready ) {
+ int pick = sched;
+ int score = score(uses[pick]);
+ for( int i=sched+1; i<ready; i++ ) {
+ int nscore = score(uses[i]);
+ if( nscore > score )
+ { score = nscore; pick = i; }
+ }
+ return pick;
+ }
+
+ // Highest score wins. Max at 1000, min at 10, except specials.
+ private static int score( Node n ) {
+ if( n.isMultiTail() ) return 1001; // Pinned just behind the multi-head
+ if( n instanceof CFGNode ) return n instanceof ReturnNode ? 2 : 1; // Pinned at block exit
+
+ // Nothing special
+ return 500;
+ }
+
+}
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java
index f6bf71a9..ac497fe8 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java
@@ -98,16 +98,12 @@ public class Parser {
// Mapping from a type name to the constructor for a Type.
public final HashMap<String, StructNode> INITS;
- // "Linker" mapping from constant TypeFunPtrs to heads of function
- public static final HashMap<TypeFunPtr,FunNode> LINKER = new HashMap<>();
-
public Parser(String source) { this(source, TypeInteger.BOT); }
public Parser(String source, TypeInteger arg) {
Node.reset();
IterPeeps.reset();
- LINKER.clear();
_lexer = new Lexer(source);
_scope = new ScopeNode();
_continueScope = _breakScope = null;
@@ -154,38 +150,38 @@ public class Parser {
public StopNode parse() { return parse(false); }
public StopNode parse(boolean show) {
_xScopes.push(_scope);
- // Enter a new scope for the initial control and arguments
- _scope.push();
- Node ctrl = new CProjNode(START, 0, ScopeNode.CTRL).peephole();
- Node pmem = new ProjNode(START, 1, ScopeNode.MEM0).peephole();
- Node arg = new ProjNode(START, 2, ScopeNode.ARG0).peephole();
- ScopeMinNode mem = new ScopeMinNode();
- mem.addDef(null);
- mem.addDef(pmem);
- _scope.define(ScopeNode.CTRL, Type.CONTROL , false, ctrl);
- _scope.define(ScopeNode.MEM0, TypeMem.BOT , false, mem );
- _scope.define(ScopeNode.ARG0, TypeInteger.BOT, false, arg );
-
- // Call main
- CallNode main = (CallNode)new CallNode(ctrl,pmem,arg,con(TypeFunPtr.MAIN)).peephole();
- // Call End
- CallEndNode cend = (CallEndNode)new CallEndNode(main).peephole();
- STOP.addDef(new CProjNode(cend,0,ScopeNode.CTRL).peephole());
- STOP.addDef(new ProjNode(cend,1,ScopeNode.MEM0).peephole());
- STOP.addDef(new ProjNode(cend,2,ScopeNode.ARG0).peephole());
+ //// Enter a new scope for the initial control and arguments
+ //_scope.push();
+ //Node ctrl = new CProjNode(START, 0, ScopeNode.CTRL).peephole();
+ //Node pmem = new ProjNode(START, 1, ScopeNode.MEM0).peephole();
+ //Node arg = new ProjNode(START, 2, ScopeNode.ARG0).peephole();
+ //ScopeMinNode mem = new ScopeMinNode();
+ //mem.addDef(null);
+ //mem.addDef(pmem);
+ _scope.define(ScopeNode.CTRL, Type.CONTROL , false, null);
+ _scope.define(ScopeNode.MEM0, TypeMem.BOT , false, null);
+ _scope.define(ScopeNode.ARG0, TypeInteger.BOT, false, null);
+ //
+ //// Call main
+ //CallNode main = (CallNode)new CallNode(ctrl,pmem,arg,con(TypeFunPtr.MAIN)).peephole();
+ //// Call End
+ //CallEndNode cend = (CallEndNode)new CallEndNode(main).peephole();
+ //STOP.addDef(new CProjNode(cend,0,ScopeNode.CTRL).peephole());
+ //STOP.addDef(new ProjNode(cend,1,ScopeNode.MEM0).peephole());
+ //STOP.addDef(new ProjNode(cend,2,ScopeNode.ARG0).peephole());
// Parse whole program, as-if function header "{ int arg -> body }"
ReturnNode ret = parseFunctionBody("main",TypeFunPtr.MAIN,"arg");
- LINKER.put(TypeFunPtr.MAIN,ret.fun());
- main.peephole();
- if( cend.peephole() != null )
- IterPeeps.addAll(cend._outputs);
+ CodeGen.CODE._linker.put(TypeFunPtr.MAIN,ret.fun());
+ //main.peephole();
+ //if( cend.peephole() != null )
+ // IterPeeps.addAll(cend._outputs);
if( !_lexer.isEOF() ) throw _errorSyntax("unexpected");
// Clean up and reset
- _scope.kill();
_xScopes.pop();
+ _scope.kill();
for( StructNode init : INITS.values() )
init.unkeep().kill();
INITS.clear();
@@ -208,6 +204,7 @@ public class Parser {
PhiNode rmem = new PhiNode(ScopeNode.MEM0,TypeMem.BOT,r,null);
PhiNode rrez = new PhiNode(ScopeNode.ARG0,Type.BOTTOM,r,null);
ReturnNode ret = new ReturnNode(r, rmem, rrez, fun);
+ fun.setRet(ret);
assert ret.inProgress();
STOP.addDef(ret);
@@ -217,10 +214,9 @@ public class Parser {
_scope.push();
ctrl(fun); // Scope control from function
// Private mem alias tracking per function
- ScopeMinNode startMem = _scope.mem();
- ScopeMinNode mem = new ScopeMinNode();
+ ScopeMinNode mem = new ScopeMinNode(true);
mem.addDef(null); // Alias#0
- mem.addDef(new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,startMem).peephole()); // All aliases
+ mem.addDef(new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,con(TypeMem.BOT)).peephole()); // All aliases
_scope.mem(mem);
// All args, "as-if" called externally
for( int i=0; i<ids.length; i++ ) {
@@ -236,7 +232,7 @@ public class Parser {
// Last expression is the return
if( ctrl()._type==Type.CONTROL )
- STOP.addReturn(ctrl(), _scope.mem(), last, fun);
+ STOP.addReturn(ctrl(), _scope.mem().merge(), last, fun);
// Function scope ends
_scope.pop();
@@ -581,7 +577,9 @@ public class Parser {
*/
private Node parseReturn() {
var expr = require(parseAsgn(), ";");
- STOP.addReturn(ctrl(), _scope.mem(), expr, _fun);
+ // Need default memory, since it can be lazy, need to force
+ // a non-lazy Phi
+ STOP.addReturn(ctrl(), _scope.mem().merge(), expr, _fun);
ctrl(XCTRL); // Kill control
return expr;
}
@@ -1043,26 +1041,36 @@ public class Parser {
// Check for assign-update, x += e0;
char ch = _lexer.matchOperAssign();
if( ch==0 ) return rvalue;
+
+ // the rvalue is an l-value now; it will be updated
+ Node lhs = rvalue.keep();
if( n._final )
throw error("Cannot reassign final '"+n._name+"'");
+ // RHS of the update
+ Node rhs =
+ (byte)ch == 1 ? con( 1) : // var++
+ (byte)ch == -1 ? con(-1) : // var--
+ parseAsgn(); // var op= rhs
+ // Widen RHS int to a RHS float
+ rhs = widenInt(rhs,n.type());
+ // Complain a RHS float into a LHS int
+ if( !rhs._type.isa(n.type()) )
+ throw error("Type " + rhs._type.str() + " is not of declared type " + n.type().str());
+
Node op = switch(ch) {
- case '+' -> new AddNode(rvalue,null);
- case '-' -> new SubNode(rvalue,null);
- case '*' -> new MulNode(rvalue,null);
- case '/' -> new DivNode(rvalue,null);
- case 1 -> new AddNode(rvalue,con( 1));
- case (char)-1 -> new AddNode(rvalue,con(-1));
- default -> throw Utils.TODO();
+ case 1, (char)-1,
+ '+' -> new AddNode(lhs,rhs);
+ case '-' -> new SubNode(lhs,rhs);
+ case '*' -> new MulNode(lhs,rhs);
+ case '/' -> new DivNode(lhs,rhs);
+ default -> throw Utils.TODO();
};
- // Return pre-value (x+=1) or post-value (x++)
- boolean pre = op.in(2)==null;
- // Parse RHS argument as needed
- if( pre )
- { op.keep().setDef(2,parseAsgn()); op.unkeep(); }
- else rvalue.keep(); // Keep post-value across peeps
- op = zsMask(peep(op),n.type());
+
+ op = zsMask(peep(op.widen()),n.type());
_scope.update(n,op);
- return pre ? op : rvalue.unkeep();
+ // Return pre-value (x+=1) or post-value (x++)
+ lhs.unkeep();
+ return (byte)ch== 1 || (byte)ch== -1 ? lhs : op;
}
ScopeMinNode.Var requireLookupId(String msg) {
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java
index bed4eb17..bacc1935 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java
@@ -28,6 +28,17 @@ public abstract class CFGNode extends Node {
// Block head is Start, Region, CProj, but not e.g. If, Return, Stop
public boolean blockHead() { return false; }
+ // Get the one control following; error to call with more than one e.g. an
+ // IfNode or other multi-way branch.
+ public CFGNode uctrl() {
+ CFGNode c = null;
+ for( Node n : _outputs )
+ if( n instanceof CFGNode cfg )
+ { assert c==null; c = cfg; }
+ return c;
+ }
+
+
// ------------------------------------------------------------------------
/**
* Immediate dominator tree depth, used to approximate a real IDOM during
@@ -90,13 +101,14 @@ public abstract class CFGNode extends Node {
_pre = pre++;
// Pre-walk
for( Node use : _outputs )
- if( use instanceof CFGNode usecfg )
+ if( use instanceof CFGNode usecfg && !(usecfg instanceof XCtrlNode) )
pre = usecfg._bltWalk(pre,use instanceof FunNode fuse ? fuse : fun,stop,post);
// Post-order work: find innermost loop
LoopTree inner = null, ltree;
for( Node use : _outputs ) {
if( !(use instanceof CFGNode usecfg) ) continue;
+ if( usecfg instanceof XCtrlNode ) continue;
// Child visited but not post-visited?
if( !post.get(usecfg._nid) ) {
// Must be a backedge to a LoopNode then
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java
index 0839ad2c..3ec1cd0c 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java
@@ -1,6 +1,6 @@
package com.seaofnodes.simple.node;
-import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.CodeGen;
import com.seaofnodes.simple.Utils;
import com.seaofnodes.simple.type.Type;
import com.seaofnodes.simple.type.TypeFunPtr;
@@ -21,7 +21,7 @@ public class CallNode extends CFGNode {
String fname = null;
Node fptr = fptr();
if( fptr._type instanceof TypeFunPtr tfp && tfp.isConstant() )
- fname = Parser.LINKER.get(tfp)._name;
+ fname = CodeGen.CODE._linker.get(tfp)._name;
if( fname==null ) fptr._print0(sb,visited);
else sb.append(fname);
sb.append("( ");
@@ -62,7 +62,7 @@ public class CallNode extends CFGNode {
for( ; fidxs!=0; fidxs = TypeFunPtr.nextFIDX(fidxs) ) {
int fidx = Long.numberOfTrailingZeros(fidxs);
TypeFunPtr tfp0 = tfp.makeFrom(fidx);
- FunNode fun = Parser.LINKER.get(tfp0);
+ FunNode fun = CodeGen.CODE._linker.get(tfp0);
if( fun!=null && !fun._folding && !linked(fun) )
link(fun);
}
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index 406b20ca..e54797a5 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -19,12 +19,18 @@ import java.util.BitSet;
* The Constant's value is the value stored in it.
*/
public class ConstantNode extends Node {
- Type _con;
+ public final Type _con;
public ConstantNode( Type type ) {
super(Parser.START);
_con = type;
}
+ public static Node make( Type type ) {
+ if( type==Type. CONTROL ) return new CtrlNode();
+ if( type==Type.XCONTROL ) return new XCtrlNode();
+ return new ConstantNode(type);
+ }
+
@Override
public String label() { return "#"+_con; }
@@ -37,6 +43,7 @@ public class ConstantNode extends Node {
}
@Override public boolean isMultiTail() { return true; }
+ @Override public boolean isConst() { return true; }
@Override
public Type compute() { return _con; }
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/CtrlNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CtrlNode.java
new file mode 100644
index 00000000..162417bb
--- /dev/null
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CtrlNode.java
@@ -0,0 +1,14 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.type.Type;
+import java.util.BitSet;
+
+public class CtrlNode extends CFGNode {
+ public CtrlNode() { super(Parser.START); }
+ @Override public String label() { return "Ctrl"; }
+ @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append("Cctrl"); }
+ @Override public boolean isConst() { return true; }
+ @Override public Type compute() { return Type.CONTROL; }
+ @Override public Node idealize() { return null; }
+}
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java
index 9087926e..94d7eff7 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java
@@ -9,24 +9,27 @@ public class FunNode extends RegionNode {
// When set true, this Call/CallEnd/Fun/Return is being trivially inlined
boolean _folding;
- TypeFunPtr _sig; // Initial signature may be missing return
- String _name; // Debug label, optional
+ public final TypeFunPtr _sig; // Initial signature
+ public String _name; // Debug label, optional
+ private ReturnNode _ret; // Return pointer
public FunNode( StartNode start, TypeFunPtr sig, String name ) { super(null,start); _sig=sig; _name=name; }
@Override
public String label() { return _name; }
- ReturnNode ret() {
- ReturnNode ret=null;
+ // Find the one CFG user from Fun. It's not always the Return, but always
+ // the Return *is* a CFG user of Fun.
+ @Override public CFGNode uctrl() {
for( Node n : _outputs )
- if( n instanceof ReturnNode ret0 ) {
- assert ret==null || ret==ret0; // Found more than one return
- ret=ret0;
- }
- return ret;
+ if( n instanceof CFGNode cfg &&
+ (cfg instanceof RegionNode || cfg.cfg0()==this) )
+ return cfg;
+ return null;
}
+ public void setRet(ReturnNode ret) { _ret=ret; }
+ ReturnNode ret() { assert _ret!=null; return _ret; }
@Override
public Type compute() {
@@ -36,12 +39,23 @@ public class FunNode extends RegionNode {
@Override
public Node idealize() {
+ // When can we assume no callers? Or no other callers (except main)?
+ // In a partial compilation, we assume Start gets access to any/all
+ // top-level public structures and recursively what they point to.
+ // This in turn is valid arguments to every callable function.
+ //
+ // In a total compilation, we can start from Start and keep things
+ // more contained.
+
+
// If no default/unknown caller, use the normal RegionNode ideal rules
// to collapse
- if( inProgress() ) return null;
+ if( unknownCallers() ) return null;
return super.idealize();
}
// Always in-progress until we run out of unknown callers
- @Override public boolean inProgress() { return in(1) instanceof StartNode; }
+ public boolean unknownCallers() { return in(1) instanceof StartNode; }
+
+ @Override public boolean inProgress() { return unknownCallers(); }
}
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/IfNode.java
index dcd2d4c7..1e6b2878 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/IfNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -26,6 +26,9 @@ public class IfNode extends CFGNode implements MultiNode {
public Node ctrl() { return in(0); }
public Node pred() { return in(1); }
+ // No one unique control follows
+ @Override public CFGNode uctrl() { return null; }
+
@Override
public Type compute() {
// If the If node is not reachable then neither is any following Proj
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java
index 33420eb9..3f2ae149 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java
@@ -58,17 +58,13 @@ public class LoopNode extends RegionNode {
setDef(2,f);
// Now fold control into the exit
- if( fun!=null )
- throw Utils.TODO();
-
- // If not in a function, look for a last-level merge point;
- // make if not there.
- RegionNode ctrl = stop.ctrl() instanceof RegionNode r ? r : new RegionNode(null,stop.ctrl());
- PhiNode mem = stop.mem () instanceof PhiNode phi && phi.in(0)==ctrl ? phi : new PhiNode("",stop.mem ()._type,ctrl,stop.mem ());
- PhiNode expr = stop.expr() instanceof PhiNode phi && phi.in(0)==ctrl ? phi : new PhiNode("",stop.expr()._type,ctrl,stop.expr());
- if( stop.ctrl()!=ctrl ) stop.setDef(0,ctrl);
- if( stop.mem ()!=mem ) stop.setDef(1,mem );
- if( stop.expr()!=expr ) stop.setDef(2,expr);
+ ReturnNode ret = fun.ret();
+ RegionNode ctrl = ret.ctrl() instanceof RegionNode r ? r : new RegionNode(null,ret.ctrl());
+ PhiNode mem = ret.mem () instanceof PhiNode phi && phi.in(0)==ctrl ? phi : new PhiNode(ctrl,ret.mem ());
+ PhiNode expr = ret.expr() instanceof PhiNode phi && phi.in(0)==ctrl ? phi : new PhiNode(ctrl,ret.expr());
+ if( ret.ctrl()!=ctrl ) ret.setDef(0,ctrl);
+ if( ret.mem ()!=mem ) ret.setDef(1,mem );
+ if( ret.expr()!=expr ) ret.setDef(2,expr);
Node top = new ConstantNode(Type.TOP).peephole();
ctrl.addDef(t );
mem .addDef(top);
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java
index 6369fb01..cc7a1d13 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -114,6 +114,7 @@ public abstract class Node {
public boolean isMultiHead() { return false; }
public boolean isMultiTail() { return false; }
+ public boolean isConst () { return false; }
// ------------------------------------------------------------------------
// Graph Node & Edge manipulation
@@ -337,8 +338,8 @@ public abstract class Node {
Type old = setType(compute());
// Replace constant computations from non-constants with a constant node
- if( !(this instanceof ConstantNode) && !(this instanceof XCtrlNode) && _type.isHighOrConst() )
- return (_type==Type.XCONTROL ? new XCtrlNode() : new ConstantNode(_type)).peepholeOpt();
+ if( _type.isHighOrConst() && !isConst() )
+ return ConstantNode.make(_type).peepholeOpt();
// Global Value Numbering
if( _hash==0 ) {
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ParmNode.java
index 136494b5..f139e4ca 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/ParmNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ParmNode.java
@@ -7,7 +7,7 @@ import java.util.BitSet;
public class ParmNode extends PhiNode {
// Argument indices are mapped one-to-one on CallNode inputs
- final int _idx; // Argument index
+ public final int _idx; // Argument index
public ParmNode(String label, int idx, Type declaredType, Node... inputs) {
super(label,declaredType,inputs);
@@ -18,7 +18,7 @@ public class ParmNode extends PhiNode {
@Override public String glabel() { return _label; }
- FunNode fun() { return (FunNode)in(0); }
+ public FunNode fun() { return (FunNode)in(0); }
@Override
StringBuilder _print1(StringBuilder sb, BitSet visited) {
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 6dd4f57d..91334b6c 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -8,7 +8,7 @@ import java.util.BitSet;
public class PhiNode extends Node {
- final String _label;
+ public final String _label;
// The Phi type we compute must stay within the domain of the Phi.
// Example Int stays Int, Ptr stays Ptr, Control stays Control, Mem stays Mem.
@@ -16,6 +16,14 @@ public class PhiNode extends Node {
public PhiNode(String label, Type declaredType, Node... inputs) { super(inputs); _label = label; assert declaredType!=null; _declaredType = declaredType; }
+ public PhiNode(RegionNode r, Node sample) {
+ super(r);
+ _label = "";
+ _declaredType = sample._type;
+ while( nIns() < r.nIns() )
+ addDef(sample);
+ }
+
@Override public String label() { return "Phi_"+MemOpNode.mlabel(_label); }
@Override public String glabel() { return "&phi;_"+_label; }
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index b305a96e..35563d6e 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -1,8 +1,7 @@
package com.seaofnodes.simple.node;
-import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.CodeGen;
import com.seaofnodes.simple.type.*;
-
import java.util.BitSet;
/**
@@ -16,14 +15,16 @@ import java.util.BitSet;
*/
public class ReturnNode extends CFGNode {
+ public final FunNode _fun;
public ReturnNode(Node ctrl, Node mem, Node data, FunNode fun) {
- super(ctrl, mem, data, fun);
+ super(ctrl, mem, data);
+ _fun = fun;
}
public Node ctrl() { return in(0); }
public Node mem () { return in(1); }
public Node expr() { return in(2); }
- public FunNode fun() { return (FunNode)in(3); }
+ public FunNode fun() { return _fun; }
@Override
public String label() { return "Return"; }
@@ -31,7 +32,6 @@ public class ReturnNode extends CFGNode {
@Override
StringBuilder _print1(StringBuilder sb, BitSet visited) {
sb.append("return ");
- if( expr()==null ) return sb.append("INPROGRESS");
expr()._print0(sb, visited);
return sb.append(";");
}
@@ -45,7 +45,7 @@ public class ReturnNode extends CFGNode {
@Override public Node idealize() { return null; }
public boolean inProgress() {
- return ctrl() instanceof RegionNode r && r.inProgress();
+ return ctrl().getClass() == RegionNode.class && ((RegionNode)ctrl()).inProgress();
}
// Add a return exit to the current parsing function
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java
index f5a33890..f29ed20b 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java
@@ -11,6 +11,8 @@ import static com.seaofnodes.simple.Utils.TODO;
/* */
public class ScopeMinNode extends Node {
+ public final boolean _inProgress;
+
/** The tracked fields are now complex enough to deserve a array-of-structs layout
*/
public static class Var {
@@ -39,8 +41,12 @@ public class ScopeMinNode extends Node {
}
}
- public ScopeMinNode() { _type = TypeMem.BOT; }
+ public ScopeMinNode(boolean inProgress) { _type = TypeMem.BOT; _inProgress = inProgress; }
+
+ // If being used by a Scope, this is "in progress" from the Parser.
+ // Otherwise its a memory merge
+ boolean inProgress() { return _inProgress; }
@Override public String label() { return "ALLMEM"; }
@Override public boolean isMem() { return true; }
@@ -63,6 +69,17 @@ public class ScopeMinNode extends Node {
return sb.append("]");
}
+ // Make a memory merge: no longer a Scope really, tracking memory state but
+ // not related to the parser in any way.
+ public Node merge() {
+ // Force default memory to not be lazy
+ ScopeMinNode merge = new ScopeMinNode(false);
+ for( Node n : _inputs )
+ merge.addDef(n);
+ merge._mem(1,null);
+ return merge.peephole();
+ }
+
@Override public Type compute() { return TypeMem.BOT; }
@@ -127,13 +144,13 @@ public class ScopeMinNode extends Node {
// Fill in the backedge of any inserted Phis
void _endLoopMem( ScopeNode scope, ScopeMinNode back, ScopeMinNode exit ) {
- for( int i=2; i<back.nIns(); i++ ) {
- if( back.in(i) != scope ) {
- PhiNode phi = (PhiNode)in(i);
- assert phi.region()==scope.ctrl() && phi.in(2)==null;
- phi.setDef(2,back.in(i)); // Fill backedge
+ Node exit_def = exit.alias(1);
+ for( int i=1; i<back.nIns(); i++ ) {
+ if( in(i) instanceof PhiNode phi && phi.region()==scope.ctrl() ) {
+ assert phi.in(2)==null;
+ phi.setDef(2,back.in(i)==scope ? phi : back.in(i)); // Fill backedge
}
- if( exit.alias(i) == scope ) // Replace a lazy-phi on the exit path also
+ if( exit_def == scope ) // Replace a lazy-phi on the exit path also
exit.alias(i,in(i));
}
}
@@ -155,16 +172,7 @@ public class ScopeMinNode extends Node {
}
}
- // If being used by a Scope, this is "in progress" from the Parser.
- // Once no more scope users, this is just a memory-merge.
- boolean inProgress() {
- for( Node n : _outputs )
- if( n instanceof ScopeNode scope )
- return true;
- return false;
- }
-
@Override boolean eq( Node n ) {
- return this==n || !inProgress();
+ return this==n || !_inProgress;
}
}
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index 8685e66b..e4a4ddc0 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -3,7 +3,6 @@ package com.seaofnodes.simple.node;
import com.seaofnodes.simple.*;
import com.seaofnodes.simple.type.*;
import java.util.*;
-import static com.seaofnodes.simple.Utils.TODO;
/**
* The Scope node is purely a parser helper - it tracks names to nodes with a
@@ -33,6 +32,7 @@ public class ScopeNode extends ScopeMinNode {
// A new ScopeNode
public ScopeNode() {
+ super(true);
_vars = new Ary<>(Var .class);
_lexSize= new Ary<>(Integer.class);
_inCons = new Ary<>(Boolean.class);
@@ -113,8 +113,8 @@ public class ScopeNode extends ScopeMinNode {
* Create a new variable name in the current scope
*/
public boolean define( String name, Type declaredType, boolean xfinal, Node init ) {
- assert name.charAt(0)!='$' || _lexSize.size()==1; // Later scopes do not define memory
- if( _lexSize._len > 1 )
+ assert _lexSize.isEmpty() || name.charAt(0)!='$' ; // Later scopes do not define memory
+ if( _lexSize._len > 0 )
for( int i=_vars.size()-1; i>=_lexSize.last(); i-- )
if( _vars.get(i)._name.equals(name) )
return false; // Double define
@@ -203,7 +203,7 @@ public class ScopeNode extends ScopeMinNode {
dup.addDef(ctrl()); // Control input is just copied
// Memory input is a shallow copy
- ScopeMinNode memdup = new ScopeMinNode(), mem = mem();
+ ScopeMinNode memdup = new ScopeMinNode(true), mem = mem();
memdup.addDef(null);
memdup.addDef(loop ? this : mem.in(1));
for( int i=2; i<mem.nIns(); i++ )
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/StartNode.java
index ab6e4931..008a910f 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -29,7 +29,19 @@ public class StartNode extends LoopNode implements MultiNode {
@Override public boolean isMultiHead() { return true; }
@Override public boolean blockHead() { return true; }
- @Override public CFGNode cfg0() { return this; }
+ @Override public CFGNode cfg0() { return null; }
+
+ // Get the one control following; error to call with more than one e.g. an
+ // IfNode or other multi-way branch. For Start, its "main"
+ @Override public CFGNode uctrl() {
+ // Find "main", its the start.
+ CFGNode C = null;
+ for( Node use : _outputs )
+ if( use instanceof FunNode fun && fun._sig==TypeFunPtr.MAIN )
+ { assert C==null; C = fun; }
+ return C;
+ }
+
@Override public TypeTuple compute() {
return TypeTuple.make(Type.CONTROL,TypeMem.TOP,_arg);
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/StopNode.java
index 4b91f1eb..fb78f720 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -22,7 +22,6 @@ public class StopNode extends CFGNode {
@Override
StringBuilder _print1(StringBuilder sb, BitSet visited) {
// For the sake of many old tests, and single value prints as "return val"
- if( nIns() == 3 ) return expr()._print0(sb.append("return "),visited).append(";");
if( ret()!=null ) return ret()._print0(sb,visited);
sb.append("Stop[ ");
for( Node ret : _inputs )
@@ -33,14 +32,10 @@ public class StopNode extends CFGNode {
@Override public boolean blockHead() { return true; }
- public CFGNode ctrl() { return (CFGNode)in(0); }
- public Node mem () { return in(1); }
- public Node expr() { return in(2); }
-
// If a single Return, return it.
// Otherwise, null because ambiguous.
public ReturnNode ret() {
- return nIns()==4 && in(3) instanceof ReturnNode ret ? ret : null;
+ return nIns()==1 && in(0) instanceof ReturnNode ret ? ret : null;
}
@Override
@@ -51,7 +46,7 @@ public class StopNode extends CFGNode {
@Override
public Node idealize() {
int len = nIns();
- for( int i=3; i<nIns(); i++ )
+ for( int i=0; i<nIns(); i++ )
if( ((ReturnNode)in(i)).fun()==null )
delDef(i--);
if( len != nIns() ) return this;
@@ -61,9 +56,8 @@ public class StopNode extends CFGNode {
@Override public int idepth() {
if( _idepth!=0 ) return _idepth;
int d=0;
- for( Node n : _inputs )
- if( n instanceof CFGNode cfg )
- d = Math.max(d,cfg.idepth()+1);
+ for( Node ret : _inputs )
+ d = Math.max(d,((ReturnNode)ret).idepth()+1);
return _idepth=d;
}
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/SubFNode.java
index 682930e0..b591718d 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/SubFNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/SubFNode.java
@@ -34,7 +34,7 @@ public class SubFNode extends Node {
Node lhs = in(1);
Type t2 = in(2)._type;
- // Sub of 1.
+ // Sub of 0.
if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==0 )
return lhs;
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java
index 83779dd2..3c6a5df3 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java
@@ -5,9 +5,11 @@ import com.seaofnodes.simple.type.Type;
import java.util.BitSet;
public class XCtrlNode extends CFGNode {
- public XCtrlNode( ) { super(Parser.START); }
+ public XCtrlNode() { super(Parser.START); }
@Override public String label() { return "Xctrl"; }
@Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append("Xctrl"); }
+ @Override public boolean isConst() { return true; }
+ @Override public boolean isMultiTail() { return true; }
@Override public Type compute() { return Type.XCONTROL; }
@Override public Node idealize() { return null; }
}