(57)【特許請求の範囲】
【請求項１】
ソースコードをコンパイルしてオブジェクトコードを生成する情報処理装置において、
外側ループと内側ループの間に分岐命令である分岐言を有する２重ループを、前記分岐言がループ外への分岐ではないこと、前記分岐言以前に変数または配列の定義が存在しないこと、ループ内に前記分岐言が複数含まれていないこと、の条件を満たす場合に前記ソースコードから検出するループ検出手段と、
前記分岐言の真率を算定するソースコードである真率算定コードを生成して前記ソースコードに付加する真率算定コード生成手段と、
前記分岐言を除く２重ループのソースコードを無分岐言ループコードとして前記ソースコードに複写する複写手段と、
前記真率が１００％である場合には、前記無分岐言ループコードに分岐し、それ以外の場合には分岐言を含むもとの２重ループに分岐する分岐コードを生成して前記ソースコードに付加する分岐コード生成手段と、
前記無分岐言ループコードを最適化する最適化手段と、
を有することを特徴とする情報処理装置。
【請求項２】
ソースコードをコンパイルしてオブジェクトコードを生成する処理をコンピュータに機能させるプログラムを記録したコンピュータ読み取り可能な記録媒体において、
コンピュータを、
外側ループと内側ループの間に分岐命令である分岐言を有する２重ループを、前記分岐言がループ外への分岐ではないこと、前記分岐言以前に変数または配列の定義が存在しないこと、ループ内に前記分岐言が複数含まれていないこと、の条件を満たす場合に前記ソースコードから検出するループ検出手段、
前記分岐言の真率を算定するソースコードである真率算定コードを生成して前記ソースコードに付加する真率算定コード生成手段、
前記分岐言を除く２重ループのソースコードを無分岐言ループコードとして前記ソースコードに複写する複写手段、
前記真率が１００％である場合には、前記無分岐言ループコードに分岐し、それ以外の場合には分岐言を含むもとの２重ループに分岐する分岐コードを生成して前記ソースコードに付加する分岐コード生成手段、
前記無分岐言ループコードを最適化する最適化手段、
として機能させるプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項３】
ソースコードをコンパイルしてオブジェクトコードを生成する処理をコンピュータに機能させるプログラムにおいて、
コンピュータを、
外側ループと内側ループの間に分岐命令である分岐言を有する２重ループを、前記分岐言がループ外への分岐ではないこと、前記分岐言以前に変数または配列の定義が存在しないこと、ループ内に分岐言が複数含まれていないこと、の条件を満たす場合に前記ソースコードから検出するループ検出手段、
前記分岐言の真率を算定するソースコードである真率算定コードを生成して前記ソースコードに付加する真率算定コード生成手段、
前記分岐言を除く２重ループのソースコードを無分岐言ループコードとして前記ソースコードに複写する複写手段、
前記真率が１００％である場合には、前記無分岐言ループコードに分岐し、それ以外の場合には分岐言を含むもとの２重ループに分岐する分岐コードを生成して前記ソースコードに付加する分岐コード生成手段、
前記無分岐言ループコードを最適化する最適化手段、
として機能させるプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は情報処理装置に関し、特に、ソースコードをコンパイルしてオブジェクトコードを生成する情報処理装置に関する。
【０００２】
【従来の技術】
プログラムを最適化する方法は従来から種々提案されている。例えば、その一例として、多重ループを単一ループに変換する方法やインデックスを入れ換える方法がある。
【０００３】
図７は、前者の多重ループを単一ループに変換する方法を説明する図である。
図７（Ａ）に示すソースプログラムでは、行番号“０１”において、２行２列で要素数がそれぞれ“１０”である実数型の行列Ａ，Ｂ，Ｃが宣言されている。
【０００４】
行番号“０２”には、インデックスＪを“１”から“１０”までカウントアップするループが記述されており、これは行番号“０６”を終端とするループである。また、行番号“０３”には、インデックスＩを１から１０までカウントアップするループが記述されており、これは行番号“０５”を終端とするループである。従って、このソースプログラムは、インデックスＩ，Ｊによる２重ループが形成されている。
【０００５】
行番号“０４”では、配列Ｂの要素（Ｉ，Ｊ）と配列Ｃの要素（Ｉ，Ｊ）を加算した値を配列Ａの要素（Ｉ，Ｊ）に対して格納する演算が実行される。
このような２重ループに対しては、図７（Ｂ）に示すように、インデックスＩおよびインデックスＪをまとめてインデックスＩＪとし、これを１から１００までカウントアップする１重ループに変換することにより、変数の数を減らして処理を高速化することができる。
【０００６】
図８は、後者のインデックスを入れ換える方法を説明する図である。
図８（Ａ）に示すソースコードは、図７（Ａ）の場合と同様である。この例では、図８（Ｂ）に示すように、内側と外側のインデックスを入れ換えることにより、メモリへのアクセスを連続にし、最適化を図っている。即ち、２次元配列は、メモリ上の連続した領域に確保されるので、この領域へのアクセスが連続して行われるようにインデックスの入れ換えを行う。
【０００７】
なお、以上の例は、２重ループを例に挙げて説明したが、それ以上の多重ループの場合にも前述の方法によって同様の効果を得ることができる。
【０００８】
【発明が解決しようとする課題】
しかし、以上のような多重ループの最適化方法は、外側ループと内側ループの間（以下、セカンダリと称す）に分岐を伴う命令（分岐言）が存在しないことが条件となる。従って、セカンダリに分岐言が存在している場合には、最適化ができないという問題点があった。
【０００９】
本発明は、このような点に鑑みてなされたものであり、セカンダリに分岐言を含む多重ループであっても最適化することが可能な情報処理装置を提供することを目的とする。
【００１０】
【課題を解決するための手段】
本発明では上記課題を解決するために、ソースコードをコンパイルしてオブジェクトコードを生成する情報処理装置において、外側ループと内側ループの間に分岐命令である分岐言を有する２重ループを、前記分岐言がループ外への分岐ではないこと、前記分岐言以前に変数または配列の定義が存在しないこと、ループ内に前記分岐言が複数含まれていないこと、の条件を満たす場合に前記ソースコードから検出するループ検出手段と、前記分岐言の真率を算定するソースコードである真率算定コードを生成して前記ソースコードに付加する真率算定コード生成手段と、前記分岐言を除く２重ループのソースコードを無分岐言ループコードとして前記ソースコードに複写する複写手段と、前記真率が１００％である場合には、前記無分岐言ループコードに分岐し、それ以外の場合には分岐言を含むもとの２重ループに分岐する分岐コードを生成して前記ソースコードに付加する分岐コード生成手段と、前記無分岐言ループコードを最適化する最適化手段と、を有することを特徴とする情報処理装置が提供される。
【００１２】
【発明の実施の形態】
以下、本発明の実施の形態を図面を参照して説明する。
図１は、本発明の実施の形態の構成例を示すブロック図である。この図において、記憶装置１はコンパイル処理の対象となるソースコードを格納している。
【００１３】
多重ループ検出手段２は、セカンダリに分岐言を有する多重ループを記憶装置１から供給されたソースコードから検出する。
真率算定コード生成手段３は、多重ループに含まれている分岐言の真率を算定するコードである真率算定コードを生成してソースコードに付加する。
【００１４】
複写手段４は、分岐言を除く多重ループのコードを無分岐言ループコードとしてソースコードに複写する。
分岐コード生成手段５は、真率が１００％である場合には、無分岐言ループコードに分岐し、それ以外の場合には分岐言を含むもとの多重ループに分岐する分岐コードを生成してソースコードに付加する。
【００１５】
最適化手段６は、無分岐言ループコードを最適化する。
次に、以上の実施の形態の動作について説明する。先ず、以下では、図２を参照して本発明の動作原理を簡単に説明した後、具体的な動作について説明する。
【００１６】
図２（Ａ）は、最適化の対象とするソースコードの一例を示す図である。このソースコードでは、行番号“０１”において、要素数が“１０”の実数型１次元配列Ｃが宣言されており、また、行番号“０２”において、要素数が１０×１０の実数型２次元配列Ａ，Ｂが宣言されている。
【００１７】
また、行番号“０３”には、インデックスＩを１から１０までカウントアップするループが記述されており、これは行番号“０９”を終端とするループである。また、行番号“０５”には、インデックスＪを１から１０までカウントアップするループが記述されており、これは行番号“０７”を終端とするループである。従って、このソースプログラムは、インデックスＩ，Ｊによる２重ループが形成されている。
【００１８】
行番号“０４”には、判断命令が記述されており、これは、配列Ｃの第Ｉ番目の要素が“１”よりも大きい場合にのみ行番号“０５”から行番号“０７”までの処理に分岐する判断命令である。従って、これは分岐言である。
【００１９】
ここで、分岐言の条件が全ての場合において必ず真ならば、図２（Ａ）は、図２（Ｂ）に示すように簡略化することができる。この場合には、セカンダリに分岐言を含まない通常の多重ループであるので、前述の何れかの方法により最適化することができる。
【００２０】
本発明ではこのように、多重ループのセカンダリに存在している分岐言が全ての場合において真であるか否かを判定し、真である場合にはその分岐言を除外して得られた多重ループを最適化したものを実行し、それ以外の場合にはもとの多重ループ（分岐言を含む多重ループ）を実行する。
【００２１】
次に、図１に示す実施例の具体的な動作を図２（Ａ）に示すソースコードを例に挙げて説明する。
いま、記憶装置１には、図２（Ａ）に示すソースコードが格納されており、このソースコードをコンパイルの対象として処理が開始されたとすると、多重ループ検出手段２は、記憶装置１から該当するソースコードを読み込み、セカンダリに分岐言を有する多重ループを検出する。
【００２２】
真率算定コード生成手段３は、多重ループ検出手段２によって検出された分岐言をセカンダリに含む多重ループから、分岐言を抽出するとともにインデックスの値の変化を参照して分岐言の真率を算定するソースコードである真率算定コード生成する。
【００２３】
真率算定コードの一例を図３の行番号“０１”から“０５”に示す。この例では、行番号“０１”において、変数ＭＡＳＫ２が宣言されるとともにその初期値が“０”に設定されている。
【００２４】
行番号“０２”には、インデックスＩ’を１から１０までカウントアップするループが記述されており、これは行番号“０５”を終端とするループである。
ループ間である、行番号“０３”には、「配列Ｃの第Ｉ’番目の要素が“１”以下である」という命題に対する真理値が変数ＭＡＳＫ１に格納される。従って、配列Ｃの第Ｉ’番目の要素が“１”より大きい場合（図２（Ａ）の行番号“０４”に示す分岐言が真となる場合）にはこの命題は偽となるので、ＭＡＳＫ１には“０”が代入される。
【００２５】
行番号“０４”では、変数ＭＡＳＫ２に対してＭＡＳＫ１の値が累積加算される。従って、行番号“０３”の命題が全て偽である場合（即ち、図２（Ａ）の行番号“０４”に示す分岐言が全て真となる場合）には、変数ＭＡＳＫ２の値は“０”となる。
【００２６】
次に、複写手段４は、対象となる多重ループを取得してその中から分岐言を除外する。そして、得られた多重ループのコードを、無分岐言ループコードとしてソースコードに複写する。
【００２７】
無分岐言ループコードの一例を図３の行番号“１９”から“２３”に示す。この例では、図２（Ａ）に示す２重ループから行番号“０４”の分岐言が除外されたコードが複写されている。
【００２８】
次に、分岐コード生成手段５は、真率が１００％である場合には、無分岐言ループコードに分岐し、それ以外の場合には分岐言を含むもとの多重ループに分岐する分岐コードを生成してソースコードに付加する。
【００２９】
無分岐言ループコードの一例を図３の行番号“０７”に示す。この例では、変数ＭＡＳＫ２の値が“０”である場合、即ち、全ての場合において図２（Ａ）の行番号“０４”に示す分岐言が真である場合には行番号“１９”に進み、それ以外の場合には行番号“０９”以降の処理が実行される。なお、行番号“０９”から“１５”までは、もとのソースコードであり、分岐言がセカンダリに含まれている。従って、変数ＭＡＳＫ２の値が“０”以外である場合には通常の処理が実行される。
【００３０】
なお、分岐コード生成手段５は、行番号“１７”に対して新たな分岐命令（無条件分岐命令）を付加しているので、行番号“０９”から行番号“１５”の処理が終了した場合には、行番号“２５”に無条件に分岐し、行番号“１９”以降の処理の実行を中止する。
【００３１】
最適化手段６は、以上のようにして生成されたソースコードに含まれている、無分岐言ループ（セカンダリに分岐言を有しない通常の多重ループ）を検出して、これを前述した方法の何れかによって最適化する。
【００３２】
コンパイル部７は、最適化手段６によって最適化された部分を含むソースコードをコンパイルしてオブジェクトコードを生成し、記憶装置８に供給してそこに記憶させる。
【００３３】
次に、以上の処理によって生成されたソースコードの概要について説明する。
図４は、図２（Ａ）に示すソースコードの行番号“０３”から“０９”までの処理の流れを模式的に示した図である。この図において、白丸「○」は、各行に記述されたコードに対応しており、また矢印は処理の流れを示している。この図に示すように、“＃１”と“＃７”は外側のループを構成しており、また、“＃３”と“＃５”は、内側のループを構成している。更に、“＃２”は分岐言であり、判断の結果に応じて“＃３”または“＃６”に分岐する。
【００３４】
図５は、図３に示すソースコードの処理の流れを模式的に示す図である。この図において黒丸「●」は、新たに追加されたコードを示している。即ち、“＃Ａ”は、図３に示す行番号“０１”から“０７”までに対応している。“＃Ｂ”は、図３に示す行番号“１７”に対応している。“＃１’”から“＃７’”は、図３に示す行番号“１９”から“２３”までに対応しており無分岐言ループである。また、“＃Ｃ”は、図３に示す行番号“２５”の「ＥＮＤ」に対応している。
【００３５】
このソースコードが実行されると、先ず、“＃Ａ”の分岐コードにより真率が算定され、真率が“１００％”である場合には“＃１’”に進み、それ以外の場合には“＃１”以降の処理が実行される。なお、“＃１”以降の処理が実行された場合には、“＃Ｂ”において無条件に“＃Ｃ”に分岐して処理を終了する。
【００３６】
また、“＃１’”に分岐した場合には、無分岐言ループ（最適化されたループ）が実行されることになる。
以上の処理によれば、セカンダリに分岐言を有する多重ループがソースコードに存在している場合には、分岐言の真率を算定する真率算定コードと、分岐言を除く多重ループのソースコード（無分岐言ループコード）と、真率が１００％である場合には、無分岐言ループコードに分岐し、それ以外の場合には分岐言を含むもとの多重ループに分岐する分岐言をソースコードに付加し、無分岐言ループコードに対しては最適化を施すようにしたので、セカンダリに分岐言を含むソースコードを最適化することが可能となる。
【００３７】
最後に、図６を参照して、図１に示す実施の形態において実行される処理の一例について説明する。
［Ｓ１］多重ループ検出手段２は、記憶装置１に記憶されているソースコードから多重ループを検出した場合にはステップＳ２に進み、それ以外の場合にはステップＳ１に戻って同様の処理を繰り返す。
［Ｓ２］多重ループ検出手段２は、ステップＳ１において検出した多重ループがセカンダリに分岐言を含むか否かを判定し、分岐言を含む場合にはステップＳ３に進み、それ以外の場合にはステップＳ２に戻って同様の処理を繰り返す。
［Ｓ３］多重ループ検出手段２は、検出した多重化ループが後述する条件を満足しているか否かを判定し、満足している場合にはステップＳ４に進み、それ以外の場合にはステップＳ１に戻って同様の処理を繰り返す。
【００３８】
ここで、判断の条件を以下に示す。
（１）ループ内の分岐命令は１つである。
（２）ループからの飛び出しになる分岐ではない。
（３）分岐命令以前に変数または配列への定義がない。
（４）分岐命令はセカンダリに存在する。
【００３９】
なお、このような条件を課すのは、ループの最適化によって削減されるコストよりも新たに発生するコストの方が高くつくことを防止するためである。例えば、（１）の例では、分岐命令が複数存在する場合には、全ての分岐命令に対して真率を求める必要が生じ、そのコストの方が最適化によるコストの削減を上回る場合が想定されるからである。
［Ｓ４］複写手段４は、ソースコードから分岐言を除くループを取得する。
［Ｓ５］複写手段４は、ステップＳ４で取得した分岐言を除くループ（無分岐言ループ）をソースコードに対して複写する。
［Ｓ６］分岐コード生成手段５は、ソースコードから分岐言を取得する。
［Ｓ７］分岐コード生成手段５は、真率算定コードを生成してソースコードに付加する。
［Ｓ８］分岐コード生成手段５は、分岐コードを生成してソースコードに付加する。
［Ｓ９］情報処理装置は、処理を継続するか否かを判定し、継続する場合にはステップＳ１に戻って前述の場合と同様の処理を繰り返し、それ以外の場合にはステップＳ１０に進む。
［Ｓ１０］最適化手段６は、無分岐言ループコードに対して最適化処理を施す。
【００４０】
なお、この最適化処理は、図７または図８を参照して説明した２種類の最適化処理の何れを用いてもよい。
［Ｓ１１］コンパイル部７は、最適化されたソースコードに対してコンパイル処理を施し、得られたオブジェクトコードを記憶装置８に対して出力する。
【００４１】
以上の処理によれば、図１に示す実施の形態の動作を実現することが可能となる。
なお、以上の実施の形態では、２重ループの場合を例に挙げて説明したが、３重ループ以上の場合にも本発明を適用することができることはいうまでもない。
【００４２】
最後に、上記の処理機能は、コンピュータによって実現することができる。その場合、情報処理装置が有すべき機能の処理内容は、コンピュータで読み取り可能な記録媒体に記録されたプログラムに記述されており、このプログラムをコンピュータで実行することにより、上記処理がコンピュータで実現される。コンピュータで読み取り可能な記録媒体としては、磁気記録装置や半導体メモリ等がある。市場へ流通させる場合には、ＣＤ−ＲＯＭ(Compact Disk Read Only Memory)やフロッピーディスク等の可搬型記録媒体にプログラムを格納して流通させたり、ネットワークを介して接続されたコンピュータの記憶装置に格納しておき、ネットワークを通じて他のコンピュータに転送することもできる。コンピュータで実行する際には、コンピュータ内のハードディスク装置等にプログラムを格納しておき、メインメモリにロードして実行する。
【００４３】
【発明の効果】
以上説明したように本発明では、ソースコードをコンパイルしてオブジェクトコードを生成する情報処理装置において、セカンダリに分岐言を有する多重ループをソースコードから検出する多重ループ検出手段と、分岐言の真率を算定するソースコードである真率算定コードを生成してソースコードに付加する真率算定コード生成手段と、分岐言を除く多重ループのソースコードを無分岐言ループコードとしてソースコードに複写する複写手段と、真率が１００％である場合には、無分岐言ループコードに分岐し、それ以外の場合には分岐言を含むもとの多重ループに分岐する分岐コードを生成してソースコードに付加する分岐コード生成手段と、無分岐言ループコードを最適化する最適化手段と、を有するようにしたので、セカンダリに分岐言を有する多重ループを最適化することが可能となる。
【図面の簡単な説明】
【図１】本発明の実施の形態の構成例を示すブロック図である。
【図２】本発明の動作原理を説明する図である。
【図３】図２に示すソースコードに対して最適化を施した場合に得られるソースコードの一例である。
【図４】図２（Ａ）に示すソースコードの行番号“０３”から“０９”までの処理の流れを模式的に示した図である。
【図５】図３に示すソースコードの処理の流れを模式的に示す図である。
【図６】図１に示す実施の形態において実行される処理の一例を説明するフローチャートである。
【図７】多重ループを単一ループに変換する最適化方法を説明する図である。
【図８】多重ループのインデックスを入れ換える最適化方法を説明する図である。
【符号の説明】
１  記憶装置
２  多重ループ検出手段
３  真率算定コード生成手段
４  複写手段
５  分岐コード生成手段
６  最適化手段
７  コンパイル部
８  記憶装置
【図１】
0004579425.tif 000002
【図２】
0004579425.tif 000003
【図３】
0004579425.tif 000004
【図４】
0004579425.tif 000005
【図５】
0004579425.tif 000006
【図６】
0004579425.tif 000007
【図７】
0004579425.tif 000008
【図８】
0004579425.tif 000009