JP2001325111A

JP2001325111A - 投機機構向けコンパイル方法

Info

Publication number: JP2001325111A
Application number: JP2000148588A
Authority: JP
Inventors: Ichiro Kushima; 伊知郎久島; Hiroyasu Nishiyama; 博泰西山
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 2000-05-16
Filing date: 2000-05-16
Publication date: 2001-11-22
Also published as: US20010044931A1

Abstract

(57)【要約】【課題】ループのように繰り返し実行される部分に対し
て投機機構を利用したコードを生成する場合に、頻繁に
投機チェックにひっかかり回復コードに分岐するために
性能が低下するのを防ぐ。【解決手段】投機命令および投機誤りをチェックするチ
ェック命令を有するプロセッサ向けのコードを生成する
コンパイラにおいて、（１）プログラム中の繰り返し実
行される部分に対し、投機命令およびチェック命令を使
用したコード(a)と、投機命令およびチェック命令を使
用しないコード(b)を含む、少なくとも２種類のパター
ンのコードを生成する処理と、（２）コード(a)の実行
中に投機誤りチェックにかかった回数が特定の条件を満
たす場合に、以降の繰り返しではコード(b)を実行する
ように、制御の移行を行うコードを生成する処理を含
む。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、計算機の利用技術
において、オブジェクトプログラムの実行時間を削減す
るコンパイル方法に関する。特に、投機機構を持つ計算
機向けのコンパイル方法に関する。

【０００２】

【従来の技術】近年のマイクロプロセッサは、オブジェ
クトプログラムを高速に実行することを目的として、特
定の命令（主にロード命令）を投機的に実行する命令
（投機ロード命令）と、その投機実行が誤りであったか
どうかをチェックする命令（チェック命令）を備えてい
るものがある。これらを合わせて投機機構と呼ぶ。投機
機構およびそれらを用いた最適化方法については、たと
えばIntel: IA−64 Application Developers Architect
ure Guide, May 1999, Order Number: 245188−001の 1
0−4節および10−5節に記載がある。

【０００３】投機機構を用いた最適化の一例として、不
明なデータ依存関係がある場合のループ不変式移動があ
る。これを図２のプログラム片を用いて示す。図２のプ
ログラムはC言語で記載されており、(201)の条件condが
満たされている間、(202)〜(204)の文を繰り返し実行す
ることを意味するループである。(202)では、a+bの値を
計算し、cに代入する。(203)では、cの値を、pが表すア
ドレスで示されるメモリ（*p）に書きこむ。(204)で
は、pの値を更新する。

【０００４】図１のプログラム片に対して、投機機構を
利用しないでオブジェクトコードを生成すると、図３の
ようになる。なお図３ではコードをわかりやすくするた
めに一部C言語の構文を用いて記述している。図３では
(301)の条件condが満たされている間、(302)〜(306)の
命令を繰り返し実行する。(302)では、変数aのアドレス
（&a）で示されるメモリ内容、即ちaの値をレジスタr1
へロードする。(303)では、同様にbの値をメモリからレ
ジスタr2へロードする。(304)ではr1とr2の和を計算
し、r3へ代入する。(305)では、r3の値をpが表すアドレ
スで示されるメモリにストアする。(306)では、pの値を
更新する。

【０００５】図３のコードでは、は、ループの繰り返し
で毎回同じ値を計算している、即ちループ不変式である
可能性が高いので、これらの命令をループ外に移動する
（ループに入る前に1度だけ計算をしておき、ループの
中では計算された値を使う）ようにすれば、実行時間が
短縮される。しかし、pが表すアドレスと、aまたはbの
アドレスが一致している場合には、このような移動はで
きない。すなわち、(305)のストア先のメモリのアドレ
スと、(302)または(303)でロードするメモリのアドレス
が一致していた場合、*pへの書き込みでaまたはbの値が
書きかえられるので、(302)から(304)で計算される値は
ループ不変でなくなり、(302)から(304)の命令をループ
外への移動することはできない。このように、不明なデ
ータ依存関係がある（ストア先のメモリのアドレスと、
ロードするメモリのアドレスが一致するかどうかがわか
らない）場合、一般にコンパイラはループ不変式移動を
行うことはできない。

