From 1a9cac97df063af82516ca35bde34fde62d24c56 Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Sat, 11 Nov 2023 23:17:22 +0000 Subject: Chapter 6 (#38) * #37 Create chapter 6 skeleton * #37 Revise type system - TOP, BOTTOM, CONTROL are now directly implemented in Type, XCONTROL is a new type and that's implemented directly too. We have a _type field that is like an enum. * #37 Revise Type.meet() - this is now final. Subclasses can override xmeet() which is protected but now handles simple types in Type itself. * #37 Basic test for peephole of CFG * #37 Revise compute of if * #37 Revise compute of if * #37 WIP peephole of If * #37 WIP peephole of If * #37 WIP peephole of If * #37 WIP peephole of If * #37 WIP peephole of If * #37 WIP fix the chars inserted by IntelliJ * #37 WIP Fix compute type in IfNode * #37 WIP Null check region inputs * #37 WIP Fix where we choose great grand parent instead of grand parent Add new test * #37 WIP More fixes and tests * #37 WIP Some minor adjustments * Cleanup folding dead IF tests Remove isDeadCtrl & just test for the constant. Remove DEAD_CTRL, doesn't properly reset between tests. Move keep/unkeep to Node. PhiNode has a proper compute() call. ProjNode ideal is a lot simpler. Region doesn't ever get a null. Move the mergeScopes Region peep till after all Phis are added. Type TOP and XCONTROL count as constants. TypeTuple gets a toString * #37 WIP Upate README * #37 WIP Region node should check if one of its inputs is a region that needs to be peepholed * #37 WIP If node should check if its ctrl input is a Region that has only 1 live input so can be peepholed * #37 WIP Further update to README to make the peephole logic clearer. Also discuss the relationship between Region and Phi nodes * Region removes dead input paths Remove region-folding in Return, If. Add a Makefile. Reformat triple-quote lines to be emacs-friendly. * StopNode idealize Return type sharpens to include control input. * Remove !=, >=, >; use Not and <, <=, == Fix bug mixing rotating different ops. Generalize Add fold constants; apply to Mul, EQ. Fix Div.copy * Fix bug rotating e.g. < or <= Peep is only valid for associative ops * #37 WIP Doc updates * Work over the Ch6 Readme Major issue: Region inputs align 1-to-1 with Phi inputs, but a Region can have zero to many Phis. When we lose a Region input (dead path), we need to lose the same inputs to each Phi - but we don't lose the Phis themselves, unless we're folding away down to the last live input. * Update chapter06/README.md Co-authored-by: Yichen Yan * Update chapter06/README.md Co-authored-by: Yichen Yan * #37 Backport type system changes to chapter 2 * #37 Backport type system changes to chapter 3 * #37 Backport type system changes to chapter 4 * #37 Backport type system changes to chapter 5 * #37 Merge chapter 5 updates from main. Remove language grammar module as we describe the grammar incrementally in each chapter. * #37 Chapter 6 doc updates - added visuals to show effects of CFG peephole * #37 Sync some updates to chapter 2 * #37 Sync some updates to chapter 3 * #37 Sync some updates to chapter 4 --------- Co-authored-by: Cliff Click Co-authored-by: Yichen Yan --- chapter06/docs/06-grammar.md | 83 +++++++ chapter06/docs/06-graph1-post.gv | 29 +++ chapter06/docs/06-graph1-post.svg | 67 +++++ chapter06/docs/06-graph1-pre.gv | 52 ++++ chapter06/docs/06-graph1-pre.svg | 160 ++++++++++++ chapter06/docs/06-graph2-post.gv | 33 +++ chapter06/docs/06-graph2-post.svg | 67 +++++ chapter06/docs/06-graph2-pre.gv | 55 ++++ chapter06/docs/06-graph2-pre.svg | 154 ++++++++++++ chapter06/docs/06-graph3-false.gv | 35 +++ chapter06/docs/06-graph3-false.svg | 67 +++++ chapter06/docs/06-graph3-nonconst.gv | 86 +++++++ chapter06/docs/06-graph3-nonconst.svg | 290 +++++++++++++++++++++ chapter06/docs/06-graph3-true.gv | 35 +++ chapter06/docs/06-graph3-true.svg | 67 +++++ chapter06/docs/06-graph4-arg2.gv | 37 +++ chapter06/docs/06-graph4-arg2.svg | 67 +++++ chapter06/docs/06-graph4-nonconst.gv | 122 +++++++++ chapter06/docs/06-graph4-nonconst.svg | 456 ++++++++++++++++++++++++++++++++++ chapter06/docs/06-graph4-true.gv | 37 +++ chapter06/docs/06-graph4-true.svg | 67 +++++ chapter06/docs/build-graphs.sh | 10 + 22 files changed, 2076 insertions(+) create mode 100644 chapter06/docs/06-grammar.md create mode 100644 chapter06/docs/06-graph1-post.gv create mode 100644 chapter06/docs/06-graph1-post.svg create mode 100644 chapter06/docs/06-graph1-pre.gv create mode 100644 chapter06/docs/06-graph1-pre.svg create mode 100644 chapter06/docs/06-graph2-post.gv create mode 100644 chapter06/docs/06-graph2-post.svg create mode 100644 chapter06/docs/06-graph2-pre.gv create mode 100644 chapter06/docs/06-graph2-pre.svg create mode 100644 chapter06/docs/06-graph3-false.gv create mode 100644 chapter06/docs/06-graph3-false.svg create mode 100644 chapter06/docs/06-graph3-nonconst.gv create mode 100644 chapter06/docs/06-graph3-nonconst.svg create mode 100644 chapter06/docs/06-graph3-true.gv create mode 100644 chapter06/docs/06-graph3-true.svg create mode 100644 chapter06/docs/06-graph4-arg2.gv create mode 100644 chapter06/docs/06-graph4-arg2.svg create mode 100644 chapter06/docs/06-graph4-nonconst.gv create mode 100644 chapter06/docs/06-graph4-nonconst.svg create mode 100644 chapter06/docs/06-graph4-true.gv create mode 100644 chapter06/docs/06-graph4-true.svg create mode 100644 chapter06/docs/build-graphs.sh (limited to 'chapter06/docs') diff --git a/chapter06/docs/06-grammar.md b/chapter06/docs/06-grammar.md new file mode 100644 index 00000000..ea779a5a --- /dev/null +++ b/chapter06/docs/06-grammar.md @@ -0,0 +1,83 @@ +# Grammar for Chapter 6 + +```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]; +``` \ No newline at end of file diff --git a/chapter06/docs/06-graph1-post.gv b/chapter06/docs/06-graph1-post.gv new file mode 100644 index 00000000..59214346 --- /dev/null +++ b/chapter06/docs/06-graph1-post.gv @@ -0,0 +1,29 @@ +digraph chapter06 { +/* +if( true ) return 2; +return 1; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_12 [ label="#2" ]; + Return13 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return13[taillabel=0 color=red]; + Return13 -> Start2:p0[taillabel=0 color=red]; + Return13 -> Con_12[taillabel=1]; +} \ No newline at end of file diff --git a/chapter06/docs/06-graph1-post.svg b/chapter06/docs/06-graph1-post.svg new file mode 100644 index 00000000..faabcd8c --- /dev/null +++ b/chapter06/docs/06-graph1-post.svg @@ -0,0 +1,67 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Stop3 + +Stop + + + +Return13 + +Return + + + +Stop3->Return13 + + +0 + + + +Con_12 + +#2 + + + +Return13->Start2:p0 + + +0 + + + +Return13->Con_12 + + +1 + + + diff --git a/chapter06/docs/06-graph1-pre.gv b/chapter06/docs/06-graph1-pre.gv new file mode 100644 index 00000000..b04fa2f9 --- /dev/null +++ b/chapter06/docs/06-graph1-pre.gv @@ -0,0 +1,52 @@ +digraph chapter06 { +/* +if( true ) return 2; +return 1; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_6 [ label="#1" ]; + If7 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_11 [ label="#2" ]; + Return12 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Con_13 [ label="#~CONTROL" ]; + Region14 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Con_15 [ label="#1" ]; + Return16 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region14;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return12[taillabel=0 color=red]; + Stop3 -> Return16[taillabel=1 color=red]; + If7 -> Start2:p0[taillabel=0 color=red]; + If7 -> Con_6[taillabel=1]; + Return12 -> If7:p0[taillabel=0 color=red]; + Return12 -> Con_11[taillabel=1]; + Region14 -> Con_13[taillabel=1]; + Region14 -> If7:p1[taillabel=2 color=red]; + Return16 -> Region14[taillabel=0 color=red]; + Return16 -> Con_15[taillabel=1]; +} \ No newline at end of file diff --git a/chapter06/docs/06-graph1-pre.svg b/chapter06/docs/06-graph1-pre.svg new file mode 100644 index 00000000..f80edcfc --- /dev/null +++ b/chapter06/docs/06-graph1-pre.svg @@ -0,0 +1,160 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Stop3 + +Stop + + + +Return12 + +Return + + + +Stop3->Return12 + + +0 + + + +Return16 + +Return + + + +Stop3->Return16 + + +1 + + + +Con_6 + +#1 + + + +If7 + + +If + + + +True + + +False + + + +If7->Start2:p0 + + +0 + + + +If7->Con_6 + + +1 + + + +Con_11 + +#2 + + + +Return12->If7:p0 + + +0 + + + +Return12->Con_11 + + +1 + + + +Con_13 + +#~CONTROL + + + +Region14 + +Region + + + +Region14->If7:p1 + + +2 + + + +Region14->Con_13 + + +1 + + + +Con_15 + +#1 + + + +Return16->Region14 + + +0 + + + +Return16->Con_15 + + +1 + + + diff --git a/chapter06/docs/06-graph2-post.gv b/chapter06/docs/06-graph2-post.gv new file mode 100644 index 00000000..dacd80fd --- /dev/null +++ b/chapter06/docs/06-graph2-post.gv @@ -0,0 +1,33 @@ +digraph chapter06 { +/* +int a=1; +if( true ) + a=2; +else + a=3; +return a; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Return17 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_13 [ label="#2" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Return17 -> Start2:p0[taillabel=0 color=red]; + Return17 -> Con_13[taillabel=1]; + Stop3 -> Return17[taillabel=0 color=red]; +} \ No newline at end of file diff --git a/chapter06/docs/06-graph2-post.svg b/chapter06/docs/06-graph2-post.svg new file mode 100644 index 00000000..269eb15c --- /dev/null +++ b/chapter06/docs/06-graph2-post.svg @@ -0,0 +1,67 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Return17 + +Return + + + +Start2 + + +Start + + + +$ctrl + + + +Return17->Start2:p0 + + +0 + + + +Con_13 + +#2 + + + +Return17->Con_13 + + +1 + + + +Stop3 + +Stop + + + +Stop3->Return17 + + +0 + + + diff --git a/chapter06/docs/06-graph2-pre.gv b/chapter06/docs/06-graph2-pre.gv new file mode 100644 index 00000000..d183b4c4 --- /dev/null +++ b/chapter06/docs/06-graph2-pre.gv @@ -0,0 +1,55 @@ +digraph chapter06 { +/* +int a=1; +if( true ) + a=2; +else + a=3; +return a; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Return16 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_7 [ label="#1" ]; + If8 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_12 [ label="#2" ]; + Con_13 [ label="#3" ]; + Region14 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a15 [ style=filled fillcolor=lightyellow label="φ_a" ]; + { rank=same; Region14;Phi_a15;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Return16 -> Region14[taillabel=0 color=red]; + Return16 -> Phi_a15[taillabel=1]; + Stop3 -> Return16[taillabel=0 color=red]; + If8 -> Start2:p0[taillabel=0 color=red]; + If8 -> Con_7[taillabel=1]; + Region14 -> If8:p0[taillabel=1 color=red]; + Region14 -> If8:p1[taillabel=2 color=red]; + Phi_a15 -> Region14 [style=dotted taillabel=0]; + Phi_a15 -> Con_12[taillabel=1]; + Phi_a15 -> Con_13[taillabel=2]; +} diff --git a/chapter06/docs/06-graph2-pre.svg b/chapter06/docs/06-graph2-pre.svg new file mode 100644 index 00000000..e9a4dd55 --- /dev/null +++ b/chapter06/docs/06-graph2-pre.svg @@ -0,0 +1,154 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Return16 + +Return + + + +Region14 + +Region + + + +Return16->Region14 + + +0 + + + +Phi_a15 + +φ_a + + + +Return16->Phi_a15 + + +1 + + + +Start2 + + +Start + + + +$ctrl + + + +Stop3 + +Stop + + + +Stop3->Return16 + + +0 + + + +Con_7 + +#1 + + + +If8 + + +If + + + +True + + +False + + + +If8->Start2:p0 + + +0 + + + +If8->Con_7 + + +1 + + + +Con_12 + +#2 + + + +Con_13 + +#3 + + + +Region14->If8:p0 + + +1 + + + +Region14->If8:p1 + + +2 + + + +Phi_a15->Con_12 + + +1 + + + +Phi_a15->Con_13 + + +2 + + + +Phi_a15->Region14 + + +0 + + + diff --git a/chapter06/docs/06-graph3-false.gv b/chapter06/docs/06-graph3-false.gv new file mode 100644 index 00000000..28f741fa --- /dev/null +++ b/chapter06/docs/06-graph3-false.gv @@ -0,0 +1,35 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_30 [ label="#1" ]; + Return31 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return31[taillabel=0 color=red]; + Return31 -> Start2:p0[taillabel=0 color=red]; + Return31 -> Con_30[taillabel=1]; +} diff --git a/chapter06/docs/06-graph3-false.svg b/chapter06/docs/06-graph3-false.svg new file mode 100644 index 00000000..49b04f09 --- /dev/null +++ b/chapter06/docs/06-graph3-false.svg @@ -0,0 +1,67 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Stop3 + +Stop + + + +Return31 + +Return + + + +Stop3->Return31 + + +0 + + + +Con_30 + +#1 + + + +Return31->Start2:p0 + + +0 + + + +Return31->Con_30 + + +1 + + + diff --git a/chapter06/docs/06-graph3-nonconst.gv b/chapter06/docs/06-graph3-nonconst.gv new file mode 100644 index 00000000..0746be85 --- /dev/null +++ b/chapter06/docs/06-graph3-nonconst.gv @@ -0,0 +1,86 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_6 [ label="#0" ]; + Con_7 [ label="#1" ]; + If8 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_12 [ label="#2" ]; + If13 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_17 [ label="#2" ]; + Con_18 [ label="#3" ]; + Region19 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_b20 [ style=filled fillcolor=lightyellow label="φ_b" ]; + Region21 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a22 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Phi_b23 [ style=filled fillcolor=lightyellow label="φ_b" ]; + Add24 [ label="+" ]; + Return25 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region19;Phi_b20;} + { rank=same; Region21;Phi_b23;Phi_a22;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return25[taillabel=0 color=red]; + If8 -> Start2:p0[taillabel=0 color=red]; + If8 -> Start2:p1[taillabel=1]; + If13 -> If8:p0[taillabel=0 color=red]; + If13 -> Start2:p1[taillabel=1]; + Region19 -> If13:p0[taillabel=1 color=red]; + Region19 -> If13:p1[taillabel=2 color=red]; + Phi_b20 -> Region19 [style=dotted taillabel=0]; + Phi_b20 -> Con_17[taillabel=1]; + Phi_b20 -> Con_18[taillabel=2]; + Region21 -> Region19[taillabel=1 color=red]; + Region21 -> If8:p1[taillabel=2 color=red]; + Phi_a22 -> Region21 [style=dotted taillabel=0]; + Phi_a22 -> Con_12[taillabel=1]; + Phi_a22 -> Con_6[taillabel=2]; + Phi_b23 -> Region21 [style=dotted taillabel=0]; + Phi_b23 -> Phi_b20[taillabel=1]; + Phi_b23 -> Con_7[taillabel=2]; + Add24 -> Phi_b23[taillabel=1]; + Add24 -> Phi_a22[taillabel=2]; + Return25 -> Region21[taillabel=0 color=red]; + Return25 -> Add24[taillabel=1]; +} \ No newline at end of file diff --git a/chapter06/docs/06-graph3-nonconst.svg b/chapter06/docs/06-graph3-nonconst.svg new file mode 100644 index 00000000..dee852e4 --- /dev/null +++ b/chapter06/docs/06-graph3-nonconst.svg @@ -0,0 +1,290 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Stop3 + +Stop + + + +Return25 + +Return + + + +Stop3->Return25 + + +0 + + + +Con_6 + +#0 + + + +Con_7 + +#1 + + + +If8 + + +If + + + +True + + +False + + + +If8->Start2:p0 + + +0 + + + +If8->Start2:p1 + + +1 + + + +Con_12 + +#2 + + + +If13 + + +If + + + +True + + +False + + + +If13->Start2:p1 + + +1 + + + +If13->If8:p0 + + +0 + + + +Con_17 + +#2 + + + +Con_18 + +#3 + + + +Region19 + +Region + + + +Region19->If13:p0 + + +1 + + + +Region19->If13:p1 + + +2 + + + +Phi_b20 + +φ_b + + + +Phi_b20->Con_17 + + +1 + + + +Phi_b20->Con_18 + + +2 + + + +Phi_b20->Region19 + + +0 + + + +Region21 + +Region + + + +Region21->If8:p1 + + +2 + + + +Region21->Region19 + + +1 + + + +Phi_a22 + +φ_a + + + +Phi_a22->Con_6 + + +2 + + + +Phi_a22->Con_12 + + +1 + + + +Phi_a22->Region21 + + +0 + + + +Phi_b23 + +φ_b + + + +Phi_b23->Con_7 + + +2 + + + +Phi_b23->Phi_b20 + + +1 + + + +Phi_b23->Region21 + + +0 + + + +Add24 + ++ + + + +Add24->Phi_a22 + + +2 + + + +Add24->Phi_b23 + + +1 + + + +Return25->Region21 + + +0 + + + +Return25->Add24 + + +1 + + + diff --git a/chapter06/docs/06-graph3-true.gv b/chapter06/docs/06-graph3-true.gv new file mode 100644 index 00000000..8fdcc5df --- /dev/null +++ b/chapter06/docs/06-graph3-true.gv @@ -0,0 +1,35 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_28 [ label="#4" ]; + Return29 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return29[taillabel=0 color=red]; + Return29 -> Start2:p0[taillabel=0 color=red]; + Return29 -> Con_28[taillabel=1]; +} \ No newline at end of file diff --git a/chapter06/docs/06-graph3-true.svg b/chapter06/docs/06-graph3-true.svg new file mode 100644 index 00000000..7e573cc6 --- /dev/null +++ b/chapter06/docs/06-graph3-true.svg @@ -0,0 +1,67 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Stop3 + +Stop + + + +Return29 + +Return + + + +Stop3->Return29 + + +0 + + + +Con_28 + +#4 + + + +Return29->Start2:p0 + + +0 + + + +Return29->Con_28 + + +1 + + + diff --git a/chapter06/docs/06-graph4-arg2.gv b/chapter06/docs/06-graph4-arg2.gv new file mode 100644 index 00000000..7d6913e2 --- /dev/null +++ b/chapter06/docs/06-graph4-arg2.gv @@ -0,0 +1,37 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_44 [ label="#5" ]; + Return45 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return45[taillabel=0 color=red]; + Return45 -> Start2:p0[taillabel=0 color=red]; + Return45 -> Con_44[taillabel=1]; +} diff --git a/chapter06/docs/06-graph4-arg2.svg b/chapter06/docs/06-graph4-arg2.svg new file mode 100644 index 00000000..8ec80be4 --- /dev/null +++ b/chapter06/docs/06-graph4-arg2.svg @@ -0,0 +1,67 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Stop3 + +Stop + + + +Return45 + +Return + + + +Stop3->Return45 + + +0 + + + +Con_44 + +#5 + + + +Return45->Start2:p0 + + +0 + + + +Return45->Con_44 + + +1 + + + diff --git a/chapter06/docs/06-graph4-nonconst.gv b/chapter06/docs/06-graph4-nonconst.gv new file mode 100644 index 00000000..b8899b48 --- /dev/null +++ b/chapter06/docs/06-graph4-nonconst.gv @@ -0,0 +1,122 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_6 [ label="#0" ]; + Con_7 [ label="#1" ]; + Con_8 [ label="#0" ]; + If9 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_13 [ label="#1" ]; + Con_14 [ label="#2" ]; + EQNode15 [ label="==" ]; + If16 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_20 [ label="#2" ]; + Con_21 [ label="#3" ]; + Region22 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_c23 [ style=filled fillcolor=lightyellow label="φ_c" ]; + If24 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_28 [ label="#2" ]; + Con_29 [ label="#3" ]; + Region30 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_b31 [ style=filled fillcolor=lightyellow label="φ_b" ]; + Region32 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a33 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Phi_b34 [ style=filled fillcolor=lightyellow label="φ_b" ]; + Phi_c35 [ style=filled fillcolor=lightyellow label="φ_c" ]; + Add36 [ label="+" ]; + Add37 [ label="+" ]; + Return38 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region22;Phi_c23;} + { rank=same; Region30;Phi_b31;} + { rank=same; Region32;Phi_c35;Phi_a33;Phi_b34;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return38[taillabel=0 color=red]; + If9 -> Start2:p0[taillabel=0 color=red]; + If9 -> Start2:p1[taillabel=1]; + EQNode15 -> Start2:p1[taillabel=1]; + EQNode15 -> Con_14[taillabel=2]; + If16 -> If9:p0[taillabel=0 color=red]; + If16 -> EQNode15[taillabel=1]; + Region22 -> If16:p0[taillabel=1 color=red]; + Region22 -> If16:p1[taillabel=2 color=red]; + Phi_c23 -> Region22 [style=dotted taillabel=0]; + Phi_c23 -> Con_20[taillabel=1]; + Phi_c23 -> Con_21[taillabel=2]; + If24 -> Region22[taillabel=0 color=red]; + If24 -> Start2:p1[taillabel=1]; + Region30 -> If24:p0[taillabel=1 color=red]; + Region30 -> If24:p1[taillabel=2 color=red]; + Phi_b31 -> Region30 [style=dotted taillabel=0]; + Phi_b31 -> Con_28[taillabel=1]; + Phi_b31 -> Con_29[taillabel=2]; + Region32 -> Region30[taillabel=1 color=red]; + Region32 -> If9:p1[taillabel=2 color=red]; + Phi_a33 -> Region32 [style=dotted taillabel=0]; + Phi_a33 -> Con_13[taillabel=1]; + Phi_a33 -> Con_6[taillabel=2]; + Phi_b34 -> Region32 [style=dotted taillabel=0]; + Phi_b34 -> Phi_b31[taillabel=1]; + Phi_b34 -> Con_7[taillabel=2]; + Phi_c35 -> Region32 [style=dotted taillabel=0]; + Phi_c35 -> Phi_c23[taillabel=1]; + Phi_c35 -> Con_8[taillabel=2]; + Add36 -> Phi_c35[taillabel=1]; + Add36 -> Phi_b34[taillabel=2]; + Add37 -> Add36[taillabel=1]; + Add37 -> Phi_a33[taillabel=2]; + Return38 -> Region32[taillabel=0 color=red]; + Return38 -> Add37[taillabel=1]; +} diff --git a/chapter06/docs/06-graph4-nonconst.svg b/chapter06/docs/06-graph4-nonconst.svg new file mode 100644 index 00000000..d38c3636 --- /dev/null +++ b/chapter06/docs/06-graph4-nonconst.svg @@ -0,0 +1,456 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Stop3 + +Stop + + + +Return38 + +Return + + + +Stop3->Return38 + + +0 + + + +Con_6 + +#0 + + + +Con_7 + +#1 + + + +Con_8 + +#0 + + + +If9 + + +If + + + +True + + +False + + + +If9->Start2:p0 + + +0 + + + +If9->Start2:p1 + + +1 + + + +Con_13 + +#1 + + + +Con_14 + +#2 + + + +EQNode15 + +== + + + +EQNode15->Start2:p1 + + +1 + + + +EQNode15->Con_14 + + +2 + + + +If16 + + +If + + + +True + + +False + + + +If16->If9:p0 + + +0 + + + +If16->EQNode15 + + +1 + + + +Con_20 + +#2 + + + +Con_21 + +#3 + + + +Region22 + +Region + + + +Region22->If16:p0 + + +1 + + + +Region22->If16:p1 + + +2 + + + +Phi_c23 + +φ_c + + + +Phi_c23->Con_20 + + +1 + + + +Phi_c23->Con_21 + + +2 + + + +Phi_c23->Region22 + + +0 + + + +If24 + + +If + + + +True + + +False + + + +If24->Start2:p1 + + +1 + + + +If24->Region22 + + +0 + + + +Con_28 + +#2 + + + +Con_29 + +#3 + + + +Region30 + +Region + + + +Region30->If24:p0 + + +1 + + + +Region30->If24:p1 + + +2 + + + +Phi_b31 + +φ_b + + + +Phi_b31->Con_28 + + +1 + + + +Phi_b31->Con_29 + + +2 + + + +Phi_b31->Region30 + + +0 + + + +Region32 + +Region + + + +Region32->If9:p1 + + +2 + + + +Region32->Region30 + + +1 + + + +Phi_a33 + +φ_a + + + +Phi_a33->Con_6 + + +2 + + + +Phi_a33->Con_13 + + +1 + + + +Phi_a33->Region32 + + +0 + + + +Phi_b34 + +φ_b + + + +Phi_b34->Con_7 + + +2 + + + +Phi_b34->Phi_b31 + + +1 + + + +Phi_b34->Region32 + + +0 + + + +Phi_c35 + +φ_c + + + +Phi_c35->Con_8 + + +2 + + + +Phi_c35->Phi_c23 + + +1 + + + +Phi_c35->Region32 + + +0 + + + +Add36 + ++ + + + +Add36->Phi_b34 + + +2 + + + +Add36->Phi_c35 + + +1 + + + +Add37 + ++ + + + +Add37->Phi_a33 + + +2 + + + +Add37->Add36 + + +1 + + + +Return38->Region32 + + +0 + + + +Return38->Add37 + + +1 + + + diff --git a/chapter06/docs/06-graph4-true.gv b/chapter06/docs/06-graph4-true.gv new file mode 100644 index 00000000..6e48ee7d --- /dev/null +++ b/chapter06/docs/06-graph4-true.gv @@ -0,0 +1,37 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_44 [ label="#6" ]; + Return45 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return45[taillabel=0 color=red]; + Return45 -> Start2:p0[taillabel=0 color=red]; + Return45 -> Con_44[taillabel=1]; +} diff --git a/chapter06/docs/06-graph4-true.svg b/chapter06/docs/06-graph4-true.svg new file mode 100644 index 00000000..a533ea21 --- /dev/null +++ b/chapter06/docs/06-graph4-true.svg @@ -0,0 +1,67 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Stop3 + +Stop + + + +Return45 + +Return + + + +Stop3->Return45 + + +0 + + + +Con_44 + +#6 + + + +Return45->Start2:p0 + + +0 + + + +Return45->Con_44 + + +1 + + + diff --git a/chapter06/docs/build-graphs.sh b/chapter06/docs/build-graphs.sh new file mode 100644 index 00000000..d65826f4 --- /dev/null +++ b/chapter06/docs/build-graphs.sh @@ -0,0 +1,10 @@ +dot -Tsvg 06-graph1-pre.gv > 06-graph1-pre.svg +dot -Tsvg 06-graph1-post.gv > 06-graph1-post.svg +dot -Tsvg 06-graph2-pre.gv > 06-graph2-pre.svg +dot -Tsvg 06-graph2-post.gv > 06-graph2-post.svg +dot -Tsvg 06-graph3-nonconst.gv > 06-graph3-nonconst.svg +dot -Tsvg 06-graph3-true.gv > 06-graph3-true.svg +dot -Tsvg 06-graph3-false.gv > 06-graph3-false.svg +dot -Tsvg 06-graph4-nonconst.gv > 06-graph4-nonconst.svg +dot -Tsvg 06-graph4-true.gv > 06-graph4-true.svg +dot -Tsvg 06-graph4-arg2.gv > 06-graph4-arg2.svg -- cgit v1.2.3