From c3842e2a01522f52ae4690de3e9c90efa33f0f27 Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Sun, 3 Mar 2024 17:55:47 +0000 Subject: Chapter 9 (#66) * chapter9 * merge fixes to chapter8 * Ch 9 notes * Ch 9 work Add a Iterate phase, after parsing. Add a Worklist with fast dup removal & rand pull. Add a Node.iter() call which returns progress or null. Peephole calls it. Iter() also asserts that Types make monotonic progress. Intern all types, so we can do a cheap/easy "isa" test. * GVN * rename temporarily * Apply Cliff's worklist changes * Apply Cliff's GVN changes * Revert "GVN" This reverts commit 9dc6db1cac7e40de4a58333cbc3c9c3e7c088e6f. * Revert "Ch 9 work" This reverts commit df5b74e6c017a4f237a5d1a550a83b40a7928876. * Fix 3-1+2 Was computing as 3-(1+2) == 0, not 4 as expected. Add tests. Unlock in swap12. * Missed some cut-n-paste changes * Break up the test file per-chapter * Fix keep-alive while looping expressions Must "hook" LHS prior to calling peepholes * Ch9 Region optimization Bug fix, GVN hits 2 inProgress Loops Bug fix lifetime tracking when parsing dead code Bug fix debug find call GraphViz post-iterate * Readme overhaul Progress on Ch 9 readme * Fix bugs hashcode Was relying on label() hashCode for Phi, Proj; since this is debug-only cannot be relied on. Proj relies on _idx field, Phi needs a !inProgress check. * Constant nodes print "#" before con * Add a farther neighbor check Peeps that check more than the nearest neighbor register a dependency on the Node that failed them. Should that Node later change, the peep root is put back on the worklist and revisited. * Fix addDeps assert Unwind golden test print, print smarter. Unlock edges in subsume * Update README * shuffle adddeps forward one its needed again shortly in another test, so just cover it now * Fix fuzzer bugs Peep x+(-y) to x-y Handle TOP inputs; didn't think it could happen before running an optimistic pass, but fuzzer proved me wrong. Deleting an input can recursively delete the self-node. When checking the compute() type assert, delay setting _type so the method can just be re-run in the debugger. Missing addDep in Phi Parser mis-handling stacked operators like "1+-2" or "1==!=<=<>=>2" Make Work list deterministic between tests. * Update fuzzer to run iterate (#62) * Update fuzzer to run iterate * Work seed is now reset by reset * A few more fuzzer tests Set _type in iter() even later, better debugging. Handle dead active scopes in visiualizer. Region ideal honors Loop invariants; finish Region ideal for single input; inProgress check is a little tighter. Type.isConstant is true strictly for lattice centerline constants. Clean up TypeInteger. ideaj warning removal * Fix all fuzzer bugs iter() does not call peep(), instead peep() is self-recursive. This allows Iterate() to call iter(), and not get into arbitrary recursive peep() changes that do not track on the worklist. Div, Minus, If all monotonic. Catch a bunch of progress issues. Robustify IRPrinter and Iterate and Region ideal * Reducer could run into an infinite loop (#63) * Write up how the Evaluator works (#64) * Write up how the Evaluator works * Some small improvements and a slightly better wrap up. * Series of fuzzer bugs. Fix monotonicity for all data nodes. Generic compute intercept for data nodes, check all inputs for TOP/BOTTOM, and again for IntDataNodes. Fix general progress bug allow high Types as constants. Fix progress Region 1-input has obvious idom. Make shortcut for fuzzer; renames Fuzzer to not have "Test" in the class name. Fix invert comment in TypeInteger * All fuzzer tests pass Turn off expensive assert accidentally turned on CSE needs to join types. Add a type join. Missing dep in Phi * More README * Hacking alternative way to fix the type compute * Node is no longer IntSupplier Renamed Work to WorkList Renamed Iterate to IterOptim Renamed Node.iter() to Node.peepholeOpt() WorkList expects elements to be of Node * Add an example of GVN * Rename the method depsClear to moveDepsToWorklist - to better capture what it actually does. * Add a second example of GVN benefits * Fix typo * Add example of worklist opt * Prepare to allow alternative post parse worklist opt * Alternative WorkList opt that has following differences: 1. It does not require dependencies between nodes 2. It does not require calls from inside the Node class, and therefore runs totally independently as a post parse step. 3. It is simple * Alternative WorkList opt that has following differences: 1. It does not require dependencies between nodes 2. It does not require calls from inside the Node class, and therefore runs totally independently as a post parse step. 3. It is simple * The RPO list was incomplete as it only identified the subgraph accessible from the STOP node. * Fix iter count * Add test suggested by Xmilia * Fix bug where after the region is peeped the phis get consistent number of inputs * Fix bug where after the region is peeped the phis get consistent number of inputs * Dump out stats on how many nodes we peepd during the post parse iterative opt. * Make it easy to switch the IterOpt * Use deps based worklist by default * Sharper worklist add * Copy across Cliff's changes * Merge changes to Iterate * Revert failing change * Update readme * Add comments / update docs to explain the patterns where we call addDep(). * As before, unconditionally made dep a dependent of region. * Fix a lot of missing dep issues Rename IterOptim -> IterPeeps Some grammar changes in comments & readme * Bump up fuzzer limits, more testing Missing dep in idom calc in IfNode. Missed idom cache clear on Region edit. * Remove RPO based peeps O(n^2) behavior * Minor updates README * fix compile bug --------- Co-authored-by: Cliff Click Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Darrick Wiebe --- chapter09/docs/09-grammar.md | 98 ++++++++++++++++++ chapter09/docs/09-graph1.gv | 67 +++++++++++++ chapter09/docs/09-graph1.svg | 222 +++++++++++++++++++++++++++++++++++++++++ chapter09/docs/09-graph2.gv | 63 ++++++++++++ chapter09/docs/09-graph2.svg | 196 ++++++++++++++++++++++++++++++++++++ chapter09/docs/09-graph3.gv | 37 +++++++ chapter09/docs/09-graph3.svg | 109 ++++++++++++++++++++ chapter09/docs/09-graph4.gv | 29 ++++++ chapter09/docs/09-graph4.svg | 67 +++++++++++++ chapter09/docs/09-graph5.gv | 63 ++++++++++++ chapter09/docs/09-graph5.svg | 210 ++++++++++++++++++++++++++++++++++++++ chapter09/docs/09-graph6.gv | 60 +++++++++++ chapter09/docs/09-graph6.svg | 184 ++++++++++++++++++++++++++++++++++ chapter09/docs/build-graphs.sh | 6 ++ 14 files changed, 1411 insertions(+) create mode 100644 chapter09/docs/09-grammar.md create mode 100644 chapter09/docs/09-graph1.gv create mode 100644 chapter09/docs/09-graph1.svg create mode 100644 chapter09/docs/09-graph2.gv create mode 100644 chapter09/docs/09-graph2.svg create mode 100644 chapter09/docs/09-graph3.gv create mode 100644 chapter09/docs/09-graph3.svg create mode 100644 chapter09/docs/09-graph4.gv create mode 100644 chapter09/docs/09-graph4.svg create mode 100644 chapter09/docs/09-graph5.gv create mode 100644 chapter09/docs/09-graph5.svg create mode 100644 chapter09/docs/09-graph6.gv create mode 100644 chapter09/docs/09-graph6.svg create mode 100644 chapter09/docs/build-graphs.sh (limited to 'chapter09/docs') diff --git a/chapter09/docs/09-grammar.md b/chapter09/docs/09-grammar.md new file mode 100644 index 00000000..c603f335 --- /dev/null +++ b/chapter09/docs/09-grammar.md @@ -0,0 +1,98 @@ +# Grammar for Chapter 8 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatment + | metaStatement + ; + +whileStatement + : 'while' '(' expression ')' statement + ; + +breakStatement + : 'break' ';' + ; + +continueStatement + : 'continue' ';' + ; + +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]; +``` \ No newline at end of file diff --git a/chapter09/docs/09-graph1.gv b/chapter09/docs/09-graph1.gv new file mode 100644 index 00000000..4f712c2d --- /dev/null +++ b/chapter09/docs/09-graph1.gv @@ -0,0 +1,67 @@ +digraph chapter08 { +/* +int x = arg + arg; +if(arg < 10) { + return arg + arg; +} +else { + x = x + 1; +} +return x; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_7 [ label="2" ]; + Mul8 [ label="*" ]; + Con_9 [ label="10" ]; + LT10 [ label="<" ]; + If11 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_16 [ label="2" ]; + Mul17 [ label="*" ]; + Return18 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Con_20 [ label="1" ]; + Add21 [ label="+" ]; + Return24 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return18[taillabel=0 color=red]; + Stop3 -> Return24[taillabel=1 color=red]; + Mul8 -> Start2:p1[taillabel=1]; + Mul8 -> Con_7[taillabel=2]; + LT10 -> Start2:p1[taillabel=1]; + LT10 -> Con_9[taillabel=2]; + If11 -> Start2:p0[taillabel=0 color=red]; + If11 -> LT10[taillabel=1]; + Mul17 -> Start2:p1[taillabel=1]; + Mul17 -> Con_16[taillabel=2]; + Return18 -> If11:p0[taillabel=0 color=red]; + Return18 -> Mul17[taillabel=1]; + Add21 -> Mul8[taillabel=1]; + Add21 -> Con_20[taillabel=2]; + Return24 -> If11:p1[taillabel=0 color=red]; + Return24 -> Add21[taillabel=1]; +} \ No newline at end of file diff --git a/chapter09/docs/09-graph1.svg b/chapter09/docs/09-graph1.svg new file mode 100644 index 00000000..fce8d53c --- /dev/null +++ b/chapter09/docs/09-graph1.svg @@ -0,0 +1,222 @@ + + + + + + +chapter08 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Stop3 + +Stop + + + +Return18 + +Return + + + +Stop3->Return18 + + +0 + + + +Return24 + +Return + + + +Stop3->Return24 + + +1 + + + +Con_7 + +2 + + + +Mul8 + +* + + + +Mul8->Start2:p1 + + +1 + + + +Mul8->Con_7 + + +2 + + + +Con_9 + +10 + + + +LT10 + +< + + + +LT10->Start2:p1 + + +1 + + + +LT10->Con_9 + + +2 + + + +If11 + + +If + + + +True + + +False + + + +If11->Start2:p0 + + +0 + + + +If11->LT10 + + +1 + + + +Con_16 + +2 + + + +Mul17 + +* + + + +Mul17->Start2:p1 + + +1 + + + +Mul17->Con_16 + + +2 + + + +Return18->If11:p0 + + +0 + + + +Return18->Mul17 + + +1 + + + +Con_20 + +1 + + + +Add21 + ++ + + + +Add21->Mul8 + + +1 + + + +Add21->Con_20 + + +2 + + + +Return24->If11:p1 + + +0 + + + +Return24->Add21 + + +1 + + + diff --git a/chapter09/docs/09-graph2.gv b/chapter09/docs/09-graph2.gv new file mode 100644 index 00000000..9f921cc0 --- /dev/null +++ b/chapter09/docs/09-graph2.gv @@ -0,0 +1,63 @@ +digraph chapter09 { +/* +int x = arg + arg; +if(arg < 10) { + return arg + arg; +} +else { + x = x + 1; +} +return x; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_7 [ label="#2" ]; + Mul8 [ label="*" ]; + LT9 [ label="<" ]; + Con_10 [ label="#10" ]; + If11 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Return18 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Add20 [ label="+" ]; + Con_21 [ label="#1" ]; + Return24 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return18[taillabel=0 color=red]; + Stop3 -> Return24[taillabel=1 color=red]; + Mul8 -> Start2:p1[taillabel=1]; + Mul8 -> Con_7[taillabel=2]; + LT9 -> Start2:p1[taillabel=1]; + LT9 -> Con_10[taillabel=2]; + If11 -> Start2:p0[taillabel=0 color=red]; + If11 -> LT9[taillabel=1]; + Return18 -> If11:p0[taillabel=0 color=red]; + Return18 -> Mul8[taillabel=1]; + Add20 -> Mul8[taillabel=1]; + Add20 -> Con_21[taillabel=2]; + Return24 -> If11:p1[taillabel=0 color=red]; + Return24 -> Add20[taillabel=1]; +} \ No newline at end of file diff --git a/chapter09/docs/09-graph2.svg b/chapter09/docs/09-graph2.svg new file mode 100644 index 00000000..111ec172 --- /dev/null +++ b/chapter09/docs/09-graph2.svg @@ -0,0 +1,196 @@ + + + + + + +chapter09 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Stop3 + +Stop + + + +Return18 + +Return + + + +Stop3->Return18 + + +0 + + + +Return24 + +Return + + + +Stop3->Return24 + + +1 + + + +Con_7 + +#2 + + + +Mul8 + +* + + + +Mul8->Start2:p1 + + +1 + + + +Mul8->Con_7 + + +2 + + + +LT9 + +< + + + +LT9->Start2:p1 + + +1 + + + +Con_10 + +#10 + + + +LT9->Con_10 + + +2 + + + +If11 + + +If + + + +True + + +False + + + +If11->Start2:p0 + + +0 + + + +If11->LT9 + + +1 + + + +Return18->Mul8 + + +1 + + + +Return18->If11:p0 + + +0 + + + +Add20 + ++ + + + +Add20->Mul8 + + +1 + + + +Con_21 + +#1 + + + +Add20->Con_21 + + +2 + + + +Return24->If11:p1 + + +0 + + + +Return24->Add20 + + +1 + + + diff --git a/chapter09/docs/09-graph3.gv b/chapter09/docs/09-graph3.gv new file mode 100644 index 00000000..9df55c1c --- /dev/null +++ b/chapter09/docs/09-graph3.gv @@ -0,0 +1,37 @@ +digraph chapter08 { +/* +return arg*arg-arg*arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Mul6 [ label="*" ]; + Mul7 [ label="*" ]; + Sub8 [ label="-" ]; + Return9 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return9[taillabel=0 color=red]; + Mul6 -> Start2:p1[taillabel=1]; + Mul6 -> Start2:p1[taillabel=2]; + Mul7 -> Start2:p1[taillabel=1]; + Mul7 -> Start2:p1[taillabel=2]; + Sub8 -> Mul6[taillabel=1]; + Sub8 -> Mul7[taillabel=2]; + Return9 -> Start2:p0[taillabel=0 color=red]; + Return9 -> Sub8[taillabel=1]; +} \ No newline at end of file diff --git a/chapter09/docs/09-graph3.svg b/chapter09/docs/09-graph3.svg new file mode 100644 index 00000000..f26c96e8 --- /dev/null +++ b/chapter09/docs/09-graph3.svg @@ -0,0 +1,109 @@ + + + + + + +chapter08 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Stop3 + +Stop + + + +Return9 + +Return + + + +Stop3->Return9 + + +0 + + + +Mul6 + +* + + + +Mul6->Start2:p1 + + +1 + + + +Mul7 + +* + + + +Mul7->Start2:p1 + + +1 + + + +Sub8 + +- + + + +Sub8->Mul6 + + +1 + + + +Sub8->Mul7 + + +2 + + + +Return9->Start2:p0 + + +0 + + + +Return9->Sub8 + + +1 + + + diff --git a/chapter09/docs/09-graph4.gv b/chapter09/docs/09-graph4.gv new file mode 100644 index 00000000..8886f73a --- /dev/null +++ b/chapter09/docs/09-graph4.gv @@ -0,0 +1,29 @@ +digraph chapter09 { +/* +return arg*arg-arg*arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_9 [ label="#0" ]; + Return10 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return10[taillabel=0 color=red]; + Return10 -> Start2:p0[taillabel=0 color=red]; + Return10 -> Con_9[taillabel=1]; +} diff --git a/chapter09/docs/09-graph4.svg b/chapter09/docs/09-graph4.svg new file mode 100644 index 00000000..4eef5414 --- /dev/null +++ b/chapter09/docs/09-graph4.svg @@ -0,0 +1,67 @@ + + + + + + +chapter09 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Stop3 + +Stop + + + +Return10 + +Return + + + +Stop3->Return10 + + +0 + + + +Con_9 + +#0 + + + +Return10->Start2:p0 + + +0 + + + +Return10->Con_9 + + +1 + + + diff --git a/chapter09/docs/09-graph5.gv b/chapter09/docs/09-graph5.gv new file mode 100644 index 00000000..72274239 --- /dev/null +++ b/chapter09/docs/09-graph5.gv @@ -0,0 +1,63 @@ +digraph chapter09 { +/* +int step = 1; +while (arg < 10) { + arg = arg + step + 1; +} +return arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_6 [ label="#1" ]; + Loop7 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_arg9 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + LT10 [ label="<" ]; + Con_11 [ label="#10" ]; + If12 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Add16 [ label="+" ]; + Add18 [ label="+" ]; + Return21 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop7;Phi_arg9;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return21[taillabel=0 color=red]; + Loop7 -> Start2:p0[taillabel=1 color=red]; + Loop7 -> If12:p0[taillabel=2 color=red constraint=false]; + Phi_arg9 -> Loop7 [style=dotted taillabel=0]; + Phi_arg9 -> Start2:p1[taillabel=1]; + Phi_arg9 -> Add18[taillabel=2 constraint=false]; + LT10 -> Phi_arg9[taillabel=1]; + LT10 -> Con_11[taillabel=2]; + If12 -> Loop7[taillabel=0 color=red]; + If12 -> LT10[taillabel=1]; + Add16 -> Con_6[taillabel=1]; + Add16 -> Phi_arg9[taillabel=2]; + Add18 -> Add16[taillabel=1]; + Add18 -> Con_6[taillabel=2]; + Return21 -> If12:p1[taillabel=0 color=red]; + Return21 -> Phi_arg9[taillabel=1]; +} diff --git a/chapter09/docs/09-graph5.svg b/chapter09/docs/09-graph5.svg new file mode 100644 index 00000000..9d0698db --- /dev/null +++ b/chapter09/docs/09-graph5.svg @@ -0,0 +1,210 @@ + + + + + + +chapter09 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Stop3 + +Stop + + + +Return21 + +Return + + + +Stop3->Return21 + + +0 + + + +Con_6 + +#1 + + + +Loop7 + +Loop + + + +Loop7->Start2:p0 + + +1 + + + +If12 + + +If + + + +True + + +False + + + +Loop7->If12:p0 + + +2 + + + +Phi_arg9 + +φ_arg + + + +Phi_arg9->Start2:p1 + + +1 + + + +Phi_arg9->Loop7 + + +0 + + + +Add18 + ++ + + + +Phi_arg9->Add18 + + +2 + + + +LT10 + +< + + + +LT10->Phi_arg9 + + +1 + + + +Con_11 + +#10 + + + +LT10->Con_11 + + +2 + + + +If12->Loop7 + + +0 + + + +If12->LT10 + + +1 + + + +Add16 + ++ + + + +Add16->Con_6 + + +1 + + + +Add16->Phi_arg9 + + +2 + + + +Add18->Con_6 + + +2 + + + +Add18->Add16 + + +1 + + + +Return21->Phi_arg9 + + +1 + + + +Return21->If12:p1 + + +0 + + + diff --git a/chapter09/docs/09-graph6.gv b/chapter09/docs/09-graph6.gv new file mode 100644 index 00000000..492c320e --- /dev/null +++ b/chapter09/docs/09-graph6.gv @@ -0,0 +1,60 @@ +digraph chapter09 { +/* +int step = 1; +while (arg < 10) { + arg = arg + step + 1; +} +return arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Loop7 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_arg9 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + LT10 [ label="<" ]; + Con_11 [ label="#10" ]; + If12 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Return21 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Con_24 [ label="#2" ]; + Add25 [ label="+" ]; + { rank=same; Loop7;Phi_arg9;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return21[taillabel=0 color=red]; + Loop7 -> Start2:p0[taillabel=1 color=red]; + Loop7 -> If12:p0[taillabel=2 color=red constraint=false]; + Phi_arg9 -> Loop7 [style=dotted taillabel=0]; + Phi_arg9 -> Start2:p1[taillabel=1]; + Phi_arg9 -> Add25[taillabel=2 constraint=false]; + LT10 -> Phi_arg9[taillabel=1]; + LT10 -> Con_11[taillabel=2]; + If12 -> Loop7[taillabel=0 color=red]; + If12 -> LT10[taillabel=1]; + Return21 -> If12:p1[taillabel=0 color=red]; + Return21 -> Phi_arg9[taillabel=1]; + Add25 -> Phi_arg9[taillabel=1]; + Add25 -> Con_24[taillabel=2]; +} \ No newline at end of file diff --git a/chapter09/docs/09-graph6.svg b/chapter09/docs/09-graph6.svg new file mode 100644 index 00000000..36c70099 --- /dev/null +++ b/chapter09/docs/09-graph6.svg @@ -0,0 +1,184 @@ + + + + + + +chapter09 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Stop3 + +Stop + + + +Return21 + +Return + + + +Stop3->Return21 + + +0 + + + +Loop7 + +Loop + + + +Loop7->Start2:p0 + + +1 + + + +If12 + + +If + + + +True + + +False + + + +Loop7->If12:p0 + + +2 + + + +Phi_arg9 + +φ_arg + + + +Phi_arg9->Start2:p1 + + +1 + + + +Phi_arg9->Loop7 + + +0 + + + +Add25 + ++ + + + +LT10 + +< + + + +LT10->Phi_arg9 + + +1 + + + +Con_11 + +#10 + + + +LT10->Con_11 + + +2 + + + +If12->Loop7 + + +0 + + + +If12->LT10 + + +1 + + + +Return21->Phi_arg9 + + +1 + + + +Return21->If12:p1 + + +0 + + + +Con_24 + +#2 + + + +Add25->Phi_arg9 + + + +1 + + + +Add25->Con_24 + + +2 + + + diff --git a/chapter09/docs/build-graphs.sh b/chapter09/docs/build-graphs.sh new file mode 100644 index 00000000..dbd22623 --- /dev/null +++ b/chapter09/docs/build-graphs.sh @@ -0,0 +1,6 @@ +dot -Tsvg 09-graph1.gv > 09-graph1.svg +dot -Tsvg 09-graph2.gv > 09-graph2.svg +dot -Tsvg 09-graph3.gv > 09-graph3.svg +dot -Tsvg 09-graph4.gv > 09-graph4.svg +dot -Tsvg 09-graph5.gv > 09-graph5.svg +dot -Tsvg 09-graph6.gv > 09-graph6.svg -- cgit v1.2.3