JPH1153197A - ループ最適化方法 - Google Patents

Abstract

(57)【要約】 【課題】 プログラム実行開始時にループの反復回数が
未定である場合において、コンディションコード数とレ
ジスタ数とに基づきループを展開し、かつ、投機的命令
を使って効率的なコードを生成することにより、ループ
を最適化する。 【解決手段】 ループ最適化方法に、中間コードからル
ープを検出し、かつ該検出されたループの構造を解析す
る第１の工程１０と、コンディションコード数１２とレ
ジスタ数１３とに基づきループ展開数を決定する第２の
工程１１と、該決定されたループ展開数だけループを展
開し、かつ、該展開されたループにおいて命令を投機的
命令に置き換え、かつ並び替えることによって効率的な
コードを生成する第３の工程１４とを備える。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、プロセッサにおけ
る投機的命令を有するアーキテクチャに対する、コンパ
イラのループ最適化方法に関するものである。

【０００２】

【従来の技術】近年のプロセッサは、複数の処理を並列
的に実行することによって高い処理性能を実現してい
る。プロセッサにおいてオブジェクトプログラムの実行
効率を向上させるためには、コンパイル処理における構
文解析によって生成された中間コードに基づいて、プロ
グラムの意味を変えずに、並列処理による実行速度の向
上、オブジェクトプログラムのサイズ削減等を行なうた
めの最適化技術が用いられる。その中でも、ループによ
る処理時間がプログラム実行時間の多くを占めることか
ら、ループの最適化が重要である。

【０００３】従来のループ最適化を、図７（ａ）〜
（ｃ）及び図８（ａ），（ｂ）を参照して説明する。な
お、コンパイラにおいては中間コードを扱うが、以後の
説明においてはわかりやすくするために、必要に応じて
Ｃ言語又はアセンブリ言語によってプログラムを記述す
る。図７（ａ）は、ループ最適化の対象となる、Ｃ言語
で記述されたソースプログラムである。該ソースプログ
ラムは、配列ｘの要素よりなる配列変数ｘ［ｉ］が０で
ない場合には、配列ｙの要素よりなる配列変数ｙ［ｉ］
とスカラ変数ｚとの積を新たに配列変数ｘ［ｉ］とし、
かつ配列要素インデックスである変数ｉをインクリメン
トする。したがって、実行するまでループの反復回数が
わからず、逐次処理しかできない。図７（ｂ）は、図７
（ａ）のソースプログラムをループ最適化せずにコンパ
イルした場合の、アセンブリ言語で記述されたオブジェ
クトプログラムである。図７（ｂ）において、初期化の
ための命令列６００に続く、命令列６１０がループを構
成する。該ループを構成する命令相互間では、例えば命
令６１１によってデータが転送されたレジスタｒ０に依
存して、命令６１２が実行されるように、先行して実行
されるべき命令と該命令に後続すべき命令との関係、す
なわちデータ依存関係が存在する。該データ依存関係が
ある場合には、後に処理される命令は先に処理される命
令の結果に常に依存するので、データ依存関係を有する
ループは逐次処理によってのみ処理される。図７（ｃ）
は、図７（ｂ）のプログラムのフローチャート図であ
る。判定工程４０と処理工程４１とからなるループは、
ｘ［ｉ］＝０になるまで逐次処理される。

【０００４】ループ最適化においては、複数の反復を１
回の反復によって処理するために、ループの展開（ルー
プアンローリング）が使用される。図８（ａ）は、図７
（ａ）のソースプログラムを１回ループ展開したプログ
ラムのフローチャート図である。図８（ａ）において
は、図７（ｃ）における２回の反復を、第１判定工程５
０、第１処理工程５１、第２判定工程５２及び第２処理
工程５３よりなる１回の反復によって処理して、ループ
回数を削減する。しかし、第２処理工程５３は第２判定
工程５２の結果が判明した後にのみ実行されるので、デ
ータ依存関係が存在する。したがって、このループ展開
されたプログラムは逐次処理によってしか処理されず、
並列処理できない。