【０００６】一方、投機機構を利用した場合、図１のプ
ログラム片に対してループ不変式移動を行うことができ
る。これを図４に示す。図４では、aおよびbのロードと
加算が、ループ外に移動されている（(401)〜(403)）。
そのときのロード命令は通常のロード命令ではなく、投
機的なものであるのでld.a命令を用いている（aはadvan
cedを意味する）。またループ内では(405)と(406)命令
で投機ロードが不正でないかどうかをチェックするチェ
ック命令（(405),(406)）が置かれている。(405)のchk.
a r1, recover1は、r1に対するld.a命令から現在のchk.
a命令までの間に、la.dでロードしたメモリアドレスに
対するストアがあったかどうかをチェックする。あった
場合には、投機実行は誤りであったので、recover1（(4
10)）に分岐する。分岐先のrecover1では、(411)でaの
値をロードし直し、(412)でa+bを計算し直し、(413)で
チェック命令の次の命令(406)に戻る。(407)および(41
4)〜(417)も同様である。なお、(410)〜(413)および(41
4)〜(417)は、投機チェック命令で引っかかった（投機
実行が誤りであった）場合に実行をやり直すので、回復
コードと呼ばれる。

【０００７】図４のコードでは、投機チェックにひっか
かって回復コードに分岐しない限り、ループ中でロード
命令や加算命令が実行されることがないので、図３のコ
ードに比べて実行時間が短くなることが期待される（ル
ープ中の命令は図３に比べて1命令しか減少していない
が、一般にチェック命令はロード命令や加算命令に比べ
て少ないサイクル数で行えるので、命令数以上に効果が
あると期待される）。このように、投機機構を用いれ
ば、ロード命令とストア命令の間に不明な依存関係があ
る場合にも、ループ不変式移動を行える。また、ループ
不変式移動以外にも、ロード命令とストア命令の間に不
明な依存関係がある場合に、ロード命令を、ストア命令
を越えて移動するなどの命令スケジューリングが行える
ようにようになる。

【０００８】

【発明が解決しようとする課題】従来技術ではしかしな
がら、投機チェック命令にひっかかって回復コードに分
岐することが頻繁に行われると、却って実行速度が低下
する可能性があるという問題がある。たとえば図４のコ
ードでは、(405)または(406)のchk.a命令で、回復コー
ドに分岐することが頻繁に行われると、分岐によるオー
バーヘッドや、再計算のため、性能が却って低下する可
能性がある。

【０００９】そこで本発明の目的は、投機機構を利用し
たコードを生成するコンパイラにおいて、図２のように
繰り返し実行される部分について、頻繁に投機チェック
にひっかかり回復コードに分岐することで性能が悪くな
る、ということが生じないコードを生成するコンパイル
方法を提供することである。

【００１０】

【課題を解決するための手段】前記目的を達成するた
め、本発明のコンパイル方法では、以下を行う。

【００１１】（１）コンパイラは、ループのように繰り
返し実行される部分に対し、投機機構（投機命令および
投機チェック命令）を利用したコード(a)と、投機機構
を利用しないコードの２種類のパターンのコード(b)を
生成する。最初は投機機構を利用したコード(a)を実行
するようにする。

【００１２】（２）投機機構を利用したコード(a)中の
投機チェック命令にひっかかった場合に実行される回復
コードでは、チェックにひっかかった回数をカウント
し、回数が上限値を越えている場合は、以降は投機機構
を利用しないパターンのコード(b)を実行するようにす
る。

【００１３】これにより、投機チェックにひっかかる回
数がある値を超えた場合は、以降は投機機構を利用しな
いコードが実行されるので、頻繁に投機チェックにひっ
かかり回復コードに分岐することで性能が悪くなること
がなくなる。また投機チェックにひっかかる回数が少な
い場合には、投機機構を利用したコードが実行されるの
で、投機機構を利用しない場合より実行速度が速くな
る。なお回数の上限値を１にすれば、回数をカウントす
る必要はなくなる。また回数ではなく、チェックにひっ
かかった確率を用いてもよい。

【００１４】

【発明の実施の形態】以下、本発明の一実施例として、
投機機構を利用したループ不変式移動を行うコンパイラ
を説明する。

【００１５】図１は、本発明によるコンパイラが稼動す
る計算機システムの構成図である。図示するように、計
算機システムはＣＰＵ１０１、主記憶装置１０４、外部
記憶装置１０５、ディスプレイ装置１０２、キーボード
１０３より構成されている。外部記憶装置１０５にはソ
ースプログラム１０６、オブジェクトプログラム１０７
が格納される。主記憶装置１０４には、コンパイラ１０
８と、コンパイル処理過程で必要となる中間コード１０
９が保持される。コンパイル処理はＣＰＵ１０１がコン
パイラプログラム１０８を実行することにより行われ
る。キーボード１０３はユーザからのコマンドをコンパ
イラ１０８に与えるのに用いる。ディスプレイ装置１０
２はコンパイルの終了またはエラーをユーザに知らせ
る。

