From b475b072b38db7f46406ed6128fffe3e15a6e7ac Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 29 Sep 2026 13:08:30 -0700 Subject: forward port lazy memory to ch11 --- chapter11/README.md | 306 +++++++------ chapter11/docs/Makefile | 2 + chapter11/docs/graph1.gv | 15 +- chapter11/docs/graph1.svg | 317 +++++++------- chapter11/docs/graph2.gv | 16 +- chapter11/docs/graph2.svg | 342 ++++++++------- chapter11/docs/graph3.gv | 16 +- chapter11/docs/graph3.svg | 354 ++++++++------- chapter11/docs/graph4.gv | 19 +- chapter11/docs/graph4.svg | 435 +++++++++--------- chapter11/docs/graph5.gv | 20 +- chapter11/docs/graph5.svg | 486 +++++++++++---------- chapter11/docs/graph6.gv | 20 +- chapter11/docs/graph6.svg | 478 ++++++++++---------- chapter11/docs/graph8.gv | 2 +- chapter11/docs/graph8.svg | 104 ++--- .../com/seaofnodes/simple/GlobalCodeMotion.java | 16 +- .../main/java/com/seaofnodes/simple/Parser.java | 39 +- .../com/seaofnodes/simple/node/BulkMemPhiNode.java | 237 ++++++++++ .../java/com/seaofnodes/simple/node/LoadNode.java | 12 +- .../com/seaofnodes/simple/node/MemMergeNode.java | 60 +++ .../com/seaofnodes/simple/node/MemPhiNode.java | 36 ++ .../main/java/com/seaofnodes/simple/node/Node.java | 12 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 6 +- .../com/seaofnodes/simple/node/ReturnNode.java | 28 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 4 +- .../java/com/seaofnodes/simple/node/StartNode.java | 46 +- .../java/com/seaofnodes/simple/node/StoreNode.java | 8 +- .../java/com/seaofnodes/simple/Chapter04Test.java | 5 +- .../java/com/seaofnodes/simple/Chapter05Test.java | 14 +- .../java/com/seaofnodes/simple/Chapter06Test.java | 12 +- .../java/com/seaofnodes/simple/Chapter07Test.java | 26 +- .../java/com/seaofnodes/simple/Chapter08Test.java | 16 +- .../java/com/seaofnodes/simple/Chapter09Test.java | 10 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 74 +++- .../java/com/seaofnodes/simple/Chapter10bTest.java | 64 +++ .../java/com/seaofnodes/simple/Chapter11Test.java | 8 +- .../com/seaofnodes/simple/evaluator/Evaluator.java | 7 +- .../com/seaofnodes/simple/evaluator/Scheduler.java | 11 +- 39 files changed, 2181 insertions(+), 1502 deletions(-) create mode 100644 chapter11/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java create mode 100644 chapter11/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java create mode 100644 chapter11/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java create mode 100644 chapter11/src/test/java/com/seaofnodes/simple/Chapter10bTest.java (limited to 'chapter11') diff --git a/chapter11/README.md b/chapter11/README.md index c2f329bc..b91f4fd7 100644 --- a/chapter11/README.md +++ b/chapter11/README.md @@ -1,9 +1,18 @@ # Chapter 11: Global Code Motion -The preceding memory lesson is now split into [10a](../chapter10a/README.md) -and [10b](../chapter10b/README.md). This snapshot still constructs the older -per-alias memory chains in the parser. The language is unchanged; forwarding -10b's bulk-memory representation through Chapters 11-24 is a separate migration. +This chapter schedules the memory representation introduced in +[10b](../chapter10b/README.md): one parser-visible `$mem`, with `MemMerge`, +`MemPhi`, and `BulkMemPhi` recovering independent field chains. Start supplies +`{ctrl, $mem, arg}`. Return consumes `{ctrl, $mem, result}`, with the complete +memory aggregate in slot 1. Nodes consuming or producing both control and +memory consistently use slot 0 for control and slot 1 for memory. + +The new scheduling rule is to distinguish a memory aggregate from a memory +write. `MemMerge` gets a placement from its inputs and uses, but emits no heap +operation and creates no load/store anti-dependency. A Store or MemPhi can +constrain a Load only for the same alias; a BulkMemPhi can constrain it only +while it still covers that alias. Both kinds of memory Phi remain attached to +their Region, just like scalar Phis. # Table of Contents @@ -56,7 +65,7 @@ At its core, the scheduling algorithm works in two phases: * Schedule Early - in this phase, we do an upward DFS walk on the "inputs" of each Node, starting from the bottom (Stop). We schedule each data node to the first control block where they are dominated by their inputs. -* Schedule Late - in this phase we do a downward DFS walk on the "outputs" of each Node starting from the top (Start), and move data nodes to a block between the first block calculated above, +* Schedule Late - in this phase we work backwards from Stop, scheduling uses before definitions, and move data nodes to a block between the first block calculated above, and the last control block where they dominate all their uses. The placement is subject to the condition that it is in the shallowest loop nest possible, and is as control dependent as possible. Additionally, the placement of Load instructions must ensure correct ordering between Loads and Stores of the same memory location. @@ -78,6 +87,10 @@ return i; First lets look at the graph before scheduling. +These walkthrough diagrams show the precise `S.f` chain and the final +MemMerge consumed by Return. The unchanged default memory comes from Start; +any redundant bulk Phis have folded away. Arrows point from uses to definitions. + ![Graph1](./docs/graph1.svg) Observe that @@ -369,133 +382,148 @@ A pre-condition of this is to ensure that infinite loops have been "fixed" as de The implementation of early schedule is shown below: ```java - // ------------------------------------------------------------------------ -private static void schedEarly() { - ArrayList rpo = new ArrayList<>(); - BitSet visit = new BitSet(); - _rpo_cfg(Parser.START, visit, rpo); - // Reverse Post-Order on CFG - for( int j=rpo.size()-1; j>=0; j-- ) { - CFGNode cfg = rpo.get(j); - cfg.loopDepth(); - for( Node n : cfg._inputs ) - _schedEarly(n,visit); - // Strictly for dead infinite loops, we can have entire code blocks - // not reachable from below - so we reach down, from above, one - // step. Since _schedEarly modifies the output arrays, the normal - // region._outputs ArrayList iterator throws CME. The extra edges - // are always *added* after any Phis, so just walk the Phi prefix. - if( cfg instanceof RegionNode region ) { - int len = region.nOuts(); - for( int i=0; i rpo = new ArrayList<>(); + BitSet visit = new BitSet(); + _rpo_cfg(Parser.START, visit, rpo); + // Reverse Post-Order on CFG + for( int j=rpo.size()-1; j>=0; j-- ) { + CFGNode cfg = rpo.get(j); + cfg.loopDepth(); + for( Node n : cfg._inputs ) + _schedEarly(n,visit); + // In dead infinite loops, entire code blocks may be unreachable + // from below. Reach down from the CFG to their Phis so their + // inputs are scheduled too. + if( cfg instanceof RegionNode ) { + int len = cfg.nOuts(); + for( int i=0; i rpo) { - if( !(n instanceof CFGNode cfg) || visit.get(cfg._nid) ) - return; // Been there, done that - visit.set(cfg._nid); - for( Node use : cfg._outputs ) - _rpo_cfg(use,visit,rpo); - rpo.add(cfg); -} + // Post-Order of CFG + private static void _rpo_cfg(Node n, BitSet visit, ArrayList rpo) { + if( !(n instanceof CFGNode cfg) || visit.get(cfg._nid) ) + return; // Been there, done that + visit.set(cfg._nid); + for( Node use : cfg._outputs ) + _rpo_cfg(use,visit,rpo); + rpo.add(cfg); + } -private static void _schedEarly(Node n, BitSet visit) { - if( n==null || visit.get(n._nid) ) return; // Been there, done that - visit.set(n._nid); - // Schedule not-pinned not-CFG inputs before self. Since skipping - // Pinned, this never walks the backedge of Phis (and thus spins around - // a data-only loop, eventually attempting relying on some pre-visited- - // not-post-visited data op with no scheduled control. - for( Node def : n._inputs ) - if( def!=null && !def.isPinned() ) - _schedEarly(def,visit); - // If not-pinned (e.g. constants, projections, phi) and not-CFG - if( !n.isPinned() ) { - // Schedule at deepest input - CFGNode early = Parser.START; // Maximally early, lowest idepth - for( int i=1; i early.idepth() ) - early = n.in(i).cfg0(); // Latest/deepest input - n.setDef(0,early); // First place this can go - } -} + private static void _schedEarly(Node n, BitSet visit) { + if( n==null || visit.get(n._nid) ) return; // Been there, done that + visit.set(n._nid); + // Schedule inputs first, except Phis: following their backedges would + // enter a data cycle before its control has been scheduled. + for( Node def : n._inputs ) + if( def!=null && !(def instanceof PhiNode) ) + _schedEarly(def,visit); + // An existing edge 0 already supplies control (or a Phi/Proj binding). + if( n.in(0)==null ) { + // Schedule at deepest input + CFGNode early = Parser.START; // Maximally early, lowest idepth + for( int i=1; i early.idepth() ) + early = n.in(i).cfg0(); // Latest/deepest input + n.setDef(0,early); // First place this can go + } + } ``` -* The early schedule populates the control input for data nodes - recall that this is null up to this point as data nodes are not attached to any control flow nodes until now. -* Most of the code above is about walking the graph in the right order. The actual computation of the early schedule is in these lines: - -```java - // If not-pinned (e.g. constants, projections, phi) and not-CFG - if( !n.isPinned() ) { - // Schedule at deepest input - CFGNode early = Parser.START; // Maximally early, lowest idepth - for( int i=1; i early.idepth() ) - early = n.in(i).cfg0(); // Latest/deepest input - n.setDef(0,early); // First place this can go - } -``` +Existing control and Phi/Proj bindings are preserved. Floating nodes receive +the deepest input block as their earliest placement. MemMerge follows this +same rule, ignoring absent entries in its sparse alias table. ## Late Schedule -During this phase we do a downward DFS walk on the "outputs" of each Node starting from the top (Start), and move data nodes to a block between the first block in the early schedule, -and the last control block where they dominate all their uses. The placement is subject to the condition that it is in the shallowest loop nest possible, and is as control dependent as possible. -Additionally, the placement of Load instructions must ensure correct ordering between Loads and Stores of the same memory location. - -The code for computing the late schedule is shown below. +Late scheduling starts at Stop and uses a worklist to place uses before their +definitions. CFG nodes, Phis, projections, and allocations provide fixed +placements. Other nodes wait until their uses have been scheduled; a Load also +waits for memory users that can overwrite or merge its alias. The chosen block +lies between the early placement and the common dominator of all uses, favoring +shallower loops and then deeper control flow. ```java - // ------------------------------------------------------------------------ - private static void schedLate(StartNode start) { + private static void schedLate( StopNode stop) { CFGNode[] late = new CFGNode[Node.UID()]; Node[] ns = new Node[Node.UID()]; - _schedLate(start,ns,late); + // Record Load NIDs at all their CFG block choices, then check against + // Store block choices to force a Load above an anti-dependent Store. + int[] anti = new int[Node.UID()]; + // Breadth-first scheduling + breadth(stop,ns,late,anti); + + // Copy the best placement choice into the control slot for( int i=0; i work = new WorkList<>(); + work.push(stop); + Node n; + outer: + while( (n = work.pop()) != null ) { + assert late[n._nid]==null; // No double visit + // These I know the late schedule of, and need to set early for loops + if( n instanceof CFGNode cfg ) late[n._nid] = cfg.blockHead() ? cfg : cfg.cfg(0); + else if( n instanceof PhiNode phi ) late[n._nid] = phi.region(); + // These nodes have a fixed late placement at their original control. + else if( n instanceof ProjNode || n instanceof NewNode || n==Parser.ZERO ) late[n._nid] = n.cfg0(); + else { + + // All uses done? + for( Node use : n._outputs ) + if( use!=null && late[use._nid]==null ) + continue outer; // Nope, await all uses done + + // Loads need their memory inputs' uses also done + if( n instanceof LoadNode ld ) + for( Node memuse : ld.mem()._outputs ) + if( antiUse(ld,memuse) && late[memuse._nid]==null ) + continue outer; + + // All uses done, schedule + _doSchedLate(n,ns,late,anti); + } + // A use just finished; reconsider its inputs and waiting loads, + // even when the shared memory input was already scheduled. + for( Node def : n._inputs ) { + if( def==null ) continue; + if( late[def._nid]==null ) work.push(def); + for( Node out : def._outputs ) + if( out instanceof LoadNode ld && late[ld._nid]==null ) + work.push(ld); + } + if( n instanceof LoopNode loop ) + for( Node phi : loop._outputs ) + if( phi instanceof PhiNode && late[phi._nid]==null ) + work.push(phi); + } + } + + private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) { // Walk uses, gathering the LCA (Least Common Ancestor) of uses - CFGNode early = (CFGNode)n.in(0); + CFGNode early = n.in(0) instanceof CFGNode cfg ? cfg : n.in(0).cfg0(); assert early != null; CFGNode lca = null; for( Node use : n._outputs ) - lca = use_block(n,use, late).idom(lca); + 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); + lca = find_anti_dep(lca,load,early,late,anti); // Walk up from the LCA to the early, looking for best place. This is - // lowest execution frequency, approximated by least loop depth and + // 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 @@ -515,35 +543,41 @@ The code for computing the late schedule is shown below. CFGNode found=null; for( int i=1; i best.idepth() || best instanceof IfNode); - } - - // Skip iteration if a backedge - private static boolean isForwardsEdge(Node use, Node def) { - return use != null && def != null && - !(use.nIns()>2 && use.in(2)==def && (use instanceof LoopNode || (use instanceof PhiNode phi && phi.region() instanceof LoopNode))); + return lca.loopDepth() < best.loopDepth() || + lca instanceof NeverNode || + lca.idepth() > best.idepth() || + best instanceof IfNode; } ``` ## Inserting Anti Dependencies -To ensure that Loads and Stores to the same memory location are correctly ordered, we insert an edge from the Load to the Store as described below. +To ensure that Loads and Stores to the same memory location are correctly ordered, we insert an edge from the Store to the Load as described below: the Store must wait for the earlier Load. We call these edges anti-dependencies because they do not represent the Def-Use dependency that we normally capture in SoN, and are purely present as scheduling constraints. We compute anti-dependencies DURING running schedule late. This is because we rely on the early-schedule, and the late-schedule of the Load's uses (before scheduling the Load). -Looking backwards from the Load we follow the memory edge to the "memory definer" - a start-mem-projection, or a phi-mem, or a store. -We look forwards from the mem-def to all its mem-def users. There is always at least one; there may be many. These completely (all of it) and exactly (no doubling up) cover the forward memory space, sort of like a network flow problem - but we limit our analysis to same-alias, -because for example, a start-mem-proj produces all aliases. This gives us a candidate set of mem-defs; some of these need the anti-dependency on the Load, but not all. +Looking backwards from the Load, we follow its memory input to Start's memory +projection, a memory Phi, or a Store. Optimization has already selected the +Load's precise slice through any MemMerge. We inspect users of that memory +definition, keeping only Stores and memory Phis that cover the Load's alias. +Start's single memory projection may supply many aliases, so sharing a memory +input alone does not imply an anti-dependency. + +MemMerge only packages slices; it does not overwrite any of them. Treating it +as a write could make a Load wait for an aggregate which itself depends on the +Load's result. The same alias filter is used both when deciding whether a Load +is ready to schedule and when computing its anti-dependencies. A completed +memory user wakes waiting loads even if their shared memory definition has +already been scheduled. Since we're in the middle of "schedule late", we have already computed all the late schedules of a Load's users, and we have the Loads "Least Common Ancestor" of uses, the LCA or late position. We inspect the set of mem-defs that might impact the Load, and either add an anti-dependency from Store to Load, or raise the Loads effective LCA. @@ -553,38 +587,50 @@ For stores, we do the same - until/unless we find stores with the SAME block as The implementation is shown below. ```java - private static CFGNode find_anti_dep(CFGNode lca, LoadNode load, CFGNode early, CFGNode[] late) { + // 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() ) - cfg._anti = load._nid; + 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); + 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 $@ + @sed -i 's/\r$$//' $@ .PHONY: clean clean: diff --git a/chapter11/docs/graph1.gv b/chapter11/docs/graph1.gv index 74c54fdb..3554a572 100644 --- a/chapter11/docs/graph1.gv +++ b/chapter11/docs/graph1.gv @@ -18,11 +18,12 @@ return i; Start - +
$ctrlarg$2
$ctrl$memarg
> ]; + MemMerge [ shape=box label="MemMerge" ]; Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; Con_4 [ label="#0" ]; new9 [ label="new S" ]; @@ -44,14 +45,14 @@ return i; Con_21 [ label="#1" ]; Store22 [ label=".f =" ]; Region23 [ shape=box style=filled fillcolor=yellow label="Region" ]; - Phi_224 [ style=filled fillcolor=lightyellow label="φ_$2" ]; + Phi_224 [ style=filled fillcolor=lightyellow label="MemPhi_2" ]; Return25 [ shape=box style=filled fillcolor=yellow label="Return" ]; { rank=same; Region23;Phi_224;} } edge [ fontname=Helvetica, fontsize=8 ]; Stop3 -> Return25[taillabel=0 color=red]; new9 -> Start2:p0[taillabel=0 color=green]; - Store12 -> Start2:p2[taillabel=1 color=blue]; + Store12 -> Start2:p1[taillabel=1 color=blue]; Store12 -> new9[taillabel=2]; Store12 -> Con_11[taillabel=3]; new13 -> Start2:p0[taillabel=0 color=green]; @@ -61,7 +62,7 @@ return i; Load16 -> Store14[taillabel=1 color=blue]; Load16 -> new9[taillabel=2]; If17 -> Start2:p0[taillabel=0 color=red]; - If17 -> Start2:p1[taillabel=1]; + If17 -> Start2:p2[taillabel=1]; Store22 -> Store14[taillabel=1 color=blue]; Store22 -> new9[taillabel=2]; Store22 -> Con_21[taillabel=3]; @@ -71,6 +72,8 @@ return i; Phi_224 -> Store22[taillabel=1 color=blue]; Phi_224 -> Store14[taillabel=2 color=blue constraint=false]; Return25 -> Region23[taillabel=0 color=red]; - Return25 -> Load16[taillabel=1]; - Return25 -> Phi_224[taillabel=2 color=blue]; + Return25 -> Load16[taillabel=2]; + Return25 -> MemMerge[taillabel=1 color=blue]; + MemMerge -> Start2:p1[taillabel=1 color=blue]; + MemMerge -> Phi_224[taillabel=2 color=blue]; } diff --git a/chapter11/docs/graph1.svg b/chapter11/docs/graph1.svg index 592db961..422d790e 100644 --- a/chapter11/docs/graph1.svg +++ b/chapter11/docs/graph1.svg @@ -1,285 +1,306 @@ - - - + + chapter11 - + cluster_Nodes - + Start2 - - -Start - - - -$ctrl - -arg - -$2 + + +Start + + + +$ctrl + +$mem + +arg + + + +MemMerge + +MemMerge + + + +MemMerge->Start2:p1 + + +1 + + + +Phi_224 + +MemPhi_2 + + + +MemMerge->Phi_224 + + +2 - + Stop3 - -Stop + +Stop - + Return25 - -Return + +Return Stop3->Return25 - - -0 + + +0 - + Con_4 - -#0 + +#0 - + new9 - -new S + +new S new9->Start2:p0 - - -0 + + +0 - + Con_11 - -#2 + +#2 - + Store12 - -.f = + +.f = -Store12->Start2:p2 - - -1 +Store12->Start2:p1 + + +1 Store12->new9 - - -2 + + +2 Store12->Con_11 - - -3 + + +3 - + new13 - -new S + +new S new13->Start2:p0 - - -0 + + +0 - + Store14 - -.f = + +.f = Store14->Con_4 - - -3 + + +3 Store14->Store12 - - -1 + + +1 Store14->new13 - - -2 + + +2 - + Load16 - -.f + +.f Load16->new9 - - -2 + + + +2 Load16->Store14 - - -1 + + +1 - + If17 - - -If - - - -True - - -False + + +If + + + +True + + +False If17->Start2:p0 - - -0 + + + +0 + + + +If17->Start2:p2 + + +1 - + Con_21 - -#1 + +#1 - + Store22 - -.f = + +.f = Store22->new9 - - -2 + +2 Store22->Store14 - - -1 + + +1 Store22->Con_21 - - -3 + + +3 - + Region23 - -Region + +Region Region23->If17:p0 - - -1 - - - -Region23->If17:p1 - - -2 - - - -Phi_224 - -φ_$2 + + +1 Phi_224->Store14 - - -2 + + +2 Phi_224->Store22 - - -1 + + +1 Phi_224->Region23 - - -0 + + +0 + + + +Return25->MemMerge + + +1 Return25->Load16 - - -1 + + +2 Return25->Region23 - - -0 - - - -Return25->Phi_224 - - -2 + + +0 diff --git a/chapter11/docs/graph2.gv b/chapter11/docs/graph2.gv index 04d02a3f..730cf845 100644 --- a/chapter11/docs/graph2.gv +++ b/chapter11/docs/graph2.gv @@ -18,11 +18,12 @@ return i;
Start
 - +
