From e7eb2db06d1b9c529f94f2da3a087c83c0498e05 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 19 Oct 2026 10:40:35 -0700 Subject: Turn off Store GVN with explaination --- chapter11/README.ja.md | 16 ++------ chapter11/README.md | 45 ++++++++-------------- .../java/com/seaofnodes/simple/node/StoreNode.java | 8 ++++ .../java/com/seaofnodes/simple/Chapter10Test.java | 27 +++++++++++-- 4 files changed, 50 insertions(+), 46 deletions(-) (limited to 'chapter11') diff --git a/chapter11/README.ja.md b/chapter11/README.ja.md index 7de65f28..fe1c771d 100644 --- a/chapter11/README.ja.md +++ b/chapter11/README.ja.md @@ -100,21 +100,11 @@ return p; ![分岐の合流が必要なのは x のメモリ Phi だけ](docs/example2b-merged.svg) -**Store をくくり出してから、上書きされた初期化を取り除きます。** ひとまとめの Phi と入力の集約がなくなると、Store #14 と #16 を使うのは MemPhi #20 だけになります。これらは同じポインタとエイリアスに格納し、同じ入力メモリを共有します。`PhiNode` は Store を合流の下に引き下げられます。 +**分岐の Store は別々に保ちます。** これが最終グラフです。Store の等価性はノードの同一性で判定するので、GVN も一般的な Phi の共通化も Store #14 と #16 をまとめません。それぞれが自身の分岐に残ります。両方が初期の `p.x = 0` の Store #7 を使うため、ユーザーが1つという条件を満たさず、連続する Store の除去でも #7 は消えません。オブジェクトを返すので、`p.y = 0` の Store #8 も残ります。 -```text -MemPhi_x(Store_x(mem, p, 3), Store_x(mem, p, 4)) - becomes -Store_x(mem, p, Phi(3, 4)) -``` - -一般に Phi の組み替えでは、第10章と同じく、Load や Store を押し上げたり引き下げたりして組み合わせられます。Phi の新しいメモリオペランドには、そのエイリアスの精密な MemPhi を使えます。このピープホール変換は精密なエイリアスを必要とし、BulkMem があると妨げられます。そのため、BulkMem を分割するきっかけにもなります。 - -例の続きを見ると、新しい値の Phi #28 は true 側で 3、false 側で 4 を選びます。Store #27 が両分岐の Store とそのメモリ Phi を置き換えます。初期の `p.x = 0` の Store #7 は、この1つの Store だけをユーザーに持つようになり、連続するストアの除去で迂回されます。`p.y = 0` の Store #8 は残ります。オブジェクトを返すので、その `y` フィールドは引き続き初期化が必要です。 - -![最終グラフ: 値の Phi を格納する1つの x Store と y の初期化](docs/example2b-final.svg) +グラフには4つの Store、1つの MemPhi、1つの MemMerge があり、BulkMemPhi は消えています。このダイヤモンドだけなら2つの Store の共通化は安全に行えますが、Store GVN とともにこの書き換えも無効にしています。3経路のうち2経路だけにある同じ Store を共有すると、残る経路でも書き込んでしまうことがあるためです。第10章の Store の等価性の説明を参照してください。Load の共通化は有効なままで、ひとまとめのメモリの分割後、異なるメモリオペランドには精密な MemPhi を使います。 -したがって最終グラフには、2つの Store、通常の値の Phi が1つ、MemMerge が1つあり、MemPhi も BulkMemPhi も残りません。ワークリストの順序が違えば、たとえば元の入力 MemMerge を平坦化前に迂回し、一時的な `y` の分割を避けられる場合もあります。 +ワークリストの順序が違えば、元の入力 MemMerge を平坦化前に迂回し、一時的な `y` の分割を避けられる場合もあります。 このメモリ分割変換は大きくグラフに介入するため、再帰的に呼び出すことを禁止します。ループの周囲を分割することはよいのですが、その途中にあるループ先頭を分割しようとすると問題になります。分割で生まれた新しいノードをワークリストに入れ、現在の分割が完了してから訪問します。これによって、ループを巡るメモリを安全に完全分割できます。 diff --git a/chapter11/README.md b/chapter11/README.md index 115cb0d2..e97e804f 100644 --- a/chapter11/README.md +++ b/chapter11/README.md @@ -143,36 +143,21 @@ from Start, `x` from MemPhi #20, and `y` from Store #8. ![Only the x memory Phi still needs the branch merge](docs/example2b-merged.svg) -**Factor the Stores, then remove the overwritten initialization.** With the -bulk Phi and the incoming aggregates gone, Stores #14 and #16 are used only -by MemPhi #20. They store to the same pointer and alias, and share the same -incoming memory. `PhiNode` can pull the Store below the merge: - -```text -MemPhi_x(Store_x(mem, p, 3), Store_x(mem, p, 4)) - becomes -Store_x(mem, p, Phi(3, 4)) -``` - -In general, Phi refactoring can combine Loads or Stores as in Chapter 10 (pushing -up or pulling down). The Phi new memory operands can use precise MemPhis for -the alias. This peep requires precise aliases, and is otherwise blocked by -BulkMems - and thus is a trigger for splitting a BulkMem. - - -Continuing with the example, the new value Phi #28 chooses 3 on the true arm -and 4 on the false arm. Store -#27 replaces both branch Stores and their memory Phi. Now the initial -`p.x = 0` Store #7 has only that one Store as a user, so store-after-store -elimination bypasses it. The `p.y = 0` Store #8 remains: we return the object, -and its `y` field still needs initialization. - -![Final graph: one x Store of a value Phi, and the y initialization](docs/example2b-final.svg) - -Thus the final graph has two Stores, one ordinary value Phi, and one MemMerge; -neither a MemPhi nor a BulkMemPhi remains. Other worklists order can, for -instance, bypass the original incoming MemMerges before flattening them, -avoiding the temporary `y` split. +**Keep the branch Stores separate.** This is the final graph. Store equality +uses node identity, so neither GVN nor generic Phi factoring combines Stores +#14 and #16. Each stays on its own branch. Both use the initial `p.x = 0` +Store #7, so the sole-use guard prevents store-after-store elimination from +removing it. The `p.y = 0` Store #8 also remains because we return the object. + +The graph has four Stores, one MemPhi, and one MemMerge; the BulkMemPhi is gone. +Although factoring the two Stores in this particular diamond could be safe, +we disable that rewrite along with Store GVN. Sharing equal Stores on only two +of three paths can force the write onto the third path. See Chapter 10's +discussion of Store equality. Load factoring remains enabled, using precise +MemPhis for differing memory operands once bulk splitting has finished. + +Other worklist orders can bypass the original incoming MemMerges before +flattening them, avoiding the temporary `y` split. This memory splitting transform is invasive, and is disallowed from being called recursively; you can end up splitting around a loop (which is good) but diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 026d5c50..024307bb 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -72,4 +72,12 @@ public class StoreNode extends MemOpNode { return false; } + + // Do not GVN Stores. Two equal Stores on two of three paths are the easy + // failure: sharing them makes GCM place the Store on all three paths. + // Sharing is safe only if every exit path goes through an original Store, + // or GCM splits the shared Store to keep it on those paths. Stores must + // sink, not run on extra paths. GVN does not check this; GCM does not split. + // Identity also disables generic Phi factoring of Stores. + @Override boolean eq(Node n) { return this == n; } } diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 9a5e4677..62c35b8e 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -15,6 +15,26 @@ import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; public class Chapter10Test { + @Test public void testConditionalStoreSharing() { + // Sharing the writes on two of three paths must not write on the third. + // Return the object so Load forwarding cannot hide the physical Store. + String src = """ + struct S { int x; }; + S a = new S; + a.x = 10; + if (arg == 1) a.x = 9; + else if (arg == 2) a.x = 9; + return a; + """; + var stop = new Parser(src).parse().iterate(); + for( int arg : new int[]{0,1,2,3} ) { + long expected = (arg==1 || arg==2) ? 9 : 10; + var obj = (com.seaofnodes.simple.evaluator.Evaluator.Obj) + com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,arg); + assertEquals(expected,obj.fields()[0]); + } + } + @Test public void testDeadReferenceReturn() { for( String body : new String[] { "return new S; return 0;", @@ -290,7 +310,7 @@ while( i.x < i.len ) { return sum; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop16,0,(Phi(Loop,0,(Phi_$2+1))+Phi_sum));", stop.toString()); + assertEquals("return Phi(Loop16,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); assertEquals(10L,Evaluator.evaluate(stop,5)); } @@ -543,7 +563,7 @@ return 0; assertEquals(3L,Evaluator.evaluate(stop,3)); } - @Test public void testDropStores() { + @Test public void testKeepBranchStores() { StopNode stop = new Parser(""" struct S { int x; } S s = new S; @@ -551,7 +571,8 @@ return 0; return s; """).parse().iterate(); // Releasing the old aggregate exposes the overwritten initializing Store. - assertEquals(1,countMemoryNodes(stop,StoreNode.class,new BitSet())); + // Two branch Stores plus the initial zero Store. + assertEquals(3,countMemoryNodes(stop,StoreNode.class,new BitSet())); assertEquals(2L,((Evaluator.Obj)Evaluator.evaluate(stop,0)).fields()[0]); assertEquals(4L,((Evaluator.Obj)Evaluator.evaluate(stop,3)).fields()[0]); } -- cgit v1.2.3