【０００５】また、ループ最適化においては、ループの
命令レベルの並列度を向上させるために、投機的命令が
使用される。投機的命令とは、ある条件分岐命令の実行
に先立って、すなわち分岐先が決まる前に、分岐後の命
令列のうちのいずれかを実行する命令をいう。図８
（ｂ）は、図８（ａ）における第２判定工程５２の前に
第２処理工程５３を配置するように、投機的命令を適用
したプログラムのフローチャート図である。図８（ｂ）
において、第１判定工程６０、第１処理工程６１、第２
処理工程６２及び第２判定工程６３がループを形成す
る。第２処理工程６２における配列変数ｘ’［ｉ］は、
図８（ａ）の第２処理工程５３における配列変数ｘ
［ｉ］の値が一時的に格納される配列変数を示す。実行
文ｘ’［ｉ］＝ｙ［ｉ］＊ｚが実行される際には配列変
数ｘ［ｉ］の更新を行なわず、第２判定工程６３により
条件がｘ［ｉ］≠０に確定した場合には、配列変数ｘ
［ｉ］の値が変数ｘ’［ｉ］によって、かつ、変数ｉの
値がｉ’によってそれぞれ置き換えられる。したがっ
て、投機的命令を使うことにより、図８（ａ）の第２判
定工程５２より後の命令を該第２判定工程５２より前
に、すなわち、条件分岐命令より後の命令を該条件分岐
命令より前に移動させ、かつ先行して実行できる。この
ことにより、ループ展開後に、条件分岐命令を含まない
命令列よりなる基本ブロックが拡大され、更に該基本ブ
ロック内の命令列をスケジューリング（並び替え）する
ことにより、命令レベルの並列度を向上する機会が拡大
される。

【０００６】

【発明が解決しようとする課題】しかしながら、上記従
来の技術によれば、比較命令等の実行結果を符号化した
コンディションコードをプロセッサが保持し得る数、す
なわちコンディションコード数を考慮しないので、プロ
グラム実行開始時にループの反復回数が未定である場合
には、効率的なコードを生成できないという問題があっ
た。すなわち、ループの展開数が、通常のプロセッサに
おいては１個であるコンディションコード数を越える場
合には、該越える分に対応する移動すべき命令列を投機
的命令で置き換えられないので基本ブロックを大きくで
きず、効率的なコードを生成できない。また、コンディ
ションコード数以下の展開数であっても、基本ブロック
における変数の数が、割り当てられたレジスタ数を越え
る場合には、該越える分だけの変数を一時的にメモリへ
退避する必要があるので非効率的なコードが生成され
る。更に、ループを展開した際に、連続するアドレスに
それぞれアクセスするメモリアクセス命令が存在して
も、該メモリアクセス命令が条件分岐にまたがって存在
する場合には１つのメモリアクセス命令では実行できな
いので、オーバヘッドが大きくなる。

【０００７】本発明は、上記従来の問題に鑑み、コンデ
ィションコード数及びレジスタ数に基づいて、効率的な
コードを生成することによってループを最適化する、ル
ープ最適化方法を提供することを目的とする。

【０００８】

【課題を解決するための手段】上記従来の課題を解決す
るために、本発明は、ループ最適化方法を、コンディシ
ョンコード数及びレジスタ数を上限としてループの展開
数を決定する工程と、該ループにおいて新たな条件分岐
命令とループボディとからなる命令列を該決定された展
開数だけ生成して該ループに代えて新たなループを生成
する工程と、該新たなループが有する基本ブロックがで
きるだけ大きくなるように、該生成されたループボディ
を該生成された条件分岐命令より前へ移動させかつ投機
的命令に置き換える工程とを備えた構成とするものであ
る。

【０００９】上記の構成によれば、コンディションコー
ド数及びレジスタ数を上限としてループの展開数を決定
するので、該コンディションコード及びレジスタを有効
に使用して効率的なコードを生成できる。

【００１０】

【発明の実施の形態】

（第１の実施形態）本発明の第１の実施形態に係るルー
プ最適化方法を、図面を参照して説明する。図１は、本
発明の第１の実施形態に係るループ最適化方法を示すフ
ローチャート図である。図１において、第１の工程１０
は、コンパイル処理において構文解析により生成された
中間コードからループを検出して、該検出されたループ
の構造を解析する工程である。第２の工程１１は、該解
析結果に基づいて、ループ実行時にプロセッサが保持し
得るコンディションコード数１２及びレジスタ数１３を
上限として、ループ展開数を決定する工程である。コン
ディションコード数１２及びレジスタ数１３は予め定め
られている。第３の工程１４は、該決定されたループ展
開数だけループを展開し、かつ該展開されたループにお
いて、投機的命令に置き換えたコードを生成する工程で
ある。