$ctrlarg$2
$ctrl$memarg
> ]; + MemMerge [ shape=box label="MemMerge" ]; Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; Con_4 [ label="#0" ]; new9 [ label="new S" ]; @@ -44,7 +45,7 @@ return i; Con_21 [ label="#1" ]; Store22 [ label=".f =" ]; Region23 [ shape=box style=filled fillcolor=yellow label="Region" ]; - Phi_224 [ style=filled fillcolor=lightyellow label="φ_$2" ]; + Phi_224 [ style=filled fillcolor=lightyellow label="MemPhi_2" ]; Return25 [ shape=box style=filled fillcolor=yellow label="Return" ]; { rank=same; Region23;Phi_224;} } @@ -52,7 +53,7 @@ return i; Stop3 -> Return25[taillabel=0 color=red]; new9 -> Start2:p0[taillabel=0 color=green]; Store12 -> Start2:p0[taillabel=0 color=red]; - Store12 -> Start2:p2[taillabel=1 color=blue]; + Store12 -> Start2:p1[taillabel=1 color=blue]; Store12 -> new9[taillabel=2]; Store12 -> Con_11[taillabel=3]; new13 -> Start2:p0[taillabel=0 color=green]; @@ -64,7 +65,7 @@ return i; Load16 -> Store14[taillabel=1 color=blue]; Load16 -> new9[taillabel=2]; If17 -> Start2:p0[taillabel=0 color=red]; - If17 -> Start2:p1[taillabel=1]; + If17 -> Start2:p2[taillabel=1]; Store22 -> Start2:p0[taillabel=0 color=red]; Store22 -> Store14[taillabel=1 color=blue]; Store22 -> new9[taillabel=2]; @@ -75,6 +76,9 @@ return i; Phi_224 -> Store22[taillabel=1 color=blue]; Phi_224 -> Store14[taillabel=2 color=blue constraint=false]; Return25 -> Region23[taillabel=0 color=red]; - Return25 -> Load16[taillabel=1]; - Return25 -> Phi_224[taillabel=2 color=blue]; + Return25 -> Load16[taillabel=2]; + Return25 -> MemMerge[taillabel=1 color=blue]; + MemMerge -> Start2:p1[taillabel=1 color=blue]; + MemMerge -> Phi_224[taillabel=2 color=blue]; + MemMerge -> Region23[taillabel=0 color=green]; } diff --git a/chapter11/docs/graph2.svg b/chapter11/docs/graph2.svg index 00f7b594..b8d43cc9 100644 --- a/chapter11/docs/graph2.svg +++ b/chapter11/docs/graph2.svg @@ -1,309 +1,335 @@ - - - + + chapter11 - + cluster_Nodes - + Start2 - - -Start - - - -$ctrl - -arg - -$2 + + +Start + + + +$ctrl + +$mem + +arg + + + +MemMerge + +MemMerge + + + +MemMerge->Start2:p1 + + +1 + + + +Region23 + +Region + + + +MemMerge->Region23 + + +0 + + + +Phi_224 + +MemPhi_2 + + + +MemMerge->Phi_224 + + +2 - + Stop3 - -Stop + +Stop - + Return25 - -Return + +Return Stop3->Return25 - - -0 + + +0 - + Con_4 - -#0 + +#0 - + new9 - -new S + +new S new9->Start2:p0 - - -0 + + +0 - + Con_11 - -#2 + +#2 - + Store12 - -.f = + +.f = Store12->Start2:p0 - - - -0 + + + +0 Store12->new9 - - -2 + + +2 Store12->Con_11 - - -3 + + +3 - + new13 - -new S + +new S new13->Start2:p0 - - -0 + + +0 - + Store14 - -.f = + +.f = Store14->Start2:p0 - - -0 + + +0 Store14->Con_4 - - -3 + + +3 Store14->Store12 - - -1 + + +1 Store14->new13 - - - -2 + + +2 - + Load16 - -.f + +.f Load16->Start2:p0 - - - -0 + + + +0 Load16->new9 - - -2 + + + +2 Load16->Store14 - - -1 + + +1 - + If17 - - -If - - - -True - - -False + + +If + + + +True + + +False If17->Start2:p0 - -0 + +0 - + Con_21 - -#1 + +#1 - + Store22 - -.f = + +.f = Store22->Start2:p0 - - -0 + + +0 Store22->new9 - - - -2 + +2 Store22->Store14 - - -1 + + +1 Store22->Con_21 - - -3 - - - -Region23 - -Region + + +3 Region23->If17:p0 - - -1 + + +1 Region23->If17:p1 - - -2 - - - -Phi_224 - -φ_$2 + + +2 Phi_224->Store14 - - -2 + + +2 Phi_224->Store22 - - -1 + + +1 Phi_224->Region23 - - -0 + + +0 + + + +Return25->MemMerge + + +1 Return25->Load16 - - -1 + + + +2 Return25->Region23 - - -0 - - - -Return25->Phi_224 - - -2 + + +0 diff --git a/chapter11/docs/graph3.gv b/chapter11/docs/graph3.gv index c47ac565..d89d0ed4 100644 --- a/chapter11/docs/graph3.gv +++ b/chapter11/docs/graph3.gv @@ -18,11 +18,12 @@ return i;
Start
 - +
