Inline 展開のアルゴリズム 長谷川啓 2018.12.02.

Presentation on theme: "Inline 展開のアルゴリズム 長谷川啓 2018.12.02."— Presentation transcript:

1 inline 展開のアルゴリズム 長谷川啓

2 inline 展開をいつするか? (1) 函数呼び出し演算子が inline 定義された函数に対して適用されたら、一度、inline ではない函数呼び出しの 3 番地コードを生成し、 inline 展開のアルゴリズムを適用する。 このタイミングで inline 展開すると最適化ルーチンの適用は一回で済む

3 inline 展開をいつするか? (2) 函数呼び出し演算子が inline 宣言されてはいるが、定義がまだされていない函数 f に対して適用されたら、前ページと同様に、まず inline ではない函数呼び出しの3番地コードを生成しておく。 このような呼び出しをした函数 g は、g に対するアセンブリコード生成をすぐにしないで f が定義されるまで保留する。つまりバックエンドジェネレータには何もさせない。 static や inline 函数が定義されたときの保留の仕組みを使う f が定義されたときに、g の f 呼び出しに対して inline 展開アルゴリズムを適用する。g に他の inline 函数呼び出しがなく、g そのものが static でも inline でもないならば g のコード生成を完了させる。 g が static か inline ならば参照されていないという理由でコード生成は保留される。この後 g が参照されたときに inline 展開されたコードを生成できるようにしておく。 g は inline 展開前に一度最適化ルーチンが適用される。inline 展開アルゴリズム適用後もう一度最適化ルーチンを適用すれば、さらに最適化される可能性はある。

4 後で inline 函数が定義されたときにinline 展開するためのデータ構造
namespace defer { map<inline 宣言されている函数名, (inline 宣言されている函数, 参照箇所)> refs; map<inline 宣言されている函数名, set<呼び出している函数> > callers; map<呼び出している函数, vector<int> > positions; }

5 例1 inline int f(int a, int b, int c){ if (a) return (b+c)/a; return b-c; } inline void g1(int, int); inline int g2(int, int); int h(int i, int j, int k){ g1(j,k); return f(i,j,k) – g2(k,i); } inline void g1(int d, int e){ if (!e) return; if (d) printf("%d\n", e); } inline int g2(int x, int y){ if (x) return x+y; return y * y; }

6 inline int f(int a, int b, int c){ if (a) return (b+c)/a : b-c; }
skip::table[f] に f, f のパラメータスコープ, f の3番地コード if a == 0 goto label0 t0 := b + c t1 := t0 / a return t1 label0: t2 := b - c return t2 が追加される

7 h での f 呼び出しは以下のように変換される
param i => a := i param j => b := j param k => c := k t3 := call f => if a == 0 goto label0 t0 := b + c t1 := t0 / a return t1 => t3 := t1 goto label1 label0: t2 := b - c return t2 => t3 := t2 goto label2 => label1: (追加) => label2: (追加)

8 defer::positions[h] inline 展開されたコード defer::positions[h]
int h(int i, int j, int k){ g1(j,k); return f(i,j,k) – g2(k,i); } param j param k call g1 a := i b := j c := k if a == 0 goto label0 t0 := b + c t1 := t0 / a t3 := t1 goto label1 label0: t2 := b - c t3 := t2 goto label2 label1: label2: param i t4 := call g2 t5 := t3 - t4 return t5 defer::positions[h] inline 展開されたコード defer::positions[h]

9 inline 展開された 3 番地コードは追加されるブロックスコープのエントリを参照するようにする
scope::root h のパラメータスコープ m_usrs : i, j, k m_usrs : f, g1, g2 h のボディ m_vars : t4, t5 追加されるブロックスコープ inline 展開された 3 番地コードは追加されるブロックスコープのエントリを参照するようにする m_vars : a, b, c 追加されるブロックスコープ m_vars : t0, t1, t2, t3

10 h のアセンブリコード生成は保留される skip::table[h] に h のパラメータスコープ、3番地コード等が登録される
defer::callers[g1] に h を追加 defer::positions[h] に g1 の呼び出し位置を記録する defer::callers[g2] に h を追加 defer::positions[h] に g2 の呼び出し位置を記録する