【００１１】プロセッサがコンディションコードを２個
保持できる場合において、図７（ａ）のソースプログラ
ムに基づいてループを最適化する方法を説明する。工程
１０において、該ソースプログラムからループを検出か
つ解析し、該ループは実行前において反復回数が未定で
あると認識する。工程１１において、コンディションコ
ード数１２が“２”であることから展開数を“２”に決
定する。工程１４において、展開数“２”に基づいて２
回ループ展開し、該ループ展開されたプログラムにおい
て、投機的命令に置き換えたループボディを条件分岐命
令より前に移動させる。

【００１２】図２（ａ）は、図７（ａ）のソースプログ
ラムを２回ループ展開したプログラムを示す、Ｃ言語に
よるプログラムリストである。図２（ａ）において、実
行文１００，１０２，１０４はそれぞれループボディで
あり、実行文１０１，１０３はそれぞれ条件判定部であ
る。実行文１０２，１０４が新たに生成されたループボ
ディ、実行文１０１，１０３が新たに生成された条件判
定部である。図２（ｂ）は、図２（ａ）のプログラムの
フローチャート図である。図２（ｂ）において、第１の
判定工程２０、第１の処理工程２１、第２の判定工程２
２、第２の処理工程２３、第３の判定工程２４及び第３
の処理工程２５がループを形成する。図２（ａ）の実行
文１００，１０２，１０４はそれぞれ第１，第２，第３
の処理工程２１，２３，２５に対応し、実行文１０１，
１０３はそれぞれ第２，第３の判定工程２２，２４に対
応する。したがって、新たな条件判定部とループボディ
とを生成することによって、図７（ａ）における３回の
反復による処理を、１回の反復によって処理する。

【００１３】図３（ａ）は、コンディションコードを一
時的に記憶するための、プロセッサが有する一時記憶レ
ジスタを説明する概念図である。図３（ａ）において、
データフィールド７０は、データを一時的に記憶するた
めの３２ビットよりなる記憶領域である。タグフィール
ド７１は、レジスタ番号、又はアクセス対象がメモリの
場合にはアドレスを記憶するための記憶領域である。条
件フィールド７２は、コンディションコードを記憶する
ための記憶領域である。データフィールド７０、タグフ
ィールド７１及び条件フィールド７２が一時記憶レジス
タを構成する。図３（ｂ）は、プロセッサが有するレジ
スタファイルを説明する概念図である。該レジスタファ
イルは、３２ビットよりなる汎用レジスタｒ０，ｒ１，
…，ｒ７によって構成される。図３（ａ）の領域８１に
おいて、該領域８１が有するデータフィールドｒ０’
は、タグフィールド７１によって指定された汎用レジス
タｒ０の記憶内容を一時的に記憶する領域である。該領
域８１において、条件フィールド７２にはコンディショ
ンコードＣＣ０が記憶される。該コンディションコード
ＣＣ０が確定して「真」である場合には、データフィー
ルドｒ０’へ記憶された値が、レジスタファイルにおけ
る対応する汎用レジスタｒ０へ記憶される。コンディシ
ョンコードＣＣ０が確定して「偽」である場合には、デ
ータフィールドｒ０’へ記憶された値は対応する汎用レ
ジスタｒ０へ記憶されず、該汎用レジスタｒ０を指定し
ていた、領域８１のタグフィールド７１がクリアされ
る。同様に、領域８２が有するデータフィールドｒ１’
は、タグフィールド７１によって指定された汎用レジス
タｒ１の記憶内容を一時的に記憶する領域である。領域
８３が有するタグフィールド７１は、汎用レジスタｒ１
が記憶するメモリのアドレスを示し、コンディションコ
ードＣＣ０が確定して「真」である場合には、データフ
ィールド［ｒ１］’へ記憶された値が該メモリのアドレ
スへ書き込まれる。領域８４が有するデータフィールド
ｒ０''は、タグフィールド７１に指定された汎用レジス
タｒ０の記憶内容を一時的に記憶する領域である。コン
ディションコードＣＣ０とＣＣ１とが共に確定して共に
「真」である場合には、データフィールドｒ０''へ記憶
された値が、レジスタファイルにおいて対応する汎用レ
ジスタｒ０へ記憶される。

