From b33647231e20e2dc155beb2c8fe721f952d67a54 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 2 Oct 2026 14:40:54 -0700 Subject: ch10a README --- chapter10a/README.md | 26 ++++++- chapter10a/docs/load-after-store-after.json | 20 +++++ chapter10a/docs/load-after-store-after.svg | 101 +++++++++++++++++++++++++ chapter10a/docs/load-after-store-before.json | 21 ++++++ chapter10a/docs/load-after-store-before.svg | 107 +++++++++++++++++++++++++++ 5 files changed, 271 insertions(+), 4 deletions(-) create mode 100644 chapter10a/docs/load-after-store-after.json create mode 100644 chapter10a/docs/load-after-store-after.svg create mode 100644 chapter10a/docs/load-after-store-before.json create mode 100644 chapter10a/docs/load-after-store-before.svg (limited to 'chapter10a') diff --git a/chapter10a/README.md b/chapter10a/README.md index 6f51df28..968180b5 100644 --- a/chapter10a/README.md +++ b/chapter10a/README.md @@ -271,10 +271,28 @@ To enable this behaviour, we make the following enhancements. ## Local memory optimizations A load immediately following a store to the **same pointer and field** can use -the stored value. A store immediately following another store to the same -address can discard the earlier store when no other user needs it. Both the -pointer and field checks matter: two different fields of one object are -different addresses, as are the same fields of two different objects. +the stored value. We just wrote `arg` into `p.x`, so reading it back needs no +memory access: + +```java +struct Box { int x; } +Box p = new Box; +p.x = arg; +return p.x; // Can return arg directly. +``` + +| Before: read back the stored value | After: use the value directly | +|---|---| +| ![Before: Return reads Load p.x after Store p.x](docs/load-after-store-before.svg) | ![After: Return uses arg and still consumes the Store's memory](docs/load-after-store-after.svg) | + +Return's result input changes from the Load to `arg`, and the unused Load +disappears. Return still consumes the Store's memory, so the write is retained. + +A store immediately following another store to the same address can also +discard the earlier store when no other user needs it. That separate rewrite +can remove the zero-initialization store still shown above. Both the pointer +and field checks matter: two different fields of one object are different +addresses, as are the same fields of two different objects. A load can also move up through a memory Phi. This extends [Chapter 5's push-through-Phi optimization](../chapter05/README.md#pushing-addition-up-through-a-phi): diff --git a/chapter10a/docs/load-after-store-after.json b/chapter10a/docs/load-after-store-after.json new file mode 100644 index 00000000..0f0d3a93 --- /dev/null +++ b/chapter10a/docs/load-after-store-after.json @@ -0,0 +1,20 @@ +{ + "ver": 1, + "comp": "load-after-store-after", + "step": 1, + "roots": [10], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 2, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}], "proj": {"par": 1, "idx": 0}}, + {"id": 3, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 1, "role": "MEM", "label": null}], "proj": {"par": 1, "idx": 1}}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "DATA", "label": null}], "proj": {"par": 1, "idx": 2}}, + {"id": 5, "label": "new Box", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": null}, + {"id": 6, "label": "#0", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 7, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 4, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/chapter10a/docs/load-after-store-after.svg b/chapter10a/docs/load-after-store-after.svg new file mode 100644 index 00000000..ee6d8189 --- /dev/null +++ b/chapter10a/docs/load-after-store-after.svg @@ -0,0 +1,101 @@ +#5[0] → #2 · CTRL#6[0] → #1 · ASSOC#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #6 · DATA#8[1] → #7 · MEM#8[2] → #5 · DATA#8[3] → #4 · DATA#10[0] → #2 · CTRL#10[1] → #8 · MEM#10[2] → #4 · DATAStart  #1#1 Start +Type not computed + +$ctrl  #2/0#2 $ctrl +Projection 0 of #1 +Type not computed + +[0] → #1 CTRL$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMarg  #4/2#4 arg +Projection 2 of #1 +Type not computed + +[0] → #1 DATAnew Box  #5#5 new Box +Type not computed + +[0] → #2 CTRL0#0  #6#6 #0 +Type not computed + +[0] → #1 ASSOC0Store p.x  #7#7 Store p.x +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Store p.x  #8#8 Store p.x +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #4 DATA0123Return  #10#10 Return +Type not computed + +[0] → #2 CTRL +[1] → #8 MEM +[2] → #4 DATA012 diff --git a/chapter10a/docs/load-after-store-before.json b/chapter10a/docs/load-after-store-before.json new file mode 100644 index 00000000..5a15a4e4 --- /dev/null +++ b/chapter10a/docs/load-after-store-before.json @@ -0,0 +1,21 @@ +{ + "ver": 1, + "comp": "load-after-store-before", + "step": 1, + "roots": [10], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 2, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}], "proj": {"par": 1, "idx": 0}}, + {"id": 3, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 1, "role": "MEM", "label": null}], "proj": {"par": 1, "idx": 1}}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "DATA", "label": null}], "proj": {"par": 1, "idx": 2}}, + {"id": 5, "label": "new Box", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": null}, + {"id": 6, "label": "#0", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 7, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "Load p.x", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 0, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/chapter10a/docs/load-after-store-before.svg b/chapter10a/docs/load-after-store-before.svg new file mode 100644 index 00000000..cdb152e3 --- /dev/null +++ b/chapter10a/docs/load-after-store-before.svg @@ -0,0 +1,107 @@ +#5[0] → #2 · CTRL#6[0] → #1 · ASSOC#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #6 · DATA#8[1] → #7 · MEM#8[2] → #5 · DATA#8[3] → #4 · DATA#9[1] → #8 · MEM#9[2] → #5 · DATA#10[0] → #2 · CTRL#10[1] → #8 · MEM#10[2] → #9 · DATAStart  #1#1 Start +Type not computed + +$ctrl  #2/0#2 $ctrl +Projection 0 of #1 +Type not computed + +[0] → #1 CTRL$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMarg  #4/2#4 arg +Projection 2 of #1 +Type not computed + +[0] → #1 DATAnew Box  #5#5 new Box +Type not computed + +[0] → #2 CTRL0#0  #6#6 #0 +Type not computed + +[0] → #1 ASSOC0Store p.x  #7#7 Store p.x +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Store p.x  #8#8 Store p.x +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #4 DATA0123Load p.x  #9#9 Load p.x +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → — DATA0123Return  #10#10 Return +Type not computed + +[0] → #2 CTRL +[1] → #8 MEM +[2] → #9 DATA012 -- cgit v1.2.3