diff options
48 files changed, 783 insertions, 123 deletions
diff --git a/chapter10/README.ja.md b/chapter10/README.ja.md index efc4f0ea..e81fbdc9 100644 --- a/chapter10/README.ja.md +++ b/chapter10/README.ja.md @@ -229,16 +229,16 @@ Load(Phi(r, m0, m1), p.x) メモリの Phi が、ロードされた値の Phi になります。このピープホール変換は Node の総数を増やすので、利益のヒューリスティックは、少なくとも1つの Load が畳み込まれることを要求します。ループの場合、この Load は**後退エッジ**でなければなりません。入口だけで畳み込むと、サイクルに沿って無限に押し上げ続けられるロードが残るためです。算術の書き換えと同じく、畳み込みを露出させることは、変換後の後片付けに期待するものではなく、グラフを変換する判断の一部です。[`LoadNode.idealize()`](src/main/java/com/seaofnodes/simple/node/LoadNode.java) を参照してください。 -逆方向は[第5章の共通演算の引き下げ](../chapter05/README.ja.md#例3)を拡張します。「Load の Phi は、Phi の Load になる」。対応する Load や Store の Phi は、合流後の1つの演算にできます。たとえば、次の2つの書き込みは、 +逆方向は[第5章の共通演算の引き下げ](../chapter05/README.ja.md#例3)を拡張します。「Load の Phi は、Phi の Load になる」。対応する Load の Phi は、合流後の1つの Load にできます。メモリやポインタも含め、異なる各オペランドについて正しく型付けされた別々の Phi を作ります。結果の型を保ち、メモリのユーザーに競合する書き込みやメモリの合流があれば変換を断念します。読み出しを遅らせると値が変わり得るためです。後の章では反依存を加えますが、ここでは保守的にチェックします。 + +Store は GVN とこの Phi の書き換えから除外します。簡単な GVN の失敗例は、3経路のうち2経路に同じ Store がある場合です。 ```java -if (arg) s.x = arg+1; -else s.x = arg+2; +if (arg == 1) s.x = 9; +else if (arg == 2) s.x = 9; ``` -`s.x = Phi(arg+1,arg+2)` になり、最終的には `s.x = arg+Phi(1,2)` にできます。一般的な書き換えでは、メモリやポインタも含め、異なる各オペランドについて正しく型付けされた別々の Phi を作ります。メモリ演算にはさらに注意が必要です。型の精度が失われる可能性があるので、それも利益判定の一部としてチェックします。 - -また、Store を移動したときに元の作用が消えるように、Store にほかのユーザーがあってはいけません。Load については、そのメモリのユーザーに、競合する書き込みやメモリの合流が生じる可能性があってはいけません。そうでなければ、読み出しを遅らせると値が変わり得ます。ずっと後に反依存を追加しますが、今は保守的にチェックします。 +この2つを共有すると、スケジューラは `s.x` を変更しないはずの経路も含め、3経路すべてで書き込む位置に Store を置いてしまいます。共有には、元の Store がすべての出口経路を覆うという証明、または共有した Store を元の経路に分割し直せるスケジューラが必要です。どちらも実装していないので、Store の等価性にはノードの同一性を使います。これにより一般的な Phi による Store の共通化も無効になります。連続する Store の除去は引き続き有効です。第17b章では、閉じたループの Store をループ出口に移す専用のピープホール変換を追加します。 ### 簡単な最適化を見逃す diff --git a/chapter10/README.md b/chapter10/README.md index db72c4cb..8b43f2b3 100644 --- a/chapter10/README.md +++ b/chapter10/README.md @@ -359,25 +359,28 @@ graph, not just a hoped-for cleanup afterward. See The reverse direction extends [Chapter 5's common-operation pull-down](../chapter05/README.md#example-3): -"A Phis of Loads becomes a Load of a Phi". A Phi of matching Loads or Stores -can become one operation after the join. For example, these two writes: +"A Phi of Loads becomes a Load of Phis". A Phi of matching Loads can become +one Load after the join. The rewrite creates a separate, correctly typed Phi +for each differing operand, including memory and pointers. It must preserve +the result's type and reject any possible conflicting write or memory merge +among the memory's users. Otherwise delaying the read could change its value. +Later chapters add anti-dependences; here we use a conservative check. + +Stores are excluded from GVN and this Phi rewrite. The easy GVN failure has +equal Stores on two of three paths: ```java -if (arg) s.x = arg+1; -else s.x = arg+2; +if (arg == 1) s.x = 9; +else if (arg == 2) s.x = 9; ``` -can become `s.x = Phi(arg+1,arg+2)` and eventually `s.x = arg+Phi(1,2)`. The -general rewrite creates a separate, correctly typed Phi for each differing -operand, including memory and pointers. We must be more careful here with -memory ops; it is possible to lose some type precision, so we check for that as -part of the profitability. - -Also, a Store must have no other users, so moving it removes the original -effect. A Load must have no possible conflicting writes or memory merges among -its memory's users; otherwise delaying the read could change its value. Much -later, we will be adding anti-dependences, but for now we do a conservative -check. +Sharing those Stores forces the scheduler to place the write on all three +paths, including the path that should leave `s.x` unchanged. Sharing needs a +proof that the original Stores cover every exit path, or a scheduler that can +split the shared Store back onto its original paths. We do neither. Store +equality therefore uses node identity; this also disables generic Phi factoring +of Stores. Explicit store-after-store elimination remains enabled. Chapter 17b +adds a separate peep that sinks a closed loop's Stores to the loop exit. ### Missing an easy one diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 71eb0842..75d1a36f 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -64,4 +64,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/chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java index f39b1e78..1374aa06 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter10/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;", @@ -169,7 +189,7 @@ while (arg) { return bar.a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,0,(Phi_$mem+2));", stop.toString()); + assertEquals("return Phi(Loop10,0,(Phi_a+2));", stop.toString()); } @Test @@ -541,14 +561,15 @@ 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; if (arg) s.x=arg+1; else s.x=arg+2; return s; """).parse().iterate(); - 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]); } 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;  -**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` フィールドは引き続き初期化が必要です。 - - +グラフには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.  -**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. - - - -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]); } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/StoreNode.java index e9eaaf2e..e09c8fd3 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -85,4 +85,12 @@ public class StoreNode extends MemOpNode { Type ptr = val()._type; return _init || ptr.isa(_declaredType) ? null : "Cannot store "+ptr+" into field "+_declaredType+" "+_name; } + + // 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/chapter12/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter10Test.java index e5d9b882..6efbeb72 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter12/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;", @@ -542,7 +562,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; @@ -550,7 +570,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]); } diff --git a/chapter13/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/StoreNode.java index e9eaaf2e..e09c8fd3 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -85,4 +85,12 @@ public class StoreNode extends MemOpNode { Type ptr = val()._type; return _init || ptr.isa(_declaredType) ? null : "Cannot store "+ptr+" into field "+_declaredType+" "+_name; } + + // 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/chapter13/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter13/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 6649c0b0..7fa9978d 100644 --- a/chapter13/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter13/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -11,6 +11,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;", @@ -540,14 +560,14 @@ 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; if (arg) s.x=arg+1; else s.x=arg+2; return s; """).parse().iterate(); - // These chapters still bind struct Stores to branch control. + // 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]); diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/StoreNode.java index e9eaaf2e..e09c8fd3 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -85,4 +85,12 @@ public class StoreNode extends MemOpNode { Type ptr = val()._type; return _init || ptr.isa(_declaredType) ? null : "Cannot store "+ptr+" into field "+_declaredType+" "+_name; } + + // 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/chapter14/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter14/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 6649c0b0..7fa9978d 100644 --- a/chapter14/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter14/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -11,6 +11,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;", @@ -540,14 +560,14 @@ 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; if (arg) s.x=arg+1; else s.x=arg+2; return s; """).parse().iterate(); - // These chapters still bind struct Stores to branch control. + // 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]); diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 485491c0..11c865a8 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -91,4 +91,12 @@ public class StoreNode extends MemOpNode { Type t = val()._type; return _init || t.isa(_declaredType) ? null : "Cannot store "+t+" into field "+_declaredType+" "+_name; } + + // 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/chapter15/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter15/src/test/java/com/seaofnodes/simple/Chapter10Test.java index a5e3a9e0..3f34c448 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -11,6 +11,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;", @@ -541,14 +561,15 @@ 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; if (arg) s.x=arg+1; else s.x=arg+2; return s; """).parse().iterate(); - assertEquals(1,countMemoryNodes(stop,StoreNode.class,new BitSet())); + // Keep each Store on its own branch. + assertEquals(2,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]); } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 8eb104a7..f8fbb907 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -116,4 +116,12 @@ public class StoreNode extends MemOpNode { Type t = val()._type; return _init || t.isa(_declaredType) ? null : "Cannot store "+t+" into field "+_declaredType+" "+_name; } + + // 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/chapter16/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 0b8be64b..5635183e 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -8,6 +8,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;", @@ -532,14 +552,15 @@ 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; if (arg) s.x=arg+1; else s.x=arg+2; return s; """).parse().iterate(); - assertEquals(1,countMemoryNodes(stop,StoreNode.class,new BitSet())); + // Keep each Store on its own branch. + assertEquals(2,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]); } diff --git a/chapter17a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter17a/src/main/java/com/seaofnodes/simple/node/StoreNode.java index a5f04dd2..6731a1b9 100644 --- a/chapter17a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter17a/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -122,4 +122,12 @@ public class StoreNode extends MemOpNode { Type t = val()._type; return _init || t.isa(_declaredType) ? null : "Cannot store "+t+" into field "+_declaredType+" "+_name; } + + // 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/chapter17a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter17a/src/test/java/com/seaofnodes/simple/Chapter10Test.java index f634e421..8f8900ca 100644 --- a/chapter17a/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter17a/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -8,6 +8,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;", @@ -532,14 +552,15 @@ 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; if (arg) s.x=arg+1; else s.x=arg+2; return s; """).parse().iterate(); - assertEquals(1,countMemoryNodes(stop,StoreNode.class,new BitSet())); + // Keep each Store on its own branch. + assertEquals(2,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]); } diff --git a/chapter17b/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter17b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 962618ef..d32384c5 100644 --- a/chapter17b/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter17b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -162,4 +162,13 @@ public class StoreNode extends MemOpNode { Type t = val()._type; return _init || t.isa(_declaredType) ? null : "Cannot store "+t+" into field "+_declaredType+" "+_name; } + + // 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. + // The closed-loop Store sink is a separate peep and still applies. + @Override boolean eq(Node n) { return this == n; } } diff --git a/chapter17b/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter17b/src/test/java/com/seaofnodes/simple/Chapter10Test.java index f634e421..8f8900ca 100644 --- a/chapter17b/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter17b/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -8,6 +8,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;", @@ -532,14 +552,15 @@ 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; if (arg) s.x=arg+1; else s.x=arg+2; return s; """).parse().iterate(); - assertEquals(1,countMemoryNodes(stop,StoreNode.class,new BitSet())); + // Keep each Store on its own branch. + assertEquals(2,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]); } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/StoreNode.java index de17bbad..93e71554 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -167,4 +167,13 @@ public class StoreNode extends MemOpNode { Type t = val()._type; return _init || t.isa(_declaredType) ? null : Parser.error("Cannot store "+t+" into field "+_declaredType+" "+_name,_loc); } + + // 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. + // The closed-loop Store sink is a separate peep and still applies. + @Override boolean eq(Node n) { return this == n; } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 2681e878..cf877cb8 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -7,6 +7,24 @@ 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 code = new CodeGen(src).driver(CodeGen.Phase.LocalSched); + for( int arg : new int[]{0,1,2,3} ) { + long expected = (arg==1 || arg==2) ? 9 : 10; + assertEquals("S{x="+expected+"}",Eval2.eval(code,arg)); + } + } + @Test public void testDeadReferenceReturn() { for( String body : new String[] { "return new S; return 0;", @@ -529,7 +547,7 @@ return 0; assertEquals("3",Eval2.eval(code,3)); } - @Test public void testDropStores() { + @Test public void testKeepBranchStores() { var code = new CodeGen(""" struct S { int x; }; !S !s = new S; @@ -537,7 +555,8 @@ return 0; return s; """).parse().iter(); StopNode stop = code._stop; - assertEquals(1,countMemoryNodes(stop,StoreNode.class,new BitSet())); + // Keep each Store on its own branch. + assertEquals(2,countMemoryNodes(stop,StoreNode.class,new BitSet())); assertEquals("S{x=2}",Eval2.eval(code,0)); assertEquals("S{x=4}",Eval2.eval(code,3)); } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter17bTest.java index a5ce8f49..3c40f684 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter17bTest.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter17bTest.java @@ -7,6 +7,31 @@ import static org.junit.Assert.fail; public class Chapter17bTest { + @Test public void testSinkLoopStores() { + var code = new CodeGen(""" + struct S { int x; }; + !S !a = new S; + a.x = 10; + int i = 0; + while (i < arg) { a.x = i + 1; i++; } + return a; + """).driver(CodeGen.Phase.LocalSched); + int[] stores = {0}; + code._stop.walk(n -> { + if( n instanceof com.seaofnodes.simple.node.StoreNode st && st._name.equals("x") ) { + assertEquals(0,st.cfg0().loopDepth()); // One final Store outside the loop. + stores[0]++; + } + return null; + }); + assertEquals(1,stores[0]); + for( int arg : new int[]{-1,0,1,4} ) { + long expected = arg<=0 ? 10 : arg; + assertEquals("S{x="+expected+"}",Eval2.eval(code,arg)); + } + } + + @Ignore @Test public void testJig() { diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 86c759bd..e21fb6ff 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -152,4 +152,13 @@ public class StoreNode extends MemOpNode { //return _init || t.isa(_declaredType) ? null : Parser.error("Cannot store "+t+" into field "+_declaredType+" "+_name,_loc); return null; } + + // 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. + // The closed-loop Store sink is a separate peep and still applies. + @Override boolean eq(Node n) { return this == n; } } diff --git a/chapter19/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 2681e878..cf877cb8 100644 --- a/chapter19/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter19/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -7,6 +7,24 @@ 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 code = new CodeGen(src).driver(CodeGen.Phase.LocalSched); + for( int arg : new int[]{0,1,2,3} ) { + long expected = (arg==1 || arg==2) ? 9 : 10; + assertEquals("S{x="+expected+"}",Eval2.eval(code,arg)); + } + } + @Test public void testDeadReferenceReturn() { for( String body : new String[] { "return new S; return 0;", @@ -529,7 +547,7 @@ return 0; assertEquals("3",Eval2.eval(code,3)); } - @Test public void testDropStores() { + @Test public void testKeepBranchStores() { var code = new CodeGen(""" struct S { int x; }; !S !s = new S; @@ -537,7 +555,8 @@ return 0; return s; """).parse().iter(); StopNode stop = code._stop; - assertEquals(1,countMemoryNodes(stop,StoreNode.class,new BitSet())); + // Keep each Store on its own branch. + assertEquals(2,countMemoryNodes(stop,StoreNode.class,new BitSet())); assertEquals("S{x=2}",Eval2.eval(code,0)); assertEquals("S{x=4}",Eval2.eval(code,3)); } diff --git a/chapter19/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter17bTest.java index 97b5d7d8..c9bd840b 100644 --- a/chapter19/src/test/java/com/seaofnodes/simple/Chapter17bTest.java +++ b/chapter19/src/test/java/com/seaofnodes/simple/Chapter17bTest.java @@ -7,6 +7,31 @@ import static org.junit.Assert.fail; public class Chapter17bTest { + @Test public void testSinkLoopStores() { + var code = new CodeGen(""" + struct S { int x; }; + !S !a = new S; + a.x = 10; + int i = 0; + while (i < arg) { a.x = i + 1; i++; } + return a; + """).driver(CodeGen.Phase.LocalSched); + int[] stores = {0}; + code._stop.walk(n -> { + if( n instanceof com.seaofnodes.simple.node.StoreNode st && st._name.equals("x") ) { + assertEquals(0,st.cfg0().loopDepth()); // One final Store outside the loop. + stores[0]++; + } + return null; + }); + assertEquals(1,stores[0]); + for( int arg : new int[]{-1,0,1,4} ) { + long expected = arg<=0 ? 10 : arg; + assertEquals("S{x="+expected+"}",Eval2.eval(code,arg)); + } + } + + @Ignore @Test public void testJig() { diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 9e6689f0..0f8e50c4 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -153,4 +153,13 @@ public class StoreNode extends MemOpNode { //return _init || t.isa(_declaredType) ? null : Parser.error("Cannot store "+t+" into field "+_declaredType+" "+_name,_loc); return null; } + + // 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. + // The closed-loop Store sink is a separate peep and still applies. + @Override boolean eq(Node n) { return this == n; } } diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 8af1c71d..3e01458b 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -8,6 +8,24 @@ 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 code = new CodeGen(src).driver(CodeGen.Phase.LocalSched); + for( int arg : new int[]{0,1,2,3} ) { + long expected = (arg==1 || arg==2) ? 9 : 10; + assertEquals("S{x="+expected+"}",Eval2.eval(code,arg)); + } + } + @Test public void testDeadReferenceReturn() { for( String body : new String[] { "return new S; return 0;", @@ -530,7 +548,7 @@ return 0; assertEquals("3",Eval2.eval(code,3)); } - @Test public void testDropStores() { + @Test public void testKeepBranchStores() { var code = new CodeGen(""" struct S { int x; }; !S !s = new S; @@ -538,7 +556,8 @@ return 0; return s; """).parse().iter(); StopNode stop = code._stop; - assertEquals(1,countMemoryNodes(stop,StoreNode.class,new BitSet())); + // Keep each Store on its own branch. + assertEquals(2,countMemoryNodes(stop,StoreNode.class,new BitSet())); assertEquals("S{x=2}",Eval2.eval(code,0)); assertEquals("S{x=4}",Eval2.eval(code,3)); } diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter17bTest.java index f6eb0190..25d27cab 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter17bTest.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter17bTest.java @@ -8,6 +8,31 @@ import static org.junit.Assert.fail; public class Chapter17bTest { + @Test public void testSinkLoopStores() { + var code = new CodeGen(""" + struct S { int x; }; + !S !a = new S; + a.x = 10; + int i = 0; + while (i < arg) { a.x = i + 1; i++; } + return a; + """).driver(CodeGen.Phase.LocalSched); + int[] stores = {0}; + code._stop.walk(n -> { + if( n instanceof com.seaofnodes.simple.node.StoreNode st && st._name.equals("x") ) { + assertEquals(0,st.cfg0().loopDepth()); // One final Store outside the loop. + stores[0]++; + } + return null; + }); + assertEquals(1,stores[0]); + for( int arg : new int[]{-1,0,1,4} ) { + long expected = arg<=0 ? 10 : arg; + assertEquals("S{x="+expected+"}",Eval2.eval(code,arg)); + } + } + + @Ignore @Test public void testJig() { diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/StoreNode.java index a5b09663..d59e5800 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -158,4 +158,13 @@ public class StoreNode extends MemOpNode { //return _init || t.isa(_declaredType) ? null : Parser.error("Cannot store "+t+" into field "+_declaredType+" "+_name,_loc); return null; } + + // 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. + // The closed-loop Store sink is a separate peep and still applies. + @Override public boolean eq(Node n) { return this == n; } } diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 8af1c71d..3e01458b 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -8,6 +8,24 @@ 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 code = new CodeGen(src).driver(CodeGen.Phase.LocalSched); + for( int arg : new int[]{0,1,2,3} ) { + long expected = (arg==1 || arg==2) ? 9 : 10; + assertEquals("S{x="+expected+"}",Eval2.eval(code,arg)); + } + } + @Test public void testDeadReferenceReturn() { for( String body : new String[] { "return new S; return 0;", @@ -530,7 +548,7 @@ return 0; assertEquals("3",Eval2.eval(code,3)); } - @Test public void testDropStores() { + @Test public void testKeepBranchStores() { var code = new CodeGen(""" struct S { int x; }; !S !s = new S; @@ -538,7 +556,8 @@ return 0; return s; """).parse().iter(); StopNode stop = code._stop; - assertEquals(1,countMemoryNodes(stop,StoreNode.class,new BitSet())); + // Keep each Store on its own branch. + assertEquals(2,countMemoryNodes(stop,StoreNode.class,new BitSet())); assertEquals("S{x=2}",Eval2.eval(code,0)); assertEquals("S{x=4}",Eval2.eval(code,3)); } diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter17bTest.java index 8ea72c21..a761a31b 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter17bTest.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter17bTest.java @@ -8,6 +8,31 @@ import static org.junit.Assert.fail; public class Chapter17bTest { + @Test public void testSinkLoopStores() { + var code = new CodeGen(""" + struct S { int x; }; + !S !a = new S; + a.x = 10; + int i = 0; + while (i < arg) { a.x = i + 1; i++; } + return a; + """).driver(CodeGen.Phase.LocalSched); + int[] stores = {0}; + code._stop.walk(n -> { + if( n instanceof com.seaofnodes.simple.node.StoreNode st && st._name.equals("x") ) { + assertEquals(0,st.cfg0().loopDepth()); // One final Store outside the loop. + stores[0]++; + } + return null; + }); + assertEquals(1,stores[0]); + for( int arg : new int[]{-1,0,1,4} ) { + long expected = arg<=0 ? 10 : arg; + assertEquals("S{x="+expected+"}",Eval2.eval(code,arg)); + } + } + + @Ignore @Test public void testJig() { diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/StoreNode.java index ecda014b..18271929 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -167,4 +167,13 @@ public class StoreNode extends MemOpNode { return Parser.error("Cannot modify final field '"+_name+"'",_loc); return null; } + + // 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. + // The closed-loop Store sink is a separate peep and still applies. + @Override public boolean eq(Node n) { return this == n; } } diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 68971e79..5fbae210 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -8,6 +8,24 @@ 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 code = new CodeGen(src).driver(CodeGen.Phase.LocalSched); + for( int arg : new int[]{0,1,2,3} ) { + long expected = (arg==1 || arg==2) ? 9 : 10; + assertEquals("S{x="+expected+"}",Eval2.eval(code,arg)); + } + } + @Test public void testDeadReferenceReturn() { for( String body : new String[] { "return new S; return 0;", @@ -532,7 +550,7 @@ return 0; assertEquals("3",Eval2.eval(code,3)); } - @Test public void testDropStores() { + @Test public void testKeepBranchStores() { var code = new CodeGen(""" struct S { int x; }; !S !s = new S; @@ -540,7 +558,8 @@ return 0; return s; """).parse().iter().finalizeIR(); StopNode stop = code._stop; - assertEquals(1,countMemoryNodes(stop,StoreNode.class,new BitSet())); + // Keep each Store on its own branch. + assertEquals(2,countMemoryNodes(stop,StoreNode.class,new BitSet())); assertEquals("S{x=2}",Eval2.eval(code,0)); assertEquals("S{x=4}",Eval2.eval(code,3)); } diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter17bTest.java index 3467f35c..9185aec8 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter17bTest.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter17bTest.java @@ -8,6 +8,31 @@ import static org.junit.Assert.fail; public class Chapter17bTest { + @Test public void testSinkLoopStores() { + var code = new CodeGen(""" + struct S { int x; }; + !S !a = new S; + a.x = 10; + int i = 0; + while (i < arg) { a.x = i + 1; i++; } + return a; + """).driver(CodeGen.Phase.LocalSched); + int[] stores = {0}; + code._stop.walk(n -> { + if( n instanceof com.seaofnodes.simple.node.StoreNode st && st._name.equals("x") ) { + assertEquals(0,st.cfg0().loopDepth()); // One final Store outside the loop. + stores[0]++; + } + return null; + }); + assertEquals(1,stores[0]); + for( int arg : new int[]{-1,0,1,4} ) { + long expected = arg<=0 ? 10 : arg; + assertEquals("S{x="+expected+"}",Eval2.eval(code,arg)); + } + } + + @Ignore @Test public void testJig() { diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 603a0607..262f6bf3 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -171,4 +171,13 @@ public class StoreNode extends MemOpNode { return Parser.error("Cannot modify final field '"+_name+"'",_loc); return null; } + + // 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. + // The closed-loop Store sink is a separate peep and still applies. + @Override public boolean eq(Node n) { return this == n; } } diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 78265bb2..4fd20b18 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -8,6 +8,24 @@ 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 code = new CodeGen(src).driver(CodeGen.Phase.LocalSched); + for( int arg : new int[]{0,1,2,3} ) { + long expected = (arg==1 || arg==2) ? 9 : 10; + assertEquals("S{x="+expected+"}",Eval2.eval(code,arg)); + } + } + @Test public void testDeadReferenceReturn() { for( String body : new String[] { "return new S; return 0;", @@ -548,7 +566,7 @@ return 0; assertEquals("3",Eval2.eval(code,3)); } - @Test public void testDropStores() { + @Test public void testKeepBranchStores() { var code = new CodeGen(""" struct S { int x; }; !S !s = new S; @@ -556,7 +574,8 @@ return 0; return s; """).parse().iter().finalizeIR(); StopNode stop = code._stop; - assertEquals(1,countMemoryNodes(stop,StoreNode.class,new BitSet())); + // Keep each Store on its own branch. + assertEquals(2,countMemoryNodes(stop,StoreNode.class,new BitSet())); assertEquals("S{x=2}",Eval2.eval(code,0)); assertEquals("S{x=4}",Eval2.eval(code,3)); } diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter17bTest.java index 28a10b05..862c9cf7 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter17bTest.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter17bTest.java @@ -8,6 +8,31 @@ import static org.junit.Assert.fail; public class Chapter17bTest { + @Test public void testSinkLoopStores() { + var code = new CodeGen(""" + struct S { int x; }; + !S !a = new S; + a.x = 10; + int i = 0; + while (i < arg) { a.x = i + 1; i++; } + return a; + """).driver(CodeGen.Phase.LocalSched); + int[] stores = {0}; + code._stop.walk(n -> { + if( n instanceof com.seaofnodes.simple.node.StoreNode st && st._name.equals("x") ) { + assertEquals(0,st.cfg0().loopDepth()); // One final Store outside the loop. + stores[0]++; + } + return null; + }); + assertEquals(1,stores[0]); + for( int arg : new int[]{-1,0,1,4} ) { + long expected = arg<=0 ? 10 : arg; + assertEquals("S{x="+expected+"}",Eval2.eval(code,arg)); + } + } + + @Ignore @Test public void testJig() { diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 4e1d7ce3..47f12d82 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -171,4 +171,13 @@ public class StoreNode extends MemOpNode { return Parser.error("Cannot modify final field '"+_name+"'",_loc); return null; } + + // 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. + // The closed-loop Store sink is a separate peep and still applies. + @Override public boolean eq(Node n) { return this == n; } } diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 40c69a4f..afe0b141 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -8,6 +8,24 @@ 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 code = new CodeGen(src).driver(CodeGen.Phase.LocalSched); + for( int arg : new int[]{0,1,2,3} ) { + long expected = (arg==1 || arg==2) ? 9 : 10; + assertEquals("S{x="+expected+"}",Eval2.eval(code,arg)); + } + } + @Test public void testDeadReferenceReturn() { for( String body : new String[] { "return new S; return 0;", @@ -548,7 +566,7 @@ return 0; assertEquals("3",Eval2.eval(code,3)); } - @Test public void testDropStores() { + @Test public void testKeepBranchStores() { var code = new CodeGen(""" struct S { int x; }; !S !s = new S; @@ -556,7 +574,8 @@ return 0; return s; """).driver(CodeGen.Phase.FinalizeIR); StopNode stop = code._stop; - assertEquals(1,countMemoryNodes(stop,StoreNode.class,new BitSet())); + // Keep each Store on its own branch. + assertEquals(2,countMemoryNodes(stop,StoreNode.class,new BitSet())); assertEquals("S{x=2}",Eval2.eval(code,0)); assertEquals("S{x=4}",Eval2.eval(code,3)); } diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter17bTest.java index 77e75449..d2fa40f3 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter17bTest.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter17bTest.java @@ -8,6 +8,31 @@ import static org.junit.Assert.fail; public class Chapter17bTest { + @Test public void testSinkLoopStores() { + var code = new CodeGen(""" + struct S { int x; }; + !S !a = new S; + a.x = 10; + int i = 0; + while (i < arg) { a.x = i + 1; i++; } + return a; + """).driver(CodeGen.Phase.LocalSched); + int[] stores = {0}; + code._stop.walk(n -> { + if( n instanceof com.seaofnodes.simple.node.StoreNode st && st._name.equals("x") ) { + assertEquals(0,st.cfg0().loopDepth()); // One final Store outside the loop. + stores[0]++; + } + return null; + }); + assertEquals(1,stores[0]); + for( int arg : new int[]{-1,0,1,4} ) { + long expected = arg<=0 ? 10 : arg; + assertEquals("S{x="+expected+"}",Eval2.eval(code,arg)); + } + } + + @Ignore @Test public void testJig() { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 8a0bf8d4..cc958348 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -129,7 +129,7 @@ public class StoreNode extends MemOpNode { // peeps can lose the declaration to a flow-sensitive constant field // state. Imported Stores already carry a serialized non-zero width. if( _size==0 && (_size= storageType()) != 0 ) { - unlock(); // Width participates in GVN identity. + unlock(); // Width participates in the cached hash. return init(); } @@ -323,6 +323,13 @@ public class StoreNode extends MemOpNode { return null; } - @Override public boolean eq(Node n) { return _size==((StoreNode)n)._size && super.eq(n); } + // 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. + // The closed-loop Store sink is a separate peep and still applies. + @Override public boolean eq(Node n) { return this == n; } @Override int hash() { return super.hash() ^ _size; } } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 924884ac..6892db0c 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -6,6 +6,24 @@ 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 code = new CodeGen(src).driver(CodeGen.Phase.LocalSched); + for( int arg : new int[]{0,1,2,3} ) { + long expected = (arg==1 || arg==2) ? 9 : 10; + assertEquals("Test.S{x="+expected+"}",Eval2.eval(code,arg)); + } + } + @Test public void testDeadReferenceReturn() { for( String body : new String[] { "return new S; return 0;", diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter17bTest.java index e85ce31d..08029c4b 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter17bTest.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter17bTest.java @@ -8,6 +8,33 @@ import static org.junit.Assert.fail; public class Chapter17bTest { + @Test public void testSinkLoopStores() { + var code = new CodeGen(""" + struct S { int x; }; + !S !a = new S; + a.x = 10; + int i = 0; + while (i < arg) { a.x = i + 1; i++; } + return a; + """).driver(CodeGen.Phase.LocalSched); + int[] stores = {0}; + code._stop.walk(n -> { + // Constructor zero Stores remain in separate private memory. + if( n instanceof com.seaofnodes.simple.node.StoreNode st && st._name.equals("x") && + st.val() instanceof com.seaofnodes.simple.node.PhiNode ) { + assertEquals(0,st.cfg0().loopDepth()); // One final Store outside the loop. + stores[0]++; + } + return null; + }); + assertEquals(1,stores[0]); + for( int arg : new int[]{-1,0,1,4} ) { + long expected = arg<=0 ? 10 : arg; + assertEquals("Test.S{x="+expected+"}",Eval2.eval(code,arg)); + } + } + + @Ignore @Test public void testJig() { diff --git a/docs/chapter-backports.md b/docs/chapter-backports.md index d10dc761..15bf73e6 100644 --- a/docs/chapter-backports.md +++ b/docs/chapter-backports.md @@ -6,19 +6,8 @@ live in the [AI notes](../skills/chapter25-codex-notes.md). ## Investigate next -These are candidates, not confirmed missing correctness fixes. Establish an -earlier-chapter failure before changing compiler behavior. - -### Conditional Store control - -Compare conditional field writes under each destination's memory-Phi and alias -model. Chapter 24 attaches control to array stores but lets ordinary field -stores rely on memory dependencies. Chapter 25's explicit Store control input -is not by itself evidence that the earlier representation is wrong. - -Keep this investigation separate from GCM's memory-Phi anti-dependency walk. -Use the existing read-before-conditional-store regression as a guard, and find -a distinct failing program before adding more control constraints. +Establish an earlier-chapter failure before changing compiler behavior. +The remaining candidate below is not yet confirmed. ### SCCP function revival: Chapter 24 diff --git a/skills/chapter25-codex-notes.md b/skills/chapter25-codex-notes.md index f66b2c65..f16407e7 100644 --- a/skills/chapter25-codex-notes.md +++ b/skills/chapter25-codex-notes.md @@ -321,25 +321,35 @@ For shared viewer work, read [the graph viewer notes](graph-viewer-codex-notes.m User-count dependencies must wake from Node.delUse, including unkeep. - Generalized Phi factoring now starts in 10 and is forwarded through 25. - Memory-specific eligibility lives in `MemOpNode.canDrop`, with virtual Load - and Store checks. Load owns `clobbered`: all these chapters check only - immediate memory users, without recursion or a visited set. Stop at Stores, - Phis, MemMerges (11+), New (15+), and Calls (18+); do not chase aliases or aggregates just - to save one Load. Keep this teaching optimization simple and conservative. + Memory-specific eligibility lives in `MemOpNode.canDrop`. Store identity + equality now excludes Stores from this rewrite. Load owns `clobbered`: all + these chapters check only immediate memory users, without recursion or a + visited set. Stop at Stores, Phis, MemMerges (11+), New (15+), and Calls (18+); + do not chase aliases or aggregates just to save one Load. Keep this teaching + optimization simple and conservative. Preserve exact operation attributes with clone-based `copyEmpty`, type each operand Phi separately, reuse identical inputs, and reject type widening. - Stores require sole use by the Phi; Loads inspect memory users for clobbers - before GCM has made anti-dependence edges. From 11, create precise memory + Loads inspect memory users for clobbers before GCM has made anti-dependence + edges. From 11, create precise memory Phis for the factored operands. Do not factor aggregates or bulk Phis; wait for other BulkMemPhis at the Region to disappear, since their slice - lookup assumes Region/alias identifies the completed memory point. Existing - control-bound Stores in 13-14 remain ineligible. `delUse` wakes recorded - dependents for user-count queries; Region's empty-diamond fold depends on + lookup assumes Region/alias identifies the completed memory point. `delUse` + wakes recorded dependents for user-count queries; Region's empty-diamond fold depends on projection rewiring as well as projection types. These guards are already forwarded through 25; preserve the later chapters' existing `copyEmpty`. `subsume` must wake each rewired user's recorded dependents, just as `setDef` does: operand identity changes can enable a Phi fold without changing the intervening operation's type (`Chapter14Test.testCloneAnd` in 16). +- Stores use identity equality from Chapter 10 onward. Equal Stores on two of + three paths must not merge and run on the third path. Sharing requires the + original Stores to cover every exit path, or GCM to split the shared Store + back onto those paths. GVN checks neither, and GCM does not split Stores. + This also disables generic Phi factoring of Stores, but keeps explicit + store-after-store elimination and the closed-loop sink introduced in 17b. + `Chapter10Test.testConditionalStoreSharing` returns the object to expose the + actual write; returning a Load could hide it through forwarding. + `Chapter17bTest.testSinkLoopStores` checks exit placement and zero-trip values + in 17b and every later snapshot. Do not restore Store GVN to recover a fold. - Find the chapter where the relevant feature first appears, not just the chapter that can parse the original reproducer. Reduce away later syntax/features when possible. Put the regression in that earliest `ChapterNTest.java`, and forward |