【００１４】図３（ａ）及び（ｂ）のレジスタを有する
プロセッサにおける、本実施形態に係るループ最適化方
法を、図４を参照して説明する。図４（ａ）は、図２
（ａ）のプログラムが有するループボディを移動させ、
かつ投機的命令に置き換えたプログラム、すなわち本実
施形態に係るループ最適化方法の最終結果であるプログ
ラムを示す、Ｃ言語によるプログラムリストである。図
２（ａ）のプログラムが有するループボディである実行
文１００，１０２，１０４のうち、実行文１０２，１０
４を実行文１０１の前に移動させ、かつ投機的命令に置
き換えて、図４（ａ）における実行文２０１，２０２を
生成する。条件判定部２０３において条件がｘ［ｉ］≠
０に確定した場合には、実行文２０１における配列変数
ｘ’［ｉ］と変数ｉ’との値に基づき、配列変数ｘ
［ｉ］の値がｘ’［ｉ］によって、変数ｉの値がｉ’に
よって、それぞれ置き換えられる。条件判定部２０３及
び２０４の結果いずれも条件がｘ［ｉ］≠０に確定した
場合には、双方の条件が確定した時点において、実行文
２０２における配列変数ｘ''［ｉ］と変数ｉ''との値に
基づき、配列変数ｘ［ｉ］の値がｘ''［ｉ］によって、
変数ｉの値がｉ''によって、それぞれ置き換えられる。

【００１５】図４（ｂ）は、図４（ａ）のプログラムの
フローチャート図である。図４（ｂ）において、第１の
判定工程３０、第１の処理工程３１、第２の処理工程３
２、第３の処理工程３３及び第２の判定工程３４がルー
プを形成する。図４（ａ）の実行文２００〜２０２はそ
れぞれ第１〜第３の処理工程３１〜３３に対応し、実行
文２０３，２０４はいずれも第２の判定工程３４に対応
する。図４（ｂ）のフローチャート図は１個のループに
対する最適化を示しているが、プログラムが有する複数
のループに対して、コンディションコード数を上限にし
てループ展開数を決定し、それぞれのループを最適化で
きる。したがって、各ループの特性に応じたループ最適
化が可能となる。

【００１６】以上説明したように、本実施形態によれ
ば、ループの実行開始時に反復回数が未定の場合におい
て、コンディションコード数を上限にして、ループ展開
数を決定する。このことにより、コンディションコード
数を有効に使用して基本ブロックを大きくできるので、
効率的なコードを生成できる。また、プログラムが有す
るそれぞれのループに対して最適化を行なうことによ
り、プログラム自体を最適化できる。したがって、スー
パースカラーやＶＬＩＷ（Ｖｅｒｙ Ｌｏｎｇ Ｉｎｓ
ｔｒｕｃｔｉｏｎ Ｗｏｒｄ）等の並列処理能力を持っ
たプロセッサにおいて、オブジェクトプログラムの実行
効率を向上できる。

【００１７】なお、上述の説明においては、図１のコン
ディションコード数１２に基づくループ最適化方法を説
明した。これに限らず、例えばレジスタ数１３よりなる
ハードウェア資源に基づいて、又はコンディションコー
ド数１２とレジスタ数１３との双方に基づいてループを
最適化することもできる。

【００１８】（第２の実施形態）本発明の第２の実施形
態に係るループ最適化方法を、図面を参照して説明す
る。図５は、本発明の第２の実施形態に係るループ最適
化方法を示すフローチャート図である。第１の実施形態
と同一の構成要件については、図１と同一の符号を付し
てその説明を省略する。図５において、第４の工程１５
は、第３の工程１４において投機的命令に置き換えるこ
とによって生成されたコードの中から、連続するアドレ
スをアクセスするためのメモリアクセス命令を選択し、
かつ、該連続するアドレスの順に、データ依存関係を保
持しつつ該選択されたメモリアクセス命令を並び替える
工程である。第５の工程１６は、該並び替えられたメモ
リアクセス命令を、１つのメモリアクセス命令に置き換
える工程である。

