diff options
44 files changed, 3852 insertions, 322 deletions
diff --git a/Makefile b/Makefile deleted file mode 100644 index c7724bc7..00000000 --- a/Makefile +++ /dev/null @@ -1,98 +0,0 @@ -SHELL := /bin/bash -.DELETE_ON_ERROR: - -# for printing variable values -# usage: make print-VARIABLE -# > VARIABLE = value_of_variable -print-% : ; @echo $* = $($*) - -# literal space -space := $() $() - -# Decide OS-specific questions -# jar-file seperator -ifeq ($(OS),Windows_NT) - SEP = ; -else - SEP = : -endif -# Find a reasonable ctags. -CTAGS = $(shell which ctags) -# Hack for MacOS: /usr/bin/ctags is unfriendly, so look for ctags from brew -ifeq ($(UNAME),Darwin) - CTAGS = $(shell brew list ctags 2> /dev/null | grep bin/ctags) -endif - -# Fun Args to javac. Mostly limit to java8 source definitions, and fairly -# aggressive lint warnings. -JAVAC_ARGS = -g - -# Source code -SIMPLE := com/seaofnodes/simple -SRC := src/main/java -TST := src/test/java -CLZDIR:= build/classes -main_javas := $(wildcard $(SRC)/$(SIMPLE)/*java $(SRC)/$(SIMPLE)/*/*java) -test_javas := $(wildcard $(TST)/$(SIMPLE)/*java $(TST)/$(SIMPLE)/*/*java) -main_classes := $(patsubst $(SRC)/%java,$(CLZDIR)/main/%class,$(main_javas)) -test_classes := $(patsubst $(TST)/%java,$(CLZDIR)/test/%class,$(test_javas)) -test_cp := $(patsubst $(TST)/$(SIMPLE)/%.java,com.seaofnodes.simple.%,$(wildcard $(TST)/$(SIMPLE)/*Test.java)) -classes = $(main_classes) $(test_classes) -# All the libraries -libs = $(wildcard lib/*jar) -jars = $(subst $(space),$(SEP),$(libs)) - - -default_targets := $(main_classes) $(test_classes) -# Optionally add ctags to the default target if a reasonable one was found. -ifneq ($(CTAGS),) -default_targets += tags -endif - -default: $(default_targets) - -# Compile just the out-of-date files -$(main_classes): build/classes/main/%class: $(SRC)/%java - @echo "compiling " $@ " because " $? - @[ -d $(CLZDIR)/main ] || mkdir -p $(CLZDIR)/main - @javac $(JAVAC_ARGS) -cp "$(CLZDIR)/main$(SEP)$(jars)" -sourcepath $(SRC) -d $(CLZDIR)/main $(main_javas) - -$(test_classes): $(CLZDIR)/test/%class: $(TST)/%java $(main_classes) - @echo "compiling " $@ " because " $? - @[ -d $(CLZDIR)/test ] || mkdir -p $(CLZDIR)/test - @javac $(JAVAC_ARGS) -cp "$(CLZDIR)/test$(SEP)$(CLZDIR)/main$(SEP)$(jars)" -sourcepath $(TST) -d $(CLZDIR)/test $(test_javas) - -# Base launch line for JVM tests -JVM=nice java -ea -cp "build/classes/main${SEP}${jars}${SEP}$(CLZDIR)/test" - -tests: $(default_targets) - @echo "testing " $(test_cp) - @$(JVM) org.junit.runner.JUnitCore $(test_cp) - -fuzzer: $(default_targets) - @echo "fuzzing " $(test_cp) - @$(JVM) org.junit.runner.JUnitCore com.seaofnodes.simple.FuzzerWrap - - -.PHONY: clean -clean: - rm -rf build - rm -f TAGS - (find . -name "*~" -exec rm {} \; 2>/dev/null; exit 0) - -# Download libs from maven -lib: lib/junit-4.12.jar lib/hamcrest-core-1.3.jar - -# Jars -lib/junit-4.12.jar: - @[ -d lib ] || mkdir -p lib - @(cd lib; wget https://repo1.maven.org/maven2/junit/junit/4.12/junit-4.12.jar) - -lib/hamcrest-core-1.3.jar: - @[ -d lib ] || mkdir -p lib - @(cd lib; wget https://repo1.maven.org/maven2/org/hamcrest/hamcrest-core/1.3/hamcrest-core-1.3.jar) - -# Build emacs tags (part of a tasty emacs ide experience) -tags: $(main_javas) $(test_javas) - @rm -f TAGS - @$(CTAGS) -e --recurse=yes --extra=+q --fields=+fksaiS $(SRC) $(TST) @@ -46,7 +46,7 @@ The Simple language is styled after a subset of C or Java. named `arg`. Binary and Comparison operators involving constants and `arg`. Non-zero values will be truthy. Peephole optimizations involving algebraic simplifications. -* Chapter 5: `if` statement. CFG construction. +* [Chapter 5](docs/chapter05/README.md): `if` statement. CFG construction. * Chapter 6: Peephole optimization around dead control flow. * Chapter 7: `while` statement; looping constructs - eager phi approach. * Chapter 8: Looping constructs continued, lazy phi creation, `break` and `continue` statements. diff --git a/appendix/dce.md b/appendix/dce.md deleted file mode 100644 index ad5be2d0..00000000 --- a/appendix/dce.md +++ /dev/null @@ -1,166 +0,0 @@ -# Appendix -## Dead Code Elimination(DCE) -Dead Code Elimination is the process or removing nodes that are dead(unused). - -There are two kinds of dead code eliminations present in this chapter. -- Delete unused nodes when popping the scope. -- Delete old nodes after finding a better replacement(after idealize call). - -Both of the methods mentioned above delete the nodes recursively. However, the first case happens -regardless of whether `peephole` is called or not. - -### Delete unused nodes when popping the scope -A node is unused if it has no outputs(users). - -### Example 1: - ``` - int a = 12; // the only output it has is the scope itself - return 1; - ``` -We clearly see `a` is unused. -This gives us the following graph(without DCE): - - - -To remove `a` we introduce the following technique when popping the scope. - - ```java - var ret = (ReturnNode) parseBlock(); - _scope.pop(); - ``` -As of now the end of the program is hard-wired to return, after finishing parsing we pop the scope. -The state of the scope before popping it: - ``` - _scope = {ScopeNode@1422} "Scope[$ctrl:null, arg:arg][a:12]" - 1 = {ProjNode@1528} "arg" - 2 = {ConstantNode@1529} "12" - _inputs = {ArrayList@1523} size = 3 - ``` -The output(s) of `a` - ``` - _outputs = {ArrayList@1544} size = 1 - 0 = {ScopeNode@1422} "Scope[$ctrl:null, arg:arg][a:12]" - ``` -Notice how the only output of `a`is the scope itself. When `a` is introduced, it is added to the -inputs of the scope, and the scope is added to the outputs of `a`(recall use-def chains). - -Since `a` is not being returned - it is unused and can be killed. - -`_scope.pop`: -```java -public void pop() { popN(_scopes.pop().size()); } -``` -`_scope.popN`(responsible for killing the unused nodes *recursively*): -```java -void popN(int n) { - for (int i = 0; i < n; i++) { - Node old_def = _inputs.removeLast(); // start from the back - if (old_def != null && // If it exists and - old_def.delUse(this)) { // If we removed the last use, the old def is now dead - old_def.kill(); // Kill the old def - } - } -} -``` -First, we start off by looping through the inputs of the scope(*remember*: scope is just a node like any other, the symbols of the scope are the inputs). -If the node returned by `removeLast` is not null, and if the only user of `old_def` is the current Node then we can delete it. - -`old_def.delUse(this)` - delete *this* from `old_def`'s outputs. -```java -protected boolean delUse( Node use ) { - Utils.del(_outputs, Utils.find(_outputs, use)); - return _outputs.isEmpty(); - } -``` -Returns true if `_outputs` becomes empty after deleting `use`. -`old_def.kill()` starts the killing process recursively. - -`old_def.kill()` -```java -public void kill( ) { - assert isUnused(); // Has no uses, so it is dead - popN(nIns()); // Set all inputs to null, recursively killing unused Nodes - _type=null; // Flag as dead - assert isDead(); // Really dead now - } -``` -`popN` is called again, our goal is to look for nodes that might also get deleted once `a` is freed. -The only input `a` has is the constant node with value 12. As every other node a `ConstantNode` takes in the control node first(`Start`), once we -drop the `Start` node from the inputs of `ConstantNode`: -``` -Node old_def = _inputs.removeLast(); -``` -we can also get rid of `ConstantNode`(`this`) from the outputs of `Start`: -``` -old_def.delUse(this) -``` -### Example 2: -``` -int a = 12; -int b = a + 1; -return 1; -``` -- Call `popN` on current scope. -- Realize that `b = a + 1;` has no uses - so we can kill it. -- In the kill function we can call `popN` but this time with the inputs of `b = a + 1;`(start killing them recursively) -- We start the killing process from the back and examine "1" first. This has no output other than the `AddNode`. Since `this = AddNode` calling `delUse` will mark "1" as dead. -- We now can kill "1" and call the `popN` function with one input(the control node). -- Now we examine "a" which has 2 uses at this point, the scope and `AddNode`. Since `this = AddNode` we will remove `AddNode` from its outputs, it will still have the scope as a user - so we can't delete it just yet. -- We move onto`a = 12`, since "a" has only one user left(the scope) and `this = scope` it can get killed easily. -- Same as before, we go through the inputs of "a" and will delete them from the outputs of the control node. - -*A constant node pointing to "Start"(ignored by the graph visualizer) but still maintains a connection:* - - - -## Delete old nodes after finding a better replacement -Consider the following code: -``` -return (2+1)+3; -``` -Without DCE after the `idealize` call we would end up with: - - -After identifying a more optimal replacement value (6) for the expression (2 + 1) + 3, -we created a constant node to store this value. -However, we did not remove the original expression, -resulting in dangling nodes in our structure. - -To fix this, we introduce an extra `deadCodeElim` call that is responsible for deleting unused nodes. - - -```java -public final Node peephole( ) { - ... - if (!(this instanceof ConstantNode) && type.isConstant()) - return new deadCodeElim(ConstantNode(type).peephole()); - - ... - - Node n = idealize(); - if( n != null ) // Something changed - // Recursively optimize - return deadCodeElim(n.peephole()); - - ... -} -``` - -```java -// m is the new Node, self is the old. -// Return 'm', which may have zero uses but is alive nonetheless. -// If self has zero uses (and is not 'm'), {@link #kill} self. -private Node deadCodeElim(Node m) { - // If self is going dead and not being returned here (Nodes returned - // from peephole commonly have no uses (yet)), then kill self. - if( m != this && isUnused() ) { - // Killing self - and since self recursively kills self's inputs we - // might end up killing 'm', which we are returning as a live Node. - // So we add a bogus extra null output edge to stop kill(). - m.addUse(null); // Add bogus null use to keep m alive - kill(); // Kill self because replacing with 'm' - m.delUse(null); // Remove bogus null. - } - return m; -} -```
\ No newline at end of file diff --git a/docs/chapter05/05-grammar.md b/docs/chapter05/05-grammar.md new file mode 100644 index 00000000..65be4bf7 --- /dev/null +++ b/docs/chapter05/05-grammar.md @@ -0,0 +1,83 @@ +# Grammar for Chapter 1 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + | ifStatement + | metaStatement + ; + +ifStatement + : 'if' '(' expression ')' statement ('else' statement)? + ; + +metaStatement + : '#showGraph' ';' + ; + +expressionStatement + : IDENTIFIER '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +declStatement + : 'int' IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : comparisonExpression + ; + +comparisonExpression + : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | primaryExpression + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | 'true' + | 'false' + | '(' expression ')' + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +``` diff --git a/docs/chapter05/05-graph1.gv b/docs/chapter05/05-graph1.gv new file mode 100644 index 00000000..539ee7f2 --- /dev/null +++ b/docs/chapter05/05-graph1.gv @@ -0,0 +1,88 @@ +digraph chapter05 { +/* +int a = 1; +if (arg == 1) + a = arg+2; +else { + a = arg-3; + #showGraph; +} +#showGraph; +return a; + +*/ + rankdir=BT; + ordering="in"; + concentrate="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>> + ]; + Con_7 [ label="#1" ]; + EQNode8 [ label="==" ]; + If9 [ 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_13 [ label="#2" ]; + Add14 [ label="+" ]; + Con_15 [ label="#3" ]; + Sub16 [ label="-" ]; + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope1_0_$ctrl">$ctrl</TD><TD PORT="Scope1_0_arg">arg</TD></TR> + </TABLE>>]; + subgraph cluster_Scope1_1 { + Scope1_1 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">1</TD><TD PORT="Scope1_1_a">a</TD></TR> + </TABLE>>]; + } + } + node [shape=plaintext]; + subgraph cluster_Scope12_0 { + Scope12_0 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope12_0_$ctrl">$ctrl</TD><TD PORT="Scope12_0_arg">arg</TD></TR> + </TABLE>>]; + subgraph cluster_Scope12_1 { + Scope12_1 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">1</TD><TD PORT="Scope12_1_a">a</TD></TR> + </TABLE>>]; + } + } + edge [ fontname=Helvetica, fontsize=8 ]; + EQNode8 -> Start2:p1[taillabel=1]; + EQNode8 -> Con_7[taillabel=2]; + If9 -> Start2:p0[taillabel=0; color=red]; + If9 -> EQNode8[taillabel=1]; + Add14 -> Start2:p1[taillabel=1]; + Add14 -> Con_13[taillabel=2]; + Sub16 -> Start2:p1[taillabel=1]; + Sub16 -> Con_15[taillabel=2]; + edge [style=dashed color=cornflowerblue]; + Scope1_0:"Scope1_0_$ctrl" -> If9:p0; + Scope1_0:"Scope1_0_arg" -> Start2:p1; + Scope1_1:"Scope1_1_a" -> Add14; + edge [style=dashed color=cornflowerblue]; + Scope12_0:"Scope12_0_$ctrl" -> If9:p1; + Scope12_0:"Scope12_0_arg" -> Start2:p1; + Scope12_1:"Scope12_1_a" -> Sub16; +} diff --git a/docs/chapter05/05-graph1.svg b/docs/chapter05/05-graph1.svg new file mode 100644 index 00000000..efe0a0e8 --- /dev/null +++ b/docs/chapter05/05-graph1.svg @@ -0,0 +1,228 @@ +<?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: chapter05 Pages: 1 --> +<svg width="432pt" height="356pt" + viewBox="0.00 0.00 432.00 356.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 352)"> +<title>chapter05</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-352 428,-352 428,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="85,-88 85,-340 415,-340 415,-88 85,-88"/> +</g> +<g id="clust2" class="cluster"> +<title>cluster_Scope1_0</title> +<polygon fill="none" stroke="black" points="8,-8 8,-76 208,-76 208,-8 8,-8"/> +</g> +<g id="clust3" class="cluster"> +<title>cluster_Scope1_1</title> +<polygon fill="none" stroke="black" points="16,-16 16,-68 86,-68 86,-16 16,-16"/> +</g> +<g id="clust4" class="cluster"> +<title>cluster_Scope12_0</title> +<polygon fill="none" stroke="black" points="216,-8 216,-76 416,-76 416,-8 216,-8"/> +</g> +<g id="clust5" class="cluster"> +<title>cluster_Scope12_1</title> +<polygon fill="none" stroke="black" points="224,-16 224,-68 294,-68 294,-16 224,-16"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="174,-303 174,-328 255,-328 255,-303 174,-303"/> +<polygon fill="none" stroke="black" points="174,-303 174,-328 255,-328 255,-303 174,-303"/> +<text text-anchor="start" x="196" y="-311.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="174,-272 174,-303 255,-303 255,-272 174,-272"/> +<polygon fill="yellow" stroke="transparent" points="179,-277 179,-298 219,-298 219,-277 179,-277"/> +<polygon fill="none" stroke="black" points="179,-277 179,-298 219,-298 219,-277 179,-277"/> +<text text-anchor="start" x="182" y="-283.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="219,-277 219,-298 250,-298 250,-277 219,-277"/> +<text text-anchor="start" x="222" y="-283.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- Con_7 --> +<g id="node2" class="node"> +<title>Con_7</title> +<ellipse fill="none" stroke="black" cx="308" cy="-300" rx="27" ry="18"/> +<text text-anchor="middle" x="308" y="-296.3" font-family="Times,serif" font-size="14.00">#1</text> +</g> +<!-- EQNode8 --> +<g id="node3" class="node"> +<title>EQNode8</title> +<ellipse fill="none" stroke="black" cx="245" cy="-214" rx="27" ry="18"/> +<text text-anchor="middle" x="245" y="-210.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQNode8->Start2 --> +<g id="edge1" class="edge"> +<title>EQNode8->Start2:p1</title> +<path fill="none" stroke="black" d="M240.7,-231.97C238.58,-241.48 236.3,-253.83 235.4,-265.95"/> +<polygon fill="black" stroke="black" points="231.9,-265.87 235,-276 238.89,-266.15 231.9,-265.87"/> +<text text-anchor="middle" x="237.7" y="-234.57" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQNode8->Con_7 --> +<g id="edge2" class="edge"> +<title>EQNode8->Con_7</title> +<path fill="none" stroke="black" d="M256.56,-230.41C266.06,-243.08 279.67,-261.23 290.51,-275.68"/> +<polygon fill="black" stroke="black" points="287.72,-277.79 296.52,-283.69 293.32,-273.59 287.72,-277.79"/> +<text text-anchor="middle" x="253.56" y="-233.01" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If9 --> +<g id="node4" class="node"> +<title>If9</title> +<polygon fill="yellow" stroke="transparent" points="169,-131 169,-156 263,-156 263,-131 169,-131"/> +<polygon fill="none" stroke="black" points="169,-131 169,-156 263,-156 263,-131 169,-131"/> +<text text-anchor="start" x="210.5" y="-139.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="169,-100 169,-131 263,-131 263,-100 169,-100"/> +<polygon fill="yellow" stroke="transparent" points="174,-105 174,-126 214,-126 214,-105 174,-105"/> +<polygon fill="none" stroke="black" points="174,-105 174,-126 214,-126 214,-105 174,-105"/> +<text text-anchor="start" x="177" y="-111.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="214,-105 214,-126 258,-126 258,-105 214,-105"/> +<polygon fill="none" stroke="black" points="214,-105 214,-126 258,-126 258,-105 214,-105"/> +<text text-anchor="start" x="217" y="-111.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If9->Start2 --> +<g id="edge3" class="edge"> +<title>If9->Start2:p0</title> +<path fill="none" stroke="red" d="M210.29,-160.14C205.78,-187.26 200.08,-228.01 199.14,-265.52"/> +<polygon fill="red" stroke="red" points="195.63,-265.96 199,-276 202.63,-266.05 195.63,-265.96"/> +<text text-anchor="middle" x="207.29" y="-162.74" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If9->EQNode8 --> +<g id="edge4" class="edge"> +<title>If9->EQNode8</title> +<path fill="none" stroke="black" d="M226.8,-160.28C229.78,-168.9 232.97,-178.17 235.85,-186.49"/> +<polygon fill="black" stroke="black" points="232.58,-187.76 239.16,-196.07 239.2,-185.48 232.58,-187.76"/> +<text text-anchor="middle" x="223.8" y="-162.88" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_13 --> +<g id="node5" class="node"> +<title>Con_13</title> +<ellipse fill="none" stroke="black" cx="120" cy="-300" rx="27" ry="18"/> +<text text-anchor="middle" x="120" y="-296.3" font-family="Times,serif" font-size="14.00">#2</text> +</g> +<!-- Add14 --> +<g id="node6" class="node"> +<title>Add14</title> +<ellipse fill="none" stroke="black" cx="153" cy="-214" rx="27" ry="18"/> +<text text-anchor="middle" x="153" y="-210.3" font-family="Times,serif" font-size="14.00">+</text> +</g> +<!-- Add14->Start2 --> +<g id="edge5" class="edge"> +<title>Add14->Start2:p1</title> +<path fill="none" stroke="black" d="M174.12,-225.69C193.67,-236.17 221.18,-252.54 231.18,-266.44"/> +<polygon fill="black" stroke="black" points="228.04,-268.01 235,-276 234.54,-265.42 228.04,-268.01"/> +<text text-anchor="middle" x="171.12" y="-228.29" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Add14->Con_13 --> +<g id="edge6" class="edge"> +<title>Add14->Con_13</title> +<path fill="none" stroke="black" d="M146.48,-231.6C141.87,-243.33 135.59,-259.3 130.31,-272.76"/> +<polygon fill="black" stroke="black" points="126.91,-271.85 126.51,-282.44 133.42,-274.41 126.91,-271.85"/> +<text text-anchor="middle" x="143.48" y="-234.2" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Con_15 --> +<g id="node7" class="node"> +<title>Con_15</title> +<ellipse fill="none" stroke="black" cx="380" cy="-300" rx="27" ry="18"/> +<text text-anchor="middle" x="380" y="-296.3" font-family="Times,serif" font-size="14.00">#3</text> +</g> +<!-- Sub16 --> +<g id="node8" class="node"> +<title>Sub16</title> +<ellipse fill="none" stroke="black" cx="317" cy="-214" rx="27" ry="18"/> +<text text-anchor="middle" x="317" y="-210.3" font-family="Times,serif" font-size="14.00">-</text> +</g> +<!-- Sub16->Start2 --> +<g id="edge7" class="edge"> +<title>Sub16->Start2:p1</title> +<path fill="none" stroke="black" d="M304.31,-229.92C290.9,-245.57 270.14,-269.43 258.76,-280.7"/> +<polygon fill="black" stroke="black" points="256.56,-277.98 251,-287 260.97,-283.41 256.56,-277.98"/> +<text text-anchor="middle" x="301.31" y="-232.52" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Sub16->Con_15 --> +<g id="edge8" class="edge"> +<title>Sub16->Con_15</title> +<path fill="none" stroke="black" d="M328.56,-230.41C338.06,-243.08 351.67,-261.23 362.51,-275.68"/> +<polygon fill="black" stroke="black" points="359.72,-277.79 368.52,-283.69 365.32,-273.59 359.72,-277.79"/> +<text text-anchor="middle" x="325.56" y="-233.01" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Scope1_0 --> +<g id="node9" class="node"> +<title>Scope1_0</title> +<polygon fill="cyan" stroke="transparent" points="105,-31 105,-52 121,-52 121,-31 105,-31"/> +<polygon fill="none" stroke="black" points="105,-31 105,-52 121,-52 121,-31 105,-31"/> +<text text-anchor="start" x="108" y="-37.8" font-family="Times,serif" font-size="14.00">0</text> +<polygon fill="none" stroke="black" points="121,-31 121,-52 161,-52 161,-31 121,-31"/> +<text text-anchor="start" x="124" y="-37.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="161,-31 161,-52 192,-52 192,-31 161,-31"/> +<text text-anchor="start" x="164" y="-37.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- Scope1_0->Start2 --> +<g id="edge10" class="edge"> +<title>Scope1_0:Scope1_0_arg->Start2:p1</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M177,-53C177,-72.12 160.6,-70.93 152,-88 122.36,-146.82 79.43,-177.9 117,-232 146.68,-274.74 223.16,-227.66 233.77,-265.81"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="230.33,-266.49 235,-276 237.28,-265.65 230.33,-266.49"/> +</g> +<!-- Scope1_0->If9 --> +<g id="edge9" class="edge"> +<title>Scope1_0:Scope1_0_$ctrl->If9:p0</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M141,-53C141,-81.73 181.94,-74.1 191.86,-94.03"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="188.48,-94.96 194,-104 195.32,-93.49 188.48,-94.96"/> +</g> +<!-- Scope1_1 --> +<g id="node10" class="node"> +<title>Scope1_1</title> +<polygon fill="cyan" stroke="transparent" points="36,-31 36,-52 52,-52 52,-31 36,-31"/> +<polygon fill="none" stroke="black" points="36,-31 36,-52 52,-52 52,-31 36,-31"/> +<text text-anchor="start" x="39" y="-37.8" font-family="Times,serif" font-size="14.00">1</text> +<polygon fill="none" stroke="black" points="52,-31 52,-52 67,-52 67,-31 52,-31"/> +<text text-anchor="start" x="55" y="-37.8" font-family="Times,serif" font-size="14.00">a</text> +</g> +<!-- Scope1_1->Add14 --> +<g id="edge11" class="edge"> +<title>Scope1_1:Scope1_1_a->Add14</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M60,-53C60,-108.8 102.8,-162.53 130.33,-191.31"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="128.14,-194.07 137.64,-198.75 133.13,-189.17 128.14,-194.07"/> +</g> +<!-- Scope12_0 --> +<g id="node11" class="node"> +<title>Scope12_0</title> +<polygon fill="cyan" stroke="transparent" points="313,-31 313,-52 329,-52 329,-31 313,-31"/> +<polygon fill="none" stroke="black" points="313,-31 313,-52 329,-52 329,-31 313,-31"/> +<text text-anchor="start" x="316" y="-37.8" font-family="Times,serif" font-size="14.00">0</text> +<polygon fill="none" stroke="black" points="329,-31 329,-52 369,-52 369,-31 329,-31"/> +<text text-anchor="start" x="332" y="-37.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="369,-31 369,-52 400,-52 400,-31 369,-31"/> +<text text-anchor="start" x="372" y="-37.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- Scope12_0->Start2 --> +<g id="edge13" class="edge"> +<title>Scope12_0:Scope12_0_arg->Start2:p1</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M385,-53C385,-133.82 402.85,-168.39 353,-232 328.7,-263.01 305.02,-246.51 272,-268 265.41,-272.29 263.77,-278.64 260.39,-282.8"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="258.7,-279.72 251,-287 261.56,-286.11 258.7,-279.72"/> +</g> +<!-- Scope12_0->If9 --> +<g id="edge12" class="edge"> +<title>Scope12_0:Scope12_0_$ctrl->If9:p1</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M349,-53C349,-98.16 313.19,-112.94 269.13,-114.79"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="268.93,-111.3 259,-115 269.07,-118.3 268.93,-111.3"/> +</g> +<!-- Scope12_1 --> +<g id="node12" class="node"> +<title>Scope12_1</title> +<polygon fill="cyan" stroke="transparent" points="244,-31 244,-52 260,-52 260,-31 244,-31"/> +<polygon fill="none" stroke="black" points="244,-31 244,-52 260,-52 260,-31 244,-31"/> +<text text-anchor="start" x="247" y="-37.8" font-family="Times,serif" font-size="14.00">1</text> +<polygon fill="none" stroke="black" points="260,-31 260,-52 275,-52 275,-31 260,-31"/> +<text text-anchor="start" x="263" y="-37.8" font-family="Times,serif" font-size="14.00">a</text> +</g> +<!-- Scope12_1->Sub16 --> +<g id="edge14" class="edge"> +<title>Scope12_1:Scope12_1_a->Sub16</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M268,-53C268,-69.44 275,-72.33 280,-88 290.77,-121.73 302.19,-160.92 309.45,-186.29"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="306.09,-187.29 312.2,-195.95 312.83,-185.37 306.09,-187.29"/> +</g> +</g> +</svg> diff --git a/docs/chapter05/05-graph2.gv b/docs/chapter05/05-graph2.gv new file mode 100644 index 00000000..12506e85 --- /dev/null +++ b/docs/chapter05/05-graph2.gv @@ -0,0 +1,78 @@ +digraph chapter05 { +/* +int a = 1; +if (arg == 1) + a = arg+2; +else { + a = arg-3; + #showGraph; +} +#showGraph; +return a; +*/ + rankdir=BT; + ordering="in"; + concentrate="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>> + ]; + Con_7 [ label="#1" ]; + EQNode8 [ label="==" ]; + If9 [ 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_13 [ label="#2" ]; + Add14 [ label="+" ]; + Con_15 [ label="#3" ]; + Sub16 [ label="-" ]; + Region17 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a18 [ style=filled fillcolor=lightyellow label="φ_a" ]; + { rank=same; Region17;Phi_a18;} + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope1_0_$ctrl">$ctrl</TD><TD PORT="Scope1_0_arg">arg</TD></TR> + </TABLE>>]; + subgraph cluster_Scope1_1 { + Scope1_1 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">1</TD><TD PORT="Scope1_1_a">a</TD></TR> + </TABLE>>]; + } + } + edge [ fontname=Helvetica, fontsize=8 ]; + EQNode8 -> Start2:p1[taillabel=1]; + EQNode8 -> Con_7[taillabel=2]; + If9 -> Start2:p0[taillabel=0 color=red]; + If9 -> EQNode8[taillabel=1]; + Add14 -> Start2:p1[taillabel=1]; + Add14 -> Con_13[taillabel=2]; + Sub16 -> Start2:p1[taillabel=1]; + Sub16 -> Con_15[taillabel=2]; + Region17 -> If9:p0[taillabel=1 color=red]; + Region17 -> If9:p1[taillabel=2 color=red]; + Phi_a18 -> Region17 [style=dotted taillabel=0]; + Phi_a18 -> Add14[taillabel=1]; + Phi_a18 -> Sub16[taillabel=2]; + edge [style=dashed color=cornflowerblue]; + Scope1_0:"Scope1_0_$ctrl" -> Region17; + Scope1_0:"Scope1_0_arg" -> Start2:p1; + Scope1_1:"Scope1_1_a" -> Phi_a18; +} diff --git a/docs/chapter05/05-graph2.svg b/docs/chapter05/05-graph2.svg new file mode 100644 index 00000000..d5e48a9e --- /dev/null +++ b/docs/chapter05/05-graph2.svg @@ -0,0 +1,229 @@ +<?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: chapter05 Pages: 1 --> +<svg width="343pt" height="428pt" + viewBox="0.00 0.00 343.03 428.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 424)"> +<title>chapter05</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-424 339.03,-424 339.03,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-88 8,-412 282,-412 282,-88 8,-88"/> +</g> +<g id="clust3" class="cluster"> +<title>cluster_Scope1_0</title> +<polygon fill="none" stroke="black" points="67,-8 67,-76 267,-76 267,-8 67,-8"/> +</g> +<g id="clust4" class="cluster"> +<title>cluster_Scope1_1</title> +<polygon fill="none" stroke="black" points="75,-16 75,-68 145,-68 145,-16 75,-16"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="113,-375 113,-400 194,-400 194,-375 113,-375"/> +<polygon fill="none" stroke="black" points="113,-375 113,-400 194,-400 194,-375 113,-375"/> +<text text-anchor="start" x="135" y="-383.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="113,-344 113,-375 194,-375 194,-344 113,-344"/> +<polygon fill="yellow" stroke="transparent" points="118,-349 118,-370 158,-370 158,-349 118,-349"/> +<polygon fill="none" stroke="black" points="118,-349 118,-370 158,-370 158,-349 118,-349"/> +<text text-anchor="start" x="121" y="-355.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="158,-349 158,-370 189,-370 189,-349 158,-349"/> +<text text-anchor="start" x="161" y="-355.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- Con_7 --> +<g id="node2" class="node"> +<title>Con_7</title> +<ellipse fill="none" stroke="black" cx="247" cy="-372" rx="27" ry="18"/> +<text text-anchor="middle" x="247" y="-368.3" font-family="Times,serif" font-size="14.00">#1</text> +</g> +<!-- EQNode8 --> +<g id="node3" class="node"> +<title>EQNode8</title> +<ellipse fill="none" stroke="black" cx="247" cy="-286" rx="27" ry="18"/> +<text text-anchor="middle" x="247" y="-282.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQNode8->Start2 --> +<g id="edge1" class="edge"> +<title>EQNode8->Start2:p1</title> +<path fill="none" stroke="black" d="M236.57,-302.62C225.76,-318.5 208.98,-342.28 198.26,-353.17"/> +<polygon fill="black" stroke="black" points="196.15,-350.37 190,-359 200.19,-356.09 196.15,-350.37"/> +<text text-anchor="middle" x="233.57" y="-305.22" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQNode8->Con_7 --> +<g id="edge2" class="edge"> +<title>EQNode8->Con_7</title> +<path fill="none" stroke="black" d="M247,-304.4C247,-315.74 247,-330.77 247,-343.68"/> +<polygon fill="black" stroke="black" points="243.5,-343.9 247,-353.9 250.5,-343.9 243.5,-343.9"/> +<text text-anchor="middle" x="244" y="-307" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If9 --> +<g id="node4" class="node"> +<title>If9</title> +<polygon fill="yellow" stroke="transparent" points="172,-203 172,-228 266,-228 266,-203 172,-203"/> +<polygon fill="none" stroke="black" points="172,-203 172,-228 266,-228 266,-203 172,-203"/> +<text text-anchor="start" x="213.5" y="-211.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="172,-172 172,-203 266,-203 266,-172 172,-172"/> +<polygon fill="yellow" stroke="transparent" points="177,-177 177,-198 217,-198 217,-177 177,-177"/> +<polygon fill="none" stroke="black" points="177,-177 177,-198 217,-198 217,-177 177,-177"/> +<text text-anchor="start" x="180" y="-183.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="217,-177 217,-198 261,-198 261,-177 217,-177"/> +<polygon fill="none" stroke="black" points="217,-177 217,-198 261,-198 261,-177 217,-177"/> +<text text-anchor="start" x="220" y="-183.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If9->Start2 --> +<g id="edge3" class="edge"> +<title>If9->Start2:p0</title> +<path fill="none" stroke="red" d="M210.31,-232.18C203.59,-253.4 193.07,-281.57 179,-304 166.9,-323.28 145.68,-322.25 139.64,-338.02"/> +<polygon fill="red" stroke="red" points="136.17,-337.56 138,-348 143.08,-338.7 136.17,-337.56"/> +<text text-anchor="middle" x="207.31" y="-234.78" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If9->EQNode8 --> +<g id="edge4" class="edge"> +<title>If9->EQNode8</title> +<path fill="none" stroke="black" d="M229.43,-232.28C232.3,-240.9 235.39,-250.17 238.16,-258.49"/> +<polygon fill="black" stroke="black" points="234.87,-259.69 241.36,-268.07 241.51,-257.48 234.87,-259.69"/> +<text text-anchor="middle" x="226.43" y="-234.88" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_13 --> +<g id="node5" class="node"> +<title>Con_13</title> +<ellipse fill="none" stroke="black" cx="135" cy="-286" rx="27" ry="18"/> +<text text-anchor="middle" x="135" y="-282.3" font-family="Times,serif" font-size="14.00">#2</text> +</g> +<!-- Add14 --> +<g id="node6" class="node"> +<title>Add14</title> +<ellipse fill="none" stroke="black" cx="119" cy="-200" rx="27" ry="18"/> +<text text-anchor="middle" x="119" y="-196.3" font-family="Times,serif" font-size="14.00">+</text> +</g> +<!-- Add14->Start2 --> +<g id="edge5" class="edge"> +<title>Add14->Start2:p1</title> +<path fill="none" stroke="black" d="M134.23,-215.02C146.68,-227.55 163.4,-247.1 171,-268 181.92,-298.04 175.64,-309.96 174.25,-337.87"/> +<polygon fill="black" stroke="black" points="170.75,-337.92 174,-348 177.75,-338.09 170.75,-337.92"/> +<text text-anchor="middle" x="131.23" y="-217.62" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Add14->Con_13 --> +<g id="edge6" class="edge"> +<title>Add14->Con_13</title> +<path fill="none" stroke="black" d="M122.24,-218C124.43,-229.5 127.37,-244.93 129.87,-258.08"/> +<polygon fill="black" stroke="black" points="126.46,-258.86 131.77,-268.03 133.33,-257.55 126.46,-258.86"/> +<text text-anchor="middle" x="119.24" y="-220.6" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Con_15 --> +<g id="node7" class="node"> +<title>Con_15</title> +<ellipse fill="none" stroke="black" cx="43" cy="-286" rx="27" ry="18"/> +<text text-anchor="middle" x="43" y="-282.3" font-family="Times,serif" font-size="14.00">#3</text> +</g> +<!-- Sub16 --> +<g id="node8" class="node"> +<title>Sub16</title> +<ellipse fill="none" stroke="black" cx="47" cy="-200" rx="27" ry="18"/> +<text text-anchor="middle" x="47" y="-196.3" font-family="Times,serif" font-size="14.00">-</text> +</g> +<!-- Sub16->Start2 --> +<g id="edge7" class="edge"> +<title>Sub16->Start2:p1</title> +<path fill="none" stroke="black" d="M54.69,-217.49C67.53,-244.81 92.56,-297.14 99,-304 122.77,-329.31 164.37,-313.46 172.57,-338.01"/> +<polygon fill="black" stroke="black" points="169.12,-338.6 174,-348 176.05,-337.61 169.12,-338.6"/> +<text text-anchor="middle" x="51.69" y="-220.09" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Sub16->Con_15 --> +<g id="edge8" class="edge"> +<title>Sub16->Con_15</title> +<path fill="none" stroke="black" d="M46.19,-218C45.65,-229.31 44.93,-244.42 44.31,-257.43"/> +<polygon fill="black" stroke="black" points="40.8,-257.58 43.82,-267.74 47.79,-257.92 40.8,-257.58"/> +<text text-anchor="middle" x="43.19" y="-220.6" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Region17 --> +<g id="node9" class="node"> +<title>Region17</title> +<polygon fill="yellow" stroke="black" points="232,-132 166,-132 166,-96 232,-96 232,-132"/> +<text text-anchor="middle" x="199" y="-110.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Region17->If9 --> +<g id="edge9" class="edge"> +<title>Region17->If9:p0</title> +<path fill="none" stroke="red" d="M198.14,-132.09C197.72,-141.54 197.27,-153.77 197.08,-165.68"/> +<polygon fill="red" stroke="red" points="193.58,-165.97 197,-176 200.58,-166.03 193.58,-165.97"/> +<text text-anchor="middle" x="195.14" y="-134.69" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region17->If9 --> +<g id="edge10" class="edge"> +<title>Region17->If9:p1</title> +<path fill="none" stroke="red" d="M217.83,-132.05C226.1,-141.05 234.63,-152.92 237.76,-165.89"/> +<polygon fill="red" stroke="red" points="234.31,-166.5 239,-176 241.25,-165.65 234.31,-166.5"/> +<text text-anchor="middle" x="214.83" y="-134.65" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_a18 --> +<g id="node10" class="node"> +<title>Phi_a18</title> +<ellipse fill="lightyellow" stroke="black" cx="119" cy="-114" rx="27" ry="18"/> +<text text-anchor="middle" x="119" y="-110.3" font-family="Times,serif" font-size="14.00">φ_a</text> +</g> +<!-- Phi_a18->Add14 --> +<g id="edge12" class="edge"> +<title>Phi_a18->Add14</title> +<path fill="none" stroke="black" d="M119,-132.4C119,-143.74 119,-158.77 119,-171.68"/> +<polygon fill="black" stroke="black" points="115.5,-171.9 119,-181.9 122.5,-171.9 115.5,-171.9"/> +<text text-anchor="middle" x="116" y="-135" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_a18->Sub16 --> +<g id="edge13" class="edge"> +<title>Phi_a18->Sub16</title> +<path fill="none" stroke="black" d="M106.13,-130.02C95.07,-142.92 78.96,-161.71 66.35,-176.42"/> +<polygon fill="black" stroke="black" points="63.61,-174.24 59.76,-184.11 68.93,-178.8 63.61,-174.24"/> +<text text-anchor="middle" x="103.13" y="-132.62" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_a18->Region17 --> +<g id="edge11" class="edge"> +<title>Phi_a18->Region17</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M146.19,-114C149.39,-114 152.58,-114 155.78,-114"/> +<polygon fill="black" stroke="black" points="155.99,-117.5 165.99,-114 155.99,-110.5 155.99,-117.5"/> +<text text-anchor="middle" x="149.19" y="-107.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Scope1_0 --> +<g id="node11" class="node"> +<title>Scope1_0</title> +<polygon fill="cyan" stroke="transparent" points="164,-31 164,-52 180,-52 180,-31 164,-31"/> +<polygon fill="none" stroke="black" points="164,-31 164,-52 180,-52 180,-31 164,-31"/> +<text text-anchor="start" x="167" y="-37.8" font-family="Times,serif" font-size="14.00">0</text> +<polygon fill="none" stroke="black" points="180,-31 180,-52 220,-52 220,-31 180,-31"/> +<text text-anchor="start" x="183" y="-37.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="220,-31 220,-52 251,-52 251,-31 220,-31"/> +<text text-anchor="start" x="223" y="-37.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- Scope1_0->Start2 --> +<g id="edge15" class="edge"> +<title>Scope1_0:Scope1_0_arg->Start2:p1</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M252,-41C369.7,-41 344.88,-203.88 283,-304 264.19,-334.43 240.54,-319.81 211,-340 204.51,-344.44 202.84,-350.75 199.44,-354.86"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="197.75,-351.78 190,-359 200.56,-358.19 197.75,-351.78"/> +</g> +<!-- Scope1_0->Region17 --> +<g id="edge14" class="edge"> +<title>Scope1_0:Scope1_0_$ctrl->Region17</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M200,-53C200,-63.75 199.84,-75.58 199.64,-85.87"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="196.14,-85.86 199.44,-95.93 203.14,-86.01 196.14,-85.86"/> +</g> +<!-- Scope1_1 --> +<g id="node12" class="node"> +<title>Scope1_1</title> +<polygon fill="cyan" stroke="transparent" points="95,-31 95,-52 111,-52 111,-31 95,-31"/> +<polygon fill="none" stroke="black" points="95,-31 95,-52 111,-52 111,-31 95,-31"/> +<text text-anchor="start" x="98" y="-37.8" font-family="Times,serif" font-size="14.00">1</text> +<polygon fill="none" stroke="black" points="111,-31 111,-52 126,-52 126,-31 111,-31"/> +<text text-anchor="start" x="114" y="-37.8" font-family="Times,serif" font-size="14.00">a</text> +</g> +<!-- Scope1_1->Phi_a18 --> +<g id="edge16" class="edge"> +<title>Scope1_1:Scope1_1_a->Phi_a18</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M119,-53C119,-63.75 119,-75.58 119,-85.87"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="115.5,-85.93 119,-95.93 122.5,-85.93 115.5,-85.93"/> +</g> +</g> +</svg> diff --git a/docs/chapter05/05-graph3.gv b/docs/chapter05/05-graph3.gv new file mode 100644 index 00000000..277bed48 --- /dev/null +++ b/docs/chapter05/05-graph3.gv @@ -0,0 +1,66 @@ +digraph chapter05 { +/* +int a = 1; +if (arg == 1) + a = arg+2; +else { + a = arg-3; + #showGraph; +} +#showGraph; +return a; +*/ + rankdir=BT; + ordering="in"; + concentrate="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" ]; + Con_7 [ label="#1" ]; + EQNode8 [ label="==" ]; + If9 [ 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_13 [ label="#2" ]; + Add14 [ label="+" ]; + Con_15 [ label="#3" ]; + Sub16 [ label="-" ]; + Region17 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a18 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Return19 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region17;Phi_a18;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return19[taillabel=0 color=red]; + EQNode8 -> Start2:p1[taillabel=1]; + EQNode8 -> Con_7[taillabel=2]; + If9 -> Start2:p0[taillabel=0 color=red]; + If9 -> EQNode8[taillabel=1]; + Add14 -> Start2:p1[taillabel=1]; + Add14 -> Con_13[taillabel=2]; + Sub16 -> Start2:p1[taillabel=1]; + Sub16 -> Con_15[taillabel=2]; + Region17 -> If9:p0[taillabel=1 color=red]; + Region17 -> If9:p1[taillabel=2 color=red]; + Phi_a18 -> Region17 [style=dotted taillabel=0]; + Phi_a18 -> Add14[taillabel=1]; + Phi_a18 -> Sub16[taillabel=2]; + Return19 -> Region17[taillabel=0 color=red]; + Return19 -> Phi_a18[taillabel=1]; +} diff --git a/docs/chapter05/05-graph3.svg b/docs/chapter05/05-graph3.svg new file mode 100644 index 00000000..855fdc2c --- /dev/null +++ b/docs/chapter05/05-graph3.svg @@ -0,0 +1,216 @@ +<?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: chapter05 Pages: 1 --> +<svg width="298pt" height="492pt" + viewBox="0.00 0.00 298.00 492.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 488)"> +<title>chapter05</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-488 294,-488 294,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-476 282,-476 282,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="113,-439 113,-464 194,-464 194,-439 113,-439"/> +<polygon fill="none" stroke="black" points="113,-439 113,-464 194,-464 194,-439 113,-439"/> +<text text-anchor="start" x="135" y="-447.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="113,-408 113,-439 194,-439 194,-408 113,-408"/> +<polygon fill="yellow" stroke="transparent" points="118,-413 118,-434 158,-434 158,-413 118,-413"/> +<polygon fill="none" stroke="black" points="118,-413 118,-434 158,-434 158,-413 118,-413"/> +<text text-anchor="start" x="121" y="-419.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="158,-413 158,-434 189,-434 189,-413 158,-413"/> +<text text-anchor="start" x="161" y="-419.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="185,-52 131,-52 131,-16 185,-16 185,-52"/> +<text text-anchor="middle" x="158" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return19 --> +<g id="node12" class="node"> +<title>Return19</title> +<polygon fill="yellow" stroke="black" points="191,-124 125,-124 125,-88 191,-88 191,-124"/> +<text text-anchor="middle" x="158" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return19 --> +<g id="edge1" class="edge"> +<title>Stop3->Return19</title> +<path fill="none" stroke="red" d="M158,-52.3C158,-60.02 158,-69.29 158,-77.89"/> +<polygon fill="red" stroke="red" points="154.5,-77.9 158,-87.9 161.5,-77.9 154.5,-77.9"/> +<text text-anchor="middle" x="155" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Con_7 --> +<g id="node3" class="node"> +<title>Con_7</title> +<ellipse fill="none" stroke="black" cx="247" cy="-436" rx="27" ry="18"/> +<text text-anchor="middle" x="247" y="-432.3" font-family="Times,serif" font-size="14.00">#1</text> +</g> +<!-- EQNode8 --> +<g id="node4" class="node"> +<title>EQNode8</title> +<ellipse fill="none" stroke="black" cx="247" cy="-350" rx="27" ry="18"/> +<text text-anchor="middle" x="247" y="-346.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQNode8->Start2 --> +<g id="edge2" class="edge"> +<title>EQNode8->Start2:p1</title> +<path fill="none" stroke="black" d="M236.57,-366.62C225.76,-382.5 208.98,-406.28 198.26,-417.17"/> +<polygon fill="black" stroke="black" points="196.15,-414.37 190,-423 200.19,-420.09 196.15,-414.37"/> +<text text-anchor="middle" x="233.57" y="-369.22" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQNode8->Con_7 --> +<g id="edge3" class="edge"> +<title>EQNode8->Con_7</title> +<path fill="none" stroke="black" d="M247,-368.4C247,-379.74 247,-394.77 247,-407.68"/> +<polygon fill="black" stroke="black" points="243.5,-407.9 247,-417.9 250.5,-407.9 243.5,-407.9"/> +<text text-anchor="middle" x="244" y="-371" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If9 --> +<g id="node5" class="node"> +<title>If9</title> +<polygon fill="yellow" stroke="transparent" points="172,-267 172,-292 266,-292 266,-267 172,-267"/> +<polygon fill="none" stroke="black" points="172,-267 172,-292 266,-292 266,-267 172,-267"/> +<text text-anchor="start" x="213.5" y="-275.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="172,-236 172,-267 266,-267 266,-236 172,-236"/> +<polygon fill="yellow" stroke="transparent" points="177,-241 177,-262 217,-262 217,-241 177,-241"/> +<polygon fill="none" stroke="black" points="177,-241 177,-262 217,-262 217,-241 177,-241"/> +<text text-anchor="start" x="180" y="-247.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="217,-241 217,-262 261,-262 261,-241 217,-241"/> +<polygon fill="none" stroke="black" points="217,-241 217,-262 261,-262 261,-241 217,-241"/> +<text text-anchor="start" x="220" y="-247.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If9->Start2 --> +<g id="edge4" class="edge"> +<title>If9->Start2:p0</title> +<path fill="none" stroke="red" d="M210.31,-296.18C203.59,-317.4 193.07,-345.57 179,-368 166.9,-387.28 145.68,-386.25 139.64,-402.02"/> +<polygon fill="red" stroke="red" points="136.17,-401.56 138,-412 143.08,-402.7 136.17,-401.56"/> +<text text-anchor="middle" x="207.31" y="-298.78" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If9->EQNode8 --> +<g id="edge5" class="edge"> +<title>If9->EQNode8</title> +<path fill="none" stroke="black" d="M229.43,-296.28C232.3,-304.9 235.39,-314.17 238.16,-322.49"/> +<polygon fill="black" stroke="black" points="234.87,-323.69 241.36,-332.07 241.51,-321.48 234.87,-323.69"/> +<text text-anchor="middle" x="226.43" y="-298.88" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_13 --> +<g id="node6" class="node"> +<title>Con_13</title> +<ellipse fill="none" stroke="black" cx="43" cy="-350" rx="27" ry="18"/> +<text text-anchor="middle" x="43" y="-346.3" font-family="Times,serif" font-size="14.00">#2</text> +</g> +<!-- Add14 --> +<g id="node7" class="node"> +<title>Add14</title> +<ellipse fill="none" stroke="black" cx="47" cy="-264" rx="27" ry="18"/> +<text text-anchor="middle" x="47" y="-260.3" font-family="Times,serif" font-size="14.00">+</text> +</g> +<!-- Add14->Start2 --> +<g id="edge6" class="edge"> +<title>Add14->Start2:p1</title> +<path fill="none" stroke="black" d="M54.69,-281.49C67.53,-308.81 92.56,-361.14 99,-368 122.77,-393.31 164.37,-377.46 172.57,-402.01"/> +<polygon fill="black" stroke="black" points="169.12,-402.6 174,-412 176.05,-401.61 169.12,-402.6"/> +<text text-anchor="middle" x="51.69" y="-284.09" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Add14->Con_13 --> +<g id="edge7" class="edge"> +<title>Add14->Con_13</title> +<path fill="none" stroke="black" d="M46.19,-282C45.65,-293.31 44.93,-308.42 44.31,-321.43"/> +<polygon fill="black" stroke="black" points="40.8,-321.58 43.82,-331.74 47.79,-321.92 40.8,-321.58"/> +<text text-anchor="middle" x="43.19" y="-284.6" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Con_15 --> +<g id="node8" class="node"> +<title>Con_15</title> +<ellipse fill="none" stroke="black" cx="135" cy="-350" rx="27" ry="18"/> +<text text-anchor="middle" x="135" y="-346.3" font-family="Times,serif" font-size="14.00">#3</text> +</g> +<!-- Sub16 --> +<g id="node9" class="node"> +<title>Sub16</title> +<ellipse fill="none" stroke="black" cx="119" cy="-264" rx="27" ry="18"/> +<text text-anchor="middle" x="119" y="-260.3" font-family="Times,serif" font-size="14.00">-</text> +</g> +<!-- Sub16->Start2 --> +<g id="edge8" class="edge"> +<title>Sub16->Start2:p1</title> +<path fill="none" stroke="black" d="M134.23,-279.02C146.68,-291.55 163.4,-311.1 171,-332 181.92,-362.04 175.64,-373.96 174.25,-401.87"/> +<polygon fill="black" stroke="black" points="170.75,-401.92 174,-412 177.75,-402.09 170.75,-401.92"/> +<text text-anchor="middle" x="131.23" y="-281.62" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Sub16->Con_15 --> +<g id="edge9" class="edge"> +<title>Sub16->Con_15</title> +<path fill="none" stroke="black" d="M122.24,-282C124.43,-293.5 127.37,-308.93 129.87,-322.08"/> +<polygon fill="black" stroke="black" points="126.46,-322.86 131.77,-332.03 133.33,-321.55 126.46,-322.86"/> +<text text-anchor="middle" x="119.24" y="-284.6" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Region17 --> +<g id="node10" class="node"> +<title>Region17</title> +<polygon fill="yellow" stroke="black" points="230,-196 164,-196 164,-160 230,-160 230,-196"/> +<text text-anchor="middle" x="197" y="-174.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Region17->If9 --> +<g id="edge10" class="edge"> +<title>Region17->If9:p0</title> +<path fill="none" stroke="red" d="M197,-196.09C197,-205.55 197,-217.77 197,-229.69"/> +<polygon fill="red" stroke="red" points="193.5,-230 197,-240 200.5,-230 193.5,-230"/> +<text text-anchor="middle" x="194" y="-198.69" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region17->If9 --> +<g id="edge11" class="edge"> +<title>Region17->If9:p1</title> +<path fill="none" stroke="red" d="M217.02,-196.12C225.64,-205.06 234.48,-216.84 237.71,-229.84"/> +<polygon fill="red" stroke="red" points="234.27,-230.52 239,-240 241.22,-229.64 234.27,-230.52"/> +<text text-anchor="middle" x="214.02" y="-198.72" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_a18 --> +<g id="node11" class="node"> +<title>Phi_a18</title> +<ellipse fill="lightyellow" stroke="black" cx="119" cy="-178" rx="27" ry="18"/> +<text text-anchor="middle" x="119" y="-174.3" font-family="Times,serif" font-size="14.00">φ_a</text> +</g> +<!-- Phi_a18->Add14 --> +<g id="edge13" class="edge"> +<title>Phi_a18->Add14</title> +<path fill="none" stroke="black" d="M106.13,-194.02C95.07,-206.92 78.96,-225.71 66.35,-240.42"/> +<polygon fill="black" stroke="black" points="63.61,-238.24 59.76,-248.11 68.93,-242.8 63.61,-238.24"/> +<text text-anchor="middle" x="103.13" y="-196.62" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_a18->Sub16 --> +<g id="edge14" class="edge"> +<title>Phi_a18->Sub16</title> +<path fill="none" stroke="black" d="M119,-196.4C119,-207.74 119,-222.77 119,-235.68"/> +<polygon fill="black" stroke="black" points="115.5,-235.9 119,-245.9 122.5,-235.9 115.5,-235.9"/> +<text text-anchor="middle" x="116" y="-199" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_a18->Region17 --> +<g id="edge12" class="edge"> +<title>Phi_a18->Region17</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M146.12,-178C148.58,-178 151.04,-178 153.5,-178"/> +<polygon fill="black" stroke="black" points="153.61,-181.5 163.61,-178 153.61,-174.5 153.61,-181.5"/> +<text text-anchor="middle" x="149.12" y="-171.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return19->Region17 --> +<g id="edge15" class="edge"> +<title>Return19->Region17</title> +<path fill="none" stroke="red" d="M167.64,-124.3C172.13,-132.36 177.56,-142.11 182.52,-151.02"/> +<polygon fill="red" stroke="red" points="179.55,-152.86 187.47,-159.9 185.66,-149.46 179.55,-152.86"/> +<text text-anchor="middle" x="164.64" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return19->Phi_a18 --> +<g id="edge16" class="edge"> +<title>Return19->Phi_a18</title> +<path fill="none" stroke="black" d="M148.36,-124.3C143.69,-132.68 138,-142.9 132.87,-152.1"/> +<polygon fill="black" stroke="black" points="129.8,-150.42 127.99,-160.86 135.92,-153.82 129.8,-150.42"/> +<text text-anchor="middle" x="145.36" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +</g> +</svg> diff --git a/docs/chapter05/05-graph4.gv b/docs/chapter05/05-graph4.gv new file mode 100644 index 00000000..88120b4a --- /dev/null +++ b/docs/chapter05/05-graph4.gv @@ -0,0 +1,63 @@ +digraph chapter05 { +/* +int a=arg==2; +if( arg==1 ) +{ + a=arg==3; +} +return a; +*/ + rankdir=BT; + ordering="in"; + concentrate="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" ]; + Con_6 [ label="#2" ]; + EQNode7 [ label="==" ]; + Con_8 [ label="#1" ]; + EQNode9 [ label="==" ]; + If10 [ 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_14 [ label="#3" ]; + EQNode15 [ label="==" ]; + Region16 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a17 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Return18 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region16;Phi_a17;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return18[taillabel=0 color=red]; + EQNode7 -> Start2:p1[taillabel=1]; + EQNode7 -> Con_6[taillabel=2]; + EQNode9 -> Start2:p1[taillabel=1]; + EQNode9 -> Con_8[taillabel=2]; + If10 -> Start2:p0[taillabel=0 color=red]; + If10 -> EQNode9[taillabel=1]; + EQNode15 -> Start2:p1[taillabel=1]; + EQNode15 -> Con_14[taillabel=2]; + Region16 -> If10:p0[taillabel=1 color=red]; + Region16 -> If10:p1[taillabel=2 color=red]; + Phi_a17 -> Region16 [style=dotted taillabel=0]; + Phi_a17 -> EQNode15[taillabel=1]; + Phi_a17 -> EQNode7[taillabel=2]; + Return18 -> Region16[taillabel=0 color=red]; + Return18 -> Phi_a17[taillabel=1]; +} diff --git a/docs/chapter05/05-graph4.svg b/docs/chapter05/05-graph4.svg new file mode 100644 index 00000000..3fcee500 --- /dev/null +++ b/docs/chapter05/05-graph4.svg @@ -0,0 +1,216 @@ +<?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: chapter05 Pages: 1 --> +<svg width="298pt" height="492pt" + viewBox="0.00 0.00 298.00 492.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 488)"> +<title>chapter05</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-488 294,-488 294,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-476 282,-476 282,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="113,-439 113,-464 194,-464 194,-439 113,-439"/> +<polygon fill="none" stroke="black" points="113,-439 113,-464 194,-464 194,-439 113,-439"/> +<text text-anchor="start" x="135" y="-447.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="113,-408 113,-439 194,-439 194,-408 113,-408"/> +<polygon fill="yellow" stroke="transparent" points="118,-413 118,-434 158,-434 158,-413 118,-413"/> +<polygon fill="none" stroke="black" points="118,-413 118,-434 158,-434 158,-413 118,-413"/> +<text text-anchor="start" x="121" y="-419.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="158,-413 158,-434 189,-434 189,-413 158,-413"/> +<text text-anchor="start" x="161" y="-419.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="185,-52 131,-52 131,-16 185,-16 185,-52"/> +<text text-anchor="middle" x="158" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return18 --> +<g id="node12" class="node"> +<title>Return18</title> +<polygon fill="yellow" stroke="black" points="191,-124 125,-124 125,-88 191,-88 191,-124"/> +<text text-anchor="middle" x="158" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return18 --> +<g id="edge1" class="edge"> +<title>Stop3->Return18</title> +<path fill="none" stroke="red" d="M158,-52.3C158,-60.02 158,-69.29 158,-77.89"/> +<polygon fill="red" stroke="red" points="154.5,-77.9 158,-87.9 161.5,-77.9 154.5,-77.9"/> +<text text-anchor="middle" x="155" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Con_6 --> +<g id="node3" class="node"> +<title>Con_6</title> +<ellipse fill="none" stroke="black" cx="43" cy="-350" rx="27" ry="18"/> +<text text-anchor="middle" x="43" y="-346.3" font-family="Times,serif" font-size="14.00">#2</text> +</g> +<!-- EQNode7 --> +<g id="node4" class="node"> +<title>EQNode7</title> +<ellipse fill="none" stroke="black" cx="47" cy="-264" rx="27" ry="18"/> +<text text-anchor="middle" x="47" y="-260.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQNode7->Start2 --> +<g id="edge2" class="edge"> +<title>EQNode7->Start2:p1</title> +<path fill="none" stroke="black" d="M54.69,-281.49C67.53,-308.81 92.56,-361.14 99,-368 122.77,-393.31 164.37,-377.46 172.57,-402.01"/> +<polygon fill="black" stroke="black" points="169.12,-402.6 174,-412 176.05,-401.61 169.12,-402.6"/> +<text text-anchor="middle" x="51.69" y="-284.09" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQNode7->Con_6 --> +<g id="edge3" class="edge"> +<title>EQNode7->Con_6</title> +<path fill="none" stroke="black" d="M46.19,-282C45.65,-293.31 44.93,-308.42 44.31,-321.43"/> +<polygon fill="black" stroke="black" points="40.8,-321.58 43.82,-331.74 47.79,-321.92 40.8,-321.58"/> +<text text-anchor="middle" x="43.19" y="-284.6" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Con_8 --> +<g id="node5" class="node"> +<title>Con_8</title> +<ellipse fill="none" stroke="black" cx="247" cy="-436" rx="27" ry="18"/> +<text text-anchor="middle" x="247" y="-432.3" font-family="Times,serif" font-size="14.00">#1</text> +</g> +<!-- EQNode9 --> +<g id="node6" class="node"> +<title>EQNode9</title> +<ellipse fill="none" stroke="black" cx="247" cy="-350" rx="27" ry="18"/> +<text text-anchor="middle" x="247" y="-346.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQNode9->Start2 --> +<g id="edge4" class="edge"> +<title>EQNode9->Start2:p1</title> +<path fill="none" stroke="black" d="M236.57,-366.62C225.76,-382.5 208.98,-406.28 198.26,-417.17"/> +<polygon fill="black" stroke="black" points="196.15,-414.37 190,-423 200.19,-420.09 196.15,-414.37"/> +<text text-anchor="middle" x="233.57" y="-369.22" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQNode9->Con_8 --> +<g id="edge5" class="edge"> +<title>EQNode9->Con_8</title> +<path fill="none" stroke="black" d="M247,-368.4C247,-379.74 247,-394.77 247,-407.68"/> +<polygon fill="black" stroke="black" points="243.5,-407.9 247,-417.9 250.5,-407.9 243.5,-407.9"/> +<text text-anchor="middle" x="244" y="-371" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If10 --> +<g id="node7" class="node"> +<title>If10</title> +<polygon fill="yellow" stroke="transparent" points="172,-267 172,-292 266,-292 266,-267 172,-267"/> +<polygon fill="none" stroke="black" points="172,-267 172,-292 266,-292 266,-267 172,-267"/> +<text text-anchor="start" x="213.5" y="-275.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="172,-236 172,-267 266,-267 266,-236 172,-236"/> +<polygon fill="yellow" stroke="transparent" points="177,-241 177,-262 217,-262 217,-241 177,-241"/> +<polygon fill="none" stroke="black" points="177,-241 177,-262 217,-262 217,-241 177,-241"/> +<text text-anchor="start" x="180" y="-247.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="217,-241 217,-262 261,-262 261,-241 217,-241"/> +<polygon fill="none" stroke="black" points="217,-241 217,-262 261,-262 261,-241 217,-241"/> +<text text-anchor="start" x="220" y="-247.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If10->Start2 --> +<g id="edge6" class="edge"> +<title>If10->Start2:p0</title> +<path fill="none" stroke="red" d="M210.31,-296.18C203.59,-317.4 193.07,-345.57 179,-368 166.9,-387.28 145.68,-386.25 139.64,-402.02"/> +<polygon fill="red" stroke="red" points="136.17,-401.56 138,-412 143.08,-402.7 136.17,-401.56"/> +<text text-anchor="middle" x="207.31" y="-298.78" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If10->EQNode9 --> +<g id="edge7" class="edge"> +<title>If10->EQNode9</title> +<path fill="none" stroke="black" d="M229.43,-296.28C232.3,-304.9 235.39,-314.17 238.16,-322.49"/> +<polygon fill="black" stroke="black" points="234.87,-323.69 241.36,-332.07 241.51,-321.48 234.87,-323.69"/> +<text text-anchor="middle" x="226.43" y="-298.88" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_14 --> +<g id="node8" class="node"> +<title>Con_14</title> +<ellipse fill="none" stroke="black" cx="135" cy="-350" rx="27" ry="18"/> +<text text-anchor="middle" x="135" y="-346.3" font-family="Times,serif" font-size="14.00">#3</text> +</g> +<!-- EQNode15 --> +<g id="node9" class="node"> +<title>EQNode15</title> +<ellipse fill="none" stroke="black" cx="119" cy="-264" rx="27" ry="18"/> +<text text-anchor="middle" x="119" y="-260.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQNode15->Start2 --> +<g id="edge8" class="edge"> +<title>EQNode15->Start2:p1</title> +<path fill="none" stroke="black" d="M134.23,-279.02C146.68,-291.55 163.4,-311.1 171,-332 181.92,-362.04 175.64,-373.96 174.25,-401.87"/> +<polygon fill="black" stroke="black" points="170.75,-401.92 174,-412 177.75,-402.09 170.75,-401.92"/> +<text text-anchor="middle" x="131.23" y="-281.62" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQNode15->Con_14 --> +<g id="edge9" class="edge"> +<title>EQNode15->Con_14</title> +<path fill="none" stroke="black" d="M122.24,-282C124.43,-293.5 127.37,-308.93 129.87,-322.08"/> +<polygon fill="black" stroke="black" points="126.46,-322.86 131.77,-332.03 133.33,-321.55 126.46,-322.86"/> +<text text-anchor="middle" x="119.24" y="-284.6" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Region16 --> +<g id="node10" class="node"> +<title>Region16</title> +<polygon fill="yellow" stroke="black" points="230,-196 164,-196 164,-160 230,-160 230,-196"/> +<text text-anchor="middle" x="197" y="-174.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Region16->If10 --> +<g id="edge10" class="edge"> +<title>Region16->If10:p0</title> +<path fill="none" stroke="red" d="M197,-196.09C197,-205.55 197,-217.77 197,-229.69"/> +<polygon fill="red" stroke="red" points="193.5,-230 197,-240 200.5,-230 193.5,-230"/> +<text text-anchor="middle" x="194" y="-198.69" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region16->If10 --> +<g id="edge11" class="edge"> +<title>Region16->If10:p1</title> +<path fill="none" stroke="red" d="M217.02,-196.12C225.64,-205.06 234.48,-216.84 237.71,-229.84"/> +<polygon fill="red" stroke="red" points="234.27,-230.52 239,-240 241.22,-229.64 234.27,-230.52"/> +<text text-anchor="middle" x="214.02" y="-198.72" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_a17 --> +<g id="node11" class="node"> +<title>Phi_a17</title> +<ellipse fill="lightyellow" stroke="black" cx="119" cy="-178" rx="27" ry="18"/> +<text text-anchor="middle" x="119" y="-174.3" font-family="Times,serif" font-size="14.00">φ_a</text> +</g> +<!-- Phi_a17->EQNode7 --> +<g id="edge14" class="edge"> +<title>Phi_a17->EQNode7</title> +<path fill="none" stroke="black" d="M106.13,-194.02C95.07,-206.92 78.96,-225.71 66.35,-240.42"/> +<polygon fill="black" stroke="black" points="63.61,-238.24 59.76,-248.11 68.93,-242.8 63.61,-238.24"/> +<text text-anchor="middle" x="103.13" y="-196.62" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_a17->EQNode15 --> +<g id="edge13" class="edge"> +<title>Phi_a17->EQNode15</title> +<path fill="none" stroke="black" d="M119,-196.4C119,-207.74 119,-222.77 119,-235.68"/> +<polygon fill="black" stroke="black" points="115.5,-235.9 119,-245.9 122.5,-235.9 115.5,-235.9"/> +<text text-anchor="middle" x="116" y="-199" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_a17->Region16 --> +<g id="edge12" class="edge"> +<title>Phi_a17->Region16</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M146.12,-178C148.58,-178 151.04,-178 153.5,-178"/> +<polygon fill="black" stroke="black" points="153.61,-181.5 163.61,-178 153.61,-174.5 153.61,-181.5"/> +<text text-anchor="middle" x="149.12" y="-171.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return18->Region16 --> +<g id="edge15" class="edge"> +<title>Return18->Region16</title> +<path fill="none" stroke="red" d="M167.64,-124.3C172.13,-132.36 177.56,-142.11 182.52,-151.02"/> +<polygon fill="red" stroke="red" points="179.55,-152.86 187.47,-159.9 185.66,-149.46 179.55,-152.86"/> +<text text-anchor="middle" x="164.64" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return18->Phi_a17 --> +<g id="edge16" class="edge"> +<title>Return18->Phi_a17</title> +<path fill="none" stroke="black" d="M148.36,-124.3C143.69,-132.68 138,-142.9 132.87,-152.1"/> +<polygon fill="black" stroke="black" points="129.8,-150.42 127.99,-160.86 135.92,-153.82 129.8,-150.42"/> +<text text-anchor="middle" x="145.36" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +</g> +</svg> diff --git a/docs/chapter05/05-graph5.gv b/docs/chapter05/05-graph5.gv new file mode 100644 index 00000000..b03e90b5 --- /dev/null +++ b/docs/chapter05/05-graph5.gv @@ -0,0 +1,60 @@ +digraph chapter05 { +/* +int a=arg==2; +if( arg==1 ) +{ + a=arg==3; +} +return a; +*/ + rankdir=BT; + ordering="in"; + concentrate="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" ]; + Con_6 [ label="#2" ]; + Con_8 [ label="#1" ]; + EQNode9 [ label="==" ]; + If10 [ 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_14 [ label="#3" ]; + Region16 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a19 [ style=filled fillcolor=lightyellow label="φ_a" ]; + EQNode20 [ label="==" ]; + Return21 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region16;Phi_a19;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return21[taillabel=0 color=red]; + EQNode9 -> Start2:p1[taillabel=1]; + EQNode9 -> Con_8[taillabel=2]; + If10 -> Start2:p0[taillabel=0 color=red]; + If10 -> EQNode9[taillabel=1]; + Region16 -> If10:p0[taillabel=1 color=red]; + Region16 -> If10:p1[taillabel=2 color=red]; + Phi_a19 -> Region16 [style=dotted taillabel=0]; + Phi_a19 -> Con_14[taillabel=1]; + Phi_a19 -> Con_6[taillabel=2]; + EQNode20 -> Start2:p1[taillabel=1]; + EQNode20 -> Phi_a19[taillabel=2]; + Return21 -> Region16[taillabel=0 color=red]; + Return21 -> EQNode20[taillabel=1]; +} diff --git a/docs/chapter05/05-graph5.svg b/docs/chapter05/05-graph5.svg new file mode 100644 index 00000000..4f6fa4bd --- /dev/null +++ b/docs/chapter05/05-graph5.svg @@ -0,0 +1,196 @@ +<?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: chapter05 Pages: 1 --> +<svg width="314pt" height="564pt" + viewBox="0.00 0.00 314.00 564.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 560)"> +<title>chapter05</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-560 310,-560 310,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-548 298,-548 298,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="97,-511 97,-536 178,-536 178,-511 97,-511"/> +<polygon fill="none" stroke="black" points="97,-511 97,-536 178,-536 178,-511 97,-511"/> +<text text-anchor="start" x="119" y="-519.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="97,-480 97,-511 178,-511 178,-480 97,-480"/> +<polygon fill="yellow" stroke="transparent" points="102,-485 102,-506 142,-506 142,-485 102,-485"/> +<polygon fill="none" stroke="black" points="102,-485 102,-506 142,-506 142,-485 102,-485"/> +<text text-anchor="start" x="105" y="-491.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="142,-485 142,-506 173,-506 173,-485 142,-485"/> +<text text-anchor="start" x="145" y="-491.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="148,-52 94,-52 94,-16 148,-16 148,-52"/> +<text text-anchor="middle" x="121" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return21 --> +<g id="node11" class="node"> +<title>Return21</title> +<polygon fill="yellow" stroke="black" points="154,-124 88,-124 88,-88 154,-88 154,-124"/> +<text text-anchor="middle" x="121" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return21 --> +<g id="edge1" class="edge"> +<title>Stop3->Return21</title> +<path fill="none" stroke="red" d="M121,-52.3C121,-60.02 121,-69.29 121,-77.89"/> +<polygon fill="red" stroke="red" points="117.5,-77.9 121,-87.9 124.5,-77.9 117.5,-77.9"/> +<text text-anchor="middle" x="118" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Con_6 --> +<g id="node3" class="node"> +<title>Con_6</title> +<ellipse fill="none" stroke="black" cx="263" cy="-336" rx="27" ry="18"/> +<text text-anchor="middle" x="263" y="-332.3" font-family="Times,serif" font-size="14.00">#2</text> +</g> +<!-- Con_8 --> +<g id="node4" class="node"> +<title>Con_8</title> +<ellipse fill="none" stroke="black" cx="43" cy="-508" rx="27" ry="18"/> +<text text-anchor="middle" x="43" y="-504.3" font-family="Times,serif" font-size="14.00">#1</text> +</g> +<!-- EQNode9 --> +<g id="node5" class="node"> +<title>EQNode9</title> +<ellipse fill="none" stroke="black" cx="71" cy="-422" rx="27" ry="18"/> +<text text-anchor="middle" x="71" y="-418.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQNode9->Start2 --> +<g id="edge2" class="edge"> +<title>EQNode9->Start2:p1</title> +<path fill="none" stroke="black" d="M92.51,-433.05C113.44,-443.41 143.59,-460.03 154.16,-474.46"/> +<polygon fill="black" stroke="black" points="151.02,-476.03 158,-484 157.51,-473.42 151.02,-476.03"/> +<text text-anchor="middle" x="89.51" y="-435.65" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQNode9->Con_8 --> +<g id="edge3" class="edge"> +<title>EQNode9->Con_8</title> +<path fill="none" stroke="black" d="M65.33,-440C61.44,-451.69 56.19,-467.44 51.76,-480.73"/> +<polygon fill="black" stroke="black" points="48.4,-479.72 48.56,-490.31 55.04,-481.93 48.4,-479.72"/> +<text text-anchor="middle" x="62.33" y="-442.6" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If10 --> +<g id="node6" class="node"> +<title>If10</title> +<polygon fill="yellow" stroke="transparent" points="24,-339 24,-364 118,-364 118,-339 24,-339"/> +<polygon fill="none" stroke="black" points="24,-339 24,-364 118,-364 118,-339 24,-339"/> +<text text-anchor="start" x="65.5" y="-347.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="24,-308 24,-339 118,-339 118,-308 24,-308"/> +<polygon fill="yellow" stroke="transparent" points="29,-313 29,-334 69,-334 69,-313 29,-313"/> +<polygon fill="none" stroke="black" points="29,-313 29,-334 69,-334 69,-313 29,-313"/> +<text text-anchor="start" x="32" y="-319.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="69,-313 69,-334 113,-334 113,-313 69,-313"/> +<polygon fill="none" stroke="black" points="69,-313 69,-334 113,-334 113,-313 69,-313"/> +<text text-anchor="start" x="72" y="-319.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If10->Start2 --> +<g id="edge4" class="edge"> +<title>If10->Start2:p0</title> +<path fill="none" stroke="red" d="M90.29,-368.12C96.41,-379.12 102.69,-391.8 107,-404 117.81,-434.65 121.3,-445.6 121.9,-473.74"/> +<polygon fill="red" stroke="red" points="118.4,-474.03 122,-484 125.4,-473.97 118.4,-474.03"/> +<text text-anchor="middle" x="87.29" y="-370.72" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If10->EQNode9 --> +<g id="edge5" class="edge"> +<title>If10->EQNode9</title> +<path fill="none" stroke="black" d="M71,-368.28C71,-376.58 71,-385.48 71,-393.56"/> +<polygon fill="black" stroke="black" points="67.5,-393.6 71,-403.6 74.5,-393.6 67.5,-393.6"/> +<text text-anchor="middle" x="68" y="-370.88" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_14 --> +<g id="node7" class="node"> +<title>Con_14</title> +<ellipse fill="none" stroke="black" cx="191" cy="-336" rx="27" ry="18"/> +<text text-anchor="middle" x="191" y="-332.3" font-family="Times,serif" font-size="14.00">#3</text> +</g> +<!-- Region16 --> +<g id="node8" class="node"> +<title>Region16</title> +<polygon fill="yellow" stroke="black" points="125,-268 59,-268 59,-232 125,-232 125,-268"/> +<text text-anchor="middle" x="92" y="-246.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Region16->If10 --> +<g id="edge6" class="edge"> +<title>Region16->If10:p0</title> +<path fill="none" stroke="red" d="M71.51,-268.03C62.68,-276.94 53.63,-288.71 50.32,-301.78"/> +<polygon fill="red" stroke="red" points="46.81,-301.63 49,-312 53.75,-302.53 46.81,-301.63"/> +<text text-anchor="middle" x="68.51" y="-270.63" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region16->If10 --> +<g id="edge7" class="edge"> +<title>Region16->If10:p1</title> +<path fill="none" stroke="red" d="M91.57,-268.09C91.36,-277.55 91.13,-289.77 91.04,-301.69"/> +<polygon fill="red" stroke="red" points="87.54,-301.99 91,-312 94.54,-302.01 87.54,-301.99"/> +<text text-anchor="middle" x="88.57" y="-270.69" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_a19 --> +<g id="node9" class="node"> +<title>Phi_a19</title> +<ellipse fill="lightyellow" stroke="black" cx="191" cy="-250" rx="27" ry="18"/> +<text text-anchor="middle" x="191" y="-246.3" font-family="Times,serif" font-size="14.00">φ_a</text> +</g> +<!-- Phi_a19->Con_6 --> +<g id="edge10" class="edge"> +<title>Phi_a19->Con_6</title> +<path fill="none" stroke="black" d="M203.87,-266.02C214.93,-278.92 231.04,-297.71 243.65,-312.42"/> +<polygon fill="black" stroke="black" points="241.07,-314.8 250.24,-320.11 246.39,-310.24 241.07,-314.8"/> +<text text-anchor="middle" x="200.87" y="-268.62" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_a19->Con_14 --> +<g id="edge9" class="edge"> +<title>Phi_a19->Con_14</title> +<path fill="none" stroke="black" d="M191,-268.4C191,-279.74 191,-294.77 191,-307.68"/> +<polygon fill="black" stroke="black" points="187.5,-307.9 191,-317.9 194.5,-307.9 187.5,-307.9"/> +<text text-anchor="middle" x="188" y="-271" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_a19->Region16 --> +<g id="edge8" class="edge"> +<title>Phi_a19->Region16</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M163.78,-250C154.35,-250 144.92,-250 135.49,-250"/> +<polygon fill="black" stroke="black" points="135.26,-246.5 125.26,-250 135.26,-253.5 135.26,-246.5"/> +<text text-anchor="middle" x="160.78" y="-243.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- EQNode20 --> +<g id="node10" class="node"> +<title>EQNode20</title> +<ellipse fill="none" stroke="black" cx="145" cy="-178" rx="27" ry="18"/> +<text text-anchor="middle" x="145" y="-174.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQNode20->Start2 --> +<g id="edge11" class="edge"> +<title>EQNode20->Start2:p1</title> +<path fill="none" stroke="black" d="M145.93,-196.36C148.75,-249.2 157.02,-408.5 157.92,-473.67"/> +<polygon fill="black" stroke="black" points="154.42,-474.03 158,-484 161.42,-473.97 154.42,-474.03"/> +<text text-anchor="middle" x="142.93" y="-198.96" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQNode20->Phi_a19 --> +<g id="edge12" class="edge"> +<title>EQNode20->Phi_a19</title> +<path fill="none" stroke="black" d="M155.44,-194.88C161.2,-203.66 168.48,-214.74 174.96,-224.58"/> +<polygon fill="black" stroke="black" points="172.19,-226.74 180.6,-233.18 178.04,-222.9 172.19,-226.74"/> +<text text-anchor="middle" x="152.44" y="-197.48" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Return21->Region16 --> +<g id="edge13" class="edge"> +<title>Return21->Region16</title> +<path fill="none" stroke="red" d="M116.96,-124.15C114.56,-134.51 111.51,-147.99 109,-160 104.69,-180.66 100.23,-204.11 96.96,-221.75"/> +<polygon fill="red" stroke="red" points="93.46,-221.44 95.09,-231.9 100.34,-222.7 93.46,-221.44"/> +<text text-anchor="middle" x="113.96" y="-126.75" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return21->EQNode20 --> +<g id="edge14" class="edge"> +<title>Return21->EQNode20</title> +<path fill="none" stroke="black" d="M126.93,-124.3C129.68,-132.3 132.99,-141.98 136.03,-150.85"/> +<polygon fill="black" stroke="black" points="132.75,-152.05 139.3,-160.38 139.37,-149.78 132.75,-152.05"/> +<text text-anchor="middle" x="123.93" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +</g> +</svg> diff --git a/docs/chapter05/05-graph6.gv b/docs/chapter05/05-graph6.gv new file mode 100644 index 00000000..1ad7b94a --- /dev/null +++ b/docs/chapter05/05-graph6.gv @@ -0,0 +1,58 @@ +digraph chapter05 { +/* +int c = 3; +int b = 2; +if (arg == 1) { + b = 3; + c = 4; +} +return c; +*/ + rankdir=BT; + ordering="in"; + concentrate="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" ]; + Con_6 [ label="#3" ]; + Con_8 [ label="#1" ]; + EQNode9 [ label="==" ]; + If10 [ 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="#4" ]; + Region16 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_c17 [ style=filled fillcolor=lightyellow label="φ_c" ]; + Return19 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region16;Phi_c17;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return19[taillabel=0 color=red]; + EQNode9 -> Start2:p1[taillabel=1]; + EQNode9 -> Con_8[taillabel=2]; + If10 -> Start2:p0[taillabel=0 color=red]; + If10 -> EQNode9[taillabel=1]; + Region16 -> If10:p0[taillabel=1 color=red]; + Region16 -> If10:p1[taillabel=2 color=red]; + Phi_c17 -> Region16 [style=dotted taillabel=0]; + Phi_c17 -> Con_15[taillabel=1]; + Phi_c17 -> Con_6[taillabel=2]; + Return19 -> Region16[taillabel=0 color=red]; + Return19 -> Phi_c17[taillabel=1]; +} diff --git a/docs/chapter05/05-graph6.svg b/docs/chapter05/05-graph6.svg new file mode 100644 index 00000000..71527d7f --- /dev/null +++ b/docs/chapter05/05-graph6.svg @@ -0,0 +1,176 @@ +<?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: chapter05 Pages: 1 --> +<svg width="294pt" height="492pt" + viewBox="0.00 0.00 294.00 492.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 488)"> +<title>chapter05</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-488 290,-488 290,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-476 278,-476 278,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="109,-439 109,-464 190,-464 190,-439 109,-439"/> +<polygon fill="none" stroke="black" points="109,-439 109,-464 190,-464 190,-439 109,-439"/> +<text text-anchor="start" x="131" y="-447.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="109,-408 109,-439 190,-439 190,-408 109,-408"/> +<polygon fill="yellow" stroke="transparent" points="114,-413 114,-434 154,-434 154,-413 114,-413"/> +<polygon fill="none" stroke="black" points="114,-413 114,-434 154,-434 154,-413 114,-413"/> +<text text-anchor="start" x="117" y="-419.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="154,-413 154,-434 185,-434 185,-413 154,-413"/> +<text text-anchor="start" x="157" y="-419.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="181,-52 127,-52 127,-16 181,-16 181,-52"/> +<text text-anchor="middle" x="154" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return19 --> +<g id="node10" class="node"> +<title>Return19</title> +<polygon fill="yellow" stroke="black" points="187,-124 121,-124 121,-88 187,-88 187,-124"/> +<text text-anchor="middle" x="154" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return19 --> +<g id="edge1" class="edge"> +<title>Stop3->Return19</title> +<path fill="none" stroke="red" d="M154,-52.3C154,-60.02 154,-69.29 154,-77.89"/> +<polygon fill="red" stroke="red" points="150.5,-77.9 154,-87.9 157.5,-77.9 150.5,-77.9"/> +<text text-anchor="middle" x="151" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Con_6 --> +<g id="node3" class="node"> +<title>Con_6</title> +<ellipse fill="none" stroke="black" cx="43" cy="-264" rx="27" ry="18"/> +<text text-anchor="middle" x="43" y="-260.3" font-family="Times,serif" font-size="14.00">#3</text> +</g> +<!-- Con_8 --> +<g id="node4" class="node"> +<title>Con_8</title> +<ellipse fill="none" stroke="black" cx="243" cy="-436" rx="27" ry="18"/> +<text text-anchor="middle" x="243" y="-432.3" font-family="Times,serif" font-size="14.00">#1</text> +</g> +<!-- EQNode9 --> +<g id="node5" class="node"> +<title>EQNode9</title> +<ellipse fill="none" stroke="black" cx="215" cy="-350" rx="27" ry="18"/> +<text text-anchor="middle" x="215" y="-346.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQNode9->Start2 --> +<g id="edge2" class="edge"> +<title>EQNode9->Start2:p1</title> +<path fill="none" stroke="black" d="M197.73,-364.01C187.32,-373.17 175.33,-386.49 171.36,-401.73"/> +<polygon fill="black" stroke="black" points="167.84,-401.63 170,-412 174.78,-402.54 167.84,-401.63"/> +<text text-anchor="middle" x="194.73" y="-366.61" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQNode9->Con_8 --> +<g id="edge3" class="edge"> +<title>EQNode9->Con_8</title> +<path fill="none" stroke="black" d="M220.67,-368C224.56,-379.69 229.81,-395.44 234.24,-408.73"/> +<polygon fill="black" stroke="black" points="230.96,-409.93 237.44,-418.31 237.6,-407.72 230.96,-409.93"/> +<text text-anchor="middle" x="217.67" y="-370.6" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If10 --> +<g id="node6" class="node"> +<title>If10</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> +<!-- If10->Start2 --> +<g id="edge4" class="edge"> +<title>If10->Start2:p0</title> +<path fill="none" stroke="red" d="M185.76,-296.14C164.32,-322.05 138.32,-361.17 134.48,-401.9"/> +<polygon fill="red" stroke="red" points="130.98,-401.84 134,-412 137.97,-402.18 130.98,-401.84"/> +<text text-anchor="middle" x="182.76" y="-298.74" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If10->EQNode9 --> +<g id="edge5" class="edge"> +<title>If10->EQNode9</title> +<path fill="none" stroke="black" d="M215,-296.28C215,-304.58 215,-313.48 215,-321.56"/> +<polygon fill="black" stroke="black" points="211.5,-321.6 215,-331.6 218.5,-321.6 211.5,-321.6"/> +<text text-anchor="middle" x="212" y="-298.88" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_15 --> +<g id="node7" class="node"> +<title>Con_15</title> +<ellipse fill="none" stroke="black" cx="115" cy="-264" rx="27" ry="18"/> +<text text-anchor="middle" x="115" y="-260.3" font-family="Times,serif" font-size="14.00">#4</text> +</g> +<!-- Region16 --> +<g id="node8" class="node"> +<title>Region16</title> +<polygon fill="yellow" stroke="black" points="226,-196 160,-196 160,-160 226,-160 226,-196"/> +<text text-anchor="middle" x="193" y="-174.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Region16->If10 --> +<g id="edge6" class="edge"> +<title>Region16->If10:p0</title> +<path fill="none" stroke="red" d="M193,-196.09C193,-205.55 193,-217.77 193,-229.69"/> +<polygon fill="red" stroke="red" points="189.5,-230 193,-240 196.5,-230 189.5,-230"/> +<text text-anchor="middle" x="190" y="-198.69" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region16->If10 --> +<g id="edge7" class="edge"> +<title>Region16->If10:p1</title> +<path fill="none" stroke="red" d="M213.02,-196.12C221.64,-205.06 230.48,-216.84 233.71,-229.84"/> +<polygon fill="red" stroke="red" points="230.27,-230.52 235,-240 237.22,-229.64 230.27,-230.52"/> +<text text-anchor="middle" x="210.02" y="-198.72" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_c17 --> +<g id="node9" class="node"> +<title>Phi_c17</title> +<ellipse fill="lightyellow" stroke="black" cx="115" cy="-178" rx="27" ry="18"/> +<text text-anchor="middle" x="115" y="-174.3" font-family="Times,serif" font-size="14.00">φ_c</text> +</g> +<!-- Phi_c17->Con_6 --> +<g id="edge10" class="edge"> +<title>Phi_c17->Con_6</title> +<path fill="none" stroke="black" d="M102.13,-194.02C91.07,-206.92 74.96,-225.71 62.35,-240.42"/> +<polygon fill="black" stroke="black" points="59.61,-238.24 55.76,-248.11 64.93,-242.8 59.61,-238.24"/> +<text text-anchor="middle" x="99.13" y="-196.62" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_c17->Con_15 --> +<g id="edge9" class="edge"> +<title>Phi_c17->Con_15</title> +<path fill="none" stroke="black" d="M115,-196.4C115,-207.74 115,-222.77 115,-235.68"/> +<polygon fill="black" stroke="black" points="111.5,-235.9 115,-245.9 118.5,-235.9 111.5,-235.9"/> +<text text-anchor="middle" x="112" y="-199" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_c17->Region16 --> +<g id="edge8" class="edge"> +<title>Phi_c17->Region16</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M142.12,-178C144.58,-178 147.04,-178 149.5,-178"/> +<polygon fill="black" stroke="black" points="149.61,-181.5 159.61,-178 149.61,-174.5 149.61,-181.5"/> +<text text-anchor="middle" x="145.12" y="-171.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return19->Region16 --> +<g id="edge11" class="edge"> +<title>Return19->Region16</title> +<path fill="none" stroke="red" d="M163.64,-124.3C168.13,-132.36 173.56,-142.11 178.52,-151.02"/> +<polygon fill="red" stroke="red" points="175.55,-152.86 183.47,-159.9 181.66,-149.46 175.55,-152.86"/> +<text text-anchor="middle" x="160.64" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return19->Phi_c17 --> +<g id="edge12" class="edge"> +<title>Return19->Phi_c17</title> +<path fill="none" stroke="black" d="M144.36,-124.3C139.69,-132.68 134,-142.9 128.87,-152.1"/> +<polygon fill="black" stroke="black" points="125.8,-150.42 123.99,-160.86 131.92,-153.82 125.8,-150.42"/> +<text text-anchor="middle" x="141.36" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +</g> +</svg> diff --git a/docs/chapter05/05-graph7.gv b/docs/chapter05/05-graph7.gv new file mode 100644 index 00000000..3abd6455 --- /dev/null +++ b/docs/chapter05/05-graph7.gv @@ -0,0 +1,72 @@ +digraph chapter05 { +/* +int a=arg+1; +int b=arg+2; +if( arg==1 ) + b=b+a; +else + a=b+1; +return a+b; +*/ + rankdir=BT; + ordering="in"; + concentrate="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" ]; + Phi_b37 [ style=filled fillcolor=lightyellow label="φ_b" ]; + Con_10 [ label="#1" ]; + Add42 [ label="+" ]; + EQNode11 [ label="==" ]; + If12 [ 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_46 [ label="#4" ]; + Con_48 [ label="#5" ]; + Phi_ab49 [ style=filled fillcolor=lightyellow label="φ_ab" ]; + Add50 [ label="+" ]; + Con_19 [ label="#2" ]; + Return51 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Mul20 [ label="*" ]; + Region31 [ shape=box style=filled fillcolor=yellow label="Region" ]; + { rank=same; Region31;Phi_b37;Phi_ab49;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return51[taillabel=0 color=red]; + Phi_b37 -> Region31 [style=dotted taillabel=0]; + Phi_b37 -> Mul20[taillabel=1]; + Phi_b37 -> Start2:p1[taillabel=2]; + Add42 -> Phi_b37[taillabel=1]; + Add42 -> Start2:p1[taillabel=2]; + EQNode11 -> Start2:p1[taillabel=1]; + EQNode11 -> Con_10[taillabel=2]; + If12 -> Start2:p0[taillabel=0 color=red]; + If12 -> EQNode11[taillabel=1]; + Phi_ab49 -> Region31 [style=dotted taillabel=0]; + Phi_ab49 -> Con_46[taillabel=1]; + Phi_ab49 -> Con_48[taillabel=2]; + Add50 -> Add42[taillabel=1]; + Add50 -> Phi_ab49[taillabel=2]; + Return51 -> Region31[taillabel=0 color=red]; + Return51 -> Add50[taillabel=1]; + Mul20 -> Start2:p1[taillabel=1]; + Mul20 -> Con_19[taillabel=2]; + Region31 -> If12:p0[taillabel=1 color=red]; + Region31 -> If12:p1[taillabel=2 color=red]; +} diff --git a/docs/chapter05/05-graph7.svg b/docs/chapter05/05-graph7.svg new file mode 100644 index 00000000..8ba5ebd6 --- /dev/null +++ b/docs/chapter05/05-graph7.svg @@ -0,0 +1,269 @@ +<?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: chapter05 Pages: 1 --> +<svg width="386pt" height="636pt" + viewBox="0.00 0.00 386.00 636.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 632)"> +<title>chapter05</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-632 382,-632 382,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-620 370,-620 370,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="187,-583 187,-608 268,-608 268,-583 187,-583"/> +<polygon fill="none" stroke="black" points="187,-583 187,-608 268,-608 268,-583 187,-583"/> +<text text-anchor="start" x="209" y="-591.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="187,-552 187,-583 268,-583 268,-552 187,-552"/> +<polygon fill="yellow" stroke="transparent" points="192,-557 192,-578 232,-578 232,-557 192,-557"/> +<polygon fill="none" stroke="black" points="192,-557 192,-578 232,-578 232,-557 192,-557"/> +<text text-anchor="start" x="195" y="-563.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="232,-557 232,-578 263,-578 263,-557 232,-557"/> +<text text-anchor="start" x="235" y="-563.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="230,-52 176,-52 176,-16 230,-16 230,-52"/> +<text text-anchor="middle" x="203" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return51 --> +<g id="node13" class="node"> +<title>Return51</title> +<polygon fill="yellow" stroke="black" points="236,-124 170,-124 170,-88 236,-88 236,-124"/> +<text text-anchor="middle" x="203" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return51 --> +<g id="edge1" class="edge"> +<title>Stop3->Return51</title> +<path fill="none" stroke="red" d="M203,-52.3C203,-60.02 203,-69.29 203,-77.89"/> +<polygon fill="red" stroke="red" points="199.5,-77.9 203,-87.9 206.5,-77.9 199.5,-77.9"/> +<text text-anchor="middle" x="200" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Phi_b37 --> +<g id="node3" class="node"> +<title>Phi_b37</title> +<ellipse fill="lightyellow" stroke="black" cx="63" cy="-322" rx="27.1" ry="18"/> +<text text-anchor="middle" x="63" y="-318.3" font-family="Times,serif" font-size="14.00">φ_b</text> +</g> +<!-- Phi_b37->Start2 --> +<g id="edge4" class="edge"> +<title>Phi_b37->Start2:p1</title> +<path fill="none" stroke="black" d="M50.14,-338.15C37.78,-354.08 20.49,-380.46 17,-407"/> +<text text-anchor="middle" x="47.14" y="-340.75" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Mul20 --> +<g id="node14" class="node"> +<title>Mul20</title> +<ellipse fill="none" stroke="black" cx="63" cy="-408" rx="27" ry="18"/> +<text text-anchor="middle" x="63" y="-404.3" font-family="Times,serif" font-size="14.00">*</text> +</g> +<!-- Phi_b37->Mul20 --> +<g id="edge3" class="edge"> +<title>Phi_b37->Mul20</title> +<path fill="none" stroke="black" d="M63,-340.4C63,-351.74 63,-366.77 63,-379.68"/> +<polygon fill="black" stroke="black" points="59.5,-379.9 63,-389.9 66.5,-379.9 59.5,-379.9"/> +<text text-anchor="middle" x="60" y="-343" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region31 --> +<g id="node15" class="node"> +<title>Region31</title> +<polygon fill="yellow" stroke="black" points="287,-340 221,-340 221,-304 287,-304 287,-340"/> +<text text-anchor="middle" x="254" y="-318.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Phi_b37->Region31 --> +<g id="edge2" class="edge"> +<title>Phi_b37->Region31</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M83.07,-309.47C97.9,-300.98 118.92,-290.52 139,-286 166.75,-279.76 175.89,-277.4 203,-286 210.99,-288.54 218.81,-292.83 225.83,-297.58"/> +<polygon fill="black" stroke="black" points="224.11,-300.66 234.24,-303.75 228.25,-295.01 224.11,-300.66"/> +<text text-anchor="middle" x="80.07" y="-303.07" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Con_10 --> +<g id="node4" class="node"> +<title>Con_10</title> +<ellipse fill="none" stroke="black" cx="321" cy="-580" rx="27" ry="18"/> +<text text-anchor="middle" x="321" y="-576.3" font-family="Times,serif" font-size="14.00">#1</text> +</g> +<!-- Add42 --> +<g id="node5" class="node"> +<title>Add42</title> +<ellipse fill="none" stroke="black" cx="63" cy="-250" rx="27" ry="18"/> +<text text-anchor="middle" x="63" y="-246.3" font-family="Times,serif" font-size="14.00">+</text> +</g> +<!-- Add42->Start2 --> +<g id="edge6" class="edge"> +<title>Add42->Start2:p1</title> +<path fill="none" stroke="black" d="M49.72,-266.09C41.69,-276.12 32.07,-289.98 27,-304 11.37,-347.26 22.99,-361.4 17,-407"/> +<path fill="none" stroke="black" d="M17,-409C11.54,-445.93 0.41,-459.55 17,-493"/> +<path fill="none" stroke="black" d="M17,-495C20.89,-502.85 19.85,-506.92 27,-512 102.92,-565.95 228.75,-471 246.01,-537.97"/> +<polygon fill="black" stroke="black" points="242.59,-538.7 247.67,-548 249.49,-537.56 242.59,-538.7"/> +<text text-anchor="middle" x="46.72" y="-268.69" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Add42->Phi_b37 --> +<g id="edge5" class="edge"> +<title>Add42->Phi_b37</title> +<path fill="none" stroke="black" d="M63,-268.3C63,-276.02 63,-285.29 63,-293.89"/> +<polygon fill="black" stroke="black" points="59.5,-293.9 63,-303.9 66.5,-293.9 59.5,-293.9"/> +<text text-anchor="middle" x="60" y="-270.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQNode11 --> +<g id="node6" class="node"> +<title>EQNode11</title> +<ellipse fill="none" stroke="black" cx="307" cy="-494" rx="27" ry="18"/> +<text text-anchor="middle" x="307" y="-490.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQNode11->Start2 --> +<g id="edge7" class="edge"> +<title>EQNode11->Start2:p1</title> +<path fill="none" stroke="black" d="M300.78,-511.7C294.25,-528.15 283.48,-552.23 273.01,-562.3"/> +<polygon fill="black" stroke="black" points="271.25,-559.27 264,-567 274.49,-565.48 271.25,-559.27"/> +<text text-anchor="middle" x="297.78" y="-514.3" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQNode11->Con_10 --> +<g id="edge8" class="edge"> +<title>EQNode11->Con_10</title> +<path fill="none" stroke="black" d="M309.83,-512C311.75,-523.5 314.32,-538.93 316.51,-552.08"/> +<polygon fill="black" stroke="black" points="313.07,-552.74 318.17,-562.03 319.98,-551.59 313.07,-552.74"/> +<text text-anchor="middle" x="306.83" y="-514.6" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If12 --> +<g id="node7" class="node"> +<title>If12</title> +<polygon fill="yellow" stroke="transparent" points="260,-411 260,-436 354,-436 354,-411 260,-411"/> +<polygon fill="none" stroke="black" points="260,-411 260,-436 354,-436 354,-411 260,-411"/> +<text text-anchor="start" x="301.5" y="-419.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="260,-380 260,-411 354,-411 354,-380 260,-380"/> +<polygon fill="yellow" stroke="transparent" points="265,-385 265,-406 305,-406 305,-385 265,-385"/> +<polygon fill="none" stroke="black" points="265,-385 265,-406 305,-406 305,-385 265,-385"/> +<text text-anchor="start" x="268" y="-391.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="305,-385 305,-406 349,-406 349,-385 305,-385"/> +<polygon fill="none" stroke="black" points="305,-385 305,-406 349,-406 349,-385 305,-385"/> +<text text-anchor="start" x="308" y="-391.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If12->Start2 --> +<g id="edge9" class="edge"> +<title>If12->Start2:p0</title> +<path fill="none" stroke="red" d="M271.9,-440.02C246.84,-465.46 216.84,-504 212.53,-545.87"/> +<polygon fill="red" stroke="red" points="209.02,-545.83 212,-556 216.01,-546.2 209.02,-545.83"/> +<text text-anchor="middle" x="268.9" y="-442.62" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If12->EQNode11 --> +<g id="edge10" class="edge"> +<title>If12->EQNode11</title> +<path fill="none" stroke="black" d="M307,-440.28C307,-448.58 307,-457.48 307,-465.56"/> +<polygon fill="black" stroke="black" points="303.5,-465.6 307,-475.6 310.5,-465.6 303.5,-465.6"/> +<text text-anchor="middle" x="304" y="-442.88" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_46 --> +<g id="node8" class="node"> +<title>Con_46</title> +<ellipse fill="none" stroke="black" cx="135" cy="-408" rx="27" ry="18"/> +<text text-anchor="middle" x="135" y="-404.3" font-family="Times,serif" font-size="14.00">#4</text> +</g> +<!-- Con_48 --> +<g id="node9" class="node"> +<title>Con_48</title> +<ellipse fill="none" stroke="black" cx="207" cy="-408" rx="27" ry="18"/> +<text text-anchor="middle" x="207" y="-404.3" font-family="Times,serif" font-size="14.00">#5</text> +</g> +<!-- Phi_ab49 --> +<g id="node10" class="node"> +<title>Phi_ab49</title> +<ellipse fill="lightyellow" stroke="black" cx="171" cy="-322" rx="32.49" ry="18"/> +<text text-anchor="middle" x="171" y="-318.3" font-family="Times,serif" font-size="14.00">φ_ab</text> +</g> +<!-- Phi_ab49->Con_46 --> +<g id="edge12" class="edge"> +<title>Phi_ab49->Con_46</title> +<path fill="none" stroke="black" d="M163.89,-339.6C158.81,-351.45 151.88,-367.62 146.08,-381.15"/> +<polygon fill="black" stroke="black" points="142.82,-379.87 142.1,-390.44 149.25,-382.63 142.82,-379.87"/> +<text text-anchor="middle" x="160.89" y="-342.2" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_ab49->Con_48 --> +<g id="edge13" class="edge"> +<title>Phi_ab49->Con_48</title> +<path fill="none" stroke="black" d="M178.11,-339.6C183.19,-351.45 190.12,-367.62 195.92,-381.15"/> +<polygon fill="black" stroke="black" points="192.75,-382.63 199.9,-390.44 199.18,-379.87 192.75,-382.63"/> +<text text-anchor="middle" x="175.11" y="-342.2" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_ab49->Region31 --> +<g id="edge11" class="edge"> +<title>Phi_ab49->Region31</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M203.75,-322C206.03,-322 208.32,-322 210.6,-322"/> +<polygon fill="black" stroke="black" points="210.63,-325.5 220.63,-322 210.63,-318.5 210.63,-325.5"/> +<text text-anchor="middle" x="206.75" y="-315.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Add50 --> +<g id="node11" class="node"> +<title>Add50</title> +<ellipse fill="none" stroke="black" cx="171" cy="-178" rx="27" ry="18"/> +<text text-anchor="middle" x="171" y="-174.3" font-family="Times,serif" font-size="14.00">+</text> +</g> +<!-- Add50->Add42 --> +<g id="edge14" class="edge"> +<title>Add50->Add42</title> +<path fill="none" stroke="black" d="M152.19,-191.19C135,-202.33 109.38,-218.94 90.01,-231.5"/> +<polygon fill="black" stroke="black" points="88.08,-228.57 81.6,-236.95 91.89,-234.44 88.08,-228.57"/> +<text text-anchor="middle" x="149.19" y="-193.79" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Add50->Phi_ab49 --> +<g id="edge15" class="edge"> +<title>Add50->Phi_ab49</title> +<path fill="none" stroke="black" d="M171,-196.13C171,-220.33 171,-264.79 171,-293.61"/> +<polygon fill="black" stroke="black" points="167.5,-293.81 171,-303.81 174.5,-293.81 167.5,-293.81"/> +<text text-anchor="middle" x="168" y="-198.73" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Con_19 --> +<g id="node12" class="node"> +<title>Con_19</title> +<ellipse fill="none" stroke="black" cx="63" cy="-494" rx="27" ry="18"/> +<text text-anchor="middle" x="63" y="-490.3" font-family="Times,serif" font-size="14.00">#2</text> +</g> +<!-- Return51->Add50 --> +<g id="edge17" class="edge"> +<title>Return51->Add50</title> +<path fill="none" stroke="black" d="M195.09,-124.3C191.39,-132.39 186.91,-142.19 182.83,-151.13"/> +<polygon fill="black" stroke="black" points="179.57,-149.83 178.6,-160.38 185.94,-152.74 179.57,-149.83"/> +<text text-anchor="middle" x="192.09" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Return51->Region31 --> +<g id="edge16" class="edge"> +<title>Return51->Region31</title> +<path fill="none" stroke="red" d="M207.09,-124.15C215.93,-161.25 236.89,-249.19 247.54,-293.9"/> +<polygon fill="red" stroke="red" points="244.17,-294.85 249.89,-303.77 250.98,-293.23 244.17,-294.85"/> +<text text-anchor="middle" x="204.09" y="-126.75" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Mul20->Start2 --> +<g id="edge18" class="edge"> +<title>Mul20->Start2:p1</title> +<path fill="none" stroke="black" d="M46.66,-422.5C28.85,-438.94 4.44,-467.68 17,-493"/> +<text text-anchor="middle" x="43.66" y="-425.1" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Mul20->Con_19 --> +<g id="edge19" class="edge"> +<title>Mul20->Con_19</title> +<path fill="none" stroke="black" d="M63,-426.4C63,-437.74 63,-452.77 63,-465.68"/> +<polygon fill="black" stroke="black" points="59.5,-465.9 63,-475.9 66.5,-465.9 59.5,-465.9"/> +<text text-anchor="middle" x="60" y="-429" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Region31->If12 --> +<g id="edge20" class="edge"> +<title>Region31->If12:p0</title> +<path fill="none" stroke="red" d="M268.23,-340.25C274.66,-349.42 281.38,-361.37 283.93,-373.89"/> +<polygon fill="red" stroke="red" points="280.47,-374.42 285,-384 287.43,-373.69 280.47,-374.42"/> +<text text-anchor="middle" x="265.23" y="-342.85" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region31->If12 --> +<g id="edge21" class="edge"> +<title>Region31->If12:p1</title> +<path fill="none" stroke="red" d="M287.08,-335.84C303.38,-344.18 320.59,-356.74 325.57,-373.96"/> +<polygon fill="red" stroke="red" points="322.13,-374.59 327,-384 329.06,-373.61 322.13,-374.59"/> +<text text-anchor="middle" x="290.08" y="-329.44" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +</g> +</svg> diff --git a/docs/chapter05/05-graph8.gv b/docs/chapter05/05-graph8.gv new file mode 100644 index 00000000..2af43847 --- /dev/null +++ b/docs/chapter05/05-graph8.gv @@ -0,0 +1,129 @@ +digraph chapter05 { +/* +int a=1; +if( arg==1 ) + if( arg==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +#showGraph; +*/ + rankdir=BT; + ordering="in"; + concentrate="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" ]; + Con_7 [ label="#1" ]; + EQNode8 [ label="==" ]; + If9 [ 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_13 [ label="#2" ]; + EQNode14 [ label="==" ]; + If15 [ 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_19 [ label="#2" ]; + Con_20 [ label="#3" ]; + Region21 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a22 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Con_23 [ label="#3" ]; + EQNode24 [ label="==" ]; + If25 [ 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_29 [ label="#4" ]; + Con_30 [ label="#5" ]; + Region31 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a32 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Region33 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a34 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Return35 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region21;Phi_a22;} + { rank=same; Region31;Phi_a32;} + { rank=same; Region33;Phi_a34;} + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope1_0_$ctrl">$ctrl</TD><TD PORT="Scope1_0_arg">arg</TD></TR> + </TABLE>>]; + subgraph cluster_Scope1_1 { + Scope1_1 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">1</TD><TD PORT="Scope1_1_a">a</TD></TR> + </TABLE>>]; + } + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return35[taillabel=0 color=red]; + EQNode8 -> Start2:p1[taillabel=1]; + EQNode8 -> Con_7[taillabel=2]; + If9 -> Start2:p0[taillabel=0 color=red]; + If9 -> EQNode8[taillabel=1]; + EQNode14 -> Start2:p1[taillabel=1]; + EQNode14 -> Con_13[taillabel=2]; + If15 -> If9:p0[taillabel=0 color=red]; + If15 -> EQNode14[taillabel=1]; + Region21 -> If15:p0[taillabel=1 color=red]; + Region21 -> If15:p1[taillabel=2 color=red]; + Phi_a22 -> Region21 [style=dotted taillabel=0]; + Phi_a22 -> Con_19[taillabel=1]; + Phi_a22 -> Con_20[taillabel=2]; + EQNode24 -> Start2:p1[taillabel=1]; + EQNode24 -> Con_23[taillabel=2]; + If25 -> If9:p1[taillabel=0 color=red]; + If25 -> EQNode24[taillabel=1]; + Region31 -> If25:p0[taillabel=1 color=red]; + Region31 -> If25:p1[taillabel=2 color=red]; + Phi_a32 -> Region31 [style=dotted taillabel=0]; + Phi_a32 -> Con_29[taillabel=1]; + Phi_a32 -> Con_30[taillabel=2]; + Region33 -> Region21[taillabel=1 color=red]; + Region33 -> Region31[taillabel=2 color=red]; + Phi_a34 -> Region33 [style=dotted taillabel=0]; + Phi_a34 -> Phi_a22[taillabel=1]; + Phi_a34 -> Phi_a32[taillabel=2]; + Return35 -> Region33[taillabel=0 color=red]; + Return35 -> Phi_a34[taillabel=1]; + edge [style=dashed color=cornflowerblue]; + Scope1_0:"Scope1_0_arg" -> Start2:p1; + Scope1_1:"Scope1_1_a" -> Phi_a34; +} diff --git a/docs/chapter05/05-graph8.svg b/docs/chapter05/05-graph8.svg new file mode 100644 index 00000000..e5310db4 --- /dev/null +++ b/docs/chapter05/05-graph8.svg @@ -0,0 +1,430 @@ +<?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: chapter05 Pages: 1 --> +<svg width="774pt" height="664pt" + viewBox="0.00 0.00 774.00 664.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 660)"> +<title>chapter05</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-660 770,-660 770,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-648 550,-648 550,-8 8,-8"/> +</g> +<g id="clust5" class="cluster"> +<title>cluster_Scope1_0</title> +<polygon fill="none" stroke="black" points="558,-72 558,-140 758,-140 758,-72 558,-72"/> +</g> +<g id="clust6" class="cluster"> +<title>cluster_Scope1_1</title> +<polygon fill="none" stroke="black" points="566,-80 566,-132 636,-132 636,-80 566,-80"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="190,-611 190,-636 271,-636 271,-611 190,-611"/> +<polygon fill="none" stroke="black" points="190,-611 190,-636 271,-636 271,-611 190,-611"/> +<text text-anchor="start" x="212" y="-619.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="190,-580 190,-611 271,-611 271,-580 190,-580"/> +<polygon fill="yellow" stroke="transparent" points="195,-585 195,-606 235,-606 235,-585 195,-585"/> +<polygon fill="none" stroke="black" points="195,-585 195,-606 235,-606 235,-585 195,-585"/> +<text text-anchor="start" x="198" y="-591.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="235,-585 235,-606 266,-606 266,-585 235,-585"/> +<text text-anchor="start" x="238" y="-591.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="286,-52 232,-52 232,-16 286,-16 286,-52"/> +<text text-anchor="middle" x="259" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return35 --> +<g id="node22" class="node"> +<title>Return35</title> +<polygon fill="yellow" stroke="black" points="292,-124 226,-124 226,-88 292,-88 292,-124"/> +<text text-anchor="middle" x="259" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return35 --> +<g id="edge1" class="edge"> +<title>Stop3->Return35</title> +<path fill="none" stroke="red" d="M259,-52.3C259,-60.02 259,-69.29 259,-77.89"/> +<polygon fill="red" stroke="red" points="255.5,-77.9 259,-87.9 262.5,-77.9 255.5,-77.9"/> +<text text-anchor="middle" x="256" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Con_7 --> +<g id="node3" class="node"> +<title>Con_7</title> +<ellipse fill="none" stroke="black" cx="136" cy="-608" rx="27" ry="18"/> +<text text-anchor="middle" x="136" y="-604.3" font-family="Times,serif" font-size="14.00">#1</text> +</g> +<!-- EQNode8 --> +<g id="node4" class="node"> +<title>EQNode8</title> +<ellipse fill="none" stroke="black" cx="169" cy="-522" rx="27" ry="18"/> +<text text-anchor="middle" x="169" y="-518.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQNode8->Start2 --> +<g id="edge2" class="edge"> +<title>EQNode8->Start2:p1</title> +<path fill="none" stroke="black" d="M190.12,-533.69C209.67,-544.17 237.18,-560.54 247.18,-574.44"/> +<polygon fill="black" stroke="black" points="244.04,-576.01 251,-584 250.54,-573.42 244.04,-576.01"/> +<text text-anchor="middle" x="187.12" y="-536.29" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQNode8->Con_7 --> +<g id="edge3" class="edge"> +<title>EQNode8->Con_7</title> +<path fill="none" stroke="black" d="M162.48,-539.6C157.87,-551.33 151.59,-567.3 146.31,-580.76"/> +<polygon fill="black" stroke="black" points="142.91,-579.85 142.51,-590.44 149.42,-582.41 142.91,-579.85"/> +<text text-anchor="middle" x="159.48" y="-542.2" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If9 --> +<g id="node5" class="node"> +<title>If9</title> +<polygon fill="yellow" stroke="transparent" points="124,-439 124,-464 218,-464 218,-439 124,-439"/> +<polygon fill="none" stroke="black" points="124,-439 124,-464 218,-464 218,-439 124,-439"/> +<text text-anchor="start" x="165.5" y="-447.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="124,-408 124,-439 218,-439 218,-408 124,-408"/> +<polygon fill="yellow" stroke="transparent" points="129,-413 129,-434 169,-434 169,-413 129,-413"/> +<polygon fill="none" stroke="black" points="129,-413 129,-434 169,-434 169,-413 129,-413"/> +<text text-anchor="start" x="132" y="-419.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="169,-413 169,-434 213,-434 213,-413 169,-413"/> +<polygon fill="none" stroke="black" points="169,-413 169,-434 213,-434 213,-413 169,-413"/> +<text text-anchor="start" x="172" y="-419.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If9->Start2 --> +<g id="edge4" class="edge"> +<title>If9->Start2:p0</title> +<path fill="none" stroke="red" d="M189.59,-468.09C195.4,-479.09 201.26,-491.78 205,-504 214.42,-534.78 214.99,-545.9 215,-573.83"/> +<polygon fill="red" stroke="red" points="211.5,-574 215,-584 218.5,-574 211.5,-574"/> +<text text-anchor="middle" x="186.59" y="-470.69" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If9->EQNode8 --> +<g id="edge5" class="edge"> +<title>If9->EQNode8</title> +<path fill="none" stroke="black" d="M170.26,-468.28C170.06,-476.58 169.85,-485.48 169.65,-493.56"/> +<polygon fill="black" stroke="black" points="166.15,-493.51 169.41,-503.6 173.15,-493.68 166.15,-493.51"/> +<text text-anchor="middle" x="167.26" y="-470.88" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_13 --> +<g id="node6" class="node"> +<title>Con_13</title> +<ellipse fill="none" stroke="black" cx="71" cy="-522" rx="27" ry="18"/> +<text text-anchor="middle" x="71" y="-518.3" font-family="Times,serif" font-size="14.00">#2</text> +</g> +<!-- EQNode14 --> +<g id="node7" class="node"> +<title>EQNode14</title> +<ellipse fill="none" stroke="black" cx="71" cy="-436" rx="27" ry="18"/> +<text text-anchor="middle" x="71" y="-432.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQNode14->Start2 --> +<g id="edge6" class="edge"> +<title>EQNode14->Start2:p1</title> +<path fill="none" stroke="black" d="M79.96,-453.18C95.23,-480.56 125.41,-533.7 133,-540 173.12,-573.31 240.9,-534.16 249.98,-573.92"/> +<polygon fill="black" stroke="black" points="246.51,-574.4 251,-584 253.48,-573.7 246.51,-574.4"/> +<text text-anchor="middle" x="76.96" y="-455.78" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQNode14->Con_13 --> +<g id="edge7" class="edge"> +<title>EQNode14->Con_13</title> +<path fill="none" stroke="black" d="M71,-454.4C71,-465.74 71,-480.77 71,-493.68"/> +<polygon fill="black" stroke="black" points="67.5,-493.9 71,-503.9 74.5,-493.9 67.5,-493.9"/> +<text text-anchor="middle" x="68" y="-457" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If15 --> +<g id="node8" class="node"> +<title>If15</title> +<polygon fill="yellow" stroke="transparent" points="24,-339 24,-364 118,-364 118,-339 24,-339"/> +<polygon fill="none" stroke="black" points="24,-339 24,-364 118,-364 118,-339 24,-339"/> +<text text-anchor="start" x="65.5" y="-347.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="24,-308 24,-339 118,-339 118,-308 24,-308"/> +<polygon fill="yellow" stroke="transparent" points="29,-313 29,-334 69,-334 69,-313 29,-313"/> +<polygon fill="none" stroke="black" points="29,-313 29,-334 69,-334 69,-313 29,-313"/> +<text text-anchor="start" x="32" y="-319.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="69,-313 69,-334 113,-334 113,-313 69,-313"/> +<polygon fill="none" stroke="black" points="69,-313 69,-334 113,-334 113,-313 69,-313"/> +<text text-anchor="start" x="72" y="-319.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If15->If9 --> +<g id="edge8" class="edge"> +<title>If15->If9:p0</title> +<path fill="none" stroke="red" d="M88.21,-368.05C98.39,-385.75 110.98,-406.4 119.78,-416.61"/> +<polygon fill="red" stroke="red" points="117.96,-419.62 128,-423 122.25,-414.1 117.96,-419.62"/> +<text text-anchor="middle" x="85.21" y="-370.65" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If15->EQNode14 --> +<g id="edge9" class="edge"> +<title>If15->EQNode14</title> +<path fill="none" stroke="black" d="M71,-368.01C71,-380.76 71,-395.4 71,-407.73"/> +<polygon fill="black" stroke="black" points="67.5,-407.87 71,-417.87 74.5,-407.87 67.5,-407.87"/> +<text text-anchor="middle" x="68" y="-370.61" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_19 --> +<g id="node9" class="node"> +<title>Con_19</title> +<ellipse fill="none" stroke="black" cx="443" cy="-336" rx="27" ry="18"/> +<text text-anchor="middle" x="443" y="-332.3" font-family="Times,serif" font-size="14.00">#2</text> +</g> +<!-- Con_20 --> +<g id="node10" class="node"> +<title>Con_20</title> +<ellipse fill="none" stroke="black" cx="515" cy="-336" rx="27" ry="18"/> +<text text-anchor="middle" x="515" y="-332.3" font-family="Times,serif" font-size="14.00">#3</text> +</g> +<!-- Region21 --> +<g id="node11" class="node"> +<title>Region21</title> +<polygon fill="yellow" stroke="black" points="147,-268 81,-268 81,-232 147,-232 147,-268"/> +<text text-anchor="middle" x="114" y="-246.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Region21->If15 --> +<g id="edge10" class="edge"> +<title>Region21->If15:p0</title> +<path fill="none" stroke="red" d="M80.74,-267.13C67.62,-275.57 54.67,-287.24 50.44,-301.92"/> +<polygon fill="red" stroke="red" points="46.94,-301.61 49,-312 53.87,-302.59 46.94,-301.61"/> +<text text-anchor="middle" x="77.74" y="-260.73" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region21->If15 --> +<g id="edge11" class="edge"> +<title>Region21->If15:p1</title> +<path fill="none" stroke="red" d="M103.71,-268.24C98.93,-277.52 93.86,-289.54 91.87,-301.76"/> +<polygon fill="red" stroke="red" points="88.36,-301.74 91,-312 95.34,-302.33 88.36,-301.74"/> +<text text-anchor="middle" x="100.71" y="-270.84" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_a22 --> +<g id="node12" class="node"> +<title>Phi_a22</title> +<ellipse fill="lightyellow" stroke="black" cx="407" cy="-250" rx="27" ry="18"/> +<text text-anchor="middle" x="407" y="-246.3" font-family="Times,serif" font-size="14.00">φ_a</text> +</g> +<!-- Phi_a22->Con_19 --> +<g id="edge13" class="edge"> +<title>Phi_a22->Con_19</title> +<path fill="none" stroke="black" d="M414.11,-267.6C419.19,-279.45 426.12,-295.62 431.92,-309.15"/> +<polygon fill="black" stroke="black" points="428.75,-310.63 435.9,-318.44 435.18,-307.87 428.75,-310.63"/> +<text text-anchor="middle" x="411.11" y="-270.2" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_a22->Con_20 --> +<g id="edge14" class="edge"> +<title>Phi_a22->Con_20</title> +<path fill="none" stroke="black" d="M425.04,-263.7C439.78,-274.21 461.03,-289.69 479,-304 483.17,-307.32 487.52,-310.94 491.71,-314.49"/> +<polygon fill="black" stroke="black" points="489.59,-317.28 499.45,-321.15 494.15,-311.98 489.59,-317.28"/> +<text text-anchor="middle" x="422.04" y="-266.3" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_a22->Region21 --> +<g id="edge12" class="edge"> +<title>Phi_a22->Region21</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M386.5,-238C370.6,-229.42 347.68,-218.6 326,-214 265.57,-201.18 247.16,-199.97 187,-214 175.19,-216.75 163.08,-221.71 152.22,-227.08"/> +<polygon fill="black" stroke="black" points="150.28,-224.14 143.03,-231.86 153.51,-230.35 150.28,-224.14"/> +<text text-anchor="middle" x="383.5" y="-231.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Con_23 --> +<g id="node13" class="node"> +<title>Con_23</title> +<ellipse fill="none" stroke="black" cx="297" cy="-522" rx="27" ry="18"/> +<text text-anchor="middle" x="297" y="-518.3" font-family="Times,serif" font-size="14.00">#3</text> +</g> +<!-- EQNode24 --> +<g id="node14" class="node"> +<title>EQNode24</title> +<ellipse fill="none" stroke="black" cx="271" cy="-436" rx="27" ry="18"/> +<text text-anchor="middle" x="271" y="-432.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQNode24->Start2 --> +<g id="edge15" class="edge"> +<title>EQNode24->Start2:p1</title> +<path fill="none" stroke="black" d="M267.14,-454.1C261.74,-479.48 252.43,-528.98 251.15,-573.9"/> +<polygon fill="black" stroke="black" points="247.65,-573.95 251,-584 254.65,-574.05 247.65,-573.95"/> +<text text-anchor="middle" x="264.14" y="-456.7" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQNode24->Con_23 --> +<g id="edge16" class="edge"> +<title>EQNode24->Con_23</title> +<path fill="none" stroke="black" d="M276.26,-454C279.88,-465.69 284.76,-481.44 288.87,-494.73"/> +<polygon fill="black" stroke="black" points="285.53,-495.8 291.84,-504.31 292.22,-493.73 285.53,-495.8"/> +<text text-anchor="middle" x="273.26" y="-456.6" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If25 --> +<g id="node15" class="node"> +<title>If25</title> +<polygon fill="yellow" stroke="transparent" points="152,-339 152,-364 246,-364 246,-339 152,-339"/> +<polygon fill="none" stroke="black" points="152,-339 152,-364 246,-364 246,-339 152,-339"/> +<text text-anchor="start" x="193.5" y="-347.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="152,-308 152,-339 246,-339 246,-308 152,-308"/> +<polygon fill="yellow" stroke="transparent" points="157,-313 157,-334 197,-334 197,-313 157,-313"/> +<polygon fill="none" stroke="black" points="157,-313 157,-334 197,-334 197,-313 157,-313"/> +<text text-anchor="start" x="160" y="-319.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="197,-313 197,-334 241,-334 241,-313 197,-313"/> +<polygon fill="none" stroke="black" points="197,-313 197,-334 241,-334 241,-313 197,-313"/> +<text text-anchor="start" x="200" y="-319.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If25->If9 --> +<g id="edge17" class="edge"> +<title>If25->If9:p1</title> +<path fill="none" stroke="red" d="M194.16,-368.3C192.87,-378.58 191.7,-390.29 191.23,-401.68"/> +<polygon fill="red" stroke="red" points="187.72,-401.93 191,-412 194.72,-402.08 187.72,-401.93"/> +<text text-anchor="middle" x="191.16" y="-370.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If25->EQNode24 --> +<g id="edge18" class="edge"> +<title>If25->EQNode24</title> +<path fill="none" stroke="black" d="M221.78,-368.01C232.02,-381.95 243.93,-398.15 253.46,-411.12"/> +<polygon fill="black" stroke="black" points="250.89,-413.54 259.63,-419.53 256.53,-409.39 250.89,-413.54"/> +<text text-anchor="middle" x="218.78" y="-370.61" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_29 --> +<g id="node16" class="node"> +<title>Con_29</title> +<ellipse fill="none" stroke="black" cx="299" cy="-336" rx="27" ry="18"/> +<text text-anchor="middle" x="299" y="-332.3" font-family="Times,serif" font-size="14.00">#4</text> +</g> +<!-- Con_30 --> +<g id="node17" class="node"> +<title>Con_30</title> +<ellipse fill="none" stroke="black" cx="371" cy="-336" rx="27" ry="18"/> +<text text-anchor="middle" x="371" y="-332.3" font-family="Times,serif" font-size="14.00">#5</text> +</g> +<!-- Region31 --> +<g id="node18" class="node"> +<title>Region31</title> +<polygon fill="yellow" stroke="black" points="253,-268 187,-268 187,-232 253,-232 253,-268"/> +<text text-anchor="middle" x="220" y="-246.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Region31->If25 --> +<g id="edge19" class="edge"> +<title>Region31->If25:p0</title> +<path fill="none" stroke="red" d="M199.51,-268.03C190.68,-276.94 181.63,-288.71 178.32,-301.78"/> +<polygon fill="red" stroke="red" points="174.81,-301.63 177,-312 181.75,-302.53 174.81,-301.63"/> +<text text-anchor="middle" x="196.51" y="-270.63" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region31->If25 --> +<g id="edge20" class="edge"> +<title>Region31->If25:p1</title> +<path fill="none" stroke="red" d="M219.57,-268.09C219.36,-277.55 219.13,-289.77 219.04,-301.69"/> +<polygon fill="red" stroke="red" points="215.54,-301.99 219,-312 222.54,-302.01 215.54,-301.99"/> +<text text-anchor="middle" x="216.57" y="-270.69" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_a32 --> +<g id="node19" class="node"> +<title>Phi_a32</title> +<ellipse fill="lightyellow" stroke="black" cx="299" cy="-250" rx="27" ry="18"/> +<text text-anchor="middle" x="299" y="-246.3" font-family="Times,serif" font-size="14.00">φ_a</text> +</g> +<!-- Phi_a32->Con_29 --> +<g id="edge22" class="edge"> +<title>Phi_a32->Con_29</title> +<path fill="none" stroke="black" d="M299,-268.4C299,-279.74 299,-294.77 299,-307.68"/> +<polygon fill="black" stroke="black" points="295.5,-307.9 299,-317.9 302.5,-307.9 295.5,-307.9"/> +<text text-anchor="middle" x="296" y="-271" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_a32->Con_30 --> +<g id="edge23" class="edge"> +<title>Phi_a32->Con_30</title> +<path fill="none" stroke="black" d="M311.87,-266.02C322.93,-278.92 339.04,-297.71 351.65,-312.42"/> +<polygon fill="black" stroke="black" points="349.07,-314.8 358.24,-320.11 354.39,-310.24 349.07,-314.8"/> +<text text-anchor="middle" x="308.87" y="-268.62" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_a32->Region31 --> +<g id="edge21" class="edge"> +<title>Phi_a32->Region31</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M271.7,-250C268.88,-250 266.06,-250 263.23,-250"/> +<polygon fill="black" stroke="black" points="263.02,-246.5 253.02,-250 263.02,-253.5 263.02,-246.5"/> +<text text-anchor="middle" x="268.7" y="-243.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Region33 --> +<g id="node20" class="node"> +<title>Region33</title> +<polygon fill="yellow" stroke="black" points="253,-196 187,-196 187,-160 253,-160 253,-196"/> +<text text-anchor="middle" x="220" y="-174.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Region33->Region21 --> +<g id="edge24" class="edge"> +<title>Region33->Region21</title> +<path fill="none" stroke="red" d="M194.07,-196.12C180.34,-205.19 163.29,-216.45 148.46,-226.24"/> +<polygon fill="red" stroke="red" points="146.45,-223.38 140.03,-231.81 150.3,-229.22 146.45,-223.38"/> +<text text-anchor="middle" x="191.07" y="-198.72" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region33->Region31 --> +<g id="edge25" class="edge"> +<title>Region33->Region31</title> +<path fill="none" stroke="red" d="M220,-196.3C220,-204.02 220,-213.29 220,-221.89"/> +<polygon fill="red" stroke="red" points="216.5,-221.9 220,-231.9 223.5,-221.9 216.5,-221.9"/> +<text text-anchor="middle" x="217" y="-198.9" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_a34 --> +<g id="node21" class="node"> +<title>Phi_a34</title> +<ellipse fill="lightyellow" stroke="black" cx="299" cy="-178" rx="27" ry="18"/> +<text text-anchor="middle" x="299" y="-174.3" font-family="Times,serif" font-size="14.00">φ_a</text> +</g> +<!-- Phi_a34->Phi_a22 --> +<g id="edge27" class="edge"> +<title>Phi_a34->Phi_a22</title> +<path fill="none" stroke="black" d="M317.81,-191.19C335,-202.33 360.62,-218.94 379.99,-231.5"/> +<polygon fill="black" stroke="black" points="378.11,-234.44 388.4,-236.95 381.92,-228.57 378.11,-234.44"/> +<text text-anchor="middle" x="314.81" y="-193.79" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_a34->Phi_a32 --> +<g id="edge28" class="edge"> +<title>Phi_a34->Phi_a32</title> +<path fill="none" stroke="black" d="M299,-196.3C299,-204.02 299,-213.29 299,-221.89"/> +<polygon fill="black" stroke="black" points="295.5,-221.9 299,-231.9 302.5,-221.9 295.5,-221.9"/> +<text text-anchor="middle" x="296" y="-198.9" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_a34->Region33 --> +<g id="edge26" class="edge"> +<title>Phi_a34->Region33</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M271.7,-178C268.88,-178 266.06,-178 263.23,-178"/> +<polygon fill="black" stroke="black" points="263.02,-174.5 253.02,-178 263.02,-181.5 263.02,-174.5"/> +<text text-anchor="middle" x="268.7" y="-171.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return35->Region33 --> +<g id="edge29" class="edge"> +<title>Return35->Region33</title> +<path fill="none" stroke="red" d="M249.36,-124.3C244.87,-132.36 239.44,-142.11 234.48,-151.02"/> +<polygon fill="red" stroke="red" points="231.34,-149.46 229.53,-159.9 237.45,-152.86 231.34,-149.46"/> +<text text-anchor="middle" x="246.36" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return35->Phi_a34 --> +<g id="edge30" class="edge"> +<title>Return35->Phi_a34</title> +<path fill="none" stroke="black" d="M268.89,-124.3C273.68,-132.68 279.52,-142.9 284.77,-152.1"/> +<polygon fill="black" stroke="black" points="281.77,-153.91 289.77,-160.86 287.85,-150.44 281.77,-153.91"/> +<text text-anchor="middle" x="265.89" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Scope1_0 --> +<g id="node23" class="node"> +<title>Scope1_0</title> +<polygon fill="cyan" stroke="transparent" points="655,-95 655,-116 671,-116 671,-95 655,-95"/> +<polygon fill="none" stroke="black" points="655,-95 655,-116 671,-116 671,-95 655,-95"/> +<text text-anchor="start" x="658" y="-101.8" font-family="Times,serif" font-size="14.00">0</text> +<polygon fill="none" stroke="black" points="671,-95 671,-116 711,-116 711,-95 671,-95"/> +<text text-anchor="start" x="674" y="-101.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="711,-95 711,-116 742,-116 742,-95 711,-95"/> +<text text-anchor="start" x="714" y="-101.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- Scope1_0->Start2 --> +<g id="edge31" class="edge"> +<title>Scope1_0:Scope1_0_arg->Start2:p1</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M727,-117C727,-185.37 648,-180.63 648,-249 648,-249 648,-249 648,-437 648,-525.53 378.1,-590.44 277.07,-594.77"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="276.92,-591.27 267,-595 277.08,-598.27 276.92,-591.27"/> +</g> +<!-- Scope1_1 --> +<g id="node24" class="node"> +<title>Scope1_1</title> +<polygon fill="cyan" stroke="transparent" points="586,-95 586,-116 602,-116 602,-95 586,-95"/> +<polygon fill="none" stroke="black" points="586,-95 586,-116 602,-116 602,-95 586,-95"/> +<text text-anchor="start" x="589" y="-101.8" font-family="Times,serif" font-size="14.00">1</text> +<polygon fill="none" stroke="black" points="602,-95 602,-116 617,-116 617,-95 602,-95"/> +<text text-anchor="start" x="605" y="-101.8" font-family="Times,serif" font-size="14.00">a</text> +</g> +<!-- Scope1_1->Phi_a34 --> +<g id="edge32" class="edge"> +<title>Scope1_1:Scope1_1_a->Phi_a34</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M610,-117C610,-172.18 418.84,-177.72 336.26,-177.53"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="336.07,-174.03 326.06,-177.48 336.04,-181.03 336.07,-174.03"/> +</g> +</g> +</svg> diff --git a/docs/chapter05/05-graph9.svg b/docs/chapter05/05-graph9.svg new file mode 100644 index 00000000..dff4d63f --- /dev/null +++ b/docs/chapter05/05-graph9.svg @@ -0,0 +1,174 @@ +<?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.40.1 (20161225.0304) + --> +<!-- Title: chapter05 Pages: 1 --> +<svg width="277pt" height="496pt" viewBox="0.00 0.00 277.00 496.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 492)"> +<title>chapter05</title> +<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-492 273,-492 273,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="#000000" points="8,-8 8,-480 261,-480 261,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="#ffff00" stroke="transparent" points="109,-442 109,-468 173,-468 173,-442 109,-442"/> +<polygon fill="none" stroke="#000000" points="109,-442 109,-468 173,-468 173,-442 109,-442"/> +<text text-anchor="start" x="127.7805" y="-450.4" font-family="Times,serif" font-size="14.00" fill="#000000">Start</text> +<polygon fill="none" stroke="#000000" points="109,-410 109,-442 173,-442 173,-410 109,-410"/> +<polygon fill="#ffff00" stroke="transparent" points="114,-415 114,-437 145,-437 145,-415 114,-415"/> +<polygon fill="none" stroke="#000000" points="114,-415 114,-437 145,-437 145,-415 114,-415"/> +<text text-anchor="start" x="116.6718" y="-421.4" font-family="Times,serif" font-size="14.00" fill="#000000">$ctrl</text> +<polygon fill="none" stroke="#000000" points="145,-415 145,-437 168,-437 168,-415 145,-415"/> +<text text-anchor="start" x="147.5624" y="-421.4" font-family="Times,serif" font-size="14.00" fill="#000000">arg</text> +</g> +<!-- Stop3 --> +<g id="node2" class="node"> +<title>Stop3</title> +<polygon fill="#ffff00" stroke="#000000" points="179,-52 125,-52 125,-16 179,-16 179,-52"/> +<text text-anchor="middle" x="152" y="-29.8" font-family="Times,serif" font-size="14.00" fill="#000000">Stop</text> +</g> +<!-- Return20 --> +<g id="node10" class="node"> +<title>Return20</title> +<polygon fill="#ffff00" stroke="#000000" points="179.1025,-124 124.8975,-124 124.8975,-88 179.1025,-88 179.1025,-124"/> +<text text-anchor="middle" x="152" y="-101.8" font-family="Times,serif" font-size="14.00" fill="#000000">Return</text> +</g> +<!-- Stop3->Return20 --> +<g id="edge1" class="edge"> +<title>Stop3->Return20</title> +<path fill="none" stroke="#ff0000" d="M152,-52.1686C152,-59.869 152,-69.0257 152,-77.5834"/> +<polygon fill="#ff0000" stroke="#ff0000" points="148.5001,-77.5867 152,-87.5867 155.5001,-77.5868 148.5001,-77.5867"/> +<text text-anchor="middle" x="149.7764" y="-54.5686" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Con_8 --> +<g id="node3" class="node"> +<title>Con_8</title> +<ellipse fill="none" stroke="#000000" cx="226" cy="-439" rx="27" ry="18"/> +<text text-anchor="middle" x="226" y="-434.8" font-family="Times,serif" font-size="14.00" fill="#000000">1</text> +</g> +<!-- EQ9 --> +<g id="node4" class="node"> +<title>EQ9</title> +<ellipse fill="none" stroke="#000000" cx="207" cy="-352" rx="27" ry="18"/> +<text text-anchor="middle" x="207" y="-347.8" font-family="Times,serif" font-size="14.00" fill="#000000">==</text> +</g> +<!-- EQ9->Start2 --> +<g id="edge2" class="edge"> +<title>EQ9->Start2:p1</title> +<path fill="none" stroke="#000000" d="M188.0971,-364.9135C176.261,-374.4033 162.483,-388.4885 158.2807,-405.0084"/> +<polygon fill="#000000" stroke="#000000" points="154.7998,-404.6361 157,-415 161.743,-405.5261 154.7998,-404.6361"/> +<text text-anchor="middle" x="190.3207" y="-367.3135" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +<!-- EQ9->Con_8 --> +<g id="edge3" class="edge"> +<title>EQ9->Con_8</title> +<path fill="none" stroke="#000000" d="M210.9368,-370.0265C213.5098,-381.8082 216.9235,-397.4393 219.8505,-410.8419"/> +<polygon fill="#000000" stroke="#000000" points="216.5151,-411.9737 222.0682,-420.9966 223.3539,-410.4801 216.5151,-411.9737"/> +<text text-anchor="middle" x="208.7132" y="-372.4265" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">2</text> +</g> +<!-- If10 --> +<g id="node5" class="node"> +<title>If10</title> +<polygon fill="#ffff00" stroke="transparent" points="169,-268 169,-294 246,-294 246,-268 169,-268"/> +<polygon fill="none" stroke="#000000" points="169,-268 169,-294 246,-294 246,-268 169,-268"/> +<text text-anchor="start" x="202.8394" y="-276.4" font-family="Times,serif" font-size="14.00" fill="#000000">If</text> +<polygon fill="none" stroke="#000000" points="169,-236 169,-268 246,-268 246,-236 169,-236"/> +<polygon fill="#ffff00" stroke="transparent" points="174,-241 174,-263 206,-263 206,-241 174,-241"/> +<polygon fill="none" stroke="#000000" points="174,-241 174,-263 206,-263 206,-241 174,-241"/> +<text text-anchor="start" x="176.7861" y="-247.4" font-family="Times,serif" font-size="14.00" fill="#000000">True</text> +<polygon fill="#ffff00" stroke="transparent" points="206,-241 206,-263 241,-263 241,-241 206,-241"/> +<polygon fill="none" stroke="#000000" points="206,-241 206,-263 241,-263 241,-241 206,-241"/> +<text text-anchor="start" x="208.7265" y="-247.4" font-family="Times,serif" font-size="14.00" fill="#000000">False</text> +</g> +<!-- If10->Start2 --> +<g id="edge4" class="edge"> +<title>If10->Start2:p0</title> +<path fill="none" stroke="#ff0000" d="M177.9557,-298.2089C157.4684,-324.8446 133.0529,-364.3668 129.4523,-404.9472"/> +<polygon fill="#ff0000" stroke="#ff0000" points="125.9531,-404.8528 129,-415 132.946,-405.1674 125.9531,-404.8528"/> +<text text-anchor="middle" x="175.7321" y="-300.6089" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- If10->EQ9 --> +<g id="edge5" class="edge"> +<title>If10->EQ9</title> +<path fill="none" stroke="#000000" d="M207,-298.3877C207,-306.7839 207,-315.7123 207,-323.8253"/> +<polygon fill="#000000" stroke="#000000" points="203.5001,-323.9075 207,-333.9075 210.5001,-323.9075 203.5001,-323.9075"/> +<text text-anchor="middle" x="204.7764" y="-300.7877" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +<!-- Con_14 --> +<g id="node6" class="node"> +<title>Con_14</title> +<ellipse fill="none" stroke="#000000" cx="43" cy="-265" rx="27" ry="18"/> +<text text-anchor="middle" x="43" y="-260.8" font-family="Times,serif" font-size="14.00" fill="#000000">2</text> +</g> +<!-- Con_16 --> +<g id="node7" class="node"> +<title>Con_16</title> +<ellipse fill="none" stroke="#000000" cx="115" cy="-265" rx="27" ry="18"/> +<text text-anchor="middle" x="115" y="-260.8" font-family="Times,serif" font-size="14.00" fill="#000000">1</text> +</g> +<!-- Region17 --> +<g id="node8" class="node"> +<title>Region17</title> +<polygon fill="#ffff00" stroke="#000000" points="217.4435,-196 160.5565,-196 160.5565,-160 217.4435,-160 217.4435,-196"/> +<text text-anchor="middle" x="189" y="-173.8" font-family="Times,serif" font-size="14.00" fill="#000000">Region</text> +</g> +<!-- Region17->If10 --> +<g id="edge6" class="edge"> +<title>Region17->If10:p0</title> +<path fill="none" stroke="#ff0000" d="M189.4415,-196.1943C189.6508,-206.0242 189.874,-218.6285 189.9616,-230.8706"/> +<polygon fill="#ff0000" stroke="#ff0000" points="186.462,-231.0134 190,-241 193.4619,-230.9868 186.462,-231.0134"/> +<text text-anchor="middle" x="187.2179" y="-198.5943" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +<!-- Region17->If10 --> +<g id="edge7" class="edge"> +<title>Region17->If10:p1</title> +<path fill="none" stroke="#ff0000" d="M205.4751,-196.1305C212.7091,-205.5926 220.1774,-217.8998 222.9129,-230.93"/> +<polygon fill="#ff0000" stroke="#ff0000" points="219.4469,-231.4334 224,-241 226.4064,-230.6821 219.4469,-231.4334"/> +<text text-anchor="middle" x="203.2515" y="-198.5305" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">2</text> +</g> +<!-- Phi_b18 --> +<g id="node9" class="node"> +<title>Phi_b18</title> +<ellipse fill="#ffffe0" stroke="#000000" cx="115" cy="-178" rx="27" ry="18"/> +<text text-anchor="middle" x="115" y="-173.8" font-family="Times,serif" font-size="14.00" fill="#000000">φ_b</text> +</g> +<!-- Phi_b18->Con_14 --> +<g id="edge9" class="edge"> +<title>Phi_b18->Con_14</title> +<path fill="none" stroke="#000000" d="M101.7941,-193.9571C90.8328,-207.202 75.0821,-226.2341 62.6416,-241.2664"/> +<polygon fill="#000000" stroke="#000000" points="59.8015,-239.2086 56.1222,-249.144 65.1943,-243.6716 59.8015,-239.2086"/> +<text text-anchor="middle" x="99.5705" y="-196.3571" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +<!-- Phi_b18->Con_16 --> +<g id="edge10" class="edge"> +<title>Phi_b18->Con_16</title> +<path fill="none" stroke="#000000" d="M115,-196.0265C115,-207.8082 115,-223.4393 115,-236.8419"/> +<polygon fill="#000000" stroke="#000000" points="111.5001,-236.9966 115,-246.9966 118.5001,-236.9967 111.5001,-236.9966"/> +<text text-anchor="middle" x="112.7764" y="-198.4265" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">2</text> +</g> +<!-- Phi_b18->Region17 --> +<g id="edge8" class="edge"> +<title>Phi_b18->Region17</title> +<path fill="none" stroke="#000000" stroke-dasharray="1,5" d="M142.1719,-178C144.9348,-178 147.6977,-178 150.4605,-178"/> +<polygon fill="#000000" stroke="#000000" points="150.4641,-181.5001 160.4641,-178 150.4641,-174.5001 150.4641,-181.5001"/> +<text text-anchor="middle" x="144.3955" y="-170.8" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Return20->Region17 --> +<g id="edge11" class="edge"> +<title>Return20->Region17</title> +<path fill="none" stroke="#ff0000" d="M161.3367,-124.1686C165.4243,-132.1229 170.3104,-141.631 174.8309,-150.4277"/> +<polygon fill="#ff0000" stroke="#ff0000" points="171.8539,-152.2922 179.5376,-159.5867 178.0799,-149.0926 171.8539,-152.2922"/> +<text text-anchor="middle" x="159.1131" y="-126.5686" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Return20->Phi_b18 --> +<g id="edge12" class="edge"> +<title>Return20->Phi_b18</title> +<path fill="none" stroke="#000000" d="M142.6633,-124.1686C138.4051,-132.4549 133.2804,-142.4273 128.6051,-151.5252"/> +<polygon fill="#000000" stroke="#000000" points="125.4085,-150.0882 123.9508,-160.5823 131.6345,-153.2877 125.4085,-150.0882"/> +<text text-anchor="middle" x="140.4397" y="-126.5686" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +</g> +</svg>
\ No newline at end of file diff --git a/docs/chapter05/Makefile b/docs/chapter05/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter05/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/docs/chapter05/README.md b/docs/chapter05/README.md new file mode 100644 index 00000000..82baca33 --- /dev/null +++ b/docs/chapter05/README.md @@ -0,0 +1,376 @@ +# Chapter 5: If Statement, Phi, and Region + +# Table of Contents + +1. [Recap](#recap) +2. [New Nodes](#new-nodes) +3. [`IfNode`](#ifnode) +4. [`PhiNode` ](#phinode) +5. [`RegionNode`](#regionnode) +6. [Pinned data nodes](#we-do-not-associate-a-control-edge-on-every-data-node-in-the-graph) +7. [`Stop` Nodes](#stop-nodes) +8. [Parsing an `if` Statement](#parsing-an-if-statement) +9. [Operations on ScopeNodes](#operations-on-scopenodes) +10. [Duplicating a ScopeNode](#duplicating-a-scopenode) +11. [Merging two ScopeNodes](#merging-two-scopenodes) +12. [Example 1](#example-1) +13. [Before Merging](#before-merging) +14. [After Merging](#after-merging) +15. [Finally](#finally) +16. [Example 2](#example-2) +17. [Example 3](#example-3) +18. [Example 3](#example-3) +19. [More Examples](#more-examples) + + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter05) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter04...linear-chapter05) it to the previous chapter. + +In this chapter we extend the language grammar with the following features: + +* We introduce the `if` statement. +* To support splitting of control flow and merging, we introduce new nodes: `Region` and `Phi`. +* Since we can now have multiple return points, we also introduce the `Stop` node as the termination. + +Here is the [complete language grammar](05-grammar.md) for this chapter. + +## Recap + +Here is a recap of the nodes introduced in previous chapters: + +| Node Name | Type | Chapter | Description | Inputs | Value | +|-----------|----------------|---------|------------------------------------------------|-------------------------------------------------------------------------------|----------------------------------------------------------------------------| +| Multi | Abstract class | 4 | A node that has a tuple result | | A tuple | +| Start | Control | 1 | Start of function, now a MultiNode | | A tuple with a ctrl token and an `arg` data node | +| Proj | Data | 4 | Projection nodes extract values from MultiNode | A MultiNode and index | Result is the extracted value from the input MultiNode at offset index | +| Bool | Data | 4 | Represents results of a comparison operator | Two data nodes | Result is a comparison, represented as integer value where 1=true, 0=false | +| Not | Data | 4 | Logical not | One data node | Result converts 0 to 1 and vice versa | +| Return | Control | 1 | End of function | Predecessor control node and a data node for the return value of the function | Return value of the function | +| Constant | Data | 1 | Represents constants such as integer literals | None, however Start node is set as input to enable graph walking | Value of the constant | +| Add | Data | 2 | Add two values | Two data nodes without restrictions on the order | Result of the add operation | +| Sub | Data | 2 | Subtract a value from another | Two data nodes, the first one is subtracted by the second one | Result of the subtraction | +| Mul | Data | 2 | Multiply two values | Two data nodes without restrictions on the order | Result of the multiplication | +| Div | Data | 2 | Divide a value by another | Two data nodes, the first one is divided by the second one | Result of the division | +| Minus | Data | 2 | Negate a value | One data node which value is negated | Result of the negation | +| Scope | Symbol Table | 3 | Represents scopes in the graph | Nodes that represent the current value of variables | None | + +## New Nodes + +The following new nodes are introduced in this chapter: + +| Node Name | Type | Chapter | Description | Inputs | Value | +|-----------|---------|---------|----------------------------------------------------|------------------------------------------------|----------------------------------------------------| +| If | Control | 5 | A branching test, sub type of `MultiNode` | A control node and a data predicate node | A tuple of two values: one for true, one for false | +| Region | Control | 5 | A merge point for multiple control flows | An input for each control flow that is merging | Merged control | +| Phi | Data | 5 | A phi function picks a value based on control flow | A Region, and data nodes for each control path | Depends on control flow path taken | +| Stop | Control | 5 | Termination of the program | All return nodes of the function | None | + +#### `IfNode` + +`If` node takes in both control and data (predicate expression) and routes the +control token to one of the two control flows, represented by true and false +`Proj` nodes. + +#### `PhiNode` + +A `Phi` reads in both data and control, and outputs a data value. The control +input to the `Phi` points to a `Region` node. The data inputs to the `Phi` are +one for each of the control inputs to that `Region`. The result computed by a +`Phi` depends both on the data and the matching control input. At most one +control input to the `Region` can be active at a time, and the `Phi` passes +through the data value from the matching input.[^1] + +#### `RegionNode` + +In this Sea of Nodes, there is an embedded Control Flow Graph - and like a +normal CFG there are merge points where two basic blocks flow into one. The +`Region` node takes control from each predecessor control (block) as input and +produces a merged control as an output.[^2] + +Both `Return` and `If` take control in slot 0. `PhiNode`s need their +corresponding `RegionNode` to know when to merge data values, so again slot 0 +is set, and data values show up in slots 1 and onward. `RegionNode`s keep +their control inputs in sync with `PhiNode`s, so again their control inputs show up +in slots 1 and onward. + +#### We do not associate a control edge on every data node in the graph + +If we want to track the basic block a normal instruction is in, we will set the +control input (always slot 0) to some control-producing Node. Typically we do +not need to (nor want to) track this - so control is `null` for most data ops. +The correctness of such a data op is solely determined by the remaining data +dependencies. It, and the Nodes that depend on it or on which it depends, +exists in a “sea” of Nodes, with little control structure. + +The “sea” of Nodes is useful for optimization, but does not represent any +traditional intermediate representation such as a CFG. We need a way to +serialize the graph and get back the control dependences. We do this with a +simple global code motion algorithm.[^3] + +#### `Stop` Nodes +`StopNode`s only have `ReturnNode` inputs. They mark the program termination. + + + +## Parsing an `if` Statement + +When we parse an `if` statement, the control flow splits at that point. We +must track the names being updated in each part of the `if` statement, and then +merge them at the end. The implementation follows the description in *Combining Analyses, Combining Optimizations*[^4]. + +This involves following: + +1. We create an `IfNode` with the current control token, i.e. the node mapped to + `$ctrl`, and the `if` predicate expression as inputs. +2. We add two `ProjNodes` - one for the `True` branch (call it `ifT`), and the + other for the `False` branch (call it `ifF`) - these extract values from the + tuple result of the `IfNode`. +3. We duplicate the current `ScopeNode`. The duplicated `ScopeNode` contains + all the same symbol tables as the original, and has the same edges. +4. We set the control token to the `True` projection node `ifT`, and parse the true + branch of the `if` statement. +5. We set the duplicated `ScopeNode` as the current one. +6. The control token is set to the `False` projection node `ifF`, and if there is an + `else` statement we parse it. +7. At this point we have two `ScopeNode`s; the original one, potentially updated + by the `True` branch, and the duplicate one, potentially updated by the + `False` branch. +8. We create a `Region` node to represent a merge point. +9. We *merge* the two `ScopeNode`s. We create `Phi` nodes for any names whose + bindings differ. The `Phi` nodes take the `Region` node as the control input + and the two data nodes from each of the `ScopeNode`s. The name binding is + updated to point to the `Phi` node. +10. Finally, we set the `Region` node as the control token, and discard the duplicated `ScopeNode`. + +Implementation is in [`parseIf` method in `Parser`](https://github.com/SeaOfNodes/Simple/blob/main/chapter05/src/main/java/com/seaofnodes/simple/Parser.java#L149-L185). + +## Operations on ScopeNodes + +As explained above, we duplicate ScopeNodes and merge them at a later point. There are some +subtleties in how this is implemented that is worth going over. + +### Duplicating a ScopeNode + +Below is the code for duplicating a ScopeNode. + +Our goals are: +1) Duplicate the name bindings across all stack levels +2) Make the new ScopeNode a user of all the bound nodes +3) Ensure that the order of defs in the duplicate is the same to allow easy merging + +For implementation [see `scopeNode.dup()`](https://github.com/SeaOfNodes/Simple/blob/main/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java#L142-L154) + +### Merging two ScopeNodes + +At the merge point we merge two ScopeNodes. The goals are: + +1) Merge names whose bindings have changed between the two nodes. For each such name, a Phi node is created, referencing the two original data nodes. +2) A new Region node is created representing the merged control flow. The phis have this region node as the first input. +3) After the merge is completed, the duplicate is discarded, and its use of each of the nodes is also deleted. + +The merging logic takes advantage of that fact that the two ScopeNodes have the bound nodes in the same order in the list of inputs. This was ensured during duplicating the ScopeNode. +Although only the innermost occurrence of a name can have its binding changed, we scan all the nodes in our input list, and simply ignore ones where the binding has not changed. + +For implementation [see `ScopeNode.mergeScopes()`](https://github.com/SeaOfNodes/Simple/blob/main/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java#L164-L173) + + +## Example #1 + +We show the graph for the following code snippet: +```java +int a = 1; +if (arg == 1) + a = arg+2; +else + a = arg-3; +return a; +``` + +### Before Merging + +Following shows the graph just before we merge the two branches of the `if` statement in a `Region` node. + + + +Note the two `ScopeNode`s in the graph. +One has its `$ctrl` pointing to the `True` projection, while the other has `$ctrl` pointing to `False` projection. +The variable `a` is bound to the `Add` node in the `True` branch, whereas it is bound to the `Sub` node in the `False` branch. +Thus `a` will need a `Phi` node when merging the two scopes. + +### After Merging + +Below is the graph after we created a `Region` node and merged the two definitions of `a` in a `Phi` node. + + + +The duplicate `ScopeNode` has been discarded and was merged into the other one. +Since `a` had two different definitions in both scopes a `Phi` node was created and is now referenced from `a`. +The `Phi` node's inputs are the `Region` node and the `Add` node from the `True` branch, and `Sub` node from the `False` branch. + +### Finally + +Here is the graph after the `return` statement was parsed and processed. + + + + + +## Example #2 + +Consider the following code snippet: +```java +int b = 0; +int c = 0; +if (arg == 1) { + b = 2; + c = 1; +} +else { + b = 1; +} +return b; +``` + +The value of `b` depends on which path the control flow took. +To resolve this, a Φ (Phi) function is inserted. + +``` +b = Phi(Region,2, 1); // values vary +c = Phi(Region,1, 0); // valuse vary, but dead +``` + +The `Phi` for `c` will die when the scope where `c` is defined dies. This does +not happen when merging but after the `return`. `return` is using `b` so `b` +stays alive. + +Before, we go ahead and parse down the if statement we duplicate the scope: +```java +ScopeNode fScope = _scope.dup(); +/* Scope[$ctrl:$ctrl, arg:arg][b:0, c:0]*/ +``` + +We then will proceed and parse down the first branch of the if statement: +```java +// Parse the true side +ctrl(ifT); // set ctrl token to ifTrue projection +parseStatement(); // Parse true-side +ScopeNode tScope = _scope; + +/* Scope[$ctrl:True, arg:arg][b:2, c:1]*/ +``` + +Notice, this branch modified and set a new value for both symbols currently existing in the symbol table. +Now, we set the scope back to where we started (without the modifications that `ifT` made) + +```java +_scope = fScope; +``` + +We then will proceed and parse down the second branch of the if statement: +```java +if (matchx("else")) { + parseStatement(); + fScope = _scope; + + /* Scope[$ctrl:False, arg:arg][b:1, c:0]*/ +} +``` + +This branch modified the values of `b` and `c`. Since the branch arms are also +lexical scopes, they cannot introduce new symbols in the current (outer) scope. +This means that the order of the name bindings stayed the same. Excluding the +first control node, we loop through and compare the nodes corresponding to the +same name binding to see if the nodes are different, if so we create a phi node +representing this conflict: + +```java + /* in(i); 2 */ + /* that.in(i); 1 */ + if( in(i) != that.in(i) ) // No need for redundant Phis + setDef(i, new PhiNode(ns[i], r, in(i), that.in(i)).peephole()); +``` + + + + + +## Example #3 + +Phi's implement a peephole illustrated in the example: + +```java +int a=arg==2; +if( arg==1 ) +{ + a=arg==3; +} +return a; +``` + +Pre-peephole we have: + + + +Post-peephole: + + + +The common operator was pulled out and the Phi node only got applied to the +operands. Notice how only the second operand of the `==` changes, the first +one stays the same (`arg`). The implementation is in +[`PhiNode.idealize()`](https://github.com/SeaOfNodes/Simple/blob/main/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java#L31-L71) + + +## More examples +```java +int c = 3; +int b = 2; +if (arg == 1) { + b = 3; + c = 4; +} +return c; +``` + + + +```java +int a=arg+1; +int b=arg+2; +if( arg==1 ) + b=b+a; +else + a=b+1; +return a+b; +``` + + + +```java +int a=1; +if( arg==1 ) + if( arg==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +``` + + + + + +[^1]: Click, C. (1995). + Combining Analyses, Combining Optimizations, 132. + +[^2]: Click, C. (1995). + Combining Analyses, Combining Optimizations, 129. + +[^3]: Click, C. (1995). + Combining Analyses, Combining Optimizations, 86. + +[^4]: Click, C. (1995). + Combining Analyses, Combining Optimizations, 102-103. diff --git a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index 62b434f3..c35a4e32 100644 --- a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -17,7 +17,7 @@ public class GraphVisualizer { // nodes in the graph. Collection<Node> all = findAll(parser); StringBuilder sb = new StringBuilder(); - sb.append("digraph chapter04 {\n"); + sb.append("digraph chapter05 {\n"); sb.append("/*\n"); sb.append(parser.src()); sb.append("\n*/\n"); @@ -40,13 +40,15 @@ public class GraphVisualizer { nodes(sb, all); // Now the scopes, in a cluster no edges - scopes(sb, parser._scope); + for (ScopeNode sn: parser._xScopes) + scopes(sb, sn); // Walk the Node edges nodeEdges(sb, all); // Walk the Scope edges - scopeEdges(sb, parser._scope); + for (ScopeNode sn: parser._xScopes) + scopeEdges(sb, sn); sb.append("}\n"); return sb.toString(); @@ -94,10 +96,25 @@ public class GraphVisualizer { // other nodes are ellipses, i.e. default shape if( n.isCFG() ) sb.append("shape=box style=filled fillcolor=yellow "); + if( n instanceof PhiNode ) + sb.append("style=filled fillcolor=lightyellow "); sb.append("label=\"").append(lab).append("\" "); } sb.append("];\n"); } + + // Force Region & Phis to line up + for( Node n : all ) { + if( n instanceof RegionNode region ) { + sb.append("\t\t{ rank=same; "); + sb.append(region).append(";") ; + for( Node phi : region._outputs ) + if( phi instanceof PhiNode ) + sb.append(phi.uniqueName()).append(";"); + sb.append("}\n"); + } + } + sb.append("\t}\n"); // End Node cluster } @@ -138,7 +155,13 @@ public class GraphVisualizer { continue; int i=0; for( Node def : n._inputs ) { - if( def != null ) { + if( n instanceof PhiNode && def instanceof RegionNode ) { + // Draw a dotted use->def edge from Phi to Region. + sb.append('\t').append(n.uniqueName()); + sb.append(" -> "); + sb.append(def.uniqueName()); + sb.append(" [style=dotted taillabel=").append(i).append("];\n"); + } else if( def != null ) { // Most edges land here use->def sb.append('\t').append(n.uniqueName()).append(" -> "); if( def instanceof ProjNode proj ) { diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index ff2c0504..80674d59 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -14,7 +14,6 @@ import java.util.*; */ public class Parser { - /** * A Global Static, unique to each compilation. This is a public, so we * can make constants everywhere without having to thread the StartNode @@ -24,12 +23,22 @@ public class Parser { */ public static StartNode START; + public StopNode STOP; + // The Lexer. Thin wrapper over a byte[] buffer with a cursor. private final Lexer _lexer; /** - * A ScopeNode contains a stack of lexical scopes, each scope is a symbol table that binds + * Current ScopeNode - ScopeNodes change as we parse code, but at any point of time + * there is one current ScopeNode. The reason the current ScopeNode can change is to do with how + * we handle branching. See {@link #parseIf()}. + * <p> + * Each ScopeNode contains a stack of lexical scopes, each scope is a symbol table that binds * variable names to Nodes. The top of this stack represents current scope. + * <p> + * We keep a list of all ScopeNodes so that we can show them in graphs. + * @see #parseIf() + * @see #_xScopes */ public ScopeNode _scope; @@ -37,17 +46,27 @@ public class Parser { * List of keywords disallowed as identifiers */ private final HashSet<String> KEYWORDS = new HashSet<>(){{ + add("else"); + add("false"); + add("if"); add("int"); add("return"); + add("true"); }}; + /** + * We clone ScopeNodes when control flows branch; it is useful to have + * a list of all active ScopeNodes for purposes of visualization of the SoN graph + */ + public final Stack<ScopeNode> _xScopes = new Stack<>(); + public Parser(String source, TypeInteger arg) { Node.reset(); _lexer = new Lexer(source); _scope = new ScopeNode(); START = new StartNode(new Type[]{ Type.CONTROL, arg }); - START.peephole(); + STOP = new StopNode(); } public Parser(String source) { @@ -66,19 +85,23 @@ public class Parser { private Node ctrl(Node n) { return _scope.ctrl(n); } - public ReturnNode parse() { return parse(false); } - public ReturnNode parse(boolean show) { + public StopNode parse() { return parse(false); } + public StopNode parse(boolean show) { + _xScopes.push(_scope); // Enter a new scope for the initial control and arguments _scope.push(); _scope.define(ScopeNode.CTRL, new ProjNode(START, 0, ScopeNode.CTRL).peephole()); _scope.define(ScopeNode.ARG0, new ProjNode(START, 1, ScopeNode.ARG0).peephole()); - var ret = (ReturnNode) parseBlock(); + parseBlock(); _scope.pop(); + _xScopes.pop(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); + STOP.peephole(); if( show ) showGraph(); - return ret; + return STOP; } + /** * Parses a block * @@ -91,21 +114,18 @@ public class Parser { private Node parseBlock() { // Enter a new scope _scope.push(); - Node n = null; - while (!peek('}') && !_lexer.isEOF()) { - Node n0 = parseStatement(); - if (n0 != null) n = n0; // Allow null returns from eg showGraph - }; + while (!peek('}') && !_lexer.isEOF()) + parseStatement(); // Exit scope _scope.pop(); - return n; + return null; } /** * Parses a statement * * <pre> - * returnStatement | declStatement | blockStatement | expressionStatement + * returnStatement | declStatement | blockStatement | ifStatement | expressionStatement * </pre> * @return a {@link Node} or {@code null} */ @@ -113,12 +133,60 @@ public class Parser { if (matchx("return") ) return parseReturn(); else if (matchx("int")) return parseDecl(); else if (match ("{" )) return require(parseBlock(),"}"); + else if (matchx("if" )) return parseIf(); else if (matchx("#showGraph")) return require(showGraph(),";"); else if (matchx(";")) return null; // Empty statement else return parseExpressionStatement(); } /** + * Parses a statement + * + * <pre> + * if ( expression ) statement [else statement] + * </pre> + * @return a {@link Node}, never {@code null} + */ + private Node parseIf() { + require("("); + // Parse predicate + var pred = require(parseExpression(), ")"); + // IfNode takes current control and predicate + IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).<IfNode>keep().peephole(); + // Setup projection nodes + Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); + Node ifF = new ProjNode(ifNode, 1, "False").peephole(); + // In if true branch, the ifT proj node becomes the ctrl + // But first clone the scope and set it as current + int ndefs = _scope.nIns(); + ScopeNode fScope = _scope.dup(); // Duplicate current scope + _xScopes.push(fScope); // For graph visualization we need all scopes + + // Parse the true side + ctrl(ifT); // set ctrl token to ifTrue projection + parseStatement(); // Parse true-side + ScopeNode tScope = _scope; + + // Parse the false side + _scope = fScope; // Restore scope, then parse else block if any + ctrl(ifF); // Ctrl token is now set to ifFalse projection + if (matchx("else")) { + parseStatement(); + fScope = _scope; + } + + if( tScope.nIns() != ndefs || fScope.nIns() != ndefs ) + throw error("Cannot define a new name on one arm of an if"); + + // Merge results + _scope = tScope; + _xScopes.pop(); // Discard pushed from graph display + + return ctrl(tScope.mergeScopes(fScope)); + } + + + /** * Parses a return statement; "return" already parsed. * The $ctrl edge is killed. * @@ -129,7 +197,7 @@ public class Parser { */ private Node parseReturn() { var expr = require(parseExpression(), ";"); - Node ret = new ReturnNode(ctrl(), expr).peephole(); + Node ret = STOP.addReturn(new ReturnNode(ctrl(), expr).peephole()); ctrl(null); // Kill control return ret; } @@ -254,13 +322,15 @@ public class Parser { * Parse a primary expression: * * <pre> - * primaryExpr : integerLiteral | Identifier | '(' expression ')' + * primaryExpr : integerLiteral | Identifier | true | false | '(' expression ')' * </pre> * @return a primary {@link Node}, never {@code null} */ private Node parsePrimary() { if( _lexer.isNumber() ) return parseIntegerLiteral(); if( match("(") ) return require(parseExpression(), ")"); + if( matchx("true" ) ) return new ConstantNode(TypeInteger.constant(1)).peephole(); + if( matchx("false") ) return new ConstantNode(TypeInteger.constant(0)).peephole(); String name = _lexer.matchId(); if( name == null) throw errorSyntax("an identifier or expression"); Node n = _scope.lookup(name); diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 5720aca4..081c9276 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -72,6 +72,24 @@ public class AddNode extends Node { if( lhs.in(2)._type.isConstant() && t2.isConstant() ) return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole()); + if( lhs.in(2) instanceof PhiNode phi && phi.allCons() && + // Do we have ((x + (phi cons)) + con) ? + // Do we have ((x + (phi cons)) + (phi cons)) ? + // Push constant up through the phi: x + (phi con0+con0 con1+con1...) + + // Note that this is the exact reverse of Phi pulling a common op + // down to reduce total op-count. We don't get in an endless push- + // up push-down peephole cycle because the constants all fold first. + (t2.isConstant() || (rhs instanceof PhiNode && phi.in(0) == rhs.in(0) && rhs.allCons()) ) ) { + Node[] ns = new Node[phi.nIns()]; + ns[0] = phi.in(0); + // Push constant up through the phi: x + (phi con0+con0 con1+con1...) + for( int i=1; i<ns.length; i++ ) + ns[i] = new AddNode(phi.in(i),t2.isConstant() ? rhs : rhs.in(i)).peephole(); + String label = phi._label + (rhs instanceof PhiNode rphi ? rphi._label : ""); + return new AddNode(lhs.in(1),new PhiNode(label,ns).peephole()); + } + // Now we sort along the spline via rotates, to gather similar things together. // Do we rotate (x + y) + z @@ -84,15 +102,22 @@ public class AddNode extends Node { // Compare two off-spline nodes and decide what order they should be in. // Do we rotate ((x + hi) + lo) into ((x + lo) + hi) ? - // Generally constants always go right, then others. + // Generally constants always go right, then Phi-of-constants, then muls, then others. // Ties with in a category sort by node ID. // TRUE if swapping hi and lo. static boolean spline_cmp( Node hi, Node lo ) { if( lo._type.isConstant() ) return false; if( hi._type.isConstant() ) return true ; + if( lo instanceof PhiNode && lo.allCons() ) return false; + if( hi instanceof PhiNode && hi.allCons() ) return true ; + + if( lo instanceof PhiNode && !(hi instanceof PhiNode) ) return true; + if( hi instanceof PhiNode && !(lo instanceof PhiNode) ) return false; + // Same category of "others" return lo._nid > hi._nid; } + @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 05495790..7a4a087e 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -46,7 +46,7 @@ abstract public class BoolNode extends Node { return null; } - public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } } - public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs < rhs; } } - public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } } + public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } Node copy(Node lhs, Node rhs) { return new EQ(lhs,rhs); } } + public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs < rhs; } Node copy(Node lhs, Node rhs) { return new LT(lhs,rhs); } } + public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } Node copy(Node lhs, Node rhs) { return new LE(lhs,rhs); } } } diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java index 3b3a4436..519a8c8a 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -37,4 +37,6 @@ public class DivNode extends Node { return in(1); return null; } + + @Override Node copy(Node lhs, Node rhs) { return new DivNode(lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java new file mode 100644 index 00000000..6124b893 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -0,0 +1,36 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.type.TypeTuple; + +public class IfNode extends MultiNode { + + public IfNode(Node ctrl, Node pred) { + super(ctrl, pred); + } + + @Override + public String label() { return "If"; } + + @Override + StringBuilder _print1(StringBuilder sb) { + sb.append("if( "); + return in(1)._print0(sb).append(" )"); + } + + @Override public boolean isCFG() { return true; } + + public Node ctrl() { return in(0); } + public Node pred() { return in(1); } + + @Override + public Type compute() { + return TypeTuple.IF; + } + + @Override + public Node idealize() { + return null; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index 36d5eb3e..2dbdd695 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -46,4 +46,5 @@ public class MulNode extends Node { return null; } + @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 9fa0a95a..5412108b 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -349,6 +349,20 @@ public abstract class Node { return this; } + // does this node contain all constants? + // Ignores in(0), as is usually control. + boolean allCons() { + for( int i=1; i<nIns(); i++ ) + if( !(in(i)._type.isConstant()) ) + return false; + return true; + } + + // Make a shallow copy (same class) of this Node, with given inputs and + // empty outputs and a new Node ID. The original inputs are ignored. + // Does not need to be implemented in isCFG() nodes. + Node copy(Node lhs, Node rhs) { throw Utils.TODO("Binary ops need to implement copy"); } + /** * 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. diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java new file mode 100644 index 00000000..374e1183 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -0,0 +1,73 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; + +public class PhiNode extends Node { + + final String _label; + + public PhiNode(String label, Node... inputs) { super(inputs); _label = label; } + + @Override public String label() { return "Phi_"+_label; } + + @Override public String glabel() { return "φ_"+_label; } + + @Override + StringBuilder _print1(StringBuilder sb) { + sb.append("Phi("); + for( Node in : _inputs ) + in._print0(sb).append(","); + sb.setLength(sb.length()-1); + sb.append(")"); + return sb; + } + + Node region() { return in(0); } + + @Override + public Type compute() { + return Type.BOTTOM; + } + + @Override + public Node idealize() { + // Remove a "junk" Phi: Phi(x,x) is just x + if( same_inputs() ) + return in(1); + + // Pull "down" a common data op. One less op in the world. One more + // Phi, but Phis do not make code. + // Phi(op(A,B),op(Q,R),op(X,Y)) becomes + // op(Phi(A,Q,X), Phi(B,R,Y)). + Node op = in(1); + if( op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op() ) { + Node[] lhss = new Node[nIns()]; + Node[] rhss = new Node[nIns()]; + lhss[0] = rhss[0] = in(0); // Set Region + for( int i=1; i<nIns(); i++ ) { + lhss[i] = in(i).in(1); + rhss[i] = in(i).in(2); + } + Node phi_lhs = new PhiNode(_label,lhss).peephole(); + Node phi_rhs = new PhiNode(_label,rhss).peephole(); + return op.copy(phi_lhs,phi_rhs); + } + + return null; + } + + private boolean same_op() { + for( int i=2; i<nIns(); i++ ) + if( in(1).getClass() != in(i).getClass() ) + return false; + return true; + } + + private boolean same_inputs() { + for( int i=2; i<nIns(); i++ ) + if( in(1) != in(i) ) + return false; + return true; + } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 2f49fe91..2826d192 100644 --- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -23,7 +23,7 @@ public class ProjNode extends Node { @Override StringBuilder _print1(StringBuilder sb) { return sb.append(_label); } - @Override public boolean isCFG() { return _idx==0; } + @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; } public MultiNode ctrl() { return (MultiNode)in(0); } diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java new file mode 100644 index 00000000..5d520d65 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -0,0 +1,27 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; + +public class RegionNode extends Node { + public RegionNode(Node... inputs) { super(inputs); } + + @Override + public String label() { return "Region"; } + + @Override + StringBuilder _print1(StringBuilder sb) { + return sb.append(label()).append(_nid); + } + + @Override public boolean isCFG() { return true; } + + @Override + public Type compute() { + return Type.CONTROL; + } + + @Override + public Node idealize() { + return null; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 8ffeac64..32045fbc 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -131,4 +131,45 @@ public class ScopeNode extends Node { */ public Node ctrl(Node n) { return setDef(0,n); } + /** + * Duplicate a ScopeNode; including all levels, up to Nodes. So this is + * neither shallow (would dup the Scope but not the internal HashMap + * tables), nor deep (would dup the Scope, the HashMap tables, but then + * also the program Nodes). + * <p> + * The new Scope is a full-fledged Node with proper use<->def edges. + */ + public ScopeNode dup() { + ScopeNode dup = new ScopeNode(); + // Our goals are: + // 1) duplicate the name bindings of the ScopeNode across all stack levels + // 2) Make the new ScopeNode a user of all the nodes bound + // 3) Ensure that the order of defs is the same to allow easy merging + for( HashMap<String,Integer> syms : _scopes ) + dup._scopes.push(new HashMap<>(syms)); + dup.addDef(ctrl()); // Control input is just copied + for( int i=1; i<nIns(); i++ ) + dup.addDef(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 + * innermost stack level where the name is bound. + * + * @param that The ScopeNode to be merged into this + * @return A new node representing the merge point + */ + public Node mergeScopes(ScopeNode that) { + RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).peephole()); + 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 + setDef(i, new PhiNode(ns[i], r, in(i), that.in(i)).peephole()); + that.kill(); // Kill merged scope + return r; + } + } diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java new file mode 100644 index 00000000..a30256f9 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -0,0 +1,46 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; + +public class StopNode extends Node { + public StopNode(Node... inputs) { + super(inputs); + } + + @Override + public String label() { + return "Stop"; + } + + @Override + StringBuilder _print1(StringBuilder sb) { + if( ret()!=null ) return ret()._print0(sb); + sb.append("Stop[ "); + for( Node ret : _inputs ) + ret._print0(sb).append(" "); + return sb.append("]"); + } + + @Override public boolean isCFG() { return true; } + + // If a single Return, return it. + // Otherwise, null because ambiguous. + public ReturnNode ret() { + return nIns()==1 ? (ReturnNode)in(0) : null; + } + + @Override + public Type compute() { + return Type.BOTTOM; + } + + @Override + public Node idealize() { + return null; + } + + public Node addReturn(Node node) { + return addDef(node); + } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index 58d757ea..475b3790 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -37,4 +37,5 @@ public class SubNode extends Node { return null; } + @Override Node copy(Node lhs, Node rhs) { return new SubNode(lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index 1687f65a..d0916312 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -43,7 +43,7 @@ public class Type { public StringBuilder _print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;} - public Type meet(Type other) { return Type.BOTTOM; } + public Type meet(Type other) { return BOTTOM; } @Override public final String toString() { diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index 25663dda..33417eb2 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -16,11 +16,13 @@ public class TypeTuple extends Type { @Override public StringBuilder _print(StringBuilder sb) { - sb.append("[ "); + sb.append("["); for( Type t : _types ) t._print(sb).append(","); sb.setLength(sb.length()-1); sb.append("]"); return sb; } + + public static final TypeTuple IF = new TypeTuple(new Type[]{Type.CONTROL,Type.CONTROL}); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/src/test/java/com/seaofnodes/simple/Chapter01Test.java index 3d568337..547c36f8 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -11,8 +11,9 @@ public class Chapter01Test { @Test public void testSimpleProgram() { Parser parser = new Parser("return 1;"); - ReturnNode ret = parser.parse(); + StopNode stop = parser.parse(); StartNode start = Parser.START; + ReturnNode ret = (ReturnNode)stop.in(0); assertTrue(ret.ctrl() instanceof ProjNode); Node expr = ret.expr(); diff --git a/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/src/test/java/com/seaofnodes/simple/Chapter02Test.java index 60ee8874..4085ed7e 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter02Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -12,7 +12,7 @@ public class Chapter02Test { public void testParseGrammar() { Parser parser = new Parser("return 1+2*3+-5;"); Node._disablePeephole = true; // disable peephole so we can observe full graph - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (1+((2*3)+(-5)));", ret.print()); GraphVisualizer gv = new GraphVisualizer(); System.out.println(gv.generateDotOutput(parser)); @@ -22,42 +22,42 @@ public class Chapter02Test { @Test public void testAddPeephole() { Parser parser = new Parser("return 1+2;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 3;", ret.print()); } @Test public void testSubPeephole() { Parser parser = new Parser("return 1-2;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return -1;", ret.print()); } @Test public void testMulPeephole() { Parser parser = new Parser("return 2*3;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 6;", ret.print()); } @Test public void testDivPeephole() { Parser parser = new Parser("return 6/3;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 2;", ret.print()); } @Test public void testMinusPeephole() { Parser parser = new Parser("return 6/-3;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return -2;", ret.print()); } @Test public void testExample() { Parser parser = new Parser("return 1+2*3+-5;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 2;", ret.print()); GraphVisualizer gv = new GraphVisualizer(); System.out.println(gv.generateDotOutput(parser)); diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java index fc8e97b6..adbfba84 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -11,21 +11,21 @@ public class Chapter03Test { @Test public void testVarDecl() { Parser parser = new Parser("int a=1; return a;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 1;", ret.print()); } @Test public void testVarAdd() { Parser parser = new Parser("int a=1; int b=2; return a+b;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 3;", ret.print()); } @Test public void testVarScope() { Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 4;", ret.print()); } @@ -33,7 +33,7 @@ public class Chapter03Test { public void testVarScopeNoPeephole() { Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;"); Node._disablePeephole = true; - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); Node._disablePeephole = false; assertEquals("return (1+3);", ret.print()); } @@ -41,7 +41,7 @@ public class Chapter03Test { @Test public void testVarDist() { Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 8;", ret.print()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/src/test/java/com/seaofnodes/simple/Chapter04Test.java index faae0aee..55c0b15f 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -11,49 +11,50 @@ public class Chapter04Test { @Test public void testPeephole() { Parser parser = new Parser("return 1+arg+2; #showGraph;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (arg+3);", ret.print()); } @Test public void testPeephole2() { Parser parser = new Parser("return (1+arg)+2;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (arg+3);", ret.print()); } @Test public void testAdd0() { Parser parser = new Parser("return 0+arg;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return arg;", ret.print()); } @Test public void testAddAddMul() { Parser parser = new Parser("return arg+0+arg;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (arg*2);", ret.print()); } @Test public void testPeephole3() { Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return ((arg*2)+6);", ret.print()); } @Test public void testMul1() { Parser parser = new Parser("return 1*arg;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return arg;", ret.print()); } @Test public void testVarArg() { - Parser parser = new Parser("return arg; #showGraph;", TypeInteger.BOT); - ReturnNode ret = parser.parse(); + Parser parser = new Parser("return arg; #showGraph;"); + StopNode stop = parser.parse(); + ReturnNode ret = stop.ret(); assertTrue(ret.in(0) instanceof ProjNode); assertTrue(ret.in(1) instanceof ProjNode); } @@ -61,49 +62,49 @@ public class Chapter04Test { @Test public void testConstantArg() { Parser parser = new Parser("return arg; #showGraph;", TypeInteger.constant(2)); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 2;", ret.print()); } @Test public void testCompEq() { Parser parser = new Parser("return 3==3; #showGraph;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 1;", ret.print()); } @Test public void testCompEq2() { Parser parser = new Parser("return 3==4; #showGraph;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 0;", ret.print()); } @Test public void testCompNEq() { Parser parser = new Parser("return 3!=3; #showGraph;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 0;", ret.print()); } @Test public void testCompNEq2() { Parser parser = new Parser("return 3!=4; #showGraph;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 1;", ret.print()); } @Test public void testBug1() { Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (arg+3);", ret.print()); } @Test public void testBug2() { Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (arg+1);", ret.print()); } @@ -120,14 +121,14 @@ public class Chapter04Test { @Test public void testBug4() { Parser parser = new Parser("return -arg;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (-arg);", ret.print()); } @Test public void testBug5() { Parser parser = new Parser("return arg--2;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (arg--2);", ret.print()); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java new file mode 100644 index 00000000..b5fcbeaf --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -0,0 +1,212 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter05Test { + + @Test + public void testIfStmt() { + Parser parser = new Parser( +""" +int a = 1; +if (arg == 1) + a = arg+2; +else { + a = arg-3; + #showGraph; +} +#showGraph; +return a;"""); + StopNode ret = parser.parse(true); + assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString()); + } + + @Test + public void testTest() { + Parser parser = new Parser( +""" +int c = 3; +int b = 2; +if (arg == 1) { + b = 3; + c = 4; +} +return c;""", TypeInteger.BOT); + StopNode ret = parser.parse(true); + assertEquals("return Phi(Region16,4,3);", ret.toString()); + } + + @Test + public void testReturn2() { + Parser parser = new Parser( +""" +if( arg==1 ) + return 3; +else + return 4; +#showGraph;""", TypeInteger.BOT); + StopNode stop = parser.parse(); + assertEquals("Stop[ return 3; return 4; ]", stop.toString()); + } + + @Test + public void testIfMergeB() { + Parser parser = new Parser( +""" +int a=arg+1; +int b=0; +if( arg==1 ) + b=a; +else + b=a+1; +return a+b;"""); + StopNode ret = parser.parse(true); + assertEquals("return ((arg*2)+Phi(Region20,2,3));", ret.toString()); + } + + @Test + public void testIfMerge2() { + Parser parser = new Parser( +""" +int a=arg+1; +int b=arg+2; +if( arg==1 ) + b=b+a; +else + a=b+1; +return a+b;"""); + StopNode ret = parser.parse(true); + assertEquals("return ((Phi(Region31,(arg*2),arg)+arg)+Phi(Region31,4,5));", ret.toString()); + } + + @Test + public void testMerge3() { + Parser parser = new Parser( +""" +int a=1; +if( arg==1 ) + if( arg==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +#showGraph;""", TypeInteger.BOT); + StopNode stop = parser.parse(); + assertEquals("return Phi(Region33,Phi(Region21,2,3),Phi(Region31,4,5));", stop.toString()); + } + + @Test + public void testMerge4() { + Parser parser = new Parser( +""" +int a=0; +int b=0; +if( arg ) + a=1; +if( arg==0 ) + b=2; +return arg+a+b; +#showGraph;""", TypeInteger.BOT); + StopNode stop = parser.parse(); + assertEquals("return ((arg+Phi(Region13,1,0))+Phi(Region22,2,0));", stop.toString()); + } + + @Test + public void testMerge5() { + Parser parser = new Parser( +""" +int a=arg==2; +if( arg==1 ) +{ + a=arg==3; +} +return a;"""); + StopNode ret = parser.parse(true); + assertEquals("return (arg==Phi(Region16,3,2));", ret.toString()); + } + + @Test + public void testTrue() { + StopNode stop = new Parser("return true;").parse(); + assertEquals("return 1;",stop.toString()); + } + + @Test + public void testHalfDef() { + try { + new Parser("if( arg==1 ) int b=2; return b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Cannot define a new name on one arm of an if",e.getMessage()); + } + } + + @Test + public void testHalfDef2() { + try { + new Parser("if( arg==1 ) { int b=2; } else { int b=3; } return b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'b'",e.getMessage()); + } + } + + @Test + public void testRegress1() { + 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 testBadNum() { + try { + new Parser("return 1-;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected an identifier or expression: ;",e.getMessage()); + } + } + + @Test + public void testKeyword1() { + try { + new Parser("int true=0; return true;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Expected an identifier, found 'true'",e.getMessage()); + } + } + + @Test + public void testKeyword2() { + try { + new Parser("int else=arg; if(else) else=2; else else=1; return else;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Expected an identifier, found 'else'",e.getMessage()); + } + } + + @Test + public void testKeyword3() { + try { + new Parser("int a=1; ififif(arg)inta=2;return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected =: (",e.getMessage()); + } + } + +} |
