単一関数内解析アルゴリズム

まず，文の削除・挿入・修正それぞれに共通な前定義節点の発見のためのアルゴリズム を示し，次に削除・挿入・修正のアルゴリズムを示す．

2.4.1 前定義節点の発見

このアルゴリズムではフロー辺を遡り，節点での定義・参照変数を調べることにより前 定義節点を求める．このアルゴリズムは2.4.2節〜2.4.4節において用いる．

アルゴリズムFINDPREDE F

input: 節点s，変数v

output: 前定義節点集合P reDef(s, v)

2

1. P reDef(s, v)←φ

2. c∈prev(s)^なる各cに対して以下を順に実行．

(a) cにおいてvが定義されていれば，

P reDef(s, v)←P reDef(s, v) ∪ {c} (b) cにおいてvが参照されていれば，

P reDef(s, v)←P reDef(s, v) ∪ source(c, v)

(c) cにおいてvが定義も参照もされていなければ，c←prev(c)^として2a.以下を 実行．

2.4.2 削除

節点を削除することにより，その文における変数の定義が無効となる．そのような変数 に関するデータ依存辺を引き直し，その後節点を削除する．

アルゴリズムDELET EVERTE X

input: 削除する節点s output: 更新されたPDG

1. sで定義されている各変数vすべてについて，DD ←DD∪ {r v^-t |r∈P reDef(s, v), t∈ target(s, v)}

2. DD ←DD− {r v^-s |r∈source(s, v)} − {s v^-t |t∈target(s, v)}

3. F LOW ← F LOW ∪ {p→n |

p∈prev(s), n∈next(s)} − {r →s |r∈prev(s)} − {s→t |t∈next(s)}

4. 節点s自身を削除

2.4.3 挿入

このアルゴリズムではまず，フロー辺をつけかえる．次に，挿入する節点で定義する変 数を参照する節点へデータ依存辺を引く．また，挿入によって依存関係の無くなるデータ 依存辺を削除する．最後に，挿入する節点で参照する変数のデータ依存辺を引く．

アルゴリズムINSE RTVERTEX

input: 挿入する節点s，prev(s)^，next(s) output: 更新されたPDG

但し，手続き・関数・プログラムの入口においてすべての変数を定義したものとみなす．

1. F LOW ← F LOW ∪ {p→s | p ∈ prev(s)} ∪ {s→n | n ∈ next(s)} − {p→n |p∈prev(s), n∈next(s)}

2. sで定義している各変数vすべてについて，以下を実行．

(a) 各r ∈ P reDef(s, v), t ∈ target(r, v)^{に対して，}vを定義しないようなパス s,· · ·, tが存在すれば，以下を実行．

i. DD ←DD ∪ {s v^-t}

ii. 任意のr∈P reDef(s, v)^に対してvを定義しないようなパスr,· · ·, tが存 在しなければ，

DD ←DD− {r v-t |r ∈P reDef(s, v)}

3. sで参照している各変数uについて，

DD←DD∪ {r u^-s |r∈P reDef(s, u)}

2.4.4 修正

このアルゴリズムは，削除アルゴリズムと挿入アルゴリズムを組み合わせることによっ て実現している．

変数集合V を定義し変数集合Uを参照する節点sを，変数集合Vを定義し変数集合U を参照するように修正したとする．

アルゴリズムMOD IFYVERTEX

input: 節点s，変更後の定義変数集合V，変更後の参照変数集合U

output: 更新されたPDG 1. F LOW ←F LOW 2. v∈V −Vに対して，

DD ←DD∪{r v^-t |r ∈P reDef(s, v), t∈target(s, v)}−{s v t^- |t∈ target(s, v)}

3. v∈V−V に対して，

(a) 各r ∈ P reDef(s, v), t ∈ target(r, v)に対して，vを定義しないようなパス s,· · ·, tが存在すれば以下を実行．

i. DD←DD∪ {s v^- t}

ii. 任意のr∈P reDef(s, v)に対して，vを定義しないようなパスr,· · ·, tが 存在しなければ，

DD ←DD− {r v^- t |t∈P reDef(s, v)}

4. u∈U−Uに対して，

DD ←DD− {r u-s |r∈P reDef(s, u)}

5. u ∈U−U に対して，

DD ←DD∪ {r u^- s |r∈P reDef(s, u)}