diff options
| author | Dibyendu Majumdar <dibyendumajumdar@users.noreply.github.com> | 2024-01-15 00:13:44 +0000 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2024-01-14 16:13:44 -0800 |
| commit | 399bb146cc0bb0c548cd0b50e51fb9aa29a7900c (patch) | |
| tree | eab8cdd62af2d874a9bc88260447cef3718b2186 | |
| parent | 0671df6c0b76f160ec8c29c219a4af5249569aea (diff) | |
| download | Simple-399bb146cc0bb0c548cd0b50e51fb9aa29a7900c.tar.gz Simple-399bb146cc0bb0c548cd0b50e51fb9aa29a7900c.zip | |
Implement break and continue (#55)
* #52 Update chapter8 to align with chapter7
* #52 Update chapter8 to align with chapter7
* #52 Fix spacing
* #51 get started on break and continue
* #51 get started on break and continue
* #51 more on break and continue
* #51 more on break and continue
* #51 more on break and continue
* #51 more on break and continue
* #51 more on break and continue
* #51 more on break and continue
* break & continue scopes are made lazily, and merged into as discovered
Drop ContBreak.
Drop ScopeNode.addScope.
Add a simple mergeScopes.
Simplify Region.inProgress; drop from child classes, use in Region.
Add a ConstantNode.XCONTROL shortcut.
* Fix some regressions
* Error on dead code after break/continue
* A more robust dead-def check
* Fix for dead loop-back path
* Fix scope shadowing bug with continue/break
Turn on LAZY phis by default; fix minor golden test results
* Fix a case with both break & continue
* #51 more on break and continue
* #51 more on break and continue
* #51 more on break and continue
* #51 fix erroneous push of scope
* #51 fix import
* #51 update test expected results
* #51 Start Chapter8 writeup
* #51 Start Chapter8 writeup
* #51 _scope needs killing after continue
* Add graph evaluator (#56)
* #51 wip writeup
* #51 wip writeup
* #51 wip writeup
* #51 wip writeup
* #51 wip writeup
* #51 update code comments / add assertion
* #51 revert assertion
* #51 evaluate graph to verify test outcome
* #51 add code snippets
* #51 add examples
* Cleanup README
Comment for usefullness of true Loops.
Try to distiguish `PhiNode` as the programming construct from `phi` as the mathematically SSA notation.
Flow long lines.
Remove LAZY flag, set as `true`. Fold up true tests.
* minor comment
* #51 Check _breakScope is not null when parsing break or continue to detect use outside of loop
* #51 in parseComparison we need to move the op= version above the op version, since at this time using <= and >= does not work since they are parsed as > and < with a preceeding = which causes an error
* #51 Update main README to link to chapter 8
* Remove useless test
---------
Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
| -rw-r--r-- | README.md | 2 | ||||
| -rw-r--r-- | chapter07/src/main/java/com/seaofnodes/simple/node/RegionNode.java | 1 | ||||
| -rw-r--r-- | chapter08/README.md | 250 | ||||
| -rw-r--r-- | chapter08/docs/08-grammar.md | 10 | ||||
| -rw-r--r-- | chapter08/docs/08-graph1.gv | 107 | ||||
| -rw-r--r-- | chapter08/docs/08-graph1.svg | 359 | ||||
| -rw-r--r-- | chapter08/docs/08-graph2.gv | 103 | ||||
| -rw-r--r-- | chapter08/docs/08-graph2.svg | 332 | ||||
| -rw-r--r-- | chapter08/docs/08-graph3.gv | 111 | ||||
| -rw-r--r-- | chapter08/docs/08-graph3.svg | 386 | ||||
| -rw-r--r-- | chapter08/docs/build-graphs.sh | 5 | ||||
| -rw-r--r-- | chapter08/src/main/java/com/seaofnodes/simple/GraphEvaluator.java | 175 | ||||
| -rw-r--r-- | chapter08/src/main/java/com/seaofnodes/simple/Parser.java | 94 | ||||
| -rw-r--r-- | chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java | 16 | ||||
| -rw-r--r-- | chapter08/src/main/java/com/seaofnodes/simple/node/Node.java | 11 | ||||
| -rw-r--r-- | chapter08/src/main/java/com/seaofnodes/simple/node/RegionNode.java | 10 | ||||
| -rw-r--r-- | chapter08/src/main/java/com/seaofnodes/simple/node/ScopeNode.java | 37 | ||||
| -rw-r--r-- | chapter08/src/test/java/com/seaofnodes/simple/Chapter08Test.java | 213 |
18 files changed, 2140 insertions, 82 deletions
@@ -35,7 +35,7 @@ The simple language will be a small subset of C. * [Chapter 5](chapter05/README.md): `if` statement. CFG construction. * [Chapter 6](chapter06/README.md): Peephole optimization around dead control flow. * [Chapter 7](chapter07/README.md): `while` statement. Looping construct - eager phi approach. -* Chapter 8: Looping construct continued, lazy phi creation, `break` and `continue` statements. +* [Chapter 8](chapter08/README.md): Looping construct continued, lazy phi creation, `break` and `continue` statements. * Chapter 9: Global Value Numbering. * Chapter 10: Functions and calls. * Chapter 11: Boolean operators `&&`, `||` and `!` including short circuit. diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 3b793758..7113f5c4 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -3,7 +3,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; -import java.util.Collection; import java.util.BitSet; public class RegionNode extends Node { diff --git a/chapter08/README.md b/chapter08/README.md index ddfde17f..402d487a 100644 --- a/chapter08/README.md +++ b/chapter08/README.md @@ -1,3 +1,251 @@ # Chapter 8 -In this chapter we move from eager to lazy phi creation in loops. +In this chapter: + +* We move from eager to lazy `Phi` creation in loops. +* We add support for `break` and `continue` statements. +* We implement a Sea of Nodes Graph Evaluator. + +Here is the [complete language grammar](docs/08-grammar.md) for this chapter. + +## Lazy Phi Creation + +In [chapter 7](../chapter07/README.md), we created `PhiNode`s for all variables +in the loop head eagerly. This approach creates some unnecessary Phis but the +redundant Phis get cleaned up later. + +In this chapter we add support for creating the `PhiNode`s lazily. + +The main complication with creating `PhiNode`s lazily is that when we create a +Phi, it must be created in the innermost loop head scope where it would have +been created had we done it eagerly. Since scopes get duped in `if` and +`while` statements, we cannot just create Phis in the current scope. + +It turns out that the easiest way to create the `PhiNode`s lazily is to hook +them up to name lookup. But how do we know that a Phi must be created when we +access a name? We need a way to flag that a particular name mapping must be +converted to a `PhiNode` on lookup. + +We do this as follows: + +* In `ScopeNode.dup()`, if the Scope is being duplicated for a loop head, then + instead of setting the name's definition to the original node, we set it to + the Scope itself. This acts like a sentinel. + + ```java + // For lazy phis on loops we use a sentinel + // that will trigger phi creation on update + dup.addDef(loop ? this : in(i)); + ``` + +* Subsequently, when a lookup accesses a name, we notice that the def is set to + the Scope node, and we create a `PhiNode` at this point. The relevant + implementation is in `ScopeNode.update()`. + + ```java + if( old instanceof ScopeNode loop ) { + // Lazy Phi! + old = loop.in(idx) instanceof PhiNode phi && loop.ctrl()==phi.region() + // Loop already has a real Phi, use it + ? loop.in(idx) + // 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,loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole()); + setDef(idx,old); + } + ``` + +* When we merge scopes, we ensure lazy `PhiNode` creation at the correct inner + scope level by invoking lookup by name instead of directly accessing the + defs. + + ```java + 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], r, this.lookup(ns[i]), that.lookup(ns[i])).peephole()); + ``` + +* Finally, in `ScopeNode.endLoop()` we clean up any leftover sentinels, replacing the sentinel with the input from loop head. + + ```java + for( int i=1; i<nIns(); i++ ) { + if( back.in(i) != this ) { + PhiNode phi = (PhiNode)in(i); + assert phi.region()==ctrl && phi.in(2)==null; + phi.setDef(2,back.in(i)); + // Do an eager useless-phi removal + Node in = phi.peephole(); + if( in != phi ) + phi.subsume(in); + } + if( exit.in(i) == this ) // Replace a lazy-phi on the exit path also + exit.setDef(i,in(i)); + } + ``` + +## `continue` Statement + +In chapter7, we had a single backedge from the loop's end flowing back to the +loop head. + +With the addition of a `continue` statement, we can have multiple backedges +flowing back to the loop head. + +We have several ways of implementing these backedges. + +1. The traditional way would be to let each backedge from `continue` merge into + the loop head. Phis would require as many inputs as there are edges. The + downside is now are Loops are not simply nested. This makes it difficult to + do many kinds of peephole-based loop optimizations, such as "partially + rolling" the loop to allow more loop invariants to get hoisted. +2. An alternative is collect all `continue`s at a single merge point (`Region`) + and then create a single backedge flowing from the continue `Region` to the + loop head. +3. A third approach is to create a stack of continue `Region`s rather than a + single continue `Region`. This has the benefit of keeping our Phis simple + with just two inputs as they are now, whereas the other approaches require + Phis with more than 2 inputs. On the other hand we end up with as many + continue `Region`s as there are `continue` statements, and corresponding + Phis that are stacked. + +In this chapter we adopt option 3 as it is the simplest implementation on top +of our basic `while` loop architecture. We also experimented with +option 2. For readers who would like to see this alternative solution, we +provide a separate branch with such an implementation. + +The implementation requires some careful handling of scopes. This is because +we would like to only generate `PhiNode/RegionNode`s for continues if necessary. + +In our [basic loop architecture](../chapter07/README.md), by the time we get to +the loop backedge, we have already exited all nested blocks/scopes, we just +need to stitch together the current scope+ctrl into the Loop scope+ctrl and +create `PhiNode`s as needed. + +A `continue` however, can occur inside nested scopes (such as nested `if` +statement). Since we want to lazily create the continue `Region`, the first +time we see a `continue`, we need to dupe the head scope and merge the current +scope into it to generate a continue Scope and `Region`. Subsequently, when we +see another `continue`, we need to construct a new `Region` and merge the +previous continue Scope with the current Scope. + +The implementation is a variation of above. + +* The first `continue` triggers a dupe of the current scope; we prune any + nested lexical scopes deeper than the head scope, removing any name bindings + that were not visible in the head scope. This is essentially ensuring that + we "exit" any nested scopes. + + We set the continue scope initially to null. + + ```java + // No continues yet + _continueScope = null; + ``` + When we parse continue, the first time `_continueScope` is null. + + ```java + private Node parseContinue() { return (_continueScope = require(jumpTo( _continueScope ),";")); } + + private ScopeNode jumpTo(ScopeNode toScope) { + ScopeNode cur = _scope.dup(); + ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill current scope + // Prune nested lexical scopes that have depth > than the loop head + // We use _breakScope as a proxy for the loop head scope to obtain the depth + while( cur._scopes.size() > _breakScope._scopes.size() ) + cur.pop(); + // If this is a continue then first time the target is null + // So we just use the pruned current scope as the base for the + // continue + if (toScope == null) + return cur; + // toScope is either the break scope, or a scope that was created here + assert toScope._scopes.size() <= _breakScope._scopes.size(); + toScope.mergeScopes(cur); + return toScope; + } + ``` + +* The continue scope becomes the base scope for the subsequent `continue` + statement, thus forming a stack of continue scopes/regions. +* After the loop is done, if we find that a continue scope was created within + the loop, we must merge the current scope into the continue scope, and make + the continue scope the active scope. + + ```java + // Merge the loop bottom into other continue statements + if (_continueScope != null) { + _continueScope = jumpTo(_continueScope); + _scope.kill(); + _scope = _continueScope; + } + ``` + +## `break` Statement + +Implementing `break` is simpler than `continue`, because the exit scope is +created before we parse the loop body, and this becomes the initial `break` +scope. When we see `break`, we merge the current scope, after pruning any +nested lexical scopes, to the current break scope, and the resulting new scope +becomes the active break scope. + +## Parser Considerations + +Since a `continue` or `break` targets the immediate surrounding `while` loop, +we maintain a stack of the `continue` and `break` scopes. This is done by +saving the previous `continue` or `break` scope before parsing a `while` loop +and restoring afterward. + +## Examples + +### Example 1 + +```java +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + break; +} +return arg; +``` + + + + +### Example 2 + +```java +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + continue; +} +return arg; +``` + + + +### Example 3 + +```java +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + break; + if (arg == 6) + break; +} +return arg; +``` + + + + +## Sea of Nodes Graph Evaluator + +TODO
\ No newline at end of file diff --git a/chapter08/docs/08-grammar.md b/chapter08/docs/08-grammar.md index cee33030..c603f335 100644 --- a/chapter08/docs/08-grammar.md +++ b/chapter08/docs/08-grammar.md @@ -14,6 +14,8 @@ statement | expressionStatement | ifStatement | whileStatement + | breakStatement + | continueStatment | metaStatement ; @@ -21,6 +23,14 @@ whileStatement : 'while' '(' expression ')' statement ; +breakStatement + : 'break' ';' + ; + +continueStatement + : 'continue' ';' + ; + ifStatement : 'if' '(' expression ')' statement ('else' statement)? ; diff --git a/chapter08/docs/08-graph1.gv b/chapter08/docs/08-graph1.gv new file mode 100644 index 00000000..604ee0fe --- /dev/null +++ b/chapter08/docs/08-graph1.gv @@ -0,0 +1,107 @@ +digraph chapter08 { +/* +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + break; +} +return arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">Start</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">$ctrl</TD><TD PORT="p1">arg</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Loop6 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_arg8 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + Con_9 [ label="10" ]; + LT10 [ label="<" ]; + If11 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Con_15 [ label="1" ]; + Add16 [ label="+" ]; + Con_17 [ label="5" ]; + EQ18 [ label="==" ]; + If19 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Con_26 [ label="6" ]; + EQ27 [ label="==" ]; + If28 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Region34 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_arg35 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + Region39 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Return40 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop6;Phi_arg8;} + { rank=same; Region34;Phi_arg35;} + { rank=same; Region39;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return40[taillabel=0 color=red]; + Loop6 -> Start2:p0[taillabel=1 color=red]; + Loop6 -> Region39[taillabel=2 color=red constraint=false]; + Phi_arg8 -> Loop6 [style=dotted taillabel=0]; + Phi_arg8 -> Start2:p1[taillabel=1]; + Phi_arg8 -> Add16[taillabel=2 constraint=false]; + LT10 -> Phi_arg8[taillabel=1]; + LT10 -> Con_9[taillabel=2]; + If11 -> Loop6[taillabel=0 color=red]; + If11 -> LT10[taillabel=1]; + Add16 -> Phi_arg8[taillabel=1]; + Add16 -> Con_15[taillabel=2]; + EQ18 -> Add16[taillabel=1]; + EQ18 -> Con_17[taillabel=2]; + If19 -> If11:p0[taillabel=0 color=red]; + If19 -> EQ18[taillabel=1]; + EQ27 -> Add16[taillabel=1]; + EQ27 -> Con_26[taillabel=2]; + If28 -> If19:p1[taillabel=0 color=red]; + If28 -> EQ27[taillabel=1]; + Region34 -> If11:p1[taillabel=1 color=red]; + Region34 -> If28:p0[taillabel=2 color=red]; + Phi_arg35 -> Region34 [style=dotted taillabel=0]; + Phi_arg35 -> Phi_arg8[taillabel=1]; + Phi_arg35 -> Add16[taillabel=2 constraint=false]; + Region39 -> If19:p0[taillabel=1 color=red]; + Region39 -> If28:p1[taillabel=2 color=red]; + Return40 -> Region34[taillabel=0 color=red]; + Return40 -> Phi_arg35[taillabel=1]; +} diff --git a/chapter08/docs/08-graph1.svg b/chapter08/docs/08-graph1.svg new file mode 100644 index 00000000..0f23a746 --- /dev/null +++ b/chapter08/docs/08-graph1.svg @@ -0,0 +1,359 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 2.43.0 (0) + --> +<!-- Title: chapter08 Pages: 1 --> +<svg width="334pt" height="764pt" + viewBox="0.00 0.00 334.00 764.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 760)"> +<title>chapter08</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-760 330,-760 330,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-748 318,-748 318,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="80,-711 80,-736 161,-736 161,-711 80,-711"/> +<polygon fill="none" stroke="black" points="80,-711 80,-736 161,-736 161,-711 80,-711"/> +<text text-anchor="start" x="102" y="-719.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="80,-680 80,-711 161,-711 161,-680 80,-680"/> +<polygon fill="yellow" stroke="transparent" points="85,-685 85,-706 125,-706 125,-685 85,-685"/> +<polygon fill="none" stroke="black" points="85,-685 85,-706 125,-706 125,-685 85,-685"/> +<text text-anchor="start" x="88" y="-691.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="125,-685 125,-706 156,-706 156,-685 125,-685"/> +<text text-anchor="start" x="128" y="-691.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- Stop3 --> +<g id="node2" class="node"> +<title>Stop3</title> +<polygon fill="yellow" stroke="black" points="130,-52 76,-52 76,-16 130,-16 130,-52"/> +<text text-anchor="middle" x="103" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return40 --> +<g id="node19" class="node"> +<title>Return40</title> +<polygon fill="yellow" stroke="black" points="136,-124 70,-124 70,-88 136,-88 136,-124"/> +<text text-anchor="middle" x="103" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return40 --> +<g id="edge1" class="edge"> +<title>Stop3->Return40</title> +<path fill="none" stroke="red" d="M103,-52.3C103,-60.02 103,-69.29 103,-77.89"/> +<polygon fill="red" stroke="red" points="99.5,-77.9 103,-87.9 106.5,-77.9 99.5,-77.9"/> +<text text-anchor="middle" x="100" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Loop6 --> +<g id="node3" class="node"> +<title>Loop6</title> +<polygon fill="yellow" stroke="black" points="70,-640 16,-640 16,-604 70,-604 70,-640"/> +<text text-anchor="middle" x="43" y="-618.3" font-family="Times,serif" font-size="14.00">Loop</text> +</g> +<!-- Loop6->Start2 --> +<g id="edge2" class="edge"> +<title>Loop6->Start2:p0</title> +<path fill="none" stroke="red" d="M45.16,-640.06C48.35,-658.19 56.02,-685.28 73.77,-692.93"/> +<polygon fill="red" stroke="red" points="73.5,-696.44 84,-695 74.89,-689.58 73.5,-696.44"/> +<text text-anchor="middle" x="42.16" y="-642.66" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region39 --> +<g id="node18" class="node"> +<title>Region39</title> +<polygon fill="yellow" stroke="black" points="268,-196 202,-196 202,-160 268,-160 268,-196"/> +<text text-anchor="middle" x="235" y="-174.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Loop6->Region39 --> +<g id="edge3" class="edge"> +<title>Loop6->Region39</title> +<path fill="none" stroke="red" d="M34.42,-603.81C18.87,-570.32 -10.82,-494.13 7,-432 35.9,-331.24 54.86,-302.97 132,-232 141.73,-223.05 168.66,-209.3 192.54,-198.05"/> +<polygon fill="red" stroke="red" points="194.25,-201.11 201.84,-193.72 191.3,-194.77 194.25,-201.11"/> +<text text-anchor="middle" x="31.42" y="-597.41" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_arg8 --> +<g id="node4" class="node"> +<title>Phi_arg8</title> +<ellipse fill="lightyellow" stroke="black" cx="197" cy="-622" rx="37.09" ry="18"/> +<text text-anchor="middle" x="197" y="-618.3" font-family="Times,serif" font-size="14.00">φ_arg</text> +</g> +<!-- Phi_arg8->Start2 --> +<g id="edge5" class="edge"> +<title>Phi_arg8->Start2:p1</title> +<path fill="none" stroke="black" d="M195.04,-640.06C192.05,-658.19 184.71,-685.28 167.15,-692.93"/> +<polygon fill="black" stroke="black" points="166.1,-689.57 157,-695 167.5,-696.43 166.1,-689.57"/> +<text text-anchor="middle" x="192.04" y="-642.66" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_arg8->Loop6 --> +<g id="edge4" class="edge"> +<title>Phi_arg8->Loop6</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M178.53,-606.01C168.46,-598.34 155.34,-589.98 142,-586 119,-579.14 110.65,-578.06 88,-586 80.86,-588.5 74.01,-592.67 67.91,-597.3"/> +<polygon fill="black" stroke="black" points="65.55,-594.71 60.08,-603.78 70.01,-600.1 65.55,-594.71"/> +<text text-anchor="middle" x="175.53" y="-599.61" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Add16 --> +<g id="node9" class="node"> +<title>Add16</title> +<ellipse fill="none" stroke="black" cx="197" cy="-550" rx="27" ry="18"/> +<text text-anchor="middle" x="197" y="-546.3" font-family="Times,serif" font-size="14.00">+</text> +</g> +<!-- Con_9 --> +<g id="node5" class="node"> +<title>Con_9</title> +<ellipse fill="none" stroke="black" cx="115" cy="-622" rx="27" ry="18"/> +<text text-anchor="middle" x="115" y="-618.3" font-family="Times,serif" font-size="14.00">10</text> +</g> +<!-- LT10 --> +<g id="node6" class="node"> +<title>LT10</title> +<ellipse fill="none" stroke="black" cx="99" cy="-550" rx="27" ry="18"/> +<text text-anchor="middle" x="99" y="-546.3" font-family="Times,serif" font-size="14.00"><</text> +</g> +<!-- LT10->Phi_arg8 --> +<g id="edge7" class="edge"> +<title>LT10->Phi_arg8</title> +<path fill="none" stroke="black" d="M116.97,-563.84C131.47,-574.19 152.11,-588.94 168.8,-600.86"/> +<polygon fill="black" stroke="black" points="166.94,-603.83 177.12,-606.8 171.01,-598.14 166.94,-603.83"/> +<text text-anchor="middle" x="113.97" y="-566.44" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- LT10->Con_9 --> +<g id="edge8" class="edge"> +<title>LT10->Con_9</title> +<path fill="none" stroke="black" d="M102.87,-567.95C104.65,-575.74 106.81,-585.18 108.81,-593.92"/> +<polygon fill="black" stroke="black" points="105.41,-594.76 111.05,-603.72 112.24,-593.2 105.41,-594.76"/> +<text text-anchor="middle" x="99.87" y="-570.55" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If11 --> +<g id="node7" class="node"> +<title>If11</title> +<polygon fill="yellow" stroke="transparent" points="24,-467 24,-492 118,-492 118,-467 24,-467"/> +<polygon fill="none" stroke="black" points="24,-467 24,-492 118,-492 118,-467 24,-467"/> +<text text-anchor="start" x="65.5" y="-475.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="24,-436 24,-467 118,-467 118,-436 24,-436"/> +<polygon fill="yellow" stroke="transparent" points="29,-441 29,-462 69,-462 69,-441 29,-441"/> +<polygon fill="none" stroke="black" points="29,-441 29,-462 69,-462 69,-441 29,-441"/> +<text text-anchor="start" x="32" y="-447.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="69,-441 69,-462 113,-462 113,-441 69,-441"/> +<polygon fill="none" stroke="black" points="69,-441 69,-462 113,-462 113,-441 69,-441"/> +<text text-anchor="start" x="72" y="-447.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If11->Loop6 --> +<g id="edge9" class="edge"> +<title>If11->Loop6</title> +<path fill="none" stroke="red" d="M65.4,-496.19C60.27,-524.77 52.76,-566.64 47.87,-593.86"/> +<polygon fill="red" stroke="red" points="44.4,-593.4 46.08,-603.86 51.29,-594.63 44.4,-593.4"/> +<text text-anchor="middle" x="62.4" y="-498.79" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If11->LT10 --> +<g id="edge10" class="edge"> +<title>If11->LT10</title> +<path fill="none" stroke="black" d="M81.43,-496.28C84.3,-504.9 87.39,-514.17 90.16,-522.49"/> +<polygon fill="black" stroke="black" points="86.87,-523.69 93.36,-532.07 93.51,-521.48 86.87,-523.69"/> +<text text-anchor="middle" x="78.43" y="-498.88" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_15 --> +<g id="node8" class="node"> +<title>Con_15</title> +<ellipse fill="none" stroke="black" cx="279" cy="-622" rx="27" ry="18"/> +<text text-anchor="middle" x="279" y="-618.3" font-family="Times,serif" font-size="14.00">1</text> +</g> +<!-- Add16->Phi_arg8 --> +<g id="edge11" class="edge"> +<title>Add16->Phi_arg8</title> +<path fill="none" stroke="black" d="M197,-578.33C197,-583.31 197,-588.51 197,-593.49"/> +<polygon fill="black" stroke="black" points="200.5,-578.3 197,-568.3 193.5,-578.3 200.5,-578.3"/> +<polygon fill="black" stroke="black" points="193.5,-593.9 197,-603.9 200.5,-593.9 193.5,-593.9"/> +<text text-anchor="middle" x="194" y="-570.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Add16->Con_15 --> +<g id="edge12" class="edge"> +<title>Add16->Con_15</title> +<path fill="none" stroke="black" d="M213.2,-564.83C225.18,-575.06 241.69,-589.15 255.18,-600.66"/> +<polygon fill="black" stroke="black" points="253.23,-603.61 263.11,-607.44 257.78,-598.28 253.23,-603.61"/> +<text text-anchor="middle" x="210.2" y="-567.43" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Con_17 --> +<g id="node10" class="node"> +<title>Con_17</title> +<ellipse fill="none" stroke="black" cx="269" cy="-550" rx="27" ry="18"/> +<text text-anchor="middle" x="269" y="-546.3" font-family="Times,serif" font-size="14.00">5</text> +</g> +<!-- EQ18 --> +<g id="node11" class="node"> +<title>EQ18</title> +<ellipse fill="none" stroke="black" cx="211" cy="-464" rx="27" ry="18"/> +<text text-anchor="middle" x="211" y="-460.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQ18->Add16 --> +<g id="edge13" class="edge"> +<title>EQ18->Add16</title> +<path fill="none" stroke="black" d="M208.17,-482C206.25,-493.5 203.68,-508.93 201.49,-522.08"/> +<polygon fill="black" stroke="black" points="198.02,-521.59 199.83,-532.03 204.93,-522.74 198.02,-521.59"/> +<text text-anchor="middle" x="205.17" y="-484.6" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQ18->Con_17 --> +<g id="edge14" class="edge"> +<title>EQ18->Con_17</title> +<path fill="none" stroke="black" d="M221.91,-480.8C230.5,-493.24 242.61,-510.78 252.4,-524.95"/> +<polygon fill="black" stroke="black" points="249.58,-527.03 258.14,-533.27 255.34,-523.05 249.58,-527.03"/> +<text text-anchor="middle" x="218.91" y="-483.4" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If19 --> +<g id="node12" class="node"> +<title>If19</title> +<polygon fill="yellow" stroke="transparent" points="116,-367 116,-392 210,-392 210,-367 116,-367"/> +<polygon fill="none" stroke="black" points="116,-367 116,-392 210,-392 210,-367 116,-367"/> +<text text-anchor="start" x="157.5" y="-375.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="116,-336 116,-367 210,-367 210,-336 116,-336"/> +<polygon fill="yellow" stroke="transparent" points="121,-341 121,-362 161,-362 161,-341 121,-341"/> +<polygon fill="none" stroke="black" points="121,-341 121,-362 161,-362 161,-341 121,-341"/> +<text text-anchor="start" x="124" y="-347.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="161,-341 161,-362 205,-362 205,-341 161,-341"/> +<polygon fill="none" stroke="black" points="161,-341 161,-362 205,-362 205,-341 161,-341"/> +<text text-anchor="start" x="164" y="-347.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If19->If11 --> +<g id="edge15" class="edge"> +<title>If19->If11:p0</title> +<path fill="none" stroke="red" d="M107.67,-379.11C81.91,-388.94 55.7,-404.9 50.1,-429.95"/> +<polygon fill="red" stroke="red" points="46.61,-429.68 49,-440 53.56,-430.44 46.61,-429.68"/> +<text text-anchor="middle" x="104.67" y="-372.71" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If19->EQ18 --> +<g id="edge16" class="edge"> +<title>If19->EQ18</title> +<path fill="none" stroke="black" d="M178.19,-396.01C184.75,-409.41 192.34,-424.91 198.57,-437.61"/> +<polygon fill="black" stroke="black" points="195.48,-439.27 203.02,-446.71 201.76,-436.19 195.48,-439.27"/> +<text text-anchor="middle" x="175.19" y="-398.61" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_26 --> +<g id="node13" class="node"> +<title>Con_26</title> +<ellipse fill="none" stroke="black" cx="283" cy="-464" rx="27" ry="18"/> +<text text-anchor="middle" x="283" y="-460.3" font-family="Times,serif" font-size="14.00">6</text> +</g> +<!-- EQ27 --> +<g id="node14" class="node"> +<title>EQ27</title> +<ellipse fill="none" stroke="black" cx="263" cy="-364" rx="27" ry="18"/> +<text text-anchor="middle" x="263" y="-360.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQ27->Add16 --> +<g id="edge17" class="edge"> +<title>EQ27->Add16</title> +<path fill="none" stroke="black" d="M247.53,-378.95C241.28,-384.42 233.92,-390.65 227,-396 204.76,-413.19 191.76,-409.43 175,-432 166.37,-443.62 168.75,-449.02 165,-463"/> +<path fill="none" stroke="black" d="M165,-465C159.41,-485.86 169.21,-508.71 179.4,-525.31"/> +<polygon fill="black" stroke="black" points="176.59,-527.4 185,-533.83 182.43,-523.55 176.59,-527.4"/> +<text text-anchor="middle" x="244.53" y="-381.55" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQ27->Con_26 --> +<g id="edge18" class="edge"> +<title>EQ27->Con_26</title> +<path fill="none" stroke="black" d="M266.48,-382.07C269.52,-396.97 273.99,-418.83 277.51,-436.08"/> +<polygon fill="black" stroke="black" points="274.13,-437.03 279.56,-446.13 280.99,-435.63 274.13,-437.03"/> +<text text-anchor="middle" x="263.48" y="-384.67" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If28 --> +<g id="node15" class="node"> +<title>If28</title> +<polygon fill="yellow" stroke="transparent" points="168,-267 168,-292 262,-292 262,-267 168,-267"/> +<polygon fill="none" stroke="black" points="168,-267 168,-292 262,-292 262,-267 168,-267"/> +<text text-anchor="start" x="209.5" y="-275.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="168,-236 168,-267 262,-267 262,-236 168,-236"/> +<polygon fill="yellow" stroke="transparent" points="173,-241 173,-262 213,-262 213,-241 173,-241"/> +<polygon fill="none" stroke="black" points="173,-241 173,-262 213,-262 213,-241 173,-241"/> +<text text-anchor="start" x="176" y="-247.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="213,-241 213,-262 257,-262 257,-241 213,-241"/> +<polygon fill="none" stroke="black" points="213,-241 213,-262 257,-262 257,-241 213,-241"/> +<text text-anchor="start" x="216" y="-247.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If28->If19 --> +<g id="edge19" class="edge"> +<title>If28->If19:p1</title> +<path fill="none" stroke="red" d="M195.1,-296.25C190.01,-306.42 185.49,-318.16 183.75,-330.03"/> +<polygon fill="red" stroke="red" points="180.26,-329.76 183,-340 187.24,-330.29 180.26,-329.76"/> +<text text-anchor="middle" x="192.1" y="-298.85" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If28->EQ27 --> +<g id="edge20" class="edge"> +<title>If28->EQ27</title> +<path fill="none" stroke="black" d="M230.19,-296.01C236.75,-309.41 244.34,-324.91 250.57,-337.61"/> +<polygon fill="black" stroke="black" points="247.48,-339.27 255.02,-346.71 253.76,-336.19 247.48,-339.27"/> +<text text-anchor="middle" x="227.19" y="-298.61" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region34 --> +<g id="node16" class="node"> +<title>Region34</title> +<polygon fill="yellow" stroke="black" points="92,-196 26,-196 26,-160 92,-160 92,-196"/> +<text text-anchor="middle" x="59" y="-174.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Region34->If11 --> +<g id="edge21" class="edge"> +<title>Region34->If11:p1</title> +<path fill="none" stroke="red" d="M60.73,-196.19C64.47,-232.93 73.83,-321.8 84,-396 86.16,-411.79 89.38,-417.84 90.55,-429.91"/> +<polygon fill="red" stroke="red" points="87.06,-430.17 91,-440 94.05,-429.85 87.06,-430.17"/> +<text text-anchor="middle" x="57.73" y="-198.79" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region34->If28 --> +<g id="edge22" class="edge"> +<title>Region34->If28:p0</title> +<path fill="none" stroke="red" d="M73.55,-196.06C91.73,-215.52 124.92,-245.31 161.58,-250.28"/> +<polygon fill="red" stroke="red" points="161.78,-253.81 172,-251 162.26,-246.82 161.78,-253.81"/> +<text text-anchor="middle" x="70.55" y="-198.66" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_arg35 --> +<g id="node17" class="node"> +<title>Phi_arg35</title> +<ellipse fill="lightyellow" stroke="black" cx="147" cy="-178" rx="37.09" ry="18"/> +<text text-anchor="middle" x="147" y="-174.3" font-family="Times,serif" font-size="14.00">φ_arg</text> +</g> +<!-- Phi_arg35->Phi_arg8 --> +<g id="edge24" class="edge"> +<title>Phi_arg35->Phi_arg8</title> +<path fill="none" stroke="black" d="M136.87,-195.37C115.38,-232.36 69.47,-324.71 99,-396 107.66,-416.91 124.41,-412 135,-432 163.81,-486.38 137.45,-511.15 161,-568 165.15,-578.02 171.36,-588.09 177.46,-596.73"/> +<polygon fill="black" stroke="black" points="174.69,-598.87 183.44,-604.83 180.32,-594.71 174.69,-598.87"/> +<text text-anchor="middle" x="133.87" y="-197.97" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_arg35->Add16 --> +<g id="edge25" class="edge"> +<title>Phi_arg35->Add16</title> +<path fill="none" stroke="black" d="M175.64,-189.71C213.39,-203.94 275.5,-227.79 279,-232 307.96,-266.86 294.53,-286.9 299,-332 301.8,-360.31 316.08,-373.26 299,-396 264.54,-441.89 216.17,-392.02 175,-432 164.61,-442.08 168.75,-449.02 165,-463"/> +<text text-anchor="middle" x="172.64" y="-192.31" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_arg35->Region34 --> +<g id="edge23" class="edge"> +<title>Phi_arg35->Region34</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M109.85,-178C107.39,-178 104.93,-178 102.47,-178"/> +<polygon fill="black" stroke="black" points="102.34,-174.5 92.34,-178 102.34,-181.5 102.34,-174.5"/> +<text text-anchor="middle" x="106.85" y="-171.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Region39->If19 --> +<g id="edge26" class="edge"> +<title>Region39->If19:p0</title> +<path fill="none" stroke="red" d="M201.88,-195.94C181.14,-207.25 157.22,-221.86 151,-232 127.62,-270.12 139.01,-288.97 140.78,-329.99"/> +<polygon fill="red" stroke="red" points="137.28,-330.08 141,-340 144.28,-329.93 137.28,-330.08"/> +<text text-anchor="middle" x="198.88" y="-189.54" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region39->If28 --> +<g id="edge27" class="edge"> +<title>Region39->If28:p1</title> +<path fill="none" stroke="red" d="M235,-196.09C235,-205.55 235,-217.77 235,-229.69"/> +<polygon fill="red" stroke="red" points="231.5,-230 235,-240 238.5,-230 231.5,-230"/> +<text text-anchor="middle" x="232" y="-198.69" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Return40->Region34 --> +<g id="edge28" class="edge"> +<title>Return40->Region34</title> +<path fill="none" stroke="red" d="M92.12,-124.3C87.01,-132.44 80.8,-142.31 75.16,-151.3"/> +<polygon fill="red" stroke="red" points="72.11,-149.57 69.75,-159.9 78.04,-153.29 72.11,-149.57"/> +<text text-anchor="middle" x="89.12" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return40->Phi_arg35 --> +<g id="edge29" class="edge"> +<title>Return40->Phi_arg35</title> +<path fill="none" stroke="black" d="M113.88,-124.3C119.07,-132.56 125.38,-142.61 131.1,-151.7"/> +<polygon fill="black" stroke="black" points="128.27,-153.77 136.55,-160.38 134.19,-150.05 128.27,-153.77"/> +<text text-anchor="middle" x="110.88" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +</g> +</svg> diff --git a/chapter08/docs/08-graph2.gv b/chapter08/docs/08-graph2.gv new file mode 100644 index 00000000..2fa82523 --- /dev/null +++ b/chapter08/docs/08-graph2.gv @@ -0,0 +1,103 @@ +digraph chapter08 { +/* +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + continue; +} +return arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">Start</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">$ctrl</TD><TD PORT="p1">arg</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Loop6 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_arg8 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + Con_9 [ label="10" ]; + LT10 [ label="<" ]; + If11 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Con_15 [ label="1" ]; + Add16 [ label="+" ]; + Con_17 [ label="5" ]; + EQ18 [ label="==" ]; + If19 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Con_26 [ label="6" ]; + EQ27 [ label="==" ]; + If28 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Region34 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Region38 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Return39 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop6;Phi_arg8;} + { rank=same; Region34;} + { rank=same; Region38;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return39[taillabel=0 color=red]; + Loop6 -> Start2:p0[taillabel=1 color=red]; + Loop6 -> Region38[taillabel=2 color=red constraint=false]; + Phi_arg8 -> Loop6 [style=dotted taillabel=0]; + Phi_arg8 -> Start2:p1[taillabel=1]; + Phi_arg8 -> Add16[taillabel=2 constraint=false]; + LT10 -> Phi_arg8[taillabel=1]; + LT10 -> Con_9[taillabel=2]; + If11 -> Loop6[taillabel=0 color=red]; + If11 -> LT10[taillabel=1]; + Add16 -> Phi_arg8[taillabel=1]; + Add16 -> Con_15[taillabel=2]; + EQ18 -> Add16[taillabel=1]; + EQ18 -> Con_17[taillabel=2]; + If19 -> If11:p0[taillabel=0 color=red]; + If19 -> EQ18[taillabel=1]; + EQ27 -> Add16[taillabel=1]; + EQ27 -> Con_26[taillabel=2]; + If28 -> If19:p1[taillabel=0 color=red]; + If28 -> EQ27[taillabel=1]; + Region34 -> If19:p0[taillabel=1 color=red]; + Region34 -> If28:p0[taillabel=2 color=red]; + Region38 -> Region34[taillabel=1 color=red]; + Region38 -> If28:p1[taillabel=2 color=red]; + Return39 -> If11:p1[taillabel=0 color=red]; + Return39 -> Phi_arg8[taillabel=1]; +} diff --git a/chapter08/docs/08-graph2.svg b/chapter08/docs/08-graph2.svg new file mode 100644 index 00000000..1f497470 --- /dev/null +++ b/chapter08/docs/08-graph2.svg @@ -0,0 +1,332 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 2.43.0 (0) + --> +<!-- Title: chapter08 Pages: 1 --> +<svg width="334pt" height="692pt" + viewBox="0.00 0.00 334.00 692.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 688)"> +<title>chapter08</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-688 330,-688 330,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-676 318,-676 318,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="81,-639 81,-664 162,-664 162,-639 81,-639"/> +<polygon fill="none" stroke="black" points="81,-639 81,-664 162,-664 162,-639 81,-639"/> +<text text-anchor="start" x="103" y="-647.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="81,-608 81,-639 162,-639 162,-608 81,-608"/> +<polygon fill="yellow" stroke="transparent" points="86,-613 86,-634 126,-634 126,-613 86,-613"/> +<polygon fill="none" stroke="black" points="86,-613 86,-634 126,-634 126,-613 86,-613"/> +<text text-anchor="start" x="89" y="-619.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="126,-613 126,-634 157,-634 157,-613 126,-613"/> +<text text-anchor="start" x="129" y="-619.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- Stop3 --> +<g id="node2" class="node"> +<title>Stop3</title> +<polygon fill="yellow" stroke="black" points="174,-210 120,-210 120,-174 174,-174 174,-210"/> +<text text-anchor="middle" x="147" y="-188.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return39 --> +<g id="node18" class="node"> +<title>Return39</title> +<polygon fill="yellow" stroke="black" points="228,-310 162,-310 162,-274 228,-274 228,-310"/> +<text text-anchor="middle" x="195" y="-288.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return39 --> +<g id="edge1" class="edge"> +<title>Stop3->Return39</title> +<path fill="none" stroke="red" d="M155.36,-210.07C162.75,-225.15 173.64,-247.39 182.14,-264.74"/> +<polygon fill="red" stroke="red" points="179.03,-266.36 186.57,-273.8 185.32,-263.28 179.03,-266.36"/> +<text text-anchor="middle" x="152.36" y="-212.67" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Loop6 --> +<g id="node3" class="node"> +<title>Loop6</title> +<polygon fill="yellow" stroke="black" points="72,-568 18,-568 18,-532 72,-532 72,-568"/> +<text text-anchor="middle" x="45" y="-546.3" font-family="Times,serif" font-size="14.00">Loop</text> +</g> +<!-- Loop6->Start2 --> +<g id="edge2" class="edge"> +<title>Loop6->Start2:p0</title> +<path fill="none" stroke="red" d="M46.96,-568.06C49.95,-586.19 57.29,-613.28 74.85,-620.93"/> +<polygon fill="red" stroke="red" points="74.5,-624.43 85,-623 75.9,-617.57 74.5,-624.43"/> +<text text-anchor="middle" x="43.96" y="-570.66" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region38 --> +<g id="node17" class="node"> +<title>Region38</title> +<polygon fill="yellow" stroke="black" points="274,-52 208,-52 208,-16 274,-16 274,-52"/> +<text text-anchor="middle" x="241" y="-30.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Loop6->Region38 --> +<g id="edge3" class="edge"> +<title>Loop6->Region38</title> +<path fill="none" stroke="red" d="M38.06,-531.98C28.81,-508.26 12.9,-463.71 7,-424 -3.78,-351.47 4.18,-330.31 25,-260 38.69,-213.78 36.96,-197.7 67,-160 103.26,-114.48 160.19,-77.91 198.98,-56.36"/> +<polygon fill="red" stroke="red" points="200.84,-59.33 207.94,-51.46 197.49,-53.18 200.84,-59.33"/> +<text text-anchor="middle" x="35.06" y="-525.58" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_arg8 --> +<g id="node4" class="node"> +<title>Phi_arg8</title> +<ellipse fill="lightyellow" stroke="black" cx="199" cy="-550" rx="37.09" ry="18"/> +<text text-anchor="middle" x="199" y="-546.3" font-family="Times,serif" font-size="14.00">φ_arg</text> +</g> +<!-- Phi_arg8->Start2 --> +<g id="edge5" class="edge"> +<title>Phi_arg8->Start2:p1</title> +<path fill="none" stroke="black" d="M196.84,-568.06C193.65,-586.19 185.98,-613.28 168.23,-620.93"/> +<polygon fill="black" stroke="black" points="167.11,-617.58 158,-623 168.5,-624.44 167.11,-617.58"/> +<text text-anchor="middle" x="193.84" y="-570.66" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_arg8->Loop6 --> +<g id="edge4" class="edge"> +<title>Phi_arg8->Loop6</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M180.53,-534.01C170.46,-526.34 157.34,-517.98 144,-514 121,-507.14 112.65,-506.06 90,-514 82.86,-516.5 76.01,-520.67 69.91,-525.3"/> +<polygon fill="black" stroke="black" points="67.55,-522.71 62.08,-531.78 72.01,-528.1 67.55,-522.71"/> +<text text-anchor="middle" x="177.53" y="-527.61" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Add16 --> +<g id="node9" class="node"> +<title>Add16</title> +<ellipse fill="none" stroke="black" cx="271" cy="-478" rx="27" ry="18"/> +<text text-anchor="middle" x="271" y="-474.3" font-family="Times,serif" font-size="14.00">+</text> +</g> +<!-- Con_9 --> +<g id="node5" class="node"> +<title>Con_9</title> +<ellipse fill="none" stroke="black" cx="117" cy="-550" rx="27" ry="18"/> +<text text-anchor="middle" x="117" y="-546.3" font-family="Times,serif" font-size="14.00">10</text> +</g> +<!-- LT10 --> +<g id="node6" class="node"> +<title>LT10</title> +<ellipse fill="none" stroke="black" cx="99" cy="-478" rx="27" ry="18"/> +<text text-anchor="middle" x="99" y="-474.3" font-family="Times,serif" font-size="14.00"><</text> +</g> +<!-- LT10->Phi_arg8 --> +<g id="edge7" class="edge"> +<title>LT10->Phi_arg8</title> +<path fill="none" stroke="black" d="M116.88,-491.51C131.61,-501.83 152.8,-516.66 169.97,-528.68"/> +<polygon fill="black" stroke="black" points="168.32,-531.8 178.52,-534.66 172.33,-526.06 168.32,-531.8"/> +<text text-anchor="middle" x="113.88" y="-494.11" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- LT10->Con_9 --> +<g id="edge8" class="edge"> +<title>LT10->Con_9</title> +<path fill="none" stroke="black" d="M103.36,-495.95C105.39,-503.86 107.86,-513.46 110.14,-522.31"/> +<polygon fill="black" stroke="black" points="106.8,-523.4 112.68,-532.21 113.58,-521.65 106.8,-523.4"/> +<text text-anchor="middle" x="100.36" y="-498.55" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If11 --> +<g id="node7" class="node"> +<title>If11</title> +<polygon fill="yellow" stroke="transparent" points="24,-395 24,-420 118,-420 118,-395 24,-395"/> +<polygon fill="none" stroke="black" points="24,-395 24,-420 118,-420 118,-395 24,-395"/> +<text text-anchor="start" x="65.5" y="-403.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="24,-364 24,-395 118,-395 118,-364 24,-364"/> +<polygon fill="yellow" stroke="transparent" points="29,-369 29,-390 69,-390 69,-369 29,-369"/> +<polygon fill="none" stroke="black" points="29,-369 29,-390 69,-390 69,-369 29,-369"/> +<text text-anchor="start" x="32" y="-375.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="69,-369 69,-390 113,-390 113,-369 69,-369"/> +<polygon fill="none" stroke="black" points="69,-369 69,-390 113,-390 113,-369 69,-369"/> +<text text-anchor="start" x="72" y="-375.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If11->Loop6 --> +<g id="edge9" class="edge"> +<title>If11->Loop6</title> +<path fill="none" stroke="red" d="M65.8,-424.19C61.04,-452.77 54.06,-494.64 49.52,-521.86"/> +<polygon fill="red" stroke="red" points="46.05,-521.42 47.86,-531.86 52.95,-522.57 46.05,-521.42"/> +<text text-anchor="middle" x="62.8" y="-426.79" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If11->LT10 --> +<g id="edge10" class="edge"> +<title>If11->LT10</title> +<path fill="none" stroke="black" d="M81.43,-424.28C84.3,-432.9 87.39,-442.17 90.16,-450.49"/> +<polygon fill="black" stroke="black" points="86.87,-451.69 93.36,-460.07 93.51,-449.48 86.87,-451.69"/> +<text text-anchor="middle" x="78.43" y="-426.88" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_15 --> +<g id="node8" class="node"> +<title>Con_15</title> +<ellipse fill="none" stroke="black" cx="281" cy="-550" rx="27" ry="18"/> +<text text-anchor="middle" x="281" y="-546.3" font-family="Times,serif" font-size="14.00">1</text> +</g> +<!-- Add16->Phi_arg8 --> +<g id="edge11" class="edge"> +<title>Add16->Phi_arg8</title> +<path fill="none" stroke="black" d="M249.16,-500.23C240.6,-508.56 230.75,-518.13 222.07,-526.57"/> +<polygon fill="black" stroke="black" points="251.7,-502.65 256.43,-493.17 246.82,-497.63 251.7,-502.65"/> +<polygon fill="black" stroke="black" points="219.53,-524.16 214.8,-533.64 224.41,-529.18 219.53,-524.16"/> +<text text-anchor="middle" x="253.43" y="-495.77" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Add16->Con_15 --> +<g id="edge12" class="edge"> +<title>Add16->Con_15</title> +<path fill="none" stroke="black" d="M273.42,-495.95C274.52,-503.65 275.85,-512.97 277.09,-521.64"/> +<polygon fill="black" stroke="black" points="273.65,-522.32 278.53,-531.72 280.58,-521.33 273.65,-522.32"/> +<text text-anchor="middle" x="270.42" y="-498.55" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Con_17 --> +<g id="node10" class="node"> +<title>Con_17</title> +<ellipse fill="none" stroke="black" cx="171" cy="-478" rx="27" ry="18"/> +<text text-anchor="middle" x="171" y="-474.3" font-family="Times,serif" font-size="14.00">5</text> +</g> +<!-- EQ18 --> +<g id="node11" class="node"> +<title>EQ18</title> +<ellipse fill="none" stroke="black" cx="171" cy="-392" rx="27" ry="18"/> +<text text-anchor="middle" x="171" y="-388.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQ18->Add16 --> +<g id="edge13" class="edge"> +<title>EQ18->Add16</title> +<path fill="none" stroke="black" d="M187.07,-406.5C203.23,-420.07 228.34,-441.16 246.89,-456.75"/> +<polygon fill="black" stroke="black" points="244.73,-459.51 254.64,-463.26 249.24,-454.15 244.73,-459.51"/> +<text text-anchor="middle" x="184.07" y="-409.1" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQ18->Con_17 --> +<g id="edge14" class="edge"> +<title>EQ18->Con_17</title> +<path fill="none" stroke="black" d="M171,-410.4C171,-421.74 171,-436.77 171,-449.68"/> +<polygon fill="black" stroke="black" points="167.5,-449.9 171,-459.9 174.5,-449.9 167.5,-449.9"/> +<text text-anchor="middle" x="168" y="-413" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If19 --> +<g id="node12" class="node"> +<title>If19</title> +<polygon fill="yellow" stroke="transparent" points="42,-295 42,-320 136,-320 136,-295 42,-295"/> +<polygon fill="none" stroke="black" points="42,-295 42,-320 136,-320 136,-295 42,-295"/> +<text text-anchor="start" x="83.5" y="-303.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="42,-264 42,-295 136,-295 136,-264 42,-264"/> +<polygon fill="yellow" stroke="transparent" points="47,-269 47,-290 87,-290 87,-269 47,-269"/> +<polygon fill="none" stroke="black" points="47,-269 47,-290 87,-290 87,-269 47,-269"/> +<text text-anchor="start" x="50" y="-275.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="87,-269 87,-290 131,-290 131,-269 87,-269"/> +<polygon fill="none" stroke="black" points="87,-269 87,-290 131,-290 131,-269 87,-269"/> +<text text-anchor="start" x="90" y="-275.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If19->If11 --> +<g id="edge15" class="edge"> +<title>If19->If11:p0</title> +<path fill="none" stroke="red" d="M63.67,-324.33C57.47,-334.31 52,-345.89 49.91,-357.87"/> +<polygon fill="red" stroke="red" points="46.41,-357.73 49,-368 53.38,-358.35 46.41,-357.73"/> +<text text-anchor="middle" x="60.67" y="-326.93" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If19->EQ18 --> +<g id="edge16" class="edge"> +<title>If19->EQ18</title> +<path fill="none" stroke="black" d="M114.95,-324.01C126.8,-338.18 140.6,-354.67 151.55,-367.75"/> +<polygon fill="black" stroke="black" points="149.18,-370.37 158.28,-375.8 154.54,-365.88 149.18,-370.37"/> +<text text-anchor="middle" x="111.95" y="-326.61" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_26 --> +<g id="node13" class="node"> +<title>Con_26</title> +<ellipse fill="none" stroke="black" cx="263" cy="-392" rx="27" ry="18"/> +<text text-anchor="middle" x="263" y="-388.3" font-family="Times,serif" font-size="14.00">6</text> +</g> +<!-- EQ27 --> +<g id="node14" class="node"> +<title>EQ27</title> +<ellipse fill="none" stroke="black" cx="273" cy="-292" rx="27" ry="18"/> +<text text-anchor="middle" x="273" y="-288.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQ27->Add16 --> +<g id="edge17" class="edge"> +<title>EQ27->Add16</title> +<path fill="none" stroke="black" d="M281.29,-309.29C287.55,-322.56 295.62,-341.97 299,-360 304.23,-387.96 305.84,-396.39 299,-424 296.57,-433.79 291.97,-443.77 287.18,-452.38"/> +<polygon fill="black" stroke="black" points="284.09,-450.74 282.02,-461.13 290.12,-454.3 284.09,-450.74"/> +<text text-anchor="middle" x="278.29" y="-311.89" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQ27->Con_26 --> +<g id="edge18" class="edge"> +<title>EQ27->Con_26</title> +<path fill="none" stroke="black" d="M271.26,-310.07C269.75,-324.88 267.53,-346.57 265.78,-363.77"/> +<polygon fill="black" stroke="black" points="262.29,-363.49 264.76,-373.8 269.25,-364.2 262.29,-363.49"/> +<text text-anchor="middle" x="268.26" y="-312.67" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If28 --> +<g id="node15" class="node"> +<title>If28</title> +<polygon fill="yellow" stroke="transparent" points="200,-195 200,-220 294,-220 294,-195 200,-195"/> +<polygon fill="none" stroke="black" points="200,-195 200,-220 294,-220 294,-195 200,-195"/> +<text text-anchor="start" x="241.5" y="-203.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="200,-164 200,-195 294,-195 294,-164 200,-164"/> +<polygon fill="yellow" stroke="transparent" points="205,-169 205,-190 245,-190 245,-169 205,-169"/> +<polygon fill="none" stroke="black" points="205,-169 205,-190 245,-190 245,-169 205,-169"/> +<text text-anchor="start" x="208" y="-175.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="245,-169 245,-190 289,-190 289,-169 245,-169"/> +<polygon fill="none" stroke="black" points="245,-169 245,-190 289,-190 289,-169 245,-169"/> +<text text-anchor="start" x="248" y="-175.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If28->If19 --> +<g id="edge19" class="edge"> +<title>If28->If19:p1</title> +<path fill="none" stroke="red" d="M200.79,-224.33C185.31,-235.25 168.15,-247.82 153,-260 146.72,-265.05 145.03,-271.43 141.32,-275.36"/> +<polygon fill="red" stroke="red" points="140.04,-272.1 132,-279 142.59,-278.62 140.04,-272.1"/> +<text text-anchor="middle" x="197.79" y="-226.93" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If28->EQ27 --> +<g id="edge20" class="edge"> +<title>If28->EQ27</title> +<path fill="none" stroke="black" d="M255.23,-224.01C258.67,-236.98 262.63,-251.9 265.93,-264.36"/> +<polygon fill="black" stroke="black" points="262.58,-265.39 268.53,-274.15 269.35,-263.59 262.58,-265.39"/> +<text text-anchor="middle" x="252.23" y="-226.61" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region34 --> +<g id="node16" class="node"> +<title>Region34</title> +<polygon fill="yellow" stroke="black" points="248,-124 182,-124 182,-88 248,-88 248,-124"/> +<text text-anchor="middle" x="215" y="-102.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Region34->If19 --> +<g id="edge21" class="edge"> +<title>Region34->If19:p0</title> +<path fill="none" stroke="red" d="M181.63,-117.1C159.08,-125.42 130.06,-139.26 111,-160 78.33,-195.56 68.34,-213.61 67.13,-257.83"/> +<polygon fill="red" stroke="red" points="63.63,-257.96 67,-268 70.63,-258.05 63.63,-257.96"/> +<text text-anchor="middle" x="178.63" y="-110.7" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region34->If28 --> +<g id="edge22" class="edge"> +<title>Region34->If28:p0</title> +<path fill="none" stroke="red" d="M219.36,-124.23C221.44,-133.63 223.68,-145.75 224.58,-157.66"/> +<polygon fill="red" stroke="red" points="221.1,-158.15 225,-168 228.09,-157.87 221.1,-158.15"/> +<text text-anchor="middle" x="216.36" y="-126.83" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Region38->If28 --> +<g id="edge24" class="edge"> +<title>Region38->If28:p1</title> +<path fill="none" stroke="red" d="M247.09,-52.47C250.45,-62.71 254.45,-75.96 257,-88 263.67,-119.49 266.43,-130.05 266.92,-157.85"/> +<polygon fill="red" stroke="red" points="263.42,-158.03 267,-168 270.42,-157.97 263.42,-158.03"/> +<text text-anchor="middle" x="244.09" y="-55.07" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Region38->Region34 --> +<g id="edge23" class="edge"> +<title>Region38->Region34</title> +<path fill="none" stroke="red" d="M234.57,-52.3C231.64,-60.19 228.11,-69.7 224.86,-78.45"/> +<polygon fill="red" stroke="red" points="221.55,-77.3 221.35,-87.9 228.12,-79.74 221.55,-77.3"/> +<text text-anchor="middle" x="231.57" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Return39->Phi_arg8 --> +<g id="edge26" class="edge"> +<title>Return39->Phi_arg8</title> +<path fill="none" stroke="black" d="M198.96,-310.24C201.84,-323.7 205.48,-342.93 207,-360 212.35,-420.21 211.52,-435.73 207,-496 206.36,-504.48 205.16,-513.66 203.88,-521.96"/> +<polygon fill="black" stroke="black" points="200.42,-521.45 202.25,-531.89 207.32,-522.59 200.42,-521.45"/> +<text text-anchor="middle" x="195.96" y="-312.84" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Return39->If11 --> +<g id="edge25" class="edge"> +<title>Return39->If11:p1</title> +<path fill="none" stroke="red" d="M179.78,-310.4C162.83,-329.64 136.01,-359.63 122.28,-372.63"/> +<polygon fill="red" stroke="red" points="119.79,-370.13 114,-379 124.06,-375.68 119.79,-370.13"/> +<text text-anchor="middle" x="176.78" y="-313" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +</g> +</svg> diff --git a/chapter08/docs/08-graph3.gv b/chapter08/docs/08-graph3.gv new file mode 100644 index 00000000..72ac10a8 --- /dev/null +++ b/chapter08/docs/08-graph3.gv @@ -0,0 +1,111 @@ +digraph chapter08 { +/* +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + break; + if (arg == 6) + break; +} +return arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">Start</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">$ctrl</TD><TD PORT="p1">arg</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Loop6 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_arg8 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + Con_9 [ label="10" ]; + LT10 [ label="<" ]; + If11 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Con_15 [ label="1" ]; + Add16 [ label="+" ]; + Con_17 [ label="5" ]; + EQ18 [ label="==" ]; + If19 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Region25 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_arg26 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + Con_28 [ label="6" ]; + EQ29 [ label="==" ]; + If30 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Region36 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_arg37 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + Return39 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop6;Phi_arg8;} + { rank=same; Region25;Phi_arg26;} + { rank=same; Region36;Phi_arg37;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return39[taillabel=0 color=red]; + Loop6 -> Start2:p0[taillabel=1 color=red]; + Loop6 -> If30:p1[taillabel=2 color=red constraint=false]; + Phi_arg8 -> Loop6 [style=dotted taillabel=0]; + Phi_arg8 -> Start2:p1[taillabel=1]; + Phi_arg8 -> Add16[taillabel=2 constraint=false]; + LT10 -> Phi_arg8[taillabel=1]; + LT10 -> Con_9[taillabel=2]; + If11 -> Loop6[taillabel=0 color=red]; + If11 -> LT10[taillabel=1]; + Add16 -> Phi_arg8[taillabel=1]; + Add16 -> Con_15[taillabel=2]; + EQ18 -> Add16[taillabel=1]; + EQ18 -> Con_17[taillabel=2]; + If19 -> If11:p0[taillabel=0 color=red]; + If19 -> EQ18[taillabel=1]; + Region25 -> If11:p1[taillabel=1 color=red]; + Region25 -> If19:p0[taillabel=2 color=red]; + Phi_arg26 -> Region25 [style=dotted taillabel=0]; + Phi_arg26 -> Phi_arg8[taillabel=1]; + Phi_arg26 -> Add16[taillabel=2 constraint=false]; + EQ29 -> Add16[taillabel=1]; + EQ29 -> Con_28[taillabel=2]; + If30 -> If19:p1[taillabel=0 color=red]; + If30 -> EQ29[taillabel=1]; + Region36 -> Region25[taillabel=1 color=red]; + Region36 -> If30:p0[taillabel=2 color=red]; + Phi_arg37 -> Region36 [style=dotted taillabel=0]; + Phi_arg37 -> Phi_arg26[taillabel=1]; + Phi_arg37 -> Add16[taillabel=2 constraint=false]; + Return39 -> Region36[taillabel=0 color=red]; + Return39 -> Phi_arg37[taillabel=1]; +}
\ No newline at end of file diff --git a/chapter08/docs/08-graph3.svg b/chapter08/docs/08-graph3.svg new file mode 100644 index 00000000..12aafcc5 --- /dev/null +++ b/chapter08/docs/08-graph3.svg @@ -0,0 +1,386 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 2.43.0 (0) + --> +<!-- Title: chapter08 Pages: 1 --> +<svg width="396pt" height="764pt" + viewBox="0.00 0.00 395.85 764.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 760)"> +<title>chapter08</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-760 391.85,-760 391.85,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-748 378,-748 378,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="44,-711 44,-736 125,-736 125,-711 44,-711"/> +<polygon fill="none" stroke="black" points="44,-711 44,-736 125,-736 125,-711 44,-711"/> +<text text-anchor="start" x="66" y="-719.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="44,-680 44,-711 125,-711 125,-680 44,-680"/> +<polygon fill="yellow" stroke="transparent" points="49,-685 49,-706 89,-706 89,-685 49,-685"/> +<polygon fill="none" stroke="black" points="49,-685 49,-706 89,-706 89,-685 49,-685"/> +<text text-anchor="start" x="52" y="-691.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="89,-685 89,-706 120,-706 120,-685 89,-685"/> +<text text-anchor="start" x="92" y="-691.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- Stop3 --> +<g id="node2" class="node"> +<title>Stop3</title> +<polygon fill="yellow" stroke="black" points="144,-52 90,-52 90,-16 144,-16 144,-52"/> +<text text-anchor="middle" x="117" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return39 --> +<g id="node20" class="node"> +<title>Return39</title> +<polygon fill="yellow" stroke="black" points="150,-124 84,-124 84,-88 150,-88 150,-124"/> +<text text-anchor="middle" x="117" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return39 --> +<g id="edge1" class="edge"> +<title>Stop3->Return39</title> +<path fill="none" stroke="red" d="M117,-52.3C117,-60.02 117,-69.29 117,-77.89"/> +<polygon fill="red" stroke="red" points="113.5,-77.9 117,-87.9 120.5,-77.9 113.5,-77.9"/> +<text text-anchor="middle" x="114" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Loop6 --> +<g id="node3" class="node"> +<title>Loop6</title> +<polygon fill="yellow" stroke="black" points="70,-640 16,-640 16,-604 70,-604 70,-640"/> +<text text-anchor="middle" x="43" y="-618.3" font-family="Times,serif" font-size="14.00">Loop</text> +</g> +<!-- Loop6->Start2 --> +<g id="edge2" class="edge"> +<title>Loop6->Start2:p0</title> +<path fill="none" stroke="red" d="M54.63,-640.06C60.09,-649.38 65.88,-661.53 68.08,-673.99"/> +<polygon fill="red" stroke="red" points="64.6,-674.36 69,-684 71.57,-673.72 64.6,-674.36"/> +<text text-anchor="middle" x="51.63" y="-642.66" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- If30 --> +<g id="node17" class="node"> +<title>If30</title> +<polygon fill="yellow" stroke="transparent" points="220,-267 220,-292 314,-292 314,-267 220,-267"/> +<polygon fill="none" stroke="black" points="220,-267 220,-292 314,-292 314,-267 220,-267"/> +<text text-anchor="start" x="261.5" y="-275.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="220,-236 220,-267 314,-267 314,-236 220,-236"/> +<polygon fill="yellow" stroke="transparent" points="225,-241 225,-262 265,-262 265,-241 225,-241"/> +<polygon fill="none" stroke="black" points="225,-241 225,-262 265,-262 265,-241 225,-241"/> +<text text-anchor="start" x="228" y="-247.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="265,-241 265,-262 309,-262 309,-241 265,-241"/> +<polygon fill="none" stroke="black" points="265,-241 265,-262 309,-262 309,-241 265,-241"/> +<text text-anchor="start" x="268" y="-247.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- Loop6->If30 --> +<g id="edge3" class="edge"> +<title>Loop6->If30:p1</title> +<path fill="none" stroke="red" d="M70.26,-607.38C73.18,-606.15 76.13,-604.99 79,-604 147.07,-580.48 188.31,-621.07 237,-568 257.49,-545.67 264.72,-456.58 247,-432 217.42,-390.95 168.58,-437.05 139,-396 122.37,-372.92 120.93,-353.97 139,-332 191.65,-267.98 269.35,-360.02 322,-296 337.53,-277.12 339.04,-258.53 322,-241 314.29,-233.07 299.85,-228.04 292.15,-231.39"/> +<polygon fill="red" stroke="red" points="289.13,-229.62 287,-240 295.14,-233.22 289.13,-229.62"/> +<text text-anchor="middle" x="73.26" y="-600.98" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_arg8 --> +<g id="node4" class="node"> +<title>Phi_arg8</title> +<ellipse fill="lightyellow" stroke="black" cx="125" cy="-622" rx="37.09" ry="18"/> +<text text-anchor="middle" x="125" y="-618.3" font-family="Times,serif" font-size="14.00">φ_arg</text> +</g> +<!-- Phi_arg8->Start2 --> +<g id="edge5" class="edge"> +<title>Phi_arg8->Start2:p1</title> +<path fill="none" stroke="black" d="M116.4,-639.61C112.12,-649.08 107.5,-661.53 105.74,-674.02"/> +<polygon fill="black" stroke="black" points="102.25,-673.77 105,-684 109.23,-674.29 102.25,-673.77"/> +<text text-anchor="middle" x="113.4" y="-642.21" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_arg8->Loop6 --> +<g id="edge4" class="edge"> +<title>Phi_arg8->Loop6</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M87.77,-622C85.3,-622 82.84,-622 80.37,-622"/> +<polygon fill="black" stroke="black" points="80.23,-618.5 70.23,-622 80.23,-625.5 80.23,-618.5"/> +<text text-anchor="middle" x="84.77" y="-615.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Add16 --> +<g id="node9" class="node"> +<title>Add16</title> +<ellipse fill="none" stroke="black" cx="293" cy="-550" rx="27" ry="18"/> +<text text-anchor="middle" x="293" y="-546.3" font-family="Times,serif" font-size="14.00">+</text> +</g> +<!-- Con_9 --> +<g id="node5" class="node"> +<title>Con_9</title> +<ellipse fill="none" stroke="black" cx="207" cy="-622" rx="27" ry="18"/> +<text text-anchor="middle" x="207" y="-618.3" font-family="Times,serif" font-size="14.00">10</text> +</g> +<!-- LT10 --> +<g id="node6" class="node"> +<title>LT10</title> +<ellipse fill="none" stroke="black" cx="125" cy="-550" rx="27" ry="18"/> +<text text-anchor="middle" x="125" y="-546.3" font-family="Times,serif" font-size="14.00"><</text> +</g> +<!-- LT10->Phi_arg8 --> +<g id="edge7" class="edge"> +<title>LT10->Phi_arg8</title> +<path fill="none" stroke="black" d="M125,-568.3C125,-576.02 125,-585.29 125,-593.89"/> +<polygon fill="black" stroke="black" points="121.5,-593.9 125,-603.9 128.5,-593.9 121.5,-593.9"/> +<text text-anchor="middle" x="122" y="-570.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- LT10->Con_9 --> +<g id="edge8" class="edge"> +<title>LT10->Con_9</title> +<path fill="none" stroke="black" d="M141.2,-564.83C153.18,-575.06 169.69,-589.15 183.18,-600.66"/> +<polygon fill="black" stroke="black" points="181.23,-603.61 191.11,-607.44 185.78,-598.28 181.23,-603.61"/> +<text text-anchor="middle" x="138.2" y="-567.43" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If11 --> +<g id="node7" class="node"> +<title>If11</title> +<polygon fill="yellow" stroke="transparent" points="44,-467 44,-492 138,-492 138,-467 44,-467"/> +<polygon fill="none" stroke="black" points="44,-467 44,-492 138,-492 138,-467 44,-467"/> +<text text-anchor="start" x="85.5" y="-475.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="44,-436 44,-467 138,-467 138,-436 44,-436"/> +<polygon fill="yellow" stroke="transparent" points="49,-441 49,-462 89,-462 89,-441 49,-441"/> +<polygon fill="none" stroke="black" points="49,-441 49,-462 89,-462 89,-441 49,-441"/> +<text text-anchor="start" x="52" y="-447.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="89,-441 89,-462 133,-462 133,-441 89,-441"/> +<polygon fill="none" stroke="black" points="89,-441 89,-462 133,-462 133,-441 89,-441"/> +<text text-anchor="start" x="92" y="-447.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If11->Loop6 --> +<g id="edge9" class="edge"> +<title>If11->Loop6</title> +<path fill="none" stroke="red" d="M81.4,-496.19C72.57,-524.89 59.61,-567.01 51.24,-594.22"/> +<polygon fill="red" stroke="red" points="47.87,-593.27 48.27,-603.86 54.56,-595.33 47.87,-593.27"/> +<text text-anchor="middle" x="78.4" y="-498.79" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If11->LT10 --> +<g id="edge10" class="edge"> +<title>If11->LT10</title> +<path fill="none" stroke="black" d="M103.66,-496.28C107.24,-505.13 111.1,-514.66 114.54,-523.15"/> +<polygon fill="black" stroke="black" points="111.34,-524.59 118.34,-532.54 117.83,-521.96 111.34,-524.59"/> +<text text-anchor="middle" x="100.66" y="-498.88" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_15 --> +<g id="node8" class="node"> +<title>Con_15</title> +<ellipse fill="none" stroke="black" cx="293" cy="-622" rx="27" ry="18"/> +<text text-anchor="middle" x="293" y="-618.3" font-family="Times,serif" font-size="14.00">1</text> +</g> +<!-- Add16->Phi_arg8 --> +<g id="edge11" class="edge"> +<title>Add16->Phi_arg8</title> +<path fill="none" stroke="black" d="M261.07,-564.31C232.75,-576.1 191.39,-593.34 161.72,-605.7"/> +<polygon fill="black" stroke="black" points="262.81,-567.37 270.69,-560.3 260.11,-560.91 262.81,-567.37"/> +<polygon fill="black" stroke="black" points="160.02,-602.62 152.13,-609.69 162.71,-609.08 160.02,-602.62"/> +<text text-anchor="middle" x="267.69" y="-562.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Add16->Con_15 --> +<g id="edge12" class="edge"> +<title>Add16->Con_15</title> +<path fill="none" stroke="black" d="M293,-568.3C293,-576.02 293,-585.29 293,-593.89"/> +<polygon fill="black" stroke="black" points="289.5,-593.9 293,-603.9 296.5,-593.9 289.5,-593.9"/> +<text text-anchor="middle" x="290" y="-570.9" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Con_17 --> +<g id="node10" class="node"> +<title>Con_17</title> +<ellipse fill="none" stroke="black" cx="201" cy="-550" rx="27" ry="18"/> +<text text-anchor="middle" x="201" y="-546.3" font-family="Times,serif" font-size="14.00">5</text> +</g> +<!-- EQ18 --> +<g id="node11" class="node"> +<title>EQ18</title> +<ellipse fill="none" stroke="black" cx="211" cy="-464" rx="27" ry="18"/> +<text text-anchor="middle" x="211" y="-460.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQ18->Add16 --> +<g id="edge13" class="edge"> +<title>EQ18->Add16</title> +<path fill="none" stroke="black" d="M225.28,-479.63C238.1,-492.76 257.09,-512.21 271.7,-527.18"/> +<polygon fill="black" stroke="black" points="269.39,-529.83 278.88,-534.54 274.4,-524.94 269.39,-529.83"/> +<text text-anchor="middle" x="222.28" y="-482.23" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQ18->Con_17 --> +<g id="edge14" class="edge"> +<title>EQ18->Con_17</title> +<path fill="none" stroke="black" d="M208.98,-482C207.61,-493.5 205.77,-508.93 204.2,-522.08"/> +<polygon fill="black" stroke="black" points="200.73,-521.68 203.02,-532.03 207.68,-522.51 200.73,-521.68"/> +<text text-anchor="middle" x="205.98" y="-484.6" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If19 --> +<g id="node12" class="node"> +<title>If19</title> +<polygon fill="yellow" stroke="transparent" points="156,-367 156,-392 250,-392 250,-367 156,-367"/> +<polygon fill="none" stroke="black" points="156,-367 156,-392 250,-392 250,-367 156,-367"/> +<text text-anchor="start" x="197.5" y="-375.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="156,-336 156,-367 250,-367 250,-336 156,-336"/> +<polygon fill="yellow" stroke="transparent" points="161,-341 161,-362 201,-362 201,-341 161,-341"/> +<polygon fill="none" stroke="black" points="161,-341 161,-362 201,-362 201,-341 161,-341"/> +<text text-anchor="start" x="164" y="-347.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="201,-341 201,-362 245,-362 245,-341 201,-341"/> +<polygon fill="none" stroke="black" points="201,-341 201,-362 245,-362 245,-341 201,-341"/> +<text text-anchor="start" x="204" y="-347.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If19->If11 --> +<g id="edge15" class="edge"> +<title>If19->If11:p0</title> +<path fill="none" stroke="red" d="M147.72,-384.8C116.87,-397.31 82.59,-414.16 72.17,-430.48"/> +<polygon fill="red" stroke="red" points="68.84,-429.41 69,-440 75.48,-431.62 68.84,-429.41"/> +<text text-anchor="middle" x="144.72" y="-378.4" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If19->EQ18 --> +<g id="edge16" class="edge"> +<title>If19->EQ18</title> +<path fill="none" stroke="black" d="M205.53,-396.01C206.57,-408.76 207.77,-423.4 208.77,-435.73"/> +<polygon fill="black" stroke="black" points="205.3,-436.19 209.6,-445.87 212.28,-435.62 205.3,-436.19"/> +<text text-anchor="middle" x="202.53" y="-398.61" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region25 --> +<g id="node13" class="node"> +<title>Region25</title> +<polygon fill="yellow" stroke="black" points="194,-282 128,-282 128,-246 194,-246 194,-282"/> +<text text-anchor="middle" x="161" y="-260.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Region25->If11 --> +<g id="edge17" class="edge"> +<title>Region25->If11:p1</title> +<path fill="none" stroke="red" d="M149.15,-282.07C140.7,-295.13 129.84,-313.92 124,-332 110.25,-374.59 110.82,-389.45 110.98,-429.78"/> +<polygon fill="red" stroke="red" points="107.48,-430.01 111,-440 114.48,-429.99 107.48,-430.01"/> +<text text-anchor="middle" x="146.15" y="-284.67" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region25->If19 --> +<g id="edge18" class="edge"> +<title>Region25->If19:p0</title> +<path fill="none" stroke="red" d="M168.33,-282.23C173.11,-294.76 178.75,-312.49 180.47,-329.86"/> +<polygon fill="red" stroke="red" points="176.99,-330.19 181,-340 183.98,-329.83 176.99,-330.19"/> +<text text-anchor="middle" x="165.33" y="-284.83" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_arg26 --> +<g id="node14" class="node"> +<title>Phi_arg26</title> +<ellipse fill="lightyellow" stroke="black" cx="73" cy="-264" rx="37.09" ry="18"/> +<text text-anchor="middle" x="73" y="-260.3" font-family="Times,serif" font-size="14.00">φ_arg</text> +</g> +<!-- Phi_arg26->Phi_arg8 --> +<g id="edge20" class="edge"> +<title>Phi_arg26->Phi_arg8</title> +<path fill="none" stroke="black" d="M63.83,-281.65C43.83,-320.21 0.18,-418.31 27,-496 41.37,-537.63 75.96,-575.97 99.94,-598.92"/> +<polygon fill="black" stroke="black" points="97.62,-601.54 107.31,-605.82 102.4,-596.43 97.62,-601.54"/> +<text text-anchor="middle" x="60.83" y="-284.25" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_arg26->Add16 --> +<g id="edge21" class="edge"> +<title>Phi_arg26->Add16</title> +<path fill="none" stroke="black" d="M91.19,-280C99.25,-285.9 109.13,-292.16 119,-296 169.26,-315.55 323.81,-291.14 359,-332 470,-460.89 226.92,-368.94 175,-432 156.92,-453.96 159.55,-472.12 175,-496 184.72,-511.01 228.01,-527.86 259.35,-538.45"/> +<polygon fill="black" stroke="black" points="258.45,-541.84 269.04,-541.65 260.65,-535.19 258.45,-541.84"/> +<text text-anchor="middle" x="88.19" y="-282.6" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_arg26->Region25 --> +<g id="edge19" class="edge"> +<title>Phi_arg26->Region25</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M110.12,-264C112.58,-264 115.04,-264 117.5,-264"/> +<polygon fill="black" stroke="black" points="117.61,-267.5 127.61,-264 117.61,-260.5 117.61,-267.5"/> +<text text-anchor="middle" x="113.12" y="-257.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Con_28 --> +<g id="node15" class="node"> +<title>Con_28</title> +<ellipse fill="none" stroke="black" cx="343" cy="-464" rx="27" ry="18"/> +<text text-anchor="middle" x="343" y="-460.3" font-family="Times,serif" font-size="14.00">6</text> +</g> +<!-- EQ29 --> +<g id="node16" class="node"> +<title>EQ29</title> +<ellipse fill="none" stroke="black" cx="323" cy="-364" rx="27" ry="18"/> +<text text-anchor="middle" x="323" y="-360.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQ29->Add16 --> +<g id="edge22" class="edge"> +<title>EQ29->Add16</title> +<path fill="none" stroke="black" d="M318.38,-381.96C314.84,-395.44 310.07,-414.81 307,-432 301.54,-462.56 297.63,-498.01 295.36,-521.8"/> +<polygon fill="black" stroke="black" points="291.86,-521.58 294.43,-531.86 298.83,-522.22 291.86,-521.58"/> +<text text-anchor="middle" x="315.38" y="-384.56" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQ29->Con_28 --> +<g id="edge23" class="edge"> +<title>EQ29->Con_28</title> +<path fill="none" stroke="black" d="M326.48,-382.07C329.52,-396.97 333.99,-418.83 337.51,-436.08"/> +<polygon fill="black" stroke="black" points="334.13,-437.03 339.56,-446.13 340.99,-435.63 334.13,-437.03"/> +<text text-anchor="middle" x="323.48" y="-384.67" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If30->If19 --> +<g id="edge24" class="edge"> +<title>If30->If19:p1</title> +<path fill="none" stroke="red" d="M238.89,-296.32C232.15,-306.21 226.24,-317.72 223.98,-329.78"/> +<polygon fill="red" stroke="red" points="220.47,-329.71 223,-340 227.44,-330.38 220.47,-329.71"/> +<text text-anchor="middle" x="235.89" y="-298.92" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If30->EQ29 --> +<g id="edge25" class="edge"> +<title>If30->EQ29</title> +<path fill="none" stroke="black" d="M284.72,-296.01C292.51,-309.64 301.52,-325.42 308.85,-338.24"/> +<polygon fill="black" stroke="black" points="305.85,-340.04 313.85,-346.98 311.92,-336.56 305.85,-340.04"/> +<text text-anchor="middle" x="281.72" y="-298.61" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region36 --> +<g id="node18" class="node"> +<title>Region36</title> +<polygon fill="yellow" stroke="black" points="194,-196 128,-196 128,-160 194,-160 194,-196"/> +<text text-anchor="middle" x="161" y="-174.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Region36->Region25 --> +<g id="edge26" class="edge"> +<title>Region36->Region25</title> +<path fill="none" stroke="red" d="M161,-196.4C161,-207.74 161,-222.77 161,-235.68"/> +<polygon fill="red" stroke="red" points="157.5,-235.9 161,-245.9 164.5,-235.9 157.5,-235.9"/> +<text text-anchor="middle" x="158" y="-199" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region36->If30 --> +<g id="edge27" class="edge"> +<title>Region36->If30:p0</title> +<path fill="none" stroke="red" d="M174.84,-196.06C187.5,-211.53 205.8,-233.52 216.25,-244.39"/> +<polygon fill="red" stroke="red" points="214.12,-247.18 224,-251 218.66,-241.85 214.12,-247.18"/> +<text text-anchor="middle" x="171.84" y="-198.66" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_arg37 --> +<g id="node19" class="node"> +<title>Phi_arg37</title> +<ellipse fill="lightyellow" stroke="black" cx="73" cy="-178" rx="37.09" ry="18"/> +<text text-anchor="middle" x="73" y="-174.3" font-family="Times,serif" font-size="14.00">φ_arg</text> +</g> +<!-- Phi_arg37->Add16 --> +<g id="edge30" class="edge"> +<title>Phi_arg37->Add16</title> +<path fill="none" stroke="black" d="M54.57,-194.1C44.32,-203.73 32.54,-217.16 27,-232 17.05,-258.65 8.44,-274.45 27,-296 97.38,-377.73 191.87,-254.61 267,-332 280.01,-345.4 288.39,-466.53 291.56,-521.77"/> +<polygon fill="black" stroke="black" points="288.07,-522.09 292.13,-531.88 295.06,-521.7 288.07,-522.09"/> +<text text-anchor="middle" x="51.57" y="-196.7" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_arg37->Phi_arg26 --> +<g id="edge29" class="edge"> +<title>Phi_arg37->Phi_arg26</title> +<path fill="none" stroke="black" d="M73,-196.4C73,-207.74 73,-222.77 73,-235.68"/> +<polygon fill="black" stroke="black" points="69.5,-235.9 73,-245.9 76.5,-235.9 69.5,-235.9"/> +<text text-anchor="middle" x="70" y="-199" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_arg37->Region36 --> +<g id="edge28" class="edge"> +<title>Phi_arg37->Region36</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M110.12,-178C112.58,-178 115.04,-178 117.5,-178"/> +<polygon fill="black" stroke="black" points="117.61,-181.5 127.61,-178 117.61,-174.5 117.61,-181.5"/> +<text text-anchor="middle" x="113.12" y="-171.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return39->Region36 --> +<g id="edge31" class="edge"> +<title>Return39->Region36</title> +<path fill="none" stroke="red" d="M127.88,-124.3C132.99,-132.44 139.2,-142.31 144.84,-151.3"/> +<polygon fill="red" stroke="red" points="141.96,-153.29 150.25,-159.9 147.89,-149.57 141.96,-153.29"/> +<text text-anchor="middle" x="124.88" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return39->Phi_arg37 --> +<g id="edge32" class="edge"> +<title>Return39->Phi_arg37</title> +<path fill="none" stroke="black" d="M106.12,-124.3C100.93,-132.56 94.62,-142.61 88.9,-151.7"/> +<polygon fill="black" stroke="black" points="85.81,-150.05 83.45,-160.38 91.73,-153.77 85.81,-150.05"/> +<text text-anchor="middle" x="103.12" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +</g> +</svg> diff --git a/chapter08/docs/build-graphs.sh b/chapter08/docs/build-graphs.sh index 73c39624..f660790b 100644 --- a/chapter08/docs/build-graphs.sh +++ b/chapter08/docs/build-graphs.sh @@ -1,3 +1,6 @@ -dot -Tsvg 07-graph1.gv > 07-graph1.svg +dot -Tsvg 08-graph1.gv > 08-graph1.svg +dot -Tsvg 08-graph2.gv > 08-graph2.svg +dot -Tsvg 08-graph3.gv > 08-graph3.svg + diff --git a/chapter08/src/main/java/com/seaofnodes/simple/GraphEvaluator.java b/chapter08/src/main/java/com/seaofnodes/simple/GraphEvaluator.java new file mode 100644 index 00000000..cbd6f1f9 --- /dev/null +++ b/chapter08/src/main/java/com/seaofnodes/simple/GraphEvaluator.java @@ -0,0 +1,175 @@ +package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.TypeInteger;
+
+import java.util.Arrays;
+import java.util.BitSet;
+import java.util.HashMap;
+
+public class GraphEvaluator {
+
+ /**
+ * Find the start node from some node in the graph or null if there is no start node
+ */
+ private static StartNode findStart(BitSet visit, Node node) {
+ if (node == null) return null;
+ if (node instanceof StartNode start) return start;
+ if( visit.get(node._nid) ) return null;
+ visit.set(node._nid);
+ for( Node def : node._inputs ) {
+ var res = findStart(visit,def);
+ if( res != null ) return res;
+ }
+ for( Node use : node._outputs ) {
+ var res = findStart(visit,use);
+ if( res != null ) return res;
+ }
+ return null;
+ }
+
+ /**
+ * Find the control output from a control node
+ */
+ private static Node findControl(Node control) {
+ for( Node use : control._outputs ) {
+ if (use.isCFG()) return use;
+ }
+ return null;
+ }
+
+ /**
+ * Find the projection for a node
+ */
+ private static ProjNode findProjection(Node node, int idx) {
+ for( Node use : node._outputs ) {
+ if (use instanceof ProjNode proj && proj._idx == idx) return proj;
+ }
+ return null;
+ }
+
+ private static RuntimeException timeout() {
+ return new RuntimeException("Timeout");
+ }
+
+ /**
+ * Cache values for phi and parameter projection nodes.
+ */
+ private final HashMap<Node, Long> cacheValues = new HashMap<>();
+ /**
+ * Cache for loop phis as they can depend on itself or other loop phis
+ */
+ private long[] loopPhiCache = new long[16];
+
+ private GraphEvaluator() {
+ }
+
+ private long div(DivNode div) {
+ long in2 = getValue(div.in(2));
+ return in2 == 0 ? 0 : getValue(div.in(1)) / in2;
+ }
+
+ /**
+ * Calculate the value of a node
+ */
+ private long getValue(Node node) {
+ var cache = cacheValues.get(node);
+ if (cache != null) return cache;
+ return switch (node) {
+ case ConstantNode cons -> ((TypeInteger)cons.compute()).value();
+ case AddNode add -> getValue(add.in(1)) + getValue(add.in(2));
+ case BoolNode.EQ eq -> getValue(eq.in(1)) == getValue(eq.in(2)) ? 1 : 0;
+ case BoolNode.LE le -> getValue(le.in(1)) <= getValue(le.in(2)) ? 1 : 0;
+ case BoolNode.LT lt -> getValue(lt.in(1)) < getValue(lt.in(2)) ? 1 : 0;
+ case DivNode div -> div(div);
+ case MinusNode minus -> -getValue(minus.in(1));
+ case MulNode mul -> getValue(mul.in(1)) * getValue(mul.in(2));
+ case NotNode not -> getValue(not.in(1)) == 0 ? 1 : 0;
+ case SubNode sub -> getValue(sub.in(1)) - getValue(sub.in(2));
+ default -> throw Utils.TODO("Unexpected node " + node);
+ };
+ }
+
+ /**
+ * Special case of latchPhis when phis can depend on phis of the same region.
+ */
+ private void latchLoopPhis(RegionNode region, Node prev) {
+ int idx = Utils.find(region._inputs, prev);
+ assert idx > 0;
+ int i = 0;
+ for( Node use : region._outputs ) {
+ if (use instanceof PhiNode phi) {
+ var value = getValue(phi.in(idx));
+ if (i == loopPhiCache.length) loopPhiCache = Arrays.copyOf(loopPhiCache, loopPhiCache.length*2);
+ loopPhiCache[i++] = value;
+ }
+ }
+ i = 0;
+ for( Node use : region._outputs ) {
+ if (use instanceof PhiNode phi) cacheValues.put(phi, loopPhiCache[i++]);
+ }
+ }
+
+ /**
+ * Calculate the values of phis of the region and caches the values. The phis are not allowed to depend on other phis of the region.
+ */
+ private void latchPhis(RegionNode region, Node prev) {
+ int idx = Utils.find(region._inputs, prev);
+ assert idx > 0;
+ for( Node use : region._outputs ) {
+ if (use instanceof PhiNode phi) {
+ var value = getValue(phi.in(idx));
+ cacheValues.put(phi, value);
+ }
+ }
+ }
+
+ /**
+ * Run the graph until either a return is found or the number of loop iterations are done.
+ */
+ private long evaluate(StartNode start, long parameter, int loops) {
+ var parameter1 = findProjection(start, 1);
+ if (parameter1 != null) cacheValues.put(parameter1, parameter);
+ Node control = findProjection(start, 0);
+ Node prev = start;
+ while (control != null) {
+ Node next;
+ switch (control) {
+ case RegionNode region -> {
+ if (region instanceof LoopNode && region.in(1) != prev) {
+ if (loops--<=0) throw timeout();
+ latchLoopPhis(region, prev);
+ } else {
+ latchPhis(region, prev);
+ }
+ next = findControl(region);
+ }
+ case IfNode cond -> next = findProjection(cond, getValue(cond.in(1)) != 0 ? 0 : 1);
+ case ReturnNode ret -> {
+ return getValue(ret.in(1));
+ }
+ case ProjNode ignored -> next = findControl(control);
+ default -> throw Utils.TODO("Unexpected control node " + control);
+ }
+ prev = control;
+ control = next;
+ }
+ return 0;
+ }
+
+ public static long evaluate(Node graph) {
+ return evaluate(graph, 0);
+ }
+
+ public static long evaluate(Node graph, long parameter) {
+ return evaluate(graph, parameter, 1000);
+ }
+
+ public static long evaluate(Node graph, long parameter, int loops) {
+ var start = findStart(new BitSet(), graph);
+ if (start == null) throw timeout();
+ var evaluator = new GraphEvaluator();
+ return evaluator.evaluate(start, parameter, loops);
+ }
+
+}
diff --git a/chapter08/src/main/java/com/seaofnodes/simple/Parser.java b/chapter08/src/main/java/com/seaofnodes/simple/Parser.java index 41803f24..45332396 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/Parser.java @@ -13,7 +13,6 @@ import java.util.*; * This is a simple recursive descent parser. All lexical analysis is done here as well. */ public class Parser { - public static boolean LAZY = false; /** * A Global Static, unique to each compilation. This is a public, so we @@ -47,6 +46,8 @@ public class Parser { * List of keywords disallowed as identifiers */ private final HashSet<String> KEYWORDS = new HashSet<>(){{ + add("break"); + add("continue"); add("else"); add("false"); add("if"); @@ -63,10 +64,14 @@ public class Parser { */ public final Stack<ScopeNode> _xScopes = new Stack<>(); + ScopeNode _continueScope; + ScopeNode _breakScope; + public Parser(String source, TypeInteger arg) { Node.reset(); _lexer = new Lexer(source); _scope = new ScopeNode(); + _continueScope = _breakScope = null; START = new StartNode(new Type[]{ Type.CONTROL, arg }); STOP = new StopNode(); } @@ -137,6 +142,8 @@ public class Parser { else if (match ("{" )) return require(parseBlock(),"}"); else if (matchx("if" )) return parseIf(); else if (matchx("while")) return parseWhile(); + else if (matchx("break")) return parseBreak(); + else if (matchx("continue")) return parseContinue(); else if (matchx("#showGraph")) return require(showGraph(),";"); else return parseExpressionStatement(); } @@ -150,65 +157,104 @@ public class Parser { * @return a {@link Node}, never {@code null} */ private Node parseWhile() { + + var savedContinueScope = _continueScope; + var savedBreakScope = _breakScope; + require("("); // Loop region has two control inputs, the first is the entry // point, and second is back edge that is set after loop is parsed // (see end_loop() call below). Note that the absence of back edge is // used as an indicator to switch off peepholes of the region and - // associated phis. + // associated phis; see {@code inProgress()}. - ctrl(new LoopNode(ctrl(),null).peephole()); // Note we set back edge to null here + ctrl(new LoopNode(ctrl()).peephole()); // Note we set back edge to null here // At loop head, we clone the current Scope (this includes all // names in every nesting level within the Scope). // We create phis eagerly for all the names we find, see dup(). // Save the current scope as the loop head - ScopeNode head = _xScopes.push(_scope).keep(); + ScopeNode head = _scope.keep(); // Clone the head Scope to create a new Scope for the body. // Create phis eagerly as part of cloning - _scope = _scope.dup(true); // The true argument triggers creating phis + _xScopes.push(_scope = _scope.dup(true)); // The true argument triggers creating phis // Parse predicate var pred = require(parseExpression(), ")"); // IfNode takes current control and predicate - IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).<IfNode>keep().peephole(); + IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).keep().peephole(); // Setup projection nodes Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); ifNode.unkeep(); Node ifF = new ProjNode(ifNode, 1, "False").peephole(); - // Clone the body Scope to create the exit Scope - // which accounts for any side effects in the predicate - // The exit Scope will be the final scope after the loop, - // And its control input is the False branch of the loop predicate - // Note that body Scope is still our current scope - var exit = _scope.dup(); - _xScopes.push(exit); - exit.ctrl(ifF); + // Clone the body Scope to create the break/exit Scope which accounts for any + // side effects in the predicate. The break/exit Scope will be the final + // scope after the loop, and its control input is the False branch of + // the loop predicate. Note that body Scope is still our current scope. + ctrl(ifF); + _xScopes.push(_breakScope = _scope.dup()); + // No continues yet + _continueScope = null; + // Parse the true side, which corresponds to loop body // Our current scope is the body Scope ctrl(ifT); // set ctrl token to ifTrue projection parseStatement(); // Parse loop body - // The true branch loops back, so whatever is current control (_scope.ctrl) gets - // added to head loop as input. endLoop() updates the head scope, - // and goes through all the phis that were created earlier. For each - // phi, it sets the second input to the corresponding input from the back edge. - // If the phi is redundant, it is replaced by its sole input. + // Merge the loop bottom into other continue statements + if (_continueScope != null) { + _continueScope = jumpTo(_continueScope); + _scope.kill(); + _scope = _continueScope; + } + + // The true branch loops back, so whatever is current _scope.ctrl gets + // added to head loop as input. endLoop() updates the head scope, and + // goes through all the phis that were created earlier. For each phi, + // it sets the second input to the corresponding input from the back + // edge. If the phi is redundant, it is replaced by its sole input. + var exit = _breakScope; head.endLoop(_scope, exit); head.unkeep().kill(); _xScopes.pop(); // Cleanup _xScopes.pop(); // Cleanup + _continueScope = savedContinueScope; + _breakScope = savedBreakScope; + // At exit the false control is the current control, and // the scope is the exit scope after the exit test. - return (_scope = exit); + return _scope = exit; } + private ScopeNode jumpTo(ScopeNode toScope) { + ScopeNode cur = _scope.dup(); + ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill current scope + // Prune nested lexical scopes that have depth > than the loop head + // We use _breakScope as a proxy for the loop head scope to obtain the depth + while( cur._scopes.size() > _breakScope._scopes.size() ) + cur.pop(); + // If this is a continue then first time the target is null + // So we just use the pruned current scope as the base for the + // continue + if (toScope == null) + return cur; + // toScope is either the break scope, or a scope that was created here + assert toScope._scopes.size() <= _breakScope._scopes.size(); + toScope.mergeScopes(cur); + return toScope; + } + + private void checkLoopActive() { if (_breakScope == null) throw Parser.error("No active loop for a break or continue"); } + + private Node parseBreak () { checkLoopActive(); return ( _breakScope = require(jumpTo( _breakScope ),";")); } + private Node parseContinue() { checkLoopActive(); return (_continueScope = require(jumpTo( _continueScope ),";")); } + /** * Parses a statement * @@ -339,10 +385,10 @@ public class Parser { var lhs = parseAddition(); if (match("==")) return new BoolNode.EQ(lhs, parseComparison()).peephole(); if (match("!=")) return new NotNode(new BoolNode.EQ(lhs, parseComparison()).peephole()).peephole(); - if (match("<" )) return new BoolNode.LT(lhs, parseComparison()).peephole(); if (match("<=")) return new BoolNode.LE(lhs, parseComparison()).peephole(); - if (match(">" )) return new BoolNode.LT(parseComparison(), lhs).peephole(); + if (match("<" )) return new BoolNode.LT(lhs, parseComparison()).peephole(); if (match(">=")) return new BoolNode.LE(parseComparison(), lhs).peephole(); + if (match(">" )) return new BoolNode.LT(parseComparison(), lhs).peephole(); return lhs; } @@ -439,7 +485,7 @@ public class Parser { // Require an exact match private void require(String syntax) { require(null, syntax); } - private Node require(Node n, String syntax) { + private <N extends Node> N require(N n, String syntax) { if (match(syntax)) return n; throw errorSyntax(syntax); } @@ -448,7 +494,7 @@ public class Parser { return error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken()); } - static RuntimeException error(String errorMessage) { + public static RuntimeException error( String errorMessage ) { return new RuntimeException(errorMessage); } diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java index eaf19199..0ed32464 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -6,7 +6,7 @@ import java.util.BitSet; public class LoopNode extends RegionNode { - public LoopNode( Node entry, Node back) { super(null,entry,back); } + public LoopNode( Node entry ) { super(null,entry,null); } Node entry() { return in(1); } Node back () { return in(2); } @@ -15,21 +15,9 @@ public class LoopNode extends RegionNode { public String label() { return "Loop"; } @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - return sb.append("Loop").append(_nid); - } - - @Override - public Type compute() { - return inProgress() ? Type.CONTROL : super.compute(); - } - - @Override public Node idealize() { return inProgress() ? null : super.idealize(); } - @Override Node idom() { return entry(); } - - @Override public boolean inProgress() { return back()==null; } + @Override Node idom() { return entry(); } } diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java index 4cd1b3d2..52d4c1e4 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java @@ -153,8 +153,6 @@ public abstract class Node { public int nIns() { return _inputs.size(); } - public Node out(int i) { return _outputs.get(i); } - public int nOuts() { return _outputs.size(); } public boolean isUnused() { return nOuts() == 0; } @@ -229,11 +227,11 @@ public abstract class Node { // Error is 'use' does not exist; ok for 'use' to be null. protected boolean delUse( Node use ) { Utils.del(_outputs, Utils.find(_outputs, use)); - return _outputs.size() == 0; + return _outputs.isEmpty(); } // Shortcut for "popping" n nodes. A "pop" is basically a - // set_def(last,null) followed by lowering the nIns() count. + // setDef(last,null) followed by lowering the nIns() count. void popN(int n) { for( int i=0; i<n; i++ ) { Node old_def = _inputs.removeLast(); @@ -443,7 +441,10 @@ public abstract class Node { * Used to allow repeating tests in the same JVM. This just resets the * Node unique id generator, and is done as part of making a new Parser. */ - public static void reset() { UNIQUE_ID = 1; _disablePeephole=false; } + public static void reset() { + UNIQUE_ID = 1; + _disablePeephole=false; + } /** * Debugging utility to find a Node by index diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 3b793758..00c010b2 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -7,8 +7,9 @@ import java.util.Collection; import java.util.BitSet; public class RegionNode extends Node { - public RegionNode(Node... inputs) { super(inputs); } + public RegionNode(Node... nodes) { super(nodes); } + @Override public String label() { return "Region"; } @@ -22,6 +23,7 @@ public class RegionNode extends Node { @Override public Type compute() { + if( inProgress() ) return Type.CONTROL; Type t = Type.XCONTROL; for (int i = 1; i < nIns(); i++) t = t.meet(in(i)._type); @@ -30,6 +32,7 @@ public class RegionNode extends Node { @Override public Node idealize() { + if( inProgress() ) return null; int path = findDeadInput(); if( path != 0 ) { for( Node phi : _outputs ) @@ -77,5 +80,8 @@ public class RegionNode extends Node { return (_idom=lhs); } - public boolean inProgress() { return false; } + // True if last input is null + public final boolean inProgress() { + return in(nIns()-1) == null; + } } diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 38dfe15d..dfd12253 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -164,25 +164,13 @@ public class ScopeNode extends Node { dup._scopes.push(new HashMap<>(syms)); dup.addDef(ctrl()); // Control input is just copied - for( int i=1; i<nIns(); i++ ) { - if ( !loop ) { dup.addDef(in(i)); } - else if (Parser.LAZY) { - // For lazy phi we need to set a sentinel that will - // trigger phi creation on update - dup.addDef(this); // Add a sentinel which is self - } - else { - String[] names = reverseNames(); // Get the variable names - // Create a phi node with second input as null - to be filled in - // by endLoop() below - dup.addDef(new PhiNode(names[i], ctrl(), in(i), null).peephole()); - // Ensure our node has the same phi in case we created one - setDef(i, dup.in(i)); - } - } + for( int i=1; i<nIns(); i++ ) + // For lazy phis on loops we use a sentinel + // that will trigger phi creation on update + dup.addDef(loop ? this : in(i)); return dup; } - + /** * Merges the names whose node bindings differ, by creating Phi node for such names * The names could occur at all stack levels, but a given name can only differ in the @@ -195,18 +183,11 @@ public class ScopeNode extends Node { RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).keep()); String[] ns = reverseNames(); // Note that we skip i==0, which is bound to '$ctrl' - for (int i = 1; i < nIns(); i++) { - if( in(i) != that.in(i) ) { // No need for redundant Phis + for (int i = 1; i < nIns(); i++) + 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 triger a phi creation - Node phi; - if (Parser.LAZY) - phi = new PhiNode(ns[i], r, this.lookup(ns[i]), that.lookup(ns[i])).peephole(); - else - phi = new PhiNode(ns[i], r, in(i), that.in(i)).peephole(); - setDef(i, phi); - } - } + // by name as it will trigger a phi creation + setDef(i, new PhiNode(ns[i], r, this.lookup(ns[i]), that.lookup(ns[i])).peephole()); that.kill(); // Kill merged scope return r.unkeep().peephole(); } diff --git a/chapter08/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/chapter08/src/test/java/com/seaofnodes/simple/Chapter08Test.java index 6baa8215..16f7e324 100644 --- a/chapter08/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/chapter08/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Assert; import org.junit.Test; import static org.junit.Assert.*; @@ -9,6 +10,197 @@ import static org.junit.Assert.*; public class Chapter08Test { @Test + public void testChapter8Ex6() { + Parser parser = new Parser( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + break; + if (arg == 6) + break; +} +return arg; + """); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Region36,Phi(Region25,Phi(Loop6,arg,(Phi_arg+1)),Add),Add);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof RegionNode); + Assert.assertEquals(5, GraphEvaluator.evaluate(stop, 1)); + Assert.assertEquals(10, GraphEvaluator.evaluate(stop, 6)); + } + + + @Test + public void testChapter8Ex5() { + Parser parser = new Parser( + """ +int a = 1; +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 7) + continue; + a = a + 1; +} +return a; + """); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Loop7,1,Phi(Region42,Phi_a,(Phi_a+1)));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + System.out.println(IRPrinter.prettyPrint(stop,99)); + } + + + @Test + public void testChapter8Ex4() { + Parser parser = new Parser( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + break; +} +return arg; + """); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Region34,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof RegionNode); + } + + @Test + public void testChapter8Ex3() { + Parser parser = new Parser( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 6) + break; +} +return arg; + """); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Region25,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof RegionNode); + } + + + @Test + public void testChapter8Ex2() { + Parser parser = new Parser( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + continue; +} +return arg; + """); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + + @Test + public void testChapter8Ex1() { + Parser parser = new Parser( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; +} +return arg; + """); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testChapter8Regress1() { + Parser parser = new Parser( + """ +while( arg < 10 ) { + int a = arg+2; + if( a > 4 ) + break; +} +return arg; + """); + StopNode stop = parser.parse(true); + assertEquals("return arg;", stop.toString()); + System.out.println(IRPrinter.prettyPrint(stop,99)); + } + + @Test + public void testChapter8BreakOutsideLoop() { + try { + new Parser(""" +if(arg <= 10) { + break; + arg = arg + 1; +} +return arg; +""").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("No active loop for a break or continue",e.getMessage()); + } + } + + @Test + public void testChapter8Regress3() { + Parser parser = new Parser(""" +while(arg < 10) { + break; +} +return arg; +"""); + StopNode stop = parser.parse(true); + assertEquals("return arg;", stop.toString()); + } + + @Test + public void testChapter8Regress4() { + Parser parser = new Parser(""" +int a = 1; +while(arg < 10) { + a = a + 1; + if (arg > 2) { + int a = 17; + break; + } +} +return a; +"""); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Region28,Phi(Loop7,1,(Phi_a+1)),Add);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof RegionNode); + } + + @Test + public void testChapter8Regress5() { + Parser parser = new Parser(""" +int a = 1; +while(1) { + a = a + 1; + if (a<10) continue; + break; +} +return a; +"""); + StopNode stop = parser.parse(true); + assertEquals("return (Phi(Loop7,1,Add)+1);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof RegionNode); + } + + @Test public void testChapter7Example() { Parser parser = new Parser( """ @@ -39,7 +231,7 @@ if(arg){}else{ return a; """); StopNode stop = parser.parse(true); - assertEquals("return Phi(Region23,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString()); + assertEquals("return Phi(Region22,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString()); } @Test @@ -60,7 +252,7 @@ while(i < arg) { return sum; """); StopNode stop = parser.parse(true); - assertEquals("return Phi(Loop8,0,Phi(Loop21,Phi_sum,(Phi(Loop,0,(Phi_j+1))+Phi_sum)));", stop.toString()); + assertEquals("return Phi(Loop8,0,Phi(Loop20,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); System.out.println(IRPrinter.prettyPrint(stop,99)); } @@ -78,7 +270,7 @@ return b; """); Node._disablePeephole = true; StopNode stop = parser.parse(true); - assertEquals("return Phi(Loop8,2,Phi(Region27,Phi_b,4));", stop.toString()); + assertEquals("return Phi(Loop8,2,Phi(Region26,Phi_b,4));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); Node._disablePeephole = false; System.out.println(IRPrinter.prettyPrint(stop,99)); @@ -99,7 +291,7 @@ while(a < 10) { return b; """); StopNode stop = parser.parse(true); - assertEquals("return Phi(Loop8,2,(Phi(Region27,Phi_b,4)+1));", stop.toString()); + assertEquals("return Phi(Loop8,2,(Phi(Region26,Phi_b,4)+1));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); System.out.println(IRPrinter.prettyPrint(stop,99)); } @@ -674,7 +866,18 @@ return a;"""); assertEquals("Undefined name 'b'",e.getMessage()); } } + + @Test + public void testChapter5Regress1() { + try { + new Parser("if(arg==2) int a=1; else int b=2; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Cannot define a new name on one arm of an if",e.getMessage()); + } + } + @Test public void testChapter5BadNum() { try { @@ -957,7 +1160,7 @@ return a;"""); parser.parse(); StartNode start = Parser.START; for( Node use : start._outputs ) - if( use instanceof ConstantNode con ) + if( use instanceof ConstantNode con && con._type instanceof TypeInteger ) assertEquals(TypeInteger.constant(0),con._type); } |
