From e4dc3273f201ae741637b626998637cce973546b Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 2 Oct 2026 13:04:34 -0700 Subject: First pass README updates --- chapter11/README.md | 26 +- chapter11/docs/Makefile | 15 +- chapter11/docs/graph1.json | 33 ++ chapter11/docs/graph1.svg | 457 +++++++++------------------- chapter11/docs/graph2.json | 33 ++ chapter11/docs/graph2.svg | 486 +++++++++-------------------- chapter11/docs/graph3-snip.json | 20 ++ chapter11/docs/graph3-snip.svg | 102 +++++++ chapter11/docs/graph3.json | 33 ++ chapter11/docs/graph3.svg | 500 +++++++++--------------------- chapter11/docs/graph4.json | 42 +++ chapter11/docs/graph4.svg | 616 ++++++++++++------------------------- chapter11/docs/graph5.json | 42 +++ chapter11/docs/graph5.svg | 659 ++++++++++++---------------------------- chapter11/docs/graph6.json | 42 +++ chapter11/docs/graph6.svg | 658 ++++++++++++--------------------------- chapter11/docs/graph7.json | 16 + chapter11/docs/graph7.svg | 132 ++++---- chapter11/docs/graph8.json | 21 ++ chapter11/docs/graph8.svg | 213 ++++++------- 20 files changed, 1590 insertions(+), 2556 deletions(-) create mode 100644 chapter11/docs/graph1.json create mode 100644 chapter11/docs/graph2.json create mode 100644 chapter11/docs/graph3-snip.json create mode 100644 chapter11/docs/graph3-snip.svg create mode 100644 chapter11/docs/graph3.json create mode 100644 chapter11/docs/graph4.json create mode 100644 chapter11/docs/graph5.json create mode 100644 chapter11/docs/graph6.json create mode 100644 chapter11/docs/graph7.json create mode 100644 chapter11/docs/graph8.json (limited to 'chapter11') diff --git a/chapter11/README.md b/chapter11/README.md index b91f4fd7..58adbbfb 100644 --- a/chapter11/README.md +++ b/chapter11/README.md @@ -1,5 +1,8 @@ # Chapter 11: Global Code Motion +[Previous: Chapter 10b](../chapter10b/README.md) | +[Next: Chapter 12](../chapter12/README.md) + 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 @@ -20,7 +23,7 @@ their Region, just like scalar Phis. 1. [High Level Overview](#high-level-overview) 2. [Scheduling Walk Through](#scheduling-walk-through) 3. [Scheduling a Loop](#scheduling-a-loop) -4. [Components of the Global Code Motion Algorithm ](#components-of-the-global-code-motion-algorithm) +4. [Components of the Global Code Motion Algorithm](#components-of-the-global-code-motion-algorithm) 5. [Identification of Basic Blocks in SoN graph](#identification-of-basic-blocks-in-son-graph) 6. [Handling Infinite Loops](#handling-infinite-loops) 7. [Dominators](#dominators) @@ -30,13 +33,12 @@ their Region, just like scalar Phis. 11. [Inserting Anti Dependencies](#inserting-anti-dependencies) 12. [Video Walk Through](#video-walk-through) - You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter11) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter10b...linear-chapter11) it to the previous chapter. The original input source program defines a sequence in which things happen. As we parse the program into Sea of Nodes representation and perform various optimizations, this sequence is not fully maintained. The optimized Sea of Nodes graph is driven more -by dependencies between nodes rather that the sequence of instructions in the original source program. +by dependencies between nodes rather than the sequence of instructions in the original source program. Our goal in this chapter is to look at how we can recover a schedule for executing instructions from an optimized Sea of Nodes graph. This schedule needs to preserve the semantics of the original source program, @@ -85,7 +87,7 @@ if (arg) v.f=1; return i; ``` -First lets look at the graph before scheduling. +First let's 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; @@ -100,13 +102,13 @@ Observe that * Ditto for Phi nodes which are attached to the Region nodes. * So what remains are the "floating" Data nodes that do not have a control input at this stage. In this example, these are the load `.f` and store `.f=` nodes. -Now, lets look at the graph after we run the early schedule. +Now, let's look at the graph after we run the early schedule. ![Graph2](./docs/graph2.svg) * Observe that the load `.f` and the stores `.f=` now have control edges to the `$ctrl` projection from Start. Thus, the early schedule has put the Data nodes in the first basic block. -* This is because the inputs to these nodes are have the `$ctrl` projection as the immediate dominator. +* This is because the inputs to these nodes have the `$ctrl` projection as the immediate dominator. The graph below shows the schedule post late scheduling. @@ -114,7 +116,7 @@ The graph below shows the schedule post late scheduling. The snip below shows the main changes in the graph: -![Graph3-snip](./docs/graph3-snip.jpg) +![Store ordered after the earlier load](./docs/graph3-snip.svg) * The store `.f=` now has an anti-dependency on the load `.f`; this ensures that the store is scheduled after the load, as required by program semantics. We discuss anti-dependencies in detail later. * Observe also that the store `.f=` is now bound to the True branch of the If node. @@ -168,7 +170,7 @@ We have already alluded to several components of the GCM algorithm in passing ab ## Identification of Basic Blocks in SoN graph -The Sea of Nodes graph already captures the programs control flow graph. This information is implicit in the control nodes and edges from control nodes to other types of nodes. +The Sea of Nodes graph already captures the program's control flow graph. This information is implicit in the control nodes and edges from control nodes to other types of nodes. To recap, Control starts at the Start node, via a projection that is bound to the name `$ctrl`. As the control flows in the program, this name binding gets updated, and control is passed around, until it reaches the Stop node. @@ -204,7 +206,7 @@ while (1) {} return 0; ``` -First lets look at the graph resulting from this: +First let's look at the graph resulting from this: ![Graph7](./docs/graph7.svg) @@ -218,7 +220,7 @@ The implementation is in the Loop node: // 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 + // Walk the backedge, then immediate dominator tree until 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(); @@ -332,7 +334,7 @@ class StopNode extends CFGNode { Simple's Sea of Nodes graph identifies loops explicitly via Loop nodes. Since the language provides a single way to create a loop, using the `while` statement, it is not necessary to implement a generic loop discovery process. -We do however need to compute a loop depth. This is done similar to how we compute the dominator depth. +We do however need to compute a loop depth. This is done similarly to how we compute the dominator depth. ```java class CFGNode { @@ -374,7 +376,7 @@ class StopNode extends CFGNode { ## Early Schedule -The GCM algorithm proper starts with the computation of the early schedule, during which do an upward DFS walk on the "inputs" of each Node, starting from the bottom (Stop). We schedule each data node to the +The GCM algorithm proper starts with the computation of the early schedule, during which 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. A pre-condition of this is to ensure that infinite loops have been "fixed" as described earlier. diff --git a/chapter11/docs/Makefile b/chapter11/docs/Makefile index 055882b2..6fa0f057 100644 --- a/chapter11/docs/Makefile +++ b/chapter11/docs/Makefile @@ -1,14 +1 @@ -GV := $(wildcard *.gv) -SVG := $(patsubst %.gv,%.svg,$(GV)) -.DELETE_ON_ERROR: - -.PHONY: all -all: $(SVG) - -%.svg: %.gv - dot -Tsvg $< > $@ - @sed -i 's/\r$$//' $@ - -.PHONY: clean -clean: - @rm -f $(SVG) +include ../../graph/docs.mk diff --git a/chapter11/docs/graph1.json b/chapter11/docs/graph1.json new file mode 100644 index 00000000..748bdae9 --- /dev/null +++ b/chapter11/docs/graph1.json @@ -0,0 +1,33 @@ +{ + "ver": 1, + "comp": "chapter11/docs/graph1.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 224, "role": "MEM", "label": null}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 5, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 6, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 2, "role": "MEM", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 7, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 2}}, + {"id": 8, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 17, "role": "CTRL", "label": null}], "proj": {"par": 17, "idx": 0}}, + {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}], "proj": null}, + {"id": 10, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 17, "role": "CTRL", "label": null}], "proj": {"par": 17, "idx": 1}}, + {"id": 11, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 12, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 11, "role": "DATA", "label": null}], "proj": null}, + {"id": 13, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}], "proj": null}, + {"id": 14, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 12, "role": "MEM", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 16, "label": ".f", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 21, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 22, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 21, "role": "DATA", "label": null}], "proj": null}, + {"id": 23, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 8, "role": "CTRL", "label": null}, {"idx": 2, "def": 10, "role": "CTRL", "label": null}], "proj": null}, + {"id": 25, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 23, "role": "CTRL", "label": null}, {"idx": 1, "def": 1, "role": "MEM", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 224, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 23, "role": "ASSOC", "label": null}, {"idx": 1, "def": 22, "role": "MEM", "label": null}, {"idx": 2, "def": 14, "role": "MEM", "label": null}], "proj": null} + ], + "groups": [ + {"id": 17, "par": 0, "nodes": [8, 10, 17, 22, 23, 224]} + ] +} diff --git a/chapter11/docs/graph1.svg b/chapter11/docs/graph1.svg index 422d790e..ef4d0293 100644 --- a/chapter11/docs/graph1.svg +++ b/chapter11/docs/graph1.svg @@ -1,306 +1,151 @@ - - - - - - -chapter11 - - -cluster_Nodes - - - - -Start2 - - -Start - - - -$ctrl - -$mem - -arg - - - -MemMerge - -MemMerge - - - -MemMerge->Start2:p1 - - -1 - - - -Phi_224 - -MemPhi_2 - - - -MemMerge->Phi_224 - - -2 - - - -Stop3 - -Stop - - - -Return25 - -Return - - - -Stop3->Return25 - - -0 - - - -Con_4 - -#0 - - - -new9 - -new S - - - -new9->Start2:p0 - - -0 - - - -Con_11 - -#2 - - - -Store12 - -.f = - - - -Store12->Start2:p1 - - -1 - - - -Store12->new9 - - -2 - - - -Store12->Con_11 - - -3 - - - -new13 - -new S - - - -new13->Start2:p0 - - -0 - - - -Store14 - -.f = - - - -Store14->Con_4 - - -3 - - - -Store14->Store12 - - -1 - - - -Store14->new13 - - -2 - - - -Load16 - -.f - - - -Load16->new9 - - - -2 - - - -Load16->Store14 - - -1 - - - -If17 - - -If - - - -True - - -False - - - -If17->Start2:p0 - - - -0 - - - -If17->Start2:p2 - - -1 - - - -Con_21 - -#1 - - - -Store22 - -.f = - - - -Store22->new9 - -2 - - - -Store22->Store14 - - -1 - - - -Store22->Con_21 - - -3 - - - -Region23 - -Region - - - -Region23->If17:p0 - - -1 - - - -Phi_224->Store14 - - -2 - - - -Phi_224->Store22 - - -1 - - - -Phi_224->Region23 - - -0 - - - -Return25->MemMerge - - -1 - - - -Return25->Load16 - - -2 - - - -Return25->Region23 - - -0 - - - +#1[1] → #6 · MEM#1[2] → #224 · MEM#3[0] → #25 · CTRL#9[0] → #5 · CTRL#12[1] → #6 · MEM#12[2] → #9 · DATA#12[3] → #11 · DATA#13[0] → #5 · CTRL#14[1] → #12 · MEM#14[2] → #13 · DATA#14[3] → #4 · DATA#16[1] → #14 · MEM#16[2] → #9 · DATA#17[0] → #5 · CTRL#17[1] → #7 · DATA#22[1] → #14 · MEM#22[2] → #9 · DATA#22[3] → #21 · DATA#23[1] → #8 · CTRL#23[2] → #10 · CTRL#25[0] → #23 · CTRL#25[1] → #1 · MEM#25[2] → #16 · DATA#224[1] → #22 · MEM#224[2] → #14 · MEMMemMerge  #1#1 MemMerge +Type not computed + +[0] → — DATA +[1] → #6 MEM +[2] → #224 MEM012Start  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #25 CTRL0#0  #4#4 #0 +Type not computed + +$ctrl  #5/0#5 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRL$mem  #6/1#6 $mem +Projection 1 of #2 +Type not computed + +[0] → #2 MEMarg  #7/2#7 arg +Projection 2 of #2 +Type not computed + +[0] → #2 DATATrue  #8/0#8 True +Projection 0 of #17 +Type not computed + +[0] → #17 CTRLnew S  #9#9 new S +Type not computed + +[0] → #5 CTRL0False  #10/1#10 False +Projection 1 of #17 +Type not computed + +[0] → #17 CTRL#2  #11#11 #2 +Type not computed + +.f =  #12#12 .f = +Type not computed + +[0] → — DATA +[1] → #6 MEM +[2] → #9 DATA +[3] → #11 DATA0123new S  #13#13 new S +Type not computed + +[0] → #5 CTRL0.f =  #14#14 .f = +Type not computed + +[0] → — DATA +[1] → #12 MEM +[2] → #13 DATA +[3] → #4 DATA0123.f  #16#16 .f +Type not computed + +[0] → — DATA +[1] → #14 MEM +[2] → #9 DATA012If  #17#17 If +Type not computed + +[0] → #5 CTRL +[1] → #7 DATA01#1  #21#21 #1 +Type not computed + +.f =  #22#22 .f = +Type not computed + +[0] → — DATA +[1] → #14 MEM +[2] → #9 DATA +[3] → #21 DATA0123Region  #23#23 Region +Type not computed + +[0] → — DATA +[1] → #8 CTRL +[2] → #10 CTRL012Return  #25#25 Return +Type not computed + +[0] → #23 CTRL +[1] → #1 MEM +[2] → #16 DATA012MemPhi_2  #224#224 MemPhi_2 +Type not computed + +[0] → #23 ASSOC +[1] → #22 MEM +[2] → #14 MEM[0] → #23012If  #17If · 6 nodes−Fold region diff --git a/chapter11/docs/graph2.json b/chapter11/docs/graph2.json new file mode 100644 index 00000000..7c50307d --- /dev/null +++ b/chapter11/docs/graph2.json @@ -0,0 +1,33 @@ +{ + "ver": 1, + "comp": "chapter11/docs/graph2.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 23, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 224, "role": "MEM", "label": null}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 5, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 6, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 2, "role": "MEM", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 7, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 2}}, + {"id": 8, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 17, "role": "CTRL", "label": null}], "proj": {"par": 17, "idx": 0}}, + {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}], "proj": null}, + {"id": 10, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 17, "role": "CTRL", "label": null}], "proj": {"par": 17, "idx": 1}}, + {"id": 11, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 12, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 11, "role": "DATA", "label": null}], "proj": null}, + {"id": 13, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}], "proj": null}, + {"id": 14, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 12, "role": "MEM", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 16, "label": ".f", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 21, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 22, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 21, "role": "DATA", "label": null}], "proj": null}, + {"id": 23, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 8, "role": "CTRL", "label": null}, {"idx": 2, "def": 10, "role": "CTRL", "label": null}], "proj": null}, + {"id": 25, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 23, "role": "CTRL", "label": null}, {"idx": 1, "def": 1, "role": "MEM", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 224, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 23, "role": "ASSOC", "label": null}, {"idx": 1, "def": 22, "role": "MEM", "label": null}, {"idx": 2, "def": 14, "role": "MEM", "label": null}], "proj": null} + ], + "groups": [ + {"id": 17, "par": 0, "nodes": [1, 8, 10, 17, 23, 224]} + ] +} diff --git a/chapter11/docs/graph2.svg b/chapter11/docs/graph2.svg index b8d43cc9..a3afd14f 100644 --- a/chapter11/docs/graph2.svg +++ b/chapter11/docs/graph2.svg @@ -1,335 +1,151 @@ - - - - - - -chapter11 - - -cluster_Nodes - - - - -Start2 - - -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 - - - -Return25 - -Return - - - -Stop3->Return25 - - -0 - - - -Con_4 - -#0 - - - -new9 - -new S - - - -new9->Start2:p0 - - -0 - - - -Con_11 - -#2 - - - -Store12 - -.f = - - - -Store12->Start2:p0 - - - -0 - - - -Store12->new9 - - -2 - - - -Store12->Con_11 - - -3 - - - -new13 - -new S - - - -new13->Start2:p0 - - -0 - - - -Store14 - -.f = - - - -Store14->Start2:p0 - - -0 - - - -Store14->Con_4 - - -3 - - - -Store14->Store12 - - -1 - - - -Store14->new13 - - -2 - - - -Load16 - -.f - - - -Load16->Start2:p0 - - - -0 - - - -Load16->new9 - - - -2 - - - -Load16->Store14 - - -1 - - - -If17 - - -If - - - -True - - -False - - - -If17->Start2:p0 - -0 - - - -Con_21 - -#1 - - - -Store22 - -.f = - - - -Store22->Start2:p0 - - -0 - - - -Store22->new9 - -2 - - - -Store22->Store14 - - -1 - - - -Store22->Con_21 - - -3 - - - -Region23->If17:p0 - - -1 - - - -Region23->If17:p1 - - -2 - - - -Phi_224->Store14 - - -2 - - - -Phi_224->Store22 - - -1 - - - -Phi_224->Region23 - - -0 - - - -Return25->MemMerge - - -1 - - - -Return25->Load16 - - - -2 - - - -Return25->Region23 - - -0 - - - +#1[0] → #23 · CTRL#1[1] → #6 · MEM#1[2] → #224 · MEM#3[0] → #25 · CTRL#9[0] → #5 · CTRL#12[0] → #5 · CTRL#12[1] → #6 · MEM#12[2] → #9 · DATA#12[3] → #11 · DATA#13[0] → #5 · CTRL#14[0] → #5 · CTRL#14[1] → #12 · MEM#14[2] → #13 · DATA#14[3] → #4 · DATA#16[0] → #5 · CTRL#16[1] → #14 · MEM#16[2] → #9 · DATA#17[0] → #5 · CTRL#17[1] → #7 · DATA#22[0] → #5 · CTRL#22[1] → #14 · MEM#22[2] → #9 · DATA#22[3] → #21 · DATA#23[1] → #8 · CTRL#23[2] → #10 · CTRL#25[0] → #23 · CTRL#25[1] → #1 · MEM#25[2] → #16 · DATA#224[1] → #22 · MEM#224[2] → #14 · MEMMemMerge  #1#1 MemMerge +Type not computed + +[0] → #23 CTRL +[1] → #6 MEM +[2] → #224 MEM012Start  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #25 CTRL0#0  #4#4 #0 +Type not computed + +$ctrl  #5/0#5 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRL$mem  #6/1#6 $mem +Projection 1 of #2 +Type not computed + +[0] → #2 MEMarg  #7/2#7 arg +Projection 2 of #2 +Type not computed + +[0] → #2 DATATrue  #8/0#8 True +Projection 0 of #17 +Type not computed + +[0] → #17 CTRLnew S  #9#9 new S +Type not computed + +[0] → #5 CTRL0False  #10/1#10 False +Projection 1 of #17 +Type not computed + +[0] → #17 CTRL#2  #11#11 #2 +Type not computed + +.f =  #12#12 .f = +Type not computed + +[0] → #5 CTRL +[1] → #6 MEM +[2] → #9 DATA +[3] → #11 DATA0123new S  #13#13 new S +Type not computed + +[0] → #5 CTRL0.f =  #14#14 .f = +Type not computed + +[0] → #5 CTRL +[1] → #12 MEM +[2] → #13 DATA +[3] → #4 DATA0123.f  #16#16 .f +Type not computed + +[0] → #5 CTRL +[1] → #14 MEM +[2] → #9 DATA012If  #17#17 If +Type not computed + +[0] → #5 CTRL +[1] → #7 DATA01#1  #21#21 #1 +Type not computed + +.f =  #22#22 .f = +Type not computed + +[0] → #5 CTRL +[1] → #14 MEM +[2] → #9 DATA +[3] → #21 DATA0123Region  #23#23 Region +Type not computed + +[0] → — DATA +[1] → #8 CTRL +[2] → #10 CTRL012Return  #25#25 Return +Type not computed + +[0] → #23 CTRL +[1] → #1 MEM +[2] → #16 DATA012MemPhi_2  #224#224 MemPhi_2 +Type not computed + +[0] → #23 ASSOC +[1] → #22 MEM +[2] → #14 MEM[0] → #23012If  #17If · 6 nodes−Fold region diff --git a/chapter11/docs/graph3-snip.json b/chapter11/docs/graph3-snip.json new file mode 100644 index 00000000..00b3e744 --- /dev/null +++ b/chapter11/docs/graph3-snip.json @@ -0,0 +1,20 @@ +{ + "ver": 1, + "comp": "chapter11/docs/graph3-snip.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 5, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 8, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 17, "role": "CTRL", "label": null}], "proj": {"par": 17, "idx": 0}}, + {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}], "proj": null}, + {"id": 14, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 0, "role": "MEM", "label": null}, {"idx": 2, "def": 0, "role": "DATA", "label": null}, {"idx": 3, "def": 0, "role": "DATA", "label": null}], "proj": null}, + {"id": 16, "label": ".f", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 0, "role": "DATA", "label": null}], "proj": null}, + {"id": 21, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 22, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 21, "role": "DATA", "label": null}, {"idx": 4, "def": 16, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/chapter11/docs/graph3-snip.svg b/chapter11/docs/graph3-snip.svg new file mode 100644 index 00000000..cf6420c5 --- /dev/null +++ b/chapter11/docs/graph3-snip.svg @@ -0,0 +1,102 @@ +#9[0] → #5 · CTRL#14[0] → #5 · CTRL#16[0] → #5 · CTRL#16[1] → #14 · MEM#16[2] → #9 · DATA#17[0] → #5 · CTRL#22[0] → #8 · CTRL#22[1] → #14 · MEM#22[2] → #9 · DATA#22[3] → #21 · DATA#22[4] → #16 · DATAStart  #2#2 Start +Type not computed + +$ctrl  #5/0#5 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLTrue  #8/0#8 True +Projection 0 of #17 +Type not computed + +[0] → #17 CTRLnew S  #9#9 new S +Type not computed + +[0] → #5 CTRL0.f =  #14#14 .f = +Type not computed + +[0] → #5 CTRL +[1] → — MEM +[2] → — DATA +[3] → — DATA0123.f  #16#16 .f +Type not computed + +[0] → #5 CTRL +[1] → #14 MEM +[2] → #9 DATA012If  #17#17 If +Type not computed + +[0] → #5 CTRL +[1] → — DATA01#1  #21#21 #1 +Type not computed + +.f =  #22#22 .f = +Type not computed + +[0] → #8 CTRL +[1] → #14 MEM +[2] → #9 DATA +[3] → #21 DATA +[4] → #16 DATA01234 diff --git a/chapter11/docs/graph3.json b/chapter11/docs/graph3.json new file mode 100644 index 00000000..998c6f87 --- /dev/null +++ b/chapter11/docs/graph3.json @@ -0,0 +1,33 @@ +{ + "ver": 1, + "comp": "chapter11/docs/graph3.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 23, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 224, "role": "MEM", "label": null}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 5, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 6, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 2, "role": "MEM", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 7, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 2}}, + {"id": 8, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 17, "role": "CTRL", "label": null}], "proj": {"par": 17, "idx": 0}}, + {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}], "proj": null}, + {"id": 10, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 17, "role": "CTRL", "label": null}], "proj": {"par": 17, "idx": 1}}, + {"id": 11, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 12, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 11, "role": "DATA", "label": null}], "proj": null}, + {"id": 13, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}], "proj": null}, + {"id": 14, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 12, "role": "MEM", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 16, "label": ".f", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 21, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 22, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 21, "role": "DATA", "label": null}, {"idx": 4, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 23, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 8, "role": "CTRL", "label": null}, {"idx": 2, "def": 10, "role": "CTRL", "label": null}], "proj": null}, + {"id": 25, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 23, "role": "CTRL", "label": null}, {"idx": 1, "def": 1, "role": "MEM", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 224, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 23, "role": "ASSOC", "label": null}, {"idx": 1, "def": 22, "role": "MEM", "label": null}, {"idx": 2, "def": 14, "role": "MEM", "label": null}], "proj": null} + ], + "groups": [ + {"id": 17, "par": 0, "nodes": [1, 8, 10, 17, 22, 23, 224]} + ] +} diff --git a/chapter11/docs/graph3.svg b/chapter11/docs/graph3.svg index a16a1733..6fe5fe73 100644 --- a/chapter11/docs/graph3.svg +++ b/chapter11/docs/graph3.svg @@ -1,348 +1,152 @@ - - - - - - -chapter11 - - -cluster_Nodes - - - - -Start2 - - -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 - - - -Return25 - -Return - - - -Stop3->Return25 - - -0 - - - -Con_4 - -#0 - - - -new9 - -new S - - - -new9->Start2:p0 - - -0 - - - -Con_11 - -#2 - - - -Store12 - -.f = - - - -Store12->Start2:p0 - - - -0 - - - -Store12->new9 - - -2 - - - -Store12->Con_11 - - -3 - - - -new13 - -new S - - - -new13->Start2:p0 - - -0 - - - -Store14 - -.f = - - - -Store14->Start2:p0 - -0 - - - -Store14->Con_4 - - -3 - - - -Store14->Store12 - - -1 - - - -Store14->new13 - - -2 - - - -Load16 - -.f - - - -Load16->Start2:p0 - - - -0 - - - -Load16->new9 - - -2 - - - -Load16->Store14 - - -1 - - - -If17 - - -If - - - -True - - -False - - - -If17->Start2:p0 - - -0 - - - -If17->Start2:p2 - - -1 - - - -Con_21 - -#1 - - - -Store22 - -.f = - - - -Store22->new9 - - -2 - - - -Store22->Store14 - - -1 - - - -Store22->Load16 - - -4 - - - -Store22->If17:p0 - - -0 - - - -Store22->Con_21 - - -3 - - - -Region23->If17:p0 - - -1 - - - -Region23->If17:p1 - - -2 - - - -Phi_224->Store14 - - -2 - - - -Phi_224->Store22 - - -1 - - - -Phi_224->Region23 - - -0 - - - -Return25->MemMerge - - -1 - - - -Return25->Load16 - - -2 - - - -Return25->Region23 - - -0 - - - +#1[0] → #23 · CTRL#1[1] → #6 · MEM#1[2] → #224 · MEM#3[0] → #25 · CTRL#9[0] → #5 · CTRL#12[0] → #5 · CTRL#12[1] → #6 · MEM#12[2] → #9 · DATA#12[3] → #11 · DATA#13[0] → #5 · CTRL#14[0] → #5 · CTRL#14[1] → #12 · MEM#14[2] → #13 · DATA#14[3] → #4 · DATA#16[0] → #5 · CTRL#16[1] → #14 · MEM#16[2] → #9 · DATA#17[0] → #5 · CTRL#17[1] → #7 · DATA#22[0] → #8 · CTRL#22[1] → #14 · MEM#22[2] → #9 · DATA#22[3] → #21 · DATA#22[4] → #16 · DATA#23[1] → #8 · CTRL#23[2] → #10 · CTRL#25[0] → #23 · CTRL#25[1] → #1 · MEM#25[2] → #16 · DATA#224[1] → #22 · MEM#224[2] → #14 · MEMMemMerge  #1#1 MemMerge +Type not computed + +[0] → #23 CTRL +[1] → #6 MEM +[2] → #224 MEM012Start  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #25 CTRL0#0  #4#4 #0 +Type not computed + +$ctrl  #5/0#5 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRL$mem  #6/1#6 $mem +Projection 1 of #2 +Type not computed + +[0] → #2 MEMarg  #7/2#7 arg +Projection 2 of #2 +Type not computed + +[0] → #2 DATATrue  #8/0#8 True +Projection 0 of #17 +Type not computed + +[0] → #17 CTRLnew S  #9#9 new S +Type not computed + +[0] → #5 CTRL0False  #10/1#10 False +Projection 1 of #17 +Type not computed + +[0] → #17 CTRL#2  #11#11 #2 +Type not computed + +.f =  #12#12 .f = +Type not computed + +[0] → #5 CTRL +[1] → #6 MEM +[2] → #9 DATA +[3] → #11 DATA0123new S  #13#13 new S +Type not computed + +[0] → #5 CTRL0.f =  #14#14 .f = +Type not computed + +[0] → #5 CTRL +[1] → #12 MEM +[2] → #13 DATA +[3] → #4 DATA0123.f  #16#16 .f +Type not computed + +[0] → #5 CTRL +[1] → #14 MEM +[2] → #9 DATA012If  #17#17 If +Type not computed + +[0] → #5 CTRL +[1] → #7 DATA01#1  #21#21 #1 +Type not computed + +.f =  #22#22 .f = +Type not computed + +[0] → #8 CTRL +[1] → #14 MEM +[2] → #9 DATA +[3] → #21 DATA +[4] → #16 DATA01234Region  #23#23 Region +Type not computed + +[0] → — DATA +[1] → #8 CTRL +[2] → #10 CTRL012Return  #25#25 Return +Type not computed + +[0] → #23 CTRL +[1] → #1 MEM +[2] → #16 DATA012MemPhi_2  #224#224 MemPhi_2 +Type not computed + +[0] → #23 ASSOC +[1] → #22 MEM +[2] → #14 MEM[0] → #23012If  #17If · 7 nodes−Fold region diff --git a/chapter11/docs/graph4.json b/chapter11/docs/graph4.json new file mode 100644 index 00000000..b021c03f --- /dev/null +++ b/chapter11/docs/graph4.json @@ -0,0 +1,42 @@ +{ + "ver": 1, + "comp": "chapter11/docs/graph4.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 230, "role": "MEM", "label": null}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 37, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 5, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 6, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 2, "role": "MEM", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 7, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 2}}, + {"id": 8, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 16, "role": "CTRL", "label": null}], "proj": {"par": 16, "idx": 0}}, + {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}], "proj": null}, + {"id": 10, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 11, "label": "Loop", "type": null, "kind": "LOOP", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 5, "role": "CTRL", "label": null}, {"idx": 2, "def": 32, "role": "CTRL", "label": null}], "proj": null}, + {"id": 12, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 16, "role": "CTRL", "label": null}], "proj": {"par": 16, "idx": 1}}, + {"id": 13, "label": "φ_arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 11, "role": "ASSOC", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}, {"idx": 2, "def": 35, "role": "DATA", "label": null}], "proj": null}, + {"id": 14, "label": "<", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}], "proj": null}, + {"id": 15, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": {"par": 25, "idx": 0}}, + {"id": 16, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": {"par": 25, "idx": 1}}, + {"id": 21, "label": "//", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}, {"idx": 2, "def": 22, "role": "DATA", "label": null}], "proj": null}, + {"id": 22, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 23, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 13, "role": "DATA", "label": null}, {"idx": 2, "def": 24, "role": "DATA", "label": null}], "proj": null}, + {"id": 24, "label": "#5", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 25, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}, {"idx": 1, "def": 23, "role": "DATA", "label": null}], "proj": null}, + {"id": 31, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 230, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 21, "role": "DATA", "label": null}], "proj": null}, + {"id": 32, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 15, "role": "CTRL", "label": null}, {"idx": 2, "def": 17, "role": "CTRL", "label": null}], "proj": null}, + {"id": 35, "label": "-", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 13, "role": "DATA", "label": null}, {"idx": 2, "def": 36, "role": "DATA", "label": null}], "proj": null}, + {"id": 36, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 37, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 12, "role": "CTRL", "label": null}, {"idx": 1, "def": 1, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 230, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 11, "role": "ASSOC", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 233, "role": "MEM", "label": null}], "proj": null}, + {"id": 233, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 32, "role": "ASSOC", "label": null}, {"idx": 1, "def": 31, "role": "MEM", "label": null}, {"idx": 2, "def": 230, "role": "MEM", "label": null}], "proj": null} + ], + "groups": [ + {"id": 11, "par": 0, "nodes": [8, 10, 11, 12, 13, 14, 16, 35, 230]}, + {"id": 25, "par": 11, "nodes": [15, 17, 21, 23, 25, 31, 32, 233]} + ] +} diff --git a/chapter11/docs/graph4.svg b/chapter11/docs/graph4.svg index 2730813a..c268b4e9 100644 --- a/chapter11/docs/graph4.svg +++ b/chapter11/docs/graph4.svg @@ -1,429 +1,187 @@ - - - - - - -chapter11 - - -cluster_Nodes - - - - -Start2 - - -Start - - - -$ctrl - -$mem - -arg - - - -MemMerge - -MemMerge - - - -MemMerge->Start2:p1 - - -1 - - - -Phi_230 - -MemPhi_2 - - - -MemMerge->Phi_230 - - -2 - - - -Stop3 - -Stop - - - -Return37 - -Return - - - -Stop3->Return37 - - -0 - - - -Con_4 - -#0 - - - -new9 - -new S - - - -new9->Start2:p0 - - -0 - - - -Store10 - -.f = - - - -Store10->Start2:p1 - - -1 - - - -Store10->Con_4 - - -3 - - - -Store10->new9 - - -2 - - - -Loop11 - -Loop - - - -Loop11->Start2:p0 - - -1 - - - -Region32 - -Region - - - -Loop11->Region32 - - -2 - - - -Phi_arg13 - -φ_arg - - - -Phi_arg13->Start2:p2 - - -1 - - - -Phi_arg13->Loop11 - - -0 - - - -Sub35 - -- - - - -LT14 - -< - - - -LT14->Con_4 - - -1 - - - -LT14->Phi_arg13 - - -2 - - - -If16 - - -If - - - -True - - -False - - - -If16->Loop11 - - -0 - - - -If16->LT14 - - -1 - - - -Div21 - -// - - - -Div21->Start2:p2 - - -1 - - - -Con_22 - -#3 - - - -Div21->Con_22 - - -2 - - - -EQ23 - -== - - - -EQ23->Phi_arg13 - - -1 - - - -Con_24 - -#5 - - - -EQ23->Con_24 - - -2 - - - -If25 - - -If - - - -True - - -False - - - -If25->If16:p0 - - -0 - - - -If25->EQ23 - - -1 - - - -Phi_230->Store10 - - -1 - - - -Phi_230->Loop11 - - -0 - - - -Phi_233 - -MemPhi_2 - - - -Store31 - -.f = - - - -Store31->new9 - - - -2 - - - -Store31->Div21 - - -3 - - - -Store31->Phi_230 - - -1 - - - -Region32->If25:p0 - - -1 - - - -Region32->If25:p1 - - -2 - - - -Phi_233->Phi_230 - - - -2 - - - -Phi_233->Store31 - - -1 - - - -Phi_233->Region32 - - -0 - - - -Sub35->Phi_arg13 - - - -1 - - - -Con_36 - -#1 - - - -Sub35->Con_36 - - -2 - - - -Return37->MemMerge - - -1 - - - -Return37->new9 - - -2 - - - -Return37->If16:p1 - - -0 - - - +#1[1] → #6 · MEM#1[2] → #230 · MEM#3[0] → #37 · CTRL#9[0] → #5 · CTRL#10[1] → #6 · MEM#10[2] → #9 · DATA#10[3] → #4 · DATA#11[1] → #5 · CTRL#11[2] → #32 · CTRL#13[1] → #7 · DATA#13[2] → #35 · DATA#14[1] → #4 · DATA#14[2] → #13 · DATA#16[0] → #11 · CTRL#16[1] → #14 · DATA#21[1] → #7 · DATA#21[2] → #22 · DATA#23[1] → #13 · DATA#23[2] → #24 · DATA#25[0] → #8 · CTRL#25[1] → #23 · DATA#31[1] → #230 · MEM#31[2] → #9 · DATA#31[3] → #21 · DATA#32[1] → #15 · CTRL#32[2] → #17 · CTRL#35[1] → #13 · DATA#35[2] → #36 · DATA#37[0] → #12 · CTRL#37[1] → #1 · MEM#37[2] → #9 · DATA#230[1] → #10 · MEM#230[2] → #233 · MEM#233[1] → #31 · MEM#233[2] → #230 · MEMMemMerge  #1#1 MemMerge +Type not computed + +[0] → — DATA +[1] → #6 MEM +[2] → #230 MEM012Start  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #37 CTRL0#0  #4#4 #0 +Type not computed + +$ctrl  #5/0#5 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRL$mem  #6/1#6 $mem +Projection 1 of #2 +Type not computed + +[0] → #2 MEMarg  #7/2#7 arg +Projection 2 of #2 +Type not computed + +[0] → #2 DATATrue  #8/0#8 True +Projection 0 of #16 +Type not computed + +[0] → #16 CTRLnew S  #9#9 new S +Type not computed + +[0] → #5 CTRL0.f =  #10#10 .f = +Type not computed + +[0] → — DATA +[1] → #6 MEM +[2] → #9 DATA +[3] → #4 DATA0123Loop  #11#11 Loop +Type not computed + +[0] → — DATA +[1] → #5 CTRL +[2] → #32 CTRL012False  #12/1#12 False +Projection 1 of #16 +Type not computed + +[0] → #16 CTRLφ_arg  #13#13 φ_arg +Type not computed + +[0] → #11 ASSOC +[1] → #7 DATA +[2] → #35 DATA[0] → #11012<  #14#14 < +Type not computed + +[0] → — DATA +[1] → #4 DATA +[2] → #13 DATA012True  #15/0#15 True +Projection 0 of #25 +Type not computed + +[0] → #25 CTRLIf  #16#16 If +Type not computed + +[0] → #11 CTRL +[1] → #14 DATA01False  #17/1#17 False +Projection 1 of #25 +Type not computed + +[0] → #25 CTRL//  #21#21 // +Type not computed + +[0] → — DATA +[1] → #7 DATA +[2] → #22 DATA012#3  #22#22 #3 +Type not computed + +==  #23#23 == +Type not computed + +[0] → — DATA +[1] → #13 DATA +[2] → #24 DATA012#5  #24#24 #5 +Type not computed + +If  #25#25 If +Type not computed + +[0] → #8 CTRL +[1] → #23 DATA01.f =  #31#31 .f = +Type not computed + +[0] → — DATA +[1] → #230 MEM +[2] → #9 DATA +[3] → #21 DATA0123Region  #32#32 Region +Type not computed + +[0] → — DATA +[1] → #15 CTRL +[2] → #17 CTRL012-  #35#35 - +Type not computed + +[0] → — DATA +[1] → #13 DATA +[2] → #36 DATA012#1  #36#36 #1 +Type not computed + +Return  #37#37 Return +Type not computed + +[0] → #12 CTRL +[1] → #1 MEM +[2] → #9 DATA012MemPhi_2  #230#230 MemPhi_2 +Type not computed + +[0] → #11 ASSOC +[1] → #10 MEM +[2] → #233 MEM[0] → #11012MemPhi_2  #233#233 MemPhi_2 +Type not computed + +[0] → #32 ASSOC +[1] → #31 MEM +[2] → #230 MEM[0] → #32012Loop  #11Loop · 17 nodes−Fold regionIf  #25If · 8 nodes−Fold region diff --git a/chapter11/docs/graph5.json b/chapter11/docs/graph5.json new file mode 100644 index 00000000..2211cb19 --- /dev/null +++ b/chapter11/docs/graph5.json @@ -0,0 +1,42 @@ +{ + "ver": 1, + "comp": "chapter11/docs/graph5.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 230, "role": "MEM", "label": null}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 37, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 5, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 6, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 2, "role": "MEM", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 7, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 2}}, + {"id": 8, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 16, "role": "CTRL", "label": null}], "proj": {"par": 16, "idx": 0}}, + {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}], "proj": null}, + {"id": 10, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 11, "label": "Loop", "type": null, "kind": "LOOP", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 5, "role": "CTRL", "label": null}, {"idx": 2, "def": 32, "role": "CTRL", "label": null}], "proj": null}, + {"id": 12, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 16, "role": "CTRL", "label": null}], "proj": {"par": 16, "idx": 1}}, + {"id": 13, "label": "φ_arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 11, "role": "ASSOC", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}, {"idx": 2, "def": 35, "role": "DATA", "label": null}], "proj": null}, + {"id": 14, "label": "<", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}], "proj": null}, + {"id": 15, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": {"par": 25, "idx": 0}}, + {"id": 16, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": {"par": 25, "idx": 1}}, + {"id": 21, "label": "//", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}, {"idx": 2, "def": 22, "role": "DATA", "label": null}], "proj": null}, + {"id": 22, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 23, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}, {"idx": 1, "def": 13, "role": "DATA", "label": null}, {"idx": 2, "def": 24, "role": "DATA", "label": null}], "proj": null}, + {"id": 24, "label": "#5", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 25, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}, {"idx": 1, "def": 23, "role": "DATA", "label": null}], "proj": null}, + {"id": 31, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}, {"idx": 1, "def": 230, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 21, "role": "DATA", "label": null}], "proj": null}, + {"id": 32, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 15, "role": "CTRL", "label": null}, {"idx": 2, "def": 17, "role": "CTRL", "label": null}], "proj": null}, + {"id": 35, "label": "-", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}, {"idx": 1, "def": 13, "role": "DATA", "label": null}, {"idx": 2, "def": 36, "role": "DATA", "label": null}], "proj": null}, + {"id": 36, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 37, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 12, "role": "CTRL", "label": null}, {"idx": 1, "def": 1, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 230, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 11, "role": "ASSOC", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 233, "role": "MEM", "label": null}], "proj": null}, + {"id": 233, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 32, "role": "ASSOC", "label": null}, {"idx": 1, "def": 31, "role": "MEM", "label": null}, {"idx": 2, "def": 230, "role": "MEM", "label": null}], "proj": null} + ], + "groups": [ + {"id": 11, "par": 0, "nodes": [1, 8, 11, 12, 13, 14, 16, 23, 31, 35, 230]}, + {"id": 25, "par": 11, "nodes": [15, 17, 25, 32, 233]} + ] +} diff --git a/chapter11/docs/graph5.svg b/chapter11/docs/graph5.svg index 9336ac3e..1669e008 100644 --- a/chapter11/docs/graph5.svg +++ b/chapter11/docs/graph5.svg @@ -1,472 +1,187 @@ - - - - - - -chapter11 - - -cluster_Nodes - - - - -Start2 - - -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 - - - -Return37 - -Return - - - -Stop3->Return37 - - -0 - - - -Con_4 - -#0 - - - -new9 - -new S - - - -new9->Start2:p0 - - -0 - - - -Store10 - -.f = - - - -Store10->Start2:p0 - - -0 - - - -Store10->Con_4 - - -3 - - - -Store10->new9 - - -2 - - - -Loop11->Start2:p0 - - -1 - - - -Region32 - -Region - - - -Loop11->Region32 - - -2 - - - -Phi_arg13 - -φ_arg - - - -Phi_arg13->Start2:p2 - - -1 - - - -Phi_arg13->Loop11 - - -0 - - - -Sub35 - -- - - - -LT14 - -< - - - -LT14->Con_4 - - -1 - - - -LT14->Loop11 - - -0 - - - -LT14->Phi_arg13 - - -2 - - - -If16 - - -If - - - -True - - -False - - - -If16->Loop11 - - -0 - - - -If16->LT14 - - -1 - - - -Div21 - -// - - - -Div21->Start2 - - -0 - - - -Div21->Start2:p2 - - -1 - - - -Con_22 - -#3 - - - -Div21->Con_22 - - -2 - - - -EQ23 - -== - - - -EQ23->Loop11 - - -0 - - - -EQ23->Phi_arg13 - - -1 - - - -Con_24 - -#5 - - - -EQ23->Con_24 - - -2 - - - -If25 - - -If - - - -True - - -False - - - -If25->If16:p0 - - -0 - - - -If25->EQ23 - - -1 - - - -Phi_230->Store10 - - -1 - - - -Phi_230->Loop11 - - -0 - - - -Phi_233 - -MemPhi_2 - - - -Store31 - -.f = - - - -Store31->new9 - - -2 - - - -Store31->Loop11 - - -0 - - - -Store31->Div21 - - - -3 - - - -Store31->Phi_230 - - -1 - - - -Region32->If25:p0 - - -1 - - - -Region32->If25:p1 - - -2 - - - -Phi_233->Phi_230 - - - -2 - - - -Phi_233->Store31 - - -1 - - - -Phi_233->Region32 - - -0 - - - -Sub35->Loop11 - - -0 - - - -Sub35->Phi_arg13 - - - -1 - - - -Con_36 - -#1 - - - -Sub35->Con_36 - - -2 - - - -Return37->MemMerge - - -1 - - - -Return37->new9 - - - -2 - - - -Return37->If16:p1 - - -0 - - - +#1[0] → #11 · CTRL#1[1] → #6 · MEM#1[2] → #230 · MEM#3[0] → #37 · CTRL#9[0] → #5 · CTRL#10[0] → #5 · CTRL#10[1] → #6 · MEM#10[2] → #9 · DATA#10[3] → #4 · DATA#11[1] → #5 · CTRL#11[2] → #32 · CTRL#13[1] → #7 · DATA#13[2] → #35 · DATA#14[0] → #11 · CTRL#14[1] → #4 · DATA#14[2] → #13 · DATA#16[0] → #11 · CTRL#16[1] → #14 · DATA#21[0] → #2 · CTRL#21[1] → #7 · DATA#21[2] → #22 · DATA#23[0] → #11 · CTRL#23[1] → #13 · DATA#23[2] → #24 · DATA#25[0] → #8 · CTRL#25[1] → #23 · DATA#31[0] → #11 · CTRL#31[1] → #230 · MEM#31[2] → #9 · DATA#31[3] → #21 · DATA#32[1] → #15 · CTRL#32[2] → #17 · CTRL#35[0] → #11 · CTRL#35[1] → #13 · DATA#35[2] → #36 · DATA#37[0] → #12 · CTRL#37[1] → #1 · MEM#37[2] → #9 · DATA#230[1] → #10 · MEM#230[2] → #233 · MEM#233[1] → #31 · MEM#233[2] → #230 · MEMMemMerge  #1#1 MemMerge +Type not computed + +[0] → #11 CTRL +[1] → #6 MEM +[2] → #230 MEM012Start  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #37 CTRL0#0  #4#4 #0 +Type not computed + +$ctrl  #5/0#5 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRL$mem  #6/1#6 $mem +Projection 1 of #2 +Type not computed + +[0] → #2 MEMarg  #7/2#7 arg +Projection 2 of #2 +Type not computed + +[0] → #2 DATATrue  #8/0#8 True +Projection 0 of #16 +Type not computed + +[0] → #16 CTRLnew S  #9#9 new S +Type not computed + +[0] → #5 CTRL0.f =  #10#10 .f = +Type not computed + +[0] → #5 CTRL +[1] → #6 MEM +[2] → #9 DATA +[3] → #4 DATA0123Loop  #11#11 Loop +Type not computed + +[0] → — DATA +[1] → #5 CTRL +[2] → #32 CTRL012False  #12/1#12 False +Projection 1 of #16 +Type not computed + +[0] → #16 CTRLφ_arg  #13#13 φ_arg +Type not computed + +[0] → #11 ASSOC +[1] → #7 DATA +[2] → #35 DATA[0] → #11012<  #14#14 < +Type not computed + +[0] → #11 CTRL +[1] → #4 DATA +[2] → #13 DATA012True  #15/0#15 True +Projection 0 of #25 +Type not computed + +[0] → #25 CTRLIf  #16#16 If +Type not computed + +[0] → #11 CTRL +[1] → #14 DATA01False  #17/1#17 False +Projection 1 of #25 +Type not computed + +[0] → #25 CTRL//  #21#21 // +Type not computed + +[0] → #2 CTRL +[1] → #7 DATA +[2] → #22 DATA012#3  #22#22 #3 +Type not computed + +==  #23#23 == +Type not computed + +[0] → #11 CTRL +[1] → #13 DATA +[2] → #24 DATA012#5  #24#24 #5 +Type not computed + +If  #25#25 If +Type not computed + +[0] → #8 CTRL +[1] → #23 DATA01.f =  #31#31 .f = +Type not computed + +[0] → #11 CTRL +[1] → #230 MEM +[2] → #9 DATA +[3] → #21 DATA0123Region  #32#32 Region +Type not computed + +[0] → — DATA +[1] → #15 CTRL +[2] → #17 CTRL012-  #35#35 - +Type not computed + +[0] → #11 CTRL +[1] → #13 DATA +[2] → #36 DATA012#1  #36#36 #1 +Type not computed + +Return  #37#37 Return +Type not computed + +[0] → #12 CTRL +[1] → #1 MEM +[2] → #9 DATA012MemPhi_2  #230#230 MemPhi_2 +Type not computed + +[0] → #11 ASSOC +[1] → #10 MEM +[2] → #233 MEM[0] → #11012MemPhi_2  #233#233 MemPhi_2 +Type not computed + +[0] → #32 ASSOC +[1] → #31 MEM +[2] → #230 MEM[0] → #32012Loop  #11Loop · 16 nodes−Fold regionIf  #25If · 5 nodes−Fold region diff --git a/chapter11/docs/graph6.json b/chapter11/docs/graph6.json new file mode 100644 index 00000000..1c08947a --- /dev/null +++ b/chapter11/docs/graph6.json @@ -0,0 +1,42 @@ +{ + "ver": 1, + "comp": "chapter11/docs/graph6.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 12, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 230, "role": "MEM", "label": null}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 37, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 5, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 6, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 2, "role": "MEM", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 7, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 2}}, + {"id": 8, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 16, "role": "CTRL", "label": null}], "proj": {"par": 16, "idx": 0}}, + {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}], "proj": null}, + {"id": 10, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 11, "label": "Loop", "type": null, "kind": "LOOP", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 5, "role": "CTRL", "label": null}, {"idx": 2, "def": 32, "role": "CTRL", "label": null}], "proj": null}, + {"id": 12, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 16, "role": "CTRL", "label": null}], "proj": {"par": 16, "idx": 1}}, + {"id": 13, "label": "φ_arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 11, "role": "ASSOC", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}, {"idx": 2, "def": 35, "role": "DATA", "label": null}], "proj": null}, + {"id": 14, "label": "<", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}], "proj": null}, + {"id": 15, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": {"par": 25, "idx": 0}}, + {"id": 16, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": {"par": 25, "idx": 1}}, + {"id": 21, "label": "//", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}, {"idx": 2, "def": 22, "role": "DATA", "label": null}], "proj": null}, + {"id": 22, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 23, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}, {"idx": 1, "def": 13, "role": "DATA", "label": null}, {"idx": 2, "def": 24, "role": "DATA", "label": null}], "proj": null}, + {"id": 24, "label": "#5", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 25, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}, {"idx": 1, "def": 23, "role": "DATA", "label": null}], "proj": null}, + {"id": 31, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 15, "role": "CTRL", "label": null}, {"idx": 1, "def": 230, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 21, "role": "DATA", "label": null}], "proj": null}, + {"id": 32, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 15, "role": "CTRL", "label": null}, {"idx": 2, "def": 17, "role": "CTRL", "label": null}], "proj": null}, + {"id": 35, "label": "-", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 32, "role": "CTRL", "label": null}, {"idx": 1, "def": 13, "role": "DATA", "label": null}, {"idx": 2, "def": 36, "role": "DATA", "label": null}], "proj": null}, + {"id": 36, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 37, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 12, "role": "CTRL", "label": null}, {"idx": 1, "def": 1, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 230, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 11, "role": "ASSOC", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 233, "role": "MEM", "label": null}], "proj": null}, + {"id": 233, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 32, "role": "ASSOC", "label": null}, {"idx": 1, "def": 31, "role": "MEM", "label": null}, {"idx": 2, "def": 230, "role": "MEM", "label": null}], "proj": null} + ], + "groups": [ + {"id": 11, "par": 0, "nodes": [8, 11, 12, 13, 14, 16, 23, 230]}, + {"id": 25, "par": 11, "nodes": [15, 17, 25, 31, 32, 35, 233]} + ] +} diff --git a/chapter11/docs/graph6.svg b/chapter11/docs/graph6.svg index 8b8bb190..8862f25c 100644 --- a/chapter11/docs/graph6.svg +++ b/chapter11/docs/graph6.svg @@ -1,471 +1,187 @@ - - - - - - -chapter11 - - -cluster_Nodes - - - - -Start2 - - -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 - - - -Return37 - -Return - - - -Stop3->Return37 - - -0 - - - -Con_4 - -#0 - - - -new9 - -new S - - - -new9->Start2:p0 - - -0 - - - -Store10 - -.f = - - - -Store10->Start2:p0 - - -0 - - - -Store10->Con_4 - - -3 - - - -Store10->new9 - - -2 - - - -Loop11 - -Loop - - - -Loop11->Start2:p0 - - -1 - - - -Region32 - -Region - - - -Loop11->Region32 - - -2 - - - -Phi_arg13 - -φ_arg - - - -Phi_arg13->Start2:p2 - - -1 - - - -Phi_arg13->Loop11 - - -0 - - - -Sub35 - -- - - - -LT14 - -< - - - -LT14->Con_4 - - -1 - - - -LT14->Loop11 - - -0 - - - -LT14->Phi_arg13 - - -2 - - - -If16->Loop11 - - -0 - - - -If16->LT14 - - -1 - - - -Div21 - -// - - - -Div21->Start2:p0 - - -0 - - - -Div21->Start2:p2 - - -1 - - - -Con_22 - -#3 - - - -Div21->Con_22 - - -2 - - - -EQ23 - -== - - - -EQ23->Phi_arg13 - - -1 - - - -EQ23->If16:p0 - - -0 - - - -Con_24 - -#5 - - - -EQ23->Con_24 - - -2 - - - -If25 - - -If - - - -True - - -False - - - -If25->If16:p0 - - -0 - - - -If25->EQ23 - - -1 - - - -Phi_230->Store10 - - -1 - - - -Phi_230->Loop11 - - -0 - - - -Phi_233 - -MemPhi_2 - - - -Store31 - -.f = - - - -Store31->new9 - - - - -2 - - - -Store31->Div21 - - -3 - - - -Store31->If25:p0 - - -0 - - - -Store31->Phi_230 - - - -1 - - - -Region32->If25:p0 - - -1 - - - -Region32->If25:p1 - - -2 - - - -Phi_233->Phi_230 - - - -2 - - - -Phi_233->Store31 - - -1 - - - -Phi_233->Region32 - - -0 - - - -Sub35->Phi_arg13 - - - -1 - - - -Sub35->Region32 - - -0 - - - -Con_36 - -#1 - - - -Sub35->Con_36 - - -2 - - - -Return37->MemMerge - - -1 - - - -Return37->new9 - -2 - - - -Return37->If16:p1 - - -0 - - - +#1[0] → #12 · CTRL#1[1] → #6 · MEM#1[2] → #230 · MEM#3[0] → #37 · CTRL#9[0] → #5 · CTRL#10[0] → #5 · CTRL#10[1] → #6 · MEM#10[2] → #9 · DATA#10[3] → #4 · DATA#11[1] → #5 · CTRL#11[2] → #32 · CTRL#13[1] → #7 · DATA#13[2] → #35 · DATA#14[0] → #11 · CTRL#14[1] → #4 · DATA#14[2] → #13 · DATA#16[0] → #11 · CTRL#16[1] → #14 · DATA#21[0] → #5 · CTRL#21[1] → #7 · DATA#21[2] → #22 · DATA#23[0] → #8 · CTRL#23[1] → #13 · DATA#23[2] → #24 · DATA#25[0] → #8 · CTRL#25[1] → #23 · DATA#31[0] → #15 · CTRL#31[1] → #230 · MEM#31[2] → #9 · DATA#31[3] → #21 · DATA#32[1] → #15 · CTRL#32[2] → #17 · CTRL#35[0] → #32 · CTRL#35[1] → #13 · DATA#35[2] → #36 · DATA#37[0] → #12 · CTRL#37[1] → #1 · MEM#37[2] → #9 · DATA#230[1] → #10 · MEM#230[2] → #233 · MEM#233[1] → #31 · MEM#233[2] → #230 · MEMMemMerge  #1#1 MemMerge +Type not computed + +[0] → #12 CTRL +[1] → #6 MEM +[2] → #230 MEM012Start  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #37 CTRL0#0  #4#4 #0 +Type not computed + +$ctrl  #5/0#5 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRL$mem  #6/1#6 $mem +Projection 1 of #2 +Type not computed + +[0] → #2 MEMarg  #7/2#7 arg +Projection 2 of #2 +Type not computed + +[0] → #2 DATATrue  #8/0#8 True +Projection 0 of #16 +Type not computed + +[0] → #16 CTRLnew S  #9#9 new S +Type not computed + +[0] → #5 CTRL0.f =  #10#10 .f = +Type not computed + +[0] → #5 CTRL +[1] → #6 MEM +[2] → #9 DATA +[3] → #4 DATA0123Loop  #11#11 Loop +Type not computed + +[0] → — DATA +[1] → #5 CTRL +[2] → #32 CTRL012False  #12/1#12 False +Projection 1 of #16 +Type not computed + +[0] → #16 CTRLφ_arg  #13#13 φ_arg +Type not computed + +[0] → #11 ASSOC +[1] → #7 DATA +[2] → #35 DATA[0] → #11012<  #14#14 < +Type not computed + +[0] → #11 CTRL +[1] → #4 DATA +[2] → #13 DATA012True  #15/0#15 True +Projection 0 of #25 +Type not computed + +[0] → #25 CTRLIf  #16#16 If +Type not computed + +[0] → #11 CTRL +[1] → #14 DATA01False  #17/1#17 False +Projection 1 of #25 +Type not computed + +[0] → #25 CTRL//  #21#21 // +Type not computed + +[0] → #5 CTRL +[1] → #7 DATA +[2] → #22 DATA012#3  #22#22 #3 +Type not computed + +==  #23#23 == +Type not computed + +[0] → #8 CTRL +[1] → #13 DATA +[2] → #24 DATA012#5  #24#24 #5 +Type not computed + +If  #25#25 If +Type not computed + +[0] → #8 CTRL +[1] → #23 DATA01.f =  #31#31 .f = +Type not computed + +[0] → #15 CTRL +[1] → #230 MEM +[2] → #9 DATA +[3] → #21 DATA0123Region  #32#32 Region +Type not computed + +[0] → — DATA +[1] → #15 CTRL +[2] → #17 CTRL012-  #35#35 - +Type not computed + +[0] → #32 CTRL +[1] → #13 DATA +[2] → #36 DATA012#1  #36#36 #1 +Type not computed + +Return  #37#37 Return +Type not computed + +[0] → #12 CTRL +[1] → #1 MEM +[2] → #9 DATA012MemPhi_2  #230#230 MemPhi_2 +Type not computed + +[0] → #11 ASSOC +[1] → #10 MEM +[2] → #233 MEM[0] → #11012MemPhi_2  #233#233 MemPhi_2 +Type not computed + +[0] → #32 ASSOC +[1] → #31 MEM +[2] → #230 MEM[0] → #32012Loop  #11Loop · 15 nodes−Fold regionIf  #25If · 7 nodes−Fold region diff --git a/chapter11/docs/graph7.json b/chapter11/docs/graph7.json new file mode 100644 index 00000000..c1c86b07 --- /dev/null +++ b/chapter11/docs/graph7.json @@ -0,0 +1,16 @@ +{ + "ver": 1, + "comp": "chapter11/docs/graph7.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 8, "label": "Loop", "type": null, "kind": "LOOP", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 1, "role": "CTRL", "label": null}, {"idx": 2, "def": 8, "role": "CTRL", "label": null}], "proj": null} + ], + "groups": [ + {"id": 8, "par": 0, "nodes": [8]} + ] +} diff --git a/chapter11/docs/graph7.svg b/chapter11/docs/graph7.svg index 854660ec..e83b8d54 100644 --- a/chapter11/docs/graph7.svg +++ b/chapter11/docs/graph7.svg @@ -1,54 +1,78 @@ - - - - - - -chapter11 - - -cluster_Nodes - - - - -Start2 - - -Start - - - -$ctrl - - - -Con_4 - -#0 - - - -Loop8 - -Loop - - - -Loop8->Start2:p0 - - -1 - - - -Loop8->Loop8 - - -2 - - - +#8[1] → #1 · CTRL#8[2] → #8 · CTRL$ctrl  #1/0#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLStart  #2#2 Start +Type not computed + +#0  #4#4 #0 +Type not computed + +Loop  #8#8 Loop +Type not computed + +[0] → — DATA +[1] → #1 CTRL +[2] → #8 CTRL012Loop  #8Loop · 1 nodes−Fold region diff --git a/chapter11/docs/graph8.json b/chapter11/docs/graph8.json new file mode 100644 index 00000000..ab2ef65c --- /dev/null +++ b/chapter11/docs/graph8.json @@ -0,0 +1,21 @@ +{ + "ver": 1, + "comp": "chapter11/docs/graph8.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 18, "role": "CTRL", "label": null}], "proj": {"par": 18, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 21, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 5, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 18, "role": "CTRL", "label": null}], "proj": {"par": 18, "idx": 1}}, + {"id": 6, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 8, "label": "Loop", "type": null, "kind": "LOOP", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 6, "role": "CTRL", "label": null}, {"idx": 2, "def": 5, "role": "CTRL", "label": null}], "proj": null}, + {"id": 18, "label": "Never", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 21, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 0, "role": "DATA", "label": null}, {"idx": 2, "def": 4, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 8, "par": 0, "nodes": [1, 5, 8, 18]} + ] +} diff --git a/chapter11/docs/graph8.svg b/chapter11/docs/graph8.svg index a89eeeb5..4db46240 100644 --- a/chapter11/docs/graph8.svg +++ b/chapter11/docs/graph8.svg @@ -1,115 +1,98 @@ - - - - - - -chapter11 - - -cluster_Nodes - - - - -Never18 - - -Never - - - -True - - -False - - - -Con_4 - -#0 - - - -Never18->Con_4 - - -1 - - - -Loop8 - -Loop - - - -Never18->Loop8 - - -0 - - - -Start2 - - -Start - - - -$ctrl - - - -Stop3 - -Stop - - - -Return21 - -Return - - - -Stop3->Return21 - - -0 - - - -Return21->Never18:p0 - - -0 - - - -Return21->Con_4 - - -2 - - - -Loop8->Never18:p1 - - -2 - - - -Loop8->Start2:p0 - - -1 - - - +#3[0] → #21 · CTRL#8[1] → #6 · CTRL#8[2] → #5 · CTRL#18[0] → #8 · CTRL#18[1] → #4 · DATA#21[0] → #1 · CTRL#21[2] → #4 · DATATrue  #1/0#1 True +Projection 0 of #18 +Type not computed + +[0] → #18 CTRLStart  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #21 CTRL0#0  #4#4 #0 +Type not computed + +False  #5/1#5 False +Projection 1 of #18 +Type not computed + +[0] → #18 CTRL$ctrl  #6/0#6 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLLoop  #8#8 Loop +Type not computed + +[0] → — DATA +[1] → #6 CTRL +[2] → #5 CTRL012Never  #18#18 Never +Type not computed + +[0] → #8 CTRL +[1] → #4 DATA01Return  #21#21 Return +Type not computed + +[0] → #1 CTRL +[1] → — DATA +[2] → #4 DATA012Loop  #8Loop · 4 nodes−Fold region -- cgit v1.2.3