コンパイラ演習 第 8 回 (2011/12/01) 中村 晃一 野瀬 貴史 前田 俊行 秋山 茂樹 池尻 拓朗 鈴木 友博 渡邊 裕貴 中村 晃一　野瀬 貴史　前田 俊行 秋山 茂樹　池尻 拓朗 鈴木 友博　渡邊 裕貴 潮田 資秀 小酒井 隆広 山下 諒蔵　佐藤 春旗 大山 恵弘　佐藤 秀明 住井 英二郎

今回の内容 データフロー解析とそれに基づく最適化手法

マシン依存性による最適化の分類 マシン非依存 マシン依存 両者に関係 静的に評価出来る部分をコンパイル時に計算 無駄な評価・計算を減らす パイプライン効率を上げる キャッシュ効率を上げる 両者に関係 並列度を上げる オーバヘッド除去

局所性による最適化の分類 局所的最適化 大域的最適化 Peephole 最適化 基本ブロック内最適化 基本ブロック間最適化 関数間最適化 プログラム間最適化

今回のターゲット マシン非依存 基本ブロック間 の データフロー解析法 最適化手法 を扱います。

今回説明する基本ブロック間最適化 コピー伝播 定数畳みこみ 共通部分式除去 値番号付け 部分冗長性除去 今回は到達定義解析・定義使用解析 に基づくアルゴリズムを紹介します。

基本ブロック間最適化の手順 制御フローグラフを構築 データフロー解析をする 最適化を行う 以上を個々の関数毎に行う

基本ブロックとは 入ってから出るまで一直線な プログラム片 １．途中での合流が無く、 ２．途中からの脱出が無い 途中に関数呼び出しを含む ブロックを許すか否かは 最適化の種類による 基本ブロック let x = f() in if x > 0 then let y = - x in … else let y = x in …

準備：ループの検出 MinCaml には明示的なループが存在しない → そのままでは関数間解析をしないと 高度な最適化が難しい。 単純な方法 → そのままでは関数間解析をしないと 高度な最適化が難しい。 単純な方法 自己末尾再帰呼び出しを while 型ループへ n = 0 let rec f n = if n < 10 then (…; f (n+1)) else () in f 0 if n < 10 … n = n + 1

準備：代入構文の用意 ループ作成によって必要になる 変数の更新を表現 左の様な let 文も右のように変換 let rec f n = if n < 10 then (…; f (n+1)) else () in f 0 if n < 10 … n  n + 1 変数の更新 変数の更新 if ... let x = if ... then e1 else e2 x  e1 x e2

制御フローグラフ 関数 body を基本ブロックを頂点、 制御移行を辺として グラフを作る 空の entry,exit ブロックを用意 入口・出口を用意しておくと あとあと楽 entry exit

データフロー解析 (前方解析) In[p] : D (ポイント p の入口でのデータ) Out[p]: D (ポイント p の出口でのデータ) pred: P2P (ポイント p の一つ前のポイントの集合を得る関数) f p: DD (ポイント p における伝達関数) すべてのポイント p について In[p], Out[p] を求める p1 p2 Out[p1] Out[p2] In[p3] p3

データフロー解析 (後方解析) In[p] : D (ポイント p の入口でのデータ) Out[p]: D (ポイント p の出口でのデータ) succ: P2P (ポイント p の一つ後のポイントの集合を得る関数) f p: DD (ポイント p における伝達関数) すべてのポイント p について In[p], Out[p] を求める p1 Out[p1] In[p2] In[p3] p2 p3

基本となるデータフロー解析 到達定義解析 定義使用解析 ある場所で使用される物(変数、式など)が どこで定義されたか? ⇒ 前方解析 ある場所で定義された変数が どこで使用されるか？ ⇒ 後方解析 一方から容易に他方を求める事が出来る。 今回は到達定義解析の結果から定義使用解析を行う

到達定義解析 データフロー解析の一種 使用される変数や式が どこで定義されているかを調べる 流れ まずプログラムポイントを基本ブロックとして解析 続いて基本ブロック毎に、 プログラムポイントを その中のステートメントとして解析

ブロック単位の到達定義解析： reach 集合 reach[B]: 基本ブロック B の入り口に到達する定義文の集合 これを計算する事が 解析の目標 s1: i = 0 s2: s = 0 reach[B1] = Φ reach[B2] = {s1, s2, s5, s6, s7} reach[B3] = {s1, s2, s5, s6, s7} B1 s3: if i < 100 B2 s4: t = i s5: t = 2*t s6: i = i + 1 s7: s = s + t B3

ブロック単位の到達定義解析： def 集合 def[B]: 基本ブロック B の中の定義文で B の出口で有効なものの集合 s1: i = 0 s2: s = 0 def[B1] = {s1, s2} def[B2] = Φ def[B3] = {s5, s6, s7} B1 s3: if i < 100 B2 s4: t = i s5: t = 2*t s6: i = i + 1 s7: s = s + t B3