$ctrlarg$2
$ctrl$memarg
> ]; + MemMerge [ shape=box label="MemMerge" ]; Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; Con_4 [ label="#0" ]; new9 [ label="new S" ]; @@ -44,7 +45,7 @@ return i; Con_21 [ label="#1" ]; Store22 [ label=".f =" ]; Region23 [ shape=box style=filled fillcolor=yellow label="Region" ]; - Phi_224 [ style=filled fillcolor=lightyellow label="φ_$2" ]; + Phi_224 [ style=filled fillcolor=lightyellow label="MemPhi_2" ]; Return25 [ shape=box style=filled fillcolor=yellow label="Return" ]; { rank=same; Region23;Phi_224;} } @@ -52,7 +53,7 @@ return i; Stop3 -> Return25[taillabel=0 color=red]; new9 -> Start2:p0[taillabel=0 color=green]; Store12 -> Start2:p0[taillabel=0 color=red]; - Store12 -> Start2:p2[taillabel=1 color=blue]; + Store12 -> Start2:p1[taillabel=1 color=blue]; Store12 -> new9[taillabel=2]; Store12 -> Con_11[taillabel=3]; new13 -> Start2:p0[taillabel=0 color=green]; @@ -64,7 +65,7 @@ return i; Load16 -> Store14[taillabel=1 color=blue]; Load16 -> new9[taillabel=2]; If17 -> Start2:p0[taillabel=0 color=red]; - If17 -> Start2:p1[taillabel=1]; + If17 -> Start2:p2[taillabel=1]; Store22 -> If17:p0[taillabel=0 color=red]; Store22 -> Store14[taillabel=1 color=blue]; Store22 -> new9[taillabel=2]; @@ -76,6 +77,9 @@ return i; Phi_224 -> Store22[taillabel=1 color=blue]; Phi_224 -> Store14[taillabel=2 color=blue constraint=false]; Return25 -> Region23[taillabel=0 color=red]; - Return25 -> Load16[taillabel=1]; - Return25 -> Phi_224[taillabel=2 color=blue]; + Return25 -> Load16[taillabel=2]; + Return25 -> MemMerge[taillabel=1 color=blue]; + MemMerge -> Start2:p1[taillabel=1 color=blue]; + MemMerge -> Phi_224[taillabel=2 color=blue]; + MemMerge -> Region23[taillabel=0 color=green]; } diff --git a/chapter11/docs/graph3.svg b/chapter11/docs/graph3.svg index e017c4af..a16a1733 100644 --- a/chapter11/docs/graph3.svg +++ b/chapter11/docs/graph3.svg @@ -1,316 +1,348 @@ - - - + + chapter11 - + cluster_Nodes - + Start2 - - -Start - - - -$ctrl - -arg - -$2 + + +Start + + + +$ctrl + +$mem + +arg + + + +MemMerge + +MemMerge + + + +MemMerge->Start2:p1 + + +1 + + + +Region23 + +Region + + + +MemMerge->Region23 + + +0 + + + +Phi_224 + +MemPhi_2 + + + +MemMerge->Phi_224 + + +2 - + Stop3 - -Stop + +Stop - + Return25 - -Return + +Return Stop3->Return25 - - -0 + + +0 - + Con_4 - -#0 + +#0 - + new9 - -new S + +new S new9->Start2:p0 - - -0 + + +0 - + Con_11 - -#2 + +#2 - + Store12 - -.f = + +.f = Store12->Start2:p0 - - - -0 + + + +0 Store12->new9 - - -2 + + +2 Store12->Con_11 - - -3 + + +3 - + new13 - -new S + +new S new13->Start2:p0 - - -0 + + +0 - + Store14 - -.f = + +.f = Store14->Start2:p0 - - -0 + +0 Store14->Con_4 - - -3 + + +3 Store14->Store12 - - -1 + + +1 Store14->new13 - - - -2 + + +2 - + Load16 - -.f + +.f Load16->Start2:p0 - - - -0 + + + +0 Load16->new9 - - -2 + + +2 Load16->Store14 - - -1 + + +1 - + If17 - - -If - - - -True - - -False + + +If + + + +True + + +False If17->Start2:p0 - -0 + + +0 + + + +If17->Start2:p2 + + +1 - + Con_21 - -#1 + +#1 - + Store22 - -.f = + +.f = Store22->new9 - - -2 + + +2 Store22->Store14 - - - -1 + + +1 Store22->Load16 - - -4 + + +4 Store22->If17:p0 - - -0 + + +0 Store22->Con_21 - - -3 - - - -Region23 - -Region + + +3 Region23->If17:p0 - - -1 + + +1 Region23->If17:p1 - - -2 - - - -Phi_224 - -φ_$2 + + +2 Phi_224->Store14 - - -2 + + +2 Phi_224->Store22 - - -1 + + +1 Phi_224->Region23 - - -0 + + +0 + + + +Return25->MemMerge + + +1 Return25->Load16 - - -1 + + +2 Return25->Region23 - - -0 - - - -Return25->Phi_224 - - -2 + + +0 diff --git a/chapter11/docs/graph4.gv b/chapter11/docs/graph4.gv index f6958ccb..cf622aa1 100644 --- a/chapter11/docs/graph4.gv +++ b/chapter11/docs/graph4.gv @@ -21,11 +21,12 @@ return v;
Start
 - +
