Using Profile Information to Assist Classic Code Optimizations

http://impact.crhc.illinois.edu/shared/journal/spe.profile-classic.91.pdf

note: 興味のあるところだけ翻訳ツールに投げ込んでいる

SUMMARY

本論文では、古典的なコードの最適化を支援するためにプロファイル情報を自動的に生成する最適化コンパイラの設計と実装について説明する。このコンパイラには、従来の最適化コンパイラにはあまり見られない、実行プロファイラとプロファイルベースのコードオプティマイザという2つの新しいコンポーネントが含まれています。実行プロファイラでは、入力プログラムにプローブを挿入し、複数の入力に対して入力プログラムを実行し、プロファイル情報を蓄積し、この情報をオプティマイザに供給する。プロファイルベースのコードオプティマイザは、プロファイル情報を利用して、従来の全体最適化手法では見えなかった新たな最適化の機会を明らかにします。実験の結果、プロファイルベースコードオプティマイザは、高品質のグローバルコードオプティマイザによってすでに最適化されている量産Cプログラムの性能を大幅に向上させることがわかりました。

CODE OPTIMIZATION ALGORITHMS

Optimizing frequently executed paths

このセクションで紹介するプロファイルベースのコード最適化はすべて、最も頻繁に実行されるパスの最適化という単一のコンセプトを追求しています。このコンセプトについて、例を挙げて説明する。図2は、ループを表す重み付きオウグラフである。をプログラムする。基本ブロック{A B C D E F}のカウントは、それぞれ{100,90,0,0,90,100}である。 {A → B , A → C , B → D , B → E , C → F , D → F , E → F , F → A} のarc_countは次の通りである。 {90,10,0,90,10,0,90,99}, respectively. 明らかに、この例で最も頻繁に実行されるパスは、基本ブロックシーケンス<A B E F>である。従来、非ループベースの古典的コード最適化の定式化は保守的であり、いかなる基本ブロックの実行時間を増加させる可能性のある変換も実行しない。ループベースの古典的コード最適化の定式化は、ループ本体全体を全体として考慮し、非常に偏った「if」文のためにループ本体内のいくつかの基本ブロックがほとんど実行されないケースは考慮しない。このセクションの残りの部分では、より積極的な判断を行い、より多くの最適化の機会を探る、いくつかのプロファイルベースのコード最適化について説明します。

私たちは、頻繁に実行されるパスを表現するために、スーパーブロックと呼ばれるシンプルなデータ構造を使用することを提案します。スーパーブロックは、基本ブロックの線形シーケンスであり、シーケンス内の最初のブロックからしか到達できない。プログラム制御は、どの基本ブロックからでもスーパーブロックを離れることができます。実行がスーパーブロックに達したとき、そのスーパーブロック内のすべての基本ブロックが実行される可能性が非常に高い。スーパーブロックの基本ブロックは、コード上では連続である必要はありません。しかし、この実装では、オプティマイザが考える限り、スーパーブロックのすべてのブロックが常に連続するようにコードを再構築しています。

Forming super-blocks

スーパーブロックの形成は、トレース選択とテールデュプリケーションという2段階の手順で行われます。トレース選択では、順番に実行される傾向がある基本ブロックを特定し、トレースにグループ化する。トレースの定義は、プログラム制御が最初の基本ブロックから入ることに制限されないことを除いて、スーパーブロックの定義と同じである。トレース選択は，トレーススケジューリングで初めて用いられた [7] [8] ．いくつかのトレース選択アルゴリズムの実験的研究が[9]に報告されている．トレース選択アルゴリズムの概要を図 3 に示す． best_predecessor_of(node)関数は，ソース基本ブロックがまだマークされていない場合，nodeのソース基本ブロックの中で最も可能性が高いものを返す．トレースの成長は、現在のノードの最も可能性の高いソース基本ブロックがマークされたときに停止される。 best_predecessor_of(node)関数は、対称的に定義される。

