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 --- .gitignore | 4 + README.md | 3 +- .../java/com/seaofnodes/simple/node/AddNode.java | 5 +- .../java/com/seaofnodes/simple/node/DivNode.java | 10 +- .../java/com/seaofnodes/simple/node/MinusNode.java | 5 +- .../java/com/seaofnodes/simple/node/MulNode.java | 6 +- .../com/seaofnodes/simple/node/ReturnNode.java | 4 +- .../java/com/seaofnodes/simple/node/StartNode.java | 6 +- .../java/com/seaofnodes/simple/node/SubNode.java | 6 +- .../main/java/com/seaofnodes/simple/type/Type.java | 21 +- .../java/com/seaofnodes/simple/type/TypeBot.java | 14 - .../com/seaofnodes/simple/type/TypeInteger.java | 7 +- .../java/com/seaofnodes/simple/node/AddNode.java | 5 +- .../java/com/seaofnodes/simple/node/DivNode.java | 10 +- .../java/com/seaofnodes/simple/node/MinusNode.java | 5 +- .../java/com/seaofnodes/simple/node/MulNode.java | 6 +- .../main/java/com/seaofnodes/simple/node/Node.java | 4 +- .../com/seaofnodes/simple/node/ReturnNode.java | 4 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 5 +- .../java/com/seaofnodes/simple/node/StartNode.java | 6 +- .../java/com/seaofnodes/simple/node/SubNode.java | 6 +- .../main/java/com/seaofnodes/simple/type/Type.java | 21 +- .../java/com/seaofnodes/simple/type/TypeBot.java | 14 - .../com/seaofnodes/simple/type/TypeInteger.java | 7 +- .../java/com/seaofnodes/simple/node/AddNode.java | 2 +- .../java/com/seaofnodes/simple/node/BoolNode.java | 3 +- .../java/com/seaofnodes/simple/node/DivNode.java | 3 +- .../java/com/seaofnodes/simple/node/MinusNode.java | 3 +- .../java/com/seaofnodes/simple/node/MulNode.java | 3 +- .../main/java/com/seaofnodes/simple/node/Node.java | 2 +- .../java/com/seaofnodes/simple/node/ProjNode.java | 7 +- .../com/seaofnodes/simple/node/ReturnNode.java | 2 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 4 +- .../java/com/seaofnodes/simple/node/StartNode.java | 1 - .../java/com/seaofnodes/simple/node/SubNode.java | 3 +- .../main/java/com/seaofnodes/simple/type/Type.java | 32 +- .../java/com/seaofnodes/simple/type/TypeBot.java | 19 - .../com/seaofnodes/simple/type/TypeControl.java | 16 - .../com/seaofnodes/simple/type/TypeInteger.java | 11 +- .../java/com/seaofnodes/simple/type/TypeTuple.java | 6 + .../main/java/com/seaofnodes/simple/Parser.java | 1 + .../java/com/seaofnodes/simple/node/AddNode.java | 2 +- .../java/com/seaofnodes/simple/node/BoolNode.java | 3 +- .../java/com/seaofnodes/simple/node/DivNode.java | 5 +- .../java/com/seaofnodes/simple/node/IfNode.java | 1 + .../java/com/seaofnodes/simple/node/MinusNode.java | 3 +- .../java/com/seaofnodes/simple/node/MulNode.java | 3 +- .../main/java/com/seaofnodes/simple/node/Node.java | 2 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 3 +- .../java/com/seaofnodes/simple/node/ProjNode.java | 7 +- .../com/seaofnodes/simple/node/RegionNode.java | 3 +- .../com/seaofnodes/simple/node/ReturnNode.java | 2 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 8 +- .../java/com/seaofnodes/simple/node/StartNode.java | 1 - .../java/com/seaofnodes/simple/node/StopNode.java | 3 +- .../java/com/seaofnodes/simple/node/SubNode.java | 3 +- .../main/java/com/seaofnodes/simple/type/Type.java | 28 +- .../java/com/seaofnodes/simple/type/TypeBot.java | 19 - .../com/seaofnodes/simple/type/TypeControl.java | 16 - .../com/seaofnodes/simple/type/TypeInteger.java | 6 +- .../java/com/seaofnodes/simple/type/TypeTuple.java | 8 +- chapter06/Makefile | 92 +++ chapter06/README.md | 154 ++++ 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 + chapter06/pom.xml | 14 + .../com/seaofnodes/simple/GraphVisualizer.java | 235 ++++++ .../main/java/com/seaofnodes/simple/Parser.java | 528 ++++++++++++++ .../java/com/seaofnodes/simple/node/AddNode.java | 154 ++++ .../java/com/seaofnodes/simple/node/BoolNode.java | 58 ++ .../com/seaofnodes/simple/node/ConstantNode.java | 41 ++ .../java/com/seaofnodes/simple/node/DivNode.java | 37 + .../java/com/seaofnodes/simple/node/IfNode.java | 44 ++ .../java/com/seaofnodes/simple/node/MinusNode.java | 28 + .../java/com/seaofnodes/simple/node/MulNode.java | 56 ++ .../java/com/seaofnodes/simple/node/MultiNode.java | 9 + .../main/java/com/seaofnodes/simple/node/Node.java | 380 ++++++++++ .../java/com/seaofnodes/simple/node/NotNode.java | 28 + .../java/com/seaofnodes/simple/node/PhiNode.java | 98 +++ .../java/com/seaofnodes/simple/node/ProjNode.java | 50 ++ .../com/seaofnodes/simple/node/RegionNode.java | 56 ++ .../com/seaofnodes/simple/node/ReturnNode.java | 44 ++ .../java/com/seaofnodes/simple/node/ScopeNode.java | 138 ++++ .../java/com/seaofnodes/simple/node/StartNode.java | 37 + .../java/com/seaofnodes/simple/node/StopNode.java | 51 ++ .../java/com/seaofnodes/simple/node/SubNode.java | 41 ++ .../main/java/com/seaofnodes/simple/type/Type.java | 77 ++ .../com/seaofnodes/simple/type/TypeInteger.java | 63 ++ .../java/com/seaofnodes/simple/type/TypeTuple.java | 32 + .../java/com/seaofnodes/simple/Chapter06Test.java | 795 +++++++++++++++++++++ language/.gitignore | 28 - language/README.md | 6 - language/examples/all-features.lang | 21 - language/pom.xml | 79 -- .../com/seaofnodes/simple/antlr/SimpleLanguage.g4 | 170 ----- pom.xml | 2 +- 116 files changed, 5623 insertions(+), 527 deletions(-) delete mode 100644 chapter02/src/main/java/com/seaofnodes/simple/type/TypeBot.java delete mode 100644 chapter03/src/main/java/com/seaofnodes/simple/type/TypeBot.java delete mode 100644 chapter04/src/main/java/com/seaofnodes/simple/type/TypeBot.java delete mode 100644 chapter04/src/main/java/com/seaofnodes/simple/type/TypeControl.java delete mode 100644 chapter05/src/main/java/com/seaofnodes/simple/type/TypeBot.java delete mode 100644 chapter05/src/main/java/com/seaofnodes/simple/type/TypeControl.java create mode 100644 chapter06/Makefile create mode 100644 chapter06/README.md 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 create mode 100644 chapter06/pom.xml create mode 100644 chapter06/src/main/java/com/seaofnodes/simple/GraphVisualizer.java create mode 100644 chapter06/src/main/java/com/seaofnodes/simple/Parser.java create mode 100644 chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java create mode 100644 chapter06/src/main/java/com/seaofnodes/simple/node/BoolNode.java create mode 100644 chapter06/src/main/java/com/seaofnodes/simple/node/ConstantNode.java create mode 100644 chapter06/src/main/java/com/seaofnodes/simple/node/DivNode.java create mode 100644 chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java create mode 100644 chapter06/src/main/java/com/seaofnodes/simple/node/MinusNode.java create mode 100644 chapter06/src/main/java/com/seaofnodes/simple/node/MulNode.java create mode 100644 chapter06/src/main/java/com/seaofnodes/simple/node/MultiNode.java create mode 100644 chapter06/src/main/java/com/seaofnodes/simple/node/Node.java create mode 100644 chapter06/src/main/java/com/seaofnodes/simple/node/NotNode.java create mode 100644 chapter06/src/main/java/com/seaofnodes/simple/node/PhiNode.java create mode 100644 chapter06/src/main/java/com/seaofnodes/simple/node/ProjNode.java create mode 100644 chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java create mode 100644 chapter06/src/main/java/com/seaofnodes/simple/node/ReturnNode.java create mode 100644 chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java create mode 100644 chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java create mode 100644 chapter06/src/main/java/com/seaofnodes/simple/node/StopNode.java create mode 100644 chapter06/src/main/java/com/seaofnodes/simple/node/SubNode.java create mode 100644 chapter06/src/main/java/com/seaofnodes/simple/type/Type.java create mode 100644 chapter06/src/main/java/com/seaofnodes/simple/type/TypeInteger.java create mode 100644 chapter06/src/main/java/com/seaofnodes/simple/type/TypeTuple.java create mode 100644 chapter06/src/test/java/com/seaofnodes/simple/Chapter06Test.java delete mode 100644 language/.gitignore delete mode 100644 language/README.md delete mode 100644 language/examples/all-features.lang delete mode 100644 language/pom.xml delete mode 100644 language/src/main/antlr4/com/seaofnodes/simple/antlr/SimpleLanguage.g4 diff --git a/.gitignore b/.gitignore index c991bc2c..57f113ef 100644 --- a/.gitignore +++ b/.gitignore @@ -13,4 +13,8 @@ target/ # Editors .#* *~ +TAGS + +# Libs +*/lib/*jar diff --git a/README.md b/README.md index d8f99553..59a342b1 100644 --- a/README.md +++ b/README.md @@ -26,7 +26,6 @@ Sea Of Nodes intermediate representation. The simple language will be a small subset of C. -* [Language](language/README.md): Simple language grammar. * [Chapter 1](chapter01/README.md): Script that returns an integer literal, i.e., an empty function that takes no arguments and returns a single integer value. The `return` statement. * [Chapter 2](chapter02/README.md): Simple binary arithmetic such as addition, subtraction, multiplication, division with constants. Peephole optimization / simple constant folding. @@ -34,7 +33,7 @@ The simple language will be a small subset of C. constant. * [Chapter 4](chapter04/README.md): A non-constant external variable input named `arg`. Binary and Comparison operators involving constants and `arg`. Non-zero values will be truthy. Peephole optimizations involving algebraic simplifications. * [Chapter 5](chapter05/README.md): `if` statement. CFG construction. -* Chapter 6: Peephole optimization around dead control flow. +* [Chapter 6](chapter06/README.md): Peephole optimization around dead control flow. * Chapter 7: `while` statement. * Chapter 8: Global Value Numbering. * Chapter 9: Functions and calls. diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/AddNode.java index 6784ad60..a0376dd4 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -21,9 +21,10 @@ public class AddNode extends Node { public Type compute() { if( in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1 ) { - return TypeInteger.constant(i0.value()+i1.value()); + if (i0.isConstant() && i1.isConstant()) + return TypeInteger.constant(i0.value()+i1.value()); } - return TypeBot.BOTTOM; + return Type.BOTTOM; } @Override diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/DivNode.java index ca7df79c..4f502e5f 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; public class DivNode extends Node { @@ -22,11 +21,12 @@ public class DivNode extends Node { public Type compute() { if (in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1) { - return i1.value() == 0 - ? TypeInteger.ZERO - : TypeInteger.constant(i0.value()/i1.value()); + if (i0.isConstant() && i1.isConstant()) + return i1.value() == 0 + ? TypeInteger.ZERO + : TypeInteger.constant(i0.value()/i1.value()); } - return TypeBot.BOTTOM; + return Type.BOTTOM; } @Override diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 834f4c11..08924563 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; public class MinusNode extends Node { @@ -20,8 +19,8 @@ public class MinusNode extends Node { @Override public Type compute() { if (in(1)._type instanceof TypeInteger i0) - return TypeInteger.constant(-i0.value()); - return TypeBot.BOTTOM; + return i0.isConstant() ? TypeInteger.constant(-i0.value()) : i0; + return Type.BOTTOM; } @Override diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/MulNode.java index 0fa54966..c6718d27 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; public class MulNode extends Node { @@ -22,9 +21,10 @@ public class MulNode extends Node { public Type compute() { if (in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1) { - return TypeInteger.constant(i0.value()*i1.value()); + if (i0.isConstant() && i1.isConstant()) + return TypeInteger.constant(i0.value()*i1.value()); } - return TypeBot.BOTTOM; + return Type.BOTTOM; } @Override diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 18f5eed9..a0f2e931 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -31,8 +31,8 @@ public class ReturnNode extends Node { @Override public boolean isCFG() { return true; } @Override - public TypeBot compute() { - return TypeBot.BOTTOM; + public Type compute() { + return Type.BOTTOM; } @Override diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/StartNode.java index 08b8333a..99e240ad 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.type.TypeBot; +import com.seaofnodes.simple.type.Type; /** * The Start node represents the start of the function. For now, we do not @@ -26,9 +26,7 @@ public class StartNode extends Node { @Override public boolean isCFG() { return true; } @Override - public TypeBot compute() { - return TypeBot.BOTTOM; - } + public Type compute() { return Type.BOTTOM; } @Override public Node idealize() { return null; } diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/SubNode.java index 71d70fa6..6eda4f11 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; public class SubNode extends Node { @@ -22,9 +21,10 @@ public class SubNode extends Node { public Type compute() { if (in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1) { - return TypeInteger.constant(i0.value()-i1.value()); + if (i0.isConstant() && i1.isConstant()) + return TypeInteger.constant(i0.value()-i1.value()); } - return TypeBot.BOTTOM; + return Type.BOTTOM; } @Override diff --git a/chapter02/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter02/src/main/java/com/seaofnodes/simple/type/Type.java index 872e453d..172cc632 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/type/Type.java @@ -17,9 +17,24 @@ package com.seaofnodes.simple.type; * simple constant folding e.g. 1+2 == 3 stuff. */ -public abstract class Type { +public class Type { - public boolean isConstant() { return false; } + // ---------------------------------------------------------- + // Simple types are implemented fully here. "Simple" means: the code and + // type hierarchy are simple, not that the Type is conceptually simple. + static final byte TBOT = 0; // Bottom (ALL) + static final byte TTOP = 1; // Top (ANY) + static final byte TSIMPLE = 2; // End of the Simple Types + static final byte TINT = 3; // All Integers; see TypeInteger + public final byte _type; - public abstract StringBuilder _print(StringBuilder sb); + public boolean is_simple() { return _type < TSIMPLE; } + private static final String[] STRS = new String[]{"BOTTOM","TOP"}; + protected Type(byte type) { _type = type; } + + public static final Type BOTTOM = new Type( TBOT ); // ALL + + public boolean isConstant() { return _type == TTOP; } + + public StringBuilder _print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;} } diff --git a/chapter02/src/main/java/com/seaofnodes/simple/type/TypeBot.java b/chapter02/src/main/java/com/seaofnodes/simple/type/TypeBot.java deleted file mode 100644 index bc191241..00000000 --- a/chapter02/src/main/java/com/seaofnodes/simple/type/TypeBot.java +++ /dev/null @@ -1,14 +0,0 @@ -package com.seaofnodes.simple.type; - -import java.lang.StringBuilder; - -public class TypeBot extends Type { - - public static final TypeBot BOTTOM = new TypeBot(); - - @Override - public String toString() { return "Bottom"; } - - @Override - public StringBuilder _print(StringBuilder sb) { return sb.append(toString()); } -} diff --git a/chapter02/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter02/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index ff6e865b..69fb811c 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -10,9 +10,12 @@ public class TypeInteger extends Type { /** * The constant value observed for this type */ - public final long _con; + private final long _con; - public TypeInteger(long con) { _con = con; } + public TypeInteger(long con) { + super(TINT); + _con = con; + } public static TypeInteger constant(long con) { return new TypeInteger(con); } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java index 6784ad60..a0376dd4 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -21,9 +21,10 @@ public class AddNode extends Node { public Type compute() { if( in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1 ) { - return TypeInteger.constant(i0.value()+i1.value()); + if (i0.isConstant() && i1.isConstant()) + return TypeInteger.constant(i0.value()+i1.value()); } - return TypeBot.BOTTOM; + return Type.BOTTOM; } @Override diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java index ca7df79c..4f502e5f 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; public class DivNode extends Node { @@ -22,11 +21,12 @@ public class DivNode extends Node { public Type compute() { if (in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1) { - return i1.value() == 0 - ? TypeInteger.ZERO - : TypeInteger.constant(i0.value()/i1.value()); + if (i0.isConstant() && i1.isConstant()) + return i1.value() == 0 + ? TypeInteger.ZERO + : TypeInteger.constant(i0.value()/i1.value()); } - return TypeBot.BOTTOM; + return Type.BOTTOM; } @Override diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 834f4c11..08924563 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; public class MinusNode extends Node { @@ -20,8 +19,8 @@ public class MinusNode extends Node { @Override public Type compute() { if (in(1)._type instanceof TypeInteger i0) - return TypeInteger.constant(-i0.value()); - return TypeBot.BOTTOM; + return i0.isConstant() ? TypeInteger.constant(-i0.value()) : i0; + return Type.BOTTOM; } @Override diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java index 0fa54966..c6718d27 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; public class MulNode extends Node { @@ -22,9 +21,10 @@ public class MulNode extends Node { public Type compute() { if (in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1) { - return TypeInteger.constant(i0.value()*i1.value()); + if (i0.isConstant() && i1.isConstant()) + return TypeInteger.constant(i0.value()*i1.value()); } - return TypeBot.BOTTOM; + return Type.BOTTOM; } @Override diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java index a778687d..43dc6fa5 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java @@ -47,7 +47,7 @@ public abstract class Node { /** * A private Global Static mutable counter, for unique node id generation. - * To make the compiler multi-threaded, this field will have to move into a TLS. + * To make the compiler multithreaded, this field will have to move into a TLS. * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values. * */ private static int UNIQUE_ID = 1; @@ -197,7 +197,7 @@ public abstract class Node { // Remove node 'use' from 'def's (i.e. our) output list, by compressing the list in-place. // Return true if the output list is empty afterward. // Error is 'use' does not exist; ok for 'use' to be null. - private boolean delUse( Node use ) { + protected boolean delUse( Node use ) { ArrayList outs = _outputs; int lidx = outs.size()-1; // Last index // This 1-line hack compresses an element out of an ArrayList diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 18f5eed9..a0f2e931 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -31,8 +31,8 @@ public class ReturnNode extends Node { @Override public boolean isCFG() { return true; } @Override - public TypeBot compute() { - return TypeBot.BOTTOM; + public Type compute() { + return Type.BOTTOM; } @Override diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 5f5d66a0..49857533 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.type.TypeBot; +import com.seaofnodes.simple.type.Type; import java.util.*; @@ -43,7 +42,7 @@ public class ScopeNode extends Node { } @Override - public TypeBot compute() { return TypeBot.BOTTOM; } + public Type compute() { return Type.BOTTOM; } @Override public Node idealize() { return null; } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/StartNode.java index 08b8333a..99e240ad 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.type.TypeBot; +import com.seaofnodes.simple.type.Type; /** * The Start node represents the start of the function. For now, we do not @@ -26,9 +26,7 @@ public class StartNode extends Node { @Override public boolean isCFG() { return true; } @Override - public TypeBot compute() { - return TypeBot.BOTTOM; - } + public Type compute() { return Type.BOTTOM; } @Override public Node idealize() { return null; } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java index 71d70fa6..6eda4f11 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; public class SubNode extends Node { @@ -22,9 +21,10 @@ public class SubNode extends Node { public Type compute() { if (in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1) { - return TypeInteger.constant(i0.value()-i1.value()); + if (i0.isConstant() && i1.isConstant()) + return TypeInteger.constant(i0.value()-i1.value()); } - return TypeBot.BOTTOM; + return Type.BOTTOM; } @Override diff --git a/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java index 872e453d..172cc632 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java @@ -17,9 +17,24 @@ package com.seaofnodes.simple.type; * simple constant folding e.g. 1+2 == 3 stuff. */ -public abstract class Type { +public class Type { - public boolean isConstant() { return false; } + // ---------------------------------------------------------- + // Simple types are implemented fully here. "Simple" means: the code and + // type hierarchy are simple, not that the Type is conceptually simple. + static final byte TBOT = 0; // Bottom (ALL) + static final byte TTOP = 1; // Top (ANY) + static final byte TSIMPLE = 2; // End of the Simple Types + static final byte TINT = 3; // All Integers; see TypeInteger + public final byte _type; - public abstract StringBuilder _print(StringBuilder sb); + public boolean is_simple() { return _type < TSIMPLE; } + private static final String[] STRS = new String[]{"BOTTOM","TOP"}; + protected Type(byte type) { _type = type; } + + public static final Type BOTTOM = new Type( TBOT ); // ALL + + public boolean isConstant() { return _type == TTOP; } + + public StringBuilder _print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;} } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/type/TypeBot.java b/chapter03/src/main/java/com/seaofnodes/simple/type/TypeBot.java deleted file mode 100644 index bc191241..00000000 --- a/chapter03/src/main/java/com/seaofnodes/simple/type/TypeBot.java +++ /dev/null @@ -1,14 +0,0 @@ -package com.seaofnodes.simple.type; - -import java.lang.StringBuilder; - -public class TypeBot extends Type { - - public static final TypeBot BOTTOM = new TypeBot(); - - @Override - public String toString() { return "Bottom"; } - - @Override - public StringBuilder _print(StringBuilder sb) { return sb.append(toString()); } -} diff --git a/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index ff6e865b..69fb811c 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -10,9 +10,12 @@ public class TypeInteger extends Type { /** * The constant value observed for this type */ - public final long _con; + private final long _con; - public TypeInteger(long con) { _con = con; } + public TypeInteger(long con) { + super(TINT); + _con = con; + } public static TypeInteger constant(long con) { return new TypeInteger(con); } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/AddNode.java index d4d15bef..d9fc6ad9 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -25,7 +25,7 @@ public class AddNode extends Node { return TypeInteger.constant(i0.value()+i1.value()); return i0.meet(i1); } - return TypeBot.BOTTOM; + return Type.BOTTOM; } @Override diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 02eb7ce9..06be0b75 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; abstract public class BoolNode extends Node { @@ -33,7 +32,7 @@ abstract public class BoolNode extends Node { return TypeInteger.constant(doOp(i0.value(), i1.value()) ? 1 : 0); return i0.meet(i1); } - return TypeBot.BOTTOM; + return Type.BOTTOM; } abstract boolean doOp(long lhs, long rhs); diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/DivNode.java index ae87deac..86b1e95c 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; public class DivNode extends Node { @@ -28,7 +27,7 @@ public class DivNode extends Node { : TypeInteger.constant(i0.value()/i1.value()); return i0.meet(i1); } - return TypeBot.BOTTOM; + return Type.BOTTOM; } @Override diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 533155d9..08924563 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; public class MinusNode extends Node { @@ -21,7 +20,7 @@ public class MinusNode extends Node { public Type compute() { if (in(1)._type instanceof TypeInteger i0) return i0.isConstant() ? TypeInteger.constant(-i0.value()) : i0; - return TypeBot.BOTTOM; + return Type.BOTTOM; } @Override diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/MulNode.java index 5f6c1ad8..19f2a340 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; public class MulNode extends Node { @@ -26,7 +25,7 @@ public class MulNode extends Node { return TypeInteger.constant(i0.value()*i1.value()); return i0.meet(i1); } - return TypeBot.BOTTOM; + return Type.BOTTOM; } @Override diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java index 804d30e0..b8a7bbd6 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java @@ -226,7 +226,7 @@ public abstract class Node { // Remove node 'use' from 'def's (i.e. our) output list, by compressing the list in-place. // Return true if the output list is empty afterward. // Error is 'use' does not exist; ok for 'use' to be null. - private boolean delUse( Node use ) { + protected boolean delUse( Node use ) { ArrayList outs = _outputs; int lidx = outs.size()-1; // Last index // This 1-line hack compresses an element out of an ArrayList diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java index be0556ed..6f36226b 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeTuple; public class ProjNode extends Node { @@ -31,7 +30,11 @@ public class ProjNode extends Node { @Override public Type compute() { Type t = ctrl()._type; - return t instanceof TypeTuple tt ? tt._types[_idx] : TypeBot.BOTTOM; + return getType(t); + } + + private Type getType(Type t) { + return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; } @Override diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index e20d01e5..73594d2a 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -32,7 +32,7 @@ public class ReturnNode extends Node { @Override public Type compute() { - return new TypeTuple(TypeControl.CONTROL,expr()._type); + return new TypeTuple(Type.CONTROL,expr()._type); } @Override diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 45966791..17ea561a 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.type.TypeBot; +import com.seaofnodes.simple.type.Type; import java.util.*; @@ -43,7 +43,7 @@ public class ScopeNode extends Node { } @Override - public TypeBot compute() { return TypeBot.BOTTOM; } + public Type compute() { return Type.BOTTOM; } @Override public Node idealize() { return null; } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java index 91573de8..85c6cd34 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeTuple; /** diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/SubNode.java index 42ddc1c1..ec2168e6 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; public class SubNode extends Node { @@ -26,7 +25,7 @@ public class SubNode extends Node { return TypeInteger.constant(i0.value()-i1.value()); return i0.meet(i1); } - return TypeBot.BOTTOM; + return Type.BOTTOM; } @Override diff --git a/chapter04/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter04/src/main/java/com/seaofnodes/simple/type/Type.java index d9567dc8..a063e28e 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/type/Type.java @@ -17,14 +17,36 @@ package com.seaofnodes.simple.type; * simple constant folding e.g. 1+2 == 3 stuff. */ -public abstract class Type { +public class Type { - public static final TypeControl CONTROL = new TypeControl(); + // ---------------------------------------------------------- + // Simple types are implemented fully here. "Simple" means: the code and + // type hierarchy are simple, not that the Type is conceptually simple. + static final byte TBOT = 0; // Bottom (ALL) + static final byte TTOP = 1; // Top (ANY) + static final byte TCTRL = 2; // Ctrl flow bottom + static final byte TSIMPLE = 3; // End of the Simple Types + static final byte TINT = 4; // All Integers; see TypeInteger + static final byte TTUPLE = 5; // Tuples; finite collections of unrelated Types, kept in parallel - public boolean isConstant() { return false; } + public final byte _type; - public abstract StringBuilder _print(StringBuilder sb); + public boolean is_simple() { return _type < TSIMPLE; } + private static final String[] STRS = new String[]{"BOTTOM","TOP","CONTROL"}; + protected Type(byte type) { _type = type; } - public Type meet(Type other) { return TypeBot.BOTTOM; } + public static final Type BOTTOM = new Type( TBOT ); // ALL + public static final Type TOP = new Type( TTOP ); // ANY + public static final Type CONTROL = new Type( TCTRL ); // Ctrl + public boolean isConstant() { return _type == TTOP; } + + public StringBuilder _print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;} + + public Type meet(Type other) { return Type.BOTTOM; } + + @Override + public final String toString() { + return _print(new StringBuilder()).toString(); + } } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/type/TypeBot.java b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeBot.java deleted file mode 100644 index a5709448..00000000 --- a/chapter04/src/main/java/com/seaofnodes/simple/type/TypeBot.java +++ /dev/null @@ -1,19 +0,0 @@ -package com.seaofnodes.simple.type; - -import java.lang.StringBuilder; - -public class TypeBot extends Type { - - public static final TypeBot BOTTOM = new TypeBot(); - - @Override - public String toString() { return "Bottom"; } - - @Override - public Type meet(Type other) { - return BOTTOM; - } - - @Override - public StringBuilder _print(StringBuilder sb) { return sb.append(toString()); } -} diff --git a/chapter04/src/main/java/com/seaofnodes/simple/type/TypeControl.java b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeControl.java deleted file mode 100644 index 0130ffd0..00000000 --- a/chapter04/src/main/java/com/seaofnodes/simple/type/TypeControl.java +++ /dev/null @@ -1,16 +0,0 @@ -package com.seaofnodes.simple.type; - -public class TypeControl extends Type { - - public static final TypeControl CONTROL = new TypeControl(); - - @Override - public StringBuilder _print(StringBuilder sb) { - return sb.append(toString()); - } - - @Override - public String toString() { - return "Control"; - } -} diff --git a/chapter04/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 63c46035..3037e45f 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -17,18 +17,17 @@ public class TypeInteger extends Type { */ private final long _con; - public TypeInteger(boolean is_con, long con) { _is_con = is_con; _con = con; } + public TypeInteger(boolean is_con, long con) { + super(TINT); + _is_con = is_con; + _con = con; + } public static TypeInteger constant(long con) { return new TypeInteger(true, con); } public boolean isTop() { return !_is_con && _con==0; } public boolean isBot() { return !_is_con && _con==1; } - @Override - public String toString() { - return _print(new StringBuilder()).toString(); - } - @Override public StringBuilder _print(StringBuilder sb) { if (isTop()) return sb.append("IntTop"); diff --git a/chapter04/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index 036147a2..513972aa 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -5,6 +5,7 @@ public class TypeTuple extends Type { public final Type[] _types; public TypeTuple(Type... _types) { + super(TTUPLE); this._types = _types; } @@ -15,6 +16,11 @@ public class TypeTuple extends Type { @Override public StringBuilder _print(StringBuilder sb) { + sb.append("[ "); + for( Type t : _types ) + t._print(sb).append(","); + sb.setLength(sb.length()-1); + sb.append("]"); return sb; } } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java index a132fce0..0461dc69 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java @@ -182,6 +182,7 @@ public class Parser { // Merge results _scope = tScope; _allScopes.pop(); // Discard pushed from graph display + return ctrl(tScope.mergeScopes(fScope)); } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java index f2b93b2e..f6c49abf 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -25,7 +25,7 @@ public class AddNode extends Node { return TypeInteger.constant(i0.value()+i1.value()); return i0.meet(i1); } - return TypeBot.BOTTOM; + return Type.BOTTOM; } @Override diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java index c1471c58..0ba5e7b0 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; abstract public class BoolNode extends Node { @@ -33,7 +32,7 @@ abstract public class BoolNode extends Node { return TypeInteger.constant(doOp(i0.value(), i1.value()) ? 1 : 0); return i0.meet(i1); } - return TypeBot.BOTTOM; + return Type.BOTTOM; } abstract boolean doOp(long lhs, long rhs); diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java index 489e7275..01314c74 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; public class DivNode extends Node { @@ -28,11 +27,11 @@ public class DivNode extends Node { : TypeInteger.constant(i0.value()/i1.value()); return i0.meet(i1); } - return TypeBot.BOTTOM; + return Type.BOTTOM; } @Override public Node idealize() { return null; } - @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); } + @Override Node copy(Node lhs, Node rhs) { return new DivNode(lhs,rhs); } } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java index feb4f245..b46d37db 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -1,6 +1,7 @@ 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 { diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 533155d9..08924563 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; public class MinusNode extends Node { @@ -21,7 +20,7 @@ public class MinusNode extends Node { public Type compute() { if (in(1)._type instanceof TypeInteger i0) return i0.isConstant() ? TypeInteger.constant(-i0.value()) : i0; - return TypeBot.BOTTOM; + return Type.BOTTOM; } @Override diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java index 9962c445..0f21f67a 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; public class MulNode extends Node { @@ -26,7 +25,7 @@ public class MulNode extends Node { return TypeInteger.constant(i0.value()*i1.value()); return i0.meet(i1); } - return TypeBot.BOTTOM; + return Type.BOTTOM; } @Override diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java index 2d8a14d4..65151acb 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java @@ -227,7 +227,7 @@ public abstract class Node { // Remove node 'use' from 'def's (i.e. our) output list, by compressing the list in-place. // Return true if the output list is empty afterward. // Error is 'use' does not exist; ok for 'use' to be null. - private boolean delUse( Node use ) { + protected boolean delUse( Node use ) { ArrayList outs = _outputs; int lidx = outs.size()-1; // Last index // This 1-line hack compresses an element out of an ArrayList diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 656e6182..87c84453 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeBot; public class PhiNode extends Node { @@ -25,7 +24,7 @@ public class PhiNode extends Node { @Override public Type compute() { - return TypeBot.BOTTOM; + return Type.BOTTOM; } @Override diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 8e223e93..86e3b144 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeTuple; public class ProjNode extends Node { @@ -31,7 +30,11 @@ public class ProjNode extends Node { @Override public Type compute() { Type t = ctrl()._type; - return t instanceof TypeTuple tt ? tt._types[_idx] : TypeBot.BOTTOM; + return getType(t); + } + + private Type getType(Type t) { + return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; } @Override diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java index ae8724b9..354a8f8b 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeControl; public class RegionNode extends Node { public RegionNode(Node... inputs) { super(inputs); } @@ -18,7 +17,7 @@ public class RegionNode extends Node { @Override public Type compute() { - return TypeControl.CONTROL; + return Type.CONTROL; } @Override diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index e20d01e5..73594d2a 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -32,7 +32,7 @@ public class ReturnNode extends Node { @Override public Type compute() { - return new TypeTuple(TypeControl.CONTROL,expr()._type); + return new TypeTuple(Type.CONTROL,expr()._type); } @Override diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 61fac118..93ef54f6 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.type.TypeBot; +import com.seaofnodes.simple.type.Type; import java.util.*; @@ -43,7 +43,7 @@ public class ScopeNode extends Node { } @Override - public TypeBot compute() { return TypeBot.BOTTOM; } + public Type compute() { return Type.BOTTOM; } @Override public Node idealize() { return null; } @@ -124,9 +124,9 @@ public class ScopeNode extends Node { * innermost stack level where the name is bound. * * @param that The ScopeNode to be merged into this - * @return A new Region node representing the merge point + * @return A new node representing the merge point */ - public RegionNode mergeScopes(ScopeNode that) { + public Node mergeScopes(ScopeNode that) { RegionNode r = (RegionNode)ctrl(new RegionNode(null,ctrl(), that.ctrl()).peephole()); for( int i=1; i 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 17 -target 17 + +# 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.%,$(test_javas)) +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) + $(JVM) org.junit.runner.JUnitCore $(test_cp) + +.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) diff --git a/chapter06/README.md b/chapter06/README.md new file mode 100644 index 00000000..dd08aff5 --- /dev/null +++ b/chapter06/README.md @@ -0,0 +1,154 @@ +# Chapter 6 + +In this chapter we do not add new language features. Our goal is to add peephole optimization to `if` statements. + +## Type System Revision + +We now need to extend the type system to introduce another lattice structure, in addition to the Integer lattice. +As before we denote "top" by T and "bottom" by ⊥. + +* "ctrl" represents a live control, whereas "~ctrl" represents a dead control. +* "INT" refers to the integer type. + +| | ⊥ | Ctrl | ~Ctrl | T | INT | +|-------|---|------|-------|-------|-----| +| T | ⊥ | Ctrl | ~Ctrl | T | INT | +| Ctrl | ⊥ | Ctrl | Ctrl | Ctrl | ⊥ | +| ~Ctrl | ⊥ | Ctrl | ~Ctrl | ~Ctrl | ⊥ | +| ⊥ | ⊥ | ⊥ | ⊥ | ⊥ | ⊥ | + +* "top" meets any type is that type, +* "bottom" meets any type is "bottom", +* "top", "bottom", "ctrl", "~ctrl" are classed as simple types, +* "ctrl" meets "~ctrl" is "ctrl" +* Unless covered above, a simple type meets non-simple results in "bottom" + +## Peephole of `if` + +* Our general strategy is to continue parsing the entire `if` statement even if we know that one branch is dead. +* This approach creates dead nodes which get cleaned up by dead code + elimination. The benefits are that we do not introduce special logic during + parsing, the normal graph building machinery takes care of cleaning up dead + nodes. +* When we peephole an `If` node we test if the predicate is a constant. If so, + then one branch or the other dead, depending on if the constant is `0` or not. +* When we add the `Proj` nodes, in this scenario, we already know one of the projections is dead. The peephole of the + relevant `Proj` node replaces the `Proj` with a `Constant` of type "~ctrl" indicating dead control. +* At this point our dead code elimination would kill the `If` node since it has no uses + - but we cannot do that because we need to continue the parse. The + important observation is that *we __can__ kill the `If` node after __both__ + the `Proj` nodes have been created*, because any subsequent control flow can + only see the `Proj` nodes. +* To ensure this, we add a dummy user to `If` before creating the first `Proj` and remove it immediately after, allowing the + second `Proj` to trigger a dead code elimination of the `If`. +* The live `Proj` gets replaced by the parent of `If`, whereas the dead `Proj` gets replaced by "~ctrl". +* The parsing then continues as normal. +* The other changes are when we reach the merge point with a dead control. +* Again keeping with our strategy we merge as normal, including creating `Phi` nodes. +* The `Region` may have have one of its inputs as "~ctrl". This will be seen + by the `Phi` which then optimizes itself. If the `Phi` has just one live + input, the `Phi` peephole replaces itself with the remaining input. +* Finally, at the end, when the `Region` node is peepholed, we see that it has only one live input and no Phi uses + and can be replaced with its one live input. + +## Discussion of `Region` and `Phi` + +One of the invariants we maintain is that the for each control input to a +`Region` every `Phi` has a 1-to-1 relationship with a data input. Thus, if a +`Region` loses a control input, every `Phi`'s corresponding data input must be +deleted. Conversely, we cannot collapse a Region until it has no dependent +`Phi`s. + +When processing `If` we do not remove control inputs to a `Region`, instead the +dead control input is simply set to `Constant(~ctrl)`. The peephole logic in +a `Phi` notices this and replaces itself with the live input. + +## Examples + +We show a number of examples of peephole in action. + +### Example 1 + +```java +if( true ) return 2; +return 1; +``` + +Before peephole: + +![Graph1-Pre](./docs/06-graph1-pre.svg) + +After peephole: + +![Graph1-Post](./docs/06-graph1-post.svg) + +### Example 2 + +```java +int a=1; +if( true ) + a=2; +else + a=3; +return a; +``` + +Before peephole: + +![Graph2-Pre](./docs/06-graph2-pre.svg) + +After peephole: + +![Graph2-Post](./docs/06-graph2-post.svg) + +### Example 3 + +```java +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; +``` + +In this example, `arg` is defined externally. If `arg` is given a non-constant value, then the graph looks like this: + +![Graph3-NonConst](./docs/06-graph3-nonconst.svg) + +If we set `arg` to a non-zero constant such as `1` we get: + +![Graph3-True](./docs/06-graph3-true.svg) + +If we set `arg` to `0` which means false, then: + +![Graph3-False](./docs/06-graph3-false.svg) + +### Example 4 + +```java +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; +``` + +In this example, `arg` is defined externally. If `arg` is given a non-constant value, then the graph looks like this: + +![Graph4-NonConst](./docs/06-graph4-nonconst.svg) + +If we set `arg` to `1` we get: + +![Graph4-True](./docs/06-graph4-true.svg) + +If we set `arg` to `2`, then: + +![Graph4-Arg2](./docs/06-graph4-arg2.svg) 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 diff --git a/chapter06/pom.xml b/chapter06/pom.xml new file mode 100644 index 00000000..7a9b466d --- /dev/null +++ b/chapter06/pom.xml @@ -0,0 +1,14 @@ + + + 4.0.0 + + com.seaofnodes + simple + 1.0 + + chapter06 + jar + Chapter 6 + \ No newline at end of file diff --git a/chapter06/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter06/src/main/java/com/seaofnodes/simple/GraphVisualizer.java new file mode 100644 index 00000000..c1c1c4c9 --- /dev/null +++ b/chapter06/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -0,0 +1,235 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; + +import java.util.*; + +/** + * Simple visualizer that outputs GraphViz dot format. + * The dot output must be saved to a file and run manually via dot to generate the SVG output. + * Currently, this is done manually. + */ +public class GraphVisualizer { + + public String generateDotOutput(Parser parser) { + + // Since the graph has cycles, we need to create a flat list of all the + // nodes in the graph. + Collection all = findAll(parser); + StringBuilder sb = new StringBuilder(); + sb.append("digraph chapter06 {\n"); + sb.append("/*\n"); + sb.append(parser.src()); + sb.append("\n*/\n"); + + // To keep the Scopes below the graph and pointing up into the graph we + // need to group the Nodes in a subgraph cluster, and the scopes into a + // different subgraph cluster. THEN we can draw edges between the + // scopes and nodes. If we try to cross subgraph cluster borders while + // still making the subgraphs DOT gets confused. + sb.append("\trankdir=BT;\n"); // Force Nodes before Scopes + + // Preserve node input order + sb.append("\tordering=\"in\";\n"); + + // Merge multiple edges hitting the same node. Makes common shared + // nodes much prettier to look at. + sb.append("\tconcentrate=\"true\";\n"); + + // Just the Nodes first, in a cluster no edges + nodes(sb, all); + + // Now the scopes, in a cluster no edges + for (ScopeNode sn: parser._allScopes) + scopes(sb, sn); + + // Walk the Node edges + nodeEdges(sb, all); + + // Walk the Scope edges + for (ScopeNode sn: parser._allScopes) + scopeEdges(sb, sn); + + sb.append("}\n"); + return sb.toString(); + } + + + private void nodes(StringBuilder sb, Collection all) { + // Just the Nodes first, in a cluster no edges + sb.append("\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name + for( Node n : all ) { + if( n instanceof ProjNode || n instanceof ScopeNode ) + continue; // Do not emit, rolled into MultiNode or Scope cluster already + sb.append("\t\t").append(n.uniqueName()).append(" [ "); + String lab = n.glabel(); + if( n instanceof MultiNode ) { + // Make a box with the MultiNode on top, and all the projections on the bottom + sb.append("shape=plaintext label=<\n"); + sb.append("\t\t\t\n"); + sb.append("\t\t\t\n"); + sb.append("\t\t\t"); + boolean doProjTable = false; + for( Node use : n._outputs ) { + if( use instanceof ProjNode proj ) { + if (!doProjTable) { + doProjTable = true; + sb.append(""); + } + sb.append("\n"); + sb.append("\t\t\t
").append(lab).append("
").append("\n"); + sb.append("\t\t\t\t").append("\n"); + sb.append("\t\t\t\t"); + } + sb.append(""); + } + } + if (doProjTable) { + sb.append("").append("\n"); + sb.append("\t\t\t\t
").append(proj.glabel()).append("
").append("\n"); + sb.append("\t\t\t
>\n\t\t"); + + } else { + // control nodes have box shape + // 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 + } + + private void scopes( StringBuilder sb, ScopeNode scopenode) { + sb.append("\tnode [shape=plaintext];\n"); + int level=0; + for( HashMap scope : scopenode._scopes ) { + String scopeName = makeScopeName(scopenode, level); + sb.append("\tsubgraph cluster_").append(scopeName).append(" {\n"); // Magic "cluster_" in the subgraph name + sb.append("\t\t").append(scopeName).append(" [label=<\n"); + sb.append("\t\t\t\n"); + // Add the scope level + sb.append("\t\t\t"); + for( String name : scope.keySet() ) + sb.append(""); + sb.append("\n"); + sb.append("\t\t\t
").append(level).append("").append(name).append("
>];\n"); + level++; + } + // Scope clusters nest, so the graphics shows the nested scopes, so + // they are not closed as they are printed; so they just keep nesting. + // We close them all at once here. + sb.append( "\t}\n".repeat( level ) ); // End all Scope clusters + } + + private String makeScopeName(ScopeNode sn, int level) { return sn.uniqueName() + "_" + level; } + private String makePortName(String scopeName, String varName) { return scopeName + "_" + varName; } + + // Walk the node edges + private void nodeEdges(StringBuilder sb, Collection all) { + // All them edge labels + sb.append("\tedge [ fontname=Helvetica, fontsize=8 ];\n"); + for( Node n : all ) { + // Do not display the Constant->Start edge; + // ProjNodes handled by Multi; + // ScopeNodes are done separately + if( n instanceof ConstantNode || n instanceof ProjNode || n instanceof ScopeNode ) + continue; + int i=0; + for( Node def : n._inputs ) { + 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 ) { + String mname = proj.ctrl().uniqueName(); + sb.append(mname).append(":p").append(proj._idx); + } else sb.append(def.uniqueName()); + // Number edges, so we can see how they track + sb.append("[taillabel=").append(i); + // control edges are colored red + if( def.isCFG() ) + sb.append(" color=red"); + sb.append("];\n"); + } + i++; + } + } + } + + // Walk the scope edges + private void scopeEdges( StringBuilder sb, ScopeNode scopenode ) { + sb.append("\tedge [style=dashed color=cornflowerblue];\n"); + int level=0; + for( HashMap scope : scopenode._scopes ) { + String scopeName = makeScopeName(scopenode, level); + for( String name : scope.keySet() ) { + Node def = scopenode.in(scope.get(name)); + if( def==null ) continue; + sb.append("\t") + .append(scopeName).append(":") + .append('"').append(makePortName(scopeName, name)).append('"') // wrap port name with quotes because $ctrl is not valid unquoted + .append(" -> "); + if( def instanceof ProjNode proj ) { + String mname = proj.ctrl().uniqueName(); + sb.append(mname).append(":p").append(proj._idx); + } else sb.append(def.uniqueName()); + sb.append(";\n"); + } + level++; + } + } + + /** + * Finds all nodes in the graph. + */ + private Collection findAll(Parser parser) { + final StartNode start = Parser.START; + final HashMap all = new HashMap<>(); + for( Node n : start._outputs ) + walk(all, n); + // Scan symbol tables + for( HashMap scope : parser._scope._scopes ) + for (Integer i : scope.values()) + walk(all, parser._scope.in(i)); + return all.values(); + } + + /** + * Walk a subgraph and populate distinct nodes in the all list. + */ + private void walk(HashMap all, Node n) { + if(n == null ) return; + if (all.get(n._nid) != null) return; // Been there, done that + all.put(n._nid, n); + for (Node c : n._inputs) + if (c != null) + walk(all, c); + for (Node c : n._outputs) + if (c != null) + walk(all, c); + } +} diff --git a/chapter06/src/main/java/com/seaofnodes/simple/Parser.java b/chapter06/src/main/java/com/seaofnodes/simple/Parser.java new file mode 100644 index 00000000..b08c3c56 --- /dev/null +++ b/chapter06/src/main/java/com/seaofnodes/simple/Parser.java @@ -0,0 +1,528 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; + +import java.util.*; + +/** + * The Parser converts a Simple source program to the Sea of Nodes intermediate + * representation directly in one pass. There is no intermediate Abstract + * Syntax Tree structure. + *

