DAGを用いた最適化
メリット
共通部分式を自然に認識できる
不要な代入文を削除できる
代数的性質を利用した最適化を容易に行える
式eを式e'に変換する場合
式eにマッチする部分DAGを容易に見つけられる
そのDAGを式e'に対応する部分DAGに容易に変換できる
DAGから得られる代入文の並べ方はたくさんあるので、レジスタ割当などの目的コード生成に適した並べ方を選ぶ事ができる
具体例
以下のコードに対して実行する
code:example
x=a*b ①
y=x+c ②
d=a*b ③
e=d-c ④
x=d+e ⑤
① x=a*b
*をラベルとして持つ頂点を生成
その子が、aとbをラベルとして持つ頂点になる
https://gyazo.com/35e097a3b7dad89fc5314d56a508ae92
② y=x+c
同じ
https://gyazo.com/2244efc24432cac9f3375f31ee41cd72
③ d=a*b
a*bに対応する部分DAGがすでに存在するので、ラベル*のリストにdを追加
https://gyazo.com/ed89d54a1c1862915fb0911f31a1c979
④ e=d-c
https://gyazo.com/21e5f1b953c450d846cbe76cdd0366dc
⑤ x=d+e
xのラベルの位置を変更する
以前に定義されたものは削除してる
https://gyazo.com/b972069449b82255bfc8706e3a3ab87e