図2はトレース選択の結果である。点線の枠がトレースを表している。トレースは{A, B, E, F }, {C }, {D }の3つである。トレース選択後、プログラム制御が最上位の基本ブロックにしか入らないようにするため、トレースの末尾部分を複製してスーパーブロックに変換する。テール部の複製アルゴリズムは図4に示す。図2の例で考えると、{A, B, E, F }トレースに入る制御経路は基本ブロックFで2つあることがわかる。そこで、基本ブロックFから始まる｛A、B、E、F｝トレースの最後尾部分を複製する。複製された各基本ブロックは、新しいスーパーブロックを形成し、関数の末尾にアプライされる。その結果が図5である。ジャンプ命令を排除するために、末尾の複製後にさらにコード変換が行われる。例えば、図5のFスーパーブロックを複製し、それぞれの複製をCとDのスーパーブロックと組み合わせて、2つの大きなスーパーブロックを形成することができます。重複を抑制するために、実行回数が閾値以下（例えば、1回の実行で100回）の基本ブロックは、トレース選択プロセスから除外している。また、コンパイル時間の増加を抑制するために、プロファイルベースのコード最適化からも除外する。

Formulation of code optimizations

name	scope
constant propagation	super-block
copy propagation	super-block
constant combining	super-block
common sub expression elimination	super-block
redundant store elimination	super-block
redundant load elimination	super-block
dead code removal	super-block
loop invariant code removal	super-block loop
loop induction variable elimination	super-block loop
global variable migration	super-block loop

Table 2 Super-block code optimizations.

表2は、プロファイル情報を利用するために拡張した古典的なコードの最適化のリストです。これらの古典的なコード最適化の原型は、[1] [19] に記載されています。表2のスコープ欄には、これらのコード最適化の拡張スコープを記述しています。非ループベースのコード最適化は、一度に1つのスーパーブロックに対して動作する。ループベースのコード最適化は、一度に1つのスーパーブロック・ループに作用する。スーパーブロックループとは、最後のノデから最初のノデまで、頻繁にバックエッジが取られるスーパーブロックのことです。オプティマイザはまず、ライブ変数分析を適用して、スーパーブロックの境界を越えてライブしている変数を検出し、次に1つのスーパーブロックを一度に最適化する。各スーパーブロックに対して、プロファイルベースのコード最適化を1回以上適用し、限界まで、またはそれ以上の機会が検出されなくなった時点で、最適化を終了する。以下の説明では、各コード最適化は、前提条件関数とアクション関数で構成されています。前提条件関数は、最適化の機会を検出し、変換によってプログラム全体の性能が向上することを確認するために使用されます。アクション関数は、実際のコード変換を実行する。コードの最適化を行うには、オプティマイザが最適化の対象となりそうな命令群を特定します。次に、前提条件関数が呼び出され、各セットについて最適化の判断が行われます。前提条件関数からの承認を得て、アクション関数が対象となるセットをより効率的な同等品に変換する。命令 $op(i)$ が変更する変数の集合を $dest(i)$ とする。また、$op(i)$がソースオペランドとして必要とする変数の集合を$src(i)$と表記する。また、$op(i)$の演算コードを $f_i$ とする。したがって、$op(i)$ は $dest(i) \leftarrow f_i(src(i))$ という演算を指す。

Local optimizations extended to super-blocks

ローカルコードの最適化には、スーパーブロックに簡単に拡張できるものがいくつかあります。これらのローカル最適化には、定数伝搬、コピー伝搬、定数結合、共通部分式消去、冗長ロード消去、冗長ストア消去などがある [1] [19].

従来、ローカル最適化は基本ブロックにまたがって適用することはできず、グローバルコード最適化は実行可能な各パスを平等に考慮する必要がありました。しかし、実行頻度の低いパスによって最適化の機会が阻害されるケースはよくある。そのため、実行頻度の低いパスを体系的に解析から除外しない限り、実行頻度の高いパスに最適化を適用することができない。尾部重複によるスーパーブロックの形成は、この効果を実現する。したがって、プロファイルベースのコード最適化は、従来のコード最適化よりも多くの機会を見つけることができます。

ローカルコードの最適化がスーパーブロックに適用されるとより効果的である理由を説明するために、図6に示す共通部分式除去のケースを考えてみましょう。元のプログラムは図6(a)に示されている。トレース選択とテール複製を行うと、図6(b)のようになる。尾部重複のため、opBからopCに到達できないので、opAとopCに共通部分式消去を適用することができる。