From e31c37890a86aedfb209cf543baf05b1b60a27d2 Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Mon, 29 Apr 2024 00:11:36 +0100 Subject: Ch10update (#75) * Store-after-Store peep * Load-after-Store peephole * Fix graph viz mem edge color bug * Scalar replace loop carried dependence * #67 Dead Not node hanging around - if we add a Not in the upcast then add it to the IterPeeps worklist to ensure it gets cleaned up. We don't see the Not node in the parser hence we cannot do a peep on it there. * #67 Update visuals. Add description of Store-Store and Store-Load peeps. Add examples. * #67 Undo the change that wasn't supposed to be committed! * #67 Update description of the Store-Store and Store-Load peepholes --------- Co-authored-by: Cliff Click --- chapter10/README.md | 45 +++++++++++++++++++++++++++++++++++++++------ 1 file changed, 39 insertions(+), 6 deletions(-) (limited to 'chapter10/README.md') diff --git a/chapter10/README.md b/chapter10/README.md index c4045513..a25ff011 100644 --- a/chapter10/README.md +++ b/chapter10/README.md @@ -254,12 +254,7 @@ To enable this behaviour, we make following enhancements. ptr. When the input is a `null` we convert to `1` and when is a not `null` ptr value, we convert to `0`. See `NotNode.compute()`. - -## Examples - -We now look at some examples. - -### Example 1 +## Memory Operations Example This is a simple example illustrating how loads and stores are ordered based on aliasing. @@ -279,6 +274,44 @@ The graph from above will have the shape: ![Graph1](./docs/example1.svg) +## Additional Peephole Optimizations + +The equivalence aliasing makes it possible to optimize following scenarios: + +* Store followed by another Store to the same field inside an object; the first Store is redundant if there are no other references to the first Store +* Load followed by a Store to a field inside an Object; the Load can be eliminated and the input value of the Store passed through. + +Both of these examples are illustrated in the example below: + +```java +struct Bar { + int a; + int b; +} +struct Foo { + int x; +} +Foo? foo = null; +Bar bar = new Bar; +bar.a = 1; +bar.a = 2; +return bar.a; +``` + +Before the peephole optimizations, we get: + +![Graph2a](./docs/example2a.svg) + +After enabling Store-Store peephole we get: + +![Graph2b](./docs/example2b.svg) + +After load-after-store elision: + +![Graph2c](./docs/example2c.svg) + +Note that at this stage the `bar` object is dead therefore the allocation of bar can be dropped. + [^1]: Diwan A., McKinley K.S., Moss J.E.B. (1998). Type Based Alias Analysis. \ No newline at end of file -- cgit v1.2.3