使用定義連鎖

use-define chain

各使用天に到達するすべての定義を列挙したものが使用定義連鎖

使用定義連鎖の情報を使用し、コード最適化に役立てる

各変数の使用点、定義点を検出し、使用定義連鎖を作る

使用点は普通にその変数を使っている場所

定義点は、代入や再代入を行った場所

以下の図の点線が使用定義連鎖

https://gyazo.com/39a0407ff2b3066fbb8868d41b6a89c3

定義d2は使用されるまでに必ず再定義される経路しかないので、

使用点からd2への点線はない

定義d1は、ある経路では上書きされることもあるが、ある経路ではそのまま使用されることもあるので

使用点からd1への点線がある

GEN集合とKILL集合を求める

$ \mathrm{OUT}(B)=\mathrm{GEN}(B)\cup(\mathrm{IN}(B)-\mathrm{KILL}(B))

INはこのブロックに入ってくる定義の集合

GENはそのブロックの中での新たな定義の集合

KILLはそのブロックの中で消滅する定義の集合

最終的に欲しいのはINとOUT

求める順序

まず小さい単位である1文ずつ求める

この文は代入文以外の場合は影響がないので、考えなくていい

次に基本ブロックごとに求める

最後に基本ブロック間で求める

つまり、フローグラフ全体

『コンパイラとバーチャルマシン』.icon p.96のアルゴリズムを用いる

参考