11 inline void g1(int d, int e){ if (
inline void g1(int d, int e){ if (!e) return; if (d) printf("%d\n", e); } skip::table[g1] に g1, g1 のパラメータスコープ, g1 の3番地コード if e != 0 goto label4 return label4: if d == 0 goto label5 t6 := &"%d\n" param t6 param e call printf label5: が追加される

12 defer::callers[g1] から defer::positions[h] をたどり、h の3番地コードにおける g1 の呼び出しを inline 展開する
param j => d := j param k => e := k call g1 => if e != 0 goto label4 reurn => goto label6 label4: if d == 0 goto label5 t6 := &"%d\n" param t6 param e call printf label5: => label6: (追加)

13 defer::callers[g1] のエントリ defer::positions[h] の g1 の呼び出し位置
⇒削除される defer::positions[h] には g2 の呼び出し位置 がまだ残っている defer::positions[h] の g2 の呼び出し位置に g1 の inline 展開により増大したコード数を加算しておく g1 の呼び出し位置が g2 の呼び出し位置よりも先だったので加算する。そうでなければ加算しない。 skip::table[h] は残したまま h のアセンブリコード生成は保留

14 inline int g2(int x, int y){ if (x) return x+y; return y * y; }
skip::table[g2] に g2, g2 のパラメータスコープ, g2 の3番地コード if x == 0 goto label7 t7 := x + y return t7 label7: t8 := y * y return t8 が追加される defer::callers[g2] から defer::positions[h] をたどり、h の3番地コードにおける g2 の呼び出し部分を inline 展開する

15 param k => x := k param i => y := i t4 := call g2 =>
if x == 0 goto label7 t7 := x + y return t7 => t4 := t7 goto label8 label7: t8 := y * y return t8 => t4 := t8 goto label9 label8: (追加) label9: (追加)

16 inline 展開のアルゴリズム 入力 出力 呼び出し側の函数の 3 番地コードと inline 函数の呼び出し位置
inline 函数、inline 函数のパラメータスコープ、inline 函数の3番地コード 出力 inline 展開された 3 番地コード call に置き換わった 3 番地コードの数

17 param a1 ... param an x := call f
inline 函数 f が n 個の引数をとるならば inline 函数の呼び出しの前に n 個の param 3番地コードがある。これらを pi := ai に変更する。pi は f の i 番目のパラメータのコピーである。 p1, ..., pn を追加したブロックスコープに登録する。

18 call f に置き換わった3番地コードの数はfの3番地コードの数とその中の return y の数との和である。
x := call f あるいは call f を f の3番地コードのコピーに置き換える 上で置き換えた3番地コードでは p1, ..., pn以外にパラメータ以外のローカル変数、中間変数もオペランドになっている。これらのコピーを追加したブロックスコープに登録する。 置き換えた3番地コードの return y は x := y goto end に置き換える。end は新しいラベルで x := call f に対して置き換えた最後に貼る。 y がない場合は x := y を生成しない y はあるが x がない場合も生成しない call f に置き換わった3番地コードの数はfの3番地コードの数とその中の return y の数との和である。

19 可変個引数を取る inline 函数 あきらめる。 inline 展開できそうな例
inline int printf(const char* fmt, ...) { va_list ap; va_start(ap, fmt); vfprintf(fmt, ap); ... } void f(int a, double b) { printf(“%d %f\n”, a, b); }

20 可変個引数を取る inline 函数(2) 前ページの3番地コード printf: inline 展開後の f f: f:
ap := va_start fmt param fmt param ap call vfprintf ... f: t0 := &”%d %f\n” param a param b call printf inline 展開後の f f: t0 := “%d %f\n” fmt := t0 param a param b call vfprintf ...

21 可変個引数を取る inline 函数(3) inline 展開が難しい例
inline int printf(const char* fmt, ...) { va_list ap; va_start(ap, fmt); ... int n = va_arg(ap, int); }

22 例2 inline int h(int, int); int main(){ h の呼び出し }
inline int f0(int a, int b){ ... } inline int f1(int a, int b){ ... } inline int g0(int, int); inline int g1(int, int); int h(int a, int b){ f0, f1, g0, g1 の呼び出し } inline int g0(int a, int b){ ...} inline int g1(int a, int b){ ... }

23 main まで読み込んだ後 h を読み込む前 h まで読みこんだ後 g0 まで読み込んだ後 g1 まで読み込んだ後
main は skip::table に入る main から inline 宣言された h の呼び出しがあるから h を読み込む前 f0, f1 は通常通り skip::table に入る h まで読みこんだ後 h は skip::table に入る h が inline 宣言されているから callers[h] に main があるので main の h 呼び出しは inline 展開される main のコード生成ルーチン inline 宣言された g0, g1 の呼び出しがあるので再び skip::table に入る g0 まで読み込んだ後 g0 は通常通り skip::table に入る callers[g0] に main があるのでそれぞれ inline 展開される main には inline 宣言された g1 の呼び出しがまだあるので skip::table から削除しない. g1 まで読み込んだ後 g1 は通常通り skip::table に入る callers[g1] に main があるので inline 展開される main にはもう inline 函数呼び出しがないのでコード生成される skip:::table から main は削除される

24 inline 展開をあきらめる仕組み inline int fact(int n){ return n ? n * fact(n-1) : 1; } int main(){ ...; fact(10); ... }

25 skip::table にあるのに inline 展開されていない
fact まで読み込んだ後 通常通り skip::table に fact を登録する main の fact 呼び出し 通常通り inline 展開される main まで読み込んだ後 main のコード生成ルーチン inline 宣言されている fact の呼び出しはある fact は skip::table にはいっている fact のコード生成ルーチンを完了させる main のコード生成ルーチンを完了させる skip::table にあるのに inline 展開されていない inline 展開をあきらめる