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

Slides:



Advertisements
Similar presentations
配列の宣言 配列要素の初期値 配列の上限 メモリ領域 多次元配列 配列の応用
Advertisements

情報基礎演習B 後半第5回 担当 岩村 TA 谷本君.
プログラミング入門2 第10回 構造体 情報工学科 篠埜 功.
アルゴリズムとプログラミング (Algorithms and Programming)
実行時のメモリ構造(1) Jasminの基礎とフレーム内動作
第10回関数2 (関数の利用と変数のスコープ).
プログラミング演習II 2004年10月19日(第1回) 理学部数学科・木村巌.
構造体.
プログラミング論 II 電卓,逆ポーランド記法電卓
問題 1 キーボードから入力した数の合計を計算するプログラムを 作成せよ。最初に、何個の数を入力するかその数を入力 するようにする。
第4回放送授業.
プログラミング演習Ⅰ 課題2 10進数と2進数 2回目.
ちょっとした練習問題① 配列iroを['R', 'W', 'R', 'R', 'W' , 'W' , 'W']を宣言して、「W」のときの配列の番号をprintfで表示するようなプログラムを記述しなさい。
プログラミング論 ファイル入出力
関数とポインタ 値呼び出しと参照呼び出し swapのいろいろ 関数引数 数値積分
関数と配列とポインタ 1次元配列 2次元配列 配列を使って結果を返す 演習問題
関数の定義.
第10回関数 Ⅱ (ローカル変数とスコープ).
プログラミング論 II 2008年10月30日 文字列
プログラミング 4 記憶の割り付け.
第10章 これはかなり大変な事項!! ~ポインタ~
プログラミング入門2 第8回 ポインタ 情報工学科 篠埜 功.
知能情報工学演習I 第12回(後半第6回) 課題の回答
プログラミング入門2 第11回 情報工学科 篠埜 功.
第7回 プログラミングⅡ 第7回
復習 前回の関数のまとめ(1) 関数はmain()関数または他の関数から呼び出されて実行される.
プログラミング言語論 第五回 理工学部 情報システム工学科 新田直也.
アルゴリズムとデータ構造 補足資料5-1 「メモリとポインタ」
プログラミング論 ファイル入出力
関数の再帰呼び出しとは ハノイの塔 リダイレクト レポート課題
関数への道.
一時的な型 長谷川啓
オブジェクト指向 プログラミング 第六回 知能情報学部 新田直也.
フロントエンドとバックエンドのインターフェース
オブジェクト指向プログラミングと開発環境
記号表の検索と登録 長谷川啓
岩村雅一 知能情報工学演習I 第12回(C言語第6回) 岩村雅一
メモリとメモリアドレス, ポインタ変数,関数へのポインタ渡し
プログラミング入門2 第9回 ポインタ 情報工学科 篠埜 功.
C++ 構文解析 構文解析器の状態保存と復元
参照されないリテラル 長谷川啓
プログラミング演習I 2003年7月2日(第11回) 木村巌.
オブジェクト指向 プログラミング 第六回 知能情報学部 新田直也.
情報基礎演習B 後半第2回 担当 岩村 TA 谷本君.
第13回 ポインタ 1 1.
11.1 標準ライブラリ関数 11.2 関数呼び出しのオーバーヘッド 11.3 大域変数 11.4 プロトタイプ宣言 11.5 関数引数
第5回 プログラミングⅡ 第5回
オブジェクト指向言語論 第五回 知能情報学部 新田直也.
精密工学科プログラミング基礎 第7回資料 (11/27実施)
プログラミング入門2 第5回 配列 for文 変数宣言 初期化
ドキュメントジェネレータ 詳細仕様 長谷川啓
オブジェクト指向 プログラミング 第四回 知能情報学部 新田直也.
X64 函数呼び出し規約 長谷川啓
フレンド関数とフレンド演算子.
演算子のオーバーロード.
Tacsim の実装 - 実行部分 長谷川啓
精密工学科プログラミング基礎Ⅱ 第2回資料 今回の授業で習得してほしいこと: 配列の使い方 (今回は1次元,次回は2次元をやります.)
関数と再帰 教科書13章 電子1(木曜クラス) 2005/06/22(Thu.).
プログラミング演習I 2003年6月11日(第9回) 木村巌.
:: の扱い 長谷川啓.
第10回 関数と再帰.
オブジェクト指向言語論 第三回 知能情報学部 新田直也.
プログラミング入門2 第5回 配列 変数宣言、初期化について
オブジェクト指向 プログラミング 第六回 知能情報学部 新田直也.
プログラミング入門2 第3回 条件分岐(2) 繰り返し文 篠埜 功.
第2章 数値の入力と変数 scanfと変数をやります.
計算技術研究会 第5回 C言語勉強会 関数(function)を使う
岩村雅一 知能情報工学演習I 第13回(後半第7回) 岩村雅一
プログラミング演習I 補講用課題
プログラミング 2 静的変数.
Presentation transcript:

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

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

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 展開アルゴリズム適用後もう一度最適化ルーチンを適用すれば、さらに最適化される可能性はある。

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

例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; }

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 が追加される

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: (追加)

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]

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

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

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: が追加される

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: (追加)

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

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 展開する

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: (追加)

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

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

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 の数との和である。

可変個引数を取る 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); }

可変個引数を取る 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 ...

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

例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){ ... }

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 は削除される

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

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