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 ++++++++++++++++++------------- 1 file changed, 18 insertions(+), 13 deletions(-) (limited to 'chapter06/README.md') 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 -- cgit v1.2.3