+ * This is a simple recursive descent parser. All lexical analysis is done here as well. + */ +public class Parser { + + /** + * The control is a name that binds to the currently active control + * node in the graph + */ + public static final String CTRL = "$ctrl"; + + /** + * A Global Static, unique to each compilation. This is a public, so we + * can make constants everywhere without having to thread the StartNode + * through the entire parser and optimizer. + *

+ * To make the compiler multithreaded, this field will have to move into a TLS. + */ + public static StartNode START; + + public StopNode STOP; + + // The Lexer. Thin wrapper over a byte[] buffer with a cursor. + private final Lexer _lexer; + + /** + * 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()}. + *

+ * 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. + *

+ * We keep a list of all ScopeNodes so that we can show them in graphs. + * @see #parseIf() + * @see #_allScopes + */ + public ScopeNode _scope; + + /** + * List of keywords disallowed as identifiers + */ + private final HashSet 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 _allScopes = new Stack<>(); + + public Parser(String source, TypeInteger arg) { + _lexer = new Lexer(source); + Node.reset(); + _scope = new ScopeNode(); + START = new StartNode(new Type[]{ Type.CONTROL, arg }); + START.peephole(); + STOP = new StopNode(); + } + + public Parser(String source) { + this(source, TypeInteger.BOT); + } + + String src() { return new String( _lexer._input ); } + + private Node ctrl() { return _scope.ctrl(); } + + private Node ctrl(Node n) { return _scope.ctrl(n); } + + public StopNode parse() { return parse(false); } + public StopNode parse(boolean show) { + _allScopes.push(_scope); + _scope.push(); + try { + _scope.define(CTRL , new ProjNode(START, 0, CTRL ).peephole()); + _scope.define("arg", new ProjNode(START, 1, "arg").peephole()); + parseBlock(); + if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); + return STOP; + } + finally { + _scope.pop(); + _allScopes.pop(); + STOP.peephole(); + if( show ) showGraph(); + } + } + + /** + * Parses a block + * + *

+     *     '{' statements '}'
+     * 
+ * Does not parse the opening or closing '{}' + * @return a {@link Node} or {@code null} + */ + 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 + }; + // Exit scope + _scope.pop(); + return n; + } + + /** + * Parses a statement + * + *
+     *     returnStatement | declStatement | blockStatement | ifStatement | expressionStatement
+     * 
+ * @return a {@link Node} or {@code null} + */ + private Node parseStatement() { + 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 return parseExpressionStatement(); + } + + /** + * Parses a statement + * + *
+     *     if ( expression ) statement [else statement]
+     * 
+ * @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).keep().peephole(); + // Setup projection nodes + Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); + ifNode.unkeep(); + 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 + _allScopes.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(); + + if( tScope.nIns() != ndefs || fScope.nIns() != ndefs ) + throw error("Cannot define a new name on one arm of an if"); + + // Merge results + _scope = tScope; + _allScopes.pop(); // Discard pushed from graph display + + return ctrl(tScope.mergeScopes(fScope)); + } + + + /** + * Parses a return statement; "return" already parsed. + * The $ctrl edge is killed. + * + *
+     *     'return' expr ;
+     * 
+ * @return an expression {@link Node}, never {@code null} + */ + private Node parseReturn() { + var expr = require(parseExpression(), ";"); + Node ret = STOP.addReturn(new ReturnNode(ctrl(), expr).peephole()); + ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill control + return ret; + } + + /** + * Dumps out the node graph + * @return {@code null} + */ + private Node showGraph() { + System.out.println(new GraphVisualizer().generateDotOutput(this)); + return null; + } + + /** + * Parses an expression statement + * + *
+     *     name '=' expression ';'
+     * 
+ * @return an expression {@link Node}, never {@code null} + */ + private Node parseExpressionStatement() { + var name = requireId(); + require("="); + var expr = require(parseExpression(), ";"); + if( _scope.update(name, expr)==null ) + throw error("Undefined name '" + name + "'"); + return expr; + } + + /** + * Parses a declStatement + * + *
+     *     'int' name = expression ';'
+     * 
+ * @return an expression {@link Node}, never {@code null} + */ + private Node parseDecl() { + // Type is 'int' for now + var name = requireId(); + require("="); + var expr = require(parseExpression(), ";"); + if( _scope.define(name,expr) == null ) + throw error("Redefining name '" + name + "'"); + return expr; + } + + /** + * Parse an expression of the form: + * + *
+     *     expr : compareExpr
+     * 
+ * @return an expression {@link Node}, never {@code null} + */ + private Node parseExpression() { return parseComparison(); } + + /** + * Parse an expression of the form: + * + *
+     *     expr : additiveExpr op additiveExpr
+     * 
+ * @return an comparator expression {@link Node}, never {@code null} + */ + private Node parseComparison() { + var lhs = parseAddition(); + if (match("==")) return new BoolNode.EQNode(lhs, parseComparison()).peephole(); + if (match("!=")) return new NotNode(new BoolNode.EQNode(lhs, parseComparison()).peephole()).peephole(); + if (match("<" )) return new BoolNode.LTNode(lhs, parseComparison()).peephole(); + if (match("<=")) return new BoolNode.LENode(lhs, parseComparison()).peephole(); + if (match(">" )) return new BoolNode.LTNode(parseComparison(), lhs).peephole(); + if (match(">=")) return new BoolNode.LENode(parseComparison(), lhs).peephole(); + return lhs; + } + + /** + * Parse an additive expression + * + *
+     *     additiveExpr : multiplicativeExpr (('+' | '-') multiplicativeExpr)*
+     * 
+ * @return an add expression {@link Node}, never {@code null} + */ + private Node parseAddition() { + var lhs = parseMultiplication(); + if (match("+")) return new AddNode(lhs, parseAddition()).peephole(); + if (match("-")) return new SubNode(lhs, parseAddition()).peephole(); + return lhs; + } + + /** + * Parse an multiplicativeExpr expression + * + *
+     *     multiplicativeExpr : unaryExpr (('*' | '/') unaryExpr)*
+     * 
+ * @return a multiply expression {@link Node}, never {@code null} + */ + private Node parseMultiplication() { + var lhs = parseUnary(); + if (match("*")) return new MulNode(lhs, parseMultiplication()).peephole(); + if (match("/")) return new DivNode(lhs, parseMultiplication()).peephole(); + return lhs; + } + + /** + * Parse a unary minus expression. + * + *
+     *     unaryExpr : ('-') unaryExpr | primaryExpr
+     * 
+ * @return a unary expression {@link Node}, never {@code null} + */ + private Node parseUnary() { + if (match("-")) return new MinusNode(parseUnary()).peephole(); + return parsePrimary(); + } + + /** + * Parse a primary expression: + * + *
+     *     primaryExpr : integerLiteral | Identifier | true | false | '(' expression ')'
+     * 
+ * @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); + if( n!=null ) return n; + throw error("Undefined name '" + name + "'"); + } + + /** + * Parse integer literal + * + *
+     *     integerLiteral: [1-9][0-9]* | [0]
+     * 
+ */ + private ConstantNode parseIntegerLiteral() { + return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole(); + } + + ////////////////////////////////// + // Utilities for lexical analysis + + // Return true and skip if "syntax" is next in the stream. + private boolean match (String syntax) { return _lexer.match (syntax); } + // Match must be "exact", not be followed by more id letters + private boolean matchx(String syntax) { return _lexer.matchx(syntax); } + // Return true and do NOT skip if 'ch' is next + private boolean peek(char ch) { return _lexer.peek(ch); } + + // Require and return an identifier + private String requireId() { + String id = _lexer.matchId(); + if (id != null && !KEYWORDS.contains(id) ) return id; + throw error("Expected an identifier, found '"+id+"'"); + } + + // Require an exact match + private void require(String syntax) { require(null, syntax); } + private Node require(Node n, String syntax) { + if (match(syntax)) return n; + throw errorSyntax(syntax); + } + + RuntimeException errorSyntax(String syntax) { + return error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken()); + } + + static RuntimeException error(String errorMessage) { + return new RuntimeException(errorMessage); + } + + //////////////////////////////////// + // Lexer components + + private static class Lexer { + + // Input buffer; an array of text bytes read from a file or a string + private final byte[] _input; + // Tracks current position in input buffer + private int _position = 0; + + /** + * Record the source text for lexing + */ + public Lexer(String source) { + this(source.getBytes()); + } + + /** + * Direct from disk file source + */ + public Lexer(byte[] buf) { + _input = buf; + } + + // Very handy in the debugger, shows the unparsed program + @Override + public String toString() { + return new String(_input, _position, _input.length - _position); + } + + // True if at EOF + private boolean isEOF() { + return _position >= _input.length; + } + + // Peek next character, or report EOF + private char peek() { + return isEOF() ? Character.MAX_VALUE // Special value that causes parsing to terminate + : (char) _input[_position]; + } + + private char nextChar() { + char ch = peek(); + _position++; + return ch; + } + + // True if a white space + private boolean isWhiteSpace() { + return peek() <= ' '; // Includes all the use space, tab, newline, CR + } + + /** + * Return the next non-white-space character + */ + private void skipWhiteSpace() { + while (isWhiteSpace()) _position++; + } + + + // Return true, if we find "syntax" after skipping white space; also + // then advance the cursor past syntax. + // Return false otherwise, and do not advance the cursor. + boolean match(String syntax) { + skipWhiteSpace(); + int len = syntax.length(); + if (_position + len > _input.length) return false; + for (int i = 0; i < len; i++) + if ((char) _input[_position + i] != syntax.charAt(i)) + return false; + _position += len; + return true; + } + + boolean matchx(String syntax) { + if( !match(syntax) ) return false; + if( !isIdLetter(peek()) ) return true; + _position -= syntax.length(); + return false; + } + + private boolean peek(char ch) { + skipWhiteSpace(); + return peek()==ch; + } + + // Return an identifier or null + String matchId() { + skipWhiteSpace(); + return isIdStart(peek()) ? parseId() : null; + } + + // Used for errors + String getAnyNextToken() { + if (isEOF()) return ""; + if (isIdStart(peek())) return parseId(); + if (isPunctuation(peek())) return parsePunctuation(); + return String.valueOf(peek()); + } + + boolean isNumber() {return isNumber(peek());} + boolean isNumber(char ch) {return Character.isDigit(ch);} + + private Type parseNumber() { + int start = _position; + while (isNumber(nextChar())) ; + String snum = new String(_input, start, --_position - start); + if (snum.length() > 1 && snum.charAt(0) == '0') + throw error("Syntax error: integer values cannot start with '0'"); + return TypeInteger.constant(Long.parseLong(snum)); + } + + // First letter of an identifier + private boolean isIdStart(char ch) { + return Character.isAlphabetic(ch) || ch == '_'; + } + + // All characters of an identifier, e.g. "_x123" + private boolean isIdLetter(char ch) { + return Character.isLetterOrDigit(ch) || ch == '_'; + } + + private String parseId() { + int start = _position; + while (isIdLetter(nextChar())) ; + return new String(_input, start, --_position - start); + } + + // + private boolean isPunctuation(char ch) { + return "=;[]<>()+-/*".indexOf(ch) != -1; + } + + private String parsePunctuation() { + int start = _position; + return new String(_input, start, 1); + } + } + + public static RuntimeException TODO() { return TODO("Not yet implemented"); } + public static RuntimeException TODO(String msg) { return new RuntimeException(msg); } +} diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java new file mode 100644 index 00000000..61359d64 --- /dev/null +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -0,0 +1,154 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.*; + +public class AddNode extends Node { + public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "Add"; } + + @Override public String glabel() { return "+"; } + + @Override + StringBuilder _print1(StringBuilder sb) { + in(1)._print0(sb.append("(")); + in(2)._print0(sb.append("+")); + return sb.append(")"); + } + + + @Override + public Type compute() { + if( in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1 ) { + if (i0.isConstant() && i1.isConstant()) + return TypeInteger.constant(i0.value()+i1.value()); + return i0.meet(i1); + } + return Type.BOTTOM; + } + + @Override + public Node idealize () { + Node lhs = in(1); + Node rhs = in(2); + Type t1 = lhs._type; + Type t2 = rhs._type; + + // Already handled by peephole constant folding + assert !(t1.isConstant() && t2.isConstant()); + + // Add of 0. We do not check for (0+x) because this will already + // canonicalize to (x+0) + if( t2 instanceof TypeInteger i && i.value()==0 ) + return lhs; + + // Add of same to a multiply by 2 + if( lhs==rhs ) + return new MulNode(lhs,new ConstantNode(TypeInteger.constant(2)).peephole()); + + // Goal: a left-spine set of adds, with constants on the rhs (which then fold). + + // Move non-adds to RHS + if( !(lhs instanceof AddNode) && rhs instanceof AddNode ) + return swap12(); + + // Now we might see (add add non) or (add non non) or (add add add) but never (add non add) + + // Do we have x + (y + z) ? + // Swap to (x + y) + z + // Rotate (add add add) to remove the add on RHS + if( rhs instanceof AddNode add ) + return new AddNode(new AddNode(lhs,add.in(1)).peephole(), add.in(2)); + + // Now we might see (add add non) or (add non non) but never (add non add) nor (add add add) + if( !(lhs instanceof AddNode) ) + return spline_cmp(lhs,rhs) ? swap12() : null; + + // Now we only see (add add non) + + // Do we have (x + con1) + con2? + // Replace with (x + (con1+con2) which then fold the constants + if( lhs.in(2)._type.isConstant() && t2.isConstant() ) + return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole()); + + + // 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...) + Node phicon = phiCon(this,true); + if( phicon!=null ) return phicon; + + // Now we sort along the spline via rotates, to gather similar things together. + + // Do we rotate (x + y) + z + // into (x + z) + y ? + if( spline_cmp(lhs.in(2),rhs) ) + return new AddNode(new AddNode(lhs.in(1),rhs).peephole(),lhs.in(2)); + + return null; + } + + // Rotation is only valid for associative ops, e.g. Add, Mul, And, Or. + // Do we have ((phi cons)|(x + (phi cons)) + con|(phi cons)) ? + // Push constant up through the phi: x + (phi con0+con0 con1+con1...) + static Node phiCon(Node op, boolean rotate) { + Node lhs = op.in(1); + Node rhs = op.in(2); + // LHS is either a Phi of constants, or another op with Phi of constants + PhiNode lphi = pcon(lhs); + if( rotate && lphi==null && lhs.nIns() > 2 ) { + // Only valid to rotate constants if both are same associative ops + if( lhs.getClass() != op.getClass() ) return null; + lphi = pcon(lhs.in(2)); // Will rotate with the Phi push + } + if( lphi==null ) return null; + + // RHS is a constant or a Phi of constants + if( !(rhs instanceof ConstantNode con) && pcon(rhs)==null ) + return null; + + // If both are Phis, must be same Region + if( rhs instanceof PhiNode && lphi.in(0) != rhs.in(0) ) + return null; + + // 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. + Node[] ns = new Node[lphi.nIns()]; + ns[0] = lphi.in(0); + // Push constant up through the phi: x + (phi con0+con0 con1+con1...) + for( int i=1; i hi._nid; + } + + @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); } +} diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/BoolNode.java new file mode 100644 index 00000000..bbcc742d --- /dev/null +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -0,0 +1,58 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + +abstract public class BoolNode extends Node { + + public BoolNode(Node lhs, Node rhs) { + super(null, lhs, rhs); + } + + abstract String op(); // String opcode name + + @Override + public String label() { return getClass().getSimpleName(); } + + @Override + public String glabel() { return op(); } + + @Override + StringBuilder _print1(StringBuilder sb) { + in(1)._print0(sb.append("(")); + in(2)._print0(sb.append(op())); + return sb.append(")"); + } + + @Override + public Type compute() { + if( in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1 ) { + if (i0.isConstant() && i1.isConstant()) + return TypeInteger.constant(doOp(i0.value(), i1.value()) ? 1 : 0); + return i0.meet(i1); + } + return Type.BOTTOM; + } + + abstract boolean doOp(long lhs, long rhs); + + @Override + public Node idealize() { + // Compare of same + if( in(1)==in(2) ) + return new ConstantNode(TypeInteger.constant(doOp(3,3)?1:0)); + + // 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...) + Node phicon = AddNode.phiCon(this,false); + if( phicon!=null ) return phicon; + + return null; + } + + public static class EQNode extends BoolNode { public EQNode(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 EQNode(lhs,rhs); } } + public static class LTNode extends BoolNode { public LTNode(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 LTNode(lhs,rhs); } } + public static class LENode extends BoolNode { public LENode(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 LENode(lhs,rhs); } } +} diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/ConstantNode.java new file mode 100644 index 00000000..bc92b540 --- /dev/null +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -0,0 +1,41 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.Type; + +/** + * A Constant node represents a constant value. At present, the only constants + * that we allow are integer literals; therefore Constants contain an integer + * value. As we add other types of constants, we will refactor how we represent + * Constants. + *

+ * Constants have no semantic inputs. However, we set Start as an input to + * Constants to enable a forward graph walk. This edge carries no semantic + * meaning, and it is present solely to allow visitation. + *

+ * The Constant's value is the value stored in it. + */ +public class ConstantNode extends Node { + Type _con; + public ConstantNode( Type type ) { + super(Parser.START); + _con = type; + } + + @Override + public String label() { return "#"+_con; } + + @Override + public String uniqueName() { return "Con_" + _nid; } + + @Override + StringBuilder _print1(StringBuilder sb) { + return _con._print(sb); + } + + @Override + public Type compute() { return _con; } + + @Override + public Node idealize() { return null; } +} diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/DivNode.java new file mode 100644 index 00000000..01314c74 --- /dev/null +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -0,0 +1,37 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + +public class DivNode extends Node { + public DivNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "Div"; } + + @Override public String glabel() { return "//"; } + + @Override + StringBuilder _print1(StringBuilder sb) { + in(1)._print0(sb.append("(")); + in(2)._print0(sb.append("/")); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1) { + if (i0.isConstant() && i1.isConstant()) + return i1.value() == 0 + ? TypeInteger.ZERO + : TypeInteger.constant(i0.value()/i1.value()); + return i0.meet(i1); + } + return Type.BOTTOM; + } + + @Override + public Node idealize() { return null; } + + @Override Node copy(Node lhs, Node rhs) { return new DivNode(lhs,rhs); } +} diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java new file mode 100644 index 00000000..9e88710c --- /dev/null +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -0,0 +1,44 @@ +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() { + // If the If node is not reachable then neither is any following Proj + if (ctrl()._type != Type.CONTROL) return TypeTuple.IF_NEITHER; + // If constant is 0 then false branch is reachable + // Else true branch is reachable + if (pred()._type instanceof TypeInteger ti && ti.isConstant()) { + if (ti.value() == 0) return TypeTuple.IF_FALSE; + else return TypeTuple.IF_TRUE; + } + return TypeTuple.IF_BOTH; + } + + @Override + public Node idealize() { + return null; + } +} diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/MinusNode.java new file mode 100644 index 00000000..08924563 --- /dev/null +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -0,0 +1,28 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + +public class MinusNode extends Node { + public MinusNode(Node in) { super(null, in); } + + @Override public String label() { return "Minus"; } + + @Override public String glabel() { return "-"; } + + @Override + StringBuilder _print1(StringBuilder sb) { + in(1)._print0(sb.append("(-")); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0) + return i0.isConstant() ? TypeInteger.constant(-i0.value()) : i0; + return Type.BOTTOM; + } + + @Override + public Node idealize() { return null; } +} diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/MulNode.java new file mode 100644 index 00000000..31683a4e --- /dev/null +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -0,0 +1,56 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + +public class MulNode extends Node { + public MulNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "Mul"; } + + @Override public String glabel() { return "*"; } + + @Override + StringBuilder _print1(StringBuilder sb) { + in(1)._print0(sb.append("(")); + in(2)._print0(sb.append("*")); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1) { + if (i0.isConstant() && i1.isConstant()) + return TypeInteger.constant(i0.value()*i1.value()); + return i0.meet(i1); + } + return Type.BOTTOM; + } + + @Override + public Node idealize() { + Node lhs = in(1); + Node rhs = in(2); + Type t1 = lhs._type; + Type t2 = rhs._type; + + // Mul of 1. We do not check for (1*x) because this will already + // canonicalize to (x*1) + if ( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==1 ) + return lhs; + + // Move constants to RHS: con*arg becomes arg*con + if ( t1.isConstant() && !t2.isConstant() ) + return swap12(); + + // 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...) + Node phicon = AddNode.phiCon(this,true); + if( phicon!=null ) return phicon; + + return null; + } + @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); } +} diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/MultiNode.java new file mode 100644 index 00000000..fe3fddf8 --- /dev/null +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/MultiNode.java @@ -0,0 +1,9 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; + +public abstract class MultiNode extends Node { + + public MultiNode(Node... inputs) { super(inputs); } + +} diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java new file mode 100644 index 00000000..fd1b870c --- /dev/null +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java @@ -0,0 +1,380 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.Type; + +import java.util.*; + +/** + * All Nodes in the Sea of Nodes IR inherit from the Node class. + * The Node class provides common functionality used by all subtypes. + * Subtypes of Node specialize by overriding methods. + */ +public abstract class Node { + + /** + * Each node has a unique dense Node ID within a compilation context + * The ID is useful for debugging, for using as an offset in a bitvector, + * as well as for computing equality of nodes (to be implemented later). + */ + public final int _nid; + + /** + * Inputs to the node. These are use-def references to Nodes. + *

+ * Generally fixed length, ordered, nulls allowed, no unused trailing space. + * Ordering is required because e.g. "a/b" is different from "b/a". + * The first input (offset 0) is often a {@link #isCFG} node. + */ + public final ArrayList _inputs; + + /** + * Outputs reference Nodes that are not null and have this Node as an + * input. These nodes are users of this node, thus these are def-use + * references to Nodes. + *

+ * Outputs directly match inputs, making a directed graph that can be + * walked in either direction. These outputs are typically used for + * efficient optimizations but otherwise have no semantics meaning. + */ + public final ArrayList _outputs; + + + /** + * Current computed type for this Node. This value changes as the graph + * changes and more knowledge is gained about the program. + */ + public Type _type; + + /** + * A private Global Static mutable counter, for unique node id generation. + * To make the compiler multithreaded, this field will have to move into a TLS. + * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values. + * */ + private static int UNIQUE_ID = 1; + + protected Node(Node... inputs) { + _nid = UNIQUE_ID++; // allocate unique dense ID + _inputs = new ArrayList<>(); + Collections.addAll(_inputs,inputs); + _outputs = new ArrayList<>(); + for( Node n : _inputs ) + if( n != null ) + n.addUse( this ); + } + + // Easy reading label for debugger, e.g. "Add" or "Region" or "EQ" + public abstract String label(); + + // Unique label for graph visualization, e.g. "Add12" or "Region30" or "EQ99" + public String uniqueName() { return label() + _nid; } + + // Graphical label, e.g. "+" or "Region" or "==" + public String glabel() { return label(); } + + @Override + public final String toString() { + // TODO: This needs a lot of work + return print(); + } + + // This is a *deep* print. This version will fail on cycles, which we will + // correct later when we can parse programs with loops. We print with a + // tik-tok style; the common _print0 calls the per-Node _print1, which + // calls back to _print0; + public final String print() { + return _print0(new StringBuilder()).toString(); + } + // This is the common print: check for DEAD and print "DEAD" else call the + // per-Node print1. + final StringBuilder _print0(StringBuilder sb) { + return isDead() + ? sb.append(uniqueName()).append(":DEAD") + : _print1(sb); + } + // Every Node implements this. + abstract StringBuilder _print1(StringBuilder sb); + + + /** + * Gets the ith input node + * @param i Offset of the input node + * @return Input node or null + */ + public Node in(int i) { return _inputs.get(i); } + + public int nIns() { return _inputs.size(); } + + public int nOuts() { return _outputs.size(); } + + public boolean isUnused() { return nOuts() == 0; } + + public boolean isCFG() { return false; } + + /** + * We allow disabling peephole opt so that we can observe the + * full graph, vs the optimized graph. + */ + public static boolean _disablePeephole = false; + + /** + * Try to peephole at this node and return a better replacement Node if + * possible. We compute a {@link Type} and then check and replace: + *

    + *
  • if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}
  • + *
  • in a future chapter we will look for a + * Common Subexpression + * to eliminate.
  • + *
  • we ask the Node for a better replacement. The "better replacement" + * is things like {@code (1+2)} becomes {@code 3} and {@code (1+(x+2))} becomes + * {@code (x+(1+2))}. By canonicalizing expressions we fold common addressing + * math constants, remove algebraic identities and generally simplify the + * code.
  • + *
+ */ + public final Node peephole( ) { + // Compute initial or improved Type + Type type = _type = compute(); + + if (_disablePeephole) + return this; // Peephole optimizations turned off + + // Replace constant computations from non-constants with a constant node + if (!(this instanceof ConstantNode) && type.isConstant()) + return deadCodeElim(new ConstantNode(type).peephole()); + + // Future chapter: Global Value Numbering goes here + + // Ask each node for a better replacement + Node n = idealize(); + if( n != null ) // Something changed + // Recursively optimize + return deadCodeElim(n.peephole()); + + return this; // No progress + } + + // 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; + } + + + /** + * Change a def into a Node. Keeps the edges correct, by removing + * the corresponding use->def edge. This may make the original + * def go dead. This function is co-recursive with {@link #kill}. + *

+ + * This method is the normal path for altering a Node, because it does the + * proper default edge maintenance. It also immediately kills + * Nodes that lose their last use; at times care must be taken to avoid + * killing Nodes that are being used without having an output Node. This + * definitely happens in the middle of recursive {@link #peephole} calls. + * + * @param idx which def to set + * @param new_def the new definition + * @return this for flow coding + */ + Node set_def(int idx, Node new_def ) { + Node old_def = in(idx); + if( old_def == new_def ) return this; // No change + // If new def is not null, add the corresponding def->use edge + // This needs to happen before removing the old node's def->use edge as + // the new_def might get killed if the old node kills it recursively. + if( new_def != null ) + new_def.addUse(this); + if( old_def != null && // If the old def exists, remove a def->use edge + old_def.delUse(this) ) // If we removed the last use, the old def is now dead + old_def.kill(); // Kill old def + // Set the new_def over the old (killed) edge + _inputs.set(idx,new_def); + // Return self for easy flow-coding + return this; + } + + // Remove the numbered input, compressing the inputs in-place. This + // shuffles the order deterministically - which is suitable for Region and + // Phi, but not for every Node. + void delDef(int idx) { + Node old_def = in(idx); + if( old_def != null && // If the old def exists, remove a def->use edge + old_def.delUse(this) ) // If we removed the last use, the old def is now dead + old_def.kill(); // Kill old def + // Set the new_def over the old (killed) edge + int last = nIns()-1; + _inputs.set(idx,in(last)); + _inputs.remove(last); + } + + /** + * Add a new def to an existing Node. Keep the edges correct by + * adding the corresponding def->use edge. + * + * @param new_def the new definition, appended to the end of existing definitions + * @return new_def for flow coding + */ + Node add_def(Node new_def) { + // Add use->def edge + _inputs.add(new_def); + // If new def is not null, add the corresponding def->use edge + if( new_def != null ) + new_def.addUse(this); + return new_def; + } + + // Breaks the edge invariants, used temporarily + protected N addUse(Node n) { _outputs.add(n); return (N)this; } + // Shortcuts to stop DCE mid-parse + public N keep() { return addUse(null); } + public Node unkeep() { delUse(null); return this; } + + // Remove node 'use' from 'def's (i.e. our) output list, by compressing the list in-place. + // Return true if the output list is empty afterward. + // Error is 'use' does not exist; ok for 'use' to be null. + protected boolean delUse( Node use ) { + ArrayList outs = _outputs; + int lidx = outs.size()-1; // Last index + // This 1-line hack compresses an element out of an ArrayList + // without having to copy the contents. The last element is + // stuffed over the deleted element, and then the size is reduced. + outs.set(outs.indexOf(use),outs.get(lidx)); + outs.remove(lidx); // Reduce ArrayList size without copying anything + return lidx==0; + } + + // Shortcut for "popping" n nodes. A "pop" is basically a + // set_def(last,null) followed by lowering the nIns() count. + void pop_n(int n) { + for( int i=0; iuses, by setting all of its defs + * to null. This may recursively kill more Nodes and is basically dead + * code elimination. This function is co-recursive with {@link #pop_n}. + */ + public void kill( ) { + assert isUnused(); // Has no uses, so it is dead + pop_n(nIns()); // Set all inputs to null, recursively killing unused Nodes + _type=null; // Flag as dead + assert isDead(); // Really dead now + } + + // Mostly used for asserts and printing. + boolean isDead() { return isUnused() && nIns()==0 && _type==null; } + + /** + * This function needs to be + * Monotonic + * as it is part of a Monotone Analysis Framework. + * See for example this set of slides. + *

+ * For Chapter 2, all our Types are really integer constants, and so all + * the needed properties are trivially true, and we can ignore the high + * theory. Much later on, this will become important and allow us to do + * many fancy complex optimizations trivially... because theory. + *

+ * compute() needs to be stand-alone, and cannot recursively call compute + * on its inputs programs are cyclic (have loops!) and this will just + * infinitely recurse until stack overflow. Instead, compute typically + * computes a new type from the {@link #_type} field of its inputs. + */ + public abstract Type compute(); + + /** + * This function rewrites the current Node into a more "idealized" form. + * This is the bulk of our peephole rewrite rules, and we use this to + * e.g. turn arbitrary collections of adds and multiplies with mixed + * constants into a normal form that's easy for hardware to implement. + * Example: An array addressing expression: + *

   ary[idx+1]
+ * might turn into Sea-of-Nodes IR: + *
   (ary+12)+((idx+1) * 4)
+ * This expression can then be idealized into: + *
   ary + ((idx*4) + (12 + (1*4)))
+ * And more folding: + *
   ary + ((idx<<2) + 16)
+ * And during code-gen: + *
   MOV4 Rary,Ridx,16 // or some such hardware-specific notation 
+ *

+ * {@link #idealize} has a very specific calling convention: + *

    + *
  • If NO change is made, return {@code null} + *
  • If ANY change is made, return not-null; this can be {@code this} + *
  • The returned Node does NOT call {@link #peephole} on itself; the {@link #peephole} call will recursively peephole it. + *
  • Any NEW nodes that are not directly returned DO call {@link #peephole}. + *
+ *

+ * Examples: + * + * + * + * + * + *
before after return comment
{@code (x+5) }{@code (x+5) }{@code null }No change
{@code (5+x) }{@code (x+5) }{@code this }Swapped arguments
{@code ((x+1)+2)}{@code (x+(1+2))}{@code (x+_) }Returns 2 new Nodes
+ * + * The last entry deserves more discussion. The new Node {@code (1+2)} + * created in {@link #idealize} calls {@link #peephole} (which then folds + * into a constant). The other new Node {@code (x+3)} does not call + * peephole, because it is returned and peephole itself will recursively + * call peephole. + *

+ * Since idealize calls peephole and peephole calls idealize, you must be + * careful that all idealizations are monotonic: all transforms remove + * some feature, so that the set of available transforms always shrinks. + * If you don't, you risk an infinite peephole loop! + * + * @return Either a new or changed node, or null for no changes. + */ + public abstract Node idealize(); + + + // ----------------------- + // Peephole utilities + + // Swap inputs without letting either input go dead during the swap. + Node swap12() { + Node tmp = in(1); + _inputs.set(1,in(2)); + _inputs.set(2,tmp); + return this; + } + + // does this node contain all constants? + // Ignores in(0), as is usually control. + boolean all_cons() { + for( int i=1; i + * In this presentation, Return functions as a Stop node, since multiple return statements are not possible. + * The Stop node will be introduced in Chapter 6 when we implement if statements. + *

+ * The Return's output is the value from the data node. + */ +public class ReturnNode extends Node { + + public ReturnNode(Node ctrl, Node data) { + super(ctrl, data); + } + + public Node ctrl() { return in(0); } + public Node expr() { return in(1); } + + @Override + public String label() { return "Return"; } + + @Override + StringBuilder _print1(StringBuilder sb) { + return expr()._print0(sb.append("return ")).append(";"); + } + + @Override public boolean isCFG() { return true; } + + @Override + public Type compute() { + return new TypeTuple(ctrl()._type,expr()._type); + } + + @Override + public Node idealize() { + if( ctrl()._type==Type.XCONTROL ) + return ctrl(); + return null; + } +} diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java new file mode 100644 index 00000000..eecab9f9 --- /dev/null +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -0,0 +1,138 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.Type; + +import java.util.*; + +/** + * The Scope node is a purely parser helper - it tracks names to nodes with a + * stack of scopes. + */ +public class ScopeNode extends Node { + + /** + * Stack of lexical scopes, each scope is a symbol table + * that binds variable names to Nodes. + * The top of this stack represents current scope. + */ + public final Stack> _scopes = new Stack<>(); + + // Reverse lookup for nicer graph printing + private final ArrayList _rlabels = new ArrayList<>(); + + @Override public String label() { return "Scope"; } + + @Override + StringBuilder _print1(StringBuilder sb) { + sb.append(label()); + for( HashMap scope : _scopes ) { + sb.append("["); + boolean first=true; + for( String name : scope.keySet() ) { + if( !first ) sb.append(", "); + first=false; + sb.append(name).append(":"); + Node n = in(scope.get(name)); + if( n==null ) sb.append("null"); + else n._print0(sb); + } + sb.append("]"); + } + return sb; + } + + @Override + public Type compute() { return Type.BOTTOM; } + + @Override public Node idealize() { return null; } + + // Add an empty lexical scope + public HashMap push() { + return _scopes.push(new HashMap<>()); + } + + // Remove the current lexical scope, killing all unused nodes. + public void pop() { + HashMap scope = _scopes.pop(); + pop_n(scope.size()); + } + + // Create a new name in the current scope + public Node define( String name, Node n ) { + HashMap scope = _scopes.lastElement(); + if( scope.put(name,nIns()) != null ) + return null; // Double define + _rlabels.add(name); + return add_def(n); + } + + // Lookup a name in all scopes + public Node lookup(String name) { + for (int i = _scopes.size() - 1; i >= 0; i--) { + var idx = _scopes.get(i).get(name); + if (idx != null) return in(idx); + } + return null; + } + + public Node ctrl() { assert lookup(Parser.CTRL)==in(0); return in(0); } + + public Node ctrl(Node n) { + assert lookup(Parser.CTRL)==in(0); + set_def(0,n); + return n; + } + + + // If the name is present in any scope, then redefine + public Node update(String name, Node n) { + for (int i = _scopes.size() - 1; i >= 0; i--) { + HashMap scope = _scopes.get(i); + Integer idx = scope.get(name); + if (idx != null) // Found prior def + return set_def(idx,n); // Update def in scope + } + return null; + } + + /** + * 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). + *

+ * The new Scope is a full-fledged Node with proper use<->def edges. + */ + public ScopeNode dup() { + // 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 + ScopeNode dup = new ScopeNode(); + for( HashMap tab : _scopes ) + dup._scopes.push(new HashMap<>(tab)); + for( int i=0; isee for example this set of slides. + *

+ * The types form a lattice; @see a symmetric complete bounded (ranked) lattice. + *

+ * This wild lattice theory will be needed later to allow us to easily beef up + * the analysis and optimization of the Simple compiler... but we don't need it + * now, just know that it is coming along in a later Chapter. + *

g + * One of the fun things here is that while the theory is deep and subtle, the + * actual implementation is darn near trivial and is generally really obvious + * what we're doing with it. Right now, it's just simple integer math to do + * simple constant folding e.g. 1+2 == 3 stuff. + */ + +public class Type { + + // ---------------------------------------------------------- + // Simple types are implemented fully here. "Simple" means: the code and + // type hierarchy are simple, not that the Type is conceptually simple. + static final byte TBOT = 0; // Bottom (ALL) + static final byte TTOP = 1; // Top (ANY) + static final byte TCTRL = 2; // Ctrl flow bottom + static final byte TXCTRL = 3; // Ctrl flow top (mini-lattice: any-xctrl-ctrl-all) + static final byte TSIMPLE = 4; // End of the Simple Types + static final byte TINT = 5; // All Integers; see TypeInteger + static final byte TTUPLE = 6; // Tuples; finite collections of unrelated Types, kept in parallel + + public final byte _type; + + public boolean is_simple() { return _type < TSIMPLE; } + private static final String[] STRS = new String[]{"BOTTOM","TOP","CONTROL","~CONTROL"}; + protected Type(byte type) { _type = type; } + + public static final Type BOTTOM = new Type( TBOT ); // ALL + public static final Type TOP = new Type( TTOP ); // ANY + public static final Type CONTROL = new Type( TCTRL ); // Ctrl + public static final Type XCONTROL = new Type( TXCTRL ); // ~Ctrl + + public boolean isConstant() { return _type == TTOP || _type == TXCTRL; } + + public StringBuilder _print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;} + + public final Type meet(Type t) { + // Shortcut for the self case + if( t == this ) return this; + // Same-type is always safe in the subclasses + if( _type==t._type ) return xmeet(t); + // Reverse; xmeet 2nd arg is never "is_simple" and never equal to "this". + if( is_simple() ) return this.xmeet(t ); + if( t.is_simple() ) return t .xmeet(this); + return BOTTOM; // Mixing 2 unrelated types + } + + // Compute meet right now. Overridden in subclasses. + // Handle cases where 'this.is_simple()' and unequal to 't'. + // Subclassed xmeet calls can assert that '!t.is_simple()'. + protected Type xmeet(Type t) { + assert is_simple(); // Should be overridden in subclass + // ANY meet anything is thing; thing meet ALL is ALL + if( _type==TBOT || t._type==TTOP ) return this; + if( _type==TTOP || t._type==TBOT ) return t; + // 'this' is {TCTRL,TXCTRL} + if( !t.is_simple() ) return BOTTOM; + // 't' is {TCTRL,TXCTRL} + return _type==TCTRL || t._type==TCTRL ? CONTROL : XCONTROL; + } + + @Override + public final String toString() { + return _print(new StringBuilder()).toString(); + } +} diff --git a/chapter06/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter06/src/main/java/com/seaofnodes/simple/type/TypeInteger.java new file mode 100644 index 00000000..93f5eae3 --- /dev/null +++ b/chapter06/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -0,0 +1,63 @@ +package com.seaofnodes.simple.type; + +/** + * Integer Type + */ +public class TypeInteger extends Type { + + public final static TypeInteger TOP = new TypeInteger(false, 0); + public final static TypeInteger BOT = new TypeInteger(false, 1); + public final static TypeInteger ZERO= new TypeInteger(true, 0); + + private final boolean _is_con; + + /** + * The constant value or + * if not constant then 0=bottom, 1=top. + */ + private final long _con; + + public TypeInteger(boolean is_con, long con) { + super(TINT); + _is_con = is_con; + _con = con; + } + + public static TypeInteger constant(long con) { return new TypeInteger(true, con); } + + public boolean isTop() { return !_is_con && _con==0; } + public boolean isBot() { return !_is_con && _con==1; } + + @Override + public StringBuilder _print(StringBuilder sb) { + if (isTop()) return sb.append("IntTop"); + if (isBot()) return sb.append("IntBot"); + return sb.append(_con); + } + + @Override + public boolean isConstant() { return _is_con; } + + public long value() { return _con; } + + @Override + public Type xmeet(Type other) { + if( this==other ) return this; + if (!(other instanceof TypeInteger i)) return super.meet(other); + // BOT wins + if ( isBot() ) return this; + if ( i.isBot() ) return i ; + // TOP loses + if ( i.isTop() ) return this; + if ( isTop() ) return i ; + assert isConstant() && i.isConstant(); + return _con==i._con ? this : TypeInteger.BOT; + } + + @Override + public boolean equals( Object o ) { + if( o==this ) return true; + if( !(o instanceof TypeInteger i) ) return false; + return _con==i._con && _is_con==i._is_con; + } +} diff --git a/chapter06/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter06/src/main/java/com/seaofnodes/simple/type/TypeTuple.java new file mode 100644 index 00000000..2e6152a8 --- /dev/null +++ b/chapter06/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -0,0 +1,32 @@ +package com.seaofnodes.simple.type; + +public class TypeTuple extends Type { + + public final Type[] _types; + + public TypeTuple(Type... _types) { + super(TTUPLE); + this._types = _types; + } + + @Override + public Type xmeet(Type other) { + throw new UnsupportedOperationException("Meet on Tuple Type not yet implemented"); + } + + @Override + public StringBuilder _print(StringBuilder sb) { + sb.append("[ "); + for( Type t : _types ) + t._print(sb).append(","); + sb.setLength(sb.length()-1); + sb.append("]"); + return sb; + } + + public static final TypeTuple IF_BOTH = new TypeTuple(new Type[]{Type.CONTROL, Type.CONTROL}); + public static final TypeTuple IF_NEITHER = new TypeTuple(new Type[]{Type.XCONTROL,Type.XCONTROL}); + public static final TypeTuple IF_TRUE = new TypeTuple(new Type[]{Type.CONTROL, Type.XCONTROL}); + public static final TypeTuple IF_FALSE = new TypeTuple(new Type[]{Type.XCONTROL,Type.CONTROL}); + +} diff --git a/chapter06/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/chapter06/src/test/java/com/seaofnodes/simple/Chapter06Test.java new file mode 100644 index 00000000..801f8d3f --- /dev/null +++ b/chapter06/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -0,0 +1,795 @@ +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 Chapter06Test { + + @Test + public void testChapter6PeepholeReturn() { + Parser parser = new Parser( +""" +if( true ) return 2; +return 1; +"""); + StopNode stop = parser.parse(true); + assertEquals("return 2;", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testChapter6PeepholeRotate() { + Parser parser = new Parser( +""" +int a = 1; +if (arg) + a = 2; +return (arg < a) < 3; +"""); + StopNode stop = parser.parse(false); + assertEquals("return ((arg= j) - break; -} - -if (1) - i = i + 5; -else if (2) - i = i - 1; -else -{ - j = 0; -} \ No newline at end of file diff --git a/language/pom.xml b/language/pom.xml deleted file mode 100644 index dbb4710e..00000000 --- a/language/pom.xml +++ /dev/null @@ -1,79 +0,0 @@ - - 4.0.0 - - com.seaofnodes - simple - 1.0 - - language-grammar - jar - SeaOfNodes Demo Simple Language Grammar - - UTF-8 - 21 - 21 - 1.22 - 4.11.1 - 4.13.2 - - - - org.antlr - antlr4-runtime - ${antlr.version} - jar - compile - - - - - - - org.apache.maven.plugins - maven-compiler-plugin - 3.10.1 - - - - - - org.antlr - antlr4-maven-plugin - ${antlr.version} - - true - true - - - - generate-sources - - antlr4 - - - - - - com.khubla.antlr - antlr4test-maven-plugin - ${antlr4test-maven-plugin.version} - - false - false - program - SimpleLanguage - com.seaofnodes.simple.antlr - examples/ - - - - - test - - - - - - - diff --git a/language/src/main/antlr4/com/seaofnodes/simple/antlr/SimpleLanguage.g4 b/language/src/main/antlr4/com/seaofnodes/simple/antlr/SimpleLanguage.g4 deleted file mode 100644 index 6779e5a2..00000000 --- a/language/src/main/antlr4/com/seaofnodes/simple/antlr/SimpleLanguage.g4 +++ /dev/null @@ -1,170 +0,0 @@ -grammar SimpleLanguage; - -program - : declaration* statement+ EOF - ; - -declaration - : type IDENTIFIER ';' - ; - -type - : 'int' - ; - -statement - : 'if' '(' expression ')' statement - | 'if' '(' expression ')' statement 'else' statement - | 'while' '(' expression ')' statement - | IDENTIFIER '=' expression ';' - | '{' declaration* statement+ '}' - | 'break' ';' - ; - -expression - : primaryExpression # PrimaryExpression_ - | ('-' | '!') expression # UnaryExpression - | expression ('*' | '/' ) expression # ArithmeticOrLogicalExpression - | expression ('+' | '-') expression # ArithmeticOrLogicalExpression - | expression ('==' | '!='| '>'| '<'| '>='| '<=') expression # ComparisonExpression - | expression '&&' expression # BooleanExpression - | expression '||' expression # BooleanExpression - ; - -primaryExpression - : - | INTEGER_LITERAL - | IDENTIFIER - | '(' expression ')' - ; - -/////////////////////////////////////////////////////////////////// - -IDENTIFIER - : IDENTIFIER_NONDIGIT - ( IDENTIFIER_NONDIGIT - | DEC_DIGIT - )* - ; - -fragment -IDENTIFIER_NONDIGIT - : NON_DIGIT - | UNIVERSAL_CHARACTER_NAME - ; - -fragment -NON_DIGIT - : [a-zA-Z_] - ; - - -fragment -UNIVERSAL_CHARACTER_NAME - : '\\u' HEX_QUAD - | '\\U' HEX_QUAD HEX_QUAD - ; - -fragment -HEX_QUAD - : HEX_DIGIT HEX_DIGIT HEX_DIGIT HEX_DIGIT - ; - -// tokens char and string -CHAR_LITERAL - : '\'' - ( - ~['\\\n\r\t] - | QUOTE_ESCAPE - | ASCII_ESCAPE - | UNICODE_ESCAPE - ) '\'' - ; - -STRING_LITERAL - : '"' - ( - ~["] - | QUOTE_ESCAPE - | ASCII_ESCAPE - | UNICODE_ESCAPE - | ESC_NEWLINE - )* '"' - ; -RAW_STRING_LITERAL: 'r' RAW_STRING_CONTENT; -fragment RAW_STRING_CONTENT: '#' RAW_STRING_CONTENT '#' | '"' .*? '"'; -BYTE_LITERAL: 'b\'' (. | QUOTE_ESCAPE | BYTE_ESCAPE) '\''; - -BYTE_STRING_LITERAL: 'b"' (~["] | QUOTE_ESCAPE | BYTE_ESCAPE)* '"'; -RAW_BYTE_STRING_LITERAL: 'br' RAW_STRING_CONTENT; -fragment ASCII_ESCAPE: '\\x' OCT_DIGIT HEX_DIGIT | COMMON_ESCAPE; -fragment BYTE_ESCAPE: '\\x' HEX_DIGIT HEX_DIGIT | COMMON_ESCAPE; -fragment COMMON_ESCAPE: '\\' [nrt\\0]; -fragment UNICODE_ESCAPE - : '\\u{' HEX_DIGIT HEX_DIGIT? HEX_DIGIT? HEX_DIGIT? HEX_DIGIT? HEX_DIGIT? '}' - ; -fragment QUOTE_ESCAPE: '\\' ['"]; -fragment ESC_NEWLINE: '\\' '\n'; - -// number -INTEGER_LITERAL - : - ( - DEC_LITERAL - | BIN_LITERAL - | OCT_LITERAL - | HEX_LITERAL - ) INTEGER_SUFFIX? - ; -DEC_LITERAL: DEC_DIGIT (DEC_DIGIT | '_')*; -HEX_LITERAL: '0x' '_'* HEX_DIGIT (HEX_DIGIT | '_')*; -OCT_LITERAL: '0o' '_'* OCT_DIGIT (OCT_DIGIT | '_')*; -BIN_LITERAL: '0b' '_'* [01] [01_]*; -FLOAT_LITERAL - : DEC_LITERAL - ( - '.' DEC_LITERAL - )? FLOAT_EXPONENT? FLOAT_SUFFIX? - ; - -fragment INTEGER_SUFFIX - : 'u8' - | 'u16' - | 'u32' - | 'u64' - | 'u128' - | 'usize' - | 'i8' - | 'i16' - | 'i32' - | 'i64' - | 'i128' - | 'isize' - ; - -fragment FLOAT_SUFFIX: 'f32' | 'f64'; -fragment FLOAT_EXPONENT: [eE] [+-]? '_'* DEC_LITERAL; -fragment OCT_DIGIT: [0-7]; -fragment DEC_DIGIT: [0-9]; -fragment HEX_DIGIT: [0-9a-fA-F]; - - -WHITESPACE - : [ \t]+ - -> skip - ; - -NEWLINE - : ( '\r' '\n'? - | '\n' - ) - -> skip - ; - -LINE_COMMENT - : '//' ~[\r\n]* - -> skip - ; - - -ANY: . ; \ No newline at end of file diff --git a/pom.xml b/pom.xml index cdd5f9ca..c4e75c83 100644 --- a/pom.xml +++ b/pom.xml @@ -19,12 +19,12 @@ - language chapter01 chapter02 chapter03 chapter04 chapter05 + chapter06 -- cgit v1.2.3