(57)【要約】【課題】ループ内で不変でない演算であっても所定の条件を満たすときはループ内不変式に変形してループ外で実行できるようにする。【解決手段】検出手段１２は、演算に使用される変数の全てが、ループ内で不変であるか、ループ内の複数箇所で定義されているがそのいずれかが必ずこの演算に先立って実行されかつそのいずれもがループ内で不変の値が代入されている変数である演算を検出する。複写手段１４は、検出された演算に対して、その演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に当該演算を複写し、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の上記演算を一時的に使用する変数から上記演算の結果を保持する変数への代入に置き換えることで、ループ内で不変でない演算をループ内不変式としてループの外で計算できるように変形する。【選択図】　図１
2004062489.tif 000002
【特許請求の範囲】
【請求項１】
ソースプログラムを解釈して中間コードを生成し最適化を行ってオブジェクトコードを生成するコンパイラにおいて、
ループ内で値が不変である変数と結果が不変である演算を検出するループ内不変式検出手段と、
演算に使用される変数の全てが、ループ内で不変であるか、ループ内の複数箇所で定義されているがそのいずれかが必ずこの演算に先立って実行されかつそのいずれもがループ内で不変の値が代入されている変数であるかのいずれかである、第一次複写可能演算を検出する第一次複写可能演算検出手段と、
上記第一次複写可能演算検出手段で検出された第一次複写可能演算に対して、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に第一次複写可能演算を複写し、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の上記第一次複写可能演算を一時的に使用する変数から上記第一次複写可能演算の結果を保持する変数への代入に置き換える、第一次複写可能演算複写手段とを備え、
演算で使用している変数がループ内で不変な値を選択的に使用しているためにループ内不変式として移動できない演算をループの外で計算できるように変形することを特徴とするループ内不変な式の移動に関する最適化方式。
【請求項２】
ソースプログラムを解釈して中間コードを生成し最適化を行ってオブジェクトコードを生成するコンパイラにおいて、
ループ内で値が不変である変数と結果が不変である演算を検出するループ内不変式検出手段と、
演算に使用される変数の全てが、ループ内で不変であるか、ループ内の複数箇所で定義されているがそのいずれかが必ずこの演算に先立って実行されかつそのいずれもがループ内で不変の値が代入されている変数であるかのいずれかである、第一次複写可能演算を検出する第一次複写可能演算検出手段と、
演算に使用される変数の全てが、ループ内で不変であるか、上記第一次複写可能演算検出手段で検出された第一次複写可能演算の結果であるかのいずれかであり、かついずれの第一次複写可能演算もその結果を代入される変数は１箇所でのみ定義されていてかつ必ずこの演算に先立って実行されているものである、第二次複写可能演算を検出する第二次複写可能演算検出手段と、
上記第一次複写可能演算検出手段で検出された第一次複写可能演算に対して、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に第一次複写可能演算を複写し、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の上記第一次複写可能演算を一時的に使用する変数から上記第一次複写可能演算の結果を保持する変数への代入に置き換える、第一次複写可能演算複写手段と、
上記第二次複写可能演算検出手段で検出された第二次複写可能演算に対して、演算で使用している第一次複写可能演算の、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に複写された第一次複写可能演算の直後に、上記第二次複写可能演算を複写し、その複写した演算で引用している複数の箇所で定義されている変数を上記第一次複写可能演算で使用した一時的な変数に置き換え、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の上記第二次複写可能演算を一時的に使用する変数から上記第二次複写可能演算の結果を保持する変数への代入に置き換える、第二次複写可能演算複写手段とを備え、
演算で使用している変数がループ内で不変な値を選択的に使用しているためにループ内不変式として移動できない演算をループの外で計算できるように変形することを特徴とするループ内不変な式の移動に関する最適化方式。
【請求項３】
ソースプログラムを解釈して中間コードを生成し最適化を行ってオブジェクトコードを生成するコンパイラにおいて、
ループ内で値が不変である変数と結果が不変である演算を検出するループ内不変式検出手段と、
演算に使用される変数の全てが、ループ内で不変であるか、ループ内の複数箇所で定義されているがそのいずれかが必ずこの演算に先立って実行されかつそのいずれもがループ内で不変の値が代入されている変数であるかのいずれかである、第一次複写可能演算を検出する第一次複写可能演算検出手段と、
演算に使用される変数の全てが、ループ内で不変であるか、ループ内の複数箇所で定義されているがそのいずれかが必ずこの演算に先立って実行されかつそのいずれもがループ内で不変の値が代入されている変数であるか、上記第一次複写可能演算検出手段で検出された第一次複写可能演算の結果であるかのいずれかであり、かついずれの第一次複写可能演算もその結果を代入される変数は１箇所でのみ定義されていてかつ必ずこの演算に先立って実行されているものである、第二次複写可能演算を検出する第二次複写可能演算検出手段と、
上記第一次複写可能演算検出手段で検出された第一次複写可能演算に対して、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に第一次複写可能演算を複写し、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の上記第一次複写可能演算を一時的に使用する変数から上記第一次複写可能演算の結果を保持する変数への代入に置き換える、第一次複写可能演算複写手段と、
上記第二次複写可能演算検出手段で検出された第二次複写可能演算に対して、複数の箇所で定義されいずれかの定義がこの演算に先立って実行されておりかついずれの定義においてもループ内で不変の値が代入される変数については、この演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に演算を複写し、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の演算を一時的に使用する変数から演算の結果を保持する変数への代入に置き換え、且つ、第一次複写可能演算で定義される変数については、第二次複写可能演算に対し、演算で使用している第一次複写可能演算の、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に複写された第一次複写可能演算の直後に、上記第二次複写可能演算を複写し、その複写した演算で引用している複数の箇所で定義されている変数を上記第一次複写可能演算で使用した一時的な変数に置き換え、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の上記第二次複写可能演算を一時的に使用する変数から上記第二次複写可能演算の結果を保持する変数への代入に置き換え、その上で、上記第二次複写可能演算を、新しく生成した変数に置き換える、第二次複写可能演算複写手段とを備え、
演算で使用している変数がループ内で不変な値を選択的に使用しているためにループ内不変式として移動できない演算をループの外で計算できるように変形することを特徴とするループ内不変な式の移動に関する最適化方式。
【請求項４】
ソースプログラムを解釈して中間コードを生成し最適化を行ってオブジェクトコードを生成するコンピュータを、
ループ内で値が不変である変数と結果が不変である演算を検出するループ内不変式検出手段、
演算に使用される変数の全てが、ループ内で不変であるか、ループ内の複数箇所で定義されているがそのいずれかが必ずこの演算に先立って実行されかつそのいずれもがループ内で不変の値が代入されている変数であるかのいずれかである、第一次複写可能演算を検出する第一次複写可能演算検出手段、
上記第一次複写可能演算検出手段で検出された第一次複写可能演算に対して、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に第一次複写可能演算を複写し、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の上記第一次複写可能演算を一時的に使用する変数から上記第一次複写可能演算の結果を保持する変数への代入に置き換える、第一次複写可能演算複写手段、
として機能させ、演算で使用している変数がループ内で不変な値を選択的に使用しているためにループ内不変式として移動できない演算をループの外で計算できるように変形することを特徴とするプログラム。
【請求項５】
ソースプログラムを解釈して中間コードを生成し最適化を行ってオブジェクトコードを生成するコンピュータを、
ループ内で値が不変である変数と結果が不変である演算を検出するループ内不変式検出手段、
演算に使用される変数の全てが、ループ内で不変であるか、ループ内の複数箇所で定義されているがそのいずれかが必ずこの演算に先立って実行されかつそのいずれもがループ内で不変の値が代入されている変数であるかのいずれかである、第一次複写可能演算を検出する第一次複写可能演算検出手段、
演算に使用される変数の全てが、ループ内で不変であるか、上記第一次複写可能演算検出手段で検出された第一次複写可能演算の結果であるかのいずれかであり、かついずれの第一次複写可能演算もその結果を代入される変数は１箇所でのみ定義されていてかつ必ずこの演算に先立って実行されているものである、第二次複写可能演算を検出する第二次複写可能演算検出手段、
上記第一次複写可能演算検出手段で検出された第一次複写可能演算に対して、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に第一次複写可能演算を複写し、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の上記第一次複写可能演算を一時的に使用する変数から上記第一次複写可能演算の結果を保持する変数への代入に置き換える、第一次複写可能演算複写手段、
上記第二次複写可能演算検出手段で検出された第二次複写可能演算に対して、演算で使用している第一次複写可能演算の、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に複写された第一次複写可能演算の直後に、上記第二次複写可能演算を複写し、その複写した演算で引用している複数の箇所で定義されている変数を上記第一次複写可能演算で使用した一時的な変数に置き換え、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の上記第二次複写可能演算を一時的に使用する変数から上記第二次複写可能演算の結果を保持する変数への代入に置き換える、第二次複写可能演算複写手段、
として機能させ、演算で使用している変数がループ内で不変な値を選択的に使用しているためにループ内不変式として移動できない演算をループの外で計算できるように変形することを特徴とするプログラム。
【請求項６】
ソースプログラムを解釈して中間コードを生成し最適化を行ってオブジェクトコードを生成するコンピュータを、
ループ内で値が不変である変数と結果が不変である演算を検出するループ内不変式検出手段、
演算に使用される変数の全てが、ループ内で不変であるか、ループ内の複数箇所で定義されているがそのいずれかが必ずこの演算に先立って実行されかつそのいずれもがループ内で不変の値が代入されている変数であるかのいずれかである、第一次複写可能演算を検出する第一次複写可能演算検出手段、
演算に使用される変数の全てが、ループ内で不変であるか、ループ内の複数箇所で定義されているがそのいずれかが必ずこの演算に先立って実行されかつそのいずれもがループ内で不変の値が代入されている変数であるか、上記第一次複写可能演算検出手段で検出された第一次複写可能演算の結果であるかのいずれかであり、かついずれの第一次複写可能演算もその結果を代入される変数は１箇所でのみ定義されていてかつ必ずこの演算に先立って実行されているものである、第二次複写可能演算を検出する第二次複写可能演算検出手段、
上記第一次複写可能演算検出手段で検出された第一次複写可能演算に対して、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に第一次複写可能演算を複写し、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の上記第一次複写可能演算を一時的に使用する変数から上記第一次複写可能演算の結果を保持する変数への代入に置き換える、第一次複写可能演算複写手段、
上記第二次複写可能演算検出手段で検出された第二次複写可能演算に対して、複数の箇所で定義されいずれかの定義がこの演算に先立って実行されておりかついずれの定義においてもループ内で不変の値が代入される変数については、この演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に演算を複写し、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の演算を一時的に使用する変数から演算の結果を保持する変数への代入に置き換え、且つ、第一次複写可能演算で定義される変数については、第二次複写可能演算に対し、演算で使用している第一次複写可能演算の、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に複写された第一次複写可能演算の直後に、上記第二次複写可能演算を複写し、その複写した演算で引用している複数の箇所で定義されている変数を上記第一次複写可能演算で使用した一時的な変数に置き換え、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の上記第二次複写可能演算を一時的に使用する変数から上記第二次複写可能演算の結果を保持する変数への代入に置き換え、その上で、上記第二次複写可能演算を、新しく生成した変数に置き換える、第二次複写可能演算複写手段、
として機能させ、演算で使用している変数がループ内で不変な値を選択的に使用しているためにループ内不変式として移動できない演算をループの外で計算できるように変形することを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンパイラの最適化方式に関し、特に演算で使用している変数がループ内で不変な値を選択的に使用しているためにループ内不変式として移動できない演算をループの外で計算できるように変形する最適化に関する。
【０００２】
【従来の技術】
一般にコンパイラは、図１１のコンパイラ１００に示すように、高級言語で記述されたソースプログラム２００を入力し、構文解析部１０１によって字句解析、構文解析、意味解析等を行って中間テキスト１０４を生成し、次いで、最適化部１０２によって中間テキスト１０４に対して最適化処理を施した中間テキスト１０５を生成し、次いで、コード生成部１０３によって中間テキスト１０５から機械語命令のオブジェクトプログラム３００を生成して出力する。最適化部１０２では各種の最適化が実施されるが、その１つに、繰り返し実行される部分（つまりループ）内に存在するループ内不変式をループ外に移動することにより、無駄な計算の繰り返しを無くす最適化処理がある。ここで、ループ内不変式とは、ループの実行回数にかかわらず計算結果が常に一定になる演算を言う。本発明はこのようなループ内不変式の最適化に関する。
【０００３】
従来、この種のループ内で不変な式の最適化は、特開平５−１８９２４４号公報に示されるように、自明なループ内で不変な式の検出を行い、その後、それらの不変な式を使用している式が不変となるかどうかの調査を行う。このため、演算の結果がループ内で不変な値を持つ場合にのみ、ループ外への移動の最適化が行われ、ループ内で不変な値を持つ変数が複数の個所で選択的に定義され、その変数を参照する演算の場合は、このような演算はループ内不変式でないと判断され、最適化の対象にはされなかった。
【０００４】
【発明が解決しようとする課題】
しかし、ある演算が、ループ内の複数の箇所で選択的にループ内で不変な値を定義されている変数を参照する場合、異なる繰り返しであっても、実際に変数が定義されている箇所が同じならば同じ演算結果となる。すなわち、同じ結果を得る演算をループの繰り返しにおいて何度も実行することになり、実行時間が長くなっている。
【０００５】
【発明の目的】
本発明の目的は、ある演算において、その演算で参照している変数が、ループ内の複数の箇所で選択的にループ内で不変な値を定義されている場合にも、ループ内で不変な演算として可能な限り多くをループ外に移動できるようプログラムを変形し得るようにすることにある。
【０００６】
【課題を解決するための手段】
第１の発明は、ソースプログラムを解釈して中間コードを生成し最適化を行ってオブジェクトコードを生成するコンパイラにおいて、ループ内で値が不変である変数と結果が不変である演算を検出するループ内不変式検出手段と、演算に使用される変数の全てが、ループ内で不変であるか、ループ内の複数箇所で定義されているがそのいずれかが必ずこの演算に先立って実行されかつそのいずれもがループ内で不変の値が代入されている変数であるかのいずれかである、第一次複写可能演算を検出する第一次複写可能演算検出手段と、上記第一次複写可能演算検出手段で検出された第一次複写可能演算に対して、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に第一次複写可能演算を複写し、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の上記第一次複写可能演算を一時的に使用する変数から上記第一次複写可能演算の結果を保持する変数への代入に置き換える、第一次複写可能演算複写手段とを備え、演算で使用している変数がループ内で不変な値を選択的に使用しているためにループ内不変式として移動できない演算をループの外で計算できるように変形することを特徴とする。
【０００７】
第２の発明は、ソースプログラムを解釈して中間コードを生成し最適化を行ってオブジェクトコードを生成するコンパイラにおいて、ループ内で値が不変である変数と結果が不変である演算を検出するループ内不変式検出手段と、演算に使用される変数の全てが、ループ内で不変であるか、ループ内の複数箇所で定義されているがそのいずれかが必ずこの演算に先立って実行されかつそのいずれもがループ内で不変の値が代入されている変数であるかのいずれかである、第一次複写可能演算を検出する第一次複写可能演算検出手段と、演算に使用される変数の全てが、ループ内で不変であるか、上記第一次複写可能演算検出手段で検出された第一次複写可能演算の結果であるかのいずれかであり、かついずれの第一次複写可能演算もその結果を代入される変数は１箇所でのみ定義されていてかつ必ずこの演算に先立って実行されているものである、第二次複写可能演算を検出する第二次複写可能演算検出手段と、上記第一次複写可能演算検出手段で検出された第一次複写可能演算に対して、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に第一次複写可能演算を複写し、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の上記第一次複写可能演算を一時的に使用する変数から上記第一次複写可能演算の結果を保持する変数への代入に置き換える、第一次複写可能演算複写手段と、上記第二次複写可能演算検出手段で検出された第二次複写可能演算に対して、演算で使用している第一次複写可能演算の、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に複写された第一次複写可能演算の直後に、上記第二次複写可能演算を複写し、その複写した演算で引用している複数の箇所で定義されている変数を上記第一次複写可能演算で使用した一時的な変数に置き換え、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の上記第二次複写可能演算を一時的に使用する変数から上記第二次複写可能演算の結果を保持する変数への代入に置き換える、第二次複写可能演算複写手段とを備え、演算で使用している変数がループ内で不変な値を選択的に使用しているためにループ内不変式として移動できない演算をループの外で計算できるように変形することを特徴とする。
【０００８】
第３の発明は、ソースプログラムを解釈して中間コードを生成し最適化を行ってオブジェクトコードを生成するコンパイラにおいて、ループ内で値が不変である変数と結果が不変である演算を検出するループ内不変式検出手段と、演算に使用される変数の全てが、ループ内で不変であるか、ループ内の複数箇所で定義されているがそのいずれかが必ずこの演算に先立って実行されかつそのいずれもがループ内で不変の値が代入されている変数であるかのいずれかである、第一次複写可能演算を検出する第一次複写可能演算検出手段と、演算に使用される変数の全てが、ループ内で不変であるか、ループ内の複数箇所で定義されているがそのいずれかが必ずこの演算に先立って実行されかつそのいずれもがループ内で不変の値が代入されている変数であるか、上記第一次複写可能演算検出手段で検出された第一次複写可能演算の結果であるかのいずれかであり、かついずれの第一次複写可能演算もその結果を代入される変数は１箇所でのみ定義されていてかつ必ずこの演算に先立って実行されているものである、第二次複写可能演算を検出する第二次複写可能演算検出手段と、上記第一次複写可能演算検出手段で検出された第一次複写可能演算に対して、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に第一次複写可能演算を複写し、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の上記第一次複写可能演算を一時的に使用する変数から上記第一次複写可能演算の結果を保持する変数への代入に置き換える、第一次複写可能演算複写手段と、上記第二次複写可能演算検出手段で検出された第二次複写可能演算に対して、複数の箇所で定義されいずれかの定義がこの演算に先立って実行されておりかついずれの定義においてもループ内で不変の値が代入される変数については、この演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に演算を複写し、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の演算を一時的に使用する変数から演算の結果を保持する変数への代入に置き換え、且つ、第一次複写可能演算で定義される変数については、第二次複写可能演算に対し、演算で使用している第一次複写可能演算の、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に複写された第一次複写可能演算の直後に、上記第二次複写可能演算を複写し、その複写した演算で引用している複数の箇所で定義されている変数を上記第一次複写可能演算で使用した一時的な変数に置き換え、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の上記第二次複写可能演算を一時的に使用する変数から上記第二次複写可能演算の結果を保持する変数への代入に置き換え、その上で、上記第二次複写可能演算を、新しく生成した変数に置き換える、第二次複写可能演算複写手段とを備え、演算で使用している変数がループ内で不変な値を選択的に使用しているためにループ内不変式として移動できない演算をループの外で計算できるように変形することを特徴とする。
【０００９】
【作用】
第１の発明にあっては、ループ内不変式検出手段により、ループ内で値が不変である変数と、結果が不変である演算を検出し、第一次複写可能演算検出手段により、演算に使用される変数の全てが、ループ内で不変であるか、ループ内の複数箇所で定義されているがそのいずれかが必ずこの演算に先立って実行されかつそのいずれもがループ内で不変の値が代入されている変数であるかのいずれかである、第一次複写可能演算を検出する。そして、第一次複写可能演算複写手段により、上記第一次複写可能演算検出手段で検出された第一次複写可能演算に対して、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に第一次複写可能演算を複写し、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の上記第一次複写可能演算を一時的に使用する変数から上記第一次複写可能演算の結果を保持する変数への代入に置き換える。これにより、各々の条件下に複写された第一次複写可能演算は、ループ内不変式として扱うことができ、ループ外へ移動することにより、ループの実行時間を短くすることが可能となる。
【００１０】
第２の発明にあっては、第１の発明に加えて更に、第二次複写可能演算検出手段により、演算に使用される変数の全てが、ループ内で不変であるか、上記第一次複写可能演算検出手段で検出された第一次複写可能演算の結果であるかのいずれかであり、かついずれの第一次複写可能演算もその結果を代入される変数は１箇所でのみ定義されていてかつ必ずこの演算に先立って実行されているものである、第二次複写可能演算を検出し、第二次複写可能演算複写手段により、上記第二次複写可能演算検出手段で検出された第二次複写可能演算に対して、演算で使用している第一次複写可能演算の、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に複写された第一次複写可能演算の直後に、上記第二次複写可能演算を複写し、その複写した演算で引用している複数の箇所で定義されている変数を上記第一次複写可能演算で使用した一時的な変数に置き換え、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の上記第二次複写可能演算を一時的に使用する変数から上記第二次複写可能演算の結果を保持する変数への代入に置き換える。これにより、各々の条件下に複写された第一次複写可能演算に加えて第二次複写可能演算も、ループ内不変式として扱うことができ、ループ外へ移動することにより、ループの実行時間をより短くすることが可能となる。
【００１１】
第３の発明にあっては、第１の発明に加えて更に、第二次複写可能演算検出手段により、演算に使用される変数の全てが、ループ内で不変であるか、ループ内の複数箇所で定義されているがそのいずれかが必ずこの演算に先立って実行されかつそのいずれもがループ内で不変の値が代入されている変数であるか、上記第一次複写可能演算検出手段で検出された第一次複写可能演算の結果であるかのいずれかであり、かついずれの第一次複写可能演算もその結果を代入される変数は１箇所でのみ定義されていてかつ必ずこの演算に先立って実行されているものである、第二次複写可能演算を検出し、第二次複写可能演算複写手段により、上記第二次複写可能演算検出手段で検出された第二次複写可能演算に対して、複数の箇所で定義されいずれかの定義がこの演算に先立って実行されておりかついずれの定義においてもループ内で不変の値が代入される変数については、この演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に演算を複写し、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の演算を一時的に使用する変数から演算の結果を保持する変数への代入に置き換え、且つ、第一次複写可能演算で定義される変数については、第二次複写可能演算に対し、演算で使用している第一次複写可能演算の、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に複写された第一次複写可能演算の直後に、上記第二次複写可能演算を複写し、その複写した演算で引用している複数の箇所で定義されている変数を上記第一次複写可能演算で使用した一時的な変数に置き換え、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の上記第二次複写可能演算を一時的に使用する変数から上記第二次複写可能演算の結果を保持する変数への代入に置き換え、その上で、上記第二次複写可能演算を、新しく生成した変数に置き換える。これにより、各々の条件下に複写された第一次複写可能演算に加えて、第一次複写可能演算で定義される変数と、複数の箇所で定義されいずれかの定義がこの演算に先立って実行されかついずれの定義においてもループ内で不変の値が代入される変数の混在する演算も、ループ内不変式として扱うことができ、ループ外へ移動することにより、ループの実行時間をより短くすることが可能となる。
【００１２】
【発明の第１の実施の形態】
次に、本発明の第１の実施の形態について図面を参照して説明する。
【００１３】
【構成の説明】
図１を参照すると、本発明の第１の実施の形態にかかるコンパイラのループ最適化部１０は、ループ内不変式検出手段１１、第一次複写可能演算検出手段１２、第二次複写可能演算検出手段１３、第一次複写可能演算複写手段１４、第二次複写可能演算複写手段１５およびループ内不変式移動手段１６を含み、中間テキスト２１を入力し、それを最適化した中間テキスト２２を出力する。中間テキスト２１は図１１の中間テキスト１０４に、中間テキスト２２は図１１の中間テキスト１０５に、そして、ループ最適化部１０は、図１１の最適化部１０２に、それぞれ相当する。
【００１４】
ループ内不変式検出手段１１は、中間テキスト２１を入力し、ループ内で値が不変である変数および演算結果がループ内で不変となる演算を検索し、記録する。
【００１５】
第一次複写可能演算検出手段１２は、中間テキスト２１とループ内不変式検出手段１１の上記記録を入力し、演算に使用される変数の全てが、ループ内で不変であるか、ループ内の複数箇所で定義されているがそのいずれかが必ずこの演算に先立って実行されかつそのいずれもがループ内で不変の値が代入されている変数であるかのいずれかである、第一次複写可能演算の検出を行い、記録する。
【００１６】
第二次複写可能演算検出手段１３は、中間テキスト２１とループ内不変式検出手段１１および第一次複写可能演算検出手段１２の上記記録を入力し、演算に使用される変数の全てがループ内で不変であるか、第一次複写可能演算検出手段１２で検出された第一次複写可能演算の結果であるかのいずれかであり、かついずれの第一次複写可能演算もその結果を代入される変数は１箇所でのみ定義されていてかつ必ずこの演算に先立って実行されているものである、第二次複写可能演算を検出し、記録する。
【００１７】
第一次複写可能演算複写手段１４は、中間テキスト２１と第一次複写可能演算検出手段１２の上記記録を入力し、第一次複写可能演算検出手段１２で検出された第一次複写可能演算に対して、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に第一次複写可能演算を複写し、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の上記第一次複写可能演算を一時的に使用する変数から上記第一次複写可能演算の結果を保持する変数への代入に置き換え、置き換え後の中間テキストを記録する。
【００１８】
第二次複写可能演算複写手段１５は、第二次複写可能演算検出手段１３の上記記録と第一次複写可能演算複写手段１４による上記置き換え後の中間テキストを入力し、第二次複写可能演算検出手段１３で検出された第二次複写可能演算に対して、演算で使用している第一次複写可能演算の、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に複写された第一次複写可能演算の直後に、上記第二次複写可能演算を複写し、その複写した演算で引用している複数の箇所で定義されている変数を上記第一次複写可能演算で使用した一時的な変数に置き換え、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の上記第二次複写可能演算を一時的に使用する変数から上記第二次複写可能演算の結果を保持する変数への代入に置き換え、置き換え後の中間テキストを記録する。
【００１９】
ループ内不変式移動手段１６は、第二次複写可能演算複写手段１５による上記置き換え後の中間テキストを入力し、その入力した中間テキストに存在するループ内不変式をループ外に移動し、最適化された中間テキスト２２を出力する。
【００２０】
【動作の説明】
次に、本実施の形態のループ最適化部１０の動作について図１乃至図６を参照して詳細に説明する。
【００２１】
ループ内不変式検出手段１１は、中間テキスト２１をループ毎に検索し、ループ内で値が不変である変数と結果が不変である演算を検出し、記録する（図２のステップＡ１）。例えば、図３のような実際のＦｏｒｔｒａｎプログラム片の場合、変数Ｉ１、Ｉ２、Ｓがループ内不変として記録される。
【００２２】
次に第一次複写可能演算検出手段１２は、演算に使用されている変数の全てが、ループ内で不変であるか、ループ内の複数箇所で定義されているがそのいずれかが必ずこの演算に先立って実行されかつそのいずれもがループ内で不変の値が代入されている変数であるかのいずれかである第一次複写可能演算を検出する（図２のステップＡ２）。例えば、図３のような実際のＦｏｒｔｒａｎプログラム片の場合、（３）の演算ＩＸ＊Ｓは、Ｓがループ内不変であり、ＩＸは（１）と（２）の２箇所で定義されており、（１）においてはＩ１、（２）においてはＩ２といういずれもループ内で不変な変数を代入されているため、第一次複写可能演算として認識される。
【００２３】
上記において、検出された演算が１つもなければ、図２の処理は終了する。１つでもあれば、次のステップＡ４に進む（図２のステップＡ３）。
【００２４】
次に第二次複写可能演算検出手段１３は、演算に使用される変数の全てが、ループ内で不変であるか、上記ステップＡ２で検出された第一次複写可能演算の結果であるかのいずれかであり、かついずれの第一次複写可能演算もその結果を代入される変数は１箇所でのみ定義されていてかつ必ずこの演算に先立って実行されているものである第二次複写可能演算の検索を行う（図２のステップＡ４）。例えば、図３のような実際のＦｏｒｔｒａｎプログラム片の場合、（４）の演算Ｔ＋Ｓは、Ｓがループ内不変であり、Ｔは第一次複写可能演算（図３の（３））の結果であるため、第二次複写可能演算として認識される。
【００２５】
次に第一次複写可能演算複写手段１４は、ステップＡ２で検索した第一次複写可能演算に対し、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に演算を複写し、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の第一次複写可能演算を一時的に使用する変数から第一次複写可能演算の結果を保持する変数への代入に置き換える（図２のステップＡ５）。例えば、図３のような実際のＦｏｒｔｒａｎプログラム片に対してこの複写を行った場合を図４に示す。第一次複写可能演算である図３の（３）の演算ＩＸ＊Ｓは、図３の（１）および（２）の直後に複写され、演算によって定義される変数は新しく生成した変数Ｔ１に変更される（図４の（５）および（６））。また、図３の（３）の演算ＩＸ＊Ｓは、上記の新しく生成した変数Ｔ１に置き換えられる（図４の（７））。
【００２６】
第二次複写可能演算検出手段（図２のステップＡ４）において、検出された演算が１つもなければ、図２の処理は終了する。１つでもあれば、次のステップＡ７に進む（図２のステップＡ６）。
【００２７】
次に第二次複写可能演算複写手段１５は、ステップＡ４で検索した第二次複写可能演算に対し、演算で使用している第一次複写可能演算の、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に複写された第一次複写可能演算の直後に、上記第二次複写可能演算を複写し、その複写した演算で引用している複数の箇所で定義されている変数を上記第一次複写可能演算で使用した一時的な変数に置き換え、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の上記第二次複写可能演算を一時的に使用する変数から上記第二次複写可能演算の結果を保持する変数への代入に置き換える（図２のステップＡ７）。例えば、図３のような実際のＦｏｒｔｒａｎプログラム片に対してこの複写を行った場合を図５に示す。第二次複写可能演算である図３の（４）の演算Ｔ＋Ｓは、図４の（５）および（６）の直後に複写され、第一次複写可能演算の結果であるＴはステップＡ３で生成された新しい変数Ｔ１に変更され、演算によって定義される変数は新しく生成した変数Ｔ２に変更される（図５の（８）および（９））。また、図３の（４）の演算Ｔ＋Ｓは、上記の新しく生成した変数Ｔ２に置き換えられる（図５の（１０））。
【００２８】
このようにして変更された図５のようなプログラム片は、従来技術によるループ内不変式の移動の最適化を行うループ内不変式移動手段１６により、図６のように変形され、ループ内の実行命令数が減り、実行時間が短くなる。
【００２９】
【発明の第２の実施の形態】
次に本発明の第２の実施の形態について、図面を参照して詳細に説明する。
【００３０】
第１の実施の形態では、演算で参照する変数は、第二次複写可能演算検出手段１３において第一次複写可能演算で定義される変数またはループ内不変な変数のみとしているが、図７の（６）のＴ＋Ｕのように第一次複写可能演算で定義される変数（Ｔ）と、複数の箇所で定義されいずれかの定義がこの演算に先立って実行されかついずれの定義においてもループ内で不変の値が代入される変数（Ｕ）の混在する場合においても、第一次複写可能演算複写手段１４と第二次複写可能演算複写手段１５を組み合わせることにより、本発明を適用可能である。
【００３１】
上記の場合、複数の箇所で定義されいずれかの定義がこの演算に先立って実行されておりかついずれの定義においてもループ内で不変の値が代入される変数（図７の（６）のＵ）については、第一次複写可能演算複写手段１４（図２のステップＡ５）と同様に、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に演算を複写し、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の演算を一時的に使用する変数から演算の結果を保持する変数への代入に置き換える。例えば、図７のような実際のＦｏｒｔｒａｎプログラム片に対してこの複写を行った場合を図８に示す。図８の（７）、（１０）、（１３）は、第一次複写可能演算複写手段１４によってすでに変更されているものとする。第二次複写可能演算である図７の（６）の演算Ｔ＋Ｕは、図７の（２）および（４）の直後に複写され、第一次複写可能演算の結果であるＴはステップＡ３で生成された新しい変数Ｔ１に変更され、演算によって定義される変数は新しく生成した変数Ｔ２に変更される（図８の（９）および（１２））。
【００３２】
次に、第一次複写可能演算で定義される変数（図７の（６）のＴ）については、第二次複写可能演算（図７の（６）のＴ＋Ｕ）に対し、演算で使用している第一次複写可能演算の、演算で使用しているループ内の複数箇所で定義されている変数の各々の定義の直後に複写された第一次複写可能演算の直後に、上記第二次複写可能演算を複写し、その複写した演算で引用している複数の箇所で定義されている変数を上記第一次複写可能演算で使用した一時的な変数に置き換え、さらに一時的に使用する新しく作成した変数を複写された演算の結果とし、元の上記第二次複写可能演算を一時的に使用する変数から上記第二次複写可能演算の結果を保持する変数への代入に置き換える。例えば、図７のような実際のＦｏｒｔｒａｎプログラム片に対してこの複写を行った場合を図８に示す。図８の（７）、（１０）、（１３）は、第一次複写可能演算複写手段１４によって既に変更されているものとする。第二次複写可能演算である図７の（６）の演算Ｔ＋Ｕは、図８の（７）および（１０）の直後に複写され、ＴはステップＡ３で生成された新しい変数Ｔ１に変更され、演算によって定義される変数は新しく生成した変数Ｔ２に変更される（図８の（８）および（１１））。その上で、第二次複写可能演算（図７の（６）のＴ＋Ｕ）は、新しく生成した変数Ｔ２に置き換えられる（図８の（１４））。
【００３３】
このようにして変更された図８のようなプログラム片は、従来技術によるループ内不変式の移動の最適化を行うループ内不変式移動手段１６により、図９のように変形され、ループ内の実行命令数が減り、実行時間が短くなる。
【００３４】
【発明の他の実施の形態】
図１０は本発明を実施するコンピュータの構成例を示すブロック図である。この例のコンピュータは、高級言語で記述されたソースプログラム２００を格納する外部記憶装置２０１と、生成された機械語命令のオブジェクトプログラム３００を格納する外部記憶装置３０１と、外部記憶装置２０１からソースプログラム２００を入力し、また外部記憶装置３０１へオブジェクトプログラム３００を出力する入出力部３１と、ソースプログラム２００を構文解析部で処理して得た中間テキスト２１、この中間テキスト２１を最適化して得た中間テキスト２２を記憶すると共に、最適化処理の過程で得られる各種の情報を一時的に記憶するワーク領域３２を有するメモリ３３と、コンパイル用プログラム３４を記憶する磁気ディスク装置等のコンピュータ可読記録媒体３５と、入出力部３１とメモリ３３とコンピュータ可読記録媒体３５に接続された中央処理装置３６とで構成される。
【００３５】
コンピュータ可読記録媒体３５に記録されたコンパイル用プログラム３４は、中央処理装置３６に読み取られ、その動作を制御することにより、当該コンピュータを前述した第１、第２の実施の形態にかかるループ最適化部１０を有するコンパイラとして機能させる。この際、メモリ３３のワーク領域３２は、ループ最適化部１０における各手段間で受け渡される情報が一時的に記憶される。例えば、第１の実施の形態にあっては、ループ内不変式検出手段１１は、ループ内で値が不変である変数および演算結果がループ内で不変となる演算を検索してワーク領域３２に記録する。第一次複写可能演算検出手段１２は、第一次複写可能演算の検出を行う際に、ワーク領域３２を参照してループ内で不変である変数等を認識し、検出した第一次複写可能演算をワーク領域３２に記録する。第二次複写可能演算検出手段１３は、第二次複写可能演算を検出する際に、ワーク領域３２を参照してループ内で不変である変数および検出された第一次複写可能演算等を認識し、検出した第二次複写可能演算をワーク領域に記録する。第一次複写可能演算複写手段１４は、ワーク領域３２を参照して第一次複写可能演算検出手段１２で検出された第一次複写可能演算等を認識し、中間テキスト２１に対して変形を施した図４のような中間テキストをワーク領域３２に記録する。第二次複写可能演算複写手段１５は、ワーク領域３２を参照して第二次複写可能演算検出手段１３で検出された第二次複写可能演算および第一次複写可能演算複写手段１４の処理結果等を認識し、自らの処理を加えて図５のような中間テキストをワーク領域３２に記録する。ループ内不変式移動手段１６は、ワーク領域３２に記録された図５のような中間テキストを入力して、ループ内の不変式の移動に関する最適化処理を施し、その結果を中間テキスト２２としてメモリ３３に記録する。第２の実施の形態においても同様に、ループ内不変式検出手段１１、第一次複写可能演算検出手段１２、第二次複写可能演算検出手段１３、第一次複写可能演算複写手段１４、第二次複写可能演算複写手段１５およびループ内不変式移動手段１６の間で、ワーク領域３２を通じて必要なデータが受け渡される。
【００３６】
【発明の効果】
以上説明したように本発明は、ループ内で不変でない演算であっても所定の条件を満たすときはそれをループ内不変式に変形することができる。このため、ループ内不変式の移動の最適化をより多くの演算について実施でき、ループ中で実行される命令数の削減により実行時間を大幅に短縮することが可能となる。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態を示すブロック図である。
【図２】本発明の第１の実施の形態の処理例を示すフローチャートである。
【図３】本発明の第１の実施の形態が適用できるＦｏｒｔｒａｎのプログラム片である。
【図４】本発明の第１の実施の形態における第一次複写可能演算複写手段を適用した後の中間テキストのイメージを表すＦｏｒｔｒａｎのプログラム片である。
【図５】本発明の第１の実施の形態における第二次複写可能演算複写手段を適用した後の中間テキストのイメージを表すＦｏｒｔｒａｎのプログラム片である。
【図６】本発明の第１の実施の形態におけるループ内不変式移動手段を適用した後の中間テキストのイメージを表すＦｏｒｔｒａｎのプログラム片である。
【図７】本発明の第２の実施の形態が適用できるＦｏｒｔｒａｎのプログラム片である。
【図８】本発明の第２の実施の形態における第一次複写可能演算複写手段および第二次複写可能演算複写手段を適用した後の中間テキストのイメージを表すＦｏｒｔｒａｎのプログラム片である。
【図９】本発明の第２の実施の形態におけるループ内不変式移動手段を適用した後の中間テキストのイメージを表すＦｏｒｔｒａｎのプログラム片である。
【図１０】本発明を適用したコンピュータの構成例を示すブロック図である。
【図１１】コンパイラの一般的な構成を示すブロック図である。
【符号の説明】
１０　ループ最適化部
１１　ループ内不変式検出手段
１２　第一次複写可能演算検出手段
１３　第二次複写可能演算検出手段
１４　第一次複写可能演算複写手段
１５　第二次複写可能演算複写手段
１６　ループ内不変式移動手段
２１　中間テキスト
２２　中間テキスト
【図１】
2004062489.tif 000003
【図２】
2004062489.tif 000004
【図３】
2004062489.tif 000005
【図４】
2004062489.tif 000006
【図５】
2004062489.tif 000007
【図６】
2004062489.tif 000008
【図７】
2004062489.tif 000009
【図８】
2004062489.tif 000010
【図９】
2004062489.tif 000011
【図１０】
2004062489.tif 000012
【図１１】
2004062489.tif 000013