【００１９】図６（ａ）は、図７（ｂ）の命令列６１０
を１回ループ展開したプログラム、すなわち本実施形態
に係るループ最適化方法の対象であるプログラムを示
す、アセンブリ言語によるプログラムリストである。図
６（ａ）において、ｒ０〜ｒ３はそれぞれ３２ビットの
汎用レジスタを示す。汎用レジスタｒ０は、演算結果を
記憶し、かつ配列ｘ又はｙが有する配列変数の値を一時
的に記憶するためのレジスタである。汎用レジスタｒ１
及びｒ２は、配列変数ｘ［ｉ］及びｙ［ｉ］のアドレス
をそれぞれ記憶するためのレジスタである。汎用レジス
タｒ３はスカラ変数ｚの値を記憶するためのレジスタで
ある。条件分岐命令を含まない命令列、すなわち基本ブ
ロック３００と、比較命令及び条件分岐命令を含む命令
列３０１とから構成されたループは、図７（ｂ）の命令
列６１０が構成するループが１回展開されたループであ
る。

【００２０】命令列３０２は、投機的命令３０３〜３０
７から構成される命令列である。以下、投機的命令３０
３〜３０７を説明する。命令３０３は、汎用レジスタｒ
２へ記憶されたメモリのアドレスから始まる２バイトの
データを、一時記憶レジスタが有するデータフィールド
ｒ０’へ転送するためのロード命令である。命令３０４
は、該データフィールドｒ０’の値と汎用レジスタｒ３
の値との積を計算し、かつ該計算された積を該データフ
ィールドｒ０’へ転送するための乗算命令である。命令
３０５は、該データフィールドｒ０’の値を、汎用レジ
スタｒ１へ記憶されたメモリのアドレスへ２バイトだけ
転送するためのストア命令である。命令３０６は、汎用
レジスタｒ１の値、すなわちメモリのアドレスへ２だけ
加算し、かつ、該２だけ加算された新たなアドレスを一
時記憶レジスタが有するデータフィールドｒ１’へ記憶
するための加算命令である。命令３０７は、該データフ
ィールドｒ１’へ記憶されたアドレスから始まる２バイ
トのデータを、データフィールドｒ０’へ転送するため
のロード命令である。

【００２１】図５の第４の工程１５において、基本ブロ
ック３００が有する各命令を、データ依存関係を保持し
たまま、連続するアドレスをアクセスするためのメモリ
アクセス命令ができるだけ連続するように並べ替える。
図６（ｂ）は、該並べ替えられたプログラム、すなわち
本実施形態に係るループ最適化方法の中間結果であるプ
ログラムを示す、アセンブリ言語によるプログラムリス
トである。図６（ｂ）において、命令４００は、汎用レ
ジスタｒ２へ記憶されたメモリのアドレスから始まる２
バイトのデータを、汎用レジスタｒ０へ転送するための
ロード命令である。命令４０１は、図６（ａ）の命令３
０８が前に移動させられたもので、汎用レジスタｒ２の
値、すなわちメモリのアドレスへ２だけ加算し、かつ、
該２だけ加算された新たなアドレスを該汎用レジスタｒ
２へ記憶するための加算命令である。命令４０２は、図
６（ａ）の命令３０３が前に移動させられたもので、汎
用レジスタｒ２へ記憶されたメモリのアドレスから始ま
る２バイトのデータを、データフィールドｒ０’へ転送
するためのロード命令である。命令４０３は、図６
（ａ）の命令３０９が後ろに移動させられたもので、汎
用レジスタｒ１へ記憶されたメモリのアドレスから始ま
る２バイトのデータを、汎用レジスタｒ０へ転送するた
めのロード命令である。命令４０４は、図６（ａ）の命
令３０６に相当し、汎用レジスタｒ１の値、すなわちメ
モリのアドレスへ２だけ加算し、かつ、該２だけ加算さ
れた新たなアドレスをデータフィールドｒ１’へ記憶す
るための加算命令である。命令４０５は、図６（ａ）の
命令３０７に相当し、該データフィールドｒ１’へ記憶
された新たなアドレスから始まる２バイトのデータを、
データフィールドｒ０’へ転送するためのロード命令で
ある。

