From fa7d56f72455828826d0ab7e1c142ca814e6e2aa Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 29 Sep 2026 10:10:53 -0700 Subject: Reverse edges --- chapter10a/README.md | 4 +- chapter10a/docs/example1.gv | 4 +- chapter10a/docs/example1.svg | 64 ++++++++++---------- chapter10a/docs/example2a.gv | 4 +- chapter10a/docs/example2a.svg | 92 ++++++++++++++-------------- chapter10a/docs/example2b.gv | 4 +- chapter10a/docs/example2b.svg | 80 ++++++++++++------------- chapter10a/docs/example2c.gv | 4 +- chapter10a/docs/example2c.svg | 46 +++++++------- chapter10b/README.md | 2 +- chapter10b/docs/example1.gv | 6 +- chapter10b/docs/example1.svg | 84 +++++++++++++------------- chapter10b/docs/example2a.gv | 6 +- chapter10b/docs/example2a.svg | 82 ++++++++++++------------- chapter10b/docs/example2b.gv | 8 +-- chapter10b/docs/example2b.svg | 136 +++++++++++++++++++++--------------------- chapter10b/docs/example2c.gv | 4 +- chapter10b/docs/example2c.svg | 50 ++++++++-------- 18 files changed, 340 insertions(+), 340 deletions(-) diff --git a/chapter10a/README.md b/chapter10a/README.md index 30db40d3..64600fa0 100644 --- a/chapter10a/README.md +++ b/chapter10a/README.md @@ -30,8 +30,8 @@ different fields are independent. Chapter 10b will remove it. ![One chain orders stores and loads](docs/example1.svg) -These diagrams are schematic dependency graphs: arrows run from definitions to -uses. Pointer and value inputs are omitted where they do not explain ordering. +These diagrams are schematic dependency graphs: arrows run from uses to their +definitions. Pointer and value inputs are omitted where they do not explain ordering. | Node | Inputs | Result | |---|---|---| diff --git a/chapter10a/docs/example1.gv b/chapter10a/docs/example1.gv index 38214174..e34c73ed 100644 --- a/chapter10a/docs/example1.gv +++ b/chapter10a/docs/example1.gv @@ -5,6 +5,6 @@ digraph Memory { X [label="Store p.x = 3"]; Y [label="Store p.y = arg"]; L [label="Load p.x"]; - M0 -> X -> Y -> L [color=blue]; - Y -> Return [color=blue]; L -> Return; + L -> Y -> X -> M0 [color=blue]; + Return -> Y [color=blue]; Return -> L; } diff --git a/chapter10a/docs/example1.svg b/chapter10a/docs/example1.svg index 7ae4b560..c0668ce3 100644 --- a/chapter10a/docs/example1.svg +++ b/chapter10a/docs/example1.svg @@ -12,62 +12,62 @@ M0 - -Initial memory + +Initial memory X - -Store p.x = 3 + +Store p.x = 3 - - -M0->X - - + + +X->M0 + + Y - -Store p.y = arg + +Store p.y = arg - + -X->Y - - +Y->X + + L - -Load p.x + +Load p.x - - -Y->L - - + + +L->Y + + Return - -Return + +Return - + -Y->Return - - +Return->Y + + - + -L->Return - - +Return->L + + diff --git a/chapter10a/docs/example2a.gv b/chapter10a/docs/example2a.gv index 13fd75e0..64e774fc 100644 --- a/chapter10a/docs/example2a.gv +++ b/chapter10a/docs/example2a.gv @@ -5,6 +5,6 @@ digraph Memory { A [label="True: Store x"]; B [label="False: Store y"]; P [label="Phi(memory)"]; - M -> A -> P [color=blue]; M -> B -> P [color=blue]; - Region -> P [style=dashed]; P -> Return [color=blue]; + P -> A -> M [color=blue]; P -> B -> M [color=blue]; + P -> Region [style=dashed]; Return -> P [color=blue]; } diff --git a/chapter10a/docs/example2a.svg b/chapter10a/docs/example2a.svg index 1752659e..c6801f59 100644 --- a/chapter10a/docs/example2a.svg +++ b/chapter10a/docs/example2a.svg @@ -12,74 +12,74 @@ M - -Incoming memory + +Incoming memory A - -True: Store x + +True: Store x - - -M->A - - + + +A->M + + B - -False: Store y + +False: Store y - - -M->B - - + + +B->M + + P - -Phi(memory) - - - -A->P - - - - - -B->P - - + +Phi(memory) - - -Return - -Return + + +P->A + + - - -P->Return - - + + +P->B + + Region - -Region + +Region - + -Region->P - - +P->Region + + + + + +Return + +Return + + + +Return->P + + diff --git a/chapter10a/docs/example2b.gv b/chapter10a/docs/example2b.gv index 9db0f5fb..7ccbcc99 100644 --- a/chapter10a/docs/example2b.gv +++ b/chapter10a/docs/example2b.gv @@ -3,6 +3,6 @@ digraph Memory { node [shape=box]; P [label="Phi(memory)"]; S [label="Loop-body Store"]; - Entry -> P [color=blue]; P -> S -> P [color=blue]; - Loop -> P [style=dashed]; P -> Return [color=blue]; + P -> Entry [color=blue]; P -> S -> P [color=blue]; + P -> Loop [style=dashed]; Return -> P [color=blue]; } diff --git a/chapter10a/docs/example2b.svg b/chapter10a/docs/example2b.svg index 1f106d63..063a6f21 100644 --- a/chapter10a/docs/example2b.svg +++ b/chapter10a/docs/example2b.svg @@ -4,70 +4,70 @@ - - + + Memory - + P - -Phi(memory) + +Phi(memory) S - -Loop-body Store + +Loop-body Store P->S - - - - - -Return - -Return - - - -P->Return - - - - - -S->P - - + + Entry - -Entry + +Entry - + -Entry->P - - +P->Entry + + Loop - -Loop + +Loop - + -Loop->P - - +P->Loop + + + + + +S->P + + + + + +Return + +Return + + + +Return->P + + diff --git a/chapter10a/docs/example2c.gv b/chapter10a/docs/example2c.gv index 0a9f0462..0c7cf67d 100644 --- a/chapter10a/docs/example2c.gv +++ b/chapter10a/docs/example2c.gv @@ -4,6 +4,6 @@ digraph Memory { M [label="Prior memory"]; L [label="Load p.x"]; S [label="Store p.x"]; - M -> L [color=blue]; M -> S [color=blue]; - L -> S [style=dashed,label="execute load first"]; + L -> M [color=blue]; S -> M [color=blue]; + S -> L [style=dashed,label="execute load first"]; } diff --git a/chapter10a/docs/example2c.svg b/chapter10a/docs/example2c.svg index 90f90920..a4d2f53e 100644 --- a/chapter10a/docs/example2c.svg +++ b/chapter10a/docs/example2c.svg @@ -4,47 +4,47 @@ - - + + Memory - + M - -Prior memory + +Prior memory L - -Load p.x + +Load p.x - + -M->L - - +L->M + + S - -Store p.x + +Store p.x - + -M->S - - +S->M + + - + -L->S - - -execute load first +S->L + + +execute load first diff --git a/chapter10b/README.md b/chapter10b/README.md index d90a9da7..1779be50 100644 --- a/chapter10b/README.md +++ b/chapter10b/README.md @@ -27,7 +27,7 @@ load-after-store forwarding turn the return value into 42. ![Independent field dependencies](docs/example1.svg) -These are schematic dependency graphs, with arrows from definitions to uses. +These are schematic dependency graphs, with arrows from uses to their definitions. Control, pointer, and value edges are omitted when they do not explain memory. ## Equivalence-class aliasing diff --git a/chapter10b/docs/example1.gv b/chapter10b/docs/example1.gv index d1b2d456..2194ae8f 100644 --- a/chapter10b/docs/example1.gv +++ b/chapter10b/docs/example1.gv @@ -5,7 +5,7 @@ digraph Memory { X [label="Store x = 42"]; Y [label="Loop: Store y"]; L [label="Load x -> 42"]; - M -> X -> L [color=blue]; M -> Y [color=green]; - X -> MemMerge [color=blue]; Y -> MemMerge [color=green]; - MemMerge -> Return; L -> Return; + L -> X -> M [color=blue]; Y -> M [color=green]; + MemMerge -> X [color=blue]; MemMerge -> Y [color=green]; + Return -> MemMerge; Return -> L; } diff --git a/chapter10b/docs/example1.svg b/chapter10b/docs/example1.svg index bcd2a221..c441bc7b 100644 --- a/chapter10b/docs/example1.svg +++ b/chapter10b/docs/example1.svg @@ -12,80 +12,80 @@ M - -Initial memory + +Initial memory X - -Store x = 42 + +Store x = 42 - - -M->X - - + + +X->M + + Y - -Loop: Store y + +Loop: Store y - + -M->Y - - +Y->M + + L - -Load x -> 42 + +Load x -> 42 - - -X->L - - + + +L->X + + MemMerge - -MemMerge + +MemMerge - + -X->MemMerge - - +MemMerge->X + + - + -Y->MemMerge - - +MemMerge->Y + + Return - -Return + +Return - + -L->Return - - +Return->L + + - + -MemMerge->Return - - +Return->MemMerge + + diff --git a/chapter10b/docs/example2a.gv b/chapter10b/docs/example2a.gv index 50f7ec80..c2db6771 100644 --- a/chapter10b/docs/example2a.gv +++ b/chapter10b/docs/example2a.gv @@ -4,7 +4,7 @@ digraph Memory { M [label="Default memory"]; X [label="Store x"]; Y [label="Store y"]; - M -> X [color=blue]; M -> Y [color=green]; - M -> MemMerge [label="default"]; X -> MemMerge [label="x",color=blue]; - Y -> MemMerge [label="y",color=green]; MemMerge -> Return; + X -> M [color=blue]; Y -> M [color=green]; + MemMerge -> M [label="default"]; MemMerge -> X [label="x",color=blue]; + MemMerge -> Y [label="y",color=green]; Return -> MemMerge; } diff --git a/chapter10b/docs/example2a.svg b/chapter10b/docs/example2a.svg index 74cb48e0..fc95e08c 100644 --- a/chapter10b/docs/example2a.svg +++ b/chapter10b/docs/example2a.svg @@ -4,79 +4,79 @@ - - + + Memory - + M - -Default memory + +Default memory X - -Store x + +Store x - + -M->X - - +X->M + + Y - -Store y + +Store y - + -M->Y - - +Y->M + + MemMerge - -MemMerge + +MemMerge - + -M->MemMerge - - -default +MemMerge->M + + +default - + -X->MemMerge - - -x +MemMerge->X + + +x - + -Y->MemMerge - - -y +MemMerge->Y + + +y Return - -Return + +Return - + -MemMerge->Return - - +Return->MemMerge + + diff --git a/chapter10b/docs/example2b.gv b/chapter10b/docs/example2b.gv index 7ef10ec8..17b35910 100644 --- a/chapter10b/docs/example2b.gv +++ b/chapter10b/docs/example2b.gv @@ -3,8 +3,8 @@ digraph Memory { node [shape=box]; P [label="MemPhi(x)"]; B [label="BulkMemPhi(All except x)"]; - Left -> P [label="slice x",color=blue]; Right -> P [label="slice x",color=blue]; - Left -> B; Right -> B; - Region -> P [style=dashed]; Region -> B [style=dashed]; - P -> MemMerge [label="x",color=blue]; B -> MemMerge [label="default"]; + P -> Left [label="slice x",color=blue]; P -> Right [label="slice x",color=blue]; + B -> Left; B -> Right; + P -> Region [style=dashed]; B -> Region [style=dashed]; + MemMerge -> P [label="x",color=blue]; MemMerge -> B [label="default"]; } diff --git a/chapter10b/docs/example2b.svg b/chapter10b/docs/example2b.svg index fae583e6..67d74ea8 100644 --- a/chapter10b/docs/example2b.svg +++ b/chapter10b/docs/example2b.svg @@ -4,98 +4,98 @@ - - + + Memory - + P - -MemPhi(x) - - - -MemMerge - -MemMerge - - - -P->MemMerge - - -x - - - -B - -BulkMemPhi(All except x) - - - -B->MemMerge - - -default + +MemPhi(x) Left - -Left + +Left - + -Left->P - - -slice x - - - -Left->B - - +P->Left + + +slice x Right - -Right + +Right - + -Right->P - - -slice x - - - -Right->B - - +P->Right + + +slice x Region - -Region + +Region - + -Region->P - - +P->Region + + - + + +B + +BulkMemPhi(All except x) + + + +B->Left + + + + + +B->Right + + + + -Region->B - - +B->Region + + + + + +MemMerge + +MemMerge + + + +MemMerge->P + + +x + + + +MemMerge->B + + +default diff --git a/chapter10b/docs/example2c.gv b/chapter10b/docs/example2c.gv index fb827b3e..7a0562ee 100644 --- a/chapter10b/docs/example2c.gv +++ b/chapter10b/docs/example2c.gv @@ -4,7 +4,7 @@ digraph Memory { M [label="Prior x memory"]; L [label="Load p.x"]; S [label="Store p.x"]; - M -> L [color=blue]; M -> S [color=blue]; - L -> S [style=dashed,label="execute load first"]; + L -> M [color=blue]; S -> M [color=blue]; + S -> L [style=dashed,label="execute load first"]; Y [label="Store p.y: independent"]; } diff --git a/chapter10b/docs/example2c.svg b/chapter10b/docs/example2c.svg index d8e5cf96..1d51ccca 100644 --- a/chapter10b/docs/example2c.svg +++ b/chapter10b/docs/example2c.svg @@ -4,53 +4,53 @@ - - + + Memory - + M - -Prior x memory + +Prior x memory L - -Load p.x + +Load p.x - + -M->L - - +L->M + + S - -Store p.x + +Store p.x - + -M->S - - +S->M + + - + -L->S - - -execute load first +S->L + + +execute load first Y - -Store p.y: independent + +Store p.y: independent -- cgit v1.2.3