$ctrlarg$2
$ctrl$memarg
> ]; + MemMerge [ shape=box label="MemMerge" ]; Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; Con_4 [ label="#0" ]; new9 [ label="new S" ]; @@ -57,10 +58,10 @@ return v; > ]; - Phi_230 [ style=filled fillcolor=lightyellow label="φ_$2" ]; + Phi_230 [ style=filled fillcolor=lightyellow label="MemPhi_2" ]; Store31 [ label=".f =" ]; Region32 [ shape=box style=filled fillcolor=yellow label="Region" ]; - Phi_233 [ style=filled fillcolor=lightyellow label="φ_$2" ]; + Phi_233 [ style=filled fillcolor=lightyellow label="MemPhi_2" ]; Sub35 [ label="-" ]; Con_36 [ label="#1" ]; Return37 [ shape=box style=filled fillcolor=yellow label="Return" ]; @@ -70,19 +71,19 @@ return v; edge [ fontname=Helvetica, fontsize=8 ]; Stop3 -> Return37[taillabel=0 color=red]; new9 -> Start2:p0[taillabel=0 color=green]; - Store10 -> Start2:p2[taillabel=1 color=blue]; + Store10 -> Start2:p1[taillabel=1 color=blue]; Store10 -> new9[taillabel=2]; Store10 -> Con_4[taillabel=3]; Loop11 -> Start2:p0[taillabel=1 color=red]; Loop11 -> Region32[taillabel=2 color=red constraint=false]; Phi_arg13 -> Loop11 [style=dotted taillabel=0]; - Phi_arg13 -> Start2:p1[taillabel=1]; + Phi_arg13 -> Start2:p2[taillabel=1]; Phi_arg13 -> Sub35[taillabel=2 constraint=false]; LT14 -> Con_4[taillabel=1]; LT14 -> Phi_arg13[taillabel=2]; If16 -> Loop11[taillabel=0 color=red]; If16 -> LT14[taillabel=1]; - Div21 -> Start2:p1[taillabel=1]; + Div21 -> Start2:p2[taillabel=1]; Div21 -> Con_22[taillabel=2]; EQ23 -> Phi_arg13[taillabel=1]; EQ23 -> Con_24[taillabel=2]; @@ -102,6 +103,8 @@ return v; Sub35 -> Phi_arg13[taillabel=1]; Sub35 -> Con_36[taillabel=2]; Return37 -> If16:p1[taillabel=0 color=red]; - Return37 -> new9[taillabel=1]; - Return37 -> Phi_230[taillabel=2 color=blue]; + Return37 -> new9[taillabel=2]; + Return37 -> MemMerge[taillabel=1 color=blue]; + MemMerge -> Start2:p1[taillabel=1 color=blue]; + MemMerge -> Phi_230[taillabel=2 color=blue]; } diff --git a/chapter11/docs/graph4.svg b/chapter11/docs/graph4.svg index 7f392664..2730813a 100644 --- a/chapter11/docs/graph4.svg +++ b/chapter11/docs/graph4.svg @@ -1,408 +1,429 @@ - - - + + chapter11 - + cluster_Nodes - + Start2 - - -Start - - - -$ctrl - -arg - -$2 + + +Start + + + +$ctrl + +$mem + +arg + + + +MemMerge + +MemMerge + + + +MemMerge->Start2:p1 + + +1 + + + +Phi_230 + +MemPhi_2 + + + +MemMerge->Phi_230 + + +2 - + Stop3 - -Stop + +Stop - + Return37 - -Return + +Return Stop3->Return37 - - -0 + + +0 - + Con_4 - -#0 + +#0 - + new9 - -new S + +new S new9->Start2:p0 - - -0 + + +0 - + Store10 - -.f = + +.f = -Store10->Start2:p2 - - -1 +Store10->Start2:p1 + + +1 Store10->Con_4 - - -3 + + +3 Store10->new9 - - -2 + + +2 - + Loop11 - -Loop + +Loop Loop11->Start2:p0 - - -1 + + +1 - + Region32 - -Region + +Region Loop11->Region32 - - -2 + + +2 - + Phi_arg13 - -φ_arg + +φ_arg -Phi_arg13->Start2:p1 - - -1 +Phi_arg13->Start2:p2 + + +1 Phi_arg13->Loop11 - - -0 + + +0 - + Sub35 - -- + +- - + LT14 - -< + +< LT14->Con_4 - - -1 + + +1 LT14->Phi_arg13 - - -2 + + +2 - + If16 - - -If - - - -True - - -False + + +If + + + +True + + +False If16->Loop11 - - -0 + + +0 If16->LT14 - - -1 + + +1 - + Div21 - -// + +// -Div21->Start2:p1 - - -1 +Div21->Start2:p2 + + +1 - + Con_22 - -#3 + +#3 Div21->Con_22 - - -2 + + +2 - + EQ23 - -== + +== EQ23->Phi_arg13 - - -1 + + +1 - + Con_24 - -#5 + +#5 EQ23->Con_24 - - -2 + + +2 - + If25 - - -If - - - -True - - -False + + +If + + + +True + + +False If25->If16:p0 - - -0 + + +0 If25->EQ23 - - -1 - - - -Phi_230 - -φ_$2 + + +1 Phi_230->Store10 - - -1 + + +1 Phi_230->Loop11 - - -0 + + +0 - + Phi_233 - -φ_$2 + +MemPhi_2 - + Store31 - -.f = + +.f = Store31->new9 - -2 + + + +2 Store31->Div21 - - -3 + + +3 Store31->Phi_230 - - -1 + + +1 Region32->If25:p0 - - -1 + + +1 Region32->If25:p1 - - -2 + + +2 Phi_233->Phi_230 - - - -2 + + + +2 Phi_233->Store31 - - -1 + + +1 Phi_233->Region32 - - -0 + + +0 Sub35->Phi_arg13 - - - -1 + + + +1 - + Con_36 - -#1 + +#1 Sub35->Con_36 - - -2 + + +2 + + + +Return37->MemMerge + + +1 Return37->new9 - - - -1 + + +2 Return37->If16:p1 - - -0 - - - -Return37->Phi_230 - - -2 + + +0 diff --git a/chapter11/docs/graph5.gv b/chapter11/docs/graph5.gv index f89a83ac..0baa512f 100644 --- a/chapter11/docs/graph5.gv +++ b/chapter11/docs/graph5.gv @@ -21,11 +21,12 @@ return v;
Start
 - +