ブロック単位の到達定義解析： kill 集合 kill[B]: B の出口で無効化される定義文の集合 制御フローは考慮しなくてよい B 内の文によって無効化され得る全ての定義文を集める。 s1: i = 0 s2: s = 0 kill[B1] = {s6, s7} kill[B2] = Φ kill[B3] = {s1, s2} B1 s3: if i < 100 B2 s4: t = i s5: t = 2*t s6: i = i + 1 s7: s = s + t B3

到達定義解析のデータフロー方程式 X とすれば以下を得る。 Ｂ fB(X)

到達定義解析のアルゴリズム 全ての基本ブロック B について def[B] と kill[B] を計算し、 reach[B] := Φとする reach[entry] := {arguments, global variables, ・・・} do { old_reach := reach # 集合としてコピー 全ての基本ブロック B について { 全ての基本ブロック b ∈ pred(B) について { reach[B] := reach[B] ∪ def[b] ∪ (reach[b] ＼ kill[b]) } } while (old_reach != reach) # 集合として比較

到達定義解析の具体例 reach[B1] = Φ reach[B2] = Φ reach[B3] = Φ s1: i = 0 s2: s = 0 B1 s3: if i < 100 B2 def[B1] = {s1, s2} def[B2] = Φ def[B3] = {s5, s6, s7} s4: t = i s5: t = 2*t s6: i = i + 1 s7: s = s + t B3 kill[B1] = {s6, s7} kill[B2] = Φ kill[B3] = {s1, s2} ※ここでは entry, exit を省略している

到達定義解析の具体例 reach[B1] = Φ reach[B2] = {s1,s2} reach[B3] = Φ B1∈pred(B2) の def reach[B1] = Φ reach[B2] = {s1,s2} reach[B3] = Φ s1: i = 0 s2: s = 0 B1 s3: if i < 100 B2 def[B1] = {s1, s2} def[B2] = Φ def[B3] = {s5, s6, s7} s4: t = i s5: t = 2*t s6: i = i + 1 s7: s = s + t B3 kill[B1] = {s6, s7} kill[B2] = Φ kill[B3] = {s1, s2} ※ここでは entry, exit を省略している

到達定義解析の具体例 reach[B1] = Φ reach[B2] = {s1,s2,s5,s6,s7} reach[B3] = Φ B3∈pred(B2) の def reach[B1] = Φ reach[B2] = {s1,s2,s5,s6,s7} reach[B3] = Φ s1: i = 0 s2: s = 0 B1 s3: if i < 100 B2 def[B1] = {s1, s2} def[B2] = Φ def[B3] = {s5, s6, s7} s4: t = i s5: t = 2*t s6: i = i + 1 s7: s = s + t B3 kill[B1] = {s6, s7} kill[B2] = Φ kill[B3] = {s1, s2} ※ここでは entry, exit を省略している

到達定義解析の具体例 reach[B1] = Φ reach[B2] = {s1,s2,s5,s6,s7} s1: i = 0 s2: s = 0 B1 s3: if i < 100 B2 B2∈pred(B3) のreach＼kill def[B1] = {s1, s2} def[B2] = Φ def[B3] = {s5, s6, s7} s4: t = i s5: t = 2*t s6: i = i + 1 s7: s = s + t B3 kill[B1] = {s6, s7} kill[B2] = Φ kill[B3] = {s1, s2} ※ここでは entry, exit を省略している

到達定義解析の具体例 reach[B1] = Φ reach[B2] = {s1,s2,s5,s6,s7} s1: i = 0 s2: s = 0 B1 変化なし 変化なし s3: if i < 100 B2 def[B1] = {s1, s2} def[B2] = Φ def[B3] = {s5, s6, s7} s4: t = i s5: t = 2*t s6: i = i + 1 s7: s = s + t B3 kill[B1] = {s6, s7} kill[B2] = Φ kill[B3] = {s1, s2} ※ここでは entry, exit を省略している

ステートメント単位の到達定義解析 変数の到達定義解析の場合以下を計算 s をブロック B の文とすると、reach[s,x] は reach[s, x] : ステートメント s で使用されている変数 x を定義している文集合 s をブロック B の文とすると、reach[s,x] は B 内の s の先行命令が x を定義していれば それのみ そうでなければ、reach[B] に含まれる x を定義している文集合 として計算できる

ステートメント単位の到達定義解析の例 例えば reach[s6,i] についてみてみる B3 の先行命令(S4,s5)は I を定義しないのでreach[B] を見る。 reach[B] 内 で i を定義している文は s1 と s6 従って s1: i = 0 s2: s = 0 B1 reach[B3] = {s1,s2,s5,s6,s7} s3: if i < 100 B2 reach[s6,i] = {s1, s6} s4: t = i s5: t = 2*t s6: i = i + 1 s7: s = s + t B3

ステートメント単位の到達定義解析の例 最終結果 reach[s3, i] = {s1, s6} reach[s5,t] = {s4} reach[s6,i] = {s1, s6} reach[s7,s] = {s2, s7} reach[s7,t] = {s5} s1: i = 0 s2: s = 0 B1 s3: if i < 100 B2 s4: t = i s5: t = 2*t s6: i = i + 1 s7: s = s + t B3

定義使用解析 以下を計算する 計算方法 use[s] : ステートメント s で定義されている変数 x を使用している文集合 use[s] = { t | s ∈ reach[t, x], x は s が定義する変数}

定義使用解析の例 use[s1] = {s3, s4, s6} use[s2] = {s7} use[s4] = {s5} s1: i = 0 s2: s = 0 s3: if i < 100 reach[s3, i] = {s1, s6} reach[s4, i] = {s1, s6} reach[s5,t] = {s4} reach[s6,i] = {s1, s6} reach[s7,s] = {s2, s7} reach[s7,t] = {s5} s4: t = i s5: t = 2*t s6: i = i + 1 s7: s = s + t

実際の最適化の例: コピー伝播 変数の到達定義解析・定義使用解析を利用 copyprop(prog) { worklist := (let x = v(変数)の形の文) while (worklist != Φ) { s := worklist.pop foreach(t in use[s]) { x := s が定義する変数 if (|reach[t,x]| == 1) { # t に到達する変数が 1 つしかない t 内の x の使用を v に置換 worklist.add(t) if t が let x’ = v’ の形で worklist に存在しない }

実際の最適化の例: 定数畳みこみ 変数の到達定義解析・定義使用解析を利用 constfold(prog) { worklist := 定数定義文 while (worklist != Φ) { s := worklist.pop foreach(t in use[s]) { x := s が定義する変数 x を定数値に置換 if reach[t,x] の全てが同じ値を定義 静的に t を評価 if t の全引数が定数 worklist.add(t) if t の計算結果が定数 }

実際の最適化の例: 共通部分式除去 「利用可能な式」の到達定義解析を行う Eavail[B]: ブロック B の入口で利用可能な式集合 ここでは基本ブロック単位の解析を説明する Eavail[B]: ブロック B の入口で利用可能な式集合 Ekill[B]: ブロック B 内でオペランドが 上書きされる式集合 Edef[B]: ブロックB内にある式で 出口で利用可能な式集合 として以下を解く (∪でなく∩となる点に注意) その後ステートメント単位での解析をする

共通部分式除去の例 x = i * 4 y = a + x p = load y x = i * 4 y = b + x reach = {i * 4, a + x} p = load y x = i * 4 y = b + x q = load y reach = {i * 4} p = i * 4 z = a + x i * 4が共通部分式になっている ※右のパスで x が上書きされるので a + x はここに到達しない。

共通部分式除去の例 x = i * 4 i * 4 の為の一時変数を作って… t = x y = a + x p = load y reach = {i * 4, a + x} p = load y x = i * 4 y = b + x q = load y reach = {i * 4} p = i * 4 z = a + x

共通部分式除去の例 x = i * 4 t = x y = a + x p = load y x = t y = b + x reach = {i * 4, a + x} p = load y x = t y = b + x q = load y reach = {i * 4} 共通部分式を除去 p = t z = a + x

実際の最適化の例: 値番号付け 先ほどのアルゴリズムでは 例えば下の様なものが解決出来ない a = 1 b = 1 c = a + 2 d = b + 2 同じ値を持つが共通部分式じゃない a = b + c d = b e = d + c 同じ値を持つが共通部分式じゃない

実際の最適化の例: 値番号付け 式の「値」を「番号」で識別して 共通な値を見つける b = ① c = ② a = ③ （③=①+②) d = ① e = ③ a = b + c d = b e = d + c a = 1 b = 1 c = a + 2 d = b + 2 a = ① b = ① c = ② (②＝①＋２) d = ②

実際の最適化の例: 部分冗長性除去 値番号付けでも 部分冗長なケースは 解決できない x = a + b このパスでだけ y = a + b

部分冗長性除去: 簡単なアイデア 式を挿入して全冗長にする z = a + b x = a + b z = a + b y = a + b

部分冗長性除去 手順 以下 a + b という形の一つの式に注目する 共通部分式の除去 危険辺の除去 入口計算・出口計算・挿入点を検査 上安全性・下安全性の検査 挿入点を求める 今回はせわしいコード移動 (busy-code-motion) という方法を紹介 式をできるだけ前方へ挿入する 以下 a + b という形の一つの式に注目する

危険辺の除去 ２つ以上の後続ブロックを持つブロックから、 ２つ以上の先行ブロックを持つブロックへの辺を新たにブロックを挿入して除去 y = a + b y = a + b ここに a + b を挿入すると 後続のパスに影響 ここなら a + b を挿入しても 大丈夫

入口計算・出口計算 ブロック B 内に a, b への代入文がある場合、 その最後の代入文の直後で分割 ブロックの集合をBとして 入口計算: 入口部分にあり、かつ a, b の代入より前にある a + b 出口計算: 出口部分にある a + b ブロックの集合をBとして NCompa+b: BBoolean (ブロック B が入口計算を持つ) XCompa+b: BBoolean (ブロック B が出口計算を持つ ) Transpa+b: BBoolean (ブロック B 内に a, b への代入文がない) x = a + b a = 2 b = x + b y = a + b x = a + b a = 2 b = x + b y = a + b 入口計算 出口計算

挿入点 以下の 2 つのプログラムポイントを「挿入点」と呼ぶ 入口挿入点 出口挿入点 x = a + b a = 2 b = x + b 入口計算の直前 (入口計算がなければ基本ブロックの先頭) 出口挿入点 出口計算の直前 (出口計算がなければ基本ブロックの最後) 入口挿入点 x = a + b a = 2 b = x + b y = a + b x = a + b a = 2 b = x + b y = a + b 入口計算 出口挿入点 出口計算

上安全性・下安全性 ある挿入点に a + b を代入しても安全かどうか 上安全性 下安全性 entryからその点までの どのパスにも a + b があり全部同じ値 下安全性 その点から exit まで どのパスにも a + b があり全部同じ値 NuSafea+b[B] : Boolean (B の入口挿入点で上安全) XuSafea+b[B] : Boolean (B の出口挿入点で上安全) NdSafea+b[B] : Boolean (B の入口挿入点で下安全) XdSafea+b[B] : Boolean (B の出口挿入点で下安全)

上安全性・下安全性の解析 NdSafe, XdSafe は以下の方程式で計算できる NuSafe, XuSafe も同様

せわしいコード移動 下安全で出来るだけ前方の挿入点に t = a + b を挿入 NEarlist[B] = trueである B の入口挿入点, XEarliest[B] = trueである B の出口挿入点に t = a + b を挿入 すべての入口計算・出口計算を t に置換

その他最適化のヒント: Do-All 型ループの検出 後の回やる並列化・キャッシュ最適化等に 欠かせない作業 Do-All 型ループとは i = a,a+d,a+2d,…,a+(k-1)d と順番に回すループ while ループには既に直してあるのだから インデックス変数 i を見つけてやればよい for (i = a; i < n; i += d) { … }

Do-All 型ループの検出: 帰納的変数検出 i0 = a in+1 = in + d ループ脱出条件により i の上限 (下限) が決定出来る 到達定義解析の結果から 右のようなパターンを 見つければよい i = a if ループ脱出条件 i = i + d

帰納的変数の検出(例) s1: i = 0 s2: s = 0 s = 0 s3: if i < 100 for (i=0;i < 100; i++) t = i t = 2*t s = s + t s4: t = i s5: t = 2*t s6: i = i + 1 s7: s = s + t

共通課題 二つの共通課題のうち 一つ以上を解いてください

課題1 MinCamlに到達定義解析を実装し それを用いた最適化 (最低1つ) を実装せよ。 第2回で扱った到達定義解析に寄らない最適化 と比較し評価せよ。

課題2 今回紹介した単純な部分冗長性除去では 上手く冗長性が除去出来ないプログラムや 遅くなってしまうプログラムがある その例を挙げ、改善する方法を考えよ 参考文献 Knoop, J., Ruthing, O., and Steffen, B. Lazy Code Motion. ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI. VanDrunen, T., and Hosking, A.L. Value-Based Partial Redundancy Elimination, Lecture Notes in Computer Science Vol. 2985/2004, pp. 167 - 184, 2004. Kennedy, R., Chan, S., Liu, S.M., Lo, R., Peng, T., and Chow, F. Partial Redundancy Elimination in SSA Form. ACM Transactions on Programming Languages Vol. 21, Num. 3, pp. 627-676, 1999.

コンパイラ係用課題 関数間解析・エイリアス解析など さらに高度な解析と それを用いた最適化を実装せよ

課題の提出先と締め切り 提出先: compiler-report-2011@yl.is.s.u-tokyo.ac.jp 締め切り: 2 週間後 (12/15) の午後 1 時 コンパイラ係用課題の締め切り: 2012 年 2月 27日 Subject: Report 8 <学籍番号: 5 桁> 例： Report 8 11099 本文にも氏名と学籍番号を明記のこと 半角スペース 1 個ずつ 質問は compiler-query-2011@yl.is.s.u-tokyo.ac.jp まで