From 10ed01188f78e3fad4b257a0241f9a89e2fdb405 Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Sun, 22 Oct 2023 05:18:58 +0100 Subject: Revision of docs (#10) * Port updates back to chapter 2 * Update older visuals to match new format * Update older visuals to match new format * update docs --- chapter02/README.md | 12 +- chapter02/docs/02-post-peephole-ex1.gv | 19 +- chapter02/docs/02-post-peephole-ex1.svg | 92 +++---- chapter02/docs/02-pre-peephole-ex1.gv | 53 ++-- chapter02/docs/02-pre-peephole-ex1.svg | 299 ++++++++++----------- .../com/seaofnodes/simple/GraphVisualizer.java | 107 ++++---- .../java/com/seaofnodes/simple/Chapter02Test.java | 6 +- 7 files changed, 295 insertions(+), 293 deletions(-) (limited to 'chapter02') diff --git a/chapter02/README.md b/chapter02/README.md index 5b4c4958..b89a3059 100644 --- a/chapter02/README.md +++ b/chapter02/README.md @@ -11,7 +11,7 @@ Here is the [complete language grammar](docs/02-grammar.md) for this chapter. ## Extensions to Intermediate Representation -In chapter 1 we introduced following nodes. +In [Chapter 1](../chapter01/README.md) we introduced following nodes. | Node Name | Type | Description | Inputs | Value | |-----------|---------|------------------------------------|------------------------------------------------------------------|-------------------------------------------------------| @@ -53,10 +53,10 @@ may *kill* the unused constants `1` and `2`. ## Constant Folding and Constant Propagation In this chapter and next we focus on a particular peephole optimization: -constant folding and constant propagation. Since we do not have variables -until Chapter 3, the main feature we demonstrate now is constant folding. +constant folding and constant propagation. Since we do not have non-constant values +until [Chapter 4](../chapter04/README.md), the main feature we demonstrate now is constant folding. However, we introduce some additional ideas into the compiler at this stage, to -set the scene for Chapter 3. +set the scene for Chapter 4. It is useful for the compiler to know at various points of the program whether a node's value is a constant. The compiler can use this knowledge to perform various @@ -107,8 +107,8 @@ some constant to ⊥. In later chapters we will explore extending this lattice, as it frequently forms the heart of core optimizations we want our compiler to do. -There are other important properties of the Lattice that we discuss in Chapter -3, such as the "meet" operator and its rules. +There are other important properties of the Lattice that we discuss in [Chapter +4](../chapter04/README.md), such as the "meet" operator and its rules. ## Nodes Pre Peephole Optimization diff --git a/chapter02/docs/02-post-peephole-ex1.gv b/chapter02/docs/02-post-peephole-ex1.gv index a39d602b..290a1178 100644 --- a/chapter02/docs/02-post-peephole-ex1.gv +++ b/chapter02/docs/02-post-peephole-ex1.gv @@ -1,10 +1,11 @@ -digraph chapter02 -{ - Start1 [shape=box, label="Start"]; - Con213 [ label="Con2"]; - Start1 -> Con213 [style=dotted]; - Return14 [shape=box, label="Return"]; - Con213 -> Return14; - edge [color=red]; - Start1 -> Return14; +digraph chapter02 { + rankdir=BT; + subgraph cluster_Nodes { + Start1 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con213 [ label="Con2" ]; + Return14 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + Con213 -> Start1 [style=dotted]; + Return14 -> Start1 [color=red]; + Return14 -> Con213; } \ No newline at end of file diff --git a/chapter02/docs/02-post-peephole-ex1.svg b/chapter02/docs/02-post-peephole-ex1.svg index 33aa5a95..b3c42c7d 100644 --- a/chapter02/docs/02-post-peephole-ex1.svg +++ b/chapter02/docs/02-post-peephole-ex1.svg @@ -1,51 +1,53 @@ + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> - - - chapter02 - - - - Start1 - - Start - - - - Con213 - - Con2 - - - - Start1->Con213 - - - - - - Return14 - - Return - - - - Start1->Return14 - - - - - - Con213->Return14 - - - - + + +chapter02 + + +cluster_Nodes + + + + +Start1 + +Start + + + +Con213 + +Con2 + + + +Con213->Start1 + + + + + +Return14 + +Return + + + +Return14->Start1 + + + + + +Return14->Con213 + + + + diff --git a/chapter02/docs/02-pre-peephole-ex1.gv b/chapter02/docs/02-pre-peephole-ex1.gv index d5a16616..c2eab457 100644 --- a/chapter02/docs/02-pre-peephole-ex1.gv +++ b/chapter02/docs/02-pre-peephole-ex1.gv @@ -1,27 +1,28 @@ -digraph chapter02 -{ - Start1 [shape=box, label="Start"]; - Con12 [ label="Con1"]; - Start1 -> Con12 [style=dotted]; - Con23 [ label="Con2"]; - Start1 -> Con23 [style=dotted]; - Con34 [ label="Con3"]; - Start1 -> Con34 [style=dotted]; - Mul5 [ label="Mul"]; - Con23 -> Mul5; - Con34 -> Mul5; - Con56 [ label="Con5"]; - Start1 -> Con56 [style=dotted]; - Minus7 [ label="Minus"]; - Con56 -> Minus7; - Add8 [ label="Add"]; - Mul5 -> Add8; - Minus7 -> Add8; - Add9 [ label="Add"]; - Con12 -> Add9; - Add8 -> Add9; - Return10 [shape=box, label="Return"]; - Add9 -> Return10; - edge [color=red]; - Start1 -> Return10; +digraph chapter02 { + rankdir=BT; + subgraph cluster_Nodes { + Start1 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con12 [ label="Con1" ]; + Con23 [ label="Con2" ]; + Con34 [ label="Con3" ]; + Mul5 [ label="Mul" ]; + Con56 [ label="Con5" ]; + Minus7 [ label="Minus" ]; + Add8 [ label="Add" ]; + Add9 [ label="Add" ]; + Return10 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + Con12 -> Start1 [style=dotted]; + Con23 -> Start1 [style=dotted]; + Con34 -> Start1 [style=dotted]; + Mul5 -> Con23; + Mul5 -> Con34; + Con56 -> Start1 [style=dotted]; + Minus7 -> Con56; + Add8 -> Mul5; + Add8 -> Minus7; + Add9 -> Con12; + Add9 -> Add8; + Return10 -> Start1 [color=red]; + Return10 -> Add9; } \ No newline at end of file diff --git a/chapter02/docs/02-pre-peephole-ex1.svg b/chapter02/docs/02-pre-peephole-ex1.svg index dc33c7f5..8a1ef457 100644 --- a/chapter02/docs/02-pre-peephole-ex1.svg +++ b/chapter02/docs/02-pre-peephole-ex1.svg @@ -1,156 +1,155 @@ + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> - - - chapter02 - - - - Start1 - - Start - - - - Con12 - - Con1 - - - - Start1->Con12 - - - - - - Con23 - - Con2 - - - - Start1->Con23 - - - - - - Con34 - - Con3 - - - - Start1->Con34 - - - - - - Con56 - - Con5 - - - - Start1->Con56 - - - - - - Return10 - - Return - - - - Start1->Return10 - - - - - - Add9 - - Add - - - - Con12->Add9 - - - - - - Mul5 - - Mul - - - - Con23->Mul5 - - - - - - Con34->Mul5 - - - - - - Add8 - - Add - - - - Mul5->Add8 - - - - - - Minus7 - - Minus - - - - Con56->Minus7 - - - - - - Minus7->Add8 - - - - - - Add8->Add9 - - - - - - Add9->Return10 - - - - + + +chapter02 + + +cluster_Nodes + + + + +Start1 + +Start + + + +Con12 + +Con1 + + + +Con12->Start1 + + + + + +Con23 + +Con2 + + + +Con23->Start1 + + + + + +Con34 + +Con3 + + + +Con34->Start1 + + + + + +Mul5 + +Mul + + + +Mul5->Con23 + + + + + +Mul5->Con34 + + + + + +Con56 + +Con5 + + + +Con56->Start1 + + + + + +Minus7 + +Minus + + + +Minus7->Con56 + + + + + +Add8 + +Add + + + +Add8->Mul5 + + + + + +Add8->Minus7 + + + + + +Add9 + +Add + + + +Add9->Con12 + + + + + +Add9->Add8 + + + + + +Return10 + +Return + + + +Return10->Start1 + + + + + +Return10->Add9 + + + + diff --git a/chapter02/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter02/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index d2aa8179..1af19d80 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -5,9 +5,7 @@ import com.seaofnodes.simple.node.Control; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.StartNode; -import java.util.Collection; -import java.util.HashMap; -import java.util.Map; +import java.util.*; /** * Simple visualizer that outputs GraphViz dot format. @@ -16,59 +14,59 @@ import java.util.Map; */ public class GraphVisualizer { - public String generateDotOutput(StartNode start) { + 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(start); + Collection all = findAll(parser); StringBuilder sb = new StringBuilder(); - sb.append("digraph chapter02\n" + - "{\n"); + sb.append("digraph chapter02 {\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 + + // Just the Nodes first, in a cluster no edges + nodes(sb, all); + + // Walk the Node edges + nodeEdges(sb, all); + + 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) { - sb.append('\t').append(n.uniqueName()); + sb.append("\t\t").append(n.uniqueName()).append(" [ "); // control nodes have box shape // other nodes are ellipses, i.e. default shape if (n instanceof Control) - sb.append(" [shape=box, "); - else - sb.append(" ["); - sb.append(" label=\"") - .append(n.label()) - .append("\"];\n"); - // Output the non control edges - walkIns(sb, n, false); + sb.append("shape=box style=filled fillcolor=yellow "); + sb.append("label=\"").append(n.label()).append("\" "); + sb.append("];\n"); } - // Now output the control edges which must be in red - sb.append("\tedge [color=red];\n"); - for (Node n : all) { - walkIns(sb, n, true); - } - sb.append("}\n"); - return sb.toString(); + sb.append("\t}\n"); // End Node cluster } - /** - * Outputs edges. If doControlEdges is true then - * edges between control nodes are output. Else other edges - * output. - */ - private void walkIns(StringBuilder sb, Node in, boolean doControlEdges) { - for (int i = 0; i < in.nIns(); i++) { - Node out = in.in(i); - if (out == null) - continue; - boolean isControlEdge = (out instanceof Control) && (in instanceof Control); - if (doControlEdges && !isControlEdge) - continue; - if (!doControlEdges && isControlEdge) - continue; - sb.append('\t') - .append(out.uniqueName()) - .append(" -> ") - .append(in.uniqueName()); - // the edge from start node to constants is just for convenience so - // show it differently - if ((out instanceof StartNode) && (in instanceof ConstantNode)) + + // Walk the node edges + private void nodeEdges(StringBuilder sb, Collection all) { + for( Node n : all ) + for( Node out : n._inputs ) + if( out != null ) { + sb.append('\t').append(n.uniqueName()).append(" -> ").append(out.uniqueName()); + // Control edges are colored red + if( n instanceof ConstantNode && out instanceof StartNode ) sb.append(" [style=dotted]"); + else if( n instanceof Control && out instanceof Control ) + sb.append(" [color=red]"); sb.append(";\n"); } } @@ -77,26 +75,25 @@ public class GraphVisualizer { * Walks the whole graph, starting from Start. * Since Start is the input to all constants - we look at the outputs for * Start, but for then subsequently we look at the inputs of each node. + * During graph construction not all nodes are reachable this way, so we + * also scan the symbol tables. */ - private Collection findAll(StartNode start) { - Map all = new HashMap<>(); - for (int i = 0; i < start.nOuts(); i++) { - Node n = start.out(i); + private Collection findAll(Parser parser) { + final StartNode start = Parser.START; + final HashMap all = new HashMap<>(); + for( Node n : start._outputs ) walk(all, n); - } return all.values(); } /** - * Walk a subgraph and populate distinct nodes in the _all list. + * Walk a subgraph and populate distinct nodes in the all list. */ - private void walk(Map all, Node n) { - if (all.get(n._nid) == null) { - // Not yet seen + private void walk(HashMap all, Node n) { + 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); - } } } diff --git a/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java index 846aff58..83cd7a0f 100644 --- a/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java +++ b/chapter02/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -24,7 +24,7 @@ public class Chapter02Test { ReturnNode ret = parser.parse(); assertEquals("return (1+((2*3)+(-5)));", ret.print()); GraphVisualizer gv = new GraphVisualizer(); - System.out.println(gv.generateDotOutput(Parser.START)); + System.out.println(gv.generateDotOutput(parser)); Node._disablePeephole = false; } @@ -69,13 +69,15 @@ public class Chapter02Test { ReturnNode ret = parser.parse(); assertEquals("return 2;", ret.print()); GraphVisualizer gv = new GraphVisualizer(); - System.out.println(gv.generateDotOutput(Parser.START)); + System.out.println(gv.generateDotOutput(parser)); } @Test public void testSimpleProgram() { Parser parser = new Parser("return 1;"); ReturnNode ret = parser.parse(); + GraphVisualizer gv = new GraphVisualizer(); + System.out.println(gv.generateDotOutput(parser)); StartNode start = Parser.START; assertEquals(start, ret.ctrl()); -- cgit v1.2.3