【００１６】図５は、コンパイル処理の流れを示したフ
ローチャートである。コンパイラの処理は、まずステッ
プ５０１で構文解析を行う。構文解析はソースプログラ
ム１０６を読み出し、コンパイラ内部で処理可能な中間
コード１０９を作成する。構文解析処理については、た
とえば「エイホ、セシィ、ウルマン著：コンパイラＩ
（サイエンス社、１９９０年）３０頁〜７４頁」に記載
されているので、ここでは詳しく説明しない。次にステ
ップ５０２で、ループ解析を行う。ループ解析処理につ
いても「エイホ、セシィ、ウルマン著：コンパイラII
（サイエンス社、１９９０年）７３４頁〜７３７頁」に
記載があるのでここでは詳しく説明しない。ループ解析
により、プログラムに含まれるループの集合が求められ
る。次にステップ５０３で、未処理のループがあるか調
べる。なければステップ５０６へ進み、オブジェクトコ
ードを生成して終了する。オブジェクトコード生成につ
いては、同じく「エイホ、セシィ、ウルマン著：コンパ
イラII（サイエンス社、１９９０年）６２４頁〜７０７
頁」に記載があるので、ここでは詳しく説明しない。未
処理のループがあればステップ５０４でループを１つ取
り出す。そしてステップ５０５で、投機機構を利用した
ループ不変式移動処理を行う。ステップ５０５の処理に
ついては図７を用いて詳しく説明する。この処理の後は
ステップ５０３から繰り返す。

【００１７】図６は本実施例におけるコンパイラの中間
コードの例である。中間コードは構文解析５０１の処理
により作成される。図６の中間コードは図２のソースプ
ログラムに対応している。図６の中間コードは、基本ブ
ロック（ＢａｓｉｃＢｌｏｃｋ、ＢＢと略される）を
エッジで結んだグラフで表現されている。（このような
グラフは制御フローグラフと呼ばれている。）６０１か
ら６０４は基本ブロックである。これらの基本ブロック
には、ＢＢ１からＢＢ４までの番号がそれぞれ付けられ
ている。基本ブロックは途中で分岐や飛び込みのない、
一連のコード列を表している。エッジ（矢印）は基本ブ
ロック間の遷移を表している。たとえば基本ブロック６
０１から６０２にエッジが張られているので、６０１が
終った後で、６０２へ制御が移ることを示している。基
本ブロックの解析方法や制御フローグラフの構成方法に
ついては前著（コンパイラII）６４２頁〜６４８頁に記
載されているので、ここでは詳しく述べない。各基本ブ
ロック中に書かれているものは実行文であり、その基本
ブロックに制御が移ったときに実行される。各文の左側
（S1〜S7）は文番号を表す。

【００１８】図７は投機機構を利用したループ不変式移
動処理５０５の流れを詳しく示したフローチャートであ
る。まずステップ７０１で、ループ中に未処理の文（命
令）があるか調べる。なければ終了する。あればステッ
プ７０２に進み、未処理の文を１つ取り出し、ステップ
７０３で、取り出した文がループ不変式であるか調べ
る。ループ不変式であるかどうかは、すべてのオペラン
ドがループ不変であるかを調べる。ロード命令の場合
はロードするメモリアドレスがループ不変であるかを調
べる。ただしアドレスがループ不変であっても、明らか
なデータ依存（同じアドレスへのストア）がループ中に
あればループ不変でないとする。（不明なデータ依存の
ある場合はループ不変式とみなす。）ループ不変でなけ
ればステップ７０１から繰り返す。ループ不変であれ
ば、それがロード命令でかつ、不明なデータ依存がある
（ロードするメモリアドレスへのストアがループ中で実
行される可能性がある）か調べる、そうであればステッ
プ７０５に進む。ステップ７０５では、すでにループの
２重化（ループの複写）を行っているか調べる。２重化
を行っていない場合はステップ７０６に進み、ループの
２重化を行う。これは、元のループの後に、複写ループ
を作るもので、たとえば図６の中間コードでは、ステッ
プ７０６を行った後の中間コードは図８のようになる。
図８ではBB5（804）およびBB8（805）が複写されたルー
プを構成する。さらに元のループの前に、カウンタをゼ
ロクリアするコード（807のS15）を挿入する。次にステ
ップ７０７で、移動対象のロード命令をループ外に移動
する。その際、ロード命令を投機ロード命令（load.a）
に変更する。次にステップ７０８で、元のロード命令が
あった位置にチェック命令（chk.a）を置くとともに、
チェックにひっかかった場合の回復コードを作成する。
これを図９に示す。