$ctrlarg$2
$ctrl$memarg
> ]; + MemMerge [ shape=box label="MemMerge" ]; Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; Con_4 [ label="#0" ]; new9 [ label="new S" ]; @@ -57,10 +58,10 @@ return v; > ]; - Phi_230 [ style=filled fillcolor=lightyellow label="φ_$2" ]; + Phi_230 [ style=filled fillcolor=lightyellow label="MemPhi_2" ]; Store31 [ label=".f =" ]; Region32 [ shape=box style=filled fillcolor=yellow label="Region" ]; - Phi_233 [ style=filled fillcolor=lightyellow label="φ_$2" ]; + Phi_233 [ style=filled fillcolor=lightyellow label="MemPhi_2" ]; Sub35 [ label="-" ]; Con_36 [ label="#1" ]; Return37 [ shape=box style=filled fillcolor=yellow label="Return" ]; @@ -71,13 +72,13 @@ return v; Stop3 -> Return37[taillabel=0 color=red]; new9 -> Start2:p0[taillabel=0 color=green]; Store10 -> Start2:p0[taillabel=0 color=red]; - Store10 -> Start2:p2[taillabel=1 color=blue]; + Store10 -> Start2:p1[taillabel=1 color=blue]; Store10 -> new9[taillabel=2]; Store10 -> Con_4[taillabel=3]; Loop11 -> Start2:p0[taillabel=1 color=red]; Loop11 -> Region32[taillabel=2 color=red constraint=false]; Phi_arg13 -> Loop11 [style=dotted taillabel=0]; - Phi_arg13 -> Start2:p1[taillabel=1]; + Phi_arg13 -> Start2:p2[taillabel=1]; Phi_arg13 -> Sub35[taillabel=2 constraint=false]; LT14 -> Loop11[taillabel=0 color=red]; LT14 -> Con_4[taillabel=1]; @@ -85,7 +86,7 @@ return v; If16 -> Loop11[taillabel=0 color=red]; If16 -> LT14[taillabel=1]; Div21 -> Start2[taillabel=0 color=red]; - Div21 -> Start2:p1[taillabel=1]; + Div21 -> Start2:p2[taillabel=1]; Div21 -> Con_22[taillabel=2]; EQ23 -> Loop11[taillabel=0 color=red]; EQ23 -> Phi_arg13[taillabel=1]; @@ -108,6 +109,9 @@ return v; Sub35 -> Phi_arg13[taillabel=1]; Sub35 -> Con_36[taillabel=2]; Return37 -> If16:p1[taillabel=0 color=red]; - Return37 -> new9[taillabel=1]; - Return37 -> Phi_230[taillabel=2 color=blue]; + Return37 -> new9[taillabel=2]; + Return37 -> MemMerge[taillabel=1 color=blue]; + MemMerge -> Start2:p1[taillabel=1 color=blue]; + MemMerge -> Phi_230[taillabel=2 color=blue]; + MemMerge -> Loop11[taillabel=0 color=green]; } diff --git a/chapter11/docs/graph5.svg b/chapter11/docs/graph5.svg index 6dbf29f9..9336ac3e 100644 --- a/chapter11/docs/graph5.svg +++ b/chapter11/docs/graph5.svg @@ -1,452 +1,472 @@ - - - + + chapter11 - + cluster_Nodes - + Start2 - - -Start - - - -$ctrl - -arg - -$2 + + +Start + + + +$ctrl + +$mem + +arg + + + +MemMerge + +MemMerge + + + +MemMerge->Start2:p1 + + +1 + + + +Loop11 + +Loop + + + +MemMerge->Loop11 + + +0 + + + +Phi_230 + +MemPhi_2 + + + +MemMerge->Phi_230 + + +2 - + Stop3 - -Stop + +Stop - + Return37 - -Return + +Return Stop3->Return37 - - -0 + + +0 - + Con_4 - -#0 + +#0 - + new9 - -new S + +new S new9->Start2:p0 - - -0 + + +0 - + Store10 - -.f = + +.f = Store10->Start2:p0 - - - -0 - - - -Store10->Start2:p2 - - -1 + + +0 Store10->Con_4 - - -3 + + +3 Store10->new9 - - -2 - - - -Loop11 - -Loop + + +2 Loop11->Start2:p0 - -1 + + +1 - + Region32 - -Region + +Region Loop11->Region32 - - -2 + + +2 - + Phi_arg13 - -φ_arg + +φ_arg -Phi_arg13->Start2:p1 - - -1 +Phi_arg13->Start2:p2 + + +1 Phi_arg13->Loop11 - - -0 + + +0 - + Sub35 - -- + +- - + LT14 - -< + +< LT14->Con_4 - - -1 + + +1 LT14->Loop11 - - -0 + + +0 LT14->Phi_arg13 - - -2 + + +2 - + If16 - - -If - - - -True - - -False + + +If + + + +True + + +False If16->Loop11 - - -0 + + +0 If16->LT14 - - -1 + + +1 - + Div21 - -// + +// Div21->Start2 - - -0 + + +0 -Div21->Start2:p1 - - -1 +Div21->Start2:p2 + + +1 - + Con_22 - -#3 + +#3 Div21->Con_22 - - -2 + + +2 - + EQ23 - -== + +== EQ23->Loop11 - - -0 + + +0 EQ23->Phi_arg13 - - -1 + + +1 - + Con_24 - -#5 + +#5 EQ23->Con_24 - - -2 + + +2 - + If25 - - -If - - - -True - - -False + + +If + + + +True + + +False If25->If16:p0 - - -0 + + +0 If25->EQ23 - - -1 - - - -Phi_230 - -φ_$2 + + +1 Phi_230->Store10 - - -1 + + +1 Phi_230->Loop11 - - -0 + + +0 - + Phi_233 - -φ_$2 + +MemPhi_2 - + Store31 - -.f = + +.f = Store31->new9 - - -2 + + +2 Store31->Loop11 - - -0 + + +0 Store31->Div21 - - - -3 + + + +3 Store31->Phi_230 - - -1 + + +1 Region32->If25:p0 - - -1 + + +1 Region32->If25:p1 - - -2 + + +2 Phi_233->Phi_230 - - - -2 + + + +2 Phi_233->Store31 - - -1 + + +1 Phi_233->Region32 - - -0 + + +0 Sub35->Loop11 - - -0 + + +0 Sub35->Phi_arg13 - - - -1 + + + +1 - + Con_36 - -#1 + +#1 Sub35->Con_36 - - -2 + + +2 + + + +Return37->MemMerge + + +1 Return37->new9 - - - -1 + + + +2 Return37->If16:p1 - - -0 - - - -Return37->Phi_230 - - -2 + + +0 diff --git a/chapter11/docs/graph6.gv b/chapter11/docs/graph6.gv index dfd07d7e..ff97eebc 100644 --- a/chapter11/docs/graph6.gv +++ b/chapter11/docs/graph6.gv @@ -21,11 +21,12 @@ return v;
Start
 - +
