diff options
Diffstat (limited to 'chapter10')
| -rw-r--r-- | chapter10/README.ja.md | 12 | ||||
| -rw-r--r-- | chapter10/README.md | 33 | ||||
| -rw-r--r-- | chapter10/src/main/java/com/seaofnodes/simple/node/StoreNode.java | 8 | ||||
| -rw-r--r-- | chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java | 27 |
4 files changed, 56 insertions, 24 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]); } |