【００１９】図９では、チェック命令（904のS16）から
回復コード（906）への分岐が作成されている。回復コ
ードの先頭では、カウンタをインクリメントし（906のS
17）、カウンタ値が一定値を超えた場合には複写ループ
へ分岐するコード（906のS18）が作成されている。カウ
ンタが一定値を超えていない場合にはaの再ロード（907
のS19）を行い、チェック命令の次の命令（905のS3）に
戻る。

【００２０】図７の説明に戻る。ステップ７０５でルー
プの２重化をすでに行っている場合は、ステップ７０７
から処理を行う。図８の中間語の例では、最初のロード
命令（S2）の移動ではループの複写を行うが、２番目の
ロード命令（S3）の移動ではループ２重化処理はスキッ
プされる。ステップ７０９では、従来のループ不変式移
動と同様に、移動対象文をループ外に移動する。さら
に、ステップ７１０で、移動対象文で参照されるオペラ
ンドが、回復コード中で設定されているかどうかを調
べ、設定されている場合は、ステップ７１１で、回復コ
ードの該設定文の直後にも、命令をコピーする。たとえ
ば、905のS4の文（t3=t1+t2）をステップ７０９でルー
プ外に移動する場合、そのオペランドのt1, t2は回復コ
ードのS19（t1=load.a(&a)）で中で設定されているの
で、その直後にもコピーされる。図７の処理を行うこと
により、図８の中間コードは最終的に図１０のようにな
る。

【００２１】図１１は、図１０の中間語をオブジェクト
コードにしたもので、本発明のコンパイラにより生成さ
れるものである。ここでは図２，３と同様、コードをわ
かりやすくするために一部C言語の構文を用いて記述し
ている。図１１のプログラムでは、投機機構を利用して
ループ不変式移動がされたループ（1105〜1110）と、投
機機構を利用しないループ（1112〜1118）の２つのルー
プがあり、最初は投機機構を利用したループが実行され
る。投機機構を利用したループ内の最初のチェック命令
（1106）にひっかかったときに分岐する回復コード（11
20〜1125）では、最初にカウンタ値を更新し（1121）、
それが一定値を超えた場合は、投機機構を利用しないル
ープに制御を移す（1122）。２つめのチェック命令（11
07）についても同様である。これにより、頻繁にチェッ
クにひっかかる場合には投機機構を利用しないループが
実行されるので、以降は、投機チェックからの回復のた
めに実行速度が低下することがない。また投機チェック
にひっかかる回数が少ない場合には、投機機構を利用し
たコード（ループ不変式移動がされている）が実行され
るので、投機機構を利用しない場合より実行速度が速く
なる。

【００２２】以上の実施例では、カウンタを用いて投機
チェックにひっかかった回数をカウントしていたが、投
機チェックにひっかかる回数の上限値を１にした場合
は、カウンタの更新処理は不要になる。すなわち、１度
でもチェックにひっかかった場合、直に投機コードを利
用しないコードに分岐すればよい。すなわち、ステップ
７０８では回復コードを生成せずに、チェック命令から
複写ループへ直接分岐するようにする。この場合に生成
されるオブジェクトコードは図１２に示すようになる。
図１２のプログラムでは、投機機構を利用してループ不
変式移動がされたループ（1204〜1209）と、投機機構を
利用しないループ（1211〜1217）の２つのループがあ
り、投機機構を利用したループ内のチェック命令（120
5、1206）にひっかかったときには、投機機構を利用し
ないループに直接分岐する。このようにすると、回復コ
ードでのカウンタ更新やカウンタ値の比較コードが不要
になるという利点がある。

【００２３】また以上の実施例では、投機チェックにひ
っかかった回数を閾値にしていたが、回数ではなく、確
率（割合）を閾値にしてもよい。すなわち、ループの実
行回数をN、チェックにひっかかった回数をMとし、M/N
が一定値以上になっているかを調べる。この場合のオブ
ジェクトコードは図１３に示すようになる。図１３のプ
ログラムでは、投機機構を利用してループ不変式移動が
されたループ（1306〜1312）と、投機機構を利用しない
ループ（1315〜1321）の２つのループがあり、投機機構
を利用したループでは、ループの実行回数をカウントす
る（1307）。投機機構を利用したループ内の最初のチェ
ック命令（1308）にひっかかったときに分岐する回復コ
ード（1323〜1329）では、チェックにひっかかった回数
を表すカウンタ値を更新し（1324）、それをループ実行
回数で割り（1325）、割った値が一定値を超えた場合
は、投機機構を利用しないループに戻る（1326）。２つ
めのチェック命令（1309）も同様である。このようにし
た場合、ループ実行回数をカウントするオーバーヘッド
や除算のオーバーヘッドが加わるものの、チェックにひ
っかかる確率で判断ができるので、どちらのループを実
行すべきかをより精密に判断することが可能になるとい
う利点がある。