$ctrlarg$2
$ctrl$memarg
> ]; + MemMerge [ shape=box label="MemMerge" ]; Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; Con_4 [ label="#0" ]; new9 [ label="new S" ]; @@ -57,10 +58,10 @@ return v; > ]; - Phi_230 [ style=filled fillcolor=lightyellow label="φ_$2" ]; + Phi_230 [ style=filled fillcolor=lightyellow label="MemPhi_2" ]; Store31 [ label=".f =" ]; Region32 [ shape=box style=filled fillcolor=yellow label="Region" ]; - Phi_233 [ style=filled fillcolor=lightyellow label="φ_$2" ]; + Phi_233 [ style=filled fillcolor=lightyellow label="MemPhi_2" ]; Sub35 [ label="-" ]; Con_36 [ label="#1" ]; Return37 [ shape=box style=filled fillcolor=yellow label="Return" ]; @@ -71,13 +72,13 @@ return v; Stop3 -> Return37[taillabel=0 color=red]; new9 -> Start2:p0[taillabel=0 color=green]; Store10 -> Start2:p0[taillabel=0 color=red]; - Store10 -> Start2:p2[taillabel=1 color=blue]; + Store10 -> Start2:p1[taillabel=1 color=blue]; Store10 -> new9[taillabel=2]; Store10 -> Con_4[taillabel=3]; Loop11 -> Start2:p0[taillabel=1 color=red]; Loop11 -> Region32[taillabel=2 color=red constraint=false]; Phi_arg13 -> Loop11 [style=dotted taillabel=0]; - Phi_arg13 -> Start2:p1[taillabel=1]; + Phi_arg13 -> Start2:p2[taillabel=1]; Phi_arg13 -> Sub35[taillabel=2 constraint=false]; LT14 -> Loop11[taillabel=0 color=red]; LT14 -> Con_4[taillabel=1]; @@ -85,7 +86,7 @@ return v; If16 -> Loop11[taillabel=0 color=red]; If16 -> LT14[taillabel=1]; Div21 -> Start2:p0[taillabel=0 color=red]; - Div21 -> Start2:p1[taillabel=1]; + Div21 -> Start2:p2[taillabel=1]; Div21 -> Con_22[taillabel=2]; EQ23 -> If16:p0[taillabel=0 color=red]; EQ23 -> Phi_arg13[taillabel=1]; @@ -108,6 +109,9 @@ return v; Sub35 -> Phi_arg13[taillabel=1]; Sub35 -> Con_36[taillabel=2]; Return37 -> If16:p1[taillabel=0 color=red]; - Return37 -> new9[taillabel=1]; - Return37 -> Phi_230[taillabel=2 color=blue]; + Return37 -> new9[taillabel=2]; + Return37 -> MemMerge[taillabel=1 color=blue]; + MemMerge -> Start2:p1[taillabel=1 color=blue]; + MemMerge -> Phi_230[taillabel=2 color=blue]; + MemMerge -> If16:p1[taillabel=0 color=green]; } diff --git a/chapter11/docs/graph6.svg b/chapter11/docs/graph6.svg index 354f5d2f..8b8bb190 100644 --- a/chapter11/docs/graph6.svg +++ b/chapter11/docs/graph6.svg @@ -1,437 +1,471 @@ - - - + + chapter11 - + cluster_Nodes - + Start2 - - -Start - - - -$ctrl - -arg - -$2 + + +Start + + + +$ctrl + +$mem + +arg + + + +MemMerge + +MemMerge + + + +MemMerge->Start2:p1 + + +1 + + + +If16 + + +If + + + +True + + +False + + + +MemMerge->If16:p1 + + +0 + + + +Phi_230 + +MemPhi_2 + + + +MemMerge->Phi_230 + +2 - + Stop3 - -Stop + +Stop - + Return37 - -Return + +Return Stop3->Return37 - - -0 + + +0 - + Con_4 - -#0 + +#0 - + new9 - -new S + +new S new9->Start2:p0 - - -0 + + +0 - + Store10 - -.f = + +.f = Store10->Start2:p0 - - -0 + + +0 Store10->Con_4 - - -3 + + +3 Store10->new9 - - -2 + + +2 - + Loop11 - -Loop + +Loop Loop11->Start2:p0 - - -1 + + +1 - + Region32 - -Region + +Region Loop11->Region32 - - -2 + + +2 - + Phi_arg13 - -φ_arg + +φ_arg -Phi_arg13->Start2:p1 - - -1 +Phi_arg13->Start2:p2 + + +1 Phi_arg13->Loop11 - - -0 + + +0 - + Sub35 - -- + +- - + LT14 - -< + +< LT14->Con_4 - - -1 + + +1 LT14->Loop11 - - -0 + + +0 LT14->Phi_arg13 - - -2 - - - -If16 - - -If - - - -True - - -False + + +2 If16->Loop11 - - -0 + + +0 If16->LT14 - - -1 + + +1 - + Div21 - -// + +// Div21->Start2:p0 - - -0 + + +0 -Div21->Start2:p1 - - -1 +Div21->Start2:p2 + + +1 - + Con_22 - -#3 + +#3 Div21->Con_22 - - -2 + + +2 - + EQ23 - -== + +== EQ23->Phi_arg13 - - -1 + + +1 EQ23->If16:p0 - - -0 + + +0 - + Con_24 - -#5 + +#5 EQ23->Con_24 - - -2 + + +2 - + If25 - - -If - - - -True - - -False + + +If + + + +True + + +False If25->If16:p0 - - -0 + + +0 If25->EQ23 - - -1 - - - -Phi_230 - -φ_$2 + + +1 Phi_230->Store10 - - -1 + + +1 Phi_230->Loop11 - - -0 + + +0 - + Phi_233 - -φ_$2 + +MemPhi_2 - + Store31 - -.f = + +.f = Store31->new9 - - - -2 + + + + +2 Store31->Div21 - - -3 + + +3 Store31->If25:p0 - - -0 + + +0 Store31->Phi_230 - - -1 + + + +1 Region32->If25:p0 - - -1 + + +1 + + + +Region32->If25:p1 + + +2 Phi_233->Phi_230 - - - -2 + + + +2 Phi_233->Store31 - - -1 + + +1 Phi_233->Region32 - - -0 + + +0 Sub35->Phi_arg13 - - - -1 + + + +1 Sub35->Region32 - - -0 + + +0 - + Con_36 - -#1 + +#1 Sub35->Con_36 - - -2 + + +2 + + + +Return37->MemMerge + + +1 Return37->new9 - - -1 + +2 Return37->If16:p1 - - -0 - - - -Return37->Phi_230 - - -2 + + +0 diff --git a/chapter11/docs/graph8.gv b/chapter11/docs/graph8.gv index 1a7b231d..431cef46 100644 --- a/chapter11/docs/graph8.gv +++ b/chapter11/docs/graph8.gv @@ -39,7 +39,7 @@ return 0; Never18 -> Con_4[taillabel=1]; Stop3 -> Return21[taillabel=0 color=red]; Return21 -> Never18:p0[taillabel=0 color=red]; - Return21 -> Con_4[taillabel=1]; + Return21 -> Con_4[taillabel=2]; Loop8 -> Start2:p0[taillabel=1 color=red]; Loop8 -> Never18:p1[taillabel=2 color=red constraint=false]; } diff --git a/chapter11/docs/graph8.svg b/chapter11/docs/graph8.svg index c577cf84..a89eeeb5 100644 --- a/chapter11/docs/graph8.svg +++ b/chapter11/docs/graph8.svg @@ -1,115 +1,115 @@ - - - + + chapter11 - + cluster_Nodes - + Never18 - - -Never - - - -True - - -False + + +Never + + + +True + + +False Con_4 - -#0 + +#0 Never18->Con_4 - - -1 + + +1 Loop8 - -Loop + +Loop Never18->Loop8 - - -0 + + +0 Start2 - - -Start - - - -$ctrl + + +Start + + + +$ctrl Stop3 - -Stop + +Stop Return21 - -Return + +Return Stop3->Return21 - - -0 + + +0 Return21->Never18:p0 - - -0 + + +0 Return21->Con_4 - - -1 + + +2 Loop8->Never18:p1 - - -2 + + +2 Loop8->Start2:p0 - - -1 + + +1 diff --git a/chapter11/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter11/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 53f51f86..35b34576 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -146,7 +146,7 @@ public abstract class GlobalCodeMotion { // Loads need their memory inputs' uses also done if( n instanceof LoadNode ld ) for( Node memuse : ld.mem()._outputs ) - if( late[memuse._nid]==null && memuse._type instanceof TypeMem ) + if( antiUse(ld,memuse) && late[memuse._nid]==null ) continue outer; // All uses done, schedule @@ -217,6 +217,17 @@ public abstract class GlobalCodeMotion { 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 @@ -224,6 +235,7 @@ public abstract class GlobalCodeMotion { 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); @@ -235,8 +247,6 @@ public abstract class GlobalCodeMotion { if( phi.in(i)==load.mem() ) lca = anti_dep(load,phi.region().cfg(i),load.mem().cfg0(),lca,null,anti); break; - case LoadNode ld: break; // Loads do not cause anti-deps on other loads - case ReturnNode ret: break; // Load must already be ahead of Return default: throw Utils.TODO(); } } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/Parser.java b/chapter11/src/main/java/com/seaofnodes/simple/Parser.java index 5f4922f4..fb4dfdf8 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/Parser.java @@ -36,6 +36,10 @@ public class Parser { public StopNode STOP; + // Field identities are independent of the memory graph and Start's tuple. + private final HashMap _aliases = new HashMap<>(); + private int _alias = 2; + // Debugger Printing. public static boolean SCHEDULED; // True if debug printer can use schedule info @@ -96,7 +100,7 @@ public class Parser { _lexer = new Lexer(source); _scope = new ScopeNode(); _continueScope = _breakScope = null; - START = new StartNode(new Type[]{ Type.CONTROL, arg }); + 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(); @@ -123,7 +127,8 @@ public class Parser { // 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, 1, ScopeNode.ARG0).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()); @@ -211,7 +216,8 @@ public class Parser { // 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 - START.addMemProj(ts, _scope); // Insert memory edges + _aliases.put(typeName,_alias); + _alias += ts._fields.length; return parseStatement(); } @@ -599,21 +605,24 @@ public class Parser { */ private Node newStruct(TypeStruct obj) { Node n = new NewNode(TypeMemPtr.make(obj), ctrl()).peephole().keep(); - int alias = START._aliasStarts.get(obj._name); + int alias = _aliases.get(obj._name); for( Field field : obj._fields ) { - memAlias(alias, new StoreNode(field._fname, alias, ctrl(), memAlias(alias), n, ZERO).peephole()); + store(field._fname,alias,n,ZERO); alias++; } return n.unkeep(); } - // We set up memory aliases by inserting special vars in the scope these - // variables are prefixed by $ so they cannot be referenced in Simple code. - // Using vars has the benefit that all the existing machinery of scoping - // and phis work as expected - private Node memAlias(int alias ) { return _scope.lookup(memName(alias) ); } - private Node memAlias(int alias, Node st) { return _scope.update(memName(alias), st); } - public static String memName(int alias) { return ("$"+alias).intern(); } + // Memory is one hidden SSA variable, including across branches and loops. + private Node mem() { return _scope.lookup("$mem"); } + private Node mem(Node n) { return _scope.update("$mem",n); } + + 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(); + mem(new MemMergeNode(prior,alias,st).peephole()); + prior.unkeep(); + } /** * Parse postfix expression. For now this is just a field @@ -632,20 +641,20 @@ public class Parser { String name = requireId().intern(); int idx = ptr._obj==null ? -1 : ptr._obj.find(name); if( idx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); - int alias = START._aliasStarts.get(ptr._obj._name)+idx; + int alias = _aliases.get(ptr._obj._name)+idx; if( match("=") ) { // Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment if( peek('=') ) _lexer._position--; else { Node val = parseExpression(); - memAlias(alias, new StoreNode(name, alias, ctrl(), memAlias(alias), expr, val).peephole()); + store(name,alias,expr,val); return expr; // "obj.a = expr" returns the expression while updating memory } } Type declaredType = ptr._obj._fields[idx]._type; - return parsePostfix(new LoadNode(name, alias, declaredType, memAlias(alias), expr).peephole()); + return parsePostfix(new LoadNode(name, alias, declaredType, mem(), expr).peephole()); } /** diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java new file mode 100644 index 00000000..8d512f21 --- /dev/null +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java @@ -0,0 +1,237 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; +import java.util.BitSet; + +/** + * A Phi for bulk memory. It covers all aliases except {@link #_aliases}; + * those aliases must be represented by parallel precise MemPhis at the same + * program slice. + */ +public class BulkMemPhiNode extends PhiNode { + + private static final BitSet EMPTY = new BitSet(); + + // Excluded Aliases; empty means NO exclusions. + // Each split clones the exclusions; published sets are never mutated. + public final BitSet _aliases; + + public BulkMemPhiNode(String label, Node... inputs) { + this(label,EMPTY,inputs); + } + + private BulkMemPhiNode(String label, BitSet aliases, Node... inputs) { + super(label,TypeMem.BOT,inputs); + _aliases = aliases; + } + + public boolean isSplit(int alias) { return _aliases.get(alias); } + + @Override public String label() { return "BulkPhi"+_aliases; } + + @Override + public Type compute() { + Type t = super.compute(); + return t instanceof TypeMem mem ? mem : + t==Type.BOTTOM ? TypeMem.BOT : + TypeMem.TOP; + } + + @Override + public Node idealize() { + Node progress = super.idealize(); + if( progress != null ) return progress; + if( ((RegionNode)region()).inProgress() || region().nIns()<=1 ) + return null; // Input is in-progress + + // "Peek through" a MemMerge that covers this alias set on its default + for( int i=1; i= mmm.nIns() || mmm.in(alias)==null) ) + return false; + return true; + } + + + // True if the MemMerge has no precise slice still covered by this Phi. + private boolean canPeek(MemMergeNode mmm) { + return missingAlias(mmm,false)==0; + } + + // Return an alias required by an input but still covered by this Phi, or 0. + private int inputAlias(Node n) { + return switch(n) { + case ProjNode proj -> 0; + case ConstantNode con -> 0; + case MemMergeNode mmm -> missingAlias(mmm,false); + case MemOpNode mem -> unsplit(mem._alias); + case BulkMemPhiNode bulk -> missingAlias(bulk); + default -> throw new AssertionError("Unexpected memory input "+n); + }; + } + + // Return an alias required by a user but still covered by this Phi, or 0. + private int outputAlias(Node use) { + // This decision depends backwards on an immediate user's alias/set. + // Normal graph-neighbor enqueueing flows from defs to uses, so retain + // an explicit forward dependency to revisit this Phi when the user + // sharpens. + use.addDepForwards(this); + return switch(use) { + case ScopeNode scope -> 0; + case MemMergeNode mmm -> missingAlias(mmm,true); + case BulkMemPhiNode bulk -> missingAlias(bulk); + case MemOpNode mem -> unsplit(mem._alias); + case MemPhiNode phi -> unsplit(phi._alias); + default -> { + assert use instanceof ReturnNode + : "Unexpected bulk-memory user "+use; + yield 0; + } + }; + } + + // Alias zero/one is bulk, and an already excluded precise alias cannot + // trigger another split of this Phi. + private int unsplit(int alias) { + if( alias <= 1 ) return 0; + assert !_aliases.get(alias); + return alias; + } + + // First alias excluded by the neighboring bulk Phi but not by this one. + private int missingAlias(BulkMemPhiNode bulk) { + for( int alias = bulk._aliases.nextSetBit(0); alias >= 0; alias = bulk._aliases.nextSetBit(alias+1) ) + if( !_aliases.get(alias) ) + return alias; + return 0; + } + + // First precise MemMerge slice still covered by this Phi. When inspecting + // a user, ignore slots which point back to this Phi. + private int missingAlias(MemMergeNode mmm, boolean user) { + for( int alias=2; alias= 0; old = _aliases.nextSetBit(old+1) ) + { assert old != alias; mmm.alias(old,precisePhi(old));} + mmm.alias(alias,precise); + assert checkMerge(mmm); + return mmm; + } + + // Find or make the precise Phi parallel to this bulk Phi at the same merge. + private Node precisePhi(int alias) { + MemPhiNode mphi = _findPhi(alias); + if( mphi!=null ) return mphi; + + mphi = new MemPhiNode("$"+alias,alias); + mphi.addDef(region()); + // Due to cycles, must set before calling peephole + mphi.setType(TypeMem.make(alias)); + for( int i=1; i= 0; alias = bulk._aliases.nextSetBit(alias+1) ) + if( alias >= mmm.nIns() || mmm.in(alias)==null ) + return false; + return true; + } + + @Override public boolean eq(Node n) { + return _aliases.equals(((BulkMemPhiNode)n)._aliases) && super.eq(n); + } + + @Override int hash() { return _aliases.hashCode(); } +} 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 39bbaff1..d057e5c9 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.Field; @@ -38,10 +39,15 @@ public class LoadNode extends MemOpNode { @Override public Node idealize() { + if( mem() instanceof MemMergeNode merge ) { + setDef(1,IterPeeps.add(merge.alias(_alias))); + return this; + } + // Simple Load-after-Store on same address. if( mem() instanceof StoreNode st && - ptr() == st.ptr() ) { // Must check same object + ptr() == st.ptr() && _alias==st._alias ) { // Must check same object assert _name.equals(st._name); // Equiv class aliasing is perfect return st.val(); } @@ -53,7 +59,7 @@ public class LoadNode extends MemOpNode { // if( pred ) ptr.x = e0; val = pred ? e0 // else ptr.x = e1; : e1; // val = ptr.x; ptr.x = val; - if( mem() instanceof PhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 ) { + if( mem() instanceof MemPhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 ) { // Profit on RHS/Loop backedge if( profit(memphi,2) || // Else must not be a loop to count profit on LHS. @@ -70,6 +76,6 @@ public class LoadNode extends MemOpNode { // Profitable if we find a matching Store on this Phi arm. private boolean profit(PhiNode phi, int idx) { Node px = phi.in(idx); - return px!=null && px.addDep(this) instanceof StoreNode st1 && ptr()==st1.ptr(); + return px!=null && px.addDep(this) instanceof StoreNode st1 && ptr()==st1.ptr() && _alias==st1._alias; } } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java new file mode 100644 index 00000000..d7fed402 --- /dev/null +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -0,0 +1,60 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; +import java.util.BitSet; + +/** All memory: a default slice and explicit overrides for individual aliases. */ +public class MemMergeNode extends Node { + public MemMergeNode(Node bulk) { super(null,bulk); _type = TypeMem.BOT; } + public MemMergeNode(Node bulk, int alias, Node precise) { + this(bulk); + alias(alias,precise); + } + + public Node alias(int alias) { + Node n = alias < nIns() ? in(alias) : null; + assert n!=null || !(in(1) instanceof BulkMemPhiNode bulk) || !bulk.isSplit(alias); + return n==null ? in(1) : n; + } + + public void alias(int alias, Node mem) { + assert alias > 1; + while( nIns()<=alias ) addDef(null); + setDef(alias,mem); + } + + @Override public String label() { return "MemMerge"; } + @Override public boolean isMem() { return true; } + @Override public Type compute() { return TypeMem.BOT; } + @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { + sb.append("MEM["); + for( int i=1; i=nIns() || in(i)==null) ) + alias(i,mem.in(i)); + IterPeeps.add(mem.in(1)); + setDef(1,mem.in(1)); + return this; + } + assert BulkMemPhiNode.checkMerge(this); + return progress ? this : null; + } +} diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java new file mode 100644 index 00000000..c806bede --- /dev/null +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java @@ -0,0 +1,36 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; + +/** A Phi for one field alias, parallel to a bulk Phi at the same Region. */ +public class MemPhiNode extends PhiNode { + public final int _alias; + + public MemPhiNode(String label, int alias, Node... inputs) { + super(label,TypeMem.make(alias),inputs); + assert alias > 1; + _alias = alias; + } + + @Override public String label() { return "MemPhi_"+_alias; } + + @Override public Type compute() { + assert BulkMemPhiNode.checkMem(this,_alias); + Type t = super.compute(); + return t==Type.TOP || t==TypeMem.TOP ? TypeMem.TOP : TypeMem.make(_alias); + } + + @Override public Node idealize() { + for( int i=1; i(); if( Utils.find(_deps ,dep) != -1 ) return this; // Already on list - if( Utils.find(_inputs,dep) != -1 ) return this; // No need for deps on immediate neighbors - if( Utils.find(_outputs,dep)!= -1 ) return this; + if( !forwards && Utils.find(_inputs,dep) != -1 ) return this; + if( !forwards && Utils.find(_outputs,dep)!= -1 ) return this; _deps.add(dep); return this; } 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 52f098fa..bbd19795 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -16,6 +16,10 @@ public class PhiNode extends Node { public PhiNode(String label, Type declaredType, Node... inputs) { super(inputs); _label = label; assert declaredType!=null; _declaredType = declaredType; } + public static PhiNode make(String label, Type type, Node... inputs) { + return type instanceof TypeMem ? new BulkMemPhiNode(label,inputs) : new PhiNode(label,type,inputs); + } + @Override public String label() { return "Phi_"+_label; } @Override @@ -70,7 +74,7 @@ public class PhiNode extends Node { // Phi(op(A,B),op(Q,R),op(X,Y)) becomes // op(Phi(A,Q,X), Phi(B,R,Y)). Node op = in(1); - if( op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op() ) { + if( !isMem() && op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op() ) { Node[] lhss = new Node[nIns()]; Node[] rhss = new Node[nIns()]; lhss[0] = rhss[0] = in(0); // Set Region 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 444b76a8..725c704f 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -4,32 +4,17 @@ import com.seaofnodes.simple.type.*; import java.util.BitSet; -/** - * The Return node has two inputs. The first input is a control node and the - * second is the data node that supplies the return value. - *

