summaryrefslogtreecommitdiff
path: root/chapter11/src
diff options
context:
space:
mode:
authorCliff Click <cliffc@acm.org>2026-10-03 14:03:48 -0700
committerCliff Click <cliffc@acm.org>2026-10-03 14:03:48 -0700
commit22df891893d30e9906d0b14fc3ae5d8e67d500b2 (patch)
tree2bda142f92febc8b26f1cabd4bb0c46d1864f34b /chapter11/src
parentc3958e34c0de21df52e57e47e4f47ffe6464f138 (diff)
downloadSimple-22df891893d30e9906d0b14fc3ae5d8e67d500b2.tar.gz
Simple-22df891893d30e9906d0b14fc3ae5d8e67d500b2.zip
Chapter renumber, and split ch 17
Renumber chapters 10a, 10b, 11, 12, 13, 14 -> 10, 11, 13, 12, [11,14]. Split ch 17 into a 17a and 17b; shuffle around im/mutable syntax to be consistent, and present it more slowly. THe new immutable syntax is pushed through all later chapters
Diffstat (limited to 'chapter11/src')
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java272
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/IRPrinter.java7
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/IterPeeps.java1
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/Parser.java52
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/Utils.java7
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/CFGNode.java95
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/CProjNode.java62
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/ConstantNode.java1
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/IfNode.java18
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/LoadNode.java4
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/LoopNode.java60
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/MemOpNode.java4
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/MultiNode.java8
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/NeverNode.java20
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/NewNode.java1
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/Node.java61
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/OutNode.java7
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java9
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/ProjNode.java18
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/RegionNode.java29
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/ReturnNode.java9
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/StartNode.java21
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/StopNode.java18
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/StoreNode.java6
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/SubNode.java1
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java14
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java8
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/type/Field.java3
-rw-r--r--chapter11/src/main/java/com/seaofnodes/simple/type/TypeTuple.java3
-rw-r--r--chapter11/src/test/java/com/seaofnodes/simple/Chapter01Test.java2
-rw-r--r--chapter11/src/test/java/com/seaofnodes/simple/Chapter04Test.java2
-rw-r--r--chapter11/src/test/java/com/seaofnodes/simple/Chapter05Test.java14
-rw-r--r--chapter11/src/test/java/com/seaofnodes/simple/Chapter06Test.java16
-rw-r--r--chapter11/src/test/java/com/seaofnodes/simple/Chapter07Test.java48
-rw-r--r--chapter11/src/test/java/com/seaofnodes/simple/Chapter08Test.java24
-rw-r--r--chapter11/src/test/java/com/seaofnodes/simple/Chapter09Test.java33
-rw-r--r--chapter11/src/test/java/com/seaofnodes/simple/Chapter10Test.java30
-rw-r--r--chapter11/src/test/java/com/seaofnodes/simple/Chapter10bTest.java64
-rw-r--r--chapter11/src/test/java/com/seaofnodes/simple/Chapter11Test.java613
-rw-r--r--chapter11/src/test/java/com/seaofnodes/simple/FuzzerWrap.java2
-rw-r--r--chapter11/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java3
-rw-r--r--chapter11/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java14
42 files changed, 288 insertions, 1396 deletions
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter11/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
deleted file mode 100644
index 35b34576..00000000
--- a/chapter11/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
+++ /dev/null
@@ -1,272 +0,0 @@
- package com.seaofnodes.simple;
-
-import com.seaofnodes.simple.IterPeeps.WorkList;
-import com.seaofnodes.simple.node.*;
-import com.seaofnodes.simple.type.*;
-import java.util.*;
-
-public abstract class GlobalCodeMotion {
-
- // Arrange that the existing isCFG() Nodes form a valid CFG. The
- // Node.use(0) is always a block tail (either IfNode or head of the
- // following block). There are no unreachable infinite loops.
- public static void buildCFG( StopNode stop ) {
- fixLoops(stop);
- schedEarly();
- Parser.SCHEDULED = true;
- schedLate(stop);
- }
-
- // ------------------------------------------------------------------------
- // Backwards walk on the CFG only, looking for unreachable code - which has
- // to be an infinite loop. Insert a bogus never-taken exit to Stop, so the
- // loop becomes reachable. Also, set loop nesting depth
- private static void fixLoops(StopNode stop) {
- // Backwards walk from Stop, looking for unreachable code
- BitSet visit = new BitSet();
- HashSet<CFGNode> unreach = new HashSet<>();
- unreach.add(Parser.START);
- for( Node ret : stop._inputs )
- ((ReturnNode)ret).walkUnreach(visit,unreach);
- if( unreach.isEmpty() ) return;
-
- // Forwards walk from unreachable, looking for loops with no exit test.
- visit.clear();
- for( CFGNode cfg : unreach )
- walkInfinite(cfg,visit,stop);
- // Set loop depth on remaining graph
- unreach.clear();
- visit.clear();
- for( Node ret : stop._inputs )
- ((ReturnNode)ret).walkUnreach(visit,unreach);
- assert unreach.isEmpty();
- }
-
-
- // Forwards walk over previously unreachable, looking for loops with no
- // exit test.
- static private void walkInfinite( CFGNode n, BitSet visit, StopNode stop ) {
- if( visit.get(n._nid) ) return; // Been there, done that
- visit.set(n._nid);
- if( n instanceof LoopNode loop )
- loop.forceExit(stop);
- for( Node use : n._outputs )
- if( use instanceof CFGNode cfg )
- walkInfinite(cfg,visit,stop);
- }
-
- // ------------------------------------------------------------------------
- private static void schedEarly() {
- ArrayList<CFGNode> rpo = new ArrayList<>();
- BitSet visit = new BitSet();
- _rpo_cfg(Parser.START, visit, rpo);
- // Reverse Post-Order on CFG
- for( int j=rpo.size()-1; j>=0; j-- ) {
- CFGNode cfg = rpo.get(j);
- cfg.loopDepth();
- for( Node n : cfg._inputs )
- _schedEarly(n,visit);
- // In dead infinite loops, entire code blocks may be unreachable
- // from below. Reach down from the CFG to their Phis so their
- // inputs are scheduled too.
- if( cfg instanceof RegionNode ) {
- int len = cfg.nOuts();
- for( int i=0; i<len; i++ )
- if( cfg.out(i) instanceof PhiNode phi )
- _schedEarly(phi,visit);
- }
- }
- }
-
- // Post-Order of CFG
- private static void _rpo_cfg(Node n, BitSet visit, ArrayList<CFGNode> rpo) {
- if( !(n instanceof CFGNode cfg) || visit.get(cfg._nid) )
- return; // Been there, done that
- visit.set(cfg._nid);
- for( Node use : cfg._outputs )
- _rpo_cfg(use,visit,rpo);
- rpo.add(cfg);
- }
-
- private static void _schedEarly(Node n, BitSet visit) {
- if( n==null || visit.get(n._nid) ) return; // Been there, done that
- visit.set(n._nid);
- // Schedule inputs first, except Phis: following their backedges would
- // enter a data cycle before its control has been scheduled.
- for( Node def : n._inputs )
- if( def!=null && !(def instanceof PhiNode) )
- _schedEarly(def,visit);
- // An existing edge 0 already supplies control (or a Phi/Proj binding).
- if( n.in(0)==null ) {
- // Schedule at deepest input
- CFGNode early = Parser.START; // Maximally early, lowest idepth
- for( int i=1; i<n.nIns(); i++ )
- if( n.in(i)!=null && n.in(i).cfg0().idepth() > early.idepth() )
- early = n.in(i).cfg0(); // Latest/deepest input
- n.setDef(0,early); // First place this can go
- }
- }
-
- // ------------------------------------------------------------------------
- private static void schedLate( StopNode stop) {
- CFGNode[] late = new CFGNode[Node.UID()];
- Node[] ns = new Node[Node.UID()];
- // Record Load NIDs at all their CFG block choices, then check against
- // Store block choices to force a Load above an anti-dependent Store.
- int[] anti = new int[Node.UID()];
- // Breadth-first scheduling
- breadth(stop,ns,late,anti);
-
- // Copy the best placement choice into the control slot
- for( int i=0; i<late.length; i++ )
- if( ns[i] != null && !(ns[i] instanceof ProjNode) )
- ns[i].setDef(0,late[i]);
- }
-
- private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) {
- // Things on the worklist have some (but perhaps not all) uses done.
- WorkList<Node> work = new WorkList<>();
- work.push(stop);
- Node n;
- outer:
- while( (n = work.pop()) != null ) {
- assert late[n._nid]==null; // No double visit
- // These I know the late schedule of, and need to set early for loops
- if( n instanceof CFGNode cfg ) late[n._nid] = cfg.blockHead() ? cfg : cfg.cfg(0);
- else if( n instanceof PhiNode phi ) late[n._nid] = phi.region();
- // These nodes have a fixed late placement at their original control.
- else if( n instanceof ProjNode || n instanceof NewNode || n==Parser.ZERO ) late[n._nid] = n.cfg0();
- else {
-
- // All uses done?
- for( Node use : n._outputs )
- if( use!=null && late[use._nid]==null )
- continue outer; // Nope, await all uses done
-
- // Loads need their memory inputs' uses also done
- if( n instanceof LoadNode ld )
- for( Node memuse : ld.mem()._outputs )
- if( antiUse(ld,memuse) && late[memuse._nid]==null )
- continue outer;
-
- // All uses done, schedule
- _doSchedLate(n,ns,late,anti);
- }
-
- // A use just finished; reconsider its inputs and waiting loads,
- // even when the shared memory input was already scheduled.
- for( Node def : n._inputs ) {
- if( def==null ) continue;
- if( late[def._nid]==null ) work.push(def);
- for( Node out : def._outputs )
- if( out instanceof LoadNode ld && late[ld._nid]==null )
- work.push(ld);
- }
- if( n instanceof LoopNode loop )
- for( Node phi : loop._outputs )
- if( phi instanceof PhiNode && late[phi._nid]==null )
- work.push(phi);
- }
- }
-
- private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) {
- // Walk uses, gathering the LCA (Least Common Ancestor) of uses
- CFGNode early = n.in(0) instanceof CFGNode cfg ? cfg : n.in(0).cfg0();
- assert early != null;
- CFGNode lca = null;
- for( Node use : n._outputs )
- if( use != null )
- lca = use_block(n,use, late).domLCA(lca);
-
- // Loads may need anti-dependencies, raising their LCA
- if( n instanceof LoadNode load )
- lca = find_anti_dep(lca,load,early,late,anti);
-
- // Walk up from the LCA to the early, looking for best place. This is
- // the lowest execution frequency, approximated by least loop depth and
- // deepest control flow.
- CFGNode best = lca;
- lca = lca.idom(); // Already found best for starting LCA
- for( ; lca != early.idom(); lca = lca.idom() )
- if( better(lca,best) )
- best = lca;
- assert !(best instanceof IfNode);
- ns [n._nid] = n;
- late[n._nid] = best;
- }
-
- // Block of use. Normally from late[] schedule, except for Phis, which go
- // to the matching Region input.
- private static CFGNode use_block(Node n, Node use, CFGNode[] late) {
- if( !(use instanceof PhiNode phi) )
- return late[use._nid];
- CFGNode found=null;
- for( int i=1; i<phi.nIns(); i++ )
- if( phi.in(i)==n )
- found = phi.region().cfg(i).domLCA(found); // Can be more than one matching input.
- assert found!=null;
- return found;
- }
-
-
- // Least loop depth first, then largest idepth
- private static boolean better( CFGNode lca, CFGNode best ) {
- return lca.loopDepth() < best.loopDepth() ||
- lca instanceof NeverNode ||
- lca.idepth() > best.idepth() ||
- best instanceof IfNode;
- }
-
- // Only a store or memory Phi covering this alias can constrain a load.
- // MemMerge packages slices without overwriting them.
- private static boolean antiUse(LoadNode load, Node use) {
- return switch( use ) {
- case StoreNode st -> st._alias==load._alias;
- case MemPhiNode phi -> phi._alias==load._alias;
- case BulkMemPhiNode phi -> !phi.isSplit(load._alias);
- default -> false;
- };
- }
-
- private static CFGNode find_anti_dep(CFGNode lca, LoadNode load, CFGNode early, CFGNode[] late, int[] anti) {
- // We could skip final-field loads here.
- // Walk LCA->early, flagging Load's block location choices
- for( CFGNode cfg=lca; early!=null && cfg!=early.idom(); cfg = cfg.idom() )
- anti[cfg._nid] = load._nid;
- // Walk load->mem uses, looking for Stores causing an anti-dep
- for( Node mem : load.mem()._outputs ) {
- if( !antiUse(load,mem) ) continue;
- switch( mem ) {
- case StoreNode st:
- lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti);
- break;
- case PhiNode phi:
- // Repeat anti-dep for matching Phi inputs.
- // No anti-dep edges but may raise the LCA.
- for( int i=1; i<phi.nIns(); i++ )
- if( phi.in(i)==load.mem() )
- lca = anti_dep(load,phi.region().cfg(i),load.mem().cfg0(),lca,null,anti);
- break;
- default: throw Utils.TODO();
- }
- }
- return lca;
- }
-
- //
- private static CFGNode anti_dep( LoadNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st, int[] anti ) {
- // Preserve the full store range for the earlier evaluator scheduler.
- // It places nodes independently of GCM and may hoist this store.
- for( ; stblk != defblk.idom(); stblk = stblk.idom() ) {
- // Store and Load overlap, need anti-dependence
- if( anti[stblk._nid]==load._nid ) {
- lca = stblk.domLCA(lca); // Raise Loads LCA
- if( lca == stblk && st != null && Utils.find(st._inputs,load) == -1 ) // And if something moved,
- st.addDef(load); // Add anti-dep as well
- return lca; // Cap this stores' anti-dep to here
- }
- }
- return lca;
- }
-
-}
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter11/src/main/java/com/seaofnodes/simple/IRPrinter.java
index 7e93e9da..d5ab15fe 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/IRPrinter.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/IRPrinter.java
@@ -8,6 +8,7 @@ public final class IRPrinter extends IRAdapter<Node> {
private static final com.seaofnodes.print.IRPrinter<Node> PRINT =
new com.seaofnodes.print.IRPrinter<>(new IRPrinter());
@Override public String type(Node n) { return n._type==null ? "" : n._type.str(); }
+ @Override public int inputColumns() { return 3; }
@Override public String inputMark(Node n, Node def) { return n instanceof MemMergeNode && def instanceof MemMergeNode ? "^" : " "; }
@Override public Kind kind(Node n) {
if( n instanceof StartNode ) return Kind.START;
@@ -17,15 +18,13 @@ public final class IRPrinter extends IRAdapter<Node> {
if( n instanceof PhiNode ) return Kind.PHI;
if( n instanceof ReturnNode ) return Kind.RETURN;
if( n instanceof ConstantNode ) return Kind.CONSTANT;
- if( n instanceof CProjNode ) return Kind.CPROJ;
- if( n instanceof ProjNode ) return n instanceof CFGNode ? Kind.CPROJ : Kind.PROJ;
- if( n instanceof CFGNode ) return Kind.CTRL;
+ if( n instanceof ProjNode ) return n.isCFG() ? Kind.CPROJ : Kind.PROJ;
+ if( n.isCFG() ) return Kind.CTRL;
if( n instanceof MultiNode ) return Kind.MULTI;
return Kind.DATA;
}
@Override public int index(Node n) {
if( n instanceof ProjNode p ) return p._idx;
- if( n instanceof CProjNode p ) return p._idx;
return n._nid;
}
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter11/src/main/java/com/seaofnodes/simple/IterPeeps.java
index 9d2b913f..7075d526 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/IterPeeps.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/IterPeeps.java
@@ -98,7 +98,6 @@ public abstract class IterPeeps {
if( obs != null ) obs.after(n, x, true);
}
- GlobalCodeMotion.buildCFG(stop);
return stop;
}
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/Parser.java b/chapter11/src/main/java/com/seaofnodes/simple/Parser.java
index fb4dfdf8..3b5f2721 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/Parser.java
@@ -31,18 +31,12 @@ public class Parser {
*/
public static StartNode START;
- public static ConstantNode ZERO;
- public static XCtrlNode XCTRL;
-
public StopNode STOP;
// Field identities are independent of the memory graph and Start's tuple.
private final HashMap<String,Integer> _aliases = new HashMap<>();
private int _alias = 2;
- // Debugger Printing.
- public static boolean SCHEDULED; // True if debug printer can use schedule info
-
// The Lexer. Thin wrapper over a byte[] buffer with a cursor.
private final Lexer _lexer;
@@ -96,14 +90,11 @@ public class Parser {
Node.reset();
IterPeeps.reset();
OBJS.clear();
- SCHEDULED = false;
_lexer = new Lexer(source);
_scope = new ScopeNode();
_continueScope = _breakScope = null;
START = new StartNode(new Type[]{ Type.CONTROL, TypeMem.BOT, arg });
STOP = new StopNode(source);
- ZERO = new ConstantNode(TypeInteger.constant(0)).peephole().keep();
- XCTRL= new XCtrlNode().peephole().keep();
}
public Parser(String source) {
@@ -126,12 +117,10 @@ public class Parser {
_xScopes.push(_scope);
// Enter a new scope for the initial control and arguments
_scope.push();
- _scope.define(ScopeNode.CTRL, Type.CONTROL , new CProjNode(START, 0, ScopeNode.CTRL).peephole());
- _scope.define(ScopeNode.ARG0, TypeInteger.BOT, new ProjNode(START, 2, ScopeNode.ARG0).peephole());
+ _scope.define(ScopeNode.CTRL, Type.CONTROL , new ProjNode(START, 0, ScopeNode.CTRL).peephole());
+ _scope.define(ScopeNode.ARG0, TypeInteger.BOT, new ProjNode(START, 2, ScopeNode.ARG0).peephole());
_scope.define("$mem", TypeMem.BOT, new ProjNode(START, 1, "$mem").peephole());
parseBlock();
- if( ctrl()._type==Type.CONTROL )
- STOP.addReturn(new ReturnNode(ctrl(), new ConstantNode(TypeInteger.constant(0)).peephole(), _scope).peephole());
_scope.pop();
_xScopes.pop();
if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken());
@@ -215,9 +204,9 @@ public class Parser {
require("}");
// Build and install the TypeStruct
TypeStruct ts = TypeStruct.make(typeName, fields);
- OBJS.put(typeName, ts); // Insert the struct name in the collection of all struct names
_aliases.put(typeName,_alias);
_alias += ts._fields.length;
+ OBJS.put(typeName, ts); // Insert the struct name in the collection of all struct names
return parseStatement();
}
@@ -259,8 +248,8 @@ public class Parser {
// IfNode takes current control and predicate
Node ifNode = new IfNode(ctrl(), pred).peephole();
// Setup projection nodes
- Node ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep();
- Node ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole();
+ Node ifT = new ProjNode(ifNode. keep(), 0, "True" ).peephole().keep();
+ Node ifF = new ProjNode(ifNode.unkeep(), 1, "False").peephole();
// Clone the body Scope to create the break/exit Scope which accounts for any
// side effects in the predicate. The break/exit Scope will be the final
@@ -306,7 +295,7 @@ public class Parser {
private ScopeNode jumpTo(ScopeNode toScope) {
ScopeNode cur = _scope.dup();
- ctrl(XCTRL); // Kill current scope
+ ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill current scope
// Prune nested lexical scopes that have depth > than the loop head
// We use _breakScope as a proxy for the loop head scope to obtain the depth
while( cur._scopes.size() > _breakScope._scopes.size() )
@@ -342,8 +331,8 @@ public class Parser {
// IfNode takes current control and predicate
Node ifNode = new IfNode(ctrl(), pred).peephole();
// Setup projection nodes
- Node ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep();
- Node ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole().keep();
+ Node ifT = new ProjNode(ifNode. keep(), 0, "True" ).peephole().keep();
+ Node ifF = new ProjNode(ifNode.unkeep(), 1, "False").peephole().keep();
// In if true branch, the ifT proj node becomes the ctrl
// But first clone the scope and set it as current
int ndefs = _scope.nIns();
@@ -390,7 +379,7 @@ public class Parser {
private Node parseReturn() {
var expr = require(parseExpression(), ";");
Node ret = STOP.addReturn(new ReturnNode(ctrl(), expr, _scope).peephole());
- ctrl(XCTRL); // Kill control
+ ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill control
return ret;
}
@@ -585,7 +574,7 @@ public class Parser {
if( _lexer.isNumber() ) return parseIntegerLiteral();
if( match("(") ) return require(parseExpression(), ")");
if( matchx("true" ) ) return new ConstantNode(TypeInteger.constant(1)).peephole();
- if( matchx("false") ) return ZERO;
+ if( matchx("false") ) return new ConstantNode(TypeInteger.constant(0)).peephole();
if( matchx("null" ) ) return new ConstantNode(TypeMemPtr.NULLPTR).peephole();
if( matchx("new") ) {
String structName = requireId();
@@ -603,11 +592,12 @@ public class Parser {
/**
* Return a NewNode but also generate instructions to initialize it.
*/
- private Node newStruct(TypeStruct obj) {
+ private Node newStruct( TypeStruct obj ) {
Node n = new NewNode(TypeMemPtr.make(obj), ctrl()).peephole().keep();
+ Node initValue = new ConstantNode(TypeInteger.constant(0)).peephole();
int alias = _aliases.get(obj._name);
for( Field field : obj._fields ) {
- store(field._fname,alias,n,ZERO);
+ store(field._fname,alias,n,initValue);
alias++;
}
return n.unkeep();
@@ -619,7 +609,7 @@ public class Parser {
private void store(String name, int alias, Node ptr, Node val) {
Node prior = mem().keep();
- Node st = new StoreNode(name,alias,ctrl(),prior,ptr,val).peephole();
+ Node st = new StoreNode(name,alias,prior,ptr,val).peephole();
mem(new MemMergeNode(prior,alias,st).peephole());
prior.unkeep();
}
@@ -759,16 +749,7 @@ public class Parser {
* Return the next non-white-space character
*/
private void skipWhiteSpace() {
- while( true ) {
- if( isWhiteSpace() ) _position++;
- // Skip // to end of line
- else if( _position+2 < _input.length &&
- _input[_position ] == '/' &&
- _input[_position+1] == '/') {
- _position += 2;
- while( !isEOF() && _input[_position] != '\n' ) _position++;
- } else break;
- }
+ while (isWhiteSpace()) _position++;
}
@@ -850,9 +831,8 @@ public class Parser {
return new String(_input, start, --_position - start);
}
- //
private boolean isPunctuation(char ch) {
- return "=;[]<>()+-/*".indexOf(ch) != -1;
+ return "=;[]<>(){}+-/*!".indexOf(ch) != -1;
}
private String parsePunctuation() {
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/Utils.java b/chapter11/src/main/java/com/seaofnodes/simple/Utils.java
index f3ac25b1..4f2af769 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/Utils.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/Utils.java
@@ -55,4 +55,11 @@ public class Utils {
// Fold a 64bit hash into 32 bits
public static int fold( long x ) { return (int)((x>>32) ^ x); }
+
+ public static boolean eq(String s0, String s1) {
+ if( s0==s1 ) return true;
+ assert s0==s0.intern();
+ assert s1==s1.intern();
+ return false;
+ }
}
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/CFGNode.java
deleted file mode 100644
index ea67d17d..00000000
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/CFGNode.java
+++ /dev/null
@@ -1,95 +0,0 @@
-package com.seaofnodes.simple.node;
-
-import com.seaofnodes.simple.Parser;
-import com.seaofnodes.simple.type.*;
-import com.seaofnodes.simple.Utils;
-
-import java.util.BitSet;
-import java.util.HashSet;
-import java.util.HashMap;
-
-/** Control Flow Graph Nodes
- * <p>
- * CFG nodes have a immediate dominator depth (idepth) and a loop nesting
- * depth(loop_depth).
- * <p>
- * idepth is computed lazily upon first request, and is valid even in the
- * Parser, and is used by peepholes during parsing and afterward.
- * <p>
- * loop_depth is computed after optimization as part of scheduling.
- *
- */
-public abstract class CFGNode extends Node {
-
- public CFGNode(Node... nodes) { super(nodes); }
-
- @Override public boolean isCFG() { return true; }
-
- public CFGNode cfg(int idx) { return (CFGNode)in(idx); }
-
- // Block head is Start, Region, CProj, but not e.g. If, Return, Stop
- public boolean blockHead() { return false; }
-
- // Should be exactly 1 tail from a block head
- public CFGNode blockTail() {
- assert blockHead();
- for( Node n : _outputs )
- if( n instanceof CFGNode cfg )
- return cfg;
- return null;
- }
-
- // ------------------------------------------------------------------------
- /**
- * Immediate dominator tree depth, used to approximate a real IDOM during
- * parsing where we do not have the whole program, and also peepholes
- * change the CFG incrementally.
- * <p>
- * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>}
- */
- public char _idepth;
- public int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(idom().idepth()+1); }
- // Zero depth means uncached. Check before narrowing so overflow cannot wrap.
- final int cacheIDepth(int depth) {
- assert 0 <= depth && depth <= Character.MAX_VALUE : "Dominator depth exceeds 65535";
- return _idepth = (char)depth;
- }
-
-
- // Return the immediate dominator of this Node and compute dom tree depth.
- public CFGNode idom() { return cfg(0); }
-
- // Return the LCA of two idoms
- public CFGNode domLCA(CFGNode rhs) {
- if( rhs==null ) return this;
- CFGNode lhs = this;
- while( lhs != rhs ) {
- if( lhs==null || rhs==null ) return null;
- int comp = lhs.idepth() - rhs.idepth();
- if( comp >= 0 ) lhs = lhs.idom();
- if( comp <= 0 ) rhs = rhs.idom();
- }
- return lhs;
- }
-
- // Loop nesting depth
- public int _loopDepth;
- public int loopDepth() { return _loopDepth==0 ? (_loopDepth = cfg(0).loopDepth()) : _loopDepth; }
-
- // ------------------------------------------------------------------------
- // Support routines for Global Code Motion
-
- // Tik-tok recursion pattern. This method is final, and every caller does
- // this work.
- public final void walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) {
- if( visit.get(_nid) ) return;
- visit.set(_nid);
- _walkUnreach(visit,unreach);
- unreach.remove(this); // Since we reached here... Node was not unreachable
- }
-
- // Tik-tok recursion pattern; not-final; callers override this.
- void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) {
- cfg(0).walkUnreach(visit,unreach);
- }
-}
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/CProjNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/CProjNode.java
deleted file mode 100644
index ff5d1a76..00000000
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/CProjNode.java
+++ /dev/null
@@ -1,62 +0,0 @@
-package com.seaofnodes.simple.node;
-
-import com.seaofnodes.print.ExprPrinter;
-
-import com.seaofnodes.simple.Parser;
-import com.seaofnodes.simple.type.Type;
-import com.seaofnodes.simple.type.TypeMem;
-import com.seaofnodes.simple.type.TypeTuple;
-
-public class CProjNode extends CFGNode {
-
- // Which slice of the incoming multipart value
- public final int _idx;
-
- // Debugging label
- public final String _label;
-
- public CProjNode(Node ctrl, int idx, String label) {
- super(ctrl);
- _idx = idx;
- _label = label;
- }
-
- @Override public String label() { return _label; }
-
- @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p(_label); }
-
- @Override public boolean isMultiTail() { return in(0).isMultiHead(); }
- @Override public boolean blockHead() { return true; }
-
- public CFGNode ctrl() { return cfg(0); }
-
- @Override
- public Type compute() {
- Type t = ctrl()._type;
- return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM;
- }
-
- @Override
- public Node idealize() {
- if ( ctrl() instanceof IfNode iff ) {
- if ( iff._type instanceof TypeTuple tt && tt._types[1 - _idx] == Type.XCONTROL )
- return iff.in(0); // We become our input control
-
- // Flip a negating if-test, to remove the not
- if( iff.pred().addDep(this) instanceof NotNode not )
- return new CProjNode(new IfNode(iff.ctrl(),not.in(1)).peephole(),1-_idx,_idx==0 ? "False" : "True");
- }
- return null;
- }
-
- @Override
- public Node getBlockStart() {
- return ctrl() instanceof IfNode ? this : ctrl().getBlockStart();
- }
- @Override
- boolean eq( Node n ) { return _idx == ((CProjNode)n)._idx; }
-
- @Override
- int hash() { return _idx; }
-
-}
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index 9ecd1152..426736ed 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -38,7 +38,6 @@ public class ConstantNode extends Node {
}
@Override public boolean isMultiTail() { return true; }
- // The special forever-zero is pinned, all others can sink
@Override
public Type compute() { return _con; }
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/IfNode.java
index 70340f7f..45f695a5 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/IfNode.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -5,10 +5,8 @@ import com.seaofnodes.simple.IterPeeps;
import com.seaofnodes.simple.type.Type;
import com.seaofnodes.simple.type.TypeInteger;
import com.seaofnodes.simple.type.TypeTuple;
-import java.util.BitSet;
-import java.util.HashSet;
-public class IfNode extends CFGNode implements MultiNode {
+public class IfNode extends MultiNode {
public IfNode(Node ctrl, Node pred) {
super(ctrl, pred);
@@ -20,6 +18,7 @@ public class IfNode extends CFGNode implements MultiNode {
@Override protected String format() { return "if( %1 )"; }
+ @Override public boolean isCFG() { return true; }
@Override public boolean isMultiHead() { return true; }
public Node ctrl() { return in(0); }
@@ -49,20 +48,11 @@ public class IfNode extends CFGNode implements MultiNode {
// Hunt up the immediate dominator tree. If we find an identical if
// test on either the true or false branch, that side wins.
if( !pred()._type.isHighOrConst() )
- for( CFGNode dom = idom(), prior=this; dom!=null; prior = dom, dom = dom.idom() )
- if( dom.addDep(this) instanceof IfNode iff && iff.pred().addDep(this)==pred() && prior instanceof CProjNode prj ) {
+ for( Node dom = idom(), prior=this; dom!=null; prior = dom, dom = dom.idom() )
+ if( dom.addDep(this) instanceof IfNode iff && iff.pred().addDep(this)==pred() && prior instanceof ProjNode prj ) {
setDef(1,new ConstantNode(TypeInteger.make(true,prj._idx==0?1:0)).peephole());
return this;
}
return null;
}
-
- @Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) {
- for( Node proj : _outputs )
- if( ((CProjNode)proj)._loopDepth == 0 )
- unreach.add((CProjNode)proj);
- super._walkUnreach(visit,unreach);
- }
-
- @Override public Node getBlockStart() { return ctrl().getBlockStart(); }
}
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/LoadNode.java
index 386009b4..9bf36459 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/LoadNode.java
@@ -23,7 +23,7 @@ public class LoadNode extends MemOpNode {
* @param memPtr The ptr to the struct from where we load a field
*/
public LoadNode(String name, int alias, Type glb, Node memSlice, Node memPtr) {
- super(name, alias, null, memSlice, memPtr);
+ super(name, alias, memSlice, memPtr, null);
_declaredType = glb;
}
@@ -67,7 +67,7 @@ public class LoadNode extends MemOpNode {
// Simple Load-after-Store on same address.
if( mem() instanceof StoreNode st &&
ptr() == st.ptr() && _alias==st._alias ) { // Must check same object
- assert _name.equals(st._name); // Equiv class aliasing is perfect
+ assert Utils.eq(_name,st._name); // Equiv class aliasing is perfect
return st.val();
}
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/LoopNode.java
index 45549f1d..a0ba973e 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/LoopNode.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/LoopNode.java
@@ -1,17 +1,15 @@
package com.seaofnodes.simple.node;
-import com.seaofnodes.simple.Parser;
-import com.seaofnodes.simple.Utils;
import com.seaofnodes.simple.type.Type;
-import com.seaofnodes.simple.type.TypeInteger;
+
import java.util.BitSet;
-import java.util.HashSet;
public class LoopNode extends RegionNode {
+
public LoopNode( Node entry ) { super(null,entry,null); }
- public CFGNode entry() { return cfg(1); }
- public CFGNode back () { return cfg(2); }
+ Node entry() { return in(1); }
+ Node back () { return in(2); }
@Override
public String label() { return "Loop"; }
@@ -27,51 +25,7 @@ public class LoopNode extends RegionNode {
return inProgress() ? null : super.idealize();
}
- // Bypass Region idom, same as the default idom() using use in(1) instead of in(0)
- @Override public int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(entry().idepth()+1); }
- // Bypass Region idom, same as the default idom() using use in(1) instead of in(0)
- @Override public CFGNode idom() { return entry(); }
-
- @Override public int loopDepth() {
- if( _loopDepth!=0 ) return _loopDepth; // Was already set
- _loopDepth = entry()._loopDepth+1; // Entry depth plus one
- // One-time tag loop exits
- for( CFGNode idom = back(); idom!=this; idom = idom.idom() ) {
- // Walk idom in loop, setting depth
- idom._loopDepth = _loopDepth;
- // Loop exit hits the CProj before the If, instead of jumping from
- // Region directly to If.
- if( idom instanceof CProjNode proj ) {
- assert proj.in(0) instanceof IfNode; // Loop exit test
- // Find the loop exit CProj, and set loop_depth
- for( Node use : proj.in(0)._outputs )
- if( use instanceof CProjNode proj2 && proj2 != idom )
- proj2._loopDepth = _loopDepth-1;
- }
- }
- return _loopDepth;
- }
-
- // If this is an unreachable loop, it may not have an exit. If it does not
- // (i.e., infinite loop), force an exit to make it reachable.
- public void forceExit( StopNode stop ) {
- // Walk the backedge, then immediate dominator tree util we hit this
- // Loop again. If we ever hit a CProj from an If (as opposed to
- // directly on the If) we found our exit.
- CFGNode x = back();
- while( x != this ) {
- if( x instanceof CProjNode exit )
- return; // Found an exit, not an infinite loop
- x = x.idom();
- }
- // Found a no-exit loop. Insert an exit
- NeverNode iff = new NeverNode(back());
- for( Node use : _outputs )
- if( use instanceof PhiNode phi )
- iff.addDef(use);
- CProjNode t = new CProjNode(iff,0,"True" );
- CProjNode f = new CProjNode(iff,1,"False");
- setDef(2,f);
- stop.addDef(new ReturnNode(t,Parser.ZERO,null));
- }
+ // Bypass Region idom, same as the default idom() using use entry in(1) instead of in(0)
+ @Override int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(entry().idepth()+1); }
+ @Override Node idom() { return entry(); }
}
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
index 5a57a8c8..44304bcb 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
@@ -12,8 +12,8 @@ public abstract class MemOpNode extends Node {
public final String _name;
public final int _alias;
- public MemOpNode(String name, int alias, Node... nodes) {
- super(nodes);
+ public MemOpNode(String name, int alias, Node memSlice, Node memPtr, Node value) {
+ super(null, memSlice, memPtr, value);
_name = name;
_alias = alias;
}
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/MultiNode.java
index 379e140d..2743bd19 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/MultiNode.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/MultiNode.java
@@ -1,10 +1,12 @@
package com.seaofnodes.simple.node;
-public interface MultiNode extends OutNode {
+public abstract class MultiNode extends Node {
+
+ public MultiNode(Node... inputs) { super(inputs); }
// Find a projection by index
- default ProjNode proj( int idx ) {
- for( Node out : outs() )
+ ProjNode proj( int idx ) {
+ for( Node out : _outputs )
if( out instanceof ProjNode prj && prj._idx==idx )
return prj;
return null;
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/NeverNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/NeverNode.java
deleted file mode 100644
index 6eb7fe63..00000000
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/NeverNode.java
+++ /dev/null
@@ -1,20 +0,0 @@
-package com.seaofnodes.simple.node;
-
-import com.seaofnodes.print.ExprPrinter;
-
-import com.seaofnodes.simple.Parser;
-import com.seaofnodes.simple.type.TypeInteger;
-import com.seaofnodes.simple.type.Type;
-
-// "Never true" for infinite loop exits
-public class NeverNode extends IfNode {
- public NeverNode(Node ctrl) { super(ctrl,Parser.ZERO); }
-
- @Override public String label() { return "Never"; }
-
- @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p("Never"); }
-
- @Override public Type compute() { return TypeInteger.BOT; }
-
- @Override public Node idealize() { return null; }
-}
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/NewNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/NewNode.java
index 74ba5184..857920bc 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/NewNode.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/NewNode.java
@@ -22,7 +22,6 @@ public class NewNode extends Node {
return p.p("new ").p(_ptr._obj.str());
}
-
@Override
public Type compute() { return _ptr; }
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java
index 568c23cc..1d8e23f8 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -2,8 +2,9 @@ package com.seaofnodes.simple.node;
import com.seaofnodes.print.BaseNode;
-import com.seaofnodes.simple.IRPrinter;
import com.seaofnodes.simple.Parser;
+
+import com.seaofnodes.simple.IRPrinter;
import com.seaofnodes.simple.IterPeeps;
import com.seaofnodes.simple.Utils;
import com.seaofnodes.simple.type.Type;
@@ -16,7 +17,7 @@ import java.util.function.Function;
* The Node class provides common functionality used by all subtypes.
* Subtypes of Node specialize by overriding methods.
*/
-public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable {
+public abstract class Node extends BaseNode<Node> implements Cloneable {
/**
* Inputs to the node. These are use-def references to Nodes.
@@ -82,7 +83,6 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable
*/
public Node in(int i) { return _inputs.get(i); }
public Node out(int i) { return _outputs.get(i); }
- @Override public ArrayList<Node> outs() { return _outputs; }
public int nIns() { return _inputs.size(); }
@@ -90,7 +90,7 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable
public boolean isUnused() { return nOuts() == 0; }
- public CFGNode cfg0() { return (CFGNode)in(0); }
+ public boolean isMem() { return false; }
/**
* Change a <em>def</em> into a Node. Keeps the edges correct, by removing
@@ -117,11 +117,11 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable
// the new_def might get killed if the old node kills it recursively.
if( new_def != null )
new_def.addUse(this);
- // Set the new_def over the old (killed) edge
- _inputs.set(idx,new_def);
if( old_def != null && // If the old def exists, remove a def->use edge
old_def.delUse(this) ) // If we removed the last use, the old def is now dead
old_def.kill(); // Kill old def
+ // Set the new_def over the old (killed) edge
+ _inputs.set(idx,new_def);
moveDepsToWorklist();
// Return self for easy flow-coding
return new_def;
@@ -149,7 +149,7 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable
* @param new_def the new definition, appended to the end of existing definitions
* @return new_def for flow coding
*/
- public Node addDef(Node new_def) {
+ Node addDef(Node new_def) {
unlock();
// Add use->def edge
_inputs.add(new_def);
@@ -268,8 +268,8 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable
Type old = setType(compute());
// Replace constant computations from non-constants with a constant node
- if( !(this instanceof ConstantNode) && !(this instanceof XCtrlNode) && _type.isHighOrConst() )
- return (_type==Type.XCONTROL ? new XCtrlNode() : new ConstantNode(_type)).peepholeOpt();
+ if( !(this instanceof ConstantNode) && _type.isHighOrConst() )
+ return new ConstantNode(_type).peepholeOpt();
// Global Value Numbering
if( _hash==0 ) {
@@ -484,17 +484,6 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable
int hash() { return 0; }
// ------------------------------------------------------------------------
- //
-
- /** Is this Node control-flow-graph related */
-
- /** Is this Node Memory related */
- public boolean isMem() { return false; }
-
- /** Return block start from a isCFG() */
- public Node getBlockStart() { return null; }
-
- // ------------------------------------------------------------------------
// Peephole utilities
// Swap inputs without letting either input go dead during the swap.
@@ -522,6 +511,38 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable
return true;
}
+ /**
+ * Immediate dominator tree depth, used to approximate a real IDOM depth
+ * during parsing where we do not have the whole program, and also
+ * peepholes change the CFG incrementally.
+ * <p>
+ * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>}
+ */
+ public char _idepth; // IDOM depth approx; Zero is unset; non-zero is cached legit
+
+ // Find the lowest common ancestor in the current dominator tree.
+ Node domLCA(Node rhs) {
+ if( rhs==null ) return this;
+ Node lhs = this;
+ while( lhs != rhs ) {
+ if( lhs==null || rhs==null ) return null;
+ int comp = lhs.idepth() - rhs.idepth();
+ if( comp >= 0 ) lhs = lhs.idom();
+ if( comp <= 0 ) rhs = rhs.idom();
+ }
+ return lhs;
+ }
+
+ int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(idom().idepth()+1); }
+ // Zero depth means uncached. Check before narrowing so overflow cannot wrap.
+ final int cacheIDepth(int depth) {
+ assert 0 <= depth && depth <= Character.MAX_VALUE : "Dominator depth exceeds 65535";
+ return _idepth = (char)depth;
+ }
+
+ // Return the immediate dominator of this Node.
+ Node idom() { return in(0); }
+
// Make a shallow copy (same class) of this Node, with given inputs and
// empty outputs and a new Node ID. The original inputs are ignored.
// Does not need to be implemented in isCFG() nodes.
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/OutNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/OutNode.java
deleted file mode 100644
index 7e531145..00000000
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/OutNode.java
+++ /dev/null
@@ -1,7 +0,0 @@
-package com.seaofnodes.simple.node;
-
-import java.util.ArrayList;
-
-public interface OutNode {
- ArrayList<Node> outs();
-}
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 8f3cda9e..6995cc2f 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -32,9 +32,10 @@ public class PhiNode extends Node {
return p.unchar(',').close();
}
- public CFGNode region() { return (CFGNode)in(0); }
+ Node region() { return in(0); }
@Override public boolean isMultiTail() { return true; }
- @Override public boolean isMem() { return _declaredType instanceof TypeMem; }
+ @Override
+ public boolean isMem() { return _declaredType instanceof TypeMem; }
@Override
public Type compute() {
@@ -84,9 +85,9 @@ public class PhiNode extends Node {
Node val = in(3-nullx);
if( region().idom() instanceof IfNode iff && iff.pred().addDep(this)==val ) {
// Must walk the idom on the null side to make sure we hit False.
- CFGNode idom = (CFGNode)region().in(nullx);
+ Node idom = region().in(nullx);
while( idom.in(0) != iff ) idom = idom.idom();
- if( idom instanceof CProjNode proj && proj._idx==1 )
+ if( idom instanceof ProjNode proj && proj._idx==1 )
return val;
}
}
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/ProjNode.java
index e82c69b3..a2632110 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/ProjNode.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -15,7 +15,7 @@ public class ProjNode extends Node {
// Debugging label
public final String _label;
- public ProjNode(Node ctrl, int idx, String label) {
+ public ProjNode(MultiNode ctrl, int idx, String label) {
super(ctrl);
_idx = idx;
_label = label;
@@ -27,16 +27,30 @@ public class ProjNode extends Node {
@Override
protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p(_label); }
+ @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; }
@Override public boolean isMultiTail() { return in(0).isMultiHead(); }
@Override public boolean isMem() { return _type instanceof TypeMem; }
+ public MultiNode ctrl() { return (MultiNode)in(0); }
+
@Override
public Type compute() {
Type t = in(0)._type;
return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM;
}
- @Override public Node idealize() { return null; }
+ @Override
+ public Node idealize() {
+ if ( ctrl() instanceof IfNode iff ) {
+ if ( iff._type instanceof TypeTuple tt && tt._types[1 - _idx] == Type.XCONTROL )
+ return iff.in(0); // We become our input control
+
+ // Flip a negating if-test, to remove the not
+ if( iff.pred().addDep(this) instanceof NotNode not )
+ return new ProjNode((MultiNode)new IfNode(iff.ctrl(),not.in(1)).peephole(),1-_idx,_idx==0 ? "False" : "True");
+ }
+ return null;
+ }
@Override
boolean eq( Node n ) { return _idx == ((ProjNode)n)._idx; }
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index f0808410..8b52494a 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -3,15 +3,13 @@ package com.seaofnodes.simple.node;
import com.seaofnodes.print.ExprPrinter;
import com.seaofnodes.simple.IterPeeps;
-import com.seaofnodes.simple.Parser;
import com.seaofnodes.simple.Utils;
import com.seaofnodes.simple.type.Type;
+
import java.util.ArrayList;
import java.util.Arrays;
-import java.util.BitSet;
-import java.util.HashSet;
-public class RegionNode extends CFGNode {
+public class RegionNode extends Node {
public RegionNode(Node... nodes) { super(nodes); }
@@ -22,8 +20,8 @@ public class RegionNode extends CFGNode {
return p.p(label()).p(_nid);
}
+ @Override public boolean isCFG() { return true; }
@Override public boolean isMultiHead() { return true; }
- @Override public boolean blockHead() { return true; }
@Override
public Type compute() {
@@ -59,7 +57,7 @@ public class RegionNode extends CFGNode {
IterPeeps.addAll(phi._outputs);
}
}
- return isDead() ? Parser.XCTRL : delDef(path);
+ return isDead() ? new ConstantNode(Type.XCONTROL) : delDef(path);
}
// If down to a single input, become that input
if( nIns()==2 && !hasPhi() )
@@ -91,30 +89,23 @@ public class RegionNode extends CFGNode {
}
// Immediate dominator of Region is a little more complicated.
- @Override public int idepth() {
+ @Override int idepth() {
if( _idepth!=0 ) return _idepth;
int depth=0;
for( Node n : _inputs )
if( n!=null )
- depth = Math.max(depth,((CFGNode)n).idepth()+1);
+ depth = Math.max(depth,n.idepth()+1);
return cacheIDepth(depth);
}
- @Override public CFGNode idom() {
- CFGNode lca = null;
+ @Override Node idom() {
+ Node lca = null;
// Recompute from predecessors: CFG edits can change the dominator.
for( int i=1; i<nIns(); i++ )
- lca = cfg(i).domLCA(lca);
+ lca = in(i).domLCA(lca);
return lca;
}
- @Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) {
- for( int i=1; i<nIns(); i++ )
- cfg(i).walkUnreach(visit,unreach);
- }
-
- @Override public int loopDepth() { return _loopDepth==0 ? (_loopDepth = cfg(1).loopDepth()) : _loopDepth; }
-
// True if last input is null
public final boolean inProgress() {
return nIns()>1 && in(nIns()-1) == null;
@@ -124,6 +115,4 @@ public class RegionNode extends CFGNode {
@Override boolean eq( Node n ) {
return !inProgress();
}
-
- @Override public Node getBlockStart() { return this; }
}
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index 161cc7d6..ef4ddb3a 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -6,11 +6,10 @@ import com.seaofnodes.simple.type.*;
/** Keeps all preceding memory effects and the return value alive: {ctrl, $mem, value}. */
-public class ReturnNode extends CFGNode {
+public class ReturnNode extends Node {
public ReturnNode(Node ctrl, Node data, ScopeNode scope) {
- // A synthetic never-taken loop exit has no source scope.
- super(ctrl, scope == null ? null : scope.lookup("$mem"), data);
+ super(ctrl, scope.lookup("$mem"), data);
}
public Node ctrl() { return in(0); }
@@ -27,6 +26,8 @@ public class ReturnNode extends CFGNode {
return p.p(";");
}
+ @Override public boolean isCFG() { return true; }
+
@Override
public Type compute() {
// Return exposes the complete memory state.
@@ -39,6 +40,4 @@ public class ReturnNode extends CFGNode {
return ctrl();
return null;
}
-
- @Override public Node getBlockStart() { return ctrl().getBlockStart(); }
}
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/StartNode.java
index c1b57915..3404f111 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -3,13 +3,10 @@ package com.seaofnodes.simple.node;
import com.seaofnodes.print.ExprPrinter;
import com.seaofnodes.simple.type.*;
-import java.util.BitSet;
-import java.util.HashSet;
-/** Start supplies control, whole memory, and the argument, in that order. */
-public class StartNode extends CFGNode implements MultiNode {
-
- private final TypeTuple _args;
+/** The entry tuple: control, initial whole-memory state, and argument. */
+public class StartNode extends MultiNode {
+ final TypeTuple _args;
public StartNode(Type[] args) {
super();
@@ -23,8 +20,8 @@ public class StartNode extends CFGNode implements MultiNode {
return p.p(label());
}
+ @Override public boolean isCFG() { return true; }
@Override public boolean isMultiHead() { return true; }
- @Override public boolean blockHead() { return true; }
@Override
public TypeTuple compute() { return _args; }
@@ -33,12 +30,6 @@ public class StartNode extends CFGNode implements MultiNode {
public Node idealize() { return null; }
// No immediate dominator, and idepth==0
- @Override public int idepth() { return 0; }
- @Override public CFGNode idom() { return null; }
-
- @Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { }
-
- @Override public int loopDepth() { return (_loopDepth=1); }
-
- @Override public Node getBlockStart() { return this; }
+ @Override int idepth() { return 0; }
+ @Override Node idom() { return null; }
}
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/StopNode.java
index 46cf51da..4b4e9615 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -8,7 +8,7 @@ import com.seaofnodes.simple.type.Type;
import com.seaofnodes.simple.IterPeeps;
-public class StopNode extends CFGNode {
+public class StopNode extends Node {
public final String _src;
@@ -31,7 +31,7 @@ public class StopNode extends CFGNode {
return p.p("]");
}
- @Override public boolean blockHead() { return true; }
+ @Override public boolean isCFG() { return true; }
// If a single Return, return it.
// Otherwise, null because ambiguous.
@@ -54,17 +54,7 @@ public class StopNode extends CFGNode {
return null;
}
- @Override public int idepth() {
- if( _idepth!=0 ) return _idepth;
- int d=0;
- for( Node n : _inputs )
- if( n!=null )
- d = Math.max(d,((CFGNode)n).idepth()+1);
- return cacheIDepth(d);
- }
- @Override public CFGNode idom() { return null; }
-
- @Override public int loopDepth() { return (_loopDepth=1); }
+ @Override public Node idom() { return null; }
public Node addReturn(Node node) {
return addDef(node);
@@ -82,6 +72,4 @@ public class StopNode extends CFGNode {
if( obs != null ) obs.phase("TypeCheck");
return this;
}
-
- @Override public Node getBlockStart() { return this; }
}
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/StoreNode.java
index f61afe78..026d5c50 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/StoreNode.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/StoreNode.java
@@ -19,8 +19,8 @@ public class StoreNode extends MemOpNode {
* @param memPtr The ptr to the struct where we will store a value
* @param value Value to be stored
*/
- public StoreNode(String name, int alias, Node ctrl, Node memSlice, Node memPtr, Node value) {
- super(name, alias, ctrl, memSlice, memPtr, value);
+ public StoreNode(String name, int alias, Node memSlice, Node memPtr, Node value) {
+ super(name, alias, memSlice, memPtr, value);
}
@Override
@@ -53,7 +53,7 @@ public class StoreNode extends MemOpNode {
// Must have exactly one use of "this" or you get weird
// non-serializable memory effects in the worse case.
st.checkNoUseBeyond(this) ) {
- assert _name.equals(st._name); // Equiv class aliasing is perfect
+ assert Utils.eq(_name,st._name); // Equiv class aliasing is perfect
setDef(1,st.mem());
return this;
}
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/SubNode.java
index 7b4cff0b..6fa87a07 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -1,7 +1,6 @@
package com.seaofnodes.simple.node;
-import com.seaofnodes.simple.Parser;
import com.seaofnodes.simple.type.Type;
import com.seaofnodes.simple.type.TypeInteger;
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java
deleted file mode 100644
index 056dfba1..00000000
--- a/chapter11/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java
+++ /dev/null
@@ -1,14 +0,0 @@
-package com.seaofnodes.simple.node;
-
-import com.seaofnodes.print.ExprPrinter;
-
-import com.seaofnodes.simple.Parser;
-import com.seaofnodes.simple.type.Type;
-
-public class XCtrlNode extends CFGNode {
- public XCtrlNode( ) { super(Parser.START); }
- @Override public String label() { return "Xctrl"; }
- @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p("Xctrl"); }
- @Override public Type compute() { return Type.XCONTROL; }
- @Override public Node idealize() { return null; }
-}
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/chapter11/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
index 89ef99bd..92d970d8 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
@@ -6,13 +6,13 @@ import com.seaofnodes.simple.node.*;
import com.seaofnodes.simple.node.Node;
import com.seaofnodes.simple.type.TypeMem;
-/** Chapter 11's view of the IR; browser, transport and layout are shared. */
+/** Chapter 10's view of the IR; browser, transport and layout are shared. */
public class SimpleGraphAdapter extends GraphAdapter<Node> {
@Override protected String[] edgeNames(Node n) {
return n instanceof ScopeNode scope && n.nIns()!=0 ? scope.reverseNames() : null;
}
- @Override protected int projectionIndex(Node n) { return n instanceof ProjNode p ? p._idx : n instanceof CProjNode p ? p._idx : -1; }
+ @Override protected int projectionIndex(Node n) { return n instanceof ProjNode p ? p._idx : -1; }
@Override protected Kind kind(Node n) {
if( n instanceof StopNode ) return Kind.STOP;
@@ -25,9 +25,9 @@ public class SimpleGraphAdapter extends GraphAdapter<Node> {
}
@Override protected Role role(Node n, int i) {
- if( n instanceof ScopeNode || n instanceof ConstantNode || n instanceof XCtrlNode ) return Role.ASSOC;
+ if( n instanceof ScopeNode || n instanceof ConstantNode ) return Role.ASSOC;
if( n instanceof PhiNode ) return i == 0 ? Role.ASSOC : isMem(n) ? Role.MEM : Role.DATA;
- if( n instanceof ProjNode || n instanceof CProjNode ) return n.isCFG() ? Role.CTRL : isMem(n) ? Role.MEM : Role.DATA;
+ if( n instanceof ProjNode ) return n.isCFG() ? Role.CTRL : isMem(n) ? Role.MEM : Role.DATA;
if( n instanceof RegionNode && i == 0 ) return Role.ASSOC;
if( i == 0 || n instanceof RegionNode || n instanceof StopNode ) return Role.CTRL;
if( i == 1 && (n instanceof MemOpNode || n instanceof ReturnNode) ) return Role.MEM;
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/type/Field.java b/chapter11/src/main/java/com/seaofnodes/simple/type/Field.java
index b50a4fa6..cdc58215 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/type/Field.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/type/Field.java
@@ -20,7 +20,6 @@ public class Field extends Type {
_fname = fname;
_type = type;
}
- // Make with existing alias
public static Field make( String fname, Type type ) {
return new Field(fname,type).intern();
}
@@ -47,7 +46,7 @@ public class Field extends Type {
boolean eq(Type t) {
Field f = (Field)t;
- return _fname.equals(f._fname) && _type==f._type;
+ return Utils.eq(_fname,f._fname) && _type==f._type;
}
diff --git a/chapter11/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter11/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
index ec7390ca..0aa019a7 100644
--- a/chapter11/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
+++ b/chapter11/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
@@ -58,7 +58,8 @@ public class TypeTuple extends Type {
for( Type t : _types )
t.typeName(sb).append(",");
sb.setLength(sb.length()-1);
- return sb.append("]");
+ sb.append("]");
+ return sb;
}
public static final TypeTuple IF_BOTH = make(new Type[]{Type. CONTROL,Type. CONTROL});
diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter01Test.java
index c10dc510..89882b2f 100644
--- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter01Test.java
+++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter01Test.java
@@ -15,7 +15,7 @@ public class Chapter01Test {
StartNode start = Parser.START;
ReturnNode ret = (ReturnNode)stop.in(0);
- assertTrue(ret.ctrl() instanceof CProjNode);
+ assertTrue(ret.ctrl() instanceof ProjNode);
Node expr = ret.expr();
if( expr instanceof ConstantNode con ) {
assertEquals(start,con.in(0));
diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter04Test.java
index 14d31245..edc62f50 100644
--- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter04Test.java
+++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter04Test.java
@@ -83,7 +83,7 @@ public class Chapter04Test {
Parser parser = new Parser("return arg; ");
StopNode stop = parser.parse();
ReturnNode ret = stop.ret();
- assertTrue(ret.in(0) instanceof CProjNode);
+ assertTrue(ret.in(0) instanceof ProjNode);
assertTrue(ret.in(1) instanceof ProjNode);
assertEquals(1, ((ProjNode)ret.in(1))._idx);
assertTrue(ret.in(2) instanceof ProjNode);
diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter05Test.java
index 7beeb4d9..cf7bd6cf 100644
--- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter05Test.java
+++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter05Test.java
@@ -22,7 +22,7 @@ else {
return a;""");
StopNode ret = parser.parse().iterate();
- assertEquals("return Phi(Region21,(arg+2),(arg-3));", ret.toString());
+ assertEquals("return Phi(Region19,(arg+2),(arg-3));", ret.toString());
}
@Test
@@ -37,7 +37,7 @@ if (arg == 1) {
}
return c;""", TypeInteger.BOT);
StopNode ret = parser.parse().iterate();
- assertEquals("return Phi(Region19,4,3);", ret.toString());
+ assertEquals("return Phi(Region17,4,3);", ret.toString());
}
@Test
@@ -65,7 +65,7 @@ else
b=a+1;
return a+b;""");
StopNode ret = parser.parse().iterate();
- assertEquals("return ((arg*2)+Phi(Region24,2,3));", ret.toString());
+ assertEquals("return ((arg*2)+Phi(Region22,2,3));", ret.toString());
}
@Test
@@ -80,7 +80,7 @@ else
a=b+1;
return a+b;""");
StopNode ret = parser.parse().iterate();
- assertEquals("return ((Phi(Region35,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString());
+ assertEquals("return ((Phi(Region33,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString());
}
@Test
@@ -100,7 +100,7 @@ else
return a;
""", TypeInteger.BOT);
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Region39,Phi(Region25,2,3),Phi(Region37,4,5));", stop.toString());
+ assertEquals("return Phi(Region37,Phi(Region23,2,3),Phi(Region35,4,5));", stop.toString());
}
@Test
@@ -116,7 +116,7 @@ if( arg==0 )
return arg+a+b;
""", TypeInteger.BOT);
StopNode stop = parser.parse();
- assertEquals("return ((arg+Phi(Region16,1,0))+Phi(Region31,2,0));", stop.toString());
+ assertEquals("return ((arg+Phi(Region14,1,0))+Phi(Region29,2,0));", stop.toString());
}
@Test
@@ -130,7 +130,7 @@ if( arg==1 )
}
return a;""");
StopNode ret = parser.parse().iterate();
- assertEquals("return (arg==Phi(Region19,3,2));", ret.toString());
+ assertEquals("return (arg==Phi(Region17,3,2));", ret.toString());
}
@Test
diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter06Test.java
index df0f2848..920e26e3 100644
--- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter06Test.java
+++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter06Test.java
@@ -17,7 +17,7 @@ return 1;
""");
StopNode stop = parser.parse().iterate();
assertEquals("return 2;", stop.toString());
- assertTrue(stop.ret().ctrl() instanceof CProjNode);
+ assertTrue(stop.ret().ctrl() instanceof ProjNode);
}
@Test
@@ -30,7 +30,7 @@ if (arg)
return (arg < a) < 3;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return ((arg<Phi(Region15,2,1))<3);", stop.toString());
+ assertEquals("return ((arg<Phi(Region13,2,1))<3);", stop.toString());
}
@Test
@@ -46,7 +46,7 @@ return a;
""");
StopNode stop = parser.parse().iterate();
assertEquals("return 2;", stop.toString());
- assertTrue(stop.ret().ctrl() instanceof CProjNode);
+ assertTrue(stop.ret().ctrl() instanceof ProjNode);
}
@Test
@@ -65,7 +65,7 @@ else
b=5;
return b;""", TypeInteger.BOT);
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Region40,42,5);", stop.toString());
+ assertEquals("return Phi(Region38,42,5);", stop.toString());
}
@Test
@@ -84,7 +84,7 @@ else
b=5;
return b;""", TypeInteger.BOT);
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Region33,2,5);", stop.toString());
+ assertEquals("return Phi(Region31,2,5);", stop.toString());
}
@Test
@@ -144,7 +144,7 @@ else
return a;
""", TypeInteger.BOT);
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Region44,3,Phi(Region42,4,5));", stop.toString());
+ assertEquals("return Phi(Region42,3,Phi(Region40,4,5));", stop.toString());
}
@Test
@@ -200,7 +200,7 @@ if( arg ) {
return a+b;
""");
StopNode ret = parser.parse().iterate();
- assertEquals("return Phi(Region27,4,1);", ret.toString());
+ assertEquals("return Phi(Region25,4,1);", ret.toString());
}
@@ -251,7 +251,7 @@ if( arg ) {
return a+b+c;
""");
StopNode ret = parser.parse().iterate();
- assertEquals("return (Phi(Region39,Phi(Region26,2,3),0)+Phi(Region,3,1));", ret.toString());
+ assertEquals("return (Phi(Region37,Phi(Region24,2,3),0)+Phi(Region,3,1));", ret.toString());
}
diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter07Test.java
index 222982e7..ff0ca599 100644
--- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter07Test.java
+++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter07Test.java
@@ -18,8 +18,8 @@ public class Chapter07Test {
return arg;
""");
StopNode stop = parser.parse();
- assertEquals("return Phi(Loop9,arg,(Phi_arg+1));", stop.toString());
- assertTrue(stop.ret().ctrl() instanceof CProjNode);
+ assertEquals("return Phi(Loop7,arg,(Phi_arg+1));", stop.toString());
+ assertTrue(stop.ret().ctrl() instanceof ProjNode);
}
@Test
@@ -35,7 +35,7 @@ if(arg){}else{
return a;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Region27,1,Phi(Loop16,1,(Phi_a+1)));", stop.toString());
+ assertEquals("return Phi(Region25,1,Phi(Loop14,1,(Phi_a+1)));", stop.toString());
}
@Test
@@ -55,7 +55,7 @@ while(i < arg) {
return sum;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Loop11,0,Phi(Loop23,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString());
+ assertEquals("return Phi(Loop9,0,Phi(Loop21,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString());
}
@Test
@@ -71,8 +71,8 @@ while(a < 10) {
return b;
""");
StopNode stop = parser.parse();
- assertEquals("return Phi(Loop11,2,Phi(Region30,Phi_b,4));", stop.toString());
- assertTrue(stop.ret().ctrl() instanceof CProjNode);
+ assertEquals("return Phi(Loop9,2,Phi(Region28,Phi_b,4));", stop.toString());
+ assertTrue(stop.ret().ctrl() instanceof ProjNode);
}
@Test
@@ -90,8 +90,8 @@ while(a < 10) {
return b;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Loop11,2,(Phi(Region30,Phi_b,4)+1));", stop.toString());
- assertTrue(stop.ret().ctrl() instanceof CProjNode);
+ assertEquals("return Phi(Loop9,2,(Phi(Region28,Phi_b,4)+1));", stop.toString());
+ assertTrue(stop.ret().ctrl() instanceof ProjNode);
}
@@ -107,8 +107,8 @@ while(a < 10) {
return a;
""");
StopNode stop = parser.parse();
- assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString());
- assertTrue(stop.ret().ctrl() instanceof CProjNode);
+ assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString());
+ assertTrue(stop.ret().ctrl() instanceof ProjNode);
}
@Test
@@ -123,8 +123,8 @@ while(a < 10) {
return a;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString());
- assertTrue(stop.ret().ctrl() instanceof CProjNode);
+ assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString());
+ assertTrue(stop.ret().ctrl() instanceof ProjNode);
}
@Test
@@ -136,8 +136,8 @@ while(arg) a = 2;
return a;
""");
StopNode stop = parser.parse();
- assertEquals("return Phi(Loop10,1,2);", stop.toString());
- assertTrue(stop.ret().ctrl() instanceof CProjNode);
+ assertEquals("return Phi(Loop8,1,2);", stop.toString());
+ assertTrue(stop.ret().ctrl() instanceof ProjNode);
}
@Test
@@ -149,8 +149,8 @@ while(arg) a = 2;
return a;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Loop10,1,2);", stop.toString());
- assertTrue(stop.ret().ctrl() instanceof CProjNode);
+ assertEquals("return Phi(Loop8,1,2);", stop.toString());
+ assertTrue(stop.ret().ctrl() instanceof ProjNode);
}
@Test
@@ -165,8 +165,8 @@ while(a < 10) {
return a;
""");
StopNode stop = parser.parse();
- assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString());
- assertTrue(stop.ret().ctrl() instanceof CProjNode);
+ assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString());
+ assertTrue(stop.ret().ctrl() instanceof ProjNode);
}
@Test
@@ -181,8 +181,8 @@ while(a < 10) {
return a;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString());
- assertTrue(stop.ret().ctrl() instanceof CProjNode);
+ assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString());
+ assertTrue(stop.ret().ctrl() instanceof ProjNode);
}
@Test
@@ -198,8 +198,8 @@ while(a < 10) {
return a;
""");
StopNode stop = parser.parse();
- assertEquals("return Phi(Loop11,1,(Phi_a+3));", stop.toString());
- assertTrue(stop.ret().ctrl() instanceof CProjNode);
+ assertEquals("return Phi(Loop9,1,(Phi_a+3));", stop.toString());
+ assertTrue(stop.ret().ctrl() instanceof ProjNode);
}
@Test
@@ -215,8 +215,8 @@ while(a < 10) {
return a;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Loop11,1,(Phi_a+3));", stop.toString());
- assertTrue(stop.ret().ctrl() instanceof CProjNode);
+ assertEquals("return Phi(Loop9,1,(Phi_a+3));", stop.toString());
+ assertTrue(stop.ret().ctrl() instanceof ProjNode);
}
}
diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter08Test.java
index 8fcb29a0..4fa08bd9 100644
--- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter08Test.java
+++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter08Test.java
@@ -24,7 +24,7 @@ while(arg < 10) {
return arg;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Region37,Phi(Region27,Phi(Loop9,arg,(Phi_arg+1)),Add),Add);", stop.toString());
+ assertEquals("return Phi(Region37,Phi(Region26,Phi(Loop7,arg,(Phi_arg+1)),Add),Add);", stop.toString());
assertTrue(stop.ret().ctrl() instanceof RegionNode);
Assert.assertEquals(5L, Evaluator.evaluate(stop, 1));
Assert.assertEquals(10L, Evaluator.evaluate(stop, 6));
@@ -47,8 +47,8 @@ while(arg < 10) {
return a;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Loop10,1,Phi(Region42,Phi_a,(Phi_a+1)));", stop.toString());
- assertTrue(stop.ret().ctrl() instanceof CProjNode);
+ assertEquals("return Phi(Loop8,1,Phi(Region43,Phi_a,(Phi_a+1)));", stop.toString());
+ assertTrue(stop.ret().ctrl() instanceof ProjNode);
}
@@ -66,7 +66,7 @@ while(arg < 10) {
return arg;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Region35,Phi(Loop9,arg,(Phi_arg+1)),Add);", stop.toString());
+ assertEquals("return Phi(Region35,Phi(Loop7,arg,(Phi_arg+1)),Add);", stop.toString());
assertTrue(stop.ret().ctrl() instanceof RegionNode);
}
@@ -82,7 +82,7 @@ while(arg < 10) {
return arg;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Region27,Phi(Loop9,arg,(Phi_arg+1)),Add);", stop.toString());
+ assertEquals("return Phi(Region26,Phi(Loop7,arg,(Phi_arg+1)),Add);", stop.toString());
assertTrue(stop.ret().ctrl() instanceof RegionNode);
}
@@ -101,8 +101,8 @@ while(arg < 10) {
return arg;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Loop9,arg,(Phi_arg+1));", stop.toString());
- assertTrue(stop.ret().ctrl() instanceof CProjNode);
+ assertEquals("return Phi(Loop7,arg,(Phi_arg+1));", stop.toString());
+ assertTrue(stop.ret().ctrl() instanceof ProjNode);
}
@@ -118,8 +118,8 @@ while(arg < 10) {
return arg;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Loop9,arg,(Phi_arg+1));", stop.toString());
- assertTrue(stop.ret().ctrl() instanceof CProjNode);
+ assertEquals("return Phi(Loop7,arg,(Phi_arg+1));", stop.toString());
+ assertTrue(stop.ret().ctrl() instanceof ProjNode);
}
@Test
@@ -186,7 +186,7 @@ while(arg < 10) {
return a;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Region30,Phi(Loop10,1,(Phi_a+1)),Add);", stop.toString());
+ assertEquals("return Phi(Region29,Phi(Loop8,1,(Phi_a+1)),Add);", stop.toString());
assertTrue(stop.ret().ctrl() instanceof RegionNode);
}
@@ -202,8 +202,8 @@ while(1) {
return a;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return (Phi(Loop10,1,Add)+1);", stop.toString());
- assertTrue(stop.ret().ctrl() instanceof CProjNode prj && prj._idx==1 );
+ assertEquals("return (Phi(Loop8,1,Add)+1);", stop.toString());
+ assertTrue(stop.ret().ctrl() instanceof ProjNode prj && prj._idx==1 );
}
}
diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter09Test.java
index 7af2fa3d..1b1920e8 100644
--- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter09Test.java
+++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter09Test.java
@@ -70,7 +70,7 @@ while (arg < 10) {
return arg;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Loop10,arg,(Phi_arg+2));", stop.toString());
+ assertEquals("return Phi(Loop8,arg,(Phi_arg+2));", stop.toString());
Assert.assertEquals(11L, Evaluator.evaluate(stop, 1));
}
@@ -87,7 +87,7 @@ while (arg < 10) {
return arg;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Loop11,arg,(Phi_arg+4));", stop.toString());
+ assertEquals("return Phi(Loop9,arg,(Phi_arg+4));", stop.toString());
Assert.assertEquals(13L, Evaluator.evaluate(stop, 1));
}
@@ -116,7 +116,7 @@ while (arg) {
return arg;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Loop17,arg,(Phi_arg+1));", stop.toString());
+ assertEquals("return Phi(Loop15,arg,(Phi_arg+1));", stop.toString());
}
@Test
@@ -134,14 +134,14 @@ while(v1+arg) {
}
""");
StopNode stop = parser.parse().iterate();
- assertEquals("Stop[ return 0; return 0; ]", stop.toString());
+ assertEquals("Stop[ ]", stop.toString());
}
@Test
public void testWhile0() {
Parser parser = new Parser("while(0) continue; if(0) arg=0;");
StopNode stop = parser.parse().iterate();
- assertEquals("return 0;", stop.toString());
+ assertEquals("Stop[ ]", stop.toString());
}
@Test
@@ -153,7 +153,7 @@ if(0) while(0) {
}
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return 0;", stop.toString());
+ assertEquals("Stop[ ]", stop.toString());
}
@@ -186,7 +186,7 @@ while(arg) {
return a;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Loop12,0,(-(Phi_a+3)));", stop.toString());
+ assertEquals("return Phi(Loop10,0,(-(Phi_a+3)));", stop.toString());
}
@Test
@@ -200,7 +200,7 @@ int v0=0!=0<-0;
return -0+0+0;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return 0;", stop.toString());
+ assertEquals("Stop[ ]", stop.toString());
}
@@ -215,7 +215,7 @@ return -0+0+0;
public void testFuzz3() {
Parser parser = new Parser("int v0=0; while(0==69) while(v0) return 0;");
StopNode stop = parser.parse().iterate();
- assertEquals("return 0;", stop.toString());
+ assertEquals("Stop[ ]", stop.toString());
}
@Test
@@ -227,7 +227,7 @@ while(1) {
}
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return 0;", stop.toString());
+ assertEquals("Stop[ ]", stop.toString());
}
@Test
@@ -249,19 +249,18 @@ while(1) {
return 0!=0;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return 0;", stop.toString());
+ assertEquals("Stop[ ]", stop.toString());
}
@Test
public void testFuzz6() {
- Parser parser = new Parser(
-"""
+ Parser parser = new Parser("""
int v0=0;
while(0==1) while(v0)
v0=1+v0;
-""");
+ """);
StopNode stop = parser.parse().iterate();
- assertEquals("return 0;", stop.toString());
+ assertEquals("Stop[ ]", stop.toString());
}
@Test
@@ -277,14 +276,14 @@ while(1)
return v1+v0;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return 0;", stop.toString());
+ assertEquals("Stop[ ]", stop.toString());
}
@Test
public void testFuzz8() {
Parser parser = new Parser("while(arg) arg = arg - 1; return arg;");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Loop9,arg,(Phi_arg-1));", stop.toString());
+ assertEquals("return Phi(Loop7,arg,(Phi_arg-1));", stop.toString());
}
@Test
diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter10Test.java
index 0da695a0..8bf1debe 100644
--- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter10Test.java
+++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter10Test.java
@@ -2,11 +2,15 @@ package com.seaofnodes.simple;
import com.seaofnodes.simple.node.Node;
import com.seaofnodes.simple.node.StopNode;
+import com.seaofnodes.simple.type.*;
import com.seaofnodes.simple.node.LoadNode;
import com.seaofnodes.simple.node.StoreNode;
import com.seaofnodes.simple.evaluator.Evaluator;
import java.util.BitSet;
import org.junit.Test;
+
+import java.util.Arrays;
+
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.fail;
@@ -165,7 +169,7 @@ while (arg) {
return bar.a;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Loop12,0,(Phi_a+2));", stop.toString());
+ assertEquals("return Phi(Loop11,0,(Phi_a+2));", stop.toString());
}
@Test
@@ -217,7 +221,7 @@ if( bar ) bar.a = 1;
return bar;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Region17,null,new Bar);", stop.toString());
+ assertEquals("return Phi(Region16,null,new Bar);", stop.toString());
}
@Test
@@ -233,7 +237,7 @@ else bar.a = 1;
return rez;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Region35,4,3);", stop.toString());
+ assertEquals("return Phi(Region34,4,3);", stop.toString());
}
@Test
@@ -250,8 +254,7 @@ while(arg) {
return ret;
""");
try { parser.parse().iterate(); fail(); }
- catch( Exception e ) {
- assertEquals("Might be null accessing 'v0'", e.getMessage()); }
+ catch( Exception e ) { assertEquals("Might be null accessing 'v0'", e.getMessage()); }
}
@Test
@@ -287,7 +290,7 @@ while( i.x < i.len ) {
return sum;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Loop17,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString());
+ assertEquals("return Phi(Loop16,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString());
}
@@ -303,12 +306,11 @@ while(arg) {
v0.v0 = arg;
arg = arg-1;
if (arg==5) ret=v0;
-
}
return ret;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Loop12,new s0,Phi(Region34,new s0,Phi_ret));", stop.toString());
+ assertEquals("return Phi(Loop11,new s0,Phi(Region34,new s0,Phi_ret));", stop.toString());
}
@Test
@@ -321,7 +323,6 @@ while(arg) {
v0.v0 = arg;
arg = arg-1;
if (arg==5) ret=v0;
-
}
return ret;
""");
@@ -343,7 +344,7 @@ while(arg < 10) {
return ret;
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Loop12,new s0,Phi(Region32,new s0,Phi_ret));", stop.toString());
+ assertEquals("return Phi(Loop11,new s0,Phi(Region32,new s0,Phi_ret));", stop.toString());
}
@Test
@@ -373,7 +374,7 @@ if(0) {
}
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return 0;", stop.toString());
+ assertEquals("Stop[ ]", stop.toString());
}
@Test
@@ -447,7 +448,7 @@ while(0) {}
}
""");
StopNode stop = parser.parse().iterate();
- assertEquals("return 0;", stop.toString());
+ assertEquals("Stop[ ]", stop.toString());
}
@Test
@@ -461,6 +462,7 @@ return 0;
assertEquals("return 0;", stop.toString());
}
+
@Test public void testReadBeforeStores() {
var stop = new Parser("""
struct S { int x; int y; }
@@ -547,8 +549,8 @@ return 0;
if (arg) s.x=arg+1; else s.x=arg+2;
return s;
""").parse().iterate();
- // These chapters still bind struct Stores to branch control.
- assertEquals(3,countMemoryNodes(stop,StoreNode.class,new BitSet()));
+ // The initializing slice also remains live as the aggregate default.
+ assertEquals(2,countMemoryNodes(stop,StoreNode.class,new BitSet()));
assertEquals(2L,((Evaluator.Obj)Evaluator.evaluate(stop,0)).fields()[0]);
assertEquals(4L,((Evaluator.Obj)Evaluator.evaluate(stop,3)).fields()[0]);
}
diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter10bTest.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter10bTest.java
deleted file mode 100644
index 6f094cfb..00000000
--- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter10bTest.java
+++ /dev/null
@@ -1,64 +0,0 @@
-package com.seaofnodes.simple;
-
-import com.seaofnodes.simple.node.*;
-import com.seaofnodes.simple.evaluator.Evaluator;
-import org.junit.Test;
-import static org.junit.Assert.*;
-
-public class Chapter10bTest {
- @Test public void testIndependentField() {
- var stop = new Parser("""
- struct S { int x; int y; }
- S s = new S;
- s.x = 42;
- while (arg > 0) { s.y = s.y + arg; arg = arg - 1; }
- return s.x;
- """).parse().iterate();
- assertEquals("return 42;",stop.toString());
- assertEquals(42L,Evaluator.evaluate(stop,5));
- assertNull(stop.walk(n -> n instanceof LoadNode ? n : null));
- }
-
- @Test public void testParallelMemoryPhis() {
- var stop = new Parser("""
- struct S { int x; int y; int z; }
- S a = new S; S b = new S;
- S p = a; if (arg) p = b;
- while (arg > 0) {
- a.x = p.x + arg;
- a.y = p.y + 2;
- a.z = p.z + 3;
- arg = arg - 1;
- }
- return a;
- """).parse().iterate();
- int[] phis = {0};
- stop.walk(n -> {
- if (n instanceof MemPhiNode) phis[0]++;
- if (n instanceof MemMergeNode m && m.in(1) instanceof BulkMemPhiNode b)
- for(int a=b._aliases.nextSetBit(0); a>=0; a=b._aliases.nextSetBit(a+1))
- assertTrue(a<m.nIns() && m.in(a)!=null);
- assertFalse(n instanceof PhiNode && n.isMem() &&
- !(n instanceof MemPhiNode) && !(n instanceof BulkMemPhiNode));
- return null;
- });
- assertTrue(phis[0]>=3);
- assertArrayEquals(new Object[]{1L,2L,3L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields());
- }
-
- @Test public void testLateSliceWorklist() throws ReflectiveOperationException {
- // Seed 97 exposed a store selecting a bulk predecessor without queuing
- // it. Keep both the worklist assertion and the final heap check.
- for (int seed : new int[]{0,97,123,456}) {
- var parser = new Parser(Chapter10Test.NESTED_MEMORY);
- var field = IterPeeps.class.getDeclaredField("WORK");
- field.setAccessible(true);
- Object work = field.get(null);
- field = work.getClass().getDeclaredField("_R");
- field.setAccessible(true);
- ((java.util.Random)field.get(work)).setSeed(seed);
- var stop = parser.parse().iterate();
- assertArrayEquals(new Object[]{9L,25L,17L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields());
- }
- }
-}
diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter11Test.java
index 4c2b42f1..5f92c9c1 100644
--- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter11Test.java
+++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter11Test.java
@@ -1,567 +1,64 @@
package com.seaofnodes.simple;
-
+import com.seaofnodes.simple.node.*;
import com.seaofnodes.simple.evaluator.Evaluator;
-import com.seaofnodes.simple.node.StopNode;
import org.junit.Test;
-
-
-import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.*;
public class Chapter11Test {
-
- // A placeholder test used to rapidly rotate through fuzzer produced issues
- @Test
- public void testFuzzer() {
- Parser parser = new Parser(
-"""
-while(-----arg) {
- while(-arg) {
- while(-----arg*---0) {
- int N=--false==false<--arg;
- while(N<-4==N) {
- N=N+N;
- }
- }
- {
- int kzEl_r7EYz=3*----0!=-arg<(37*--97!=0/arg==arg)<=-(--arg!=0);
- while(kzEl_r7EYz<---1) {
- kzEl_r7EYz=kzEl_r7EYz+kzEl_r7EYz*arg>=24;
- if(7) continue;
- kzEl_r7EYz=false;
- if(-kzEl_r7EYz+arg<-3) continue;
- else {
- while(kzEl_r7EYz) continue;
- arg=----3;
- kzEl_r7EYz=-(-----arg*1>-kzEl_r7EYz);
- int v2uF_4ba=9;
- }
- }
- }
- int pjcp7rv=arg;
- {
- int m2ya3=--arg-pjcp7rv;
- while(m2ya3<-----pjcp7rv>=pjcp7rv+--pjcp7rv!=---pjcp7rv!=-arg<---(-m2ya3)>m2ya3<=-----true>14!=--m2ya3) {
- m2ya3=m2ya3+-(--0<=false<pjcp7rv/arg<=-true);
- while((--m2ya3)<--arg<-----arg*false!=arg<pjcp7rv*arg) {
- pjcp7rv=-3+-arg;
- break;
- }
- while(-3) {
- while(67+0-61) m2ya3=m2ya3;
- if(----pjcp7rv==---(---arg)) pjcp7rv=0!=-23;
- else pjcp7rv=----89;
- while(m2ya3!=m2ya3<pjcp7rv) m2ya3=1;
- while(--arg<=pjcp7rv) pjcp7rv=-32<=-m2ya3+62;
- }
- break;
- }
- }
- {
- int arg=-1<-9!=(-arg>=-pjcp7rv>=arg<=arg);
- while(arg<-arg) {
- arg=arg+--arg;
- {
- while((--93)--pjcp7rv*-pjcp7rv+arg) arg=0-(6>=(--(---41/(0))!=--pjcp7rv)>=---2*33);
- pjcp7rv=11;
- int c=pjcp7rv;
- if(--107) break;
- else break;
- }
- }
- }
- pjcp7rv=pjcp7rv;
- int aR0Wkua=-pjcp7rv==pjcp7rv;
- {
- if(-0!=-0) while(-true) break;
- else {
- while(aR0Wkua) pjcp7rv=-0/pjcp7rv;
- pjcp7rv=pjcp7rv;
- }
- }
- }
- if(-arg) {
- {
- int Isdlt0fr91=0!=arg;
- while(Isdlt0fr91<-Isdlt0fr91==-Isdlt0fr91+true) {
- Isdlt0fr91=Isdlt0fr91+-1!=true;
- if(-arg) if(--arg<=Isdlt0fr91) Isdlt0fr91=-Isdlt0fr91;
- int i=---arg<---arg!=--40;
- {
- int jVX43Ln4Dm=-(6)==-Isdlt0fr91/----0;
- while(jVX43Ln4Dm<--(3-3)) {
- jVX43Ln4Dm=jVX43Ln4Dm+-0<25;
- i=24<--(jVX43Ln4Dm);
- }
- }
- i=(arg!=----false>=7);
- int Te=5>-arg;
- break;
- }
- }
- arg=arg!=--true/arg;
- {
- int UX=arg;
- while(UX<-3*arg) {
- UX=UX+arg/-1;
- arg=-3--(-UX--47<arg==--arg==arg)/arg--UX>=-arg;
- if(---12) while(-UX) break;
- break;
- }
- }
- continue;
- }
- if(arg) arg=--0;
- else if(1) continue;
- int DtTlhjYq=19==arg;
- {
- arg=--DtTlhjYq<=(DtTlhjYq/---DtTlhjYq<=-DtTlhjYq);
- if(---arg) continue;
- else {
- int Zsl=40;
- while(Zsl<--Zsl--false>((Zsl))==Zsl!=--DtTlhjYq-DtTlhjYq-DtTlhjYq) {
- Zsl=Zsl+arg;
- }
- }
- if((arg)) if(-DtTlhjYq) {
- }
- else while(((2)==3*arg/DtTlhjYq)<=0==---arg) return false;
- else {
- int lwbF=arg>=0;
- while(lwbF<57) {
- lwbF=lwbF+--(-arg+lwbF)>=-2>=arg!=arg;
- arg=----0+0;
- while(49) break;
- if(true) DtTlhjYq=-----arg;
- DtTlhjYq=0!=-----(0);
- }
- }
- arg=---arg!=DtTlhjYq/--0;
- DtTlhjYq=-DtTlhjYq/(--arg<arg);
- if(32) {
- int q=-DtTlhjYq;
- while(q<arg*(0*q)/0) {
- q=q+DtTlhjYq;
- DtTlhjYq=arg;
- }
- }
- else if(--arg) if(15) break;
- else arg=0==arg<=-55>DtTlhjYq;
- else {
- }
- DtTlhjYq=-0;
- {
- while((0)<-arg) DtTlhjYq=-DtTlhjYq;
- }
- if(30/--(arg)>=0) DtTlhjYq=-0>=arg;
- else {
- int Y2wcIQJ=--DtTlhjYq*---11;
- if(arg==arg) {
- Y2wcIQJ=-----Y2wcIQJ;
- Y2wcIQJ=Y2wcIQJ<7;
- if(DtTlhjYq) arg=arg;
- else break;
- while(-arg!=-31==(false<=-15>=-DtTlhjYq+--6*-----Y2wcIQJ<=---arg!=-Y2wcIQJ<=---0<-arg*--Y2wcIQJ)) DtTlhjYq=arg!=3;
- }
- continue;
- }
- arg=DtTlhjYq;
- arg=--3/(---arg)>=80>=-DtTlhjYq<=DtTlhjYq;
- arg=51+---(-true)!=arg!=----1==-DtTlhjYq;
- if(11<=arg) if((arg)+79<32+(-arg)) continue;
- else if(true==DtTlhjYq) break;
- break;
- }
-}
-if(arg!=62==arg) {
- while(---arg) {
- {
- int bhmDacPM=arg/arg;
- while(bhmDacPM<arg) {
- bhmDacPM=bhmDacPM+80*((-bhmDacPM)/---bhmDacPM>1)<bhmDacPM-2!=7;
- arg=-0;
- arg=bhmDacPM>=-arg+-arg;
- break;
- }
- }
- int arg=true;
- arg=arg<=arg;
- {
- int KlC=30;
- while(KlC<-2) {
- KlC=KlC+-1!=25<=-KlC>KlC>----0;
- int Ij=arg>=-arg<=---10;
- {
- int LAbgurVa2R=-arg!=Ij;
- while(LAbgurVa2R<-true) {
- LAbgurVa2R=LAbgurVa2R+Ij;
- KlC=-LAbgurVa2R;
- Ij=42*(-Ij>true);
- while(Ij) arg=KlC;
- KlC=-----7>-(--KlC<--7)==-LAbgurVa2R;
- }
- }
- int a=Ij<=-KlC;
- if(Ij) {
- int r1W=a!=-false;
- }
- else {
- arg=56>=Ij;
- while(54) break;
- arg=8>=-(a<--Ij)/a>=-a-KlC;
- }
- int Yt_T=KlC;
- arg=KlC;
- }
- }
- if(----false/--arg/12+-----0) if(-9+-arg) while(arg!=(arg)) arg=--1>=-71-arg!=---(--arg*11+102)/--arg;
- else if(----arg) continue;
- if(-arg-arg) {
- arg=-(-arg)*--(-3)<(-7==-arg----arg);
- {
- int arg=arg;
- while(arg<-0>arg==-arg-(-arg>1+11)) {
- arg=arg+6-arg!=--0>---30>=---arg<=arg/(3)+---arg;
- }
- }
- arg=-arg+arg;
- arg=--47+-arg<1>arg*(-arg==-arg--0>3);
- arg=(----arg)!=arg+--59;
- arg=--4+arg==-(arg)-arg;
- }
- else {
- while(--true-----true*-25+-18>arg>=-----(-arg)---13) {
- arg=-0+--true<false;
- continue;
- }
- arg=true<=arg;
- break;
- }
- arg=arg*22<--(0+-arg);
- {
- continue;
- }
- }
- arg=1*---((3<=true)==---2);
- arg=7+-(-1);
- return arg+--true;
-}
-else {
- int o3ypEsewxM=-(---arg);
- int vzXB=(-(---11<=--o3ypEsewxM>=--0))<=-0/-arg;
- int L=-arg;
- int B4mHcrf=---vzXB;
- int oZWGdzZl=-o3ypEsewxM;
- int K6tQqa1=11;
- while(0!=--L) {
- int sdZfTM=vzXB*true+K6tQqa1;
- while(sdZfTM<false) {
- sdZfTM=sdZfTM+arg;
- sdZfTM=oZWGdzZl;
- K6tQqa1=-K6tQqa1;
- arg=---K6tQqa1;
- while((3+-K6tQqa1)<oZWGdzZl) {
- if(-----(-1)) sdZfTM=-false;
- {}
- }
- K6tQqa1=vzXB!=-(B4mHcrf+-7>false);
- sdZfTM=vzXB;
- }
- }
- L=false;
- while(31) B4mHcrf=arg;
- oZWGdzZl=-0<--oZWGdzZl<=--2;
- if(K6tQqa1>=20<=46) {
- if(-1+-L) if(oZWGdzZl) {
- int wmhv=-----0;
- }
- int arg=0;
- o3ypEsewxM=---(oZWGdzZl);
- return -oZWGdzZl/0;
- }
- else if(arg) {
- int yKk5=B4mHcrf>=4>K6tQqa1<-B4mHcrf/o3ypEsewxM;
- return -K6tQqa1;
- }
- else {
- if(---0) {
- {}
- {}
- }
- return o3ypEsewxM;
+ @Test public void testIndependentField() {
+ var stop = new Parser("""
+ struct S { int x; int y; }
+ S s = new S;
+ s.x = 42;
+ while (arg > 0) { s.y = s.y + arg; arg = arg - 1; }
+ return s.x;
+ """).parse().iterate();
+ assertEquals("return 42;",stop.toString());
+ assertEquals(42L,Evaluator.evaluate(stop,5));
+ assertNull(stop.walk(n -> n instanceof LoadNode ? n : null));
+ }
+
+ @Test public void testParallelMemoryPhis() {
+ var stop = new Parser("""
+ struct S { int x; int y; int z; }
+ S a = new S; S b = new S;
+ S p = a; if (arg) p = b;
+ while (arg > 0) {
+ a.x = p.x + arg;
+ a.y = p.y + 2;
+ a.z = p.z + 3;
+ arg = arg - 1;
+ }
+ return a;
+ """).parse().iterate();
+ int[] phis = {0};
+ stop.walk(n -> {
+ if (n instanceof MemPhiNode) phis[0]++;
+ if (n instanceof MemMergeNode m && m.in(1) instanceof BulkMemPhiNode b)
+ for(int a=b._aliases.nextSetBit(0); a>=0; a=b._aliases.nextSetBit(a+1))
+ assertTrue(a<m.nIns() && m.in(a)!=null);
+ assertFalse(n instanceof PhiNode && n.isMem() &&
+ !(n instanceof MemPhiNode) && !(n instanceof BulkMemPhiNode));
+ return null;
+ });
+ assertTrue(phis[0]>=3);
+ assertArrayEquals(new Object[]{1L,2L,3L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields());
+ }
+
+ @Test public void testLateSliceWorklist() throws ReflectiveOperationException {
+ // Seed 97 exposed a store selecting a bulk predecessor without queuing
+ // it. Keep both the worklist assertion and the final heap check.
+ for (int seed : new int[]{0,97,123,456}) {
+ var parser = new Parser(Chapter10Test.NESTED_MEMORY);
+ var field = IterPeeps.class.getDeclaredField("WORK");
+ field.setAccessible(true);
+ Object work = field.get(null);
+ field = work.getClass().getDeclaredField("_R");
+ field.setAccessible(true);
+ ((java.util.Random)field.get(work)).setSeed(seed);
+ var stop = parser.parse().iterate();
+ assertArrayEquals(new Object[]{9L,25L,17L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields());
}
-}
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("Stop[ return 9; return 0; return 0; ]", stop.toString());
- }
-
-
-
- @Test
- public void testPrimes() {
- Parser parser = new Parser(
-"""
-if( arg < 2 ) return 0;
-int primeCount = 1;
-int prime = 3;
-while( prime <= arg ) {
- int isPrime = 1;
- // Check for even case, so the next loop need only check odds
- if( (prime/2)*2 == prime )
- continue;
- // Check odds up to sqrt of prime
- int j = 3;
- while( j*j <= prime ) {
- if( (prime/j)*j == prime ) {
- isPrime = 0;
- break;
- }
- j = j + 2;
- }
- if( isPrime )
- primeCount = primeCount + 1;
- prime = prime + 2;
-}
-return primeCount;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("Stop[ return 0; return Phi(Loop20,1,Phi(Region82,Phi_primeCount,Phi(Region77,(Phi_primeCount+1),Phi_primeCount))); ]", stop.toString());
- assertEquals(0L, Evaluator.evaluate(stop, 1)); // No primes 1 or below
- assertEquals(1L, Evaluator.evaluate(stop, 2)); // 2
- assertEquals(2L, Evaluator.evaluate(stop, 3)); // 2, 3
- assertEquals(2L, Evaluator.evaluate(stop, 4)); // 2, 3
- assertEquals(3L, Evaluator.evaluate(stop, 5)); // 2, 3, 5
- assertEquals(4L, Evaluator.evaluate(stop, 10)); // 2, 3, 5, 7
- }
-
- @Test
- public void testAntiDeps1() {
- Parser parser = new Parser(
-"""
-struct S { int f; }
-S v=new S;
-v.f = 2;
-int i=new S.f;
-i=v.f;
-if (arg) v.f=1;
-return i;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("return .f;", stop.toString());
- }
-
- @Test
- public void testAntiDeps2() {
- Parser parser = new Parser(
-"""
-struct S { int f; }
-S v = new S;
-S t = new S;
-int i = 0;
-if (arg) {
- if (arg+1) v = t;
- i = v.f;
-} else {
- v.f = 2;
-}
-return i;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Region34,.f,0);", stop.toString());
- }
-
- @Test
- public void testAntiDeps3() {
- Parser parser = new Parser(
-"""
-struct S { int f; }
-S v0 = new S;
-S? v1;
-if (arg) v1 = new S;
-if (v1) {
- v0.f = v1.f;
-} else {
- v0.f = 2;
-}
-return v0;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("return new S;", stop.toString());
- }
-
-
- @Test
- public void testAntiDeps4() {
- Parser parser = new Parser(
-"""
-struct S { int f; }
-S v = new S;
-S t = new S;
-int i = v.f;
-if (arg+1) arg= 0;
-while (arg) v.f = 2;
-return i;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("return .f;", stop.toString());
- }
-
- @Test
- public void testAntiDeps5() {
- Parser parser = new Parser(
-"""
-struct S { int f; }
-S v = new S;
-while(1) {
- while(arg+1) { arg=arg-1; }
- if (arg) break;
- v.f = 2;
-}
-return v;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("return new S;", stop.toString());
- }
-
- @Test
- public void testAntiDeps6() {
- Parser parser = new Parser(
-"""
-struct s { int v; }
-s ptr=new s;
-while( -arg )
- ptr = new s;
-while(1)
- arg = arg+ptr.v;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("return 0;", stop.toString());
- }
-
- @Test
- public void testAntiDeps7() {
- Parser parser = new Parser(
-"""
-struct S { int f; }
-S v = new S;
-S t = new S;
-int i = v.f;
-while (arg) {
- v.f = arg;
- arg = arg-1;
-}
-return i;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("return .f;", stop.toString());
- }
-
- @Test
- public void testAntiDeps8() {
- Parser parser = new Parser(
-"""
-struct S { int f; }
-S v = new S;
-S t = new S;
-while(arg) {
- arg=arg-1;
- int f = v.f;
- v.f = 2;
- if (arg) arg = f;
- else v.f = 3;
-}
-return arg;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Loop15,arg,Phi(Region39,.f,0));", stop.toString());
- }
-
- @Test
- public void testAntiDeps9() {
- Parser parser = new Parser(
-"""
-struct S { int f; }
-S v = new S;
-S t = new S;
-if (arg) {
- v.f=2;
- int i=t.f;
- v.f=i;
-}
-return v;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("return new S;", stop.toString());
- }
-
- @Test
- public void testExample2() {
- Parser parser = new Parser(
- """
-struct S { int f; }
-S v = new S;
-int i = arg;
-while (arg > 0) {
- int j = i/3;
- if (arg == 5)
- v.f = j;
- arg = arg - 1;
-}
-return v;
-""");
- StopNode stop = parser.parse().iterate();
- //assertEquals("return new S;", stop.toString());
- }
-
- @Test
- public void testSplit() {
- Parser parser = new Parser(
- """
-struct S { int f; }
-S s = new S;
-if( arg==0 ) s.f = 1;
-else if (arg == 1) s.f = 1;
-return s.f;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("return Phi(Region41,1,Phi(Region36,1,0));", stop.toString());
- assertEquals(1L, Evaluator.evaluate(stop, 0));
- assertEquals(1L, Evaluator.evaluate(stop, 1));
- assertEquals(0L, Evaluator.evaluate(stop, 2));
- }
-
- @Test
- public void testScheduleUse() {
- Parser parser = new Parser(
-"""
-int v0=0;
-while(0>=0) {
- int v1=0;
- v1=v0;
- if(v1*0)
- v0=-v1;
-}
-return 0;
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("return 0;", stop.toString());
- }
-
- @Test
- public void testLoopCarriedDep() {
- Parser parser = new Parser(
-"""
-int v0=0;
-{
- int v1=0;
- while(v1) {
- v1=1+(v0!=0);
- v0=v1/0;
- }
-}
-""");
- StopNode stop = parser.parse().iterate();
- assertEquals("return 0;", stop.toString());
}
}
diff --git a/chapter11/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/chapter11/src/test/java/com/seaofnodes/simple/FuzzerWrap.java
index 52c2a014..019140ad 100644
--- a/chapter11/src/test/java/com/seaofnodes/simple/FuzzerWrap.java
+++ b/chapter11/src/test/java/com/seaofnodes/simple/FuzzerWrap.java
@@ -29,8 +29,8 @@ public class FuzzerWrap {
fuzzer.fuzzPeepsRegression(seed);
}
- @Ignore
@Test
+ @Ignore
public void fuzzPeepsLarge() {
var fuzzer = new Fuzzer();
for (int i=0; i<1000000; i++)
diff --git a/chapter11/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter11/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
index 355d906b..ac7c5e09 100644
--- a/chapter11/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
+++ b/chapter11/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
@@ -140,8 +140,7 @@ public class Evaluator {
case StoreNode store -> store(store);
case MemMergeNode merge -> MEMORY;
case NewNode alloc -> alloc(alloc);
- case CProjNode cproj -> ((Object[])val(cproj.ctrl()))[cproj._idx];
- case ProjNode proj -> ((Object[])val( proj.in(0) ))[ proj._idx];
+ case ProjNode proj -> ((Object[])val(proj.ctrl()))[proj._idx];
default -> throw new AssertionError("Unexpected node " + node);
};
}
diff --git a/chapter11/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java b/chapter11/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java
index d16f4300..48ac0562 100644
--- a/chapter11/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java
+++ b/chapter11/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java
@@ -164,7 +164,7 @@ public class Scheduler {
* @return true if the node is not XCtrl.
*/
private static boolean isNotXCtrl(Node node) {
- return !(node instanceof ConstantNode c && c.compute() == Type.XCONTROL) && !(node instanceof XCtrlNode);
+ return !(node instanceof ConstantNode c && c.compute() == Type.XCONTROL);
}
/**
@@ -215,7 +215,7 @@ public class Scheduler {
private void refinePlacement(NodeData data, BasicBlock block) {
assert !isPinnedNode(data);
data.block = data.block == null ? block : dom(data.block, block);
- assert isValid(data);
+ assert isValid(data) : data.node.uniqueName()+" at "+data.block.entry.uniqueName();
}
/**
@@ -328,8 +328,6 @@ public class Scheduler {
for(int i=1; i<r.nIns(); i++) {
if (od(r.in(i)).map(d->d.block==null).orElse(false)) return false;
}
- } else if (node instanceof XCtrlNode) {
- return false;
} else {
assert d(node.in(0)).block != null;
}
@@ -405,7 +403,7 @@ public class Scheduler {
}
}
if (!(node instanceof ReturnNode))
- for (Node n:node._outputs) if (n!=null && n.isCFG() && isCFGNodeReady(n) && d(n).block == null) queue.push(d(n));
+ for (Node n:node._outputs) if (n.isCFG() && isCFGNodeReady(n) && d(n).block == null) queue.push(d(n));
var b = block;
for(var in:data.node._inputs) od(in).ifPresent(d->update(d, b));
}
@@ -451,7 +449,7 @@ public class Scheduler {
node = data.node;
assert node.isCFG();
if (!(node instanceof ReturnNode)) {
- for (var out : node._outputs) if (out!=null && out.isCFG() && isNotXCtrl(out)) markAlive(cfgQueue, out, true);
+ for (var out : node._outputs) if (out.isCFG() && isNotXCtrl(out)) markAlive(cfgQueue, out, true);
}
for (var in : node._inputs) if(in!=null && !in.isCFG() && isNotXCtrl(in)) markAlive(dataQueue, in, false);
}
@@ -505,7 +503,7 @@ public class Scheduler {
*/
private static Node findSingleCFGOut(Node node) {
if (node instanceof StartNode) {
- for(var n:node._outputs) if (n instanceof CProjNode p && p._idx==0) return p;
+ for(var n:node._outputs) if (n instanceof ProjNode p && p._idx==0) return p;
return null;
}
assert node._outputs.stream().filter(Node::isCFG).limit(2).count()<=1;
@@ -572,7 +570,7 @@ public class Scheduler {
switch(block.exit) {
case null: break;
case IfNode i:
- for(var out:i._outputs) if (out instanceof CProjNode p) block.next[p._idx] = blocks.get(p);
+ for(var out:i._outputs) if (out instanceof ProjNode p) block.next[p._idx] = blocks.get(p);
break;
case RegionNode r:
block.next[0] = blocks.get(r);