【００２２】ところで、３２ビットの汎用レジスタを備
えたプロセッサは、通常、１命令で４バイトのデータを
転送できるロード命令を有する。命令４００と前に移動
させられた命令４０２とにおいて、汎用レジスタｒ２が
記憶するメモリのアドレスから始まる２バイトのデータ
を汎用レジスタｒ０へ、該汎用レジスタｒ２が記憶する
アドレスへ２だけ加算された新たなアドレスから始まる
２バイトのデータをデータフィールドｒ０’へ、順次転
送する。該順次転送された４バイトのデータはアドレス
が連続しているので、３２ビットの汎用レジスタを有す
るプロセッサにおいては、１つの汎用レジスタへ該４バ
イトのデータを転送できる。同様に、後ろに移動させら
れた命令４０３と、命令４０５とに基づいて生成される
１つのロード命令を使用して、１つの汎用レジスタへ該
４バイトのデータを転送できる。図５の工程１６におい
て、命令４００と４０２と、及び命令４０３と４０５と
からなるそれぞれ２つのロード命令（メモリアクセス命
令）を、アドレスが連続する４バイトのデータを転送で
きる１つの命令へそれぞれ置き換える。

【００２３】図６（ｃ）は、図６（ｂ）のプログラムに
ついて、命令を置き換えることによって変換したプログ
ラム、すなわち本実施形態に係るループ最適化方法の最
終結果であるプログラムを示す、アセンブリ言語による
プログラムリストである。図６（ｃ）において、命令５
００は、図６（ｂ）の命令４００と４０２に基づいて生
成された、汎用レジスタｒ２へ記憶されたアドレスから
始まる４バイトのデータを汎用レジスタｒ０へ転送する
ためのロード命令である。命令５０１は、図６（ｂ）の
命令４０２によってデータフィールドｒ０’へ２バイト
転送されることに基づいて、汎用レジスタｒ０へ記憶さ
れた４バイトのデータのうち２バイトをデータフィール
ドｒ０’へ転送するための転送命令である。命令５０２
は、図６（ｂ）の命令４０３と４０５とに基づいて生成
された、汎用レジスタｒ１へ記憶されたアドレスから始
まる４バイトのデータを汎用レジスタｒ０へ転送するた
めのロード命令である。命令５０３は、図６（ｂ）の命
令４０５によってデータフィールドｒ０’へ２バイト転
送されることに基づいて、汎用レジスタｒ０へ記憶され
た４バイトのデータのうち２バイトをデータフィールド
ｒ０’へ転送するための転送命令である。

【００２４】以上説明したように、本実施形態によれ
ば、ループ展開後に、連続するアドレスをアクセスする
メモリアクセス命令が条件分岐にまたがって複数存在し
ている場合において、投機的命令に置き換えたうえで該
複数のメモリアクセス命令を並び替え、かつ１つのメモ
リアクセス命令へ置き換える。このことにより、メモリ
アクセスのオーバヘッドが小さくなる。

【００２５】なお、上述の説明においては、図５の第４
の工程１５において、選択されたメモリアクセス命令を
連続するアドレスの順に並び替え、第５の工程１６にお
いて、該並び替えられたメモリアクセス命令を１つのメ
モリアクセス命令に置き換えた。これに代えて、第４の
工程１５において、選択されたメモリアクセス命令を連
続するアドレスの順に認識し、第５の工程１６におい
て、該認識されたメモリアクセス命令を１つのメモリア
クセス命令に置き換えてもよい。

【００２６】

【発明の効果】本発明に係るループ最適化方法によれ
ば、ループの実行開始時に反復回数が未定である場合に
おいて、コンディションコード数及びレジスタ数を上限
にして、ループ展開数を決定する。このことにより、コ
ンディションコード数を有効に使用して基本ブロックを
大きくし、かつ変数が一時的にメモリへ退避することを
防止するので、効率的なコードを生成してループを最適
化できる。また、プログラムが有するそれぞれのループ
に対して最適化を行なうことにより、プログラム自体を
最適化できる。また、連続するアドレスをアクセスし、
かつ条件分岐にまたがって存在する複数のメモリアクセ
ス命令を、投機的命令に置き換えたうえで並び替え、か
つ１つのメモリアクセス命令へ置き換える。このことに
より、メモリアクセスのオーバヘッドを小さくしてプロ
グラムの実行効率を向上できる。