【００２４】以上の実施例は、投機機構を利用してルー
プ不変式移動を行う場合に本発明を適用したものであっ
たが、本発明はこれに限定されるものではなく、投機機
構を利用して、ループ内で命令を移動する（命令スケジ
ューリング）場合にも適用できる。命令スケジューリン
グは、命令の順序を並べ替えることにより、命令レイテ
ンシを隠蔽し、命令列の実行時間を削減する最適化であ
る。一般に、ストア命令と、後続するロード命令の間に
不明な依存関係がある場合（それぞれの命令で参照する
メモリアドレスが一致している可能性がある場合）は、
ロード命令をストア命令の前に移動することはできない
が、投機機構を利用すれば命令の順序を入れ替えること
ができる。すなわち、ストア命令の前に投機的ロード命
令を実行し、ストア命令の後でチェック命令を実行すれ
ばよい。ループに対してこのような投機機構を利用した
命令スケジューリングに本発明を適用した場合、投機機
構を利用したループと、投機機構を利用しないループの
２つのループコードを生成し、投機機構を利用したルー
プ内でのチェック命令にひっかかった回数がある条件を
満たす場合は、以降は投機機構を利用しないループに分
岐するようにする。これにより、投機チェックに頻繁に
ひっかかる場合の性能低下を防ぐことができる。

【００２５】

【発明の効果】本発明のコンパイル方法によれば、ルー
プのように繰り返し実行される部分に対して投機機構を
利用したコードを生成する場合、頻繁に投機チェックに
ひっかかり回復コードに分岐するために性能が低下す
る、ということが発生しないコードを生成できる。

【図面の簡単な説明】

【図１】本発明のコンパイラが稼動する計算機システム
の構成図。

【図２】ソースプログラム例を示す図。

【図３】投機機構を利用しない場合の従来技術の生成コ
ードを示す図。

【図４】投機機構を利用した場合の従来技術の生成コー
ドを示す図。

【図５】コンパイル処理の流れを示す図。

【図６】図２のプログラムの対する中間コードの例を示
す図。

【図７】本発明を適用したループ不変式移動処理の流れ
を示す図。

【図８】ループ２重化直後の中間コードの例を示す図。

【図９】最初のロード命令をループ外移動した直後の中
間語の例を示す図。

【図１０】ループ不変式移動処理後の中間コードの例を
示す図。

【図１１】本発明を適用した場合の生成コードの例を示
す図。

【図１２】本発明を適用した場合の別の生成コードの例
を示す図。

【図１３】本発明を適用した場合の別の生成コードの例
を示す図。

Claims

【特許請求の範囲】

【請求項１】投機命令および投機誤りをチェックする
チェック命令を有するプロセッサ向けのコードを生成す
るコンパイラにおいて、（１）プログラム中の繰り返し実行される部分に対し、
投機命令およびチェック命令を使用したコード(a)と、
投機命令およびチェック命令を使用しないコード(b)を
含む、少なくとも２種類のパターンのコードを生成する
処理と、（２）コード(a)の実行中に投機誤りチェックにかかっ
た回数が特定の条件を満たす場合に、以降の繰り返しで
はコード(b)を実行するように、制御の移行を行うコー
ドを生成する処理を含むことを特徴とする、投機機構向
けコンパイル方法。
【請求項２】請求項１のコンパイル方法において、
（２）における特定の条件として、投機チェックにかか
った回数が一定値を超えることを条件とする、投機機構
向けコンパイル方法。
【請求項３】請求項１のコンパイル方法において、
（２）における特定の条件として、繰り返し部分の実行
回数に対する、投機チェックにかかった回数の割合が一
定値を超えることを条件とする、投機機構向けコンパイ
ル方法。
【請求項４】請求項１のコンパイル方法において、投
機チェックにかかった場合、カウンタを更新し、その値
が一定値を越えた場合には、コード(b)に制御を移すこ
とを特徴とする、投機機構向けコンパイル方法。
【請求項５】請求項１のコンパイル方法において、投
機チェックにかかった場合、ただちにコード(b)に制御
を移すことを特徴とする、投機機構向けコンパイル方
法。
【請求項６】請求項１のコンパイル方法を用いたコン
パイラ。
【請求項７】請求項６のコンパイラを格納した記憶媒
体。