From 0caf37adc5f8c1600f13d80aaf77361f407c9694 Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Thu, 2 May 2024 22:08:06 +0100 Subject: Documentation updates (#76) * More clearly explain why we do not have an AST in the implementation * Improve the description of type lattice. Cross reference to future chapters. * Minor update * Add lattice visual Revise the text describing meet. * minor update * Add a lattice visual to the text * Update the lattice visual. Add description of the new edges in the SoN graph --- chapter06/README.md | 31 ++++--- chapter06/docs/build-graphs.sh | 2 + chapter06/docs/lattice.gv | 64 +++++++++++++ chapter06/docs/lattice.svg | 206 +++++++++++++++++++++++++++++++++++++++++ 4 files changed, 290 insertions(+), 13 deletions(-) create mode 100644 chapter06/docs/lattice.gv create mode 100644 chapter06/docs/lattice.svg (limited to 'chapter06') diff --git a/chapter06/README.md b/chapter06/README.md index d3fe6ed9..6f7f3baa 100644 --- a/chapter06/README.md +++ b/chapter06/README.md @@ -4,11 +4,11 @@ In this chapter we do not add new language features. Our goal is to add peephole ## 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 ⊥. +We now need to extend the type system to introduce another lattice structure, in addition to the Integer sub-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" represents a live control, whereas "~Ctrl" represents a dead control. +* "INT" refers to an integer value, note that integer values have their own sub-lattice. | | ⊥ | Ctrl | ~Ctrl | T | INT | |-------|---|------|-------|-------|-----| @@ -17,11 +17,16 @@ As before we denote "top" by T and "bottom" by ⊥. | ~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" +* "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" + +The entire revised Lattice is shown below: + +![Lattice](./docs/lattice.svg) + ## Peephole of `if` @@ -33,7 +38,7 @@ As before we denote "top" by T and "bottom" by ⊥. * 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. + 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__ @@ -41,11 +46,11 @@ As before we denote "top" by T and "bottom" by ⊥. 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 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 +* 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 @@ -60,7 +65,7 @@ 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 +dead control input is simply set to `Constant(~Ctrl)`. The peephole logic in a `Phi` notices this and replaces itself with the live input. ## Discussion diff --git a/chapter06/docs/build-graphs.sh b/chapter06/docs/build-graphs.sh index 5238dbfc..44d2de3a 100644 --- a/chapter06/docs/build-graphs.sh +++ b/chapter06/docs/build-graphs.sh @@ -9,3 +9,5 @@ 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 +dot -Tsvg lattice.gv > lattice.svg + diff --git a/chapter06/docs/lattice.gv b/chapter06/docs/lattice.gv new file mode 100644 index 00000000..2cf27452 --- /dev/null +++ b/chapter06/docs/lattice.gv @@ -0,0 +1,64 @@ +digraph Lattice { + // Define nodes + splines=false; + node [shape=circle, style=filled, fillcolor=lightblue]; + nodesep=0.6; + + TOP [label="⊤"]; + BOT [label="⊥"]; + + XCTRL [label="~Ctrl"]; + CTRL [label="Ctrl"]; + + INT_TOP [label="IntTop"]; + INT_BOT [label="IntBot"]; + + INT_MIN [label="-n"]; + INT_MINDOTS [label="..." shape=none style=none]; + INT_MINUS [label="-1"]; + INT_ZERO [label="0"]; + INT_PLUS [label="1"]; + INT_MAXDOTS [label="..." shape=none style=none]; + INT_MAX [label="+n"]; + + TUPLE [label="TUPLE"]; + + // Define edges + edge [arrowhead=none]; + + TOP -> INT_TOP; + INT_TOP -> INT_MIN; + INT_TOP -> INT_MINDOTS; + INT_TOP -> INT_MINUS; + INT_TOP -> INT_ZERO; + INT_TOP -> INT_PLUS; + INT_TOP -> INT_MAXDOTS; + INT_TOP -> INT_MAX; + INT_MIN -> INT_BOT; + INT_MINDOTS -> INT_BOT; + INT_MINUS -> INT_BOT; + INT_ZERO -> INT_BOT; + INT_PLUS -> INT_BOT; + INT_MAXDOTS -> INT_BOT; + INT_MAX -> INT_BOT; + INT_BOT -> BOT; + + INT_MIN -> INT_MINDOTS -> INT_MINUS -> INT_ZERO -> INT_PLUS -> INT_MAXDOTS -> INT_MAX [style=invis]; + + TOP -> TUPLE; + TUPLE -> BOT; + + TOP -> XCTRL; + XCTRL -> CTRL; + CTRL -> BOT; + + // Additional customization + {rank=same; TOP} + {rank=same; INT_TOP; XCTRL} + {rank=same; INT_MIN; INT_MINDOTS; + INT_MINUS; INT_ZERO; + INT_PLUS; INT_MAXDOTS; + INT_MAX; TUPLE} + {rank=same; INT_BOT; CTRL} + {rank=same; BOT;} +} \ No newline at end of file diff --git a/chapter06/docs/lattice.svg b/chapter06/docs/lattice.svg new file mode 100644 index 00000000..713b54c1 --- /dev/null +++ b/chapter06/docs/lattice.svg @@ -0,0 +1,206 @@ + + + + + + +Lattice + + + +TOP + +⊤ + + + +XCTRL + +~Ctrl + + + +TOP->XCTRL + + + + +INT_TOP + +IntTop + + + +TOP->INT_TOP + + + + +TUPLE + +TUPLE + + + +TOP->TUPLE + + + + +BOT + +⊥ + + + +CTRL + +Ctrl + + + +XCTRL->CTRL + + + + +CTRL->BOT + + + + +INT_MIN + +-n + + + +INT_TOP->INT_MIN + + + + +INT_MINDOTS +... + + + +INT_TOP->INT_MINDOTS + + + + +INT_MINUS + +-1 + + + +INT_TOP->INT_MINUS + + + + +INT_ZERO + +0 + + + +INT_TOP->INT_ZERO + + + + +INT_PLUS + +1 + + + +INT_TOP->INT_PLUS + + + + +INT_MAXDOTS +... + + + +INT_TOP->INT_MAXDOTS + + + + +INT_MAX + ++n + + + +INT_TOP->INT_MAX + + + + +INT_BOT + +IntBot + + + +INT_BOT->BOT + + + + +INT_MIN->INT_BOT + + + + + +INT_MINDOTS->INT_BOT + + + + + +INT_MINUS->INT_BOT + + + + + +INT_ZERO->INT_BOT + + + + + +INT_PLUS->INT_BOT + + + + + +INT_MAXDOTS->INT_BOT + + + + + +INT_MAX->INT_BOT + + + + +TUPLE->BOT + + + + -- cgit v1.2.3