【図面の簡単な説明】

【図１】本発明の第１の実施形態に係るループ最適化方
法を示すフローチャート図である。

【図２】（ａ）は第１の実施形態に係るループ最適化方
法の中間結果であるプログラムを示すＣ言語によるプロ
グラムリスト、（ｂ）は該プログラムのフローチャート
図である。

【図３】（ａ）は一時記憶レジスタを、（ｂ）はレジス
タファイルをそれぞれ説明する概念図である。

【図４】（ａ）は第１の実施形態に係るループ最適化方
法の最終結果であるプログラムを示すＣ言語によるプロ
グラムリスト、（ｂ）は該プログラムのフローチャート
図である。

【図５】本発明の第２の実施形態に係るループ最適化方
法を示すフローチャート図である。

【図６】（ａ）は本発明の第２の実施形態に係るループ
最適化方法の対象であるプログラムを、（ｂ）は中間結
果であるプログラムを、（ｃ）は最終結果であるプログ
ラムをそれぞれ示すアセンブリ言語によるプログラムリ
ストである。

【図７】（ａ）はループ最適化方法の対象であるソース
プログラムをＣ言語によって、（ｂ）は該ソースプログ
ラムをループ最適化せずにコンパイルしたプログラムを
アセンブリ言語によってそれぞれ示すプログラムリスト
であり、（ｃ）は（ｂ）のプログラムのフローチャート
図である。

【図８】（ａ）は図７（ａ）のプログラムを１回ループ
展開したプログラムの、（ｂ）は従来のループ最適化後
のプログラムのそれぞれフローチャート図である。

【符号の説明】

１０ 第１の工程 １１ 第２の工程 １２ コンディションコード数 １３ レジスタ数 １４ 第３の工程 １５ 第４の工程 １６ 第５の工程

Claims (4)

【特許請求の範囲】
1. 【請求項１】 ソースプログラムに基づいて、投機的命
   令を用いるプロセッサが実行するオブジェクトプログラ
   ムを生成するためのコンパイラにおけるループ最適化方
   法であって、 前記プロセッサが保持し得るコンディションコードの数
   を上限として展開数を決定する工程と、 ループにおいて前記決定された展開数に基づき、新たな
   条件分岐命令とループボディとからなる命令列を該展開
   数だけ生成して、前記ループに代わる新たなループを生
   成する工程と、 前記新たなループが有する、条件分岐を含まない命令列
   よりなる基本ブロックができるだけ大きくなるように、
   前記生成されたループボディを、前記生成された条件分
   岐命令より前へ移動させかつ前記投機的命令に置き換え
   る工程とを備えたことを特徴とするループ最適化方法。
2. 【請求項２】 請求項１記載のループ最適化方法であっ
   て、 前記ソースプログラム中のループを検出して該検出され
   たループの構造を解析する工程と、 前記解析されたループの構造と前記プロセッサが保持し
   得るコンディションコードの数の上限とに基づいて、該
   解析されたループ毎に前記展開数を決定する工程とを更
   に備えたことを特徴とするループ最適化方法。
3. 【請求項３】 請求項１又は２のいずれかに記載のルー
   プ最適化方法であって、 前記プロセッサが有するレジスタの数を上限として前記
   展開数を決定する工程を更に備えたことを特徴とするル
   ープ最適化方法。
4. 【請求項４】 請求項１記載のループ最適化方法であっ
   て、 前記ループボディを移動させかつ前記投機的命令に置き
   換えて生成された命令列の中から、連続するアドレスを
   アクセスするためのメモリアクセス命令を選択して、該
   選択されたメモリアクセス命令を、連続するアドレスの
   順に認識し、かつデータ依存関係を保持して１つのメモ
   リアクセス命令へ置き換える工程を更に備えたことを特
   徴とするループ最適化方法。