コンパイラ 2012年11月5日 酒居敬一@A468(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2012/index.html.

Slides:



Advertisements
Similar presentations
2.5 プログラムの構成要素 (1)文字セット ① ASCII ( American Standard Code for Interchange ) JIS コードと同じ ② EBCDIC ( Extended Binary Coded Decimal for Information Code ) 1.
Advertisements

コンパイラ 2012年10月25日
第6回条件による分岐.
コンパイラ 2011年10月17日
計算機アーキテクチャ特論Chapter.6.6~6.9
C言語 配列 2016年 吉田研究室.
第2回:Javaの変数と型の宣言 プログラミングII 2007年10月2日.
論理式の表現を数学的に取り扱いやすくするために代数学の助けを借りる.
システム開発実験No.7        解 説       “論理式の簡略化方法”.
  【事例演習6】  数式インタプリタ      解 説     “インタプリタの基本的な仕組み”.
プログラムはなぜ動くのか.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
プログラミング演習Ⅰ 課題2 10進数と2進数 2回目.
コンパイラ 2012年10月15日
コンパイラ 2012年10月22日
2016年度 プログラミングⅠ ~ 内部構造と動作の仕組み(1) ~.
大域的データフロー解析 流れグラフ 開始ブロック 基本ブロックをnodeとし、 基本ブロック間の制御関係をedgeとするグラフを、
コンパイラ 2011年10月24日
第7回 条件による繰り返し.
コンピュータの原理 1E17M053-9 奈良 皐佑 1E17M070-7 師尾 直希        1E17M078-6 渡邊 惇.
コンパイラ 2011年10月27日
最適化の方法 中田育男著 コンパイラの構成と最適化 朝倉書店, 1999年 第11章.
アルゴリズムとデータ構造1 2006年6月16日
コンピュータ系実験Ⅲ 「ワンチップマイコンの応用」 第1週目 アセンブリ言語講座
アルゴリズムとプログラミング (Algorithms and Programming)
コンパイラ 2012年11月15日
04: 式・条件分岐 (if) C プログラミング入門 基幹7 (水5) Linux にログインし、以下の講義ページ を開いておくこと
第7回 条件による繰り返し.
コンピュータの基本構成について 1E16M001-1 秋田梨紗 1E16M010-2 梅山桃香 1E16M013-3 大津智紗子
レジスタの割付け 中田育男著 コンパイラの構成と最適化 朝倉書店, 1999年 第12章5節.
言語プロセッサ 第8回目 平成22年11月22日.
情報処理Ⅱ 第2回:2003年10月14日(火).
第5章 計算とプログラム 本章で説明すること ・計算の概観と記述法 ・代表的な計算モデル ・プログラムとプログラム言語.
復習 一定回数を繰り返す反復処理の考え方 「ループ」と呼ぶ false i < 3 true i をループ変数あるいはカウンタと呼ぶ
コンパイラ 2011年10月20日
C言語 はじめに 2016年 吉田研究室.
2010年度 情報科学序論 ~ 内部構造と動作の仕組み(2) ~.
JAVAバイトコードにおける データ依存解析手法の提案と実装
文法と言語 ー文脈自由文法とLR構文解析ー
コンピュータアーキテクチャ 第 2 回.
2013年度 プログラミングⅠ ~ 内部構造と動作の仕組み(2) ~.
2017年度 プログラミングⅠ ~ 内部構造と動作の仕組み(1) ~.
コンピュータアーキテクチャ 第 3 回.
コンパイラ 2012年10月29日
コンパイラ 2011年11月10日
コンピュータアーキテクチャ 第 2 回.
アルゴリズムとデータ構造1 2009年6月15日
コンピュータアーキテクチャ 第 4 回.
復習 if ~ 選択制御文(条件分岐) カッコが必要 true 条件 false 真(true)なら この中が aを2倍する 実行される
コンピュータアーキテクチャ 第 3 回.
情報処理Ⅱ 第7回 2004年11月16日(火).
情報処理Ⅱ 2005年10月28日(金).
言語プロセッサ 第12日目 平成20年1月9日.
オブジェクト指向言語論 第二回 知能情報学部 新田直也.
コンパイラ 2012年10月11日
アルゴリズムとデータ構造 2010年6月17日
プログラミング演習I 数値計算における計算精度と誤差
2014年度 プログラミングⅠ ~ 内部構造と動作の仕組み(1) ~.
2008年度 情報科学序論 ~ 内部構造と動作の仕組み(2) ~.
情報処理Ⅱ 第2回 2004年10月12日(火).
オブジェクト指向言語における セキュリティ解析アルゴリズムの提案と実現
情報処理Ⅱ 2005年11月25日(金).
情報処理Ⅱ 小テスト 2005年2月1日(火).
プログラミング入門2 第3回 条件分岐(2) 繰り返し文 篠埜 功.
復習 いろいろな変数型(2) char 1バイト → 英数字1文字を入れるのにぴったり アスキーコード → 付録 int
情報処理Ⅱ 第3回 2004年10月19日(火).
情報処理Ⅱ 2006年10月20日(金).
分岐(If-Else, Else if, Switch) ループ(While, For, Do-while)
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
6.5 最終コード生成 (1)コードの形式 ①絶対2進コード(AB : absolute binary) 命令後のオペランドが絶対番地指定。
Presentation transcript:

コンパイラ 2012年11月5日 酒居敬一@A468(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2012/index.html

コード最適化 これまでの内容 今回の内容 ソースプログラムから機械語に翻訳する。 同じ機能を実現するにあたって、より最適なコードを説明する。 字句解析 構文解析 意味解析 コード生成 今回の内容 同じ機能を実現するにあたって、より最適なコードを説明する。 さらにコード生成の前後で、コードサイズの縮小や実行時間の 短縮のための変更ができるかどうか、を説明する。

解析と変換 最適化としての要求項目 いずれにせよ、プログラム変換である 最適化の目的 オブジェクトコードの大きさの縮小。 オブジェクトコードの実行時間の短縮。 いずれにせよ、プログラム変換である しかし、無闇に変換すると元のプログラムと動作が変わる。 そこで、制御フロー解析とデータフロー解析により、変換可能な 部分に限りプログラムを変換する。 最適化の目的 ソースプログラムで表現できない部分の変換。 ソースプログラムで表現しない部分の変換。 特殊な高性能ハードウェアの性能を引き出す変換。

ソースプログラムで表現できない部分 演算はレジスタ間か、レジスタ-メモリ間で行われる。 ソースプログラムからは指示できないこと 一方もしくは両方の被演算対象がレジスタに入る。 しかし、ソースプログラムからレジスタの割り当てはできない。 ソースプログラムからは指示できないこと レジスタに入れた値の再利用。 都度計算したところで、値が同じであることがわかれば再利用できる。 レジスタに入れる値のアドレスの再利用。 構造型データでは実効アドレスの計算にも機械語命令が必要かも… コンパイル時に計算できてしまう値の確定。 書いたとおりに翻訳するべきか、書いた機能だけを実現すべきか。

ソースプログラムで表現しない部分 保守のために、「読みやすさ」も重要。 例: コメントとして説明文を添える方法がひとつ。 プログラムそのもので説明する方法もある。 例: 回数固定の小さいループなのに、展開して書かない。 記号定数や定数を利用して、条件分岐の条件を固定する。 1つの機能に2つの実装があり、コンパイル時に決めうちにする。 事前に計算可能な定数式の値を、計算しないでそのまま書く。 多重ループで説明しやすい順にネストする。 ループ中は結果が不変の式をループ内に書く。 値を求める場所と使う場所を近づけて、説明を省く。 最適化コンパイラを使う前提なら、わかりやすく書いたらいいのです。

特殊な高性能ハードウェア 汎用プロセッサに内蔵されたShort vector命令 DSP命令 MMX, SSE, 3D Now! など。 演算器が別にある。データに制約がある。 DSP命令 パイプライン処理のため、オペランドが3個以上ある。 先行命令の結果の格納。 現命令の演算。 後続命令で使う値たちのメモリからの読み込み。 メモリオペランドに制約がある。 Xメモリ・Yメモリといったメモリの場所の制約。 それらメモリを区別してアクセスするためのアドレス用レジスタの制約。

誤差・副作用 浮動小数点演算では、安易に演算順序を変えられない。 式の評価順の問題。 例:x + 1.0 - 1.0 数学的には (x + 1.0) - 1.0 = x なので、x に最適化していいのか? 数学では加算は交換則が成立するので x + (1.0 + (-1.0)) としてもいい。 xが単精度浮動小数点数で 0.000000001 だったとすると、 書いたとおりの解釈では結果は 0 になる。xに最適化した結果と違う。 xの表現に誤差が含まれるだけではなく、計算によって情報が落ちる。 計算機では加算に交換則が成り立ってない。 式の評価順の問題。 二項演算の被演算項が両方とも関数の戻り値である場合に、 どちらの関数を先に呼び出すべきか? 厳密な関数ではなく、手続きでは全域的な状態が異なる場合がある。 浮動小数点数は実数じゃない。

制御フロー解析 ノード アーク フローグラフ 基本ブロックと呼ぶ逐次実行される連続する実行文のかたまり。 実行順にノードを結ぶ有向線分。 実行の途中から分岐したり、他から飛び込んでくることはない。 アーク 実行順にノードを結ぶ有向線分。 フローグラフ ノードがアークで結ばれている。 グラフの形からループを検出することができる。 while, for といった予約語だけではなく、条件分岐・無条件分岐を 組み合わせてループになったものも含めることができる。 グラフ化により、while・if・goto・for の区別はなくなります。 検出したループに対して最適化することができる。 for・whileで0回か1回しか回らなければループより条件分岐に見える。

ソースプログラムと制御フローグラフ i=0; eps = x[i] - x[i-1]; i++; q = s; eps > 0.01 x[i] = q + x[i]; q > 0 q = s/q; 次の実行文 true false i=0; while(eps > 0.01){ x[i] = q + x[i]; if(q > 0) q = s/q; else q = s; eps = x[i] - x[i-1]; i++; } 次の実行文

データフロー解析 使用点 定義点 使用定義連鎖 定義使用連鎖 プログラムの中で、変数の値を参照する場所。 プログラムの中で、変数に値を設定する場所。 使用定義連鎖 使用点に到達している定義点への連鎖 定義使用連鎖 定義点から、その定義が到達する使用点への連鎖。

到達する定義 定義dの直後の点からuへ、定義が消滅しない経路が 少なくともひとつあること。 定義dの直後の点からuへ、定義が消滅しない経路が 少なくともひとつあること。 定義点d1とd3の定義はそれぞれは使用点uに到達する。 使用点uに関しては、定義点d2の定義は消滅する。 x= … 定義点d1 = x … 使用点u x= … 定義点d2 x= … 定義点d3

到達定義を求めるアルゴリズム 基本ブロックBの出口で生きている定義は、そのBの中 で作り出される定義と、Bの入り口に達してかつ定義が Bの中を通っても消滅しないものの、和集合である。 定義dが基本ブロックBの中に現れて、Bの中を通って Bの終わりに達する。 定義dが基本ブロックBの先頭に達したものの、Bの 終わりにその定義が達することがない。

95ページの直感的説明 2つの文が連接しているときに、 2つの文が連接しているとき、 これらの文が消滅させる定義は GEN[S1;S2]=GEN[S2]∪(GEN[S1]-KILL[S2]) GEN[S1] GEN[S2] KILL[S2] KILL[S1;S2]=KILL[S2]∪(KILL[S1]-GEN[S2]) KILL[S2] KILL[S1] GEN[S2] 2つの文が連接しているときに、 これらの文が消滅させる定義は それぞれの和である。 ただし、先行する文が消滅した定義を 後続の文でも定義することで消滅 する場合を考慮しないといけない。 2つの文が連接しているとき、 定義の生成はそれぞれの文が 生成する定義の和となる。 ただし、後続の文による定義が 先行する文の定義を消滅させて しまう場合を考慮しないといけない。

データフロー方程式を解く反復アルゴリズム  入力:フローグラフ      各基本ブロックのGEN[B]とKILL[B]  出力:各基本ブロックのIN[B]とOUT[B] 初期化:すべての基本ブロックBについてIN[B]={φ},      すべての基本ブロックBについてOUT[B]=GEN[B] while(すべてのIN[B]が収束するまでフローグラフの入口から経路順に){ IN[B] ∪= OUT[P]; // PはBの直接先行ブロック OUT[B] = GEN[B]∪(IN[B]ーKILL[B]); }

A i=0; i > 100 s > 0 p > 0 s = s - p; x = y/p; a = s; true false i=0; i > 100 s > 0 p > 0 s = s - p; x = y/p; a = s; s = s+q; i = i + 1; s = s + i; A GEN={①} KILL={⑨} B GEN={φ} KILL={φ} C D E GEN={⑤} F GEN={⑥} KILL={⑧,⑩} G GEN={⑦} KILL={⑪} H GEN={⑨,⑩,⑪} KILL={①,⑥,⑦,⑧} i=0; while(i > 100){ while(s > 0){ if(p > 0){ x = y/p; }else{ s = s - p; } a = s; s = s+q; i = i + 1; s = s + i; ① GEN = {①} KILL={⑨} ② GEN = {φ} KILL={φ} ③ GEN = {φ} KILL={φ} ④ GEN = {φ} KILL={φ} ⑤ GEN = {⑤} KILL={φ} ⑥ GEN = {⑥} KILL={⑧, ⑩} ⑦ GEN = {⑦} KILL={⑪} ⑧ GEN = {⑧} KILL={⑥, ⑩} ⑨ GEN = {⑨} KILL={①} ⑩ GEN = {⑩} KILL={⑥, ⑧} ⑪ GEN = {⑪} KILL={⑦} B C D E F G H

到達定義から使用定義連鎖へ 基本ブロックごとに、INとOUTの集合を求める。 基本ブロック内で使用される変数と、INに含まれる定 義のうち同じ変数に対するすべての代入文を結ぶ。 使用点で使われる定義を辿ることができる。 基本ブロックの入口までの使用定義連鎖は求まった。 しかし、基本ブロック内部については解析していない。 基本ブロック内を実行順にたどって不要な演算を省く。

最適化変換 ループにかかわる最適化変換 ループ不変式の追い出し ループ展開 ループボディを実行している間、値が変化しない式を検出し、 ループの開始前に処理してしまう。 すべての不変式を追い出せるわけではない。 ループ展開 ループの繰り返し部分を展開し、ループの終了条件を判定する 機械命令やループするための分岐命令を削減する。 ループ回数を整数除で簡単にするために、展開するループの回数 を2のべき乗にすることが多い。 ループボディが小さく、ループ終了条件の処理の時間が目立つ 場合には効果が大きい。多重ループの場合は最内周ループに使う。

【ループ不変式の検出アルゴリズム】 中間表現をたどり、定数と、ループ内で使用される変数に届くすべての使用定義連鎖の定義がループの外にある変数に「不変マーク」を付加する。 代入文に付加される不変マークが変化しなくなるまで、3と4の処理を繰り返す。 演算子ノードの第1オペランドと第2オペランドの両方に不変マークがついている場合、その演算子にも不変マークを付加する。 右辺式に全体に不変マークが付いている場合は、その代入文と左辺変数に不変マークを付加し、その左辺変数からの定義が唯一届いている変数の使用にも不変マークを付ける。 【ループ不変文の追出し】  ループ繰り返しの中で値の変わらない計算を行っている代入文も、必ずしも常にループの外に追い出せるわけではない。不変式としてループの外に追い出すことが可能である式を、ある変数に代入する。不変代入文を追い出すためには、次の条件を満たす必要がある。 不変な文は、ループの各繰り返しで必ず実行される。 左辺の変数への代入処理は、そのループの中では検出した不変代入文だけが行う。 不変な代入文の左辺変数から、ループ内への使用定義連鎖が届く変数の使用には、  ほかの定義からの使用定義連鎖が届かない。

基本的な最適化変換 定数伝播 静式評価 コピー伝播 命令強度の削減 変数の使用点に唯一の定数定義が届くとき、定数に置換。 コンパイル時に評価できるものは評価しておく。 コピー伝播 a=b;のように右辺に演算がない場合、aをbで置き換える。 ただし、aの使用にはその文からの使用定義連鎖しか届かない ことと、その文から置き換えて使用するまでのいかなるパス にも変数bへの代入がないこと。 命令強度の削減 乗算・除算にシフトを使う。 乗算に加算命令(算術加算・EA計算)を使う。