- * In this presentation, Return functions as a Stop node, since multiple return statements are not possible. - * The Stop node will be introduced in Chapter 6 when we implement if statements. - *

- * The Return's output is the value from the data node. - */ +/** Keeps all preceding memory effects and the return value alive: {ctrl, $mem, value}. */ public class ReturnNode extends CFGNode { public ReturnNode(Node ctrl, Node data, ScopeNode scope) { - super(ctrl, data); - // We lookup memory slices by the naming convention that they start with $ - // We could also use implicit knowledge that all memory projects are at offset >= 2 - if( scope != null ) { - String[] names = scope.reverseNames(); - for (String name: names) { - if (!name.equals("$ctrl") && name.startsWith("$")) - addDef(scope.lookup(name)); - } - } + // A synthetic never-taken loop exit has no source scope. + super(ctrl, scope == null ? null : scope.lookup("$mem"), data); } public Node ctrl() { return in(0); } - public Node expr() { return in(1); } + public Node mem () { return in(1); } + public Node expr() { return in(2); } @Override public String label() { return "Return"; } @@ -43,7 +28,8 @@ public class ReturnNode extends CFGNode { @Override public Type compute() { - return TypeTuple.make(ctrl()._type,expr()._type); + // Return exposes the complete memory state. + return TypeTuple.make(ctrl()._type,TypeMem.BOT,expr()._type); } @Override diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 455f4b3a..b931e862 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -129,7 +129,7 @@ public class ScopeNode extends Node { // Set real Phi in the loop head // The phi takes its one input (no backedge yet) from a recursive // lookup, which might have insert a Phi in every loop nest. - : loop.setDef(idx,new PhiNode(name, lookupDeclaredType(name),loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole()); + : loop.setDef(idx,PhiNode.make(name, lookupDeclaredType(name),loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole()); setDef(idx,old); } return n==null ? old : setDef(idx,n); // Not lazy, so this is the answer @@ -207,7 +207,7 @@ public class ScopeNode extends Node { if( in(i) != that.in(i) ) // No need for redundant Phis // If we are in lazy phi mode we need to a lookup // by name as it will trigger a phi creation - setDef(i, new PhiNode(ns[i], this.lookupDeclaredType(ns[i]), r, this.lookup(ns[i]), that.lookup(ns[i])).peephole()); + setDef(i, PhiNode.make(ns[i], this.lookupDeclaredType(ns[i]), r, this.lookup(ns[i]), that.lookup(ns[i])).peephole()); that.kill(); // Kill merged scope IterPeeps.add(r); return r.unkeep().peephole(); 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 62fc8a6b..b4fa549b 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -1,59 +1,17 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.*; -import java.util.Arrays; import java.util.BitSet; -import java.util.HashMap; import java.util.HashSet; -/** - * The Start node represents the start of the function. - * - * Start initially has 1 input (arg) from outside and the initial control. - * In ch10 we also add mem aliases as structs get defined; each field in struct - * adds a distinct alias to Start's tuple. - */ +/** Start supplies control, whole memory, and the argument, in that order. */ public class StartNode extends CFGNode implements MultiNode { - // This field is NOT final, because the tuple expands as we add memory aliases - TypeTuple _args; - - // The alias number of the first field in the struct. - // - public final HashMap _aliasStarts; - + private final TypeTuple _args; public StartNode(Type[] args) { super(); - _args = TypeTuple.make(args); - _type = _args; - _aliasStarts = new HashMap<>(); - } - - /** - * Creates a projection for each of the struct's fields, using the field alias - * as the key. - */ - public void addMemProj( TypeStruct ts, ScopeNode scope) { - int len = _args._types.length; - _aliasStarts.put(ts._name,len); - - // resize the tuple's type array to include all fields of the struct - int max = len + ts._fields.length; - Type[] args = Arrays.copyOf(_args._types, max); - - // The new members of the tuple get a mem type with an alias - for( int alias = len; alias < max; alias++ ) - args[alias] = TypeMem.make(alias); _type = _args = TypeTuple.make(args); - // For each of the fields we now add a mem projection. Note that the - // alias matches the slot of the field in the tuple - for( int alias = len; alias < max; alias++ ) { - String name = Parser.memName(alias); - Node n = new ProjNode(this, alias, name).peephole(); - scope.define(name, args[alias], n); - } } @Override 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 5b30b3ec..b816762b 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.*; import java.util.BitSet; @@ -37,11 +38,16 @@ public class StoreNode extends MemOpNode { @Override public Node idealize() { + if( mem() instanceof MemMergeNode merge ) { + setDef(1,IterPeeps.add(merge.alias(_alias))); + return this; + } + // Simple store-after-store on same address. Should pick up the // required init-store being stomped by a first user store. if( mem() instanceof StoreNode st && - ptr()==st.ptr() && // Must check same object + ptr()==st.ptr() && _alias==st._alias && // Must check same object ptr()._type instanceof TypeMemPtr && // No bother if weird dead pointers // Must have exactly one use of "this" or you get weird // non-serializable memory effects in the worse case. diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter04Test.java index a3109ff7..14d31245 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -84,7 +84,10 @@ public class Chapter04Test { StopNode stop = parser.parse(); ReturnNode ret = stop.ret(); assertTrue(ret.in(0) instanceof CProjNode); - assertTrue(ret.in(1) instanceof ProjNode); + assertTrue(ret.in(1) instanceof ProjNode); + assertEquals(1, ((ProjNode)ret.in(1))._idx); + assertTrue(ret.in(2) instanceof ProjNode); + assertEquals(2, ((ProjNode)ret.in(2))._idx); } @Test diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 8d15493f..91efc3d6 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(Region20,(arg+2),(arg-3));", ret.toString()); + assertEquals("return Phi(Region21,(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(Region18,4,3);", ret.toString()); + assertEquals("return Phi(Region19,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(Region23,2,3));", ret.toString()); + assertEquals("return ((arg*2)+Phi(Region24,2,3));", ret.toString()); } @Test @@ -80,7 +80,7 @@ else a=b+1; return a+b;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return ((Phi(Region34,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString()); + assertEquals("return ((Phi(Region35,(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(Region38,Phi(Region24,2,3),Phi(Region36,4,5));", stop.toString()); + assertEquals("return Phi(Region39,Phi(Region25,2,3),Phi(Region37,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(Region15,1,0))+Phi(Region30,2,0));", stop.toString()); + assertEquals("return ((arg+Phi(Region16,1,0))+Phi(Region31,2,0));", stop.toString()); } @Test @@ -130,7 +130,7 @@ if( arg==1 ) } return a;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return (arg==Phi(Region18,3,2));", ret.toString()); + assertEquals("return (arg==Phi(Region19,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 7b11bc35..df0f2848 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -30,7 +30,7 @@ if (arg) return (arg < a) < 3; """); StopNode stop = parser.parse().iterate(); - assertEquals("return ((arg 0) { + s.x = s.x + 1; + int j = 3; + while (j > 0) { + j = j - 1; + if (j == 1) continue; + s.y = s.y + arg; + if (arg == 2) break; + s.z = s.z + 1; + } + arg = arg - 1; + } + return s; + """; + + @Test public void testMemoryAcrossNestedLoops() { + var stop = new Parser(NESTED_MEMORY).parse().iterate(); + for (int arg=0; arg<7; arg++) { + var obj = (com.seaofnodes.simple.evaluator.Evaluator.Obj) + com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,arg); + org.junit.Assert.assertArrayEquals(new Object[] { + 5L+arg, 7L+arg*(arg+1)-(arg>=2 ? 2 : 0), 11L+2*arg-(arg>=2 ? 2 : 0) + }, obj.fields()); + } + } + + @Test public void testMemoryAtEarlyReturns() { + var stop = new Parser(""" + struct S { int x; int y; int z; } + S s = new S; + s.x = 3; s.y = 5; s.z = 7; + if (arg) { s.x = 11; s.z = 13; return s; } + s.y = 17; + return s; + """).parse().iterate(); + for (int arg=0; arg<2; arg++) { + var obj = (com.seaofnodes.simple.evaluator.Evaluator.Obj) + com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,arg); + org.junit.Assert.assertArrayEquals(arg==0 ? new Object[]{3L,17L,7L} : new Object[]{11L,5L,13L}, obj.fields()); + } + } } diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter10bTest.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter10bTest.java new file mode 100644 index 00000000..6f094cfb --- /dev/null +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter10bTest.java @@ -0,0 +1,64 @@ +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=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 3e03d1f7..4c2b42f1 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -326,7 +326,7 @@ while( prime <= arg ) { return primeCount; """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 0; return Phi(Loop19,1,Phi(Region81,Phi_primeCount,Phi(Region76,(Phi_primeCount+1),Phi_primeCount))); ]", stop.toString()); + assertEquals("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 @@ -368,7 +368,7 @@ if (arg) { return i; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region31,.f,0);", stop.toString()); + assertEquals("return Phi(Region34,.f,0);", stop.toString()); } @Test @@ -474,7 +474,7 @@ while(arg) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop13,arg,Phi(Region35,.f,0));", stop.toString()); + assertEquals("return Phi(Loop15,arg,Phi(Region39,.f,0));", stop.toString()); } @Test @@ -525,7 +525,7 @@ else if (arg == 1) s.f = 1; return s.f; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region35,1,Phi(Region33,1,0));", stop.toString()); + assertEquals("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)); 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 4a405a3b..355d906b 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -138,6 +138,7 @@ public class Evaluator { case CastNode cast -> val(cast.in(1)); case LoadNode load -> load(load); 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]; @@ -151,8 +152,8 @@ public class Evaluator { public Object evaluate(long parameter, int loops) { if (start == null) return Status.TIMEOUT; var s = new Object[start.compute()._types.length]; - s[1] = parameter; - for(int i=2;id.users++); + if (out instanceof LoadNode l && l._alias==((StoreNode)node)._alias) + od(out).ifPresent(d->d.users++); } } } -- cgit v1.2.3